敏捷对地观测卫星自主任务调度方法

刘 嵩，孔鸿滨

(广州城市理工学院 计算机工程学院，广东 广州 510812)

0 引言

对地观测卫星作为一种重要的对地观测手段，具有覆盖区域广、可长时间运行和不受飞行空域限制等优势[1-2]，而对地观测卫星任务调度正是充分发挥这些优势的关键。

对地观测卫星任务调度负责分配卫星观测资源、制定观测计划[3]。传统的对地观测卫星任务调度是由地面控制系统完成。首先要预估卫星状态，根据用户需求提前为卫星制定观测方案，然后在特定时间将执行指令上注至卫星执行[4-9]。但该过程会受到地面预估误差、星地通信时间窗口等限制，而且指令一旦上注便无法变更，这将导致卫星很可能错过对重点目标的最佳成像时机，更加无法快速灵活地根据自身状态应对随时可能到达的动态观测需求。

为了解决上述问题，各国学者越来越重视卫星自主调度技术方面的研究[10-11]。一旦卫星具备了自主调度能力，便可以随时根据动态到达的观测需求，在星上自主制定观测方案，真正实现对地观测数据的智能化实时服务，从而克服地面调度的弊端。

针对对地观测卫星自主任务调度问题，文献[12]提出了一种基于任务轴的滚动调度策略，由于调度与执行任务交替进行，所以调度占用的时间越长，执行任务的时间就越短，二者存在矛盾。文献[13-17]针对EO-1卫星自主任务调度问题进行了深入研究，通过在星上分析重点目标的地质现象是否发生变化，来决定是否触发迭代修复算法，但这种触发事件发生的概率较低，因此该方法对动态事件的响应能力不强。文献[18-19]提出了一种星上随机迭代贪婪算法，能够解决目标被云层遮挡下的敏捷卫星自主任务调度问题，虽然对动态事件响应能力有所提升，但是动态事件主要是指云层遮挡造成的任务取消，并没有考虑观测需求随机到达的情况。文献[20]利用迭代修复的方法进行自主任务调度，但卫星状态实时变化，所以修复时机很难把握，而且每一次调度的持续时间无法确定。另外，目前的研究主要针对非敏捷卫星，而且大多只考虑观测任务，没有结合考虑数据回传任务。

针对上述不足，本文首先提出了一种星上自主调度策略，明确了星上自主任务调度的时机，以及每次调度的范围，然后针对此策略，设计了一种基于变邻域搜索的星上自主任务调度算法，算法不仅考虑了敏捷卫星特点，还考虑了数据回传任务，最后通过仿真实验验证了该算法的有效性。

1 问题描述与建模

非敏捷对地观测卫星只能对目标实行过顶成像，成像时间是一定的，一旦错过了过顶时间，将无法完成观测任务。敏捷对地观测卫星则不同，在卫星尚未到达目标正上方时，便可以通过调整俯仰角度观测到地面目标。有效观测范围示意如图1所示。

图1 观测范围示意Fig.1 Observation scope

敏捷对地观测卫星的观测时间窗口更长，观测时间不再局限于过顶时间，而是可以在观测时间窗口内任意滑动。因此对于非敏捷对地观测卫星一次过境无法完成观测的区域目标，敏捷对地观测卫星可以采用同一轨道多次向同一方向进行推扫的方式，完成区域目标的同轨多条带拼接成像。条带长度由扫描时间决定，一次推扫过程如图2所示。敏捷性提升了卫星的观测能力，但更长的时间窗口也大大增加了任务调度的优化难度。

图2 对地观测过程示意Fig.2 Process of earth observation

敏捷对地观测卫星自主任务调度问题可以描述为：面对随时可能到达的观测需求，敏捷对地观测卫星能够在不需要或较少依靠地面人员干预的情况下，根据自身的状态，星上自主决策调度时机和调度范围，自主制定观测方案，在快速响应动态观测需求、提高观测时效性的同时，实现以尽可能少的资源消耗获取尽可能大的观测收益。

1.1 模型的输入输出

模型输入：调度开始时间p，调度结束时间q和观测任务集合J；J中每个观测任务j所对应的优先级wj、占用固存大小cj、观测持续时间oj和数据回传持续时间dj；能够对任务j进行观测的卫星圈次的集合Mj，以及在圈次k对任务j进行观测时，所对应的观测时间窗口的开始时间sj,k和结束时间ej,k；数据回传时间窗口集合I，I中每个数据回传时间窗口i所对应的开始时间bi和结束时间ri；卫星固存最大值C。

1.2 目标函数与约束条件

优化目标是使得完成观测任务和数据回传任务的累积收益最大，目标函数为：

(1)

约束条件：

(2)

bi≤bj,i

(3)

(4)

(5)

0≤Ct≤C，

(6)

(7)

(8)

xj,k≥yj,i，

(9)

(10)

式(2)为观测时间窗口约束，每个观测任务必须在其观测时间窗口内被观测。

式(3)为回传时间窗口约束，每个数据回传任务必须在回传时间窗口内被回传。

式(4)为观测与回传的时间顺序约束，观测数据的回传开始时间不能早于该目标的观测结束时间。

式(5)为姿态转换时间约束，当任务j与j′在第k个轨道圈次上连续执行，则需要时间TSj,j′来完成卫星的姿态转换。

式(6)为卫星存储约束，表示任意时刻的卫星固存Ct都不能超出卫星最大固存C。

式(7)为观测机会约束，每个目标最多只能被观测一次。

式(8)为回传机会约束，每个观测任务的数据最多只能被回传一次。

式(9)为观测与回传的逻辑关系约束，只有完成观测的任务，其观测数据才会被回传。

式(10)为任务不间断约束，任意2个观测任务j和j′，以及2个任务所对应的数据回传任务不能同时执行，观测任务和数据回传任务不能同时执行。

2 星上自主调度策略

星上自主调度策略的核心思想是通过缩小调度周期和调度范围，增加调度次数，实现用反复进行的小规模的调度代替一次性大规模的调度。由于调度次数大幅增加，所以每一次进行调度时都能建立在最新任务信息的基础上，从而应对动态观测需求。

本策略规定每一次调度都包含3个步骤:步骤1建立调度窗口，即确定哪些任务参与本次调度；步骤2调度求解，即针对调度窗口内的任务进行调度，输出观测任务序列作为调度结果；步骤3建立执行窗口，即在调度结果中选择一部分任务作为将要执行的任务执行方案。

第n次调度产生的任务执行方案的编号为n。每一次调度都与卫星执行任务执行方案同时进行，即执行第n个任务执行方案的同时进行第n+1次调度。第n个任务执行方案中的最后1个任务的执行结束时间，就是第n+1次调度的结束时间。每次调度结束后，立即开始下一次调度，因此每一次调度的开始和结束时间可以通过计算得到。自主调度策略的控制过程如图3所示。

图3 自主调度策略活动图Fig.3 Activity diagram of autonomous task scheduling strategy

相比文献[12]中调度与执行交替进行的滚动方式，本策略的最大好处在于调度过程和任务执行过程都是持续进行的，如图4所示，该策略下调度的机会更多，所以能够对观测需求的动态变化做出快速响应。同时,执行的时间也更长了，所以能够充分发挥卫星的观测效能。

图4 对比图Fig.4 Comparison chart

2.1 调度窗口

建立调度窗口是每一次调度的第1个步骤。调度窗口有2个控制参数：“数量上限”和“时间跨度”。“数量上限”是指调度窗口内任务数量的最大值；“时间跨度”要求调度窗口内所有观测任务时间窗口的开始时间与建立调度窗口的时间差必须小于该跨度。

建立调度窗口之前，首先要将星上的观测任务和数据回传任务分为4类：等待调度任务、等待执行任务、已完成任务和执行任务，任务类型随时间变化。等待调度任务是指那些没有被纳入任务执行方案，没有确定执行时间，正在等待调度的观测或数据回传任务。等待执行任务是指那些已经被纳入任务执行方案，确定执行时间，但尚未被执行的观测或数据回传任务。已完成任务是指那些已经完成的观测或数据回传任务。执行任务是指卫星正在执行的观测或数据回传任务。

任务分类示意如图5所示，假设当前建立调度窗口的时刻为时刻1，即本次调度开始时刻。时刻2为相邻的下一个调度窗口的建立时刻，即下一次调度的开始时刻。如果以时刻1为基准对任务进行分类，那么观测任务1和数据回传任务1属于已完成任务。观测任务2和数据回传任务2属于等待执行任务，数据回传任务3属于执行任务。等待调度任务由于没有被赋予执行时间段，因此没有在图中标出。在时刻2，图中全部任务均属于已完成任务。所以说这种分类方式具有动态性。

图5 任务分类示意Fig.5 Task classification

调度窗口由等待调度任务构成。假设当前调度窗口开始时刻为t，相邻的下一个调度窗口开始时刻为t″，“时间跨度”为T。在建立调度窗口之前，首先将所有在t″～t″+T时刻存在观测时间窗口的等待调度任务组成观测任务集合Observe(t)。如果Observe(t)不为空，那么按照时间窗口开始时间的先后顺序对观测任务进行排序。当任务有多个时间窗口时，依据其最早可用时间窗口参与排序。如果2个任务的时间窗口开始时间相同，则按照优先级从高到低的顺序进行排序，如果2个任务的优先级相同，则随机确定2个任务的前后关系。

将所有在t″～t″+T时刻存在数据回传时间窗口的等待调度任务组成数据回传任务集合Transmission(t)。如果Transmission(t)不为空，则任务按照从前至后，优先级由高至低的顺序进行排序。如果2个数据回传任务的优先级相同，则随机确定2个任务的前后关系。

最后将Transmission(t)连接在Observe(t)之前构成一个新的任务序列，并从前至后连续选择min(Transmission(t)+Observe(t),k)个任务构成任务集合ScheduleWin(t)，ScheduleWin(t)就是t时刻的调度窗口，k表示“数量上限”。建立调度窗口的流程如图6所示。调度窗口建立后，即确定了调度对象，便可以运用算法进行调度求解。求解结果即调度结果，用Schedule(t)表示。Schedule(t)是一个按执行开始时间排序的任务序列，其中的每一个任务都有明确的执行时间段。

图6 调度窗口构建流程Fig.6 Flow chart of scheduling window construction

2.2 执行窗口

根据Schedule(t)建立执行窗口。执行窗口有2个控制参数：“执行上限”和“间隔上限”控制。“执行上限”是指任务执行方案中所包含的任务数量的最大值。“间隔上限”要求任务执行方案中前一个任务的结束时间和后一个任务的开始时间的时间间隔不能超过此上限，目的是控制任务执行方案的松散程度，避免2个任务之间的等待时间过长。

建立执行窗口时，在Schedule(t)中从前至后一共选择min(|Schedule(t)|,k″)个卫星任务构成执行窗口，执行窗口内的任务序列就是任务执行方案，而k″就是观测方案的执行上限。如果k″比较大，将导致执行任务和下一次调度的持续时间变长，而调度的机会变少，最终造成对动态观测需求的反应能力减弱。但是如果k″太小，虽然调度的机会变多，对动态观测需求的反应能力得到提高，但调度持续时间变短，会导致调度算法的求解时间受到限制，所以优化结果的质量难以保证。

通过“执行上限”可以控制执行和调度持续时间长度，但只考虑k″得到的任务执行方案可能比较松散。如果任务之间的时间间隔比较大，即使k″很小，整个任务执行方案的执行持续时间也可能会很长，从而降低调度频率。因此需要使用“间隔上限”对任务执行方案做进一步限制。当任务执行方案中出现2个连续任务Task1和Task2，且Task1和Task2的时间间隔大于Task2及其之后的所有任务删除，保证任务执行方案中的任意2个连续任务的时间间隔都小于等于k‴，而k‴表示的就是“间隔上限”。

3 算法设计

本算法用于针对调度窗口内的任务进行调度求解，并输出Schedule(t)。算法的核心思想是首先利用启发式规则生成一定数量的初始解，选取其中的最优解作为初始解x，即搜索起点，然后进行变邻域搜索。在每一个邻域内进行搜索的次数达到lmin时，则视为已经陷入局部最优，必须改变邻域结构。搜索过程中，如果搜索到一个更优的解y，则说明该邻域有利于解的改进，并将y替换x作为搜索起点，继续在该邻域内搜索。

自主调度策略根据调度的开始时间和结束时间，控制算法的开始和结束，每次调度结束时输出当前最优解。除此之外算法还设置了最大迭代次数lmax，当达到该条件则算法也将停止，算法流程如图7所示。

图7 算法流程Fig.7 Flow chart of algorithm

3.1 初始解

第1步，任务排序。首先使用文献[12]所设计的7种排序规则对调度窗口的观测任务进行排序，得到7种观测任务序列。如果调度时存在已经完成观测但数据尚未被回传的数据回传任务，那么还要确定当前最早可用数据回传时间窗口的开始时间。在观测任务序列中从前至后寻找第一个观测时间窗口开始时间大于该时间的观测任务。如果存在，将数据回传任务按高优先级优先规则插入该任务之前。如果不存在，则将数据回传任务序列按高优先级优先规则插入到序列末端。

第2步，确定任务执行时间并进行约束检查。从前至后为队列中每个任务选择执行的开始和结束时间。在确定任务的执行时间时，首先使用文献[12]所设计的时间窗口裁剪方法对该任务的时间窗口进行裁剪，避免不同任务在时间上发生重叠。将最早可用的时间窗口的开始时间作为观测任务的开始时间。将最早可用的数据回传时间窗口的开始时间作为数据回传任务的开始时间。每当一个观测任务确定了执行时间，立即对它进行约束检查，如果满足约束条件，增加一个该任务所对应的数据回传任务，否则将该任务删除。增加的数据回传任务按高优先级优先规则插入到已经存在的数据回传任务序列中。如果是序列中唯一的数据回传任务，那么排序位置参照第1步中的规则。

第3步，收益计算。将收益最高的解作为初始解。

3.2 邻域结构设计

3.2.1 末位插入邻域

在解中任意选择n个xj,k=1的观测任务，将这n个任务转移至任务序列Sequence的末端，这n个任务分别用x1，x2，…，xn表示，如图8所示。观测任务序列改变后，重新插入数据回传任务。插入方法与生成初始解第1步中的插入方法一致。一般来说，如果将某些观测任务移至序列末尾，那么这些任务能够被执行的可能会变得很小，但从优化的角度来看，可以通过末位插入，增大完成其他任务的概率。

图8 末位插入邻域Fig.8 Final bit insertion neighborhood

3.2.2 首位插入邻域

在解中任意选择n个xj,k=0的观测任务，这n个任务分别用x1，x2，…，xn表示，如图9所示。观测任务序列改变后，重新插入数据回传任务。插入方法与生成初始解第一步中的插入方法一致。一般来说，如果将某些观测任务移至序列前端，那么这些任务能够被执行的可能性会增加，从而有机会提高解的质量。

图9 首位插入邻域Fig.9 First bit insert neighborhood

3.2.3 交换邻域

任意选择n个xj,k=1的观测任务。这些任务用x1，x2，…，xn表示。然后任意选择n个xj,k=0的观测任务，并用y1，y2，…，yn表示这些任务。先后将x1与y1，x2与y2的位置进行交换，直到最后将xn与yn的位置进行交换，如图10所示。观测任务序列改变后，重新插入数据回传任务。插入方法与生成初始解第1步中的插入方法一致。

图10 交换邻域Fig.10 Exchange neighborhood

4 实验结果及分析

实验中卫星的轨道参数来自北美空防司令部2017年5月公布的WorldView-2卫星轨道数据。观测目标为点目标，分布在卫星星下点轨迹附近。每个观测任务都由任务编号、轨道编号、任务优先级、观测时间窗口和观测持续时间等相关信息构成。

假设每个观测任务的观测持续时间是5～30 s，每个观测任务的数据回传持续时间是观测持续时间的2倍，每个观测任务的优先级是1～10。实验中用观测持续时间代替具体的固存占用大小，假设卫星固存最大可容纳2 400 s的观测数据。假设有1个机动地面站可以提供5个数据回传时间窗口，单个数据回传时间窗口平均长度为720 s。实验计算机配置为Intel(R) Core(TM) i5-7200U CPU@2.50 GHz，内存为8 GB，操作系统为Windows10，编程环境为Matlab。

4.1 实验1

利用Simulink模块中的有限状态机模拟自主调度策略，确定调度时机、调度范围，控制算法的开始和结束，并模拟任务动态到达场景。实验场景时间设定为24 h。实验中，“数量上限”设置为50，“时间跨度”设置为3 600 s，“执行上限”设置为10，“间隔上限”设置为300 s。为了模拟星上有限的运算能力，假设星上算法迭代一次生成一个可行解所花费的时间为10 s。

观测任务完成数量如图11所示。随着动态观测需求数量的不断增加，卫星每天可以观测的任务数量逐渐增加，并在270附近处趋于平稳，这说明270个任务接近实验中每天观测的最大任务数量，这主要是由于固存和数据回传时间窗口约束造成的。由于观测能力限制，随着观测需求的不断增加，任务完成率呈下降趋势，如图12所示。但如果在观测能力范围内，任务完成率还是很高的，可以稳定在90%附近。实验中数据回传时间窗口利用率能够稳定在90%附近，如图13所示。

图11 观测任务完成数量Fig.11 Completion number of observing tasks

图12 观测任务完成率Fig.12 Completion rate of observing tasks

图13 数据回传时间窗口利用率Fig.13 Use rate of data backhaul time-window

数据回传时间窗口没有被完全利用，是因为每个数据回传任务的回传持续时间不同，数据回传任务不能在不同的回传窗口中接续回传，所以如果数据回传窗口剩余的时间不足以完成一个回传任务，那么就不能执行数据回传。但较高的数据回传时间窗口利用率会导致很多观测时间窗口与数据回传时间窗口发生重叠的观测任务将在发生重叠的这一轨无法完成观测，这也是无法完成全部观测任务的一个原因。

观测需求数量对高优先级任务(优先级在9以上)比例和低优先级任务(优先级在2以下)比例的影响并不大，如图14所示。高优先级任务比例保持在28%附近，而低优先级任务比例保持在15%以下，与优化目标一致。

图14 任务完成率对比Fig.14 Comparison of completion rates

实验结果表明，面对随机到达的观测需求，在考虑数据回传任务和敏捷卫星特点的同时，所提出的自主任务调度策略和自主任务调度算法能够较好地解决敏捷对地观测卫星自主任务调度问题。另外，虽然较多的观测需求可以充分发挥卫星效能，但有限的数据回传资源将导致大量观测数据无法在当天回传。

4.2 实验2

分别使用文献[12]中的LS算法和本算法对不同规模的卫星任务调度问题进行求解。实验根据任务数量分为4组，最终取平均值作为实验结果。各组任务中10%的任务是已经存在的数据回传任务，其他为观测任务。假设卫星固存的最大值为参与调度的观测任务的固存占用值之和的50%。lmax=100，lmin=lmax/3。实验结果如表1所示。

表1 算法对比实验结果Tab.1 Experimental results of algorithms comparison

在有限的迭代次数下，本算法的求解效果要优于LS算法。这是因为本算法在搜索过程中用邻域结构引导搜索方向。LS算法的初始解比较多，因此根据每个初始解进行迭代改进的迭代次数变得非常有限。另外，LS算法在迭代改进过程中，使用的是轮盘赌的思想，没有明确的邻域结构，因此在有限的迭代次数中对解的改进略显盲目。另外，2种算法的优化目标并不相同。LS算法中，如果一个观测任务和其所对应的数据回传任务不能在调度结果中同时出现，则没有收益。这种方式忽略了观测任务自身的收益，也是结果相对于本算法较差的原因之一。

5 结束语

针对星上自主任务调度问题展开研究，提出了星上自主调度策略，建立了问题的约束满足模型，并根据星上运算能力弱的实际设计了基于变邻域搜索的星上自主任务调度算法，主要取得了以下成果：

① 自主调度策略能够保证在合适的时机，针对合适的任务进行星上调度，并利用反复进行的小规模的调度代替一次性大规模的调度。由于每一次调度都能建立在最新任务信息的基础上，因此可以应对观测需求的随机到达。

② 针对问题建立了约束满足模型，考虑了数据回传任务和敏捷卫星特点，并在此基础上提出了一种基于变邻域搜索的星上自主任务调度算法。算法利用邻域结构引导搜索方向，从而保证了解的质量。

③ 实验结果表明，算法在自主调度策略的控制下能够对频繁到达的观测需求进行快速响应，达到了设计预期。另外相比较LS算法，本算法针对不同问题规模，均有更好的表现。