混合传感网络覆盖洞修复改进算法研究

于 秦，王伟东，李龙江，钱 艇



混合传感网络覆盖洞修复改进算法研究

于 秦1，王伟东2，李龙江1，钱 艇1

(1. 电子科技大学通信与信息工程学院 成都 611731；2. 电子科技大学信息与软件工程学院 成都 610054)

针对传统的无线传感网络覆盖洞修复算法VOR(VORonoi algorithm)存在的不足，该文在混合传感网络环境下提出基于优先机制的VORP(Priority-based VOR)和基于复杂优先机制的VORCP两种改进的覆盖洞修复算法。通过对两种改进算法进行仿真和分析，以及对运用修复算法前和分别运用VOR、VORP、VORCP算法后，监测区域无线传感网络覆盖情况的纵向与横向的比较分析，结果表明该文所提出的改进算法在性能和效率上均优于传统的覆盖洞修复算法。

覆盖洞; 混合传感网络; 优先机制; 修复

覆盖是无线传感器网络(wireless sensor networks, WSNs)设计和规划中的一个重要基础支撑技术。针对覆盖问题展开的研究包括传感器节点的部署策略、传感器网络连通性研究、节能网络的实现等。其中，网络节点的部署对网络的覆盖性能起着决定性的作用。在许多自然环境的监控应用中，尤其是针对复杂、敌对或人员不可到达环境的监控，传感器网络的相关情况不能预先确定。由此采取将传感器节点随机分布在监控区域内而预先不能确定节点位置的随机部署方式。随机的部署往往造成无线传感网络对目标感知区域的覆盖度大大降低，覆盖洞由此形成。另外，节点由于能量耗尽或意外失效也会造成覆盖洞的形成[1]。

覆盖洞的出现将极大地影响无线传感网络的覆盖度，而覆盖度是衡量无线传感网络工作性能好坏的重要指标。解决覆盖洞问题的常用方法有两种：1) 增加区域内散播的传感器数量，形成重覆盖，减小某一区域形成覆盖洞的可能性；2) 使用可移动的传感器节点，通过相关算法将移动节点移动到覆盖洞区域，从而减小覆盖洞[2-3]。

文献[4]提出3种计算修复覆盖空洞的算法。第一种算法VEC(VECtor-based algorithm)属于一种虚拟力算法，在节点之间引入一种基于距离函数的虚拟斥力，当两个节点之间的距离小于阈值，则使用距离函数将其中一个节点向反方向移动。该算法适用于所有传感器节点都拥有一定移动能力的纯移动节点网络。第二种算法VOR(VORonoi-based algorithm)属于一种贪婪算法。第三种算法minimax algorithm的思想与VOR算法类似，但在确定最佳移动位置时，它更多地考虑到节点对所有Voronoi顶点的兼顾。文献[5]提出了一种基于分布式的覆盖洞修复算法。文献[6]提出CHPA(coverage hole patching algorithm)算法。文献[7]提出了PATT(patching algorithm triangle by triangle)算法。文献[8]提出了一种基于覆盖洞边界点来确定节点最佳移动位置的方法。文献[9]提出一种竞标策略下的覆盖洞修复方法。

本文在混合传感网络下提出基于VOR算法的两种覆盖洞修复改进算法VORP(priority-based VORonoialgorithm)和VORCP(complex priority-based VORonoi algorithm)，旨在改善VOR算法的不足，使无线传感网络覆盖达到应有的标准。

1 VOR算法

Voronoi图又称泰森图，是计算几何中的一种结构，已经证明能用来确定无线传感网络中的潜在覆盖洞位置，满足以下定义[10]。

图1所示是一幅Voronoi图，图中的黑点表示传感器节点，节点周围形成的多边形叫做Voronoi多边形。由定义可知，Voronoi多边形内的任意一点都只与其包围内的节点距离最近。VOR算法则基于Voronoi图。VOR算法的优点在于通过构建Voronoi多边形可以快速找到潜在覆盖洞区域，并获得移动节点最佳移动位置；算法具有普适性，不受覆盖盲区形状的影响。其缺点在于：VOR算法采用的是纯移动节点网络覆盖监测区域，任意一个节点的移动都有可能造成新覆盖洞的出现，并影响其他节点的覆盖性能。并且移动节点的频繁移动本身会消耗大量的能量，缩短无线传感网络的寿命；算法对所有多边形顶点所在覆盖洞区域修复时没有区别对待，会出现当移动节点不足时，移动节点未能优先修补较大覆盖洞而削弱节点的修复功能[11-12]。

2 基于优先机制的VORP算法

针对传统VOR算法存在的缺点，考虑现实的无线传感网络环境，本文改变单纯的移动传感器网络方式，使用复合式传感器网络，即首先部署静态节点，负责监测区域主要部分的覆盖，并通过构造Voronoi图来检测并指导移动节点修复覆盖洞。另外，当部署的移动节点数量少于潜在覆盖洞数量(实际情况多是如此)时，采用VORP算法来提高移动节点修复性能。

2.1 算法思路

由于VOR算法未对Voronoi多边形顶点所在覆盖洞进行大小估计并采用优先覆盖策略，使得当Voronoi多边形顶点数过多而移动节点不足的情况下，无法最大限度地修复覆盖洞。本文所说的优先机制是指给予覆盖洞优先等级，大覆盖洞的需要优先进行修复，小的覆盖洞后修复或者不修复。本文提出的基于优先机制的VORP算法，在修复覆盖洞之前，先对覆盖洞大小进行定性比较，即比较泰森多边形顶点与周围节点的距离，越远则说明覆盖洞越大，得到覆盖洞修复位置的优先级，再调度有限的移动节点按照优先级进行覆盖洞修复，使覆盖效率达到最优。

2.2 算法步骤及流程

VORP算法步骤如下：

1) 在随机布置静态节点后，构建Voronoi图，并获得每个多边形顶点位置的信息列表。删除中监测区域外的顶点信息；

2) 新建一个移动节点修复位置信息优先级列表list和临时信息列表temp；

3) 对中的每一个顶点，若存在与它距离小于等于R(R为节点感知半径)的静态节点，则将它从中删除，否则将d(d为该顶点和与之最近的静态节点之间的距离)以及顶点的位置信息添入list中；

4) 初始化临时信息列表temp；

5) 进行一次循环(循环次数为移动节点数目)遍历list，若说明该位置处于一个大覆盖洞中心，则更新temp中顶点d(置零)和位置信息，发送给移动节点指导其移动。list中删除该顶点相关信息，进行下一次循环；若，则比较此顶点d和temp中d，若此顶点d大于temp中d，则将此顶点d和位置信息添入temp，将其更新。若list中顶点全部遍历，则将temp中顶点d和位置信息发送给移动节点指导其移动。list中删除该顶点相关信息。进行下一次循环。

2.3 VORP算法仿真

考虑监测区域为10 m´10 m的正方形区域，该区域内部署着30个静态节点以及20个动态节点，节点的感知半径R为1 m，该通信半径条件下邻居节点可以互相交换信息，每一个圆的圆心代表一个节点的地理位置，圆形包围的区域为无线传感网络覆盖区域。本文在Matlab平台上对VORP算法进行了仿真。图2为静态节点部署后的区域覆盖情况，图3为运用一次VOR算法后的区域覆盖情况，图4为运用一次VORP算法后的区域覆盖情况。

经计算，图2、图3和图4中区域的覆盖度分别为58.28%、75.33%和78.24%。经泰森图构造后，监测区域共存在25个潜在覆盖洞区域，远远大于可使用的移动节点。这些覆盖洞的大小各不相同，显然优先机制的引入让移动传感器优先修复较大覆盖盲区以更好地利用有限的传感器资源，优化覆盖洞修复性能。由图可见，VOR、VORP算法都具有不错的覆盖洞修复性能，而引入了优先机制的VORP算法性能更优。

3 基于复杂优先机制的VORCP算法

上述VORP算法虽然能提高VOR算法在移动节点不足以覆盖所有潜在覆盖洞时的性能，将有限的移动节点部署到最大覆盖洞区域，然而仿真结果发现，该算法往往会出现以下情况：多个最佳覆盖Voronoi多边形的顶点位置互相粘连，彼此距离很近，当移动节点覆盖其中一个顶点之后，周围的覆盖洞也相应减小，使得其余部署在这个区域附近的移动节点不再位于最佳修复位置，也就削弱了VORP算法在部署移动节点上的优越性。图5具体展示了该问题。因此，本文提出更进一步的改进算法VORCP，用于检测并改善以上问题。

3.1 VORCP算法思想

为检测和改善VORP算法存在的上述缺陷，VORCP算法设置了一个可容忍的最小粘连距离阈值threshold，若一个潜在覆盖洞修复位置与某个已修复的覆盖洞位置的距离小于threshold，则降低这个覆盖洞修复优先级至最低。

3.2 VORCP算法步骤

1) 在随机布置静态节点之后，构建Voronoi图，并获得每个多边形顶点位置信息列表。删除中监测区域外的顶点信息；

2) 新建一个移动节点修复位置信息优先级列表list和临时信息列表temp1、temp2以及一个计数标志；

3) 对中每一个顶点，若存在与它距离小于等于的静态节点，则将它从中删除；否则将(为该顶点和与之最近的静态节点之间的距离)以及顶点的位置信息添入list中；

4) 初始化临时信息列表temp1、temp2；

5) 进行一次循环(循环次数为移动节点数目)。遍历list，添加顶点及位置信息到temp2中，计算该顶点与temp1中所有顶点的距离。若存在(threshold为可容忍的最小粘连距离)，则将list中该顶点的更新为0，使+1并初始化temp2；若且，则跳出遍历，将temp2中顶点所有信息添至temp1中，指导移动节点向其移动，删除list中该顶点信息。若且，则比较此顶点的和temp2中的顶点信息，若此顶点大于temp2中的，则将此顶点和位置信息覆盖至temp2中，直到遍历结束，将temp2中顶点所有信息添至temp1中，指导移动节点向其移动，删除list中该顶点相关信息。若等于list中剩余的节点数，则将list中所有顶点信息依次添入temp1中至所有移动节点都部署完成或list中顶点清空。

3.3 VORCP算法仿真

本文在Matlab平台上对VORCP算法进行了仿真。仿真场景同2.3节。图6为静态节点部署后的区域覆盖情况，图7为运用一次VORP算法后的区域覆盖情况，图8为运用一次VORCP算法后的区域覆盖情况。threshold可以根据具体要求自行设置，本文中threshold设置为/4(即0.25 m)。

从图6～图8可以看出两种算法对覆盖洞的修复情况。经计算，图6中区域的覆盖度为61.72%，图7中区域的覆盖度为86.38%，图4中区域的覆盖度为88.26%。可见VORP、VORCP算法都具有不错的覆盖洞修复性能，且VORCP算法性能更优。

4 算法比较与分析

本文对VOR、VORP以及VORCP算法进行横向以及纵向的比较，以直观地验证后两种算法的优越性。在横向比较中，利用算法对同一片监测区域进行覆盖洞修复，通过对覆盖度的计算和分析得出结论；在纵向比较中，将给定工作要求下的最下限覆盖度水平，并分别使用3种算法进行节点部署，以得出算法各自达到要求所需的周期，进而分析算法效率。

4.1 算法横向比较与分析

图9依次展示了运用修复算法前和分别运用VOR、VORP、VORCP算法后监测区域无线传感网络覆盖情况。仿真场景同2.3节，threshold设值为/4(即0.25 m)。在静态节点部署完成之后，移动节点根据静态节点构造出泰森图，按照不同算法步骤选择覆盖洞进行修复。

由计算可得，算法运用前无线传感网络对监测区域的覆盖度为59.81%；而运用VOR、VORP、VORCP算法之后无线传感网络对监测区域的覆盖度分别为67.95%、75.65%、77.83%。就一般性而言，3种算法的覆盖洞修复性能比较为VORCP>VORP> VOR。通过深入的仿真与分析发现，当检测出的覆盖洞数量与可使用的移动节点数量相差越大，VORP和VORCP算法比VOR算法的优越性越明显；局部覆盖洞越密集，VORCP对VORP算法的优越性越明显。

4.2 算法纵向比较与分析

本文设计的算法可以对监测区域的覆盖洞进行多次修复。在现实情况下，进行一次移动节点部署来提高无线传感网络的覆盖度往往是不够的。为了达到应用所要求的覆盖度，需要进行二次或者多次部署，最终使监测区域的覆盖度达到可容忍的要求。

因此，本文对各个算法的覆盖洞修复效率进行比较。仿真环境中监测区域为12 m´12 m的正方形区域，初始静态节点为40个，每使用一次覆盖洞修复算法，将添加10个移动节点以提高区域覆盖度。所有节点的感知半径依旧为1 m，保持通信半径满足邻居节点互相交换信息的要求。假设某应用要求的覆盖度下限为90.0%，分别使用VOR、VORP、VORCP算法来提高无线传感器网络对监测区域的覆盖度，使其达到该应用所要求的覆盖度下限。通过观察分析覆盖度提高的情况以及比较算法使用的轮数来验证哪种算法的效率最高。表1展示了3种覆盖洞修复算法达到所需覆盖度时经过的轮数以及每一轮之后无线传感网络的覆盖度大小。图10更为直观地显示了覆盖度提高的情况。可以看出，VORCP算法在第四轮算法结束后已经达到了覆盖度要求，而VOR及VORP算法则进行了6轮算法修复才达到应有的覆盖度水平。由此可见，VORCP算法在效率和性能方面均优于前两种算法。值得一提的是，VORP算法在覆盖洞较大的时候修复效果优于VOR算法，但从长期的算法效率看并没有优势。因为当具有大覆盖洞时，采用优先机制能够很明显地先对它们进行修复，从而显著提高覆盖度；然而在覆盖度逐渐提高时，大覆盖洞区域逐渐减少，而移动节点修复覆盖洞时的粘连状况更容易发生，并成为影响其性能的主要因素，算法性能和效率都开始下降，甚至最后差于VOR算法。

a. original

b. VOR算法

c. VORP算法

d. VORCP算法

图9 算法横向比较

表1 无线传感网络覆盖度大小

5 结束语

覆盖是传感器网络中的一个基本问题，覆盖度是衡量无线传感网络工作性能好坏的重要指标，覆盖洞的出现将影响该参数。

本文在混合传感网络下基于传统的覆盖洞修复算法VOR，针对其存在的不足，提出两种改进的覆盖洞修复算法：基于优先机制的VORP算法和基于复杂优先机制的VORCP算法。通过对两种改进算法的仿真与分析以及对运用修复算法前和分别运用VOR、VORP、VORCP算法后监测区域无线传感网络覆盖的纵向和横向的比较分析，表明本文所提出的改进算法在性能和效率上优于传统的覆盖洞修复算法。在后续的研究工作中，将对基于复杂优先机制的覆盖洞修复算法的复杂度进行进一步的研究，以更好的提高其性能。

本文研究工作得到成都市科技惠民项目(2014- HM01-00310-SF)的资助，在此表示感谢！

[1] 曾雅丽, 赵福双. 无线传感器网络覆盖空洞修复策略[J]. 中国科技信息, 2015(9): 66-67.

ZENG Ya-li, ZHAO Fu-shuang. Strategy of coverage hole repairing in wireless sensor networks[J]. China Science and Technology Information, 2015(9): 66-67.

[2] 王珊, 王庆生, 樊茂森. 基于移动节点的无线传感器网络覆盖空洞修复方法[J]. 传感器与微系统, 2015(4): 134- 136.

WANG Shan, WANG Qing-sheng, FAN Mao-sen. Repairing method for coverage hole of WSNs based on mobile node[J]. Transducer and Microsystem Technologies, 2015(4): 134- 136.

[3] 戴国勇, 陈麓屹, 周斌彬, 等. 基于Voronoi图的无线传感器网络覆盖空洞检测算法[J]. 计算机应用, 2015, 35(3): 620-623.

DAI Guo-yong, CHEN Lu-yi, ZHOU Bin-bin, et al. Coverage hole detection algorithm based on Voronoi diagram in wireless sensor network[J]. Journal of Computer Applications, 2015, 35(3): 620-623.

[4] 范高俊. 无线传感器网络覆盖性能评估与提高[D]. 长沙: 国防科技大学, 2009.

FAN Gao-jun. Evaluating and improving coverage performance for wireless sensor networks[D]. changsha: National University of Defense Technology, 2009.

[5] 李红. 无线传感网络两类覆盖问题研究[D]. 镇江: 江苏大学, 2012.

LI Hong. Research of two type coverage issues in wireless sensor networks[D]. Zhenjiang: Jiangsu University, 2012.

[6] 宁菲菲. 无线传感器网络中的覆盖算法研究[D]. 长沙: 中南大学, 2010.

NING Fei-fei. Research on coverage algorithms in wireless sensor networks[D]. Changsha: Central South University, 2010.

[7] 张帆. 无线传感网络基于覆盖问题的部署模型研究[D]. 大连: 大连理工大学, 2009.

ZHANG Fan. Research on deployment model base on coverage in wireless sensor networks[D]. Dalian: Dalian University of Technology, 2009.

[8] 王鲁鹏. 无线传感器网络覆盖与连通问题研究[D]. 长沙: 中南大学, 2005.

WANG Lu-peng. Research on coverage and connectivity in wireless sensor networks[D]. Changsha: Central South University, 2005.

[9] 李致远. 无线传感器网络节能覆盖算法及仿真研究[D]. 开封: 河南大学, 2008.

LI Zhi-yuan. Research on Energy-efficient coverage algorithms and simulation in wireless sensor networks[D]. Kaifeng: Henan University, 2008.

[10] 刘丽萍. 无线传感器网络节能覆盖[D]. 杭州: 浙江大学, 2006.

LIU Li-ping. Energy-efficient coverage issues in wireless sensor networks[D]. Hangzhou: Zhejiang University, 2006.

[11] 于书鹏. 无线传感器网络k-覆盖算法研究[D]. 济南:山东大学, 2011.

YU Shu-peng. Research on k-coverage algorithms in wireless sensor networks[D]. Jinan: Shandong University, 2011.

[12] ANTOINE G, JEAN C, DAVID S R, et al. Localized sensor area coverage with low communication overhead[J]. IEEE Trans on Mobile Computing, 2008, 7(5): 661-672.

编 辑 叶 芳

Improved Recovery Algorithms of Coverage Holes in Hybrid WSN

YU Qin1, WANG Wei-dong2, LI Long-jiang1, and QIAN Ting1

(1. School of Communication and Information Engineering, University of Electronic Science and Technology of China Chengdu 611731; 2. School of Information and Software Engineering, University of Electronic Science and Technology of China Chengdu 610054)

This paper proposes two improved recovery algorithms on the base of Voronoi algorithm (VOR): priority-based VOR (VORP) and V complex priority-based VOR (ORCP) of coverage holes in wireless sensor networks (WSNs) in view of the existing problems in traditional VOR. Through the simulations and analyses of these two improved algorithms, as well as the vertical and horizontal comparisons and analyses of recovery algorithms unused and VOR, VORP, VORCP used, the results demonstrate that the proposed algorithms have better performances and efficiency than traditional recovery algorithms of coverage holes in WSNs.

coverage holes; hybrid sensor network; priority-based scheme; recovery algorithm

TN919

A

10.3969/j.issn.1001-0548.2017.04.010

2016-02-22；

2016-06-01

国家自然科学基金面上项目(61273235)；四川省科技计划(2016GZ0073)；交通运输部信息化技术研究项目(2014364X14040)；985工程杰出人才引进与培养计划(A1098531023601064)

于秦(1974-)，博士，副教授，主要从事无线网络、移动通信、信息安全等方面的研究.