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

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

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

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

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

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

1 引言

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

近年來國內(nèi)外針對衛(wèi)星網(wǎng)絡拓撲時變和鏈路頻繁切換問題提出了多種路由算法和實現(xiàn)策略，根據(jù)其基本思想可分為動態(tài)拓撲路由、虛擬節(jié)點路由和虛擬拓撲路由三大類。動態(tài)拓撲路由基本思想是采用數(shù)據(jù)包自動尋址的方式，依據(jù)實時衛(wèi)星網(wǎng)絡拓撲進行路由計算［2］。虛擬節(jié)點路由基本思想是將衛(wèi)星網(wǎng)絡模型化為拓撲固定的虛擬衛(wèi)星節(jié)點進行路由計算［3］。虛擬拓撲路由基本思想是利用衛(wèi)星網(wǎng)絡的周期性和可預測性，將星座周期劃分為若干時間段，每個時間段內(nèi)星座拓撲可視為固定不變，稱為拓撲快照或者時隙，從而利用拓撲快照為各衛(wèi)星節(jié)點分段計算路由［4］。

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

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

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

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

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

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

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

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

GEO／LEO雙層衛(wèi)星網(wǎng)絡中包含三種全雙工通信鏈路：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)絡之間的用戶數(shù)據(jù)鏈路（User Data Link，UDL）。

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

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

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

在本文研究的GEO／LEO雙層衛(wèi)星網(wǎng)絡中，GEO衛(wèi)星相對地面固定不變，網(wǎng)絡拓撲變化主要由LEO衛(wèi)星進入或者離開GEO層星座覆蓋域所引起的，極區(qū)邊界值β如圖2所示，由LEO衛(wèi)星的LEO－GEO最小仰角Emin和軌道高度HL共同決定。

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

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

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

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

GEO衛(wèi)星覆蓋域和極區(qū)示意如圖4所示，其中，β′≤β為動態(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值取最大值。因此，當LEO衛(wèi)星Li，j運行到極區(qū)邊界時，其相同軌道上的（當NL為偶數(shù)時）或者相鄰軌道上的（當NL為奇數(shù)時）恰好運行到相對稱的極區(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算法通過動態(tài)調(diào)整極區(qū)邊界值，在路由起始時刻關閉即將進入極區(qū)衛(wèi)星的軌間ISL，造成了部分網(wǎng)絡鏈路資源的浪費。設L（Δt）為極區(qū)邊界值調(diào)整后單個時隙內(nèi)連通的鏈路數(shù)量，Lc為調(diào)整前單個時隙內(nèi)連通的鏈路數(shù)量，則網(wǎng)絡鏈路利用率U＝L（Δt）／Lc。

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

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

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

3.2 星上路由計算與更新

按照路由計算承擔對象，虛擬拓撲路由可分為基于地面網(wǎng)關的離線式路由和基于星上分布式路由。由于離線式路由存在突發(fā)情況處置能力差、拓撲狀態(tài)收集時間長、特殊時期地面網(wǎng)關易被摧毀等問題，為提高GEO／LEO雙層衛(wèi)星網(wǎng)絡路由算法的魯棒性、縮短路由收斂時間，本文采用星上分布式路由算法。在每個時隙起始時刻，衛(wèi)星網(wǎng)絡收集鏈路狀態(tài)信息（LMR），進行路由計算和更新。路由計算與更新流程如圖5所示。

具體步驟可描述為：

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

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

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

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

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

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

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

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

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

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

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

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

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

GEO衛(wèi)星Gk依據(jù)LMRw，以最小節(jié)點跳數(shù)為優(yōu)化目標，采用貝爾曼（Bellman）算法，為自身計算其到所有LEO／GEO衛(wèi)星的最優(yōu)路徑，將計算結果添加到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é)點的最優(yōu)下一跳、次優(yōu)下一跳，生成LEO衛(wèi)星路由轉(zhuǎn)發(fā)表LRT（X），并分發(fā)至相應的LEO衛(wèi)星。LEO衛(wèi)星路由轉(zhuǎn)發(fā)表LRT（X）主要包括：路由源節(jié)點、路由目的節(jié)點、最優(yōu)下一跳、次優(yōu)下一跳等信息。

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

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

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

4 仿真與性能分析

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

4.1 星座仿真與時隙劃分

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

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

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

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

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

圖6 時隙劃分結果比較Fig.6 Interval snapshot results of two algorithms

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

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

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

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

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

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

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

（1）端到端時延特性仿真

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

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

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

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

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

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

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

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

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

5 結束語

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

［1］ 妥艷君，劉云，郝立剛.具有星際鏈路的LEO／MEO衛(wèi)星網(wǎng)絡動態(tài)路由協(xié)議 ［J］.北京交通大學學報，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)絡動態(tài)多徑路由協(xié)議［J］.計算機科學，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］ 周云暉，孫富春，張鈸，等.一種基于時隙劃分的三層衛(wèi)星網(wǎng)絡QoS路由協(xié)議［J］.計算機學報，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)絡路由算法及仿真研究［J］.宇航學報，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］ 王京林，晏堅，曹志剛.LEO衛(wèi)星網(wǎng)絡快照序列路由算法優(yōu)化［J］.宇航學報，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)結構分析［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)體系結構及路由交換技術研究 ［D］.北京：中國科學院計算技術研究所，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è)于西安通信學院，現(xiàn)為西安通信學院軍隊指揮學碩士研究生。研究方向為衛(wèi)星通信網(wǎng)絡協(xié)議。

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

（編輯：楊嬋）

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

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