通信卫星动态调度问题研究

近年来，在抗震救灾、远洋贸易、反恐维稳等通信中暴露出我国卫星通信保障能力有限、卫星通信资源调度缓慢等问题，卫星通信在全球通信、国防通信、应急通信以及边海疆通信中的重要作用日益突出。国家高度重视并加快了专用卫星通信系统的建设与发展，我国在轨通信卫星数量，天线波束和转发器类型、带宽、功率、工作频段，多址接入技术及地面终端类型、性能等将大幅提升，卫星通信保障能力将进一步增强。

通信卫星调度是指卫星调度中心根据资源状态及任务请求，依据任务优先级、时间窗口需求及资源任务匹配规则，以完成任务的优先级之和最大为优化目标，科学合理地利用卫星通信资源。当前多样化任务及应急任务对卫星通信应用提出了更高的要求，现有的人工调度方法无法解决大规模动态调度的突出问题。因此，通过研究建立通信卫星动态调度系统，能够有效提高卫星通信资源的利用效率。

一、通信卫星动态调度框架

通信卫星调度问题主要包括卫星通信资源、地面站资源、任务需求及调度约束条件等，通过通信任务场景的假设，对于上述资源及约束条件进行数学抽象，根据调度策略生成目标优化函数，建立调度模型，最后进行优化算法求解。通信卫星调度的目标就是要选择需要保障的通信任务、确定完成通信保障的卫星转发器资源及任务执行时间窗口。对于多颗卫星、多种转发器、多个通信任务需求的情况下，如何生成一个优化的卫星资源调度方案，合理分配卫星资源保障更多的通信任务，对充分发挥卫星通信系统效能是至关重要的。通信卫星动态调度总体框架如图1所示，通信卫星动态调度主要考虑新任务插入和资源变化两种扰动。

（1）新增任务而导致的动态调度

通信卫星调度过程中，新增任务的到达需要对初始调度方案进行调整，按照优先级高低尽可能满足所有任务需求，尤其当新增任务优先级相对比较高时，如果在资源有限且不能满足所有任务需求的情况下进行重新调度，那么需要中断某些低优先级任务的调度，满足新增高优先级任务的需求。

（2）通信卫星资源状态变化导致的动态调度

通信卫星调度过程中，通信资源状态变化是不确定的。卫星通信资源状态主要变化情况是卫星故障或者特殊情况下被敌方干扰，导致可用卫星通信资源的减少，如果卫星通信资源发生重大变化，则初始调度方案是无法继续执行的，需要进行初始调度方案调整。通常情况是资源的有限性造成了多任务调度问题的困难，因此对于卫星通信资源增加情况，即使存在部分任务没有被调度的情况，可以用初始调度模型对新任务与新资源重新进行求解匹配。

二、通信卫星动态调度流程

通信卫星动态调度流程如图2所示，通过对任务需求和卫星资源状态分析，为调度模型求解进行数据准备，确定可以满足通信任务需求的卫星及转发器资源。如果某个通信任务需求具有满足其要求的卫星通信资源（通过分析任务所属地面终端类型、所需通信资源），则需要计算该通信需求的可见时间窗口（卫星同地面站的可见时间段，主要是卫星点波束覆盖范围限制）。只有当通信需求同时具有可用资源和可用时间窗口，才认为该通信任务需求可能被完成，需要通过按照优先级调度原则来确定其是否被执行及执行该通信任务的卫星资源。然后，根据确定的通信需求、时间窗口等基本数据，建立通信卫星调度模型，采用优化算法对模型进行求解，分配通信任务的资源需求和时间窗口，获得初始调度方案。

在初始方案执行过程中，可能会出现各种扰动因素。需要根据扰动类型，对问题进行重新建模求解，以满足扰动需求。如果没有扰动发生，则执行初始方案；当有扰动发生时（主要指卫星资源状态变化或者新任务插入），则作相应的方案调整，这是一个根据实际需要重复执行的过程，当扰动发生时，如新任务插入，则需对新增任务进行调度预处理，即进行数据分析工作。

三、通信卫星动态调度模型分析

动态约束满足问题（Dynamic Constraint Satisfaction Problems，DCSP）能够很好地描述智能领域的调度、规划和组合等复杂问题，适用于表示和求解大规模组合优化问题，动态体现在变量、变量值域和约束条件的变化，如图3所示。根据动态变化状态，动态约束满足问题分为变量状态变化、约束条件动态变化和两者均有的混合变化。

调度问题一直是系统工程中的难点热点问题，通信卫星动态调度包括资源约束、时间窗口约束等通常的约束条件，还包括地面终端类型及任务时效性等复杂约束条件。通信卫星调度问题可视为一个基于DCSP的优化问题，可以将通信卫星动态调度问题中的任务、卫星资源与时间窗口、约束规则分别映射到DCSP中的变量集合、变量集合值域以及限制变量取值的约束集合。DCSP求解目标是确保原调度方案与新调度方案之间空间距离变化最小的情况下，完成任务优先级之和最大。

3.1新增任务的动态调度模型

当增加或减少CSP问题的变量数目时，将引发原问题发生改变，使之变成一个新的CSP问题。对于此类问题，需要考虑解的稳定性，即获得的初始解尽量能够继续使用。例如：调度问题中，用户在某时刻的需求是m，CSP根据用户需求进行求解得到了调度方案，在下一时刻用户的需求发生变化，又增加了n个需求，如果CSP在此时对该问题进行重新求解，其前面的解决方案会遭到破坏，这对于调度问题是很不利的。基于新任务到达的通信卫星调度模型就可以视为增加变量数目的CSP问题，即基于数量变化的DCSP问题。

基于新任务到达的动态调度可以简单表示为如图4所示，新任务的到达造成了变集合任务数量在tn时刻发生变化，约束集合新增了动态约束条件，变量的值域集合即卫星资源没有发生变化，tn时刻需要进行最小化地调整任务到资源的映射关系。

3.3动态调度遵循的原则

在动态调度过程中，必须充分考虑约束规则的变化，最大化保障任务需求。对于动态调度要遵循以下原则。

（1）优先级调度原则

在通信任务保障过程中，根据调度优化的目标，要按照优先级高低进行调度，高优先级的任务必须优先保障完成。针对某些突发事件带来的应急任务，是要求优先保障完成的，以确保突发事件的情况处置能力。在优先保障高优先级任务的条件下，最大化保障时效性强的低优先级通信任务。

（2）方案变化最小原则

由于扰动因素导致初始调度方案进行整时，应确保调整后方案与初始方案相比变化最小。对于卫星资源来说，卫星通信应用过程复杂，工作指令需要专门的时间和设备进行上传，大规模改变卫星指令浪费通信资源和时间；对于用户来说，初始调度方案确定后，可能相关用户根据调度方案中的需求安排，制定了相应的工作计划，如果对任务规划进行大规模调整，必定会影响用户的下一步工作和决策，导致较大的损失，故应该将这种影响降到最低。

（3）快速调整原则

在实际应用中，在通信任务或卫星资源发生变化时，需要对初始调度方案进行动态调整，对于方案调整的时间性要求较高，需要在原有方案基础上进行快速调整，以快速满足资源与任务变化的需求。

四、结语

通信卫星调度问题属于航天领域亟需解决的重点问题之一，对于该问题的研究具有重要意义，能够有效提高卫星通信系统的服务保障能力和资源利用效率。通过对通信卫星动态调度问题的研究，利用优化算法生成动态调度方案，可以为实际卫星通信规划方案提供参考依据，为解决星上通信资源和任务需求的供需矛盾提供技术支持。