改进的离散果蝇优化算法在WSNs覆盖中的应用*

霍慧慧， 李国勇

(太原理工大学 信息工程学院，山西 太原 030024)



改进的离散果蝇优化算法在WSNs覆盖中的应用*

霍慧慧， 李国勇

(太原理工大学 信息工程学院，山西 太原 030024)

摘要:针对无线传感器网络(WSNs)随机部署产生的区域覆盖率低、节点利用率差问题，提出一种改进的离散果蝇优化算法(FOA)对WSNs覆盖进行优化。新算法引入自适应步长的分类嗅觉随机搜索和基于移民操作及精英库的多种群协同进化机制，提高了优化精度和效率。仿真实验结果表明：新算法有效解决了WSNs覆盖问题，在确保网络覆盖率最大化的同时节点利用率较大，延长网络寿命。

关键词:无线传感器网络； 覆盖； 果蝇优化算法； 多种群； 自适应步长

0引言

无线传感器网络(wireless sensor networks，WSNs)广泛应用于军事、环境保护、农业和医疗等其他领域。由于传感器节点的能量受限和区域的特殊性，经常需要由飞行器将传感器节点随机撒播在监测区域进行大规模随机部署，由此可能会导致部分区域覆盖盲区或高密度节点部署，覆盖盲区直接影响监测质量，节点密度大则会在汇聚节点接收、处理和转发数据时浪费能量，且过多的冗余数据会堵塞信道和产生数据干扰，影响网络的可靠性。因此，设计一种最大改善初始覆盖率且低能耗的覆盖算法对于WSNs服务质量的提升是很有价值和意义的。

目前，利用群智能优化算法来优化WSNs覆盖已经成为研究的热点，例如：遗传算法、粒子群算法、模拟退火算法等[1～4]。果蝇优化算法(fruit-fly optimization algorithm，FOA)是我国台湾学者潘文超教授提出的一种新的群智能优化算法[5]，具有全局寻优、计算量小、精度高、收敛快速及易于实现等优势。FOA目前已被应用于解决交通事件、企业经营绩效等实际问题，但对于解决WSNs覆盖问题还未查到相关研究。基于此，本文创新性提出一种改进的果蝇优化算法—多种群自适应离散果蝇优化算法(multi-po-pulation adaptive discrete fruit-fly optimization algorithm，MADFOA)， 仿真实验验证了算法的有效性和稳定性。

1WSNs覆盖问题描述

1.1问题模型

随机部署M个固定传感器节点构成节点集S={s1,s2,…,si,…,sM}至二维矩形目标区域A，其中，传感器节点数量M足够大，可以基本满足目标区域的全覆盖。研究的问题是：在保证覆盖率的前提下，将尽可能多的传感器节点置于休眠状态，达到网络全连通并且整体低能耗的效果。

在不影响问题本质的情况下，对WSNs进行相关假设：1)所有传感器节点均是物理同构的，具有相同的感知半径Rs和通信半径Rc，并且通信半径是感知半径的2倍，即Rc=2Rs；2)所有节点均采用全向型天线发射；3)所有传感器节点初始能量相同；4)所有传感器节点均可以获得自己的准确位置信息；5)所有传感器节点均包括工作、侦测和休眠三种状态;6)将目标区域离散化为l×n个像素点。

1.2节点感知模型

传感器节点感知模型一般分为二元感知模型和概率感知模型，由于节点的感知信号会受环境、距离等因素影响，传感器节点与监测像素点的欧氏距离越近，像素点被感知到的概率就越大，数据的可靠性越高；反之，则越小，数据的可靠性越低。鉴于此，引入概率感知模型来表示节点感知信号强度的不确定性。像素点p(xp,yp)可以被节点si(xi,yi)感知到的概率可以表示为

(1)

节点集S联合监测像素点p的概率为

(2)

由于在概率低于阈值Cth时，像素点不能被有效感知，即像素点被有效感知的条件是Cp(S,p)≥Cth。由于Cp(S,p)取值在0～1之间，为简化计算，将像素点p的监测概率设为

(3)

1.3WSNs交叉覆盖模型

(4)

进一步得出传感器节点si的平均重叠覆盖率为

(5)

1.4WSNs覆盖目标

根据问题模型，覆盖目标为寻找满足覆盖质量的最小覆盖集。文献[6]已经证明了在满足全覆盖的条件下，Rc,Rs满足Rc=2Rs时网络可以达到全连通，因此，可以将网络连通性的目标忽略掉。本文定义子集S′⊂S，对于子集S′应满足两个目标：

目标1：覆盖率Pcov(S′)最大，即

(6)

目标2：WSNs中，工作节点数最小，即节点休眠率最大

maxf2=1-|S′|/|S|.

(7)

其中，|S′|为工作节点总数；|S|为WSNs中部署的传感器节点总数。

由于WSNs覆盖目标为两个目标，即多目标优化问题，本文采用加权法将多目标优化问题转化为单目标优化问题，即本文目标函数(味道判决函数)为

maxf=w1f1+w2f2.

(8)

其中，w1和w2为加权系数，代表两个目标函数的权重，由决策者对于目标的侧重性决定其大小，二者之和为1。

2MADFOA优化WSNs覆盖

MADFOA不同于基本FOA：各个种群内部采用自适应步长的分类嗅觉随机搜索策略，种群之间通过移民操作协同进化并采用精英个体最少保持代数替代人为设置的最大迭代次数作为终止条件。

2.1种群编码与初始化

每个果蝇个体对应一个WSNs覆盖状态。本文采用长度为n的二进制编码，表示所有传感器节点的工作状态，其中,n为飞行器随机部署的固定传感器节点数，0,1分别表示传感器处于休眠与工作的状态。

随机初始化N个果蝇个体，并将其随机划分为M个果蝇种群。初始迭代次数g=0，初始精英个体保持次数k=0，终止条件：精英个体最少保持次数为kmax。

2.2基于自适应步长的分类嗅觉随机搜索机制

果蝇在嗅觉搜索阶段的步长设置会影响算法的收敛性能。步长越大，个体寻优范围越广，全局寻优性能强；步长越小，寻优范围减小，个体进行精细化搜索，局部寻优能力强；如果步长过小，个体易陷入局部最优。而传统的固定觅食步长，不能兼顾收敛精度与收敛效率，因此，本文提出了基于自适应步长的分类嗅觉搜索策略，在平衡寻优精度和效率的同时，有效避免算法早熟。

1)自适应步长设计

本文根据果蝇个体之间的相异度(又称距离)来调整其嗅觉随机搜索阶段的步长值。果蝇个体间的相异度定义为二进制编码中相同位置处不同基因位的数目，表达式为

S(xi,xj)=|{xim|xim≠xjm,xim∈xi,xjm∈xj}|.

(9)

例如:假定n=8，xi=(01100010)，xj=(11010111)，则相异度S(xi,xj)=5。本文中果蝇个体的自适应步长策略为Li=S(xi,xbest)，其中,xbest为上一代果蝇个体的最优个体。

2)分类嗅觉随机搜索策略

本文针对不同的步长值，果蝇个体采取逆转和交换两种不同的嗅觉随机搜索策略。

逆转策略：当步长值Li≥2时，在个体xi中随机选定某个位置(视为随机搜索方向)，对该位置及其后续的Li-1个位置的编码进行逆转操作。通过采取该搜索方案，随着果蝇个体与最优个体相异度的减小，逆转操作的力度逐渐减小，使得算法由前期的全局寻优，逐步向后期局部搜索转变，形成自适应的嗅觉随机搜索机制，使算法在寻优精度与搜索效率上获得动态平衡。

交换策略：当步长值Li=1时，此时果蝇个体较为集中，种群多样性减少，容易陷入局部最优。此时，在个体xi中随机选取两个位置(视为随机搜索方向)，并对相应位置的编码进行交换。在果蝇个体差异度很小时，通过对果蝇个体任意两个位置的二进制编码进行交换操作，增强了种群多样性，使其能够跳出局部最优，有效避免早熟，进而提高算法的收敛性能。

2.3多种群协同进化机制

针对原始果蝇算法存在早熟现象和人为设置最大迭代次数的不合理性，本文提出基于移民操作和精华库的多种群协同进化机制。其中，通过精华库收集和保留所有种群公认的最优个体(即精英个体)，实现种群间的信息共享，并将精英个体最少保持代数作为终止条件；各个种群通过移民操作进行种群间的信息交换，实现多种群的协同进化。

基于精英库的信息共享机制。精华库对精英个体的保留操作伪代码实现如下：

ifmax(f(bestj))≤f(elitek-1)

elitek=elitek-1;

k=k+1;

else

elitek=b_best;

k=1.

其中，本次迭代各种群的最优个体bestj(j=1,2,…,M)，上次迭代得到的精英个体elitek-1，本次精英个体为elitek，b_best表示bestj中的最好值。

基于移民操作的信息交换机制。移民操作具体为：M个种群本次迭代得到的最优个体分别为bestj(j=1,2,…,M)，则将种群j+1的最差个体替换为bestj，将第1个种群的最差个体替换为bestM。通过移民操作使各果蝇种群间进行有效的信息交换，实现种群间的协同进化。

2.4MADFOA流程

MADFOA主要提出两个重要改进：1)基于移民操作和精华种群的多种群协同机制；2)各种群内部采用基于自适应步长的分类嗅觉随机搜索机制。新算法具体流程如图1所示。

图1　MADFOA的流程图Fig 1　Flow chart of MADFOA

3实验结果与分析

3.1算法有效性与稳定性

参数设置为：区域D为100 m×100 m，M为200，感知半径为Rs=13 m，通信半径为Rc=26 m,容错感知半径为Re=5 m,λ=0.5,β=0.5，感知概率门限Cth=0.7，w1=0.8，w2=0.2。

1)检验算法的可行性:由参数设定，得出WSNs初始覆盖如图2所示。

图2　WSNs初始节点分布与覆盖区域Fig 2　Distribution and coverage area of initial node

由图2可知，WSNs初始随机部署后，覆盖区域具有明显的覆盖冗余，需要算法对其进行优化。算法优化过程中的部分迭代次数的最优覆盖集如图3所示。

图3　进化过程节点分布图Fig 3　Node distribution diagram of evolution process

由图3知，随着算法迭代次数的增加，冗余节点在逐渐减少，各个目标值变化如表1所示。

表1　进化过程目标值

经过本文算法优化后，覆盖率增加明显，节点休眠率也明显增大。

2)检验算法的稳定性:将算法执行10次，得出实验结果如图4所示。 图中数字表示工作节点数，通过算法优化可以使WSNs覆盖率均可以达到97 %以上，且使得网络中的冗余节点均处于休眠状态，延长网络寿命。

图4　优化前后覆盖率对比Fig 4　Coverage rate comparison before and after optimization

3.2与其他算法进行比较

为进一步验证算法的性能，将本文算法与原始的FOA、覆盖配置协议(coverage configuration protocol,CCP)算法[7]及遗传算法(GA)进行比较分析，得出性能比较曲线如图5所示。

由图5可知，在工作节点数相同的情况下，本文算法可以获得更高的覆盖率。

图5　性能对比曲线Fig 5　Performance comparison curves

4结束语

本文对WSNs覆盖问题进行分析，并提出MADFOA对其进行优化。新算法采用基于自适应步长的分类嗅觉随机搜索和多种群协同进化策略，提高了优化精度与效率。通过实验仿真验证了新算法求解WSNs覆盖优化问题的有效性和稳定性。通过与其他算法的比较，发现在工作节点数相同的情况下，本文算法可以得到更高的覆盖率，增大节点利用率，延长网络寿命。

参考文献:

[1]Mo Yuanbin,Liu Jizhong,Wang Baolei,et al.A novel swarm intelligence algorithm and its application in solving wireless sensor networks coverage problems[J].Journal of Networks,2012,7(12):2037-2043.

[2]张轮,陆琰,董德存,等.一种无线传感器网络覆盖的粒子群优化算法[J].同济大学学报,2009,37(2):262-266.

[3]屈巍,汪晋宽,赵旭,等.基于遗传算法的无线传感器网络覆盖控制优化策略[J].系统工程与电子技术,2010,32(11):2476-2479.

[4]关志艳,耿岩.虚拟力导向群聚智能优化的无线传感器网络覆盖策略[J].传感器与微系统,2015,34(1):40-42,46.

[5]Pan Wen-Tsao.A new fruit-fly optimization algorithm:Taking the financial distress model as an example[J].Knowledge-Based Systems,2012,26(2):69-74.

[6]Zhang H,Hou J C.Maintaining sensing coverage and connectivity in large sensor networks[J].Ad Hoc & Sensor Wireless Networks,2005,1(1/2):89-124.

[7]Wang X,Xing G,Zhang Y,et al.Integrated coverage and connectivity configuration in wireless sensor networks [C]∥Procee-dings of the ACM International Conference on Embedded Networked Sensor Systems (SenSys),New York:ACM,2003:28-39.

Application of improved discrete fruit-fly optimization algorithm in WSNs coverage*

HUO Hui-hui, LI Guo-yong

(College of Information Engineering,Taiyuan University of Technology,Taiyuan 030024,China)

Abstract:An improved discrete fruit-fly optimization algorithm(FOA) is proposed,aiming at problems of low area coverage rate and poor utilization rate of node caused by random deployment of wireless sensor networks(WSNs).Adaptive classify smell-based random search step size and different random search methods for different steps adopted,migration-based operation and elite library are introduced in multiple population co-evolution mechanism,which improves precision and efficiency of optimization.Simulation result shows that this new algorithm effectively resolve problem of WSNs coverage,it has the highest nodes usage while maximizing the network coverage rate and extend the network lifetime.

Key words:wireless sensor networks(WSNs); coverage; fruit-fly optimization algorithm(FOA); multi-population; adaptive size

DOI:10.13873/J.1000—9787(2016)02—0157—04

收稿日期：2015—05—28

*基金项目：国家自然科学基金资助项目(51075291)

中图分类号:TP 212

文献标识码:A

文章编号:1000—9787(2016)02—0157—04

作者简介:

霍慧慧(1988-)，山西文水人，硕士，主要从事预测控制、智能控制理论与应用等研究。

李国勇，通讯作者，E—mail:tygdlgy@163.com。