明 樂(lè)，周 峰，顧競(jìng)豪，丁日顯

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

0 引言

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

1 駐留任務(wù)模型

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

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

(1)

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

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

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

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

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

(2)

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

(3)

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

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

(4)

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

2.1 改進(jìn)時(shí)間指針原理

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

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

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

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

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

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

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

(5)

tw0≥tx1+tw1+tr1

(6)

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

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

(7)

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

(8)

(9)

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

(10)

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

(11)

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

(12)

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

(13)

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

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

假設(shè)某一個(gè)調(diào)度間隔(SI)的起始時(shí)刻為to，結(jié)束時(shí)刻為tend，tp為時(shí)間指針，Q={q1,q2,…,qN}表示的是tp時(shí)刻整個(gè)調(diào)度時(shí)間軸上所有任務(wù)請(qǐng)求形成的申請(qǐng)鏈表。基于改進(jìn)時(shí)間指針的啟發(fā)式脈沖交錯(cuò)算法的具體步驟如下：

第一步 初始化剩余時(shí)間軸為[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，然后進(jìn)行下一個(gè)調(diào)度間隔的工作。

第八步 雷達(dá)工作完畢。

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

3.1 性能評(píng)估指標(biāo)

為了驗(yàn)證本文所提新算法的優(yōu)勢(shì)，利用以下評(píng)估指標(biāo)進(jìn)行算法間的對(duì)比：

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

(14)

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

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

(15)

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

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

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

通過(guò)仿真得到本文算法與時(shí)間指針?biāo)惴ā鹘y(tǒng)的時(shí)間指針脈沖交錯(cuò)算法的調(diào)度成功率和時(shí)間利用率對(duì)比曲線圖如圖5和圖6所示。

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

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

圖6 時(shí)間利用率對(duì)比Fig.6 Comparison of time utilization

從圖5中能夠得出在目標(biāo)數(shù)量超過(guò)30批時(shí)，時(shí)間指針?biāo)惴ê蛡鹘y(tǒng)的時(shí)間指針脈沖交錯(cuò)算法的調(diào)度成功率已經(jīng)開(kāi)始下降；當(dāng)目標(biāo)數(shù)量超過(guò)40批時(shí)，本文提出的改進(jìn)的時(shí)間指針啟發(fā)式脈沖交錯(cuò)算法的調(diào)度成功率才開(kāi)始下降，提升了系統(tǒng)跟蹤目標(biāo)的最大數(shù)量。而且本文算法下降得更加緩慢，因?yàn)槠洳粌H使用了脈沖交錯(cuò)技術(shù)，充分利用了雷達(dá)任務(wù)的等待期，還從整個(gè)時(shí)間軸出發(fā)選擇請(qǐng)求任務(wù)，在一定程度上可以減少任務(wù)的錯(cuò)失率，能夠進(jìn)一步提升其調(diào)度成功率。

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

4 結(jié)論

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