刘建平, 李　晶, 张天骄

(西安卫星测控中心宇航动力学国家重点实验室, 陕西 西安 710043)



航天测控网调度的混合构造启发式算法

刘建平, 李晶, 张天骄

(西安卫星测控中心宇航动力学国家重点实验室, 陕西 西安 710043)

摘要：针对航天测控网调度问题,提出一种基于混合启发式的解构造算法。与其他构造启发式算法不同的是,本启发式算法充分利用了我国航天测控网调度需求的特点,包括优先级、任务之间时间间隔要求和一个需求包括多个相同任务要求等,综合考虑了任务局部和需求全局,融合最大可用窗口价值规则和最早可用窗口集规则。其优势在于通过动态选择构造启发式规则来提高求解质量。最后,通过仿真实验分析比较,该算法可以在不明显增加计算时间的基础上得到更高的初始解质量。

关键词：构造启发式; 航天测控网调度问题; 测控需求; 约束优化问题; 时间间隔

0引言

随着各航天大国对空间领域的高度重视,在轨卫星的日益增加造成测控资源的高度紧张,航天测控网调度问题研究成为航天工业领域运筹学研究热点之一[1]。航天测控网调度是航天测控网管理的核心任务,主要负责协调测控设备与在轨卫星(或即将发射卫星)之间的通信分配。航天测控网调度问题是指在测控资源有限的情况下,如何为测控任务分配合理的测控资源和时间,以最大化地满足所有测控需求[2]。在实际的航天测控网调度中,最终调度方案的形成一般分为3个阶段:第一阶段是初始解生成阶段,就是利用某种或多种构造启发式规则快速生成满足所有约束的无冲突初始分配结果;第二阶段是优化解生成阶段,就是利用某种局部搜索算法或迭代修复规则在初始解的基础上进行改进,通常是以一定计算代价来获得高质量的解;第三阶段是冲突消解阶段,主要采用与用户协商的机制进行冲突任务约束松弛,也最大化地满足各方需求的调度方案[3]。其中前两个阶段通常不需要人参与求解,因而往往合并为计算机自动调度阶段[4]。本文的研究主要针对计算机自动调度阶段的初始解生成。

航天测控网调度问题初始解生成算法一般包括两个决策问题,即任务的选择和可用窗口的选择。任务的选择一般都是基于任务优先级规则(如果任务具有事先确定的优先级)。而可用窗口的选择目前主要有4种规则:一种是可用窗口开始时间最早最先分配规则,称为“先到先服务”(first coming first serving,FCFS)或“先进先出”(first in first out,FIFO)策略,将基于测控需求和可见信息生成的测控任务所对应的时间窗口开始时间作为排序的标准,进行可用窗口的选择[5];一种是可用窗口冲突最少最先分配规则,称为“瓶颈避免”(bottleneck avoidance, BA),以冲突度来衡量每个可用的时间窗口,并以冲突度作为排序的标准,进行可用窗口的选择[6];一种是可用窗口灵活度最小最先分配规则,以某种灵活度指标来衡量每个可用的时间窗口,并以灵活度为排序的标准,进行可用窗口选择[7-8]。一种是可用窗口价值最大最先分配规则,以某种价值指标来综合衡量每个可用的时间窗口,并以价值为排序的标准,进行可用窗口选择[9-10]。

考虑到我国航天测控网调度需求特点,以上构造启发式算法很难适应单个测控需求多时间关联任务的表现形式,本文提出一种基于混合构造启发式规则的求解算法。该算法综合考虑任务局部和测控需求整体,能够在不明显增加计算时间的基础上得到更高质量初始解。本文结构如下:首先介绍当前常用的4种构造启发式算法,给出统一的算法流程;接着分析我国航天测控网的调度需求;基于我国航天测控网调度特点,给出了基于COP的问题表示,并对4种构造启发式算法进行适应性调整;然后提出基于混合构造启发式的多星测控资源调度求解算法;最后给出仿真试验。

14种构造启发式算法

前面提到了,4种构造启发式算法包括:基于可用窗口开始时间最早最先分配规则(FIFO)的构造启发式算法、基于可用窗口冲突最少最先分配规则(Min-Conflict)的构造启发式算法、基于可用窗口灵活度最小最先分配规则(Min-Flexibility)的构造启发式算法和基于可用窗口价值最大最先分配规则(Max-Value)的构造启发式算法。这4种构造启发式算法的一个共同特点就是利用可用窗口的排序准则来觉得任务和可用窗口的选择。其中前3种没有考虑任务优先级,第4种将任务优先级融入到可用窗口的价值指标中。图1给出了4种构造启发式算法统一的算法流程。

图1　4种构造启发式算法统一算法流程

首先根据测控需求和可见窗口信息生成可调度的可用窗口集合,并按照相应的构造启发式规则对所有可用窗口集中的所有元素进行排序;然后按照顺序先后对任务分配资源,将先分配资源的任务所确定的资源及占用时间作为后续任务调度时必须遵守的硬约束,更新可用窗口集中合中受影响任务的可用时间信息,同时更新被调度任务对应需求的满足程度;重复分配资源的步骤,当所有任务都已被操作(成功调度或由于冲突等原因调度失败)或所有卫星需求得到满足时算法终止。

2我国航天测控网调度需求分析

虽然已经有部分文献比较明确地描述了我国航天测控网调度需求[11-13],但是本文首次从与几个具有代表性的航天测控网调度需求对比的角度,来分析我国航天测控网调度需求的特点。有代表性的航天测控网调度需求分别是美国AFSCN[2]、ESA ESTRACK系统[14]、ESA GALILEO系统[15]和欧洲共享航天测控网络(academic ground station network , AGSN)[16]。各国航天测控网调度需求的不同主要体现在任务需求和优化目标的不同形式,本文这里主要从任务形式的不同来进行比较。

表1主要从7个方面进行比较,包括任务提交形式、任务执行时间、任务优先级、关联任务、任务间隔时间、任务可用窗口的升/降轨要求和任务冗余。从表1中可以清楚地看到我国航天测控网调度需求所具有的特点。这些特点大多数是因为我国航天测控网的几何布局造成的,主要是中国大陆境内测控站。

3基于COP的问题表示

将航天测控网调度问题描述为四元组,表示为

P=

(1)

式中，Reg表示所有卫星用户向测控网管中心提出的测控需求集合,包括具体的测控需求(指明了所用的设备和时间区间)、一般测控需求(日常管理的周期性需求),即Reg={r1,r2,…,rn}(ri表示第i个需求,n表示需求的数量)。参考文献[9],测控需求r可以表示为

r={No,Sat,p,deviceset,Orbit,

(Rn,Fn)/N,Last,Min,Max}

(2)

其中,No表示需求编号;Sat表示需求对应的卫星编号;p表示需求的优先级;deviceset表示可供完成此需求的测控设备集合,包括中继测控设备、设备偏好次序、最少设备次数等;Orbit表示轨道类型,包括低/中/高轨;(Rn,Fn)是针对低轨类型卫星来说,表示升轨次数和降轨次数;N是针对中高轨卫星来说,表示测控次数;Last表示一次测控最短持续时间要求;Min表示两次测控之间的最短测控间隔时间要求;Max表示两次测控之间的最长测控间隔时间要求。

Sce表示航天测控网资源调度场景,主要由一个调度周期内所有用于调度的可用时间窗口构成,该时间窗口是卫星与测控资源的可见弧段;即Sce=Sce1∨Sce2∨…∨Scen (Scei表示第i个测控需求率的所有可用弧段集合)。

表1　典型的航天测控网调度需求比较

C表示航天测控网资源调度问题所有约束集合,如卫星约束、资源约束、时间窗口约束、关系约束等。约束的具体形式可以参考文献[11],本文这里不再赘述。

由于zi=r(i,:)Xl,s+Ni (l{1,2,…,Nt}，s S)，Ni为QHN的第i个元素，此时βi(l,x)= ui(l,x)+ Ni，其中，ui(l,x)=r(i,:)Xl,s-r(i,:)X.在某一时刻，接收端信道状态信息已知时，信道传输矩阵H已知，发射向量固定，接收端检测时假设发端发射向量也是已知的，因此ui(l,x)可以近似看成一个常量.由于N服从高斯分布，可以推导出βi(l,x)也服从高斯分布，归一化为：

O表示优化目标,最大限度地满足航天测控网的测控需求。即

(3)

式中,p表示测控需求的优先级;d表示单个测控需求的任务满足率,例如某测控需求一天需要完成m个测控任务,则d∈{0,1/m,2/m,…,(m-1)/m,1};优化目标O表示整个航天测控网的测控需求满足率。

4构造启发式算法的适应性调整

为了使4种常用的构造启发式算法能够适应我国航天测控网调度需求,需要对这4种算法进行适应性调整。图2给出了调整后的统一算法流程,其中虚线框为适应性调整的部分。可以看到,整个流程在两个地方进行了适应性调整:一处是在构造启发式规则应用可用窗口之前,增加了基于优先级的任务选择模块,这主要是为了适应任务优先级的需求;另一处是在构造启发式规则应用可用窗口之后,增加了可用窗口的升/降轨和时间间隔要求的判断,这主要是为了适应任务的升/降轨需求和任务间隔时间要求。

另外,由于以上4种常用构造启发式规则都是从单任务角度进行逐个求解,而没有从任务所属的测控需求整体考虑。因此,为了适应以测控需求为表现形式的相同多任务提交形式,也就是一个测控需求时段内往往具有多个带有时间间隔要求的相同任务,本文提出了面向同一测控需求的最早可用窗口集优先分配规则(First-Set)。First-Set定义如下:假设一个测控需求具有m个具有时间间隔要求的相同任务,最短/最长时间间隔为Δmin/Δmax,其可见窗口集合为W。若存在同时满足这m个任务的可用时间窗口集合为AWm(AWm⊆W),则First-Set就是AWm中具有第一个任务可见窗口开始时间最早的集合;若AWm为空集,可以继续搜索同时满足m-1个任务的可用时间窗口集合AWm-1,依次类推。

图2　4种构造启发式算法调整后的统一算法流程

5基于混合构造启发式的求解算法

针对我国航天测控网调度需求特点,使构造启发式规则既能适应传统单任务提交形式又能适应单个测控需求多任务的表现形式,综合考虑任务局部和测控需求整体,本文这里提出了混合First-Set规则和Max-Value规则的构造启发式规则,缩写为First-Set & Max-Value。其中First-Set规则侧重于单个测控需求整体,而Max-Value侧重于单个任务。图3给出了求解算法流程。

与4种常见构造启发式算法的单一任务尺度不同,本算法混合了测控需求和任务两种不同尺度,且一个测控需求包括多个优先级相同或不同的任务。首先以优先级为准则依次选择测控需求,再以该测控需求内所包含的任务优先级为准则依次选择任务。Max-Value规则运行一次仅得到一个调度任务,而First-Set规则运行一次可以得到多个调度任务。当完成一个测控需求分配时,通过比较两者该测控需求满足率,以较大者产生的调度任务作为本测控需求的已调度任务。这样设计的优势在于,通过每一轮以测控需求满足率为指标动态选择构造启发式规则,以融合First-Set规则和Max-Value规则的优势,提高整个求解质量。当然,从算法复杂性来看,由于混合了两者规则,相对单一规则来说增加了计算成本,运行时间上应该是两个单一规则算法运行时间之和。

图3　混合构造启发式算法流程

6仿真实例与结果分析

6.1仿真场景

假设航天测控网具有5个地面站9套设备,分别位于喀什(2套)、佳木斯(2套)、三亚(2套)、渭南(2套)和青岛(1套),75颗在轨卫星(包括4颗中高轨卫星),其编号为1~75,每个卫星测控任务需求如表2所示。

表2　每个卫星测控任务需求

不失一般性,对于低轨卫星来说,可见时间窗口一般为满足任务最短持续时间要求的整个弧段;对于中高轨卫星来说,由于可见弧段时间一般较长,为了提高弧段利用率,对每个长可见弧段进行子弧段离散化处理,即每个子弧段时长为最短持续时间,时间间隔取1 min。仿真场景设计了3种不同规模的场景,分别是大、中和小规模场景,场景配置如表3所示。

6.2比较算法的设计

为了验证本文提出的混合构造启发式算法的有效性,这里考虑了本文第4节给出的基于FIFO规则启发式算法、基于Max-Value规则启发式算法和基于First-Set规则启发式算法。其中基于Max-Value规则启发式算法采用文献[10]的CHBR算法的弧段价值计算方法。这3种算法的选择具有一定的代表性:FIFO启发式反映在单个任务的可能开始时间上;Max-Value启发式反映在涵盖相邻任务时间间隔要求的单任务价值上;First-Set启发式则反映在具有多个时间关联任务的测控需求上。

表3　3种场景配置

6.3仿真结果比较分析

为了更加客观地反映各个算法的性能,这里以测控需求满足度来衡量算法求解质量,以计算时间来衡量算法计算成本。每个场景以需求优先级的不同生成200个算例,每个算例在1~10间随机生成所包含测控需求的优先级。而且,每个场景设计了两种时间间隔:一个最长时间间隔为8 h,一个最长时间间隔为10 h。表4是各算法在不同场景下的平均测控需求满足度,表5是各算法在不同场景下的平均计算时间。

从求解质量来看,First-Set & Max-Value启发式最好,Max-Value次之,其次First-Set,FIFO最差。随着最长时间间隔由10 h缩短为8 h,测控需求的时间间隔约束加强,虽然4个算法的求解质量都有所下降,但是相比较次优的Max-Value启发式,有两点发现:一是First-Set & Max-Value启发式的求解质量从2%提高到6%;二是First-Set启发式的求解质量逐步逼近Max-Value启发式。这两点发现实际上也反映了First-Set & Max-Value启发式综合考虑任务局部和测控需求整体的优势所在。

表4　各算法在不同场景下的平均测控需求满足度

表5　各算法在不同场景下的平均计算时间　s

从计算成本来看,由于本文所给出的算法都是调度问题初始解构造的贪婪算法,每一步任务的选择和可用弧段的选择都是根据启发式规则确定的,直至所剩任务没有可以弧段为止。因此在算法运行过程中,未调度集合随时间变化都应是线性递减,直至算法结束。不同的是,各个算法进行每一步可用弧段选择时进行的计算复杂度是不同的,从仿真结果来看,FIFO由于仅仅进行简单排序,因而计算量最少;First-Set由于要先确定AW窗口集,再排序,因而次之;Max-Value由于需要先确定每个可用弧段的价值而需要更多计算量;First-Set & Max-Value即要先确定AW窗口集又要确定每个可用弧段的价值,因此计算量最大。

7结论

针对我国航天测控网调度需求特点,提出一种混合构造启发式的测控网调度问题求解算法。算法综合考虑任务局部和测控需求整体,融合了First-Set规则和Max-Value规则的构造启发式规则,通过以测控需求满足率为指标动态选择构造启发式规则来提高求解质量。通过仿真实验分析比较验证了该算法可以在不明显增加计算时间的基础上得到更高的初始解质量。本文虽然对航天测控网调度的混合构造启发式算法进行了一个很好的尝试,但是由于混合的方式还比较简单而造成计算代价较大。下一步将继续深入研究这种混合构造启发式算法,提高两者构造启发式规则的耦合程度,如在可用窗口集的选择依据上引入Max-Value规则等,进一步改善计算成本。

参考文献：

[1] Jorg F, Konstantinos K, Banafsheh K. Operations research in the space industry[J].EuropeanJournalofOperationalResearch, 2012, 217(2): 233-240.

[2] Barbulescu L, Howe A, Whitley D. AFSCN scheduling: how the problem and solution have evolved[J].MathematicalandComputerModelling, 2006, 43(9/10):1023-1037.

[3] Stottler D. Satellite communication scheduling, optimization, and deconfliction using artificial intelligence techniques[C]∥Proc.oftheInfotech@Aerospace,2010.

[4] Schalck S M. Automating satellite range scheduling[D]. Dayton: Air Force Institute of Technology, 1993.

[5] Barbulescu L, Watson J P, Whitley L D, et al. Scheduling space-ground communications for the air force satellite control network[J].JournalofScheduling, 2004, 7(1): 7-34.

[6] Stottler R, Mahan K, Jensen R. Bottleneck avoidance techniques for automated satellite communication scheduling[C]∥Proc.oftheInfotech@Aerospace, 2011.

[7] Gooley T. Automating the satellite range scheduling process[D]. Dayton: Air Force Institute of Technology, 1993.

[8] Chen L J, Wu X Y, Li Y F. Scheduling algorithm for relaying satellite based on temporal flexibility[J].AeronauticalComputingTechnique,2006,36(4):48-51.(陈理江,武小悦,李云峰.基于时间灵活度的中继卫星调度算法[J].航空计算技术,2006,36(4):48-51.)

[9] Ling X D, Wu X Y, Liu Q. Requirement-oriented TT&C scheduling algorithm[J].SystemsEngineeringandElectronics, 2009, 31(7):1661-1666.(凌晓冬,武小悦,刘琦.面向需求的航天测控资源调度算法[J].系统工程与电子技术, 2009,31(7):1661-1666.)

[10]Chen F. Research on genetic algorithm for multi-satellite TT&C scheduling problem[D].Changsha:National University of Defense Technology,2010.(陈峰.多星测控调度问题的遗传算法研究[D].长沙:国防科学技术大学,2010.)

[11]Ling X D, Wu X Y, Liu B, et al. Study on the CSP model of satellite TT&C resource scheduling[J].SystemsEngineeringandElectronics,2012,34(11):2275-2279.(凌晓冬,武小悦,刘冰,等.卫星测控资源调度CSP模型研究[J].2012,34(11):2275-2279.)

[12]Chen F, Wu X Y. Space and ground TT&C resource integrated scheduling model[J].JournalofAstronautics, 2010, 31(5): 1405-1412.(陈峰,武小悦.天地测控资源一体化调度模型[J].宇航学报,2010,31(5):1405-1412.)

[13]Kang N. Research on genetic algorithm for multi-satellite TT&C scheduling problem[D]. Changsha: National University of Defense Technology,2011.(康宁.航天测控优化调度模型及其拉格朗日松弛[D].长沙:国防科学技术大学,2011.)

[14]Damiani S, Dreihahn H, Noll J, et al. Automated allocation of ESA ground station network services[C]∥Proc.oftheInternationalWorkshoponPlanningandSchedulingforSpace,2006:1-10.

[15]Marinelli F, Rossi F, Nocella S, et al. A Lagrangian heuristic for satellite range scheduling with resource constraints[J].Computers&OperationsResearch,2005,38(11):1572-1583.

[16]Schmidt M, Schilling K. A scheduling system with redundant scheduling capabilities for ground station networks[C]∥Proc.oftheInternationalWorkshoponPlanningandSchedulingforSpace, 2009: 1-6.

刘建平(1975-),男,高级工程师,博士,主要研究方向为航天任务智能规划与优化调度。

E-mail:ljpnudt@sina.com

李晶(1963-),女,研究员,博士,主要研究方向为航天任务智能规划与优化调度。

E-mail:carol_lee_0727@sina.com

张天骄(1988-),女,工程师,博士研究生,主要研究方向为航天任务智能规划与优化调度。

E-mail:tiantian880407@163.com

网络优先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20141119.2227.011.html

Hybrid constructive heuristics of space measurement and

control network scheduling problem

LIU Jian-ping, LI Jing, ZHANG Tian-jiao

(StateKeyLaboratoryofAstronauticDynamics,Xi’anSatelliteControlCentre,Xi’an710043,China)

Abstract:For the space measurement and control network scheduling problem, a hybrid constructive heuristics is proposed. Different from existing constructive heuristics, this heuristics takes advantage of characteristics of space measurement and control network scheduling requirements, including priorities, temporal intervals and multiple same tasks in one requirement. Considering both local tasks and the complete requirement, it integrates the maximum valued available task window rule with the first available task window set rule. Its advantage is to improve the solution quality by means of dynamic choice of the two rules. Finally,through simulation cases and computational results analysis,it is found that this hybrid constructive heuristics can improve the solution quality and increase less computation cost.

Keywords:constructive heuristics; space measurement and control network scheduling problem; tracking, telemetry and command (TT&C) requirement; constraint optimization problem (COP); temporal interval

作者简介：

中图分类号：TP 18

文献标志码：A

DOI:10.3969/j.issn.1001-506X.2015.07.16

基金项目：青年创新基金(GFZX04060103-02)资助课题

收稿日期：2014-07-08；修回日期：2014-11-01；网络优先出版日期：2014-11-19。