衛(wèi)星網(wǎng)絡(luò)中基于蟻群優(yōu)化的概率路由算法

戴翠琴，尹小盼

(重慶郵電大學(xué) 移動(dòng)通信技術(shù)重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

0 引 言

與地面通信網(wǎng)絡(luò)相比，衛(wèi)星通信網(wǎng)絡(luò)具有廣覆蓋、大容量、遠(yuǎn)距離傳輸?shù)葍?yōu)點(diǎn)，能夠滿足靈活、動(dòng)態(tài)的空間網(wǎng)絡(luò)配置需求[1]。但是，由于衛(wèi)星節(jié)點(diǎn)圍繞地球周期性的運(yùn)動(dòng)特性，使得網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化、星間鏈路(inter-satellite link, ISL)頻繁切換、鏈路長(zhǎng)度和通斷關(guān)系隨時(shí)間動(dòng)態(tài)變化，對(duì)空間信息傳輸?shù)挠行院涂煽啃栽斐闪藝?yán)重的影響。同時(shí)，考慮到星上資源有限、負(fù)載分布不均勻等因素，如何設(shè)計(jì)高效、可靠、靈活的衛(wèi)星網(wǎng)絡(luò)路由算法日益成為研究者們關(guān)注的熱點(diǎn)問(wèn)題[2-3]。

目前，按照路由算法能否根據(jù)網(wǎng)絡(luò)拓?fù)涞淖兓皶r(shí)更新路由表，可將衛(wèi)星網(wǎng)絡(luò)中的路由算法大致分為兩類(lèi)：靜態(tài)路由算法[4]和動(dòng)態(tài)路由算法[5-8]。其中，文獻(xiàn)[4]將低軌衛(wèi)星網(wǎng)絡(luò)(low earth orbit, LEO)模擬成有限狀態(tài)自動(dòng)機(jī)，將LEO衛(wèi)星網(wǎng)絡(luò)的動(dòng)態(tài)鏈路分配問(wèn)題轉(zhuǎn)換為靜態(tài)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的固定鏈路分配和路由優(yōu)化問(wèn)題。但是，由于靜態(tài)路由機(jī)制不能根據(jù)網(wǎng)絡(luò)流量和拓?fù)浣Y(jié)構(gòu)的變化來(lái)調(diào)整自身的路由表，也就無(wú)法適應(yīng)星間鏈路的動(dòng)態(tài)變化。相比之下，動(dòng)態(tài)路由算法充分考慮了網(wǎng)絡(luò)當(dāng)前的實(shí)時(shí)狀態(tài)信息，使得路由選擇能夠更好地適應(yīng)網(wǎng)絡(luò)流量、拓?fù)浣Y(jié)構(gòu)的變化，能夠改善網(wǎng)絡(luò)整體性能。文獻(xiàn)[5]在LEO衛(wèi)星網(wǎng)絡(luò)中提出了一種基于分布式負(fù)載感知的動(dòng)態(tài)路由算法，采用一種逐跳機(jī)制來(lái)分割流量負(fù)載，以緩解極區(qū)附近發(fā)生的擁塞問(wèn)題。文獻(xiàn)[6]針對(duì)最短路徑問(wèn)題，提出一種動(dòng)態(tài)虛擬拓?fù)渎酚?dynamic virtual topology routing, DVTR)算法。文獻(xiàn)[7]針對(duì)如何延長(zhǎng)衛(wèi)星使用壽命的問(wèn)題，提出了一種能量高效的路由算法。文獻(xiàn)[8]提出了一種基于代理分組交換的動(dòng)態(tài)路由算法，改善了網(wǎng)絡(luò)吞吐性能。文獻(xiàn)[9]考慮了衛(wèi)星網(wǎng)絡(luò)中的傳輸業(yè)務(wù)需求，提出了一種基于多業(yè)務(wù)傳輸優(yōu)化的動(dòng)態(tài)路由算法，但未考慮網(wǎng)絡(luò)吞吐量和鏈路利用率。因此，現(xiàn)有衛(wèi)星網(wǎng)絡(luò)中的動(dòng)態(tài)路由算法主要針對(duì)某個(gè)單一的特定問(wèn)題進(jìn)行優(yōu)化，沒(méi)有能夠同時(shí)兼顧網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化和鏈路頻繁切換對(duì)網(wǎng)絡(luò)性能造成的影響。因此，以上研究結(jié)果若直接應(yīng)用到衛(wèi)星時(shí)變網(wǎng)絡(luò)中，將產(chǎn)生端到端時(shí)延增大、星上資源利用率低等問(wèn)題。

蟻群優(yōu)化(ant colony optimization, ACO)，是一種用來(lái)尋找最優(yōu)路徑的機(jī)率型算法，最早由Marco Dorigo提出[10]，來(lái)源于螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為。ACO具有自適應(yīng)性和魯棒性的優(yōu)點(diǎn)，能夠通過(guò)正反饋、分布式協(xié)作來(lái)尋找最優(yōu)徑。因此，近來(lái)已有少量文獻(xiàn)將ACO運(yùn)用在衛(wèi)星網(wǎng)絡(luò)中的路由路徑計(jì)算中，使之能夠適應(yīng)衛(wèi)星網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化的同時(shí)平衡網(wǎng)絡(luò)負(fù)載，進(jìn)而減少或避免發(fā)生鏈路擁塞[11-15]。其中，文獻(xiàn)[11]通過(guò)改善傳統(tǒng)蟻群優(yōu)化，利用虛擬拓?fù)浣鉀Q了衛(wèi)星網(wǎng)絡(luò)中拓?fù)淇焖僮兓膯?wèn)題，雖然提高了蟻群優(yōu)化的收斂時(shí)間，但是沒(méi)有解決鏈路易發(fā)生擁塞的問(wèn)題。文獻(xiàn)[12]中提出一種基于改進(jìn)蟻群優(yōu)化的自適應(yīng)路由優(yōu)化算法(improved ant colony optimization, IACO)，改善了ACO算法易導(dǎo)致ISL發(fā)生擁塞和路由收斂時(shí)間慢的缺點(diǎn)。文獻(xiàn)[13]提出一種跨層設(shè)計(jì)和基于ACO的負(fù)載均衡路由算法(cross-layer design and ant-colony optimization based load-balancing routing algorithm, CAL-LSN)，其利用物理層信息作出路由決定，采用多目標(biāo)優(yōu)化模型實(shí)現(xiàn)負(fù)載均衡。文獻(xiàn)[14]運(yùn)用ACO的啟發(fā)式方法提出了一種路由優(yōu)化算法，使得尋找到的最優(yōu)路徑具有最大吞吐量。文獻(xiàn)[15]結(jié)合概率路由協(xié)議(probabilistic routing protocol using history of encounters and transitivity, ProPHET)的概率度量標(biāo)準(zhǔn)和ACO算法，提出了一種基于蟻群優(yōu)化的ProPHET改進(jìn)方案，提高信息傳輸率的同時(shí)降低了網(wǎng)絡(luò)成本。以上已有的基于ACO的衛(wèi)星網(wǎng)絡(luò)路由算法主要針對(duì)收斂時(shí)間進(jìn)行了優(yōu)化，均沒(méi)有考慮到衛(wèi)星網(wǎng)絡(luò)中數(shù)據(jù)包的傳輸時(shí)延和ISL利用率問(wèn)題。同時(shí)，由于衛(wèi)星網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)變化，當(dāng)多個(gè)包需要傳輸時(shí)，一個(gè)連通時(shí)間片內(nèi)不能完全將數(shù)據(jù)包完全轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)，需等待下一個(gè)連通時(shí)間片，這將會(huì)產(chǎn)生多個(gè)節(jié)點(diǎn)向同一節(jié)點(diǎn)發(fā)送包，進(jìn)而造成鏈路使用沖突、系統(tǒng)丟包率增大以及傳輸包時(shí)延增大等問(wèn)題。

針對(duì)以上問(wèn)題，本文綜合考慮衛(wèi)星網(wǎng)絡(luò)中時(shí)延帶寬和鏈路容量2個(gè)因素對(duì)傳輸路徑選擇的影響，提出一種基于蟻群優(yōu)化的概率路由算法(ant colony optimization based probabilistic routing algorithm, ACO-PRA)。首先，結(jié)合衛(wèi)星網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)時(shí)變特性，將鏈路容量和星間鏈路距離2個(gè)性能因素引入到ACO節(jié)點(diǎn)選擇概率函數(shù)中，建立最小化時(shí)延目標(biāo)函數(shù)；然后，根據(jù)節(jié)點(diǎn)概率函數(shù)選擇下一跳節(jié)點(diǎn)，最終找到一條最佳信號(hào)傳輸路徑。仿真結(jié)果表明，相比DVTR[6]算法和IACO[12]算法,ACO-PRA算法不僅在網(wǎng)絡(luò)吞吐量上有較大提高，而且在平均時(shí)延性能上也有明顯的改善。

1 系統(tǒng)模型

1.1 衛(wèi)星網(wǎng)絡(luò)模型

以LEO衛(wèi)星為例，建立LEO衛(wèi)星網(wǎng)絡(luò)模型如圖1a所示。該系統(tǒng)由若干顆LEO衛(wèi)星組成，運(yùn)用分時(shí)方法將衛(wèi)星運(yùn)轉(zhuǎn)周期T劃分為n個(gè)時(shí)間片Δt，如圖1b所示。在每個(gè)時(shí)間片內(nèi)，衛(wèi)星網(wǎng)絡(luò)可以看做一個(gè)靜態(tài)的無(wú)向圖G=(V,E)。其中，V=N×M表示衛(wèi)星星座中共有分布于N條衛(wèi)星軌道，每條軌道有M顆衛(wèi)星，任意時(shí)間片內(nèi)可以連通的衛(wèi)星節(jié)點(diǎn)集合，E表示衛(wèi)星間的星間鏈路ISL。星間鏈路可分為兩類(lèi)：軌道內(nèi)的星間鏈路(Intra-plane ISL)和軌道間的星間鏈路(Inter-plane ISL)。同一軌道內(nèi)的衛(wèi)星的相對(duì)位置變化比較小，所以鏈路可以長(zhǎng)期保持連通；而不同軌道內(nèi)的衛(wèi)星之間的距離和視角動(dòng)態(tài)變化，ISL很難長(zhǎng)時(shí)間保持，經(jīng)常會(huì)發(fā)生臨時(shí)性的中斷。設(shè)每個(gè)時(shí)間片Δt取得足夠小，星際鏈路長(zhǎng)度和連通關(guān)系的改變僅在每個(gè)Δt的開(kāi)始時(shí)刻t0,t1,…或tn發(fā)生。因此，動(dòng)態(tài)的衛(wèi)星網(wǎng)絡(luò)拓?fù)浔浑x散化為一系列靜態(tài)網(wǎng)絡(luò)拓?fù)溥B通圖。

圖1 系統(tǒng)模型Fig.1 System model

1.2 星間可見(jiàn)性

由于衛(wèi)星圍繞地球周期性地運(yùn)轉(zhuǎn)，任意2顆衛(wèi)星vi,vj之間的可見(jiàn)性也隨著衛(wèi)星運(yùn)行時(shí)間的變化而改變，造成星間通信鏈路頻繁切換，導(dǎo)致傳統(tǒng)的蟻群算法計(jì)算得到的結(jié)果不能保證是最優(yōu)解。因此，分析星間可見(jiàn)性、獲得星間連接及距離信息是進(jìn)行衛(wèi)星網(wǎng)絡(luò)中動(dòng)態(tài)路由算法設(shè)計(jì)的必要環(huán)節(jié)。

星間可見(jiàn)性幾何模型如圖2所示，設(shè)地球半徑為R，衛(wèi)星軌道高度為r，大氣層高度為h，任意2顆衛(wèi)星vi與vj之間的通信鏈路距離為L(zhǎng)ij。從地球遮擋和大氣影響考慮，星—星可見(jiàn)性條件如(1)式所示

(1)

圖2 星間可見(jiàn)性的幾何模型Fig.2 Geometry model of inter satellite visibility

2 ACO-PRA算法總體描述

2.1 問(wèn)題描述

衛(wèi)星網(wǎng)絡(luò)拓?fù)涑手芷诳深A(yù)測(cè)性、時(shí)刻動(dòng)態(tài)變化，這是不同于傳統(tǒng)地面網(wǎng)絡(luò)的主要特點(diǎn)。傳統(tǒng)蟻群算法，通過(guò)概率函數(shù)選擇下一跳節(jié)點(diǎn)，具有平衡網(wǎng)絡(luò)負(fù)載與避免網(wǎng)絡(luò)發(fā)生擁塞等優(yōu)點(diǎn)。但是，LEO衛(wèi)星上的資源有限，一旦發(fā)射硬件設(shè)施很難改善；同時(shí)，當(dāng)每個(gè)節(jié)點(diǎn)都選擇最優(yōu)節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)時(shí)，容易產(chǎn)生星間鏈路使用沖突的問(wèn)題，引起數(shù)據(jù)包傳輸時(shí)延增大，降低網(wǎng)絡(luò)性能。因此，地面網(wǎng)絡(luò)中成熟的蟻群算法不能直接地運(yùn)用在衛(wèi)星網(wǎng)絡(luò)中。

傳統(tǒng)蟻群算法的問(wèn)題分析如圖3所示，當(dāng)信息從源節(jié)點(diǎn)S傳輸?shù)侥康墓?jié)點(diǎn)D時(shí)，節(jié)點(diǎn)A、節(jié)點(diǎn)B與節(jié)點(diǎn)C是t1時(shí)刻與源節(jié)點(diǎn)S相鄰的節(jié)點(diǎn)集。源節(jié)點(diǎn)S發(fā)送多個(gè)數(shù)據(jù)包時(shí)，在Δt的連通時(shí)間片內(nèi)不能完全將數(shù)據(jù)包轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)D。因此，源節(jié)點(diǎn)S在t1時(shí)刻轉(zhuǎn)發(fā)部分?jǐn)?shù)據(jù)包到節(jié)點(diǎn)A，源節(jié)點(diǎn)剩余數(shù)據(jù)包S剩。隨著衛(wèi)星運(yùn)行時(shí)間的變化，節(jié)點(diǎn)E與節(jié)點(diǎn)F是ti時(shí)刻與節(jié)點(diǎn)D相鄰的節(jié)點(diǎn)。此時(shí)，可能會(huì)發(fā)生源節(jié)點(diǎn)S剩、節(jié)點(diǎn)E與節(jié)點(diǎn)F同時(shí)向目的節(jié)點(diǎn)D轉(zhuǎn)發(fā)數(shù)據(jù)包。本文假設(shè)目的節(jié)點(diǎn)D在Δt連通時(shí)間片內(nèi)只能接受某一個(gè)節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包。由于連通時(shí)間有限，在單個(gè)時(shí)間片內(nèi)每條ISL只能接收部分?jǐn)?shù)據(jù)包，選擇合適的ISL以便在最短的時(shí)間內(nèi)將全部的數(shù)據(jù)包及時(shí)地轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)。

圖3 傳統(tǒng)蟻群算法的問(wèn)題分析Fig.3 Problems analysis of traditional ant colony algorithm

因此，傳統(tǒng)的蟻群算法應(yīng)用在衛(wèi)星時(shí)變網(wǎng)絡(luò)中時(shí)，會(huì)因星間持續(xù)可見(jiàn)的連通時(shí)間頻繁周期性的變化導(dǎo)致單個(gè)時(shí)間片無(wú)法將數(shù)據(jù)包全部傳輸?shù)侥康墓?jié)點(diǎn)的問(wèn)題。

2.2 建立目標(biāo)函數(shù)

在ACO-PRA算法中，為了保證數(shù)據(jù)包傳輸?shù)膶?shí)時(shí)性及避免鏈路發(fā)生擁塞，將鏈路容量和星間鏈路距離2個(gè)性能因素引入到蟻群算法的節(jié)點(diǎn)選擇概率函數(shù)中，建立最小化時(shí)延目標(biāo)函數(shù)。

假設(shè)P={v0,v1,…,vd|v0,v1,…,vd∈V}是衛(wèi)星網(wǎng)絡(luò)中從源節(jié)點(diǎn)v0到目的節(jié)點(diǎn)vd中的某一條路徑，并用權(quán)值W來(lái)表示為

?L(vi,vi+1)∈E

(2)

衛(wèi)星網(wǎng)絡(luò)拓?fù)涑尸F(xiàn)快速地動(dòng)態(tài)時(shí)變性，因此，任意時(shí)間片內(nèi)的拓?fù)浣Y(jié)構(gòu)各不相同，進(jìn)而星間鏈路的連接情況也不同，用(3)式來(lái)表述衛(wèi)星網(wǎng)絡(luò)中任意2顆衛(wèi)星vi和vj間的連接情況。

(3)

(3)式中，(Ni,Nj)∈N,(Mi,Mj)∈M。

用矩陣C(t)表示任意2顆衛(wèi)星vi和vj之間鏈路上的業(yè)務(wù)流，如(4)式所示。

(4)

為了更明確地表達(dá)衛(wèi)星網(wǎng)絡(luò)中從源節(jié)點(diǎn)v0到目的節(jié)點(diǎn)vd帶有權(quán)值W的路徑P，用(5)式來(lái)表示每條鏈路的成本。

Dlij=ω1Tij+ω2Qij

(5)

在ACO-PRA算法中，從源節(jié)點(diǎn)v0到目的節(jié)點(diǎn)vd的路徑P應(yīng)滿足(6)—(8)式中的約束條件。

min (i,j)∈pRBi,j≥B

(6)

?Link(i,j)vi,j=vj,i=1,(i,j)∈p

(7)

? 0

(8)

(6)式中，RBi,j為任意2顆衛(wèi)星vi和vj間通信鏈路上的剩余帶寬，且RBmax=BW，B為鏈路傳輸數(shù)據(jù)包所需的最小帶寬。(6)式用以保證數(shù)據(jù)包能可靠地進(jìn)行傳輸；(7)式表明衛(wèi)星間相鄰可見(jiàn)，能夠滿足數(shù)據(jù)傳輸要求；(8)式表示星間鏈路上業(yè)務(wù)流需要滿足的約束條件。

2.3 ACO-PRA算法描述

ACO-PRA算法流程如圖4所示。下面將在2.2節(jié)建立目標(biāo)函數(shù)的優(yōu)化模型基礎(chǔ)上，進(jìn)一步詳細(xì)地闡述ACO-PRA算法的具體步驟。算法流程具體如下。

步驟1虛擬化網(wǎng)絡(luò)拓?fù)?。將衛(wèi)星運(yùn)行周期均勻分為若干個(gè)時(shí)間間隔相等的時(shí)間片，根據(jù)星間可見(jiàn)性的計(jì)算模型分析衛(wèi)星間的連接及距離信息，從而生成任意時(shí)間片的網(wǎng)絡(luò)拓?fù)溥B通圖。

步驟2選擇相鄰節(jié)點(diǎn)集。選擇任意一時(shí)間片內(nèi)生成的拓?fù)溥B通圖。任意節(jié)點(diǎn)vi為源節(jié)點(diǎn)S,vj為目的節(jié)點(diǎn)，尋找與S節(jié)點(diǎn)相鄰的節(jié)點(diǎn)集合A。

步驟3判斷目的節(jié)點(diǎn)。若下一跳節(jié)點(diǎn)vn是目的節(jié)點(diǎn)，且目的節(jié)點(diǎn)vd在與源節(jié)點(diǎn)S相鄰的節(jié)點(diǎn)集合A中，則直接轉(zhuǎn)發(fā)數(shù)據(jù)包，并存儲(chǔ)當(dāng)前時(shí)刻尋找到的路由路徑；否則，進(jìn)行步驟4。

步驟4計(jì)算概率函數(shù)。如果目的節(jié)點(diǎn)vd不在與源節(jié)點(diǎn)S相鄰的節(jié)點(diǎn)集合A中，用(9)式計(jì)算同時(shí)滿足時(shí)延帶寬和鏈路容量要求的下一跳節(jié)點(diǎn)，并轉(zhuǎn)發(fā)數(shù)據(jù)包。之后重復(fù)步驟3。

步驟5最佳信號(hào)傳輸路徑。遍歷所有衛(wèi)星節(jié)點(diǎn)。存儲(chǔ)所有數(shù)據(jù)包到達(dá)目的節(jié)點(diǎn)vd的路由路徑，并比較每條路徑，找到最佳信號(hào)傳輸路徑。

圖4 ACO-PRA算法流程圖Fig.4 Flow chart of ACO-PRA algorithm

3 基于概率函數(shù)的節(jié)點(diǎn)選擇

由2.3節(jié)描述可知，ACO-PRA算法的基本流程：①綜合考慮時(shí)延帶寬和鏈路容量，建立最小時(shí)延目標(biāo)函數(shù)；②將鏈路容量和星間距離因子引入到傳統(tǒng)ACO算法的節(jié)點(diǎn)概率函數(shù)中，生成新的節(jié)點(diǎn)概率函數(shù)；③運(yùn)用生成的節(jié)點(diǎn)概率函數(shù)計(jì)算下一跳，最終尋找到最佳傳輸信號(hào)的路徑。

下面，將重點(diǎn)針對(duì)ACO-PRA算法中如何選擇下一跳的過(guò)程進(jìn)行詳細(xì)地闡述。

3.1 基于ACO的節(jié)點(diǎn)概率函數(shù)

在ACO-PRA算法中，發(fā)送數(shù)據(jù)包的每個(gè)衛(wèi)星節(jié)點(diǎn)定義為前向Ant，且前向Ant負(fù)責(zé)收集節(jié)點(diǎn)信息，當(dāng)前向Ant到達(dá)目的節(jié)點(diǎn)時(shí)，會(huì)立即按照原路徑返回到源節(jié)點(diǎn)，同時(shí)Ant會(huì)釋放一種信息素τ，并用路徑上信息素τ濃度的大小來(lái)表示路徑的遠(yuǎn)近。結(jié)合傳統(tǒng)ACO中節(jié)點(diǎn)概率函數(shù)，ACO-PRA綜合考慮了星間鏈路容量和星間距離2個(gè)影響因子。因此，前向節(jié)點(diǎn)vi在時(shí)刻t選擇節(jié)點(diǎn)vj作為下一跳節(jié)點(diǎn)的概率公式表示為

(9)

(10)

當(dāng)數(shù)據(jù)包遍歷完所有路徑后，節(jié)點(diǎn)i和節(jié)點(diǎn)j之間鏈路上的信息素就會(huì)更新。因此，在(t+1)時(shí)刻節(jié)點(diǎn)i和節(jié)點(diǎn)j之間鏈路上的信息素用(11)式來(lái)計(jì)算

τij(t+1)=(1-ρ)τij(t)+Δτij(t)

(11)

(12)

3.2 下一跳節(jié)點(diǎn)選擇過(guò)程

源節(jié)點(diǎn)S發(fā)送數(shù)據(jù)包的情況可分為2種：①若下一跳節(jié)點(diǎn)為目的節(jié)點(diǎn)，則直接將數(shù)據(jù)包轉(zhuǎn)發(fā)；②若不是，數(shù)據(jù)包將需經(jīng)過(guò)若干個(gè)時(shí)間片才能轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)。因而，數(shù)據(jù)包在傳輸過(guò)程中發(fā)生鏈路選擇的問(wèn)題，即節(jié)點(diǎn)vi在[ti,ti+1]時(shí)間片內(nèi)不能將m個(gè)數(shù)據(jù)包完全轉(zhuǎn)發(fā)到下一跳節(jié)點(diǎn)vm，節(jié)點(diǎn)vi就剩余m剩個(gè)數(shù)據(jù)包需等到下一個(gè)連通時(shí)間片內(nèi)轉(zhuǎn)發(fā)。如圖5所示，在某個(gè)時(shí)間片內(nèi)會(huì)發(fā)生3個(gè)節(jié)點(diǎn)同時(shí)向節(jié)點(diǎn)D轉(zhuǎn)發(fā)數(shù)據(jù)包。

節(jié)點(diǎn)A、節(jié)點(diǎn)B與節(jié)點(diǎn)C是t時(shí)刻與目的點(diǎn)D相鄰的節(jié)點(diǎn)集。假設(shè)鏈路LAD在時(shí)間片[tA,tD]內(nèi)的連通時(shí)間為tAD,鏈路LBD在時(shí)間片[tB,tD]內(nèi)的連通時(shí)間為tBD，鏈路LCD在時(shí)間片[tC,tD]內(nèi)的連通時(shí)間為tCD；當(dāng)連通時(shí)間tAD>tBD>tCD時(shí)，選擇鏈路LAD轉(zhuǎn)發(fā)數(shù)據(jù)包；當(dāng)連通時(shí)間tAD=tBD>tCD或者tAD

圖5 某一時(shí)間片數(shù)據(jù)包的轉(zhuǎn)發(fā)示例Fig.5 Example of forwarding packet in a time slice

4 仿真分析

為了驗(yàn)證ACO-PRA算法性能，本文采用衛(wèi)星工具包(satellite tool kit，STK)和MATLAB進(jìn)行了聯(lián)合仿真。在相同負(fù)載的情況下，與LEO衛(wèi)星網(wǎng)絡(luò)中典型的路由算法DVTR，IACO在吞吐量、平均時(shí)延等性能方面的進(jìn)行比較分析。

仿真參數(shù)設(shè)置如表1所示，地球半徑為R=6 371 km，LEO衛(wèi)星星座采用walker衛(wèi)星星座，24顆衛(wèi)星均勻分布在3個(gè)軌道平面，軌道傾斜角為60°，每顆衛(wèi)星有2條星間鏈路、2條星內(nèi)鏈路，其中，ρ=0.5[13]。

LEO衛(wèi)星網(wǎng)絡(luò)中的吞吐量性能如圖6所示。由圖6可知，3種算法的吞吐量都隨著算法迭代次數(shù)的增加而增大，ACO-PRA算法吞吐量性能呈現(xiàn)優(yōu)勢(shì)，這是由于在衛(wèi)星節(jié)點(diǎn)高速移動(dòng)的情況下，造成網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)頻繁變化，DVTR算法不能及時(shí)地更新路由，且路由路徑是在地面預(yù)先計(jì)算后上傳給衛(wèi)星，并沒(méi)有解決由于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化而引起的鏈路頻繁切換的重路由問(wèn)題，從而導(dǎo)致在同一時(shí)刻，采用ACO-PRA算法的網(wǎng)絡(luò)在相同負(fù)載情況下收到的數(shù)據(jù)包數(shù)更多。LEO衛(wèi)星網(wǎng)絡(luò)中的平均時(shí)延性能如圖7所示，同一時(shí)刻，IACO算法的吞吐量性能總是低于ACO-PRA算法。因?yàn)镮ACO算法并沒(méi)有考慮鏈路的剩余帶寬；同時(shí)，IACO算法總是尋找最優(yōu)路徑，造成最優(yōu)路徑上業(yè)務(wù)流過(guò)重而部分?jǐn)?shù)據(jù)包丟失。因此，相比較于ACO-PRA算法，其吞吐量有所降低。

表1 仿真參數(shù)設(shè)置Tab.1 Simulation parameter settings

圖6 LEO衛(wèi)星網(wǎng)絡(luò)中的吞吐量性能Fig.6 Throughput performance in LEO satellite networks

由圖7可得，隨著算法迭代次數(shù)的增加，IACO算法和ACO-PRA算法的平均時(shí)延性能明顯優(yōu)于DVTR算法。這是因?yàn)樾l(wèi)星網(wǎng)絡(luò)拓?fù)涑矢咚賱?dòng)態(tài)的變化，ISLs頻繁快速切換，當(dāng)衛(wèi)星網(wǎng)絡(luò)中某些星間鏈路斷開(kāi)或切換，DVTR算法不能根據(jù)網(wǎng)絡(luò)當(dāng)前的狀態(tài)及時(shí)地進(jìn)行路由更新，從而使得部分星間鏈路負(fù)載加重而發(fā)生擁塞，數(shù)據(jù)包排隊(duì)時(shí)延增大，需等到下一個(gè)連通時(shí)間片才能將數(shù)據(jù)包轉(zhuǎn)發(fā)到下一跳節(jié)點(diǎn)。因此，DVTR算法的平均時(shí)延要高于ACO-PRA算法。而IACO算法的平均時(shí)延稍高于ACO-PRA算法，這是由于IACO算法沒(méi)有考慮鏈路剩余帶寬和鏈路容量，只是單一的根據(jù)鏈路上信息素大小來(lái)選擇下一跳，容易造成最優(yōu)路徑業(yè)務(wù)流增大，鏈路中排隊(duì)等待轉(zhuǎn)發(fā)的包增多，這樣就增加了IACO算法的時(shí)延性能。

圖7 LEO衛(wèi)星網(wǎng)絡(luò)中的平均時(shí)延性能Fig.7 Average delay performance in LEO satellite networks

LEO衛(wèi)星網(wǎng)絡(luò)中的丟包性能如圖8所示。從圖8中可看出， ACO-PRA算法和IACO算法的丟包率性能均逐漸降低并趨于穩(wěn)定，而DVTR算法的丟包率性能增大到一定幅度而趨于平穩(wěn)。這是因?yàn)镈VTR算法在鏈路的切換或斷開(kāi)時(shí)，路由表不能根據(jù)網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)特性及時(shí)地調(diào)整路由方案，源節(jié)點(diǎn)計(jì)算的路由失效而造成數(shù)據(jù)包的丟失數(shù)增大。同時(shí)，IACO算法的丟包率總是低于ACO-PRA算法。因?yàn)镮ACO算法并沒(méi)有考慮到衛(wèi)星間的星間距離和ISLs的鏈路容量，在同樣的連通拓?fù)浣Y(jié)構(gòu)內(nèi)，ACO-PRA算法能夠滿足業(yè)務(wù)流要求，優(yōu)先選擇鏈路剩余容量大的衛(wèi)星節(jié)點(diǎn)，保證數(shù)據(jù)包及時(shí)地傳輸?shù)侥康墓?jié)點(diǎn)。此外，IACO算法總是尋找最優(yōu)路徑，導(dǎo)致最優(yōu)路徑上的業(yè)務(wù)流增大而發(fā)生擁塞，目的節(jié)點(diǎn)無(wú)法準(zhǔn)確地接受而造成數(shù)據(jù)包丟失。因此，隨著算法迭代次數(shù)的增加，IACO算法的丟包率總是高于ACO-PRA算法。

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

針對(duì)衛(wèi)星網(wǎng)絡(luò)拓?fù)鋾r(shí)變、鏈路連接性差等問(wèn)題，提出了一種基于蟻群優(yōu)化的概率路由算法(ACO-PRA)。首先，將網(wǎng)絡(luò)拓?fù)渲芷诰鶆蚍譃槿魝€(gè)時(shí)間片而生成不同時(shí)刻的拓?fù)溥B通圖；其次，將星間鏈路帶寬和鏈路容量作為約束條件建立優(yōu)化模型；最后，根據(jù)生成的節(jié)點(diǎn)概率函數(shù)選擇下一跳衛(wèi)星節(jié)點(diǎn)，找到一條滿足約束條件的最佳傳輸路徑。仿真結(jié)果表明，所提出的ACO-PRA算法不僅能夠降低網(wǎng)絡(luò)平均端到端時(shí)延和丟包率，還能提高網(wǎng)絡(luò)吞吐量。

圖8 LEO衛(wèi)星網(wǎng)絡(luò)中的丟包率性能Fig.8 Packet loss rate performance in LEO satellite networks

參考文獻(xiàn)：

[1] ARANITI G, BEZIRGIRGIANNIDIS N, BIRRANE E, et al. Contact graph routing in DTN space networks: overview, enhancements and performance[J]. IEEE Communications Magazine, 2015, 53(3):38-46.

[2] LIU Ziluan, HAN Jiangxue, WANG Ying, et al. Performance analysis of routing algorithms in satellite network under node failure scenarios[C]//IEEE Global Communications Conference. Austin, TX: IEEE Press, 2014:2838-2843.

[3] 盧勇,趙有健,孫富春.衛(wèi)星網(wǎng)絡(luò)路由技術(shù)[J]. 軟件學(xué)報(bào), 2014, 25(5):1085-1100.

LU Yong, ZHAO Youjian, SUN Fuchun. Routing techniques on satellite networks[J]. Journal of Software,2014,25(5):1085-1100.

[4] CHANG H S, KIM B W, CHANG L, et al. FSA-based link assignment and routing in low-earth orbit satellite networks [J]. IEEE Transactions on Vehicular Technology,1998, 47(3):1037-1048.

[5] PAPAPETROU E, PAVLIDOU F N. Distributed Load-Aware Routing in LEO Satellite Networks[C]//IEEE Global Telecommunications Conference. New Orleans, LO: IEEE Press, 2008:1-5.

[6] HUSSEIN M, JAKLLARI G, PAILLASSB B. On routing for extending satellite service life in LEO satellite networks[C]//IEEE Global Communications Conference.Austin, TX: IEEE Press, 2014:2832-2837.

[7] YANG Yuan, XU Mingwei, WANG Dan, et al. Towards Energy-Efficient Routing in Satellite Networks[J]. IEEE Journal on Selected Areas in Communications, 2016, 34(12):3869-3886.

[8] WU Zhaofeng, HU Guyu, JIN Fenglin, et al. Agent-based dynamic routing in the packet-switched LEO satellite networks[C]//IEEE International Conference on Wireless Communications & Signal Processing. Nanjing, China: IEEE Press, 2015:1-6.

[9] 楊力,孫晶,潘成勝.基于多目標(biāo)決策的LEO衛(wèi)星網(wǎng)絡(luò)多業(yè)務(wù)路由算法[J]. 通信學(xué)報(bào), 2016, 37(10):25-32.

YANG Li, SUN Jing, PAN Chengsheng. LEO multi-service routing algorithm based on Multi-objective decision making[J]. Journal of Communications,2016, 37(10):25-32.

[10] DORIGO M, MANIEZZO V, COLORNI A.The Ant System: Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1996,26(1):29 - 41.

[11] LONG Fei, SUN Fuchun. An Improved Ant Colony Algorithm and Its Application In Routing Computation of Satellite Networks[C]//IEEE IMACS Multiconference on Computational Engineering in Systems Applications. Beijing: IEEE Press, 2006:1567-1573.

[12] GAO Zihe, GUO Qing, WANG Ping. An Adaptive Routing Based on an Improved Ant Colony Optimization in LEO Satellite Networks[C]//IEEE International Conference on Machine Learning and Cybernetics. Hong Kong, China: IEEE Press, 2007:1041-1044.

[13] WANG Houtian, ZHANG Qi, XIN Xiangjun,et al. Cross-layer design and ant-colony optimization based routing algorithm for low earth orbit satellite networks[J]. China Communications, 2013, 10(10):37-46.

[14] BHATIA A, JOHARI R. Genetically optimized ACO inspired PSO algorithm for DTNs[C]//IEEE 3rd International Conference on Reliability,Infocom Technologies and Optimization. Noida: IEEE Press, 2015:1-6.

[15] MOHAMED A, RACHID E K, BELLAFKIH M, et al.AntProPHET: A New Routing Method for Delay Tolerant Networks [C]//Mediterranean Microwave Symposium. Marrakech: IEEE Press,2015:1-6.