基于改進時間指針的啟發(fā)式脈沖交錯任務(wù)調(diào)度方法

明 樂，周 峰，顧競豪，丁日顯

(空軍工程大學研究生學院，陜西 西安 710051)

0 引言

相控陣雷達不僅具備靈活、快速的波束捷變能力，而且還具備波束自適應(yīng)能力，因此可以同時進行搜索、跟蹤等多個任務(wù)[1-4]。相控陣雷達及其技術(shù)的快速發(fā)展，受到國內(nèi)外學者的高度重視。文獻[5]提出將截止期最早最優(yōu)先(Earlist Deadline First，EDF)算法，用于相控陣雷達任務(wù)調(diào)度，從而保證了截止期更早的任務(wù)能夠被最先調(diào)度執(zhí)行。文獻[6—7]提出在任務(wù)調(diào)度過程中引入遺傳算法，利用遺傳算法的尋優(yōu)能力，來解決任務(wù)調(diào)度過程中存在的NP問題(Non-deterministic Polynomial Complete problem)。文獻[8—9]對整體任務(wù)進行二次規(guī)劃，從而獲取其最佳執(zhí)行時間。以上所提到的調(diào)度方法均是從任務(wù)本身出發(fā)來選取其執(zhí)行時刻，可能會使大量空余時間沒有被充分利用，浪費了一部分時間資源。針對這一問題，文獻[10—11]從時間角度出發(fā)來選擇相應(yīng)的任務(wù)，從一個調(diào)度間隔內(nèi)所有任務(wù)請求中，為該時間指針所指向的時刻選取最合適的任務(wù)，從而在一定程度上能夠提高雷達對時間資源的利用率。但是該方法只是拘泥于在時間指針所在調(diào)度間隔內(nèi)選擇當前時刻需要執(zhí)行的任務(wù)，當此調(diào)度間隔內(nèi)的任務(wù)數(shù)量較少時，也會存在大量的空余時間無法被充分利用，并且沒有充分利用雷達任務(wù)的等待期。文獻[12]通過脈沖交錯技術(shù)充分利用雷達任務(wù)的等待期時長，在時間指針的基礎(chǔ)上引入脈沖交錯，得到了基于時間指針的脈沖交錯調(diào)度方法。但是由于考慮了脈沖交錯過程中的幾種具體方式，調(diào)度過程較為復雜。本文針對前述問題，提出了基于改進時間指針的啟發(fā)式脈沖交錯任務(wù)調(diào)度方法。

1 駐留任務(wù)模型

一個雷達任務(wù)的完成需要經(jīng)過三個過程：波束駐留指令的產(chǎn)生、天線端的發(fā)射和接收以及處理器端的信號處理。這其中需要脈沖的發(fā)射與接收，因此一個駐留任務(wù)的參數(shù)除了包括其工作方式優(yōu)先級、期望執(zhí)行時刻、實際執(zhí)行時刻和時間窗，還應(yīng)該包括任務(wù)的駐留長度、脈沖重復周期、脈沖積累個數(shù)、脈沖寬度。建立相應(yīng)的雷達波束駐留任務(wù)模型如下：

T={Tr,Tn,tp,w,ld,rt,st,pr}

(1)

式(1)中，Tr指的是脈沖重復周期，Tn指的是脈沖積累個數(shù)，tp指的是脈沖寬度，w指的是時間窗長度，ld指的是任務(wù)的駐留長度，rt指的是任務(wù)的期望執(zhí)行時間，st指的是任務(wù)的實際執(zhí)行時間，pr指的是任務(wù)的工作方式優(yōu)先級。

雷達任務(wù)在被調(diào)度執(zhí)行過程中可以分為三個階段，即發(fā)射期、等待期和接收期，記ld={tx,tw,tr}，其中tx、tw和tr分別指的是雷達任務(wù)的發(fā)射期時長、等待期時長和接收期時長。如圖1所示，可以利用回波信號得到的目標距離R計算得到跟蹤任務(wù)的等待期長度tw，其中tx=tp，tw=2R/c。

圖1 雷達跟蹤駐留模型Fig.1 Radar tracking dwell model

雷達波束駐留調(diào)度在進行脈沖交錯過程中必須同時滿足相應(yīng)的時間資源約束條件和能量資源約束條件。時間約束條件需要滿足：不僅要保證雷達任務(wù)能夠在其截止期之前調(diào)度完成，而且任意兩個雷達任務(wù)之間的發(fā)射期和接收期是不允許互相占用的。因此這里通過引入標識變量PT來反映當前準備調(diào)度任務(wù)的發(fā)射期或者接收期與已經(jīng)調(diào)度完成任務(wù)的是否發(fā)生重疊，從而更好地判斷待調(diào)度的任務(wù)是否滿足相應(yīng)的時間約束條件，其定義如下：

PT={x1,x2,r1,r2,s}

(2)

式(2)中，x1、x2分別指的是雷達任務(wù)的任意一個發(fā)射脈沖起始時刻以及相應(yīng)的結(jié)束時刻；r1和r2是該雷達任務(wù)的接收脈沖起始時刻以及相應(yīng)的結(jié)束時刻；s指的是該發(fā)射或者接收脈沖的編號，故s∈{0,1,2,…,Tn-1}，如圖所示。發(fā)射脈沖過程中會消耗一定的能量，從而使得系統(tǒng)的溫度有所升高，一旦溫度達到了系統(tǒng)無法承受的程度時，系統(tǒng)就會損壞，因此需要對系統(tǒng)的瞬態(tài)能量進行限制來保證系統(tǒng)的正常運行。系統(tǒng)在t時刻的瞬態(tài)能量可以表示為：

(3)

式(3)中，p(x)指的是系統(tǒng)功率函數(shù)；τ指的是回退參數(shù)，反映的是系統(tǒng)本身的散熱性能。現(xiàn)將系統(tǒng)時間離散化處理，按照ΔtE的間隔劃分成多個離散時間點，此時式(3)的約束條件可轉(zhuǎn)變?yōu)槊恳粋€離散時間點所消耗的能量不超過能量閾值，將其記為能量狀態(tài)變量Ei(k)，其中k為離散時間點編號。設(shè)系統(tǒng)可以承受的最大瞬態(tài)能量為Emax，那么瞬態(tài)能量約束即可表示為：

Ei(k)≤Emax，k={1，2，…}

(4)

2 基于改進時間指針的啟發(fā)式脈沖交錯調(diào)度方法

2.1 改進時間指針原理

傳統(tǒng)的時間指針算法僅僅拘泥于在時間指針所在調(diào)度間隔內(nèi)進行相應(yīng)的任務(wù)選擇。傳統(tǒng)的調(diào)度方式有可能會產(chǎn)生兩種后果：一方面當調(diào)度間隔內(nèi)的任務(wù)請求比較少時，會有相當一部分的空余時間沒有被利用；另一方面當調(diào)度間隔內(nèi)的任務(wù)較多時，可能導致一部分任務(wù)被延遲執(zhí)行或者直接刪除。假設(shè)現(xiàn)在存在兩個調(diào)度間隔，并且有8個任務(wù)請求，滿足調(diào)度間隔1有3個任務(wù)請求以及調(diào)度間隔2有5個任務(wù)請求，任務(wù)示意圖如圖2所示?，F(xiàn)根據(jù)傳統(tǒng)時間指針的調(diào)度方式對任務(wù)進行調(diào)度，可以得出任務(wù)的調(diào)度結(jié)果如圖3(a)所示。從圖3(a)中也可以看出調(diào)度間隔1內(nèi)還剩下一部分空余時間未被充分利用，而在調(diào)度間隔2內(nèi)因為相應(yīng)的任務(wù)請求比較多，所以導致了任務(wù)8無法被調(diào)度。

改進的調(diào)度方法的基本思想是：雷達在某一時刻選擇調(diào)度任務(wù)時，不再局限于此調(diào)度間隔內(nèi)的任務(wù)請求，而是從整個調(diào)度時間軸出發(fā)進行考慮，從所有滿足此時刻執(zhí)行條件的任務(wù)中選取一個綜合優(yōu)先級最高的任務(wù)調(diào)度執(zhí)行?，F(xiàn)采用改進的調(diào)度方法對圖2中的任務(wù)進行調(diào)度，其結(jié)果如圖3(b)所示，即調(diào)度間隔1內(nèi)的空余時間得以充分利用，并且8個任務(wù)全部得到執(zhí)行。

圖2 任務(wù)示意圖Fig.2 Task diagram

圖3 調(diào)度結(jié)果示意圖Fig.3 Schematic diagram of scheduling results

2.2 啟發(fā)式脈沖交錯原理

雖然傳統(tǒng)的脈沖交錯技術(shù)能夠提高系統(tǒng)的時間利用率，但是其調(diào)度過程較為繁瑣。為了簡化整個調(diào)度過程，本文在時間指針的基礎(chǔ)上引入一種啟發(fā)式的脈沖交錯技術(shù)。雷達任務(wù)交錯的兩種方式如圖4所示。

圖4中的陰影矩形框和空白矩形框分別代表的是任務(wù)0和任務(wù)1；tp0和P0分別表示的是雷達任務(wù)0發(fā)射期結(jié)束的時刻點和相應(yīng)的功率消耗值。對圖4(a)和(b)進行相應(yīng)的分析得到，在兩種脈沖交錯方式下任務(wù)0和任務(wù)1必須分別滿足式(5)和式(6)時間關(guān)系：

(5)

tw0≥tx1+tw1+tr1

(6)

圖4 任務(wù)的兩種交錯方式Fig.4 Two interleaving ways of tasks

假設(shè)在一個調(diào)度間隔[tstart,tend]內(nèi)有N個任務(wù)請求，并且將其按照綜合優(yōu)先級方式進行排列，記為0,1,2,…,N-1。首先初始化剩余時間軸為整個調(diào)度間隔長度，并且令時間指針tp0=tstart。如果在tp0時刻，任務(wù)0可以被調(diào)度執(zhí)行，則對時間指針進行相應(yīng)的更新，即tp0=tp0+tx0。此時，任務(wù)0的發(fā)射期和接收期將剩余時間軸分割成兩個時間段，即[tp0,tp0+tx0]和[tp0+tw0+tr0,tend]。接下來需要分析任務(wù)1是否可以在此時刻調(diào)度執(zhí)行，假設(shè)任務(wù)1能夠在tp0時刻被調(diào)度，分析其發(fā)射期能否符合相應(yīng)的剩余時間資源約束條件：

(7)

若滿足剩余時間資源約束條件，則更新時間指針為tp0=tp0+tx1，剩余時間軸更新為[tp0,tp0+tw0-tx1]，[tp0+tw0-tx1+tr0,tend]。然后對任務(wù)1的接收期進行檢驗，是否滿足如下剩余時間資源約束：

(8)

(9)

若任務(wù)1的接收期滿足式(8)或式(9)時，則表明任務(wù)1符合相應(yīng)的時間約束條件。當任務(wù)1的發(fā)射期不能滿足式(7)時，對時間指針進行更新為tp0=tp0+tw0+tr0，然后繼續(xù)檢驗任務(wù)1的發(fā)射期，看是否能在tp0時刻調(diào)度執(zhí)行：

(10)

若能夠滿足式(10)，那么將時間指針和剩余時間軸分別更新為tp0=tp0+tx1， [tp0-tx1-tr0-tw0,tp0-tx1-tr0]，[tp0,tend]。然后對任務(wù)1的接收期進行相應(yīng)的檢驗，看是否滿足如下剩余時間資源約束條件：

(11)

如果任務(wù)1能夠符合時間資源約束，下一步需要對其能否符合能量資源約束進行相應(yīng)的分析，能量資源約束條件如下：

(12)

如果任務(wù)1不符合時間約束條件或者能量約束條件時，則通過預(yù)先設(shè)定的最小指針滑動步長Δtp來移動指針，并且更新相應(yīng)的參數(shù)得到：

(13)

然后按照上述對任務(wù)1的分析流程，依次對余下的其他任務(wù)進行可調(diào)度性分析。啟發(fā)式脈沖交錯算法采用上述時間指針和剩余時間軸的更新方式，因此不需要再考慮具體的脈沖交錯形式，在一定程度上避免了調(diào)度過程的繁瑣。

2.3 算法調(diào)度流程

假設(shè)某一個調(diào)度間隔(SI)的起始時刻為to，結(jié)束時刻為tend，tp為時間指針，Q={q1,q2,…,qN}表示的是tp時刻整個調(diào)度時間軸上所有任務(wù)請求形成的申請鏈表?；诟倪M時間指針的啟發(fā)式脈沖交錯算法的具體步驟如下：

第一步 初始化剩余時間軸為[tp,tend]，任務(wù)功率指示參數(shù)P0，并令i=0。

第二步 在Q中，選取截止期小于tp的任務(wù)，并將其送入刪除鏈表。

第五步 若i≥M，若是，轉(zhuǎn)第八步；若不是，轉(zhuǎn)第六步。

第六步 若tp≥tend，則轉(zhuǎn)第七步；否則，轉(zhuǎn)第二步。

第七步 此調(diào)度間隔結(jié)束，得到此調(diào)度間隔相應(yīng)的的執(zhí)行鏈表以及參數(shù)tp和P0，然后進行下一個調(diào)度間隔的工作。

第八步 雷達工作完畢。

3 仿真實驗

3.1 性能評估指標

為了驗證本文所提新算法的優(yōu)勢，利用以下評估指標進行算法間的對比：

1) 調(diào)度成功率(Schedule Sccess Ratio, SSR)：

(14)

式(14)中，Nsuc為成功調(diào)度任務(wù)總數(shù)，N為所有請求的任務(wù)總數(shù)。調(diào)度成功率用來描述調(diào)度任務(wù)的情況，調(diào)度成功率越高，性能越好。

2) 時間利用率(Time Utilization Ratio，TUR)：

(15)

式(15)中，Nsuc為成功調(diào)度任務(wù)總數(shù)，Δti指的是任務(wù)的駐留時間，T表示的是仿真時間長度。由此可見，時間利用率越高，說明調(diào)度方法的性能越好。

3.2 仿真結(jié)果及其分析

仿真參數(shù)：1) 調(diào)度間隔為50 ms，仿真時長為10 s；2) 綜合優(yōu)先級的設(shè)計采用HPEDF準則；3) 目標數(shù)量為10～100批，每增加10批目標重復進行100次實驗；4) 指針最小滑動步長Δtp=0.5，各類任務(wù)的具體參數(shù)設(shè)置如表1所示。

通過仿真得到本文算法與時間指針算法、傳統(tǒng)的時間指針脈沖交錯算法的調(diào)度成功率和時間利用率對比曲線圖如圖5和圖6所示。

表1 任務(wù)參數(shù)表Tab.1 Task parameters

圖5 調(diào)度成功率對比Fig.5 Comparison of dispatching success rate

圖6 時間利用率對比Fig.6 Comparison of time utilization

從圖5中能夠得出在目標數(shù)量超過30批時，時間指針算法和傳統(tǒng)的時間指針脈沖交錯算法的調(diào)度成功率已經(jīng)開始下降；當目標數(shù)量超過40批時，本文提出的改進的時間指針啟發(fā)式脈沖交錯算法的調(diào)度成功率才開始下降，提升了系統(tǒng)跟蹤目標的最大數(shù)量。而且本文算法下降得更加緩慢，因為其不僅使用了脈沖交錯技術(shù)，充分利用了雷達任務(wù)的等待期，還從整個時間軸出發(fā)選擇請求任務(wù)，在一定程度上可以減少任務(wù)的錯失率，能夠進一步提升其調(diào)度成功率。

從圖6中能夠得出在目標數(shù)量比較少時，三種算法在時間利用率方面差別不大，這是由于此時雷達系統(tǒng)時間資源充足；隨著目標數(shù)量的增多，由于本文算法和傳統(tǒng)的時間指針脈沖交錯算法均使用脈沖交錯技術(shù)，相比于時間指針算法，時間利用率更高；當目標數(shù)量達到100批時，傳統(tǒng)時間指針脈沖交錯算法的時間利用率維持在55%左右，而本文所提算法的時間利用率維持在60%左右，因此本文所提算法性能更好。

4 結(jié)論

本文提出了基于改進時間指針的啟發(fā)式脈沖交錯任務(wù)調(diào)度方法，該方法從整個時間軸出發(fā)來考量調(diào)度任務(wù)，并合理利用任務(wù)的等待期時長，提升了雷達系統(tǒng)的調(diào)度成功率和時間利用率，并且利用時間資源約束分析和能量約束分析避免了傳統(tǒng)算法的復雜流程。仿真實驗結(jié)果表明，本文所提算法在任務(wù)調(diào)度成功率和時間利用率方面均優(yōu)于傳統(tǒng)時間指針算法和基于時間指針的脈沖交錯算法，調(diào)度性能更佳。