含時間窗的資源調(diào)度算法性能分析

萬 錚,孟慶鵬

(1. 中國船舶重工集團(tuán)公司第七二四研究所，南京 211153;2. 海軍駐南京地區(qū)雷達(dá)系統(tǒng)軍事代表室，南京 210003)

0 引 言

現(xiàn)代軍事戰(zhàn)爭中，雷達(dá)和電子戰(zhàn)有著重要的意義，電子偵察也是其中亟待研究的領(lǐng)域。資源調(diào)度策略的優(yōu)劣決定了雷達(dá)、電子戰(zhàn)系統(tǒng)性能的高下，影響著現(xiàn)代化戰(zhàn)爭的進(jìn)程。相控陣?yán)走_(dá)資源調(diào)度的主要算法有靜態(tài)優(yōu)先級的速率單調(diào)調(diào)度算法、時限單調(diào)調(diào)度算法、動態(tài)優(yōu)先級的最早截止期優(yōu)先(EDF)調(diào)度算法、最小裕度優(yōu)先調(diào)度算法等[1-2]。這些常規(guī)的資源調(diào)度策略雷達(dá)的系統(tǒng)資源無法充分利用，重點目標(biāo)和任務(wù)無法有效實現(xiàn)。因此，急需一種與目標(biāo)優(yōu)先級和時間利用率密切相關(guān)的調(diào)度策略優(yōu)化系統(tǒng)性能。

1 強(qiáng)實時系統(tǒng)資源調(diào)度策略

現(xiàn)代電子偵察系統(tǒng)的強(qiáng)實時資源綜合調(diào)度問題，其核心有兩點：一是系統(tǒng)各項公共資源的利用效能問題，需要依據(jù)系統(tǒng)要求操作的不同功能和任務(wù)，調(diào)配相應(yīng)的硬件資源，通過資源合理調(diào)度實現(xiàn)整體性能提升，增強(qiáng)軟硬件資源利用率，使得任務(wù)可以高效完成并有一定的均衡性；二是多樣化任務(wù)服務(wù)可靠性問題，即在系統(tǒng)資源有限的前提下，如何確保任務(wù)安全、可靠、持續(xù)、穩(wěn)定地完成，維持整個系統(tǒng)的穩(wěn)定運轉(zhuǎn)[3]。

對于現(xiàn)今越來越重要的軟件化系統(tǒng)而言，資源調(diào)度軟件需要考慮系統(tǒng)重組的效率。系統(tǒng)的軟件可重組包括了軟件功能新構(gòu)和軟件故障屏蔽重構(gòu)。

軟件功能新構(gòu)是軟件化系統(tǒng)需要執(zhí)行一項新任務(wù)時進(jìn)行軟件配置到部件運行退出的一系列操作，其流程可用圖1表示。

圖1 軟件功能新構(gòu)流程圖

系統(tǒng)決定執(zhí)行功能新構(gòu)時，首先根據(jù)決策下達(dá)部件配置指令，各部件根據(jù)執(zhí)行功能任務(wù)的需求控制相互間數(shù)據(jù)流向和芯片架構(gòu)。配置完成后將各部件啟動，并對下載傳輸?shù)娜蝿?wù)功能完成初始化。在部件等待時清理過往數(shù)據(jù)，等待接收新的信息。之后根據(jù)決策執(zhí)行各部件功能算法，將得到的結(jié)果儲存?zhèn)鬏敚蠼Y(jié)束功能退出等待下一步指令。

軟件故障重組流程則是當(dāng)系統(tǒng)面對功能更新、部件故障、任務(wù)更改等需求時執(zhí)行的重組操作，其具體流程如圖2所示。

監(jiān)測單元實時監(jiān)控各部件的故障信息，接收到部件故障情報通過總線上報故障，系統(tǒng)將各個部件的監(jiān)測單元情報信息收集后進(jìn)行判斷。根據(jù)各部件信息計算重組策略。將決策下達(dá)至各個部件，部件根據(jù)決策重啟模塊，清空信息等待新的數(shù)據(jù)流傳入，回歸正常運行。

系統(tǒng)的硬件平臺是資源調(diào)度中另一個需要提前考慮的問題。軟件化系統(tǒng)的硬件平臺需要很強(qiáng)的通用性，由中心處理機(jī)控制著包括數(shù)字信道化、數(shù)字多波束形成到輻射源識別在內(nèi)的數(shù)字信號處理。天線陣列及前端模擬量處理應(yīng)在規(guī)范協(xié)議下實現(xiàn)可重構(gòu)[4]。

因為電子偵察系統(tǒng)超寬帶工作的特性，所以有著較高的數(shù)據(jù)傳輸速率。這就對各部分硬件的處理速率和數(shù)據(jù)吞吐量有著極高的要求，同時也要考慮成本的控制和實現(xiàn)難易的問題。圖3為軟件化系統(tǒng)硬件平臺的基本組成框圖。

利用光電轉(zhuǎn)換模塊進(jìn)行數(shù)字信號傳輸適合于傳輸數(shù)據(jù)量大和易被外界噪聲干擾的背景。集成方便、軟件化程度高且易于維護(hù)和升級的高性能通用計算機(jī)可以實現(xiàn)軟件控制重組等多種操控。

為適應(yīng)寬頻域、全空域處理帶來的海量數(shù)據(jù)，基于PCI-E和Rapid I/O總線的快速傳輸網(wǎng)絡(luò)可以減少處理機(jī)的性能限制。結(jié)合高速光纖傳輸網(wǎng)絡(luò)可以基本滿足軟件化系統(tǒng)總線高帶寬、低延遲支持并行處理、擴(kuò)展自由靈活的要求[5]。

基于寬帶相控陣體制的多功能軟件化系統(tǒng)的任務(wù)調(diào)度可根據(jù)系統(tǒng)需執(zhí)行的不同任務(wù)和功能選擇不同的調(diào)度策略。常用的調(diào)度策略有固定模板、多模板、部分模板和自適應(yīng)調(diào)度策，調(diào)度的性能隨著調(diào)度策略復(fù)雜度的提升而增加。

(1) 固定模板法

這是最簡單直接的一種調(diào)度策略。在一個調(diào)度間隔內(nèi)固定分配一系列固定的電子偵察任務(wù)組合，分別執(zhí)行搜索確認(rèn)跟蹤等任務(wù)。系統(tǒng)按此流程固定的調(diào)度硬件進(jìn)行序列任務(wù)，如圖4所示。這種調(diào)度策略的設(shè)計結(jié)構(gòu)簡單，需求系統(tǒng)資源較少，也不需要實時進(jìn)行任務(wù)排序。但是，由于這種算法的固定性限制，導(dǎo)致這種策略僅適用于一些特殊的任務(wù)目標(biāo)，缺乏普遍性和靈活性，無法自動根據(jù)任務(wù)進(jìn)行調(diào)節(jié)，不適合多功能的電子偵察系統(tǒng)。

(2) 多模板法

這是由固定模板法衍生而來的一種調(diào)度策略。它擺脫了固定性的局限，增強(qiáng)了策略的多功能適應(yīng)性。多模板法提前根據(jù)面對的環(huán)境設(shè)計了多個固定模板，在調(diào)度時根據(jù)一定要求尋找其中最適合的模板，其流程如圖5所示。這種調(diào)度策略適用在對目標(biāo)具有一定先驗知識的情況下，但若面對的模板數(shù)過多則會耗費大量的計算機(jī)硬件資源進(jìn)行搜尋模板的計算，難以滿足多功能強(qiáng)實時調(diào)度的要求。

(3) 部分模板法

該策略在調(diào)度間隔中事先設(shè)計了部分電子偵察系統(tǒng)需要完成的任務(wù)以保證一些功能的最小程度執(zhí)行，而對調(diào)度間隔中的其余時間則根據(jù)其他任務(wù)的優(yōu)先級和約束條件進(jìn)行調(diào)度安排，如圖6所示。

這種調(diào)度策略相比前兩種在系統(tǒng)資源利用率上有較大提升，且對不同的電磁環(huán)境有著較強(qiáng)的自適應(yīng)能力，但在設(shè)計和分析策略時較為困難，在多任務(wù)多功能強(qiáng)實時要求下仍有缺陷。

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

該策略根據(jù)不同工作方式優(yōu)先級條件，在電子偵察系統(tǒng)硬件約束范圍內(nèi)實時響應(yīng)各種任務(wù)功能的駐留請求時間、能力和計算機(jī)資源，為每一個調(diào)度間隔選擇最佳的實時任務(wù)調(diào)度序列。圖7所示是這種調(diào)度策略的框圖。這種調(diào)度策略需要與動態(tài)的電子偵察環(huán)境相匹配，要符合系統(tǒng)設(shè)計條件，在多功能、多任務(wù)、強(qiáng)實時需求下的電子偵察系統(tǒng)中具有靈活調(diào)度、可自適應(yīng)、資源利用率高等優(yōu)點。

2 綜合優(yōu)先級自適應(yīng)算法

各類資源調(diào)度算法在處理不同任務(wù)數(shù)情況下的資源利用率和調(diào)度成功率有明顯差異。在任務(wù)數(shù)較少時，系統(tǒng)調(diào)度產(chǎn)生的資源沖突少，各種調(diào)度算法都能順利完成調(diào)度。但是，當(dāng)同時執(zhí)行多種任務(wù)時，資源競爭加劇，只有擁有自適應(yīng)能力的調(diào)度算法可以保持對高優(yōu)先級目標(biāo)的精密跟蹤。在系統(tǒng)資源趨近飽和時，自適應(yīng)調(diào)度策略可以根據(jù)當(dāng)前任務(wù)及資源分配合理提高資源和時間利用率，高效準(zhǔn)確地完成各項任務(wù)，并能對系統(tǒng)資源做出合理配置。

因此，結(jié)合目標(biāo)威脅度設(shè)計一種優(yōu)先級自適應(yīng)調(diào)度算法對系統(tǒng)的資源調(diào)度進(jìn)行優(yōu)化。設(shè)計時的準(zhǔn)則為：

(1) 在同一時間段內(nèi)申請執(zhí)行的任務(wù)，優(yōu)先調(diào)度綜合優(yōu)先級更高的。當(dāng)系統(tǒng)硬件資源不足時，首先配置資源給綜合優(yōu)先級高的任務(wù)，優(yōu)先級較低的任務(wù)可根據(jù)需要進(jìn)行延遲，任務(wù)沖突時優(yōu)先保證高級別任務(wù)執(zhí)行。

(2) 在系統(tǒng)約束條件下按時間利用率高的方式配置系統(tǒng)公共資源(如式(1)所示)，使調(diào)度間隔內(nèi)執(zhí)行的任務(wù)數(shù)量最多，空閑時間最少，任務(wù)執(zhí)行時間總和趨近于調(diào)度間隔。

(1)

系統(tǒng)調(diào)度得益的評判標(biāo)準(zhǔn)可以由以下幾個指標(biāo)給出：

(1) 任務(wù)調(diào)度成功率(SSR)(如式(2)所示)是調(diào)度成功的任務(wù)數(shù)與申請調(diào)度的總?cè)蝿?wù)數(shù)之比，成功率越高則說明調(diào)度策略性能越好。

(2)

(2) 實現(xiàn)價值率(HVR)(如式(3)所示)是成功調(diào)度任務(wù)的綜合優(yōu)先級之和與申請調(diào)度任務(wù)的綜合優(yōu)先級之和的比值，實現(xiàn)價值率越高說明高優(yōu)先級任務(wù)成功調(diào)度越多，優(yōu)先級調(diào)度算法越可靠。

(3)

(3) 時間利用率(TUR)(如式(4)所示)表示成功調(diào)度任務(wù)的調(diào)度時間與總調(diào)度時間之比，時間利用率越高則電偵系統(tǒng)資源有效調(diào)度效率越高，調(diào)度策略性能越好。

(4)

基于數(shù)字相控陣體制的電子偵察系統(tǒng)利用數(shù)字相控陣多自由度的特點可以執(zhí)行多種體制功能，針對不同優(yōu)先級的目標(biāo)也有相應(yīng)的應(yīng)對策略。一般情況下，系統(tǒng)在低優(yōu)先級搜索中按固定規(guī)律對全空域、寬頻段進(jìn)行常規(guī)搜索，在高優(yōu)先級搜索中對特定的空域進(jìn)行精細(xì)搜索，在截獲目標(biāo)后通過系統(tǒng)的信號、信息處理功能對目標(biāo)識別，根據(jù)目標(biāo)種類和戰(zhàn)術(shù)需求進(jìn)行編批、跟蹤。對于威脅程度不高的普通目標(biāo)，系統(tǒng)可以利用較少的資源進(jìn)行更新率較低的普通跟蹤定位。對威脅程度高的目標(biāo)以較大更新率進(jìn)行精密跟蹤。

偵察系統(tǒng)根據(jù)目標(biāo)的威脅程度進(jìn)行優(yōu)先級判定，判定截獲信號為高威脅的目標(biāo)后，會對其進(jìn)行更高優(yōu)先級的跟蹤、顯示；判定為低威脅目標(biāo)后，會對其進(jìn)行較低優(yōu)先級的警戒跟蹤。截獲目標(biāo)的威脅度是由目標(biāo)自身特性決定的，一般以截獲信號的脈沖寬度(PW)和脈沖重復(fù)頻率(PRF)作為判決指標(biāo)[6]。低重頻、寬脈沖雷達(dá)信號測向距離遠(yuǎn)，但需長時間積累，測速能力和抗雜波能力弱，一般應(yīng)用在遠(yuǎn)程搜索警戒雷達(dá)上，對我方電偵系統(tǒng)威脅度較小。高重頻、窄脈沖雷達(dá)信號測向、測速精確迅速，一般設(shè)計為機(jī)載雷達(dá)、導(dǎo)彈制導(dǎo)等近目標(biāo)快速作戰(zhàn)裝備，對我方威脅程度高，應(yīng)調(diào)度資源對其優(yōu)先跟蹤定位。

設(shè)計的算法流程如圖8所示。首先初始化調(diào)度程序，查詢調(diào)度申請序列，計算所有申請任務(wù)的綜合優(yōu)先級并排序，然后依次執(zhí)行調(diào)度，分析調(diào)度結(jié)果。

3 時間窗優(yōu)化策略

現(xiàn)代相控陣系統(tǒng)采用了時間窗優(yōu)化自適應(yīng)算法。利用時間窗對存在沖突的任務(wù)進(jìn)行調(diào)整調(diào)度，從而提高調(diào)度效率和時間利用率。若申請調(diào)度的任務(wù)在一定時間窗內(nèi)仍未被調(diào)度執(zhí)行，則判斷此任務(wù)請求失效，送入刪除隊列處理。利用時間窗調(diào)整優(yōu)先級低的任務(wù)占用的調(diào)度時間，提高實現(xiàn)價值率[7]。

為了驗證有時間窗的綜合優(yōu)先級自適應(yīng)調(diào)度算法的性能，設(shè)計了仿真試驗，調(diào)度間隔為50 ms，高、低優(yōu)先級任務(wù)在一定虛警概率下按固定頻率產(chǎn)生。設(shè)計的虛警概率為0.001，檢測概率0.9，在隨機(jī)產(chǎn)生的50個目標(biāo)中有20個需要精確跟蹤。將有時間窗和無時間窗的自適應(yīng)調(diào)度算法結(jié)果與傳統(tǒng)的平均分配型固定模板法作對比得到表1所示?？梢钥吹?，采用優(yōu)先級自適應(yīng)算法可以在各項指標(biāo)中獲得更優(yōu)的結(jié)果，有時間窗的調(diào)度方法在實現(xiàn)價值率上比無時間窗算法有明顯提升。

表1 時間窗對資源調(diào)度算法性能影響分析

4 結(jié)束語

在電子偵察系統(tǒng)作戰(zhàn)管理中，綜合資源調(diào)度系統(tǒng)是任務(wù)編排的決策部件。本文提出以目標(biāo)綜合優(yōu)先級為核心，建立含有時間窗的自適應(yīng)調(diào)度算法。仿真結(jié)果表明，該算法在任務(wù)安排上合理、有效，具有較高的調(diào)度成功率、時間利用率和實現(xiàn)價值率。