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

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

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

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

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

0　引言

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

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

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

1　任務(wù)模型

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

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

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

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

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

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

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

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

2　調(diào)度算法

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

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

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

將這n個請求按照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中每一個任務(wù)Qi的3個參數(shù)di、si和prii必然是上述3組排列中的3個值，記為＜di，si，prii，＞=＜dk，sl，prim＞，其中k、l、m是［1，n］范圍內(nèi)的自然數(shù)，分別為特征參數(shù)在d序列、s序列和pri序列中的位置。那么該任務(wù)的綜合優(yōu)先級就由參數(shù)＜k，l，m＞確定，表示任務(wù)的3個屬性參數(shù)映射到同一層面，并可以直接加權(quán)的3個值。那么有pi為k、l和m的函數(shù)pi=f（k，l，m）。

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

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

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

2.2時間窗設(shè)計

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

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

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

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

3　仿真實(shí)驗

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

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

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

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

其中，T為采樣周期，dwell為駐留時間。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4　結(jié)論

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

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

［1］綦文超，楊瑞娟，李曉柏，等.基于最小時間窗的多功能雷達(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ī)仿真，2013，30（7）：11-16.

［5］盧建斌，胡衛(wèi)東，郁文賢.多功能相控陣?yán)走_(dá)實(shí)時任務(wù)調(diào)度研究［J］.電子學(xué)報，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］.信號處理，2015，31（4）：474-482.

［8］郭坤鵬，左燕，薛安克.一種基于模糊邏輯優(yōu)先級的雷達(dá)任務(wù)自適應(yīng)調(diào)度算法［J］.江南大學(xué)學(xué)報（自然科學(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é)報，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年度全軍軍事類研究生基金資助項目（2014JY548）

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