基于周期果蝇算法的无线传感网覆盖优化

尹向兵，吴良超

（1.安徽警官职业学院 教务处，安徽 合肥 230031；2.安徽大学 计算智能与信号处理重点实验室，安徽 合肥 230039）

基于周期果蝇算法的无线传感网覆盖优化

尹向兵1，吴良超2

（1.安徽警官职业学院 教务处，安徽 合肥 230031；2.安徽大学 计算智能与信号处理重点实验室，安徽 合肥 230039）

无线传感器网络(Wireless Sensor Networks,WSN)是一种分布式传感网络，由大量可移动的微型传感器节点以自组织的方式组成，信息通过节点进行多跳传输.在无线传感器网络覆盖问题上，传统的节点部署策略会出现部署速度慢，覆盖范围小，服务质量差等问题.本文将提出一种改进的果蝇算法，实现网络覆盖的优化.果蝇算法具有很多优点，例如计算量较小，运行时间短，算法复杂度低，且寻优精度较高等.本文将果蝇算法与WSN覆盖模型相结合，可以快速实现节点布局优化，得到更高的网络覆盖率.通过仿真对比实验，可以看出改进果蝇算法的有效性和优越性，在寻优性能方面明显优于其它几种算法.

WSN；果蝇算法；传感器节点；覆盖优化

1 引言

无线传感器网络[1]是一种分布式传感，面对多节点、多任务的无线自组织网络.无线传感器网络是由大量部署在监测区域内的传感器节点组成，通过传感器节点对监测区域的信息进行实时收集.WSN作为一门新的技术，被广泛应用于军事领域、农业生产、生态监测与灾害预警、基础设施状态检测、工业领域、智能家居等.传感器网络的一个关键问题就是节点的部署优化，对于如何提高网络的覆盖率、降低网络的能耗、简化网络模型，最终提高服务质量，这是目前研究的一大热门问题，也是未来无线传感技术发展的基础.

目前已有多种智能算法运用在无线传感器网络的覆盖优化问题上，例如粒子群算法、鱼群算法、遗传算法等.这些算法虽然在覆盖的优化问题上取得了良好的效果和重大的进步，但依然存在着一些明显的不足，例如某些算法的结构过于复杂，导致整体的计算速度太慢，达不到实时的要求，某些算法的性能太差，导致最后的覆盖效果太差，远远达不到用户的服务要求，某些算法的参数太多，导致网络模型过于复杂，实际的部署方式往往不容易做到，等等.因此本文将运用一种改进的果蝇算法，解决以上算法在无线传感器网络覆盖优化问题上的弊端，实现对网络覆盖的进一步优化.

2 果蝇算法

果蝇优化算法[2]（Fruit Fly Optimization Algorithm，FOA）是台湾学者潘文超经过研究发现，并于2011年提出的一种新型智能优化算法，它具有很好的全局优化性能，能够解决很多的优化求解问题.果蝇有着优于其它生物的感官知觉，特别是视觉与嗅觉，依靠灵敏的嗅觉，果蝇可以很好的感知到空气中的各种气味分子，甚至可以嗅到几十公里以外的食物.同时利用敏锐的视觉与其它果蝇聚集，并向该方向移动.果蝇算法就是模仿果蝇的觅食过程而提出一种新型的群智能优化算法.

2.1 基本果蝇算法：

果蝇拥有优于其它物种的感官，它可以收集空气中的气味分子搜寻远处的食物，然后聚集同伴朝食物方向并拢. FOA算法就是模拟果蝇群体的觅食过程而衍生的优化算法，其步骤可以归纳为：

①初始化种群大小Sizepop,最大迭代次数Maxgen,随机初始化果蝇群体位置X_axis,Y_axis.

②果蝇个体随机向各个方向的位置进行搜寻.

③计算果蝇个体与原点距离d,再将距离的倒数做为果蝇个体的味道浓度判定值Si.

④将味道浓度判定值 Si代入适应度函数（Fitness function），求出果蝇个体的味道浓度.

⑤找出果蝇群体中Smelli最佳的果蝇

⑥记录并保留最佳味道浓度值bestSmelli与X,Y坐标.

⑦开始迭代，重复执行②～⑤，并判断最佳味道浓度是否优于前一次迭代得到的味道浓度，并且当前迭代次数小于最大迭代数Maxgen,则执行⑥，否则，算法结束.

2.2 改进步长果蝇算法

根据上一节对果蝇算法的介绍，果蝇算法中的果蝇个体每次迭代从相同的起点出发，然后向随机的方向进行搜索，搜索步长为固定区间[-H,H]内的随机数.当H设置比较大时，算法的全局搜索能力较强，收敛的速度较快，但算法局部搜索能力较低，导致后期收敛精度不够.相反，如果H设置比较小时，局部搜索能力较强，全局搜索能力较低，导致算法收敛速度较慢，而且算法在小区域内搜索，收敛结果易陷入局部最优的错误解集中.针对以上所述的局限性，本文提出的可变步长果蝇算法（CS-FOA,Change the Step of FOA）将搜索分为若干个周期，如取50次迭代为一个周期T，每个周期内步长采用Sin(x)的形式进行跌宕变化，表示如下：

其中，L为算法搜索区间长度，T为单位周期的迭代次数，mod(i,T)为第i次迭代相对于T取余.

从公式（1）可以看出，CS-FOA首先将整个搜索过程分为若干个周期，这样做可以增加搜索过程的多样性，使算法能够有效跳出局部收敛，大大减小局部收敛的可能性.其次CS-FOA在每个周期内采用Sin(x)函数，使步长在单位周期T内可以跌宕变化.在Sin(x)单调递增时，步长指数型增大，算法具有很强的全局搜索能力，可以实现快速收敛，并且收敛结果不易陷入局部最优，同时步长的增大可以解决Sin(x)在上个单调递减区间内可能存在的局部收敛问题.在Sin(x)单调递减区间内，步长指数型减小，可以使算法在小范围内完成高精度的搜索，结果具有更好的收敛效果.

3 WSN节点模型

本文采用是网格覆盖模型[3].在一个a×b的二维区域内，区域被离散化为a×b个接收点，每个接收点的位置表示为(at,bt).在该目标区域内随机部署N个传感器节点，节点覆盖的额定有效半径为R.每个节点将自身位置发给Sink节点，由Sink节点完成优化运算.每组传感器节点可以表示为：

节点wi与接收点(ak.bk)距离表示为：

接收点(ak.bk)可以接受到节点wi信号的概率表示为：

接收点(ak.bk)能接收到这组节点发射的信号的概率表示为：

最后，发射器W对这片区域的信号覆盖率表示为：

4 改进果蝇算法的应用

将CS-FOA应用于解决WSN问题的算法步骤如下：

①初始化无线传感器网络相关参数，包括区域长a，宽b，节点的额定有效覆盖半径R，该区域布置传感器节点个数N；

②初始化CS-FOA的相关参数，包括果蝇种群大小Sizepop，最大迭代次数Maxgen，单位周期迭代次数T，搜索区间长度L；

③随机初始Sizepop个果蝇的位置Wt，根据式（2），第t个果蝇的传感器节点表示为wt,i=(xt,i,yt,i)，其中t∈[1,Sizepop]，i∈[1,N]；

④根据式（3）～（6）计算出GW，将GW最大的果蝇标记为最佳果蝇，记录此果蝇的GW以及位置W：

⑤进入迭代寻优计算，果蝇个体根据式（7）确定搜索步长，随机向各个方向搜寻.

⑥执行步骤④，找出其中覆盖率最大的果蝇个体，记录此果蝇的位置和覆盖率，并将此果蝇的覆盖率与上一代最佳果蝇的覆盖率比较，如果此果蝇覆盖率大于上一代覆盖率，那么将此果蝇标记为最佳果蝇.最佳果蝇的位置设为节点位置，也是下一次搜索的果蝇初始位置，所有果蝇向此果蝇聚拢.

⑦循环执行步骤⑤⑥，直至迭代次数达到Maxgen，记录最终的结果.此时得到无线传感器网络最大的覆盖率bestG和对应节点位置G_axis.

5 仿真实验

5.1实验参数设置

实验测试平台 Window XP,Matlab7,机器主频为3.3GHz，内存为2GB.

在50m×50m的正方形监测区域内放置25个无线传感器节点，这些节点具有位置可移动，额定有效半径固定的特点.节点的额定有效半径R为5m，通信半径为2R.

5.2 实验结果分析

图1 CS-FOA覆盖节点分布图

在上述无线传感器网络模型下，选取了FOA、DS-FOA[4]和本文提出的CS-FOA三种算法，设迭代次数Maxgen=200，果蝇种群数量Sizepop=50,搜索长度L=5m，搜索区间为[0,50].仿真实验运行50次，最后对实验结果进行平均.图4为理论最大覆盖率的节点分布图，理论最大覆盖率为78.5%.图5～7分别是上述3种果蝇算法在迭代结束后的节点分布图.在迭代200次后，CS-FOA的覆盖率为77.12%，达到理论最大覆盖率的 98.24%，DS-FOA的覆盖率为75.03%，达到理论最大覆盖率的95.54%，而FOA的覆盖率为68.28%，达到理论最大覆盖率为86.98%.通过比较可以看出，在果蝇优化算法和改进果蝇算法中，CS-FOA能更好的结合无线传感器网络模型，在相同参数的条件下，得到更高的网络覆盖率，问题能够得到更有效的解决.

图2 3种果蝇算法收敛比较图

图2为在上述无线传感器网络模型下，分别应用FOA、DS-FOA和CS-FOA三种果蝇算法对节点分布寻优的覆盖率变化图.从图8可以看出，FOA由于搜索步长固定，所以导致在100次迭代以后，陷入了局部收敛，随着迭代次数的增加，算法自身并不能跳出局部收敛，最后结果的收敛精度不够理想.DS-FOA由于前期搜索步长过大，所以导致算法的收敛速度太慢，到中期的收敛精度依然不高，影响了收敛的整体进度，导致后期的寻优收敛起点太差，算法需要更多次的迭代才能达到一定的效果.相比于FOA和DS-FOA， CS-FOA具有很快收敛速度的同时，也具有很高的收敛精度.CS-FOA通过步长的周期性和跌宕性变化，在寻优周期的前期，随着步长的增加可以使搜索达到快速的收敛，很快的接近理论覆盖率，在寻优周期的后期，算法在小范围内搜索，使搜索结果达到很高的精度，得到更高的网络覆盖率.

为了验证CS-FOA在无线传感器网络覆盖优化问题上的优越性，在迭代次数为200次，覆盖区域面积为50m× 50m，节点额定有效半径为5m的条件下，选取CS-FOA、改进虚拟力粒子群算法[5]（VFPSO）、改进蝙蝠算法[6]（BA）、改进混沌鱼群算法[7]、DS-FOA五种算法进行无线传感器网络覆盖优化的仿真实验，取50次实验的结果平均值作为结果.最后得到结果如表1所示（设理论覆盖率为1）.

表1 算法覆盖率比较表

从表1可以看出，在相同的情况下，相对于其它几种应用在无线传感器网络覆盖优化问题上的改进优化算法，CS-FOA最后得到的网络覆盖率最高，可以得到理论覆盖率的98.24%，相比DS-FOA、改进VFPSO、改进BA和改进鱼群算法，分别提高了2.7%、0.23%、8.98%和1.94%.由于CS-FOA紧密结合无线传感器网络模型和算法高性能的特点，所以在可移动节点的无线传感器网络覆盖优化问题上具有更好的效果.

6 结束语

针对无线传感器网络覆盖优化问题，本文应用了一种改进的果蝇算法（CS-FOA）.通过对仿真实验的数据展示和分析，可以看出CS-FOA在无线传感器网络覆盖优化问题上具有良好的性能（收敛精度和收敛速度），相对于其它几种应用于无线传感器网络覆盖优化问题的改进智能优化算法，本文算法能够更好的结合网络模型，具有更好的效果和过程更加稳定，最后得到更高的网络覆盖率，更适用于无线传感器网络覆盖优化.

〔1〕王保云.物联网技术研究综述[J].电子测量与仪器学报, 2009(12):1-7.

〔2〕潘文超.果蝇最佳化演算法[M].台北:沧海书局,2011.10-12.

〔3〕徐跃州,张欣.基于混沌果蝇算法的WSN优化布局[J].计算机工程与设计,2015(4).

〔4〕宁剑平,王冰,李洪儒,等.递减步长果蝇优化算法及应用[J].深圳大学学报(理工版),2014,31(4):367-373.

〔5〕宋明智,杨乐.改进VFPSO算法于WSN节点随机部署中的应用[J].计算机工程与应用,2016,52(2):141-145.

〔6〕袁曦,张曦煌.基于改进蝙蝠算法的无线传感器网络的移动节点部署[J].传感器与微系统,2016,35(3):144-146.

〔7〕李显,刘明生,李燕,等.基于混沌鱼群改进算法的无线传感网覆盖优化[J].激光杂志,2015(1):98-101.

TN926；TP393

A

1673-260X（2017）08-0015-03

2017-05-06

本文为安徽省高校自然科学研究项目“《基于云平台实验实训教学资源库系统开发与应用》（12219zrkx2015B02）”的研究成果