基于离散粒子群算法的卫星地面站任务规划系统

王峥

基于离散粒子群算法的卫星地面站任务规划系统

王峥

（中国人民大学 信息学院，北京 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—），女，本科毕业于北京联合大学信息学院，中国人民大学在职研究生在读，工程师，研究方向为卫星规划调度。

〔编辑：王霞〕