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

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

機(jī)動通信網(wǎng)中的DTN路由協(xié)議研究

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

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

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

機(jī)動通信；延遲容忍網(wǎng)絡(luò)；路由協(xié)議

0 引言

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

DTN是Kevin Fall在2003年提出的一種新型的異步信息網(wǎng)絡(luò)結(jié)構(gòu)［4］，是在星際網(wǎng)絡(luò)的基礎(chǔ)之上發(fā)展而來，區(qū)別于普通網(wǎng)絡(luò)的特性在于其行星之間通信具有較高延遲和非連續(xù)的連接。目前，DTN網(wǎng)絡(luò)主要應(yīng)用于軍事戰(zhàn)爭、航天通信、災(zāi)難恢復(fù)和應(yīng)急搶險等方面，在惡劣的通信環(huán)境中有較強(qiáng)的適用性。

1 DTN路由協(xié)議分類

DTN結(jié)構(gòu)在應(yīng)用層和傳輸層之間添加了一個Bundle層［5］。Bundle層主要功能有保管傳遞和存儲轉(zhuǎn)發(fā)，是一個面向異步消息的覆蓋網(wǎng)。在DTN網(wǎng)絡(luò)中，主要目標(biāo)是最大可能地傳輸報文信息，而選取最短路徑或者節(jié)省開銷不是首要的選擇。

DTN網(wǎng)絡(luò)中的路由主要包括建立網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、維護(hù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和路由算法三個方面。本文將路由算法分為三類，分別是不基于先驗知識的路由方案(Nonknowledge-based Approach)、基于先驗知識的路由方案(Knowledge-based Approach)、基于社會網(wǎng)絡(luò)分析技術(shù)路由方案(Social-based Approach)［6，7］。同時也根據(jù)DTN內(nèi)部的消息隊列管理、消息復(fù)制和節(jié)點(diǎn)間消息的轉(zhuǎn)發(fā)機(jī)制進(jìn)行分類。

1.1 分類技術(shù)

1.1.1 隊列管理

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

①先進(jìn)先出原則(FIFO);

②目的無關(guān)原則(Destination Independent):QM只使用那些與目的節(jié)點(diǎn)不相關(guān)的參數(shù)，譬如跳數(shù)、轉(zhuǎn)發(fā)次數(shù)、消息大小等;

③目的相關(guān)原則(Destination Dependent):QM使用與目的節(jié)點(diǎn)相關(guān)參數(shù)。例如到達(dá)目的節(jié)點(diǎn)的路徑長度、延時等。

1.1.2 轉(zhuǎn)發(fā)機(jī)制

兩個節(jié)點(diǎn)在對方的通信范圍內(nèi)，會觸發(fā)轉(zhuǎn)發(fā)機(jī)制(Forwarding)。轉(zhuǎn)發(fā)機(jī)制通常是基于消息的優(yōu)先級來對消息進(jìn)行轉(zhuǎn)發(fā)，同時其作用時間較短，只在兩個節(jié)點(diǎn)相互接觸的時間之內(nèi)。通用的轉(zhuǎn)發(fā)機(jī)制有以下幾種:

①直接投遞，消息只傳輸給目的節(jié)點(diǎn)，不需要經(jīng)過中間節(jié)點(diǎn);

②總是轉(zhuǎn)發(fā)，消息全部被轉(zhuǎn)發(fā)。該策略的路由計算量小，但是會導(dǎo)致大量的消息被轉(zhuǎn)播。

③基于知識，根據(jù)當(dāng)前節(jié)點(diǎn)的環(huán)境(Contextual Information)、歷史(Historical Information)或者社會信息(Social Information)進(jìn)行消息的轉(zhuǎn)發(fā)。環(huán)境信息包含當(dāng)前節(jié)點(diǎn)的狀態(tài)，如電池、速度、動向等。歷史信息隨著時間而獲取，用于估計未來網(wǎng)絡(luò)行為、接觸時間等。社會信息描述使用者的關(guān)系用來預(yù)測社會行為，從而提高傳送效率。

1.1.3 復(fù)制機(jī)制

復(fù)制(Replication)機(jī)制用來控制消息副本的數(shù)量和提高拓?fù)涞聂敯粜?。可以發(fā)現(xiàn)當(dāng)節(jié)點(diǎn)接觸時，一個消息可以被轉(zhuǎn)發(fā)機(jī)制轉(zhuǎn)發(fā)，復(fù)制機(jī)制可以通過重新進(jìn)入隊列來復(fù)制多個副本。在DTN網(wǎng)絡(luò)中，消息副本在網(wǎng)絡(luò)中的數(shù)量會在一定程度上影響消息的投遞率。

①單個拷貝，信息從不復(fù)制;

②有限，消息復(fù)制的數(shù)目被控制;

③受控，只有條件達(dá)成是消息才能被復(fù)制;

④無限，對消息的復(fù)制無任何要求;

1.2 路由分類

本章路由協(xié)議的分類主要是根據(jù)上節(jié)介紹的隊列管理、轉(zhuǎn)發(fā)機(jī)制和復(fù)制機(jī)制。下面介紹一些典型的DTN路由協(xié)議。

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

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

PROPHET(Probabilistic Routing Protocol Using History of Encounters and Transitivity)使用可預(yù)測性傳輸作為標(biāo)準(zhǔn)來估算節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)的可能性，可以認(rèn)為是對傳染性路由協(xié)議的改進(jìn)。一個節(jié)點(diǎn)將消息轉(zhuǎn)發(fā)給預(yù)測性傳輸概率比它自己高的鄰居節(jié)點(diǎn)。隊列管理使用先進(jìn)先出原則，復(fù)制機(jī)制使用無限復(fù)制。

在MaxProp算法中，每個節(jié)點(diǎn)維護(hù)一張路由表，用來預(yù)測通過目前的鄰居節(jié)點(diǎn)到達(dá)其他節(jié)點(diǎn)的可能性。路由表通過鄰居節(jié)點(diǎn)和消息中提取的信息來維護(hù)。由此可知，轉(zhuǎn)發(fā)機(jī)制使用了歷史信息，復(fù)制機(jī)制使用了無限復(fù)制，隊列管理使用了目的無關(guān)原則。

2 DTN路由協(xié)議仿真

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

2.1 仿真場景及設(shè)置

網(wǎng)絡(luò)場景地圖是一個城市地區(qū)，共選擇125個網(wǎng)絡(luò)節(jié)點(diǎn)并對它們的運(yùn)行軌跡進(jìn)行了設(shè)置，模擬了道路、步行街、郵局、商店、公交、有軌電車等節(jié)點(diǎn)裝載工具，仿真的拓?fù)浣Y(jié)構(gòu)如圖1所示。所有節(jié)點(diǎn)共分為6個組，分別用字母p、c、w、t表示。其中p代表一組行人，c代表汽車，w代表另一組行人，t包括3組有軌電車，每一組運(yùn)行在不同的子區(qū)域。隨著公交和行人的隨機(jī)移動，網(wǎng)絡(luò)進(jìn)行自組網(wǎng)，并且消息的遠(yuǎn)端與目的端的鏈路會隨著節(jié)點(diǎn)的移動發(fā)生斷裂，這與DTN的特點(diǎn)一致。

圖1 仿真場景圖

2.2 仿真結(jié)果及分析

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

根據(jù)表2可以看出，這3種路由協(xié)議都具有較高的投遞成功率，而它們的路由開銷都很高，緩存時間較長。由于DTN網(wǎng)絡(luò)本身就不注重延遲和開銷，因此路由協(xié)議投遞成功率可以通過提高開銷和延時來換取。但是投遞成功率還是遠(yuǎn)低于普通無線網(wǎng)絡(luò)和戰(zhàn)術(shù)通信網(wǎng)絡(luò)的指標(biāo)要求。

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

PROPHET路由算法比傳染性路由算法的表現(xiàn)較好、平均跳數(shù)較低，這是由于PROPHET實際上是對傳染性路由協(xié)議的改進(jìn)，傳染性路由協(xié)議是無條件地向鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)，PROPHET路由算法是計算該鄰居節(jié)點(diǎn)的轉(zhuǎn)發(fā)數(shù)據(jù)的可能性，如果比自己高的話才會轉(zhuǎn)發(fā)，所以表現(xiàn)較好。

表1 三種網(wǎng)絡(luò)路由協(xié)議的仿真對比

通過以上分析，在通信環(huán)境復(fù)雜、穩(wěn)定性較低、期望投遞率較高的網(wǎng)絡(luò)中，采用節(jié)點(diǎn)間消息復(fù)制量無限制、節(jié)點(diǎn)存儲的關(guān)于鄰居節(jié)點(diǎn)、鏈路、轉(zhuǎn)發(fā)次數(shù)、跳數(shù)等信息越多，那么消息投遞的成功率會越高，但與此同時網(wǎng)絡(luò)的開銷也會增加，這也是DTN網(wǎng)絡(luò)中路由協(xié)議設(shè)計的難點(diǎn)。在網(wǎng)絡(luò)協(xié)議設(shè)計的工程實踐中，需要根據(jù)實際情況做出適當(dāng)?shù)恼壑小?/p>

3 機(jī)動環(huán)境下的應(yīng)用分析

機(jī)動通信網(wǎng)絡(luò)通常需要部署在戰(zhàn)場、災(zāi)難現(xiàn)場等惡劣的環(huán)境中。在這些惡劣環(huán)境中，通信節(jié)點(diǎn)時刻面臨干擾和毀傷打擊，一些重要信息例如戰(zhàn)場態(tài)勢、災(zāi)情信息即使在網(wǎng)絡(luò)遭受打擊時，仍需要完整、及時地發(fā)送給指揮節(jié)點(diǎn)。在這些場合中，機(jī)動通信網(wǎng)絡(luò)必須具有更高的抗毀性能。

目前的DTN路由算法尚不能直接應(yīng)用到機(jī)動通信環(huán)境中，它們的主要問題包括:

①網(wǎng)絡(luò)結(jié)構(gòu)單調(diào)。通常的MANET網(wǎng)絡(luò)路由協(xié)議設(shè)計時都假設(shè)網(wǎng)絡(luò)中的節(jié)點(diǎn)平等，這是出于簡單化設(shè)計的考慮，但是單一的網(wǎng)絡(luò)結(jié)構(gòu)在網(wǎng)絡(luò)毀傷后容易產(chǎn)生分割;

②路由方法單一，不能自適應(yīng)地調(diào)整，在某些特殊的應(yīng)用場合中，網(wǎng)絡(luò)拓?fù)渥兓^頻繁和多樣，需要更靈活的路由方法以保證較高的可靠性;

③路由安全方面的考慮較少。如果被敵方獲取通信節(jié)點(diǎn)，則可能竊取我方信息或者破壞整個通信網(wǎng)絡(luò);

④仿真結(jié)果表明DTN路由算法的投遞率仍然較低，不適應(yīng)機(jī)動通信網(wǎng)對通信高可靠性的要求。

因此機(jī)動通信環(huán)境下網(wǎng)絡(luò)的路由算法需要結(jié)合網(wǎng)絡(luò)頂層設(shè)計，采用跨層設(shè)計方案，優(yōu)先考慮抗毀性、安全性和自適應(yīng)能力等指標(biāo)。

4 結(jié)束語

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

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

［2］馬馳，孟錦，張宏．抗毀的混合移動自組織網(wǎng)路由策略[J]．計算機(jī)應(yīng)用，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］樊秀梅，單志廣，張寶賢，等．容遲網(wǎng)絡(luò)體系結(jié)構(gòu)及其關(guān)鍵技術(shù)研究[J]．電子學(xué)報，2008(01):161－170．

［6］薛靜鋒，陸慧梅，石琳．DTN路由技術(shù)研究綜述[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］張龍，周賢偉，王建萍，等．容遲與容斷網(wǎng)絡(luò)中的路由協(xié)議[J]．軟件學(xué)報，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，F(xiàn)ENG 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

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

2015－04－22

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