王官龍,宋建國,陳慧偉,范志勇,侯光華

(西安衛(wèi)星測控中心,西安 710043)

0 引 言

中高軌衛(wèi)星軌道類型差異大,可見時間窗口長,使得中高軌衛(wèi)星在遙測、遙控、測軌、數傳等任務類型需要的設備類型、跟蹤時長存在明顯的差異,同時多個弧段、不同任務類型之間還有關聯約束要求,再疊加上設備支持能力存在差異,導致中高軌衛(wèi)星資源調度問題求解復雜度相比低軌衛(wèi)星呈指數級上升。中高軌衛(wèi)星所需任務需求中,遙測數據接收任務占用設備跟蹤時長最多,通常需要多套設備通過接力跟蹤完成,單個弧段的跟蹤時長和切換時刻自由度較大,且跟蹤時間窗口沒有確定的時刻,進一步增加了調度計算的自由度。中高軌衛(wèi)星因可見時間長造成相同時段有多個設備可選,使得多個衛(wèi)星搶同一點位設備的沖突更為明顯。以上這些因素都增加了中高軌衛(wèi)星遙測任務調度的復雜性。

關于資源調度算法研究,以往研究以低軌衛(wèi)星資源調度較多[1-4],以美國空軍衛(wèi)星控制網的調度系統(tǒng)研究最有參考價值,其中遺傳算法、啟發(fā)式算法(Spider Wasp Optimizer,SWO)、隨機本地搜索算法(Random Local Search,RLS)的性能較好,在應對超量需求的調度問題(需處理的調度申請數量超過資源最大滿足數)時,啟發(fā)式算法在保持較好性能時算法實現復雜度度較低[1,5]。但已有的調度算法基本只針對固定弧長的調度模型,并不能較好地解決中高軌衛(wèi)星遙測任務調度時中面臨的設備時長和切換時刻都存在自由度的資源調度難題。

本文以中高軌衛(wèi)星遙測任務需求整體滿足率最大和算法復雜度低為設計目標,基于從人工安排中高軌遙測任務測控工作計劃的經驗數據中提取的先驗信息,提出一種基于先驗信息的中高軌衛(wèi)星遙測任務資源調度算法。結合我國測控站布站的實際情況,從中高軌衛(wèi)星任務對資源的需求開始,建立中高軌衛(wèi)星的遙測任務需求模型,在給定的可用設備范圍內,研究中高軌衛(wèi)星遙測任務資源調度算法,配合優(yōu)化迭代,使該算法能兼顧較好的調度效率和調度質量。

1 調度需求模型

通常資源調度問題模型可用以下要素描述:一組衛(wèi)星及其需求的任務類型、時間窗口、約束條件,一組測控資源及設備能力和可見預報,以及調度優(yōu)化目標。在需求側一個典型的中高軌衛(wèi)星資源需求可以模型化為(S,C,L,RW),其中,S表示衛(wèi)星代號,C表示該衛(wèi)星需求的任務類型(遙測、遙控、測軌、數傳或其組合),L表示衛(wèi)星S需求的最小服務時長,R表示該衛(wèi)星的可用資源(支持衛(wèi)星需求任務類型,上標W表示衛(wèi)星S對資源R的可見窗口,包括一個開始時間和一個結束時間)。衛(wèi)星S在資源R的時間窗口內,滿足最小服務時長L的弧段可能有K個(K的數量取決于當前可見窗口長度包含最小服務時長的數量),將其中每個滿足的弧段定義為一個可行解f=(S,C,L,RW)k,0≤k

中高軌衛(wèi)星遙測任務可行解模型如圖1所示。假定有3顆中高軌衛(wèi)星S1、S2、S3(S1代表MEO類衛(wèi)星典型遙測接收任務需求,S2和S3代表IGSO類衛(wèi)星典型遙測接收任務需求),衛(wèi)星的遙測跟蹤需求窗口如圖中豎實線所示,虛線框表示R1、R2、R3、R4設備在需求窗口內的可用時長。多個衛(wèi)星對同一個設備存在競爭,如設備R1對衛(wèi)星S1、S2和S3都是可用資源,依據人工制定遙測跟蹤計劃的經驗,R1最好的分配策略是優(yōu)先分配給S2或S3衛(wèi)星,然后S1和S2(或S3,取決于R1優(yōu)先用于S2或S3)衛(wèi)星繼續(xù)在R2、R3和R4設備上進行拼接來滿足需求,而且每個分配弧段的長度不是一個唯一的固定值。

圖1 中高軌衛(wèi)星遙測任務需求的可行解空間模型

2 調度算法設計

2.1 提取先驗信息

基于中高軌衛(wèi)星資源調度問題的復雜性,中高軌衛(wèi)星遙測數據接收任務資源調度往往采用人工制定計劃的方式,由此積累了大量歷史計劃數據,從 這些歷史計劃數據中提取出人工制定中高軌衛(wèi)星遙測數據接收計劃的有價值信息,作為中高軌衛(wèi)星遙測任務資源調度中優(yōu)先分配設備的初始先驗信息。IGSO衛(wèi)星軌道重復周期為24 h,其遙測數據接收的需求具有明顯的周期特征,因此在特定時間段的可見設備也有一定的周期特征?；谝陨线@些重要的先驗信息,對某個衛(wèi)星的遙測任務需求在調度算法中按先驗信息給出的設備使用優(yōu)先級進行分配,多顆衛(wèi)星在分配到同一套設備時按照優(yōu)先級順序競爭使用,可在工程實踐中達到較好的調度效果和降低算法復雜度的平衡。

2.2 資源調度算法流程設計

基于提取的先驗信息為每個衛(wèi)星的遙測任務需求配置可用設備優(yōu)先級,在資源調度時按照配置的設備優(yōu)先級進行資源調度。中高軌衛(wèi)星遙測任務初始先驗信息如表1所示,表中設備代號后括號中數值為該設備用于當前衛(wèi)星遙測數據接收任務的優(yōu)先使用順序,優(yōu)先級數值越小,代表優(yōu)先級越高。基于給出的設備使用優(yōu)先級使用信息,同步設計了相應的資源調度算法流程,如圖2所示。

表1 中高軌衛(wèi)星遙測任務先驗信息

圖2 中高軌衛(wèi)星遙測任務資源調度算法流程

Step1 設每一個需求窗口為一個目標區(qū)間W,該窗口區(qū)間的可行解集合為∑Qn,t,構建所有衛(wèi)星的可行解空間∑∑Qn,t。

Step2 計算各目標窗口區(qū)間的資源覆蓋率,即計算該窗口的可行解集合∑Qn,t對窗口區(qū)間W的覆蓋性,方法是將n個可行解與窗口W的時長比值相加,即為該目標窗口的覆蓋率P。

Step3 選取覆蓋率P最小的目標區(qū)間W,即從資源滿足率最小的目標窗口開始,使沖突資源優(yōu)先分配給可用資源最少的目標。

Step4 在選定的目標區(qū)間W,計算其每一個可行解Qn,t在解空間∑∑Qn,t中的有銜接和沖突概率Pc,計算該可行解與解空間所有弧段重疊時間,從中選出優(yōu)先級最高的可行解。

Step5 更新目標區(qū)間W可行解集合,調整可行解集合∑Qn,t中與當前選擇弧段時間重疊的弧段開始或結束時間,即逐步縮小目標區(qū)間W的長度,直到目標區(qū)間W小于等于零時,將該區(qū)間的所有剩余可行解全部清除。

Step6 更新其他目標窗口的可行解集合∑Qn,t,即調整該目標區(qū)間的可行解集合,消除與當前選擇弧段設備沖突弧段的開始和結束時間。

Step7 重新計算各目標區(qū)間的資源覆蓋率,回到Step 2,從中選出下一個優(yōu)選弧段。

對按一定優(yōu)先級和順序調度處理后,仍有沖突而未分配的需求,可在已制定的無沖突計劃基礎上使用窗口滑動、設備交換、需求變更[6-8]等方式進行優(yōu)化處理,完成最終計劃的制定。

中高軌衛(wèi)星可見時間窗口較長,各種任務的需求區(qū)間時長小于可見窗口長度,需求區(qū)間可在可見窗口內進行較大范圍的滑動,具有可移動性。單遙測類任務的需求區(qū)間雖然不能滑動,但中高軌衛(wèi)星因軌道高度高,同一需求區(qū)間可能有多套設備可見,可將單遙測類計劃交換到其他設備。通過對選定的目標設備時間區(qū)間內已分配計劃的滑動、交換,將沖突的任務插入。圖3所示為當前占用資源R1的任務隊列S1,S2,S3…按任務開始時間順序排列。假設選定在弧段S2_R1和S3_R1之間插入沖突弧段S5_R1,在S2_R1和S3_R1之間的空閑時長不滿足弧段S5_R1的需求區(qū)間時長時,考慮將S2_R1及其之前的弧段向前、S3_R1及其之后的弧段向后滑動,或者交換到其他設備。

圖3 回溯算法處理示意

中高軌衛(wèi)星遙測任務調度回溯算法基于以下規(guī)則實現。

1)沖突任務最大可滑動規(guī)則

弧段S2_R1最大前向可滑動時長,同時受S2_R1及其之前所有受影響的弧段最大可滑動時長約束。不僅要考慮S2_R1可見預報窗口前沿(S2_R1可見預報前沿S2_BV),還要考慮S2_R1之前任務S1_R1等的可見預報窗口前沿(S1_R1可見預報前沿S1_BV)約束(S2_R1向前滑動到S1_R1后沿的時長不足以插入沖突弧段S5_R1前沿,還需要S1_R1繼續(xù)向前滑動直到可插入弧段S5_R1的前沿)。同理,弧段S3_R1最大后向可滑動時長,同時受S3_R1及其之后所有受影響的弧段最大可滑動時長約束。

2)可交換任務規(guī)則

對最大可滑動策略不滿足弧段,或者不能滑動的弧段,可繼續(xù)嘗試將其交換到同需求區(qū)間的其他設備。首先確定可交換集和∑Qt?？山粨Q任務Qt的確定應符合以下要求:Qt是已安排的任務計劃;Qt不是特殊性質的任務(指定設備)。

將任務交換到Qt后,如果仍不能滿足插入弧段的需求區(qū)間,對下一個沖突弧段繼續(xù)執(zhí)行最大可滑動規(guī)則或者可交換規(guī)則。例如S3_R1是單遙測弧段,不可滑動,但可在需求區(qū)間不變的前提下將其交換到設備R2(S3_R2)。

3)回溯結束規(guī)則

處理到可調整出滿足需求區(qū)間的空閑時段時,本次回溯處理結束。回溯調度處理,直到碰到已達可滑動極限或者不可交換的任務,該選定資源的回溯處理結束。如果當前資源的回溯處理不能滿足需求,則轉到下一個選定資源進行回溯處理,直到找出可調整的資源或者全部可選資源已回溯處理完。

4)需求降低規(guī)則

對回溯處理仍不能滿足需求的任務,最后可考慮進行降低需求處理。例如一體化遙測需求的最短服務時長是4 h,在現有設備上已經找不到符合需求的空閑時段時,可考慮將不滿足最小服務時長但空閑的時段繼續(xù)進行分配,以保證滿足率最大的目標。

3 軟件實例分析

使用本文設計的基于先驗信息的中高軌衛(wèi)星資源調度算法,在一個時間周期(7天)內,衛(wèi)星任務需求如表2所示,單遙測申請時長2 220.56 h,可用設備情況如表3所示,測試環(huán)境配置如表4所示,中高軌衛(wèi)星資源資源分配情況如表5所示,計劃分布情況如表6所示。表3中,12套設備除支持遙測功能外,還同時支持測控數傳一體化、遙控測軌;15套支持遙控、測軌功能的設備包括支持測控數傳一體化的5套設備和支持C頻段的3套設備。

表2 中高軌衛(wèi)星資源需求情況

表3 中高軌衛(wèi)星調度可用設備能力情況

表4 測試環(huán)境參數配置

表5 中高軌衛(wèi)星資源分配情況

表6 中高軌衛(wèi)星單遙測計劃在設備分布情況

4 結束語

本文從建立中高軌衛(wèi)星資源使用需求模型出發(fā),以整體滿足率最高為目標,基于有限的可用設備時間、支持的功能,提取人工安排中高軌衛(wèi)星遙測接收計劃的有益信息作為先驗信息,為中高軌衛(wèi)星遙測單收任務可行解賦予設備使用優(yōu)先級,作為中高軌衛(wèi)星遙測接收資源調度的基本依據,并開發(fā)相應軟件進行仿真分析,單遙測申請滿足率超過99.7%,單遙測任務在15套單遙測設備分布占比達到97.7%,平均每臺單遙測設備的利用時長達到144.68 h,設備負荷率達到86.11%,實現了較好的調度效益。

本文是對中高軌衛(wèi)星遙測需求調度算法的一個有益工程性嘗試,但由于算法只研究了中高軌衛(wèi)星調度策略,較多考慮工程實現和降低計算量,回溯調整處理未進行多重調度回溯,沒有達到最優(yōu)解。后續(xù)將提出更加合理的中高軌衛(wèi)星資源調度模型,為我國航天器一體化調度算法研究提供參考。