多站多星任务调度模型及求解

王万玉,张志强

(中国科学院对地观测与数字地球科学中心,北京 100086)

1 引 言

随着空间技术及遥感应用业务化、产业化的发展,越来越多的中低轨道卫星和地面接收站投入使用,使得如何合理有效地使用地面接收站资源,快速、高效地制定卫星数据接收计划,最优化接收卫星数据,成为一个亟待解决的问题。

目前,多数任务调度研究针对的是单卫星[1]或多星任务调度[2,3],主要解决卫星资源的优化问题;或多卫星单地面接收系统[4],主要解决多星任务冲突的问题;或多星地面资源配置[5,6],主要解决多星测控资源优化配置问题。已有任务调度模型大多是针对某一特定的任务类型,较难扩展到多接收站多卫星系统的遥感数据接收任务调度上来。对多站多星接收任务的调度问题,需针对遥感卫星数据接收任务的特征,如用户需求的多样性、地面接收资源的使用约束,以及后续数据传输、处理的需求,建立针对该系统任务需求的优化调度模型,以满足对地观测卫星应用中的最优化接收卫星数据的需求。

本文针对遥感卫星接收任务的特征,分析了多站多星任务调度的主要约束条件,提出了完成任务优先级之和最大与尽可能使用同一天线完成同一任务两个优化目标函数;建立了基于约束满足优化问题的多站多星任务调度优化模型;将多站多星任务调度优化模型分为预处理和优化两个阶段进行求解。预处理过程综合利用贪婪算法和约束传播相结合的方法;优化过程主要根据任务初始调度结果进行调整和优化,在不降低完成任务优先级之和的情况下,使得同一任务尽可能地由同一天线执行,这样就可以减少天线进行任务转换的次数,增强卫星遥感数据接收的完整性。

2 多站多星任务调度的特征与约束分析

多站多星任务调度是一个基于约束的资源优化问题[7],即在一定的约束条件下,将有限的资源分配到不同的任务时间段上,其目标之一是在给定的时间内完成最多的任务,或者在考虑任务的权重时最大化完成任务的权重之和,即在卫星可视时间窗口集内,选择执行的任务权重之和最大。

多站多星任务调度主要受任务约束、资源约束和时间窗口约束3种约束关系的制约,任务约束指的是任务的优先级高低排序、任务执行过程的不可中断性等;资源约束主要指的是地面站接收系统的可用性、可选择性、任务转换时间间隔等;时间窗口约束指的是时间窗口的开始时间和结束时间、时间窗口的可用性等。

2.1 任务约束

假设有Mt个任务T={T1,T2,…,TMt}所属卫星有Ms颗S={S1,S2,…,SMs},所有任务按照开始时间的先后顺序进行编号,即 t1s<…

(1)任务优先级

由于地面站资源的有限性,且用户对卫星遥感数据的需求存在差异性,任务的重要程度是不相同的。因此,任务首先存在优先级不同这样的约束。

任务优先级确定该卫星数据接收任务需求的重要程度,该值是由国家紧急需求、用户订购需求重要程度、卫星数据类型以及需求时间先后顺序等因素综合得出。国家紧急需求任务务必调度执行;用户订购需求任务尽最大可能地调度执行,为区分用户需求的重要程度,分若干等级设置其优先级;重要卫星数据存档任务尽可能实施,同样分若干等级设置其优先级;其余数据接收任务根据时间窗口安排。这些任务的优先级依次降低,如表1所示。

表1 任务优先级Table 1 Task Priority

在讨论卫星遥感数据接收任务需求时,我们按照表1为每一个任务分配一个优先级,即Mt个任务的优先级是p={p1,p2,…,pMt}。一种可行的调度方案是按照任务优先级由高至低的顺序进行任务调度。

(2)任务是否必须被调度执行

为说明该约束,我们首先定义任务决策变量w={w1,w2,…,wMt}:

假设一个任务是否必须被执行用Ct来表示,则该约束可以表示为

(3)任务执行过程的不可中断性

此约束表明,任务一旦被调度执行,就必须被完成,不允许插入其它任务。

2.2 资源约束

地面站资源主要包括地面接收天线与伴随天线的控制、数据接收通道、记录和数据传输等分系统,这些资源统称为地面接收天线系统资源。我们将多地面站多套接收天线资源作为整体来表现对接收遥感卫星下传数据是否可用,且在任意时刻一个地面接收天线只能执行一个数据接收任务。

卫星遥感数据接收任务在调度过程中,首先选择合适的地面接收天线系统,需要考虑天线系统的可用性、资源容量限制和任务转换调整时间。

(1)天线系统的可选择性和可用性

如果地面站接收天线系统能够接收某颗卫星的遥感数据,并且能够正常工作,那么就称该天线系统对该卫星是可用的,否则便是不可用的。记AVA为某一时刻地面天线对任务的可用性,则:

定义资源约束为Cr,则天线系统资源可选择性与可用性约束Cr1为

式(4)表示任务Ti要么未被调度(wi=0),要么被调度安排(wi=1),此时必须至少存在一个可用的地面接收天线。

(2)天线任务转换时间

地面接收天线由一个任务转向执行另一个任务必须有一段时间用来预置天线、配置系统参数并跟踪卫星。一般地,该时间段长度为3～5 min。假设该时间段为Δt,则天线任务转换时间约束Cr2为

式(5)表示对任意地面接收天线系统 Aj,它所执行的任意两个任务之间的时间间隔都不小于天线任务转换时间。同时,该式还表明,在任意时刻,一个地面天线最多只能执行一个任务。

2.3 时间约束

多站多星任务调度问题的时间约束主要包括任务调度时间范围约束 Ctime和卫星过境时间窗口约束Cw。

假设任务调度开始时间是0,截止时间是thorizon,则调度时间约束Ctime为

式中,tis和tie分别是任务Ti的开始时间和结束时间。该约束表明,任何一个任务的完成必须在给定截止时间之前。

时间窗口指的是遥感卫星经过地面站接收覆盖范围时的入境和出境之间的时间段。只有在这个时间段,卫星和地面站才是可见的,才能进行数据传输,地面接收天线才能执行待调度任务。卫星过境时间窗口可用开始时间、结束时间和可用性状态3个属性来描述,可用性状态用来标识该时间窗口是否具有数据接收意义、是否已经被调度任务占用等。

多站多星数据接收的时间窗口存在多个时间窗口相互重叠的现象,不同天线之间存在共视区。为此,我们定义一个时间窗口需求变量Qij,它表示任务Ti对地面接收天线Aj的时间窗口需求。则时间窗口需求约束Cw1为

式(7)表示任务Ti要么未被调度(wi=0),要么被调度安排(wi=1),此时∪Qij≠ ,在确定地面接收天线系统的情况下,至少有一个可用时间窗口被分配给该任务。

同时,要求一根天线在一段时间内不能同时分配给两个任务,表现在时间窗口上就是一个时间窗口不能同时分配给两个任务需求,用Cw2来表示:

3 基于约束满足优化问题的多站多星任务调度模型

多站多星任务调度具体可归纳为:根据任务需求,在一定的约束条件下,按照给定的优化目标,将地面接收系统资源和可用时间窗口分配给不同的卫星数据接收任务,是一个包括地面接收天线选择和时间窗口选择的双重选择映射问题。

多站多星任务调度(TS)问题可以用4元组来表征:

式中,T为任务集,T={T1,T2,…,TMt},表示待调度的卫星遥感数据接收任务集合;A为地面接收天线集,A={A1,A2,…,AMa},包括地面站所有在运行的接收天线;TW为时间窗口集:遥感卫星相对于地面站的过境时间窗口集合,每一个时间窗口可以表示为一个闭区间[ts,te],ts表示时间窗口开始时间start-time,te表示时间窗口结束时间end-time;C为约束集,描述各种约束关系,主要包括任务约束、资源约束和时间窗口约束。

若使用4元组TS={T,A,TW,C}表示多站多星接收任务调度问题,则该问题的主要约束就是任务约束(Ct)、资源约束(Cr)和时间窗口约束(Ctime,Cw),即:

通常,多站多星任务调度问题的优化目标函数为最大化完成任务优先级之和;实际工作中,总是希望尽可能使用同一地面接收天线系统完成同一任务的卫星遥感数据接收,以利于后续数据处理及应用。下面分别讨论这些目标函数。

完成任务优先级之和函数:

式中,Pi为任务优先级,wi为任务决策变量。

为表示尽可能使用同一天线系统完成整个任务这一目标函数,我们定义另一任务决策变量W:

它与决策变量w的关系为wi=Wij,即只要有天线执行了任务Ti,就说明该任务得到了调度执行。

记地面接收站在调度时间范围内执行任务总次数为f2:

根据上述的变量约定、约束分析和目标函数,我们建立多站多星任务调度优化模型如下:

4 基于贪婪算法和约束传播的模型求解算法

采用贪婪算法[1,8]和约束传播相结合的方法,初步求解多站多星任务调度问题。贪婪算法使得优先级高的任务最先得到调度,约束传播主要减小了问题的搜索空间,加快求解速度。然后基于不降低完成任务优先级之和的同时尽可能满足同一任务由同一接收天线完成的思想对初始调度进行调整和优化,最后得到多站多星任务调度问题的最优调度方案。

4.1 任务调度顺序的选择规则

任务调度顺序的选择规则如下:

(1)选择优先级最大的任务;

(2)在优先级相等时选择所属卫星重要程度高的任务;

(3)当所属卫星重要程度相同时选择开始时间较早的任务。

4.2 地面接收天线的选择规则

对每一个待调度的任务 Ti来说,若要被安排,则必须指定至少一个地面接收天线和相应的接收时间窗口。而对某一地面接收天线Aj系统来说,它是否能够完成该任务,则要受两方面因素的影响:一是它能否接收来自该任务所属卫星的遥感数据;二是它与该卫星是否存在与任务时间范围相重叠的可用时间窗口。这两方面因素都满足时,才能将任务分配给该天线系统,否则便不可以分配给该天线。

任务 Ti时间范围与可用时间窗口TWk之间在时间上有6种相对位置关系,如图1所示。

图1 任务时间范围与可用时间窗口之间的关系Fig.1 Relations between task time scope and available time-window

如果任务Ti时间范围与可用时间窗口TWk之间的相对位置处于类型0或者1,则说明两者没有任何重叠,不能将该任务分配给这样的时间窗口;处于类型2或者3时,两者部分重叠,根据重叠时间的长度决定是否将任务的一部分分配给该时间段,同时考虑剩余的时间能否再利用;处于类型4时,任务Ti完全可以在该时间窗口内完成;处于类型5时,时间窗口在任务时间范围内,只能执行部分任务。

根据地面站的接收覆盖范围、地面接收天线的性质和能力、地面站至地面数据中心的数据传送和分发成本,将各地面站的接收天线按照总代价最小的原则进行排序,即优先考虑用接收范围大、工作容量大、数据传送成本低的地面接收天线来完成任务。

4.3 任务初始调度时的可行性判读

假设某一地面接收天线 Aj能够执行待调度任务Ti且具有一个可用时间窗口TWk,该时间窗口与任务时间范围重叠的部分记为[ts,te],那么在将任务分配给该天线之前,必须检查它与已经分配给该天线的任务是否有冲突。如果没有冲突,就将任务Ti分配给天线Aj,执行时间段为[ts,te],而后更新任务Ti的时间范围和天线Aj的可用时间窗口。如果存在冲突,则根据冲突类型和天线任务转换时间,减小[ts,te]为[t′s,t′e]。重新检查如果任务 Ti占用天线 Aj的时间范围[t′s,t′e]是否存在冲突,直到没有冲突或者时间范围的长度小于最小任务长度为止。

这种任务分配可行性判读方法,不仅可以检测到天线执行调度任务时是否发生冲突,且可以自适应地调整待调度任务在该天线上可执行的时间范围,增强了任务的可分配性。

4.4 任务初始调度后的参数值更新

如果可将任务Ti分配给天线Aj,执行时间段为[ts,te],那么就要更新任务Ti的时间范围和天线Aj的可用时间窗口TWk,以便再次分配。同时,更新任务集,包括已经得到调度的任务子集和未调度的任务子集,更新可用天线子集、可用时间窗口子集等。

4.5 任务初始调度优化方法和过程

根据任务优先级和天线有效性,利用贪婪算法和约束传播相结合的方法进行多站多星任务调度优化模型的求解,常常会将本应由一个地面接收天线系统执行的任务分配给不同的天线,不利于地面站运行,原因是:任务转换需要时间,浪费资源;同一任务记录成不同文件,不利于后端处理。

因此,我们提出了尽可能使用同一天线完成整个任务的优化目标函数,最大程度上减少任务调度过程中的任务分解。具体的调整优化过程分两步。

Step1:根据任务优先级高低依次检查任务调度预处理阶段的调度结果,如果任务完全被分配给一个地面接收天线系统执行,或者被分配给多个地面站的接收天线系统且每个地面站最多只有一个天线执行该任务,则继续检查下一个任务,直至结束。

Step2:检查该任务是否一定需要不同地面站的接收天线来执行,因此才产生的任务分解。如果该任务被分配给同一地面站的不同接收天线系统,则调整该任务的调度,使之使用同一地面站的同一个天线来执行,转Step1。

5 结 论

利用上述模型、求解算法及开发的软件,对3个遥感卫星地面站8套地面接收天线组成的卫星地面接收站网,接收10颗遥感卫星的多站多星接收任务进行了规划调度。从规划调度结果可以看出,优先级别高的任务均已被优先安排,所有的任务都得到了调度安排,且地面接收天线系统执行任务的时间长度较为均衡,没有冲突;从读取任务输入文件开始至生成任务调度计划表仅需5 s。

该优化调度模型及求解算法已成功应用于遥感卫星数据接收的日常运行工作中,实际使用效果表明,本文提出的多站多星接收任务调度的主要约束条件和优化目标函数是合理的,构建的模型和采用的算法是可行的。

[1]William J Wolfe,Stephen E Sorensen.Three Scheduling Algorithms Applied to the Earth Observing Systems Domain[J].Management Science,2000,46(1):148-168.

[2]刘洋,陈英武,谭跃进.一类多卫星动态调度问题的建模与求解方法[J].系统仿真学报,2004(12):2696-2699.LIU Yang,CHEN Ying-wu,TAN Yue-jin.Modeling and Solution of the Problem ofMulti-SatellitesDynamic Scheduling[J].Journal of System Simulation,2004(12):2696-2699.(in Chinese)

[3]刘洋,贺仁杰,谭跃进.基于约束满足的多卫星调度模型研究[J].系统工程与电子技术,2004(8):1076-1079.LIU Yang,HE Ren-jie,TAN Yue-jin.Modeling the Scheduling Problem of Multi-satellite Based on the Constraint Satisfaction[J].System Engineering and Electronics,2004(8):1076-1079.(in Chinese)

[4]刘洋,陈英武,谭跃进.卫星地面站系统任务调度动态规划方法[J].中国空间科学技术,2005(2):44-47.LIU Yang,CHEN Ying-wu,TAN Yue-jin.The Method of Mission Planning of the Ground Station of Satellite Based on Dynamic Programming[J].Chinese Space Science and Technology,2005(2):44-47.(in Chinese)

[5]王远振,高卫斌,聂成.多星地面站系统资源配置优化研究综述[J].系统工程与电子技术,2004(4):437-439.WANG Yuan-zhen,GAO Wei-bin,NIE Cheng.Summary of the resource configuration optimization for a multi-satellite ground station system[J].Systems Engineering and Electronics,2004(4):437-439.(in Chinese)

[6]金光,武小悦,高卫斌.卫星地面站资源调度优化模型及启发式算法[J].系统工程与电子技术,2004(12):1839-1841.JIN Guang,WU Xiao-yue,GAO Wei-bin.Ground station resource scheduling optimization model and its heuristic algorithm[J].Systems Engineering and Electronics,2004(12):1839-1841.(in Chinese)

[7]Joseph C Pemberton,Flavius Galiber III.A Constraint-Based Approach to Satellite Scheduling[EB/OL].2006-09-05[2010-01-08].http://www.cs.sfu.ca/cs/research/groups/ISL/library/Satellite%20Scheduling/pemberton.galiber.dimacs98.pdf.

[8]Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to Algorithms[M].2nd ed.New York:McGraw-Hill Book Company,2001.