基于局部隊列的導航衛星網絡路由算法

燕洪成，張慶君，孫 勇

(中國空間技術研究院總體部，北京100094)

0 引言

衛星導航系統可以利用星間鏈路的星間測距功能實現自主導航;同時，也可以利用星間鏈路的星間通信功能實現全球組網，從而提高系統的整體性能［1－3］。由于導航衛星平臺和指向性星間鏈路(Inter-Satellite Link，ISL)天線的約束，導航衛星所能攜帶的天線數量有限(比如僅能攜帶一條)，導航衛星網絡中的ISL將呈現半雙工、大時延、鏈路間斷可用的特點。同時，由于地球自轉和導航星座運行的影響，導航衛星與地面站之間的星地鏈路(Ground-Satellite Link，GSL)也呈現周期性的連接與中斷特點。ISL和GSL的這種鏈路間斷可用特點使導航衛星網絡任意兩個網絡節點之間并不一定時刻存在端到端路徑，使其形成一個典型的延遲/中斷容忍網 絡(Delay/Disruption Tolerant Network，DTN)［4－6］。這對導航衛星網絡的數據傳輸問題，特別是路由問題帶來了新的挑戰［7］。

圖1為一個典型導航衛星網絡不同時刻的拓撲示意圖，時間間隔固定為Δt，稱為一個時隙。假設有6顆導航衛星(圓形)和1個地面站(正方形)，兩顆導航衛星之間用兩個單向箭頭連接說明在該時隙內建立了半雙工ISL，導航衛星和地面站之間用雙向箭頭連接說明在該時隙內建立了全雙工GSL。假定每顆導航衛星均配置1副ISL天線和1副GSL天線，1顆導航衛星在1個時隙內僅能選擇與另外1顆可見衛星建立ISL，并以一定策略與地面站建立GSL。從圖1可以看出，由于ISL和GSL間斷連接，導航衛星網絡中任意兩個節點間并不一定時刻存在端到端路徑，從而形成一個非全連通的網絡拓撲。比如衛星4與地面站G1在任何時隙均不存在端到端路徑，這使Dijkstra算法［8］在任何一個時隙均不能計算出可行路徑。但衛星4可以在時隙［0，Δt)將消息發送給衛星3，衛星3暫存消息，并在時隙［2Δt，3Δt)轉發給地面站G1，最終完成消息的投遞。導航衛星網絡中的路由問題不僅需要考慮某一時刻的靜態拓撲，同時需要考慮網絡拓撲的時間演化特性，通過綜合考慮不同時刻的網絡拓撲完成路由計算。

圖1 導航衛星網絡在不同時刻的網絡拓撲示意圖Fig．1 Network topology of navigation satellite network in different time slots

導航衛星網絡的網絡拓撲由ISL和GSL的鏈路調度決定，ISL和GSL的鏈路調度一般根據一定策略提前生成，并分發到每個網絡節點;因此，導航衛星網絡的路由問題可以看作是確定鏈路調度的DTN路由問題。

由于傳統的移動通信衛星網絡路由算法［9－10］均假定網絡時刻存在端到端路徑，因此并不適用于導航衛星網絡。學術界針對DTN路由問題的研究主要集中在機會網絡［11－12］，確定鏈路調度的DTN路由算法相對較少。目前，學術界針對確定鏈路調度的DTN路由問題提出了演化圖模型［7，13］、空時路由算法［14］、接觸圖路由(Contact Graph Routing，CGR)［15］、時變圖模型［16］等，但這些路由算法均只考慮網絡的鏈路調度，而未考慮網絡的排隊延時，因此，其性能有限。由于導航衛星網絡鏈路通信機會有限，排隊延時可能使消息錯過當前可用通信機會，從而增大端到端延時，并使消息長時間占用網絡資源，降低消息投遞成功率。

Jain等［17］提出了基于本地隊列的最早投遞(Earliest Delivery with Local Queue，EDLQ)和基于全網隊列的最早投遞(Earliest Delivery with All Queues，EDAQ)路由算法;Bezirgiannidis等［18－19］針對CGR提出了一種基于最早傳輸機會(Earliest Transmission Opportunity，ETO)的路由算法(CGRETO)，并考慮全網隊列信息。但上述路由算法存在以下問題:首先，僅考慮本地節點隊列信息不能夠使消息避開擁塞的鄰居節點;其次，獲取全網的隊列信息會帶來大量的協議開銷，且由于導航衛星網絡的端到端延時較大，網絡節點獲取的隊列信息可能已經過時。因此，向全網泛洪隊列信息帶來的性能提升有限。

本文針對鏈路間斷可用的導航衛星網絡，提出一種基于局部隊列的最早投遞(Earliest Delivery with Partial Queues，EDPQ)路由算法。EDPQ綜合利用鏈路調度信息、本地和鄰居節點隊列信息，可以實現鏈路調度按需更新，并以較低協議開銷更新鄰居節點隊列信息，實現了更高效的數據傳輸。

1 EDPQ路由算法

EDPQ路由算法利用全網的鏈路調度信息、本地和鄰居節點的隊列信息完成路由計算。全網的鏈路調度信息為已知信息且一般周期性重復，由于提前存儲未來所有的鏈路調度信息不現實，EDPQ采用一種按需更新的策略來更新鏈路調度信息;本地節點的隊列信息較容易獲取，而鄰居節點的隊列信息需要不斷更新，EDPQ采用一種低開銷的機制更新鄰居節點隊列信息。

1．1導航衛星網絡的圖模型

記導航衛星網絡的節點集合為V，邊集為E?V×V。定義ρ:E×R+→{0，1}為存在函數，表示在時刻t邊e是否存在;定義d:E×R+→R+為傳播延時函數，表示在時刻t邊e的傳播延時。對于導航衛星網絡，節點集合為衛星、地面站和任務運行中心等網絡節點的集合;邊集為星間鏈路、星地鏈路和地面有線鏈路等通信鏈路的集合。

假定所有鏈路在可用時間間隔內帶寬恒定，那么，在時刻t邊e的容量可以表示為c(e，t)=b(e)·ρ(e，t)，其中b(e)為邊e的帶寬。

記邊e的存在時間為I(e)={t∈R+:ρ(e，t)=1}，表示邊e存在的所有時間的集合。邊e的存在時間也可表示為一系列鏈路調度區間的集合，即I(e)={［t1，t2)∪［t3，t4)∪…}。對于導航衛星網絡，鏈路的存在時間通常呈現周期性。定義邊e存在函數的周期為p，即對于任意t∈R+，任意k∈N，ρ(e，t)=ρ(e，t+kp)成立。那么邊e的存在時間可以表示為

1．2鏈路調度按需更新機制

對于導航衛星網絡的鏈路調度信息，本文只存儲每條邊一個周期的鏈路調度信息，并在路徑計算過程中按需更新鏈路調度信息;同時，每隔固定時間Δtrm移除過去的鏈路調度信息，防止鏈路調度信息無限制增長，占用導航衛星有限的存儲資源。

EDPQ利用改進Dijkstra算法［17］計算下一跳，改進Dijkstra算法可以利用邊的時變代價w:E×R+→R+計算延時最優路徑。邊的時變代價w(e，t)除了與邊和時間有關外，與當前消息大小和本地節點也有關，因此，為了統一，將代價函數寫為w(e，t)=w'(e，t，m，s)，其中，m為消息的大小，s為當前節點［17］。

w'(e，t，m，s)可以寫為

w'(e，t，m，s)=t'(e，t，m，s)－t+d(e，t')

其中，

在上式中，函數Q(e，t，s)為本地節點s在時刻t獲取的邊e源端的隊列長度，t'為將隊列中的消息和當前消息發送到網絡中的最早時刻［17］。

改進Dijkstra算法的關鍵在于時間t'的計算，在實際實現t'計算公式中的積分時，需要綜合考慮當前隊列中消息與待發送消息的大小、時刻t與接觸機會的關系，以及接觸機會的容量限制。圖2為當前時刻與接觸機會的三種關系示意圖。第一種情況t=t1時，計算t'需要考慮下一個接觸機會的容量，如果下一個接觸機會容量不夠，還需要考慮下下一個接觸機會。第二種情況t=t2時，計算t'需要考慮當前接觸機會的剩余容量，如果剩余容量不夠，也要考慮下一個接觸機會。第三種情況t=t3時，由于已經沒有未來的接觸機會可用，需要首先增加一個周期的接觸機會，然后按第一種或第二種情況計算t'。

圖2 當前時刻與接觸機會的三種關系Fig．2 Three potential relationships between current time and contact opportunities

圖3為計算t'及鏈路調度按需更新機制的偽代碼，其中，I為鏈路調度區間鏈表，臨時變量II為邊的某個鏈路調度區間，并用start和stop分別表示該鏈路調度區間的開始時間和結束時間，load為當前消息和隊列中消息大小的總和;函數AddSched()將增加邊的一個周期的鏈路調度。

圖3 計算t'及鏈路調度按需更新機制的偽代碼Fig．3 Pseudocode of calculation for t'and on-demand link schedule updating mechanism

1．3鄰居節點隊列信息更新機制

演化圖模型［7，13］、空時路由算法［14］、接觸圖路由［15］、時變圖模型［16］和ED路由算法［17］等均只考慮鏈路調度信息，未考慮網絡的排隊延時，因此其性能有限。在DTN網絡中，消息傳輸的端到端延時主要包括等待鏈路可用延時、排隊延時、發送延時和傳播延時。排隊延時雖然可能只占路徑延時的小部分，但由于導航衛星網絡鏈路通信機會有限，較大的排隊延時可能會使消息錯過當前可用接觸機會，而只能等待下次接觸機會，從而增大端到端時延，并使消息長時間占用網絡資源，降低消息投遞成功率。因此，在導航衛星網絡的路由計算中應該考慮消息的排隊延時。

導航衛星網絡的本地節點隊列信息較容易獲取，鄰居節點隊列信息也相對容易獲取。由于僅利用本地節點隊列信息不能使消息避開擁塞的鄰居節點;而獲取全網隊列信息會帶來較大的協議開銷，且由于導航衛星網絡路徑延時較大，獲取的全網隊列信息時效性較差，實際能夠帶來的性能改進有限。因此，EDPQ除了利用鏈路調度信息外，僅考慮了本地和鄰居節點的隊列信息。

EDPQ采用一種隊列閾值觸發機制觸發隊列信息的發送，以降低鄰居節點隊列信息傳播帶來的協議開銷。本地節點收到鄰居節點發送的包含隊列信息的消息(簡稱隊列消息)后，通過人為加大擁塞的邊的排隊延時來降低選擇此邊的概率，從而避開排隊延時大的路徑。同時，鄰居節點隊列信息的作用應該隨時間慢慢減弱，因此，本地節點對鄰居節點隊列信息按指數進行衰減。

當本地節點的發送機會(由于ISL為半雙工)出現時，本地節點首先統計除當前邊外，其它邊的隊列大小Qsize≥95%Qlimit(Qlimit為隊列容量)的隊列個數。如果超出閾值的隊列個數大于等于1，本地節點將首先發送隊列消息到鄰居節點，然后再發送本地數據消息;否則，直接發送本地數據消息。鄰居節點如果利用本地節點與其相連的邊的話會產生路由環路，因此，沒有統計當前邊。Qsize≥95%Qlimit說明即將發生擁塞，需要通知鄰居節點以避開此邊。

鄰居節點收到隊列消息后，將Qsize≥95%Qlimit的相應隊列的大小按下式設置為一個比較大的數值，以避免選擇此邊。

式(1)基于這樣一種考慮，在DTN網絡中，等待時間通常占端到端延時的大部分，而最短路徑和次短路徑的延時代價可能相差較大，且相差的部分主要來自等待時間，排隊時間的變化通常不足以使最短路徑變為次短路徑，使消息仍然選擇最短路徑進一步加劇擁塞。

為了更清晰地說明上述情況，考慮圖4所示的一個示意圖。其中圖4(a)顯示了圖1中衛星6到地面站G1的兩條路徑，圖中假定Δt為3 s，半雙工約定前半個時隙序號小的衛星先發送，后半個時隙正好相反;圖4(b)為衛星6的一種隊列情況示意圖，圖中衛星6為每個鄰居節點分配一個等容量的隊列用于緩存消息。假設衛星6的消息均發往地面站G1，由圖4(a)可知，消息可以通過最短路徑6－＞5－＞2－＞G1在4．5 s到達地面站G1，也可以通過次短路徑6－＞3－＞G1在6 s到達地面站G1，最短和次短路徑代價相差1．5 s。假定衛星6中衛星5的隊列已經緩存了大量的消息，那么對于當前消息m，雖然通過衛星5轉發會經歷較大的排隊延時，但只有當排隊延時超過1．5 s時最短路徑的代價才會高于次短路徑。排隊延時最大為隊列容量除以ISL速率，假設隊列容量為40 kbits，ISL速率為50 kbps，排隊延時最大為0．8 s，仍然不能夠使最短路徑變為次短路徑，因此需要人為加大擁塞的邊的排隊時間，降低選擇此邊的概率。由于最短路徑和次短路徑之間相差大于等于一個周期的情況較少，因此，設置排隊時間為該邊一個周期的時間。

EDPQ在產生消息或收到消息后，首先分別對本地隊列和鄰居節點隊列進行處理。對每個本地隊列，如果Qsize≥Qlimit，那么按式(1)設置該隊列大小;對每個鄰居節點隊列，按下式進行衰減［20］

式中:Δt為距上次鄰居節點隊列信息更新所經歷的時間間隔數量，其值為實際時間間隔除以時間單位tunit，β∈(0，1)為衰減因子。由于節點發送消息時使用的鄰居節點隊列信息可能不是最新的，而且鄰居節點隊列信息更新不是周期性的，因此鄰居節點隊列信息應該慢慢衰減。在對本地隊列信息和鄰居節點隊列信息處理完成后，利用改進Dijkstra算法計算下一跳轉發節點。

2 性能評估

2．1仿真環境

圖4 用于解釋隊列大小設置的一個例子Fig．4 An example to explain the setting of queue size

為了校驗EDPQ的性能，在典型的導航衛星網絡中進行了仿真評估。導航衛星網絡由導航衛星星座及相關地面站和任務運行中心(Mission Operation Center，MOC)組成，如圖5所示。導航衛星星座構型選擇walker 24/3/2，即一共24顆衛星分布在3個軌道面內，相位因子為2。導航衛星軌道高度為20232 km，傾角為55°。選用北京、喀什、三亞3個地面站，每個地面站均配置2副天線，并選擇與自己未來通信時間最長的兩顆導航衛星建立全雙工GSL。地面站與MOC之間通過地面網絡時刻保持連通。

圖5 導航衛星網絡系統架構圖Fig．5 Network architecture of the navigation satellite network

每顆衛星僅攜帶一副半雙工ISL天線，指向方位角限定在［－60°，60°］。由于地球的遮擋和ISL的指向限制，并不是所有衛星間都能建立ISL［21］。一顆導航衛星選擇與哪顆可見衛星建立ISL屬于導航衛星網絡的鏈路分配問題［22］，不在本文的研究范圍內。為簡便起見，ISL的鏈路調度按每顆衛星均能與全周期可見的同軌和異軌衛星建立ISL的策略手動生成。ISL的鏈路調度共有8個時隙，并以此為周期循環，每個時隙的持續時間為Δt。

導航衛星網絡ISL的鏈路調度用一個24×8的矩陣表示，如圖6所示。矩陣的元素(i，j)表示衛星i與衛星(i，j)，在第j個時隙建立半雙工ISL。比如位于第2行和第3列的13表示，在第3個時隙，衛星2與衛星13建立半雙工ISL。每個時隙的前Δt/2，數值小的衛星發送，數組大的衛星接收，后Δt/2相反。

在OPNET網絡仿真軟件中對導航衛星網絡進行了建模，默認仿真參數如表1所示，后文中，若無特殊說明，均采用此默認仿真參數。導航衛星網絡的消息由衛星和MOC產生，消息到達時間間隔均服從指數分布。導航衛星產生消息的目的節點為MOC，MOC產生消息的目的節點為隨機一顆衛星。

表1 默認仿真參數Table 1 The default simulation parameters

2．2仿真結果

比較的路由算法選擇ED、EDLQ和EDAQ。EDAQ可以有分布式和集中式兩種實現方式，由于Jain等［17］沒有說明EDAQ具體采用哪種實現方式，本文同時實現了兩種EDAQ，即EDAQ分布式(EDAQ Distributed，EDAQ-D)和EDAQ集中式(EDAQ Central，EDAQ-C)。EDAQ-D通過向全網泛洪隊列消息來獲取全網隊列信息，而EDAQ-C維護一個全局的網絡隊列信息庫，沒有任何協議開銷。EDAQ-C現實中較難實現，主要用作性能對比。

圖6 導航衛星網絡ISL的鏈路調度Fig．6 Link schedule of the navigation satellite network

性能度量指標選擇消息投遞成功率、端到端時延和協議開銷。投遞成功率為投遞成功的消息數量占產生消息總量的百分比;端到端時延為消息從產生到成功投遞所經歷的時間，由于無法統計丟棄消息的時延，因此端到端時延僅統計成功投遞的消息;協議開銷為單位時間內傳播的隊列消息的比特數，即協議開銷為傳播的隊列消息個數乘以隊列消息大小，再除以仿真持續時間，其中，隊列消息大小為416 bits。在比較的五種路由算法中，僅有EDPQ和EDAQ-D會產生協議開銷。

為了測試不同網絡負載對路由算法性能的影響，設置導航衛星的消息到達時間間隔從0．8 s以指數間隔變化到0．05 s，即網絡負載不斷增大。MOC的消息到達時間間隔保持恒定，仿真結果如圖7所示。由圖7(a)可以看出，隨著網絡負載的增大，五種路由的投遞成功率均呈下降趨勢，這是由于有限的存儲資源逐漸不能存儲產生的越來越多的消息，因此，越來越多的消息不能投遞到目的地。ED和EDLQ的性能較差，其投遞成功率在較低網絡負載時就開始下降。EDAQ-C的投遞成功率最高，EDPQ的性能與EDAQ-C接近。EDAQ-D的投遞成功率在網絡負載較大時比EDPQ要低，這是因為EDAQ-D產生了較大的協議開銷，而EDPQ的協議開銷相對較低，如圖7(c)所示，較大的協議開銷會占用導航衛星有限的存儲資源，使消息不能得到存儲而被丟棄。在圖7(c)中，當消息到達時間間隔為0．8 s時，EDPQ和EDAQ-D的協議開銷均為零。

圖7(b)為不同路由算法的端到端時延性能。當網絡負載較低時，五種路由算法的時延性能相當。隨著網絡負載的增大，ED與EDLQ的端到端時延仍然較低，這與其較低的投遞成功率有關;而其它路由算法的時延開始增大，這與其選擇擁塞程度差的路徑避免丟包有關。EDAQ-D產生的大量協議開銷會占用導航衛星網絡有限的通信資源，使消息錯過當前可用通信機會，增大端到端時延。EDPQ與EDAQ-C的端到端時延性能接近。

為了測試不同隊列容量對路由算法性能的影響，設置導航衛星每鄰居節點隊列容量分別為20、30、40、50、60 kbits，仿真結果如圖8所示。由圖8(a)可以看出，隨著隊列容量的增大，五種路由的投遞成功率均呈增大趨勢，這是由于增多的隊列容量可以存儲更多的消息，使更多的消息成功投遞到目的節點。在隊列容量小于50 kbits時，EDPQ與EDAQ-C的投遞成功率接近，而EDAQ-D的投遞成功率要比EDPQ低。這是由于EDAQ-D產生了大量的協議開銷，如圖8(c)所示，大量的協議開銷會占用有限的存儲資源，使消息得不到存儲而被丟棄。在隊列容量非常充足時(60 kbits)，EDPQ、EDAQ-D和EDAQ-C的投遞成功率均達到了百分之百。ED和EDLQ的投遞成功率均較低。

圖8(b)為不同路由算法的端到端時延性能。EDAQ-D的端到端時延較大，這是由于EDAQ-D產生的大量協議開銷會占用有限的通信資源，使消息錯過當前可用通信機會。EDPQ與EDAQ-C的端到端時延性能接近，但比EDAQ-D的端到端時延要低。ED與EDLQ的端到端時延較低，這與其較低的投遞成功率有關。

圖7 不同網絡負載時的路由性能Fig．7 Performance with varying network loads

為了測試不同ISL通信速率和不同數據消息大小對路由算法性能的影響，設置ISL通信速率分別為20、40、60、80 kbps，設置數據消息大小分別為512、1024、2048、4096 bits，仿真結果如圖9所示。由圖9(a)可以看出，當ISL通信速率為20 kbps時，EDLQ、EDPQ與EDAQ-C的投遞成功率接近，而EDAQ-D和ED性能較差。由于EDAQ-D會產生大量的通信開銷占用有限的通信資源，這在ISL速率較低時會更明顯，因此其投遞成功率較低。當ISL通信速率為40、60和80 kbps時，EDAQ-C的投遞成功率最高，EDPQ的投遞成功率與EDAQ-C接近，EDAQ-D的投遞成功率比EDPQ低，ED和EDLQ的投遞成功率最低。

圖8 不同隊列容量時的路由性能Fig．8 Performance with varying queue capacities

在圖9(b)中，當數據消息大小為512 bits時，EDPQ與EDAQ-C的投遞成功率接近，而EDAQ-D與ED、EDLQ的投遞成功率較低。這是由于EDAQD帶來的較大協議開銷在數據消息大小與隊列消息大小相近時會更加明顯。較大的協議開銷使數據消息沒有機會得到有限的存儲資源，從而被丟棄;較大的協議開銷也使數據消息不能獲得有限的通信資源，而不得不等待未來的通信機會，進而使數據消息長時間占用網絡存儲資源，使其它消息不能得到存儲資源，造成其它消息的丟棄。當數據消息大小為1024、2048和4096 bits時，EDAQ-C的投遞成功率最高，EDPQ的投遞成功率與EDAQ-C接近，EDAQD的投遞成功率比EDPQ低，ED和EDLQ的投遞成功率最低。

圖9 投遞成功率與ISL通信速率和消息大小的關系Fig．9 Delivery success ratio with varying ISL rates and message sizes

3 結論

本文提出了一種基于局部隊列的最早投遞(EDPQ)路由算法，并在典型的導航衛星網絡中對EDPQ進行了仿真評估。仿真結果表明，EDPQ實現了較高的消息投遞成功率和較低的端到端延時，且具有較低的協議開銷，為鏈路間斷可用的導航衛星網絡的路由問題提供了一種可行的技術方案。

［1］Maine K，Anderson P，Bayuk F．Communication architecture for GPS III［C］．2004 IEEE Aerospace Conference，Big Sky，USA，March 6－13，2004．

［2］Luba O，Boyd L，Gower A．GPS III system operations concepts［J］．IEEE Aerospace and Electronic Systems Magazine，2005，20(1):10－18．

［3］Fernandez A．Inter-satellite ranging and inter-satellite communication links for enhancing GNSS satellite broadcast navigation data［J］．Advances in Space Research，2011，47:786－801．

［4］Fall K．A delay-tolerant network architecture for challenged internets［C］．ACM SIGCOMM 2003，Karlsruhe，Germany，August 25－29，2003．

［5］ 林闖，董揚威，單志廣．基于DTN的空間網絡互聯服務研究綜述［J］．計算機研究與發展，2014，51(5):931－943．［Lin Chuang，Dong Yang-wei，Shan Zhi-guang．Research on space internetworking service based on DTN［J］．Journal of Computer Research and Development，2014，51(5):931－943．］

［6］ 燕洪成，張慶君，孫勇，等．延遲/中斷容忍網絡技術及其在行星際因特網中的應用［J］．航天器工程，2014，23(2):114－123．［Yan Hong-cheng，Zhang Qing-jun，Sun Yong，et al．Delay/disruption tolerant network and its application to interplanetary Internet［J］．Spacecraft Engineering，2014，23(2):114－123．］

［7］ 王彥，劉波，虞萬榮，等．基于演化圖的導航星座星間路由算法［J］．中國空間科學技術，2012(5):76－83．［Wang Yan，Liu Bo，Yu Wan-rong，et al．Routing algorithm for navigation constellation based on evolving graph model［J］．Chinese Space Science and Technology，2012(5):76－83．］

［8］Cormen T，Leiserson C．Introduction to algorithm［M］．Cambridge:The MIT Press，2004．

［9］ 盧勇，趙有健，孫富春，等．衛星網絡路由技術［J］．軟件學報，2014，25(5):1085－1100．［Lu Yong，Zhao You-jian，Sun Fuchun，et al．Routing techniques on satellite networks［J］．Journal of Software，2014，25(5):1085－1100．］

［10］ 王路，劉立祥，胡曉惠．基于地理位置信息的無收斂多測度衛星網絡路由算法研究［J］．宇航學報，2011，32(7):1542－1550．［Wang Lu，Liu Li-xiang，Hu Xiao-hui．Geographical location-based convergence-free routing using multiple metrics for satellite networks［J］．Journal of Astronautics，2011，32(7):1542－1550．］

［11］ 蘇金樹，胡喬林，趙寶康，等．容延容斷網絡路由技術［J］．軟件學報，2010，21(1):119－132．［Su Jin-shu，Hu Qiao-lin，Zhao Bao-kang，et al．Routing techniques on delay/disruption tolerant networks［J］．Journal of Software，2010，21(1):119－132．］

［12］Cao Y，Sun Z．Routing in delay/disruption tolerant networks:a taxonomy，survey and challenges［J］．IEEE Communications Surveys＆Tutorials，2013，15(2):654－677．

［13］Ferreira A．Building a reference combinatorial model for MANETs［J］．IEEE Network，2004，18(5):24－29．

［14］Merugu S，Ammar M，Zegura E．Routing in space and time in networks with predictable mobility，GIT-CC－04－07［R］．Atlanta，USA:Georgia Institute of Technology，March 2004．

［15］Burleigh S．Contact graph routing，IRTF Internet-Draft［EB/OL］．2010－07－08［2014－12－02］．http://tools．ietf．org/html/draft-burleigh-dtnrg-cgr-01．

［16］Casteigts A，Flocchini P，Quattrociocchi W，et al．Time-varying graphs and dynamic networks［J］．International Journal of Parallel，Emergent and Distributed Systems，2012，27(5):387－408．

［17］Jain S，Fall K，Patra R．Routing in a delay tolerant network［J］．ACM SIGCOMM Computer Communication Review，2004，34(4):145－158．

［18］Bezirgiannidis N，Caini C，Montenero D P，et al．Contact graph routing enhancements for delay tolerant space communications［C］．7th Advanced Satellite Multimedia Systems Conference and the 13th Signal Processing for Space Communications Workshop(ASMS/SPSC)，Livorno，Italy，September 8－10，2014．

［19］Bezirgiannidis N，Tsapeli F，Diamantopoulos S，et al．Towards flexibility and accuracy in space DTN communications［C］．The 8th ACM MobiCom Workshop on Challenged Networks，Miami，USA，September 30，2013．

［20］Lindgren A．Probabilistic routing in intermittently connected networks［J］．ACM Mobile Computing and Communication Review，2003，7(3):19－20．

［21］ 李振東，何善寶，劉崇華，等．一種導航星座星間鏈路拓撲設計方法［J］．航天器工程，2011，20(3):32－37．［Li Zhendong，He Shan-bao，Liu Chong-hua，et al．An topology design method of navigation satellite constellation inter-satellite links［J］．Spacecraft Engineering，2011，20(3):32－37．］

［22］ 石磊玉，向為，唐小妹．一種兼顧衛星導航系統星間觀測及通信的鏈路分配算法［J］．宇航學報，2011，32(9):1971－1977．［Shi Lei-yu，Xiang Wei，Tang Xiao-mei．A link assignment algorithm applicable to crosslink ranging and data exchange for satellite navigation system［J］．Journal of Astronautics，2011，32(9):1971－1977．］