Voronoi图又称泰森图，是计算几何中的一种结构，已经证明能用来确定无线传感网络中的潜在覆盖洞位置，满足以下定义^[10]。

定义1  支配域：给定二维欧几里得空间R²中任意两点p和q，L是线段$\overline {pq} $垂直平分线，该空间被L划分成为两个部分L−left和L−right，显然，L−left中任意点r都满足$\left| {\overline {pr} } \right|＜\left| {\overline {qr} } \right|$，称L−left为p相对q的支配域，描述为H(p, q) [L-left]。反之亦然，即H(p, q)={x∈R²|d(x，p)＜d(x，q)}。

定义2   Voronoi多边形：给定n点集合S = {p₁, p₂, …, p_n}，定义S中所有的H p(p_i, p_j)的交集(j≠i)为点p_i的Voronoi多边形，即$V({p_i}) = \cap {p_j} \in S -\{ {p_i}\} H({p_i}, {p_j})$。

定义3   Voronoi图：集合S中所有点的Voronoi多边形的并集，称为集合S的Voronoi图。即$V(S) = \cup {p_i} \in SV({p_i})$。

图 1所示是一幅Voronoi图，图中的黑点表示传感器节点，节点周围形成的多边形叫做Voronoi多边形。由定义可知，Voronoi多边形内的任意一点都只与其包围内的节点距离最近。VOR算法则基于Voronoi图。VOR算法的优点在于通过构建Voronoi多边形可以快速找到潜在覆盖洞区域，并获得移动节点最佳移动位置；算法具有普适性，不受覆盖盲区形状的影响。其缺点在于：VOR算法采用的是纯移动节点网络覆盖监测区域，任意一个节点的移动都有可能造成新覆盖洞的出现，并影响其他节点的覆盖性能。并且移动节点的频繁移动本身会消耗大量的能量，缩短无线传感网络的寿命；算法对所有多边形顶点所在覆盖洞区域修复时没有区别对待，会出现当移动节点不足时，移动节点未能优先修补较大覆盖洞而削弱节点的修复功能^[11-12]。

图  1  传感网络泰森图展示

针对传统VOR算法存在的缺点，考虑现实的无线传感网络环境，本文改变单纯的移动传感器网络方式，使用复合式传感器网络，即首先部署静态节点，负责监测区域主要部分的覆盖，并通过构造Voronoi图来检测并指导移动节点修复覆盖洞。另外，当部署的移动节点数量少于潜在覆盖洞数量(实际情况多是如此)时，采用VORP算法来提高移动节点修复性能。

由于VOR算法未对Voronoi多边形顶点所在覆盖洞进行大小估计并采用优先覆盖策略，使得当Voronoi多边形顶点数过多而移动节点不足的情况下，无法最大限度地修复覆盖洞。本文所说的优先机制是指给予覆盖洞优先等级，大覆盖洞的需要优先进行修复，小的覆盖洞后修复或者不修复。本文提出的基于优先机制的VORP算法，在修复覆盖洞之前，先对覆盖洞大小进行定性比较，即比较泰森多边形顶点与周围节点的距离，越远则说明覆盖洞越大，得到覆盖洞修复位置的优先级，再调度有限的移动节点按照优先级进行覆盖洞修复，使覆盖效率达到最优。

VORP算法步骤如下：

1) 在随机布置静态节点后，构建Voronoi图，并获得每个多边形顶点位置的信息列表v。删除v中监测区域外的顶点信息；

2) 新建一个移动节点修复位置信息优先级列表list和临时信息列表temp；

3) 对v中的每一个顶点，若存在与它距离小于等于R_s(R_s为节点感知半径)的静态节点，则将它从v中删除，否则将d_i(d_i为该顶点和与之最近的静态节点之间的距离)以及顶点的位置信息添入list中；

4) 初始化临时信息列表temp；

5) 进行一次循环(循环次数为移动节点数目)遍历list，若${d_i} \ge 2{R_s}$说明该位置处于一个大覆盖洞中心，则更新temp中顶点d_i (置零)和位置信息，发送给移动节点指导其移动。list中删除该顶点相关信息，进行下一次循环；若${R_s}＜{d_i}＜2{R_s}$，则比较此顶点d_i和temp中d_i，若此顶点d_i大于temp中d_i，则将此顶点d_i和位置信息添入temp，将其更新。若list中顶点全部遍历，则将temp中顶点d_i和位置信息发送给移动节点指导其移动。list中删除该顶点相关信息。进行下一次循环。

考虑监测区域为10 m×10 m的正方形区域，该区域内部署着30个静态节点以及20个动态节点，节点的感知半径R_s为1 m，该通信半径条件下邻居节点可以互相交换信息，每一个圆的圆心代表一个节点的地理位置，圆形包围的区域为无线传感网络覆盖区域。本文在Matlab平台上对VORP算法进行了仿真。图 2为静态节点部署后的区域覆盖情况，图 3为运用一次VOR算法后的区域覆盖情况，图 4为运用一次VORP算法后的区域覆盖情况。

图  2  静态节点部署后的区域覆盖情况

图  3  基于VOR算法的区域覆盖情况

图  4  基于VORP算法的区域覆盖情况

经计算，图 2、图 3和图 4中区域的覆盖度分别为58.28%、75.33%和78.24%。经泰森图构造后，监测区域共存在25个潜在覆盖洞区域，远远大于可使用的移动节点。这些覆盖洞的大小各不相同，显然优先机制的引入让移动传感器优先修复较大覆盖盲区以更好地利用有限的传感器资源，优化覆盖洞修复性能。由图可见，VOR、VORP算法都具有不错的覆盖洞修复性能，而引入了优先机制的VORP算法性能更优。

上述VORP算法虽然能提高VOR算法在移动节点不足以覆盖所有潜在覆盖洞时的性能，将有限的移动节点部署到最大覆盖洞区域，然而仿真结果发现，该算法往往会出现以下情况：多个最佳覆盖Voronoi多边形的顶点位置互相粘连，彼此距离很近，当移动节点覆盖其中一个顶点之后，周围的覆盖洞也相应减小，使得其余部署在这个区域附近的移动节点不再位于最佳修复位置，也就削弱了VORP算法在部署移动节点上的优越性。图 5具体展示了该问题。因此，本文提出更进一步的改进算法VORCP，用于检测并改善以上问题。

图  5  VORP算法存在的缺陷

为检测和改善VORP算法存在的上述缺陷，VORCP算法设置了一个可容忍的最小粘连距离阈值threshold，若一个潜在覆盖洞修复位置与某个已修复的覆盖洞位置的距离小于threshold，则降低这个覆盖洞修复优先级至最低。

1) 在随机布置静态节点之后，构建Voronoi图，并获得每个多边形顶点位置信息列表v。删除v中监测区域外的顶点信息；

2) 新建一个移动节点修复位置信息优先级列表list和临时信息列表temp1、temp2以及一个计数标志c；

3) 对v中每一个顶点，若存在与它距离小于等于R_s的静态节点，则将它从v中删除；否则将d_i(d_i为该顶点和与之最近的静态节点之间的距离)以及顶点的位置信息添入list中；

4) 初始化临时信息列表temp1、temp2；

5) 进行一次循环(循环次数为移动节点数目)。遍历list，添加顶点d_i及位置信息到temp2中，计算该顶点与temp1中所有顶点的距离dv_i。若存在0＜dv_i(threshold为可容忍的最小粘连距离)，则将list中该顶点d_i更新为0，使c+1并初始化temp2；若dv_i ≥threshol且d_i≥2R_s，则跳出遍历，将temp2中顶点所有信息添至temp1中，指导移动节点向其移动，删除list中该顶点信息。若dv_i ≥threshol且${R_s}＜{d_i}＜2{R_s}$，则比较此顶点的d_i和temp2中的顶点d_i信息，若此顶点d_i大于temp2中的d_i，则将此顶点d_i和位置信息覆盖至temp2中，直到遍历结束，将temp2中顶点所有信息添至temp1中，指导移动节点向其移动，删除list中该顶点相关信息。若c等于list中剩余的节点数，则将list中所有顶点信息依次添入temp1中至所有移动节点都部署完成或list中顶点清空。

本文在Matlab平台上对VORCP算法进行了仿真。仿真场景同2.3节。图 6为静态节点部署后的区域覆盖情况，图 7为运用一次VORP算法后的区域覆盖情况，图 8为运用一次VORCP算法后的区域覆盖情况。threshold可以根据具体要求自行设置，本文中threshold设置为R_s/4(即0.25 m)。

图  6  静态节点部署后的区域覆盖情况

图  7  基于VORP算法的区域覆盖情况

图  8  基于VORCP算法的区域覆盖情况

从图 6~图 8可以看出两种算法对覆盖洞的修复情况。经计算，图 6中区域的覆盖度为61.72%，图 7中区域的覆盖度为86.38%，图 4中区域的覆盖度为88.26%。可见VORP、VORCP算法都具有不错的覆盖洞修复性能，且VORCP算法性能更优。

本文对VOR、VORP以及VORCP算法进行横向以及纵向的比较，以直观地验证后两种算法的优越性。在横向比较中，利用算法对同一片监测区域进行覆盖洞修复，通过对覆盖度的计算和分析得出结论；在纵向比较中，将给定工作要求下的最下限覆盖度水平，并分别使用3种算法进行节点部署，以得出算法各自达到要求所需的周期，进而分析算法效率。

图 9依次展示了运用修复算法前和分别运用VOR、VORP、VORCP算法后监测区域无线传感网络覆盖情况。仿真场景同2.3节，threshold设值为R_s/4(即0.25 m)。在静态节点部署完成之后，移动节点根据静态节点构造出泰森图，按照不同算法步骤选择覆盖洞进行修复。

图  9  算法横向比较

由计算可得，算法运用前无线传感网络对监测区域的覆盖度为59.81%；而运用VOR、VORP、VORCP算法之后无线传感网络对监测区域的覆盖度分别为67.95%、75.65%、77.83%。就一般性而言，3种算法的覆盖洞修复性能比较为VORCP > VORP > VOR。通过深入的仿真与分析发现，当检测出的覆盖洞数量与可使用的移动节点数量相差越大，VORP和VORCP算法比VOR算法的优越性越明显；局部覆盖洞越密集，VORCP对VORP算法的优越性越明显。

本文设计的算法可以对监测区域的覆盖洞进行多次修复。在现实情况下，进行一次移动节点部署来提高无线传感网络的覆盖度往往是不够的。为了达到应用所要求的覆盖度，需要进行二次或者多次部署，最终使监测区域的覆盖度达到可容忍的要求。

因此，本文对各个算法的覆盖洞修复效率进行比较。仿真环境中监测区域为12 m×12 m的正方形区域，初始静态节点为40个，每使用一次覆盖洞修复算法，将添加10个移动节点以提高区域覆盖度。所有节点的感知半径依旧为1 m，保持通信半径满足邻居节点互相交换信息的要求。假设某应用要求的覆盖度下限为90.0%，分别使用VOR、VORP、VORCP算法来提高无线传感器网络对监测区域的覆盖度，使其达到该应用所要求的覆盖度下限。通过观察分析覆盖度提高的情况以及比较算法使用的轮数来验证哪种算法的效率最高。表 1展示了3种覆盖洞修复算法达到所需覆盖度时经过的轮数以及每一轮之后无线传感网络的覆盖度大小。图 10更为直观地显示了覆盖度提高的情况。可以看出，VORCP算法在第四轮算法结束后已经达到了覆盖度要求，而VOR及VORP算法则进行了6轮算法修复才达到应有的覆盖度水平。由此可见，VORCP算法在效率和性能方面均优于前两种算法。值得一提的是，VORP算法在覆盖洞较大的时候修复效果优于VOR算法，但从长期的算法效率看并没有优势。因为当具有大覆盖洞时，采用优先机制能够很明显地先对它们进行修复，从而显著提高覆盖度；然而在覆盖度逐渐提高时，大覆盖洞区域逐渐减少，而移动节点修复覆盖洞时的粘连状况更容易发生，并成为影响其性能的主要因素，算法性能和效率都开始下降，甚至最后差于VOR算法。

图  10  算法纵向比较

覆盖是传感器网络中的一个基本问题，覆盖度是衡量无线传感网络工作性能好坏的重要指标，覆盖洞的出现将影响该参数。

本文在混合传感网络下基于传统的覆盖洞修复算法VOR，针对其存在的不足，提出两种改进的覆盖洞修复算法：基于优先机制的VORP算法和基于复杂优先机制的VORCP算法。通过对两种改进算法的仿真与分析以及对运用修复算法前和分别运用VOR、VORP、VORCP算法后监测区域无线传感网络覆盖的纵向和横向的比较分析，表明本文所提出的改进算法在性能和效率上优于传统的覆盖洞修复算法。在后续的研究工作中，将对基于复杂优先机制的覆盖洞修复算法的复杂度进行进一步的研究，以更好的提高其性能。