李 波, 周靜楊, 高曉光

(西北工業(yè)大學(xué)電子信息學(xué)院, 陜西 西安 710129)

0 引 言

相控陣雷達(phased array radar,PAR)是一種通過改變雷達波相位從而改變波束方向的雷達,其利用陳列天線實現(xiàn)波束在空間的電掃描。與傳統(tǒng)的機械掃描雷達相比,PAR掃描速度與掃描范圍更大,波束位置、波束照射時間、次數(shù)等均更為靈活多變,其抗干擾性能和環(huán)境適應(yīng)能力也更為優(yōu)秀[1]。因此,PAR能夠?qū)崿F(xiàn)搜索、多目標跟蹤、制導(dǎo)等多項任務(wù)同時進行,為了更加有效合理地分配雷達資源,達到雷達的最大工作效能,需要設(shè)計雷達的任務(wù)調(diào)度方法。

相比于模板法、部分模板法等常見的PAR調(diào)度方法,自適應(yīng)調(diào)度策略是最為有效且復(fù)雜的調(diào)度方法[2]。文獻[3-6]在經(jīng)典的最小截止期優(yōu)先(earliest deadline first,EDF)算法上提出了修正的EDF模型,并在其基礎(chǔ)上提出了PAR實時駐留的自適應(yīng)調(diào)度算法。文獻[7-8]利用“時間窗”增加了任務(wù)調(diào)度的時間靈活性。文獻[9]提出了駐留時間可變調(diào)度算法,進一步提高了任務(wù)調(diào)度能力。文獻[10]針對調(diào)度過程中因采樣周期不同在時間上產(chǎn)生沖突的問題,提出了基于周期分區(qū)的時間調(diào)度算法。文獻[11-12]提出了脈沖交錯算法,進一步提高了對時間資源的利用率。文獻[13-15]提出了基于遺傳算法(genetic algorithm,GA)的自適應(yīng)調(diào)度方案,在分析雷達約束條件的基礎(chǔ)上,設(shè)計相應(yīng)的編碼方式和遺傳操作。

EDF算法雖然提高了時間利用率,但是不能保障高優(yōu)先級的任務(wù)調(diào)度成功率;GA雖然能夠提供較好的解決方案,但迭代次數(shù)較多,實時性能較差。拍賣算法(auction algorithm,AA)也能解決此類非確定多項式問題(non-deterministic polynomial, NP),并能達到更好的實時性要求,例如文獻[16-17]提出利用AA來解決任務(wù)分配問題,文獻[18]提出在AA相比于GA更適用于解決時間約束條件下的目標分配問題。本文提出基于AA的PAR自適應(yīng)調(diào)度方案,將任務(wù)執(zhí)行時間與期望執(zhí)行時間的標準差作為競拍者的競標期望值,最大剩余連續(xù)時間和任務(wù)優(yōu)先級作為拍賣條件,以時間作為競拍物品,求能夠使拍賣者和競拍者的社會福利最大的分配方案。仿真結(jié)果表明本文算法在具有良好的任務(wù)調(diào)度成功率和時間偏移率的前提下,可以根據(jù)實際事態(tài)需求調(diào)整加權(quán)系數(shù)來提高時間利用率或高優(yōu)先級的任務(wù)調(diào)度成功率。

1 任務(wù)模型及優(yōu)先級設(shè)計

1.1 任務(wù)模型

在調(diào)度間隔長度為L的時間內(nèi),有N個雷達波束駐留任務(wù),其中單個駐留任務(wù)為

mj={Pji,tje,tjl,tjw,tjp,mjs,(Rj,αj,βj)}

(1)

式中,Pji表示任務(wù)工作優(yōu)先級;由時間窗的概念可知任務(wù)有最早執(zhí)行時間tje和最晚執(zhí)行時間tjl。即在時間[tje,tjl]內(nèi)還未被執(zhí)行,則該任務(wù)被終止;tjw表示期望執(zhí)行時間;tjr表示實際執(zhí)行時間;tjp表示任務(wù)駐留時間;mjs為更新率即任務(wù)自動生成周期；(Rj,αj,βj)為期望波束位置。

1.2 任務(wù)優(yōu)先級

基于固定優(yōu)先級的調(diào)度算法是一種常見的PAR自適應(yīng)調(diào)度算法,其固定優(yōu)先級如表1所示。在這種固定優(yōu)先級算法中,相同工作方式的調(diào)度順序只取決于時間窗和期望執(zhí)行時間。不同的工作方式優(yōu)先級不同,但對于多功能PAR,工作方式不能作為確定任務(wù)優(yōu)先級的唯一指標,因為相同的雷達工作方式下的不同任務(wù)也會有著不同的重要程度[19-20]。不同的跟蹤任務(wù),其目標的類型、方位、速度、加速度,都對目標威脅程度的評判有著重要影響。同時,目標的航跡質(zhì)量可以用來評判目標的優(yōu)先級,航跡質(zhì)量越好,目標跟蹤狀態(tài)越好,目標優(yōu)先級則可以相應(yīng)地降低。

表1 雷達主要任務(wù)表

本文在優(yōu)先級表的基礎(chǔ)上,加入目標的方位、速度、加速度及航跡質(zhì)量這些要素設(shè)計一種綜合優(yōu)先級。具體方法是通過將以上4個要素量化并加權(quán),將跟蹤任務(wù)優(yōu)先級細化,同時為了保證細化后的優(yōu)先級不能越級超出其本身優(yōu)先級,對其加權(quán)系數(shù)進行約束，即

(2)

式中，D0=D/Dmax,D為該追蹤任務(wù)的目標距離;Dmax為任務(wù)中所有目標中的距離最大值;同理,將該任務(wù)的目標速度V0、加速度a0、航跡質(zhì)量Y0與所有任務(wù)中該項的最大值做比,以進行歸一化處理。δ1、δ2、δ3、δ4為不小于0的常數(shù)。n為該任務(wù)在優(yōu)先級表(即表1)中的優(yōu)先級。

2 調(diào)度算法

PAR任務(wù)調(diào)度策略主要解決在一個調(diào)度間隔內(nèi)如何分配有限的時間資源,使得PAR能夠合理地、優(yōu)化地滿足處于飽和狀態(tài)下的任務(wù)調(diào)度請求[21-25]。從這點考慮,可以將PAR資源調(diào)度問題作為時間的分配問題來求解。近來AA在資源分配問題上被廣泛應(yīng)用,本文采用AA對任務(wù)PAR時間資源進行分配。

2.1 算法基本思想

進行雷達任務(wù)調(diào)度時,有以下3個原則:①根據(jù)優(yōu)先級原則,當多個任務(wù)競爭同一時間槽時,優(yōu)先級高的優(yōu)先安排。②為了充分利用時間應(yīng)盡量為后續(xù)任務(wù)留出最大連續(xù)空閑時間段,避免分割時間[25]。③為了使雷達的跟蹤精度達到最優(yōu)化,根據(jù)期望時間原則,雷達系統(tǒng)給某任務(wù)安排的真實執(zhí)行時間應(yīng)盡量逼近該任務(wù)申請的期望執(zhí)行時間。

雷達任務(wù)的真實執(zhí)行時間應(yīng)盡量逼近此雷達任務(wù)申請時的期望執(zhí)行時間,這有利于跟蹤雷達精度的最優(yōu)化。AA由拍賣者和競拍者構(gòu)成拍賣機構(gòu),拍賣者提供拍賣物品由競拍者競價,競拍者根據(jù)自身情況決定加價或退出本輪拍賣,拍賣者不斷更新競拍者給出的最高價,直到參加拍賣的競拍者只剩一位,最高價不變拍賣停止。根據(jù)貪婪原則,拍賣者對物品進行拍賣時會追求利潤最大化,即只追求物品拍賣后所得的最高價值。競拍者根據(jù)自身信息對物品進行估價,不盲目競價,同時也不輕易放棄競價。綜合上述AA的特性,結(jié)合雷達任務(wù)調(diào)度的3個原則。算法以時間作為拍賣物品,以待調(diào)度雷達任務(wù)為競拍者。將原則①和原則②作為拍賣條件,建立競拍價值函數(shù)。競拍者的優(yōu)先級越高,拍賣后剩余的連續(xù)時間越長,拍賣者獲得的利潤越高。將原則③作為競拍者的競標期望,建立競標期望函數(shù),雷達調(diào)度任務(wù)競拍到的時間越是逼近其期望執(zhí)行時間,雷達調(diào)度任務(wù)的獲利越高。

2.2 調(diào)度算法設(shè)計

設(shè)在某一調(diào)度間隔為T=[t0,t1]的時間段內(nèi),有未調(diào)度任務(wù)集合M={m1,m2,m3…mn},其中調(diào)度間隔T為拍賣者,拍賣[t0,t1]上的時間。

未調(diào)度任務(wù)集合M內(nèi)的調(diào)度任務(wù)為競拍者。

下面給出本調(diào)度算法中的兩個定義。

定義1在時間段T上,已經(jīng)被調(diào)度任務(wù)競拍得到并占用的時間段為占用段,競拍并得到其時間段的調(diào)度任務(wù)為已定任務(wù)nj。時間段T上的占用段集為Td。

定義2在時間段T上,由屬于調(diào)度任務(wù)mj時間窗內(nèi)的任一時間點ti,作為調(diào)度任務(wù)mj的實際執(zhí)行時間,能夠使任務(wù)mj執(zhí)行完畢,即[ti,ti+tjp]上的所有點均在時間段T上且均不屬于占用段集Td,則稱ti為任務(wù)mj在時間段T上的飽和點,否則稱ti為任務(wù)mj在時間段T上的缺失點。任務(wù)mj在時間段T上的所有飽和點,稱為任務(wù)mj在時間段T上的飽和集Bj。任務(wù)mj在時間段T上的所有缺失點,稱為任務(wù)mj在時間段T上的缺失集Qj。

2.2.1 確定競拍價值函數(shù)

為了評估各調(diào)度任務(wù)給出的競拍價,在上述PAR調(diào)度原則①和原則②的基礎(chǔ)上,建立在某一調(diào)度間隔內(nèi)單個雷達任務(wù)的競拍價值量(auction value),用Vj表示為

Vj=fj(pj,Δtj)

(3)

式中,f(·)為價值量函數(shù);pj表示參與競拍的調(diào)度任務(wù)mj的任務(wù)優(yōu)先級;Δtj為最大連續(xù)剩余時間,即調(diào)度任務(wù)mj競拍到時間段T上的時間后,將原時間段分割成兩個時間段中較大的那個時間段。

Δtj的求法:設(shè)在調(diào)度任務(wù)mj競拍到時間段T上的時間后其任務(wù)執(zhí)行時間為ti,則有

(4)

若在時間段T上,ti的前后均存在占用段,則占用段上的任務(wù)分別記為nT-1和nT+1,如圖1所示。

圖1 最長連續(xù)時間示意圖Fig.1 Diagram of the longest continuous time

此時,可知式(3)也可化為

Vj=fj(pj,ti)

(5)

根據(jù)上述任務(wù)優(yōu)先級原則和最大連續(xù)時間原則可以得出,價值函數(shù)f(·)應(yīng)隨任務(wù)優(yōu)先級的變大和最大剩余時間的變長而增加,反之變小。f(·)可以通過將任務(wù)優(yōu)先級量化和最大剩余連續(xù)時間量化并加權(quán)得到,即

(6)

式中,a,b≥0,a+b=1,a和b為加權(quán)系數(shù)。當a越大b越小,pj對Vj的影響越大,Δtj對Vj的影響越小;當a為0 時,pj對Vj沒有影響;當b為0 時,Δtj對Vj沒有影響。

2.2.2 確定競標期望函數(shù)

在競標過程中,競拍者對于不同的拍賣品獲取期望是不同的,同樣,在本算法中,調(diào)度任務(wù)mj對時間段T上時間點的獲取期望也是不同的。根據(jù)原則(3)可知,時間點ti距離調(diào)度任務(wù)mj的期望時間越近，其相對于任務(wù)mj的價值越高,任務(wù)mj獲取ti的期望越高。因此取調(diào)度任務(wù)mj對于時間段T上的時間點ti的獲取期望函數(shù)為

(7)

式中,使Pj最大的ti稱為調(diào)度任務(wù)mj在時間段T上的最佳時間點tjb,[tjb,tjb+jp]稱為最佳時間段。

2.2.3 調(diào)度流程

設(shè)本輪拍賣是對時間段T進行的第K輪拍賣,每輪拍賣只確定一個已定任務(wù)。第K輪拍賣過程如流程圖2所示。

圖2 拍賣流程圖Fig.2 Flow chart of auction

詳細步驟如下。

步驟1求出未調(diào)度集合M中所有任務(wù)在時間段T上的最佳時間點tjb以及最佳時間段[tjb,tjb+jp]。并給出各自在最佳時間點的競標價fj(pj,tjb)。

步驟2找到給出最高競標價fj(pj,tjb)的調(diào)度任務(wù)mj,令T=j,tTz=tTb并將時間段[tTz,tTz+Tp]暫由任務(wù)mT占有。

步驟3對于任務(wù)集M中除mj以外的其他任務(wù)mk,若時間段[tTz,tTz+Tp]不包含任務(wù)mk的最佳調(diào)度時間段內(nèi)的點,mk則不參與競價,否則根據(jù)mk的最佳調(diào)度時間段內(nèi)的被占用點的位置分為以下4種情況:

①tkb∈[tTz,tTz+Tp]且在[tTz,tTz+Tp]上不存在一點ti使得fk(pk,ti)≥fT(pT,tTz),則任務(wù)mk退出競價。

②tkb∈[tTz,tTz+Tp]且在[tTz,tTz+Tp]上存在一點ti最先使得fk(pk,ti)≥fT(pT,tTz),則取消任務(wù)mT對時間段[tTz,tTz+Tp]的占有狀態(tài),令T=k,tTz=ti且任務(wù)mT暫時占有時間段[tTz,tTz+Tp]。

③(tkb+tkp)∈[tTz,tTz+Tp]且在[tTz,tTz+Tp]上不存在一點ti使得fk(pk,ti)≥fT(pT,tTz),則任務(wù)mk退出競價。

④(tkb+tkp)∈[tTz,tTz+Tp]且在[tTz,tTz+Tp]上存在一點ti最先使得fk(pk,ti)≥fT(pT,tTz),則取消任務(wù)mT對時間段(tkb+tkp)∈[tTz,tTz+Tp]的占有狀態(tài),令T=k,tTz=ti且任務(wù)mT暫時占有時間段[tTz,tTz+Tp]。

重復(fù)步驟3直至在未調(diào)度任務(wù)集合M中除mT以外的其他任務(wù)都退出競價,則轉(zhuǎn)到步驟4。

步驟4將時間段[tTz,tTz+Tp]判為mT所有,并將時間段[tTz,tTz+Tp]加入占用段集Td,令nT=mT,將mT從未調(diào)度任務(wù)集合M中移除并將nT加入已定任務(wù)集合N。更新未調(diào)度任務(wù)集合M中所有任務(wù)的飽和集Bj,若Bj=?且tjl≤t1,將任務(wù)mj從未調(diào)度任務(wù)集合M中移除并從任務(wù)隊列中刪除;若Bj=?且tjl≥t1,將任務(wù)mj從未調(diào)度任務(wù)集合M中移除并推遲到下個調(diào)度間隔中的任務(wù)集合中。

步驟5若未調(diào)度任務(wù)集合M=?,則結(jié)束拍賣,調(diào)度結(jié)束。否則,進入下一輪拍賣。

3 仿真實驗分析

本文選取以下3種雷達工作方式對算法進行仿真實驗:搜索(分為高優(yōu)先級搜索和低優(yōu)先級搜索);驗證;跟蹤(分為精密跟蹤和普通跟蹤)。雷達任務(wù)優(yōu)先級和各任務(wù)駐留時間如表1所示,其中高優(yōu)先級搜索任務(wù)和低優(yōu)先級任務(wù)的任務(wù)周期為60SI,驗證任務(wù)時間窗為20SI,精密跟蹤時間窗為4SI,普通跟蹤時間窗為10SI。調(diào)度間隔取SI=50 ms,仿真時長為1 000SI。δ1、δ2、δ3、δ4分別設(shè)為0.2、0.5、0.2、0.1。

本文采取任務(wù)調(diào)度成功率、實現(xiàn)價值率及平均時間偏移率3項指標來衡量所設(shè)計調(diào)度算法的性能,其具體定義及評估意義如下:

(1) 任務(wù)調(diào)度成功率(scheduling success rate, SSR)為

SSR=N/M

(8)

式中,N為調(diào)度成功的任務(wù)總數(shù);M為請求調(diào)度的任務(wù)總數(shù)。

各類事件調(diào)度成功率(SSRk)為

SSRk=Nk/Mk,k=1,2,…,n

(9)

式中,Nk為第k類雷達事件調(diào)度成功的任務(wù)數(shù);Mk為第k類雷達事件參與調(diào)度的任務(wù)數(shù)。

設(shè)定仿真場景為雷達任務(wù)隨仿真周期的增加趨于飽和,在仿真初期逐漸將目標數(shù)目增加至150個,其中精密跟蹤數(shù)目與普通跟蹤數(shù)的比值為2∶3。分別取不同的a值,觀測本算法在不同的a值下總?cè)蝿?wù)調(diào)度成功率、精密跟蹤調(diào)度成功率、實現(xiàn)價值率及平均時間偏移率,并與EDF算法作比較。仿真結(jié)果如圖3所示。

圖3 任務(wù)總調(diào)度成功率Fig.3 Success rate of task total scheduling

圖3為從仿真開始到仿真雷達周期數(shù)達到1 000的過程中,本文算法在a=0.3和a=0.6時的任務(wù)總調(diào)度成功率與EDF的任務(wù)總調(diào)度成功率對比。EDF算法表示在調(diào)度處理中,截止期越早,任務(wù)優(yōu)先級越高,越優(yōu)先被調(diào)度。EDF算法分為搶占式EDF調(diào)度和非搶占式調(diào)度,本文采用的是搶占式EDF調(diào)度方法。其調(diào)度的充要條件為

(10)

式中,ei和pi分別是執(zhí)行時間和周期。EDF算法作為最優(yōu)的單一處理器調(diào)度算法,非常適用于在雷達任務(wù)不飽和時對低優(yōu)先級任務(wù)進行調(diào)度,但其調(diào)度性能在任務(wù)達到飽和后不斷下降。為了保持EDF算法在單一條件下的優(yōu)良性能,本文將調(diào)度剩余時間加入到拍賣價值函數(shù)中,同樣能夠保證在任務(wù)不飽和情況下的任務(wù)調(diào)度成功率。在仿真剛開始時,雷達任務(wù)以搜索為主,調(diào)度任務(wù)處于不飽和狀態(tài),三者皆具有良好的調(diào)度性能。但隨著仿真周期的增加,不斷有新的目標被確認,雷達任務(wù)逐漸趨于飽和,三者SSR開始下降, EDF算法由于優(yōu)先級判定條件較為單一,導(dǎo)致不能充分利用任務(wù)調(diào)度時間窗的靈活性,因此在仿真后期調(diào)度成功率較低。而本文算法將剩余時間和時間窗均添加到調(diào)度優(yōu)先級因素中,因此能夠較大限度地利用時間窗,提高本算法在飽和任務(wù)情況下的調(diào)度成功率。另外,在仿真前期本文算法在a=0.3時比在a=0.6時稍具優(yōu)勢,但在仿真后期任務(wù)趨于飽和時,兩者性能相似。這是因為在仿真后期雷達調(diào)度任務(wù)主要以跟蹤為主,而a=0.6時更加側(cè)重優(yōu)先保障高優(yōu)先級調(diào)度。

圖4為從仿真開始到仿真雷達周期數(shù)達到1 000的過程中,本文算法在a=0和a=1時的任務(wù)調(diào)度成功率與EDF的任務(wù)調(diào)度成功率對比。

圖4 a、b取特殊值下本算法的任務(wù)調(diào)度成功率Fig.4 Success rate of task scheduling in this algorithm under the special value of a and b

當a=0時本算法的拍賣價值函數(shù)將以最大剩余時間為唯一考慮因素,剩余時間越大拍賣價值越高,這時本算法結(jié)合時間窗可以更加有效地利用調(diào)度間隔內(nèi)的時間,提高算法的調(diào)度成功率。與EDF算法相比,本算法在時間利用上不但學(xué)習(xí)了EDF算法的最早截止時間優(yōu)先調(diào)度思想,并且利用了時間窗概念擴充了算法的靈活性,同時結(jié)合了AA保證了算法的全局性,因此在調(diào)度任務(wù)飽和情況下相比EDF具有更高的任務(wù)調(diào)度成功率。a=1時本算法的拍賣價值函數(shù)將以任務(wù)優(yōu)先級做為唯一考慮因素,優(yōu)先級越大拍賣價值越高。算法雖然能夠保障高優(yōu)先級的優(yōu)先調(diào)度,但是由于沒有考慮時間原則,對于調(diào)度間隔內(nèi)的時間利用不夠充分。因此在a=1時本算法的總?cè)蝿?wù)調(diào)度成功率要比EDF算法更低。

(2) 實現(xiàn)價值率(hit value rate, HVR)為

(11)

式中,pi為任務(wù)i工作方式優(yōu)先級。指成功調(diào)度執(zhí)行的任務(wù)工作方式優(yōu)先級之和與參與調(diào)度的總?cè)蝿?wù)工作方式優(yōu)先級之和的比值。

圖5為本算法在不同a值下的實現(xiàn)價值率及與EDF算法的實現(xiàn)價值率的比較。EDF算法由于算法設(shè)計時的針對性不同,并未將任務(wù)工作方式優(yōu)先級作為任務(wù)調(diào)度的重點考慮因素,而本文算法則將任務(wù)工作優(yōu)先級加入到了拍賣價值函數(shù)中。因此在調(diào)度任務(wù)處于飽和狀態(tài)下,本文算法比EDF算法具有更高的實現(xiàn)價值率,且提高a值可以一定程度上增加實現(xiàn)價值率,但過于提高a值可能會影響到算法的時間利用率,因此在提高a值的時候應(yīng)注意保障算法的時間利用率。

圖5 實現(xiàn)價值率Fig.5 Hit value rate

(3) 平均時間偏移率(average time shifting rate, ATSR)為

(12)

式中,Wi為任務(wù)時間窗長度。指各調(diào)度成功任務(wù)的實際執(zhí)行時刻和期望執(zhí)行時刻差的絕對值與時間窗之比的平均值。

圖6為本算法在不同a值下的平均時間偏移率與EDF算法的平均時間偏移率的比較。EDF算法將截止時間作為調(diào)度優(yōu)先級的主要參考因素并未考察保證時間偏移率下的任務(wù)調(diào)度性能,而本文將期望執(zhí)行時間作為本文拍賣算法的競拍價值函數(shù),保障了算法的時間偏移率,在飽和任務(wù)下比EDF算法具有更低的時間偏移率。因此本文能夠很好地保證任務(wù)調(diào)度的及時性和算法設(shè)計的期望時間原則。

圖6 平均時間偏移率Fig.6 Average time shifting rate

4 結(jié) 論

本文針對多功能PAR任務(wù)調(diào)度中的時間資源調(diào)度問題,提出了基于AA的PAR自適應(yīng)調(diào)度方案。該算法結(jié)合PAR任務(wù)調(diào)度原則,設(shè)計AA的競拍價值函數(shù)和競標期望函數(shù)?；诒疚奶岢龅脑O(shè)計方案和算法流程進行了仿真實驗,分析實驗結(jié)果得到,該算法在可使多功能PAR任務(wù)調(diào)度中的各指標達到優(yōu)良性能。并且通過對比該算法在2種不同a的加權(quán)條件下,算法的3項性能指標,表明算法能夠通過調(diào)整加權(quán)系數(shù)來提高算法的時間利用率,并在高優(yōu)先級任務(wù)的調(diào)度處理中表現(xiàn)出了更高的成功率。