面向導航星座的混合路由技術研究

張 方，周 淦，喻瑤瑤，聶殿輝，豐大軍

(1. 中國電子信息產業集團有限公司第六研究所，北京 100083；2. 西安電子科技大學 空間科學與技術學院，陜西 西安 710071)

0 引言

隨著衛星應用和需求的不斷發展，衛星導航系統無論是在戰略資源上還是商務民用方面都體現了其重要的應用價值，給人們的工作和生活帶來很大的便利。然而，由于傳統的衛星導航系統存在導航精度低、抗毀性能差和無自主運行能力等缺點，已無法滿足人們對衛星業務的需求。星間鏈路的建立則可以很好地解決以上問題，它不僅可以實現各節點(不同軌道的衛星與地面站)之間的互聯互通，還幫助形成具有對空間傳輸信息的獲取、存儲、處理、傳輸以及分發等功能的空間信息網絡，是衛星導航系統的必然發展方向[1-4]。

近年來，全球衛星導航系統飛速發展并不斷完善，星間鏈路的引入給導航系統帶來較多的技術難題，其中，路由規劃問題成為研究的焦點。國內外學者對于導航系統的路由規劃問題也有大量的研究成果可以借鑒。文獻[5]對星間可見性以及星間距離變化做了詳細分析，根據推導出的公式設計了一種靜態無需切換和一種動態帶切換的網絡拓撲結構；文獻[6]針對同軌道星間鏈路拓撲結構進行分析，通過對比不同的拓撲結構對星地數據傳輸性能的影響，得出當數據在節點處理時延較大時同軌鏈路應選擇八角星拓撲結構的結論；文獻[7]基于TDMA時分多址體制的星間通信模式提出了一種較為全面的通信代價評估方案，得出星間鏈路混合型拓撲結構比環形拓撲結構的通信性能更好的結論。

針對以上研究現狀，本文面向導航星座，研究包含衛星網絡所組成的天基網和各地面站所組成的地基網絡的多層空間網絡路由規劃問題，提出了一種混合路由方案。首先對節點負載和傳輸距離等影響數據傳輸的因素進行單獨研究，然后綜合考慮等待時延、鏈路速率、節點負載和傳輸距離等多種影響因素，探索并建立合理的混合評價函數，使算法所規劃出的路徑能夠減小復雜的空間運行環境對信息傳輸的影響，合理有效地利用星間鏈路資源，從而增強系統的穩定性和可靠性，為正在建設過程中的“北斗”衛星導航系統提供理論依據和應用基礎。

1 星座拓撲分析

1.1 星座構型

本文研究的空間網絡模型分為3層，包括高軌衛星、中軌衛星和地面站以及地面控制管理中心。其中，高軌衛星高度約36 000 km，由3顆GEO和3顆IGSO構成，GEO分布在赤道上，經度分別為80°、110.5°和140°；IGSO軌道傾角為55°，三星相位差120°。中軌衛星MEO由構型為Walker24/3/1星座構成，軌道高度為21 528 km，為了便于分析，將24顆MEO衛星分別命名為MEOij(i∈[1,3]，表示軌道面編號；j∈[1,8]，表示軌道內的衛星編碼)。地面由3個地面站和1個地面控制管理中心構成，分布于我國境內，其中，地面控制管理中心通過對地面站合理的規劃與調度實現對衛星的監測與控制。導航星座整體架構如圖1所示。

圖1 導航星座構型示意圖

1.2 星間可視性分析

衛星之間的可視性是星間通信的前提條件。目前影響衛星之間的可視因素主要包括地球及大氣層的遮擋、衛星天線波束掃描范圍限制以及電磁波測距極限3個方面，下面作詳細介紹。

(1)地球及大氣層的遮擋

假設地球半徑為R，衛星軌道高度為h，大氣層厚度為H，衛星A、B之間的距離為l，如圖2所示。

圖2 地球遮擋情況下衛星可見關系示意圖

由幾何關系可得衛星之間的距離l應滿足如下關系式：

(1)

(2)衛星天線波束掃描范圍限制

假設地球半徑為R，衛星軌道高度為h，兩衛星之間的距離為l，波束掃描范圍為±β，如圖3所示。

圖3 衛星波束掃描范圍受限情況下可見關系示意圖

由幾何關系可得衛星之間的距離l應滿足如下關系式：

l>2(R+h)cosβ

(2)

綜上所述，兩衛星之間建立通信的前提條件為它們之間的距離l應滿足如下關系式：

(3)

(3)電磁波測距極限

衛星A、B要能夠建立鏈路進行通信，除了滿足以上兩個條件外，還必須滿足兩者之間的距離小于電磁波所能達到的最大距離，即：

l

(4)

式中，Lmax為測距極限，本文取Lmax=5 000 km。

因此，星間鏈路可見性可表述為：如果衛星A、B之間的連線與地球表面(考慮大氣層)沒有交點，接收星在發射星的天線覆蓋范圍內，且在發射星的測距范圍內，則稱兩顆星是可見的；否則，如果缺少任何一個或幾個條件，則稱它們是不可見的。因此衛星B對衛星A的可見性VB→A定義為：VB→A=1，交點不存在，即可見；VB→A=0，交點存在，即不可見。由此，可以確定一個瞬時的拓撲結構。

1.3 衛星拓撲模型

星間鏈路有3種，包括永久鏈路、非永久鏈路和不可見鏈路，分別對應衛星持續可見、非持續可見和永遠不可見3種情況。對于導航星座來說，頻繁地切換拓撲結構對于系統的穩定性是不利的，因此建立如下建鏈規則：

(1)優先與永久鏈路建鏈，盡量減少網絡拓撲結構的切換頻度。

(2)采用在永久鏈路的基礎上增加非永久鏈路的組合方式建鏈，以避免鏈路性質過于單一導致拓撲結構的抗毀性降低。

通過使用衛星工具包(Satellite Tools Kit, STK)對星座進行仿真，得到衛星的永久鏈路有6條，包括同軌道中和本星相隔的2顆衛星，西側相鄰軌道與目標星平近點角相差-15°、-150°的2顆衛星以及東側相鄰軌道與目標星平近點角相差15°、150°的2顆衛星。

對于非永久鏈路的選取，則采用GDOP貢獻值法，將除永久鏈路之外的可視衛星進行GDOP貢獻值排序，選取GDOP貢獻值較大的衛星進行建鏈，以保證導航星座的測量精度，提高導航服務質量。本文中非永久鏈路為5條[8]。

2 路由方案的設計

2.1 概述

路由生成方案的設計要解決的問題是：針對特定場景，從多條備選路徑中搜索出最佳路由方案。通常，為鏈路設置一個權值來反映該鏈路的數傳代價，進而通過選擇權值最小的鏈路進行最優路由的生成。本文針對鏈路權值展開重點分析，而在路徑搜索上則沿用傳統的Dijkstra算法。

2.2 Dijkstra算法描述

Dijkstra算法的基本思想是：以路徑長度為對應路徑的權值，通過對權值的迭代，得到從源節點到目的節點的最小權值對應的最短路徑[9]。代碼如下：

Dijkstra算法：function Dijkstra(G, w, s)

輸入： 鄰接矩陣G，起始節點w，目的節點s

輸出： 最短路徑對應的節點及權值

for (each vertex v in V[G]){

d[v]:= infinity //將各點的已知最短距離設成無窮大

previous[v]:= undefined

}

d[s]:= 0

//將s到s的最小距離設為0

S:= empty set

Q:= set of all vertices

while (Q is not an empty set){

u:= Extract_Min(Q)

S.append(u)

for (each edge outgoing from u as (u,v)){

if d[v] > d[u] + w(u,v)

d[v]:= d[u] + w(u,v)

previous[v]:= u

}

}

通過使用Dijkstra算法即可搜索出源節點到目的節點的最短路徑。在實際的衛星導航系統中，地面控制管理中心即可通過該路徑對全網衛星進行遙測回收或境外星指令上注，具有實際應用價值。

2.3 混合路由策略

傳統的路由生成方法對于數傳的影響因素考慮較為單一，如最短路徑算法以距離作為數傳代價進行路徑搜索，算法可以搜索出源節點到目的節點距離最短的路徑，但不能保證時延最小，實際上衛星從接收信息到發射信息期間的時延是不容忽視的。因此，傳統的路由算法難以滿足實際工程應用的需求。

本文在減小端到端時延和均衡節點負載方面，對影響因素進行較為全面的分析。其中，端到端時延主要包括等待時延(衛星從接收到發送期間的等待時間)、鏈路傳輸速率所產生的時延以及節點空間距離產生的傳播時延。同時，為了充分高效地利用空間網絡資源，算法會首先計算各節點的負載，然后再進行路由規劃，并盡可能使各節點的負載均衡化，來降低網絡出現擁塞或者丟包的可能性，從而保障系統能夠穩定運行。因此，本文考慮的數傳代價包括[10]：(1)等待時延；(2)鏈路速率；(3)節點距離；(4)節點負載。

2.4 鏈路權值的定義

節點距離、節點負載以及等待時延與數據傳輸代價成正比，而鏈路速率越大，數據傳輸所消耗的時間就越短，因此鏈路速率與數據傳輸代價成反比。結合以上因素，本文給出鏈路權值Q的定義如下[11]：

(5)

其中，ρ為鏈路長度，ρmax為當前時刻所有能夠進行通信的節點之間的距離的最大值；l為節點的負載，lmax為當前所有節點負載的最大值；t_wait為下一跳節點的等待時延，t_waitmax為全網節點等待時延的最大值；r為節點之間的信息傳輸速率，考慮到真實系統中鏈路傳輸速率的可選性，本文中星間傳輸速率包含4組可選值，而星地傳輸速率包含2組可選值，rmax為當前正在進行通信的所有衛星間的最大信息傳輸速率。將式(5)中的各因素進行歸一化處理可以更客觀公平地反映鏈路代價。

3 仿真結果

3.1 仿真場景

本實驗采用典型的遙測回傳及數據上注的業務場景，實現地面控制管理中心對24顆中軌道衛星的實時監測和控制。地面站不可直接觀察到的衛星為境外星；反之，則為境內衛星。兩種衛星與地面控制管理中心的數據傳輸都需要對地面站進行規劃與調度，另外，對于境外衛星而言，還要選擇合適的節點星進行數據中轉。因此，要求路由算法能夠規劃出一條合理的路徑，使得衛星與地面控制管理中心的通信時延應盡可能小，同時要保證各節點的負載指數差在可接受范圍內。本實驗仿真時刻為2017年10月13日4:00:00am，假設每顆衛星所產生的遙測數據量相等(GEO/IGSO除外)，圖例中衛星編號1～24分別對應MEO11～MEO38。

3.2 實驗結果

實驗首先將最短路徑路由算法和所提出的混合指標約束的路由算法得出的結果進行對比，來驗證混合指標約束方案能夠從當前滿足建鏈條件的衛星中選擇距離較近的衛星來建鏈；然后，將負載均衡路由算法和混合指標約束路由方案得出的結果進行對比，驗證混合路由方案能從滿足建鏈條件的衛星中選擇當前時刻較為空閑的衛星進行數據傳輸；最后，將3種算法得到的路由方案時延進行對比，驗證混合路由方案可以在綜合多種影響因素的情況下為衛星計算出時延最小的路由，從而確保地面控制管理中心對衛星監測和遙控的實時性。下面對仿真結果進行詳細介紹。

3.2.1混合路由方案路徑最短驗證

將最短路徑路由算法和混合路由方案所規劃的路徑進行進一步整理，得到兩種算法的鏈路距離，結果如圖4所示。

圖4 源節點到目的節點路徑的距離

從圖4中可以看出，混合路由方案在大部分情況下得到的結果與最短路徑算法得到的結果接近，只有在個別處出現較大的差距，這是因為混合路由方案選擇了使得遙測回傳時延最小的路徑而沒有選取最短路徑所致，并且通過3.2.3節可以看出這并不影響混合路由方案選擇出時延最小的路徑。

3.2.2混合路由方案負載均衡驗證

將負載均衡算法和混合路由方案下各節點的負載情況進行了統計，統計結果如圖5所示。

圖5 衛星負載

從圖5可以看出兩種算法各節點的負載均衡度相差不大，混合路由方案在衛星MEO17、MEO26處負載稍大，這種情況是符合最優化理論的。為此進一步計算出了所有節點負載指數的方差以定量分析均衡度。負載均衡算法各節點負載指數方差為0.022，混合路由方案下各節點負載指數方差為0.029，由此可以得到結論：混合路由方案能夠從滿足建鏈條件的衛星中選擇相對空閑的衛星建立鏈接，以達到負載均衡的目的。值得指出的是，兩種算法負載指數在衛星MEO14、MEO15、MEO21、MEO22和MEO23處均出現峰值，這是由于當前時刻這些衛星節點作為境內接入衛星所導致的。

3.2.3混合路由方案最小時延驗證

對于路由算法，其所規劃的路徑具有較小的時延是至關重要的。為了進一步驗證混合路由方案能夠規劃出時延較小的路徑，將最短路徑和負載均衡路由算法同本文提出的混合路由方案所規劃的路徑時延進行了統計分析，統計結果如圖6所示。

圖6 衛星數據下傳到地面站時延

圖6是最短路徑算法、負載均衡算法和混合路由方案下， 24顆MEO將數據下傳到地面站的時延統計圖。從圖中可以看出，混合路由方案所規劃的路徑時延在大部分情況下都是小于其他兩種算法的。這是由于在一些特殊情況下，為了使各節點負載相對均衡，算法選擇了等待時延或者距離稍大的衛星作為中轉衛星所致，但該路徑時延仍在可接受范圍內。同樣，在衛星MEO14、MEO15、MEO21、MEO22和MEO23處，各方案所規劃路徑時延相等是該衛星和地面站的可見性導致的。

4 結論

本文首先簡要分析了星間鏈路拓撲結構模型，引出衛星導航系統的路由問題；然后，提出了一種綜合考慮等待時延、鏈路速率、節點負載和傳輸距離等多種影響因素的混合路由策略；最后，以端到端時延和節點負載為評價指標，通過實驗驗證了本文所提出的混合路由策略大部分情況下能夠在保證網絡負載均衡的同時，搜索出端到端時延最小的路徑，合理有效地利用星間鏈路資源，為正在建設過程中的北斗全球衛星導航系統提供理論依據和應用基礎。

[1] LUBA O, BOYD L, GOWER A, et al. GPSIII system operations concepts[J]. Position Location and Navigation Symposium, 2004, 20(1):354-363.

[2] RAJAN J A. Highlights of GPSII-R autonomous navigation

[C]//Proceedings of the ION 58th Annual Meeting of the Institute of Navigation and CIGTF 21st Guidance Test Symposium. Albuquerque, NM:The Institute of Navigation, Inc, 2002:354-363.

[3] HOLMES J K, RAGHAVAN S. A summary of the new GPS IIR-M and IIF modernization signals[C]//Proceedings of the Vehicular Technology Conference (VTC 2004-fall). Los Angeles: IEEE, 2004:4116-4126.

[4] 劉小躍.空間信息網高性能路由協議研究[D]. 西安：西安電子科技大學，2012.

[5] 李振東，何善寶，劉崇華，等，一種導航星座星間鏈路拓撲設計方法[J].航天器工程，2011,20(3):32-37.

[6] 侯穎，米志超，于衛波，等，星地一體化導航系統星間鏈路仿真分析[J].通信技術，2014, 47(2)：145-149.

[7] 陳建云，吳光耀，馮旭哲，等，衛星星座星間通信鏈路拓撲分析[J].儀器儀表學報，2014, 35(12)：101-105.

[8] 周淦，張方，喻瑤瑤，等，導航星座星間鏈路拓撲及混合路由方案[C].北京：中國衛星導航學術年會，2018.

[9] 張美玉，簡琤峰，侯向輝，等.Dijkstra算法在多約束農產品配送最優路徑中的研究應用[J]. 浙江工業大學報，2012, 40(3)：321-325，330.

[10] 王冬霞，趙金賢，胡彩波，等.雙層衛星網星間鏈路混合路由算法設計 [J]. 導航定位學報，2016, 4(2):29-35.

[11] 孫娟.導航星座星間鏈路設計研究[D]. 南京：南京航空航天大學，2011.