王 军， 赵子君， 李国强

(沈阳化工大学 计算机科学与技术学院， 辽宁 沈阳 110142)

随着科学技术的发展和无线传感器网络的普及应用，无线传感器网络在生活中扮演着越来越重要的角色，特别是在海上监测、森林火灾等自然灾害方面，灾情信息的及时获取都给我们带来巨大便利[1].通过在监测区域内投放大量的无线传感器节点来获取实时信息，但是由于节点投放的随机性导致监测区域的覆盖不均匀，节点分布稀疏的区域就会产生覆盖漏洞，节点分布过于密集又会产生覆盖冗余.因此设计一种移动节点调度优化方案来提高覆盖质量至关重要[2].

目前，传统的无线传感器网络覆盖问题已经进行了很多研究.Penny等[3]使用改进的粒子群算法指导无线传感器网络的部署，在一定程度上提高了网络覆盖率，但算法容易陷入局部最优解.文献[4-5]使用人工蜂群(artificial bee colony，ABC)算法指导网络布局，但算法收敛速度慢，容易陷入局部最优.Lee 等[6]提出了基于泰森多边形形心的部署策略(Centroid-Based scheme，CBS)，一定程度上降低了算法复杂度，但网络覆盖效果不够理想.

由固定节点和移动节点共同组成的混合无线传感器网络随机部署在二维目标监测区域可以通过移动节点的位置调整，实现目标区域的优质覆盖[7].因此，对于传统人工蜂群算法的缺点，首先利用Delaunay图寻找覆盖漏洞，再把改进的人工蜂群算法(Delaunay artificial bee colony，D-ABC)对无线传感器网络(wireless sensor networks,WSNs)覆盖策略进行优化，提高了WSN的整体性能.

1 相关问题

1.1 人工蜂群算法

人工蜂群算法(ABC)是由D.Karaboga[8]于2005年提出的一种人工模拟蜜蜂觅食行为的启发式智能算法，其优点在于优化过程简单，控制参数少，易操作.但ABC算法也有启发式智能算法都有的缺点即过度的随机性：蜜源初始位置是随机的；侦查蜂随机探索新蜜源的位置.以上原因导致蜂群算法后期收敛速度慢，容易陷入局部极值和早熟[9].

1.2 Delaunay图

1.2.1 Delaunay图

Delaunay图即对于一组无线传感器固定节点，可以得到很多种不用的三角剖分，其中最优三角剖分就是Delaunay三角网[10].体现在其最重要的两个性质：唯一性，一组点无论如何构造都能得到同一个delaunay三角网；不相交性，delaunay三角网内各边都不相交.在此根据Delaunay三角网内每个三角形外接圆圆心的位置得到引领蜂的初始位置和个数.还要根据每个delaunay三角形的面积计算每个三角形内部需要部署的侦察蜂个数.

1.2.2 覆盖漏洞的估算方法

想要确定引领蜂和侦查蜂的位置和个数，首先需要找到Delaunay三角形的外接圆圆心，三角形的外接圆圆心到三角形三个顶点的距离相等，通过比较外接圆圆心到节点的距离与传感器节点通信半径的大小关系来判断三角形内是否存在覆盖漏洞.

本文研究的是由静态节点和移动节点组成的混合网络，由静态节点在每个三角形内计算覆盖空洞面积以及计算出移动节点的位置，然后命令移动节点修复覆盖漏洞.现在需要解决的问题是在每个三角型内判断是否存在覆盖空洞，计算覆盖空洞的面积和移动节点位置信息.

1.3 网络覆盖率

网络覆盖率指全部传感器节点覆盖的总面积占监测区域总面积的百分比[11].在此令So为传感器节点所覆盖的总面积，a×b为监测区域总面积，覆盖率为：

(1)

1.4 感知模型

1.4.1 二元感知模型

二元感知模型也称布尔感知模型，如果监测节点的感知范围覆盖了目标节点，监测概率为1；反之，监测节点的感知范围没有覆盖目标节点，监测概率则为0.这就是所谓的0-1感知模型，又称之为二元感知模型，最典型的例子当属圆盘感知模型[12]，如图1所示.节点o(xo,yo)的感知区域定义为节点o为圆心、以ro为半径的圆形区域Ro(o,ro)，则位于Ro(o,ro)内的任意点都能被o监测到.其中，ro也被称作o的感知半径，且节点的物理特性决定了ro的大小.设平面上任一目标点P(xp,yp)，节点o监测到点p处发生事件的概率表示为：

(2)

图1 二元感知模型

1.4.2 概率感知模型

概率感知模型是一种离散的理想模型，符合无线传感器网络的真实覆盖效果，即假定目标点是否被传感器节点监测到的情况是确定的，也就是监测到设为1，确定不覆盖设为0.概率感知模型存在一个“中间区域”，即在确定不覆盖和确定覆盖中间，如图2所示.而在实际应用场景中，节点的无线信号由于受到如障碍物、噪声等外界环境的干扰，概率感知模型反映出节点感知能力随着距离变化而变化的特征[13].

目标区域内任一目标点p被传感器节点o监测到的概率表示为:

(3)

图2 概率感知模型

2 基于D-ABC的覆盖优化策略

从蜂群算法的基本原理可知：算法中每个食物源与引领蜂的位置和数量一一对应，侦查蜂围绕引领蜂进行局部搜索.移动节点的个数等于引领蜂的个数与侦查蜂的个数之和.

2.1 Delaunay三角网覆盖漏洞的估算

根据讨论三角形外接圆圆心到节点距离与节点通信半径的大小关系来判断三角形内是否存在覆盖漏洞.首先求出外接圆圆心So=(Xo,Yo).

(4) 如果三角形的外接圆圆心So(Xo,Yo)到三角形任意一点的距离都小于节点的通信半径，那么三角形内不存在覆盖漏洞，反之一定存在覆盖漏洞.分为以下情况进行讨论：

1) 一定不存在覆盖漏洞

当d(Oi,So)≤Ro时，3个节点的通信半径覆盖的面积会两两相交，并且一定不存在覆盖漏洞，如图3所示.

图3 不存在覆盖漏洞

2) 存在覆盖漏洞情况

A：如果d(Oi,So)>Ro，即O1、O2、O3这3个节点每两个都不相交而且3个节点到外接圆圆心的距离都大于节点的通信半径，那么delaunay三角形内一定存在覆盖漏洞，如图4所示.可计算出覆盖漏洞的面积为三角形的面积减去3个扇形的面积之和：

(5)

图4 情况A:存在覆盖漏洞

B：如果d(Oi,So)>Ro，并且其中一个节点和另两个节点相交时，delaunay三角形将会形成钝角三角形，如图5所示.由图5可知：

(6)

那么若想求出S1需先求出两圆相交面积的一半，用扇形面积SO1C1C2减去三角形面积SΔO1C1C2，计算出d(O1,c)和三角形面积SΔO1C1C2：

(7)

两圆相交的面积SC1C2C2C1和S1为：

(8)

图5 情况B:存在覆盖漏洞

2.2 引领蜂的产生

在传统ABC算法中，蜜源初始位置是随机的，引领蜂的搜索过程也是随机的[14].D-ABC算法是根据固定节点的随机部署情况，生成固定节点对应的 Delaunay三角网，利用 Delaunay三角网找出固定节点覆盖漏洞，根据三角形面积确定是否生成蜜源，从而确定是否生成引领蜂；三角形的外接圆圆心的位置即蜜源位置，得到引领蜂的位置.

2.3 侦查蜂的改进

在传统ABC算法中，侦查蜂随机寻找蜜源，寻找蜜源的过程对应最优解的过程[15].D-ABC算法蜜源位置即引领蜂的位置，通过判断覆盖漏洞的大小，分配侦查蜂的数量.

2.4 矩形内创建delaunay三角网

由于delaunay三角网是一个凸多边形，不能完整覆盖整个监测区域，这里在矩形内建立delaunay三角网.如图6所示.

图6 矩形内的delaunay三角网

2.5 算法执行过程

算法具体步骤如下：

(1) 随机部署固定节点，并且根据固定节点部署情况生成对应的delaunay三角网.

(2) 通过计算每个delaunay三角形的覆盖漏洞面积，确定需要填充覆盖漏洞的delaunay三角形.

(3) 根据delaunay三角形外接圆圆心的数量，初始化引领蜂的数量.

(4) 根据delaunay三角形的面积，确定侦查蜂的数量.

(5) 根据引领蜂和侦察蜂的数量随机部署移动节点，计算无线传感器网络的初始覆盖率.

(6) 根据delaunay三角形外接圆圆心的位置，初始化引领蜂的位置.

(7) 侦查蜂进行delaunay三角形内部的局部搜索，计算有限次后，停止局部搜索.

(8) 记录移动节点的最终位置并且生成最终的网络覆盖图并计算网络覆盖率.

3 仿 真

建立100 m×100 m的正方形仿真区域，初始条件下随机放置40个固定节点.由固定节点构成的delaunay三角网计算得到需要的31个移动节点(20个引领蜂和11个侦查蜂).得到初始情况的随机部署，如图7所示.网络覆盖率为73.63 %.使用D-ABC算法后，网络覆盖率为95.71 %.如图8所示.

图7 初始部署状态

图8 优化后部署状态

为更好地体现D-ABC算法的性能，与其他的群智能算法进行对比.在Matlab中对蜂群算法(ABC)、混沌蜂群算法(CABC)、和D-ABC算法的网络覆盖率进行了对比，3种算法的迭代次数与网络覆盖率的折线图如图9所示，可以直观看出：ABC算法最终可达到的网络覆盖率为90.11 %，CABC算法可达到93.48 %，CABC算法相较于ABC算法收敛速度更快，网络覆盖率有明显提高[16]，D-ABC算法相较于CABC收敛速度更快并且网络覆盖率可达到95.71 %.

图9 ABC、CABC、D-ABC算法对比

4 结束语

覆盖问题是无线传感器网络中的基本问题.本文在传统的人工蜂群算法的基础上结合delaunay三角网算法提出D-ABC算法，用于解决无线传感器网络的节点覆盖不均匀，覆盖率低等问题.D-ABC算法能够快速估算覆盖漏洞的大小，并且提高网络覆盖效率，实现无线传感器网络的覆盖优化.本文目前解决了混合无线传感器网络覆盖中的区域覆盖问题，需要进一步研究栅栏覆盖问题，以及在此过程中的移动路径和节点能量消耗等问题，完成完整的无线传感器网络部署.