基于离散粒子群算法的卫星任务规划系统设计

赵超

中国电子科技集团公司第五十四研究所，河北，石家庄，050000

0 引言

对地观测卫星是目前国际上发射数量最多，且极具代表性和应用范围最广的卫星类型。自1962年诞生空间遥感技术至今，据统计全球已发射对地观测卫星500多颗。在几十年来的发展中，我国卫星对地观测事业获得了长足发展，随着成像任务需求的不断增加，任务类型愈加多样化复杂化，再加上对地观测卫星数量的增加，这些都很大程度上增加了卫星任务规划的复杂度。因此有必要对卫星任务进行综合规划，建立卫星任务规划系统[1]。对卫星资源科学规划合理调度，实现卫星任务优化配置，这是目前迫切需要解决的重要问题。结合以往的文献分析，卫星任务规划问题属于NP-hard问题，求解空间会随着卫星任务与资源数量的增加急剧增大，对于大规模任务规划问题，无法在合理时间内最优求解[2]。对此，理论研究界认为智能算法可以评价函数对解优劣的判定结果，在目标函数与约束要求方面比较宽松，与传统算法相比智能算法效率更高，每一个群个体的能力都十分简单，并且执行时间也相对较短，实现了较强的鲁棒性[3]。本文研究的粒子群算法就作为其中一类，因其卓有成效的最优解求解问题被广泛应用于各领域，在此算法基础上设计卫星任务规划系统，结合仿真实验证明本次系统的设计简单灵活，经过优化之后的算法可以有效求解问题。

1 PSO算法原理

根据资源的具体分配特点，定义第i个粒子的当前位置为：

当前历史p为当前历史最优位置：

当前群体最优解标识为：

定义粒子群方程式如下：

由此可见粒子会因为自身目前所处位置和具体速度，以及历史最佳所在位形成的方位关系确定新速度。

2 DPSO资源调度优化算法

根据上述对PSO算法原理的分析，提出DPSO资源调度优化算法，通过将全部任务的集合根据任务的具体时间和接收资源划分为多个子集，在资源调度后面临的整个问题分解为多个子问题，这样预处理子集后再进行测控任务分组和DPSO算法优化，如图1所示为本次优化DPSO的算法流程图。

图1 算法流程图

2.1 确定适应度函数

适应度函数受以下四个因素的影响：（1）观测任务的优先级程度，优先级越高越好；（2）完成的观测任务的数量，数量越多越好；（3）完成观测任务所用的接收时间间隔，间隔越小越好；（4）同时完成观测任务所用的接收资源数量，接收资源数量越少越好。

具体收益公式如下：

2.2 求解步骤

（1）预处理。首先要确定完成本次任务的基础信息，有卫星名、观测任务的开始结束时间、任务优先级、记录速率、地面站名称、接收开始结束时间、回放速率等。离散粒子群类似于基本粒子群，粒子目前的具体状态、粒子的历史飞行最优位置记录、粒子群的最优位置历史记录这三个因素都会影响更新粒子的所在位。在粒子群具体资源合理分配方面，粒子飞行速度根据粒子内部的置换操作和粒子间的替换操作表示，在粒子的“惯性”操作状态下，可以对粒子内部结构进行调整，获得粒子更新所在位。计算置换后粒子的适应度结果，如果结果与最优值更加接近，这个置换过程即代表优势置换，否则是劣势置换，这就需要对i、j根据一定概率进行置换[4]。

（2）优化任务安排。在离散粒子群的粒子拥有“自我认知”，粒子可以依据历史最优飞行记录调整自身所在位，在粒子“惯性”操作的基础上执行，叠加至粒子“惯性”操作之上，可以两粒子间替换操作，获得替换区间，并对此区间内最有粒子“自我认知”的部分内容进行替换，其中学习因子使粒子具有自我总结、向历史最优学习的能力。

（3）任务排序计算适应值。判断替换是否满足性能约束条件，如果不满足需要设置循环j=j-1直至满足约束，或者i＜j；如果替换满足约束条件，计算替换后粒子的适应度，如果此适应度远远大于目前适应度，则作为优势替换，否则作为劣势替换。粒子在整个粒子群的最优历史记录，实现了粒子自身位置调整，此操作在上一步的基础上完成。

3 构建卫星任务规划系统

3.1 系统架构

卫星任务规划系统在设计中需要考虑多方因素，包括卫星目标可见性、卫星载荷使用规则、卫星地面接收可见性、任务冲突、数据传输能力等。尤其近年来随着不断提升的卫星灵巧度，给目标观测提供了诸多可选择的机会，所以面对更复杂化的卫星任务规划需求，应当考虑多方因素。对卫星运行轨迹预报后，根据所获取的特定目标，对于可用时间窗口和卫星，获取卫星任务时间窗口，建立任务规划模型，选择数据传输任务与目标任务，具体安排任务时间从而消除冲突。如图2所示为本次基于离散粒子群算法设计的卫星任务规划系统架构图，主要包括以下三个子系统。

图2 卫星任务规划系统架构图

任务预处理环节：主要负责面向获取的卫星观测任务和数传接收窗口相关信息，对所接收的信息逐一验证之后，依据具体规则和标准来判断计划可行性，对无法安排的任务以及无法使用的接收资源直接舍弃，如在最后一个接收后面的观测任务、在最早观测任务前的接收资源、可利用时间过短的接收资源。

任务规划环节：任务规划环节是核心环节，依据业务规则和有关约束条件，对观测任务进行数传窗口资源分配，随机初始化种群，描述最优目标函数，迭代收敛至满足终止条件后优化形成合理的卫星任务规划方案。

计划生成环节：依据任务规划方案进行解译，最终生成卫星可执行的观测和数传动作，同时完成接收任务时间的确定，统筹协调卫星和地面站资源完成任务安排。

3.2 任务规划建模

根据卫星任务优化方向构建对应的优化目标函数，在设计卫星任务规划系统时，一般情况下会选择在满足卫星固存容量、卫星能源、执行任务时间间隔等约束条件下，获得最大化任务完成收益，包括尽可能多地安排任务，同时保证安排的数传窗口尽可能靠前，公式如下：

4 模拟仿真

对本文基于离散粒子群算法的卫星任务规划系统进行仿真算例分析，将离散粒子群算法对比穷举算法，验证多星任务规划中应用此系统的离散粒子群算法能力。对于对地观测卫星任务规划领域中，验证没有标准的数据集，运用STK工具包仿真生成模拟卫星及对应的地面站，与卫星对地观测的任务特点相结合，对一定时间窗口内进行任务场景匹配，模拟生成对应的观测任务和数传窗口，随机为任务赋值对应的优先级，每个观测目标均为正整数任务优先级，利用卫星模拟软件仿真生成卫星任务[6-7]。设定本次模拟卫星对地观测任务数目，分别为20、30、35、40、50、60、80、100，对应数传窗口数量为10、10、25、40、40、40、50、60。分别采用穷举算法与离散粒子群算法，进行同组数据求解，设定离散粒子群共计500个粒子数，进行一万次迭代寻求最优解，设置0.9为惯性权重，3个置换门限值设为0.0005，得到仿真模拟结果如表1所示。

根据表1模拟仿真处理结果，可以发现随着卫星任务数量的不断增加，应用本文设计的基于离散粒子群算法的系统完成任务的具体时间几乎表现为线性增长，而穷举法耗时则呈现指数增长。由于面对多星任务规划时，应当从根源认识这一约束规划问题，而约束规划作为NP问题，在面对较大问题规模的情况下，使用穷举算法的处理效率就不高。离散粒子群算法的具体执行时间也会随着问题规模的增加而增长，这也在一定程度上证明了本次设计的卫星任务规划系统的良好拓展性。同时，由于离散粒子群算法利用不同粒子迭代过程中本身具备良好的并行可操作性，可以对大规模多星任务规划问题进行有效处理。

5 结语

综上所述，本文基于离散粒子群算法，设计了包括任务预处理、任务规划、计划生成三大功能的卫星任务规划系统。根据构建的任务规划模型，运用粒子群算法优化模拟求解，通过模拟结果发现，离散粒子群算法可以对大规模多星任务规划问题进行有效处理，特别是在任务及数传窗口数量较大的情况下，能够快速收敛，从而有效解决大规模的卫星任务规划问题。