單國(guó)厚，劉 建，水 艷，李麗華，喻光曄

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

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

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

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

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

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

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

0 引言

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

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

1 問(wèn)題分析及建模

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

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

圖1 AEOS觀測(cè)過(guò)程

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

1.1 近似實(shí)時(shí)云層

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

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

(1)

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

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

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

1.2 觀測(cè)任務(wù)

1.3 問(wèn)題建模

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

圖3 時(shí)間對(duì)觀測(cè)收益的影響指標(biāo)

從圖3可以看出，時(shí)間對(duì)觀測(cè)收益的影響指標(biāo)隨著用戶接收任務(wù)觀測(cè)結(jié)果的時(shí)間的增大而減小。

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

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

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

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

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

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

2 算法設(shè)計(jì)

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

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

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

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

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

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{

其他特征變量對(duì)住宅價(jià)格也有一定的影響．建筑面積每增加1%,住宅價(jià)格增加0.213%;建筑年齡每減少1%,住宅價(jià)格增加0.032%;小區(qū)容積率每增加1%,住宅價(jià)格增加0.059%;裝修程度每提升一個(gè)等級(jí),住宅價(jià)格增加3.05%;朝南的住宅比其他方向的住宅價(jià)格高出6.18%;住宅至最近商圈距離每增加1%,住宅價(jià)格降低0.033%;住宅至CBD距離每增加1%,住宅價(jià)格降低0.078%;物業(yè)水平每增加1%,住宅價(jià)格增加0.075%．

/*隨機(jī)太陽(yáng)能充電*/performsunpointing；t=t+tadjust;}

endif

ifrandom(p)>pthen {

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

endif

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

endif

}

end

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

表1 恒定輸入變量

表2 前10個(gè)任務(wù)的任務(wù)屬性

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

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

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

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

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

從表5可以看出，隨著任務(wù)觀測(cè)周期變長(zhǎng)，任務(wù)觀測(cè)收益不斷增多，但增幅變小，所需任務(wù)平均觀測(cè)時(shí)間越來(lái)越多，任務(wù)平均觀測(cè)質(zhì)量越來(lái)越好。

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

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

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

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

圖5 不同算法性能對(duì)比

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

4 結(jié)語(yǔ)

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

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

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

)

[1] 鄭義成,袁茵,鄧勇,等.基于Pareto前沿與粒子群優(yōu)化的衛(wèi)星資源調(diào)度算法[J].計(jì)算機(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)星成像偵察需求滿足度評(píng)價(jià)方法研究[J].計(jì)算機(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。

國(guó)家自然科學(xué)基金資助項(xiàng)目(71671168)；國(guó)家重大科技專項(xiàng)(2014ZX07204- 006- 05)。

單國(guó)厚(1992—)，男，安徽滁州人，碩士研究生，主要研究方向：衛(wèi)星調(diào)度、智能算法優(yōu)化； 劉建(1961—)，男，安徽蚌埠人，教授級(jí)工程師，博士，主要研究方向：水資源調(diào)度、智能算法優(yōu)化； 水艷(1982—)，女，安徽繁昌人，高級(jí)工程師，碩士，主要研究方向：水資源調(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