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

(中國地質大學(武漢) 計算機學院，湖北 武漢430074)

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

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

(中國地質大學(武漢) 計算機學院，湖北 武漢430074)

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

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

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

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

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

1 任務壓縮

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

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

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

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

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

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

1.1 任務壓縮處理指令模板沖突

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

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

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

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

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

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

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

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

假如，通過上面的策略仍然無法消解沖突，則按照貪婪準則，直接刪去任務2來進行消解沖突。

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

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

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

③ 刪除價值較低的任務。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

⑤ 刪去其中一個價值較低的任務。

1.2 任務壓縮消解文件下傳約束

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

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

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

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

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

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

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

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

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

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

2 任務壓縮實驗與分析

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

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

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

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

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

圖16 完成觀測時長對比

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

3 結束語

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

[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)星任務規(guī)劃模型、算法及其應用[J].系統(tǒng)工程理論與實踐,2011,31(3):411-422．

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

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

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

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

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

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

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

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

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

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

[13] 李軍,郭玉華,王鈞,等.基于分層控制免疫遺傳算法的多衛(wèi)星聯(lián)合任務規(guī)劃方法[J].航空學報,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].國防科技大學學報,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èi)星任務規(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

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

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