【正文】 2個(gè)副本，直到某節(jié)點(diǎn)僅僅持有一個(gè)副本時(shí)進(jìn)入第二個(gè)階段。因次，在同一時(shí)刻，網(wǎng)絡(luò)中存在著同一報(bào)文的多個(gè)副本在傳輸。而文獻(xiàn) [12]則針對節(jié)點(diǎn)的周期 性地運(yùn)動并且會以一定概率相遇的一類 DTN 網(wǎng)絡(luò)，提出了一個(gè)機(jī)會路由算法 RCM。根據(jù)節(jié)點(diǎn)的移動模型，可以將這一類 DTN 網(wǎng)絡(luò)的路由算法分為面向確定或者半確定的移動模型路由算法以及面向隨機(jī)移動模型的路由算法 [7]。 第 2 章對 DTN 網(wǎng)絡(luò) 的 路由算法做了深入詳細(xì)的研究。其中等待 時(shí)延 是最主要的 時(shí)延 ， 等待時(shí)延 的大小可能是 從 幾秒 鐘 到幾天不等。 東北大學(xué)碩士學(xué)位論文 第 1 章 緒 論 － 5－ 表 延遲容忍網(wǎng)絡(luò)和傳統(tǒng)互聯(lián)網(wǎng)絡(luò)的終端特點(diǎn)比較 Table Comparison between DTN work terminal and traditional Inter work terminal 特點(diǎn) DTN 網(wǎng)絡(luò) Inter 壽命 可能能源緊缺，壽命有限 不考慮能源問題，假設(shè)壽命無限 占空比 為了保證較長的壽命而降低占空比 越大越好 存儲器 排隊(duì)時(shí)間較長時(shí)可能需 要外存儲器，對存儲器要求較高 內(nèi)存和高速緩存，對存儲器要求低 DTN 網(wǎng)絡(luò)的與 Ad Hoc 網(wǎng)絡(luò)的特點(diǎn)比較 從節(jié)點(diǎn)移動性，對等性，自適應(yīng)性的角度，由移動的自適應(yīng)的對等節(jié) 點(diǎn)組成的 DTN網(wǎng)絡(luò)與 Ad Hoc 網(wǎng)絡(luò)非常相似，都具有移動、多跳、節(jié)點(diǎn)對等（無中心）等特點(diǎn)，同時(shí)兩種類型的網(wǎng)絡(luò)中節(jié)點(diǎn)處理能力都非常有限。 這是 由于節(jié)點(diǎn)是處 在 戰(zhàn)爭 的環(huán)境下，或者 是 能源 短缺 的 環(huán)境中 ，網(wǎng)絡(luò) 中 節(jié)點(diǎn)隨時(shí)都 有 可能被拆除 、擊毀 或 者是 由于能源枯竭問題而 停止工作。 DTN 網(wǎng)絡(luò)的特點(diǎn) 人們往往采取如下 特征 對于 傳統(tǒng)的 通信網(wǎng)絡(luò)的性能好壞進(jìn)行描述 ： 時(shí)延 、數(shù)據(jù)率、誤碼 率 和 鏈路 的 穩(wěn)定性。延時(shí)容忍是指網(wǎng)絡(luò)協(xié)議能夠在某些極端情形下仍然能夠工作而不至于崩潰 。 作者和導(dǎo)師同意網(wǎng)上交流 的時(shí)間為作者獲得學(xué)位后： 半年 □ 一年 □ 一年半 □ 兩年 □ 學(xué)位論文作者簽名： 導(dǎo)師簽名： 簽字日期： 簽字日期： 東北大學(xué)碩士學(xué)位論文 摘 要 － II－ DTN 網(wǎng)絡(luò)路由算法研究與仿真 摘 要 DTN 網(wǎng)絡(luò)是一種新型的自組織網(wǎng)絡(luò)，由于其長延時(shí)、高動態(tài)拓?fù)?、?jié)點(diǎn)分布稀疏、頻繁斷路等網(wǎng)絡(luò)特性，造成難以維持穩(wěn)定的端到端路徑。 通過 NS2 網(wǎng)絡(luò)模擬軟件對算法進(jìn)行仿真，從網(wǎng)絡(luò)成功投遞率、網(wǎng)絡(luò)流量和時(shí)延三個(gè)方面與 AODV 路由協(xié)議、 PRoPHET 路由協(xié)議進(jìn)行對比，結(jié)果表明：所提出的算法具有較好的性能，適合在 DTN 網(wǎng)絡(luò)中應(yīng)用。因此， DTN 網(wǎng)絡(luò)是隨著科技發(fā)東北大學(xué)碩士學(xué)位論文 第 1 章 緒 論 － 2－ 展，隨著人們對于網(wǎng)絡(luò)技術(shù)的研究深入而被提出一種新型的網(wǎng)絡(luò)。 甚至于在一些特殊的條件 下， 僅僅只存在 單向鏈路的可能性也是存在的， 例如在軍事應(yīng)用 中 的與 一些需要 絕對 隱蔽的裝備進(jìn)行通信。 鏈路中斷 頻繁出現(xiàn) ，不能簡單地丟棄數(shù)據(jù)包 出錯(cuò)，直接丟棄數(shù)據(jù)包 排隊(duì)等待時(shí)間 長時(shí)間 短時(shí) （ 2） 低占空比操作 當(dāng)節(jié)點(diǎn)的 硬件配置 是缺乏能源的時(shí)候，它的 信息 通信方案就要被 事先設(shè)定 好。 歸納起來， DTN 網(wǎng)絡(luò)與 Ad Hoc 網(wǎng)絡(luò)相比，在實(shí)現(xiàn)路由方面存在著一定的困難，但也因其網(wǎng)絡(luò)中節(jié)點(diǎn)本身的運(yùn)行特征具有一些有利于路由算法設(shè)計(jì)的因素，包括以下幾個(gè)方面： （ 1）節(jié)點(diǎn)的移動性： DTN 網(wǎng)絡(luò)中節(jié)點(diǎn)往往是高速運(yùn)動的，一般比傳統(tǒng)的 Ad Hoc網(wǎng)絡(luò)中節(jié)點(diǎn)的運(yùn)動速度要快的多，一方面，這使得 傳統(tǒng)的 Ad Hoc 路由協(xié)議建立起來的通信鏈路容易斷開，另一方面，可以通過利用節(jié)點(diǎn)的快速移動性，將節(jié)點(diǎn)本身作為攜帶數(shù)據(jù)的載體，傳輸信息。 （ 3） 存儲空間 為了 針對鏈路 的斷開 的情況 ， 數(shù)據(jù) 必須在節(jié)點(diǎn) 的存儲器中 緩存一段時(shí)間。最后， 詳細(xì)描述了 路由協(xié)議 各階段的實(shí)現(xiàn)流程 。在復(fù)制策略的路由算法中，節(jié)點(diǎn)以復(fù)制信息的方法轉(zhuǎn)發(fā)報(bào)文，網(wǎng)絡(luò)中在同一 個(gè) 時(shí)間段 之內(nèi) 會存在同一報(bào)文的多個(gè)副本在傳輸。這些節(jié)點(diǎn)在主要報(bào)文的傳輸過程之中起到了“橋”的作用，它們可以自發(fā)地控制自身的移動行為，按照一定的線路在相互分隔的網(wǎng)絡(luò)節(jié)點(diǎn)或者區(qū)域之間進(jìn) 行移動，用“存儲 攜帶 轉(zhuǎn)發(fā)”數(shù)據(jù)的方式幫助網(wǎng)絡(luò)中的節(jié)點(diǎn)傳輸報(bào)文。在某些特定的網(wǎng)絡(luò)環(huán)境中，人們常常會使用直接接 觸的算法 來 完成 網(wǎng)關(guān) 與 無線移動節(jié)點(diǎn)之間的直接通信 ，這樣可以 達(dá)到增加 整個(gè) 網(wǎng)絡(luò)的吞吐量 以及 降低 端到端傳輸延時(shí)的目的 。 此外，文獻(xiàn) [26]針對 DTN 移動傳感網(wǎng)絡(luò)，還提出了基于共享無線信息站模型 (Shared Wireless Information Model， SWIM)的路由協(xié)議中存在的延時(shí)、能耗和存儲空間之間的折中問題，并提出了一個(gè)基于局部最優(yōu)樹的報(bào)文傳輸方法，用來限定網(wǎng)絡(luò)中的副本數(shù)量。 MV算法利用了節(jié)點(diǎn)之間的相遇概率來定義報(bào)文傳輸?shù)某晒Ω怕省? 轉(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)化的傳輸路徑，使得報(bào)文沿著這條路徑逐跳地進(jìn)行傳輸。這種路由策略上根本性的改變導(dǎo)致了 DTN 網(wǎng)絡(luò)路由與 Ad Hoc 網(wǎng)絡(luò)路由相比，具有了以下幾點(diǎn)的不同： （ 1）時(shí)延： DTN 網(wǎng)絡(luò)路由不采用建立路由再傳輸數(shù)據(jù)的策略，因此傳輸時(shí)延主要都由節(jié)點(diǎn)攜帶數(shù)據(jù)的時(shí)間，節(jié)點(diǎn)等待合適的下一跳節(jié)點(diǎn)的時(shí)間所決定，而 Ad Hoc 網(wǎng)絡(luò)路由采用了建立路徑再傳數(shù)據(jù)的方法，數(shù)據(jù)傳輸過程中都是具有完整路徑的，因此其時(shí)延 要遠(yuǎn)遠(yuǎn)小于 DTN 網(wǎng)絡(luò)的路由。 （ 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è)計(jì)更加有效的 DTN 路由策略的可能性。但是，由于真正面向?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ò)中的報(bào)文傳輸。 LP 路由算法則是進(jìn)一步考慮了對于流量需求的信息，使得原先的最優(yōu)路徑求解問題形式化成為一個(gè)線性規(guī)劃問題從而加以分析和求解。 東北大學(xué)碩士學(xué)位論文 第 2 章 DTN 路由的研 究現(xiàn)狀 － 15－ 文獻(xiàn) [32]提出了一種基于網(wǎng)絡(luò)編碼的路由算法。該算法假設(shè)節(jié)點(diǎn)之間的相遇時(shí)間符合指數(shù)分布，因此采用了分布式的算法來估算節(jié)點(diǎn)之間報(bào)文傳輸延時(shí)的期望值，并依據(jù)傳輸延時(shí)定義了報(bào)文傳輸?shù)男в煤瘮?shù)，傳輸延時(shí)較長的報(bào)文將具有較小的效 用函數(shù)值。在第一個(gè)階段中，報(bào)文的源節(jié)點(diǎn)僅僅向網(wǎng)絡(luò)中復(fù)制固定數(shù)量的副本，即噴灑報(bào)文。 復(fù)制策略的路由算法 使用復(fù)制策略的路由算法時(shí)，當(dāng)節(jié)點(diǎn)之間出現(xiàn)通信機(jī)會 （ 在 DTN 網(wǎng)絡(luò)中也被稱為contact，即“聯(lián)系” ） 的時(shí)候，節(jié)點(diǎn)以復(fù)制信息的方式轉(zhuǎn)發(fā)報(bào)文。然后，利用這種方法對于實(shí)際的 DTN 網(wǎng)絡(luò)進(jìn)行建模，并在此基礎(chǔ)之上提出了基于 移動空間 的路由算法。在被動移動的 DTN 網(wǎng)絡(luò)中，節(jié)點(diǎn)不能控制其自身的移動，而只能按照默認(rèn)的移動路線進(jìn)行移動。 引出了 DTN 網(wǎng)絡(luò)的路由問題。 （ 1） 節(jié)點(diǎn) 之 間連接的多樣性 端到端 之間 的 時(shí)延 主要包括等待 時(shí)延 、排隊(duì) 等待時(shí)延 、傳播 時(shí)延 和傳輸 時(shí)延 。這樣就 會 大大 的復(fù)雜化了整個(gè) 系統(tǒng)的設(shè)計(jì)。 東北大學(xué)碩士學(xué)位論文 第 1 章 緒 論 － 4－ DTN 網(wǎng)絡(luò)中終端的特點(diǎn)： （ 1）生存時(shí)間短暫 在 某些網(wǎng)絡(luò) 環(huán)境 中 ， 例 如 在一些 軍事用途中，傳感器網(wǎng) 絡(luò) ，或者 是 在 臨時(shí)緊急的 情況下 創(chuàng)建 的節(jié)點(diǎn)，它們的 生存時(shí)間往往 是比較 短暫 的。圖 通過 與 Inter 的體系結(jié)構(gòu) 相比較 ， 說明 了 包裹層的位置。 DTN 被 定義為一種抽象的 網(wǎng)絡(luò) 模型 ，它不是針對某一個(gè)特定的網(wǎng)絡(luò)的 某 個(gè)層面，相反，它關(guān)注具有 延時(shí) 容忍 (Delay Tolerant)特性的所有網(wǎng)絡(luò)。本人同意東北大學(xué)可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索、交流。 關(guān)鍵詞 ： DTN 網(wǎng)絡(luò) ；路由；傳輸概率； 虛擬坐標(biāo) 東北大學(xué)碩士學(xué)位論文 Abstract － III－ Research and Simulation on DTN Network Routing Algorithm Abstract DTN work is a new type of mobile Ad Hoc work. Due to its characteristics such as long munication delay, high dynamic topology, sparse distribution of nodes and frequent link break, it is difficult to maintain the stability of end to end path. Therefore, the traditional wired or wireless work routing protocol cannot be directly used in DTN work. Design of effective and reliable routing algorithms has bee the key issue in DTN work. A DTN routing algorithm with the thought of storagecarryforward is proposed in this paper. Source nodes don’t establish a plete route to destination nodes to send data packets. However, a source node selects an appropriate node as a data carrier called ―relay node‖ in the context of that the end to end route cannot be established. Under this circumstance, the relay node receives packets, stores them and then finds the destination or a better relay node to forward packets. Through hopbyhop storagecarryforward strategy, packet will finally arrive at the destination. In the storagecarryforward process, routs are constructed by considering characteristics of DTN work. Although DTN work topology is frequently changing, nodes within local area may be strong connected in a short time and thus can provide a path from source or relay nodes to destination or better relay nodes. So Ad Hoc Network routing strategies are used to improve work performance. For the two cases of that motions of DTN nodes are predictable and unpredictable, we design relay node selection schemes respectively. For the case of motions of DTN nodes are predictable, a virtual Euclid space is constructed, which divides the work into N regions. According to motion regularity of nodes, virtual coordinates of each node are calculated offline. Nodes choose relay nodes with smallest virtual Euclid distance to the destination nodes within their munication range. For the case of motions of DTN nodes are unpredictable, nodes periodically broadcast Hello packets. Nodes realtimely maintain information table of transmission prob