考慮斷點續傳的中繼衛星調度模型及啟發式算法

李夏苗，陳新江，伍國華,*，賀川，龍運軍

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

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

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

在精確算法上，Rojanasoonthon等[7]研究了任務具有兩個時間窗口約束的中繼衛星多址鏈路調度問題，采用分支-定界法對模型進行了求解。算法在求解小規模任務時能在較短時間內取得最優解，但求解大規模任務時很難在有效或合理時間內取得最優解。

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

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

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

基于現有研究文獻的分析，智能優化算法只適用于中、小規模的中繼衛星調度場景的求解，針對多中繼衛星多用戶航天器大規模任務申請的中繼衛星調度場景，會出現“維數災”現象，導致智能優化算法性能迅速下降，求解時間也將大大超出實際調度工作要求。

根據當前的研究現狀，可以發現：

1) 有部分文獻研究了中繼衛星任務調度問題，但是考慮斷點續傳的中繼衛星調度模型和算法的相關研究依然缺乏。

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

本文在分析研究考慮斷點續傳的中繼衛星系統任務規劃問題的基礎上，建立系統模型及設計求解算法，具體貢獻與創新總結如下：

1) 考慮了在中繼衛星任務調度周期內進行斷點續傳。為最大程度體現任務調度的靈活性，本文改進了傳統的中繼衛星應用模式，創新性地提出了考慮斷點續傳的中繼衛星應用模式，將中繼衛星任務調度過程劃分為完整任務分配和斷點續傳任務分配階段。同時提出了基于沖突風險評估的沖突度計算方法，將沖突度量化為一定時段內任務在其當前可見時間窗內發生沖突的概率。

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

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

1 中繼衛星任務規劃問題及模型

1.1 問題描述與模型假設

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

圖1 中繼衛星系統任務規劃過程Fig.1 Relay satellite system mission planning process

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

1.2 中繼衛星系統基本要素

任務需求的基本要素可用一個六元組{pt,startt,endt,ntimet,Rt,ust}表示。其中pi表示任務的優先級或權重，任務優先級是描述任務重要程度的唯一標識碼，是決定任務調度順序的主要參考標準。[startt,endt]表示任務的服務時間窗口，用戶依據中繼衛星相關管理機構發布的可用中繼衛星資源，結合自身需求提出任務在某段可見時間窗內完成的要求。startt表示任務允許服務的最早開始時刻；endt表示任務允許服務的最晚結束時刻；ntimet表示任務t期望服務時長，即完成任務t所需的時間；Rt表示任務t可用天線集合；ust表示任務所屬用戶航天器。

圖2 任務的時效性特征Fig.2 Time efficiency of task

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

1.3 中繼衛星應用模式設定

假設圖3為中繼衛星的一個應用場景，傳統的中繼衛星應用模式包括用戶申請方式、資源釋放方式、申請處理方式、計劃調整權限等相關要求和規則[24-25]。上述中繼衛星應用模式可以歸納為：① 用戶基于任務需求申請一個確定的時間窗口，每項任務對應一個時間窗口；② 中繼衛星資源(主要是可見時間窗口資源)周期性釋放；③ 調度工作根據任務申請信息和周期性釋放的中繼衛星資源進行調度方案安排。

圖3 中繼衛星應用場景Fig.3 Relay satellite scheduling scenario

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

基于以上分析，為更好地適應用戶需求特點和工作實際，提出考慮斷點續傳的中繼衛星應用模式：中繼衛星任務調度主要分兩個階段進行，第1階段為完整任務分配階段，在此階段中，中繼衛星優先對不需進行斷點續傳的任務進行調度；第2階段為斷點續傳任務分配階段，在此階段中，將第1階段中未能成功調度的任務采用斷點續傳的方式進行調度。

1.4 優化模型

任務拆分在調度過程中動態進行，具體方法在2.2節介紹。假設任務經過拆分后的子任務集合為{t1,t2,…,tn}，ntimetn表示任務第n個子任務的期望服務時長，子任務服務時長滿足：

(1)

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

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

(2)

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

用Tβ表示T中不需進行拆分的任務集，即

T=Tα∩Tβ

(3)

將Tβ轉化為子任務集T2，即

T2=Tβ

(4)

(5)

1) 優化目標

(6)

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

(7)

2) 任務需求約束

(8)

(9)

tstartt,r,j≥starttxt,r,j

(10)

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

(11)

(12)

(13)

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

3) 資源使用約束

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

(14)

(15)

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

(16)

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

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

2 考慮斷點續傳的兩階段調度算法

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

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

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

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

考慮斷點續傳的兩階段調度算法主要包括以下6個算法模塊：① 任務資源匹配；② 任務拆分；③ 生成任務可用資源集；④ 計算可用時段沖突度；⑤ 任務插空；⑥ 任務可用資源集更新。

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

圖4 斷點續傳示意圖Fig.4 Diagram of breakpoint transmission

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

基于上述分析，設定任務進行斷點續傳的兩個原則：① 任務拆分后的子任務優先在同一中繼衛星進行調度；② 基于最小拆分次數進行子任務的資源匹配和任務插空。

2.1 任務資源匹配方法

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

(17)

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

2.2 任務拆分

針對調度過程中服務時間較長或優先級較低的任務在資源匹配階段難以匹配到合適可用資源的問題，提出了一種考慮斷點續傳的任務拆分方法，該方法是在調度過程中對任務的動態處理。根據資源匹配結果，對于任務，若任務最長的可用時間窗口不滿足其服務時長需求，即

(18)

(19)

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

ntimet1+ntimet2=ntimet

(20)

(21)

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

(22)

2.3 生成任務可用資源集

2.4 計算任務可用時段沖突度

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

圖6 任務可用時段沖突示意圖Fig.6 Diagram of conflict at avaliable task time

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

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

(23)

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

(24)

則任務i、j在當前可用時間窗內不沖突。當滿足以下任一條件時：

tstartj,r,n-tstarti,r,m

(25)

tstarti,r,m-tstartj,r,n

(26)

(27)

式中：pi為任務i的優先級或權重。在任務調度過程中，為了提高任務調度的成功率和減小對其他任務調度的干擾和資源損耗，總是優先選擇沖突度最小的可用時段作為當前任務的執行時段。

2.5 任務插空策略

圖8 任務插空策略Fig.8 Task insertion strategy

2.6 任務可用資源集更新

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

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

2.7 算法框架與流程

基于上述分析，考慮斷點續傳的兩階段調度算法如算法1所示。

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

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

3 仿真實驗

3.1 任務需求仿真

在任務需求仿真階段，分別運用正態分布確定任務的期望服務時長及其服務時間窗口，即

(28)

(29)

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

(30)

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

(31)

假設在任務申請階段中共收到300個任務，任務需求參數設置如表2所示。

表2 任務需求參數設置Table 2 Task requirement parameter setting

3.2 仿真場景參數設置

在仿真實驗中構建了一個調度周期為1天，由3顆中繼衛星、10個用戶航天器的中繼衛星應用場景，每顆中繼衛星攜帶一副單址天線用于執行常規任務，天線對準時間為360 s，復位時間為240 s，應用場景參數設置如表3所示。

表3 應用場景參數設置Table 3 Application scenario parameter setting

3.3 實驗結果

實驗平臺為2.80 GHz Intel Core CPU、8 GB內存、Windows 10操作系統的PC機。由于考慮斷點續傳的中繼衛星應用模式目前沒有標準測試集可供調用，故首先運用STK與MATLAB軟件進行資源與任務需求仿真，獲取實驗數據，再運用MATLAB R2016b對本文所提算法進行測試。

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

步驟1將任務按照任務優先級排序，形成任務集T。

步驟2依次從任務集T中選取優先級最高的任務t。

步驟3遍歷任務t的可用時段資源，為其安排可用資源，并將任務t從任務集T中刪除。如果T=?，算法結束；否則轉步驟2。

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

表4 不同算法運行結果Table 4 Running results of different algorithm

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

表5 TSCBT部分調度方案Table 5 Partial scheduling plans of TSCBT

3.4 算法性能測試與參數分析

為了測試本文所提出算法的性能，同時對影響算法的參數進行分析，在3.2節構建的中繼衛星調度應用場景中，依次分析不同任務規模、不同用戶航天器數量、不同中繼衛星數量和不同服務時長對算法的影響。分30組實驗進行測試，各組實驗具體參數設置如表6所示。最后分別運用TSCBT、Greedy Algorithm、HA-MCD和HA-TP算法對以上30組不同參數設置的調度場景進行測試。實驗結果如圖9～圖14、表7～表9所示。

表6 實驗參數設置Table 6 Experimental parameters setting

圖9 不同任務規模下算法性能測試結果Fig.9 Algorithm performance test results for different number of tasks

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

圖11 不同中繼衛星數量下算法性能測試結果Fig.11 Algorithm performance test results for different number of TDRSs

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

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

實驗結果表明，在求解中繼衛星調度問題時，TSCBT算法總是優于Greedy Algorithm、HA-MCD和HA-TP算法，考慮斷點續傳的中繼衛星應用模式對中繼衛星任務完成率和資源利用率有明顯的增益。算法評價指標和運行時間隨用戶航天器數量的波動呈現小幅度波動，可見用戶航天器數量對算法性能和調度工作影響較小。

值得注意的是，4種算法的任務完成數和任務完成率均隨任務規模和中繼衛星數量的增大而增大，當到達一定程度之后，任務完成數和任務完成率增長速度明顯減緩。前者是因為在當前算法性能下，中繼衛星天線資源已接近其最大利用率，后者是因為任務可用資源已接近其最大利用率，任務完成率難以實現進一步增長[32-33]。同時，隨著任務數量和中繼衛星數量的增多，4種算法的任務完成數的增長速度遠小于任務申請的增長速度，算法運行時間也隨之增長，可見二者對調度工作和算法性能有較大影響。

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

圖14 不同調度方式完成任務占比Fig.14 Ratio of tasks completed for different scheduling modes

表7 不同任務規模下算法性能測試結果
Table 7 Algorithm performance test results for different number of tasks

實驗編號任務完成數任務完成率/%算法運行時間/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 不同用戶航天器數量下算法性能測試結果Table 8 Algorithm performance test results for different number of spacecraft

表9 不同中繼衛星數量下算法性能測試結果Table 9 Algorithm performance test results for different number of TDRSs

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

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

4 結 論

本文在分析任務拆分機制的基礎上，構建了考慮斷點續傳的中繼衛星單址天線調度模型和設計了考慮斷點續傳的兩階段調度算法，獲得以下結論：

1) 考慮斷點續傳的中繼衛星任務規劃模型闡明了任務拆分機制，統一表征了原任務與子任務的內在聯系，對創新和開發中繼衛星系統應用模式具有一定的借鑒意義。

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

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