應用多智能體鏈路認知的低軌衛星網絡路由算法

雙煒

（山東航天電子技術研究所，山東煙臺 264670）

1 引言

低軌衛星網絡中的衛星沿著各自軌道高速運轉，使整個網絡的拓撲結構快速變換，這對網絡中的路由機制提出了特殊要求。此外，衛星軌道低，面臨著各種干擾，星際鏈路質量會發生不可預測的變化，也使通信網絡路由面臨著嚴重挑戰。

國內外對衛星網絡上的路由機制進行了一些研究，主要包括負載平衡路由技術、服務質量（QoS）路由技術和多服務路由技術。早期的衛星網絡路由算法［1-4］著眼于尋找一條連接源衛星和目的衛星的路由，自適應能力較差。隨著研究的深入，負載平衡問題逐漸受到重視［5］。然而，現有的分布式負載平衡路由技術，僅使用局部流量信息，不能反映出全局流量分布情況［6］。近年來，衛星網絡QoS得到重視并取得了一些成果［7］，不過其由于計算復雜度過高而無法在實際工程中應用，而且算法性能不高導致找到的鏈路不是最優的。文獻［8-10］中提出了衛星網絡多服務路由技術，但它的路由更新是以周期性為主，對網絡流量變化自適應能力不強，且要維護大量鏈路狀態信息，導致網絡開銷大。

為了克服上述衛星網絡路由技術的不足，本文提出了一種多智能體鏈路認知的低軌衛星路由算法，運用移動智能體技術［11］和認知理論［12］解決低軌衛星網絡的路由問題。該算法可通過多智能體對節點負載、鏈路投遞率和鏈路可用性等環境進行感知和推理，實時獲得網絡中星際鏈路的質量評價，且評價結果能實時地用于路由的自適應優化，可提高低軌衛星網絡通信的路由性能。

2 路由算法描述

2.1 基本思路

應用多智能體鏈路認知的低軌衛星網絡中衛星節點的路由更新算法體系結構，如圖1所示。每個衛星節點中部署靜止智能體、移動智能體和管理智能體。其中：靜止智能體可包括多個，如鏈路代價／位置智能體、路由表維護智能體等。移動智能體自治遷移探測路徑，一旦遷移入某個衛星節點，即成為該衛星節點的訪問智能體。訪問智能體通過與靜止智能體的信息交互來感知網絡鏈路，收集路由信息（包括星際鏈路代價、衛星位置等），更新路由表。而且，移動智能體以傳遞路由信息的方式通知路由表維護智能體更新路由表。管理智能體負責靜止智能體、移動智能體的創建，與后兩者共同完成監控星際鏈路的工作狀態、評估星際鏈路代價和更新路由條目的任務。

圖1 衛星節點的路由更新算法體系結構Fig.1 Satellite node routing updating algorithm architecture

低軌衛星網絡路由更新過程中，為了避免出現返回的移動智能體滯后問題，將移動智能體分簇，并限制單個移動智能體移動的最大范圍，讓簇內移動智能體完成簇內的鏈路感知任務，簇間移動智能體完成簇間的信息交接，以保證時延達到要求，同時也避免使用多個移動智能體。

2.2 衛星節點狀態感知

衛星節點狀態感知主要由移動智能體來完成。移動智能體感知獲取相關鏈路信道質量和衛星節點對業務流負載的處理能力等性能參數。根據移動智能體的成功投遞率，可獲取衛星節點的成功投遞率（間接反映鏈路上的通信干擾及其數據傳輸率）；通過感知衛星節點隊列緩存容量的占用率，可獲取衛星節點間鏈接的可用性。占用率反映本衛星節點的業務流強度，并反映衛星節點還可接納的分組容量。

在移動智能體遷移過程中，衛星節點j 完整地接收到另外一個鄰居衛星節點i 傳輸過來的信息幀，則認為一個幀發送、接收成功；如果接收到的幀發生校驗錯誤，或因為發生沖突造成幀接收不完整，則認為該幀丟失。移動智能體的成功投遞率為

式中：Ns（i，j）和Nr（i，j）分別為衛星節點i到相鄰衛星節點j發送和成功接收的數據幀數目。

設衛星節點i的隊列緩存總容量為C（i），當前緩存分組數為M（i），則其隊列緩存當前占用率為

2.3 星際鏈路狀態推理

通過移動智能體獲取衛星節點的成功投遞率，以及隊列的緩存容量占用率等基礎狀態信息。星際鏈路質量的良好程度與衛星節點的成功投遞率、衛星節點的隊列緩存空閑度均有關，如果只考慮成功投遞率，會出現網絡節點負載不均衡，使單個衛星節點負載過高而影響整體性能。為了達到網絡節點負載均衡的目的，即相關衛星節點的負載相等時會得到一個性能的極好值。設衛星節點i和衛星節點j的隊列緩存空閑度分別為Li和Lj，表示節點能繼續承擔的網絡負載能力大小，用來衡量衛星節點平衡程度。在節點隊列緩存空閑度之和Li＋Lj一定時，當Li＝Lj時，即負載均衡時取極大值。

定義衛星節點i與j 之間鏈路質量狀態的良好程度為

式中：α和β為預設的指數，取值范圍為［0，3］；Li＝1-ηi。

3 多智能體路由優化選擇

鏈路狀態推理過程中使用兩種移動智能體，即前向智能體和后向智能體。前向智能體使用高優先級隊列及時傳遞路由信息，每隔固定的時間，各衛星節點加載前向智能體，并派遣至網絡中；此后，前向智能體在衛星網絡中自治地遷移，通過與部署在所到達衛星節點中的靜止智能體交互，感知鏈路狀態。前向智能體到達目的衛星節點時自動轉換為后向智能體。后向智能體沿著前向智能體的路徑反向遷移。在各中間衛星節點，后向智能體與靜止智能體交互，向其傳遞路由信息。后向智能體根據獲取的路由信息更新衛星路由表。移動智能體工作過程如圖2所示。

路徑優化選擇原則為：源衛星節點和目的衛星節點分別為ns和nd，兩個節點之間的路徑集合定義為R，假如R ≠?，滿足條件為的路徑P 即為ns到nd所要選擇的路由路徑。該路徑上所有鏈路的質量良好程度之和為YP，ns和nd之間的任何一條路徑由網絡節點序列（n1，n2，…，nk）表示為式中：k為該路徑經過的中間節點總數；nm為該路徑上第m 個中間節點。

圖2 移動智能體工作過程示意Fig.2 Travelling agent work process

4 仿真試驗

4.1 仿真環境

以類似“銥”（Iridium）的衛星系統為研究對象，對本文算法進行仿真驗證。假設數據從源終端經過衛星系統傳輸到達目的終端，仿真環境設置如表1所示。

表1 仿真環境參數Table 1 Simulation environment parameters

以下對吞吐量、丟包率和端到端時延等指標，分別用本文提出的算法與傳統的自適應最短路徑路由算法［13］進行比較。

4.2 仿真結果與分析

1）吞吐量

圖3 為網絡吞吐量隨著終端數據率的變化情況。從圖3可以看出，當終端數據率較低時，本文算法和自適應最短路由算法基本一致，負載較高時，本文算法的吞吐量能提高7%～22%。

圖3 不同終端數據率下的吞吐量Fig.3 Thruput at different terminal data rates

2）丟包率

圖4為網絡不同終端數據率下的丟包率變化情況。從圖4可以看出，數據率較低時，兩種算法的丟包率都接近于0，但是隨著數據率的增加，本文算法丟包率明顯低于自適應最短路由算法。

圖4 不同終端數據率下的丟包率Fig.4 Packet loss rate at different terminal data rates

3）端到端時延

圖5為網絡不同負載下的端到端時延變化情況。從圖5可以看出，負載較低時，本文算法端到端時延明顯長于自適應最短路徑路由算法；但負載較高時，本文算法時延要短于自適應最短路徑路由算法。這是因為：在低負載情況下，本文算法的數據包穿越了較多的跳數，需要較長的時延，而自適應最短路徑路由算法基于優先級的選擇機制，偏向于最少跳數的路徑路由，需要較短時延；當負載較高時，自適應最短路徑路由算法性能急劇下降，更容易擁塞，導致長時延。因此，本文算法在高負載情況下具有優勢，更適用于流量變化劇烈的低軌移動通信網絡。

圖5 不同終端數據率下的端到端時延Fig.5 End to end delay at different terminal data rates

5 結束語

本文在低軌衛星網絡通信路由中引入了多智能體技術和認知理論，提出了一種路由算法，在自適應最小路徑的基礎上，通過感知星際鏈路投遞率和鏈路可用性等信息，反映衛星網絡中衛星節點處理負載的能力，根據衛星節點的感知信息對鏈路質量進行推理，獲得星際鏈路質量評價，再進行路由的優化選擇，從而提高網絡的吞吐量，實現負載均衡。本文提出的算法可以提高低軌衛星網絡路由的環境適應性，為我國低軌衛星通信網絡建設提供參考。

（References）

［1］Alagoz F，Korcak O，Jamalipour A.Exploring the routing strategies in next-generation satellite networks［J］.IEEE Journal on Wireless Communications，2007，14（3）：79-88

［2］Werner M，Delucchi C，Vogel H，et al.ATM-based routing in LEO／MEO satellite networks with intersatellite links［J］.IEEE Journal on Selected Areas in Communications，1997，15（1）：69-82

［3］Werner M，Berndl G，Edmaier B.Performance of optimized routing in LEO intersatellite link networks［C］／／Proceedings of IEEE 47th Vehicular Technology.New York：IEEE，1997：246-250

［4］Werner M.A dynamic routing concept for ATM-based satellite personal communication networks［J］.IEEE Journal on Selected Areas in Communications，1997，15（8）：1636-1648

［5］Taleb T，Jamalipour A，Kato N，et al.Computer and information sciences-ISCIS［M］.Verlag Berlin：Springer Berlin Heidelberg，2005：113-123

［6］Chatterjee P，Das N.Distributed computing and networking［M］.Verlag Berlin：Springer Berlin Heidel-berg，2008：332-338

［7］Molinaro A，De Rango F，Marano S，et al.A scalable framework for end-to-end QoS assurance in IP-oriented terrestrial-GEO satellite networks［J］.IEEE Communications Magazine，2005，43（4）：130-137

［8］Svigelj A，Mohorcic M，Kandus G，et al.Routing in ISL networks considering empirical IP traffic［J］.IEEE Journal on Selected Areas in Communications，2004，22（2）：261-272

［9］Mohorcic M，Svigelj A，Kandus G.Traffic class dependent routing in ISL networks［J］.IEEE Transactions on Aerospace and Electronic Systems，2004，40（4）：1160-1172

［10］Gorazd Kandus，Ales Svigelj，Mihael Mohorcic.The impact of different scheduling policies on traffic class dependent routing in intersatellite link networks［J］.International Journal of Satellite Communications and Networking，2004，22（5）：533-546

［11］Fünfrocken S，Mattern F.Kommunikation in verteilten systemen（KiVS）［M］.Verlag Berlin：Springer Berlin Heidelberg，1999：32-43

［12］Gelenbe E，Liu P，Szymanski B K，et al.Cognitive and self-selective routing for sensor networks ［J］.Computational Management Science，2011，8（3）：237-258

［13］Korcak O，Alagoz F，Jamalipour A.Priority-based adaptive shortest path routing for IP over satellite networks ［J］.International Journal of Communication Systems，2007，20（3）：313-333