鄭玉軍，田康生，邢曉楠，豐坤

（1.空軍預(yù)警學(xué)院，武漢430019；2.駐207所軍代室，太原030006）

帶時(shí)間窗的相控陣?yán)走_(dá)實(shí)時(shí)任務(wù)調(diào)度方法*

鄭玉軍1，田康生1，邢曉楠2，豐坤1

（1.空軍預(yù)警學(xué)院，武漢430019；2.駐207所軍代室，太原030006）

為了解決傳統(tǒng)相控陣?yán)走_(dá)任務(wù)調(diào)度中采用基于工作方式優(yōu)先級(jí)的方法而存在忽略任務(wù)時(shí)間緊迫性和重要性的問題，提出了一種基于任務(wù)自身工作方式優(yōu)先級(jí)、截止期和空閑時(shí)間3個(gè)特征參數(shù)的相控陣?yán)走_(dá)任務(wù)調(diào)度方法，通過調(diào)整參數(shù)的權(quán)重來適應(yīng)調(diào)度器不同的負(fù)載情況，并采用時(shí)間窗處理發(fā)生沖突的任務(wù)請(qǐng)求，確保更多的高優(yōu)先級(jí)任務(wù)在調(diào)度間隔內(nèi)被調(diào)度。仿真結(jié)果表明，所提出的方法能夠有效提高任務(wù)的調(diào)度成功率，明顯改善調(diào)度器性能。

相控陣?yán)走_(dá)，任務(wù)調(diào)度，截止期，空閑時(shí)間，優(yōu)先級(jí)，時(shí)間窗

0　引言

相控陣?yán)走_(dá)天線在計(jì)算機(jī)的控制下，可以在微秒量級(jí)上進(jìn)行波束捷變，這就使得相控陣?yán)走_(dá)能夠在搜索的同時(shí)進(jìn)行多目標(biāo)跟蹤、制導(dǎo)等多種工作方式的操作［1］。充分發(fā)揮相控陣?yán)走_(dá)波束的靈活電掃描優(yōu)勢(shì)的關(guān)鍵在于任務(wù)調(diào)度。一種高效的調(diào)度方法能夠有效地分配相控陣?yán)走_(dá)資源，達(dá)到提升相控陣?yán)走_(dá)整體性能的目的。

文獻(xiàn)［1］提出了基于最小時(shí)間窗的調(diào)度算法，將每個(gè)任務(wù)的可執(zhí)行時(shí)間擴(kuò)展到整個(gè)調(diào)度間隔，但僅參考了兩個(gè)特征參數(shù)進(jìn)行排序；文獻(xiàn)［2］提出的多任務(wù)并行EDF，綜合了截止期和任務(wù)自身工作方式優(yōu)先級(jí)的兩個(gè)特征參數(shù)，在負(fù)載量較小的情況下有一定的優(yōu)勢(shì)，但在過載情況下其調(diào)度性能并不理想；文獻(xiàn)［3］以加權(quán)時(shí)間偏移量平方和為調(diào)度代價(jià)設(shè)計(jì)調(diào)度算法，但算法復(fù)雜度過大，以至于影響執(zhí)行效率；文獻(xiàn)［4］提出了一種基于任務(wù)綜合規(guī)劃的相控陣?yán)走_(dá)調(diào)度算法，引入了時(shí)間窗的方法，但僅參考了調(diào)度時(shí)刻前后任務(wù)和資源使用情況。

本文在上述研究的基礎(chǔ)上，綜合考慮了相控陣?yán)走_(dá)自身工作方式優(yōu)先級(jí)、任務(wù)截止期和空閑時(shí)間3個(gè)特征參數(shù)，提出了一種帶時(shí)間窗的相控陣?yán)走_(dá)調(diào)度方法。仿真結(jié)果表明本文所提出的方法可以有效改善調(diào)度器的性能。

1　任務(wù)模型

相控陣?yán)走_(dá)任務(wù)調(diào)度的特點(diǎn)是非搶占式，即已執(zhí)行的任務(wù)不能被其他任務(wù)所中斷［5］。與實(shí)時(shí)系統(tǒng)中任務(wù)調(diào)度不同的是相控陣?yán)走_(dá)是按照調(diào)度間隔進(jìn)行任務(wù)的調(diào)度，即當(dāng)前調(diào)度間隔內(nèi)調(diào)度分析下一個(gè)調(diào)度間隔內(nèi)的駐留請(qǐng)求。

任務(wù)請(qǐng)求Qi包含以下要素：

①prii表示任務(wù)自身工作方式優(yōu)先級(jí)。工作方式優(yōu)先級(jí)類型個(gè)數(shù)是在調(diào)度效率、計(jì)算機(jī)處理時(shí)間、存儲(chǔ)器占用量以及目標(biāo)分類方法之間折衷的結(jié)果［6］，旨在根據(jù)目標(biāo)的重要程度強(qiáng)制實(shí)現(xiàn)對(duì)空監(jiān)視和目標(biāo)跟蹤。

②di表示任務(wù)的截止期，即該任務(wù)在這個(gè)時(shí)間之前必須執(zhí)行完畢。

③ai表示任務(wù)的到達(dá)時(shí)間，即任務(wù)被啟動(dòng)并準(zhǔn)備執(zhí)行的時(shí)間。

④dwelli表示任務(wù)的駐留時(shí)間，即任務(wù)在沒有其他任務(wù)中斷的條件下所需的處理器時(shí)間。

⑤si表示任務(wù)的空閑時(shí)間，即該任務(wù)執(zhí)行完畢時(shí)刻到截止期的時(shí)間間隔，反映了任務(wù)的緊迫性。

其中，w2為最晚有效執(zhí)行時(shí)間，w1為最早有效執(zhí)行時(shí)間。

2　調(diào)度算法

2.1綜合優(yōu)先級(jí)設(shè)計(jì)

任務(wù)的工作方式優(yōu)先級(jí)、截止期和空閑時(shí)間是任務(wù)的3個(gè)重要參數(shù)，在很多經(jīng)典的調(diào)度算法（HPF、EDF、LSF等）中得到廣泛應(yīng)用。本文綜合考慮這3個(gè)特征參數(shù)來進(jìn)行調(diào)度分析，將這3個(gè)不同量綱的參數(shù)映射到同一層面上，再利用線性加權(quán)綜合法計(jì)算其綜合優(yōu)先級(jí)pi。本文約定優(yōu)先級(jí)越高，pi數(shù)值越小。

假設(shè)當(dāng)前時(shí)刻調(diào)度器有n個(gè)請(qǐng)求，分別記為Q= {Q1，Q2，…，Qn}，并滿足所有任務(wù)的到達(dá)時(shí)間不大于當(dāng)前時(shí)刻，且所有任務(wù)的截止期減去其駐留時(shí)間不小于當(dāng)前時(shí)刻。

將這n個(gè)請(qǐng)求按照d、s從小到大和pri從高到低進(jìn)行排序，得到d序列d1，d2，…，dn（滿足d1＜d2＜…＜dn）、s序列s1，s2，…，sn（滿足s1＜s2＜…＜sn）以及pri序列pri1，pri2，…，prin（滿足pri1＜pri2＜…＜prin）。任務(wù)請(qǐng)求Q中每一個(gè)任務(wù)Qi的3個(gè)參數(shù)di、si和prii必然是上述3組排列中的3個(gè)值，記為＜di，si，prii，＞=＜dk，sl，prim＞，其中k、l、m是［1，n］范圍內(nèi)的自然數(shù)，分別為特征參數(shù)在d序列、s序列和pri序列中的位置。那么該任務(wù)的綜合優(yōu)先級(jí)就由參數(shù)＜k，l，m＞確定，表示任務(wù)的3個(gè)屬性參數(shù)映射到同一層面，并可以直接加權(quán)的3個(gè)值。那么有pi為k、l和m的函數(shù)pi=f（k，l，m）。

綜合優(yōu)先級(jí)設(shè)計(jì)的目的是為了使緊迫的、重要的任務(wù)具有較高的優(yōu)先級(jí)，考慮到相控陣?yán)走_(dá)處理目標(biāo)數(shù)據(jù)的實(shí)時(shí)性和算法復(fù)雜度，本文采用簡單線性函數(shù)計(jì)算pi，即

其中α、β、γ分別為k、l、m的加權(quán)值，且α+β+γ=1。當(dāng)α＞β+γ時(shí)，調(diào)度算法為截止期優(yōu)先，即任務(wù)的截止期對(duì)綜合優(yōu)先級(jí)的影響最大；當(dāng)β＞α+γ時(shí)，調(diào)度算法為空閑時(shí)間優(yōu)先；同樣，γ＞α+β時(shí)，調(diào)度算法為工作方式優(yōu)先級(jí)優(yōu)先；當(dāng)α=β=γ時(shí)（本文選取α=0. 33、β=0.33、γ=0.34），即均衡考慮3個(gè)參數(shù)，得到的是截止期加空閑時(shí)間加工作方式優(yōu)先級(jí)的調(diào)度算法，是在截止期、空閑時(shí)間以及工作方式優(yōu)先級(jí)之間進(jìn)行折衷的結(jié)果。

式（2）得到的綜合優(yōu)先級(jí)與每個(gè)任務(wù)請(qǐng)求可能不是一一對(duì)應(yīng)的，有可能出現(xiàn)多個(gè)請(qǐng)求的綜合優(yōu)先級(jí)相同的情況［7］。在這種情況下，對(duì)綜合優(yōu)先級(jí)相同的請(qǐng)求可采用FIFO（FirstInFirstOut）準(zhǔn)則來處理。

2.2時(shí)間窗設(shè)計(jì)

為了解決任務(wù)請(qǐng)求在時(shí)間上沖突的問題，利用任務(wù)的實(shí)際執(zhí)行時(shí)間可在期望執(zhí)行時(shí)間前后移動(dòng)的特點(diǎn)，本文在部分借鑒文獻(xiàn)［8］時(shí)間窗設(shè)計(jì)的基礎(chǔ)上，提出了一種帶時(shí)間窗的相控陣?yán)走_(dá)任務(wù)實(shí)時(shí)調(diào)度方法。算法流程如下頁圖1所示。

2.3調(diào)度算法的實(shí)現(xiàn)

文中提出的帶時(shí)間窗的相控陣?yán)走_(dá)實(shí)時(shí)任務(wù)調(diào)度方法流程如圖2所示，由綜合優(yōu)先級(jí)設(shè)計(jì)和時(shí)間窗兩個(gè)部分組成。

圖1　帶時(shí)間窗的相控陣?yán)走_(dá)任務(wù)實(shí)時(shí)調(diào)度流程

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

3.1仿真參數(shù)設(shè)置

相控陣?yán)走_(dá)工作在TAS模式，模擬5種典型的雷達(dá)任務(wù)：驗(yàn)證、精密跟蹤、普通跟蹤、高優(yōu)先級(jí)搜索和低優(yōu)先級(jí)搜索，如表1所示。調(diào)度間隔SI=1 s，按照固定的更新周期產(chǎn)生搜索任務(wù)，當(dāng)搜索檢測(cè)到目標(biāo)時(shí)或以一定概率出現(xiàn)虛警時(shí)產(chǎn)生驗(yàn)證任務(wù)，檢測(cè)概率Pd=0.9，虛警概率Pfa=10-6。目標(biāo)跟蹤起始后按其更新率周期產(chǎn)生跟蹤任務(wù)，一次實(shí)驗(yàn)的仿真時(shí)間為10s。

圖2　調(diào)度算法流程圖

相控陣?yán)走_(dá)調(diào)度器負(fù)載容量是目標(biāo)跟蹤能力的綜合體現(xiàn)，由跟蹤的駐留時(shí)間和采樣率決定［9］。根據(jù)式（3）推算調(diào)度器負(fù)載為250個(gè)。

其中，T為采樣周期，dwell為駐留時(shí)間。

3.2仿真結(jié)果與分析

表征任務(wù)調(diào)度優(yōu)劣的指標(biāo)一般用任務(wù)截止期錯(cuò)失率（Missed DeadlineRatio，MDR）和調(diào)度成功率（Scheduling Success Rate，SSR），計(jì)算公式如下所示［10］。

其中，Ne為未成功調(diào)度執(zhí)行的任務(wù)數(shù)，N為任務(wù)總數(shù)。

表1　相控陣?yán)走_(dá)任務(wù)參數(shù)設(shè)置

圖3　搜索任務(wù)的截止期錯(cuò)失率

圖4　跟蹤任務(wù)的截止期錯(cuò)失率

圖3和圖4為10次仿真結(jié)果的平均值，可以看出當(dāng)γ=1時(shí)，pi=m，綜合優(yōu)先級(jí)完全取決于自身的工作方式優(yōu)先級(jí)，在過載的情況下，刪除的搜索任務(wù)最多，跟蹤任務(wù)的截止期錯(cuò)失率最低；當(dāng)γ=0.7時(shí)，pi=α·k+β·l+0.7m，綜合優(yōu)先級(jí)由截止期、空閑時(shí)間和工作方式優(yōu)先級(jí)決定，但工作方式優(yōu)先級(jí)權(quán)重較大，在調(diào)度器過載的情況下，刪除了一定量的搜索任務(wù)，保證了跟蹤任務(wù)的執(zhí)行；同樣，γ=0.5時(shí)，刪除了一定量的搜索任務(wù)和跟蹤任務(wù)；在γ=0.3時(shí)，綜合優(yōu)先級(jí)很大程度上取決于截止期和空閑時(shí)間，跟蹤任務(wù)雖然工作方式優(yōu)先級(jí)高，但權(quán)重較小，故調(diào)度器刪除了一定量的跟蹤任務(wù)；當(dāng)γ=0時(shí)，綜合優(yōu)先級(jí)完全由截止期和空閑時(shí)間決定，此時(shí)，搜索任務(wù)的截止期錯(cuò)失率最低，跟蹤任務(wù)的截止期錯(cuò)失率最高。

權(quán)值的大小可以由相控陣?yán)走_(dá)執(zhí)行的任務(wù)來調(diào)節(jié)，當(dāng)執(zhí)行搜索任務(wù)時(shí)，可適當(dāng)降低γ值，當(dāng)執(zhí)行跟蹤任務(wù)時(shí)，可適當(dāng)增大γ值。

為了驗(yàn)證本文算法的性能，在相同仿真場(chǎng)景下與經(jīng)典EDF算法進(jìn)行對(duì)比。圖5是γ分別為0.7和0.3時(shí)與經(jīng)典EDF算法的仿真圖，可以看出跟蹤目標(biāo)數(shù)在250個(gè)之前兩種算法的調(diào)度成功率在0.99以上；隨著調(diào)度器負(fù)載的增加，兩種算法的SSR隨之降低，且γ=0.3比γ=0.7時(shí)的算法SSR下降的快，但調(diào)度性能均優(yōu)于EDF算法。

圖5　任務(wù)調(diào)度成功率曲線

為驗(yàn)證帶時(shí)間窗的調(diào)度算法的有效性，將文中提出的方法與無時(shí)間窗的綜合優(yōu)先級(jí)任務(wù)調(diào)度算法進(jìn)行仿真對(duì)比，結(jié)果如圖6～圖8所示?？梢钥闯?，帶時(shí)間窗的調(diào)度算法優(yōu)于無時(shí)間窗的綜合優(yōu)先級(jí)任務(wù)調(diào)度算法。

圖6　任務(wù)請(qǐng)求序列

圖7　無時(shí)間窗的綜合優(yōu)先級(jí)任務(wù)調(diào)度序列

圖8　帶時(shí)間窗的綜合優(yōu)先級(jí)任務(wù)調(diào)度序列

下頁表2為兩種算法調(diào)度性能結(jié)果，其中執(zhí)行任務(wù)數(shù)包括搜索任務(wù)和跟蹤任務(wù)。在跟蹤目標(biāo)不多的情況下，兩種方法的調(diào)度成功率都維持在較高的水平上，且差別不大；隨著跟蹤目標(biāo)數(shù)增加，帶時(shí)間窗調(diào)度方法的優(yōu)勢(shì)顯現(xiàn)出來，調(diào)度成功率比傳統(tǒng)方法高出2%～4%，且在跟蹤150個(gè)目標(biāo)的情況下調(diào)度成功率維持在0.74以上。

表2　兩種算法調(diào)度成功率對(duì)比

4　結(jié)論

如何在資源約束和雷達(dá)限制范圍內(nèi)高效地執(zhí)行多目標(biāo)探測(cè)和跟蹤任務(wù)是相控陣?yán)走_(dá)研制和使用中的一個(gè)關(guān)鍵問題。本文針對(duì)傳統(tǒng)調(diào)度算法調(diào)度成功率低的問題，提出了一種新的相控陣?yán)走_(dá)任務(wù)調(diào)度方法，該方法借鑒了EDF、HPF和LSF等經(jīng)典調(diào)度算法的優(yōu)勢(shì)，綜合考慮了任務(wù)自身工作方式優(yōu)先級(jí)、截止期和空閑時(shí)間，并且引入了時(shí)間窗的方法來提高時(shí)間資源利用率。仿真結(jié)果表明文中方法可以高效地調(diào)度任務(wù)請(qǐng)求，特別是在資源受限的情況下具有很高的調(diào)度成功率。

從文中可以看出3個(gè)特征參數(shù)的權(quán)重在不同程度上影響任務(wù)調(diào)度的性能，權(quán)重值設(shè)置過小會(huì)弱化該參數(shù)的作用，權(quán)重值設(shè)置過大同樣會(huì)降低調(diào)度成功率。因此，如何設(shè)置合理的權(quán)重是下一步研究的內(nèi)容。

［1］綦文超，楊瑞娟，李曉柏，等.基于最小時(shí)間窗的多功能雷達(dá)調(diào)度算法研究［J］.現(xiàn)代防御技術(shù)，2012，40（5）：104-110.

［2］綦文超，楊瑞娟，李曉柏，等.多功能一體化雷達(dá)任務(wù)調(diào)度算法研究［J］.雷達(dá)科學(xué)與技術(shù)，2012，10（2）：150-155.

［3］趙宇.李建勛，曹蘭英，等.基于二次規(guī)劃的相控陣?yán)走_(dá)任務(wù)自適應(yīng)調(diào)度算法［J］.系統(tǒng)工程與電子技術(shù)，2012，34（4）：698-703.

［4］鄭世友，鄭瑤.基于任務(wù)綜合規(guī)劃的相控陣?yán)走_(dá)自適應(yīng)調(diào)度方法［J］.計(jì)算機(jī)仿真，2013，30（7）：11-16.

［5］盧建斌，胡衛(wèi)東，郁文賢.多功能相控陣?yán)走_(dá)實(shí)時(shí)任務(wù)調(diào)度研究［J］.電子學(xué)報(bào)，2006，34（4）：732-736.

［6］趙新爽，汪厚祥，蔡益朝.反導(dǎo)預(yù)警作戰(zhàn)資源調(diào)度方法［J］.系統(tǒng)工程與電子技術(shù)，2015，37（6）：1300-1305.

［7］鄭偉，王磊，曹建蜀.改進(jìn)DPSO算法求解仿真任務(wù)調(diào)度問題［J］.信號(hào)處理，2015，31（4）：474-482.

［8］郭坤鵬，左燕，薛安克.一種基于模糊邏輯優(yōu)先級(jí)的雷達(dá)任務(wù)自適應(yīng)調(diào)度算法［J］.江南大學(xué)學(xué)報(bào)（自然科學(xué)版），2013，12（5）：591-595.

［9］羅江鋒，朱承，劉忠，等.連續(xù)多目標(biāo)來襲下的艦艇防空火力在線調(diào)度［J］.系統(tǒng)工程理論與實(shí)踐，2014，34（11）：2929-2937.

［10］葉朝謀，丁建江，余志強(qiáng)，等.基于周期分區(qū)的相控陣?yán)走_(dá)任務(wù)交叉調(diào)度研究［J］.電子與信息學(xué)報(bào)，2014，36（2）：435-440.

Way of Phased Array Radar Real-time Task Scheduling with Time Windows

ZHENG Yu-jun1，TIANKang-sheng1，XING Xiao-nan2，F(xiàn)ENG Kun1
（1.Air Force Early-warning Academy，Wuhan 430019，China；2.Martial Delegate Office of PLA in 207 Institute，Taiyuan 030006，China）

In order to solve the traditional phased array radar task scheduling，a prior way，which will ignore the issues of the urgency and importance of task time，based on work style，is adopted to come up with a way of the phased array radar task scheduling that is based on the three characteristic parameters：the priority of itself work style，deadline and idle time.It accommodates the different load conditions of the radar scheduler by adjusting the parameter weight.The request of handling sudden tasks with time windows is aimed at making sure that more and more high priority tasks can be dispatched in a scheduling interval.The simulation results show that the methods mentioned in the article can efficiently increase the successful rate of task scheduling and obviously improve the property of radar scheduler.

phasedarrayradar，task scheduling，deadline，idletime，priority，timewindow

TN958.92

A

1002-0640（2016）10-0070-05

2015-08-13

2015-09-16

2014年度全軍軍事類研究生基金資助項(xiàng)目（2014JY548）

鄭玉軍（1988-），男，山東濟(jì)寧人，博士生。研究方向：預(yù)警情報(bào)組網(wǎng)。