基于移动WSN 的分布式漏洞检测与修复算法

尹 皓，王 军

（1.苏州科技大学 电子与信息工程学院，江苏 苏州 215009；2.中国科学院 长春光学精密机械与物理研究所，吉林 长春 130033）

0 引 言

无线传感器网络（Wireless Sensor Network, WSN）是由部署在目标区域的大量传感器节点通过自组织的方式构成[1]。分布的节点能够有效监测周围环境所发生的事件，并通过邻居节点将收集到的数据汇总到用户终端，以便进一步处理。但由于网络内各节点能耗不均以及物理损坏等多种原因，导致某些节点意外死亡形成网络监测覆盖漏洞[2]，因此对于传感器网络覆盖漏洞的检测与修复研究具有重要意义。

在移动WSN 中，本文设计一种分布式漏洞检测与修复算法（Distributed Vulnerability Detection and Repair Algorithm, DVDR）。该算法使用网络内已部署的移动节点来修复覆盖漏洞。当网络内任何一个节点检测到与另一个节点通信中断时，即可触发漏洞检测机制[3]，该机制通知故障附近节点收集关于漏洞的最新消息；之后每个节点转发此信息，并根据自身可用能量和与邻居距离独立决定为漏洞恢复贡献多少，同时保持现有的覆盖和连通性[4]。仿真结果表明，DVDR 算法在覆盖范围、网络能耗和连通性方面具有优势。

1 目标建模与假设

假设移动传感器网络区域为一个二维正方形区域，其中分布了n个移动节点用来监测，部署时不存在独立的节点或区域。将任意传感器节点抽象为二维欧几里得空间中的一个点，并且每个节点的感测范围是以该点为中心的布尔圆盘来建模[5]。假设所有节点规格相同，其通信范围是监测范围的2 倍，从而保证感知范围重叠的任意2 个节点之间的连通性。

此外，每个节点都有一个唯一的标识号，监测节点周期性地向各自邻居发送感测数据，并将其汇总至网关节点。每个节点定期广播心跳消息[6]，以证明其状态正常。图1 展示了每个节点及其标识号的初始部署，在通信范围内的2 个节点由一条灰色虚线连接，代表其通信链路。

图1 WSN 节点初始部署图

假设所有节点都配备有GPS 定位模块，知道自身所处位置，其中位置信息由笛卡尔坐标系中的xy坐标表示，邻居节点位置是在部署后节点相互之间交换广播信息后知晓，其中广播信息包含节点ID 号、位置信息以及监测数据等。

考虑到网络内节点能量有限，必须尽量减少节点能耗，要做到这一点，算法还需协调好两个主要的权衡问题：首先，算法必须最小化节点移动，并保证最大化覆盖范围；其次，必须尽量减少节点之间的通信，同时要保证节点移动过程中的合作。

2 分布式漏洞检测与修复算法

2.1 DVDR 总体算法过程

DVDR 主要包括两个阶段：第一阶段是漏洞检测阶段，邻居检测到一个死亡的节点，并估计其产生的漏洞大小和位置；第二阶段是漏洞修复阶段，所选节点计算恢复最大覆盖所需的移动距离和方向，之后根据计算结果节点移动修复所检测到的覆盖漏洞。

假设某一节点已经故障死亡并导致了如图2 所示的覆盖漏洞，当任意节点出现故障时，其邻居节点都会检测到这个丢失的节点，这是由于该节点没有在固定的周期内传输广播信息；此后故障节点附近的邻居节点会将自己标记为故障邻居，并启动覆盖漏洞修复过程，在此期间这些故障邻居们估计覆盖漏洞的大小和位置，并计算自己与周围邻居的交点。对于覆盖漏洞，本文只关注包围漏洞未覆盖的交点（Uncovered Intersection Point, UIP）。UIP 主要表示2 个节点感测范围内的交叉点，同时不被任何其他节点的感测范围覆盖。

图2 覆盖漏洞示意图

修复过程中，需要明确哪些节点应该参与修复，并对于选定的节点计算其新的位置，以便在保持连通性和最小化能量开销的情况下同时修复覆盖漏洞。

2.2 查找UIP 集合

在查找UIP 集合阶段，所有的UIP 将被分成成对的点，称为一个UIP 集合，同一个集合中的点属于同一个覆盖漏洞。假设各节点知道自己的位置和邻居的位置，也知道自己与邻居的感知范围，则其能够找到自己与邻居的感知范围交点。由于每个节点的感知半径固定，因而可以很容易地计算节点感知范围交集。

计算完所有交点后，将其标记为覆盖或者未覆盖交点。一个节点是否被覆盖取决于该点是否位于已知邻居节点的半径内[7]，可以通过以下不等式来检查：

式中：(xp,yp)是交叉点的二维坐标；(xc,yc)是当前被检查的邻居坐标；rs表示当前邻居的感测范围，即固定值，对于所有节点都相等。

UIP 正确配对图如图3 所示。将找到的所有UIP 交点分成唯一的对，其中每对只属于一个覆盖漏洞；再创建一组线段，将当前节点与其所有邻居连接起来，即图3 中的虚线部分；图3 中实线表示连接一对UIP。为成对UIP 的每个组合创建单独线段，当任意虚线与实线不相交时，则认为找到了UIP 的正确配对。

图3 UIP 正确配对图

图4 展示出了会被算法拒绝的UIP 集合配对，线段相交表示分配给集合的交点不属于同一个覆盖漏洞。

图4 UIP 错误配对图

2.3 根据UIP 集合检测漏洞

当故障节点的邻居检测到故障时，它们会触发漏洞检测过程的开始，并将这些节点标识为启动节点。对于任意给定的节点，如果只找到一个UIP 集合，那么这个集合与漏洞相邻；如果存在一组以上的UIP 集合，那么UIP 属于两个不同的漏洞，并且节点必须找出哪一组UIP 与最初检测到的故障节点导致的漏洞相关。

如果当前节点是启动节点，则UIP 集合即为包含故障节点半径内的点集合；若故障节点半径内没有点，那么最靠近故障节点的点集合就是UIP 集合。一旦选择了一组相关的UIP，该节点就会传输一个广播信息包，其中包含它的ID、邻居ID、它们各自坐标以及标识哪些节点参与了UIP 集合。为了保证漏洞附近的所有节点都能接收到该信息，采用的转发方案[8]如下：如果接收该信息包的节点是启动节点，那么它只转发该消息；如果它为非启动节点，那么这会作为其成为覆盖漏洞邻居节点的通知。之后非启动节点计算自己的UIP 集合，并执行相同的消息转发，直到漏洞附近没有新的非启动节点为止。对于非启动节点，其UIP 集合仅仅只是来自通知邻居的点的集合。图5 展示了覆盖漏洞是如何被相关UIP 集合正确识别的。

图5 UIP 集合识别覆盖漏洞图

2.4 寻找补洞候选节点

在移动WSN 中，默认覆盖漏洞周围的所有节点都是漏洞修复的候选对象，但是，对于其是否参与修复，必须满足特定要求。最适合移动的节点是仅与当前覆盖漏洞相邻的节点，若这些节点相邻了不止一个覆盖漏洞，则必须验证其是否被允许移动。

如果候选节点只是1 个漏洞的邻居，那么其能够移动；若候选节点是2 个漏洞的邻居，应该计算它的覆盖增益来决定其是否移动；若候选节点是2 个及以上漏洞的一部分，则其被禁止移动，这是由于通过移动修复1 个漏洞会加剧其他漏洞覆盖范围。

对于任何与2 个漏洞相邻的节点，它将有2 组UIP集合，其中只有一个集合会被标记为与当前覆盖漏洞相关。UIP 集是由2 个节点组成，这2 个点限定了相同的覆盖范围。如图6 所示，DVDR 算法正在寻找候选节点修复H1漏洞，其中UIP 集{P1,P2}是相关集，属于H1；而{P3,P4}是不相关集，属于H2。

图6 UIP 集之间距离比较图

若非相关UIP 集距离d34小于相关UIP 集距离d12，这表明在相关漏洞H1的方向上移动会提供净覆盖增益；若d34小于阈值距离dth，则该节点允许移动。但需要注意，对于这类节点本质上总会遗漏另一个漏洞，但大多数时候，移动节点获得的覆盖率比失去的多，所以这是一种可以接受的权衡[9]，并且节点移动的距离不会超过其通信距离。因此，WSN 内不会中断路由或连接。

2.5 节点移动距离与方向

当选择一个节点进行漏洞修复时，节点需要知道它将移动的确切位置，可以通过计算移动距离和方向来完成。节点移动之前，首先找到当前节点被覆盖的交叉点（Covered Intersection Point, CIP），CIP 是位于第3 个节点的感测范围内的2 个节点的感知范围的交叉点，因此当前节点必须找到包含在其自身半径内的所有交点，这些点用来指示该节点可移动多远，且不会影响覆盖范围和网络连通性。

根据广播信息包，每个节点都知道自己和邻居的位置，因此，当前节点只需找到其邻居之间的所有交点，然后使用2.2 节中不等式（1）检查交点是否位于自己半径内，并将位于半径之外的交点丢弃，剩余的交点则为当前节点的CIP 交点。若当前节点半径内没有CIP 交点，则节点可能是孤立的，也可能与其邻居感应半径不重叠。这两种情况都意味着当前节点的任何移动都会加剧现有的覆盖漏洞。所以若未检测到CIP 交点，则当前节点不能移动。在确定移动距离之前，需要知道移动的确切方向。

由于漏洞检测阶段已经完成，当前节点已知其哪个UIP 集是相关的，对于运动方向，首先需要计算连接相关集合的2 个UIP 的线段中点[10]，坐标标记为(xmid,ymid)；之后从当前节点的位置(xnode,ynode)开始，指向中点(xmid,ymid)的单位向量就是其方向向量，其计算公式如下所示：

通常vdir的方向就是节点修复漏洞应该移动的方向，但是若当前节点中心到2 个UIP 的角度大于180°，此时节点会向相反方向移动，远离覆盖漏洞，如图7a）所示。为了纠正这种情形，使用线段交点来检查这种情况，如果当前节点每个邻居都用一条线段连接到它，这些线段中的任何一条与相交，则vdir必须取相反方向移动（即乘以-1）。正确移动方向vdir如图7b）所示，其中不与邻居连接到当前节点的任何线段相交。

图7 方向向量正确与错误示意图

最后计算当前节点的最大允许移动距离。计算每个CIP 到与vdir方向相反的节点边缘的欧几里得距离，并设定dmov为移动距离，其移动距离与方向伪代码如下所示：

Input：相关UIP 集合，邻居节点列表

Output：移动距离dmov，方向向量vdir

1. 计算CIP 交点

2. if（No of CIP < 1）then

3. returndmov=∅

4. end if

5. 计算相关UIP 集的中点

6. 计算方向向量vdir

7. if（从相邻节点到当前节点的任何线段与相关的UIP 线段相交）then

8.vdir=-vdir

9. end if

10. for 每个CIP do

2.6 对节点进行移动分级

若所有可能移动的候选节点都试图修复漏洞，那么当每个节点都汇聚到覆盖漏洞上时，它们的感知覆盖面积肯定会有大量重叠，在增加网络能耗的情形下，会降低网络覆盖率，因此需要限制节点移动，以降低能耗并提高覆盖范围。

本文设计一种节点移动分级系统，分级较高的节点移动最大距离，而分级较低的节点需要相应调整其移动距离。由于在2.3 节中设定覆盖范围内的所有节点之间共享了相关UIP 信息，因此进行分级计算的每个单独节点值都相同，并且节点可以在不进行任何进一步沟通的情形下就分级排名达成共识。

DVDR 算法使用一个名为“合格性（eligibility）”的变量查看哪些节点在移动中具有最高优先级。分级排名取决于两个标准：估计移动距离和弧长。移动距离是指节点在不失去当前邻居连接的情况下可以移动的距离；弧长是指节点的覆盖周长中比邻居当前覆盖漏洞的部分，可以找到当前节点的相关UIP 集之间距离来估计它[11]。这两个标准决定了一个节点通过移动可以获得多少覆盖率。

eligibility 的计算公式如下：

式中：larc为估计的弧长；dmov为标准化最大移动距离；α是调整系数，用来权衡哪个参数对优先级影响更大，其值由文献[10]参考得到。

当所有节点eligibility 都已计算完毕，它们将按降序排列。如果多个节点具有相同的eligibility，令具有最低标识号的节点具有更高优先级，这是为了减少通信能耗，使得节点能够快速进行移动修复。图8 所示为节点通过eligibility 计算后如何进行漏洞修复的过程。

图8 覆盖漏洞修复后的WSN

3 仿真结果与性能分析

3.1 仿真实验设置

在本节实验中，使用Matlab 仿真软件对提出的DVDR 算法进行验证，并将其与最远邻居干预算法（Farthest Neighbor Intervention Algorithm, FNIA）和中心简单移动算法（Center Simple Moving Algorithm, CSMA）这两种经典算法进行比较。

在网络内部署90 个可移动传感器节点，每个节点最大感知半径为15 m，最大通信半径为30 m，令所有传感器节点以分布式方式随机分布在一个300 m×300 m的二维区域内，并设置以下指标类衡量算法性能：

1）覆盖率：由一个或多个传感器节点监测的传感器网络覆盖比例。

2）节点移动次数：响应检测到覆盖漏洞后的节点移动次数。

3）移动距离：对覆盖漏洞做出响应的所有节点移动总距离。

4）累计能耗：节点移动与通信消耗的总能量。

5）分区数量：分区是一组相互连接但与网络其余部分隔离的节点，大规模节点故障后，分区是不可避免的。

6）隔离节点数量：隔离节点是分区的一种特殊情况，整个分区由一个节点组成。不能通信的孤立节点对网络没有作用。

3.2 覆盖率分析

为了验证在多个节点发生故障后，不同算法对于覆盖率的修复情况，本文比较了三种算法在网络覆盖率修复方面的性能，并且为了突出覆盖算法的优势，在其中加入了不使用修复算法的覆盖率变化曲线。其覆盖率变化曲线如图9 所示。

图9 多种算法覆盖率比较结果

由图9 可知，所有算法开始都是在100%覆盖率的网络中运行，随着故障节点个数增加，没有使用覆盖漏洞修复算法的网络监测覆盖迅速恶化，而其他三种算法开始时性能较为相似。但是，CSMA 算法需要密集部署，随着节点故障数增多，其覆盖率修复性能快速下降，事实上，当剩余节点很少时，CSMA 算法的修复尝试会变得有害，其性能甚至比没有修复算法的网络还要糟糕。DVDR 算法和FNIA 算法性能较为相似，本文算法在覆盖漏洞检测与计算方面更为精确，所以算法在覆盖率修复表现上更为突出。

3.3 网络能耗分析

图10 所示为DVDR、FNIA 和CSMA 这三种算法在节点数量一定时WSN 内能量消耗情况，其中横轴代表故障节点数，纵轴为网络内节点累计能量消耗。

图10 移动过程中消耗的总能量

图10 中，CSMA 算法使用虚拟的方向来确定节点应该移动到的位置，但其没有考虑节点能耗，以致于CSMA 中所有节点都被吸引至覆盖漏洞附近，若漏洞较大，其会消耗很多能量。如图10 中所示，当多个节点发生故障时，CSMA 能量累计消耗最大。

FNIA 算法在选择节点移动时会考虑其能量影响，它总是选择那些具有较高能量储备的节点。但是由于其只使用一个替换节点来修复覆盖漏洞，所以该替换节点必须移动较远距离；随着故障节点增多，FNIA 算法会发生每个替换节点的移动，从而留下另一个覆盖漏洞。这种级联方式选择替换节点的措施，故障节点越多其能耗越高。本文DVDR 算法只允许故障节点邻居作为替换节点，这就极大地限制了替换节点移动距离引起的节点能耗，并且这种决策也并不影响网络覆盖漏洞修复性能。

3.4 连通性分析

在三种覆盖漏洞修复算法中，DVDR 保持了最稳定的连通性能，因为它确保了任何移动节点都不会出现中断通信连接的状况；而FNIA 和CSMA 算法并未考虑连通性因素。

图11 所示为三种算法的连通性比较结果。从图11可以看出，在20 个节点故障之后，CSMA 算法的连接数急剧增加。从图9 中可以看到，其覆盖范围同时快速减少，这是由于当可用节点数减少时，其覆盖漏洞变得极大，幸存节点无法处理；加上没有检测机制，漏洞吸引力导致节点聚集在漏洞中心，从而增加了连通性并减少了覆盖。

图11 算法连通性比较结果

如图11 所示，FNIA 算法注重最大化覆盖范围，但其没有考虑节点连通性因素。若允许节点获得更大覆盖范围，它们可能中断现有的连接，这也是FNIA 算法的连通性比无修复算法更差的原因。另一方面，DVDR 算法在最大化覆盖范围的基础上加入了节点连通性因素，不允许其中断现有连接，因此它在这两种权衡之间最为合适。

4 结 语

本文针对移动无线传感器网络覆盖漏洞边界搜寻不准确、漏洞修复能耗过高的问题，提出一种低能耗和高覆盖率的分布式漏洞检测与修复算法。该算法只需要距离漏洞一跳的邻居节点来进行检测与修复工作，进而恢复网络覆盖范围与连通性，这使得其可以应用在大型网络。仿真实验中，将本文算法与FNIA 和CSMA 算法进行比较，在给定相同部署与相同故障节点数量下，DVDR 算法在网络覆盖率、累计能耗和节点连通性等方面具有显著提高。

在后续研究中，算法会在更贴近实际情况的三维空间中进行实验验证，并且考虑监测区域内外界噪声以及通信延时等因素对实际漏洞修复的影响，以达到更适用的覆盖漏洞修复效果。