灰狼算法下无线传感器网络覆盖优化

前言：想要写出一篇引人入胜的文章？我们特意为您整理了灰狼算法下无线传感器网络覆盖优化范文，希望能给你带来灵感和参考，敬请阅读。

摘要:如何利用移动节点实现覆盖的最大化并减少能量的使用是研究无线传感器网络的一个重要方向。基于Circle映射，改进了莱维飞行策略；结合能量位置融合机制，用优化后的灰狼算法对无线传感器网络覆盖问题进行求解。首先，引入的Cir－cle映射大幅改善了狼群的多样性，从而能实现更加有力的搜索；其次，改进后的莱维飞行策略平衡了不同时期对全局搜索和局部寻优的需求，一定程度上加快了搜索进程，提高了收敛速度；最后考虑能量和位置的交融，每个个体不再单一考虑位置，而是结合一部分能量因素来进行移动。仿真结果表明，未考虑能量受限的改进后的灰狼算法较基本灰狼算法覆盖率有所提升，和其他文献中的算法相比，也具有更高的收敛速度和覆盖率。在考虑能量受限以后，不但保证了覆盖率，还延长了节点寿命。

关键词：无线传感器网络；覆盖优化；灰狼算法；莱维飞行；能量位置融合

随着材料科学和电子信息技术的发展，体积小、能耗低、无线覆盖范围广的传感器越来越来成为主流，无线传感器网络也就自然而然地走进了科学界和工业界的视线中。无线传感器网络作为大量传感器在自组织和多跳的方式下构成的无线网络结构，目的是群体内的协作感知、收集、处理和转发网络覆盖目标区域内感知对象的监测信息。无线传感器网络有着深远的应用前景，无论是在战争战术［1］、化学工业监测和预报，还是航天器状态监控、城市轨道交通和仓储物流管理［2］等领域都极具意义。近年来，群体智能算法在WSN覆盖问题中的应用与日俱增。文献［3］提出了一种粒子群和萤火虫的混合算法（PG－SO），以粒子群为主体，萤火虫进行局部搜索，算法复杂度提升较高，需要迭代的次数显著增加，同时，节点部署稀疏时效果不明显。文献［4］提出了一种指数加权的粒子群改进方法，尽管粒子群动态性能有所改善，但收敛速度并没有大幅提高，粒子群算法早熟的局限性依然存在，对覆盖问题的求解不利。Hu等［5］利用混沌映射加上非线性因子和Delta狼的变异行为对灰狼优化算法进行了改进，但由于是第三优个体的变异，跳出局部最优仍存在困难，变异也导致迭代次数增加，降低了快速性。上述方法虽然可用于解决覆盖问题，但算法带来的覆盖能力依然不够，收敛速度慢，有些还没有考虑能量受限等问题。灰狼优化算法（GreyWolfOptimizer，GWO）是2014年提出的一种群智能优化方法［6］。由于其出色的寻优性能，明显优于粒子群、萤火虫等传统算法，因此被大量应用在核科学［7］、农业预测［8］等领域。然而，与其他算法一样，即便拥有3个优势引导个体，灰狼优化算法也不可避免地存在过早收敛、全局能力不足等问题。针对这些问题，国内外大量学者采取了不同的改进措施来提升算法的性能。文献［9］中用混合蛙跳和灰狼混合，大幅提高了精度，但对低维度问题，尤其是最高三维的覆盖问题求解存在着不足，收敛速度不如传统算法。Zhang等［10］引入差分策略提升了算法的性能，但由于自适应参数和趋优因子的存在，在覆盖问题上反而降低了算法的迭代速度，延长了达到最优的时间，一定意义上降低了整个网络的生存周期。为了提高目标区域覆盖率，文中提出了一种能量位置融合改进灰狼算法。该方法在传统灰狼算法中加入了混沌映射对初始种群进行改进；在更新种群的过程中通过本文提出的改进莱维飞行策略对算法的全局探索能力进行改善；种群更新的同时考虑文中提出的能量和位置融合机制，使得每一步都是平衡两者的更优解，从而提高覆盖率，也为能量受限条件下算法的设计提供新思路。

1覆盖模型分析

假设求解的是二维覆盖问题，即可定义网络监测区域面积为M×N，区域内目标可以被离散化为M×N个点，在区域内随机布置n个传感器节点，节点集可以表示为U＝｛u1，u2，…，un}，所有节点的感知半径Rs和通信半径Rc都相同，且Rs≤2Rc。被检测区域任意节点Ui的坐标为（xi，yi），目标节点Oj的坐标为（xj，yj），两者之间的距离表示为：d（ui，Oj）＝（xi－xj）2＋（yi－yj）■2（1）用Q（ui，Oj）表示节点ui对Oj的感知品质，目标Oj处于节点ui的感知范围内就可以被成功感知，感知质量就是1；反之，节点ui无法感知目标Oj，感知质量就是0，数学表达式如下：Q（ui，Oj）＝1，d（ui，Oj）≤Rs0，其他｛（2）式（2）就是0－1感知模型，感知范围内的目标都可以被成功感知。以提高感知概率为导向，同一目标可能被多个传感节点感知，其节点联合感知概率分布（即联合感知质量）为：Q（U，Oj）＝1－∏ni＝1［1－Q（ui，Oj）］（3）监测区域的总覆盖率Rcov的定义是所有节点覆盖的目标数与总目标数的比值，数学表达式如下：

2灰狼算法原理

灰狼算法是模拟灰狼群体性行为，利用灰狼的等级制度以及在捕食过程中的搜索、包围、捕猎等行为来达到优化的目的。假设灰狼种群个体数为pop，搜索区域的维度为h。其中，第i个灰狼个体的位置可以表示为Zi＝｛Zi1，Zi2，…，Zih}，在种群中适应度（Fitness）最大的个体被记作α，将顺次适应度第二名的个体记作β，第三名记作δ，剩余的个体记作ω。在搜索猎物的过程中，灰狼接近并且围捕猎物行为的数学模型［6］，具体如式（5）－式（9）所示：其中，Zp（t）为第t代猎物的位置；Z（t）为第t代灰狼个体的位置；Ci为摆动因子；r1为［0，1］之间的随机数；A为收敛因子；Tmax为最大迭代次数；r2为［0，1］之间的随机数；a为控制参数，其取值随着迭代次数的增加而线性递减，从2减至0。当灰狼搜索到猎物所在的位置时，头狼α最先带领狼群对猎物采取包围操作；其次，头狼α带领β狼和δ狼对猎物进行攻击捕捉。在灰狼群体中，狼、狼、狼距离猎物位置最近，也就是位置最优的前三名。根据3个头狼位置Zα，Zβ，Zδ来计算其余灰狼个体向猎物移动后的位置，其具体的数学模型如式（10）－式（13）所示：

3算法改进策略

3．1混沌初始化

混沌是非线性系统独有的且广泛存在的一种非周期运动形式，其涉及自然科学和社会科学的每一个分支。因为其普适性和随机性，不同优化算法都能在全局区域实现高效寻优。灰狼算法虽然收敛速度不慢，但在全局寻优上仍然需要改善初始种群的质量。为此，本文在灰狼算法的初始化过程中引入混沌映射，混沌映射可以让初始种群个体分布更加均匀。混沌模型上，本文选择了Circle映射，数学描述如下：其中，Zk为个体位置，通常a取0．2，b取0．5。

3．2改进莱维飞行策略

分析原始灰狼算法可知，整个种群随着迭代次数的增加逐渐向三头优势狼靠近，灰狼个体分布变得集中，极有可能错失全局最优解。为此，文中提出了一种改进的莱维飞行策略，在传统策略下，个体每次都要进行飞行［11］，改进后的策略是否飞行取决于时间步长近似出的数值概率，而在算法全程运行的不同周期中概率不同，有效地平衡了全局和局部能力，既可以让算法在前期不至于全局过于发散，也可以保证在后期具有跳出局部最优的能力。改进的飞行概率随迭代次数t变化的公式如下：其中，Tmax为最大迭代次数。结合改进的莱维飞行策略，下面对灰狼优化算法进行改进，更新后的灰狼个体位置为：Zl（t）＝Z（t）＋α⊕Levy（λ）（20）其中，Zl（t）为飞行后灰狼个体的位置，⊕是点乘符号，α为步长控制参数，Levy（λ）表示随机游走方程，表现形式为幂次未知的概率密度函数，数学表达式如下：Levy～μ＝t－λ，1＜λ≤3（21）通常使用Mantegna算法来模拟莱维分布的随机步长s，为了保证飞行后的个体不会劣于原先位置，引入贪婪策略。如果飞行后的位置优于原先位置，就用新位置替代旧位置；反之，在原位置不动。表达式如下：

3．3能量位置融合

传感器节点的能量储备是有限的，为了节省能量的使用，优化网络资源，提升网络生存周期，本文将能量概念引入算法中，使得算法寻找的最优点不再单单是整个网络的最大覆盖率，而是能量位置移动综合考虑后的最优位置。对灰狼的每一次移动进行归一化以此代表能量，公式如下：改进后适应度函数就变为未覆盖率和能量之和，其值越小越优，公式如下：

4覆盖优化设计

改进后的灰狼优化算法目的是未覆盖率和能量之和最小化，算法步骤如下：Step1初始化参数，设置灰狼种群规模为pop，求解问题的维数为2，最大迭代次数为Tmax。对参数A，C，a进行赋值。Step2初始化种群，利用Circle映射随机产生种群个体。Step3由给出的适应度函数计算各灰狼个体的适应度fitness，并按适应度排序，前三名设置为个体α，β，δ，对应的位置信息为Z1，Z2，Z3。Step4利用式（5）－式（16）更新个体位置。Step5重新按适应度排序，更新前三名。Step6比较随机产生的［0，1］随机数是否大于概率p，如果大于，则进行莱维飞行，保留更优的位置；反之，则不进行飞行，直接进入下一步。Step7再次对灰狼个体按适应度排序，给出前三名的适应度值。Step8判断迭代次数t是否达到了最大迭代次数，如果达到，则输出最优解，即α个体的适应度值，否则返回Step4继续执行。流程图如图1所示。

5仿真实验与分析

5．1未考虑能量受限的仿真

未考虑能量时的仿真主要是改进的IGWO与原始灰狼算法即文献［6］，还有文献［3］、文献［4］、文献［5］进行对比，其中不同文献的实验参数设置与本文相同，随后进行比较。实验平台为CPU主频为2．9GHz、动态加速频率4．2GHz的计算机，仿真软件为MATLAB，所有后续实验均在此实验环境中进行。表1所列为对比算法。（1）与GWO对比实验参数设置：监测区域为10×10的正方形区域，传感器节点数为48，种群数量为30，迭代次数1000，感知半径为1m，通信半径10m。图2给出了GWO与IGWO迭代时的覆盖率变化曲线。由图2可以看出，改进灰狼算法跳出局部最优只有40次迭代，而原始灰狼算法大约需要200次。在改进的莱维飞行策略下，不论是最优还是最弱的个体，跳出局部能力都有一定程度的提升，带来了迭代次数的减少。在寻找全局最优上，改进灰狼算法达到了全覆盖，灰狼算法只有99％，一定程度上可以归功于Circle映射下的初始种群优越性，使得IGWO能做到100％的覆盖率。由此可见，IGWO的全局能力远强于GWO。（2）与PGSO，IPSO，FGWO的对比实验参数同上。图3给出了4种算法的共同对比图。由表2可见，改进后的灰狼优化算法性能明显优于文献［3－5］中所提到的算法。在迭代40次后，改进灰狼算法的覆盖率达到了100％，而其他算法此时的覆盖率不到90％，这可以归因于初始种群的优越性，并且改进的莱维飞行在保证全局能力的同时没有降低前期的收敛速度，全局收敛速度因此有所提高。莱维飞行所进行的随机行走使得个体按照重尾分布改变自身位置，大大提高了跳出局部最优的能力。

5．2能量位置融合仿真

实验平台及参数同上。由图4可见，在考虑能量位置融合后依然能够达到网络的100％覆盖。算法在整个迭代过程中覆盖率也并非一直在上升，由于要考虑能量的影响，覆盖率也会出现回退，但最终仍然能够达到全局最优，即全覆盖。6结束语面对传统无线传感器网络覆盖问题，在随机抛洒的节点覆盖和能量利用效率不佳的情况下，本文提出了改进的莱维飞行策略和能量融合机制并基于Circle映射改进了灰狼算法。改进后的莱维飞行策略进一步加快了收敛速度和全局探索速度。在文章最后提出的能量位置融合机制将节点移动的最优和网络能量的最小化结合在一起，为节省移动节点网络能量提供了新思路。然而，本文研究仍存在一定的改进空间，例如，覆盖模型上可以采用更加贴合现实场景的概率密度分布模型；算法改进上可以采用动态优势种群，使群体探索更灵活；能量受限上可以从网络拓扑的角度进行考虑分析，这也是我们未来要研究的内容。

作者:范星泽 禹梅 单位:华北电力大学控制与计算机工程学院