基于離散粒子群算法的衛星地面站任務規劃系統

王崢

基于離散粒子群算法的衛星地面站任務規劃系統

王崢

（中國人民大學 信息學院，北京 100872）

衛星地面站是衛星通信系統的重要組成部分，主要作用是上注指令控制衛星，并接收和處理衛星發回的觀測數據。近年來衛星任務數量劇增，地面站資源相對不足，資源使用沖突日益明顯。為了提高地面站資源使用效率，針對多衛星、多地面站的測控類任務和數傳接收任務建立了任務規劃系統。具體流程為，首先，計劃接收子系統收到任務需求后對任務進行分類和預處理；其次，資源調度子系統采用基于離散粒子群算法（DPSO）的優化方法進行資源調度優化，為各任務安排合適的測控或接收資源；第三，任務資源下發子系統將各任務和需要的資源下發到各個地面站和相關的接收設備。任務規劃過程綜合考慮了任務時間約束、資源優先級、任務優先級、設備負載均衡等因素，系統應用到中國遙感地面站的實際生產環境中，真實案例分析證明了建模的合理性和算法的有效性。

任務規劃；衛星地面站資源調度；離散粒子群算法；數據交互

中國遙感衛星地面站有多個衛星地面站組成的地面站網，設備多，任務量大，任務規劃系統的建立是實現自動化、減少人工成本、提高生產效率的重要手段。同時需要建立與實際需求匹配的資源優化模型和可行的模型求解算法。

本文針對衛星地面站測控接收一體化業務，根據地面站接收資源包括天線信道及記錄器等資源約束建立數學模型求解。對此，趙和鵬確定了以啟發式搜索為主體的求解思路，給出了一種分治法和隨機化思想的貪婪算法，但缺少對于高分衛星系統的接收規劃調度能力。張為良建立了衛星地面站資源優化調度模型，但對于接收資源只考慮了接收天線的約束，實際接收過程中還有很多因素。

1 問題描述

衛星與地面站的數據交互任務分為測控任務和數據接收兩類任務。衛星過境地面站接收范圍時，地面站可執行測控或數據接收任務。地面站接收資源調度主要考慮天線資源和記錄器資源，各個地面站均設有多部資源設備，可同時接收多個衛星任務。對于數據接收任務，應先經天線資源接收，后由記錄器記錄后存儲。而測控任務包括遙控、遙測、測量等任務，只需使用天線資源，不需要記錄器資源。對同一地面資源來說，可同時執行同一衛星的測控和數據接收兩類任務，但不能同時執行兩個以上衛星的任務。任務規劃的目標是確定執行各個任務的地面資源，盡量多地執行數據交互任務，提高資源利用率。同時考慮到資源性能、用戶習慣、負載均衡等因素，獲取合理的地面資源使用方案。

2 任務規劃系統組成

任務規劃系統如圖1所示。根據衛星數據交互任務的處理流程，任務規劃系統可分為三個部分：計劃接收子系統、資源調度子系統、任務資源下發子系統。

圖1 任務規劃系統框圖

計劃接收子系統面向衛星接收計劃的獲取，驗證接收計劃文件，根據規則判斷計劃的可行性，針對接收計劃間沖突情況給出合理建議，對計劃的完成情況進行實時監測、上報，對衛星接收計劃和數據文件信息進行管理。

資源調度子系統面向衛星數據接收計劃與地面接收資源，根據業務規則等各項約束條件，完成對接收任務所需的各數據接收站接收設備、記錄設備、光纖傳輸鏈路資源的分配決策，快速形成合理優化的接收任務規劃方案。

任務資源下發子系統具備信息交換能力，具備境內外接收站的衛星數據接收記錄任務、數據傳輸任務、數據質量監測任務和原始數據監視顯示任務的信息交互能力，保障系統內外各類數據交換暢通。

3 基于DPSO資源調度優化方法

衛星與地面站的數據交互任務數量多，約束條件復雜，導致模型規模大，變量多，求解困難。考慮采用智能算法（DPSO）求解，可在可接受的求解時間內獲取可行解。

3.1 DPSO簡介

通過模仿鳥群覓食時所呈現的群體智能提出了粒子群算法（PSO）。具體的，鳥群中不同個體之間會交流和共享有關食物方位的信息，每個個體的覓食路徑都是在其自身判斷和其他同伴覓食經驗的共同影響下形成的，個體間合作與競爭等社會行為同時存在，使整個種群能夠更加“智能”地獲得食物。因此，PSO是一種基于群體智能的元啟發式算法。PSO算法中的粒子代表問題候選解且大量粒子以種群的形式共存于問題解空間。就如同鳥群在空中覓食一樣，PSO算法所制定的粒子更新與種群進化機制使粒子們在搜索空間內自適應地飛行，以尋找到一個具有最優目標函數值的期望落點。PSO算法中的粒子都具有關于最佳位置的記憶，這增進了群體內部的信息共享，并在一定程度上指導粒子決策各自的飛行路徑。從最初生成到當前代為止，對于每個粒子而言，它能夠記住其所落入過的最佳位置（記為），這代表粒子自身的搜尋經驗；對于種群而言，它能夠記住全部粒子所落入過的一個最佳位置（記為），這代表整個群體的搜尋經驗。在粒子間合作與競爭共存的氛圍下，PSO算法實現了全局搜索廣泛性和局部搜索深入性的良好平衡。

在PSO算法中，每個粒子都有位置和速度這兩種屬性，ik和ik分別表示維搜索空間中第代種群的第個粒子的位置和速度，其中位置表征問題候選解。ik=[i，1k，i，2k，…，i，Dk]和k=[1k，2k，…，Dk]分別表示截止到第代種群時，第個粒子和整個種群落入過的具有最優目標函數值的最佳位置。設種群內粒子總數為NP種群最大進化代數為，則標準PSO算法中的任意粒子按以下公式更新其速度：

i，k+1=i，k+11（i，k－i，k）+22（k－i，k）

?=1，2，…，NP，=1，2，…，，

=0，1，…，－1 （1）

式（1）中：慣性權重用于控制當前速度對更新后速度的影響大小；1和2為加速系數，分別反映粒子自身以及整個種群的飛行經驗對粒子更新后速度指導作用的強弱；1和2是兩個取值在[0，1]間均勻分布且相互獨立的隨機數。

可見，粒子會根據其當前速度以及當前位置與歷史最佳位置間的方位關系確定新的速度。在此基礎上，標準PSO算法中的任意粒子按以下公式更新其位置：

?=1，2，…，NP，=1，2，…，，

=0，1，…，－1 （2）

另外，粒子速度和位置中的每一維分量都會被分別限制在[，]和[，]范圍內，以避免粒子飛出搜索空間。在隨機搜尋和飛行經驗的共同作用下，以目標函數值為衡量指標，粒子不斷調整其落點，從而逐步接近甚至獲得問題的全局最優解。上述更新過程會不斷重復直至用戶為PSO算法設定的停止準則得到滿足。

標準PSO算法的流程如下所示。

步驟1：隨機初始化整個種群中每個粒子的速度和位置，使它們較為均勻地分布在可行解空間內。

步驟2：評價每個粒子，即計算其所代表的問題候選解的目標函數值，并將該初始位置和評價值分別設為其和的評價值；對于初始種群中評價值最優的粒子，將其位置和評價值分別設為和的評價值。

步驟3：根據式（1）和（2）更新整個種群中所有粒子的速度和位置。

步驟4：評價整個種群中所有粒子。

步驟5：比較每個粒子的當前評價值與其的評價值，如果當前評價值更優，則將其和的評價值更新為其當前位置和評價值。

步驟6：對于當前種群中評價值最優的，如果其評價值優于的評價值，則將和的評價值更新為該及其評價值。

步驟7：如果停止準則得到滿足，則以當前及其評價值作為最終結果，PSO算法終止；否則返回步驟3。由于粒子的候選解表征和更新公式都是針對連續變量設計的，所以標準PSO算法通常僅用于處理連續優化問題。作為PSO搜索機制和演化流程在離散優化領域的發展成果，DPSO保持PSO算法性能優良的全局尋優能力，從而能夠高效解決離散優化問題。其中，一類通過重新定義更新操作構造出的DPSO算法為PSO尋優思想在離散優化領域的應用提供了有效思路，并已在許多組合優化問題的求解中取得良好效果。該類DPSO算法[102，103]規定粒子的位置和速度均為離散編碼，設計交叉、變異等操作對粒子更新公式中的各類運算進行重新定義。我們選擇此類DPSO算法作為地面站資源調度優化算法。

3.2 算法流程

首先將所有任務集合按執行時間和地面站分為多個子集，對各個子集分別進行資源調度，將整體問題分解為多個子問題，減小了問題規模。對各個子集進行預處理，將測控和數傳任務分組，將同時進行的不同類型任務分為一組，然后對預處理后的各個子問題分別采用離散粒子群（DPSO）算法優化。

算法流程如圖2所示。

圖2 算法流程

3.3 算法適應度函數和求解步驟

適應度函數考慮4個因素：①天線的適用程度，即是否使用該任務對應的優先級高的天線；②記錄器的適用程度，即是否使用該任務對應的優先級高的記錄器；③任務完整接收程度和未接收時長；④是否多個任務在同一時間共用記錄器。操作人員通常要避免在同一臺記錄器上同時安排多個任務，以減少接收的風險。

收益為：

步驟1：預處理，首先獲取任務信息，包括衛星名、過境地面站、任務開始時間、任務結束時間、軌道號、任務編號、任務優先級、任務類型（測運控或數傳任務）、接收數據通道、接收任務作業方式、接收數據各通道碼速率、傳感器、是否主接收任務、任務分組號、是否需要備份接收任務等。其次獲取資源信息，包括地面站名稱、各站天線資源、記錄器資源等。通過衛星與地面站資源的使用約束，計算各個任務的資源約束，包括資源是否可用以及使用優先級等。同時，根據任務時間計算該任務時段是否可使用該資源。然后根據任務開始時間按先后順序排序，按衛星名稱分組。根據任務時間判斷各衛星是否存在“接力”接收任務。“接力”任務是指跨多個地面站接收區域的任務，可由多地面站協同接收。由于地面站接收區域有重疊，為了避免資源浪費，需要決策在重疊區域使用的地面站和接收資源。

步驟2：優化“接力”接收任務。根據接收資源使用規則優化“接力”任務的接收資源，確定接收任務的接收地面站。優化原則為兩地面站進行“接力”接收，需保證一定的重疊時間，即兩地面站同時執行接收任務的時段。優化后的任務集記為。

步驟3：將中的任務排序，按接收地面站分組，得到各地面站的任務集（）。地面站集合記為。

步驟4：初始化參數，包括慣性因子、加速常數c1和c2、種群規模、粒子的初始位置i和速度i、進化代數、收斂精度等。

初始化種群。獲取各任務的可選天線集合i。種群中各粒子位置i為[0，1]之間的小數，i×[i]的值取整表示任務的使用天線在i中的序號，由此可解碼獲取天線調度結果。

步驟5：根據適應度函數，計算各粒子適應值，即天線使用沖突的任務數量。

步驟6：找出個體和群體最優值以及最優位置。

步驟7：利用更新公式更新各粒子的位置和速度。如果更新后的粒子位置值大于1或小于0，采用高斯函數將其轉化為[0，1]范圍內的數。

步驟8：判斷是否滿足終止條件。如果是，轉步驟9，否則轉步驟7。

步驟9：結束。輸出計算結果。

4 結論

在衛星任務日益增多、地面站資源相對有限的情況下，衛星地面站任務規劃系統解決了衛星與地面站數據交互任務的接收和地面站資源調度問題，是衛星地面系統的核心組成部分。本文介紹了任務規劃系統的設計構成和基于DPSO的地面站資源調度方法，可實現多衛星、多地面站的自動化任務接收、調度和下發。

［1］SPANGELO S，CUTLER J，GILSON K，et al. Optimization-based scheduling for the single-satellite，multi-ground station communication problem［J］. Computers&Operations Research，2015（57）：1-16.

［2］BAEK S，HAN S，CHO K，et al.Development of a scheduling algorithm and GUI for autonomous satellite missions［J］.Acta Astronautica，2011，68（7-8）：1396-1402.

［3］ZHUANG Y，HUANG H. Time-optimal trajectory planning for underactuated spacecraft using a hybrid particle swarm optimization algorithm［J］. Acta Astronautica，2014，94（2）：690-698.

［4］LI Y，WANG R，LIU Y，et al.Satellite range scheduling with the priority constraint: an improved genetic algorithm using a station ID encoding method［J］.Chinese Journal of Aeronautics，2015，28（3）：789-803.

［5］XHAFA F，BAROLLI A，TAKIZAWA M.Steady state genetic algorithm for ground station scheduling problem［C］//Advanced Information Networking and Applications（AINA），2013 IEEE 27th International Conference on.IEEE，2013：153-160.

［6］BARBULESCU L，WATSON J P，WHITLEY L D，et al.Scheduling space–ground communications for the air force satellite control network［J］.Journal of Scheduling，2004，7（1）：7-34.

［7］FALONE R，CORRAO G.Ground station network scheduling through genetic and deterministic combined algorithm［C］//2018 SpaceOps Conference，2018：2725.

［8］XHAFA F，SUN J，BAROLLI A，et al. Evaluation of genetic algorithms for single ground station scheduling problem［C］//Advanced Information Networking and Applications（AINA），2012 IEEE 26th International Conference on. IEEE，2012：299-306.

［9］ XHAFA F，HERRERO X，BAROLLI A，et al.Evaluation of struggle strategy in genetic algorithms for ground stations scheduling problem［J］. Journal of Computer and System Sciences，2013，79（7）：1086-1100.

［10］ SUN J，XHAFA F. A genetic algorithm for ground station scheduling［C］//Complex，Intelligent and Software Intensive Systems（CISIS），2011 International Conference on.IEEE，2011：138-145.

［11］DAMIANI S，DREIHAHN H，NOLL J，et al.A planning and scheduling system to allocate ESA ground station network services［C］//The Int'l Conference on Automated Planning and Scheduling，2007.

［12］KO H P.Discretized genetic algorithm for satellite constellation and multiple ground antenna scheduling［C］//14th International Conference on Space Operations，2016：2511.

［13］MARINELLI F，NOCELLA S，ROSSI F，et al.A lagrangian heuristic for satellite range scheduling with resource constraints［J］.Computers&Operations Research，2011，38（11）：1572-1583.

［14］LIN W C，LIU C Y，LIAO D Y，et al.Daily imaging scheduling of an earth observation satellite［C］//IEEE International Conference on Systems，Man and Cybernetics，2003.

［15］ZHU K J，LI J F，BAOYIN H X.Satellite scheduling considering maximum observation coverage time and minimum orbital transfer fuel cost［J］.Acta Astronautica，2010，66（1-2）：220-229.

［16］LI J，ZHANG T J，YE G Q.Satellite-ground TT&C united scheduling methods of GNSS constellation based on nodes constraint［C］//China Satellite Navigation Conference（CSNC）2015 Proceedings：Volume I. Springer，Berlin，Heidelberg，2015：55-66.

［17］KUCHEROV B，P?IBYL O.Increasing efficiency of ground stations scheduling for sustainable satellite based services［C］//2018 Smart City Symposium Prague（SCSP）. IEEE，2018：1-6.

［18］郭文忠，陳國龍.離散粒子群優化算法及其應用［M］.北京：清華大學出版社，2012.

［19］趙和鵬.多地面站衛星數據接收任務規劃問題研究［D］.成都：電子科技大學，2013.

［20］張為良.基于改進型遺傳算法衛星地面站資源調度優化研究［D］.成都：國家海洋環境預報中心，2013.

2095－6835（2020）24－0018－04

TN927.21

A

10.15913/j.cnki.kjycx.2020.24.006

王崢（1982—），女，本科畢業于北京聯合大學信息學院，中國人民大學在職研究生在讀，工程師，研究方向為衛星規劃調度。

〔編輯：王霞〕