夏 磊，俞能海

(中國科學技術(shù)大學中國科學院電磁空間信息重點實驗室，安徽合肥230027)

0 引言

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

與傳統(tǒng)AFSCN等衛(wèi)星通信系統(tǒng)不同的是，適用于小衛(wèi)星通信系統(tǒng)的地面站網(wǎng)絡(luò)被稱為學術(shù)型地面站網(wǎng)絡(luò)，這類地面站主要被科研機構(gòu)用于對小衛(wèi)星進行操控，數(shù)據(jù)下載等操作，具有沖突窗口多、非盈利、低成本等特點，小衛(wèi)星的調(diào)度問題目前還沒有過多的研究。文中在充分分析了小衛(wèi)星學術(shù)地面站任務(wù)調(diào)度問題的前提下，在對比了傳統(tǒng)地面站網(wǎng)絡(luò)和學術(shù)型地面站網(wǎng)絡(luò)的不同點后，針對學術(shù)型地面站網(wǎng)絡(luò)與小衛(wèi)星任務(wù)調(diào)度中出現(xiàn)的冗余調(diào)度問題進行了研究，定義了冗余調(diào)度公平性函數(shù)，并證明了其對于調(diào)度的公平性。選取Cubsat［9］體系中三個地面站和四顆小衛(wèi)星進行仿真實驗，利用STK工具得到衛(wèi)星與地面站的通信時間窗口，基于遺傳算法對可通信時間窗口進行優(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)星的運行特點，小衛(wèi)星和地面站的通信受到可見窗口的限制，如圖1所示得出可見分析:地理可見，表示地面站剛好進入到衛(wèi)星的掃描邊緣，但是此時的地面站還不可以進行通信，只是地理意義上的可見;仰角可見，衛(wèi)星繼續(xù)運行，當衛(wèi)星和地面站達到仰角可見范圍是，地面站開始對衛(wèi)星進行跟蹤和姿態(tài)調(diào)整，這里需要一定的重構(gòu)時間，這段時間不可通信;通信可見，在進行了一定的調(diào)整之后，地面站與衛(wèi)星將建立穩(wěn)定的通信鏈路，為可通信窗口時間段 T4－T3。

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

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

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

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

2 冗余調(diào)度

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

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

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

定義公平函數(shù):

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

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

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

分三種情況討論證明:

(1)若Tsat_1=Tsat_2

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

(2)若 Tsat_1≤Tsat_2

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

(3)若 Tsat_1≥Tsat_2

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

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

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

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

?wm存在可通信窗口;

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

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

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

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

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

4 仿真實驗

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

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

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

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

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

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

5 結(jié)語

文中通過對于傳統(tǒng)衛(wèi)星調(diào)度問題進行詳細的研究和分析，結(jié)合近十幾年小衛(wèi)星的發(fā)展，對學術(shù)型地面站網(wǎng)絡(luò)和低軌小衛(wèi)星網(wǎng)絡(luò)的調(diào)度問題進行了分析和研究。對于學術(shù)型地面站網(wǎng)絡(luò)中非盈利特性以及共享資源使得在小衛(wèi)星任務(wù)調(diào)度中存在的冗余調(diào)度問題進行了研究，提出了時間粒度上的公平函數(shù)的概念，定義公平函數(shù)，在學術(shù)小衛(wèi)星任務(wù)調(diào)度中，綜合考慮星站之間通信效率和公平性問題進行了最終優(yōu)化目標函數(shù)的定義，對于該問題采用效果最好的遺傳算法進行仿真調(diào)度實驗。仿真結(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è)計與實現(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］ 盧亮，張婷，鄧磊．北斗導航民用市場分析研究［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］ 李玉慶，王日新，徐敏強，等．基于改進遺傳算法的一類多資源測控調(diào)度問題研究［J］．宇航學報，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］．湖南:國防科學技術(shù)大學，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)度問題的演化學習型蟻群算法［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．