基于混沌果蝇算法的WSN优化布局

徐跃州，张 欣

（贵州大学 大数据与信息工程学院，贵州 贵阳550025）

0 引 言

无线传感器网络［1］节点的优化部署研究可以有效提高传感器网络覆盖率和降低能耗，增长网络寿命。目前，常用的优化算法有虚拟力算法 （VFA）、萤火虫群优化（GSO）、粒子群算法 （PSO）、蛙跳算法 （SFLA）等，文献 ［2－5］分别采用VFA、GSO、PSO、SFLA这4种算法对传感器网络节点进行优化部署，提升监测区域的覆盖率。然而，上述算法却存在着高复杂度、低收敛速度和精度等问题。针对这些问题，本文提出一种简单、高效的混沌果蝇算法 （chaotic fruit fly algorithm，CFOA），并通过仿真验证分析其性能的优越性。

1 果蝇算法

果蝇 算 法［6］（fruit fly optimization algorithm，FOA）是2011年台湾学者潘文超从果蝇觅食行为中得到启发，提出的一种寻求全局优化的新方法，是一种新型仿生行为学智能算法，广泛运用于求解函数极值、Z－SCORE模型的系数调整、向量机参数优化以及各类广义回归神经网络系数优化等［7］。由于算法提出较晚，FOA的研究仍处于起步阶段，理论尚不成熟，如对多维极值复杂优化的问题等。

FOA与VFA、GSO、PSO、SFLA相比，不但算法简单、收敛速度快 （如SFLA和PSO的优化方程为二阶微分方程，而FOA的优化方程为一阶微分方程）、代码运行时间短，且FOA仅需调整3个参数，算法复杂度低；而其它仿生算法至少需调整6、7个参数，各个参数间的关系和相互影响十分复杂，导致分析算法的复杂度变得异常困难［8］。与此同时，果蝇算法和上述算法一样，极易陷入局部最优解，以至于后期收敛精度降低、收敛速度变慢，特别是对于高维多极值复杂优化问题。

2 混沌优化

混沌优化 （chaos optimization，CP）是利用混沌运动的随机性、遍历性、规律性和初值敏感性来提高随机优化算法的效率［9］，混沌运动介于确定性与随机性之间，具有丰富的时空动态，并且混沌搜索能在一定范围内按其身的“规律性”不重复的遍历所有状态。Logistic映射系统是混沌系统中最著名的系统模型之一，其模型如下

当u＝4时，系统处于混沌状态。若xi∈［mi，ni］，可由式 （2）、式 （3）对混沌变量xi进行往返映射，具体的混沌搜索迭代方法可见文献 ［10］

由于果蝇算法类似于其它智能算法，均为通过对初值的迭代和进化寻求最优解，初值的选取不当极易使算法陷入局部最优，而对于传感器网络节点部署，模型及其复杂，很难找出一个对初值的评价标准。为了避免算法陷入局部最优，采用混沌优化，随机生成一个混沌扰动因子，在每次果蝇群进化前进行混沌扰动，使果蝇群迅速跳出局部寻优，进行全局搜索。

3 WSN节点部署模型

假设在一个二维监测区域，区域被离散化为m＊n个像素点，每个像素点表示为（m，n）。在该区域内投入N个传感器节点，其感知半径为r。传感器的节点集表示为式（4），节点和像素点距离为式 （5）

则像素点（mi，ni）被节点ci监测到的概率为

所以，该像素点被节点集C联合监测到的概率为

综上，传感器网络的节点覆盖率［11］为

4 混沌果蝇算法的应用和性能分析

本文在借鉴文献 ［12］的基础上，提出混沌果蝇算法，具体算法如下：

步骤1 随机初始化N个果蝇位置，Smellbest＝0，步长h；果蝇位置为： （Init X（i），Init Y（i）），其中i∈（1，N）；

步骤2 根据式 （8）、式 （9），求出覆盖率最大的果蝇及其位置

步骤3 记录果蝇位置和覆盖率，所有果蝇飞向该位置，如式 （10）所示

步骤4 根据果蝇步长h，每个果蝇随机向4周搜寻食物，如式 （11），其中K为节点个数

步骤5 重复步骤2；

步骤6 对当前覆盖率最大的果蝇进行混沌搜索，随机生成两个n维变量

根据混沌模型可得式 （13），将得到的 （a2，b2）各个分量载波到混沌扰动范围［－d，d］，则扰动量为式 （14），此时新位置坐标为式 （15）

计算新老位置的覆盖率f＊、f，若f＊＞f，则

若f＊＜f，则果蝇位置与bestSmell不变，混沌搜索迭代M次。

步骤7 重复步骤3。

步骤8 迭代步骤4～步骤7，直至迭代结束，得到最优分簇 （X＿axis，Y＿axis）和最优解Smellbest。

从上述算法流程可以看出，CFOA每次迭代时，所有果蝇均聚集到当前最优位置进行寻优，相对于其它智能算法各个因子从当前位置移动向最优位置寻优，具有更好的收敛速度；对于智能算法 “早熟”问题，CFOA每次迭代时，对当前的最优位置进行混沌扰动，及时跳出 “早熟收敛”，进行全局寻优。显然，混沌果蝇算法具有更高的收敛速度和收敛精度。

5 仿真结果及分析

假定在边长为50 m的正方形监测区域中放置25个同一性能的传感器网络节点，节点额监测半径r＝5 m。当粒子数为待测区域面积的0.25%至4%时，偏差约为0.1%至0.5%，综合分析，本文均匀选取2500个粒子，使实验结果具有较小的偏差性。为了分析CFOA中果蝇算法的参数选择，本文从不同果蝇种群，不同初始覆盖率以及不同迭代步长3个方面进行仿真研究，挑选出合适的参数应用于混沌果蝇算法，如图1～图3所示。所有算法均在MATLAB2012上进行仿真模拟。

图1 种群数目不同的网络覆盖率

图2 初始覆盖率不同的网络覆盖率

如图1所示，选取固定的果蝇群 （初始覆盖率为58.3%），步长h＝1，迭代200次。从图1中可以看出数量大的果蝇群 （（N＝100））在算法前期体现出良好的收敛性和收敛精度，但随着算法迭代，数量小的果蝇群 （N＝50）和数量大的果蝇群在收敛精度上渐渐趋于一致。

图3 步长不同的网络覆盖率

如图2所示，选取不同的果蝇群 （初始覆盖率为59%、63%），步长h＝1，迭代200次，果蝇种群数量N＝50。从图2中可看出初始覆盖率为63%的果蝇算法全局收敛性和收敛精度均远高于初始覆盖率为59%的果蝇算法。这表明果蝇算法的初始布局直接影响传感器网络最终布局的优劣。

如图3所示，选取固定的果蝇群，相同的迭代次数，不同的步长h。从图3中可以看出，步长为两个单位的果蝇群在前期收敛速度很快，但后期步长小的果蝇群收敛速度和精度却渐渐超过步长大的果蝇群。这说明选择合适果蝇步长将直接提升算法的性能。

如图4～图7所示，选取近些年深入研究的蛙跳和虚拟力算法与混沌果蝇算法作比较，蛙跳算法参数为：种群分组数m＝8，模因组青蛙数n＝8，组内最大迭代数Ne＝8；虚拟力算法参数为：距离阈值dth＝10 m，Max＿Step＝2.5 m；混沌果蝇算法参数为：N＝100，h＝1，M＝50。图4～图7是4种算法的节点覆盖图，在边长为50m的正方形监测区域，25个传感器节点理论最优覆盖率为78.5%。图4为蛙跳算法200轮后节点覆盖图，占62.5%，达到最优覆盖率的79.6%；图5为虚拟力算法200轮后节点覆盖图，占67.3%，达到最优覆盖率的85.7%；图6为果蝇算法200轮后覆盖图，占72.7%，达到最优覆盖率的92.6%；图7为混沌果蝇算法200轮后覆盖图，占76.4%，达到最优覆盖率的97.3%。仿真结果表明，果蝇算法和改进果蝇算法要明显优于蛙跳和虚拟力算法，改进果蝇算法更易于摆脱局部极值解，寻求全局最优解。

如图8所示，混沌果蝇算法和果蝇算法在收敛速度和收敛精度上远优于虚拟力算法和蛙跳算法，更适用于WSN节点布局优化。果蝇算法在前期性能较好，但在后期随着网络布局的稳定渐渐收敛，陷于局部极值解；而混沌果蝇算法能够在果蝇进化时进行混沌扰动，跳出局部搜索，进行全局寻优，具有更好的网络布局优化性能。

6 结束语

本文针对WSN传统算法覆盖率低、算法复杂高的问题，提出一种简单、高效的混沌果蝇算法，并应用于无线传感器网络的节点布局。该算法通过在果蝇算法每次进化时对当前最优解进行混沌扰动，保证果蝇群在下轮迭代时具有一个更好的初始值。

图4 蛙跳算法节点覆盖

图5 虚拟力算法节点覆盖

图6 果蝇算法节点覆盖

图7 混沌果蝇算法节点覆盖

图8 4种算法性能比较

通过MATLAB仿真结果表明，混沌果蝇算法能够迅速跳出局部极值解，进行全局搜索。相对于其它智能算法，混沌果蝇算法具有更高的网络覆盖率、更快的收敛速度以及更低的算法复杂度，更适应于当前的传感器网络布局优化。随着WSN发展迅速，应用广泛，下一步将重点研究传感器节点基于混沌果蝇算法的动态半径规划。

［1］WANG Chengliang，WANG Qiang.Activity－aware ＆energy balance based routing protocol for wireless sensor networks［J］.Journal of Beijing University of Aeronautics and Astronautics，2014，40 （1）：10－17 （in Chinese）.［汪成亮，王强.基于活动预测和能耗均衡的WSN路由算法 ［J］.北京航空航天大学学报.2014，40 （1）：10－17.］

［2］LI Qiangyi，MA Dongqian，ZHANG Juwei.Nodes deployment algorithm based on perceived probability of wireless sensor network ［J］.Computer Measurement ＆ Control，2014，22（2）：643－645 （in Chinese）. ［李强懿，马冬前，张聚伟.基于感知概率的无线传感器网络节点部署算法 ［J］.计算机测量与控制，2014，22 （2）：643－645.］

［3］LIU Cuiping，ZHANG Haitao，BAI Ge.Node deployment of wireless sensor network based on glowworm swarm optimization algorithm ［J］.Journal of Computer Applications，2013，33（4）：905－907 （in Chinese）. ［刘翠苹，张海涛，白舸.基于萤火虫群优化算法的无线传感器节点部署 ［J］.计算机应用，2013，33 （4）：905－907.］

［4］SONG Mingzhi，YANG Le.Improving coverage of wireless sensor network using enhanced adaptive PSO algorithm ［J］.Application Research of Computers，2013，30 （11）：3472－3475（in Chinese）.［宋明智，杨乐.基于改进自适应PSO算法的WSN覆盖优化方法 ［J］.计算机应用研究，2013，30（11）：3472－3475.］

［5］LONG Teng，SUN Hui，ZHAO Jia.Research of mobile node deployment in WSN based on improved frog leaping algorithm［J］.Computer Engineering，2012，38 （5）：96－98 （in Chinese）.［龙腾，孙辉，赵嘉.基于改进蛙跳算法的 WSN移动节点部署研究 ［J］.计算机工程，2012，38 （5）：96－98.］

［6］PAN Wenchao.Using fruit fly optimization algorithm optimized general regression neural network to construct the operating performance of enterprises model ［J］.Journal of Taiyuan University of Technology，2011，29 （4）：1－5 （in Chinese）. ［潘文超.应用果蝇优化算法优化广义回归神经网络进行企业经营绩效评估 ［J］.太原理工大学学报，2011，29 （4）：1－5.］

［7］CHENG Hui，LIU Chengzhong.Mixed fruit fly optimization algorithm based on chaotic mapping ［J］.Computer Enginee－ring，2013，39 （5）：218－221 （in Chinese）. ［程慧，刘成忠.基于混沌映射的混合果蝇优化算法 ［J］.计算机工程，2013，39 （5）：218－221.］

［8］HAN Junying，LIU Chengzhong.Fruit fly optimization algorithm with adaptive mutation ［J］.Application Research of Computers，2013，30 （9）：2641－2644 （in Chinese）. ［韩俊英，刘成忠.自适应变异的果蝇优化算法 ［J］.计算机应用研究，2013，30 （9）：2641－2644.］

［9］LIU Changping，YE Chunming.Firefly algorithm with chaotic search strategy ［J］.Journal of Systems ＆ Management，2013，22 （4）：538－543 （in Chinese）. ［刘长平，叶春明.具有混沌搜索策略的萤火虫优化算法 ［J］.系统管理学报，2013，22 （4）：538－543.］

［10］ZHAN Mengmeng.Reactive power optimization of distribution network based on modified chaos genetic algorithm ［D］.Hangzhou：Hangzhou Dianzi University，2013：19－21 （in Chinese）.［詹萌萌.基于改进混沌遗传算法的配电网无功优化 ［D］.杭州：杭州电子科技大学，2013：19－21.］

［11］LI Li.Strategy of WSN coverage optimization by improved artificial fish swarm algorithm ［J］.Microelectronics ＆ Computer，2013，30 （2）：83－86 （in Chinese）. ［李丽.基于改进鱼群算法的WSN覆盖优化策略 ［J］.微电子学与计算机，2013，30 （2）：83－86.］

［12］PAN Wenchao.A new fruit fly optimization algorithm：Taking the financial distress model as an example ［J］.Knowledge－Based Systems，2012，26：69－74.