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

孫榮凱　衣曉　薛興亮

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

關鍵詞： 無線傳感器網絡； 概率感知模型； 區域覆蓋； 集中式算法

中圖分類號： 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 引 言

無線傳感器網絡的覆蓋問題與網絡能效性和節點連接性密切相關，是網絡完成目標監測和信息獲取任務的前提，是無線傳感器網絡設計和規劃面臨的基本問題之一[1?2]。在實際應用中，傳感器對目標的感知能力是隨著距離的增大而不斷衰減的，因而概率感知模型[3]更貼近實際情況。本文基于概率感知模型，把被監測區域的覆蓋問題轉化為對可數個點目標的覆蓋問題，利用點覆蓋算法思想對區域覆蓋進行了研究，并通過仿真實驗，對網絡采用單重覆蓋與多重覆蓋的效果進行了比較。

1 區域到點目標的轉化

為了簡化問題，本文假設被監測區域內已經部署好所有節點，節點已完成自身定位[4?6]，節點不可移動且無新節點加入，同時采用的傳感器節點是同構的[7]，節點的感知半徑固定不變。

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

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

1.2 區域塊權值的求取

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

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

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

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

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

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

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

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

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

2.1 單重覆蓋的集中式算法

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

2.1.1 算法思想

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

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

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

2.1.2 算法流程

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

2.2 多重覆蓋的集中式算法

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

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

3 仿真分析

在仿真中，工作節點集的工作輪次即為整個網絡的生命周期[10]。在對被監測區域實行不同覆蓋標準的效果進行比較時，本文采取網絡覆蓋質量指標[11]來刻畫區域多重覆蓋的重要意義，從下面兩個方面進行：

3.1 網絡的監測概率

當障礙物在節點感知圓盤內的出現概率為[pc]時，對區域采取多重覆蓋對比僅采取單重覆蓋，可極大提高網絡監測概率，如圖5所示。

3.2 網絡的未達覆蓋要求概率

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

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

4 結 語

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

參考文獻

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

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

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

[6] 劉瑜，衣曉，何友.基于分治求精的無線傳感器網絡節點定位算法[J].系統工程與電子技術，2012，34（9）：1906?1913.

[7] 李海波，杜慶偉.一種能量有效的無線傳感器網絡覆蓋控制算法[J].小型微型計算機系統，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] 張碩，蒲菊華，劉玉恒.無線傳感器網絡覆蓋質量問題[J].北京航空航天大學學報，2009，35（5）：631?635.