改进的麻雀搜索算法优化无线传感器网络覆盖 段锦.pdf

该【改进的麻雀搜索算法优化无线传感器网络覆盖 段锦 】是由【彩霞】上传分享，文档一共【12】页，该文档可以免费在线阅读，需要了解更多关于【改进的麻雀搜索算法优化无线传感器网络覆盖 段锦 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:.
吉林大学学报(工学版)
JournalofJilinUniversity(EngineeringandTechnologyEdition)
ISSN1671-5497,CN22-1341/T
《吉林大学学报(工学版)》网络首发论文
题目:改进的麻雀搜索算法优化无线传感器网络覆盖
作者:段锦,姚安妮,王震,于林韬
网络首发日期:2022-07-27
引用格式:段锦,姚安妮,王震,
盖[J/OL].吉林大学学报(工学版).
.
网络首发:在编辑部工作流程中,稿件从录用到出版要经历录用定稿、排版定稿、整期汇编定稿等阶
段。录用定稿指内容已经确定,且通过同行评议、主编终审同意刊用的稿件。排版定稿指录用定稿按照期
刊特定版式(包括网络呈现版式)排版后的稿件,可暂不确定出版年、卷、期和页码。整期汇编定稿指出
版年、卷、期、页码均已确定的印刷或数字出版的整期汇编稿件。录用定稿网络首发稿件内容必须符合《出
版管理条例》和《期刊出版管理规定》的有关规定;学术研究成果具有创新性、科学性和先进性,符合编
辑部对刊文的录用要求,不存在学术不端行为及其他侵权行为;稿件内容应基本符合国家有关书刊编辑、
出版的技术标准,正确使用和统一规范语言文字、符号、数字、外文字母、法定计量单位及地图标注等。
为确保录用定稿网络首发的严肃性,录用定稿一经发布,不得修改论文题目、作者、机构名称和学术内容,
只可基于编辑规范进行少量文字的修改。
出版确认:纸质期刊编辑部通过与《中国学术期刊(光盘版)》电子杂志社有限公司签约,在《中国
学术期刊(网络版)》出版传播平台上创办与纸质期刊内容一致的网络版,以单篇或整期出版形式,在印刷
出版之前刊发论文的录用定稿、排版定稿、整期汇编定稿。因为《中国学术期刊(网络版)》是国家新闻出
版广电总局批准的网络连续型出版物(ISSN2096-4188,CN11-6037/Z),所以签约期刊的网络版上网络首
发论文视为正式出版。
:.
췸싧쫗랢쪱볤ꎺ2022-07-2709:09:42
췸싧쫗랢뗘횷ꎺ.
吉林大学学报(工学版)
JournalofJilinUniversity(EngineeringandTechnologyEdition)
改进的麻雀搜索算法优化无线传感器网络覆盖
段锦,姚安妮,王震,于林韬
(长春理工大学电子信息工程学院长春130012)
摘要:针对麻雀搜索算法随机性大,在高维复杂问题上容易陷入局部最优的缺点,提出了融合多策略改进的麻雀
搜素算法。在麻雀搜索算法初始化阶段,引入佳点集策略进行种群初始化,以确保种群的多样性和遍历性。在发
现者位置更新方式中引入动态学****机制,有效平衡算法全局寻优和局部探索能力。在跟随者位置更新方式中引入
莱维飞行扰动机制,加强算法局部逃逸能力。并将改进的麻雀搜索算法应用在无线传感器网络覆盖问题的优化上。
为平衡网络覆盖和网络寿命两大关键性问题,从最大化覆盖率、最小化覆盖冗余和最大化能耗均衡三个角度考虑,
把无线传感器网络中节点的多目标覆盖优化问题优化抽象成一个函数,并利用改进的麻雀搜索算法进行寻优。仿
真结果表示三种改进措施效果明显,改进的麻雀搜索算法可有效应用于网络覆盖问题,可提高网络节点覆盖质量,
增强网络的整体性能,具有良好的实用性。
关键词:麻雀搜索算法;无线传感器网络覆盖;佳点集初始化;动态学****机制;莱维飞行策略
中图分类号::A
AnImprovedSparrowSearchAlgorithmOptimizesCoverageinWirelessSensor
Networks
DUANJin,YAOAnni,WANGZhen,YULintao
(ChangchunUniversityofScienceandTechnology,Changchun130012,China)
Abstract:Aimingatthedisadvantagesoflargerandomnessofsparrowsearchalgorithmandeasytofallintolocaloptimumin
high-dimensionalcomplexproblems,animprovedsparrowsearchalgorithmbasedonmulti-
initializationstageofthesparrowsearchalgorithm,thegoodpointsetstrategyisintroducedforpopulationinitializationtoensurethe

effectivelybalancethealgorithm'


problemsofnetworkcoverageandnetworklifetime,themulti-objectivecoverageoptimizationproblemofnodesinwirelesssensor
networksisoptimallyabstractedintoafunctionfromthreeperspectivesofmaximizingcoverage,minimizingcoverageredundancy
andmaximizingenergybalance,
resultsindicatethatthethreeimprovementmeasuresareeffectiveandtheimprovedsparrowsearchalgorithmcanbeeffectively
appliedtothenetworkcoverageproblem,whichcanimprovethecoveragequalityofthenetworknodesandenhancetheoverall
performanceofthenetworkwithgoodpracticality.
Keywords:Sparrowsearchalgorithm;Wirelesssensornetworkcoverage;Goodpointsetinitialization;Dynamiclearning
mechanism;Levyflightstrategy
基金项目:国家自然科学基金().
作者简介:段锦(1971—),男,教授、博士生导师,博士,数字图像处理、机器学****与模式识别,******@
通信作者:段锦(1971—),男,教授、博士生导师,博士,数字图像处理、机器学****与模式识别,******@:.
0引言(StochasticConfigurationNetwork,SCN)中,构成
CSSA-SCN,采用CSSA自动给出较优的SCN参数;
无线传感器网络(WirelessSensorNetwork,最后,利用基准函数和多个数据集对CSSA和
WSN)是由大量具有无线通信与计算能力的微小传CSSA-SCN的性能进行了测试,验证了CSSA-SCN
感器节点构成的自组织分布式网络系统,无线传感算法的可行性和有效性。Liu等人[14]提出了一种改
器网络低成本、易于部署、高可靠性等优势使无线进的麻雀搜索算法—CASSA来解决无人机航路规
传感器网络成为最有能力处理民用和军用应用的技划问题。首先,建立三维任务空间模型和无人机航
术之一,在军事勘探、环境监测、智慧城市等方面路规划成本函数,将航路规划问题转化为多维函数
有着巨大应用价值[1]。无线传感器网络的覆盖优化
优化问题;其次,引入混沌策略来增强算法种群的多
作为无线传感器网络最基本的问题之一,有限的传样性,并利用自适应惯性权值来平衡算法的收敛速
感器节点能量、网络通信带宽和计算能力都给传感度和探索能力;最后,采用柯西高斯变异策略来增强
器网络的覆盖可持续性带来了挑战。如何在保持高算法摆脱停滞的能力。仿真结果表明CASSA能有
覆盖率的同时,平衡网络能耗,最终实现延长网络效地解决无人机航路规划问题。Yuan等人[15]提出
寿命的目标,是一个重要的问题[2]。
了一种基于改进麻雀搜索算法(ImprovedSparrow
群智能优化算法属于生物启发式方法,核心思SearchAlgorithm,ISSA)的分布式最大功率点跟踪方
想是通过模拟自然界中生物特性,通过在有限的空法,来解决光伏微网系统部分遮阳下的功率失配损
间内搜索解的空间分布来寻找最优解。近几十年来,失问题。首先,利用重心反向学****机制对种群进行
群智能优化算法因其结构简单、求解效率高被广泛初始化,使种群具有更好的空间解分布;其次,在发
应用在求解优化问题上[3]。常见的智能优化算法包
现器的位置更新部分引入学****系数,提高算法的全
括蚁群算法(AntColonyOptimization,ACO)[4]、粒子
局搜索能力;同时利用变异算子改进了接合器的位
群算法(ParticleSwarmOptimization,PSO)[5]、遗传算
置更新,避免了算法陷入局部极值。仿真结果表明,
法(GeneticAlgorithm,GA)[6]等等。其中,麻雀搜索
ISSA算法能快、准、稳地跟踪最大功率点。
算法(SparrowSearchAlgorithm,SSA)[7]是2020年由
以上作者利用各种方法对麻雀搜索算法进行改
薛建凯学者提出的一种新颖的群智能优化算法,通进,可以更好地提高各算法的优化能力,但仍存在
过模仿麻雀个体搜索食物行为和反捕食行为进行迭一些不足:
代寻优。SSA算法相较于其他群体智能优化算法,(1)SSA算法采用了随机初始化种群的方式,在
如GWO、PSO、引力搜索算法(GravitySearch后续改进的过程中,有些作者采用的初始化理论,
Algorithm,GSA)等具有更好的寻优能力[8]。为解[16]
如混沌映射,其本身就具有很强的不确定性,不能
决工程问题上提供了新思路[9-12]。然而,SSA具有
从根本上改变算法的随机性,难以保证种群的多样
群智能算法普遍存在的缺点,在求解复杂的优化问性和遍历性。
题时,SSA学****能力不足,当搜索接近全局最优时,(2)SSA算法的性能的关键就是寻优能力。现有
种群多样性大大减少,算法容易陷入局部最优。为的研究只是提高了算法在邻域空间的搜索能力,没
了克服麻雀搜索算法的这些缺点,学者们已经展开有从根本上改变算法本身的优化机制,算法依旧缺
了很多有效且有着很强的应用价值的研究。Zhang乏学****能力,因此在遇到高维复杂问题时仍有陷入
等人[13]首先提出了混沌麻雀搜索算法(Chaotic
局部最优的可能。
SparrowSearchAlgorithm,CSSA),该算法主要利(3)算法局部逃逸能力很弱,陷入局部最优解的时
用逻辑映射、自适应超参数和变异算子来增强SSA候,算法很难跳出局部最优解。
的全局寻优能力;并将CSSA运用到随机组态网络
:.
因此,在众多学者研究的基础上,本文提出了一种2改进的麻雀搜索算法MSSA
改进麻雀搜索算法MSSA,并且将MSSA成功应用
在无线传感器网络覆盖问题的优化上。
在算法初始化的过程中,SSA采用的是随机初
1麻雀搜索算法始化种群个体,这种初始化方法难以保证种群的多
样性和遍历性。为了提高算法全局搜索能力,这里
麻雀搜索算法中,麻雀被分为三种群体:发现引入佳点集的初始化种群方式。佳点集理论是由华
者、跟随者、预警者。发现者引领种群确定觅食方罗庚等学者提出[17]。
向,发现者位置更新公式如下:[18]
佳点集重要的性质之一:采用随机法的偏差
Xi,i,RST
Xi,jt1(1)2为(n)O(n1/2(log,采用佳点集方法的偏差为logn)1/2)
Xi,jt,RST
2,这里是样本数,是任意小的正数。
(n)O(n1)n
式(1)中t代表当前迭代数,N代表最大迭代次数。由此可以看出佳点集布点的方式比随机选择的点的
偏差小很多,故佳点集是一种分布均匀且有效的选
t表示第i只麻雀在第j维中的位置信息。
Xi,j点方式,利用佳点集的均匀性的优点来初始化种群,
0,1。R2(R2[0,1])代表预警值,ST(ST[,1])可以提高种群的多样性和遍历性,使算法表现较稳
代表安全值。Q是服从正态分布的随机数。L是一定且始终保持初始种群良好的多样性,从而避免算
行多维的全一矩阵。法出现早熟现象,最终成功收敛到全局最优。进一
跟随者跟随发现者进行觅食,跟随者的位置更步证明了选择佳点集初始化的优越性。
新描述如下:
Xt发现者位置引入动态学****策略
worsti,j,ifin
i22
t1麻雀搜索算法有一大缺点就是搜索模式过分依
Xi,jt
Xt1X(2)Xt,算法本身的学****能力不足,使算法不能很A.L,otherwise.
Pi,jP

好的寻优。为了解决算法寻优模式的问题,本文引
入动态学****策略,其包含两种学****策略,分别为动
XP是当前发现者所占据的最优位置,Xworst态学****对象和动态学****因子。
表示当前全局最差的位置;A是每个元素随机赋值
为1或-1的1d的矩阵,且AAT(AA。T)
预警者是麻雀种群中随机选择的个体,用来预
动态学****对象是指SSA利用学****对象转变个
警被捕食的危险。预警者位置更新如下:
tt体搜索模式,当预警值较小时,tSSA倾向于自我位
XbestXi,jXbest,fifg
Xt1tt
i,jtXi,(3)jXworst
Xi,jk(置更新,其学****对象是他本身个体最优解),fifgt。此
fifXi,j
举目的是为了尽可能获取解空间信息,防止陷入局
Xbest表示种群中最好的位置。是服从标准正
部最优解。当预警值较大,麻雀会出现聚集效应,
态分布的随机数。K[1,1]。fi是当前麻雀个体的麻雀搜索算法倾向于向全局最优解靠近,此时麻雀
适应度值。fg和fw分别是当前全局最佳和最差的更新方式应该以全局最优解Xbestt作为参考,算法转
适应度值。是一个极小的常数,用来防止分母为入局部勘探环节,此时麻雀搜索算法学****对象应该
零。是全局最优解,有效提高算法求解的精度。
Xit,.iteri,ifR(4)2ST
Xit,j1tmax.
Xbest,ifR2ST
:.
开始
初始化种群参数、如种群参数n,迭
代次数、发现者比例PD、警戒者比例
SD等等
随机初始化种群数量
计算各只麻雀的适应度值,找出当前
最优值和最差值及其对应的位置
从适应度值较优的麻雀中选取部分作
为发现者,按照式(1)更新位置
剩余麻雀作为跟随者,按照式(2)
更新位置
从麻雀中随机选择部分麻雀作为警戒
xx1!(10)
者,并按照式(3)更新位置
改进后的跟随者位置更新公式如下:

动态学****因子是指为了平衡算法全局搜索能力XworsttXit,j,ifin
Xt1i2(11)2
和局部勘探能力,引入了动态学****因子ω,其计算i,jXPt1Xit,jXPt1Levy(d),otherwise.

公式如下:其中代表当前发现者的最佳位置。
XPt1
(5)
expi以下是改进的麻雀搜索算法MSSA的流程图。
.iter
limlim(6)expiexp01
iteriter.iter否
迭代初期个体对于学****对象的参考较小,SSA是否满足条件?
处于全局搜索阶段,迭代后期,学****因子ω逐渐逼
近于1,个体对于学****对象的参考较大,算法转入
局部开采阶段。此举有效动态平衡算法全局搜索和
局部勘探的能力,改进后发现者位置更新如下:是
Xit,j.,ifR2ST(7)
Xit,j1.
Xbestt,ifR2ST
结束

SSA中的种群角色较为简单,同一角色相同的
位置更新公式会导致相同角色的个体处于同一最优图1改进的麻雀搜索算法流程图
位置的情况,产生过多的重复最优解,
效率大大降低。且在面对高维复杂问题时,标准的

域,这可能使麻雀陷入局部最优状态。

因此,引在跟随者位置更新方式中引进Levy
为了测试MSSA算法的性优化能力,选取了12
飞行策略。“Levy飞行策略”是生物在未知环境中
个多类型的标准测试函数来验证改进算法的性能。
寻找食物的理想方式,在随机搜索问题中,
测试函数选取如表1所示。为了测试MSSA算法的
很多的启发式算法都基于这个策略进行改进并取得
[19]性优化能力,选取了12个多类型的标准测试函数来
了很好的效果。
验证改进算法的性能。测试函数选取如表1所示。
由于Levy分布非常复杂,通常使用Mantegna
[20]为了进一步证明MSSA的优越性,将MSSA与原算法
算法来模拟它,采用Mantegna算法得出的Levy
[20]SSA、经典算法PSO、最新其他改进算法HPSOBOA、
飞行机制如下:[13]
同类型改进算法CSSA、GGSC-SSA、LOSSA的优化
Levy(x)11/效果进行比较。算法参数设置如表1。算法的种群
2(8)
数量设为100,迭代次数设为500次.
其中1,2为[0,1]中的两个随机数,为常数
实验环境是MATLAB2018b,Windows10操作系
(),σ计算如下:
1统,运行内存16G,***@。为了加强实验说服力,

1sin()排除影响偶然事件,每个算法独立运行30次。
21(9)
12
22

:.
表1所有算法的初始化参数
Table1Initializationparametersofallalgorithms
算法参数
c1c22,Vmax1,Vmin1,max,min
PSO
first,final,c(0),p,x(0),,c1c2。
HPSOBOA
SSA、MSSA
CSSA、GGSC-SSA、,
LOSSA
表2标准测试函数
Table2Standardtestfunctions
function维度(d)区间最小值
F1(x)nxi230[-100,100]0
i1
F2(x)nxinxi30[-10,10]0
i1i1
F(3x)n(jxj)230[-100,100]0
i1j1
F4(x)maxi{xi,1in}30[-100,100]0
F5(x)in1xisin(xi)30[-500,500]-
30[-,]0
F6(x)in1[xi210cos(2xi10)]
F7(x)20exp(in130xi2)[exp(-32,32]n1n0cos(2xi))20e
i1
F8(x)40001in1xi2in1cos(xii)301[-600,600]0
F(9x)(5001j125ji112(2xiaij[)-)65,65]1
4[-5,5]
F10(x)11i[aibix12(bibix23bix2x4)]2
F11(x)i41ciexp(j31aij(xj3pij)2)[0,1]-
F12(x)i41ciexp(j61aij(xj6pij)2)[0,1]-
:.
MSSA来确定给定覆盖区域内节点的部署位置,考

虑到了网络的能耗大小,还考虑网络节点的能耗均
选取F1(x)-F4(x)单峰测试函数来测试算法的局衡情况和覆盖的溢出情况。取得了良好的效果,实
现无线传感器网络多目标覆盖优化的目的。
部开采能力,选取F5(x)-F8(x)、F9(x)-F12(x)
在无线传感器网络中,假设监测区域是一个二
多峰测试函数和固定维多峰测试函数,用来测试算维平面。
法的全局搜索能力。其中算法能力的大小用三大基
本指标最优值、最差值、方差来衡量。并附上算法(1)所有节点均采用布尔感知模型和布尔通信
迭代曲线,更加直观的显示算法的收敛速度和寻优模型。
精度,展现了算法跳出局部空间的能力。从表2分(2)在WSN覆盖过程中,传感器节点为同构
析可知:传感器节点,每个传感器节点都具有相同的通信半径
(1)在单峰测试函数中,MSSA在F(x)-F(x)RC以及感知半径RS,为保证无线传感器网络的连通
14
都精确的寻找到了最优值,其他算法求解结果均劣性,满足RC2RS,这里方便计算,取RC2RS。
与MSSA。可知MSSA具有较好的收敛速度并对单
峰函数进行了高效求解,具有较强的局部求解能力。
(2)MSSA在F4(x)、F7(x)、F8(x)都成功收
敛于最优解。在F5(x)上虽然未寻得全局最优解,但
其表现最优。故MSSA克服局部最优,全局搜索的(a)
能力更强,比其他算法更适合一些复杂的优化问题。
(3)MSSA在固定维测试函数上的表现也非常
出众,在F19(x)-F12(x)皆表现最优,故MSSA的求
解能力和稳定性都是十分优越的。
多种策略的引入显著提高了算法的稳定性和搜索能(b)
力。综上可知,MSSA对不同类型的单峰、多峰、
固定维测试函数具有较好的寻优能力和通用性,对
比六种其他算法拥有更好的寻优能力,尤其是在对
高维寻优时避免了早熟收敛、落入局部极值的情况、
收敛速度也得到了极大地提升。
3无线传感器网络覆盖优化
(c)
(部分)
针对无线传感器网络覆盖优化的问题,
:.
表3各算法运行结果对比
Table3Comparisonoftherunningresultsofeachalgorithm
函数结果SSAPSOHPSOBOACSSAGGSC-SSALOSSAMSSA
F(x)------2060
1
------1710
------1270
F2(x)-----4600
------1590
------1250
------1530
F3(x)
------1530
------1530
F4(x)-----830
--------95
-------94
F(x)BEST-+03-+04-+03-+04-+03-+03-+03
5
Mean-+03