空間延遲/中斷容忍網絡路由算法性能評估

燕洪成，郭堅，張紅軍

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

?

空間延遲/中斷容忍網絡路由算法性能評估

燕洪成*，郭堅，張紅軍

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

文章主要針對空間延遲/中斷容忍網絡(Delay/disruption Tolerant Networks，DTN)路由算法的性能進行分析評估，為未來空間DTN路由技術的設計提供參考和建議。首先，從利用網絡知識多少的角度，對目前提出的適用于空間DTN的路由算法進行了分析和比較；然后，在一個典型空間DTN場景下，通過設定不同的接觸計劃，從微觀和宏觀兩個方面，對最早投遞(Earliest Delivery，ED)、基于本地隊列的最早投遞(Earliest Delivery with Local Queue，EDLQ)、接觸圖路由(Contact Graph Routing，CGR)和基于最早傳輸機會的接觸圖路由(Contact Graph Routing Earliest Transmission Opportunity，CGR-ETO)幾種典型空間DTN路由算法的性能進行了仿真評估；最后，對仿真評估結果進行了分析和總結，并對未來空間DTN路由算法的研究提出了建議。仿真結果表明，對于端到端延時和束投遞完成率兩項性能指標，ED性能最差，CGR次之，EDLQ和CGR-ETO的性能相當。

空間DTN；路由算法；最早投遞；基于本地隊列的最早投遞；接觸圖路由；基于最早傳

隨著太空中航天器數量的增多，傳統點到點通信方式的缺點越來越明顯，只有將不同航天器與不同地面支持設施互聯互通為一個天地一體的信息化網絡，才能滿足未來航天任務的數據傳輸需求[1-3]。

由于空間網絡所處的太空環境比較惡劣，因此，空間網絡具有不同于地面網絡的特點，比如，空間網絡中的鏈路通常具有延時大、帶寬不對稱、通信誤碼率高等特點，且由于天體遮擋等原因，鏈路并不是持續可用的；空間網絡中網絡節點的存儲和通信等資源一般非常有限；空間網絡一般不能保證時刻存在端到端路徑。

空間網絡具有的以上特點，對網絡協議的設計帶來了巨大的挑戰。由于地面因特網一般假定源節點和目的節點之間存在端到端路徑，節點之間延時不會太長，而且網絡丟包率較小，因此地面因特網的網絡協議并不適用于空間網絡。

延遲/中斷容忍網絡(Delay/disruption Tolerant Networks，DTN)最初起源于NASA噴氣推進實驗室對行星際互聯網的研究[4]，其通過采用一種新的端到端的覆蓋層網絡(Overlay Network)體系結構[5]，能夠適應網絡的大延時和鏈路間斷特點，可以運行于不存在端到端路徑的網絡中。

由于DTN潛在的應用前景，美國、歐洲、日本相繼開展了大量關于DTN的研究工作和演示試驗[6]，應用范圍涵蓋深空任務[6]、激光通信[7]、國際空間站[6]、遙感科學任務[6,8]和中繼通信[9]等領域。

空間數據系統咨詢委員會(CCSDS)最早針對空間網絡定義了一套空間通信協議規范(Space Communications Protocol Specification，SCPS)，然而，隨著越來越多的新方法得以提出，CCSDS不再贊成使用SCPS，而是傾向于太陽系互聯網(Solar System Internetwork，SSI)協議族[10]。SCPS中的網絡協議、安全協議和文件協議都被CCSDS降級為歷史文檔狀態，只有傳輸協議由于仍在商業應用中被采用才被CCSDS作為活動建議書維護。對于新的空間任務和研發，CCSDS強烈建議不要使用SCPS，而是應該參考SSI協議族(DTN和相關建議)[11]。目前，CCSDS專門成立了空間互聯業務——DTN工作組，以推動DTN技術的標準化[10,12]。

中國早在2000年左右就提出了研究和建設天基綜合信息網的設想[13]，并通過專項研究取得了顯著成果。

未來的空間信息網絡將包括遙感、導航、通信、深空探測、載人飛船，以及高空平臺等各種系統，具有時空跨度大和網絡節點分布稀疏等特點，網絡拓撲一般非全連通，網絡不能夠保證節點間時刻存在端到端路徑，從而形成一個典型的空間DTN(空間DTN在概念上側重地球軌道空間網絡，而行星際互聯網則側重深空網絡)。DTN最初起源于對行星際互聯網的研究，并繁榮于地面DTN的廣泛應用[14]，DTN不僅適用于深空網絡，同樣適用于地球軌道空間網絡[15-16]，對我國天地一體化信息網絡的建設具有重要的啟示作用[6-17]。

DTN為空間信息網絡提供了一種端到端的網絡傳輸服務，而這種端到端的網絡傳輸服務需要依賴于路由技術來提供最優的傳輸路徑，因此，路由技術是空間DTN數據傳輸功能的重要基礎。目前，針對空間DTN路由算法性能評估的研究還較少，因此，文章主要針對空間DTN路由算法的性能進行分析比較和仿真評估，為未來空間DTN路由技術的設計提供參考。

1　空間DTN路由算法

路由算法是空間DTN數據傳輸功能的基礎，由于空間DTN的鏈路斷續可用，且不能保證時刻存在端到端路徑，因此，傳統網絡的路由算法并不能適用于空間DTN，需要研究新的DTN路由算法。

由于空間DTN節點的運行軌跡是可預測的，因此，空間DTN的鏈路調度一般可以提前獲得，即空間DTN的路由問題可以看作是確定鏈路調度的DTN路由問題。目前，研究人員針對移動通信衛星網絡的路由問題進行了大量研究[18]，但這些路由算法均假定網絡在任意時刻都存在端到端路徑，因此，并不適用于空間DTN。針對DTN路由的研究主要集中在機會網絡，確定鏈路調度的DTN路由算法相對較少[19]。

文獻[20]針對確定的動態網絡提出了演化圖模型，并提出了不同優化目標的路徑計算算法，王彥等[21]將演化圖應用于采用指向性天線的導航星座星間網絡的路由計算。文獻[22]針對節點運動可預測網絡提出一種空時路由框架，采用一種層次化的空時圖模型和動態規劃來計算消息的最短路徑。文獻[23]針對DTN、機會移動網絡和社交網絡等不同的動態網絡，提出了一種統一的時變圖模型，但仍然采用演化圖的方法計算路徑。文獻[24]利用空間網絡星座拓撲的規律性和可預見性，針對空間DTN提出了一種時間圖路由。

以上路由算法均只考慮鏈路調度信息，未考慮網絡的排隊延時，因此其性能有限。在DTN中，消息傳輸的端到端延時主要包括等待鏈路可用延時、排隊延時、發送延時和傳播延時。排隊延時雖然可能只占路徑延時的小部分，但由于空間DTN鏈路通信機會有限，較大的排隊延時可能會使消息錯過當前可用連接機會，而只能等待下次連接機會，從而增大端到端延時。因此，在空間DTN的路由計算中應考慮消息的排隊延時。

文獻[25]在2004年美國計算機協會數據通信專業組國際會議(ACM SIGCOMM)上第一次提出了DTN的路由問題，并設計了一種改進的Dijkstra算法，并根據利用知識庫的多少提出了不同的路由算法(見圖1)，如首次接觸(First Contact，FC)、最小預計延時(Minimum Estimated Delay，MED)、最早投遞(Earliest Delivery，ED)、基于本地隊列的最早投遞(Earliest Delivery with Local Queue，EDLQ)、基于全網隊列的最早投遞(Earliest Delivery with All Queues，EDAQ)、線性規劃(Linear Programming，LP)，這些算法利用的網絡信息越來越多，性能也越來越好。LP雖能得到最優路徑，但需要知道未來的流量需求，現實中較難實現。EDAQ需要利用全網隊列信息，但由于DTN時延較大，獲取的隊列信息時效性較差；同時，向全網泛洪隊列信息會帶來大量的協議開銷。

圖1　利用不同網絡知識路由算法的性能情況[25]Fig.1　Performance of routing algorithms using different amount of knowledge[25]

在2008年的太空運管(SpaceOps)會議上,文獻[26]針對行星際互聯網提出了接觸圖路由(Contact Graph Routing，CGR)。CGR利用已知的接觸計劃(Contact Plan)計算消息的轉發路徑，并通過消息的預計容量消耗(Estimated Capacity Consumption，ECC)和接觸的殘余容量(Residual Capacity，RC)考慮接觸的容量限制，因此，其性能會比ED好，但它沒有考慮網絡的排隊延時[27]。

文獻[28]在2013年美國計算機學會挑戰網絡研討會上針對CGR提出一種考慮全網隊列的基于最早傳輸機會的接觸圖路由(Contact Graph Routing Earliest Transmission Opportunity，CGR-ETO)，并通過接觸計劃更新協議更新全網的隊列信息。由于CGR假定消息可以在接觸的開始時刻發送，而沒有考慮排隊延時，因此，CGR-ETO通過為每個接觸增加一個優先級相關的ETO變量來考慮排隊延時[29]。

目前，針對確定DTN提出的有代表性的路由算法利用網絡知識的情況如表1所示，選取典型的ED、CGR、EDLQ和CGR-ETO四種路由算法，在一個典型空間DTN場景中對路由算法的性能進行評估。

表1　確定DTN路由算法利用網絡知識情況比較

演化圖路由、空時路由、ED路由均未考慮網絡的排隊延時，因此，路由計算結果一致，我們選取ED路由算法作比較。CGR通過消息的預計容量消耗和接觸的殘余容量考慮接觸的容量限制，因此，其性能會比ED好，但其仍然沒有考慮網絡的排隊延時。CGR-ETO考慮了全網的排隊延時，但為了簡化仿真，設定CGR-ETO僅考慮本地節點的排隊延時，并使其與EDLQ進行比較。EDAQ與LP由于實現復雜度較高，因此不在本文的比較范圍之內。

2　性能評估

選取圖2所示的典型空間DTN場景對4種路由算法進行性能評估，其中，節點1表示航天器，為信源，節點2表示地面站1或中繼衛星1，節點3表示地面站2或中繼衛星2(由于中繼衛星是透明轉發，因此可以看作航天器直接與中繼衛星的地面站相連)，節點4表示任務運行中心，為信宿[29]。節點1與節點2和節點3之間的通信鏈路用虛線表示表明這些鏈路是斷續可用的，節點4與節點2和節點3之間的通信鏈路始終連通。圖2所示的拓撲雖然簡單，但代表了一個典型的地球軌道任務場景。

圖2　典型空間DTN場景Fig.2　A typical space DTN scenario

在OPNET網絡仿真軟件中對圖2所示的空間DTN場景進行了建模，并實現了ED、CGR、EDLQ和CGR-ETO四種路由算法。由于鏈路傳播延時和通信誤碼率對路由算法的影響較小，而路由算法主要受鏈路斷續連接的影響，因此，為降低仿真復雜度，假定所有通信鏈路的傳播延時和通信誤碼率可以忽略不計，而主要評估路由算法在鏈路斷續連接情況下的性能。

設定節點1產生數據，數據的優先級相同。路由算法的任務即在鏈路斷續可用的情況下找出到達節點4的延時最優路徑。路由算法在消息產生時或收到消息時做出路由轉發決策，并將消息添加到鄰節點對應的待發送隊列中，例如節點1會為節點2和節點3維護兩個待發送隊列。若待發送隊列對應的鏈路當前可用，即馬上發送，若鏈路當前不可用，那么等待鏈路可用時發送。待發送隊列采用先入先出機制。

假設束(束為DTN傳輸單位)的載荷大小為100 kbyte，且束的預計容量消耗(為實際占用的通信容量)為107.235 kbyte(由于束在下層協議會被分段，并增加其他協議頭部，因此束的預計容量消耗會大于束的載荷大小)[29]。

接觸計劃的設定按照從簡單到復雜的原則，從而逐漸顯示出低級路由算法存在的問題和高級路由算法的優勢。首先，在一個沒有重疊的接觸計劃下評估四種路由算法的性能，在這個接觸計劃下，可以看出CGR的預計容量消耗和殘余容量消耗所起的作用；然后，在一個較復雜的有重疊的接觸計劃下評估4種路由算法的性能，在這個接觸計劃下，可以看出考慮排隊延時與不考慮排隊延時的區別。路由性能的分析采用微觀(Microscopic)和宏觀(Macroscopic)相結合的方式，微觀分析針對每個束進行，宏觀分析主要分析路由算法的平均端到端延時和束投遞完成率性能。

2.1無重疊的接觸計劃

表2為無重疊的接觸計劃及其鏈路特性，其中鏈路1-3有兩次接觸，接觸容量同時也以能夠發送的束的數量表示。

表2　無重疊的接觸計劃及鏈路特性

圖3為接觸計劃無重疊時ED的性能。節點1一共產生了15個束，在圖3的左側用實心菱形表示。生成的束在什么時刻經由哪個中間節點(節點2還是節點3)最終投遞到節點4用矩形表示，實心矩形表示經由節點2投遞，虛心矩形表示經由節點3投遞。鏈路1-2和鏈路1-3的接觸在圖3的底部表示。

由于ED路由算法沒有考慮接觸的容量限制，也沒有考慮排隊延時，因此，ED將產生的所有的束都通過鏈路1-3經由節點3發送到節點4。ED選擇節點3的原因是因為僅考慮當前消息的話，通過鏈路1-3的接觸1會最早投遞當前消息?？梢钥闯鲈诮涍^鏈路1-3的兩個接觸后，ED仍然沒有將產生的15個束投遞完畢，而僅投遞了7個束。盡管空間DTN的鏈路調度一般具有周期性，未投遞的束可以繼續等待鏈路1-3的下一次接觸機會，但這大大增加了數據投遞的延時，同時，對于通信帶寬更大的鏈路1-2卻沒有利用。

接觸計劃無重疊時，CGR、EDLQ和CGR-ETO三種路由算法的性能相同，如圖4所示。由于EDLQ和CGR-ETO均考慮了排隊延時，因此其路由性能是最好的。CGR考慮了接觸的容量限制，在接觸計劃沒有重疊時，其性能與EDLQ和CGR-ETO相當。對于CGR，在為序號3的束計算路徑時，由于鏈路1-3的接觸1的殘余容量已經不足以完成束的發送，CGR在進行路由計算時，將不再考慮鏈路1-3的接觸1，因此，CGR會選擇鏈路1-2來轉發束3。在為束14計算路徑時，由于鏈路1-2的接觸的容量已經耗盡，CGR會選擇鏈路1-3來轉發束。

圖3　接觸計劃無重疊時ED的性能Fig.3　Performance of ED under non-overlapping contact plan

圖4　接觸計劃無重疊時CGR、EDLQ和CGR-ETO的性能Fig.4　Performance of CGR, EDLQ and CGR-ETO under non-overlapping contact plan

圖5為接觸計劃無重疊時，不同路由算法的平均端到端延時性能。由于ED沒有考慮排隊延時，所以其平均端到端延時最大，CGR通過考慮接觸容量限制，獲得了與EDLQ和CGR-ETO相同的平均端到端延時性能。

圖6為接觸計劃無重疊時，不同路由算法的束投遞完成率性能隨時間的變化情況。某時刻的束投遞完成率為當前投遞成功的束的數量與待投遞的束的總數量之比。由于ED沒有考慮排隊延時，不能充分利用可用通信鏈路，因此，其束投遞完成率最低，而其他三種路由算法的束投遞完成率相同，且優于ED,在109 s時，將所有的束都投遞成功。

圖5　接觸計劃無重疊時路由算法的平均端到端延時Fig.5　Average end-to-end delay of routing algorithms under non-overlapping contact plan

圖6　接觸計劃無重疊時路由算法的束投遞完成率Fig.6　Bundle delivery completion ratio of routing algorithms under non-overlapping contact plan

2.2有重疊的接觸計劃

為了更進一步地評估不同路由算法的性能，選用表3所示有重疊的接觸計劃。

圖7為ED在接觸計劃有重疊時的性能。由于較接觸計劃沒有重疊時，鏈路1-3所有接觸的容量總和增大，因此，ED一共投遞了12個束，但仍然沒有將產生的所有15個束投遞成功。由于ED沒有考慮接觸的容量限制和排隊延時，其始終選擇通過鏈路1-3轉發所有產生的束，而對于通信帶寬更大的鏈路1-2，ED仍然沒有利用。

表3　有重疊的接觸計劃及鏈路特性

圖7　接觸計劃有重疊時ED的性能Fig.7　Performance of ED under overlapping contact

由于考慮了接觸的容量限制，在接觸計劃有重疊時，CGR的路由性能較ED有一定提高，如圖8所示。在鏈路1-3的接觸1的容量耗盡后，CGR通過選擇鏈路1-2的接觸來完成束的轉發，并在140 s內將產生的所有15個束投遞成功。CGR將束1～8均通過鏈路1-3的接觸1轉發，這是因為CGR未考慮網絡的排隊延時，選擇通過鏈路1-3轉發僅僅是因為鏈路1-3接觸1的開始時間早于鏈路1-2接觸的開始時間。雖然CGR成功投遞了產生的所有15個束，但束的投遞順序被打亂了，束1～4首先被投遞，束5～7與束9～15同時被投遞，束8最后被投遞。實際上，束8可以通過鏈路1-2的接觸被更早地投遞。

圖8　接觸計劃有重疊時CGR的性能Fig.8　Performance of CGR under overlapping contact plan

由于考慮了排隊延時，EDLQ和CGR-ETO的路由性能最好，如圖9所示。EDLQ在每次計算束的轉發路徑時，會考慮當前待發送隊列中的數據，將發送完當前隊列中數據所花費的時間考慮進束的最早投遞時間。CGR-ETO每次決定一個束的轉發路徑并將其添加進對應待發送隊列后，會為對應的接觸更新ETO變量，從而考慮排隊延時。從圖9可以看出，EDLQ和CGR-ETO的投遞順序沒有被打亂，且整體的投遞時間更早。

圖9　接觸計劃有重疊時EDLQ、CGR-ETO的性能Fig.9　Performance of EDLQ and CGR-ETO under overlapping contact plan

圖10為接觸計劃有重疊時，不同路由算法的平均端到端延時性能。由于ED沒有考慮排隊延時，所以其平均端到端延時最大。CGR雖然考慮了接觸容量限制，但仍然沒有考慮排隊延時，其平均端到端延時性能略差于EDLQ和CGR-ETO。

圖11為接觸計劃有重疊時，不同路由算法的束投遞完成率性能隨時間的變化情況。由于ED沒有考慮排隊延時，不能充分利用可用通信鏈路，因此，其束投遞完成率最低。CGR雖然考慮了接觸容量限制，但仍然沒有考慮排隊延時，也不能充分利用通信鏈路，因此，其束投遞完成率略差于EDLQ和CGR-ETO的束投遞完成率。CGR在84 s時，將所有的束都投遞成功，而EDLQ和CGR-ETO在76 s時即將所有束投遞成功。

圖10　接觸計劃有重疊時路由算法的平均端到端延時Fig.10　Average end-to-end delay of routing algorithms under overlapping contact plan

圖11　接觸計劃有重疊時路由算法的束投遞完成率Fig.11　Bundle delivery completion ratio of routing algorithms under overlapping contact plan

2.3討論

從以上的仿真評估中可以看出，ED由于沒有考慮排隊延時和接觸的容量限制，路由性能最差，具體體現在ED的平均端到端延時較大，以及束投遞完成率較低。CGR由于考慮了接觸的容量限制，在接觸計劃無重疊時的路由性能與EDLQ和CGR-ETO相當；但當接觸計劃有重疊時，由于沒有考慮排隊延時，CGR的路由性能不如EDLQ和CGR-ETO。從目前的仿真實例來看，EDLQ與CGR-ETO的路由性能相當，具體表現在它們的平均端到端延時較低，且束投遞完成率較高。平均端到端延時較低可以使消息傳輸具有較高的實時性，而束投遞完成率較高可以使消息傳輸的吞吐量較高。

對于圖2所示的地球軌道網絡，當節點1的航天器為一顆遙感衛星時，較高的路由性能可以帶來如下好處：第一，較高的實時性可以使地面更早地獲得遙感圖像信息，這可以使地面決策人員更早地做出決策，爭取寶貴的時間；第二，較高的吞吐量可以使地面獲得更多的遙感圖像信息，這可以使地面決策人員基于更多的信息做出更優的決策。

文獻[25]根據利用網絡知識的多少為DTN提出的不同路由算法對空間DTN路由算法的理論研究具有重要意義。由于實際實現路由算法時面臨種種制約，因此，現實中的路由算法應該基于部分網絡知識做出盡量優化的決策。CGR作為DTN軟件實現——行星際覆蓋網絡(Interplanetary Overlay Network，ION)[30]采用的路由算法，是專門為實際實現而設計的，且已經在大量的在軌試驗中驗證了其有效性[6,31]。CGR-ETO作為ION目前最先進的路由算法，對于實際實現空間DTN具有重要的參考意義。

目前，針對空間DTN路由算法進行評估的網絡場景均較簡單，未來應該在較復雜的空間DTN場景中對路由算法進行更詳盡的評估。同時，空間DTN的存儲和通信資源較有限，網絡擁塞不可避免，未來還應在空間DTN擁塞控制問題上進行進一步地研究。

3　結束語

未來的空間信息網絡具有時空跨度大和網絡節點分布稀疏等特點，從而形成一個典型的空間DTN，路由技術是空間DTN數據傳輸功能的重要基礎，本文主要針對空間DTN路由算法的性能進行了分析評估。從仿真評估的結果可以看出，ED的路由性能最差，CGR的路由性能次之，EDLQ和CGR-ETO的路由性能相當。未來針對空間DTN路由算法的研究應該在更復雜的網絡場景中進行，同時，需要關注空間DTN的擁塞控制問題。

References)

[1]沈榮駿. 中國天地一體化航天互聯網構想[J]. 中國工程科學，2006，8(10)：19-30.

SHEN R J.Some thoughts of Chinese integrated spaceground network system[J]. Engineering Science，2006，8(10)：19-30 (in Chinese).

[2]閔士權. 中國天基綜合信息網構想[J]. 航天器工程，2013，22(5)：1-14.

MIN S Q.An idea of China′s space-based integrated information network[J]. Spacecraft Engineering, 2013, 22(5): 1-14 (in Chinese).

[3]BURLEIGH S，CERF V G，CROWCROFT J，et al. Space for internet and internet for space[J]. Ad. Hoc. Networks，2014，23：80-86.

[4]BURLEIGH S，HOOKE A，TORGERSON L，et al. Delay-tolerant networking: an approach to interplanetary internet[J]. IEEE Communications Magazine，2003，41(6)：128-136.

[5]CERF V，BURLEIGH S，HOOKE A，et al. Delay-tolerant networking architecture，RFC 4838[EB/OL]. (2007-04)[2015-09-16]. http:∥tools.ietf.org/html/rfc4838.

[6]燕洪成, 張慶君, 孫勇, 等. 延遲/中斷容忍網絡技術及其在行星際因特網中的應用[J]. 航天器工程, 2014, 23(2): 114-123.

YAN H C，ZHANG Q J，SUN Y，et al. Delay/disruption tolerant network and its application to interplanetary internet[J]. Spacecraft Engineering，2014，23(2)：114-123 (in Chinese).

[7]ISRAEL D，CORNWELL D. Disruption tolerant networking demonstrations over LLCD′s optical links[EB/OL].(2014-02)[2015-09-16]. http:∥www.ipnsig.org/wp-content/uploads/2014/02/LLCD-DTN-Demonstration-IPNSIG-Final.pdf.

[8]Space-Data Routers[EB/OL]. 2010[2015-09-16]. http:∥www.spacedatarouters.eu.

[9]SUZUKI K，INAGAWA S，LIPPINCOTT J，et al. JAXA-NASA interoperability demonstration for application of DTN under simulated rain attenuation[C]∥The 13th International Conference on Space Operations (SpaceOps 2014)，Pasadena，USA，May 5-9，2014：1-13.

[10]Consultative Committee for Space Data Systems (CCSDS). Solar system internetwork (SSI) architecture，CCSDS 730.1-G-1[R]. Washington：CCSDS，2014.

[11]Consultative Committee for Space Data Systems (CCSDS). [EB/OL][2015-09-16]. http:∥public.ccsds.org/publications/scps.html.

[12]Consultative Committee for Space Data Systems (CCSDS). Rationale，scenarios，and requirements for DTN in space，CCSDS 734.0-G-1[R]. Washington：CCSDS，2010.

[13]袁孝康. 天基綜合信息網絡構想[J]. 上海航天, 2001(1): 12-15.

YUAN X K.Architecture of space base synthetic information networks[J]. Aerospace Shanghai，2001(1)：12-15 (in Chinese).

[14]FALL K. A delay-tolerant network architecture for challenged internets[C]∥ACM SIGCOMM 2003，Karlsruhe，Germany，August 25-29，2003：27-34.

[15]CAINI C, CRUICKSHANK H, FARRELL S, et al. Delay and disruption-tolerant networking (DTN)：an alternative solution for future satellite networking applications[J]. Proceedings of the IEEE，2011，99(11)：1980-1997.

[16]APOLLONIO P，CAINI C. DTN LEO satellite communications through ground stations and GEO relays[C]∥The 5th International ICST Conference (PSATS 2013)，Toulouse，France，June 27-28，2013：1-12.

[17]林闖，董揚威，單志廣. 基于DTN的空間網絡互聯服務研究綜述[J]. 計算機研究與發展，2014，51(5)：931-943.

LIN C，DONG Y W，SHAN Z G. Research on space internetworking service based on DTN[J]. Research and Development，2014，51(5)：931-943 (in Chinese).

[18]盧勇，趙有健，孫富春，等. 衛星網絡路由技術[J]. 軟件學報，2014，25(5)：1085-1100.

LU Y, ZHAO Y J, SUN F C, et al. Routing techniques on satellite networks[J]. Journal of Software，2014，25(5)：1085-1100 (in Chinese).

[19]蘇金樹，胡喬林，趙寶康，等. 容延容斷網絡路由技術[J]. 軟件學報，2010，21(1)：119-132.

SU J S，HU Q L，ZHAO B K，et al. Routing techniques on delay/disruption tolerant networks[J]. Journal of Software，2010，21(1)：119-132(in Chinese).

[20]FERREIRA A. Building a reference combinatorial model for MANETs[J]. IEEE Network，2004，18(5)：24-29.

[21]王彥，劉波，虞萬榮，等. 基于演化圖的導航星座星間路由算法[J]. 中國空間科學技術，2012，32(5)：76-83.

WANG Y，LIU B，YU W R，et al. Routing algorithm for navigation constellation based on evolving graph model[J]. Chinese Space Science and Technology，2012，32(5)：76-83 (in Chinese).

[22]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，2004.

[23]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.

[24]王占偉，王海濤，鄒光南. 面向空間容遲容斷網絡的路由算法研究[J]. 航天器工程，2013，22(3)：62-66.

WANG Z W，WANG H T，ZOU G N. Analysis of routing algorithm for space delay/disruption tolerant network[J]. Spacecraft Engineering，2013，22(3)：62-66 (in Chinese).

[25]JAIN S，FALL K，PATRA R. Routing in a delay tolerant network[C]∥ACM SIGCOMM 2004, Portland, USA, August 30-September 3，2004：145-158.

[26]BURLEIGH S C. Dynamic routing for delay-tolerant networking in space flight operations[C]∥The 10th International Conference on Space Opereations (SpaceOps 2008)，Heidelberg，Germany，May 12，2008：1-9.

[27]BURLEIGH S. Contact graph routing, IRTF Internet-Draft, draft-burleigh-dtnrg-cgr-01[EB/OL].[2015-09-16].http:∥tools.ietf.org/html/draft-burleigh-dtnrg-cgr-01.

[28]BEZIRGIANNIDIS N，TSAPELI F. Towards flexibility and accuracy in space DTN communications[C]∥The 8th ACM MobiCom workshop on Challenged Networks (CHANTS′13)，Miami，USA，September 30，2013：43-48.

[29]BEZIRGIANNIDIS N，CAINI C，MONTENERO D 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：17-23.

[30]Interplanetary Overlay Network (ION)[EB/OL]. (2015-5)[2015-09-16]. http:∥sourceforge.net/projects/ion-dtn.

[31]ARANITI G，BEZIRGIANNIDIS N，BIRRANE E，et al. Contact graph routing in DTN space networks: overview，enhancements and performance[J]. IEEE Communications Magazine，2015，35(3)：38-46.

(編輯：車曉玲、范真真)

Performanceevaluation of routing algorithms on space delay/disruption tolerant networks

YAN Hongcheng*，GUO Jian，ZHANG Hongjun

Institute of Spacecraft System Engineering, China Academy of Space Technology, Beijing 100094, China

Performance of routing algorithms on space delay/disruption tolerant networks (DTN) was evaluated to provide design reference and advices for future design of routing techniques on space DTN. Firstly, routing algorithms applicable to space DTN were analyzed and compared in aspect of utilization amount of network knowledege. Then, from microscopic and macroscopic aspects, four typical space DTN routing algorithms, which are earliest delivery(ED), earliest delivery with local queue(EDLQ), contact graph routing(CGR)and contact graph routing earliest transmission opportunity(CGR-ETO), were evaluated by simulations in a typical space DTN scenario with different contact plan configurations. Finally, evaluation results were analyzed and summarized, and future research issues about routing algorithms on space DTN were also discussed. Simulation results indicate that from aspects of end-to-end delay and bundle delivery completion ratio, the performance of CGR is better than ED while the performance of EDLQ and CGR-ETO are the same best.

space delay/disruption tolerant networks；routing algorithms；ED；EDLQ；CGR；CGR-ETO；performance evaluation

10.16708/j.cnki.1000-758X.2016.0038

2015-10-08；

2015-11-11；錄用日期：2016-05-11；

時間：2016-07-1213:26:55

http:∥www.cnki.net/kcms/detail/11.1859.V.20160712.1326.007.html

國家自然科學基金(91438102)

燕洪成(1985-)，男，工程師，yanhc519@163.com，主要研究方向為航天器信息系統、空間信息網絡

V44；TP393

A

http:∥zgkj.cast.cn

引用格式：燕洪成，郭堅，張紅軍. 空間延遲/中斷容忍網絡路由算法性能評估[J].中國空間科學技術, 2016,36(4)：38-46.

YANHC,GUOJ，ZHANGHJ.Performanceevaluationofroutingalgorithmsonspacedelay/disruptiontolerantnetworks[J].ChineseSpaceScienceandTechnology, 2016,36(4)：38-46(inChinese).

輸機會的接觸圖路由；性能評估