基于多級(jí)時(shí)間窗的綜合優(yōu)先級(jí)雷達(dá)任務(wù)調(diào)度算法

魯 金 暢 言 陳 春

(西安電子工程研究所 西安 710100)

0 引言

現(xiàn)代相控陣?yán)走_(dá)往往集搜索、確認(rèn)、跟蹤、識(shí)別等多種功能于一體。而多功能一體化勢(shì)必導(dǎo)致各種任務(wù)同時(shí)競(jìng)爭(zhēng)雷達(dá)的時(shí)間、空間和能量等資源。這時(shí)就需要合理地安排各類任務(wù)的執(zhí)行順序，最優(yōu)地利用雷達(dá)的各類資源，以滿足作戰(zhàn)任務(wù)的需求。這是對(duì)雷達(dá)多任務(wù)的調(diào)度能力提出了新的需求。

傳統(tǒng)的調(diào)度算法[1-4]是基于任務(wù)工作方式的優(yōu)先級(jí)調(diào)度算法，即按工作方式進(jìn)行優(yōu)先級(jí)排序，重要的任務(wù)(如確認(rèn)任務(wù)、精確跟蹤任務(wù)等)優(yōu)先被執(zhí)行；次要的任務(wù)(如氣象任務(wù)、自檢任務(wù))隨后被執(zhí)行。該類算法著重考慮了任務(wù)重要性原則，但分隔了同一任務(wù)中駐留請(qǐng)求的相關(guān)性，在高負(fù)載情況下會(huì)導(dǎo)致低優(yōu)先級(jí)一直不能被調(diào)度；文獻(xiàn)[5]將EDF(Earlier Deadline First)調(diào)度算法引入到雷達(dá)任務(wù)調(diào)度中，該算法假設(shè)每個(gè)任務(wù)都有一個(gè)截止時(shí)間，對(duì)于截止期最鄰近的任務(wù)設(shè)置最高的優(yōu)先級(jí)，進(jìn)行優(yōu)先調(diào)度，若過了這個(gè)截止時(shí)間還未被執(zhí)行，則丟棄。文獻(xiàn)[6]從理論上證明了該算法從截止期錯(cuò)失率(MTR，Missed Deadline Ratio)的角度是最優(yōu)的。但該算法僅考慮了任務(wù)緊迫性，而未考慮任務(wù)的重要性。 MEDF(Modified Earlier Deadline First)[7]是EDF的推廣模型，它將EDF和事件優(yōu)先級(jí)相結(jié)合，綜合考慮了任務(wù)的時(shí)間屬性和事件屬性，確保有些緊迫性的實(shí)時(shí)任務(wù)(如確認(rèn)任務(wù))未必是截止期最早的，也可以被優(yōu)先調(diào)度。文獻(xiàn)[8]在MEDF的基礎(chǔ)上，提出了基于時(shí)間窗的任務(wù)調(diào)度算法，該算法允許任務(wù)的實(shí)際執(zhí)行時(shí)間可以在期望執(zhí)行時(shí)間的時(shí)間窗內(nèi)移動(dòng)，這大大提高了任務(wù)調(diào)度的成功率。

以上基于EDF的雷達(dá)任務(wù)調(diào)度算法本質(zhì)上均屬于硬實(shí)時(shí)調(diào)度算法[9]，即雷達(dá)任務(wù)的執(zhí)行必須在某個(gè)時(shí)間點(diǎn)或者時(shí)間窗口內(nèi)執(zhí)行，過了這個(gè)時(shí)間點(diǎn)或者窗口期則該任務(wù)就被丟棄。而雷達(dá)在實(shí)際應(yīng)用中，尤其是在定向監(jiān)視模式下，當(dāng)負(fù)載較輕時(shí)，可以提前于窗口期執(zhí)行，以提高任務(wù)的數(shù)據(jù)率；當(dāng)負(fù)載較重時(shí)，也可以在窗口期后執(zhí)行，此時(shí)雖然降低了任務(wù)數(shù)據(jù)率，但提高了任務(wù)的容量。基于此，本文提出了一種基于“多級(jí)時(shí)間窗的綜合優(yōu)先級(jí)”的調(diào)度算法。

1 調(diào)度模型

綜合優(yōu)先級(jí)由靜態(tài)事件優(yōu)先級(jí)和動(dòng)態(tài)自適應(yīng)優(yōu)先級(jí)兩部分疊加組成。即

(1)

表1 各類任務(wù)事件優(yōu)先級(jí)典型值

圖1 “多級(jí)時(shí)間窗”動(dòng)態(tài)權(quán)值

(2)

其中，τi為第i個(gè)任務(wù)距離上一次被執(zhí)行經(jīng)歷的時(shí)間；Ti為第i個(gè)任務(wù)指標(biāo)要求的數(shù)據(jù)周期；ξi是一個(gè)與“時(shí)間窗”相關(guān)的因子，表征該任務(wù)需要被執(zhí)行的緊迫程度。當(dāng)ξi是一個(gè)常數(shù)時(shí)，表征該任務(wù)需要被執(zhí)行的緊迫性與時(shí)間是一個(gè)線性關(guān)系，ξi也可以是τi表達(dá)式，如式(3)所示。

ξi=ek·τi

(3)

此時(shí)，當(dāng)k>0時(shí)，任務(wù)被執(zhí)行緊迫性隨時(shí)間的增加而指數(shù)級(jí)增加。

2 仿真分析

仿真選取兩種工作方式，即搜索任務(wù)和跟蹤任務(wù)，詳細(xì)參數(shù)見表2所示。在仿真中，對(duì)于每個(gè)目標(biāo)的跟蹤時(shí)刻假定是從仿真起始時(shí)刻到該目標(biāo)第一個(gè)跟蹤采樣周期間隨機(jī)選取，而跟蹤目標(biāo)的撤銷時(shí)刻是仿真結(jié)束時(shí)刻。

表2 仿真參數(shù)

仿真結(jié)果如圖2所示，其中圖2(a)分別給出了傳統(tǒng)事件優(yōu)先級(jí)算法(HPF)、最早截止期優(yōu)先算法(EDF)、基于時(shí)間窗最早截止期優(yōu)先算法(FEDF)，以及本文提出的基于多級(jí)時(shí)間窗綜合優(yōu)先級(jí)算法(MF)的截止期錯(cuò)失率(未被調(diào)度成功的任務(wù)個(gè)數(shù)與參加調(diào)度的任務(wù)總數(shù)之比)與目標(biāo)跟蹤個(gè)數(shù)的曲線關(guān)系。從圖2(a)中可以看出：

1)若用截止期錯(cuò)失率衡量調(diào)度算法好壞的性能指標(biāo)，則HPF

2) 基于多級(jí)時(shí)間窗的綜合優(yōu)先級(jí)算法(MF)的截止期錯(cuò)失率恒為0，表明所有任務(wù)均被調(diào)度。

而從圖2(b)中搜索任務(wù)與跟蹤任務(wù)隨目標(biāo)個(gè)數(shù)的變化曲線可以看出：

圖2 任務(wù)截止期錯(cuò)失率和任務(wù)數(shù)據(jù)率隨跟蹤目標(biāo)數(shù)的變化曲線

1) 低負(fù)載情況下，跟蹤任務(wù)嚴(yán)格等于指標(biāo)規(guī)定的數(shù)據(jù)率，而搜索任務(wù)數(shù)據(jù)率隨著負(fù)載的增加而變小(周期變大)；

2) 隨著負(fù)載的增加，搜索任務(wù)數(shù)據(jù)率增加至特定值后保持不變，而跟蹤數(shù)據(jù)率開始下降(等效于事件優(yōu)先級(jí)算法的優(yōu)先級(jí)反轉(zhuǎn))；

3) 再增加負(fù)載，搜索任務(wù)和跟蹤任務(wù)的數(shù)據(jù)率同時(shí)下降，且搜索任務(wù)下降的速率大于跟蹤任務(wù)。

3 結(jié)束語

高效的任務(wù)調(diào)度算法是實(shí)現(xiàn)相控陣?yán)走_(dá)多功能一體化的基礎(chǔ)。本文在傳統(tǒng)相控陣?yán)走_(dá)任務(wù)調(diào)度算法的基礎(chǔ)上，提出一種新的基于多級(jí)時(shí)間窗的綜合優(yōu)先級(jí)調(diào)度算法。該算法綜合考慮靜態(tài)任務(wù)屬性和動(dòng)態(tài)“時(shí)間窗”權(quán)值兩個(gè)參數(shù)，以保證低優(yōu)先級(jí)的任務(wù)隨著時(shí)間的增加而提高其綜合優(yōu)先級(jí)，從而提高其被調(diào)度執(zhí)行的機(jī)會(huì)。仿真結(jié)果表明，該算法能保證系統(tǒng)所有任務(wù)都能被執(zhí)行。且隨著負(fù)載的增加，各個(gè)任務(wù)的數(shù)據(jù)率會(huì)整體下降。這符合相控陣?yán)走_(dá)多功能一體化的需求。但在一些特殊應(yīng)用場(chǎng)景，如雷達(dá)正在執(zhí)行跟蹤制導(dǎo)射擊時(shí)，此時(shí)系統(tǒng)需全力保證被射擊對(duì)象的精密跟蹤。針對(duì)此類特殊的應(yīng)用場(chǎng)景，還可以在以后的研究中做進(jìn)一步的探索。