張景斌劉炯申普兵（西安通信學(xué)院，西安 7006）（2 7332部隊(duì)，漳州 363）

一種基于等長時(shí)隙劃分雙層衛(wèi)星網(wǎng)絡(luò)路由算法

張景斌1，2劉炯1申普兵1
（1西安通信學(xué)院，西安 710106）（2 73132部隊(duì)，漳州 363111）

針對(duì)網(wǎng)絡(luò)拓?fù)鋾r(shí)變和鏈路頻繁切換影響衛(wèi)星網(wǎng)絡(luò)路由性能的問題，采用“骨干／接入”和“弱連接”思想，構(gòu)建雙層衛(wèi)星網(wǎng)絡(luò)，實(shí)現(xiàn)地球靜止軌道衛(wèi)星（GEO）與低軌道衛(wèi)星（LEO）各層的分開管理。在此基礎(chǔ)上，通過動(dòng)態(tài)調(diào)整極區(qū)邊界值，進(jìn)行系統(tǒng)周期的平均劃分，提出了適合于雙層衛(wèi)星網(wǎng)絡(luò)的等長時(shí)隙快照和星上分布式路由算法（Equal－length Interval Snapshots and On－board Distributed Routing Algorithm，EDRA）。分析和仿真驗(yàn)證表明，這種“骨干／接入”的雙層衛(wèi)星網(wǎng)絡(luò)架構(gòu)更加合理，EDRA算法劃分的時(shí)隙數(shù)量僅為時(shí)間虛擬化和分層管理的路由算法（Virtualized Time and Layered Management Routing Algorithm，VLRA）的一半，平均時(shí)隙長度則為VLRA的3倍以上，減少了路由計(jì)算與更新的次數(shù)，提高了網(wǎng)絡(luò)鏈路利用率，并且端到端時(shí)延抖動(dòng)小，數(shù)據(jù)丟包率低，更加適合于衛(wèi)星網(wǎng)絡(luò)中應(yīng)用。

地球靜止軌道衛(wèi)星／低軌道衛(wèi)星雙層衛(wèi)星網(wǎng)絡(luò)；等長時(shí)隙劃分；星上分布式路由算法；動(dòng)態(tài)極區(qū)邊界值；仿真

1 引言

路由技術(shù)是衛(wèi)星網(wǎng)絡(luò)應(yīng)用的關(guān)鍵技術(shù)之一，決定著整個(gè)衛(wèi)星網(wǎng)絡(luò)系統(tǒng)效率和可靠性。在衛(wèi)星網(wǎng)絡(luò)中，衛(wèi)星之間相對(duì)高速移動(dòng)使得網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)周期性頻繁變化，同時(shí)星間通信鏈路隨著兩顆終端衛(wèi)星距離和方位角的變化而頻繁切換，使得網(wǎng)絡(luò)中的分組數(shù)據(jù)傳輸與交換質(zhì)量難以保證［1］。因此，在設(shè)計(jì)衛(wèi)星網(wǎng)絡(luò)路由算法時(shí)必須首先解決網(wǎng)絡(luò)拓?fù)鋾r(shí)變和鏈路頻繁切換問題。

近年來國內(nèi)外針對(duì)衛(wèi)星網(wǎng)絡(luò)拓?fù)鋾r(shí)變和鏈路頻繁切換問題提出了多種路由算法和實(shí)現(xiàn)策略，根據(jù)其基本思想可分為動(dòng)態(tài)拓?fù)渎酚?、虛擬節(jié)點(diǎn)路由和虛擬拓?fù)渎酚扇箢?。?dòng)態(tài)拓?fù)渎酚苫舅枷胧遣捎脭?shù)據(jù)包自動(dòng)尋址的方式，依據(jù)實(shí)時(shí)衛(wèi)星網(wǎng)絡(luò)拓?fù)溥M(jìn)行路由計(jì)算［2］。虛擬節(jié)點(diǎn)路由基本思想是將衛(wèi)星網(wǎng)絡(luò)模型化為拓?fù)涔潭ǖ奶摂M衛(wèi)星節(jié)點(diǎn)進(jìn)行路由計(jì)算［3］。虛擬拓?fù)渎酚苫舅枷胧抢眯l(wèi)星網(wǎng)絡(luò)的周期性和可預(yù)測(cè)性，將星座周期劃分為若干時(shí)間段，每個(gè)時(shí)間段內(nèi)星座拓?fù)淇梢暈楣潭ú蛔?，稱為拓?fù)淇煺栈蛘邥r(shí)隙，從而利用拓?fù)淇煺諡楦餍l(wèi)星節(jié)點(diǎn)分段計(jì)算路由［4］。

在多層衛(wèi)星網(wǎng)絡(luò)中，研究較多的是虛擬拓?fù)渎酚桑鋺?yīng)用基礎(chǔ)和前提是時(shí)隙劃分。目前時(shí)隙劃分方法研究較多，概括起來可分為不等長時(shí)隙劃分和等長時(shí)隙劃分兩類方法。前者依據(jù)網(wǎng)絡(luò)拓?fù)渥兓蛐请H鏈路切換劃分系統(tǒng)周期，文獻(xiàn)［5］針對(duì)三層衛(wèi)星網(wǎng)絡(luò)提出了具體時(shí)隙優(yōu)化方法，文獻(xiàn)［6］針對(duì)時(shí)間段長度較小帶來的路由收斂問題，提出了具體路由策略；后者依據(jù)衛(wèi)星覆蓋區(qū)域變化或其他約束條件來劃分系統(tǒng)周期，文獻(xiàn)［7］針對(duì)12顆星的Walker Delta星座提出了一種時(shí)隙劃分方法，文獻(xiàn)［8］則將鏈路利用率作為約束條件進(jìn)行等長時(shí)隙劃分。雖然對(duì)于這兩類時(shí)隙劃分方法，國內(nèi)外已經(jīng)開展了大量研究工作，但所提出的具體實(shí)現(xiàn)方法都受到極區(qū)邊界參數(shù)的影響，仍然面臨極區(qū)邊界時(shí)隙內(nèi)部分通信鏈路將會(huì)中斷、分組數(shù)據(jù)丟失的問題［8－10］。

2 GEO／LEO雙層衛(wèi)星網(wǎng)絡(luò)體系架構(gòu)介紹

本文研究的GEO／LEO雙層衛(wèi)星網(wǎng)絡(luò)體系架構(gòu)如圖1所示，該體系架構(gòu)由GEO星座、LEO星座以及地面系統(tǒng)組成。

圖1 GEO／LEO雙層衛(wèi)星網(wǎng)絡(luò)體系架構(gòu)Fig.1 Structure of GEO／LEO double－layered satellite constellation network

為克服多層衛(wèi)星網(wǎng)絡(luò)中互聯(lián)關(guān)系復(fù)雜、設(shè)計(jì)難度高等問題，GEO／LEO雙層衛(wèi)星網(wǎng)絡(luò)體系架構(gòu)采用“骨干／接入”模型［11］，即GEO層星座構(gòu)成骨干網(wǎng)，LEO層星座構(gòu)成接入網(wǎng)；為降低網(wǎng)絡(luò)拓?fù)鋸?fù)雜度，減少鏈路切換頻率，GEO／LEO雙層衛(wèi)星網(wǎng)絡(luò)層間鏈路設(shè)計(jì)采用“弱連接”思想［12］，即某一時(shí)刻，每顆LEO衛(wèi)星只與覆蓋它的上層GEO衛(wèi)星中通信質(zhì)量最優(yōu)的一顆建立連接關(guān)系。

GEO星座作為骨干層，由均勻分布在赤道上空的NG顆GEO衛(wèi)星構(gòu)成，采用多波束星下天線，可實(shí)現(xiàn)中低緯度區(qū)域全覆蓋。GEO星座承擔(dān)衛(wèi)星網(wǎng)絡(luò)的路由計(jì)算、狀態(tài)監(jiān)控、LEO衛(wèi)星管理等任務(wù)；當(dāng)管理組內(nèi)LEO衛(wèi)星負(fù)荷較重時(shí)，為其分擔(dān)部分非實(shí)時(shí)數(shù)據(jù)業(yè)務(wù)，以緩解LEO層流量負(fù)載；當(dāng)管理組內(nèi)LEO衛(wèi)星失效時(shí)，臨時(shí)替代失效衛(wèi)星，以提高網(wǎng)絡(luò)抗毀性能。用k對(duì)GEO衛(wèi)星進(jìn)行編號(hào)，k＝1，2，…，NG。

LEO星座作為接入層，由ML個(gè)等經(jīng)度間隔分布的軌道平面構(gòu)成，每個(gè)軌道包含NL顆均勻分布的類極軌道LEO衛(wèi)星，滿足理論上的全球覆蓋要求。LEO衛(wèi)星承擔(dān)地面網(wǎng)關(guān)及終端用戶接入、信息傳輸與交換、鏈路狀態(tài)信息收集等任務(wù)，并接受GEO層衛(wèi)星管理。為提高網(wǎng)絡(luò)抗毀性和業(yè)務(wù)傳輸能力，體系架構(gòu)中LEO衛(wèi)星具有軌內(nèi)、軌間星際鏈路。用（i，j）對(duì)LEO衛(wèi)星進(jìn)行編號(hào)，i表示軌道號(hào)，i＝1，2，…，ML；j表示單條軌道內(nèi)LEO衛(wèi)星號(hào)，j＝1，2，…，NL。

地面系統(tǒng)主要包括地面控制中心、地面網(wǎng)關(guān)和終端用戶等。其中地面控制中心通過GEO層對(duì)整個(gè)衛(wèi)星網(wǎng)絡(luò)進(jìn)行監(jiān)控，可通過注入功能修改或控制GEO層的管理模式，以適應(yīng)技術(shù)發(fā)展和應(yīng)用需求的實(shí)時(shí)變化；終端用戶可直接接入衛(wèi)星網(wǎng)絡(luò)；陸基、空基等其他網(wǎng)絡(luò)用戶可通過地面網(wǎng)關(guān)接入衛(wèi)星網(wǎng)絡(luò)。

GEO／LEO雙層衛(wèi)星網(wǎng)絡(luò)中包含三種全雙工通信鏈路：1）同層衛(wèi)星之間的星間鏈路（Inter Satellite Link，ISL），具體又分為軌內(nèi)ISL（同一軌道內(nèi)兩顆相鄰衛(wèi)星間的星間鏈路）和軌間ISL（相鄰軌道相鄰衛(wèi)星間的星間鏈路）；2）不同層衛(wèi)星之間的層間鏈路（Inter Orbit Link，IOL）；3）地面系統(tǒng)與衛(wèi)星網(wǎng)絡(luò)之間的用戶數(shù)據(jù)鏈路（User Data Link，UDL）。

3 GEO／LEO雙層衛(wèi)星網(wǎng)絡(luò)的路由算法

3.1 基于動(dòng)態(tài)極區(qū)邊界值等長時(shí)隙劃分

圖2 GEO／LEO雙層衛(wèi)星網(wǎng)絡(luò)極區(qū)邊界值Fig.2 Polar boundar of GEO／LEO double－layered satellite constellation network

在本文研究的GEO／LEO雙層衛(wèi)星網(wǎng)絡(luò)中，GEO衛(wèi)星相對(duì)地面固定不變，網(wǎng)絡(luò)拓?fù)渥兓饕蒐EO衛(wèi)星進(jìn)入或者離開GEO層星座覆蓋域所引起的，極區(qū)邊界值β如圖2所示，由LEO衛(wèi)星的LEO－GEO最小仰角Emin和軌道高度HL共同決定。

圖2中，RE為地球半徑，HL為LEO衛(wèi)星高度，HG為GEO衛(wèi)星高度，Emin為LEO－GEO的最小仰角。

由余弦定理和正弦定理可求得極區(qū)邊界值：

采用等長時(shí)隙劃分方法時(shí)，時(shí)隙越長，星座系統(tǒng)周期內(nèi)拓?fù)淇煺諗?shù)量就越少，星上存儲(chǔ)開銷和路由計(jì)算開銷就越低。極軌道星座平面示意如圖3所示，其中，Pi、Pi＋1為相鄰軌道，β為極區(qū)邊界值（一般用弧度表示），NL為單條軌道上衛(wèi)星數(shù)量，相鄰軌道間相鄰衛(wèi)星之間相位差為ΔΩ＝π／NL。由文獻(xiàn)［9］可知，極軌道星座最大時(shí)隙長度為Δt＝T／2 NL。為降低系統(tǒng)開銷，本文選取時(shí)隙長度取最大長度Δt，將GEO／LEO雙層星座系統(tǒng)周期劃分為2 NL個(gè)等長拓?fù)淇煺?，LEO衛(wèi)星在單個(gè)時(shí)隙內(nèi)相位移動(dòng)π／NL。

由公式（1）可知，當(dāng)GEO／LEO雙層星座參數(shù)固定之后，其極區(qū)邊界值也隨即固定。在極軌道星座中，當(dāng)衛(wèi)星進(jìn)入極區(qū)時(shí)將關(guān)閉軌間ISL，采用等長時(shí)隙劃分的路由算法，時(shí)隙越長，時(shí)隙內(nèi)路徑失效概率越大。為此，本文給出一種基于動(dòng)態(tài)極區(qū)邊界值的等長時(shí)隙劃分方法，即通過調(diào)整極區(qū)邊界值，在每個(gè)拓?fù)淇煺掌鹗紩r(shí)刻關(guān)閉即將進(jìn)入極區(qū)的LEO衛(wèi)星的軌間ISL，使得時(shí)隙內(nèi)不會(huì)發(fā)生鏈路切換，計(jì)算所得的路徑不會(huì)失效。

GEO衛(wèi)星覆蓋域和極區(qū)示意如圖4所示，其中，β′≤β為動(dòng)態(tài)調(diào)整后的極區(qū)邊界值。調(diào)整后LEO衛(wèi)星在GEO衛(wèi)星覆蓋域和極區(qū)內(nèi)經(jīng)歷相位恰好為相鄰軌道相鄰衛(wèi)星相位差ΔΩ的X、Y倍，X、Y均為正整數(shù)，且X值取最大值。因此，當(dāng)LEO衛(wèi)星Li，j運(yùn)行到極區(qū)邊界時(shí)，其相同軌道上的（當(dāng)NL為偶數(shù)時(shí)）或者相鄰軌道上的（當(dāng)NL為奇數(shù)時(shí)）恰好運(yùn)行到相對(duì)稱的極區(qū)邊界上。綜上可得：

圖3 極軌道星座平面示意Fig.3 2－D figure of polar orbit satellite constellation

圖4 GEO衛(wèi)星覆蓋域和極區(qū)示意Fig.4 Coverage area and ploar area of GEO satellite

整理公式（2）可得調(diào)整后的極區(qū)邊界值為

EDRA算法通過動(dòng)態(tài)調(diào)整極區(qū)邊界值，在路由起始時(shí)刻關(guān)閉即將進(jìn)入極區(qū)衛(wèi)星的軌間ISL，造成了部分網(wǎng)絡(luò)鏈路資源的浪費(fèi)。設(shè)L（Δt）為極區(qū)邊界值調(diào)整后單個(gè)時(shí)隙內(nèi)連通的鏈路數(shù)量，Lc為調(diào)整前單個(gè)時(shí)隙內(nèi)連通的鏈路數(shù)量，則網(wǎng)絡(luò)鏈路利用率U＝L（Δt）／Lc。

設(shè)LEO星座中衛(wèi)星總數(shù)為N，軌道面數(shù)為p。在極軌道星座中，由于軌間ISL在緯度線上均勻分布，且反向縫兩側(cè)衛(wèi)星高速運(yùn)動(dòng)，不建立軌間ISL，所以：

綜上，EDRA算法等長劃分的時(shí)隙長度已取得最大值，單個(gè)時(shí)隙內(nèi)路徑變化較小，便于路由優(yōu)化與計(jì)算，節(jié)省了星上存儲(chǔ)空間；通過動(dòng)態(tài)調(diào)整極區(qū)邊界值，使得時(shí)隙內(nèi)無鏈路切換，保證了時(shí)隙內(nèi)網(wǎng)絡(luò)拓?fù)涞姆€(wěn)定；另外所劃分的時(shí)隙長度均等，便于整個(gè)衛(wèi)星網(wǎng)絡(luò)的管理與控制。

圖5 路由計(jì)算與更新流程Fig.5 Flow diagram of routing calculation and updation

3.2 星上路由計(jì)算與更新

按照路由計(jì)算承擔(dān)對(duì)象，虛擬拓?fù)渎酚煽煞譃榛诘孛婢W(wǎng)關(guān)的離線式路由和基于星上分布式路由。由于離線式路由存在突發(fā)情況處置能力差、拓?fù)錉顟B(tài)收集時(shí)間長、特殊時(shí)期地面網(wǎng)關(guān)易被摧毀等問題，為提高GEO／LEO雙層衛(wèi)星網(wǎng)絡(luò)路由算法的魯棒性、縮短路由收斂時(shí)間，本文采用星上分布式路由算法。在每個(gè)時(shí)隙起始時(shí)刻，衛(wèi)星網(wǎng)絡(luò)收集鏈路狀態(tài)信息（LMR），進(jìn)行路由計(jì)算和更新。路由計(jì)算與更新流程如圖5所示。

具體步驟可描述為：

步驟1）GEO衛(wèi)星下達(dá)LMR收集指令。

步驟2）LEO衛(wèi)星LMR的生成。

LEO衛(wèi)星Li，j測(cè)量自身出口鏈路狀態(tài)信息，生成LMR（Li，j）。LEO衛(wèi)星的出口鏈路主要包括：與地面站相連的UDL、與相鄰LEO衛(wèi)星相連的ISL、與管理衛(wèi)星GEO相連的IOL。由此可得：

式中 A表示Li，j衛(wèi)星從編號(hào)0到編號(hào)ST（Li，j）－1的所有時(shí)隙；B表示所屬管理衛(wèi)星Gk下，Li，j衛(wèi)星k0到k3與相鄰衛(wèi)星的4條連接鏈路，k為GEO管理衛(wèi)星編號(hào)，即Gk；C表示Li，j衛(wèi)星與管理衛(wèi)星GEO的連接鏈路。

步驟3）LEO衛(wèi)星LMR的傳播。

LEO衛(wèi)星生成LMR（Li，j）后，經(jīng)IOL報(bào)告給其管理衛(wèi)星Gk。GEO衛(wèi)星Gk等待時(shí)間δ，若在時(shí)間δ內(nèi)收到LMR（Li，j）數(shù)量與管理組成員數(shù)量相等，轉(zhuǎn)步驟4）；否則Gk向地面控制中心發(fā)送衛(wèi)星節(jié)點(diǎn)失效報(bào)告alert（Y），并轉(zhuǎn)步驟4）。

步驟4）GEO衛(wèi)星LMR的生成。

GEO衛(wèi)星Gk在時(shí)隙起始時(shí)刻測(cè)量自身出口鏈路狀態(tài)信息，生成LMR（Gk）。

步驟5）鏈路狀態(tài)信息庫的生成。

GEO衛(wèi)星將收集到的組內(nèi)成員LMR和自身LMR在GEO層內(nèi)洪泛?NG／2」次，即按照NG／2的取整計(jì)算結(jié)果來設(shè)置洪泛次數(shù)。至此，GEO星座生成整個(gè)網(wǎng)絡(luò)的鏈路狀態(tài)信息庫，記為LMRw。

步驟6）LEO衛(wèi)星原始路由表的計(jì)算。

GEO星座根據(jù)LMRw為GEO／LEO雙層衛(wèi)星網(wǎng)絡(luò)計(jì)算路由。GEO衛(wèi)星Gk以路徑總時(shí)延為優(yōu)化目標(biāo)，利用Dijkstra算法，為管理組內(nèi)每顆LEO衛(wèi)星計(jì)算其到其余所有LEO衛(wèi)星的最優(yōu)路徑和次優(yōu)路徑，將計(jì)算結(jié)果添加到LEO衛(wèi)星原始路由表LOT（Gk｜X）中。

步驟7）GEO衛(wèi)星路由轉(zhuǎn)發(fā)表的計(jì)算。

GEO衛(wèi)星Gk依據(jù)LMRw，以最小節(jié)點(diǎn)跳數(shù)為優(yōu)化目標(biāo)，采用貝爾曼（Bellman）算法，為自身計(jì)算其到所有LEO／GEO衛(wèi)星的最優(yōu)路徑，將計(jì)算結(jié)果添加到GEO衛(wèi)星路由轉(zhuǎn)發(fā)表GRT（Gk）中。

GEO衛(wèi)星Gk將其生成的LOT和GRT匯總并發(fā)送到地面控制中心備份。

步驟9）LEO衛(wèi)星路由轉(zhuǎn)發(fā)表的生成與分發(fā)。

GEO衛(wèi)星Gk依據(jù)LOT（Gk｜X）為管理組每顆LEO衛(wèi)星生成其到目的節(jié)點(diǎn)的最優(yōu)下一跳、次優(yōu)下一跳，生成LEO衛(wèi)星路由轉(zhuǎn)發(fā)表LRT（X），并分發(fā)至相應(yīng)的LEO衛(wèi)星。LEO衛(wèi)星路由轉(zhuǎn)發(fā)表LRT（X）主要包括：路由源節(jié)點(diǎn)、路由目的節(jié)點(diǎn)、最優(yōu)下一跳、次優(yōu)下一跳等信息。

步驟10）GEO／LEO雙層衛(wèi)星網(wǎng)絡(luò)依據(jù)LRT（X）和GRT進(jìn)行信息傳輸與交換。

GEO／LEO雙層衛(wèi)星網(wǎng)絡(luò)在每個(gè)時(shí)隙起始時(shí)刻進(jìn)行一次路由計(jì)算與更新。EDRA算法在GEO星座中直接生成鏈路狀態(tài)信息庫，并依此進(jìn)行路由計(jì)算與更新，縮短了路由收斂時(shí)間、提高了整個(gè)網(wǎng)絡(luò)抗毀性能；在LEO星座中每個(gè)節(jié)點(diǎn)只需保存一個(gè)本節(jié)點(diǎn)的路由轉(zhuǎn)發(fā)表，對(duì)星上存儲(chǔ)開銷需求較低。

衛(wèi)星網(wǎng)絡(luò)中由于流量負(fù)載分布不均，極易發(fā)生鏈路擁塞、節(jié)點(diǎn)失效等突發(fā)情況。EDRA算法為每顆LEO衛(wèi)星分別計(jì)算了到達(dá)目的節(jié)點(diǎn)的最優(yōu)路徑和次優(yōu)路徑，當(dāng)?shù)竭_(dá)最優(yōu)下一跳的鏈路利用率達(dá)到閾值時(shí)，當(dāng)前節(jié)點(diǎn)選擇次優(yōu)下一跳轉(zhuǎn)發(fā)分組數(shù)據(jù)；如果到達(dá)次優(yōu)下一跳的鏈路利用率也達(dá)到閾值時(shí)，當(dāng)前節(jié)點(diǎn)將分組數(shù)據(jù)轉(zhuǎn)交其GEO管理衛(wèi)星進(jìn)行轉(zhuǎn)發(fā)，并觸發(fā)一次路由計(jì)算與更新。當(dāng)最優(yōu)下一跳節(jié)點(diǎn)失效時(shí)，當(dāng)前節(jié)點(diǎn)選擇次優(yōu)下一跳轉(zhuǎn)發(fā)分組數(shù)據(jù)；如果次優(yōu)下一跳節(jié)點(diǎn)也失效時(shí)，當(dāng)前節(jié)點(diǎn)將分組數(shù)據(jù)轉(zhuǎn)交其GEO管理衛(wèi)星進(jìn)行轉(zhuǎn)發(fā)，并觸發(fā)一次路由計(jì)算與更新。

4 仿真與性能分析

首先，建立GEO／LEO雙層衛(wèi)星網(wǎng)絡(luò)仿真模型，計(jì)算網(wǎng)絡(luò)拓?fù)潆x散化后的時(shí)隙；然后通過NS2仿真軟件測(cè)試EDRA算法性能，分別與衛(wèi)星群組和路由協(xié)議（Satellite Grouping and Routing Protocl，SGRP）算法、Dijkstra算法比較不同鏈路利用率下端到端時(shí)延和網(wǎng)絡(luò)丟包率。

4.1 星座仿真與時(shí)隙劃分

表1 雙層衛(wèi)星網(wǎng)絡(luò)星座參數(shù)Tab.1 Parameters of double－layered satellite constellation network

使用STK仿真工具構(gòu)建GEO／LEO雙層衛(wèi)星網(wǎng)絡(luò)仿真模型，星座參數(shù)如表1所示，GEO星座采用等經(jīng)度間隔、均勻分布的4顆GEO衛(wèi)星；LEO星座采用類Iridium星座結(jié)構(gòu)。設(shè)LEO－GEO最小仰角Emin＝10°，則由公式（2）可得極區(qū)邊界值β＝74.62°，由公式（3）可得調(diào)整后極區(qū)邊界值β′＝70°。

我的畫：有位畫家說過，“好的繪畫在你面前是往后退的?！倍嗄甑睦L畫實(shí)踐更明白了其中的道理。優(yōu)秀的繪畫呈現(xiàn)的是一種整體的氛圍，吸引你去感受畫面背后的一種精神性的東西，而不是停留在表面的技法、色彩等物質(zhì)性上。精神性的呈現(xiàn)，需要你對(duì)物的持續(xù)關(guān)注和體驗(yàn)，才能在最為熟悉的物上得到靈感。因此我畫身邊的人與物，通過和諧的色調(diào)，細(xì)膩的手法，書寫的筆意，努力營造畫面的氛圍，給物以升華，如同打開一扇窗。

（1）與優(yōu)化后的不等長時(shí)隙劃分方法比較

分別采用文獻(xiàn)［6］中的VLRA算法和EDRA算法對(duì)該星座模型進(jìn)行時(shí)隙劃分，以24h為一個(gè)運(yùn)行周期，時(shí)隙劃分結(jié)果如圖6所示。由于VLRA時(shí)隙劃分非常密集，并且時(shí)隙并不相等，圖6（a）中呈現(xiàn)黑色陰影；EDRA則時(shí)隙劃分相對(duì)寬松，并且時(shí)隙相等。

圖6 時(shí)隙劃分結(jié)果比較Fig.6 Interval snapshot results of two algorithms

與VLRA相比，采用EDRA劃分時(shí)隙，時(shí)隙個(gè)數(shù)由774個(gè)減少到了234個(gè)，平均時(shí)隙長度由111.796 2s增加到了368.222 2s，明顯減少了運(yùn)行周期內(nèi)路由計(jì)算與更新次數(shù)，延長了路由持續(xù)時(shí)間，且時(shí)隙內(nèi)無鏈路切換，保證了網(wǎng)絡(luò)拓?fù)涞姆€(wěn)定性。

（2）與優(yōu)化后的等長時(shí)隙劃分方法比較

當(dāng)采用文獻(xiàn)［8］中以網(wǎng)絡(luò)鏈路利用率為約束條件的等長時(shí)隙劃分方法時(shí)，由文獻(xiàn)［8］中公式（5）可得，網(wǎng)絡(luò)鏈路利用率為95%時(shí)，等長時(shí)隙長度上限為298.34s；而采用EDRA等長時(shí)隙劃分時(shí)，等長時(shí)隙長度為368.222 2s，由本文中公式（4）可得此時(shí)網(wǎng)絡(luò)鏈路利用率U＝97.52%。因此，與文獻(xiàn)［8］相比，EDRA算法路由持續(xù)時(shí)間更長，網(wǎng)絡(luò)鏈路利用率更高。

4.2 路由算法性能分析與比較

根據(jù)表1的星座參數(shù)，選取NS2仿真軟件分別完成EDRA、SGRP和Dijkstra三種算法端到端時(shí)延特性和網(wǎng)絡(luò)丟包率仿真試驗(yàn)。在Dijkstra算法中，假設(shè)每個(gè)節(jié)點(diǎn)均知道整個(gè)衛(wèi)星網(wǎng)絡(luò)拓?fù)?，鏈路狀態(tài)實(shí)時(shí)更新，實(shí)際上是一種沒有協(xié)議開銷的理想最優(yōu)路由算法，是路由算法性能的極限。所有地面站均通過LEO星座接入衛(wèi)星網(wǎng)絡(luò)，最小仰角為10°，網(wǎng)絡(luò)中所有通信鏈路均設(shè)置為20Mbit。仿真中設(shè)置了北京（東經(jīng)116.5°，北緯39.9°）作為源端節(jié)點(diǎn)；紐約（西經(jīng)74.1°，北緯40.7°）作為目的節(jié)點(diǎn)。

為比較三種路由協(xié)議在不同鏈路利用率下的性能，在LEO衛(wèi)星上設(shè)置一個(gè)速率服從指數(shù)分布、平均值為λ的背景流量，逐步增大λ可使得LEO衛(wèi)星鏈路利用率逐漸增加。

圖7 平均端到端時(shí)延特性比較Fig.7 Results of average end－to－end delay

（1）端到端時(shí)延特性仿真

仿真中，選取北京到紐約這一對(duì)地面站作為觀察節(jié)點(diǎn)，由北京站向紐約站發(fā)送一個(gè)持續(xù)時(shí)間為60min、平均速率為8Mbit／s的分組數(shù)據(jù)流量，逐漸增大鏈路負(fù)載，重復(fù)仿真10次。對(duì)于每一個(gè)平均鏈路負(fù)載值，端到端時(shí)延均取10次仿真的平均值，仿真結(jié)果如圖7所示。

由圖7可知，Dijkstra端到端時(shí)延幾乎不變；SGRP端到端時(shí)延在鏈路利用率高于60%時(shí)急劇增長；EDRA端到端時(shí)延在鏈路利用率達(dá)到60%時(shí)繼續(xù)平緩增長；在鏈路利用率低于60%時(shí)，SGRP和EDRA端到端時(shí)延相差不大，與Dijkstra相差大約4ms。分析原因主要有：

1）在鏈路利用率低于60%時(shí)，SGRP和EDRA與Dijkstra端到端時(shí)延差值主要為路由計(jì)算和星上分組處理時(shí)間；

2）SGRP無擁塞回避機(jī)制，在鏈路利用率高于60%時(shí)，端到端時(shí)延增加部分主要為排隊(duì)時(shí)延與處理時(shí)延；而EDRA具有擁塞回避機(jī)制，在最優(yōu)鏈路利用率過高時(shí)，可通過次優(yōu)路徑和GEO衛(wèi)星進(jìn)行分流，在鏈路利用率60%時(shí)出現(xiàn)的“臺(tái)階”，主要為選擇次優(yōu)路徑而增加的部分傳輸時(shí)延。

另外，在仿真中，Dijkstra算法的實(shí)現(xiàn)采用理想方式，即假設(shè)每個(gè)節(jié)點(diǎn)均知道整個(gè)衛(wèi)星網(wǎng)絡(luò)拓?fù)?，所以沒有鏈路數(shù)據(jù)開銷；SGRP算法無擁塞回避機(jī)制，無論鏈路處于什么狀態(tài)，其鏈路開銷僅與時(shí)隙數(shù)量有關(guān)，其鏈路開銷為2.4kbit／s；EDRA算法采用了擁塞回避機(jī)制，當(dāng)鏈路利用率低于60%時(shí)，鏈路開銷僅為0.8kbit／s，當(dāng)鏈路利用率高于60%時(shí)，由于需要進(jìn)行次優(yōu)鏈路搜索，鏈路開銷增大為1.1kbit／s。

圖8 網(wǎng)絡(luò)丟包率比較Fig.8 Packet loss rate in satellite networks

（2）網(wǎng)絡(luò)丟包率仿真

仿真中，同樣選取北京到紐約這一對(duì)地面站作為觀察節(jié)點(diǎn)。由北京站向紐約站發(fā)送一個(gè)持續(xù)時(shí)間為60min、平均速率為8Mbit／s的分組數(shù)據(jù)流量，逐漸增大鏈路負(fù)載，重復(fù)仿真10次。對(duì)于每一個(gè)平均鏈路負(fù)載值，網(wǎng)絡(luò)丟包率均取10次仿真的平均值，仿真結(jié)果如圖8所示。

由圖8可知，Dijkstra和EDRA分組丟包率變化較小，隨著鏈路利用率增大而緩慢增長；SGRP分組丟包率在鏈路利用率低于60%時(shí)增長緩慢，當(dāng)鏈路利用率高于60%時(shí)急劇增長。分析原因主要是：隨著鏈路利用率增大，鏈路容量逐漸飽和，造成了部分分組數(shù)據(jù)丟包，而EDRA及時(shí)通過次優(yōu)路徑和GEO衛(wèi)星進(jìn)行分流，避免了分組數(shù)據(jù)丟失。

5 結(jié)束語

本文提出了一種適用于GEO／LEO雙層衛(wèi)星網(wǎng)絡(luò)的基于等長時(shí)隙劃分的星上分布式路由算法EDRA，通過動(dòng)態(tài)調(diào)整極區(qū)邊界值等長劃分時(shí)隙，有效解決了網(wǎng)絡(luò)拓?fù)鋾r(shí)變和鏈路切換問題；利用星上分布式路由，提高了網(wǎng)絡(luò)抗毀性能，縮短了路由收斂時(shí)間；衛(wèi)星網(wǎng)絡(luò)在時(shí)隙起始時(shí)刻收集鏈路狀態(tài)信息，進(jìn)行路由計(jì)算與更新。仿真驗(yàn)證表明：動(dòng)態(tài)極區(qū)邊界值等長時(shí)隙劃分能夠延長路由持續(xù)時(shí)間，提高網(wǎng)絡(luò)鏈路利用率；EDRA算法端到端時(shí)延穩(wěn)定；當(dāng)鏈路利用率增大時(shí)，其網(wǎng)絡(luò)丟包率較低，趨近于路由性能極限。下一步將在EDRA算法基礎(chǔ)上，深入研究衛(wèi)星網(wǎng)絡(luò)抗毀性路由算法。

［1］ 妥艷君，劉云，郝立剛.具有星際鏈路的LEO／MEO衛(wèi)星網(wǎng)絡(luò)動(dòng)態(tài)路由協(xié)議 ［J］.北京交通大學(xué)學(xué)報(bào)，2010，34（2）：48－52.

TUO YANJUN，LIU YUN，HAO LIGANG.Dynamic routing protocol in LEO／MEO satellite networks with inter－satellite links［J］.Journal of Beijing Jiaotong University，2010，34（2）：48－52.

［2］ 唐劍，佘春東，徐志明.LEO／MEO衛(wèi)星網(wǎng)絡(luò)動(dòng)態(tài)多徑路由協(xié)議［J］.計(jì)算機(jī)科學(xué)，2009，36（10）：42－45.

TANG JIAN，SHE CHUNDONG，XU ZHIMING.Dynamic multi－path routing protocol for LEO／MEO satellite networks［J］.Computer Science，2009，36（10）：42－45.

［3］ FATIH ALAGOZ，OMER KORCAK，ABBAS JAMMLIPOUR.Exploring the routing strategies in next－generation satellite networks［J］.IEEE Wireless Communication，2007，14（3）：79－88.

［4］ WERNER M，DELUCCHI C，VOGEL H.ATM－based routing in LEO satellite networks with inter－satellite links［J］.IEEE Journal on Selected Areas in Communications，1997，15（1）：69－81.

［5］ 周云暉，孫富春，張鈸，等.一種基于時(shí)隙劃分的三層衛(wèi)星網(wǎng)絡(luò)QoS路由協(xié)議［J］.計(jì)算機(jī)學(xué)報(bào)，2006，29（10）：1813－1822.

ZHOU YUNHUI，SUN FUCHUN，ZHANG BO，et al.A time－division QoS routing protocol for three－layered Satellite Networks［J］.Chinese Journal of Computers，2006，29（10）：1813－1822.

［6］ 楊力，楊校春，潘成勝.一種GEO／LEO雙層衛(wèi)星網(wǎng)絡(luò)路由算法及仿真研究［J］.宇航學(xué)報(bào)，2012，33（10）：1445－1452.

YANG LI，YANG XIAOCHUN，PAN CHENGSHENG.A GEO／LEO double－layered satellite network routing algorithm and its simulation［J］.Journal of Astronautics，2012，33（10）：1445－1452.

［7］ HONG SEONG CHANG，BYOUNG WAN KIM，CHANG GUN LEE，et al.Performance comparison of static routing and dynamic routing in low－earth orbit satellite networks［C］.Vehicular Technology Conference 1996：1240－1243.

［8］ 王京林，晏堅(jiān)，曹志剛.LEO衛(wèi)星網(wǎng)絡(luò)快照序列路由算法優(yōu)化［J］.宇航學(xué)報(bào)，2009，30（5）：2003－2007.

WANG JINGLIN，YAN JIAN，CAO ZHIGANG.Optimization of sequent snapshots routing algorithm in LEO satellite networks［J］.Journal of Astronautics，2009，30（5）：2003－2007.

［9］ JUNFENG WANG，LEI LI，MINGTIAN ZHOU.Topological dynamics characterization for LEO satellite networks［J］.Computer Network Journal，2007，51（1）：43－53.

［10］ WANG JUNFENG，XU FANJIANG，SUN FUCHUN.Benchmarking of routing protocols for layered satellite networks［C］.MACS Multi conference on Computational Engineering in Systems Application：2006：1087－1094.

［11］ 何俊，易先清.基于GEO／LEO兩層星座的衛(wèi)星組網(wǎng)結(jié)構(gòu)分析［J］.火力與指揮控制，2009，34（03）：47－50.

HE JUN，YI XIANQING.Analysis of satellite network architecture based on GEO／LEO constellation［J］.Fire Control and Command Control，2009，34（03）：47－50.

［12］ 代坤.天基信息網(wǎng)體系結(jié)構(gòu)及路由交換技術(shù)研究 ［D］.北京：中國科學(xué)院計(jì)算技術(shù)研究所，2005.

DAI KUN.The construction and routine technology for the sky－based information networks［D］.Beijing：Institute of Computing Technology，Chinese Academy of Sciences，2005.

A Double－layered Satellite Constellation Network Routing Algorithm Based on Equal－length Interval Snapshots

ZHANG Jingbin1，2LIU Jiong1SHEN Pubing1
（1Xi′an communications Institute，Xi′an 710106） （2 Army Unit 73132，Zhangzhou 363111）

For the satellite constellation network，changes in real－time of network topology and frequently handover of ISL have bad impacts on the routing performance.Based on the backbone－and－accessions theory and the weak connection theory，a new double－layered satellite constellation network structure was proposed，which can help the administration for each layer.Moreover，a new routing algorithm，named EDRA，was proposed.The routing algorithm improves the method of equal－length interval snapshots by adjusting the polar boundary dynamically and adopting the new idea of layered management.The analysis and simulations show that the new satellite constellation network structure is more sensible，the number of snapshots of the EDRA algorithm is only the half of the VLRA algorithm，and the average duration of snapshots is more than three times of the VLRA algorithm.The EDRA algorithm can reduce the number of calculation and updating of the routing，improve the utilization of network ISL，reduce the delay jitter and packet loss rate.

GEO／LEO double－layered satellite constellation network；Equal－length interval snapshots；On－board distributed routing algorithm；Dynamically adjust the polar boundary；Simulation

10.3780／j.issn.1000－758X.2015.03.003

張景斌 1985年生，2007年畢業(yè)于西安通信學(xué)院，現(xiàn)為西安通信學(xué)院軍隊(duì)指揮學(xué)碩士研究生。研究方向?yàn)樾l(wèi)星通信網(wǎng)絡(luò)協(xié)議。

劉 炯 1973年生，2007年獲清華大學(xué)信息與通信工程專業(yè)博士學(xué)位，西安通信學(xué)院副教授。研究方向?yàn)樾l(wèi)星通信網(wǎng)絡(luò)協(xié)議、信息安全。

（編輯：楊嬋）

陜西省科學(xué)技術(shù)研究發(fā)展計(jì)劃（2013JM8007）；全軍軍事學(xué)研究生課題（2011JY002－253）資助項(xiàng)目

2014－11－28。收修改稿日期：2015－02－27