基于虛力的移動節點的無線傳感網絡空洞修復算法

摘 要： 由于無線傳感網絡WSNs的內在特性以及環境因素，興趣區域RoI內出現覆蓋空洞是無法避免的。為此，提出基于虛力的局部移動空洞處理（VF?LMH）算法。VF?LMH算法分為空洞檢測及空洞修復兩個階段。首先進入空洞檢測階段，利用網絡Gabriel圖局部協議識別空洞以及空洞中心位置、尺寸，隨后進入空洞修復階段，先明確空洞處理區域，然后空洞處理區域內的節點依據虛力進行局部移動，修復空洞。仿真結果表明，提出的VF?LMH算法能夠有效檢測并修復空洞，與同類算法相比，VF?LMH算法的修復空洞成本低廉（參與移動的節點數少、總移動距離小）。

關鍵詞： 虛力； Gabriel圖； 興趣區域； 空洞修復； 無線傳感網絡

中圖分類號： TN926?34； TPT393 文獻標識碼： A 文章編號： 1004?373X（2016）14?0064?05

Virtual force mobile node based algorithm to heal holes in wireless sensor networks

SONG Xizhong， ZHANG Renzhi

（School of Information Engineering， Huanghuai University， Zhumadian 463000， China）

Abstract：The emergence of holes in the region of interest （RoI） is unavoidable due to the inherent properties and environmental factors of WSNs. Therefore， the virtual forces?based localized movement hole healing （VF?LMH） algorithm is proposed in this paper. The VF?LMF algorithm is operated in two distinct phases： hole detection and hole repair. The VF?LMH algorithm in the phase of detecting hole is to discover the holes， hole center location and size by the localized protocol of Gabriel graph （GG） of network. In the hole repair phase， the hole healing area （HHA） is confirmed first， and then the nodes in HHA are moved according to the virtual force for the hole healing. The simulation results show that the proposed VF?LMH algorithm is able to detect and heal the holes. Compared with the similar algorithms， the cost for hole healing of VF?LMH algorithm is lower because it has less moved nodes and shorter total moving distance.

Keywords： virtual force； Gabriel graph； interested region； hole healing； wireless sensor network

0 引 言

由傳感節點組建的無線傳感網絡WSNs（Wireless Sensor Networks）被廣泛應用，如棲息地監控[1]、環境監控[2?3]以及監視系統[4]（Surveillance Systems）等。實際上，傳感節點是一個微型設備，具有有限的計算以及通信功能。然而，傳感節點是非常脆弱，易受到外界多種因素干擾，如瞬息震動（Sudden Shock）、能量耗盡，致使傳感節點失效，一旦失效，就在對特定的興趣區域RoI（Region of Interest）形成覆蓋空洞（Coverage Holes）[5]。

然而，WSNs提供的基礎性服務之一就是對RoI區域進行持續監測。而覆蓋空洞就會導致監測的中斷，破壞了數據的傳輸。因此，維持RoI區域的覆蓋是非常重要的[6]。然而，由于WSNs內在特性及環境因素，RoI出現空洞是無法避免的，為此，在WSNs中，提供檢測并修復空洞的機制是最基本的要求。為此，本文以檢測、修復空洞為主題，分析了目前空洞修復的算法[7?14]，并提出新的算法。目前，現有的多數算法都是以苛刻的假設為前提條件，現有算法的不足如表1所示。

1 VF?LMH算法

具體而言，提出的VF?LMH算法從二個角度修復空洞：如何檢測空洞以及估計空洞的尺寸；在修復空洞時，哪個位置是移動節點的最佳的目標位置。

1.1 空洞檢測

文獻[15]在貪婪多跳轉發方式中，定義了停足節點（Stuck Nodes）。假定節點[p]在其通信范圍外存在位置[q]。如果節點[p]的一跳鄰居的所有節點內沒有節點比節點[p]離位置[q]更近，那么節點[p]就是Stuck Node。為此，文獻[15]提出用于檢測網絡節點是否為Stuck Node的規則，稱為TENT規則。在空洞檢測過程，采用了TENT規則。

1.1.1 空洞識別

首先，通過識別Stuck Nodes，檢測空洞是否存在。網絡內的每個節點執行TENT規則，檢測自己是否為Stuck Node。具體而言，節點[p]檢測過程如下：如圖1所示，假定節點[u]和v是一對邊緣鄰居節點，連接[up]和[vp]，然后過點[o]作[up]和[vp]的垂直平分線[l1]，[l2]。在節點[p]一跳鄰居節點范圍內，沒有節點比[p]離節點[o]更近，因此節點[p]是Stuck Node。

所有Stuck Nodes觸發空洞發現階段，并找出空洞的邊界以及空洞的尺寸，即空洞的中心位置以及半徑。

Stuck Node[Si]產生一個用于空洞發現數據包Packet_discovery，并用自己的ID進行標識。數據包Packet_discovery的任務就是收集空洞邊界節點的位置信息。節點[Si]依據網絡GG，按照右手規則向邊界節點[Si+1]轉發數據包Packet_discovery。節點[Si+1]接收后，將自己的位置信息插入到數據包Packet_discovery中，并也依據網絡GG，按照右手規則向邊界節點[Si+2]轉發，直到數據包Packet_discovery遍歷了空洞邊界，最終傳遞到節點[Si]中，才停止轉發數據包Packet_discovery。

接收了數據包Packet_discovery后，節點[Si]從數據包中提取邊界節點[S0，S1，???，SN]的位置信息。從中選擇兩個節點[Sm]，[Sn]，這兩個節點間的距離是邊界節點[S0，S1，???，SN]間任意節點間距離最長的，如式（1）所示。

[distSm，Sn=maxdistSm，Sn，m，n=0，1，???，N，m≠n] （1）

式中，[distSm，Sn]表示節點[Sm]，[Sn]間的歐式距離。

然后，計算空洞的中心位置[oxo，yo]，其等于[SmSn]的中點，如式（2）所示。

[xo=xSm+xSn2yo=ySm+ySn2] （2）

式中：[xSm，][ySm]以及[xSn，][ySn]分別表示節點[Sm，][Sn]的二維坐標。

1.1.2 空洞邊緣

網絡邊界Network boundary節點（所有節點一定是在RoI內）執行TENT規則，因此，它們檢測自己是否為Stuck Nodes。然后，由Stuck Nodes啟動空洞檢測以及空洞修復階段。

以分布式方式檢測網絡邊界，步驟如下：

（1） 網絡內的每個節點執行TENT規則；

（2） 每個Stuck Node觸發空洞發現階段，識別空洞邊界節點；

（3） 在數據包Packet_discovery中，定義一個區域，用于表示Network boundary的最大、最小坐標[Xmax]，[Ymax]，[Xmin]，[Ymin]。每個Stuck Node接收了數據包Packet_discovery后，將自己的位置坐標與數據包Packet_discovery中的[Xmax]，[Ymax]，[Xmin]，[Ymin]進行比較。如果比[Xmax]，[Ymax]大，或者比[Xmin]，[Ymin]更小，則替換；

（4） 當數據包Packet_discovery遍歷了空洞后，用數據包Packet_discovery存有的[Xmax]，[Ymax]，[Xmin]，[Ymin]表示最大空洞的網絡邊界，空洞半徑[r]為：

[r=Xmax-Xmin2+Ymax-Ymin2] （3）

1.2 空洞修復

空洞檢測后，采用完全分布式的空洞處理算法對空洞進行修復。提出空洞算法引用了虛力（Virtual Forces）概念。為了處理已檢測到的空洞，在空洞處理區域（Hole Healing Area，HHA）中定義引力和斥力。引力是空洞中心對節點的吸引力，而斥力是指兩節點間的排斥力，其用于最小化重疊覆蓋區域。

在空洞處理過程中，從Stuck Nodes中隨機選擇一個節點作為空洞主管（Healing Manger，HM），其擔任決策HHA以及通知節點的移動信息任務。HM節點具有空洞的尺寸以及邊緣節點的所有信息。接下來，分析空洞處理的具體過程。

1.2.1 規劃HHA

識別了空洞后，HM節點計算空洞的中心位置以及尺寸。如上所述，將空洞區域近似為圓，因此，為了規劃HHA，需要計算圓的半徑。

采用基于式（4）的迭代算法近似計算HHA圓的半徑。

[R=r?1+β， β∈R+] （4）

式中：[r]表示空洞的半徑；[β]為常數，其取決于節點密度和節點的通信范圍[RS]。

首先（第一輪迭代，記為HHA?0），令[β]=0，規劃HHA的圓的半徑等于[r]，那么這個圓的面積為[πr2]。則覆蓋區域[πr2]所需的節點數等于：

[πr2πR2S=r2R2S] （5）

然后，HM節點計算HHA?0內現有節點數量。HM節點請求其一跳鄰居節點估計它們在HHA?0內一跳鄰居數。為此，HM節點廣播空洞處理區域估計（Hole?Healing Region Estimation，HHRE）數據包Packet_HHRE，其包含該空洞的信息。如果HM節點估計的數量少于處理該空洞要求的節點數，那么這些節點的移動將帶來新的空洞。為了避免新空洞的出現，HM節點通過增加[β]開始新一輪估計鄰居節點，這個過程重復進行，直到發現有足夠多的節點處理空洞。

估計了HHA后，HM節點向相關節點發送移動數據包Packet_Move，以處理該空洞。接收了該數據包，節點就進行了移動，調整位置（Relocation）。

1.2.2 節點Relocation

在計算HHA后，HM節點通知相應的節點進行移動。這些節點將接收到來自空洞中心的力，并向其移動，這個力包括引力和斥力，如圖2所示。

引力：空洞中心[o]對離自己距離大于[dath]的HHA內的每個節點產生指向[o]的推動作用。為此，HHA內的節點[p]接收到來自空洞中心[o]的引力[Fap，o]：

[Fap，o=-kadp，ola?exprdp，oua， p，o≤dath0， p，o≤dath] （6）

式中：[ua]表示從節點[p]指向空洞中心[o]的單位向量；[dp，o]為節點[p]與空洞中心[o]間的歐式距離；[la]為距離系數；[ka]表示引力強度的系數；[r]表示空洞半徑。

斥力：為了最小化重疊覆蓋區域，相距小于[drth]的兩節點間存在斥力[Fr]，即[0

[Frp，q=-krdp，qlrur， 0

式中：[ur]表示從節點[q]指向[p]的單位向量；[dp，q]為節點[p]與[q]之間的歐式距離；[lr]為距離系數，且[lr>la]；[kr]表示引力強度的系數。

接下來，分析節點的移動原則。

節點[p]的最終位置是由節點[p]所受多個鄰居節點間的斥力和來自空洞中心的引力的合力[Fp]決定：

[Fp=q∈Np，q≠pFrp，q+Fap，o] （8）

式中，[Np]表示節點[p]的鄰居節點集。

采用文獻[16]使用方法很方便計算[Fp]。如果在時間[t]，[Fp=0]，節點[p]停留初始位置[Ppt]，不移動。否則，節點[p]依據[Fp]，經[Δt]移動后，節點[p]最終位置[Ppt+Δt]為：

[Ppt+Δt=FpFp?V+Ppt] （9）

式中[V]表示節點移動速度。

VF?LMH算法的流程圖，如圖3所示。

2 系統仿真及性能分析

利用仿真軟件NS2對提出的VF?LMH算法進行仿真，并考慮兩個仿真場景。

第一個場景用于驗證VF?LMH算法空洞檢測以及空洞處理的能力。第二個場景用于將提出的VF?LMH算法與DSSA[17]和SMART[18]進行性能比較，兩個場景的仿真參數如表2所示。

2.1 場景1

場景1中，RoI中出現不同位置，并且尺寸變化的空洞，考察提出的VF?LMH算法檢測空洞以及處理空洞的能力。采用確定性部署（Deterministic Deployment）傳感節點。首先，產生42 m的兩個空洞，如圖4（a）所示。經VF?LMH檢測及修復后結果如圖4（b）所示。可以看出，VF?LMH算法能夠有效地檢測空洞，并且成功地修復空洞。

2.2 場景2

本小節的仿真，主要考察VF?LMH算法在修復空洞時參與移動的節點數、節點移動的總距離、以及網絡覆蓋率性能，并與DSSA和SMART進行比較。選擇DSSA和SMART的原因在于：DSSA是基于虛力的集中式移動修復空洞，SMART是基于grid?quorum的移動修復算法，與VF?LMH算法，具有可比性。

圖5 顯示了VF?LMH，DSSA以及SMART三個算法的網絡覆蓋率隨節點數的變化情況。從圖5可知，在節點數為200時，VF?LMH算法的覆蓋率最低。主要是因為：在200 m×200 m的區域內，隨機部署200個節點，在區域邊界以及ROI區域內產生了較多的空洞。VF?LMH算法在檢測到空洞后，沒有足夠節點修復空洞。隨著節點密度提升，VF?LMH算法性能隨之提高，當節點密度達到較大（350個節點），提出的VF?LMH算法優于DSSA和SMART。

圖6顯示了VF?LMH，DSSA以及SMART三個算法在修復空洞參與節點移動的總距離隨節點數的變化情況。從圖6可知，在節點數在[200，300]的范圍內，VF?LMH算法的移動的總距離隨節點數的增加而增加。此外，與SMART相比，提出的VF?LMH算法節點移動的總距離更少，而DSSA算法的節點總移動距離隨節點數的增加而下降，這主要是因為中間節點力迅速下降，節點的分布區域更小，相應地，節點覆蓋區域更小。此外，從圖7可知，節點數在[200，300]的范圍內，SMART和VF?LMH算法在修復空洞時節點移動數性能相近，但是，當節點數大于300后，VF?LMH算法的節點移動數低于SMART。在[200，300]的范圍內，VF?LMH算法的平均移動的節點數為40，SMART算法為160，并且VF?LMH算法的覆蓋率提高了7%（見圖4）。而在這間隔內，DSSA獲取了大的覆蓋率（見圖4），但是，其以付出大的移動節點數（1 200～1 600）。這主要是因為：VF?LMH算法和SMART算法的節點是定向移動。而DSSA中所有節點依據虛力原則進行移動。

上述的仿真結果表明，VF?LMH算法能夠有效地檢測空洞、處理空洞，并且提高了網絡覆蓋率。

3 結 語

本文提出了檢測、處理空洞的VF?LMH算法。VF?LMH算法首先利用TENT規則，檢測Stuck Nodes，隨后利用這些Stuck Nodes識別空洞，再利用網絡的GG圖，檢測空洞的中心位置以及半徑。然后，規劃空洞處理區域HHA，再利用基于虛力局部移動算法，計算HHA內節點所受的力。節點依據所受力的作用進行移動，從而修復空洞。

仿真結果表明，提出的VF?LMH算法能夠有效地處理空洞，并與DSSA和SMART相比，VF?LMF算法在網絡覆蓋率、參與移動的節點數以及移動距離方面占有優勢。

參考文獻

[1] ZITTERBART D， WIENECKE B， BUTLER J， et al. Coordinated movements prevent jamming in an emperor penguin huddle [J]. PLoS ONE， 2011， 6（6）： 202?216.

[2] XU H， HUANG L， ZHANG Y， et al. Energy?efficient cooperative data aggregation for wireless sensor networks [J]. Journal of parallel distrib comput， 2010， 70（9）： 953?961.

[3] EL?MOUKADDEM F， TORNG E， XING G. Maximizing data gathering capacity of wireless sensor networks using mobile relays [J]. IEEE MASS， 2010（2）： 312?321.

[4] 夏韻，陳志剛，曾鋒.無線傳感器網絡中基于MDS?MCC問題的啟發式算法研究[J].計算機工程與科學，2013，35（4）：53?58.

[5] AHMED N， KANHERE S S， JHA S. The holes problem in wireless sensor networks： a survey [J]. SIGMOBILE mobile computing comm rev， 2005， 9（2）： 4?18.

[6] CHANG C Y， HUNG L L， SCHAN G W， et al. Decentralized and energy?balanced algorithms for maintaining temporal full?coverage in mobile WSNs [J]. Journal of wireless comm. and mobile computing， 2012， 12（5）： 445?462.

[7] KUN B， KUN T， NAIJIE G， et al. Topological hole detection in sensor networks with cooperative neighbors [C]// Proceedings of International Conference on Systems and Networks Comm. [S.l.： s.n.]， 2006： 31?40.

[8] GHRIST R， MUHAMMAD A. Coverage and hole?detection in sensor networks via homology [C]// Proceedings of Fourth International Symposium on Information Processing in Sensor Networks. [S.l.： s.n.]， 2005： 254?260.

[9] DE SILVA V， GHRIST R， MUHAMMAD A. Blind swarms for coverage in 2?D [C]// Proceedings of Robotics： Science and Systems. [S.l.： s.n.]， 2005： 335?342.

[10] F. Stefan.Topological Hole Detection in wireless sensor networks and its applications[C]// Proceedings of Joint Workshop on Foundations of Mobile Computing. [S.l.： s.n.]， 2005： 44?53.

[11] STEFAN F， CHRISTIAN K. Hole detection or： how much geometry hides in connectivity [C]// Proceedings of 22nd Ann Symposium on Computational Geometry. [S.l.： s.n.]， 2013： 377?385.

[12] FEKETE S P， KRCOLLER A， PFISTERER D， et al. Neighborhood?based topology recognition in sensor networks[C]// Proceedings of International Workshop on Algorithmic Aspects of Wireless Sensor Networks. [S.l.： s.n.]， 2004： 123?136.

[13] FEKETE S P， KAUFMANN M， KRCOLLER A， et al. A new approach for boundary recognition in geometric sensor networks [C]// Proceedings of 17th Canadian Conference on Computational Geometry. [S.l.： s.n.]， 2012： 82?85.

[14] SHIRSAT A， BHARGAVA B. Local geometric algorithm for hole boundary detection in sensor networks [J]. Security and comm networks， 2011， 4（9）： 1003?1012.

[15] FANG Q， GAO J， GUIBAS L J. Locating and bypassing holes in sensor networks [J]. Mobile networks and applications， 2011， 11（2）： 187?200.

[16] SIBLEY G T， RAHIMI M H， SUKHATME G S. Robomote： A tiny mobile robot platform for large?scale ad?hoc sensor networks [C]// Proceedings of IEEE International Conference on Robotics and Automation. [S.l.： s.n.]， 2002： 1143?1148.

[17] YONG Z， LI W. A sensor deployment algorithm formobile wireless sensor networks [C]// Proceedings of 21st Ann. International Conference on Chinese Control and Decision Conf. [S.l.： s.n.]， 2010： 4642?4647.

[18] YANGY S， LIZ M， WU J. Scan?based movement?assisted sensor deployment methods in wireless sensor networks [J]. IEEE transactions on parallel and distributed systems， 2010， 18（8）： 1108?1121.