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

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

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

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

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

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

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

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

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

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

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

1.2 數(shù)學(xué)規(guī)劃模型

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

表1 符號定義

1.2.1 優(yōu)化目標

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

(1)

1.2.2 約束條件

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

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

(2)

(3)

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

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ù)所選的備選服務(wù)時間窗指定中繼衛(wèi)星天線，則必須使用當前任務(wù)計劃指定的中繼衛(wèi)星天線執(zhí)行該項任務(wù)，否則任務(wù)調(diào)度失敗。因此，任務(wù)的服務(wù)天線約束可表示為：

(6)

調(diào)度過程中任務(wù)的實際服務(wù)時長應(yīng)不大于任務(wù)的期望服務(wù)時長，同時不應(yīng)小于備選服務(wù)時間窗的最短服務(wù)時長。因此任務(wù)的服務(wù)時長約束可表示為：

stt,k,r,j≤ntt,k

(7)

stt,k,r,j≥tshortt,k

(8)

2)資源使用約束

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

[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)

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

(10)

(11)

(12)

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

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

2.1 算法流程描述

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

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

2.2 任務(wù)資源匹配與鄰域生成

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

(13)

2.3 實際服務(wù)時間窗生成

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

(14)

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

2.4 任務(wù)沖突分析

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

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

2.5 鄰域搜索與沖突消解

鄰域搜索與沖突消解主要根據(jù)任務(wù)沖突分析的結(jié)果，對“擾動-刪除”池中的任務(wù)進行隨機擾動，或?qū)⑷蝿?wù)刪除，逐步迭代消解任務(wù)沖突。該模塊共有3個步驟：

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

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

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

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

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

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

3 仿真實驗

3.1 實驗設(shè)置

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

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

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

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

TFDt=(WINmax+1-wint)+

(WINmax-wint+wint,α)

(15)

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

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

Step5：如果T=?，算法結(jié)束；否則轉(zhuǎn)到Step3。

3.2 實驗結(jié)果

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

表2 算法性能比較

3.3 參數(shù)影響分析

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

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

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

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

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

表3 不同參數(shù)下的算法實驗結(jié)果

4 結(jié)論

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