基于鏈路權(quán)重的分布式星群網(wǎng)絡(luò)路由算法

劉治國(guó)，張自敬，李秦鋒

（大連大學(xué)a.信息工程學(xué)院；b.遼寧省通信網(wǎng)絡(luò)與信息處理重點(diǎn)實(shí)驗(yàn)室，遼寧大連116622）

基于鏈路權(quán)重的分布式星群網(wǎng)絡(luò)路由算法

劉治國(guó)a，b，張自敬a，b，李秦鋒a，b

（大連大學(xué)a.信息工程學(xué)院；b.遼寧省通信網(wǎng)絡(luò)與信息處理重點(diǎn)實(shí)驗(yàn)室，遼寧大連116622）

針對(duì)分布式衛(wèi)星群間網(wǎng)絡(luò)傳輸時(shí)延長(zhǎng)、鏈路連接不穩(wěn)定的問(wèn)題，提出一種基于鏈路權(quán)重的改進(jìn)AODV路由算法。利用鏈路時(shí)延和連接時(shí)間定義鏈路權(quán)重，調(diào)整蟻群算法的信息素大小，使數(shù)據(jù)包在傳輸過(guò)程中能夠選擇權(quán)重較小的鏈路，避開擁塞路徑并均衡網(wǎng)絡(luò)負(fù)載。采用蟻群算法改進(jìn)AODV協(xié)議的路由表，達(dá)到優(yōu)化分布式星群網(wǎng)絡(luò)路由選擇的目的。仿真結(jié)果表明，該算法在路由選擇過(guò)程中能夠選擇低負(fù)載的路徑，且當(dāng)數(shù)據(jù)包發(fā)送速率高于600 Kb/s時(shí)，與位置輔助路由算法、AODV算法相比，具有較低的平均端到端時(shí)延和丟包率，以及較高的網(wǎng)絡(luò)吞吐量。

分布式衛(wèi)星網(wǎng)絡(luò)；路由算法；蟻群算法；鏈路權(quán)重；AODV協(xié)議

1 概述

分布式衛(wèi)星網(wǎng)絡(luò)是指由分布在一個(gè)或多個(gè)相近軌道平面上的多個(gè)衛(wèi)星組成的衛(wèi)星網(wǎng)絡(luò)，以一顆主星的方式，完成通信、遙感探測(cè)、跟蹤定位等單顆衛(wèi)星完成不了的任務(wù)［1］。而分布式星群網(wǎng)絡(luò)是指由多個(gè)分布式衛(wèi)星網(wǎng)絡(luò)組成的星群通信網(wǎng)絡(luò)，能夠?yàn)榇蠓秶㈤L(zhǎng)距離的客戶端提供滿足要求的服務(wù)。為提供高質(zhì)量、無(wú)間斷的服務(wù)，每個(gè)單獨(dú)的分布式衛(wèi)星網(wǎng)絡(luò)都需要數(shù)顆衛(wèi)星組成，這些衛(wèi)星具有星上處理能力，衛(wèi)星之間具有星際鏈路，與其他星群通過(guò)主星或者中繼衛(wèi)星進(jìn)行通信。由此可見，分布式星群網(wǎng)絡(luò)的衛(wèi)星數(shù)目多、軌道周期長(zhǎng)、覆蓋區(qū)域大，在通信時(shí)既要考慮群內(nèi)路徑，又要兼顧群間路徑。所以，路由問(wèn)題一直是分布式星群網(wǎng)絡(luò)研究的重點(diǎn)和難點(diǎn)［2-3］。

針對(duì)衛(wèi)星網(wǎng)絡(luò)路由問(wèn)題，目前研究人員已提出流量工程路由算法［4］、基于預(yù)案的衛(wèi)星網(wǎng)絡(luò)路由算法［5］、動(dòng)態(tài)故障容忍路由算法［6］等多種算法。文獻(xiàn)［7］提出負(fù)載均衡路由協(xié)議PAR，根據(jù)鏈路過(guò)去的利用率與緩存信息確定鏈路等級(jí)，進(jìn)而利用該等級(jí)選擇下一跳，但PAR存在負(fù)載反映滯后的問(wèn)題。文獻(xiàn)［8］提出一種雙層星座中負(fù)載均衡路由協(xié)議LBRD，利用分層思想，層間衛(wèi)星采取地理位置路由策略，利用鄰間鏈路負(fù)載通告的方式，調(diào)節(jié)單顆衛(wèi)星的負(fù)載，但多顆相鄰衛(wèi)星過(guò)載時(shí)調(diào)節(jié)緩慢。文獻(xiàn)［9］提出位置輔助路由協(xié)議LAOR，LAOR協(xié)議本質(zhì)上是按需路由協(xié)議，利用衛(wèi)星網(wǎng)絡(luò)軌道的周期性，將路由請(qǐng)求（RREQ）分組限制在一定范圍內(nèi)，縮小了路由查找范圍，但沒(méi)有考慮衛(wèi)星網(wǎng)絡(luò)鏈路狀態(tài)。

然而上述衛(wèi)星路由算法都是針對(duì)衛(wèi)星群內(nèi)網(wǎng)絡(luò)設(shè)計(jì)，不適用于分布式衛(wèi)星群間網(wǎng)絡(luò)。因此，本文針對(duì)分布式衛(wèi)星群間網(wǎng)絡(luò)的時(shí)延大、連接時(shí)間不固定等特點(diǎn)，提出一種適用于分布式衛(wèi)星群間網(wǎng)絡(luò)的路由算法：基于鏈路權(quán)重的改進(jìn)AODV路由算法（Link W eight-based Ad Hoc On-demand Vector Routing，LW-AODV）。該算法利用鏈路時(shí)延和連接時(shí)間定義鏈路權(quán)重調(diào)整信息素大小，使數(shù)據(jù)包在傳輸過(guò)程中能夠選擇權(quán)重較小的鏈路。

2 AODV路由協(xié)議和蟻群算法

分布式衛(wèi)星群間網(wǎng)絡(luò)不僅具有傳統(tǒng)衛(wèi)星網(wǎng)絡(luò)的特征，而且與Ad Hoc網(wǎng)絡(luò)類似。一個(gè)星群本身即可視為Ad Hoc網(wǎng)絡(luò)中的一個(gè)簇，簇頭與簇頭的通信可視為星群間主星的通信。因此，Ad Hoc路由算法對(duì)分布式星群路由算法的設(shè)計(jì)有一定的借鑒意義。

目前，經(jīng)典的Ad Hoc網(wǎng)絡(luò)路由協(xié)議主要有目的節(jié)點(diǎn)序列距離矢量（Destination Sequenced Distance Vector，DSDV）路由協(xié)議、動(dòng)態(tài)源路由（dynamic Source Routing，DSR）協(xié)議、Ad Hoc網(wǎng)絡(luò)按需距離矢量路由（AODV）協(xié)議。DSDV路由協(xié)議解決了無(wú)窮環(huán)路的問(wèn)題，DSR路由協(xié)議解決了周期發(fā)送路由包的問(wèn)題，而AODV路由協(xié)議是兩者的結(jié)合，其在衛(wèi)星網(wǎng)絡(luò)適用性和性能方面已經(jīng)得到驗(yàn)證。本文借鑒AODV協(xié)議思想，將其與改進(jìn)的蟻群算法相結(jié)合應(yīng)用于分布式衛(wèi)星群間網(wǎng)絡(luò)，以提高路由效率。

2.1 AODV路由協(xié)議

AODV路由協(xié)議是在DSDV協(xié)議的基礎(chǔ)上結(jié)合DSR中的按需路由機(jī)制提出，因此，既有DSDV的逐跳路由、序現(xiàn)形式，又依據(jù)DSR形成特有的路由發(fā)現(xiàn)和路由維護(hù)過(guò)程。

（1）路由發(fā)現(xiàn)

源節(jié)點(diǎn)（Src）有數(shù)據(jù)包需要發(fā)送時(shí)，則啟動(dòng)路由發(fā)現(xiàn)過(guò)程。源節(jié)點(diǎn)向其鄰節(jié)點(diǎn)廣播路由請(qǐng)求報(bào)文RREQ。中間節(jié)點(diǎn)收到RREQ時(shí)，首先建立到上一跳的反向路由，接著查找自己的路由表，如果存在到目的節(jié)點(diǎn)（Dest）的有效路由，則通過(guò)已建立的反向路由返回路由應(yīng)答（RREP）報(bào)文［10］；否則繼續(xù)向鄰節(jié)點(diǎn)廣播RREQ，直到該RREQ到達(dá)目的節(jié)點(diǎn)，由目的節(jié)點(diǎn)生成RREP，并沿已建立的反向路由將RREP發(fā)送給源節(jié)點(diǎn)［11-12］。依次類推，直到到達(dá)目的節(jié)點(diǎn)或是中間某個(gè)有直接到達(dá)目的節(jié)點(diǎn)的節(jié)點(diǎn)。路由發(fā)現(xiàn)過(guò)程由建立反向路由和前向路由兩部分組成，如圖1所示。

圖1 AODV路由發(fā)現(xiàn)過(guò)程

（2）路由維護(hù)

由于分布式星群網(wǎng)絡(luò)衛(wèi)星節(jié)點(diǎn)的移動(dòng)性，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)時(shí)刻發(fā)生改變，因此路由要保持持續(xù)連通必須進(jìn)行路由維護(hù)，其主要思想是通過(guò)節(jié)點(diǎn)周期性地發(fā)送Hello分組來(lái)實(shí)現(xiàn)。在每個(gè)周期開始時(shí)，每個(gè)節(jié)點(diǎn)都會(huì)構(gòu)造一個(gè)生存時(shí)間（Time to Live，TTL）為1的RREP分組并對(duì)其所有鄰居節(jié)點(diǎn)進(jìn)行廣播，收到廣播分組的鄰節(jié)點(diǎn)會(huì)對(duì)其回復(fù)Hello分組來(lái)確認(rèn)彼此間的連通性。如果某個(gè)節(jié)點(diǎn)在過(guò)去收到過(guò)來(lái)自某節(jié)點(diǎn)的Hello分組，而在給定時(shí)間t后沒(méi)有再次收到來(lái)自該節(jié)點(diǎn)的任何分組，則認(rèn)為這2個(gè)節(jié)點(diǎn)間的鏈路已經(jīng)斷開，其上的路由信息視為無(wú)效，需進(jìn)行路由修復(fù)。因此，本文提出的LW-AODV路由算法采取本地鏈路修復(fù)。

2.2 蟻群算法

盡管AODV路由協(xié)議已經(jīng)被普遍使用，但是它仍然存在一些缺點(diǎn)，其中比較明顯的缺點(diǎn)是：在建立路由時(shí)，鄰居節(jié)點(diǎn)依次向周圍節(jié)點(diǎn)廣播此分組，導(dǎo)致分組包的數(shù)量激增，從而增加路徑選擇的管理開銷。針對(duì)該問(wèn)題，一些學(xué)者提出使用遺傳算法、模擬退化算法、禁忌搜索算法、人工神經(jīng)網(wǎng)絡(luò)改進(jìn)AODV協(xié)議的路由包，用于解決組合優(yōu)化問(wèn)題。但是這些算法需要設(shè)置系統(tǒng)輸入?yún)?shù)，否則起不到改進(jìn)AODV協(xié)議的結(jié)果。蟻群算法［13-14］是一種現(xiàn)代智能算法，通過(guò)螞蟻釋放的信息素濃度，以一定的概率選擇最佳路徑，并利用正反饋機(jī)制達(dá)到發(fā)現(xiàn)最優(yōu)路徑的目的，能夠很好地解決AODV協(xié)議中廣播路由包的缺點(diǎn)。

3 基于鏈路權(quán)重的分布式衛(wèi)星群間路由算法

本文在AODV的RREQ和RREP報(bào)文的下一跳節(jié)點(diǎn)信息域中加入信息素值、鏈路權(quán)重值和概率選擇表等參數(shù)，即將改進(jìn)的基于鏈路權(quán)重的蟻群算法應(yīng)用于AODV協(xié)議。本文算法基本思想是：每顆衛(wèi)星都維護(hù)一張路由表，利用蟻群算法改進(jìn)AODV協(xié)議后，此路由表被稱為概率表。螞蟻尋找食物的運(yùn)動(dòng)可以看作數(shù)據(jù)包的發(fā)送過(guò)程，則數(shù)據(jù)包尋路時(shí)會(huì)受到螞蟻釋放的信息素的影響，進(jìn)而依據(jù)一定的概率有目標(biāo)性地選擇下一跳節(jié)點(diǎn)。每次進(jìn)行路由查找過(guò)程時(shí)，源節(jié)點(diǎn)就會(huì)根據(jù)相關(guān)權(quán)重參數(shù)以及相關(guān)公式求得本節(jié)點(diǎn)到下一節(jié)點(diǎn)的信息素值，進(jìn)而計(jì)算出選擇下一節(jié)點(diǎn)的概率。在回復(fù)RREP時(shí)，設(shè)定初始目的節(jié)點(diǎn)信息素，并沿著反向路由進(jìn)行擴(kuò)散。本文算法在繼承AODV算法路由建立和路由維護(hù)的基礎(chǔ)上，利用蟻群算法優(yōu)化下一跳選擇。

3.1 算法基本規(guī)則

3.1.1 下一跳節(jié)點(diǎn)選擇規(guī)則

式（1）規(guī)定了數(shù)據(jù)包K在節(jié)點(diǎn)i選擇移動(dòng)到下一跳節(jié)點(diǎn)j的概率：

其中，τij（t）表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的信息素值；cij表示鏈路帶寬；rij表示鏈路傳輸速率；lij表示鏈路丟包率；α，β和γ分別表示帶寬、傳輸速率和丟包率對(duì)信息素影響的重要程度，取值為0～1；tabuK（K=1，2，…，m）為螞蟻K的禁忌表，記錄了螞蟻K已走過(guò)的節(jié)點(diǎn)；allowedK=｛c-tabuK｝表示在t時(shí)刻螞蟻K下一步允許選擇的節(jié)點(diǎn)。

3.1.2 信息素更新規(guī)則

數(shù)據(jù)包的傳輸路徑能夠影響鏈路信息素的變化。若有數(shù)據(jù)包經(jīng)過(guò)某鏈路，則釋放信息素，使該鏈路信息素的值增加，否則該鏈路的信息素就會(huì)由于揮發(fā)而減少。信息素更新公式具體如下：

其中，ρ（0≤ρ≤1）表示路徑上信息素的揮發(fā)系數(shù)，（1-ρ）表示信息素的殘留因子；τij（Δt）表示路徑（i，j）上信息素的增量；為常量，表示螞蟻?zhàn)咄晁谐鞘兴尫诺男畔⑺乜偭?，dij為路徑（i，j）的長(zhǎng)度。

3.1.3 鏈路權(quán)重定義規(guī)則

本文在蟻群算法的基礎(chǔ)上考慮每一跳的權(quán)重，選擇權(quán)重較小的路徑，則能優(yōu)化路由選擇。相對(duì)于地面網(wǎng)絡(luò)，衛(wèi)星網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)具有易變性，鏈路連接的時(shí)間是路由建立過(guò)程中必須考慮的因素；相對(duì)于群內(nèi)衛(wèi)星網(wǎng)絡(luò)，群間衛(wèi)星距離長(zhǎng)，造成通信時(shí)延大，因此時(shí)延也是群間路由中必須考慮的問(wèn)題。鑒于此，本文使用鏈路連接時(shí)間和時(shí)延2種參數(shù)來(lái)定義鏈路權(quán)重。節(jié)點(diǎn)Phert到鄰居節(jié)點(diǎn)Phert之間鏈路的權(quán)重wij定義如下：

其中，D（i，j）表示鏈路（i，j）上的時(shí)延；L（i，j）表示鏈路（i，j）的連接時(shí)間；α1和β1分別表示時(shí)延和連接時(shí)間的相對(duì)重要性，可以根據(jù)對(duì)帶寬和時(shí)延的具體要求進(jìn)行調(diào)節(jié)。鏈路連接時(shí)間采用GPS運(yùn)動(dòng)方程，如式（6）所示：

其中，a=νicosθi-νjcosθj；b=χi-χj；c=νisinθiνjsinθj；d=yi-yj；νi和νj分別為節(jié)點(diǎn)i和j的平均移動(dòng)速度；θi和θj分別為節(jié)點(diǎn)i和j的節(jié)點(diǎn)移動(dòng)方向；（χi，yi）和（χj，yj）分別為節(jié)點(diǎn)i和j的坐標(biāo)。

3.2 改進(jìn)的蟻群算法

蟻群算法是根據(jù)路徑上信息素的大小來(lái)做出路由決策，所以，將鏈路狀態(tài)作為影響信息素增量的因素，即根據(jù)鏈路擁塞情況來(lái)增大或減小信息素增量。在算法開始時(shí)，設(shè)定一個(gè)適合的鏈路權(quán)重閾值w0，當(dāng)所經(jīng)過(guò)的鏈路權(quán)重小于該閾值時(shí)，信息素更新時(shí)就加上該鏈路的權(quán)重，否則就減去該鏈路權(quán)重。這樣權(quán)重較小的鏈路更新時(shí)增加的信息素就較大，從而被后續(xù)螞蟻選中的可能性就越大。根據(jù)鏈路權(quán)重更新信息素的規(guī)則，如式（7）所示：

當(dāng)螞蟻經(jīng)過(guò)鏈路Phert后 ，該路徑上的信息素按照式（3）、式（4）、式（7）進(jìn)行更新，這樣后來(lái)的螞蟻就會(huì)受信息素的影響，選擇鏈路權(quán)重較小的鏈路，更好地避開擁塞鏈路。

當(dāng)網(wǎng)絡(luò)初始化時(shí)，傳統(tǒng)蟻群算法認(rèn)為此時(shí)節(jié)點(diǎn)路由表為空，這將增加路由建立時(shí)間。但是衛(wèi)星網(wǎng)絡(luò)拓?fù)浯嬖谝?guī)則性和周期性特點(diǎn)，所以，衛(wèi)星節(jié)點(diǎn)在開始時(shí)可以按照式（8）初始化路由表，則路由建立時(shí)間將會(huì)大大降低。

其中，HoPij是對(duì)于目的節(jié)點(diǎn)選擇節(jié)點(diǎn)j作為下一跳節(jié)點(diǎn)的最短跳數(shù)。

3.3 分布式衛(wèi)星群間路由算法步驟

分布式衛(wèi)星群間網(wǎng)絡(luò)通過(guò)群內(nèi)主星進(jìn)行通信，若距離較遠(yuǎn)，則通過(guò)中轉(zhuǎn)衛(wèi)星進(jìn)行通信。本文假設(shè)每個(gè)衛(wèi)星群主星節(jié)點(diǎn)都有與之相連的ILS（Intel Satellites Link）傳播時(shí)延和連接時(shí)間等信息，同時(shí)假設(shè)發(fā)送數(shù)據(jù)的衛(wèi)星群和接收數(shù)據(jù)的衛(wèi)星群都已確定。當(dāng)某個(gè)衛(wèi)星節(jié)點(diǎn)收到鏈接請(qǐng)求時(shí)，首先檢查自己的路由表是否有有效路由存在，若存在則利用此路由通信，否則該節(jié)點(diǎn)就成為路由進(jìn)程的源節(jié)點(diǎn)，開始建立路由。該算法中Phert表示概率表，tabu表保存螞蟻已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)，以避免路由環(huán)的產(chǎn)生。該算法具體步驟如下：

（1）網(wǎng)絡(luò)節(jié)點(diǎn)初始化：當(dāng)時(shí)間t=0時(shí)，設(shè)置算法中相應(yīng)的參數(shù)。按照分布式星群網(wǎng)絡(luò)節(jié)點(diǎn)跳數(shù)的分配情況，根據(jù)式（8）初始化概率表，根據(jù)式（1）計(jì)算信息素表Phert，在源衛(wèi)星節(jié)點(diǎn)s放置L只螞蟻，并為每只螞蟻設(shè)置一個(gè)空的禁忌表tabu。

（2）把源衛(wèi)星節(jié)點(diǎn)s放入tabu中，螞蟻從信息素表Phert中，選出概率最大衛(wèi)星節(jié)點(diǎn)j，并將其選為下一跳節(jié)點(diǎn)。

（3）假設(shè)此時(shí)螞蟻在節(jié)點(diǎn)i，當(dāng)節(jié)點(diǎn)i為目的節(jié)點(diǎn)d時(shí)，則沿著螞蟻來(lái)時(shí)的路徑，向源節(jié)點(diǎn)發(fā)送一只反向螞蟻，同時(shí)根據(jù)式（3）、式（4）、式（7）更新鏈路信息素的值。選擇路徑P（s，d），將該路徑上所有節(jié)點(diǎn)放入tabu表中。更新Phert表，供下一次路徑查找使用，本輪算法結(jié)束。如果i不是目的節(jié)點(diǎn)d，根據(jù)表移動(dòng)到下一個(gè)節(jié)點(diǎn)j。

（4）如果j∈tabu，則螞蟻返回節(jié)點(diǎn)i，重復(fù)步驟（3）。

（5）對(duì)于節(jié)點(diǎn)j，重復(fù)上述在節(jié)點(diǎn)i的步驟（3）、步驟（4）。

（6）在路由建立后，為維護(hù)路由，此算法利用Hello消息報(bào)文進(jìn)行路由維護(hù)。

3.4 算法時(shí)間復(fù)雜度分析

假設(shè)有m只螞蟻，則有m個(gè)路徑表，初始化時(shí)間復(fù)雜度為O（m）。m只螞蟻全部完成Nc次遍歷是一個(gè)3層嵌套循環(huán)過(guò)程：最外層是遍歷次數(shù)Nc，次外層是螞蟻數(shù)量m，最內(nèi)層是每只螞蟻遍歷的n個(gè)節(jié)點(diǎn)。最內(nèi)層循環(huán)在每一步選擇下一個(gè)節(jié)點(diǎn)時(shí)會(huì)計(jì)算概率和比較路徑表中的節(jié)點(diǎn)，有一層復(fù)雜度為O（n）級(jí)別的嵌套，因此最終所有螞蟻完成Nc次遍歷的時(shí)間復(fù)雜度為O（Nc·m·n2）。而一般衛(wèi)星網(wǎng)絡(luò)的規(guī)模都較小，即節(jié)點(diǎn)較少，所以此時(shí)間復(fù)雜度在衛(wèi)星網(wǎng)絡(luò)是可以接受的。

4 實(shí)驗(yàn)仿真與性能分析

本文利用已在STK（Satellite Tool K it）中搭建好的仿真星座數(shù)據(jù)，在NS2中構(gòu)建分布式星群網(wǎng)絡(luò)仿真模型，分析改進(jìn)的路由算法應(yīng)用到分布式衛(wèi)星網(wǎng)絡(luò)的有效性和可行性。

4.1 仿真場(chǎng)景

本文仿真場(chǎng)景采取3個(gè)星群進(jìn)行通信，衛(wèi)星本身的處理速率為1 000 packet/s，衛(wèi)星間鏈路帶寬為10 M b/s，上行鏈路和下行鏈路帶寬為9 M b/s，衛(wèi)星天線的半功率角為1.179 4 rad。此場(chǎng)景采用2個(gè)GEO衛(wèi)星群和一個(gè)LEO衛(wèi)星群組成的3層星群模型結(jié)構(gòu)。所有衛(wèi)星（包括主星）用Lij標(biāo)識(shí)，其中，i表示衛(wèi)星所處星群編號(hào)；j表示衛(wèi)星在星群內(nèi)的序號(hào)。GEO衛(wèi)星群和LEO衛(wèi)星群各自與相鄰節(jié)點(diǎn)建立ISL鏈路，群間通過(guò)各自星群內(nèi)的主星建立群間鏈路。星群1向星群3發(fā)送數(shù)據(jù)和語(yǔ)音業(yè)務(wù)，等效拓?fù)浣Y(jié)構(gòu)如圖2所示。

圖2 三星群通信的等效拓?fù)浣Y(jié)構(gòu)

4.2 仿真結(jié)果分析

在模擬過(guò)程中，評(píng)價(jià)本文算法、LAOR算法以及AODV算法的性能，主要通過(guò)實(shí)驗(yàn)仿真網(wǎng)絡(luò)的吞吐量、平均端到端時(shí)延和平均丟包率這3個(gè)指標(biāo)來(lái)衡量算法性能，這3個(gè)指標(biāo)是路由算法性能評(píng)價(jià)的重要指標(biāo)。

圖3是3種算法的平均端到端時(shí)延變化情況。當(dāng)發(fā)送速率低于600 Kb/s時(shí)，網(wǎng)絡(luò)處于低負(fù)載，AODV有較大優(yōu)勢(shì)，但隨著發(fā)送速率的增強(qiáng)，網(wǎng)絡(luò)業(yè)務(wù)量明顯增加，本文算法和LAOR算法的平均端到端時(shí)延優(yōu)于AODV算法。相比之下，本文算法選擇權(quán)重較小，即繁忙程度低的路徑，因此平均端到端時(shí)延較小。

圖3 不同發(fā)送速率下的平均端到端時(shí)延

圖4 是3種算法平均丟包率的變化情況。由此可知，當(dāng)發(fā)送速率較低時(shí)，網(wǎng)絡(luò)處于低負(fù)載，3種算法的丟包率基本為0。但隨著發(fā)送速率的增加，網(wǎng)絡(luò)節(jié)點(diǎn)開始出現(xiàn)擁塞，丟包率開始增加。當(dāng)數(shù)據(jù)速率超過(guò)400 Kb/s時(shí)，AODV算法的丟包率迅速增加。然而，本文算法和LAOR算法的丟包率較小，因?yàn)楸疚乃惴ㄔ诼酚山r(shí)，通過(guò)避開高負(fù)載的路徑，降低了擁塞概率。圖5是3種算法的網(wǎng)絡(luò)吞吐量變化情況。

圖4 不同發(fā)送速率下的平均丟包率

圖5 不同發(fā)送速率下的網(wǎng)絡(luò)吞吐量

當(dāng)數(shù)據(jù)發(fā)送速率低于600 Kb/s時(shí)，3種算法并無(wú)明顯區(qū)別。隨著發(fā)送速率的提高，網(wǎng)絡(luò)業(yè)務(wù)量不斷增強(qiáng)，尤其當(dāng)數(shù)據(jù)發(fā)送速率高于800 Kb/s時(shí)，本文算法吞吐量有明顯改善，這是因?yàn)楸疚乃惴▉G包率低，加大了網(wǎng)絡(luò)吞吐量。綜上分析可知，本文算法更適合于高負(fù)載的動(dòng)態(tài)分布式衛(wèi)星網(wǎng)絡(luò)群間路由的建立。

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

本文針對(duì)分布式衛(wèi)星群間網(wǎng)絡(luò)提出一種改進(jìn)的路由算法，采用改進(jìn)的蟻群算法優(yōu)化AODV協(xié)議的路由表，達(dá)到優(yōu)化分布式衛(wèi)星群間網(wǎng)絡(luò)路由選擇的目的。當(dāng)鏈路連接不穩(wěn)定與傳輸時(shí)延較長(zhǎng)時(shí)，根據(jù)改進(jìn)的蟻群算法的信息素更新策略，降低螞蟻選擇該路徑的概率，避開網(wǎng)絡(luò)中的擁塞路徑并且均衡網(wǎng)絡(luò)負(fù)載，進(jìn)而減少鏈路時(shí)延和丟包率，增加網(wǎng)絡(luò)吞吐量。下一步將對(duì)算法中信息素變化的計(jì)算以及信息素表的更新做進(jìn)一步研究。

［1］ 潘成勝.空間信息網(wǎng)絡(luò)的若干關(guān)鍵技術(shù)［J］.中國(guó)計(jì)算機(jī)學(xué)會(huì)通信，2013，9（4）：46-51.

［2］ 楊 力，楊校春，潘成勝.一種GEO/LEO雙層衛(wèi)星網(wǎng)絡(luò)路由算法及仿真研究［J］.宇航學(xué)報(bào)，2012，33（10）：1444-1452.

［3］ Song Guanghua，Chao Mengyuan，Yang Bowei.A Trafficlight-based Intelligent Routing Strategy for NGEO Satellite IPNetworks［J］.Wireless Communications，2014，13（6）：37-46.

［4］ 肖 甫，孫力娟，葉曉國(guó)，等.面向衛(wèi)星網(wǎng)絡(luò)的流量工程路由算法［J］.通信學(xué)報(bào)，2011，32（5）：104-111.

［5］ 李洪鑫，張傳富，蘇錦海.基于OPNET的衛(wèi)星網(wǎng)絡(luò)路由協(xié)議仿真［J］.計(jì)算機(jī)工程，2011，37（11）：120-122.

［6］ Lu Yong，Zhao Youjian，Sun Fuchun.dynamic Faulttolerant Routing Based on FSA for LEO Satellite Networks［J］.IEEE Transactions on Computers，2013，62（10）：1945-1958.

［7］ Korcak O，A lagoz F，Jamalipour A.Priority-based Adaptive Shortest Path Routing for IP Over Satellite Networks［J］.International Journal of Communication System s，2007，20（3）：313-333.

［8］ 陳建州，王 路，劉立祥，等.雙層星座中負(fù)載均衡路由協(xié)議研究［J］.宇航學(xué)報(bào)，2012，33（6）：743-753.

［9］ Papapetrou E，Karapantazis S，Pavlidou F N.Distributed On-demand Routing for LEO Satellite System s［J］. Computer Networks，2007，51（15）：4356-4376.

［10］ 薛 強(qiáng)，呂光宏.AODV的本地修復(fù)改進(jìn)機(jī)制［J］.計(jì)算機(jī)工程，2008，34（19）：121-122，126.

［11］ 周少瓊，徐 袆，蔣 麗，等.蟻群優(yōu)化算法在Ad Hoc網(wǎng)絡(luò)路由中的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用，2011，31（2）：332-334.

［12］ 王 鵬，郭達(dá)偉.一種基于監(jiān)聽鄰居信息的AODV本地修復(fù)算法［J］.科學(xué)技術(shù)與工程，2012，12（2）：313-316.

［13］ Wang Houtian，Zhang Qi，Xin Xiangjun，et al.Cross-layer Design and Ant-colony Optim ization Based Routing Algorithm for Low Earth Orbit Satellite Networks［J］.China Communications，2013，10（10）：37-46.

［14］ Jiang Wenjuan，Zong Peng.Multi-class Traffic QoS Routing For LEO Satellite Network［J］.Transactions of Nanjing University of Aeronautics&Astronautics，2012，29（3）：254-262.

編輯 陸燕菲

Routing Algorithm of Distributed Constellation Network Based on Link W eight

LIU Zhiguoa，b，ZHANG Zijinga，b，LIQinfenga，b
（a.College of Information Engineering；b.Liaoning Key Laboratory of Communication Networks and Information Processing，Dalian University，Dalian 116622，China）

Aim ing at the problems of long transmission delay and instable link-connection in distributed satellite intergroup network，this paper proposes an improved Ad Hoc On-demand Distance Vector（AODV）routing algorithm based on link weight.It defines the link weight by using link delay and connection time，adjusts the size of pheromone by using ant colony algorithm and chooses the light weight in the transmission process to avoid congestion and trade-off network load.It uses the improved ant algorithm to optimize routing table of AODV protocol to achieve the purpose of optimizing distributed satellite network routing selection.Simulation results show that this algorithm can choose low load path in the routing selection when the data package transmission rate is over 600 Kb/s.Compared with the position auxiliary routing algorithm and AODV algorithm，it can shorten the end-to-end delay，reduce the package loss and improve the throughout.

distributed satellite network；routing algorithm；ant colony algorithm；link weight；Ad Hoc On-demand Distance Vector（AODV）protocol

劉治國(guó)，張自敬，李秦鋒.基于鏈路權(quán)重的分布式星群網(wǎng)絡(luò)路由算法［J］.計(jì)算機(jī)工程，2015，41（9）：145-149.

英文引用格式：Liu Zhiguo，Zhang Zijing，Li Qinfeng.Routing Algorithm of Distributed Constellation Network Based on Link W eight［J］.Computer Engineering，2015，41（9）：145-149.

1000-3428（2015）09-0145-05

A

TP393

10.3969/j.issn.1000-3428.2015.09.026

國(guó)家自然科學(xué)基金資助項(xiàng)目（91338104）；國(guó)家“863”計(jì)劃基金資助項(xiàng)目；大連市杰出青年人才計(jì)劃基金資助項(xiàng)目（2014J 11JH135）。

劉治國(guó)（1974-），男，教授，主研方向：空間信息網(wǎng)絡(luò)與通信；張自敬、李秦鋒，碩士研究生。

2014-08-18

2014-10-26 E-m ail：liuzhiguo863@163.com