陈彦斌 高越

【摘要】    本文针对我国测控接收一体化站网调度业务和资源现状，开展了兼顾精确任务和模糊需求的任务需求建模;采用基于贪婪策略的启发式算法，以最大化安排重要任务、分配最合适弧段为目标，实现任务冲突消解、应急任务常态化插入的资源调度能力;最后通过仿真试验证明了该方法的有效性。

【关键字】    遥感卫星    资源调度    测控接收一体化

一、引言

航天站网资源作为航天系统的重要组成部分，承担着对航天器的跟踪测量、监视控制和上下行信息交换等任务。随着多年来的我国站网基础设施建设以及应用场景的不断丰富，长管需求与应急需求并存、测控任务与接收任务并存、状态各异的卫星和站网设备并存，使得站网资源承担的任务类型和复杂性不断增加、冲突日趋严重。鉴于这些现实的情况，迫切需要研究高效实用的调度系统，充分发挥站网资源的服务效能。

世界各航天大国在该领域均取得了一定程度的研究成果[1-5]并建立了各自的业务系统。为适应国内应用实际情况，杨永安等[6]确定了测控弧段优先级及量化方法和冲突消解方法，已成功应用于陆基测控网的工程应用;金光[7]采用CSP模型描述测控调度中的約束条件;陶孙杰[8]设计了一种启发式算法与遗传算法组合的站网资源调度方法，以天线及配套链路为站网资源的调度粒度。

本文针对我国站网调度需求开展任务需求建模、约束条件梳理、优化目标设计，采用基于贪婪策略的启发式算法，设计具备前瞻冲突消解、满足应急任务常态化插入的贪婪规则，最后通过仿真试验证明了该方法的有效性。

二、问题建模

卫星测控接收资源调度问题包含了复杂的约束关系、不确定性、优先级关系，本文结合测控接收特点对任务、优化目标进行建模。

2.1任务需求建模

为了支持指定资源和模糊需求两种资源申请方式，建立了如下的8元组任务需求模型：

t={TaskId，SatId，Type，TStart，TEnd，Station，UserPref，TPri}

其中，t：任务需求;TaskId：任务编号;SatId：卫星代号;Type：任务类型，如接收、测控、一体化;TStart：任务最早开始时刻;TEnd：任务有效期结束时刻;Station：可用的站列表;UserPref：用户的偏好，包括任务来源、弧段数量偏好、时长偏好、时效性偏好、设备偏好、弧段间隔等;TPri：任务的重要程度。

2.2约束条件分析

调度过程中主要考虑如下几种约束条件：

（1）能力约束：根据资源能力进行星站匹配;

（2）可见性约束：星站在任务有效时段内物理可见;

（3）状态约束：只有空闲状态的弧段可以使用;

（4）时长约束：弧段长度应不小于本次任务最短时长要求;

（5）关联约束检查：多个弧段的总时长不小于最短任务时间;两个弧段的时间间隔应满足最大/小任务间隔;测控任务不能在数传任务之后;

（6）资源独占约束：一个波束、一条链路、一个通道同一时刻只能给一颗卫星使用;

（7）任务间隔约束：同一套设备相邻任务间隔应大于最短任务切换时间。

2.3优化目标设计

在构造目标函数时，针对多星测控接收问题提出的优化目标包括：成功执行的任务数目最大化、成功执行的任务加权优先级最大化、任务的弧段质量最高等。对于任务列表T中的每个任务t，本文在此基础上定义目标函数为：

Max{∑t∈T  F（t）×P（t）×S（t）}

其中，F（t）表示任务是否可以被安排，任务优先度P（t）表示了任务的重要程度，需求满足度S（t）表示该任务是否被安排了最合适的弧段。

在计算P（t）时，采用德尔菲法并根据实际工程经验[6]确定每个任务的优先级，优先级原则：优先响应重大、应急任务;上行任务优先于无上行的任务;有关联关系的任务优先于无关联的任务;可用弧段少的任务优先于可用弧段多的任务。

在计算S（t）时，根据实际工程经验确定每个弧段wti对任务t的满足度，并综合考虑如下原则：用户推荐设备、时长长的弧段、时间早的弧段满足度加分。

三、问题求解

本文采用基于贪婪策略的启发式算法完成求解。贪婪算法是一种解决最优化问题的近似方法，对于一些大规模或涉及复杂约束的任务规划问题，其计算速度较快 [10]。

3.1贪婪准则设计

该算法的关键在于贪婪准则的设定，即在求解的每一步依据何种标准对变量进行赋值。具体规则如下：

（1）弧段选用规则：优选非保留圈次弧段（保留中继资源、出境圈弧段）;根据前瞻策略，优先选用与其它弧段冲突少的弧段;根据用户偏好，优选用户指定的设备、跟踪质量较好的弧段。

（2）冲突消解规则：排除优先级低的任务占用的弧段;排除可用弧段多的任务占用的弧段;对于弧段被排除的任务，重新加入队列编排。

（3）应急响应规则：优选空闲弧段、保留弧段;被调整任务优先安排到原有站、原有圈次;限定调整深度。

3.2算法流程

根据每个任务的优先级，从高到低插入到已有的任务队列，在资源约束、任务约束等条件都满足的条件下为所有任务选择合适的弧段：

Step1：循环从任务队列中取出未分配、优先级最高的需求;

Step2：从可用弧段列表中选择满足度最高的空闲弧段作为预分配结果;

Step3：查看该设备两个相邻弧段之间间隔是否满足任务切换时间;

Step4：如果被占用则按下列规则消解冲突：排除优先级低的任务占用的弧段，排除可用弧段多的任务占用的弧段，将弧段被排除的任务重新加入任务队列;

Step5：对于冲突的任务，将冲突次数加1，标记被抢占的弧段;

Step6：当任务没有可用弧段可用时，标记任务分配失败，并记录失败原因;

Step7：当所有任务都处理完毕时，规划完成。

四、试验结果与分析

为了验证本文算法的性能，搭建试验环境进行测试。试验环境使用Win7 64bit系统、Oracle 12c数据库，CPU为3.6GHz四核，内存16GB，采用C++语言实现。试验中使用仿真卫星300颗，仿真测控接收设备100套，中继星10颗。算法性能对比如表1所示。

由试验结果可见，本文方法能夠快速完成多星、多站、多需求的天地测控接收资源一体化调度问题，并且在大量任务安排后支持快速滚动插入应急任务。

五、结论

本文从我国航天站网管理业务需求和资源实际情况出发，提出了一种遥感卫星测控接收资源一体化调度方法，先后完成了任务需求建模、约束条件分析、优化目标设计，最后采用基于贪婪策略的启发式算法，以最大化安排重要任务、分配最合适弧段为目标完成问题求解。与其它方法相比，本文方法以工程应用为目的，支持地基单天线、中继星、多波束设备，支持精确任务和模糊需求，支持快速调度计算和应急任务滚动插入，并通过仿真实例验证了模型和算法的有效性。由于站网资源调度问题是一件非常复杂的系统工程，该项工作还需在实践应用中不断完善。

参  考  文  献

[1] CASTAING J. Scheduling downloads for multi-satellite，multi-ground station missions[C]. //Proceedings of 28thAnnual AIAA/ USU Conference on Small Satellites. Utah，USA：AIAA，2014：1-12.

[2] SPANGELO S，CUTLER J，GILSON K，et al. Optimization-based scheduling for the single-satellite，multi-groundstation communication problem[J]. Computers & OperationsResearch，2015，57（C）：1-16.

[3] 唐旻.卫星系统数传与测控服务策略研究[D]，国防科学技术大学研究生院硕士论文，2013.11.

[4] Burrowbridge. Optimal Allocation of Satellite Network Resources[D]. in Ph.D Thesis.1999， Virginia Tech： Virginia.

[5] Edwards B L， Israel D， Wilson K E， et al. An Optical CommunicationsPathfinder for the Next Generation Tracking and Data Relay Satellite[C].International Conference on Space Operations， Pasadena， USA， 2015.

[6] 杨永安，樊恒海，冯祖仁等.一种基于 ES 法的卫星测控资源调度仿真及实现[J].系统仿真学报，2005，17（4）：982—985.