差分进化花朵授粉算法的WSN节点部署策略_常宇飞.pdf

第2卷 第1期V o l.2 N o.1 2 0 2 3年2月 J o u r n a l o f A r m y E n g i n e e r i n g U n i v e r s i t y o f P L A F e b.2 0 2 3差分进化花朵授粉算法的W S N节点部署策略常宇飞1,李重阳1,张爱军1,宋彬杰2(1.3 2 1 5 3部队,河北 张家口 0 7 5 1 0 0;2.陆军炮兵防空兵学院,河南 郑州 4 5 0 0 0 2)摘要:针对无线传感器网络(w i r e l e s s s e n s o r n e t w o r k,WS N)的节点部署问题,提出了一种基于差分进化算法(d i f f e r e n t i a l e v o l u t i o n a l g o r i t h m,D E A)优化的花朵授粉算法(f l o w e r p o l l i n a t i o n a l g o r i t h m,F P A):D E-F P A。设计了动态转换概率,自适应平衡全局授粉和局部授粉间的相互转换,提高算法全局搜索能力。优化了全局授粉过程中的步长缩放因子,进一步提高算法收敛速度。为避免算法陷入局部极值,在每次全局授粉或者局部授粉迭代后引入差分进化策略,增加种群多样性,提高了算法搜索能力。实验结果表明,D E-F P A收敛速度快、寻优精度高,能够在网络连通的约束条件下,达到较高的网络覆盖率。关键词:无线传感器网络;差分进化算法;花朵授粉算法;网络覆盖率 中图分类号:T P 3 0 1.6D O I:1 0.1 2 0 1 8/j.i s s n.2 0 9 7-0 7 3 0.2 0 2 2 0 7 0 3 0 0 1S t r a t e g y o f WS N N o d e D e p l o y m e n t B a s e do n D i f f e r e n t i a l-E v o l u t i o n F l o w e r-P o l l i n a t i o n A l g o r i t h m CHANG Y u f e i1,L I C h o n g y a n g1,Z HANG A i j u n1,S ONG B i n j i e2(1.U n i t 3 2 1 5 3 o f P L A,Z h a n g j i a k o u 0 7 5 1 0 0,C h i n a;2.A r m y A r t i l l e r y&A i r D e f e n s e A c a d e m y,Z h e n g z h o u 4 5 0 0 0 2,C h i n a)A b s t r a c t:A i m i n g a t t h e p r o b l e m o f t h e n o d e d e p l o y m e n t o f w i r e l e s s s e n s o r n e t w o r k(WS N),t h e D E-F P A,a n o p t i m i z e d f l o w e r p o l l i n a t i o n a l g o r i t h m(F P A)b a s e d o n d i f f e r e n t i a l e v o l u t i o n a l g o r i t h m(D E A),i s p r o p o s e d.F i r s t l y,t h e o p t i m i z e d a l g o r i t h m d e s i g n e d t h e d y n a m i c s e l f-a d a p t i v e c o n v e r s i o n p r o b a b i l i t y t o b a l a n c e t h e m u t u a l c o n v e r s i o n b e t w e e n t h e g l o b a l p o l l i n a t i o n a n d t h e l o c a l p o l l i n a t i o n s o a s t o i m p r o v e t h e g l o b 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.S e c o n d l y,t h e s t e p-s i z e s c a l i n g f a c t o r i n t h e g l o b a l p o l l i n a t i o n p r o c e s s w a s o p t i m i z e d t o f u r t h e r i m p r o v e t h e a l g o r i t h m c o n v e r g e n c e s p e e d.F i n a l l y,i n o r d e r t o p r e v e n t t h e a l g o r i t h m f r o m e a s i l y f a l l i n g i n t o t h e l o c a l e x t r e m e v a l u e,t h e s t r a t e g y o f d i f f e r e n t i a l e v o l u t i o n w a s i n t r o d u c e d a f t e r e v e r y g l o b a l p o l l i n a t i o n o r l o c a l p o l l i n a t i o n i t e r a t i o n t o 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 a n d i m p r o v e t h e a l-g o r i t h m s s e a r c h a b i l i t y.T h e e x p e r i m e n t a l r e s u l t s s h o w t h a t t h e D E-F P A a l g o r i t h m h a s h i g h e r n e t w o r k c o v e r a g e u n d e r t h e c o n s t r a i n t s o f n e t w o r k c o n n e c t i v i t y,w i t h a f a s t c o n v e r g e n c e s p e e d a n d h i g h o p t i m i z a t i o n a c c u r a c y.K e y w o r d s:w i r e l e s s s e n s o r n e t w o r k(WS N);d i f f e r e n t i a l e v o l u t i o n a l g o r i t h m(D E A);f l o w e r p o l l i n a-t i o n a l g o r i t h m(F P A);n e t w o r k c o v e r a g e 收稿日期:2 0 2 2-0 7-0 3第一作者:常宇飞,助理讲师,主要研究物联网和模糊系统,2 0 1 7 2 0 1 3 9 9 6 8m a i l.s c u t.e d u.c n。通信作者:李重阳,助理讲师,主要研究物联网,7 8 5 3 7 2 2 6 4q q.c o m。无 线 传 感 器 网 络(w i r e l e s s s e n s o r n e t w o r k,WS N)由数量众多、性能有限、能量受限的微型传感器组成1,具有很好的交互性和自组性,能够以协作方式完成信息的感知、融合和传输。物联网时代,WS N技术极大改善了人与自然环境的交互方式,已经渗透到国防军事、生态环境监测、智能家居、智慧城市等应用领域2,正成为当今时代最重要的一项关键技术。传感器节点部署研究是WS N技术发展的基础研究工作之一。根据环境和场景的不同要求,节点部署通常采用随机部署和固定部署两种方式3。部署策略直接影响到WS N的整体覆盖率和连通性,同时决定了感知数据的完整性和准确性。因此,在保证网络连通性的前提下,覆盖率成为评价WS N的一项重要指标。随着群智能算法在优化问题中的优秀表现,近些年来学者们已经将群智能算法应用在WS N节点部署优化,如粒子群算法(p a r t i c a l s w a r m o p t i m i z a-t i o n,P S O)4、蛙跳算法(s h u f f l e d f r o g l e a p i n g a l g o-r i t h m,S F L A)5、蝴蝶算法(b u t t e r f l y o p t i m i z a t i o n a l g o r i t h m,B OA)6、灰 狼 算 法(g r e y w o l f o p t i m i-z e r,GWO)7、萤 火 虫 算 法(f i r e f l y a l g o r i t h m,F A)8等。文献9 提出混合粒子群-蝴蝶算法,采用自适应调节策略控制参数,提高了算法全局寻优能力,但收敛速度较慢。文献1 0 提出一种基于萤火虫算法的WS N节点重部署,有效均衡了网络中节点能耗。文献1 1 提出了基于蛙跳算法的WS N节点重部署,采用全局信息交换和子群局部搜索相结合的策略。文献1 2 提出了改进多目标蚁狮算法的WS N节点部署策略,提高了检测区域的覆盖率与连通性,但存在收敛精度不高的缺陷。花朵授粉算法(f l o w e r p o l l i n a t i o n a l g o r i t h m,F P A)是一种启发式搜索算法1 3。F P A结构简化,具有良好的收敛速度和寻优能力,被广泛应用于目标优化问题。为提高WS N网络节点覆盖率,提出一种差分进化改进的花朵授粉算法D E-F P A,主要改进体现在:(1)设计自适应动态转换概率,以平衡全局授粉和局部授粉相互转换,提高算法的全局搜索能力;(2)优化全局授粉的步长缩放因子,提高算法收敛速度;(3)在每次全局授粉或者局部授粉迭代后引入差分进化策略,避免花朵授粉算法陷入局部极值,提高算法求解精度。1 系统模型1.1 节点模型假设WS N监测区域为L1L2二维平面结构,在该区域内随机部署N个传感器节点,节点集S=s1,s2,sN。节点的感知半径和通信半径分别用Rs和Rc表示,通常Rc2Rs。假设节点为同构传感器,即所有节点的感知半径和通信半径分别一致。为便于计算,将监测区域离散为L1L2个面积相等的单位网格,每个方格的几何中心点代表监测目标点位置,监测点集表示为M=m1,m2,mL1L2。1.2 感知模型本文采用布尔感知模型1 4来计算监测区域的覆盖情况,布尔感知模型定义为f(si,mj)=1d(si,mj)Rs0其他(1)式中:d(si,mj)表示节点si与监测点mj间的欧式距离。其计算方式为d(si,mj)=(xi-xj)2+(yi-yj)2(2)式中:(xi,yi)、(xj,yj)分别表示节点si和监测点mj的横纵坐标。监测点可以同时被多个节点覆盖,每个监测点的联合感知概率定义为C S,mj()=1-Ni=1(1-f(si,mj)(3)根据式(3)计算所有监测点的联合感知概率和,即监测区域的覆盖面积,因此WS N网络整体覆盖率J表示