面向LEO衛(wèi)星網(wǎng)絡(luò)的高效路由算法 *

雷援杰 ，唐 宏，馬樞清，李 藝

(重慶郵電大學(xué) a.通信與信息工程學(xué)院；b.移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

0 引 言

隨著通信技術(shù)的發(fā)展，天地一體化網(wǎng)絡(luò)已成為下一代通信的發(fā)展趨勢(shì)。作為天基骨干網(wǎng)絡(luò)的低軌(Low Earth Orbit，LEO)衛(wèi)星網(wǎng)絡(luò)因?yàn)榫哂腥蚋采w、可以忽略地形限制進(jìn)行點(diǎn)對(duì)點(diǎn)通信等優(yōu)點(diǎn)而成為研究的熱點(diǎn)[1]。

LEO衛(wèi)星網(wǎng)絡(luò)具有時(shí)變的動(dòng)態(tài)拓?fù)涮卣?，這是不能直接將地面網(wǎng)絡(luò)路由算法直接遷移到衛(wèi)星網(wǎng)絡(luò)上的主要原因[2]。隨著SpaceX的starlink計(jì)劃的推進(jìn)[3]，衛(wèi)星組網(wǎng)規(guī)模變得更加龐大，成為未來衛(wèi)星網(wǎng)絡(luò)發(fā)展的一種趨勢(shì)，但是衛(wèi)星星上存儲(chǔ)以及計(jì)算能力有限[4]，所以高效簡(jiǎn)潔的路由算法成為衛(wèi)星網(wǎng)絡(luò)的一個(gè)研究重點(diǎn)。

衛(wèi)星路由是衛(wèi)星通信中的核心。針對(duì)該問題，DT-DVTR(Discrete Time Dynamic Virtual Topology Routing)算法[5]利用快照的思想，將衛(wèi)星隨時(shí)間連續(xù)變化的動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)離散化，并且在每個(gè)快照內(nèi)近似認(rèn)為網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是靜止不變的，然后將在線下利用Dijkstra算法尋找出的最短路徑存儲(chǔ)在衛(wèi)星上，當(dāng)有數(shù)據(jù)轉(zhuǎn)發(fā)需求時(shí)，查詢路由表完成數(shù)據(jù)轉(zhuǎn)發(fā)。但是該算法并沒有應(yīng)對(duì)突發(fā)流量的能力。文獻(xiàn)[6-7]通過對(duì)服務(wù)質(zhì)量(Quality of Service,QoS)指標(biāo)進(jìn)行最優(yōu)化建模，通過蟻群算法計(jì)算出滿足多種QoS約束的最優(yōu)路徑。盡管蟻群算法能夠求解出一條或者多條滿足QoS指標(biāo)的路徑，但是相對(duì)于傳統(tǒng)算法，計(jì)算復(fù)雜度相對(duì)較高。

最短路徑算法是表驅(qū)動(dòng)路由中的重要組成部分。廣度優(yōu)先搜索(Breadth First Search,BFS)算法可以解決無權(quán)圖的最短路徑問題。Dijkstra算法擁有較低的復(fù)雜度，但是不能處理負(fù)權(quán)邊問題。Bellman-Ford算法可以解決負(fù)權(quán)邊的最短路徑問題，卻擁有相對(duì)較高的時(shí)間復(fù)雜度[8]。隨著啟發(fā)式算法的發(fā)展，一些仿生優(yōu)化算法也常被應(yīng)用到尋找?guī)Ъs束條件的最優(yōu)路徑中。文獻(xiàn)[9]將路徑距離作為蟻群算法的啟發(fā)式因子從而計(jì)算出螞蟻移動(dòng)到相鄰下一跳的轉(zhuǎn)移概率，最后通過信息素濃度選出滿足約束條件的最優(yōu)路徑。文獻(xiàn)[10]將待選路徑編碼成可變長(zhǎng)度的字符串，將路徑的權(quán)值和作為適應(yīng)度函數(shù)，利用遺傳算法尋找最優(yōu)路徑。啟發(fā)式算法的優(yōu)點(diǎn)在于能夠?qū)ふ覔碛屑s束條件的最優(yōu)路徑，但是其時(shí)間復(fù)雜度一般比傳統(tǒng)的最短路徑算法高。

本文提出一種基于BFS的最優(yōu)路徑算法en-BFS(Enhance Breadth First Search)，將跳數(shù)作為最優(yōu)路徑的主要衡量指標(biāo)尋找出最小跳數(shù)路徑集合，然后通過在最小跳數(shù)集合中篩選出權(quán)值和最小的路徑作為目標(biāo)路徑完成數(shù)據(jù)的轉(zhuǎn)發(fā)，極大地降低了路由算法復(fù)雜度以及衛(wèi)星的計(jì)算資源。為了克服en-BFS算法在網(wǎng)絡(luò)負(fù)載較輕時(shí)時(shí)延相對(duì)偏大的缺點(diǎn)，提出了NCARA(Network Congestion-Aware Routing Algorithm)路由策略，即在路由時(shí)，節(jié)點(diǎn)會(huì)感知網(wǎng)絡(luò)擁塞程度，當(dāng)網(wǎng)絡(luò)處于非擁塞狀態(tài)時(shí)，采用Dijkstra算法尋路；當(dāng)網(wǎng)絡(luò)擁塞時(shí)，采用en-BFS算法尋路，使得網(wǎng)絡(luò)性能能夠得到保障。

1 系統(tǒng)模型

本文的研究對(duì)象為極軌道衛(wèi)星星座，并且將網(wǎng)絡(luò)建模為G=(V,E)，V=N×M表示當(dāng)前衛(wèi)星星座中有N個(gè)軌道到平面，每個(gè)軌道平面有M顆衛(wèi)星。為了方便后續(xù)的敘述，每個(gè)節(jié)點(diǎn)v用(xv，yv)來表示該節(jié)點(diǎn)是第xv軌道平面的第yv顆衛(wèi)星。并且對(duì)于極軌道衛(wèi)星星座而言，每顆衛(wèi)星可以建立4條星間鏈路，包括不同軌道平面相鄰衛(wèi)星之間建立的2條軌道間鏈路以及相同軌道平面相鄰衛(wèi)星之間建立的2條軌道內(nèi)鏈路。在第一個(gè)軌道平面與最后一個(gè)軌道平面以及處于極地區(qū)域的相鄰軌道的衛(wèi)星之間，由于衛(wèi)星相對(duì)運(yùn)動(dòng)速度過快，故一般不存在軌道間鏈路。所以，由于衛(wèi)星周期性地進(jìn)出極地區(qū)域，會(huì)導(dǎo)致衛(wèi)星軌道間鏈路周期性地?cái)嚅_與連接，從而使得衛(wèi)星網(wǎng)絡(luò)拓?fù)鋼碛袆?dòng)態(tài)變化的特征。

為了屏蔽衛(wèi)星拓?fù)渥兓膭?dòng)態(tài)性，本文采用虛擬拓?fù)洳呗?，將衛(wèi)星連續(xù)變化的動(dòng)態(tài)拓?fù)渫ㄟ^采樣的方式抽象成n個(gè)離散的時(shí)間片，只要相鄰時(shí)間片的間隔Δt足夠小，便可以認(rèn)為每個(gè)時(shí)間片內(nèi)的拓?fù)涫庆o止不變的。所以在每個(gè)快照范圍內(nèi)，節(jié)點(diǎn)可以近似抽象為一個(gè)二維網(wǎng)格拓?fù)洹?/p>

2 算法總體架構(gòu)

為了在降低尋路算法復(fù)雜度的同時(shí)保證網(wǎng)絡(luò)性能,本文提出一種針對(duì)網(wǎng)絡(luò)的擁塞情況選擇不同的尋路算法尋路的路由策略——NCARA。

NCARA的基本思想如下：在每個(gè)節(jié)點(diǎn)泛洪自身信息的時(shí)候，會(huì)將該節(jié)點(diǎn)的擁塞情況泛洪出去，節(jié)點(diǎn)擁塞情況可以利用該節(jié)點(diǎn)的待處理數(shù)據(jù)隊(duì)列長(zhǎng)度進(jìn)行判斷。設(shè)定閾值β，當(dāng)隊(duì)列長(zhǎng)度大于β時(shí)判定該節(jié)點(diǎn)處于擁塞狀態(tài)，否則該節(jié)點(diǎn)為非擁塞節(jié)點(diǎn)。并且在每個(gè)節(jié)點(diǎn)收集網(wǎng)絡(luò)拓?fù)湫畔⒌臅r(shí)候，會(huì)統(tǒng)計(jì)擁塞節(jié)點(diǎn)總數(shù)，并根據(jù)擁塞節(jié)點(diǎn)總數(shù)來選擇不同的尋路算法。設(shè)定閾值β1和β2，當(dāng)擁塞節(jié)點(diǎn)總數(shù)小于β1時(shí)，采用Dijkstra算法尋路;當(dāng)擁塞節(jié)點(diǎn)總數(shù)大于β2時(shí)采用后文將要介紹的en-BFS算法尋路，并且β1>β2。一般β1和β2應(yīng)取不同值，主要是防止以下情況發(fā)生：假設(shè)網(wǎng)絡(luò)選取閾值一樣，則可能出現(xiàn)網(wǎng)絡(luò)的擁塞節(jié)點(diǎn)個(gè)數(shù)一直在所選取的閾值處波動(dòng)的情況，從而造成頻繁的選路算法切換。

3 en-BFS算法

3.1 en-BFS算法總體思想

en-BFS算法主要由兩部分組成，即尋找最小跳數(shù)路徑集和尋找最小權(quán)值路徑。尋找最小跳數(shù)路徑集可以通過推導(dǎo)出最小跳數(shù)路徑的節(jié)點(diǎn)所被包含的范圍完成，然后在最小跳數(shù)路徑集中通過加上松弛操作的BFS算法尋找權(quán)值和最小的路徑。

本文使用的術(shù)語定義如下：

定義1：最小跳數(shù)路徑集為從源節(jié)點(diǎn)src到目的節(jié)點(diǎn)dst的跳數(shù)和最小的路徑集合,即滿足

(1)

定義2：最小權(quán)值路徑表示在源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最條跳數(shù)路徑集中權(quán)值和最小的路徑，并且滿足

(2)

3.2 尋找最小跳數(shù)路徑集

定理1：組成最小跳數(shù)路徑集的每一條路徑的每個(gè)節(jié)點(diǎn)一定包含在源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最小矩形內(nèi)，即滿足v∈pi,pi∈mhopsetsd→xsrc≤xv≤xdes且ysrc≤yv≤ydes。

證明：如圖1所示，假設(shè)a是源節(jié)點(diǎn)，b是目的節(jié)點(diǎn)，p1={a,d,e,f,g}是矩形外的一條路徑，p2={a,b,c}是矩形內(nèi)的一條路徑。由于網(wǎng)絡(luò)拓?fù)錇橐粋€(gè)二維網(wǎng)格拓?fù)?，并且假設(shè)hop(v1,v2)表示從節(jié)點(diǎn)v1到v2的跳數(shù)，故hop(a,b)=hop(d,e)，且hop(b,c)=hop(f,g)，可得出hop(p1)>hop(p2)。除此之外，矩形外路徑也可以提前到達(dá)矩形區(qū)域內(nèi)節(jié)點(diǎn)，然后由矩形內(nèi)區(qū)域的節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)，證明過程和上面一樣。

圖1 最小跳數(shù)路徑集范圍證明

定理2：假設(shè)節(jié)點(diǎn)v和節(jié)點(diǎn)w為從源節(jié)點(diǎn)src到目的節(jié)點(diǎn)dst的一條最小跳數(shù)路徑上的兩個(gè)節(jié)點(diǎn)，并且節(jié)點(diǎn)w為節(jié)點(diǎn)v的后繼節(jié)點(diǎn)，則節(jié)點(diǎn)w一定是在相對(duì)于v朝目的節(jié)點(diǎn)靠攏的方向?？捎脭?shù)學(xué)語言描述如下：

xw=xv且(yv-yw)·(ysrc-ydst)≥0，

或者

yw=yv且(xv-xw)·(xsrc-xdst)≥0。

3.3 尋找最小權(quán)值路徑

由定理1可知，最小跳數(shù)路徑一定是在包含源節(jié)點(diǎn)和目的節(jié)點(diǎn)最小矩形中，然后可以在該矩形范圍內(nèi)采用en-BFS算法尋找權(quán)值最小的路徑。為了方便，本文權(quán)值采用傳輸時(shí)延和傳播時(shí)延的加和，如公式(3)所示：

weight=α1Pt+α2Qt。

(3)

式中：weight表示尋找路徑時(shí)的權(quán)值；Pt表示傳播時(shí)延；Qt表示傳輸時(shí)延；α1和α2分別表示傳輸時(shí)延和傳播時(shí)延的權(quán)重因子，一般α1和α2都取0.5。

3.3.1 en-BFS算法需用符號(hào)說明

接下來定義en-BFS算法需要用到的符號(hào)。定義集合Q，v∈Q表示v已經(jīng)找到最短路徑；反之，表示v沒有找到最短路徑。并且節(jié)點(diǎn)w為節(jié)點(diǎn)v的后繼節(jié)點(diǎn)，v為w的前驅(qū)節(jié)點(diǎn)，pre(v)用來記錄從源節(jié)點(diǎn)到v的最短路徑中的上一跳節(jié)點(diǎn)，dis(v)表示從源節(jié)點(diǎn)到v的最短距離，weight(v,w)表示節(jié)點(diǎn)v和w的邊的權(quán)值，隊(duì)列queue用來模擬BFS的遍歷過程，s代表源節(jié)點(diǎn)。

3.3.2 en-BFS算法具體步驟

en-BFS算法的具體步驟如下：

Step1 先將dis數(shù)組中所有值初始化為無窮大并且將源節(jié)點(diǎn)s加入隊(duì)列queue以及已訪問集合Q中，標(biāo)記該節(jié)點(diǎn)的最優(yōu)路徑已經(jīng)找到。將從源節(jié)點(diǎn)s到該節(jié)點(diǎn)的最短距離dis(s)置為0，s的上一跳pre(s)置為s。

Step2 取出queue中的第一個(gè)元素v，并且將它加入已訪問集合Q中，進(jìn)入Step 3。

Step3 將節(jié)點(diǎn)v的后繼節(jié)點(diǎn)w加入隊(duì)列queue的過程中判斷節(jié)點(diǎn)w是否可以通過節(jié)點(diǎn)v進(jìn)行轉(zhuǎn)接使得源節(jié)點(diǎn)到w的距離更小，即判斷dis(w)>dis(v)+weight(v,w)是否成立，如果成立進(jìn)入Step 4,否者進(jìn)入Step 5。

Step4 令dis(w)=dis(v)+weight(v,w)，并且將w的上一跳置為v，即pre(w)=v。

Step5 判斷所有節(jié)點(diǎn)是否全部都已經(jīng)加入到已訪問集合queue中，如果條件不滿足執(zhí)行Step 2，否則算法結(jié)束。

3.3.3 en-BFS算法偽代碼

en-BFS算法的偽代碼如下：

for eachv∈Gdo

pre(v)←0

dis(v)←∞

visited(v)←false

pre(s)←s

dis(s)←0

queue.add(s)

while queue is not empty do

v←queue.removefirst

visited.add(v)

for eachw∈ adj(v) do

ifw? visited then

if dis(v)+weight(v,w)

dis(w)←dis(v)+weight(v,w)

pre(w)←v

3.3.4 en-BFS算法正確性分析

定理3:在包含源節(jié)點(diǎn)和目的節(jié)點(diǎn)的最小矩形范圍內(nèi)用en-BFS算法尋找到的路徑一定是最小跳數(shù)路徑集中權(quán)值和最小的路徑。

證明：首先證明所尋路徑一定是最小跳數(shù)路徑。由BFS可以尋找無權(quán)圖的最短路徑可知，通過BFS對(duì)圖進(jìn)行廣度優(yōu)先遍歷尋找到的路徑一定是無權(quán)圖中的最短路徑，也即最小跳數(shù)路徑。

接下來證明所尋路徑一定是權(quán)值和最小的路徑。如圖2所示，假設(shè)源節(jié)點(diǎn)src在目的節(jié)點(diǎn)dst的左上方，由定理2可知對(duì)于最小跳數(shù)路徑中的每一個(gè)節(jié)點(diǎn)的上一跳一定是在它的左方或者它的右方。

圖2 en-BFS遍歷層次圖

圖2中，l1表示搜索的第一層，l2為第二層，依次類推。利用數(shù)學(xué)歸納法可知：

(1)當(dāng)搜索層次n=1時(shí)，從源節(jié)點(diǎn)到該節(jié)點(diǎn)v只有一條邊，即為最短路徑；

(2)當(dāng)n=k時(shí)，假設(shè)該搜索層lk上的任意一個(gè)節(jié)點(diǎn)所尋找到的路徑都為最短路徑，如圖2所示，便有dis(v1)和dis(v2)都是源節(jié)點(diǎn)到該節(jié)點(diǎn)的距離最小值；

(3)當(dāng)n=k+1時(shí)，任取lk+1上的節(jié)點(diǎn)w,并且w的上一跳一定是它的左方節(jié)點(diǎn)v1或者它的上方節(jié)點(diǎn)v2，由于dis(w)=min{(dis(v1)+weight(v1,w)),((dis(v2)+weight(v2,w)}，故對(duì)于節(jié)點(diǎn)w尋找到的路徑也一定是權(quán)值和最小的路徑。

綜上，算法正確性證明完畢。

3.3.5 en-BFS算法復(fù)雜度分析

由于en-BFS算法的核心思想是廣度優(yōu)先搜索算法,即遍歷圖中的所有邊和所有的點(diǎn)，故en-BFS的時(shí)間復(fù)雜度為O(V+E)，V為圖的節(jié)點(diǎn)個(gè)數(shù)，E為圖的邊的數(shù)目。

表1是常用的尋找最短路徑算法的復(fù)雜度，可以看出Dijkstra算法是和Bellman-Ford算法的時(shí)間復(fù)雜度都約等于O(V2)，而蟻群算法的復(fù)雜度和螞蟻數(shù)量m以及迭代次數(shù)T有關(guān)，但是它至少也是一個(gè)復(fù)雜度為O(V2)的算法。

表1 算法復(fù)雜度對(duì)比

綜上，本文算法為一個(gè)線性復(fù)雜度的算法，并且相比Dijkstra算法以及傳統(tǒng)的最短路徑算法其復(fù)雜度都有明顯降低。

4 仿真分析

4.1 仿真建立

本文采用衛(wèi)星工具包(Satellite Tool Kit,STK)模擬生成銥星系統(tǒng)的軌道參數(shù)，然后導(dǎo)入到OPNET中，通過在OPNET中的網(wǎng)絡(luò)域、節(jié)點(diǎn)域、進(jìn)程域編程實(shí)現(xiàn)網(wǎng)絡(luò)仿真[11]。

在銥星系統(tǒng)中，一共有6個(gè)軌道平面，每個(gè)軌道平面上有12顆衛(wèi)星，軌道高度為780 km，每顆衛(wèi)星有4條星間鏈路(第一個(gè)軌道平面和最后一個(gè)軌道平面的衛(wèi)星以及極區(qū)內(nèi)衛(wèi)星除外)。由于天線原因，第一個(gè)軌道平面和最后一個(gè)軌道平面之間不存在軌道間鏈路，同時(shí)極區(qū)內(nèi)衛(wèi)星之間不存在軌道間鏈路，仿真設(shè)置極區(qū)邊界值為70°。為了方便研究，衛(wèi)星系統(tǒng)的軌道傾角設(shè)置為90°。為了屏蔽衛(wèi)星網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)性，本文采用虛擬拓?fù)涞姆绞?。由于全文?duì)比算法都是表驅(qū)動(dòng)路由的形式，故設(shè)置更新路由表的時(shí)間間隔為10 s。表2是仿真所用衛(wèi)星系統(tǒng)的參數(shù)。

表2 仿真參數(shù)設(shè)置

本文中衛(wèi)星的軌道間鏈路和軌道內(nèi)鏈路帶寬都設(shè)置為1 Mb/s，每個(gè)衛(wèi)星節(jié)點(diǎn)的等待隊(duì)列長(zhǎng)度為100 Mb，并且設(shè)定β為75 Mb，當(dāng)節(jié)點(diǎn)的隊(duì)列長(zhǎng)度超過β時(shí)便判定該節(jié)點(diǎn)為擁塞節(jié)點(diǎn)，并且當(dāng)節(jié)點(diǎn)隊(duì)列中的數(shù)據(jù)包總比特?cái)?shù)超過隊(duì)列總長(zhǎng)度100 Mb時(shí)便丟棄該數(shù)據(jù)包。β1設(shè)置為36，β2設(shè)置為30，當(dāng)衛(wèi)星擁塞節(jié)點(diǎn)個(gè)數(shù)小于36時(shí)采用Dijkstra算法尋找最短路徑，當(dāng)擁塞節(jié)點(diǎn)個(gè)數(shù)大于30時(shí)采用en-BFS算法尋路。

4.2 仿真結(jié)果分析

在仿真實(shí)驗(yàn)中，我們選取了DT-DVTR、ACO-PRA等典型衛(wèi)星網(wǎng)絡(luò)路由算法和本文的en-BFS算法以及NCARA算法進(jìn)行比較。其中DT-DVTR采用Dijkstra算法尋找最短路徑，而ACO-PRA采用的尋路算法是蟻群算法。

本文中設(shè)定數(shù)據(jù)包的到達(dá)時(shí)間間隔服從指數(shù)分布，從而可以通過控制仿真中指數(shù)分布的平均值來控制平均數(shù)據(jù)發(fā)送速率。

4.2.1 平均跳數(shù)

網(wǎng)絡(luò)平均跳數(shù)如圖3所示，可見隨著平均數(shù)據(jù)發(fā)送速率的增大，en-BFS算法的跳數(shù)一直處于穩(wěn)定狀態(tài)并且優(yōu)于其他三種算法，原因是en-BFS算法將跳數(shù)作為主要衡量指標(biāo)，故它尋找的每條路徑都是最小跳數(shù)路徑。PRA-ACO算法將跳數(shù)作為QoS的衡量指標(biāo)，故在數(shù)據(jù)發(fā)送速率較小時(shí)比以DT-DVTR的平均跳數(shù)略低。而DT-DVTR算法采用Dijkstra算法作為尋路算法，衡量指標(biāo)為傳播時(shí)延和傳輸時(shí)延，在網(wǎng)絡(luò)非擁塞時(shí)，傳播時(shí)延作為主要的衡量指標(biāo)，故尋找的最短路徑不一定是最小跳數(shù)路徑。隨著平均發(fā)送速率的增大，網(wǎng)絡(luò)處于擁塞狀態(tài)，此時(shí)傳輸時(shí)延在衡量指標(biāo)中權(quán)重加大，故此時(shí)最短路徑近似等價(jià)為最小跳數(shù)路徑，此時(shí)DT-DVTR算法和en-BFS算法都趨于尋找最小跳數(shù)路徑，故平均跳數(shù)趨于穩(wěn)定。NCARA算法前面采用Dijkstra算法，后面采用en-BFS算法，故平均跳數(shù)和DT-DVTR算法近似保持一致。

圖3 路由算法平均跳數(shù)對(duì)比

4.2.2 平均端到端時(shí)延

圖4所示為平均端到端時(shí)延，可以看出ACO-PRA算法由于考慮多種QoS因素，平均端到端時(shí)延略高于其他三種算法。en-BFS算法在平均發(fā)送速率較低即網(wǎng)絡(luò)擁塞程度較低的時(shí)候，其主要衡量指標(biāo)為跳數(shù)，故尋找到的路徑可能不是最優(yōu)路徑，導(dǎo)致平均端到端時(shí)延略大于DT-DVTR算法。NCARA算法在網(wǎng)絡(luò)處于非擁塞時(shí)采用Dijkstra算法，而在擁塞時(shí)采用en-BFS算法，故它的平均端到端時(shí)延和DT-DVTR算法的平均端到端時(shí)延近乎一致。

圖4 路由算法平均端到端時(shí)延對(duì)比

4.2.3 平均丟包率

平均丟包率如圖5所示。由于在仿真時(shí)設(shè)置了節(jié)點(diǎn)的隊(duì)列長(zhǎng)度，并且當(dāng)節(jié)點(diǎn)的隊(duì)列數(shù)據(jù)包比特?cái)?shù)超過隊(duì)列長(zhǎng)度的時(shí)候，便會(huì)丟棄數(shù)據(jù)包，這是造成丟包的主要原因。并且由于本文算法為表驅(qū)動(dòng)路由，故也有可能由于節(jié)點(diǎn)在傳輸數(shù)據(jù)包時(shí)由于星間鏈路斷開，但是更新路由表不及時(shí)，從而導(dǎo)致丟包。

圖5 路由算法平均丟包率對(duì)比

由于ACO-PRA算法將丟包率也作為一個(gè)QoS因子進(jìn)行路徑計(jì)算，所以它的丟包慮相對(duì)較低。en-BFS算法尋找的路徑為最小跳數(shù)路徑，所以其因?yàn)檐壍篱g鏈路斷開而丟包的概率應(yīng)該略低于其他兩種算法。NCARA算法和DT-DVTR所尋找的路徑在隨著平均數(shù)據(jù)發(fā)送速率增大都是近乎一樣，故丟包率也近似一樣。

5 結(jié)束語

本文針對(duì)低軌衛(wèi)星網(wǎng)絡(luò)呈二維網(wǎng)格拓?fù)涞奶卣?，提出了一種en-BFS算法。該算法以跳數(shù)作為主要衡量指標(biāo)尋找出最小跳數(shù)路徑集，然后以傳輸時(shí)延和傳播時(shí)延作為鏈路權(quán)值，通過en-BFS算法尋找出權(quán)值和最小的路徑。由仿真可知，當(dāng)網(wǎng)絡(luò)處于擁塞時(shí)，采用en-BFS算法和DT-DVTR算法中采用Dijkstra算法尋找的路徑近乎是一樣的，但是傳輸時(shí)延卻高于DT-DVTR算法，于是提出了基于網(wǎng)絡(luò)擁塞程度感知的路由算法(NCARA)。該算法設(shè)置了網(wǎng)絡(luò)擁塞閾值，當(dāng)網(wǎng)絡(luò)擁塞程度高于擁塞閾值時(shí)采用en-BFS算法尋路，當(dāng)網(wǎng)絡(luò)擁塞程度低于擁塞閾值時(shí)采用Dijkstra算法尋路，這樣該算法尋找到的最短路徑便和DT-DVTR采用Dijkstra算法尋找到的最短路徑近乎一樣。由仿真可知，NCARA和DT-DVTR算法性能差不多，但是在算法復(fù)雜度上，NCARA在網(wǎng)絡(luò)擁塞時(shí)采用的en-BFS算法是一個(gè)O(V+E)時(shí)間復(fù)雜度的算法，優(yōu)于其他尋路算法。所以本文在沒有犧牲網(wǎng)絡(luò)性能的前提下降低了算法復(fù)雜度。

為了解決網(wǎng)絡(luò)負(fù)載不均衡問題，下一步將增加負(fù)載均衡策略，達(dá)到網(wǎng)絡(luò)負(fù)載均衡的目的。