静止轨道通信卫星资源调度模型与算法研究

刘文文，熊 伟，韩 驰，骆 骁

(1.航天工程大学 信息学院，北京 101416；2.中国人民解放军32039部队，北京 102300)

0 引言

静止轨道通信卫星具有覆盖面大、性能稳定可靠、机动灵活、不受地理条件限制和远距离通信成本低等优点，在国际通信、国内通信、军事通信、移动通信和广播电视等领域发挥了重要的作用。

近年来，国家出台多项政策措施鼓励推动卫星在各行业的规模化应用、商业化服务及国际化拓展，行业面临重大的发展机遇及挑战。面对多网系、多任务，且卫星通信资源有限的现实情况，采用卫星资源调度方法来分配资源成为解决任务与资源之间矛盾的主要方式[1-2]。

在静止轨道通信卫星调度研究的过程中，常用的调度模型包括数学规划模型、约束满足模型、图论模型和车辆调度模型等[3-6]。数学规划模型求解通信卫星资源调度问题时，会简化变量之间的关系，忽略问题的非线性约束，采用的精确求解算法只适用于小规模的调度。图论模型形式简单，理论基础完善，可以在合理的时间内求得卫星资源调度问题的解，但由于卫星系统约束繁多，如何将所有约束恰当地表征到图中还是一个较难的问题，其使用具有较大的局限性。约束满足模型结构层次清晰，能够从变量值域、决策变量和约束条件为切入点对卫星资源调度问题展开描述，能够对一些难以用数学语言描述的约束进行描述，适用于较大规模调度问题，应用广泛。

目前的研究在求解静止轨道卫星资源调度问题时，为方便调度模型建立，会简化调度场景，有倾向性地建立约束条件，不同文章考虑的模型目标和约束存在差异，且不全面。根据已有的模型，结合静止轨道卫星资源调度的特点，建立资源调度基础框架，系统全面地梳理调度问题存在的目标和约束条件，构建一种静止轨道卫星资源调度基础模型，为该问题的研究提供统一的范式，在为研究新的调度场景提供支撑的同时，提供问题求解性能横向比较的可能。

本文从静止轨道卫星资源调度问题的根本出发，综合考虑调度过程中涉及的各项因素，建立静止轨道通信卫星资源调度的基础模型，形成问题求解的完整框架，并结合智能优化算法提高框架的求解效果。

1 静止轨道通信卫星资源调度分析

静止轨道通信卫星资源调度，从用户的角度，是用户需要组网通信时，向卫星资源管理中心提交任务申请，卫星资源管理中心根据任务需求为其分配符合要求的卫星资源；从卫星资源管理中心的角度，资源调度首先要梳理现有系统的资源池，整理可用资源列表，其次面对多任务申请，需要对所有任务需求进行统一梳理、系统的分析，最后选择合适的调度模型和算法进行求解，形成调度方案，合理地为任务分配资源，同时保证卫星资源使用的高效性和可沿用性。具体的调度流程如图1所示。

图1 通信卫星资源调度流程Fig.1 Communication satellite resource scheduling process

随着通信卫星业务应用不断拓展，任务数量及任务对资源的需求量随之增加，出现卫星资源紧张甚至不足的情况，增加卫星资源管理中心资源分配的难度和复杂度，形成了静止轨道通信卫星资源调度问题。但无论调度场景如何变化，任务需求如何多样，静止轨道通信卫星资源调度最根本的问题是任务之间的冲突及任务与卫星资源之间的矛盾。因此，求解静止轨道通信卫星资源调度问题从这个根本问题出发，系统梳理卫星资源、任务需求及调度过程中的约束，通过建立规范化、科学的基础框架结构，可以应对未来日趋复杂的调度场景，为卫星资源管理中心提供通用求解的手段。

2 通信卫星资源调度框架的构建

根据静止轨道通信卫星资源调度的过程，形成通信卫星资源调度架构，如图2所示，架构主要包括资源管理、任务管理、资源调度和应用4个部分。

图2 通信卫星资源调度架构Fig.2 Communication satellite resource scheduling architecture

2.1 资源管理

通信卫星资源是调度的对象，是系统分配的基础。通信卫星资源主要分为硬件资源和软资源。硬件资源是卫星的载荷资源，主要包括卫星、天线和转发器等；软资源为卫星的时间、频率和功率等，如图3所示。

图3 通信卫星载荷Fig.3 Communication satellite payloads

硬件资源是软资源的支撑，也是软资源的约束。通信天线发射的电磁波在地球表面形成波束，形成了卫星的覆盖范围，也约束了使用该天线的转发器内频率资源的使用范围，只有在波束的覆盖区域内才能使用其频率进行通信。根据移动性，波束可以分为固定波束和可移动波束，固定波束的覆盖范围固定不变，可移动波束在其移动范围内可以根据任务需要调整覆盖区域，更加灵活。转发器或者通道是卫星频率划分的最小单元，约束了频率可连续带宽及功率大小，其频段及带宽与任务所需频段及带宽的匹配，也是任务是否被执行的关键。转发器可以分为透明转发器和处理转发器，透明转发器主要实现对信号的放大功能，处理转发器可以对信号进行调制解调或者多址方式再处理。目前，对通信卫星资源调度的研究中，卫星的资源模型较为简单，波束以固定波束为主，转发器主要以透明转发器为主。

资源管理主要维护资源池，一是将卫星资源规范化存储；二是对资源进行监视更新，任务结束后，将其使用资源收回，及时发现干扰或者载荷故障，更新资源池，确保卫星资源的可用性。

2.2 任务管理

任务申请来自用户对于组网通信的需求，用户根据自己的任务场景提出的主要需求包括任务基本信息和资源需求信息两方面。

① 任务基本信息：主要用于任务识别，即任务的身份证，包括任务名称、任务发起者和任务类型等信息。

② 资源需求信息：最基础的内容包括任务时间、任务范围、需求频段及带宽，是实现任务资源匹配的基本条件。任务时间为任务开始时间和结束时间；任务范围是任务过程中任务活动区域；需求频率资源包括频段和带宽2部分，且带宽需要连续。

任务管理主要是对任务需求信息处理及更新。将任务的需求申请处理为资源调度模块的输入格式，出现新的任务申请或任务需求变动时，对任务集进行更新，还可以根据任务的重要程度设置任务优先级，用于辅助资源调度的决策。

2.3 资源调度

资源调度主要包括调度模型和调度算法2个模块。调度模型是资源调度的重要基础，决定了场景的描述方式、问题的复杂程度，以及影响调度算法的选择。调度算法是求解优化调度模型结果的方法，实现调度问题的求解，形成调度方案。

2.3.1 资源调度模型

通信卫星资源调度求解过程中，问题建模是首要步骤，也是关键步骤。建立卫星通信调度模型主要考虑卫星资源调度的场景，根据场景设置调度目标，构建约束条件。从调度场景角度出发可以分为静态调度模型和动态调度模型。

(1) 静态调度模型

静态调度是指在资源调度时，卫星资源和用户任务需求是确定的，调度过程中无已规划任务或新的资源调度，不影响已有规划任务的调度，此时可建立静态调度模型。在通信卫星静态调度问题中，主要研究如何分配通信卫星处理任务的时间资源和频率资源，最大化地满足用户的任务请求，不考虑任何扰动因素。

建立常见静态调度的基本数学模型如下:

调度目标

(1)

约束条件

TDi∈D,

(2)

Tb≤tbi,tei≤Te,

(3)

TFi∈F,

(4)

bi≤B,

(5)

(6)

(7)

·调度目标

常见调度目标还有以下几种：

① 任务调度数量最大化f2：当任务需求总资源超过卫星资源数量，或任务之间冲突较大时，导致部分任务无法获取资源，需以最大化任务调度数量为目标，进行舍取。

② 卫星资源利用率最大化f3：卫星资源紧张的情况下，优先考虑资源的分配，充分提高资源的利用率。

③ 资源使用均衡度f4：任务集中分配在某段资源上，增加了该段资源故障扰动带来的风险。将任务均衡地分配到各个卫星资源段中，可以降低故障造成的影响，减轻卫星载荷的负载压力。

④ 资源破碎度最小化f5：在任务与任务之间会产生空余的频率资源段，如果空余的频段较宽，会造成资源的浪费，所以在调度的过程中要尽量减小空闲的数量，在避免不了时减小其带宽，使资源段相对完整，减少资源的浪费，有利于后续任务的调度。

该数学模型中，设置了一个调度目标，可以根据实际需要增加目标数量，建立多目标优化模型。

·约束条件

式(2)是覆盖范围约束：TDi为任务i的活动范围；D为卫星资源的覆盖范围，要求任务区域必须在转发器覆盖范围内。

式(3)是时间约束：tbi,tei分别为任务i的开始和结束时间；Tb，Te分别为资源的可用开始时间和结束时间，要求任务的执行时间必须在资源可用时间范围内。

式(4)是频段约束：TFi为任务i的申请频段；F为资源频段，要求任务所需频段必须与转发器频段一致。

式(5)是带宽约束：bi为任务i的需求带宽;B为资源提供带宽，要求卫星资源的可用带宽大于或者等于任务需求带宽，才能提供服务。

式(6)是任务执行次数的约束:yi,j=1表示第i个任务使用第j个资源;yi,j=0表示第i个任务不使用第j个资源;m为资源的数量。式(6)表示每个任务在其可用资源中仅选取一个资源，只执行一次，且执行过程不能中断。

式(7)是资源使用次数的约束：hj,i=1表示第j个资源被第i个任务使用；yi,j=0表示第j个资源未被第i个任务使用，n为任务数量。式(7)表示同一资源在同一时刻不可以被多任务共同使用。

以上约束为静止轨道通信卫星资源分配的基础约束，在具体场景的运用中，可以根据实际情况添加约束。

静态调度的优点是调度过程、算法简单，但是静态调度灵活性不强，对于需要提前长时间进行部署的任务不友好，对用户来讲增加了资源调度的不确定性。

(2) 动态调度模型

动态调度是指在调度方案的执行过程中，出现突发情况影响任务的执行，需要即刻在原有调度方案的基础上进行资源分配的调整，此时需根据扰动因素建立动态调度模型，应对系统突发扰动事件。动态扰动主要包括卫星设备损坏或者干扰所导致的卫星资源变化、任务的突然撤销或者新任务的增加所导致的任务数量的变化、任务持续时间变动等[7-11]。

建立动态调度数学模型如下：

调度目标

(8)

max(αnd+βnc)。

(9)

约束条件

TDi∈D，

(10)

Tb≤tbi,tei≤Te，

(11)

TFi∈F，

(12)

bi≤B，

(13)

(14)

(15)

·动态调度目标

根据动态扰动因素规划新的调度方案时，常考虑与原有初始调度方案的变更情况，即在最大化地满足用户的任务请求等性能目标的同时，要保证新方案与初始方案之间变化最小，即新方案与初始方案之间相似性最大。故增加了目标式(9)：nd表示初始方案到新方案任务分配资源不变的任务总数；nc表示初始方案到新方案任务分配资源变动的任务总数；α表示分配资源不变任务的权重；β表示资源调整任务的权重。

·约束分析

① 任务扰动

任务时间、任务需求带宽的改变主要是任务与转发器之间可用资源和时间窗口约束的变化，更新约束式(11)和(13)。新增任务扰动主要增加任务的数量，更新n的数值，增加TD,tb,te,TF,b集合内参数值。

② 资源扰动因素

在用资源受扰和卫星设备故障造成的影响都是资源故障，其主要引起资源集的变化，从而导致卫星资源的时间、可用资源集的变化，故需要更新集合Tb，Te，F，B。

动态调度方法更加灵活，根据通信卫星资源变动和任务新增需求，在相对减小对原有方案影响的基础上，近似于实时调整调度，更加符合实际需求。

2.3.2 调度算法

调度算法是求解调度问题的关键，目前，精确算法、启发式算法等一系列调度算法被应用于通信卫星资源调度问题中，表现出较好的优化效果。

精确算法包括线性规划、动态规划、整数规划和分支定界法等运筹学中的传统算法，需要遍历所有解空间，能够解出全局最优解，其算法计算复杂性一般很大，只适合于求解小规模问题，在应用于复杂、困难的优化问题时有较大的局限性[12-13]。面对现在大规模、复杂度高的卫星资源调度，精确算法并不适用，但是其在模型建立、目标函数设计等方面有一定的指导意义。

启发式算法是设计在解空间搜索的一类算法，在可接受的计算成本内去搜寻最好的解，但不能保证所得解是最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。启发式算法的求解结果可能千变万化，选择合适的初始参数对启发式算法非常重要，一般需要根据问题本身的特点进行适应性改造，如常采用的模拟退火算法(SA)、禁忌搜索、遗传算法(GA)、蚁群算法(ACO)、粒子群算法(PSO)和人工蜂群(ABC)等，在卫星资源调度问题[14-16]中都有成功的应用，但其本身也存在一些不足。例如，局部搜索能力差、存在未成熟收敛等现象，从而导致算法的收敛性能差，需要很长时间才能找到最优解。为提高算法的搜索能力和提高算法的收敛速度，产生了众多改进型算法。王海波等[17]利用蚁群优化模拟退火算法进行天地测控资源联合调度。启发式算法之间进行适当结合，可以针对性地改善遗传算法自身存在的问题，形成算法性能上的互补，使问题优化的过程快速高效。

常见启发式算法的伪代码如下。

Algorithm Framework of Heuristic algorithmInput:task set T,Satellite resources set S,Satellite and mission mat-ching set DS,population size NP,maximum generation Gen,limit the number of improvements LimitOutput: the best solution1:Initialize all parameters2:P←Initial population generation (NP,T)3:Solution0 ←Satellite and mission match4:f←Calculate the fitness value of the initial population individual(NP)5:G_best ←Update the best solution6:forgen= 1 to GEN do7: foreach operator do8: Search for new individuals9:end10: L_best ←find the best individual11: If L_best>G_best then12: G_best=L_best;13: end14:end

面对日益复杂的大规模优化问题，尤其是多模态、高维、带约束和多目标优化问题，需要不断寻找性能更高的智能算法，例如超启发式算法、学习算法等，将其应用在通信卫星资源调度问题中，以获取更加令人满意的优化效果。

本文采用海洋捕食者算法(Marine Predators Algorithm,MPA)对资源调度问题进行求解。该算法是Faramarzi等[18]于2020年提出的一种新型元启发式优化算法，是受海洋生物中捕食者和猎物的行为启发，通过实验验证具有很高的寻优能力。

2.4 资源调度模式

卫星资源管理中心的调度模式主要以日常调度和应急调度为主。在日常调度中，用户会根据任务的开始时间提前较长时间进行资源申请，资源调度中心有足够的时间选择合适的时间点进行资源调度，并将调度方案中规划的任务资源按照时间节点下发给用户。应急调度常与动态调度模型相结合，用以应对原有调度方案执行过程中，出现新的紧急任务或卫星资源出现扰动等突发事件时，进行实时调度，需在第一时间将调度方案结果通知用户。

3 实例验证

基于上述通信卫星资源调度框架，结合MPA，进行通信卫星资源调度问题的仿真求解。

3.1 仿真场景

应用调度场景设计如下：假设有4个可用卫星资源，具体卫星资源信息如表1所示，在2021年7月16日00时，接收到日常任务申请40个，需进行资源调度操作。经整理，任务申请需求如表2所示。任务区域范围以经度、纬度为中心点，半径为r的圆形表示。任务优先级为1～5的随机整数，数值越小优先级越高。在设置任务开始时间和需求带宽时，增加了任务之间的冲突，以体现资源调度解决任务之间矛盾的有效性。

表1 卫星通信资源Tab.1 Satellite communication resources

表2 通信任务Tab.2 Communication task

3.2 建模求解

MPA是一种基于群体的方法，利用布朗运动(Brownian Motion)和莱维飞行(Lévy Flight)2种随机游走算子来进行搜索。莱维飞行的随机游走以小步碎走和间歇性大跳为主，步长较小，使算法能够有效且深入地搜索附近的邻域；间歇性大跳能使算法跳出局部，进行其他区域的搜索，但跳步较大，不能完全覆盖所有区域。布朗运动的步长服从正态分布，可以追踪和探索邻居的较远区域，但不能像莱维飞行策略精确和深入地搜索。MPA将莱维飞行的独特性和布朗运动的特性相结合，探索如何更全局/局部地探索和利用解空间。本文将MPA与静止轨道卫星资源调度相结合，在迭代后期，对莱维飞行和布朗运动的使用进行了调整改进，猎物种群前半部分采用布朗运动算子进行搜索；后半部分采用莱维飞行算子进行搜索，形成改进的MPA——IMPA，用以提高算法的求解质量，算法流程如图4所示。

图4 IMPA的流程Fig.4 IMPA process

采用IMPA对调度模型进行求解，图5为IMPA求解目标值的搜索过程，可以看出,IMPA以相对均匀的小步碎走和间歇性大跳的方式进行搜索，深入进行邻域搜索的同时避免陷入局部。

图5 IMPA运行结果Fig.5 IMPA operation result

采用ABC,MPA和改进后的IMPA同时对问题进行求解，迭代次数均设置为NP=500，种群数量为pop=100。为消除随机性的影响，将算法运行10次，以均值体现算法的求解性能，以方差表示算法的稳定性，对运行数据进行分析梳理如表3所示，将算法10次运行的收益值绘制成图，如图5所示。

表3 场景仿真计算结果Tab.3 Scene simulation calculation results

场景中，任务数量为40个，总收益为36。采用ABC，10次运行获得平均收益为30.90，占总收益的85.83%，平均执行任务32.2个，占总任务数的80.5%；使用MPA，10次运行获得平均收益为32.32，占总收益的89.78%，平均执行任务33.5个，占总任务数的82.5%；使用IMPA，10次运行获得平均收益为33.36，占总收益的92.67%，平均执行任务35个，占总任务数的87.5%。IMPA的平均收益值比ABC提高了8.9%，比MPA提升2.89%，任务数量平均增加2个左右。算法运行目标值分布如图6所示。由图6及方差值可以看出，IMPA更加稳定。

图6 算法运行目标值分布Fig.6 Distribution of target values for algorithm operation

4 结束语

静止轨道通信卫星资源调度的框架和调度过程较为简单，但是随着技术的发展，通信卫星载荷更加复杂，简单的透明转发器模型不能满足当前的需求；任务之间的关联关系逐渐呈现，简单的约束关系不能适应复杂的调度场景。因此需要根据调度框架，结合实际情况，建立更加复杂且贴近实际的调度模型，来更好地解决卫星资源与任务之间的矛盾。