貪婪搜索算法在衛(wèi)星調(diào)度中的應用

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

(1.中國科學技術大學 管理學院，合肥 230026； 2.淮河流域水資源保護局 淮河水資源保護科學研究所，安徽 蚌埠 230000)

貪婪搜索算法在衛(wèi)星調(diào)度中的應用

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

(1.中國科學技術大學 管理學院，合肥 230026； 2.淮河流域水資源保護局 淮河水資源保護科學研究所，安徽 蚌埠 230000)

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

針對采用天氣預報的滯后云層進行衛(wèi)星調(diào)度影響觀測圖像質(zhì)量和觀測收益的問題，提出一種獲取實時云層的數(shù)學模型，并基于此構(gòu)建考慮實時變換云層的敏捷觀測衛(wèi)星(AEOS)調(diào)度模型。由于貪婪搜索算法(GSA)具有局部優(yōu)化的特性，能夠充分考慮衛(wèi)星觀測的云層和有限存儲資源等約束，研究了GSA在該衛(wèi)星調(diào)度問題中的應用。首先，GSA優(yōu)先考慮觀測任務的云層遮擋，并根據(jù)云層遮擋大小，計算待觀測任務的圖像質(zhì)量，將之排序選擇待觀測的任務；其次，結(jié)合任務的大小、截止時間和衛(wèi)星的存儲資源約束，選擇能夠給觀測收益帶來最大化的任務；最后，進行觀測和任務傳送。仿真實驗表明，在任務數(shù)為100的情況下，采用GSA進行衛(wèi)星調(diào)度的任務收益比常用于衛(wèi)星調(diào)度的動態(tài)規(guī)劃算法(DPA) 所獲得任務收益提高了14.82%，比局部搜索算法(LSA) 所獲得任務收益提高了10.32%，并且同等條件下，采用GSA得到的觀測圖像的質(zhì)量比其他兩種方法得到的圖像質(zhì)量更高。實驗結(jié)果表明，GSA在實際衛(wèi)星調(diào)度中，能夠有效地提高圖像觀測質(zhì)量和任務觀測收益。

衛(wèi)星調(diào)度；貪婪搜索算法；近似實時云層；任務收益；圖像質(zhì)量

0 引言

地球觀測衛(wèi)星在觀測地面物體和活動中，起著很重要的作用[1-2]。隨著敏捷觀測衛(wèi)星(Agile Earth Observation Satellite, AEOS)，特別是具有自主優(yōu)化性質(zhì)的AEOS 的廣泛應用，衛(wèi)星調(diào)度遇到新的挑戰(zhàn)[3-4]：有限的在線存儲資源和實時變換的云層信息。目前，針對衛(wèi)星調(diào)度的研究主要分為兩類：傳統(tǒng)的衛(wèi)星調(diào)度研究和AEOS 調(diào)度的研究。傳統(tǒng)的觀測衛(wèi)星只負責調(diào)度計劃的執(zhí)行，其調(diào)度過程是由地面空間站結(jié)合任務特性、預測云層分布以及存儲空間等的資源約束所規(guī)劃[5]。由于地面空間的存儲資源、運算資源等比較豐富，傳統(tǒng)衛(wèi)星調(diào)度的研究主要是考慮實際條件和任務約束等，提出和改進算法，優(yōu)化觀測結(jié)果[6]。然而，由于傳統(tǒng)衛(wèi)星調(diào)度得到的優(yōu)化算法，并沒有考慮動態(tài)變化的云層和有限的衛(wèi)星存儲資源，因而它們并不能真正解決AEOS 調(diào)度遇到的問題。針對AEOS[7]，當前的研究主要在于提出和改進調(diào)度算法，優(yōu)化衛(wèi)星觀測和任務調(diào)度[8]。然而，AEOS 采用的調(diào)度算法，在云層處理上，采用的是天氣預報的預測云層，這一方法已經(jīng)被學者認定不夠精確[9]；在考慮衛(wèi)星在線存儲資源上，主要通過使用占用內(nèi)存小的調(diào)度算法進行衛(wèi)星觀測任務的調(diào)度和執(zhí)行[10]。這類研究沒有針對觀測任務本身的特性進行算法優(yōu)化。當前的調(diào)度算法，在給AEOS 調(diào)度時，仍沒有考慮實時變換的云層和衛(wèi)星有限的存儲資源，然而這兩個約束條件，已經(jīng)嚴重影響衛(wèi)星調(diào)度的觀測結(jié)果和觀測收益。

貪婪搜索算法(Greedy Search Algorithm, GSA)由于具有高效的算法執(zhí)行效率和局部優(yōu)化等特性，可以優(yōu)先考慮調(diào)度任務的某些特性[11]。因而，本文將該算法應用于考慮云層信息的AEOS 調(diào)度，可以充分利用該算法的特性，優(yōu)先考慮觀測任務的云層遮擋以及調(diào)度衛(wèi)星的有限存儲資源，從而優(yōu)化衛(wèi)星調(diào)度的觀測結(jié)果。

1 問題分析及建模

本文研究的問題是將GSA應用于考慮云層信息的AEOS 的任務觀測調(diào)度，從而提高觀測收益和觀測圖像質(zhì)量,其具體的觀測過程如圖1所示。

該問題研究的模型是AEOS 的任務調(diào)度模型。模型的目標是最大化一個周期內(nèi)的觀測收益。模型的約束條件包括：實時的云層信息、衛(wèi)星存儲資源和任務截止時間。本章主要從云層和任務特點的角度分析問題，再結(jié)合調(diào)度理論進行問題建模[12]。

圖1 AEOS觀測過程

從圖1可以看出，對于AEOS，其地面空間站主要負責修飾和傳送任務，而真正負責任務調(diào)度和任務觀測是敏捷衛(wèi)星本身。這一因素要求能夠適合于該環(huán)境下的調(diào)度算法運行時，必須占用較小的內(nèi)存空間。

1.1 近似實時云層

云層分布是影響衛(wèi)星任務觀測結(jié)果圖像質(zhì)量的一個重要原因[13]。在敏捷衛(wèi)星進行任務觀測時，空中動態(tài)的云層，往往對任務觀測形成一定的遮擋。在以往的研究中，衛(wèi)星調(diào)度往往采用天氣預報云層。然而，依靠天氣預報預測的云層分布信息并不可靠[9]。為了提高AEOS 的觀測結(jié)果圖像質(zhì)量和觀測收益，必須采用新的方式獲取更為精確和實時的云層分布。AEOS，如法國空間站自主通用架構(gòu)：測試與應用項目(Autonomy Generic Architecture: Test and Applications, AGATA)發(fā)射的衛(wèi)星，自帶云層觀測設備[14]，這一基礎性裝備能夠用來捕捉云層信息，并且由于在實際觀測中，衛(wèi)星觀測云層和觀測任務的旋轉(zhuǎn)角度已被固定[9]，因而，根據(jù)衛(wèi)星對地面的相對位置和角度關系，可以獲取近似實時的云層分布情況。

如圖2所示，衛(wèi)星在圍繞地球運轉(zhuǎn)的同時，可以觀測β角度內(nèi)的云層分布和θ角度內(nèi)的任務分布。依據(jù)三角函數(shù)知識，可計算得到近似實時的云層分布，計算過程如式(1)所示。

(1)

式中：Cms表示衛(wèi)星在某一時間點可觀測的云層覆蓋區(qū)域；Tms表示衛(wèi)星在某一時間點可觀測的任務覆蓋區(qū)域；t表示云層分布近似不變的時間。根據(jù)式(1)計算可得出如下結(jié)果：

圖2 衛(wèi)星云層角度關系

由于在實際觀測中，云層變化很快，獲取實時云層所需代價過高[9]。同時，由于衛(wèi)星觀測時間與式(1)中獲得的云層分布近似不變時間t相比比較小，因而為了節(jié)約成本和提高衛(wèi)星調(diào)度效率，本文將衛(wèi)星獲取的近似實時云層，當成衛(wèi)星觀測的實時云層信息。

1.2 觀測任務

1.3 問題建模

本文主要是將GSA應用于考慮近似實時云層信息的AEOS的一個調(diào)度周期內(nèi)，從而優(yōu)化觀測結(jié)果。在這個周期內(nèi)，假設有n個觀測任務。衛(wèi)星調(diào)度的目標是使觀測任務總收益最大化，其約束條件包括時間約束、資源約束和圖像質(zhì)量約束等。具體描述如下：

圖3 時間對觀測收益的影響指標

從圖3可以看出，時間對觀測收益的影響指標隨著用戶接收任務觀測結(jié)果的時間的增大而減小。

2)時間約束。敏捷衛(wèi)星對其能夠完成的任務i需要滿足一定的時間約束，即任務i需要在用戶對其需求的截止時間內(nèi)完成觀測。因而必須滿足如下約束：

3)資源約束。本文考慮的衛(wèi)星調(diào)度的資源約束，主要是指衛(wèi)星的存儲資源。由于衛(wèi)星存儲資源有限，因而敏捷衛(wèi)星決定觀測任務i時，衛(wèi)星存儲資源必須滿足：

其中：Sim表示觀測任務i需要使用的存儲空間；Mi表示衛(wèi)星分配給任務i的存儲空間；Mr表示衛(wèi)星剩余的存儲空間。

4)圖像質(zhì)量約束。由于天空中時時存在的動態(tài)變化云層，衛(wèi)星的觀測結(jié)果圖像往往帶有一定的云層遮擋。在實際的任務觀測中，用戶對觀測的結(jié)果圖像有一個最低質(zhì)量要求Qum。當衛(wèi)星決定觀測該任務時，該任務觀測結(jié)果圖像fi(Q)必須大于這個最低的圖像清晰度要求。

綜上所述，可以得出本文研究的問題規(guī)劃模型：

從該問題模型可以看出，本文的研究符合傳統(tǒng)的調(diào)度問題。由于GSA被廣泛應用于傳統(tǒng)的調(diào)度問題，因而本文將該算法應用于考慮實時云層信息的AEOS的調(diào)度具有科學依據(jù)和應用基礎。

2 算法設計

在以往的研究中，被普遍應用于傳統(tǒng)觀測衛(wèi)星調(diào)度和AEOS調(diào)度的成熟算法主要有動態(tài)規(guī)劃算法和局部搜索算法[16-18]。動態(tài)規(guī)劃算法(DynamicProgrammingAlgorithm,DPA)是一個能夠在O(n2)或O(n3)解決很多不同類型問題的強有力的算法[19]。這一算法已經(jīng)被成功地應用于解決非AEOS的觀測調(diào)度[20]。局部搜索算法(LocalSearchAlgorithm,LSA)是被用于解決高度組合問題的通用算法，并且它已經(jīng)被成功高效地應用于解決衛(wèi)星調(diào)度問題[21]。GSA應用于調(diào)度問題中時，能夠快速獲得合理的解，并且該算法可以根據(jù)持續(xù)偏好的原則，產(chǎn)生調(diào)度決策。同時，該算法要求當前的調(diào)度決策不影響之后的調(diào)度策略[4]。

將GSA應用于衛(wèi)星觀測調(diào)度中，可以高效地獲得局部最優(yōu)的觀測結(jié)果。且由于該算法具有依據(jù)持續(xù)偏好的原則獲得最優(yōu)解的特點[22]，在本文研究中，該算法將優(yōu)先選擇待觀測任務的觀測結(jié)果圖像質(zhì)量較高的任務，作為算法調(diào)度持續(xù)偏好的準則。因而，衛(wèi)星選擇觀測任務之前，首先觀測云層分布，并根據(jù)待觀測任務的圖像質(zhì)量對觀測任務進行排序，結(jié)合考慮任務截止時間和內(nèi)存資源等約束條件，選擇任務進行觀測。具體流程如圖4所示。

在圖4中，c′和c″均表示重新觀測之后任務的云層遮擋大小。從圖4可以看出，本文的衛(wèi)星調(diào)度優(yōu)先考慮待觀測任務圖像質(zhì)量較高的任務，在選擇具體的任務進行觀測時，會考慮衛(wèi)星的存儲資源、任務的觀測收益以及任務截止時間等約束條件。圖4選取4個任務作為實例，說明貪心思想在衛(wèi)星調(diào)度中的應用。本實例中，衛(wèi)星優(yōu)先觀測滿足圖像質(zhì)量約束的p1、p2、p3任務。但是，為了說明其他諸如衛(wèi)星存儲資源等約束條件會對觀測任務產(chǎn)生影響，本實例在一次觀測中僅僅觀測圖像質(zhì)量較好的p1、p3任務。與傳統(tǒng)的衛(wèi)星調(diào)度相比，本文方案將云層信息考慮在算法的優(yōu)化執(zhí)行中，可以有效地提高觀測任務的圖像質(zhì)量，從而提高客戶滿意度，帶來更高的觀測收益。具體的執(zhí)行偽代碼如下：

輸入 任務信息S(p,s,tneed,tobs)；衛(wèi)星參數(shù)(M,θ,β)；任務角度調(diào)整時間tadjust；任務觀測周期T；任務開始時間tstart；任務初始收益P=0。

輸出 衛(wèi)星調(diào)度計劃。

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%;小區(qū)容積率每增加1%,住宅價格增加0.059%;裝修程度每提升一個等級,住宅價格增加3.05%;朝南的住宅比其他方向的住宅價格高出6.18%;住宅至最近商圈距離每增加1%,住宅價格降低0.033%;住宅至CBD距離每增加1%,住宅價格降低0.078%;物業(yè)水平每增加1%,住宅價格增加0.075%．

/*隨機太陽能充電*/performsunpointing；t=t+tadjust;}

endif

ifrandom(p)>pthen {

/*ns表示完成的任務數(shù)*/}

endif

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

endif

}

end

在上面的算法偽代碼描述中，①Rank(task-list)表示貪心算法根據(jù)待觀測任務的結(jié)果即圖像質(zhì)量對待觀測列表進行排序。②中滿足的約束包括：圖像質(zhì)量約束、任務時間約束以及衛(wèi)星存儲約束。因而，從以上算法偽代碼可以看出，GSA優(yōu)先考慮了觀測任務的云層遮擋情況，并在考慮近似實時的云層信息的基礎上，充分結(jié)合了衛(wèi)星的有限存儲資源和任務本身的時間約束，進行任務的調(diào)度和觀測。同時，從以上算法偽代碼中可以看出，該算法在原有基礎上加入了隨機將完成任務傳輸給用戶的特點，從而減輕了衛(wèi)星調(diào)度的內(nèi)存壓力，并提高了該衛(wèi)星調(diào)度的調(diào)度效率。

圖4 GSA在衛(wèi)星調(diào)度的應用

3 實驗結(jié)果及分析

為了驗證GSA在考慮云層信息的敏捷衛(wèi)星調(diào)度中應用的優(yōu)越性，本章進行相關的對比實驗。在敏捷衛(wèi)星調(diào)度領域常用的調(diào)度算法包括動態(tài)規(guī)劃和局部搜索算法等，而對于考慮實時云層的衛(wèi)星調(diào)度問題并沒有被很好地研究，因而并不存在常用的調(diào)度算法。由于敏捷衛(wèi)星調(diào)度問題的特殊性，包括本身有限稀缺的存儲資源和運算資源，應用于傳統(tǒng)調(diào)度問題的智能算法，均不能應用于該調(diào)度問題。因而，為了驗證GSA比較適合應用于敏捷衛(wèi)星調(diào)度，本文將GSA與常用于衛(wèi)星調(diào)度的動態(tài)規(guī)劃算法和局部搜索算法在該調(diào)度問題上進行實驗結(jié)果對比。該實驗主要做了關于衛(wèi)星調(diào)度的任務觀測收益、圖像質(zhì)量以及衛(wèi)星內(nèi)存利用率的對比實驗。該實驗在裝載有Corei5- 5200UCPU@ 2.20GHz處理器的PC上運行。實驗所需的輸入數(shù)據(jù)和相關參數(shù)可根據(jù)Beaumet等[9]的研究獲得。其中，部分相關數(shù)據(jù)可見表1～2。

由于論文篇幅限制，表2列出了前10個任務的屬性。本文仿真實驗的任務收益是從[1,10]中隨機生成，任務大小所需內(nèi)存分布在8MB和15MB之間，任務截止時間分布在300～600s內(nèi)，任務的觀測時間分布在5～15s內(nèi)[9]。

本文的實驗，對比了一個周期內(nèi)，任務個數(shù)分別是50、100、200、400情況下，GSA、DPA和LSA三種算法的收益、平均任務完成時間、圖像質(zhì)量和內(nèi)存占用率的情況，其中不同算法的收益和平均任務完成時間分別如表3～4所示。

從表3中可以看出，隨著任務數(shù)的增長，三種算法衛(wèi)星調(diào)度的總收益均在增長，并且對于相同任務量，GSA比DPA和LSA能使衛(wèi)星調(diào)度獲得更多的觀測收益。在任務量為100的情況下，與DPA相比，將GSA應用于AEOS調(diào)度能夠?qū)⑷蝿沼^測得到的總收益提高14.82%；與LSA相比，將GSA應用于AEOS調(diào)度能夠?qū)⑷蝿沼^測得到的總收益提高10.32%。這說明將GSA應用于考慮云層的衛(wèi)星調(diào)度比DPA和LSA能夠獲得更大的收益。

表1 恒定輸入變量

表2 前10個任務的任務屬性

表3 不同任務數(shù)情況下不同算法的收益對比

表4 不同任務數(shù)情況下不同算法任務平均完成時間對比s

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

從表4中可以看出，GSA在任務平均完成時間上比DPA和LSA需要更多的時間。但是，從表4中也可以看出，GSA僅僅多花了1～2s的時間優(yōu)化觀測結(jié)果。其中，在任務量為100時，GSA需要46.554 1s，DPA需要45.231 6s，LSA需要46.365 4s。由此可以看出，GSA需要用的時間最多，但是GSA在算法收益和圖像質(zhì)量上，均比其他兩種算法優(yōu)越。綜合考慮觀測收益、圖像質(zhì)量和任務平均完成時間，可以得出，GSA具有更高的優(yōu)越性，其平均只需多花1～2s的時間，就能給用戶提供更為優(yōu)質(zhì)的服務和觀測結(jié)果。

由于本文的部分輸入數(shù)據(jù)是根據(jù)現(xiàn)有的相關研究成果獲得，因而為了尋找GSA在實際應用中最佳的求解性能參數(shù)，本文對比了任務量為100時，任務周期分別為2 400s、3 600s、4 800s以及客戶最大滿意時間分別為60s、90s、120s時，GSA應用于衛(wèi)星調(diào)度的運行結(jié)果,具體結(jié)果如表5～6所示。

從表5可以看出，隨著任務觀測周期變長，任務觀測收益不斷增多，但增幅變小，所需任務平均觀測時間越來越多，任務平均觀測質(zhì)量越來越好。

從表6中可以看出，隨著客戶最大滿意時間變長，任務觀測收益不斷增多，但增幅變小，所需任務平均觀測時間先變小后變多，任務平均觀測質(zhì)量越來越好。

表5 不同任務周期下GSA算法運行結(jié)果比較

表6 不同客戶最大滿意時間下GSA運行結(jié)果比較

為了更進一步對比GSA、LSA和DPA三種算法應用于衛(wèi)星調(diào)度的情況，本文選取一個周期內(nèi)任務數(shù)為100的情況下進行對比實驗，性能對比結(jié)果如圖5所示。

圖5 不同算法性能對比

從圖5可以看出，GSA應用于考慮云層的衛(wèi)星調(diào)度，可以獲得更高質(zhì)量的圖像，同時該算法對衛(wèi)星的內(nèi)存使用率較小。從圖5的曲線波動可以看出，GSA在觀測得到的圖像質(zhì)量波動和內(nèi)存使用率變化上，均比LSA和DPA穩(wěn)定。這說明GSA比其他兩個衛(wèi)星調(diào)度常用算法更符合考慮云層情況下的衛(wèi)星調(diào)度觀測問題。

4 結(jié)語

本文利用數(shù)學三角函數(shù)知識構(gòu)建獲取近似實時云層的模型，能夠解決傳統(tǒng)AEOS調(diào)度問題中，圖像觀測質(zhì)量受云層遮擋嚴重影響的問題。由于任務觀測時間短和新任務開始前重新觀測云層的特點，近似實時云層可以看作是實時變化的云層。將實時變化的云層信息納入衛(wèi)星任務的觀測調(diào)度中，能夠有效地提高衛(wèi)星任務觀測的結(jié)果圖像質(zhì)量。由于GSA不僅具有局部優(yōu)化和算法執(zhí)行占用內(nèi)存小的特點，該算法還能根據(jù)一定的偏好進行算法的執(zhí)行，其算法特性使得其比較符合考慮實時云層信息的AEOS的調(diào)度。本文將GSA應用于解決考慮實時變換云層的衛(wèi)星調(diào)度問題，能夠優(yōu)先觀測圖像質(zhì)量高的任務，從而能夠提高衛(wèi)星調(diào)度的任務觀測圖像質(zhì)量、觀測收益以及優(yōu)化衛(wèi)星的內(nèi)存使用率。

在理論分析和算法設計的基礎上，本文的仿真實驗主要對比了GSA和常用于該領域的LSA和DPA，在不同任務量情況下，其觀測收益、圖像質(zhì)量、內(nèi)存使用率以及任務平均觀測時間上的不同。對比結(jié)果表明，GSA總體收益、任務觀測圖像質(zhì)量和內(nèi)存利用率上，均比其他兩種算法具有性能更優(yōu)。

本文接下來的工作是基于GSA在考慮云層的AEOS調(diào)度應用的基礎上，控制其他資源組合并進行優(yōu)化，得到一個調(diào)度周期內(nèi)最優(yōu)的任務調(diào)度數(shù)量，從而給衛(wèi)星的任務調(diào)度客戶承載量提供一定的建議。

)

[1] 鄭義成,袁茵,鄧勇,等.基于Pareto前沿與粒子群優(yōu)化的衛(wèi)星資源調(diào)度算法[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] 邱滌珊,談群,馬滿好,等.衛(wèi)星成像偵察需求滿足度評價方法研究[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—)，男，安徽滁州人，碩士研究生，主要研究方向：衛(wèi)星調(diào)度、智能算法優(yōu)化； 劉建(1961—)，男，安徽蚌埠人，教授級工程師，博士，主要研究方向：水資源調(diào)度、智能算法優(yōu)化； 水艷(1982—)，女，安徽繁昌人，高級工程師，碩士，主要研究方向：水資源調(diào)度、智能算法優(yōu)化； 李麗華(1990—)，女，河南鄭州人，工程師，碩士，主要研究方向：水資源調(diào)度、智能算法優(yōu)化； 喻光曄(1990—)，男，湖北隨州人，工程師，碩士，主要研究方向：水資源調(diào)度、智能算法優(yōu)化。

1001- 9081(2017)06- 1814- 06

10.11772/j.issn.1001- 9081.2017.06.1814

TN927.2

A