劉彬彬，李 暉，趙 曼，董理君，吳 杰

(中國地質(zhì)大學(xué)(武漢) 計算機(jī)學(xué)院，湖北 武漢430074)

基于任務(wù)壓縮的成像衛(wèi)星任務(wù)規(guī)劃

劉彬彬，李 暉，趙 曼，董理君，吳 杰

(中國地質(zhì)大學(xué)(武漢) 計算機(jī)學(xué)院，湖北 武漢430074)

傳統(tǒng)成像衛(wèi)星任務(wù)規(guī)劃過程中任務(wù)在時間窗口確定后是不可變的，但受限于衛(wèi)星的各類約束條件，有些任務(wù)無法執(zhí)行。針對該問題，在任務(wù)可以壓縮的前提下，提出了采用多種任務(wù)壓縮的方法處理指令模板沖突和消解文件下傳約束，提高規(guī)劃結(jié)果質(zhì)量。對任務(wù)壓縮策略進(jìn)行了實(shí)驗，測試結(jié)果表明，任務(wù)壓縮策略的使用能夠有效優(yōu)化規(guī)劃結(jié)果，提高衛(wèi)星觀測時長和完成任務(wù)數(shù)。

任務(wù)壓縮；衛(wèi)星任務(wù)規(guī)劃；指令模板沖突；文件下傳約束

AbstractIn the process of traditional imaging satellite mission planning,task is immutable after the confirmation of time window.Owing to the limitation of various satellite constraints,some tasks cannot be completed.To solve this problem,a variety of task compression strategies were proposed to deal with instruction template conflict and to resolve file downstream constraint under the premise that the task can be compressed,in order to improve the quality of planning results.Finally,the task compression strategies are tested.The results indicate that the use of task compression strategies can effectively optimize the planning results and increase satellite observation time and tasks completed.

Keywordstasks compression;satellite mission planning;instruction template conflict;file downstream constraint

0 引言

成像衛(wèi)星利用可見光、多光譜、高光譜、超光譜和合成孔經(jīng)雷達(dá) (Synthetic Aperture Radar，SAR) 等星載傳感器，獲取地面目標(biāo)的圖像信息[1]。成像衛(wèi)星對地觀測具有覆蓋范圍廣、運(yùn)行時間長、不受國界和空域限制、無需考慮人員安全等獨(dú)特優(yōu)勢，可以對全球任何地區(qū)實(shí)施觀測[2]。衛(wèi)星任務(wù)規(guī)劃是衛(wèi)星系統(tǒng)核心模塊，其性能直接影響到衛(wèi)星系統(tǒng)的工作效益[3]。主要目標(biāo)是對衛(wèi)星資源進(jìn)行有效的分配和調(diào)度，制定衛(wèi)星的觀測計劃，最大限度地完成用戶提交的觀測任務(wù)需求。

衛(wèi)星任務(wù)規(guī)劃是指為處理大量的用戶任務(wù)，對組網(wǎng)衛(wèi)星制定拍攝計劃[4]。需要考慮固有的衛(wèi)星能力約束及任務(wù)需求約束，是一個多約束的復(fù)雜組合優(yōu)化問題。現(xiàn)有的衛(wèi)星任務(wù)規(guī)劃模型可以歸納為3類：數(shù)學(xué)規(guī)劃模型[5-6]、約束滿足模型[7-9]和其他模型[10-12]。李軍等[13]建立了針對重點(diǎn)保障任務(wù)和其他重要任務(wù)評價的約束滿足模型。Fabrizio[14]提出了一種緊時間序列模型，包括了大量復(fù)雜技術(shù)約束，用非標(biāo)準(zhǔn)的拉格朗日啟發(fā)式算法求解。李云峰[15]給出衛(wèi)星數(shù)傳調(diào)度模型，把約束置于每個任務(wù)中，降低了建模和求解的難度。Frank[16]采用了基于約束的間隔框架對衛(wèi)星星上資源建模，提出了基于資源滿足的啟發(fā)式搜索算法，但忽略了任務(wù)沖突的情況。

現(xiàn)有研究一般是在任務(wù)不可壓縮的前提下開展的。但是由于衛(wèi)星技術(shù)的不斷發(fā)展，衛(wèi)星的數(shù)傳模式逐漸呈現(xiàn)多樣化和復(fù)雜化，規(guī)劃時往往有多種數(shù)傳模式可供選擇。為了選擇出滿足約束條件的最優(yōu)安排方式，實(shí)際工程中允許對任務(wù)進(jìn)行壓縮以提高衛(wèi)星的資源利用率。

本文基于任務(wù)可以壓縮的特點(diǎn)，提出了多種任務(wù)壓縮的方法優(yōu)化衛(wèi)星任務(wù)規(guī)劃結(jié)果。衛(wèi)星任務(wù)壓縮是指在原始的觀測任務(wù)和接收任務(wù)不滿足約束條件時不刪除整個任務(wù)，通過壓縮任務(wù)的持續(xù)時間來消解約束沖突。

1 任務(wù)壓縮

衛(wèi)星任務(wù)規(guī)劃問題需要考慮諸多的約束，有些任務(wù)往往無法滿足所有約束。雖然通過刪去觀測任務(wù)可以消解沖突，但是會導(dǎo)致規(guī)劃結(jié)果不理想。通過壓縮任務(wù)時間，可以使規(guī)劃結(jié)果滿足各類約束的同時最大化觀測任務(wù)完成數(shù)和觀測時長。本文闡述了通過任務(wù)壓縮來處理指令模板沖突和消解文件下傳約束?；谌蝿?wù)壓縮的衛(wèi)星任務(wù)規(guī)劃程序流程如圖1所示。

圖1 基于任務(wù)壓縮的衛(wèi)星任務(wù)規(guī)劃程序流程

指令模板沖突和文件下傳約束的處理單元是組合元任務(wù)，一個組合元任務(wù)對應(yīng)一種數(shù)傳模式，至少包含一個觀測任務(wù)或一個接收任務(wù)。指令模板沖突是指任務(wù)之間的間隔時間不滿足最短間隔時間要求。采用任務(wù)壓縮，需要滿足2個必要條件：一是任務(wù)被壓縮后能夠滿足最小觀測時長約束；二是壓縮后任務(wù)必須滿足一種數(shù)傳模式的要求。文件下傳約束是指由于接收窗口時長的限制而無法接收太大的成像文件，通過壓縮觀測使接收窗口能夠被最大化利用。

本文涉及5種數(shù)傳模式，一種數(shù)傳模式對應(yīng)一套指令模板，具體數(shù)傳模式指令模板如表1所示。表1中，ti(i=1,2,3,4,5,6,7)為指令模板時間，表示做相應(yīng)的數(shù)傳模式前后需要的指令控制時間；tmin為最小成像時間；Δt1、Δt2均為固定時長；T代表成像；W代表回放；TW代表同時成像和回放。其中：Δt1>Δt2>Δtmin，t1>t2>t3>t4，t5>t6>t7。

表1 數(shù)傳模式指令模板匯總

序號模板名稱開始時間結(jié)束時間備注1成像延時回放TW1-t1TW1+t5成像時間tmin成像+回放時間TW12回放W1-t2W1+t7回放時間W13成像T1-t3T1+t6成像時間T14回放轉(zhuǎn)成像延時回放W1-t2TW1+t5回放時間W1W1需不小于Δt2成像+回放時間TW15成像轉(zhuǎn)成像延時回放T1-t4TW1+t5成像時間T1T1需不小于Δt1成像+回放時間TW1

1.1 任務(wù)壓縮處理指令模板沖突

本文提出了2種壓縮策略來處理指令模板沖突：基于貪婪思想保留任務(wù)價值更高的任務(wù)(簡稱策略1)、啟發(fā)式動態(tài)調(diào)整指令模板(簡稱策略2)。

1.1.1 基于貪婪思想保留任務(wù)價值更高的任務(wù)

指令模板沖突壓縮前(情形1)如圖2所示，任務(wù)1和任務(wù)2在添加指令模板后存在沖突，首先比較它們的價值，選擇價值較低的進(jìn)行壓縮。假設(shè)任務(wù)2價值低，壓縮情況如圖3所示，壓縮量根據(jù)沖突量計算得到，只要保證壓縮后剛好不存在模板沖突即可。

圖2 指令模板沖突壓縮前(情形1)

圖3 指令模板沖突壓縮后(情形1)

上述情況沒有壓縮觀測，僅壓縮了接收開始時間，但是這種壓縮必須保證壓縮后的“剩余量”滿足當(dāng)前任務(wù)數(shù)傳模式(回放轉(zhuǎn)成像延時回放)的要求，即“剩余量”不小于Δt2。

當(dāng)然，僅壓縮任務(wù)的接收開始時間可能無法消解沖突。圖4中情形2對觀測也進(jìn)行了壓縮，以保證數(shù)傳模式不變的同時滿足其約束。其中，圖5中“剩余量1”必須不小于Δt2。此外，觀測壓縮后，“剩余量2”需滿足不小于tmin的要求。

圖5 指令模板沖突壓縮后(情形2)

假如，通過上面的策略仍然無法消解沖突，則按照貪婪準(zhǔn)則，直接刪去任務(wù)2來進(jìn)行消解沖突。

雖然示例中只介紹了數(shù)傳模式為“回放轉(zhuǎn)成像延時回放”時的壓縮方法。但是，同樣的壓縮方法可以被類比應(yīng)用于其他數(shù)傳模式，壓縮都遵循如下步驟：

① 嘗試壓縮接收時間消解沖突，無法消解時轉(zhuǎn)向步驟②；

② 嘗試同時壓縮接收和觀測來消解沖突，無法消解時轉(zhuǎn)向步驟③；

③ 刪除價值較低的任務(wù)。

1.1.2 啟發(fā)式動態(tài)調(diào)整指令模板

采用策略1相同情景進(jìn)行分析。當(dāng)任務(wù)1和任務(wù)2之間的沖突量過大，貪婪思想消解沖突是在數(shù)傳方式不變的前提下進(jìn)行的。然而，策略2則根據(jù)發(fā)生沖突任務(wù)的數(shù)傳方式，分析不同數(shù)傳方式下指令模板的差異，通過啟發(fā)式動態(tài)調(diào)整任務(wù)數(shù)傳模式的方式來消解沖突。

如圖6和圖7所示，將任務(wù)2的數(shù)傳模式從“回放轉(zhuǎn)成像延時回放”調(diào)整為“成像延時回放”，從而消解沖突。這種壓縮雖然沒有壓縮任務(wù)的觀測，但是，由于數(shù)傳模式發(fā)生了變動，相應(yīng)的指令模板也發(fā)生改變，所以，必須重新檢測是否滿足指令模板沖突。

圖6 指令模板沖突壓縮前(情形1)

圖7 指令模板沖突壓縮后(情形1)

假如上述處理仍然無法消解沖突，則可以將任務(wù)2的數(shù)傳模式從“回放轉(zhuǎn)成像延時回放”調(diào)整為“成像轉(zhuǎn)成像延時回放”。因為，查看表1可以發(fā)現(xiàn)“回放轉(zhuǎn)成像延時回放”指令模板的前模板時間為t2，而“成像轉(zhuǎn)成像延時回放”指令模板的前模板時間只需要t4，由于t4

圖8 指令模板沖突壓縮后(情形2)

當(dāng)沖突仍然無法消解時，需要在變動數(shù)傳模式的基礎(chǔ)上，繼續(xù)壓縮相同量(由剩余沖突量決定)的觀測和接收。當(dāng)然，最極端的情況就是將任務(wù)2的數(shù)傳模式從“回放轉(zhuǎn)成像延時回放”調(diào)整為“成像”，即刪去接收部分。然后，根據(jù)沖突量來壓縮觀測，如圖9所示。

圖9 指令模板沖突壓縮后(情形3)

倘若通過以上這些方式都無法消解沖突，可以嘗試對發(fā)生沖突的2個任務(wù)中的前一個任務(wù)進(jìn)行壓縮，壓縮方法以前一個任務(wù)是“回放轉(zhuǎn)成像延時回放”模式為例進(jìn)行介紹。

通過查看表1，發(fā)現(xiàn)“回放轉(zhuǎn)成像延時回放”模式的后模板時間為t5s，而“成像”模式的后模板時間為t6s(t6

圖10 前一個任務(wù)變換數(shù)傳模式

圖10中任務(wù)的結(jié)束時間沒有變，由于調(diào)整數(shù)傳模式后，后模板時間減小了，當(dāng)沖突量較小時可以消解沖突。當(dāng)然，也可以調(diào)整數(shù)傳模式的同時對觀測和接收進(jìn)行壓縮。

對于其他數(shù)傳模式，可以由此類推，壓縮遵循如下步驟：

① 嘗試變動數(shù)傳模式(其指令模板的后模板時間較當(dāng)前的更短)來消解沖突；如果無法消解轉(zhuǎn)向步驟②；

② 同時壓縮觀測與接收的結(jié)束時間、調(diào)整任務(wù)數(shù)傳模式來消解沖突。如果無法消解轉(zhuǎn)向步驟③；

③ 刪除2個沖突任務(wù)中優(yōu)先級較低的任務(wù)。

策略2總體處理步驟如下：

① 對每個任務(wù)添加指令模板時間，作為任務(wù)的指令起止時刻；

② 將任務(wù)兩兩進(jìn)行比較，前一個任務(wù)的指令結(jié)束時刻大于后一個任務(wù)的指令開始時刻，則存在沖突，計算二者差值，記為沖突量；

③ 檢查后一個任務(wù)的數(shù)傳模式，通過變動數(shù)傳模式及向后壓縮任務(wù)時間消解沖突。沖突無法消解則繼續(xù)執(zhí)行步驟④；

④ 檢查前一個任務(wù)的數(shù)傳模式，通過變動數(shù)傳模式及向前壓縮任務(wù)時間消解沖突。如果沖突仍未消解則繼續(xù)執(zhí)行步驟⑤；

⑤ 刪去其中一個價值較低的任務(wù)。

1.2 任務(wù)壓縮消解文件下傳約束

文件下傳約束存在2種情況：① 受限于衛(wèi)星固存大小，按照原始任務(wù)觀測時長產(chǎn)生的文件使固存超出，傳統(tǒng)的處理方式就是刪除任務(wù)，任務(wù)壓縮的方法則通過壓縮觀測使文件能夠放入固存；② 在給接收窗口安排回放文件時，當(dāng)固存中每個文件所需接收時長均大于接收窗口時長時，壓縮觀測使文件能夠放入接收窗口回放。固存超出時壓縮觀測的情況較為簡單，本文主要介紹壓縮觀測來為接收窗口安排回放文件的處理方法。

1.2.1 不調(diào)整數(shù)傳模式

一般觀測和接收按照固定的比例匹配，假設(shè)1 min的成像需要1 min的接收窗口來回放。任務(wù)壓縮方式可以將任務(wù)的觀測開始時間向后壓縮，也可以將任務(wù)的觀測結(jié)束時間向前壓縮，壓縮的前提是保證滿足數(shù)傳模式不變。

如圖11和圖12所示，任務(wù)1的成像文件被安排在任務(wù)2的接收窗口回放，任務(wù)2同時產(chǎn)生時長220 s的成像文件。但是，后面在給任務(wù)3安排回放文件時，發(fā)現(xiàn)無法下傳任務(wù)2的文件，必須對任務(wù)2的觀測進(jìn)行壓縮。示例中任務(wù)2的數(shù)傳模式為“成像轉(zhuǎn)成像延時回放”，要求觀測早于接收至少Δt1(Δt1<100 s)。通過將任務(wù)2的觀測開始時間向后壓縮20 s從而使任務(wù)3可以接收。并且，壓縮后任務(wù)2的觀測早于回放100 s，滿足數(shù)傳模式要求。

圖11 消解文件下傳約束壓縮前

圖12 消解文件下傳約束壓縮后

1.2.2 調(diào)整數(shù)傳模式

如圖13和圖14所示，任務(wù)2產(chǎn)生時長220 s的成像文件。但是，后面的接收窗口都無法下傳該文件，必須對任務(wù)2的觀測進(jìn)行壓縮。示例中任務(wù)2的數(shù)傳模式為“成像轉(zhuǎn)成像延時回放”，要求觀測早于接收至少Δt1(Δt1>80 s)，任務(wù)3的接收窗口只能接收140 s的成像文件。理論上只要壓縮任務(wù)2觀測80 s就可以了，但是壓縮后不滿足“成像轉(zhuǎn)成像延時回放”Δt1的約束。所以調(diào)整數(shù)傳模式，將其調(diào)整為“成像延時回放”模式(要求成像早于回放tmin)壓縮了90 s的觀測，剩下130 s的觀測。任務(wù)3的接收窗口也對應(yīng)壓縮10 s。

圖13 消解文件下傳約束壓縮前

圖14 消解文件下傳約束壓縮后

2 任務(wù)壓縮實(shí)驗與分析

任務(wù)壓縮實(shí)驗是為了對比采用任務(wù)壓縮和不采用任務(wù)壓縮的效果。其中，任務(wù)壓縮在處理指令模板沖突時又有2種策略：基于貪婪思想保留任務(wù)價值更高的任務(wù)(策略1)和啟發(fā)式動態(tài)調(diào)整指令模板(策略2)。

采用任務(wù)壓縮的優(yōu)化效果取決于元任務(wù)集時間窗口的分布情況。本文針對觀測元任務(wù)為10、100和200的量級，分別測試不采用任務(wù)壓縮、采用任務(wù)壓縮策略1和采用任務(wù)壓縮策略2，記錄衛(wèi)星完成任務(wù)數(shù)和完成觀測時長。

在完成任務(wù)數(shù)方面，規(guī)劃結(jié)果如圖15所示。

圖15 完成任務(wù)數(shù)對比

在完成觀測時長方面，規(guī)劃結(jié)果如圖16所示。

圖16 完成觀測時長對比

從上述實(shí)驗結(jié)果可以看出，任務(wù)壓縮策略的使用能有效提高衛(wèi)星完成任務(wù)數(shù)和完成觀測時長。當(dāng)元任務(wù)數(shù)量增多時，優(yōu)化效果更加明顯。并且，采用任務(wù)壓縮策略二比任務(wù)壓縮策略一效果更優(yōu)。在實(shí)際工程中，需要最大化利用衛(wèi)星觀測能力，想要在完成任務(wù)數(shù)和觀測時長上進(jìn)行少許提升都十分不易，實(shí)驗表明任務(wù)壓縮的使用能夠進(jìn)一步提升觀測效益。

3 結(jié)束語

本文提出了基于任務(wù)壓縮的衛(wèi)星任務(wù)規(guī)劃，針對指令模版沖突和文件下傳約束分別給出了任務(wù)壓縮策略。在處理指令模版沖突時，設(shè)計了2種任務(wù)壓縮策略進(jìn)行優(yōu)化。在處理文件下傳時，分別給出了不調(diào)整數(shù)傳模式和調(diào)整數(shù)傳模式的處理方法。實(shí)驗結(jié)果表明，任務(wù)壓縮機(jī)制的引入有效地提高了衛(wèi)星完成任務(wù)數(shù)和完成觀測時長,并且在任務(wù)量大且沖突任務(wù)多時任務(wù)壓縮的效果更加明顯。

[1] LIN W C，LIAO D Y，LIU C Y．Daily Imaging Scheduling of an Earth Observation Satellite[J].IEEE Transactions on Systems,Man and Cybernetics,Part A:Systems and Humans,2005,35(2):213-223.

[2] 賀仁杰,高鵬,白保存.成像衛(wèi)星任務(wù)規(guī)劃模型、算法及其應(yīng)用[J].系統(tǒng)工程理論與實(shí)踐,2011,31(3):411-422．

[3] 姜維,郝會成,李一軍.對地觀測衛(wèi)星任務(wù)規(guī)劃問題研究述評[J].系統(tǒng)工程與電子技術(shù),2013,35(9):1878-1885．

[4] 姜維,龐秀麗.提高衛(wèi)星服務(wù)壽命的任務(wù)規(guī)劃方法研究[J].自動化學(xué)報,2014,40(5):909-920.

[5] 李菊芳,譚躍進(jìn).衛(wèi)星觀測聯(lián)合調(diào)度問題的VRP與JSP模型[J].系統(tǒng)工程,2006,24(6):111-115．

[6] 王沛,譚躍進(jìn).多星聯(lián)合對地觀測調(diào)度問題的列生成算法[J].系統(tǒng)工程理論與實(shí)踐,2011,31(10):1932-1939.

[7] 劉洋,陳英武,譚躍進(jìn).一種有新任務(wù)到達(dá)的多衛(wèi)星動態(tài)調(diào)度模型與方法[J].系統(tǒng)工程理論與實(shí)踐,2005 (4):35-41.

[8] 馬冬青,王蔚.基于改進(jìn)遺傳算法的星地任務(wù)優(yōu)化調(diào)度研究[J].計算機(jī)工程與應(yīng)用,2014,50(6):246-249.

[9] 龐秀麗,于渤,姜維.成像衛(wèi)星任務(wù)周規(guī)劃模型與算法[J].國防科技大學(xué)學(xué)報,2013,35(5):44-51.

[10] 龍運(yùn)軍,陳宇寧,陳英武,等.基于Petri網(wǎng)和混合蟻群算法的多星成像調(diào)度[J].計算機(jī)工程,2013,39(1):35-40.

[11] 唐忠興,韓潮.基于有向無圈圖的敏捷衛(wèi)星姿態(tài)機(jī)動策略[J].北京航空航天大學(xué)學(xué)報,2014,40(5):69-75.

[12] 郝會成,姜維,李一軍,等.基于Multi-Agent敏捷衛(wèi)星動態(tài)任務(wù)規(guī)劃問題[J].國防科技大學(xué)學(xué)報,2013,35(1):53-59.

[13] 李軍,郭玉華,王鈞,等.基于分層控制免疫遺傳算法的多衛(wèi)星聯(lián)合任務(wù)規(guī)劃方法[J].航空學(xué)報,2010,31(8):1636-1645.

[14] MARINELLI F,NOCELLA S,ROSSI F,et al.A Lagrangian Heuristic for Satellite Range Scheduling with Resource Constraints[J].Computers & Operations Research,2011,11(38):1572-1583.

[15] 李云峰,陳祥國,武小悅.衛(wèi)星數(shù)傳調(diào)度模型研究[J].國防科技大學(xué)學(xué)報,2007,6(29):121-125.

[16] FRANK J,JONSON A,MORRIS R.Planning and Scheduling for Fleets of Earth Observing Satellites[C]∥Proceedings of the 6th International Symposium on Artificial Intelligence,Robotics,Automation and Space,Montredal,2002:342-347.

ImagingSatelliteMissionPlanningBasedonTaskCompression

LIU Bin-bin，LI Hui，ZHAO Man，DONG Li-jun，WU Jie

(SchoolofComputerScience,ChinaUniversityofGeosciences,WuhanHubei430074,China)

TP302.1

A

1003-3106(2017)11-0073-06

劉彬彬男，(1991—)，碩士研究生。主要研究方向：智能計算與智能信息處理。

10.3969/j.issn.1003-3106.2017.11.16

劉彬彬,李暉,趙曼,等.基于任務(wù)壓縮的成像衛(wèi)星任務(wù)規(guī)劃[J].無線電工程,2017,47(11):73-78.[LIU Binbin,LI Hui,ZHAO Man,et al.Imaging Satellite Mission Planning Based on Task Compression[J].Radio Engineering,2017,47(11):73-78.]

2017-01-18

湖北省自然科學(xué)基金資助項目(2016CFB278)。

李暉女，(1967—)，教授，碩士生導(dǎo)師。主要研究方向：智能計算與智能信息處理。