衛星網絡動態資源圖多QoS約束路由算法

梁超，楊力，潘成勝，，戚耀文

1．大連大學 通信與網絡重點實驗室，大連 116622

2．南京理工大學 自動化學院，南京 210094

近年來，全球高中低軌衛星通信，尤其是巨型低軌星座系統進入井噴式發展階段［1］，衛星的計算能力、存儲能力也逐漸變強，同時，基于衛星網絡的應用也越來越多并朝著多樣化的方向發展。路由技術作為衛星網絡中的關鍵技術仍面臨很多問題，例如高動態、高時延、局部擁塞等。因此，設計高效可靠的路由算法至關重要。

文獻［2］指出，路由協議有許多是為特定網絡設計的，呈現出不同的特性，因此，在研究路由算法時，需要考慮不同網絡環境所產生的影響。當前衛星網絡路由主要基于2種網絡模型，一種是基于離散時間片的虛擬拓撲模型，文獻［3］提出基于時間片分割的拓撲生成優化算法得到抗毀性良好的拓撲結構，但當有大量衛星時，這種模式不可擴展；另一種是基于虛擬節點的模型，該機制屏蔽了網絡的動態性，同時簡化了路由機制。基于虛擬節點的路由策略雖然能夠規避衛星網絡的高動態性問題，但這種方式忽略了虛擬節點與物理節點切換時所帶來的路徑失效問題。

路由問題是一個多目標優化問題，在網絡性能優化方面，主要是以端到端時延、網絡吞吐量和數據包交付成功率等指標為優化目標，研究者針對不同的優化目標提出了大量可行方案。文獻［4］提出了一種新穎的時間網絡模型來描繪大規模小型衛星網絡的時變拓撲并提出了一種高效的基于網格的最短路徑路由算法。文獻［5］提出了一種基于計劃拓撲的延遲約束路由機制算法，該算法基于預測的拓撲建立路由表并以時延為約束條件進行路由計算。文獻［6］提出了一種基于服務概率和有限副本的算法，基于轉發概率和衛星剩余緩存選擇路徑。文獻［7］提出了一種基于星間鏈路狀態信息的路由算法，衛星根據與相鄰衛星的鏈路狀態信息和網絡拓撲為每一跳做出路由決策。文獻［8］提出了一個聯合的時空路由算法框架，設計了一種多路徑路由算法。文獻［9］提出了一種基于網絡編碼的多徑協作路由協議，該方案采用非停止等待機制完成數據包的分批次傳輸。能量感知路由算法從能量的角度“驗證”和“確認”節點的有效性，并基于此設計了一種解決路由無效問題并繞過敏感節點的路由方案［10-11］。以上方案在縮短網絡傳輸時延，降低網絡控制開銷，提高網絡性能方面發揮了重要作用，但在流量突發情況下，網絡會發生擁塞，難以保障通信服務質量（Quality of Service，QoS）。

為了緩解網絡擁塞，文獻［12］提出了一種隊列調度的虛擬拓撲延遲容忍網絡路由算法，該算法能夠較好地平衡空間通信網絡拓撲更新和資源消耗的影響。文獻［13］針對低軌衛星網絡，提出了基于分段路由的負載均衡路由算法，基于擁塞指數在輕載區和重載區采用不同的方案計算路由。以上方案在負載均衡方面均體現了較好的性能，但當網絡負載很高時在時延方面略有劣勢。文獻［14］提出了一種基于存儲時間聚合圖的多流最大化路由方案以保證任務的QoS。采用蟻群算法求解路由，并將QoS約束應用于改進啟發式算法，能夠滿足網絡業務的QoS需求［15-16］，文獻［17］討論了蟻群算法在路由問題中的應用，并針對應用中的問題提出了3種改進策略。上述算法均在某些方面保證了通信的QoS需求，但忽略了網絡動態切換帶來的影響。

針對拓撲變化導致的網絡更新期間可用路徑失效問題，文獻［18］提出的適應拓撲變化的擁塞最小化網絡更新策略降低了網絡擁塞。文獻［19］明確指出了低軌衛星的切換問題，分析了衛星運行所引起的鏈路切換對路由計算的影響，表明接入衛星的頻繁切換，必然導致原有轉發路徑失效，繼續在其上傳輸業務時將產生嚴重的數據包丟失現象，此時需要重新計算衛星通信網絡的拓撲和路由。因此，將路由計算和衛星鏈路切換結合起來可以降低重路由所帶來的開銷。

綜上所述，雖然研究者為提高衛星網絡QoS、緩解網絡擁塞做了大量研究，但在路由計算時均未考慮衛星動態切換造成的路徑失效問題。因此，本文基于虛擬節點網絡拓撲，構建動態資源圖，提出了一種虛擬節點動態資源圖多QoS約束路由算法（Multi-QoS Constraints Routing Algorithm based on Dynamic Resource Graph of Virtual Nodes，DRGVN-QR），從而達到緩解網絡擁塞，提高網絡QoS的目的。首先，建立虛擬節點動態資源圖和多目標優化模型，該模型同時考慮了節點的切換狀態、緩存以及鏈路的剩余帶寬、時延等信息；其次，利用蟻群算法建立多QoS約束計算模型求解目標函數，為每個連接請求找到一段時間內符合QoS約束的多條路徑，并討論了信息素揮發系數的取值問題；最后，設計一種冪數加權公式選出一段時間范圍內的最優路徑。

1 系統模型

1.1 軟件定義衛星網絡模型

將軟件定義網絡（Software Defined Network，SDN）應用于衛星網絡可以有效緩解星上資源有限、管理困難的問題。因此，本文將SDN應用于低軌（Low Earth Orbit，LEO）衛星網絡，SDN控制器部署在3顆地球靜止軌道（Geostationary Earth Orbit，GEO）衛星和對應的地面站，位于GEO的控制器負責收集其覆蓋區域的LEO衛星節點的狀態信息，3個控制器協同工作獲取全局視圖，地面控制器與GEO控制器進行信息交互并負責路由計算，圖1展示了由衛星和地球站組成系統架構，GEO層和地面站作為控制層，LEO層作為數據轉發層。

本文采用類銥星星座［20］作為衛星網絡模型，假設星座中共有N個軌道平面，每個軌道M顆衛星，則衛星集群可表示為S=｛1，2…，n，n+1，…，2n，…，（m－1）n+1，…，mn｝，其中n代表軌道編號，m表示衛星在軌道中的編號。星座的網絡拓撲由星間鏈路（Inter-Satellite Link，ISL）構成，除了位于反向縫的衛星外，每顆衛星均有4個ISL，即2個軌內ISL和2個軌間ISL；而位于反向縫的衛星只有1個軌間ISL，因此只有3個ISL。

圖1 系統架構Fig. 1 System architecture

軌間ISLs長度的計算公式為

式中：R為衛星的軌道半徑。

軌內ISLs長度Lh的計算公式為

式中：lat為指軌內ISLs所在的緯度。

為了適應LEO衛星網絡拓撲結構的動態變化，本文采用基于虛擬節點的網絡拓撲方式，根據LEO衛星網絡的初始狀態，將地球表面根據衛星星座進行區域劃分，每個區域對應一顆衛星，然后給每個區域分配一個邏輯地址〈o，s〉，o代表衛星軌道編號，s代表軌道上的衛星編號，然后根據邏輯地址生成網絡拓撲，路由計算總是基于此拓撲進行。

1.2 虛擬節點動態資源圖模型

基于虛擬節點的網絡拓撲邏輯地址雖然固定，但物理節點時刻變化，在某一時刻邏輯節點與物理節點的對應關系需要進行切換，這會導致虛擬節點和邏輯鏈路出現短暫甚至長時間的中斷現象，如果在切換時刻進行數據轉發請求將無法按規劃路徑到達，并且切換后的虛擬節點資源情況變化很大，如果仍按原路徑進行轉發將無法保障QoS需求。虛擬節點與物理節點的切換對轉發過程的影響如圖2所示，在圖2（a）中，t時刻源站向目的站發送業務請求，如果按t時刻計算路由，虛擬節點路徑為A→B→C，對應的物理節點為1→2→3，在圖2（b）中，t+1時刻業務到達節點B即2號衛星，此時虛擬節點與物理節點發生切換，虛擬節點C對應衛星2，此時如果仍進行B→C的轉發，那么將無法到達目的站，而可以由2號衛星直接交付給目的站。

因此，本文利用SDN控制器收集網絡的所有狀態信息，然后將節點切換時間和動態變化的資源情況刻畫在各虛擬節點和邏輯鏈路上，其中虛擬節點與物理節點的切換時間可預測，同時假設節點和鏈路的其他資源信息也已經通過預測獲得。基于此構建出虛擬節點動態資源圖（Dynamic Resource Graph of Virtual Nodes，DRGVN），即

圖2 節點切換過程Fig. 2 Node switching process

式中：V表示節點 集合；E表示星 間鏈路；T表示時間范圍；Sv(t)表示虛擬節點v與物理節點的切換狀態；Bu，v(t)表示鏈路(u，v)剩余帶寬；Dpu，v(t)表示鏈路(u，v)的傳輸時延；Bufv表示節點v的緩存大小；Uv(t)表示節點v在t時刻的緩存占用情況。虛擬節點動態資源圖采用表1的形式存儲。

表1 動態資源信息Table 1 Dynamic resource information

1.3 路徑代價優化模型

本節利用上文中建立的虛擬節點動態資源圖約束路徑的選取并計算路徑代價。路徑代價的計算主要考慮3個指標，即跳數、傳播時延和總端到端時延［21］。本文考慮衛星網絡的高動態性因素和數據包在逐跳轉發過程中易發生不可預知的情況，在保證鏈路代價優的前提下應盡量選擇節點數量少的路徑，因此路徑代價通過端到端時延和跳數共同來計算，即

式中：Ps，d(t)表 示t時 刻 源 節 點s到目的節點d的路徑代價；ω1、ω2分別表示鏈路代價和路徑包含節點數的權值；hs，d表示路徑所包含的節點跳數；Ii，j(t)表 示 節 點i到 節 點j的 單 鏈 路 代 價，本 文 僅考 慮 傳 輸 時 延與 排 隊 時 延對 鏈 路代價的影響，即

式 中：Li，j表 示 路 徑 長 度；c表 示 電 磁 波 傳 播 速 度；Qi，j表示隊列 長度；rout表示 出隊速度。

本文用fi，j(t)表示t時刻節點i到節點j的流量，虛擬節點v與物理節點的切換狀態Sv(t)=1時表示未切換，Sv(t)=0時表示發生切換。在時延、切換狀態、帶寬和緩存的約束下，設計了多QoS目標優化模型，該模型的目標是為每個源到目的的連接請求尋找一條路徑代價最小的路徑。因此，建立優化模型的目標函數為

約束條件

為約束（11）表示t時刻鏈路的可行流量需小于鏈路的剩余帶寬，約束（12）表示節點實際緩存需小于節點最大緩存；約束（13）表示t時刻節點不應處于切換狀態。上述模型是一個多目標優化問題，這通常是一個NP難問題，第2節將對該模型進行求解。

2 算法設計

蟻群優化（Ant Colony Optimization， ACO）被用于為每個連接請求尋找最佳路徑，因為ACO不僅具有獲得組合優化問題最優解的強大能力，而且已經成功地應用于解決LEO衛星網絡中的路由問題。因此，本文使用ACO算法求解1.3節的目標函數，求出一段時間內多個時刻的最優路徑集合，最后選出該時段路徑質量最高的路徑。

2.1 基于動態資源圖的節點集優化

根據優化目標模型約束，不符合約束條件的節點和鏈路不能作為備選節點，因此本文基于DRGVN實現一種縮小螞蟻下一步節點集allowedk的算法，提前去除負載過重的鏈路實現負載均衡并提高算法收斂速度。具體實現方法如下：

首先，基于虛擬節點的邏輯拓撲圖生成拓撲矩陣G

式中：aij表示節點i和節點j之間的距離，當aij=?1時，表示節點i和節點j之間無法建立直接的ISL；節點邏輯地址的求解為然后，根據拓撲矩陣判斷鏈路聯通狀態，根據DRGVN判斷節點切換狀態和QoS約束條件，將滿足條件的節點加入allowedk集合中。其中節點i到節點j的QoS約束為

式中：Imax表示單條鏈路所允許的最大代價。

優化allowedk集合的具體實現如算法1所示。

2.2 動態路徑選取

為使算法選取的路徑在滿足QoS約束的基礎上實現路徑代價最小的優化目標，基于文獻［17］的蟻群算法數學模型，本文將鏈路的剩余帶寬Bi，j(t)和鏈路代價Ii，j(t)作為計算選擇下一步節點概率的2個約束條件，則螞蟻k由當前節點i轉移到下一節點j的概率對應的啟發函數為

算法1 優化allowedk集合算法

式中：ηij表示節點i到節點j鏈路的能見度；λ1、λ2、λ3分別表示剩余帶寬、鏈路代價和節點剩余緩存的重要程度；Tij代表節點i到節點j邊上的信息素值；α表示信息素的相對權重；β表示能見度的相對重要性。

當所有螞蟻都完成了一次迭代，需要更新路徑上的信息素值，信息素更新公式為

式中：ρ為 信息素 揮發系數；1?ρ為信 息素持 久程度表示螞蟻k從節點i到節點j留下的信息素增量；P為一個固定值，表示一只螞蟻一次尋路的信息素總量；Lk表示螞蟻k經過的路徑長度。

2.3 基于時延系數的信息素揮發速度選取

由式（21）可知，螞蟻k未經過的路徑上的信息素以一定速度ρ減少。ρ的數值如果太大，信息素揮發速度過快，導致算法收斂速度慢，路徑選擇的時效性較低；ρ的數值如果太小，信息素揮發速度慢，容易過早陷入停滯狀態，無法選出最優路徑。因此，根據路由的時延QoS需求選擇合適的ρ值，有利于提升路徑質量。

傳統蟻群算法的ρ值是一個固定值，不能根據當前網絡狀態進行調節，無法保證路徑質量。本文基于軟件定義衛星網絡架構，利用SDN控制器實時動態調整ρ值，使算法選擇出的路徑時刻處于較優狀態。設置Tmax代表路徑上信息素的閾值，Dmax代表時延閾值，則ρ的取值為

式中：Tsd代表算法選出的最優路徑的信息素值；Dsd代表源節點到目的節點的時延；s1、s2、s3、s4為常數閾值，并滿足不等式（25）。當路徑上的信息素Dmax時，ρ應該增大，在保證一定收斂速度的同時可以緩解網絡擁塞；當路徑上的信息素>Tmax但時延Tmax且時延>Dmax時，ρ應該選取較大值，因為此時已經接近擁塞邊緣，需要快速選取新路徑。

2.4 DRGVN-QR算法步驟

為了將衛星網絡的動態變化考慮在路徑選擇過程中，本文綜合考慮一段時間范圍內的網絡狀態及所選路徑在該時間范圍內的代價，從而選出全局最優路徑。因此，本文基于DRGVN，采用ACO算法并發在每一個時間間隔內選擇出一條路徑放入Pareto集合中，然后對Pareto集合中路徑的代價在時間T范圍內進行冪數加權求和，最終選出該時間范圍內質量最優的路徑。該方案充分利用網絡的狀態和資源情況進行路徑規劃，能夠有效緩解局部擁塞，提高網絡整體的服務質量。

路徑代價的冪數加權求和公式為

DRGVN-QR算法的實現流程如圖3所示。具體實現流程為：

輸入動態資源圖DRGVN={V，E，T，Sv(t)，Bu，v(t)，Dpu，v(t)，Bufv，Uv(t)}，隨機生成的源目的節點對，給定的業務請求M。

輸出源節點s到目的節點d的路徑path（M），滿足M的傳輸需求且具有多QoS保障。

步驟1根據衛星網絡虛擬節點生成拓撲矩陣G，初 始 化 參 數：α、β、ω1、ω2、λ1、λ2、μ、Tmax、Dmax、Bmax等。

步驟2將代表不同時刻的螞蟻kt放到源節點，并將源節點標記為已經訪問。

步驟3使用算法1計算優化后的下一步節點集allowedkt。

圖3 算法流程圖Fig. 3 Algorithm process

步驟4螞蟻根據式（18）計算出的概率在allowedk中選擇下一個節點，并將節點標記為已經訪問。

步驟5判斷當前節點，如果不是目的節點則繼續執行步驟6，如果是目的節點則執行步驟8。

步驟6判斷allowedk集合是否為空，如果為空則該螞蟻尋路失敗返回執行步驟2，如果不為空則執行步驟4。

步驟7SDN控制器根據式（24）選取ρ值，然后使用式（21）更新信息素。

步驟8迭代結束后，將路徑放入Pareto集合。

步驟9使用式（26）對Pareto集合中路徑進行質量計算，輸出最優解。

3 仿真實驗

3.1 仿真場景及參數設置

本文使用STK進行類銥星星座仿真，星座共有6個軌道平面，每個軌道11顆衛星，共66顆衛星均勻分布，軌道高度780 km，軌道傾角86.4°。使用MATLAB進行算法仿真，算法詳細步驟見2.4節。

文獻［22］對蟻群的算法重要參數進行了大量實驗分析，確定了使算法收斂速度和求解性能均達到最優的參數，本文選取α=1、β=5。螞蟻數量一般與問題規模一致，一般認為節點數量的2/3是最優螞蟻數量，因此選取m=40。信息素總量在500以內時，問題規模對于信息素總量的選擇影響較小，本文選取信息素總量P=20。以上參數的設置能夠保證算法性能最優。

設置單條路徑信息素最大值Tmax=200，單條鏈路最大時延Dmax=1 000 ms，根據本文的優化目標，確定各性能指標的重要程度，選取ω1=0.8，ω2=0.2；λ1=0.2，λ2=0.4，λ3=0.4。仿真過程模擬連續發包1 500次，鏈路可用帶寬Bmax=200 Mbps［23］，每次隨機選擇源和目的節點對。并 通 過 實 驗 對 幾 組s1、s2、s3、s4取 值 進 行 驗證，其網絡平均吞吐量如圖4示。

圖4 網絡平均吞吐量Fig. 4 Average throughout of network

實驗結果表明當s1=s2=s3=s4=0.5時，仿真后期網絡吞吐量出現大幅度波動，因為ρ值固定，算法初期表現較好，但后期沒有及時調整路徑信息素濃度，出現了緩存隊列排隊較長的現象，吞吐量無法提升。當s1=0.1、s2=0.3、s3=0.5、s4=0.7時，網絡吞吐量整體上明顯提高，且比較穩定，但仍有輕微波動，當s1=0.2、s2=0.4、s3=0.6、s4=0.8時，整個網絡的吞吐量達到較優狀態，且能夠保持穩定。根據上述現象，本文選取s1=0.2、s2=0.4、s3=0.6、s4=0.8。

3.2 仿真結果分析

本文在相同實驗環境下，將所提出的算法與經典Dijkstra算法和基于多QoS約束的蟻群優化路由算法（QoS-ACO）［16］，以及基于SDN的最短路徑算法（SDN-SPF）［20］進行比較。

算法的平均求解時間如圖5所示，該指標體現了算法的收斂性。以Dijkstra算法的表現為基準，縱坐標表示所對比算法的求解時間與Dijkstra算法的求解時間的比值。從圖中可以看出，SDN-SPF算法在仿真初期求解時間相對較快，但隨著仿真的進行，為了緩解網絡擁塞該算法的求解時間逐漸增大。本文DRGVN-QR算法在仿真初期就獲得了較好的收斂速度，隨著仿真的進行，由于本文算法動態調整信息素揮發系數，求解時間出現波動現象，但整體上優于其他算法。因為加入了優化allowedk的算法，DRGVN-QR算法的收斂速度有所提升。

圖5 平均求解時間Fig. 5 Average solving time

算法的平均端到端時延如圖6所示。在仿真前半段，時延變化平緩，幾種算法的時延差別不明顯。但隨著數據包的不斷發送，本文所提DRGVN-QR算法的平均時延最低，與其他算法相比網絡端到端時延最大降低了7.8%，且明顯優于其他算法。這是因為本文在ACO的啟發函數中引入了時延作為重要參考因素，并且揮發系數ρ的值隨著網絡的變化而動態改變。在選取路徑時，本文考慮了一個時間段內的路徑代價從而緩解網絡擁塞，因此所選路徑具有較好的時延性能和帶寬優勢。

算法的平均丟包率如圖7所示，可以看出，隨著請求數量的增加網絡負載逐漸變大，時延和丟包率也隨之增大，與其他算法相比本文所提DRGVN-QR算法的丟包率最低，最大降低了8.6%，且增長趨勢越來越小，最終能夠保持一個相對穩定狀態。這是因為本文避免了路徑切換帶來的丟包問題，時延降低的同時也能降低丟包率。

算法的平均時延抖動如圖8所示。可以看出，在仿真前期，各算法的時延抖動沒有太大差距，但隨著請求數量的增加，其他算法的平均時延抖動明顯增加，DRGVN-QR算法的平均時延抖動整體低于其他算法，最大降低了9.2%，且這種優勢愈加明顯，最后逐漸趨于穩定。仿真表明，DRGVN-QR算法在網絡平均時延抖動方面表現良好，能夠有效地提升了網絡數據傳輸的穩定性。

綜合考慮以上因素，本文算法通過與其他算法進行對比，體現了良好的性能。

圖6 平均端到端時延Fig. 6 Average end-to-end delay

圖7 平均丟包率Fig. 7 Average packet loss rate

圖8 平均時延抖動Fig. 8 Average delay jitter

4 結 論

本文針對衛星網絡特性，首先，建立一種虛擬節點動態資源圖模型刻畫節點切換和資源的動態性，基于此建立最小路徑代價多目標優化模型，該模型同時考慮了節點的切換狀態、緩存以及鏈路的剩余帶寬、時延等信息。其次，利用蟻群算法求解滿足多QoS約束的最小代價路徑集合，并討論蟻群算法信息素揮發系數的選取問題。最后，設計一種冪指加權公式選出最優路徑，保證數據傳輸的可靠性。通過仿真驗證：

1） 在銥星星座仿真環境中，本文所提DRGVN-QR算 法 與SDN-SPF和QoS-ACO算法相比，網絡端到端時延最大降低了7.8%。

2） 同時平均丟包率最大降低了8.6%，提高了交付成功率。

3） 平均時延抖動最大降低了9.2%，網絡穩定性得到顯著提升。