一種基于周期分區(qū)的時間調(diào)度算法*

葉朝謀，丁建江，俞志強，程夢夢

（1.空軍預(yù)警學(xué)院，武漢 430019；2.解放軍95112部隊，廣東 佛山 528227）

一種基于周期分區(qū)的時間調(diào)度算法*

葉朝謀1，2，丁建江1，俞志強1，程夢夢1

（1.空軍預(yù)警學(xué)院，武漢 430019；2.解放軍95112部隊，廣東 佛山 528227）

針對多功能相控陣雷達任務(wù)實時調(diào)度問題，提出了一種基于采樣周期分區(qū)的時間資源調(diào)度算法（記為PD）。該算法以各類任務(wù)采樣周期的最大公約數(shù)為分區(qū)標準，將各采樣周期均分為多個等長區(qū)間，再將各類任務(wù)平均分配到不同分區(qū)中調(diào)度執(zhí)行，可解決調(diào)度過程中任務(wù)因采樣周期不同產(chǎn)生沖突的難題。仿真結(jié)果表明，該算法可提高系統(tǒng)任務(wù)調(diào)度能力，可廣泛應(yīng)用于相控陣雷達任務(wù)調(diào)度及其他實時任務(wù)調(diào)度系統(tǒng)。

資源管控，時間調(diào)度，周期分區(qū)，算法

引言

相控陣雷達天線波束可在微秒量級上快速捷變，但是如何充分發(fā)揮上述優(yōu)勢，合理分配有限時間能量資源從而提高系統(tǒng)整體探測效能，任務(wù)調(diào)度是其中需要解決的關(guān)鍵問題之一。

目前相控陣雷達調(diào)度策略的設(shè)計方法逐漸從固定模板、多模板和部分模板等模板類調(diào)度策略轉(zhuǎn)向自適應(yīng)調(diào)度策略的設(shè)計上，自適應(yīng)調(diào)度策略是最有效但也是最復(fù)雜的調(diào)度方法［1］。相關(guān)研究較多，如文獻［2-3］考慮任務(wù)實時性要求，綜合多個任務(wù)屬性得到任務(wù)綜合優(yōu)先級，提高了調(diào)度性能。文獻［4］將雷達任務(wù)建模成實時周期性任務(wù)，提出了一種綜合任務(wù)周期調(diào)度算法。文獻［5］以任務(wù)偏離規(guī)定執(zhí)行點為優(yōu)化函數(shù)，提出的調(diào)度方法在任務(wù)延遲方面具有較好的性能。文獻［6］針對同時多波束情形提出了一種多波束調(diào)度算法。文獻［7］基于駐留時間可變思想，分別提出了駐留時長可變調(diào)度算法，提高了任務(wù)調(diào)度能力。另外，文獻［8-9］在任務(wù)調(diào)度優(yōu)化模型、抗干擾條件下任務(wù)合并與失蹤處理等方面進行了深入分析。

上述各調(diào)度算法從不同應(yīng)用條件下使得系統(tǒng)調(diào)度能力得到一定的提高，但仍未有效解決任務(wù)因采樣周期不同在時間上相互沖突的問題。對此，本文進行深入研究并提出一種基于采樣周期分區(qū)的時間資源實時調(diào)度算法。

1 任務(wù)模型

1.1 單個駐留任務(wù)的描述

通常情況下，單個駐留任務(wù)可由以下一組要素來表示：（M，ta，td，te，I，P），其中M表示駐留模式，ta表示任務(wù)到達時間，td表示任務(wù)截止期，te表示任務(wù)實際執(zhí)行時間，I表示任務(wù)重要性優(yōu)先級，P表示駐留任務(wù)采樣周期。駐留模式M包含3個要素：（t，w，r），其中t表示發(fā)射持續(xù)時間，w表示空閑時間，r表示接收持續(xù)時間。

1.2 搜索任務(wù)模型

設(shè)某搜索區(qū)域i包含Bsi個波位，搜索采樣周期為Psi，搜索區(qū)域重要性值為Isi，發(fā)射模式為Msi，將整個區(qū)域一次完整搜索視為一個搜索任務(wù)，則可得到此區(qū)域搜索任務(wù)模型為：

各駐留請求到達時間關(guān)系為：

各駐留請求截止期關(guān)系為：

1.3 跟蹤任務(wù)模型

設(shè)第i號目標跟蹤任務(wù)模型為：

其中Bti表示對第i號目標的跟蹤照射次數(shù)，通常由于目標捕獲與消失時間難以確定而為未知數(shù)。

假設(shè)目標捕獲后隨即發(fā)射一個驗證波束，確認目標后進行跟蹤，且設(shè)緊接確認波束后的跟蹤波束間隔時間可為不大于跟蹤間隔時間的任意值，則此目標各駐留請求到達時間與截止期關(guān)系有：

其中Pti表示此類目標跟蹤間隔時間；ΔPti表示確認后的首次跟蹤駐留請求間隔時間，要求不大于Pti；Δt1ti表示驗證駐留請求的時間窗寬度；Δtti表示i號目標駐留請求的時間窗寬度。

2 任務(wù)調(diào)度算法

2.1 算法基本思想

設(shè)跟蹤任務(wù)采樣周期的集合為 {P1，P2，P3，…，Pn}，所有周期的最大公約數(shù)為Pgcd，以Pgcd作為一個標準調(diào)度區(qū)間長度，設(shè)為Plot=Pgcd。

將任一采樣周期Pk按Pgcd均分為Nk個標準調(diào)度區(qū)間長度，即有：

且在任一標準調(diào)度區(qū)間內(nèi)，各類周期任務(wù)分別集中分配到一個相對固定的范圍內(nèi)執(zhí)行。設(shè)各類周期任務(wù)相對本區(qū)間起始點的執(zhí)行起始時間為Sk，該類周期任務(wù)在各區(qū)間中的最大占用時間長度為Lk，各類周期區(qū)相對本區(qū)間起始點的結(jié)束時間點為Ek。注意各Ek后須保留一定的空閑時間Rk作為備用，且將跟蹤任務(wù)占用之外后的剩余時間盡量平均分配到各類周期結(jié)束時間點Ek之前。調(diào)度過程中，搜索任務(wù)則按優(yōu)先級順序依次在各類周期跟蹤任務(wù)完畢之后的空閑時段內(nèi)完成。圖1所示為跟蹤任務(wù)包含3個不同采樣周期的任務(wù)調(diào)度分配關(guān)系，其中P1，P2，P3分別為1 s、2 s、3 s。

圖1 任務(wù)調(diào)度分配示意圖

2.2 算法實現(xiàn)流程

對任一標準調(diào)度區(qū)間［t0，t0+Plot］，跟蹤任務(wù)以采樣周期類別不同在所劃定的起始與結(jié)束點范圍［Sk，Ek］內(nèi)分別執(zhí)行，且本類周期跟蹤任務(wù)執(zhí)行完畢后，如果在Ek時間點之前還有空閑時間，則執(zhí)行搜索任務(wù)；當時間指針到達Ek時則執(zhí)行下一類周期跟蹤任務(wù)，時間指針跳轉(zhuǎn)至下一類周期起始點Sk+1。算法的具體實現(xiàn)步聚如下頁圖2所示。

Step1：時間指針tp跳轉(zhuǎn)至本標準調(diào)度區(qū)間第一類周期起始點S1；初始化k=0；

Step2：k=k+1；若k＜=n即跟蹤任務(wù)采樣周期類別數(shù)，則按照調(diào)度間隔執(zhí)行Pk周期類跟蹤任務(wù)tkj，tp跳轉(zhuǎn)至Sk；若k＞n，跳轉(zhuǎn)至Step5；

Step3：若tkj未執(zhí)行完且tp已到達Ek，則轉(zhuǎn)而執(zhí)行下一類周期跟蹤任務(wù)，跳轉(zhuǎn)至Step2；

Step4：若tkj執(zhí)行完畢后，tp〈Ek，則按任務(wù)優(yōu)先級執(zhí)行搜索任務(wù)，tp到達Ek或搜索任務(wù)執(zhí)行完則轉(zhuǎn)而執(zhí)行下一類周期任務(wù)，跳轉(zhuǎn)至Step2；注意在執(zhí)行搜索任務(wù)過程中，如果發(fā)現(xiàn)采樣周期為Pm類新目標，將其置于本類周期最小Lmj（j=mod（i，Nm））的對應(yīng)區(qū)間跟蹤任務(wù)之后，并保證首次跟蹤采樣周期不大于Pm。

圖2 基于采樣周期分區(qū)的任務(wù)調(diào)度流程圖

Step5：進行負載分析與過載處理，若過載，則刪除部分任務(wù)；

Step6：調(diào)整各類周期起始點Sk，使各周類周期跟蹤任務(wù)之后盡量平均分配空閑時間；

Step7：該標準調(diào)度區(qū)間結(jié)束，轉(zhuǎn)入下一區(qū)間。

3 調(diào)度負載分析

定義任務(wù)時間負載率為任務(wù)集內(nèi)各任務(wù)駐留時間與采樣周期之比值的總和；任務(wù)時間占用率為任務(wù)集調(diào)度過程中占用時間與采樣周期之比值。

根據(jù)前面建立的任務(wù)模型，可得：

采樣周期為Pk的跟蹤任務(wù)時間資源占用率為：

某i區(qū)搜索的時間占用率為：

任務(wù)總時間占用率為：

當η'〈=1-∑Rk/pgcd時，則表示系統(tǒng)負載正常，否則表示過載，此時需根據(jù)實際采取必要的降低任務(wù)時間負載調(diào)整措施，如降低跟蹤目標數(shù)據(jù)率、增大搜索幀周期、刪除部分跟蹤或搜索任務(wù)等。

4 仿真分析

仿真條件：假定雷達探測目標可分為3類，各類目標分別對應(yīng)各自搜索、驗證與跟蹤工作方式，任務(wù)參數(shù)如表1所示。設(shè)仿真時間為150 s，調(diào)度間隔選取為25 ms，各類目標發(fā)現(xiàn)時間隨機產(chǎn)生且直到仿真結(jié)束才消失。任一標準調(diào)度區(qū)間的各類周期目標結(jié)束點后保留15 ms作為備用時間。圖3至下頁圖5分別為PD、HPEDF［1］、EDF算法仿真結(jié)果，其中大時間窗時各類跟蹤任務(wù)時間窗限制分別為25 ms、50 ms、75 ms，小時間窗時各類跟蹤任務(wù)時間窗限制均為25 ms。

表1 任務(wù)參數(shù)表

仿真結(jié)果分析：

圖3 大時間窗時性能對比

圖4 小時間窗時性能對比

①由圖3、圖4可知，當時間窗較大時，3種算法的最大調(diào)度負載能力相近，當時間窗較小時，PD算法的最大調(diào)度負載能力高于其他算法；在系統(tǒng)負載飽和時，HPEDF、EDF算法存在高優(yōu)先級任務(wù)比低優(yōu)先級任務(wù)先被刪除的現(xiàn)象，而PD算法可按任務(wù)優(yōu)先級排序進行任務(wù)刪除處理，避免了高優(yōu)先級任務(wù)比低優(yōu)先級任務(wù)先被刪除的不足。

②由圖5可知，時間窗更小的條件下，PD算法調(diào)度性能沒有明顯下降，僅在系統(tǒng)飽和前新任務(wù)調(diào)度失敗率略高一點，但系統(tǒng)最大負載能力未降低，表明算法具有較好的時間窗適應(yīng)性。

圖5 PD算法大小時間窗時性能對比

5 結(jié)束語

本文針對相控陣雷達任務(wù)實時調(diào)度問題，提出了一種基于周期最大公約數(shù)分區(qū)的時間資源調(diào)度算法，該算法可解決跟蹤任務(wù)因周期不同產(chǎn)生沖突的問題，從而提高了系統(tǒng)負載能力，仿真結(jié)果表明了其有效可行性，調(diào)度性能優(yōu)于一般調(diào)度算法。該算法可廣泛應(yīng)用于相控陣雷達任務(wù)調(diào)度以及一般性任務(wù)調(diào)度系統(tǒng)。

［1］Komorniczak W，Pietrasinski J，Solaiman B.The Data Fusion Approach to the Priority Assignment in the Multifunction Radar［C］//IEEE 14th International Conference on Microwarves，Radar and Wireless Communications，Poland，2002:647-650.

［2］盧建斌.相控陣雷達資源優(yōu)化管理的理論與方法［D］.長沙：國防科學(xué)技術(shù)大學(xué)研究生院，2007.

［3］Zhang B Y，Li S H，Yan W，et al.An Efficient Scheduling Method for Phased Array Radars with Limited Time Resources［C］//IEEE International Radar Conference，Guilin，China，2009:1-4.

［4］Shih C S，Gopalakrishnan S，Ganti P，et al.Scheduling Real-time Dwells Tasks with Synthetic Periods［C］//IEEE Real-Time Systems Symposium，Mexico，2003:210-219.

［5］Baptiste P，Sadykov R.Time-indexed Formulations for Scheduling Chains on a Single Machine:An Application to Airborne Radars［J］.European Journal of Operational Research，2010，203（2）:476-483.

［6］Chen J，Tian Z，Wang L，et al.Adaptive Simultaneous Multi-beam Dell Scheduling Algorithm for Multifunction Phased Array Radars［J］.Journal of Information&Computational Science，2011，8（14）:3051-3061.

［7］Mir H，Abdelaziz F B.Cyclic Task Scheduling for Multifunction Radar［J］.IEEE Transanctions on Automation Science and Engineering，2012，9（3）:529-537.

［8］ Jimenez M I，Val L D，Villacorta J J.Design of Task Scheduling Process for a Multifunction Radar［J］.Radar，Sonar&Navigation，IET，2012，6（5）:341-347.

［9］周 穎，施龍飛，陳明輝，等.密集干擾環(huán)境下相控陣雷達資源管理優(yōu)化研究［J］.電子學(xué)報，2005（6）:999-1003.

A Time Scheduling Algorithm Based on Period Division

YE Chao-mou1，2，DING Jian-jiang1，YU Zhi-qiang1，CHENG Meng-meng1
（1.Air Force Early Warning Academy，Wuhan 430019，China；2.Unit 95112 of PLA，F(xiàn)oshan 528227，China）

A time scheduling algorithm for multifunction radar task scheduling based on period division is proposed in this paper.This method divides various sampling periods into several equal portions according to the greatest common divisor of all sampling periods and assigns equally tasks to different divisions，which can solve tasks confliction caused by different sampling periods.The results show that the approach proposed improves tasks scheduling capability and is practicable in phased array radar task scheduler and other systems.

resource management，time scheduling，period division，algorithm

TN95

A

1002-0640（2014）10-0023-04

2013-08-20

2013-10-20

軍隊“十二五”預(yù)研項目（51307010102）；全軍軍事學(xué)研究生課題（2011JY002-537）；全軍軍事學(xué)研究生基金資助項目（2012JY002-601）

葉朝謀（1980- ），男，湖北洪湖人，博士研究生。研究方向：雷達組網(wǎng)資源優(yōu)化管控。