基于背包問題的多相控陣雷達多目標跟蹤時間資源管理算法

丁海婷，周琳，刁偉峰

(南京電子技術研究所，江蘇 南京 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)