敏捷對地觀測衛星自主任務調度方法

劉 嵩，孔鴻濱

(廣州城市理工學院 計算機工程學院，廣東 廣州 510812)

0 引言

對地觀測衛星作為一種重要的對地觀測手段，具有覆蓋區域廣、可長時間運行和不受飛行空域限制等優勢[1-2]，而對地觀測衛星任務調度正是充分發揮這些優勢的關鍵。

對地觀測衛星任務調度負責分配衛星觀測資源、制定觀測計劃[3]。傳統的對地觀測衛星任務調度是由地面控制系統完成。首先要預估衛星狀態，根據用戶需求提前為衛星制定觀測方案，然后在特定時間將執行指令上注至衛星執行[4-9]。但該過程會受到地面預估誤差、星地通信時間窗口等限制，而且指令一旦上注便無法變更，這將導致衛星很可能錯過對重點目標的最佳成像時機，更加無法快速靈活地根據自身狀態應對隨時可能到達的動態觀測需求。

為了解決上述問題，各國學者越來越重視衛星自主調度技術方面的研究[10-11]。一旦衛星具備了自主調度能力，便可以隨時根據動態到達的觀測需求，在星上自主制定觀測方案，真正實現對地觀測數據的智能化實時服務，從而克服地面調度的弊端。

針對對地觀測衛星自主任務調度問題，文獻[12]提出了一種基于任務軸的滾動調度策略，由于調度與執行任務交替進行，所以調度占用的時間越長，執行任務的時間就越短，二者存在矛盾。文獻[13-17]針對EO-1衛星自主任務調度問題進行了深入研究，通過在星上分析重點目標的地質現象是否發生變化，來決定是否觸發迭代修復算法，但這種觸發事件發生的概率較低，因此該方法對動態事件的響應能力不強。文獻[18-19]提出了一種星上隨機迭代貪婪算法，能夠解決目標被云層遮擋下的敏捷衛星自主任務調度問題，雖然對動態事件響應能力有所提升，但是動態事件主要是指云層遮擋造成的任務取消，并沒有考慮觀測需求隨機到達的情況。文獻[20]利用迭代修復的方法進行自主任務調度，但衛星狀態實時變化，所以修復時機很難把握，而且每一次調度的持續時間無法確定。另外，目前的研究主要針對非敏捷衛星，而且大多只考慮觀測任務，沒有結合考慮數據回傳任務。

針對上述不足，本文首先提出了一種星上自主調度策略，明確了星上自主任務調度的時機，以及每次調度的范圍，然后針對此策略，設計了一種基于變鄰域搜索的星上自主任務調度算法，算法不僅考慮了敏捷衛星特點，還考慮了數據回傳任務，最后通過仿真實驗驗證了該算法的有效性。

1 問題描述與建模

非敏捷對地觀測衛星只能對目標實行過頂成像，成像時間是一定的，一旦錯過了過頂時間，將無法完成觀測任務。敏捷對地觀測衛星則不同，在衛星尚未到達目標正上方時，便可以通過調整俯仰角度觀測到地面目標。有效觀測范圍示意如圖1所示。

圖1 觀測范圍示意Fig.1 Observation scope

敏捷對地觀測衛星的觀測時間窗口更長，觀測時間不再局限于過頂時間，而是可以在觀測時間窗口內任意滑動。因此對于非敏捷對地觀測衛星一次過境無法完成觀測的區域目標，敏捷對地觀測衛星可以采用同一軌道多次向同一方向進行推掃的方式，完成區域目標的同軌多條帶拼接成像。條帶長度由掃描時間決定，一次推掃過程如圖2所示。敏捷性提升了衛星的觀測能力，但更長的時間窗口也大大增加了任務調度的優化難度。

圖2 對地觀測過程示意Fig.2 Process of earth observation

敏捷對地觀測衛星自主任務調度問題可以描述為：面對隨時可能到達的觀測需求，敏捷對地觀測衛星能夠在不需要或較少依靠地面人員干預的情況下，根據自身的狀態，星上自主決策調度時機和調度范圍，自主制定觀測方案，在快速響應動態觀測需求、提高觀測時效性的同時，實現以盡可能少的資源消耗獲取盡可能大的觀測收益。

1.1 模型的輸入輸出

模型輸入：調度開始時間p，調度結束時間q和觀測任務集合J；J中每個觀測任務j所對應的優先級wj、占用固存大小cj、觀測持續時間oj和數據回傳持續時間dj；能夠對任務j進行觀測的衛星圈次的集合Mj，以及在圈次k對任務j進行觀測時，所對應的觀測時間窗口的開始時間sj,k和結束時間ej,k；數據回傳時間窗口集合I，I中每個數據回傳時間窗口i所對應的開始時間bi和結束時間ri；衛星固存最大值C。

1.2 目標函數與約束條件

優化目標是使得完成觀測任務和數據回傳任務的累積收益最大，目標函數為：

(1)

約束條件：

(2)

bi≤bj,i

(3)

(4)

(5)

0≤Ct≤C，

(6)

(7)

(8)

xj,k≥yj,i，

(9)

(10)

式(2)為觀測時間窗口約束，每個觀測任務必須在其觀測時間窗口內被觀測。

式(3)為回傳時間窗口約束，每個數據回傳任務必須在回傳時間窗口內被回傳。

式(4)為觀測與回傳的時間順序約束，觀測數據的回傳開始時間不能早于該目標的觀測結束時間。

式(5)為姿態轉換時間約束，當任務j與j′在第k個軌道圈次上連續執行，則需要時間TSj,j′來完成衛星的姿態轉換。

式(6)為衛星存儲約束，表示任意時刻的衛星固存Ct都不能超出衛星最大固存C。

式(7)為觀測機會約束，每個目標最多只能被觀測一次。

式(8)為回傳機會約束，每個觀測任務的數據最多只能被回傳一次。

式(9)為觀測與回傳的邏輯關系約束，只有完成觀測的任務，其觀測數據才會被回傳。

式(10)為任務不間斷約束，任意2個觀測任務j和j′，以及2個任務所對應的數據回傳任務不能同時執行，觀測任務和數據回傳任務不能同時執行。

2 星上自主調度策略

星上自主調度策略的核心思想是通過縮小調度周期和調度范圍，增加調度次數，實現用反復進行的小規模的調度代替一次性大規模的調度。由于調度次數大幅增加，所以每一次進行調度時都能建立在最新任務信息的基礎上，從而應對動態觀測需求。

本策略規定每一次調度都包含3個步驟:步驟1建立調度窗口，即確定哪些任務參與本次調度；步驟2調度求解，即針對調度窗口內的任務進行調度，輸出觀測任務序列作為調度結果；步驟3建立執行窗口，即在調度結果中選擇一部分任務作為將要執行的任務執行方案。

第n次調度產生的任務執行方案的編號為n。每一次調度都與衛星執行任務執行方案同時進行，即執行第n個任務執行方案的同時進行第n+1次調度。第n個任務執行方案中的最后1個任務的執行結束時間，就是第n+1次調度的結束時間。每次調度結束后，立即開始下一次調度，因此每一次調度的開始和結束時間可以通過計算得到。自主調度策略的控制過程如圖3所示。

圖3 自主調度策略活動圖Fig.3 Activity diagram of autonomous task scheduling strategy

相比文獻[12]中調度與執行交替進行的滾動方式，本策略的最大好處在于調度過程和任務執行過程都是持續進行的，如圖4所示，該策略下調度的機會更多，所以能夠對觀測需求的動態變化做出快速響應。同時,執行的時間也更長了，所以能夠充分發揮衛星的觀測效能。

圖4 對比圖Fig.4 Comparison chart

2.1 調度窗口

建立調度窗口是每一次調度的第1個步驟。調度窗口有2個控制參數：“數量上限”和“時間跨度”。“數量上限”是指調度窗口內任務數量的最大值；“時間跨度”要求調度窗口內所有觀測任務時間窗口的開始時間與建立調度窗口的時間差必須小于該跨度。

建立調度窗口之前，首先要將星上的觀測任務和數據回傳任務分為4類：等待調度任務、等待執行任務、已完成任務和執行任務，任務類型隨時間變化。等待調度任務是指那些沒有被納入任務執行方案，沒有確定執行時間，正在等待調度的觀測或數據回傳任務。等待執行任務是指那些已經被納入任務執行方案，確定執行時間，但尚未被執行的觀測或數據回傳任務。已完成任務是指那些已經完成的觀測或數據回傳任務。執行任務是指衛星正在執行的觀測或數據回傳任務。

任務分類示意如圖5所示，假設當前建立調度窗口的時刻為時刻1，即本次調度開始時刻。時刻2為相鄰的下一個調度窗口的建立時刻，即下一次調度的開始時刻。如果以時刻1為基準對任務進行分類，那么觀測任務1和數據回傳任務1屬于已完成任務。觀測任務2和數據回傳任務2屬于等待執行任務，數據回傳任務3屬于執行任務。等待調度任務由于沒有被賦予執行時間段，因此沒有在圖中標出。在時刻2，圖中全部任務均屬于已完成任務。所以說這種分類方式具有動態性。

圖5 任務分類示意Fig.5 Task classification

調度窗口由等待調度任務構成。假設當前調度窗口開始時刻為t，相鄰的下一個調度窗口開始時刻為t″，“時間跨度”為T。在建立調度窗口之前，首先將所有在t″～t″+T時刻存在觀測時間窗口的等待調度任務組成觀測任務集合Observe(t)。如果Observe(t)不為空，那么按照時間窗口開始時間的先后順序對觀測任務進行排序。當任務有多個時間窗口時，依據其最早可用時間窗口參與排序。如果2個任務的時間窗口開始時間相同，則按照優先級從高到低的順序進行排序，如果2個任務的優先級相同，則隨機確定2個任務的前后關系。

將所有在t″～t″+T時刻存在數據回傳時間窗口的等待調度任務組成數據回傳任務集合Transmission(t)。如果Transmission(t)不為空，則任務按照從前至后，優先級由高至低的順序進行排序。如果2個數據回傳任務的優先級相同，則隨機確定2個任務的前后關系。

最后將Transmission(t)連接在Observe(t)之前構成一個新的任務序列，并從前至后連續選擇min(Transmission(t)+Observe(t),k)個任務構成任務集合ScheduleWin(t)，ScheduleWin(t)就是t時刻的調度窗口，k表示“數量上限”。建立調度窗口的流程如圖6所示。調度窗口建立后，即確定了調度對象，便可以運用算法進行調度求解。求解結果即調度結果，用Schedule(t)表示。Schedule(t)是一個按執行開始時間排序的任務序列，其中的每一個任務都有明確的執行時間段。

圖6 調度窗口構建流程Fig.6 Flow chart of scheduling window construction

2.2 執行窗口

根據Schedule(t)建立執行窗口。執行窗口有2個控制參數：“執行上限”和“間隔上限”控制。“執行上限”是指任務執行方案中所包含的任務數量的最大值。“間隔上限”要求任務執行方案中前一個任務的結束時間和后一個任務的開始時間的時間間隔不能超過此上限，目的是控制任務執行方案的松散程度，避免2個任務之間的等待時間過長。

建立執行窗口時，在Schedule(t)中從前至后一共選擇min(|Schedule(t)|,k″)個衛星任務構成執行窗口，執行窗口內的任務序列就是任務執行方案，而k″就是觀測方案的執行上限。如果k″比較大，將導致執行任務和下一次調度的持續時間變長，而調度的機會變少，最終造成對動態觀測需求的反應能力減弱。但是如果k″太小，雖然調度的機會變多，對動態觀測需求的反應能力得到提高，但調度持續時間變短，會導致調度算法的求解時間受到限制，所以優化結果的質量難以保證。

通過“執行上限”可以控制執行和調度持續時間長度，但只考慮k″得到的任務執行方案可能比較松散。如果任務之間的時間間隔比較大，即使k″很小，整個任務執行方案的執行持續時間也可能會很長，從而降低調度頻率。因此需要使用“間隔上限”對任務執行方案做進一步限制。當任務執行方案中出現2個連續任務Task1和Task2，且Task1和Task2的時間間隔大于Task2及其之后的所有任務刪除，保證任務執行方案中的任意2個連續任務的時間間隔都小于等于k?，而k?表示的就是“間隔上限”。

3 算法設計

本算法用于針對調度窗口內的任務進行調度求解，并輸出Schedule(t)。算法的核心思想是首先利用啟發式規則生成一定數量的初始解，選取其中的最優解作為初始解x，即搜索起點，然后進行變鄰域搜索。在每一個鄰域內進行搜索的次數達到lmin時，則視為已經陷入局部最優，必須改變鄰域結構。搜索過程中，如果搜索到一個更優的解y，則說明該鄰域有利于解的改進，并將y替換x作為搜索起點，繼續在該鄰域內搜索。

自主調度策略根據調度的開始時間和結束時間，控制算法的開始和結束，每次調度結束時輸出當前最優解。除此之外算法還設置了最大迭代次數lmax，當達到該條件則算法也將停止，算法流程如圖7所示。

圖7 算法流程Fig.7 Flow chart of algorithm

3.1 初始解

第1步，任務排序。首先使用文獻[12]所設計的7種排序規則對調度窗口的觀測任務進行排序，得到7種觀測任務序列。如果調度時存在已經完成觀測但數據尚未被回傳的數據回傳任務，那么還要確定當前最早可用數據回傳時間窗口的開始時間。在觀測任務序列中從前至后尋找第一個觀測時間窗口開始時間大于該時間的觀測任務。如果存在，將數據回傳任務按高優先級優先規則插入該任務之前。如果不存在，則將數據回傳任務序列按高優先級優先規則插入到序列末端。

第2步，確定任務執行時間并進行約束檢查。從前至后為隊列中每個任務選擇執行的開始和結束時間。在確定任務的執行時間時，首先使用文獻[12]所設計的時間窗口裁剪方法對該任務的時間窗口進行裁剪，避免不同任務在時間上發生重疊。將最早可用的時間窗口的開始時間作為觀測任務的開始時間。將最早可用的數據回傳時間窗口的開始時間作為數據回傳任務的開始時間。每當一個觀測任務確定了執行時間，立即對它進行約束檢查，如果滿足約束條件，增加一個該任務所對應的數據回傳任務，否則將該任務刪除。增加的數據回傳任務按高優先級優先規則插入到已經存在的數據回傳任務序列中。如果是序列中唯一的數據回傳任務，那么排序位置參照第1步中的規則。

第3步，收益計算。將收益最高的解作為初始解。

3.2 鄰域結構設計

3.2.1 末位插入鄰域

在解中任意選擇n個xj,k=1的觀測任務，將這n個任務轉移至任務序列Sequence的末端，這n個任務分別用x1，x2，…，xn表示，如圖8所示。觀測任務序列改變后，重新插入數據回傳任務。插入方法與生成初始解第1步中的插入方法一致。一般來說，如果將某些觀測任務移至序列末尾，那么這些任務能夠被執行的可能會變得很小，但從優化的角度來看，可以通過末位插入，增大完成其他任務的概率。

圖8 末位插入鄰域Fig.8 Final bit insertion neighborhood

3.2.2 首位插入鄰域

在解中任意選擇n個xj,k=0的觀測任務，這n個任務分別用x1，x2，…，xn表示，如圖9所示。觀測任務序列改變后，重新插入數據回傳任務。插入方法與生成初始解第一步中的插入方法一致。一般來說，如果將某些觀測任務移至序列前端，那么這些任務能夠被執行的可能性會增加，從而有機會提高解的質量。

圖9 首位插入鄰域Fig.9 First bit insert neighborhood

3.2.3 交換鄰域

任意選擇n個xj,k=1的觀測任務。這些任務用x1，x2，…，xn表示。然后任意選擇n個xj,k=0的觀測任務，并用y1，y2，…，yn表示這些任務。先后將x1與y1，x2與y2的位置進行交換，直到最后將xn與yn的位置進行交換，如圖10所示。觀測任務序列改變后，重新插入數據回傳任務。插入方法與生成初始解第1步中的插入方法一致。

圖10 交換鄰域Fig.10 Exchange neighborhood

4 實驗結果及分析

實驗中衛星的軌道參數來自北美空防司令部2017年5月公布的WorldView-2衛星軌道數據。觀測目標為點目標，分布在衛星星下點軌跡附近。每個觀測任務都由任務編號、軌道編號、任務優先級、觀測時間窗口和觀測持續時間等相關信息構成。

假設每個觀測任務的觀測持續時間是5～30 s，每個觀測任務的數據回傳持續時間是觀測持續時間的2倍，每個觀測任務的優先級是1～10。實驗中用觀測持續時間代替具體的固存占用大小，假設衛星固存最大可容納2 400 s的觀測數據。假設有1個機動地面站可以提供5個數據回傳時間窗口，單個數據回傳時間窗口平均長度為720 s。實驗計算機配置為Intel(R) Core(TM) i5-7200U CPU@2.50 GHz，內存為8 GB，操作系統為Windows10，編程環境為Matlab。

4.1 實驗1

利用Simulink模塊中的有限狀態機模擬自主調度策略，確定調度時機、調度范圍，控制算法的開始和結束，并模擬任務動態到達場景。實驗場景時間設定為24 h。實驗中，“數量上限”設置為50，“時間跨度”設置為3 600 s，“執行上限”設置為10，“間隔上限”設置為300 s。為了模擬星上有限的運算能力，假設星上算法迭代一次生成一個可行解所花費的時間為10 s。

觀測任務完成數量如圖11所示。隨著動態觀測需求數量的不斷增加，衛星每天可以觀測的任務數量逐漸增加，并在270附近處趨于平穩，這說明270個任務接近實驗中每天觀測的最大任務數量，這主要是由于固存和數據回傳時間窗口約束造成的。由于觀測能力限制，隨著觀測需求的不斷增加，任務完成率呈下降趨勢，如圖12所示。但如果在觀測能力范圍內，任務完成率還是很高的，可以穩定在90%附近。實驗中數據回傳時間窗口利用率能夠穩定在90%附近，如圖13所示。

圖11 觀測任務完成數量Fig.11 Completion number of observing tasks

圖12 觀測任務完成率Fig.12 Completion rate of observing tasks

圖13 數據回傳時間窗口利用率Fig.13 Use rate of data backhaul time-window

數據回傳時間窗口沒有被完全利用，是因為每個數據回傳任務的回傳持續時間不同，數據回傳任務不能在不同的回傳窗口中接續回傳，所以如果數據回傳窗口剩余的時間不足以完成一個回傳任務，那么就不能執行數據回傳。但較高的數據回傳時間窗口利用率會導致很多觀測時間窗口與數據回傳時間窗口發生重疊的觀測任務將在發生重疊的這一軌無法完成觀測，這也是無法完成全部觀測任務的一個原因。

觀測需求數量對高優先級任務(優先級在9以上)比例和低優先級任務(優先級在2以下)比例的影響并不大，如圖14所示。高優先級任務比例保持在28%附近，而低優先級任務比例保持在15%以下，與優化目標一致。

圖14 任務完成率對比Fig.14 Comparison of completion rates

實驗結果表明，面對隨機到達的觀測需求，在考慮數據回傳任務和敏捷衛星特點的同時，所提出的自主任務調度策略和自主任務調度算法能夠較好地解決敏捷對地觀測衛星自主任務調度問題。另外，雖然較多的觀測需求可以充分發揮衛星效能，但有限的數據回傳資源將導致大量觀測數據無法在當天回傳。

4.2 實驗2

分別使用文獻[12]中的LS算法和本算法對不同規模的衛星任務調度問題進行求解。實驗根據任務數量分為4組，最終取平均值作為實驗結果。各組任務中10%的任務是已經存在的數據回傳任務，其他為觀測任務。假設衛星固存的最大值為參與調度的觀測任務的固存占用值之和的50%。lmax=100，lmin=lmax/3。實驗結果如表1所示。

表1 算法對比實驗結果Tab.1 Experimental results of algorithms comparison

在有限的迭代次數下，本算法的求解效果要優于LS算法。這是因為本算法在搜索過程中用鄰域結構引導搜索方向。LS算法的初始解比較多，因此根據每個初始解進行迭代改進的迭代次數變得非常有限。另外，LS算法在迭代改進過程中，使用的是輪盤賭的思想，沒有明確的鄰域結構，因此在有限的迭代次數中對解的改進略顯盲目。另外，2種算法的優化目標并不相同。LS算法中，如果一個觀測任務和其所對應的數據回傳任務不能在調度結果中同時出現，則沒有收益。這種方式忽略了觀測任務自身的收益，也是結果相對于本算法較差的原因之一。

5 結束語

針對星上自主任務調度問題展開研究，提出了星上自主調度策略，建立了問題的約束滿足模型，并根據星上運算能力弱的實際設計了基于變鄰域搜索的星上自主任務調度算法，主要取得了以下成果：

① 自主調度策略能夠保證在合適的時機，針對合適的任務進行星上調度，并利用反復進行的小規模的調度代替一次性大規模的調度。由于每一次調度都能建立在最新任務信息的基礎上，因此可以應對觀測需求的隨機到達。

② 針對問題建立了約束滿足模型，考慮了數據回傳任務和敏捷衛星特點，并在此基礎上提出了一種基于變鄰域搜索的星上自主任務調度算法。算法利用鄰域結構引導搜索方向，從而保證了解的質量。

③ 實驗結果表明，算法在自主調度策略的控制下能夠對頻繁到達的觀測需求進行快速響應，達到了設計預期。另外相比較LS算法，本算法針對不同問題規模，均有更好的表現。