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

王崢

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

王崢

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

衛(wèi)星地面站是衛(wèi)星通信系統(tǒng)的重要組成部分，主要作用是上注指令控制衛(wèi)星，并接收和處理衛(wèi)星發(fā)回的觀測(cè)數(shù)據(jù)。近年來(lái)衛(wèi)星任務(wù)數(shù)量劇增，地面站資源相對(duì)不足，資源使用沖突日益明顯。為了提高地面站資源使用效率，針對(duì)多衛(wèi)星、多地面站的測(cè)控類(lèi)任務(wù)和數(shù)傳接收任務(wù)建立了任務(wù)規(guī)劃系統(tǒng)。具體流程為，首先，計(jì)劃接收子系統(tǒng)收到任務(wù)需求后對(duì)任務(wù)進(jìn)行分類(lèi)和預(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ī)劃過(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í)際接收過(guò)程中還有很多因素。

1 問(wèn)題描述

衛(wèi)星與地面站的數(shù)據(jù)交互任務(wù)分為測(cè)控任務(wù)和數(shù)據(jù)接收兩類(lèi)任務(wù)。衛(wèi)星過(guò)境地面站接收范圍時(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ì)同一地面資源來(lái)說(shuō)，可同時(shí)執(zhí)行同一衛(wèi)星的測(cè)控和數(shù)據(jù)接收兩類(lèi)任務(wù)，但不能同時(shí)執(zhí)行兩個(gè)以上衛(wèi)星的任務(wù)。任務(wù)規(guī)劃的目標(biāo)是確定執(zhí)行各個(gè)任務(wù)的地面資源，盡量多地執(zhí)行數(shù)據(jù)交互任務(wù)，提高資源利用率。同時(shí)考慮到資源性能、用戶(hù)習(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)外各類(lè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)介

通過(guò)模仿鳥(niǎo)群覓食時(shí)所呈現(xiàn)的群體智能提出了粒子群算法（PSO）。具體的，鳥(niǎo)群中不同個(gè)體之間會(huì)交流和共享有關(guān)食物方位的信息，每個(gè)個(gè)體的覓食路徑都是在其自身判斷和其他同伴覓食經(jīng)驗(yàn)的共同影響下形成的，個(gè)體間合作與競(jìng)爭(zhēng)等社會(huì)行為同時(shí)存在，使整個(gè)種群能夠更加“智能”地獲得食物。因此，PSO是一種基于群體智能的元啟發(fā)式算法。PSO算法中的粒子代表問(wèn)題候選解且大量粒子以種群的形式共存于問(wèn)題解空間。就如同鳥(niǎo)群在空中覓食一樣，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è)粒子而言，它能夠記住其所落入過(guò)的最佳位置（記為），這代表粒子自身的搜尋經(jīng)驗(yàn)；對(duì)于種群而言，它能夠記住全部粒子所落入過(guò)的一個(gè)最佳位置（記為），這代表整個(gè)群體的搜尋經(jīng)驗(yàn)。在粒子間合作與競(jìng)爭(zhēng)共存的氛圍下，PSO算法實(shí)現(xiàn)了全局搜索廣泛性和局部搜索深入性的良好平衡。

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

可見(jiàn)，粒子會(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)，從而逐步接近甚至獲得問(wèn)題的全局最優(yōu)解。上述更新過(guò)程會(huì)不斷重復(fù)直至用戶(hù)為PSO算法設(shè)定的停止準(zhǔn)則得到滿足。

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

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

步驟2：評(píng)價(jià)每個(gè)粒子，即計(jì)算其所代表的問(wèn)題候選解的目標(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)化問(wèn)題。作為PSO搜索機(jī)制和演化流程在離散優(yōu)化領(lǐng)域的發(fā)展成果，DPSO保持PSO算法性能優(yōu)良的全局尋優(yōu)能力，從而能夠高效解決離散優(yōu)化問(wèn)題。其中，一類(lèi)通過(guò)重新定義更新操作構(gòu)造出的DPSO算法為PSO尋優(yōu)思想在離散優(yōu)化領(lǐng)域的應(yīng)用提供了有效思路，并已在許多組合優(yōu)化問(wèn)題的求解中取得良好效果。該類(lèi)DPSO算法[102，103]規(guī)定粒子的位置和速度均為離散編碼，設(shè)計(jì)交叉、變異等操作對(duì)粒子更新公式中的各類(lèi)運(yùn)算進(jìn)行重新定義。我們選擇此類(lèi)DPSO算法作為地面站資源調(diào)度優(yōu)化算法。

3.2 算法流程

首先將所有任務(wù)集合按執(zhí)行時(shí)間和地面站分為多個(gè)子集，對(duì)各個(gè)子集分別進(jìn)行資源調(diào)度，將整體問(wèn)題分解為多個(gè)子問(wèn)題，減小了問(wèn)題規(guī)模。對(duì)各個(gè)子集進(jìn)行預(yù)處理，將測(cè)控和數(shù)傳任務(wù)分組，將同時(shí)進(jìn)行的不同類(lèi)型任務(wù)分為一組，然后對(duì)預(yù)處理后的各個(gè)子問(wèn)題分別采用離散粒子群（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)星名、過(guò)境地面站、任務(wù)開(kāi)始時(shí)間、任務(wù)結(jié)束時(shí)間、軌道號(hào)、任務(wù)編號(hào)、任務(wù)優(yōu)先級(jí)、任務(wù)類(lèi)型（測(cè)運(yùn)控或數(shù)傳任務(wù)）、接收數(shù)據(jù)通道、接收任務(wù)作業(yè)方式、接收數(shù)據(jù)各通道碼速率、傳感器、是否主接收任務(wù)、任務(wù)分組號(hào)、是否需要備份接收任務(wù)等。其次獲取資源信息，包括地面站名稱(chēng)、各站天線資源、記錄器資源等。通過(guò)衛(wèi)星與地面站資源的使用約束，計(jì)算各個(gè)任務(wù)的資源約束，包括資源是否可用以及使用優(yōu)先級(jí)等。同時(shí)，根據(jù)任務(wù)時(shí)間計(jì)算該任務(wù)時(shí)段是否可使用該資源。然后根據(jù)任務(wù)開(kāi)始時(shí)間按先后順序排序，按衛(wèi)星名稱(chēng)分組。根據(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èn)題，是衛(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ī)劃問(wèn)題研究［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)度。

〔編輯：王霞〕