基于改进型遗传蚁群算法的TDOA多点定位研究*

唐菁敏，周 旋，张 伟，王朝阳，王红彬

（昆明理工大学 信息工程与自动化学院，云南 昆明 650500）

0 引 言

国内外航空运输业在近几十年来发展十分迅速。这些年，航空量大大增加，随之而来的是飞机数量的巨增，特别是大型机场，表现尤为明显。多点定位系统是通过移动物应答使得多个基站获取定位的系统。该系统通过基站获取飞机的各种应答信号，同时也可以接收ADS-B的信号，根据信号到达各个基站产生的时间差确定飞机的位置[1]。从MLAT（多点定位技术）系统优势性上分析，其具有覆盖面广、定位高精度、受环境影响小和成本低等一系列优点。将其和场面雷达相互比较，现今的场面监视选择MLAT系统会更加合适，也能够满足现在场面监视的各项不同需求[2-3]。国外较早便开始多点定位技术及算法的研究，因而其应用的多点定位算法类型较为丰富，但多数是以TDOA（到达时间差）与TOA（到达时间）为基础，以TDOA为基础的算法占比较大，以TOA为基础的算法主要包括Bancroft算法和最小二乘法，而SX和SI算法、Taylor算法、Friedlander算法、Fang算法和Chan算法等都是经典的TDOA算法。我国对MLAT系统的研究较晚，民航第二研究所在站点覆盖与精度分析技术上成功实现了使用几何精度衰减因子同地理信息系统相结合的方法，研制了ADS-B全兼容多点定位原理样机系统，实现了民航应用领域的高精度时差多点定位系统，但算法研究上并没有实现技术创新，只是针对传统经典算法开展的研究[4-6]。

多点定位系统中最常用的一种方法是利用迭代法对代数中存在的非线性等式进行求解，以泰勒级数展开法为代表。此方法需要初始猜测值作为保证，对测量误差求得其局部线性最小二乘解，从而求得更精确的估计位置。该方法的优劣很大程度上取决于初始参考点选取的优劣。初始参考点的准确与否会对算法收敛性产生极大影响，且迭代运算也会因之出现局部极小化问题，计算量大且无法保证算法收敛性[7-8]。针对上述情况，本文的改进思路是提出改进型遗传蚁群算法搜索空间最优解，并作为初始参考点对泰勒级数展开法提供辅助。首先利用正反馈机制存在的优点和改进型遗传蚁群算法表现的快速全局收敛性在空间搜寻最优解，将最优解赋值给初始参考点后，以此为基础运用泰勒级数展开法对定位坐标进行求解，如此对机场场面移动目标实现精确定位。该方法并不受迭代法无初始猜测值的限制，使得遗传算法与蚁群算法很好地融合，不仅使得蚁群算法和遗传算法在寻优过程中良好体现了各自特点，而且避免了寻优效率不高的遗传算法和寻优开始阶段信息素不足的蚁群算法存在的缺陷，拥有较好的求解效率和时间效率。该改进算法被称为基于改进型遗传蚁群算法的泰勒级数展开多点定位算法，改进思路如图1所示。

图1 基于改进型遗传蚁群算法的泰勒级数展开多点定位算法思路

此外，在TDOA多点定位算法研究中，通常假设Chan算法中定位目标距离各个基站很远，有Ri≈Ri0，Ri表示从移动目标到基站i的距离，Ri0表示定位目标和基站之间的实际距离，那么Q ≈φ，Q表示TDOA测量噪声的协方差矩阵，φ表示误差矢量的协方差矩阵。分别通过第一次和第二次加权最小二乘法（WLS）求解得出定位目标的位置坐标，则一般认为Chan算法不需要初始猜测值。但是，Chan算法中的另一种情况是定位目标距离各个基站较近时，Ri≈Ri0则不成立。此情况下，需要通过假设定位目标距离各个基站很远，估算一个定位目标的大概位置，再通过假设定位目标距离基站较远时的第一次WLS表达式，求解初始解估计矩阵B，随后将矩阵B代入分别进行第一次和第二次WLS求解，最终得出定位目标精确位置。所以，研究Chan算法可以看出，当定位目标距离各个基站较近时，第一次估算也需要初始猜测值，才能求解初始解估计矩阵B[9-10]。

本文的改进思路二是针对Chan算法中定位目标距离各个基站较近时的情况，提出改进型遗传蚁群算法搜索空间最优解，并对Chan算法提供辅助。首先利用正反馈机制存在的优点和改进型遗传蚁群算法表现的快速全局收敛性，在空间搜寻最优解；将最优解赋值作为初始猜测值，求解初始解估计矩阵B，之后以此为基础运用Chan算法进行第一次和第二次WLS求解。如此一来，对于机场场面移动目标，就能够实现精确的定位。该方法并不受Chan算法中定位目标距离各个基站较近时需要假设得到定位目标大概位置的限制，同时使得遗传算法与蚁群算法很好地融合，不仅使得蚁群算法和遗传算法在寻优过程中良好地体现了各自的特点，而且避免了寻优效率不高的遗传算法和寻优开始阶段信息素不足的蚁群算法存在的缺陷，拥有较好的求解效率和时间效率。该改进算法被称为基于改进型遗传蚁群算法的Chan多点定位算法，改进思路如图2所示。

图2 基于改进型遗传蚁群算法的Chan多点定位算法思路

1 多点定位数学模型

以TDOA为基础的双曲面定位算法，建立如下数学模型。假定目标同地面第i个接收站距离用Ri表示，则距离计算公式为：

其中，[Xi,Yi,Zi]表示地面第i个接收站的三维坐标，[x,y,z]表示目标空间位置。

定位目标与同地面第i个接收站距离用Ri表示，定位目标同地面第1个接收站（即主站）距离R1之差Ri,1计算如下：

其中，Ti,1表示定位目标至地面第i个接收站的时间同到达地面第1个接收站的时间差，c表示电波传播速度。

于是，有：

其中Xi,1=Xi-X1，Yi,1=Yi-Y1，Zi,1=Zi-Z1。所有 TDOA定位算法都时基于式（1）～式（5）进行的计算。二维空间坐标只需去除z轴坐标，即可得到类似表达式。

2 算法描述

2.1 改进型遗传蚁群算法

2.1.1 确定种群中每一个体取值范围

为了让遗传算法有更快的运算效率和更高的定位精度，本文首先确定遗传算法中种群的每一个体的取值范围。其中，每一个体即表示目标飞机初始猜测位置。设定代码如下：

FieldDR=[center-searchR;center+searchR]

其中FieldDR表示种群中每个个体的取值范围，center表示目标位置搜索中心，searchR表示搜索半径。

2.1.2 初始种群和适应度函数选取

本文采用的遗传算法需创建实值原始种群Chrom，具体代码如下：

Chrom=crtrp(cNum,FieldDR)

其中crtrp函数用来创建实值原始种群，cNum表示种群个体数。本文设定cNum值为50，即种群个体数为50。

就初始种群而言，在特定的机场场面坐标范围内，其初始猜测位置是随机产生的。为了对优化时种群个体和最优解接近的程度作出评价，本文采用ranking函数作为适应度函数。此函数是基于排序的适应度分配，即从最小化方向对个体进行排序，具体代码如下：

FitnV=ranking(E)

其中E表示种群初始能量值，是包含与基站坐标Locs、基站测量值Ms和实值原始种群Chrom有关的量。

2.1.3 遗传算子的选择

选择算子。本文选择“随机遍历抽样”方法，等距离选择优良个体向下一代群体遗传。具体代码如下：

SelCh=select('sus',Chrom,FitnV,GGAP)

其中select表示从种群中选择个体的函数，sus表示随机遍历抽样方法，GGAP表示进化比例，即为交叉概率Pc，本文设定值为0.9。

交叉算子。为了子代能够获取较优解，在其父代中选择两个最优个体让其搭配成对，在两者间通过交叉概率选定部分基因并两两交换，从而获得新的个体。

变异算子。在种群中选取遗传算法育种器的变异算子mutbga，这样种群就会更加多样，局部搜索能力也会得到很好的提升。

2.1.4 设置信息素的初始值

遗传算法具有快速全局收敛性，所以据此可得到和最优解相近的一个定位坐标。蚁群算法就是以该坐标作为信息素初始值的。对衔接点初始时刻而言，信息素有如下生成规则：

其中，τc为设置在蚁群算法路径上的信息素常量；τG为遗传算法搜索结果通过转换得来的信息素值。

2.1.5 路径选择

蚁群算法具有的正反馈机制是最明显的优势。根据之前经过的蚂蚁残留的信息素强度作出下一个节点的选择，状态转移概率函数为：

其中：Pijk(t)为在t时刻第k个蚂蚁由i节点向j节点转移的概率。τij为ij路径上残留的信息素强度。ηij为蚂蚁由i节点向j节点转移的期望度。α代表信息启发式因子，β代表期望启发式因子，allowedk代表第k个蚂蚁下一步能够选择的节点。

2.1.6 信息素更新

假设t时刻蚂蚁的一次循环已经完成，那t+1时刻信息素的更新方式为：

其中，ρ为信息素的挥发系数，且ρ∈(0,1)；Δτij代表ij路径上信息素的增量变化；第k个蚂蚁在ij路径上走过的距离长度用Lk表示，残留的信息素则用Δτijk表示，Q0(x0,y0)代表信息素强度。

本文通过改进的节点编码方式减少了传统蚁群算法的求解空间。首先蚁群算法是用来解决旅行商（TSP）等离散问题的，而本文所求定位坐标信息是连续的，故而如何将求解连续坐标问题转化为蚁群算法解决的离散问题，这是改进算法的一个重点。在实际求解过程中，遗传蚁群算法在较大的求解空间中寻优，是费时且没有效果的，基本不可能遍历所有路线，优化结果全靠遗传算法保证，蚁群算法基本不能发挥作用。通过改进其编码方式，遍历节点数大大减少，提高了搜索效率，蚁群算法可以真正遍历，甚至多次经过某路线，找到最优路线的概率大大提高。本文程序中设定遗传算法迭代次数为10次，蚁群算法迭代次数为3次。

本文的改进算法在程序设计首先利用遗传算法搜索求解得到一个初始估计值，设为P0(x0,y0,z0)。可知，遗传算法搜索结果精度可达小数点后一位。随后，将初始估计值P0(x0,y0,z0)代入蚁群算法，进一步优化各坐标值小数点后第2位开始的3位小数，此处即将得到的初始位置估计值坐标进行拆分，运用SplitT函数对位置坐标拆分，具体程序代码如下：

function num=SplitT(T)

T=abs(10*T-fix(10*T))+0.0001;

strT1=num2str(T(1),'%0.4f');

strT2=num2str(T(2),'%0.4f');

strT3=num2str(T(3),'%0.4f');

num=[str2num(strT1(3)),str2num(strT1(4)),str2 num(strT1(5)),str2num(strT2(3)),str2num(strT2(4)),st r2num(strT2(5)),str2num(strT3(3)),str2num(strT3(4)),str2num(strT3(5))];

end

其中T即表示P0(x0,y0,z0)，abs为绝对值函数，fix函数代表取整数位。

随后依据遗传算法的结果得到的拆分数据即为蚁群算法中的最优路径。以此初始化信息素，并增加该条路径上的信息素num，具体程序代码如下：

num=[0,SplitT(Ti)];num=num+1;

更新蚂蚁轨迹，合并得到新位置坐标，具体程序代码如下：

function T=CombT(Ti,num )

Ti2=fix(10*abs(Ti))/10;

T(1)=Ti2(1)+0.01*num(1)+0.001*num(2)+0.0001*num(3);

T(2)=Ti2(2)+0.01*num(4)+0.001*num(5)+0.0001*num(6);

T(3)=Ti2(3)+0.01*num(7)+0.001*num(8)+0.0001*num(9);

T=T.*sign(Ti);

end

其中fix函数代表取整数位。

最后，找出最佳蚂蚁，提高其轨迹上的信息素，记录最佳估计值，并用CombT函数得到新的初始目标P1(x1,y1,z1)，将得到数值作为初始猜测值代入泰勒算法和Chan算法求解。

2.2 基于改进型遗传蚁群算法的泰勒级数展开多点定位算法

泰勒算法作为递归算法需选定一个初始估计值。为了保证其运算速度和收敛性，应当尽量选择和实际位置较为接近的初始值。所以，以改进型遗传蚁群算法已经搜索到的P0(x0,y0)作为初始位置，对二维空间有：

在(x0,y0)处进行泰勒展开：

ψ为误差矢量矩阵，忽略二阶以上分量，有：

对式（12）采用加权最小二乘算法（WLS），可以得到δ的最小二乘估计：

其中，Q表示TDOA测量值的协方差矩阵。在第二次递归计算中，令x'=x0+Δx，y'=y0+Δy，重复计算多次，直至Δx和Δy达到足够小的水平且满那么得到的估计值可以视为飞机的估计位置。

2.3 基于改进型遗传蚁群算法的Chan多点定位算法

Chan算法中定位目标距离各个基站较远时，可以按正常算法流程进行2次WLS估计计算。但是，当定位目标距离各个基站较近时，可以通过改进型遗传蚁群算法搜索空间最优解，并对Chan算法提供辅助。首先利用正反馈机制存在的优点和改进型遗传蚁群算法表现的快速全局收敛性，在空间搜寻最优解，将最优解赋值作为初始猜测值，再求解初始解估计矩阵B，之后以此为基础运用Chan算法进行第一次和第二次WLS求解。就场面监控系统而言，考虑到大多数目标运动都是在二维平面进行，所以可以单纯从二维上考量目标定位问题，具体求解步骤如下。

先将式（2）展开可得：

误差矢量为：

其中Q表示TDOA测量噪声的协方差矩阵。

运用加权最小二乘法得到第一次WLS为：

当定位目标和各个基站的距离较近时，不可以作出Ri≈Ri0的判定。那么，通过改进型遗传蚁群算法得到一个初始解P0(x0,y0)，然后进行初始解估计矩阵B的求解，再将其代入得到第一次WLS的值。

第二次WLS。鉴于第一次WLS没有考虑R1和x、y之间的关系，此次WLS中应当考虑Ri和x、y之间的关系，让定位结果能实现更高的精确度。令P11=x0+e1，P12=y0+e2，P13=R10+e3， 其 中 e1、e2、e3表示P1的估计误差，则：0

式（28）中，x0、y0可由第一次WLS得到的P1近似估计，则ψ'的协方差矩阵φ'为：

同理，根据WLS可得：

3 仿真分析

本文假设仿真采用星型布站设计，设置在15 km×15 km的矩形区域环境内进行，类似于机场场面监视的参数。接收站点基站个数分别为4个、5个、6个和7个，分布在半径为12 km的圆上，具体分布如图3、图4、图5和图6所示。

图3 四个基站分布

图4 五个基站分布

图5 六个基站分布

图6 七个基站分布

本文仿真考虑了4、5、6、7个基站情况下的定位解均方误差。设定中心1号基站坐标为（0，0），按图6所示基站进行分布，故其余各站为相对坐标，各基站坐标值如表1所示。

表1 基站数量和基站坐标

下面针对某一选定区域对其目标位置误差予以追踪，从而验证算法性能。接收站点和图3、图4、图5和图6的分布一致。算法性能的衡量指标为定位均方误差（即MSE），可以表征定位误差具有的稳定性。

3.1 仿真实验1

TDOA的测量误差可看成是均值为0且呈理想的高斯分布，标准差分别是5 m、10 m、15 m、20 m、25 m、30 m、35 m、40 m、45 m、50 m、55 m、60 m、65 m、70 m、75 m、80 m、85 m、90 m、100 m。当参与定位的基站为4个、5个、6个以及7个时，选取图3、图4、图5和图6中所述的地面接收基站来定位目标。圆心设在1号中心基站，半径则设置为7 000 m。在该圆内随机选取104个目标位置，用MSE来评估实验结果。设置遗传算法中参数种群数M=50，交叉概率Pc=0.9，实值种群的变异算子默认mutbga，通过仿真得出在不同基站数目下，泰勒级数展开法、Chan算法、基于改进型遗传蚁群算法的泰勒级数展开多点定位算法、基于改进型遗传蚁群算法的Chan多点定位算法的TDOA定位误差和MSE之间的关系仿真结果，依次如图7、图8、图9和图10所示。

图8 Chan算法仿真结果

图9 改进型泰勒级数展开多点定位

图7 Taylor算法仿真结果

图10 改进型遗传蚁群算法的Chan多点定位

从仿真图中统计得到的实验结果数据可以总结得出，泰勒级数展开法、Chan算法、基于改进型遗传蚁群算法的泰勒级数展开多点定位算法、基于改进型遗传蚁群算法的Chan多点定位算法四种算法，在同等定位误差条件下，随着定位基站数目的增加，定位均方误差都会逐渐降低，同时伴随着定位误差的不断增加，其定位均方误差也不断增加，即四种算法的MSE随着TDOA定位误差从5 m增加到100 m的过程中不断增大，同时定位精度会随着基站个数的增加而提高。

3.2 仿真实验2

为了对四种算法在定位性能方面进行验证，在圆心设在1号中心基站的半径为7 000 m的圆内，随机抽选任意点设为初始猜测位置，对泰勒算法、Chan算法、改进型遗传蚁群算法的泰勒级数展开多点定位算法和基于改进型遗传蚁群算法的Chan多点定位算法，在基站个数不同、TDOA定位误差不同的情况下进行比较仿真。即TDOA的测量误差可看成是均值为0且呈理想的高斯分布，标准差则是5 m、10 m、15 m、20 m、25 m、30 m、35 m、40 m、45 m、50 m、55 m、60 m、65 m、70 m、75 m、80 m、85 m、90 m、100 m。圆心设在1号中心基站，半径则设置为7 000 m，在该圆内随机选取104个目标位置，用MSE来评估实验结果。用Improved图标表示改进型遗传蚁群算法的泰勒级数展开多点定位算法走势，用Improved_Chan图标表示改进型遗传蚁群算法的Chan多点定位算法走势，地面接收站按照图3、图4、图5和图6分布，得到的仿真结果如图11、图12、图13和图14所示。

图11 四个地面基站四种算法对比

图12 五个地面基站四种算法对比

图13 六个地面基站四种算法对比

图14 七个地面基站四种算法对比

从仿真图中统计得到的实验结果数据可以总结出，在同等定位误差和相同定位基站数目条件下，改进型遗传蚁群算法的泰勒级数展开多点定位算法定位均方差更小，定位性能优于其他三种算法，且四种算法的定位均方差都随着TDOA定位误差的增加而不断增加。

3.3 运算效率

为了便于统计，验证基于改进型遗传蚁群算法的泰勒级数展开多点定位算法和基于改进型遗传蚁群算法的Chan多点定位算法的运算效率，在仿真实验2的条件下对四种算法迭代1 000次的时间作了统计，具体如表2所示。

表2 算法运行时间比较/s

对改进型遗传蚁群算法的泰勒级数展开多点定位算法、改进型遗传蚁群算法的Chan多点定位算法、Chan算法和泰勒算法四种算法的仿真试验2和运算时间统计表2分析可以得到：以TDOA的测量误差可视为呈理想的高斯分布为前提，在同样的仿真条件下，Chan算法和泰勒算法都有较高的定位精度，但泰勒算法在选择初值时对真实值范围太过依赖，局限性大；改进后的两种算法均提高了定位精度，尤其是随着基站数的增加，改进后的两种算法的定位精度优势更加明显。改进型遗传蚁群算法的泰勒级数展开多点定位算法定位精度高于改进型遗传蚁群算法的Chan多点定位算法。

相对Chan算法来说，改进后的两种算法因为提高了算法的复杂度，故而有着稍低于Chan算法的运算效率。但是，和泰勒算法相比，改进算法平均都有近1倍的提升，改进型遗传蚁群算法的泰勒级数展开多点定位算法运行效率要低于改进型遗传蚁群算法的Chan多点定位算法。

另外，基站个数越多，四种算法自身的定位精度也会越高；TDOA测量值定位误差越大，其精度会越小。同时，相较于泰勒算法、Chan算法来说，改进后的两种算法有着更高的定位精准度，算法也趋于更加稳定。运算效率相较于单一的泰勒算法来说，也处于较高水平。总体而言，改进后的两种算法虽然增加了算法的复杂度和算法运行时间，但获取了更优的定位精度，性能总体较优，具有一定的实际应用意义。

4 结 语

民用航空交通运输业伴随着中国综合国力的日益增长，发展势头迅猛。因此，更好地管理空中交通变得越来越重要，这激增了空中安全压力。为了能够提高航空安全水平，保障空中的绝对安全，需要不断加大对新一代监视技术的研发投入，而多点定位系统是其中重要的一项技术，具有定位精度较高、安装方便等特点，被广泛应用于世界各国。本文通过探讨两种传统泰勒和chan算法的优缺点，相应提出了基于改进型遗传蚁群算法的泰勒级数展开多点定位算法和基于改进型遗传蚁群算法的Chan多点定位算法，避免了两种传统经典算法存在的局限性。在假设确定的相同仿真条件下，对两种改进算法从定位精度和算法运行效率两个方面进行仿真实验，探讨了两种改进算法具有的优缺点，验证了改进算法的有效性和可靠性，提高了定位精度。但是，本文未考虑其他因素影响，在今后多点定位算法研究中还需综合考虑。