20世纪80年代，美国国家航空航天局(NASA)开始建设跟踪与数据中继卫星系统(TDRSS)，在对地静止轨道先后部署了11颗中继卫星^[1]，并在此基础上发展出“空间网络”和“空间通信与导航星座集成网络”^[2]，中继卫星系统在其中承担着骨干传输节点的关键作用。

空间网络中目标众多、任务庞杂，为了充分发挥中继卫星系统的效能，需要预备较长的时间用于优化任务调度，因此现有的中继卫星系统以预约式服务为主^[3]。以NASA的TDRSS为例，20世纪80年代NASA要求用户提前1周预约申请服务，用户申请和响应之间的时间间隔最长达到7×24 h^[4]。2000年后，NASA将用户预约申请时间缩短为24 h^[5]。随着中继卫星系统能力的提升，中继卫星系统支持目标的数量和对空间任务的响应速度都在不断提升，预约申请时间必将进一步缩短。

现有中继卫星系统任务调度研究的主要对象是预约式任务。文^[6]将约束规划(CP)模型应用于中继卫星任务调度，建立了约束满足规划(CSP)模型，在满足任务之间逻辑约束条件下，采用优先级高低作为资源竞争时的分配依据，但仅针对单个空间目标的复杂任务调度。文^[7]统筹考虑了中继卫星S和Ka频段服务链路，利用时间窗口的冲突检测分配链路资源，但由于遗传算法求解问题的收敛速度慢，仅适用于任务数量较少的情况。文^[8]提出一种六元法对任务进行分解，利用优先级高低作为资源分配依据，但仅解决单个中继卫星的任务调度。

文^[9]提出一种任务调度框架，将中继卫星的任务进一步分解为持续时间更短的子任务集合，但仅针对单个空间目标的可分解任务调度。上述预约式任务调度的研究均没有考虑空间任务的容忍延时能力，且主要集中在2个方面： 1) 从空间任务本身出发，考察任务内容的可分解性、相关性和冲突特性，寻求任务调度的最大收益； 2) 从时间特性出发，问题被归结为任务冲突检测，最终转变成优先级判决问题。此外，文^[5]假设空间任务之间相互独立，建立了一种并机调度模型，但忽略了单址接入(single access,SA)天线和多址接入(multiple access,MA)天线之间的差异^[1]。

针对上述问题，本文构建了中继卫星系统的多星多天线服务模型，并提出了一种动态的空间任务调度方法，仿真试验表明： 该方法能够有效提升中继卫星系统的空间任务完成能力，更好发挥多星多天线资源效能。

中继卫星搭载有SA和MA这2种天线。SA天线是机械转动的，天线转动时间与转动角度成正比，转动所需时间为分钟级别^[10]。MA天线采用数字波束成形技术，MA天线波束指向的调整时间是常量，调整所需时间小于1 s^[11]。此外，SA天线的传输速率大于等于MA天线，因此对于同一任务Job_i采用SA天线的处理时间小于等于采用MA天线的，即有：

$d_i^{SA} \le d_i^{MA}.$

假设当前任务集合J={Job₁,Job₂,...,Job_N}，有M个相互独立的中继卫星服务链路。Job_i的时间窗口为tw_i=[a_i,b_i]，其中a_i和b_i分别是Job_i的最早起始时间和最晚终止时间，且在tw_i内Job_i有m_i个链路可以提供服务，则可服务链路集合NPM_i可以表示为

$NP{M_I} = \left\{ {{M_{ik}}|k = 1,2,...,{m_i}} \right\},$

链路M_ik独立处理任务Job_i的持续时间为d_ik。

此外，还需定义以下几个变量：

1) x_ijk为任务序列化变量，如果在M_jk上Job_j被调度在Job_i之后则x_ijk=1，否则x_ijk=0。该变量满足以下约束条件：

$\sum\limits_{j \in J\backslash \{ Jo{b_i}\} }^{} {\sum\limits_{{M_{jk}} \in NP{M_j}}^{} {{x_{ijk}}} } \le 1.$

2) y_ik为服务链路标记变量，如果调度M_ik服务Job_i则y_ik=1，否则y_ik=0。该变量满足以下约束条件：

$\sum\limits_{{M_{jk}} \in NP{M_j}}^{} {{y_{ik}} \le 1.} $

3) s_ijk为天线准备时间变量，表示M_jk由Job_i切换至Job_j所属天线需要的准备时间，需要满足以下约束条件：

${S_{ijk}} \ge 0.$

4) w_ijk为链路空闲时间变量，表示M_jk从Job_i结束到Job_j开始的空闲时间，需要满足以下约束条件：

${\omega _{ijk}} \ge 0.$

5) t_ik为任务调度开始时间变量，表示Job_i在M_ik上的调度开始时间。

中继卫星系统任务调度问题被建模成如下多星多天线服务模型：

目标函数式(1)的物理含义是最大化中继卫星系统的任务调度收益，其中ω_i是Job_i的收益权重。约束式(2)用于保证任一任务只能服务一次，避免任务重复服务； 约束式(3)用于保证任一任务只能被一个中继卫星链路服务，避免重复服务； 约束式(4)用于保证在任一服务链路的调度序列中，任意任务的前者和后者均由该链路提供服务； 约束式(5)和(6)分别用于保证任一任务的服务开始时间必须晚于其时间窗口的起始时间，服务结束时间必须早于其时间窗口的终止时间 ；最后，约束式(7)用于保证相邻2个任务之间的等待时间要大于天线准备时间。

依据空间网络拓扑结构的动态变化，在时间上对调度过程进行细分，减小每次调度的规划时长和任务数量，进而达到动态的空间任务调度效果。

假设某一中继卫星在时刻i存在u_i个可视目标，当时刻j可视目标发生变化，则定义时刻i的规划时隙为

S_i=i,j-1, i<j,u_i≠u_j.

令ΔT为最小的规划时隙门限，当某一规划时隙小于该门限时，需与后一个规划时隙进行合并，则有：

${S_i} = \left\{ \begin{array}{l} [i,j - 1],j - i \ge \Delta T,{u_i} \ne {u_j};\\ [i,k - 1],j - i \lt \Delta T \le k - i,{u_i} \ne {u_j} \ne {u_k}, \end{array} \right.$

在时间上依次做递进处理，可以将整个时间轴细分为多个持续时间较短的规划时隙。

基于上述拓扑结构的动态变化特征，提出了一种动态的空间任务调度方法，具体实现步骤如图 1所示。

图 1 空间任务动态调度方法流程图

图选项

已知空间任务调度的时间范围为[T_b,T_e]，对n个中继卫星分别划分规划时隙，第j个中继卫星划分出的规划时隙依次为S^j₁,S^j₂,…,S^j_k,…。在具有最早起始时间的规划时隙S′内进行中继卫星系统资源分配，此时有：

$S' = \min (S_k^j),j = 1,2,...,n.$

选取当前规划时隙S′内可服务任务的集合J，其中任一Job_i的tw_i需要满足：

||tw_i∩S′||≥d_ik,

即tw_i与S′的交集需要大于d_ik。结合各个中继卫星的覆盖范围，逐个对任务进行可服务性分析，得到Job_i的NPM_i和任务的容忍延时约束集合

$||t{w_i} \cap S'|| \ge {d_{ik}}$

在当前规划时隙S′内，结合中继卫星2种天线资源差异，建立中继卫星系统的多星多天线服务模型。

最后，求解中继卫星系统的最优资源分配结果即空间任务的调度方案。

为了充分利用空间任务的容忍延时特性，提出了一种基于种群联合进化的中继卫星系统资源分配算法，算法实现流程如图 2所示。

图 2 中继卫星系统资源分配算法流程图

图选项

首先，确定在当前规划时隙S′内可服务的空间任务集合J。假设空间任务分为ρ个优先级，则按照优先级从高到低的顺序逐级调度。尝试将集合J中优先级为q的任务插入到当前服务链路k中，构造初始解p_q,k,j，重复N次上述过程随机构造一组初始解集合{p_q,k,j,j=1,2,...,N}。

然后，对{p_q,k,j,j=1,2,...,N}执行种群联合进化，通过邻域搜索实现对初始解集合的优化，得到进化种群中的当前最优解p_q,k。

最后，遍历ρ个优先级和M条服务链路，得到中继卫星系统资源分配结果{p_ρ,k,k=1,2,...,M}，即为任务调度的当前最优解。

针对空间任务具有容忍延时的特性，提出一种自适应任务子序列调整算法。当Job_i尝试插入到当前服务链路k的任务链P_q,k,j中时，可以通过灵活调整已调度任务的起止时间，进而构造出更优的解，如图 3所示。

图 3 空间任务插入任务链的示意图

图选项

图 3中当w_αβk≤d_ik时，Job_i无法插入到Job_α和Job_β之间。假设Job_α和Job_β具有容忍延时能力，Job_α开始时间可以前移即ΔD^f_α≥0，Job_β开始时间可以后移即ΔD^b_β≥0，如果有

${\omega _{\alpha \beta k}} + \Delta D_\alpha ^f + \Delta D_\beta ^b \ge {d_{ik}} + {\omega _{\alpha ik}} + {\omega _{i\beta k}}$

则Job_i插入到Job_α和Job_β之间成功，从而构造出更优的任务链。

当选择不同的相邻任务对进行任务插入时，得到的任务链也是不同的，因此，问题转化如何选择最优的任务对Job_α,Job_β。选用的目标函数是最大化空闲时间：

$\begin{array}{l} \max {f_k}(Jo{b_\alpha },Jo{b_i},Jo{b_\beta }),\\ {f_k}(Jo{b_\alpha },Jo{b_i},Jo{b_\beta }) = {\omega _{\alpha \beta k}} + \Delta D_\alpha ^f + \Delta D_\beta ^b - {d_{ik}} - {\omega _{\alpha \iota k}} - {\omega _{\iota \beta k}} \end{array}$

即当任务插入完成后，得到的新的任务链在Job_i前后具有最大的空闲时间。

针对空间任务调度中任务链的时间约束特性，提出了一种非对称路径重连算法用于解的邻域搜索，如图 4所示。

图 4 两个解的交叉示意图

图选项

在服务链路k的解集合{p_q,k,j,j=1,2,...,N}中，不同任务链中调度的任务集合可能存在差异,各任务的起止时间也就不同；另一方面，不同任务链中任务的执行顺序是不同的，天线用于任务切换的准备时间也就不同，因此，任意2个任务链在时间上是非对称的。

针对任务链之间的非对称特性，非对称路径重连算法选择以任务的中心时间点作为交叉点，可以生成邻域解的数量为

δ_pq,k,i↔p_q,k,j=2(|p_q,k,i|+|p_q,k,j|).

其中p_q,k,i和p_q,k,j分别表示任务链p_q,k,i和p_q,k,j中调度任务的数量。

在非对称路径重连过程中并没有增加调度任务的数量，产生的邻域解也不会优于当前解，还需在邻域解的基础上构造出更优的解，即采用自适应任务子序列调整算法对邻域解逐个进行优化。

采用非对称路径重连算法搜索的邻域局限于2个当前解，受2个解中已调度任务的影响，邻域解数量有限且容易陷入局部最优。因此，提出种群联合进化算法，实现步骤如图 5所示。

图 5 种群联合进化算法示意图

图选项

首先，需要采用自适应任务子序列调整算法随机构造多个初始解，组成初始种群。其次，将初始种群集合中的N个初始解随机配对，分成N/2对进行邻域搜索。然后，采用非对称路径重连算法对每对初始解的邻域空间进行搜索。在每对初始解的领域空间中选出最优的2个邻域解作为进化解。进化种群与初始种群的规模相同，进化解均源于初始种群，并优于初始解。

此外，采用自适应迭代准则控制迭代过程，即当进化种群相对初始种群没有明显改善时，则自动停止迭代进化过程，也可以通过设置迭代次数或者计算时间控制迭代进化过程。

以低轨卫星星座和中继卫星系统模拟空间网络运行场景。采用文^[12]中48低轨卫星星座，中继卫星星座由2颗对地静止轨道卫星组成，轨道参数选自STK9.0软件数据库，假设每颗中继卫星具有1个SA天线和2个MA天线，且各提供1条服务链路。

空间任务采用文^[5]的数据模型，场景持续时间为86 400 s，随机发生400个相互独立的空间任务分配在48个低轨卫星上。其中，200个任务为高优先级任务，权重设置为201； 其余200个任务为低优先级，权重设置为1； 全部任务权重为40 400 。

1) 算法性能对比。

假设400个空间任务不具有容忍延时能力，随机生成了15个实例，分别采用种群联合进化算法和贪婪算法^[5]进行调度，结果如图 6所示。

图 6 调度任务权重结果

图选项

图 6中，种群联合进化算法平均调度任务权重约为34 908 ，贪婪算法约为34 289 ，前者比后者多619，相当于多调度3个高优先级任务和16个低优先级任务。仿真结果表明： 采用种群联合进化算法能够明显提升调度结果，即使在没有容忍延时可以利用的情况下，依然全面优于贪婪算法。

2) 容忍延时仿真分析。

假设任一空间任务Job_i以概率p∈[0.0,1.0]具有容忍延时能力。针对不同的空间任务容忍延时概率生成10组实例，调度任务权重如表 1所示。

采用Evolution表示种群联合进化算法调度结果，Greedy表示贪婪算法调度结果。以贪婪算法调度结果为基准，种群联合进化算法相对于贪婪算法降低失败任务的比例为

$g = 1 - \frac{{40400 - Evolution}}{{40400 - Greedy}}$

根据表 1中的仿真结果可得种群联合进化算法增益如图 7所示。

仿真结果表明： 调度任务权重与空间任务容忍延时概率成正比，随着空间任务容忍延时概率的增加，调度任务权重也在增长(见表 1)，且种群联合进化算法始终优于贪婪算法(见图 7)，平均增益为18.7%，当容忍延时概率p=1.0时，取得最大增益为40.89%。

3) 空间任务延时分布。

当p=1.0时，取得最大任务调度收益权重40 108 ，对此时空间任务延时的统计结果如图 8所示。

图 7 种群联合进化算法相对于贪婪算法的增益

图选项

图 8 空间任务延时分布

图选项

在中继卫星系统处于满负荷运行状态下，全部调度任务的平均延时约为1 182 s。延时小于5 min的空间任务数量约占被调度任务数量的24%，小于15 min的约占50%，小于25 min的约占70%； 此外，还有10%以上的空间任务延时大于45 min。

本文面向中继卫星系统提出了一种多星多天线的空间任务动态调度方法。首先，针对中继卫星的单址接入天线和多址接入天线的服务特征差异，建立中继卫星系统的多星多天线服务模型。然后，利用空间网络拓扑结构动态变化的特征，提出一种动态的空间任务调度方法。最后，针对空间任务的多优先级和容忍延时特性，提出了一种高效的种群联合进化算法，与贪婪算法相比，能够降低约18.7%的任务失败概率，有效提高了中继卫星系统的任务完成能力，更好地发挥了中继卫星系统的资源效能。