基于拍賣算法的相控陣?yán)走_(dá)任務(wù)調(diào)度方法

李 波, 周靜楊, 高曉光

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

0 引 言

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

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

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

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

1.1 任務(wù)模型

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

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

(1)

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

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

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

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

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

(2)

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

2 調(diào)度算法

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

2.1 算法基本思想

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

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

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

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

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

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

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

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

2.2.1 確定競(jìng)拍價(jià)值函數(shù)

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

Vj=fj(pj,Δtj)

(3)

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

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

(4)

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

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

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

Vj=fj(pj,ti)

(5)

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

(6)

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

2.2.2 確定競(jìng)標(biāo)期望函數(shù)

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

(7)

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

2.2.3 調(diào)度流程

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

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

詳細(xì)步驟如下。

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

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

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

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

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

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

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

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

步驟4將時(shí)間段[tTz,tTz+Tp]判為mT所有,并將時(shí)間段[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ù)隊(duì)列中刪除;若Bj=?且tjl≥t1,將任務(wù)mj從未調(diào)度任務(wù)集合M中移除并推遲到下個(gè)調(diào)度間隔中的任務(wù)集合中。

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

3 仿真實(shí)驗(yàn)分析

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

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

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

SSR=N/M

(8)

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

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

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

(9)

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

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

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

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

(10)

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

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

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

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

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

(11)

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

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

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

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

(12)

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

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

圖6 平均時(shí)間偏移率Fig.6 Average time shifting rate

4 結(jié) 論

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