基于區(qū)域劃分的星間流量均衡路由算法

朱 博，雙 煒， 閆海平，喻竹希，李 波

(中國航天三江集團 航天行云科技有限公司，武漢 430048)

0 引言

低軌衛(wèi)星(low-earth orbit,LEO)通信技術(shù)是下一代移動通信技術(shù)的主要發(fā)展方向之一，IMT2030推進組指出，低軌衛(wèi)星網(wǎng)絡(luò)是6G時代的關(guān)鍵基礎(chǔ)設(shè)施，以為全球用戶提供無縫覆蓋的空天地一體化網(wǎng)絡(luò)為建設(shè)目標[1]。我國由于受地緣政治等因素的影響，用于接收衛(wèi)星下傳數(shù)據(jù)的信關(guān)站在建設(shè)和運營等方面受到諸多限制，難以在全球范圍內(nèi)廣泛部署。比如服務(wù)于我國衛(wèi)星網(wǎng)絡(luò)的信關(guān)站通常集中部署在某一片區(qū)域(國境內(nèi)以及一些友好國家)，導(dǎo)致在單位時間內(nèi)大量的回傳數(shù)據(jù)只能路由到少數(shù)幾個目的節(jié)點，從而在流量較大時容易導(dǎo)致局部鏈路的過載，甚至引發(fā)網(wǎng)絡(luò)擁塞[2-3]。因此，需要借鑒流量工程的思路，充分利用衛(wèi)星網(wǎng)絡(luò)中的冗余路徑，在路由計算時兼顧回傳流量的均衡問題。

低軌衛(wèi)星網(wǎng)絡(luò)與地面互聯(lián)網(wǎng)在拓撲結(jié)構(gòu)、應(yīng)用場景和用戶需求方面存在很大差異，因此，很難在衛(wèi)星網(wǎng)絡(luò)中直接使用成熟的地面網(wǎng)絡(luò)技術(shù)。比如提出了路由干擾概念的最小干擾路由算法[4]、將分布式路由模型用于低軌衛(wèi)星網(wǎng)絡(luò)的離散時間流量拓撲自適應(yīng)路由算法[5]以及分布式流量均衡路由算法[6]等，這些算法對于星間流量工程具有很強的啟發(fā)意義，但一些限制因素使其更適用于地面網(wǎng)絡(luò)場景，并且在當前的研究中，對于地面信關(guān)站部署受限的問題并未得到足夠的關(guān)注。針對該問題，本文提出了一種基于區(qū)域劃分的星間流量均衡路由算法。該算法在考慮信關(guān)站位置集中的情況下，首先根據(jù)衛(wèi)星星座的“反向縫”與信關(guān)站的相對位置關(guān)系將回傳流量密集的區(qū)域劃分為輕負荷區(qū)和重負荷區(qū)，然后針對不同的負荷區(qū)域，分別采用不同的路由策略，對于輕負荷區(qū)采用預(yù)加權(quán)最短路徑算法，在最小生成樹算法的基礎(chǔ)上增加新的預(yù)設(shè)置項，以路徑加權(quán)和最小為目標計算最優(yōu)路徑。對于重負荷區(qū)域，采用基于擁塞系數(shù)的最低權(quán)重路由算法，該算法利用擁塞系數(shù)來對鏈路權(quán)重進行分配，以此來減少擁塞發(fā)生的概率，從而最大化網(wǎng)絡(luò)吞吐量。在系統(tǒng)運行時，不同區(qū)域分別執(zhí)行兩種不同的算法，并使用分段路由(segment routing,SR)技術(shù)[7]來統(tǒng)一實施，最終達到流量均衡的目的。

1 系統(tǒng)建模

本文的主要研究對象是具備星間鏈路的地軌衛(wèi)星網(wǎng)絡(luò)，其中每顆衛(wèi)星可分別與同軌道面和相鄰軌道面上的四顆衛(wèi)星建立通信連接，同時還可通過星地間的饋電鏈路與地面信關(guān)站建立連接。對系統(tǒng)建模時需定義一些約束條件并對問題進行適當?shù)暮喕Ｊ紫?，假定地面信關(guān)站僅部署在有限的區(qū)域內(nèi)，并且每個信關(guān)站在單位時間內(nèi)只能與一顆衛(wèi)星建立通信鏈路，因此衛(wèi)星節(jié)點與星下小區(qū)具有一一對應(yīng)關(guān)系。此外，由于星座構(gòu)型的原因，第一個軌道面與最后一個軌道面之間存在“反向縫”，即這兩個軌道面上的衛(wèi)星彼此運行方向相反，相對移動速度很快，導(dǎo)致難以建立穩(wěn)定的通信連接，所以處于“反向縫”上的兩個軌道面之間通常沒有星間鏈路。最后，模型中所涉及的通信信道均被認為是理想信道，不考慮衰落，多徑等影響，并且將用戶與衛(wèi)星間的切換過程理想化，不考慮異常情況的發(fā)生。

網(wǎng)絡(luò)中所有衛(wèi)星均被看作理想的對等節(jié)點，令整個星座中衛(wèi)星節(jié)點總數(shù)為N×M，其中N表示軌道數(shù)，M表示每條軌道上的衛(wèi)星節(jié)點數(shù)。衛(wèi)星節(jié)點在軌道上呈均勻分布,除“反向縫”上的節(jié)點之外，所有節(jié)點都能包含兩條同軌鏈路和兩條異軌鏈路。因此，整個衛(wèi)星網(wǎng)絡(luò)拓撲可建模為一張由節(jié)點和邊組成的圖G(V,E)，令包含N個衛(wèi)星節(jié)點的集合為VS，網(wǎng)關(guān)節(jié)點集合為VGW，其中包含X個信關(guān)站節(jié)點，以及中心站節(jié)點VC(中心站可達任意信關(guān)站節(jié)點，且衛(wèi)星下行鏈路僅與中心站相連)。鏈路集合E中包含的星間鏈路條數(shù)為EISL，饋電鏈路集合為EF，信關(guān)站間的地面鏈路集合為EG。各信關(guān)站節(jié)點均可直接訪問中心站節(jié)點，EISL的帶寬為BISL，EF的帶寬為BF，EG可認為帶寬無窮大。

基于以上網(wǎng)絡(luò)模型，根據(jù)星座覆蓋情況將整個地球劃分為多個等面積的小區(qū)[8]，衛(wèi)星與小區(qū)在某一時刻具有唯一映射關(guān)系，即每個小區(qū)內(nèi)的用戶在任意時刻都僅能與一顆衛(wèi)星建立連接。用戶當前接入的衛(wèi)星如果移動到相鄰小區(qū)，則將觸發(fā)用戶與接入衛(wèi)星之間的服務(wù)切換[9]。與此同時，每個小區(qū)產(chǎn)生的上行流量可根據(jù)地理位置、經(jīng)濟程度以及人口數(shù)量境因素來進行初步的估計[10]。

(1)

(2)

(3)

綜上所述，本系統(tǒng)的求解目標可定義為在滿足以下兩個約束條件的情況下，設(shè)計路由算法來求解路徑P，使得吞吐量最大化。

(1)約束條件1：G=(V,E)

f(k),k∈[0,N-1]

(2)約束條件2：

2 星間流量均衡路由算法

2.1 算法描述

地面小區(qū)發(fā)起的上行流量會通過星間鏈路逐跳轉(zhuǎn)發(fā)到信關(guān)站上方的衛(wèi)星節(jié)點，由于信關(guān)站的位置分布不均勻，待下傳的流量最終會匯集到有限的幾顆衛(wèi)星上，使得靠近信關(guān)站區(qū)域的鏈路負荷過重。將這部分區(qū)域定義為重負荷區(qū)，除此之外的所有區(qū)域均定義為輕負荷區(qū)。重負荷區(qū)域的面積由覆蓋該區(qū)域的衛(wèi)星總數(shù)An×m來定量表示，其中n表示軌道數(shù)，m表示每條軌道上的衛(wèi)星數(shù)。因此輕負荷區(qū)域的面積為A(N-n×m)。由于“反向縫”的存在，根據(jù)星座“反向縫”與信關(guān)站集中區(qū)域的相對位置，將星下小區(qū)按照流量負荷的輕重進行劃分。反向縫與信關(guān)站的距離越遠，重負荷區(qū)面積越大，當反向縫處于信關(guān)站正上方時，重負荷區(qū)面積達到最小。

針對輕負荷區(qū)的路由策略將分為兩段來執(zhí)行。首先，流量從輕負荷區(qū)路由到重負荷區(qū)邊緣節(jié)點，然后與重負荷區(qū)產(chǎn)生的流量一同執(zhí)行后續(xù)的路由策略，直至目的信關(guān)站。因為輕負荷區(qū)的流量較少，在到達重負荷區(qū)邊緣節(jié)點前的路由可直接采用最短路徑算法生成最小生成樹(MST)，但是為了避免過多的流量同時選擇了相同的邊緣目的節(jié)點，采用預(yù)加權(quán)的方法來減少這類情況的發(fā)生。首先每個邊緣節(jié)點被路由算法選中的次數(shù)可以根據(jù)初始MST的原始路徑進行計算。對于使用頻次較高的邊緣節(jié)點，增加對應(yīng)的鏈路權(quán)重，以降低被算法選中的頻率。假設(shè)i所占據(jù)的邊緣節(jié)點數(shù)為xi，則鏈路權(quán)重函數(shù)可設(shè)置為(0.5+0.1xi)，其中0.5表示網(wǎng)絡(luò)中的初始鏈路權(quán)重，0.1作為阻尼因子來降低xi的調(diào)整幅度，從而避免權(quán)重值的過度震蕩。按照本路由策略，每條從輕負荷區(qū)域衛(wèi)星節(jié)點發(fā)起的流量會在重負荷區(qū)的某個邊緣節(jié)點處結(jié)束，然后與重負荷區(qū)域的流量合并開始執(zhí)行下一階段的路由。

重負荷區(qū)的路由策略與輕負荷區(qū)有很大區(qū)別。顯然，處于重負荷區(qū)的衛(wèi)星節(jié)點產(chǎn)生的流量僅會在區(qū)域內(nèi)路由直到目的信關(guān)站，而不會進入輕負荷區(qū)。重負荷區(qū)域的邊緣節(jié)點所承載的流量主要由兩部分組成，一部分直接來自地面小區(qū)的上行流量，另一部分則是來自輕負荷區(qū)。使用擁塞指數(shù)c(e)來描述鏈路的擁塞程度，如式(4)所示，其中b(e)表示鏈路e的帶寬，F(xiàn)(e)表示當前鏈路e上承載的總流量，r(e)表示鏈路e中的剩余帶寬。c(e)越大表明鏈路擁塞越嚴重，當r(e)=0且b(e)=F(e)時,c(e)=∞，此時說明鏈路e已經(jīng)沒有可用帶寬。相反，當c(e)=0且r(e)=b(e)時，F(xiàn)(e)=0，此時鏈路e的全部帶寬均可使用?？梢?，擁塞指數(shù)c(e)對于F(e)具有更加單調(diào)的遞增趨勢，對于鏈路負荷的變化更加敏感，因此可用c(e)的變化來評價算法對于鏈路擁塞狀態(tài)的控制能力。

c(e)=F(e)/r(e),r(e)=b(e)-F(e)

(4)

鏈路的權(quán)重系數(shù)用于描述其承載的流量負荷，鏈路e在重負荷區(qū)的權(quán)重系數(shù)w(e)定義如式(5)所示，鏈路承載的流量越少，權(quán)重值w(e)就越小。當鏈路處于空載時，權(quán)重值達到最小值0.01。相反，鏈路承載的流量越多時，權(quán)重值w(e)就越大，當鏈路帶寬被耗盡時w(e)=∞。所以，路徑P的權(quán)重如式(6)所示，路徑P的剩余帶寬如式(7)所示。需要注意的是，當在重負荷區(qū)路由時，如果鏈路的剩余帶寬小于所需帶寬，則該鏈路將被刪除。

w(e)=0.01+c(e)=0.01+F(e)+r(e)

(5)

(6)

r(P)=mine∈Pr(e)

(7)

所以，當衛(wèi)星在重負荷區(qū)進行路由時，將依據(jù)權(quán)重配置生成一個帶權(quán)值的網(wǎng)絡(luò)，可使用Dijkstra算法求解出權(quán)重值累計最小的路徑，以此來建立對應(yīng)的路由表項。注意，如果衛(wèi)星節(jié)點無法找到到達信關(guān)站的路徑，則節(jié)點承載的流量將會被路由算法拒絕。

綜上所述，基于區(qū)域劃分的流量均衡路由算法的主要執(zhí)行步驟如下：

1.根據(jù)“反向縫”與信關(guān)站的位置關(guān)系進行區(qū)域劃分;2.將重、輕負荷區(qū)域的節(jié)點集合分別記為(yn×ym)、(N-yn×ym);3.輕負荷區(qū)進行初始MST路由計算;4.記錄原始路徑集并生成預(yù)加權(quán)網(wǎng)絡(luò);5.根據(jù)預(yù)加權(quán)網(wǎng)絡(luò)來更新MST;6.記錄輕負荷區(qū)域的路徑集,并標記重負荷區(qū)邊緣節(jié)點;7.更新重負荷區(qū)邊緣節(jié)點承載的流量值;8.分配和存儲每個衛(wèi)星節(jié)點在重負荷區(qū)的優(yōu)先級,然后對重負荷區(qū)流量進行路由;for(i=0;i

2.2 復(fù)雜度分析

在包含v個網(wǎng)絡(luò)節(jié)點的拓撲中使用Dijkstra算法的時間復(fù)雜度是Q(v2)[11]。低軌衛(wèi)星網(wǎng)絡(luò)中如果存在N個衛(wèi)星節(jié)點，X個信關(guān)站以及一個中心站節(jié)點，重負荷區(qū)擁有yn×ym個節(jié)點，且N≥yn×ym。輕負荷區(qū)使用Dijkstra算法時的復(fù)雜度為O(N+X+12)=O(N2)，重負荷區(qū)的復(fù)雜度則為：O((yn×ym)×(yn×ym+X+1)2)=O(yn×ym)3，所以本算法的時間復(fù)雜度為O(N2+(yn×ym)3)。隨著重負荷區(qū)域面積An×m的擴大，算法的復(fù)雜度也會提高，反之則會降低。當輕負荷區(qū)域有N顆衛(wèi)星節(jié)點時，重負荷區(qū)域面積為0，此時復(fù)雜度降低到O(N2)。

3 算法驗證與性能評估

3.1 實驗設(shè)置

本實驗場景包含72個衛(wèi)星節(jié)點，均勻分布在6個軌道面上，小區(qū)的劃分如圖1所示。

圖1 流量小區(qū)劃分Fig.1 Traffic cells division

每個小區(qū)中的數(shù)值為參考流量密度[12]。實驗中設(shè)置了兩種流量密度的分布方式用于對比，流量密度均為1的均勻分布和依據(jù)圖1中預(yù)測得到的分布(預(yù)配置分布)。在均勻分布時，設(shè)置單位服務(wù)面積分別為U=1、2和3。在預(yù)配置分布時，考慮到很多人口稀疏的地區(qū)上行流量會很有限，網(wǎng)絡(luò)有足夠容量來滿足傳輸需求，因此設(shè)置為U=4和U=5。

流量負荷區(qū)域的劃分是該算法的關(guān)鍵步驟，為了分析重負荷區(qū)域面積的大小對該算法性能的影響，將重負荷區(qū)的面積進行適當?shù)目s放，考慮軌道面從3～6和每軌衛(wèi)星數(shù)2～6之間的所有可能區(qū)域(最大6×6)，并將全球面積(6×12)設(shè)置為對照組?？疾毂舅惴ㄔ诹髁棵芏葹榫鶆蚍植己皖A(yù)配置分布兩種情況下的性能。實驗使用的SR技術(shù)是一種基于源路由的轉(zhuǎn)發(fā)技術(shù)，它在計算路由時將流量路徑按照節(jié)點和鏈路的組合進行分段，并為每個段和轉(zhuǎn)發(fā)節(jié)點分配專屬的段標簽(SID)，將所有段和節(jié)點按順序排列成段列表，以形成完整的轉(zhuǎn)發(fā)路徑[13]。SR的特點是配置靈活且易于實現(xiàn)，適用于本算法的驗證。

3.2 實驗結(jié)果分析

為了客觀有效地評估本算法的性能，將使用以下4個指標來對實驗結(jié)果進行評估：

1)平均拒絕率

如果流量無法找到可達目的地址的轉(zhuǎn)發(fā)路徑，則本次傳輸請求將會被系統(tǒng)拒絕，平均拒絕率指的是被拒絕的總流量與系統(tǒng)總流量的比值，定義如式(8)，式(8)中R表示平均拒絕率，RS表示被拒絕的流量小區(qū)的集合。平均拒絕率越低表明算法的均衡能力越強。

(8)

在流量均勻分布情況下平均拒絕率的仿真結(jié)果如圖2(a)所示。小區(qū)面積在A6×12時，相比其他情況下的平均拒絕率達到最優(yōu)(接近于0%)。當U隨著相同面積的重負荷區(qū)增加時平均拒絕率也隨之增加。當重負荷區(qū)的軌道數(shù)相同時，平均拒絕率隨著每軌衛(wèi)星數(shù)量的增加而逐漸降低。當每軌衛(wèi)星數(shù)量相同時，拒絕率也會隨著軌道數(shù)的增加而降低。在預(yù)配置分布的情況下(如圖2(b)所示)，小區(qū)面積為A6×12時的拒絕率為0%，且隨著重負荷區(qū)面積的增大呈現(xiàn)出減少的趨勢，負載均衡的性能表現(xiàn)更好。

圖2 平均拒絕率Fig. 2 Average rejection ratio

2)平均相對吞吐量

平均相對吞吐量是成功傳輸流量的總和，定義如式(9)所示，T表示平均相對吞吐量，Ss是流量傳輸成功的小區(qū)的集合，相對吞吐量和拒絕率是一對互補的概念。相對吞吐量定量地反應(yīng)了成功傳輸?shù)牧髁?，與拒絕率成反比關(guān)系，平均相對吞吐量越大，算法的均衡能力就越強。

(9)

流量均勻分布時的平均相對吞吐量如圖3(a)所示，在全面積時取得最大值。當重負荷區(qū)中的軌道數(shù)相同時，平均相對吞吐量隨著每軌衛(wèi)星數(shù)量的增加而增加，當每軌衛(wèi)星數(shù)相同時，吞吐量也會隨著軌道數(shù)的增加而增加。在相同的U時，平均吞吐量隨著拒絕率的降低而增加。此外，當重負荷區(qū)面積相同時，U增加時吞吐量增加，同時拒絕率也隨之增加，但是與最優(yōu)吞吐量閾值的差異增加了，圖3(b)是流量預(yù)測分布時的仿真結(jié)果，變化趨勢與圖3(a)類似。

圖3 平均相對吞吐量Fig.3 Average relative throughput

3)最大鏈路利用率

最大鏈路利用率的定義如式(10)所示，F(xiàn)(e)是當前鏈路e上承載的流量，b(e)是鏈路e的帶寬，當拒絕率很低的時候，最大鏈路利用率會很重要。最大鏈路利用率低，負載均衡能力就越好。

(10)

圖4(a)表示流量均勻分布時，最大鏈路利用率的變化，區(qū)域面積A6×12時的最大鏈路利用率最低，并且提供了更低的閾值，當軌道數(shù)相同時，最大鏈路利用率會隨著每軌衛(wèi)星數(shù)量的增加而降低。當每軌衛(wèi)星數(shù)相同時，最大鏈路利用率隨著軌道數(shù)的增加而減少。最大鏈路利用率會隨著u的增加而增加。這個結(jié)果會更關(guān)注拒絕率低的小區(qū)面積，因為鏈路利用率超過100%將會導(dǎo)致傳輸被拒絕。圖4(b)顯示了在流量預(yù)測分布時的結(jié)果，重負荷區(qū)面積擴大時最大鏈路利用率會降低，然而，由于預(yù)測分布的極度不平衡，結(jié)果與較低閾值有差距。

圖4 最大鏈路利用率Fig.4 Maximum link utilization

4)平均延時

平均延時是所有傳輸成功的流量所產(chǎn)生延時的平均值，其反映了該算法的代價，定義如式(11)所示，|Ss|表示Ss中小區(qū)的具體個數(shù)，d(b)是流量f(b)所產(chǎn)生的延時，包括路由過程的處理延時和路徑傳播延時。平均延時越小，用戶的體驗也就越好。

(11)

在流量均勻分布的情況下，平均延時的仿真結(jié)果如圖5(a)所示，小區(qū)面積在A6×12時的結(jié)果作為參考閾值，當吞吐量增加時，延時和代價都會隨之增加，然而，在一些面積區(qū)域U值增加時，平均延時會減少。這種現(xiàn)象是因為拒絕率升高導(dǎo)致的，僅有小部分流量可以占用鏈路資源。當拒絕率很低時，隨著小區(qū)面積的擴大，平均延時也會增加。在預(yù)配置流量分布的情況下，仿真結(jié)果如圖5(b)所示，可以再次印證前面的觀點。

圖5 平均延時Fig.5 Average delay

實驗結(jié)果表明，隨著重負荷區(qū)面積的擴大，平均拒絕率隨之降低，平均相對吞吐量隨之提高，最大鏈路利用率也隨著減少，這些指標能夠直觀地體現(xiàn)本算法的性能。需要注意的是，小區(qū)面積的擴大指的是軌道數(shù)和每軌上的衛(wèi)星個數(shù)的同時增加，實驗表明僅在一個維度上增加，負載均衡的收益會很小。此外，平均延時也會隨著小區(qū)面積的擴展而增加，這將使代價和資源占用也隨之增加。本算法的時間復(fù)雜度為O(N2+(yn×ym)3)，顯然其隨著小區(qū)面積的擴大而顯著增加，因此，如果小區(qū)規(guī)模太大，相應(yīng)的延時和資源消耗也會很大，如果小區(qū)面積太小則很難避免網(wǎng)絡(luò)擁塞，所以重負荷區(qū)的面積是需要考慮的關(guān)鍵因素。

4 結(jié)語

本文針對低軌衛(wèi)星網(wǎng)絡(luò)中，由于信關(guān)站部署過于集中而導(dǎo)致下行鏈路擁塞的問題，提出了一種基于區(qū)域劃分的負載均衡路由算法，并使用SR技術(shù)進行了仿真驗證。本算法首先根據(jù)星座“反向縫”與信關(guān)站區(qū)域的位置關(guān)系對小區(qū)流量負荷的輕重進行劃分，使用預(yù)加權(quán)最小生成樹算法來計算輕負荷區(qū)域的路由，而重負荷區(qū)則采用基于擁塞系數(shù)的最小權(quán)重路由算法。重負荷區(qū)的總面積對算法性能的影響較大，仿真結(jié)果表明，隨著小區(qū)面積的增大，在延時增加不大的情況下，平均拒絕率，平均相對吞吐量，最大鏈路利用率等指標都有了顯著提高，表現(xiàn)出了良好的負載均衡能力，證明本算法能夠成為解決低軌衛(wèi)星網(wǎng)絡(luò)下行擁塞問題的有效方案。

致 謝

本研究工作受到湖北省軍民融合類重點研發(fā)計劃項目(項目號：2020BIB005)天基物聯(lián)網(wǎng)關(guān)鍵技術(shù)研究課題的資助。