传感器网络的修补算法仿真与性能分析

王志强

济源职业技术学院，河南 济源 459000

传感器网络作为一项影响世界的新兴技术，在各领域都拥有着非常广阔的应用前景[1]。郝占军等人提出了WSN 三维覆盖空洞动态修复方法，以最少的节点完成整体网络覆盖[2]。邹增辉等人设计了一种基于可信信息覆盖模型的覆盖空洞检测策略，有效确定可信信息覆盖空洞数目和边界信息[3]。本文采用三角形分解法[4]，利用其中三个相邻节点所形成的三角形的边长、角度来计算出移动节点的最佳位置，通过在该位置部署移动节点，以不断地填充三角形区域来修补传感器网络中覆盖空洞。

1 基于三角形信息的覆盖空洞修补算法设计

1.1 最佳移动节点位置的几何模型

已知节点的通信半径为R，设B 为首个覆盖空洞修补发起点，通过与相邻节点的通信确定边缘节点A 和C 的位置，并且得到∠的大小，然后通过测距算法得到AB 和BC 的长度x、y，利用上述条件进行和的求解，具体过程如下。

图1 移动节点的最佳位置模型

如图1 所示，过节点E 作AC边的垂直平分线，交AC 于F 点，而节点E 和A、C 之间保持最大的通信距离。

在得到了线段BE 的长度后，在△ABE 中，利用余弦定理可得

但是在求解出来后，可能存在另一种情况，即当移动节点E 不能与边缘节点B 进行直接通信时，为了保证B、E 两个节点之间的正常通信与△ABE内空洞覆盖率，就需要限定BE 的长度不能大于节点的通信半径R。即最终线段BE 长度f 的限制条件为，在最终BE 的长度f 确定后，可在△中求解∠的大小

1.2 PATT 算法修复空洞的流程图

下图为使用PATT 算法进行修补整个覆盖空洞的具体流程：

如图2 所示，为利用PATT 算法进行整个传感器网络覆盖空洞修补的具体流程，需要注意的是x、y 和分别为线段AB、BC 的长度和∠ABC 的大小，边缘节点集合由横坐标集合和纵坐标集合其中为常数，sum 表示的是总共所增加的节点数量，初始时令sum=0，每增加一个移动节点时sum 加1，并且算出当前覆盖空洞的覆盖度，当整个传感器网络中的空洞覆盖率达到90%以上时，停止修补过程。

图2 利用PATT 算法进行覆盖空洞修补的具体流程

2 算法仿真和分析

2.1 仿真环境设置

本文算法在matlab7.10 上进行仿真，用边长为a 的正n 边形作为传感器网络的覆盖空洞模型，所有的移动节点都是随机分布并且处于休眠状态，但是能被其他节点唤醒，移动到指定位置。传感器网络中的节点感知半径为r，其通信半径R=2r。在修补覆盖空洞的仿真实验中，并没有考虑各节点在通信过程中所产生的能量消耗。一般是选择最近的节点移动到指定位置进行修补。

2.2 修补效果分析

首先要验证算法的可行性，在此仿真实验中，需要在边长a=13m，n=15 的正十五边形的覆盖空洞模型下进行修补，节点的感知半径r=7.5m,。如图3所示，为空洞修补仿真实验的结果。

图3 正15 边形的修补效果图

由上图可以直观的看出本算法具有修复空洞的可行性，修补完成后，得到相关数据进行分析：sum=9，即表示使用了9 个移动节点进行了整个正十五边形的空洞修补；=0.9256，允许存在少量的覆盖盲区，覆盖度符合应用要求，具有可行性。

2.3 覆盖率验证

覆盖率是衡量算法可行性的重要指标。在本文算法中，覆盖率为被覆盖的空洞面积与覆盖空洞总面积的比值，修复完成后的覆盖率的计算式如下：

图4 正25 边形的覆盖空洞修复效果图

图5 覆盖率p 与移动节点sum 的关系

由图5 可以看出，当放置的移动节点数量sum 增加时，覆盖率也随之近似线性的增大，这种近似线性的关系表明，每当在覆盖空洞中增加一个移动节点时，其空洞面积就会减少，本文算法也起到了避免修复过程中出现重复覆盖的情况，最终当节点sum=54 时，与之对应的覆盖率=0.9216，说明了本算法能保证覆盖率在90%以上。

2.4 稳定性分析

为了验证本算法具有一定的稳定性，在边长a不变的情况下，改变正多边形的边长数n，计算所需的移动节点数sum。由于改变了边长数n，从而覆盖空洞的面积S 也随之改变。在此仿真实验中，本文计算了在边长数分别为10、15…90 的27 个正多边形覆盖空洞下，修复完成所需的移动节点个数，记录下来，并以对应的覆盖空洞面积S 的变化为横坐标x，以完成修补所需的节点数sum 的变化为纵坐标，绘制成曲线图进行观察。

图6 移动节点冗余度与覆盖空洞面积的关系

如图6 所示，可以看出在正多边形边长a 不变的情况下，当覆盖空洞的面积S 增大时，其完成修补空洞所需的移动节点数sum 也随着近似线性增加，表明移动节点数目增长的速度几乎与覆盖空洞面积增长速度相同，代表着本文算法具有很好的执行稳定性。

2.5 冗余度分析

在上述算法稳定性分析的基础上，改变正多边形的边长数，即得到不同覆盖空洞面积时，使用本文算法完成整个覆盖洞的修补后，计算其不同覆盖面积对应的冗余度。

其中M 为完成修补所需的节点数，r 为节点的感知半径，S 为覆盖空洞面积。以覆盖空洞面积S 为横坐标，冗余度δ 为纵坐标，绘制成图进行分析。

3 结论

本文主要针对混合传感器网络中出现的覆盖空洞问题，在混合传感器网络模型中利用移动节点来修补其内出现的覆盖空洞，在修补效果上，能够实现使用较少的移动节点修补空洞，且覆盖度大于90%，节约了节点成本。并且算法具有良好的稳定性，不会出现随着覆盖空洞面积增大而所需移动节点数量急剧增加的情况，两者具有一定的线性关系。但漏洞修补过程会较为复杂，使得冗余度较大，因此还需考虑所增加节点在移动过程中产生的能耗以及最佳的移动路径。