貪婪搜索算法在衛星調度中的應用

單國厚，劉 建，水 艷，李麗華，喻光曄

(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