低軌衛(wèi)星網(wǎng)絡(luò)的航點(diǎn)分段路由及業(yè)務(wù)性能分析

趙鑫，趙光，陳睿，王文鼐, 2

低軌衛(wèi)星網(wǎng)絡(luò)的航點(diǎn)分段路由及業(yè)務(wù)性能分析

趙鑫1，趙光1，陳睿1，王文鼐1, 2

（1.南京郵電大學(xué)通信與信息工程學(xué)院，江蘇 南京 210003；2.寬帶無線通信與傳感網(wǎng)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003）

提出一種基于衛(wèi)星航點(diǎn)的分段路由（waypoint-segment routing，WSR）算法，WSR算法以可預(yù)測(cè)的衛(wèi)星網(wǎng)絡(luò)拓?fù)溥\(yùn)動(dòng)周期為基礎(chǔ)，根據(jù)衛(wèi)星節(jié)點(diǎn)鏈路狀態(tài)確定衛(wèi)星航點(diǎn)的位置；利用分段路由靈活規(guī)劃分組傳輸路徑的機(jī)制，提前響應(yīng)網(wǎng)絡(luò)拓?fù)渥兓?jì)算得到一條不受網(wǎng)絡(luò)拓?fù)淇煺涨袚Q影響的傳輸路徑。基于NS-3仿真平臺(tái)進(jìn)行仿真實(shí)驗(yàn)，設(shè)置源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)在反向縫同側(cè)與不同側(cè)兩種場(chǎng)景，選取優(yōu)化鏈路狀態(tài)路由（optimized link state routing，OLSR）算法和最短路徑算法與WSR進(jìn)行時(shí)延抖動(dòng)與分組丟失率的對(duì)比分析。實(shí)驗(yàn)證明WSR與OLSR相比，兩種場(chǎng)景下最大時(shí)延抖動(dòng)分別降低46 ms與126 ms，分組丟失率分別降低30%和21%，并且能夠解決拓?fù)淇煺涨袚Q導(dǎo)致分組傳輸路徑中斷的問題。

低軌衛(wèi)星網(wǎng)絡(luò)；虛擬拓?fù)洌粯O區(qū)星間鏈路；衛(wèi)星航點(diǎn)路由；性能仿真

0 引言

衛(wèi)星通信系統(tǒng)近年來得到廣泛的關(guān)注與迅速的發(fā)展，其中低地球軌道（low earth orbit，LEO，以下簡(jiǎn)稱低軌）衛(wèi)星通信系統(tǒng)憑借信號(hào)發(fā)射功率小、發(fā)射成本低以及傳輸時(shí)延低等優(yōu)點(diǎn)[1-2]，成為全球通信領(lǐng)域的研究熱點(diǎn)之一。此外，一些業(yè)內(nèi)專家認(rèn)為，在6G通信系統(tǒng)中，為了提供全球覆蓋應(yīng)當(dāng)引入衛(wèi)星通信，以實(shí)現(xiàn)天地空一體化[3-5]。

從Globalstar系統(tǒng)的48顆衛(wèi)星，到如今Starlink系統(tǒng)計(jì)劃的數(shù)萬顆衛(wèi)星，為全球用戶提供網(wǎng)絡(luò)接入服務(wù)，LEO衛(wèi)星得到快速的發(fā)展[6]。現(xiàn)代巨型星座衛(wèi)星使用更先進(jìn)的調(diào)制技術(shù)、多波束天線和復(fù)雜的頻率復(fù)用技術(shù)，降低了制造與發(fā)射成本[7]。同時(shí)，星座結(jié)構(gòu)更加多樣化[8-9]，星間拓?fù)涞淖儎?dòng)周期更短[10]。

由于地面網(wǎng)絡(luò)的路由協(xié)議無法直接應(yīng)用到LEO衛(wèi)星通信系統(tǒng)上，故為不斷演變的動(dòng)態(tài)衛(wèi)星網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)一種有效的路由方法成為當(dāng)下的熱點(diǎn)研究問題。傳統(tǒng)的Dijkstra算法通過遍歷拓?fù)渲泄?jié)點(diǎn)的權(quán)值來計(jì)算得到最短路徑，即從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的分組傳輸時(shí)延最小，但是LEO衛(wèi)星網(wǎng)絡(luò)是一種對(duì)稱網(wǎng)絡(luò)拓?fù)洌@將導(dǎo)致來自同一節(jié)點(diǎn)的多條最短路徑可能包含同一條鏈路[11]，這對(duì)動(dòng)態(tài)變化LEO網(wǎng)絡(luò)拓?fù)涫遣焕摹Ｈ欢鴳?yīng)用于MANET的優(yōu)化鏈路狀態(tài)路由（optimized link state routing，OLSR）算法能夠根據(jù)網(wǎng)絡(luò)拓?fù)渥兓龀隹焖俚膽?yīng)對(duì)，文獻(xiàn)[12]的研究結(jié)果表明，OLSR協(xié)議應(yīng)用于LEO衛(wèi)星網(wǎng)絡(luò)中可以有效降低分組傳輸?shù)目倳r(shí)延，且OLSR協(xié)議適用于極地衛(wèi)星任務(wù)。文獻(xiàn)[13]在OLSR協(xié)議的基礎(chǔ)上，根據(jù)LEO衛(wèi)星網(wǎng)絡(luò)運(yùn)動(dòng)周期計(jì)算出的每條鏈路狀態(tài)，得到更加穩(wěn)定的傳輸路徑，使得分組丟失率得到顯著的改善。文獻(xiàn)[14]提出應(yīng)用于衛(wèi)星與地面網(wǎng)絡(luò)結(jié)合場(chǎng)景的OLSR優(yōu)化算法，并做出性能評(píng)估。目前，虛擬拓?fù)洌╲irtual topology，VT）技術(shù)成為處理動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)涞年P(guān)鍵技術(shù)之一[15]，VT模型依據(jù)衛(wèi)星運(yùn)動(dòng)的周期性，將一個(gè)時(shí)間連續(xù)的動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)涑橄髣澐殖扇舾蓮堨o止的網(wǎng)絡(luò)拓?fù)鋱D，每一張靜止的拓?fù)鋱D被稱為一張快照[16]，故可以離線計(jì)算衛(wèi)星網(wǎng)絡(luò)的路由，這降低了對(duì)衛(wèi)星的存儲(chǔ)空間與計(jì)算能力的要求[17]。基于VT網(wǎng)絡(luò)模型技術(shù)，文獻(xiàn)[18]對(duì)分布式星間路由算法做出研究，未考慮擁塞避免的分布式路由算法造成網(wǎng)絡(luò)擁塞，將導(dǎo)致分組丟失率上升，然而集中式路由算法相對(duì)于分布式路由算法收斂速度更快[19]，集中式的分段路由（segment routing，SR）允許源節(jié)點(diǎn)將一條或多條指令加在分組的頭部，這些指令引導(dǎo)分組沿著一個(gè)特定的路徑進(jìn)行傳輸，即一條通向某個(gè)目的節(jié)點(diǎn)的路徑通過在中間添加航點(diǎn)而被分割成若干段[20]，與傳統(tǒng)的網(wǎng)絡(luò)架構(gòu)相比，SR更具有靈活性、可擴(kuò)展性[21]，這更加有利于解決動(dòng)態(tài)LEO網(wǎng)絡(luò)的路由問題。

另外，星載硬件設(shè)備小型化和計(jì)算能力的增強(qiáng)，推動(dòng)了LEO衛(wèi)星的發(fā)展。Starlink、OneWeb和Telesat等已在衛(wèi)星中部署小型硬件設(shè)備，其端到端傳輸時(shí)延及可靠性的需求，成為現(xiàn)代巨型星座技術(shù)的核心問題之一[22]。分組在傳輸過程中發(fā)生網(wǎng)絡(luò)拓?fù)淇煺涨袚Q導(dǎo)致分組傳輸路徑斷開，會(huì)造成路由重計(jì)算，即分組在該中間節(jié)點(diǎn)將會(huì)有短暫的等待時(shí)間，繼而總時(shí)延增加，這對(duì)通信質(zhì)量造成了嚴(yán)重的影響，而拓?fù)淇煺涨袚Q后，同時(shí)路由收斂完成，傳輸時(shí)延會(huì)恢復(fù)正常。因此，網(wǎng)絡(luò)拓?fù)淇煺涨袚Q前后時(shí)間段內(nèi)會(huì)出現(xiàn)嚴(yán)重的抖動(dòng)現(xiàn)象，而先驗(yàn)式路由協(xié)議OLSR與目的節(jié)點(diǎn)序列距離矢量協(xié)議都具有較好的魯棒性，因此能夠適應(yīng)具有抖動(dòng)特性的LEO衛(wèi)星網(wǎng)絡(luò)[23]，但不能完全解決該問題，且目前LEO衛(wèi)星數(shù)量急劇增加使得拓?fù)淇煺諗?shù)量急劇增加[24]，故高頻率的拓?fù)淇煺涨袚Q導(dǎo)致時(shí)延抖動(dòng)更加頻繁。

本文提出一種基于衛(wèi)星航點(diǎn)的分段路由（waypoint-segment routing，WSR）算法用于解決衛(wèi)星網(wǎng)絡(luò)拓?fù)淇煺涨袚Q前后路由中斷問題，并進(jìn)一步改善時(shí)延抖動(dòng)問題。仿真實(shí)驗(yàn)選擇OLSR算法、Dijkstra算法與WSR進(jìn)行性能對(duì)比，選取分組丟失率來分析拓?fù)淇煺涨袚Q前后是否出現(xiàn)傳輸路徑中斷的問題，并且為了進(jìn)一步觀察時(shí)延抖動(dòng)改善程度，選擇分組端到端時(shí)延作為性能評(píng)價(jià)指標(biāo)。

1 低軌衛(wèi)星網(wǎng)絡(luò)路由中斷問題

1.1 星間鏈路特征

LEO衛(wèi)星網(wǎng)絡(luò)拓?fù)淙鐖D1所示，空心圓點(diǎn)代表衛(wèi)星，衛(wèi)星在軌道上向極區(qū)方向運(yùn)動(dòng)。每顆衛(wèi)星與前后左右的4顆衛(wèi)星通過星間鏈路（inter satellite link，ISL）[25]連接，同一軌道內(nèi)的鏈路稱為軌內(nèi)星間鏈路，相鄰軌道間的鏈路稱為軌間星間鏈路。

LEO衛(wèi)星運(yùn)動(dòng)過程中，軌內(nèi)ISL始終保持連接狀態(tài)，軌間ISL卻會(huì)出現(xiàn)斷開與恢復(fù)的現(xiàn)象。相鄰軌道的兩顆運(yùn)動(dòng)方向相同的衛(wèi)星在向極區(qū)方向運(yùn)動(dòng)時(shí)，兩顆衛(wèi)星之間的距離不斷縮小[26]，因?yàn)镮SL通過衛(wèi)星天線的不斷轉(zhuǎn)動(dòng)調(diào)整來保持連接狀態(tài)，故為了適應(yīng)兩顆衛(wèi)星之間不斷縮小的距離，衛(wèi)星天線的旋轉(zhuǎn)角速度將會(huì)隨之增大。但因?yàn)樘炀€無法承受過大的角速度，因此衛(wèi)星天線旋轉(zhuǎn)角速度達(dá)到某一閾值，即衛(wèi)星進(jìn)入極圈時(shí)會(huì)關(guān)閉軌間ISL，與相鄰軌道衛(wèi)星斷開連接，在出極區(qū)時(shí)恢復(fù)連接。圖1中衛(wèi)星S1與S2、S2與S3之間的虛線代表衛(wèi)星即將通過極圈而將要關(guān)閉的軌間ISL，稱為極區(qū)ISL。LEO衛(wèi)星網(wǎng)絡(luò)拓?fù)渲邢噜徿壍郎闲l(wèi)星反向運(yùn)動(dòng)時(shí)，兩軌道間的區(qū)域稱為反向縫，圖1中反向縫兩側(cè)上的衛(wèi)星高速相對(duì)運(yùn)動(dòng)，故反向縫兩側(cè)上的衛(wèi)星之間無法建立ISL[27]。

圖1 LEO衛(wèi)星網(wǎng)絡(luò)拓?fù)?/p>

1.2 星間路由中斷問題分析

分組在ISL上傳輸過程中發(fā)生網(wǎng)絡(luò)拓?fù)淇煺涨袚Q，會(huì)導(dǎo)致路由中斷。0時(shí)刻與0+時(shí)刻的網(wǎng)絡(luò)拓?fù)淇煺諏?duì)比如圖2所示，源節(jié)點(diǎn)S 向目標(biāo)節(jié)點(diǎn)D沿著箭頭線所指的兩條傳輸路徑傳輸分組。其中，下一個(gè)為next，繼續(xù)為continue，壓入為push。源節(jié)點(diǎn)S到目標(biāo)節(jié)點(diǎn)D的傳輸路徑見表1，路徑1因?yàn)榇嬖?-3與3-D極區(qū)ISL，在發(fā)生拓?fù)淇煺涨袚Q后，該路徑發(fā)生中斷。即圖2中，0+時(shí)刻網(wǎng)絡(luò)拓?fù)淇煺罩械膬蓷l鏈路e1與e2斷開，而路徑2則在拓?fù)淇煺涨袚Q后未受影響。故可以認(rèn)為一次通信過程中某個(gè)時(shí)間點(diǎn)發(fā)生網(wǎng)絡(luò)拓?fù)淇煺涨袚Q，若此次通信的分組傳輸路徑包含極區(qū)ISL，則必將發(fā)生路由中斷，導(dǎo)致路由重計(jì)算，增加某一分組的總時(shí)延，造成抖動(dòng)問題。

圖2 t0時(shí)刻與t0+T時(shí)刻的網(wǎng)絡(luò)拓?fù)淇煺諏?duì)比

表1 源節(jié)點(diǎn)S到目標(biāo)節(jié)點(diǎn)D的傳輸路徑

2 WSR算法描述

文獻(xiàn)[20]指出SR算法是基于松散源路由的概念，分組頭部加入的單條指令被稱為段指令（segment），多條有序的指令序列稱為segment列表，每個(gè)segment可以執(zhí)行一個(gè)拓?fù)湫枨螅缑罘纸M傳輸路徑必須包含某一個(gè)具體的節(jié)點(diǎn)。現(xiàn)行的多協(xié)議標(biāo)簽交換（MPLS）技術(shù)，通過標(biāo)簽分配協(xié)議（LDP）在所有中間節(jié)點(diǎn)完成分組標(biāo)記和轉(zhuǎn)發(fā)控制，并結(jié)合流量工程擴(kuò)展的資源預(yù)留（RSVP-TE）協(xié)議實(shí)現(xiàn)網(wǎng)絡(luò)資源分配和業(yè)務(wù)質(zhì)量保障。相比而言，SR僅需在SR域中的入口節(jié)點(diǎn)保持逐流（per-flow）狀態(tài)并對(duì)傳輸路徑上的節(jié)點(diǎn)編號(hào)Node-SID與鏈路編號(hào)Adj-SID操作即可，而其他SR路由器根據(jù)SID轉(zhuǎn)發(fā)分組，無須了解數(shù)據(jù)包的其他信息[28]。SR操作功能描述見表2。

表2 SR操作功能描述

文獻(xiàn)[26]指出，現(xiàn)代LEO衛(wèi)星通信的星座規(guī)模變大，衛(wèi)星不僅需要完成中繼轉(zhuǎn)發(fā)，還需要具有路由計(jì)算能力。除此之外，LEO衛(wèi)星網(wǎng)絡(luò)拓?fù)渥兓哂泄潭ǖ闹芷冢虼丝梢杂?jì)算出所有LEO衛(wèi)星在任何時(shí)刻的具體位置，即可以計(jì)算出任意一條ISL變成極區(qū)ISL的時(shí)刻。WSR算法在LEO衛(wèi)星網(wǎng)絡(luò)路由計(jì)算中使用SR算法機(jī)制，分組傳輸過程中，傳輸路徑中的某條或某幾條ISL變成極區(qū)ISL，為了避免在拓?fù)淇煺涨袚Q后出現(xiàn)路由中斷，可在節(jié)點(diǎn)中push相應(yīng)的segment，從而規(guī)避極區(qū)ISL，以維持正常業(yè)務(wù)流傳輸。圖2中，源節(jié)點(diǎn)S根據(jù)0時(shí)刻網(wǎng)絡(luò)拓?fù)湫畔ⅲ卸窂?包含e1、e2兩條極區(qū)ISL，便執(zhí)行push操作，即將節(jié)點(diǎn)A與目標(biāo)節(jié)點(diǎn)D的Node-SID插入分組頭部。分組到達(dá)節(jié)點(diǎn)4被執(zhí)行continue，即節(jié)點(diǎn)4不處理當(dāng)前segment列表。到達(dá)節(jié)點(diǎn)A后，執(zhí)行next操作，即指針指向下一條segment，代表當(dāng)前segment完成并向目標(biāo)節(jié)點(diǎn)D傳輸分組。由此分組可沿路徑2傳輸，繞開極區(qū)ISL，即當(dāng)前分組的傳輸路徑不會(huì)受到網(wǎng)絡(luò)拓?fù)淇煺涨袚Q的影響。

2.1 LEO衛(wèi)星航點(diǎn)的確定

通過上述可知WSR算法的關(guān)鍵在于確定衛(wèi)星航點(diǎn)，由衛(wèi)星網(wǎng)絡(luò)拓?fù)溥\(yùn)動(dòng)的周期性，可計(jì)算出任意時(shí)刻的衛(wèi)星節(jié)點(diǎn)及ISL的位置。因此，可以根據(jù)源節(jié)點(diǎn)S或目標(biāo)節(jié)點(diǎn)D在當(dāng)前時(shí)刻的位置，尋找航點(diǎn)以確定新的分組傳輸路徑，有效避開極區(qū)ISL，以保證在快照切換時(shí)刻正在傳輸分組的路徑不受影響。

2.1.1 源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)在反向縫同側(cè)情況

源節(jié)點(diǎn)S與目標(biāo)節(jié)點(diǎn)D在反向縫同側(cè)的情況下，在S或D所在的軌道上沿著衛(wèi)星運(yùn)動(dòng)的反方向，在極區(qū)外找一個(gè)不與極區(qū)ISL相連的節(jié)點(diǎn)作為航點(diǎn)，為保證傳輸路徑最小，通常選擇距離S或D最小的節(jié)點(diǎn)。S與D確定航點(diǎn)的方法相同，用S進(jìn)行說明。源節(jié)點(diǎn)S確定航點(diǎn)示意圖如圖3所示，表示源節(jié)點(diǎn)S所在位置的3種情況，虛線代表極區(qū)ISL，衛(wèi)星向極區(qū)方向運(yùn)動(dòng)。

圖3 源節(jié)點(diǎn)S確定航點(diǎn)示意圖

圖3（a）中S位于極區(qū)內(nèi)且未到達(dá)極點(diǎn)，為保證傳輸路徑不受快照切換影響，從S發(fā)出的分組前兩跳必須是軌內(nèi)ISL，即選擇a作為S的航點(diǎn)；同理，圖3（b）中S與極區(qū)ISL相連，從S發(fā)出的分組第一跳必須是軌內(nèi)ISL，即選擇b作為S的航點(diǎn)；而圖3（c）中，S的軌間ISL不會(huì)受下次拓?fù)淇煺涨袚Q的影響，故不需要為其尋找航點(diǎn)確定新路徑。

2.1.2 源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)在反向縫兩側(cè)情況

源節(jié)點(diǎn)S與目標(biāo)節(jié)點(diǎn)D分別在反向縫兩側(cè)的情況下，需分別對(duì)S與D進(jìn)行航點(diǎn)確定。在S所在軌道上沿著衛(wèi)星運(yùn)動(dòng)方向和衛(wèi)星運(yùn)動(dòng)的反方向，分別在反向縫的另一側(cè)找到第一個(gè)不與極區(qū)ISL連接的兩個(gè)衛(wèi)星節(jié)點(diǎn)作為節(jié)點(diǎn)S的備選航點(diǎn)，并選擇距離節(jié)點(diǎn)S跳數(shù)較小的備選航點(diǎn)作為其最終的航點(diǎn)。源節(jié)點(diǎn)S與目標(biāo)節(jié)點(diǎn)D確定航點(diǎn)示意圖如圖4所示，在節(jié)點(diǎn)S所在軌道上，從節(jié)點(diǎn)S開始沿著箭頭方向找到備選航點(diǎn)f與b。從節(jié)點(diǎn)S到節(jié)點(diǎn)f為5跳，到節(jié)點(diǎn)b為4跳，故最終選擇節(jié)點(diǎn)b為節(jié)點(diǎn)S的航點(diǎn)。

圖4 源節(jié)點(diǎn)S與目標(biāo)節(jié)點(diǎn)D確定航點(diǎn)示意圖

在反向縫的另一側(cè)確定了源節(jié)點(diǎn)S的航點(diǎn)后，根據(jù)目標(biāo)節(jié)點(diǎn)D當(dāng)前的位置確定是否需要為其確定航點(diǎn)。圖4中節(jié)點(diǎn)D與極區(qū)ISL相連，這與圖3（b）相符，故將節(jié)點(diǎn)d作為節(jié)點(diǎn)D的航點(diǎn)。

2.2 算法流程

WSR算法用于解決網(wǎng)絡(luò)拓?fù)淇煺涨袚Q而導(dǎo)致傳輸路徑中斷的問題。在發(fā)送每個(gè)分組前，根據(jù)LEO衛(wèi)星網(wǎng)絡(luò)拓?fù)涞闹芷冢?jì)算出各個(gè)衛(wèi)星節(jié)點(diǎn)的位置，判斷當(dāng)前時(shí)刻Dijkstra算法計(jì)算出的分組傳輸路徑是否包含極區(qū)ISL，若包含則通過WSR算法找到航點(diǎn)，確定新的傳輸路徑發(fā)送分組。WSR算法流程如圖5所示，其函數(shù)功能解釋見表3。

表3 函數(shù)功能解釋

算法執(zhí)行步驟如下。

步驟1：首先輸入源節(jié)點(diǎn)S、目標(biāo)節(jié)點(diǎn)D與一個(gè)用于存儲(chǔ)航點(diǎn)的集合（初始為空），并判斷S與D的運(yùn)動(dòng)方向是否一致，運(yùn)動(dòng)方向一致可說明S與D在反向縫同側(cè)，反之則在不同側(cè)。Dir()與Dir()返回結(jié)果代表S與D的運(yùn)動(dòng)方向，運(yùn)動(dòng)方向一致執(zhí)行步驟2，不一致則執(zhí)行步驟5。

圖5 WSR算法流程

步驟2：通過POS()獲取S的緯度位置信息，判斷是否大于極圈緯度66°，用bool型變量pos存儲(chǔ)判斷結(jié)果。pos為0，即S位于極區(qū)內(nèi)需為其尋找航點(diǎn)；pos非0，即S處于極區(qū)外，但仍需要確定S運(yùn)動(dòng)方向的前一個(gè)衛(wèi)星節(jié)點(diǎn)S+1的緯度位置，判斷S在下一張拓?fù)淇煺罩惺欠裨跇O區(qū)內(nèi)。POS(+1)執(zhí)行判斷結(jié)果存儲(chǔ)于nextpos中，若nextpos為0，即S+1在極區(qū)內(nèi)，說明S在下一張拓?fù)淇煺罩性跇O區(qū)內(nèi)，即當(dāng)前時(shí)刻S的軌間ISL為極區(qū)ISL，需要為其尋找航點(diǎn)，執(zhí)行步驟3，為S尋找航點(diǎn)；若nextpos非0，即S+1不在極區(qū)內(nèi)，說明S在下一張拓?fù)淇煺罩胁辉跇O區(qū)內(nèi)，則執(zhí)行步驟4直接為D尋找航點(diǎn)。

步驟3：通過BACKW()在S所在軌道上沿著衛(wèi)星運(yùn)動(dòng)反方向?qū)ふ液近c(diǎn)，并存儲(chǔ)于集合中，BACKW()算法偽代碼如算法1所示，其中tempS為存儲(chǔ)衛(wèi)星節(jié)點(diǎn)編號(hào)的臨時(shí)變量，sat為一個(gè)軌道上的衛(wèi)星數(shù)量。

算法1 BACKW()算法

輸入：節(jié)點(diǎn)編號(hào)

輸出：航點(diǎn)編號(hào)

（1） while POS() == 0 do

（2） tempS←modsat

（3） if tempS== 0 then

（4）←+sat– 1

（5） else←– 1

（6） end if

（7）end while

（8）←– 1

（9） return

步驟4：通過POS()與POS(1)，判斷是否需要為D尋找航點(diǎn)，判斷邏輯與步驟2中是否需要為S尋找航點(diǎn)的判斷邏輯相同。若需要，則通過BACKW()在D所在軌道上沿著衛(wèi)星運(yùn)動(dòng)反方向?qū)ふ液近c(diǎn)，存儲(chǔ)于集合中，并結(jié)束流程。

步驟5：S與D運(yùn)動(dòng)方向不一致的情況下，即S與D在反向縫兩側(cè)時(shí)，需通過OVERF()在S所在軌道上，沿著S運(yùn)動(dòng)反方向在反向縫的另一側(cè)確定兩個(gè)不在極區(qū)的備選航點(diǎn)f與b，并比較S到f的跳數(shù)Pa(,)與到b的跳數(shù)Pa(,)，選取距離S較短的備選航點(diǎn)作為其最終的航點(diǎn)并存儲(chǔ)于中，再執(zhí)行步驟4。函數(shù)OVERF()的算法偽代碼如算法2所示，其中’用于沿衛(wèi)星運(yùn)動(dòng)方向執(zhí)行遍歷使用，與分別用于記錄正向遍歷與反向遍歷執(zhí)行次數(shù)。

算法2 OVERF()算法

輸入：節(jié)點(diǎn)編號(hào)

輸出：航點(diǎn)編號(hào)

（1）’←,← 0,← 0

（2） while POS() >= POS(– 1) do

（3） temp←modsat

（4） if temp== 0 then

（5）←+sat– 1

（6） else←– 1

（7） end if

（8）←+ 1

（9） end while

（10）←– 2

（11） Pa(,) ←+ 2

（12） while POS(’) >= POS(’ + 1) do

（13） temp← (’1) modsat

（14） if temp== 0 then

（15）’ ←’ –sat+ 1

（16） else’ ←’ + 1

（17） end if

（18）←+ 1

（19） end while

（20）←’ + 1

（21） Pa(,) ←+ 1

（22）if Pa(,) >= Pa(,)

（23）←

（24）else←

（25） end if

（26） return

因此，最后輸出的航點(diǎn)集合一定非空，源節(jié)點(diǎn)S根據(jù)利用SR規(guī)劃新的分組傳輸路徑，從而導(dǎo)致頻繁的拓?fù)淇煺涨袚Q不會(huì)對(duì)分組傳輸造成影響。

3 仿真模型描述與場(chǎng)景設(shè)置

為了在NS-3仿真平臺(tái)中實(shí)現(xiàn)對(duì)WSR算法的性能仿真，在仿真中根據(jù)銥星系統(tǒng)設(shè)計(jì)出以一種簡(jiǎn)化的LEO衛(wèi)星移動(dòng)模型。對(duì)于大規(guī)模星座，其拓?fù)渥儎?dòng)具有與中小規(guī)模星座相同的周期性，其可預(yù)測(cè)的極區(qū)ISL中斷，同樣可以采用WSR算法。

模型設(shè)計(jì)6個(gè)圓形軌道面等夾角間隔，即相鄰軌道面夾角為30°；設(shè)計(jì)每個(gè)軌道面上的11顆衛(wèi)星等距離間隔，即兩顆相鄰衛(wèi)星之間夾角約為32.72°，衛(wèi)星軌道高度設(shè)置為780 km。模型中衛(wèi)星節(jié)點(diǎn)的位置可由真近點(diǎn)角(,)與升交點(diǎn)赤經(jīng)()確定，計(jì)算式為：

其中，代表衛(wèi)星節(jié)點(diǎn)編號(hào)，即=0,1,2,...,65；為當(dāng)前仿真時(shí)間，Sat代表一個(gè)軌道內(nèi)的衛(wèi)星數(shù)量，Orb代表模型中的軌道數(shù)，Sat代表衛(wèi)星運(yùn)動(dòng)周期。如該模型在運(yùn)動(dòng)190 s后，24號(hào)衛(wèi)星節(jié)點(diǎn)的真近點(diǎn)角(190,24)約為76.8°，升交點(diǎn)赤經(jīng)(24)為180°。

模型中衛(wèi)星經(jīng)過極圈時(shí)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化，該時(shí)間點(diǎn)即拓?fù)淇煺涨袚Q的時(shí)間點(diǎn)，從小到大排序?yàn)椋?7.68 s、186.22 s、361.74 s、460.11 s、635.64 s、727.17 s、909.69 s等。

選取OLSR與Dijkstra算法與WSR算法進(jìn)行時(shí)延與分組丟失率的比較，以分析拓?fù)淇煺涨袚Q導(dǎo)致的傳輸路徑中斷問題與時(shí)延抖動(dòng)問題。NS-3平臺(tái)中，Dijkstra算法被稱為全局路由算法，全局路由的路由表更新函數(shù)沒有考慮計(jì)算路由的時(shí)間成本，即不會(huì)出現(xiàn)分組丟失，而且分組傳輸時(shí)延最優(yōu)，故在實(shí)際場(chǎng)景中無法實(shí)現(xiàn)，因此可認(rèn)為此路由算法是理想最佳路由。仿真中所用參數(shù)見表4。

表4 仿真參數(shù)設(shè)置

場(chǎng)景1為源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)在反向縫同側(cè)，目標(biāo)節(jié)點(diǎn)在186.22 s進(jìn)入極區(qū)；場(chǎng)景2則為源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)在反向縫兩側(cè)，源節(jié)點(diǎn)在727.17 s進(jìn)入極區(qū)。場(chǎng)景1、場(chǎng)景2中，源節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間由Dijkstra算法計(jì)算出的最短路徑存在極區(qū)ISL，故可以證明WSR算法是否能解決拓?fù)淇煺涨袚Q造成的路徑中斷問題。

4 算法性能對(duì)比

4.1 算法性能評(píng)價(jià)指標(biāo)

仿真實(shí)驗(yàn)中選取分組端到端的傳輸時(shí)延d作為算法性能的評(píng)價(jià)指標(biāo)之一，通過觀察前后傳輸分組的時(shí)延變化分析是否產(chǎn)生傳輸路徑中斷或時(shí)延抖動(dòng)問題，計(jì)算式如下：

其中，rk代表目標(biāo)節(jié)點(diǎn)接收第個(gè)分組的時(shí)間點(diǎn)，sk代表源節(jié)點(diǎn)發(fā)送第個(gè)分組的時(shí)間點(diǎn)。若拓?fù)淇煺涨袚Q造成傳輸路徑中斷，則會(huì)使得分組丟失率PLR上升，其計(jì)算式如下：

其中，s與r分別代表源節(jié)點(diǎn)發(fā)送分組的個(gè)數(shù)與目標(biāo)節(jié)點(diǎn)接收分組的個(gè)數(shù)。另外，定義前后分組傳輸?shù)臅r(shí)延抖動(dòng)()為：

式（5）體現(xiàn)了前后分組傳輸時(shí)延的變化程度，通過觀察時(shí)延抖動(dòng)的大小與個(gè)數(shù)能夠更好地分析出算法對(duì)抖動(dòng)問題的影響。

4.2 仿真結(jié)果與分析

將WSR算法在兩種場(chǎng)景下與OLSR算法、Dijkstra算法進(jìn)行仿真對(duì)比分析，分組傳輸時(shí)延比較如圖6所示，OLSR與WSR的目標(biāo)節(jié)點(diǎn)接收分組個(gè)數(shù)比較如圖7所示，OLSR與WSR的時(shí)延抖動(dòng)比較如圖8所示。

圖6中，兩種場(chǎng)景下，不考慮路由重計(jì)算時(shí)間的Dijkstra算法計(jì)算出的最短路徑作為最理想的傳輸路徑用于比較。OLSR分別在186.22 s與727.17 s發(fā)生分組傳輸中斷，即OLSR兩種場(chǎng)景下的傳輸路徑包含極區(qū)ISL，在網(wǎng)絡(luò)拓?fù)淇煺涨袚Q時(shí)造成分組傳輸路徑中斷，如圖6中所示的兩個(gè)中斷區(qū)間。因?yàn)橹虚g節(jié)點(diǎn)的重路由造成中間節(jié)點(diǎn)上正在傳輸?shù)姆纸M丟失，如圖7所示，OLSR分別在186.22 s與727.17 s目標(biāo)節(jié)點(diǎn)接收分組個(gè)數(shù)開始不變，即發(fā)生分組丟失；最終目標(biāo)節(jié)點(diǎn)接收的分組個(gè)數(shù)分別為140與158，即分組丟失率分別為30%和21%。而WSR算法在拓?fù)淇煺涨袚Q前，分別約在183 s與725 s計(jì)算出不包含極區(qū)ISL的傳輸路徑，從而避免了OLSR中出現(xiàn)的問題，并且如圖7所示，目標(biāo)節(jié)點(diǎn)接收了源節(jié)點(diǎn)所發(fā)的全部分組。因此由圖6與圖7的分析證明WSR算法可以計(jì)算出一條新的傳輸路徑，從而避免拓?fù)淇煺涨袚Q造成的路由中斷問題。

圖8反映了OLSR與WSR在兩種場(chǎng)景下的時(shí)延抖動(dòng)的情況，兩種場(chǎng)景下OLSR出現(xiàn)兩次相對(duì)劇烈的抖動(dòng)現(xiàn)象，而WSR的時(shí)延抖動(dòng)相對(duì)較小，且出現(xiàn)抖動(dòng)的次數(shù)少，故WSR算法能夠較好地改善時(shí)延抖動(dòng)問題。

圖6 分組傳輸時(shí)延比較

圖7 OLSR與WSR的目標(biāo)節(jié)點(diǎn)接收分組個(gè)數(shù)比較

性能比較見表5，進(jìn)一步定量分析了算法性能的對(duì)比。WSR與OLSR相比，兩種場(chǎng)景下，分組丟失率降低分別為0.3和0.21，最大時(shí)延抖動(dòng)分別降低46 ms與126 ms。因此WSR計(jì)算出的傳輸路徑是不受拓?fù)淇煺涨袚Q影響的穩(wěn)定的分組傳輸路徑。

圖8 OLSR與WSR的時(shí)延抖動(dòng)比較

通過上述對(duì)仿真結(jié)果的分析，可以得到結(jié)論，在分組傳輸期間，因拓?fù)淇煺涨袚Q造成OLSR計(jì)算出的傳輸路徑中斷，故發(fā)生嚴(yán)重的抖動(dòng)現(xiàn)象，而WSR算法通過計(jì)算出航點(diǎn)位置，重新為分組找到一條不受拓?fù)淇煺涨袚Q影響的傳輸路徑，從而解決了路由中斷問題，并改善了時(shí)延抖動(dòng)與分組丟失現(xiàn)象。

表5 性能比較

5 結(jié)束語

本文通過虛擬拓?fù)浼夹g(shù)對(duì)LEO衛(wèi)星拓?fù)涞膭?dòng)態(tài)問題進(jìn)行分析解決，重點(diǎn)針對(duì)因拓?fù)淇煺涨袚Q導(dǎo)致極區(qū)ISL斷開、造成路由中斷乃至整個(gè)業(yè)務(wù)流崩潰的問題做出闡述分析，并提出一種基于衛(wèi)星航點(diǎn)的分段路由算法，通過仿真實(shí)現(xiàn)了對(duì)算法性能的研究。

仿真實(shí)驗(yàn)中，WSR算法分組丟失率低，時(shí)延抖動(dòng)小，并且通過設(shè)定航點(diǎn)計(jì)算出的新的分組傳輸路徑能夠避開極區(qū)ISL，從而解決了網(wǎng)絡(luò)拓?fù)渥兓瘜?dǎo)致的路由中斷問題。如今LEO衛(wèi)星數(shù)量的不斷增加使得拓?fù)淇煺涨袚Q頻率提高，導(dǎo)致抖動(dòng)現(xiàn)象頻繁，WSR算法可有效地解決該問題。實(shí)際情況下，若某顆衛(wèi)星節(jié)點(diǎn)發(fā)生故障，恢復(fù)故障衛(wèi)星及路由需要較長(zhǎng)時(shí)間，可利用WSR算法繞過發(fā)生故障的衛(wèi)星，以保證業(yè)務(wù)流的持續(xù)性。

[1] ZHANG J R, ZHU S B, BAI H F, et al. Optimization strategy to solve transmission interruption caused by satellite-ground link switching[J]. IEEE Access, 2020(8): 32975-32988.

[2] LI C C, ZHANG Y S, XIE R C, et al. Integrating edge computing into low earth orbit satellite networks: architecture and prototype[J]. IEEE Access, 2021(9): 39126-39137.

[3] MARCO G, MICHELE Z. Non-terrestrial networks in the 6G era: challenges and opportunities[J]. IEEE Network, 2021, 35(2): 244-251.

[4] GUO H Z, LI J Y, LIU J J, et al. A survey on space-air-ground-sea integrated network security in 6G[J]. IEEE Communications Surveys & Tutorials, 2022, 24(1): 53-87.

[5] JIA Z Y, SHENG M, LI J D, et al. VNF-based service provision in software defined LEO satellite networks[J]. IEEE Transactions on Wireless Communications, 2021, 20(9): 6139-6153.

[6] KHALIFE J, NEINAVAIE M, KASSAS Z M. The first carrier phase tracking and positioning results with Starlink LEO satellite signals[J]. IEEE Trans on Aerospace and Electronic Systems, 2022, 58(2): 1487-1491.

[7] PORTILLO I D, CAMERON B G, CRAWLEY E F. A technical comparison of three low earth orbit satellite constellation systems to provide global broadband[J]. Acta Astronautica, 2019(159): 123-135.

[8] XIE H R, ZHAN Y F, ZENG G M, et al. LEO Mega-constellations for 6G global coverage: challenges and opportunities[J]. IEEE Access, 2021(9): 164223-164244.

[9] OSORO O B, OUGHTON E J. A techno-economic framework for satellite networks applied to low earth orbit constellations: assessing Starlink, OneWeb and Kuiper[J]. IEEE Access, 2021(9): 141611-141625.

[10] RABJERG J W, LEYVA-MAYORGA I, SORET B, et al. Exploiting topology awareness for routing in LEO satellite constellations[C]//Proceedings of 2021 IEEE Global Communications Conference (GLOBECOM). Piscataway: IEEE Press, 2021: 1-6.

[11] LIU J, LUO R Z, HUANG T, et al. A load balancing routing strategy for LEO satellite network[J]. IEEE Access, 2020(8): 155136-155144.

[12] RUIZ-DE-AZúA J A, CAMPS A, CALVERAS AUGé A. Benefits of using mobile Ad-Hoc network protocols in federated satellite systems for polar satellite missions[J]. IEEE Access, 2018(6): 56356-56367.

[13] YUE P C, QU H, ZHAO J H, et al. An inter satellite link handover management scheme based on link remaining time[C]// Proceedings of the 2nd IEEE International Conference on Computer and Communications. Piscataway: IEEE Press, 2016: 1799-1803.

[14] RODRIGUEZ C G, FRANCK L, BAUDOIN C, et al. OLSR-H: a satellite-terrestrial hybrid broadcasting for OLSR signaling[C]// Proceedings of International Conference on Personal Satellite Services. Heidelberg: Springer, 2011: 143-150.

[15] WERNER M, DELUCCHI C, VOGEL H, et al. ATM-based routing in LEO/MEO satellite networks with intersatellite links[J]. IEEE Journal on Selected Areas in Communications, 1997, 15(1): 69-82.

[16] 齊星, 柳震, 梁家輝, 等. 一種面向低軌遙感星座的路由任務(wù)規(guī)劃算法研究[J]. 電信科學(xué), 2022, 38(4): 30-38.

QI X, LIU Z, LIANG J H, et al. Research on a routing task planning algorithm for LEO remote sensing constellation[J]. Telecommunications Science, 2022, 38(4): 30-38.

[17] ZHU Y, RUI L L, QIU X S, et al. Double-layer satellite communication network routing algorithm based on priority and failure probability[C]//Proceedings of the 15th International Wireless Communications & Mobile Computing Conference. Piscataway: IEEE Press, 2019: 1518-1523.

[18] LIU H Y, SUN F C, YANG Z, et al. A novel distributed routing algorithm for LEO satellite network[C]//Proceedings of 2012 International Conference on Industrial Control and Electronics Engineering. Los Alamitos: IEEE Computer Society, 2012: 37-40.

[19] LIU F, QIAN G. Simulation analysis of network capacity for LEO satellite[C]//Proceedings of 2020 International Conference on Computer Science and Management Technology. Piscataway: IEEE Press, 2020: 100-104.

[20] VENTRE P L, SALSANO S, CIANFRANI A, et al. Segment routing: a comprehensive survey of research activities, standardization efforts, and implementation results[J]. IEEE Communications Surveys Tutorials, 2021, 23(1): 182-221.

[21] ABDULLAH Z N, AHMAD I, HUSSAIN I. Segment routing in software defined networks: a survey[J]. IEEE Communications Surveys & Tutorials, 2019, 21(1): 464-486.

[22] PAN G F, YE J, AN J P, et al. Latency versus reliability in LEO mega-constellations: terrestrial, aerial, or space relay[J]. IEEE Transactions on Mobile Computing, 2022, Early Access.

[23] XIE X Y, WANG J, GUO X B, et al. Performance evaluation of Ad-Hoc routing protocols in hybrid MANET-Satellite network[C]// Proceedings of International Conference on Machine Learning and Intelligent Communications. Heidelberg: Springer, 2018: 500-509.

[24] PAN T, HUANG T, LI X C, et al. OPSPF: orbit prediction shortest path first routing for resilient LEO satellite networks[C]// Proceedings of 2019 IEEE International Conference on Communications. Piscataway: IEEE Press, 2019: 1-6.

[25] LU N N, ZHANG H P, MA J. A novel inter-satellite routing protocol based on link recognizing[C]//Proceedings of International Conference on Cyberspace Technology (CCT 2014). Bangalore, KA: IET, 2014: 1-4.

[26] RUIZ J A, CALVERAS A, CAMPS A. Internet of satellites (IoSat): analysis of network models and routing protocol requirements[J]. IEEE Access, 2018(6): 20390-20411.

[27] LIU W, TAO Y, LIU L. Load-balancing routing algorithm based on segment routing for traffic return in LEO satellite networks[J]. IEEE Access, 2019(7): 112044-112053．

[28] ZHOU J X, ZHANG Z P, ZHOU N. A segment list management algorithm based on segment routing[C]//Proceeding of IEEE the 11th International Conference on Communication Software and Networks. Piscataway: IEEE Press, 2019: 297-302.

Analysis on waypoint-segment routing and performance evaluation for LEO satellite networks

ZHAO Xin1, ZHAO Guang1, CHEN Rui1, WANG Wennai1, 2

1. College of Telecommunications & Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China2. Key Lab of Broadband Wireless Communication and Sensor Network Technology, Ministry of Education, Nanjing University of Posts and Telecommunications, Nanjing 210003, China

A waypoint-segment routing (WSR) algorithm was proposed. Based on the predictable periodicity of the topological changes of satellite network, the location of satellite waypoints based on the link state of satellite nodes at the current moment was determined by WSR algorithm. The mechanism of flexible planning of packet transmission paths was responded by segment routing to changes in satellite network topology in advance, and a packet transmission path that was not affected by network topology snapshot switch was calculated. Simulation experiment was based on the NS-3, and the optimized link state routing (OLSR) algorithm and the shortest path algorithm were selected to compare with WSR in order to analyze the delay jitter and packet loss rate. It was proved that compared with OLSR, the maximum delay jitter of WSR was reduced by 46 ms and 126 ms respectively in the two scenarios, the packet loss rate was reduced by 30% and 21% respectively, and the problem of packet transmission path interruption caused by topology snapshot switching can be solved.

low earth orbit satellite network, virtual topology, polar ISL, satellite waypoint routing, performance simulation

TN927

A

10.11959/j.issn.1000-0801.2023020

趙鑫（1995-），男，南京郵電大學(xué)通信與信息工程學(xué)院碩士生，主要研究方向?yàn)榈蛙壭l(wèi)星通信與網(wǎng)絡(luò)規(guī)劃。

趙光（1995-），男，南京郵電大學(xué)通信與信息工程學(xué)院碩士生，主要研究方向?yàn)榈蛙壭l(wèi)星通信與網(wǎng)絡(luò)規(guī)劃。

陳睿（1991-），女，南京郵電大學(xué)通信與信息工程學(xué)院博士生，主要研究方向?yàn)榈蛙壭l(wèi)星通信與網(wǎng)絡(luò)規(guī)劃。

王文鼐（1966-），男，南京郵電大學(xué)教授，主要研究方向?yàn)橥ㄐ啪W(wǎng)技術(shù)理論、通信網(wǎng)仿真與網(wǎng)絡(luò)規(guī)劃。

The Postgraduate Research and Practice Innovation Program of Jiangsu Province (No.KYCX21_0724, No.KYCX20_0718)

2022-07-12；

2023-01-20

王文鼐，wangwn@njupt.edu.cn

江蘇省研究生科研與實(shí)踐創(chuàng)新計(jì)劃項(xiàng)目（No.KYCX21_0724，No.KYCX20_0718）