基于虚力的移动节点的无线传感网络空洞修复算法

摘 要： 由于无线传感网络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。

式中：[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.