延時容忍網絡的路由技術研究.pdf

1、與互聯(lián)網(Internet)的倍受關注不同，許多工業(yè)用途的專用網絡離人們的視線比較遠，但是它們在人們生活中發(fā)揮的作用卻非常重要，例如道路監(jiān)測網絡、災難發(fā)生地的臨時通信網絡等。這類網絡的絕大部分都有這些特征：以無線電波為載體、節(jié)點能力受限、節(jié)點移動頻繁、通信環(huán)境惡劣等。在這類網絡里，用于Internet的協(xié)議很難正常工作，于是人們提出延時容忍網絡(DTN：Delay-Tolerant Network)的概念來描述這類網絡，并努力為之建立一

2、套協(xié)議標準。 在本論文中，DTN被定義為一種抽象的網絡模型，它不是針對某一個特定的網絡的每個層面，相反，它關注具有延時容忍(Delay-Tolerant)特性的所有網絡。延時容忍是指網絡協(xié)議能夠在某些極端情形下仍然能夠工作而不至于崩潰；所謂極端(Challenging)情形是指節(jié)點之間信道非常不穩(wěn)定、高不對稱，節(jié)點處理能力多樣，網絡整體拓撲不穩(wěn)定，經常出現(xiàn)長時間的分割，業(yè)務分布不可預測等，其中網絡拓撲的不穩(wěn)定是主要特征。從本質上

3、說，DTN否定了傳統(tǒng)網絡模型中的一個根本前提--在路由期間或者數(shù)據(jù)包傳遞期間，存在一條或多條從源端到目的端的路徑。這個前提隱含在傳統(tǒng)路由協(xié)議中，即便是以節(jié)點動態(tài)性為主要背景的MANET(Mobile Ad hoc Network)的代表路由協(xié)議AODV(Ad-hoc On-demand Distance Vector)協(xié)議，其路由發(fā)現(xiàn)過程也必須在存在路徑的條件下完成。 和眾多自組織類網絡一樣，DTN的核心問題是路由。DIN對傳統(tǒng)

4、路由中“路由期間存在從源端到目的端的路徑”這一假設的否定，其實是重新定義了路徑的概念。在傳統(tǒng)網絡中，甚至包括MANET，雖然考慮的拓撲的動態(tài)性，但是拓撲的穩(wěn)態(tài)持續(xù)時間相對于數(shù)據(jù)包的RTT(Round Trip Time)來說還是還是要高很多；這樣，在一次數(shù)據(jù)投遞過程中，拓撲是靜態(tài)的，路徑是與時間無關的。而DTN下，數(shù)據(jù)包每轉發(fā)一次之后，網絡的拓撲可能已經改變，網絡中有的鏈路已經不存在了，同時又有新的鏈路建立；這樣，從整體看來，路徑在時間

5、的維度上是有縱深的，即DTN路徑中的每一條鏈路只有在數(shù)據(jù)包位于該鏈路的兩端的節(jié)點上時該鏈路依然存在時才是有效鏈路。在這個基礎上，對于路由算法而言，其輸入已經不再是一個靜態(tài)的無向圖了，而是一個隨時間變化的圖，其輸出也變成以(鏈路，時間)二元組為基本元素的序列了。針對這個變化，人們提出了空-時圖(Space-Time Graph)來描述DIN的拓撲。在空-時圖中，網絡中的節(jié)點處于很多個層中，每一層代表了一個時刻的拓撲，數(shù)據(jù)包可能的傳遞路徑就

6、是從第一層的源節(jié)點開始逐層往下(沿時間方向)直到遇到目的節(jié)點。 本論文的研究重點是DTN的路由。就路由算法所需要的路由信息的不同，DTN的路由協(xié)議可以分為兩類：需要先驗知識的的路由協(xié)議和不需要先驗知識的家路由協(xié)議。先驗知識的引入是DTN區(qū)別于傳統(tǒng)網絡模型的另一個重要標志。這里的先驗知識是網絡全局信息的一部分。在傳統(tǒng)網絡中，路由算法依賴于當前的網絡狀況，而DTN則還要依賴于將來的網絡狀況。因為網絡狀態(tài)相對穩(wěn)定，傳統(tǒng)網絡中，當前的網

7、絡狀況一般是通過路由信息交互協(xié)議獲取的過去某個時刻的網絡狀況的預測得到的。DTN需要未來較長時間內的網絡狀況，僅僅通過對過去狀況的簡單預測并不準確，因此需要需要引入先驗知識。在研究了MANET，WSN等網絡路由協(xié)議的基礎上，本文主要對DTN的路由研究作出了如下貢獻： 著眼于路由算法的信息集中最重要的參數(shù)--延時，建立了DTN中數(shù)據(jù)包的單跳延時模型。把延時作為選擇最佳路徑的標準可以減少數(shù)據(jù)包在網絡中的駐留時間，減少網絡緩存的消耗，

8、反過來增加網絡的容量。在DTN的研究中延時的構成以及其量化的分析還沒有涉及。本文給出了單跳的范圍，即鏈路上的延時模型，指出延時構成的幾個基本量，即傳輸延時、排隊延時、等待鏈路建立延時和傳播延時。為了分析這幾個參量的相互關系，把鏈路作為服務窗建立排隊模型，提出了一種新的“帶隨機休假的非空竭排隊系統(tǒng)”，利用排隊論的分析方法，對隊列長度、排隊延時進行隨機分解，最后得到隊長和延時的分布函數(shù)，以及它們與業(yè)務分布等參數(shù)的數(shù)學期望之間的關系。最后通過

9、仿真證實了實際測量值和計算值之間有很高的擬合度，在一定精度下本文的分析結果可以成立。 在標準Earliest Delivery算法的基礎上，把先驗知識的準確性考慮進去，提出AED(Adaptive Earliest Delivery)算法。Earliest Delivery算法只具有理論上的意義，它給出了一種很好的描述DTN路由問題的方式；但是在實用性方面，它對先驗知識過高的需求造成實現(xiàn)的困難。但是，從另一個方面來看，現(xiàn)實中存在

10、這一些可以預先知道鏈路容量函數(shù)的場景，例如衛(wèi)星通信；這時Earliest Delivery算法可以提供更好的路由效果，但是，現(xiàn)實中預知的鏈路容量函數(shù)總是存在誤差，如何衡量這種誤差，以及如何使Earliest Delivery算法在誤差下也能夠有較好的性能就成為了本文的一個研究內容。首先，建立誤差模型，從理論上分析丟包概率與誤差強度的關系，給出了表達式；然后，把誤差的標準差作為參數(shù)去修正延時，就是AED算法。仿真表明新的算法對誤差的容忍能

11、力有明顯提高。 提出一種基于模板運算的運動模式識別框架PM<'3>D，并提出基于運動模式的路由模型。運動模式是用來描述節(jié)點(群)的運動規(guī)律的概念，但是本文中的運動模式不關注物理的參數(shù)，而是宏觀上的模式；這種模式可以從網絡的空-時圖的各元素(只考慮0和1，也就是通和斷)之間的位置關系中反映出來。一種基于模板運算的機制PM<'3>D被用來從空-時圖中識別這些運動模式，并用一個統(tǒng)一的數(shù)據(jù)結構--訪問列表(VL：Visit List)來