基于鄰居衛星負載狀態的低軌衛星分布式路由算法

　　摘 要：衛星靈活性和機動性強、不易受地面因素的影響，使空間衛星技術不斷飛速發展。衛星網絡隨著負載的增加始終存在負載擁塞現象，使路由算法成為衛星網絡研究領域的核心問題。基于衛星網絡的擁塞緩解、網絡的信令開銷以及算法運算復雜度問題，深入研究低軌衛星網絡局部負載均衡的分布式路由算法。構建基于銥星系統的網絡模型，提出一種基于鄰居衛星負載狀態的分布式路由(DRNL)算法。DRNL 算法包含鄰居衛星負載狀態更新、負載均衡和路由判決等機制，具有一定的可移植性，能夠適應其他極軌或近極軌星座。OPNET 仿真結果表明，DRNL 算法在較重的網絡負載情況下能較好地適應負載的變化，緩解衛星擁塞的狀況并獲得較低的時延和數據分組丟失率。

　　楊明川; 薛冠昌; 李清毅， 通信學報 發表時間：2021-08-19

　　關鍵字：負載均衡;LEO;分布式路由;DRNL 算法

　　1 引言

　　隨著通信技術的進步、通信業務的增長和業務種類的增多，未來的通信網絡向著地面網絡和衛星網絡融合的方向發展，低軌衛星網絡在星地互聯網絡中扮演著重要的角色[1]。目前，移動通信系統已經發展到了 5G 時代，通信終端數量也發生了爆炸式的增長[2]。衛星通信成為地面移動通信系統和固定通信網絡的延伸，且由于低軌星座能夠實現全球通信的無縫覆蓋，其作用和戰略價值非常重要。

　　LEO(low earth orbit)衛星的傳輸損耗小，能夠支持小型移動終端之間的通信，便于實現終端小型化和多樣化，所以應用價值很高[3]。低軌衛星的運行軌道高度比較低，傳播延時比較短，通常在 10 ms 左右，能夠通過星間鏈路(ISL, inter satellite link)和相鄰衛星建立全雙工通信，實現對數據進行路由轉發。雖然星間鏈路的建立使得星座系統的設計復雜度增加，但不需要在全球范圍內建立大量的信關站，也降低了成本。

　　隨著業務量增加，星座網絡會出現擁塞現象。為緩解擁塞問題，Liu 等[4]提出 LEO 衛星網絡基于分段路由的負載均衡算法，動態劃分輕負載區和重負載區。輕載區采用預平衡最短路徑算法，重載區采用最小權重路徑算法。分段路由算法吞吐量、鏈路利用率和平均時延方面得到提高，但是采用分段路由算法造成星上存儲空間增加且算法復雜度較高。Feng等[5]提出緩解擁塞狀態的最小跳路由算法，根據衛星之間的經緯度信息計算出 2 條備選路徑，根據網絡負載情況判決出最優路徑。算法的信令開銷和運算復雜度較低，并在一定程度上緩解網絡擁塞現象，但路由表由固定節點計算，造成網絡的實時響應性差。

　　Geng 等[6]提出 LEO 衛星通信網絡的最優時延路由算法，對衛星網絡的時延變化進行表征，并選擇有效的候選路徑。算法得出路徑的時延及其變化的時延評估指標，以網絡中信令開銷增加為代價，實時響應網絡的擁塞情況。Wang 等[7]提出了基于擁塞預測的負載均衡路由算法，建立了多目標優化模型。采用修正因子來調整路徑成本，通過擁塞預測來預測衛星間鏈路的擁塞。利用蟻群算法求解該模型，從而為每個連接請求找到最佳路徑，運用神經網絡以更高的運算復雜度，實現衛星網絡的高效負載均衡。

　　當前衛星網絡面對擁塞緩解問題，路由算法往往以網絡中信令分組的增加為代價，獲取全網衛星的負載狀態信息，或者通過神經網絡等算法及時進行流量預測進行提前緩解，增加了運算的復雜度以及星上存儲空間。針對算法復雜度和信令開銷，基于小衛星星座的背景，算法設計考慮以較小的運算復雜度和信令開銷獲得時延和吞吐量性能的提升。

　　2 LEO 星座的建模

　　銥星(Iridium)系統由 66 顆 LEO 衛星交叉連接組成覆蓋全球范圍的復雜全網狀衛星網絡，數據在衛星之間進行路由而不經過地面。銥星無縫的語音和數據全球覆蓋，實現真正的移動通信，并且系統中衛星數量多，星間鏈路的互通能夠滿足未來物聯網信息的接入需求[8]。本文選用 Iridium 系統進行網絡建模，采用軟件 STK 11.2 進行衛星軌道的參數建模和 OPNET 14.5 進行衛星網絡路由算法的仿真分析。

　　Iridium 系統的衛星運行軌道均采用順時針方向。在 STK11.2 中進行衛星軌道建模時[9]，設置衛星的編號規則采用三位數字表示。衛星命名的第 10 位表示衛星的軌道編號，第 12 和 13 位表示衛星的軌內編號[10]。衛星進入南北極圈后關閉相鄰軌道間的鏈路(軌間鏈路)，極圈邊界緯度為 70°。每顆衛星包含一個單波束衛星天線，天線圓錐半角為 62°，即可實現全球無縫覆蓋。由于 Iridium 系統軌道 1 和軌道 6 相鄰，相鄰軌道的衛星運動方向相反(此區域稱為反向縫地區)，衛星節點之間相對運行速度很快，天線難以及時調整且通信時間比較短，故取消反向縫間衛星的軌間鏈路。Iridium 系統仿真參數如表 1 所示，3D 建模如圖 1 所示。

　　從星座的 3D 建模圖可以看出，Iridium 實現了全球無縫覆蓋。設置地面衛星的通信仰角為 5°，隨機選取北京市測量任意時刻可接入衛星的數量，仿真結果如圖 2 所示。

　　在任意時刻地面終端可選接入衛星數量始終大于或等于 1，這意味著地面終端可以采取最長接入時間覆蓋、最大地面仰角、最大接入信號功率等多種星地鏈路的選擇方案。

　　3 DRNL 路由算法

　　考慮衛星網絡中較低的信令開銷以及算法的運算復雜度，基于衛星網絡的擁塞緩解問題，本文提出一種基于鄰居衛星負載狀態的分布式路由算法(DRNL, distributed routing algorithm based on the load status of neighbor satellite)，充分考慮了衛星移動的規律性，將星座網絡中的每顆衛星看成虛擬節點[11-12]。衛星采用雙向通信，通過無線收發信機實現數據發送和接收[13]。該路由算法采用虛擬節點的思想，將地球表面劃分為 66 個邏輯區域，距離邏輯區域中心最近的衛星加載其邏輯地址。每顆衛星節點能夠獨立進行分布式的路由決策，且衛星的軌道采用近極軌道，軌道傾角為 87°，根據虛擬節點的思想該策略能夠簡化衛星之間的相對運動問題，可適用于其他近極軌道星座[14]。

　　通過衛星網絡的拓撲結構可知，衛星不通過極區時，非反向縫兩側的衛星時存在 4 條星間鏈路，且每對衛星節點之間包括發送和接收鏈路 2 個方向，如圖 3 所示。

　　DRNL 路由算法中每顆衛星獨立的進行路由選擇，當前衛星節點在星座中的編號為< ks , ls >，目的衛星節點在星座中的編號為< kd , ld >，其中 k 代表軌道編號，l 代表軌內編號。通過衛星之間命名的關系(相對位置)，判斷出可選路由下一跳衛星節點，數據分組的可選節點路由策略如圖 4 所示。其中 d s ? ? ? k k k ， d s ? ? ? l l l ，圖中指向箭頭表示可選節點路由的方向。

　　數據分組到達衛星節點時，根據分組域中的目的地址和當前節點的編號采用 DRNL 算法獲取可選下一節點。如果當前節點與可選節點的星間鏈路處于連接狀態，則依據負載判決機制選擇合適的下一節點。如果與可選下一節點的軌間鏈路斷開，則依據迂回路由算法選擇其余的待選路徑。待選路徑的衛星一般為當前衛星節點軌道面內的上、下兩顆衛星，依據鄰居衛星的緯度和負載狀態選擇合適的下一跳進行路由轉發。

　　衛星節點間的鏈路負載情況[10]的計算如式(1) 所示。

　　其中， b1 q 為緩存隊列長度， Qb1 為緩存隊列容量， B1 q 到 B4 q 為節點 B 的 4 條星間鏈路的緩存隊列利用率， Bq 為鄰居節點 B 的綜合負載情況， ab q 為當前節點 A 對應相鄰節點 B 的緩存隊列的利用率， AB q 為綜合判決下一跳衛星的鏈路利用率信息。

　　鏈路負載狀況采用三級負載判決形式，代表 3 種等級狀態，如式(2)所示。等級越高說明鏈路越繁忙，則減少到擁塞鏈路的流量，起到均衡局部負載的作用。

　　狀態信令包含綜合判決下一跳衛星的鏈路利用率信息以及負載等級信息。初始時刻，衛星每間隔 1 s 更新一次本地負載信息，如果當前時刻和上一時刻的狀態相同，則每間隔 2 s 發送當前衛星的狀態信令給鄰居衛星。如果狀態不同，則每間隔 1 s 發送狀態信令。相鄰衛星接收到狀態信令數據后，更新存儲的網絡負載信息表，從而調整選擇下一跳衛星的路由策略。

　　衛星節點定期監測周圍衛星狀態信息，當網絡出現負載不均衡或者是鏈路斷開的情況時，衛星應該及時解決緩解擁塞和鏈路通斷時的路由問題。狀態信令含有衛星的緯度和負載信息，緯度信息用于判斷相鄰衛星是否進入極區。衛星在經過極區時關閉軌間鏈路，衛星拓撲如圖 5 所示。

　　路由轉發利用當前和目的衛星的經緯度信息，根據改進的最小跳路由算法計算下一跳衛星。當前節點 C loc lac ? , ?，其中 loc 和 lac 分別為當前衛星的經度和緯度，目的衛星節點記為 D lod lad ? , ?，其中 lod 和 lad 分別為目的衛星的經度和緯度[5]。

　　當前衛星和目的衛星之間的緯度關系滿足式(3) 時，可選路徑的方向向上。 0 90 180 90 lad lac lad lac ? ?? ? ? ? ≤ ≤ (3) 緯度關系滿足式(4)時，可選路徑的方向向下。

　　當前衛星與目的衛星之間的經緯度的關系總滿足上述 4 個條件中的 2 個，即該算法存在 2 個方向的可選下一跳衛星。在數據分組域用設置過極區標識，如果經過極區，則將其置 1，反之置 0。此時由于極區上空的衛星關閉軌間鏈路，如果數據分組路由到達極區，但目的衛星不在極區，則需保持進入極區的路由方向直至離開極區，然后通過星間鏈路到達目的衛星節點，防止根據最小跳算法在極區發送到軌間鏈路上造成數據分組丟失。

　　衛星發生擁塞現象時，隊列中緩存的數據分組將會增加從而造成排隊時延的增加。此時，根據衛星負載狀態更新策略檢測出擁塞等級。相鄰衛星接收到狀態信令后，將減少數據分組發往擁塞節點。當衛星節點 A 具有 2 個可選下一跳衛星 B 和 C 時，此時采用負載判決機制，根據可選衛星的擁塞等級進行判斷。當 L L B C = 時，則下一跳衛星按比例 0.5 隨機選擇。如果 L L B C ?，當 =1 L L B C ? 時，下一跳衛星按比例 0.7 選擇負載等級低的衛星，按比例 0.3 選擇負載等級高的衛星。當 =2 L L B C ? 時，下一跳衛星按比例 0.85 選擇負載等級低的衛星，按比例 0.15 選擇負載等級高的衛星。如果當前衛星與目的衛星在同一軌道面或具有相同軌內編號時，采取改進的最小跳算法為緩解擁塞可能會路由數據分組到非最小跳數的路徑方向，造成路由的跳數增加。

　　當源衛星節點為 104、目的衛星節點為 306 時，如圖 5 所示，源節點首先判斷與 204 之間的鏈路是否連接。如果鏈路斷開，選擇節點 105 作為下一跳衛星。反之，如果鏈路連接，則根據節點 105 和 204 的負載情況選擇下一跳衛星。如果選擇節點 105，則給數據分組設置極區標志，表示其經過極區的方向。然后當前衛星再根據極區標志判斷下一跳衛星是 106，此時和目的節點在同一水平環內，途徑衛星 206 轉發數據分組到目的節點。如果選擇 204，由于與 304 的軌間鏈路關閉，只能選擇到下一跳衛星 205，同理途經 206 到達目的節點。

　　4 OPNET 建模

　　4.1 星座負載建模

　　由于考慮到極地區域業務負載比較少，衛星在極區關閉軌間鏈路的情況下，對極地地區和非極地地區的業務分布進行單獨建模。星座中總共包含 66 顆衛星，對應將地球表面劃分為 66 個服務區域，每個區域對應一顆 LEO 衛星承擔區域中的通信業務。在衛星節點建模的過程中使用模擬數據源，用以模擬衛星在實際過程中接收到的地面終端發送的數據分組[15]。考慮極地地區和非極地地區業務負載不均衡，將星座中信元生成負載情況按照衛星在運行中所處的緯度進行更新。

　　衛星網絡中模擬業務源的數據產生速率為 0 10.24 W W kbps? ?。其中，W 為不同衛星產生模擬通信業務的權重大小，W0 為全網衛星設置的初始權重大小，權重分布如表 2 所示。

　　4.2 網絡層建模

　　OPNET 是商業化仿真軟件，其中產品 Modeler 能夠對多種業務進行模擬，繪制仿真圖和輸出仿真報告。在仿真的過程中能夠收集統計量數據、查看網絡運行的動畫和調試程序。Modeler 在仿真時維護一個全局事件列表，在仿真運行的時刻執行排在當前列表最前面的事件，將基于數據分組的統計方法結合基于數學統計的建模方法[16]。

　　Iridium 星座的網絡層如圖 6 所示，主要建模星座的拓撲結構，是實現仿真分析 LEO 路由算法的基礎。在 OPNET 網絡層導入修改后的 STK 生成的軌道文件，每條軌道對應生成一個衛星節點，圖中包含 66 顆衛星節點和一個接收主詢配置。接收主詢模塊通過基于衛星的經緯度、鏈路可視性以及依據衰落現象判斷數據分組是否可達、通斷星間鏈路，控制衛星之間數據分組的路由轉發經過鏈路的連接情況。

　　4.3 節點層建模

　　星座中衛星的節點層模型如圖 7 所示，用于模擬衛星節點實現的通信功能，是實現路由算法的硬件條件。天線的指向通過 ant_point 模塊進行周期調整，數據分組的接收和發送都是通過無線收發信機模塊來實現，每個無線收發信機對應一條 ISL 星間鏈路。其中，虛線為狀態連接線，傳輸隊列模塊的存儲信息。

　　圖7中的app_gen模塊用于模擬業務源的產生;

　　sink 模塊統計數據分組的傳輸時延等統計量，銷毀數 據 分 組 釋 放 仿 真 運 行 占 用 的 內 存 空 間 ; LEO_route 模塊進行數據分組的下一節點的選擇。由于衛星路由考慮星間鏈路，每顆衛星節點需要有 4 條星間鏈路，所以節點層需要 4 對無線鏈路收發信機。

　　無線信號在仿真過程中需要配置 14 個管道階段，包括調制方式、噪聲系數、接收增益、背景噪聲、信噪比、比特誤碼率等模擬真實無線信號傳輸的環境。模擬信號產生后通過分組流連接線傳輸到路由模塊，選擇合適的下一跳衛星節點，傳輸到對應鏈路的緩存隊列 queue 模塊，然后經由收發信機進行發送。

　　4.4 進程層建模

　　節點域模塊中每個模塊都有不同的進程層模型，進程層是通過有限狀態機模型進行建模，每個狀態機對應進程模型的一個狀態，通過狀態連接線實現狀態的轉移。在進程層中狀態分為強制性和非強制性狀態，強制性狀態是綠色標識，非強制性狀態是紅色標識[10]。當進程執行強制性狀態時，直接狀態執行入口代和出口代碼，然后跳入其他狀態或終止。當進程執行非強制性狀態時，先執行狀態的入口代碼，然后將控制器交給仿真核心，等待其他進程或者事件的觸發返回執行出口代碼。

　　1) ant_point 模塊

　　由于衛星在不停的運行過程中，衛星之間的位置會發生改變，因此需要天線校準模塊及時的跟蹤鄰居衛星節點的位置，其狀態轉移如圖 8 所示。

　　圖 8 中 point 模塊是獲取相鄰衛星的位置參數進行天線校準的狀態。首先獲取周圍相鄰的衛星節點的 ID，依次獲取其經度、緯度和高度信息，然后賦值給天線的指向參數。天線指向跟蹤的調整時間

　　間隔為 1 s，通過設置天線模塊提高發射增益，減少數據路由的誤碼率和數據分組丟失率。

　　2) LEO_route 模塊

　　數據分組的路由需要LEO_route模塊選擇合適的下一跳，路由模塊內的有限狀態機模型如圖 9 所示。

　　STATE 狀態為當前衛星節點進行檢測自身的 4 條鏈路的緩存情況，并劃分相應的擁塞等級。 SEND_HELLO 狀態為當前節點發送的信令分組，將 STATE 狀態統計的衛星節點的緩存數據和緯度信息存入信令分組。

　　RCV_LOCAL 狀態為接收到本節點產生的模擬數據分組后執行的操作。RCV_NEIGH 狀態首先判斷接收到的數據是信令分組或數據分組，如果為數據分組判斷其目的地址，判決是執行銷毀還是路由轉發。

　　5 仿真結果與性能分析

　　在研究過程中，改變網絡中模擬數據分組的產生速率，與典型的最小跳路由算法進行比較，通過對數據分組的端到端時延、數據分組丟失率、平均路由跳數指標，判斷星座網絡的擁塞處理能力[17]。

　　5.1 路由性能指標

　　1)平均端到端時延

　　平均端到端時延為星座網絡中數據分組在模擬信源中產生的時刻開始，到通過路由轉發到達目的衛星節點時刻的間隔求平均值。

　　其中， T?vg 為數據發送到接收的平均時延值， N 為接收到的數據分組的數量，Ti 為在星座中傳輸的單個數據分組的端到端時延。

　　2)數據分組丟失率

　　數據分組在星座網絡傳輸的過程中遇到緩存溢出、誤判決和路徑損耗等發生數據分組丟失的現象，丟失的數據分組數量與網絡中傳輸的數據分組的總數的比值。

　　其中， Nloss 為在傳輸過程中丟失的數據分組的總數， Nsend 為網絡中發送的數據分組的總數， Rloss 為數據分組丟失率。

　　3)平均路由跳數

　　在路由過程中，所有數據分組到達目的節點經過的跳數的平均值稱為平均路由跳數。 1 vg N i i H H N ?? ?? (9) 其中， H?vg 為平均路由跳數， N 為接收到的數據分組的數量，Hi 為網絡中單個數據分組的路由跳數。

　　5.2 OPNET 仿真參數設置

　　本文采用 BPSK 進行數據編碼且衛星天線的校準周期設置為 1 s，本文仿真參數設置如表 3 所示。

　　5.3 DRNL 算法仿真與分析

　　本文采用的比較路由性能的2種算法為文獻[5] 提出的最小跳路由算法及其改進型，均為分布式路由算法。

　　1) 固定路徑的分布式最小跳路由算法(FPRA， fixed path routing algorithm)

　　衛星節點在路由決策時不考慮負載狀況，當數據分組到達時，按照當前衛星和目的衛星的經緯度位置依據最小跳算法采用固定方向的策略選擇下一跳節點進行路由。

　　2) 隨機選擇路徑的分布式最小跳路由算法(RSRA, random select routing algorithm)

　　衛星節點不考慮負載狀況，當數據分組到達時，衛星按照最小跳路由算法計算的 2 條備選方向隨機選擇作為下一跳衛星節點轉發數據分組，能夠避免衛星網絡在一些鏈路上傳輸引起擁塞，從而增強網絡的路由能力。

　　5.4 仿真結果

　　1) 平均端到端時延

　　數據分組產生時間間隔減小，衛星節點的負載越重，所以端到端時延成向上增長的趨勢。仿真結果如圖 10 所示。

　　分組產生間隔在 0.14~0.08 s 時，3 種路由算法為相對空閑狀態，端到端時延在 0.167 s 左右。分組產生間隔為 0.08~0.04 s 時，3 種路由算法為相對繁忙狀態，DRNL 路由算法依然保持穩定的路由能力，端到端時延保持在 0.2 s 以下。分組產生間隔為 0.03 s 時，網絡達到擁塞狀態，3 種算法端到端延時大幅度上升，但 DRNL 算法時延維持在 0.538 s。仿真結果表明，DRNL 算法具有緩解網絡擁塞、降低時延的能力。

　　2)數據分組丟失率

　　仿真結果表明，隨著網絡負載加重，數據分組丟失率與端到端時延均增加，如圖 11 所示。當分組產生間隔為 0.03 s 時，3 種路由算法的數據分組丟失率均顯著上升，這是由于網絡的擁塞現象加重，部分節點的緩存隊列出現溢出、數據分組同時到達收發信機引起沖突造成數據分組丟失，但是 DRNL 算法的數據分組丟失率維持在 0.09 左右，保持較好的性能。

　　3)平均路由跳數

　　數據分組路由的跳數增加會造成時延增大，需要考慮衛星在自由空間的傳播時延。同軌道面內衛星均勻分布，星間距離保持固定，即軌道內相鄰衛星之間通信具有固定的時延，如式(10)所示。其中，R 是軌道面的半徑，M 是軌道面內衛星數， c 是電磁波傳播速度。

　　軌道間衛星之間的距離隨著衛星的相對運動不斷發生變化。在赤道附近緯度較低，衛星的分布比較稀疏，傳輸時延最大，計算式為 1 cos( ) c 360 2 1 cos 2 t lat R N ???? ? ?? ?? ? ? ? ? ? ?間(11)其中，N 是軌道面的數量，lat 是衛星的緯度。

　　3 種算法平均路由跳數的仿真結果如圖 12 所示。當分組產生間隔大于 0.07 s 時，網絡相對空閑， FPRA 和 RSRA 算法的路由跳數基本保持不變; DRNL 算法的平均路由跳數最小，使平均端到端延時最小。當分組產生間隔小于 0.04 s 時，FPRA 和 RSRA 算法平均路由跳數下降，但由圖 10 可知，端到端時延仍呈上升趨勢。

　　端到端時延需考慮排隊時延和傳播時延，此時平均路由跳數減少，傳播時延降低，但是排隊時延增加。這是因為數據分組丟失率的增加導致數據分組不能到達目的地，在路由過程中丟失。由于 DRNL 算法中數據分組采用迂回路由轉發具有局部擁塞緩解的功能，此時數據分組丟失率依舊很低，但是隨著網絡負載增加，DRNL 平均路由跳數逐漸增加。

　　DRNL 路由算法考慮相鄰衛星的負載狀態，衛星采用分布式思想，使每顆衛星能夠獨立進行負載均衡路由判決，實時響應衛星網絡中負載的變化以及鏈路的通斷問題。以相對較低運算復雜度換取端到端時延和數據分組丟失率的降低，但是以網絡中相對較低的信令開銷為代價，使星座具有一定的抗毀性。

　　6 結束語

　　當前世界掀起新一輪衛星網絡建設風潮，建設低軌衛星網絡成為關系國計民生的重大戰略性工程。路由算法是衛星網絡的核心技術，本文提出的 DRNL 路由算法能夠通過較低的信令開銷獲取緩解網絡擁塞的能力，滿足一定的實時性要求。DRNL 算法通過信令分組及時獲取鄰居衛星節點的負載狀態和鏈路的連接情況，提升了網絡的穩健性，能夠滿足我國對低軌衛星網絡通信系統的發展需要。