数据链系统的航迹关联方法

摘 要：针对数据链系统中多平台多目标情形下航迹关联较为复杂的特点，提出一种基于加权最小二乘估计和蚁群算法的航迹关联算法，并建立了多平台多目标航迹关联处理模型。为了使蚁群算法能够满足数据链实时性的要求，对蚁群算法进行了改进。通过设置参数的取值使算法能够适用于不同的战场环境和量测误差。对新提出的航迹关联算法进行了Monte Carlo仿真，结果表明了算法的有效性和可行性。

关键词：数据链； 加权最小二乘估计； 蚁群算法； 航迹关联

中图分类号：TN911-34文献标识码：A

文章编号：1004-373X(2011)09-0006-04

Method of Track Association in Tactical Datalink

LIN Ji-feng1, ZHOU De-yun1, LU Hua1,2

(1. Northwestern Polytechnical University，Xi’an 710072，China； 2. Xi’an Institute of Applied Optics，Xi’an 710072，China)

Abstract： A track association method based on weighted least-squares estimation and ant colony algorithm is proposed to solve the complicated track association for multiple platforms and multiple targets in the tactical datalink, and the processing model is set up. Ant colony algorithm is improved to satisfy the real-time datalink. The method can set the parameter according to the battlefield circumstance and the measuring error of platforms. Monte Carlo simulation is performed with the constructed model. Results show that this method is feasible and effective.

Keywords： datalink; weighted least-squares estimation; ant colony algorithm; track association

0 引 言

在战术数据链系统中，各个平台都有自己的信息处理系统，并且各系统中都收集了大量的目标航迹信息。那么，一个重要问题是如何判断来自于不同系统的两条航迹是否代表同一目标，这就是航迹与航迹关联(或互联)问题，简称航迹关联或者相关问题。在各平台的航迹间相距很远并且没有干扰、杂波的情况，关联问题比较简单。但在多目标、干扰、杂波、噪声和交叉、分叉航迹较多的场合下，航迹关联问题就变得比较复杂。再加上各平台传感器之间在距离和方位上的组合失配、传感器位置误差、目标高度误差、坐标转化误差等因素的影响，使有效关联变得更加困难。

在数据链系统中，充分利用各个平台传感器获得的目标监视消息能大幅度提高整个作战平台的覆盖范围，并提高系统的定位精度。但由于各平台的传感器性能以及各个平台所受杂波干扰的不同，对同一个目标的测量结果可能不完全相同，因此，需要对目标航迹进行相关处理，以便形成统一的战场态势图。目前文献中出现的航迹关联算法主要有最近邻域法(NN)、K-NN法和修正的K近邻域法等［1］，这些都是基于统计的方法。数据链系统中各平台包含有较大的导航、校准及转换和延迟误差时，统计方法就显得力不从心，需要寻求其他方法。所以，本文从数据链在信息化战争中应用的角度出发，结合最小二乘和蚁群算法的特点，并将蚁群算法改进后，提出了在数据链中对多平台多目标航迹数据进行关联的一种算法，且建立了关联结构模型。

1 多平台多目标航迹关联模型

战术数据链系统的示意图如图1所示，每个平台都带有航迹关联模块，每个平台必须将本平台传感器获得的本地航迹与数据链上其他平台获得的远程航迹进行相关处理，然后再将关联处理后的航迹通过数据链发送给其他平台［2-3］。航迹关联模型如图2所示。它类似于分布式结构，主要包括航迹数据预处理和航迹相关。数据预处理是对数据链和本平台的航迹进行时间对准和坐标转换；根据数据链系统体系结构特点航迹相关处理采用本文提出的基于加权最小二乘和蚁群算法的航迹关联算法；关联结束后通过数据链将航迹进行统一管理，以便形成统一的战场态势。

图1 战术数据链系统示意图

图2 航迹关联处理模型

2 航迹关联算法

美国和北约各国应用最广泛的Link-16数据链采用了时分多址即TDMA协议，是一种分配通信资源供使用者传输数据的入网协议。系统将时间轴划分为时元，时元划分为时间帧，时间帧划分为时隙(Time Slot)。在每个时元中为每个成员分配一定量的时隙，用户在自己的时隙内发送信息，在其他用户的时隙时处于监听状态。在这用技术支持下，信息能够被同步传输到任意有需求的平台上［4-5］。

本文研究的数据链采用Link-16的时分多址协议，在数据链系统中有n个监测平台而且每个平台在每个时元内都有属于自己的时隙。结合数据链的特点和战场的需要，提出多平台多目标航迹关联算法如下：

(1) 航迹建立。利用各航迹连续10次的点迹，采用加权最小二乘估计算法建立各航迹运动方程，并通过数据链发送到其他平台。

(2) 发送、接收、记录目标航迹信息。在第i个网络周期中，本地目标航迹信息在ti时刻发送到数据链，在ti以后，每个平台开始记录从数据链接收到的其他平台监测到期开始之前的信息，这样，每个平台都记录了数据链系统中其他平台监测到的目标航迹信息。

(3) 坐标转换和时间对准。通过航迹运动方程得到目标在ti+1时刻的点迹，并将其转换到本地坐标系中。然后所有目标在ti+1时刻的点迹被保存在C中。

(4) 蚁群搜索算法。通过设置阈值TV，利用蚁群算法就可以找到相同的目标点迹集合，将其记录在target［］中。显然，TV将影响正确的关联概率。

(5) 关联判断准则。从第i到第i+m个网络周期，如果target［］出现了x次，那么target［］中的目标就认为关联成功。x/m也将影响正确的关联概率。

3 加权最小二乘估计

平台测量得到的目标信息是采样值，如果要得到采样点之外的目标信息，就必须建立目标的运动方程。本文采用加权最小二乘法估计目标运动方程。假设目标运动方程是由n阶多项式描述的，可以表示成如下矩阵形式：

X(t)=x(t)

y(t)

z(t)=a0a1…an

b0b1…bn

c0c1…cn1

t1

式中:(x(t),y(t),z(t))是目标在t时刻的坐标值。若能确定上述方程的系数矩阵，就可以解出目标的运动方程。考虑到精确性需要和高阶多项式赋值引起的数值不稳定性，取n=5，将10个以前的观测值代入运动方程中。观测方程假设如下：

式中:H为已知t的幂函数;X为5个待定的未知数;V是测量误差，E(V)=0。

因此t时刻目标的状态为:

Z(t)=［1t…t4］

(8)

4 蚁群搜索算法

遗传算法等仿生算法是近年研究的热点。意大利学者Dorigo于1991年首次提出了蚁群算法。该方法已经应用到许多实际问题中，诸如车辆路径问题、电力系统、航迹规划、空战决策等。这些研究成果得益于蚁群算法的内在机制，蚂蚁的内在生理特征使得蚂蚁能够发现蚁穴到食物之间的最短路径。这种内在特征是通过蚂蚁在经过的路上留下的挥发性分泌物信息素来实现的。当蚂蚁选择一条路径后，后来的蚂蚁会根据各条路径上信息素的强弱来选择所要经过的路径，这就是算法的选择机制。信息素随着时间的推移会逐渐挥发消失，但是对于蚂蚁选择的路径而言，该路径上留下的信息素浓度会越来越大；反之，信息素浓度大路径会吸引更多的蚂蚁。这种能够收敛到最优解的方式被称为更新机制，一开始的路径几乎不可能是最优的，甚至是最差的。当大量的蚂蚁通过信息素的更新后，最终是可以发现最佳路径的，这就是协调机制。由此可见，蚁群算法的优化机制对于多目标航迹关联问题而言业提供了一种很好的解决思路。其详细原理可见文献［6］。

4.1 蚁群算法的改进

数据链系统对实时性有着严格的要求，所以为了尽快地找到蚁群算法的最优解，本文对蚁群算法进行了两点改进：

(1) 在蚂蚁进行下一个节点的选择时加入阈值TV；

(2) 在蚂蚁每走一步之后都进行信息素的更新。

每只蚂蚁每个节点必须且只能经过一次，因此给每只蚂蚁构造一个允许列表allowk，该列表中存放蚂蚁还没有走过的节点，tabuk列表存放蚂蚁已经走过的节点。在算法的初始时刻，将m只蚂蚁放在起始节点，此时各路径上的信息素相同，设τij(0)=c。每只蚂蚁根据路径上的信息素的量独立地选择下一个城市，蚂蚁k由节点i转向节点j的状态转移概率如下：

pkij(t)=ταij(t)ηβij(t)∑v∈allowkταiv(t)ηβiv(t),

j∈allowk

0,jallowk

(9)

为了多目标航迹关联的需要，取allowk=［j1,j2,…,js,…,jw］，其中jstabuk，k，1≤k≤i，d(k,js)≤TV。TV是影响航迹关联正确概率的阈值，使得蚂蚁不会经过与节点距离远的节点，从而加快算法的收敛，快速找到最优解。

当蚂蚁找到下一步的解时，各路径上的信息素将会按照下式进行更新：

τij(t+1)=(1－ρ)τij(t)+Δτij,ρ∈(0,1)

(10)

Δτij=∑mk=1Δτkij

(11)

Δτkij=Q/Lik,if蚂蚁k经过路径ij

0,else

(12)

式中：Δτkij表示蚂蚁k经过(i,j)时信息素的增量；Δτij表示路径(i,j)总的信息素增量；当t=0时，τkij(0)=c，Δτkij=0;ρ表示信息素挥发系数，ρ∈(0,1); Q为调节常数;Lik表示第一个目标到当前目标之间的距离。在每一步之后都更新信息素，是为了加快算法的收敛，快速找到最优解。

4.2 算法流程

根据上述原理和规则，采用蚁群算法求解多目标航迹关联问题的具体步骤如下：

(1) 设置初始参数，C表示所有目标点迹集合，Nc表示循环次数，将所有蚂蚁置于起始节点，并将起始节点加入tabuk列表，计算出allowk列表。

(2) 蚂蚁根据式(9)选择下一节点，更新tabuk和allowk列表，并根据式(10)进行信息素更新。

(3) 判断蚂蚁allowk是否为空，若否执行步骤(2)，否则在最后一个目标处待命；等到所有的蚂蚁allowk列表为空，执行步骤(4)。

(4) 计算出所有蚂蚁从第一个目标走到最后一个目标的最短路径Lkmin=min Lk；之后各个路径上的信息素将按照式(13),式(14)计算：

τnextij=(1－α)τcurrentij+αΔτij

(13)

Δτij=1/Lk,Lij∈Lkmin

0,else

(14)

式中:Lk表示蚂蚁走过的最短路径的长度。

(5) 判断Lkmin是否是最优解，即与之前的L对比。如果Lkmin

(6) 判断循环次数Nc是否进行完毕，若没有则将所有蚂蚁重新置于开始目标点。

(7) 在Nc次循环完成之后，输出最优解，将最相近的一组目标从集合C中删除；重复上述步骤继续寻找下一组相近的目标，直到集合C变成空集。

5 仿真结果与分析

为了验证本文提出的航迹关联算法，采用Monte Carlo方法在一定的情形下进行仿真。假设数据链系统由30个平台构成，100个目标在数据链系统的监测范围之内。根据最小二乘法得到每个目标的真实运动轨迹。为了充分检验关联算法的关联效果，平台每10 s监测得到一次目标的位置坐标，假设随机测量误差为［0,50］m，考虑参数TV和x/m对正确关联目标航迹概率的影响，采样航迹上50个点进行100次仿真。仿真结果如表1所示。

从蚁群搜索算法的原理可以看出，在一定的仿真条件下，目标航迹和测量误差确定，x/m和TV对航迹的正确关联概率有很大的影响。如果TV太大，算法就可能把不同的目标航迹关联在一起。相反，如果TV太小，算法就可能把同一个目标的航迹关联不到一起。同样，x/m也影响信息的可靠度，对航迹的正确关联率也有一定影响作用。如表1的仿真结果所示，当TV=0.2，x/m=0.6时，正确关联概率达到最大值93.4%。实际上，在真实的战场环境中，如果平台对目标的分辨能力相对较强，测量误差较小，当TV取值过大的情况下，算法就有可能分辨不出相近的目标。相反，如果平台对目标的分辨能力较弱，测量误差较大的话，关联算法就有可能关联不到目标的正确航迹。因此，仿真结果与理论和实际的战场环境是相符的。

图3是改进后的蚁群算法在TV=0.2，x/m=06时的最优路径和平均路径的长度随循环次数增加的变化情况，从结果可以出，改进后的蚁群算法收敛速度较快，符合数据链系统的实时性要求。本文中的仿真条件是一般情况，可以根据战场环境和平台的测量误差设置TV和x/m。当数据链系统中有大量的平台和目标时，蚁群算法能够表现出优势，说明本文提出的算法具有很好的适应性。

6 结 论

对于数据链的应用来说，多平台多目标的航迹关联不仅是重点，也是难点。本文从战场需要和数据链的实际应用环境出发，以最小二乘和蚁群算法为基础，提出了一种应用于数据链系统的多平台多目标航迹关联算法。通过建立关联模型进行Monte Carlo仿真，仿真结

果表明了算法与理论和实际战场环境是一致的，也表明了新算法的有效性与可行性，从而为数据链的研制打下了一定的基础。

图3 改进后的蚁群算法仿真

参考文献

［1］何友，王国宏，陆大金，等.多传感器信息融合及应用［M］.北京：电子工业出版社，2007.

［2］王文政,周经纶,罗鹏程,等.战术数据链仿真研究综述［J］.系统仿真学报,2008,20(14)：3623-3627.

［3］田斌鹏.战术数据链实时性研究［D］.成都：西南交通大学，2007.

［4］任培,周经纶,罗鹏程,等.美军数据链发展概况与启示［J］.装备指挥技术学院学报,2008,19(1):43-47.

［5］孙义明,杨丽萍.信息化战争中的战术数据链［M］.北京:北京邮电大学出版社，2005.

［6］段海滨.蚁群算法原理及其应用［M］.北京:科学出版社,2005.

［7］秦卫华,胡飞,秦超英.多平台多目标航迹关联方法［J］.火力与指挥控制,2006,31(10):18-21.

［8］张珂馨,黄敬雄,康莉.一种基于蚁群算法的数据关联方法［J］.系统仿真学报,2009,21(22):7127-7129.

［9］THOMAS S, HOLGER H H. MAX-MIN ant system [J]. Future Generation Computer Systems, 2000, 16(8): 889-914.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文