王　伟，朱娟娟，万家山，乔　焰，李　旸*

（1.安徽农业大学信息与计算机学院，合肥230036；2.农业部农业物联网技术集成与应用重点实验室，合肥230036；3.安徽工程大学机电学院，安徽芜湖241000）



基于混沌量子粒子群算法的无线传感器网络覆盖优化*

王伟1，2，朱娟娟1，2，万家山3，乔焰1，2，李旸1，2*

（1.安徽农业大学信息与计算机学院，合肥230036；2.农业部农业物联网技术集成与应用重点实验室，合肥230036；3.安徽工程大学机电学院，安徽芜湖241000）

摘要：针对传统粒子群算法在求解无线传感器网络覆盖问题上存在的收敛速度慢、易陷入局部极值等缺陷，以提高传感器网络覆盖率为主要优化目标，提出了基于量子粒子群和Logistic混沌映射相结合的优化算法CQPSO。该算法基于量子δ势阱模型，同时引入精英个体适应值方差的早熟判断机制，提高了搜索效率。仿真结果表明，对比基本粒子群、混沌粒子群以及量子粒子群三种算法，该算法在覆盖率、均匀度以及平均移动距离指标方面具有更好的覆盖优化效果。

关键词：无线传感器网络；混沌搜索；量子粒子群；覆盖优化

自温总理提出“感知中国”以来，我国物联网产业进入健康快速的发展期。作为当前物联网领域的热门研究方向，无线传感器网络［1］WSN（Wireless Sensor Networks）的研究与开发也越来越得到重视。作为一种目标区域监测和信息获取的重要技术，无线传感器网络在环境保护［2-3］、智慧医疗［4］、智能建筑、农业物联网［5］等诸多领域发挥着重大作用。

覆盖率是无线传感器网络的一个重要的衡量指标［6-7］，如何使用有限数量的传感节点最大范围的覆盖目标区域，同时尽可能的延长网络生存时间，一直是无线传感器网络研究的热点。因此，传感节点在待测区域的部署数量以及分布位置的合理性对于网络服务质量的影响显得尤为重要。针对WSN覆盖优化问题，群体智能算法［8］在这方面的研究越来越广泛，国内外学者们相继提出了基于遗传算法［9］、蚁群算法［10-11］、粒子群优化算法［12］、人工蜂群算法［13］、人工鱼群算法［14］、蛙跳算法［15］以及相关算法的改进组合［16-17］等的WSN覆盖优化算法。这些算法均能够有效提高覆盖率，并使整个网络节点的分布更加均匀。但算法本身也存在着不足之处，均存在“早熟”收敛、局部最优解［18］等问题。

为了获得更优的传感器节点覆盖率，提高算法搜索效率，并克服标准粒子群算法群体智能程度低，协同搜索能力差［19］等缺陷，本文提出一种基于混沌量子粒子群CQPSO（Chaos Quantum-Behaved Particle Swarm Optimization）的WSN覆盖优化算法，通过覆盖率、均匀度、平均移动距离、耗时4个典型的传感器网络性能评价指标，并同基本粒子群、混沌粒子群以及量子粒子群三种算法做对比仿真实验，对CQPSO算法的性能进行验证。

1　相关工作

1.1无线传感器网络覆盖优化问题概述

本文中，传感节点的感知模型采用混合感知模型［20］，相比于圆盘模型，该模型能较为客观的反映现实网络部署环境。假设监测区域为一个二维平面区域，各个传感器节点可以部署在该区域内的任意位置。设传感器网络中传感节点si的坐标为（xi，yi），监测区域中任意点p（像素节点）的坐标为（xp，yp），则节点si对目标点p的监测概率为：

式中：d(si,p)为传感器节点si与目标点p的欧氏距离；re(0＜re＜Rs)是传感节点测量可靠性参数；α1=re-Rs+d(si,p)，α2=re+Rs-d(si,p)；λ1,λ2,β1,β2是与节点特性有关的测量参数。

整个监测区域的传感节点对目标点p同时进行检测的联合检测概率为：

设无线传感器目标节点可以被检测到的概率阈值为Cth，那么，传感器目标节点能被检测到的限制条件为：

假设无线传感器监测区域为m×n（m2）的矩形，将该待测区域划分成大小相等、面积为1的m×n个相同网格，然后再将网格简化成为像素点，其离散精度为1。本研究中，WSN传感器节点覆盖率定义为满足式（3）要求的网格数量与待测区域网格总数之比，即：

那么，覆盖优化问题简述如下：

Step 1利用式（1）计算一个像素点对各个传感节点的覆盖率；

Step 2利用式（2）计算该像素点对各个传感节点的联合覆盖率；

Step 3重复Step 1～Step 2，计算各个像素点对各个传感节点的联合覆盖率；

Step 4利用式（3）～式（4）计算该监测区域的区域覆盖率，把式（4）作为覆盖优化算法的目标函数f。

1.2量子粒子群算法描述

2004年，孙俊博士等从量子力学的角度出发提出了一种新的PSO（Particle Swarm Optimization，PSO）算法模型，该模型是以δ势阱为基础，认为粒子具有量子的行为，并据此提出了量子粒子群算法［21］。在量子空间中粒子满足聚集态的性质完全不同，它可以在整个可行解空间中进行搜索，因而QPSO（Quantum- behaved Particle Swarm Optimization）算法的全局搜索性能优于标准PSO算法，且群体智能化程度高，协同搜索能力强［19］。

设搜索空间为j维，则基于δ势阱模型的粒子位置更新公式如式（5）～式（8）所示：

QPSO算法详细描述如下：

Initialize X；%初始化种群中每个粒子的位置向量

for t=1：t_max

belta=（1.0-0.5）*（t_max-t）/t_max+0.5 %收缩-扩张系数β%从1.0到0.5线性递减

mbest=mean（X）%计算平均最好位置

for i=1 to种群规模N

if f（Xi）＞f（Pi）then Pi=Xi%P保存个体最优值

Pg=max（Pi）% Pg保存群体最优值

for j=1 to粒子维度D

u=rand（0，1）v=rand（0，1）

p=u*Pid+（1-u）*Pg%局部吸引子坐标公式

if v＞=0.5 %位置更新公式

Xid=p+β*abs（mbest-Xid）*ln（1/v）

else Xid=p-β*abs（mbest-Xid）*ln（1/v）

将更新后的粒子位置限制在搜索范围中

直到达到终止条件

1.3Logistic混沌映射

混沌运动具有随机性、规律性、遍历性的特点，这些特性应用到优化搜索中将带来很大的优越性［22］。混沌的随机性可以让搜索形成负反馈，避免陷入局部最优；规律性使得搜索有章可循，新解由确定的迭代方程式产生；遍历性可以无重复的搜索整个可行解区域，提高算法的全局寻优能力。本文使用典型的Logistic混沌映射，方程式如（9）所示：

式中：u为控制参量，N为混沌搜索次数，当u=4，0≤Z0≤1，Logistic完全处于混沌状态。

2　基于混沌量子粒子群的WSN网络覆盖优化算法

2.1算法基本思想

为了解决粒子群算法在求解无线传感器网络覆盖问题上存在的收敛速度慢、易陷入局部极值等问题，本文基于量子粒子群的强全局收敛性和混沌运动的特性，提出了混沌量子粒子群的WSN网络覆盖优化算法。该算法迭代寻优过程中依据精英适应值方差的早熟判断机制，在当前最优解局部进行精细化搜索，避免算法陷入局部极值而停滞，保证了粒子的种群多样性。

2.2基于精英个体适应值方差的早熟判断机制

量子粒子群算法在迭代寻优过程中，如果一些粒子暂时找到局部最优解，则其他粒子通过局部吸引子式（6）迅速向其靠拢，导致整个算法易陷入局部最优，即所谓的“早熟”收敛现象。当种群发生早熟收敛，所有粒子聚集在一起时，算法要么陷入了局部最优解，要么就是找到了全局最优解。此时算法寻优过程十分缓慢，降低搜索效率。为保持种群粒子的多样性，文献［23-25］提出了基于群体适应值方差的早熟收敛判断机制，较好的帮助粒子逃离局部最优。然而，这种机制运算量大、耗时多。为此，本文提出基于精英个体适应度方差的早熟判断机制，其理论依据在于：一个种群发生早熟收敛时，主要应看这个种群中当前适应度暂时最大的那些个体是否有重复或相互趋同的现象。定义如下：

精英个体的适应值方差设粒子种群数量为N，其第t代种群粒子的适应度分别为f1(t),f2(t),…,fN(t)，种群个体的平均适应度记为f_avg(t)，如式（10）所示。将粒子适应度值大于平均适应度的个体成为精英个体，假设有m个（m＜N），记全体精英个体的适应度平均值为f_elite(t)，定义精英个体适应值方差σ2(t)，计算方式如式（11）所示。

其中：F为归一化因子，作用是限制σ2的大小。在本文中，F的取值如式（12）所示。

此处计算f_elite(t)与fi(t)之间的差值，而不是计算fi(t),i∈(1,N)与f_avg(t)之间的差值，主要是为避免适应值差的个体对整个计算结果带来的不利影响，最大程度的反映种群在搜索过程中的收敛情况。

2.3算法流程

①设置WSN传感器节点的覆盖模型参数，利用混沌算法产生初始化的传感节点位置，并根据目标函数计算对应粒子的网络覆盖率；②初始化每个粒子的个体最优Pbest和群体最优Pg；③收缩扩张系数β随迭代次数从1.0到0.5线性减小；④根据式（8）计算种群的平均最好位置mbest，并利用式（5）更新每个粒子的位置，并根据目标函数f计算每个粒子更新后的网络覆盖率；⑤将每个粒子更新位置后的覆盖率与Pbest对应的覆盖率相比较，如果前者较大，则更新Pbest；⑥将种群中的每个粒子的个体最优Pbest对应的覆盖率与Pg对应的覆盖率相比较，如果前者较大，则更新Pg；⑦根据式（11）计算种群适应度的方差σ2，如果σ2＜C（C为判断早熟收敛的停滞阈值，其值根据算法前期测试情况而定），则根据式（9）进行N次（具体算法中取30）混沌搜索，得到最优解向量Y和对应的适应值Ybest，若Ybest＞Pg则Pg=Ybest；⑧如果循环未达到预设最大迭代次数，则返回2）；否则算法结束，并返回群体最优分布。

3　仿真实验

3.1仿真设置与平台

根据1.1节覆盖网络模型，在20 m×20 m的平面监测区域部署30个无线传感器节点。所有节点感知半径Rs=2.5 m，通信半径Rc=2Rs=5 m。概率模型中，λ1=1，λ2=0，β1=1，β2=1.5，Cth=0.6，t_max=500，测量可靠性参数re=1.25 m，使用MATLAB 2010进行实验仿真（算法使用元胞数组保存传感节点位置坐标，每个粒子包含30个传感节点位置坐标）。

3.2停滞阈值C的影响

CQPSO算法的主要参数包括种群规模，收-扩因子β以及停滞阈值C等。对收-扩因子β进行讨论的文献已有很多。因此，本节将重点研究停滞阈值C对算法搜索性能的影响。

种群数量取30，收-扩因子β从1.0到0.5线性减少，停滞阈值C分别取0.002 5，0.003 0，0.003 5，0.004 0，0.004 5。对目标函数f分别进行10次优化，函数的维度取30，迭代次数500，优化结果见下表1。同时，为了更好的评估影响，除主要指标覆盖率外，引入最优值迭代次数（算法寻得最优值之前的迭代次数）、均匀度、平均移动距离、耗时4个性能指标。

表1　停滞阈值C对算法的影响

表1中：elite/all：elite表示基于精英个体适应值方差的早熟判断机制的优化结果，all表示基于群体适应值方差的早熟收敛判断机制的优化结果。网络均匀度指标计算公式如式（13）式所示：

式中：n为节点总数；ki为节点i的邻居数；Di,j为节点i、j之间的欧氏距离；Mi为节点i与其所有邻居节点之间欧氏距离的平均值；U为网络均匀度，U越小，则覆盖均匀性越好。

从表1数据可以发现，C值太小或太大都会影响算法的优化性能。总体来看，基于精英个体适应值方差的早熟判断机制的表现比基于群体适应值方差的早熟收敛判断机制性能的函数优化结果要优越些。在小于及大于0.003 5的范围结果较差。这是由于C取太小会使得粒子非常聚集时才进行扰动，容易陷入局部极值。而C太大，则使得粒子还没有对局部区域仔细搜索就被扰动，影响其局部搜索能力。考虑图1所示两种机制对主要指标覆盖率影响，本次实验中的停滞阈值C取0.003 5。

图1　C的取值对两种机制下覆盖率的影响

3.3实验结果与分析

3.3.1初始传感节点覆盖情况分析

为了分析两种不同算法所产生的初始传感节点位置分布情况，在待测区域生成如图2、图3所示的节点位置分布图（图中的“+”表示传感节点的位置，圆周表示传感节点的感知范围），可以看出：随机生成的传感节点分布杂乱无章，重复覆盖区域较多；而结合混沌算法优化后节点布局较为均匀，重复覆盖区域相对较少。

图2　随机生成的传感节点位置分布

图3　混沌生成的传感节点位置分布

对种群的20个粒子位置分布情况求取平均值，计算出初始覆盖率、均匀度，如表2所示。从表中可以看出，混沌算法产生的初始节点位置分布的覆盖率、均匀度分别为0.712 0、0.824 7，相比于随机生成的0.676 0、1.042 0分别提高3.60%、0.217 3，可见经混沌优化后的传感节点分布具有相对更好的覆盖效果。

表2　传感节点初始位置生成情况对比

3.3.24种算法的实验结果对比

为了验证算法性能，选择基本粒子群（PSO）、混沌粒子群CPSO（Chaos Particle Swarm Optimization）以及量子粒子群（QPSO）3种粒子群算法做对比实验。图4～图7分别代表PSO、CPSO、QPSO以及CQPSO算法优化后的传感节点位置分布。从图4～图7可以看出，CPSO和CQPSO算法优化后的节点在待测区域内分布更加均匀。如图8所示，4种算法经500次迭代进化后，CQPSO、CPSO、QPSO和PSO算法的网络覆盖率分别为88.13%、86.17%、80.17%和75.92%，CQPSO相比于其他3种算法分别提高1.96%、7.96%和12.21%。

图5　混沌粒子群算法优化后的节点分布

图6　量子粒子群算法优化后的节点分布

图8　4种优化算法的网络覆盖率收敛曲线

3.3.3性能指标对比结果

为了更好的评价算法，对4种算法分别进行20次独立的优化实验求各指标均值，比较每种算法在各个性能指标上的优劣，每种算法的性能指标数据如表3所示。

表3　算法运行20次结果对比

从表3数据可以得出：在均匀度方面，CQPSO算法的均匀度最高，20次测试平均值为0.6846，比CPSO、QPSO和PSO算法分别提高了2.51%、9.06%以及16.05%；在平均移动距离方面，CQPSO算法平均移动距离为9.24m，比CPSO、QPSO和PSO算法平均少移动了0.35 m、0.72 m和1.28 m；然而在整个算法耗时方面，CQPSO算法平均耗时21 986 s，比QPSO和PSO算法延时2 182 s和1 587 s，但比CP⁃SO算法耗时快了约710 s，这是由于CQPSO算法有比CPSO算法更好的全局收敛性（位置更新公式的不同），混沌优化次数较少。

综合上述可知，CQPSO算法相比于其他3种算法在网络覆盖率、均匀度以及平均移动距离3个指标方面具有更优的表现，混沌优化后的传感节点分布更加均匀，交叉重复覆盖相对较小，节点能量消耗相对均衡；同时，每个节点平均移动距离减少，降低了节点移动的能量耗损。由于CQPSO算法中增加了混沌优化环节，导致计算复杂度有一定增加，计算耗时相应增多。

4　结语

鉴于覆盖优化问题在当前无线传感器网络研究中的重要性，以网络覆盖率为优化目标，本文将量子粒子群算法和混沌优化相结合，提出了基于混沌量子粒子群算法的无线传感器网络覆盖优化算法。该算法基于量子粒子群算法提高算法的全局收敛性，以及精英个体适应值方差的机制判断算法是否陷入过早收敛；若陷入局部极值，算法对局部极值位置进行混沌搜索，引导其跳出局部最优。仿真结果表明，相对于其他3种粒子群WSN覆盖优化算法，CQPSO算法提高了WSN节点覆盖率，网络均匀度较低，平均移动距离较少，提高了WSN网络的整体性能。

参考文献：

［1］孙利民，李建中，陈渝.无线传感器网络［M］.北京：清华大学出版，2005.

［2］高德民，林海峰，刘云飞，等.基于无线传感网的森林火灾FWI系统分析［J］.林业科技开发，2015，29（1）：105-109.

［3］李光辉，赵军，王智.基于无线传感器网络的森林火灾监测预警系统［J］.传感技术学报，2007，19（6）：2760-2764.

［4］赵泽，崔莉.一种基于无线传感器网络的远程医疗监护系统［J］.信息与控制，2006，35（2）：265-269.

［5］常超，鲜晓东，胡颖.基于WSN的精准农业远程环境监测系统设计［J］.传感技术学报，2011，24（6）：879-883.

［6］Huang C F，Tseng Y C.The Coverage Problem in A Wireless Sen⁃sor Network［J］.Mobile Networks and Applications，2005，10（4）：519-528.

［7］Cardei M，Wu J.Energy-efficient Coverage Problems in Wireless Ad Hoc Sensor Networks［J］.Computer Communications，2006，29 （4）：413-420.

［8］胡中功，李静.群智能算法的研究进展［J］.自动化技术与应用，2008，27（2）：13-15.

［9］贾杰，陈剑，常桂然，等.无线传感器网络中基于遗传算法的优化覆盖机制［J］.控制与决策，2007，22（11）：1259-1292.

［10］黄亮.基于改进蚁群算法的无线传感器网络节点部署［J］.计算机测量与控制，2010，18（9）：2210-2212.

［11］毛科技，方凯，戴国勇，等.基于改进蚁群算法的无线传感器网络栅栏覆盖优化研究［J］.传感技术学报，2015，28（7）：1058-1065

［12］林祝亮，冯远进.基于粒子群算法的无线传感器网络覆盖优化策略［J］.计算机仿真，2009，26（4）：190-193.

［13］文政颖，翟红生.基于混沌人工蜂群算法的无线传感器网络覆盖优化［J］.计算机测量与控制，2014，22（5）：1609-1612.

［14］李显，刘明生，李燕，等.基于混沌鱼群改进算法的无线传感网覆盖优化［J］.激光杂志，2015，36（1）：98-101.

［15］龙腾，孙辉，赵嘉.基于改进蛙跳算法WSN移动节点部署研究［J］.计算机工程，2012，38（5）：96-98，116.

［16］李忠.采用遗传模拟退火策略的WSN节点部署优化［J］.系统仿真学报，2014，26（2）：353-356.

［17］刘洲洲，王福豹，张克旺.改进萤火虫算法性能分析及其在WSNs网络覆盖中的应用［J］.传感技术学报，2013，26（5）：675-682.

［18］赫然，王永吉，王青，等.一种改进的自适应逃逸微粒群算法及实验分析［J］.软件学报，2005，16（12）：2036-2044.

［19］孙俊.量子行为粒子群优化算法研究［D］.无锡：江南大学，2009.

［20］Li S J，Xu C F，Pan W K.Sensor Deployment Optimization for De⁃tecting Maneuvering Targets［C］//Proceedings of 7th International Conference on Information Fusion.Washington，DC：IEEE Com⁃puter Society，2005：1629-1635.

［21］Sun J，Feng B，Xu W B.Particle Swarm Optimization with Parti⁃cles Having Quantum Behavior［C］.Proceedings of 2004 Congresson Evolution Computation.Piscataway，NJ：IEEE Press，2004：325-331.

［22］申清明，阎立军.基于混沌搜索的特征选择方法［J］.兵工学，2013，34（12）：1616-1619.

［23］逄珊，杨欣毅，张小峰.混沌映射的多种群量子粒子群优化算法［J］.计算机工程与应用，2012，48（33）：56-62.

［24］谷海红，齐名军，李士勇.基于混沌机制的混合量子粒子群优化算法［J］.计算机工程，2009，35（12）：164-165，168.

［25］林星，冯斌，孙俊.混沌量子粒子群优化算法［J］.计算机工程与设计，2008，29（10）：2610-2612.

王　伟（1989-），男，安徽六安人，硕士研究生，主要从事计算机应用技术、计算机网络安全方面的研究，17009636880，wwang0211@163.com；

李　旸（1963-），男，安徽怀远人，现任安徽农业大学教授、硕士生导师、院学术委员会副主任、院教学专家组组长，主要研究方向为计算机网络分析管理、智能交通、智能建筑与安全防范技术、农业网络信息工程应用等；担任安徽省及合肥市政府采购资深专家评委；安徽省智能交通协会理事；安徽省建筑智能化资深专家；安徽省教育信息化专家委员会委员，lyand@ahau.edu.cn。

朱娟娟（1991-），女，安徽肥东人，硕士研究生，主要从事从事计算机应用技术、智能农业信息技术方面的研究，15056977902，15056977902@163.com；

Coverage Optimization of Wireless Sensor Networks Based on Chaotic Quantum-Behaved Particle Swarm Algorithm*

WANG Wei1，2，ZHU Juanjuan1，2，WAN Jiashan3，QIAO Yan1，2，LI Yang1，2*
（1.School of Information &Computer Science，Anhui Agriculture University，Hefei 230036，China；2.Key Laboratory of Technology Integration and Application in Agricultural Internet of Things，Ministry of Agriculture，Hefei 230036，China；3.College of Mechanical &Electrical Engineering，Anhui Polytechnic University，Wuhu Anhui 241000，China）

Abstract：The conventional PSO algorithm has its own shortages of low convergence speed，sensitivity to local con⁃vergence in solving problems of the WSN coverage rate.To address these problems，based on the combined utiliza⁃tion of quantum-behaved particle swarm algorithm and logistic chaotic map，taking the network coverage rate as the optimized goal，a hybrid optimal algorithm（chaos quantum-behaved particle swarm optimization，CQPSO）is pro⁃posed.By using the new model based delta potential and judging the local convergence by the variance of the elite individuals’fitness，the algorithm improves the search's efficiency and precision.Simulating results show that the proposed algorithm is superior to other algorithms（namely PSO，QPSO and CPSO algorithm）on the coverage rate，network evenness and average traveling distance.

Key words：wireless sensor networks（WSN）；chaos searching；QPSO；coverage optimization

doi：EEACC：621010.3969/j.issn.1004-1699.2016.02.023

收稿日期：2015-08-10修改日期：2015-12-04

中图分类号：TP391.9

文献标识码：A

文章编号：1004-1699（2016）02-0290-07

项目来源：国家自然科学基金项目（61402013）；省科技攻关计划项目（1301b042008）