考慮多滑動窗口的中繼衛(wèi)星調(diào)度模型及啟發(fā)式算法

何敏藩， 朱燕麒， 賈學(xué)卿

(1.佛山科學(xué)技術(shù)學(xué)院 數(shù)學(xué)與大數(shù)據(jù)學(xué)院， 廣東 佛山 528000； 2.北京市遙感信息研究所， 北京 100085； 3.國防科技大學(xué) 電子科學(xué)學(xué)院，湖南 長沙 410073)

0 引言

跟蹤與數(shù)據(jù)中繼衛(wèi)星(tracking and data relay satellite, TDRS)，簡稱為中繼衛(wèi)星[1-2]，主要為中、低軌道的航天器提供數(shù)據(jù)中繼、連續(xù)跟蹤與軌道測控服務(wù).中繼衛(wèi)星的出現(xiàn)是20世紀(jì)航天測控領(lǐng)域的重大突破，其“天基”設(shè)計思想從根本上解決了對中、低軌道航天器測控通信的高覆蓋率問題，減少了地面測控站的數(shù)量，在航天活動中發(fā)揮著越來越重要的作用，也成為未來航天器發(fā)展趨勢[3-5].我國的中繼衛(wèi)星系統(tǒng)主要承擔(dān)載人航天保障、登月計劃保障、航天器數(shù)據(jù)傳輸以及航天器測控任務(wù)，其中前兩項屬于頻率較低的重大任務(wù)，后兩項為常規(guī)任務(wù).對于載人航天保障等重大任務(wù)而言，其執(zhí)行優(yōu)先級較高，中繼衛(wèi)星系統(tǒng)將在任務(wù)全過程對其優(yōu)先提供服務(wù)，因此在中繼衛(wèi)星應(yīng)用模式及調(diào)度方法方面不需要較為復(fù)雜的機制.隨著我國國家利益的擴展以及航天器數(shù)量的增加，需要執(zhí)行大量海外任務(wù).航天器獲取的數(shù)據(jù)主要通過中繼衛(wèi)星系統(tǒng)實現(xiàn)實時傳輸和利用.這使得航天器數(shù)據(jù)傳輸與測控的任務(wù)需求與日俱增，用戶規(guī)模龐大，調(diào)度方案的質(zhì)量將直接影響任務(wù)完成的效果以及中繼衛(wèi)星的使用效能，這對中繼衛(wèi)星資源的合理調(diào)度提出了更高的要求[6].需要進一步深入考慮中繼衛(wèi)星應(yīng)用與用戶需求的實際情況，研究符合實際的中繼衛(wèi)星調(diào)度模型以及快速穩(wěn)定的求解算法.

衛(wèi)星調(diào)度問題是一個具有實踐和科學(xué)意義的優(yōu)化問題，國內(nèi)外取得了不少的研究成果[7-9].開彩紅等[10]針對中繼衛(wèi)星單址天線調(diào)度問題，建立了調(diào)度約束規(guī)劃模型，提出基于人工蜂群(ABC)算法的中繼衛(wèi)星任務(wù)調(diào)度算法，并通過仿真數(shù)據(jù)分析驗證了算法的合理性和有效性.王志淋等[11]借鑒時間窗約束的車輛路徑問題理論，提出天線準(zhǔn)備時間變長的規(guī)劃優(yōu)化問題(LOPVAPT)模型，通過優(yōu)化天線的掃描路徑，實現(xiàn)天線準(zhǔn)備時間的動態(tài)最優(yōu)取值，并基于蟻群算法進行了實驗驗證.林鵬等[12]面向空間網(wǎng)絡(luò)中任務(wù)發(fā)生的時間和空間隨機性，建立中繼衛(wèi)星系統(tǒng)服務(wù)模型，并提出了一種動態(tài)的空間任務(wù)調(diào)度方法.利用空間網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化的特點，結(jié)合空間任務(wù)的多優(yōu)先級和容忍延時特性，提出一種基于種群聯(lián)合進化的資源分配算法.顧中舜[13]研究了中繼衛(wèi)星動態(tài)調(diào)度問題，建立了中繼衛(wèi)星動態(tài)調(diào)度框架，分析了中繼衛(wèi)星工作的約束條件，提出了任務(wù)完成評價指標(biāo)，創(chuàng)造性地提出完成任務(wù)的收益與完成任務(wù)時間窗口的選擇有關(guān)，考慮了任務(wù)的具體執(zhí)行時間在窗口中的分布情況.陳理江等[14]研究了基于時間靈活度的中繼衛(wèi)星調(diào)度算法，在已有的調(diào)度方案基礎(chǔ)上，通過調(diào)度插空和任務(wù)交換優(yōu)化原調(diào)度方案，該算法機制比較簡單，且可以動態(tài)調(diào)整.

張彥等[15]在TDRS動態(tài)調(diào)度問題求解算法研究中，設(shè)計了動態(tài)擴展/刪除樹搜索算法(dynamic extended /delete tree search，DEDTS)，該算法在搜索過程中利用基于動態(tài)擾動測度的目標(biāo)值控制刪除任務(wù)和調(diào)整任務(wù)的時機，從而更好地體現(xiàn)實際應(yīng)用的需求.智能優(yōu)化算法在求解復(fù)雜優(yōu)化問題上表現(xiàn)出優(yōu)異性能[16]，近年來，蟻群算法(ant colony optimization, ACO)、遺傳算法(genetic algorithm, GA)、模擬退火(simulated annealing, SA)等智能優(yōu)化算法在求解組合優(yōu)化問題方面顯示了較強的能力[17-19],在中繼衛(wèi)星調(diào)度問題中也得到了一定的應(yīng)用[20].但是從文獻的仿真實驗來看，對于中繼衛(wèi)星調(diào)度問題，智能優(yōu)化算法只適用于中、小規(guī)模場景的求解，面對多中繼衛(wèi)星多用戶航天器大規(guī)模任務(wù)申請時會出現(xiàn)“維數(shù)災(zāi)”問題，導(dǎo)致智能優(yōu)化算法性能迅速下降，求解時間也將大大超出實際調(diào)度工作要求.

顧中舜[13]利用蟻群算法求解中繼衛(wèi)星初始調(diào)度模型，并與基于遺傳算法和模擬退火算法的計算結(jié)果進行了比較，結(jié)果表明，蟻群算法在求解時間和求解精度上都明顯優(yōu)于另外兩種算法.方炎申等[21]采用基于有效的基因路徑的遺傳算法來實現(xiàn)中繼衛(wèi)星單址鏈路任務(wù)調(diào)度,分析了調(diào)度問題中時間窗口的特性，對基本遺傳算法進行改進，引入有效基因概念，應(yīng)用結(jié)果表明，采用基于有效基因路徑表示的遺傳算法求解是合理的.顧中舜[13]比較了蟻群算法、遺傳算法和模擬退火算法求解中繼衛(wèi)星初始調(diào)度模型的計算結(jié)果，最后得出由于模擬退火算法有限度地接受劣解，可以跳出局部最優(yōu)解,但有計算量過大和控制參數(shù)過多的缺點.開彩紅等[10]提出了一種基于人工蜂群(artificial bees colony, ABC)算法的中繼衛(wèi)星任務(wù)編排算法.通過在算法的迭代過程中對每個可行調(diào)度方案進行評估、鄰域操作尋找局部最優(yōu)調(diào)度方案，從而獲得全局最優(yōu)調(diào)度方案.鄧博于等[22]針對遺傳算法容易陷入局部最優(yōu)和蟻群算法初始信息素匱乏的缺點，提出將遺傳和蟻群融合算法應(yīng)用于中繼衛(wèi)星系統(tǒng)的資源調(diào)度問題.通過改進蟻群算法信息素的定義，利用基于時間窗口序號編碼思想，給出中繼衛(wèi)星資源調(diào)度約束條件與目標(biāo)函數(shù)并建立數(shù)學(xué)模型.Liu等[23]研究了基于數(shù)據(jù)中繼衛(wèi)星的空間網(wǎng)絡(luò)調(diào)度問題，在模型中考慮了天線轉(zhuǎn)動時間.Lin等[24]提出了一種非對稱路徑重連接方法解決中繼系統(tǒng)中的工作調(diào)度問題.Deng等[25]提出初始調(diào)度與動態(tài)調(diào)度相結(jié)合求解中繼衛(wèi)星系統(tǒng)的調(diào)度問題.

筆者針對中繼衛(wèi)星單址天線調(diào)度問題進行研究，主要貢獻包括：著眼中繼衛(wèi)星系統(tǒng)應(yīng)用實際以及用戶需求特點，面向多中繼衛(wèi)星多用戶航天器大規(guī)模調(diào)度問題，擴展用戶申請的自主性和靈活性，設(shè)計基于多滑動窗口用戶申請的中繼衛(wèi)星應(yīng)用模式，允許用戶提交多個備選服務(wù)窗口，指定天線偏好，使得模型更加符合實際情況；詳細(xì)分析該應(yīng)用模式下中繼衛(wèi)星單址天線調(diào)度問題的優(yōu)化目標(biāo)和約束條件并建立相應(yīng)的優(yōu)化調(diào)度模型；設(shè)計相應(yīng)的啟發(fā)式算法求解調(diào)度問題；最后通過仿真實驗驗證該調(diào)度方法的有效性.

1 中繼衛(wèi)星調(diào)度模型

筆者對于中繼衛(wèi)星單址天線調(diào)度問題的研究，面向的是多中繼衛(wèi)星多用戶航天器的大規(guī)模調(diào)度問題，該問題有兩個主要的輸入：任務(wù)申請和中繼衛(wèi)星資源.任務(wù)申請即是各用戶航天器根據(jù)自身需求，向中繼衛(wèi)星相關(guān)管理機構(gòu)提出的對某段時間窗口的占用申請.中繼衛(wèi)星資源主要指的是中繼鏈路，由于筆者研究的是單址天線的調(diào)度問題，中繼衛(wèi)星可以搭載多個單址天線，一個單址天線在同一時刻只能提供一條中繼鏈路，即在同一時刻只能執(zhí)行一項任務(wù).因此可以將中繼衛(wèi)星單址天線與鏈路等同，作為基本資源單位.本研究中，中繼衛(wèi)星資源輸入信息包括多顆中繼衛(wèi)星搭載的多個單址天線的可用時間窗口，以及各中繼衛(wèi)星單址天線對各用戶航天器的可見時間窗口.其中，可用時間窗口由中繼衛(wèi)星相關(guān)管理機構(gòu)發(fā)布，可見時間窗口由中繼衛(wèi)星和用戶航天器軌道參數(shù)決定.

中繼單址天線調(diào)度問題的輸出主要是針對每個中繼衛(wèi)星單址天線的調(diào)度方案，可以從任務(wù)和天線兩個角度進行定義.從任務(wù)角度分析，中繼單址天線調(diào)度問題的輸出即是確定每項任務(wù)是否成功調(diào)度，若成功調(diào)度，確定該任務(wù)由哪條天線對其進行服務(wù)，以及服務(wù)的開始時刻、結(jié)束時刻、持續(xù)時間等.從中繼衛(wèi)星天線角度分析，中繼單址天線調(diào)度問題的輸出即是對每個天線確定周期內(nèi)的工作計劃，具體包括何時開始對哪個用戶航天器執(zhí)行任務(wù)，以及任務(wù)的結(jié)束時刻、持續(xù)時間等.

1.1 模型假設(shè)與符號說明

首先對數(shù)學(xué)模型中將用到的符號進行說明，如表1所示.

表1 集合符號定義

1.2 中繼衛(wèi)星單址天線周期調(diào)度問題的數(shù)學(xué)規(guī)劃模型

中繼衛(wèi)星單址天線調(diào)度問題，實質(zhì)上是要建立中繼衛(wèi)星資源與各任務(wù)之間的映射關(guān)系.其目的是使中繼衛(wèi)星資源在一個調(diào)度周期內(nèi)完成的任務(wù)能夠最大程度地滿足用戶的需求.因此，必須對任務(wù)和中繼衛(wèi)星資源進行統(tǒng)一管理，通過調(diào)度規(guī)劃，為各項任務(wù)分配相應(yīng)的資源，使調(diào)度方案在滿足各項約束的條件下達到預(yù)期的效果.

在筆者介紹的中繼衛(wèi)星應(yīng)用模式下，中繼衛(wèi)星單址天線調(diào)度問題就是對每項任務(wù)申請確定以下6個維度的信息：選擇在哪個備選服務(wù)時間窗口執(zhí)行、選擇哪個中繼衛(wèi)星單址天線執(zhí)行、選擇該中繼衛(wèi)星單址天線的哪個可用時間窗口執(zhí)行、選擇該中繼衛(wèi)星單址天線與任務(wù)所屬用戶航天器的哪個可見窗口執(zhí)行、實際任務(wù)開始時刻以及實際任務(wù)服務(wù)時長，因此，決策變量包括xt,tk,r,trj,rl、startt,tk,r,trj,rl和timet,tk,r,trj,rl.

xt,tk,r,trj,rl為0～1變量，其值確定以下4個維度的信息：選擇在哪個備選服務(wù)時間窗口執(zhí)行、選擇哪個中繼衛(wèi)星單址天線執(zhí)行、選擇該中繼衛(wèi)星單址天線的哪個可用時間窗口執(zhí)行、選擇該中繼衛(wèi)星單址天線與任務(wù)所屬用戶航天器的哪個可見窗口執(zhí)行.

優(yōu)化目標(biāo)反映了優(yōu)化問題研究的優(yōu)化對象的本質(zhì).針對中繼衛(wèi)星單址天線調(diào)度問題，建立兩個優(yōu)化目標(biāo)，其中任務(wù)完成率最大化是首要優(yōu)化目標(biāo)，用戶期望滿足度最大化是次要優(yōu)化目標(biāo).

(1)任務(wù)完成率最大化

在大規(guī)模任務(wù)申請條件下，不可能所有的任務(wù)申請都得到滿足，任務(wù)完成率就成為評價調(diào)度方案的重要指標(biāo)，是調(diào)度模型的主要優(yōu)化目標(biāo).

(1)

(2)用戶期望滿足度最大化

最大程度滿足用戶任務(wù)申請的偏好或者

期望，可以提高調(diào)度方案的服務(wù)水平，有利于提升任務(wù)執(zhí)行的質(zhì)量和效果.因此用戶期望滿足度是調(diào)度模型的另一個優(yōu)化目標(biāo).在筆者的中繼衛(wèi)星應(yīng)用模式下，用戶期望得到滿足需要以下兩個條件：采用任務(wù)備選服務(wù)時間窗口指定或偏好的中繼衛(wèi)星天線；采用任務(wù)備選服務(wù)時間窗口的期望服務(wù)時長.

(2)

中繼衛(wèi)星調(diào)度問題主要包含兩類約束：任務(wù)需求約束和資源使用約束.任務(wù)需求約束主要是用戶根據(jù)其需求,提出的任務(wù)申請中包含的約束.

(1)任務(wù)的執(zhí)行約束.在筆者提出的中繼衛(wèi)星應(yīng)用模式中，允許用戶根據(jù)實際需求提交多個備選服務(wù)時間窗口，在生成調(diào)度方案時，僅選擇其中的一個備選服務(wù)時間窗口進行調(diào)度，不可對任務(wù)進行重復(fù)安排，并且每項任務(wù)僅選擇一個中繼衛(wèi)星單址天線執(zhí)行.根據(jù)該約束得到Constraint 1～2.

Constraint 1：每個任務(wù)僅選擇一個備選服務(wù)時間窗口,

(3)

Constraint 2：每個任務(wù)僅選擇一個中繼衛(wèi)星單址天線執(zhí)行,

(4)

(2)任務(wù)的服務(wù)時間窗口約束.由于任務(wù)需求具有很強的時效性,例如遙感衛(wèi)星獲取的某些敏感數(shù)據(jù)必須通過中繼衛(wèi)星在用戶申請的時間段內(nèi)回傳到地面站，因此，中繼衛(wèi)星對任務(wù)的服務(wù)時間窗口必須在相應(yīng)的備選服務(wù)時間窗口范圍內(nèi)，過早或過晚都會影響任務(wù)執(zhí)行效果，導(dǎo)致任務(wù)失敗,根據(jù)該約束得到Constraint 3～4.

Constraint 3：每個任務(wù)的實際開始時刻不早于所在備選服務(wù)時間窗口的最早開始時刻,

startt,tk,r,trj,rl≥(startt,tk-forwardt,tk)·xt,tk,r,trj,rl.

(5)

Constraint 4：每個任務(wù)的實際開始時刻不晚于所在備選服務(wù)時間窗口的最晚開始時刻,

startt,tk,r,trj,rl·xt,tk,r,trj,rl≤startt,tk+backwardt,tk.

(6)

(3)任務(wù)的服務(wù)天線約束.如果選擇的任務(wù)備選服務(wù)時間窗口指定了服務(wù)的中繼衛(wèi)星天線，則必須使用指定的中繼衛(wèi)星天線為該項目進行服務(wù)，使用其他天線則無法滿足用戶需求，視為任務(wù)失敗,根據(jù)該約束得到Constraint 5.

Constraint 5：對于選擇指定天線的備選服務(wù)時間窗口的任務(wù)，執(zhí)行天線必須滿足指定要求,

?((rt,tk≠?)∧(xt,tk,r,trj,rl≠0)),r=rt,tk.

(7)

(4)任務(wù)的服務(wù)時長約束.選擇的任務(wù)備選服務(wù)時間窗口包含期望服務(wù)時長和最短服務(wù)時長，實際調(diào)度方案中的任務(wù)服務(wù)時長應(yīng)不大于期望服務(wù)時長，不小于最短服務(wù)時長,根據(jù)該約束得到Constraint 6～7.

Constraint 6：每個任務(wù)的實際服務(wù)時長不大于備選服務(wù)時間窗口的期望服務(wù)時長,

timet,tk,r,trj,rl≤dt,tk.

(8)

Constraint 7：每個任務(wù)的實際服務(wù)時長不小于備選服務(wù)時間窗口的最短服務(wù)時長,

timet,tk,r,trj,rl≥dshortt,tk.

(9)

(5)中繼衛(wèi)星單址天線能力約束.一個單址天線在同一時刻只能提供一條中繼鏈路，即在同一時刻只能執(zhí)行一項任務(wù)，并且在任務(wù)開始之前，中繼衛(wèi)星天線需要根據(jù)預(yù)先計算結(jié)果，提前將天線轉(zhuǎn)動到合適的角度與用戶航天器進行對準(zhǔn)操作，天線對準(zhǔn)需要占用一定時間.在任務(wù)執(zhí)行結(jié)束之后，中繼衛(wèi)星天線需要一段時間進行恢復(fù)調(diào)整，為執(zhí)行下一項任務(wù)做好準(zhǔn)備.在進行天線對準(zhǔn)操作和天線恢復(fù)調(diào)整過程中，無法執(zhí)行任務(wù)或進行其他工作，根據(jù)該約束得到Constraint 8.

Constraint 8：每個中繼衛(wèi)星單址天線任意時刻僅能執(zhí)行一項工作，

?r∈R,t1∈T,t2∈T,(adjust+Et1,r+rec)∩

(adjust+Et2,r+rec)=?.

(10)

(6)可用時間窗口約束.可用時間窗口由中繼衛(wèi)星相關(guān)管理機構(gòu)發(fā)布，由于任務(wù)執(zhí)行過程不允許中斷，因此中繼衛(wèi)星執(zhí)行任務(wù)相關(guān)的所有操作，包括天線對準(zhǔn)、任務(wù)執(zhí)行與天線調(diào)整恢復(fù)，必須在中繼衛(wèi)星天線的某個可用時間窗口內(nèi)完成,根據(jù)該約束得到Constraint 9～11.

Constraint 9：每個任務(wù)在中繼衛(wèi)星單址天線的一個可用時間窗口內(nèi)執(zhí)行,

(11)

Constraint 10：每個任務(wù)開始前的天線對準(zhǔn)開始時刻不早于所在單址天線的可用時間窗口的開始時刻，

startt,tk,r,trj,rl-adjust≥startrl·xt,tk,r,trj,rl.

(12)

Constraint 11：每個任務(wù)結(jié)束后的天線調(diào)整恢復(fù)結(jié)束時刻不晚于所在單址天線的可用時間窗口的結(jié)束時刻,

(startt,tk,r,trj,rl+timet,tk,r,trj,rl+rec)·xt,tk,r,trj,rl≤endrl.

(13)

(7)可見時間窗口約束.可見時間窗口由中繼衛(wèi)星和用戶航天器軌道參數(shù)決定，在任務(wù)執(zhí)行過程中必須時刻保持中繼衛(wèi)星天線與用戶航天器的直視.由于任務(wù)執(zhí)行過程不允許中斷，因此中繼衛(wèi)星的任務(wù)執(zhí)行過程必須在中繼衛(wèi)星天線與用戶航天器的某個可見時間窗口內(nèi)完成.任務(wù)執(zhí)行前的天線對準(zhǔn)和任務(wù)完成后的天線調(diào)整恢復(fù)操作，不要求在可見窗口內(nèi)完成,根據(jù)該約束得到Constraint 12～14.

Constraint 12：每個任務(wù)在中繼衛(wèi)星單址天線與用戶航天器的一個可見時間窗口內(nèi)執(zhí)行,

(14)

Constraint 13：每個任務(wù)的實際開始時刻不早于所在單址天線與用戶航天器的可見時間窗口的開始時刻,

startt,tk,r,trj,rl≥starttrj·xt,tk,r,trj,rl.

(15)

Constraint 14：每個任務(wù)的實際結(jié)束時刻不晚于所在單址天線與用戶航天器的可見時間窗口的結(jié)束時刻,

(startt,tk,r,trj,rl+timet,tk,r,trj,rl)·xt,tk,r,trj,rl≤endtrj.

(16)

筆者建立的中繼衛(wèi)星單址天線周期調(diào)度模型為NP-hard問題，考慮多個滑動的備選服務(wù)時間窗口、多個中繼衛(wèi)星單址天線、多個可見時間窗口和多個可用時間窗口，問題的解空間隨著資源與任務(wù)數(shù)量的增長呈指數(shù)激增且面臨著組合爆炸的挑戰(zhàn).模型具有超高的決策變量維度以及復(fù)雜的約束條件，尚不存在按多項式時間復(fù)雜度找到全局最優(yōu)解的算法，現(xiàn)有通用算法難以直接求解本模型，對模型求解算法的設(shè)計提出了更高的要求.

2 基于時間自由度的啟發(fā)式算法

基于規(guī)則的啟發(fā)式算法，具有求解速度快、穩(wěn)定性高的優(yōu)點，能夠在較短的時間內(nèi)給出較優(yōu)的可行解，求解中繼衛(wèi)星調(diào)度問題的有效算法.筆者設(shè)計的基于時間自由度的啟發(fā)式算法，考慮到用戶的任務(wù)申請可以包含多個備選服務(wù)時間窗口，且備選服務(wù)時間窗口有可能指定或不指定中繼衛(wèi)星天線.依據(jù)任務(wù)申請包含的備選服務(wù)時間窗口數(shù)量以及指定天線情況，對任務(wù)的時間自由度進行評價，根據(jù)評價結(jié)果決定任務(wù)調(diào)度的優(yōu)先次序.在調(diào)度理論中，該算法屬于構(gòu)造性算法，即依次對任務(wù)進行調(diào)度，最終生成較優(yōu)的可行調(diào)度方案.

基于時間自由度的啟發(fā)式算法主要包括以下4個算法模塊：①任務(wù)時間自由度評價；②任務(wù)資源匹配；③任務(wù)插空；④資源刷新.①是根據(jù)任務(wù)的備選服務(wù)時間窗口數(shù)量及指定天線情況，評價任務(wù)的時間自由度并決定優(yōu)先次序.②是根據(jù)任務(wù)提交的備選服務(wù)時間窗口信息，為任務(wù)匹配當(dāng)前可用時段資源.③是基于啟發(fā)式規(guī)則，根據(jù)②中任務(wù)各備選服務(wù)時間窗口與當(dāng)前可見時間窗口以及當(dāng)前天線可用時間窗口的匹配結(jié)果，為當(dāng)前任務(wù)安排合適的調(diào)度方案.④是在安排新的任務(wù)之后，對現(xiàn)有可見時間窗口以及天線可用時間窗口進行刷新，刪除已被占用的資源.

2.1 任務(wù)時間自由度評價

根據(jù)任務(wù)的備選服務(wù)時間窗口數(shù)量及指定天線情況，評價該任務(wù)的時間自由度.一般來說，提交的備選服務(wù)時間窗口數(shù)量越多，不指定天線的備選服務(wù)時間窗口數(shù)量越多，任務(wù)的時間自由度越高，任務(wù)調(diào)度的難度越小，可以使其獲得較低的優(yōu)先次序，在算法運行的靠后階段進行調(diào)度.

具體的評價方式為：首先遍歷任務(wù)集合T，獲取最大備選服務(wù)時間窗口數(shù)量winmax=max{[Kt],t∈T}；然后依次分析任務(wù)集合T中的任務(wù)，獲取當(dāng)前任務(wù)t的備選服務(wù)時間窗口數(shù)量wint=[Kt]，當(dāng)前任務(wù)t指定天線的備選服務(wù)窗口數(shù)量winassign；最后對當(dāng)前任務(wù)t進行時間自由度評價，評價公式為：

scoret= (winmax+1-wint)+(winmax-

wint+winassign).

(17)

對其進行簡化，即

scoret=2×(winmax-wint)+winassign+1.

(18)

式中：scoret的取值范圍為[1,2×winmax]，任務(wù)t的時間自由度評價scoret取值越大，表明任務(wù)t的時間自由度越低，將取得較為靠前的調(diào)度次序.

2.2 任務(wù)資源匹配

對于當(dāng)前處理的任務(wù)t，遍歷其提交的備選服務(wù)時間窗口Kt，與現(xiàn)有資源進行比對，得到可以安排的可用時段資源.任務(wù)資源匹配需要與當(dāng)前可見時間窗口和當(dāng)前天線可用時間窗口分別進行比對，將匹配得到的可用時段資源分成兩類存放：一類是指定天線的備選服務(wù)時間窗口匹配得到的可用時段資源集合，記為taskresource1；另一類是不指定天線的備選服務(wù)時間窗口匹配得到的可用時段資源集合，并記錄其偏好信息，記為taskresource2.

任務(wù)資源匹配方法如圖1所示，其中dtimet,tk是任務(wù)t的備選服務(wù)時間窗口tk在任務(wù)資源匹配時采用的服務(wù)時長.

圖1 任務(wù)資源匹配方法Fig.1 The task-resource matching method

對于當(dāng)前備選服務(wù)時間窗口tk，若tk指定中繼衛(wèi)星單址天線，則首先遍歷其指定天線rt,tk與該任務(wù)用戶航天器當(dāng)前可見時間窗口集合Jt,r.對于Jt,r中的可見時間窗口trj，若滿足條件

(19)

則可見時間窗口trj與當(dāng)前備選服務(wù)時間窗口tk無交集，可直接排除；對于與tk有交集的可見時間窗口trj，判斷其是否滿足以下條件：

(20)

若滿足該條件，則可見時間窗口trj可用，繼續(xù)進行下一步比對.遍歷指定天線rt,tk的當(dāng)前可用時間窗口集合Jr，對于Jr中的可用時間窗口rl，若滿足條件：

(21)

則可用時間窗口rl可用.該步比對加入了任務(wù)執(zhí)行前的天線對準(zhǔn)和任務(wù)完成后的天線恢復(fù)調(diào)整時間.記可用時段資源開始時刻為T1，可用時段資源結(jié)束時刻為T2，并同時記錄可用時段資源所在中繼衛(wèi)星單址天線，記入taskresource1.

2.3 任務(wù)插空

對于當(dāng)前處理的任務(wù)t，根據(jù)任務(wù)資源匹配算法得到的可用時段資源集合taskresource1和taskresource2，進行任務(wù)的安排.

首先判斷taskresource1是否非空，若其非空，在其中隨機選擇一個可用時段資源進行調(diào)度，采用緊前、隨機或緊后策略，轉(zhuǎn)入算法(2.4)刷新資源.任務(wù)插空方法如圖2所示.

圖2 任務(wù)插空方法Fig.2 Task insertion method

其中，緊前策略

(22)

隨機策略

(23)

random()為隨機生成的[0,1]的隨機數(shù).

緊后策略

(24)

若taskresource1為空集，判斷taskresource2的情況，若其非空，遍歷其中的可用時段資源，找出其中天線偏好非空且與可用時段資源所在天線相同的時段.如果存在天線偏好非空且與可用時段資源所在天線相同的時段，在其中隨機選擇一個進行調(diào)度，采用緊前、隨機或緊后策略，轉(zhuǎn)入資源刷新操作.若不存在天線偏好非空且與可用時段資源所在天線相同的時段，則在taskresource2中隨機選擇一個可用時段資源進行調(diào)度，采用緊前、隨機或緊后策略，轉(zhuǎn)入資源刷新操作.

若taskresource2也為空集，則將該任務(wù)所有備選服務(wù)時間窗口采用的服務(wù)時長由期望服務(wù)時長改為最短服務(wù)時長，轉(zhuǎn)入任務(wù)資源匹配操作，重新進行任務(wù)資源匹配，得到該任務(wù)的taskresource1和taskresource2，并重復(fù)上述過程.

若taskresource1和taskresource2仍均為空集，則認(rèn)為當(dāng)前資源無法完成該任務(wù)的調(diào)度，當(dāng)前任務(wù)調(diào)度失敗.

2.4 資源刷新

每當(dāng)有任務(wù)被成功調(diào)度，會占用該中繼衛(wèi)星單址天線與本用戶航天器以及其他用戶航天器的可見時間窗口以及天線可用時間窗口，由于資源的互斥性，需要對可見時間窗口以及天線可用時間窗口均進行刷新，刪除本次調(diào)度占用的時段.被占用的時段不僅包括任務(wù)的服務(wù)時長timet,tk,r,trj,rl，還包括之前的中繼衛(wèi)星天線對準(zhǔn)時間adjust以及隨后的恢復(fù)調(diào)整時間rec.

對可見時間窗口資源進行刷新時，要遍歷該中繼衛(wèi)星單址天線r對所用用戶航天器的所有可見時間窗口，對當(dāng)前處理的可見時間窗口trj，令

(25)

則本次調(diào)度所占用的時段與可見時間窗口trj可能存在的情形如圖3所示.

圖3 可見時間窗口資源刪除及刷新方法Fig.3 Method for deleting and updating visible time-windows

針對不同情況的刷新方法如表2所示.

表2 針對不同情況的資源刷新規(guī)則Tab.2 Resource update rules under different conditions

天線可用時間窗口資源刪除及刷新方法與上述方法相同，在此不再贅述.

3 仿真實驗

3.1 實驗設(shè)置

實驗平臺為配置3.29 GHz Intel Core CPU、8 GB內(nèi)存、Windows 7操作系統(tǒng)的PC機，算法在Matlab 2014中編程實現(xiàn).由于采用基于多滑動窗口用戶申請的中繼衛(wèi)星應(yīng)用模式，沒有標(biāo)準(zhǔn)測試集可供調(diào)用，為完成仿真實驗，首先進行中繼衛(wèi)星資源與任務(wù)需求場景仿真，生成所需應(yīng)用場景.在此基礎(chǔ)上，對筆者所提算法進行測試.

中繼衛(wèi)星相關(guān)管理機構(gòu)下屬4顆中繼衛(wèi)星，每顆中繼衛(wèi)星載有1副中繼衛(wèi)星單址天線用于執(zhí)行常規(guī)任務(wù)，面向的用戶部門共下屬20顆用戶航天器.

根據(jù)日常工作安排，中繼衛(wèi)星相關(guān)管理機構(gòu)于2017年11月25日發(fā)布2017年12月1日0時～2017年12月7日0時的可用中繼衛(wèi)星資源，各用戶部門可根據(jù)自身工作需要與所屬航天器工作情況于2017年11月28日前進行任務(wù)申請，允許每項任務(wù)申請?zhí)峤?～3個備選服務(wù)時間窗口.最終收到500個任務(wù)申請，中繼衛(wèi)星相關(guān)管理機構(gòu)于2017年11月29日完成周期調(diào)度工作，在周期調(diào)度方案生成后，2017年11月30日有3個臨時任務(wù)申請到達.任務(wù)開始前中繼衛(wèi)星單址天線對準(zhǔn)時間10 min，任務(wù)結(jié)束后中繼衛(wèi)星單址天線恢復(fù)調(diào)整時間4 min.

針對以上假定的應(yīng)用場景，將相關(guān)參數(shù)整理如表3所示.

表3 應(yīng)用場景參數(shù)設(shè)置

中繼衛(wèi)星資源主要包括中繼衛(wèi)星單址天線的可用時間窗口，以及各中繼衛(wèi)星單址天線對各用戶航天器的可見時間窗口，需仿真相關(guān)數(shù)據(jù)用于后續(xù)實驗.本案例將4個中繼衛(wèi)星單址天線的可用時間窗口設(shè)置為2017年12月1日0時至2017年12月7日0時均可用.對于各中繼衛(wèi)星單址天線對各用戶航天器的可見時間窗口，筆者利用STK軟件設(shè)置了相關(guān)場景進行仿真，獲取相關(guān)數(shù)據(jù).

3.2 計算結(jié)果

利用基于時間自由度的啟發(fā)式算法對上述案例場景進行測試，其中1～10項任務(wù)的調(diào)度方案如表4所示.

表4 基于時間自由度的啟發(fā)式算法部分調(diào)度結(jié)果

表中信息值-1表示該項任務(wù)由于資源不足未成功調(diào)度，時間段數(shù)值的單位為天.

算法的主要評價指標(biāo)數(shù)據(jù)如表5所示.實驗結(jié)果表明，算法具有很快的運行速度，能夠在2 s內(nèi)完成500項任務(wù)規(guī)模場景的周期調(diào)度方案，任務(wù)完成率可以達到76.4%，用戶期望滿足度達到50.2%，具備較強的可用性，能夠滿足調(diào)度方案快速生成的要求.

3.3 與最大權(quán)重任務(wù)最先服務(wù)算法對比

表5 基于時間自由度的啟發(fā)式算法性能指標(biāo)Tab.5 The performance criterion of the heuristic algorithm based on the time freedom degree

可以發(fā)現(xiàn)基于時間自由度的啟發(fā)式算法里使用了4個靈活的算子，包括任務(wù)時間自由度評價、任務(wù)資源匹配、任務(wù)插空和資源更新，保障算法能夠快速高效得到中繼衛(wèi)星系統(tǒng)的調(diào)度方案.為了驗證算法的有效性，將其與最大權(quán)重任務(wù)最先服務(wù)算法(highest weight task first service， HWFS)進行比較.最大權(quán)重任務(wù)最先服務(wù)算法的步驟如下:

Step 1：對待完成的中繼任務(wù)根據(jù)其權(quán)重從大到小排序，形成任務(wù)隊列Q.

Step 2：然后每次從任務(wù)隊列Q中選出權(quán)重最大的任務(wù)t.

Step 3：為任務(wù)t安排最佳服務(wù)資源，從Q中刪除t.如果Q=?，算法結(jié)束；否則轉(zhuǎn)Step 2.

兩個算法的計算結(jié)果如表6所示.由表6中的數(shù)據(jù)可以看出，在該場景下，HA-TFD把HWFS的任務(wù)完成率從70%提升到76.4%，把HWFS的用戶期望滿足度從43%提升到50.2%，該對比實驗說明，HA-TFD是一種更加靈活高效的啟發(fā)式優(yōu)化算法.

3.4 任務(wù)規(guī)模對算法的影響

為了分析不同任務(wù)規(guī)模對算法的影響，本節(jié)在任務(wù)需求仿真相關(guān)參數(shù)取值不變的條件下，設(shè)置100、300、500、800、1 200、1 600共6個不同任務(wù)申請數(shù)量的任務(wù)場景，分別對基于時間自由度的啟發(fā)式算法和基于沖突消解的隨機搜索算法進行測試.每個任務(wù)場景進行20次重復(fù)實驗，對算法性能進行分析，相關(guān)數(shù)據(jù)如表7所示.

表6 算法比較結(jié)果Tab.6 Comparison results

表7 不同任務(wù)規(guī)模下的實驗結(jié)果Tab.7 The experimental results of different scales of tasks

3.5 用戶航天器數(shù)量對算法的影響

為了分析不同用戶航天器數(shù)量對算法的影響，在任務(wù)需求仿真相關(guān)參數(shù)取值不變的條件下，僅改變應(yīng)用場景參數(shù)中的用戶航天器數(shù)量.設(shè)置4、8、16、20、28、36共6個不同用戶航天器數(shù)量的任務(wù)場景，分別對基于時間自由度的啟發(fā)式算法和基于沖突消解的隨機搜索算法進行測試.每個任務(wù)場景進行20次重復(fù)實驗，實驗結(jié)果如表8所示.

表8 不同用戶航天器數(shù)量下的實驗結(jié)果Tab.8 Experimental results of different numbers of user Spacecraft

4 結(jié)論

分析中繼衛(wèi)星單址天線周期調(diào)度問題，考慮多滑動窗口用戶申請的中繼衛(wèi)星應(yīng)用模式，針對中繼衛(wèi)星單址天線周期調(diào)度多目標(biāo)、多約束的特點，建立了數(shù)學(xué)規(guī)劃模型.模型最大化任務(wù)完成率和用戶期望滿足度，其中任務(wù)完成率是最重要的優(yōu)化目標(biāo)，用戶期望滿足度是次要優(yōu)化目標(biāo).將周期調(diào)度中的任務(wù)需求約束、資源使用約束作為模型的約束條件.提出基于時間自由度的啟發(fā)式算法，算法利用任務(wù)申請信息在任務(wù)調(diào)度之前對任務(wù)完成難度進行評估，并以此為依據(jù)進行任務(wù)調(diào)度優(yōu)先順序的安排，提高了啟發(fā)式算法任務(wù)調(diào)度的成功率，從而提高了調(diào)度方案的質(zhì)量.筆者創(chuàng)造性地提出基于多滑動窗口用戶申請的中繼衛(wèi)星應(yīng)用模式，大大擴展了用戶申請的自主性和靈活性，有利于提高調(diào)度方案的質(zhì)量和中繼衛(wèi)星系統(tǒng)資源的使用效能，對于中繼衛(wèi)星系統(tǒng)實際應(yīng)用模式的創(chuàng)新具有一定的借鑒意義.基于時間自由度的啟發(fā)式算法具有求解速度快，算法穩(wěn)定的優(yōu)點，適用于應(yīng)急調(diào)度情況和大規(guī)模調(diào)度場景，其不足之處在于，由于沒有引入隨機迭代求解策略，求解的質(zhì)量還有待進一步提高.下一步將繼續(xù)研究高效智能優(yōu)化算法求解中繼衛(wèi)星調(diào)度問題，提高調(diào)度效率和調(diào)度方案質(zhì)量.