基于多徑的低軌衛星網絡路由擁塞控制策略

焦媛媛，田 豐，石 神 ，劉 潔，劉會杰1，，3

（1.中國科學院上海微系統與信息技術研究所上海200050；2.中國科學院上海微小衛星工程中心上海201203；3.上海科技大學信息科學與技術學院，上海201210；4.中國科學院大學北京100049）

隨著星上處理技術的發展與星上存儲能力的增 強，衛星通信因其獨特的優勢（覆蓋范圍廣、不受地理條件影響等）與地面通信系統形成互補，廣泛應用于地面通信系統不易覆蓋或建設成本過高的領域。其中LEO衛星相對于靜止軌道衛星來說具有更低的傳輸時延、能夠覆蓋較高的維度區域和更低的終端發射功率要求等優點，使得LEO衛星通信占據優勢地位，眾多LEO衛星系統成功運營是最好的證明，如Iridium、Teledesic、Orbcomm等[1-2]。

與高軌通信衛星相比，低軌衛星功率較小、覆蓋面積較小，需要構建低軌衛星網絡，進行組網通信[3]。現實場景中，業務需求分布不均勻，例如發達國家業務需求高于發展中國家，陸地業務需求高于海洋業務請求，使得低軌衛星通信網絡出現鏈路阻塞，從而影響通信質量[4]。針對這一挑戰，本文提出一種新的網絡擁塞控制策略，利用多徑均衡整網流量，減小擁塞，提高網絡魯棒性。

目前已有許多常用擁塞控制算法，如主動隊列管理、丟包策略、數據包管理[5-6]。前兩種方法都有一定的丟包概率，數據包調度最適用于路由算法改進達到擁塞控制目的，是一種能盡量降低丟包率的一種方法，他通過感知節點自身擁塞狀況與周圍鄰居節點的擁塞狀況，及時分流給鄰居節點，然而是以犧牲實時性能、可靠性等性能指標實現的。現有的以時延或跳數為目標的單徑路由算法（如Dijkstra、BellmanFord算法等）在網絡任務數較少的情況下性能較優，但是在任務量較多的情況下易造成擁塞狀況[7-8]。

多徑路由有利于均衡負載，減少網絡擁塞[9-10]。考慮低軌衛星網絡（LEO）是高度確定的網絡（衛星在確定的軌道上運動），在特定時間每顆衛星路由的流量大致可以估計，我們可以提前對網絡進行網絡流量的分配，而不是被動地分流[11]。為了盡可能降低丟包率同時不犧牲路由算法的實時性和可靠性，本算法同時將路徑的時延和跳數考慮在內作為網絡帶寬的開銷指標，采用多徑，以最小化整網鏈路傳輸帶寬方差與整網鏈路傳輸帶寬開銷總和為目標，得出多徑路徑帶寬分配系數，當網絡任務數增多時，與單徑路徑對比能夠大幅度降低網絡中超負荷鏈路數，同時達到實時分流的效果。

1 模型的建立

銥星星座共有66顆衛星（有6個軌道，每個軌道有11顆）[1]。假設衛星彼此可視，且在一定的通信距離下，可以通信[13]。網絡中任意一對節點間存在多條路徑，為每一條路徑設置傳輸帶寬上限。當任務超過一定數目時，多個任務的路徑存在部分鏈路重合現象，即存在鏈路同時傳送多個任務的帶寬。如下圖1。

圖1 部分鏈路重合

此時網絡存在多條鏈路擁塞，導致網絡魯棒性下降。然而，即使有些鏈路如此“繁忙”，網絡中仍存在鏈路處于“閑置”狀態。如何均衡整網流量成為以銥星星座為代表的LEO網絡亟待解決的問題。

將上述低軌衛星星座抽象為一個有N（對于銥星N為66）個節點的網絡。假設網絡中大部分點對之間存在超過M條鏈路。網絡中共有taskNum個任務數，即taskNum對通信衛星[12]。將每個任務的帶寬按照相應的比例分配到M條路徑上。則網絡中共有taskNum*M條傳輸數據的路徑。記第i顆衛星到第j顆衛星的鏈路給整網帶來的代價為costij。cost由時延、跳數等一系列影響網絡中鏈路好壞的參數決定，后文將根據低軌衛星網絡的特點給出詳細的定義。BWi為傳輸第i個任務所需的帶寬。于是整網的任務模型圖如圖2所示。

圖2 多徑帶寬分配模型

2 基于多徑的低軌衛星網絡路由擁塞控制算法

2.1 一般情況

圖2中每一對下標相同的(s,d)節點對表示網絡中的一個任務，每個節點對之間均存在多條路徑，圖中為簡化模型，實際的網絡中各任務的多條路徑間可能存在中間節點重合或部分路徑重合的情況。整網鏈路數學表達式如式（1）所示：

∑i表示第i個任務。規模為S個節點的網絡中每一條路徑均可以用一個S*S的矩陣表示[13]。上式中的每一行中的矩陣表示每個任務選擇的前M條路徑，為了方便說明，這里的所有路徑均用相同的矩陣表示，實際的矩陣顯然是不同的。λ為每一路徑的權值，表示該路徑傳輸該任務(λ*100)%帶寬的數據量。λ滿足下式：

為了評價每一條路徑性能的好壞，我們給每一條路徑設置一個cost值。在實際衛星網絡中，評價一條路徑的好壞主要有兩個指標，時延和跳數。為了同時綜合考慮這兩個指標，將cost值定義如下：

α和β分別表示在該網絡中我們分別對路徑時延和跳數的重視程度。delayij為任務i的第j條路徑的時延，delaymin為第i個任務最短路徑的時延；hopij為任務i的第j條路徑的跳數，hopmin任務i最少跳數的路徑的跳數。分別計算每個任務的cost值，取每個任務前M條最小cost的路徑作為我們要傳輸數據的多徑路徑。

X為維度(S*S)*(N*M)的矩陣。令

λ為N*M維度的列向量。則多徑策略的整網路徑的流量方差為：

設μ為整網路徑帶寬的平均值，U=[μ μ…μ]T，U為S*S維列向量，則

這里ones(n,m)表示n行m列的元素全為1的矩陣。故

同時網絡所有鏈路傳輸帶寬的開銷為SUM=||X*λ||1=sum(X)*λ。sum(X)表示以矩陣X的每一列為對象，對一列內的數字求和。

這里的sum(X)為N*M維的行向量。

令fT=sum(X)，則SUM=fT*λ。

我們的目標是求出λ行向量使得整網鏈路傳輸帶寬方差VAR和整網鏈路傳輸帶寬TOTAL加和最小。即TATOL=VAR+SUM。

綜上所述，可轉化為一個二次規劃問題[14]：

其中λ為帶求系數向量；G'和fT在上文已給出詳細定義，均可由已經量表示；

每一行有M個如圖所示的連續的1；

由二次規劃得到的網絡中所有路徑權值向量λ。即可得到整網鏈路的傳輸帶寬。

2.2 特殊情況

隨著任務數的增多，可能出現某任務的可行路徑不足M條的情況，不滿足二次規劃的條件，需要進行以下處理。

對cost進行采樣，去除cost矩陣中值為Inf和NaN的元素；采樣路徑矩陣X，去除不存在路徑的列；對于Aeq，若存在極端情況，即某個任務一條可行路徑都不存在，則Aeq存在全零行，則需要去除該全零行，與此同時beq的列數減一。

實驗表明，以上情況只會在任務數超過一定數量時會出現。

2.3 策略分析

本策略提出一個綜合考慮時延和跳數的cost標準。取每個任務路徑時延最短的前M條路徑，綜合考慮跳數，得出該任務的多條路徑的cost值。對整網的每個任務均采用多徑路由，以最小化整網鏈路傳輸帶寬方差與整網鏈路傳輸帶寬開銷總和為目標，將問題轉化為二次規劃問題，最終得出每條路徑應分配的帶寬比例。既最大可能地均衡了整網的流量，避免了擁塞，也同時考慮到多條路徑的優劣，最小化整網鏈路傳輸帶寬的開銷。

3 實驗與分析

3.1 實驗步驟及參數設置

3.1.1 星座的建立

在STK中插入一顆衛星，以這顆星為母星建立6個軌道，每個軌道11顆星的Walker星座。設置衛星軌道高度780 km[15-16]，衛星軌道偏心率0度，軌道傾角86.4度，軌道近地點角度0度，升交點赤經0度，真近點角0度，星座相位因子為2，衛星軌道在赤道上的分布范圍為180度，星座可建立星間鏈路的最大距離為5000 km，仿真時長7200*12 s（24 h），仿真時間內的取樣時間步長60 s。

3.1.2 參數的設置

生成星座后，從STK中導出星座各節點的坐標，對整網節點進行可見性分析（衛星全向天線，兩星之間超過5000 km不可見），生成66*66的可見性矩陣。矩陣中1表示兩點可見，0表示不可見。顯然生成的可見性矩陣為對稱矩陣。

本實驗我們比較看重時延，令cost中的α=0.7，β=0.3。取多徑數M=4。對于每次仿真，依次設置5～30個節點的任務數。對于每個任務，生成N（N=5，6，…，29，30）個 0～1024 M的隨機傳輸帶寬和N個均為1024 M的固定帶寬。為網絡中的每條鏈路設置負載上限loadMax為500 M，超過上限認為鏈路超過負荷，每次仿真記錄整網鏈路的超負載數，并與以最小時延為目標的路由算法進行對比。

3.2 實驗結果與分析

路徑權值為該路徑傳輸所屬任務的帶寬比例。同一任務的路徑權值之和為1。生成使得整網鏈路代價最小的多徑路徑的權值λ。圖3和圖4分別為5個和30個任務帶寬均為1024 Mbps時的整網路徑的權值。

圖3 5個任務時整網路徑權值

圖4 30個任務時整網路徑權值

當只有5個任務時，路徑序號最大為20，此時說明每個任務均有大于4條的路徑。觀察同屬一個任務的路徑（例如1～4和9～12）的權值可發現，本算法得到的序號小的權值較大。可能原因是，我們是以時延最短為目標依次生成的路徑（時延越短，路徑序號越靠前），取前4條最短路徑，而這幾條路徑的跳數差別并不大，甚至是相同的。而我們最終的二次規劃優化目標的一次項是網絡所有傳輸數據的鏈路帶寬的開銷，所以同任務中序號靠前的路徑代價（cost）較小，是完全合理的。

隨著任務逐漸增多時，當任務數為30時，路徑序號最大為113，小于120。說明存在某個任務的路徑數不足4條，例如序號為108的路徑權值為1，即該路徑所屬任務只有一條路徑。這種情況本算法已按照2.2節所述的特殊情況處理方案進行了解決。

圖5和圖6分別為任務帶寬隨機和任務帶寬均為1024 Mbps情況下5到30個任務的整網鏈路超過500 Mbps鏈路數。

圖5 任務帶寬隨機情況下的超負載鏈路數

仿真結果顯示，隨著任務數的增多兩種負載情況下的單徑和多徑路由方案的超負載鏈路數都整體呈現遞增趨勢。但是優化后的多徑路由方案的整網超負載鏈路數明顯少于以時延為代價的單徑路由方案，并且隨著任務數的增多和任務負載的加重多徑路由方案的優勢愈加明顯。

圖6 任務帶寬均為1024 Mbp情況的超負載鏈路數

4 結束語

文中基于低軌衛星網絡的特點，針對衛星網絡中存在的負載非均衡問題，提出了一種基于多徑的低軌衛星網絡擁塞控制算法，并以典型的低軌衛星網絡銥星系統為背景進行了仿真，得出每個任務多條路徑傳輸帶寬的比例和整網的超負載鏈路數，并與以時延為目標的單徑路由方案對比，能夠有效地均衡負載，達到控制擁塞的目的。本算法適合多數點對間存在多徑路徑的網絡，且多徑數目越多，本算法的優越性愈顯著，具有擴展性，使用范圍廣的優點。