基于機器學習的認知雷達資源管理

楊潔 李國騰 曾耀平

摘 要：現代雷達可以設計成多種功能，如監視、跟蹤和火災控制。每個功能都要求雷達執行許多收發任務。這就出現了將雷達資源分配給不同任務的問題。具體而言，雷達資源管理（RRM）模塊對這些任務的參數選擇、優先級和調度進行決策，在超負荷情況下，RRM變得特別具有挑戰性，有些任務可能需要延遲甚至放棄。隨著多通道雷達變得越來越智能，大大提高了執行任務的能力，但它也使任務調度復雜化。之前的研究選擇使用分支和約束（B&B）方法來解決這一問題。文章使用B&B方法的結果來訓練一個基于機器學習的調度器，通過使用神經網絡估計搜索樹節點的值來加快B&B方法。結果表明，使用神經網絡結合B&B方法得到了一個接近最優解，同時顯著降低了計算復雜度。

關鍵詞：機器學習;認知雷達;分支定界法

0? ? 引言

認知雷達（CR）被定義為一種進行智能信號處理的雷達，它建立在通過雷達與周圍環境[1]的交互學習的基礎上。CR的關鍵要素是通過觀察獲取知識，并在實際決策中使用這些知識。本文考慮了一種多功能認知雷達（MFR）中雷達資源管理（RRM）的方法。

MFR通過執行一些收發任務來處理各種功能，如廣域監視和跟蹤多個目標在這種情況下，可用的雷達資源，特別是時間、頻率和能量，需要以有效的方式分配給不同的任務。RRM模塊對[2]參數選擇、優先級和任務調度進行決策。通常，在某些過載情況下，任務數量超過MFR的能力，其中一些任務可能需要延遲甚至放棄，因此RRM變得特別具有挑戰性。

目前已經開發了多種技術用于多功能雷達的資源管理[3-4]，由于是RRM，任務調度通常是一個NP難題，需要考慮的一個共同主題是將RRM分為兩個步驟[2]。第一步是確定任務參數，例如優先級、停留時間和重訪間隔，方法是針對每一個任務單獨使用基于規則的方法，或者在考慮所有任務的情況下，通過對所有任務進行聯合優化來實現整體效用函數資源約束[3]。確定參數后，第二步是任務選擇和調度。在選擇階段，根據資源限制選擇任務的子集，并制定績效因數，其余的任務被刪除。在調度階段，將時隙分配給任務，以上步驟也可以反復迭代以提高性能。

在單獨的軌道上，多通道、多頻率雷達變得越來越可行。多通道雷達帶來了在不同信道上同時執行多個任務的可能性。然而，這種額外的能力也使已經困難的RRM問題復雜化。除了調度外，任務現在必須分配給通道。本文考慮了多通道多功能雷達的聯合資源管理問題，即一個能夠同時執行多個任務的聯合雷達。在考慮多通道雷達的RRM時，本團隊以往都是使用的最優的分支定界（B&B）技術[5]。但是，正如任何NP難問題的解決方案都必須考慮指數計算復雜性，并且對于任何超出任務列表的事情，都不能期望它可以實時執行。由于需要平衡性能和復雜性，本文將機器學習（ML）技術引入到多通道MFR的RRM問題中。本研究的ML方法學習了以前執行的B&B算法（在訓練階段）。然后將所獲得的知識用于未來的調度問題。具體來說，本研究使用神經網絡來估計B&B方法中與節點相關的值，從而收斂到接近最優解，同時顯著地減少了計算負擔。該值是從給定節點開始可以獲得的完整解決方案的最小成本，并且如果它離最優解太遠，則從樹中消除節點及其子分支。

使用監督學習對神經網絡進行訓練。通過運行得到訓練數據集（標記數據），B&B算法離線處理相對較小的問題，生成的訓練數據使本研究能夠訓練卷積神經網絡，本研究的仿真結果表示，計算負載的性能損耗低。

1? ? 問題分析

問題如下：本研究考慮在一個時間窗口內，在K個相同的通道上執行N個任務。任務可以在不同的通道上同時執行，但不能在給定的時間軸上重疊。此外，本研究考慮了非搶占式調度場景，其中正在運行的任務直到完成才停止。對于每個任務，都有一個起始時間rn，之后才可以執行任務。還有一個截止時間Dn，在此之后，任務被刪除。這第n個（1≤n≤N）任務的執行時間（駐留時間）用ln表示。

例如，考慮一個跟蹤任務。任務的開始時間由所需的跟蹤精度和最后一次測量的時間決定。截止時間取決于雷達的波束寬度和目標的估計軌跡。在假定目標已從雷達波束中移出后，該任務將不會執行，因此，它被丟棄將產生一定的成本，所以，需要采取進一步措施來補償下降。

一個計劃的但延遲的任務的延遲成本在這里被建模為與延遲成線性比例，令en為任務n開始執行的時間，延遲成本由ωn（en-rn）給出，其中ωn為衡量延遲的權重。讓二進制變量xnk表示任務n是否在第k個時間軸上調度（=1）。如果xnk=? ?0k，則刪除任務n。然后第n個任務相關的成本為。本研究的聯合任務選擇和調度問題是總成本C的最小化，由下式給出：

在此，優化變量是xnk和en。如果計劃了任務，即xnk=1，對于一些k，則還需要確定執行時間en。因此，本研究的優化問題是：

第二個約束，確保在計劃時將任務僅分配給單個時間軸。沒有任務丟失的調度問題是NP難題[6]。可以看出，聯合任務的選擇和調度也是NP難題。

2? ? 解決方法

在公式（2）[5]中，可以采用B&B過程來找到問題的最優解。B&B方法的主要缺點是執行時間，在任務數量上可能是指數的。執行時間取決于任務參數，B&B過程是重尾的，也就是說，雖然許多執行在合理的時間內是可能的，但有一些情況需要一個較長的執行時間。為了降低B&B算法的復雜度，本文提出了一種利用神經網絡加速搜索的近似方法。

B&B方法隱式地列舉了搜索樹上所有可能的解決方案。樹的根節點表示整個解決方案空間。其余節點與解空間的子集相關聯。分支操作將父節點的空間分割成結果子節點的子空間。每個子空間表示部分解。在搜索過程中，使用邊界和優勢規則從樹中消除節點。除了這些規則外，本研究還建議使用神經網絡來促進從搜索樹中消除未產生的節點。一旦對整個樹進行了遍歷，就會返回搜索中找到最佳解決方案。

對于公式（2）的問題，該樹的每個節點代表一個部分調度，包括任務的子集。本研究搜索任務的最佳執行時間，可以變換為搜索任務的最佳排列。本研究通過以下方式構造搜索樹。根節點為空序列，一個分支代表選擇還沒有被安排在父節點和其限期尚未通過的任務。所選任務將附加到父節點的序列中，以獲取結果子節點的序列。使用“序列到計劃的映射”[5]獲得計劃，該計劃在序列的元素上進行迭代，并將每個任務放在最早可用的時間軸上。使用這種技術，尋找最佳序列。

優勢規則是特定于問題的，并且經過數學驗證的規則，用于從搜索樹中消除節點。如果可以證明所有解決方案的性能在給定的節點S1比另一個節點S2的解決方案的性能更差，那么S1是由S2主導的，因此可以從樹中消除S1。

下界和上界也可以用于修剪搜索樹的節點。如果給定節點S的所有解的代價上的下界大于最優解的代價上界UB，則可以得出S不包括最優解。因此，S可以從樹中消除。上界可以使用啟發式方法初始化，并且可以在搜索過程中使用最佳解決方案發現-到目前為止進行更新。

在與節點關聯的部分時間表中，一組任務被安排在特定的時間表上，具有已知的執行時間和延遲成本。此外，截止時間已經超過所有時間表的任務也被取消。其余的任務還沒有安排或放棄。狀態v*（s）定義為部分調度節點的表示。它包括任務的初始參數以及它們在相應的部分時間表中的狀態（計劃、刪除或未計劃）。

假設有一個值函數v*（s），其確定一個完整的時間表，表示從一個給定狀態S開始至少達到的成本，這里的價值函數是S子空間中最佳解決方案的成本。搜索的深度可通過截斷樹S的價值函數得到，替換的最佳時間表的成本中的子樹在S內是降低的。本研究使用神經網絡，產生價值函數的近似vθ（s）≈v*（s），在這θ表示價值網絡的權重。以狀態作為輸入，輸出給定狀態的近似最優值。這樣的網絡可以使用B&B算法脫機執行獲得的標記數據進行訓練。價值網絡在給定節點S處所做的預測與UB進行比較，如果預測的成本足夠大，則可以從搜索樹中消除節點S。這樣，B&B方法通過刪除不太可能最終得到最優解的節點而變得更快。標有"*"的用于記錄數據，而不用于算法的必需部分。搜索樹已實現使用堆棧數據結構。深度優先搜索策略用于遍歷樹的節點，本研究修改了[7]的B&B方法以包括任務刪除。堆棧的每個元素都是一個元組，元組由一系列任務T（代表部分調度），在T之后立即安排的一組任務PF，一組未計劃的任務NS和已刪除的一組任務DR組成。增強分支定界法的具體步驟如下：

在節點S，分支是通過從PF中選擇具有最小起始時間的任務a來執行的。然后，將任務a從PF中刪除，并添加到NS中，a被安排在當前分支中，對于S的其余分支，它還沒有被安排。因此，它被添加到NS集中。這樣，當在節點S處添加一個新的分支時，將NS集的任務與PF集的元素合并，形成第一組可能的節點。在根節點，可能的第一組節點被初始化為包含所有任務，NS和DR被設置為空。上界UB包含在搜索過程中獲得的最佳調度的成本。UB最初設置為無窮大，根節點被推到堆棧的頂部，然后，只要堆棧不是空的，就執行以下過程：在每次迭代時，檢查堆棧頂部的節點，如果可能的第一組PF為空，則節點將從堆棧中刪除，在刪除節點之前，檢查未調度集合NS中是否有任何任務，如果NS為空，則節點是終端，并表示完整的解決方案。在這種情況下，將總體成本C與UB進行比較，如果有改進，則應該更新UB。在堆棧頂部可能的第一組節點不是空的情況下，使用PF任務生成一個新節點。具體來說，設置一個PF中最小的任務開始時間。本研究從PF中刪除a并在T的末尾附加它以獲得新節點的序列T'。新節點PF的可能第一組PF'被設定為PF和NS的并集。刪除的任務DR'是從DR繼承的，新節點NS的未計劃集合被設置為空。然后，將任務a添加到NS。

在生成新節點后，應該確定是否應該將其添加到堆棧中，以便下一次迭代時進行進一步的研究，或者可以忽略它，從而進行修剪。要做到這一點，本研究首先對T'這條規則規定檢查，第T'任務的執行時間的順序應該不減少啟動時間的主導地位規則，否則，T'占主導地位，無法得出最優解。接下來本研究檢查PF'中的任務，任何截止時間在頻道最早可用時間之前的任務都被刪除。此時，可以計算新的部分解的延遲和下降成本之和，再從該節點導出的任何完整解上提供一個下界C'。如果這個成本不低于UB，則可以忽略新節點。此外，如果T'不能映射到活動計劃，則它可以被丟棄。一個較好的時間表是沒有任務可以提前完成，也不延遲另一個任務。對PF'中的任務檢查，它們中的任何一個是否可以在T'中的最后一個任務之前進行調度且不造成延誤，以確定T'是否是活動的。

接下來，本研究檢查T'是否是一個最低調度。一個最低活動時間表是不交換兩個相鄰的任務就可以改善時間表。任務a的相鄰任務被定義為在調度任務a之前，在每個時間線的最終時隙上調度的任務集。檢查時間表是否為最低活動的條件與上面相同，但也需要考慮任務刪除。在這種情況下，考慮時間軸的可用時間而不是完成時間，下降成本取代延遲成本。如果新節點是最低活動的，則檢查它是否也是一個完整的解決方案。在這種情況下，更新父節點的統計數據，以便進行數據記錄。

除了檢查C是否小于UB之外，還可以使用價值網絡從新節點得到預計的最低最終成本，并將其與UB進行比較。如果估計值大于UB×α，則從搜索中刪除該節點。引入縮放系數α≥1以使該算法對估計誤差具有魯棒性。使用較大的α值可以實現更好的性能，但這意味著從搜索樹中刪除更少的節點。如果通過了邊界和優勢規則，則新節點將被推到堆棧的頂部。完成此步驟后，搜索將繼續進行下一個迭代。最后，一旦探索了整個樹，就會返回找到的最佳解決方案就。

2.1? 數據記錄

本研究在搜索過程中記錄節點的統計信息，將它們用作標記數據以監督學習價值神經網絡。對于給定的節點S，有一個標志∏s，表示是否已經達到至少一個完整搜索過程。在∏s終止的情況下，記錄其最佳終端解決方案的成本。

如上一節中所述，在分支步驟中，本研究檢查新的子節點S'是否為最低活動狀態，如果為真，則接下來檢查∏s是否為完整解決方案，如果∏s的可能第一集合為空，則代表到達了終端節點，即完整的解決方案。在這種情況下，父節點S的統計信息將被更新。如果∏s為假或S'的成本小于∏s的最佳終端成本，則S將設置為真并且最佳終端成本的S將被設置為s'的成本。

在B&B程序中，在從堆棧中刪除給定節點S之前，本研究檢查其是否終止，即∏s是否為真。在這種情況下，S的父節點的統計信息將更新。此外，節點S及其所有統計信息都被記錄下來。而且，記錄的給定節點的最佳終端成本是v*（s），記錄的標記數據（s，v*（s））用于價值網絡的監督學習中。

2.2? 價值網絡架構

本研究使用6層卷積神經網絡實現價值網絡[8]。前三層是卷積的，最后三層是完全連接的。在每個卷積層，將輸入與濾波器卷積以產生輸出特征。濾波器的系數是使用監督學習獲得。每個層的輸出經過一個非線性函數（整流函數），然后傳遞到下一層。網絡的最終輸出是一個標量數，表示輸入部分調度的估計最小總體成本。網絡的輸入是一個矩陣，每個列表示一個任務，每一行表示相應任務的一個特征。

在本文中，考慮了給出的每個任務的14個特征（見表2）。假設有4個通道可用于任務調度。每個通道都有一個輸入特性，本團隊使用一個熱編碼來表示任務被調度的通道。對于每個任務，對應于任務計劃所在信道的輸入特征設置為1，其余輸入時間軸特征設置為0。

對于卷積層，使用寬度為7的過濾器（查看每個步幅的? ?7個連續任務的特征）。每層使用64個濾波器，每個卷積層的輸出具有64個特征。本研究已經為第一個完全連接的層考慮了512個隱藏單元。第二個完全連接的層具有128個隱藏單元，最后一層具有一個標量。

訓練階段通常使用正則化方法，以避免訓練樣本過擬合神經網絡的問題。這些方法的一般模式是幫助網絡學習訓練樣本的[9]，而不是記憶它們。本研究使用正則化最常用的方法退火技術[10]，在訓練階段，每個層的單位的固定百分比被隨機丟棄，導致了基本網絡的訓練子網絡，是一個好的特性。在訓練階段中，還使用批歸一化來改進優化過程。設H是給定激活層的的一部分。為了規范H，本研究用H'代替它

其中μ和σ分別表示單位的均值和標準差。對于卷積層，這些矩是在H的前三個維度上得到的，因此它們的長度為64。對于完全連接的層，矩是在H行上計算的，因此，它們的長度等于隱藏單元的數目。通過廣播來執行公式（3）中的減法和除法運算。在訓練過程中，使用當前批次的樣本均值和方差獲得μ和σ。在推理過程中，μ和σ可以被訓練期間收集的運行平均值所取代。將卷積層的激活標準化可能會降低網絡的表現力。因此，歸一化批次H'被γH'+β所取代，γ和β是在訓練階段學習的變量。

網絡的權重可以通過使用梯度下降對訓練狀態結果（s，v*（s））進行回歸來找到，以最小化估計值vθ（s）和目標值之間的均方誤差（MSE）[11]。相應的真實結果v*（s）如下：

培訓數據是通過離線執行B&B方法獲得的，如上面所述。該網絡使用90 000個樣本進行了訓練。通過使用自適應矩估計優化方法使損失最小化來獲得權重。對于大小為100的迷你批處理，本研究使用100 000步的隨機改組（RR）方法進行處理。

3? ? 仿真結果

本研究現在給出了仿真結果，說明了該方法的性能。本研究考慮一種具有K=4個相同信道的多通道雷達。有N=35個任務分布在100 ms的時間線窗口上。目標是安排任務，使公式（2）中的目標最小。在本研究的仿真中，任務的開始時間均勻分布在100 ms的時間窗口上。其中，。

對于每個任務，起始時間和截止時間之間的間隔，即dn-rn從μ（2，12）中采樣。任務長度ln是根據μ（2，11）分配的。此外，下降成本Dn和拖延權重ωn分別分布在μ（100，500）和μ（1，5）上。在仿真中，本研究使用蒙特卡洛方法進行100次試驗，以獲得每種方法的平均性能。

B&B的運行時間和所提出的方法與訪問節點的數量成正比。正如預期的那樣，B&B算法具有最佳的性能和最高的復雜度。B&B方法的平均訪問節點為13 134個。在使用α=1的價值網絡的情況下，平均訪問節點數下降到僅342個節點，這比沒有價值網絡的B&B方法的訪問節點數少了大約38倍。然而，這種復雜性降低導致性能下降。本研究通過增加縮放系數可以獲得更好的性能。用α=2，平均成本為49。得到3個顯著低于啟發式方法的平均成本。然而，這時訪問節點的平均數量增加到962個，但仍然比B&B算法中的平均訪問節點少約14倍。性能可以隨著α=3而進一步提高，但是計算負擔略有增加。EST和ED分別是最早開始時間最早和最早截止時間最早的方法。SW指的是任務交換技術。最后三個列是使用具有不同比例系數的價值網絡增強的B&B方法的，結果如表3和表4所示。

4? ? 結語

本文考慮了多通道多功能雷達的雷達資源管理問題，介紹了如何利用機器學習技術在雷達運行過程中獲取知識，在未來的決策中使用這些知識。

分支定界算法為任務調度問題找到了最優解，但計算負擔較高。本研究展示了如何使用機器學習方法來降低分支定界方法的復雜性。在搜索樹的每個節點上使用一個價值網絡來預測節點的給定部分計劃中可以實現的最小成本。價值網絡是使用監督學習和從最佳分支定界方法的離線執行中獲得的數據樣本進行訓練的。雖然這大大減少了搜索樹的訪問節點數量，但性能不會受到太大的影響。

[參考文獻]

[1]HAYKIN S.Cognitive radar：a way of the future[J].IEEE Signal Processing Magazine，2006（1）：30-40.

[2]MOO P W，DING Z.Adaptive radar resource management[J].Adaptive Radar Resource Management，2015（2）：141–148.

[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（3）2212–2224.

[4]MIRANDA S L C，BAKER C J，WOODBRIDGE K，et al.Comparison of scheduling algorithms for multifunction radar[J].IET Radar Sonar and Navigation，2007（6）：414–424.

[5]SHAGHAGHI M，ADVE R S.Task selection and scheduling in multifunction multichannel radars[C].Seattle：In 2017 IEEE Radar Conference（RadarConf），2017.

[6]LENSTRA J K，KAN A R，BRUCKER P.Complexity of machine scheduling problems[J].Annals of Discrete Mathematics，1977（1）：343–362.

[7]JOUGLET A，SAVOUREY D.Dominance rules for the parallel machine total weighted tardiness scheduling problem with release dates[J].Computers & Operations Research，2011（9）：1259–1266，2011.

[8]童行行.基于機器學習的網絡流量分析研究[D].北京：清華大學，2015.

[9]顧依依，談詢滔，袁玉波.基于凸邊界的學習樣本抽取方法[J].計算機應用，2019（8）：2281-2287.

[10]曾靖，李文，李宏民，等.基于模擬退火算法的連續時間系統的時域綜合[J].電子測量與儀器學報，2019（12）：189-195.

[11]姜鵬飛，蔡之華.基于遺傳算法和梯度下降的RBF神經網絡組合訓練方法[J].計算機應用，2007（2）：366-368.

（編輯 何 琳）