无线传感器网络覆盖漏洞发现与修补算法综述

杨莉莉

摘 要： 无线传感器网络因其能检监测目标区域特定事件的发生，而被广泛应用到军事国防、交通运输、智能家居等各个领域。无线传感器节点通常是有电池供电，具有能量有限、难补给的特点，容易导致节点死亡，造成监测区域内出现监测覆盖漏洞的出现。为了保证传感器网络的覆盖率，发现监测区域内的覆盖漏洞并进行修补，就需要有效的覆盖漏洞发现和修补算法。文章详细描述了几种发现和修补覆盖漏洞的算法，并对算法做了相应的分析。

关键词： 无线传感器网络； 覆盖漏洞； 发现算法； 修补算法

中图分类号：TP393 文献标志码：A 文章编号：1006-8228（2017）05-34-03

The survey of discovery and repair algorithm for wireless sensor networks coverage holes

Yang Lili

（College of Computer and Information Engineering， Henan University， Kaifeng， Henan 475004， China）

Abstract： Wireless sensor networks are widely used in military defense， transportation， intelligent home and other fields because of its ability to detect the occurring of specific events in the target area. However， the wireless sensor nodes are usually battery-powered， and have the characteristics of limited energy and difficult to supply， which can lead to the death of the nodes， resulting in the emergence of coverage holes in the monitoring area. In order to ensure the coverage of the wireless sensor networks， to find the coverage holes in the monitoring area and repair them， the effective algorithms for finding and repairing are needed. This paper describes several coverage holes discovery algorithms and repair algorithms， and makes the corresponding analysis of them.

Key words： wireless sensor networks； coverage holes； discovery algorithm； repair algorithm

0 引言

无线传感器网络（Wireless Sensor Networks， WSNs）由无数个微型传感器节点組成，并且每个传感器节点能够感知周围环境，能够实时监控感知区域内特定事件的发生[1]。伴随着微电子技术、传感器技术、信息处理等技术的不断发展，传感器节点制造成本不断降低，无线传感器网络迅速发展，其正被广泛应用于现代农业、智能建筑、交通运输、森林防火等各个领域[2]。而服务质量（Quality of Service， QoS）体现了无线传感器网络感知现实世界的能力，是对监测区域的覆盖程度衡量的一项重要指标[3]。

传感器网络覆盖漏洞是指监测区域中存在一片连续未被任何节点所覆盖的区域。而无线传感器节点的能量通常都是由电池提供，具有能量有限、难补给的特点，同时无线传感器网络往往被部署在人难以到达的复杂区域。节点能量耗尽导致传感器节点死亡使传感器网络中产生不被监测的覆盖漏洞出现。

而为了保证网络的服务质量往往部署节点数量大大超过实际需求，但是这种高密度的大量部署节点同时工作时会导致采集信息冗余、通信冲突等问题，反而缩短了网络生存时间[4]。因此对无线传感器网络覆盖漏洞的发现和修补成为新的研究热点。而无线传感器网络覆盖漏洞的发现既是覆盖漏洞修补的前提，又是覆盖漏洞研究的难点。

1 传感器网络特点

无线传感器网络通过在环境中部署大量节点来实现对物理现实世界感知的能力，是物理世界和信息世界沟通的桥梁，一般由传感器节点、感知对象、观察者构成。大量的传感器节点被部署在检测区域内通过自组织的方式构成无线传感器网络。无线传感器网络被部署在恶劣环境与常见的无线网络（如：无线局域网、Ad hoc网络）相比，无线传感器网络具有以下显著特点。

⑴ 传感器节点受体积、成本的影响，其计算能力和存储能力都有限；节点受实际应用环境的影响，往往是由电池提供电力，通常能量有限、不易补给。

⑵ 为了能够获得被监测区域内的详细数据信息，无线传感器节点往往被大量部署在检测区域内，具有较高的部署密度。

⑶ 传感器网络没有严格的控制中心，所有节点地位平等，节点能够自己决定是否加入自组织成网络，具有较强的动态性。

⑷ 节点的发射功率有限，其通信范围也很小，通常只能够与其相邻节点通信。如果节点想要与其覆盖区域外的节点进行通信，必须借助其相邻节点进行转发。

无线传感器网络的特点导致部署在恶劣环境中的节点常常因为自身原因或自然灾害等各种随机因素造成的物理设备损坏或软件故障，从而导致传感器节点失去监测周围环境的能力，致使覆盖网络受损出现覆盖漏洞。

2 覆盖发现算法分析

为了保证无线传感器网络的覆盖率，需要对覆盖漏洞的进行发现，同时覆盖漏洞的发现是实现覆盖漏洞修补的基础与前提。而对传感器网络覆盖漏洞的发现算法主要分为三个方面的研究。

第一类研究主要是在保证一定的覆盖率时用概率计算的方法来计算节点密度。这些研究通常假设传感器节点均匀分布，计算所需的传感器密度满足覆盖和网络寿命要求[5-6]，但是这些研究并不能完全解决覆盖漏洞检测问题。

第二类关于覆盖漏洞发现的研究主要是用几何计算的方法来实现漏洞检测。文献[7-9]等基于几何学中的Voronoi图和Delaunary三角形原理，提出了不同的覆盖漏洞探测方法。戴国勇[10]通过计算Voronoi区域内节点到该区域的顶点和边的距离，来判断是否存在覆盖漏洞，评估节点密度、节点感知半径不同时对算法的空洞检测时间和能量消耗的影响，并且比典型的路径密度（Path Destiny， PD）在空洞检测时间和能量消耗有一定提升。而赵春江[11]在检测到覆盖漏洞的同时，能够较准确的计算出覆盖漏洞的面积，找出最佳漏洞修复位置，部署较少节点的同时保证网络的连通性。

第三类研究主要是在保证覆盖要求的前提下，提出拓扑控制解决方案，通过调度最大限度地提高传感器网络的生命时间。文献[4]作者结合移动 Agent 的特点， 提出了一种基于移动Agent的无线传感器网络拓扑发现机制，该拓扑发现机制相对于当前存在的拓扑发现算法具有很好的稳定性和良好的节能效果。

以上几类对应无线传感器网络覆盖漏洞发现算法的研究，都是在无线传感器节点的位置信息已知的条件下进行的。而节点的地理位置信息的获取主要依靠全球定位系统（Global Positioning System，GPS）定位设备[11]。采用GPS装置不仅会增加传感器网络的运行成本，在卫星信号被干扰或无法达到的区域（如深水环境、地下深井），传感器节点将无法获取到精确的地理位置信息。随着研究的深入，Gao[12]首次提出了在没有地理位置信息的条件下实现对空洞边缘的确定方法，并在不同的空洞形状条件下实现了空洞边缘节点的确定。

研究发现，一个传感器不相邻覆盖洞只有当其感应边界被它的邻居节点完全由覆盖，继而提出了“传感器边界”的概念。Bejerano[13]等借助传感器边界的概念提出循环边界序列获得各节点与其相邻节点的边界信息，判断各个节点是否被完全覆盖，并且将传感器覆盖的概念扩展到k（k>1）层覆盖，实现了覆盖区域k-覆盖的漏洞的发现，进一步提升了覆盖网络的可靠性。在文献[14]中，作者提出分布式覆盖无线传感器网络的覆盖漏洞恢复算法设计使用矢量方法来决定幅度和方向。并且，以自组织的方式通过移动节点来修复网络的覆盖漏洞。为了使节点的移动过程能量消耗最小，算法设计为移动性仅限于节点的一跳内，并且节点的最高k覆盖之后不增加其移动性。该覆盖漏洞恢复算法显示在其通信范围内移动节点有可能百分之百实现覆盖恢复。

3 覆盖修补算法分析

在覆盖漏洞填补方面，很多方法都假定传感器节点拥有精确的地理位置信息，在缺乏地理位置信息的条件下，现有的空洞填补算法都将失去作用。对于传感器网络，通常通过放置节点装备GPS定位设备或者通过设置信标节点来获得节点的粗略的地理位置，但是这些装置的使用都存在一定的限制。

在已提到的文献[11]中，采用幾何图形向量方法对节点感知范围和Voronoi多边形的位置特性相结合的理论分析方法，该方法引入部署传感器网络中的节点来降低覆盖空洞大小。一些算法采用网格覆盖的方式对传感器网络目标区域进行划分，将部署密度高的区域中的传感器节点逐步移动到部署密度低的区域来保证网络的覆盖率。苏瀚在Bejerano的空洞探测算法的基础上，提出了传感器网络中空洞填补的两个准则，即：①填补节点的引入至少消除一段空洞边缘弧；②填补节点的引入不能造成空洞的分裂。该算法将空洞填补工作分布到空洞边缘节点上分别执行，并最终实现分布式的空洞填补。

现有的空洞填补算法虽然都在一定假设条件下达到了一定的效果，但都依赖于精确地理位置信息。因此，对于未知地理位置信息的传感器网络中覆盖漏洞的监测成为无线传感器网络应用发展的新的研究方向。

4 结束语

无线传感器网络由无数传感器节点组成，具有感知物理世界的能力，被广泛应用于各个生产、生活领域。但是无线传感器节点的能量有限导致节点失去监测能力，使无线传感器网络出现未被监测的覆盖漏洞。

本文介绍了无线传感器网络的特点以及导致覆盖漏洞出现的原因。针对传感器网络节点位置信息是否已知的两种前提下，详细介绍了几种传感器网络覆盖漏洞发现算法，以及节点的位置信息已知时，覆盖漏洞的修复算法，并且对其进行了分析。而节点的地理位置信息未知是传感器网络覆盖漏洞修补的重要挑战，也是无线传感器网络的新的研究方向。

参考文献（References）：

[1] 邓鑫，张乐君.无线传感器网络可生存性增强技术研究概述[J].传感器与微系统，2014.33（1）：1-4

[2] 包旭，巨永锋.面向节点失效的无线传感器网络覆盖空洞修复算法[J].计算机测量与控制，2011.19（6）：1516-1522

[3] Xiao-heng Deng， Chu-gui Xu， Fu-yao Zhao， et al. Repair policies of coverage holes based dynamic node activation in wireless sensor networks[C]. In Proc. of the 2010 IEEE/IFIP International Conference on Embedded and Ubiquitous Computing.

[4] 凡高娟，王汝传，黄海平.基于容忍覆盖区域的无线传感器网络节点调度算法[J].电子学报，2011.39（1）：89-94

[5] S. Shakkottai， R. Srikant， N. Shroff. Unreliable sensor grids： Coverage， connectivity and diameter[C]. In Proc. of IEEE Infocom'03，April 2003.

[6] S. Kumar， T. H. Lai， J. Balogh. On k-Coverage in a Mostly Sleeping Sensor Network[C]. In Proc. of ACM Mobicom'04， Sep. 2004.

[7] Fang Q， Gao J， Guibas L J. Locating and bypassing routingholes in sensor networks[C]. In Proc. of IEEE INFOCOM，2004.4（2）：2458-2468

[8] Wang G， Cao G， Porta T L. Movement-Assisted Sensor Deployment[J].IEEE Transactions on Mobile Computing，2006.5（6）：640-652

[9] 戴国勇，陈麓屹，周斌彬等.基于Voronoi的无线传感器网络覆盖空洞检测算法[J].计算机应用，2015.35（3）：620-623

[10] 赵春江，吴华瑞，刘强，朱丽.基于Voronoi的无线传感器网络覆盖控制优化策略[J].软件通信，2013.34（9）：115-122

[11] 吴昊然.GPS和无线传感器网络融合定位算法研究[J].计算机仿真，2009.26（11）：145-148

[12] Gao J ，Lederer S， Wang Y. Connectivity-based localization of large scale sensor networks with complex shape[J]. ACM Transactions on Sensor Networks （TOSN），2009.5（4）：789-797

[13] Yigal Bejerano. Coverage Verification without Location Information[J]. IEEE Transactions on Mobile Computing，2012.11（4）：631-643

[14] Prasan Kumar Sahoo， Jang-zern Tsai，Hong-lin ke.Vector method based coverage hole recovery in wireless sensor networks[C]. International Conference on Communication Systems & Networks，2010：1-9

[15] 蘇瀚，汪芸.传感器网络中无需地理信息的空洞填补算法[J].计算机学报，2009.32（10）：1957-1970