一種基于DCSP模型的遙感衛(wèi)星任務(wù)調(diào)度算法仿真與分析

馬紅梅， 項(xiàng) 杰， 王 昊， 李瑞琴

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

0 引言

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

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

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

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

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

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

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

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

(1) 時(shí)間窗口

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

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

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

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

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

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

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

3.1 任務(wù)元組描述

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

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

(1)

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

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

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

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

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

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

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

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

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

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

(2)

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

(3)

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

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

(4)

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

(5)

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

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

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

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

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

基于DCSP任務(wù)調(diào)度算法，是按照遙感衛(wèi)星任務(wù)的綜合評(píng)估值進(jìn)行調(diào)度計(jì)算的。假如第i個(gè)任務(wù)要進(jìn)入任務(wù)隊(duì)列，則算法復(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)。為驗(yàn)證此算法的有效性，根據(jù)遙感衛(wèi)星實(shí)際的工作場(chǎng)景，進(jìn)行算法測(cè)試。

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

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

表1 規(guī)劃場(chǎng)景

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

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

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

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

5 結(jié)論

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