基于多目标优化的中继卫星重调度方法

2022-06-29 05:06龙运军李恒伟

无线电工程 2022年7期

龙运军，李恒伟，尹谦，郭磊

(1.北京空间信息中继传输技术研究中心，北京 100094；2.中南大学交通运输工程学院，湖南长沙 410075)

0 引言

随着卫星数量增多，航天器之间的数据交流需求越来越大，对中继卫星的需求也变大。中继卫星的运行轨道在地面36 000 km之上，轨道高度高，覆盖面广。3颗中继卫星组成的卫星网络，能全部覆盖300～2 000 km轨道上的卫星，实现数据中继和对卫星的连续跟踪，使得卫星数据传输对地面测控站的依赖减小，节省卫星数据传输的成本。

随着对中继卫星的需求增大，如何合理地调配中继卫星资源，满足用户的需求，成为提高整个系统利用效率的关键。当前，对中继卫星的调度方法研究大多是在特定的理想情况下，对于单目标需求进行优化。

现有中继卫星系统调度研究主要分为对应用模式的研究和对算法的研究。在应用模式方面，Hajghassem[1]对NASA的中继卫星系统在航天网络的应用模式进行了分析。Reddy[2]针对单窗口和单根天线的约束调度问题进行了求解，提出的动态算法能够在约束条件下获得优化结果。Rojanasoonthon[3]针对多时间窗口和多址链路约束调度进行求解，采用了分支定界法来进行最优解的求解。

在算法方面，顾中舜[4]将蚁群算法运用到调度问题中，与经典的遗传算法和模拟退火算法进行比较，发现蚁群算法更适合中继卫星调度问题，无论是时间还是精度都更优。Liu等[5]利用时间窗口的灵活范围和数学特征，提出了一种调度算法，与其他经典算法对比，提高了约11%的任务完成率。He等[6]基于中继卫星动态调度中的多址问题，构建了一种基于随机优化的数学架构，将问题转化为一个天线内嵌多个的形式，并利用了2种算法进行求解。张彦等[7]主要针对新增任务和任务时间变化等动态扰动建立了中继卫星动态调度模型，并提出了动态扩展/删除树搜索算法，以删除任务和调整任务之比作为指导，提高了算法效率，并证明了其能够在实际中运用。

上述研究主要侧重于中继卫星系统静态任务调度。随着中继卫星的运用范围越来越大，各类型用户目标对中继卫星系统资源需求动态性越来越高，而且在未来战争中，中继卫星系统作为重要战略资源是敌人破坏摧毁的目标。面对海量应急中继使用需求或资源受损时，如何快速重新进行资源分配调整计划，成为发挥或保持整个中继卫星系统效能的关键。当前研究对中继卫星的调度方法大多是针对单目标需求进行优化，如最大化任务完成度，对于多目标情况的研究鲜有涉及。

因此，本文针对中继卫星系统接收海量临时申请或者中继资源故障时如何快速进行重调度问题进行研究，以满足最大化任务完成率和最小化动态扰动测度2个互相冲突的需求为优化目标，建立了调度过程中突发新增任务的动态调度的模型，基于NSGA-Ⅱ多目标优化算法，对中继卫星进行动态重调度。

1 中继卫星应用模式

1.1 系统工作原理和流程

中继卫星系统是指将中继卫星发射至地球的静止轨道，并将地面站作为终端，对中低轨道卫星进行大面积覆盖，提供测控通信和数据中继的系统。

中继卫星系统概貌如图1所示，可以将整个中继卫星系统分为3个部分：第1部分是中继卫星；第2部分是用户层，由多种用户航天器构成；第3部分为地面设施，主要包含用户航天器及中继卫星的管理中心和地面网络终端。

图1 中继卫星系统概貌Fig.1 Overview of relay satellite system

由于用户层与地面可见时间较短，需要利用中继卫星进行数据中转，在用户航天器与中继卫星的可见时间窗口内，将需要传给地面的数据信息传给中继卫星。用户航天器管理部门需要根据中继卫星管理部门对外发布的下一周期卫星资源，以及自身的任务需求，向中继卫星的管理部门提交任务申请，中继卫星管理部门对用户需求进行整理，科学合理地分配有限的卫星资源，并生成调度方案。对于突发情况，中继卫星管理部门会及时启用相应的动态调度算法进行调整，保证中继卫星服务的正常运行，并获得动态调度方案。最后，各部门依据最终方案，完成地面站和用户航天器之间的数据传输任务。

1.2 系统应用模式分析

本文的中继卫星系统应用模式采用传统的通用模式，可归纳如下[8-10]：

① 用户管理部门提交的任务申请信息包括其任务的紧急程度、需求的服务时间和窗口等。提交的每一项任务只能所属一个用户航天器，通常对应一个或多个中继卫星服务时间窗口，任务必须一次性完成。

② 在用户申请完毕后，由中继卫星管理部门进行统计，并通过静态调度算法，根据用户需求生成合理的卫星调度方案，依据调度方案完成任务。

③ 对于在中继卫星执行任务过程中可能出现的动态扰动，如紧急新增任务、资源失效等任务变化，导致静态调度方案中部分任务可能无法按原有方案进行执行时，需要紧急启用动态调度算法，进行动态调度，来满足任务需求；失效资源上已安排的任务均作为新增任务申请进行重新分配。

④ 在静态调度方案和动态方案生成完毕后，获得一个新的方案，中继卫星将按新的方案执行任务。同时，中继卫星管理部门需要将任务执行情况下达至各个用户及所对应的地面站。

2 考虑任务扰动的中继卫星重调度模型

中继卫星系统调度问题复杂，涉及变量众多，约束条件繁杂，因此本文在构建模型时做了适当简化，降低求解难度。

2.1 问题假设

为降低问题建模与求解难度，对中继卫星任务调度问题做了简化，做如下基本假设[11-13]：

① 不考虑不同任务间可能存在的相关性；

② 所有任务被执行时必须一次性完成；

③ 用户申请的服务时间窗口为固定的时间窗口，不具备弹性。

2.2 变量符号说明

本文构建的中继卫星重调度模型将要用到的变量定义如表1所示。

表1 符号定义Tab.1 Symbol definition

2.3 模型决策变量和优化目标

2.3.1 决策变量

在本文选定的应用模式下，整个问题实际上就是对用户申请的任务确定6个要素的信息：任务的执行紧急程度、任务执行的最早开始时间和最晚结束时间、任务的执行所需时间、任务能被执行的天线和任务对应用户航天器。故模型的决策变量为xtrj,actstrj和acdtrj。

决策变量xtrj的值只有0或1两种，用来表示任务是否被成功执行，成功其值为1，不成功则为0。决策变量actstrj表示在可见窗口j内，任务t在被资源r执行的开始时间，为一个连续变量。决策变量acdtrj，表示在可见窗口j内，任务t在被资源r执行的实际持续时间，为一个连续变量。

2.3.2 优化目标

在中继卫星重调度模型中，选取最大化任务执行率和最小化动态扰动测度为目标函数。最大化任务完成率是指算法求解时，在满足约束条件的情况下，向任务完成率最大的解靠近。

动态扰动测度(DDM)是指当动态扰度发生后，经过算法产生的动态调度方案与之前静态调度的方案的差异程度[14]：

ψ(s0,snew)=λdelndel+λcnc，

(1)

式中，s0表示静态调度的方案；snew表示动态调度后产生的新方案；ndel表示从静态至动态调度删除的任务与除新增任务外另增加的任务数量之和；nc表示从静态调度到动态调度的任务调整数量(比如任务从第1个卫星调整到第2个卫星执行)数量；λ表示任务的权重。重调度的目标函数为：

(2)

minf2=λdelndel+λcnc。

(3)

本文建立的中继卫星重调度模型中，将最大化任务完成率作为本文的优化目标，即希望通过算法求解时，在满足约束条件的情况下，向任务完成率最大的解靠近。

2.4 约束条件

在中继卫星系统调度问题中，主要涉及两方面约束：一方面为资源约束；另一方面为任务需求约束。

2.4.1 资源约束

资源约束包括可见时间窗口约束和资源的使用约束。

① 可见时间窗口约束

中继卫星与用户航天器之间可以传输数据的时间称为可见时间窗口，要求在任务被执行的过程中，必须与其所属的用户航天器对应的与中继卫星的可见时间窗口匹配。由此可得约束条件C1,C2：

(4)

(5)

C1表示任务执行的开始时间不能小于其所属的用户航天器与中继卫星的可见时间窗口的开始时间。C2表示任务执行的结束时间不能大于其所属的用户航天器与中继卫星的可见时间窗口的结束时间。

② 天线资源约束

在中继卫星重调度问题中，一个天线资源在任意时刻只能执行一个任务，得到约束C3：

C3:(adjust+Dmr+rec)∩(adjust+Dnr+rec)=φ,

∀t∈T,r∈R,m∈T。

(6)

2.4.2 任务需求约束

任务方面的约束包括任务执行时间约束和任务执行约束。

① 任务服务时长约束

在中继卫星重调度问题中，任务在被调度时，分配的任务时长必须等于任务需求的服务时长，可得约束C4：

(7)

② 任务时间窗口约束

与可见时间窗口相似，任务不是时时都能够被执行，每个任务都有一个能被执行的窗口，称为服务时间窗口，因此任务的执行时间都应在任务服务时间窗口内。可得约束C5,C6：

(8)

(9)

C5表示任务的执行时刻应迟于其对应的服务时间窗口的开始时间。C6表示任务的执行结束时刻应早于其对应的服务时间窗口的结束时刻。

③ 任务执行约束

在中继卫星重调度问题中，中继卫星执行的任务只能被一个天线选择执行，同时也只能选择一个可见时间窗口被执行，可得约束C7,C8：

(10)

(11)

2.5 重调度数学模型

本文所构建的中继卫星多目标重调度模型以任务完成率最大化和动态扰动测度最小化为目标，以资源和任务需求为约束，构建的具体数学模型如下：

minf2=λdelndel+λcnc，

3 基于多目标优化的重调度算法

本文研究的内容为多目标优化下的中继卫星的重调度。基于多目标优化，选取NSGA-Ⅱ这一多目标优化领域内的流行算法作为本文动态调度问题的优化算法，探究其对中继卫星动态调度的优化效果。

3.1 算法简介

NSGA-Ⅱ作为优化算法的一种，基于遗传算法改进而来。遗传算法作为经典的智能优化算法，是以达尔文生物学中“优胜劣汰”为背景，以自然选择和遗传作为原理，模拟生物进化的一种算法。NSGA-Ⅱ算法继承了遗传算法优胜劣汰的思想，同时引进了Pareto支配关系和非支配排序、种群拥挤度和精英保留策略等思想[15]。Pareto支配关系和非支配排序主要是为多目标优化服务，种群拥挤度的提出是为了得到最优解在空间中形成均匀的分布，精英保留策略则是为了更方便地选择出更为优秀的个体，遗传至下一代。

3.2 流程设计

① 生成静态调度方案

首先，根据用户提交的任务信息和中继卫星资源信息，利用静态调度算法生成初始的静态调度方案。主要是通过任务的服务窗口和中继卫星与用户航天器的可见时间窗口的交集生成任务的可用时间，运用算法进行初步的任务调度，得到静态调度方案，方便后续动态扰度测定计算。

② 对第一代种群进行非支配排序

静态调度后进行动态调度初始方案的生成。在动态调度中，要保证新增任务必须执行，然后考虑执行新增任务后，资源和任务的匹配生成动态调度的初始解，即整个进化算法的初始种群。然后计算种群中每个个体的目标函数值，本文考虑的多目标为最大化任务完成率和最小化动态扰动测度，依据多目标函数值，对每个个体进行非支配排序。

③ 选择、交叉、变异

选择是指从父代中选出优秀的个体，进行交配产生下一代。在遗传算法中选择的方式有很多，如轮盘赌和锦标赛选择法等。NSGA-Ⅱ中运用的锦标赛选择法，即从种群N个个体中，选出k个个体，一般取N的一半，然后根据个体的适应度(Pareto等级和拥挤度)，将表现最好的个体放入交配集。

交叉之前进行编码，将每个任务和执行任务的卫星都用二进制的方式表达出来。染色体编码示意如图2所示。

将所有的任务编码完毕后，一个任务及其执行情况将会对应一段同样长度的编码，然后进行交叉，产生新的2段不同的编码，本文选用两点交叉法，实现过程不复杂，也有较好的随机性。两点交叉法示意如图3所示。

图3 两点交叉法示意Fig.3 Schematic diagram of two-point crossover method

④ 精英选择

将输出的子代与父代合并为同一个种群，计算种群中每个个体的目标函数值，即最大化任务完成率和最小化动态扰动测度，依据多目标函数值，对每个个体进行非支配排序，然后对恰好无法全部放入种群的那层Pareto层级个体进行拥挤度计算，保留拥挤度较大的个体进入下一代。精英选择示意如图4所示。

图4 精英选择示意Fig.4 Schematic diagram of elite selection

⑤ 算法结束

将上面的4个步骤循环一次，代表整个种群进化了一次，持续循环直到满足输出条件，得到最后的优化结果，即重调度的最终结果。

4 仿真实验和结果分析

4.1 任务需求信息

① 任务编号

在实验中，为了方便，任务直接从1开始编号。

② 任务对应航天器

任务实际能够被执行的时间，实际上为任务对应航天器和中继卫星的可见时间窗口和任务的执行时间窗口的交集。每一个任务相应地对应一个航天器，在本文的实验中，采用均匀生成随机数的方法，将任务与航天器一一匹配。

ust=ceil(λ*us)，

(12)

式中，ust表示任务的航天器编号；ceil表示向上取整；λ表示(0，1)的随机数；us表示每个实验中用户航天器的数量。

③ 任务服务时间

由用户提交任务能够被执行的开始时间和结束时间。在本文的仿真实验中，通过随机数和正态分布来生成。

stst=λ*86 400，

(13)

stet=stst+abs(normrnd(mean,std))，

(14)

式中，stst表示开始时间；stet表示结束时间；mean表示整个服务时间正态分布的均值；std表示整个服务时间正态分布的标准差；abs表示取绝对值。

④ 任务服务时长

用户根据其需求对任务进行评估后提交的信息。在本文的实验中，根据随机数和正态分布来生成。任务服务时长为：

dt=abs(normrnd(mean,std))。

(15)

部分任务数据信息如表2所示。

表2 任务数据信息表Tab.2 Task data information

4.2 仿真实验参数设定

在本文的实验中，选择86 400 s作为调度周期。然后根据不同的变量构建实验，观察不同变量的变化对整个动态调度优化效果的影响。最大参数规模可以达到500个任务申请、3颗中继卫星、10个航天器。本次实验的环境参数如表3所示。

表3 环境参数Tab.3 Environmental parameters

4.3 优化结果展示与算法性能分析

为研究NSGA-Ⅱ算法对中继卫星动态调度的优化效果以及不同中继卫星数量、用户航天器数量和新增任务数量对优化效果的影响，本文选择300个任务规模，做新增任务和用户航天器数量变化实验，在500个任务规模做中继卫星数量变化实验，并在相同条件下选取了经典的多目标算法SPEA-Ⅱ算法进行优化效果对比。

在本文中选用超体积指标(HV)做算法性能评价[16]，在双目标优化问题中，HV的运算方法为获得的非支配解集的每个个体与参照点(最大值个体)在空间中围成的矩形的面积之和，HV值越大，说明算法的综合性能越好。

(16)

4.3.1 300个任务申请

在300个任务规模时，将中继卫星数量固定为2，考虑此基础上的优化效果以及不同新增任务数量和不同用户航天器数量对优化效果的影响。

① 新增任务数量对算法的影响

不同新增任务优化效果对比如图5所示。

(a) 2个新增任务

(b) 4个新增任务

(d) 8个新增任务

(e) 10个新增任务

(f) 12个新增任务

(g) 14个新增任务

(h) 16个新增任务

(i) 18个新增任务

(j) 20个新增任务图5 优化效果对比Fig.5 Optimization effect comparison

不同新增任务优化数据对比如表4所示。

表4 优化数据对比Tab.4 Optimized data comparison

图6展现了在300个任务、2颗中继卫星、10个用户航天器的条件下，不同新增任务的优化效果，输出的为在同样迭代次数下SPEA-Ⅱ和NSGA-Ⅱ算法优化后种群的Pareto最优值。

图6 HV值对比Fig.6 HV value comparison

由图6可以看出，在新增任务数量不同时，NSGA-Ⅱ算法输出的Pareto最优解在空间上分布的均匀性、收敛性和广泛性相较SPEA-Ⅱ算法都更加优秀。

对比图5可以看出，HV值相较SPEA-Ⅱ要更大，说明NSGA-Ⅱ算法在中继卫星动态调度优化方面性能更好，能优化出收敛性和多样性更佳的非支配个体。

② 对算法的影响

不同用户航天器数量优化效果对比如图7所示。

(a) 2个用户航天器

(b) 4个用户航天器

(d) 8个用户航天器

(e) 10个用户航天器

(f) 12个用户航天器

(g) 14个用户航天器图7 优化效果对比Fig.7 Optimization effect comparison

不同用户航天器数量优化数据对比如表5所示。

表5 优化数据对比Tab.5 Optimized data comparison

图8展示了在300个任务、2颗中继卫星、10个新增任务的情况下，不同用户航天器数量对优化效果的影响。

由图8可以看出，在300个任务条件下，仅用2个用户航天器承载任务会导致任务的完成率减少，这是由于任务的服务时间和航天器与卫星的可见时间匹配随机概率减少。在不同的用户航天器情况下，NSGA-Ⅱ算法展现了较强的优化性能，得到的Pareto最优解适应性、均匀性和收敛性都较好。

图8 HV值对比Fig.8 HV value comparison

4.3.2 500个任务申请

500个任务时，将用户航天器数量固定为10个，考虑此基础上的优化效果及不同中继卫星数量对优化效果的影响。500个任务规模也和300个形成对比，展现不同任务数量时，对优化结果的影响，优化效果对比如图9所示，优化数据对比如表6所示。

(a) 2颗中继卫星

(b) 3颗中继卫星

表6 优化数据对比Tab.6 Optimized data comparison

图10展示了在500个任务、10个用户航天器、10个新增任务的动态扰动环境下，变化中继卫星数量，对算法优化效果的影响。

图10 HV值对比Fig.10 HV value comparison

随着资源数量的增加，任务完成率也随之增加，且NSGA-Ⅱ算法的优化结果分布更均匀，种群多样性更高，同时NSGA-Ⅱ算法的性能，即HV值，要优于SPEA-Ⅱ算法。

5 结束语

在中继卫星单址天线调度问题基础上，考虑调度需求多样性，构建了多目标函数的中继卫星重调度模型，在生成初始调度方案后，运用NSGA-Ⅱ算法对初始调度方案进行优化。仿真实验中，本文对比了在实验参数，如任务规模和资源数量等变化的情况下，NSGA-Ⅱ算法的优化情况。其总能优化得到一个收敛性、均匀性和广泛性较好的Pareto最优解。在对比SPEA-Ⅱ这一经典多目标算法时，NSGA-Ⅱ展现了更强的适用性，基于多目标优化的NSGA-Ⅱ算法输出的Pareto最优解，为调度方案提供了多样化的选择，为中继卫星管理部门和用户建立了一个较佳的选择空间。