基于遺傳算法的小衛(wèi)星任務(wù)調(diào)度

夏 磊，俞能海

(中國科學(xué)技術(shù)大學(xué)中國科學(xué)院電磁空間信息重點(diǎn)實(shí)驗(yàn)室，安徽合肥230027)

0 引言

過去的十幾年內(nèi)，現(xiàn)代小衛(wèi)星由于其獨(dú)特的優(yōu)勢，逐步得到了國內(nèi)外研究者的青睞，小衛(wèi)星的數(shù)量也在不斷的增加，然而用于控制接收小衛(wèi)星數(shù)據(jù)的地面站數(shù)量卻不多。目前學(xué)術(shù)型地面站在世界范圍內(nèi)的分布主要集中在北美以及歐洲等國家，我國僅臺灣NCKU［1］擁有一個(gè)自己的低成本學(xué)術(shù)型地面站。國內(nèi)對于衛(wèi)星通信技術(shù)的研究主要集中在軍事領(lǐng)域［2］，在民用［3］和學(xué)術(shù)科研領(lǐng)域各大科研院所還未重視，然而伴隨著小衛(wèi)星技術(shù)的不斷成熟發(fā)展，高校以及科研院所的自主衛(wèi)星通信系統(tǒng)將逐步得到發(fā)展，因此學(xué)術(shù)型地面站網(wǎng)絡(luò)與小衛(wèi)星網(wǎng)絡(luò)的信息交互，特別是在任務(wù)調(diào)度方面具有十分重要的研究意義。傳統(tǒng)的衛(wèi)星任務(wù)調(diào)度 (SRS，Satellite Range Scheduling)問題一直是衛(wèi)星地面站交互的研究重點(diǎn)，美國的Barbulescu［4］等人對于傳統(tǒng)的衛(wèi)星調(diào)度問題進(jìn)行了詳細(xì)的研究，針對美國空軍衛(wèi)星控制網(wǎng)絡(luò) (Air Force Satellite Control Network)實(shí)際應(yīng)用場景進(jìn)行分析，證明了這種SRS問題在多站多星的應(yīng)用環(huán)境下屬于NP難問題，同時(shí)針對衛(wèi)星調(diào)度的幾種求解算法進(jìn)行了性能分析。李玉慶［5］提出了改進(jìn)遺傳算法來求解衛(wèi)星測控任務(wù)調(diào)度問題，文獻(xiàn) ［6－8］也對傳統(tǒng)衛(wèi)星任務(wù)調(diào)度問題進(jìn)行了分析研究。

與傳統(tǒng)AFSCN等衛(wèi)星通信系統(tǒng)不同的是，適用于小衛(wèi)星通信系統(tǒng)的地面站網(wǎng)絡(luò)被稱為學(xué)術(shù)型地面站網(wǎng)絡(luò)，這類地面站主要被科研機(jī)構(gòu)用于對小衛(wèi)星進(jìn)行操控，數(shù)據(jù)下載等操作，具有沖突窗口多、非盈利、低成本等特點(diǎn)，小衛(wèi)星的調(diào)度問題目前還沒有過多的研究。文中在充分分析了小衛(wèi)星學(xué)術(shù)地面站任務(wù)調(diào)度問題的前提下，在對比了傳統(tǒng)地面站網(wǎng)絡(luò)和學(xué)術(shù)型地面站網(wǎng)絡(luò)的不同點(diǎn)后，針對學(xué)術(shù)型地面站網(wǎng)絡(luò)與小衛(wèi)星任務(wù)調(diào)度中出現(xiàn)的冗余調(diào)度問題進(jìn)行了研究，定義了冗余調(diào)度公平性函數(shù)，并證明了其對于調(diào)度的公平性。選取Cubsat［9］體系中三個(gè)地面站和四顆小衛(wèi)星進(jìn)行仿真實(shí)驗(yàn)，利用STK工具得到衛(wèi)星與地面站的通信時(shí)間窗口，基于遺傳算法對可通信時(shí)間窗口進(jìn)行優(yōu)化調(diào)度。文中的研究將會為我國未來小衛(wèi)星事業(yè)的發(fā)展奠定一定的理論基礎(chǔ)。

1 問題分析與建模

衛(wèi)星任務(wù)調(diào)度(SRS)問題作為NP難問題與傳統(tǒng)地面上job－shop調(diào)度問題的主要區(qū)別在于存在著幾大限制:窗口限制，資源限制和任務(wù)限制。由于LEO衛(wèi)星的運(yùn)行特點(diǎn)，小衛(wèi)星和地面站的通信受到可見窗口的限制，如圖1所示得出可見分析:地理可見，表示地面站剛好進(jìn)入到衛(wèi)星的掃描邊緣，但是此時(shí)的地面站還不可以進(jìn)行通信，只是地理意義上的可見;仰角可見，衛(wèi)星繼續(xù)運(yùn)行，當(dāng)衛(wèi)星和地面站達(dá)到仰角可見范圍是，地面站開始對衛(wèi)星進(jìn)行跟蹤和姿態(tài)調(diào)整，這里需要一定的重構(gòu)時(shí)間，這段時(shí)間不可通信;通信可見，在進(jìn)行了一定的調(diào)整之后，地面站與衛(wèi)星將建立穩(wěn)定的通信鏈路，為可通信窗口時(shí)間段 T4－T3。

圖1 衛(wèi)星任務(wù)調(diào)度可見時(shí)間窗口Fig．1 Contact window of SRS problem

在一個(gè)調(diào)度時(shí)間周期內(nèi)，通常一個(gè)星期，LEO衛(wèi)星可能會與同一個(gè)地面站存在許多可通信窗口，但是由于衛(wèi)星通信受到例如太陽直射，云層厚度等多方面干擾，不同時(shí)間段的可通信時(shí)間窗口效率受到這些因素的影響，Spangelo［10］等人對于星站通信效率進(jìn)行了細(xì)致的研究，因此在問題的分析建模中，不同星站的窗口效率是文中最終優(yōu)化調(diào)度的重點(diǎn)影響因素。

由于可通信時(shí)間窗口在給定衛(wèi)星參數(shù)以及地面站參數(shù)之后已經(jīng)固定，只需要對調(diào)度任務(wù)進(jìn)行數(shù)學(xué)建模:

參數(shù)說明:tstart:任務(wù)最早開始時(shí)間;tend:任務(wù)最晚結(jié)束時(shí)間;dur:任務(wù)需求的持續(xù)時(shí)間;Uu:任務(wù)的發(fā)起者;Ss:任務(wù)指向的執(zhí)行衛(wèi)星;TGOS:衛(wèi)星與地面站可通信時(shí)間開始時(shí)刻;TLOS:衛(wèi)星與地面站可通信時(shí)間結(jié)束時(shí)刻;Tij(wm):地面站j為任務(wù)i在某時(shí)間窗口wm內(nèi)提供的服務(wù)時(shí)間;Tsj(wm):地面站j和衛(wèi)星s的可通信時(shí)間窗口wm的通信時(shí)間;Ps:衛(wèi)星權(quán)重;Esj(wm):地面站j和衛(wèi)星s的可通信時(shí)間窗口wm的通信效率。

2 冗余調(diào)度

學(xué)術(shù)地面網(wǎng)絡(luò)與傳統(tǒng)地面網(wǎng)存在這許多不同點(diǎn)，最明顯的一個(gè)不同就是學(xué)術(shù)網(wǎng)主要承擔(dān)的是一些非商業(yè)性質(zhì)的研究任務(wù)，所有接入者均希望最大化使用自己的衛(wèi)星資源，希望自己得到的服務(wù)時(shí)間充分，并不在乎具體是哪個(gè)地面站提供的服務(wù)，但是由于小衛(wèi)星的數(shù)量增加和一箭多星技術(shù)成熟，使得多顆衛(wèi)星同時(shí)覆蓋一個(gè)地面站的情況相較于傳統(tǒng)的衛(wèi)星地面站網(wǎng)絡(luò)而言出現(xiàn)頻率更多，從而產(chǎn)生大量的沖突窗口，地面站在提供服務(wù)的時(shí)候存在選擇性問題，傳統(tǒng) FGN(Federated Ground Network)網(wǎng)絡(luò)［11－12］考慮任務(wù)需求衛(wèi)星的權(quán)重進(jìn)行沖突窗口的調(diào)配(如圖2所示)，但是單純的以衛(wèi)星權(quán)重作為調(diào)度的衡量標(biāo)準(zhǔn)會使得權(quán)重大的請求會占用非常多的可通信窗口以至于一些衛(wèi)星權(quán)重比較低的請求無法被調(diào)度，相同衛(wèi)星權(quán)重的任務(wù)之間的窗口調(diào)度為隨機(jī)調(diào)度，對于這種非盈利的學(xué)術(shù)研究請求，需要考慮公平性問題，德國研究小組Schmidt［13］等人針對該問題提出了冗余調(diào)度的概念，即對于沖突造成的冗余窗口如何分配。

圖2 沖突窗口的調(diào)度問題Fig．2 Contact window confliction scheduling

文獻(xiàn)［11］以每顆衛(wèi)星分配的通信窗口數(shù)目進(jìn)行公平性定義，這種定義方式在一定程度上可以體現(xiàn)任務(wù)調(diào)度的公平性，但是由于不同通信窗口的通信時(shí)間不同，簡單的以調(diào)度窗口數(shù)目為評判標(biāo)準(zhǔn)是不充分的，文中以每一顆衛(wèi)星最終分配到的服務(wù)時(shí)間來進(jìn)行公平性的判別，在時(shí)間粒度上重新定義了公平性函數(shù)，公平函數(shù)值越小則公平性越大，對公平性的判斷進(jìn)行了數(shù)學(xué)分析，證明了在任務(wù)需求衛(wèi)星優(yōu)先級相同的前提下，不同任務(wù)請求最終分配到的服務(wù)時(shí)間越相近則越公平。定義每一顆小衛(wèi)星最終調(diào)度分配的服務(wù)時(shí)間:

定義公平函數(shù):

最終的優(yōu)化目標(biāo)則是在保障星站利用度函數(shù)值大的情況下，盡可能的減小公平函數(shù)的函數(shù)值。

假設(shè)兩顆小衛(wèi)星最終調(diào)度后的服務(wù)時(shí)間分別為Tsat_1和Tsat_2，公平函數(shù)計(jì)算結(jié)果為:

如果小衛(wèi)星1與小衛(wèi)星2存在可視窗口上的沖突，那么在調(diào)度的時(shí)候就存在一個(gè)沖突時(shí)間重分配的問題，這里假設(shè)小衛(wèi)星1在最公平調(diào)度分配下讓出一部分時(shí)間 t給小衛(wèi)星2，那么新的公平函數(shù)值為:

分三種情況討論證明:

(1)若Tsat_1=Tsat_2

明顯可知f'≥f，也就是說倘若最終調(diào)度結(jié)果中，小衛(wèi)星1和小衛(wèi)星2分配的服務(wù)時(shí)間是相等的話，那么定義的公平函數(shù)將會是最小值，如果這時(shí)候再從小衛(wèi)星1的調(diào)度時(shí)間里抽調(diào)服務(wù)時(shí)間給小衛(wèi)星2，那么將會使得公平函數(shù)值變大，破壞公平性。

(2)若 Tsat_1≤Tsat_2

則f'≥f，當(dāng)最終調(diào)度結(jié)果小衛(wèi)星1的服務(wù)時(shí)間已經(jīng)小于小衛(wèi)星2分配的服務(wù)時(shí)間時(shí)，如果再從小衛(wèi)星1里面調(diào)度服務(wù)時(shí)間給小衛(wèi)星2，那么明顯的會破壞公平性，公平函數(shù)值變大。

(3)若 Tsat_1≥Tsat_2

則有f'≤f，如果最終調(diào)度結(jié)果小衛(wèi)星1的服務(wù)時(shí)間比小衛(wèi)星2的服務(wù)時(shí)間長，此時(shí)可以再不擴(kuò)大公平函數(shù)值的前提下抽調(diào)一部分衛(wèi)小星1的服務(wù)時(shí)間給小衛(wèi)星2，也就是沖突窗口的時(shí)間分配一部分給服務(wù)時(shí)間少的衛(wèi)星，會提高公平性。

3 目標(biāo)函數(shù)設(shè)定

前文中對小衛(wèi)星地面站調(diào)度問題進(jìn)行數(shù)學(xué)建模，冗余調(diào)度分析，考慮到學(xué)術(shù)性小衛(wèi)星使用上的公平性原則，對于每一顆小衛(wèi)星的任務(wù)在衛(wèi)星權(quán)重上做出相等的前提假設(shè)。優(yōu)化目標(biāo)設(shè)置為等衛(wèi)星權(quán)重下的小衛(wèi)星與地面站網(wǎng)絡(luò)利用效率與小衛(wèi)星最終分配服務(wù)時(shí)間公平性函數(shù)的組合，通過調(diào)節(jié)每一個(gè)優(yōu)化目標(biāo)的權(quán)重值，使得最終的優(yōu)化目標(biāo)達(dá)到最好效果。

調(diào)度需要滿足下面限制條件:

?wm存在可通信窗口;

Topreation_start≥tstart調(diào)度后任務(wù)執(zhí)行開始時(shí)間要在任務(wù)最早開始時(shí)間之后;

Toperation_end≤tend調(diào)度后任務(wù)執(zhí)行結(jié)束時(shí)間要在任務(wù)最遲完成時(shí)間之前;

Toperation_end－Toperation_start≥dur調(diào)度后任務(wù)執(zhí)行總時(shí)間需滿足任務(wù)持續(xù)時(shí)間要求;

{Toperation_end，Toperation_start}∈∪{TGOS，TLOS}調(diào)度后任務(wù)的調(diào)度時(shí)間需要存在于某個(gè)可通信窗口內(nèi)。

從定義的優(yōu)化目標(biāo)函數(shù)中可以看出，在小衛(wèi)星權(quán)重相同的前提下最大化小衛(wèi)星與地面站網(wǎng)絡(luò)的利用度，同時(shí)保障不同任務(wù)之間的調(diào)度公平性，P值越大，說明調(diào)度結(jié)果越好，一方面需要增加調(diào)度結(jié)果中窗口的利用度，另一方面則需要減減小公平函數(shù)的值。

4 仿真實(shí)驗(yàn)

衛(wèi)星任務(wù)調(diào)度問題屬于NP難解問題［4］，伴隨著衛(wèi)星，地面站以及任務(wù)請求數(shù)量的增加，問題的求解復(fù)雜度十分的高，并且傳統(tǒng)的貪婪算法等并沒有辦法求解出一個(gè)全局最優(yōu)解，對于該種調(diào)度問題，Barbulescu［4］對遺傳算法在求解該類問題上進(jìn)行了性能分析，實(shí)驗(yàn)證明了遺傳算法可以得到比較優(yōu)良的全局優(yōu)化解，文中選取遺傳算法來求解相對全局最優(yōu)的解，對可通信窗口進(jìn)行二進(jìn)制編碼，以及優(yōu)化選擇種群個(gè)體進(jìn)行遺傳操作，定義遺產(chǎn)算法的迭代次次數(shù)為結(jié)束指標(biāo)進(jìn)行仿真。通過從世界上現(xiàn)役小衛(wèi)星網(wǎng)絡(luò)Cubesat系統(tǒng)中的地面站和小衛(wèi)星中選取3個(gè)地面站，4顆衛(wèi)星［14］，具體參數(shù)如表 1，表 2所示，利用STK軟件得出他們的可通信時(shí)間窗口，這些可通信窗口時(shí)間為T3－T4時(shí)間段，可進(jìn)行直接通信的時(shí)間，隨機(jī)賦予每一個(gè)通信窗口的衛(wèi)星－地面站通信效率值(0－100)，定義觀測時(shí)間為24小時(shí)，定義每一顆小衛(wèi)星的任務(wù)需求時(shí)間段為24小時(shí)的觀測周期內(nèi)，每一顆小衛(wèi)星需求15個(gè)完整的星站通信窗口。

表1 學(xué)術(shù)型地面站參數(shù)Table 1 Parameter of academic ground stations

表2 小衛(wèi)星參數(shù)Table 1Parameter of small satellites

定義優(yōu)化目標(biāo)函數(shù)為:

對遺傳算法進(jìn)行參數(shù)設(shè)置，種群數(shù)量設(shè)置為40，雜交概率1，變異概率0．2，定義最大迭代次數(shù)300。圖3為遺傳算法優(yōu)化過程中優(yōu)化目標(biāo)的典型進(jìn)化曲線，可以看出，伴隨著迭代次數(shù)的增加，50次迭代后，種群的適應(yīng)值基本達(dá)到收斂，但是由于是多目標(biāo)函數(shù)的優(yōu)化問題，所以后面的迭代存在一定的波動，迭代結(jié)束后得到一組相對最優(yōu)調(diào)度結(jié)果。由于遺傳算法得出的結(jié)果并不是一定是全局最優(yōu)解，這里進(jìn)行了多組相同參數(shù)下的仿真實(shí)驗(yàn)，并分別對他們最終的適應(yīng)值進(jìn)行比較，仿真結(jié)果數(shù)值如圖4顯示，仿真結(jié)果可以看出第五組的仿真調(diào)度結(jié)果最終的目標(biāo)函數(shù)值最大，從而選取第五組優(yōu)化結(jié)果作為最終調(diào)度結(jié)果。圖5為第五組優(yōu)化調(diào)度后小衛(wèi)星與地面站之間窗口分布甘特圖。

圖3 遺傳算法優(yōu)化目標(biāo)進(jìn)化曲線Fig．3 A typical curve of genetic algorithm

圖4 五組遺傳算法優(yōu)化調(diào)度結(jié)果數(shù)據(jù)對比Fig．4 Comparision of the five groups’result

圖5 第五組優(yōu)化調(diào)度甘特Fig．5 Gantt chart of the fifth scheduling result

五組遺傳算法最終的優(yōu)化目標(biāo)值、小衛(wèi)星服務(wù)時(shí)間均方差和星站總效率值如圖4所示，可以看出第五組優(yōu)化目標(biāo)函數(shù)值最大，第三組優(yōu)化結(jié)果在本次仿真中最差，從圖4中可以看出最終調(diào)度結(jié)果中地面站對于四顆衛(wèi)星提供服務(wù)時(shí)間的均方差，以及最終調(diào)度后目標(biāo)函數(shù)中星站效率的值。從圖中數(shù)據(jù)可以分析出，雖然第四組的各星服務(wù)時(shí)間均方差值最小，但是由于對于公平性優(yōu)化目標(biāo)的比重參數(shù)設(shè)置，綜合考慮調(diào)度后的星站總效率和公平性兩方面因素，選取第五組仿真優(yōu)化調(diào)度結(jié)果是最合適的。

5 結(jié)語

文中通過對于傳統(tǒng)衛(wèi)星調(diào)度問題進(jìn)行詳細(xì)的研究和分析，結(jié)合近十幾年小衛(wèi)星的發(fā)展，對學(xué)術(shù)型地面站網(wǎng)絡(luò)和低軌小衛(wèi)星網(wǎng)絡(luò)的調(diào)度問題進(jìn)行了分析和研究。對于學(xué)術(shù)型地面站網(wǎng)絡(luò)中非盈利特性以及共享資源使得在小衛(wèi)星任務(wù)調(diào)度中存在的冗余調(diào)度問題進(jìn)行了研究，提出了時(shí)間粒度上的公平函數(shù)的概念，定義公平函數(shù)，在學(xué)術(shù)小衛(wèi)星任務(wù)調(diào)度中，綜合考慮星站之間通信效率和公平性問題進(jìn)行了最終優(yōu)化目標(biāo)函數(shù)的定義，對于該問題采用效果最好的遺傳算法進(jìn)行仿真調(diào)度實(shí)驗(yàn)。仿真結(jié)果顯示遺傳算法對于這種多約束限制的衛(wèi)星調(diào)度問題有著很好的解決問題的能力。

［1］ HSIAO F B，LIU H P，CHEN C C．The Development of a Low－cost Amateur Microsatellite Ground Station for Space Engineering Education［J］．Global J of Engng Educ，2000，4(01):83－88．

［2］ 吳文敬，韓穎，張楨．綜合應(yīng)急指揮調(diào)度系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)［J］．通信技術(shù)，2013，46(04):103－105，108．WU Wen－jing，HAN Ying，ZHANG Zhen．Design and Implementation of Integrated Emergency Command＆Control System［J］．Communications Technology，2013，46(04):103－105，108．

［3］ 盧亮，張婷，鄧?yán)冢倍穼?dǎo)航民用市場分析研究［J］．通信技術(shù)，2013，46(05):101－103．LU Liang，ZHANG Ting，DENG Lei．Study on Civilian Market of Beidou Satellite Navigation［J］．CommunicationsTechnology，2013，46(05):101－103．

［4］ BARBULESCU L，WATSON J P，WHITLEY LD，et al．Scheduling Space-ground Communications for the Air Force Satellite Control Network［J］．Journal of Scheduling，2004，7(01):7－34．

［5］ 李玉慶，王日新，徐敏強(qiáng)，等．基于改進(jìn)遺傳算法的一類多資源測控調(diào)度問題研究［J］．宇航學(xué)報(bào)，2012，33(01):85－90．LI Yu－qing，WANG Ri－xin，XU Min－qiang，et al．An Improved Genetic Algorithm for a Class of Multi－Resource Range Scheduling Problem［J］．Journal of Astronautics，2012，33(01):85－90．

［6］ 李云峰．衛(wèi)星—地面站數(shù)傳調(diào)度模型及算法研究［D］．湖南:國防科學(xué)技術(shù)大學(xué)，2008．LI Yun－feng．Research on Satellite－Ground Station Data Transmission Scheduling Models and Algorithms［D］．Hunan:National University of Defense Technology，2008．

［7］ 姚鋒，邢立寧．求解衛(wèi)星地面站調(diào)度問題的演化學(xué)習(xí)型蟻群算法［J］．系統(tǒng)工程與電子技術(shù)，2012，34(11):2270－2274．YAO Feng，XING Li－ning．Learnable Ant Colony Optimization Algorithm for Solving Satellite Ground Station Scheduling Problems［J］．Systems Engineering and Electronics，2012，34(11):2270－2274．

［8］ 張紅旗．基于貪婪算法的衛(wèi)星地面站資源調(diào)度方法［J］．無線電工程，2010，40(12):4－6．ZHANG Hong－qi．Resource Scheduling Method of Satellite Ground Station based on Greedy Algorithm［J］．Radio Engineering，2010，40(12):4－6．

［9］ Wikipedia．CubeSat［DB/OL］．(2013－02－03)［2013－09－11］．http://en．wikipedia．org/wiki/CubeSat．

［10］ SPANGELO S，CUTLER J，KLESH A，et al．Models and Tools to Evaluate Space Communication Network Capacity［J］．Aerospace and Electronic Systems，IEEE Transactions，2012，48(03):2387－404．

［11］ JUNG－HYUN L，MYUNG WS，CHUNG D，et al．Multi－satellite Control System Architecture and Mission Scheduling Optimization［C］//Aerospace Conference．USA:IEEE，2012:1－13．

［12］ KOTA S L，GIAMBENE G，KIM S．IJSC＆N，Special Issue on‘hybrid/integrated Satellite-terrestrial Networks’［J］．International Journal of Satellite Communications and Networking，2011，29(03):187－90．

［13］ SCHMIDT M，SCHILLING K．A Scheduling System with Redundant Scheduling Capabilities［C］//International Workshop for Planning and Scheduling in Space．Pasadena:AAAI，2009:12－18．

［14］ James Cutler．Small Satellite Survey［DB/OL］．(2009－10－11)［2013－09－11］．http://gs．engin．umich．edu．