【文章內(nèi)容簡(jiǎn)介】 圖 定向路由洪泛機(jī)制 .................................................................................................. 38 圖 中間節(jié)點(diǎn)處理 RREQ 報(bào)文的過(guò)程 ........................................................................ 40 圖 中間節(jié)點(diǎn)處理 RREP 報(bào)文的過(guò)程 .......................................................................... 41 圖 數(shù)據(jù)包成功發(fā)送率 1 ............................................................................................... 43 圖 數(shù)據(jù)包成功發(fā)送率 2 ............................................................................................. 44 圖 網(wǎng)絡(luò)路由包開銷 1................................................................................................... 44 圖 網(wǎng)絡(luò)路由包開銷 2 .................................................................................................. 45 圖 端 到端的平均時(shí)延 1 ............................................................................................. 45 圖 端到端的平均時(shí)延 2 .............................................................................................. 46 工程碩士學(xué)位論文 VII 附表索引 表 路由協(xié)議性能比較（按路由建立時(shí)間分類） ..................................................... 8 表 路由協(xié)議性能比較（按邏輯組織機(jī)構(gòu)分類） ................................................... 11 表 典型 Ad hoc 路由協(xié)議實(shí)現(xiàn)機(jī)制比較 .................................................................. 17 工程碩士學(xué)位論文 1 第 1 章 緒 論 隨著 通信 技術(shù) 和 計(jì)算機(jī) 技術(shù)的 不斷 發(fā)展 ， 計(jì)算機(jī) 網(wǎng)絡(luò) 正快速進(jìn)入到 商業(yè)、 工業(yè)、教育和科研 等 領(lǐng)域，進(jìn)入到人們的日常生活中，深 深 影響和改變著 我 們的 生活 和 工作 方式。 移動(dòng)通信網(wǎng)（如 GSM 和 CDMA 等） 在 我們周圍 廣泛存 在 ， 它 們需要有 有線網(wǎng)絡(luò)或存在 固定基站 ，對(duì)于原 來(lái)沒有有線網(wǎng)絡(luò) 的區(qū)域或者 有線網(wǎng)絡(luò) 已經(jīng)被破壞的區(qū)域，例如在 荒蕪人間的沙漠中， 浩瀚無(wú)邊的大海上，以及被 火災(zāi) 或其它災(zāi)難所毀壞的城市，戰(zhàn)場(chǎng)等特殊場(chǎng)所， 以前的 移動(dòng)通信網(wǎng)絡(luò)就不能滿足 要 求。在某些 特殊 情況下，需要 快速、 臨時(shí)地建立一 個(gè) 新的移動(dòng)通信網(wǎng)絡(luò)， 來(lái) 實(shí)現(xiàn)信息的傳 輸 。為了滿足這種需求， 一種新的 移動(dòng)通信 網(wǎng)（ 移動(dòng) ad hoc 網(wǎng)絡(luò) ）應(yīng)運(yùn)而生 。移動(dòng) ad hoc 網(wǎng)絡(luò) (MANET)是一個(gè)復(fù)雜的分布式系統(tǒng)，它由 很多 自由移 動(dòng) 的無(wú)線節(jié)點(diǎn) ， 動(dòng)態(tài)地自組織成 一個(gè) 任意網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) 系統(tǒng) 。 它 使 各 設(shè) 備之間 不需要 固定基礎(chǔ)設(shè)施 就可以 進(jìn)行 相互 通信，并且能 很好 地連接到 Inter 等網(wǎng)絡(luò) 。在 戰(zhàn)爭(zhēng) 和 日常生活 上 美好的 應(yīng)用前景 漸漸 成為人們的研究中心之一， 也使 ad hoc 網(wǎng)絡(luò) 逐漸 成為下一代網(wǎng)絡(luò)的重要 分支 。 課題的研究背景及意義 移動(dòng) Ad hoc 網(wǎng)絡(luò) 概述 Ad hoc[15]來(lái) 源于拉丁語(yǔ)，是 “ 專門地， 特別地 ， 隨機(jī) 地， 隨 時(shí) 地 為 即將 發(fā)生的特定事件或 情況 ” 的意思。這里的 Ad hoc 網(wǎng)絡(luò) 是 指 一種特定的 、 多跳、自組織、無(wú)中心 的 無(wú)線網(wǎng)絡(luò)。 目前 國(guó)內(nèi) 很多專家將 Ad hoc 網(wǎng)絡(luò) 稱 為 “ 自組網(wǎng) ” ，或者 “ 多跳網(wǎng)絡(luò) ” 等等。 移動(dòng) ad hoc 網(wǎng)絡(luò)是由 許多動(dòng)態(tài)節(jié)點(diǎn)（ 帶有無(wú)線收發(fā)裝置 ）自組織成一個(gè) 臨時(shí)性的多跳的 無(wú)中心的分布式 系統(tǒng)。 在 任意時(shí)刻， 每個(gè)節(jié)點(diǎn) 可以向 不同 方向以 不同速度 移 動(dòng)，在網(wǎng)絡(luò)中 每 個(gè)節(jié)點(diǎn) 可以完全自由 的運(yùn)動(dòng) ， 因此 無(wú)法預(yù)測(cè) 網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)發(fā)生 怎樣 變化。 移動(dòng) ad hoc 網(wǎng)絡(luò) 是一個(gè)多跳 (Multihop)的無(wú)線移動(dòng)網(wǎng)絡(luò) [6 9]， 當(dāng)網(wǎng)絡(luò)中 兩個(gè) 移動(dòng) 節(jié)點(diǎn)在彼此的 數(shù)據(jù) 傳輸范圍內(nèi)時(shí)，可以直接進(jìn)行無(wú)線通信 ； 而當(dāng)兩個(gè) 移動(dòng) 節(jié)點(diǎn)不在彼此的 數(shù)據(jù) 傳輸范圍內(nèi)時(shí)，兩個(gè) 移動(dòng) 節(jié)點(diǎn) 必須經(jīng)過(guò)其它中間 移動(dòng) 節(jié)點(diǎn)轉(zhuǎn)發(fā) 進(jìn)行無(wú)線通信。 這里，我們 描述了一個(gè)簡(jiǎn)單 的 由三個(gè) 移動(dòng) 節(jié)點(diǎn)組成的ad hoc 網(wǎng)絡(luò) ，如 圖 11。在該網(wǎng)絡(luò)中， 移動(dòng) 節(jié)點(diǎn) A 和 C 都 不在彼此的 數(shù)據(jù) 傳輸范圍內(nèi)，但是它們都在 移動(dòng) 節(jié)點(diǎn) B 的 數(shù)據(jù) 傳輸范圍內(nèi)，因此如果 移動(dòng) 節(jié)點(diǎn) A 要 向移動(dòng) 節(jié)點(diǎn) C 進(jìn)行 數(shù)據(jù)通信，必須通 過(guò) 移動(dòng) 節(jié)點(diǎn) B 進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。這 是移動(dòng) ad hoc基于位置預(yù)測(cè)的 Ad hoc 網(wǎng)絡(luò)路由協(xié)議研究 2 網(wǎng)絡(luò)的一個(gè) 基本特征 —— 多跳性 ，也是路由 設(shè)計(jì) 的一個(gè)難點(diǎn)。 圖 簡(jiǎn)單的移動(dòng) Ad hoc 網(wǎng)絡(luò)示例 在 ad hoc 網(wǎng)絡(luò)中， 移動(dòng) 節(jié)點(diǎn) 既作為 主機(jī) ，又具有 路由器的功能。 一 方面 ， 移動(dòng)節(jié)點(diǎn)作為主機(jī) 運(yùn)行相關(guān)的協(xié)同應(yīng)用程序 ； 另一方面， 移動(dòng) 節(jié)點(diǎn)作為路由器運(yùn)行相關(guān)的路由協(xié)議， 實(shí)現(xiàn) 路由發(fā)現(xiàn)、路由維護(hù)等路由操作， 如果 接收到的 數(shù)據(jù) 不是給自己的 數(shù)據(jù) 分組 即 進(jìn)行 數(shù)據(jù) 轉(zhuǎn)發(fā)。 Ad Hoc 網(wǎng)絡(luò)中路由協(xié)議問(wèn)題 當(dāng) 前 Inter 網(wǎng)絡(luò) 中 主要 使用的路由協(xié)議 [10] [11]是基于距離矢量的路由協(xié)議和基于鏈路狀態(tài)的路由協(xié)議。這兩類 路由 協(xié)議都是針對(duì) 有線 或 固定網(wǎng)絡(luò)而設(shè)計(jì)，由于 Ad Hoc 網(wǎng)絡(luò) 的動(dòng)態(tài) 拓?fù)浣Y(jié)構(gòu) 、 數(shù)據(jù) 轉(zhuǎn)發(fā)的多跳性等 特點(diǎn)，使得實(shí)用于 Inter網(wǎng)絡(luò)的 路由協(xié)議并不適 合 Ad Hoc 網(wǎng)絡(luò)。 目 前 Ad Hoc 路由協(xié)議基于不同的出發(fā)點(diǎn)和機(jī)制，尚無(wú)比較完善的性能都比較優(yōu)越的路由協(xié)議。各種路由協(xié)議都存在或多或少的問(wèn)題，主要表現(xiàn)在以下幾個(gè)方面： （ 1） 動(dòng)態(tài)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) Ad hoc 網(wǎng)絡(luò)中， 移動(dòng) 節(jié)點(diǎn) 可以以 任意 速度和方向 移動(dòng) 、 電 源用 盡 /關(guān)機(jī)或損毀、同時(shí) 節(jié)點(diǎn) 發(fā)送功率的變化、無(wú)線信道 之間 相互干擾 、地理環(huán)境 等 因素 的影響，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)隨時(shí)都會(huì)發(fā)生變化 ，若在 Ad hoc 網(wǎng)絡(luò) 中直接運(yùn)行 Inter 網(wǎng)絡(luò)的 路由協(xié)議 ， 一旦拓?fù)浣Y(jié)構(gòu)變化 ， Inter 網(wǎng)絡(luò)的 路由協(xié)議 需要花費(fèi)很長(zhǎng)的時(shí)間和很大 的代價(jià)才能 完成 收斂。 （ 2）有限 的無(wú)線傳輸帶寬、鏈路容量動(dòng)態(tài)變化 無(wú)線 信道 通信環(huán)境 比較 惡劣，信號(hào)的 干擾、 衰落、 噪聲 等因素的 影響 以及信道的共享與競(jìng)爭(zhēng)， 使無(wú)線鏈路的狀態(tài)隨時(shí)間 的變化而 變化 ，另外， 由于 移動(dòng)節(jié)點(diǎn)在網(wǎng)絡(luò)中以任意的方式移動(dòng) ， Ad Hoc 網(wǎng)絡(luò)的拓?fù)?結(jié)構(gòu) 變化頻繁，為了能夠 最快、最 精確地反映網(wǎng)絡(luò)拓?fù)?結(jié)構(gòu) 的變化， 因此， 與固定網(wǎng)絡(luò)相比，需要 在節(jié)點(diǎn)間不斷地 交互控制報(bào)文 。 由于無(wú)線 傳輸 信道帶寬 有限 ，路 由 協(xié)議 只有 盡量 減少 節(jié) 點(diǎn) 間 信息 交互， 才能減少 路 由 協(xié)議開銷，提高信道效率 。 （ 3）移動(dòng)終端能力的有限性 Ad hoc 網(wǎng)絡(luò)中 終端 節(jié)點(diǎn) 內(nèi)存小、 CPU 處理能力低、 所帶 電源 和發(fā)射功率十分 A B C 工程碩士學(xué)位論文 3 有限 。網(wǎng)絡(luò) 中 節(jié)點(diǎn) 既要 作為 主機(jī)又要 作為 路由器 ， 節(jié)點(diǎn)能量 一旦 耗盡將會(huì)改變網(wǎng)絡(luò)拓?fù)?結(jié)構(gòu) ，從 而改變網(wǎng)絡(luò) 壽命及 性能 。 要求路 由 協(xié)議算法 相當(dāng) 簡(jiǎn)單有效， 最大限度 節(jié)省能源， 或在路由選擇時(shí)盡 可能 選擇能量較高的節(jié)點(diǎn)， 而 Inter 網(wǎng)絡(luò)的路由協(xié)議 則沒有 上述的限制 。 （ 4）單向無(wú)線信道的存在 Inter 網(wǎng)絡(luò)的 路由協(xié)議 通常認(rèn)為 物理層 的通信信道是雙向的 ， 但在 Ad hoc網(wǎng)絡(luò) 中 由 于發(fā)射功率或地理環(huán)境等相互 影響可能存在單向信道 ，它為 Inter 網(wǎng)絡(luò)的 路由協(xié)議 帶來(lái)了嚴(yán)重的影響。 （ 5）安全性差 移動(dòng) Ad hoc 網(wǎng)絡(luò)是一種無(wú)線方式的 無(wú)中心的 分布式結(jié)構(gòu)， 開放的鏈路 非常 容易受到攻擊 ， 沒有 固定的網(wǎng)絡(luò)基礎(chǔ)設(shè)施 對(duì) 用戶 進(jìn)行 鑒權(quán)和認(rèn)證，容易被 入侵、 竊聽、網(wǎng)絡(luò)攻擊和拒絕服務(wù)等。 （ 6） 不能提供可靠的 QoS 保證。 只有提高 網(wǎng)絡(luò)的整體性能 才能 提供端到端的可靠 QoS 保證。目前 尚無(wú)比較完善的性能都比較優(yōu)越的路由協(xié)議 ， 還需要進(jìn)一步的完善。雖然 已出現(xiàn) 部分 QoS 路由協(xié)議，但大 多 處于研究 階段，很難 真正 提供可靠的 QoS 保證， 總的來(lái)說(shuō) ， Ad Hoc網(wǎng)絡(luò)的 QoS 路由技術(shù)還需要進(jìn)一步提高，發(fā)展空間很大。 要想 設(shè)計(jì)一個(gè) 整體性能高， 在所有情況 下 都 合適 的 Ad Hoc 網(wǎng)絡(luò)路 由 協(xié)議非常 困難，也可以說(shuō)是基 本不 可能的。 論文研究的 意義 在移動(dòng) ad hoc 網(wǎng)絡(luò)中，移動(dòng)節(jié)點(diǎn)通過(guò)多跳無(wú)線鏈路實(shí)現(xiàn)相互間的通信 ， 開發(fā)一種能有效地找到節(jié)點(diǎn)間路由的動(dòng)態(tài)路由協(xié)議就成為移動(dòng) ad hoc 網(wǎng)絡(luò)設(shè)計(jì)的關(guān)鍵 ，是實(shí)現(xiàn)快速 適應(yīng)快速變化的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) ， 保證網(wǎng)絡(luò)良好的魯棒性和路由查找的有效性 ，減少 路由開銷 ，降 低電能損耗 的保障 。 所以設(shè)計(jì)一個(gè)好的路由協(xié)議算法 具有重要的研究?jī)r(jià)值和現(xiàn)實(shí)意義： （ 1） 通過(guò)自適應(yīng)的節(jié)點(diǎn)定位算法，計(jì)算節(jié)點(diǎn)位置，為定向洪泛提供基礎(chǔ)。 （ 2） 通過(guò)定向洪泛，減少網(wǎng)絡(luò)路由開銷 。 （ 3） 通過(guò) 自適應(yīng)的節(jié)點(diǎn)定位算法獲得 節(jié)點(diǎn)位置，提出 基于位置預(yù)測(cè)的LAODV 路由協(xié)議 ，并詳細(xì)闡述其 設(shè)計(jì) 過(guò)程 和仿真 實(shí)驗(yàn) ，為 Ad hoc 網(wǎng)絡(luò)路由查找提供一種 更優(yōu)化的 協(xié)議 ，解決核心技術(shù)難點(diǎn)，具有現(xiàn)實(shí)意義。 總之，本課題針對(duì) 移動(dòng) ad hoc 網(wǎng)絡(luò) 的特點(diǎn)， 探討 ad hoc 網(wǎng)絡(luò) 路由協(xié)議， 特別是 AODV 路由協(xié)議和基于位置的路由協(xié)議 ， 提出基于位置預(yù)測(cè)的 LAODV 路由協(xié)議， 對(duì)于降低路由開銷，提高包轉(zhuǎn)發(fā)率，降低平均時(shí)延有很重要的意義。 基于位置預(yù)測(cè)的 Ad hoc 網(wǎng)絡(luò)路由協(xié)議研究 4 Ad Hoc 網(wǎng)絡(luò)路由協(xié)議的研究現(xiàn)狀 由于移動(dòng) Ad Hoc 網(wǎng)絡(luò) 具有動(dòng)態(tài)的網(wǎng)絡(luò) 拓?fù)浣Y(jié)構(gòu)，所 以路由問(wèn)題 顯得尤為重要，路由 協(xié)議 的好壞直接 影響 到整個(gè)網(wǎng)絡(luò) 的整體 性能。對(duì)移動(dòng) Ad Hoc 路由協(xié)議的研究已經(jīng)成為無(wú)線通信的熱點(diǎn)之一，對(duì)路由 算法 的 研究 也越來(lái)越深入， 已經(jīng) 從不同的角度提出了多種針對(duì) Ad Hoc 網(wǎng)絡(luò)的路由協(xié)議 [12]， 每種路由協(xié)議 都有著自己的特點(diǎn)， 他 適用于不同的應(yīng)用環(huán)境。目前大致可以將它們分為主動(dòng)路由協(xié)議、被動(dòng)路由協(xié)議，混合路由協(xié)議及全球定位系統(tǒng) GPS 輔助的路由協(xié)議。 主 動(dòng) 路 由 協(xié) 議 又 叫 表 驅(qū) 動(dòng) 路 由 協(xié) 議 ， 目 前 主 要 有 DSDV[13] (DestinationSequenced DistanceVector)、 WRP[14] [15] (Wireless Routing Protocol)和 CGSR(Cluster HeadGateway Switch Routing)等，該類協(xié)議每個(gè) 移動(dòng) 節(jié)點(diǎn) 需要 維護(hù)一張包含到達(dá)其它 所有 節(jié)點(diǎn)的路由信息的路由表， 隨著 網(wǎng)絡(luò)拓?fù)?結(jié)構(gòu) 的變化隨時(shí)更新路由表， 它 準(zhǔn)確地反映網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。 每當(dāng) 源節(jié)點(diǎn)發(fā)送報(bào)文， 通過(guò)路由表 即 可 獲得到達(dá)目的節(jié)點(diǎn)的路由。因此這種路由協(xié)議延時(shí)較小，但 維護(hù)路由開銷較大。 被動(dòng)路由協(xié)議 又叫按需路由協(xié)議， 目前主要有 DSR[17] (Dynamic Source Routing) 、 AODV[16] (Ad hoc On demand Distance Vector) 和 TORA[18] [19] (TemporallyOrdered Routing Algorithm)等，該類協(xié)議中 每個(gè) 移動(dòng) 節(jié)點(diǎn)不需要 隨時(shí)維護(hù) 更新 路由信息，當(dāng) 源節(jié)點(diǎn) 需要發(fā)送數(shù)據(jù)時(shí)才 起動(dòng) 路由查找過(guò)程。與主動(dòng)路由協(xié)議相比，按需路由協(xié)議的開銷較小，但是報(bào)文傳送的延 時(shí) 較大。 混合式路由協(xié)議 [20] [21]，是結(jié)合了 主動(dòng)路由協(xié)議和被動(dòng)路由協(xié)議 的優(yōu)缺點(diǎn)，即在 小 范圍內(nèi)使用主動(dòng)路由協(xié)議，維護(hù)準(zhǔn)確的路由信息，可以 減少 路由 控制消息傳