基于復制的DTN網絡路由算法研究

從立鋼，楊華民，王楊惠，底曉強

（1.長春理工大學計算機科學技術學院，長春　130022；2.長春理工大學化學與環境工程學院，長春　130022）

基于復制的DTN網絡路由算法研究

從立鋼1，楊華民1，王楊惠2，底曉強1

（1.長春理工大學計算機科學技術學院，長春130022；2.長春理工大學化學與環境工程學院，長春130022）

DTN是一種適用于挑戰環境的新型網絡，對長延遲、頻中斷等惡劣條件具有良好的適應性。目前，人們對于DTN網絡的研究熱點主要集中在傳輸協議、路由算法、安全防護等方面。本文針對基于復制的DTN路由算法展開研究，首先介紹了DTN的概念、結構、特點及應用，然后分析了四種典型路由算法的原理，最后利用仿真工具實現了對路由算法的仿真，并對不同條件下的算法性能進行了對比。實驗結果表明，節點密度、節點緩存和數據包生存時間等網絡因素對于算法的性能都有著顯著影響，不同路由算法均有其特定的適用場景。

DTN；路由算法；網絡仿真

DTN［1］是Delay/Disruption Tolerant Network的簡寫，被譯為延遲/中斷容忍網絡，由于網絡中斷是造成延遲的重要原因，所以一般將中斷容忍網絡歸為延遲容忍網絡一類，所以DTN一般特指延遲容忍網絡。DTN網絡概念最早由DTNRG（Delay Tolerant Network Research Group，延遲容忍網絡研究組）在2003年提出，試圖通過DTN網絡來解決星際網絡頻繁中斷、時延大的問題。隨后，在同年的SIGCOMM國際會議上，Kevin Fall發表了論文“A Delay-Tolerant Network Architecture for Challenged Internets”，該文章成為了DTN網絡研究領域的經典。

圖1　DTN網絡體系結構

如圖1所示，與傳統網絡結構不同，DTN網絡在應用層與傳輸層之間添加了一個新層，即束層［2］（Bundle Layer），并制定了相應的束協議［3］（Bundle Protocol）。束層及相關束協議的出現，解決了DTN網絡頻繁中斷、大延遲的問題，同時也為解決DTN網絡與其他現有網絡的兼容問題指明了方向。

1　DTN網絡應用

DTN概念一經提出，便吸引了大量機構和研究者的關注，目前，DTN網絡在空間激光通信［4］、星際網絡［5］、野生動物研究［6］等眾多領域都有廣泛應用，其中比較典型的包括：（1）2012年10月，NASA與ESA（European Space Agency，歐洲航空航天局）合作，利用DTN技術在國際空間站實現了對地面實驗室內樂高機器人的遠程控制；（2）印度等國為解決邊遠地區網絡無法覆蓋的問題，利用DTN在部分地區建立了DakNet網絡［7］，實現了偏遠地區網絡的覆蓋；（3）水下延遲容忍網絡項目SWIM［6］運用無線傳感網絡技術監視海洋鯨魚，其中大量使用了DTN相關技術。

目前DTN網絡的研究熱點主要集中在應用/傳輸層協議、路由算法及協議、網絡安全、仿真環境研究等方面。本文主要針對基于復制的DTN路由算法展開研究。

2　基于復制的DTN路由算法

DTN網絡與傳統TCP/IP網絡在結構和運行環境上存在巨大差異，因此在路由上不能照搬TCP/IP的路由算法，為了解決這一難題，研究者提出了大量的DTN路由方案。根據機制不同可以被分成基于傳播、基于場景、基于固定設施和基于移動設施四大類，其中基于傳播的DTN路由算法又可以被分為基于復制和基于傳播兩類［8］，本文主要研究基于復制的DTN路由算法。

基于復制的DTN路由算法雖然有多種，但是基本思想都是將所要傳遞的消息復制多個副本，將這些副本傳遞給遇到的尚未攜帶相關信息的其他節點，通過多次消息復制過程，直到將消息交付給目的節點。常見的基于復制的路由算法包括Epidemic、MaxProp、PROPHET、Spray and Wait、SEPR、Controlled Flooding等，本文選取其中最具代表性的四種，它們是Epidemic、MaxProp、PROPHET和Spray and Wait，分別介紹四種其算法基本原理，并根據仿真結果分析算法性能。

2.1Epidemic路由算法

Epidemic路由算法由杜克大學的Amin Vahdat和David Becker在文獻［9］中提出。如圖2所示，Epidemic路由協議的基本過程分為三個階段：

（1）當網絡中任意兩個節點A、B進入彼此通信范圍后，節點A將其所存儲的報文概要向量信息SVA（Summary Vector）發送給節點B；

（2）B節點獲得SVA后，將自身所存儲的報文概要向量信息SVB取反，并與SVA進行邏輯與操作，通過與運算結果B節點即可獲知A節點擁有但自身不具有的報文信息，隨后B節點將向A節點發送一個向量請求信息，要求A節點發送B節點不具備的報文信息；

（3）A節點獲得請求信息后，將B節點請求的報文信息發送給B即可，此時節點B獲得了A的信息。

圖2　Epidemic路由協議信息交換過程示意圖

2.2Spray and Wait路由算法

Spray and Wait路由算法最早由Thrasyvoulos Spyropoulos等人在國際會議SIGCOMM’05上首次提出。［10］該路由算法將數據報轉發分成兩個階段，分別是Spray階段和Wait階段，每個階段所采用的策略不同。

（1）Spray階段：該階段，數據源節點會產生L個數據報副本，并將L個副本發送給L個與源節點接觸的中繼節點；

（2）Wait階段：如果沒有在Spray階段找到目的節點，則路由算法進入Wait階段，在該階段，每一個攜帶報文副本的節點將采用直接傳輸的方式傳遞消息，指導報文傳遞給目的節點。

Spray and Wait路由算法將Epidemic算法與直接傳輸路由算法相結合，利用了直接傳輸路由算法的簡潔，同時限制了Epidemic路由算法對于資源的占用，集成了兩種算法的優點。但是，對于Spray and Wait路由算法來說，確定Spray階段的L值是整個算法的關鍵，如果L值過大，將增加系統的開銷；如果L值過小，數據報的可達性會降低。在Spray and Wait路由算法基礎上又改進出了Binary Spray and Wait算法，進一步提高了該算法的性能。

2.3PROPHET路由協議

PROPHET路由算法最早由瑞典呂勒奧理工大學的Anders Lindgren等人首次提出，［11］PROPHET是Probabilistic Routing Protocol using History of Encounters and Transitivity的縮寫，該路由算法在Epidemic算法的基礎上進行改進，引入投遞概率值P（Delivery Predictabilities），避免泛洪似的數據分發方式，提高了網絡的效率。PROPHET路由算法中對于P值得計算可以分成encounter、age和transitive三部分，分別使用三個公式用于更新投遞概率值P，三部分的簡要說明如下：

（1）encounter：當節點A、B相遇機會越來越頻繁時，投遞概率值P（a，b）也應逐漸變大，隨著每次相遇將更新投遞概率值，此時采用的計算公式為

其中Pinit為初始化參數，范圍在（0，1］。

（2）age：如果A、B長時間未相遇，則需要定時更新P（a，b），該值將隨著不相遇的時間變長而不斷變小，此時采用的計算公式為

其中γ為一個常數，范圍為（0，1），k為P值距離上次更新的時間單元數。

（3）transitive：如果A與B時常相遇，B與C又時常相遇，那么A與C之間存在傳遞性聯通，則A與C之間投遞概率值得計算公式為

其中β為放大常數，取值范圍為［0，1］。

2.4MaxProp路由協議

MaxProp路由算法由美國馬薩諸塞州大學的John Burgess等人在INFOCOM 2006上首次提出。［12］MaxProp路由算法引入了優先級對數據進行標記，優先級高的數據先發送，同樣優先級低的數據先刪除，這樣大大提高了節點資源的利用率。

MaxProp路由算法由三部分組成，分別是相遇概率預估、數據交換管理和節點緩存管理。

（1）相遇概率預估部分用于計算網絡中節點間信息傳遞的概率。在初始階段將對每一個節點利用公式=1/（|s|—1）進行初始化賦值，該值代表該節點與相應節點進行信息傳遞的可能性，其中s代表一個DTN網絡，任意一個節點i將信息傳遞給另一個節點j的概率記為。當i與j實際相遇時值將增1，并重新平衡概率值，使各節點概率值更新，接下來利用公式（4）計算源節點到目的節點的成本，在進行數據傳遞時選擇成本較低的路徑。

（2）數據交換管理發生在節點間進行數據交換的過程中，在節點間進行數據交換時首先交換向量鏈表，該鏈表其中包括節點相遇概率、源節點信息、目的節點信息等，在鏈表信息傳遞結束后節點根據已知的信息完成數據信息的傳遞，傳遞過程中根據閾值來判斷數據包是否應該被發送，只有超過閾值的數據才被發送。

（3）節點緩存管理用來管理節點內存，在三種情況下節點可以刪除內存中的數據，情況一：節點p中保存的數據包m已經被傳送到目的節點，則m可以被刪除；情況二：在數據報m的生命周期內，節點p與目的節點間沒有夠的帶寬完成數據傳輸，則m可以被刪除；情況三：即使節點P上的數據包m的副本被丟棄，該消息在其他節點上的副本也會被正常發送，則此種情況下m在p上的副本可以被刪除。節點緩存管理正式以以上三種規則作為刪除數據包的依據。

3　路由分析方法

3.1仿真工具簡介

本文所使用的仿真工具為ONE［13］（Opportunistic Network Environment，機會網絡仿真環境），該工具最早由芬蘭赫爾辛基阿爾托大學的Ari Ker?nen和J?rg Ott等人利用Java編程語言開發，目前由芬蘭阿爾托大學與德國墨尼黑工業大學共同維護，該工具在Windows、Linux和MacOS等平臺上都可以編譯運行。

3.2仿真場景設置與評估參數

本文的仿真場景為市區內行人所持智能手機所構成的DTN網絡，每部智能手機都安裝了類似于DroidDTN的DTN客戶端。仿真場景主要參數如表1所示。

表1中的所有參數均在ONE仿真工具的配置文件中設置，除表中參數外，仿真的其他參數還包括網絡節點數、路由協議、節點緩存等參數，這些參數將作為變量參與仿真，用于比較不同環境下的路由算法的性能。

表1　仿真場景設置

仿真工具ONE可以根據使要求生成相應的報告文件，報告中的主要參數包括created、dropped、delivery_prob、latency_avg以及overhead_ratio等，其中：delivery_prob（網絡交付率）是指數據的成功到達率，即成功發送數據數量與產生數據總量的比值，該值越大代表性能越好；latency_avg（成功到達數據包的平均延遲）是指所有成功到達數據的延遲平均值；overhead_ratio（網絡開銷比率）由數據轉發總數和數據成功到達數決定，轉發總數越大，網絡開銷比率越大，相反成功到達數目越大，網絡開銷比率約小；以上三個參數可以比較全面的體現路由算法的具體性能，因此本文選擇以上三值作為路由算法性能的評估依據。

4　仿真結果分析

4.1節點密度對路由算法性能的影響

本節研究節點密度與路由算法性能之間的關系。以表1仿真場景為基礎，定義節點緩存為10M，消息生存周期為2h，通過修改節點數量，考察移動節點密度對于不同DTN路由算法性能的影響，實驗結果如圖3至圖5所示。

圖3　節點數量與傳輸成功率關系圖

圖3說明，在網絡交付率方面，節點密度對于不同路由算法的影響不盡相同。對于MaxProp算法，隨著節點數量的增加，其交付率顯著提高；相反，對于Epidemic和PROPHET算法而言，節點密度的增加非但沒有提高數據交付率，反而有所降低；而Spray and Wait算法的交付率對于結點密度并不敏感，隨著節點密度的增加交付率并無較大波動。

圖4　節點數量與平均時延關系圖

圖4說明，隨著節點密度的增大，四種路由算法的數據包平均延遲均有所降低，其中Epidemic、PROPHET和Spray and Wait路由算法隨著節點的增加其數據包的平均延遲趨于穩定；MaxProp算法數據包的平均延遲隨著節點數量的增加持續降低。

圖5　節點數量與路由開銷率關系圖

圖5說明，Spray and Wait路由算法的路由開銷與節點密度基本無關，在四種算法中一直保持較低水平；其余三種路由算法的路由開銷隨著節點密度的變大而持續增加，其中Epidemic和PROPHET兩種算法的增加趨勢最為明顯。

4.2節點緩存大小對路由算法性能的影響

本節研究節點緩存大小與路由算法性能之間的關系。以表1仿真場景為基礎，定義節點數量為300個，消息生存周期為2h，通過修改節點緩存大小，考察移動節點緩存大小對于不同DTN路由算法性能的影響，實驗結果如圖6至圖8所示。

圖6　節點緩存與傳輸成功率關系圖

圖6說明，網絡交付率方面，在節點密度相同的條件下，Epidemic和PROPHET兩種算法隨著節點緩存的不斷增加，其數據包的交付率也相應增大；節點緩存大小對于MaxProp路由算法的影響分成兩個階段，當緩存有5M變為10M，數據包交付率顯著提高，但是從10M到30M，數據報交付率并無變化；對于Spray and Wait算法而言，節點緩存大小的變化對其數據包交付率并無影響。

圖7　節點緩存與平均時延關系圖

圖7說明，隨著節點緩存的變大，MaxProp路由算法數據包的平局延遲不斷變小，當超過20M后平均延遲逐漸趨于穩定；Epidemic、PROPHET和Spray and Wait三種路由算法數據包平均延遲的變化隨節點緩存變化不大。

圖8說明，Spray and Wait路由算法的路由開銷與節點緩存大小基本無關，一直保持較低水平；其余三種路由算法的路由開銷隨著節點緩存的變大均有所降低。

圖8　節點數量與路由開銷率關系圖

4.3數據包生存時間對路由算法性能的影響

本節研究數據包生存時間與路由算法性能之間的關系。以表1仿真場景為基礎，定義節點數量為300個，節點緩存為10M，通過修改數據包生存時間，分析數據包生存時間與DTN路由算法性能之間的關系，實驗結果如圖9至圖11所示。

圖9　數據包生存時間與傳輸成功率關系圖

圖9說明，在網絡交付成功率方面，數據包生存時間的變化對于不同路由算法性能的影響并不一致。隨著生存時間的增加，Epidemic和PROPHET兩種路由算法的數據傳輸成功率不斷降低；Spray and Wait算法的數據傳輸成功率則不斷升高；對MaxProp算法而言，數據包生存時間的改變基本不會影響其數據傳輸成功率。

圖10　數據包生存時間與平均時延關系圖

圖10說明，四種路由算法的平均時延在數據包生存時間增大初期均隨之增大，但是隨著生存時間持續變大，路由算法數據包平均時延的變化又有所區別，其中PROPHET和MaxProp算法的平均時延將逐漸穩定；Spray and Wait的平均時延將一直增大；當數據包生存時間超過一定值（150分鐘）時，Epidemic的平均時延將出現降低趨勢。

圖11　數據包生存時間與路由開銷率關系圖

圖11說明，MaxProp和Spray and Wait路由算法的路由開銷率與數據包生存時間的大小基本無關；Epidemic和PROPHET路由算法的路由開效率隨著數據包生存時間的延長不斷變大。

5　結論

經過對不同條件下仿真結果的對比分析，主要得出以下結論：（1）網絡環境對于DTN路由算法性能的影響較大，在進行DTN網絡設計時應根據網絡環境和設計目標選擇合適的路由方案；（2）當節點較為稀疏時，Epidemic路由算法的性能與其他算法的性能較為接近，但是當節點變密時其性能急劇降低；（3）PROPHET路由算法的性能在大多數情況下強于Epidemic算法，但是并無出色表現，在各種條件下其數據傳輸成功率均維持較低水平；（4）MaxProp路由算法的性能在各種環境下均比較優秀，尤其體現在對于節點密度變化的容忍度上，無論節點密度增大還是減少，均保持了較高的數據傳輸成功率、較低的時延和較少的開銷；（5）Spray and Wait路由算法對于網絡環境也具有較好的適應性，在各種條件下均表現出優秀的性能，尤其是結點緩存較大時，其性能明顯優于其他路由算法。

本文對基于復制的DTN路由算法的原理進行了說明，并利用仿真工具分析了四種路由算法在不同環境下的具體表現，為DTN網絡的路由方案選擇提供了一定依據。

［1］Burleigh S，Hooke A，Torgerson L，et al.Delay-tol

erant networking：an approach to interplanetary Internet［J］.Communications Magazine，IEEE，2003，41（6）：128-136.

［2］Cerf V，Burleigh S，Hooke A，et al.RFC 4838：Delay-tolerant networking architecture［S］.USA：IETF，April 2007.

［3］ScottK，BurleighS.RFC5050：Bundleprotocol specification［S］.USA：IETF，November 2007.

［4］呂春雷，佟首峰，姜會林，等.深空激光通信的研究現狀及關鍵技術［J］.長春理工大學學報：自然科學版，2012，35（1）：1-5.

［5］林闖，董揚威，單志廣.基于DTN的空間網絡互聯服務研究綜述［J］.計算機研究與發展，2014（5）：931-943.

［6］P Juang，H Oki，W Yong，et al.Energy-efficient computing for wildlife tracking：design tradeoffs and earlyexperienceswithZebraNet［J］.AcmSigops Operating Systems Review，2002，36（5）：96-107.

［7］Pentland A，Fletcher R，Hasson A.DakNet：Rethinking connectivity in developing nations［J］.Computer，2004，37（1）：78-83.

［8］任智，黃勇，陳前斌.機會網絡路由協議［J］.計算機應用，2010（3）：723-728.

［9］A Vahdat，D Becker.Epidemic routing for partially connected ad hoc networks［R］.Technical Report CS-200006，Duke University，2000.

［10］T.Spyropoulos，K.Psounis，and C.S.Raghavendra.Spray and wait：an efficient routing scheme forintermittentlyconnectedmobilenetworks［C］. ACM SIGCOMM 2005，Philadelphia：ACM，2005.

［11］A.Lindgren，A.Doria，O.Schel.Probabilistic routing in intermittently connected networks［J］.SIGMOBILE Mob.Comput.Commun.Rev.2003，7（3）：19-20.

［12］J.Burgess，B.Gallagher，D.Jensen，et al.MaxProp：Routingforvehicle-baseddisruption-tolerant networks［J］.Proceedings-IEEE INFOCOM，2015（6）：1-11.

［13］AriKer?nen，J?rgOttandTeemuK?rkk?inen. The ONE simulator for DTN protocol evaluation［C］.SIMUTools'09：2ndInternationalConference onSimulationToolsandTechniques.Rome，March 2009.

［14］于海洋，楊華民，姜會林，等.一種全球覆蓋的多層星座鏈路分析［J］.長春理工大學學報：自然科學版，2014，37（3）：56-59.

［15］孫踐知，劉乃瑞，張迎新，等.機會網絡典型路由算法性能分析［J］.計算機工程，2011（16）：86-89.

［16］王朕，王新華，隋敬麒.機會網絡模擬器ONE及其擴展研究［J］.計算機應用研究，2012（1）：272-277.

The Research on DTN Routing Algorithm Based on Replication

CONG Ligang1，YANG Huamin1，WANG Yanghui2，DI Xiaoqiang1
（1.School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022；
2.School of Chemistry and Environmental Engineering，Changchun University of Science and Technology，Changchun 130022）

DTN is a new kind of network which is suitable for the challenge environment，and it has good adaptability to the long delay and frequency interruption.At present，the research hotspots of DTN are transmission protocol，routing algorithm，security protection and so on.This paper focuses on the research of DTN routing algorithm based on replication，Firstly，we introduce the DTN concept，structure，characteristics and applications，and then analyze the principle of four typical routing algorithm.Finally，we use simulation tools to simulate the routing algorithm，and compare the performance of the algorithm under different conditions.The experimental results show that the network factors，such as node density，node cache and TTL，have a significant impact on the performance of the algorithm，and the different routing algorithms have their specific application scenarios.

DTN；routing algorithm；network simulation

TP393

A

1672-9870（2016）04-0119-06

2016-03-21

“863”計劃信息技術領域課題資助項目（2015AA015701）；吉林省科技發展計劃資助項目（20140101206JC）；吉林省計算中心公共計算平臺資助項目（20140101206JC-12）

從立鋼（1983-），男，碩士，講師，E-mail：clg_cust@126.com