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

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

(重慶郵電大學 a.通信與信息工程學院；b.移動通信技術(shù)重慶市重點實驗室，重慶 400065)

0 引 言

隨著通信技術(shù)的發(fā)展，天地一體化網(wǎng)絡已成為下一代通信的發(fā)展趨勢。作為天基骨干網(wǎng)絡的低軌(Low Earth Orbit，LEO)衛(wèi)星網(wǎng)絡因為具有全球覆蓋、可以忽略地形限制進行點對點通信等優(yōu)點而成為研究的熱點[1]。

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

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

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

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

1 系統(tǒng)模型

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

為了屏蔽衛(wèi)星拓撲變化的動態(tài)性，本文采用虛擬拓撲策略，將衛(wèi)星連續(xù)變化的動態(tài)拓撲通過采樣的方式抽象成n個離散的時間片，只要相鄰時間片的間隔Δt足夠小，便可以認為每個時間片內(nèi)的拓撲是靜止不變的。所以在每個快照范圍內(nèi)，節(jié)點可以近似抽象為一個二維網(wǎng)格拓撲。

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

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

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

3 en-BFS算法

3.1 en-BFS算法總體思想

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

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

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

(1)

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

(2)

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

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

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

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

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

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

或者

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

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

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

weight=α1Pt+α2Qt。

(3)

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

3.3.1 en-BFS算法需用符號說明

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

3.3.2 en-BFS算法具體步驟

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

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

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

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

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

Step5 判斷所有節(jié)點是否全部都已經(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é)點和目的節(jié)點的最小矩形范圍內(nèi)用en-BFS算法尋找到的路徑一定是最小跳數(shù)路徑集中權(quán)值和最小的路徑。

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

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

圖2 en-BFS遍歷層次圖

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

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

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

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

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

3.3.5 en-BFS算法復雜度分析

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

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

表1 算法復雜度對比

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

4 仿真分析

4.1 仿真建立

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

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

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

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

4.2 仿真結(jié)果分析

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

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

4.2.1 平均跳數(shù)

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

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

4.2.2 平均端到端時延

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

圖4 路由算法平均端到端時延對比

4.2.3 平均丟包率

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

圖5 路由算法平均丟包率對比

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

5 結(jié)束語

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

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