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

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

0 引言

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

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

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

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

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

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

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

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

(1) 時間窗口

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

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

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

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

(3) 任務(wù)的不可中斷性

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

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

3.1 任務(wù)元組描述

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

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

(1)

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

單次遙感任務(wù)可用的資源包括：

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

b) 圖像類型R2——可以是光學(xué)圖像、雷達(dá)圖像等；

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

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

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

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

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

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

(2)

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

(3)

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

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

(4)

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

(5)

4 算法設(shè)計及分析

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

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

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

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

基于DCSP任務(wù)調(diào)度算法，是按照遙感衛(wèi)星任務(wù)的綜合評估值進(jìn)行調(diào)度計算的。假如第i個任務(wù)要進(jìn)入任務(wù)隊列，則算法復(fù)雜度可表示為

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

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

(6)

因此，基于DCSP任務(wù)調(diào)度算法的算法復(fù)雜度為O(n2)。為驗證此算法的有效性，根據(jù)遙感衛(wèi)星實際的工作場景，進(jìn)行算法測試。

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

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

表1 規(guī)劃場景

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

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

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

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

5 結(jié)論

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