一種基于DCSP模型的遙感衛星任務調度算法仿真與分析

馬紅梅， 項 杰， 王 昊， 李瑞琴

(上海衛星工程研究所， 上海 200240)

0 引言

傳統的衛星遙感任務功能的實現，是通過地面上注任務包，衛星根據地面安排好時序完成遙感任務。這種實現遙感任務的方法完全依賴于地面對此次遙感任務的精確分解，地面若注數不成功，將會導致遙感衛星任務的錯誤執行，進而會給遙感衛星的安全使用帶來影響。傳統的遙感任務功能的實現已不能滿足遙感衛星應用方面的要求。

本文提出一種基于DCSP(Dynamic Constraint Satisfaction Problem，動態約束滿足問題)模型的遙感衛星任務調度算法[1]。

1 遙感衛星任務

經過多年建設，我國已基本建成星地一體測控通信體系，但是我國的測控站尚未實現全球覆蓋，無法對衛星進行24小時全球跟蹤及監控。

遙感任務是指遙感衛星通過衛星資源對特定的地面目標進行探測。對于一般衛星遙感任務的實現，需要地面在測控弧段內，將提前安排好的指令上注。遙感衛星收到指令后，按照指令執行時間，依次執行指令。由于傳統遙感衛星無任務調度的能力，即僅根據地面上注的遙感衛星觀測目標，智能分解衛星指令的能力。隨著遙感衛星任務量的增多，導致地面指令的分解工作量大幅度增大。

對于傳統的遙感衛星任務，若存在遙感任務沖突，只有任務執行后將無正確數據傳送到地面，才發現此次任務的失敗。這樣即浪費寶貴的遙感衛星資源，又增加了地面人員的工作要求。因此，遙感衛星星載軟件需增加一種任務調度算法，從而有效完成各項遙感任務。

2 遙感衛星調度約束

遙感衛星任務調度問題的本質是在一定的約束條件下，按照給定的衛星有限資源條件下，將衛星資源和衛星可用時間窗口分配給不同任務，是一個包括衛星資源選擇和時間窗口選擇的雙重選擇問題，主要有以下幾個要求和特點。

(1) 時間窗口

衛星調度的一個最大特點在于衛星是圍繞地球按照一定的軌道運行，并不是時時可見的。因此，這事實上是增加了衛星調度過程中的約束條件。如果要衛星執行對某個目標的觀測任務，那么在衛星遙感器和目標之間必須要有可見時間窗口。而這個時間窗口是由衛星軌道、遙感器、目標位置共同確定的。因此，進行調度計算時，遙感衛星成像時間必需在衛星時間窗口內。

(2) 衛星資源的可選性

傳統的調度問題，資源通常都是可以完全互換的。在衛星調度問題中，具有同樣功能的衛星資源是可以互換的。但是，由于受到地面設備資源的制約，同樣的數據下傳，需要采用不同數據下傳通道。

假設有一個觀測任務vi，要求觀測目標，需要及時下傳載荷數據。但是此時數傳地面站比較忙，無法下傳。而此時，衛星只能現將數據暫時存儲等數傳地面站有空閑時間再將數據下傳到地面。或者使用中繼通道，將數據先發送到中繼衛星，再由中繼衛星下傳到地面。

(3) 任務的不可中斷性

衛星的任務通常具有不可中斷性，即在調度過程中，若確定了某個任務的開始時間和結束時間，則在該段時間內，不能插入其它任務。

3 調度約束算法實現

3.1 任務元組描述

遙感衛星調度問題可以用五元組來描述：

J={V,P,Q,TB,R}

(1)

式中：V為要執行的遙感任務集合(即遙感衛星觀測目標集)，包括預先確定的任務和隨時改變的任務，V={v1,v2,…,vi,…}，vi表示遙感衛星第vi個遙感任務；P為遙感衛星任務等級，pvi表示遙感任務vi本身的重要程度，pvi∈{1,2,3,4,5}，數值越大，等級越高；Q為遙感衛星用戶優先級，qvi表示遙感任務用戶需求緊迫程度，qvi∈{1,2,3,4,5}，數值越大，用戶優先級越高；TB為任務時間窗口集，相對于某個指定的遙感任務，每個衛星的可用時間窗口的集合，每一個時間窗口可表示為一個閉區間(Svi,Ovi)，其中Svi表示遙感任務vi開始時刻，Ovi表示遙感任務vi結束時刻，受到遙感衛星的能源限制，每軌的工作任務數量是有限的，tmin表示兩次遙感任務的最小間隔時間；R為衛星資源集，單次任務可用的資源，R={R1,R2,…,Rm,…}。

單次遙感任務可用的資源包括：

a) 目標區域R1——可以是點目標(一個很小的矩形區域，矩形中心點代表需要觀測目標的經緯度)，或者區域目標(由一個經緯度定義的多邊形區域)；

b) 圖像類型R2——可以是光學圖像、雷達圖像等；

c) 成像時間R3——定義該圖像需求的時間范圍，如果超過該時間，該需求或者不安排或者降低優先級；

d) 下傳途徑R4——根據地面站的情況，確定圖像是否需要下傳或者先行保存，數傳下傳通道選擇數傳地面站通道，還是選擇中繼衛星通道下傳；

e) 觀測窗口R5——任務目標，不在遙感衛星的觀測區間內，則需要對該任務進行降級。

3.2 任務調度算法描述

一般來說，由于單顆衛星資源的短缺，用戶需求不能全部被滿足。因此，單顆遙感衛星調度的目標就是在有限的衛星資源的條件下，最大化的完成遙感任務。單次遙感任務，需在單顆衛星資源的能力范圍之內。

遙感衛星任務調度，需綜合考慮遙感衛星任務等級[2]、遙感衛星用戶優先級、資源滿足等因素[3]，采用加權合法來設計遙感任務的目標。因此定義每次遙感任務vi綜合評估值為

(2)

由此定義遙感衛星遙感任務的規劃模型為

(3)

式中：a、b分別為pvi、qvi的加權系數；cm為Rm的系數，當cm=1時，資源Rm滿足任務要求，當cm=0時，資源Rm不滿足任務要求。

按照每次遙感任務vi綜合評估值排序形成的新的評估任務隊列為

(4)

遙感衛星在執行任務的時候，任務數量是一個動態變化的過程，任務執行順序會根據任務的優先級進行動態調整的。如圖1所示，如果遙感任務v2的開始時間，遙感任務v1還沒有正確執行結束，兩次遙感任務v1和v2的執行間隔時間不滿足遙感衛星能源所能保證的最小保護時間tmin，新的遙感任務v2將會被丟棄。

(5)

4 算法設計及分析

針對遙感衛星的任務動態調度，本文設計了一種基于DCSP模型的遙感衛星任務調度算法。

基于DCSP任務調度算法，步驟如下：

a)計算任務集V中每次任務的綜合評估值Kvi；

b)將任務集V中的綜合評估值Kvi降序排序，形成新的評估任務隊列V′；

基于DCSP任務調度算法，是按照遙感衛星任務的綜合評估值進行調度計算的。假如第i個任務要進入任務隊列，則算法復雜度可表示為

E=0+1/2(0+1)+1/3(0+1+2)+…+

1/n(0+1+2+…+n-1)=n(n-1)/4

(6)

因此，基于DCSP任務調度算法的算法復雜度為O(n2)。為驗證此算法的有效性，根據遙感衛星實際的工作場景，進行算法測試。

測試環境：2.93 GHz CPU，2G內存，Microsoft Visual C++ 6.0開發環境。

測試數據：采用了5組不同規劃場景，每個規劃場景中包括普通的任務目標和重點目標和特殊目標。其中，重點目標占總任務目標比例為20%。特殊目標占總任務目標比例為5%。每個場景中目標信息如表1所示。

表1 規劃場景

算法測試過程中，分別設置a、b加權系數為0.4和0.8,即衛星用戶的優先等級是首選。仿真測試數據如表2所示。

由表2可知，規劃時間越長，任務規劃時間越長，目標覆蓋率越高。特別是針對優選目標能夠達到100%的覆蓋率。

綜上所述，一種基于DCSP模型的遙感衛星任務調度算法，能夠實時解決遙感任務中資源約束等限制，能夠滿足遙感衛星任務調度功能。

表 2 測試數據

5 結論

本文描述了遙感衛星任務調度流程，深入分析了遙感任務時間窗口及衛星資源，有針對性地提出了一種基于DCSP模型的遙感衛星任務調度算法。該算法首先按照遙感任務綜合評估值形成新的評估任務隊列，然后根據是否滿足最小保護時間，從而確定出遙感任務是否插入遙感衛星執行隊列。仿真結果表明，該算法可以對遙感任務進行高級調度規劃，滿足遙感衛星任務需求，對未來遙感衛星任務調度的設計有一定的參考價值。該算法已在遙感衛星中得到廣泛的應用，不僅減少遙感衛星對衛星測控弧段的依賴性，也能減少地面指令的分解工作量。