延遲/中斷可容忍網絡路由中的關鍵技術

劉水仙，周 健

（南京郵電大學 通信與信息工程學院，江蘇 南京 210003）

0 引言

隨著網絡技術研究不斷的進展，“受限網絡”成為無線通信的一個新的領域，延遲/中斷容忍網絡簡稱為 DTN，是一種特殊受限網絡，采用一種新型的網絡體系結構，2003年SIGCOMM 國際會議上由Kevin提出[1]。典型例子有：陸地移動網絡、外來媒體網絡、軍事無線自組織網絡、傳感器網絡等，存在共同的特點：間歇的連通性、缺少端到端路徑、網絡分割/斷開使得傳輸控制協議/因特網互聯協議（TCP/IP）不適用，長而可變的延遲，非對稱的數據速率，高差錯率。

1 與DTNs路由相關的基本問題

1.1 DTN路由實現的目標

DTN用于描述自組織網絡等無線網絡中頻繁發生長時間網絡分割情形，它主要關注的是如何提高成功投遞率，盡量減少交付延時，節約節點緩存和降低耗能，在實現相同路由性能的條件下，盡量降低算法的復雜度，提高算法的實用性。此外，針對不同的消息服務等級要求，應關注于不同的性能參數，采用滿足相應要求的路由方法。

1.2 DTN路由算法分類

在ACM SIGCOMM2004 年會中, Jain等人提出了DTN網絡中的路由問題[2]，提出了一個如何在 DTN 網絡中評估路由算法性能的框架 ,明確提出了 DTN 路由的主要問題就是確定消息如何端到端地穿越一個隨時間變化而連續變化的網絡,且這種動態性是可能預知的。Zhang Z[3]在已有研究成果基礎上,將 DTN 路由策略分為兩大類:一類為確定性路由方案,它假定將來的移動和連接是可以知道的、是可預測的；另一類為隨機性路由方案,它假定網絡是動態的、不確定的。主要的確定性路由方法有：基于樹的方法、時空路由、修正的最短路徑方法；隨機性路由算法根據不同的轉發機制分為：傳染性/ 隨意散發方式，改進的算法有約束洪泛、Spray AndWait等；基于預測和歷史消息的方法（如PROPHET ）、可控移動的方法、基于編碼的方法。

2 DTN路由的關鍵技術

2.1 擁塞控制

DTN網絡中消息傳輸采用存儲轉發模式，許多DTN路由協議在實際使用時，會產生長期的存儲，節點緩存受限時易發生阻塞；另外，網絡中數據單元稱為“捆綁（束）”，是自載的應用級數據單元，它們常常是很大的，當移動性導致節點間短暫的接觸時，可用帶寬可能不足以使所有預定消息通信。因此，有效的丟棄策略是必要的。

目前的研究結果主要分為兩類[4]：主動方法，通過緩存管理和保管傳輸的相應調整起到擁塞控制的作用；被動方法，采用接入控制避免在開始處的擁塞。文獻[5]采用主動方法的思想，并結合傳染路由算法，提出了一種基于傳染路由的擁塞控制策略（當節點緩存完全占用又需存儲新分組時，遍歷緩存，找出轉發次數大于等于N次的分組將其刪除；若緩存中沒有這樣的分組，則刪除最后一個存入的分組），為信息的集合建立SV索引,引入擁塞檢測和擁塞避免操作，有效緩解了節點擁塞。

Zhang Z.分析了緩存區受限的epidemic路由[6]，并評估了一些簡單的丟棄策略例如 drop-front 和 drop-tail。使用一個有效的聯合調度和丟棄策略能夠最優化不同的性能指標[7]，比如平均延遲和交付概率，首先分析一個最優聯合調度和丟棄策略——基于全局知識的排序和丟棄（GBSD，GlobalAcknowledgeBasedScheduling& Drop），以最大化平均交付率或者最小化平均傳遞時延，用網絡的全局信息來為一個給定的路由度量推導每個消息的特性，在實踐中很難實現。為了修改這種方法，提出另一個策略，HBSD采用一個基于統計學習的分布式算法，從歷史學習中估計當前網絡的全局狀態，能被用來計算message utility。

另外可通過控制復本或轉發數目來避免過多耗用節點緩存，一些算法中使用單個復本，如FC、DD，可有效地緩解空間和帶寬，但同時使得消息交付率很小，SprayAndWait設定消息被復制的數目，有一般模式和二進制模式，通過調整復本數目來平衡分發與耗用內存。

2.2 運動模式

考慮節點運動知識，將虛擬空間運用于DTN路由中[8]，算法將因此受益，它根據與節點在某個位置出現的可能性相關的坐標來描述節點，利用一個與節點運動模式相關的高維Euclidean空間結構，為DTNs定義一個一般的路由方案。

“移動空間”是一個高維的虛擬空間．節點活動的物理空間所劃分的區域數是這個“移動空間”的維數，節點在這個區域出現的概率就是節點坐標在這個維上的截距。“移動空間”中的坐標并不是節點的物理坐標，而是用概率的方法反應了節點在物理空間中的運動規律，作為路由選擇的依據。

不同的空間概率分布代表了不同的移動模型，常用節點移動模型主要有隨機模型、隨機地圖限制模型、人類行為模型。其中隨機移動模型有隨機移動（RW），隨機路點（RWP）和隨機方向（RD）模型；為了將實際移動性模型化，MBM根據實際的map數據中預定路徑限制節點移動，例如隨機地圖移動（MBM）、基于最短路徑的移動（SPMBM）、基于路線的移動（RMBM）；工作日移動模型（WDMM）。

文獻[9]節點維護一個包含所有節點三維容量的矩陣，利用圖像處理中的模板運算機制從中提出可能的運動模式，最后用一個通用的數據結構存儲這些信息，并用于路由決策過程中。為了應對不同的運動模式，節點自定位是一個影響路由算法關鍵的因素，文獻[10]通過引入修正因子的自定位方案，在節點移動過程中不斷對節點坐標進行調整，最后收斂到一個可用范圍，增強了路由算法的穩定性。

2.3 拓撲先念知識

文獻[2]針對五種不同的先念信息等級，設計出幾種具有代表性的路由算法。MED基于經典的Dijkstra算法，使用延時期望作為代價。改進算法有MED-PC算法[2.911]性能比MED有明顯改善，增加了對先驗知識的假設，每當一個鏈接到達，中間節點都要對隊列中所有報文分別計算路由，計算強度較大。另一種改進算法AMED[12]，仍基于dijkstra算法，從目的節點開始計算到源節點的路由，返回反轉后的永久節點序列，而不是傳統意義上的單條路由，比MED-PC算法的計算量少，但性能相當，驗證了oracle 2對Oracle 1的實際優勢并不是很大。在ED算法基礎上，引入了對節點運動精確性的考慮[13]，加入時間精確性因子ρ，反映出連接建立的時刻處在偏離預定時刻的某個領域的概率，并以之作為ED算法中的鏈接代價的權重，提出一種更穩健的路由算法AED，當節點運動不確定性增加時，AED維持較好的性能，而ED的性能則明顯下降。

Oracle 3以上的先念等級不常用，雖然擁有先念知識越多，路由算法有更好的性能，但是先驗知識的獲取和計算處理的代價遠遠大于它們帶來的優勢。

由于長的傳播延時和網絡動態特性，先前的路由信息常常是過期或不準確的，信息陳舊成為機會網絡路由性能的限制，文獻[1.4.314]提出了云級別重排和接觸能力最大化來解決這些限制，將云計算應用到DTN路由中（云路由），通過智能地利用轉發機會避免了擁塞，由于云計算帶來的性能改善和幾乎可忽略的并行網絡控制信道的成本，當有兩個或多個不同特性的網絡，它們應該被看作是一個平行網絡架構并且采用云計算來提高各信道的聯合性能。

2.4 延遲模型

DTN的特點決定了其路由算法適合選擇延時作為基本的代價，其延遲主要來源于等待鏈路建立的時間，當緩存區的消息數量足夠大時，排隊延遲就不可忽略，一般而言，消息的傳輸時間相對很小，在精確度要求不高的計算中可以忽略，圖1描述了一個基本的延遲結構，由基本的三類延遲組成，事實上對應了一種新的排隊模型--帶休假的排隊模型，是設計DTN路由算法的基礎。文獻[15]從排隊論的角度分析了 DTN的延時模型，并引入了休假規律的隨機排隊系統，通過分析得到平均隊列長度和平均延時的表達式。

圖1 兩個節點間的消息延時結構

2.5 多播路由方案

實際的應用場景中常常要用到多播，可以使用受控的洪泛機制實現DTN中的多播[3.6.116]，從而研究多播路由機制的基本性能度量，例如消息交付率、消息延遲和占用緩存。在單播路由方案中可以使用基于兩跳 3.6.12] [3.6.13].【3.6.5】【3.6.的方案可以緩解路由負載，這是因為源節點轉發消息包給中繼節點，中繼節點只有遇到目的點時才將包轉發給目的節點，文獻。[3.6.317]將mobility-assist路由用于DTN無線多播中背景下，最后提出了RelayCast，將兩跳路由擴展到多播場景中。這些方案都是在消息發送者知道消息接收組成員，且組成員在消息傳遞過程中不會改變的情況下提出的，文獻[18]中設計了一個靈活的多播路由協議，解決多播組成員變化的問題。

2.6 域間路由方案

幾乎所有的 DTN路由都專注于單個域內的消息傳遞，這個域的特點是有相同的網絡架構和單個名字空間。文獻[19]介紹了一個基于隨機和確定轉發機制的域間路由方案，說明了一個標準的路由框架應該考慮到不同的路由方案的整合，提出網絡意識的機會多區域異步交付（NOMAD）框架來解決不同系統的共有設計問題，目標是討論一個通用的架構的條件，它超越不同類型的通信模式和傳輸機制。

2.7 路由算法仿真

2.7.1 仿真平臺

DTN路由性能高度地依賴潛在的移動性和節點的特性，通過許多場景估計協議性能要求有一個合適的仿真工具。現有比較成熟的網絡仿真平臺主要有NS2、OMNet++和OPNET，但是沒有一個是專門針對DTN的。dtnsim和dtnsim27是為DTN環境開發的用于路由仿真的平臺，隨后提出的ONE[7.one20]可以實現DTN路由和應用協議的仿真，允許用戶基于不同的移動模型創建應用場景，并且提供了一個實現路由和應用協議的框架，ONE的核心是一個基于代理的離散事件模擬引擎，在每一個模擬時間片斷，這個引擎更新一些實現主要仿真功能的模塊，。主要的功能模塊有節點移動模塊、事件產生模塊、路由模塊、結果可視化模塊。

2.7.2 仿真參數的選擇

研究者們大多數關注路由算法的設計，然而，各種路由協議面臨一個根本性的挑戰：選擇合適的協議參數和正確的仿真時間尺度，這些依賴于不同場景下節點的運動特性。在一個場景內或者是不同場景間，移動節點運動特性很可能不同，文獻[21]使用兩個具有代表性的路由協議交付概率路由（PROPHET）和最大概率路由（MaxPROP），推導了獨立動態和獨立決定移動節點中路由參數的機制，分析了時間尺度對DTN路由算法的影響。

3 結語

由于 DTN網絡自身的特點，實現一個適用于這種特定環境的路由方案面臨許多問題，需要有相應的技術來解決這些限制，總結設計過程中的關鍵技術是有必要的，將來的研究仍然要從這些關鍵點出發，提出新的思路和解決方法，設計出一個通用的性能良好的路由機制，克服網絡的受限特性，從而實現DTNs中有效可靠的通信。

[3]參考文獻

[1] FAL1 K.A Delay Tolerant Network Architecture for Challenged Intemets[C]. New York:ACM Press,2003:27-34.

[2] JAIN S, FALL K, PATRA R. Routing in a Delay Tolerant Networking[C]. New York: ACM Press, 2004:145-158.

[8][3] ZHANG Z. Routing in Intermittently Connected Mobile Ad Hocnetworks and Delay Tolerant Networks: Overview and Challeng[C]. USA:IEEE,2006: 24-37.

[4] 樊秀梅. 容遲網絡的體系結構及關鍵技術[EB/OL]. (2006-12-06).[2010-01-14].http://www.paper.edu.cn.

[5] 趙玲,劉占軍,李云,等.DTN中基于傳染路由的節點擁塞控制策略[J].通信技術,2009, 42 (02):136-140.

[6] ZHANG X, NEGLIA G, KUROSE J, et al. Performance Modeling of Epidemic Routing[J].In Proceedings of IFIP Networking,2007,51(10):2867-2891.

[7] KRIFA A, BARAKAT C. An Optimal Joint Scheduling and Drop Policy for Delay Tolerant Networks[C].USA:IEEE,2008:1-6.

[8] LEGUAY J, FRIEDMAN T, CONAN V. DTN Routing in a Mobility Pattern Space[M].USA:ACM,2005:276-283.

[9] 周曉波,張幸,彭敏,等.DTN網絡中基于泛模板運算的運動模式發現機制[J]電子與信息學報,2009,31(02):472-475.

[10] 王行甫,衛平青,苗付友,等.一種節點自定位方案及其性能分析[J].中國科學院研究生院學報,2008,25(03):367-371.

[11] EVAN P C, LI J L,PAUL A S W. Practical Routing in Delay-Tolerant Networks[M].USA:ACM,2005:237-243.規劃局

[12] 陳飄,盧漢成,李津生,等.用于延時可容忍網絡的增強型MED路由算法[J].計算機工程,2007,33(21):90-98.快樂

[13] 周曉波,盧漢成,李津生,等.AED:一種用于DTN 的增強型Earliest-Delivery算法[J].電子與信息學報,29(08):1956-1960.

[14] MIKE P W, HARRAS K A, ALMEROTH K C, et al. On the Implications of Routing Metric Staleness in Delay Tolerant Networks[J].Computer Communications,2009(32):1699-1709.

[15] 周曉波,周健,盧漢成,等. DTN網絡的延時模型分析[J].計算機研究與發展,2008,45(06):960-966.

[16] ABDULLA M, SIMON R. Controlled Epidemic Routing for Multicasting in Delay Tolerant Networks. Modeling, Analysis and Simulation of Computers and Telecommunication Systems[C].USA:IEEE,2008:1-10.

[17] Lee U, Young O S, Lee K W, et al. RelayCast: Scalable Multicast Routing in Delay Tolerant Networks[C].USA:IEEE,2008:218-227.

[18] YIN L, LU H M, LONG K,et al. A Flexible Multicast Routing Scheme for Multicasting in Delay Tolerant Networks[C].USA:IEEE,2009:1-5.

[19] MUSOLESI M, MASCOLO C. A Framework for Multiregion Delay Tolerant Networking. Proceedings of ACM International Workshop on Wireless Networks and Systems for Developing Regions (WiNS-DR)[M].USA:ACM,2008.

[20] Keranen A.Opportunistic Network Environment Simulator[EB/OL](2008-05-29)[2010-01-14].http://www.dtnrg.org/wiki/Code.

[21] KARVO J,J?RG OT. Time Scales and Delay-tolerant Routing Protocols[M].USA:ACM.2008:13-19.