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