多站多星任務(wù)調(diào)度模型及求解

王萬玉,張志強

(中國科學(xué)院對地觀測與數(shù)字地球科學(xué)中心,北京 100086)

1 引 言

隨著空間技術(shù)及遙感應(yīng)用業(yè)務(wù)化、產(chǎn)業(yè)化的發(fā)展,越來越多的中低軌道衛(wèi)星和地面接收站投入使用,使得如何合理有效地使用地面接收站資源,快速、高效地制定衛(wèi)星數(shù)據(jù)接收計劃,最優(yōu)化接收衛(wèi)星數(shù)據(jù),成為一個亟待解決的問題。

目前,多數(shù)任務(wù)調(diào)度研究針對的是單衛(wèi)星[1]或多星任務(wù)調(diào)度[2,3],主要解決衛(wèi)星資源的優(yōu)化問題;或多衛(wèi)星單地面接收系統(tǒng)[4],主要解決多星任務(wù)沖突的問題;或多星地面資源配置[5,6],主要解決多星測控資源優(yōu)化配置問題。已有任務(wù)調(diào)度模型大多是針對某一特定的任務(wù)類型,較難擴展到多接收站多衛(wèi)星系統(tǒng)的遙感數(shù)據(jù)接收任務(wù)調(diào)度上來。對多站多星接收任務(wù)的調(diào)度問題,需針對遙感衛(wèi)星數(shù)據(jù)接收任務(wù)的特征,如用戶需求的多樣性、地面接收資源的使用約束,以及后續(xù)數(shù)據(jù)傳輸、處理的需求,建立針對該系統(tǒng)任務(wù)需求的優(yōu)化調(diào)度模型,以滿足對地觀測衛(wèi)星應(yīng)用中的最優(yōu)化接收衛(wèi)星數(shù)據(jù)的需求。

本文針對遙感衛(wèi)星接收任務(wù)的特征,分析了多站多星任務(wù)調(diào)度的主要約束條件,提出了完成任務(wù)優(yōu)先級之和最大與盡可能使用同一天線完成同一任務(wù)兩個優(yōu)化目標(biāo)函數(shù);建立了基于約束滿足優(yōu)化問題的多站多星任務(wù)調(diào)度優(yōu)化模型;將多站多星任務(wù)調(diào)度優(yōu)化模型分為預(yù)處理和優(yōu)化兩個階段進(jìn)行求解。預(yù)處理過程綜合利用貪婪算法和約束傳播相結(jié)合的方法;優(yōu)化過程主要根據(jù)任務(wù)初始調(diào)度結(jié)果進(jìn)行調(diào)整和優(yōu)化,在不降低完成任務(wù)優(yōu)先級之和的情況下,使得同一任務(wù)盡可能地由同一天線執(zhí)行,這樣就可以減少天線進(jìn)行任務(wù)轉(zhuǎn)換的次數(shù),增強衛(wèi)星遙感數(shù)據(jù)接收的完整性。

2 多站多星任務(wù)調(diào)度的特征與約束分析

多站多星任務(wù)調(diào)度是一個基于約束的資源優(yōu)化問題[7],即在一定的約束條件下,將有限的資源分配到不同的任務(wù)時間段上,其目標(biāo)之一是在給定的時間內(nèi)完成最多的任務(wù),或者在考慮任務(wù)的權(quán)重時最大化完成任務(wù)的權(quán)重之和,即在衛(wèi)星可視時間窗口集內(nèi),選擇執(zhí)行的任務(wù)權(quán)重之和最大。

多站多星任務(wù)調(diào)度主要受任務(wù)約束、資源約束和時間窗口約束3種約束關(guān)系的制約,任務(wù)約束指的是任務(wù)的優(yōu)先級高低排序、任務(wù)執(zhí)行過程的不可中斷性等;資源約束主要指的是地面站接收系統(tǒng)的可用性、可選擇性、任務(wù)轉(zhuǎn)換時間間隔等;時間窗口約束指的是時間窗口的開始時間和結(jié)束時間、時間窗口的可用性等。

2.1 任務(wù)約束

假設(shè)有Mt個任務(wù)T={T1,T2,…,TMt}所屬衛(wèi)星有Ms顆S={S1,S2,…,SMs},所有任務(wù)按照開始時間的先后順序進(jìn)行編號,即 t1s<…

(1)任務(wù)優(yōu)先級

由于地面站資源的有限性,且用戶對衛(wèi)星遙感數(shù)據(jù)的需求存在差異性,任務(wù)的重要程度是不相同的。因此,任務(wù)首先存在優(yōu)先級不同這樣的約束。

任務(wù)優(yōu)先級確定該衛(wèi)星數(shù)據(jù)接收任務(wù)需求的重要程度,該值是由國家緊急需求、用戶訂購需求重要程度、衛(wèi)星數(shù)據(jù)類型以及需求時間先后順序等因素綜合得出。國家緊急需求任務(wù)務(wù)必調(diào)度執(zhí)行;用戶訂購需求任務(wù)盡最大可能地調(diào)度執(zhí)行,為區(qū)分用戶需求的重要程度,分若干等級設(shè)置其優(yōu)先級;重要衛(wèi)星數(shù)據(jù)存檔任務(wù)盡可能實施,同樣分若干等級設(shè)置其優(yōu)先級;其余數(shù)據(jù)接收任務(wù)根據(jù)時間窗口安排。這些任務(wù)的優(yōu)先級依次降低,如表1所示。

表1 任務(wù)優(yōu)先級Table 1 Task Priority

在討論衛(wèi)星遙感數(shù)據(jù)接收任務(wù)需求時,我們按照表1為每一個任務(wù)分配一個優(yōu)先級,即Mt個任務(wù)的優(yōu)先級是p={p1,p2,…,pMt}。一種可行的調(diào)度方案是按照任務(wù)優(yōu)先級由高至低的順序進(jìn)行任務(wù)調(diào)度。

(2)任務(wù)是否必須被調(diào)度執(zhí)行

為說明該約束,我們首先定義任務(wù)決策變量w={w1,w2,…,wMt}:

假設(shè)一個任務(wù)是否必須被執(zhí)行用Ct來表示,則該約束可以表示為

(3)任務(wù)執(zhí)行過程的不可中斷性

此約束表明,任務(wù)一旦被調(diào)度執(zhí)行,就必須被完成,不允許插入其它任務(wù)。

2.2 資源約束

地面站資源主要包括地面接收天線與伴隨天線的控制、數(shù)據(jù)接收通道、記錄和數(shù)據(jù)傳輸?shù)确窒到y(tǒng),這些資源統(tǒng)稱為地面接收天線系統(tǒng)資源。我們將多地面站多套接收天線資源作為整體來表現(xiàn)對接收遙感衛(wèi)星下傳數(shù)據(jù)是否可用,且在任意時刻一個地面接收天線只能執(zhí)行一個數(shù)據(jù)接收任務(wù)。

衛(wèi)星遙感數(shù)據(jù)接收任務(wù)在調(diào)度過程中,首先選擇合適的地面接收天線系統(tǒng),需要考慮天線系統(tǒng)的可用性、資源容量限制和任務(wù)轉(zhuǎn)換調(diào)整時間。

(1)天線系統(tǒng)的可選擇性和可用性

如果地面站接收天線系統(tǒng)能夠接收某顆衛(wèi)星的遙感數(shù)據(jù),并且能夠正常工作,那么就稱該天線系統(tǒng)對該衛(wèi)星是可用的,否則便是不可用的。記AVA為某一時刻地面天線對任務(wù)的可用性,則:

定義資源約束為Cr,則天線系統(tǒng)資源可選擇性與可用性約束Cr1為

式(4)表示任務(wù)Ti要么未被調(diào)度(wi=0),要么被調(diào)度安排(wi=1),此時必須至少存在一個可用的地面接收天線。

(2)天線任務(wù)轉(zhuǎn)換時間

地面接收天線由一個任務(wù)轉(zhuǎn)向執(zhí)行另一個任務(wù)必須有一段時間用來預(yù)置天線、配置系統(tǒng)參數(shù)并跟蹤衛(wèi)星。一般地,該時間段長度為3～5 min。假設(shè)該時間段為Δt,則天線任務(wù)轉(zhuǎn)換時間約束Cr2為

式(5)表示對任意地面接收天線系統(tǒng) Aj,它所執(zhí)行的任意兩個任務(wù)之間的時間間隔都不小于天線任務(wù)轉(zhuǎn)換時間。同時,該式還表明,在任意時刻,一個地面天線最多只能執(zhí)行一個任務(wù)。

2.3 時間約束

多站多星任務(wù)調(diào)度問題的時間約束主要包括任務(wù)調(diào)度時間范圍約束 Ctime和衛(wèi)星過境時間窗口約束Cw。

假設(shè)任務(wù)調(diào)度開始時間是0,截止時間是thorizon,則調(diào)度時間約束Ctime為

式中,tis和tie分別是任務(wù)Ti的開始時間和結(jié)束時間。該約束表明,任何一個任務(wù)的完成必須在給定截止時間之前。

時間窗口指的是遙感衛(wèi)星經(jīng)過地面站接收覆蓋范圍時的入境和出境之間的時間段。只有在這個時間段,衛(wèi)星和地面站才是可見的,才能進(jìn)行數(shù)據(jù)傳輸,地面接收天線才能執(zhí)行待調(diào)度任務(wù)。衛(wèi)星過境時間窗口可用開始時間、結(jié)束時間和可用性狀態(tài)3個屬性來描述,可用性狀態(tài)用來標(biāo)識該時間窗口是否具有數(shù)據(jù)接收意義、是否已經(jīng)被調(diào)度任務(wù)占用等。

多站多星數(shù)據(jù)接收的時間窗口存在多個時間窗口相互重疊的現(xiàn)象,不同天線之間存在共視區(qū)。為此,我們定義一個時間窗口需求變量Qij,它表示任務(wù)Ti對地面接收天線Aj的時間窗口需求。則時間窗口需求約束Cw1為

式(7)表示任務(wù)Ti要么未被調(diào)度(wi=0),要么被調(diào)度安排(wi=1),此時∪Qij≠ ,在確定地面接收天線系統(tǒng)的情況下,至少有一個可用時間窗口被分配給該任務(wù)。

同時,要求一根天線在一段時間內(nèi)不能同時分配給兩個任務(wù),表現(xiàn)在時間窗口上就是一個時間窗口不能同時分配給兩個任務(wù)需求,用Cw2來表示:

3 基于約束滿足優(yōu)化問題的多站多星任務(wù)調(diào)度模型

多站多星任務(wù)調(diào)度具體可歸納為:根據(jù)任務(wù)需求,在一定的約束條件下,按照給定的優(yōu)化目標(biāo),將地面接收系統(tǒng)資源和可用時間窗口分配給不同的衛(wèi)星數(shù)據(jù)接收任務(wù),是一個包括地面接收天線選擇和時間窗口選擇的雙重選擇映射問題。

多站多星任務(wù)調(diào)度(TS)問題可以用4元組來表征:

式中,T為任務(wù)集,T={T1,T2,…,TMt},表示待調(diào)度的衛(wèi)星遙感數(shù)據(jù)接收任務(wù)集合;A為地面接收天線集,A={A1,A2,…,AMa},包括地面站所有在運行的接收天線;TW為時間窗口集:遙感衛(wèi)星相對于地面站的過境時間窗口集合,每一個時間窗口可以表示為一個閉區(qū)間[ts,te],ts表示時間窗口開始時間start-time,te表示時間窗口結(jié)束時間end-time;C為約束集,描述各種約束關(guān)系,主要包括任務(wù)約束、資源約束和時間窗口約束。

若使用4元組TS={T,A,TW,C}表示多站多星接收任務(wù)調(diào)度問題,則該問題的主要約束就是任務(wù)約束(Ct)、資源約束(Cr)和時間窗口約束(Ctime,Cw),即:

通常,多站多星任務(wù)調(diào)度問題的優(yōu)化目標(biāo)函數(shù)為最大化完成任務(wù)優(yōu)先級之和;實際工作中,總是希望盡可能使用同一地面接收天線系統(tǒng)完成同一任務(wù)的衛(wèi)星遙感數(shù)據(jù)接收,以利于后續(xù)數(shù)據(jù)處理及應(yīng)用。下面分別討論這些目標(biāo)函數(shù)。

完成任務(wù)優(yōu)先級之和函數(shù):

式中,Pi為任務(wù)優(yōu)先級,wi為任務(wù)決策變量。

為表示盡可能使用同一天線系統(tǒng)完成整個任務(wù)這一目標(biāo)函數(shù),我們定義另一任務(wù)決策變量W:

它與決策變量w的關(guān)系為wi=Wij,即只要有天線執(zhí)行了任務(wù)Ti,就說明該任務(wù)得到了調(diào)度執(zhí)行。

記地面接收站在調(diào)度時間范圍內(nèi)執(zhí)行任務(wù)總次數(shù)為f2:

根據(jù)上述的變量約定、約束分析和目標(biāo)函數(shù),我們建立多站多星任務(wù)調(diào)度優(yōu)化模型如下:

4 基于貪婪算法和約束傳播的模型求解算法

采用貪婪算法[1,8]和約束傳播相結(jié)合的方法,初步求解多站多星任務(wù)調(diào)度問題。貪婪算法使得優(yōu)先級高的任務(wù)最先得到調(diào)度,約束傳播主要減小了問題的搜索空間,加快求解速度。然后基于不降低完成任務(wù)優(yōu)先級之和的同時盡可能滿足同一任務(wù)由同一接收天線完成的思想對初始調(diào)度進(jìn)行調(diào)整和優(yōu)化,最后得到多站多星任務(wù)調(diào)度問題的最優(yōu)調(diào)度方案。

4.1 任務(wù)調(diào)度順序的選擇規(guī)則

任務(wù)調(diào)度順序的選擇規(guī)則如下:

(1)選擇優(yōu)先級最大的任務(wù);

(2)在優(yōu)先級相等時選擇所屬衛(wèi)星重要程度高的任務(wù);

(3)當(dāng)所屬衛(wèi)星重要程度相同時選擇開始時間較早的任務(wù)。

4.2 地面接收天線的選擇規(guī)則

對每一個待調(diào)度的任務(wù) Ti來說,若要被安排,則必須指定至少一個地面接收天線和相應(yīng)的接收時間窗口。而對某一地面接收天線Aj系統(tǒng)來說,它是否能夠完成該任務(wù),則要受兩方面因素的影響:一是它能否接收來自該任務(wù)所屬衛(wèi)星的遙感數(shù)據(jù);二是它與該衛(wèi)星是否存在與任務(wù)時間范圍相重疊的可用時間窗口。這兩方面因素都滿足時,才能將任務(wù)分配給該天線系統(tǒng),否則便不可以分配給該天線。

任務(wù) Ti時間范圍與可用時間窗口TWk之間在時間上有6種相對位置關(guān)系,如圖1所示。

圖1 任務(wù)時間范圍與可用時間窗口之間的關(guān)系Fig.1 Relations between task time scope and available time-window

如果任務(wù)Ti時間范圍與可用時間窗口TWk之間的相對位置處于類型0或者1,則說明兩者沒有任何重疊,不能將該任務(wù)分配給這樣的時間窗口;處于類型2或者3時,兩者部分重疊,根據(jù)重疊時間的長度決定是否將任務(wù)的一部分分配給該時間段,同時考慮剩余的時間能否再利用;處于類型4時,任務(wù)Ti完全可以在該時間窗口內(nèi)完成;處于類型5時,時間窗口在任務(wù)時間范圍內(nèi),只能執(zhí)行部分任務(wù)。

根據(jù)地面站的接收覆蓋范圍、地面接收天線的性質(zhì)和能力、地面站至地面數(shù)據(jù)中心的數(shù)據(jù)傳送和分發(fā)成本,將各地面站的接收天線按照總代價最小的原則進(jìn)行排序,即優(yōu)先考慮用接收范圍大、工作容量大、數(shù)據(jù)傳送成本低的地面接收天線來完成任務(wù)。

4.3 任務(wù)初始調(diào)度時的可行性判讀

假設(shè)某一地面接收天線 Aj能夠執(zhí)行待調(diào)度任務(wù)Ti且具有一個可用時間窗口TWk,該時間窗口與任務(wù)時間范圍重疊的部分記為[ts,te],那么在將任務(wù)分配給該天線之前,必須檢查它與已經(jīng)分配給該天線的任務(wù)是否有沖突。如果沒有沖突,就將任務(wù)Ti分配給天線Aj,執(zhí)行時間段為[ts,te],而后更新任務(wù)Ti的時間范圍和天線Aj的可用時間窗口。如果存在沖突,則根據(jù)沖突類型和天線任務(wù)轉(zhuǎn)換時間,減小[ts,te]為[t′s,t′e]。重新檢查如果任務(wù) Ti占用天線 Aj的時間范圍[t′s,t′e]是否存在沖突,直到?jīng)]有沖突或者時間范圍的長度小于最小任務(wù)長度為止。

這種任務(wù)分配可行性判讀方法,不僅可以檢測到天線執(zhí)行調(diào)度任務(wù)時是否發(fā)生沖突,且可以自適應(yīng)地調(diào)整待調(diào)度任務(wù)在該天線上可執(zhí)行的時間范圍,增強了任務(wù)的可分配性。

4.4 任務(wù)初始調(diào)度后的參數(shù)值更新

如果可將任務(wù)Ti分配給天線Aj,執(zhí)行時間段為[ts,te],那么就要更新任務(wù)Ti的時間范圍和天線Aj的可用時間窗口TWk,以便再次分配。同時,更新任務(wù)集,包括已經(jīng)得到調(diào)度的任務(wù)子集和未調(diào)度的任務(wù)子集,更新可用天線子集、可用時間窗口子集等。

4.5 任務(wù)初始調(diào)度優(yōu)化方法和過程

根據(jù)任務(wù)優(yōu)先級和天線有效性,利用貪婪算法和約束傳播相結(jié)合的方法進(jìn)行多站多星任務(wù)調(diào)度優(yōu)化模型的求解,常常會將本應(yīng)由一個地面接收天線系統(tǒng)執(zhí)行的任務(wù)分配給不同的天線,不利于地面站運行,原因是:任務(wù)轉(zhuǎn)換需要時間,浪費資源;同一任務(wù)記錄成不同文件,不利于后端處理。

因此,我們提出了盡可能使用同一天線完成整個任務(wù)的優(yōu)化目標(biāo)函數(shù),最大程度上減少任務(wù)調(diào)度過程中的任務(wù)分解。具體的調(diào)整優(yōu)化過程分兩步。

Step1:根據(jù)任務(wù)優(yōu)先級高低依次檢查任務(wù)調(diào)度預(yù)處理階段的調(diào)度結(jié)果,如果任務(wù)完全被分配給一個地面接收天線系統(tǒng)執(zhí)行,或者被分配給多個地面站的接收天線系統(tǒng)且每個地面站最多只有一個天線執(zhí)行該任務(wù),則繼續(xù)檢查下一個任務(wù),直至結(jié)束。

Step2:檢查該任務(wù)是否一定需要不同地面站的接收天線來執(zhí)行,因此才產(chǎn)生的任務(wù)分解。如果該任務(wù)被分配給同一地面站的不同接收天線系統(tǒng),則調(diào)整該任務(wù)的調(diào)度,使之使用同一地面站的同一個天線來執(zhí)行,轉(zhuǎn)Step1。

5 結(jié) 論

利用上述模型、求解算法及開發(fā)的軟件,對3個遙感衛(wèi)星地面站8套地面接收天線組成的衛(wèi)星地面接收站網(wǎng),接收10顆遙感衛(wèi)星的多站多星接收任務(wù)進(jìn)行了規(guī)劃調(diào)度。從規(guī)劃調(diào)度結(jié)果可以看出,優(yōu)先級別高的任務(wù)均已被優(yōu)先安排,所有的任務(wù)都得到了調(diào)度安排,且地面接收天線系統(tǒng)執(zhí)行任務(wù)的時間長度較為均衡,沒有沖突;從讀取任務(wù)輸入文件開始至生成任務(wù)調(diào)度計劃表僅需5 s。

該優(yōu)化調(diào)度模型及求解算法已成功應(yīng)用于遙感衛(wèi)星數(shù)據(jù)接收的日常運行工作中,實際使用效果表明,本文提出的多站多星接收任務(wù)調(diào)度的主要約束條件和優(yōu)化目標(biāo)函數(shù)是合理的,構(gòu)建的模型和采用的算法是可行的。

[1]William J Wolfe,Stephen E Sorensen.Three Scheduling Algorithms Applied to the Earth Observing Systems Domain[J].Management Science,2000,46(1):148-168.

[2]劉洋,陳英武,譚躍進(jìn).一類多衛(wèi)星動態(tài)調(diào)度問題的建模與求解方法[J].系統(tǒng)仿真學(xué)報,2004(12):2696-2699.LIU Yang,CHEN Ying-wu,TAN Yue-jin.Modeling and Solution of the Problem ofMulti-SatellitesDynamic Scheduling[J].Journal of System Simulation,2004(12):2696-2699.(in Chinese)

[3]劉洋,賀仁杰,譚躍進(jìn).基于約束滿足的多衛(wèi)星調(diào)度模型研究[J].系統(tǒng)工程與電子技術(shù),2004(8):1076-1079.LIU Yang,HE Ren-jie,TAN Yue-jin.Modeling the Scheduling Problem of Multi-satellite Based on the Constraint Satisfaction[J].System Engineering and Electronics,2004(8):1076-1079.(in Chinese)

[4]劉洋,陳英武,譚躍進(jìn).衛(wèi)星地面站系統(tǒng)任務(wù)調(diào)度動態(tài)規(guī)劃方法[J].中國空間科學(xué)技術(shù),2005(2):44-47.LIU Yang,CHEN Ying-wu,TAN Yue-jin.The Method of Mission Planning of the Ground Station of Satellite Based on Dynamic Programming[J].Chinese Space Science and Technology,2005(2):44-47.(in Chinese)

[5]王遠(yuǎn)振,高衛(wèi)斌,聶成.多星地面站系統(tǒng)資源配置優(yōu)化研究綜述[J].系統(tǒng)工程與電子技術(shù),2004(4):437-439.WANG Yuan-zhen,GAO Wei-bin,NIE Cheng.Summary of the resource configuration optimization for a multi-satellite ground station system[J].Systems Engineering and Electronics,2004(4):437-439.(in Chinese)

[6]金光,武小悅,高衛(wèi)斌.衛(wèi)星地面站資源調(diào)度優(yōu)化模型及啟發(fā)式算法[J].系統(tǒng)工程與電子技術(shù),2004(12):1839-1841.JIN Guang,WU Xiao-yue,GAO Wei-bin.Ground station resource scheduling optimization model and its heuristic algorithm[J].Systems Engineering and Electronics,2004(12):1839-1841.(in Chinese)

[7]Joseph C Pemberton,Flavius Galiber III.A Constraint-Based Approach to Satellite Scheduling[EB/OL].2006-09-05[2010-01-08].http://www.cs.sfu.ca/cs/research/groups/ISL/library/Satellite%20Scheduling/pemberton.galiber.dimacs98.pdf.

[8]Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to Algorithms[M].2nd ed.New York:McGraw-Hill Book Company,2001.