无线传感器网络覆盖空洞修复算法综述

田晓光

(河南大学计算机与信息工程学院，河南 开封 475000)

0　引言

无线传感器网络（WirelessSensor Networks,WSN）对人类的生活和生产方式带来巨大的变革，被认为是21世纪最重要的技术之一。无线传感器网络由微机电系统的支持发展而来，是一种分布式传感网络，其具有大规模、动态性、自组织、以数据为中心等特点，被广泛应用于军事国防、医疗健康、智能家居等各个方面[1]。覆盖质量是无线传感器网络应用中最重要的问题。评价传感器网络覆盖质量的一个重要指标是节点覆盖率[2]，如果节点覆盖率过低会导致网络中出现覆盖空洞，造成数据监测不准确，更为严重的可能会导致对目标区域监测数据错误。

无线传感器网络常被用于紧急救援、空间探索、军事应用等特殊环境。由于应用环境特殊，传感器节点常被随机布撒于目标区域，并通过自组织形成网络。因此恶劣的环境、节点能量耗尽以及动物入侵等因素的影响都有可能造成节点死亡，从而导致网络中会出现某些区域未被任何节点感知，形成覆盖空洞。若不及时修复就可能引起节点通讯受阻、网络数据监测不准确等问题[3]，严重的还有可能引起网络瘫痪。为了保证网络正常运行，需要对网络中出现的覆盖空洞采取合适的修复策略，以保证网络覆盖质量，维持网络正常运行。

1　无线传感器网络特点

相比于一般网络，无线传感器网络一般都应用于人类无法到达甚至危险的区域。无线传感器网络节点的位置一般是固定不变的，只有极少数节点需要移动。一般情况下通过随机部署节点，利用节点自组织形成网络。无线传感器网络还具有以下显著特点。

⑴ 规模巨大。通常无线传感网络在运行的时候为了保证覆盖质量一般要求网络部署时一定要保证网络中节点具有一定的冗余，因此网络在部署初期需要部署大量的传感器节点，这样既减少了网络对单个传感器节点的依赖，同时也保障了网络的健壮性。虽然要求网络中具有一定的节点冗余，但并不是冗余越大越好，因为节点冗余过大不仅会造成监测成本过高而且会导致后期维护成本增大。

⑵ 动态性。动态性是指在网络中节点增加或去除都有可能改变网络的拓扑结构。在无线传感器网络运行的过程中，由于节点能量耗尽等其他因素的影响可能导致节点死亡造成网络中拓扑结构的改变。新增传感器节点到网络中同样会导致网络拓扑结构发生变化，因此网络中的拓扑结构并不是一成不变的。

⑶ 自组织。在监测区域内，一般都是随机部署大量传感器节点，由于节点没有其他网络可依赖，其通过自组织形成网络，并以多跳的方式传送和转发数据。

⑷ 以数据为中心。无线传感器网络以数据为导向，当用户指定监测目标，网络会通过节点协作的方式监测用户感兴趣的目标属性值，然后通过节点转发将数据发送到汇聚节点，再由汇聚节点将数据通过卫星等发送到计算机，经计算机分析后将数据展现给用户。

⑸ 相互协作执行任务。无线传感器从部署到执行都是由多个传感器节点共同参与完成的，在数据转发阶段传感器节点需要互相通信，然后数据经过多个传感器节点以多跳的方式将数据转发到汇聚节点。

2　覆盖空洞修复算法分析

针对无线传感器网络覆盖空洞修复问题国内外众多专家学者作了大量研究，也提出了很多开创性的算法思想，主要分为以下三类。

⑴ 基于几何计算。核心思想是在保证网络中节点冗余度的前提下，找出传感器网络中覆盖空洞的最佳修复位置并修复。文献[4-8]都是基于节点的位置在网络中构建几何关系，确定空洞的最佳修复点，最终根据修复点的位置新增正常节点，达到修复覆盖空洞的目的。文献[4]在监测区域内随机部署传感器节点并在节点感知范围相同的前提下，提出分析近似算法。计算随机部署节点的感知覆盖率，并表示具有覆盖重叠区域的任何两个传感器节点的顶点之间存在的边缘，主要是近似至少一个感测节点覆盖的感测区域的比例，并给定二维泊松过程中每单位面积的预期节点数目，通过几何图形的性质得到近似概率。该算法可以指导节点的部署，并在后期网络出现覆盖空洞时，指导节点修复。文献[6]提出基于Voronoi覆盖洞修复算法（EECHS），随机部署的节点将监测区域划分为若干Voronoi，将划分后Voronoi分割为若干三角形并结合相邻节点生成的Voronoi找到覆盖空洞的位置，然后连接节点与相邻公共边两端点形成一个夹角，在夹角平分线上找到最优空洞修复点。

虽然该算法可以较好的修复覆盖空洞，但该算法复杂程度较高且修复后节点冗余较大。文献[7]针对节点失效或死亡造成的网络覆盖空洞，提出在网络部署时为每个传感器节点设置一个能量阈值，当网络运行过程中某个节点的能量低于设定的阈值时，该节点向汇聚节点发出信号，汇聚节点认为发出信号节点的所有邻居都为覆盖空洞的边界点，然后在低于能量阈值节点的覆盖范围内找出冗余节点，该节点即为覆盖空洞修复点。文献[8]针对修复空洞问题提出最佳节点匹配算法（BFNP），该算法前提是在网络部署初期部署部分惰性节点即未激活节点，当某惰性节点符合修复空洞要求时激活该节点。当网络管理者发现网络中由于节点死亡等原因造成节点失效时，检测网络中是否存在覆盖空洞，如果存在覆盖空洞则以覆盖空洞边缘为边界，根据距离查询空洞最近处未被激活的节点，激活该节点来达到修复覆盖空洞的目的。

⑵ 移动节点辅助。在传感器网络中全部使用移动节点，实现节点以移动最短的距离最大程度地修复覆盖空洞。文献[9-11]为了使节点移动距离最小，全部采用移动节点修复覆盖空洞。这样虽然能较好地控制节点移动的距离，但网络部署花费过高、运行代价过大。文献[9]基于集群式的分布网络提出虚拟力算法，网络部署初期将传感器节点随机部署在监测区域并根据虚拟力算法中的排斥力将节点均匀分开，以达到监测区域被最大程度覆盖的目的。当网络中出现覆盖空洞时，根据算法中的吸引力和排斥力，控制节点移动方向，将节点移动至最佳修复位置。由于移动节点的移动距离有限，为了使移动节点用最少的能量消耗去最大程度地修复覆盖空洞，文献[11]提出了基于移动节点的动态修复算法（DCM），该算法中网络对节点的决策和移动完全自治，不需要外界干预，网络控制部分传感器节点，以确定的位置移动实现对网络覆盖最大化。

⑶ 静动节点混合部署。部署网络时在静态传感器节点中加入一定量的移动节点，当需要修复网络覆盖空洞时，采用移动节点修复覆盖空洞并以最小的移动代价修复网络覆盖空洞，也在一定程度上降低了后期网络维护成本。文献[12-14]都是基于移动节点和混合节点组成的混合网络修复覆盖空洞。假设覆盖空洞已经存在且位置已知，文献[12]提出基于移动节点的覆盖空洞修复算法（PATT），该算法将已知覆盖空洞连接成多边形，三个相邻顶点将多边形划分为若干三角形，为保证新增节点最大程度地覆盖三角形所在的空洞区域，在三角形边的中垂线上计算出移动节点的最佳修复位置，然后将修复后的节点加入到网络中。依据此算法将覆盖空洞采用三角形逐步贴片的方式使覆盖空洞逐步变小，直至达到满意的修复效果。但是如果完全修复覆盖空洞，所消耗的移动节点较多，网络复杂度较高。文献[13]基于文献[12]提出基于距离的无线传感器网络覆盖空洞修复算法，将已确定修复位置的移动节点加入传感器网络中，然后将覆盖空洞边缘连接成多边形，连接不相邻多边形的两个顶点并找出多边形中两顶点连线最长的线段，说明该线段上存在修复覆盖空洞的最佳位置，根据文献[12]计算多边形中三个相邻顶点形成三角形边的中垂线，计算该中垂线，求出多边形中不相邻两顶点连线的最长线段的交点，该交点即为移动节点最佳修复位置。该算法相较于文献[12]减少了移动节点的数目，在一定程度上使网络复杂度降低。文献[14]提出基于探测率的覆盖空洞修复策略。依据节点探测模型，在监测区域内所有点的探测概率连续，探测过程中若探测概率达到最低值则说明该点是需要修复的位置，然后在该位置放置一虚拟节点，直到探测完成。探测完成后将移动节点移到虚拟节点的位置即最佳修复点。该算法在保证网络最大覆盖的同时，也控制了移动节点的移动距离和节省了节点的资源。

3　结束语

无线传感器网络具有对外界环境感知能力，是由若干个传感器节点自组织形成网络，通过多跳的方式发送和转发数据。当某个或某些传感器节点因能量耗尽或其他因素造成节点死亡，可能会出现网络覆盖空洞从而导致网络发送或转发数据异常，因此当网络中出现覆盖空洞时需进行及时的修复。

文本介绍了无线传感器网络的特点以及出现覆盖空洞的主要原因，并针对传感器网络空洞修复问题详细介绍了几类覆盖空洞修复算法并作必要分析。文中算法大部分都采用MATLAB理想环境下进行仿真实验，未考虑算法在实际应用中温度、湿度等环境因素的影响，如何在考虑环境因素的条件下也能达到理想的修复效果也是未来研究的重点。

参考文献(References):

[1]杨玺.面向实时监测的无线传感器网络[M].人民邮电出版社,2010.

[2]Wei An,Nan Qu,et al.Coverage hole problem under sensing topology in flat wirelesssensornetworks[J].WirelessCommunications andMobileComputing,2016.10:578-589

[3]Surjit S,Rajeev M S.Some Aspects of Coverage Awareness inWirelessSensorNetworks[J].Procedia Computer Science,2015.10:160-165

[4]Xiaoyun Li,David K.Coverage Properties of the Target Area in Wireless Sensor Networks[J].IEEE Transactions on Information Theory,2012.58(1):430-437

[5]LINJW,CHENYT.Improvingthecoverageof randomized schedul-ing in wireless sensor networks[J].IEEE Transactions on WirelessCommunications,2008.7(1):4807-4812

[6]赵春江,无华瑞,刘强等.基于Voronoi的无线传感器网络覆盖控制优化策略[J].通信学报,2013.9:115-122

[7]包旭,巨永锋.面向节点失效的无线传感器网络覆盖空洞修复算法[J].计算机测量与控制,2011.19(6):1516-1518

[8]胥楚贵,邓晓衡,邹豪杰.无线传感器网络覆盖空洞修复策略[J].传感技术学报,2010.23(2):256-259

[9]ZOU Y,CHAKRABARTY K.Sensor deployment and targetlocalization based on virtual forces[A].INFOCOM2003[C],2003.1293-1303

[10]WANG G,CAO G,PORTA T.Movement-assisted sensordeploy-ment[J].IEEETransaction onMobile Computing,2006.5(6):640-652

[11]SEKHA A,MANOJ B,MURTHY C.Dynamic coverage maintenancealgorithms for sensor networks with limited mobility[A].Proceedingsof the 3rd IEEE Int'l Conf on Pervasive Computing and Communica-tions[C].Kauai,Island,2005:51-60

[12]王良民,李菲,秦颖.基于移动节点的无线传感器网络覆盖洞修复方法[J].通信学报,2011,32(4):1-8.

[13]韩春延.基于距离的无线传感器网络覆盖洞修复算法[J].传感器与微系统,2013.32(4):91-94

[14]黄月,吴成东,张运洲,等.基于移动节点的无线传感器网络覆盖优化[J].东北大学学报(自然科学版),2012.33(2):165-168