基于Delaunay三角划分策略的WSN区域覆盖优化研究*

张 晶，魏 淼

(1.昆明理工大学信息工程与自动化学院，云南 昆明 650500;2.云南枭润科技服务有限公司，云南 昆明 650500;3.昆明理工大学云南省人工智能重点实验室，云南 昆明 650500;4.昆明理工大学云南省计算机技术应用重点实验室，云南 昆明 650500)

1 引言

近年来无线传感器网络WSN(Wireless Sensor Network)在各个专业领域的应用之中都有良好的表现，而构建一个完备的无线传感器网络的首要问题便是如何对传感器节点进行部署。由于在如山林、荒漠、高楼等具有特殊性的环境之中对传感器网络进行部署时，人工部署节点的工作具有很大的难度，而传感器节点在通过飞行器抛洒的过程中，由于环境和抛洒方式的影响必然无法一次性将节点布署在合适的位置，从而在监测区域中产生覆盖漏洞[1]。所以，如何通过无线传感器网络中的移动节点对在监测区域内存在的大量覆盖漏洞进行修补，以提高监测区域的覆盖率，是当下无线传感器网络的相关研究领域亟需解决的一大问题。

无线传感器网络的覆盖问题根据监测效果的不同，可以分为点覆盖问题、区域覆盖问题和栅栏覆盖问题[2]。目前针对无线传感器网络在平面区域的覆盖优化问题，国内外的学者进行了大量的研究，且取得了优越的成果。近些年来计算几何学在区域覆盖优化问题上得到了很好的应用。文献[3]提出了一种基于泰森多边形形心的部署策略，虽然在一定程度上降低了算法的复杂度，但是在最终的覆盖效果方面还可以进一步提高。方伟等人[4]提出了一种基于Voronoi图的WSN覆盖部署策略，通过Voronoi图对监测区域内的节点进行划分得到泰森多边形，从而进一步分析得出覆盖漏洞，再通过传感器网络动态节点移动到盲区多边形形心位置的方式来达到提高覆盖率的目的。但是，该部署策略计算较为复杂，算法复杂度较高。虽然计算几何学在区域覆盖优化上应用甚广，但是由于计算复杂，绝大多数研究都是在节点的布尔感知模型下进行的，这就造成了优化结果的理想化。而群优化智能算法在覆盖优化问题中的应用，虽然避免了复杂的几何推导及计算，如基于粒子群优化PSO(Particle Swarm Optimization)算法的覆盖优化方法或者基于人工蜂群算法的覆盖优化方法，但是群优化智能算法往往存在种群粒子难以跳出局部最优、算法收敛速度欠佳等缺点[5]。如文献[6]提出了一种基于灰狼算法的覆盖优化方案，虽然提高了覆盖率，但较之其他算法仍有不足；文献[7]提出了一种改进蚁狮算法的WSN覆盖优化方案，能够极大程度提高无线传感器网络的性能，但其收敛速度还有进一步优化的空间。

本文针对无线传感器网络在对初次抛洒节点形成的覆盖漏洞进行二次部署的过程中，传统的计算几何学方法难以应用于概率感知模型的问题，提出概率感知模型下监测区域内节点完全未覆盖区域的概念，首先对监测区域内随机抛洒的静态节点进行Delaunay三角划分，以得到静态节点三角网；并通过三角网边缘顶点构建监测区域内完整的三角网，证明三角形内部存在完全未覆盖区域，并将求取的三角形形心集合作为粒子群优化算法的初始解集；最后通过个体搜索能力增强的改进粒子群优化算法完成无线传感器网络的覆盖优化。通过仿真实验与其他算法进行对比，本文所提出的基于Delaunay三角划分结合粒子群优化算法的区域覆盖优化算法——DPSO(Delaunay triangulation improved Particle Swarm Optimization)算法具有更好的收敛速度，并且能够修复无线传感器网络初次抛洒产生的漏洞，使区域覆盖率得到显著提高。

2 传感器覆盖模型

2.1 概率感知模型

由于无线传感器网络对环境的监测是需要通过每个节点之间的合作共同完成的，故而研究无线传感器的覆盖就需要先建立单个传感器节点的感知模型。在近些年对无线传感器网络覆盖优化的研究中，国内外的大多数学者使用布尔感知模型来表示单个节点的感知能力。在该模型中，在传感器节点感知半径范围内的区域可以被节点准确地感知，即感知概率为1；而在感知半径距离外的区域皆不可被此节点所感知，即感知概率为0。布尔模型忽略了周围环境以及信号随距离衰减等因素的影响，因具有模型简单、易于实验等特性而被广泛地应用。但是，在传感器网络的实际监测过程中，传感器节点的感知概率通常会受到环境、信号传输距离等因素的影响。基于此，研究人员进一步提出了一种概率感知模型，该模型可以有效地反映出传感器节点的感知能力随感知距离变化的特性[8]。

记监测区域中所有的无线传感器节点为(S1,S2,…Si,…,SN)，所有的目标监测点为(T1,T2,…Tj,…,TM)，则传感器节点Si对目标监测点Tj的感知概率模型如式(1)所示：

(1)

其中，P(Si,Tj)表示网络中任一节点Si可以感知到目标Tj的概率，d(Si,Tj)表示节点Si到Tj的距离，RSi表示节点Si可以感知目标点的最远距离，r表示在此距离内目标可以被该传感器节点完全感知，α=d(Si,Tj)-r，λ和β是用来表示单个传感器节点感知能力的可调参数值，使用DSi表示传感器节点Si的通信半径并且有DSi≥2RSi。

2.2 区域覆盖率

假设被监测区域为一个m×n的二维方形区域，目标监测点的个数为M，无线传感器节点个数为N。

在传感器网络需要监测的区域内的目标点Tj可能会位于多个节点感知范围所交叉的区域，则该目标监测点Tj的联合感知概率如式(2)所示：

(2)

无线传感器网络对需要监测的区域的覆盖率通过传感器网络内所有节点可以有效监测到的范围与该区域的面积之比表示，则区域覆盖率Pcov可表示如式(3)所示：

(3)

3 相关算法

3.1 基本粒子群优化算法

基本粒子群优化算法PSO属于智能优化算法的一种，该算法的核心思想是模仿自然界中禽类寻找食物的行为，在解决传感器网络覆盖优化的问题时，先从随机产生的解集出发，通过粒子不断对自身位置进行更新，指导传感器网络中的动态节点移动，经过多次迭代最终寻找到可以使传感器网络覆盖率得以提高的解。粒子群优化算法因其参数少、便于实现的特性而被广泛应用，但是其依然存在易收敛于局部最优等缺陷[9]。PSO算法流程如下所示：

Step1初始化算法的相关参数。

Step2计算粒子的适应度值。

Step3更新个体和全局的最优解。

Step4若算法已经达到所设置的最大迭代次数，则停止迭代，算法结束；否则根据式(4)和式(5)计算更新粒子下一时刻的速度和位置，并跳回到Step 2计算新一轮的适应度值并继续执行，直到算法达到所设置的最大迭代次数。

根据上述算法流程，在迭代过程中粒子需要对自身的位置与速度进行不断更新，粒子每次对速度与位置更新的公式如式(4)和式(5)所示：

(4)

(5)

3.2 人工蜂群算法

人工蜂群ABC(Artificial Bee Colony)算法模仿自然界中蜜蜂的采蜜行为[10]，蜂群中包含的采蜜蜂、观察蜂和侦查蜂会根据从蜂群获得的信息进行自身位置的移动，从而达到寻找最大蜜量蜜源的目的。

在基本的人工蜂群算法中，采蜜蜂通过蜜源信息来更新自身位置，以寻找新的蜜源。蜂群中第i个采蜜蜂位置更新的依据如式(6)所示[11]：

x′i=xi+φi(xi-xk)

(6)

其中，xi和x′i分别表示旧的蜜源和采蜜蜂所寻找的新蜜源的位置，φi表示在[-1,1] 内的随机数，k≠i。算法将新找到的蜜源x′i与旧蜜源xi作比较，并采取贪婪策略的思想保留较好的蜜源。

4 DPSO算法

4.1 Delaunay三角形形心确定初始解集

4.1.1 区域Delaunay三角形划分

由于本文采用的传感器节点概率感知模型具有感知能力随距离减弱，超出最大感知半径则不能感知的特性，故而本文提出一种监测区域内绝对未覆盖区域的概念。

定义1若监测区域内存在某一块区域不能被任何传感器节点所感知，即在所有节点的最大感知半径之外，则称此区域为传感器网络的绝对未覆盖区域。

Delaunay三角划分是一种特殊的离散点三角网的构成方法，由俄国的数学家Delaunay提出[12]。其特征包括：以最接近的3个顶点连接形成三角形，所构成的三角网的边缘必然为一个凸多边形。

对监测区域内的所有传感器节点进行Delaunay三角划分并构建三角网，通过对比各传感器节点与监测区域边界之间所构建成的三角形的边长与节点覆盖半径的大小，可以判断三角形内部是否存在绝对未覆盖区域。

对区域内所有的点进行Delaunay三角划分，可以得到如图1所示的三角网。

Figure 1 Delaunay triangulation of nodes图1 节点的Delaunay三角网

除此之外，Delaunay三角网的边缘与监测区域边界之间也存在大量的未覆盖区域，本文将对此边缘区域进行进一步划分。

首先获取所有位于Delaunay三角网边缘的传感器节点，并与监测区域的边界构成新的多边形，然后对此多边形进一步进行Delaunay三角划分，从而完成整个监测区域内的三角划分。

判断被划分的多边形是否全为凸多边形，若存在非凸多边形，则使用Delaunay三角划分对该多边形进行进一步剖分，直到监测区域被完全划分成Delaunay三角形。经过本文上述划分过程的监测区域如图2所示。

Figure 2 Regional Delaunay triangulation图2 区域Delaunay三角划分

4.1.2 根据Delaunay三角形判断绝对无覆盖区域

本文通过Delaunay三角形的最长边与节点的最大感知半径的长度关系，证明三角形内出现绝对未覆盖区域的规律如下所示：

假设传感器节点A,B,C拥有完全相同的属性，记以此3个节点为顶点所构成的三角形为ΔABC，用R表示3个节点的最大感知半径，用d(,)表示2个传感器节点之间的距离。则经过Delaunay三角划分的三角形与绝对未覆盖区域有以下关系：

(1)如图3a所示，当三角形的3条边长皆小于传感器节点最大感知半径的2倍，即max(d(A,B),d(A,C),d(B,C))<2R时，三角形内部必然不存在完全未覆盖区域。

(2)如图3b所示，当三角形中的最大边长恰好与节点最大感知半径的2倍相等，即max(d(A,B),d(A,C),d(B,C))=2R时，当且仅当此三角形为锐角三角形时，三角形内部出现绝对未覆盖区域且完全位于三角形内部。

(3)如图3c所示，当三角形的最大边长超过节点最大感知半径的2倍，即max(d(A,B),d(A,C),d(B,C))>2R时，若此三角形为锐角三角形或直角三角形，则三角形内部必然存在完全未覆盖区域，若此三角形为钝角三角形，若点C到AB的垂直距离大于传感器最大感知半径，则三角形内部出现绝对未覆盖区域。

Figure 3 Relationship between Delaunay triangle and absolutely uncovered area图3 Delaunay三角形与绝对未覆盖区域关系

4.1.3 确定Delaunay三角形形心

根据4.1.2节可知，传感器节点感知的绝对未覆盖区域出现在三角形的内部，故可以求出已经剖分完毕的Delaunay三角形的形心位置，并从三角形的形心集合中产生PSO算法的初始解集，迅速定位出粒子在整个目标区域寻优的大概位置，有利于全局寻优并加快算法的收敛速度。

将一个由节点A、B、C所构成的三角形的顶点坐标按照顺时针的方向记为(X1,Y1),(X2,Y2),(X3,Y3)，将此三角形的形心坐标记为(Cx,Cy)，则形心计算公式如式(7)和式(8)所示：

(7)

(8)

4.2 改进粒子群优化算法

在基本粒子群优化算法及其相关的改进算法中，通常用以评价算法性能的准则是种群和粒子的搜索能力，而两者则主要通过算法的收敛速度和解的准确程度来评价。然而，由于PSO算法缺乏严密的数学推导过程，尽管一些方法能够提高算法的全局探索能力，但是从单个粒子的角度出发，依然存在陷于局部最优的缺点。所以，本文从粒子局部探索能力的角度着手，设计一种方案以提高粒子个体的探索能力，从而达到加快算法收敛速度的目的[13]。

4.2.1 个体粒子搜索能力增强

考虑到无线传感器网络覆盖优化领域中使用粒子群优化算法容易陷入局部最优的缺陷，本文结合人工蜂群算法的采蜜蜂行为设计一种增强单个粒子寻优能力的改进粒子群优化算法。其主要思想如下所示：

使用传感器网络区域覆盖率的求解公式作为算法的适应度函数，算法每次迭代粒子产生新的速度和位置后选取当前适应度值最优的粒子随机产生若干个虚拟粒子，并模仿人工蜂群算法蜜蜂的行为模式按照式(6)向随机方向进行试探性搜索并更新自己的位置，若所产生的若干个虚拟粒子中的某个粒子试探性搜索得到的结果优于当前粒子，则用该虚拟粒子代替当前粒子。

从式(6)中可以看出，由于φi的取值介于[-1,1]，从而可以使虚拟粒子的移动方向更具有随机性，粒子的搜索能力得到提高并且免于陷入局部最优。而本文在算法的每次迭代过程中只选取了当前适应度值最优的粒子产生虚拟粒子，从而避免了大量计算。

4.2.2 改进粒子群优化算法流程

本文所提出的改进PSO算法流程如下所示：

Step1初始化算法的相关参数。

Step2计算粒子的适应度值。

Step3选取当前适应度值最优的粒子，并随机产生若干个虚拟粒子，按照3.3节式(6)更新每个虚拟粒子的位置，并与当前粒子对比，若某个虚拟粒子的适应度值更优，则由此虚拟粒子代替当前粒子。

Step4更新个体和全局的最优解。

Step5若算法已经达到所设置的最大迭代次数，则停止迭代，算法结束；否则根据式(4)和式(5)计算更新粒子下一时刻的速度和位置，并跳回到Step 2继续执行，直到迭代结束。

Figure 4 Comparison of convergence between two algorithms图4 2种算法收敛性对比

通过图4可以看出，经过不同的迭代次数，标准PSO算法和本文所提出的改进PSO算法都能够达到Sphere函数的最小函数值0，但相较于标准的PSO算法迭代40次，本文所提出的改进PSO算法在迭代12次之后，粒子群收敛于最优值0，拥有更好的收敛速度。

4.3 DPSO算法流程

DPSO算法具体执行过程描述如下：

Step1无线传感器网络节点在监测区域内随机部署，获取所有节点的坐标值并根据2.2节中的式(3)计算出初始覆盖率。

Step2根据静态节点坐标，使用Delaunay三角网进行划分，再将划分完的Delaunay三角网与传感器网络区域边界作进一步的Delaunay三角划分，构建完整的监测区域Delaunay三角网。

Step3根据4.1.2节选取所有存在绝对未覆盖区域的三角形，并根据式(7)和式(8)计算三角形的形心位置。

Step4对算法中的相关参数进行初始化，其中种群的初始位置从三角形的形心位置集合中选取产生。

Step5计算粒子的适应度值。

Step6选取适应度值最优的粒子，产生5个虚拟粒子，按照3.3节的式(6)更新每个虚拟粒子的位置，并与原粒子对比，若其中某个虚拟粒子的适应度值更优，则用此虚拟粒子代替原粒子。

Step7更新个体和全局的最优解。

Step8若算法达到最大迭代次数，则停止迭代，算法结束；否则根据3.2节中式(4)和式(5)计算更新粒子的速度和位置，并跳回Step 5继续执行，直到迭代次数达到初始设置的迭代最大值。

Step9输出最优的动态节点移动位置，计算当前的覆盖率并生成监测区域的覆盖图。

本文算法的流程图如图5所示。

Figure 5 Flow chart of DPSO图5 DPSO算法流程

5 仿真实验

5.1 相关参数

假设实验过程中需要监测的区域面积为100 m×100 m。实验中计算网络覆盖率所使用的概率感知模型的相关参数为：RAi=10 m，r=6 m，λ=β=0.5。

在实验过程中，本文直接采用区域覆盖率的计算公式作为算法的适应度函数，如式(9)所示：

(9)

5.2 实验及结果分析

本文以Matlab 2016a为实验环境对无线传感器网络覆盖优化问题的求解方法进行了仿真，其相关参数设置如5.1节所述。

首先取50个传感器节点，其中静态节点30个，动态节点20个。通过初始的随机部署所形成的覆盖效果如图6所示，其中浅色代表静态节点，深色代表动态节点。通过计算可以得出监测区域内网络的初始覆盖率为58.18%。经过DPSO算法优化后，监测区域内的节点分布如图7所示，可以看出，动态节点较好地移动到了网络的绝对未覆盖区域，并且覆盖均匀，经过计算，覆盖率达到74.47%，本文提出的DPSO算法达到了很好的优化效果。

Figure 6 Initial node deployment of WSN图6 传感器网络初始节点部署

Figure 7 Node deployment after DPSO algorithm optimization图7 DPSO算法优化后的节点部署

为了进一步分析DPSO算法的性能和覆盖效果，本文选取了基本PSO算法和标准ABC算法与DPSO算法通过10次蒙特卡罗实验进行对比。图8是单次实验中使用PSO、ABC、DPSO算法对监测区域进行覆盖优化的过程对比。从图8中可以看出，相比于PSO算法和ABC算法，本文所提出的DPSO算法能够最快收敛，并且在迭代80次之后覆盖率迅速提高。这归功于对区域的Delaunay三角划分能够迅速锁定传感器网络的绝对未覆盖区域，并且在算法过程中产生的虚拟粒子同样加快了DPSO算法的收敛速度，使得算法在迭代306次之后收敛且传感器网络最终的覆盖率达到了74.47%。

Figure 8 Comparison of coverage among three algorithms图8 3种算法覆盖率对比

通过10次蒙特卡罗实验对比，从表1中可以看出，DPSO算法优化得到的结果稳定，10次实验覆盖率的平均值可达75%以上，且覆盖率相比于PSO和ABC分别提高了14.59%和4.13%，优化效果优于PSO算法和ABC算法。

除此之外，本文还在静态节点数为30，动态节点数不同的情况下对算法进行了对比。从图9中可以看出，当动态节点数为10时，PSO算法的覆盖率为55.71%,DPSO算法的覆盖率为61.21%；当动态节点数为20时，PSO算法的覆盖率为62.59%,而DPSO算法的覆盖率迅速上升到77.48%；当动态节点数为30时，PSO算法的覆盖率为73.68%，而DPSO算法的覆盖率为84.59%；当动态节点数为40时，PSO算法的覆盖率为77.98%，而DPSO算法的覆盖率超过90%达到90.64%；当动态节点数为50时，PSO算法的覆盖率为83.35%,DPSO算法的覆盖率为94.37%。由此可知，当动态节点的数目小于50时，相比于PSO算法，本文的DPSO算法拥有明显较好的优化效果；而当动态节点数目超过50时，算法之间的差异开始减小，覆盖率皆可以达到85%以上。

Figure 9 Comparison of algorithm coverage with different dynamic node numbers图9 动态节点数不同时算法覆盖率对比

6 结束语

在无线传感器网络的区域覆盖优化问题中，本文提出了一种基于Delaunay三角划分策略的区域覆盖优化算法DPSO，解决了常规的计算几何学难以应用于概率感知模型的问题。仿真实验分析表明，本文提出的DPSO算法能够快速定位传感器网络初始部署所存在的绝对未覆盖区域，能够修复区域中存在的漏洞使覆盖率得以有效提高的同时保持节点间的良好通信。算法产生的虚拟粒子有效地加快了算法收敛速度，并且使得算法具有良好的稳定性。但是，本文所提出的区域覆盖优化算法目前仅可以运用于二维平面的场景，其使用范围具有局限性。下一步将致力于研究算法在三维空间内区域覆盖优化的运用，使其拥有更多的应用场景。

Table 1 Experiment results of different algorithms表1 不同算法实验结果对比 %