立方混沌非线性哈里斯鹰优化算法在无线传感器节点部署分析研究
时间：2023-04-20 11:20:07 来源：千叶帆 本文已影响人
洪丽啦，莫愿斌，2，鲍冬雪
（1.广西民族大学 人工智能学院，广西 南宁 530006；
2.广西民族大学 广西混杂计算与集成电路设计分析重点实验室，广西 南宁 530006）
无线传感器网络（Wireless Sensor Network，WSN）实际上就是一个分布式动态传感网络[1]，由多个用于数据信息处理、通信、传输的节点组成，节点覆盖率是衡量无线传感器网络性能的一个重要指标之一，因为它体现了对目标区域的检测能力。传感器节点可以随机或确定性地部署在目标区域，这取决于实际的应用程序，比如在灾区，随机部署比确定性部署具有更高的可行性[2]。20世纪，群体智能概念被正式提出之后，元启发式算法被广泛地应用于处理各种最优化问题。元启发式算法的一个特点是：每次迭代的时候都会根据位置更新机制不断地更新种群位置来寻找最优值，因此，可以利用元启发式动态更新位置的特点调整无线传感器的位置，从而提高传感器网络在检测区域的覆盖率。
近年来，针对传感器网络覆盖率问题，许多学者提出将各种改进的群智能优化算法应用于解决传感器节点部署问题的优化。文献[3]提出了一种基于自适应粒子群的传感器网络覆盖方法，覆盖率相比于其他几种改进的粒子群算法优化有很大提升。文献[4]提出了一种基于帝鹅差分算法的WSN覆盖优化，当算法陷入局部极值时，对种群个体进行差分进化算法中的变异、交叉、选择操作，增加种群多样性。虽然改进的算法相较于灰狼改进算法在覆盖率上有了一定程度的提升，但还是未能解决算法陷入局部最优的缺陷，算法很快就陷入了“早熟”。文献[5]提出了改进差分进化算法下的WSN覆盖优化，通过设置精英群体引导变异向量，参数自适应机制加快种群收敛速度，并在不同节点数量上进行实验，得出在节点数较多的时候覆盖率较高，但是在节点数稀少的时候传感器的覆盖率有待提升。文献[6]提出了一种基于粒子群算法的无线传感器网络信息覆盖优化方法。文献[7]采用分阶段对传感器覆盖进行优化，提出了一种用于混合无线传感器网络的两阶段覆盖增强算法。一是用差分算法计算候选目标的位置；
二是对计算出来的目标位置进行优化，以减少移动传感器的移动距离。虽然以上文献方法有多种改进，但仍存在不足之处。为了更好地提升WSN的覆盖率，本文提出了一种立方混沌非线性哈里斯鹰优化算法的无线传感器节点部署方法。
假设把N个传感器节点随机地抛撒在一个面积为S=V×V的监测区域，节点O={O1,O2,…,O N}，每个节点的结构相同。设节点在区域内的位置坐标为O i=(x i,y i)(i=1,2,…,N)，节点的感知半径为r，通信半径为R，R=2r，为了更好地评估覆盖性，将监测区域简化成一个m×n的网格[8-10]，每个网格的面积为1。假设覆盖优化目标的位置为P j=(x j,y j),j∈{1,2,…,m·n}，如果P j与集合O中的任意一个节点的欧氏距离小于等于感知半径r，则认为该点已经被传感器覆盖，距离公式如下所示：
采用布尔模型作为概率感知模型，目标位置被感知的概率表示为：
在监测区域内，某一目标P j可能同时被多个传感器感知，其联合感知率定义为：
传感器覆盖率Pcov为节点O所覆盖的网格总数与所有网格的比值，其表达式为：
因此，本文优化传感器节点部署转换成用改进的哈里斯鹰优化算法求解Pcov的最大值问题。
哈里斯鹰优化算法（Harris Hawks Optimization Algorithm，HHO）[11]是一种根据哈里斯鹰觅食猎物的抓捕行为而研究出来的群智能优化算法。算法分为两个阶段，具体的过程描述如下。
2.1 勘探阶段
勘探阶段即全局搜索阶段，当||E≥1时，哈里斯鹰广泛且随机地栖息在搜索区域，以两种相同的概率随机地分布在搜索区域对猎物进行观察和监视。数学模型如下：
式中：X r(t)表示当前迭代种群中的一个随机个体；
Xrabbit(t)表示当前迭代种群的最优个体位置；
Xm(t)表示本次迭代的种群的平均位置；
N为种群的规模，q,r1,r2,r3,r4∈(0,1)；
LB表示搜索区间的下界，UB表示搜索区间的上界。
2.2 勘探阶段向开发阶段的转换
勘探阶段转向开发阶段由逃跑能量因子E来决定，计算方式如下：
式中：E0∈(-1,1)；
t表示当前迭代次数；
T表示最大迭代次数。
2.3 开发阶段
开发阶段即局部搜索阶段，当||E＜1时，哈里斯鹰发现猎物并对猎物形成一个包围圈准备抓捕猎物。由于猎物逃跑的方式不同，哈里斯鹰采取4种围攻策略对猎物进行抓捕，根据逃跑能量因子E和一个r∈(0,1)的随机数来决定采用哪种抓捕方式，具体狩猎行为如下。
方式1：软包围。当||E≥0.5&&r≥0.5时，猎物具有充足的能量试图跳跃出包围圈，但最终没能逃脱哈里斯鹰的包围，具体操作如下：
式中：ΔX表示当前迭代的最优个体与个体之间的位置差；
r5∈(0,1)；
J表示猎物在逃跑追捕过程中的跳跃程度。
方式2：硬包围。当||E＜0.5&&r≥0.5时，猎物已经成为囊中之物，没有逃跑的机会，哈里斯鹰采用硬包围方式捕获猎物，具体操作如下：
方式3：采用循序渐进式俯冲的软包围。当|E|≥0.5&&r＜0.5时，猎物有足够的能量逃脱包围圈，哈里斯鹰需要根据猎物的逃跑方式更换抓捕策略，采用更合理的抓捕方式袭击猎物，具体操作如下：
式中：D为求解问题规模维度；
S表示一个D维的随机向量；
LF表示莱维飞行算子；
υ,μ∈(0,1)；
β=1.5。
方式4：采用循序渐进性俯冲的硬包围。当|E|＜0.5&&r＜0.5时，猎物有逃跑的机会，但由于没有足够的能量逃跑，哈里斯鹰在袭击前将猎物围成一个硬包围圈，拉近与猎物之间的距离，具体操作如下：
3.1 算法特点分析
首先，算法在初始化种群的时候采用随机化的方式，导致有些个体可能会聚集在某一区域，错失了对其他区域信息的开采，使种群未能充分开采搜索区域更多的信息。其次，勘探阶段向开发阶段的转化是通过能量因子E控制，由式（7）可知，算法从刚开始迭代到前T/ 2次迭代时，逃跑能量因子|E|从2线性减小到1，从T/ 2次迭代到第T代时，逃跑能量因子|E|从1线性减小到0。根据勘探和开发的条件可知，算法在前T/ 2次迭代时执行全局搜索策略，在T/ 2次迭代后执行局部搜索策略，由于算法后期只对局部区域进行探索，导致算法容易陷入局部最优。最后，对猎物进行软围困和硬围困时，种群集中在当前最优值附近，随着算法迭代到后期，由于种群多样性的减少与种群间信息交流变少，导致算法容易早熟。基于以上三点不足分析，本文提出了相应的改进策略。
3.2 立方混沌映射初始化种群
初始解在解空间的分布对算法求解复杂优化问题具有重大的影响，初始种群如果在解空间能够随机且不重复地遍历所有状态，充分利用搜索区域的信息，这样能够有效提高算法的全局搜索能力，避免算法迭代后期由于种群多样性的减少陷入局部最优。混沌现象具有随机性、规律性、遍历性等特点，因此混沌算子常被用于种群初始化，由于立方混沌相比于Logistic具有更好的均匀性[12]，因此本文使用立方混沌对种群进行初始化。立方混沌算子公式如下所示：
首先，在n个d维的种群上，使用随机生成一个每维均在-1～1的d维向量y1作为第一个个体；
然后基于式（20），用迭代的方式依次生成剩余的（n-1）个个体；
最后把用立方混沌算子得到的数据通过下式映射到种群上：
式中：Xub,Xlb分别为搜索边界的上下界；
X i为个体变量。
立方混沌和随机分布的对比图如图1所示，由图1可知，立方混沌的分布更均匀。
图1 立方混沌和随机分布对比图
3.3 非线性逃跑能量因子
由式（7）可知，协调HHO算法的全局搜索和局部搜索是由逃跑能量因子决定。经过分析，种群迭代次数从1→T/ 2时，逃跑能量因子从2线性减少到1，期间算法执行全局搜索和局部搜索；
迭代次数从T/ 2→T时，逃跑能量因子从1线性减少到0，期间算法只执行局部搜索。但是哈里斯鹰追捕猎物的过程并非如此简单，原有线性递减的方式不能很好地模拟这一过程，因此，本文提出了一种新的非线性控制策略，公式如下：
根据式（22）及|E|的变化图可知：在迭代早期进行全局探索；
在迭代中期，能量因子变化缓慢，算法在全局和局部之前进行切换，更好地平衡了全局和局部搜索；
在迭代后期，算法在进行局部探索时，根据能量因子|E|的非线性变化随机地采用4种策略中的一个对猎物进行抓捕。非线性逃跑能量E的变化和对比图如图2、图3所示，从图中可知，当线性E只进行开发阶段时，非线性E1还保留勘探能力，动态地调节开发和探索阶段。
图2 E变化图
图3 逃跑能力因子E对比图
3.4 纵横交叉策略
在局部搜索阶段，由于哈里斯鹰在追捕猎物的过程中不断地向最优个体周围靠拢，使种群过度地聚集在“最优解”周围，导致算法的探索能力降低，使算法容易陷入局部最优。为防止算法过早的陷入早熟，可以加强个体之间的合作交流与信息的共享，增强种群的多样性。
为此，本文在软围困和硬围困搜索策略上引入了纵横交叉策略[13]。
1）横向交叉策略
横向交叉操作是对不同个体的相同维度进行交叉操作，其原理类似于遗传操作的交叉机制。针对哈里斯鹰在软围困时种群向最优解靠拢，易陷入局部最优的不足，本文采用横向交叉策略对哈里斯鹰的软围困位置进行更新操作，具体操作如下：
式中：r1,r2∈(0,1)，c1,c2∈[-1,1]；
H X ti,d,H X tj,d是由个体X ti,d和X tj,d经过横向交叉产生的新个体。
2）纵向交叉策略
在硬围困时，由公式（11）可知，种群集中在最优解附近，如果找到的解是局部最优，那么算法将陷入局部极值，无法找到全局最优值。算法“早熟”在一定情况下是由于有些个体在某一维度上陷入了局部最优，为此，本文引入纵向交叉策略算子，交叉策略原理类似于遗传算法中的变异操作，通过对个体的不同维度进行交叉运算。
假设对个体X ti,d的第d1和d2维进行纵向交叉操作产生后代个体，具体操作如下：
式中：H X ti,d是新产生的个体；
r∈(0,1)。基于贪婪选择，新产生个体需要同父代进行竞争，根据优胜劣汰法则保留适应度较高的个体。
4.1 基准测试函数
本文选取了6个基准测试函数进行测试，包含了3个单峰函数函数、3个多峰函数，将其测试结果与HHO、鲸鱼优化算法（Whale Optimization Algorithm，WOA）[14]、灰狼优化算法（Grey Wolf Optimizer，GWO）[15]、蝴蝶优化算法（Butterfly Optimization Algorithm，BOA）[16]、差分进化算法（Differential Evolution Algorithm，DE）[17]进行比较。为避免偶然性，每个算法对基准测试函数独立地运行30次，取最优值、最差值、平均值进行比较，平均值用于评判求解精度，标准差用来检验算法的鲁棒性能。设置种群规模为N=30，最大迭代次数T=500，测试函数如表1所示。
表1 测试函数
4.2 测试结果与分析
HHO、CCHHO、GWO、WOA、BOA、DE算法对6个基准测试函数的测试结果如表2所示，对求解效果高的算法进行加粗。收敛曲线图如图4所示。
图4 不同算法的收敛曲线对比图
由表2可知，CCHHO算法表现出了较强的求解精度。由图4可知，CCHHO算法的收敛速度比其他算法都快，求解精度也最高，验证了提出的改进策略的可行性和有效性。
表2 实验数据
利用CCHHO算法和文献[18-20]中三种不同的算法对相同条件下的WSN进行节点部署，对节点覆盖率进行对比分析，在相同的实验环境下进行实验研究。
5.1 算法参数设置
在实验中，种群规模N=30，最大迭代次数T=1 000，每组实验独立运行30次取平均覆盖率。
5.2 实测结果分析
5.2.1 实测1与文献[18]对比
设被监测区域的平面面积大小为S=30 m×30 m，将该区域离散成31×31个像素点，在区域内抛撒20个具有相同性质的传感器节点，感知半径r=5 m，通信半径R=10 m，实验结果如表3和图5、图6所示。
表3 CCHHO与HHO、ESCA的WSN节点覆盖率对比%
图5 CCHHO优化节点分布图
图6 CCHHO优化节点覆盖收敛曲线图
由表3可知：CCHHO对该区域传感器节点覆盖率相较于改进的正余弦算法（ESCA）在平均值、最优值和最差值上分别提高了0.31个百分点、0.11个百分点、0.37个百分点；
相较于HHO在平均值、最优值和最差值上分别提高了1.78个百分点、0.83个百分点、2.81个百分点。从平均覆盖收敛曲线可以看出，算法对节点部署具有跳出局部的能力。
5.2.2 实测2与文献[19]对比
设被监测区域平面面积大小为S=20 m×20 m，将该区域离散成21×21个像素点，在区域内抛撒24个具有相同性质的传感器节点，感知半径r=2.5，通信半径R=5，实验结果如表4和图7所示。
表4 CCHHO和DACQPSO的WSN节点覆盖率对比%
图7 CCHHO对不同节点优化部署（一）
由表4可知，CCHHO对WSN覆盖率相对于自适应混沌量子粒子群算法（DACQPSO）提高了4.16个百分点，当传感器个数V=22时，CCHHO对其覆盖率为87.44%，节省了2个传感器。
5.2.3 实测3与文献[20]对比
设被监测区域平面的面积大小为S=100 m×100 m，将该区域离散成101×101个像素点，在区域内抛撒50个具有相同性质的传感器节点，感知半径r=10 m，通信半径R=20 m，实验结果如表5和图8所示。
表5 CCHHO和EABC的WSN节点覆盖率对比%
图8 CCHHO对不同节点优化部署（二）
由表5可知：CCHHO对V=50和V=46时的节点覆盖率相对于外推人工蜂群算法（EABC）分别提高了8.02个百分点和7.09个百分点，且EABC在部署节点V=50和V=46时的覆盖率相同，说明算法陷入了局部最优；
CCHHO对节点V=36时的覆盖率比EABC对节点V=50时的覆盖率高了0.45个百分点，在覆盖率差不多的前提下节省了14个传感器。
针对在监测区域内随机部署节点导致节点分布不均匀，从而使WSN覆盖不全面的问题，本文提出一种基于哈里斯鹰优化算法的传感器网络覆盖优化方法。由于种群初始化的分布对算法寻优具有很大的影响，故采用立方混沌映射对种群进行初始化，使种群个体对搜索空间的信息进行全面的探索。采用非线性能量因子来平衡全局和局部搜索，在保留局部探索的情况下还能有一定的概率向全局搜索。针对迭代后期种群多样性减少，导致算法容易陷入局部最优的现象，引入了纵横交叉策略增强种群多样性。通过与HHO、WOA、GWO、BOA、DE算法对6个基准测试函数的实验数据及收敛曲线图对比，证明了CCHHO具有较快的收敛速度和较高的求解精度。最后，对WSN节点部署优化的仿真数据表明，相对于其他算法，CCHHO对WSN节点覆盖率有明显的提高，且在相同的覆盖率下，CCHHO算法能够节省传感器节点个数，说明本文提出的CCHHO对WSN节点部署具有较好的优化性能。
猜你喜欢哈里斯覆盖率猎物蟒蛇为什么不会被猎物噎死青少年科技博览（中学版）(2022年9期)2022-11-01民政部等16部门：到2025年村级综合服务设施覆盖率超80%今日农业(2022年15期)2022-09-20我国全面实施种业振兴行动 农作物良种覆盖率超过96%今日农业(2021年21期)2021-11-26可怕的杀手角鼻龙第二课堂(小学版)(2019年7期)2019-07-16霸王龙的第一只大型猎物金色少年(奇趣科普)(2017年1期)2017-03-03神奇的蝴蝶微型小说选刊(2016年3期)2017-01-18你是创业圈的猎人还是猎物中国科技信息(2016年12期)2016-08-29基于喷丸随机模型的表面覆盖率计算方法西南交通大学学报(2016年6期)2016-05-042015年湖南省活立木蓄积量、森林覆盖率排名前10位的县市区林业与生态(2016年2期)2016-02-27哈里斯中波广播发射机外部接口研究西部广播电视(2015年10期)2016-01-18 相关热词搜索：立方，分析研究，节点，
