基于負載均衡的導航時分網絡建鏈優化技術研究

賈衛松 王琦 李露銘 岳佳

(1 北京空間飛行器總體設計部，北京 100094)(2 北京跟蹤與通信技術研究所，北京 100094) (3 太原衛星發射中心技術部，太原 030027)

全球衛星導航系統具備利用地面站完成全球導航衛星管理的能力，利用星間鏈路通過境內衛星快速完成境外衛星的測控管理及運控信息注入。同時，全球衛星導航系統的戰略作用要求其在沒有地面站支持情況下實現長時間自主運行，在自主運行期間實現60天自主定軌與時間同步。因此導航星座中的衛星之間的鏈路數量應大于4條，從而為自主導航提供充足的高精度星間測量信息。根據短響應時間、高建鏈精度、長鏈路壽命、建鏈靈活的需求，全球衛星導航系統可基于相控陣天線周期輪詢構建星間鏈路，形成衛星連接拓撲隨時間變化的延遲容忍網絡。

由于衛星網絡的時分建鏈特性，導致衛星網絡路由規劃策略有別于地面網絡，需要考慮星間拓撲隨時間的演化，在路徑權值計算時增加建鏈時間因素。針對延遲容忍網絡(Delay Tolerant Network，DTN)網絡的路由問題，文獻[1]基于輪詢建鏈模式構建星間鏈路分配方案，提出星座內信息傳輸路徑選擇方法，文獻[2]等將接觸計劃建模為公平系數和平均時延的多目標優化問題，提出利用模擬退火算法求解建鏈規劃，均未考慮網絡流量的負載均衡。針對負載均衡，文獻[3]等提出了基于本地隊列的最早投遞和基于全網隊列的最早投遞路由算法，文獻[4]提出一種基于局部隊列的的最早投遞路由算法，但網絡節點間進行隊列信息的交互對于延遲容忍網絡而言時延較大，隊列信息容易過時。而且基于隊列狀態的負載均衡，需要在固定的建鏈拓撲規劃的基礎上動態計算路由，無法保證建鏈計劃相對于隨機的路由策略的最優化。

全球衛星導航系統星座網絡中衛星與衛星、衛星與地面站之間的可見性關系是周期性可預測的，因此導航衛星網絡的最優鏈路拓撲也是可預先規劃的。一旦拓撲確定，則基于特定約束的圖路由算法計算出的端到端最短路徑也是確定的[5-7]，進而提前獲得基于路徑集合的每個衛星節點的負載。本文在建鏈及路由規劃之初即考慮節點負載情況及業務非對稱特性，利用模擬退火全局最優搜索算法實現平均時延、最大時延和負載均衡多優化目標約束下的建鏈規劃求解，以接入能力、網絡時延、網絡容量為指標驗證時分網絡建鏈規劃方法對負載進行均衡的性能。

1 網絡模型及優化目標

由于衛星平臺和星間鏈路的約束，導航衛星裝配天線數量有限，而自主定軌與時間同步要求每顆衛星與盡量多的衛星建立星間鏈路，以獲得較好的幾何精度因子(Geometic Dilution of Precision, GDOP)值。當導航衛星只攜帶一臺相控陣收發信機時，在規劃的時隙內，每顆衛星至多建立一條半雙工星間鏈路。為保證衛星之間建鏈的公平性，即本星與其它每顆衛星建立星間鏈路的機會較為均等，將導航星座運行周期劃分為若干建鏈周期T，在每個建鏈周期T中，導航衛星重復的依次與不同的衛星建立鏈路，直至衛星可見性發生變化，形成典型的延遲容忍網絡，如圖1所示。

圖1 導航網絡輪詢建鏈Fig.1 Polling chain building of navigation network

在建鏈周期T內的星座鏈路狀態可視為有限狀態機，其中每個狀態代表衛星在某時隙內的鏈路配對關系。劃分建鏈周期T為n個時隙，對應狀態機中的n個狀態。令k∈(1,n)表示第k個時隙，基于時間代價和建鏈規劃構建導航衛星網絡的圖模型。

(1)pk,is,id表征第k個時隙衛星is和衛星id的建鏈關系，其中衛星is的下標s代表源衛星，衛星id的下標d代表目的衛星。

(2)ek,is,id表征第k個時隙衛星is和衛星id間的邊代價，若衛星is與衛星id在時隙k直接建鏈，則邊代價僅包含通信帶來的時間代價；若衛星is與衛星id在t個時隙后建立鏈接，則邊代價包含通信時間代價和延遲時間代價Δk；若衛星is與衛星id始終不建鏈，則邊代價為無窮大。

(3)ck,is,id表征第k個時隙衛星is和衛星id的最小代價。

為便于形象的描述圖模型，如圖2所示利用4個衛星節點建立導航衛星網絡的時變圖結構。

圖2 導航衛星網絡簡化模型Fig.2 Simplified model of navigation satellite network

定義lk,i1,id={(k+Δk1,i1,i2),(k+Δk2,i2,i3)…(k+Δkd-1,id-1,id)}表征在第k個時隙信息從源衛星節點i1出發到達目的衛星節點id的最短路徑，最短路徑依次經過衛星i1、i2、i3…id，則lk+Δk1,i2,id={(k+Δk2,i2,i3)…(k+Δkd-1,id-1,id)}且lk+Δk1,i2,id∈lk,i1,id。即若第k時隙從衛星i1到衛星id的最短路徑中包含衛星i2，則在第k+Δk1時隙從衛星i2出發到達id的最短路徑必然與時隙k從衛星i1到衛星id的最短路徑重合。因此，在一個建鏈周期內的任意時隙計算出的端到端最短路徑與其他時隙的端到端最短路徑彼此重合，端到端的信息傳遞最短路徑是唯一的。當在確定建鏈規劃下利用改進的Dijkstra算法[8]計算出唯一的最短路徑時，衛星節點對中轉信息的路由選擇策略也隨之確定，以確保網絡中的信息均能夠沿著最優路徑傳遞。所以在不考慮突發非對稱流量的前提下，對導航衛星網絡的路由負載均衡的過程就是對建鏈規劃的優化過程。

導航衛星網絡中承載著遙測業務、遙控業務、自主導航業務，其中遙測業務從非接入衛星通過網絡轉發至接入衛星下行至地面站，而遙控業務通過地面站上傳至接入衛星并轉發至非接入衛星，使導航衛星網絡呈現流量長期非對稱的特點。接入衛星在導航衛星網絡中作為星地的連接樞紐負載壓力較大，如圖3所示。

圖3 導航業務非對稱流量示意圖Fig.3 Asymmetric flow diagram of navigation service

設定M為接入衛星集合，在建鏈規劃時，應優先保證接入衛星作為起點或終點的端到端路徑時延最小，實現基于非對稱業務的負載均衡。此外，在端到端最短路徑集合L={l1,i1,id,l1,i2,id…ln,id-2,id,ln,id-1,id}中出現衛星節點i的次數越多，代表在信息流經衛星節點i的概率越大，可以提前通過建鏈重規劃調整最短路徑集，實現基于衛星節點的負載均衡。

2 基于負載均衡的建鏈規劃方法

基于時變圖的導航衛星網絡建鏈規劃問題，實質上是基于多優化目標的全局最優解搜索問題。首先設定目標函數并計算最優值，通過持續調整建鏈規劃，利用模擬退火算法求解近似全局最優解，尋優過程的關鍵步驟在以下章節中進行詳細說明。

2.1 模擬退火優化

若采用遺傳算法求解，則影響網絡鏈路路徑的基因僅包含時間和節點流量相關的因素，相較而言利用模擬退火算法對最優路徑的求解更為有效。優化步驟如下。

(1)設置初始溫度τ=1，形成初始建鏈規劃及評價函數值f(xold)；

(2)通過調整產生新的建鏈規劃；

(3)計算得到新的評價函數值f(xnew)；

(4)計算增量Δf=f(xnew)-f(xold)；

(6)若連續λ次調整未被接受，則結束優化，若調整次數小于λ則跳轉至步驟2；

(7)τ=τ×μ，當τ>τmin時，轉至步驟2。

模擬退火中溫度下降的速度μ和調整次數λ取決于建鏈優化過程中評價函數值變化速度，若評價函數值能夠快速收斂，則μ和λ可以設置為較小值。

2.2 確定評價函數

為達到負載均衡的目的，首先需要考慮衛星節點的存儲負載，減小各個衛星節點的存儲區利用率的差異；此外，為適應導航衛星網絡流量長期非對稱的特點，在評價函數中引入接入衛星上行與下行端到端時延，使額外承載著星地流量的接入衛星獲得更高的建鏈優先權；同時，以平均端到端時延和最大端到端時延保證網絡整體性能，滿足自主導航信息的實時交互要求。綜合以上因素，定義求解最優建鏈規劃的目標函數為f(x)=αDAverage+βDMax+γDAeverageUp+δDAverageDown+εEMeanSquare。其中DAverage為平均端到端時延，DMax表示最大端到端時延，DAeverageUp表示接入衛星上行平均端到端時延，DAverageDown表示接入衛星下行平均端到端時延，EMeanSquare表示在最優路徑集合中衛星節點負載均方差，其中衛星節點負載利用最優路徑集合中節點出現次數表征。以α、β、γ、δ、ε為各指標的調節因子，當非對稱業務流量較大時，提高γ和δ的值，當非對稱業務流量較小時，則降低γ和δ的值。建鏈規劃問題從而轉化為尋找f(x)全局最小值的問題。

2.3 最短路徑計算

本文通過改進Dijkstra算法完成時變網絡圖中時隙k源節點is到任意目的節點id的端到端最短路徑的計算，算法步驟如下：

(1)設定V為星座網絡節點集合，Q為最短路徑節點集合，Q集合中的元素代表某衛星是否已經被納入至最短路徑集合L中，P=V-Q為尚未納入至最短路徑集合L的節點集合。

(2)初始化最短路徑節點集合Q和最短路徑集合L，使其包含源節點is，初始化ck,is,id為∞。

(3)在P中找到與is距離值最短的衛星節點iu，并將iu加入至Q和L。

(4)對L中目的衛星節點id∈P的路徑進行松弛，若ck,is,id>(ck,is,iu+ek+Δk,iu,id)，則將節點iu加入至最短路徑集合中的最短路徑lk,is,id，并修改最短路徑距離值ck,is,id。

(5)重復步驟(3)和(4)，所有衛星節點均被納入最短路徑節點集合Q，即Q=V。

與衛星節點始終可見的持續鏈路網絡拓撲Dijkstra算法不同，由于時變圖的時間演化特性，在對非最優路徑進行松弛的時候，中間節點iu到目的衛星id的邊代價應為ek+Δk,iu,id而非ek,iu,id，其中Δk=ck,is,iu代表在Δk個時隙后信息地帶衛星iu，并準備從衛星iu出發。

2.4 調整建鏈規劃

當目標函數解未達到最優值時，需要對建鏈規劃進行微量調整，本文采用隨機鏈路交換方法，步驟如下：

(1)隨機產生時隙k，衛星1、衛星2；

(2)根據原建鏈規劃獲取衛星1指向的衛星3，衛星2指向的衛星4；

(3)若衛星3與衛星4為不同衛星，則對衛星1、衛星2、衛星3和衛星4進行可見性匹配，若不能產生與原建鏈規劃存在差異的鏈路，則轉至步驟(1)繼續產生隨機值。

3 性能仿真

3.1 仿真場景參數設置

導航衛星網絡采用24MEO+3GEO+3IGSO的星座，其中MEO構型選擇walker24/3/1，每顆衛星攜帶一條星間鏈路。基于網絡參數構建STK仿真場景，獲得星間可見性，形成建鏈規劃方案。基于負載均衡的建鏈規劃方法形成建鏈配置方案A，以最小平均端到端時延作為優化目標形成建鏈配置方案B。利用Matlab搭建導航衛星網絡節點傳輸仿真平臺，通過仿真結果比較不同方案的網絡時延、容量和接入能力。表1列出了導航衛星星座網絡模型參數。

表1 導航衛星星座網絡參數

3.2 優化結果分析

對建鏈規劃的負載均衡可以從兩方面進行評價：①在確定的網絡負載下，評估網絡的最大時延、衛星節點緩存占用及平均時延；②在網絡節點參數不變的情況下，不斷提高接入流量，評估網絡的最大接入能力。

1)基于確定網絡負載的評估

設置導航衛星仿真模型參數如表2所示。設置基于負載均衡的建鏈規劃方法中的評價函數指標權重調節因子如表3所示。

在流量非對稱的導航衛星網絡的管理控制場景中，利用基于負載均衡的建鏈規劃方法形成的建鏈配置方案A，僅以平均端到端時延作為優化目標形成建鏈規劃方案B，如圖4所示。

表2 導航衛星網絡傳輸仿真參數

表3 評價函數指標權重調節因子

圖4 基于確定網絡負載的評估結果Fig.4 Evaluation results based on determining network load

分析仿真結果發現，方案A中各衛星節點的端到端最大時延、節點緩存占用率優于方案B，端到端最大時延出現在方案B中的第24號衛星，衛星節點最大負載出現在方案B的第22號衛星。方案A與方案B的平均端到端時延差值小于1，性能基本一致。這是因為方案B是以平均端到端時延作為優化目標的，而方案A兼顧了其他指標。

2)基于接入能力的評估

按表2設置導航衛星仿真模型參數，并調整其中遙控業務注入速率。比較基于表2調節因子的負載均衡方案A以及基于平均時延優化的最大遙控業務注入速率，見圖5。

圖5 基于最大接入能力的評估結果Fig.5 Evaluation results based on maximum access capability

圖5中可以看出，基于負載均衡的建鏈規劃網絡中遙控業務的接入能力為25幀每時隙，若對基于平均時延優化的建鏈規劃網絡注入同樣的負荷，則會在4號、5號、10號、14號、17號、23號衛星節點發生丟幀現象。基于平均時延優化的建鏈規劃網絡的最大接入能力為16幀每時隙，遠低于基于負載均衡的方案。

綜上所述，基于負載均衡的DTN網絡建鏈規劃方案在不影響平均端到端時延的基礎上有效實現導航衛星網絡衛星節點間的負載的均衡。

4 結束語

本文建立導航星座時分復用網絡模型，根據固定建鏈拓撲下最優路由路徑的唯一性，以及導航衛星網絡業務信息路徑非對稱特點，提出在拓撲建鏈規劃時提高網絡路由負載均衡性能的方法。仿真結果表明，基于負載均衡的拓撲建鏈優化方法優于以平均端到端時延為優化目標的建鏈方法，能夠實現業務信息在各衛星節點間高效均衡的傳輸，為全球導航系統星間鏈路的鏈路規劃提供支持。下一步研究將在建鏈規劃過程中考慮更多的影響因素。例如，衛星可見性變化會導致建鏈規劃切換，信息傳輸過程中會發生最優路徑的變化，需要保證切換過程中網絡時延性能不會下降。此外，自主導航需要導航衛星之間建立更多的測距鏈路，且具有較好的幾何精度因子；在選擇地面接入節點時，需要考慮衛星仰角、星地建鏈時長以及地面接入衛星數量對建鏈規劃帶來的影響。