基于離散粒子群算法的衛(wèi)星地面站任務(wù)規(guī)劃系統(tǒng)

王崢

基于離散粒子群算法的衛(wèi)星地面站任務(wù)規(guī)劃系統(tǒng)

王崢

（中國人民大學(xué) 信息學(xué)院，北京 100872）

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

任務(wù)規(guī)劃；衛(wèi)星地面站資源調(diào)度；離散粒子群算法；數(shù)據(jù)交互

中國遙感衛(wèi)星地面站有多個衛(wèi)星地面站組成的地面站網(wǎng)，設(shè)備多，任務(wù)量大，任務(wù)規(guī)劃系統(tǒng)的建立是實現(xiàn)自動化、減少人工成本、提高生產(chǎn)效率的重要手段。同時需要建立與實際需求匹配的資源優(yōu)化模型和可行的模型求解算法。

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

1 問題描述

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

2 任務(wù)規(guī)劃系統(tǒng)組成

任務(wù)規(guī)劃系統(tǒng)如圖1所示。根據(jù)衛(wèi)星數(shù)據(jù)交互任務(wù)的處理流程，任務(wù)規(guī)劃系統(tǒng)可分為三個部分：計劃接收子系統(tǒng)、資源調(diào)度子系統(tǒng)、任務(wù)資源下發(fā)子系統(tǒng)。

圖1 任務(wù)規(guī)劃系統(tǒng)框圖

計劃接收子系統(tǒng)面向衛(wèi)星接收計劃的獲取，驗證接收計劃文件，根據(jù)規(guī)則判斷計劃的可行性，針對接收計劃間沖突情況給出合理建議，對計劃的完成情況進行實時監(jiān)測、上報，對衛(wèi)星接收計劃和數(shù)據(jù)文件信息進行管理。

資源調(diào)度子系統(tǒng)面向衛(wèi)星數(shù)據(jù)接收計劃與地面接收資源，根據(jù)業(yè)務(wù)規(guī)則等各項約束條件，完成對接收任務(wù)所需的各數(shù)據(jù)接收站接收設(shè)備、記錄設(shè)備、光纖傳輸鏈路資源的分配決策，快速形成合理優(yōu)化的接收任務(wù)規(guī)劃方案。

任務(wù)資源下發(fā)子系統(tǒng)具備信息交換能力，具備境內(nèi)外接收站的衛(wèi)星數(shù)據(jù)接收記錄任務(wù)、數(shù)據(jù)傳輸任務(wù)、數(shù)據(jù)質(zhì)量監(jiān)測任務(wù)和原始數(shù)據(jù)監(jiān)視顯示任務(wù)的信息交互能力，保障系統(tǒng)內(nèi)外各類數(shù)據(jù)交換暢通。

3 基于DPSO資源調(diào)度優(yōu)化方法

衛(wèi)星與地面站的數(shù)據(jù)交互任務(wù)數(shù)量多，約束條件復(fù)雜，導(dǎo)致模型規(guī)模大，變量多，求解困難。考慮采用智能算法（DPSO）求解，可在可接受的求解時間內(nèi)獲取可行解。

3.1 DPSO簡介

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

在PSO算法中，每個粒子都有位置和速度這兩種屬性，ik和ik分別表示維搜索空間中第代種群的第個粒子的位置和速度，其中位置表征問題候選解。ik=[i，1k，i，2k，…，i，Dk]和k=[1k，2k，…，Dk]分別表示截止到第代種群時，第個粒子和整個種群落入過的具有最優(yōu)目標函數(shù)值的最佳位置。設(shè)種群內(nèi)粒子總數(shù)為NP種群最大進化代數(shù)為，則標準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）中：慣性權(quán)重用于控制當前速度對更新后速度的影響大小；1和2為加速系數(shù)，分別反映粒子自身以及整個種群的飛行經(jīng)驗對粒子更新后速度指導(dǎo)作用的強弱；1和2是兩個取值在[0，1]間均勻分布且相互獨立的隨機數(shù)。

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

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

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

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

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

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

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

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

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

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

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

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

3.2 算法流程

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

算法流程如圖2所示。

圖2 算法流程

3.3 算法適應(yīng)度函數(shù)和求解步驟

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

收益為：

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

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

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

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

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

步驟5：根據(jù)適應(yīng)度函數(shù)，計算各粒子適應(yīng)值，即天線使用沖突的任務(wù)數(shù)量。

步驟6：找出個體和群體最優(yōu)值以及最優(yōu)位置。

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

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

步驟9：結(jié)束。輸出計算結(jié)果。

4 結(jié)論

在衛(wèi)星任務(wù)日益增多、地面站資源相對有限的情況下，衛(wèi)星地面站任務(wù)規(guī)劃系統(tǒng)解決了衛(wèi)星與地面站數(shù)據(jù)交互任務(wù)的接收和地面站資源調(diào)度問題，是衛(wèi)星地面系統(tǒng)的核心組成部分。本文介紹了任務(wù)規(guī)劃系統(tǒng)的設(shè)計構(gòu)成和基于DPSO的地面站資源調(diào)度方法，可實現(xiàn)多衛(wèi)星、多地面站的自動化任務(wù)接收、調(diào)度和下發(fā)。

［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］郭文忠，陳國龍.離散粒子群優(yōu)化算法及其應(yīng)用［M］.北京：清華大學(xué)出版社，2012.

［19］趙和鵬.多地面站衛(wèi)星數(shù)據(jù)接收任務(wù)規(guī)劃問題研究［D］.成都：電子科技大學(xué)，2013.

［20］張為良.基于改進型遺傳算法衛(wèi)星地面站資源調(diào)度優(yōu)化研究［D］.成都：國家海洋環(huán)境預(yù)報中心，2013.

2095－6835（2020）24－0018－04

TN927.21

A

10.15913/j.cnki.kjycx.2020.24.006

王崢（1982—），女，本科畢業(yè)于北京聯(lián)合大學(xué)信息學(xué)院，中國人民大學(xué)在職研究生在讀，工程師，研究方向為衛(wèi)星規(guī)劃調(diào)度。

〔編輯：王霞〕