【正文】 和目的節(jié)點之間，所以說報文首先要被節(jié)點緩存一段時間，一般情況下，當(dāng)遇到一個節(jié)點時，將概率傳遞矢量進行比較，而不會立刻轉(zhuǎn)發(fā)報文給該節(jié)點，如果該節(jié)點到當(dāng)前節(jié)點的概率與到目的節(jié)點的概率進行相比，較高的話，則報文的副本就先轉(zhuǎn)發(fā)給該節(jié)點，如果該節(jié)點到當(dāng)前節(jié)點的概率與到目的節(jié)點的概率進行相比，較低的話，報文的轉(zhuǎn)發(fā)就不會進行。 圖 ：概率路由中節(jié)點間報文的轉(zhuǎn)發(fā) Message change in Probabilistic Routing 由圖可知：節(jié)點 B 到目的節(jié)點的概率與節(jié)點 A 到目的節(jié)點的概率進行比較，如果較低，報文就會被節(jié)點 A 傳遞給節(jié)點 B。同理，相互轉(zhuǎn)發(fā)報文在節(jié)點 B 和節(jié)點 C 之間進行時，概率矢量的比較也會首先進行，節(jié)點 B 到目的節(jié)點的概率與節(jié)點 C 到目的節(jié)點的概率進行相比，如果較低，報文也同樣會被節(jié)點 B 傳遞給節(jié)點 C。節(jié)點 A 和節(jié)點 C 之間在圖中，報文的傳遞并沒有直接地進行，報文的傳遞在他們之間進行是通過節(jié)點 B 的，同樣的概率關(guān)系也存在于節(jié)點 A 和節(jié)點 C 之間，當(dāng)從節(jié)點 A—— 節(jié)點 B— — 節(jié)點 C 之間的報文轉(zhuǎn)發(fā)完成的時候，就可進行概率的傳遞。從圖 中可以看出，將概率路由和蔓延路由進行比較時，也有不同之處。不同之處在于：報文被轉(zhuǎn)發(fā)給鄰居節(jié)點之前，節(jié)點間概率矢量首A C B 節(jié)點的概率矢量 所傳遞的報文 基于擁塞控制的 DTN 路由選擇研究 18 先要進行比較，是否進行報文的轉(zhuǎn)發(fā)也需要通過比較節(jié)點的概率來決定。在網(wǎng)絡(luò)開銷方面，蔓延路由算法和概率路由算法進行比較，其明顯要高很多；而散發(fā)等待路由算法和概率路由算法進行比較時，其網(wǎng)絡(luò)開銷卻要低很多，但是散發(fā)等待路由算法的報文投遞率要小很多。 選擇報文的下一跳節(jié)點在傳統(tǒng)的路由協(xié)議中，通常是很簡單的。如果僅僅是簡單地轉(zhuǎn)發(fā)節(jié)點到鄰居節(jié)點中 ，可以說報文是到達報文信宿最短路徑最小的一個。又由于其具有較高的路徑可靠性，通常只選擇轉(zhuǎn)發(fā)給唯一的一個節(jié)點，對于報文來說。但是，當(dāng)報文遇到一個節(jié)點時，在 DTN 網(wǎng)絡(luò)中，往往通往信宿的路徑?jīng)]有一條可以采用，除非能夠找到可用的連接，否則節(jié)點只有存儲該報文一條路可行得通。而當(dāng)獲得可用的連接時，是否傳遞某個報文的決定必須做出，否則就被浪費掉連接機會。 當(dāng)然在有些情況下也可以采取另一種方法，選擇一個閾值可以考慮，當(dāng)該閾值小于兩節(jié)點間的投遞預(yù)測值時報文才會得到傳遞，反過來說則不傳遞。當(dāng)兩節(jié)點間的投遞預(yù)測值較小，當(dāng)遇到這樣 一個節(jié)點時，預(yù)測值更大的節(jié)點在何時才能出現(xiàn)，可能就會造成不能確定。所以是否轉(zhuǎn)發(fā)報文可以用某些更寬松的條件來決定。報文到達信宿的可能性，在報文被散布給大量的節(jié)點之后，顯然會得到提高，但是就會浪費掉相應(yīng)的更多的系統(tǒng)資源。從另一方面來看，如果只有少量的節(jié)點（包括一個節(jié)點）獲得轉(zhuǎn)發(fā)的報文，系統(tǒng)資源確實是可以節(jié)省下來。 總而言之，要想決定轉(zhuǎn)發(fā)的策略，必須得根據(jù)協(xié)議具體的應(yīng)用場景。 Prophet 路由協(xié)議轉(zhuǎn)發(fā)策略 Prophet Routing protocol forwarding strategy A B C S D P(A,B) P(A,C) 第二章 DTN 網(wǎng)絡(luò)路由算法 19 其他路由 以上三種典型的 DTN 路由協(xié)議使用頻率較多，除這幾個算法之外，我們還簡單討論介紹下面幾種路由協(xié)議。 其中之一是 DD(Direct Delivery)算法 [33]，在 DD 路由算法中，并不需要用到中繼節(jié)點。當(dāng)報文副本需要被節(jié)點發(fā)送的時候，它僅僅攜帶報文副本并不傳遞，除非遇到目的節(jié)點，報文副本才會被直接傳遞到目的節(jié)點。拓撲變化在 DD 路由算法這種方案中顯得較為重要。而且在一些特殊的情況下，這種算法還是適合的，例如：傳感器網(wǎng)絡(luò)將數(shù)據(jù)集中發(fā)送 給收集器或者衛(wèi)星通信，在這些場合下，目標(biāo)節(jié)點都會定期出現(xiàn)的。 另外一種路由算法是 FC(First Contact)路由算法。與 DD 路由算法相比，有所不同，當(dāng)遇到第一個節(jié)點的時候，報文就被開始傳遞，如果此時沒有遇到節(jié)點，報文就會被緩存起來，但是，如果不止一個節(jié)點同時被遇到，這時就隨機選擇一個節(jié)點而傳遞報文。從某種形式上， FC 路由算法屬于一種隨機轉(zhuǎn)發(fā)模式，但它并非能計算得出報文被傳遞的下一跳節(jié)點，也不用刻意去計算，這完全是隨機的。在網(wǎng)絡(luò)存在動態(tài)的擺渡 (Ferry)節(jié)點的情況下或者網(wǎng)絡(luò)節(jié)點較稀疏的環(huán)境下可應(yīng)用該算 法。 還有一種路由算法被稱為 RAPID(Resouce Allocation Protocol for Intentional DTN routing)協(xié)議，它是一種基于效用函數(shù)的路由方案。我們可以賦予一個效用值 Ui 給每個報文 i，接著進行路由選擇，一般是根據(jù)這個效用值來進行的。假設(shè)報文延遲用 Ui 來表示，那么決定報文是否轉(zhuǎn)發(fā)都是取決于 Ui 的最小值。假設(shè)報文被 X 傳遞給 Y，可以分四步協(xié)議來完成： (1) 初始化：源數(shù)據(jù) (Metadata)可以通過 Y 獲得，接著它的報文效用大小就可以估算出來了； (2) 直接發(fā)送：將 報文傳遞給 Y，而且是按照降序的順序； (3) 復(fù)制：對于緩存在 X 中的每個報文 i Y 中已經(jīng)存有報文 i， i 就可以忽略 Y 的報文 i 的邊限效用進行評估δ Ui(通過對 i 進行復(fù)制而增加的 Ui) ，且是以δ Ui/si(si 表示 i 的大小 )的值降序的方法 基于擁塞控制的 DTN 路由選擇研究 20 (4) 終止：當(dāng)傳遞完所有的報文之后或者無線電范圍小于通信距離時，傳遞就會終止。 本章小結(jié) 對于本章的主要內(nèi)容是： DTN 網(wǎng)絡(luò)的路由算法，本章一開始介紹的是 DTN網(wǎng)絡(luò)路由算法的相關(guān)概念。接下來按照蔓延路由算法、散發(fā)等待路由算法、 概率路由算法的順序，本章詳細地介紹并分析了這幾種 DTN 網(wǎng)絡(luò)的路由算法。從上述介紹的路由算法中，我們又可以將它由單拷貝路由和多拷貝路由兩種構(gòu)成，其中還重點提到，多拷貝路由具有的特點是：它能夠獲取較低的傳遞延遲和較高的報文投遞率，都是犧牲了網(wǎng)絡(luò)開銷來換得的。 在上面所述的 DTN 網(wǎng)絡(luò)的路由算法中，其中散發(fā)等待路由算法中對中繼節(jié)點的選擇是沒有原則的，當(dāng)中繼節(jié)點被攜帶報文的節(jié)點所遇到時，就會將報文傳遞給中繼節(jié)點。此外，傳遞報文副本的數(shù)目也是一個固定值，這樣只會導(dǎo)致一種結(jié)果：即使中繼節(jié)點會經(jīng)常遇到目的節(jié)點，報文也不能被 它攜帶著進行傳遞，所以說報文的傳遞率會大大的降低下來。正因為考慮到這個原因，本章提出了一個更優(yōu)的路由算法 —— 帶有概率選擇的散發(fā)等待路由算法。在下一章節(jié)當(dāng)中，我們將繼續(xù)介紹相關(guān)概念。 第三章 DTN 網(wǎng)絡(luò)節(jié)點能量限制 21 第三章 DTN 網(wǎng)絡(luò)節(jié)點能量限制 概述 在 極端 的 網(wǎng)絡(luò)環(huán)境 下，例如 傳輸延遲超長、連通間歇 性 、缺乏連接保證等 環(huán)境下， DTN 網(wǎng)絡(luò) (Delay/Disruption Tolerant Network)也是 能夠適用 的 。報文 的 傳輸 大多是通過 DTN 路由協(xié)議依 靠 中間節(jié)點的存儲 和 轉(zhuǎn)發(fā)來 完成的 。 可以將 這些DTN 路由 協(xié)議算法分為 多 復(fù)制 算法 和 單 復(fù)制算法 兩種，這是 根據(jù)在網(wǎng)絡(luò)中是否能夠?qū)?報文 進行 多次復(fù)制 來劃分的 。 在單復(fù)制 算法 方案里， 只有 唯一一個報文拷貝 存在于 網(wǎng)絡(luò)中， 然后 該報文 被各中繼節(jié)點傳遞到信宿，例如，根據(jù)效用函數(shù)的最大值 ， 在概率路由方案中，報文 由 每個相遇節(jié)點 進行 轉(zhuǎn)發(fā)。在多復(fù)制 算法 方案里， 可以將 報文依據(jù)某些允許的條件， 進行 多次復(fù)制 和 散發(fā)。 比如， 多變的報文散發(fā)方案在散發(fā)等待機制中 多被采用 ， 如源端散發(fā)等。在相遇 的 時 候， 所有節(jié)點 在 純洪泛機制中， 都僅僅是 簡單地 將 報文 進行 交換 。 往往在 DTN 路由算法的研究中忽視了節(jié)點的能量狀態(tài)。 但 是 ，在某些情況下 ， 這樣的假設(shè)條件 通常 是不成立的 ，比 如當(dāng) 限制了 參加節(jié)點的能量供應(yīng) 的 時候。在 能量損耗 方面， DTN 網(wǎng)絡(luò) 節(jié)點 的往往 與路由算法本身有關(guān)。 綜上所述的 多復(fù)制路由算法 ，是比較 具有代表性的，本章在不 太 影響遞交延遲和遞交率的前提下，對于 節(jié)點節(jié)能方面進行改進， 目的是對 節(jié)點能量的損耗 能夠 降低。 節(jié)點能量限制 DTN 網(wǎng)絡(luò)研究組 (DTNRG)從屬于因特網(wǎng)研究任務(wù)組 (IRTF) ， DTN 網(wǎng)絡(luò)體系結(jié)構(gòu)就是它在星際網(wǎng)絡(luò)研究組 (IPNRG) 的基礎(chǔ)之上發(fā)展而來的，其最初提出的目的是為了行星間的網(wǎng)絡(luò)能夠進行互聯(lián)通信，其應(yīng) 用主要有兩個方面：一是不同網(wǎng)絡(luò)間的協(xié)同工作環(huán)境，比較缺乏持續(xù)的連接；二是高延遲的太空通信。 互聯(lián)網(wǎng)結(jié)構(gòu)是以 TCP/IP 協(xié)議為基礎(chǔ)的，在網(wǎng)絡(luò)層的報文轉(zhuǎn)發(fā)是通過 IP 協(xié)議來執(zhí)行的，當(dāng)在傳輸層時有一條確定的端到端的連接是有必要的。然而在非常惡劣的網(wǎng)絡(luò)環(huán)境條件下，甚至在端到端的連接不存在的情況下， DTN 網(wǎng)絡(luò)仍可以工作，只不過在這種網(wǎng)絡(luò)環(huán)境下，傳統(tǒng)的路由協(xié)議將不會很好地工作。 本節(jié)重點研究兩種 DTN 網(wǎng)絡(luò)的性能，這兩種性能都是在資源受限環(huán)境下表基于擁塞控制的 DTN 路由選擇研究 22 現(xiàn)出的，因此具有重要理論以及現(xiàn)實意義價值。一是在實際的資源受限的情況下，研究怎 樣有效地實現(xiàn)網(wǎng)絡(luò)的路由，而且是利用 DTN 網(wǎng)絡(luò)的多拷貝機制；并進一步在資源受限情況下研究出性能指標(biāo)更完善的路由算法；二是對于和 DTN 網(wǎng)絡(luò)路由協(xié)議相結(jié)合的穩(wěn)定性分析、緩存調(diào)度建模以及探索各項性能更佳的擁塞控制機制進行研究。 路由技術(shù)可以說是 DTN 網(wǎng)絡(luò)技術(shù)的熱點和難點之一，這是由 DTN 網(wǎng)絡(luò)特殊的性質(zhì)決定的。有很多非確定性存在于 DTN 網(wǎng)絡(luò)中，例如隊列緩存、連接持續(xù)時間、動態(tài)拓撲特性、業(yè)務(wù)量、機會鏈接、以及節(jié)點壽命等非確定性都將重重挑戰(zhàn)帶給 DTN 網(wǎng)絡(luò)的路由。 近幾年來，適合 DTN 路由協(xié)議的一些方案已經(jīng)由國內(nèi)外研究者設(shè) 計出：在不連通的網(wǎng)絡(luò)之間，報文擺渡技術(shù)負責(zé)攜帶數(shù)據(jù)并傳遞數(shù)據(jù)，這是利用特殊的移動節(jié)點完成的；利用多跳路由技術(shù)，在稀疏的 DTN 網(wǎng)絡(luò)中，可以無回環(huán)地進行轉(zhuǎn)發(fā)；在面對路徑失敗時，克服 DTN 的路由問題大多采用多路遞交技術(shù)；每個節(jié)點在節(jié)點緩存技術(shù)中，需要選擇之前遇到的節(jié)點的子集，通常利用一個簡單的緩存試探來進行選擇，并使其成為自己的路由鄰居；蔓延技術(shù)允許在網(wǎng)絡(luò)中將報文無限制地進行復(fù)制，然后報文最終被轉(zhuǎn)發(fā)到信宿節(jié)點，這是采用泛洪機制，而這種技術(shù)適合于稀疏的 DTN 網(wǎng)絡(luò)，其節(jié)點的緩存空間是不受限制的；散發(fā)技術(shù)要控制報文在網(wǎng) 絡(luò)中的數(shù)目，可以在源節(jié)點處，通過設(shè)定報文的起始拷貝數(shù)的方式來完成，散播路由不僅是高度可擴展的，而且它還同時很大程度上減少了每個報文被傳遞的次數(shù)，可以保持優(yōu)良的性能在多種場景下；概率路由技術(shù)是否將報文傳遞給相遇到的節(jié)點（機會鏈接），這是將節(jié)點到達信宿節(jié)點的概率進行比較來決定的；概率延遲技術(shù)計算路由多是采用 Dijkstra，并充分對于節(jié)點之間的連接性、傳輸延遲等因素引起的有效路由進行考慮。 綜上所述， DTN 網(wǎng)絡(luò)環(huán)境下， DTN 網(wǎng)絡(luò)要解決節(jié)點間的間歇連通性，多是采用多拷貝路由機制。但是對于帶寬的競爭、電力的消耗、網(wǎng) 絡(luò)的節(jié)點緩存等資源，這種多拷貝技術(shù)無疑為它們帶來了很重的負擔(dān)。而上述路由技術(shù)的前提大多是假設(shè)節(jié)點緩存不會受到限制，所以說研究 DTN 網(wǎng)絡(luò)的路由技術(shù)具有極其重要的意義，尤其對于解決和研究報文的節(jié)點緩存及拷貝數(shù)、帶寬、電力、網(wǎng)絡(luò)的間歇連通性等為前提的資源內(nèi)部的權(quán)衡關(guān)系。 第三章 DTN 網(wǎng)絡(luò)節(jié)點能量限制 23 在實現(xiàn)了 DTN 網(wǎng)絡(luò)路由之時，在擁塞的性能方面，具有存儲 — 攜帶 — 傳遞模式的多拷貝機制同時對網(wǎng)絡(luò)提出了挑戰(zhàn)。所以對于網(wǎng)絡(luò)的性能方面，當(dāng) DTN網(wǎng)絡(luò)節(jié)點在擁塞的狀況下，如何能有效地并及時進行擁塞避免、擁塞檢測及擁塞處理有著很深刻的意義。 近幾年來，國內(nèi)外 的非線性科學(xué)工作者、控制理論專家、計算機網(wǎng)絡(luò)研究者對于 DTN 網(wǎng)絡(luò)的擁塞控制研究產(chǎn)生了的廣泛關(guān)注。這幾年來在擁塞控制方面，國內(nèi)外的研究工作主要集中在兩個部分。一部分集中在報文的有效調(diào)度管理上，而且是節(jié)點緩存器中的報文，用來緩解節(jié)點緩存器中的擁塞情況，這個操作是通過對節(jié)點緩存器中的報文，進行存儲和傳遞隊列的有效管理來實現(xiàn)的。要實現(xiàn)對節(jié)點進行有效緩存管理，就得通過報文被傳遞的次數(shù)（跳數(shù)）以及報文到達信宿節(jié)點之后的開銷大小來決定報文在緩存器的存儲、傳遞及丟棄的優(yōu)先權(quán)，比如MaxProp。報文在存儲、傳遞時的優(yōu)先權(quán)是 由 fuzzyspray 通過報文的大?。?MS）和報文的轉(zhuǎn)發(fā)傳輸數(shù)（ FTC）這兩個參數(shù)給予的，進而實現(xiàn)在緩存器中對報文進行的有效管理。實現(xiàn)節(jié)點的緩存管理是通過執(zhí)行報文存儲、傳遞和丟棄的優(yōu)先級的方式來完成的。另一部分則是集中于如何去實現(xiàn)報文的合理丟棄，在節(jié)點緩存已處于擁塞的情況下。通常也可采用 NDrop 算法，即緩存器中傳遞（跳數(shù)）次數(shù)大于等于 N 的（閾值）報文首先被丟棄，這是在節(jié)點緩存器滿的狀況下丟棄的。 然而，在 DTN 網(wǎng)絡(luò)擁塞控制研究方面，國內(nèi)外目前一般僅僅單一地對有發(fā)生擁塞節(jié)點現(xiàn)象的緩存器進行考慮，在與擁 塞節(jié)點的實際路由情況相結(jié)合之后，去建立適當(dāng)?shù)膿砣呗詤s是很少考慮到；在擁塞控制模型研究與分析方面，大部分的工作集中于緩存器中的報文丟棄和緩存器中的報文調(diào)度，對于現(xiàn)實中出現(xiàn)的擁塞源