李夏苗，陳新江，伍國華,*，賀川，龍運(yùn)軍

1.中南大學(xué) 交通運(yùn)輸工程學(xué)院，長沙 410075 2.北京空間信息中繼傳輸技術(shù)研究中心，北京 100094

跟蹤與數(shù)據(jù)中繼衛(wèi)星(Tracking and Data Relay Satellite, TDRS)，簡稱為中繼衛(wèi)星，主要為中、低軌道的航天器提供數(shù)據(jù)中繼、連續(xù)跟蹤與軌道測控服務(wù)[1]。中繼衛(wèi)星具有軌道高、覆蓋面積大的特點(diǎn)，可以擴(kuò)大中低軌道衛(wèi)星與地面站之間的可見時(shí)間窗[1-3]。中繼衛(wèi)星系統(tǒng)作為同步地球靜止軌道的天基傳輸平臺(tái)，不僅需要執(zhí)行預(yù)定任務(wù)，而且還為全球突發(fā)的應(yīng)急任務(wù)服務(wù)，這對中繼衛(wèi)星任務(wù)的有效調(diào)度造成巨大的挑戰(zhàn)[4]。

目前，國內(nèi)外關(guān)于中繼衛(wèi)星的研究主要集中在中繼衛(wèi)星與用戶航天器之間、不同的中繼衛(wèi)星之間的通信鏈路分析，包括天線的捕獲跟蹤與偽隨機(jī)碼的捕獲[5-6]，針對中繼衛(wèi)星任務(wù)調(diào)度的研究相對偏少。關(guān)于中繼衛(wèi)星任務(wù)規(guī)劃問題的研究大多將其描述為帶時(shí)間窗口的并行機(jī)調(diào)度問題(Parallel Machine Scheduling Problem with Time Windows, PMSPTW)[4, 7]，其中中繼衛(wèi)星天線等同于機(jī)器，用戶提交的任務(wù)等同于待加工的工件，并假設(shè)每個(gè)任務(wù)僅能被一顆中繼衛(wèi)星的一條天線執(zhí)行，不允許斷點(diǎn)續(xù)傳，即不允許任務(wù)拆分。針對多中繼衛(wèi)星多用戶航天器大規(guī)模任務(wù)申請的中繼衛(wèi)星調(diào)度場景，研究人員提出了多種模型和算法來解決中繼衛(wèi)星系統(tǒng)任務(wù)規(guī)劃問題。調(diào)度模型包括混合整數(shù)優(yōu)化模型[4, 7]、約束滿足模型[8]和天線校準(zhǔn)時(shí)間變長的規(guī)劃優(yōu)化模型[9]等。求解算法包括精確算法[4, 7]、啟發(fā)式算法[10-15]和智能優(yōu)化算法[8, 16-18]。

在精確算法上，Rojanasoonthon等[7]研究了任務(wù)具有兩個(gè)時(shí)間窗口約束的中繼衛(wèi)星多址鏈路調(diào)度問題，采用分支-定界法對模型進(jìn)行了求解。算法在求解小規(guī)模任務(wù)時(shí)能在較短時(shí)間內(nèi)取得最優(yōu)解，但求解大規(guī)模任務(wù)時(shí)很難在有效或合理時(shí)間內(nèi)取得最優(yōu)解。

在啟發(fā)式算法上，基于規(guī)則的啟發(fā)式算法是現(xiàn)有中繼衛(wèi)星調(diào)度系統(tǒng)中應(yīng)用較多的算法。He等[10]構(gòu)建了一個(gè)隨機(jī)優(yōu)化框架，將中繼衛(wèi)星多址天線動(dòng)態(tài)混合任務(wù)調(diào)度問題等價(jià)地轉(zhuǎn)換為一個(gè)內(nèi)嵌多個(gè)天線時(shí)間分配問題的調(diào)度周期調(diào)整問題，并提出了求解問題的兩種有效算法。Wang等[11]在考慮可見窗口和動(dòng)態(tài)設(shè)置時(shí)間約束的基礎(chǔ)上，建立了異構(gòu)星間鏈路天線指向路徑問題的數(shù)學(xué)模型，提出了一種基于分層調(diào)度策略的兩階段啟發(fā)式求解算法。Liu等[12]構(gòu)建了一個(gè)天線回轉(zhuǎn)時(shí)間感知調(diào)度方案，將中繼衛(wèi)星任務(wù)調(diào)度問題轉(zhuǎn)化為混合整數(shù)非線性規(guī)劃問題，設(shè)計(jì)了一個(gè)多項(xiàng)式時(shí)間算法求解，實(shí)驗(yàn)結(jié)果表明，該方案顯著提高了預(yù)定任務(wù)的完成率。Lin等[13]利用作業(yè)空閑時(shí)間窗的時(shí)域靈活性和統(tǒng)計(jì)特性，提出了一種啟發(fā)式算法，與傳統(tǒng)算法相比，該算法將任務(wù)的完成率提高約11%。

賀川等[14]在對按需申請模式下的中繼衛(wèi)星任務(wù)調(diào)度研究的基礎(chǔ)上，構(gòu)建了沖突任務(wù)檢測和損失機(jī)會(huì)評估模型，并提出了基于沖突風(fēng)險(xiǎn)規(guī)避的任務(wù)規(guī)劃算法，但文中并沒有進(jìn)行相關(guān)仿真實(shí)驗(yàn)。劉潤滋等[15]通過設(shè)定一個(gè)任務(wù)拆分閾值，將服務(wù)時(shí)長大于該閾值的任務(wù)拆分成兩個(gè)服務(wù)時(shí)長相等的子任務(wù)，并設(shè)計(jì)了一種多項(xiàng)式時(shí)間的啟發(fā)式算法。通過實(shí)驗(yàn)驗(yàn)證了其在資源利用率等方面的增益。但任務(wù)拆分閾值的取值對調(diào)度效果的影響較大，且文中僅討論了將任務(wù)拆分成兩個(gè)服務(wù)時(shí)長相等的子任務(wù)。

在智能優(yōu)化算法上，近年來，以蟻群算法(Ant Colony Algorithm, ACA)[16]、遺傳算法(Genetic Algorithm, GA)[8, 17]、人工蜂群(Artificial Bee Colony, ABC)算法[18]、模擬退火(Simulated Annealing, SA)[16]為代表的智能優(yōu)化算法在求解組合優(yōu)化問題方面顯示了較強(qiáng)的能力,在中繼衛(wèi)星調(diào)度問題中也得到了一定的應(yīng)用。比如，顧中舜[16]利用蟻群算法求解中繼衛(wèi)星調(diào)度模型，并與基于遺傳算法和模擬退火算法進(jìn)行比較，結(jié)果表明，蟻群算法在求解時(shí)間和精度上都明顯優(yōu)于另外兩種算法。

基于現(xiàn)有研究文獻(xiàn)的分析，智能優(yōu)化算法只適用于中、小規(guī)模的中繼衛(wèi)星調(diào)度場景的求解，針對多中繼衛(wèi)星多用戶航天器大規(guī)模任務(wù)申請的中繼衛(wèi)星調(diào)度場景，會(huì)出現(xiàn)“維數(shù)災(zāi)”現(xiàn)象，導(dǎo)致智能優(yōu)化算法性能迅速下降，求解時(shí)間也將大大超出實(shí)際調(diào)度工作要求。

根據(jù)當(dāng)前的研究現(xiàn)狀，可以發(fā)現(xiàn)：

1) 有部分文獻(xiàn)研究了中繼衛(wèi)星任務(wù)調(diào)度問題，但是考慮斷點(diǎn)續(xù)傳的中繼衛(wèi)星調(diào)度模型和算法的相關(guān)研究依然缺乏。

2) 隨著天基傳輸需求的日益增長，用戶需求呈多樣化增長[19-20]，中繼系統(tǒng)任務(wù)的規(guī)劃也面臨新的挑戰(zhàn)，考慮斷點(diǎn)續(xù)傳的中繼衛(wèi)星應(yīng)用模式在提高中繼衛(wèi)星系統(tǒng)效能與中繼數(shù)傳任務(wù)完成率等方面具有重要的研究意義。

本文在分析研究考慮斷點(diǎn)續(xù)傳的中繼衛(wèi)星系統(tǒng)任務(wù)規(guī)劃問題的基礎(chǔ)上，建立系統(tǒng)模型及設(shè)計(jì)求解算法，具體貢獻(xiàn)與創(chuàng)新總結(jié)如下：

1) 考慮了在中繼衛(wèi)星任務(wù)調(diào)度周期內(nèi)進(jìn)行斷點(diǎn)續(xù)傳。為最大程度體現(xiàn)任務(wù)調(diào)度的靈活性，本文改進(jìn)了傳統(tǒng)的中繼衛(wèi)星應(yīng)用模式，創(chuàng)新性地提出了考慮斷點(diǎn)續(xù)傳的中繼衛(wèi)星應(yīng)用模式，將中繼衛(wèi)星任務(wù)調(diào)度過程劃分為完整任務(wù)分配和斷點(diǎn)續(xù)傳任務(wù)分配階段。同時(shí)提出了基于沖突風(fēng)險(xiǎn)評估的沖突度計(jì)算方法，將沖突度量化為一定時(shí)段內(nèi)任務(wù)在其當(dāng)前可見時(shí)間窗內(nèi)發(fā)生沖突的概率。

2) 提出一種考慮斷點(diǎn)續(xù)傳的任務(wù)拆分方法，將原任務(wù)集合轉(zhuǎn)化為子任務(wù)集合。以最大化任務(wù)完成率為目標(biāo)函數(shù)，以任務(wù)需求、資源使用等約束為約束條件，構(gòu)建了考慮斷點(diǎn)續(xù)傳的中繼衛(wèi)星任務(wù)規(guī)劃模型。同時(shí)針對問題及模型特點(diǎn)設(shè)計(jì)了考慮斷點(diǎn)續(xù)傳的兩階段調(diào)度算法(Two-stage Scheduling algorithm Considering Breakpoint Transmission, TSCBT)，算法第1階段為完整任務(wù)分配階段，采用基于最小沖突度的資源選擇策略生成較優(yōu)的初始可行調(diào)度方案;算法第2階段為斷點(diǎn)續(xù)傳任務(wù)分配階段，對完整任務(wù)分配階段中未能成功調(diào)度的任務(wù)進(jìn)行斷點(diǎn)續(xù)傳，采用基于最小任務(wù)拆分次數(shù)的資源選擇策略生成最終調(diào)度方案。

3) 通過構(gòu)建一個(gè)多中繼衛(wèi)星多用戶航天器大規(guī)模任務(wù)申請的應(yīng)用場景驗(yàn)證算法的有效性。同時(shí)通過實(shí)驗(yàn)將本文提出的算法與不考慮斷點(diǎn)續(xù)傳的貪婪算法(Greedy Algorithm)、基于最小沖突度的啟發(fā)式算法(Heuristic Algorithm Based on Minimum Conflict Degree, HA-MCD)和基于任務(wù)優(yōu)先級(jí)的啟發(fā)式算法(Heuristic Algorithm based on Task Priority, HA-TP)比較，結(jié)果表明，本文提出的算法能分別將任務(wù)完成率提高7.67%、6.34%和8.67%。最后對算法進(jìn)行性能測試與參數(shù)分析，驗(yàn)證了其在任務(wù)完成率和天線利用率等方面的增益。

1 中繼衛(wèi)星任務(wù)規(guī)劃問題及模型

1.1 問題描述與模型假設(shè)

中繼衛(wèi)星任務(wù)規(guī)劃過程如圖1所示，中繼業(yè)務(wù)系統(tǒng)由3層網(wǎng)絡(luò)組成:位于高軌道的骨干網(wǎng)絡(luò)層、中低軌道的用戶層和地面網(wǎng)絡(luò)層，各層網(wǎng)絡(luò)具體組成部分和功能為：由數(shù)據(jù)中繼衛(wèi)星(Data Relay Satellite, DRS)組成的骨干網(wǎng)絡(luò)負(fù)責(zé)向用戶層提供數(shù)據(jù)中繼服務(wù)。用戶層主要包括各種衛(wèi)星、近空飛行器以及深空探測器。地面網(wǎng)絡(luò)層包括網(wǎng)絡(luò)化地面終端(networked Ground Terminal, GT)、用戶管理中心(User Manage Center, UMC)和數(shù)據(jù)中繼網(wǎng)絡(luò)管理中心(Manage Center of data relay satellite networks, MC)。通常，任務(wù)請求通過地面網(wǎng)絡(luò)從UMC提交到MC。

圖1 中繼衛(wèi)星系統(tǒng)任務(wù)規(guī)劃過程Fig.1 Relay satellite system mission planning process

中繼衛(wèi)星天線任務(wù)調(diào)度是指在滿足任務(wù)需求約束和資源使用約束的前提下，在合理的時(shí)間內(nèi)得到一種最優(yōu)的調(diào)度方案[21]。其調(diào)度難點(diǎn)主要有以下兩點(diǎn)：① 中繼衛(wèi)星調(diào)度問題是NP-hard問題，求解難度大；② 問題規(guī)模大，加上其復(fù)雜性和多約束的特點(diǎn)而難于求解。中繼衛(wèi)星與用戶航天器之間并非時(shí)時(shí)可見，二者在不同的時(shí)段有不同的可見時(shí)間窗口。常將中繼衛(wèi)星調(diào)度問題描述為帶時(shí)間窗的并行機(jī)調(diào)度問題，其約束主要包括任務(wù)服務(wù)時(shí)長、任務(wù)服務(wù)時(shí)間窗口、可見時(shí)間窗口、天線使用約束等[22-23]。

1.2 中繼衛(wèi)星系統(tǒng)基本要素

任務(wù)需求的基本要素可用一個(gè)六元組{pt,startt,endt,ntimet,Rt,ust}表示。其中pi表示任務(wù)的優(yōu)先級(jí)或權(quán)重，任務(wù)優(yōu)先級(jí)是描述任務(wù)重要程度的唯一標(biāo)識(shí)碼，是決定任務(wù)調(diào)度順序的主要參考標(biāo)準(zhǔn)。[startt,endt]表示任務(wù)的服務(wù)時(shí)間窗口，用戶依據(jù)中繼衛(wèi)星相關(guān)管理機(jī)構(gòu)發(fā)布的可用中繼衛(wèi)星資源，結(jié)合自身需求提出任務(wù)在某段可見時(shí)間窗內(nèi)完成的要求。startt表示任務(wù)允許服務(wù)的最早開始時(shí)刻；endt表示任務(wù)允許服務(wù)的最晚結(jié)束時(shí)刻；ntimet表示任務(wù)t期望服務(wù)時(shí)長，即完成任務(wù)t所需的時(shí)間；Rt表示任務(wù)t可用天線集合；ust表示任務(wù)所屬用戶航天器。

圖2 任務(wù)的時(shí)效性特征Fig.2 Time efficiency of task

根據(jù)上述分析，中繼衛(wèi)星任務(wù)調(diào)度可以描述為：制定調(diào)度方案P，在滿足天線使用要求的前提下(同一時(shí)刻同一天線僅能服務(wù)一個(gè)任務(wù))，使得任務(wù)能夠在[startt,endt]內(nèi)被Rt中一副或多副天線服務(wù)，且任務(wù)總服務(wù)時(shí)長等于ntimet。

1.3 中繼衛(wèi)星應(yīng)用模式設(shè)定

假設(shè)圖3為中繼衛(wèi)星的一個(gè)應(yīng)用場景，傳統(tǒng)的中繼衛(wèi)星應(yīng)用模式包括用戶申請方式、資源釋放方式、申請?zhí)幚矸绞?、?jì)劃調(diào)整權(quán)限等相關(guān)要求和規(guī)則[24-25]。上述中繼衛(wèi)星應(yīng)用模式可以歸納為：① 用戶基于任務(wù)需求申請一個(gè)確定的時(shí)間窗口，每項(xiàng)任務(wù)對應(yīng)一個(gè)時(shí)間窗口；② 中繼衛(wèi)星資源(主要是可見時(shí)間窗口資源)周期性釋放；③ 調(diào)度工作根據(jù)任務(wù)申請信息和周期性釋放的中繼衛(wèi)星資源進(jìn)行調(diào)度方案安排。

圖3 中繼衛(wèi)星應(yīng)用場景Fig.3 Relay satellite scheduling scenario

上述應(yīng)用模式主要存在以下問題：① 由于每項(xiàng)任務(wù)只允許申請一個(gè)時(shí)間窗口，且不允許任務(wù)進(jìn)行斷點(diǎn)續(xù)傳，如果在調(diào)度過程中無法滿足該時(shí)間窗口，則該任務(wù)將無法成功調(diào)度;② 難以通過合理調(diào)度實(shí)現(xiàn)不同任務(wù)間的沖突消解，不利于提高調(diào)度工作的靈活性和調(diào)度方案質(zhì)量。

基于以上分析，為更好地適應(yīng)用戶需求特點(diǎn)和工作實(shí)際，提出考慮斷點(diǎn)續(xù)傳的中繼衛(wèi)星應(yīng)用模式：中繼衛(wèi)星任務(wù)調(diào)度主要分兩個(gè)階段進(jìn)行，第1階段為完整任務(wù)分配階段，在此階段中，中繼衛(wèi)星優(yōu)先對不需進(jìn)行斷點(diǎn)續(xù)傳的任務(wù)進(jìn)行調(diào)度；第2階段為斷點(diǎn)續(xù)傳任務(wù)分配階段，在此階段中，將第1階段中未能成功調(diào)度的任務(wù)采用斷點(diǎn)續(xù)傳的方式進(jìn)行調(diào)度。

1.4 優(yōu)化模型

任務(wù)拆分在調(diào)度過程中動(dòng)態(tài)進(jìn)行，具體方法在2.2節(jié)介紹。假設(shè)任務(wù)經(jīng)過拆分后的子任務(wù)集合為{t1,t2,…,tn}，ntimetn表示任務(wù)第n個(gè)子任務(wù)的期望服務(wù)時(shí)長，子任務(wù)服務(wù)時(shí)長滿足：

(1)

用Tα表示T中拆分成功的任務(wù)集，T1表示Tα中任務(wù)拆分后子任務(wù)集合，則有

T1={tn|tn∈{t1,t2,…,tn}=ZC(t),t∈Tα}

(2)

式中：ZC(t)表示原任務(wù)與子任務(wù)之間的轉(zhuǎn)化關(guān)系[15]，即tn∈{t1,t2,…,tn}=ZC(t)可抽象表示為將任務(wù)拆分成n個(gè)子任務(wù)。

用Tβ表示T中不需進(jìn)行拆分的任務(wù)集，即

T=Tα∩Tβ

(3)

將Tβ轉(zhuǎn)化為子任務(wù)集T2，即

T2=Tβ

(4)

(5)

1) 優(yōu)化目標(biāo)

(6)

xt2,r,j,…,xtn,r,j)=1

(7)

2) 任務(wù)需求約束

(8)

(9)

tstartt,r,j≥starttxt,r,j

(10)

(tstartt,r,j+stimet,r,j)xt,r,j≤endt

(11)

(12)

(13)

其中:式(8)和式(9)表示任務(wù)服務(wù)時(shí)長約束;原任務(wù)或子任務(wù)的實(shí)際服務(wù)時(shí)長等于其期望服務(wù)時(shí)長;式(10)表示服務(wù)時(shí)間窗口約束;原任務(wù)或子任務(wù)的實(shí)際執(zhí)行時(shí)刻不早于其允許的最早開始時(shí)刻;式(11)表示原任務(wù)或子任務(wù)的實(shí)際結(jié)束時(shí)刻不晚于其允許的最晚結(jié)束時(shí)刻;式(12)表示每個(gè)原任務(wù)或子任務(wù)只選擇一條天線服務(wù);式(13)表示每個(gè)原任務(wù)或子任務(wù)只在一個(gè)可見時(shí)間窗口內(nèi)調(diào)度。

3) 資源使用約束

定義Et,r為任務(wù)t在天線r中實(shí)際執(zhí)行的時(shí)間段。中繼衛(wèi)星任務(wù)規(guī)劃過程中的資源使用約束主要包括任務(wù)與天線可見時(shí)間窗口和中繼衛(wèi)星天線使用約束：① 中繼衛(wèi)星與用戶航天器的可見時(shí)間窗口的起始時(shí)刻由二者的軌道參數(shù)共同決定，任務(wù)的調(diào)度時(shí)段應(yīng)落在用戶航天器與中繼衛(wèi)星天線的可見時(shí)間窗口內(nèi)；② 同一時(shí)刻同一中繼衛(wèi)星天線僅能執(zhí)行一項(xiàng)任務(wù)。即

(14)

(15)

(adjust+Em,r+rec)∧(adjust+En,r+rec)=?

(16)

其中：式(14)和式(15)為任務(wù)與天線的可見時(shí)間窗約束，式(14)表示原任務(wù)或子任務(wù)的實(shí)際開始時(shí)刻不早于其可見時(shí)間窗的開始時(shí)刻，式(15)表示原任務(wù)或子任務(wù)的實(shí)際結(jié)束不晚于其可見時(shí)間窗的結(jié)束時(shí)刻；式(16)表示同一時(shí)刻同一中繼衛(wèi)星天線僅能執(zhí)行一項(xiàng)任務(wù)。

綜上所述，以最大化任務(wù)完成率為目標(biāo)函數(shù)，以任務(wù)使用約束和資源使用約束為約束條件構(gòu)建了考慮斷點(diǎn)續(xù)傳的中繼衛(wèi)星任務(wù)規(guī)劃模型式(6)～式(16)?？芍獌?yōu)化模型屬于高維混合整數(shù)優(yōu)化問題，具有組合優(yōu)化問題的特征，其解空間隨著資源與任務(wù)數(shù)量的增長將呈指數(shù)增長[24-25]。此外，模型還涉及復(fù)雜的約束條件，采用常見的智能優(yōu)化算法求解將面臨搜索和尋優(yōu)困難。較高的決策變量維度以及復(fù)雜的約束條件使得本模型的求解難度較大[27-28]。一般的通用算法難以直接用于求解本模型。因此，針對問題和模型特點(diǎn)設(shè)計(jì)了考慮斷點(diǎn)續(xù)傳的兩階段調(diào)度算法。

2 考慮斷點(diǎn)續(xù)傳的兩階段調(diào)度算法

關(guān)于中繼衛(wèi)星任務(wù)規(guī)劃的研究大多將其描述為帶時(shí)間窗約束的并行機(jī)調(diào)度問題，并假設(shè)任務(wù)不可拆分。這種假設(shè)沒有充分考慮中繼衛(wèi)星業(yè)務(wù)的實(shí)際情況和部分任務(wù)的特殊需求，造成中繼衛(wèi)星資源浪費(fèi)和服務(wù)時(shí)長較長的任務(wù)完成率低等問題。實(shí)際上，中繼業(yè)務(wù)系統(tǒng)支持對較大的數(shù)據(jù)進(jìn)行拆分分組，不同的分組可在不同的時(shí)間采用不同的路徑回傳[29]，即本文所考慮的斷點(diǎn)續(xù)傳。

在中繼衛(wèi)星任務(wù)規(guī)劃過程中應(yīng)用斷點(diǎn)續(xù)傳機(jī)制的必要性和優(yōu)越性有：① 能夠有效減少中繼衛(wèi)星系統(tǒng)待機(jī)空轉(zhuǎn)時(shí)間，提高中繼衛(wèi)星系統(tǒng)應(yīng)用效能。若不允許拆分任務(wù)，則會(huì)增加中繼衛(wèi)星在其可用時(shí)段內(nèi)的閑置待機(jī)時(shí)間，造成資源浪費(fèi)和降低中繼系統(tǒng)效能。② 斷點(diǎn)續(xù)傳機(jī)制適應(yīng)中繼衛(wèi)星業(yè)務(wù)的實(shí)際需求，能有效提高任務(wù)完成率。調(diào)度服務(wù)時(shí)長較長的任務(wù)需消耗更多的資源，即此類任務(wù)與其他任務(wù)發(fā)生沖突的可能性也就越大，導(dǎo)致任務(wù)調(diào)度成功率低等問題。而這一問題主要是由上述假設(shè)任務(wù)不可拆分導(dǎo)致的。采用斷點(diǎn)續(xù)傳機(jī)制可以有效解決該問題，提高服務(wù)時(shí)長較長的任務(wù)完成率。

假設(shè)任務(wù)i、任務(wù)j和任務(wù)k的期望服務(wù)時(shí)長及其與天線的可見時(shí)間窗口如圖4(a)所示，在以往假定任務(wù)每個(gè)任務(wù)僅能被一顆中繼衛(wèi)星的一條天線執(zhí)行，不允許斷點(diǎn)續(xù)傳的前提下，任務(wù)i、任務(wù)j和任務(wù)k無法同時(shí)調(diào)度成功。

顯然，采用斷點(diǎn)續(xù)傳的調(diào)度方式可以提高服務(wù)時(shí)間較長的任務(wù)的調(diào)度成功率，如圖4(b)所示。其中stimekn,r,j({k1,k2,…,kn}=ZC(k))表示任務(wù)k拆分后的第n個(gè)子任務(wù)與天線r的第j個(gè)可見時(shí)間窗口內(nèi)的實(shí)際服務(wù)時(shí)間。圖4(b)中將任務(wù)k拆分成子任務(wù)k1、k2后，可在不同時(shí)段內(nèi)調(diào)度完成。

考慮斷點(diǎn)續(xù)傳的兩階段調(diào)度算法主要包括以下6個(gè)算法模塊：① 任務(wù)資源匹配；② 任務(wù)拆分；③ 生成任務(wù)可用資源集；④ 計(jì)算可用時(shí)段沖突度；⑤ 任務(wù)插空；⑥ 任務(wù)可用資源集更新。

模塊①是根據(jù)任務(wù)提交的服務(wù)時(shí)間窗口及任務(wù)的服務(wù)時(shí)長，為任務(wù)匹配當(dāng)前可用的時(shí)段資源。模塊②是根據(jù)當(dāng)前任務(wù)的資源匹配結(jié)果，判斷任務(wù)是否需要進(jìn)行拆分，若沒有滿足任務(wù)的服務(wù)時(shí)長需求的可用資源，則將原任務(wù)拆分成若干個(gè)子任務(wù)。需要注意的是，任務(wù)拆分操作是在調(diào)度過程中實(shí)時(shí)動(dòng)態(tài)地進(jìn)行。模塊③是根據(jù)模塊①的匹配結(jié)果和模塊②的拆分結(jié)果，生成當(dāng)前任務(wù)的可用資源集合。模塊④是根據(jù)任務(wù)可用資源集，計(jì)算每個(gè)任務(wù)可用時(shí)段的沖突度。沖突度是評價(jià)在同一中繼衛(wèi)星天線下任務(wù)可用資源被其他任務(wù)的可用時(shí)段侵占程度。因此，為了提高資源的利用率和任務(wù)完成率，優(yōu)先選擇最小沖突度的可用時(shí)段作為任務(wù)的執(zhí)行時(shí)段。模塊⑤是選定任務(wù)的執(zhí)行時(shí)段后，進(jìn)行任務(wù)插空，常見的任務(wù)插空策略有緊前策略、緊后策略、隨機(jī)策略。模塊⑥是任務(wù)調(diào)度成功后，刷新任務(wù)集和任務(wù)可用資源集。

圖4 斷點(diǎn)續(xù)傳示意圖Fig.4 Diagram of breakpoint transmission

考慮斷點(diǎn)續(xù)傳的兩階段調(diào)度算法屬于構(gòu)造型算法，算法著重考慮任務(wù)需求的差異性和中繼衛(wèi)星資源的利用率，通過采用合理的解構(gòu)造策略，生成較優(yōu)的調(diào)度方案。在完整任務(wù)分配階段，重點(diǎn)考察任務(wù)之間沖突度，對任務(wù)所有可用時(shí)段進(jìn)行沖突度評價(jià)，根據(jù)評價(jià)結(jié)果選擇任務(wù)的可用資源，采用基于最小沖突度的沖突規(guī)避策略生成較優(yōu)的初始可行調(diào)度方案。在斷點(diǎn)續(xù)傳任務(wù)分配階段，著重考慮中繼衛(wèi)星資源的利用率和用戶的實(shí)際需求，對完整任務(wù)分配階段中未能成功調(diào)度的任務(wù)進(jìn)行斷點(diǎn)續(xù)傳。同時(shí)兼顧中繼業(yè)務(wù)的實(shí)際情況：在中繼衛(wèi)星任務(wù)調(diào)度過程中，任務(wù)切換時(shí)天線會(huì)有一定的空轉(zhuǎn)時(shí)間[30-31]，任務(wù)切換次數(shù)增多，天線空轉(zhuǎn)時(shí)間越多，勢必會(huì)造成天線可用資源的損耗和浪費(fèi)。故在此階段采用基于最小任務(wù)拆分次數(shù)的資源選擇策略，生成最終調(diào)度方案。

基于上述分析，設(shè)定任務(wù)進(jìn)行斷點(diǎn)續(xù)傳的兩個(gè)原則：① 任務(wù)拆分后的子任務(wù)優(yōu)先在同一中繼衛(wèi)星進(jìn)行調(diào)度；② 基于最小拆分次數(shù)進(jìn)行子任務(wù)的資源匹配和任務(wù)插空。

2.1 任務(wù)資源匹配方法

任務(wù)資源匹配主要是將任務(wù)提交的服務(wù)時(shí)間窗口、服務(wù)時(shí)長與其可見時(shí)間窗口對比，匹配結(jié)果為生成當(dāng)前任務(wù)可用的時(shí)段資源，并生成決策變量的約束信息。任務(wù)資源匹配具體方法如下。

(17)

圖5 任務(wù)資源匹配方法示意圖Fig.5 Diagram of task resource matching method

2.2 任務(wù)拆分

針對調(diào)度過程中服務(wù)時(shí)間較長或優(yōu)先級(jí)較低的任務(wù)在資源匹配階段難以匹配到合適可用資源的問題，提出了一種考慮斷點(diǎn)續(xù)傳的任務(wù)拆分方法，該方法是在調(diào)度過程中對任務(wù)的動(dòng)態(tài)處理。根據(jù)資源匹配結(jié)果，對于任務(wù)，若任務(wù)最長的可用時(shí)間窗口不滿足其服務(wù)時(shí)長需求，即

(18)

(19)

式中：ntimet1和ntimet2分別表示任務(wù)t的第1和第2個(gè)子任務(wù)的期望服務(wù)時(shí)長。任務(wù)t拆分后的子任務(wù)優(yōu)先級(jí)、允許執(zhí)行的最早開始時(shí)刻、最晚結(jié)束時(shí)刻、服務(wù)天線和所屬用戶航天器與原任務(wù)一致，子任務(wù)期望服務(wù)時(shí)長的累加和等于原任務(wù)的期望服務(wù)時(shí)長，即

ntimet1+ntimet2=ntimet

(20)

(21)

值得注意的是，當(dāng)最長可見時(shí)間窗口不滿足任務(wù)t1、t2的服務(wù)時(shí)長需求時(shí)，又可將t1、t2拆分成更細(xì)小的子任務(wù)，即t1、t2拆分后的子任務(wù)都可視為任務(wù)的子任務(wù)，令Tα=Tα∪{t}，即

(22)

2.3 生成任務(wù)可用資源集

2.4 計(jì)算任務(wù)可用時(shí)段沖突度

不同任務(wù)可用時(shí)間窗口存在交叉重疊，由于任務(wù)執(zhí)行時(shí)刻存在不確定性，即可視為任務(wù)服務(wù)時(shí)段可在其可用時(shí)間窗內(nèi)滑動(dòng)，同時(shí)受天線使用約束(同一天線同一時(shí)刻僅能執(zhí)行一項(xiàng)任務(wù))限制，不同任務(wù)在同一天線下的可用時(shí)間窗口可能存在沖突，如圖6所示。

圖6 任務(wù)可用時(shí)段沖突示意圖Fig.6 Diagram of conflict at avaliable task time

圖7 沖突度計(jì)算方法示意圖Fig.7 Conflict degree calculation method

tstartj,r,n-tstarti,r,m>adjust+ntimei

(23)

tstarti,r,m-tstartj,r,n>adjust+ntimej

(24)

則任務(wù)i、j在當(dāng)前可用時(shí)間窗內(nèi)不沖突。當(dāng)滿足以下任一條件時(shí)：

tstartj,r,n-tstarti,r,m

(25)

tstarti,r,m-tstartj,r,n

(26)

(27)

式中：pi為任務(wù)i的優(yōu)先級(jí)或權(quán)重。在任務(wù)調(diào)度過程中，為了提高任務(wù)調(diào)度的成功率和減小對其他任務(wù)調(diào)度的干擾和資源損耗，總是優(yōu)先選擇沖突度最小的可用時(shí)段作為當(dāng)前任務(wù)的執(zhí)行時(shí)段。

2.5 任務(wù)插空策略

圖8 任務(wù)插空策略Fig.8 Task insertion strategy

2.6 任務(wù)可用資源集更新

任務(wù)調(diào)度成功后，會(huì)占用任務(wù)與天線的可見時(shí)間窗口，其他用戶航天器與該中繼衛(wèi)星的天線的可見時(shí)段可能與任務(wù)占用時(shí)段存在交集。由于同一中繼衛(wèi)星同一時(shí)刻僅能執(zhí)行一項(xiàng)任務(wù)，所以需要刷新可見時(shí)間窗口。假設(shè)調(diào)度過程中任務(wù)服務(wù)時(shí)間為(T3,T4)，則可根據(jù)(T3,T4)對其他任務(wù)可見時(shí)間窗口的侵占情況刷新任務(wù)資源，將各類情況總結(jié)如表1所示。

表1 不同情況下資源刷新結(jié)果Table 1 Resource refresh results in different situations

2.7 算法框架與流程

基于上述分析，考慮斷點(diǎn)續(xù)傳的兩階段調(diào)度算法如算法1所示。

算法1考慮斷點(diǎn)續(xù)傳的兩階段調(diào)度算法1.初始化Tα=?,TaskResource1=?,TaskResource2=?,i=1,T為任務(wù)集,P為調(diào)度方案2.將任務(wù)按照任務(wù)優(yōu)先級(jí)排序,生成任務(wù)集T=1,2,…,i,…,n{}3.完整任務(wù)分配階段4.foreachi∈T5.進(jìn)行任務(wù)資源匹配,生成任務(wù)可用資源集TaskResource1=pi,aji,r,bji,r,ntimei,ri,usi{}6.計(jì)算所有可用時(shí)段aji,r,bji,r[]沖突度cji,r7.按cji,r數(shù)值由小到大的順序遍歷aji,r,bji,r[]8.if?bji,r-aji,r()≥ntimeii∈T()9.任務(wù)調(diào)度成功,更新TaskResource1、P10.elseif?bji,r-aji,r()

觀察上述算法流程可知，完整任務(wù)分配階段(第4～13行)算法復(fù)雜度為O(nW+nRa)，其中n為任務(wù)數(shù)，W為可見時(shí)間窗口數(shù)量，Ra為可用時(shí)間窗口數(shù)量，由于W>Ra，所以完整任務(wù)分配階段(第4～13行)算法時(shí)間復(fù)雜度為O(nW)。同理，斷點(diǎn)續(xù)傳任務(wù)分配階段(第15～25行)算法時(shí)間復(fù)雜度為O(|Tα|W)，其中，|Tα|為需進(jìn)行斷點(diǎn)續(xù)傳的任務(wù)數(shù)量。由于|Tα|≤n，即O(|Tα|W)≤O(nW)。故所提算法的時(shí)間復(fù)雜度為O(nW)，所提算法可在多項(xiàng)式時(shí)間內(nèi)執(zhí)行完畢。

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

3.1 任務(wù)需求仿真

在任務(wù)需求仿真階段，分別運(yùn)用正態(tài)分布確定任務(wù)的期望服務(wù)時(shí)長及其服務(wù)時(shí)間窗口，即

(28)

(29)

startt=start+rand()×(end-start)

(30)

endt=startt+abs(normrnd(cmean,cstd))

(31)

假設(shè)在任務(wù)申請階段中共收到300個(gè)任務(wù)，任務(wù)需求參數(shù)設(shè)置如表2所示。

表2 任務(wù)需求參數(shù)設(shè)置Table 2 Task requirement parameter setting

3.2 仿真場景參數(shù)設(shè)置

在仿真實(shí)驗(yàn)中構(gòu)建了一個(gè)調(diào)度周期為1天，由3顆中繼衛(wèi)星、10個(gè)用戶航天器的中繼衛(wèi)星應(yīng)用場景，每顆中繼衛(wèi)星攜帶一副單址天線用于執(zhí)行常規(guī)任務(wù)，天線對準(zhǔn)時(shí)間為360 s，復(fù)位時(shí)間為240 s，應(yīng)用場景參數(shù)設(shè)置如表3所示。

表3 應(yīng)用場景參數(shù)設(shè)置Table 3 Application scenario parameter setting

3.3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)平臺(tái)為2.80 GHz Intel Core CPU、8 GB內(nèi)存、Windows 10操作系統(tǒng)的PC機(jī)。由于考慮斷點(diǎn)續(xù)傳的中繼衛(wèi)星應(yīng)用模式目前沒有標(biāo)準(zhǔn)測試集可供調(diào)用，故首先運(yùn)用STK與MATLAB軟件進(jìn)行資源與任務(wù)需求仿真，獲取實(shí)驗(yàn)數(shù)據(jù)，再運(yùn)用MATLAB R2016b對本文所提算法進(jìn)行測試。

運(yùn)用考慮斷點(diǎn)續(xù)傳的兩階段調(diào)度算法對上述實(shí)例進(jìn)行測試，同時(shí)，在同一中繼衛(wèi)星調(diào)度場景下，將考慮斷點(diǎn)續(xù)傳的兩階段調(diào)度算法(TSCBT)與貪婪算法(Greedy Algorithm)、基于最小沖突度的啟發(fā)式算法(HA-MCD)和基于任務(wù)優(yōu)先級(jí)的啟發(fā)式算法(HA-TP)比較。其中貪婪算法的貪婪策略為選取單位時(shí)間內(nèi)權(quán)重(Wt=pt/ntimet)最大的任務(wù)，HA-MCD除了不考慮任務(wù)的斷點(diǎn)續(xù)傳，其他算法模塊與TSCBT一致。HA-TP主要步驟如下：

步驟1將任務(wù)按照任務(wù)優(yōu)先級(jí)排序，形成任務(wù)集T。

步驟2依次從任務(wù)集T中選取優(yōu)先級(jí)最高的任務(wù)t。

步驟3遍歷任務(wù)t的可用時(shí)段資源，為其安排可用資源，并將任務(wù)t從任務(wù)集T中刪除。如果T=?，算法結(jié)束；否則轉(zhuǎn)步驟2。

實(shí)驗(yàn)結(jié)果如表4所示，結(jié)果表明，TSCBT僅用了0.218 84 s就完成了對300個(gè)任務(wù)的調(diào)度，任務(wù)完成率達(dá)到84.67%，算法整體性能較好。此外，TSCBT能顯著將Greedy Algorithm、HA-MCD和HA-TP的任務(wù)完成率從分別從77.00%、78.33%和76.00%提高到84.67%，HA-MCD能分別將Greedy Algorithm和HA-TP的任務(wù)完成率從77.00%和76.00%提高到78.33%。這驗(yàn)證了采用斷點(diǎn)續(xù)傳機(jī)制對任務(wù)完成率的增益，同時(shí)也驗(yàn)證了基于最小沖突度的任務(wù)資源選擇策略能夠有效地實(shí)現(xiàn)沖突規(guī)避。

表4 不同算法運(yùn)行結(jié)果Table 4 Running results of different algorithm

從TSCBT的求解結(jié)果中，選取10個(gè)任務(wù)的調(diào)度方案進(jìn)行分析，如表5所示，其中調(diào)度時(shí)段為2019年5月15日0～24時(shí)，“+1”表示任務(wù)以完整任務(wù)分配方式調(diào)度(即任務(wù)不拆分)，“+2”表示任務(wù)以斷點(diǎn)續(xù)傳分配方式調(diào)度。觀察表5可知，不拆分方式調(diào)度的任務(wù)，任務(wù)從開始到完成的持續(xù)時(shí)間為單一的時(shí)間段。以斷點(diǎn)續(xù)傳方式調(diào)度的任務(wù)，由于任務(wù)被拆分成若干個(gè)子任務(wù)，子任務(wù)在多個(gè)可用時(shí)間段內(nèi)完成，所以任務(wù)從開始到完成的持續(xù)時(shí)間由若干時(shí)間段組成。

表5 TSCBT部分調(diào)度方案Table 5 Partial scheduling plans of TSCBT

3.4 算法性能測試與參數(shù)分析

為了測試本文所提出算法的性能，同時(shí)對影響算法的參數(shù)進(jìn)行分析，在3.2節(jié)構(gòu)建的中繼衛(wèi)星調(diào)度應(yīng)用場景中，依次分析不同任務(wù)規(guī)模、不同用戶航天器數(shù)量、不同中繼衛(wèi)星數(shù)量和不同服務(wù)時(shí)長對算法的影響。分30組實(shí)驗(yàn)進(jìn)行測試，各組實(shí)驗(yàn)具體參數(shù)設(shè)置如表6所示。最后分別運(yùn)用TSCBT、Greedy Algorithm、HA-MCD和HA-TP算法對以上30組不同參數(shù)設(shè)置的調(diào)度場景進(jìn)行測試。實(shí)驗(yàn)結(jié)果如圖9～圖14、表7～表9所示。

表6 實(shí)驗(yàn)參數(shù)設(shè)置Table 6 Experimental parameters setting

圖9 不同任務(wù)規(guī)模下算法性能測試結(jié)果Fig.9 Algorithm performance test results for different number of tasks

圖10 不同用戶航天器數(shù)量下算法性能測試結(jié)果Fig.10 Algorithm performance test results for different number of spacecraft

圖11 不同中繼衛(wèi)星數(shù)量下算法性能測試結(jié)果Fig.11 Algorithm performance test results for different number of TDRSs

圖12 任務(wù)完成率提升程度對比Fig.12 Comparison of task completion rate

圖13 天線利用率對比Fig.13 Comparison of antenna utilization ratios

實(shí)驗(yàn)結(jié)果表明，在求解中繼衛(wèi)星調(diào)度問題時(shí)，TSCBT算法總是優(yōu)于Greedy Algorithm、HA-MCD和HA-TP算法，考慮斷點(diǎn)續(xù)傳的中繼衛(wèi)星應(yīng)用模式對中繼衛(wèi)星任務(wù)完成率和資源利用率有明顯的增益。算法評價(jià)指標(biāo)和運(yùn)行時(shí)間隨用戶航天器數(shù)量的波動(dòng)呈現(xiàn)小幅度波動(dòng)，可見用戶航天器數(shù)量對算法性能和調(diào)度工作影響較小。

值得注意的是，4種算法的任務(wù)完成數(shù)和任務(wù)完成率均隨任務(wù)規(guī)模和中繼衛(wèi)星數(shù)量的增大而增大，當(dāng)?shù)竭_(dá)一定程度之后，任務(wù)完成數(shù)和任務(wù)完成率增長速度明顯減緩。前者是因?yàn)樵诋?dāng)前算法性能下，中繼衛(wèi)星天線資源已接近其最大利用率，后者是因?yàn)槿蝿?wù)可用資源已接近其最大利用率，任務(wù)完成率難以實(shí)現(xiàn)進(jìn)一步增長[32-33]。同時(shí)，隨著任務(wù)數(shù)量和中繼衛(wèi)星數(shù)量的增多，4種算法的任務(wù)完成數(shù)的增長速度遠(yuǎn)小于任務(wù)申請的增長速度，算法運(yùn)行時(shí)間也隨之增長，可見二者對調(diào)度工作和算法性能有較大影響。

觀察圖12～圖14可知，相比于沒有考慮斷點(diǎn)續(xù)傳的Greedy Algorithm、HA-MCD和HA-TP算法，TSCBT對服務(wù)時(shí)長較長的任務(wù)調(diào)度成功率有明顯的增益，且其天線利用率也高于其他3種算法，波動(dòng)較為平穩(wěn)。

圖14 不同調(diào)度方式完成任務(wù)占比Fig.14 Ratio of tasks completed for different scheduling modes

表7 不同任務(wù)規(guī)模下算法性能測試結(jié)果
Table 7 Algorithm performance test results for different number of tasks

實(shí)驗(yàn)編號(hào)任務(wù)完成數(shù)任務(wù)完成率/%算法運(yùn)行時(shí)間/sTSCBTGreedyHA-MCDHA-TPTSCBTGreedyHA-MCDHA-TPTSCBTGreedyHA-MCDHA-TPC119218318618096.0091.5093.0090.000.099430.938120.103830.08472C225423123522884.6777.0078.3376.000.218840.212230.218690.20373C330824225223577.0060.5063.0058.750.468850.432730.457820.38753C431924424824063.8048.8049.6048.000.703740.684060.708750.54518C533524925624355.8341.5042.6740.501.236551.087461.153930.83385C633325025524747.5737.7136.4335.292.066361.785621.792951.26859C733825927125242.2532.3633.8831.503.004712.776253.306452.28433

表8 不同用戶航天器數(shù)量下算法性能測試結(jié)果Table 8 Algorithm performance test results for different number of spacecraft

表9 不同中繼衛(wèi)星數(shù)量下算法性能測試結(jié)果Table 9 Algorithm performance test results for different number of TDRSs

TSCBT能顯著提高任務(wù)完成率的主要原因可從斷點(diǎn)續(xù)傳機(jī)制在任務(wù)規(guī)劃和資源利用上的優(yōu)越性來分析：① TSCBT在調(diào)度過程中應(yīng)用了斷點(diǎn)續(xù)傳機(jī)制，即允許對任務(wù)進(jìn)行合理拆分，使其在多個(gè)時(shí)間窗口內(nèi)完成，這大大提高了任務(wù)成功調(diào)度的可能性；② 在資源利用方面，若不考慮斷點(diǎn)續(xù)傳，優(yōu)先級(jí)較低或服務(wù)時(shí)長較長的任務(wù)通常面臨著調(diào)度資源不足、可用資源不滿足任務(wù)服務(wù)時(shí)長需求等難題，造成此類任務(wù)完成率低。而采用斷點(diǎn)續(xù)傳機(jī)制能充分利用中繼衛(wèi)星剩余可用資源，為任務(wù)規(guī)劃提供更多可用資源，進(jìn)一步提高任務(wù)成功調(diào)度的可能性。

在算法的調(diào)度開銷上，可以從兩方面進(jìn)行討論：① 理論上4種算法的時(shí)間復(fù)雜都為O(nW)；② 仿真實(shí)驗(yàn)中4種算法的運(yùn)行時(shí)間差距不大。實(shí)際上，TSCBT算法比Greedy Algorithm、HA-MCD和HA-TP算法增加了對斷點(diǎn)續(xù)傳任務(wù)的調(diào)度規(guī)劃，而TSCBT不僅顯著提高了預(yù)定任務(wù)的完成率，且運(yùn)行時(shí)間與其他3種算法幾乎一致，可見與傳統(tǒng)中繼衛(wèi)星應(yīng)用模式相比，采用斷點(diǎn)續(xù)傳機(jī)制能有效降低調(diào)度開銷，提高任務(wù)完成率。

4 結(jié) 論

本文在分析任務(wù)拆分機(jī)制的基礎(chǔ)上，構(gòu)建了考慮斷點(diǎn)續(xù)傳的中繼衛(wèi)星單址天線調(diào)度模型和設(shè)計(jì)了考慮斷點(diǎn)續(xù)傳的兩階段調(diào)度算法，獲得以下結(jié)論：

1) 考慮斷點(diǎn)續(xù)傳的中繼衛(wèi)星任務(wù)規(guī)劃模型闡明了任務(wù)拆分機(jī)制，統(tǒng)一表征了原任務(wù)與子任務(wù)的內(nèi)在聯(lián)系，對創(chuàng)新和開發(fā)中繼衛(wèi)星系統(tǒng)應(yīng)用模式具有一定的借鑒意義。

2) 基于沖突風(fēng)險(xiǎn)評估的沖突度量化方法提供了一種計(jì)算可滑動(dòng)時(shí)間窗口沖突度大小的方法，根據(jù)其原理衍生的基于最小沖突度的沖突規(guī)避策略能分別將任務(wù)完成率提高1.33%和2.33%，有效地降低了資源損耗。

3) 考慮斷點(diǎn)續(xù)傳的兩階段調(diào)度算法采用基于最小沖突度和基于最小任務(wù)拆分次數(shù)的資源選擇策略，能分別將任務(wù)完成率提高7.67%、6.34%和8.67%，將天線利用率提高2.00%以上，顯著提升了中繼系統(tǒng)應(yīng)用效能。