陈光武， 佘一鸣， 杨菊花， 任 超

(1.兰州交通大学 自动控制研究所，甘肃 兰州 730070；2.甘肃省高原交通信息工程及控制重点实验室，甘肃 兰州 730070)

0 引 言

到达时间差(time difference of arrival,TDOA)技术在无源定位中具有对硬件要求低、不需要特定的时间戳要求以及精度较高的优势。目前对于TDOA问题的研究有多种方法，一般来说较为常见的有泰勒级数展开法[1,2]，这种方法的缺点就是迭代初期的初值必须有一定的准确度，否则容易出现算法不收敛的情况。此外，解决这类问题较为常见的还有最小二乘算法。例如：约束总体最小二乘法，顺序最小二乘法等[3～5],这些算法也是处理定位问题的传统方法。这类算法的优势在于速度快，计算量少，在噪声较小时定位精度较高，是当前研究较为成熟的方法。文献[6]提出一种约束最小二乘法，针对约束最小二乘无源定位算法中最优 Lagrange乘数的求解问题，提出了新的计算方法。2014年，曲付勇等人[7]提出的基于约束总体最小二乘法的方法，使非线性问题转变为带约束条件的最小二乘模型问题，将约束最小二乘定位解作为约束总体最小二乘的定位解。以上这些针对最小二乘法的改进方法虽然在噪声较小时精度很高，但是却有两个显著的不足：1)这类算法在计算过程中含有求逆矩阵的步骤，为了使矩阵不出现奇异，必须通过增加观测站来提升精确度，在三维情况中，在基础原理上至少需要4个观测站才可满足条件，对于改进算法所需的观测站最少也得5个才可比较精确地找到位置；2)这类方法只能用于噪声较小的环境，否则就会出现门限效应，从而导致精度大幅度下降。

除去上述的各种解析法以外，还有智能优化算法被运用到这一问题的解决，2005年李俊峰等人[8]提出利用粒子群优化算法去解决TDOA问题。2017年刘宝生等人[9]提出利用遗传优化算法对时差问题求解，但其算法的计算量较大。这类使用智能优化算法的方法首先在搜索范围内初始化大量的随机点，通过建立符合要求的适应度函数来筛选合适的随机点，然后利用迭代过程在这些较好的随机点中找出最优解，这个解即为目标位置。这种方法不存在矩阵求逆的过程，所以，对基站个数的要求较最小二乘的方法少。

目前使用智能算法处理TDOA问题时一般会出现算法后期收敛太慢，陷入局部最优解的问题，还有一些智能算法的控制参数过多，不但加大了调整参数的难度而且还使得计算速度减慢，所以，找到一种针对这类问题的合适的智能算法显得十分重要。

2016年，澳大利亚学者Mirjalili S根据座头鲸的捕食行为，提出了一种新的群体智能算法即鲸鱼优化算法(whale optimization algorithm，WOA)[10]。这种全局搜索算法的优势在于结构简单，调节的参数少，运算速率快，也间接减少了参数影响问题。本文将改进WOA(improved WOA,IWOA)应用于三维时差定位，通过对适应度函数和初始化的调整，使其更加适合时差问题的解决，并将IWOA算法与其他智能优化算法进行性能比较。

1 多站TDOA定位模型的建立

在三维时空中建立时差观测模型，假设存在M个观测站，设定基站的位置Si=[xi,yi,zi]，i=1,2,…,M，目标位置L=[x,y,z]。观测目标发出的信号到达基站时间ti为

(1)

(2)

eri=ceti

(3)

ri,j=c(ti-tj)=c(ti+eti-tj-etj)=ri+eri-rj-erj

(4)

即

(5)

为了使得似然函数取得最大值，相当于求解式(6)

(6)

2 IWOA

2.1 种群初始化优化

将寻找目标位置的空间假定为一个N×M维的，N代表的是种群数量，M则代表空间的维数，Lm和Um分别表示空间的上下限，m=1,2,…,M，初始化种群的初始位置依据式(7)在空间中随机产生

Xim=Lm+rand(1,3)(Um-Lm)

(7)

初始化的种群散布情况对接下来的搜寻过程有着较大影响，大部分智能算法采用随机分布，本文则采取复杂程度较低的Chan算法[11]先去生成一个初始解，将这个解去替换掉初始种群中的一个随机解，对初始种群进行优化处理。因为初始解比较接近最终估计解，所以,全局搜索的效率会提升。

2.2 改进适应度函数

2.2.1 针对基站不同影响问题

根据式(6)可以看出，传统的解析法对于这个问题的求解较为复杂，本文利用IWOA对其求解，可以根据式(6)得出适应度函数

(8)

式中X为位置矢量，适应度函数的构建将会对算法产生较大影响，结合式(2)可以得出如下结论：主基站的到达时间t1对式(8)中的每一项都有作用，但是从基站的达到时间ti则对其中的i-1项有影响，可知主从基站存在差异，主基站的影响较大，假如主基站的测量误差较大，那么对于适应度函数将产生很大影响。

所以做出进一步改进，改进的适应度函数为

(9)

利用式(9)将每个基站作为主基站去处理，消除了主从基站差异。筛选出其中的最小值作为改进的f(X)代入方程，具体公式为

f(X)=min[f1(X),f2(X),…,fM(X)]

(10)

(11)

2.2.2 针对优化算法调整

在此基础上对其进一步改进，通过引入惯性权重因子ω协调全局和局部性能。具体如下：在运算过程中，将各个个体的适应度值按大小进行排序，将序列分割成两部分，分别计算平均数值fa1fa2(fa1

1)f(i)

此时的个体适应度优于较好平均值，说明此个体的质量较好，此时应该在其附近进行小范围运动，有利于对局部的搜索能力提升，所以,ω取值(0.8,1.2)之间的随机数。

2)f(i)>fa2

此时个体的适应度比较差群体的平均值还差，说明其位置不好，个体应该在大范围移动去寻找有利位置，故此时ω以50%概率选择(0.3,0.6)或者(1.3,1.6)之间的随机数。

3)f(i)介于两数值之间

此时个体的适应度数值不好也不坏，按照一般规律运动即可。ω取值为1即可。

2.3 WOA的优化

WOA主要分为3个部分：包围收缩、觅食以及螺旋式更新。

2.3.1 包围收缩

座头鲸识别猎物并且将其包围，在此过程中以鲸群中处于最佳的捕食位置作为目标或最接近目标的位置，其他鲸鱼向其移动，其表达式为

(12)

A=2ar-a

C=2r

(13)

式中a为一个控制变量，取值通过a=2-2t/tmax形式变化，tmax为最大迭代次数，r为(0,1)间随机数。

2.3.2 觅食搜索

在此阶段进行随机搜索行为，表示如下

(14)

2.3.3 螺旋式更新

此阶段是模仿座头鲸狩猎中，鲸鱼通过螺旋移动方式向着最优解靠近，数学模型建立如下

(15)

(16)

其中，第i个鲸鱼目前位置和最佳个体的距离关系，b为个螺旋形状参数，l为(-1,1)间的随机数。

此时的鲸鱼不仅要以螺旋形式游动而且要收缩包围猎物，其通过50%的概率在螺旋游动和收缩包围两种机制之间进行位置变化，表示如下

(17)

其中，p为(0,1)间随机数。

2.4 IWOA算法步骤

使用IWOA算法针对TDOA定位问题的具体步骤如下：

1)初始化种群和各个参数。根据式(7)随机初始化种群个体，然后如2.1节所述，通过使用Chan算法产生一个初始解去替换种群中一个随机的个体；

2)对种群计算适应度。通过式(10)分别计算出当前个体的适应度值，记录其中的适应度最优值个体位置；

3)开始迭代，当t

4)位置更新。使用式(17)通过p值选择行为机制；

5)计算更新后种群的适应度,通过适应度数值比较进行位置替换；

6)重复步骤(3)～步骤(5)，直至算法到达迭代次数的门限，输出最优食物位置以及其适应度取值,此时的猎物位置就是目标的估计位置。

3 实验的仿真结果与分析

3.1 收敛性能分析

本文设定三维时空模型，在此条件下，通过与常见的粒子群(PSO)算法及其改进权重的粒子群(IPSO)算法，遗传算法(GA)，经典WOA进行对比，验证IWOA对于TDOA非线性问题求解的性能，仿真实验的环境设定如下：基站按照Y型分布，在地上的基站的坐标分别为，主观测站S1=[0,0,0]，从观测站S2=[0,15,0]，S3=[-10,10,0]，S4=[-10,-10,0]，目标位置L=[80,55,20]，单位km。

种群数为40，迭代上限为500，以此条件进行迭代运算，以反应其不同算法针对TDOA问题计算的特性，结果如图1所示。

图1 算法迭代对比

从图1中可以看出，经过500次的迭代过程，曲线均是可以收敛的，前期过程中可以看出，IWOA算法由于引入了初始解，初始种群更接近全局最优解，其搜索范围相比其他算法更有效，效率也较其他算法有提升，减缓了智能算法迭代次数多的劣势。其他算法由于前期过程需要在整个空间中做充分的全局搜寻工作，所以，需要进行更多次迭代才可以收敛到较小值。

在迭代的后期，IWOA相比于经典WOA采取了一种新的适应度函数策略，其对个体位置好坏的评价标准更准确，使得算法可以收敛到更低的适应度值，而其他智能算法都是采用一般的适应度函数，所以其最后收敛结果近似且高于IWOA。在后期，IWOA的适应度已经明显低于IPSO算法了，此外值得注意的是，在仿真的过程中，PSO及其IPSO算法，GA很容易出现问题，会出现因为参数设置问题导致收敛结果出现问题，而且这类智能算法的参数比较多，对收敛的速度和效率的影响较大，在实际中找到最优参数是很困难的，IWOA在这一方面与其相比有着明显的优势。

3.2 精度分析

为了观察算法在位置判断中的精确性，对不同位置的目标源进行位置判断，采用Monte-Carlo方法仿真统计各个算法的定位正确率。仿真条件为，上界ub=[100,100,50]，下界lb=[-100,-100,0]，单位km，最大迭代次数600次，种群数40，对各个目标源进行5000次的Monte-Carlo仿真实验，并与WOA，PSO及其IPSO算法进行比较，设定距离超过15 m即为错误，实验结果如表1所示。

表1 定位正确率 %

从表1中可以看出，在目标位置较近的情况下，几种算法的准确率都是比较高的，当目标源位置开始变远时，几种算法便出现差异性，PSO算法和WOA的正确率开始降低。IPSO通过改进线性权重，在迭代后期，其由于权重数值变小，个体的移动步长也随其减少，所以在后期时其强于PSO算法，另外PSO算法的过程中很容易陷入到局部极值之中，所以其准确率较低。

相比于PSO及其改进算法，IWOA更适合处理TDOA定位问题，其算法中特有的搜索策略使得权值随适应度函数值随机调整，使得种群在寻优中更加多样化，即增强了全局搜索的随机性，提升全局搜索能力，平衡了局部探索和全局最优的问题。从结果看出，条件相同时，IWOA的准确率较高，其面对不同的目标位置时，算法的稳定性也比较好。

图2 实验结果

根据试验结果可以看出，在目标较近时，几种算法都没有出现太大的波动，IWOA比较贴合克拉美罗界，其他算法曲线相比之下略高于IWOA曲线。对于远场的目标，IWOA的精度更高，可以更好地接近克拉美罗界。综上，IWOA的稳定性较好，精度更高。另外，由于PSO及其改进算法，GA等涉及参数较多，且选取适合的参数需要更多的条件，所以复杂度较大，而IWOA的参数较少，且由于改进了适应度函数，计算结果更为准确，相对其他算法结构简单，且精度更高。在所选试验误差功率下，实验中几种算法没有出现因门限问题导致的大幅度曲线波动，曲线变化较平稳。

4 结束语

本文针对时差定位非线性问题使用了一种新型的鲸鱼优化算法(IWOA)，通过对初始种群和适应度函数的调整，使得本文算法更加贴合定位问题。通过与其他智能优化算法的定位性能比较，结果表明，IWOA具有结构简单，计算效率较高，定位的精度高且稳定性好的优势，对于实际利用基站定位有一定参考价值。