基于感知概率的無線傳感器網絡ｋ重覆蓋算法

摘 要:基于布爾感知的無線傳感器網絡多重覆蓋控制模型未考慮實際應用中環境因素對節點感知能力的影響，為彌補這種不足，提出了一種分布式k重覆蓋算法(KCAPSM)，該算法采用了感知概率模型，依據節點感知能力的強弱，將監測區域中的任一點被相關節點監測的情況賦值為某一概率，并通過節點與鄰居交換信息，根據能量大小競選找出k組不相交工作節點集，保證監測區域中每一點被k重覆蓋。實驗表明，KCAPSM算法讓冗余節點處于休眠狀態，節省了網絡能量，優化了資源。

關鍵詞:無線傳感器網絡; 感知概率模型; k重覆蓋

中圖分類號:TP393文獻標志碼:A

文章編號:1001-3695(2009)09-3484-03

doi:10.3969/j.issn.1001-3695.2009.09.080

k-coverage algorithm based on probabilistic sensing model in WSN

JIANG Li-ping， WANG Liang-min， XIONG Shu-ming， ZHAN Yong-zhao

(School of Computer Science Telecommunications Engineering， Jiangsu University， Jiangsu Zhenjiang 212013， China)

Abstract:Binary-detection model based method for k-coverage controlling in wireless sensor network is not practicable without consideration of the environment factors. This paper proposed a k-coverage distributed algorithm based on probabilistic sensing model (KCAPSM). Gave any point in the target area sensed by a sensorvalue based on the sensing capability， and in KCAPSM a sensor compared its residual energy with the neighborhood. They cooperated to construct k working covers that provided probabilistic k-coverage for the whole target region. Experimental results display that KCAPSM made the redundant nodes sleeping， save the energy of the network， and optimize the resources.

Key words:wireless sensor Network(WSN); probabilistic sensing model; k-coverage

0 引言

無線傳感器網絡(WSN)通過無線節點的感知模塊獲取外部環境信息，然后通過無線信道傳輸給基站[1]。然而無線節點的計算能力、電池能量以及無線通信能力的極端有限決定了節點獲取信息的脆弱性，在類似于軍事應用、森林火災檢測等關鍵應用中，如何保障檢測質量成為研究的關鍵問題。通常在監測的目標區域中每個點至少處于k個節點的共同感知范圍內來提供冗余數據，以備份和容錯的多重覆蓋模式彌補單重覆蓋在采集數據可靠性方面的不足。

目前覆蓋控制的文獻[2～4]大多采用基于布爾感知模型，即0/1模型。節點感知半徑內發生的事件以概率1感知，而半徑之外的事件感知率為0。實際應用中，傳感器的感知能力是逐步削弱的，任意傳感器節點對目標監控區域內的任一目標點的探測貢獻量定義為該節點對該目標點的感知強度，文獻[5]給出了相關函數式。為更貼近實際應用，本文提出了一種分布式算法(KCAPSM)，采用了感知概率模型，依據節點感知能力的強弱，將監測區域中的任一點被該節點監測的情況賦值為某一概率，可以適用于因節點能量減弱而引起監測結果準確性變化的實際應用中。基于該模型，提出一種工作節點有效選擇算法，通過節點與鄰居交換信息決定其工作狀態，保證區域中的每個點在任何時刻都至少被k個不同節點以某個概率感知。

1 網絡模型及相關概念

1.1 網絡模型

無線傳感器節點通常采用飛機播撒等方式進行布置[6]，因而假設傳感器節點在目標區域中呈隨機分布，且每個節點的感知范圍為半徑相同的圓形區域，節點的通信范圍大于等于兩倍的節點感知半徑。Wang等人[7]已經證明了當通信范圍Rp大于等于感知范圍Rs的兩倍時，k重覆蓋的網絡一定是k度連通的網絡，因而k覆蓋保證了網絡的k連通性。此外，本文采用與文獻[4]相同的網絡模型:假設覆蓋區域已經部署了足夠密度的傳感器節點，通過喚醒—休眠策略來決定哪些節點工作以保證k覆蓋，哪些休眠以節省能量;要求所有節點在部署之后不再移動，無須人為地進行維護(unattended);其次，網絡中維護一個弱同步時鐘，如達到秒級時間同步。

1.2 相關概念

借鑒文獻[3]的思想，將區域覆蓋問題看成區域內所有點被覆蓋的問題。本文基于感知概率的覆蓋模型，每個節點通過與鄰居交換信息，并根據能量大小競選找出k組不相交工作節點，確保監測區域中每一點的覆蓋概率均大于給定值pth(目標被發現的極限概率)，最終實現無線傳感器網絡的k重覆蓋。以下給出相關概念。

定義1 感知概率。依據節點感知能力的強弱，將監測區域中的某一點被相關節點監測的情況賦值為某一概率p(0

定義2 k重覆蓋。監測區域中任何一點至少同時處于k個節點感知范圍內，即被k個節點覆蓋。

定義3 si的鄰居N(si)。與節點si之間的距離d(si， sn)小于等于通信范圍Rp的節點的集合，即

N(si)={sn∈N|d(si，sn)≤Rp;n≠i}(1)

其中:d(si， sn)表示節點si與節點sn之間的距離;Rp表示節點的通信范圍;N表示所有節點集合。

定義4 區域中某一點u的覆蓋率。



p(u，si)=0if Rs≤d(u，si)

e-εdif Rs-Re

1 if d(u，si)≤Rs-Re(2)

其中:d=d(u， si)-(Rs-Re)，ε為參數，表示傳感器節點的物理特性;Re表示節點監測中的不確定因素;d(u， si)表示u和節點si之間的距離。如果u的覆蓋率滿足p≥pth，則u被檢測到;否則，u未被檢測到。

2 KCAPSM算法

KCAPSM算法按輪次運行，每一輪分為三個階段，即初始化、活躍和工作階段。初始化階段完成候選節點的選取;活躍階段則產生工作節點集合;在工作階段，工作節點將收集的數據傳送到基站，而其他節點則處于睡眠狀態。其中，初始化階段時間為Td，活躍時間為Tj，工作時間為Tw。

2.1 初始化階段

初始化階段，節點通過與鄰居的信息交換，協作完成候選節點的選取:

a)開始所有節點處于就緒狀態(ready)，并隨機分布在某一層，在Rp范圍內廣播hello消息(包括節點ID)。為避免每一輪過多的鄰居被選為候選節點，引入back-off機制，分別為每個就緒節點設置一個隨機時間Twaiting∈[0，Td]。

如果節點在Twaiting時間內，未收到鄰居的hello消息，則將自己的狀態設為候選狀態(candidate)。如果節點在Twaiting時間內，收到了來自不同層鄰居發來的hello消息，則判斷鄰居sj對si的覆蓋率p(si，sj):(a)如果在某一邏輯層有p(si，sj)pth，則取消節點的隨機時間Twaiting，以及候選資格。

b)經過時間Td，所有候選節點廣播botify消息(包括ID、能量、狀態、所在層等信息)。如果候選節點能量Ecurr小于閾值Emin時，則將自己狀態設為睡眠狀態(sleepling)。Emin根據3.1節的能量模型計算。

2.2 基于感知概率的k重覆蓋算法

Td結束，進入活躍階段。活躍階段主要完成k組不相交工作節點選取并保證網絡覆蓋質量。

首先，每個候選節點在廣播notify消息后，均要運行本算法，多次循環迭代確定是否成為工作節點。這里建立k個邏輯層以實現k重覆蓋。其中每一邏輯層由一組不相交的工作節點組成，這些工作節點保證目標區域中每一點被監測到的概率不低于門限值pth。每一邏輯層工作節點的競選遵循:節點通過與鄰居交換信息且多次循環迭代，確定自己是否成為某邏輯層的工作節點，判斷條件是pactive=1。如果為1且滿足覆蓋要求，則宣布成為某邏輯層的工作節點。當節點能量小于Emin時，就不參與競選。

在一個監測區域R中，覆蓋整個區域R的節點數量與節點的傳感半徑Rs直接相關，文獻[8]給出了覆蓋一個區域R需要最少工作節點數目的公式:

nπR2s/Rarea=2π/27(3)

其中:n表示節點數量;Rarea表示監控區域面積。在感知概率情況下，為確保節點覆蓋率，由p(s)=e-ε-d≥pth，計算得近似值:R′s=-ln pth/ε+Rs-Re。根據式(3)，每個節點成為工作節點的概率近似為pinit=2Rarea/27NR′2s。其中N為節點總數。每個節點根據式(4)計算自己成為活躍節點的概率:

pactive=pinit×Ecurr/Emax=2Rarea/27NR′2s×(Ecurr/Emax)(4)

其中:Ecurr為節點當前能量;Emax為節點初始能量。

具體步驟如下:

a)判斷是否收到新的候選節點的notify消息，如果有，則將新的候選節點的ID加入到它的候選節點集N_set中。

b)如果節點在循環過程中收到候選節點的active消息，則更新N_set集合中候選節點的狀態信息;如果未收到消息，進入c)。

c)如果N_set非空，且能量是N_set中能量最高的，用式(4)計算pactive，如果pactive=1，節點則廣播active消息，宣布成為工作節點。如果節點不是能量最高的節點，且pactive=1，則判斷節點的覆蓋率p(si)是否大于門限值pth:節點依次查看N_set集中活躍在各層的active節點，如果N_set中有active節點，則根據它們的工作層(layer)分別計算節點的覆蓋率，對于層信息k(layer)相同的工作節點，計算出節點所在位置的覆蓋率:

pk(s)=1-Π|N_set(s)|i=1(1-p(s，si))(5)

其中:p(s，si)為N_set集中其他工作節點對si的覆蓋率;|N_set|表示N_set集中工作節點數目。

c)具體實現。節點查看N_set集中所有層信息為第1層的狀態為active的工作節點，若有pk(s)=p1(s)≥pth，則表明節點如果不成為該層的工作節點，它所在的位置s也會被它的鄰居(活躍在該層的其他節點)覆蓋且感知概率大于pth，此時節點廣播candidate消息，然后對N_set集中所有層信息為第2層的狀態為active的工作節點進行判斷，若有p1(s)=p2(s)

d)如果N_set為空，則節點未收到候選節點的notify消息，則節點以pactive參加競選。多次循環直到pactive=1，此時如果N_set仍未空的話，則區域中節點數目已經不足以完成多重覆蓋。

e)本次循環結束，加倍pactive。

f)最后Tj結束，判斷所有節點的狀態，如果為candidate和ready則將其置為sleeping狀態。

此外，循環的時間Tx必須小于競選的時間Tj，且要保證節點在Tx內能收到鄰居的消息。

筆者注意到初始化階段，節點從就緒態轉為候選態，完成候選節點的選取;活躍階段，節點在自身能量充足且滿足覆蓋要求時，從候選態轉為活躍態;工作階段，節點處于活躍態，直到下一輪開始轉為就緒狀態，或當節點能量耗盡時轉為睡眠態。節點狀態轉換如圖1所示。

3 實驗分析與相關工作評價

3.1 實驗分析

模擬實驗使用與文獻[9]相同的能量模型與參數。發送和接收數據的無線通信模型分別為

 Etr(k，d)=Eelec(k)+Eamp(k，d)=kEelec+kεfsd2;d

kEelec+kεamp d4;d>d0

(5)

Erx(k)=kEelec(6)

其中:Eelec表示無線收發電路所消耗的能量;εfs和εamp分別表示自由空間模型和多路衰減模型的放大器消耗的能量;d0是常數，取決于傳感器網絡應用的環境。詳細參數如表1所示。

表1 參數表

parametervalue

networksize50×50 m2

deploynodes100～800

sensing range (Rs)10 m

transmission range(Rp)25 m

Eelec50 nJ/b

εamp0.0013 pJ/b/m4

εfs10 pJ/b/m4

data packet size500 B

broadcast packet size25 B

packet header size25 B

initial energy2J/battery

Emin0.02J/battery

為了解部署節點數目與工作節點數目之間的關系，筆者將KCAPSM與GAF(geographical adaptive fidelity)[10]、基于探測(probing)的密度控制算法PEAS[11]算法進行了比較，實驗效果如圖2所示。PEAS是基于探測機制的，它要求每個睡眠節點定期地在其探測范圍內探測鄰居節點的狀態，若在其探測范圍內沒有工作節點，則進入工作狀態;否則仍處于睡眠狀態;在k=1的情況下，PEAS算法選出的工作節點數目與KCAPSM相當，而GAF算法選出的工作節點則比KCAPSM多出50%。

圖2表示當k=1，ε=0.5，Re=2，pth=0.8時，各類算法產生的工作節點數目的大小。可知，隨著部署節點的變化，KCAPSM算法產生的工作節點數目改變較小，適用于大規模無線網絡。在圖2中，網絡需求的覆蓋為1重覆蓋，它的覆蓋率要求pth分別從0.65變化到0.9。實際應用中，可以根據監測任務的不同調整pth的值。

圖3給出了在k=1，ε=0.5，Re=2時，監測區域中工作節點的數目隨著網絡需求覆蓋率pth的改變而改變。這是因為在覆蓋率逐漸改變的過程中，一些節點可能會因為能耗或其他因素的影響，導致不能完全覆蓋所有節點位置的情況，所以原本處于不工作的候選節點需要醒來參加競選成為工作節點。圖4給出了在pth =0.8時，不同參數k和ε下，工作節點數目的變化情況。如圖4中，k重覆蓋按照邏輯分層選擇工作節點，k=2的工作節點數目接近于k=1的兩倍。同時ε取值的大小也會影響工作節點的數目。隨著ε取值的增加，工作節點數目也不斷增加，且在k=2時，工作節點增加的數目較k=1時多。

3.2 相關工作

當前很多研究覆蓋控制的算法都是基于{0，1}布爾感知模型，文獻[2]利用采樣技術，提出了一種解決多重覆蓋的傳感器節點調度算法。該調度算法在滿足監控性能的前提下，通過采樣的方法來判斷一個節點是否為冗余節點，實現冗余節點的休眠。該算法基于理想的布爾模型，依懶GPS或定位協議獲取物理位置信息，耗能大，成本相對較高。在文獻[3]中，作者給出大規模網絡實現k重覆蓋的兩種算法，即集中式算法RKC和分布式算法DRKC。算法最終返回的節點集就是實現k重覆蓋的近似最小數目的工作節點集。這兩種算法都是基于{0，1}布爾模型。在文獻[4]中，作者提出了一種數學模型，給出了檢測范圍與傳感半徑之間的關系，從而得出達期望覆蓋的節點數目，該模型不需要節點的位置信息，降低了開銷，但作者未就如何實現k重覆蓋控制給出相應的解決方案。Xu等人在文獻[10]中提出GAF算法，但沒有考慮到網絡的覆蓋問題，也不能保證節點能耗均勻。實驗表明，單覆蓋時，GAF產生的工作節點數目比KCAPSM多出50%。僅僅文獻[12]為基于[0，1]區間上的感知概率模型，但是沒有考慮k重覆蓋。表2給出了各種算法的比較。

4 結束語

本文提出一種基于感知概率模型的分布式無線傳感器網絡的k重覆蓋算法(KCAPSM)。KCAPSM依據感知能力的強弱，將監測區域中的任一點被該節點監測的情況賦值為某一概率，通過節點間相互交換信息，考慮節點能量大小，進行k組不同工作節點的選擇。實驗表明，KCAPSM算法在滿足監控性能的條件下，讓網絡中的冗余節點休眠，節省系統能量。

參考文獻:

[1]任豐原，黃海寧，林闖.無線傳感器網絡[J]. 軟件學報， 2003，14(7): 1282-1291.

[2]陸克中，劉應玲.一種基于采樣的傳感器網絡多重覆蓋算法[J].計算機工程與應用，2007，43(17): 127-129.

[3]HEFEEDA M， BAGHERI M. Randomized k-coverage algorithms for dense sensor networks[C]//Proc of Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM). Anchorage， UAS: IEEE press， 2007: 2376-2380.

[4]劉明，曹建農，鄭源.無線傳感器網絡多重覆蓋問題分析[J]. 軟件學報， 2007，18(1):127-136.

[5]LU Jun， SUDA T. Coverage-aware self-scheduling in sensor networks[C]//Proc of IEEE CCW. California: IEEE Press， 2003: 117-123.

[6]孫永進，孫雨耕，房朝輝.無線傳感器網絡的連通與覆蓋[J]. 天津大學學報， 2005，38(1):14-17.

[7]WANG Xiao-rui， XING Guo-liang， ZHANG Yuan-fang，et al. Integrated coverage and connectivity configuration in wireless sensor networks[C]//Proc of the ACM International Conference on Embedded Networked Sensor Systems (SenSys). New York: ACM Press， 2003: 28-39.

[8]WILLIAMS R. The geometrical foundation of natural structure[M]. New York: Dover Publication Inc， 1979:51-52.

[9]HEINZELMAN W. Application specific-protocol architecture for wireless sensor networks[D]. Cambridge MA: MIT， 2000.

[10]XU Ya， HEIDEMANN J， ESTRIN D. Geography-Informed energy conservation for Ad hoc routing[C]//Proc of the 7th Annual ACM/IEEE International Conference on Mobile Computing and Networking. Rome: ACM Press， 2001: 70-84.

[11]YE Fan， ZHONG G，CHENG J， et al. PEAS: a robust energy conserving protocol for long lived sensor networks[C]//Proc of the 23rd International Conference on Distributed Computing Systems (ICDCS). Providence， Rhode island: IEEE Press， 2003:28-37.

[12]柳立峰， 鄒仕洪， 張雷，等. 基于概率覆蓋模型的無線傳感器網絡密度控制算法[J].北京郵電大學學報， 2005， 28(4): 14-17.