2. 光电控制技术重点实验室, 河南 洛阳 471009
目前的航迹关联算法主要分为2类:基于统计的方法及基于模糊数学的方法。然而,这些算法主要针对2个局部节点的情况。随着研究的逐步深入,一些新方法、新思路,如灰色理论[1]、自适应关联算法[2]、聚类方法[3]、多维分配法等相继被提出用来解决多传感器多目标的航迹关联问题。
当系统规模较大时,多传感器的航迹关联可转化为多维分配问题来求解[4]。对此问题的求解,已有的算法包括Viterbi算法[5]、平均场人工神经网络求解法[6]、Lagrange松弛算法[7]等。另外,田宝国等在文献[8]中提出了利用遗传算法来解决多节点的航迹关联问题,但求解方法存在着早熟收敛及收敛速度慢的缺陷。上述这些方法的求解过程仍比较复杂,很难满足信息融合系统对于实时性的要求,不利于工程应用,为此,人们一直在寻求更加快速的求解算法。蚁群算法作为一种新的群智能演化算法,全局搜索能力强。文献[4]针对蚁群算法收敛速度慢、求解代数多的缺点,提出了一种航迹关联的变异蚁群算法,但算法的迭代次数及关联效果与动态门限值有关。本文将蚁群算法中蚂蚁的搜索范围限定在最大灰关联系数的邻域内,减少了无效搜索次数;采用狼群分配原则更新信息素,提高收敛速率;并采用GPU加速的并行策略进行求解。
1 基于灰色理论的航迹关联多维分配问题模型设传感器数目为m,定义其航迹集合为U=[u1,u2,…,uM];传感器s的航迹i表示usi。基于灰色关联理论,取局部节点Sm的航迹i为参考数列,记作Xi=｛Xi(k)|k=1,2,…,l｝;局部节点Sn的航迹j为比较数列,记作Xj=｛Xj(k)|k=1,2,…,l｝,(j=1,2,…,nSn),nSn为Sn的已知航迹数;l表示航迹信息维度。
对数据列进行标准化处理,具体如下
式中,k=1,2,…,l,j=1,2,…,nSn。
Xi(k)与Xj(k)的灰关联系数为
式中,Δij(k)=|Xi(k)-Xj(k)|,ρ表示分辨系数,通常取0.5;Δij(k)为第k个指标Xi与Xk的绝对差。
则Xj与Xi的灰关联系数可记为γij,如下
为此,多局部节点情况下构造全局统计量,如下
设置变量如下
式中,is=1,2,…,ns;s=1,2,…,m。H0表示原始假设,代表航迹i1,i2,…,iM为不同传感器探测到的相同目标;H1为对立假设,代表航迹i1,i2,…,iM来自于不同目标。则基于灰色理论的航迹关联多维分配问题模型如下
其约束条件为
对于上述问题的求解,如何快速求得约束条件下目标函数最优解仍然是制约该类航迹关联算法的瓶颈。为此,本文提出了一种结合灰关联系数的改进蚁群算法,能够实现上述问题的快速求解。
2 航迹关联问题的改进蚁群求解算法当运用蚁群算法求解航迹关联多维分配问题时,随着问题规模(目标数量及传感器数量)的增加,其计算复杂度将发生爆炸性增长。因此,对于多传感器多目标的航迹关联问题,传统的蚁群算法并不适用,无法满足实时性的要求。其主要原因在于:①蚁群算法在寻求目标函数最优解的过程中,采用全局搜索策略,当目标数较多时,搜索范围过大,具有一定的盲目性;②为了强化当前最优解,每次迭代后进行信息素更新,容易陷入局部最优,影响求解性能,所以为避免陷入局部最优的停滞状态,算法中引入路径随机选择策略,但这又会陷入盲目的随机搜索,因此,往往需要通过多次迭代才可获取满意解。
针对蚁群算法因采用全局搜索策略而导致的搜索范围过大问题,提出基于灰关联系数限定搜索区域用以提高搜索效率。假设某一时刻传感器s1的某条航迹为us1i,传感器s2的航迹集合为us2,航迹数为is2,由灰关联系数计算公式可求得传感器s1中的航迹us1i与传感器s2航迹集合us2中各航迹的灰关联系数,记为γ=｛γj |j=1,2,…,is2｝。设传感器s2航迹集合us2中的us2k与us1i来自于同一目标,则一定存在常数δ,使得us2k与us1i的灰关联系数γk位于max(γ)的左δ邻域内,即γk∈[(max(γ)-δ),max(γ)]。在稀疏目标环境下,通常max(γ)为γk;在密集目标环境下,由于随机误差及系统误差的影响,传感器经滤波后所获得的目标状态估计值与真实值存在一定的偏差,使得us2中取得max(γ)值所对应的航迹与us1i不一定来自于同一目标,此时,γk位于max(γ)的邻域内。经统计分析可知,δ可选取介于0.1与0.3之间的常数。因此,在运用蚁群算法进行求解的过程中,蚂蚁由当前节点转向到下一节点时,可依据最大灰关联系数的左δ邻域更新搜索列表,缩小了最优解的搜索范围,减少了无效搜索次数,进而,可大幅度提高搜索效率及有效性。
其中,蚂蚁由当前节点转向下一节点的转移概率如下
式中,τisjx(T/tk)为信息素强度;ηisjx(tk)为启发因子,取usi与uxj的灰关联系数γisjx;α和β分别体现了τisjx(T/tk)和ηisjx(tk)的重要程度;pisjx(T/tk)为节点转移概率,按轮盘赌法选取下一目标。
在基于蚁群算法进行求解的过程中,最差蚂蚁释放的信息素将会导致算法的搜索陷入局部最优,为了避免局部最优及盲目的随机搜索,提高收敛速度,本文借鉴狼群分配原则对信息素进行了更新。研究中发现狼群通常将捕捉到的大部分猎物分给强壮的狼,尽管会饿死一些弱小的狼,但能保证强壮的狼在下次扑捉到猎物,不至于使整个狼群饿死,进而提高了狼群的生存能力。因此,借鉴狼群分配原则,本文算法对每次迭代中局部最优路径的蚂蚁,增大其释放的信息素量,去除局部最差路径上蚂蚁释放的信息素。基于狼群分配原则的信息素更新机制如下
式中,D* 为当前迭代中最优路径对应的目标函数值,D** 最差路径对应的目标函数值;φ和表示本次迭代中局部最优和最差蚂蚁的个数。
基于灰关联系数寻优的改进蚁群算法,在求解航迹关联多维分配问题时,以最大灰关联系数的邻域对搜索列表进行更新,并采用基于狼群分配原则的信息素更新机制。基于灰关联系数寻优的改进蚁群算法求解过程如图 1所示。
 |
| 图 1 航迹关联多维分配求解过程 |
另外,由于当前tk时刻关联后的信息素矩阵保留了航迹之间的历史信息,且实际空域中目标的航迹为连续曲线,因此,可将当前时刻的信息素矩阵作为下一关联时刻的初始信息素矩阵,如(11)式所示。因此,随着关联周期内关联次数的增加,迭代次数NC可逐步减少,迭代次数与关联周期内关联次数的关系如(12)式所示。
式中,ceil为向上取整函数;NCini为初始迭代次数;k为一个关联周期内的第k次关联。
3 基于GPU加速的并行蚁群算法蚁群算法进行求解的过程中,每只蚂蚁均独立构建回路,蚂蚁之间仅通过信息素进行协作,因此,蚁群算法存在着并行特性;另外,算法的性能瓶颈在路径搜索过程,尤其是问题规模较大时,传统的CPU串行求解方法无法满足实时性要求。为此,使用CUDA架构的线程块模拟蚂蚁的求解过程,充分利用GPU的并行计算能力,提高算法的运行速度。并行蚁群算法的实现流程如图 2所示。
 |
| 图 2 并行蚁群算法流程 |
核心模块包括:变量声明及存储空间分配、GPU端变量初始化模块、路径选择模块、局部最优解计算模块、信息素更新模块等。变量声明及存储空间分配:变量包括CPU端变量及GPU端变量。CPU端变量主要有2个作用:①变量在CPU端完成初始化,并将值拷贝到GPU端,即实现由CPU到GPU的值传递过程;②经GPU计算后的值拷贝到CPU端变量,完成由GPU到CPU的值传递过程,用于打印输出等操作。本部分的核心是GPU端变量的声明及空间分配,对于固定不变的变量,声明为-constant-类型,设备端所有线程均可访问;对于实时更新的变量,声明为-device-类型,可供所有线程调用;对于并行计算中使用的临时变量,声明为-shared-类型。存储空间的分配在CPU端完成,因此,各变量的维度及各维度的大小需先行设计,以便在GPU端进行初始化操作及更新。
GPU端变量初始化模块:为了提高执行效率,应尽量避免CPU端变量向GPU端的直接拷贝,因此,GPU端变量的初始化任务应尽量在GPU端执行。本部分初始化的GPU端变量主要包括信息素矩阵、灰关联系数矩阵、搜索列表矩阵等。
路径选择模块:路径选择模块是GPU并行蚁群算法实现的核心部分,主要包括航迹对中初始航迹节点的选择、最大灰关联系数的左δ邻域更新搜索列表、节点转移概率的并行计算、轮盘赌规则选取目标节点等。① 初始节点的选择及轮盘赌法选取目标节点,需要通过产生随机数来确定,然而CUDA中没有提供随机数生成的函数,尽管可在CPU端调用随机数生成函数产生一系列随机数,但数据从CPU端到GPU缓存的拷贝,执行效率较低,因此,编写随机数生成函数是GPU并行蚁群算法的重要组成部分;② 蚂蚁由当前航迹节点向下一传感器目标节点转移时,需要计算各灰关联系数的最大值,以限定搜索区域,但常规的串行求解算法执行效率低下,不适合在GPU端执行,因此,最大值求解的并行算法模块是路径选择模块的一个部分;③ 并行求解转移概率及轮盘赌法选取目标节点的过程中,存在着累加求和的过程,在GPU端基于前缀和并行求解模块,可进一步提高执行效率。
局部最优解计算模块:各蚂蚁完成一次迭代之后,由搜索列表确定完整路径,并行计算各蚂蚁搜索路径的目标函数值,并利用最大值并行求解模块,求取目标函数最大值,即可获得当前迭代的局部最优解。信息素更新模块:一次迭代完成之后,由搜索列表确定各完整航迹对,根据信息素更新公式,并行计算信息素。
4 仿真实验分析 4.1 仿真条件为了验证本文所提出的改进蚁群算法求解航迹关联多维分配问题的性能,采用蒙特卡洛方法对本文的求解算法进行了50次仿真,仿真步长为10步。仿真实验中设置3部2D雷达,其测距误差与测角误差分别是σd1=10 m,σθ1=0.3°,σd2=15 m,σθ2=0.6°,σd3=30 m,σθ3=0.3°。目标批次为100批次,首先采用扩展卡尔曼滤波对目标进行状态估计,目标状态向量Xk可表示为
。其中,
及
分别表示目标在水平及垂直方向的位置、速度及加速度对应的分量。滤波算法中目标的运动状态模型为匀加速模型。仿真实验中,改进蚁群算法的参数分别设置为:Q=10,α=2,β=6,衰减因子ρ=0.1。
仿真实验中,蚂蚁数量为100只,初始迭代次数NCini为10,设最大灰关联系数的邻域δ为0.2。仿真步进内的迭代次数由公式(12)得到,分别采用3种算法进行求解。其中,算法1对应于本文提出的改进蚁群算法;算法2与算法1相比,未采用狼群分配原则对信息素进行更新;算法3为常规的蚁群算法。相同的仿真条件下,3种不同算法求解得出的正确关联率如图 3所示。
 |
| 图 3 正确关联率曲线 |
由图 3可知,本文提出的改进蚁群算法能够在较少的迭代次数内获得较高的正确关联率;由算法2与算法1比较结果可知,采用狼群优化原则更新信息素,能够加速收敛;因目标批次较多,较少的迭代次数内常规蚁群算法无法满足需要。
对于本文所提出的改进蚁群算法求解航迹关联多维分配问题,基于CUDA平台实现该算法的GPU并行求解,并与常规的CPU实现过程进行对比。分别设置不同的仿真条件,条件一:蚂蚁数量为100只、目标数量10批次;条件二:蚂蚁数量为100只、目标数量50批次;条件三:蚂蚁数量为100只、目标数量100批次;条件四:蚂蚁数量为200只、目标数量100批次。表 1统计单次关联过程中改进蚁群算法单次迭代的执行时间及加速比。
| 仿真条件 | CPU执行时间/s | GPU执行时间/s | 加速比 |
| 一 | 0.38 | 0.17 | 2.24 |
| 二 | 4.50 | 0.20 | 22.50 |
| 三 | 19.98 | 0.27 | 74.00 |
| 四 | 38.52 | 0.28 | 137.57 |
由表 1可知,基于GPU加速的并行蚁群求解算法,能够大幅度提高求解效率,且随着问题规模的增大,加速效果越明显;蚂蚁数量的增加对GPU并行蚁群算法的求解效率没有影响,因算法的CPU实现是一个串行的过程,随着蚂蚁数量的增加,算法的求解时间将呈比例增长。
5 结论本文在基于灰色理论建立航迹关联多维分配问题模型的基础上,实现了一种基于改进蚁群算法的求解方法。改进的求解算法具有一定的工程应用价值,主要体现在:①将蚁群算法中蚂蚁的搜索路径限定在最大灰关联系数的左δ邻域内,既避免了蚂蚁搜索的盲目性,又很大程度的缩小了搜索范围;②采用狼群分配原则的信息素更新机制,可以进一步加快收敛速率;③一个关联周期内,平均迭代次数在10步迭代之内,关联正确率可达到90％以上;④GPU加速的并行蚁群算法能够大幅度提高航迹关联问题的求解效率。
| [1] | Guan Xin, He You, Yi Xiao. Grey Track-to-Track Correlation Algorithm for Distributed Multitarget Tracking System[J]. Signal Processing, 2006, 86(11): 3448-3455 |
| Click to display the text | |
| [2] |
刘颢,陈世友,汪学东,张必银. 一种自适应航迹关联算法[J]. 电子学报,2013, 41(12): 2416-2421 Liu Hao, Chen Shiyou, Wang Xuedong, Zhang Biyin. An Adaptive Track Correlation Algorithm[J]. Acta Electronica Sinica, 2013, 41(12): 2416-2421 (in Chinese) |
| Cited By in Cnki (1) | Click to display the text | |
| [3] |
徐丽,马培军,苏小红. 基于K-Medoids聚类的多传感器航迹关联算法[J]. 哈尔滨工业大学学报,2012, 44(1): 107-110 Xu Li, Ma Peijun, Su Xiaohong. A Multisensor Track Association Algorithm Based on Medoids Clustering[J]. Journal of Harbin Institute of Technology, 2012, 44(1): 107-110 (in Chinese) |
| Cited By in Cnki (2) | Click to display the text | |
| [4] |
郭蕴华,袁成. 一种异步航迹关联的变异蚁群算法[J]. 电子学报,2012,40(11):2200-2205 Guo Yunhua, Yuan Cheng. A Mutation Ant Colony Algorithm for the Asynchronous Track Correlation[J]. Acta Electronica Sinica, 2012, 40(11): 2200-2205 (in Chinese) |
| Cited By in Cnki (6) | Click to display the text | |
| [5] |
朱洪艳,韩崇昭,韩红,等. 分布式多传感器信息融合系统的异步航迹关联方法[J]. 控制理论与应用,2004,21(3): 453-456 Zhu Hongyan, Han Chongzhao, Han Hong, et al. Asynchronous Track to Track Association Method in Distributed Multi-Sensor Information Fusion System[J]. Control Theory & Applications, 2004, 21(3): 453-456 (in Chinese) |
| Cited By in Cnki (8) | Click to display the text | |
| [6] |
田宝国,何友,杨日杰. 平均场网络在航迹关联中的应用[J]. 航空学报,2005,26(1): 94-97 Tian Baoguo, He You, Yang Rijie. Application of Mean-Field Network to Track Correlation[J]. Acta Aeronautica et Astronautica Sinica, 2005, 26(1): 94-97 (in Chinese) |
| Cited By in Cnki (8) | Click to display the text | |
| [7] | Chen Huimin, Bar-Shalom Y, Kirubarajan T. Tracking of Spawning Targets with Multiple Finite Resolution Sensors[J]. IEEE Trans on Aerospace and Electronic Systems, 2008, 44(1): 2-14 |
| Click to display the text | |
| [8] |
田宝国,何友,杨日杰. 基于遗传算法的分布式多传感器航迹关联算法[J]. 火力与指挥控制,2005, 30(5): 44-47 Tian Baoguo, He You, Yang Rijie. Track Correlation Algorithm based on Genetic Algorithm for Distributed Multi-Sensor System[J]. Fire Control and Command Control, 2005, 30(5): 44-47 (in Chinese) |
| Cited By in Cnki (5) | Click to display the text |
2. Science and Technology on Electro-Optic Control Laboratory, Luoyang 471009, China
