基于局部洪泛優(yōu)化的低軌星座分布式路由算法

周 宇，尹增山，王 龍

（1.中國科學(xué)院微小衛(wèi)星創(chuàng)新研究院，上海 201304；2.上?？萍即髮W(xué)信息科學(xué)與技術(shù)學(xué)院，上海 201210；3.中國科學(xué)院大學(xué)，北京 100049）

0 引言

衛(wèi)星網(wǎng)絡(luò)近年來發(fā)展迅速，星座路由算法致力于實(shí)現(xiàn)衛(wèi)星網(wǎng)絡(luò)數(shù)據(jù)包的高效轉(zhuǎn)發(fā)和擁塞控制，將顯著地影響網(wǎng)絡(luò)性能和效率，許多學(xué)者對(duì)此做了長期研究。WERNER 等［1］提出的虛擬路徑路由算法［1］和GOUNDER 等［2］提出的快照序列算法，首先將衛(wèi)星的周期運(yùn)動(dòng)劃分為離散的狀態(tài)序列以實(shí)現(xiàn)靜態(tài)路由，但難以進(jìn)行網(wǎng)絡(luò)擁塞控制。AKYILDIZ等［3］隨后提出了多層路由算法，通過協(xié)同星座內(nèi)部高/中/低多層軌道，進(jìn)行分區(qū)分工管理，以實(shí)現(xiàn)衛(wèi)星之間動(dòng)態(tài)路由和網(wǎng)絡(luò)協(xié)調(diào)。在此基礎(chǔ)上，許多學(xué)者針對(duì)服務(wù)質(zhì)量（Quality of Service，QoS）路穩(wěn)定性、擁塞控制等方面進(jìn)行了研究。

分布式路由算法不依賴地面站，能夠在軌自主運(yùn)行，對(duì)網(wǎng)絡(luò)突發(fā)流量和需求波動(dòng)快速響應(yīng)，具有重要工程價(jià)值。HENDERSON 和EKICI 等［4-7］指出，通信星座網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)具有規(guī)律性，輕量級(jí)算法即可實(shí)現(xiàn)近似最優(yōu)路由性能。TARIK 等［8-11］通過相鄰鏈路的擁塞感知，利用交通燈機(jī)制、拓?fù)潢P(guān)系或替代路徑分配，進(jìn)一步改進(jìn)了算法。此外，融入了蟻群算法、極限學(xué)習(xí)機(jī)等啟發(fā)式方法的分布式算法［12-13］相繼出現(xiàn)，通過全局傳導(dǎo)或洪泛收集沿途鏈路信息，以進(jìn)行網(wǎng)絡(luò)擁塞控制。隨后，多層星座的分布式路由算法［14-16］也被提出，用于中/低軌層間的流量均衡或QoS 性能保障。

然而，目前低軌星座呈現(xiàn)規(guī)模大、節(jié)點(diǎn)數(shù)量多、多層分布特征。例如StarLink 星座一期包含數(shù)千顆衛(wèi)星，分5 層，軌道高度在540～570 km 之間［17］?；谌趾榉旱木W(wǎng)絡(luò)路徑規(guī)劃存在較大路由延遲和通信開銷；而傳統(tǒng)分布式算法［4-6］以單層衛(wèi)星網(wǎng)絡(luò)拓?fù)錇橹?，較難適用于多層低軌衛(wèi)星網(wǎng)絡(luò)結(jié)構(gòu)［17-18］。針對(duì)以上問題，提出一種基于局部洪泛優(yōu)化的分布式路由算法，具有如下創(chuàng)新：

1）利用分布式的局部洪泛，以較低的算力開銷和延遲，實(shí)現(xiàn)了對(duì)局部擁塞的路徑優(yōu)化。

2）基于局部鏈路感知，可適用于單層或多層低軌衛(wèi)星網(wǎng)絡(luò)結(jié)構(gòu)，提高了對(duì)衛(wèi)星隨機(jī)故障的適應(yīng)性，降低網(wǎng)絡(luò)丟包率。

1 基于局部洪泛的擁塞感知

1.1 通信需求高度不均的分布特征

相比地面通信網(wǎng)絡(luò)，低軌星座網(wǎng)絡(luò)具有規(guī)律性移動(dòng)特征。因此各類星座計(jì)劃［17-18］，主要采用均勻穩(wěn)定Walker［19］或極地軌道星座構(gòu)型。若要對(duì)特定區(qū)域提供持續(xù)衛(wèi)星信號(hào)覆蓋，需要均勻地部署大量低軌衛(wèi)星。然而，陸地僅占地球表面積約30%，并且人口和經(jīng)濟(jì)活動(dòng)進(jìn)一步集中在少數(shù)陸地區(qū)域［20］，如圖1 所示，圖中顏色越深表示人口和經(jīng)濟(jì)活動(dòng)密度越大（耶魯大學(xué)的G-Econ［21］項(xiàng)目）。

圖1 人口與通信需求的高度不均勻分布Fig.1 Highly uneven distribution of population and communication demand

衛(wèi)星星座建設(shè)無法像地面網(wǎng)絡(luò)基站一樣依據(jù)用戶密度按需部署，因此容易出現(xiàn)局部擁塞。傳統(tǒng)路由一般采用全局洪泛［22］或啟發(fā)式方法的全局傳導(dǎo)［12］，然而對(duì)于大型低軌星座，通信和處理開銷很大。因此，提出了基于局部洪泛優(yōu)化的分布式路由算法，有利于解決圖1 中高度不均衡的通信業(yè)務(wù)需求引起的局部擁塞。

1.2 局部洪泛的過程

為了緩解局部擁塞，算法采取局部洪泛的機(jī)制收集周圍鏈路的排隊(duì)延遲。

1）洪泛數(shù)據(jù)包格式定義

設(shè)單顆衛(wèi)星共有q條星間鏈路，則每經(jīng)過時(shí)間周期Tlocal，每顆衛(wèi)星即向周圍發(fā)出一個(gè)局部洪泛包，數(shù)據(jù)格式為

式中：IDsate為當(dāng)前衛(wèi)星的唯一標(biāo)號(hào)；tpacket為此局部洪泛包的生成時(shí)間，s；hlocal為此局部洪泛包的剩余跳數(shù)，當(dāng)跳數(shù)被用完，此包失活并被丟棄；tISL-1～tISL-q為當(dāng)前衛(wèi)星的q條星間鏈路的實(shí)時(shí)排隊(duì)延遲。IDsate和tpacket用于唯一確定洪泛包，防止重復(fù)轉(zhuǎn)發(fā)。

令局部洪泛跳數(shù)hlocal的初始值為一個(gè)預(yù)設(shè)值Hlocal，則單個(gè)洪范包所能傳輸?shù)淖钸h(yuǎn)跳數(shù)是Hlocal。由此，星座中每顆衛(wèi)星能夠搜集到相隔Hlocal跳之內(nèi)各顆鄰近衛(wèi)星的鏈路排隊(duì)延遲信息。

2）局部洪泛范圍的確定

局部洪泛跳數(shù)Hlocal的取值應(yīng)當(dāng)對(duì)于不同的星座參數(shù)進(jìn)行調(diào)整，以保證覆蓋可能產(chǎn)生局部擁塞的人口密集區(qū)域。但如果Hlocal的取值過大，則容易加重衛(wèi)星算力負(fù)擔(dān)。使用如下步驟確定Hlocal的取值。

步驟1計(jì)算出鄰近某個(gè)特定城市的衛(wèi)星集合Z。

式中：Si為衛(wèi)星；Ssite_city為城市坐標(biāo)；Llocal為城市區(qū)域的半徑，m。

把以Ssite_city為中心Llocal為半徑的地面范圍，視為可能會(huì)產(chǎn)生局部網(wǎng)絡(luò)擁塞的城市區(qū)域。而函數(shù)N(Si，Ssite_city)用于計(jì)算衛(wèi)星Si所覆蓋的地面區(qū)域，到城市坐標(biāo)Ssite_city的距離。此函數(shù)與軌道高度、星地通信最小仰角有關(guān)，可根據(jù)幾何關(guān)系求解。

步驟2計(jì)算出距離最接近某個(gè)特定城市的衛(wèi)星Scity，如下式所示。其中，函數(shù)D(·)用于計(jì)算兩者距離，易知Scity∈Z。

步驟3依據(jù)集合Z和衛(wèi)星Scity，計(jì)算出最遠(yuǎn)跳數(shù)Hlocal的取值，如下式所示：

式中：函數(shù)Hop(Si，Scity)用于計(jì)算從衛(wèi)星Si到Scity最少需要經(jīng)過幾條星間鏈路，可通過Ekici 等［4］的衛(wèi)星標(biāo)號(hào)方法算得。

基于此流程算得的Hlocal，保證了衛(wèi)星的局部洪泛范圍能夠完整地覆蓋容易產(chǎn)生網(wǎng)絡(luò)局部擁塞的城市區(qū)域（以Llocal為預(yù)設(shè)半徑），因?yàn)槠浒怂锌赡軐?duì)城市區(qū)域進(jìn)行波束覆蓋并建立星地鏈路的衛(wèi)星。一般選取從低緯度的新加坡，到高緯度的倫敦等主要城市的坐標(biāo)帶入?yún)?shù)Ssite_city，并按照現(xiàn)在的城區(qū)范圍，令Llocal為100 km 等數(shù)值，即可算得局部洪泛最遠(yuǎn)跳數(shù)Hlocal。

2 局部感知優(yōu)化的算法設(shè)計(jì)

2.1 路徑優(yōu)化

在局部洪泛的基礎(chǔ)上，設(shè)存在衛(wèi)星A正在路由轉(zhuǎn)發(fā)數(shù)據(jù)包P，并且數(shù)據(jù)包P的接收地為點(diǎn)O，則局部洪泛優(yōu)化如圖2 所示。圖中綠色背景的衛(wèi)星處于洪泛邊緣。

圖2 局部洪泛感知和確定轉(zhuǎn)發(fā)路徑Fig.2 Diagram for local flooding awareness and selecting forwarding paths

設(shè)局部洪泛共涵蓋N顆衛(wèi)星，共有M顆衛(wèi)星位于洪泛邊緣，洪泛邊緣的衛(wèi)星可表示為Ei(1 ≤i≤M)。首先，根據(jù)式（1）進(jìn)行局部洪泛獲取的鏈路信息，用Dijkstra 算法得出局部最優(yōu)路徑序列：

式中：tpath為生成此序列的時(shí)間，s；IDi為圖2 中的第i顆衛(wèi)星的唯一標(biāo)號(hào)；Qi為衛(wèi)星A到第i顆衛(wèi)星的最短路徑權(quán)重，是路徑上每條星間鏈路的排隊(duì)延遲和傳輸延遲之和，s；Pi為最短路徑中途經(jīng)衛(wèi)星的標(biāo)號(hào)序列。

因?yàn)橥ǔ晤w衛(wèi)星有4 條星間鏈路數(shù)（2 條同軌，2 條異軌），遠(yuǎn)小于衛(wèi)星數(shù)量N，可利用堆結(jié)構(gòu)將Dijkstra 算法的時(shí)間復(fù)雜度降為O(NlogN)［23］。

在高度擁塞的局部網(wǎng)絡(luò)中，最優(yōu)路徑會(huì)變得迂回曲折。因此，定義了指標(biāo)“距離成本系數(shù)”，用于衡量數(shù)據(jù)包P如果傳輸至洪泛邊緣衛(wèi)星Ei，是否能用更短的時(shí)間更快地接近目的地。以圖2 為例，處于洪泛邊緣的衛(wèi)星Ei相對(duì)于數(shù)據(jù)包P及其接收地O的距離成本系數(shù)為

式中：函數(shù)D(·)用于計(jì)算兩者間的直線距離；ε用于防止除零；QEi式（5）中的最短路徑權(quán)重。

路由時(shí)，當(dāng)前衛(wèi)星會(huì)為每個(gè)數(shù)據(jù)包選出“距離成本系數(shù)”最大的轉(zhuǎn)發(fā)路徑，如式（7）所示。其中函數(shù)p(·)可依據(jù)式（5）將參數(shù)衛(wèi)星映射為對(duì)應(yīng)的局部最優(yōu)路徑（以途徑衛(wèi)星的標(biāo)號(hào)序列表示），RP為路由算法數(shù)據(jù)包P選出的轉(zhuǎn)發(fā)路徑。

由此，算法可在局部洪泛范圍內(nèi)，選出讓每個(gè)數(shù)據(jù)包最快接近目的地的局部最優(yōu)路徑，從而實(shí)現(xiàn)對(duì)局部網(wǎng)絡(luò)擁塞的路徑優(yōu)化。

2.2 多路徑間負(fù)載平衡

上述過程分布式地運(yùn)行在每顆衛(wèi)星上，存在兩個(gè)問題：首先，衛(wèi)星在軌資源受限，局部洪泛和路徑優(yōu)化的頻率不能過高；其次，路由算法需要及時(shí)響應(yīng)網(wǎng)絡(luò)突發(fā)流量和通信需求波動(dòng)。

例如，任意兩地之間如果出現(xiàn)大量的瞬時(shí)衛(wèi)星通信需求，式（7）會(huì)將全部數(shù)據(jù)包轉(zhuǎn)發(fā)到某一條局部最優(yōu)路徑上，隨即加重了此路徑的擁塞程度和傳輸延遲。如果將突發(fā)流量分?jǐn)偟蕉鄺l相似的路徑上，可降低端到端延遲，提高整體的網(wǎng)絡(luò)效率。

為此，引入指標(biāo)“路徑附加延遲”REi作為式（6）分母的補(bǔ)充，則式（7）更新成下式：

當(dāng)圖2 的衛(wèi)星A完成路徑更新后，REi的初始值為0。當(dāng)衛(wèi)星A根據(jù)式（8）選擇出的局部最短路徑，以洪泛邊緣衛(wèi)星Ei為終點(diǎn)時(shí)，令數(shù)據(jù)包長度為LP，星間鏈路傳輸速率為SISL，則REi按下式更新：

在式（8）中，REi與路徑延遲QEi之和，可用于實(shí)時(shí)估算各條路徑所花費(fèi)的時(shí)間成本，把流量負(fù)載動(dòng)態(tài)平衡地分配到多條相似路徑上，以提高網(wǎng)絡(luò)的傳輸效率。不過，附加延遲REi的數(shù)值準(zhǔn)確度較低，因?yàn)槎鄺l路徑之間可能包含相同的星間鏈路，其他相鄰衛(wèi)星也在并行地進(jìn)行著相同的路由轉(zhuǎn)發(fā)過程。其主要作用是實(shí)現(xiàn)局部的網(wǎng)路負(fù)載均衡。

綜上，算法流程圖如圖3 所示。

圖3 局部感知優(yōu)化的分布式路由算法流程Fig.3 Flow chart of the distributed routing algorithm based on local flooding optimization

如圖3 所示，若數(shù)據(jù)包的接收地靠近當(dāng)前衛(wèi)星，則在局部洪泛范圍內(nèi)即可找到下傳衛(wèi)星和下傳路徑。這種情況依然要用到式（9）的“路徑附加延遲”，以助于在多個(gè)下傳衛(wèi)星中平衡分配流量。

算法基于“距離成本系數(shù)”選擇局部轉(zhuǎn)發(fā)路徑。在圖2 中，由于衛(wèi)星連續(xù)均勻部署，總會(huì)存在更靠近O點(diǎn)的洪泛邊緣衛(wèi)星，讓式（8）的分式D(O，A)-D(O，Ei)大于零，使得數(shù)據(jù)包會(huì)不斷接近O點(diǎn)。此過程不可逆，因此算法可以避免出現(xiàn)環(huán)路。

同時(shí)，利用局部洪泛收集鏈路信息，該算法可建立到達(dá)洪泛邊緣衛(wèi)星的路徑映射關(guān)系，無論部署在單層或多層低軌衛(wèi)星網(wǎng)絡(luò)中，或面對(duì)隨機(jī)的衛(wèi)星故障，均可屏蔽局部網(wǎng)絡(luò)的結(jié)構(gòu)差異，正常運(yùn)行。

2.3 時(shí)間和空間復(fù)雜度

每顆衛(wèi)星存在4條星間鏈路，以Hlocal=4 為例，局部洪泛收集鏈路信息所涉及的局部網(wǎng)絡(luò)如圖4 所示。根據(jù)圖4 類推，局部網(wǎng)絡(luò)的衛(wèi)星數(shù)目為N=1+2Hlocal(Hlocal+1)，洪泛邊緣的衛(wèi)星數(shù)M=4Hlocal。為了防止洪泛包的重復(fù)轉(zhuǎn)發(fā)，需保存O(N)的數(shù)據(jù)。而式（5）的路徑信息，需保存O(N2)的數(shù)據(jù)。則空間復(fù)雜度為

圖4 洪泛感知的局部網(wǎng)絡(luò)（以Hlocal=4 為例）Fig.4 Diagram of flooding aware local network（taking Hlocal=4 as an example）

設(shè)局部洪泛和Dijkstra 算法的運(yùn)行周期為Tlocal，已知Dijkstra 算法的時(shí)間復(fù)雜度為O(NlogN)，則每秒的計(jì)算復(fù)雜度為1/TlocalO(NlogN)。設(shè)每顆衛(wèi)星每秒需要傳輸平均k個(gè)數(shù)據(jù)包。根據(jù)式（8），單個(gè)數(shù)據(jù)包選擇局部路徑的復(fù)雜度為O(M)。由圖4 類推，從衛(wèi)星A到洪泛邊緣，路徑最短為Hlocal。數(shù)據(jù)包每完成一條路徑僅路由一次，則單顆衛(wèi)星需要處理最多k/Hlocal個(gè)數(shù)據(jù)包。因此，每顆衛(wèi)星每秒運(yùn)行的時(shí)間復(fù)雜度為

近年發(fā)表的GomHop 算法［24］和低開銷分配方案協(xié) 議（Low-overhead Distribution Scheme Protocol，LSP）算法［10］時(shí)間復(fù)雜均為O(k)。算法增加的部分來自局部路徑優(yōu)化。因?yàn)镠local取值范圍通常在3 至10 之間，若洪泛周期Tlocal取值合理，算法的時(shí)間復(fù)雜度依然較小。同理根據(jù)式（10），算法的空間復(fù)雜度也較小。

3 仿真分析

為了驗(yàn)證算法的擁塞控制性能，以及對(duì)網(wǎng)絡(luò)隨機(jī)故障、多層低軌衛(wèi)星網(wǎng)絡(luò)結(jié)構(gòu)的寬適應(yīng)性，獨(dú)立搭建了仿真環(huán)境。

選擇StarLink 星座其中3 層作為仿真對(duì)象，相關(guān)軌道參數(shù)見表1［17］。其相位因子、鏈路設(shè)置等細(xì)節(jié)，參考了Handley 等［25］的處理方法。星間鏈路傳輸速率設(shè)為10 Gbps，設(shè)置所有數(shù)據(jù)包的收發(fā)地相隔大于1 000 km，以排除無需通過星間路由轉(zhuǎn)發(fā)情況。通信業(yè)務(wù)分布假定與人口數(shù)量以及人類發(fā)展指數(shù)（Human Development Index，HDI）正相關(guān)，人口數(shù)據(jù)與HDI 數(shù)據(jù)參照美國航空航天局官網(wǎng)，經(jīng)緯度1°方格為網(wǎng)格單元。實(shí)驗(yàn)中選擇洪泛范圍Hlocal和洪泛周期Tlocal分別取(4，0.3 s)、(6，0.3 s)、(6，0.1 s)3 種情況。選擇GomHop 算法［24］（2019）和LSP 算法［10］（2019）作為比較對(duì)象。

表1 仿真實(shí)驗(yàn)的星座軌道參數(shù)Tab.1 Constellation orbit parameters of the simulation tests

3.1 擁塞控制和故障包容仿真實(shí)驗(yàn)

取表1 中軌道高度550 km 單層衛(wèi)星網(wǎng)絡(luò)，針對(duì)不同網(wǎng)絡(luò)負(fù)載和衛(wèi)星故障率5%的情況進(jìn)行仿真結(jié)果如圖5 所示。

圖5 擁塞控制和故障包容的仿真結(jié)果Fig.5 Simulation results for congestion control and fault containment

如圖5 所示，圖中LAD 為局部感知分布式算法（Locally Aware Distributed Algorithm）。算法能夠明顯降低網(wǎng)絡(luò)丟包率，并且局部洪泛跳數(shù)越大、洪泛周期越短，丟包率越低，性能越好。在衛(wèi)星故障率為5%時(shí)，依然能將低流量負(fù)載的丟包率降至接近0%，對(duì)故障的包容性更大。

同時(shí)仿真表明，針對(duì)通信業(yè)務(wù)需求均勻分布情況，幾種算法的丟包率都會(huì)降低到0%。針對(duì)高度不均衡通信業(yè)務(wù)需求分布情況，算法具有擁塞控制能力，能夠疏導(dǎo)局部擁塞。

3.2 多層網(wǎng)絡(luò)結(jié)構(gòu)適應(yīng)性仿真實(shí)驗(yàn)

多層低軌衛(wèi)星網(wǎng)絡(luò)存在跨層星間鏈路。在仿真中設(shè)定2 層中滿足距離近、移動(dòng)方向相同，并且位置關(guān)系滿足一定持續(xù)穩(wěn)定建鏈時(shí)間需求的2 顆衛(wèi)星間建立一條跨層鏈路。選取表1 中所有層次作為仿真對(duì)象，結(jié)果如圖6 所示。

圖6 多層低軌衛(wèi)星網(wǎng)絡(luò)中的丟包率Fig.6 Packet loss rates in multi-layer LEO satellite networks

當(dāng)衛(wèi)星出現(xiàn)故障時(shí)，本文算法相比GomHop 在丟包率上有更好的表現(xiàn)。當(dāng)參數(shù)選取Hlocal=6，Tlocal=0.1 s 時(shí)，本文算法能夠?qū)⒕W(wǎng)絡(luò)負(fù)載小于1 000 Gbps 時(shí)的丟包率降為接近0%，將網(wǎng)絡(luò)負(fù)載小于1 500 Gbps 的丟包率降至5%以下。

4 結(jié)束語

本文針對(duì)傳統(tǒng)分布式星座路由算法擁塞控制能力有限，全局路徑優(yōu)化開銷過大的問題，提出了一種局部洪泛優(yōu)化的分布式路由算法。通過定義“距離成本系數(shù)”為每個(gè)數(shù)據(jù)包確定轉(zhuǎn)發(fā)路徑，估算各條路徑延遲增量，將瞬時(shí)流量平衡分配。該算法空間/時(shí)間復(fù)雜度較低，能夠滿足小衛(wèi)星在軌部署的需求，且不會(huì)出現(xiàn)路由環(huán)路，能夠自動(dòng)適應(yīng)鏈路故障和多樣化網(wǎng)絡(luò)結(jié)構(gòu)。仿真表明，針對(duì)高度不均通信需求分布，該算法可降低2%～10%的丟包率，并能更好適應(yīng)多層低軌衛(wèi)星網(wǎng)絡(luò)架構(gòu)。本質(zhì)上，該算法融合了高計(jì)算開銷的全局尋徑，低擁塞控制能力的靜態(tài)路由這兩者的部分機(jī)制，嘗試在降低路由開銷和減少網(wǎng)絡(luò)擁塞之間取得平衡，以更好應(yīng)對(duì)地域人口高度集中和需求分布不均的普遍現(xiàn)象，節(jié)省在軌路由算力，優(yōu)化天基網(wǎng)絡(luò)的通信效率。

未來研究中，面對(duì)流量地理分布不均，將計(jì)劃開展統(tǒng)計(jì)學(xué)建模分析，構(gòu)設(shè)流量統(tǒng)計(jì)和波動(dòng)預(yù)測(cè)模型。同時(shí)，將跟進(jìn)修改本文算法，以實(shí)現(xiàn)針對(duì)擁塞程度和范圍的自適應(yīng)統(tǒng)計(jì)感知。并且基于即時(shí)擁塞感知，將路由算力按需定向投入，在進(jìn)一步降低端到端丟包率和通信延遲的同時(shí)，嘗試保持全局較低的平均路由開銷，以優(yōu)化全網(wǎng)通信效率，讓未來的算法更好彌合“地面基站密度可按需按域增減”和“通信星座的衛(wèi)星密度全球大致均勻”這一硬件機(jī)制差異，提升天基網(wǎng)絡(luò)應(yīng)對(duì)瞬時(shí)高強(qiáng)度流量沖擊的自適應(yīng)能力。