DTN多播路由算法研究

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

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

0 前言

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

1 DTN概述

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

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

2 DTN多播服務技術應用與發展

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

3 DTN多播路由

現有的DTN多播路由算法從大的方向看，可以大致分為域內多播路由算法和域間多播路由算法。

3.1 域內多播路由算法

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

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

3.2 域間多播路由算法

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

4 總結

DTN是一種新型的無線網絡體系結構，至力于解決頻繁間斷網絡中的數據通訊問題。許多潛在的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，Fang J，Su W.Inter-Planet Network Internet：State-of-the-Art and research challenges[J].Computer Networks，2003，43(2)：75-112.

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

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

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