袁 野 楊 劍 劉辛雨 易 偉 孔令講

①(電子科技大學信息與通信工程學院 成都 611731)

②(火箭軍工程大學導彈工程學院 西安 710025)

1 引言

利用空間上廣域分布的多雷達節(jié)點協(xié)同工作，可從不同頻段、不同時空、不同極化方式下充分挖掘探測目標雷達散射截面積(Radar Cross Section,RCS)的多樣性[1–3]，顯著提升隱身、微弱等目標的探測性能。同時，多雷達系統(tǒng)分布式探測構(gòu)型具備極強的抗干擾能力，在復雜電磁場景下?lián)碛懈鼜姷纳媪4,5]。鑒于多雷達協(xié)同在探測和對抗方面的效能得益，圍繞多雷達協(xié)同的相關(guān)研究逐漸成為當前雷達信號處理領(lǐng)域的前沿和熱點問題。

隨著相控陣、頻控陣、數(shù)字陣列等雷達體制的出現(xiàn)和逐步成熟，多功能雷達的概念和相關(guān)研究也得以發(fā)展。多功能雷達能夠通過調(diào)整其工作模式和工作參數(shù)實現(xiàn)不同的探測功能，以完成搜索、跟蹤、確認、制導等多元化的作戰(zhàn)任務(wù)，例如：相控陣雷達能夠以邊掃描邊跟蹤(Track While Scan,TWS)、搜索加跟蹤(Track and Search,TAS)[6]兩種不同模式實現(xiàn)不同數(shù)據(jù)率下的目標搜索和跟蹤任務(wù)。在此背景下，如何保證多功能雷達系統(tǒng)在復雜多元化的任務(wù)場景中的適應(yīng)性，以提升其任務(wù)執(zhí)行效能(如雷達數(shù)據(jù)率[7]、探測威力[2]、跟蹤精度[8,9]、低截獲概率[10]等不同類型任務(wù)指標)，成為當前多功能雷達、多雷達協(xié)同探測等領(lǐng)域研究的熱門問題。圍繞此需求，現(xiàn)有工作主要從雷達系統(tǒng)的多任務(wù)動態(tài)規(guī)劃和資源優(yōu)化調(diào)度兩個角度展開相關(guān)問題研究。其中，多任務(wù)動態(tài)規(guī)劃主要從宏觀任務(wù)場景出發(fā)，解決多個探測任務(wù)如何在多個雷達間合理分配執(zhí)行，或如何規(guī)化多個任務(wù)在單個雷達節(jié)點的執(zhí)行先后順序的問題，以提升多任務(wù)的綜合執(zhí)行效率[11](如雷達數(shù)據(jù)率、任務(wù)執(zhí)行耗時等)；相較而言，雷達系統(tǒng)資源優(yōu)化調(diào)度則從微觀的發(fā)射資源粒度級出發(fā)，旨在結(jié)合具體探測任務(wù)，通過優(yōu)化雷達系統(tǒng)資源(如節(jié)點位置[12]、發(fā)射功率[13–16]、駐留時間[17,18]、工作帶寬[19]等)，以提升特定探測任務(wù)性能(如檢測概率、定位誤差、跟蹤精度等)或達到預(yù)設(shè)的探測任務(wù)性能，最小化系統(tǒng)資源消耗。

多任務(wù)動態(tài)規(guī)劃問題的核心在于如何實現(xiàn)雷達節(jié)點執(zhí)行任務(wù)的合理、高效分配，并完成雷達節(jié)點任務(wù)執(zhí)行線程的優(yōu)化排布，以提升多任務(wù)的執(zhí)行效率或盡量降低任務(wù)執(zhí)行延遲。近年來，多任務(wù)動態(tài)規(guī)劃也依托多功能雷達系統(tǒng)、相控陣雷達等，逐步完善了其相關(guān)理論算法研究[11,20–24]。朱希同等人[21]針對天波超視距雷達探測場景，提出了一種基于綜合優(yōu)先級最大化的雷達波位調(diào)度算法。根據(jù)任務(wù)屬性和工作場景確定了任務(wù)的最終優(yōu)先級，然后根據(jù)任務(wù)優(yōu)先級完成了雷達波位掃描順序的安排；圍繞相控陣雷達任務(wù)分配場景，趙宇等人[22]提出了一種基于任務(wù)執(zhí)行時間偏移最小的任務(wù)規(guī)劃策略。通過最小化雷達的期望執(zhí)行時間和實際執(zhí)行時間偏移量與任務(wù)優(yōu)化級的加權(quán)求和，相控陣雷達任務(wù)規(guī)劃問題被建模成一個數(shù)學優(yōu)化問題。趙宇等人隨后分析了最優(yōu)解存在條件，并給出最優(yōu)解解析的求解方案；同樣針對相控陣雷達多任務(wù)規(guī)劃，展紅英[23]結(jié)合了遺傳和粒子群算法，實現(xiàn)了任務(wù)規(guī)劃問題的求解。

上述研究證明了雷達任務(wù)動態(tài)分配算法在提升任務(wù)執(zhí)行效率、降低執(zhí)行等待延時等方面具有顯著效果。但當前大部分多任務(wù)動態(tài)規(guī)劃研究還基于單個雷達節(jié)點任務(wù)場景開展，鮮見針對一般化的多雷達、多任務(wù)場景的在線探測任務(wù)分配相關(guān)研究。而在多雷達場景下，任務(wù)動態(tài)規(guī)劃算法除了需要解決原本單雷達場景下的任務(wù)執(zhí)行線程優(yōu)化排布問題，在此之前，還需要完成“探測任務(wù)-雷達節(jié)點”的優(yōu)化分配，其對應(yīng)的數(shù)學模型更為復雜，優(yōu)化參量的維度也隨之增加，是一個更復雜且更具挑戰(zhàn)性的問題。而如前所述，多雷達協(xié)同是未來雷達目標探測形態(tài)的一種重要發(fā)展趨勢。實際場景中，多雷達協(xié)同系統(tǒng)通常也需要同時執(zhí)行多項探測任務(wù)。因此，如何在多雷達節(jié)點間完成多探測任務(wù)的合理分配規(guī)劃成為雷達目標探測領(lǐng)域一個亟待解決的前沿問題。

本文針對多雷達協(xié)同場景下的多任務(wù)在線分配需求，提出了一種基于任務(wù)效用最大化的多雷達協(xié)同在線任務(wù)分配算法。以探測任務(wù)的性能和任務(wù)執(zhí)行的等待時間分別構(gòu)建了任務(wù)質(zhì)量函數(shù)和任務(wù)效率函數(shù)，并以其加權(quán)求和完成了任務(wù)效用函數(shù)的建模；通過最大化任務(wù)效用函數(shù)，多雷達協(xié)同任務(wù)分配被建模成了一個整數(shù)規(guī)劃的混合變量優(yōu)化問題；隨后，本文提出了兩種算法，包括啟發(fā)式貪婪算法和基于凸松弛的兩步解耦算法(Convex Relaxationbased Two-Step Decoupling,CRTSD)實現(xiàn)了該問題的高效求解，相較而言，前者具備更快的計算效率而后者具備更高的優(yōu)化精度；最后，通過仿真實驗驗證了提出方法的有效性。

2 多雷達協(xié)同任務(wù)分配系統(tǒng)模型

考慮多雷達系統(tǒng)協(xié)同執(zhí)行多個探測任務(wù)的場景，系統(tǒng)中各節(jié)點以統(tǒng)一的時序周期工作，并在周期開始前進行協(xié)同任務(wù)分配，本文則主要解決多雷達系統(tǒng)單個周期探測任務(wù)的合理分配和執(zhí)行問題。

在某一特定探測周期開始時，考慮由N(N＞1)部雷達節(jié)點組成的協(xié)同探測系統(tǒng)收到Q個探測任務(wù)執(zhí)行請求，每個任務(wù)所在的位置(xq,yq)(q=1,2,...,Q)各不相同。探測系統(tǒng)需要在每部雷達任務(wù)執(zhí)行能力有限情況下，將這Q個探測任務(wù)優(yōu)化分配給N部雷達執(zhí)行，以實現(xiàn)多任務(wù)全局探測效能最優(yōu)。

數(shù)學上講，為表示任務(wù)-雷達的分配結(jié)果以及各部雷達對分配任務(wù)的執(zhí)行順序，定義Q=Perm{1,2,...,Q}為上述Q個任務(wù)序號的任一排列，則可以使用U|Q∈ZN×Q表示在特定任務(wù)排列 Q下，每個任務(wù)的分配結(jié)果：

為了更形象地解釋任務(wù)排列 Q 和任務(wù)分配U|Q變量對整個任務(wù)分配結(jié)果的影響，圖1給出了兩部雷達分配5個任務(wù)的場景，其中任務(wù)1、任務(wù)2、任務(wù)4分配給雷達1執(zhí)行，任務(wù)3、任務(wù)5分配給雷達2執(zhí)行?？梢园l(fā)現(xiàn)，在兩種不同的任務(wù)排列 Q情況下，即使任務(wù)分配結(jié)果U|Q相同，雷達執(zhí)行任務(wù)順序是不同的。因此，多雷達系統(tǒng)的任務(wù)分配和執(zhí)行過程需要利用任務(wù)排列 Q 和任務(wù)分配U|Q兩個變量表征。

圖1 任務(wù)排列與任務(wù)分配概念解釋Fig.1 An illustration of the concepts for task arrangement and task scheduling

2.1 探測任務(wù)屬性

多功能雷達通常需要執(zhí)行目標搜索、跟蹤、確認、制導等多類型任務(wù)[21]，每項待執(zhí)行任務(wù)通常擁有其任務(wù)重要性、執(zhí)行代價、實時性要求等特征。在任務(wù)規(guī)劃問題模型中，探測任務(wù)屬性主要用于描述各項探測任務(wù)的上述特征，以滿足多任務(wù)間多元化的探測資源需求。本文采用任務(wù)位置 (xq,yq)、任務(wù)重要性ρq和任務(wù)耗時tq來描述每項探測任務(wù)的基本屬性。

其中，0≤ρq≤1表示第q個探測任務(wù)的重要性，任務(wù)重要性用于表征該項任務(wù)執(zhí)行的優(yōu)先級。優(yōu)先級越高任務(wù)的重要性ρq值越大；tq表示第q個探測任務(wù)的執(zhí)行耗時，表示承接該項任務(wù)時，雷達節(jié)點需要付出的探測資源代價。

2.2 多雷達任務(wù)分配模型

在N部雷達協(xié)同執(zhí)行上述Q個探測任務(wù)時，每部雷達需消耗部分探測時間資源用于執(zhí)行分配到的任務(wù)?？紤]每部雷達的時間資源有限，此時存在以下雷達節(jié)點探測能力約束：

其中，t=[t1t2...tQ]T為任務(wù)執(zhí)行耗時向量；tn,max為雷達節(jié)點n(n=1,2,...,N)的最大可用時間資源。為簡化問題建模，本文假設(shè)一個探測任務(wù)同時只被一個雷達節(jié)點選取并執(zhí)行1若要消除該假設(shè)，可通過將一個待執(zhí)行任務(wù)q拆分成在同一個位置的多個子任務(wù)。例如：可將某項任務(wù)={(xq,yq),ρq,tq}，拆分成 k個子任務(wù)，其中。。因此，單個任務(wù)被選中次數(shù)以及所有雷達執(zhí)行任務(wù)的次數(shù)存在以下約束：

多雷達任務(wù)分配問題的本質(zhì)就是在式(4)和式(5)的約束下，將Q個探測任務(wù)在線分配給N部雷達，同時每部雷達將分得的任務(wù)在其任務(wù)執(zhí)行時間軸上進行優(yōu)化排布，以使多任務(wù)執(zhí)行的全局效能最大化。

圖2給出了Q=8項具有不同優(yōu)先級的任務(wù)分配給N=2部雷達的任務(wù)分配示意圖，其中雷達1、雷達2分別分得了5項和3項任務(wù)，且在其各自的任務(wù)執(zhí)行時間軸上把任務(wù)進行了執(zhí)行順序的排布。

圖2 任務(wù)規(guī)劃示意圖(N=2,Q=8)Fig.2 Schematic diagram of the task scheduling with N=2,Q=8

可以發(fā)現(xiàn)，由于不同任務(wù)擁有不同的屬性，不同的任務(wù)分配和執(zhí)行方案所帶來的探測效能及資源使用代價通常不同。因此，本文要解答的問題就是如何將多個探測任務(wù)分配給各個雷達，以及分配后的任務(wù)如何排序，以實現(xiàn)多任務(wù)全局探測效能的最優(yōu)。

3 多雷達協(xié)同任務(wù)分配效用函數(shù)模型

高效執(zhí)行協(xié)同任務(wù)分配的前提是制定一個可評估任務(wù)執(zhí)行效能的指標，并基于該指標實現(xiàn)多雷達協(xié)同任務(wù)分配。對此，本節(jié)提出了一種基于效用函數(shù)最大化的任務(wù)動態(tài)分配模型。首先基于任務(wù)質(zhì)量(Quality of Service,QoS)框架[13]，給出了一種多雷達協(xié)同任務(wù)分配全局效用函數(shù)的建模方案，然后基于構(gòu)建的效用函數(shù)，將多雷達協(xié)同任務(wù)分配建模成一個數(shù)學優(yōu)化問題；隨后，利用任務(wù)執(zhí)行距離、任務(wù)執(zhí)行等待時間，完成了對提出的多任務(wù)動態(tài)分配模型的實例化。

3.1 多雷達協(xié)同任務(wù)分配全局效用函數(shù)及優(yōu)化問題

本文基于QoS框架，將雷達的任務(wù)分配表示為關(guān)于效用函數(shù)最大化的數(shù)學優(yōu)化問題：

其中，φq(Q,U|Q)為任務(wù)q的效用函數(shù)，表示在特定任務(wù)分配方案{Q,U|Q}下任務(wù)q的執(zhí)行效能。上述優(yōu)化問題被寫成了Q個任務(wù)效用函數(shù)和對應(yīng)任務(wù)重要性的加權(quán)求和，以表示多任務(wù)的全局任務(wù)效能。求解該優(yōu)化問題后，問題的解即對應(yīng)多任務(wù)的分配方案及其在各雷達節(jié)點間的執(zhí)行順序?？紤]到大部分任務(wù)分配問題都主要關(guān)注任務(wù)優(yōu)化分配后的任務(wù)性能和執(zhí)行效率，因此，可將任務(wù)效用函數(shù)φq(Q,U|Q)進一步拆分成如下形式：

其中，ωq(U|Q)為任務(wù)q(q=1,2,...,Q)的歸一化任務(wù)質(zhì)量函數(shù)，用于表征特定任務(wù)分配方案{Q,U|Q}下該項任務(wù)能夠獲得的性能，質(zhì)量函數(shù)值越大則表明任務(wù)執(zhí)行所獲得的性能越高；eq(U|Q)為任務(wù)q的歸一化任務(wù)效率函數(shù)，用于表征該項任務(wù)的執(zhí)行效率，任務(wù)效率函數(shù)可被建模成一個與雷達時間資源呈負相關(guān)的函數(shù)。

在實際的探測場景中，上述歸一化任務(wù)質(zhì)量函數(shù)和任務(wù)效率函數(shù)的具體表達式可根據(jù)特定的任務(wù)類型和目標進行針對性的定義。例如：針對目標檢測任務(wù)，任務(wù)質(zhì)量函數(shù)可被定義為與檢測概率、虛警概率相關(guān)的函數(shù)[25]；而針對目標跟蹤任務(wù)，任務(wù)質(zhì)量函數(shù)則可被定義為目標參數(shù)估計的后驗克拉默-拉奧界(Posterior Cramér-Rao Lower Bound,PCRLB)相關(guān)函數(shù)，用于表征跟蹤目標狀態(tài)估計性能[26]。

3.2 基于任務(wù)-雷達距離指標的任務(wù)質(zhì)量函數(shù)

考慮到包括上述提到的檢測概率、跟蹤PCRLB在內(nèi)的大部分探測任務(wù)性能指標都與雷達接收信噪比(Signal to Noise Ratio,SNR)相關(guān)[27]。而根據(jù)雷達方程可知，當雷達節(jié)點的天線孔徑、接收機靈敏度等參數(shù)固定時，其接收SNR主要受雷達和目標間的雙程時延，即距離的4次方的影響。因此，不失一般性，本文提出了基于探測任務(wù)與雷達間距離的任務(wù)質(zhì)量函數(shù)，定義如下：

3.3 基于等待時間指標的任務(wù)效率函數(shù)建模

本文以任務(wù)等待時間的倒數(shù)實現(xiàn)任務(wù)效率函數(shù)的建模，基于等待時間的任務(wù)效率函數(shù)定義如下：

其中，(·)[a:b]表示向量 (·)的第a到第b個元素構(gòu)成的子向量，其中定義特殊情況 (·)[1:0]=0。的下標n*表示用于執(zhí)行任務(wù)q的雷達節(jié)點序號：

式(9)表明在同一個雷達節(jié)點中，任務(wù)的執(zhí)行效率與其等待時間成反比。當某個任務(wù)q排在雷達節(jié)點的第1個執(zhí)行時，其任務(wù)效率函數(shù)值eq(U|Q)=1，若后續(xù)等待時間越長，則任務(wù)效率函數(shù)值越低。

一般的探測任務(wù)規(guī)劃問題中，通常會有一個被執(zhí)行的期待時間窗，在時間窗內(nèi)執(zhí)行該任務(wù)，則通常認為該任務(wù)的執(zhí)行效率是滿足要求的。而需要注意的是，本文是將多雷達的任務(wù)執(zhí)行時間線周期化了，任務(wù)分配是針對某一個任務(wù)周期內(nèi)出現(xiàn)的探測任務(wù)。因此，本文認為在單個任務(wù)周期內(nèi)，所有需要分配的任務(wù)都是在其期待的執(zhí)行時間窗內(nèi)的。這種情況下，利用任務(wù)的等待時間對該周期內(nèi)不同任務(wù)執(zhí)行順序優(yōu)化，理論上可實現(xiàn)：(1)在任務(wù)數(shù)較少時，可在滿足任務(wù)執(zhí)行期待時間窗前提下，進一步提升多任務(wù)執(zhí)行效率；(2)在任務(wù)數(shù)超過雷達執(zhí)行能力時，可結(jié)合任務(wù)的優(yōu)先級、任務(wù)耗時等因素給出一個綜合的任務(wù)執(zhí)行方案。

4 基于任務(wù)效用最大化的多雷達協(xié)同在線任務(wù)分配算法

4.1 基于任務(wù)效用最大化的任務(wù)分配優(yōu)化問題

將式(8)和式(9)代入式(7)中，再將結(jié)果代回優(yōu)化問題式(6)，同時考慮雷達的能力約束，最終可將多雷達任務(wù)分配建模成如下數(shù)學優(yōu)化問題：

該問題為一個關(guān)于整型變量U|Q和Q的離散優(yōu)化問題?？梢园l(fā)現(xiàn)，不同的任務(wù)排列方式 Q會影響到任務(wù)分配變量U|Q的取值以及任務(wù)分配后各任務(wù)在對應(yīng)雷達節(jié)點的執(zhí)行順序，不存在多項式時間復雜度的算法實現(xiàn)該問題的求解，因此，該優(yōu)化問題是一個NP難問題[28]。

4.2 窮舉搜索

針對優(yōu)化問題式(11)，最優(yōu)的解法是對所有的任務(wù)分配和任務(wù)排序解空間進行窮舉搜索?？蓪γ總€任務(wù)分配到每個雷達節(jié)點的情況進行窮舉，再在任務(wù)分配特定的組合下，對各雷達節(jié)點內(nèi)任務(wù)的排序進行并行排列計算，其偽代碼如算法1所示。

下面對窮舉搜索算法的時間復雜度進行分析，窮舉搜索算法首先包括外部的Q層串行迭代，需要執(zhí)行O(NQ)次循環(huán)；此外，在上述串行迭代內(nèi)，需要對每個雷達分得的任務(wù)完成任務(wù)排序。任務(wù)排序計算可并行執(zhí)行，此時對任一雷達最多需要執(zhí)行=Q!次排列，因此窮舉搜索算法最終的時間復雜度為O(NQQ!)。

可以發(fā)現(xiàn)，雖然窮舉搜索算法遍歷了任務(wù)分配所有可能的解，能夠找到最優(yōu)的任務(wù)分配結(jié)果，但由于任務(wù)規(guī)劃問題的NP難特性，該最優(yōu)算法的計算量巨大，時間復雜度隨任務(wù)數(shù)量的增加呈指數(shù)乘以階乘的水平增加。當任務(wù)數(shù)較多時，窮舉搜索算法將導致計算的維度災(zāi)難。

算法1 窮舉搜索算法Alg.1 Exhaustive search algorithm

算法2 離散化任務(wù)分配變量Alg.2 Discretization of task scheduling variables

算法3 啟發(fā)式貪婪算法Alg.3 Heuristic greedy search algorithm

4.3 基于凸松弛的兩步解耦算法(CRTSD)

為了降低式(11)的求解復雜度，以滿足在線任務(wù)分配的實時性要求，本文將提出一種次優(yōu)的CRTSD求解算法，以實現(xiàn)在多項式時間復雜度內(nèi)完成對問題的求解。

CRTSD將任務(wù)排列變量 Q與任務(wù)分配變量U|Q解耦，以實現(xiàn)問題降維，包含兩個主要步驟。第1步是在特定的任務(wù)排列下，完成任務(wù)分配變量的確定；第2步則是在確定任務(wù)分配變量后，再次對各雷達節(jié)點分得的任務(wù)進行排序，以實現(xiàn)任務(wù)效用最大化。

4.3.1 基于任務(wù)重要性優(yōu)先原則的任務(wù)排列

可以發(fā)現(xiàn)，由于雷達節(jié)點是在特定的任務(wù)排列Q 下，按照任務(wù)分配變量U|Q每一行從左至右依次執(zhí)行分配任務(wù)的。因此，任務(wù)排列變量 Q會決定任務(wù)執(zhí)行的先后順序，并且與任務(wù)分配變量U|Q呈強耦合關(guān)系?？紤]到重要性程度高的任務(wù)通常被期望盡快執(zhí)行，因此，不妨先以任務(wù)重要性ρq對任務(wù)進行初始排列，從而得到任務(wù)排列變量 Q，并將其從優(yōu)化問題中解耦。因此，任務(wù)排列變量 Q可表示為

式(13)依舊為一個離散非凸問題。為了進一步簡化其求解，可以對其進行連續(xù)化的放縮，即將0-1變量放縮為一個0到1之間的連續(xù)變量。此外，在根據(jù)任務(wù)分配給各個雷達之后，任務(wù)執(zhí)行效率eq(U|Q)可通過對雷達分得的任務(wù)進行排序而計算得到。此時，可將問題式(13)目標函數(shù)中的任務(wù)執(zhí)行效率eq(U|Q)項省略，以降低問題求解的復雜度。因此，省略任務(wù)執(zhí)行效率eq(U|Q)項后，優(yōu)化問題式(13)可變?yōu)槿缦滦问剑?/p>

上述優(yōu)化問題的等價形式可表示為

在經(jīng)過多次放縮之后，式(15)為一個4次的凸優(yōu)化問題，可通過常用的凸優(yōu)化算法進行直接求解，本文采用CVX tools對其進行求解[29]。在求解優(yōu)化問題式(15)后可確定連續(xù)的任務(wù)分配變量U|Q。接下來需要對其進行離散化，以得到最終的任務(wù)分配結(jié)果。實現(xiàn)離散化的算法如算法2所示。

4.3.2 任務(wù)執(zhí)行順序重排序

在確定任務(wù)分配變量Uopt后，可根據(jù)任務(wù)分配結(jié)果對任務(wù)執(zhí)行順序進行重排列，以進一步提升任務(wù)效能。將Uopt代入任務(wù)效用函數(shù)，可得到如下任務(wù)q的加權(quán)效用函數(shù)表達式：

為了明確每個任務(wù)在對應(yīng)雷達中的執(zhí)行順序，這里定義如下函數(shù)：

最后{Qopt,Uopt}即為得到的任務(wù)分配問題的解，圖3為CRTSD算法的流程圖。

可以發(fā)現(xiàn)，由于CRTSD算法中存在凸松弛以及在任務(wù)排序時使用了啟發(fā)式求解等手段，其問題的解并非最優(yōu)。但本文會在后續(xù)仿真實驗中通過與最優(yōu)的窮舉搜索算法對比來證明，CRTSD算法在大多數(shù)場景下都能找到令人滿意的次優(yōu)解。

下面對CRTSD算法的時間復雜度進行分析，CRTSD算法主要包括以下4個步驟：(1)任務(wù)重要性排序；(2)凸松弛；(3)離散化任務(wù)分配變量；(4)任務(wù)執(zhí)行順序重排序4個串行執(zhí)行的模塊。其中：步驟(1)和步驟(4)若采用最簡單的冒泡排序算法，時間復雜度為O(NQ2)；步驟(2)若采用等步長的梯度下降算法實現(xiàn)凸問題求解，則其時間復雜度為O(1/ε)，其中ε為梯度下降算法的停止精度；步驟(3)需要執(zhí)行O(NQ)次迭代。由于這4個步驟是串行執(zhí)行的，CRTSD算法的總體復雜度為

可以發(fā)現(xiàn)，CRTSD算法可在多項式時間內(nèi)完成問題求解，相比于窮舉搜索算法的階乘級復雜度，CRTSD算法時間復雜度可大為下降。

4.4 啟發(fā)式貪婪搜索算法

除CRTSD算法外，本文還提供了一種次優(yōu)的啟發(fā)式算法用于實現(xiàn)任務(wù)的在線分配。該算法相較于CRTSD算法而言，其優(yōu)化性能精度稍差，但在大規(guī)模問題中可具備更低的算法復雜度。主要基于貪婪的規(guī)則，包括以下兩個步驟：(1)在tn,max的約束下，每個任務(wù)分給距離其最近的雷達節(jié)點執(zhí)行，以實現(xiàn)任務(wù)分配；(2)完成任務(wù)分配后，每部雷達節(jié)點內(nèi)的任務(wù)按照其重要性由高到低進行排序和執(zhí)行。啟發(fā)式貪婪算法的執(zhí)行流程如算法3所示。

可以發(fā)現(xiàn)，若串行執(zhí)行，啟發(fā)式貪婪算法的復雜度仍舊在O(n3)。但相較于CRTSD算法而言，由于啟發(fā)式貪婪算法各雷達節(jié)點任務(wù)排序部分相互獨立，若采用并行執(zhí)行的手段(如MATLAB中的parfor命令)，則可將排序的復雜度降低，整體復雜度最低可降至O(n2)。因此，相比于窮舉和CRTSD算法，啟發(fā)式貪婪算法在大規(guī)模任務(wù)分配問題中可望擁有更低的時間復雜度。

5 仿真實驗

本節(jié)將給出幾組仿真場景，用以展示本文提出的啟發(fā)式貪婪搜索算法、CRTSD算法的有效性?？紤]如圖4所示的探測場景：N=4部雷達完成對一個10 km×10 km方形區(qū)域的協(xié)同探測，為便于后續(xù)任務(wù)分配結(jié)果的對比，考慮這4部雷達分布在方形區(qū)域的4個角，坐標 (xn,yn)依次為(1 km,1 km),(9 km,1 km),(1 km,9 km)和(9 km,9 km)，每部雷達的最大可用時間資源tn,max=10 s；Q個探測任務(wù)出現(xiàn)在該方形區(qū)域內(nèi)，其位置(xq,yq)在10 km×10 km的方形區(qū)域均勻分布。類似地，每項任務(wù)重要性在λ到1 之間呈均勻分布ρq～U(λ,1)，任務(wù)耗時在0到1 s之間呈均勻分布tq～U(0,1)。

圖4 多雷達-多任務(wù)探測場景Fig.4 Task scenario of multiradar with multitask

5.1 不同算法性能比較

第1個場景如圖4所示，為了便于展示任務(wù)分配的結(jié)果，考慮較少的任務(wù)數(shù)量，區(qū)域內(nèi)存在Q=8個待分配任務(wù)，并將任務(wù)1到任務(wù)8根據(jù)其任務(wù)重要性由高到低進行排序，即對?q＞1,ρq-1＞ρq，設(shè)置任務(wù)重要性分布相關(guān)參數(shù)λ=0.9。

圖5和圖6分別展示了窮舉搜索、提出的CRTSD算法和啟發(fā)式貪婪算法下任務(wù)分配以及任務(wù)排序的結(jié)果。為便于觀察，圖5中的兩條點線將整個監(jiān)視區(qū)域劃分成了4塊，劃分后的每塊區(qū)域分別對應(yīng)距離這4部雷達最近的區(qū)域，雷達與任務(wù)存在連線表示該任務(wù)分配給該雷達節(jié)點執(zhí)行。圖6的每個階梯表示單個任務(wù)執(zhí)行的耗時。

圖5 3種算法下的多雷達-多任務(wù)分配結(jié)果Fig.5 Multiradar-multitask scheduling results of the three algorithms

圖6 3種算法下的各雷達分得的任務(wù)執(zhí)行順序排序結(jié)果Fig.6 The task execution order of each radar under the three algorithms

從圖5可以發(fā)現(xiàn)，啟發(fā)式貪婪算法和CRTSD算法中，在時間資源tn,max足夠的情況下，都將任務(wù)分配給距離最近的雷達節(jié)點?？紤]到雷達接收SNR主要受距離因素的影響，這是一種直觀且合理的方案。相比之下，雖然最優(yōu)的窮舉搜索算法任務(wù)分配主要還是受距離因素的影響，但可以發(fā)現(xiàn)，在另外兩種次優(yōu)算法中分配給雷達3的任務(wù)3被分配給了距離其次近的雷達1。結(jié)合圖6可以發(fā)現(xiàn)，這是由于次優(yōu)算法中分給雷達3的任務(wù)3和任務(wù)8都需要消耗較大的時間資源，導致雷達3的任務(wù)響應(yīng)效率較低。此時，窮舉搜索將任務(wù)3分配給任務(wù)較少的雷達1，可以提升整體的任務(wù)效能。由此可知，最優(yōu)的任務(wù)分配應(yīng)當充分考慮任務(wù)探測性能和整體任務(wù)執(zhí)行效率之間的權(quán)衡。

通過對比圖6(b)和圖6(c)可發(fā)現(xiàn)啟發(fā)式貪婪算法只是按照任務(wù)的重要性由高到低對其進行執(zhí)行順序的安排。而從CRTSD算法對雷達2的任務(wù)安排可知，CRTSD算法會將執(zhí)行耗時短的任務(wù)(任務(wù)7)優(yōu)先執(zhí)行，相比于啟發(fā)式貪婪算法的安排，CRTSD算法在任務(wù)2執(zhí)行效率稍微損失前提下，可顯著降低任務(wù)6、任務(wù)7的執(zhí)行等待時間，從而有望提升整體的任務(wù)執(zhí)行效能。

圖7和圖8分別展示了不同任務(wù)數(shù)量Q下，3種算法得到的任務(wù)效用函數(shù)值和運行時間對比。其中，運行時間是在MATLAB 2022a軟件平臺、i7-11700K處理器、32GB內(nèi)存硬件平臺下得到的。由于窮舉搜索算法涉及枚舉Q個任務(wù)的全排列，MATLAB仿真軟件僅支持生成=10!=3628800種排列情況，因此窮舉搜索算法只給出了Q從1到10的情況?？梢园l(fā)現(xiàn)，CRTSD算法可獲得顯著高于啟發(fā)式貪婪算法的任務(wù)效能，且在任務(wù)數(shù)量較少時與啟發(fā)式貪婪算法擁有近似的計算時間。而在任務(wù)數(shù)量較大時，啟發(fā)式貪婪算法擁有最快的執(zhí)行時間。此外，雖然窮舉搜索算法能夠獲得最好的任務(wù)效用值，但其計算時間是呈指數(shù)級增長的，在Q=10的情況下為302 s，約為CRTSD算法的600倍。同時可以預(yù)見，隨目標數(shù)的增長，窮舉搜索算法的計算時間將進一步惡化。

圖7 不同任務(wù)數(shù)量Q下3種算法得到的任務(wù)效用值Fig.7 Task utility values of the three algorithms with different number of tasks Q

圖8 不同任務(wù)數(shù)量Q下3種算法運行時間Fig.8 Runtime of the three algorithms with different number of tasks Q

5.2 復雜場景下提出算法的適應(yīng)性

本節(jié)將給出更為復雜的任務(wù)分配場景，以體現(xiàn)本文提出算法在不同場景下的適應(yīng)性。由于啟發(fā)式貪婪搜索算法的任務(wù)分配結(jié)果與CRTSD算法類似，本文接下來主要展示CRTSD算法的任務(wù)分配結(jié)果。本節(jié)仿真實驗中，考慮存在Q=40個任務(wù)待分配，其余參數(shù)與5.1節(jié)保持一致。主要考慮不同雷達探測構(gòu)型以及不同任務(wù)重要性情況下任務(wù)分配結(jié)果的合理性及其自適應(yīng)程度。

圖9給出了N=4部雷達線性探測構(gòu)型和不規(guī)則探測構(gòu)型下對Q=40個探測任務(wù)的分配結(jié)果。其中，情況1下每部雷達的最大可用時間資源均為tn,max=10 s，情況2下雷達3的最大可用時間資源減少到t3,max=1 s?？梢园l(fā)現(xiàn)，在時間資源足夠情況下(情況1)，兩種構(gòu)型都傾向于將任務(wù)分配給距離其最近的節(jié)點，其中雷達3在兩種構(gòu)型下都被分配了最多的任務(wù)。當減少雷達3的可用時間資源至t3,max=1 s后(情況2)，原本雷達3需要執(zhí)行的任務(wù)同樣按照距離遠近被依次分配給了其余3個節(jié)點，這展示了本文提出的CRTSD算法在雷達節(jié)點變化情況下的適應(yīng)性。

圖9 不同探測構(gòu)型下CRTSD算法任務(wù)分配結(jié)果Fig.9 Task scheduling results of CRTSD algorithm with different radar configurations

圖10給出了在不同任務(wù)重要性參數(shù)分布下，40個任務(wù)的優(yōu)先級ρq(q=1,2,...,40)以及CRTSD算法所得到的對應(yīng)的任務(wù)效用值分布?？梢园l(fā)現(xiàn)，不同任務(wù)間的優(yōu)先級差距越大，優(yōu)先級越高的任務(wù)越傾向于獲得更高的效用值。由此可見，CRTSD算法針對優(yōu)先級的變化也能夠給出合理的分配結(jié)果。同時，在實際應(yīng)用場景中可通過增加某項重要任務(wù)的ρq值來保證其執(zhí)行的性能和響應(yīng)效率。

圖10 不同任務(wù)優(yōu)先級設(shè)置下CRTSD算法得到的任務(wù)效用值Fig.10 Task utility values of CRTSD algorithm with different task priorities

6 結(jié)語

本文針對多雷達協(xié)同探測場景下的多任務(wù)在線分配需求，提出了一種基于任務(wù)效用最大化的在線任務(wù)分配算法。該算法將多任務(wù)的執(zhí)行效能建模成與任務(wù)-雷達節(jié)點分配結(jié)果相關(guān)的函數(shù)，通過最大化多任務(wù)的全局效能，把任務(wù)分配問題建模成一個離散整數(shù)規(guī)劃問題；為求解得到的該離散高維優(yōu)化問題，本文提出了啟發(fā)式貪婪搜索和CRTSD算法，并在多項式時間內(nèi)找到了問題的解。CRTSD算法具備更高的優(yōu)化求解精度，而啟發(fā)式貪婪算法具備相對較快的計算速度，使用者可根據(jù)所用平臺的計算能力、實時性要求、任務(wù)分配規(guī)模等因素，綜合權(quán)衡選擇提出的優(yōu)化算法。最后，通過仿真實驗證明了提出的任務(wù)分配算法可動態(tài)適應(yīng)探測任務(wù)性能、任務(wù)響應(yīng)效率、任務(wù)重要性等參數(shù)變化，自適應(yīng)地得到全局任務(wù)效能最大化的多任務(wù)多雷達分配方案。

此外，本文主要以探測性能和任務(wù)執(zhí)行效率兩個要素為例定義了多任務(wù)執(zhí)行的效用函數(shù)。本文提出的任務(wù)分配框架還可根據(jù)特定的任務(wù)需求，進行多元化的拓展設(shè)計，可應(yīng)用到更為廣泛的多雷達多任務(wù)在線分配問題中。