一种测控数传一体化站网资源调度算法*

陶孙杰，宋 竹

(中国西南电子技术研究所，成都610036)

1 引 言

随着在轨卫星数量的增加、卫星能力的提升，为卫星提供数传、测控服务的地面资源也越来越紧张，对于同一套地面站天线及配套设备，同一时刻该地面资源仅能为一颗卫星提供服务，当多颗卫星的过境时间窗口存在交叉时，该资源即存在资源使用冲突问题。因此，如何合理有效地为用户卫星任务分配地面站网资源，在满足卫星测控数传需求的情况下，最大化地发挥地面站网资源使用效益，是站网资源调度的首要关注点。

现有的大部分站网资源调度都是根据不同任务类型(测控、数传)单独进行规划，不符合地面站网资源测控数传一体化的发展方向。因此，设计具备在站网资源调度中考虑不同任务类型，同时尽可能最大化满足各用户需求，针对实际应用的多星多站多任务站网资源调度算法，是当前站网资源调度规划亟待解决的问题。

近年来，国内外学者针对卫星和地面资源调度开展了大量工作并取得丰硕的研究成果[1-10]。但是，现有的研究都聚焦于单一测控任务或单一数传任务的资源调度，未考虑未来测控数传一体化卫星任务规划和地面资源调度中测控需求和数传需求的差异性。同时，现有的理论研究虽然较为深入，但对于实际应用中用户常规使用约束和使用要求未进行充分考虑和针对性设计，使得研究成果无法直接进行工程应用。因此，本文从实际应用出发，针对测控数传一体化的用户需求及任务类型特点，对约束分析、问题建模、算法设计等方面进行研究。

2 站网资源调度问题描述

站网资源调度可以理解为为用户的站网资源使用申请分配地面站资源以及资源的使用时间。在测控数传一体化规划要求下，站网资源调度需要为测控、数传任务进行统一资源调度，需要支持不同的卫星任务类型，具备多星多天线1～7天资源调度的能力。

为了切实满足工程和实际应用需求，站网资源调度算法的研究需要考虑以下内容：

(1)需求与任务类型。支持用户指定卫星进出站时间的指定圈次模式以及用户指定时间范围与任务总时长的指定时长模式。其中指定圈次模式需要用户指定该弧段的任务类型，而指定时长模式需要用户分别指定测控、数传任务的需求时长。

(2)各类约束与优先原则。调度算法必须满足所有客观约束条件，同时尽量满足用户的主观优先原则或使用习惯。

(3)调度规模与调度性能。在一定调度规模下，调度算法必须在要求的时间内生成有效的调度方案。

(4)目标函数与结果评估。目标函数应体现分配方案对需求的满足程度及其他用户关注的指标。

由于站网资源种类繁多，性能各异，为了聚焦实际应用，本文的研究内容适用的对象有具备配套链路(变频器、解调器)及记录设备的常规抛物面天线接收站、测控站或接收测控一体化站，包括固定站和机动站。同时，本文的研究内容亦可对其他类型测控数传资源调度提供参考。

站网资源调度的约束与需求可以分为客观约束和主观要求两类。

站网资源调度主要关注地面资源的使用约束，包括规划时间约束、可达性约束、任务切换时间约束、任务能力匹配约束、地面站资源冲突约束、任务优先级约束、遥测任务约束、数传任务约束、最小可用弧段约束和弧段完整性约束。

在实际应用中，除了上述地面资源约束外，还需考虑星上载荷的约束，例如连续工作时长、开关机时间、卫星天线切换时间等约束。

主观要求包括任务需求要求、资源使用负载均衡要求、弧段能力要求和卫星任务均衡性要求。

3 问题建模

站网调度问题的特性在于调度过程中必须满足的所有客观约束和尽可能满足的所有主观使用要求，使得站网调度问题的解空间不具有连续性。因此，现有的通用算法不能直接用于这类解空间离散问题的寻优，需要针对所有约束条件建立约束满足模型解决解空间离散的问题。

3.1 约束满足模型

对于约束条件较多的站网调度问题，可以预见直接使用优化算法将导致算法的适配过于繁复。对于元启发式算法，需要将随机搜索范围适配至所有约束范围内，这将导致算法邻域结构设计的复杂化，甚至导致算法无法适配。以遗传算法为例，需要解决编码方式和编码对象。为保证种群中的下一代在遗传或变异后仍然满足模型中所有约束条件，需要设计对应的遗传算法编码方式和编码对象，因此优化算法的适配需要首先建立约束满足模型。通过建立约束满足模型，可以使得算法的搜索区域永远位于问题的解空间内，从而使得优化算法的适配成为可能。

约束满足模型根据所有需求与约束条件，设计多种启发式规则，建立了以弧段处理顺序为驱动的确定性启发式算法。通过启发式规则，算法的搜索空间被限制在站网调度问题的解空间内，对于确定的弧段的处理顺序，通过启发式算法可以得到确定的结果和目标函数；通过改变弧段的处理顺序，实现站网调度问题的全局搜索。

3.2 邻域结构设计

邻域构建直接决定了算法的搜索效率，本算法的邻域设计结构参考了经典旅行商问题(Traveling Salesman Problem，TSP)的常用邻域结构设计。TSP问题和寻找最优弧段处理顺序问题具有一定程度的相似性。TSP问题是赋权汉密尔顿(Hamiltonian)回路最小化问题(回到起点)，寻找最优弧段处理顺序问题可以抽象为赋权汉密尔顿路径最小化问题(无需回到起点)。TSP问题求解的是最优路径，在n个节点的集合中，选择一条经过每个节点各一次，最终再回到起点的路径，要求路线的总距离或开销最小。对于多星多站调度问题也可以抽象成类似的问题：卫星的弧段组成一个序列，寻找序列的最佳排序方式(无需回到起点)使得算法在该弧段处理顺序下得到的调度方案在满足约束的条件下目标函数最优。

在TSP问题中，任意两点的距离或开销是一定的，不会因为经过某节点的不同次序使得该节点与另一节点的距离或开销改变。该问题的领域结构通常采用交换序列中两节点顺序的方式进行领域搜索。

在站网资源调度问题中，卫星的某一弧段一旦被选定，可能会对其他卫星的弧段可用性造成影响，该影响的结果可能使得受影响的弧段不可用或弧段因冲突消解改变了长度。对于某一颗卫星，寻找其弧段的最优排列顺序和TSP问题相似，但对于多星来讲，卫星的处理顺序同样可能对每颗卫星的弧段造成影响。多星多站调度问题可以看作是一个两层的赋权汉密尔顿路径最小化问题：一层是卫星处理序列，一层是各卫星的弧段处理序列。

根据站网资源调度的需求，用户的站网资源使用申请分为应急、重要、普通三类，其中重要和普通类站网资源使用申请属于常规任务申请，需要通过算法为其分配使用方案。因此在邻域设计上，本文根据任务的优先程度，依据任务优先级、卫星优先级固化逻辑上的卫星处理序列。仅针对各卫星的弧段处理序列设计邻域交换模式，以改变某卫星的弧段排序方式实现邻域交换。卫星序列层次结构示意如图1所示。改变卫星弧段排序的方式可以采用序列交换、多点随机排序、交叉排序等方式。

图1 卫星序列层次结构Fig.1 Hierarchy of satellites’ sequence

根据优先级约束的要求，将同一颗卫星优先级为重要的弧段和优先级为普通的弧段视为两颗逻辑卫星弧段进行排序，使得优先级为重要的弧段优先进行分配。对于相同优先级的内部用户卫星和外部商用卫星，卫星处理序列中内部用户卫星在外部商用卫星前列，使得同优先级情况下内部用户卫星任务优先进行分配。

在每个逻辑卫星弧段排序中，用户的站网资源使用申请包括指定圈次模式和指定时长模式。其中指定时长模式下弧段的分配由资源调度算法决定，而指定圈次模式下，用户已对确定的弧段提出申请，因此可以认为同优先级下，指定圈次模式的申请应优先进行分配。同时根据弧段能力要求，具备全任务能力的弧段优先于只具备部分能力的弧段分配。每个逻辑卫星弧段排序如图2所示。

图2 弧段序列和邻域结构Fig.2 Structure of arcs’ sequence and neighborhoods

3.3 模型表示

T：资源调度时间范围T=[TS,TE]，仅对TS至TE时间范围内的可用资源和弧段进行调度。

S：过境卫星集合S={s1,s2,…,sn}。

A：地面站天线集合A={a1,a2,…,am}。

W：地面站天线权重集合W={w1,w2,…,wm}。

R：站网资源使用需求集合R={r1,r2,…,rz}，对于集合R中的任意需求ri={ridi,sidi,rwi,rmi,tmi,Dtci,Ddti,Tsi,Tei}，其中ridi为需求id，sidi为申请卫星id，rwi为需求的权重，rmi为需求模式(指定时长/指定圈次模式)，tmi为需求的任务类型(测控/数传/测控+数传)，Dtci为需求测控任务时长，Ddti为需求数传任务时长，Tsi和Tei分别为需求任务开始时间和结束时间。

Td：任务切换时间，即地面站资源在两个相邻任务间需要的常量任务切换准备时间。

Tl：弧段长度阈值，低于阈值的弧段不进行任务分配。

站网资源调度模型需要满足的主要地面资源约束条件可以表示为

(1)

(2)

(3)

(4)

(5)

式(1)表示同一地面站天线两个相邻可用时段的间隔必须满足任务切换时间约束，且同一天线及配套设备不能同时对两颗及以上卫星执行任务；式(2)表示仅对调度时间范围内的资源进行规划；式(3)表示所有分配执行任务的弧段必须满足最小弧段长度约束；式(4)表示分配给测控或数传任务的弧段必须具备相应能力；式(5)表示执行数传任务时，该卫星不能同时执行其他数传任务。

3.4 目标函数

根据用户需求，本文目标函数用以评估调度方案对用户申请的满足程度以及对地面站资源分配均衡性的评价。由于地面资源调度的目的为尽量满足用户测控和数传任务的需求，因此仅在同样满足用户需求的情况下，比较两组调度方案的资源分配均衡性优劣才有意义。因此，目标函数设计为两部分：一是用户申请的满足程度，用整数位表示，综合考虑任务优先级、优先级权重、需求时长、分配时长，计算方案对所有申请的整体满足情况；二是资源负载均衡使用情况评估，用小数位表示，计算当前分配方案下对各地面资源的使用情况，依据地面站天线权重评估分配方案。

算法对于最大化目标函数F的定义如下：

max:F=f1(R)+f2(A)。

(6)

式中：f1(R)为需求满足程度，用以标识方案对需求的满足程度；f2(A)为资源使用情况评估，用以标识方案的负载均衡分配评价指标；R为用户的需求集合，需求数量为z，方案中分配给需求ri的测控任务总时长和数传任务总时长分别记为Ttci和Tdti。需求ri的满足率Pi为

(7)

需求ri的权重记为rwi,则需求满足程度f1(R)可由下式所得：

(8)

记地面站天线aj的分配时长为Taj，则

(9)

目标函数体现了对方案优劣程度的评估，方案对用户申请的满足程度(整数部分)决定了方案的优劣，在满足程度相同的情况下比较方案对地面资源的使用负载均衡情况(小数部分)。

4 算法设计

本文提出了一种组合式站网调度算法，算法由通用的遗传算法和本文提出的启发式站网调度算法组成，嵌套使用。其中启发式算法用于计算一个输入(卫星弧段序列，即弧段分配判断的先后顺序)下的调度方案、目标函数值，而智能算法则根据需求目标函数结果在卫星弧段的所有可能序列中寻找最优排序方式。

通过启发式站网调度算法，对于确定的卫星和弧段的处理顺序，得到确定的结果和目标函数；通过智能优化算法，搜索最优的卫星和弧段的处理顺序；同时，与算法无直接关联的数据处理在预处理部分解决。站网资源调度的简要流程图如图3所示。

图3 站网资源调度简要流程图Fig.3 Flow chart of ground-station resource scheduling

4.1 预处理

根据预处理工作的内容和工作顺序，分为三级预处理：需求及资源汇总预处理、可见窗口预处理以及弧段标注预处理。

需求及资源汇总预处理汇总所有用户需求，得到任务规划卫星集合、任务规划起止时间、优先级、需求类型和需求时长等信息，同时也汇总所有参与调度的资源信息，包括可用的地面站天线、天线能力信息、天线可用时段，最小可用弧段长度等信息。

可见窗口预处理根据卫星与各地面站天线的可见时间窗口，为每个弧段建立索引维护与该弧段在时间上有重叠的弧段，便于资源调度过程中弧段的冲突监测与消解。通过建立索引方式可避免资源调度冲突检测频繁的弧段遍历和判断，提高算法效率，且索引一次计算，多次使用。

弧段标注预处理在卫星弧段标注其连续升/降轨周期序号、弧段序号、对应的需求id，根据弧段对应地面站天线能力，标注测控任务能力和数传任务能力，供站网资源调度算法使用。

4.2 启发式算法

本文提出的启发式算法为基于贪心思想的确定性算法，计算一个卫星序列和一组卫星弧段序列输入下的目标函数值和结果。算法根据卫星序列依次选择卫星开始规划。依据弧段连续升/降轨周期序号，以周期为单位选择相同周期的弧段进行分配，以满足卫星任务的均衡性。在每个周期，按照该卫星的弧段序列，依次判断弧段对应的需求是否已满足，若不满足且弧段可分配时，分配弧段，并依据该弧段对应的测控或数传需求，决定是否对与该弧段时间交叉的弧段进行数传卫星弧段冲突消解。依次进行该周期内的弧段分配，直至满足该卫星任务均衡性要求。随后进入下一周期，以此类推。当该卫星所有周期均满足卫星任务均衡性要求后(或无弧段可分配)，整合所有该卫星未分配弧段，逐条进行分配，直至遍历完所有弧段。

完成一颗卫星的弧段分配后，按卫星序列进入下一颗卫星进行分配，以此类推，直至完成所有卫星任务分配。启发式算法流程如图4所示。

4.3 遗传算法

本文站网资源调度组合算法的步骤如下：

Step1 初始化算法控制参数，根据预处理输入的卫星序列，随机生成种群数量个卫星弧段序列，随机仅限于弧段邻域交换范围内。

Step2 对当前种群内每个个体(各卫星弧段序列)调用启发式算法。

Step2.1 根据遗传算法输入的卫星序列，依次选择卫星；

Step2.6 判断周期内分配弧段数是否满足卫星任务均衡性要求，不满足则选择待处理队列中下一弧段，进入Step 2.3；满足则进入Step 2.2；

Step2.7 清空待处理队列，汇总该卫星弧段序列中所有未分配弧段并顺序加入待处理队列，顺序选择队列中弧段进行调度分配，直至完成该卫星所有弧段的分配，进入Step 2.1；

Step2.8 完成所有卫星的弧段分配后，输出调度方案与目标函数。

Step3 将适应度最高的个体作为精英解，直接进入下一代种群。

Step4 通过轮盘赌方式依次选择个体进入候选解。

Step5 按照交叉概率进行交叉操作，得交叉后的所有候选解。

Step6 根据变异概率对候选个体进行变异操作，与精英解组成下一代种群，种群代数+1。

Step7 判断种群代数是否满足终止条件，满足则进入Step 8，否则进入Step 2。

Step8 输出当代种群最优方案和相应的目标函数值。

本文组合算法中，遗传算法为启发式算法的上层调用算法，为启发式算法提供输入。遗传算法根据弧段序列结构和邻域交换范围，在允许的卫星弧段排序方式中进行搜索，通过调用启发式算法得到一组卫星弧段排序的目标函数值，并通过交叉和变异的方法实现寻优。

遗传算法采用实数编码方式，以弧段排序序号为编码对象，以启发式算法输出的目标函数作为适应度函数，以轮盘赌方式作为选择算子，并使用精英策略将每一代中适应度最大的个体直接选择至下一代。在卫星弧段序列的每一个弧段邻域交换范围内，采用次序交叉[11](Order Crossover)作为交叉算子，对其分别进行交叉操作。算法采用单点置顶的方式实现变异，按照变异概率选择需要进行变异的个体，随机选择该个体的一个弧段序号，并将该序号置入其邻域交换范围中队列顶端。单点置顶变异示意图如图5所示。

图5 遗传算法单点置顶变异示意图Fig.5 Diagram of single gene mutation of GA

5 仿真验证

为了验证本文提出的测控数传一体化站网资源调度算法的性能，建立仿真模型进行验证。仿真验证环境为Win7 32位系统，CPU为Core i3-4160，3.60 GHz双核，4 GB RAM，仿真工具为Matlab R2009a。

算法设置种群个体数目为30，交叉概率为0.8，变异概率为0.1，遗传算法终止条件为进化30代。设置任务切换时间Td=240 s，弧段长度阈值Tl=180 s。

本文以真实卫星轨道为基础，设计了10颗存在不同程度冲突的卫星轨道参数用于仿真验证，通过STK计算所有卫星一周内的过境弧段，对每颗卫星的需求设置为指定时长模式，每个需求要求全能力弧段总时长10 000 s。

在不同的场景下，站网资源调度的规模如图6所示。

图6 弧段数量与应用场景的关系Fig.6 The relationship between the number of arcs and application scenarios

从图6可以看出，弧段数量，即资源调度的问题规模，随卫星及天线数量的增加呈线性增长，因此需要评估实际应用中问题规模对算法性能的影响。经过50种卫星-天线数量组合，各取3次仿真时间均值，得到不同场景下，本文启发式算法的运算性能曲线，如图7所示。可以看出，在10星10天线7天约2 800弧段的仿真场景下，启发式算法的时间消耗在当前仿真环境下仍处于可接受范围内。

图7 启发式算法运行时间与应用场景的关系Fig.7 The relationship between time consumptions of the heuristic algorithm and application scenarios

由于实际应用中通常以一天为规划时间范围，因此本文使用6组场景一天的卫星过境弧段验证本文的测控数传一体化站网资源调度算法效果。测控数传一体化站网资源调度算法为遗传算法与本文启发式算法的组合使用,对比算法选用本文的启发式算法，该算法核心为贪婪算法，且该算法针对用户需求进行了针对性设计了启发式规则，因此调度效果要优于常规的基于优先级的贪婪算法。算法性能对比如表1所示。

表1 算法性能对比Tab.1 Performance comparison between proposed algorithm and the heuristic algorithm

以表中分配弧段数量与弧段总数量的比值为调度成功率，对比6种场景下两种算法的调度结果，使用本文的组合式算法调度成功率较启发式算法平均提高了22.3%，目标函数值平均提高了11.8%。

可以看出，本文的启发式算法与遗传算法的组合使用在各仿真场景下，均能有效提高需求的满足程度和设备的负载均衡要求，其中4个场景的分配方案可完全满足用户需求。从弧段的分配数量也可看出，对比传统的贪婪算法，本文的测控数传一体化站网资源调度算法可有效提高资源调度成功率。

6 结 论

本文针对未来测控和数传任务统一进行站网资源调度的发展趋势，提出了一种测控数传一体化的站网资源调度算法。算法针对测控数传一体化实际应用需求，以天线及配套链路为站网资源的调度粒度，建立了约束满足模型并设计了相应的启发式算法，通过定义邻域结构并采用遗传算法和启发式算法组合使用的方法，在仿真实验中验证了本文算法的寻优能力。仿真结果显示，在多种仿真场景下，本文组合式算法可有效提高资源调度的成功率以及任务需求的满足程度。