基于位置感知的大規(guī)模LEO星座分布式路由算法

劉高賽, 姜興龍, 李華旺, 梁 廣

(1. 中國科學院微小衛(wèi)星創(chuàng)新研究院, 上海 201203; 2. 中國科學院大學, 北京 100049;3. 上海微小衛(wèi)星工程中心, 上海 201203)

0 引 言

低地球軌道(low earth orbit,LEO)衛(wèi)星網絡由于經濟高效、傳播時延低、路徑損耗小等特性,在發(fā)展全球信息化建設中受到了較多的關注。近幾年LEO衛(wèi)星互聯(lián)網的發(fā)展突飛猛進,為了滿足日益增長的業(yè)務對大容量的需求,衛(wèi)星互聯(lián)網多采用大規(guī)模LEO衛(wèi)星組網,其中典型的包括美國的Starlink星座、英國的Oneweb星座、加拿大的Telesat系統(tǒng)。Starlink星座預計會有超過12 000顆衛(wèi)星組成,用于提供寬帶接入和高速互聯(lián)網服務。面向寬帶互聯(lián)網的大容量吞吐需求,Starlink和Telesat星座紛紛采用激光星間鏈路,由于激光高精度跟瞄和超高速傳輸?shù)燃夹g復雜、成熟度較低以及日凌影響等問題,因此有較高的中斷頻率。大規(guī)模LEO衛(wèi)星網絡的高動態(tài)性、鏈路中斷率高、拓撲變化快等問題,對星座的路由算法帶來了新的挑戰(zhàn)。

路由算法是衛(wèi)星組網的關鍵,影響著衛(wèi)星業(yè)務的吞吐量、魯棒性、傳輸時延等服務質量(quality of service, QoS)。衛(wèi)星節(jié)點有著計算能力低、存儲空間小、能源受限和無法升級硬件等特點。衛(wèi)星節(jié)點和衛(wèi)星網絡的特點使得地面已有的路由算法不適用于衛(wèi)星網絡。傳統(tǒng)的衛(wèi)星路由策略包括虛擬拓撲和虛擬節(jié)點,虛擬拓撲的路由表是由地面站注入,無法根據(jù)實時網絡狀態(tài)避免網絡擁塞和節(jié)點故障。針對以上不足,文獻[9-14]采用基于虛擬節(jié)點的分布式路由算法。但分布式路由中，當中間節(jié)點出現(xiàn)故障,衛(wèi)星需重新計算路由,將增加數(shù)據(jù)傳輸時延。文獻[15]提出了一種基于備用節(jié)點的分布式路由算法,解決分布式路由算法在節(jié)點出現(xiàn)故障導致傳輸效率下降的問題。針對分布式路由的星座運算量大的問題,文獻[16]提出了一種加權半分布式路由算法(weighted semi-distributed routing algorithm,WSDRA),將星座中衛(wèi)星分為信使衛(wèi)星和路由衛(wèi)星,僅路由衛(wèi)星計算數(shù)據(jù)包的流向,將星座整體運算量平均減少了一半。

分布式路由算法采用廣播方式尋找最佳路徑,造成大量的資源浪費,星座的路由收斂速度慢,大規(guī)模星座尤為明顯。為簡化星座管理和減小路由尋徑開銷,地面網絡分域思想被應用于星座分簇,主要算法包括動態(tài)劃分簇和靜態(tài)劃分簇。簇內衛(wèi)星路由發(fā)現(xiàn)多采用泛洪方式,造成不必要的能源和帶寬浪費。也有研究人員將大規(guī)模星座劃分為一定數(shù)量的小立方體,通過小立方體而不是坐標來定位衛(wèi)星,降低了端到端時延和計算復雜度。但此算法需衛(wèi)星節(jié)點向周圍衛(wèi)星發(fā)送維活信令,采用網格方式劃分網絡,需要衛(wèi)星存儲網格信息,增大了衛(wèi)星存儲負載。同時，隨著網格數(shù)量增多,也將影響路由效率。為減少HELLO包的發(fā)送,文獻[23]利用衛(wèi)星的可預測性,提出GomHop算法,減少了數(shù)據(jù)跨平面的傳輸,將數(shù)據(jù)優(yōu)先傳送到同一平面中,但未考慮算法的魯棒性,衛(wèi)星出現(xiàn)故障時需要重新計算路由。

綜上,為了降低路由開銷、端到端時延，提高星座吞吐量,研究人員對已有的分布式路由算法和分簇路由算法進行了優(yōu)化。還有研究人員在大規(guī)模星座采用分層的路由策略,高軌衛(wèi)星管理低軌衛(wèi)星,中繼低軌衛(wèi)星數(shù)據(jù)。這些策略同樣提高了路由的效率,降低了端到端時延。但是路由收斂時未能充分利用衛(wèi)星運行位置可預測的特性,多層衛(wèi)星造成了成本增高、鏈路時延增加等問題。通過上述分析,本文提出了一種基于位置感知的分布式路由算法(distributed routing algorithm based on location awareness, LADRA),該算法為保證不同業(yè)務的QoS要求,基于狀態(tài)矢量函數(shù)(state vector function,SVF)和傳播矢量函數(shù)(propagation vector function,PVF),充分利用了衛(wèi)星軌道運行的可預測性,對傳統(tǒng)先進先出(first in first out,FIFO)排隊規(guī)則進行優(yōu)化。通過仿真表明,本算法相比傳統(tǒng)分布式路由算法(distributed routing algorithm,DRA)和WSDRA,降低了路由開銷,隨著鏈路中斷概率的增加,降低了端到端時延,提高了星座吞吐量。本文的主要貢獻如下。

(1) 提出大規(guī)模LEO星座路由預選算法。根據(jù)衛(wèi)星運行位置可預測性,每顆衛(wèi)星傳輸數(shù)據(jù)包時,預選2～3個發(fā)送端口。此過程每顆衛(wèi)星只需存儲周圍衛(wèi)星的軌道參數(shù),存儲空間的占用不受星座規(guī)模大小的影響。

(2) 提出大規(guī)模LEO星座路徑收斂機制。根據(jù)SVF和PVF對預選路徑收斂。采用SVF避免了網絡擁塞,降低了排隊時延。PVF對路徑的收斂過程,在兩條完全獨立的路徑中,根據(jù)QoS需求,選擇較優(yōu)的一條作為主路徑,另一條作為備用路徑,提高了路由的魯棒性和吞吐量。

(3) 針對SVF收斂過程中可能發(fā)生的碰撞問題,本文給出了處理流程,保障了SVF收斂之后有兩條無重合的路徑。

(4) 優(yōu)化FIFO排隊策略。本文的隊列出隊規(guī)則不僅和入隊時間有關,而且與數(shù)據(jù)包大小有關,提高了單位時間數(shù)據(jù)包的傳輸量。

1 系統(tǒng)模型與問題定義

1.1 大規(guī)模LEO星座模型

圖1 大規(guī)模LEO星座拓撲和衛(wèi)星節(jié)點定義Fig.1 Large-scale LEO constellation topology and satellite node definition

1.2 問題定義

傳統(tǒng)的FIFO排隊模型,按照業(yè)務到達的時間先后進行排隊,先進的數(shù)據(jù)包先出,不考慮數(shù)據(jù)包的大小不同。本文對FIFO排隊規(guī)則進行改進,出隊規(guī)則不僅與入隊時間有關,而且與數(shù)據(jù)包的大小和數(shù)據(jù)包的傳輸速率有關。出隊順序所參照的表達式為

=+pkg

(1)

式中:為數(shù)據(jù)包入隊時間；為數(shù)據(jù)包傳輸速率；pkg為數(shù)據(jù)包大小。在同一個衛(wèi)星端口排隊的數(shù)據(jù)包,值小的數(shù)據(jù)包優(yōu)先出隊。

按照此規(guī)則不同數(shù)據(jù)包排隊時延計算表達式為

(2)

式中:<表示衛(wèi)星中,由式(1)計算出數(shù)據(jù)包pkg的值,小于數(shù)據(jù)包pkg的值,Δ表示pkg加入隊列時,正在傳輸?shù)臄?shù)據(jù)包已經傳輸?shù)臅r間。例如,圖1中的衛(wèi)星的一個發(fā)送端口在排隊的數(shù)據(jù)包有4個,4個數(shù)據(jù)包的入隊時間如圖2所示。由式(2)可知,數(shù)據(jù)數(shù)據(jù)包pkg排隊時延為(pkgpkgpkg)-(-),pkg的排隊時延為(pkgpkg)。

圖2 數(shù)據(jù)包到達時間和數(shù)據(jù)包大小Fig.2 Packet arrival time and packet size

星座的吞吐率是評價路由算法的一個關鍵指標,本文定義的星座吞吐率表達式為

(3)

式中:Rcv為衛(wèi)星, 作為目的節(jié)點接收到的業(yè)務數(shù)據(jù)量;end為星座中數(shù)據(jù)包接收結束的時刻;start為星座中存在衛(wèi)星接收數(shù)據(jù)的時刻。

對于資源受限的衛(wèi)星網路,路由開銷是評價路由算法的另一個關鍵指標,本文路由開銷定義如下:

(4)

式中:表示星座中路由控制包的數(shù)量;表示目的衛(wèi)星接收到的數(shù)據(jù)包總數(shù)。

2 LADRA路由算法設計

2.1 路徑預選機制

(5)

圖3 SRC與DST的位置關系圖Fig.3 Relative position of SRC and DST

根據(jù)在時刻SRC、DST和SRC周圍衛(wèi)星的位置信息,計算出圖3中的∠：

(6)

采用同樣的方法求得∠、∠、∠的值,SRC根據(jù)∠、∠、∠、∠的大小選擇下一跳,以90°為選擇下一跳的閾值角度。如圖3中,∠、∠大于90°,SRC_L和SRC_D不作為SRC的下一跳衛(wèi)星,∠、∠小于90°,SRC_U、SRC_R可以作為SRC的下一跳衛(wèi)星。SRC到DST的中間節(jié)點,選擇下一跳衛(wèi)星時,同樣選擇夾角小于90°的衛(wèi)星作為下一跳。迭代上述過程,將路由請求包(routing request packet,RREQ)傳輸?shù)紻ST。路由預選機制中的RREQ,從源衛(wèi)星到目的衛(wèi)星的傳輸過程中,每顆衛(wèi)星會傳輸RREQ到一個或兩個下一跳衛(wèi)星,導致較多的RREQ在星座中傳輸,浪費了鏈路資源和有限的衛(wèi)星能源,為此提出了路徑收斂機制。

2.2 路徑收斂機制

本文選擇夾角小于90°的衛(wèi)星作為下一跳,由圖3可知,SRC會有兩顆衛(wèi)星滿足此條件。中間衛(wèi)星的下一跳同樣可能有一顆或兩顆衛(wèi)星,如圖3中SRC_R周圍有兩顆衛(wèi)星滿足此條件。如果中間節(jié)點較多,每顆中間衛(wèi)星產生兩個分支,由文獻[27]可知,路徑的建立會消耗較多的衛(wèi)星能源。為此在路徑建立時,對路徑進行收斂,減少不必要的RREQ的復制傳輸。本文采用兩個因子收斂路徑,第一個因子根據(jù)衛(wèi)星端口的排隊長度,簡稱排隊因子,第二個因子根據(jù)不同路徑衛(wèi)星節(jié)點的能源狀況,簡稱能源因子。

排隊因子采用SVF,從SRC到DST的方向收斂路徑。能源因子采用PVF,從DST到SRC的方向收斂路徑。SVF的表達式為

(7)

PVF的表達式為

(8)

首先通過路徑預選,然后通過排隊因子和能源因子對路徑進行收斂,最終確定數(shù)據(jù)包傳輸路徑。防止SVF收斂后,SRC衛(wèi)星到DST衛(wèi)星只有一條路徑,本文的排隊因子對路徑的收斂作用于中間衛(wèi)星。中間衛(wèi)星收到RREQ后,以SRC_R為例,SRC_R經過路徑預選后,采用SVF收斂,在預選鏈路中選擇排隊時延短的端口發(fā)送RREQ。中間節(jié)點迭代SRC_R的處理過程,直到RREQ傳送到DST。按照上述過程,DST會收到來自兩條路徑的RREQ,DST采用PVF實現(xiàn)路徑最終的收斂。確定一條路徑為主路徑,另一條路徑為備用路徑。

在SRC衛(wèi)星發(fā)送的RREQ中,加上SRC的PVF,中間節(jié)點收到RREQ后,按照式(8)更新PVF,最終兩條路徑的PVF傳輸?shù)紻ST。DST比較兩條路徑的大小,選擇兩條路徑中較大的作為主傳輸路徑,另一條路徑作為備用路徑。當主路徑出現(xiàn)擁塞或其他鏈路問題時,SRC采用備用路徑傳輸業(yè)務數(shù)據(jù)。當路徑上中間衛(wèi)星感知到下一跳的位置變化范圍超出路徑預選的范圍,將向SRC發(fā)送路徑更新包。SRC將按照上述過程重新構建主路徑和備用路徑。通過SVF,采用排隊因子,降低業(yè)務數(shù)據(jù)的排隊時延。通過PVF,采用能源因子,降低由于中繼衛(wèi)星能源不足導致鏈路中斷的概率。主路徑和備用路徑的迭代建立,保證了主路徑中斷后,數(shù)據(jù)包能夠快速重傳。

采用SVF收斂路徑時,存在收斂碰撞的問題,即RREQ傳輸?shù)侥康男l(wèi)星前,兩顆衛(wèi)星通過SVF收斂,將RREQ傳輸?shù)搅送活w衛(wèi)星,導致RREQ到達目的衛(wèi)星時只有一條路徑。為解決收斂碰撞的問題,本文對SVF收斂導致的碰撞問題進行了處理。

2.3 SVF收斂碰撞處理

采用SVF收斂路徑,會產生兩種收斂結果,第一種是從SRC到DST,兩條路徑不會收斂到同一顆中間衛(wèi)星。第二種是SVF收斂的過程中發(fā)生收斂碰撞,兩條路徑到達DST前收斂到了同一顆中間衛(wèi)星。SVF的第一種收斂結果如圖4所示。從源衛(wèi)星到目的衛(wèi)星,沒有發(fā)生SVF收斂碰撞,從SRC到DST產生了兩條獨立的路徑。

圖4 SVF收斂無碰撞示意圖Fig.4 Diagram of SVF convergence without collision

SVF的第二種收斂結果如圖5所示。衛(wèi)星與衛(wèi)星在選擇下一跳時,均選擇了衛(wèi)星,按照上述提出的SVF收斂機制,衛(wèi)星到目的衛(wèi)星只會產生一條路徑,導致PVF收斂機制失效。針對SVF的收斂碰撞問題,本文提出了SVF收斂碰撞處理機制。以圖5為例說明SVF收斂碰撞處理過程。SVF收斂碰撞發(fā)生在圖5中衛(wèi)星和衛(wèi)星,由于衛(wèi)星為DST,在DST衛(wèi)星發(fā)生碰撞,采用PVF從碰撞的兩條路徑,分別選擇一條主傳輸路徑和一條備用路徑。如果在衛(wèi)星預選路徑之后再使用SVF對路徑收斂,會導致只有一條路徑到達DST衛(wèi)星,因此對于在中間節(jié)點發(fā)生的收斂碰撞,以衛(wèi)星為例,SVF收斂碰撞的處理流程如圖6所示。

圖5 SVF收斂碰撞示意圖Fig.5 Diagram of SVF convergence collision

圖6 衛(wèi)星v2,2處理SVF收斂碰撞流程Fig.6 SVF convergence collision processing flow of satellite v2,2

假設發(fā)生SVF收斂碰撞的衛(wèi)星,通過PVF收斂后選擇作為上一跳。收斂碰撞處理如下:

(1) 中間衛(wèi)星傳遞RREQ包時,在RREQ包中加入經過SVF收斂后,沒被選擇的下一跳位置信息。例如,圖5中向發(fā)送的RREQ包中包含的位置信息。

(2) 按照假設,經過PVF的收斂,選擇為上一跳,將的RREQ包中的位置信息刪除,保留的RREQ包中的位置信息,并將該位置信息寫入的RREQ包中。

(3) 發(fā)生碰撞的衛(wèi)星,進行路徑預選機制后,發(fā)送包含位置信息的RREQ包到衛(wèi)星和,接收到發(fā)生收斂碰撞衛(wèi)星的RREQ包,計算上一跳可能的位置信息,并與的位置信息對比,確認是的上一跳,則在中將上一跳置為。

(4) 衛(wèi)星接收到發(fā)生收斂碰撞衛(wèi)星的RREQ包,進行與相同的操作,但不是的上一跳,的上一跳確認為。

LADRA首先通過位置感知執(zhí)行路徑預選,然后采用SVF和PVF對路徑進行收斂,最后針對SVF收斂過程中的碰撞問題,本文給出了處理流程。LADRA的偽代碼如算法1所示。

算法 1 LADRA輸入:周圍衛(wèi)星的軌道參數(shù)i, Ω, e, ω, a, M0,時間t輸出:數(shù)據(jù)包輸出端口P1) 通過式(5)計算周圍衛(wèi)星的位置2) 將周圍衛(wèi)星的位置信息和目的衛(wèi)星的位置信息,輸入到式(6),分別計算周圍每顆衛(wèi)星和目的衛(wèi)星的夾角,按照周圍衛(wèi)星上下左右4個方位,將夾角分別定義為β、η、γ、α3) for i=[β, η, γ, α]4) if i≤90°then5) 將i存儲到待選端口集合P,P=[P, i] 6) end if7) end for8) if 此衛(wèi)星為SRC衛(wèi)星 then9) 將RREQ通過預選端口集合P發(fā)送出去10) else if 此衛(wèi)星為DST衛(wèi)星 then11) 由式(8)的PVF,選擇路徑中最低剩余能量最高的路徑,回復RREP作為主路徑,另一條路徑,回復RREP作為備用路徑12) else13) if 收到兩個RREQ(發(fā)生碰撞) then14) 由式(8)PVF,選擇路徑中最低剩余能量較高的路徑,回復RREP 15) 執(zhí)行圖6的碰撞處理流程,將RREQ包從預選路徑的端口集合P發(fā)出16) else (無碰撞發(fā)生)17) 由式(7)的SVF,計算待選端口P中排隊時間次少的下一跳位置信息寫入RREQ包,向排隊時間最短的端口發(fā)送路由請求RREQ包18) end if 19) end if

其中,標號1)～7)是路徑預選,8)～19)是采用排隊因子和能源因子對路徑進行收斂。本文提出的路徑預選和收斂機制,減少了路由開銷,每次路由的更新,每顆衛(wèi)星僅需完成周圍衛(wèi)星的位置計算和路徑收斂計算。衛(wèi)星的路由存儲開銷主要包括周圍衛(wèi)星的軌道六根數(shù),與星座規(guī)模的大小無關。計算開銷主要包括周圍衛(wèi)星位置的計算和數(shù)值比較。排隊因子降低了排隊時延,均衡了網絡負載；能源因子減少了對能源相對少的衛(wèi)星進一步消耗,延長了星座運行時間。本文提出的基于SVF和PVF的路徑收斂策略,除采用排隊因子和能源因子,還可以根據(jù)業(yè)務QoS需求,選擇端到端時延、路由跳數(shù)、鏈路故障率等因子。

3 仿真實驗

為了驗證LADRA的有效性,本文使用STK開發(fā)平臺設計了大規(guī)模LEO近極軌星座,借鑒STK導出的軌道數(shù)據(jù),利用Matlab對LADRA算法進行驗證和分析,并將LADRA分別與DRA以及WSDRA進行對比。

3.1 仿真參數(shù)

網絡架構采用第一代Oneweb近極軌星座,星座共有648顆衛(wèi)星,分布在18條LEO軌道。星座中除反向縫處不存在星間鏈路,其余衛(wèi)星存在4條星間鏈路。仿真參數(shù)設置如表1所示。圖7為第一代Oneweb星座結構圖。根據(jù)STK導出的軌道信息,在Matlab中實現(xiàn)本文算法功能,如圖8所示為根據(jù)STK軌道信息,在Matlab中計算的實時星下點分布。

表1 仿真參數(shù)設置Table 1 Simulation parameters setting

圖7 第一代Oneweb星座結構圖Fig.7 The first generation Oneweb constellation structure diagram

圖8 星下點分布圖Fig.8 Distribution map of sub-satellite points

3.2 仿真分析

對于資源受限的衛(wèi)星網絡,路由建立階段的開銷是影響衛(wèi)星網絡運行的一個因素,也是評價路由算法的一個標準，式(3)為路由開銷的定義。本文對LADRA、傳統(tǒng)的DRA、WSDRA 3種路由建立開銷進行了對比。圖9是3種算法在不同跳數(shù)下,路由建立階段的開銷對比圖。從圖9中可以看出,隨著源衛(wèi)星與目的衛(wèi)星的跳數(shù)增加,發(fā)送相同數(shù)量的數(shù)據(jù)包,路由開銷逐漸增大,傳統(tǒng)的DRA路由開銷隨著跳數(shù)增加,路由開銷呈()增加。本文的LADRA,隨著路由跳數(shù)增加,開銷呈線性增長,且增長速度較慢。路由跳數(shù)大于10跳,LADRA路由開銷平均為WSDRA的50%。路由建立的開銷方面,LADRA更加適合大規(guī)模LEO衛(wèi)星網絡。

圖9 不同跳數(shù)下路由建立階段的開銷Fig.9 Cost of route establishment at different hop counts

圖10給出了傳統(tǒng)DRA、WSDRA和本文提出的LADRA,在不同的鏈路中斷概率下的端到端時延對比圖。仿真結果表明,3種算法在中斷概率小于1%時,端到端時延相近,但隨著鏈路的中斷頻率增加,本文的LADRA端到端時延增加量最小。中斷頻率大于3%時,LADRA端到端時延平均為WSDRA的一半。因為本文算法在構建端到端傳輸路徑時,不僅構建了一條主傳輸路徑,而且構建了一條備用路徑,當鏈路出現(xiàn)故障時,能夠直接切換備用路徑傳輸業(yè)務數(shù)據(jù)。另外,WSDRA的端到端時延低于傳統(tǒng)DRA。因為WSDRA在衛(wèi)星節(jié)點出現(xiàn)故障或擁塞時,能夠在主方向和次方向選擇下一跳,而DRA只在主方向上選擇下一跳。

圖10 不同鏈路中斷概率下的端到端時延Fig.10 End-to-end delay at different link interruption probabilities

圖11給出了傳統(tǒng)DRA、WSDRA和本文提出的LADRA,在不同傳輸中斷頻率下的星座吞吐量。從圖11中可以看出,中斷概率小于1%時,3種算法的吞吐量相近。當中斷頻率大于3%時,本文LADRA吞吐量大約為WSDRA的兩倍。這是因為備用路徑和對傳統(tǒng)FIFO方式進行優(yōu)化的結果,另外,本文LADRA,在路徑建立階段信令包的開銷較少,節(jié)約了鏈路資源。

圖11 不同鏈路中斷概率下的吞吐率Fig.11 Throughput rates at different link interruption probabilities

4 結 論

由于大規(guī)模LEO星座具有高時延、高動態(tài)、激光星間鏈路中斷概率大等特性,采用傳統(tǒng)的路由算法,存在著適用性差等問題。因此,本文提出了一種LADRA,為解決大規(guī)模星座路由問題提供一種新的思路。首先,通過路徑預選和收斂機制,根據(jù)業(yè)務數(shù)據(jù)自適應地確定一條主路徑和一條備用路徑。然后,針對SVF導致的收斂碰撞問題提出了處理方案,避免了SVF收斂到同一顆中間節(jié)點。最后，通過理論分析和實驗驗證了LADRA的路由建立階段開銷較小。隨著中斷概率的增加,LADRA與傳統(tǒng)的DRA、WSDRA相比,降低了端到端時延、提高了星座的吞吐量,更加適合大規(guī)模LEO星座。

未來將對此算法進行優(yōu)化,確保此算法運行在大規(guī)模LEO星座中具有更好的抗毀能力、安全性、更高的吞吐量和更低的端到端時延。