孫榮凱　衣曉　薛興亮

摘 要： 覆蓋問(wèn)題是無(wú)線(xiàn)傳感器網(wǎng)絡(luò)完成目標(biāo)監(jiān)測(cè)和信息獲取任務(wù)的前提。為了更貼近實(shí)際地描述區(qū)域覆蓋問(wèn)題，采用概率感知模型，并把對(duì)被監(jiān)測(cè)區(qū)域的覆蓋問(wèn)題轉(zhuǎn)化為對(duì)可數(shù)個(gè)點(diǎn)目標(biāo)的覆蓋問(wèn)題，然后利用點(diǎn)覆蓋算法對(duì)整個(gè)監(jiān)測(cè)區(qū)域的覆蓋問(wèn)題進(jìn)行了研究。最后通過(guò)仿真實(shí)驗(yàn)，對(duì)網(wǎng)絡(luò)采用單重覆蓋與多重覆蓋的效果進(jìn)行了比較，驗(yàn)證了區(qū)域多重覆蓋的優(yōu)越性。

關(guān)鍵詞： 無(wú)線(xiàn)傳感器網(wǎng)絡(luò)； 概率感知模型； 區(qū)域覆蓋； 集中式算法

中圖分類(lèi)號(hào)： TN921?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2015）01?0001?04

Abstract： Region coverage is a basic premise to realize target monitoring and information acquisition in wireless sensor network. In order to describe the region coverage more closely to the actuality， the probabilistic sensing model is applied， and the coverage of the monitored area is turned to the coverage of the countable point targets. The coverage of the whole monitored area is investigated by means of the point target coverage algorithm. The effects of single coverage algorithm and multiple coverage algorithm are compared by means of simulation experiment. The superiority of multiple coverage algorithm was verified.

Keywords： wireless sensor network； probability perceptual model； region coverage； centralized algorithm

0 引 言

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的覆蓋問(wèn)題與網(wǎng)絡(luò)能效性和節(jié)點(diǎn)連接性密切相關(guān)，是網(wǎng)絡(luò)完成目標(biāo)監(jiān)測(cè)和信息獲取任務(wù)的前提，是無(wú)線(xiàn)傳感器網(wǎng)絡(luò)設(shè)計(jì)和規(guī)劃面臨的基本問(wèn)題之一[1?2]。在實(shí)際應(yīng)用中，傳感器對(duì)目標(biāo)的感知能力是隨著距離的增大而不斷衰減的，因而概率感知模型[3]更貼近實(shí)際情況。本文基于概率感知模型，把被監(jiān)測(cè)區(qū)域的覆蓋問(wèn)題轉(zhuǎn)化為對(duì)可數(shù)個(gè)點(diǎn)目標(biāo)的覆蓋問(wèn)題，利用點(diǎn)覆蓋算法思想對(duì)區(qū)域覆蓋進(jìn)行了研究，并通過(guò)仿真實(shí)驗(yàn)，對(duì)網(wǎng)絡(luò)采用單重覆蓋與多重覆蓋的效果進(jìn)行了比較。

1 區(qū)域到點(diǎn)目標(biāo)的轉(zhuǎn)化

為了簡(jiǎn)化問(wèn)題，本文假設(shè)被監(jiān)測(cè)區(qū)域內(nèi)已經(jīng)部署好所有節(jié)點(diǎn)，節(jié)點(diǎn)已完成自身定位[4?6]，節(jié)點(diǎn)不可移動(dòng)且無(wú)新節(jié)點(diǎn)加入，同時(shí)采用的傳感器節(jié)點(diǎn)是同構(gòu)的[7]，節(jié)點(diǎn)的感知半徑固定不變。

1.1 基于布爾感知模型的區(qū)域劃分思想

先就布爾感知模型的情況進(jìn)行研究，如圖1所示。在已經(jīng)部署好傳感器節(jié)點(diǎn)的被監(jiān)測(cè)區(qū)域中，每個(gè)傳感器節(jié)點(diǎn)感知圓盤(pán)的邊界線(xiàn)相互交割，形成可數(shù)條相交的弧線(xiàn)段；這些弧線(xiàn)段圍成一個(gè)個(gè)最小區(qū)域塊，這些區(qū)域塊不可再分，且所有區(qū)域塊的并集為整個(gè)被監(jiān)測(cè)區(qū)域。此時(shí)，這些區(qū)域塊可看作為一個(gè)個(gè)點(diǎn)目標(biāo)，只要覆蓋了這些點(diǎn)目標(biāo)，就可以覆蓋整個(gè)被監(jiān)測(cè)區(qū)域。這樣，區(qū)域覆蓋問(wèn)題就轉(zhuǎn)化成為點(diǎn)覆蓋問(wèn)題。

1.2 區(qū)域塊權(quán)值的求取

應(yīng)當(dāng)注意，這個(gè)以點(diǎn)目標(biāo)覆蓋思想進(jìn)行劃分的區(qū)域覆蓋算法與點(diǎn)覆蓋算法還是有所區(qū)別的。因?yàn)辄c(diǎn)覆蓋算法中，在工作節(jié)點(diǎn)競(jìng)選時(shí)進(jìn)行的傳感器節(jié)點(diǎn)貢獻(xiàn)值[8]大小比較中，所有目標(biāo)均為同等地位，只是以傳感器節(jié)點(diǎn)能夠覆蓋的尚未被覆蓋的點(diǎn)目標(biāo)個(gè)數(shù)來(lái)衡量貢獻(xiàn)值大小。而在經(jīng)過(guò)劃分的區(qū)域覆蓋算法中，對(duì)于每一個(gè)被看作為點(diǎn)目標(biāo)的區(qū)域塊而言，可能幾個(gè)區(qū)域塊的面積之和還不如另一個(gè)區(qū)域塊的面積大，因此應(yīng)當(dāng)計(jì)算每個(gè)小區(qū)域塊的面積，以此面積作為此區(qū)域塊對(duì)應(yīng)虛擬點(diǎn)目標(biāo)的權(quán)值，這樣在節(jié)點(diǎn)競(jìng)選時(shí)，就以該節(jié)點(diǎn)能夠覆蓋的尚未被覆蓋區(qū)域塊的權(quán)值之和來(lái)確定其貢獻(xiàn)值大小。

1.3 擴(kuò)展至概率感知模型的區(qū)域劃分思想

按照前面的區(qū)域劃分原則，被監(jiān)測(cè)區(qū)域被劃分為可數(shù)個(gè)最小區(qū)域塊。然而，對(duì)于概率感知模型，因?yàn)樽钚^(qū)域塊上的任意一點(diǎn)到節(jié)點(diǎn)的距離不同，從而任意一點(diǎn)被感知的概率不同，而且這樣的點(diǎn)是無(wú)窮多的，因此難以用明確的形式表征節(jié)點(diǎn)對(duì)區(qū)域塊的感知概率。這里介紹一種簡(jiǎn)化的概率感知模型[9]，既可以滿(mǎn)足節(jié)點(diǎn)概率感知模型中感知概率依距離增加而遞減的特性，又便于表示節(jié)點(diǎn)對(duì)每個(gè)區(qū)域塊的感知概率，如圖3所示。

圖3是由圓心相同而半徑不同的圓組成，所有半徑的值都介于0和[R]之間。任意兩個(gè)相鄰的圓，假設(shè)其半徑分別是[Ri，][Ri-1i=1，2，…]，由這兩個(gè)圓構(gòu)成圓環(huán)的被感知概率介于[11+ξ?Riσ]和[11+ξ?Ri-1σ]之間。而如果所形成的圓環(huán)的被感知概率用其最小概率值[11+ξ?Riσ]代替，則節(jié)點(diǎn)[O]對(duì)監(jiān)測(cè)區(qū)域內(nèi)任意一點(diǎn)[P]處的感知概率為：[p（O，P）=0，d（O，P）>R11+ξ?Riσ，Ri-1≤d（O，P）≤Ri≤R] （3）

其中，[d（O，P）]為節(jié)點(diǎn)[O]與目標(biāo)[P]之間的歐氏距離；[R]為設(shè)定的閾值，由節(jié)點(diǎn)感知單元的物理特性決定；[ξ]和[σ]為與傳感器物理特性有關(guān)的類(lèi)型參數(shù)，通常[σ]取值為[1，4]之間的整數(shù)，而[ξ]是個(gè)可調(diào)的參數(shù)。

本文把節(jié)點(diǎn)感知圓盤(pán)中每個(gè)[Ri]和[Ri+1]之間的部分稱(chēng)之為感知圓環(huán)，依據(jù)此概率模型，每個(gè)感知圓環(huán)內(nèi)任何一點(diǎn)的被感知概率是相等的。假設(shè)[Ri]和[Ri+1]之間的差值為[φii=1，2，…，]很明顯只要[φi]值越小，[Ri]和[Ri+1]的值就會(huì)越接近，則此概率模型就越接近于實(shí)際情況。

本文中討論的區(qū)域劃分問(wèn)題，即可以依據(jù)此概率感知模型加以擴(kuò)展，由所有節(jié)點(diǎn)的感知圓環(huán)的邊界線(xiàn)相互交割而形成一個(gè)個(gè)最小區(qū)域塊，每個(gè)最小區(qū)域塊均滿(mǎn)足任意一個(gè)節(jié)點(diǎn)對(duì)此區(qū)域塊中的任意一點(diǎn)僅有一個(gè)感知概率。而此時(shí)每個(gè)區(qū)域塊都可以被看成一個(gè)點(diǎn)目標(biāo)，區(qū)域覆蓋問(wèn)題同樣轉(zhuǎn)化為對(duì)點(diǎn)目標(biāo)的覆蓋問(wèn)題。

2 基于概率感知模型的區(qū)域覆蓋集中式算法

在概率模型的覆蓋問(wèn)題中，一般采用設(shè)定一個(gè)概率值[η0<η<1]的方法作為覆蓋要求。如果在覆蓋區(qū)域內(nèi)，每一點(diǎn)處的覆蓋概率都大于設(shè)定的概率值[η]，則認(rèn)為已達(dá)到了覆蓋要求，此區(qū)域完成覆蓋。在本文中，假設(shè)被監(jiān)測(cè)區(qū)域中的節(jié)點(diǎn)存在足夠的冗余，且區(qū)域已劃分完畢，即此時(shí)的被監(jiān)測(cè)區(qū)域可看作為可數(shù)個(gè)已編號(hào)的最小區(qū)域塊的集合；同時(shí)所有傳感器節(jié)點(diǎn)覆蓋的區(qū)域塊及對(duì)應(yīng)面積都已確定，并且所有節(jié)點(diǎn)均可確定自身剩余能量以及落入其感知范圍內(nèi)的最小區(qū)域塊編號(hào)、權(quán)值以及感知概率。

2.1 單重覆蓋的集中式算法

所謂概率感知模型中的單重覆蓋即為選取一個(gè)工作節(jié)點(diǎn)集，保證被監(jiān)測(cè)區(qū)域中每個(gè)區(qū)域塊的被覆蓋概率均可達(dá)到覆蓋要求[η。]

2.1.1 算法思想

該算法的思想為被監(jiān)測(cè)區(qū)域中所有的普通傳感器節(jié)點(diǎn)均向中心節(jié)點(diǎn)上報(bào)其感知信息。與布爾模型情況有所區(qū)別，感知信息應(yīng)除了包括該節(jié)點(diǎn)的位置信息、剩余能量以及覆蓋的所有最小區(qū)域塊的編號(hào)、權(quán)值以外，還應(yīng)包括該節(jié)點(diǎn)覆蓋的所有最小區(qū)域塊相應(yīng)的感知概率。當(dāng)所有的節(jié)點(diǎn)向中心節(jié)點(diǎn)上報(bào)完畢后，中心節(jié)點(diǎn)將上報(bào)信息分類(lèi)存儲(chǔ)并進(jìn)行統(tǒng)計(jì)，對(duì)于任意一個(gè)最小區(qū)域塊，計(jì)算出可令其達(dá)到覆蓋要求[η]的全部節(jié)點(diǎn)集的集合[G1，G2，G3，…]。選取節(jié)點(diǎn)集[Gj（j=1，2，…）]的原則應(yīng)設(shè)定為：節(jié)點(diǎn)集合中全部節(jié)點(diǎn)對(duì)該區(qū)域塊的聯(lián)合概率可達(dá)到覆蓋要求，不同的集合之間可以存在交集，但是其中每一個(gè)集合都不能成為另外任何一個(gè)集合的子集，即：

然后，對(duì)所有區(qū)域塊的可滿(mǎn)足其覆蓋要求的節(jié)點(diǎn)集合個(gè)數(shù)進(jìn)行比較，擁有這樣的集合數(shù)目最少的也就是最少覆蓋區(qū)域塊。繼而從此最少覆蓋區(qū)域塊的滿(mǎn)足其覆蓋要求的節(jié)點(diǎn)集合中，根據(jù)一定的競(jìng)爭(zhēng)規(guī)則選取一個(gè)進(jìn)入工作狀態(tài)。競(jìng)爭(zhēng)規(guī)則為：該節(jié)點(diǎn)集合中節(jié)點(diǎn)個(gè)數(shù)盡可能少，節(jié)點(diǎn)集合中剩余能量最少的節(jié)點(diǎn)的剩余能量盡可能多，節(jié)點(diǎn)集合與已確定工作的節(jié)點(diǎn)集合中元素重合個(gè)數(shù)盡可能多。

在確定了工作節(jié)點(diǎn)集合之后，中心節(jié)點(diǎn)更新未被覆蓋區(qū)域塊集合，只要未被覆蓋區(qū)域塊集合不為空，則需要繼續(xù)在未被覆蓋區(qū)域塊集合中選取下一個(gè)最少覆蓋區(qū)域塊，繼而選取工作節(jié)點(diǎn)集合，直至所有區(qū)域塊都達(dá)到覆蓋要求。

2.1.2 算法流程

該算法流程圖如圖4所示。

2.2 多重覆蓋的集中式算法

對(duì)于概率感知模型，多重覆蓋需要確保被監(jiān)測(cè)區(qū)域中的每個(gè)區(qū)域塊都能被多個(gè)節(jié)點(diǎn)集合覆蓋，而這些節(jié)點(diǎn)集合的要求是對(duì)區(qū)域塊的覆蓋概率達(dá)到覆蓋要求[η]且相互不相交。

其后的算法步驟，雙重覆蓋與單重覆蓋完全一致，并且[k（k>2）]重覆蓋的情況可以按照雙重覆蓋的情況進(jìn)行類(lèi)推。多重覆蓋算法僅僅是對(duì)每個(gè)最小區(qū)域塊選取達(dá)到覆蓋要求節(jié)點(diǎn)集合的原則與單重覆蓋算法有所不同，其算法流程與單重覆蓋算法完全一致，因此多重覆蓋的算法流程框圖可參看圖4。

3 仿真分析

在仿真中，工作節(jié)點(diǎn)集的工作輪次即為整個(gè)網(wǎng)絡(luò)的生命周期[10]。在對(duì)被監(jiān)測(cè)區(qū)域?qū)嵭胁煌采w標(biāo)準(zhǔn)的效果進(jìn)行比較時(shí)，本文采取網(wǎng)絡(luò)覆蓋質(zhì)量指標(biāo)[11]來(lái)刻畫(huà)區(qū)域多重覆蓋的重要意義，從下面兩個(gè)方面進(jìn)行：

3.1 網(wǎng)絡(luò)的監(jiān)測(cè)概率

當(dāng)障礙物在節(jié)點(diǎn)感知圓盤(pán)內(nèi)的出現(xiàn)概率為[pc]時(shí)，對(duì)區(qū)域采取多重覆蓋對(duì)比僅采取單重覆蓋，可極大提高網(wǎng)絡(luò)監(jiān)測(cè)概率，如圖5所示。

3.2 網(wǎng)絡(luò)的未達(dá)覆蓋要求概率

當(dāng)節(jié)點(diǎn)自身存在失效概率[ps]時(shí)，采取多重覆蓋對(duì)比僅采取單重覆蓋，會(huì)遠(yuǎn)遠(yuǎn)降低網(wǎng)絡(luò)未達(dá)覆蓋要求的概率，如圖6所示。

通過(guò)仿真對(duì)比發(fā)現(xiàn)，網(wǎng)絡(luò)采用雙重覆蓋時(shí)的生命周期幾乎是網(wǎng)絡(luò)采用單重覆蓋時(shí)的一半，這是因?yàn)榫W(wǎng)絡(luò)采用雙重覆蓋時(shí)每一輪次使用的節(jié)點(diǎn)遠(yuǎn)遠(yuǎn)多于網(wǎng)絡(luò)采用單重覆蓋時(shí)使用的節(jié)點(diǎn)。通過(guò)對(duì)網(wǎng)絡(luò)監(jiān)測(cè)概率和網(wǎng)絡(luò)未達(dá)覆蓋要求概率兩個(gè)方面的比較可知，網(wǎng)絡(luò)采用雙重覆蓋要遠(yuǎn)遠(yuǎn)優(yōu)于采用單重覆蓋。因此當(dāng)對(duì)傳感器網(wǎng)絡(luò)的監(jiān)測(cè)效果要求較高時(shí)，雙重覆蓋相對(duì)于單重覆蓋具有較高的優(yōu)越性。

4 結(jié) 語(yǔ)

本文基于概率感知模型，依據(jù)節(jié)點(diǎn)感知圓盤(pán)之間的相互關(guān)系，將被監(jiān)測(cè)區(qū)域劃分為可數(shù)個(gè)最小區(qū)域塊的并集，由此將區(qū)域覆蓋問(wèn)題轉(zhuǎn)化為點(diǎn)覆蓋問(wèn)題，最終通過(guò)改進(jìn)的點(diǎn)覆蓋中的貪婪式算法給予解決；并通過(guò)仿真實(shí)驗(yàn)對(duì)網(wǎng)絡(luò)采用單重覆蓋與多重覆蓋的效果進(jìn)行了比較，驗(yàn)證了區(qū)域多重覆蓋在監(jiān)測(cè)和覆蓋概率方面的優(yōu)越性。

參考文獻(xiàn)

[1] 孫利民，李建中，陳渝，等.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.

[2] 許毅.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)原理及方法[M].北京：清華大學(xué)出版社，2012.

[3] 趙靜，曾建潮.無(wú)線(xiàn)多媒體傳感器網(wǎng)絡(luò)感知模型與數(shù)量估計(jì)[J].軟件學(xué)報(bào)，2012，23（8）：2104?2114.

[4] LU J， SUDA T.Coverage?aware self?scheduling in sensor networks [C]// Proceedings of 2003 IEEE 18th Annual Workshop on Computer Communications. [S.l.]： IEEE， 2003： 117?123.

[5] 衣曉，劉瑜.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)Range?free自身定位算法仿真分析[J].海軍航空工程學(xué)院學(xué)報(bào)，2009，24（4）：369?375.

[6] 劉瑜，衣曉，何友.基于分治求精的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].系統(tǒng)工程與電子技術(shù)，2012，34（9）：1906?1913.

[7] 李海波，杜慶偉.一種能量有效的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)覆蓋控制算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2011，32（2）：233?236.

[8] LIU Yu， WANG Yu?mei， ZHANG Lin. Approximation for a scheduling problem with application in wireless networks [J]. Science China （Mathematics）， 2010， 29（06）： 62?66.

[9] 薛興亮，衣曉，馬德良，等.基于概率感知模型的邊界線(xiàn)多重覆蓋算法研究[J].揚(yáng)州大學(xué)學(xué)報(bào)，2013，16（3）：16?23.

[10] LIU Ying， YANG Zhen， MEI Zhong?hui. Research on adaptive compression coding for network coding in wireless sensor network [J]. Journal of Electronics， 2012， 29（05）： 415?421.

[11] 張碩，蒲菊華，劉玉恒.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)覆蓋質(zhì)量問(wèn)題[J].北京航空航天大學(xué)學(xué)報(bào)，2009，35（5）：631?635.