延時(shí)容忍網(wǎng)絡(luò)的路由技術(shù)研究.pdf

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

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

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

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

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

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

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

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

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

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

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