按需申请模式下的中继卫星任务规划模型与算法设计

，，

1.北京空间信息中继传输技术研究中心，北京 100094 2.北京卫星导航中心，北京 100094

中继卫星任务规划是按照各用户提交的服务需求，在满足特定约束的前提下，指定一定使用时长的中继卫星资源，以支持用户型号完成数传、测控等任务的活动[1-3]。结合具体应用背景，采用高效分配模式以制定合理的资源使用计划，这对于充分发挥中继卫星系统的服务能力至关重要[4-5]。

当前，随着用户型号的不断增加，持续的任务增长对中继卫星系统造成了较大的服务压力。在现有系统配置条件下，采用包括改进申请模式、调整计划流程、提升算法性能等手段，成为进一步挖掘系统服务潜力的有效途径[6-8]。其中，申请模式对于计划流程的设计和优化算法的选择都有决定性作用，其主要内容包括确定资源申请的时机和任务需求的描述方式。

在资源申请时机方面，周申请(长期申请)和临时申请(短期申请)是较为常见的申请方式。周申请方式要求用户提前一周确定需求集中提交，而中继卫星规划系统则以周为单位提前向用户发布可用资源时段。临时申请方式允许用户以随到随占用的方式提交申请，其所面向的仅为规划系统释放的可用资源。两种方式各有优缺点，通常结合使用，即主用长期申请方式，但以短期申请方式提交补充需求。在实际任务中，两种申请方式一般要求规划系统以同步周期释放各中继星的可用时段，该模式已逐渐难以适应任务需求的多样性，不利于发挥不同轨位中继星的能力优势。

在任务需求描述方面，“点杀”式申请较为常见，即用户为每个申请指定唯一占用的中继星和固定的捕跟时段，规划系统仅依据事先拟定的优先级准则判定申请是否得到满足。但实际上，用户往往并不关心任务执行的具体时段和中继星，而仅要求任务在某个时间范围内得到执行即可。因此，“点杀”式申请实质上削弱了中继卫星资源分配的灵活性，降低了计划调整的可行空间，制约了规划系统消解任务冲突的能力。为此，对任务时限性特征的精细化描述尤为必要，它是规划系统优化资源调配的重要依据。传统的任务申请在时效性描述方面，仅对捕跟时段进行明确，而将计划响应时限和计划变更时限则作为隐含

条件。例如，在周申请中，计划响应时限通常为计划提交后的1天，而在临时申请中，计划响应时限通常为计划提交后的若干分钟。

按需申请模式采用异步资源释放周期方式，可将应急任务需求的稀缺资源时段采用短期申请方式发布，而其余资源时段采用长期申请方式发布。在任务申请描述上，按需申请模式仅要求用户填写必要的需求要素，而诸如确定具体执行时段和选择服务资源等工作则全部交由规划系统完成。对于用户而言，按需申请是一种更为友好的申请方式。

本文以按需申请模式为研究背景，探讨从任务特征分析到规划模型构建，再到调度算法设计的具体实现方法。从现实用户申请中提取能够表述任务共性需求的特征要素，并对其中的复杂需求进行转换，形成可供规划系统集中处理的简单任务。在问题建模中，考虑异步资源释放周期对任务申请的影响，归纳出任务规划所需考虑的主要约束。在算法设计中，基于冲突风险规避策略进行资源时段选择，根据待规划对象的需求时段分布，为用户需求指派低冲突风险的执行时段。

1 任务需求的特征描述

为便于后续阐述，对文中出现的常用符号进行定义，如表1所示。

表1 相关符号定义Table 1 Definition of main notations

续表1

1.1 特征要素分类

在描述相同需求时，可能存在多种描述方式，其需求描述的非唯一性可概括为描述特征组合方式的多样性。一般而言，这些特征之间可能存在相互换算关系，并非完全独立。为实现用户需求的快速输入和集中规划，从众多描述特征中提取简单、独立，而又能最大程度涵盖用户原始需求信息的特征要素就显得极为必要[9-11]。

定义1：将独立的不可再分的任务称为简单任务(或元任务)，将非独立或需要通过分解转化的任务称为复杂任务。

将简单任务的描述特征称为基本特征要素，复杂任务可由基本特征要素和附加特征要素组合的形式描述。为实现统一建模，应保证任务描述的统一性，这就要求对复杂任务进行预处理，使其分解为简单任务。

1.2 基本特征要素

在按需申请模式下，描述简单任务的基本特征要素主要包括：

(1)提交时刻

用户向中继卫星规划系统提交任务申请的时刻。在周申请模式下，任务申请通常在约定时段内按批到达，往往具有相同提交时刻。在高动态应急任务场景下，任务申请以流的形式逐个到达，提交时刻具有随机性。

(2)用户中心/用户型号

中继卫星提供数据传输的服务对象，一个用户中心可能拥有多个用户型号，相同用户型号的不同业务也可能隶属多个用户中心。

(3)任务类型/优先级

任务类型是对任务性质的直接描述，能够直观体现任务执行价值和保障紧迫程度等。通常情况下，任务优先级与任务类型密切相关，其量化方法已有大量研究成果，本文不再赘述。

(4)需求时段

用户期望任务执行的时间范围，以滑动窗口的形式表示：

(5)捕跟时长/数据量

对于测控类任务，捕跟时长主要取决于用户期望的连续跟踪时长；对于数传类任务，捕跟时长主要依赖于任务传输数据量和中继卫星系统的数据传输速率。

定义2：捕跟时长加上预置任务模板的额定保护时长(状态准备时长和状态恢复时长)，即为实际占用资源时间，称为任务申请的服务时长。

在规划过程中，资源占用量往往换算成服务时长的形式。对于同一个任务申请，在不同中继资源上执行所采用的任务模板可能不同，因此服务时长也存在差异。

若指派taski在TDRSk上执行，所需的持续服务时长为：

式中：RPTi,k为系统准备时长；DTLengthi,k为持续捕跟时长；CPTi,k为状态恢复时长。

(6)资源偏好

在按需申请模式下，用户可以不指定任务占用的中继星，规划系统默认将所有符合约束条件的中继资源参与分配。但实际应用中，考虑到中继星能力的差异，用户对期望占用的中继资源存在偏好。为便于算法设计，将任务的资源偏好与需求时段绑定，即在提交滑动窗口时，区分为在各中继星上的可滑动窗口。

(7)计划响应截止期

无论任务需求是否得到满足，都应及时将计划结果反馈至用户。计划响应截止期是规划系统向用户发送计划结果的时限，也是确定中继资源规划时刻点的重要依据。

(8)计划变更截止期

用户能够接受的计划变更时限，对任务执行方案的调整应在该时限内完成，可作为重调度时，选择任务对象的依据。

在上述基本特征中，提交时刻、计划响应截止期、计划变更截止期、滑动窗口、可视窗口、捕跟时长等属于时效性特征，如图1所示。

令MFPTi=PBDi-ATi，称为taski的容忍计划反应时长。若MFPTi≤24 h，taski为短期任务，否者为长期任务。令MFDTi=DTEndi-ATi，称为taski的容忍任务反应时长。若MFDTi≤1 h，taski为快响任务，否则为常规任务。

1.3 附加特征要素

对于复杂任务需求的描述，除了要使用简单需求描述特征外，还需要利用诸如关联性、可分性、周期性等附加特征要素。

(1)关联性

任务的执行情况受其他任务影响，主要包括状态关联和时序关联两种类型。状态关联是指任务间的执行状态存在相互制约，可分为共生关联和独占关联。时序关联是指任务间的执行弧段存在相互制约，可分为间隔关联或顺序关联。

(2)可分性

任务可切割为多个子任务执行，子任务间可完全独立，也可具有关联性。任务分割需明确两项参数，即切割的粒度下限和数量上限。粒度下限是指切割后子任务应具有的最小捕跟时长/数据量，而数量上限是指最多允许的切割份数(子任务数量)。

(3)周期性

在一定时限内的重复需求可作为周期性任务，既适用于描述常态化任务申请，也适用于描述临时性的应急需求。

在以上附加特征要素中，关联性约束可在规划模型中直接体现；具有可分性特征的任务采用特定分解算法，分解为多个简单子任务，各子任务间具有关联性；具有周期性特征的任务，也可按照其需求频率，复制为多个非周期性的简单子任务。因此，具备上述需求特征的复杂任务均可通过预处理转换为简单任务。在后续问题建模和算法设计中，本文仅针对简单任务的情况进行研究。

2 问题描述与建模

在整个任务周期内，各用户中心提交的新申请不断到达，汇聚至等待处理任务队列中。中继卫星任务规划系统根据申请特征、资源状态、调度规则等信息安排调度事件序列，完成对所有任务申请的处理。在每次调度触发前，系统计算本轮调度追加释放的可用资源时段，并选择参与调度的任务对象，而调度事件本身也需耗用一定的时间。调度的结果是明确用户申请的满足情况，制定中继资源的使用计划[12-13]。每次调度后，均以新的任务状态更新之前任务状态。

如图2所示，设调度事件序列为SL={Sl1,Sl2,…,SlPNum}，对于第i次调度事件sli，所需占用的时段为SLWi=[SLBegini,SLEndi]，其中SLBegini和SLEndi分别为开始调度时刻和完成调度并反馈计划时刻。在sli中，向用户追加释放TDRSk的可用时段FTWi,k=[FTBegini,k,FTEndi,k]，其中FTBegini,k,FTEndi,k分别为FTWi,k开始时刻和结束时刻。通常情况下，规划系统完成一次调度所需时长较为恒定，不妨设为SLT=SLEndi-SLBegini，i=1,2,…,PNum。

设当前调度事件为slnow，向用户累计释放的TDRSk可用时段为：

在slnow开始后，对已到达任务依据其规划状态和执行状态进行分类。

1)完成服务任务集：当前已执行完毕的任务集合，表示为FTaskSetnow={taski|(VSi=0)∨(ASi=1∧ETEndi≤SLBegini)}。

2)当前服务任务集：当前已进入执行状态，但尚未执行完毕的任务集合，表示为ETaskSetnow= {taski|(PSi=1)∧(ETWi∩SLWnow≠∅)}。

3)等待服务任务集：当前已分配资源，但尚待执行的任务集合，表示为WTaskSetnow={taski|(PSi=1)∧(ETBegini>SLBeginnow)}。

4)未规划任务集：当前尚未参与规划且未丧失执行可能性的任务集合，表示为NPlanSetnow={taski|(ASi=0)∧(VSi=1)}。

5)拒绝服务任务集：当前暂时未被满足且未丧失执行可能性的任务集合，表示为DTaskSetnow={taski|(PSi=0)∧(VSi=1)}。

其中，判断taski规划价值的方法如下：

在上述集合中，对ETaskSetnow中任务计划的调整可能需要岗位人员手动干预完成，该过程具有较高的误操作风险，且耗时较长，因此本文不考虑抢占服务的情况。对待规划任务集WPlanSetnow的构造方法如下：

WPlanSetnow=WTaskSetnow∪DTaskSetnow∪

从中继资源使用者的角度考虑，所需优化的目标应为各用户中心的任务满足率，记为：

式中：Q为决策矩阵X的可行域。

定义3：构造区间长度度量函数dim()，对于任意时段tsi=[tbi,tei]，记dim(tsi)=tei-tbi。特别地，若tsi=∅，令dim(tsi)=0。

从中继资源管理者的角度考虑，优化目标为各中继星的资源使用率，记为：

调度过程中需考虑的主要约束包括：

约束1：对于本轮调度选取的任务对象，应保证在其计划响应截止期/调整截止期内，完成规划：

约束2：每个任务最多被执行一次，且只能选择由一颗中继星执行：

约束3：资源具有独占性，在某颗中继星上，同一时刻最多执行一圈任务：

约束4：对于被执行的任务，占用资源的时间不低于所需持续服务时长：

约束5：任务的捕跟时段应处于其滑动可视窗口内：

约束6：同一用户型号不能同时占用多颗中继卫星：

DTWi∩DTWi′=∅,

约束7：在计划方案制定过程中，非独立任务的关联性应得到满足：

约束8：仅将本轮调度前已累计释放的中继资源分配给任务：

[STBegini,STBEndi]∩VRTWnow≠∅,

每一轮调度，均为在满足以上约束的可行解域中寻找优化解的过程。调度完成后，更新任务的可执行状态、执行资源、执行时段等，从而形成新的计划方案。

3 冲突风险评估与规避

由于中继卫星资源的稀缺性，任务冲突在规划过程中广泛存在，冲突消解一直是计划制定与资源调配的难点[14-15]。在资源分配前，评估可能出现的冲突风险，可作为资源时段选择的重要依据。

3.1 冲突任务检测

对于待规划任务，可能存在的冲突对象包括当前服务任务、等待服务任务和其他待规划任务。在非抢占规则下，当前服务任务的状态不受待规划任务的影响，其占用的资源对于待规划任务完全不可用；对于等待服务任务，其预先分配的资源具备更改可能；而对于其他待规划任务，其需求仅作为当前待规划任务优选执行时段的考虑因素。因此，将与当前服务任务、等待服务任务和其他待规划任务形成的冲突，分别称为强冲突、弱冲突和需求冲突。

定义3：对于∀taski∈WPlanSetnow，在TDRSk上的强冲突任务集为：

CETaskSeti,k={taskj|VTWSi,k∩STWSi,k∩

定义4：对于∀taski∈WPlanSetnow，在TDRSk上的弱冲突任务集为：

CWTaskSeti,k={taskj|STWSi,k∩ETWj≠∅,

定义5：对于∀taski∈WPlanSetnow，在TDRSk上的需求冲突任务集为：

3.2 损失机会评估

在不变更WTaskSetnow中任务计划方案的前提下，计算taski在TDRSk上的可用时段为：

当不存在满足taski最小捕跟时长要求的可用时段时，可调整WTaskSetnow中任务的原方案。下面计算taski在TDRSk上的可协调时段：

若安排taski在TDRSk上执行，其可选的资源时段集合VCTWi,k为：

如果TDRSk在t∈VCTWi,k时刻被taski占用，则对于其他任务taskj∈WPlanSetnow，该时刻资源呈现不可用状态，即taskj损失在t时刻被TDRSk执行的机会。

定义6：在将WPlanSetnow中对TDRSk在t时刻存在服务需求的任务数量，称为对t时刻TDRSk的需求重叠度。

通常情况下，安排某个任务在具有较高需求重叠度的时段执行，将导致后续任务损失较多的潜在执行机会，进而降低后续任务的可执行性。因此，在选择执行时段时，应优先选择覆盖需求重叠度低的时段。

设taski为当前待调度任务，此时对t∈VCTWi,k存在服务需求的待规划任务集合为：

CReqSeti,k(t)={taskjt∈VCTWi,k∩STWSj

对t时刻TDRSk的需求重叠度为：

式中：‖·‖用于度量集合中的元素个数。

若安排taski在tsi=[tbi,tei]内由TDRSk执行，由此造成其他待规划任务损失的潜在执行机会为：

完成损失机会评估的关键在于构造出需求重叠系度分布函数。由于其为阶梯函数，因此可采用两个离散序列，即分布函数上的拐点和拐点间的重叠度描述。

构建序列KNi,k和CIi,k的基本步骤如下：

1:Let set CW←VCTWi,k,KNi,k←∅,CNi,k←∅;

2:Construct set CQTaskSeti,kby Eq.(17);

3:for each taskjfrom set CQTaskSeti,kdo

4:Let a=VCTWi,k∩STWSj,kand insert a to set CW;

5:endfor

6: Remove all time points from CW to KNi,k,and delete

the same one;

7: Sort all point in set KNi,kby increasing order, and

8:forj←1 tom-1 do

10:for each taskjfrom set CQTaskSeti,kdo

11:if Var∩STWSj,k≠∅ then

13:endif

14:endfor

16:endfor

算法中，Line 1对离散序列KNi,k和CIi,k进行初始化；Line 2检测存在需求冲突的任务；Line 3～5完成需求冲突任务集的构造；Line 6～7识别CNFi,k(t)的拐点；Line 8～15统计相邻拐点间的重叠度。

3.3 执行时段优选

在可选时段集合中，基于最小损失机会原则为taski指派执行时段，计算方法如下：

定理4：基于冲突风险规避策略获取taski在TDRSk上服务时段的最优解集合，其中必然存在某个解Etwi,k=[Etbi,k,Etei,k]，满足(Etbi,k∈KNi,k)∨(Etei,k∈KNi,k)。

根据上述结论，可采用算法遍历需求重叠系度分布函数的拐点，以获取etwi,k在最小损失机会原则下的最优解，基本步骤如下：

1:Let OSTW←∅,OSTL←∅,CTWNum←0;

4:CTWNum←CTWNum+1;

6: Calculate OStlCTWNum←LTLi,k(OStwCTWNum) by Eq.

(20);

7: Insert OStwCTWNumto OSTW, and add OStlCTWNumto

OSTL;

8:end if

10:CTWNum←CTWNum+1;

12: Calculate OStlCTWNum←LTLi,k(OStwCTWNum) by Eq.

(20);

13: Insert OStwCTWNumto OSTW, and add OStlCTWNum

to OSTL;

14:endif

15:endfor

16:if OSTW≠∅ then

17: Asumme OStlh=min {OSTL}, and let etwi,k←

OStwh;

18:else

19:etwi,k←∅;

20:end

算法中，Line 2～15检测至少有一个端点包含于KNi,k的可用服务时段OSTW；Line 16～20从OSTW中选出损失服务机会时长最小的时段指派给etwi,k，若不存在可用服务时段，则etwi,k为空。

4 结束语

采用按需申请模式可有效提升规划系统资源协调的灵活性，增加任务申请满足概率。本文针对新模式下的中继卫星任务规划模型与优化算法展开研究，提出了用户需求的基本描述要素，归纳了资源分配中所需考虑的主要约束，从使用者和管理者的角度分别提出了优化目标。在此基础上，基于冲突风险规避策略设计出问题的优化算法，给出了算法中采用的冲突检测模型和损失机会评估模型。所采用的启发式算法具有低时间复杂度，有利于计划方案的快速生成。但需要指出的是，本文虽然构建了异步资源释放周期条件下的任务规划模型，但并未给出资源释放周期的确定方法，该部分内容将在后续研究中作进一步探讨。

References)

[1] WANG J S, QI X. China′s data relay satellite system served for manned spaceflight[J]. Science China Technological Sciences, 2014, 44(3):235-242.

[2] ZHANG S J, CAO X B. Coordinated attitude control for a tracking and data relay satellite with mobile antennas[J]. Aircraft Engineering and Aerospace Technology, 2004, 76(4): 414-419.

[3] 李于衡, 黄惠明, 郑军. 中继卫星系统应用效能提升技术[J]. 中国空间科学技术, 2014, 34(1): 71-76.

LI Y H，HUANG H M，ZHENG J. Efficiency improvement technologies for tracking and data relay satellite system[J]. Chinese Space Science and Technology, 2014, 34(1): 71-76(in Chinese).

[4] MARCO A. Heuristic scheduling of the DRS communication system[J]. Engineering Applications of Artificial Intelligence, 1995, 8(2): 147-156.

[5] 陈英武, 方炎申, 顾中舜. 中继卫星单址链路调度模型与算法研究[J]. 中国空间科学技术, 2007, 27(2): 52-58.

CHEN Y W, FANG Y S, GU Z S. Algorithms for the single access link scheduling model of tracking and data relay satellite system[J]. Chinese Space Science And Technology, 2007, 27(2): 52-58(in Chinese).

[6] 王海波, 徐敏强, 王日新, 等. 基于蚁群优化-模拟退火的天地测控资源联合调度[J]. 宇航学报, 2012, 33(11): 1636-1645.

WANG H B, XU M Q, WANG R X, et.al. Solvingspace and ground TT&C resources integrated scheduling problem with ant colony optimization-simulated annealing algorithm[J]. Journal of Astronautics, 2012, 33(11): 1636-1645(in Chinese).

[7] WU B, LI Y X, HUANG Y X. Optimal scheduling of TT&C network resources based on genetic algorithm[J]. Journal of Astronautics, 2006, 27(6): 1132-1136.

[8] 张娜,柯良军,冯祖仁. 一种新的卫星测控资源调度模型及其求解算法[J].宇航学报, 2009, 30(5):1636-1645.

ZHANG N,KE L J,FENG Z R. A new model for satellite TT&C resource scheduling and its solution algorithm[J]. Journal of Astronautics, 2009, 30(5):1636-1645(in Chinese).

[9] 贺川, 孟宪贵, 祝转民, 等. 基于执行时段滑动调整策略的中继卫星任务规划算法设计[J]. 飞行器测控学报, 2015, 34(3): 246-253.

HE C, MENG X G, ZHU Z M, et al.Research on the tasks programming algorithm for tdrs based on the slide adjustment strategy of execution time[J]. Journal of Spacecraft TT&C Technology, 2015, 34(3): 246-253(in Chinese).

[10] TOSCO G, CRONE G, ROEDERER A G.. Analysis of the S-band communication link between the automated transfer vehicle and the data relay satellites in the presence of the space station[J]. IEEE Antennas and Propagation Magazine, 2002, 44(6): 12-23.

[11] VAZQUEZ A J , ERWIN R S. On the tractability of satellite range scheduling[J]. Optimization Letters, 2014, 9(2):311-327.

[12] LIU X L, BAI B C, CHEN Y W. Multi satellites scheduling algorithm based on task merging mechanism[J]. Applied Mathematics and Computation, 2014, 230(2): 687-700.

[13] WU G H, LIU J,MA M H. A two-phase scheduling method with the consideration of task clustering for earth observing satellites[J]. Computers & Operations Research, 2013, 40(7): 1884-1894.

[14] KOLICI V, HERRERO X, XHAFA F. Local search and genetic algorithms for satellite scheduling problems[C]∥Proceedings of the 8th IEEE International Conference on Broadband, Wireless Computing, Communication and Applications. Compiegne, 2013: 328-335.

[15] 刘洋, 贺仁杰, 谭跃进. 基于约束满足的多卫星调度模型研究[J]. 系统工程与电子技术, 2004, 26(8): 1076-1079.

LIU Y, HE R J, TAN Y J. Modeling the scheduling problem of multi-satellites based on the constraint satisfaction[J]. Systems Engineering and Electronics, 2004, 26(8): 1076-1079(in Chinese).