衛星數據傳輸全流程調度及優化算法

向云武, 章文毅, 田妙苗

(1. 中國科學院遙感與數字地球研究所衛星地面系統運行管理部, 北京 100089;2. 中國科學院大學資源與環境學院, 北京 101400)

0 引 言

隨著遙感應用的日益普及,遙感衛星的需求也不斷增長。大量不同類型的在軌衛星獲取了豐富的對地觀測信息,這些信息通過星地傳輸鏈路傳輸到地面站,這個環節稱為衛星到地面站的星地傳輸。地面站接收這些信息后,將其通過地面光纖鏈路傳輸到數據中心,這個環節稱為地面站到數據中心的地面傳輸。星地傳輸過程和地面傳輸過程合稱衛星數據傳輸過程,如圖1所示。衛星數據傳輸需要滿足兩個基本的條件:①在星地傳輸環節中,衛星天線與地面站天線幾何可見,且地面站天線處于空閑狀態;②在地面傳輸環節中,地面光纖傳輸鏈路不超負荷。此時就要做出合理的規劃,以便在盡可能短的時間內獲得全部的衛星數據。當衛星數量以及星載任務較多時,則更凸顯調度的必要性。

衛星數據傳輸問題是指如何為衛星數據合理分配地面接收資源和傳輸鏈路資源,包括星地傳輸環節的數據傳輸問題和地面傳輸環節的數據傳輸問題。星地傳輸環節的數據傳輸實現了數據傳輸任務的數傳資源及時間窗口分配,是典型的具有NP-Hard特征的組合優化問題[1-2];地面傳輸環節的數據傳輸實現了地面站傳輸鏈路資源分配,是典型的流水線排序問題。

圖1 衛星數據傳輸過程Fig.1 Process of satellite data transmission

針對星地傳輸環節的數據傳輸問題,已有不少學者做了各種模型和算法的研究。文獻[3]將基于信息素評價的蟻群算法運用到衛星數傳調度問題上;文獻[4]提出了混合遺傳算法在衛星數傳調度問題上的應用;文獻[5-6]提出了進化算法中的遺傳算法在多星數據下傳資源調度中的應用和一種基于遺傳算法的數據傳輸沖突窗口模型;文獻[7-9]提出了禁忌搜索算法和基于struggle策略的遺傳算法的多星數傳調度方法;文獻[10]提出了K-shortest path遺傳算法解決數傳調度;文獻[11]提出了基于沖突消解的地面站資源調度方法;文獻[12]提出了基于吱呀輪優化的多衛星數傳調度問題求解方法;文獻[13]在解決衛星數傳調度時,提出了基于地面站編碼的遺傳算法以提高算法的尋優能力。這些成果只考慮了星地傳輸環節調度而沒有考慮地面傳輸環節的調度。目前星地傳輸和地面傳輸的全局調度尚未見報道。

本文同時考慮了星地傳輸環節和地面傳輸環節,以在最短時間內獲取所有衛星數據為調度目標建立衛星數據傳輸模型,并采用基于動態規劃和雙閾值控制遺傳算法的混合算法求解。這里星地傳輸環節的數傳調度區別于傳統的數傳調度[3-13],不再以在一段時間內接收最多任務為調度目標,而是在考慮到星地傳輸和地面傳輸兩個環節的約束的基礎上,以在最短時間內將所有衛星數據下達到地面站為目標。即在已知各任務下達到各地面站的時刻、任務數據本身大小以及地面光纖傳輸鏈路帶寬的前提下,在最短時間內將所有衛星數據傳輸到數據中心。這在充分高效利用衛星以及地面站資源(包括接收資源和傳輸鏈路資源)方面意義重大:例如,當面對自然災害需要作出應急措施時,在最短時間內獲取相關數據更是顯得尤為重要。

1 衛星數據傳輸問題描述

遙感衛星數據由遙感衛星對目標區域進行拍攝得到,通過地面站和數據鏈路傳輸到數據中心。其過程如圖1所示,主要包括兩個環節:第一,衛星到地面站的星地傳輸環節,此環節為各衛星數據分配目標地面站;第二,地面站到數據中心的地面傳輸環節,此環節為下傳完成的數據分配地面光纖傳輸鏈路。地面站的位置一般情況下是固定不變的,而衛星受其軌道周期和回歸周期的影響,使其在一段時間內與各地面站只有在特定的幾個時間窗口內相互可見。各地面站的接收資源(天線)和傳輸資源(傳輸鏈路)不同,需要統籌規劃星地傳輸和地面傳輸兩個環節。

圖2 問題描述示意圖Fig.2 Schematic diagram of problem description

當面對多星多站衛星數據傳輸問題時,還會面臨更多更復雜的問題。比如,當多星同時對某地面站幾何可見時,由于該地面站天線數量有限會導致對天線資源的爭用從而產生沖突;當某衛星在單位時間窗口內有多個任務需要下傳時,將面對具體選擇哪幾個任務下傳以充分利用該時間窗口的問題;當有任務陸續下達到某地面站時,若該地面站的地面光纖數量不止一條,將面對如何為這些任務選擇具體的光纖傳輸鏈路以在最短的時間內將所有任務傳輸到數據中心的問題。針對這些問題,本文分別建立了衛星數據接收沖突時段約束模型、單位連續時間窗口內下傳任務選擇模型以及地面傳輸模型,并分別采用動態規劃和貪心算法求解。

2 衛星數據傳輸模型

如圖1所示,每個地面站的每部天線都可以接收多顆衛星的數據,存在因為地面站接收天線數量有限而產生爭用進而導致沖突的可能;假設單位連續時間窗口內,從衛星數據任務集里選擇需要下傳的數據任務時可以任意選擇;在地面傳輸環節,若某地面站的地面光纖有多條,需要綜合考慮所有下達到該站的任務的大小、下達時間以及各條光纖的帶寬為各任務選擇具體的光纖傳輸鏈路,以便在最短時間內將所有任務傳輸到數據中心。本文將提出沖突時段約束模型解決天線爭用問題,同時還提出背包模型用于選擇需要下傳的任務,最后在地面傳輸環節提出了以經典流水線作業排序問題為背景的地面傳輸模型。

2.1 符號定義

符號定義如表1所示。

表1 符號定義

2.2 目標函數

本文以在最短時間內獲取所有衛星數據為調度目標,即所有任務回傳的總時間最短

MinFTime

(1)

式中,FTime是指所有任務會傳到總部所需時間。

FTime=max{Ft1,Ft2,…,FtN}

(2)

式中,N為任務總數量。

Fti=arriveTi-startT

(3)

式中,startT為規劃開始時刻;arriveTi為第i個任務傳輸到數據中心的時刻。

2.3 沖突時段約束模型

衛星數據接收需同時考慮到如下約束:

(1) 一部天線在同一時刻只能接收一個任務;

(2) 一個任務只能通過一部天線接收;

(3) 一部天線先后接收來自兩顆衛星的任務時需要一段切換時間,在這里用Shift1表示;

(4) 一顆衛星先后通過兩個地面站的天線下傳任務時需要一段切換時間,在這里用Shift2表示。

當衛星過境地面站時,由于地面接收資源有限,可能會產生資源爭用而出現沖突的情況,這時候就需要消解沖突,為各顆衛星合理分配地面接收資源以及相應的接收時段。

在這里以衛星過境地面站事件作為考慮對象,按照先到先得原則為各衛星分配天線,根據衛星進站時間先后排序,依次為各衛星分配地面站的天線,直到所有衛星的星載任務完成下行,流程如圖3所示。

衛星i對地面站j的天線的可用開始時間為

(4)

(5)

(6)

圖3 沖突消解流程圖Fig.3 Flow chart of conflict resolution

同時更新衛星i的星載任務集

(7)

2.4 單位時間窗口內下傳任務選擇模型

本文采用背包模型來選擇所要下傳的任務,使得單位時間窗口內下傳的任務數據量最大,并采用動態規劃算法求解模型。設衛星此次過境時長為T,星上有u個任務需要下傳,每個任務下傳完成需要的時間為

Dur={Dur1,Dur2,…,Duru}

(8)

則模型可描述為

(9)

s.t.XiDuri≤T

(10)

Xi=0或1

(11)

采用動態規劃[14]向前遞推算法,設gi(M)是Knap(i+1,u,M)的最優解,則有

g0(T)=Knap(1,u,T)

(12)

由于X1=0或1,可得

(13)

對于某個Xi,Xi=0或1,則有

(14)

初始值為

(15)

2.5 地面傳輸模型

在地面傳輸環節,以最短時間內將所有數據傳輸到數據中心為目標建立衛星數據地面傳輸模型,并將其抽象為經典流水線作業排序問題。已知各地面站的地面光纖數量和帶寬以及各任務下達地面站的時間和任務數據大小。同時,一個任務的數據只能通過一條鏈路傳輸,一條鏈路在同一時刻只能傳輸一個任務的數據。在某地面站下傳的所有任務下達的時刻表示為

T={t1,t2,…,tr}

(16)

式中,ti

W={w1,w2,…,wr}

(17)

該地面站的地面光纖帶寬表示為

Band={b1,b2,…,bs}

(18)

式中,s為該地面站地面光纖數量。

當有新任務數據下達到地面站時,傳輸鏈路有兩種情形:①沒有數據在等待傳輸;②有數據在等待傳輸。如果面對的是第一種情形,直接計算該任務數據分別通過s條傳輸鏈路傳輸時所有任務傳輸完成所需時間,選擇所需時間最短的一條鏈路傳輸該任務;如果面對的是第二種情形,就采用貪心策略,將該任務和所有等待傳輸的任務作為一個任務集合,對該集合運用多路背包模型求解得到各任務的最佳傳輸鏈路。

3 基于混合遺傳算法的衛星數據傳輸算法

本文通過混合遺傳算法求解,外層算法框架為雙閾值控制的遺傳算法,適應度函數值由求解內層模型所得。通過圖4可以看到,在外層遺傳算法迭代過程中,通過求解衛星數據傳輸模型(包括衛星數據接收沖突時段約束模型、單位連續時間窗口內下傳任務選擇模型以及地面傳輸模型)得到適應度函數值。

3.1 雙閾值控制的遺傳算法

算法的外層采用雙閾值控制的遺傳算法。遺傳算法,也稱基因算法,效法基于自然選擇的生物進化,是一種模仿生物進化過程的隨機迭代進化的搜索算法。

雙閾值控制的遺傳算法[15]是對簡單遺傳算法的改進,雙閾值指父輩相似度閾值和收斂度閾值。通過這兩個閾值能夠靈活控制變異的時間和概率,進而提高種群多樣性,防止迭代陷入局部最優。

圖4 混合算法流程圖Fig.4 Flow chart of hybrid algorithm

3.2 算法設計

3.2.1 算法思想及流程

雙閾值控制的遺傳算法流程圖如圖5所示。

圖5 遺傳算法流程圖Fig.5 Flow chart of genetic algorithm

3.2.2 編碼

本文采用自然數編碼,這樣能直觀地反映任務的調度結果。對每個任務進行編碼,碼元的取值范圍為[1,m],表示該任務被分配到相應的地面站下傳。

3.2.3 適應度函數

由于每代各個個體目標函數的相對差較小,從而使得各個個體的選擇概率差別很小,進而導致選優功能被弱化,因此需要對目標函數進行標定,本文采用冪律標定和線性標定相結合的方法,同時,由于本文面對的是最小值問題,因此不能將目標函數作為適應值函數,需要先求倒數

f=MinFTime

(19)

式中,f為目標函數。

(20)

3.2.4 選擇

本文采用精英選擇和蒙特卡羅選擇相結合的方法。精英選擇能保證每一代的最優解可以直接遺傳到下一代而不被破壞,蒙特卡羅選擇能夠保證種群的多樣性,以避免進化陷入局部最優解。

3.2.5 交叉

為了提高產生優良解的速度,本文采用多父輩POX交叉。多父輩相較于兩父輩而言,綜合了更多父代個體的信息,可以在產生子代個體時獲得更好的解空間搜索效率和尋優質量。具體步驟:

步驟1首先選擇父代個體Parent1和Parent2,并從優良種群中選擇父代個體Parent3;

步驟2隨機選擇3個基因位,將父代個體分成4個部分;

步驟3按圖6所示模式進行交叉,得到兩個子代個體。

圖6 交叉示意圖Fig.6 Sketch map of hybridization

3.2.6 變異

變異的時間和概率對變異操作的效果有很大影響。本文通過父輩相似度閾值和收斂度閾值來分別控制變異時間和變異概率,既可以保證優良的父代個體在進化過程中不被破壞,又可以提高算法在進化后期的收斂速度。同時,本文選擇多點變異,隨機選擇3個基因位,然后隨機生成3個與相應基因位數值不相等隨機數分別代替這些數值。

4 案例結果及分析

案例在Intel(R) Core(TM) i5-650 3.2GHz CPU、8GB 三星DDR3 SDRAM 1333MHZ 內存、500GB(7200 RPM) 硬盤、Win7操作系統的計算機上,采用Microsoft Visual Studio 2013C++編程完成。

為了驗證本文模型及算法的有效性,采用星地傳輸和地面傳輸分步優化的結果作為對比。共有6個地面站,20顆衛星,每顆衛星下行碼速率為雙通道900 Mbps。表2為地面站信息,包括經緯度、高程、天線數量和傳輸鏈路光纖帶寬。其中,地面站2和3各有兩條傳輸鏈路,帶寬分別為498 Mbps和124 Mbps。

表2 地面站信息

算法參數設置:種群大小NP=200,最大進化代數NG=150,交叉概率Pc=0.9,初始變異概率Pm=0.05。

通過成像軟件生成不同數量的數傳任務,共10組。針對這10組調度任務,分別運行10次,取其平均值作為結果,如表3所示。

表3 分步優化和全局優化求解結果對比

表3中,“分步優化”是指傳統算法兩個環節分開優化,即先優化星地傳輸環節,然后優化地面傳輸環節;“星地傳輸時間”指第一環節所需時間,“總時間”指兩個環節總共所需時間;“全局優化時間”即同時考慮兩個環節約束的全流程優化結果;“時間縮短百分比”為“全局優化時間”與“分步優化總時間”的相對差,即

表3中的結果展示如圖7所示。從圖7中可以看出,對不同數量的調度任務,相較于傳統分步優化,本文全局優化可以更高效傳輸所有衛星數據。從案例1～4,時間縮短百分比逐次降低,是因為這幾組案例的任務規模都較小,使得分布優化總時間也較小,因此縮短的時間和分步優化總時間的比值會偏大且呈現逐次降低的趨勢。從案例4～10,時間縮短百分比逐漸增加,是因為地面接收站的接收能力和傳輸能力保持不變,而任務數卻不斷增加,使得全局優化的空間也隨之增加,因此,時間縮短百分比才會呈現逐次上升的趨勢。

圖7 結果對比Fig.7 Result comparison

圖8是案例6(312個調度任務)的收斂曲線?？梢钥闯?在進化到第25代時已經得到較好的解。說明算法具有較好的收斂性能。

圖8 算法收斂曲線Fig.8 Algorithm convergence curve

5 結 論

衛星數據的傳輸問題研究對于高效利用衛星和地面站資源有重要意義。本文建立了考慮星地傳輸和地面傳輸兩個環節的衛星數據傳輸模型,包括沖突時段約束模型、單位連續時間窗口內下傳任務選擇模型和地面傳輸模型,并通過基于動態規劃和雙閾值控制遺傳算法的混合算法求解。與傳統算法將兩個環節分開優化相比,全局優化能明顯縮短傳輸所有衛星數據所需的最短時間;且隨著問題規模的增大,全局優化的優勢更加明顯。

參考文獻：

[1] BARBULESCU L, HOWE A E, WHITLEY L D, et al. How to schedule more in a multi-resource oversubscribed scheduling problem[C]∥Proc.of the 14th International Conference on Automated Planning & Scheduling,2004:227-234.

[2] BARBULESCU L, WATSON J P, WHITLEY L D, et al. Scheduling space-ground communications for the air force satellite control network[J]. Journal of Scheduling, 2004, 7(1): 7-34.

[3] 陳祥國,武小悅.基于信息素評價的衛星數傳調度蟻群算法[J].系統仿真學報, 2009, 21(20): 6418-6423.

CHEN X G, WU X Y. Ant colony algorithm of satellite data transmission scheduling based on pheromone evaluation[J]. Journal of System Simulation, 2009, 21(20): 6418-6423.

[4] 李云峰,武小悅.遺傳算法在衛星數傳調度問題中的應用[J].系統工程理論與實踐, 2008, 28(1): 124-131.

LI Y F, WU X Y. Application of genetic algorithm in satellite data transmission scheduling problem[J]. System Engineering-Theory and Practice, 2008, 28(1): 124-131.

[5] CHEN H, ZHONG Z N, WU L J, et al. Multi-satellite data downlink resource scheduling algorithm for incremental observation tasks based on evolutionary computation[C]∥Proc.of the 7th International Conference on Advanced Computational Intelligence,2015:27-29.

[6] CHEN H, ZHOU Y R, DU C, et al. A satellite cluster data transmission scheduling methodbased on genetic algorithm with rote learning operator[C]∥Proc.of the IEEE Congress on Evolutionary Computation, 2016: 5076-5083.

[7] XHAFA F, HERRERO X, BAROLLI A, et al. Evaluation of struggle strategy in genetic algorithms for ground stations sche-duling problem[J]. Journal of Computer and System Sciences, 2013, 79(7) : 1086-1100.

[8] XHAFA F, SUN J, BAROLLI A. Genetic algorithms for satellite scheduling problems[J]. Mobile Imformation Systems, 2012, 8(4): 351-377.

[9] XHAFA F, HERRERO X, BAROLLI A, et al. A tabu search algorithm for ground station scheduling problem[C]∥Proc.of the 28th IEEE International Conference on Advanced Information Networking and Applications, 2014: 1033-1040.

[10] LI J, LI J, CHEN H, et al. A data transmission scheduling algorrithm for rapid-response earth-observing operations[J]. Chinese Journal of Aeronautics, 2014, 27(2) : 349-364.

[11] 金光,武小悅,高衛斌.基于沖突的衛星地面站系統資源調度與能力分析[J].小型微型計算機系統. 2007,28(2):310-312.

JIN G, WU X Y, GAO W B. Conflict based resource scheduling and capability analys is of satellite-ground station system[J]. Journal of Chinese Computer Systems,2007,28(2):310-312.

[12] 經飛,王鈞,李軍,等.基于吱呀輪優化的多衛星數傳調度問題求解方法[J].宇航學報. 2011, 32 (4): 863-870.

JING F, WANG J, LI J, et al. A new scheduling method for multi-satellite data transmission based on squeaky-wheel optimization[J].Journal of Astronautics,2011,32(4): 863-870.

[13] LI Y Q, WANG R X, LIU Y, et al. Satellite range scheduling with the priority constraint: an improved genetic algorithm using a station ID encoding method[J]. Chinese Journal of Aeronautics, 2015, 28(3): 789-803.

[14] HOWARD R A. Dynamic programming[J]. Management Science, 1966,12(5):317-348.

[15] 黃明, 王佳, 梁旭. 雙閾值控制的遺傳算法求解作業車間調度問題[J]. 計算機集成制造系統, 2007, 13(2): 329-332.

HUANG M, WANG J, LIANG X. Genetic algorithm controlled by two thresholds for job shop scheduling problem[J].Computer Integrated Manufacturing System,2007,13(2):329-332.