基于背包问题的多相控阵雷达多目标跟踪时间资源管理算法

丁海婷，周琳，刁伟峰

(南京电子技术研究所，江苏 南京 210039)

0 引言

随着现代雷达所面临的作战环境日益严峻，单一雷达已经很难满足处理各类威胁的要求，多雷达联合进行调度的研究逐步走入人们的视野，通过联合调度多相控阵雷达有利于进一步挖掘雷达的工作潜力，但同时也增加了资源管理的复杂性。相控阵雷达在执行多目标跟踪任务时需要占用大量的时间、能量和计算资源，但相控阵天线技术的发展和计算机运算能力的提升，使得能量和计算资源对相控阵雷达的束缚日益减弱，本文主要考虑时间资源对多目标跟踪的影响。

多相控阵雷达要实现对多目标的跟踪需要解决目标分组和时间规划两方面的问题。所谓目标分组就是实现雷达和目标的配对(即确定每部雷达进行跟踪的目标)。文献[1-3]均使用了“拍卖算法”来选择雷达，这种模拟现实生活中拍卖过程的算法在多雷达联合调度中表现良好；文献[4]从博弈论的角度研究了雷达网络中跟踪多目标时的目标选择问题；文献[5]提出一种基于负载最小的传感器选择方案，有利于时间资源的合理配置；文献[6]对测量参数进行优化，使用于跟踪的资源最小化；文献[7-8]从图形模型的角度出发，给出了目标和传感器最优分配解，具有良好的跟踪性能。而时间规划则是在正确的调度间隔内选择和规划要执行的任务[9]，主要包括基于优先级[10-12]和基于填充[13-14]两种设计方法：基于优先级进行时间规划是将任务的优先级进行排序，从高到低依序执行任务，这种方法保证了高优先级的任务可以得到执行；基于填充的设计方法要求调度尽可能多的任务，有利于提高时间资源的利用率。然而，以往的研究大都将目标分组和时间规划两方面分开进行考虑，在时间充足的情况下性能较好，一旦时间有限，整体跟踪目标的数目较少。

鉴于此，本文提出一种基于背包问题的多相控阵雷达多目标跟踪的时间资源管理算法，在时间资源受限时联合实现目标分组和时间规划，从而保证对重要目标的跟踪和增加跟踪目标的数目。文中使用优先级衡量目标的重要程度，选取跟踪目标优先级之和最大化作为算法的目标函数；基于背包问题联合考虑时间资源规划和多相控阵雷达跟踪多目标的分组问题，从填充的角度出发可以最大限度地减少雷达的空闲时间；并通过动态规划的思想进行时间资源问题的求解。最后的仿真结果说明了算法的有效性。

1 时间资源管理问题描述

雷达跟踪目标的任务模型为

Ei={Ri,vi,Ii,Hi}，

(1)

式中：Ei表示第i个目标的跟踪任务，i=1,2…n，n为目标总数；Ri、vi、Ii和Hi分别表示目标i的距离、速度、威胁和敌意，其中威胁主要指目标类型的威胁，敌意由敌我属性决定，这些均属于目标的先验信息。

本文考虑时间资源对目标跟踪的影响，首先需要获得雷达跟踪第i个目标所需要的时间资源ti. 相控阵雷达处于跟踪状态时，由雷达距离方程可知，相控阵雷达的最大跟踪作用距离与跟踪时间呈正相关。而各目标的跟踪时间是由其脉冲重复周期Tr决定的，由于本文考虑的是时间资源有限时多目标的跟踪问题，这里选取脉冲重复周期Tri作为目标跟踪的时间资源ti，根据目标与雷达的距离不同，相应地使用不同的脉冲重复周期跟踪目标。与采取固定的脉冲重复周期相比，使用可变的脉冲重复周期将一定程度上节约时间资源，有利于有限时间内实现更多目标的跟踪。文献[15]中指出，为了方便信号的产生和任务调度时的时间编排，脉冲重复周期时间尽量设计成整数倍关系。基于上述考虑和实际设计经验，本文中的脉冲重复周期设计为0.2 ms的整数倍。在使用单脉冲进行目标跟踪时，为了避免距离模糊，这里根据目标的距离选择合适的脉冲重复周期，即目标的距离Ri要小于脉冲重复周期对应的最大无模糊距离Rui，Rui=cTri/2(c为光速)，同时为了节约时间资源，选取满足无模糊距离对应的脉冲重复周期的最小值。(2)式中体现了上述设计中脉冲重复周期与目标距离之间的对应关系，其中l为正整数。

(2)

当时间资源有限时，相控阵雷达无法实现对所有目标的跟踪，这时需要保证重要目标可以得到跟踪。使用优先级来衡量目标的重要性，优先级越高的目标越重要。优先级的确定方法有很多，其中，优先级表法和人工智能法是较为常见的综合优先级确定法，可以适用于复杂环境下的任务调度。本文使用的模糊逻辑优先级[16-18]就是一种智能算法，可以根据跟踪目标的运动状态和属性等先验信息，综合直觉和专家的考虑进行设计，并不断通过仿真进行调整，从而模拟人类决策过程动态计算其优先级。选取目标距离、目标速度、威胁和敌意等主要影响因素作为决策的输入，生成的决策树如图1所示，其中优先级的计算使用模糊逻辑优先级法。在多相控阵雷达系统中，目标与不同雷达的距离不同，这将影响优先级的计算，规定输入的目标距离为目标与一定点的距离，从而计算目标i的绝对优先级pi.

图1 跟踪目标优先级决策树Fig.1 Decision tree of tracking target priority

通过上述讨论，可以得到目标i的时间资源ti和优先级pi，给定第j部雷达(j∈[1,M]，M为此次调度间隔内所有可以用于跟踪的雷达数目)在一个调度间隔内用于跟踪的时间资源Tj和这个调度间隔内所有请求跟踪的目标，跟踪目标消耗的时间资源不能高于雷达可调用的时间资源：

(3)

式中：tij为第j部雷达跟踪目标i的时间资源，同一目标在不同雷达的跟踪时间不同，每部雷达选择跟踪目标的时间资源不能超出给定的限制；Cij综合考虑了目标分组和时间规划问题，其定义如下：

(4)

本文进行时间资源管理的目的是为了在资源有限情况下保证重要目标的跟踪，以及尽可能多地增加跟踪目标的数目，因此目标函数为跟踪目标优先级之和最大化：

(5)

基于(3)式～(5)式讨论，多相控阵雷达跟踪多目标的时间资源管理问题可以描述为

(6)

2 基于背包问题的算法设计

背包问题是运筹学中典型的NP-hard问题，广泛应用在资源分配、投资管理、货物装载、生成密钥等方面，其名称来源于为给定的背包选择最合适的物品，这是从填充的角度考虑问题。0-1背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，其要求是找出m个物品的一个子集使其尽可能的装满容量为W的背包，这里每个物品只有一件供选择放还是不放。前文描述的时间资源管理问题可以看作典型的0-1背包问题。文献[11]中指出基于背包问题的算法设计虽然牺牲了部分目标的跟踪精度，但对跟踪系统的影响要小于灾难性的后果。

给定wk、Vk分别为物品k(k=1,2,…,m) 的质量和价值，0-1背包问题可以描述为

(7)

这里的xk可以取0(表示物品k不装入背包)和1(表示物品k装入背包)。

(7)式问题可以转化为只考虑第k件物品的装包策略(放或者不放)问题，状态转移方程为

f(k,W)=max(f(k-1,W),f(k-1,W-wk)+Vk)，

(8)

式中：f(k,W)表示前k件物品和一个容量为W的背包进行装包可以获得的最大价值；若不放第k件物品，此时背包的价值为前k-1件物品和一个容量为W的背包进行装包可以获得的最大价值f(k-1,W)；若放入第k件物品，此时背包的价值为前k-1件物品和一个容量为(W-wk)的背包进行装包可以获得的最大价值f(k-1,W-wk)加上第k件物品的价值Vk.

本文将目标i的时间资源ti和优先级pi分别视为“物品”的质量和价值，雷达的时间资源视为“背包”的容量。为了充分利用时间资源，在时间资源有限情况下取ni≤1，从而将多相控阵雷达跟踪多目标的时间资源问题转换为背包问题进行求解，具体描述为

(9)

基于上述讨论，本文设计的多相控阵雷达多目标跟踪时间资源管理算法具体流程为：

1) 选择合适的调度间隔，将所有要求在此间隔内请求跟踪的目标加入任务列表；

2) 获得所有可以在此间隔内执行跟踪任务的雷达编号及其可用于跟踪的时间资源；

3) 对任务列表中的目标进行处理，得到其优先级及雷达对其跟踪所用的时间资源；

4) 构造并求解时间资源问题，得到每部雷达选择执行跟踪的目标列表；

5) 雷达执行对目标的跟踪，没有得到跟踪的目标增加其优先级等待下次调度。

3 动态规划求解算法

0-1背包问题的求解算法有很多，诸如穷举法、回溯法、动态规划法、分支限界法和粒子群算法、遗传算法等。文献[19]中指出：穷举法、回溯法、动态规划法和分支限界法可以求得全局最优解，但普遍存在解的数量多、计算量大的特点；粒子群算法和遗传算法等群智能算法的运算速度较快，但求得的解可能是局部最优解。为了避免求得局部最优解，且考虑到涉及目标的数量并不庞大，因此选择使用动态规划的思想进行求解。动态规划法的基本思想是将最优化问题分成若干个子问题，各个子问题并非相互独立而是呈现递归现象，后一个子问题的求解要依赖前面子问题的最优解，最后从子问题的解中求出整体的最优解。对每个子问题的求解只进行1次，将求解结果填入表格中，在需要应用时直接调用，因而动态规划法也叫填表法。

基于背包问题设计的算法具体求解的步骤如下：

步骤1将问题分解为i个子问题，每个子问题为是否对第i个目标建立跟踪、选择哪部雷达建立跟踪。

步骤2构建递归方程定义最优解：

(10)

当第i个目标在所有雷达的跟踪时间均超出时间限制，此时的最优解为前i-1个目标的跟踪情况；当第i个目标在部分或全部雷达的跟踪时间未超出时间限制，此时的最优解为“未超出时间限制的雷达对目标i进行跟踪”和“不对目标i进行跟踪”多种情况下优先级之和最大的那种跟踪情况。

步骤3以自底向上、从左到右的方式，计算得到优先级之和的最大值。

步骤4上述计算得到优先级之和的最大值，利用最优解回溯找出解的组成，依次判断雷达j是否对目标i进行跟踪：

若f(i,T1,T2,…,TM)=f(i-1,T1,T2,…,TM)说明没有雷达对目标i进行跟踪；若f(i,T1,T2,…,TM)=f(i-1,T1,…，Tj-tij,…,TM)+pi说明雷达j对目标i进行跟踪，此时雷达j可用的时间资源将减去跟踪目标i消耗的时间资源；i的初始值为n，一直遍历到i=0，找到所有解，给出对n个目标的跟踪情况。

4 算法验证

4.1 评价指标

为了验证上述算法设计的有效性及其性能优劣，本文使用下列3种算法进行比较：

算法1基于负载最小[5]进行目标分组，基于填充设计[13-14]进行时间规划；

算法2基于优先级[10]进行时间规划，基于负载最小进行目标分组；

算法3本文提出的基于背包问题设计的算法进行目标分组和时间规划。

参照(5)式，这里使用实现价值率来对比3种算法的调度性能。实现价值率[20](HVR)是指成功调度的任务其优先级之和与所有需要调度的任务其优先级之和的比值，如 (11) 式所示。

(11)

(11)式反映了算法的任务调度成功率以及是否满足重要性原则的情况[21]。

4.2 仿真验证

首先进行仿真验证，具体的仿真场景设置为：使用2部雷达跟踪多个目标，雷达1的位置为(500 km,0 km)，雷达2的位置为(0 km,0 km)。目标位置、目标速度、威胁和敌意等属性为随机数，其中位置的范围均为0～1 000 km，速度的马赫数范围为0～10，威胁和敌意是0～1之间的任意值。根据前文介绍的方法求得各个目标跟踪所用的时间资源和优先级，选取两雷达连线的中点作为定点求目标的绝对优先级。图2表示的是2部雷达跟踪随机产生的20个目标的仿真场景。

图2 仿真场景设置Fig.2 Simulation scene setting

仿真参数设置与结果如下：

1) 给定2部雷达可用的时间资源均为20 ms，跟踪目标数为20个，随机进行10次测试，仿真结果如图3所示：当时间资源无法实现对所有目标的跟踪时，3种算法的调度结果显示本文提出的算法其实现价值率明显优于其他两种算法，10次随机测试避免了偶然情况的发生。

图3 随机10次测试的实现价值率对比Fig.3 Comparison of hit value ratios in 10 random tests

2) 给定2部雷达可用的时间资源均为30 ms，跟踪目标数分别设为10，20，……100个，随机产生目标进行测试，仿真结果如图4所示：当时间资源充足时，3种算法均能实现对所有目标的跟踪；在时间资源有限时，本文提出的算法其实现价值率整体优于其他两种算法。

图4 不同目标数的实现价值率对比Fig.4 Comparison of hit value ratios of different target numbers

4.3 试验验证

对某外场试验得到的目标先验信息进行处理，此次试验的具体设置为：雷达1部署在(280 km,370 km)，雷达2部署在(0 km,0 km)，目标远离雷达进行运动。采用粗跟踪获取所有目标的态势信息，并从中选取14个重点目标进行精跟踪，精跟踪的采样间隔为200 ms. 这里要求对目标进行连续跟踪，图5显示了某一时刻雷达与目标的分布位置。由于雷达的搜索、监视和粗跟踪等工作方式占用了大部分时间资源，本次试验中2部雷达每次调度用于精跟踪的时间资源均为10 ms，使用4.1节中的算法进行验证，最后的结果如图6所示。

图5 试验场景(14个重点目标)Fig.5 Test scene (14 main targets)

图6 试验验证结果Fig.6 Test verification results

调度开始之初，目标距雷达较近，精跟踪消耗的时间资源较少，3种算法均能实现对所有目标的跟踪；随着目标逐渐远离雷达，精跟踪所消耗的时间资源随之增加，雷达用于精跟踪的时间有限，后续调度无法实现对所有目标的跟踪，此时，本文提出的算法整体优于其他两种算法。

4.4 验证分析

通过上面的验证结果可以发现：算法1中先分组后进行时间规划的方法在对较少目标进行连续跟踪时，实现价值率明显低于本文的算法，这是因为试验场景中目标分布不均时，部分雷达存在剩余资源未利用，其时间资源浪费较多；而当目标数目逐渐增加时，其资源浪费减少，实现价值率略低于本文的算法。算法2保证了重要目标可以得到跟踪，但高优先级的目标可能会占用较多的时间资源，影响对其他目标的跟踪，跟踪目标数目较少，在仿真场景目标较为分散时，其实现价值率明显低于本文算法；而试验场景目标较为聚集，跟踪目标的时间相差不大，高优先级的目标并不会占用特别多的时间资源，某些时刻时具有较为优异的实现价值率。

但无论哪种场景，本文提出的基于背包问题联合实现目标分组和时间规划的算法在考虑目标优先级情况下合理分配时间资源，从而可以在有限时间内跟踪更多的目标，同时使跟踪目标的优先级之和更大，保证重要目标得到跟踪和较高的实现价值率。

5 结论

本文提出了一种基于背包问题的多相控阵雷达多目标跟踪的时间资源管理算法，在时间资源有限时联合实现目标分组和时间规划。依据充分利用时间资源和保证重要目标得到跟踪的考虑，使用最大化跟踪目标优先级之和作为目标函数，并通过动态规划的思想求解时间资源问题，最后的仿真结果说明了算法的有效性。从背包问题的角度考虑相控阵雷达选择跟踪目标的问题，使得问题的求解算法更加丰富，给后续的研究者提供了一种思路。

参考文献(References)

[1] MIR H,ABDELAZIZ F B.Scheduling of tasks with fuzzy dwell times in a multifunction radar[C]∥Proceedings of 2010 Second International Conference on Engineering System Management and Applications.Sharjah ,United Arab Emirates:IEEE,2010.

[2] TIAN T W,ZHANG T X,KONG L J.Timeliness constrained task scheduling for multifunction radar network[J].IEEE Sensors Journal,2019,19(2):525-534.

[3] CHARLISH A,WOODBRIDGE K,GRIFFITHS H.Phased array radar resource management using continuous double auction[J].IEEE Transactions on Aerospace and Electronic Systems,2015,51(3):2212-2224.

[5] NARYKOV A S,KRASNOV O A,YAROVOY A.Algorithm for resource management of multiple phased array radars for target tracking[C]∥Proceedings of the 16th International Conference on Information Fusion.Istanbul ,Turkey:IEEE,2013:1258-1264.

[6] HUANG J,ZHENG S,MIAO L.Resource management of multiple phased array radars for multi-target tracking[C]∥Proceedings of 2019 International Conference on Control,Automation and Information Sciences.Chengdu,China:IEEE,2019.

[7] XIANG Y J,AKCAKAYA M,SEN S,et al.Target tracking via recursive Bayesian state estimation in radar networks[C]∥ 2017 51st Asilomar Conference on Signals,Systems,and Computers.Pacific Grove,CA,US:IEEE,2017:880-884.

[8] 童俊,单甘霖.基于修正Riccati方程与Kuhn-Munkres算法的多传感器跟踪资源分配[J].控制与决策,2012,27(5):747-751.

TONG J,SHAN G L.Study of multi-sensor allocation based on modified Riccati equation and Kuhn-Munkres algorithm[J].Control and Decision,2012,27(5):747-751.(in Chinese)

[9] JIMÉNEZ M I,VAL L D,VILLACORTA J J,et al.Design of task scheduling process for a multifunction radar[J].IET Radar,Sonar &Navigation,2012,6(5):341-347.

[10] 张浩为,谢军伟,盛川.综合优先级规划下的相控阵雷达自适应调度方法[J].兵工学报,2016,37(11):2163-2169.

ZHANG H W,XIE J W,SHENG C.Adaptive scheduling algorithm over comprehensive priority for phased array radar[J].Acta Armamentarii,2016,37(11):2163-2169.(in Chinese)

[11] 陆晓莹,程婷,何子述,等.相控阵波束驻留调度综合优先级构造方法[J].现代雷达,2019,41(2):43-48.

LU X Y,CHENG T,HE Z S,et al.A synthetic priority construction method for phased array radar with adaptive dwell sche-duling algorithm [J].Modern Radar,2019,41(2):43-48.(in Chinese)

[12] JEAUNEAU V,BARBARESCO F,GUENAIS T.Radar tasks scheduling for a multifunction phased array radar with hard time constraint and priority[C]∥Proceedings of 2014 International Radar Conference.Lille,France:IEEE,2014.

[13] SPASOJEVIC Z,DEDEO S,JENSEN R.Dwell scheduling algorithms for phased array antenna[J].IEEE Transactions on Aerospace and Electronic Systems,2013,49(1):42-54.

[14] MIR H S,GUITOUNI A.Variable dwell time task scheduling for multifunction radar[J].IEEE Transactions on Automation Science and Engineering,2014,11(2):463-472.

[15] 毕增军.相控阵雷达资源管理技术[M].北京:国防工业出版社,2016:154-155.

BI Z J.Phased array radar resource management[M].Beijing:National Defense Industry Press,2016:154-155.(in Chinese)

[16] ZHANG Y S,PAN M H,HAN Q H.Joint sensor selection and power allocation algorithm for multiple-target tracking of unmanned cluster based on fuzzy logic reasoning[J].Sensors,2020,20(5):1371-1395.

[17] HAN Q,PAN M,ZHANG W,et al.Time resource management of OAR based on fuzzy logic priority for multiple target tracking[J].Journal of Systems Engineering and Electronics,2018,29(4):742-755.

[18] 郭坤鹏,左燕,薛安克.一种基于模糊逻辑优先级的雷达任务自适应调度算法[J].江南大学学报(自然科学版),2013,12(5):591-595.

GUO K P,ZUO Y,XUE A K.An adaptive task scheduling algorithm based on the fuzzy logic priority for multifunction radars[J].Journal of Jiangnan University (Natural Science Edition) ,2013,12(5):591-595.(in Chinese)

[19] 徐小平,庞润娟,王峰,等.求解0-1背包问题的烟花算法[J].计算机系统应用,2019,28(2):164-170.

XU X P,PANG R J,WANG F,et al.Fireworks algorithm for solving 0-1 Knapsack problems[J].Computer Systems &Applications,2019,28(2):164-170.(in Chinese)

[20] 张浩为,谢军伟,张昭建,等.基于混合自适应遗传算法的相控阵雷达任务调度[J].兵工学报，2017，38(9)：1761-1770．

ZHANG H W,XIE J W,ZHANG Z J，et al．Task scheduling of phased array radar based on hybrid adaptive genetic algorithm[J].Acta Armamentarii,2017,38(9):1761-1770．(in Chinese)

[21] 杨善超,田康生,李宏权,等.综合优先级下反导预警相控阵雷达任务调度算法[J].兵工学报,2020,41(2):315-323.

YANG S C,TIAN K S,LI H Q,et al.Comprehensive priority-based task scheduling algorithm for anti-missile early warning phased array radar [J].Acta Armamentarii,2020,41(2):315-323.(in Chinese)