機動通信網中的DTN路由協議研究

李文，劉文，馮微，鄭相全

(1．中國電子系統設備工程公司研究所，北京 100000; 2．信息化部檔案館，北京 100000)

機動通信網中的DTN路由協議研究

李文1，劉文2，馮微1，鄭相全1

(1．中國電子系統設備工程公司研究所，北京 100000; 2．信息化部檔案館，北京 100000)

針對DTN網絡的核心機制－路由算法，分析了目前DTN路由算法的主要技術及其特點，包括隊列管理、復制機制和轉發機制。并且根據DTN網絡的特點，采用了幾種路由算法進行仿真。通過仿真表明，這幾種路由算法都具有較高的消息投遞成功率，但開銷較大，消息的無限復制會大大地占用節點的緩存空間。因此平衡DTN網絡中的開銷與投遞率還是一個設計的難點，需要根據實際網絡參數做出適當的折中。仿真結果表明，DTN路由不能直接應用于機動通信網，但是一些設計思想可以借鑒。

機動通信；延遲容忍網絡；路由協議

0 引言

現有的IP路由協議設計都基于以下前提:①傳輸時延短;②鏈路傳輸可靠性足夠高。DTN網絡的特點表明，傳統IP協議棧包括路由協議已經不適用于DTN網絡。因此，通過研究DTN網絡的特征，并分析專為DTN網絡設計的路由協議和算法，試圖找到適用于機動通信環境的路由協議。以Ad Hoc網絡為研究對象，因為Ad Hoc網絡隨著節點的移動進行隨機組網，同時鏈路也會隨著節點的移動間歇性地斷開。

DTN是Kevin Fall在2003年提出的一種新型的異步信息網絡結構［4］，是在星際網絡的基礎之上發展而來，區別于普通網絡的特性在于其行星之間通信具有較高延遲和非連續的連接。目前，DTN網絡主要應用于軍事戰爭、航天通信、災難恢復和應急搶險等方面，在惡劣的通信環境中有較強的適用性。

1 DTN路由協議分類

DTN結構在應用層和傳輸層之間添加了一個Bundle層［5］。Bundle層主要功能有保管傳遞和存儲轉發，是一個面向異步消息的覆蓋網。在DTN網絡中，主要目標是最大可能地傳輸報文信息，而選取最短路徑或者節省開銷不是首要的選擇。

DTN網絡中的路由主要包括建立網絡拓撲結構、維護網絡拓撲結構和路由算法三個方面。本文將路由算法分為三類，分別是不基于先驗知識的路由方案(Nonknowledge-based Approach)、基于先驗知識的路由方案(Knowledge-based Approach)、基于社會網絡分析技術路由方案(Social-based Approach)［6，7］。同時也根據DTN內部的消息隊列管理、消息復制和節點間消息的轉發機制進行分類。

1.1 分類技術

1.1.1 隊列管理

隊列管理機制—QM(Queue Management)是基于節點定義了隊列中關于處理消息的一系列的命令，隊列管理是由節點之間相互交換信息來獲取對環境的了解來驅動的。QM的命令針對所有消息，甚至是那些無法轉播的信息。當一條消息必須加入隊列而內存不夠時，根據隊列刪除策略命令來刪除消息，并提供存儲空間。考慮到DTN網絡具有較高的延遲，消息會在隊列中存在很長的時間;而另一方面，DTN節點的存儲空間有限，因此必須采用高效的隊列管理策略，以避免刪除有用信息。目前通用的QM策略有以下幾種:

①先進先出原則(FIFO);

②目的無關原則(Destination Independent):QM只使用那些與目的節點不相關的參數，譬如跳數、轉發次數、消息大小等;

③目的相關原則(Destination Dependent):QM使用與目的節點相關參數。例如到達目的節點的路徑長度、延時等。

1.1.2 轉發機制

兩個節點在對方的通信范圍內，會觸發轉發機制(Forwarding)。轉發機制通常是基于消息的優先級來對消息進行轉發，同時其作用時間較短，只在兩個節點相互接觸的時間之內。通用的轉發機制有以下幾種:

①直接投遞，消息只傳輸給目的節點，不需要經過中間節點;

②總是轉發，消息全部被轉發。該策略的路由計算量小，但是會導致大量的消息被轉播。

③基于知識，根據當前節點的環境(Contextual Information)、歷史(Historical Information)或者社會信息(Social Information)進行消息的轉發。環境信息包含當前節點的狀態，如電池、速度、動向等。歷史信息隨著時間而獲取，用于估計未來網絡行為、接觸時間等。社會信息描述使用者的關系用來預測社會行為，從而提高傳送效率。

1.1.3 復制機制

復制(Replication)機制用來控制消息副本的數量和提高拓撲的魯棒性。可以發現當節點接觸時，一個消息可以被轉發機制轉發，復制機制可以通過重新進入隊列來復制多個副本。在DTN網絡中，消息副本在網絡中的數量會在一定程度上影響消息的投遞率。

①單個拷貝，信息從不復制;

②有限，消息復制的數目被控制;

③受控，只有條件達成是消息才能被復制;

④無限，對消息的復制無任何要求;

1.2 路由分類

本章路由協議的分類主要是根據上節介紹的隊列管理、轉發機制和復制機制。下面介紹一些典型的DTN路由協議。

DTN網絡衡量的主要指標就是消息的成功投遞率。由于DTN網絡具有源端與目的端不存在端到端路徑、鏈路質量不穩定等特點。隨著節點的移動并與其他節點交互本節點存儲的信息。因此，消息在網絡中的副本量會影響它的投遞率;而另一方面，節點基于的先驗知識越多的話，那么對于數據投遞率會越高。傳染性路由協議(Epidemic Routing)、PROPHET路由協議和MaxProp路由協議，這幾種路由協議的復制機制是無限的，并且轉發機制是直接轉發的，或者是基于一些歷史或環境信息。下面簡要介紹一下這幾種路由協議:

傳染性路由協議(Epidemic Routing):這是一個泛洪模式的路由傳播過程。其主要工作模式為兩個接觸的網絡節點通過交換信息ID來交換自身未存儲的信息，從而達到信息交換的目的，直到將消息交換給目標節點。假設節點的緩沖區足夠大，那么消息將會像病毒一樣擴散到整個網絡。傳染性路由協議相對簡單，因為不需要對網絡進行了解。它的缺陷在于由于信息的大量復制、轉發導致了緩存、帶寬、能源等資源的極大消耗。傳染性路由協議是DTN網絡路由研究的開始。

PROPHET(Probabilistic Routing Protocol Using History of Encounters and Transitivity)使用可預測性傳輸作為標準來估算節點到達目的節點的可能性，可以認為是對傳染性路由協議的改進。一個節點將消息轉發給預測性傳輸概率比它自己高的鄰居節點。隊列管理使用先進先出原則，復制機制使用無限復制。

在MaxProp算法中，每個節點維護一張路由表，用來預測通過目前的鄰居節點到達其他節點的可能性。路由表通過鄰居節點和消息中提取的信息來維護。由此可知，轉發機制使用了歷史信息，復制機制使用了無限復制，隊列管理使用了目的無關原則。

2 DTN路由協議仿真

經過理論分析得出，消息在傳播的過程中消息的副本量在網絡中越多，那么消息的投遞成功率就會越高。本節將設置仿真場景，模擬移動Ad Hoc網絡的組網環境，對上述幾種路由協議進行仿真，將仿真結果與理論分析進行對比。觀察的主要參數有消息成功投遞率、平均時延和路由開銷等。

2.1 仿真場景及設置

網絡場景地圖是一個城市地區，共選擇125個網絡節點并對它們的運行軌跡進行了設置，模擬了道路、步行街、郵局、商店、公交、有軌電車等節點裝載工具，仿真的拓撲結構如圖1所示。所有節點共分為6個組，分別用字母p、c、w、t表示。其中p代表一組行人，c代表汽車，w代表另一組行人，t包括3組有軌電車，每一組運行在不同的子區域。隨著公交和行人的隨機移動，網絡進行自組網，并且消息的遠端與目的端的鏈路會隨著節點的移動發生斷裂，這與DTN的特點一致。

圖1 仿真場景圖

2.2 仿真結果及分析

在仿真過程中分別加載了3種路由協議并對其進行比較，比較結果如表1所示，仿真時間都為43 200 s。在仿真過程中，每一種路由協議下都發送1 461個報文，其余參數一致。

根據表2可以看出，這3種路由協議都具有較高的投遞成功率，而它們的路由開銷都很高，緩存時間較長。由于DTN網絡本身就不注重延遲和開銷，因此路由協議投遞成功率可以通過提高開銷和延時來換取。但是投遞成功率還是遠低于普通無線網絡和戰術通信網絡的指標要求。

從這3種路由算法進行比較可以看出，MaxProp路由算法傳輸報文最多，傳輸效率最高，路由開銷較低。這是因為在MaxProp路由算法中每個節點維護一張路由表，預測了通過當前節點的鄰居節點到達其他節點(包括目的節點)的可能性，在傳輸的過程中不是盲目地轉發，并且它的平均傳輸跳數也最低。

PROPHET路由算法比傳染性路由算法的表現較好、平均跳數較低，這是由于PROPHET實際上是對傳染性路由協議的改進，傳染性路由協議是無條件地向鄰居節點轉發數據，PROPHET路由算法是計算該鄰居節點的轉發數據的可能性，如果比自己高的話才會轉發，所以表現較好。

表1 三種網絡路由協議的仿真對比

通過以上分析，在通信環境復雜、穩定性較低、期望投遞率較高的網絡中，采用節點間消息復制量無限制、節點存儲的關于鄰居節點、鏈路、轉發次數、跳數等信息越多，那么消息投遞的成功率會越高，但與此同時網絡的開銷也會增加，這也是DTN網絡中路由協議設計的難點。在網絡協議設計的工程實踐中，需要根據實際情況做出適當的折中。

3 機動環境下的應用分析

機動通信網絡通常需要部署在戰場、災難現場等惡劣的環境中。在這些惡劣環境中，通信節點時刻面臨干擾和毀傷打擊，一些重要信息例如戰場態勢、災情信息即使在網絡遭受打擊時，仍需要完整、及時地發送給指揮節點。在這些場合中，機動通信網絡必須具有更高的抗毀性能。

目前的DTN路由算法尚不能直接應用到機動通信環境中，它們的主要問題包括:

①網絡結構單調。通常的MANET網絡路由協議設計時都假設網絡中的節點平等，這是出于簡單化設計的考慮，但是單一的網絡結構在網絡毀傷后容易產生分割;

②路由方法單一，不能自適應地調整，在某些特殊的應用場合中，網絡拓撲變化較頻繁和多樣，需要更靈活的路由方法以保證較高的可靠性;

③路由安全方面的考慮較少。如果被敵方獲取通信節點，則可能竊取我方信息或者破壞整個通信網絡;

④仿真結果表明DTN路由算法的投遞率仍然較低，不適應機動通信網對通信高可靠性的要求。

因此機動通信環境下網絡的路由算法需要結合網絡頂層設計，采用跨層設計方案，優先考慮抗毀性、安全性和自適應能力等指標。

4 結束語

DTN網絡和機動通信網絡的使用環境和網絡架構有很多相似之處。本文試圖通過分析DTN網絡的核心機制－路由算法，找到適合機動通信環境的組網機制。在分析了部分主流DTN路由算法的主要技術及其特點后，對幾種主流DTN路由算法進行仿真。仿真結果表明，這幾種路由算法的開銷較大，包括節點緩存空間和傳輸時延。而且傳輸成功率還不能達到機動通信網的指標要求。在機動通信環境下，不僅要求消息的投遞率高，同時也要保證消息的完整性和安全性，因此目前DTN網絡中路由算法無法直接應用到機動通信環境。下一步采用跨層設計，結合接入層和物理層參數可能是一個可行的方向。總而言之，如何設計具有高投遞率、低開銷、高穩定性和安全性的路由算法是一個巨大的挑戰，但是其應用前景廣泛，在應急通信以及機動通信環境將會發揮很廣泛的作用。

［1］陳林星，曾曦，曹毅．移動Ad Hoc網絡——自組織分組無線網絡技術(第2版)[M]．北京:電子工業出版社．

［2］馬馳，孟錦，張宏．抗毀的混合移動自組織網路由策略[J]．計算機應用，2011，11:2883－2886，2890．

［3］Daly Elizabeth M，Mads Haahr．The Challenges of Disconnected Delay-tolerant MANETs[J]．Ad Hoc Networks 8，2010:241－250．

［4］Kevin Fall．ADelay-tolerant Network Architecture for Challenged Internets[J]．In Proceedings of ACM SIGCOMM，2003:27－24．

［5］樊秀梅，單志廣，張寶賢，等．容遲網絡體系結構及其關鍵技術研究[J]．電子學報，2008(01):161－170．

［6］薛靜鋒，陸慧梅，石琳．DTN路由技術研究綜述[EB/ OL]．[2007－11－21]．中國科技論文在線，http:∥www.paper.edu.cn/releasepaper/content/200711－407.

［7］GONG Hai-gang，YU Ling-fei．Study on Routing Protocols for Delay Tolerant Mobile Networks[EB/OL]．International Journal of Distributed Sensor Networks，2013，http:∥www.hindawi.com/journals/ijdsn/2013/145727/.

［8］Danlei Yu，Young-Bae Ko．FFRDV:Fastest-Ferry Routing in DTN-enabled Vehicular Ad Hoc Networks[J]．ICACT，2009，2:1410－1414．

［9］張龍，周賢偉，王建萍，等．容遲與容斷網絡中的路由協議[J]．軟件學報，2010，10:2554－2572．

［10］Spyropoulos T，Psounis K，Raghavendra C．Spray and Wait:an Efficient Routing Scheme for Intermittently Connected Mobile Networks［C］∥in Proceedings of the 2005 ACM SIGCOMM Workshop on Delay-tolerant Networking (WDTN)，New York，NY，USA:252－259．

［11］Elizabeth Daly，Mads Haahr．Social Network Analysis for Routing in Disconnected Delay-Tolerant MANETs［C］∥MobiHoc’07，2007:32－40．

［12］Khalil Massri，Alessandro Vernata，Andrea Vitaletti．Routing Protocols for Delay Tolerant Networks:a Quantitative Evaluation［C］∥MSWiM’12，October 21－25，2012: 107－114．

Study on DTN Routing Protocols in Mobile Communication Network

LI Wen1，LIU Wen2，FENG Wei1，ZHENG Xiang-quan1
(1．Institute of China Electronics System Engineering Company，Beijing 1000000，China; 2．The Archives of Ministry of Information Technology，Beijing 1000000，China)

The circumstance of the mobile communication network is usually very severe，and interplanetary internet，sensor network，temporary network for disasters and sudden emergencies are considered as mobile communication network．These networks have such characteristics as large delay，intermittent link loss，low data rate，etc．The traditional IP protocol stack does not work well in these networks．To address these issues，Delay Tolerant Network(DTN)has been proposed．The Bundle layer in the DTN can mitigate these issues．Furthermore，appropriate routing protocols can improve the communication quality in the network．In this paper，some popular routing protocols are classified in terms of queue management，message replication and forwarding mechanism．These routing protocols have been simulated，with the key performance metrics and characteristics of the DTN．Finally，the simulation results show that DTN routing mechanism can’t be applied directly in mobile tactical network，but some ideas could be referred．

mobile communication;DTN;routing protocols

TP393

A

1003－3114(2015)05－15－4

10.3969/j.issn.1003－3114.2015.05.04

李文，劉文，馮微，等．機動通信網中的DTN路由協議研究［J］．無線電通信技術，2015，41(5):15－18．

2015－04－22

李文(1979—)，男，工程師，主要研究方向:無線通信。劉文(1982—)，女，碩士研究生，主要研究方向:指揮自動化。