宋偉強(qiáng) 陳 春 高 劍

(西安電子工程研究所 西安 710100)

基于緊時(shí)間約束的多功能相控陣?yán)走_(dá)任務(wù)調(diào)度

宋偉強(qiáng) 陳 春 高 劍

(西安電子工程研究所 西安 710100)

本文闡述了雷達(dá)任務(wù)的調(diào)度問題，定義了兩類任務(wù)，分為緊時(shí)間約束(Hard Time Constraint，HTC)任務(wù)和松時(shí)間約束(Soft Time Constraint，STC)任務(wù)，緊時(shí)間約束任務(wù)不能延遲執(zhí)行超過一個(gè)固定變量α，而松時(shí)間約束任務(wù)可以在任意時(shí)刻被執(zhí)行。為解決上述問題，本文詳細(xì)介紹了一種算法，首先分別建立了HTC任務(wù)序列和STC任務(wù)序列，接下來針對(duì)兩類任務(wù)序列被調(diào)度的順序問題提出了一種選擇原則。

仿真；調(diào)度；相控陣?yán)走_(dá)

0 引言

現(xiàn)代雷達(dá)多使用相控陣天線，它可以瞬間控制和調(diào)整雷達(dá)波束。這種靈活性使雷達(dá)能同時(shí)實(shí)現(xiàn)多種功能，如導(dǎo)彈制導(dǎo)，跟蹤和監(jiān)視，其中每個(gè)功能都進(jìn)行了大量的雷達(dá)任務(wù)。多功能的實(shí)現(xiàn)需要雷達(dá)資源管理的研究，需考慮雷達(dá)任務(wù)的調(diào)度和優(yōu)先順序。在過載期間當(dāng)雷達(dá)沒有足夠的時(shí)間預(yù)算去調(diào)度所有雷達(dá)任務(wù)時(shí)，雷達(dá)資源管理顯得特別重要。在這種情況下，雷達(dá)調(diào)度必須決定哪些任務(wù)必須執(zhí)行而哪些任務(wù)必須被拒絕,這類問題被稱為雷達(dá)任務(wù)調(diào)度問題，它是雷達(dá)資源管理的子問題[1]。此外，這類問題決定了雷達(dá)任務(wù)調(diào)度的起始時(shí)刻和執(zhí)行順序。

本文將重點(diǎn)研究在考慮緊時(shí)間約束和優(yōu)先級(jí)情況下的雷達(dá)任務(wù)調(diào)度問題。系統(tǒng)的物理性(例如波形計(jì)算和信號(hào)處理)不予考慮。為了解決這類問題，首先分別建立了HTC任務(wù)序列和STC任務(wù)序列，接下來針對(duì)兩類任務(wù)序列被調(diào)度的順序問題提出了一種算法。

1 緊時(shí)間約束和優(yōu)先級(jí)的調(diào)度問題

對(duì)于多功能雷達(dá)系統(tǒng)，有幾種類型的任務(wù)要處理(圖1)[2]。其中一些是定期的：監(jiān)視，跟蹤，武器制導(dǎo)等，還有一些是不確定的：確認(rèn)，分類等。本文重點(diǎn)研究防空雷達(dá)系統(tǒng)。雷達(dá)必須進(jìn)行對(duì)空搜索以便檢測(cè)目標(biāo)，總搜索量可以看作是m行和n列的二維矩陣，矩陣的每個(gè)元素代表對(duì)應(yīng)的波束位置，每個(gè)波束位置關(guān)聯(lián)一個(gè)監(jiān)視任務(wù)。當(dāng)目標(biāo)被檢測(cè)到，雷達(dá)將會(huì)對(duì)它實(shí)施跟蹤，系統(tǒng)控制臺(tái)將會(huì)發(fā)出攔截請(qǐng)求，并且在每個(gè)攔截請(qǐng)求中都有武器制導(dǎo)任務(wù)(對(duì)于同一個(gè)目標(biāo)而言可能擁有多個(gè)攔截請(qǐng)求)。在攔截結(jié)束后，殺傷評(píng)估任務(wù)將被用來確定目標(biāo)是否被摧毀?？梢娙蝿?wù)類型之間有明確的優(yōu)先級(jí)結(jié)構(gòu)。

詳細(xì)的說，一個(gè)定期任務(wù)想要每θi秒執(zhí)行一次。這意味著一個(gè)任務(wù)被獲取后最佳表現(xiàn)是該任務(wù)恰好在θi秒內(nèi)被執(zhí)行，其中該任務(wù)的最后一次重復(fù)記為起始時(shí)刻si，那么該任務(wù)的截止時(shí)刻oi即為起始時(shí)刻si與執(zhí)行時(shí)間θi的和。盡管oi是任務(wù)Ti的截止時(shí)刻，但是Ti沒有必要在oi時(shí)被執(zhí)行。如圖2所示，任務(wù)Ti在oi之前被調(diào)度，增加了系統(tǒng)負(fù)載導(dǎo)致任務(wù)Ti的性能降低；在oi時(shí)被調(diào)度或者在oi之后被調(diào)度，雖減小負(fù)載但是更降低了Ti的性能。另一方面，一個(gè)不確定任務(wù)必須恰好在一段時(shí)間內(nèi)被執(zhí)行，所以一個(gè)不確定任務(wù)可以用創(chuàng)建時(shí)刻ci和截止時(shí)刻oi表示。但是相比于定期任務(wù)，不確定任務(wù)可以在截止時(shí)刻之前、截止時(shí)刻或截止時(shí)間之后被執(zhí)行。

對(duì)于本文所提問題，任務(wù)被分為兩類。第一類定義了緊時(shí)間約束(HTC)任務(wù)。這類任務(wù)不能延遲執(zhí)行超過一個(gè)固定變量α，且不能在截止時(shí)刻oi之前被執(zhí)行。這意味HTC任務(wù)必須在區(qū)間[oi,oi+α]內(nèi)開始執(zhí)行，否則任務(wù)被拒絕(圖3)。對(duì)于HTC任務(wù)，這一約束將會(huì)帶來很高的跟蹤精度。例如，導(dǎo)彈制導(dǎo)就是HTC任務(wù)。第二類定義了軟時(shí)間約束(STC)任務(wù)。這類任務(wù)可以在任意時(shí)刻被處理，但是越延遲任務(wù)的處理，任務(wù)的性能會(huì)越低。例如，搜索任務(wù)就是STC任務(wù)。

如前所述，任務(wù)類型之間有優(yōu)先級(jí)結(jié)構(gòu)。這意味著，如果在過載期間，系統(tǒng)寧愿繼續(xù)跟蹤目標(biāo)而不是試圖發(fā)現(xiàn)新的目標(biāo)，這說明跟蹤任務(wù)相比于搜索任務(wù)有更高的優(yōu)先級(jí)。而且在相同類型任務(wù)之間同樣存在優(yōu)先級(jí)結(jié)構(gòu)。例如，在跟蹤敵對(duì)目標(biāo)上的任務(wù)優(yōu)先級(jí)要高于跟蹤友好目標(biāo)上的任務(wù)優(yōu)先級(jí)。

通過上述對(duì)雷達(dá)任務(wù)的描述，本文將定義以下雷達(dá)任務(wù)參數(shù)：

表1 雷達(dá)任務(wù)參數(shù)

任務(wù)最后一次重復(fù)的開始時(shí)刻si(定期任務(wù))ci(不確定任務(wù))執(zhí)行時(shí)間pi截止時(shí)刻oi完成時(shí)刻di=oi+pi+α(僅適用于HTC任務(wù))優(yōu)先級(jí)wi

本文理論上討論的是實(shí)時(shí)任務(wù)調(diào)度問題。事實(shí)上，雷達(dá)系統(tǒng)通過對(duì)任務(wù)的處理來監(jiān)視空域，每次任務(wù)的處理都會(huì)發(fā)生環(huán)境的變化。由此可見，環(huán)境是動(dòng)態(tài)變化的，并且隨著任務(wù)的出現(xiàn)、消失或更新而改變。但在實(shí)際中，雷達(dá)系統(tǒng)的任務(wù)調(diào)度是建立在框架內(nèi)的，在建立框架之前，我們固定環(huán)境變量。這意味著，在一個(gè)框架的構(gòu)造期間，環(huán)境是固定的，它將在下一個(gè)框架構(gòu)造之前更新[3]。

2 松時(shí)間約束任務(wù)序列的確認(rèn)

前文提到，STC任務(wù)可以在任意時(shí)刻被處理，但是越延遲他們的處理，任務(wù)的表現(xiàn)會(huì)越低。因此，在本節(jié)中，我們將根據(jù)其截止時(shí)刻和優(yōu)先結(jié)構(gòu)對(duì)STC任務(wù)進(jìn)行排序(見圖4.確認(rèn)STC任務(wù)序列概述)。

存在某任務(wù)晚于截止時(shí)刻(即當(dāng)前時(shí)刻大于該任務(wù)截止時(shí)刻)，那么如果一個(gè)計(jì)劃任務(wù)在截止時(shí)刻之前執(zhí)行，不僅沒有增加該計(jì)劃任務(wù)的性能，而且增加了這些后期任務(wù)的延遲降低它們的表現(xiàn)。

利用上述約束，我們定義了一個(gè)規(guī)則用以確定STC任務(wù)序列。那么，首先將STC任務(wù)根據(jù)其截止時(shí)刻降序排列，然后把該順序分成兩個(gè)子集。第一組稱為“緊急狀態(tài)”包含的為晚于他們截止時(shí)刻的任務(wù)，第二組稱為“非緊急狀態(tài)”包含的任務(wù)為不晚于截止時(shí)刻(即如果沒有這些晚于截止時(shí)刻的任務(wù)，這些任務(wù)將被執(zhí)行)。這個(gè)區(qū)分是用當(dāng)前時(shí)刻t值來完成的，所以如果一個(gè)任務(wù)的截止時(shí)刻大于或等于當(dāng)前時(shí)刻，則該任務(wù)處于“緊急狀態(tài)”，否則就是“非緊急狀態(tài)”。

當(dāng)雷達(dá)系統(tǒng)過載時(shí)，尋找兩類任務(wù)間優(yōu)先級(jí)最高的任務(wù)進(jìn)行調(diào)度[4]。因此，在“緊急狀態(tài)”的任務(wù)根據(jù)他們的優(yōu)先級(jí)進(jìn)行降序排列，在“非緊急狀態(tài)”的任務(wù)根據(jù)其相對(duì)延遲降序排列(即依據(jù)pi/(oi-ai)的大小降序排列)，通過調(diào)度這類任務(wù)來使局部過載最小化。

3 緊時(shí)間約束任務(wù)序列的確認(rèn)

為確認(rèn)HTC任務(wù)序列，我們將依據(jù)被拒絕任務(wù)最大優(yōu)先級(jí)的數(shù)量最小化的原則安排任務(wù)的執(zhí)行順序。正如前文提到的，HTC任務(wù)不能延遲處理超過固定變量α，且不能在截止時(shí)刻之前被執(zhí)行。所以，HTC任務(wù)必須在區(qū)間[oi,di]內(nèi)開始執(zhí)行，否則該任務(wù)被拒絕。

文獻(xiàn)[5]中指出調(diào)度時(shí)刻表的標(biāo)準(zhǔn)形式：存在索引j,0≤j≤n-1，標(biāo)準(zhǔn)形式的調(diào)度順序開始于任務(wù)T1,T2,…Tj，接下來的執(zhí)行順序?yàn)門n,Tj+1,Tj+2,…,Tn-1，盡可能的減少無(wú)意義的時(shí)間。需要說明的是，標(biāo)準(zhǔn)形式定義的任務(wù)序列依據(jù)它們的截止時(shí)刻増序排列。

首先定義SF(i,t)為任務(wù)T1,T2,…Ti子集標(biāo)準(zhǔn)形式的排列順序，其中每個(gè)優(yōu)先級(jí)任務(wù)的數(shù)量包含在數(shù)組t中。例如，如果SF(i,t)任務(wù)優(yōu)先級(jí)的順序?yàn)?1,3,5,3,4)，那么t為[1;0;2;1;1]。定義C(i,t)為SF(i,t)順序中每個(gè)任務(wù)盡可能被調(diào)度的情況下任務(wù)的完成時(shí)間。從標(biāo)準(zhǔn)形式的定義知，SF(i,t)由SF(j,t′),0≤j≤i-1和Ti,Tj+1,Tj+2,…,Ti-1組成。

a)l=0:

b)l=1:

c)l≥2:

對(duì)于任意t值，當(dāng)全部序列SF(i,t)和全部值C(i,t)已知時(shí)，那么當(dāng)前迭代i已完成。通過迭代i直到i=n，使序列中所含任務(wù)最大優(yōu)先級(jí)增至最大時(shí)，HTC任務(wù)序列就可以通過SF(n,t*)獲得，其中t是最優(yōu)解，C(n,t*)≠+。需要注意的是，在t1=[0;1;2;1;3]和t2=[0;0;1;2;3]兩解中，t2優(yōu)于t1。因?yàn)閠1執(zhí)行3個(gè)優(yōu)先級(jí)為5的任務(wù)和一個(gè)優(yōu)先級(jí)為4的任務(wù)，而t2執(zhí)行3個(gè)優(yōu)先級(jí)為5的任務(wù)和2個(gè)優(yōu)先級(jí)為4的任務(wù)。

4 算法和仿真結(jié)果

4.1 算法

正如前文所述，雷達(dá)任務(wù)調(diào)度是實(shí)時(shí)調(diào)度，但實(shí)際上是使用框架來進(jìn)行雷達(dá)任務(wù)調(diào)度。這種方式對(duì)于任務(wù)調(diào)度順序給予了一定的靈活性，因?yàn)橹灰蚣艿臉?gòu)造還沒有完成，那么仍有可能改變包含在框架內(nèi)任務(wù)的執(zhí)行順序。另一方面，這種方式對(duì)于環(huán)境變化有延遲，因?yàn)楫?dāng)我們建立現(xiàn)有框架時(shí)，雷達(dá)天線調(diào)度先前的框架。此外，環(huán)境的更新僅發(fā)生在一個(gè)框架構(gòu)造之前。所以，當(dāng)一個(gè)框架被執(zhí)行時(shí)，環(huán)境的改變由于框架的執(zhí)行并沒有包括在下一個(gè)框架構(gòu)造的系統(tǒng)中(下一個(gè)框架的構(gòu)造發(fā)生在當(dāng)前框架被執(zhí)行期間)。但是在下一個(gè)框架之后將會(huì)充分考慮環(huán)境因素。

我們的調(diào)度算法必須構(gòu)造這些框架。當(dāng)一個(gè)框架開始構(gòu)造時(shí)，將使用在先前章節(jié)確認(rèn)的STC任務(wù)序列和HTC任務(wù)序列，即STC任務(wù)序列和HTC任務(wù)序列作為算法的輸入。之后結(jié)合這兩類序列去建立框架。所以，本文提出算法必須決定兩類序列中被首批執(zhí)行的任務(wù)，哪類任務(wù)將首先進(jìn)入到框架中。

因?yàn)樵贖TC序列中的任務(wù)不能它的截止時(shí)刻之前被執(zhí)行，所以在插入框架之前，我們必須判斷當(dāng)前時(shí)刻是否大于某HTC任務(wù)的截止時(shí)刻。這個(gè)限制將會(huì)用于決定兩類序列首批被執(zhí)行任務(wù)中，哪類任務(wù)將首先進(jìn)入到框架中。當(dāng)任務(wù)被插入到框架時(shí)，該任務(wù)在當(dāng)前時(shí)刻將會(huì)執(zhí)行，隨后我們將通過增加任務(wù)的執(zhí)行時(shí)間來更新當(dāng)前時(shí)刻。當(dāng)框架構(gòu)造完成，任務(wù)調(diào)度停止。(圖6.算法說明概述)

4.2 仿真結(jié)果

最后針對(duì)偵察范圍為方位[-45°，+45°]俯仰[0°，70°]的多功能相控陣?yán)走_(dá)，我們搭建了類似仿真平臺(tái)，得出仿真結(jié)果。對(duì)于這種相控陣?yán)走_(dá)，跟蹤任務(wù)相比于搜索任務(wù)有較高的優(yōu)先級(jí)，所以當(dāng)系統(tǒng)的全部負(fù)載超過100%時(shí)，搜索任務(wù)將會(huì)在跟蹤任務(wù)之前被延時(shí)。

討論多功能相控陣?yán)走_(dá)的搜索范圍是以便發(fā)現(xiàn)目標(biāo)。仿真中主要考慮兩類目標(biāo)：敵對(duì)目標(biāo)和友好目標(biāo)。其中敵對(duì)目標(biāo)會(huì)被判定為HTC任務(wù)，而友好目標(biāo)會(huì)被判定為STC任務(wù)。敵對(duì)目標(biāo)將會(huì)在Xms且不超過α的時(shí)間內(nèi)被調(diào)度，而友好目標(biāo)會(huì)每Y秒被調(diào)度一次。敵對(duì)目標(biāo)的優(yōu)先級(jí)固定為wx，而友好目標(biāo)的優(yōu)先級(jí)被固定為wy，wxgt;wy。

在仿真期間，如果某敵對(duì)目標(biāo)的跟蹤任務(wù)被拒絕(即該任務(wù)在Xms且不超過α的時(shí)間內(nèi)被執(zhí)行、系統(tǒng)過載或者有太多HTC任務(wù)共享時(shí)間區(qū)間[oi，di])，那么任務(wù)的執(zhí)行時(shí)間將增加Xms，任務(wù)的優(yōu)先級(jí)增加1，之后該任務(wù)帶著這些新參數(shù)插入到系統(tǒng)中。當(dāng)該任務(wù)被調(diào)度時(shí)，它的參數(shù)將會(huì)被重新定義執(zhí)行時(shí)間Xms和優(yōu)先級(jí)wx。

跟蹤敵對(duì)目標(biāo)的執(zhí)行時(shí)間會(huì)被作為系統(tǒng)表現(xiàn)的評(píng)估標(biāo)準(zhǔn)，這意味著每2Xms跟蹤兩個(gè)敵對(duì)目標(biāo)的系統(tǒng)表現(xiàn)好于每Xms跟蹤一個(gè)敵對(duì)目標(biāo)，另一個(gè)目標(biāo)每3Xms跟蹤一次。

本文進(jìn)行了兩類仿真，第一類仿真(SHTC)使用的是本章節(jié)第一部分介紹的算法，跟蹤敵對(duì)目標(biāo)劃為HTC任務(wù)。第二類仿真(SSTC)使用的是一種典型算法，跟蹤敵對(duì)目標(biāo)劃為STC任務(wù)：每個(gè)敵對(duì)目標(biāo)每Xms被跟蹤一次，優(yōu)先級(jí)為wx，劃為STC任務(wù)。如果該STC任務(wù)被執(zhí)行時(shí)刻超過最大延遲變量α，那么該任務(wù)被拒絕并且參數(shù)將會(huì)更新(它的處理時(shí)段增加Xms，優(yōu)先級(jí)增加1)，當(dāng)該任務(wù)再被執(zhí)行時(shí)，它的參數(shù)被重新定義為每Xms處理一次，優(yōu)先級(jí)為wx。

圖7、圖8分別呈現(xiàn)了SSTC仿真和SHTC仿真針對(duì)敵對(duì)目標(biāo)跟蹤任務(wù)的重復(fù)執(zhí)行時(shí)間。SHTC的仿真結(jié)果顯示多功能相控陣?yán)走_(dá)利用本文提供的算法同時(shí)跟蹤四個(gè)敵對(duì)目標(biāo)所能達(dá)到的最大重復(fù)時(shí)間為2Xms。而SSTC達(dá)到了3Xms。由此可得結(jié)論，本文提出的算法在保持很高跟蹤精度的前提下管理高優(yōu)先級(jí)目標(biāo)方面明顯好于典型算法。

圖9是圖10在[x,x+α]時(shí)段和[2x,2x+α]時(shí)段的放大圖。圖10說明了搜索任務(wù)的重復(fù)執(zhí)行時(shí)間。從圖中可以明顯看出三個(gè)負(fù)載狀態(tài)：滿載，過載，欠載。第一階段即為滿載狀態(tài)，系統(tǒng)的全部負(fù)載為100%。在第一階段，目標(biāo)還沒有判定為敵對(duì)目標(biāo)，它們被認(rèn)為STC任務(wù)進(jìn)行跟蹤。第二階段系統(tǒng)開始出現(xiàn)過載，目標(biāo)被判定為敵對(duì)目標(biāo)，當(dāng)目標(biāo)為敵對(duì)目標(biāo)時(shí)，系統(tǒng)將每Y秒重復(fù)一次的STC任務(wù)轉(zhuǎn)為每Xms重復(fù)一次的HTC任務(wù)。因?yàn)閄lt;Y，每一次目標(biāo)都被定為敵對(duì)目標(biāo)，系統(tǒng)的負(fù)載增加，然而，在第二階段系統(tǒng)負(fù)載的增加是逐步的。第二階段結(jié)束，目標(biāo)被摧毀。因?yàn)閮H有搜索任務(wù)被調(diào)度，雷達(dá)的負(fù)載減小，出現(xiàn)最后一個(gè)階段，欠載狀態(tài)。在這一階段，任務(wù)在它的截止時(shí)刻之前被調(diào)度。

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

在本文中，我們討論了雷達(dá)任務(wù)調(diào)度問題，要求在保持高跟蹤精度的前提下率先執(zhí)行優(yōu)先級(jí)較高的任務(wù)，然而這些任務(wù)必須在[oi,oi+α]內(nèi)被調(diào)度。為了解決這類問題，定義了兩類任務(wù)：緊時(shí)間約束(HTC)任務(wù)和松時(shí)間約束(STC)任務(wù)，確認(rèn)每類任務(wù)的執(zhí)行順序，首先STC任務(wù)依據(jù)其截止時(shí)刻降序排列，然后將任務(wù)分為兩個(gè)子集，最后根據(jù)優(yōu)先級(jí)順序重新排列每個(gè)子集中任務(wù)的順序；對(duì)于HTC任務(wù)序列，我們提出了利用調(diào)度時(shí)刻表的標(biāo)準(zhǔn)形式動(dòng)態(tài)確認(rèn)任務(wù)的執(zhí)行順序。最后將這兩類任務(wù)序列作為輸入，結(jié)合這兩類序列構(gòu)建框架，被采用的操作即位雷達(dá)要執(zhí)行的任務(wù)。在每一步中，通過當(dāng)前時(shí)刻與HTC任務(wù)截止時(shí)刻相比的原則決定排列在這兩類序列中被首批執(zhí)行的任務(wù)誰(shuí)先被調(diào)度?；诜抡娼Y(jié)果可以驗(yàn)證，相比于傳統(tǒng)算法，本文提出的算法對(duì)于多功能相控陣?yán)走_(dá)任務(wù)的調(diào)度具有一定的優(yōu)越性。

[1] 侯澤欣.多功能相控陣?yán)走_(dá)資源調(diào)度理論與方法研究[D].中國(guó)艦船研究院.2013.

[2] Q. Zheng, P. Baptiste, and F. Barbaresco.On scheduling a multifunc-tion radar with duty cycle budget. International Conference COGIS’09 (COG nitive systems with Interactive Sensors). 2009.

[3] 冀琛.對(duì)相控陣?yán)走_(dá)工作模式的資源調(diào)度研究[D].現(xiàn)代防御技術(shù).2014.

[4] P.W. Moo.Scheduling for multifunction radar via two-slope benefit functions.IET Radar Sonar Navig, 2011, 5(8):884-894.

[5] 胡曉培.相控陣?yán)走_(dá)數(shù)據(jù)處理和資源調(diào)度仿真[D].西安電子科技大學(xué). 2015.

[6] 盧建斌,席澤敏.一種基于IMMKF的相控陣?yán)走_(dá)波束調(diào)度算法[D].海軍工程大學(xué).2014.

HardTimeConstraintBasedTasksSchedulingforaMultifunctionPhasedArrayRadar

Song Weiqiang, Chen Chun, Gao Jian

(Xi’an Electronic Engineering Research Institute, Xi’an 710100)

Scheduling of radar tasks is described, two types of tasks are defined: hard time constraint (HTC) task, and soft time constraint (STC) task. Execution of HTC tasks cannot be delayed for more than a fixed constraint , STC tasks can be executed at any time. An algorithm is presented for this purpose, sequence of HTC tasks and sequence of STC tasks are made, then a selection rule to determine scheduling sequence between these two kinds of tasks is presented.

simulation; scheduling; phased array radar

2017-05-30

宋偉強(qiáng)(1990-)，男，碩士研究生。研究方向?yàn)樾盘?hào)處理技術(shù)。

TN958.92

A

1008-8652(2017)03-006-05