趙 靜,趙尚弘,李勇軍,王 翔,趙衛(wèi)虎

(空軍工程大學(xué)信息與導(dǎo)航學(xué)院,西安 710077)

1 引 言

跟蹤與數(shù)據(jù)中繼衛(wèi)星系統(tǒng)(Tracking and Data Relay Satellite System,TDRSS)是轉(zhuǎn)發(fā)地球站對中、低軌道航天器的跟蹤測控信號,并對中、低軌道航天器發(fā)回地面的數(shù)據(jù)、圖像和話音等進(jìn)行實時、連續(xù)的中繼的系統(tǒng)。通常包括中繼衛(wèi)星(Tracking and Data Relay Satellite,TDRS)、用戶航天器與地面站3個部分[1-3]。由于中繼衛(wèi)星具有覆蓋性廣、實時性強(qiáng)、經(jīng)濟(jì)性好、不受國際政治形勢變化影響等優(yōu)點,其在對地遙感、海洋觀測、軍事偵察、載人航天等方面有著重要的應(yīng)用,具有極高的戰(zhàn)略價值,受到世界各國的高度重視[4-7]。

隨著航空航天領(lǐng)域中對地觀測、軍事偵察以及深空探測等技術(shù)的不斷發(fā)展,中繼衛(wèi)星數(shù)據(jù)傳輸呈現(xiàn)了大容量、高速率以及多樣化中繼任務(wù)的特點,衛(wèi)星資源優(yōu)化調(diào)度問題愈凸顯迫切和重要。特別是近年來,衛(wèi)星激光鏈路技術(shù)的日益成熟,基于星間激光鏈路的數(shù)據(jù)中繼衛(wèi)星組網(wǎng)是必然發(fā)展趨勢[8-10],對中繼衛(wèi)星調(diào)度問題提出了更多的挑戰(zhàn)。本文從模型表示和求解算法兩方面詳細(xì)論述了中繼衛(wèi)星調(diào)度問題,并根據(jù)衛(wèi)星激光和微波鏈路聯(lián)合組網(wǎng)的發(fā)展趨勢,討論了資源調(diào)度問題進(jìn)一步的發(fā)展方向。

2 中繼衛(wèi)星資源調(diào)度基本內(nèi)涵

中繼衛(wèi)星資源調(diào)度問題是根據(jù)中繼衛(wèi)星系統(tǒng)應(yīng)用的任務(wù)需求,對中繼衛(wèi)星資源進(jìn)行優(yōu)化配置,對信息的獲取、處理與傳輸活動進(jìn)行調(diào)度,制定出滿足中繼衛(wèi)星應(yīng)用任務(wù)需求的資源分配和活動調(diào)度方案[11-15]。

2.1 問題描述

中繼衛(wèi)星資源調(diào)度問題可以用5元組表示,T={t1,…,tn}是任務(wù)集合,n表示調(diào)度任務(wù)數(shù);R={r1,…,rm}是資源集合,m表示資源數(shù);C為約束集合;TW={,…}為可用時間窗口,表示第k個資源對第i個任務(wù)的第j個時間窗口;F是目標(biāo)函數(shù)。

根據(jù)衛(wèi)星資源調(diào)度問題的特點并參考相關(guān)研究的經(jīng)驗成果,中繼衛(wèi)星資源調(diào)度問題求解過程分為建立中繼任務(wù)想定、數(shù)學(xué)建模、求解和尋優(yōu)3個主要階段,其流程如圖1所示。首先,收集整理用戶需求以及可用資源狀態(tài),建立調(diào)度任務(wù)想定,確定任務(wù)的可見窗口集合;其次根據(jù)調(diào)度任務(wù)信息,建立關(guān)于中繼衛(wèi)星調(diào)度問題的數(shù)學(xué)模型,描述問題的優(yōu)化目標(biāo)和約束條件;最后,針對所研究的問題設(shè)計并實現(xiàn)求解算法,利用算法對模型進(jìn)行求解,確定每個調(diào)度任務(wù)序列和對應(yīng)的時間序列,最終輸出中繼衛(wèi)星資源調(diào)度計劃。

圖1 衛(wèi)星任務(wù)調(diào)度流程Fig.1 Process of satellite task scheduling

2.2 活動與資源

中繼衛(wèi)星資源調(diào)度問題中的活動指中繼衛(wèi)星與用戶星之間的信號傳輸活動,既包括中繼衛(wèi)星轉(zhuǎn)發(fā)地面站的跟蹤測控信號的前向信號傳輸,也包括用戶衛(wèi)星返回地面的數(shù)據(jù)、圖像、話音等的反向信號傳輸。中繼衛(wèi)星與用戶星都是在太空中高速運(yùn)動的平臺,其相對位置實時改變,因此它們之間的信號傳輸活動包括星間鏈路建立(天線捕獲與跟蹤等)與信號傳輸,是衛(wèi)星資源調(diào)度問題中的關(guān)鍵問題之一。

中繼衛(wèi)星資源調(diào)度問題中的資源指中繼衛(wèi)星上的天線資源,包括單址天線和多址天線。單址天線只能為一個用戶提供服務(wù);多址天線可以同時形成多個前向和反向波束,每個多址服務(wù)波束僅能提供單向的服務(wù)。

2.3 主要約束條件

中繼衛(wèi)星資源調(diào)度問題求解中存在很多約束,主要有衛(wèi)星資源和任務(wù)兩個方面的約束。

2.3.1 衛(wèi)星資源

衛(wèi)星資源的主要約束有可見時間窗口約束和太陽干擾約束。

(1)可見時間窗口約束

在中繼衛(wèi)星資源調(diào)度的約束條件中,可見時間窗口是中繼衛(wèi)星調(diào)度中一個重要的約束條件。數(shù)據(jù)中繼只有在用戶星與中繼衛(wèi)星之間能夠直視時進(jìn)行,即必須具有可見時間窗口。可見時間窗口是中繼衛(wèi)星與用戶星之間可通行的時間段的集合,是指在某時刻,用戶星與中繼衛(wèi)星之間的連線與地球沒有交點即兩者可視,中繼星與用戶星進(jìn)行數(shù)據(jù)中繼時必須建立穩(wěn)定的鏈路,建立過程分為準(zhǔn)備、捕獲、跟蹤、釋放4個階段,如圖2所示。

圖2 衛(wèi)星間鏈路建立過程Fig.2 Establishment of inter-satellite links

(2)太陽干擾約束

當(dāng)衛(wèi)星天線波束對準(zhǔn)太陽時,天線的有效噪聲溫度增加,有時甚至使通信中斷,這種現(xiàn)象稱為日凌中斷。對于極窄的天線波束來說,這種效應(yīng)極為嚴(yán)重,此時太陽光可能會充滿整個波束,噪聲溫度將會提高數(shù)千度。當(dāng)中繼星與用戶星間發(fā)生太陽干擾時,不僅會中斷數(shù)據(jù)通信而且可造成中繼星對用戶星跟蹤的失鎖。

2.3.2 任務(wù)資源

任務(wù)資源的主要約束有優(yōu)先級約束和任務(wù)約束。

(1)優(yōu)先級約束。中繼衛(wèi)星服務(wù)的用戶星不同,就會有不同的任務(wù)需要中繼,不同任務(wù)的優(yōu)先級不同,任務(wù)的優(yōu)先級越高,其活動越需要優(yōu)先安排。

(2)任務(wù)約束。如任務(wù)傳輸?shù)臅r段、最晚傳輸時間、指定中繼星傳輸、數(shù)據(jù)回傳地面站等。

3 模型表示

衛(wèi)星資源調(diào)度問題涉及計算機(jī)科學(xué)、運(yùn)籌學(xué)及人工智能等多個學(xué)科,研究人員針對不同的應(yīng)用場景,提出了各不同的建模方案。

3.1 數(shù)學(xué)規(guī)劃模型

基本的數(shù)學(xué)規(guī)劃有線性規(guī)劃(Linear Program,LP)、整數(shù)規(guī)劃(Integer Program,IP)、整數(shù)線性規(guī)劃(Integer Linear Program,ILP)、混合整數(shù)規(guī)劃(Mixed Integer Program,MIP)等。Gabrel[12]、Bensana[13]把衛(wèi)星觀測調(diào)度問題看作優(yōu)化問題,從數(shù)學(xué)規(guī)劃角度提出可以用ILP模型描述衛(wèi)星資源調(diào)度問題,但并未給出正式的描述模型。Arbabi[14]與Gooley[15]提出了衛(wèi)星數(shù)傳問題中的MIP模型,其調(diào)度數(shù)據(jù)輸入固定,并不完全適用于具有實時動態(tài)特點的中繼衛(wèi)星調(diào)度問題。Rojanasoonthon[16-17]針對美國的TDRSS采用并行機(jī)器調(diào)度理論對中繼衛(wèi)星資源調(diào)度問題進(jìn)行了研究,建立了中繼衛(wèi)星調(diào)度的混合整數(shù)規(guī)劃模型,模型中僅研究了不多于兩個時間窗口的調(diào)度問題,在實際調(diào)度問題中仍需要進(jìn)一步擴(kuò)展。

數(shù)學(xué)規(guī)劃模型具有成熟的理論基礎(chǔ)和廣泛的應(yīng)用,基本上可以描述衛(wèi)星任務(wù)調(diào)度問題中的所有約束,而且可以充分利用成熟的整數(shù)規(guī)劃軟件工具(如ILOG CPlex),但是并不適用于具有復(fù)雜調(diào)度約束且任務(wù)規(guī)模較大的衛(wèi)星任務(wù)調(diào)度問題。

3.2 約束滿足問題模型

中繼衛(wèi)星資源調(diào)度問題可以看作一類約束滿足問題(Constraint Satisfaction Problem,CSP)。方炎申[18-20]等基于約束滿足理論,通過分析中繼衛(wèi)星調(diào)度問題的特點與約束條件,建立了中繼衛(wèi)星調(diào)度問題的CSP模型。在約束條件分析的基礎(chǔ)上,建立了中繼衛(wèi)星單址鏈路調(diào)度和多址鏈路調(diào)度的數(shù)學(xué)模型,并對模型進(jìn)行求解,有效解決了中繼衛(wèi)星多址鏈路調(diào)度問題。張彥[21]等建立了中繼衛(wèi)星靜態(tài)調(diào)度的CSP模型,在此基礎(chǔ)上建立了中繼衛(wèi)星動態(tài)調(diào)度問題的動態(tài)約束滿足(Dynamic Constraint Satisfaction Problem,DCSP)模型,并設(shè)計了動態(tài)擴(kuò)展/刪除樹搜索算法求解,有效提高了該方法的可行性和實用性,約束滿足理論與方法還可用于求解其他類似問題。

約束滿足問題模型與數(shù)學(xué)規(guī)劃模型在原理和形式上較為相似,但是能夠描述具有非線性特征的約束,而且能夠用更自然的語言來描述問題中的各種變量和約束,也可以利用一些成熟的約束規(guī)劃軟件(如ILOG Solver),但在問題規(guī)模較大時,缺乏有效的分支定界策略,求解算法的效率也很低,其上界計算比較困難,依賴于成熟的上界計算方法。

3.3 基于圖論的模型

自歐拉1736年發(fā)表第一篇有關(guān)圖論的論文以來,圖論獲得廣泛研究和應(yīng)用。在衛(wèi)星調(diào)度領(lǐng)域,Reddy[22]針對中繼衛(wèi)星資源調(diào)度問題提出根據(jù)任務(wù)的在前約束關(guān)系建立有向圖,通過尋找有向圖的最長路獲得問題的解。Reddy的研究對中繼衛(wèi)星調(diào)度問題進(jìn)行了很大的簡化,但只考慮了任務(wù)具有單時間窗口約束的情形,在實際調(diào)度應(yīng)用中還應(yīng)進(jìn)行擴(kuò)展。

圖論模型的優(yōu)點在于形式簡單,具有成熟的多項式時間求解算法,但是該模型難以描述存儲容量、能量限制、復(fù)合觀測任務(wù)等實際約束,一般只用于單星任務(wù)調(diào)度,具有較大的局限性,較多應(yīng)用于早期對簡化問題的研究中。

4 求解算法

4.1 完全搜索算法

衛(wèi)星資源調(diào)度問題是NP-hard問題(非多項式確定-難問題),由于其復(fù)雜性和多約束的特點而難于求解。完全搜索算法只能用于求解中繼目標(biāo)少、問題規(guī)模小的調(diào)度問題。Reddy[22]研究了任務(wù)具有單時間窗口約束的中繼衛(wèi)星單址鏈路調(diào)度問題,提出了問題求解的動態(tài)規(guī)劃算法,在對任務(wù)具有單時間窗口約束模型的求解中獲得了優(yōu)化結(jié)果。Rojanasoonthon[16-17]研究了任務(wù)具有兩個時間窗口約束的中繼衛(wèi)星多址鏈路調(diào)度問題,采用分支-定界算法對模型進(jìn)行了求解,在求解較少任務(wù)數(shù)據(jù)時獲得最優(yōu)解,但在求解多任務(wù)數(shù)據(jù)時很難獲得最優(yōu)結(jié)果。

完全搜索算法理論成熟,運(yùn)算速度快、精度高,應(yīng)用較早,但是對問題約束的處理能力較弱,在大規(guī)模問題中,很難在有限時間內(nèi)獲得最優(yōu)解。

4.2 啟發(fā)式算法

基于規(guī)則的啟發(fā)式算法,是現(xiàn)有衛(wèi)星資源調(diào)度系統(tǒng)中應(yīng)用較多的算法,最常見的是基于優(yōu)先級的規(guī)則,即優(yōu)先安排高優(yōu)先級的任務(wù),并選擇較早的時間窗口。Marco Adinolfi[23]對歐洲航天局的中繼衛(wèi)星系統(tǒng)的調(diào)度問題進(jìn)行了研究,研究中考慮了任務(wù)優(yōu)先級、活動的時效性與持續(xù)時間,采用基于回溯的啟發(fā)式算法對問題進(jìn)行求解,該算法比較簡單但任務(wù)調(diào)整的范圍較小,算法性能有待進(jìn)一步提高。Rojanasoonthon[24]采用并行機(jī)調(diào)度理論對中繼衛(wèi)星調(diào)度問題進(jìn)行研究,建立了混合整數(shù)規(guī)劃模型,考慮了任務(wù)的優(yōu)先級,調(diào)度目標(biāo)是在規(guī)劃的時間段內(nèi),分配中繼衛(wèi)星的天線資源完成用戶所提交的任務(wù)需求數(shù)最多。采用貪婪隨機(jī)自適應(yīng)搜索算法對模型進(jìn)行求解,并與采用分支-定界算法的求解結(jié)果做了比較分析,結(jié)果表明,貪婪隨機(jī)自適應(yīng)搜索算法在求解多任務(wù)時獲得更優(yōu)結(jié)果。

4.3 智能優(yōu)化算法

近年來,蟻群算法(Ant Colony Optimization,ACO)、遺傳算法(Genetic Algorithm,GA)、模擬退火(Simulated Annealing,SA)等智能優(yōu)化算法在求解組合優(yōu)化問題方面顯示了較強(qiáng)的能力,在衛(wèi)星資源調(diào)度中也得到了廣泛的應(yīng)用。

(1)蟻群算法

蟻群優(yōu)化算法最初應(yīng)用于旅行商問題(Traveling Salesman Problem,TSP)[25]。在單機(jī)(single-machine)調(diào)度、并行機(jī)(parallel-machine)調(diào)度、車間(job-shop)調(diào)度等眾多經(jīng)典調(diào)度問題中也獲得成功應(yīng)用[26-29]。在衛(wèi)星調(diào)度領(lǐng)域,顧中舜[30]利用蟻群算法求解中繼衛(wèi)星初始調(diào)度模型,并與基于遺傳算法和模擬退火算法的計算結(jié)果進(jìn)行了比較,結(jié)果表明,蟻群算法在求解時間和求解精度上都明顯優(yōu)于另外兩種算法。李泓興[31]等提出了一種加入精英策略的改進(jìn)蟻群算法對成像衛(wèi)星進(jìn)行調(diào)度,實例計算表明,該方法能夠獲得更高質(zhì)量的求解結(jié)果。

(2)遺傳算法。

遺傳算法是模擬自然界生物進(jìn)化的一種隨機(jī)、并行和自適應(yīng)搜索算法。適用于傳統(tǒng)搜索算法難以解決的復(fù)雜和非線性優(yōu)化問題,目前已被廣泛應(yīng)用于組合優(yōu)化、人工智能等領(lǐng)域并取得了良好的成果。方炎申[19]等采用基于有效的基因路徑的遺傳算法來實現(xiàn)中繼衛(wèi)星單址鏈路任務(wù)調(diào)度,分析了調(diào)度問題中時間窗口的特性,對基本遺傳算法進(jìn)行改進(jìn),引入有效基因概念,應(yīng)用結(jié)果表明,采用基于有效基因路徑表示的遺傳算法求解是合理的。

(3)模擬退火算法

模擬退火算法由Kirkpatrick等人于1982年提出。顧中舜[30]比較了利用蟻群算法、遺傳算法和模擬退火算法求解中繼衛(wèi)星初始調(diào)度模型計算結(jié)果,最后得出由于模擬退火算法有限度地接受劣解,可以跳出局部最優(yōu)解,有效解決大規(guī)模問題,但有著過大計算量和過多控制參數(shù)的缺點,因此模擬退火法常與其他算法相結(jié)合來得出性能好、收斂速度快的混合優(yōu)化算法。

4.4 算法的比較

許多研究證明[16-17,22],當(dāng)問題規(guī)模較小時,采用完全搜索算法可以在較短的時間內(nèi)得到一個最優(yōu)解,但當(dāng)問題規(guī)模較大時,采用完全搜索算法不可行,而非完全搜索算法的啟發(fā)式算法和智能優(yōu)化算法可以在合理時間內(nèi)得到問題的滿意解。

由于各研究都是針對特定的衛(wèi)星和任務(wù)展開的,各個衛(wèi)星的性能不一,考慮的約束條件差異較大,任務(wù)特點不同,因而各算法的性能不好比較,多針對特定的衛(wèi)星應(yīng)用,采用不同算法進(jìn)行測試比較。

Wolfe[32]比較了貪婪算法、具有前看功能的貪婪算法以及遺傳算法等3種不同算法,得到結(jié)論在遺傳算法中,由于定義了一些交叉、變異算子,允許撤銷已經(jīng)安排的觀測需求,從而得到一個較好的調(diào)度方案。Nicholas[33]等人設(shè)計并比較了8種啟發(fā)式算法,這些啟發(fā)式算法得到了接近于上界的解。顧中舜[29]比較了利用蟻群算法、遺傳算法和模擬退火算法求解中繼衛(wèi)星初始調(diào)度模型計算結(jié)果,比較結(jié)果認(rèn)為,無論是求解時間還是求解精度,蟻群算法都明顯優(yōu)于遺傳算法和模擬退火方法。

隨著衛(wèi)星數(shù)量增多、任務(wù)需求增大,完全搜索算法將不再適用。啟發(fā)式算法和進(jìn)化算法具有快速、高效、高可靠的特點,在解決中繼衛(wèi)星資源調(diào)度的多目標(biāo)優(yōu)化方面存在優(yōu)勢,應(yīng)由決策者按照一定的經(jīng)驗和偏好進(jìn)行選擇。

5 發(fā)展與展望

目前,各國的跟蹤與數(shù)據(jù)中繼衛(wèi)星系統(tǒng)都是基于微波鏈路,如美國的跟蹤與數(shù)據(jù)中繼系統(tǒng)(TDRSS)、歐洲的數(shù)據(jù)中繼衛(wèi)星(DRS)等。然而,微波頻率資源有限,難以滿足高速數(shù)據(jù)傳輸速率的要求,并且由于微波鏈路抗干擾性能較差,難以保證保密信息的可靠傳輸?；诩す怄溌返臄?shù)據(jù)中繼衛(wèi)星系統(tǒng)具有高速率、強(qiáng)保密性和抗電磁干擾等優(yōu)點,是針對現(xiàn)有微波鏈路的不足所提出的有效的解決方案。以歐洲為代表的發(fā)達(dá)國家都相繼開展了激光鏈路數(shù)據(jù)中繼衛(wèi)星關(guān)鍵技術(shù)研究和星上演示驗證,提出了數(shù)據(jù)中繼衛(wèi)星激光鏈路組網(wǎng)的概念[34],并啟動了相應(yīng)的工程驗證計劃。隨著2008年5月我國首顆數(shù)據(jù)中繼衛(wèi)星“天鏈一號01星”成功定點和2011年7月“天鏈一號02星”的成功發(fā)射,解決了我國在中繼衛(wèi)星這一嶄新領(lǐng)域的“有無”問題,兩顆中繼衛(wèi)星計劃組網(wǎng)運(yùn)行,初步構(gòu)建我國的數(shù)據(jù)中繼網(wǎng)。今后我國數(shù)據(jù)中繼衛(wèi)星系統(tǒng)的建設(shè)發(fā)展中,數(shù)據(jù)中繼衛(wèi)星的激光鏈路組網(wǎng)是具有前瞻性和戰(zhàn)略性的重要技術(shù)研究內(nèi)容。

從外國的發(fā)展經(jīng)驗和我國數(shù)據(jù)中繼衛(wèi)星發(fā)展目標(biāo)來看,微波/光混合鏈路的中繼衛(wèi)星系統(tǒng)是滿足空間海量信息傳輸?shù)年P(guān)鍵技術(shù)領(lǐng)域。基于微波/光混合鏈路的中繼衛(wèi)星資源調(diào)度是未來研究的熱點,存在很多問題有待于進(jìn)一步深入研究。

(1)微波/光混合鏈路的調(diào)度理論

微波/光混合鏈路數(shù)據(jù)中繼衛(wèi)星組網(wǎng)實現(xiàn)以后,數(shù)顆數(shù)據(jù)中繼衛(wèi)星可基于激光鏈路互聯(lián),構(gòu)建高速、安全的數(shù)據(jù)中繼骨干網(wǎng),中繼衛(wèi)星可為用戶星提供多條激光和微波鏈路,再通過激光和微波接入到地面,為不同軌道類型、不同功能的用戶星提供大容量、無縫數(shù)據(jù)中繼服務(wù),其應(yīng)用場景如圖3所示。

圖3 微波/光混合鏈路中繼網(wǎng)Fig.3 Data and relay networks of microwave/laser links

目前的資源調(diào)度問題研究都只針對微波鏈路,而針對激光鏈路的中繼衛(wèi)星資源調(diào)度問題與已有的微波鏈路調(diào)度問題在具體調(diào)度方法上存在差異。如2.3節(jié)所述,數(shù)據(jù)中繼只有在用戶星與中繼衛(wèi)星之間具有可見時間窗口時進(jìn)行。中繼星與用戶星通信鏈路建立過程分為準(zhǔn)備、捕獲、跟蹤、釋放4個階段,而激光鏈路與微波鏈路在鏈路建立時存在很大差異。由于激光束發(fā)射角窄,激光鏈路對準(zhǔn)精度要求高,相對于微波鏈路捕獲難度大,在可見時間窗口一定的情況下,其數(shù)據(jù)星與中繼星的數(shù)據(jù)傳輸窗口窄,使得資源調(diào)度問題變得復(fù)雜。在微波/光混合鏈路的中繼衛(wèi)星系統(tǒng)中,必須考慮星間光鏈路與微波鏈路在資源調(diào)度中的區(qū)別,進(jìn)一步分析現(xiàn)有的星間微波鏈路的調(diào)度現(xiàn)狀,改進(jìn)調(diào)度算法,最終提出微波/光混合鏈路的調(diào)度算法。

(2)基于多終端-多節(jié)點的調(diào)度理論研究

在具有星間鏈路的微波/光中繼衛(wèi)星網(wǎng)絡(luò)中,中繼星通過激光鏈路構(gòu)成數(shù)據(jù)中繼骨干網(wǎng),同時為用戶星提供多條激光和微波鏈路,由于中繼衛(wèi)星的數(shù)量有限,且受載荷的限制,一顆中繼星只能為用戶星提供一條光學(xué)鏈路,因此必然會出現(xiàn)一顆中繼星收到多顆用戶星中繼服務(wù)請求的極端情況,同時,還有其他微波鏈路用戶的接入,有時用戶星需先后連接不同的中繼星才能保證數(shù)據(jù)中繼的持續(xù),這就使得中繼網(wǎng)具有多終端-多節(jié)點的特點。因此,在中繼衛(wèi)星具有多終端、多節(jié)點的情況下,如何生成一個滿意的中繼衛(wèi)星調(diào)度方案,合理分配中繼衛(wèi)星系統(tǒng)資源來完成更多的跟蹤、測控與數(shù)據(jù)中繼任務(wù),對充分發(fā)揮中繼衛(wèi)星系統(tǒng)的能力至關(guān)重要。在這種情況下,必須分析中繼星中多終端-多節(jié)點的資源調(diào)度方式的特點,建立基于多終端-多節(jié)點的資源調(diào)度模型,并提出有效的資源調(diào)度算法。

(3)資源故障調(diào)度任務(wù)模型研究

激光鏈路中繼衛(wèi)星容易受到各種因素影響(如衛(wèi)星平臺抖動使通信中斷等),造成中繼星資源故障,目前針對中繼衛(wèi)星動態(tài)調(diào)度問題的研究集中在微波鏈路資源故障、任務(wù)時間改變、新任務(wù)增加等問題,針對激光鏈路中繼星資源調(diào)度中突發(fā)故障的特點,分析在突發(fā)故障的資源調(diào)度目標(biāo),建立起基于突發(fā)故障的資源調(diào)度模型并提出資源調(diào)度算法求解,是未來中繼衛(wèi)星資源調(diào)度研究方向之一。

[1] Teles J,Samii M V,Doll C E.Overview of TDRSS[J].Advances in Space Research,1995,16(12):67-76.

[2] 王振河,孫寶升.航天器TDRSS中繼終端入網(wǎng)驗證初探[J].飛行器測控學(xué)報,2011,30(4):14-17.WANG Zhen-he,SUN Bao-sheng.Research on Access Verification foe Spacecraft TDRSS Customer Terminal[J].Journal of Spacecraft TT&C Technology,2011,30(4):14-17.(in Chinese)

[3] Shaw H C,Rackley M W.TDRSS Space Ground Link Terminal User Services Subsystem Replacement and Upgrades[C]//Proceeding of SpaceOps.Huntsville,Alabama:AIAA,2010:1-13.

[4] 王家勝.數(shù)據(jù)中繼衛(wèi)星系統(tǒng)的研制與分析[J].航天器工程,2008,17(5):7-12.WANG Jia-sheng.Development and Analysis of Data Relay Satellite System[J].Spacecraft Engineering,2008,17(5):7-12.(in Chinese)

[5] 王家勝.我國數(shù)據(jù)中繼衛(wèi)星系統(tǒng)發(fā)展建議[J].航天器工程,2011,20(2):1-8.WANG Jia-sheng.Proposal for Developing China s Data Relay Satellite System[J].Spacecraft Engineering,2011,20(2):1-8.(in Chinese)

[6] 史西斌,李本津,王琨,等.美國三代跟蹤與數(shù)據(jù)中繼衛(wèi)星系統(tǒng)的發(fā)展[J].飛行器測控學(xué)報,2011,30(2):1-8.SHI Xi-bin,LI Ben-jin,WANG Kun,et al.Development of Three Generationsof Tracking and Data Relay Satellite System[J].Journal of Spacecraft TT&C Technology,2011,30(2):1-8.(in Chinese)

[7] 史西斌,高堅,寇保華.歐洲數(shù)據(jù)中繼衛(wèi)星系統(tǒng)的未來發(fā)展[J].中國航天,2009(10):29-33.SHI Xi-bin,GAO Jian,KOU Bao-hua.Future Development of EDRS[J].Aerospace China,2009(10):29-33.(in Chinese)

[8] Toyoshima M,Sasaki T,Takenaka H,et al.Research and development of free-space laser communications and quantum key distribution technologies at NICT[C]//Proceedings of 2011 International Conference on Space Optical Systems and Application.Santa Monica,CA:IEEE,2011:1-7.

[9] Cesarone R J,Abraham D S,Shambayati S.Deep-Space Optical Communications[C]//Proceedings of 2011 International Conference on Space Optical Systems and Application.Santa Monica,CA:IEEE,2011:410-423.

[10] 趙尚弘,吳繼禮,李勇軍,等.衛(wèi)星激光通信現(xiàn)狀與發(fā)展趨勢[J].激光與光電子學(xué)進(jìn)展,2011,48(9):7-21.ZHAO Shang-hong,WU Ji-li,LI Yong-jun,et al.Present Status and Developing Trends of Satellite Laser Communication[J].Laser&Optoelectronics Progress,2011,48(9):7-21.(in Chinese)

[11] Pinedo M.Scheduling:Theory,Algorithms,and Systems[M].Englewood Cliffs:Prentice-Hall,1995.

[12] Gabrel V,Vanderpooten D.Enumeration and Interactive Selection of Efficient Paths in a Multiple Criteria Graph for Scheduling anEarth Observing Satellite[J].European Journal of Operational Research,2002,139(3):533-542.

[13] Bensana E,Verfaillie G,Lemaitre M.Earth Observing Satellite Management[J].Constraints,1999,4(3):293-299.

[14] Arbabi M.Range Scheduling Automation[J].IBM Technical Directions,1984,10(3):57-62.

[15] Gooley T D.Automating the Satellite Range Scheduling Process[D].X′an:Air Force Institute of Technology,1993.

[16] Rojanasoonthon S,Bard J F,Reddy S D.Algorithms for parallel machine scheduling:a case study of the Tracking and Data Relay Satellite System[J].Journal of the Operational Research Society,2003,54(8):806-821.

[17] Rojanasoonthon S.Parallel machine scheduling with time windows[D].Austin,TX:University of Texas at Austin,2003:265-276.

[18] 方炎申,陳英武,顧中舜.中繼衛(wèi)星調(diào)度問題的CSP模型[J].國防科技大學(xué)學(xué)報,2005,27(2):6-10.FANG Yan-shen,CHEN Ying-wu,GU Zhong-shun.CSP Model of the Relay Satellite Scheduling[J].Journal of National University of Defense Technology,2005,27(2):6-10.(in Chinese)

[19] 陳英武,方炎申.中繼衛(wèi)星單址鏈路調(diào)度模型與算法研究[J].中國空間科學(xué)技術(shù),2007,27(2):52-58.CHEN Ying-wu,FANG Yan-shen,GU Zhong-shun.Algorithms for the Single Access Link Scheduling Model of T racking and Data Relay Satellite System[J].Chinese Space Science and T echnology,2007,27(2):52-58.(in Chinese)

[20] 方炎申,陳英武,王軍民.中繼衛(wèi)星多址鏈路調(diào)度問題的約束規(guī)劃模型及算法研究[J].航天返回與遙感,2006,27(4):62-67.FANG Yan-shen,CHEN Ying-wu,WANG Jun-min.Constraint Programming Model and Algorithms for Multiple Access Links Scheduling of Tracking and Data Relay Satellite System(TDRSS)[J].Spacecraft Recovery&Remote Sensing,2006,27(4):62-67.(in Chinese)

[21] 張彥,孫占軍,李劍.中繼衛(wèi)星動態(tài)調(diào)度問題研究[J].系統(tǒng)仿真學(xué)報,2011,23(7):1468-1468.ZHANG Yan,SUN Zhan-jun,LI Jian.Study of TDRS Dynamic Scheduling Problem[J].Journal of System Simulation,2011,23(7):1468-1468.(in Chinese)

[22] R eddy S D,Brown W L.Single processor scheduling with job priorities and arbitrary ready and due times[M].Beltsville,Maryland:Computer Sciences Corporation,1986.

[23] Adinolfi M,CestalA.Heuristic scheduling of the DRS communication system[J].Engineering Applications of Artificial Intelligence,1995,8(2):147-156.

[24] Rojanasoonthon S,Bard J.A GRASP for parallel machine scheduling with time windows[J].Journal on Computing,2005,17(1):32-51.

[25] Yang Jinhui,Shi Xiaohu,Marchese M,et al.AnAnt Colony Optimization Method for Generalized TSP Problem[J].Progress in Natural Science,2008,18(11):1417-1422.

[26] Cheng T C E,Ng C T,Yuan J J.Multi-Agent Scheduling on a Single Machine with Max-form Criteria[J].European Journal of Operational Research,2008,188(2):603-609.

[27] Cheng T C E,Lazarev A A,Gafarov E R.A Hybrid Algorithm for the Single-Machine Total Tardiness Problem[J].Computers&Operations Research,2007,36(2):308-315.

[28] Huang Kuo-Ling,Liao Ching-Jong.Ant Colony Optimization Combined with Taboo Search for the Job Shop Scheduling Problem[J].Computers&Operations Research,2008,35(4):1030-1046.

[29] Heinonen J,Pettersson F.Hybrid Ant Colony Optimization and Visibility Studies Applied to a Job-shop Scheduling Problem[J].Applied Mathematics and Computation,2007,187(2):989-998.

[30] 顧中舜.中繼衛(wèi)星動態(tài)調(diào)度問題建模及優(yōu)化技術(shù)研究[D].長沙:國防科學(xué)技術(shù)大學(xué),2008.GU Zhong-shun.Research on the Relay Satellite Dynamic Scheduling Problem Modeling and Optimizational Technology[D].Changsha:National University of Defense Technology,2008.(in Chinese)

[31] 李泓興,豆亞杰,鄧宏鐘,等.基于改進(jìn)蟻群算法的成像衛(wèi)星調(diào)度方法[J].計算機(jī)應(yīng)用,2011,31(6):1656-1659.LI Hong-xing,DOU Ya-jie,DENG Hong-zhong,et al.Scheduling of imaging satellites based on improved ant colony algorithm[J].Journal of Computer Apploication,2011,31(6):1656-1659.(in Chinese)

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

[33] Nicholas G,Michael J.Maximizing the Value of a Space Mission[J].European Journal of Operational Research,1994,78:224-241.

[34] Wilfert O,Henniger H,Kolk Z.Optical communication in free space[C]//Proceedings of the 16th Polish-Slovak-Czech Optical Conference on Wave and Quantum Aspects of Contemporary Optics.Polanica Zdroj,Poland:SPIE,2008:714102-1-12.