基于图的分布式平飞航迹关联算法

鹿传国， 冯新喜， 孔云波， 王振兴

(空军工程大学电讯工程学院，西安 710077)

0 引言

航迹关联作为分布式传感器信息融合的关键技术之一，是一个典型的模式识别问题，主要目的在于判断来自于不同传感器的航迹是否来源于同一目标。当前主流算法有统计航迹关联和模糊航迹关联等［1－6］。其中，统计关联的主要思想在于寻求概率上的最近邻，难以对实际情况进行精细刻画，而模糊航迹关联确定各因素权值较为困难。拓扑方法［7］是一种较为新颖的关联算法，利用航迹数据空间位置的不变性来作为航迹的特征模式。工程应用中为获得高的关联精度可综合利用各类算法，一般可先利用统计方法进行粗关联，再利用拓扑方法进行精关联。文献［7－9］利用目标之间相对位置不变性使得航迹关联获得了较好的效果，然而这一方法仍存在一定的缺陷，在信息不完整时效果急剧恶化。

上述方法在构造检验统计量时都需要应用目标的方差数据，而实际工程中，受信息传输带宽、存储容量的限制往往无法实时获取目标的方差数据，这使得传统的统计关联方法难以直接应用，而使用“最近邻”算法正确率难以满足应用需求，特别是在出现近距平飞目标时。一般而言，近距离平飞航迹由于传感器分辨率、测量误差以及目标在空间位置、速度、航向等各因素较为接近时而导致关联判决错误率较高，是关联判决的难点所在。

航迹实质上是一个在时空上演变的时间序列，对同一节点获取的航迹而言，各航迹间关联关系实质上为航迹提供了一种支持度信息。本文基于图论的思想，给出了一种适用于平飞航迹关联的算法。如将各航迹抽象为图中无分辨的点，将航迹间关联度信息抽象为各点间距离，即建立了反映航迹间关联关系的双向连通图。图中节点分布的稠密程度均从一定侧面反映了航迹集合的特征。不同传感器的公共观测航迹关联度信息是十分接近的，故而其所对应的邻接矩阵必然是相似的。补图的邻接矩阵的特征值反映了各节点间的散射强度，可作为对应节点的特征值。

在求取节点关联度信息时，灰色理论是一种度量时间序列间相似关系的经典方法，且对数据的完整性并无苛刻要求，但经典的灰关联方法只表征趋势的相似性，忽略了相对距离、方向等因素，故而在实际应用中效果较差。综合B型灰关联度是一种较好的改进方法，可全面描述事物发展的异同性［10］。

本文将灰理论和图论的方法相结合，建立了一种无需方差数据即可解决平飞航迹关联的关联模型，该方法关联使用的信息量较少，既考虑了航迹的发展态势，又综合了航迹之间的相对关系，实验仿真也表明了该算法的正确性。

1 邻接矩阵的建立

1.1 综合B型关联度

灰关联分析的实质是整体比较，其内涵在于建立分析因子间的差异信息空间，计算差异测度，进而建立因子间的序关系［11］。综合B型关联度综合考虑总体位移差、总体一阶斜率差和总体二阶斜率差，全面描述事物发展的异同性［12］。

定义1记两序列分别为Xi=(xi(1)，xi(2)，…，xi(n))，Xj=(xj(1)，xj(2)，…，xj(n))。

令

则B型关联度的计算公式为

式中，γ(Xi，Xj)= γ(Xj，Xi)且当 Xi=Xj时，有 γ(Xi，Xj)=1。

1.2 邻接矩阵

对某传感器获取的航迹集合而言，将各航迹元素作为灰关联空间中的点，将综合B型关联理论求取各节点关联信息抽象为各节点间距离。

如式(4)所示，利用综合B型关联度建立传感器i的邻接矩阵 Gi=(γij)，其中 γij=γ(Xi，Xj)。邻接矩阵具有如下特点:1)Gi为正定对称矩阵;2)0≤γij≤1;3)γii=1。其中，γij为双向连通图中节点Xi与Xj的距离。

2 分布式航迹关联

在分布式航迹关联判决之前，每条航迹在判决者看来均是无区分的点，故直接利用某航迹元素与其余元素的关联度作为模式向量无法做出判决，因为作为参考的航迹元素对应关系并不明确。不同节点各航迹元素相对关联关系不变，不同传感器邻接矩阵之间必然相似，即必然存在初等变换矩阵X满足

如能求解出唯一的X，即可成批完成航迹关联判决，利用这一方法的难度在于X本身的特殊性，式(5)便是具有二次约束的超定方程，求解该方程较为困难，本文采用了矩阵主子式特征值多维分配的方法进行航迹关联。

2.1 算法思想

由于误差的影响，必然使得不同传感器建立的图中节点的距离存在微小的差异，根据邻接矩阵定义可知，该矩阵是Hermite阵，依据矩阵扰动分析理论［13］可知，Hermite阵必为良态矩阵，即矩阵数据的扰动不会引起特征值的显著变化。故可将余子式特征值按大小顺序组成列向量，进而作为航迹元素的特征向量。

实质上，利用余子式特征值作为特征向量是一种相对向量，而在节点对应的邻接矩阵中被删除的行或列蕴含着该节点与其补集的距离信息，可以视为一种绝对距离信息，可利用该距离信息对主子式特征值向量进行扩维，进而抽象为主子式特征向量。

2.2 关联唯一性问题

利用以上方法无法保证关联判决具有绝对唯一性，原因在双向连通图中可能存在。故在模式提取之前，须对邻接矩阵进行预处理，具体流程如下:

1)建立节点i初始灰关联矩阵Gi;

2)求取Gi各l阶主子式特征值向量，利用特征值判断各主子式是否相似，设定门限，如，则将元素 p、q进行合批的处理;

3)处理后矩阵输出。

合批具体操作为删除矩阵Gi对应p或q的行和列，并将两航迹元素作为一个整体参与关联，将航迹号标示为较小航迹号。

对合批目标，可以再利用统计等方法进行处理，这里不予赘述。

目标合批出现的原因在于对称补图的出现，实际中主要有以下情况。

1)多目标编队平飞，由于几何上的对称性而造成关联不唯一。此时结合统计关联方法或寻找特定参考航迹均可进行关联判决，参考航迹的选择一般在航迹走势上与平飞航迹具有一定的夹角，以使得在序关系上不具有明显的对称性。

2)目标间距太小不足以对平飞目标关联度产生显著影响，此时目标几近于合批，难以判断，因此可行方法是利用冗余的属性信息进行逻辑推断。

2.3 关联判决模型

为简化论述，这里假定 Gi=(γij)，(i=1，2)已预处理，记Gi的各主子式分别为求取的特征值，记列向量

式中，λ1≥λ2≥…≥λN－1。

记节点l对应行记为gl，节点l与其补图绝对距离信息定义为

引入统计量

3 实验仿真

实际雷达航迹关联中难以判决的往往是平飞编队目标。本文设定了如下场景。

目标平行编队飞行，航迹编号i=1，2，…，N，相邻目标飞行间隔 di(i=1，…，N －1)且在区间［0.2，1］间随机选取;目标速度为1 km/s，航向为π/3;利用两部雷达组网对目标跟踪，雷达坐标 O1为(0，50)，O2为(0，100)，单位为 km。

两部雷达均通过采用卡尔曼滤波对目标进行持续跟踪得到航迹数据，目标状态方程为

观测方程为

分布矩阵分别为

测量向量Z=(x，y)T，其测量矩阵为

对目标跟踪持续时间为120 s，采样周期T=3 s，Monte－Carlo 仿真次数为 100。

当目标数N=5时，正确关联概率曲线及各目标正确关联曲线如图1、图2所示。

图1 关联正确率结果对比Fig.1 Comparison of the correct association ratio of different methods

综合图1、图2所得结果曲线进行分析，可得如下结论。

1)由图1发现，本文算法航迹正确关联概率比统计关联算法有较大的改善，且随着历史数据的增加，正确关联概率逐渐增加。这是十分明显的，因为随着历史数据的增加，各航迹之间的关联度与真实值更加相近，而最近邻法几乎无法分辨。

2)观察图2发现，目标3关联正确率最高，其次是目标1、目标5对应的航迹正确关联概率，而目标2、目标4对应的航迹正确关联概率相对较小。原因在于灰度理论从实质上描述了一种序关系，目标3在序关系上具有唯一性，故而正确关联率较高。

由以上实验结果可以看出，基于图论的平飞航迹关联算法较之基于统计的最近邻关联算法具有更好的关联效果，且不需要方差数据参与运算，另外，由于关联信息对数据并无严苛要求，故而在个别数据丢失的情况下不会产生太大影响，进一步增强了算法的鲁棒性。

图2 各目标关联正确率结果对比Fig.2 Comparison of the correct association of each target

4 结论

本文将传感器获取的航迹集合抽象为双向连通图，利用邻接矩阵提取各航迹对应的特征模式。该方法充分利用了航迹数据的时空特征，而在图上构成了一种关联拓扑。实质上双向连通图表征了航迹集合的“种群特征”，利用群特征进行航迹关联可保证整体最优，从而避免了传统航迹关联方法陷入局部最优而造成的航迹误关联，进一步优化了关联效果。如借鉴序贯航迹关联的思想，加入航迹管理技术，可进一步提高关联概率。该算法从航迹的时间序列属性着手，故而适用于纯方位航迹关联。

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

［2］ 王骏，刘以安.分布式信息融合系统的性能评估方法［J］.计算机工程与设计，2007，8(15):3773－3775.

［3］ AZIZ A M，TUMMALA M，CRISTI R.Fuzzy logic data correlation approach in multi－sensor multi－target tracking systems［J］.Signal Processing，1999，76:195－209.

［4］ CHEN H，BAR－SHALOM Y.Track association and fusion with heterogeneous local trackers［C］//Proceedings of the 46th IEEE Conference on Decision and Control，New Orleans，LA，USA，2007:2675－2680.

［5］ 何友，陆大纟金，彭应宁.分布式多传感器系统中的航迹关联算法评述［J］.系统工程与电子技术，1999，21(10):15－18.

［6］ 朱必浩，冯新喜，鹿传国，等.综合利用各类信息的异类灰色航迹关联算法［J］.电光与控制，2011，18(7):35－39.

［7］ 石玥，王钺，王树刚，等.基于目标参照拓扑的模糊航迹关联方法［J］.国防科技大学学报，2006，28(4):105－109.

［8］ 余振威，王钺，张林，等.位置和拓扑信息融合的航迹关联算法［C］//第十三届全国信号处理学术年会，山东济南，2007，23(4A):456－459.

［9］ 吴泽民，任姝婕，刘熹.基于拓扑序列法的航迹关联算法［J］.航空学报，2009，30(10):1937－1942.

［10］ 桂预风，夏桂芳，邓旅成.赋范空间中的灰色关联度［J］.武汉理工大学学报:交通科学与工程版，2004，28(3):399－401.

［11］ 邓聚龙.灰理论基础［M］.武汉:华中科技大学出版社，2003.

［12］ 黄友澎，周永丰，谭秀湖，等.基于B型灰色关联度的纯方位航迹关联算法［J］.武汉理工大学学报:交通科学与工程版，2009，33(3):989－991.

［13］ 孙继广.矩阵扰动分析［M］.北京:科学出版社，1987:143－177.