基于混合鸡群优化算法的WSN节点部署优化.pdf
《基于混合鸡群优化算法的WSN节点部署优化.pdf》由会员分享,可在线阅读,更多相关《基于混合鸡群优化算法的WSN节点部署优化.pdf(11页珍藏版)》请在咨信网上搜索。
1、无线传感网络(W i r e l e s sS e n s o rN e t w o r k,WS N)技术,在节点随机部署的情况下,容易出现节点分布不均的问题.为了提高节点部署的覆盖率,提出了一种基于混合鸡群优化算法(H y b r i dC h i c k e nS w a r m O p t i m i z a t i o nA l g o r i t h m,HC S O)的WS N节点部署优化方法.首先为了平衡算法的全局搜索和局部搜索的能力,提出了一种自适应种群分配策略;其次,结合正余弦算法思想,改进了公鸡种群更新公式,提高其收敛速度和精度;最后,优化小鸡种群学习方式,使其不仅学习母
2、鸡,也向公鸡和最优个体学习,提高小鸡粒子的质量.将HC S O算法在基准函数上测试,实验结果表明,本算法比其他算法的法收敛精度提高了1 0%,收敛速度均比原算法提高了0.0 50.1 0s.最后将HC S O算法应用于WS N节点部署优化中,结果表明所提出的方法所得到的覆盖率高于其他算法,提高了0.21 3.1个百分点,充分证明了基于HC S O算法的WS N节点部署优化方法的优越性.关键词:无线传感网络;节点部署;鸡群优化算法;自适应分配;正余弦算法中图分类号:T P 1 8文献标志码:A无线传感网络(WS N)是由一组轻量级、自主的空间分布节点组成,这些节点相互协调,形成一个感知特定应用任
3、务的通信网络1,具有成本低,适应度高等特点.随着科技的不断发展,科学家对于WS N的研究也越来越多,并已经应用到许多领域,如:路径调度目标跟踪、灾难预警和可穿戴设备2等.其中WS N的覆盖率问题是关键问题也是难点之一,覆盖率的大小反映了WS N网络的性能以及效率的好坏.在传统WS N网络中,传感器的部署位置大多是采用随机抛撒进行决定的,通过这种方法部署的网络容易出现节点分布不均的问题,使得一部分空间内的节点密度过高,从而导致网络的覆盖率降低,传感速度和效率变差.而解决这一问题就需要对节点部署方法进行优化.随着群智能优化算法的出现,如:教与学优化算法(T e a c h i n g-l e a
4、r n i n g-b a s e dO p t i m i z a t i o n,T L B O)3,麻雀搜索算法(S p a r r o wS e a r c hA l g o r i t h m,S S A)4,旗鱼优化算法(S a i lF i s hO p t i m i z e r,S F O)5等.近年来,群智能优化算法的研究人员越来越多,由于这类优化算法对于解决寻优问题有着显著的优点,许多国内外学者将群智能优化算法融到WS N节点部署优化中,如:M I AO等6等将增强层次结构的灰狼优化算法应用其中,D E E P A等7提出了利用L v y飞行增强的鲸鱼优化算法,并应用到W
5、S N覆盖优化中,并将KNN(K-N e a r e s tN e i g h b o r,KNN)变体整合到WS N中,得到了效率更高、收敛度更好的覆盖优化方法.宋明智等8等提出了改进虚拟力-粒子群算法于WS N节点随机部署中的应用,最终实验表明其提出的方法覆盖率较其他优化算法有3%5%的提升.虽然,将群智能优化算法运用到WS N节点部署优化中能使其覆盖率有一定的提升,但使用基本算法所得到的结果仍然还有许多不足,故这些算法还有许多可以提升和改进的空间.为了获得更好的WS N网络性能,还需要进一步开拓群智能优化算法的能力,更好地改善WS N节点部署优化问题,提高覆盖率.鸡群优化算法(C h i
6、 c k e nS w a r mO p t i m i z a t i o n,C S O),于2 0 1 4年由ME NG等9提出,该算法作为群智能优化算法中的一员,一经提出就备受研究人员及学者关注.目前C S O算法及其改进算法已经应用到了光伏发 收稿日期:2 0 2 2-0 6-2 1;修回日期:2 0 2 2-0 7-2 1.基金项目:国家自然科学基金(6 2 2 6 6 0 0 7;6 1 6 6 2 0 0 5);广西自然科学基金(2 0 2 1 G X N S F AA 2 2 0 0 6 8;2 0 1 8 G X N S F A A 2 9 4 0 6 8).作者简介(通信
7、作者):韦修喜(1 9 8 0-),男,广西百色人,广西民族大学副教授,博士,研究方向为机器学习、计算智能,E-m a i l:w e i x i u x i 1 6 3.c o m.电1 0,电动汽车充电站规划1 1,电网控制1 2等领域中,但应用到WS N节点部署优化的案例还不是很成熟,因此这一方向具有一定的研究意义.并且,WU等1 3根据随机搜索算法的收敛准则,证明C S O算法满足两个收敛准则,保证了全局收敛性,但也指出了该算法的不足.由于算法的学习方法等原因,导致该算法在收敛速度和收敛精度上有所损失,同时易过早陷入局部最优解,因此C S O算法还有许多提升的空间.故D E B等1 4
8、等将T L B O算法与C S O算法相结合,提出了一种基于教与学算法的鸡群优化算法.L I ANG等1 5提出了一种改进C S O算法用于机器人路径寻优,该算法引入了具有L v y飞行特性的搜索策略和非线性递减策略,寻找到了较好的路径.虽然已经有许多学者和专家对C S O算法的改进和应用进行了大量的研究,但仍有许多开发的空间.针对上述不足,本文提出了一种混合鸡群优化算法(HC S O)用于WS N节点部署优化的应用.1 W S N节点部署优化概念与模型1.1 问题假设假设WS N里面的每个节点对应一个传感器,传感器的覆盖范围都是半径固定的圆.假设每个传感器都可以实时感受到其感知半径内的其他传
9、感器位置,并且所有的传感器的结构都是相同,这样就可以将WS N节点覆盖优化问题看为一个二维问题.若整个监测区域划为MN个像素,如果WS N网络能够覆盖x个像素点,则覆盖率为xMN.1.2 节点覆盖模型设监测区域内分布有N个传感器节点,每个节点的感知半径为r,通信半径为R,并且满足2rR.设T=t1,t2,tN,其中ti为第i个传感器,其位置坐标表示为(xi,yi),若第j个像素点为hj,其位置坐标为(xj,yj).则任意像素点与传感器之间的欧氏距离可用式(1)来表示:d(ti,hj)=(xi-xj)2+(yi-yj)2.(1)对于传感器与像素点的感知概率,本文使用二元感知模型进行建模,如式(2
10、)表示:p(ti,hj)=1,d(ti,hj)r,0,d(ti,hj)r,(2)其中p(ti,hj)为感知概率,r为传感器的感知半径,若p(ti,hj)为1则表示像素点hj被传感器ti所覆盖,反之则没有被覆盖.在整个监测范围中,会出现同一个像素点被不同的多个传感器同时感应到的现象,故需要进行联合感知概率的计算.像素点与多个传感器的联合感知概率如式(3)所展示:p(T,hj)=1-tiT(1-p(ti,hj),(3)其中p(T,hj)为联合感知概率.最终,覆盖率由式(4)求出:pc o v=MNj=1p(T,hj)MN,(4)其中pc o v表示为覆盖率.综上所述,式(4)为HC S O应用到W
11、S N节点部署优化的适应度函数,其目标为提高pc o v数值.2 鸡群优化算法C S O算法是通过观察鸡群的等级秩序以及鸡群的觅食行为而提出的.该算法中设置有公鸡、母鸡、小鸡3种等级不同的群体.其中公鸡群体的适应度最优,是其子群的领导者.小鸡群体的适应度最差,是种群中的弱势群体.剩下的粒子则为母鸡种群.假设整个鸡群中总共有N只鸡,则xti,j为第t次迭代中,第i只鸡在第j(j(1,D),D为解的维度)维度上的位置.85河南师范大学学报(自然科学版)2 0 2 3年公鸡为适应度较好的前NR只鸡,根据上述表示方法,公鸡的位置更新公式为:xt+1i,j=xti,j1+N(0,2),(5)2=1,fi
12、fk,e x p(fk-fi|fi|-),fifk,k1,NR,k1,(6)其中xt+1i,j为下一次迭代中第i只鸡在第j维度上的位置;N(0,2)代表均值为0,方差为2的正态分布;k与i均代表一只公鸡,且k与i不相等,公鸡的适应度值分别由fi和fk对应;为计算机中最小的常数,保证了式子分母不为零,防止出现错误.NH代表母鸡的总数,母鸡的适应度适中,母鸡的位置更新公式如下所示:xt+1i,j=xti,j+S1R1(xtr1,j-xti,j)+S2R2(xtr2,j-xti,j),(7)S1=e x p(fi-fr1a b s(fi)+),(8)S2=e x p(fr2-fi),(9)其中,R1
13、和R2均为0,1 的随机数;r1为与母鸡同一子群的公鸡;r2为另一只随机选取的鸡,且r2i,r2r1,fr2fi.适应度最差的个体将被划分为小鸡种群,NC代表种群中小鸡的个数.由于小鸡是种群中的弱势群体,故指定其只能跟随鸡妈妈进行觅食.式(1 0)展示了这一现象的位置更新公式:xt+1i,j=xti,j+F L(xtm,j-xti,j),(1 0)其中xtm,j表示鸡妈妈的位置,F L表示小鸡跟随其鸡妈妈的调节参数,通常为0,2上的随机数.3 混合鸡群优化算法3.1 自适应种群分配C S O算法是一个全局算法,为了加强其后期的局部搜索能力,本文加入了自适应种群分配策略.该策略使前期公鸡种群的粒
14、子个数增加,随着迭代的过程,慢慢减少;而母鸡种群的粒子个数与之相反,是处于慢慢增加的状态.由于每G次迭代C S O会重新规划一次种群秩序,故种群数量的改变也是每G次进行一次.该策略的具体实现方法如式(1 1)所示:PR=C1t a n(4-t4T)+PRm i n,PH=C2t a n(4-t4T)+PHm a x,PC=1-PR-PH,PRPH,(1 1)其中PR,PH,PC分别代表每一个种群个体数量占鸡群总数量的百分比;t代表当前迭代次数;T代表最大迭代次数;C1,C2用来控制每次迭代种群个体数量百分比增长或减小的速度;PRm i n用来控制最终公鸡的数量比;PHm a x用来控制母鸡的最
15、终数量比,经实验测试PRm i n和PHm a x的取值与基本C S O算法的公鸡和母鸡占比数相同时算法的性能最优.3.2 融合正余弦思想的公鸡位置更新优化由于C S O算法中公鸡位置更新方法只是基于正态分布的变异方法,当算法的种群多样性变低时,会导致公鸡种群的个体难以跳出局部最优,从而使算法效率变慢,收敛精度变低.本文引入正余弦算法(S i n eC o-s i n eA l g o r i t h m,S C A)1 6的思想来优化公鸡位置更新公式,具体方法如下:xt+1i,j=xti,j+2r1s i n(r2)|r3ptj-xti,j|,r40.5,xti,j+2r1c o s(r2)
16、|r3ptj-xti,j|,r40.5,(1 2)95第5期 韦修喜,等:基于混合鸡群优化算法的WS N节点部署优化r1=a(1-tT),(1 3)其中r1控制迭代方向,r2控制移动距离,r3控制最优解的影响力,r4用来选择使用正弦还是余弦更新位置;r20,2 ,r30,2,r40,1且都为随机数;ptj为第t次迭代中第j维的最优解;a为正常数.3.3 改进小鸡更新思想由于C S O算法中,小鸡向其母亲学习,若其母亲陷入局部最优解,小鸡也会随之学习,从而降低算法整体的效率.故本文使小鸡向其双亲学习,并增加突变的可能,学习全局最优个体.引进随机交叉变异思想,改进后的小鸡位置更新公式如下:xt+1
17、i,j=F Lxti,j+(1-F L)(Q(xtm,j-xti,j)+(1-Q)(xtr,j-xti,j),r0.5,F Lxti,j+(1-F L)(Q(xtm,j-xti,j)+(1-Q)(ptj-xti,j),r0.5,(1 4)=t3T3,(1 5)其中F L0,2 为随机交叉变异的调节参数;Q是-1,1 的随机数,该参数为学习调控因子,能够同时调控两边的学习力度;是一个自适应权重系数;r为0,1之间的随机数,控制小鸡是否发生突变.改进后的小鸡更新位置公式使小鸡能够更好地跳出局部最优解,提高适应度,提高算法的效率.3.4 H C S O节点部署优化流程步骤1 初始化WS N节点参数和
18、HC S O算法参数,如:节点个数N,感知半径r,粒子个数p o p,最大迭代次数等.步骤2 初始化粒子位置,并使用式(1)(4)计算覆盖率.步骤3 判断m o d(t,G)是否为1,是则根据式(1 1)进行种群规划;否则进行步骤4.步骤4 每个粒子根据其被划分的种群,按照式(7)(9),式(1 2)(1 5)进行位置更新.步骤5 算法若到最大迭代次数,则输出优化后的覆盖率等结果;算法若没达到最大迭代次数,跳至第3步进行下一次的迭代.3.5 复杂度分析假设种群中总粒子数量为N,公鸡数量为NR,小鸡数量为NC,解空间维度为D,T为最大迭代次数.HC S O引入了自适应种群分配策略,每G次更改一次
19、种群比例,则计算种群百分比的时间复杂度为O(T/G);改进后的公鸡位置更新公式时间复杂度为O(NRDT);修改了小鸡的学习策略,其时间复杂度为O(NCDT),本算法的时间复杂度与原算法相同.4 仿真实验设计与分析4.1 基准函数测试4.1.1 实验设计为了验证HC S O算法的有效性,本文选取了6个具有代表性的基准测试函数,其中函数f1为简单的单峰函数,能够测试算法的收敛速度;函数f2为高维单峰函数,能够测试算法的收敛精度和收敛速度;函数f3是不连续阶梯函数,该函数能够对算法的有效性进行测试;函数f4f6为3个不同的多峰函数,能够很好地检验算法的全局搜索能力.通过这些函数对HC S O进行测试
20、,并与P S O1 7,C S O,S C A,GWO1 8,I C S O1 5进行结果对照及分析,表1中给出了函数的具体表达式.每个算法在其搜索空间中共有3 0个粒子进行搜索,单独在6个基准函数上运行3 0次(每次迭代10 0 0次)所统计出来其优化结果进行比较.各算法的具体参数设计如表1所示,基准函数表达式如表2所示.4.1.2 测试结果分析图1、图2为每个算法在f1f6的函数收敛图和箱线图,附表为每个算法在f1f6单独运行3 0次(每次迭代10 0 0次)所统计出来的数据表.通过3种不同的展示方法可以明显看出,HC S O与原算法相比,收敛精度、收敛速度和跳出局部最优能力都有提高.06
21、河南师范大学学报(自然科学版)2 0 2 3年表1 算法参数表T a b.1 A l g o r i t h mp a r a m e t e r t a b l e算法名称参数设置P S Oc1=c2=1.5,=0.8C S ONR=0.1 5N,NH=0.7N,NM=0.5NH,NC=N-NR-NH,G=1 0,F0,2S C Ar2=0,2 ,r30,2,r40,1GWOr10,1,r20,1I C S ONR=0.1 5N,NH=0.7N,NM=0.5NH,NC=N-NR-NR,G=1 0,F0,2HC S OG=1 0,F0,2,Prm i n=0.1 5,Phm a x=0.7,C
22、1=1 3,C2=-8表2 基准函数表T a b.2 B e n c h m a r kf u n c t i o nt a b l e基准函数范围维度最优值f1(x)=Di=1x2ixi-1 0 0,1 0 03 00f2(x)=Di=1|xi|+Di=1|xi|xi-1 0,1 03 00f3(x)=Di=1(|xi+0.5|)2xi-1.2 8,1.2 83 00f4(x)=Di=1x2i-1 0 c o s(2 xi)+1 0 xi-5.1 2,5.1 23 00f5(x)=-2 0 e x p(-0.21nDi=1x2i)-e x p(1nDi=1c o s(2 xi)+2 0+ex
23、i-3 2,3 23 00f6(x)=140 0 0Di=1(x2i)-Di=1c o s(xii)+1xi-6 0 0,6 0 03 00 在单峰测试函数,图1(a-c)中可以看到虽然本算法没有优化到理想最优值,但相较于其他算法,HC S O的精度都是最好的.GWO虽然能快速地收敛,但都陷入了局部最优.附表中黑体部分为HC S O运算结果,可以看出P S O和S C A运行速度非常快,但他们的精度却不高,虽然HC S O的运行速度总体比P S O和S C A16第5期 韦修喜,等:基于混合鸡群优化算法的WS N节点部署优化的运行速度慢,但这是由C S O算法本身的结构造成的,HC S O已经
24、比其原算法有所减少.故本算法对于单峰函数优化起到了比较好的效果.在多峰函数测试中,可以在箱线图中看出,HC S O是最稳定的,且没有离群值.对于函数f4和f5,HC-S O已经找到了理论最优值,并且十分稳定.附表中可以看到其平均值和标准差都是0,说明独立运行的3 0次每次都能找到局部最优.虽然其他算法也能够找到,但是并不稳定.在图1(d)和图1(f)中可以看到,HC S O几乎在不到1 0 0次迭代就可以找到理论最优值,故其收敛速度也很优秀.因此可以看出,HC S O对于多峰函数的优化也很出色,其收敛速度和精度都有大幅度提高,并且稳定性较好.由图2的算法箱线图可以看出,改进后的HC S O算法
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 混合 优化 算法 WSN 节点 部署
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。