一种分区快速航迹关联算法

庄 俊，杨 沛

(解放军63889部队，河南 孟州 454750)

0 引 言

分布式多传感器信息融合系统中，为解决目标重复跟踪问题，需要建立来自不同传感器的局部航迹之间的对应关系，即进行航迹关联[1]。航迹关联是多传感器系统后续进行融合、识别处理的依据。

分布式多传感器系统的传感器一般配置在很宽广的地理范围上，所以系统目标区域较大[2]。如果直接对整个目标区域的所有局部航迹进行两两航迹关联，运算量会非常大，难以满足工程应用的实时计算要求。所以，选择一种能够降低航迹关联运算量的方法是必要的。

近年来，有一些文献对如何降低航迹关联运算量这一问题进行了研究。文献[3]利用剖分的网格对目标进行分配，减少了目标之间进行两两关联的次数，从而降低了运算量；文献[4]提出了将目标进行分区，只对本区域和相邻区域进行航迹关联的策略，但该策略仍有较多重复计算；文献[5]基于网格技术将关联计算分解成多个小任务，各个小任务并行计算，这种方法受处理器并行性能的影响，并未从根本上降低运算量。

本文提出了一种分区快速航迹关联算法，该算法将目标区域划分为若干个子区域，对目标区域内的航迹进行分区，只对同一子区域内的航迹进行两两关联判决。为了抑制分区导致的漏关联和错关联，相邻子区域间设置重叠区域。随着目标区域内航迹密度变化，自适应选择最优分区数。仿真实验表明，该算法可有效降低航迹关联的运算量。

1 航迹关联算法概述

目前，常用的航迹关联算法可分为3类：第1类是基于统计理论的航迹关联算法，主要有加权法[6]、修正法[7]、最近邻域法、经典分配法等；第2类是基于模糊理论的关联算法，主要有模糊双门限法[8]、模糊综合决策法[9]等；第3类是基于灰色理论[10]的关联算法。基于统计理论的航迹关联算法在目标密集、存在较多航迹交叉、分岔及传感器存在较大误差场景下关联性能严重降低；基于模糊理论的航迹关联算法在上述场景下的关联性能优于基于统计理论的关联方法，但其参数设置复杂，需要通过大量的仿真确定；基于灰色理论的航迹关联算法对传感器数据的要求较少，参数设置较少，比较适合于工程应用。本文算法仿真选择灰关联算法进行航迹关联。

2 基于区域划分的航迹关联

本文对航迹关联算法的研究是基于两坐标雷达进行的，很容易推广到三坐标雷达的应用。

2.1 目标区域划分方法

传统航迹关联算法在进行精关联之前，一般要先设定关联门限进行粗关联，大于粗关联门限的航迹点之间是没有必要进行关联比较的。所以，可以考虑将目标区域划分成若干个小区域，只对小区域范围内的目标航迹点进行关联，从而减少两两航迹关联次数，降低航迹关联运算量。

将多传感器系统目标区域按照一定策略划分后的小区域称为目标子区域，目标子区域可以根据需要继续划分成更小的目标子区域。

由于自身精度的影响和各种杂波及干扰的存在，传感器的量测数据或多或少会存在一定的系统误差和随机误差，目标航迹会偏离目标真实位置，进行区域划分时有可能将不同传感器源于同一目标的航迹划分到不同目标子区域，从而产生漏关联或错关联。为了抑制分区导致的漏关联和错关联，在相邻目标子区域之间设置部分重叠区域。如图1所示，假设目标区域为一长方形区域，将目标区域平均划分为若干个目标子区域，Δx、Δy为目标子区域长度和宽度，灰色区域为相邻目标子区域之间的重叠区域，宽度为D。

图1 目标区域划分示意图

2.2 重叠区域宽度计算

以两坐标雷达为例，传感器对目标的量测是在极坐标系下获取的，其距离和方位测量误差分别为σr、σa，为了计算方便，需要将雷达在距离和方位上的测量误差变换到直角坐标系中，分别为σx、σy，其计算公式为：

(1)

式中:R为距离量测值；A为方位量测值。

设传感器1的最大作用距离为Rmax1，则可根据式(1)计算出传感器1对目标的最大测量距离偏差为Δdmax1。假设多传感器系统中共有S个主动传感器，则系统中传感器对目标的量测距目标真实位置的最大距离偏差为：

Δdmax=maxΔdmaxs,s=1,2,…,S

(2)

2个传感器对同一目标的量测距离偏差可能方向相反，则2个传感器对同一目标的量测之间的距离最大为Δdmax的2倍。所以，重叠区域宽度D应大于系统最大距离偏差的2倍。同时，为了避免重叠区域过大，增加重复关联运算量，按照重叠区域不大于目标子区域面积一半的原则，重叠区域宽度D应小于min(Δx、Δy)的一半。

2.3 关联冲突处理

由于相邻目标子区域之间存在重叠区域，处于重叠区域内的航迹可能同时和2个或2个以上航迹点关联成功。假设传感器1的航迹i在l时刻的航迹点处于目标子区域的重叠区域，在l时刻分区航迹关联结果中传感器1的航迹i同时和传感器2的航迹j和k关联成功，如图2所示，则航迹关联对t1_i、t2_j和航迹关联对t1_i、t2_k冲突。

关联冲突处理机制如下：比较航迹i与j之间的距离dij和航迹i与k之间的距离dik，若dij>dik，则判定航迹i与k关联成功；否则，判定航迹i与j关联成功。

3 最优分区数确定

与一般航迹关联算法不同的是，分区航迹关联算法在进行航迹关联之前，需要先对输入航迹进行子区域划分，将各子区域航迹进行独立存储，然后分别对各子区域航迹进行关联，最后对各子区域关联关系表进行合并和关联冲突处理，形成关联关系总表。因此，为了评估分区航迹关联算法的运算量，需要综合评估目标子区域划分和子区域航迹关联的运算量。

假设2个传感器目标区域完全重叠，目标区域内航迹总数为N，将目标区域划分为M个目标子区域。对目标子区域划分和航迹关联的时间复杂度进行分析，进而对最优分区数进行判定。

3.1 目标子区域划分复杂度分析

对输入航迹进行子区域划分时，目标子区域数M越大，搜索某航迹所属子区域的运算量就越大，存储子区域航迹数据的数据结构也越复杂，运算时间复杂度随M线性变化；航迹数N越大，子区域划分的运算量也越大，运算时间复杂度随N线性变化，则目标子区域划分对M和N的时间复杂度均为O(n)。

3.2 目标子区域航迹关联算法复杂度分析

假设某时刻落入目标子区域i(i=1,2,…,M)内的航迹数为Ni，则目标子区域i内的航迹关联次数为Ni2，整个目标区域内的航迹关联总次数为∑Ni2。若不对目标区域进行分区，则航迹关联次数为N2。不考虑目标航迹落入相邻目标子区域之间重叠区域的情况，则有:

特别地，当航迹均匀分布在各目标子区域，即Ni=N/M时，则：

(4)

由式(3)和式(4)可以看出，子区域航迹关联运算量随航迹数N变化的时间复杂度为O(n2)，随子区域数M变化的时间复杂度为O(1/n)。

3.3 最优分区数判定

分区航迹关联算法耗时为子区域划分耗时和子区域航迹关联耗时之和。当航迹数N不变时，随着子区域数M的增加，子区域划分耗时线性增加，而子区域航迹关联耗时线性减少，则可能存在1个拐点(最小值)，使得在该分区数下分区关联算法总耗时最小。影响算法总耗时随M变化的趋势的因素主要有子区域划分方法和航迹关联算法。

由于子区域划分运算量随航迹数N变化的时间复杂度为O(n)，子区域航迹关联运算量随航迹数N变化的时间复杂度为O(n2)，则随航迹数N的变化，耗时最少的最优分区数也可能发生变化。

工程应用中，可在航迹关联系统调试时运用仿真数据对系统进行测试，得到在不同目标密度下的最优分区数。实际应用中，根据输入的航迹数量自动调整目标子区域数，使系统关联耗时最少，提高了系统效率。

4 算法仿真与分析

4.1 仿真场景设置

假设目标在二维平面运动，各目标起始方位和航向在[0,2π]内服从均匀分布，距离在[5 km,40 km]内服从均匀分布，速度在[100 m/s,300 m/s]区间服从均匀分布，过程噪声协方差Q=diag[100,100]。2部雷达均位于坐标原点，雷达1的测距标准差e1r=50 m，测角标准差e1θ=0.1°，测距系统误差Δ1r=20 m，测角系统误差Δ1θ=0.1°；雷达2的测距标准差e1r=50 m，测角标准差e1θ=0.1°，测距系统误差Δ1r=100 m，测角系统误差Δ1θ=0.2°。采样周期T=1 s，仿真时长50 s，蒙特卡洛仿真50次。目标区域内目标个数分别为50、100、200、400，将整个目标区域按横、纵坐标划分为1、4、9、16、25、36、49、64、81、100个目标区域，相邻区域间重叠区域宽度为1 km。选用灰关联算法进行航迹关联[12]，统计不同目标密度下不同分区数时的关联性能和运算耗时。

4.2 仿真结果分析

对不同目标密度不同分区数下子区域划分和航迹关联耗时进行统计，结果见表1～表3，图3～图4为对应的时间统计曲线。

表1 子区域划分耗时(单位：s)

表2 子区域航迹关联耗时(单位：s)

表3 航迹关联总耗时(单位：s)

由表1和图3可以看出，子区域划分耗时随航迹数N和子区域数M的增加线性增加。由表2和图4可以看出，子区域航迹关联耗时随航迹数N的增加呈平方阶增加，但随子区域数M的增加并不是线性减少的。这是由于重叠区域的存在，使得分区数较大时，重复关联运算量也比较大，增加了关联耗时。

图3 子区域划分耗时

图4 子区域航迹关联耗时

由表3和图5的统计结果可以看出，对目标区域进行分区，能够大大降低运算量，提高了关联速度。子区域划分耗时和航迹关联耗时的变化规律不同使得航迹关联总耗时随航迹数N和子区域数M的变化呈现不同的变化趋势。由最优分区数统计结果可以看出，并不是分区数越多，运算量越小，但随着航迹数N的增加，最优分区数也越来越大。

图5 航迹关联总耗时

图6为N=200时不同分区数下的关联正确率曲线。由图6可以看出，在目标密集且均匀分布的情况下，航迹关联正确率随分区数量的增加而有所降低，但与不分区时的航迹关联正确率相比，下降的幅度较小。这是由于划分目标子区域时，在相邻子区域设置了重叠区域，抑制了传感器测量误差可能带来的漏关联和错关联。

图6 N=200时关联正确率统计

综上所述，本文提出的分区航迹关联算法在保证关联性能的同时能够大大提高计算速度，在实际工程应用中具有重要的意义。

5 结束语

本文针对多传感器信息融合系统航迹关联运算量大，无法满足工程应用实时计算要求的问题，提出了一种分区快速航迹关联算法。该算法将目标区域划分成多个目标子区域，为消除测量误差对关联的影响，相邻目标子区域之间设置了重叠区域，并给出了最优分区数的判定方法。仿真实验结果表明，本文提出的算法能够大大降低航迹关联运算量，且保证了航迹关联性能，适用于工程应用。