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

孫榮凱　衣曉　薛興亮

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 單重覆蓋的集中式算法

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

2.1.1 算法思想

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

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

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

2.1.2 算法流程

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

2.2 多重覆蓋的集中式算法

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

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

3 仿真分析

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

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

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

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

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

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

4 結(jié) 語

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

參考文獻

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

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

[3] 趙靜，曾建潮.無線多媒體傳感器網(wǎng)絡(luò)感知模型與數(shù)量估計[J].軟件學報，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ǎng)絡(luò)Range?free自身定位算法仿真分析[J].海軍航空工程學院學報，2009，24（4）：369?375.

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

[7] 李海波，杜慶偉.一種能量有效的無線傳感器網(wǎng)絡(luò)覆蓋控制算法[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] 薛興亮，衣曉，馬德良，等.基于概率感知模型的邊界線多重覆蓋算法研究[J].揚州大學學報，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ǎng)絡(luò)覆蓋質(zhì)量問題[J].北京航空航天大學學報，2009，35（5）：631?635.