【正文】 議用在了 DTN 網(wǎng)絡(luò)路由算法中，并提出了被稱為“中間免疫”(intermediate immunity)的技術(shù)來限制報文副本的數(shù)量。 基于調(diào)度的路由算法 基于調(diào)度的路由算法首先給報文設(shè)定了優(yōu)先級，傳輸效率較高的報文往往被賦予了較高的優(yōu)先級。每當(dāng)出現(xiàn)“聯(lián)系”或者通信時機(jī)的時候，通過調(diào)度優(yōu)先復(fù)制傳輸具有更高優(yōu)先級的報文。由于節(jié)點(diǎn)之間的傳輸容量以及節(jié)點(diǎn) 自身的緩存容量有限，因次一次只有一部分報文能夠被復(fù)制傳輸，而較低優(yōu)先級的報文則會因?yàn)殚L時間得不到通信機(jī)會而被丟棄。通過這樣的調(diào)度方式，丟棄低效傳輸?shù)膱笪模梢蕴岣呔W(wǎng)絡(luò)資源的利用率。這一類的主要算法包括 Burgess 等人提出的 MaxProp 算法 [28]以及 Balasubramanian 等人提出的 RAPID 算法 [29]。 MaxProp 算法采用了增量平均化 (incremental averaging)的策略來估算節(jié)點(diǎn)之間成功傳輸報文的概率，并且將報文傳輸失敗的概率之和作為端到端傳輸路徑的代價，以傳輸東北大學(xué)碩士學(xué)位論文 第 2 章 DTN 路由的研 究現(xiàn)狀 － 14－ 代價來作為確 定該報文的優(yōu)先級。報文成功傳輸?shù)母怕试酱螅瑒t該報文的傳輸代價就越小，因次將會被賦予較高的優(yōu)先級，從而被優(yōu)先的復(fù)制轉(zhuǎn)發(fā)；相反，如果報文的傳輸概率較小，則會被賦予較低的優(yōu)先級，也就得不到轉(zhuǎn)發(fā)的機(jī)會，因而能夠避免生成低效傳輸?shù)膱笪母北?，從而提高了網(wǎng)絡(luò)資源的利用率。 RAPID 算法將 DTN 網(wǎng)絡(luò)的路由問題模型化成了一個以效用作為驅(qū)動的資源分配問題。該算法假設(shè)節(jié)點(diǎn)之間的相遇時間符合指數(shù)分布，因此采用了分布式的算法來估算節(jié)點(diǎn)之間報文傳輸延時的期望值，并依據(jù)傳輸延時定義了報文傳輸?shù)男в煤瘮?shù)，傳輸延時較長的報文將具有較小的效 用函數(shù)值。此后，根據(jù)報文的邊際效用值依照降序規(guī)律進(jìn)行報文的復(fù)制轉(zhuǎn)發(fā)。 RAPID 算法是一個具有明確的優(yōu)化目標(biāo)的路由算法，并且在一個由40 輛公交車組成的 DTN 網(wǎng)絡(luò)實(shí)驗(yàn)平臺上對其性能進(jìn)行了有效的驗(yàn)證。 基于概率的路由算法 基于概率的路由算法對于報文傳輸?shù)某晒Ω怕蔬M(jìn)行了估算和比較，有選擇性地復(fù)制報文。通過這種方法可以減少報文復(fù)制的盲目性，避免了生成低效傳輸?shù)母北?，增加了網(wǎng)絡(luò)資源的利用效率。基于概率的路由算法代表性的算法主要包括 Burns 等人提出的MV 路由算法 [30]和 Lindgren 等人提出的 PRoPHET 算法 [31]。 MV算法利用了節(jié)點(diǎn)之間的相遇概率來定義報文傳輸?shù)某晒Ω怕省Ｈ我鈨蓚€節(jié)點(diǎn)之間的相遇概率直接作為這對節(jié)點(diǎn)的傳輸概率，在這個基礎(chǔ)上再通過遞歸的方法來計算多跳傳輸?shù)某晒Ω怕?。?jié)點(diǎn)相遇時會交換各自的報文和各自的傳輸概率信息。通過比較，節(jié)點(diǎn)僅僅會向傳輸概率比自己更高的節(jié)點(diǎn)復(fù)制報文。 PRoPHET 算法則定義了一個被稱為傳輸預(yù)測值 (delivery predictability)的參數(shù)用來描述節(jié)點(diǎn)之間成功傳輸?shù)目赡苄?。與傳染病路由算法相比，每當(dāng)兩個節(jié)點(diǎn)相遇的時侯，它們除了要交換各自的概要向量之外，其還需要交換各自 的傳輸預(yù)測值向量。基于交換所得的信息，每個節(jié)點(diǎn)會更新各自的傳輸預(yù)測值向量。此后，節(jié)點(diǎn)將對傳輸預(yù)測值向量和概要向量進(jìn)行比較，只有在自身到目標(biāo)節(jié)點(diǎn)的傳輸預(yù)測值小于對方節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的傳輸預(yù)測值時，節(jié)點(diǎn)才會選擇向?qū)Ψ焦?jié)點(diǎn)復(fù)制報文。 基于編碼的路由算法 基于編碼的路由算法主要包括了基于網(wǎng)絡(luò)編碼 (work coding)的路由算法 [32]以及基于擦除碼 (erasure code)的路由算法 [33,34]。這類基于編碼的路由算法將報文拆分成為數(shù)據(jù)塊，通過多路徑在網(wǎng)絡(luò)中傳輸，目標(biāo)節(jié)點(diǎn)只要收集到了一定數(shù)量的數(shù)據(jù)塊就可 以解碼出原報文。 東北大學(xué)碩士學(xué)位論文 第 2 章 DTN 路由的研 究現(xiàn)狀 － 15－ 文獻(xiàn) [32]提出了一種基于網(wǎng)絡(luò)編碼的路由算法。這種算法在基于概率的路由算法基礎(chǔ)上，新引入了線性網(wǎng)絡(luò)編碼技術(shù)來降低路由算法的代價。通過仿真實(shí)驗(yàn)顯示，在一個節(jié)點(diǎn)稀疏部署的移動網(wǎng)絡(luò)中，尤其是在節(jié)點(diǎn)具有較高的丟包率時，在引入了網(wǎng)絡(luò)編碼技術(shù)之后，路由算法的性能將會提升的尤為明顯。 文獻(xiàn) [3334]則 提出了基于擦除碼的路由算法 ?；诓脸a的路由算法的最關(guān)鍵性的問題是如何將報文分塊、復(fù)制、分配到多個傳輸路徑才可以最大化報文傳輸?shù)某晒β?。文獻(xiàn) [33]對這個問題進(jìn)行了形式化分析，借用了現(xiàn)代投資組合理論 (modern portfolio theory)，分別在高斯路徑傳輸模型和伯努利路徑傳輸模型下求解了這個問題，并且提出了簡單有效的算法，能夠獲得最優(yōu)的報文傳輸概率。 轉(zhuǎn)發(fā)策略的路由算法 在轉(zhuǎn)發(fā)策略路由算法當(dāng)中，節(jié)點(diǎn)會根據(jù)其所獲得的關(guān)于網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化的信息，按照一定的優(yōu)化方式選擇一條最優(yōu)化的傳輸路徑，使得報文沿著這條路徑逐跳地進(jìn)行傳輸。在報文的傳輸過程之中，節(jié)點(diǎn)不會對該報文進(jìn)行復(fù)制。因此，網(wǎng)絡(luò)中只存在一個報文的副本在傳輸。 在適用于轉(zhuǎn)發(fā)策略的 DTN 網(wǎng)絡(luò)路由算法之中，最具有代表性的算法是由 Jain 等學(xué)者在文獻(xiàn) [35]中提出的一系列的算法，其中包括了 FC(First Contact)， MED(Minimum Expected Delay)， EDLQ(Earliest Delivery with Local Queue)， ED(Earliest Delivery)，EDAQ(Darliest Delivery with All Queue)和 LP(Linear Program)這 6 種路由算法。這些算法首先是將 DTN 網(wǎng)絡(luò)抽象化成為一個多圖，節(jié)點(diǎn)之間的“聯(lián)系”則對應(yīng)于多圖的每條邊。然后，基于這個多圖，以降低傳輸時延為優(yōu)化 目標(biāo)，從中選擇最優(yōu)化的路徑轉(zhuǎn)發(fā)報文。在這些算法之中，基于零信息需求的 FC 路由算法最為簡單，節(jié)點(diǎn)從最先出現(xiàn)的“聯(lián)系”之中隨機(jī)地選擇一個用來轉(zhuǎn)發(fā)報文，因此這種方法的性能最低，并且不能夠保證消息能夠成功地傳遞到目的節(jié)點(diǎn)。 MED 路由算法是基于網(wǎng)絡(luò)之中“聯(lián)系”的摘要信息，采用了 Dijkstra 算法來求解最優(yōu)的路由。 ED 路由算法則是基于網(wǎng)絡(luò)中所有的“聯(lián)系”信息表，采用了改進(jìn)的 Dijkstra 算法求解報文能夠最快到達(dá)的最優(yōu)路由。而 EDAQ 和 EDLQ路由算法則是在 ED 路由算法的基礎(chǔ)之上，分別引入了全局的緩存隊(duì)列信息和局部節(jié) 點(diǎn)的緩存隊(duì)列信息，進(jìn)一步地優(yōu)化了網(wǎng)絡(luò)的性能。 LP 路由算法則是進(jìn)一步考慮了對于流量需求的信息，使得原先的最優(yōu)路徑求解問題形式化成為一個線性規(guī)劃問題從而加以分析和求解。 東北大學(xué)碩士學(xué)位論文 第 2 章 DTN 路由的研 究現(xiàn)狀 － 16－ 除此之外，文獻(xiàn) [36]還提出了一個基于鏈接狀態(tài)的路由協(xié)議，改路由協(xié)議首先采用了傳染病算法將網(wǎng)絡(luò)的鏈接狀態(tài)信息廣播到網(wǎng)絡(luò)之中的各個節(jié)點(diǎn)，然后再利用這些鏈接狀態(tài)信息作為路由決策的評判依據(jù)。文獻(xiàn) [37]首先根據(jù)消息傳遞到目的節(jié)點(diǎn)的成功概率定義了一個效用函數(shù)，并且提出了一個基于此效用函數(shù)的路由策略。文獻(xiàn) [38]則考慮了異質(zhì)的容遲移動 Ad Hoc 網(wǎng)絡(luò)，將 網(wǎng)絡(luò)容量的分析轉(zhuǎn)化成為最大一致流的問題，并在這個基礎(chǔ)上提出了一個以傳輸容量最大化作為優(yōu)化目標(biāo)的漸進(jìn)最優(yōu)的節(jié)點(diǎn)調(diào)度和路由的機(jī)制。在文獻(xiàn) [12]中，作者假設(shè)在 DTN 網(wǎng)絡(luò)中的節(jié)點(diǎn)要么是靜止不動的、要么是做有規(guī)律的運(yùn)動的，針對滿足上述描述的這一類簡單的 DTN 網(wǎng)絡(luò)，提出了一個可以加以擴(kuò)展的分層路由算法 DHR。 DTN 網(wǎng)絡(luò)路由協(xié)議與 Ad Hoc 路由協(xié)議的特點(diǎn)比較 前一小節(jié)中已經(jīng)總結(jié)了現(xiàn)有的很多 DTN 網(wǎng)絡(luò)的路由協(xié)議，迄今為止， DTN 網(wǎng)絡(luò)路由協(xié)議有一個很重要的不同于傳統(tǒng) Ad Hoc 網(wǎng)絡(luò) [39]路由協(xié)議的思想，即“存儲 攜帶 轉(zhuǎn)發(fā)”，這是因?yàn)?DTN 路由協(xié)議網(wǎng)絡(luò)的易斷性和被分割性，路由協(xié)議很難找到完整的路徑從而進(jìn)行傳輸，因此，只有選擇讓中間節(jié)點(diǎn)“攜帶”數(shù)據(jù)，慢慢的等待接觸到合適的節(jié)點(diǎn)進(jìn)行數(shù)據(jù)的下一跳傳輸。這種路由策略上根本性的改變導(dǎo)致了 DTN 網(wǎng)絡(luò)路由與 Ad Hoc 網(wǎng)絡(luò)路由相比，具有了以下幾點(diǎn)的不同： （ 1）時延： DTN 網(wǎng)絡(luò)路由不采用建立路由再傳輸數(shù)據(jù)的策略，因此傳輸時延主要都由節(jié)點(diǎn)攜帶數(shù)據(jù)的時間，節(jié)點(diǎn)等待合適的下一跳節(jié)點(diǎn)的時間所決定，而 Ad Hoc 網(wǎng)絡(luò)路由采用了建立路徑再傳數(shù)據(jù)的方法，數(shù)據(jù)傳輸過程中都是具有完整路徑的，因此其時延 要遠(yuǎn)遠(yuǎn)小于 DTN 網(wǎng)絡(luò)的路由。 （ 2）適用環(huán)境：由于 Ad Hoc 網(wǎng)絡(luò)傳輸數(shù)據(jù)需要建立完整路徑，因此網(wǎng)絡(luò)中被選中作為路由的路徑的穩(wěn)定性會成為影響 Ad Hoc 網(wǎng)絡(luò)性能的重要因素。這意味著網(wǎng)絡(luò)中節(jié)點(diǎn)分布密集的環(huán)境是有利于 Ad Hoc 網(wǎng)絡(luò)路由的性能的，而一旦網(wǎng)絡(luò)中節(jié)點(diǎn)密度稀疏，則 Ad Hoc 網(wǎng)絡(luò)路由策略則會由于路徑易斷而受到很大的影響 . 與此相反， DTN 網(wǎng)絡(luò)路由策略正是針對網(wǎng)絡(luò)惡劣的情況下所設(shè)計的，其采用的是盡最大努力，但不保證的交付原則。這種路由策略采用的選路思想主要是通過一些判斷標(biāo)準(zhǔn)，選取相對合適的下一條節(jié)點(diǎn)交付 數(shù)據(jù)的方法。在網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量稀少的時候，每個節(jié)點(diǎn)之間的信息記錄較少，每個節(jié)點(diǎn)的個體信息特征體現(xiàn)的較為明顯，在這樣的環(huán)境中使用 DTN 網(wǎng)絡(luò)路由策略是適用的，而當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量較多的時候，每個節(jié)點(diǎn)的個東北大學(xué)碩士學(xué)位論文 第 2 章 DTN 路由的研 究現(xiàn)狀 － 17－ 體信息特征就會很不明顯，網(wǎng)絡(luò)中很可能就會出現(xiàn)路由環(huán)路，數(shù)據(jù)無法交遞給真正最適合攜帶的節(jié)點(diǎn)而導(dǎo)致無法成功傳遞給目的節(jié)點(diǎn)。 DTN 網(wǎng)絡(luò) 路由協(xié)議 與 Ad Hoc 網(wǎng)絡(luò) 路由協(xié)議的基本思想具有很大的差異性 ， 適用環(huán)境也正好相反，可以認(rèn)為這兩種路由思想是完全屬于兩種網(wǎng)絡(luò)環(huán)境的。然而，對于某些特定的網(wǎng)絡(luò)，其既具有 DTN 網(wǎng)絡(luò)的網(wǎng)絡(luò)被分割性 ，拓?fù)湟鬃冃缘奶攸c(diǎn)，兼而在局部又具備一些 Ad Hoc 網(wǎng)絡(luò)的特點(diǎn)。 因此 ，本文在針對這種特殊的 DTN 網(wǎng)絡(luò)設(shè)計 DTN 路由的時候， 借鑒 了部分傳統(tǒng)的 Ad Hoc 網(wǎng)絡(luò)的路由思想 。利用 Ad Hoc 網(wǎng)絡(luò)的路由 思想在一定程度上優(yōu)化 DTN 路由協(xié)議，提出了一種適用新型的 DTN 網(wǎng)絡(luò)路由協(xié)議 DTNDMOR。 本章小結(jié) 通過以上分別從網(wǎng)絡(luò)模型和路由策略的角度，對于已有的典型的 DTN 網(wǎng)絡(luò)路由算法的介紹，可以得知這些算法都有其各自的特點(diǎn)： （ 1） 從 面向 網(wǎng)絡(luò)模型的角度來看 ，在面向被動移動模型的路由算法的研究方面 ,到目前為止，針對幾個比較常 用的隨機(jī)移動模型，已經(jīng)取得了一定的理論研究成果，從而對于分析路由算法的性能指標(biāo)有著非常重要的指導(dǎo)作用。但是，由于真正面向?qū)嶋H應(yīng)用的 DTN 網(wǎng)絡(luò)往往是不符合這些隨機(jī)移動模型的規(guī)律的，因此需要對于實(shí)際的 DTN 網(wǎng)絡(luò)中的節(jié)點(diǎn)移動數(shù)據(jù)進(jìn)行分析和建模，而且就目前而言，相關(guān)的研究還非常的有限；而 面向主動移動模型 的路由算法能夠利用節(jié)點(diǎn)本身的移動特性從而協(xié)助網(wǎng)絡(luò)中的報文傳輸。在一般情況下，這些路由算法主要都是在已經(jīng)知道了部分節(jié)點(diǎn)部署的情況下，通過節(jié)點(diǎn)之間的相互協(xié)作來規(guī)劃主動移動節(jié)點(diǎn)的移動路線，但是如何通過更加深入的理論分析將這 種算法的優(yōu)化目標(biāo)進(jìn)行量化，使得其能夠具備更好的服務(wù)質(zhì)量，以及如何能夠提高算法的魯棒性、可擴(kuò)展性、自適應(yīng)性和智能性等等，都還需要進(jìn)一步的研究。 （ 2）從制訂路由策略的角度來看，復(fù)制策略的路由算法往往是不需要了解整個網(wǎng)絡(luò)的拓?fù)鋭討B(tài)變化的，對于網(wǎng)絡(luò)移動模型的依賴性比較低，因此適用的范圍更為廣闊。但是，這些算法也存在著開銷太大，網(wǎng)絡(luò)資源利用率較低的問題。而且，由于設(shè)計的路由策略大多數(shù)只是定性地優(yōu)化了某些性能指標(biāo)，難以做到量化，特別是針對較為復(fù)雜的DTN 網(wǎng)絡(luò)，想要實(shí)現(xiàn)優(yōu)化目標(biāo)明確的路由算法還是非常困難的，需要更為深入 的理論分析和研究。而轉(zhuǎn)發(fā)策略的路由算法往往是需要對網(wǎng)絡(luò)拓?fù)涞膭討B(tài)變化有至少一定程度的了解，從而才能夠選擇比較合適的路徑轉(zhuǎn)發(fā)報文，網(wǎng)絡(luò)之中不存在冗余報文，網(wǎng)絡(luò)資源利用率相對較高，但是獲取和更新有關(guān)網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化的信息則會耗費(fèi)大量的網(wǎng)絡(luò)東北大學(xué)碩士學(xué)位論文 第 2 章 DTN 路由的研 究現(xiàn)狀 － 18－ 資源，而且如何能夠以一種可擴(kuò)展的方法去定義和擴(kuò)散網(wǎng)絡(luò)拓?fù)渥兓男畔⒁彩沁@以類算法中的難題。 （ 3）從 DTN 網(wǎng)絡(luò)路由協(xié)議和 Ad Hoc 網(wǎng)絡(luò)路由協(xié)議的特點(diǎn)對比來看，總結(jié)了兩種類型協(xié)議策略各自的特點(diǎn)及適用環(huán)境，引出結(jié)合兩者優(yōu)點(diǎn)設(shè)計更加有效的 DTN 路由策略的可能性。 總體而言， DTN 網(wǎng) 絡(luò)的路由算法雖然已經(jīng)取得了一定的研究成果，但是仍然是處于初步階段的，特別是在理論研究以及面向?qū)嶋H應(yīng)用的方面還有很大的可以研究的空間， DTN 網(wǎng)絡(luò)的路由問題依舊是 DTN 網(wǎng)絡(luò)的關(guān)鍵難點(diǎn)問題之一。 東北大學(xué)碩士學(xué)位論文 第 3 章 DTNDMOR 路由算法的設(shè)計和實(shí)現(xiàn) － 19－ 第 3章 DTNDMOR 路由算法的設(shè)計和實(shí)現(xiàn) DTNDMOR 路由協(xié)議思想 DTNDMOR 路由思想的提出 基于對 Ad Hoc網(wǎng)絡(luò)特點(diǎn)與 DTN網(wǎng)絡(luò)特點(diǎn)的比較分析，可以看到 DTN網(wǎng)絡(luò)與 Ad Hoc網(wǎng)絡(luò)具有很多相似的特點(diǎn) ，比如節(jié)點(diǎn)移動性、自適應(yīng)性、對等性、節(jié)點(diǎn)處理能力有限性等， 因此 DTN 網(wǎng)絡(luò)的 路由設(shè)計可以借鑒 現(xiàn)在相對比 較成熟的 Ad Hoc 網(wǎng)絡(luò)的路由 設(shè)計 思想 。 Ad Hoc 網(wǎng)絡(luò)路由協(xié)議分為按需路由協(xié)議和表驅(qū)動路由協(xié)議。在按需的 Ad Hoc 網(wǎng)絡(luò)路由協(xié)議中，只有當(dāng)源節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)時才生成路由，因此 其 在 網(wǎng)絡(luò)開銷、算法復(fù)雜度等 方面的 性能指標(biāo)優(yōu)于其它 路由 協(xié)議