孫銘才， 張 秦， 袁俊超

(空軍工程大學(xué) 防空反導(dǎo)學(xué)院，陜西 西安 710051)

?

基于改進(jìn)時(shí)間指針的相控陣?yán)走_(dá)任務(wù)調(diào)度方法*

孫銘才， 張 秦， 袁俊超

(空軍工程大學(xué) 防空反導(dǎo)學(xué)院，陜西 西安 710051)

針對相控陣?yán)走_(dá)實(shí)時(shí)任務(wù)調(diào)度中時(shí)間資源利用不充分的問題，提出了一種基于改進(jìn)時(shí)間指針的任務(wù)自適應(yīng)調(diào)度方法。以時(shí)間指針為對象，從整個(gè)調(diào)度時(shí)間軸上所有滿足時(shí)間指針處執(zhí)行條件的任務(wù)請求中，選擇一個(gè)優(yōu)先級最高的任務(wù)作為當(dāng)前時(shí)刻的執(zhí)行任務(wù)，有效減少了空閑時(shí)間的浪費(fèi)，使得相控陣?yán)走_(dá)能夠在有限時(shí)間資源內(nèi)調(diào)度執(zhí)行更多的任務(wù)。與基于傳統(tǒng)時(shí)間指針的調(diào)度方法仿真對比，結(jié)果表明：方法提高了任務(wù)調(diào)度成功率和時(shí)間利用率，有效提升了相控陣?yán)走_(dá)的整體調(diào)度性能，具有一定的優(yōu)越性。

相控陣?yán)走_(dá)； 時(shí)間指針； 時(shí)間資源； 任務(wù)調(diào)度

0 引 言

相控陣?yán)走_(dá)具有靈活、快速的波束捷變和波束自適應(yīng)能力，可以同時(shí)執(zhí)行搜索、跟蹤等多個(gè)任務(wù)[1～2]。隨著現(xiàn)代戰(zhàn)場環(huán)境日益復(fù)雜，相控陣?yán)走_(dá)需執(zhí)行的任務(wù)數(shù)量不斷增多，要求相控陣?yán)走_(dá)在有限的時(shí)間資源內(nèi)盡可能多地執(zhí)行任務(wù)，因此，需要對雷達(dá)任務(wù)調(diào)度方法進(jìn)行合理設(shè)計(jì)，以實(shí)現(xiàn)時(shí)間資源有效利用，從而提升相控陣?yán)走_(dá)的整體性能。

近年來，隨著相控陣?yán)走_(dá)技術(shù)的廣泛應(yīng)用，資源調(diào)度方法研究成為其中一個(gè)重要的研究方向。文獻(xiàn)[3]將截止期最早最優(yōu)先(earlist deadline first，EDF)算法引入到了相控陣?yán)走_(dá)的任務(wù)調(diào)度過程中，即優(yōu)先級高的任務(wù)最先被調(diào)度，在其可執(zhí)行時(shí)間范圍內(nèi)盡量靠近其期望執(zhí)行時(shí)間。文獻(xiàn)[4,5]結(jié)合啟發(fā)式規(guī)則將遺傳算法引入到了相控陣?yán)走_(dá)的任務(wù)調(diào)度過程中。文獻(xiàn)[6,7]提出了基于二次規(guī)劃的任務(wù)調(diào)度方法，利用對整體任務(wù)的二次規(guī)劃獲取最佳執(zhí)行時(shí)間，使得雷達(dá)對任務(wù)的調(diào)度代價(jià)最小。上述調(diào)度方法實(shí)質(zhì)是從任務(wù)的角度出發(fā)，根據(jù)任務(wù)選擇執(zhí)行時(shí)間，結(jié)果可能導(dǎo)致使被成功調(diào)度的任務(wù)之間存在空閑時(shí)間，從而造成時(shí)間資源浪費(fèi)。文獻(xiàn)[8，9]從時(shí)間的調(diào)度出發(fā)，提出基于時(shí)間指針的相控陣?yán)走_(dá)任務(wù)調(diào)度方法，方法定義了時(shí)間指針，根據(jù)時(shí)間指針?biāo)赶虻臅r(shí)刻，從指針?biāo)谡{(diào)度間隔的申請任務(wù)中選擇最適合在此時(shí)刻執(zhí)行的任務(wù)，有效減少了任務(wù)之間的空閑時(shí)間，提升了雷達(dá)的調(diào)度性能。但是當(dāng)相鄰兩個(gè)調(diào)度間隔的任務(wù)中，前一個(gè)調(diào)度間隔的任務(wù)較少，后一個(gè)調(diào)度間隔的任務(wù)較多時(shí)，其調(diào)度結(jié)果會使得前一個(gè)調(diào)度間隔中存在著空閑時(shí)間，而后一個(gè)調(diào)度間隔存在任務(wù)被延遲或刪除的現(xiàn)象。文獻(xiàn)[10～13]在上述調(diào)度算法的基礎(chǔ)上，針對任務(wù)優(yōu)先級的綜合設(shè)計(jì)，提出了將任務(wù)工作方式、截止期以及目標(biāo)屬性互相結(jié)合的優(yōu)先級設(shè)計(jì)方法。

上述文獻(xiàn)中，相控陣?yán)走_(dá)在對任務(wù)整個(gè)調(diào)度過程中均沒有實(shí)現(xiàn)對時(shí)間的充分利用，存在時(shí)間資源浪費(fèi)。針對這一問題，本文提出了一種基于改進(jìn)時(shí)間指針的相控陣?yán)走_(dá)任務(wù)調(diào)度方法，根據(jù)時(shí)間指針?biāo)赶虻漠?dāng)前時(shí)刻，從整個(gè)調(diào)度時(shí)間軸上所有滿足此時(shí)刻執(zhí)行條件的任務(wù)請求中，選擇一個(gè)優(yōu)先級最高的任務(wù)作為當(dāng)前的執(zhí)行任務(wù)，有效減少了空閑時(shí)間的浪費(fèi)，使得相控陣?yán)走_(dá)能夠在有限的時(shí)間資源內(nèi)調(diào)度執(zhí)行更多的任務(wù)。通過設(shè)定相控陣?yán)走_(dá)的工作場景，對該方法進(jìn)行了仿真，結(jié)果證明了其優(yōu)越性。

1 任務(wù)建模

相控陣?yán)走_(dá)須執(zhí)行的任務(wù)主要有搜索、驗(yàn)證、跟蹤以及失跟處理等。任務(wù)通過以下模型進(jìn)行描述

qi={tei,Δti,wi,prii,Pi},i=1,2,3…

(1)

式中qi為為第i個(gè)任務(wù)；tei和Δti分別為每個(gè)任務(wù)的期望執(zhí)行時(shí)刻和所需執(zhí)行時(shí)間長度；wi為每個(gè)任務(wù)的時(shí)間窗，時(shí)間窗指任務(wù)實(shí)際執(zhí)行時(shí)刻可以在其期望執(zhí)行時(shí)刻前后移動的時(shí)間范圍[14]；prii和Pi分別為每個(gè)任務(wù)的工作方式優(yōu)先級和綜合優(yōu)先級。設(shè)tfi為任務(wù)qi的最早可執(zhí)行時(shí)刻，則tfi=tei-wi；設(shè)tli為任務(wù)qi的最晚可執(zhí)行時(shí)刻，即截止期，則tli=tei+wi。

任務(wù)的綜合優(yōu)先級設(shè)計(jì)，主要由工作方式優(yōu)先級和截止期決定[9]。任務(wù)的工作方式優(yōu)先級越高，則越優(yōu)先調(diào)度；任務(wù)的截止期越早，則越優(yōu)先調(diào)度。任務(wù)的工作方式優(yōu)先級與其本身類型有關(guān)，根據(jù)經(jīng)驗(yàn)事先確定，用pri表示；任務(wù)的截止期與其時(shí)間窗和期望執(zhí)行時(shí)刻有關(guān)，表示為tli=tei+wi。假設(shè)當(dāng)前時(shí)刻有J個(gè)任務(wù)，對這J個(gè)任務(wù)分別按照工作方式優(yōu)先級由高到低和截止期由小到大進(jìn)行2次排序，記第j個(gè)任務(wù)qj在2次排序中的序號分別為Npj和Ndj。構(gòu)建任務(wù)綜合優(yōu)先級函數(shù)

(2)

式中 η為傾向工作方式優(yōu)先級的加權(quán)值，其取值范圍是[1,J+1]?？梢酝ㄟ^選取不同的權(quán)值η來增加或減小工作方式優(yōu)先級對綜合優(yōu)先級的影響。

2 調(diào)度方法的原理與實(shí)現(xiàn)

2.1 調(diào)度方法的原理

對于傳統(tǒng)時(shí)間指針調(diào)度方法，相控陣?yán)走_(dá)在對時(shí)間指針?biāo)赶虻臅r(shí)刻分析調(diào)度任務(wù)時(shí)，只是對時(shí)間指針?biāo)谡{(diào)度間隔內(nèi)的任務(wù)進(jìn)行分析，從該調(diào)度間隔內(nèi)滿足當(dāng)前執(zhí)行條件的任務(wù)中，選擇一個(gè)綜合優(yōu)先級最高的任務(wù)執(zhí)行。在不同調(diào)度間隔任務(wù)不均衡的情況下，這種方法往往可能造成2種結(jié)果：當(dāng)調(diào)度間隔內(nèi)任務(wù)數(shù)較少時(shí)，會造成時(shí)間資源的空閑；而當(dāng)調(diào)度間隔內(nèi)任務(wù)數(shù)較多時(shí)，往往造成任務(wù)的延遲或刪除。圖1為時(shí)間軸上2個(gè)調(diào)度間隔共有8個(gè)任務(wù)請求的情況，其中調(diào)度間隔1的任務(wù)較少，調(diào)度間隔2的任務(wù)較多。傳統(tǒng)時(shí)間指針調(diào)度方法對這些任務(wù)的調(diào)度結(jié)果如圖2(a)所示，圖2(a)中，2個(gè)調(diào)度間隔各自分析調(diào)度各自的任務(wù)，使得調(diào)度間隔1存在空閑時(shí)間沒有被利用，而調(diào)度間隔2由于任務(wù)過多，導(dǎo)致任務(wù)8得不到調(diào)度。

在相控陣?yán)走_(dá)對任務(wù)的調(diào)度執(zhí)行過程中，任務(wù)在被雷達(dá)調(diào)度執(zhí)行后，系統(tǒng)根據(jù)該任務(wù)回波信號的處理結(jié)果，產(chǎn)生后續(xù)任務(wù)，并且給出后續(xù)任務(wù)的執(zhí)行參數(shù)，包括期望執(zhí)行時(shí)刻、時(shí)間窗、執(zhí)行時(shí)間長度以及工作方式優(yōu)先級。所以，對于某一時(shí)刻，相控陣?yán)走_(dá)在該時(shí)刻的整個(gè)調(diào)度時(shí)間軸上所有已產(chǎn)生的任務(wù)的執(zhí)行參數(shù)均可知。因此，雷達(dá)在某時(shí)刻分析調(diào)度任務(wù)時(shí)，可以對整個(gè)調(diào)度時(shí)間軸上的任務(wù)進(jìn)行分析，從所有滿足此時(shí)刻執(zhí)行條件的任務(wù)中，選擇一個(gè)綜合優(yōu)先級最高的任務(wù)在此時(shí)刻執(zhí)行。根據(jù)以上所述，利用改進(jìn)時(shí)間指針調(diào)度方法對圖1中的任務(wù)進(jìn)行分析調(diào)度，得到如圖2(b)所示的調(diào)度結(jié)果。圖2(b)中，調(diào)度間隔2的任務(wù)4在調(diào)度間隔1中得到執(zhí)行，使得調(diào)度間隔1的空閑時(shí)間減少，并且兩個(gè)調(diào)度間隔的全部任務(wù)都能得到調(diào)度。

圖1 任務(wù)請求

圖2 兩種方法調(diào)度結(jié)果對比

2.2 調(diào)度方法的具體步驟

假設(shè)某一個(gè)調(diào)度間隔(SI)起始時(shí)刻為to，結(jié)束時(shí)刻為tn=to+SI，tp為調(diào)度過程中的當(dāng)前時(shí)刻，即為時(shí)間指針，Q=[q1,q2,…,qN]為tp時(shí)刻整個(gè)調(diào)度時(shí)間軸上所有任務(wù)請求形成的任務(wù)申請鏈表。任務(wù)的實(shí)時(shí)調(diào)度過程:

1)獲得該調(diào)度間隔的起始時(shí)間指針tp，由于上一調(diào)度間隔中最后一個(gè)任務(wù)的調(diào)度執(zhí)行可能占用了本調(diào)度間隔的時(shí)間，所以tp≥to。

2)取出任務(wù)申請鏈表Q中最晚可執(zhí)行時(shí)刻小于tp的任務(wù)，送入刪除鏈表。

5)檢查任務(wù)申請鏈表Q是否為空，若空，轉(zhuǎn)步驟(8)；若非空，轉(zhuǎn)步驟(6)。

6)若tp≥tn，轉(zhuǎn)步驟(7)；否則，轉(zhuǎn)步驟(2)。

7)該調(diào)度間隔結(jié)束，得到該調(diào)度間隔的執(zhí)行鏈表，并進(jìn)入到下一個(gè)調(diào)度間隔的調(diào)度過程。

8)雷達(dá)工作完畢。

3 仿真試驗(yàn)與性能評估

3.1 性能評估指標(biāo)

為了驗(yàn)證本文方法的優(yōu)越性，采用以下評估指標(biāo)進(jìn)行性能評估：

1)調(diào)度成功率(schedule sccess ratio,SSR)

(3)

式中 Nsuc為成功調(diào)度任務(wù)總數(shù)；N為所有請求的任務(wù)總數(shù)。調(diào)度成功率用以表征方法對任務(wù)的調(diào)度執(zhí)行情況，調(diào)度成功率越高，方法性能越佳。

2)時(shí)間利用率(timeutilizationratio，TUR)

(4)

式中 T為仿真時(shí)間長度。時(shí)間利用率用以表征方法對有限時(shí)間資源的占用情況，時(shí)間利用率越高，方法性能越佳。

3.2 仿真分析

對本文中的改進(jìn)時(shí)間指針方法和傳統(tǒng)時(shí)間指針方法[7]分別進(jìn)行仿真，利用評估指標(biāo)對仿真結(jié)果進(jìn)行分析對比。除調(diào)度方法不同外，實(shí)驗(yàn)場景和仿真參數(shù)設(shè)置完全相同。

仿真參數(shù)：1)調(diào)度間隔為50ms，仿真時(shí)間為5s； 2)搜索任務(wù)在仿真開始均按其更新率周期產(chǎn)生，目標(biāo)被隨機(jī)搜索到；3)搜索檢測到的目標(biāo)經(jīng)驗(yàn)證確定為有效目標(biāo)后，進(jìn)行跟蹤，跟蹤任務(wù)按其更新率產(chǎn)生；4)驗(yàn)證任務(wù)由兩部分產(chǎn)生：目標(biāo)驗(yàn)證與虛警；5)失跟處理任務(wù)在跟蹤起始后隨機(jī)產(chǎn)生；6)綜合優(yōu)先級設(shè)計(jì)中的權(quán)值η，設(shè)η=J/2+1，為綜合優(yōu)先級的設(shè)計(jì)均衡考慮工作方式優(yōu)先級和截止期的影響。

仿真實(shí)驗(yàn)場景設(shè)置為：相控陣?yán)走_(dá)對5～30批目標(biāo)進(jìn)行跟蹤。任務(wù)的參數(shù)設(shè)置如表1所示。

對兩種方法進(jìn)行仿真，通過性能評估指標(biāo)對其進(jìn)行比較。圖3為兩種方法在不同數(shù)量目標(biāo)下的任務(wù)調(diào)度成功率；圖4為兩種方法在不同數(shù)量目標(biāo)下的時(shí)間利用率。

表1 任務(wù)參數(shù)設(shè)置

圖3 任務(wù)調(diào)度成功率對比

圖4 時(shí)間利用率對比

從圖3和圖4中可知，當(dāng)目標(biāo)數(shù)量為5時(shí)，兩種方法的調(diào)度成功率均為100 %，表示都能夠調(diào)度所有任務(wù)，且此時(shí)兩種方法的時(shí)間利用率相同。當(dāng)目標(biāo)數(shù)量為8時(shí)，傳統(tǒng)時(shí)間指針方法的調(diào)度成功率開始小于100 %，而改進(jìn)時(shí)間指針方法的調(diào)度成功率仍然為100 %，并且改進(jìn)時(shí)間指針方法的時(shí)間利用率開始大于傳統(tǒng)時(shí)間指針方法。當(dāng)目標(biāo)數(shù)量為18時(shí)，改進(jìn)時(shí)間指針方法的時(shí)間利用率開始等于100 %，說明此時(shí)整個(gè)調(diào)度時(shí)間軸上已無空閑時(shí)間。綜合上述分析可以得出:由于改進(jìn)的時(shí)間指針方法能夠在整個(gè)時(shí)間軸上使得任務(wù)的分配更加均衡，故與與傳統(tǒng)時(shí)間指針方法相比，能夠更加充分利用時(shí)間資源，減少空閑時(shí)間的浪費(fèi)，同時(shí)提高任務(wù)成功調(diào)度的概率，增加有限時(shí)間內(nèi)執(zhí)行任務(wù)的數(shù)量。從而提高相控陣?yán)走_(dá)的資源調(diào)度效率。

4 結(jié)束語

針對相控陣?yán)走_(dá)的實(shí)時(shí)任務(wù)調(diào)度問題，提出了一種改進(jìn)時(shí)間指針調(diào)度方法，給出了調(diào)度方法的詳細(xì)流程，并對其進(jìn)行了仿真。仿真結(jié)果表明：在執(zhí)行任務(wù)負(fù)荷較大的情況下，方法在任務(wù)調(diào)度成功率和時(shí)間利用率上相比傳統(tǒng)方法具有一定的優(yōu)勢，能夠有效提升相控陣?yán)走_(dá)的任務(wù)調(diào)度性能。方法未引入對能量資源和雷達(dá)信息處理資源的約束條件，研究多種約束條件下的任務(wù)調(diào)度方法，為下一步的研究重點(diǎn)。

[1] 嚴(yán)軍超，胡明全.相控陣天氣雷達(dá)氣象雷達(dá)方程修正研究[J].現(xiàn)代雷達(dá)，2015,36(5)：1-5.

[2] 邵正途，朱和平.空地聯(lián)合反導(dǎo)預(yù)警技術(shù)探討[J].傳感器與微系統(tǒng)，2008，27(4)：59-62.

[3] Gopalakrishnan S，Caccamo M，Shih C S.Finite-horizon scheduling of radar dwells with online template construction[C]∥Proc of 25th IEEE International Real-Time Systems Symposium,Lisbon，Portugal：IEEE，2004：23-33.

[4] 周 穎，王雪松，汪連棟，等.基于遺傳算法的相控陣?yán)走_(dá)最優(yōu)化調(diào)度研究[J].系統(tǒng)工程與電子技術(shù)，2005，27(12)：1977-1980.

[5] 周 穎，王國玉，王雪松，等.基于啟發(fā)式混合遺傳算法的相控陣?yán)走_(dá)最優(yōu)化調(diào)度[J].系統(tǒng)工程與電子技術(shù)，2006，28(7)：992-1005.

[6] 盧建斌，胡衛(wèi)東，郁文賢.多功能相控陣?yán)走_(dá)實(shí)時(shí)駐留的自適應(yīng)調(diào)度算法[J].系統(tǒng)工程與電子技術(shù)，2005，27(12)：1981-1984.

[7] 趙 宇，李建勛，曹蘭英，等.基于二次規(guī)劃的相控陣?yán)走_(dá)任務(wù)自適應(yīng)調(diào)度算法[J].系統(tǒng)工程與電子技術(shù)，2012，34(4)：698-703.

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

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

[10] Cheng T，He Z S，Tang T.Dwell scheduling algorithm for multifunction phased array radars based on the scheduling gain[J].Journal of Systems Engineering，2008，19(3)：479-485.

[11] Lu J B，Xiao H，Xi Z M，et al.Multifunction phased array resource management：Real-time scheduling algorithm[J].Journal of Computational Information Systems，2011，7(2)：385-393.

[12] Lu J B，Xiao H，Xi Z M，et al.Phased array radar resource management:Task scheduling and performance evaluation[J].Journal of Computational Information Systems，2013，9(3)：1131-1138.

[13] 張浩為，謝軍偉，盛 川.綜合優(yōu)先級規(guī)劃下的相控陣?yán)走_(dá)自適應(yīng)調(diào)度方法[J].兵工學(xué)報(bào)，2016，37(11)：2163-2169.

[14] 郭坤鵬.相控陣?yán)走_(dá)自適應(yīng)調(diào)度算法研究[D].杭州：杭州電子科技大學(xué)，2015.

Task scheduling algorithm for phased array radar based on modified time pointer*

SUN Ming-cai, ZHANG Qin, YUAN Jun-chao

(Air and Missile Defense College,Air Force Engineering University,Xi’an 710051,China)

Aiming at the insufficient utilization of time resources of the phased array radar real-time task scheduling,a method based on modified time pointer is given to achieve task adaptive scheduling.Method takes the time pointer as object,selects the highest priority task to be current one from all tasks on the timeline that need to be scheduled and meet the execution conditions of the time pointer.The method reduces the waste of idle time effectively,and makes the radar to execute more tasks in limited time resources.Compared with the methods based on conventional time pointer by simulation,the result shows that the method increases task scheduling ratio and time utilization,improves the overall scheduling performance of the phased array radar,and has certain advantages.

phased array radars; time pointer; time resource; task scheduling

10.13873/J.1000—9787(2017)07—0023—03

2017—06—10

國家自然科學(xué)基金資助項(xiàng)目(61601499)

TN 958

A

1000—9787(2017)07—0023—03

孫銘才(1993-)，男，碩士研究生，主要研究方向?yàn)橄嗫仃嚴(yán)走_(dá)資源管理，E—mail:398327155@qq.com。