非并行二分法的覆盖空洞修复算法

韩雨涝

攀枝花学院 数学与计算机学院，四川 攀枝花617000

1 引言

网络覆盖服务质量是度量无线传感器网络服务质量重要性能指标之一[1-2]。节点对监测区域的不充分的感知表现为网络中节点分布不均匀，存在未被任何节点感知范围覆盖的区域，该区域称为覆盖空洞（Coverage Hole，CH）[3-4]。覆盖空洞边缘区域的节点因过度承担数据转发任务过早死亡，加大了覆盖空洞的面积[5]。文献[6]提出覆盖空洞修复算法，向三角形网格中添加移动节点使目标区域完全覆盖。文献[7]提出分布式空洞修复算法HEAL，采用基于分布式虚拟力的覆盖空洞修复方法，只有位于距离覆盖空洞适当距离的节点才会参与空洞修复。文献[8]提出不需要节点地理位置信息的覆盖空洞修复算法CHH，通过定位的方法计算节点之间距离以及到覆盖空洞边界节点距离，但在节点测距误差较大的情况下，覆盖空洞修复率低，且该算法只能完成闭合覆盖空洞的修复。文献[9]提出了一种覆盖空洞检测和修复算法，可以完整修复网络中任意覆盖空洞。混合式传感器网络[10]是在静态网络基础上，部署少量移动节点作为辅助节点。文献[11]针对混合式无线传感器网络覆盖增强的问题，提出移动节点的路径规划算法，网络空洞修复具有最小平均检测延迟和最大覆盖率。文献[12]提出的Center算法通过估算覆盖空洞的面积，结合覆盖范围冗余度、节点剩余能量以及移动距离参数确定移动节点完成空洞修复。文献[13]提出未完全修复的HPA覆盖空洞修复算法，将两个相邻未完全覆盖交点连线的中垂线上的点作为移动节点的修复目标位置。上述方法存在的问题是空洞修复效率不高，存在空洞修复冗余度高的问题，且大多不能实现覆盖空洞的完全修复。

考虑到混合式WSN网络模型有网络成本低和节点移动灵活的特点。本文在混合传感器网络模型下，提出基于非并行二分法的覆盖空洞修复算法CHRND（Coverage Hole Repair algorithm based on Non-parallel Dichotomy），以非并行方式选择具有劣弧的空洞边界节点作为覆盖空洞修复的驱动节点，通过弧二分法确定移动节点的最佳目标位置，能以较少数量的移动节点和较低覆盖冗余实现覆盖空洞的完全修复。

2 网络模型

传感器节点在监测区域随机部署自组织构成网络表示为G=(V,E),V代表节点集合，包括移动节点和静态节点；E代表无线链路集合。网络中覆盖空洞修复由移动节点的位置迁移完成。节点位置信息通过装载GPS定位设备或已有的网络定位算法[14]获取。网络中节点的感知范围和通信范围同构，使用简单圆盘模型[15]，感知半径和通信半径分别记为RG和RT。本文基于以下定义：

定义1（空洞边界节点（Hole Boundary Node，HBN））当节点Ni存在未完全覆盖交点P，则定义Ni为HBN节点。

定义2（驱动节点）在组成覆盖空洞的边界节点集合中，用于确定覆盖空洞修复移动节点以及最佳目标位置的节点称为驱动节点。

定义3（空洞弧）每个HBN节点的感知圆盘和覆盖空洞邻接的弧段，称为该HBN节点相对于当前覆盖空洞的空洞弧。弧的弧度小于180°，称为空洞劣弧，否则称为空洞优弧。

3 CHRND算法设计

3.1 空洞修复驱动节点确定原则

空洞修复由驱动节点发起，应遵循以下原则。

原则1空洞修复应至少保证所选驱动节点的空洞弧能够被完全覆盖。

由于移动节点的覆盖圆盘无法对空洞优弧完全覆盖，故选择的HBN节点对应的空洞弧应为劣弧。根据以下定理1：当覆盖空洞未被修复，必然存在空洞劣弧，使得算法能够继续修复空洞。另外，在空洞修复过程中，对于空洞优弧，必然存在移动节点的引入将其转变为劣弧，使得算法继续进行。

原则2在覆盖空洞修复过程中，移动节点的引入应避免覆盖空洞被分割。

考虑覆盖空洞分割导致空洞数量增加，空洞碎片面积可能极小，造成大量空洞碎片的产生。为了满足完全覆盖服务质量的要求，大量移动节点导致网络成本提高，而部分区域又存在冗余覆盖，极大地浪费了节点资源。如果随机选择的HBN节点导致空洞分割，算法需重新选择HBN节点尝试覆盖空洞修复，直至所选HBN节点不产生空洞分割。

定理1在覆盖空洞修复过程中，总能在组成覆盖空洞的空洞弧集合中找到空洞劣弧，使得算法能够继续修复当前覆盖空洞。

证明 使用反证法，假设移动节点在覆盖空洞修复过程中，未能够找到满足条件的空洞劣弧，即全部空洞弧都为空洞优弧。连接未完全覆盖交点构成图1所示五边形区域。由于全部弧均为优弧，则该五边形的每个内角至少为180°，内角和至少为900°，这与公式（1）计算的五边形内角和540°相矛盾，故问题得以证明。

图1 覆盖空洞劣弧确定

3.2 基于二分法的移动节点目标位置确定

如图2网络覆盖空洞区域表示为A，假定节点N6为当前覆盖空洞修复的驱动节点，对应的空洞弧为弧P1P2。采用弧二分法确定移动节点的位置点T(xt,yt)，使得移动节点以T(xt,yt)为圆心的感知圆盘恰好完全覆盖空洞弧P1P2，即点T(xt,yt)到空洞弧的端点P1和P2的距离为节点感知半径RG。

图2 最佳目标位置点确定

（1）最佳目标位置点确定

最佳目标位置点T(xt,yt)应位于线段P1P2的中垂线的覆盖空洞侧，且到交点P1和P2距离均为RG。

方程组解(xt,yt)对应目标点T到节点N6的距离满足式（3），保证了点T(xt,yt)位于线段P1P2的中垂线的覆盖空洞侧。

当移动节点目标位置偏离点T(xt,yt)，不能保证移动节点的引入对空洞弧P1P2的完全覆盖，且有可能导致不必要的空洞分割；目标位置点沿P1P2的中垂线向下偏移虽实现了空洞弧P1P2的完全覆盖，但减少了移动节点有效修复面积，增加了修复的覆盖冗余。综上所述，点T(xt,yt)为移动节点的最佳目标位置。

（2）覆盖空洞分割分析

考虑到覆盖空洞分割造成空洞数量的增加，产生大量空洞碎片，导致移动节点数量增加以及覆盖冗余问题的出现。为此，在移动节点迁徙之前检查在位置点T(xt,yt)的移动节点引入是否会导致空洞分割。

当节点Ny在目标位置T(xt,yt)的引入和构成覆盖空洞A的HBN节点序列集合HA中任意节点Ni满足式（4）条件，则覆盖圆盘之间存在覆盖交点。

解方程组（5）得到对应交点记为Pj

当HA中不存在其他节点Nk和Pj满足式（6）条件，则定义交点Pj为未完全覆盖交点。

最后，如果移动节点Ny的引入产生的未完全覆盖交点的数量m不大于2，根据定理2可知，移动节点在目标位置点T(xt,yt)的引入不会导致覆盖空洞分割。

定理2在覆盖空洞修复过程中，当移动节点的感知圆盘与组成覆盖空洞A的集合HA所有HBN节点的感知圆盘的未完全覆盖交点不大于2个，则覆盖空洞不会被分割。

证明 采用反证法，假设移动节点引入产生的未完全覆盖交点不大于2个，导致覆盖空洞被分割，则至少产生两个覆盖空洞区域。图3（a）所示的每个分割的覆盖空洞存在2个未完全覆盖交点，特殊情况如图3（b）所示两个未完全覆盖交点为同一交点。总之，空洞分割产生的未完全覆盖交点大于等于3个，这与假设矛盾，故得以证明。

3.3 基于最小距离的移动修复节点确定

（1）k跳范围移动节点获取

网络中移动节点向HBN节点广播移动节点通知（Mobile Node Notification，MNN）消息，该消息包含了移动节点ID、位置和消息生命期k。HBN节点收到MNN消息，存储移动节点的ID和位置信息，当参数k减1不为0时，继续广播消息，直到k减1为0，消息不再广播。最终，每个HBN节点获得了k跳内范围内移动节点信息。将HBN节点Nk的移动节点集合记为Yk。FCN节点收到MNN消息，无需存储移动节点信息，仅当k-1不为0，继续广播该消息。

图3 覆盖空洞分割交点数量

（2）基于最小距离的移动修复节点确定

Nk使用最小距离法在驱动节点Nk的移动节点集合Yk中，选取距离目标点T(xt,yt)位置最近的移动节点，作为当前修复节点，记为Nr。

之后，节点Nk向移动节点Nr发送移动节点确认消息（Mobile Node Confirmation），Nr收到消息后广播移动节点删除消息（Mobile Node Cancellation，MNC），k跳内的HBN节点接收到MNC消息，删除移动节点Nr的信息。最后，移动节点Nr迁移到位置点T(xt,yt)，完成此次覆盖空洞的修复。

3.4 非并行方式的覆盖空洞修复

在覆盖空洞修复过程中，移动节点采用并行方式修复覆盖空洞，虽能快速完成覆盖空洞的修复，但冗余问题严重。如图4（a）同时选择N1和N2作为驱动节点，分别独立确定移动节点目标位置L1和L2，并发在L1和L2位置修复覆盖空洞，覆盖空洞修复冗余严重。相比之下，采用图4（b）的非并行方式的覆盖空洞修复策略，驱动节点N1确定移动节点的目标位置L1，移动节点首先在L1位置修复覆盖空洞。然后，驱动节点N2对当自己新的空洞弧使用二分法确定目标位置L2，并在该位置修复覆盖空洞，有效地提高了节点利用率，覆盖冗余明显降低。最后，在移动节点引入使得空洞不被分割基础上，定理3保证了按照该非并行二分法方式能够实现覆盖空洞完全修复。

定理3移动节点引入使得空洞不被分割基础上，采用非并行二分法能够保证覆盖空洞被完全修复。

图4 覆盖空洞修复方式比较

证明 在移动节点引入使得空洞不被分割的基础上，由于每个移动节点对覆盖空洞的修复最少能够消除2个未完全覆盖交点，根据定理2，每次空洞修复最多引入2个未完全覆盖交点。如在图5所示的覆盖空洞区域，移动节点的引入消除了P1到P4共4个未完全覆盖交点，引入了P5和P6共2个未完全覆盖交点。定理1保证了算法能以非并行方式对覆盖空洞连续修复，随着移动节点的持续引入，覆盖空洞区域面积逐步减少，未完全覆盖交点数量减少，当未完全覆盖交点数量为0，则覆盖空洞已被完全修复。

图5 覆盖空洞完全修复

算法1 CHRND空洞修复算法

0.whileHBN节点集合HA不为空

1.任选空洞弧为劣弧的HBN节点N1；

2.Nj按照二分法确定移动节点的目标位置Posj；

3.if Posj位置移动节点引入导致空洞分割then

4.return 1；

5.end if

6.Nj用最小距离法确定到Posj的最近移动节点Nj；

7.Nj沿直线移动到位置Posj；

8.集合HA删除Nj引入已完全覆盖的HBN节点；

9.if HBN节点序列集合HA不为空then

10.增加移动节点Nj到集合H；

11.end if

12.end while

4 CHRND算法仿真与分析

选取Matlab7.0作为仿真实验平台，无线传感器节点在400 m×100 m矩形区域内随机部署，静态节点数量为400个，节点感知半径为RG=10 m，通信半径为RT=20 m，静态节点能量Estatic_init=100 J，移动节点能量Emobile_init=200J，假定发送和接收一个消息能耗均为0.2 J，节点在移动过程中能量消耗为1 J/m。

4.1 CHRND算法性能分析

假定覆盖空洞完全修复需要N个移动节点。定义覆盖空洞完全修复对应的覆盖冗余度为节点覆盖总面积之和减去覆盖空洞面积的值与覆盖空洞面积的比值。

以下比较了CHRND算法与采用并行方式修复策略在不同覆盖空洞面积和不同节点感知半径下完成空洞完全修复产生的覆盖冗余度。

（1）不同空洞面积完全修复对应的覆盖冗余度

图6给出了在RG=10 m前提下的覆盖空洞面积与空洞修复覆盖冗余度关系。可以看出，CHRND算法覆盖冗余度在0.152～0.354之间，当空洞面积区域较小，覆盖冗余度较大，随着空洞面积增大，覆盖冗余度降低。这是因为空洞面积较大，降低了空洞修复产生碎片的机会，也降低了修复节点与其他节点覆盖重叠的可能。另外，相对于采用并行方式修复策略，CHRND算法的空洞修复覆盖冗余度显著降低，能以较少数量移动节点实现空洞区域完全修复。

图6 覆盖空洞面积与覆盖冗余度

（2）不同节点感知半径完全修复对应的冗余度

图7给出了在空洞面积S=5 000 m2前提下的移动节点感知半径与空洞修复覆盖冗余度关系。可以看出，当移动节点感知半径较小，覆盖冗余较小，随着移动节点感知半径增大，空洞修复覆盖冗余度显著增加。这是因为当节点感知半径增大，使得每个修复节点空洞修复利用率降低。此外，同图1结论一致，图7也验证了相比于并行修复策略，CHRND算法采用非并行方法能显著降低空洞修复的覆盖冗余度。

4.2 不同算法的比较

图7 移动节点感知半径与覆盖冗余度

仿真实验分别从覆盖空洞修复所需移动节点数量、覆盖空洞修复率以及移动节点平均移动距离三个方面，比较了本文CHRND算法与现有覆盖空洞修复算法Center[12]和HPA[13]。

（1）覆盖空洞区域面积与移动节点数量关系

移动节点数量为200个，图8给出三种算法在不同覆盖空洞面积下所需移动节点的数量，可以看出，随着覆盖空洞面积的增加，三种算法所需的移动节点数量均增加。CHRND算法所需移动节点数量低于Center算法，这是因为CHRND算法使用非并行二分法确定移动节点最佳位置，避免了并发修复产生的过度冗余。另外，CHRND算法移动节点数量要高于HPA算法，这是因为HPA算法不要求空洞完全修复，允许空洞碎片存在，使得每个节点的利用率较高，空洞修复具有较低的冗余度，而CHRND算法要求实现覆盖空洞完全修复。

图8 空洞区域面积与移动节点数量

（2）网络覆盖修复率

网络覆盖修复率定义为移动节点完成空洞区域的修复面积与覆盖空洞的总面积比值。

图9 移动节点数量与空洞修复率

图9 给出了不同移动节点数量下的网络覆盖空洞修复率情况，可以看出，随着移动节点数量增多，三种算法覆盖空洞修复率提高。当移动节点较少时，三种算法的覆盖空洞修复率较低，而HPA算法覆盖空洞修复率相对较高，这是因为三种算法覆盖空洞修复所需移动节点数量均不足，而HPA算法在给定移动节点数量下实现空洞修复最大化，并不要求空洞完全修复。随着移动节点数量增加，当移动节点比例超过29%，CHRND算法覆盖空洞修复率可达100%。Center算法修复率低于CHRND算法，达到相同的修复率所需移动节点较多，Center算法虽也可完成覆盖空洞的完全修复，但所需移动节点数量比例超过了50%。HPA算法目标是提高节点使用率，因此在空洞修复过程中可能产生空洞碎片，增加了覆盖所需节点数量。Center算法修复率低于CHRND算法，这是因为Center算法仅考虑HBN节点的一跳范围内移动节点，使得移动节点数量存在不足。

（3）移动节点数量与平均移动距离

移动距离是影响移动节点能耗的一个重要因素，与网络中移动节点的数量有关。图10给出了覆盖空洞面积为2 000m2下的不同移动节点数量对应的平均移动距离。可以看出，随着移动节点数量增加，其平均移动距离减小，这是因为移动节点数量增加，更有利于选择距离目标位置更近的节点。进一步发现，CHRND算法节点平均移动距离低于其他两种算法，这是因为CHRND算法使用非并行二分法确定移动节点的目标位置，使用最小距离法选择距离目标位置最近的移动节点，而HPA和Center算法移动节点的目标位置的选择结合了节点能耗等多种因素，使得节点移动距离较长。

图10 移动节点数量与平均移动距离

5 结束语

无线传感器网络覆盖空洞影响网络服务质量性能。为此，提出了基于非并行二分法的覆盖空洞修复算法——CHRND，移动节点以非并行方式实现覆盖空洞的完全修复。仿真结果显示，CHRND算法能以较少数量的移动节点实现覆盖空洞的完全修复，移动节点修复利用率较高，具有极少的冗余覆盖，适用于通过一定数量的移动节点要求空洞区域完全修复的应用场景。