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

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

0 引言

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

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

1 遙感衛(wèi)星任務

經(jīng)過多年建設，我國已基本建成星地一體測控通信體系，但是我國的測控站尚未實現(xiàn)全球覆蓋，無法對衛(wèi)星進行24小時全球跟蹤及監(jiān)控。

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

對于傳統(tǒng)的遙感衛(wèi)星任務，若存在遙感任務沖突，只有任務執(zhí)行后將無正確數(shù)據(jù)傳送到地面，才發(fā)現(xiàn)此次任務的失敗。這樣即浪費寶貴的遙感衛(wèi)星資源，又增加了地面人員的工作要求。因此，遙感衛(wèi)星星載軟件需增加一種任務調(diào)度算法，從而有效完成各項遙感任務。

2 遙感衛(wèi)星調(diào)度約束

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

(1) 時間窗口

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

(2) 衛(wèi)星資源的可選性

傳統(tǒng)的調(diào)度問題，資源通常都是可以完全互換的。在衛(wèi)星調(diào)度問題中，具有同樣功能的衛(wèi)星資源是可以互換的。但是，由于受到地面設備資源的制約，同樣的數(shù)據(jù)下傳，需要采用不同數(shù)據(jù)下傳通道。

假設有一個觀測任務vi，要求觀測目標，需要及時下傳載荷數(shù)據(jù)。但是此時數(shù)傳地面站比較忙，無法下傳。而此時，衛(wèi)星只能現(xiàn)將數(shù)據(jù)暫時存儲等數(shù)傳地面站有空閑時間再將數(shù)據(jù)下傳到地面?；蛘呤褂弥欣^通道，將數(shù)據(jù)先發(fā)送到中繼衛(wèi)星，再由中繼衛(wèi)星下傳到地面。

(3) 任務的不可中斷性

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

3 調(diào)度約束算法實現(xiàn)

3.1 任務元組描述

遙感衛(wèi)星調(diào)度問題可以用五元組來描述：

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

(1)

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

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

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

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

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

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

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

3.2 任務調(diào)度算法描述

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

遙感衛(wèi)星任務調(diào)度，需綜合考慮遙感衛(wèi)星任務等級[2]、遙感衛(wèi)星用戶優(yōu)先級、資源滿足等因素[3]，采用加權(quán)合法來設計遙感任務的目標。因此定義每次遙感任務vi綜合評估值為

(2)

由此定義遙感衛(wèi)星遙感任務的規(guī)劃模型為

(3)

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

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

(4)

遙感衛(wèi)星在執(zhí)行任務的時候，任務數(shù)量是一個動態(tài)變化的過程，任務執(zhí)行順序會根據(jù)任務的優(yōu)先級進行動態(tài)調(diào)整的。如圖1所示，如果遙感任務v2的開始時間，遙感任務v1還沒有正確執(zhí)行結(jié)束，兩次遙感任務v1和v2的執(zhí)行間隔時間不滿足遙感衛(wèi)星能源所能保證的最小保護時間tmin，新的遙感任務v2將會被丟棄。

(5)

4 算法設計及分析

針對遙感衛(wèi)星的任務動態(tài)調(diào)度，本文設計了一種基于DCSP模型的遙感衛(wèi)星任務調(diào)度算法。

基于DCSP任務調(diào)度算法，步驟如下：

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

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

基于DCSP任務調(diào)度算法，是按照遙感衛(wèi)星任務的綜合評估值進行調(diào)度計算的。假如第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任務調(diào)度算法的算法復雜度為O(n2)。為驗證此算法的有效性，根據(jù)遙感衛(wèi)星實際的工作場景，進行算法測試。

測試環(huán)境：2.93 GHz CPU，2G內(nèi)存，Microsoft Visual C++ 6.0開發(fā)環(huán)境。

測試數(shù)據(jù)：采用了5組不同規(guī)劃場景，每個規(guī)劃場景中包括普通的任務目標和重點目標和特殊目標。其中，重點目標占總?cè)蝿漳繕吮壤秊?0%。特殊目標占總?cè)蝿漳繕吮壤秊?%。每個場景中目標信息如表1所示。

表1 規(guī)劃場景

算法測試過程中，分別設置a、b加權(quán)系數(shù)為0.4和0.8,即衛(wèi)星用戶的優(yōu)先等級是首選。仿真測試數(shù)據(jù)如表2所示。

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

綜上所述，一種基于DCSP模型的遙感衛(wèi)星任務調(diào)度算法，能夠?qū)崟r解決遙感任務中資源約束等限制，能夠滿足遙感衛(wèi)星任務調(diào)度功能。

表 2 測試數(shù)據(jù)

5 結(jié)論

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