邢 川，陳二虎，韓笑冬

0 引 言

近年來，低軌(LEO，low earth orbit)移動衛(wèi)星星座組網(wǎng)成為衛(wèi)星領(lǐng)域的熱點，衛(wèi)星網(wǎng)絡(luò)的路由方法問題實現(xiàn)衛(wèi)星組網(wǎng)的重要技術(shù)問題[1].相比于中高軌衛(wèi)星，LEO衛(wèi)星能夠為用戶提供更低時延的高速網(wǎng)絡(luò)連接，然而低軌衛(wèi)星星座的拓?fù)浣Y(jié)構(gòu)變化也更為頻繁，使得其網(wǎng)絡(luò)路由方法也相應(yīng)較為復(fù)雜.受限于星間鏈路、星地鏈路有限的帶寬、衛(wèi)星有限的計算能力和數(shù)據(jù)存儲能力的制約，衛(wèi)星網(wǎng)絡(luò)的特點區(qū)別于傳統(tǒng)地面固定網(wǎng)絡(luò)和無線通信網(wǎng)絡(luò)，因此必須針對衛(wèi)星網(wǎng)絡(luò)的特點研究并設(shè)計新的路由方法[2].

對于LEO衛(wèi)星星座來說，軌道和衛(wèi)星排布是確定的，每顆衛(wèi)星的環(huán)繞周期通常是固定的，因而其星座的拓?fù)浣Y(jié)構(gòu)隨時間的變化是可預(yù)測的[3].因此傳統(tǒng)的星間路由方法主要是根據(jù)衛(wèi)星網(wǎng)絡(luò)周期性的拓?fù)渥兓A(yù)先將路由信息包括路由表和轉(zhuǎn)發(fā)表注入到衛(wèi)星上，衛(wèi)星節(jié)點按照時間進行相應(yīng)的路由和轉(zhuǎn)發(fā)，此類路由方法為靜態(tài)配置類路由方法(簡稱靜態(tài)方法)[4].當(dāng)前地面網(wǎng)絡(luò)常用的路由方法主要包括OSPF、AODV、ATM等方法[5]，這類型方法通常需要動態(tài)的進行信令的分發(fā)傳遞，獲取實時的鏈路狀態(tài)和節(jié)點狀態(tài)，然后及時更新計算路由路徑，此類方法為動態(tài)探測類路由方法(簡稱動態(tài)方法)[6].

在衛(wèi)星網(wǎng)絡(luò)中應(yīng)用靜態(tài)方法的弊端是無法適應(yīng)突發(fā)的鏈路故障及網(wǎng)絡(luò)結(jié)構(gòu)變化.當(dāng)某個衛(wèi)星節(jié)點或某條衛(wèi)星鏈路發(fā)生故障或通信流量變化造成鏈路擁塞時，繼續(xù)根據(jù)原始拓?fù)浣Y(jié)構(gòu)規(guī)劃路徑可能會導(dǎo)致丟包或擁塞加重.動態(tài)方法的弊端則是消耗占用衛(wèi)星網(wǎng)絡(luò)大量的帶寬，同時受收斂速度影響必然會造成一定程度的丟包[7].

本文將靜態(tài)方法與動態(tài)方法進行了有效的結(jié)合，采用自協(xié)調(diào)的方法同時運行動態(tài)方法與靜態(tài)方法.當(dāng)星座實際拓?fù)浞项A(yù)測時主要使用靜態(tài)方法，同時對網(wǎng)絡(luò)狀態(tài)進行實時的探測，減少實時不斷更新的計算工作.當(dāng)探測到部分節(jié)點或鏈路發(fā)生的故障時，自動切換為動態(tài)方法，盡可能降低故障的影響.在故障消失或恢復(fù)后，動態(tài)方法可自動切換至靜態(tài)方法，此方法可極大的加強傳統(tǒng)衛(wèi)星網(wǎng)絡(luò)路由方法的可靠性，提高衛(wèi)星的自主生存能力.

1 星座拓?fù)浣Y(jié)構(gòu)

在典型的極地軌道低軌星座網(wǎng)絡(luò)模型中，星座內(nèi)部衛(wèi)星間的網(wǎng)絡(luò)為點對點網(wǎng)絡(luò)[8]，每個衛(wèi)星有4個端口，分別與其他4～6個相鄰衛(wèi)星的衛(wèi)星相鄰，每個端口與唯一的鄰居衛(wèi)星建立雙向連接通信[9].作為一個典型的網(wǎng)格狀無向網(wǎng)絡(luò)，網(wǎng)絡(luò)部分拓?fù)淇梢猿橄鬄槿鐖D1所示的結(jié)構(gòu).

圖1 網(wǎng)絡(luò)部分拓?fù)浣Y(jié)構(gòu)圖Fig.1 Network topology frame

該類型網(wǎng)絡(luò)對路由方法的基本要求是在運行正常時不因為路由算法丟包，在出現(xiàn)故障時能夠自動進行規(guī)避.

2 靜態(tài)路由方法

自協(xié)調(diào)路由方法中以基于快照的靜態(tài)路由作為靜態(tài)方法，當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)與快照相符時，靜態(tài)方法快照按時序切換，在某幅快照時間內(nèi)，路由表根據(jù)該快照所反映的網(wǎng)絡(luò)拓?fù)溆嬎愕玫?為了防止快照切換過于頻繁及切換過程導(dǎo)致的丟包，本文提出一種快照序列構(gòu)造及分割策略.

2.1 快照建立與切換

當(dāng)星座內(nèi)衛(wèi)星的連接關(guān)系與當(dāng)前時刻拓?fù)淇煺障嗤瑫r，認(rèn)為沒有星間鏈路的故障，這時星座內(nèi)采用靜態(tài)路由方法.雖然網(wǎng)絡(luò)隨著衛(wèi)星的運動而時刻發(fā)生變化，但一段時間內(nèi)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)保持不變，且在網(wǎng)絡(luò)不同周期內(nèi)其拓?fù)浣Y(jié)構(gòu)是周期性的.靜態(tài)路由方法利用星座結(jié)構(gòu)的周期性變化特征，通過對衛(wèi)星運行狀態(tài)的仿真將單個系統(tǒng)周期進行“分片”，生成離散的有限可數(shù)的拓?fù)淇煺?將衛(wèi)星構(gòu)型發(fā)生變化的時刻定義為集合T=(t0,t1,…,tN)，其中每個時間代表一個拓?fù)渥兓臅r刻，劃分時間間隔[ti,tt+1]的依據(jù)是任意一條星間鏈路發(fā)生變化的時刻(連接或斷開).在時間間隔內(nèi)網(wǎng)絡(luò)拓?fù)洳话l(fā)生變化，定義此時快照為Si，時間間隔[ti,ti+1]定義為有效時間間隔.在全周期內(nèi)，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可以總結(jié)為一個快照序列S=(S0,S1,S2,…,SN).

圖2 離散拓?fù)涫疽鈭DFig.2 Discrete-time topology sketch map

由于某些時段多個鏈路發(fā)生切換的時間間隔很小，例如在高緯地區(qū)異軌相鄰衛(wèi)星相對速度較大，往往規(guī)定緯度高于60°時異軌星間鏈路不連接，故當(dāng)幾個異軌衛(wèi)星到達(dá)指定緯度時幾乎同時發(fā)生鏈路斷開.若仍以單條鏈路的變化劃分快照可能會造成快照在短時間內(nèi)發(fā)生多次快速切換，為了避免這種狀況，應(yīng)對有效時間間隔較小的幾個快照進行合并.

以圖3為例，Tk表示快照生存時間.當(dāng)在T0到Tk中，相鄰單幅快照之間只有一條鏈路發(fā)生變化，若不存在反復(fù)變化的鏈路(即各條鏈路最多只變化一次)，可以將這段時間的快照進行合并，保留T0時刻和時刻兩幅快照作為快照N和N+2，到為過渡狀態(tài).過渡狀態(tài)以第N和N+2幅快照作為依據(jù)，兩幅之間有通斷變化的鏈路在過渡狀態(tài)快照中均強制設(shè)置為斷，T0到T8之間始終不變的鏈路即保持其狀態(tài)，從而保證不會因為快照合并和切換而發(fā)生丟包.以S[N]表示第N幅快照內(nèi)所有連接鏈路，則上述規(guī)則可以表示為，

S[N+1]=S[N]∩S[N+2]

(1)

圖3 快照合并示例Fig.3 Snapshot combination demonstration

此外，為了保證切換過程的可靠性，需要將切換時間特殊處理.以圖3(b)為例，S[N]與S[N+1]快照在tp時刻發(fā)生切換，若某數(shù)據(jù)包在tp-Δt時刻發(fā)出(其中Δt?t0)，tp時刻前未到達(dá)目的端.如果數(shù)據(jù)包恰好經(jīng)過在tp時刻斷開的鏈路，就會發(fā)生丟包.

過渡快照N+1的開始時間前移δa時間，同時結(jié)束時間后移δb時間.δa和δb的值可以根據(jù)數(shù)據(jù)包在網(wǎng)絡(luò)中傳輸?shù)淖畲髸r延確定.對于有M×N顆衛(wèi)星(N個軌道面，每個軌道面上有M顆衛(wèi)星)的星座來說，其網(wǎng)絡(luò)半徑R為信息在網(wǎng)絡(luò)中傳輸?shù)淖畲缶嚯x(跳數(shù)).

(4)

對應(yīng)的端到端時延可以表示為，

DTmax=∑i,jDISLIJ+r·ts≈R·(DISL_average+TS)

(5)

其中，DISLIJ表示數(shù)據(jù)包在衛(wèi)星i到衛(wèi)星j間的傳播時延，可以用其平均值DISL_average近似估算；TS為數(shù)據(jù)包在路由節(jié)點內(nèi)的傳輸時延.不妨取δa=δb=DTmax，盡可能減少拓?fù)淝袚Q過程導(dǎo)致的丟包.

拓?fù)淇煺湛梢灶A(yù)置在星上非易失存儲器中，也可以由地面站上注到衛(wèi)星內(nèi)存中，以節(jié)約星上存儲資源.快照對應(yīng)的路由表也可以采用事先預(yù)置的方式，或通過快照切換前在星上提前進行計算的方式節(jié)約存儲空間.

2.2 靜態(tài)路由計算

當(dāng)系統(tǒng)內(nèi)未出現(xiàn)鏈路故障時，快照只在ti(i∈T)時刻發(fā)生切換，并將在時間間隔內(nèi)維持不變，在此時間間隔內(nèi)的選路都遵循該拓?fù)淇煺占捌鋵?yīng)的路由表.在快照有效時間內(nèi)，路由問題可以看作是靜態(tài)拓?fù)渎酚桑瑥亩行Ш喕酚蓡栴}.路由表使用最短路徑算法Dijkstra計算得到，在時間段內(nèi)的數(shù)據(jù)包都將根據(jù)這一時段事先計算的路由表進行轉(zhuǎn)發(fā).

3 動態(tài)路由方法

動態(tài)路由方法主用于解決星間鏈路出現(xiàn)異常故障的問題，此時鏈路實際連接狀態(tài)與拓?fù)浣Y(jié)構(gòu)不符，繼續(xù)使用靜態(tài)路由方法會造成丟包.根據(jù)衛(wèi)星的計算能力和傳輸能力，采用裁剪的OSPF協(xié)議實現(xiàn)動態(tài)路由方法.

動態(tài)路由方法依賴HELLO協(xié)議及LSA協(xié)議進行鏈路狀態(tài)的探知和通知.在當(dāng)前時刻已經(jīng)確認(rèn)正確的鏈路狀態(tài)基礎(chǔ)上進行鏈路狀態(tài)的更新，依靠實時的HELLO探測及(相較于靜態(tài)路由)更頻繁的LSA洪泛在全網(wǎng)各衛(wèi)星間同步當(dāng)前網(wǎng)絡(luò)拓?fù)錉顟B(tài).

3.1 鏈路探測機制

衛(wèi)星之間需要短間隔周期性發(fā)送探測數(shù)據(jù)包(HELLO)，通過交換HELLO包確定可達(dá)的鄰居路由器.當(dāng)衛(wèi)星某個端口收到來自其他衛(wèi)星的HELLO時，該衛(wèi)星將根據(jù)當(dāng)前快照中對應(yīng)的拓?fù)浣Y(jié)構(gòu)判斷該HELLO包是否來自其相鄰衛(wèi)星，若是正常鄰居衛(wèi)星，且在對方應(yīng)答的鄰居表中填寫自身ID，建立雙向的連接關(guān)系，否則將丟棄該HELLO包.此外，HELLO協(xié)議還負(fù)責(zé)連接關(guān)系的維持.對于已經(jīng)建立連接的衛(wèi)星，當(dāng)上次接收到鄰居衛(wèi)星的HELLO包超過一定時間間隔后，判定鏈路超時.HELLO包協(xié)議作為鏈路探測的基礎(chǔ)協(xié)議，應(yīng)當(dāng)始終以較高的頻次運行.

3.2 連接狀態(tài)洪泛機制

為了保證星座中每個衛(wèi)星都維護相同的連接狀態(tài)，需在衛(wèi)星間進行連接狀態(tài)洪泛.衛(wèi)星網(wǎng)絡(luò)運行時，當(dāng)某個衛(wèi)星的鏈路發(fā)生變化或鏈路狀態(tài)到達(dá)刷新時間，衛(wèi)星向外發(fā)送一個反映當(dāng)前自身連接鏈路狀態(tài)的LSA(link state advertisement)數(shù)據(jù)包，用洪泛的方法向全網(wǎng)進行鏈路狀態(tài)更新，最終保證整個衛(wèi)星網(wǎng)絡(luò)中所有衛(wèi)星都能夠得到該消息的一個副本.其他衛(wèi)星收到最新的LSA時，若其中表示的連接信息與其自身所維護的連接狀態(tài)數(shù)據(jù)庫不同，就對數(shù)據(jù)庫進行更新，從而保證每顆衛(wèi)星都能同步維護相同的星座連接狀態(tài).

3.3 動態(tài)路由計算

每顆衛(wèi)星再根據(jù)其連接狀態(tài)數(shù)據(jù)庫進行路由表的計算，以自身衛(wèi)星為根節(jié)點，計算到網(wǎng)絡(luò)內(nèi)除自身以外的其他衛(wèi)星所需要經(jīng)過的最優(yōu)路徑，并將其存在路由表中.衛(wèi)星利用Dijkstra最短路徑算法自主進行路由表的動態(tài)計算，依照此時計算得到的路由表進行查表轉(zhuǎn)發(fā)

4 動靜結(jié)合方法

在靜態(tài)路由階段可以設(shè)置較低頻次的LSA刷新策略，或僅當(dāng)HELLO協(xié)議探測到鏈路狀態(tài)變化時再進行LSA的洪泛，以減少靜態(tài)路由階段的網(wǎng)絡(luò)開銷.當(dāng)系統(tǒng)進入動態(tài)路由時期后，需要各衛(wèi)星節(jié)點以較高的頻次進行LSA洪泛，以保證鏈路的變化能夠在全網(wǎng)各個節(jié)點快速悉知.

4.1 動靜切換邏輯

路由協(xié)議切換狀態(tài)機示意如圖4所示.

圖4 系統(tǒng)狀態(tài)轉(zhuǎn)換圖Fig.4 System state-transition graph

圖中包含狀態(tài)：

S0:路由停止?fàn)顟B(tài)

S1:靜態(tài)路由狀態(tài)1(使用原始快照進行路由計算)

S2:動態(tài)路由狀態(tài)

S3:靜態(tài)路由狀態(tài)2(存在永久故障鏈路，根據(jù)修改后的快照進行路由表計算)

事件：

e01:系統(tǒng)開始運行時網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與快照相符

e03:系統(tǒng)開始運行時網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與快照不符

e13:連接狀態(tài)與快照不符(至少一條鏈路故障)

e21:永久故障鏈路恢復(fù)，連接狀態(tài)與快照相符?e31:鏈路故障恢復(fù)(故障計時器未超時)，連接狀態(tài)與快照相符

e32:故障鏈路計時器超時，認(rèn)為出現(xiàn)永久故障鏈路，連接狀態(tài)與快照不符?

e_stop:系統(tǒng)停止運行

動作：

a13:開啟鏈路故障計時器

a21:取消快照中永久故障標(biāo)識，恢復(fù)原始快照

a31:關(guān)閉鏈路故障計時器

a32:在快照中給相應(yīng)鏈路置永久故障標(biāo)識

4.2 動靜切換方法

系統(tǒng)在每次鏈路狀態(tài)發(fā)生變化時，將其與當(dāng)前時刻快照進行對比.當(dāng)對比結(jié)果相同時，說明星座中沒有故障鏈路或故障鏈路在當(dāng)前時刻快照中應(yīng)該是斷開的鏈路，網(wǎng)絡(luò)實際的拓?fù)渑c快照相符，這時系統(tǒng)采用靜態(tài)路由策略.當(dāng)通過HELLO協(xié)議探測到大于等于一條的鏈路發(fā)生故障時，連接狀態(tài)與拓?fù)淇煺詹环?，該衛(wèi)星由靜態(tài)路由協(xié)議切換到動態(tài)路由協(xié)議，并將該連接狀態(tài)變化的信息通過LSA泛洪到全網(wǎng)，全網(wǎng)所有衛(wèi)星都將在其當(dāng)前連接狀態(tài)中記錄鏈路臨時故障，并切換到動態(tài)路由協(xié)議.當(dāng)HELLO協(xié)議探測到故障鏈路恢復(fù)，由LSA廣播至全網(wǎng)，且連接狀態(tài)恢復(fù)到與當(dāng)前時刻原定快照相同時，系統(tǒng)切換回靜態(tài)路由協(xié)議.

4.3 異常狀態(tài)處理

動態(tài)路由協(xié)議仍然基于當(dāng)前(有故障標(biāo)識的)連接狀態(tài)計算路由表，每當(dāng)連接狀態(tài)發(fā)生變化時，需要重新計算路由表，以供當(dāng)前時段的查表轉(zhuǎn)發(fā).當(dāng)網(wǎng)絡(luò)中存在故障鏈路時，由于存在拓?fù)渥兓瘜?dǎo)致的鏈路周期性斷開/連接，一直使用動態(tài)路由會產(chǎn)生較大星上計算資源及信令開銷，可能造成網(wǎng)絡(luò)的擁塞和丟包.為了防止某條鏈路的長久故障造成系統(tǒng)一直處于動態(tài)路由的狀態(tài)，當(dāng)某些星間鏈路出現(xiàn)長期故障(HELLO協(xié)議無法探測到對方的時間超過規(guī)定時長)時，將在全周期所有快照中標(biāo)記該鏈路為永久故障，并重新計算全周期各個快照對應(yīng)的路由表，在永久故障恢復(fù)之前，全網(wǎng)使用基于新路由表的靜態(tài)路由.待故障恢復(fù)后重新恢復(fù)無故障鏈路的原始靜態(tài)路由，基于原始路由表進行狀態(tài)轉(zhuǎn)發(fā).

5 仿真驗證

本文采用EXata網(wǎng)絡(luò)仿真軟件對路由協(xié)議進行仿真驗證.設(shè)置EXata使用的衛(wèi)星模型為第1章所述模型如圖5所示.

圖5 衛(wèi)星模型仿真場景Fig.5 Satellite model simulation scene

在模型上添加業(yè)務(wù)流測試路由方法運行的正確性，得出以下仿真結(jié)果：

路由方法運行狀態(tài)業(yè)務(wù)丟包率衛(wèi)星連接情況方法收斂時間無故障情況靜態(tài) 0%全部正常連接0s鏈路故障情況動態(tài)2%～5%(在拓?fù)浣Y(jié)構(gòu)發(fā)生變化時丟包)除故障鏈路外正常連接1～5s

6 結(jié) 論

本文通過對的靜態(tài)路由方法和動態(tài)路由方法的有機協(xié)調(diào)，從仿真結(jié)果看，在故障和正常情況下均能夠正常的實現(xiàn)衛(wèi)星網(wǎng)絡(luò)的路由計算，有效提高了路由方法的魯棒性和可靠性.

該路由方法可在各類通信、導(dǎo)航、遙感衛(wèi)星需要使用路由算法時進行應(yīng)用.