基于隨機搜索策略的中繼衛(wèi)星調度方法*

姚 鋒，羅啟章，朱燕麒，陳盈果

(1. 國防科技大學 系統(tǒng)工程學院， 湖南 長沙 410073； 2. 中南大學 交通運輸工程學院， 湖南 長沙 410075)

中繼衛(wèi)星能夠為中、低軌道的航天器提供數據中繼、連續(xù)跟蹤與軌道測控等服務[1-2]。通過少量中繼衛(wèi)星組網，可實現對軌道高度在200～12 000 km范圍內所有航天器的連續(xù)跟蹤與數據中繼，減少地面測控站和測量船、測量飛機的數量，節(jié)省遠程通信費用及人工維護費用，打破國土面積以及地理因素的限制，使得對用戶航天器進行連續(xù)通信成為可能[3]。因此，中繼衛(wèi)星逐漸成為各國發(fā)展航天事業(yè)越來越重要的項目。

隨著我國航天器和海外任務數量的增加，中繼任務需求與日俱增，用戶規(guī)模日益龐大，對中繼衛(wèi)星的調度能力和水平提出了更高的要求[4]。有必要結合實際應用情況，采用更加靈活的中繼衛(wèi)星調度應用模式，并設計相應的數學模型和求解算法，為用戶提供更高質量的調度服務。

目前，針對中繼衛(wèi)星應用模式的研究和創(chuàng)新不多，在相關文獻中較少明確介紹中繼衛(wèi)星應用模式，也較少對其進行設計和創(chuàng)新。現有研究主要基于較為通用的應用模式展開[5-6]，即用戶基于任務需求申請一個確定的時間窗口，每項任務對應一個時間窗口，并指定一個需要服務的中繼衛(wèi)星天線。然而，傳統(tǒng)的應用模式主要存在以下問題：第一，用戶的任務需求情況復雜多樣，有的任務有多個備選服務時間窗口，有的任務需要指定中繼衛(wèi)星天線，有的任務則不需要指定，單個服務時間窗口難以滿足用戶需求。第二，用戶在申請時通常難以提供準確的服務時間窗信息，為了保證數據有足夠時間下傳，往往會申請一個比自身需求大很多的時間窗口，導致天線與窗口資源的浪費。第三，由于每項任務只允許申請一個時間窗口，如果無法滿足該時間窗口，則該任務將無法成功調度。因此，本文提出了一種全新的中繼衛(wèi)星用戶申請的應用模式，允許用戶針對每項任務提交多個可以滑動的服務時間窗口，并在每個服務窗口指定偏好的中繼衛(wèi)星天線，從而提高調度的靈活性和合理性，滿足用戶的多樣化需求。

高質量的調度算法對提高中繼衛(wèi)星資源的服務水平具有重要意義。中繼衛(wèi)星調度問題由于其復雜性和多約束的特點而難于被求解[7]，國內外僅有少量學者對中繼衛(wèi)星調度問題進行研究。針對中繼衛(wèi)星的動態(tài)調度問題，Deng等[8]和Zhuang等[9]分別設計了基于多選擇背包問題的調度算法和結合人工蜂群與逼近理想解排序法的調度算法。Zhou等[10]將中繼衛(wèi)星任務調度問題構建為混合整數非線性規(guī)劃模型，通過將其分解為混合整數線性規(guī)劃子問題，針對性地設計了一種兩階段的算法以進行求解。He等[11]面向具有時間窗的動態(tài)混合中繼衛(wèi)星任務調度問題，通過聯合優(yōu)化調度周期和天線時間塊分配F來提高任務的完成率。Spangelo等[12]研究了單中繼衛(wèi)星與多地面站的通信調度問題，并設計了一種迭代算法對問題進行求解。王璐琦等[13]針對地月中繼任務的特點，以最小數據丟失量為研究目標，設計了一種基于離散演化算法的地月中繼衛(wèi)星調度算法。何敏潘等[14]設計了多滑動窗口的中繼衛(wèi)星應用模式，并提出了基于時間自由度的啟發(fā)式算法對問題模型進行求解。Lin等[15]利用中繼衛(wèi)星業(yè)務過程中空閑時間窗的時域靈活性和統(tǒng)計特性，提出了一種啟發(fā)式作業(yè)調度框架，以加快時間收斂速度。Net等[16]考慮了用戶需求的變異性，將與用戶需求相關的不確定性因素添加到現有的通信網絡體系中，并構建了相應的中繼衛(wèi)星調度模型。李夏苗等[2]針對采用斷點續(xù)傳技術的中繼衛(wèi)星，提出了一種基于沖突風險評估量化的兩階段調度算法。

對于本文研究的復雜約束條件下的大規(guī)模調度優(yōu)化問題，精確算法很難在有限時間內獲得最優(yōu)解[17]。傳統(tǒng)的智能優(yōu)化算法雖然也被應用于中繼衛(wèi)星優(yōu)化調度問題[18-19]，但面對多中繼衛(wèi)星多用戶航天器的大規(guī)模任務申請的調度場景，會遇到“維數災難”、難以處理復雜約束條件等問題，嚴重影響算法求解質量[19-20]。因此，本文對研究問題的特點進行深入分析，針對性地提出了一種基于隨機搜索策略的求解算法。

1 中繼衛(wèi)星單址天線調度模型

1.1 問題描述與模型假設

本文研究的是多中繼衛(wèi)星多用戶航天器大規(guī)模調度問題，要求在服從任務需求約束和資源使用約束的情況下獲得最優(yōu)的調度方案[21]。其中，任務需求指用戶向中繼衛(wèi)星相關管理機構提出的對某段時間窗口的占用申請。假設用戶在申請時，每項任務可以擁有多個備選服務窗口，可以指定執(zhí)行該任務的天線，并假設備選服務窗口的開始時間可以在一定范圍內滑動。資源使用指任務對中繼鏈路的占用。中繼衛(wèi)星天線分為單址天線和多址天線，多址天線可看作單址天線進行并行傳輸能力擴展的結果，對單址天線的調度問題擴展和轉化即可適用于多址天線。因此，單址天線的調度問題研究是基礎，假設每顆中繼衛(wèi)星可以搭載多個單址天線，一個單址天線在同一時刻只能執(zhí)行一項任務，且單址天線在中繼衛(wèi)星與用戶航天器的可見時間窗口內時時可用。

1.2 數學規(guī)劃模型

模型中用到的符號及定義見表1。

表1 符號定義

1.2.1 優(yōu)化目標

在任務需求約束和資源使用約束的限制下，無法保證每個任務都被成功調度。因此，設定任務完成率為優(yōu)化目標和評價調度方案質量的重要指標，如式(1)所示。

(1)

1.2.2 約束條件

1)任務需求約束

用戶申請任務時可提交多個備選任務時間窗，但在任務調度過程中，每項任務僅能選擇一個備選時間窗和一條天線執(zhí)行。 因此任務的執(zhí)行約束可表示為：

(2)

(3)

由于某些任務具有很強的時效性，或某些任務本身有特定的執(zhí)行時段，因此任務的執(zhí)行時段必須在其相應的備選服務時間窗內，即中繼衛(wèi)星執(zhí)行任務時段不早于所在備選服務時間窗的最早開始時刻，不晚于其最晚開始時刻。任務的服務時間窗口約束可表示為：

taskstartt,k,r,j≥(startt,k-advt,k)·xt,k,r,j

(4)

taskstartt,k,r,j·xt,k,r,j≤startt,k+delt,k

(5)

若用戶在任務所選的備選服務時間窗指定中繼衛(wèi)星天線，則必須使用當前任務計劃指定的中繼衛(wèi)星天線執(zhí)行該項任務，否則任務調度失敗。因此，任務的服務天線約束可表示為：

(6)

調度過程中任務的實際服務時長應不大于任務的期望服務時長，同時不應小于備選服務時間窗的最短服務時長。因此任務的服務時長約束可表示為：

stt,k,r,j≤ntt,k

(7)

stt,k,r,j≥tshortt,k

(8)

2)資源使用約束

天線能力約束主要表現為三個方面：一是同一時刻天線僅能執(zhí)行一項任務；二是在任務執(zhí)行前中繼衛(wèi)星與用戶航天器需要進行天線對準操作，即在任務執(zhí)行前占用一定的時間將天線轉動到合適角度；三是在任務結束后，天線需要一定的時間復位。因此天線能力約束可表示為：

[taskstartt1,k,r,j-adj,taskstartt1,k,r,j+Et1,r+rec]∩

[taskstartt2,k,r,j-adj,taskstartt2,k,r,j+Et2,r+rec]=? ,

?(r∈R,t1∈T,t2∈T)

(9)

由于任務執(zhí)行過程不允許中斷，所以任務應該在中繼衛(wèi)星與用戶航天器的某個可見時間窗內執(zhí)行完成。因此可見時間窗口約束可表示為：

(10)

(11)

(12)

綜上所述，中繼衛(wèi)星單址天線調度問題為最大化式(1)函數，并服從式(1)～(12)中定義的約束條件。

2 中繼衛(wèi)星單址天線調度算法設計

2.1 算法流程描述

針對調度模型的特點，設計了基于隨機搜索策略的調度算法(Scheduling Algorithm based on Stochastic sEarch strategy，SA-SE)。該算法主要包括5個算法模塊：①任務資源匹配與鄰域生成；②實際服務時間窗生成；③任務沖突分析；④鄰域搜索與沖突消解；⑤資源與任務集更新。其中，模塊①根據任務提交的備選服務時間窗口信息為任務匹配中繼衛(wèi)星資源，以任務的多種可執(zhí)行方案作為該任務調度的鄰域。模塊②根據模塊①的結果，生成任務的實際服務時間段。模塊③對任務實際服務時間段之間的沖突進行檢測與分析，找出造成沖突的關鍵任務，生成任務的“擾動-刪除”池。模塊④對于“擾動-刪除”池中的任務進行隨機擾動，或將任務刪除，逐步迭代利用鄰域搜索過程消解任務沖突。模塊⑤刪除無沖突的資源與任務，更新資源與任務集，通過重復上述過程，使調度方案不斷優(yōu)化。算法流程如圖1所示。

圖1 基于隨機搜索策略的調度算法流程Fig.1 Flow of scheduling algorithm based on stochastic search strategy

2.2 任務資源匹配與鄰域生成

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

(13)

2.3 實際服務時間窗生成

根據任務資源匹配的結果，產生任務的實際服務時間窗，作為任務調度的初始方案。遍歷每個任務的可用時段資源，若可用時段資源長度大于或等于該任務的期望服務時長，則選擇期望服務時長作為實際服務時長；若可用時段資源小于期望服務時長，且大于最短服務時長，則選擇該任務的最短服務時長作為實際服務時長，即

(14)

因此，每個任務的實際服務時間窗可表示為awt,k,r,j=[stt,k,r,j,stt,k,r,j+Et,r]，從而可以確定該階段的任務調度方案。然而，由于初始調度方案中各任務之間可能存在資源和時段的沖突，需要進一步對沖突進行分析與消解。

2.4 任務沖突分析

首先，遍歷當前調度方案中所有被調度的任務，將其占用資源依次與其他被調度任務的占用資源進行比對，如果兩項任務使用相同中繼衛(wèi)星天線且占用時段有交集，則兩項任務之間有沖突，將兩項任務的編號記入沖突列表。

然后，對沖突列表中每項任務出現的次數進行統(tǒng)計分析，并對任務按照出現次數進行降序排列。若存在沖突的任務數為num，設置閾值threshold∈(0,1)，對于排序在num×threshold之前的任務，將其放入“擾動-刪除”池，轉入鄰域搜索與沖突消解模塊進行下一步的鄰域搜索沖突消解操作；若當前解不存在任務沖突，則返回空的“擾動-刪除”池，表明當前階段沖突消解完成，轉入資源與任務集更新模塊。

2.5 鄰域搜索與沖突消解

鄰域搜索與沖突消解主要根據任務沖突分析的結果，對“擾動-刪除”池中的任務進行隨機擾動，或將任務刪除，逐步迭代消解任務沖突。該模塊共有3個步驟：

Step1：清空“擾動-刪除”池中所有任務的調度方案，重新對其進行調度方案的安排，即對于每項任務在其鄰域范圍內隨機游走，生成新的實際服務窗，轉入Step2。

Step2：調用任務沖突分析模塊，對于Step1中生成的新調度方案進行沖突檢測與分析，重新生成新的“擾動-刪除”池。若新的“擾動-刪除”池為空，表明當前階段沖突消解完成，轉入資源與任務集更新模塊；否則重復鄰域搜索的操作，生成新的調度方案，并轉入Step3。

Step3：對Step1和Step2中的兩個“擾動-刪除”池進行對比分析，找出同時出現在兩個“擾動-刪除”池中的任務并記入“刪除”池，隨機選擇一個“刪除”池中的任務，清空其調度方案，在當前階段的算法流程中刪除該任務，生成新的解。之后轉入任務沖突分析模塊，對新解進行沖突檢測與分析。

2.6 資源與任務集更新

當算法每次調用任務沖突分析模塊后生成的“擾動-刪除”池為空集時，將當前解中所有成功調度任務的方案記錄之后從任務集合T中刪除，并將成功調度的任務所占用的時段從可見時間窗口和天線可用時間窗口中刪除，從而實現資源與任務集的更新。其本質是得到一個小于當前問題規(guī)模的新的調度問題，再重新轉入任務資源匹配與鄰域生成模塊，從而實現重復迭代優(yōu)化。

資源與任務集更新模塊同時負責控制算法整體的運行與終止，當達到預設的算法終止條件或迭代次數時，終止算法的迭代過程，保留當前調度方案作為算法的輸出。

3 仿真實驗

3.1 實驗設置

由于研究的問題不存在標準測試集，基于STK和MATLAB 2014展開中繼衛(wèi)星資源與任務需求場景仿真和算法測試。仿真環(huán)境為搭載3.29 GHz Intel Core CPU、8GB內存和Windows 7 OS的計算機。

仿真場景設定參數與文獻[14]一致，假設有4顆單址天線中繼衛(wèi)星和20個用戶航天器。用戶共提交了500個任務，計劃于2017年12月1日0時到2017年12月7日0時之間執(zhí)行。每項任務包括1～3個備選服務時間窗口，備選服務時間窗口開始時間的可前移時段和可后移時段的長度服從正態(tài)分布N(1800,300)，備選服務時間窗口的期望時長服從正態(tài)分布N(900,300)。任務開始前天線對準時間設定為600 s，任務結束后天線復位時間設定為240 s。此外，在同一中繼衛(wèi)星調度場景下，將本所提算法與基于時間自由度的啟發(fā)式算法(Heuristic Algorithm based on Time Freedom Degree, HA-TFD)[14]比較。HA-TFD的主要步驟如下：

Step1：遍歷任務集T，WINmax為任務集T中的最大備選服務時間窗口數量，wint為當前任務t的備選服務時間窗口數量，wint,α為任務t指定天線時的備選服務窗口數量。

Step2：根據式(15)依次計算T中任務的時間自由度。

TFDt=(WINmax+1-wint)+

(WINmax-wint+wint,α)

(15)

Step3：依次從任務集T中選取TFDt值最高的任務t。

Step4：遍歷任務t的可用時間窗口，為其安排合適的服務資源以形成調度方案，并從任務集T中刪除已被調度的任務t。

Step5：如果T=?，算法結束；否則轉到Step3。

3.2 實驗結果

將算法重復運行20次，取各項評價指標的平均值，實驗結果見表2。由表2可知，所提SA-SE能將HA-TFD的任務完成率從76.4%提高至82.4%。但SA-SE的運行時間較長，其使用近158 s的時間完成500項任務的調度，相比HA-TFD，為典型的“以時間換精度”。總體上，運用SA-SE求解中繼衛(wèi)星調度問題能夠獲得更高質量的調度方案，較大程度上滿足用戶的實際需求，適用于對調度方案質量要求較高的工作場景。

表2 算法性能比較

3.3 參數影響分析

為了研究不用參數對算法性能的影響，在上文構建的中繼衛(wèi)星調度場景中，依次按照不同任務規(guī)模(表3場景編號1～6)、不同用戶航天器數量(表3場景編號3和編號7～11)、不同中繼衛(wèi)星數量(表3場景編號3和編號12～16)以及不同最大備選服務時間窗口數量(表3場景編號3和編號17～20)，對本文提出的調度算法性能的變化進行分析，實驗結果見表3。

表3場景編號1～6的結果顯示：隨著任務規(guī)模的擴大，算法的平均任務完成數量增大，當到達一定數值之后，增長速度明顯降低，此時中繼衛(wèi)星系統(tǒng)資源已接近最大程度被利用，難以實現進一步增長。而隨著任務規(guī)模的擴大，算法的平均任務完成數量增長速度小于任務申請數量的增長速度，平均任務完成率呈現下降趨勢。算法平均運行時間則隨任務規(guī)模的擴大迅速增長。因此，任務規(guī)模對算法性能和調度工作影響很大。

表3場景編號3和編號7～11的結果表明：隨著用戶航天器數量的增加，算法平均任務完成數量呈現一定的波動，平均任務完成率呈現相應波動。平均算法運行時間在不同用戶航天器數量場景下基本保持平穩(wěn)。因此，用戶航天器數量對算法性能和調度工作影響較小。

表3場景編號3和編號12～16的結果表明：隨著中繼衛(wèi)星數量的增加，算法平均任務完成數量增大，當到達一定數值之后，增長速度明顯降低；相應地，平均任務完成率呈現相同趨勢。算法平均運行時間隨中繼衛(wèi)星數量的增大平穩(wěn)增長。因此，中繼衛(wèi)星數量對算法性能和調度工作影響很大。

表3場景編號3和編號17～20的結果顯示：隨著最大備選服務時間窗口數量的增加，算法平均任務完成數和平均任務完成率平穩(wěn)增長，增長至4個備選服務窗口結束并略有波形。平均算法運行時間在不同用戶航天器數量場景下基本保持較為穩(wěn)定的增長。因此，用戶航天器數量對算法性能和調度工作有一定影響，設置合適的最大備選服務時間窗口數量，有利于調度工作質量的提高。

表3 不同參數下的算法實驗結果

4 結論

針對中繼衛(wèi)星單址天線調度問題，重點考慮了調度任務間的沖突與用戶的實際需求。為了更加符合實際情況，最大程度體現用戶申請的自主性和靈活性，設計了多滑動窗口用戶申請的中繼衛(wèi)星應用模式，允許用戶提交多個備選服務窗口，指定偏好天線。同時，以最大化任務完成率為目標函數，以任務需求約束、資源使用約束作為約束條件，構建了中繼衛(wèi)星調度問題的數學規(guī)劃模型。并借鑒智能優(yōu)化算法隨機搜索的思想來指導鄰域搜索，設計了基于隨機搜索策略的中繼衛(wèi)星調度算法，較好地解決了多中繼衛(wèi)星多用戶航天器大規(guī)模調度問題。實驗結果表明：基于沖突消解和隨機搜索策略的算法適用于對調度方案質量要求較高的工作場景，其能獲得較高質量的調度方案，但不足之處在于算法運行時間較長。下一步的研究將結合智能優(yōu)化算法，設計高效穩(wěn)定的鄰域結構和改進策略，在保持調度方案質量的同時，進一步提高調度效率。同時針對中繼衛(wèi)星存在數據傳輸、測控等多樣性任務的需求，研究多址模式的調度算法。