基于復(fù)制的DTN網(wǎng)絡(luò)路由算法研究

從立鋼，楊華民，王楊惠，底曉強(qiáng)

（1.長春理工大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長春　130022；2.長春理工大學(xué)化學(xué)與環(huán)境工程學(xué)院，長春　130022）

基于復(fù)制的DTN網(wǎng)絡(luò)路由算法研究

從立鋼1，楊華民1，王楊惠2，底曉強(qiáng)1

（1.長春理工大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長春130022；2.長春理工大學(xué)化學(xué)與環(huán)境工程學(xué)院，長春130022）

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

DTN；路由算法；網(wǎng)絡(luò)仿真

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

圖1　DTN網(wǎng)絡(luò)體系結(jié)構(gòu)

如圖1所示，與傳統(tǒng)網(wǎng)絡(luò)結(jié)構(gòu)不同，DTN網(wǎng)絡(luò)在應(yīng)用層與傳輸層之間添加了一個(gè)新層，即束層［2］（Bundle Layer），并制定了相應(yīng)的束協(xié)議［3］（Bundle Protocol）。束層及相關(guān)束協(xié)議的出現(xiàn)，解決了DTN網(wǎng)絡(luò)頻繁中斷、大延遲的問題，同時(shí)也為解決DTN網(wǎng)絡(luò)與其他現(xiàn)有網(wǎng)絡(luò)的兼容問題指明了方向。

1　DTN網(wǎng)絡(luò)應(yīng)用

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

目前DTN網(wǎng)絡(luò)的研究熱點(diǎn)主要集中在應(yīng)用/傳輸層協(xié)議、路由算法及協(xié)議、網(wǎng)絡(luò)安全、仿真環(huán)境研究等方面。本文主要針對基于復(fù)制的DTN路由算法展開研究。

2　基于復(fù)制的DTN路由算法

DTN網(wǎng)絡(luò)與傳統(tǒng)TCP/IP網(wǎng)絡(luò)在結(jié)構(gòu)和運(yùn)行環(huán)境上存在巨大差異，因此在路由上不能照搬TCP/IP的路由算法，為了解決這一難題，研究者提出了大量的DTN路由方案。根據(jù)機(jī)制不同可以被分成基于傳播、基于場景、基于固定設(shè)施和基于移動(dòng)設(shè)施四大類，其中基于傳播的DTN路由算法又可以被分為基于復(fù)制和基于傳播兩類［8］，本文主要研究基于復(fù)制的DTN路由算法。

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

2.1Epidemic路由算法

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

（1）當(dāng)網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)A、B進(jìn)入彼此通信范圍后，節(jié)點(diǎn)A將其所存儲(chǔ)的報(bào)文概要向量信息SVA（Summary Vector）發(fā)送給節(jié)點(diǎn)B；

（2）B節(jié)點(diǎn)獲得SVA后，將自身所存儲(chǔ)的報(bào)文概要向量信息SVB取反，并與SVA進(jìn)行邏輯與操作，通過與運(yùn)算結(jié)果B節(jié)點(diǎn)即可獲知A節(jié)點(diǎn)擁有但自身不具有的報(bào)文信息，隨后B節(jié)點(diǎn)將向A節(jié)點(diǎn)發(fā)送一個(gè)向量請求信息，要求A節(jié)點(diǎn)發(fā)送B節(jié)點(diǎn)不具備的報(bào)文信息；

（3）A節(jié)點(diǎn)獲得請求信息后，將B節(jié)點(diǎn)請求的報(bào)文信息發(fā)送給B即可，此時(shí)節(jié)點(diǎn)B獲得了A的信息。

圖2　Epidemic路由協(xié)議信息交換過程示意圖

2.2Spray and Wait路由算法

Spray and Wait路由算法最早由Thrasyvoulos Spyropoulos等人在國際會(huì)議SIGCOMM’05上首次提出。［10］該路由算法將數(shù)據(jù)報(bào)轉(zhuǎn)發(fā)分成兩個(gè)階段，分別是Spray階段和Wait階段，每個(gè)階段所采用的策略不同。

（1）Spray階段：該階段，數(shù)據(jù)源節(jié)點(diǎn)會(huì)產(chǎn)生L個(gè)數(shù)據(jù)報(bào)副本，并將L個(gè)副本發(fā)送給L個(gè)與源節(jié)點(diǎn)接觸的中繼節(jié)點(diǎn)；

（2）Wait階段：如果沒有在Spray階段找到目的節(jié)點(diǎn)，則路由算法進(jìn)入Wait階段，在該階段，每一個(gè)攜帶報(bào)文副本的節(jié)點(diǎn)將采用直接傳輸?shù)姆绞絺鬟f消息，指導(dǎo)報(bào)文傳遞給目的節(jié)點(diǎn)。

Spray and Wait路由算法將Epidemic算法與直接傳輸路由算法相結(jié)合，利用了直接傳輸路由算法的簡潔，同時(shí)限制了Epidemic路由算法對于資源的占用，集成了兩種算法的優(yōu)點(diǎn)。但是，對于Spray and Wait路由算法來說，確定Spray階段的L值是整個(gè)算法的關(guān)鍵，如果L值過大，將增加系統(tǒng)的開銷；如果L值過小，數(shù)據(jù)報(bào)的可達(dá)性會(huì)降低。在Spray and Wait路由算法基礎(chǔ)上又改進(jìn)出了Binary Spray and Wait算法，進(jìn)一步提高了該算法的性能。

2.3PROPHET路由協(xié)議

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

（1）encounter：當(dāng)節(jié)點(diǎn)A、B相遇機(jī)會(huì)越來越頻繁時(shí)，投遞概率值P（a，b）也應(yīng)逐漸變大，隨著每次相遇將更新投遞概率值，此時(shí)采用的計(jì)算公式為

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

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

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

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

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

2.4MaxProp路由協(xié)議

MaxProp路由算法由美國馬薩諸塞州大學(xué)的John Burgess等人在INFOCOM 2006上首次提出。［12］MaxProp路由算法引入了優(yōu)先級對數(shù)據(jù)進(jìn)行標(biāo)記，優(yōu)先級高的數(shù)據(jù)先發(fā)送，同樣優(yōu)先級低的數(shù)據(jù)先刪除，這樣大大提高了節(jié)點(diǎn)資源的利用率。

MaxProp路由算法由三部分組成，分別是相遇概率預(yù)估、數(shù)據(jù)交換管理和節(jié)點(diǎn)緩存管理。

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

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

（3）節(jié)點(diǎn)緩存管理用來管理節(jié)點(diǎn)內(nèi)存，在三種情況下節(jié)點(diǎn)可以刪除內(nèi)存中的數(shù)據(jù)，情況一：節(jié)點(diǎn)p中保存的數(shù)據(jù)包m已經(jīng)被傳送到目的節(jié)點(diǎn)，則m可以被刪除；情況二：在數(shù)據(jù)報(bào)m的生命周期內(nèi)，節(jié)點(diǎn)p與目的節(jié)點(diǎn)間沒有夠的帶寬完成數(shù)據(jù)傳輸，則m可以被刪除；情況三：即使節(jié)點(diǎn)P上的數(shù)據(jù)包m的副本被丟棄，該消息在其他節(jié)點(diǎn)上的副本也會(huì)被正常發(fā)送，則此種情況下m在p上的副本可以被刪除。節(jié)點(diǎn)緩存管理正式以以上三種規(guī)則作為刪除數(shù)據(jù)包的依據(jù)。

3　路由分析方法

3.1仿真工具簡介

本文所使用的仿真工具為ONE［13］（Opportunistic Network Environment，機(jī)會(huì)網(wǎng)絡(luò)仿真環(huán)境），該工具最早由芬蘭赫爾辛基阿爾托大學(xué)的Ari Ker?nen和J?rg Ott等人利用Java編程語言開發(fā)，目前由芬蘭阿爾托大學(xué)與德國墨尼黑工業(yè)大學(xué)共同維護(hù)，該工具在Windows、Linux和MacOS等平臺(tái)上都可以編譯運(yùn)行。

3.2仿真場景設(shè)置與評估參數(shù)

本文的仿真場景為市區(qū)內(nèi)行人所持智能手機(jī)所構(gòu)成的DTN網(wǎng)絡(luò)，每部智能手機(jī)都安裝了類似于DroidDTN的DTN客戶端。仿真場景主要參數(shù)如表1所示。

表1中的所有參數(shù)均在ONE仿真工具的配置文件中設(shè)置，除表中參數(shù)外，仿真的其他參數(shù)還包括網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)、路由協(xié)議、節(jié)點(diǎn)緩存等參數(shù)，這些參數(shù)將作為變量參與仿真，用于比較不同環(huán)境下的路由算法的性能。

表1　仿真場景設(shè)置

仿真工具ONE可以根據(jù)使要求生成相應(yīng)的報(bào)告文件，報(bào)告中的主要參數(shù)包括created、dropped、delivery_prob、latency_avg以及overhead_ratio等，其中：delivery_prob（網(wǎng)絡(luò)交付率）是指數(shù)據(jù)的成功到達(dá)率，即成功發(fā)送數(shù)據(jù)數(shù)量與產(chǎn)生數(shù)據(jù)總量的比值，該值越大代表性能越好；latency_avg（成功到達(dá)數(shù)據(jù)包的平均延遲）是指所有成功到達(dá)數(shù)據(jù)的延遲平均值；overhead_ratio（網(wǎng)絡(luò)開銷比率）由數(shù)據(jù)轉(zhuǎn)發(fā)總數(shù)和數(shù)據(jù)成功到達(dá)數(shù)決定，轉(zhuǎn)發(fā)總數(shù)越大，網(wǎng)絡(luò)開銷比率越大，相反成功到達(dá)數(shù)目越大，網(wǎng)絡(luò)開銷比率約??；以上三個(gè)參數(shù)可以比較全面的體現(xiàn)路由算法的具體性能，因此本文選擇以上三值作為路由算法性能的評估依據(jù)。

4　仿真結(jié)果分析

4.1節(jié)點(diǎn)密度對路由算法性能的影響

本節(jié)研究節(jié)點(diǎn)密度與路由算法性能之間的關(guān)系。以表1仿真場景為基礎(chǔ)，定義節(jié)點(diǎn)緩存為10M，消息生存周期為2h，通過修改節(jié)點(diǎn)數(shù)量，考察移動(dòng)節(jié)點(diǎn)密度對于不同DTN路由算法性能的影響，實(shí)驗(yàn)結(jié)果如圖3至圖5所示。

圖3　節(jié)點(diǎn)數(shù)量與傳輸成功率關(guān)系圖

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

圖4　節(jié)點(diǎn)數(shù)量與平均時(shí)延關(guān)系圖

圖4說明，隨著節(jié)點(diǎn)密度的增大，四種路由算法的數(shù)據(jù)包平均延遲均有所降低，其中Epidemic、PROPHET和Spray and Wait路由算法隨著節(jié)點(diǎn)的增加其數(shù)據(jù)包的平均延遲趨于穩(wěn)定；MaxProp算法數(shù)據(jù)包的平均延遲隨著節(jié)點(diǎn)數(shù)量的增加持續(xù)降低。

圖5　節(jié)點(diǎn)數(shù)量與路由開銷率關(guān)系圖

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

4.2節(jié)點(diǎn)緩存大小對路由算法性能的影響

本節(jié)研究節(jié)點(diǎn)緩存大小與路由算法性能之間的關(guān)系。以表1仿真場景為基礎(chǔ)，定義節(jié)點(diǎn)數(shù)量為300個(gè)，消息生存周期為2h，通過修改節(jié)點(diǎn)緩存大小，考察移動(dòng)節(jié)點(diǎn)緩存大小對于不同DTN路由算法性能的影響，實(shí)驗(yàn)結(jié)果如圖6至圖8所示。

圖6　節(jié)點(diǎn)緩存與傳輸成功率關(guān)系圖

圖6說明，網(wǎng)絡(luò)交付率方面，在節(jié)點(diǎn)密度相同的條件下，Epidemic和PROPHET兩種算法隨著節(jié)點(diǎn)緩存的不斷增加，其數(shù)據(jù)包的交付率也相應(yīng)增大；節(jié)點(diǎn)緩存大小對于MaxProp路由算法的影響分成兩個(gè)階段，當(dāng)緩存有5M變?yōu)?0M，數(shù)據(jù)包交付率顯著提高，但是從10M到30M，數(shù)據(jù)報(bào)交付率并無變化；對于Spray and Wait算法而言，節(jié)點(diǎn)緩存大小的變化對其數(shù)據(jù)包交付率并無影響。

圖7　節(jié)點(diǎn)緩存與平均時(shí)延關(guān)系圖

圖7說明，隨著節(jié)點(diǎn)緩存的變大，MaxProp路由算法數(shù)據(jù)包的平局延遲不斷變小，當(dāng)超過20M后平均延遲逐漸趨于穩(wěn)定；Epidemic、PROPHET和Spray and Wait三種路由算法數(shù)據(jù)包平均延遲的變化隨節(jié)點(diǎn)緩存變化不大。

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

圖8　節(jié)點(diǎn)數(shù)量與路由開銷率關(guān)系圖

4.3數(shù)據(jù)包生存時(shí)間對路由算法性能的影響

本節(jié)研究數(shù)據(jù)包生存時(shí)間與路由算法性能之間的關(guān)系。以表1仿真場景為基礎(chǔ)，定義節(jié)點(diǎn)數(shù)量為300個(gè)，節(jié)點(diǎn)緩存為10M，通過修改數(shù)據(jù)包生存時(shí)間，分析數(shù)據(jù)包生存時(shí)間與DTN路由算法性能之間的關(guān)系，實(shí)驗(yàn)結(jié)果如圖9至圖11所示。

圖9　數(shù)據(jù)包生存時(shí)間與傳輸成功率關(guān)系圖

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

圖10　數(shù)據(jù)包生存時(shí)間與平均時(shí)延關(guān)系圖

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

圖11　數(shù)據(jù)包生存時(shí)間與路由開銷率關(guān)系圖

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

5　結(jié)論

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

本文對基于復(fù)制的DTN路由算法的原理進(jìn)行了說明，并利用仿真工具分析了四種路由算法在不同環(huán)境下的具體表現(xiàn)，為DTN網(wǎng)絡(luò)的路由方案選擇提供了一定依據(jù)。

［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］呂春雷，佟首峰，姜會(huì)林，等.深空激光通信的研究現(xiàn)狀及關(guān)鍵技術(shù)［J］.長春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，35（1）：1-5.

［5］林闖，董揚(yáng)威，單志廣.基于DTN的空間網(wǎng)絡(luò)互聯(lián)服務(wù)研究綜述［J］.計(jì)算機(jī)研究與發(fā)展，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，F(xiàn)letcher R，Hasson A.DakNet：Rethinking connectivity in developing nations［J］.Computer，2004，37（1）：78-83.

［8］任智，黃勇，陳前斌.機(jī)會(huì)網(wǎng)絡(luò)路由協(xié)議［J］.計(jì)算機(jī)應(yīng)用，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］于海洋，楊華民，姜會(huì)林，等.一種全球覆蓋的多層星座鏈路分析［J］.長春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，37（3）：56-59.

［15］孫踐知，劉乃瑞，張迎新，等.機(jī)會(huì)網(wǎng)絡(luò)典型路由算法性能分析［J］.計(jì)算機(jī)工程，2011（16）：86-89.

［16］王朕，王新華，隋敬麒.機(jī)會(huì)網(wǎng)絡(luò)模擬器ONE及其擴(kuò)展研究［J］.計(jì)算機(jī)應(yīng)用研究，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，F(xiàn)irstly，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”計(jì)劃信息技術(shù)領(lǐng)域課題資助項(xiàng)目（2015AA015701）；吉林省科技發(fā)展計(jì)劃資助項(xiàng)目（20140101206JC）；吉林省計(jì)算中心公共計(jì)算平臺(tái)資助項(xiàng)目（20140101206JC-12）

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