宋喜忠，張韌志

（黃淮學(xué)院 信息工程學(xué)院，河南 駐馬店　463000）

基于虛力的移動節(jié)點的無線傳感網(wǎng)絡(luò)空洞修復(fù)算法

宋喜忠，張韌志

（黃淮學(xué)院 信息工程學(xué)院，河南 駐馬店463000）

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

虛力；Gabriel圖；興趣區(qū)域；空洞修復(fù)；無線傳感網(wǎng)絡(luò)

0　引言

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

然而，WSNs提供的基礎(chǔ)性服務(wù)之一就是對RoI區(qū)域進行持續(xù)監(jiān)測。而覆蓋空洞就會導(dǎo)致監(jiān)測的中斷，破壞了數(shù)據(jù)的傳輸。因此，維持RoI區(qū)域的覆蓋是非常重要的［6］。然而，由于WSNs內(nèi)在特性及環(huán)境因素，RoI出現(xiàn)空洞是無法避免的，為此，在WSNs中，提供檢測并修復(fù)空洞的機制是最基本的要求。為此，本文以檢測、修復(fù)空洞為主題，分析了目前空洞修復(fù)的算法［7?14］，并提出新的算法。目前，現(xiàn)有的多數(shù)算法都是以苛刻的假設(shè)為前提條件，現(xiàn)有算法的不足如表1所示。

表1　現(xiàn)有處理空洞方案的不足

為此，本文提出的基于虛力的局部移動空洞修復(fù)VF?LMH（Virtual Forces?based Localized Movement HoleHealing）算法。VF?LMH算法主要有兩個階段。第一階段：空洞檢測。采用分布式基于網(wǎng)絡(luò)Gabriel圖GG（Ga?briel Graph）的局部空洞檢測方案。第二階段：空洞修復(fù)。在空洞修復(fù)時，先采用迭代算法計算HHA區(qū)域半徑，明確空洞處理區(qū)域HHA（Hole Healing Area）后，采用基于HHA內(nèi)的節(jié)點虛力驅(qū)動節(jié)點移動，修復(fù)空洞。

1　VF?LMH算法

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

1.1空洞檢測

文獻［15］在貪婪多跳轉(zhuǎn)發(fā)方式中，定義了停足節(jié)點（Stuck Nodes）。假定節(jié)點 p在其通信范圍外存在位置q。如果節(jié)點 p的一跳鄰居的所有節(jié)點內(nèi)沒有節(jié)點比節(jié)點 p離位置q更近，那么節(jié)點 p就是Stuck Node。為此，文獻［15］提出用于檢測網(wǎng)絡(luò)節(jié)點是否為Stuck Node的規(guī)則，稱為TENT規(guī)則。在空洞檢測過程，采用了TENT規(guī)則。

1.1.1空洞識別

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

圖1　TENT規(guī)則實施示例

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

Stuck NodeSi產(chǎn)生一個用于空洞發(fā)現(xiàn)數(shù)據(jù)包Pack?et_discovery，并用自己的ID進行標識。數(shù)據(jù)包Pack?et_discovery的任務(wù)就是收集空洞邊界節(jié)點的位置信息。節(jié)點Si依據(jù)網(wǎng)絡(luò)GG，按照右手規(guī)則向邊界節(jié)點Si+1轉(zhuǎn)發(fā)數(shù)據(jù)包Packet_discovery。節(jié)點 Si+1接收后，將自己的位置信息插入到數(shù)據(jù)包Packet_discovery中，并也依據(jù)網(wǎng)絡(luò)GG，按照右手規(guī)則向邊界節(jié)點Si+2轉(zhuǎn)發(fā)，直到數(shù)據(jù)包Packet_discovery遍歷了空洞邊界，最終傳遞到節(jié)點Si中，才停止轉(zhuǎn)發(fā)數(shù)據(jù)包Packet_discovery。

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

式中，dist（Sm，Sn）表示節(jié)點Sm，Sn間的歐式距離。

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

1.1.2空洞邊緣

網(wǎng)絡(luò)邊界Network boundary節(jié)點（所有節(jié)點一定是在RoI內(nèi)）執(zhí)行TENT規(guī)則，因此，它們檢測自己是否為Stuck Nodes。然后，由Stuck Nodes啟動空洞檢測以及空洞修復(fù)階段。

以分布式方式檢測網(wǎng)絡(luò)邊界，步驟如下：

（1）網(wǎng)絡(luò)內(nèi)的每個節(jié)點執(zhí)行TENT規(guī)則；

（2）每個Stuck Node觸發(fā)空洞發(fā)現(xiàn)階段，識別空洞邊界節(jié)點；

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

（4）當數(shù)據(jù)包Packet_discovery遍歷了空洞后，用數(shù)據(jù)包Packet_discovery存有的 Xmax，Ymax，Xmin，Ymin表示最大空洞的網(wǎng)絡(luò)邊界，空洞半徑r為：

1.2空洞修復(fù)

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

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

1.2.1規(guī)劃HHA

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

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

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

首先（第一輪迭代，記為HHA?0），令 β=0，規(guī)劃HHA的圓的半徑等于r，那么這個圓的面積為πr2。則覆蓋區(qū)域πr2所需的節(jié)點數(shù)等于：

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

估計了HHA后，HM節(jié)點向相關(guān)節(jié)點發(fā)送移動數(shù)據(jù)包Packet_Move，以處理該空洞。接收了該數(shù)據(jù)包，節(jié)點就進行了移動，調(diào)整位置（Relocation）。

1.2.2節(jié)點Relocation

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

引力：空洞中心o對離自己距離大于dath的HHA內(nèi)的每個節(jié)點產(chǎn)生指向o的推動作用。為此，HHA內(nèi)的節(jié)點p接收到來自空洞中心o的引力

圖2HHA內(nèi)節(jié)點移動示意圖

接下來，分析節(jié)點的移動原則。

式中，Np表示節(jié)點p的鄰居節(jié)點集。

式中V表示節(jié)點移動速度。

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

2　系統(tǒng)仿真及性能分析

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

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

表2　仿真參數(shù)

圖3　VF?LMH算法流程圖

2.1場景1

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

2.2場景2

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

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

圖4　空洞處理過程

圖5　網(wǎng)絡(luò)覆蓋率隨網(wǎng)絡(luò)節(jié)點數(shù)的變化情況

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

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

圖6　總的移動距離隨網(wǎng)絡(luò)節(jié)點數(shù)的變化情況

圖7　參與移動的節(jié)點數(shù)隨網(wǎng)絡(luò)節(jié)點數(shù)的變化情況

3　結(jié)語

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

仿真結(jié)果表明，提出的VF?LMH算法能夠有效地處理空洞，并與DSSA和SMART相比，VF?LMF算法在網(wǎng)絡(luò)覆蓋率、參與移動的節(jié)點數(shù)以及移動距離方面占有優(yōu)勢。

［1］ZITTERBART D，WIENECKE B，BUTLER J，et al.Coordi?nated movements prevent jamming in an emperor penguin hud?dle［J］.PLoS ONE，2011，6（6）：202?216.

［2］XU H，HUANG L，ZHANG Y，et al.Energy?efficient coopera?tive 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 re?lays［J］.IEEE MASS，2010（2）：312?321.

［4］夏韻，陳志剛，曾鋒.無線傳感器網(wǎng)絡(luò)中基于MDS?MCC問題的啟發(fā)式算法研究［J］.計算機工程與科學(xué)，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 Inter?national Symposium on Information Processing in Sensor Net?works.［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 net?works 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 ge?ometry 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.Neigh?borhood?based topology recognition in sensor networks［C］//Pro?ceedings 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 net?works［C］//Proceedings of 17th Canadian Conference on Com?putational 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 applica?tions，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 net?works［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.Inter?national 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 sen?sor deployment methods in wireless sensor networks［J］.IEEE transactions on parallel and distributed systems，2010，18 （8）：1108?1121.

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）

The emergence of holes in the region of interest（RoI）is unavoidable due to the inherent properties and environ?mental 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.

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

10.16652/j.issn.1004?373x.2016.14.018

TN926?34；TPT393

A

1004?373X（2016）14?0064?05

2015?12?09

河南省科技廳發(fā)展計劃（142102110088）

宋喜忠（1977—），男，河南駐馬店人，副教授，碩士。主要從事計算機網(wǎng)絡(luò)、數(shù)據(jù)庫方面的研究。

張韌志（1980—），男，河南泌陽人，講師，碩士。主要從事軟件工程開發(fā)、網(wǎng)絡(luò)管理等研究。