改进蛇优化算法在室内UWB定位的应用

郑 凯，裘 君，童应楠，虞 锋

(1.江西理工大学 电气工程与自动化学院，江西 赣州 341411；2.浙大宁波理工学院 信息科学与工程学院，浙江 宁波 315100；3.宁波瓦萨智能科技有限公司，浙江 宁波 315100)

0 引言

伴随着智能制造时代的到来,基于室内定位技术的服务深入到人们生活的方方面面。相较于传统的无线技术如红外线定位[1]、超声波定位[2]、蓝牙定位[3]、WiFi定位[4]、射频识别技术[5]和Zigbee技术[6]等,超宽带技术(Ultra-Wide Band, UWB)因其自身具有的高传输速率、高带宽、低功耗和强抗干扰性的特性,被广泛应用在物流生产线、办公室和居家等场景[7]。

基于UWB的定位技术分为时间参数和非时间参数2种:基于时间参数的定位技术有TOA[8]、TDOA[9];基于非时间参数的定位技术有AOA[10]、RSSI[11]。基于测距的传统定位算法利用TOA和TDOA测得相关距离信息,通过传统的三边测量法、极大似然估计法、Chan算法[12]和Taylor级数展开法[13]来估计待定位物体的坐标。

三边测量算法原理简单,测出基站到标签的距离,以3个基站为圆心画圆找到交点即为定位点,计算量小、计算速度快。实际情况下,由于测距的随机误差和非视距误差的存在,作出的3个圆实际无法相交于一点[14],导致出现较大误差。对比传统的定位算法,智能优化算法寻求在求解时间和求解速度上的平衡,但是不能保证最终结果是最优解,有可能会陷入局部最优解,因此将智能算法的改进应用于室内定位成为了当今研究的热点。如何改善部分智能算法的收敛速度和精度成为了值得关注的问题。

文献[15]提出了基于该改进鸽群算法的无线传感器网络定位方法,在鸽群算法中引入自适应调整机制,在种群分组过程中融入随机游走机制,使定位算法具有较高的定位精度和较快的收敛速度。刘双等[16]提出了一种基于黄金正弦与Sigmoid连续化海鸥优化算法,提高了算法的寻优能力和后期收敛速度。将基于RSSI的定位精度大幅度提升。田洪舟等[17]提出了一种改进樽海鞘算法的优化DV-Hop算法,在种群初始化时利用混沌映射,更新追随者位置引入精英,同时采用淘汰者个体产生较优个体,使得该算法比传统DV-Hop算法及其他算法具有更好的定位能力。

本文提出了利用自适应调整测距值的改进蛇优化(Snake Optimization,SO)算法来提升非视距误差所带来的定位误差。首先对基站测得的测距值进行自适应调整。将测距得到的值代入用于SO算法的适应度函数。对SO算法初始化种群初期引入sine混沌映射,提高种群的分布的均匀性。在雌性个体和雄性个性位置更新以后对其更新位置进行正弦余弦算法(Sine and Cosine Algorithm, SCA)优化,提高算法收敛速度。实验结果表明,相较于传统算法和传统智能优化算法,改进算法具有较高的定位精度和收敛效率。

1 传统室内定位方法与改进

1.1 传统三边测量算法

三边测量法是一种先测得3个参考基站和待定位标签之间的距离,再通过几何学方法计算标签位置的方法。

三边测量法实现简单但是总体来说定位精度不高。测距本身存在随机误差;非视距误差的影响,会造成该算法误差变大。提高测距精度会加大成本 ,需要增加基站数量,虽然能在一定程度上减小误差[17],但最终效果有限。

1.2 自适应改进测距值法

三边测量算法原理简单、实现快速,但是由于非视距误差的存在,导致以基站为圆心的圆无法相交于一个点上,出现圆相交的区域过大的现象,如图1所示。为解决上述情况,本文引入一种自适应三边定位测距值修正方法[18],并对其修改,能够有效缩小相交区域。

图1 实际相交区域过大Fig.1 Too large for actual intersection area

(1)选择基站

因非视距误差因素的影响,基站误差有大有小。室内设置3个基站,每次选3个基站,按序号选出不平行的n组,先根据标签的位置找出3个测量距离移动标签距离误差最小的基站,再对选出的基站进行自适应调整。

(2)进行自适应调整算法

每组选出的3个基站,作为三边测量法的基站。设置基站圆交点间距离的上限,对图1中的测量距离进行自适应调整。

① 算出基站与基站间的距离,得到基站B1与基站B2之间距离d12,同理计算出基站1和基站3间距离d13以及d23;

② 判断2基站为圆心的圆之间的位置:若(ra1+ra2)≥d12,则表明基站1和基站2作的圆为相切或是相交;如果(ra1+ra2)

③ 判断基站为圆心的圆的位置关系:若2圆相交,求出2圆交点,然后得到第3个圆的圆心到2个交点之间的距离,将最小的距离保留下来记作r。若半径ra3>r,那么3个圆之间存在公共区域,即3圆有相交区域;

④ 根据判断系数来判断2圆位置,若B1和B2中的(ra1+ra2)/d12>1.2,则这2个基站之间的距离远大于实际测距值,需要调整。同时,对比圆B1和B3中(ra1+ra3)/d13以及B2和B3中(ra2+ra3)/d23。选取比值较大的2个圆的半径调整,选出2个圆中距离差较大的那个圆的半径进行修正。在第一次调整之后,计算出2个圆之间交点距离,判断是否小于交点间距的0.9倍,如果小于此数值,则停止递推;否则继续进行调整,直到交点距离小于目标距离差。

2 SO算法的应用

2.1 原始SO算法

受启发于蛇奇特的交配行为, 2022年Fatma A和Hussien A G提出了SO算法[19]。

蛇的雄性和雌性交配行为的发生受到某些因素的影响。若是气温低、食物充足,那么蛇发生交配行为;否则蛇只会去寻找食物或者吃已有的食物。基于此SO的搜索过程分为2个阶段:探索和开发。蛇种群在搜索空间随机初始化以后,会被平分为雄性和雌性2组。雄性和雌性的数量分别表示为:

(1)

Nf=N-Nm,

(2)

式中:N为种群总数,Nm为雄性个体,Nf为雌性个体。从每组中找出最好个体然后得到最佳雄性和最佳雌性以及食物的位置,分别记为fbest,m,fbest,f和ffood。温度定义如下:

(3)

式中:t为当前迭代次数,T为最大迭代次数。食物数量定义为:

(4)

式中:c1为常数,取0.5。

探索阶段描述了寒冷地区环境因素和食物,此时蛇不会在周围寻找食物。如果Q

Xi,m(f)(t+1)=Xrand,m(f)(t)±c2×Am(f)×

((Xmax-Xmin)×rand)+Xmin,

(5)

式中:Xi,m(f)表示雄性或是雌性个体,rand是[0,1]的随机数,c2取0.05,Am(f)是雄性或是雌性寻找食物的能力。

(6)

式中:frand,m(f)为随机选择的雄雌个体位置Xrand,m(f)的适应度值,fi,m(f)为雌雄种群中第i个个体位置Xi,m(f)的适应度值。

开发阶段时有食物,即Q>Threshold。若temperature>Threshold(Threshold=0.6),气温高,只会寻找食物,位置更新公式为:

Xi,j(t+1)=Xfood±c3×Temp×rand×

(Xfood-Xi,j(t)),

(7)

式中:Xi,j(t)为个体位置,Xfood为蛇个体的最佳位置,c3取2。

若temperature

战斗模式下的位置更新公式:

Xi,m(f)(t+1)=Xi,m(f)(t)±c3×FM(F)×rand×

(Q×Xbest,f(m)-Xi,m(f)(t)),

(8)

式中:Xbest,f(m)为雌(雄)组最佳位置,FM(F)为雄性或雌性战斗能力。

(9)

式中:fbest,f(m)为雌雄最佳个体的适应度值,fi为当前蛇个体的适应度值。

交配模式下仅需将Xbest,f(m)换成Xi,f(m)即第i个雌性或雄性个体的位置,FM(F)替换为Mm(f),表示雄性和雌性的交配能力,计算如下:

(10)

若蛇卵孵化,选择适应度最差的雄性和雌性替换它们的位置,表示为:

Xworst,m(f)=Xmin+rand×(Xmax-Xmin)。

(11)

2.2 改进SO算法

2.2.1 改进sine混沌映射种群初始化

通常群体智能算法使用随机方法产生初始种群,但此种方式可能会使个体位置分布不均,从而导致部分个体远离较优位置。

混沌现象是指确定的宏观非线性系统在一定条件下呈现的不可预测随机现象,其对初始值异常敏感,即初始情况下任意的微小变动都会造成之后的非线性变化。混沌序列因其遍历性、随机性和不确定性能够产生分布更加均匀的种群个体,提高算法的寻优能力。

原始sine混沌映射产生的一维序列在相空间中分布并不均匀,处于混沌状态的参数空间相对较窄,基于此,文献[20]提出了一种改进的sine映射方法,用2个控制参数来计算序列数,其混沌特性要好于原始的sine混沌映射序列,如下所示:

(12)

将改进的sine映射应用到SO算法的种群初始化中,首先产生混沌映射初始迭代点:

X(1)=lb+rand×(ub-lb)。

(13)

根据目标优化问题的具体条件,将式(12)改写为:

(14)

式中:ub、lb分别为变量的上界和下界,rand为随机生成的0～1的随机数,di、ei为控制参数,wi+1为迭代序列值即为蛇种群中的位置。

对改进后的sine混沌映射进行模拟仿真,得到在不同μ值下的混沌映射分布,如图2所示。

(a)Sine混沌分布 μ=0.99

(b)改进的sine混沌分布 μ=0.99

原始的sine混沌映射在μ=0.99已经进入了混沌状态,但是本文改进的sine混沌映射在μ相同时的分布状态明显要比初始sine混沌映射更加均匀,遍历性更好,有利于蛇种群初期的种群初始化。

2.2.2 改进SCA优化

2016年Mirjalili[21]提出了一种基于正弦余弦的新型元启发式优化算法,基于正余弦函数的性质,通过改变正余弦函数的振幅使初始随机候选值朝最佳值内外波动,来平衡算法的局部和全局寻优能力。

在随机产生初始化个体后,先计算各个体的适应度值,找出最优位置和最佳适应度值。个体位置更新公式为:

(15)

式中:D=r3×X*-X(t),t为当前迭代次数,X*为上一轮更新的最优解,r2～r4均为随机数,r2∈[0,2π],r3∈[0,2],r4∈[0,1],r1为线性递减的控制参数,它可以提供更大更广的搜索空间。

(16)

式中:a为常数,取2;tmax为最大迭代次数。

传统SCA算法中,参数的设置过于简单,如r1仅为一条截距为2的线性直线,对算法的探索和开发阶段过渡效果有限,算法可能会提早陷入局部最优解,所以对r1进行改进[22]:

(17)

利用正弦函数的性质,使控制参数r1局部震荡,能够进一步平衡寻优能力。

为更加全面地利用个体位置信息,使个体当前的位置对新位置的影响权重产生变化,添加动态的权重系数β为:

(18)

式中:b为优化因子,服从参数为λ的指数分布,即b～E(λ),将λ设置为雄性或是雌性的蛇种群数N/2。迭代初期,β下降较为缓慢,此时个体位置对算法的干预有较大影响,以便全局搜索。后期β下降以减小个体的影响力,此时充分进行局部开发,个体更新的公式为:

(19)

改进后的SCA作为蛇算法雌性雄性位置更新后的补充,得到新的更新过的位置,提升算法的寻优能力。

2.2.3 结合自适应测距值的SO算法

自适应调整后的测距值作为改进SO算法的适应度函数的参数,设置适应度函数:

(20)

式中:xi、yi分别为每个基站的横纵坐标,x、y分别为每个蛇个体的坐标,di为每个基站到标签的距离,这里使用自适应调整过的测距值。

2.2.4 改进SO算法的算法流程

综上所述,本文提出基于UWB信号的改进SO算法室内定位过程如图3所示。

图3 算法流程Fig.3 Flowchart of the algorithm

步骤1: 获取基站到标签的距离值,根据自适应规则调整测距值,使3圆相交区域尽可能小。

步骤2: 设置蛇种群数量、最大迭代次数,根据优化的sine混沌映射初始化蛇的种群。

步骤3: 根据式(1)、式(2)将种群分为雄性与雌性2组,设置适应度函数,并计算相应的适应度,找当前最佳雌雄个体。

步骤4: 根据式(3)、式(4)定义环境温度Temp和食物数量Q。

步骤5:根据食物量Q的多少来判断只寻找食物或战斗和交配。如果Q<0.25,则寻找食物,根据式(5)更新蛇个体的位置。

步骤6: 若食物充足,Temp>0.6,只寻找食物和吃现有食物,根据式(7)更新位置。

步骤7: 根据模式随机数rand判断进入战斗模式和交配模式,根据式(8)更新战斗模式位置,用式(10)替换战斗模式下的Am,将最佳个体替换成当前个体,更新位置。如果卵孵化,选出最差个体,替换掉它们。

步骤8:处理更新后的位置,更新个体历史最佳值。

步骤9: 根据式(19)改进的SCA对位置再次更新。

步骤10:更新个体历史最佳值。

步骤11:再次更新全局最佳适应度,更新食物位置。

步骤12:判断是否达到迭代次数,不满足进入下一轮迭代;满足则结束迭代并输出最佳位置。

3 实验与结果分析

本文采用将上述自适应调整策略对测距值进行调整,再与采用了sine混沌映射和正余弦优化的SO算法进行结合的方法,对待定物体的室内位置进行计算。将基于自适应调整测距值的MSSCASO(Modified Sine Mapping Sine Cosine Snake Optimization)定位算法分别与基于最小二乘法(LSM)的定位算法、基于Chan算法的定位算法和基于引入本文自适应调整策略的Chan算法做比较。

3.1 室内平面实验

本文在实验室下分别安置5个基站作为参考节点,基站所摆放的位置分别为(0,0)、 (2.525,0)、 (5.62,0)、(5.46,5.625)和 (0,5.625),高度为1.205 m的平面内。标签作为待测点,选取多个点放置,先进行距离测量再进行坐标解算。选取点和参考基站位置如图4所示。

图4 实验室基站分布情况Fig.4 Distribution of lab bases

对每个待测定位点进行500次采样,并对每个点的测距采样结果取平均值。将测距值代入LSM、Chan法、改进后的Chan算法、原始SO算法以及本文算法进行对比。

图5为每个待测点在改进的SO算法下的估计位置。图6为8个目标点的各算法误差对比。

图5 待测点在改进SO算法下的估计位置Fig.5 Estimated positions of test points under improved SO algorithm

图6 各算法的多点欧氏距离误差Fig.6 Multiple-point Euclidean distance error for each algorithm

由图6的欧氏距离误差对比状况来看,LSM的误差位于最上方,最大的误差接近0.4 m。基于3基站的Chan算法与LMS差距不大,基本重合。加入了自适应调整策略的Chan算法精度有一定的提升。SO算法精度要好于前3种,基本徘徊在0.1～0.15 m。改进SO算法下的预测误差线基本在0.1 m的位置以下,并且误差线较为平稳,算法稳定性好。

表1记录了所有点在不同算法下的不同坐标轴方向上以及欧氏距离误差,以及所有点的均方根误差(Root Mean Squared Error,RMSE)。

表1 各点在不同算法下的误差数据

从表1可以看到,LSM、Chan算法和改进Chan算法在X轴上的平均误差在0.1 m左右。从Y轴上的平均误差来看,修正Chan算法和本文算法最小分别为0.098 m和0.033 m,LSM最大达到 0.127 m。从欧式距离误差来看,LSM和Chan算法平均为0.217 m,改进的Chan算法平均欧氏距离误差为0.176 m,因为经过自适应调整策略和后,该算法在一定程度上消除了非视距因素带来的影响。改进后的SO算法的平均误差最小,为0.074 m。从欧式距离误差和RMSE观察,LSM和Chan算法的稳定性最差,SO算法和本文MSSCASO算法稳定性较好,分别为0.128 m和0.078 m。综上所述,改进的SO定位算法,定位精度高、稳定性高,满足室内定位的需求。

3.2 收敛速度分析

分别使用PSO、MPSO、SO 以及本文算法MSSCASO进行400次迭代。如图7所示,基于PSO和MPSO的定位算法在100次迭代前下降速度快,之后缓缓下降逐步接近最低适应值,MPSO对PSO算法的惯性权重ω进行线性化处理,提高了PSO算法初期的全局搜索能力和后期的局部收敛能力。相比基于PSO算法的定位算法,基于SO算法的定位算法在初始适应度值上就要小得多,这得益于SO算法的种群初始化分布较为均匀。在前10次迭代,基于SO算法和MSSCASO算法的适应度值就已经快速下降。相比原始的SO算法,改进的SO算法初始适应度值更小,这是因为经过优化的sine混沌映射,使得初始化的蛇种群分布更加均匀。可以看到,改进SO算法中引入了改进的SCA,提高了算法的局部寻优能力,所以改进SO算法的迭代曲线始终位于初始SO算法的下方,提升了收敛性能。

图7 算法效率Fig.7 The efficiency of algorithms

3.3 室内立体定位实验

在平面实验的基础上,将个别基站移至不同平面,使得各基站形成三维立体空间。基站的位置设置为(0,0,1.205)、(2.525,0,2.5)、 (5.62,0,1.205)、 (5.46,5.625,2.5)和 (0,5.625,1,205)。将基于改进SO算法的UWB室内定位算法与基于LSM、基于PSO算法的室内定位算法进行对比。

首先通过UWB传感器测距,进行500次距离值采样,对测距值取平均值,分别将得到的测距值代入LSM、PSO、SO算法以及本文的改进SO算法。将预测点与实际点的直线距离差作为定位误差进行对比,如图8～图11所示。

图8 基于LSM算法的定位结果Fig.8 Positioning results based on LSM algorithm

图9 基于PSO算法的定位结果Fig.9 Positioning results based on PSO algorithm

图10 基于SO算法的定位结果Fig.10 Positioning results based on SO algorithm

图11 基于MSSCASO算法的定位结果Fig.11 Positioning results based on MSSCASO algorithm

表2列出了各算法下待定位标签的估计欧氏距离差,基于LSM算法的UWB室内定位,定位误差达到了0.314 m,定位误差较大,因为室内环境较为复杂,非视距干扰多,对定位结果造成较大的干扰。基于PSO算法的定位结果,定位误差为0.176 m。基于原始SO算法和基于改进SO算法的定位结果的欧氏误差分别为0.148 m和0.118 m。后3种智能优化算法相较于LSM明显较高。基于SO和改进SO的定位算法相较于PSO算法,收敛速度更快、全局寻优能力更强、定位精度更高。基于改进的SO定位算法在SO算法的基础上对初始化种群过程进行混沌化,提高了初始种群分布的均匀性,更有利于全局寻优。位置更新的过程中进行改进的SCA,提升了算法的寻优能力。相较于基于PSO的定位算法和基于SO的定位算法,改进后的SO算法定位精度分别提高了32.95%和20.27%。

表2 立体定位下各算法的欧氏误差

4 结束语

本文提出了基于MSSCASO算法的UWB室内定位算法。在多点定位的二维平面定位实验中,本文引入了一种自适应的测距值修正法,并将修正后的测距值代入了改进的SO算法,定位精度良好,该算法的平均定位欧氏距离误差为0.074 m,定位稳定性好,RMSE为0.078 m。在单点的室内立体定位算法中,LSM、PSO和SO算法的欧氏距离定位误差分别为0.314、 0.176、0.148 m,本文提出的改进SO算法MSSCASO定位精度更高,为0.119 m,满足室内立体定位精度要求,验证了相对于SO算法,引入改进的sine混沌映射和正余弦优化算法,能够有效改善优化算法的局部与全局寻优能力。