基于跳數(shù)背壓策略的低軌衛(wèi)星網(wǎng)絡(luò)負載均衡路由

摘 要：隨著用戶規(guī)模的擴大，低軌衛(wèi)星網(wǎng)絡(luò)中流量的突發(fā)性和區(qū)域通信負載的不均衡性導(dǎo)致其面臨著愈發(fā)嚴(yán)重的負載均衡問題。對此，提出一種分布式基于跳數(shù)的背壓路由（hops-based back-pressure routing， HBPR）協(xié)議。HBPR首先根據(jù)鏈路中間節(jié)點距離目的衛(wèi)星的剩余跳數(shù)計算鏈路權(quán)重。然后，為控制可用轉(zhuǎn)發(fā)路徑數(shù)量，將可用傳播區(qū)域限制在由源節(jié)點目的節(jié)點構(gòu)成的矩形拓撲區(qū)域，以降低傳播代價。最后，采用分布式方式設(shè)計HBPR，在無需收集全網(wǎng)拓撲信息的條件下實現(xiàn)低擁塞最短鏈路的動態(tài)選擇和流量均衡分配。通過理論分析證明了HBPR吞吐量的最優(yōu)性。網(wǎng)絡(luò)仿真結(jié)果表明，與現(xiàn)有路由協(xié)議相比，HBPR具有更高的網(wǎng)絡(luò)吞吐量和更低的時延。

關(guān)鍵詞： 負載均衡; 背壓路由; 低軌衛(wèi)星網(wǎng)絡(luò); 路由協(xié)議; 跳數(shù)計算

中圖分類號： TN 927 文獻標(biāo)志碼： A""" DOI：10.12305/j.issn.1001-506X.2024.10.32

Load balancing routing for low Earth orbit satellite network with

hops-based back-pressure strategy

HAN Chi^1， XIONG Wei^1， YU Ronghuan^1， LIU Yali FU Jingyu³

（1. School of Space Information， Space Engineering University， Beijing 101400， China;

2. National Key Laboratory of Space Target Awareness， Space Engineering University，

Beijing 101400， China; 3. Jiuquan Satellite Launch Center， Jiuquan 732750， China）

Abstract： With the expansion of users scale in low Earth orbit （LEO） satellite networks， the bursty characteristic of network traffic and imbalanced regional communication load lead to the problem of load disequilibrium. A distributed hops-based back-pressure routing （HBPR） is proposed. HBPR calculates the link weight according to the remaining hops of the link’s intermediate node to the destination satellite， firstly. Then， in order to control the number of available forwarding paths， the permitted propagation area is limited to a rectangular topology region shaped by source nodes and destination nodes to reduce the propagation cost. Finally， the HBPR is designed in a distributed way to realize the dynamic selection of the shortest link with low congestion and balanced distribution of traffic without collecting topology information of the whole network. The throughput optimality of HBPR is proved by theoritical analysis. Web simulation results show that compared with the existing routing protocols， HBPR has higher network throughput and lower delay.

Keywords： load balancing; back-pressure routing （BPR）; low Earth orbit （LEO） satellite network; routing protocol; hops-count

0 引 言

衛(wèi)星網(wǎng)絡(luò)具有覆蓋范圍廣、通信容量大的特點，可借助星間組網(wǎng)突破地理條件限制，為全球用戶提供高傳輸速率、低時延、無縫銜接的網(wǎng)絡(luò)接入服務(wù)，已成為天地一體化網(wǎng)絡(luò)的重要組成部分。低地球軌道（low Earth orbit，LEO）衛(wèi)星網(wǎng)絡(luò)部署的軌道高度位于160～2 000 km，相比于地球靜止軌道（geostationary Earth orbit， GEO）和中地球軌道（medium Earth orbit，MEO）網(wǎng)絡(luò)，LEO衛(wèi)星網(wǎng)絡(luò)能夠以更低的功耗實現(xiàn)更低的傳輸時延和更高的傳輸速率^［13］。例如，Iridium系統(tǒng)由66顆軌道高度為780 km、傾角為86.4°的LEO衛(wèi)星組成，為首個搭載星間鏈路的衛(wèi)星通信系統(tǒng)，可為全球提供移動數(shù)據(jù)服務(wù)^［4］。Starlink星座由SpaceX公司于2015年提出，計劃部署約42 000顆衛(wèi)星以創(chuàng)建LEO巨型星座網(wǎng)絡(luò)，并與地面網(wǎng)絡(luò)融合，最終實現(xiàn)近全球范圍的寬帶互聯(lián)網(wǎng)接入^［5］。

由于網(wǎng)絡(luò)流量的時間突發(fā)性和用戶地理分布的不均勻性，隨著用戶規(guī)模的不斷擴大，LEO衛(wèi)星網(wǎng)絡(luò)的負載不均衡問題愈發(fā)凸顯^［6］。在融合地面網(wǎng)絡(luò)的LEO衛(wèi)星網(wǎng)絡(luò)中，地面信關(guān)站之間的通信較為繁忙，通信高峰時期兩者之間的最短路徑可能出現(xiàn)擁塞^［7］。在此情況下，LEO衛(wèi)星網(wǎng)絡(luò)的巨型網(wǎng)狀拓撲提供了多條候選路徑。通過對網(wǎng)絡(luò)負載的合理管理與分配，可兼顧衛(wèi)星網(wǎng)絡(luò)的高傳輸速率和低時延。

針對LEO衛(wèi)星網(wǎng)絡(luò)負載均衡問題，國內(nèi)外學(xué)者提出了多種路由策略。Li等^［8］提出一種基于狀態(tài)感知及負載均衡（state-aware and load-balancing， SALB）路由策略，SALB對鏈路狀態(tài)進行估計，動態(tài)設(shè)置隊列排隊時延權(quán)重，并使用最短路徑樹減少路由開銷，提升網(wǎng)絡(luò)吞吐量。Liu等^［9］設(shè)計一種混合全局局部負載（hybrid global-local load， HGL）均衡路由方案，將網(wǎng)絡(luò)流量需求分解為可預(yù)測的長期流量和不可預(yù)測的短期擾動流量，在此基礎(chǔ)上優(yōu)化流量分配，實現(xiàn)擁塞消除。Wang等^［10］提出一種基于擁塞預(yù)測的負載均衡路由（load balancing routing based on congestion prediction， LBRA-CP），將負載均衡轉(zhuǎn)換為多目標(biāo)優(yōu)化問題。通過預(yù)測鏈路擁塞，以智能優(yōu)化算法求解最優(yōu)路徑，提升網(wǎng)絡(luò)吞吐量。Liu等^［11］提出一種低復(fù)雜度路由算法（low complexity routing algorithm， LCRA）。LCRA利用相鄰衛(wèi)星的擁塞信息，選擇擁塞程度較低的下一跳進行轉(zhuǎn)發(fā)。當(dāng)僅有單條路徑時，LCRA選擇等待一段時間再轉(zhuǎn)發(fā)數(shù)據(jù)包，提高網(wǎng)絡(luò)傳輸速率并降低時延。劉沛龍等^［12］設(shè)計一種衛(wèi)星并行鏈路不相交多徑路由協(xié)議（satellite parallel edge-disjoint multipath routing protocol， SPEMR），每顆衛(wèi)星迭代計算多條至宿點不相交最短路徑，根據(jù)最短路徑樹進行分組轉(zhuǎn)發(fā)，實現(xiàn)遙感數(shù)據(jù)下行任務(wù)場景下路由性能的提升。這些工作主要側(cè)重于LEO衛(wèi)星網(wǎng)路集中式路由方案設(shè)計，難以處理網(wǎng)絡(luò)重負載條件下的資源失衡問題。背壓路由（back-pressure routing， BPR）通過節(jié)點間數(shù)據(jù)包隊列的擁塞梯度處理路由流量^［1314］，已被廣泛應(yīng)用于解決多跳網(wǎng)絡(luò)的負載均衡問題，如無線傳感器網(wǎng)絡(luò)（wireless sensor network，WSN）和移動自組織網(wǎng)絡(luò)（mobile Ad-Hoc network，MANET）^［1516］。與多跳網(wǎng)絡(luò)類似，LEO衛(wèi)星網(wǎng)絡(luò)中的數(shù)據(jù)包遵循多跳傳輸機制^［17］，因此BPR亦適用于LEO衛(wèi)星網(wǎng)絡(luò)的流量突發(fā)和負載不均衡問題。然而，相比于WSN或MANET，LEO衛(wèi)星網(wǎng)絡(luò)中的節(jié)點距離較遠，且網(wǎng)絡(luò)拓撲為曼哈頓網(wǎng)絡(luò)^［18］，源目的節(jié)點間存在數(shù)量眾多的互聯(lián)鏈路和可用路徑，標(biāo)準(zhǔn)BPR在此情況下將探索大量路由路徑，導(dǎo)致巨大的端到端延遲和計算存儲開銷。因此，標(biāo)準(zhǔn)BPR策略難以適用于LEO衛(wèi)星網(wǎng)絡(luò)場景。

針對此問題，本文將衛(wèi)星網(wǎng)絡(luò)端到端跳數(shù)這一關(guān)鍵傳輸代價度量指標(biāo)引入BPR。相比于傳統(tǒng)無線網(wǎng)絡(luò)，LEO衛(wèi)星網(wǎng)絡(luò)節(jié)點間距可達數(shù)百乃至數(shù)千公里^［19］。以Starlink星座Shell I為例^［3］，在軌道高度為550 km時，同軌道面內(nèi)相鄰衛(wèi)星間距約為1 972 km，相鄰軌道面內(nèi)相鄰衛(wèi)星間距則在880～1 400 km范圍內(nèi)變化。巨大的鄰節(jié)點間距導(dǎo)致端到端傳輸跳數(shù)對網(wǎng)絡(luò)時延存在較大影響。在確定下一跳路徑時，除背壓策略外，還應(yīng)將端到端剩余跳數(shù)納入考慮。本文提出一種分布式基于跳數(shù)的BPR （hops-based BPR，HBPR）和緩存調(diào)度策略，將BPR策略與端到端跳數(shù)相結(jié)合，實現(xiàn)自適應(yīng)資源分配和負載感知路由。同時，引入流傳播限制域以降低傳播時延。經(jīng)仿真實驗驗證，相比于集中式策略，所提策略組合可在較低傳輸成本條件下提升網(wǎng)絡(luò)吞吐量并降低網(wǎng)絡(luò)延時。

1 系統(tǒng)模型與BPR策略

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

LEO衛(wèi)星網(wǎng)絡(luò)可用G=（V，E）表示，其中V為衛(wèi)星節(jié)點集合，E為節(jié)點間星間鏈路集合。星間鏈路類型包括面內(nèi)星間鏈路和面間星間鏈路，面內(nèi)星間鏈路用于連接同一軌道面內(nèi)前后兩顆衛(wèi)星，面間星間鏈路則用于連接兩個相鄰軌道上的相鄰衛(wèi)星。假設(shè)網(wǎng)絡(luò)中包含的衛(wèi)星節(jié)點數(shù)量為N，每個節(jié)點通常包含兩條面內(nèi)鏈路和兩條面間鏈路，如圖1所示。

得益于LEO衛(wèi)星網(wǎng)絡(luò)相對規(guī)則的拓撲結(jié)構(gòu)，可將其建模為曼哈頓網(wǎng)絡(luò)^［20］，其二維拓撲如圖2所示。S_n，m表示第n個軌道面上的第m顆衛(wèi)星，每顆衛(wèi)星包含兩條面內(nèi)鏈路和兩條面間鏈路，藍色連接線為面內(nèi)鏈路，衛(wèi)星沿箭頭方向運動，黑色連接線為面間鏈路。衛(wèi)星在軌道上的運動為周期性和可預(yù)測的^［21］，通常假設(shè)在一段較小時間周期內(nèi)，LEO衛(wèi)星網(wǎng)絡(luò)拓撲保持恒定^［22］，面內(nèi)鏈路長度不會改變，而面間鏈路長度會隨著衛(wèi)星緯度發(fā)生變化，低緯度區(qū)域面間鏈路距離較長而高緯度區(qū)域面間鏈路距離相對縮短。

1.2 BPR協(xié)議

BPR起源于Tassiulas等在文獻［23］中提出的無線數(shù)據(jù)包多跳網(wǎng)絡(luò)，是一種根據(jù)多跳網(wǎng)絡(luò)中相鄰節(jié)點間擁塞梯度進行動態(tài)流量分配的算法^［24］。BPR并不構(gòu)建從源節(jié)點至目的節(jié)點的具體路徑，僅構(gòu)建每個時隙的隊列積壓差^［25］，BPR以積壓差最大化為目標(biāo)進行路由決策并傳輸數(shù)據(jù)^［13］。給定衛(wèi)星網(wǎng)絡(luò)G=（V，E），以（a，b）表示衛(wèi)星節(jié)點a和b之間的星間鏈路，P^c_a（t）為t時刻節(jié)點a處數(shù)據(jù)流c的隊列積壓，P^c_b（t）為t時刻節(jié)點b處數(shù)據(jù)流c的隊列積壓，則數(shù)據(jù)包流c在節(jié)點a，b之間的隊列積壓差為P^c_a（t）－P^c_b（t）。通常，單個衛(wèi)星節(jié)點上存在多個數(shù)據(jù)包流，以D_ab（t）定義鏈路（a，b）上最大數(shù)據(jù)包隊列積壓差。

D_ab（t）=maxc：（a，b）［P^c_a（t）－P^c_b（t）］（1）

在此基礎(chǔ)上，按如下策略為數(shù)據(jù)包流c分配鏈路（a，b）上的傳輸速率：

max∑Na=1∑Nb=1r_ab（t）D_ab（t）

s.t. r_ab（t）∈Γ_s（t）（2）

式中：r_ab（t）為鏈路（a，b）上的數(shù)據(jù)傳輸速率，Γ_s（t）包含了網(wǎng)絡(luò)拓撲中所有可用的傳輸速率矩陣?；谝陨喜呗?，BPR可應(yīng)用于具有不同目的端的多數(shù)據(jù)包流網(wǎng)絡(luò)，實現(xiàn)網(wǎng)絡(luò)吞吐量的最大化，并支持任何流到達率和信道狀態(tài)概率。

2 衛(wèi)星網(wǎng)絡(luò)端到端跳數(shù)

在LEO衛(wèi)星網(wǎng)絡(luò)中，衛(wèi)星節(jié)點間具有較大的物理距離和傳播時延，可利用到目的節(jié)點的剩余跳數(shù)使數(shù)據(jù)包沿較短路徑傳播，以改善網(wǎng)絡(luò)延時性能。本節(jié)將分析傾斜軌道星座中任意節(jié)點間最短傳播跳數(shù)，為BPR策略改進提供依據(jù)。

給定一個由n個軌道面構(gòu)成的Walker-delta星座，每個軌道面上均勻分布m顆衛(wèi)星，所有軌道面的軌道傾角均為α且沿赤道等角度間隔分布，相鄰軌道面升交點赤經(jīng)差為ΔΩ=2π/n，同軌道面上相鄰衛(wèi)星相位差為ΔΦ=2π/m。設(shè)星座相位因子為F，則相鄰軌道上相鄰衛(wèi)星相位差為Δf=2πF/（mn）。LEO傾斜軌道星下點軌跡如圖3所示，可以看出，傾斜軌道衛(wèi)星網(wǎng)絡(luò)中源節(jié)點至目的節(jié)點的跳數(shù)（紫色箭頭）由兩部分組成^［26］：橫向移動的面間跳數(shù)H_h以及縱向移動的面內(nèi)跳數(shù)H_v。

2.1 面間跳數(shù)H_h

表現(xiàn)為橫向移動的軌道面間跳數(shù)H_h由圖4中衛(wèi)星1和衛(wèi)星2所在的初始軌道平面的升交點經(jīng)度差ΔL₀決定^［27］：

ΔL₀=（L₂－L₁）mod2π∈［0，2π］（3）

式中：L₁、L₂分別為衛(wèi)星1和衛(wèi)星2的升交點赤經(jīng)，若目的節(jié)點在西側(cè)則對應(yīng)的經(jīng)度差為2π－ΔL₀。由于相鄰軌道面升交點精度差ΔΩ=2π/n為常量，則東、西向移動的面間跳數(shù)分別為

H^←_h=〈2π－ΔL₀ΔΩ〉

H^→_h=〈ΔL₀ΔΩ〉（4）

式中：〈x〉=sgn（x）x+0.5表示x被四舍五入到最接近的整數(shù);H^←_h為西向軌道面間跳數(shù);H^→_h為東向軌道面間跳數(shù)。

2.2 面內(nèi)跳數(shù)H_v

軌道面間衛(wèi)星跳數(shù)由源、目的衛(wèi)星升交點經(jīng)度差ΔL₀決定，相對應(yīng)的軌道面內(nèi)跳數(shù)取決于衛(wèi)星間相位角差Δu。由于每一次軌道面內(nèi)跳躍使相位角增加ΔΦ，而每一次軌道面間跳躍使相位角增加Δf，因此目的衛(wèi)星（衛(wèi)星2）的相位角可表示為

u₂=u₁+（H^→_h·Δf）+（H^↗_v·ΔΦ）Δu→（5）

式中：H^→_h為面間東向跳數(shù)，H^↗_v為面內(nèi)東向跳數(shù)。為計算面內(nèi)跳數(shù)H_v，首先需從總體相位差Δu=u₂－u₁剔除面間跳引起的相位差H^→_h·Δf。與面間跳數(shù)的計算類似，相位差Δu的計算區(qū)分東、西兩個傳播方向：

Δu→=（u₂－u₁－H^→_h·Δf）mod2π

Δu←=（u₂－u₁+H^←_h·Δf）mod2π（6）

式中：Δf為每一次面間跳導(dǎo)致的相位角變化量;H^→_h為向東傳播所需跳數(shù);H^←_h為向西傳播所需跳數(shù)。

由于衛(wèi)星在軌道上的運行包括上行（自西南向東北）和下行（自西北向東南），在上行和下行軌道上又分為前向跳躍和后向跳躍，因此本文分4個方向計算面內(nèi)跳數(shù)：

H^↖_v=Δu←ΔΦ

H^↗_v=Δu→ΔΦ

H^↙_v=2π－Δu←ΔΦ

H^↘_v=2π－Δu→ΔΦ（7）

式中：ΔΦ為同一軌道面內(nèi)相鄰衛(wèi)星間相位差;Δu←為被西向面內(nèi)跳所覆蓋的相位角差值;Δu→為被東向面內(nèi)跳所覆蓋的相位角差值;H^↖_v為向西北方向的面內(nèi)跳數(shù)量;H^↗_v為向東北方向的面內(nèi)跳數(shù)量;H^↙_v為向西南方向的面內(nèi)跳數(shù)量;H^↘_v為向東南方向的面內(nèi)跳數(shù)量。

上文分別計算了可能的軌道面間跳數(shù)和可能的軌道面內(nèi)跳數(shù)。因此，傾斜軌道星座中端到端最小跳數(shù)H可通過求取可能跳數(shù)的最小值獲得

H=minH^←_h+H^↖_v，H^←_h+H^↙_v，H^→_h+H^↗_v， H^→_h+H^↘_v（8）

3 HBPR

3.1 HBPR算法

在傳統(tǒng)基于隊列的BPR協(xié)議中，網(wǎng)絡(luò)節(jié)點的報文積壓通常僅考慮緩存中報文數(shù)量，而不考慮報文時延^［2829］，這可能導(dǎo)致較大的通信時延，影響網(wǎng)絡(luò)性能。通過上文的分析，在LEO衛(wèi)星網(wǎng)絡(luò)中，節(jié)點間跳數(shù)對于分組時延存在較大影響。為提升BPR協(xié)議的時延性能，本文采用下一跳至目的節(jié)點的端到端跳數(shù)近似節(jié)點中每個分組到目的節(jié)點的傳播時延，對應(yīng)時延定義為目的跳數(shù)時延。給定衛(wèi)星節(jié)點a處數(shù)據(jù)包流c的分組集合為Q^c_a，對于每個分組p∈Q^c_a，定義其從節(jié)點a至目的節(jié)點b的目的跳數(shù)時延為H（p）。

在LEO衛(wèi)星網(wǎng)絡(luò)中，周期性、可預(yù)測的運行軌道使得其軌道根數(shù)是已知的。因此，根據(jù)第2節(jié)所提計算策略，中間衛(wèi)星可快速求解候選下一跳節(jié)點至目的節(jié)點的端到端跳數(shù)。通過定義每個分組的目的跳數(shù)時延，數(shù)據(jù)流c在節(jié)點a處所有分組累積目的跳數(shù)時延記為∑H（p）。本文將累計的目標(biāo)跳數(shù)時延定義為BPR的積壓度量Q-^c_a：

Q-^c_a=∑p∈QcaH（p）=|Q^c_a（t）|×H（p）（9）

式中：|Q^c_a（t）|為t時刻節(jié)點a處數(shù)據(jù)包流c中的分組數(shù)量。在此基礎(chǔ)上，t時刻，鏈路（a，b）中數(shù)據(jù)包流c的基于目的跳數(shù)時延的積壓差可定義為

ω-_a→b（t）=maxc［Q-^c_a（t）－Q-^c_b（t）］（10）

根據(jù)式（2）和式（3），按如下策略為數(shù)據(jù)包流c在鏈路（a，b）上確定傳輸速率：

max∑Na=1∑Nb=1r_ab（t）ω-_a→b（t）（11）

s.t. r_ab（t）∈Γ_s（t）

式中：r_ab（t）為流c在鏈路（a，b）上的傳輸速率。

HBPR的緩存管理與隊列積壓計算示例如圖4所示。

每個網(wǎng)絡(luò)節(jié)點同時維護數(shù)據(jù)包隊列和虛擬跳數(shù)時延隊列，以計算每個數(shù)據(jù)包流的跳數(shù)時延積壓Q-。假設(shè)源節(jié)點s發(fā)送數(shù)據(jù)包流c至目的節(jié)點d，當(dāng)數(shù)據(jù)包到達節(jié)點A時，將按如下步驟確定選擇節(jié)點B，E，F(xiàn)中的哪個節(jié)點作為下一跳。在t時刻，數(shù)據(jù)包流c在節(jié)點A處數(shù)據(jù)包隊列長度為Q^c_A（t）=6。同理，數(shù)據(jù)包流c在節(jié)點B， E， F處的隊列長度為Q^c_B（t）=4，Q^c_E（t）=4，Q^c_F（t）=5。因此，節(jié)點A至節(jié)點B，E，F(xiàn)的隊列積壓差分別為2，2，1。在傳統(tǒng)基于隊列的BPR協(xié)議中，節(jié)點A至節(jié)點B，E具有相同的積壓差。在所提HBPR中，根據(jù)式（10）計算到目的節(jié)點的積壓差。在本例中，節(jié)點B至目的節(jié)點的跳數(shù)小于節(jié)點E，因此排除節(jié)點E作為下一跳。假設(shè)節(jié)點B，F(xiàn)具有相同的目的節(jié)點跳數(shù)，節(jié)點A至節(jié)點B的隊列積壓差Q^c_AB（t）=2，大于節(jié)點A至節(jié)點F的積壓差Q^c_AF（t）=1，因此節(jié)點B相較于節(jié)點F更優(yōu)，應(yīng)選擇節(jié)點B作為下一跳節(jié)點。

3.2 分布式路由算法

在LEO衛(wèi)星星座中，由于衛(wèi)星平臺尺寸和功耗的限制，星載計算資源和存儲資源較為緊張。多跳的網(wǎng)絡(luò)結(jié)構(gòu)使得每顆衛(wèi)星可以通過星間鏈路連接至周圍衛(wèi)星，適合采用分布式方式部署路由協(xié)議。

3.2.1 隊列控制

假定源節(jié)點s，目的節(jié)點d，分組p到達鏈路（s，d）上的中間節(jié)點n時，可計算該分組與目的節(jié)點間的目的跳數(shù)時延H（p）。當(dāng)?shù)谝粋€分組到達節(jié)點n時，在節(jié)點n創(chuàng)建積壓為Q-^c_n的虛擬跳數(shù)時延隊列，并計算H（p）。然后，當(dāng)分組p到達節(jié)點n時，Q-^c_n將增加H（p）。當(dāng)分組p從節(jié)點n發(fā)送至下一跳，則Q -^c_n對應(yīng)減少H（p）。以上過程計算復(fù)雜度僅為O（1）。

假設(shè)節(jié)點數(shù)為N的網(wǎng)絡(luò)中每個節(jié)點與周圍R個節(jié)點相鄰，HBPR需維護虛擬跳數(shù)時延隊列數(shù)上界為R（N－1）（N－2）。在LEO衛(wèi)星網(wǎng)絡(luò)中，通常R=4，如圖3所示。因此，每個節(jié)點需維護O（N2）個虛擬跳數(shù)時延隊列，存儲壓力相對較小。

3.2.2 傳播區(qū)域控制

在LEO衛(wèi)星網(wǎng)絡(luò)中，每個節(jié)點包含4條星間鏈路，源目的節(jié)點間可用路徑數(shù)量根據(jù)衛(wèi)星數(shù)目呈指數(shù)速率增加。若不對數(shù)據(jù)包可用傳播區(qū)域加以限制，將導(dǎo)致數(shù)據(jù)包跨越范圍過大，影響網(wǎng)絡(luò)時延性能。因此，本文將數(shù)據(jù)包可用傳播區(qū)域限制在源節(jié)點s和目的節(jié)點d構(gòu)成的矩形區(qū)域內(nèi)，如圖5所示，以在保證可用鏈路數(shù)量的同時降低冗余。

圖5中，藍色區(qū)域為可用傳播區(qū)域，其他區(qū)域為禁止傳播區(qū)域。HBPR根據(jù)所定義最大跳數(shù)時延權(quán)重分配鏈路，在藍色區(qū)域內(nèi)傳輸數(shù)據(jù)包。數(shù)據(jù)包流c在鏈路（s，d）到達節(jié)點n時，首先在發(fā)送緩沖區(qū)頭部出列一個數(shù)據(jù)包p，然后p在可用傳播區(qū)域內(nèi)，根據(jù)ω-^c_n→b（t）最大化準(zhǔn)則確定下一跳路徑，b為決策得到的下一跳節(jié)點。

b=arg maxb∈N* ω-^c_n→b（t） （12）

ω-^c_n→b（t）=Q-^c_n（t）-Q-^c_b（t）

=∑p∈QcnH（p）-∑p∈Q^cbH（p） （13）

式中：N為鏈路（n，d）上節(jié)點n下一跳候選節(jié)點的集合。HBPR算法的詳細步驟如算法1所示。

算法 1 "HBPR

將數(shù)據(jù)包插入隊列：

假設(shè)源節(jié)點n至目的節(jié)點d上的數(shù)據(jù)流為c;t時刻，p到達節(jié)點n;

if 節(jié)點n為p的目的節(jié)點 then

將數(shù)據(jù)包p傳遞至網(wǎng)絡(luò)上層

else

將數(shù)據(jù)包p放入緩沖區(qū);

將目的跳數(shù)時延更新為H（p）

將虛擬跳數(shù)時延隊列更新為

Q-^c_n（t）←Q-^c_n（t）+H（p）

end if

數(shù)據(jù)包轉(zhuǎn)發(fā)：

在發(fā)送緩沖區(qū)頭部將p出列;

for 節(jié)點n的所有鄰居節(jié)點N^* do

if N^*屬于可用轉(zhuǎn)發(fā)區(qū)域 then

為所有鄰居節(jié)點N^*計算ω-^c_n→b（t）

end if

end for

根據(jù)式（13）確定下一跳節(jié)點b， 在鏈路（n， b）上傳輸數(shù)據(jù)包p， 然后在緩沖區(qū)刪除p;

將虛擬跳數(shù)時延隊列更新為

Q-^c_n（t）←Q-^c_n（t）－H（p）

3.3 HBPR吞吐量分析

對于LEO衛(wèi)星網(wǎng)絡(luò)等排隊網(wǎng)絡(luò)，當(dāng)流到達率使網(wǎng)絡(luò)處于穩(wěn)定狀態(tài)時其吞吐量達到最大^［14］。因此，HBPR吞吐量最優(yōu)化策略等價于保證網(wǎng)絡(luò)在允許的流到達率λ^c_n上穩(wěn)定的策略，即最小化t和t+1時刻HBPR策略的隊列積壓差。本文采用Lyapunov偏移函數(shù)衡量t時刻和t+1時刻的隊列積壓差：

Q^（t）=∑n∈N∑c∈NQ^^c_n（t）（14）

Δt=∑n∈N∑c∈NE［Q^^c_n（t+1）²－Q^^c_n（t）²2Q^（t）］（15）

考慮動態(tài)路由過程，單個時隙內(nèi)隊列積壓滿足：

Q^^c_n（t+1）≤max{（Q^^c_n（t）－X^^c_n），0}+Y^^c_n+H（A^c_n（t））（16）

式中：X^c_n（t）和Y^c_n（t）分別表示t時刻鏈路（a，b）和（b，a）上報文數(shù)量。由于當(dāng)q≥0，a≥0，b≥0時

（max{q－b，0}+a）²≤q²+a²+b²+2q（a－b）（17）

因此，Δt滿足：

Δt≤M+∑n∈N∑c∈NQ^^c_n（t）

·EH（A^c_n（t））－X^^c_n（t）+Y^^c_n（t）Q^（t）（18）

式中：M和H（A^c_n（t））為有限值。因此，為最小化Δt，需最大化：

E［∑n∈N∑c∈nQ^^c_n（t）·X^^c_n（t）－Y^^c_n（t）Q^（t）］

即最大化：

∑n∈N∑c∈nQ^^c_n（t）·［X^^c_n（t）－Y^^c_n（t）］

其中，

X^^c_n（t）－Y^^c_n（t）=H（X^c_n（t））－H（Y^c_n（t））=

∑p∈X^cn（t）H（p）－∑p∈Y^cn（t）H（p） （19）

假設(shè)網(wǎng)絡(luò)中所有數(shù)據(jù)包隨機到達，當(dāng)觀測時間足夠長時，可以得到

H（X^c_n（t））X^c_n（t）=H（Y^c_n（t））Y^c_n（t）=H（Q^c_n（t））Q^c_n（t）=Q^^c_n（t）Q^c_n（t）（20）

基于以上假設(shè)，需最大化：

∑n∈N∑c∈nQ^^c_n（t）［H（X^^c_n（t））－H（Y^^c_n（t））］=

∑n∈N∑c∈nQ^^c_n（t）H（X^^c_n（t））［X^c_n（t）Q^c_n（t）－Y^c_n（t）Q^c_n（t）］=

∑n∈N∑c∈nQ^^c_n（t）H（Q^c_n（t））Q^c_n（t）［X^c_n（t）－Y^c_n（t）］=

∑n∈N∑c∈nQ^^c_n（t）H（Q^c_n（t））Q^c_n（t）［∑b∈Nr^c_nb（t）－∑a∈Nr^c_an（t）］

（21）

由于Q^^c_n（t）/Q^c_n（t）為非負值，最大化上述等式等價于最大化：

∑n∈N∑c∈nH（Q^c_n（t））·［∑b∈Nr^c_nb（t）－∑a∈Nr^c_an（t）］=

∑a∈N∑b∈N∑c∈nr^c_ab（t）·［H（Q^c_a（t））－H（Q^c_b（t））］=

∑a∈N∑b∈N∑c∈nr^c_ab（t）·［Q^^c_a（t）－Q^^c_b（t）］=

∑a∈N∑b∈N∑c∈nr^c_ab（t）·ω^^c_ab（t）（22）

式中：ω^^c_ab（t）為鏈路（a，b）上數(shù)據(jù)包流c的隊列積壓差。HBPR決策即為選擇傳輸速率r^c_ab（t）以最大化式（22）及最小化Δt，其中最大化即為HBPR策略。因此，通過考慮衛(wèi)星間剩余跳數(shù)，HBPR是一個最優(yōu)吞吐量路由方案。

4 仿真實驗與結(jié)果分析

4.1 實驗設(shè)置

本文采用NS3網(wǎng)絡(luò)仿真平臺和類Starlink星座的傾斜軌道星座評估HBPR策略的性能。星座由648顆衛(wèi)星構(gòu)成，包含18個軌道面，每個軌道面均勻分布36顆衛(wèi)星。軌道高度為550 km，軌道傾角為53.0°。在網(wǎng)絡(luò)參數(shù)設(shè)置方面，與LEO衛(wèi)星網(wǎng)絡(luò)相關(guān)研究類似^［3031］，本文為每顆衛(wèi)星設(shè)置4條雙向星間鏈路，包括兩條軌道面內(nèi)鏈路和兩條相鄰軌道鏈路，上、下行鏈路和星間鏈路的鏈路傳輸速率設(shè)置為10 Mbps^［32］，采用數(shù)據(jù)包大小為512 byte的恒定流量。每輪仿真的模擬時間設(shè)置為120 s。星座及網(wǎng)絡(luò)參數(shù)設(shè)置如表1所示。

由于全球區(qū)域通信負載地理分布的不均勻性，分別設(shè)置了分布于60°S至60°N的8個源流量節(jié)點和目的流量節(jié)點，共組合成8組源目的對。源目的節(jié)點對應(yīng)城市如表2所示，衛(wèi)星和流量節(jié)點的分布情況如圖6所示。網(wǎng)絡(luò)流量從源節(jié)點附近地面站發(fā)出，通過與其距離最近的衛(wèi)星接入LEO衛(wèi)星網(wǎng)絡(luò)，到達距離目的節(jié)點最近的衛(wèi)星時流量落地。

在NS3網(wǎng)絡(luò)仿真平臺實現(xiàn)所提出的HBPR，并將之與使用鏈路距離而非跳數(shù)作為BPR積壓度量的距離BPR（distance-based BPR， DBPR）進行了比較^［4］。為保證比較的準(zhǔn)確性，HBPR和DBPR協(xié)議傳輸區(qū)域均控制在矩形范圍內(nèi)。第2個對比路由協(xié)議為使用Dijkstra最短路徑的開放最短路徑優(yōu)先（open shortest path first， OSPF）。第3個對比路由協(xié)議為基于鏈路SALB路由，SALB路由同樣采用分布式方式獲取路由，通過鏈路狀態(tài)動態(tài)調(diào)整排隊時延權(quán)重^［6］。為從多個角度有效衡量不同路由協(xié)議的性能，本文采用以下性能指標(biāo)。

（1） 平均時延：所有消息從源節(jié)點到目的節(jié)點所經(jīng)歷的時間的均值。

（2） 平均轉(zhuǎn)發(fā)次數(shù)：每個數(shù)據(jù)包從源節(jié)點到目的節(jié)點所經(jīng)過的轉(zhuǎn)發(fā)次數(shù)的均值，衡量了數(shù)據(jù)包的平均交付代價。

（3） 網(wǎng)絡(luò)吞吐量：數(shù)據(jù)包到目的節(jié)點的整體成功投遞率。

（4） 數(shù)據(jù)傳送率：網(wǎng)絡(luò)中成功送達目的節(jié)點的報文數(shù)量與源節(jié)點發(fā)送的報文數(shù)量的比值。

4.2 實驗結(jié)果

為驗證HBPR協(xié)議在LEO衛(wèi)星網(wǎng)絡(luò)中有效性，在不同流量模式下開展HBPR與DBPR、OSPF和SALB路由協(xié)議的仿真實驗。本文所采用流量模式包括恒定碼率（constant bit rate，CBR）流量和泊松流量。

4.2.1 CBR流量

在CBR流量模式下，流量生成率從2 Mbps按0.25 Mbps步長逐步變化至4 Mbps，測試不同程度鏈路負載下路由協(xié)議的性能指標(biāo)，仿真結(jié)果如圖7所示。不同路由協(xié)議下源節(jié)點至目的節(jié)點的平均時延如圖7（a）所示，最短路徑的OSPF的平均時延最低，由于OSPF僅采用基于Dijkstra的最短路徑，僅從相鄰設(shè)備獲取信息整合路由表，當(dāng)鏈路負載較重時該協(xié)議將導(dǎo)致大量數(shù)據(jù)包被丟棄，導(dǎo)致網(wǎng)絡(luò)性能下降。所提出的HBPR采用跳數(shù)作為積壓度量，相較于采用鏈路長度作為度量的DBPR路由協(xié)議具有更小的鏈路時延。SALB路由協(xié)議根據(jù)鏈路狀態(tài)調(diào)整排隊時延的權(quán)重，整體時延相對較大。

LEO衛(wèi)星網(wǎng)絡(luò)執(zhí)行不同路由協(xié)議下的平均轉(zhuǎn)發(fā)次數(shù)如圖7（b）所示，平均轉(zhuǎn)發(fā)次數(shù)衡量了每個數(shù)據(jù)包在鏈路中的平均傳遞代價?？梢钥闯觯捎贖BPR采用跳數(shù)作為積壓度量，且將可用路徑限制在矩形傳播區(qū)域內(nèi)，相對于對比協(xié)議，HBPR的平均轉(zhuǎn)發(fā)次數(shù)具有較為顯著的優(yōu)勢。曼哈頓網(wǎng)絡(luò)的拓撲特性為LEO衛(wèi)星網(wǎng)絡(luò)提供了大量冗余鏈路，將傳播區(qū)域限制在一定區(qū)域內(nèi)可在不影響數(shù)據(jù)傳輸性能的前提下進一步降低傳輸成本。

圖7（c）為不同路由協(xié)議下網(wǎng)絡(luò)吞吐量隨流量生成率的變化情況，隨著CBR速率增加，路由協(xié)議的吞吐量呈現(xiàn)增加態(tài)勢。相比較而言，HBPR具有最大的網(wǎng)絡(luò)吞吐量，而OSPF的吞吐量最小。在流量生成率小于2.4 Mbps時，HBPR和DBPR具有相近的吞吐量性能，隨著鏈路負載繼續(xù)增大，DBPR吞吐量逐漸趨于最大值。

圖7（d）為數(shù)據(jù)傳送率的隨流量生成率的變化情況，當(dāng)CBR速率增加時，由于網(wǎng)絡(luò)負載加重，所有協(xié)議的數(shù)據(jù)傳送率均呈現(xiàn)降低的趨勢。相比較而言，HBPR實現(xiàn)了最高的數(shù)據(jù)傳送率，并表現(xiàn)出較好的負載均衡能力。當(dāng)CBR為4 Mbps

時，HBPR協(xié)議相比DBPR，數(shù)據(jù)傳送率提高了約11%。這是由于HBPR同時考慮了BPR和剩余跳數(shù)，采用中間衛(wèi)星到目的衛(wèi)星的剩余條數(shù)確定鏈路權(quán)重，利用基于剩余跳數(shù)時延的積壓差靈活平衡擁塞，取得了比采用距離度量的DBPR協(xié)議更好的均衡能力。

4.2.2 泊松流量

現(xiàn)實中網(wǎng)絡(luò)流量需求可采用泊松分布進行描述，本文測試了不同流量生成率下路由協(xié)議在泊松流量下的指標(biāo)性能，仿真結(jié)果如圖8所示。

可以看出，與CBR流量類似，HBPR具有最好的吞吐量性能和最低的傳輸代價，數(shù)據(jù)傳送率高于DBPR和SALB，顯示出較好的負載均衡性能。

5 結(jié) 論

LEO衛(wèi)星網(wǎng)絡(luò)具有覆蓋范圍廣、通信容量大的特點，將作為傳統(tǒng)地面網(wǎng)絡(luò)的重要補充，最終實現(xiàn)空天地一體化的網(wǎng)絡(luò)服務(wù)。然而，在LEO衛(wèi)星網(wǎng)絡(luò)中，網(wǎng)絡(luò)流量的突發(fā)性和用戶流量地理分布的不均勻性導(dǎo)致其面臨的負載均衡問題愈發(fā)嚴(yán)重。針對此問題，本文提出一種基于跳數(shù)時延的HBPR。首先，從理論上推導(dǎo)傾斜軌道LEO衛(wèi)星網(wǎng)絡(luò)中任意衛(wèi)星節(jié)點間最小端到端傳播跳數(shù)的快速求解方法。在此基礎(chǔ)上，HBPR將鏈路中間節(jié)點距離目的衛(wèi)星的剩余跳數(shù)作為BPR的積壓度量，動態(tài)選擇滿足低擁塞的最短路徑，實現(xiàn)LEO衛(wèi)星網(wǎng)絡(luò)流量開銷的平衡，在高負載條件下緩解網(wǎng)絡(luò)擁塞。同時，考慮到曼哈頓網(wǎng)絡(luò)特性造成的鏈路冗余，本文將鏈路可用傳播區(qū)域限制在由源節(jié)點和目的節(jié)點確定的矩形拓撲區(qū)域內(nèi)，以此控制傳播代價。以類Starlink的傾斜軌道星座為例，在NS3平臺進行了網(wǎng)絡(luò)仿真驗證。仿真結(jié)果表明，所提HBPR協(xié)議可在不增加鏈路傳輸代價的前提下提升網(wǎng)絡(luò)吞吐量，并優(yōu)化時延性能。相比于SALB、DBPR、OSPF等路由協(xié)議，HBPR能夠更加高效地均衡LEO衛(wèi)星網(wǎng)絡(luò)的過載流量。

參考文獻

［1］ MICHEL F， TREVISAN M， GIORDANO D， et al. A first look at Starlink performance［C］∥Proc.of the 22nd ACM Internet Mea-surement Conference， 2022： 130136.

［2］ KASSEM M M， RAMAN A， PERINO D， et al. A browser-side view of Starlink connectivity［C］∥Proc.of the 22nd ACM Internet Measurement Conference， 2022： 151158.

［3］ MCDOWELL J C. The low Earth orbit satellite population and impacts of the SpaceX Starlink constellation［J］. The Astrophy-sical Journal Letters， 2020， 892（2）： 3645.

［4］ DENG X， CHANG L， ZENG S Y， et al. Distance-based back-pressure routing for load-balancing LEO satellite networks［J］. IEEE Trans.on Vehicular Technology， 2023， 72（1）： 12401253.

［5］ LAI Z Q， LI H W， LI J C. StarPerf： characterizing network performance for emerging mega-constellations［C］∥Proc.of the IEEE 28th International Conference on Network Protocols， 2020.

［6］ JIANG D D， WANG F， LYU Z H， et al. QoE-aware efficient content distribution scheme for satellite-terrestrial networks［J］. IEEE Trans.on Mobile Computing， 2023， 22（1）： 443458.

［7］ HAN Z Z， XU C， ZHAO G F， et al. Time-varying topology model for dynamic routing in LEO satellite constellation networks［J］. IEEE Trans.on Vehicular Technology， 2023， 72（3）： 34403454.

［8］ LI X， TANG F L， CHEN L， et al. A state-aware and load-ba-lanced routing model for LEO satellite networks［C］∥Proc.of the IEEE Global Communications Conference， 2017： 16.

［9］ LIU Z L， LI J S， WANG Y R， et al. HGL： a hybrid global-local load balancing routing scheme for the internet of things through satellite networks［J］. International Journal of Distributed Sensor Networks， 2017， 13（3）： 155014771769258.

［10］ WANG H T， WEN G L， LIU N J， et al. A load balanced routing algorithm based on congestion prediction for LEO satellite networks［J］. Cluster Computing， 2019， 22（8）： 80258033.

［11］ LIU X M， JIANG Z Q， LIU C H， et al. A low-complexity probabilistic routing algorithm for polar orbits satellite constellation networks［C］∥Proc.of the IEEE/CIC International Conference on Communications in China， 2015.

［12］ 劉沛龍， 陳宏宇， 魏松杰， 等. LEO衛(wèi)星網(wǎng)絡(luò)海量遙感數(shù)據(jù)下行的負載均衡多徑路由算法［J］. 通信學(xué)報， 2017， 38（S1）： 135142.

LIU P L， CHEN H Y， WEI S J， et al. Load balancing multipath routing protocol for mass remote sensing data downlink in LEO satellite network［J］. Journal of Communications， 2017， 38（S1）： 135142.

［13］ 章萬靜. 無線傳感網(wǎng)絡(luò)中基于時延感知的背壓路由［J］. 傳感技術(shù)學(xué)報， 202 34（12）： 16841689.

ZHANG W J. Delay-aware back pressure routing algorithm in wireless sensor networks［J］. Chinese Journal of Sensors and Actuators， 202 34（12）： 16841689.

［14］ ZHUANG X F， REN Q. Channel congestion control model based on improved asynchronous back-pressure routing algorithm in wireless distributed networks［J］. Journal of Ambient Intelligence and Humanized Computing， 2020. DOI：10.1007/S1265202001685W.

［15］ JIAO Z Z， TIAN R， ZHANG B X， et al. DTN routing with back-pressure based replica distribution［J］. Journal of Communications and Networks， 2014， 16（4）： 378384.

［16］ YING L， SHAKKOTTAI S， REDDY A， et al. On combining shortest-path and back-pressure routing over multihop wireless networks［J］. IEEE/ACM Trans.on Networking， 201 19（3）： 841854.

［17］ HAI L， GAO Q H， WANG J， et al. Delay-optimal back-pressure routing algorithm for multihop wireless networks［J］. IEEE Trans.on Vehicular Technology， 2018， 67（3）： 26172630.

［18］ MAXEMCHUK N. Routing in the Manhattan street network［J］. IEEE Trans.on Communications， 1987， 35（5）： 503512.

［19］ JING Y J， YI L T， ZHAO Y L， et al. Deep-learning-based path computation without routing convergence in optical sate-llite networks［J］. Journal of Optical Communications and Networking， 2023， 15（5）： 294303.

［20］ WOOD L， CLERGET A， ANDRIKOPOULOS I， et al. IP routing issues in satellite constellation networks［J］. International Journal of Satellite Communications， 200 19（1）： 6992.

［21］ CHEN C， EKICI E. A routing protocol for hierarchical LEO/MEO satellite IP networks［J］. Wireless Networks， 2005， 11（4）： 507521.

［22］ EKICI E， AKYILDIZ I F， BENDER M D. A distributed routing algorithm for datagram traffic in LEO satellite networks［J］. IEEE/ACM Trans.on Networking， 200 9（2）： 137147.

［23］ TASSIULAS L， EPHREMIDES A. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multi-hop radio networks［J］. IEEE Trans.on Automatic Control， 199 37（12）： 19361948.

［24］ 陶勇. 容遲容斷網(wǎng)絡(luò)擁塞控制關(guān)鍵技術(shù)研究［D］. 長沙： 國防科學(xué)技術(shù)大學(xué)， 2011.

TAO Y. Research on the key techniques of congestion control for DTN［D］. Changsha： National University of Defense Technology， 2011.

［25］ AMIRI I S， PRAKASH J， BALASARASWATHI M. DABPR： a large-scale internet of things-based data aggregation back pressure routing for disaster management［J］. Wireless Networks， 2020， 26（4）： 23532374.

［26］ CHEN Q， GIAMBENE G， YANG L， et al. Analysis of inter-sa-tellite link paths for LEO mega-constellation networks［J］. IEEE Trans.on Vehicular Technology， 202 70（3）： 27432755.

［27］ 張馳， 陳全， 唐祖平， 等. 基于最小路由代價的巨型星座網(wǎng)絡(luò)接入策略［J］. 系統(tǒng)工程與電子技術(shù)， 2024， 46（5）： 17921800.

ZHANG C， CHEN Q， TANG Z P， et al. Access strategy of mega-constellation network based on minimum routing cost［J］. Systems Engineering and Electronics， 2024， 46（5）： 17921800.

［28］ CUI Y， YEH E M. Enhancing the delay performance of dynamic backpressure algorithms［C］∥Proc.of the Asilomar Conference on Signals， Systems and Computers， 2013： 2731.

［29］ ALRESAINI M， WRIGHT K L， KRISHNAMACHARI B， et al. Backpressure delay enhancement for encounter-based mobile networks while sustaining throughput optimality［J］. IEEE/ACM Trans.on Networking， 2016， 24（2）： 11961208.

［30］ JIANG X F， HUANG Y H， LI J J， et al. Spatio-temporal routing， redundant coding and multipath scheduling for deterministic satellite network transmission［J］. IEEE Trans.on Communications， 2023， 71（5）： 28602875.

［31］ LIU J C， ZHAO B K， XIN Q， et al. DRL-ER： an intelligent energy-aware routing protocol with guaranteed delay bounds in satellite mega-constellations［J］. IEEE Trans.on Network Science and Engineering， 202 8（4）： 28722884.

［32］ NEELY M J， MODIANO E， ROHRS C E. Dynamic power allocation and routing for time-varying wireless networks［J］. IEEE Journal on Selected Areas in Communications， 2005， 23（1）： 89103.

作者簡介

韓 馳（1997—），男，博士研究生，主要研究方向為巨型星座路由、衛(wèi)星網(wǎng)絡(luò)仿真。

熊 偉（1971—），男，研究員，博士，主要研究方向為網(wǎng)絡(luò)信息體系。

于榮歡（1983—），男，副研究員，博士，主要研究方向為衛(wèi)星星座設(shè)計、網(wǎng)絡(luò)信息體系。

劉亞麗（1998—），女，碩士研究生，主要研究方向為網(wǎng)絡(luò)信息體系、巨型星座設(shè)計。

付婧雨（2000—），女，碩士研究生，主要研究方向為巨型星座設(shè)計、液體火箭發(fā)動機流場仿真。