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

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

②(火箭軍工程大學(xué)導(dǎo)彈工程學(xué)院 西安 710025)

1 引言

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

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

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

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

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

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

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

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

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

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

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

2.1 探測任務(wù)屬性

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

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

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

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

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

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

圖2給出了Q=8項(xiàng)具有不同優(yōu)先級(jí)的任務(wù)分配給N=2部雷達(dá)的任務(wù)分配示意圖，其中雷達(dá)1、雷達(dá)2分別分得了5項(xiàng)和3項(xiàng)任務(wù)，且在其各自的任務(wù)執(zhí)行時(shí)間軸上把任務(wù)進(jìn)行了執(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í)行方案所帶來的探測效能及資源使用代價(jià)通常不同。因此，本文要解答的問題就是如何將多個(gè)探測任務(wù)分配給各個(gè)雷達(dá)，以及分配后的任務(wù)如何排序，以實(shí)現(xiàn)多任務(wù)全局探測效能的最優(yōu)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2 窮舉搜索

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

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

可以發(fā)現(xiàn)，雖然窮舉搜索算法遍歷了任務(wù)分配所有可能的解，能夠找到最優(yōu)的任務(wù)分配結(jié)果，但由于任務(wù)規(guī)劃問題的NP難特性，該最優(yōu)算法的計(jì)算量巨大，時(shí)間復(fù)雜度隨任務(wù)數(shù)量的增加呈指數(shù)乘以階乘的水平增加。當(dāng)任務(wù)數(shù)較多時(shí)，窮舉搜索算法將導(dǎo)致計(jì)算的維度災(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)的求解復(fù)雜度，以滿足在線任務(wù)分配的實(shí)時(shí)性要求，本文將提出一種次優(yōu)的CRTSD求解算法，以實(shí)現(xiàn)在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)完成對(duì)問題的求解。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 仿真實(shí)驗(yàn)

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

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

5.1 不同算法性能比較

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

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

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

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

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

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

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

圖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種算法運(yùn)行時(shí)間Fig.8 Runtime of the three algorithms with different number of tasks Q

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

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

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

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

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

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

6 結(jié)語

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

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