一种基于改进天牛须探索算法的多点定位算法

甄 然，王振博，阚海龙，倪永婧

(1.河北科技大学 电气工程学院,河北 石家庄 050018;2.河北科技大学 信息科学与工程学院，河北 石家庄 050018)

随着经济社会及人工智能的发展，定位的重要性越发得到展现。而在定位中，即使是卫星定位，算法也是当之无愧的重中之重。因此，越来越多的研究者对定位算法进行研究与改进，得到了许多创造性的成果，比如Chan-Taylor联合算法[1-2]和WiFi定位[3]等。

智能优化算法的提出，为一系列复杂问题的解决提供了思路。智能优化算法对目标函数和约束的连续性与凸性没有任何要求，有时连有没有解析表达式都不要求，对计算中数据的不确定性也有很强的适应能力，因此受到研究者的喜爱，将粒子群算法[4]和卡尔曼滤波算法[5-6]等优化算法与定位算法进行融合，进而对目标进行定位。

天牛须探索(Beetle Antennae Search,BAS)算法是2017年提出的一种生物启发的智能优化算法[7]，是利用天牛觅食原理启发而开发的算法，适用于多个领域的问题优化[8-13]，同时该算法也可以与多种优化算法进行融合，比如遗传算法[14]和神经网络[15]等，从而改善收敛性，提高优化性能。

在定位领域，由于天牛自身大小的原因，BAS算法如果不进行改进则不适用于大空间远距离定位，因此大部分研究者运用BAS算法进行室内短距离的定位，邹东尧等[16-17]将BAS算法与RSSI算法进行结合，提出运用BAS优化的室内定位算法，刘影等[18]提出普适的基于天牛须寻优的室内定位算法。

Chan算法作为基本的TDOA定位算法，虽然有着在非视距环境下定位误差较大的缺点，但是由于其经济性强、非常适合工程实际，一直以来都被进行研究，如魏振婷等[19]提出的基于自适应误差模型的改进Chan算法。

大多数研究针对某种算法的优化时采用的是结合另一种优化算法，而未能对该算法进行深入研究，或者是仅对算法进行数学上的改进但却未能结合实际。对此，针对BAS算法因为天牛自身大小不能在远距离定位中应用的问题，本文对BAS算法本身进行了结合定位实际的适当的改进，提出了一种基于Chan算法的改进BAS算法。

本算法具有以下几个优势：

① 通过将大空间远距离的定位转换为小空间近距离的定位，可以将原本仅仅适用于室内近距离定位的算法(如BAS算法)应用于远距离定位[20]。

② 因为BAS算法收敛速度快，因此本算法运行时间较短，并且可以较好地定位目标点。

③ 增加了一个对步长的选择过程，与卷积神经网络的训练过程相似[21]，可以选取合适的步长来对目标点进行定位，准确度更高。

④ 本文选择的2种不同精度的定位算法为Chan-Taylor算法和卡尔曼-Chan算法，经过改进的BAS算法具有一定的普适性，初始的2种不同精度的定位算法可以是任何2种算法，初始定位算法越精确，最终的结果也会越精确。

Chan算法是一种基于TDOA技术，具有解析表达式解的定位算法。该算法可以分为2部分：第一部分是利用待定点到各个基站与待定点到达参考基站的时间差求出各个基站与待定点相对于参考基站的距离差；
第二部分是利用这些距离差，采用最小二乘法进行定位。Chan算法的具体步骤如下。

由于定位时常是在三维环境下进行的，因此对三维环境下的定位进行分析，三维环境下的基站系统如图1所示。

图1 三维环境下的基站系统Fig.1 Base station system in 3D environment

用方程对图1进行描述：

(1)

式中，(x,y,z)为目标位置；
(xi,yi,zi)为地面站坐标；
Ri为目标点到第i站间的距离；
Ri,1为目标点到达主站与第i副站间的距离差；
c为无线电磁波传播速度；
τi,1为飞机发出的信号到达主站与第i副站间的时间差。

对于求解式(1)中的未知量，当基站数量大于维数与1的和时，可以利用加权最小二乘(WLS)法进行求解。而Chan算法利用将R1视为已知量，则式(1)为x,y,z的线性方程，经过计算，求得：

(2)

将式(2)代入R12=(x-x1)2+(y-y1)2+(z-z1)2中，整理得到：

(3)

当N2-4MK=0时，即R1解唯一，定位有效，且目标位置唯一。

当N2-4MK>0时，R1有2个解，如果2个解一正一负，取正解作为R1的真实值；
如果同为正或同为负，即存在模糊解，则需要根据其他条件进行判定。

当N2-4MK<0时，无解，定位不能实现。

求解出R1的值后，根据R1的方程和BSi坐标就可以求得目标T(x,y,z)的值。

Chan算法的定位原理如图2所示。

图2 Chan算法的定位原理Fig.2 Positioning principle of Chan algorithm

d1,d2,d3分别为目标点到各个基站之间带有误差的距离，由于误差的存在，实际计算所得到的是2条带状区域的重合部分。

Chan算法的简洁十分适合工程实际，因而一直被广泛研究。本文基于Chan算法，利用2种不同精度的Chan算法，结合2017年提出的BAS算法，提出基于Chan算法的改进BAS定位算法，将原本仅适用于短距离定位的BAS算法应用于远距离定位。

2.1 BAS算法

BAS算法是2017年提出的生物优化算法，该算法的原理是天牛在搜寻食物的过程中，根据左右两须探测到气味的强弱程度进而决定向左还是向右前进，并最终找到整个区域内气味最浓的点。针对BAS算法，结合Chan算法和TDOA思想，对BAS算法进行改进，使其能够更好地适应大空间定位。BAS算法概述如图3所示。

图3 BAS算法概述Fig.3 Overview of BAS algorithm

根据BAS算法原理，建立天牛模型，模型如下所示：

① 确定天牛的初始位置：与当前多数的随机给定初始位置的方式相比，为了减少无用的探索，改进的BAS算法采用Chan-Taylor算法对目标点进行一次定位，并将该点定为天牛的初始位置Q。同时,确定天牛左右两须的位置坐标:

(4)

式中,Xl为天牛左须的坐标;Xr为天牛右须的坐标;d0为天牛须的长度;t为天牛的方向向量。

② 通过适应度函数p获取左右两须的函数值，并朝着对应须的方向进行移动。比较p(Xr)与p(Xl)的大小。若p(Xr)>p(Xl)，则天牛向着右须方向行进步长step;反之，天牛则向左须方向行进步长step。

③ 按照上面的步骤进行迭代，直至找到目标函数W值最优的点，即为目标点。

BAS算法的流程如图4所示，本文针对其中的部分步骤进行改进。

图4 BAS算法流程Fig.4 Process of BAS Algorithm

2.2 对初始位置的改进

当前,多数优化算法对于初始位置采用的是随机赋值的方式，对于原始的BAS算法，针对初始位置同样采用的是随机赋值方式。但是这种方式下，在增加全局探索的同时，增加了较多对无用区域的探索。在数学上，增加全局搜索能力对最终结果的确定有着极大的好处，但是在定位领域，真正有用的探索区域是目标点附近的区域。初始值设在目标点附近与设在远离目标点的位置，对算法的后续迭代会有很大的影响。人是通过参照物来确定自身的，定位同样如此，通过把初始位置作为参照物或参考点，能够使其移动更加准确。

因此，改进的BAS算法采用一次定位的方式来确定天牛的初始位置。通过对目标点进行一次定位，并将该点定为天牛的初始位置Q。通过一次定位，减少天牛对无用区域的探索。以二维平面为例，对于天牛初始位置，经过一次定位所确定的初始位置距离目标点相对较近，而采用随机设定方式所确定的初始值距离目标点相对较远。探索范围对比如图5所示，在40 000 m×20 000 m的平面进行定位，若设中心点为目标真实位置，则经过一次定位所确定的范围可以用内部圆来进行表示，而随机赋值所确定的范围则为外部圆所表示的区域。很明显，经过一次定位后，算法的无效探索范围得到极大程度的减小，相对的，算法运行时间和准确度等也会得到一定程度的提高。

图5 探索范围对比Fig.5 Comparison of exploration areas

2.3 对位置更新公式的改进

BAS算法的位置更新式为：

A=A+step×(-1)×t×sign(p(l)-p(r))+

0.05×rand(1)。

(5)

改进的BAS算法的位置更新式为：

A=A+(step/cos(θ))×(-1)×t×

sign(p(l)-p(r))+0.05×rand(1)，

(6)

式中，t为天牛的行动方向，由初始随机设定；
p(l)和p(r)为左右两须的适应度函数；
A为天牛的位置；
θ为天牛当前位置与一次定位点之间的夹角。

假设天牛的初始位置为A，迭代次数为(n1+n2)，其中朝左移动n1次，朝右移动n2次，每次移动的步长为step，运用BAS算法的最终结果为：

A=A+step×t×(n2-n1)。

(7)

运用改进的BAS算法的最终结果为：

A=A+step×t×[(cos(θa1)+…+cos(θan2))-

(cos(θb1)+…+cos(θbn1))]，

(8)

式中，a1,a2,…,an2为向右移动的次数；
b1,b2,…,bn1为向左移动的次数。

相对于原始的BAS算法，经过改进后，每次移动的距离随着角度的变化而随时变化，避免了BAS算法初始步长因子随机设定而造成的移动距离与实际不适应的问题，增强了算法的自适应能力，也可以避免采用时变步长造成探索区域不适应的问题。

对式(7)进行分析，若n2=n1，则经过(n2+n1)次迭代后，天牛相当于未移动，导致定位失败，但是经过改进后，如式(8)，由于角度在实时变化，即使n2=n1，天牛的最终位置也会有所变化。

2.4 对步长的改进

根据对BAS算法的理解可以得出，假设天牛的初始位置为A，迭代次数为(n1+n2)，其中朝左移动n1次，朝右移动n2次，每次移动的步长为step，则天牛的最终位置为：

A+step×t×(n2-n1)。

(9)

因此，对于BAS算法，影响其定位精度的因素可以分为3部分：迭代次数、初始位置和每次移动步长。其中，初始位置由一次定位确定，误差一定，所以主要影响因素是迭代次数和每次移动的步长。

BAS算法的迭代次数一般为20，因此主要考虑步长的影响。

对于步长，基于对卷积神经网络训练行为的理解，对改进的BAS算法采用增加一个对于移动步长的训练部分的方式，借鉴卷积神经网络通过训练集来对整个网络进行训练即可使网络逐渐适应实际情况的思想，选取多个步长，对于一个在2次定位结果范围内的训练点进行定位，找到适合的步长，再对目标点进行定位。

当前，有研究者提出采用时变步长的方式，就是随着迭代次数的增加步长逐渐减小，此步长变化方式在定位领域可能会造成探索区域减小的问题，进而影响定位精度，且步长与迭代次数之间的变化关系随着定位地点和天牛初始位置等一些其他因素的不同，会有一定的变化，确定步长和迭代次数二者关系较为复杂。

步长的大小决定算法探索的密度，与初始值结合在一起决定算法的探索区域。优化算法本质上是对探索区域内的尽可能多的点进行验证，但是这并不意味着步长越小越好。步长的选择要与初始值一起考虑，即：

K=f(A,step)，

(10)

式中，f为一个未知的函数关系，且在一定范围内该函数关系可以认为不变。正因为如此，通过对2次定位确定的范围内的一个确定点进行训练定位，可以通过对该点的定位确定f的关系，进而选择出适合的步长对目标点进行定位。

2.5 改进BAS算法步骤

综上所述，改进BAS算法的具体流程如图6所示。

图6 改进BAS算法流程Fig.6 Process of improved BAS algorithm

远距离定位时，采集到的数据有一定程度的非视距误差，因此首先利用卡尔曼滤波的方式，适当降低该误差对定位的影响。然后，利用2次定位的方式，对目标点进行范围定位，将目标点确定到一定的范围中，同时，对天牛的初始位置进行赋值，而不是采用随机赋值的方式对天牛的初始位置进行赋值。这样可以降低系统对无用区域的探索，同时也可以避免对某些区域进行探索时陷入局部最优的情况。

利用2种不同精度的Chan算法对目标点进行定位，将其中一个结果作为待定点的一次定位结果Q，将另一个结果作为天牛的初始位置A，这样可以将大空间远距离定位转换为小空间近距离定位。然后，利用BAS算法，进行优化，待定点的具体位置就是天牛要寻找的食物。假设在整个定位区域内共有n个基站对该目标进行定位。

该算法的目标函数W为：

(11)

式中，(Qx,Qy)为一次定位点Q的坐标；
(x,y)为经过BAS算法的最终结果，直至迭代结束，找到目标函数值最小的点，即为所求。同时，该算法的适应度函数p为：

(12)

式中，h为一次定位点到各个基站与到参考基站之间的距离差；
s为天牛左须和右须各自到各个基站与到参考基站之间的距离差。

基于Chan算法的改进BAS定位算法定位的具体步骤如下：

步骤1 利用TOA的方式采集数据。

步骤2 根据接收到的信号对目标点进行2次定位，将其中一个结果作为待定点的一次定位结果Q，将另一个结果作为天牛的初始位置A，确定目标点的大致范围。同时，在该范围内随机选择一个点作为训练点，然后,对训练点进行二次定位，为训练过程做准备。

步骤3 首先改进BAS算法的位置更新公式。在k维空间中，待定点的初始方向用一个矩阵t表示，本文中，将该矩阵设为t=[1,1，…]，即将天牛的初始方向始终设置为朝着各轴的正方向。同时，根据天牛自身的特点，写出其左右两须的坐标方程：

(13)

式中，A为天牛的初始位置，由步骤1所得，是[x,y，…]，由所需探测空间的维数确定；
d0为天牛左右两须之间固有的距离；
A1与Ar分别表示天牛左右两须的坐标。根据左右两须各自的适应度函数和一次定位点Q,求出左右两须的适应度函数值，然后确定天牛下一步的行动，确定天牛的位置方程为：

A=A+(step/cos(θ))×(-1)×t×

sign(p(l)-p(r))+0.05×rand(1)，

(14)

式中，p(l),p(r)，分别为关于左右两须的适应度函数；
θ为一次定位点与天牛主体之间的夹角，用来调整天牛的移动方向。

步骤4 训练改进的BAS算法，找到最优步长。具体方式为选取多个步长，再根据训练点的2次定位结果，采用改进后的BAS算法对该点进行定位，找到最优步长。

步骤5 将找到的最优步长带入到改进后的BAS算法中，对目标点进行定位。

改进BAS算法定位的具体流程如图7所示。

图7 改进BAS算法定位的具体流程Fig.7 Specific process of improving the positioning of BAS algorithm

为了验证该算法的准确性及对定位结果的优化，使用Matlab 2019a对该算法进行仿真实验。误差选用均值为10的高斯白误差。

4.1 算法改进前后的性能分析

4.1.1 初始位置的改进

对于初始位置的选择，仿真验证采用Chan-Taylor联合算法，用该算法对目标点进行一次定位，将该点作为天牛的初始位置点，以减小天牛在无效区域的探索。

初始值的设定，标志着探索范围的确定。在定位领域，真正有用的探索区域是目标点附近的区域。对BAS算法的初始值分别采用随机赋值和经过一次定位赋值2种不同的方式，其他均不变，连续定位多次。然后，采用平均定位误差作为评判好坏的标准。先对小空间进行考虑，设小空间为50 m×50 m的范围，其仿真结果如图8所示。

图8 小空间对比结果Fig.8 Small space comparison results

同样，对大空间进行考虑，设大空间为50 000 m×50 000 m的范围，其仿真结果如图9所示，各仿真误差如表1所示。

图9 大空间对比结果Fig.9 Large space comparison results

表1 初始值与误差Tab.1 Relationship between the initial value and error 单位：m

对表1中的数据进行分析，因为每一列的随机误差相同，但是每一行随机误差不同，因此对表1各列进行分析，可以看出在选择相同的迭代次数的情况下，初始值对于优化算法而言是很重要的，随机赋值的方式虽然可以增加算法的全局搜索能力，但是在定位方面是无用的，甚至是有害的。在定位范围较大的空间，采用随机赋初始值的方式会让优化算法定位的结果出现较大失误。

4.1.2 位置更新公式的改进

对位置更新公式进行修改，使每次移动的距离随着运行的推进而结合实际不断地变化，可以有效地避免未改进的每次移动均为固定移动距离而与实际不适应的问题，也可以避免采用时变步长造成的探索区域不适应问题。

为了验证仿真改进后的位置更新公式是否有效，采用2种不同的位置更新公式，对同一个目标点进行定位，最终取定位误差作为评判标准，其中天牛的初始位置采用一次定位确定，仿真采用50 000 m×50 000 m的空间。仿真定位结果如图10和图11所示，定位误差如表2所示。对于表2，因为每一列的随机误差相同，但是每一行随机误差不同，因此对表2各列进行分析，可以看出，位置更新公式的改进对于定位准确度同样有一定程度的提升。

图10 二维环境下不同的位置更新公式的定位结果Fig.10 Positioning results of different position update formulas in 2D environment

图11 三维环境下不同的位置更新公式的定位结果Fig.11 Positioning results of different position update formulas in 3D environment

表2 不同的位置更新公式对应的定位误差Tab.2 Positioning errors corresponding to different position update formulas 单位：m

4.1.3 步长的改进

对BAS算法与Chan算法进行了深入研究发现，步长也是影响BAS算法的主要因素之一，因此对步长进行一定的调整与改进。

神经网络可以通过训练来使其拟合度提高，更加适合实际。但是，由于神经网络的复杂性与定位要求的短时间需求，因此对BAS算法采用训练的方式，选择多个步长，提前对一个训练点进行尝试性的定位，找到最适合的步长，然后再对目标点进行定位来降低误差。

首先是二维环境下的仿真，目标点随机设定，误差采用高斯白误差，经过多次仿真发现，经过训练的BAS算法与Chan算法的融合算法误差相较于未经过训练的BAS算法与Chan算法的融合算法有很大程度的降低,仿真结果如图12所示。在三维环境下的仿真，目标点随机设定，误差采用高斯白误差，经过多次仿真发现，经过训练的BAS算法与Chan算法的融合算法误差相较于未经过训练的BAS算法与Chan算法的融合算法有很大程度减小。其中一次的仿真结果如图13所示。

图12 经过训练与未经过训练的天牛须-Chan算法的定位结果对比(二维)Fig.12 Comparison of positioning results of trained and untrained BAS-Chan algorithm(2D)

图13 经过训练与未经过训练的天牛须-Chan算法的定位结果对比(三维)Fig.13 Comparison of positioning results of trained and untrained BAS-Chan algorithm(3D)

未经过训练与经过训练的BAS算法的误差如表3所示。

表3 未经过训练与经过训练的BAS算法的误差Tab.3 Error comparison of untrained and trained BAS algorithm

因为每一列的随机误差相同，但是每一行随机误差不同，因此对表3各列进行分析，可以看出，步长是影响BAS算法定位精度的重要因素，增加一个训练部分，以一个训练点提前确定适合的步长，对于更好地定位有着很大的意义。当步长选择不合适时，定位会出现相差极大的情况，在相同的采集数据前提下，经过一个训练，选择合适的步长，虽然增加了一定的运行时间，但是可以有效地降低最终误差。

4.2 改进BAS算法与粒子群算法对比

粒子群算法(PSO)是于1987年提出的优化算法，经过多年的发展已广泛地应用于多个领域，在定位领域也有所应用。对PSO中粒子初始位置同样也采用一次定位方式进行设置。对于改进BAS算法结合Chan定位和PSO结合Chan定位的对比，分别在二维和三维环境下验证，二维空间采用50 000 m×50 000 m的空间，三维空间采用50 000 m×50 000 m×50 000 m的空间，目标点采用随机赋值的方式给定，BAS算法的迭代次数选择20，PSO的种群数量选择为50。

二维环境下，目标点随机给定，粒子群-Chan和天牛须-Chan两种算法同时对目标点进行定位，误差采用高斯白误差。当PSO的迭代次数为200而BAS算法为20时，仿真结果如图14所示。

图14 2种优化算法与Chan算法结合后的定位结果对比Fig.14 Comparison of the positioning results of the two optimization algorithms combined with Chan algorithm respectively

当PSO的迭次数与BAS算法的迭代次数相同，均为20时，仿真结果如图15所示。

图15 2种优化算法与Chan算法结合后的定位结果对比Fig.15 Comparison of the positioning results of the two optimization algorithms combined with Chan algorithm respectively

在三维环境下对同一随机目标点进行定位时，当PSO的迭次数与BAS算法的迭代次数相同，均为20时，仿真结果如图16所示。当PSO的迭代次数增加至200而BAS算法为20时，仿真结果如图17所示。

图16 2种优化算法与Chan算法结合后的定位结果对比Fig.16 Comparison of the positioning results of the two optimization algorithms combined with Chan algorithm respectively

图17 2种优化算法与Chan算法结合后的定位结果对比Fig.17 Comparison of the positioning results of the two optimization algorithms combined with Chan algorithm respectively

BAS算法与PSO在不同环境下的误差对比如表4所示。

表4 BAS算法与PSO在不同环境下的误差对比Tab.4 Error comparison between the BAS algorithm and particle swarm algorithm in different situations

因为每一列的随机误差相同，但是每一行随机误差不同，因此对表4的各列进行分析，可以看出，虽然BAS算法提出的时间不长，但是BAS算法与Chan定位可以很好地结合，效果比提出多年的PSO与Chan定位的结合算法好。同时，由PSO的定义可以得出，随着迭代次数的增加，PSO的精度将会上升，但是随之而来的是运行时间的增加。BAS算法的收敛性很好，在较短的次数内就会收敛，此时即使增加迭代次数，其影响并不会很大，在这个方面，BAS算法更具有优越性。

经过对各个算法改进前后的对比仿真可以看出，经过改进的BAS算法适用于远距离定位，且精度相较于未改进的BAS算法有很大的提升。经过PSO与改进BAS算法的对比仿真可以发现，改进BAS算法增加的训练部分可以有效地减小误差，并且不会对运行时间有较大的影响。同时，相比于PSO，BAS算法仅仅一个天牛，大大降低了运行时间和迭代次数。对于天牛初始位置的确定，一次定位结果的确定，不仅可以使用Chan算法及其优化算法，还可以使用其他定位算法。随着定位算法的更新以及精确度的加强，定位结果将得到更好的提升。

经过对初始位置、位置更新公式以及步长的改进，BAS算法改善了其不能应用于远距离定位的问题，且定位精度得到一定的提升，相较于PSO等更有着消耗时间短的优点。

当前，主要是通过事先设定不同数量级的步长，然后通过对训练点的定位来确定最适合的步长，步长的选择有一定的局限性，如何在满足定位时间的需求下选择合适的步长，以及训练点的确定方法和天牛的行进策略的改进将是接下来需要完成的工作。