基于自適應(yīng)調(diào)度間隔的雷達(dá)事件調(diào)度算法

譚賢四 曲智國 王 紅

(1. 空軍預(yù)警學(xué)院， 湖北武漢 430019； 2. 95174部隊(duì)， 湖北武漢 430000)

0 引言

相控陣?yán)走_(dá)具有波束捷變、天線波束快速掃描、空間功率合成與多波束形成等能力[1]，能夠完成多目標(biāo)跟蹤、多區(qū)域搜索等復(fù)雜任務(wù)，因此在現(xiàn)代戰(zhàn)爭中得到廣泛運(yùn)用。但同時(shí)大型相控陣?yán)走_(dá)跟蹤目標(biāo)數(shù)量多、監(jiān)視區(qū)域大，不同任務(wù)存在相互沖突的可能，因此必須選擇靈活有效的調(diào)度策略發(fā)揮相控陣?yán)走_(dá)性能、完成作戰(zhàn)任務(wù)[2]。

目前相控陣?yán)走_(dá)調(diào)度策略主要有固定模板、多模板、部分模板和自適應(yīng)調(diào)度策略，其中模板類策略適用環(huán)境單一，調(diào)度效率低下，難以適應(yīng)現(xiàn)代戰(zhàn)爭需要；自適應(yīng)調(diào)度策略由于具有資源利用率高、環(huán)境適應(yīng)力強(qiáng)、可開發(fā)性大等優(yōu)點(diǎn)，在相控陣?yán)走_(dá)事件調(diào)度問題中得到廣泛應(yīng)用[3]。

相控陣?yán)走_(dá)事件調(diào)度問題的核心內(nèi)容在于調(diào)度算法設(shè)計(jì)，趙宇等[4]在文獻(xiàn)[5]基礎(chǔ)上提出基于二次規(guī)劃的調(diào)度算法，孫銘才等[6]提出基于改進(jìn)時(shí)間指針的調(diào)度算法。近年來，隨著智能優(yōu)化算法(如遺傳算法)的發(fā)展與計(jì)算機(jī)硬件性能的提高，不少學(xué)者提出利用智能優(yōu)化算法對雷達(dá)事件進(jìn)行調(diào)度，Charlish等[7]利用連續(xù)雙拍賣算法，張浩為等[8]利用混合遺傳-粒子群算法，Abdelaziz[9]利用禁忌搜索算法，有效提高算法的全局尋優(yōu)能力與可開發(fā)性。

但在這些算法中，調(diào)度間隔通常都被設(shè)置為一定值，基于固定調(diào)度間隔的調(diào)度算法在調(diào)度過程中難以有效利用雷達(dá)資源，實(shí)現(xiàn)最佳調(diào)度效果；這是由于當(dāng)調(diào)度間隔設(shè)置過大時(shí)無法滿足系統(tǒng)對某些任務(wù)的頻率要求；當(dāng)調(diào)度間隔設(shè)置過小時(shí)會(huì)增加“時(shí)間碎片”形成可能性，降低時(shí)間資源利用率[10]。針對這個(gè)問題，本文提出基于自適應(yīng)調(diào)度間隔的調(diào)度算法：設(shè)置一時(shí)間指針，調(diào)取該指針下所有可執(zhí)行事件，依次計(jì)算這些事件該時(shí)刻收益并選取收益最高事件執(zhí)行；遞推該指針直至該調(diào)度間隔內(nèi)無法執(zhí)行任何事件；提前結(jié)束該調(diào)度間隔并將該間隔剩余資源“傳遞”至下一調(diào)度間隔；重復(fù)上述步驟直至調(diào)度結(jié)束。仿真實(shí)驗(yàn)表明，與基于固定調(diào)度間隔的調(diào)度算法相比，基于自適應(yīng)調(diào)度間隔的調(diào)度算法能夠有效減少“時(shí)間碎片”的形成，提高調(diào)度成功率與時(shí)間資源利用率。

1 事件調(diào)度基本問題

1.1 調(diào)度意義

雷達(dá)為穩(wěn)定跟蹤目標(biāo)，必須定期/不定期對目標(biāo)進(jìn)行回訪，每次回訪將消耗一定量的雷達(dá)資源，以圖1(a)為例。圖中每一白色方塊表征為一次雷達(dá)“事件”。

當(dāng)雷達(dá)同時(shí)需要跟蹤若干批目標(biāo)時(shí)，不同事件彼此間存在相互沖突的可能，如圖1(b) 所示，圖中黑色方塊與白色方塊存在重疊，表明雷達(dá)在跟蹤目標(biāo)A的過程中將影響對目標(biāo)B的跟蹤，因此必須通過合理有效的調(diào)度手段對沖突事件進(jìn)行調(diào)度(圖1(c))，以充分利用雷達(dá)資源，發(fā)揮兵器效能。

(a) 跟蹤單批目標(biāo)時(shí)

(b) 跟蹤多批目標(biāo)調(diào)度前

1.2 調(diào)度流程

當(dāng)相控陣?yán)走_(dá)在接受到事件請求后將事件請求序列送入雷達(dá)資源管理系統(tǒng)(Radar Resource Management，RRM)生成待調(diào)度序列，RRM提取下一調(diào)度間隔內(nèi)所有事件請求并根據(jù)雷達(dá)硬件條件與戰(zhàn)場環(huán)境需求等因素計(jì)算事件屬性；計(jì)算完成后事件請求被送入調(diào)度模塊進(jìn)行調(diào)度并生成執(zhí)行、延遲、刪除序列，其中執(zhí)行序列送入發(fā)射機(jī)執(zhí)行，延遲序列送入下一調(diào)度將進(jìn)行再調(diào)度，刪除序列不予執(zhí)行，其具體過程如圖2所示。

圖2 調(diào)度流程示意圖

1.3 事件請求模型

相控陣?yán)走_(dá)事件請求模型應(yīng)包括事件綜合優(yōu)先級、發(fā)射功率、駐留時(shí)長、時(shí)間窗大小、請求執(zhí)行時(shí)刻等信息，可通過以下模型來描述：

TaskRequire={PS,Pw,Tτ,te,TW}

(1)

式中：PS為事件綜合優(yōu)先級，由目標(biāo)類型、速度、高度等信息與雷達(dá)資源利用情況共同決定；Pw為發(fā)射功率，由雷達(dá)能量資源約束決定；te為最佳執(zhí)行時(shí)刻，由雷達(dá)上次照射執(zhí)行時(shí)刻與跟蹤間隔共同決定；TW為時(shí)間窗大小[11]，由目標(biāo)運(yùn)動(dòng)狀態(tài)與雷達(dá)波門大小共同決定；Tτ表示事件駐留時(shí)長，可細(xì)分為發(fā)射脈沖時(shí)長、等待階段時(shí)長、接受脈沖時(shí)長，對于采用非搶占式EDF算法來說，事件一旦開始無法停止，即Tτ內(nèi)時(shí)間無法執(zhí)行其他事件，對于采用交錯(cuò)脈沖技術(shù)雷達(dá)來說，Tτ內(nèi)事件等待階段可以執(zhí)行其他事件。

1.4 調(diào)度數(shù)學(xué)模型

相控陣?yán)走_(dá)事件調(diào)度問題實(shí)質(zhì)上可歸為調(diào)度中作業(yè)車間調(diào)度問題(JSP job scheduling problem)。需要考慮多參數(shù)優(yōu)化與多條件約束。

1) 約束條件

相控陣?yán)走_(dá)沒完成一次事件，都將消耗一定量的雷達(dá)資源，而雷達(dá)系統(tǒng)所擁有的資源是有限的，因此必須通過限制條件對雷達(dá)資源加以約束；雷達(dá)資源主要體現(xiàn)為時(shí)間資源、能力資源、硬件條件資源和計(jì)算機(jī)資源四種。

4種資源約束中由于時(shí)間軸固定，因此時(shí)間資源約束不能調(diào)節(jié)，屬于“剛性約束”；能量資源約束可以通過加大輸入電流、更換扇熱設(shè)備等方法調(diào)節(jié)，屬于“彈性約束”；后兩種約束條件難以用數(shù)學(xué)模型表述。因此本文重點(diǎn)考慮時(shí)間資源約束。

將4種約束條件分別記為h1,h2,h3,h4。

2) 評價(jià)指標(biāo)

為評價(jià)調(diào)度算法的優(yōu)劣，本文選取實(shí)現(xiàn)價(jià)值率(HVR hit value rate)與時(shí)間資源利用率(TUR time utilization rate)作為評價(jià)指標(biāo)[12]，其中HVR與TUR計(jì)算式分別為

(2)

式中，Ne為調(diào)度成功事件數(shù)目，Nt為參與調(diào)度事件總數(shù)。

(3)

根據(jù)約束條件與目標(biāo)函數(shù)可得相控陣?yán)走_(dá)事件調(diào)度問題數(shù)學(xué)模型為

(4)

2 基于自適應(yīng)調(diào)度間隔的調(diào)度算法

2.1 調(diào)度間隔影響

由上文可知，事件調(diào)度模塊中調(diào)度算法僅對本間隔內(nèi)待調(diào)度事件或是上一間隔內(nèi)延遲事件進(jìn)行調(diào)度，因此調(diào)度間隔選取對算法性能有著重要影響，它決定了雷達(dá)控制回路子程序執(zhí)行頻率，也決定了支持該間隔內(nèi)工作方式處理能力的極限。顯然調(diào)度間隔不能選取太長，過長的調(diào)度間隔無法滿足系統(tǒng)回路相應(yīng)時(shí)間要求；由文獻(xiàn)[13]可知，調(diào)度間隔時(shí)長最長可等于系統(tǒng)中最短的伺服回路閉合時(shí)間的1/4，即

(5)

式中，TSI為調(diào)度間隔時(shí)長，Thmin為回路最小相應(yīng)時(shí)間。

圖3 調(diào)度效果示意圖

但調(diào)度間隔也不能過短，過短的調(diào)度間隔會(huì)增加“時(shí)間碎片”形成可能性，降低時(shí)間資源利用率。以圖3為例，圖中將時(shí)間段[0,100 ms]劃分為兩個(gè)調(diào)度間隔，其中第一個(gè)間隔內(nèi)有3批待調(diào)度事件，第二個(gè)間隔內(nèi)有2批待調(diào)度事件，每批事件駐留時(shí)長均為20 ms；利用傳統(tǒng)基于固定間隔的調(diào)度算法進(jìn)行調(diào)度，即將每個(gè)調(diào)度間隔時(shí)長設(shè)置為50 ms(策略A)，則第一個(gè)調(diào)度間隔內(nèi)可執(zhí)行2批事件，剩余10 ms時(shí)間資源無法執(zhí)行第三批事件，因此事件3被延遲到下一調(diào)度間隔執(zhí)行，但下一間隔內(nèi)依然只能執(zhí)行2批事件，再次形成10 ms“時(shí)間碎片”；可見，基于固定間隔的調(diào)度算法難以充分利用時(shí)間資源，調(diào)度性能較為低下。此時(shí)若將時(shí)間段[0,100 ms]僅劃分為一個(gè)調(diào)度間隔(策略B)，則5批事件都能得到調(diào)度，SSR與TUR均得到顯著提高，但此時(shí)將面臨超出系統(tǒng)最短伺服回路閉合時(shí)間風(fēng)險(xiǎn)。利用基于自適應(yīng)調(diào)度間隔的調(diào)度算法將時(shí)間段[0,100 ms]劃分為40 ms和60 ms兩個(gè)調(diào)度間隔(策略C)，則5批事件都能得到調(diào)度，SSR和TUR與策略B均相同，同時(shí)超出系統(tǒng)最短伺服回路閉合時(shí)間風(fēng)險(xiǎn)大大降低。

2.2 算法步驟

由上文思路可知，基于自適應(yīng)調(diào)度間隔的調(diào)度算法應(yīng)根據(jù)該間隔內(nèi)事件多少靈活調(diào)節(jié)調(diào)度間隔時(shí)長，當(dāng)本間隔內(nèi)剩余資源無法調(diào)度更多事件時(shí)應(yīng)提前結(jié)束該間隔，將剩余資源延遲至下一調(diào)度間隔內(nèi)，避免形成“時(shí)間碎片”，提高雷達(dá)資源利用率。其具體步驟如圖4所示。

水資源管理水平得到提高。國家最嚴(yán)格水資源管理制度試點(diǎn)建設(shè)通過水利部中期評估。水資源論證納入政府投資項(xiàng)目聯(lián)合審批，規(guī)模以上地下水用戶全部實(shí)現(xiàn)水量在線監(jiān)測。推行再生水、淡化海水、生態(tài)水和地下水“三增一減”管理，年利用再生水1.4億t、淡化海水3 000萬t，中心城區(qū)年生態(tài)補(bǔ)水1.73億m3，壓采深層地下水1 200萬m3。順利通過國家節(jié)水型城市復(fù)查，完成水功能區(qū)跨界斷面核定，全市所有水功能區(qū)納入水質(zhì)監(jiān)測。全年用水總量控制在24億m3以內(nèi)，萬元GDP用水量降至18 m3，萬元工業(yè)增加值用水量降至8.3 m3，重要江河湖泊水功能區(qū)達(dá)標(biāo)率提高到21%。

圖4 調(diào)度流程

步驟1 初始化，調(diào)取事件請求序列與延遲序列。

步驟2 置時(shí)間指針t=0。

步驟3 提取滿足t∈[te-Tw,te+Tw]所有事件，假設(shè)共計(jì)I批;若I=0，令t=t+1，進(jìn)入步驟4；若I≠0，進(jìn)入步驟5。

步驟4 判斷t≥TSI，若為真，進(jìn)入步驟8；反之回到步驟3。

步驟5 計(jì)算I批事件綜合優(yōu)先級，并按綜合優(yōu)先級對事件排序，置i=1。

步驟7 判斷i=I，若為真，令當(dāng)前調(diào)度間隔時(shí)長TSI=t；反之令i=i+1，返回步驟6。

步驟8 在待調(diào)度事件序列中剔除執(zhí)行序列。

步驟9 判斷剩余事件是否滿足下個(gè)調(diào)度間隔，若是，寫入延遲序列；反之寫入刪除序列。

步驟10 結(jié)束調(diào)度。

3 仿真分析

3.1 基于固定場景的調(diào)度效果比較

1) 事件請求生成

按照類別可將相控陣?yán)走_(dá)事件分為低優(yōu)先級搜索(LS)、高優(yōu)先級搜索(HS)、普通跟蹤(NT)、精度跟蹤(PT)、高精度跟蹤(HPT)和跟蹤確認(rèn)(TC)事件六種[14]，6種事件綜合優(yōu)先級分別設(shè)置為1～6，不同類類別事件參數(shù)如表1所示，事件期望執(zhí)行時(shí)間te～U(0 ms,1 000 ms)，此處U(a,b)表示[a,b]范圍內(nèi)均勻分布，生成事件請求如圖5所示。

表1 事件請求參數(shù)

圖5 事件請求

由圖5可見，該想定場景下不同事件之間存在大量重復(fù)，時(shí)間利用率高達(dá)169%，因此必須利用某種調(diào)度策略對這些事件請求進(jìn)行調(diào)度。

2) 調(diào)度結(jié)果比較

表2 調(diào)度性能比較

(a) 基于固定調(diào)度間隔(25 ms)

(b) 基于固定調(diào)度間隔(50 ms)

(c) 基于固定調(diào)度間隔(100 ms)

(d) 基于固定調(diào)度間隔(200 ms)

(e) 基于自適應(yīng)調(diào)度間隔(50 ms)

(f) 基于自適應(yīng)調(diào)度間隔(200 ms)圖6 調(diào)度結(jié)果

基于自適應(yīng)調(diào)度間隔的調(diào)度算法中各間隔時(shí)長如圖7所示(以max(TSI)=50 ms為例)，由圖中可以看見在時(shí)間段[0,1 000 ms]內(nèi)共存在有23個(gè)調(diào)度間隔，多于傳統(tǒng)算法的20個(gè)，但每個(gè)間隔均小于最大時(shí)長max(TSI)，杜絕超出系統(tǒng)最短伺服回路閉合時(shí)間的風(fēng)險(xiǎn)。

圖7 調(diào)度間隔時(shí)長

3.2 基于蒙特卡洛仿真的調(diào)度效果比較

(a) HVR比較

(b) TUR比較圖8 算法性能比較

由圖8可以看出，隨著參與調(diào)度事件數(shù)目增多，兩種算法HVR與TUR分別呈下降與上升趨勢。在基于固定調(diào)度間隔的調(diào)度算法中隨著調(diào)度間隔時(shí)長TSI增加，HVR與TUR均有所提高，但均小于基于自適應(yīng)調(diào)度間隔的調(diào)度算法。

4 結(jié)束語

針對相控陣?yán)走_(dá)事件調(diào)度問題中傳統(tǒng)算法將調(diào)度間隔設(shè)置為固定值，造成實(shí)現(xiàn)價(jià)值率不高、雷達(dá)資源利用率過低的問題，本文提出了一種自適應(yīng)調(diào)度間隔的調(diào)度算法，該算法能夠根據(jù)雷達(dá)資源利用情況自適應(yīng)調(diào)節(jié)調(diào)度間隔大小，充分利用雷達(dá)資源，進(jìn)而顯著提升調(diào)度性能。

但本文僅就啟發(fā)式算法中調(diào)度間隔如何自適應(yīng)變化這個(gè)問題進(jìn)行了討論，在其他算法尤其是智能優(yōu)化算法(例如遺傳算法)中調(diào)度間隔如何自適應(yīng)變化有待進(jìn)一步研究。