綜合優先級下反導預警相控陣雷達任務調度算法

楊善超， 田康生， 李宏權， 周廣濤， 梁復臺

(1.空軍預警學院 預警情報系, 湖北 武漢 430019; 2.31101部隊, 江蘇 南京 210016)

0 引言

相控陣雷達可以實現波束自適應捷變，擁有豐富的工作波形和強大的資源配置，相比機械掃瞄雷達優勢巨大，是執行反導預警任務的主要裝備[1-2]。為提升相控陣雷達時間資源利用效率，發揮相控陣雷達性能優勢，更好執行反導預警任務，必須要進行時間資源分配，也就是任務調度[3-4]。

相控陣雷達任務調度器主要包含兩個模塊：任務優先級規劃和調度策略選取。簡單的優先級規劃，是單因素確定任務優先級，包括高任務模式優先級最優先(HPF)算法[5]和截止期最早最優先(EDF)算法[3-4,6]。僅利用一種參數確定優先級，分析不夠全面，進而影響優先級的動態自適應性。文獻[7-10]借鑒優先級表思想[11]，結合工作方式優先級和截止期進行綜合優先級規劃，提出工作方式優先級加截止期(HPEDF)算法及其兩種變形算法：修正EDF(MEDF)算法和修正HPF(MHPF)算法，并仿真驗證了這3種綜合優先級算法的性能優勢。然而上述算法在規劃優先級過程中沒有充分利用目標先驗信息，且存在人為劃定工作方式優先級而導致主觀性過強的問題。針對此問題，文獻[12-14]建立關于目標屬性的威脅度模型，通過目標威脅度和任務截止期共同確定任務優先級。雷達調度策略主要包含模板類策略和自適應策略兩類，后者更能發揮相控陣雷達性能優勢。文獻[15-17]利用時間窗方法進行動態任務調度，使雷達任務請求的實際執行時刻可以在其期望時間前后移動，極大提高了調度成功率和時間利用率。文獻[14,18-21]采用了任務交錯算法，使任務等待期可以發射或接收其他任務駐留的波束，進一步提高了時間利用率。文獻[22,25]提出了基于代價或收益的調度算法，構建任務調度優化模型，并利用二次規劃、啟發式算法等進行求解。此外，文獻[26-27]提出了動態駐留時間調度算法，將任務駐留時間設定為模糊集，增強了任務調度的靈活性?？偟膩砜?，上述研究不適用于多彈道導彈目標跟蹤任務的調度，主要由于：1)任務優先級規劃大多針對空中目標，不符合彈道導彈目標特性；2)彈道導彈跟蹤任務對于及時性要求很高，而上述調度策略沒有充分考慮調度及時性。此外還存在將任務價值作為一個固定參數，沒有考慮其隨執行時刻動態變化的問題。

因此，本文提出綜合優先級下基于價值優化的反導預警相控陣雷達調度算法。該算法中優先級規劃符合彈道導彈目標特性，且調度策略使任務請求貼近期望時刻被執行，更滿足調度及時性原則。

1 彈道導彈目標威脅度模型

彈道導彈飛行速度快、機動性強、破壞殺傷性大，對防御方存在巨大威脅；另一方面，其飛行彈道和目的點是可預測的。因此分析彈道導彈目標威脅度過程中，不僅要考察導彈自身屬性因素，還要考察導彈和目的地之間的相互關系，以及目的地的重要程度，影響因素主要考慮以下5方面：目標速度、目標飛行階段、目標距目的地距離、目的地重要程度、彈頭種類?？紤]到各影響因素對目標威脅度的非線性影響，分別對其構建如下威脅度函數：

1) 目標速度威脅度：

(1)

式中：v為目標速度；vc為臨界速度；a為控制速度威脅函數的常系數，一般取[0.01,0.10]，a越大，曲線上升拐點處的v越大，且之后曲線上升越快。該函數表明隨著目標速度變大，威脅度不斷增大，當速度大于臨界值時，威脅度一直處于最大狀態。

2) 目標飛行階段威脅度。彈道導彈飛行過程可以分為3部分：主動段、自由飛行段、再入段。處于主動段時，目標速度相對較慢，防御方反導系統應對時間相對較長，威脅度最小。自由飛行段在飛行過程中占比最大，此階段防御方仍有一定應對時間，但是目標逐漸飛臨目的地，威脅度增大。處于再入段時，目標速度急劇增大，已經非常迫近攻擊目標，留給防御方的反應時間很短，威脅度最大。因此建立如下飛行階段威脅度函數：

(2)

式中：下標s表示目標所處的飛行階段；Wsr、Wsf、Wsp分別為3個目標飛行階段對應的威脅度設定值。

3) 目標距目的地距離威脅度。目標離目的地越近，距其造成殺傷的時間越短，威脅度越大。例如同樣處于主動段的2個目標，一個自3 000 km之外發射，一個自1 000 km之外發射，攻擊同一個目的地，顯然后者威脅度更大。建立距離威脅度函數為

Wr=(1-b)exp(-cr)+b,

(3)

式中：r為目標離目的地距離(km)；b為最小距離威脅度；c為控制目標距離威脅度函數的常系數，c越大，曲線拐點處的目標距離越小，曲線越接近呈現“L”形分布。

4) 目的地重要程度威脅度。彈道導彈目標的攻擊目的地可預測，目的地屬性是決定目標威脅度的重要因素。根據作戰層次分級，將目的地重要程度分為戰略、戰役、戰術3類，對應建立威脅度函數為

(4)

式中：下標d表示目的地重要程度，具體分級由專家確定；Wds、Wdc、Wdt分別為3個不同目的地重要程度對應的威脅度設定值。

5) 彈頭種類威脅度。彈頭是彈道導彈的戰斗部，部分導彈具備載核能力，將彈頭分成核彈頭、常規彈頭兩類，構建如下威脅度函數：

(5)

式中：下標h表示目標攜帶彈頭種類；Whn、Whc分別為2個彈頭種類對應的威脅度設定值。

基于以上各影響因素的威脅度函數，構建彈道導彈目標威脅度模型：

W=δ1Wv+δ2Ws+δ3Wr+δ4Wd+δ5Wh，

(6)

2 任務綜合優先級規劃

任務調度一般以調度間隔S為周期，在調度間隔[t0,t0+S]內共有N個任務駐留請求，第i個任務請求可以表示為

Ti={pi,tai,tdi,tei,tdwi,Δti,Ii},

(7)

式中：pi表示任務工作方式；tai為請求到達時刻，tdi為截止期，因此任務時間窗為[tai,tdi]；tei為期望執行時刻；tdwi為駐留時間；Δti為采樣間隔；Ii為目標信息集合，Ii可進一步描述為

Ii={v,s,r,d,h,W}.

(8)

(8)式中變量均滿足(6)式，需要注意的是：當pi為搜索任務時，Ti中不包含目標信息集合。

從任務調度的重要性和緊急性原則[10]出發，利用優先級表思想[11]，結合彈道導彈目標威脅度和任務截止期進行綜合優先級規劃。將任務集合中所有任務按照目標威脅度由大到小排列，得到威脅度序列{W1,W2,…,WN}，其中搜索任務在序列中排在所有跟蹤任務之后，搜索任務之間按照請求到達時間tai由前到后排列。再將所有任務按照截止期由小到大排列，得到截止期序列{d1,d2,…,dN}。將任務Ti在兩個序列中的位置序號分別記為m、n，加權綜合的優先級計算公式[12]為

Pi=[α·(m-1-β)+2·n-2]·(m+β)+m,

(9)

式中：α表示側重目標威脅度的加權系數；β=?(m-2)/α」.Pi越小，對應任務的優先級越高。α取值一般在[1,4]，值越大，綜合優先級越傾向于目標威脅度，當目標威脅度大小一致時，截止期越小的任務綜合優先級越高。圖1為α=1、α=2兩種情形下的優先級表設計。

圖1 優先級表設計Fig.1 Design of priority table

通過該動態優先級表設計，不用對目標威脅度和截止期進行去量綱處理，每個任務對應唯一的綜合優先級，且增強了優先級表的動態自適應特性。

3 基于價值優化的調度策略

3.1 任務價值模型

實際上，任務執行時刻變化時，會導致目標跟蹤精度和搜索發現概率的不同，必然會對任務實現價值產生影響。因此，任務實現價值不應該是固定值，而是隨著執行時刻動態變化的。構建如下任務動態價值函數：

(10)

(11)

任務Ti的價值變化斜率包括兩部分，分別對應著相對期望時刻提前或滯后執行，本文將二者的價值變化斜率絕對值大小設為一致，建立價值變化斜率函數為

(12)

式中：ξ為控制價值變化斜率的常系數。當ξ∈(0,1]時，不同優先級任務之間的價值變化斜率差異呈現增大趨勢；當ξ>1時，價值變化斜率差異呈減小趨勢；特別地，當ξ→∞時，所有任務的價值變化斜率都趨向于0. 可以看出，優先級越高的任務，價值變化斜率絕對值越大，任務動態價值隨執行時刻變化下降越快。

3.2 價值優化調度模型

本文綜合優先級規劃過程體現了任務調度的重要性、緊急性原則。彈道導彈目標具有高機動性、高威脅性，對于任務調度及時性的要求非常高，要從及時性原則出發構建調度模型。(10)式反映出任務調度及時性越高，實現價值越大，因此構建價值優化調度模型為

(13)

(14)

式中：C1表示被調度任務執行時刻的前后關系以及總駐留時間約束；C2、C3分別表示被延遲、刪除任務的時間約束；ηi表示任務調度屬性，取值規則為

(15)

f(ηi)是關于任務調度屬性的函數，

(16)

綜上可以看出，優化調度等價于在滿足(14)式的約束下，使(13)式所表示的總實現價值最大，主要目的包括兩個：一是判斷任務調度屬性；二是對被調度任務選擇優化執行時刻。

3.3 調度模型求解算法

上述優化調度問題可以視為一個高維的線性規劃問題，運用傳統的單純形法或者遍歷算法求解此類問題，會產生較大的計算量。遺傳算法(GA)[28]是一種模仿生物遺傳機制的智能搜索算法，能夠有效減少求解調度模型的計算量。但是傳統的GA搜索效率不高且容易陷入局部最優，因此本文設計一種改進的GA(MGA)，算法中選擇操作采用精英保留和排名選擇相結合的策略，并設置自適應的交叉、變異算子，以增大種群多樣性、避免陷入局部最優、提高算法效率。

3.3.1 種群初始化及適應度計算

隨機產生規模為Z的初始種群，每個染色體表示一種任務調度方案，由N個代表雷達任務的基因組成?；虿捎脙晌欢M制編碼方案，“11”表示該基因對應的任務被執行，“10”或“01”表示任務被延遲，“00”表示任務被刪除。

將個體對應的總實現價值Vtot作為其適應度，調度模型的目標函數為適應度函數。

3.3.2 選擇算子

采用精英保留和排序選擇相結合的策略：將個體按照適應度由大到小排列，保留種群中適應度最大的個體不參與交叉、變異操作，而是用其替換子代中適應度最低的個體；此外，其他Z-1個個體根據適應度采用輪盤賭法確定父本。輪盤賭法選擇的公式為

(17)

式中：PRSk為個體k被選擇的概率。

3.3.3 交叉算子

從群體進化過程來看，隨著進化的推進，交叉概率呈現出減小趨勢，以避免在算法后期因交叉概率過大導致其穩定性下降，進而導致算法延緩收斂甚至不能收斂。而在群體內部，所有個體在操作上應具有同等地位，即交叉概率應相同，從而使算法在搜索空間各方向上的搜索能力達到平衡。本文設計了決定于進化代數的自適應交叉概率：

(18)

3.3.4 變異算子

在算法早期，種群具有較高的多樣性，此時變異概率應該較小，以提高算法的運行速度。而隨著進化的推進，群體不斷向適應度高的個體不斷趨近，導致種群多樣性下降，此時應增大變異概率，以增強其多樣性。同理，在同代種群中，不同個體的變異概率應該決定于其優劣性，應該加大優質個體變異概率，以使群體多樣化。因此，本文設計與遺傳進化代數和個體適應度相關的自適應變異概率：

(19)

4 仿真實驗

4.1 仿真實驗1：算法有效性和性能驗證

4.1.1 評價指標

通過以下指標來評判算法的性能優劣：

1) 調度成功率[8-9]。成功調度的任務與請求調度的任務數目之比為

SSR=Xsuc/Xtot,

(20)

式中：Xsuc為成功調度的任務總數；Xtot為請求調度的任務總數。

2) 時間偏移率[25]。成功調度任務的實際執行時刻相對于期望時刻的偏移程度，用以反映任務調度的及時性：

(21)

3) 實現價值率。常用的實現價值率指標[8-9,25]將各任務的優先級直接作為任務價值，用成功調度任務與所有請求任務的總價值相比得到指標值。這只能反映出任務調度成功率以及滿足重要性原則的情況，而不能體現任務及時性對實現價值率的動態影響。因此根據本文動態價值函數，對實現價值率進行改進：

(22)

4.1.2 參數設置

調度間隔50 ms，仿真時長25 s，以目標總數來代表不同的雷達負載情況，目標數量設為10,20,…,80批。設置3個目的地A、B、C，分別對應于戰略、戰役、戰術層級，各目標隨機設置攻擊目的地。不同工作方式任務的參數設置如表1所示，精密跟蹤(下簡稱為精跟)、普通跟蹤(下簡稱為普跟)、監視目標的數目之比為5∶3∶2，且由場景發生器對應隨機產生各類目標參數，使目標威脅度滿足：精跟>普跟>監視。每增加10批目標，進行100次蒙特卡洛仿真，取實驗平均值。對于每一個跟蹤采樣，探測概率設置為1. 搜索任務為常駐任務，依編排好的波位進行，在仿真開始后按搜索間隔產生，該搜索間隔由彈道導彈穿越搜索屏的時間和搜索累積探測概率決定。

表1 任務參數設置Tab.1 Parameters setting of tasks

4.1.3 仿真結果及分析

圖2為3種算法的調度成功率對比。3種算法的調度成功率在目標數量超過20批時都處于下降狀態，其中MEDF算法的調度成功率下降最快，HPEDF算法調度成功率下降最慢，這是由于HPEDF算法能夠在盡量減少刪除搜索任務的情況下使更多跟蹤任務被調度，因而調度成功率在3種算法中最高。在目標數目為80批時，本文算法相對于MEDF算法調度成功率提升了13%，HPEDF算法相對于MEDF算法提升了20%.

圖2 調度成功率對比Fig.2 Comparison of scheduling success ratios

圖3 時間偏移率對比Fig.3 Comparison of time shift ratios

圖3為3種算法的時間偏移率對比。MEDF算法、HPEDF算法的時間偏移率上升較快，且MEDF算法的時間偏移率最高，而本文算法時間偏移率最低、上升速率最慢。這是由于MEDF算法和HPEDF算法都沒有考慮到及時性因素，且MEDF算法優先對截止期臨近的任務進行調度，導致其時間偏移率最高；而本文算法注重任務及時性的滿足，在盡可能調度多的跟蹤任務基礎上，使任務貼近期望時刻被執行。當目標數目80批時，本文算法的時間偏移率相對于MEDF算法、HPEDF算法分別減小了48%和46%.

圖4所示為3種算法的實現價值率對比。結合圖2～圖4可以看出，當調度成功率為1.0的時候，實現價值率并不一定為1.0，這是由于本文中的任務實現價值率指標不僅與成功調度的任務數目有關，還受到調度及時性的動態影響。MEDF算法的實現價值率最低，因為該算法調度成功率低，且調度過程中不僅刪除搜索任務還會刪除價值更高的跟蹤任務。本文算法在調度成功率略低于HPEDF算法的基礎上，實現價值率卻比HPEDF算法更高，當目標數目80批的時候，指標提升了12%. 這是由于本文算法更能滿足任務及時性要求，尤其是對于高價值任務，其時間偏移率更低。該結果說明任務調度及時性的變化對于實現價值率有重要影響。

圖4 實現價值率對比Fig.4 Comparison of hit value ratios

圖5 不同工作方式的實現價值率對比Fig.5 Comparison of hit value ratios of different task types

圖5所示為在本文算法中，不同工作方式跟蹤任務的實現價值率對比。從圖5可以看出，在精跟目標和普跟、監視目標數目一致的情況下，本文算法對于精跟任務的實現價值率更高，在總目標80批時達到了78%，比普跟、監視任務高47%. 這是由于本文算法利用導彈目標威脅度和截止期構建綜合優先級，且威脅度占主要地位；精跟目標威脅度相對較大，優先級更高，進而最大價值更大，且執行時刻更加貼近期望時刻，產生了較好的實現價值率。這說明本文算法在保證總體調度性能的基礎上，注重對高優先級任務的調度效果。

以上仿真結果表明：本文算法相比MEDF算法、HPEDF算法，能夠較好滿足任務調度及時性；此外，本文算法實現價值率更高，且對于高優先級任務的調度效果更加明顯。

4.2 仿真實驗2：價值函數參數對算法性能的影響分析

實驗1中任務動態價值函數參數設置為θ=1、ξ=3.0，實驗2對不同價值函數參數對算法性能的影響進行驗證分析。

目標總數述設置為40批，精跟目標20批，普跟、監視目標20批。對表2所示的3種參數組合分別進行仿真，其他設置與實驗1一致。對每種參數組合進行100次蒙特卡洛實驗，取結果平均值。

表2 任務價值函數參數設置組合Tab.2 Parameters setting of task value function

圖6 組合1下任務調度偏移情況對比Fig.6 Comparison of task scheduling shifts under Combination 1

圖6～圖8是3種參數組合下，精跟任務以及普跟、監視任務的調度偏移情況對比，圖中縱軸的任務比例表示滿足橫軸對應條件的任務數目在總任務數目中的占比。

圖7 組合2下任務調度偏移情況對比Fig.7 Comparison of task scheduling shifts under Combination 2

圖8 組合3下任務調度偏移情況對比Fig.8 Comparison of task scheduling shifts under Combination 3

結合圖6和圖7可以看出，當ξ=3.0而θ不同時，θ越大，精跟任務實際執行時刻的偏移程度越小，且在期望時刻被執行的的任務比例越高，當θ=1時為49%，當θ=2時為57%. 此外θ越大，精跟任務的調度成功率越高，當θ=1時為90%，當θ=2時為99%. 而普跟、監視任務的時間偏移和調度成功率變化趨勢正好相反。這是由于ξ相同時θ越大，不同優先級任務間的最大價值差異變大，調度模型以總實現價值最大為目標函數，使得高優先級的精跟任務的調度成功率增大，時間偏移率降低。

結合圖6和圖8可以看出，當θ=1而ξ不同時，ξ越小，精跟任務的時間偏移程度越小，且當ξ=3.0時，在期望時刻被執行的的精跟任務比例為49%，當ξ=0.5時為64%. 而低優先級任務(普跟、監視)的調度偏移程度變化呈相反趨勢。這是由于θ相同時ξ越小，不同優先級任務之間的價值變化斜率差異越大，隨著執行時刻的偏移，高優先級任務實現價值下降越快。因此當ξ=0.5時，為了使總實現價值最大，要減小高優先級任務也就是精跟任務的時間偏移率。

該仿真結果說明，任務動態價值函數中的參數θ、ξ對調度性能產生影響，θ越大、ξ越小，對高威脅度、高優先級任務的調度效果越好。

4.3 仿真實驗3：模型求解算法性能對比

將本文的MGA與文獻[29]提出的單純形法，以及傳統GA在求解調度模型時的運行時間進行對比，以對算法性能進行分析。其中，MGA參數設置與實驗1保持不變，傳統GA的參數設置如表3所示。

表3 GA參數設置Tab.3 Parameters setting of genetic algorithm

圖9 算法平均運行時間對比Fig.9 Comparison of average running times of algorithms

進行100次蒙特卡洛仿真，取實驗結果平均值，得到3種算法的平均運行時間對比如圖9所示。單純形法在求解模型時會產生最多的計算量，其運行時間最長。而MGA設置了自適應選擇算子、交叉算子、變異算子，增強了對全局最優解的搜索能力和收斂速度，因此其平均運行時間小于GA. 該仿真結果說明，本文提出的MGA具有較好的求解性能。

5 結論

資源的優化調度是發揮反導預警相控陣雷達效能的關鍵，本文提出一種綜合優先級下基于價值優化的任務調度算法，所作的主要貢獻和結論如下：

1) 根據彈道導彈目標特性，結合目的地重要程度以及二者之間的相互關系，構建彈道導彈目標威脅度模型。

2) 基于任務優先級確定任務最大價值，并提出任務動態價值函數，反映出任務價值隨實際執行時刻的變化規律。

3) 構建了價值優化調度模型，使任務執行時刻更貼近期望時刻，提高了任務調度及時性，更滿足彈道導彈跟蹤任務要求。

4) 改進了實現價值率指標，能更好反映出任務及時性對任務實現價值的影響。

5) 仿真結果表明，該算法具有有效性，能夠提升任務調度及時性和實現價值率。

6) 本文將任務提前或滯后執行的價值變化斜率大小設為一致，需要進一步研究：根據提前或滯后執行對任務價值的不同影響，構建差異化的價值變化斜率函數。