基于動(dòng)靜結(jié)合方法的衛(wèi)星網(wǎng)絡(luò)路由方法研究*

邢 川，陳二虎，韓笑冬

0 引 言

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

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

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

本文將靜態(tài)方法與動(dòng)態(tài)方法進(jìn)行了有效的結(jié)合，采用自協(xié)調(diào)的方法同時(shí)運(yùn)行動(dòng)態(tài)方法與靜態(tài)方法.當(dāng)星座實(shí)際拓?fù)浞项A(yù)測(cè)時(shí)主要使用靜態(tài)方法，同時(shí)對(duì)網(wǎng)絡(luò)狀態(tài)進(jìn)行實(shí)時(shí)的探測(cè)，減少實(shí)時(shí)不斷更新的計(jì)算工作.當(dāng)探測(cè)到部分節(jié)點(diǎn)或鏈路發(fā)生的故障時(shí)，自動(dòng)切換為動(dòng)態(tài)方法，盡可能降低故障的影響.在故障消失或恢復(fù)后，動(dòng)態(tài)方法可自動(dòng)切換至靜態(tài)方法，此方法可極大的加強(qiáng)傳統(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ò)為點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)[8]，每個(gè)衛(wèi)星有4個(gè)端口，分別與其他4～6個(gè)相鄰衛(wèi)星的衛(wèi)星相鄰，每個(gè)端口與唯一的鄰居衛(wèi)星建立雙向連接通信[9].作為一個(gè)典型的網(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ò)對(duì)路由方法的基本要求是在運(yùn)行正常時(shí)不因?yàn)槁酚伤惴▉G包，在出現(xiàn)故障時(shí)能夠自動(dòng)進(jìn)行規(guī)避.

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

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

2.1 快照建立與切換

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

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

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

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

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

(1)

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

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

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

(4)

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

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

(5)

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

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

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

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

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

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

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

3.1 鏈路探測(cè)機(jī)制

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

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

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

3.3 動(dòng)態(tài)路由計(jì)算

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

4 動(dòng)靜結(jié)合方法

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

4.1 動(dòng)靜切換邏輯

路由協(xié)議切換狀態(tài)機(jī)示意如圖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(使用原始快照進(jìn)行路由計(jì)算)

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

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

事件：

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

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

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

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

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

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

動(dòng)作：

a13:開啟鏈路故障計(jì)時(shí)器

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

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

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

4.2 動(dòng)靜切換方法

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

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

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

5 仿真驗(yàn)證

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

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

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

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

6 結(jié) 論

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

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