雙煒

（山東航天電子技術(shù)研究所，山東煙臺(tái) 264670）

1 引言

低軌衛(wèi)星網(wǎng)絡(luò)中的衛(wèi)星沿著各自軌道高速運(yùn)轉(zhuǎn)，使整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)快速變換，這對(duì)網(wǎng)絡(luò)中的路由機(jī)制提出了特殊要求。此外，衛(wèi)星軌道低，面臨著各種干擾，星際鏈路質(zhì)量會(huì)發(fā)生不可預(yù)測(cè)的變化，也使通信網(wǎng)絡(luò)路由面臨著嚴(yán)重挑戰(zhàn)。

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

為了克服上述衛(wèi)星網(wǎng)絡(luò)路由技術(shù)的不足，本文提出了一種多智能體鏈路認(rèn)知的低軌衛(wèi)星路由算法，運(yùn)用移動(dòng)智能體技術(shù)［11］和認(rèn)知理論［12］解決低軌衛(wèi)星網(wǎng)絡(luò)的路由問題。該算法可通過多智能體對(duì)節(jié)點(diǎn)負(fù)載、鏈路投遞率和鏈路可用性等環(huán)境進(jìn)行感知和推理，實(shí)時(shí)獲得網(wǎng)絡(luò)中星際鏈路的質(zhì)量評(píng)價(jià)，且評(píng)價(jià)結(jié)果能實(shí)時(shí)地用于路由的自適應(yīng)優(yōu)化，可提高低軌衛(wèi)星網(wǎng)絡(luò)通信的路由性能。

2 路由算法描述

2.1 基本思路

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

圖1 衛(wèi)星節(jié)點(diǎn)的路由更新算法體系結(jié)構(gòu)Fig.1 Satellite node routing updating algorithm architecture

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

2.2 衛(wèi)星節(jié)點(diǎn)狀態(tài)感知

衛(wèi)星節(jié)點(diǎn)狀態(tài)感知主要由移動(dòng)智能體來完成。移動(dòng)智能體感知獲取相關(guān)鏈路信道質(zhì)量和衛(wèi)星節(jié)點(diǎn)對(duì)業(yè)務(wù)流負(fù)載的處理能力等性能參數(shù)。根據(jù)移動(dòng)智能體的成功投遞率，可獲取衛(wèi)星節(jié)點(diǎn)的成功投遞率（間接反映鏈路上的通信干擾及其數(shù)據(jù)傳輸率）；通過感知衛(wèi)星節(jié)點(diǎn)隊(duì)列緩存容量的占用率，可獲取衛(wèi)星節(jié)點(diǎn)間鏈接的可用性。占用率反映本衛(wèi)星節(jié)點(diǎn)的業(yè)務(wù)流強(qiáng)度，并反映衛(wèi)星節(jié)點(diǎn)還可接納的分組容量。

在移動(dòng)智能體遷移過程中，衛(wèi)星節(jié)點(diǎn)j 完整地接收到另外一個(gè)鄰居衛(wèi)星節(jié)點(diǎn)i 傳輸過來的信息幀，則認(rèn)為一個(gè)幀發(fā)送、接收成功；如果接收到的幀發(fā)生校驗(yàn)錯(cuò)誤，或因?yàn)榘l(fā)生沖突造成幀接收不完整，則認(rèn)為該幀丟失。移動(dòng)智能體的成功投遞率為

式中：Ns（i，j）和Nr（i，j）分別為衛(wèi)星節(jié)點(diǎn)i到相鄰衛(wèi)星節(jié)點(diǎn)j發(fā)送和成功接收的數(shù)據(jù)幀數(shù)目。

設(shè)衛(wèi)星節(jié)點(diǎn)i的隊(duì)列緩存總?cè)萘繛镃（i），當(dāng)前緩存分組數(shù)為M（i），則其隊(duì)列緩存當(dāng)前占用率為

2.3 星際鏈路狀態(tài)推理

通過移動(dòng)智能體獲取衛(wèi)星節(jié)點(diǎn)的成功投遞率，以及隊(duì)列的緩存容量占用率等基礎(chǔ)狀態(tài)信息。星際鏈路質(zhì)量的良好程度與衛(wèi)星節(jié)點(diǎn)的成功投遞率、衛(wèi)星節(jié)點(diǎn)的隊(duì)列緩存空閑度均有關(guān)，如果只考慮成功投遞率，會(huì)出現(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)負(fù)載不均衡，使單個(gè)衛(wèi)星節(jié)點(diǎn)負(fù)載過高而影響整體性能。為了達(dá)到網(wǎng)絡(luò)節(jié)點(diǎn)負(fù)載均衡的目的，即相關(guān)衛(wèi)星節(jié)點(diǎn)的負(fù)載相等時(shí)會(huì)得到一個(gè)性能的極好值。設(shè)衛(wèi)星節(jié)點(diǎn)i和衛(wèi)星節(jié)點(diǎn)j的隊(duì)列緩存空閑度分別為L(zhǎng)i和Lj，表示節(jié)點(diǎn)能繼續(xù)承擔(dān)的網(wǎng)絡(luò)負(fù)載能力大小，用來衡量衛(wèi)星節(jié)點(diǎn)平衡程度。在節(jié)點(diǎn)隊(duì)列緩存空閑度之和Li＋Lj一定時(shí)，當(dāng)Li＝Lj時(shí)，即負(fù)載均衡時(shí)取極大值。

定義衛(wèi)星節(jié)點(diǎn)i與j 之間鏈路質(zhì)量狀態(tài)的良好程度為

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

3 多智能體路由優(yōu)化選擇

鏈路狀態(tài)推理過程中使用兩種移動(dòng)智能體，即前向智能體和后向智能體。前向智能體使用高優(yōu)先級(jí)隊(duì)列及時(shí)傳遞路由信息，每隔固定的時(shí)間，各衛(wèi)星節(jié)點(diǎn)加載前向智能體，并派遣至網(wǎng)絡(luò)中；此后，前向智能體在衛(wèi)星網(wǎng)絡(luò)中自治地遷移，通過與部署在所到達(dá)衛(wèi)星節(jié)點(diǎn)中的靜止智能體交互，感知鏈路狀態(tài)。前向智能體到達(dá)目的衛(wèi)星節(jié)點(diǎn)時(shí)自動(dòng)轉(zhuǎn)換為后向智能體。后向智能體沿著前向智能體的路徑反向遷移。在各中間衛(wèi)星節(jié)點(diǎn)，后向智能體與靜止智能體交互，向其傳遞路由信息。后向智能體根據(jù)獲取的路由信息更新衛(wèi)星路由表。移動(dòng)智能體工作過程如圖2所示。

路徑優(yōu)化選擇原則為：源衛(wèi)星節(jié)點(diǎn)和目的衛(wèi)星節(jié)點(diǎn)分別為ns和nd，兩個(gè)節(jié)點(diǎn)之間的路徑集合定義為R，假如R ≠?，滿足條件為的路徑P 即為ns到nd所要選擇的路由路徑。該路徑上所有鏈路的質(zhì)量良好程度之和為YP，ns和nd之間的任何一條路徑由網(wǎng)絡(luò)節(jié)點(diǎn)序列（n1，n2，…，nk）表示為式中：k為該路徑經(jīng)過的中間節(jié)點(diǎn)總數(shù)；nm為該路徑上第m 個(gè)中間節(jié)點(diǎn)。

圖2 移動(dòng)智能體工作過程示意Fig.2 Travelling agent work process

4 仿真試驗(yàn)

4.1 仿真環(huán)境

以類似“銥”（Iridium）的衛(wèi)星系統(tǒng)為研究對(duì)象，對(duì)本文算法進(jìn)行仿真驗(yàn)證。假設(shè)數(shù)據(jù)從源終端經(jīng)過衛(wèi)星系統(tǒng)傳輸?shù)竭_(dá)目的終端，仿真環(huán)境設(shè)置如表1所示。

表1 仿真環(huán)境參數(shù)Table 1 Simulation environment parameters

以下對(duì)吞吐量、丟包率和端到端時(shí)延等指標(biāo)，分別用本文提出的算法與傳統(tǒng)的自適應(yīng)最短路徑路由算法［13］進(jìn)行比較。

4.2 仿真結(jié)果與分析

1）吞吐量

圖3 為網(wǎng)絡(luò)吞吐量隨著終端數(shù)據(jù)率的變化情況。從圖3可以看出，當(dāng)終端數(shù)據(jù)率較低時(shí)，本文算法和自適應(yīng)最短路由算法基本一致，負(fù)載較高時(shí)，本文算法的吞吐量能提高7%～22%。

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

2）丟包率

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

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

3）端到端時(shí)延

圖5為網(wǎng)絡(luò)不同負(fù)載下的端到端時(shí)延變化情況。從圖5可以看出，負(fù)載較低時(shí)，本文算法端到端時(shí)延明顯長(zhǎng)于自適應(yīng)最短路徑路由算法；但負(fù)載較高時(shí)，本文算法時(shí)延要短于自適應(yīng)最短路徑路由算法。這是因?yàn)椋涸诘拓?fù)載情況下，本文算法的數(shù)據(jù)包穿越了較多的跳數(shù)，需要較長(zhǎng)的時(shí)延，而自適應(yīng)最短路徑路由算法基于優(yōu)先級(jí)的選擇機(jī)制，偏向于最少跳數(shù)的路徑路由，需要較短時(shí)延；當(dāng)負(fù)載較高時(shí)，自適應(yīng)最短路徑路由算法性能急劇下降，更容易擁塞，導(dǎo)致長(zhǎng)時(shí)延。因此，本文算法在高負(fù)載情況下具有優(yōu)勢(shì)，更適用于流量變化劇烈的低軌移動(dòng)通信網(wǎng)絡(luò)。

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

5 結(jié)束語(yǔ)

本文在低軌衛(wèi)星網(wǎng)絡(luò)通信路由中引入了多智能體技術(shù)和認(rèn)知理論，提出了一種路由算法，在自適應(yīng)最小路徑的基礎(chǔ)上，通過感知星際鏈路投遞率和鏈路可用性等信息，反映衛(wèi)星網(wǎng)絡(luò)中衛(wèi)星節(jié)點(diǎn)處理負(fù)載的能力，根據(jù)衛(wèi)星節(jié)點(diǎn)的感知信息對(duì)鏈路質(zhì)量進(jìn)行推理，獲得星際鏈路質(zhì)量評(píng)價(jià)，再進(jìn)行路由的優(yōu)化選擇，從而提高網(wǎng)絡(luò)的吞吐量，實(shí)現(xiàn)負(fù)載均衡。本文提出的算法可以提高低軌衛(wèi)星網(wǎng)絡(luò)路由的環(huán)境適應(yīng)性，為我國(guó)低軌衛(wèi)星通信網(wǎng)絡(luò)建設(shè)提供參考。

（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