基于DCSOP的低轨卫星测控数传资源动态调度模型研究

A DCSOP-Based Dynamic Scheduling of Low-Orbit Satellite Measurement and Control Data Transmission Resources Model

摘要: 针对低轨卫星测控数传资源动态调度问题，提出了一种基于动态约束满足优化问题(DCSOP)的动态调度模型。通过分析多星测控数传资源调度的原理和特点，对相关概念进行了定义及规范，实现了对象和调度过程的建模。本文在静态调度模型基础上，进一步针对设备失效情形提出了动态调度模型，该模型同时考虑了不引入新资源和引入新资源两种情形，使动态调度模型结果是对静态调度模型的一种递推修正。

Abstract: Aiming at the problem of dynamic scheduling of low-orbit satellite measurement and control data transmission resources, a dynamic scheduling model based on the Dynamic Constraint Satisfaction Optimization Problem (DCSOP) is proposed. By analyzing the principle and characteristics of multi-satellite measurement and control data transmission resource scheduling, the related concepts are defined and standardized, and the modeling of the object and the scheduling process is realized. Based on the static scheduling model, this paper further proposes a dynamic scheduling model for equipment failure situations. This model also considers the two situations of not introducing new resources and introducing new resources, so that the result of the dynamic scheduling model is a kind of evolution to the static scheduling model.

1. 引言

航天测控优化调度是一个涉及多种测控资源、多种航天器、多种测控需求类型、多种约束类型的组合最优化问题。目前，应用于航天测控优化调度及相关调度问题的模型主要有：数学规划模型、约束满足问题模型、Petri网模型、Agent模型、基于图论的模型等。

混合整数规划模型最早用于航天测控优化调度领域，美国空军卫星测控网(AFSCN)是美国空军用于卫星与地面站通信的网络，包括100多颗卫星和16个接收天线。20世纪80年代，为了应对AFSCN出现的资源不足和测控需求增加之间的矛盾，由IBM公司的Arbabi [1] 博士领导的研究小组在1981至1984年间，提出了航天测控优化调度问题并采用混合整数规划模型对其进行了研究，模型以测控任务是否在远程跟踪站(Remote Tracking Station, RTS)上的任意时间窗口中调度为决策变量，以最大化成功调度测控任务的收益值之和为目标函数，并应用调度人员人工排序时使用的启发式规则对模型进行求解。

Arbabi的混合整数规划模型最多只能在合理时间内处理50个以内的测控任务，为了满足求解更大规模航天测控优化调度问题的需要，1992年，美国空军技术学院(AFIT)的Gooley [2] [3] 对AFSCN中的各种轨道卫星的调度问题进行了研究。在研究低轨卫星调度问题时，建立了该问题的混合整数规划模型。该模型按某地面站天线是否分配给某卫星需求定义了0-1决策变量，以某地面站天线分配给某卫星需求后的开始服务时间定义了一个连续决策变量，以被调度的测控任务数量最大作为目标函数。同时考虑了多类约束，采用整数规划算法对低轨卫星调度模型进行求解。

国内方面，吴斌 [4] 基于测控操作的一般原则，用整数规划模型对测控资源最优调度进行了描述。贺仁杰 [5] 在研究侦察卫星对点目标的任务规划问题时，将多星调度问题视为具有时间窗口的多机调度问题，建立了混合整数规划模型。刘洋等 [6] 研究了单天线地面站任务调度问题，将地面站天线与卫星的通信视为任务，考虑任务权重和地面站天线转换时间，以最大化完成任务权重之和为目标，建立了整数规划模型。金光 [7] 针对航天测控优化调度问题提出了一种非线性泛函模型，以规定时段内所有地面站稳定跟踪服务总时间为衡量调度结果的目标函数。常飞 [8] 深入研究了卫星地面站数传资源配置优化模型与算法，设计了基于元模型的地面站数传资源配置方案优化框架，构建了地面站数传资源配置方案与其数传能力之间映射关系的元模型，并在此基础上进行地面站资源配置优化。从以上研究现状可以看出，目前国内外关于测控数传资源筹划问题的研究尚存在以下几方面不足：1) 现有研究成果主要集中在测控数传资源静态筹划问题研究，即测控数传资源配置优化问题，而未涉及资源动态筹划问题；2) 测控资源配置与数传资源配置分开独立研究，并没有面向卫星任务进行测控、数传资源融合考虑。

本文通过分析多星测控数传资源调度原理和特点，对测控需求、数传需求及约束条件进行了规范化描述，在静态调度模型基础上，研究提出了一种基于DCSOP的六元组动态调度模型。该模型重点考虑了不引入新资源和引入新资源两种情形。

2. CSP和CSOP概念

2.1. 约束满足问题CSP概念

约束满足优化问题(Constraint Satisfaction and Optimization Problem, CSOP)融合了约束满足问题和优化问题，是有约束情况下的优化问题，满足约束条件的解即为可行解，问题的最优解是使目标函数值取得全局极值的可行解。

对满足约束的需求以及优化目标要结合具体的领域知识进行确定，在资源能够满足需求时，即所有的任务都能被安排时，要在满足所有约束的基础上依据目标函数进行优化；而在资源不能满足需求时，硬约束必须满足，而允许软约束被违反，此时局部解是可接受的，问题是需要寻找一个使目标函数值取得局部极大或极小的解，这种情况下也可认为是部分约束满足问题(Partial Constraint Satisfaction Problem, PCSP)，针对不同的问题和优化目标，软硬约束可依据问题相互转化。

2.2. 约束满足优化问题CSOP概念

前文介绍的约束满足问题的一个显著的特点就是它是静态的，即它的变量集、值域以及约束关系集一经确定，在整个问题的求解过程中，是不变的。而在实践中，许多问题并不是不变的，会由于各种扰动的存在，使得问题发生变化。DCSP就是由一系列静态约束满足问题在时间轴上构成的序列。

设 $P=\left\{V,D,C\right\}$ 为一典型的CSP问题， $P^{\prime }=\left\{V^{\prime },D^{\prime },C^{\prime }\right\}$，若 $V^{\prime }\supseteq V$ (即变量数目增加)， $\forall v\in V$， ${D^{\prime }}_v\subseteq D_v$ (即每一个变量的值域减小)，且 $C^{\prime }\subseteq C$ (即可行变量值的组合减少)，这种CSP问题称为强化CSP问题；相反，如果： $V^{\prime }\subseteq V$ (即变量数目减少)， $\forall v\in V$， ${D^{\prime }}_v\supseteq D_v$ (即每一个变量的值域减少)且 $C^{\prime }\supseteq C$ (即可行变量值的组合增加)，这种CSP问题称为弱化CSP问题。DCSP问题就是一个CSP问题序列： $P_1,P_2,\cdots ,P_n$，其中每个 $P_i\left(i\ge 1\right)$ 都是 $P_{i-1}$ 的强化或弱化。因此，DCSP事实上是一系列随时间演化的CSP问题。

2.3. 动态约束满足优化问题DCSOP概念

结合前面提到的CSOP和DCSP的基本概念，针对战损条件下站网快速重构模型，本课题提出了DCSOP概念。

在调度方案已经形成并在实施的过程中，随着调度方案在时间轴上的推移，CSOP问题的场景和任务数量在自然递减，即值域和变量集随着时间推移慢慢变小。当运行过程中发生某应急事件，使得原来调度方案执行无法满足要求，则需要依据新的值域和变量集，重新建立CSOP问题以适应应急事件的发生。为了描述这个动态调度过程，本文提出了DCSOP概念。

DCSOP就是由一系列CSOP在时间轴上构成的序列。设 $P\left(0\right)=\left\{V,D,C,O\right\}$ 为一个初始的CSOP问题， $P\left(t\right)=\left\{V\left(t\right),D\left(t\right),C\left(t\right),O\right\}$ 为正常执行过程中的CSOP问题，随着初始 $P\left(0\right)$ 解的随时间的推移， $V\left(t\right)$ 、 $D\left(t\right)$ 、 $C\left(t\right)$ 数目都减小； $P^{\prime }\left(t\right)=\left\{V^{\prime }\left(t\right),D^{\prime }\left(t\right),C^{\prime }\left(t\right),O^{\prime }\right\}$ 为t时刻出现应急事件的CSOP问题，此时的 $V^{\prime }\left(t\right)$ 、 $D^{\prime }\left(t\right)$ 、 $C^{\prime }\left(t\right)$ 和 $O^{\prime }$ 都有可能分别与 $V\left(t\right)$ 、 $D\left(t\right)$ 、 $C\left(t\right)$ 、O不同。因此需要重新求解 $P^{\prime }\left(t\right)$ 来适

应应急事件引起的变量、值域、约束或目标的变化。

3. 基于CSOP的低轨卫星测控数传资源静态调度模型

针对低轨卫星地基测控数传资源静态调度问题，文献 [9] 考虑测控、数传、低轨等不同组合下的用户需求，对测控需求、数传需求及约束条件进行规范化描述，构建了测控数传六元组任务模型。本节在此基础上，针对地面站失效情形，研究提出基于DCSOP的低轨卫星测控数传资源动态调度模型。

在研究测控数传资源的动态调度问题时，其动态调度模型依然可用六元组 $\Theta =\left\{A,S,TW,DV,C,J\right\}$ 来

统一描述。其中，A为任务集合，S为资源集合，TW表示测控数传任务相对于测控数传资源的时间窗口

集，即可见弧段集合；DV为决策变量集合，包括任务需求规划变量 $t_k^{p,q}$ 和资源选择决策变量 $x_{k,h}$ ；C为

约束集合，包括任务需求约束、决策变量约束、时间窗口约束；J为优化目标。当前测控数传资源已分配

计划P_当前 ( $x_{k,h},k\in \left\{1,2,\cdots ,m\right\},h\in \left\{1,2,\cdots ,z\right\}$ )，其中m为总的待执行任务个数，z为地基测控数传资源总

数。分析可知，因为某些原因导致部分设备失效不可用，希望在原有调度计划基础上重新生成新的调度

计划。假设共有u套设备失效，失效设备编号集合为 $D=\left\{D_1,D_2,\cdots ,D_u\right\}$，集合D中的每一个元素隶属于 $\left\{1,2,\cdots ,z\right\}$。

首先，针对地面站失效情形开展影响域分析，此阶段分析站点受损后受影响已分配的测控、数据接

收任务。从数学模型角度来说，设备失效等价于 $x_{k,d}=0,d\in D$，倘若之前在静态调度模型结果中 $x_{k,d}=1$ 的，则表示该任务因设备失效受到影响；倘若之前在静态调度模型结果中 $x_{k,d}=0$ 的，则表示该任务未受设备失效影响。因此，可针对每套失效设备 $d\in D$，通过统计静态调度模型结果 $\underset{d}{{\displaystyle \sum }}\left({\displaystyle \underset{k}{\sum }{x}_{k,d}\cdot P_k}\right)$ 开展其对任务的影响分析。 $P_k$ 为任务的优先级。

其次，针对设备失效情形建立测控数传资源快速重构模型，并求解得到资源快速重构方案。主要包括两个阶段：1) 第一阶段：利用现有资源，通过优化调整完成受影响的测控数传任务；2) 第二阶段：通过逐步引入新资源进行资源快速重构，从而完成测控数传任务。

综上所述，在静态调度模型的基础上，本节针对设备失效情形下资源重构问题，提出基于DCSOP的低轨卫星测控数传资源动态调度模型。由前面的分析可知，该模型主要考虑不引入新资源和引入新资源两种情形。

3.1. 不引入新资源情形

3.1.1. 任务集合

在不引入新资源情形下，任务集合同前述静态调度模型一致，为 $A=\left\{a_1^{p,q},\cdots ,a_k^{p,q},\cdots ,a_m^{p,q}\right\}$，其中m

为总的待执行任务个数。需要说明的是，相比前述静态调度模型，部分设备失效有可能会导致某任务圈次不可见，但这里为保持动态模型中任务序号与静态模型一致的延续性，仍然保留了原任务序号，但在约束集合中对相关决策变量值域空间做了约束限制。

3.1.2. 资源集合

地基测控数传资源集合同静态调度模型一致，为 $S=\left\{b_1,\cdots ,b_h,\cdots ,b_z\right\}$，其中z为地基测控数传资源总数。针对设备失效情形，假设共有u套设备因战损失效，战损设备资源集合为 $D=\left\{D_1,D_2,\cdots ,D_u\right\}$，集合D中的每一个元素隶属于 $\left\{1,2,\cdots ,z\right\}$。

3.1.3. 可见弧段集合

用TW表示测控数传任务相对于测控数传资源的时间窗口集，即可见弧段集合。测控数传任务k相

对于地基测控数传资源h的时间窗口为 $t{w}_{k,h}=\left[st{w}_{k,h},et{w}_{k,h}\right]$， $k\in \left\{1,2,\cdots ,m\right\},h\in \left\{1,2,\cdots ,z\right\}$。其中， $st{w}_{k,h}$ 为可见时间窗口 $t{w}_{k,h}$ 的开始时间， $et{w}_{k,h}$ 为可见时间窗口 $t{w}_{k,h}$ 的结束时间，相关数值由可见报提供；倘若测站对任务不可见，则有 $st{w}_{k,h}=0$， $et{w}_{k,h}=0$。对于低轨航天器而言，由于其可见时间很短(几分钟

到十几分钟不等)，可认为其可见时间窗口即为执行时间窗口。

3.1.4. 决策变量集合

决策变量用DV表示，包括任务需求规划变量 $t_k^{p,q}$ 和地基资源选择决策变量 $x_{k,h}$，均为0-1型决策变量。

1) 任务需求规划变量

引入任务需求规划变量 $t_k^{p,q}\in \left\{0,1\right\}$， $t_k^{p,q}=0$ 表示无任务需求， $t_k^{p,q}=1$ 表示有任务需求， $k\in \left\{1,2,\cdots ,m\right\}$，其中p为升降圈标识，q为任务类型标识。

2) 地基资源选择决策变量

引入地基资源选择决策变量 $x_{k,h}\in \left\{0,1\right\}$， $x_{k,h}=0$ 表示测控数传资源h不完成测控数传任务k， $x_{k,h}=1$

表示由测控数传资源h完成测控数传任务k，其中k为测控数传任务编号，h为地基测控数传资源编号。假设资源h对任务k可见，则变量 $x_{k,h}$ 值域范围为0和1；假设资源h对任务k不可见，则变量 $x_{k,h}$ 值域范围为0，这属于资源决策变量的值域约束。因此，根据测站可见报，即可得每个决策变量 $x_{k,h}$ 值域范围。

全部资源选择决策变量 $x_{k,h},k\in \left\{1,2,\cdots ,m\right\},h\in \left\{1,2,\cdots ,z\right\}$ 的赋值对应于一个地基调度计划，结合时间

窗口数据就可得到调度计划表。

3.1.5. 约束集合

在不引入新资源情形下，动态调度模型的关于指定圈次任务需求、低轨卫星长期管理任务基本需求、数传任务需求、任务需求变量对测控数传资源选择变量的制约、时间窗口等约束条件同前述静态调度模型一致。与静态调度模型不一样的地方是，新增资源决策变量赋值约束，即部分设备战损失效无法执行任务，相关约束可表示为：

$x_{k,d}=0,d\in \left\{D_1,D_2,\cdots ,D_u\right\}$。

3.1.6. 优化目标

针对不引入新资源情形，此时优化目标J包括两部分：一部分是最大化任务效益 $J_t$，另一部分是对原有方案改动最小，定义指标为 $J_r$。

1) 最大化任务效益优化目标 $J_t$ 为：

$J_t={\displaystyle \underset{k}{\sum }{\displaystyle \underset{h}{\sum }{x}_{k,h}\cdot P_k}}$。

2) 当前站网资源已分配计划P_当前 ( $x_{k,h},k\in \left\{1,2,\cdots ,m\right\},h\in \left\{1,2,\cdots ,z\right\}$ )，动态调度优化新生成的计划P_新( ${x^{\prime }}_{k,h},k\in \left\{1,2,\cdots ,m\right\},h\in \left\{1,2,\cdots ,z\right\}$ )，对原有方案改动较小指标定义为

$J_r=1-\frac{{\displaystyle \underset{k}{\sum }{\displaystyle \underset{h}{\sum }xor\left(x_{k,h},{x^{\prime }}_{k,h}\right)}}}{mz}$。

$xor(·)$ 运算符：相异元素返回1，相同元素返回0。 $J_r$ 值越大，说明新生成方案对原有方案改动越小。

综上所述，优化目标J可表示为：

$J=\max \left(w_t{J}_t+w_r{J}_r\right)$

其中， $w_t$ 和 $w_r$ 为权重系数。

3.1.7. 初始解构造

在不引入新资源情形下，动态调度模型初始解可在当前资源已分配计划P_当前

( $x_{k,h},k\in \left\{1,2,\cdots ,m\right\},h\in \left\{1,2\cdots ,z\right\}$ )基础上改造构成，即强行使得 $x_{k,d}=0,d\in \left\{D_1,D_2,\cdots ,D_u\right\}$。此时，该解P_不引入 ( $x_{k,h},k\in \left\{1,2,\cdots ,m\right\},h\in \left\{1,2,\cdots ,z\right\}$ )是可行解，但无法满足所有任务。利用该解作为初始解，进行迭

代求解。

3.2. 引入新资源情形

倘若部分设备失效后利用现有测控数传资源，不能完成分配的任务，此时需要引入新的测控数传资源，包括预留资源、民商资源和机动资源等，从而完成资源快速重构。无论是引入预留、民商还是机动资源，其数学建模过程本质上来说是一致的。

3.2.1. 任务集合

当引入1套新资源 $b_{z+1}$ 后，测控数传任务集合变为 $A_{\text{new}}=\left\{a_1^{p,q},\cdots ,a_k^{p,q},\cdots ,a_m^{p,q},\cdots ,a_{m+v}^{p,q}\right\}$，其中 $m+v$ 为

总的待执行任务个数。值得注意的是，可能存在 $v=0$ 的情形，因为新增的资源 $b_{z+1}$ 并没有改变调度时间内n个航天器的可见圈数目，只有当新增了调度时间内某些航天器的可见圈数目时，此时才会有 $A_{\text{new}}$，且新增的航天器可见圈次依次排在原有的m个航天器任务之后，并不需要同原有的航天器任务一道按航天器进行重排序。这样能够保持设备失效前后两个场景中原有任务序号的一致性。

3.2.2. 资源集合

当引入1套新资源 $b_{z+1}$ 后，地基测控数传资源集合变为 $S_{\text{new}}=\left\{b_1,\cdots ,b_h,\cdots ,b_z,b_{z+1}\right\}$，其中 $z+1$ 为地基

测控数传资源总数(包含之前失效设备)。针对设备失效情形，假设共有u套设备失效，失效设备资源集合

为 $D=\left\{D_1,D_2,\cdots ,D_u\right\}$，集合D中的每一个元素隶属于 $\left\{1,2,\cdots ,z\right\}$。假设预留资源有N套设备。

3.2.3. 可见弧段集合

相关定义同静态调度模型。

3.2.4. 决策变量集合

在引入1套新资源 $b_{z+1}$ 情形下，测控数传任务集合变为 $A_{\text{new}}\in {ℝ}^{m+v}$，地基测控数传资源集合变为 $S_{\text{new}}\in {ℝ}^{z+1}$，此时相比原有静态调度模型，其资源决策变量从P_当前( $x_{k,h},k\in \left\{1,2,\cdots ,m\right\},h\in \left\{1,2,\cdots ,z\right\}$ )拓展为P_引入 ( ${x^{\prime }}_{k,h},k\in \left\{1,2,\cdots ,m+v\right\},h\in \left\{1,2,\cdots ,z+1\right\}$ )。

3.2.5. 约束集合

在引入1套新资源 $b_{z+1}$ 情形下，动态调度模型的关于指定圈次任务需求、低轨卫星长期管理任务基本需求、数传任务需求、需求变量对测控数传资源选择变量的制约、时间窗口等约束条件同前述静态调度模型一致。在此基础上，新增设备失效无法执行任务约束，即

$x_{k,d}=0,d\in \left\{D_1,D_2,\cdots ,D_u\right\}$

由前面的分析可知，还需要考虑 $v\ne 0$ 时，解内部固有约束，即

$x_{m+i,j}=0,\forall i=1,\cdots ,v;j=1,2,\cdots ,z$

倘若 $v=0$，则无需考虑上述约束。

因此，相比已分配计划P_当前，新的任务计划P_引入新增的有效资源决策变量为 $\left\{x_{1,z+1},x_{2,z+1},\cdots ,x_{m+v,z+1}\right\}$，

而其他从组合数学角度新增的资源决策变量

$\left\{x_{m+1,1},x_{m+1,2},\cdots ,x_{m+1,z},x_{m+2,1},x_{m+2,2},\cdots ,x_{m+2,z},x_{m+v,1},x_{m+v,2},\cdots ,x_{m+v,z}\right\}$，其值域为0。这样的好处是新的任务计

划P_引入可充分继承先前计划P_当前，以一种递推的方式构造新计划的初始解，而不需要做新旧计划的映射关系，大大节省计算量。

3.2.6. 优化目标

针对不引入新资源情形，此时优化目标J包括三部分：第一部分是最大化任务效益 $J_t$ ；第二部分是对原有方案改动最小，定义指标为 $J_r$ ；第三部分是引入资源套数较少，定义指标为

1) 最大化任务效益优化目标 $J_t$ 为：

$J_t={\displaystyle \underset{k}{\sum }{\displaystyle \underset{h}{\sum }{x}_{k,h}\cdot P_k}}$。

2) 当前站网资源已分配计划P_当前 ( $x_{k,h},k\in \left\{1,2,\cdots ,m\right\},h\in \left\{1,2,\cdots ,z\right\}$ )，动态调度优化新生成的计划P_新( ${x^{\prime }}_{k,h},k\in \left\{1,2,\cdots ,m\right\},h\in \left\{1,2,\cdots ,z\right\}$ )

$J_r=1-\frac{{\displaystyle \underset{k}{\sum }{\displaystyle \underset{h}{\sum }xor\left(x_{k,h},{x^{\prime }}_{k,h}\right)}}}{mz}$。

$xor(·)$ 运算符：相异元素返回1，相同元素返回0。 $J_r$ 值越大，说明新生成方案对原有方案改动越小。

3) 引入资源套数惩罚指标函数

对于新引入资源套数p，惩罚函数指标为

$J_p=1-\frac{p}{N}$

式中，N为预留资源总套数。 $J_p$ 值越大，说明完成任务需引入的新资源套数越少。

综上所述，优化目标J可表示为：

$J=\max \left(w_t{J}_t+w_r{J}_r+w_p{J}_p\right)$

其中， $w_t$， $w_r$ 和 $w_p$ 为权重系数。

3.2.7. 初始解构造

在引入1套新资源 $b_{z+1}$ 情形下，动态调度模型初始解可在当前站网资源已分配计划P_当前( $x_{k,h},k\in \left\{1,2,\cdots ,m\right\},h\in \left\{1,2,\cdots ,z\right\}$ )基础上改造构成：1) 强行使得 $x_{k,d}=0,d\in \left\{D_1,D_2,\cdots ,D_u\right\}$ ；2) 新增的资源决策变量 $x_{i,z+1}=0,\forall i=1,\cdots ,m+v$ ； $x_{m+i,j}=0,\forall i=1,\cdots ,v;j=1,2,\cdots ,z$ ( $v\ne 0$ 情形)此时，该解P_引入( $x_{k,h},k\in \left\{1,2,\cdots ,m+v\right\},h\in \left\{1,2,\cdots ,z+1\right\}$ )是可行解，但无法满足所有任务。

对于要同时引入多套资源时，依次类推，重复上述步骤进行建模。

4. 结论

针对地面站失效情形下低轨卫星测控数传资源动态调度问题，本文在对测控需求、数传需求及约束条件进行规范化描述的基础上，提出了一种基于DCSOP的动态调度模型，使动态调度模型结果是对静态调度模型的一种递推修正，在求解的过程中可大大减少映射的计算量。该模型同时考虑了不引入新资源和引入新资源两种情形，并进行了初始解构造，且数学模型是严格的，可用来进行寻优求解。