北斗全球衛(wèi)星導(dǎo)航系統(tǒng)境外星數(shù)據(jù)快速回傳的路由優(yōu)化方法

,,,

1. 湖南大學(xué) 電氣與信息工程學(xué)院,長沙 410073 2. 國防科技大學(xué) 機電工程與自動化學(xué)院,長沙 410073 3. 中國科學(xué)院 上海天文臺,上海 200030

星間鏈路(Inter-Satellite Link)技術(shù)是全球衛(wèi)星導(dǎo)航系統(tǒng)的一項關(guān)鍵技術(shù)，利用星間鏈路提升衛(wèi)星導(dǎo)航系統(tǒng)性能和自主運行能力已成為全球衛(wèi)星導(dǎo)航系統(tǒng)的重要發(fā)展趨勢[1]。以GPS為代表的國外衛(wèi)星導(dǎo)航系統(tǒng)都在積極發(fā)展星間鏈路[2]。中國北斗衛(wèi)星導(dǎo)航系統(tǒng)在2015年發(fā)射的新一代導(dǎo)航衛(wèi)星上已經(jīng)具備星間鏈路功能，并成功進行了在軌試驗。北斗衛(wèi)星導(dǎo)航系統(tǒng)預(yù)計在2020年前后建成全球系統(tǒng)。由于全球布站不足，北斗衛(wèi)星導(dǎo)航系統(tǒng)屆時將通過星間鏈路解決境外星的數(shù)據(jù)傳輸和遙測遙控等問題。因此，如何利用星間鏈路提高數(shù)據(jù)傳輸效率是解決北斗全球衛(wèi)星導(dǎo)航系統(tǒng)運行控制的關(guān)鍵技術(shù)之一。

針對星間數(shù)傳規(guī)劃及其路由問題，國內(nèi)外專家學(xué)者進行了一定的研究。文獻[3]提出了一種基于地面站集中式的導(dǎo)航星座星間路由算法，其中的假設(shè)條件是星間鏈路資源豐富，每顆衛(wèi)星可以同一時刻與其他多顆衛(wèi)星建立星間鏈路。文獻[4]和文獻[5]應(yīng)用演化圖對導(dǎo)航星座動態(tài)拓撲進行建模分析，提出了以最短到達時間和最小跳數(shù)為優(yōu)化目標(biāo)的路由算法；文獻[6]應(yīng)用有向圖理論對指向性星間鏈路導(dǎo)航網(wǎng)絡(luò)的信息傳輸進行描述，并基于Dijkstra算法提出了最早到達路徑和最短路徑的路由方法；文獻[7]綜合利用鏈路調(diào)度信息和節(jié)點隊列信息實現(xiàn)鏈路調(diào)度按需更新，提出一種基于局部隊列的最早投遞路由算法。這些研究對于解決全星座的通信與測量問題具有參考價值。但專門針對境內(nèi)境外數(shù)據(jù)快速回傳問題的研究，目前還沒有相關(guān)文獻報道。

本文針對中國北斗導(dǎo)航星座全球布站受限難題，提出了一種基于遺傳算法的路由優(yōu)化方法，從最大回傳時延最小和平均回傳時延最小兩個方面對路由表進行了優(yōu)化；分析了導(dǎo)航星座星間鏈路在不同時間的數(shù)據(jù)傳輸?shù)穆酚蓡栴}，采用了基于虛擬拓撲的路由算法，將動態(tài)的衛(wèi)星網(wǎng)絡(luò)拓撲按一定的時間間隔劃分為靜態(tài)的網(wǎng)絡(luò)拓撲序列進行分析處理。試驗結(jié)果表明，該方法可以有效解決境外星數(shù)據(jù)的快速回傳問題。

1 問題描述

導(dǎo)航星座中境外星數(shù)據(jù)快速回傳問題的實質(zhì)是對數(shù)據(jù)傳輸路由表進行優(yōu)化處理，經(jīng)過優(yōu)化處理的路由表能夠滿足境外星數(shù)據(jù)快速回傳的要求。星間數(shù)據(jù)傳輸中，星間路由的傳輸原理如圖1所示。

圖1 星間路由Fig.1 Inter-satellite routing

在圖1中，衛(wèi)星被劃分為境內(nèi)星、境外星兩種屬性，其中，境外星上攜帶一定的數(shù)據(jù)D，星間的數(shù)據(jù)傳輸速度是R，時隙用K表示。以圖中境外星2為例，境外星2上的數(shù)據(jù)D在K=1時隙傳輸給境外星4，K=2時隙又傳輸給境內(nèi)星6，即境外星2上數(shù)據(jù)D的一條傳輸路徑是(2,4,6)。本文的目的就是找到優(yōu)化路由表，在任意時刻，根據(jù)優(yōu)化路由表，境外星數(shù)據(jù)傳輸回境內(nèi)星所用時延最小。

上述問題可用以下數(shù)學(xué)模型來描述：

(1)

式中：S為衛(wèi)星集合，共有N顆衛(wèi)星；Sat_JN為境內(nèi)星子集；Sat_JW為境外星子集；G為地面站集合；R為數(shù)據(jù)傳輸速率；M為傳輸任務(wù)，即境外星上攜帶的數(shù)據(jù)；W為可見性窗口，即導(dǎo)航星座中衛(wèi)星與地面站的可見時間段。

根據(jù)上述模型，總結(jié)如下約束條件：

1)建鏈衛(wèi)星對之間滿足可見性要求；

2)建鏈表必須是對稱的，衛(wèi)星不與自身建鏈；

3)同一個時隙中，一顆源衛(wèi)星只能與一顆目的衛(wèi)星建立鏈路。

優(yōu)化模型可用下列數(shù)學(xué)表達式描述：

(2)

式中：f0為路由表最大傳輸時延；K為時隙；Kend和Kstart為數(shù)據(jù)傳輸?shù)慕Y(jié)束時隙和開始時隙，k為時隙長度，(Kend-Kstart)×k為數(shù)據(jù)傳輸時延。f1是整體路由表的平均傳輸時延，其中：Nn是記錄整張路由表傳輸時延的矩陣。例如N(n)=i1表示目標(biāo)路由表中，傳輸時延為n×k的路徑共有i1條。

(3)

根據(jù)上述的優(yōu)化模型，可以確定優(yōu)化函數(shù)：

mina×f0+b×f1

(4)

式中：a，b為優(yōu)化權(quán)重。

綜上所述，導(dǎo)航星座中境外星數(shù)據(jù)快速回傳重點需要解決兩個問題：

1)確定一個合理的優(yōu)化路由表，按照該路由表建鏈傳輸數(shù)據(jù)時，境外星數(shù)據(jù)全部傳回境內(nèi)星的時延最??；

2)根據(jù)優(yōu)化所得路由表及星間數(shù)據(jù)傳輸速度，明確一種數(shù)據(jù)傳輸方案。

2 星間數(shù)傳模型

衛(wèi)星網(wǎng)絡(luò)中的路由可以分為兩個部分，星間鏈路網(wǎng)絡(luò)路由和邊界路由，邊界路由解決衛(wèi)星網(wǎng)絡(luò)與地面網(wǎng)絡(luò)之間的融合。一般情況下，若非特殊說明，衛(wèi)星網(wǎng)絡(luò)中的路由都是指星間鏈路網(wǎng)絡(luò)路由。本文研究的是星間鏈路網(wǎng)絡(luò)路由，包括同層衛(wèi)星網(wǎng)絡(luò)路由和層間衛(wèi)星網(wǎng)絡(luò)路由?；谔摂M拓撲路由算法，鏈路分配周期是T，每個分配周期劃分為多個時隙K。路由表是根據(jù)初始規(guī)劃的建鏈表和數(shù)據(jù)傳輸方向確定的。

2.1 星間鏈路模型

導(dǎo)航星座選用的是北斗導(dǎo)航星座。根據(jù)星地可見性關(guān)系將導(dǎo)航衛(wèi)星劃分為境內(nèi)星和境外星的組合。根據(jù)衛(wèi)星位置，考慮星間距離、天線角度、地球遮擋等約束條件，可以計算星座中衛(wèi)星之間的相互可見性關(guān)系矩陣V=vi,j,Kslot∈RN×N×Kslot。衛(wèi)星可見性矩陣V如圖2所示。

圖2 星間可見性關(guān)系Fig.2 Inter-satellite visibility relationship

在圖2中，每一層矩陣代表一個建鏈周期的衛(wèi)星間的可見關(guān)系，矩陣中元素為1時表示衛(wèi)星i與衛(wèi)星j在該時刻Kslot可見，元素為0則表示兩顆衛(wèi)星之間是不可見。圖2中的可見性矩陣生成過程如圖3所示。

圖3中，T為建鏈周期，每T/2的衛(wèi)星數(shù)據(jù)生成一組初始可見關(guān)系，3個T/2的初始可見關(guān)系生成一個建鏈周期T的可見性，相鄰兩個建鏈周期的可見性之間存在T/2的重疊時段，有重疊可見性時段的可見性關(guān)系生成的路由表，在兩個相鄰的路由表中，當(dāng)兩個相鄰路由表間切換或前一個路由表的A區(qū)域向后一個路由表的B區(qū)域延展時，可以無需考慮可見性的約束。這種利用重疊可見性的方法生成的路由表，可以有效解決路由表間銜接問題，使得相鄰路由表的切換、時隙拓展更加方便合理。

圖3 星間可見關(guān)系生成過程Fig.3 Generate visible relationships between satellites

根據(jù)上述方法生成星間可見性關(guān)系，并利用星地可見關(guān)系將衛(wèi)星劃分出境外星子集合Sat_JW，以星間可見性為約束條件，進行星間鏈路分配，生成星間鏈路分配矩陣B=bi,K∈RN×K。鏈路分配矩陣B為：

其中bi,K=j，表示衛(wèi)星i與衛(wèi)星j在時隙K建立鏈路。

在鏈路分配矩陣生成過程中，需要考慮星間可見性、建鏈表對稱性、星間鏈路數(shù)量等約束，約束條件的數(shù)學(xué)表達式如下：

vi,bi,K,Kslot=1 ?i,K

(5)

bbi,K,K=i?i,K

(6)

bi1,K≠bi2,K?i1≠i2,K

(7)

2.2 星間數(shù)傳路由模型

路由表作為數(shù)據(jù)傳輸路徑的走向表，其方向必須要是確定的。本文針對境外數(shù)據(jù)快速回傳這一目標(biāo)，以境外星到境內(nèi)星的數(shù)據(jù)傳輸方向為準(zhǔn)則，形成滿足回傳目標(biāo)的路由表。路由表形成規(guī)則如下：

1)關(guān)閉雙向建鏈表中的境內(nèi)-境外、境內(nèi)-境內(nèi)鏈路，置零；

2)對于境外-境外鏈路，隨機關(guān)閉其中的一個方向，置零。

通過上述關(guān)閉規(guī)則，可以確定數(shù)據(jù)傳輸路由表。如圖4中的路由表保證了數(shù)據(jù)的單向傳輸，不會發(fā)生數(shù)據(jù)去向不明的情況。例如，在時隙K=1，境外星1將數(shù)據(jù)傳輸給境外星2，然后K=2，衛(wèi)星2將數(shù)據(jù)傳輸給境內(nèi)星1，境外星3將數(shù)據(jù)傳輸給境內(nèi)星2。根據(jù)這樣的路由表，能夠保證每顆境外星上的數(shù)據(jù)在一定延遲后傳回境內(nèi)星，從而實現(xiàn)境外數(shù)據(jù)回傳境內(nèi)的目標(biāo)。

圖4 路由表Fig.4 Routing table

3 星間傳輸路由優(yōu)化方法

基于遺傳算法進行優(yōu)化計算，得到一個優(yōu)化路由表，優(yōu)化路由表需要滿足上述路由表的所有約束條件，并且能夠滿足一定的優(yōu)化目標(biāo)。遺傳算法的優(yōu)化步驟如下：

(1)編碼方法

本文采用實數(shù)編碼，一張路由表即一個染色體，每個時隙代表一個基因。

Chrom=[G1,G2,…,GM]

式中：GM代表一個染色體，染色體GM根據(jù)第2節(jié)中描述的模型計算產(chǎn)生。每個染色體GM的編碼為：

(2)初始化群體

初始化群體方法：對境外星子集Sat_JW中的衛(wèi)星進行輪詢建鏈，輪詢選擇時加隨機數(shù)，避免建鏈表中鏈路分配不均勻，由于可見星數(shù)有限，建鏈?zhǔn)r，將鏈路置零。按照路由表生成規(guī)則，形成算法所需初始種群。

(3)適應(yīng)度計算

本文在第1節(jié)中已經(jīng)對優(yōu)化模型進行了闡述。本步驟中的適應(yīng)度計算就是對上文中優(yōu)化模型的實現(xiàn)，具體實現(xiàn)方法如下。

假設(shè)每顆境外星上攜帶一個數(shù)據(jù)，根據(jù)路由表，可以計算每個時隙的數(shù)據(jù)傳輸流向。傳輸時延T的計算公式如下：

Ttime=skip×k

式中：skip是跳數(shù)，數(shù)據(jù)每傳遞一次，就代表一跳;k是時隙長度。某境外星在第m個時隙開始傳輸數(shù)據(jù)，在第n個時隙數(shù)據(jù)傳輸?shù)骄硟?nèi)星，該數(shù)據(jù)經(jīng)過n-m+1次傳遞(即skip=n-m+1)到達境內(nèi)星完成傳輸，記錄該跳數(shù)skip，skip×k就是該境外星的傳輸時延。篩選出種群中的最大傳輸時延，將其記為f0。記錄了一張表中每個境外星的傳輸時延，對所有境外星的傳輸時延求平均值，輸出的就是待求路由表的境外到境內(nèi)的平均傳輸時延，將其記為f1。

本文中，用于遺傳算法染色體的適應(yīng)度計算函數(shù)定義如下：

Ccost=min(a×f0+b×f1)

式中：f0，f1分別對應(yīng)于第1節(jié)中的傳輸時延；a，b分別對應(yīng)于優(yōu)化權(quán)重。

(4)選擇算子

遺傳算法的選擇方法有很多，本文中為了避免遺傳算法父代個體中的某些個體絕對占優(yōu)，采用的選擇方法是排序法，將染色體的適應(yīng)度值轉(zhuǎn)變成等差數(shù)列，以此作為該染色體的選擇概率。

(5)交叉操作

根據(jù)前文所述的編碼規(guī)則，一個路由表即一個染色體，交叉操作就是對兩個染色體(父代)中的基因進行交叉，從而得到新的染色體(子代)。本文所用的交叉方法如下：

1)根據(jù)適應(yīng)度函數(shù)得到染色體概率值，對概率值排序，根據(jù)交叉概率，選取待交叉染色體；

2)待交叉染色體中，采用兩兩交叉的方法，隨機選取一個或多個時隙K，互換兩個染色體中K時隙的基因內(nèi)容，交叉后形成新的子代染色體。

交叉方式如圖5所示。

圖5 染色體的交叉操作Fig.5 Chromosome cross operation

由于待交叉的路由表是由可見性、境內(nèi)境外屬性等多約束決定的路由表，如果按照簡單的隨機選取表中元素互換的方法來實行交叉操作，極易造成子代的不合理化，這樣極度浪費運算速度，甚至造成遺傳算法不收斂等結(jié)果。所以本文采用交換整體時隙的內(nèi)容，這樣避免產(chǎn)生的新表中部分數(shù)據(jù)不合理的情況，使每次交叉后的子代染色體都是符合約束條件的。

(6)變異操作

根據(jù)變異概率，對選擇出的待變異染色體進行變異操作，本文所用的變異操作是隨機選取一個時隙K，對該時隙的路由表進行變異規(guī)劃。首先對時隙K中境外星的可見星劃分優(yōu)先級，可見境內(nèi)星優(yōu)先級大于可見境外星，然后根據(jù)優(yōu)先級進行建鏈，再用路由表關(guān)閉規(guī)則，生成時隙K的變異后路由。

4 仿真算例及結(jié)果分析

4.1 仿真場景構(gòu)建

以北斗全球衛(wèi)星導(dǎo)航系統(tǒng)包含30顆衛(wèi)星為例。本例中，考慮北斗系統(tǒng)混合星座的特點，30顆衛(wèi)星按照24顆中軌(MEO)衛(wèi)星、3顆地球靜止軌道(GEO)衛(wèi)星和3顆傾斜同步軌道(IGSO)衛(wèi)星的方案(不代表北斗全球系統(tǒng)實際方案)進行分配。每顆衛(wèi)星裝有一部星間鏈路天線，天線為窄波束天線。衛(wèi)星軌道參數(shù)如表1所示。試驗所用到的地面站有北京站、三亞站。遺傳算法具體參數(shù)見表2。

表1 星座衛(wèi)星軌道參數(shù)

表2 遺傳算法參數(shù)

為了對算法進行檢驗，仿真場景的具體參數(shù)設(shè)置見表3。

表3 仿真場景參數(shù)

4.2 仿真結(jié)果與分析

根據(jù)表3仿真場景進行仿真試驗，得到優(yōu)化路由表，對試驗結(jié)果進行分析。試驗統(tǒng)計了2015年10月1日每分鐘的境內(nèi)星數(shù)量，并計算每分鐘優(yōu)化所得路由表的最大傳輸時延和平均傳輸時延。境內(nèi)星數(shù)量、最大傳輸時延和平均傳輸時延分別如圖6和圖7所示。

對比分析圖6和圖7，可知優(yōu)化結(jié)果的好壞與境內(nèi)星數(shù)目有直接關(guān)系。當(dāng)衛(wèi)星數(shù)量大于或等于15顆時，最大傳輸時延和平均傳輸時延均收斂到1跳；當(dāng)衛(wèi)星數(shù)量小于15顆時，最大傳輸時延收斂到2跳，平均傳輸時延收斂到1.3跳。

圖6 境內(nèi)星數(shù)量Fig.6 Number of domestic satellites

圖7 最大傳輸時延和平均傳輸時延Fig.7 Maximum transmission delay and average transmission delay

選取兩個典型的時刻，分別是境內(nèi)星數(shù)量大于15的第34 s和境內(nèi)星數(shù)小于15的第220 s，假設(shè)每次建鏈傳輸可以傳遞的數(shù)據(jù)量是100 Kbit，每顆衛(wèi)星上攜帶的數(shù)據(jù)量是50 Kbit和300 Kbit，根據(jù)兩個時刻優(yōu)化所得路由表，分析數(shù)據(jù)傳輸時間，結(jié)果如表4所示。

表4 數(shù)據(jù)傳輸時間

4.3 算法性能分析

北斗導(dǎo)航星座的24顆中軌衛(wèi)星(MEO)+3顆地球同步軌道(GEO)衛(wèi)星+3顆傾斜同步軌道(IGSO)衛(wèi)星+北京站+三亞站，獨立運行20次，遺傳算法的收斂性能如圖8所示。圖8(a)是平均傳輸時延的收斂性，圖8(b)是最大傳輸時延的收斂性能。從圖8可以看出，本文中的算法有著良好的收斂性，多次獨立運行均能快速收斂到最優(yōu)值。

圖8 算法收斂性Fig.8 Algorithm convergence

5 結(jié)束語

導(dǎo)航星座星間鏈路是導(dǎo)航星座實現(xiàn)整網(wǎng)數(shù)傳的重要方法，本文提出基于遺傳算法的境外數(shù)據(jù)快速回傳的路由優(yōu)化方法和數(shù)據(jù)傳輸方案，并通過仿真試驗，驗證了算法的有效性和可靠性。從仿真分析的結(jié)果可以看出，針對不同境內(nèi)星數(shù)量，算法均可以優(yōu)化得到傳輸時延最優(yōu)的路由表。

參考文獻(References)

[1] MAINE K, ANDERSON P, BAYUK F. Communication architecture for GPS III[C]∥Proceedings of 2004 IEEE Aerospace Conference. Piscataway: IEEE Press, 2004: 1532-1539.

[2] 陳忠貴,帥平,曲廣吉. 現(xiàn)代衛(wèi)星導(dǎo)航系統(tǒng)技術(shù)特點與發(fā)展趨勢分析[J]. 中國科學(xué)(E輯:技術(shù)科學(xué)),2009,39(4): 686-695.

CHENZ G， SHUAI P，QU G J. Technical characteristics and development trend analysis of modern navigation satellite systems [J]. Scientia Sinica，Technologica，2009，39(4):686-695.

[3] 李振東，何善寶，劉崇華. 一種適用于導(dǎo)航衛(wèi)星星間鏈路的動態(tài)路由算法[C]. 第二屆中國衛(wèi)星導(dǎo)航學(xué)術(shù)年會，上海：中國衛(wèi)星導(dǎo)航學(xué)術(shù)年會， 2011:1.

LI Z D，HE S B，LIU C H. An active routing algorithm for navigation satellite constellation inter-satellite links[C]. The 2th China Satellite Navigation Conference，Shanghai: China Satellite Navigation Conference， 2011:1.

[4] 張之學(xué)，薛峰，趙金賢，等. 基于演化圖理論的導(dǎo)航衛(wèi)星星座動態(tài)路由準(zhǔn)則及算法[C]. 第七屆中國衛(wèi)星導(dǎo)航年會，長沙：中國衛(wèi)星導(dǎo)航年會2016:6.

ZHANG Z X，XUE F，ZHAO J X，et al. Dynamic routing metrics and algorithms for navigation satellite constellation based on evolving graphic theory[C].The 7th China Satellite Navigation Conference，Changsha: China Satellite Navigation Conference，2016:6.

[5] 王彥,劉波,虞萬榮,等. 基于演化圖的導(dǎo)航星座星間路由算法[J]. 中國空間科學(xué)技術(shù),2012,32(5):76-83.

WANG Y，LIU B，YU W R，et al. Routing algorithm for navigation constellation based on evolving graph model[J].Chinese Space Science and Technology，2012，32(5)：76-83.

[6] HOU Z W, YI X Q,ZHAO Y,et al.Information trans-mission path selection of navigation satellite network based on directional crosslink[C]. The 7thChina Satellite Navigation Conference，Changsha：China Satellite Navigation Conference ,2016：461-470.

[7] 燕洪成，張慶君，孫勇. 基于局部隊列的導(dǎo)航衛(wèi)星網(wǎng)絡(luò)路由算法[J]. 宇航學(xué)報, 2015,36(12)：1444-1452.

YAN H C，ZHANG Q J，SUN Y. A novel routing algorithm for navigation satellite network based on partial queues[J]. Journal of Astronautics,2015,36 (12): 1444-1452.