基于綜合優(yōu)先級(jí)的改進(jìn)執(zhí)行時(shí)間分配算法

侯澤欣，涂剛毅，吳少鵬

(中國(guó)船舶重工集團(tuán)公司第七二四研究所，南京 210003)

0 引言

相控陣天線的波束快速掃描技術(shù)特點(diǎn)使相控陣?yán)走_(dá)可在搜索的同時(shí)進(jìn)行多目標(biāo)跟蹤及多種雷達(dá)功能的操作，但相控陣?yán)走_(dá)的多目標(biāo)、多功能工作能力受雷達(dá)時(shí)間資源及雷達(dá)輻射信號(hào)總能量的限制。因此，研究合理的雷達(dá)任務(wù)調(diào)度算法對(duì)相控陣?yán)走_(dá)的資源有效分配及優(yōu)化雷達(dá)的整體性能具有重大意義。

傳統(tǒng)相控陣?yán)走_(dá)調(diào)度按照任務(wù)預(yù)定的優(yōu)先級(jí)由高到低或截止期由早到晚調(diào)度執(zhí)行，靈活性差、時(shí)間利用率低。何金新、李大鵬等［1-2］對(duì)駐留時(shí)間窗進(jìn)行了研究，使雷達(dá)任務(wù)調(diào)度的時(shí)間靈活性得到提高，但對(duì)任務(wù)的優(yōu)先級(jí)設(shè)計(jì)均未作考慮。盧建斌等［3］提出綜合考慮工作方式優(yōu)先級(jí)和截止期兩個(gè)參數(shù)獲得綜合優(yōu)先級(jí)，算法靈活性高，調(diào)度性能有明顯改善。王多強(qiáng)等［4］對(duì)實(shí)時(shí)任務(wù)調(diào)度的多特征參數(shù)綜合優(yōu)先級(jí)設(shè)計(jì)進(jìn)行了研究，使調(diào)度性能得到提高。

本文基于多特征參數(shù)的任務(wù)優(yōu)先級(jí)表設(shè)計(jì)思想，研究一種雷達(dá)任務(wù)多特征參數(shù)綜合優(yōu)先級(jí)的計(jì)算方法，并在傳統(tǒng)的自適應(yīng)執(zhí)行時(shí)間順序分配調(diào)度算法基礎(chǔ)上提出改進(jìn)的執(zhí)行時(shí)間分配算法，根據(jù)綜合優(yōu)先級(jí)計(jì)算結(jié)果進(jìn)行任務(wù)的自適應(yīng)調(diào)度。最后仿真結(jié)果表明，本文所提算法能夠有效地減小任務(wù)的平均時(shí)間偏移率，確保多功能相控陣?yán)走_(dá)中對(duì)時(shí)序要求極高的通信、干擾及數(shù)據(jù)傳輸?shù)热蝿?wù)的有效執(zhí)行，提高多功能相控陣?yán)走_(dá)的作戰(zhàn)效能。

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

相控陣?yán)走_(dá)控制器需要對(duì)申請(qǐng)執(zhí)行的任務(wù)進(jìn)行有效的調(diào)度分配，根據(jù)各任務(wù)綜合優(yōu)先級(jí)的大小進(jìn)行合理的調(diào)度。下面對(duì)幾種主要雷達(dá)駐留任務(wù)進(jìn)行分析，根據(jù)各任務(wù)特征參數(shù)研究任務(wù)綜合優(yōu)先級(jí)的計(jì)算算法。

1.1 雷達(dá)駐留任務(wù)分析

根據(jù)相控陣?yán)走_(dá)系統(tǒng)的兩種最基本工作方式，將申請(qǐng)調(diào)度任務(wù)分為搜索和跟蹤兩類，其中搜索任務(wù)包括低優(yōu)先級(jí)搜索和高優(yōu)先級(jí)搜索任務(wù)。搜索檢測(cè)到新目標(biāo)后將產(chǎn)生確認(rèn)任務(wù)對(duì)目標(biāo)進(jìn)行航跡起始，然后針對(duì)目標(biāo)的不同特征屬性及威脅度分析將跟蹤任務(wù)分為普通跟蹤和精密跟蹤任務(wù)。下面給出相控陣?yán)走_(dá)的駐留任務(wù)的形式化描述:

其中，Pri為工作方式優(yōu)先級(jí);TOA為期望發(fā)射時(shí)間即到達(dá)時(shí)間;W 是任務(wù)時(shí)間窗;Tdwell為駐留時(shí)間即任務(wù)執(zhí)行所需時(shí)間長(zhǎng)度;D 表示任務(wù)的絕對(duì)截止期(D=TOA+W/2），即任務(wù)必須在該時(shí)刻前執(zhí)行完畢;TaskStep為任務(wù)自動(dòng)生成的周期即更新率;(R，α，β）為期望波束位置。任務(wù)調(diào)度模塊將根據(jù)雷達(dá)申請(qǐng)任務(wù)的相關(guān)屬性參數(shù)進(jìn)行綜合優(yōu)先級(jí)的計(jì)算，根據(jù)綜合優(yōu)先級(jí)大小在下一調(diào)度間隔分配任務(wù)序列。

1.2 綜合優(yōu)先級(jí)計(jì)算

運(yùn)用優(yōu)先級(jí)表的思想［5］及任務(wù)的空閑時(shí)間、截止期和工作方式優(yōu)先級(jí)3個(gè)特征參數(shù)進(jìn)行綜合優(yōu)先級(jí)的設(shè)計(jì)。

1.2.1 任務(wù)調(diào)度原則

考慮到任務(wù)的重要性和緊迫性，綜合優(yōu)先級(jí)設(shè)計(jì)首先需要遵循以下調(diào)度原則:

(1）工作方式優(yōu)先級(jí)越高、截止期越早及任務(wù)空閑時(shí)間越短的任務(wù)的綜合優(yōu)先級(jí)越高，任務(wù)就越早得到執(zhí)行;

(2）綜合優(yōu)先級(jí)值計(jì)算結(jié)果相同時(shí)采用FIFO的準(zhǔn)則進(jìn)行調(diào)整。

1.2.2 綜合優(yōu)先級(jí)計(jì)算算法

基于優(yōu)先級(jí)表的思想并按照任務(wù)調(diào)度原則設(shè)計(jì)任務(wù)綜合優(yōu)先級(jí)的計(jì)算算法，其具體實(shí)現(xiàn)步驟如下:

步驟1 將任務(wù)空閑時(shí)間和截止期序列按照升序排列，工作方式優(yōu)先級(jí)序列按照降序排列。各任務(wù)的3個(gè)參數(shù)在排序后的序列值為ti、di、wi;

步驟2 由圖1 優(yōu)先級(jí)表設(shè)計(jì)模式計(jì)算各任務(wù)的優(yōu)先級(jí)等級(jí)pi=wi+di+ti;

圖1 優(yōu)先級(jí)表設(shè)計(jì)

步驟3 優(yōu)先考慮工作方式優(yōu)先級(jí)和截止期參數(shù)，其重要程度相同且均大于空閑時(shí)間參數(shù)。綜合優(yōu)先級(jí)的計(jì)算公式如式(1）。圖2為綜合優(yōu)先級(jí)計(jì)算結(jié)果。

圖2 任務(wù)綜合優(yōu)先級(jí)

下面利用本節(jié)綜合優(yōu)先級(jí)的計(jì)算算法對(duì)雷達(dá)駐留任務(wù)進(jìn)行自適應(yīng)資源調(diào)度。

2 自適應(yīng)調(diào)度算法設(shè)計(jì)

對(duì)于多功能多任務(wù)相控陣?yán)走_(dá)系統(tǒng)，采用自適應(yīng)調(diào)度算法，雷達(dá)的資源利用率最高、資源管理調(diào)度效果最好。

2.1 自適應(yīng)調(diào)度算法

相控陣?yán)走_(dá)自適應(yīng)調(diào)度算法的設(shè)計(jì)需要遵循3 種原則:優(yōu)先級(jí)原則、時(shí)間利用原則和期望時(shí)間原則，然后對(duì)雷達(dá)申請(qǐng)任務(wù)進(jìn)行分析，可將滿足不同條件的任務(wù)送入執(zhí)行隊(duì)列、延遲隊(duì)列或刪除隊(duì)列?；诰C合優(yōu)先級(jí)的自適應(yīng)調(diào)度算法實(shí)現(xiàn)步驟如下:

(1）初始化調(diào)度程序，清空各類任務(wù)隊(duì)列;

(2）計(jì)算申請(qǐng)任務(wù)隊(duì)列中期望執(zhí)行時(shí)間在本調(diào)度間隔內(nèi)任務(wù)的綜合優(yōu)先級(jí);

(3）依次取綜合優(yōu)先級(jí)最大的任務(wù)，判斷其駐留時(shí)間是否滿足小于調(diào)度間隔的剩余時(shí)間，若滿足則根據(jù)該任務(wù)的可執(zhí)行時(shí)間范圍［te－W/2，te+W/2］分配任務(wù)實(shí)際執(zhí)行時(shí)刻tp，且任務(wù)在該時(shí)刻執(zhí)行不與已調(diào)度執(zhí)行的任務(wù)在時(shí)間上產(chǎn)生沖突，將任務(wù)送入執(zhí)行隊(duì)列;當(dāng)不滿足調(diào)度間隔剩余時(shí)間或任務(wù)可分配執(zhí)行時(shí)刻與其他已調(diào)度任務(wù)時(shí)間沖突則時(shí)轉(zhuǎn)入步驟4;

(4）判斷任務(wù)最晚可執(zhí)行時(shí)間是否滿足在下一調(diào)度間隔內(nèi)執(zhí)行，若滿足則將任務(wù)送入延遲隊(duì)列，否則送入刪除隊(duì)列;

(5）分析統(tǒng)計(jì)調(diào)度結(jié)果并計(jì)算評(píng)估指標(biāo)，調(diào)度分析結(jié)束。

2.2 改進(jìn)任務(wù)執(zhí)行時(shí)間分配算法

經(jīng)過(guò)仿真分析，發(fā)現(xiàn)基于綜合優(yōu)先級(jí)的自適應(yīng)調(diào)度算法若按照傳統(tǒng)的執(zhí)行時(shí)間順序分配方法(即將當(dāng)前仿真時(shí)刻設(shè)置為該任務(wù)的實(shí)際調(diào)度執(zhí)行時(shí)刻），其任務(wù)調(diào)度的平均時(shí)間偏移率較高。

平均時(shí)間偏移率體現(xiàn)了雷達(dá)任務(wù)調(diào)度執(zhí)行的及時(shí)性，反映了任務(wù)執(zhí)行效果的好壞，并且有些任務(wù)如通信、數(shù)據(jù)傳輸和干擾等對(duì)任務(wù)執(zhí)行的時(shí)序要求很高，較大的時(shí)間偏移會(huì)使任務(wù)執(zhí)行的效果很差甚至?xí)斐蓤?zhí)行失敗?；谏鲜龇治觯疚难芯苛烁倪M(jìn)的執(zhí)行時(shí)間分配算法。

改進(jìn)執(zhí)行時(shí)間分配算法:首先選擇綜合優(yōu)先級(jí)最高的任務(wù)進(jìn)行分配調(diào)度。若其到達(dá)時(shí)刻，即期望執(zhí)行時(shí)間未被占用，則將到達(dá)時(shí)刻分配給任務(wù)執(zhí)行;若到達(dá)時(shí)刻已被先前所調(diào)度任務(wù)占用，則查找距離其到達(dá)時(shí)刻最近的空余時(shí)間段分配實(shí)際執(zhí)行時(shí)間。改進(jìn)執(zhí)行時(shí)間分配算法流程如圖3所示。

3 仿真結(jié)果分析

基于以上研究對(duì)算法進(jìn)行了仿真。為有效衡量調(diào)度算法的性能，根據(jù)自適應(yīng)調(diào)度算法的設(shè)計(jì)原則，從任務(wù)調(diào)度成功率(SSR）、實(shí)現(xiàn)價(jià)值率(HVR）、時(shí)間利用率(TUR）和平均時(shí)間偏移率(ATSR）四項(xiàng)指標(biāo)［6-7］評(píng)估算法的調(diào)度性能，并將本文所提算法與傳統(tǒng)調(diào)度算法性能進(jìn)行仿真比較。

圖3 改進(jìn)執(zhí)行時(shí)間分配算法流程圖

3.1 基于綜合優(yōu)先級(jí)的自適應(yīng)調(diào)度仿真

假設(shè)仿真場(chǎng)景中有5 種典型雷達(dá)任務(wù):確認(rèn)任務(wù)、精密跟蹤、普通跟蹤、高優(yōu)先級(jí)搜索和低優(yōu)先級(jí)搜索，其具體參數(shù)如表1所示，其中調(diào)度間隔SI=50 ms。高優(yōu)先級(jí)、低優(yōu)先級(jí)搜索任務(wù)是按照固定的更新率周期性產(chǎn)生，確認(rèn)任務(wù)一部分以一定概率產(chǎn)生代表虛警，另一部分是當(dāng)搜索檢測(cè)到目標(biāo)時(shí)產(chǎn)生，檢測(cè)概率為0.9，虛警概率0.001。精密跟蹤、普通跟蹤任務(wù)是對(duì)目標(biāo)跟蹤起始后按其更新率周期性產(chǎn)生。雷達(dá)作用空域內(nèi)隨機(jī)產(chǎn)生50個(gè)目標(biāo)，對(duì)其中20個(gè)目標(biāo)進(jìn)行精密跟蹤，總調(diào)度仿真時(shí)間12 s。

采用基于綜合優(yōu)先級(jí)的自適應(yīng)調(diào)度算法進(jìn)行相控陣?yán)走_(dá)任務(wù)調(diào)度仿真，分析執(zhí)行時(shí)間順序分配方法與改進(jìn)執(zhí)行時(shí)間分配算法的仿真結(jié)果，得到各項(xiàng)評(píng)估性能指標(biāo)的比較結(jié)果如表2所示。雷達(dá)任務(wù)調(diào)度執(zhí)行序列結(jié)果如圖4所示，條形框表示各雷達(dá)任務(wù)，其高度為任務(wù)工作方式優(yōu)先級(jí)，寬度表示任務(wù)的駐留時(shí)間長(zhǎng)度。圖4(a）、(b）為兩種執(zhí)行時(shí)間分配方法未經(jīng)調(diào)度的雷達(dá)任務(wù)原始請(qǐng)求序列圖，可以看出兩種方法產(chǎn)生的原始任務(wù)請(qǐng)求序列均有較多的任務(wù)重疊，即不同任務(wù)的期望執(zhí)行時(shí)間產(chǎn)生沖突、搶占同一執(zhí)行時(shí)間段。經(jīng)過(guò)自適應(yīng)算法調(diào)度使發(fā)生沖突的雷達(dá)申請(qǐng)任務(wù)的實(shí)際執(zhí)行時(shí)刻相對(duì)期望執(zhí)行時(shí)刻提前或延遲，使它們得到成功調(diào)度，調(diào)度結(jié)果如圖4(c）、(d）所示。通過(guò)與原始請(qǐng)求序列比較可明顯看出，改進(jìn)算法任務(wù)實(shí)際執(zhí)行時(shí)間與其期望執(zhí)行時(shí)間更貼近，任務(wù)執(zhí)行的效果更好，且該調(diào)度間隔內(nèi)的任務(wù)基本在本調(diào)度間隔分配成功，而傳統(tǒng)方法有大量任務(wù)將被延遲到時(shí)間窗范圍內(nèi)的下幾個(gè)調(diào)度間隔中分配執(zhí)行。

表1 相控陣?yán)走_(dá)任務(wù)參數(shù)設(shè)置編號(hào)任務(wù)類型工作方式

調(diào)度仿真結(jié)束計(jì)算分析結(jié)果，各項(xiàng)評(píng)估性能指標(biāo)如表2所示。

表2 調(diào)度算法性能評(píng)估指標(biāo)

由表2 指標(biāo)結(jié)果可以看出，利用基于綜合優(yōu)先級(jí)的自適應(yīng)調(diào)度算法進(jìn)行調(diào)度時(shí)，不管運(yùn)用何種執(zhí)行時(shí)間分配算法都能達(dá)到較好的調(diào)度性能。而通過(guò)比較兩種不同執(zhí)行時(shí)間分配方法的評(píng)估指標(biāo)，得出如下結(jié)論:改進(jìn)算法在任務(wù)調(diào)度成功率、時(shí)間利用率及實(shí)現(xiàn)價(jià)值率等指標(biāo)損失很小的情況下平均時(shí)間偏移率大幅度降低。

3.2 算法性能比較

為驗(yàn)證本文算法性能的優(yōu)劣，在相同場(chǎng)景設(shè)置下精密跟蹤目標(biāo)數(shù)由2個(gè)增加到20個(gè);對(duì)本文算法和傳統(tǒng)EDF(截止期優(yōu)先）、HPF(高工作方式優(yōu)先級(jí)優(yōu)先）算法進(jìn)行仿真，計(jì)算算法性能評(píng)估指標(biāo)，做100 次蒙特卡洛實(shí)驗(yàn)結(jié)果如圖5。

由圖5 可見(jiàn)，本文算法任務(wù)調(diào)度的時(shí)間偏移率較傳統(tǒng)算法大大降低且任務(wù)調(diào)度成功率、時(shí)間利用率等指標(biāo)損失極小。因此，本文算法可有效保障多功能相控陣?yán)走_(dá)通信、干擾及數(shù)據(jù)傳輸?shù)榷喙δ芏嗳蝿?wù)的有效調(diào)度執(zhí)行，具有很好的調(diào)度性能。

圖4 雷達(dá)任務(wù)自適應(yīng)調(diào)度仿真結(jié)果

圖5 性能評(píng)估曲線比較

4 結(jié)束語(yǔ)

本文基于綜合優(yōu)先級(jí)的改進(jìn)執(zhí)行時(shí)間分配算法，在綜合優(yōu)先級(jí)計(jì)算算法研究的基礎(chǔ)上，提出相控陣?yán)走_(dá)自適應(yīng)調(diào)度的改進(jìn)執(zhí)行時(shí)間分配方法并進(jìn)行仿真。仿真結(jié)果表明，與傳統(tǒng)調(diào)度算法相比，本文算法在任務(wù)調(diào)度成功率、時(shí)間利用率等指標(biāo)損失極小的情況下有效降低了任務(wù)執(zhí)行的時(shí)間偏移率，可有效保障通信等多功能多任務(wù)的執(zhí)行效果、提高多功能相控陣?yán)走_(dá)系統(tǒng)的作戰(zhàn)效能。

［1］何金新，邱杰，王國(guó)宏.相控陣?yán)走_(dá)事件調(diào)度中的時(shí)間窗研究［J］.雷達(dá)科學(xué)與技術(shù)，2010，8(1）:80-86.

［2］李大鵬，何金新，胡云安.資源調(diào)度時(shí)間窗在垂直發(fā)射導(dǎo)彈導(dǎo)引上的應(yīng)用［J］.導(dǎo)彈與制導(dǎo)學(xué)報(bào)，2009，29(4）:85-87.

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

［4］王多強(qiáng)，魯劍鋒，李慶華.實(shí)時(shí)調(diào)度中基于多特征參數(shù)的任務(wù)優(yōu)先級(jí)設(shè)計(jì)方法［J］.計(jì)算機(jī)工程與科學(xué)，2008，30(1）:73-78.

［5］王永炎，王強(qiáng)，等.基于優(yōu)先級(jí)表的實(shí)時(shí)調(diào)度算法及其實(shí)現(xiàn)［J］.軟件學(xué)報(bào)，2004，15 (3）:360-370.

［6］趙洪濤，程婷，何子述.數(shù)字陣列雷達(dá)波束駐留調(diào)度間隔分析算法［J］.信息與電子工程，2011，9(1）:17-21.

［7］陳大偉.相控陣?yán)走_(dá)自適應(yīng)調(diào)度算法研究［D］.成都:電子科技大學(xué)，2011.