導(dǎo)航星座抗毀路由方法與技術(shù)研究

易先清,羅雪山,李健杰,湯邵勛

(國防科技大學(xué)五院信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室,湖南長沙410073)

0 引 言

北斗二代導(dǎo)航系統(tǒng)具有分期建設(shè)、局部覆蓋到全球覆蓋、滿足不同應(yīng)用及性能需求等特點(diǎn),星座組網(wǎng)結(jié)構(gòu)包括同步星座、高軌星座、中軌星座的復(fù)合組網(wǎng)。對于由多個星層組成的二代導(dǎo)航衛(wèi)星網(wǎng)絡(luò),其結(jié)構(gòu)相對單層星座復(fù)雜,特別是各星層之間的相對移動為星座的設(shè)計/建設(shè)與運(yùn)行/管理帶來了極大的挑戰(zhàn),其中基于多層星座結(jié)構(gòu)的二代導(dǎo)航系統(tǒng)路由問題是其中亟待解決的關(guān)鍵問題之一。

在北斗二代導(dǎo)航系統(tǒng)中,需要傳輸?shù)男畔ㄐ亲刂菩畔?包括單星控制信息和星座組網(wǎng)運(yùn)行控制信息)、星座狀態(tài)信息(包括單星狀態(tài)反饋信息和星座組網(wǎng)運(yùn)行狀態(tài)反饋信息)、用戶應(yīng)用信息(包括導(dǎo)航定位信息、授時信息、短報文通信相關(guān)信息等)、感知報告信息(包括雙向授時相關(guān)信息、位置報告信息、目標(biāo)偵測信息)等,為了有效傳輸這些不同類型的信息,必須設(shè)計出合理的二代導(dǎo)航系統(tǒng)路由策略,研究正是從導(dǎo)航系統(tǒng)中各組成星座的組成結(jié)構(gòu)與運(yùn)行特點(diǎn),特別是導(dǎo)航系統(tǒng)中衛(wèi)星節(jié)點(diǎn)失效對其信息傳輸?shù)挠绊懗霭l(fā),進(jìn)行北斗二代導(dǎo)航星座抗毀路由研究。

研究包括如下三個部分:1)在基于我國初步設(shè)計的北斗二代導(dǎo)航星座系統(tǒng)組網(wǎng)結(jié)構(gòu)[15]的基礎(chǔ)上,給出基于此結(jié)構(gòu)的導(dǎo)航星座抗毀路由所需定義,2)分析并給出基于此結(jié)構(gòu)的導(dǎo)航星座抗毀路由算法,3)進(jìn)行分析與總結(jié)。

1 基于GEO/M EO組網(wǎng)的二代導(dǎo)航星座抗毀結(jié)構(gòu)與定義

分析衛(wèi)星網(wǎng)絡(luò)的組網(wǎng)結(jié)構(gòu)是研究二代導(dǎo)航系統(tǒng)通信路由的基礎(chǔ),根據(jù)我國初步設(shè)計的北斗二代導(dǎo)航星座系統(tǒng)組網(wǎng)結(jié)構(gòu),設(shè)計基于此星座組網(wǎng)結(jié)構(gòu)的抗毀路由方法與算法。我國北斗二代導(dǎo)航星座系統(tǒng)由同步靜止軌道星座GEO(高軌星座HEO)、中軌星座MEO、傾斜軌星座IGSO、地面監(jiān)控網(wǎng)節(jié)點(diǎn)站組成。IGSO星座的運(yùn)行方式與MEO星座類似、而且IGSO星座每條軌道上僅有一顆衛(wèi)星,為簡化問題描述、突出研究重點(diǎn),在接下來的討論中將IGSO星座與MEO星座劃分為一類進(jìn)行討論。在同軌星座、鄰軌星座以及GEO星座與MEO星座之間、GEO星座和MEO星座與地面監(jiān)控站節(jié)點(diǎn)之間設(shè)計通信鏈路,定義如下:

1)同步靜止軌道星座(簡稱GEO星層)

GEO星層中的GEO衛(wèi)星均勻分布在赤道上空的地球同步軌道面上,設(shè)GEO星層由NG(NG≥5)顆GEO衛(wèi)星Gi((i=1,2,L,NG)組成。

2)中軌星座(MEO星層)

MEO星層由星座中所有MEO衛(wèi)星組成,并按Walker星座形式組織,提供包括極地區(qū)域的全球性通信覆蓋。設(shè)MEO星層由 NM×MM顆MEO衛(wèi)星Mi,j(i=1,…,NM;j=1,………,MM)組成,其中NM是MEO星層軌道面數(shù),MM為均勻分布在一個軌道面上的衛(wèi)星數(shù)。

3)地面監(jiān)控節(jié)點(diǎn)TS

地面監(jiān)控節(jié)點(diǎn) TS(Terrestrial)由分布在地球表面某固定位置的地面用戶接收終端設(shè)備組成,提供強(qiáng)大的信息處理與收發(fā)能力,被GEO星層或MEO星層所覆蓋。設(shè)地面監(jiān)控節(jié)點(diǎn)由 TSw座地面監(jiān)控節(jié)點(diǎn)TSi(i=1,2,L,TSw)組成。

基于北斗二代導(dǎo)航星座系統(tǒng)組網(wǎng)結(jié)構(gòu),進(jìn)行如下路由描述所需定義,以滿足其抗毀路由分析需求:

定義1(分群與群管理者GH(x)):設(shè)X為某GEO衛(wèi)星Gi通信覆蓋域AGi下的一個MEO物理分群,AG i下對應(yīng)的MEO邏輯分群定義為X′,顯然有X?X′,設(shè) x為群X 中衛(wèi)星,x′為群X′中衛(wèi)星。GEO衛(wèi)星Gi便作為群X 和X′中的群管理者,定義為GH(x)。

定義 2(群首 H(x)):定義 H(x)為 X群群首,根據(jù)分群時刻群X中距離GEO衛(wèi)星Gi由近至遠(yuǎn),依次分為首選群首 H0(x),第1備份群首H1(x),第2備份群首 H2(x),…,第S(X)-1備份群首HS(X)-1(x),這里S()是計算物理群X大小的函數(shù),該函數(shù)只統(tǒng)計群中MEO類型的成員。

首選群首H0(x)為X群中分群時刻距離Gi最近的MEO衛(wèi)星,滿足

定義3(鏈路延時函數(shù)D(lx′→y))設(shè)x′、y分別為二代導(dǎo)航星座系統(tǒng)中各通信節(jié)點(diǎn)直接連接的通信鏈路(只經(jīng)過一跳)兩端的信源節(jié)點(diǎn)和信宿節(jié)點(diǎn),定義 lx′→y為兩通信節(jié)點(diǎn) x′、y間的直連鏈路,其延時函數(shù)D(lx′→y)定義如下

定義4(鏈路延時報告LDR)鏈路延時報告LDR包括MEO星座延時報告MLDR和GEO星座延時報告GLDR。設(shè)x′為MEO星座的某MEO衛(wèi)星,MEO星座延時報告MLDR(x′)定義為一組二元值{y,D(lx′→y)},其中 y是x′與y間通信鏈路的目的節(jié)點(diǎn),可以是地面監(jiān)控節(jié)點(diǎn) TG(TG:Terrestrial Gateway)或MEO衛(wèi)星Mi,j或GEO衛(wèi)星Gi,關(guān)于MEO星座的鏈路延時報告 MLDR(x′)由下式描述:

設(shè)x為GEO星座的某GEO衛(wèi)星,GEO星座延時報告GLDR(x)定義為一組二元值{y,D(lx→y)},其中y是x與y間通信鏈路的目的節(jié)點(diǎn),可以是地面監(jiān)控節(jié)點(diǎn) TG或MEO衛(wèi)星 Mi,j或GEO衛(wèi)星 Gi,關(guān)于 GEO星座的鏈路延時報告GLDR(x)由下式描述:

定義5(群鏈路延時報告 GroupLDR(X′)與網(wǎng)絡(luò)鏈路延時報告 NetLDR)在以某GEO衛(wèi)星xG為群管理者的分群中,其群鏈路延時報告包括群管理者收集的鏈路延時報告GLDR(xG)和其覆蓋域下MEO星座中的所有MEO成員 xM的鏈路延時報告MLDR(xM),其中分為邏輯群X′鏈路延時報告GroupLDR(X′)和物理群X鏈路延時報告GroupLDR(X),分別定義如下:

定義6(路徑Ps→d)定義路徑Ps→d為二代導(dǎo)航星座系統(tǒng)中源節(jié)點(diǎn)s至目的節(jié)點(diǎn)d間的最短延時路徑 。設(shè) N 路徑 Ps→d上的節(jié)點(diǎn)數(shù) ,則路徑 Ps→d定義為

定義7(路由表計算者RTC(x))路由表計算的群管理者GH(x)或群首H0(x)或備份群首 Hi(x)統(tǒng)稱為針對該邏輯分群 X′的路由表計算者RTC(x)。定義如下

定義8(靜態(tài)初始路由表SORT)SOR T根據(jù)二代導(dǎo)航星座系統(tǒng)中衛(wèi)星軌道的可預(yù)測特性和衛(wèi)星運(yùn)行的周期性和當(dāng)時的網(wǎng)絡(luò)狀態(tài)為整個二代導(dǎo)航星座系統(tǒng)各路徑Ps→d預(yù)先計算所得,以引導(dǎo)數(shù)據(jù)包按計劃路徑傳輸。定義邏輯分群X′路由子表SOR T(X′)和全網(wǎng)路由表SORT如下

定義9(動態(tài)真實(shí)路由表D TRT)全網(wǎng)各群X′同時以分布式異步生成其動態(tài)真實(shí)路由表DTRT(X′),各群 DTRT(X′)交換合并形成全網(wǎng)動態(tài)真實(shí)路由表DTRT。邏輯分群X′路由子表DTRT(X′)和全網(wǎng)路由表DTRT定義如下

2 抗毀路由方法與算法設(shè)計

為了有效傳輸二代導(dǎo)航星座系統(tǒng)中不同類型的各類信息,設(shè)計的基于北斗二代導(dǎo)航星座系統(tǒng)組網(wǎng)結(jié)構(gòu)的抗毀路由算法DRRA基于雙層星座、分群管理、群首備份、鏈路冗余、鏈路修補(bǔ)的組網(wǎng)結(jié)構(gòu)和管理模式,具有數(shù)據(jù)包路由抗毀、數(shù)據(jù)包路由擁塞回避、數(shù)據(jù)包路由最短延時等特點(diǎn)。

基于二代導(dǎo)航星座系統(tǒng)組網(wǎng)結(jié)構(gòu)的抗毀路由算法DRRA實(shí)現(xiàn)過程主要通過兩大步驟來完成,首先建立靜態(tài)初始路由表SORT,然后在SORT的基礎(chǔ)上增量建立動態(tài)真實(shí)路由表DTRT。

建立靜態(tài)初始路由表SORT。為了減少網(wǎng)上冗余信息,路由表計算者RTC(x)首先根據(jù)導(dǎo)航星座衛(wèi)星軌道的可預(yù)測特性和衛(wèi)星運(yùn)行的周期性,針對每一快照周期 Ts內(nèi)收集的運(yùn)行狀態(tài)信息,在系統(tǒng)T周期開始時為整個二代導(dǎo)航星座系統(tǒng)中各路徑Ps→d預(yù)先計算針對各快照周期的靜態(tài)初始路由表SOR T,并按信源節(jié)點(diǎn)s歸屬分別存儲在對應(yīng)群的各路由表計算者RTC(x)中。

建立動態(tài)真實(shí)路由表DTRT。在二代導(dǎo)航星座系統(tǒng)實(shí)際運(yùn)行的過程中,在每一快照周期Ts開始時或在某事件觸發(fā)啟動路由表更新時,各群的路由表計算者RTC(x)分別從靜態(tài)初始路由表SORT中抽取、復(fù)制對應(yīng)群成員的路由信息,再根據(jù)其收集到的來自全網(wǎng)各通信節(jié)點(diǎn)的當(dāng)前狀態(tài)信息,利用信息增量修正IIM方法,進(jìn)行增量修正,建立反映二代導(dǎo)航星座系統(tǒng)實(shí)際運(yùn)行狀態(tài)的基于邏輯群X′的動態(tài)真實(shí)路由表DTRT(X′),最后通過交換復(fù)合,形成整個二代導(dǎo)航星座系統(tǒng)的動態(tài)真實(shí)路由表DTRT中。并將DTRT(X′)分發(fā)至對應(yīng)群的各成員中。

在二代導(dǎo)航星座系統(tǒng)抗毀路由算法 DRRA中,鏈路狀態(tài)更新主要分成兩大類型:周期性更新和事件觸發(fā)更新。

2.1 信息增量修正IIM方法

根據(jù)采用快照周期和事件觸發(fā)兩種方式啟動路由表更新,信息增量修正IIM方法也設(shè)計了周期性修正與觸發(fā)性修正兩種方法:

一種是在二代導(dǎo)航星座系統(tǒng)組網(wǎng)拓?fù)浣Y(jié)構(gòu)未發(fā)生預(yù)料之內(nèi)的變化時,基于快照周期 Ts的周期性修正:在本系統(tǒng)通信網(wǎng)絡(luò)兩次快照周期Ts之間,若無通信節(jié)點(diǎn)或鏈路失效,各通信節(jié)點(diǎn)間的互連關(guān)系保持不變(基于“快照”認(rèn)為不變,實(shí)際連續(xù)變化),但鏈路流量負(fù)載的變化以及因衛(wèi)星移動引起的鏈路長度變化都將導(dǎo)致鏈路延時的動態(tài)變化,此時信息增量修正IIM方法主要是從相應(yīng)群的SORT(X′)中提取、復(fù)制針對該快照周期 Ts的SORT(X′),并對發(fā)生鏈路延時變化的鄰接節(jié)點(diǎn)根據(jù)路由表計算者RTC(x)計算新路由信息進(jìn)行針對性的修正。

另一種情況是在二代導(dǎo)航星座系統(tǒng)組網(wǎng)拓?fù)浣Y(jié)構(gòu)發(fā)生預(yù)料之內(nèi)的變化時,基于隨機(jī)事件的觸發(fā)性修正:在二代導(dǎo)航星座系統(tǒng)運(yùn)行的過程中,若網(wǎng)絡(luò)中通信節(jié)點(diǎn)或鏈路失效,其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)將隨之發(fā)生變化。通過監(jiān)視檢測網(wǎng)絡(luò)中的這種通信節(jié)點(diǎn)或鏈路失效,以此隨即觸發(fā)二代導(dǎo)航星座系統(tǒng)中的路由表更新。此時信息增量修正IIM方法從相應(yīng)群的SORT(X′)中提取、復(fù)制基于當(dāng)前快照周期Ts的SORT(X′),對因網(wǎng)絡(luò)中通信節(jié)點(diǎn)或鏈路失效引起的路由表計算者RTC(x)計算進(jìn)行引導(dǎo),通知RTC(x)只對受通信節(jié)點(diǎn)或鏈路失效影響的相關(guān)節(jié)點(diǎn)進(jìn)行路由的重計算,并將重計算的路由信息更新到提取的基于當(dāng)前快照周期 Ts的SOR T(X′)中,生成新的相關(guān)群的動態(tài)真實(shí)路由表DTRT(X′)。這樣可以使計算出的路徑不再經(jīng)過失效節(jié)點(diǎn)和鏈路,以便適應(yīng)新的網(wǎng)絡(luò)結(jié)構(gòu)。

進(jìn)行基于信息增量修正IIM方法的路由表更新時,以每個快照周期 Ts內(nèi)的靜態(tài)初始路由表SORT為基礎(chǔ),由路由表計算者RTC(x)從SORT中抽取復(fù)制建立本快照周期 Ts的屬于本群的SORT(X′),然后逐項(xiàng)搜索 SORT(X′)中每一表項(xiàng),并根據(jù)收集/交換得到的(7)式定義的全網(wǎng)狀態(tài)信息報告NetLDR檢查表項(xiàng)中路徑Ps→d上的每一鏈路lx→y狀態(tài)情況,若發(fā)生變化,RTC(x)采用一種稱為Bellman的分布式異步最短路由算法,啟動針對路徑Ps→d源節(jié)點(diǎn)s和目的節(jié)點(diǎn)d的路由重計算。對于上述第一種情況,將新路徑與原路徑不同的鏈路lx→y更新到SROT(X′)中;對于上述第二種情況,則分別將新路徑與原路徑不同的鏈路lx→y更新到SORT 和SORT(X′)中。

抗毀路由算法DRRA的實(shí)施由延時報告生成、延時報告交換、路由表計算三個過程組成。

2.2 延時報告生成

在二代導(dǎo)航星座系統(tǒng)運(yùn)行的過程中,路由表計算者RTC(x)再根據(jù)系統(tǒng)各通信節(jié)點(diǎn)在當(dāng)前快照周期收集到的狀態(tài)信息,利用信息增量修正IIM方法,在靜態(tài)初始路由表SORT路由信息的基礎(chǔ)上,抽取、復(fù)制、修正,建立反映二代導(dǎo)航星座系統(tǒng)實(shí)際運(yùn)行狀態(tài)的基于群 X′的動態(tài)真實(shí)路由表DTRT(X′),最后通過交換復(fù)合,形成整個二代導(dǎo)航星座系統(tǒng)的動態(tài)真實(shí)路由表DTRT中,包括準(zhǔn)備、初始化、延時測量、延時報告生成、延時發(fā)送等過程。

2.3 延時報告交換

群管理者GH(x)形成所屬群X′完整的群鏈路延時報告GroupLDR(X′)后,便開始在各群 X′間相互交換、復(fù)合各自形成的這些群鏈路延時報告GroupLDR(X′),以獲取整個二代導(dǎo)航星座系統(tǒng)拓?fù)浣Y(jié)構(gòu)的全部狀態(tài)信息NetLDR。

雖然延時報告的交換主要發(fā)生諸群群管理者GH(x)之間,但根據(jù)群管理者GH(x)失效與否,延時報告交換包含以下四種情況:

1)當(dāng)二代導(dǎo)航星座系統(tǒng)中GEO星座無GEO衛(wèi)星失效時,延時報告交換發(fā)生在GEO星座中諸衛(wèi)星之間。

2)當(dāng)二代導(dǎo)航星座系統(tǒng)中GEO星座存在失效衛(wèi)星(設(shè)Gi-1)時,延時報告交換發(fā)生在GEO星座中諸正常衛(wèi)星和GEO失效衛(wèi)星管理群群首衛(wèi)星H0(xi-1)之間。

在二代導(dǎo)航星座系統(tǒng)運(yùn)行的過程中,因某種原因致使GEO星座中某GEO衛(wèi)星Gi-1失效時,或因某種特定需求需要GEO星座中某GEO衛(wèi)星Gi-1關(guān)閉時,延時報告交換發(fā)生GEO星座中正常工作的GEO衛(wèi)星與失效衛(wèi)星Gi-1原管理群群首H0(xi-1)之間。為了降低延時報告交換過程中失效的GEO衛(wèi)星Gi-1對MEO星座產(chǎn)生的壓力,待失效衛(wèi)星Gi-1原管理群群首H0(xi-1)在MEO星座中完成收集群鏈路延時報告后,按最短延時路徑通過多跳星間鏈路 ISLMEO?MEO轉(zhuǎn)發(fā)至Gi和Gi-2所管理群群首H0(xi)和H0(xi-2),再由相應(yīng)群首通過單跳星際鏈路IOLMEO?GEO傳遞至相鄰群群管理者GH0(xi)和GH0(xi-2),如圖1所示。待各正常工作的GEO衛(wèi)星形成完整的整個系統(tǒng)網(wǎng)絡(luò)的鏈路延時總報告 NetLDR后,再通過逆向星際鏈路 IOLGEO?MEO將該 NetLDR 轉(zhuǎn)發(fā)至H0(xi-1),完成整個二代導(dǎo)航星座系統(tǒng)存在GEO衛(wèi)星失效情況下的鏈路延時總交換。

圖1 GEO同步星座各星間延時報告交換

3)當(dāng)二代導(dǎo)航星座系統(tǒng)中GEO星座中諸衛(wèi)星全部失效時,延時報告交換只發(fā)生在MEO星座不同群的群首之間。

在二代導(dǎo)航星座系統(tǒng)運(yùn)行的過程中,因某種原因致使GEO星座中所有GEO衛(wèi)星失效時,或應(yīng)某種特定需求需要GEO星座中所有GEO衛(wèi)星關(guān)閉時,MEO星座中各分群群首H(x)并不將形成的鏈路延時報告MLDR(X′)向原群管理者GH(x)傳遞,而是向MEO星座中與其左右相鄰的邏輯群群首按最短延時路徑通過星間鏈路ISLMEO?MEO進(jìn)行多跳轉(zhuǎn)發(fā),即延時報告交換只發(fā)生在MEO星座中各群群首H(x)之間。

4)當(dāng)二代導(dǎo)航星座系統(tǒng)中GEO星座與MEO獨(dú)立工作時,延時報告交換分別發(fā)生在GEO星座中各衛(wèi)星和MEO星座中不同群群首之間。

在二代導(dǎo)航星座系統(tǒng)分期建設(shè)的過程中,或在上述二代導(dǎo)航星座系統(tǒng)運(yùn)行過程中應(yīng)某種需求需要GEO星座與MEO星座獨(dú)立運(yùn)行時,各星座獨(dú)立進(jìn)行延時報告交換,其中GEO星座的延時報告交換按上述1)中描述的步驟進(jìn)行,MEO星座的延時報告交換按上述3)中描述的步驟進(jìn)行。

2.4 路由表計算

在二代導(dǎo)航星座系統(tǒng)中,為了降低路由表計算過程中對二代導(dǎo)航星座系統(tǒng)資源的占用率,和提高路由表計算者進(jìn)行路由決策時的計算效率[11],采用群中集中與群間分布計算相結(jié)合的方法進(jìn)行整個系統(tǒng)通信網(wǎng)絡(luò)路由表的計算與重計算,具體為:按邏輯分群由群中路由表計算者RTC(x)進(jìn)行群內(nèi)各節(jié)點(diǎn)成員路由表的統(tǒng)一集中計算,各不同群由各自的路由表計算者R TC(x)采用分布異步的方式分別計算各群(成員)的路由表。當(dāng)二代導(dǎo)航星座系統(tǒng)各星座協(xié)同工作時,網(wǎng)絡(luò)路由表計算主要由充當(dāng)群管理者的衛(wèi)星GH(x)或 H0(x)完成;在GEO星座衛(wèi)星全部失效或兩星座獨(dú)立運(yùn)行時,各星座的路由表計算由各星座獨(dú)立完成,其中MEO星座路由表計算由其中充當(dāng)群首的MEO衛(wèi)星H0(x)完成。

計算過程主要包括如下兩種情況:

1)當(dāng)二代導(dǎo)航星座系統(tǒng)中GEO星座與MEO星座協(xié)同工作時,由路由表計算者RTC(x)分別為其管理群計算全系統(tǒng)范圍內(nèi)的路由表SORT和DTRT;

2)在GEO星座衛(wèi)星全部失效或兩星座獨(dú)立運(yùn)行時,各星座的路由表DTRT計算由各星座獨(dú)立完成。

針對基于GEO/MEO雙層星座聯(lián)合組網(wǎng)的二代導(dǎo)航星座系統(tǒng),在建設(shè)初期或根據(jù)網(wǎng)絡(luò)運(yùn)行需求需要兩星座獨(dú)立運(yùn)行時,或在GEO星座衛(wèi)星全部失效時,各星座的路由表的重計算由各星座獨(dú)立完成。其中GEO星座路由表計算簡單,各GEO衛(wèi)星分別收集狀態(tài)信息并交換后調(diào)用Bellman算法進(jìn)行路由重計算。而MEO星座路由表計算則仍按分群模式管理,由其群首H0(x)充當(dāng)群管理者完成路由重計算。

3 抗毀路由算法性能分析與總結(jié)

下面主要從算法的星上計算開銷/存儲開銷和鏈路通信資源開銷的角度比較分析其實(shí)施復(fù)雜性。文獻(xiàn)[19]詳細(xì)討論了算法的星上計算開銷/星上存儲開銷以及鏈路通信資源開銷。

3.1 星上計算開銷/星上存儲開銷

為了簡明分析,設(shè)m,n分別為二代導(dǎo)航星座系統(tǒng)中GEO和MEO星座中GEO和MEO衛(wèi)星數(shù)。

通過前面對二代導(dǎo)航星座系統(tǒng)抗毀路由算法DRRA的設(shè)計描述可知,該算法的復(fù)雜性主要體現(xiàn)在全網(wǎng)鏈路狀態(tài)NetLDR更新的復(fù)雜性和路徑Ps→d計算的復(fù)雜性上,通過文獻(xiàn)[19]分析其復(fù)雜性為O(m2+m×n+n),而已有星上路由算法如SGRP、MLSR的計算復(fù)雜性為O(m2×n2),星上全分布式路由算法FDIS(Full Distributed)的計算復(fù)雜性為O((m+n)2)。與其它星上路由機(jī)制相比,由于抗毀路由算法充分利用了分層二代導(dǎo)航星座系統(tǒng)的結(jié)構(gòu)特點(diǎn),其星上計算開銷和星上存儲開銷主要由指定的具有較強(qiáng)星上處理能力的群管理者GEO衛(wèi)星和與群管理者最近的群首MEO衛(wèi)星承擔(dān),而普通衛(wèi)星節(jié)點(diǎn)的星上開銷非常低,且路由表計算者RTC(x)利用信息增量修正IIM方法只對發(fā)生狀態(tài)變化的節(jié)點(diǎn)重計算路由,未發(fā)生狀態(tài)變化的節(jié)點(diǎn)路由僅從SORT中抽取復(fù)制得到,并將狀態(tài)變化持久有效(如節(jié)點(diǎn)或鏈路失效)形成的新路由記錄至SORT中以備后用,因此單節(jié)點(diǎn)路由計算的復(fù)雜度較其它相關(guān)算法要低,因此該算法能夠較好地適用于基于分層的二代導(dǎo)航星座系統(tǒng)環(huán)境。

3.2 鏈路通信資源開銷

在基于多個星座的二代導(dǎo)航星座系統(tǒng)結(jié)構(gòu)中,各通信節(jié)點(diǎn)間的鏈路通信資源開銷也是衡量其組網(wǎng)結(jié)構(gòu)和路由算法的一項(xiàng)重要指標(biāo)。二代導(dǎo)航星座系統(tǒng)鏈路通信資源開銷與星座規(guī)模、路由更新周期、鏈路狀態(tài)更新機(jī)制等因素相關(guān)。提出的二代導(dǎo)航星座系統(tǒng)抗毀路由算法DRRA中,其鏈路狀態(tài)更新機(jī)制充分利用了GEO衛(wèi)星通信覆蓋域與MEO星座之間的覆蓋關(guān)系和各星座的運(yùn)行特點(diǎn),通過分群來實(shí)現(xiàn)分布與集中相結(jié)合的路由更新策略,使服務(wù)路由更新的鏈路狀態(tài)延時報告首先通過各分布群群中各成員x′收集,然后同期匯集到各群群首H0(x),再通過各分布群的群首H0(x)傳送至相應(yīng)群管理者GH(x),各群管理者GH(x)再全面交換形成路由計算所需的全網(wǎng)鏈路延時總報告NetLDR,從而降低網(wǎng)絡(luò)中傳送的總鏈路狀態(tài)通告數(shù)目。

4 結(jié) 論

提出了一種適應(yīng)二代導(dǎo)航星座系統(tǒng)組網(wǎng)結(jié)構(gòu)的抗毀路由算法DRRA,與其它星上路由機(jī)制相比,該算法具有計算復(fù)雜度相對較低、存儲容量相對較小、支持衛(wèi)星節(jié)點(diǎn)失效運(yùn)行的特點(diǎn)和功能。這主要基于:

1)二代導(dǎo)航星座系統(tǒng)中通信節(jié)點(diǎn)間鏈路冗余設(shè)計方案;

2)二代導(dǎo)航星座系統(tǒng)中通信節(jié)點(diǎn)失效時間隔失效節(jié)點(diǎn)視距范圍內(nèi)次相鄰節(jié)點(diǎn)鏈路修補(bǔ)方案;

3)MEO星座分群群首失效時采用群首選擇備份機(jī)制;

4)二代導(dǎo)航星座系統(tǒng)中分群群管理者失效時采用群首兼容群管理者功能的角色擴(kuò)充機(jī)制。另外較其它相關(guān)算法而言,提出的路由算法在計算/存儲復(fù)雜度以及通信資源占用率和數(shù)據(jù)包路由最短延時等方面具有優(yōu)勢,這主要基于提出:

1)基于GEO通信覆蓋域的MEO星座分群管理機(jī)制;

2)通過分群來實(shí)現(xiàn)分布與集中相結(jié)合的路由更新策略;

3)基于狀態(tài)更新的信息增量修正路由計算方法;

4)二代導(dǎo)航星座系統(tǒng)中通信節(jié)點(diǎn)間鏈路冗余設(shè)計方案。

[1]Werner M,Delucchi C.ATM virtual path routing for LEO/MEO satellite networks with intersatellite links[C]//Satellite Systems for Mobile Communications and Navigation,1996,Fifth International Conference on,London,1996:143-146.

[2]Werner M.A Dynamic Routing Concept for ATMBased Satellite Persona1 Communication Networks[J].IEEE Journa1 on Selected Areas in Communications,1997,15(8):1639-1648.

[3]Chang K L,Chang H,Kim W,et a1.Topological Design and Routing for Low-Earth Orbit Satellite Networks[C]//Proc.of IEEE GLOBECOM,1995:529-535.

[4]Gounder V V,Prakash R,Abu-Anlara H.Routing in LEO-based satellite networks[C]//Proc.of IEEE E-merging Technologies Symp.Wireless Communications and Systems,1999(22):1-22,6.

[5]Chang H S,Kim B W,lee G G,et a1.FSA-based link assignment and routing in low-Earth orbit satellite networks[J].IEEE Transactions on Vehicular Technology,1998,47(3):1037-1048.

[6]Werner W,Berndl G,Edmaier B.Performance of optimized routing in LEO intersatellite link networks[C]//Proc.of IEEE 47th VehicularTechnology Conference,1997(1):246-250.

[7]Ekici E,Akyildiz I F,Bender M D.A distributed routing algorithm for datagram traffic in LEO satellite networks[J].IEEE/ACM Transaction on Networking,2001,9(2):137-147.

[8]Lo M W.Satellite constellation design[J].IEEE Computing in Science and Engineering,1999,1(1):58-67.

[9]Chen C,Ekici E.A routing protocol for hierarchical LEO/MEOsatellite IP networks[J].ACM/Kluwer Wireless Networks(WINET),2005:507-521.

[10]Chen C,Ekici E,Akyildiz I F.Satellite Grouping and Routing Protocol for LEO/MEO Satellite IP Networks[C]//Proc.of the Fifth International ACM Workshop on Wireless M obile Multimedia,2002:109-116.

[11]Akyildiz I F,Ekici E,Bender M D.M LSR:A novel routing algorithm for multi-layered satellite IP networks[J].IEEE/ACM Transaction on Networking,2002,10(3):411-424.

[12]China National Administration of GNSS.COMPASS and Its Applications in Life Relief.[C]//Proc.of theUnited Nations/Azerbaijan/United States of America/European Space Agency Workshop on the Applications of Global Navigation Satellite Systems,Baku,Azerbaijan,2009.

[13]China Satellite Navigation Project Center.COMPASS/BeiDou Navigation Satellite System Development[C]//Proc.of the The 4th Meeting of International Committee on GNSS,Saint Petersburg Russia,2009.

[14]Sun H W,Li Z G,Ping F.Development of Satellite Navigation in China[C]//Proc.of the Frequency Control Symposium,2007 Joint with the 21st European Frequency and Time Forum IEEE International,2007.

[15]China National Administration of GNSS.Applications and Development and Applications of Compass/Beidou Satellite Navigation System[C]//Proc.of the International Committee on GNSS 2009(IGNSS2009),Gold Coast Australia,2009.

[16]Maine K P,Anderson P,Langer J.Crosslinks for the next-generation GPS[C]//the Aerospace Conference,2003.Proceedings of 2003 IEEE,2003(4):1589-1596.

[17]譚述森.北斗衛(wèi)星導(dǎo)航系統(tǒng)的發(fā)展與思考[J].宇航學(xué)報,2008,29(2):391-396.

[18]童 鎧.衛(wèi)星導(dǎo)航系統(tǒng)在我國的應(yīng)用與發(fā)展[J].國際太空,2004,(1):4-8.

[19]易先清,馮明月,趙 陽,羅雪山.一種基于GEO/MEO星層組網(wǎng)的衛(wèi)星網(wǎng)絡(luò)抗毀路由研究[J].計算機(jī)科學(xué),2007,34(8):74-82.