李华+卢静

摘 要： 由于无线传感器网络覆盖属于组合优化范畴，为了在有限节点数量情况下提高其覆盖率，引入人工蜂群算法并进行改进。通过注入全局最优个体反馈来提高收敛速度，并升级了侦查蜂更新方法，采用一维高斯变异的方法，充分利用粒子先验知识，使粒子既能够保证足够的活力，又提高了算法的全局搜索能力。在40个节点数量条件下进行仿真实验，提出的改进算法覆盖率达到了87.2%，与改进蛙跳算法和标准人工蜂群算法的覆盖率相比分别提高了1.6%和3.87%。

关键词： 无线传感器网络； 人工蜂群； 全局最优； 一维高斯变异； 概率测量模型； 覆盖优化

中图分类号： TN711?34； TP393.04 文献标识码： A 文章编号： 1004?373X（2018）03?0014?05

Abstract： Since the wireless sensor networks coverage belongs to the combinatorial optimization category， the artificial bee colony algorithm is introduced and perfected to improve the coverage rate in the condition of limited node quantity. The global optimal individual feedback is injected to improve the convergence rate， and update the refresh method of investigation bee. The one?dimensional Gaussian mutation method and particle prior knowledge are used fully to make the particles active， and improve the global search capability of the algorithm. The algorithm with 40 nodes was carried out with simulation experiment. The experimental results show that the coverage rate of the improved algorithm can reach up to 87.2%， and is increased by 1.6% and 3.87% respectively than that of the improved shuffled frog leaping algorithm and standard artificial bee colony algorithm.

Keywords： wireless sensor network； artificial bee colony； global optimization； one?dimensional Gaussian mutation； probabilistic measurement model； coverage optimization

0 引 言

无线传感器网络[1]具有低功耗和方便组网的优势，在物联网、智能交通、目标定位和环境探测等领域得到了广泛应用[2?3]。但随着网络中传感器节点数量的不断增加，节点冗余问题也越加突出，怎样才能低成本投入且高效的利用成为研究热门，增大网络的覆盖面积成为无线传感器网络应用的关键问题。

由于传统算法[4?5]存在节点覆盖程度低的问题，要想实现全局最优在技术层面还有欠缺，鉴于无线传感网络的结构与群体智能算法的特点极其相似，因此，大量的学者开始使用智能算法优化无线传感器网络。

文献[6]将改进的粒子群算法应用到无线传感网络的自组织中，有效地提高了节点的覆盖面积；文献[7]根据节点位置信息建立部署模型，提出一种基于改进混合蛙跳算法；文献[8]将遗传算法应用于优化无线传感器网络覆盖；文献[9]将萤火虫算法用于网络覆盖优化。但这些应用于无线传感网络覆盖问题的群体智能算法由于本身存在一些缺点，导致其优化的结果不是很理想。

人工蜂群算法[10?11]具有良好的全局性，已经在很多领域内被证明优于其他一些算法。结合无线传感器网络的结构特点，把节点的部署看成是蜂群寻找最优蜜源的过程，将改进人工蜂群算法应用到无线传感器网络覆盖优化中，与其他几种算法的比较实验说明，提出算法得到的效果有明显改善。

1 人工蜂群算法及改进方法

1.1 人工蜂群算法描述

根據蜜蜂在活动中扮演的角色，将其归纳为观察蜂、采蜜蜂以及侦查蜂三种类型。侦查蜂在正常情况下是不存在的，当采蜜蜂结束采蜜后自动转化为侦查蜂[12?13]。其搜索步骤为：首先采蜜蜂选取周围最近的一个蜜源，然后观察蜂通过信息跟随其中一只采蜜蜂，在这个过程中选取出较好的蜜源，最后采蜜蜂放弃蜜源，转化为侦查蜂，随机搜索新蜜源。

上述过程即为一个优化问题，将每个蜜源的位置看成一个解。假设蜜源位置表示为总数为其中，第个蜜源表示为为其收益度值。观察蜂选取蜜源的概率表示如下[14]：

观察蜂对周边的蜜源进行权衡后，会选取较好的蜜源，蜜源位置更新公式为：

式中：为[0，1]之间的随机数。如果，那么观察蜂就会更新位置，否则不变。在更新的同时限定次数加1，当循环次数达到限定阈值时，会丢弃该蜜源，转化为侦查蜂，生成位置公式为：

1.2 改进的人工蜂群算法

在蜂群算法中，当达到一定次数后适应值仍然没有改进时，该蜜蜂会变成侦查蜂，然后随机生成新的蜜源位置代替原位置。采用侦查蜂随机搜索的目的是当算法处于收敛状态，全部蜜蜂均汇聚在同一蜜源时，把蜜蜂强制转移，以此保证蜜蜂的活力。但由于这种策略放弃了原来蜜源的所有信息，导致算法收敛速度较慢，为了让蜜蜂既能够保证足够的活力，同时又可以充分地利用先验知识，采用一维高斯变异的搜索策略，计算公式如下：endprint

人工蜂群算法采用概率选择蜜源位置进行更新，所以具有全局搜索能力，从而使粒子具有很强的随机性，即便是加入了收益度值的判定，并没有明显提高其收敛速度。所以又在更新公式中增加了最优蜜源位置这样就使得其性能更加均衡，改进算法位置更新的表达式为：

改进人工蜂群算法的步骤如图1所示。

2 网络覆盖优化的问题

无线传感网络覆盖优化的问题可以描述为：在一个已知大小的空间内布置多个能够感应与通信的节点，在保证节点之间连通性的同时，采取一定的措施来部署节点，且尽可能使用较少的节点达到网络覆盖范围最大化。其中网络覆盖率是最重要的一个衡量标准。

常用的节点测量有二元测量法和概率测量法两种模型[15]。由于前者具有本身的局限，容易导致测量的精度偏低，故这里通过概率测量模型研究无线传感器网络覆盖率的问题。设测量范围内有个节点，节点用表示，其中且每个节点的属性和参数均相同，通信半径为感应半径为同时满足

在二维空间中研究该问题，假设节点所处的位置为，测量范围内任意点坐标为，所以相对的检测概率可表示如下：

式中：是传感节点测量的可靠性参数，且是到的欧氏距离；为传感器节点属性相关参数，且满足与是输入参数。

通过得到的能够算出测量范围内传感器节点对点的联合检测概率，可表示如下：

式中表示测量范围内的全部节点。在这里设定的检测阈值为0.8，也就是说，当联合检测概率小于0.8时，就可以认为点不被检测；反之，就认为点可以被检测。

假设检测区域为规则矩形，为了计算无线传感器网络覆盖率，在检测区域上划分个面积相等的小矩形，然后把小矩形看作点利用式（8）算出所有点的检测概率，同时计算出被检测点的数量，两者的乘积即为覆盖面积，那么覆盖率可以表示为：

3 实验结果及分析

为了验证改进人工蜂群算法在无线传感器网络覆盖中的效果，使用Matlab软件对其进行仿真实验，并与标准粒子群算法、标准人工蜂群算法和文献[7]中的改进蛙跳算法进行对比，进而说明本文提出算法的有效性。

3.1 相同节点数量对比实验

在边长50 m的正方形区域内，随机部署40个节点，感应半径5 m，通信半径10 m，传感节点测量的可靠性参数传感器节点属性相关参数。

参与比较算法的迭代次数极限为500，粒子数为50。其中，标准人工蜂群算法和改进人工蜂群算法参数设置一致，最大采蜜次数为50，改进蛙跳算法的迭代次数为5，粒子群算法参数且从0.5～0.2线性递减。

为了验证提出的改进算法的优越性，将标准粒子群算法（PSO）、改进蛙跳算法（GSFLA）和标准人工蜂群算法（ABCA）进行比较，得到的结果如表1所示。

从表1得到的结果可以看出，采用改进人工蜂群算法的无线传感器网络覆盖率达到了87.2%，与改进蛙跳算法相比提高了1.6%，与标准人工蜂群算法相比提高了3.87%，网络覆盖率得到了明显的改善。

为了从直观上观察覆盖效果，将上述实验结果输出，分别得到40个初始节点、改进蛙跳算法、标准人工蜂群算法和改进人工蜂群算法的直观覆盖效果如图2～图6所示。

从上面几种算法对应的覆盖图可以看出，利用智能算法对初始节点覆盖进行优化后，大块空白的现象消失，节点分布趋于均衡，改进人工蜂群算法的优化效果最佳。

3.2 不同节点数量对比实验

为进一步验证改进人工蜂群算法在无线传感器网络覆盖中的效果，与标准人工蜂群与改进蛙跳算法在不同节点数量下的覆盖率进行了对比实验，配置参数不变，得到的结果如表2所示。

从表2可以看出，改进人工蜂群算法不管是在节点数量较多时，还是在节点数较少时均比其他几种算法能更加有效地提高无线传感器网络覆盖率。为方便对比在节点变化情况下算法覆盖优化效果变化差异，将节点数量与覆盖率的关系变化绘制成曲线图，如图7所示。

从节点数量与覆盖率关系曲线图中可以看出：随着无线传感器节点数量的增多，网络覆盖率均得到了明显的提升。节点的利用率体现在曲线的斜率上，随着无线传感器节点数量的增多，均表现出减弱的趋势，但是改进人工蜂群算法的下降速率要小于标准人工蜂群的下降速率，说明改进人工蜂群算法的全局搜索能力更强，在同等条件下具有更优的节点利用率，网络覆盖效果更好。

4 结 语

结合无线传感器网络的结构特点，引入改进人工蜂群算法，在更新策略中添加全局最优个体反馈，提升了算法的收敛速度，并借助一维高斯变异的更新方法，保证了粒子的活力，同时具有良好的全局搜索能力。在40个节点时进行了对比实验，结果显示，使用改进人工蜂群算法的网络覆盖率均优于其他几种算法，比改进蛙跳算法提高了1.6%，比标准人工蜂群算法提高了3.87%，且能够使节点分布更加均匀，在不同节点的实验中，改进人工蜂群算法依然能够保持较好的全局搜索能力和鲁棒性，相比其他算法具有更优的节点利用率和覆盖效果。

参考文献

[1] 龙宇翔，赵英杰.基于WSN覆盖问题及自愈算法的研究[J].现代电子技术，2016，39（1）：27?30.

LONG Yuxiang， ZHAO Yingjie. Study on coverage control problem for WSN and self?healing algorithm [J]. Modern electronics technique， 2016， 39（1）： 27?30.

[2] FERNANDO L， ANTONIO?JAVIER G， FELIPE G， et al. A comprehensive approach to WSN?based ITS applications： a survey [J]. Sensors， 2011（11）： 10220?10265.endprint

[3] 张敖木翰，张平，曹剑东.基于物联网的公路交通运行状态评估与预测[J].公路，2015，60（9）：178?183.

ZHANG Aomuhan， ZHANG Ping， CAO Jiandong. Estimate and prediction of traffic state on expressway under Internet of Things [J]. Highway， 2015， 60（9）： 178?183.

[4] CRISTINA A， PEDRO S， ANDR?S I， et al. Wireless sensor networks for oceanographic monitoring： a systematic review [J]. Sensors， 2010， 10（7）： 6948?6968.

[5] 戴宁，毛剑琳，付丽霞，等.基于虚拟势场的有向传感器网络覆盖优化算法[J].计算机应用研究，2014，31（3）：905?907.

DAI Ning， MAO Jianlin， FU Lixia， et al. Virtual potential field based coverage optimization algorithm for directional sensor networks [J]. Application research of computers， 2014， 31（3）： 905?907.

[6] 王巍，彭力.基于改进微粒群算法的移动传感器网络自组织[J].计算机工程与设计，2009，30（3）：654?659.

WANG Wei， PENG Li. Self?deployment of mobile sensor network based on improved particle swarm optimization [J]. Computer engineering and design， 2009， 30（3）： 654?659.

[7] 李响，郑瑞娟.基于改进蛙跳算法的无线传感器网络覆盖优化[J].计算机测量与控制，2014，22（6）：1993?1995.

LI Xiang， ZHENG Ruijuan. Wireless sensor network coverage optimization based on improved leapfrog algorithm [J]. Computer measurement & control， 2014， 22（6）： 1993?1995.

[8] 屈巍，汪晋宽，赵旭，等.基于遗传算法的无线传感器网络覆盖控制优化策略[J].系统工程与电子技术，2010，32（11）：2476?2479.

QU Wei， WANG Jinkuan， ZHAO Xu， et al. Optimal coverage stra?tegy based on genetic algorithm in wireless sensor networks [J]. Systems engineering and electronics， 2010， 32（11）： 2476?2479.

[9] 刘洲洲，王福豹，张克旺.基于改进萤火虫优化算法的WSN覆盖优化分析[J].传感技术学报，2013，26（5）：675?682.

LIU Zhouzhou， WANG Fubao， ZHANG Kewang. Performance analysis of improved glowworm swarm optimization algorithm and the application in coverage optimization of WSNs [J]. Chinese journal of sensors and actuators， 2013， 26（5）： 675?682.

[10] 张鹏，刘弘，刘鹏.改进的蜂群算法及其在CBD选址规划中的应用[J].计算机科学，2013，40（8）：210?213.

ZHANG Peng， LIU Hong， LIU Peng. Improved artificial bee colony algorithm and its application in CBD location planning [J]. Computer science， 2013， 40（8）： 210?213.

[11] 陈杰，沈艳霞，陆欣.基于信息反馈和改进适应度评价的人工蜂群算法[J].智能系统学报，2016，11（2）：172?179.

CHEN Jie， SHEN Yanxia， LU Xin. Artificial bee colony algorithm based on information feedback and an improved fitness value evaluation [J]. CAAI transactions on intelligent systems， 2016， 11（2）： 172?179.

[12] BARRON J L， FLEET D J， BEAUCHEMIN S S. Performance of optical flow techniques [C]// Proceedings of 1992 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 1992： 236?242.

[13] 张玲，王玲，吴桐.基于改进的粒子群算法优化反向传播神经网络的热舒适度预测模型[J].计算机应用，2014，34（3）：775?779.

ZHANG Ling， WANG Ling， WU Tong. Thermal comfort prediction model based on improved particle swarm optimization?back propagation neural network [J]. Journal of computer applications， 2014， 34（3）： 775?779.

[14] 孙泽宇，伍卫国，王换招，等.概率模型下的一种优化覆盖算法[J].软件学报，2016，27（5）：1285?1300.

SUN Zeyu， WU Weiguo， WANG Huanzhao， et al. Optimized coverage algorithm in probability model [J]. Journal of software， 2016， 27（5）： 1285?1300.

[15] 孙伟，朱正礼，郑磊，等.基于人工鱼群和微粒群混合算法的WSN节点部署策略[J].计算机科学，2012，39（11）：83?85.

SUN Wei， ZHU Zhengli， ZHENG Lei， et al. Deployment strategy of wireless sensor network nodes based on AFSA?PSO hybrid algorithm [J]. Computer science， 2012， 39（11）： 83?85.endprint