基于节点移动的WSNs覆盖空洞修复算法

黄 祎

(重庆电子工程职业学院 通信工程学院， 重庆 401331)

无线传感网络(Wireless Sensor Networks,WSNs)已在各类应用中广泛使用，如森林火灾检测、战场侦察、入侵检测、目标跟踪以及健康康复[1-2]。这些应用要求对感测区域具有足够的覆盖率。若有些区域未能覆盖，就无法收集该区域数据，降低应用性能。因此，感测覆盖率也是检测这些应用性能的重要指标。

通常，以随机或预定方式在检测区域(Region of Interest,ROI)部署传感节点。部署后，一旦传感节点失效，就无法感测环境数据，便留下未覆盖的区域，即形成覆盖空洞问题[3]。而节点硬件故障、能耗殆尽均会引起节点失效。由于传感节点随时可能失效，网络内的任何一个区域均可能会出现覆盖空洞。因此，覆盖空洞是WSNs一个不可避免的现象[4]。

覆盖空洞不但留下未覆盖空白区域，也分裂了网络，这影响了数据传输的流畅性。因此，需要引用机制[5]，使感测区域能够被连续覆盖。

然而，WSNs常部署于人难以进入或无法直接接入的区域，这就给维持网络连通和覆盖率提出了挑战。此外，如何预测何时何区域发生了覆盖空洞也是一个挑战问题。因此，设计一个动态检测、修复覆盖空洞的机制十分重要[6]。

为此，提出了一个基于节点移动的覆盖空洞的修复 (Moving Node-based Coverage Hole Repair,MNCHR) 算法。MNCHR算法依据节点剩余能量、移动距离和相互重叠区域信息，寻找最合适的修复节点。通过修复节点的移动，覆盖空洞区域，减少邻居节点间的覆盖重叠区域，进而满足区域覆盖率。

1 网络模型及问题描述

1.1 网络模型

假定在网络区域内有n个移动节点，且S={s1,s2,…,sn}随机分布于二维区域。区域内的信宿节点不受能量限制。n个移动节点自行组织并形成网络，进而保证兴趣区域被最大化覆盖[7-8]。此外，每个移动节点si∈S具有感测、存储数据的能力，并且能够与其他节点进行通信。

此外，每个传感节点si∈S具有6维信息si=[id,rs,rc,L,E,N],其中id为节点唯一标号，而rs是感测半径，rc是通信半径，而L表示节点的当前位置，E为节点的当前能量，N为节点的邻居节点集。每个传感节点能通过GPS或其他定位算法[9]获取自己的位置。同时，节点的通信半径是节点感测半径的两倍(rc=2rs)，致使任意两个有相互重叠感测区域的节点能够相互通信。

1.2 问题描述

由于节点的能耗、硬件故障等原因，节点可能会失效，形成覆盖空洞问题。而以随机方式部署传感节点，容易形成节点的重叠区域覆盖，这就为修复覆盖空洞提供了条件，即可利用重叠覆盖区域修复覆盖区域。

如图1(a)所示，灰色表示由多个节点的覆盖区域，而空白区域表示未覆盖的区域，即覆盖空洞。虚线表示失效节点的位置，而实线表示修复节点的位置。图1(b)、图1(c)显示了利用节点的移动修复覆盖空洞的过程。

图1 覆盖空洞的修复过程

如图1所示，一旦形成覆盖空洞，就选择覆盖空洞周围的节点作为修复节点，并通过节点移动，修复覆盖空洞。因此，这主要涉及两个问题：1)如何选择修复节点；2)修复节点移动距离。

2 MNCHR算法

MNCHR算法由3个阶段构成。其中第一个阶段就是计算移动距离，即修复覆盖空洞所需移动的距离；第二阶段就是计算节点的冗余率；第三个阶段就是选择最合适的修复节点。

2.1 移动距离

为了修复覆盖空洞，修复节点需要寻找最优的移动距离以及目标位置。因此，每个节点计算需要移动的距离,再通过些距离来选择最合适的修复节点。

每个节点计算它与覆盖空洞区域交叉点的位置。交叉点一定是成对出现的，因此，只选择其中一个节点用来计算此距离。将离覆盖空洞最近的那个点的坐标位置保存，另一个点丢弃。所有邻居节点通过分享自己的交叉点，如图2(a)所示。因此，若自己成为修复节点，节点就计算所需的移动距离d，即：

(1)

式(1)中，(xi,yi)表示传感节点si与覆盖空洞区域交叉点的位置坐标；(xp,yp)为最远的交叉点位置坐标，如图2(b)所示。

图2 交叉点及移动距离示意图

2.2 覆盖冗余

由两个或两个以上的节点同时覆盖的区域称为覆盖冗余。节点覆盖冗余等于覆盖重叠区域与整个覆盖区域面积之比。节点的覆盖冗余是用来测量节点的感测区域的利用率。冗余率越高，节点利用率越低。

为了计算节点的覆盖冗余，首先得计算节点与其邻居节点的覆盖重叠区域。为了寻找重叠区域，先计算每两个交叉圆重叠区域Atwo。

假定两个圆，半径分别为r1、r2，并且这两个圆中心的相距距离为d，则这两个圆的重叠区域为Atwo[8]：

(2)

然而，在实际环境中，可能有三个圆共同重叠，即三个邻居同时覆盖同一区域。因此，必须要计算三个节点共同覆盖的区域Athree。假定三个圆(C1,C2,C3)，且三个圆的半径相同(节点感测半径相同)。这三个圆发生共同重叠有二种情况，如图3所示。

图3 三个圆发生共同重叠的情况

图3(a)描述了三个圆共同重叠的区域为两个圆的重叠区域，而图3(b)的共同重叠区域为三角形区域。要区分这两种,首先，寻找任意一对圆的交叉点，然后，每一对圆，检测交叉点是否位于第三圆内。如果没有位于第三个圆内，就属于图3(b)情况。如果全部落在第三个圆内，则属于图3(a)情况。

如图4所示，三个圆所形成的覆盖区域可近似为三角形。因此，可利用三角形计算理论，估计覆盖区域。依据Heron公式，可计算三角形Atriangle为：

(3)

式(3)中，s=0.5(a+b+c)，而a、b、c分别为三个交叉点的相互距离。

图4 三角形覆盖区域

因此，三个圆的共同覆盖区域Athree可表示为：

(4)

算法1总结计算冗余区域的过程，其中C1、C2和C3分别表示三个圆。首先，计算交叉点，然后，再判断这些交叉点是否落在第三个圆内。最后，再通过式(2)和式(4)计算冗余区域。算法1的伪代码如图5所示。

利用式(4)和式(2)，可计算覆盖冗余R，其等于任意两个圆的重叠面积与由三个圆的重叠面积之差，与节点的感测面积之比，即：

(5)

图5 算法1的伪代码

2.3 修复节点的选择

本小节分析选择修复节点的具体过程。先定义权值ρ，其定义为：

(6)

式(6)中，E为节点的剩余能量。

每个节点计算权值ρ，将自己的ρ值传输至邻居节点。具有最大ρ值的节点作为修复节点。从式(6)可知，R越大，即冗余率越大的节点，成为修复节点的概率也越大。将冗余率大的节点选为修复节点，这使得此节点移动后，不会形成新的覆盖空洞。

此外，尽可能地选择剩余能量大的节点作为修复节点，避免了因移动而导致能量过早耗尽。同时，选择移动距离d小的节点作为修复节点，这利于减少因移动而产生的能耗。

整个过程如图6所示。先获取失效节点sidle坐标和邻居节点集。再计算相关的交叉点，并将交叉点传输至邻居节点。随后，再从邻居节点收集交叉点信息，并依据这些信息确认空洞区域。

依据式(1)计算移动距离d，如图6的Step3。并依据式(6)计算式权值ρ，如图6的Step6。再将此值传输至邻居节点。再从邻居节点中选择具有最大ρ值的节点作为修复节点s′，并由s′移动距离d后到达目标位置，如Step7。

图6 算法2的伪代码

3 性能分析

3.1 仿真平台

利用MATLAB R2105a建立仿真平台，且90个传感节点随机分布于300 m×300 m方形区域。假定这些传感节点的感测半径rs=25 m、通信半径rc=50 m。传感节点的初始能量不同，能量在1～100 J范围内随机设定。此外，节点每移动1 m消耗1 J。

为了更好地分析MNCHR算法的性能，选择基于最小懒惰距离(Minimum Distance Lazy,MDL)[10]算法、基于自模糊逻辑空洞覆盖 (Fuzzy-based self-healing coverage,FSHC)[11]算法以及Center[12]算法作为参照，并与算法MNCHR进行比较。MDL算法通过节点的移动距离指标选择修复节点，并完成覆盖空洞。而FSHC算法利用模糊逻辑系统选择修复节点。这些算法都是以修复空洞区域为目的，但采用的策略不同。

同时，选择覆盖率、总移动距离以及能量消耗作为性能指标。每次实验独立重复20次，取平均值作为最终仿真数据。

3.2 仿真结果

3.2.1覆盖率

首先考查覆盖率随网络内失效节点数的变化情况，实验数据如图7所示。此外，图7也绘制了静态节点环境下的覆盖率，即节点失效后，节点不移动，即对覆盖不进行修复。

图7 覆盖率

从图7可知，MDL算法的覆盖率逼近于静态节点环境，原因在于：MDL算法对节点移动有严格的限制。而FSHC算法的覆盖率略好于MDL算法，但其覆盖率仍较低，这主要是因为FSHC算法只是让节点随机移动去修复覆盖空洞。与MDL、FSHC算法相比，MNCHR算法的覆盖率得到有效地提高，这在于MNCHR算法充分利用节点能量信息以及移动距离，选择最合适的修复节点，使得修复节点在修复空洞时，不影响原有的覆盖区域，即不会出现“拆东墙，补西墙”的现象。

3.2.2移动距离

图8显示了各算法的在修复覆盖空洞时所移动的距离。显然，移动的距离越短，越利于保存能量，但是短的移动距离可能也意味着空洞修复的质量越差。因为移动的距离反映了能耗与覆盖增益间的折衷。

图8 移动距离随失效节点的变化情况

从图8可知，MDL移动的距离最少，原因在于：MDL算法是通过移动最少距离来保存节点能量。而MNCHR算法和FSHC算法所移动的所有距离相近，但MNCHR算法保持较好的覆盖率。当一个节点失效，MNCHR算法就移动距离，致使能通过移动此距离来弥补因节点移动而产生的覆盖空洞。与Center算法相比，MNCHR算法移动得少、保存了更多的能量，修复了更多的覆盖空洞。

3.2.3能量消耗及修复的空洞区域

图9显示了各算法的能耗。从图9可知，MNCHR算法允许节点快速移动，因此，MNCHR算法比MDL算法消耗了更多的能量。而图10显示能量消耗更多用于修复覆盖空洞。MDL算法最多修复了10%的空洞区域，FSHC算法修复了50%，而MNCHR算法几乎修复了70%的空洞区域。

图9 能耗

图9和图10的实验数据表明：MDL算法的严格能量限制导致低的覆盖空洞修复，而MNCHR算法和FSHC算法在修复空洞时消耗了更多能量。换而言之，它们是以能量为代价，满足覆盖率的要求。

图10 修复的空洞率

4 结论

针对无线传感网络内因节点失效而引用的覆盖空洞问题，提出了基于节点移动的覆盖空洞修复算法MNCHR。MNCHR算法利用失效节点的一跳邻居节点信息，并利用这些节点的剩余能量、覆盖冗余以及移动距离选择最优的修复节点。通过修复节点的移动，实现对覆盖空洞的修复。

仿真数据表明，提出的MNCHR算法能够有效地修复空洞区域。然而，相比于同类算法，尽管在修复空洞区域方面有较大的提高，但是其是以消耗更多能量为代价的。后期，将优化算法，降低能耗。