0 引言

地球观测卫星在观测地面物体和活动中，起着很重要的作用^[1-2]。随着敏捷观测卫星(Agile Earth Observation Satellite, AEOS)，特别是具有自主优化性质的AEOS的广泛应用，卫星调度遇到新的挑战^[3-4]：有限的在线存储资源和实时变换的云层信息。目前，针对卫星调度的研究主要分为两类：传统的卫星调度研究和AEOS调度的研究。传统的观测卫星只负责调度计划的执行，其调度过程是由地面空间站结合任务特性、预测云层分布以及存储空间等的资源约束所规划^[5]。由于地面空间的存储资源、运算资源等比较丰富，传统卫星调度的研究主要是考虑实际条件和任务约束等，提出和改进算法，优化观测结果^[6]。然而，由于传统卫星调度得到的优化算法，并没有考虑动态变化的云层和有限的卫星存储资源，因而它们并不能真正解决AEOS调度遇到的问题。针对AEOS ^[7]，当前的研究主要在于提出和改进调度算法，优化卫星观测和任务调度^[8]。然而，AEOS采用的调度算法，在云层处理上，采用的是天气预报的预测云层，这一方法已经被学者认定不够精确^[9]；在考虑卫星在线存储资源上，主要通过使用占用内存小的调度算法进行卫星观测任务的调度和执行^[10]。这类研究没有针对观测任务本身的特性进行算法优化。当前的调度算法，在给AEOS调度时，仍没有考虑实时变换的云层和卫星有限的存储资源，然而这两个约束条件，已经严重影响卫星调度的观测结果和观测收益。

贪婪搜索算法(Greedy Search Algorithm, GSA)由于具有高效的算法执行效率和局部优化等特性，可以优先考虑调度任务的某些特性^[11]。因而，本文将该算法应用于考虑云层信息的AEOS调度，可以充分利用该算法的特性，优先考虑观测任务的云层遮挡以及调度卫星的有限存储资源，从而优化卫星调度的观测结果。

1 问题分析及建模

本文研究的问题是将GSA应用于考虑云层信息的AEOS的任务观测调度，从而提高观测收益和观测图像质量, 其具体的观测过程如图 1所示。

该问题研究的模型是AEOS的任务调度模型。模型的目标是最大化一个周期内的观测收益。模型的约束条件包括：实时的云层信息、卫星存储资源和任务截止时间。本章主要从云层和任务特点的角度分析问题，再结合调度理论进行问题建模^[12]。

从图 1可以看出，对于AEOS，其地面空间站主要负责修饰和传送任务，而真正负责任务调度和任务观测是敏捷卫星本身。这一因素要求能够适合于该环境下的调度算法运行时，必须占用较小的内存空间。

1.1 近似实时云层

云层分布是影响卫星任务观测结果图像质量的一个重要原因^[13]。在敏捷卫星进行任务观测时，空中动态的云层，往往对任务观测形成一定的遮挡。在以往的研究中，卫星调度往往采用天气预报云层。然而，依靠天气预报预测的云层分布信息并不可靠^[9]。为了提高AEOS的观测结果图像质量和观测收益，必须采用新的方式获取更为精确和实时的云层分布。AEOS，如法国空间站自主通用架构：测试与应用项目(Autonomy Generic Architecture: Test and Applications, AGATA)发射的卫星，自带云层观测设备^[14]，这一基础性装备能够用来捕捉云层信息，并且由于在实际观测中，卫星观测云层和观测任务的旋转角度已被固定^[9]，因而，根据卫星对地面的相对位置和角度关系，可以获取近似实时的云层分布情况。

如图 2所示，卫星在围绕地球运转的同时，可以观测β角度内的云层分布和θ角度内的任务分布。依据三角函数知识，可计算得到近似实时的云层分布，计算过程如式(1) 所示。

$ \left\{ \begin{array}{l} (h + R)/{\rm{sin}}({\rm{\pi - }}\alpha - \beta ) = R/{\rm{sin}}\beta \\ (h + R)/{\rm{sin}}({\rm{\pi - }}\theta {\rm{ - }}\omega ) = R/{\rm{sin}}\theta \\ {C_{{\rm{ms}}}} = {\rm{\pi \cdot}}{R^2}{\rm{\cdot}}{\alpha ^{\rm{2}}}\\ {T_{{\rm{ms}}}} = {\rm{\pi \cdot}}{R^2}{\rm{\cdot}}{\omega ^{\rm{2}}}\\ t = R\alpha /v \end{array} \right. $

(1)

式中：C_ms表示卫星在某一时间点可观测的云层覆盖区域；T_ms表示卫星在某一时间点可观测的任务覆盖区域；t表示云层分布近似不变的时间。根据式(1) 计算可得出如下结果：

$ \left\{ \begin{align} &t=R\text{ }\!\!\cdot\!\!\text{ }\left[\arcsin \langle \left( h+R \right)/R\text{ }\!\!\cdot\!\!\text{ }\sin \theta \rangle-\beta \right]/v \\ &{{C}_{\text{ms}}}=\text{ }\!\!\pi\!\!\text{ }\!\!\cdot\!\!\text{ }{{R}^{2}}\text{ }\!\!\cdot\!\!\text{ }{{\left[\arcsin \langle \left( h/R+1 \right)\text{ }\!\!\cdot\!\!\text{ sin}\beta \rangle-\beta \right]}^{2}} \\ &{{T}_{\text{ms}}}=\text{ }\!\!\pi\!\!\text{ }\!\!\cdot\!\!\text{ }{{R}^{2}}\text{ }\!\!\cdot\!\!\text{ }{{\left[\arcsin \langle \left( h/R+1 \right)\text{ }\!\!\cdot\!\!\text{ sin}\theta \rangle-\theta \right]}^{2}} \\ \end{align} \right. $

由于在实际观测中，云层变化很快，获取实时云层所需代价过高^[9]。同时，由于卫星观测时间与式(1) 中获得的云层分布近似不变时间t相比比较小，因而为了节约成本和提高卫星调度效率，本文将卫星获取的近似实时云层，当成卫星观测的实时云层信息。

1.2 观测任务

卫星的观测任务是由用户将观测指令发送给地面空间站，再由空间站处理之后发送给卫星得到，具体可见图 1。由于用户对任务观测结果有截止时间要求，因而任务观测必须满足相应的时间约束^[15]。同时，卫星调度需要考虑用户对观测结果的支付愿意和观测任务的大小。为了构建模型和调度方便，本文将观测任务i定义为S(s_i, p_i, t_obsⁱ, t_needⁱ)，其中各参数分别表示观测任务i的大小、用户支付意愿、任务观测时间和用户需求截止时间。

1.3 问题建模

本文主要是将GSA应用于考虑近似实时云层信息的AEOS的一个调度周期内，从而优化观测结果。在这个周期内，假设有n个观测任务。卫星调度的目标是使观测任务总收益最大化，其约束条件包括时间约束、资源约束和图像质量约束等。具体描述如下：

1) 观测收益。任务i的观测收益主要与图像质量和用户接收到观测结果的时间有关，其收益P_i=p_i*f_i(Q)*f_i(T)。其中：f_i(Q)=(s_i-$ \sum\limits_{j=1}^{m}{{{a}_{ij}}} $)/s_i表示任务i的观测结果的图像质量, s_i表示任务大小, a_ij表示第j个云层对任务i的遮挡大小；f_i(T)表示任务i观测结果的接收时间对观测收益的影响指标。根据用户对观测任务的需求时间的实际情况，任务收益的时间约束f(T)需满足如下条件：

$ {{f}_{i}}\left( T \right)=\left\{ \begin{align} &1, \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T\in (0, {{T}_{0}}^{i}] \\ &1/(T-{{T}_{0}}^{i}), T\in ({{T}_{0}}^{i}, {{T}_{1}}^{i}) \\ &0, \ \ \ \ \ \ \ \ \ \ \ \ \ T\in [{{T}_{1}}^{i}, +\infty ) \\ \end{align} \right. $

其中：T₀ⁱ表示用户最大满意时间；T₁ⁱ表示用户对任务i观测结果的截止时间要求；T表示用户的观测结果接收时间。任务收益约束f(T)可用图 3表示。

从图 3可以看出，时间对观测收益的影响指标随着用户接收任务观测结果的时间的增大而减小。

2) 时间约束。敏捷卫星对其能够完成的任务i需要满足一定的时间约束，即任务i需要在用户对其需求的截止时间内完成观测。因而必须满足如下约束：

$ {{t}_{\text{start}}}^{i}+{{t}_{\text{obs}}}^{i}+{{t}_{\text{adjust}}}^{i}<{{t}_{\text{need}}}^{i} $

其中：t_startⁱ表示任务i开始观测时间；t_obsⁱ表示任务i观测所需时间；t_adjustⁱ表示观测任务i的角度调整时间；t_needⁱ表示任务i的需求截止时间。该约束给出了敏捷卫星对于可完成的任务的时间约束。在任务观测调度中，该约束条件对卫星传送观测结果有一定的影响。

3) 资源约束。本文考虑的卫星调度的资源约束，主要是指卫星的存储资源。由于卫星存储资源有限，因而敏捷卫星决定观测任务i时，卫星存储资源必须满足：

$ \left\{ \begin{align} &{{S}_{im}}\le {{M}_{i}} \\ &\sum\limits_{j=1}^{i}{{{M}_{j}}\le M} \\ &{{M}_{r}}\ge 0 \\ \end{align} \right. $

其中：S_im表示观测任务i需要使用的存储空间；M_i表示卫星分配给任务i的存储空间；M_r表示卫星剩余的存储空间。

4) 图像质量约束。由于天空中时时存在的动态变化云层，卫星的观测结果图像往往带有一定的云层遮挡。在实际的任务观测中，用户对观测的结果图像有一个最低质量要求Q_um。当卫星决定观测该任务时，该任务观测结果图像f_i(Q)必须大于这个最低的图像清晰度要求。

综上所述，可以得出本文研究的问题规划模型：

$ \text{Max}\ \ \ \ \ P=\sum\limits_{i=1}^{n}{{{p}_{i}}{{f}_{i}}(Q){{f}_{i}}(T)} $

$ \text{s}\text{.t}\text{.}\left\{ \begin{align} &{{f}_{i}}(Q)\ge {{Q}_{um}} \\ &{{t}_{\text{start}}}^{i}+{{t}_{\text{obs}}}^{i}+{{t}_{\text{adjust}}}^{i}\le {{t}_{\text{need}}}^{i} \\ &{{T}_{0}}^{i}\le {{t}_{\text{need}}}^{i} \\ &{{S}_{im}}\le {{M}_{i}} \\ &0\le {{M}_{r}} \\ &\sum\limits_{j=1}^{i}{{{M}_{j}}{{x}_{j}}\le M} \\ &{{s}_{j}}=0, \ \ \ \ \ \text{如果任务}j\text{被传送} \\ &{{x}_{j}}=1, \ \ \ \ \ \text{如果任务}j未被传送 \\ \end{align} \right. $

从该问题模型可以看出，本文的研究符合传统的调度问题。由于GSA被广泛应用于传统的调度问题，因而本文将该算法应用于考虑实时云层信息的AEOS的调度具有科学依据和应用基础。

2 算法设计

在以往的研究中，被普遍应用于传统观测卫星调度和AEOS调度的成熟算法主要有动态规划算法和局部搜索算法^[16-18]。动态规划算法(Dynamic Programming Algorithm, DPA)是一个能够在O(n²)或O(n³)解决很多不同类型问题的强有力的算法^[19]。这一算法已经被成功地应用于解决非AEOS的观测调度^[20]。局部搜索算法(Local Search Algorithm, LSA)是被用于解决高度组合问题的通用算法，并且它已经被成功高效地应用于解决卫星调度问题^[21]。GSA应用于调度问题中时，能够快速获得合理的解，并且该算法可以根据持续偏好的原则，产生调度决策。同时，该算法要求当前的调度决策不影响之后的调度策略^[4]。

将GSA应用于卫星观测调度中，可以高效地获得局部最优的观测结果。且由于该算法具有依据持续偏好的原则获得最优解的特点^[22]，在本文研究中，该算法将优先选择待观测任务的观测结果图像质量较高的任务，作为算法调度持续偏好的准则。因而，卫星选择观测任务之前，首先观测云层分布，并根据待观测任务的图像质量对观测任务进行排序，结合考虑任务截止时间和内存资源等约束条件，选择任务进行观测。具体流程如图 4所示。

在图 4中，c′和c″均表示重新观测之后任务的云层遮挡大小。从图 4可以看出，本文的卫星调度优先考虑待观测任务图像质量较高的任务，在选择具体的任务进行观测时，会考虑卫星的存储资源、任务的观测收益以及任务截止时间等约束条件。图 4选取4个任务作为实例，说明贪心思想在卫星调度中的应用。本实例中，卫星优先观测满足图像质量约束的p₁、p₂、p₃任务。但是，为了说明其他诸如卫星存储资源等约束条件会对观测任务产生影响，本实例在一次观测中仅仅观测图像质量较好的p₁、p₃任务。与传统的卫星调度相比，本文方案将云层信息考虑在算法的优化执行中，可以有效地提高观测任务的图像质量，从而提高客户满意度，带来更高的观测收益。具体的执行伪代码如下：

输入  任务信息S(p, s, t_need, t_obs)；卫星参数(M, θ, β)；任务角度调整时间t_adjust；任务观测周期T；任务开始时间t_start；任务初始收益P=0。

输出  卫星调度计划。

begin

while t ≤ T do

  if task-list is none then

     perform task download;

  end if

  if task is new then {

     perform cloud detection;

     perform orbit maneuver;

     t=t+t_adjust; }

  end if

  ① Rank (task-list);

  Schedule{

     select (task);

  ② if task i suits to the requirements {

$ \left\{ \begin{align} &{{f}_{i}}(Q)\ge {{Q}_{um}} \\ &{{t}_{\text{start}}}^{i}+{{t}_{\text{obs}}}^{i}+{{t}_{\text{adjust}}}^{i}\le {{t}_{\text{need}}}^{i} \\ &{{T}_{0}}^{i}\le {{t}_{\text{need}}}^{i} \\ &{{S}_{im}}\le {{M}_{i}} \\ \end{align} \right. $

   }

   then {

                /*the requirements includes satellite memory

                            and task deadline requirements*/

     perform task observation；

$ \begin{align} &t=t+{{t}_{\text{obs}}}; \\ &{{M}_{r}}={{M}_{r}}-\sum\limits_{i}^{nb}{{{S}_{i}};/*\sum\limits_{i}^{nb}{{{S}_{i}}\text{表示该观测占用的内存*/ }\!\!\}\!\!\text{ }}} \\ \end{align} $

  end if

  if task-list is not none then{

     perform orbit maneuver;

     perform cloud detection;

     t=t+t_adjust; }

  end if

  if random I > r then{           /*随机太阳能充电*/

     perform sun pointing；

     t=t+t_adjust; }

  end if

  if random(p) < p then {/*随机选择传送已完成的任务*/

     transmit completed tasks to ground station;

$ \begin{align} &P=P+\sum\limits_{i}^{ns}{{{p}_{i}}\text{ }\!\!\cdot\!\!\text{ }{{f}_{i}}(Q)\text{ }\!\!\cdot\!\!\text{ }{{f}_{i}}(T)}; \\ &{{M}_{r}}={{M}_{r}}+\sum\limits_{i}^{ns}{{{S}_{i}};\ \ \ \ \ \ \ \ /*ns\text{表示完成的任务数*/ }\!\!\}\!\!\text{ }} \\ \end{align} $

  end if

  For any task i in the observed task-list {

     if t_need -t > 0 then {

       send task i to the ground station;

       M_r=M_r+S_i;

       P=P+p_i·f_i(Q)·f_i(T); }

     end if

  }

end

在上面的算法伪代码描述中，① Rank(task-list)表示贪心算法根据待观测任务的结果即图像质量对待观测列表进行排序。② 中满足的约束包括：图像质量约束、任务时间约束以及卫星存储约束。因而，从以上算法伪代码可以看出，GSA优先考虑了观测任务的云层遮挡情况，并在考虑近似实时的云层信息的基础上，充分结合了卫星的有限存储资源和任务本身的时间约束，进行任务的调度和观测。同时，从以上算法伪代码中可以看出，该算法在原有基础上加入了随机将完成任务传输给用户的特点，从而减轻了卫星调度的内存压力，并提高了该卫星调度的调度效率。

3 实验结果及分析

为了验证GSA在考虑云层信息的敏捷卫星调度中应用的优越性，本章进行相关的对比实验。在敏捷卫星调度领域常用的调度算法包括动态规划和局部搜索算法等，而对于考虑实时云层的卫星调度问题并没有被很好地研究，因而并不存在常用的调度算法。由于敏捷卫星调度问题的特殊性，包括本身有限稀缺的存储资源和运算资源，应用于传统调度问题的智能算法，均不能应用于该调度问题。因而，为了验证GSA比较适合应用于敏捷卫星调度，本文将GSA与常用于卫星调度的动态规划算法和局部搜索算法在该调度问题上进行实验结果对比。该实验主要做了关于卫星调度的任务观测收益、图像质量以及卫星内存利用率的对比实验。该实验在装载有Core i5-5200U CPU@ 2.20 GHz处理器的PC上运行。实验所需的输入数据和相关参数可根据Beaumet等^[9]的研究获得。其中，部分相关数据可见表 1~2。

由于论文篇幅限制，表 2列出了前10个任务的属性。本文仿真实验的任务收益是从[1, 10]中随机生成，任务大小所需内存分布在8 MB和15 MB之间，任务截止时间分布在300~600 s内，任务的观测时间分布在5~15 s内^[9]。

本文的实验，对比了一个周期内，任务个数分别是50、100、200、400情况下，GSA、DPA和LSA三种算法的收益、平均任务完成时间、图像质量和内存占用率的情况，其中不同算法的收益和平均任务完成时间分别如表 3~4所示。

从表 3中可以看出，随着任务数的增长，三种算法卫星调度的总收益均在增长，并且对于相同任务量，GSA比DPA和LSA能使卫星调度获得更多的观测收益。在任务量为100的情况下，与DPA相比，将GSA应用于AEOS调度能够将任务观测得到的总收益提高14.82%；与LSA相比，将GSA应用于AEOS调度能够将任务观测得到的总收益提高10.32%。这说明将GSA应用于考虑云层的卫星调度比DPA和LSA能够获得更大的收益。

从表 4中可以看出，GSA在任务平均完成时间上比DPA和LSA需要更多的时间。但是，从表 4中也可以看出，GSA仅仅多花了1~2 s的时间优化观测结果。其中，在任务量为100时，GSA需要46.554 1 s，DPA需要45.231 6 s，LSA需要46.365 4 s。由此可以看出，GSA需要用的时间最多，但是GSA在算法收益和图像质量上，均比其他两种算法优越。综合考虑观测收益、图像质量和任务平均完成时间，可以得出，GSA具有更高的优越性，其平均只需多花1~2 s的时间，就能给用户提供更为优质的服务和观测结果。

由于本文的部分输入数据是根据现有的相关研究成果获得，因而为了寻找GSA在实际应用中最佳的求解性能参数，本文对比了任务量为100时，任务周期分别为2 400 s、3 600 s、4 800 s以及客户最大满意时间分别为60 s、90 s、120 s时，GSA应用于卫星调度的运行结果, 具体结果如表 5~6所示。

从表 5可以看出，随着任务观测周期变长，任务观测收益不断增多，但增幅变小，所需任务平均观测时间越来越多，任务平均观测质量越来越好。

从表 6中可以看出，随着客户最大满意时间变长，任务观测收益不断增多，但增幅变小，所需任务平均观测时间先变小后变多，任务平均观测质量越来越好。

为了更进一步对比GSA、LSA和DPA三种算法应用于卫星调度的情况，本文选取一个周期内任务数为100的情况下进行对比实验，性能对比结果如图 5所示。

从图 5可以看出，GSA应用于考虑云层的卫星调度，可以获得更高质量的图像，同时该算法对卫星的内存使用率较小。从图 5的曲线波动可以看出，GSA在观测得到的图像质量波动和内存使用率变化上，均比LSA和DPA稳定。这说明GSA比其他两个卫星调度常用算法更符合考虑云层情况下的卫星调度观测问题。

4 结语

本文利用数学三角函数知识构建获取近似实时云层的模型，能够解决传统AEOS调度问题中，图像观测质量受云层遮挡严重影响的问题。由于任务观测时间短和新任务开始前重新观测云层的特点，近似实时云层可以看作是实时变化的云层。将实时变化的云层信息纳入卫星任务的观测调度中，能够有效地提高卫星任务观测的结果图像质量。由于GSA不仅具有局部优化和算法执行占用内存小的特点，该算法还能根据一定的偏好进行算法的执行，其算法特性使得其比较符合考虑实时云层信息的AEOS的调度。本文将GSA应用于解决考虑实时变换云层的卫星调度问题，能够优先观测图像质量高的任务，从而能够提高卫星调度的任务观测图像质量、观测收益以及优化卫星的内存使用率。

在理论分析和算法设计的基础上，本文的仿真实验主要对比了GSA和常用于该领域的LSA和DPA，在不同任务量情况下，其观测收益、图像质量、内存使用率以及任务平均观测时间上的不同。对比结果表明，GSA总体收益、任务观测图像质量和内存利用率上，均比其他两种算法具有性能更优。

本文接下来的工作是基于GSA在考虑云层的AEOS调度应用的基础上，控制其他资源组合并进行优化，得到一个调度周期内最优的任务调度数量，从而给卫星的任务调度客户承载量提供一定的建议。