考虑多滑动窗口的中继卫星调度模型及启发式算法

何敏藩， 朱燕麒， 贾学卿

(1.佛山科学技术学院 数学与大数据学院， 广东 佛山 528000； 2.北京市遥感信息研究所， 北京 100085； 3.国防科技大学 电子科学学院，湖南 长沙 410073)

0 引言

跟踪与数据中继卫星(tracking and data relay satellite, TDRS)，简称为中继卫星[1-2]，主要为中、低轨道的航天器提供数据中继、连续跟踪与轨道测控服务.中继卫星的出现是20世纪航天测控领域的重大突破，其“天基”设计思想从根本上解决了对中、低轨道航天器测控通信的高覆盖率问题，减少了地面测控站的数量，在航天活动中发挥着越来越重要的作用，也成为未来航天器发展趋势[3-5].我国的中继卫星系统主要承担载人航天保障、登月计划保障、航天器数据传输以及航天器测控任务，其中前两项属于频率较低的重大任务，后两项为常规任务.对于载人航天保障等重大任务而言，其执行优先级较高，中继卫星系统将在任务全过程对其优先提供服务，因此在中继卫星应用模式及调度方法方面不需要较为复杂的机制.随着我国国家利益的扩展以及航天器数量的增加，需要执行大量海外任务.航天器获取的数据主要通过中继卫星系统实现实时传输和利用.这使得航天器数据传输与测控的任务需求与日俱增，用户规模庞大，调度方案的质量将直接影响任务完成的效果以及中继卫星的使用效能，这对中继卫星资源的合理调度提出了更高的要求[6].需要进一步深入考虑中继卫星应用与用户需求的实际情况，研究符合实际的中继卫星调度模型以及快速稳定的求解算法.

卫星调度问题是一个具有实践和科学意义的优化问题，国内外取得了不少的研究成果[7-9].开彩红等[10]针对中继卫星单址天线调度问题，建立了调度约束规划模型，提出基于人工蜂群(ABC)算法的中继卫星任务调度算法，并通过仿真数据分析验证了算法的合理性和有效性.王志淋等[11]借鉴时间窗约束的车辆路径问题理论，提出天线准备时间变长的规划优化问题(LOPVAPT)模型，通过优化天线的扫描路径，实现天线准备时间的动态最优取值，并基于蚁群算法进行了实验验证.林鹏等[12]面向空间网络中任务发生的时间和空间随机性，建立中继卫星系统服务模型，并提出了一种动态的空间任务调度方法.利用空间网络拓扑动态变化的特点，结合空间任务的多优先级和容忍延时特性，提出一种基于种群联合进化的资源分配算法.顾中舜[13]研究了中继卫星动态调度问题，建立了中继卫星动态调度框架，分析了中继卫星工作的约束条件，提出了任务完成评价指标，创造性地提出完成任务的收益与完成任务时间窗口的选择有关，考虑了任务的具体执行时间在窗口中的分布情况.陈理江等[14]研究了基于时间灵活度的中继卫星调度算法，在已有的调度方案基础上，通过调度插空和任务交换优化原调度方案，该算法机制比较简单，且可以动态调整.

张彦等[15]在TDRS动态调度问题求解算法研究中，设计了动态扩展/删除树搜索算法(dynamic extended /delete tree search，DEDTS)，该算法在搜索过程中利用基于动态扰动测度的目标值控制删除任务和调整任务的时机，从而更好地体现实际应用的需求.智能优化算法在求解复杂优化问题上表现出优异性能[16]，近年来，蚁群算法(ant colony optimization, ACO)、遗传算法(genetic algorithm, GA)、模拟退火(simulated annealing, SA)等智能优化算法在求解组合优化问题方面显示了较强的能力[17-19],在中继卫星调度问题中也得到了一定的应用[20].但是从文献的仿真实验来看，对于中继卫星调度问题，智能优化算法只适用于中、小规模场景的求解，面对多中继卫星多用户航天器大规模任务申请时会出现“维数灾”问题，导致智能优化算法性能迅速下降，求解时间也将大大超出实际调度工作要求.

顾中舜[13]利用蚁群算法求解中继卫星初始调度模型，并与基于遗传算法和模拟退火算法的计算结果进行了比较，结果表明，蚁群算法在求解时间和求解精度上都明显优于另外两种算法.方炎申等[21]采用基于有效的基因路径的遗传算法来实现中继卫星单址链路任务调度,分析了调度问题中时间窗口的特性，对基本遗传算法进行改进，引入有效基因概念，应用结果表明，采用基于有效基因路径表示的遗传算法求解是合理的.顾中舜[13]比较了蚁群算法、遗传算法和模拟退火算法求解中继卫星初始调度模型的计算结果，最后得出由于模拟退火算法有限度地接受劣解，可以跳出局部最优解,但有计算量过大和控制参数过多的缺点.开彩红等[10]提出了一种基于人工蜂群(artificial bees colony, ABC)算法的中继卫星任务编排算法.通过在算法的迭代过程中对每个可行调度方案进行评估、邻域操作寻找局部最优调度方案，从而获得全局最优调度方案.邓博于等[22]针对遗传算法容易陷入局部最优和蚁群算法初始信息素匮乏的缺点，提出将遗传和蚁群融合算法应用于中继卫星系统的资源调度问题.通过改进蚁群算法信息素的定义，利用基于时间窗口序号编码思想，给出中继卫星资源调度约束条件与目标函数并建立数学模型.Liu等[23]研究了基于数据中继卫星的空间网络调度问题，在模型中考虑了天线转动时间.Lin等[24]提出了一种非对称路径重连接方法解决中继系统中的工作调度问题.Deng等[25]提出初始调度与动态调度相结合求解中继卫星系统的调度问题.

笔者针对中继卫星单址天线调度问题进行研究，主要贡献包括：着眼中继卫星系统应用实际以及用户需求特点，面向多中继卫星多用户航天器大规模调度问题，扩展用户申请的自主性和灵活性，设计基于多滑动窗口用户申请的中继卫星应用模式，允许用户提交多个备选服务窗口，指定天线偏好，使得模型更加符合实际情况；详细分析该应用模式下中继卫星单址天线调度问题的优化目标和约束条件并建立相应的优化调度模型；设计相应的启发式算法求解调度问题；最后通过仿真实验验证该调度方法的有效性.

1 中继卫星调度模型

笔者对于中继卫星单址天线调度问题的研究，面向的是多中继卫星多用户航天器的大规模调度问题，该问题有两个主要的输入：任务申请和中继卫星资源.任务申请即是各用户航天器根据自身需求，向中继卫星相关管理机构提出的对某段时间窗口的占用申请.中继卫星资源主要指的是中继链路，由于笔者研究的是单址天线的调度问题，中继卫星可以搭载多个单址天线，一个单址天线在同一时刻只能提供一条中继链路，即在同一时刻只能执行一项任务.因此可以将中继卫星单址天线与链路等同，作为基本资源单位.本研究中，中继卫星资源输入信息包括多颗中继卫星搭载的多个单址天线的可用时间窗口，以及各中继卫星单址天线对各用户航天器的可见时间窗口.其中，可用时间窗口由中继卫星相关管理机构发布，可见时间窗口由中继卫星和用户航天器轨道参数决定.

中继单址天线调度问题的输出主要是针对每个中继卫星单址天线的调度方案，可以从任务和天线两个角度进行定义.从任务角度分析，中继单址天线调度问题的输出即是确定每项任务是否成功调度，若成功调度，确定该任务由哪条天线对其进行服务，以及服务的开始时刻、结束时刻、持续时间等.从中继卫星天线角度分析，中继单址天线调度问题的输出即是对每个天线确定周期内的工作计划，具体包括何时开始对哪个用户航天器执行任务，以及任务的结束时刻、持续时间等.

1.1 模型假设与符号说明

首先对数学模型中将用到的符号进行说明，如表1所示.

表1 集合符号定义

1.2 中继卫星单址天线周期调度问题的数学规划模型

中继卫星单址天线调度问题，实质上是要建立中继卫星资源与各任务之间的映射关系.其目的是使中继卫星资源在一个调度周期内完成的任务能够最大程度地满足用户的需求.因此，必须对任务和中继卫星资源进行统一管理，通过调度规划，为各项任务分配相应的资源，使调度方案在满足各项约束的条件下达到预期的效果.

在笔者介绍的中继卫星应用模式下，中继卫星单址天线调度问题就是对每项任务申请确定以下6个维度的信息：选择在哪个备选服务时间窗口执行、选择哪个中继卫星单址天线执行、选择该中继卫星单址天线的哪个可用时间窗口执行、选择该中继卫星单址天线与任务所属用户航天器的哪个可见窗口执行、实际任务开始时刻以及实际任务服务时长，因此，决策变量包括xt,tk,r,trj,rl、startt,tk,r,trj,rl和timet,tk,r,trj,rl.

xt,tk,r,trj,rl为0～1变量，其值确定以下4个维度的信息：选择在哪个备选服务时间窗口执行、选择哪个中继卫星单址天线执行、选择该中继卫星单址天线的哪个可用时间窗口执行、选择该中继卫星单址天线与任务所属用户航天器的哪个可见窗口执行.

优化目标反映了优化问题研究的优化对象的本质.针对中继卫星单址天线调度问题，建立两个优化目标，其中任务完成率最大化是首要优化目标，用户期望满足度最大化是次要优化目标.

(1)任务完成率最大化

在大规模任务申请条件下，不可能所有的任务申请都得到满足，任务完成率就成为评价调度方案的重要指标，是调度模型的主要优化目标.

(1)

(2)用户期望满足度最大化

最大程度满足用户任务申请的偏好或者

期望，可以提高调度方案的服务水平，有利于提升任务执行的质量和效果.因此用户期望满足度是调度模型的另一个优化目标.在笔者的中继卫星应用模式下，用户期望得到满足需要以下两个条件：采用任务备选服务时间窗口指定或偏好的中继卫星天线；采用任务备选服务时间窗口的期望服务时长.

(2)

中继卫星调度问题主要包含两类约束：任务需求约束和资源使用约束.任务需求约束主要是用户根据其需求,提出的任务申请中包含的约束.

(1)任务的执行约束.在笔者提出的中继卫星应用模式中，允许用户根据实际需求提交多个备选服务时间窗口，在生成调度方案时，仅选择其中的一个备选服务时间窗口进行调度，不可对任务进行重复安排，并且每项任务仅选择一个中继卫星单址天线执行.根据该约束得到Constraint 1～2.

Constraint 1：每个任务仅选择一个备选服务时间窗口,

(3)

Constraint 2：每个任务仅选择一个中继卫星单址天线执行,

(4)

(2)任务的服务时间窗口约束.由于任务需求具有很强的时效性,例如遥感卫星获取的某些敏感数据必须通过中继卫星在用户申请的时间段内回传到地面站，因此，中继卫星对任务的服务时间窗口必须在相应的备选服务时间窗口范围内，过早或过晚都会影响任务执行效果，导致任务失败,根据该约束得到Constraint 3～4.

Constraint 3：每个任务的实际开始时刻不早于所在备选服务时间窗口的最早开始时刻,

startt,tk,r,trj,rl≥(startt,tk-forwardt,tk)·xt,tk,r,trj,rl.

(5)

Constraint 4：每个任务的实际开始时刻不晚于所在备选服务时间窗口的最晚开始时刻,

startt,tk,r,trj,rl·xt,tk,r,trj,rl≤startt,tk+backwardt,tk.

(6)

(3)任务的服务天线约束.如果选择的任务备选服务时间窗口指定了服务的中继卫星天线，则必须使用指定的中继卫星天线为该项目进行服务，使用其他天线则无法满足用户需求，视为任务失败,根据该约束得到Constraint 5.

Constraint 5：对于选择指定天线的备选服务时间窗口的任务，执行天线必须满足指定要求,

∀((rt,tk≠∅)∧(xt,tk,r,trj,rl≠0)),r=rt,tk.

(7)

(4)任务的服务时长约束.选择的任务备选服务时间窗口包含期望服务时长和最短服务时长，实际调度方案中的任务服务时长应不大于期望服务时长，不小于最短服务时长,根据该约束得到Constraint 6～7.

Constraint 6：每个任务的实际服务时长不大于备选服务时间窗口的期望服务时长,

timet,tk,r,trj,rl≤dt,tk.

(8)

Constraint 7：每个任务的实际服务时长不小于备选服务时间窗口的最短服务时长,

timet,tk,r,trj,rl≥dshortt,tk.

(9)

(5)中继卫星单址天线能力约束.一个单址天线在同一时刻只能提供一条中继链路，即在同一时刻只能执行一项任务，并且在任务开始之前，中继卫星天线需要根据预先计算结果，提前将天线转动到合适的角度与用户航天器进行对准操作，天线对准需要占用一定时间.在任务执行结束之后，中继卫星天线需要一段时间进行恢复调整，为执行下一项任务做好准备.在进行天线对准操作和天线恢复调整过程中，无法执行任务或进行其他工作，根据该约束得到Constraint 8.

Constraint 8：每个中继卫星单址天线任意时刻仅能执行一项工作，

∀r∈R,t1∈T,t2∈T,(adjust+Et1,r+rec)∩

(adjust+Et2,r+rec)=∅.

(10)

(6)可用时间窗口约束.可用时间窗口由中继卫星相关管理机构发布，由于任务执行过程不允许中断，因此中继卫星执行任务相关的所有操作，包括天线对准、任务执行与天线调整恢复，必须在中继卫星天线的某个可用时间窗口内完成,根据该约束得到Constraint 9～11.

Constraint 9：每个任务在中继卫星单址天线的一个可用时间窗口内执行,

(11)

Constraint 10：每个任务开始前的天线对准开始时刻不早于所在单址天线的可用时间窗口的开始时刻，

startt,tk,r,trj,rl-adjust≥startrl·xt,tk,r,trj,rl.

(12)

Constraint 11：每个任务结束后的天线调整恢复结束时刻不晚于所在单址天线的可用时间窗口的结束时刻,

(startt,tk,r,trj,rl+timet,tk,r,trj,rl+rec)·xt,tk,r,trj,rl≤endrl.

(13)

(7)可见时间窗口约束.可见时间窗口由中继卫星和用户航天器轨道参数决定，在任务执行过程中必须时刻保持中继卫星天线与用户航天器的直视.由于任务执行过程不允许中断，因此中继卫星的任务执行过程必须在中继卫星天线与用户航天器的某个可见时间窗口内完成.任务执行前的天线对准和任务完成后的天线调整恢复操作，不要求在可见窗口内完成,根据该约束得到Constraint 12～14.

Constraint 12：每个任务在中继卫星单址天线与用户航天器的一个可见时间窗口内执行,

(14)

Constraint 13：每个任务的实际开始时刻不早于所在单址天线与用户航天器的可见时间窗口的开始时刻,

startt,tk,r,trj,rl≥starttrj·xt,tk,r,trj,rl.

(15)

Constraint 14：每个任务的实际结束时刻不晚于所在单址天线与用户航天器的可见时间窗口的结束时刻,

(startt,tk,r,trj,rl+timet,tk,r,trj,rl)·xt,tk,r,trj,rl≤endtrj.

(16)

笔者建立的中继卫星单址天线周期调度模型为NP-hard问题，考虑多个滑动的备选服务时间窗口、多个中继卫星单址天线、多个可见时间窗口和多个可用时间窗口，问题的解空间随着资源与任务数量的增长呈指数激增且面临着组合爆炸的挑战.模型具有超高的决策变量维度以及复杂的约束条件，尚不存在按多项式时间复杂度找到全局最优解的算法，现有通用算法难以直接求解本模型，对模型求解算法的设计提出了更高的要求.

2 基于时间自由度的启发式算法

基于规则的启发式算法，具有求解速度快、稳定性高的优点，能够在较短的时间内给出较优的可行解，求解中继卫星调度问题的有效算法.笔者设计的基于时间自由度的启发式算法，考虑到用户的任务申请可以包含多个备选服务时间窗口，且备选服务时间窗口有可能指定或不指定中继卫星天线.依据任务申请包含的备选服务时间窗口数量以及指定天线情况，对任务的时间自由度进行评价，根据评价结果决定任务调度的优先次序.在调度理论中，该算法属于构造性算法，即依次对任务进行调度，最终生成较优的可行调度方案.

基于时间自由度的启发式算法主要包括以下4个算法模块：①任务时间自由度评价；②任务资源匹配；③任务插空；④资源刷新.①是根据任务的备选服务时间窗口数量及指定天线情况，评价任务的时间自由度并决定优先次序.②是根据任务提交的备选服务时间窗口信息，为任务匹配当前可用时段资源.③是基于启发式规则，根据②中任务各备选服务时间窗口与当前可见时间窗口以及当前天线可用时间窗口的匹配结果，为当前任务安排合适的调度方案.④是在安排新的任务之后，对现有可见时间窗口以及天线可用时间窗口进行刷新，删除已被占用的资源.

2.1 任务时间自由度评价

根据任务的备选服务时间窗口数量及指定天线情况，评价该任务的时间自由度.一般来说，提交的备选服务时间窗口数量越多，不指定天线的备选服务时间窗口数量越多，任务的时间自由度越高，任务调度的难度越小，可以使其获得较低的优先次序，在算法运行的靠后阶段进行调度.

具体的评价方式为：首先遍历任务集合T，获取最大备选服务时间窗口数量winmax=max{[Kt],t∈T}；然后依次分析任务集合T中的任务，获取当前任务t的备选服务时间窗口数量wint=[Kt]，当前任务t指定天线的备选服务窗口数量winassign；最后对当前任务t进行时间自由度评价，评价公式为：

scoret= (winmax+1-wint)+(winmax-

wint+winassign).

(17)

对其进行简化，即

scoret=2×(winmax-wint)+winassign+1.

(18)

式中：scoret的取值范围为[1,2×winmax]，任务t的时间自由度评价scoret取值越大，表明任务t的时间自由度越低，将取得较为靠前的调度次序.

2.2 任务资源匹配

对于当前处理的任务t，遍历其提交的备选服务时间窗口Kt，与现有资源进行比对，得到可以安排的可用时段资源.任务资源匹配需要与当前可见时间窗口和当前天线可用时间窗口分别进行比对，将匹配得到的可用时段资源分成两类存放：一类是指定天线的备选服务时间窗口匹配得到的可用时段资源集合，记为taskresource1；另一类是不指定天线的备选服务时间窗口匹配得到的可用时段资源集合，并记录其偏好信息，记为taskresource2.

任务资源匹配方法如图1所示，其中dtimet,tk是任务t的备选服务时间窗口tk在任务资源匹配时采用的服务时长.

图1 任务资源匹配方法Fig.1 The task-resource matching method

对于当前备选服务时间窗口tk，若tk指定中继卫星单址天线，则首先遍历其指定天线rt,tk与该任务用户航天器当前可见时间窗口集合Jt,r.对于Jt,r中的可见时间窗口trj，若满足条件

(19)

则可见时间窗口trj与当前备选服务时间窗口tk无交集，可直接排除；对于与tk有交集的可见时间窗口trj，判断其是否满足以下条件：

(20)

若满足该条件，则可见时间窗口trj可用，继续进行下一步比对.遍历指定天线rt,tk的当前可用时间窗口集合Jr，对于Jr中的可用时间窗口rl，若满足条件：

(21)

则可用时间窗口rl可用.该步比对加入了任务执行前的天线对准和任务完成后的天线恢复调整时间.记可用时段资源开始时刻为T1，可用时段资源结束时刻为T2，并同时记录可用时段资源所在中继卫星单址天线，记入taskresource1.

2.3 任务插空

对于当前处理的任务t，根据任务资源匹配算法得到的可用时段资源集合taskresource1和taskresource2，进行任务的安排.

首先判断taskresource1是否非空，若其非空，在其中随机选择一个可用时段资源进行调度，采用紧前、随机或紧后策略，转入算法(2.4)刷新资源.任务插空方法如图2所示.

图2 任务插空方法Fig.2 Task insertion method

其中，紧前策略

(22)

随机策略

(23)

random()为随机生成的[0,1]的随机数.

紧后策略

(24)

若taskresource1为空集，判断taskresource2的情况，若其非空，遍历其中的可用时段资源，找出其中天线偏好非空且与可用时段资源所在天线相同的时段.如果存在天线偏好非空且与可用时段资源所在天线相同的时段，在其中随机选择一个进行调度，采用紧前、随机或紧后策略，转入资源刷新操作.若不存在天线偏好非空且与可用时段资源所在天线相同的时段，则在taskresource2中随机选择一个可用时段资源进行调度，采用紧前、随机或紧后策略，转入资源刷新操作.

若taskresource2也为空集，则将该任务所有备选服务时间窗口采用的服务时长由期望服务时长改为最短服务时长，转入任务资源匹配操作，重新进行任务资源匹配，得到该任务的taskresource1和taskresource2，并重复上述过程.

若taskresource1和taskresource2仍均为空集，则认为当前资源无法完成该任务的调度，当前任务调度失败.

2.4 资源刷新

每当有任务被成功调度，会占用该中继卫星单址天线与本用户航天器以及其他用户航天器的可见时间窗口以及天线可用时间窗口，由于资源的互斥性，需要对可见时间窗口以及天线可用时间窗口均进行刷新，删除本次调度占用的时段.被占用的时段不仅包括任务的服务时长timet,tk,r,trj,rl，还包括之前的中继卫星天线对准时间adjust以及随后的恢复调整时间rec.

对可见时间窗口资源进行刷新时，要遍历该中继卫星单址天线r对所用用户航天器的所有可见时间窗口，对当前处理的可见时间窗口trj，令

(25)

则本次调度所占用的时段与可见时间窗口trj可能存在的情形如图3所示.

图3 可见时间窗口资源删除及刷新方法Fig.3 Method for deleting and updating visible time-windows

针对不同情况的刷新方法如表2所示.

表2 针对不同情况的资源刷新规则Tab.2 Resource update rules under different conditions

天线可用时间窗口资源删除及刷新方法与上述方法相同，在此不再赘述.

3 仿真实验

3.1 实验设置

实验平台为配置3.29 GHz Intel Core CPU、8 GB内存、Windows 7操作系统的PC机，算法在Matlab 2014中编程实现.由于采用基于多滑动窗口用户申请的中继卫星应用模式，没有标准测试集可供调用，为完成仿真实验，首先进行中继卫星资源与任务需求场景仿真，生成所需应用场景.在此基础上，对笔者所提算法进行测试.

中继卫星相关管理机构下属4颗中继卫星，每颗中继卫星载有1副中继卫星单址天线用于执行常规任务，面向的用户部门共下属20颗用户航天器.

根据日常工作安排，中继卫星相关管理机构于2017年11月25日发布2017年12月1日0时～2017年12月7日0时的可用中继卫星资源，各用户部门可根据自身工作需要与所属航天器工作情况于2017年11月28日前进行任务申请，允许每项任务申请提交1～3个备选服务时间窗口.最终收到500个任务申请，中继卫星相关管理机构于2017年11月29日完成周期调度工作，在周期调度方案生成后，2017年11月30日有3个临时任务申请到达.任务开始前中继卫星单址天线对准时间10 min，任务结束后中继卫星单址天线恢复调整时间4 min.

针对以上假定的应用场景，将相关参数整理如表3所示.

表3 应用场景参数设置

中继卫星资源主要包括中继卫星单址天线的可用时间窗口，以及各中继卫星单址天线对各用户航天器的可见时间窗口，需仿真相关数据用于后续实验.本案例将4个中继卫星单址天线的可用时间窗口设置为2017年12月1日0时至2017年12月7日0时均可用.对于各中继卫星单址天线对各用户航天器的可见时间窗口，笔者利用STK软件设置了相关场景进行仿真，获取相关数据.

3.2 计算结果

利用基于时间自由度的启发式算法对上述案例场景进行测试，其中1～10项任务的调度方案如表4所示.

表4 基于时间自由度的启发式算法部分调度结果

表中信息值-1表示该项任务由于资源不足未成功调度，时间段数值的单位为天.

算法的主要评价指标数据如表5所示.实验结果表明，算法具有很快的运行速度，能够在2 s内完成500项任务规模场景的周期调度方案，任务完成率可以达到76.4%，用户期望满足度达到50.2%，具备较强的可用性，能够满足调度方案快速生成的要求.

3.3 与最大权重任务最先服务算法对比

表5 基于时间自由度的启发式算法性能指标Tab.5 The performance criterion of the heuristic algorithm based on the time freedom degree

可以发现基于时间自由度的启发式算法里使用了4个灵活的算子，包括任务时间自由度评价、任务资源匹配、任务插空和资源更新，保障算法能够快速高效得到中继卫星系统的调度方案.为了验证算法的有效性，将其与最大权重任务最先服务算法(highest weight task first service， HWFS)进行比较.最大权重任务最先服务算法的步骤如下:

Step 1：对待完成的中继任务根据其权重从大到小排序，形成任务队列Q.

Step 2：然后每次从任务队列Q中选出权重最大的任务t.

Step 3：为任务t安排最佳服务资源，从Q中删除t.如果Q=∅，算法结束；否则转Step 2.

两个算法的计算结果如表6所示.由表6中的数据可以看出，在该场景下，HA-TFD把HWFS的任务完成率从70%提升到76.4%，把HWFS的用户期望满足度从43%提升到50.2%，该对比实验说明，HA-TFD是一种更加灵活高效的启发式优化算法.

3.4 任务规模对算法的影响

为了分析不同任务规模对算法的影响，本节在任务需求仿真相关参数取值不变的条件下，设置100、300、500、800、1 200、1 600共6个不同任务申请数量的任务场景，分别对基于时间自由度的启发式算法和基于冲突消解的随机搜索算法进行测试.每个任务场景进行20次重复实验，对算法性能进行分析，相关数据如表7所示.

表6 算法比较结果Tab.6 Comparison results

表7 不同任务规模下的实验结果Tab.7 The experimental results of different scales of tasks

3.5 用户航天器数量对算法的影响

为了分析不同用户航天器数量对算法的影响，在任务需求仿真相关参数取值不变的条件下，仅改变应用场景参数中的用户航天器数量.设置4、8、16、20、28、36共6个不同用户航天器数量的任务场景，分别对基于时间自由度的启发式算法和基于冲突消解的随机搜索算法进行测试.每个任务场景进行20次重复实验，实验结果如表8所示.

表8 不同用户航天器数量下的实验结果Tab.8 Experimental results of different numbers of user Spacecraft

4 结论

分析中继卫星单址天线周期调度问题，考虑多滑动窗口用户申请的中继卫星应用模式，针对中继卫星单址天线周期调度多目标、多约束的特点，建立了数学规划模型.模型最大化任务完成率和用户期望满足度，其中任务完成率是最重要的优化目标，用户期望满足度是次要优化目标.将周期调度中的任务需求约束、资源使用约束作为模型的约束条件.提出基于时间自由度的启发式算法，算法利用任务申请信息在任务调度之前对任务完成难度进行评估，并以此为依据进行任务调度优先顺序的安排，提高了启发式算法任务调度的成功率，从而提高了调度方案的质量.笔者创造性地提出基于多滑动窗口用户申请的中继卫星应用模式，大大扩展了用户申请的自主性和灵活性，有利于提高调度方案的质量和中继卫星系统资源的使用效能，对于中继卫星系统实际应用模式的创新具有一定的借鉴意义.基于时间自由度的启发式算法具有求解速度快，算法稳定的优点，适用于应急调度情况和大规模调度场景，其不足之处在于，由于没有引入随机迭代求解策略，求解的质量还有待进一步提高.下一步将继续研究高效智能优化算法求解中继卫星调度问题，提高调度效率和调度方案质量.