DTN多播路由算法研究

黃勇萍 秦芳遠 葉佳寧 黃樑昌

（1.廣西民族師范學院數(shù)學與計算機科學系，廣西 崇左 532200；2.南方醫(yī)科大學網(wǎng)絡中心，廣東 廣州510515；3.廣東省地震局，廣東 廣州 510070；4.中國電信廣西公司，廣西 南寧 530015）

0 前言

DTN是延遲容忍網(wǎng)絡(Delay Tolerant Network)[1]的簡稱，由K.Fall等科學家于2002年在ICIR會議上提出來的。是從具有延時容忍特性的一類網(wǎng)絡中抽象出來的，最初來源于對星際因特網(wǎng)IPN(Inter-Planet Network)[2]項目的研究，把節(jié)點間的長延時、高不對稱性和間歇性連接作為主要的場景加以考慮。多播服務支持一組用戶的數(shù)據(jù)分發(fā)，許多潛在的DTN應用是基于多播方式的（例如軍事戰(zhàn)場、災難營救過程），通過多播技術，能夠提高網(wǎng)絡的資源利用率，降低通信成本，節(jié)約帶寬。多播技術在因特網(wǎng)和移動自組網(wǎng)中已有深入廣泛的研究。但是對于DTN，由于頻繁網(wǎng)絡斷開的特性使得DTN中的多播成為一個難題。網(wǎng)絡設計者若把適用于Internet中多播路由 （例如MOSPF和DVMRP）或 ad hoc網(wǎng)絡中的多播路由（例如AMRoute和ODMRP）直接應用于DTN環(huán)境，將面臨很大的障礙和挑戰(zhàn)。因此，DTN多播需要新的定義和路由設計，本文針對DTN的特點，對DTN的多播路由算法進行論述。

1 DTN概述

當前，Internet在互連全球異構的網(wǎng)絡上取得了巨大的成功，TCP/IP協(xié)議已成為互連網(wǎng)絡的事實標準。但是隨著計算機技術，微電子技術的發(fā)展以及軍事和其他領域研究的需要，越來越多的新型網(wǎng)絡開始出現(xiàn)，如陸地移動網(wǎng)絡、外來媒體網(wǎng)絡、軍事無線自組織網(wǎng)絡和無線傳感網(wǎng)絡等。這些受限網(wǎng)絡中存在共同的特點：高延遲、低數(shù)據(jù)率、間歇性連接、缺少端到端路徑、能量和存儲受限，給傳統(tǒng)的基于TCP/IP協(xié)議的端到端通信的Internet技術帶來嚴峻的挑戰(zhàn)。為了使這些受限網(wǎng)絡可以和現(xiàn)有的因特網(wǎng)互聯(lián)，并改善網(wǎng)絡的傳輸性能。K.Fall等科學家于2002年在ICIR會議上提出了延遲容忍網(wǎng)絡 (Delay Tolerant Network，DTN)的架構。

不同于現(xiàn)有的網(wǎng)絡，DTN的主要特征表現(xiàn)為：高延遲、低數(shù)據(jù)率、連接中斷頻繁以及較長的排隊時間等。對DTN來說，傳輸率可能是比較小的，延遲相對來說卻比較大，上行和下行的數(shù)據(jù)率很大程度上不對稱的。在一些特殊的情況下，單向鏈路的可能性也是存在的，如在軍用中同一些需要隱蔽的裝備進行通信。同時，在DTN中，連接中斷頻繁，而且中斷的原因也不一定全都是由于出錯導致的。尤其是在無線移動網(wǎng)絡中，連接中斷的原因主要來自節(jié)點的運動和低占空比操作。在一些傳統(tǒng)的分組網(wǎng)絡中，消息的排隊時間經(jīng)常對整個延時起決定性作用的。但在這些網(wǎng)中，排隊時間通常是非常短的，一般都遠遠小于1秒鐘。而且，當下一個節(jié)點無法連接時，數(shù)據(jù)包就會丟失。相比之下，DTN的連接斷開情況比較常見，節(jié)點的排隊時間相對而言比較大，有可能達到幾個小時甚至幾天。[3]

2 DTN多播服務技術應用與發(fā)展

多播服務支持一組用戶的數(shù)據(jù)分發(fā)。隨著通信網(wǎng)絡的發(fā)展以及通信研究領域的深入，許多潛在的DTN應用是基于多播方式的，例如在軍事戰(zhàn)場中，利用多播技術可以將控制中心的命令快速、可靠地發(fā)送到各個現(xiàn)場指揮基地，實現(xiàn)士兵之間的有關戰(zhàn)場周邊環(huán)境信息的共享；在災難營救過程中，通過多播技術，可以快速地實現(xiàn)營救工作者之間共享傷者有關的信息以及現(xiàn)場可能存在的一些潛在危險。[4]另一方面，利用多播技術能夠提高網(wǎng)絡的資源利用率，降低通信成本，節(jié)約帶寬。多播技術在因特網(wǎng)和移動自組網(wǎng)中已有深入廣泛的研究。但是對于DTN，由于頻繁網(wǎng)絡斷開的特性使得DTN中的多播成為一個難題。網(wǎng)絡設計者若把適用于Internet中多播路由 （例如MOSPF和DVMRP）或 ad hoc網(wǎng)絡中的多播路由（例如AMRoute和ODMRP）直接應用于DTN環(huán)境，將面臨很大的障礙和挑戰(zhàn)。首先，在DTN多播消息傳輸過程中，保持多播結構（樹形或者是網(wǎng)狀結構）的連通性是困難的。第二，由于DTN自身的特點，多播結構不斷發(fā)生變化而引起中斷從而導致消息傳輸時發(fā)生頻繁失敗或大的端到端延遲。第三，傳統(tǒng)多播路由方案的設計是基于網(wǎng)絡連通性較好的假設，而這種假設在DTN環(huán)境中是不可能的。所以，DTN多播不僅要求新的多播定義，而且?guī)砹寺酚稍O計的新問題。

3 DTN多播路由

現(xiàn)有的DTN多播路由算法從大的方向看，可以大致分為域內(nèi)多播路由算法和域間多播路由算法。

3.1 域內(nèi)多播路由算法

域內(nèi)多播是指在屬于同一個管理域內(nèi)進行一組用戶的數(shù)據(jù)分發(fā)。目前，主要的DTN域內(nèi)多播路算法，根據(jù)尋路路由機制的不同，大概可分為2類：基于知識的多播路由算法和基于概率的多播路由算法。[4]（1）基于知識的多播路由算法主要有：①U-Multicast(Unicast-based Multicast)是一種基于單播的簡單的DTN多播路由算法，它通過使用多個從源節(jié)點到目的節(jié)點的單播服務來實現(xiàn)組播數(shù)據(jù)傳輸；②STMulticast(Static-tree-based Multicast)是一種基于靜態(tài)樹的多播路由算法；③DTBR(Dynamic Tree-Based Routing)是一種基于動態(tài)樹的多播路由算法，每個中繼節(jié)點都要計算自己的多播樹；④OS-multicast(On-demand Situation-aware Multicasting)是在 DTBR的基礎上發(fā)展起來的。針對DTBR的不能很好地動態(tài)利用當前可行路徑的缺陷而提出的改進算法；⑤CAMR(Context-Aware Multicast Routing)是基于節(jié)點密度的自適應的多播路由算法，它主要利用了網(wǎng)絡一些額外的信息，如節(jié)點的位置、節(jié)點的速度等來進行路由選擇。（2）基于概率的多播路由算法主要有：①EMR (Epidemic Multicast Routing)將Vahdat和Becker的Epidemic算法的設計思想引入到容斷網(wǎng)絡的多播路由中；②EBMR(Encounter Based Multicast Routing)是在Prophet基礎上發(fā)展而來的。Prophet是一種采用相遇或投遞轉移的歷史信息，為每個節(jié)點估算將數(shù)據(jù)成功轉發(fā)到目的節(jié)點的概率，即到達概率，節(jié)點只會將數(shù)據(jù)轉發(fā)給比自己到達概率高的節(jié)點。在轉發(fā)策略上，EBMR對Prophet作了一些改進：如果下一跳節(jié)點的到達概率 (delivery predictability)大于設定的門限值，上游節(jié)點就會向該下游節(jié)點轉發(fā)消息；如果沒有找到合適的下一跳節(jié)點，該節(jié)點緩存束信息，直到等待時間(wait timer)到達極限值。

基于知識的多播路由算法依據(jù)一定的網(wǎng)絡知識做出路由選擇，這些網(wǎng)絡知識主要涉及到網(wǎng)絡拓撲、節(jié)點間的連通模式、節(jié)點的地理位置信息、節(jié)點的運動時刻表等等。并且基于知識的多播路由算法假定：網(wǎng)絡能夠預先發(fā)現(xiàn)一定的相關網(wǎng)絡知識。所以其魯棒性及擴展性相對較差。比較適用于節(jié)點相對比較集中或者節(jié)點密度較大的情況。基于概率的多播路由算法不需要維護任何網(wǎng)絡拓撲信息以及一些網(wǎng)絡的額外知識，實現(xiàn)比較簡單，而當節(jié)點較為稀疏或節(jié)點的位置變化較為劇烈時，基于概率的路由算法仍可獲得較好的路由效果。EBMR不依賴于任何路由發(fā)現(xiàn)過程，屬于一種基于概率的多播路由算法。這種多播路由算法，有比較廣的適用范圍。

3.2 域間多播路由算法

在不同管理域間進行一組用戶的數(shù)據(jù)分發(fā)叫做域間多播。目前，關于容遲網(wǎng)絡路由的研究大部分集中在單域即域內(nèi)消息傳遞的問題上。然而，許多實際應用場景，特別在發(fā)展中區(qū)域，往往需要在多域間進行信息傳遞。目前，實現(xiàn)域間通信的多播路由算法主要有：①SHIM是一種可擴展（scalable）的分等級的域間多播路由方案。在SHIM中，組長（域頭）形成高層（upper layer），各個組除組長外其余的節(jié)點形成低層（lower layer）。多播源節(jié)點發(fā)送消息包到它的組長，然后由組長分發(fā)要發(fā)送的數(shù)據(jù)包給所有包含興趣接收點的組的組長。該方案的主要缺點是它利用DTBR或者OS-Multicast作為域內(nèi)多播路由方案。因為DTBR或者OS-Multicast采用類似于DSR的路由決策算法進行組長之間的路由發(fā)現(xiàn)，所以，這兩者方案在節(jié)點密度比較稀疏DTN環(huán)境下，適用性不強。②基于擺渡的域間多播（FBIMR）：FBIMR借助于特定的叫“擺渡”的節(jié)點完成域與域之間的消息通信[5]，而域內(nèi)節(jié)點間的通信則采用增加冗余消息復制的基于相遇（EBMR2）的多播方案。該機制采用“擺渡”節(jié)點在域與域之間中轉數(shù)據(jù)，可以有效避免過多的能量損耗和網(wǎng)絡資源負擔，但需要預先規(guī)劃節(jié)點運動路徑或要求節(jié)點移動可控。

4 總結

DTN是一種新型的無線網(wǎng)絡體系結構，至力于解決頻繁間斷網(wǎng)絡中的數(shù)據(jù)通訊問題。許多潛在的DTN應用是基于多播方式的，由于DTN高延遲、間歇性連接、資源受限等特點，其多播技術需要新的定義和路由設計。本文對DTN多播路由算法目前的研究進展進行論述，綜合分析了目前存在的DTN多播路由算法，在這基礎上，將進一步深入研究，設計更合理有效的路由算法。

［1］Fall K.A delay-tolerant network architecture for challenged Internets[J].In：Proc.of the 2003 Conf.on Applications，Technologies，Architectures，and Protocols for Computer Communications.Karlsruhe：ACM，2003：27-34.

［2］Akyildiz IF，Akan B，Chen C，F(xiàn)ang J，Su W.Inter-Planet Network Internet：State-of-the-Art and research challenges[J].Computer Networks，2003，43(2)：75-112.

［3］鄭煒.延遲容忍網(wǎng)絡的相關問題研究及仿真[D].上海：上海交通大學，2007.

［4］尤齊，徐昌彪，畢元梅，祁彥.容斷網(wǎng)絡中的組播路由算法研究[J].數(shù)據(jù)通信，2008(03).

［5］胡偉.基于消息擺渡的DTN路由關鍵技術研究[D].長沙：國防科學技術大學，2011.