王崢

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

王崢

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

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

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

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

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

1 問題描述

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

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

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

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

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

資源調(diào)度子系統(tǒng)面向衛(wèi)星數(shù)據(jù)接收計(jì)劃與地面接收資源，根據(jù)業(yè)務(wù)規(guī)則等各項(xiàng)約束條件，完成對(duì)接收任務(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)測(cè)任務(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）求解，可在可接受的求解時(shí)間內(nèi)獲取可行解。

3.1 DPSO簡(jiǎn)介

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

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

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

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

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

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

標(biāo)準(zhǔn)PSO算法的流程如下所示。

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

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

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

步驟4：評(píng)價(jià)整個(gè)種群中所有粒子。

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

步驟6：對(duì)于當(dāng)前種群中評(píng)價(jià)值最優(yōu)的，如果其評(píng)價(jià)值優(yōu)于的評(píng)價(jià)值，則將和的評(píng)價(jià)值更新為該及其評(píng)價(jià)值。

步驟7：如果停止準(zhǔn)則得到滿足，則以當(dāng)前及其評(píng)價(jià)值作為最終結(jié)果，PSO算法終止；否則返回步驟3。由于粒子的候選解表征和更新公式都是針對(duì)連續(xù)變量設(shè)計(jì)的，所以標(biāo)準(zhǔn)PSO算法通常僅用于處理連續(xù)優(yōu)化問題。作為PSO搜索機(jī)制和演化流程在離散優(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è)計(jì)交叉、變異等操作對(duì)粒子更新公式中的各類運(yùn)算進(jìn)行重新定義。我們選擇此類DPSO算法作為地面站資源調(diào)度優(yōu)化算法。

3.2 算法流程

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

算法流程如圖2所示。

圖2 算法流程

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

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

收益為：

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

在衛(wèi)星任務(wù)日益增多、地面站資源相對(duì)有限的情況下，衛(wèi)星地面站任務(wù)規(guī)劃系統(tǒng)解決了衛(wèi)星與地面站數(shù)據(jù)交互任務(wù)的接收和地面站資源調(diào)度問題，是衛(wèi)星地面系統(tǒng)的核心組成部分。本文介紹了任務(wù)規(guī)劃系統(tǒng)的設(shè)計(jì)構(gòu)成和基于DPSO的地面站資源調(diào)度方法，可實(shí)現(xiàn)多衛(wèi)星、多地面站的自動(dòng)化任務(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］郭文忠，陳國(guó)龍.離散粒子群優(yōu)化算法及其應(yīng)用［M］.北京：清華大學(xué)出版社，2012.

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

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

2095－6835（2020）24－0018－04

TN927.21

A

10.15913/j.cnki.kjycx.2020.24.006

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

〔編輯：王霞〕