贪婪搜索算法在卫星调度中的应用

单国厚，刘 建，水 艳，李丽华，喻光晔

(1.中国科学技术大学 管理学院，合肥 230026； 2.淮河流域水资源保护局 淮河水资源保护科学研究所，安徽 蚌埠 230000)

贪婪搜索算法在卫星调度中的应用

单国厚1*，刘 建2，水 艳2，李丽华2，喻光晔2

(1.中国科学技术大学 管理学院，合肥 230026； 2.淮河流域水资源保护局 淮河水资源保护科学研究所，安徽 蚌埠 230000)

(*通信作者电子邮箱jackshan@mail.ustc.edu.cn)

针对采用天气预报的滞后云层进行卫星调度影响观测图像质量和观测收益的问题，提出一种获取实时云层的数学模型，并基于此构建考虑实时变换云层的敏捷观测卫星(AEOS)调度模型。由于贪婪搜索算法(GSA)具有局部优化的特性，能够充分考虑卫星观测的云层和有限存储资源等约束，研究了GSA在该卫星调度问题中的应用。首先，GSA优先考虑观测任务的云层遮挡，并根据云层遮挡大小，计算待观测任务的图像质量，将之排序选择待观测的任务；其次，结合任务的大小、截止时间和卫星的存储资源约束，选择能够给观测收益带来最大化的任务；最后，进行观测和任务传送。仿真实验表明，在任务数为100的情况下，采用GSA进行卫星调度的任务收益比常用于卫星调度的动态规划算法(DPA) 所获得任务收益提高了14.82%，比局部搜索算法(LSA) 所获得任务收益提高了10.32%，并且同等条件下，采用GSA得到的观测图像的质量比其他两种方法得到的图像质量更高。实验结果表明，GSA在实际卫星调度中，能够有效地提高图像观测质量和任务观测收益。

卫星调度；贪婪搜索算法；近似实时云层；任务收益；图像质量

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

1.1 近似实时云层

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

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

(1)

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

图2 卫星云层角度关系

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

1.2 观测任务

1.3 问题建模

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

图3 时间对观测收益的影响指标

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

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

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

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

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

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

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

2 算法设计

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

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

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

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

输出 卫星调度计划。

beginwhilet≤Tdoiftask-listisnonethenperformtaskdownload;

endif

iftaskisnewthen{performclouddetection;performorbitmaneuver;t=t+tadjust;}

endif

①Rank(task-list);

Schedule{

}

then{

/*therequirementsincludessatellitememory

endif

iftask-listisnotnonethen{performorbitmaneuver;performclouddetection;t=t+tadjust;}

endif

ifrandomI>rthen{

其他特征变量对住宅价格也有一定的影响．建筑面积每增加1%,住宅价格增加0.213%;建筑年龄每减少1%,住宅价格增加0.032%;小区容积率每增加1%,住宅价格增加0.059%;装修程度每提升一个等级,住宅价格增加3.05%;朝南的住宅比其他方向的住宅价格高出6.18%;住宅至最近商圈距离每增加1%,住宅价格降低0.033%;住宅至CBD距离每增加1%,住宅价格降低0.078%;物业水平每增加1%,住宅价格增加0.075%．

/*随机太阳能充电*/performsunpointing；t=t+tadjust;}

endif

ifrandom(p)>pthen {

/*ns表示完成的任务数*/}

endif

Foranytaskiintheobservedtask-list{iftneed-t>0then{sendtaskitothegroundstation;Mr=Mr+Si;P=P+pi·fi(Q)·fi(T);}

endif

}

end

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

图4 GSA在卫星调度的应用

3 实验结果及分析

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

由于论文篇幅限制，表2列出了前10个任务的属性。本文仿真实验的任务收益是从[1,10]中随机生成，任务大小所需内存分布在8MB和15MB之间，任务截止时间分布在300～600s内，任务的观测时间分布在5～15s内[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能够获得更大的收益。

表1 恒定输入变量

表2 前10个任务的任务属性

表3 不同任务数情况下不同算法的收益对比

表4 不同任务数情况下不同算法任务平均完成时间对比s

Tab. 4 Task average completion time comparison ofdifferent algorithms under different task numberss

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

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

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

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

表5 不同任务周期下GSA算法运行结果比较

表6 不同客户最大满意时间下GSA运行结果比较

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

图5 不同算法性能对比

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

4 结语

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

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

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

)

[1] 郑义成,袁茵,邓勇,等.基于Pareto前沿与粒子群优化的卫星资源调度算法[J].计算机工程,2016,42(1):193-198.(ZHENGYC,YUANY,DENGY,etal.SatelliteresourceschedulingalgorithmbasedonParetofrontandparticleswarmoptimization[J].ComputerEngineering, 2016, 42(1): 193-198.)

[2]KAUFMANYJ,TANRÉD,REMERLA,etal.OperationalremotesensingoftroposphericaerosoloverlandfromEOSmoderateresolutionimagingspectroradiometer[J].JournalofGeophysicalResearch:Atmospheres, 1997, 102(D14): 17051-17067.

[3] 邱涤珊,谈群,马满好,等.卫星成像侦察需求满足度评价方法研究[J].计算机工程,2012,38(8):256-259.(QIUDS,TANQ,MAMH,etal.Researchonsatisfieddegreeevaluationmethodforsatelliteimagingreconnaissancerequirement[J].ComputerEngineering, 2012, 38(8): 256-259.)

[4]LEMATREM,VERFAILLIEG,JOUHAUDF,etal.Selectingandschedulingobservationsofagilesatellites[J].AerospaceScienceandTechnology, 2002, 6(5): 367-381.

[5]WOLFEWJ,SORENSENSE.Threeschedulingalgorithmsappliedtotheearthobservingsystemsdomain[J].ManagementScience, 2000, 46(1): 148-166.

[6]BEAUMETG.Continuousplanningforthecontrolofanautonomousagilesatellite[EB/OL]. [2016- 10- 16].http://icaps06.icaps-conference.org/dc-papers/paper1.pdf.

[7]CHIENS,SHERWOODR,TRAND,etal.Theautonomoussciencecraftembeddedsystemsarchitecture[C]//Proceedingsofthe2005IEEEInternationalConferenceonSystems,ManandCybernetics.Piscataway,NJ:IEEE, 2005: 3927-3932.

[8]TANGPATTANAKULP,JOZEFOWIEZN,LOPEZP.Multi-objectiveoptimizationforselectingandschedulingobservationsbyagileearthobservingsatellites[C]//Proceedingsofthe2012InternationalConferenceonParallelProblemSolvingfromNature,LNCS7492.Berlin:Springer, 2012: 112-121.

[9]BEAUMETG,VERFAILLIEG,CHARMEAUMC.Feasibilityofautonomousdecisionmakingonboardanagileearth-observingsatellite[J].ComputationalIntelligence, 2011, 27(1): 123-139.

[10]WANGJJ,ZHUXM,YANGLT,etal.Towardsdynamicreal-timeschedulingformultipleearthobservationsatellites[J].JournalofComputerandSystemSciences, 2015, 81(1): 110-124.

[11]CHENY,ZHANGDY,ZHOUMQ,etal.Multi-satelliteobservationschedulingalgorithmbasedonhybridgeneticparticleswarmoptimization[M]//AdvancesinInformationTechnologyandIndustryApplications.Berlin:Springer, 2012: 441-448.

[12]GRAVESSC.Areviewofproductionscheduling[J].Operationsresearch, 1981, 29(4): 646-675.

[13]WANGJ,DEMEULEMEESTERE,QIUD.Apureproactiveschedulingalgorithmformultipleearthobservationsatellitesunderuncertaintiesofclouds[J].ComputersandOperationsResearch, 2016, 74(C): 1-13.

[14]CHARMEAUMC,POULYJ,BENSANAE,etal.TestingspacecraftautonomywithAGATA[EB/OL]. [2016- 10- 16].http://robotics.estec.esa.int/i-SAIRAS/isairas2008/Proceedings/SESSION%2022/m102-Charmeau.pdf.

[15]CHIENS,SHERWOODR,TRAND,etal.Usingautonomyflightsoftwaretoimprovesciencereturnonearthobservingone[J].JournalofAerospaceComputing,Information,andCommunication, 2005, 2(4): 196-216.

[16]TZIRKEL-HANCOCKE.Patternmatchingmethod,apparatusandcomputerreadablememorymediumforspeechrecognitionusingdynamicprogramming:US, 5960395 [P]. 1999- 9- 28.

[17]LARSENB,AONEC.Fastandeffectivetextminingusinglinear-timedocumentclustering[C]//ProceedingsoftheFifthACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACM, 1999: 16-22.

[18]RABIDEAUG,KNIGHTR,CHIENS,etal.IterativerepairplanningforspacecraftoperationsusingtheASPENsystem[EB/OL]. [2016- 10- 16].http://www.metahack.org/isairas99-aspen.pdf.

[19]SMITHDK.Dynamicprogrammingandoptimalcontrol.volume1 [J].JournaloftheOperationalResearchSociety, 1996, 47(6): 833-834.

[20]DAMIANIS,VERFAILLIEG,CHARMEAUMC.Ananytimeplanningapproachforthemanagementofanearthwatchingsatellite[EB/OL]. [2016- 10- 16].http://robotics.estec.esa.int/IWPSS/IWPSS_2004/workshop/works/6/006-verfaillie.pdfI

[21]AARTSE,LENSTRAJK.LocalSearchinCombinatorialOptimization[M].Princeton,NJ:PrincetonUniversityPress, 2003: 20-40.

[22]BENSANAE,VERFAILLIEG,AGNESEJC,etal.Exact&inexactmethodsfordailymanagementofearthobservationsatellite[C]//SpaceOps1996:ProceedingsoftheFourthInternationalSymposiumonSpaceMissionOperationsandGroundDataSystems.Paris:EuropeanSpaceAgency, 1996: 507-514.

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(71671168),theNationalScienceandTechnologyMajorProject(2014ZX07204- 006- 05).

SHAN Guohou, born in 1992, M. S. candidate. His research interests include satellite schedule, intelligent algorithm optimization.

LIU Jian, born in 1961, Ph. D., professor of engineer. His research interests include water resource schedule, intelligent algorithm optimization.

SHUI Yan, born in 1982, M. S., senior engineer. Her research interests include water resource schedule, intelligent algorithm optimization.

LI Lihua, born in 1990, M. S., engineer. Her research interests include water resource schedule, intelligent algorithm optimization.

YU Guangye, born in 1990, M. S., engineer. His research interests include water resource schedule, intelligent algorithm optimization.

Application of greedy search algorithm in satellite scheduling

SHAN Guohou1*, LIU Jian2, SHUI Yan2, LI Lihua2, YU Guangye2

(1.SchoolofManagement,UniversityofScienceandTechnologyofChina,HefeiAnhui230026,China; 2.ScientificResearchDepartmentofWaterResourcePreservationonHuaiheRiver,WaterResourcePreservationDeputyofHuaiheRiver,BengbuAnhui230000,China))

In order to solve the problem that observational image quality and profits are low in satellite scheduling by adopting lagged weather forecast cloud information, a mathematic model capturing real-time cloud distribution was proposed. The Agile Earth Observation Satellite (AEOS) scheduling model was also built based on the real-time cloud information. Considering the local optimization of Greedy Search Algorithm (GSA) and it can give full consideration for constraints such as cloud of satellite observation and limited storage resources, the applications of GSA for the satellite scheduling problem were researched. Firstly, the cloud coverage of observation task was considered in priority order by GSA. The image quality value of observation task was calculated according to the size of cloud coverage and the observation task was selected by the sort of the image quality value. Secondly, the task with the maximize profit was selected according to task size, deadline and satellite storage resource. Finally, satellite observation and task transmission were completed according to their ability of improving profit. The simulation experiments show that, on the case of 100 tasks, the task profit of satellite schedule adopting GSA was improved by 14.82% and 10.32% compared with the Dynamic Programming Algorithm (DPA) and Local Search Algorithm (LSA) respectively. Besides, the image quality of applying GSA is higher than taking DPA and LSA in the same circumstance. The experimental results show that the GSA can effectively improve the image observation quality and task observation profit of satellite scheduling.

satellite scheduling; Greedy Search Algorithm (GSA); nearly real-time cloud; task profit; image quality

2016- 11- 16;;

2017- 01- 04。

国家自然科学基金资助项目(71671168)；国家重大科技专项(2014ZX07204- 006- 05)。

单国厚(1992—)，男，安徽滁州人，硕士研究生，主要研究方向：卫星调度、智能算法优化； 刘建(1961—)，男，安徽蚌埠人，教授级工程师，博士，主要研究方向：水资源调度、智能算法优化； 水艳(1982—)，女，安徽繁昌人，高级工程师，硕士，主要研究方向：水资源调度、智能算法优化； 李丽华(1990—)，女，河南郑州人，工程师，硕士，主要研究方向：水资源调度、智能算法优化； 喻光晔(1990—)，男，湖北随州人，工程师，硕士，主要研究方向：水资源调度、智能算法优化。

1001- 9081(2017)06- 1814- 06

10.11772/j.issn.1001- 9081.2017.06.1814

TN927.2

A