楊潔 李國騰 曾耀平

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

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

0? ? 引言

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

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

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

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

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

1? ? 問題分析

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

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

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

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

第二個約束，確保在計劃時將任務僅分配給單個時間軸。沒有任務丟失的調(diào)度問題是NP難題[6]?？梢钥闯?，聯(lián)合任務的選擇和調(diào)度也是NP難題。

2? ? 解決方法

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

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

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

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

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

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

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

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

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

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

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

2.1? 數(shù)據(jù)記錄

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

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

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

2.2? 價值網(wǎng)絡架構(gòu)

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

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

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

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

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

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

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

3? ? 仿真結(jié)果

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

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

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

4? ? 結(jié)語

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

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

[參考文獻]

[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]童行行.基于機器學習的網(wǎng)絡流量分析研究[D].北京：清華大學，2015.

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

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

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

（編輯 何 琳）