基于混合策略麻雀搜索算法的WSN覆盖优化_陈立万.pdf

电 子 测 量 技 术E L E C T RON I CME A S U R EME N TT E CHNO L O G Y第4 5卷 第2 3期2 0 2 2年1 2月 D O I:1 0.1 9 6 5 1/j.c n k i.e m t.2 2 1 0 1 9 9基于混合策略麻雀搜索算法的W S N覆盖优化*陈立万1 赵尚飞2 曾 蝶2 欧 俊2 崔 浩2(1.重庆三峡学院教师教育学院 重庆 4 0 4 1 2 0;2.重庆三峡学院电子与信息工程学院 重庆 4 0 4 1 2 0)摘 要:为了有效提高无线传感器网络的节点覆盖率,提出了一种基于混合策略麻雀搜索算法的WS N优化算法。利用T e n t混沌映射初始化麻雀种群,增加种群的多样性;再用反向学习策略生成反向解扩大搜索范围,提高算法全局的搜索能力;加入惯性因子选择对预警麻雀个体进行L e v y策略更新,提高算法局部搜索能力;对最优麻雀位置进行随机游走扰动进一步提高局部的搜索能力。仿真结果显示,H S S S A算法使节点分布更加均匀,覆盖率有明显提高。关键词:无线传感器网络;麻雀搜索算法;优化策略;覆盖率中图分类号:T P 3 9 3 文献标识码:A 国家标准学科分类代码:5 1 0.1 0 5 0W S N c o v e r a g e o p t i m i z a t i o n b a s e d o n h y b r i d s t r a t e g y s p a r r o w s e a r c h a l g o r i t h m C h e n L i w a n1 Z h a o S h a n g f e i2 Z e n g D i e2 O u J u n2 C u i H a o2(1.T e a c h e r S c h o o l o f E d u c a t i o n,C h o n g q i n g T h r e e G o r g e s U n i v e r s i t y,C h o n g q i n g 4 0 4 1 2 0,C h i n a;2.S c h o o l o f E l e c t r o n i c a n d I n f o r m a t i o n E n g i n e e r i n g,C h o n g q i n g T h r e e G o r g e s U n i v e r s i t y,C h o n g q i n g 4 0 4 1 2 0,C h i n a)A b s t r a c t:I n o r d e r t o e f f e c t i v e l y i m p r o v e t h e n o d e c o v e r a g e o f w i r e l e s s s e n s o r n e t w o r k s,a n e t w o r k c o v e r a g e o p t i m i z a t i o n a l g o r i t h m b a s e d o n h y b r i d s t r a t e g y s p a r r o w s e a r c h a l g o r i t h m i s p r o p o s e d.F i r s t l y,t h e T e n t c h a o t i c m a p p i n g i s u s e d t o i m p r o v e t h e i n i t i a l i z a t i o n s p a r r o w p o p u l a t i o n a n d i n c r e a s e t h e d i v e r s i t y o f t h e p o p u l a t i o n;R e v e r s e l e a r n i n g s t r a t e g y i s u s e d t o g e n e r a t e i n v e r s e s o l u t i o n s t o e x p a n d t h e s e a r c h r a n g e a n d i m p r o v e t h e g l o b a l s e a r c h c a p a b i l i t y;T h e n t h e i n e r t i a f a c t o r i s a d d e d t o s e l e c t L e v y s t r a t e g y a n d u p d a t e t h e s p a r r o w p o s i t i o n t o i m p r o v e t h e l o c a l s e a r c h a b i l i t y o f t h e a l g o r i t h m;F i n a l l y t h e o p t i m a l s p a r r o w p o s i t i o n i s p e r t u r b e d b y r a n d o m w a l k s t r a t e g y t o f u r t h e r i m p r o v e t h e l o c a l s e a r c h c a p a b i l i t y.T h e s i m u l a t i o n r e s u l t s s h o w t h a t H S S S A a l g o r i t h m r e s u l t e d i n a m o r e u n i f o r m d i s t r i b u t i o n o f n o d e s a n d a s i g n i f i c a n t i m p r o v e m e n t i n c o v e r a g e r a t e.K e y w o r d s:WS N;S S A;o p t i m i z a t i o n s t r a t e g i e s;c o v e r a g e r a t e 收稿日期:2 0 2 2-0 6-0 3*基 金 项 目:重 庆 市 教 委 科 学 技 术 研 究 项 目(K J QN 2 0 2 1 0 1 2 3 3,K J QN 2 0 2 0 0 1 2 2 9)、重 庆 市 人 工 智 能+智 慧 农 业 学 科 群 开 放 基 金(Z NNYK F B 2 0 1 9 0 1)、重庆市三峡库区地质环境监测与灾害预警重点实验室开放基金(MP 2 0 2 0 B 0 2 0 2)项目资助0 引 言 无线传感器网络(w i r e l e s s s e n s o r n e t w o r k s,WS N)由能够进行传感、处理和无线通信的传感器节点组成1-3。多年来无线传感器网络随着科技的发展越来越备受关注,由于WS N大多随机部署在偏远地区或者恶劣环境条件下,造成节点冗余,无法实现网络监测区域的充分覆盖4。网络区域覆盖优化一直以来都是WS N研究中 热点。近年来,智能优化算法对于N P-h a r d难点问题的解决越来越备受关注。随着启发式群体智能优化算法在WS N覆盖优化方面得到了很好地应用。如L e i等5提出了将反向学习策略方法加入基本的鲸鱼算法中,其改进后的算法收敛很好,但稳定性较差,造成节点能耗加剧;胡小平等6提出了几种策略改进灰狼优化算法,虽然算法性能和覆盖效果上有所提升,但与其他优化 算 法 不 具 备 优 势;Z h o u等7提出蜘蛛优化算法来优化传感器节点的部署,虽然有效提高检测区域的覆盖率,但算法的覆盖性有待进一步的提升。张春雨等8提出了主成布谷鸟算法优化无线传感器网络优化,虽然很大程度提升了网络覆盖范围,但是监测区域存在较大的节点冗余。以上文献表明启发式改进群智能优化算法可以优化网络区域覆盖,但优化效果存在不足,可以进一步改善。2 0 2 0年 一 种 新 型 的 智 能 优 化 算 法 麻 雀 搜 索 算 法(s p a r r o w s e a r c h a l g o r i t h m,S S A)被X u e等9提出。该算471 陈立万 等:基于混合策略麻雀搜索算法的WS N覆盖优化第2 3期法主要模拟麻雀生活觅食行为和反捕食行为进行数学建模。该基本算法具备很多优点,参数少,结构简单等。该算法已被广泛应用于无人机航路规划1 0,聚合物电解质燃料电池堆辨识参数优化1 1、肿瘤诊断算法检测能力提升等许多工程领域。由于S S A算法存在早熟且精度不高,易陷入局部最优等缺点。考虑到混沌映射策略可以提高种群的多样性,莱维飞行策略和随机游走策略对局部搜索能力的进一步增强。结合以上分析,本文提出一种基于混合策略麻雀搜 索 算 法(h y b r i d s t r a t e g y s p a r r o w s e a r c h a l g o r i t h m,H S S S A)来优化区域覆盖。该算法通过混沌映射和反向学习生成新的初始化种群;引入L e v y飞行策略,避免易陷入局部极值的情况;基于游走策略对最优值扰动,提高了算法全局搜索和局部探索能力。最后,基于基准函数测试算法性能和节点的覆盖优化应用。1 覆盖模型 在监测区域M内,设每个传感器节点具有相同的感知半径r,每个传感器节点覆盖范围是以r为半径的圆形区域。将监测区域离散为L1W1个待覆盖的网格,各个网格中心为覆盖目标,其集合为P(x,y),若第j个覆盖目标点PJ与任一传感器节点距离不大于节点监测半径,则认为位置被传感器覆盖。网络监测区域内多个传感器节点集合为S=s1,s2,sN,第i个传感器节点si的位置(xi,yi),si与覆盖目标点距离为:d(si,pj)=(xi-x)2+(yi-y)2(1)其中,所有节点在监测区域内 L(si)M。使用布尔感知模型,对目标点监测概率为:Cx,y=1,d(si,pj)r0,其他(2)监测区域内目标点可以被多个传感器节点同时检测,则对目标点的联合测量概率为:Cx,y(so v,pj)=1-siso v1-Cx,y(si,pj)(3)式中:so v为整体监测传感器集合。所有节点对待检测区域的覆盖率为:Cr=L1x=1W1y=1Cx,y(so v,pj)L1W1(4)因此,将式(4)作为改进麻雀搜索算法求解WS N覆盖优化问题的目标函数,求Cr最大覆盖率。2 基于混合策略的麻雀搜索算法2.1 麻雀搜索算法 麻雀搜索算法1 2由3种担任不同角色的麻雀组成:生产者、伴随者和侦察者。首先生产者作为向导为种群觅食提供区域和方向,其适应度值较高,更容易存活下去。其次伴随者紧密跟随生产者觅食,以保证自己捕食率的同时继续存活下去。侦察者扮演着警戒外来危险的角色,一旦发现捕食者后立即发出报警信号,使得整个种群飞离该危险区域向更安全的区域继续觅食。麻雀集合矩阵如下:X=x1,x2,xNT,xi=xi,1,xi,2,xi,d(5)式中:N是麻雀的规模,i=1,2,N,d是变量的维数。麻雀的适应度值矩阵表示如下:Fx=f(x1),f(x2),f(xN)T,f(xi)=f(xi,1),f(xi,2),f(xi.d)(6)其中,N是表示麻雀数量,而FX中的每个值表示个体的适应度值。1)生产者的位置更新公式如下:Xi,j(t+1)=Xi,j(t)e x p-iT(),R2N2Xb e s t j(t+1)+|Xi j(t)-Xb e s t j(t+1)|A+L,iN2 (8)其中,Xw o r s t(t)表示当前全局最差位置,Xi,j(t)表示生产者占据的最佳位置,A+=AT(A AT)-1,A为1d矩阵,AT为A的转置。3)侦察者的数量占