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

A CSOP-Based Static Scheduling of Low-Orbit Satellite Measurement and Control Data Transmission Resources Model

摘要: 针对低轨卫星测控数传资源调度问题，提出了一种基于约束满足优化问题(CSOP)的静态调度模型。通过分析多星测控数传资源调度原理和特点，对相关概念进行了定义及规范，实现了对象和调度过程的建模。本文将给航天器测控数传任务分配测控数传资源过程与为航天器选取合适的时间窗口视为等价过程，用航天器在测控数传资源可见圈内测控数传次数及测控数传持续时间描述其任务需求，在对测控需求、数传需求及约束条件进行规范化描述的基础上，构建了一种基于CSOP的六元组静态调度模型。

Abstract: Aiming at the problem of low-orbit satellite measurement and control data transmission resource scheduling, a static scheduling model based on the constraint satisfaction optimization problem (CSOP) 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. In this paper, the process of assigning measurement and control data transmission resources to spacecraft measurement and control data transmission tasks and selecting a suitable time window for the spacecraft are regarded as equivalent processes. The number of measurement and control data transmissions and the measurement and control data transmission duration in the visible circle of measurement and control data transmission resources are used by the spacecraft. Time describes its task requirements. Based on the standardized description of measurement and control requirements, data transmission requirements and constraints, a CSOP-based six-tuple static scheduling model is constructed.

1. 引言

测控数传资源筹划问题从时效性要求上可以分为两类问题：一类是静态筹划问题，给定未来一段时间的卫星测控、数传任务需求，在给定测控数传资源地理分布的情况下，优化配置测控数传资源数量，满足任务收益；另一类是动态筹划问题，给定当前测控数传资源配置方案和批量应急任务需求，或是测控数传资源发生故障损坏情况下，快速调配测控数传资源，满足应急任务需求或补偿任务损失。对于测控数传资源静态筹划问题，即地面资源优化配置问题，国外对于这类涉及卫星调度问题的研究起步较早，公开报道的文献也比较多。早在1981至1984年间，美国IBM公司的Arbabi博士等人就开始尝试利用计算机求解卫星调度(Satellite Range Scheduling, SRS)问题 [1]。此后，以美国空军技术研究院Gooley [2]、Parish [3] 和Schalck [4] 等人为代表，对美国空军卫星控制网(Air Force Satellite Control Network, AFSCN)下的卫星调度问题进行了深入研究。Jang [5] 在上述研究基础上进一步对AFSCN的服务能力进行了评估，Burrowbridge [6] 则分析了卫星网络资源的优化配置问题。随着我国航天事业的蓬勃发展，测控数传资源的规划管理问题成为国内相关领域学者的研究热点。王远振 [7] 提出了针对多卫星地面系统的设备进行优化配置的整体技术思路和研究方案，初步探讨了多星地面站系统设备配置方案效能评价、多星任务调度策略与算法以及设备配置方案优化算法等关键技术，并提出运用Delphi法与AHP法建立卫星地面系统设备配置方案评价指标体系，该体系包含5个准则16个指标要素。冯宏胜 [8] 研究了卫星地面站测控资源配置建模与优化方法，提出利用支持向量回归(SVR)的元建模方法拟合其输入输出关系，并运用拟合得到的回归函数预测未知的样本，据此进行地面资源的优化配置。常飞 [9] 深入研究了卫星地面站数传资源配置优化模型与算法，设计了基于元模型的地面站数传资源配置方案优化框架，构建了地面站数传资源配置方案与其数传能力之间映射关系的元模型，并在此基础上进行地面站资源配置优化。从以上研究现状可以看出，目前国内外关于测控数传资源筹划问题的研究尚存在以下几方面不足：1) 现有研究成果主要集中在测控数传资源静态筹划问题研究，即测控数传资源配置优化问题，而未涉及资源动态筹划问题；2) 测控资源配置与数传资源配置分开独立研究，并没有面向卫星任务进行测控、数传资源融合考虑；3) 现有研究建立的测控数传资源评估指标体系主要是从资源使用和任务满足率两个角度进行构建，而未考虑从站、区域和全网的角度来衡量测控数传资源支持能力和弹性能力。

本文通过分析多星测控数传资源调度原理和特点，对测控需求、数传需求及约束条件进行了规范化描述，在此基础上构建了测控数传任务模型，实现了对象和调度过程的建模。围绕低轨卫星测控数传资源调度问题，研究提出了一种基于CSOP的六元组静态调度模型。

2. CSP和CSOP概念

2.1. 约束满足问题CSP概念

约束满足问题(Constraint Satisfaction Programming, CSP)是描述约束规划问题时常用而有效的一种问题模型，它通常由1) 变量集2) 变量的值域3) 限制变量取值的约束集3部分共同定义。约束满足问题已经被证明是用于求解复杂组合优化问题的有效模式，其求解是从变量的值域中找到一组值，分配给变量，满足问题所有的约束，这样的一组值被称为满意解或可行解。

一个约束满足问题可定义为一个三元组 $P=\left(V,D,C\right)$，其中V为变量集合， $V=\left\{v_1,v_2,\cdots ,v_n\right\}$ ；令 $v_i\in D_i=\left\{d_1,\cdots ,d_{\left|D_i\right|}\right\}$，则D为变量的值域 $D=\left\{D_1,D_2,\cdots ,D_n\right\}$ ；C为约束关系集合 $C=\left\{C_1,C_2,\cdots ,C_m\right\}$，该集合体现了变量集合中各变量之间的约束关系，限制了变量的赋值空间，令 $V_i\subset V$， $R_i\subset D$， $i\in \left\{1,2,\cdots ,m\right\}$， $R_i$ 是与 $V_i$ 相关的值域，则 $c_i=\left(V_i,R_i\right)$，赋值 $\langle v_i,r_i\rangle$ 成立的充分必要条件就是要满足约束 $c_i$。

一个约束满足问题的约束可分为硬约束和软约束。硬约束是指必须被满足的约束条件，如果某个硬约束没有满足，则认为所得的解是不可行的；软约束是指可偏离的约束条件，即所得的解可偏离某些约束条件。例如对于某一任务集，“任务i必须被执行”属于硬约束，若调度计划中不包括i则不满足要求；“任务i不一定被执行”属于软约束，调度计划中可包括i也可不包括i。

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

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

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

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

本节重点针对低轨卫星地基测控数传资源静态调度问题展开分析。对于地基测控数传资源，在为其分配测控数传任务时，其调度本质上都是给其分配一个时间窗口，在此时间窗口内完成测控数传任务。因此，测控数传任务是测控数传资源调度过程的基本实体，具有不可中断约束特征，任务时间窗口属性即为任务航天器相对测控数传资源的可见时间窗口；测控数传资源是一元资源(某一时刻只能为一个目标航天器服务)，具有状态资源的特征(比如实际调度过程中的设备最高仰角)；约束集合主要包含资源约束和切换约束两类。调度问题约束建模就是要分析并识别调度问题中的各个要素，确定资源、任务及其时间窗口变量属性、约束集中的三类约束及目标约束，并将其模型化的过程。目标函数反映优化指标。一般将目标优化当作一种带目标的约束知识，本质上属于全局约束(global constraint)，称之为目标约束(object constraint)。当存在多个目标约束时，还要进一步对目标约束进行融合，比如采用加权和的方式进行目标约束融合。

因此，考虑测控、数传、低轨等不同组合下的用户需求，基于卫星测控与数传需求以及约束条件，对测控需求、数传需求及约束条件进行规范化描述，最后构建测控数传任务模型，构建方式如图1所示。

Figure 1. Model composition of telemetry control and data transmission mission

图1. 测控数传任务模型构成

综上所述，在研究测控数传资源的调度问题时，可作如下抽象：将给航天器测控数传任务分配测控数传资源过程与为航天器选取合适的时间窗口视为等价过程；用航天器在测控数传资源可见圈内测控数传次数及测控数传持续时间描述其任务需求；调度问题的优化需求通过优化因子反映到模型目标函数中。因此，测控数传资源静态调度模型可用六元组 $\Theta =\left\{A,S,TW,DV,C,J\right\}$ 来统一描述。其中，A为任务集合，S为资源集合，TW表示测控数传任务相对于测控数传资源的时间窗口集，即可见弧段集合；DV为决策变量集合，包括任务需求规划变量和资源选择决策变量；C为约束集合，包括任务需求约束、决策变量约束、时间窗口约束；J为优化目标。

3.1. 任务集合

任务集合用A表示，包括测控任务和数传任务。将航天器i在调度时间内待完成的任务定义为 $w_{i,j}^{p,q}$，其中 $i\in \left\{1,\cdots ,n\right\}$，n为所有参与测控任务调度的航天器总数； $j\in \left\{1,\cdots ,N_i\right\}$， $N_i$ 为航天器i在调度时间内的所有可见圈数目； $p\in \left\{0,1\right\}$ 为升降轨圈标识， $p=0$ 为升轨圈标识，根据航天器的圈次j标定， $p=1$ 为降轨圈标识，根据航天器的圈次j标定； $q\in \left\{0,1\right\}$ 为任务类型标识， $q=0$ 为测控任务标识， $q=1$ 为数传任务标识，根据任务属性标定。由此航天器测控数传任务集为：

$A=\left\{w_{1,1}^{p,q},\cdots ,w_{1,N_1}^{p,q};\cdots ;w_{i,1}^{p,q},\cdots ,w_{i,N_i}^{p,q};\cdots ;w_{n,1}^{p,q},\cdots ,w_{n,N_n}^{p,q}\right\}$。

为了标识，又记为 $A=\left\{a_1^{p,q},\cdots ,a_k^{p,q},\cdots ,a_m^{p,q}\right\}$，其中m为总的待执行任务个数。

令 $N_0=0$， $K_0=0$， $K_i=\left\{k|\underset{j=0}{\overset{j=i-1}{{\displaystyle \sum }}}{N}_j<k\le \underset{j=0}{\overset{j=i}{{\displaystyle \sum }}}{N}_j\right\}$， $i\in \left\{1,\cdots ,n\right\}$。

则当 $k\in K_i$ 时， $a_k^{p,q}$ 表示航天器i的第j圈任务，其中 $j=k-\max \left(K_{i-1}\right)$，p为升降圈标识，q为任务类型标识。

3.2. 资源集合

地基测控数传资源集用S表示。将地面站f的第g套测数传设备记为测控数传资源 $s_{f,g}^{}$，其中 $f\in \left\{1,\cdots ,l\right\}$ 为地面站编号，l为地面站总数；g为f地面站内测控数传资源的编号， $g\in \left\{1,\cdots ,L_f\right\}$， $L_f$ 为该地面站可用测控数传设备总数。地基测控数传资源集表示为：

$S=\left\{s_{1,1},\cdots ,s_{1,L_1};\cdots ;s_{f,1},\cdots ,s_{f,L_f};\cdots ;s_{l,1},\cdots ,s_{l,L_l}\right\}$

为了标识，又记 $S=\left\{b_1^{},\cdots ,b_h^{},\cdots ,b_z^{}\right\}$，其中z为地基测控数传资源总数。令 $L_0=0$， $H_0=0$， $H_f=\left\{k|\underset{j=0}{\overset{j=f-1}{{\displaystyle \sum }}}{L}_j<k\le \underset{j=0}{\overset{j=f}{{\displaystyle \sum }}}{L}_j\right\}$， $f\in \left\{1,\cdots ,l\right\}$。

则当 $h\in H_f$，h表示测控站f的第g套测控数传资源，其中 $g=h-\max \left(H_{f-1}\right)$。

3.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.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.5. 约束集合

3.5.1. 任务需求约束

1) 指定圈次测控任务需求

指定圈次任务的约束表达，记为约束 $C_1$。对于航天器i的第j圈有明确的测控任务需求，则即是 $k=\max \left(K_{i-1}\right)+j\wedge q=0$ 时：

$t_k^{p,q}=1$

2) 低轨卫星长期管理任务基本需求

低轨卫星长期管理任务基本需求：升轨测控 $P_0=2$ 圈，降轨测控 $P_1=2$ 圈。即是对于同一颗航天器i的测控任务，所有升轨测控任务(标识 $p=0\wedge q=0$ )要满足，记为约束 $C_2$ ：

$\underset{k\in {\Omega }_0}{{\displaystyle \sum }}{t}_k^{p,q}=P_0$

其中， ${\text{Ω}}_0=\left\{k|k\to p=0\wedge q=0\wedge k\in K_i\right\}$， $k\in K_i$ 表示属于同一航天器的任意测控任务； $k\to p=0\wedge q=0$ 表示使得标识p满足 $p=0$ 的该航天器的所有测控任务编号。

所有降轨测控任务(标识 $p=1\wedge q=0$ )要满足，记为约束 $C_3$ ：

$\underset{k\in {\Omega }_1}{{\displaystyle \sum }}{t}_k^{p,q}=P_1$

其中， ${\text{Ω}}_1=\left\{k|k\to p=1\wedge q=0\wedge k\in K_i\right\}$， $k\in K_i$ 表示属于同一航天器的任意测控任务； $k\to p=1\wedge q=0$ 表示使得标识p满足 $p=1$ 的该航天器的所有测控任务编号。

3) 数传任务需求

数传任务需求由卫星用户提出，通常为在规定时间段内完成Q圈数据接收工作，记为约束 $C_4$ ；显然，规定时间段肯定在调度周期内，结合星地可见性分析，可求得 $K_i$ 的一个子集 ${K^{\prime }}_i$，即 $k\in {K^{\prime }}_i$ 表示航天器 在数传需求规定时间段内可见圈次。因此，约束 $C_4$ 可表示为

${\displaystyle \underset{k\in {\Omega }_3}{\sum }{t}_k^{p,q}}=Q$

其中， ${\Omega }_3=\left\{q=1\wedge k\in {K^{\prime }}_i\right\}$。

3.5.2. 决策变量约束

决策变量包括任务需求规划变量和资源选择决策变量。

首先，根据测站可见报情况，可得到每个资源决策变量 $x_{k,h}$， $k\in \left\{1,2,\cdots ,m\right\}$， $h\in \left\{1,2,\cdots ,z\right\}$ 值域范围，将资源对任务不可见情形的资源决策变量赋值为0，约束为 $C_5$。

其次，任务需求规划变量对资源选择变量的制约，记为约束 $C_6$ ：

$\underset{h}{{\displaystyle \sum }}{x}_{k,h}\le \underset{q\in \{0,1\}}{{\displaystyle \sum }}{t}_k^{p,q}$

其中，h表示对于任意地基资源。

3.5.3. 时间窗口约束

对于地基测控数传资源h而言，资源选择决策变量 $x_{k,h}$ 满足，记约束为 $C_7$ ：

$st{w}_{k,h}\ge st{w}_{k^{\prime },h}$ 时，

$x_{k,h}\cdot st{w}_{k,h}-x_{k^{\prime },h}\left(et{w}_{k^{\prime },h}+r_h\right)+\left(1-x_{k,h}\right)\cdot M\ge 0$

$st{w}_{k,h}\le st{w}_{k^{\prime },h}$ 时，

$x_{k^{\prime },h}\cdot st{w}_{k^{\prime },h}-x_{k,h}\left(et{w}_{k,h}+r_h\right)+\left(1-x_{k^{\prime },h}\right)\cdot M\ge 0$

式中， $k\ne k^{\prime }$ 且 $k,k^{\prime }\in \left\{1,\cdots ,m\right\}$，M为任意大正数。 $r_h$ 为地基测控数传资源h的转换时间，设备转换时间认为只与设备有关，认为是设备属性，故每个测控数传资源的设备转换时间为一确定值。

综上所述，对测控资源调度问题建立其约束满足模型C如下：

主要约束有：

1) 任务需求约束： $C_1\vee \left(C_2\wedge C_3\right)\vee C_4$ ；

2) 决策变量约束： $C_5\vee C_6$ ；

3) 时间窗口约束： $C_7$。

3.6. 优化目标

优化目标用J表示。对于静态调度问题，该目标是最大化任务效益(最大化已完成任务的优先级之和)，记任务的优先级为 $P_k$，则该优化目标J为：

$J=\max \underset{k}{{\displaystyle \sum }}\left(\underset{h}{{\displaystyle \sum }}{x}_{k,h}\cdot P_k\right)$

3.7. 小结

分析可知，与经典的调度模型相比，上述调度问题模型具有较大的优势，主要体现在以下几个方面：

首先，模型中含有诸多非线性因素，比如优化目标中含有非线性的优化因子项；

其次，是涉及大量的输入参量及决策变量，除了资源选择变量还存在着需求变量的规划，兼有任务规划与资源调度的双重特征；

最后，模型中的任务开始执行时间决策变量取值为相应时间窗口中的某个值，又为模型增加了混合整数规划的特点。

4. 结论

针对低轨卫星测控数传资源调度问题，本文在对测控需求、数传需求及约束条件进行规范化描述的基础上，提出了一种基于CSOP的静态调度模型。与经典的调度模型相比，该调度模型除了资源选择变量还存在着需求变量的规划，兼有任务规划与资源调度的双重特征，虽然涉及大量的输入参量及决策变量，但其数学模型严格的，可用来进行寻优求解。