文档介绍：该【基于改进自适应乌鸦搜索算法的无源定位-论文 】是由【珍珠夸克】上传分享，文档一共【6】页，该文档可以免费在线阅读，需要了解更多关于【基于改进自适应乌鸦搜索算法的无源定位-论文 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第33卷第3期重庆邮电大学学报(自然科学版)
2021年6月JournalofChongqingUniversityofPostsandTelecommunications(NaturalScienceEdition)
D0I:.1673-
基于改进自适应乌鸦搜索算法的无源定位
唐菁敏,郑锦文,曲文博
(昆明理工大学信息工程与自动化学院,昆明650500)
摘要:为解决利用时差(timedifferenceofarrival,TDOA)信息无源定位计算困难的问题,引入乌鸦搜索算法(crow
searchalgorith,CSA),针对该算法易陷入局部极值,提出一种改进自适应乌鸦搜索算法(adaptivecrowsearchalgo­
rithm,ACSA)。综合考虑随进化代数增加种群的整体变化,平衡算法迭代过程中的全局搜索能力与局部寻优能力,
设计一种自适应感知概率模型,使算法在初期保留较多优良个体,保证种群多样性,避免局部最优,在后期快速收
敛。理论和仿真结果表明,改进算法精度优于Taylor算法及其他同类型算法,收敛速度也有显著提高,同时算法还
具有高精度、鲁棒性等优点。
关键词:到达时间差;乌鸦搜索算法;自适应感知概率
中图分类号:TN971文献标志码:A文章编号:1673-825X(2021)03-0372-06
Improvedadaptivecrowsearchalgorithmbasedonpassivelocation
TANGJingmin,ZHENGJinwen,QUWenbo
(SchoolofInformationEngineeringandAutomation,KunmingUniversityofScienceandTechnology,Kunming650500,)
Abstract:Crowsearchalgorithm(CSA)isusuallyintroducedtosolvetheproblemofusingtimedifferenceofarrival
(TDOA)informationtocalculatethepassivelocation,,anim­
provedadaptivecrowsearchalgorithm(ACSA)
evolutionaryalgebra,balancingtheglobalsearchabilityandlocaloptimizationabilityintheiterativeprocessofthealgo­
rithm,anadaptiveperceptualprobabilitymodelisdesignedtokeepmoreexcellentindividualsintheinitialstage,ensure
thediversityofpopulation,
showthattheimprovedalgorithmissuperiortoTayloralgorithmandothersimilaralgorithms,andtheconvergencespeedis
alsoimprovedsignificantly,andthealgorithmhastheadvantagesofhighprecisionandrobustness.
Keywords:timedifferenceofarrival;crowsearchalgorithm;adaptiveperceptualprobability
用在无线传感器网络、雷达通信等方向,在现代军事
0引言
和民用领域发挥着越来越重要的作用。较常用的定
近年来,随着我国导航系统的发展,定位技术也位方法有到达时间(timeofarrival,TOA)、到达时间
成为研究的热点。在目前的研究中,定位分为有源差(timedifferenceofArrival,TDOA)、到达时间和
定位与无源定位。所谓无源定位,是指在不向目标(timesumofarrival,TSOA)、到达角度(angleofarri­
发射电磁信号的条件下获得目标位置。相比有源定val,AOA)[1]等测量参数实现目标定位[2];如果基站
位,无源定位的范围广、精度高且隐蔽性好,广泛应与目标之间存在相对运动,则利用多普勒频率差
收稿日期:2019-08-02修订日期:2021-03-12通讯作者:唐菁敏tang_******@
基金项目:国家自然科学基金项目(61761025)
FoundationItem:TheNationalNaturalScienceFoundationofChina(61761025)
第3期唐菁敏,等:基于改进自适应乌鸦搜索算法的无源定位-373-
(frequencydifferenceofarrival,FDOA)进行定位。以维空间内。在二维平面内若要唯一确定一点坐标需
上定位方法中基于TDOA的方法精度高,测量环境至少3个已知位置信息的接收机。假设待测目标估
无较多限制。计位置为w=[“y]T,接收机位置为I,=[叫y,]T
基于TDOA的定位方程具有高度非线性,非凸(,=1,2,…,K),参考接收机11位置为11=[X1
的特点,在研究中通常使用迭代求解法、几何模糊算y「]T,假设测量过程中存在噪声e,则目标位置关于
法以及智能优化算法等来提高解算方程的速度、精接收机1(,V1)和参考接收机11的TDOA为
度和稳定性。经典的泰勒级数展开法需要一个初值。。。Ilw-/,||2yw-/11|2
S,,1=S,-S1+e,,1=-+e,,1=
进行递归操作,如果初值较差易造成算法发散[3];
两步加权最小二乘法引入辅助变量将TDOA定位问(叫-“)2+(y,-y)2-(”1-“)2+(j1-y)2,八
------------------------------------------------------+6,1(1)
题转化为伪线性方程求解,此方法运算速率高,但在c
非视距(nonlineofsight,NLOS)情况下定位精度较(1)式中:S1表示目标到达参考接收机Z1的时间;s,
差且容易产生模糊解,性能明显下降⑷。
表示目标到达接收机1,(,丰1)的时间;e,」表示接收
近年来,人们从自然现象中汲取灵感,提出了大机1(iV1)与参考接收机11之间的噪声;c为光速;
量生物自然启发算法,这些算法被广泛用于解决非II-I2表示2点间的欧氏距离。将K-1(KM3)个
线性优化问题[5],并被证明当参数设置合理时,生TDOA方程组用向量形式表达为
物启发算法有更高的收敛速度与精度。文献[6]提AS=S-S1+£(2)
出利用粒子群优化算法(particleswarmoptimization,(2)式各向量维数均为K-1维,其中
PSO)解决TDOA定位问题,算法在定位时不需要初AS=[S1,2S1,3…S1,K]T'
始值,且精度较高。文献[7]提出一种基于混合遗S=[S2S3…Sk]t](3)
传拟牛顿搜索的算法,算法结合了遗传算法和拟牛
S1=[S1S1…S1]T.
顿算法的优点,降低了后期的搜索速率。文献[8]
(2)式中,£=[…]Tk-1)x1,
提出NLOS环境下基于蚁群优化算法的定位方法,
均值,方差为的高斯白噪声,根据最大似然法来
文献[9]利用海鞘群算法(salpswarmalgorithm,
估计目标位置,推导出似然函数为
SSA)对TDOA定位问题进行解算,采用一种新的群
K-1「1「(AS-S+S1)2]]
体更新模型,并证明了该算法在TDOA定位问题的
有效性。生物启发算法已经发展成为人工智能领域
的重要方向,在解决海量数据处理、非线性优化等问(AS-S+S1)T(AS-S+S1)
题上具有高效、稳定等优势。2b;
群智能优化乌鸦搜索算法(crowsearchalgo-(4)
rithm,CSA)在高维函数寻优[10]、特征选择[11]等方当该似然函数具有最大值时,可解出目标位置
面均有良好表现。本文首次将该算法应用在TDOA(”,y)
定位问题中,并提出改进策略,设计了自适应感知概(”,y)=
率的计算公式。首先分析无源时差定位的数学模(AS-S+S1)T(AS-S+S1)
argmaxexp
型,根据其模型特点使用乌鸦搜索进行解算,然后设2土
计了自适应感知概率的计算公式,适应无源时差定(5)
位问题。较好地平衡了迭代过程中的全局搜索能力可得
与局部寻优能力,避免了其他智能优化算法容易陷入(x,y)=arg{min[(AS-S+S1)T(AS-S+S1)]}
局部极值的问题。最后,通过仿真实验证明了所提自(6)
适应乌鸦搜索算法(adaptivecrowsearchalgorithm,由于(6)式高度非线性,用解析法难以求解出
ACSA)在二维空间中定位估计的高效性和鲁棒性。最优解。本文采用改进的ACSA算法对目标函数进
行寻优。
1时差定位数学模型
2乌鸦搜索算法(CSA)
在计算过程中为了简单起见,考虑二维平面中
的TDOA定位方法,不失一般性,其结论可推广至三据加拿大动物行为学家测验,乌鸦的智力超众,
-374-重庆邮电大学学报(自然科学版)第33卷
其水平和家犬相近,它拥有逻辑推理的能力,是具有(10)式中,P为感知概率,表示乌鸦k在第t次迭代
一流智商的动物。乌鸦在食物盈余时,会将食物藏时移动到除食物位置外的任意一点的概率。
匿到自己已知的位置,并且会跟踪其他乌鸦盗窃食通过评估新位置的适应度函数来确认每个乌鸦
物,被跟踪的乌鸦会有一定的概率移动到没有食物的新位置是否有效,如果乌鸦新位置的适应度函数
的位置以欺骗跟踪者,2016年Alireza根据乌鸦藏值优于记忆位置的适应度函数值,则新位置有效,通
食、觅食的****性提出了乌鸦搜索算法(crowsearch过(11)式更新其记忆。乌鸦会更新它的位置。否
algorithm,CSA)[12],该算法的参数较少,寻优速率和则,乌鸦停留在当前位置并且不会移动到生成的新
效果较好。具体描述如下。位置。
假设CSA算法中每只乌鸦k(k=1,2,…,N)代弊1,代町「)优于/(mk)
表种群N中的1个候选解,乌鸦所处的环境代表QUk,其他(11)
维的可行解空间范围,乌鸦k在第t(t=1,2,…,T,
T为最大迭代次数)次迭代时的位置是d\=[血》,3基于ACSA的TDOA定位过程
竝k,…,〃Q,k],记忆的食物位置为祝k=[mJ,m;,基于TDOA的定位方程具有高度非线性,非凸
…,mQ,k]。特点,用传统解析法求解困难很大,根据对CSA算
N个乌鸦随机定位在Q维搜索空间中作为群法模型参数的分析,该算法的局部搜索能力较差。
的一员。每个乌鸦表示候选解,Q是决策变量的数参数不合理可能造成过早收敛,无法找到全局最优。
量。种群如(7)式,因为在最初的迭代中,乌鸦没有
在不同的场景中,需要对应其模型特点设定参数,以
经验,所以假设它们将食物隐藏在它们的初始位置,
保证算法的寻优性能。在TDOA定位问题中,其寻
每个乌鸦的记忆被初始化,如(8)式
优的范围较大,因此设计一种改进的ACSA解决
TDOA定位的寻优,采用自适应感知概率对算法进
行动态调控,维持种群的多样性。随着迭代次数的
Crows二(7)
增加,使算法初期偏向全局搜索能力倾斜,而在迭代
后期倾斜于局部开采能力。
11
m;m2…m°
22
m:m2…m°根据对CSA的分析得知,感知概率P的取值对
Memory=(8)
算法的搜索效果起决定性作用,若唯一确定感知概
N率P的值则不能充分地发挥算法的性能,减小P值
m1m:…mQ
算法会快速收敛,容易陷入局部最优,若增大P值
假设乌鸦k想要生成一个新位置,在飞行过程
则会造成算法后期无法较好地进行局部寻优。因
中有2种情形发生。
此,提出一种自适应感知概率的方法,在种群进化的
1)当第t次迭代时,乌鸦a在飞向记忆的食物
过程中能保证感知概率P处于一个较为合适的值。
藏匿地点m;时未发现跟踪的乌鸦k,乌鸦k在t+1
该表达式为
次迭代时位置更新为
V3(P1-P2)(nt2)上/
町1=必+rx/Zx(m;-必)(9)P=15呵〔一詞,八几(⑵
(9)式中:r为0-1之间的随机数;fl为乌鸦k的移
动步长。
P1,fW尤vg
2)乌鸦a在飞向食物藏匿地点m;时,有感知(12)式中:p1,p2分别表示感知概率P的最大值和最
概率P发现跟踪的乌鸦k,此时乌鸦a会飞到Q维小值;T表示最大迭代次数;t表示当前迭代次数;
可行解空间中的任意一欺骗点。
/avg,/分别表示当前迭代次数下,种群中所有候选解
综上2种情况,可整理得乌鸦k在t+1次迭代的平均适应度和最大适应度。感知概率P的取值
时的位置表达式为为[,],其变化曲线如图1o
fk+rXflx(m:-必),r工P由图1可知,改进后的算法在迭代初期可以保
随机位置,其他证种群中较为丰富的个体,避免算法收敛较快,形成
(10)局部最优。迭代后期较小的P值可以促使种群快
第3期唐菁敏,等:基于改进自适应乌鸦搜索算法的无源定位-375-
速集中,保证算法性能,加速收敛。8:dk+1=dk+厂xxs:-dk)
9:else
10:d;+1=a厂a〃do叱0$:加0”
11:endif
12:endfor
13:根据(13)式计算个体适应度/(dk+1)
14:根据(11)式评估乌鸦位置
15:更新乌鸦的记忆
16:endwhile
evolutionaryprocess
针对基于TDOA的定位问题,求解目标函数的
自适应乌鸦搜索算法具体步骤如下。
Step1初始化乌鸦种群N、位置d、记忆,确定
参数移动步长求、决策数量Q;
Step2根据(12)式计算感知概率P;
Step3根据(13)式计算个体适应度代d;+1);
Step4根据(10)式和(11)式更新乌鸦位置;
Step5判断是否到达终止条件,否则返回步
骤2。
图2ACSA定位流程图
图2中算法的个体适应度可根据(6)式定义为
4仿真结果及分析
(AS-S+S1)T(AS-S+SJ为了验证自适应乌鸦搜索算法在TDOA定位问
(13)式中,d为ICSA中乌鸦个体的位置,代表问题
题中的性能,实验中用经典泰勒算法(Taylor),CSA,
的可行解。
SSA,PSO与所提算法进行了比较。假设仿真环境
,采用星型布站设
采用ACSA对TDOA定位进行解算的伪代码如下。计,设置在15kmX15km的矩形区域环境内进行。
算法1自适应乌鸦搜索算法接收机个数为4个,分布在半径为12m的圆上,坐
输入:NJI标为(0,0),(600,6003),(-600,6003),(-600,
输出:最佳位置(%』)
-6003)(单位:m)。目标位于(-350,300)(单位:
1:根据(7)式和(8)式随机初始化N个初始解(乌鸦的位
m),其坐标具体分布如图3。实验中PSO,SSA,CSA
置),乌鸦种群的记忆力和适应度
与ACSA的种群规模均为50,5种算法终止条件为
2:计算初始乌鸦种群的适合度并保存最佳位置
最大迭代次数设置为取次蒙特卡洛实验
3:while,<Tdo100,104
4:fork=1:N的平均数据,5种算法的均方误差(meansquareer-
5:根据(12)式计算Pror,MSE)比较如图4。实验中通过均方误差、算法
6://随机选择一只乌鸦跟随(例如a),比较P与随机数收敛速度、平均估计坐标E[(;,?)]与计算时间3
厂并产生k个乌鸦的下一个位置种指标进行定位性能评估。
7:if厂三P
-376-重庆邮电大学学报(自然科学版)第33卷
比所提算法快,但在后期收敛速度逐渐降低,PSO在
整个迭代周期中收敛速度都较慢;由图5b可知,在
测量误差为20ns时,5种算法收敛速度比测量误差
为1ns时稍慢。Taylor算法、CSA,PSO,SSA定位精
度在100次迭代内均低于所提算法。通过对收敛曲
线进行分析知,CSA,SSA,PSO与所提算法相比,由于
所提算法为保持算法种群规模的多样性,参数随迭代
过程变化,所以初期慢后期快。而Taylor算法属于迭
代算法,基于迭代性展开,在计算中较为依赖初始位
置的猜测值,在测量误差较大时,导致初值不理想,
因此出现迭代次数过多并陷入局部最优的情况。
迭代次数
2
史糊已超械墨轻晅部归瑕拠懈时怎那怎皿
lOlg&J/dB
图45种算法的均方误差比较
假设(x,y)为目标的真实位置,(X,y)为目标
的估计位置。二维场景下的均方误差计算方法为
MSE=E[(x-X)2+(y-j)2](14)
从图4可以看出,当噪声方差较小时,5种算法
的性能无差别;随着噪声方差增大,Taylor算法的恶
化速度与噪声方差正相关,从-12dB开始,Taylor算
图55种算法的迭代收敛对比
法定位精度急剧恶化,而PSO,SSA,CSA,
不同的噪声测量环境中,其均方误差一直随噪声方
在一定的偏高噪声功率条件下,对Taylor算法、
差保持较稳定的增长,与Taylor算法比较,具有良好CSA,PSO,SSA,ACSA这5种算法进行算法运行效
的性能,原因是在求解过程中,使用最大似然估计对
率及精度对比,结果如表1o从表1可以看出,当噪
定位模型中所有可能的解进行最优选择。所提算法
声功率为-2dB时,相对于Taylor算法,其运行效率
改进了参数设定,从而适应进化过程中各个阶段的与估计结果都略差于其余4种算法;相对于所提
特点,保持算法的鲁棒性,与CSA,PSO,SSA相比ACSA算法,其估计结果精度高于其余4种算法,由
较,始终有更好的表现。于所提算法的复杂度升高,故运行效率差于CSA和
为了分析5种算法在进行TDOA问题解算时的SSA,但和Taylor算法、PSO相比,所提算法效率明
收敛情况,本文对5种算法进行100次迭代的仿真显优于以上2种算法。
实验,当目标位置与算法定位位置变化差稳定时视
5结束语
为收敛,仿真结果如图5o由图5a可知,在测量误
差为1ns时,5种算法都能得到准确位置,其中,本文提出的算法为改进的自适应乌鸦搜索算
Taylor算法的收敛速度最快,CSA,SSA在迭代初期法,在设计新的自适应感知概率时考虑了随着进化
第3期唐菁敏,等:基于改进自适应乌鸦搜索算法的无源定位-377-
代数增加种群的整体变化。对ACSA,CSA,PSO,Shenzhen,China:IEEE,2011:606-610.
SSA,Taylor5种方法进行了比较分析,前4种属于[8]ZHANGZ,LIUX,
basedantlionoptimizationmethodinNLOSenvironment
智能算法,实验可知采用智能算法来解决TDOA的
[C]//The9thIEEEAnnualInformationTechnology,E­
,
高度非线性问题是一种非常有效的手段在噪声方lectronics,andMobileCommunicationConference.[S.
差较低时,5种算法定位精度相近,随着噪声方差的l.]:IEEE,2018:281-285.
增大,所提算法保持较高的精度,智能算法表现出良:9]陈涛,王梦馨,
好的鲁棒性,验证了ACSA算法的有效性。定位[J].电子与信息学报,2018,40(7):1591-1597.
表110lgc2贰=-2dB时5种算法性能比较CHENT,WANGMX,
ArrivalPassiveLocationBasedonSalpSwarmAlgorithm
]--2dBComparisonoffivealgorithms
[J].JournalofElectronicsandInformationTechnology,
performance
2018,40(7):1591-1597.
运行时间估计坐标估计坐标:10]赵世杰,高雷阜,于冬梅,
算法
/s%/my/m代维度交叉策略的改进CSA算法:J].电子学报,
-,47(1):40-48.
-,GAOLF,YUDM,
--FactorWeighted
--GenerationsDimensionCrossover
-[J].ActaElectronicaSinica,2019,47(1):40-48.
:11]王颖,曹捷,
参考文献:择算法[J].吉林大学学报(理学版),2019,57(4):
:1]:D].869-874.
西安:西安电子科技大学,,CAOJ,
AlgorithmBasedonCrowSearchAlgorithm[J].Journalof
­
erandFrequencyDifferencesofarrival[D].Xi'an:Xid-JiLinUniversity(ScienceEdition),2019,57(4):869-874.
[12]
ianUniversity,2016.
:2]郑倩,胡久松,刘宏立,:crow
统的定位性能分析[J].重庆邮电大学学报(自然科学searchalgorithm[J].ComputersandStructures,2016,
版),2018,30(6):768-(C):1-12.
ZHENGQ,HUJS,LIUHL,­
formanceanalysisofindoorpositioningsystembasedon
唐菁敏(1979),男,湖南人,教授,博士,
compressivesensing[J].JournalofChongqingUniversity
研究方向为认知无线电、无线传感器网络。
ofPostsandTelecommunications(NaturalScienceEdi­
E-mail:tang_******@
tion),2018,30(6):768-775.
:3]FANGJQ,FENGDZ,­
tonandTaylorseriesmethodsinTDOA[J].Journalof
XidianUniversity,2016,43(6):27-33.
:4]JIAT,WANGH,SHENX,
basedonstructuredtotalleastsquareswithhybridTDOA-郑锦文(1995),女,云南昆明人,硕士研
AOAmeasurements[J].SignalProcessing,2018(143):究生,研究方向为多点定位。E-mail:cxhx-
211-221.
******@
[5]SACHANRK,GUPTAS,
andResearchDirectionsinNature-InspiredAlgorithms
[C]//20185thIEEEUttarPradeshSectionInternational
ConferenceonElectrical,ElectronicsandComputerEngi­
neering(UPCON).[]:IEEE,2018:1-5.
:6]LUIKWK,ZHENGJ,­曲文博(1992),男,陕西西安人,硕士研
zationfortime-difference-of-arrivalbasedlocalization究生,研究方向为无线传感器网络。
[C]//,
PL:IEEE,2007:414-417.
[7]SHIHY,­
calizationinwirelesssensornetwork[C]//2011IEEEIn­
(编辑:魏琴芳)
ternationalConferenceonInformationandAutomation.