混合无线传感器网络覆盖优化算法*

张 军， 邵晓倩， 侯向丹

(1.河北工业大学 计算机科学与软件学院, 天津 300401；2.河北省大数据计算重点实验室，天津 300401)

0 引 言

混合无线网络可以有效利用移动节点的动态部署弥补固定节点所形成的信号覆盖盲区，从而与仅有固定节点组成的传感器网络[1]相比能更好地解决网络资源浪费、易出现覆盖盲区等问题。文献[2]将遗传算法引入混合无线传感器网络中。文献[3]应用改进的蜂群算法对无线传感器网络进行部署优化，将传感器感知节点部署问题转化为组合优化问题。但2种方法收敛效果不是很明显。文献[4]提出了将反向学习策略方法加入基本的人工蜂群(artificial bee colony,ABC)算法中，其改进的ABC(improved ABC,IABC)算法收敛效果非常好，但网络覆盖效果不是很满意。文献[5]提出一种基于Voronoi多边形和ABC算法相结合的新型混合优化算法(Voronoi-ABC,VABC)，应用VABC来部署节点，收敛速度很好，目标区域覆盖率效果明显，但跟随蜂产生新食物源的时，依赖本代的最坏食物源的可能性比较大，不利于获得最优的结果。

本文利用Voronoi多边形来确定固定节点的覆盖盲区作为指引移动节点的移动参数。利用蜂群算法对移动节点进行分析，确定最佳移动节点及移动位置。应用反向学习策略加快算法的收敛速度的同时避免算法陷入局部最优。确定移动节点的最终位置，达到覆盖率最优。

1 基于IVABC的覆盖优化策略

针对传统的蜂群算法中的轮盘赌方式会使种群多样性被降低，从而引发收敛速度慢、易陷入局部最优解的缺点[6]，本文提出了将Voronoi多边形和反向学习算法结合到人工蜂群算法里来解决覆盖优化问题。

1.1 引领蜂的产生

在ABC中，食物源的产生是随机的，同时引领蜂的搜索过程也是随机的。将Voronoi多边形引入ABC算法中，应用Voronoi多边形顶点找出固定节点的覆盖盲区位置,并且将覆盖盲区作为产生新蜜源的移动位置。与此同时，指导引领蜂的搜索位置，快速锁定蜜源在整个目标区域的大致位置，并且计算食物源的适应度值。同时引领蜂更新食物源位置。

1.2 跟随蜂选择策略

通过Voronoi多边形加入蜂群算法中，跟随蜂通过距离评价覆盖盲区的大小来选取引领蜂进行跟随。评价覆盖盲区大小策略如下：

1)如果顶点VA,VB完全被节点s的覆盖圆所覆盖，则不存在覆盖盲区；

2)如果顶点VA,VB中的两个点有一个落在节点s的覆盖圆内，另一个落在覆盖圆外，假设顶点VA落在覆盖圆内，而顶点VB落在覆盖圆外,必然出现覆盖盲区。利用Voronoi多边形将顶点VB做出标记，此时顶点VB为覆盖盲区，顶点VA不进行标记。

1.3 最差蜜源替换

(1)

式中xijU为xi的第j个分量的上界，xijL为x的第j个分量的下界。本文更新最差食物源都采用式(1)得到新食物源，如果新食物源效果更好，则代替旧食物源。

1.4 IVABC的算法过程

1)目标区域内随机部署无线传感器网络的固定节点，对固定节点进行Voronoi划分;根据无线传感器固定节点的覆盖圆到Voronoi顶点之间的相对位置找到覆盖盲区,并计算初始覆盖率。

2)对蜜蜂种群规模、最大迭代次数等进行初始化处理。

4)计算网络覆盖率，同时应用贪婪算法寻找相对较好的解来更新当前移动节点位置。

5)有限次循环步骤(3)后，假如有移动节点位置不能提高网络覆盖率，则由对应的引领蜂转变为侦查蜂进行搜索，应用反向学习策略产生新移动节点位置取代原来的节点位置。

6)对最大循环次数进行判断，假如达到最大执行次数，循环停止；否则，根据网络覆盖率重新对蜂群进行搜索。

7)检验循环结束的条件是否得到满足：若是，就输出记录最优的移动节点位置作为寻优结果，最终生成的无线传感器网络覆盖图。

2 实验与结果分析

使用MATLAB 2014软件进行仿真，仿真目标区域为100 m×100 m，混合无线传感器总节点数为50个，其中固定节点30个，移动节点20个，通信距离20 m，感知半径10 m。在ABC和IVABC中，参数分别为：种群规模50，引领蜂数20，蜜源数20，最大迭代次数1 000次。实验中传感器部署选定监测区域为二维网络空间，所有传感器节点处于同一平面内，同构，具有相同的传感半径R。传感器节点感知模型为概率感知模型，每个传感器节点覆盖圆范围为πR2。

应用本文提出的IVABC算法的实验仿真结果中节点随机部署情况如图1、图2所示，图2中深色区域表示移动节点覆盖区域，浅色区域表示固定节点覆盖区域。由结果可知，初始网络覆盖率为67.81 %。图2算法优化后的，最终目标区域覆盖率为97.13 %，从而使覆盖率达到最大化。

图1 节点初始随机部署

图2 优化完成后节点最终部署

表1为10次仿真实验的覆盖率数据统计表。从表1中可以看出应用本文提出的IVABC算法后，混合无线网覆盖率每次均有很大的提升。图3为4种算法的平均覆盖率的寻优曲线。

表1 10次覆盖率仿真实验结果 %

图3 4种算法平均覆盖率对比

可见本文提出的IVABC算法收敛速度快，且收敛效果好。由表1中仿真10次的网络平均覆盖率数据比较，看出IVABC算法覆盖效果更好，平均最大覆盖率最后达到96.39 %。IVABC在迭代95次后，达到最大覆盖率的95 %，由此可见，收敛速度加快的同时，覆盖效果明显。

3 结束语

针对混合无线网覆盖优化问题和无线传感器节点的部署问题，本文提出一种IVABC算法，并通过与ABC,IABC,VABC算法在混合无线网络中的最终覆盖率、平均覆盖率和迭代次数等方面的对比，说明了IVABC算法能较好避免基本ABC易陷入局部最优解的同时减少了迭代次数。