高分多模衛星啟發式調度模型任務規劃系統實現

邱虎 劉明亮 李紫未

(中國資源衛星應用中心，北京 100094)

高分多模衛星具有分辨率高，敏捷性強，可中繼傳輸等特點，可以實現對目標的快速訪問和傳輸，因此，在地面任務管理系統中對星地資源，結合各種約束的綜合管控，實現系統收益最大化，滿足更多用戶的需求具有非常重要的意義。

但另一方面，高分多模衛星對地觀測任務調度問題約束條件眾多，問題復雜，任務調度問題的特點有以下幾個方面。

1)觀測開始時間的不確定性

由于高分多模衛星的較強機動性，因此其對地面觀測目標的可見時間窗口相對較長，最長可以達到幾分鐘，目標的觀測開始時間可以在此時間內任意選擇，觀測動作可以在衛星飛行到觀測目標的上方之前、之時或者之后，而非敏捷衛星在觀測地面目標時，其觀測開始時間是確定的，不能夠前移或者后移，否則其觀測到的目標數據就不完整[1-2]。高分多模衛星通過機動性實現同一軌道的全覆蓋觀測多個目標，這一優點使得如何在可見時間窗口內安排觀測窗口成為一個重要的問題，這將直接約束敏捷衛星強大觀測能力的發揮。

2)時間窗口選擇的多樣性

高分多模衛星具有俯仰、偏航及滾動等3個方向的自由度，對目標的可觀測機會成倍增加，對同一任務也可能有多個時間窗口。在數據回傳的過程中，同一任務也必須在多個回傳時間窗口內選定一個作為其回傳窗口。因此，無論是觀測時間窗口還是回傳時間窗口，都需要在多個窗口內選定，顯示出問題時間窗口選擇多樣性的特點。

3)數據回傳活動的不確定性

高分多模衛星具有實時傳輸、延時回放及中繼中轉并回放等模式獲取數據，由于高分辨率數據率高及實傳弧段的不足，不同數據的獲取優先級不同，也增加了數據獲取模式的復雜性。同時，對于數據回傳活動對后續觀測活動影響很大，怎樣確定回傳任務及其回傳時間才能更有利于后續觀測活動也是高分多模衛星任務調度問題的關鍵之一。

4)觀測次序的不確定性

對兩個地理位置相近的觀測目標而言，高分多模衛星對它們的觀測活動次序是不定的，取決于用戶偏好或者算法選擇[3-4]，而非敏捷衛星對它們的觀測次序是由星歷的先后事先決定的。觀測次序的不確定性，增強了高分多模衛星任務調度的靈活性，也增加了其求解難度。

5)用戶需求的多樣性

由于高分多模衛星強大的觀測能力和圖像特性，用戶對目標的觀測需求相應復雜和多樣，比如多條帶拼接需求、立體成像需求等，也是敏捷衛星體現其強大觀測能力的關鍵。其中存在的多個條帶如何同時安排、條帶之間的機動時間如何計算、立體成像任務如何安排等問題也為任務調度的難點之一。

6)能量消耗與補充的不確定性

高分多模衛星的能量平衡是影響觀測任務的重要問題。通過對不同任務能量消耗的計算，可以實現較小的代價實現更多的任務觀測。因此，觀測任務如何選擇觀測資源成為調度算法中要解決的難點之一。

啟發調度算法是一種基于直觀或經驗構造的算法[5]，對優化問題的實例能給出可接受的計算成本(計算時間、占用資源等)內，給出一個近似最優解。本文主要研究了高分多模衛星在一定使用約束和可用資源下，建立基于用戶需求滿足最大化收益的函數模型，進而尋找最優解，并在系統中進行驗證。

1 建模及求解

高分多模衛星任務規劃問題，就是在綜合考慮衛星、載荷、地面站等資源的能力和不同用戶的任務需求、不同規劃目標的基礎上，將生成的成像任務合理分配給衛星，進行約束檢查并消除任務間的沖突，確定各個元任務的具體執行次序、執行時間、執行方式，最大限度地滿足用戶及管理部門的需求，生成衛星對地觀測和接收計劃[6]。將其抽象為數學模型即為在高分多模衛星現有的約束下，實現綜合收益的最大化。

1.1 變量定義

高分多模衛星的任務規劃問題可以抽象為使用資源(衛星資源、接收窗口資源)在約束條件下(衛星觀測時間約束、衛星存儲資源約束、衛星擺動約束、觀測窗口時間約束)對觀測目標(點目標，區域目標)的最大收益值。

為了更好引入及描述在一定約束條件下的收益目標函數以及其約束條件模型，先將場景中的使用的相關變量定義如下。

觀測目標可以是多個點目標和多個區域目標集合，T={t1,t2,…,tN}，其中N為目標數量；

wi為觀測目標ti的收益(優先級)，i=1,…N；

Ssce和Esce為場景的開始時間和結束時間；

oikv為衛星s對目標ti的第k個時間窗口內構造的第v個條帶；

wsikv為任務條帶oikv的最早觀測開始時間，weikv為最遲觀測開始時間，dikv為任務條帶oikv的觀測持續時間，rikv為觀測側擺角度；

wsrikv為任務條帶oikv實際觀測開始時間，werikv為實際觀測結束時間；

衛星觀測oikv的側視角rikv，衛星觀測oikv的俯仰角pikv；

ui∈(0,1)，ui=1代表條帶oikv可以直拍直傳，[dsi,dei]表示條帶oikv的直傳時間窗口；

sdi∈(0,1),sdi=1代表條帶oikv要求立體成像；

Wsi為任務ti的觀測開始時間(ti第一個條帶觀測開始時間)，Wei為任務ti的觀測結束時間(ti最后一個條帶觀測結束時間)；

Dwsi為任務ti的回傳開始時間(ti第一個條帶回傳開始時間)，Dwei為任務ti的回傳結束時間(ti最后一個條帶回傳結束時間)；

M表示衛星的存儲的最大容量；

E表示可以消耗的衛星能量閾值；

rikv表示t時刻衛星上的存儲容量使用數值；

Et表示t時刻衛星上的電量數值；

tsuv,u≠v表示衛星觀測條帶oiku和條帶oikv之間的姿態轉換時間；

Tsij,i≠j表示衛星觀測目標ti和目標tj之間的姿態轉換時間；

fuv∈(0,1),u,v∈oik,fuv=1表示觀測條帶oijku和條帶oijkv連續觀測；

Fij∈(0,1),i,j∈T,Fij=1表示任務ti和任務tj被衛星s連續觀測；

需要說明的是觀測目標ti的所有條帶觀測收益相同；當oikv為立體成像任務條帶時，pikv固定值，并且此時wsikv=weikv，即立體成像任務的觀測開始時間是固定的。

1.2 模型建立

1)目標函數

(1)

式中：wi為觀測目標ti的綜合收益(價值綜合優先級)；xik=1表示目標i在衛星s的第k個時間窗口觀測 ；xikv=1表示目標i的任務條帶v在衛星s的第k個時間窗口觀測，0表示任務條帶v沒有被選擇觀測。

2)約束條件

(1)觀測時間窗口約束，即任務及其條帶的觀測時間不得超出其時間窗口，即

?v∈oi:(xikv=1)?(wsikv≤wsrikv≤

werikv≤weikv)

(2)

(2)任務之間的姿態機動時間約束，即兩個連續觀測任務中，前一個任務的觀測結束時間加上機動時間不得超過后一個任務的觀測開始時間，即

?ti,tj∈T:(Fij=1)?Wei+Tsij≤Wej

(3)

式中：Tsij為機動時間，Wej為后一任務的觀測開始時間。

(3)連續觀測條帶之間的姿態機動時間約束，即兩個連續觀測條帶中，前一個條帶的觀測結束時間加上機動時間不得超過后一個條帶的觀測開始時間，即

?u,v∈oi:(fuv=1)?wsriku+diku+tsuv≤wsrikv

(4)

(4)任務觀測規則約束，即一個任務的所有條帶在其一次觀測機會中必須全部觀測或者全部不觀測，即

(5)

(5)任務觀測唯一性約束，即在一個調度周期中，每個任務及其條帶只能被觀測一次，即

(6)

式中：NT為觀測目標總量。

(6)實傳任務約束，即實傳任務的觀測時間與回傳時間必須在同一時間段，即

?ti∈T,?i∈Oi:(ui=1)?(dsi≤wrsi

(7)

式中：wrsi為實傳任務的觀測時間，di為回放持續時間。

(7)立體成像約束，即立體成像任務條帶的最早可見時間與最晚可見時間固定不變，即

?ti∈T:(sdi=1)?(wsikv=weikv)

(8)

式中：sdi=1代表條帶立體成像。

(8)任務回傳約束，即對于存儲回放任務，每個任務的回傳時間必須在其觀測時間之后，即

?ti∈T,?i∈Oi:(ui=0)?(wrsi<

wrsi+di≤dsi)

(9)

式中：Oi為目標分解的元任務集合。

(9)衛星存儲約束，即任意時刻衛星上觀測任務所占用的存儲容量不能超出其存儲器的容量，即

?t∈[Ssce,Esce]:Mt≤M

(10)

式中：Mt為任意t時刻衛星固態存儲的存儲容量。

(10)衛星能量約束，即任意時刻衛星上能量存量不能低于衛星可消耗的能量閾值，即

?t∈[Ssce,Esce]:Et≥E

(11)

1.3 模型求解

高分多模衛星調度模型的求解是一類復雜的組合優化問題，可分為精確算法和近似算法。由于在實際應用中需要在一定的計算條件下，快速的求解出較優解。以啟發式算法為代表的近似算法能夠在短時間內獲得問題的相對滿意解[7]。同時綜合考慮高分多模衛星生成方案的時效性，以及衛星動作的連續性，避免在方案中插入任務產生復雜的約束傳播過程，設計了基于時序的動態前瞻啟發式算法；按照場景的開始時間到結束時間的順序推演來安排任務，算法中采用基于專家知識的啟發式規則來決定當前任務的選擇及衛星動作序列的安排。算法步驟及算法流程如圖1描述如下。

圖1 算法流程圖Fig.1 Algorithm flow chart

(1)獲取預處理之后的任務隊列及時間窗口信息；

(2)按照開始時間早的順序排列任務，形成任務列表，判斷任務是否是直拍直傳任務或回傳任務，如果是則進入(3)，不是則(4)；

(3)判斷任務是否違反姿態機動及回傳約束，如果是則返回(1)，否則加入(7)的回傳窗口隊列；

(4)按順序選取當前任務Ti，檢查任務是否安排觀測；

(5)按照規則決定當前任務Ti是否安排觀測，如果安排轉(6)，否則轉(1)；

(6)選擇當前任務方案安排衛星開機方案，轉(7)；

(7)把Ti放入回傳窗口隊列，等待下一個回傳窗口按照一定規則回傳該任務；

(8)檢查Ti與之前任務之間能否安排對日定向或者對地定向活動，滿足要求則安排本任務，否則轉(1)；

(9)輸出最終任務調度結果及衛星動作序列。

1.4 算法規則

對于高分多模衛星而言，由于其具有三向的機動能力，觀測目標具有一個大的時間窗口，其觀測開始時間可以在這個大的時間窗口內任意選擇，這樣就導致任務可以在時間窗口之內滑動，那么任務沖突檢測就相對復雜。

在高分多模衛星工程實現中，為保障綜合效益最大化策略，其目標是在成像質量與任務數量之間尋找一個平衡點[8]，即爭取完成更多的任務同時成像質量也有所提高。在前瞻任務組中，如果當前任務的觀測開始時間安排在最佳成像時間點，且完成時間與后續任務的最佳成像時間點不沖突，則當前任務觀測安排在最佳成像時間點；如果當前任務的完成時間與后續任務的最佳成像時間點存在交錯，則當前任務安排在其最早成像時間點，保證后續任務安排在其最佳成像時間點。在工程實現中，前瞻任務與當前任務存在沖突時選擇任務的規則：成像質量>優先級>剩余觀測機會>窗口的長短>側擺角的大小>俯仰角的大小。下面對各個規則進行簡要描述。

(1)成像質量優先策略，指任務觀測安排在成像最佳觀測時間點，以期望完成任務的平均成像質量最高。但是如果任務較為密集，這樣選擇會對后續任務時間影響較大，導致有些任務由于時間窗口被占用太多而無法觀測。

(2)高優先級，指由仿真管控給出的任務重要程度的度量，數值在1-10之間，值越大重要程度越高，需要優先完成。

(3)剩余觀測機會，指在當前時間窗口之后任務還有存在的可觀測時間窗口數量稱為該任務的剩余觀測機會。如果兩個任務在執行時間上嚴格沖突，一般而言，有剩余觀測機會的任務可以考慮延后安排觀測。

(4)觀測時間窗口的長短，指在優先級相同的情況下，觀測時間短的任務優先安排，這是因為時間窗口越短可能引起沖突的概率就越小，能夠安排更多任務。

(5)側擺角的大小，側擺角越大則拍攝圖像的質量越差，因此當任務沖突時，盡量選擇側擺角較小的任務安排觀測。

(6)俯仰角的大小，俯仰角越大則拍攝圖像的質量越差，因此當任務沖突時，盡量選擇俯仰角較小的任務安排觀測。

另外，當沖突任務的觀測時間窗口的長短、側擺角的大小、俯仰角的大小等3種情況下差別在10%以內時，認為其差別在可以接受的范圍內，然后進行下一個判斷標準的比較。當2個任務5個判斷標準都通過時，則安排觀測時間點靠前的任務，舍棄另一個任務。

2 試驗結果及分析

高分多模衛星規劃系統采用瀏覽器和服務器(B/S)架構模式，后端部署于資源中心高性能計算服務器上，滿足復雜的規劃算法計算要求。操作人員通過瀏覽器界面操作軟件，并可以設置各種可配置資源及規則項。

為測試系統目標訪問特性，在需求界面中錄入多個點目標散列分布于高分多模衛星單軌可視范圍內(見圖2)。

圖2 測試點目標分布圖Fig.2 Spatial distribution of the testing target points

(1)點1，2，3位于星下點兩側，用于測試訪問特性；并將點2和點3優先級設置為8(較高)。

(2)點7位于星下線較遠位置，滾動角超過40°，用于測試規劃的約束滿足情況。

(3)點4，5，6位于星下線軌跡同一側，并且具有相同經度和相同的觀測優先級，用于測試目標的訪問順序。

將圖2中7個目標作為一組輸入到系統中進行任務規劃方案計算，經過數秒時間的計算后輸出的方案如圖3所示。

圖3 測試目標規劃方案Fig.3 Planning results based on testing targets

從規劃結果可以分析得出：

(1)7個點目標參與規劃，高分多模衛星通過三軸機動，實現了星下線附近6個目標的單次過境全覆蓋。第7個目標點處在衛星可視范圍內，但是超出設置的40°滾動角范圍，沒有對其進行觀測，符合設計預期。

(2)點2和點3設置了較高的觀測優先級，而且位于星下線較近的位置，可以通過較小的滾動角和俯仰角完成覆蓋。從輸出的收益值可以看出，這兩點達到最高的收益值，符合設計預期。

(3)點4，5，6位于同一個經度上，觀測順序為自東向西依次觀測，結合衛星飛行和地球自轉特性，滿足衛星總體姿態變化量小，能源消耗低的要求，符合設計預期。

(4)該規劃方案經過動態啟發算法計算，綜合收益值為239 322,是規劃算法的相對最優解，滿足最大化的用戶收益。

3 結束語

本文依據高分多模衛星成像特點，考慮到敏捷衛星任務規劃的多樣化用戶需求和使用約束，根據衛星規劃的難點，抽象出了問題模型，并采用了基于可配置規則的啟發式算法，從規劃結果可以看出，對于多目標任務的場景，任務規劃系統可以快速有效的生成規劃方案，在符合約束的條件下，實現對目標的最大化覆蓋。通過在軌測試的檢驗，也達到了較好的效果。

隨著衛星使用年限的增長，衛星的使用約束將會出現變化，未來還需要對模型進行針對性優化以滿足新情況的使用，實現對高分多模衛星動態的效率最大化管理。