基于局部洪泛優化的低軌星座分布式路由算法

周 宇，尹增山，王 龍

（1.中國科學院微小衛星創新研究院，上海 201304；2.上海科技大學信息科學與技術學院，上海 201210；3.中國科學院大學，北京 100049）

0 引言

衛星網絡近年來發展迅速，星座路由算法致力于實現衛星網絡數據包的高效轉發和擁塞控制，將顯著地影響網絡性能和效率，許多學者對此做了長期研究。WERNER 等［1］提出的虛擬路徑路由算法［1］和GOUNDER 等［2］提出的快照序列算法，首先將衛星的周期運動劃分為離散的狀態序列以實現靜態路由，但難以進行網絡擁塞控制。AKYILDIZ等［3］隨后提出了多層路由算法，通過協同星座內部高/中/低多層軌道，進行分區分工管理，以實現衛星之間動態路由和網絡協調。在此基礎上，許多學者針對服務質量（Quality of Service，QoS）路穩定性、擁塞控制等方面進行了研究。

分布式路由算法不依賴地面站，能夠在軌自主運行，對網絡突發流量和需求波動快速響應，具有重要工程價值。HENDERSON 和EKICI 等［4-7］指出，通信星座網絡拓撲結構具有規律性，輕量級算法即可實現近似最優路由性能。TARIK 等［8-11］通過相鄰鏈路的擁塞感知，利用交通燈機制、拓撲關系或替代路徑分配，進一步改進了算法。此外，融入了蟻群算法、極限學習機等啟發式方法的分布式算法［12-13］相繼出現，通過全局傳導或洪泛收集沿途鏈路信息，以進行網絡擁塞控制。隨后，多層星座的分布式路由算法［14-16］也被提出，用于中/低軌層間的流量均衡或QoS 性能保障。

然而，目前低軌星座呈現規模大、節點數量多、多層分布特征。例如StarLink 星座一期包含數千顆衛星，分5 層，軌道高度在540～570 km 之間［17］。基于全局洪泛的網絡路徑規劃存在較大路由延遲和通信開銷；而傳統分布式算法［4-6］以單層衛星網絡拓撲為主，較難適用于多層低軌衛星網絡結構［17-18］。針對以上問題，提出一種基于局部洪泛優化的分布式路由算法，具有如下創新：

1）利用分布式的局部洪泛，以較低的算力開銷和延遲，實現了對局部擁塞的路徑優化。

2）基于局部鏈路感知，可適用于單層或多層低軌衛星網絡結構，提高了對衛星隨機故障的適應性，降低網絡丟包率。

1 基于局部洪泛的擁塞感知

1.1 通信需求高度不均的分布特征

相比地面通信網絡，低軌星座網絡具有規律性移動特征。因此各類星座計劃［17-18］，主要采用均勻穩定Walker［19］或極地軌道星座構型。若要對特定區域提供持續衛星信號覆蓋，需要均勻地部署大量低軌衛星。然而，陸地僅占地球表面積約30%，并且人口和經濟活動進一步集中在少數陸地區域［20］，如圖1 所示，圖中顏色越深表示人口和經濟活動密度越大（耶魯大學的G-Econ［21］項目）。

圖1 人口與通信需求的高度不均勻分布Fig.1 Highly uneven distribution of population and communication demand

衛星星座建設無法像地面網絡基站一樣依據用戶密度按需部署，因此容易出現局部擁塞。傳統路由一般采用全局洪泛［22］或啟發式方法的全局傳導［12］，然而對于大型低軌星座，通信和處理開銷很大。因此，提出了基于局部洪泛優化的分布式路由算法，有利于解決圖1 中高度不均衡的通信業務需求引起的局部擁塞。

1.2 局部洪泛的過程

為了緩解局部擁塞，算法采取局部洪泛的機制收集周圍鏈路的排隊延遲。

1）洪泛數據包格式定義

設單顆衛星共有q條星間鏈路，則每經過時間周期Tlocal，每顆衛星即向周圍發出一個局部洪泛包，數據格式為

式中：IDsate為當前衛星的唯一標號；tpacket為此局部洪泛包的生成時間，s；hlocal為此局部洪泛包的剩余跳數，當跳數被用完，此包失活并被丟棄；tISL-1～tISL-q為當前衛星的q條星間鏈路的實時排隊延遲。IDsate和tpacket用于唯一確定洪泛包，防止重復轉發。

令局部洪泛跳數hlocal的初始值為一個預設值Hlocal，則單個洪范包所能傳輸的最遠跳數是Hlocal。由此，星座中每顆衛星能夠搜集到相隔Hlocal跳之內各顆鄰近衛星的鏈路排隊延遲信息。

2）局部洪泛范圍的確定

局部洪泛跳數Hlocal的取值應當對于不同的星座參數進行調整，以保證覆蓋可能產生局部擁塞的人口密集區域。但如果Hlocal的取值過大，則容易加重衛星算力負擔。使用如下步驟確定Hlocal的取值。

步驟1計算出鄰近某個特定城市的衛星集合Z。

式中：Si為衛星；Ssite_city為城市坐標；Llocal為城市區域的半徑，m。

把以Ssite_city為中心Llocal為半徑的地面范圍，視為可能會產生局部網絡擁塞的城市區域。而函數N(Si，Ssite_city)用于計算衛星Si所覆蓋的地面區域，到城市坐標Ssite_city的距離。此函數與軌道高度、星地通信最小仰角有關，可根據幾何關系求解。

步驟2計算出距離最接近某個特定城市的衛星Scity，如下式所示。其中，函數D(·)用于計算兩者距離，易知Scity∈Z。

步驟3依據集合Z和衛星Scity，計算出最遠跳數Hlocal的取值，如下式所示：

式中：函數Hop(Si，Scity)用于計算從衛星Si到Scity最少需要經過幾條星間鏈路，可通過Ekici 等［4］的衛星標號方法算得。

基于此流程算得的Hlocal，保證了衛星的局部洪泛范圍能夠完整地覆蓋容易產生網絡局部擁塞的城市區域（以Llocal為預設半徑），因為其包含了所有可能對城市區域進行波束覆蓋并建立星地鏈路的衛星。一般選取從低緯度的新加坡，到高緯度的倫敦等主要城市的坐標帶入參數Ssite_city，并按照現在的城區范圍，令Llocal為100 km 等數值，即可算得局部洪泛最遠跳數Hlocal。

2 局部感知優化的算法設計

2.1 路徑優化

在局部洪泛的基礎上，設存在衛星A正在路由轉發數據包P，并且數據包P的接收地為點O，則局部洪泛優化如圖2 所示。圖中綠色背景的衛星處于洪泛邊緣。

圖2 局部洪泛感知和確定轉發路徑Fig.2 Diagram for local flooding awareness and selecting forwarding paths

設局部洪泛共涵蓋N顆衛星，共有M顆衛星位于洪泛邊緣，洪泛邊緣的衛星可表示為Ei(1 ≤i≤M)。首先，根據式（1）進行局部洪泛獲取的鏈路信息，用Dijkstra 算法得出局部最優路徑序列：

式中：tpath為生成此序列的時間，s；IDi為圖2 中的第i顆衛星的唯一標號；Qi為衛星A到第i顆衛星的最短路徑權重，是路徑上每條星間鏈路的排隊延遲和傳輸延遲之和，s；Pi為最短路徑中途經衛星的標號序列。

因為通常單顆衛星有4 條星間鏈路數（2 條同軌，2 條異軌），遠小于衛星數量N，可利用堆結構將Dijkstra 算法的時間復雜度降為O(NlogN)［23］。

在高度擁塞的局部網絡中，最優路徑會變得迂回曲折。因此，定義了指標“距離成本系數”，用于衡量數據包P如果傳輸至洪泛邊緣衛星Ei，是否能用更短的時間更快地接近目的地。以圖2 為例，處于洪泛邊緣的衛星Ei相對于數據包P及其接收地O的距離成本系數為

式中：函數D(·)用于計算兩者間的直線距離；ε用于防止除零；QEi式（5）中的最短路徑權重。

路由時，當前衛星會為每個數據包選出“距離成本系數”最大的轉發路徑，如式（7）所示。其中函數p(·)可依據式（5）將參數衛星映射為對應的局部最優路徑（以途徑衛星的標號序列表示），RP為路由算法數據包P選出的轉發路徑。

由此，算法可在局部洪泛范圍內，選出讓每個數據包最快接近目的地的局部最優路徑，從而實現對局部網絡擁塞的路徑優化。

2.2 多路徑間負載平衡

上述過程分布式地運行在每顆衛星上，存在兩個問題：首先，衛星在軌資源受限，局部洪泛和路徑優化的頻率不能過高；其次，路由算法需要及時響應網絡突發流量和通信需求波動。

例如，任意兩地之間如果出現大量的瞬時衛星通信需求，式（7）會將全部數據包轉發到某一條局部最優路徑上，隨即加重了此路徑的擁塞程度和傳輸延遲。如果將突發流量分攤到多條相似的路徑上，可降低端到端延遲，提高整體的網絡效率。

為此，引入指標“路徑附加延遲”REi作為式（6）分母的補充，則式（7）更新成下式：

當圖2 的衛星A完成路徑更新后，REi的初始值為0。當衛星A根據式（8）選擇出的局部最短路徑，以洪泛邊緣衛星Ei為終點時，令數據包長度為LP，星間鏈路傳輸速率為SISL，則REi按下式更新：

在式（8）中，REi與路徑延遲QEi之和，可用于實時估算各條路徑所花費的時間成本，把流量負載動態平衡地分配到多條相似路徑上，以提高網絡的傳輸效率。不過，附加延遲REi的數值準確度較低，因為多條路徑之間可能包含相同的星間鏈路，其他相鄰衛星也在并行地進行著相同的路由轉發過程。其主要作用是實現局部的網路負載均衡。

綜上，算法流程圖如圖3 所示。

圖3 局部感知優化的分布式路由算法流程Fig.3 Flow chart of the distributed routing algorithm based on local flooding optimization

如圖3 所示，若數據包的接收地靠近當前衛星，則在局部洪泛范圍內即可找到下傳衛星和下傳路徑。這種情況依然要用到式（9）的“路徑附加延遲”，以助于在多個下傳衛星中平衡分配流量。

算法基于“距離成本系數”選擇局部轉發路徑。在圖2 中，由于衛星連續均勻部署，總會存在更靠近O點的洪泛邊緣衛星，讓式（8）的分式D(O，A)-D(O，Ei)大于零，使得數據包會不斷接近O點。此過程不可逆，因此算法可以避免出現環路。

同時，利用局部洪泛收集鏈路信息，該算法可建立到達洪泛邊緣衛星的路徑映射關系，無論部署在單層或多層低軌衛星網絡中，或面對隨機的衛星故障，均可屏蔽局部網絡的結構差異，正常運行。

2.3 時間和空間復雜度

每顆衛星存在4條星間鏈路，以Hlocal=4 為例，局部洪泛收集鏈路信息所涉及的局部網絡如圖4 所示。根據圖4 類推，局部網絡的衛星數目為N=1+2Hlocal(Hlocal+1)，洪泛邊緣的衛星數M=4Hlocal。為了防止洪泛包的重復轉發，需保存O(N)的數據。而式（5）的路徑信息，需保存O(N2)的數據。則空間復雜度為

圖4 洪泛感知的局部網絡（以Hlocal=4 為例）Fig.4 Diagram of flooding aware local network（taking Hlocal=4 as an example）

設局部洪泛和Dijkstra 算法的運行周期為Tlocal，已知Dijkstra 算法的時間復雜度為O(NlogN)，則每秒的計算復雜度為1/TlocalO(NlogN)。設每顆衛星每秒需要傳輸平均k個數據包。根據式（8），單個數據包選擇局部路徑的復雜度為O(M)。由圖4 類推，從衛星A到洪泛邊緣，路徑最短為Hlocal。數據包每完成一條路徑僅路由一次，則單顆衛星需要處理最多k/Hlocal個數據包。因此，每顆衛星每秒運行的時間復雜度為

近年發表的GomHop 算法［24］和低開銷分配方案協 議（Low-overhead Distribution Scheme Protocol，LSP）算法［10］時間復雜均為O(k)。算法增加的部分來自局部路徑優化。因為Hlocal取值范圍通常在3 至10 之間，若洪泛周期Tlocal取值合理，算法的時間復雜度依然較小。同理根據式（10），算法的空間復雜度也較小。

3 仿真分析

為了驗證算法的擁塞控制性能，以及對網絡隨機故障、多層低軌衛星網絡結構的寬適應性，獨立搭建了仿真環境。

選擇StarLink 星座其中3 層作為仿真對象，相關軌道參數見表1［17］。其相位因子、鏈路設置等細節，參考了Handley 等［25］的處理方法。星間鏈路傳輸速率設為10 Gbps，設置所有數據包的收發地相隔大于1 000 km，以排除無需通過星間路由轉發情況。通信業務分布假定與人口數量以及人類發展指數（Human Development Index，HDI）正相關，人口數據與HDI 數據參照美國航空航天局官網，經緯度1°方格為網格單元。實驗中選擇洪泛范圍Hlocal和洪泛周期Tlocal分別取(4，0.3 s)、(6，0.3 s)、(6，0.1 s)3 種情況。選擇GomHop 算法［24］（2019）和LSP 算法［10］（2019）作為比較對象。

表1 仿真實驗的星座軌道參數Tab.1 Constellation orbit parameters of the simulation tests

3.1 擁塞控制和故障包容仿真實驗

取表1 中軌道高度550 km 單層衛星網絡，針對不同網絡負載和衛星故障率5%的情況進行仿真結果如圖5 所示。

圖5 擁塞控制和故障包容的仿真結果Fig.5 Simulation results for congestion control and fault containment

如圖5 所示，圖中LAD 為局部感知分布式算法（Locally Aware Distributed Algorithm）。算法能夠明顯降低網絡丟包率，并且局部洪泛跳數越大、洪泛周期越短，丟包率越低，性能越好。在衛星故障率為5%時，依然能將低流量負載的丟包率降至接近0%，對故障的包容性更大。

同時仿真表明，針對通信業務需求均勻分布情況，幾種算法的丟包率都會降低到0%。針對高度不均衡通信業務需求分布情況，算法具有擁塞控制能力，能夠疏導局部擁塞。

3.2 多層網絡結構適應性仿真實驗

多層低軌衛星網絡存在跨層星間鏈路。在仿真中設定2 層中滿足距離近、移動方向相同，并且位置關系滿足一定持續穩定建鏈時間需求的2 顆衛星間建立一條跨層鏈路。選取表1 中所有層次作為仿真對象，結果如圖6 所示。

圖6 多層低軌衛星網絡中的丟包率Fig.6 Packet loss rates in multi-layer LEO satellite networks

當衛星出現故障時，本文算法相比GomHop 在丟包率上有更好的表現。當參數選取Hlocal=6，Tlocal=0.1 s 時，本文算法能夠將網絡負載小于1 000 Gbps 時的丟包率降為接近0%，將網絡負載小于1 500 Gbps 的丟包率降至5%以下。

4 結束語

本文針對傳統分布式星座路由算法擁塞控制能力有限，全局路徑優化開銷過大的問題，提出了一種局部洪泛優化的分布式路由算法。通過定義“距離成本系數”為每個數據包確定轉發路徑，估算各條路徑延遲增量，將瞬時流量平衡分配。該算法空間/時間復雜度較低，能夠滿足小衛星在軌部署的需求，且不會出現路由環路，能夠自動適應鏈路故障和多樣化網絡結構。仿真表明，針對高度不均通信需求分布，該算法可降低2%～10%的丟包率，并能更好適應多層低軌衛星網絡架構。本質上，該算法融合了高計算開銷的全局尋徑，低擁塞控制能力的靜態路由這兩者的部分機制，嘗試在降低路由開銷和減少網絡擁塞之間取得平衡，以更好應對地域人口高度集中和需求分布不均的普遍現象，節省在軌路由算力，優化天基網絡的通信效率。

未來研究中，面對流量地理分布不均，將計劃開展統計學建模分析，構設流量統計和波動預測模型。同時，將跟進修改本文算法，以實現針對擁塞程度和范圍的自適應統計感知。并且基于即時擁塞感知，將路由算力按需定向投入，在進一步降低端到端丟包率和通信延遲的同時，嘗試保持全局較低的平均路由開銷，以優化全網通信效率，讓未來的算法更好彌合“地面基站密度可按需按域增減”和“通信星座的衛星密度全球大致均勻”這一硬件機制差異，提升天基網絡應對瞬時高強度流量沖擊的自適應能力。