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

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

0 引 言

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

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

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

1 調(diào)度需求模型

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

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

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

2 調(diào)度算法設(shè)計(jì)

2.1 提取先驗(yàn)信息

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

2.2 資源調(diào)度算法流程設(shè)計(jì)

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

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

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

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

Step2 計(jì)算各目標(biāo)窗口區(qū)間的資源覆蓋率,即計(jì)算該窗口的可行解集合∑Qn,t對(duì)窗口區(qū)間W的覆蓋性,方法是將n個(gè)可行解與窗口W的時(shí)長(zhǎng)比值相加,即為該目標(biāo)窗口的覆蓋率P。

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

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

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

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

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

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

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

圖3 回溯算法處理示意

中高軌衛(wèi)星遙測(cè)任務(wù)調(diào)度回溯算法基于以下規(guī)則實(shí)現(xiàn)。

1)沖突任務(wù)最大可滑動(dòng)規(guī)則

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

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

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

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

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

處理到可調(diào)整出滿足需求區(qū)間的空閑時(shí)段時(shí),本次回溯處理結(jié)束?；厮菡{(diào)度處理,直到碰到已達(dá)可滑動(dòng)極限或者不可交換的任務(wù),該選定資源的回溯處理結(jié)束。如果當(dāng)前資源的回溯處理不能滿足需求,則轉(zhuǎn)到下一個(gè)選定資源進(jìn)行回溯處理,直到找出可調(diào)整的資源或者全部可選資源已回溯處理完。

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

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

3 軟件實(shí)例分析

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

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

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

表4 測(cè)試環(huán)境參數(shù)配置

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

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

4 結(jié)束語(yǔ)

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

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