第四章__Ad_Hoc網(wǎng)絡(luò)的路由技術(shù)

1、第四章 MANET路由MANET Mobile Ad hoc NETworkMANET路由概述n通信兩點可能不再相互的無線傳輸范圍內(nèi)n需要其他節(jié)點承擔(dān)路由器的轉(zhuǎn)發(fā)工作n節(jié)點移動需要發(fā)現(xiàn)新路由MANET路由概述n多條鏈組成路徑n移動導(dǎo)致路徑變化MANET路由面臨的困難n路由信息不易獲得 定期交換路由信息或者按需搜索路由的開銷大 網(wǎng)絡(luò)資源有限，并且必須被所有節(jié)點共享 節(jié)點資源（電池、CPU等）也是有限的 也許不可能收集齊所有的路由信息n路由信息不完整 移動和分區(qū)很難將信息分發(fā)到一個沒有固定成員網(wǎng)絡(luò)的所有節(jié)點n路由信息可能過期 不可能連續(xù)地或者立即交換信息 節(jié)點隨時移動 無線傳播變化很大常規(guī)路由協(xié)議

2、是否可用？n常規(guī)路由協(xié)議不是為高移動性和低帶寬網(wǎng)絡(luò)設(shè)計的nDV算法存在“無窮計算”問題和慢收斂n采用洪泛技術(shù)的（鏈路狀態(tài)）協(xié)議造成額外的通信和控制開銷n常規(guī)路由協(xié)議周期性的路由更新消耗大量的網(wǎng)絡(luò)帶寬和節(jié)點能源n當(dāng)網(wǎng)絡(luò)節(jié)點失效和網(wǎng)絡(luò)分區(qū)時形成路由回路n無線終端功率的差異以及無線信道的干擾導(dǎo)致單向信道的存在AD HOC網(wǎng)絡(luò)對路由協(xié)議的要求n收斂迅速n提供無環(huán)路由n避免無窮計算n控制管理開銷小n對終端無過高要求n支持單向信道n盡量簡單實用n路由機(jī)制必須適應(yīng)網(wǎng)絡(luò)三個不斷變化的基本特征 移動節(jié)點的總體密度 節(jié)點到節(jié)點的拓?fù)?網(wǎng)絡(luò)的使用模式AD HOC路由協(xié)議分類n平面路由 無需建立具有特殊cluster

3、頭功能節(jié)點的層次結(jié)構(gòu) 不劃分區(qū)域以及所謂的區(qū)內(nèi)/外不同路由 所有的節(jié)點在路由機(jī)制中地位平等 尋址方式是平面的n層次路由 節(jié)點功能不同 尋址方式是分層進(jìn)行的n地理信息輔助路由 利用地理信息進(jìn)行路由選擇按需（ON-DEMAND）路由協(xié)議n反應(yīng)式（reactive）路由 在源端需要時候通過路由發(fā)現(xiàn)過程來確定路由 控制信息采用洪泛（flooding）方式 路由請求延遲高 路由開銷低 兩種實現(xiàn)技術(shù) 源路由（報文頭攜帶完整的路由信息） 逐跳路由（類似現(xiàn)有的Internet路由）洪泛技術(shù)（FLOODING）在自組網(wǎng)路由中具有廣泛應(yīng)用工作原理： （1）源節(jié)點向所有的鄰居節(jié)點廣播分組。 （2）中間節(jié)點判斷自己是

4、否是目的節(jié)點，如果不是，而且是第一次收到該分組，則繼續(xù)廣播；否則，直接丟棄 （3）目的節(jié)點接收分組，不廣播。改進(jìn)：在分組中加入TTL（Time To Live）字段，將分組的傳播限制在一定范圍內(nèi)。效果：洪泛使分組像輻射波一樣從源節(jié)點已波浪形式向外傳播，最終到達(dá)目的節(jié)點（如果目的節(jié)點是可達(dá)的話） 最健壯最基本的方法表驅(qū)動（TABLE DRIVEN）路由n先應(yīng)式（proactive）路由 傳統(tǒng)的分布式最短路徑路由協(xié)議 鏈路狀態(tài)或者距離向量 所有節(jié)點連續(xù)更新“可達(dá)”信息 每個節(jié)點維護(hù)到網(wǎng)絡(luò)中所有節(jié)點的路由 所有路由都已經(jīng)存在并且隨時可用 路由請求的延遲低 路由開銷高兩種路由機(jī)制的權(quán)衡n路由發(fā)現(xiàn)的延遲

5、 主動協(xié)議因全程維護(hù)所有的路由而具備低延遲 按需協(xié)議因只在需要時才發(fā)現(xiàn)所需路由而導(dǎo)致高延遲n路由發(fā)現(xiàn)/維護(hù)的開銷 按需協(xié)議因只在需要時才維護(hù)路由而具備低開銷 主動協(xié)議因連續(xù)更新路由可能導(dǎo)致高開銷n那種途徑表現(xiàn)更好取決于流量和移動模式分層路由協(xié)議n層次（hierarchical）路由 一些節(jié)點組成一個cluster或則zone 這些cluster或則zone可組成較大的super cluster或則super zonenCluster和zone的不同 Cluster內(nèi)所有節(jié)點都與cluster head直接通信，cluster內(nèi)節(jié)點間的通信一般是兩跳 Zone的大小沒有限制，zone內(nèi)節(jié)點的通信

6、可多跳nZRP兩層路由協(xié)議概念描述分層路由協(xié)議的優(yōu)缺點n優(yōu)點 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的細(xì)節(jié)通過節(jié)點的層層聚合都被隱藏起來，因此大大降低大型網(wǎng)絡(luò)的存儲要求 路由信息分層傳播，需要在全局傳播的路由信息較少 有限的鏈路狀態(tài)維護(hù)n缺點 分層路由協(xié)議的移動管理比較復(fù)雜 某些節(jié)點（cluster head/gateway）比其他節(jié)點承擔(dān)更多的通信和計算負(fù)載評價MANET路由協(xié)議的指標(biāo)n端-端的數(shù)據(jù)吞吐量和延遲 反映了數(shù)據(jù)報的傳輸質(zhì)量n路由請求的時間 有數(shù)據(jù)需要發(fā)送到發(fā)送出去的時間n路由協(xié)議的效率 路由控制信息與數(shù)據(jù)信息的比率MANET路由主動路由n表驅(qū)動（Table driven）/先應(yīng)式路由機(jī)制 傳統(tǒng)的分布式最短

7、路徑路由協(xié)議 鏈路狀態(tài)或則距離向量 所有節(jié)點連續(xù)更新“可達(dá)”信息n每個節(jié)點維護(hù)到網(wǎng)絡(luò)中所有節(jié)點的路由n所有路由都已經(jīng)存在并且隨時可用n優(yōu)點：路由請求的延遲低n缺點：路由開銷大距離矢量（DISTANCE VECTOR）n基于分布式的Bellman-Ford算法n每個節(jié)點維持一張路由表 所有可達(dá)目的地 到目的地的下一跳 達(dá)到目的地的跳計數(shù)n定期把路由表發(fā)給所有的鄰居DV算法過程n初始化ABC32n路由更新ABC32路由更新消息路由更新消息DV算法無窮計算問題DV算法無窮計算問題（續(xù)）DV算法不能直接用于AD HOC網(wǎng)絡(luò)n計數(shù)到無窮問題n部分解決方法 選擇一個相對較少的數(shù)作為無窮大 水平分割 (sp

8、lit horizon)：當(dāng)一個節(jié)點把路由更新發(fā)送給相鄰節(jié)點時，它并不把從各個相鄰節(jié)點處學(xué)到的路由再回送給該節(jié)點無法發(fā)現(xiàn)路由循環(huán)無法發(fā)現(xiàn)路由循環(huán)限制了網(wǎng)絡(luò)的可擴(kuò)展性限制了網(wǎng)絡(luò)的可擴(kuò)展性對兩個節(jié)點的路由循環(huán)有效，更大的路由循環(huán)需要更強(qiáng)的措施對兩個節(jié)點的路由循環(huán)有效，更大的路由循環(huán)需要更強(qiáng)的措施DSDV協(xié)議 DESTINATION-SEQUENCED DISTANCE VECTOR目的序列距離矢量路由協(xié)議n基于DV算法 簡單、易于實現(xiàn) 需要的存儲空間?。ㄖ缓袜従庸?jié)點交換信息）n確保無路由回路 措施：新的路由表帶有目標(biāo)序列號（由目的節(jié)點生成）n對于拓?fù)渥兓芸焖俜磻?yīng) 當(dāng)路由表發(fā)生重大變化時立即啟動r

9、oute advertisement 延遲不穩(wěn)定路由的通告（減緩路由波動）n先驗式（表驅(qū)動）路由 節(jié)點維護(hù)到所有目的地的路由信息 路由信息必須周期性的更新（無休眠節(jié)點） 即使網(wǎng)絡(luò)拓?fù)錈o變化也存在著通信開銷 維護(hù)的路由可能從不使用DSDV協(xié)議細(xì)節(jié)nDSDV要求每個節(jié)點保存路由表，表中列出了所有可達(dá)的目的節(jié)點及到達(dá)該目的節(jié)點的跳數(shù)。每個路由條目包含目的節(jié)點產(chǎn)生的序列號，用來區(qū)分新舊路由。n節(jié)點間通過周期性地發(fā)布路由更新分組來交互路由信息，以保證路由表的正確性。當(dāng)有重要的新信息是也廣播路由更新分組。*移動節(jié)點收到新的路由信息分組時，路由的更新遵循以下兩個原則：1. 比較該更新分組中攜帶的路由信息和節(jié)

10、點保存的路由條目。如果節(jié)點收到的路由的目的節(jié)點序列號大于路由表中相應(yīng)的目的節(jié)點的序列號，則采用有更新序列號的路由而丟棄原有的舊序列號的路由。 2.如果更新分組中目的節(jié)點序列號與現(xiàn)存的序列號相同，則選擇具有較好度量的路由條目，若新路由有較好度量，則丟棄現(xiàn)存的路由或?qū)⑵浯鎯榇沃酚?。為了減輕網(wǎng)絡(luò)的負(fù)擔(dān)，路由更新分組采用兩種形式：n第一種為“full dump”,它攜帶節(jié)點所有的路由表信息；n另一種為“增長（Incremental）”型數(shù)據(jù)分組，它攜帶的信息是自上次發(fā)送full dump以后節(jié)點的路由表中發(fā)生變化的哪些路由條目的信息。移動節(jié)點還保存一個附加表來存儲已經(jīng)在增長型路由信息數(shù)據(jù)內(nèi)傳送的數(shù)

11、據(jù)。nDSDV算法采用以下兩種方法來檢測鏈路的中斷： 1）鏈路層檢測到某條鏈路中斷時，向路由層報告。 2）通過時間推斷，即節(jié)點在過了一段時間后仍沒有收到某個節(jié)點發(fā)送的分組，就自動認(rèn)為本節(jié)點到該節(jié)點的鏈路中斷，將相應(yīng)的路由條目設(shè)置為無窮大（實際中，若鏈路度量為跳數(shù)，則經(jīng)常設(shè)置為N+1，N為網(wǎng)絡(luò)的節(jié)點數(shù)）來描述斷開的鏈路。n檢測出鏈路中斷的節(jié)點會發(fā)送一個更新分組，該分組有一個新的序列號，跳數(shù)為無窮大。這會引起網(wǎng)絡(luò)中路由表的更新，只有當(dāng)再次收到丟失節(jié)點的信息后新的路由才會重新建立起來。 n雖然在網(wǎng)絡(luò)拓?fù)渥兓l繁的情況下，DSDV協(xié)議的收斂性能不好，但在一般情況下，收斂還是相當(dāng)快的。但是，當(dāng)加入網(wǎng)絡(luò)的

12、節(jié)點越來越多，路由表容量及開銷和帶寬也相應(yīng)的增加。n節(jié)點不一定用到至所有目的節(jié)點的路由條目，多余的路由條目也會造成資源的浪費。DSDV協(xié)議僅支持雙向鏈路，這就限制了其在無線網(wǎng)絡(luò)中的使用。最后，當(dāng)節(jié)點的移動率較高時，DSDV協(xié)議的性能將急劇惡化DSDV路由表nSequence number 由目標(biāo)節(jié)點生成，用來保證不出現(xiàn)路由回路nInstall time 該表項創(chuàng)建時間（用來刪除表中過時路由信息）nStable data 指向一個包含有路由穩(wěn)定狀態(tài)信息的表 用來緩解路由波動路由通告（ROUTE ADVERTISEMENT）n向每個鄰居通告自己的路由信息 目標(biāo)地址 Metric = 到目標(biāo)的跳計數(shù)

13、 目的節(jié)點序列號n設(shè)置序號的規(guī)則 每次通告遞增自己的目標(biāo)序號（只用偶數(shù)值） 如果一個節(jié)點不再可達(dá)（timeout），則將該節(jié)點的序號遞增1（奇數(shù)值）并置metric = 路由選擇（ROUTE SELECTION）n將收到的路由更新信息與自己的路由表比較 選擇目標(biāo)序號大的路由（這樣能確保使用的總是來自目的地的最新路由信息） 如果目標(biāo)序號相同，則選擇具有較好metric值的路由DSDV實例DSDV實例（續(xù)）DSDV對拓?fù)渥兓捻憫?yīng)n立即通告 有關(guān)新路由、鏈路中斷、metric變化的信息立即傳播給鄰居n完全/增量更新 完全（Full Update） 發(fā)送路由表的全部路由信息 增量（Increment

14、al Update） 僅發(fā)送路由表中有變化的表項n使得可用一個分組完成更新增加一個新節(jié)點-1增加一個新節(jié)點-2如何解決路由回路和無窮計算？拓?fù)渥兓瘯r的立即通告DSDV協(xié)議操作：路由波動2. A收到來自收到來自P的路由更新消的路由更新消息息11 Hops12 HopsAPQD1. D公告序列號為公告序列號為D-102的的路由路由更新路由表中到更新路由表中到D的表項的表項立即進(jìn)行路由公告立即進(jìn)行路由公告3. A收到來自收到來自Q的路由更新消的路由更新消息息更新路由表中到更新路由表中到D的表項的表項立即進(jìn)行路由公告立即進(jìn)行路由公告由于由于D或者任何一個節(jié)點的路由更新消息到或者任何一個節(jié)點的路由更新消

15、息到達(dá)節(jié)點達(dá)節(jié)點A時存在著時間差時存在著時間差,就會導(dǎo)致不必要的就會導(dǎo)致不必要的路由公告路由公告路由表波動路由表波動DSDV協(xié)議操作：減緩路由波動n在一個單獨的表中記錄每條路由的最近的和平均的Settling Time Settling Time：第一條路由和最佳路由之間的時間間隔 路由表中的stable data指向該表nA在包含新序列號的第一條路由到達(dá)時更新路由表，但是等待一段時間再廣播該條路由 等待時間=2*(avg. Setting Time)10 Hops11 HopsAPQD可緩解大型網(wǎng)絡(luò)的路由波動問題，可緩解大型網(wǎng)絡(luò)的路由波動問題，從而避免不必要的公告，節(jié)約了帶寬從而避免不必要的

16、公告，節(jié)約了帶寬DSDV總結(jié)n優(yōu)點 簡單（幾乎與DV算法一致） 通過目的地賦予的序號值來防止出現(xiàn)路由回路 不存在路由發(fā)現(xiàn)帶來的延遲n缺點 沒有節(jié)點睡眠 收斂慢 開銷：多數(shù)路由信息從不使用DSDV總結(jié)1）DSDV能迅速地為節(jié)點建立路由并發(fā)送數(shù)據(jù)，在任何情況下都能避免路由環(huán)路。2）在網(wǎng)絡(luò)拓?fù)渥兓l繁的情況下，DSDV收斂性并不好3）由于要求節(jié)點定期廣播路由更新消息，當(dāng)加入的節(jié)點越來越多時，路由表的容量，開銷和帶寬要求也急劇上升，這是DSDV的主要缺點。4）DSDV要求節(jié)點保存到網(wǎng)絡(luò)中所有節(jié)點的路由，造成很大的浪費。5）當(dāng)節(jié)點的移動率較高時，DSDV協(xié)議的性能將急劇惡化WRP協(xié)議（WIRELESS

17、ROUTING PROTOCOL）無線路由協(xié)議nWRP協(xié)議中，節(jié)點保存的信息表包括距離表、路由表、鏈路開銷表、分組重傳列表4個部分。節(jié)點通過獲得鄰節(jié)點的狀態(tài)變化信息來維護(hù)自己的信息表，并通知鄰節(jié)點；收到來自鄰節(jié)點的信息后，要更改保存的信息表，節(jié)點需要發(fā)送一個回復(fù)分組（ACK）說明已經(jīng)收到并處理了某個更新消息。n若節(jié)點沒有轉(zhuǎn)發(fā)數(shù)據(jù)分組或是更新消息，則要定期發(fā)送HELLO分組，以確保節(jié)點間的聯(lián)通性，節(jié)點在一段時間內(nèi)沒收到鄰節(jié)點發(fā)送的任何分組，就認(rèn)為和該鄰節(jié)點間的鏈路失敗。節(jié)點就要重新計算到受影響的目的節(jié)點的距離和對應(yīng)的前驅(qū)節(jié)點，并且向其鄰節(jié)點發(fā)送更新分組通知哪些目的節(jié)點的距離和前驅(qū)節(jié)點發(fā)生變化。n

18、WRP通過記錄到目的節(jié)點的距離信息和先驅(qū)節(jié)點（Predecessor）信息解決路由環(huán)路問題。 所謂先驅(qū)節(jié)點是指到所選的目的節(jié)點的路由上，目的節(jié)點的前一個節(jié)點，也稱為“倒數(shù)第二跳”節(jié)點（Second-to-last Hop）。nWRP要求節(jié)點維護(hù)4張路由表，這會給節(jié)點帶來負(fù)擔(dān)，特別是節(jié)點較多的時候。n由于利用HELLO分組保持連通性，WRP不允許節(jié)點處于睡眠狀態(tài)，這會耗費電池電量，網(wǎng)絡(luò)的帶寬也會被更新分組大量占用。按需（ON-DEMAND）路由n反應(yīng)式（reactive）路由 在源端需要時通過路由發(fā)現(xiàn)過程來確定路由 控制信息采用洪泛（flooding）方式 路由請求延遲高 路由開銷低 兩種實現(xiàn)技

19、術(shù) 源路由（報文頭攜帶完整的路由信息） 逐跳（hop-hop）路由按需操作的優(yōu)點n路由發(fā)現(xiàn)和維護(hù)都是按需進(jìn)行的 不需要周期性的通告路由 不需要感測鏈路狀態(tài)/不需要鄰居檢測 不依賴于任何底層協(xié)議動態(tài)源路由協(xié)議(DSR)nDynamic Source Routing 按需路由 節(jié)點需要發(fā)送數(shù)據(jù)時才進(jìn)行路由發(fā)現(xiàn)過程 反應(yīng)型路由，僅維護(hù)活躍的路由 源路由 發(fā)送節(jié)點在分組中攜帶到達(dá)目的節(jié)點的路由信息（轉(zhuǎn)發(fā)分組的完整的節(jié)點序列）n不需要中間節(jié)點維護(hù)路由信息 節(jié)點緩存到目的節(jié)點的多條路由n避免了在每次路由中斷時都需要進(jìn)行路由發(fā)現(xiàn)，因此能夠?qū)ν負(fù)渥兓鞒龈斓姆磻?yīng)，DSR工作流程:1)源節(jié)點S將使用洪泛技術(shù)發(fā)

20、送路由請求消息RREQ，其中包含源節(jié)點地址，目的節(jié)點地址，唯一的標(biāo)志號以及中間節(jié)點列表。2）中間節(jié)點轉(zhuǎn)發(fā)RREQ，并附上自己的標(biāo)識。3）當(dāng)RREQ消息到達(dá)目的節(jié)點D或任何一個緩存有到目的節(jié)點D的路由的中間節(jié)點時，D或該中間節(jié)點將向S發(fā)送路由應(yīng)答消息RREP，該消息中將包含節(jié)點S到D的路由信息，并反轉(zhuǎn)節(jié)點S到D的路徑供RREP消息使用。4）節(jié)點S收到RREP后，路由建立過程結(jié)束，通信可以開始。5）在通信過程中，當(dāng)中間節(jié)點檢測到通往目的節(jié)點D的下一跳鏈路中斷時，它將從自己的路由緩存中移除包含該鏈路的路由，并向節(jié)點S返回一個路由出錯分組RRER。6）節(jié)點S收到路由出錯分組RRER，觸發(fā)一次新的路由建

21、立DSR協(xié)議描述nDSR協(xié)議由兩個相互協(xié)同的機(jī)制組成 Route discovery 由需要發(fā)送數(shù)據(jù)給目的節(jié)點D的源節(jié)點S使用 該過程只在S需要發(fā)送數(shù)據(jù)并且不知道到D的路由時才啟動 Route maintenance 節(jié)點S在給D發(fā)送數(shù)據(jù)時要能檢測出由于網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化導(dǎo)致源路由中斷的情況 當(dāng)前的源路由不能用時，S切換到另一條已知的路由或者重新發(fā)起route discovery尋找新路由DSR路由發(fā)現(xiàn)：路由請求n源節(jié)點向鄰居節(jié)點廣播路由請求（RREQ：Route Request）消息 源節(jié)點地址 目的節(jié)點地址 路由記錄：紀(jì)錄從源節(jié)點到目的節(jié)點路由中的中間節(jié)點 請求IDn中間節(jié)點接收到RREQ后

22、，將自己的地址附在路由紀(jì)錄中ABCDEF(A-)(A-F)(A-)(A-B-)(A-B-C-)(A-B-C-)(A-B-C-E-)DSR路由發(fā)現(xiàn)：中間節(jié)點處理n中間節(jié)點維護(hù)序列對列表n重復(fù)RREQ檢測 如果接收到的RREQ消息中的存在于本節(jié)點的序列對列表中 如果接收到的RREQ消息中的路由紀(jì)錄中包含本節(jié)點的地址n如果檢測到重復(fù)，則中間節(jié)點丟棄該RREQ消息ABCDEF(A-)(A-F)(A-)(A-B-)(A-B-C-)(A-B-C-)(A-B-C-E-)丟棄丟棄F轉(zhuǎn)發(fā)轉(zhuǎn)發(fā)的的RREQDSR路由發(fā)現(xiàn)：路由應(yīng)答n目的節(jié)點收到RREQ后，給源節(jié)點返回路由應(yīng)答（RREP：Route Reply）消息

23、 拷貝RREQ消息中的路由紀(jì)錄n源節(jié)點收到RREP后在本地路由緩存中緩存路由信息(A-B-C-D)ABCDEF(A-B-C-D)(A-B-C-D)DSR路由發(fā)現(xiàn)：非對稱信道n對稱信道 目的節(jié)點到源節(jié)點的路由即為源節(jié)點到目的節(jié)點的反向路由n非對稱信道 如果目的節(jié)點的路由緩存中有到達(dá)源節(jié)點的路由，則直接使用 否則目的節(jié)點需要發(fā)起到源節(jié)點的路由請求過程，同時將RREP消息稍帶在新的RREQ消息中DSR的多路徑思想n多路徑獲得途徑 作為route discovery的響應(yīng) Overheard到其他路由控制包和數(shù)據(jù)包中的路由信息 為任何目的地緩存多條路由n多路徑的作用 如果正在使用的一條路徑中斷，節(jié)點可

24、立即切換到另一條緩存的路由 多條路由的緩存可避免每次路由中斷后執(zhí)行route discoveryDSR基本ROUTE MAINTENANCEn路由的維護(hù) 每個節(jié)點確保使用源路由發(fā)送/轉(zhuǎn)發(fā)的數(shù)據(jù)報被路徑上的下一跳接收 若沒有收到下一跳確認(rèn)則不斷重發(fā)（直至最大重試次數(shù)）n如何確保數(shù)據(jù)報被逐跳轉(zhuǎn)發(fā) 鏈路級的確認(rèn)（IEEE 802.11） 被動確認(rèn)（B偵聽C向D轉(zhuǎn)發(fā)） 要求DSR軟件返回確認(rèn)基本ROUTE MAINTENANCE（續(xù)）n如果數(shù)據(jù)分組被重發(fā)了最大次數(shù)仍然沒有收到下一跳的確認(rèn)，則節(jié)點（C）要向分組的源端發(fā)送route error（PERR）消息，并指明中斷的鏈路n分組的源端A將該路由從路由

25、緩存中刪除n若源端路由緩存存在另一條到目標(biāo)的路由則重發(fā)此分組n否則，重新開始route discovery過程DSR優(yōu)化：路由緩存(1)n 每個節(jié)點緩存它通過任何方式獲得的新路由 轉(zhuǎn)發(fā)RREQ 獲得從本節(jié)點到RREQ路由記錄中所有節(jié)點的路由，例如E轉(zhuǎn)發(fā)RREQ(A-B-C)獲得到到A的路由(C-B-A) 轉(zhuǎn)發(fā)RREP 獲得本節(jié)點到RREP路由紀(jì)錄中所有節(jié)點的路由，例如B轉(zhuǎn)發(fā)RREP(A-B-C-D)獲得到D的路由(C-D) 轉(zhuǎn)發(fā)數(shù)據(jù)分組 獲得從本節(jié)點到數(shù)據(jù)分組節(jié)點列表中所有節(jié)點的路由，例如E轉(zhuǎn)發(fā)數(shù)據(jù)分組(A-B-C)獲得到A的路由(C-B-A) 監(jiān)聽相鄰節(jié)點發(fā)送的分組 RREQ、RREP、數(shù)據(jù)

26、分組等(A-B-C-D)ABCDEF(A-B-C-D)(A-B-C-D)ABCDEF(A-)(A-F)(A-)(A-B-)(A-B-C-)(A-B-C-)(A-B-C-E-)以上均假設(shè)信道是對稱的以上均假設(shè)信道是對稱的!DSR優(yōu)化：路由緩存(2)n中間節(jié)點使用緩存的到目的節(jié)點的路由響應(yīng)RREQ RREP中的路由紀(jì)錄=RREQ中的路由紀(jì)錄+緩存的到目的節(jié)點的路由ABCDEF(B-C-D)(A-B-C-D)(A-)DSR優(yōu)化：路由緩存(3)nRREP風(fēng)暴 節(jié)點廣播到某個目的節(jié)點的RREQ，當(dāng)其鄰居節(jié)點的路由緩存中都有到該目的節(jié)點的路由時，每個鄰居節(jié)點都試圖以自己緩存的路由響應(yīng)，由此造成RREP風(fēng)暴

27、 RREP風(fēng)暴將浪費網(wǎng)絡(luò)帶寬，并且加劇消息沖突ABCDEF(B-A)G(C-B-A)(F-A)(E-C-B-A)G發(fā)起到發(fā)起到A的的路由發(fā)現(xiàn)過程路由發(fā)現(xiàn)過程DSR優(yōu)化：路由緩存(4)n預(yù)防RREP風(fēng)暴 每個節(jié)點延時D發(fā)送RREP D與節(jié)點到目的節(jié)點的跳數(shù)成正比，使得到目的節(jié)點有最短路徑的RREP最先發(fā)送 節(jié)點將接口設(shè)置成混雜模式(promiscuous)，監(jiān)聽是否存在有比自己更短的到目的節(jié)點的路徑，如果有，則不發(fā)送本節(jié)點的RREPD=H*（h-1+r）其中其中H是每條鏈路的傳播延時是每條鏈路的傳播延時h是自己返回的路徑長度，即到目的節(jié)點的跳數(shù)是自己返回的路徑長度，即到目的節(jié)點的跳數(shù)r是是0或者

28、或者1DSR協(xié)議優(yōu)點n節(jié)點不需要周期性地發(fā)送路由廣播分組n無需維持到全網(wǎng)所有節(jié)點的路由信息 節(jié)省了電池能量和網(wǎng)絡(luò)帶寬，尤其是當(dāng)沒有節(jié)點要發(fā)送數(shù)據(jù)時，網(wǎng)絡(luò)中沒有通信開銷n僅需要維護(hù)路徑上節(jié)點之間的聯(lián)通n能完全消除路由環(huán)路n能同時提供多條路由n可用于單向信道n中間節(jié)點的應(yīng)答使源節(jié)點快速獲得路由DSR協(xié)議缺點n會引起過時路由問題n每個分組都需要攜帶完整的路由信息 開銷增大 降低了網(wǎng)絡(luò)帶寬的利用率 不適合網(wǎng)絡(luò)直徑大的自組網(wǎng) 網(wǎng)絡(luò)可擴(kuò)展性不強(qiáng)按需距離矢量路由協(xié)議AODV內(nèi)容n1、AODV 概述n2、RREQ路由請求幀n3、RREP路由應(yīng)答幀n4、路由發(fā)現(xiàn)和維護(hù)n5、路由錯誤控制n6、擁塞控制1、AODV

29、 概述nAODV是為快速移動自組網(wǎng)（MANET）設(shè)計的數(shù)據(jù)包路由協(xié)議n較適用于有大量節(jié)點的無線自主網(wǎng)絡(luò)n按需路由協(xié)議，只有當(dāng)?shù)竭_(dá)某目的節(jié)點的路由不存在時才會激活該協(xié)議發(fā)起路由請求n使用節(jié)點序列號機(jī)制避免環(huán)路產(chǎn)生n傳輸層使用的是UDP協(xié)議 n網(wǎng)絡(luò)各節(jié)點使用IP地址統(tǒng)一編址n每一個節(jié)點維護(hù)一個包含到達(dá)目的節(jié)點路由信息的路由表路由表字段n目的節(jié)點IP地址n目的節(jié)點序列號（Sequence Number）n目的節(jié)點序列號有效標(biāo)志位n下一跳節(jié)點IP地址n本節(jié)點到達(dá)目的節(jié)點的跳數(shù)n前驅(qū)節(jié)點列表（precursor list）n生存時間（路由失效或刪除時間）n網(wǎng)絡(luò)層接口n其他的狀態(tài)和路由標(biāo)志位n路由表每項只

30、記錄下一跳路由信息，而不是整條路由信息，簡化了路由表的建立和維護(hù)n源節(jié)點和目的節(jié)點都維護(hù)各自的序列號n如何管理序列號是提高路由建立和維護(hù)的關(guān)鍵 序列號是用來標(biāo)識路由信息新舊程度（freshness）的 源節(jié)點發(fā)起路由請求RREQ，或者目的節(jié)點返回路由應(yīng)答RREP，都要更新各自的序列號 其他節(jié)點（中間節(jié)點）依據(jù)序列號的大小判斷路由的新舊nAODV路由幀格式主要包括: RREQ 路由請求幀 RREP 路由應(yīng)答幀 RERR 路由錯誤幀 HELLO 活躍路由鏈路監(jiān)測幀AODV路由請求的發(fā)起流程圖AODV對路由控制信息的控制流程圖2、RREQ路由請求幀n幀格式為：RREQ路請求由幀 在兩個節(jié)點之間的路由

31、有效、通信正常的情況下，AODV路由協(xié)議不起任何作用 只有當(dāng)源節(jié)點S需要向目的節(jié)點D發(fā)送數(shù)據(jù)包，但又沒有D節(jié)點的路由入口時才會發(fā)起路由請求，即發(fā)送路由廣播幀RREQ 當(dāng)RREQ在網(wǎng)絡(luò)中傳播時，中間節(jié)點會更新各自到源節(jié)點的路由，我們稱此路由為反向路由 RREQ請求幀中包含源節(jié)點以前記錄的到目的節(jié)點的序列號，但此序列號可能不是最新的（最大的） 中間節(jié)點如果有到目的節(jié)點的路由時，只有該節(jié)點記錄的目的節(jié)點序列號比RREQ中的目的節(jié)點序列號更新（更大）時，才認(rèn)為這條路由是有效的RREQ請求幀的傳播n應(yīng)答幀格式：3、RREP路由應(yīng)答幀RREP應(yīng)答幀 當(dāng)RREQ最終到達(dá)目的節(jié)點時，目的節(jié)點通過向該反向路由（

32、即該RREQ傳播路線）發(fā)送RREP應(yīng)答幀，從而在該條路徑的各個節(jié)點建立通向目的節(jié)點的前向路由 只有在以下情況下節(jié)點才會產(chǎn)生RREP: 該節(jié)點本身就是目的節(jié)點 該節(jié)點為中間節(jié)點，但是它有通向目的節(jié)點的活躍路徑 當(dāng)RREP傳播到源節(jié)點時，中間節(jié)點根據(jù)該RREP更新它們各自指向目的節(jié)點的路由信息 節(jié)點只對第一次收到的RREQ發(fā)送RREP應(yīng)答幀，之后到達(dá)的RREQ將被忽略RREP路由應(yīng)答幀的傳播4、路由發(fā)現(xiàn)和維護(hù)n路由發(fā)現(xiàn)過程 廣播RREQ路由請求幀 中間節(jié)點更新各自到源節(jié)點的路由表 如果收到RREQ的節(jié)點不是目的節(jié)點，并且沒有到達(dá)目的節(jié)點的更新的有效路由，則轉(zhuǎn)發(fā)該RREQ 中間節(jié)點維護(hù)指向路由發(fā)起節(jié)

33、點（源節(jié)點）的反向路由 目的節(jié)點或存在到目的節(jié)點有效路由的中間節(jié)點產(chǎn)生RREP路由應(yīng)答幀 RREP通過之前建立的反向節(jié)點單播至源節(jié)點 源節(jié)點收到RREP應(yīng)答幀，至此源節(jié)點可以向目的節(jié)點發(fā)送數(shù)據(jù)包 路由發(fā)現(xiàn)算法n源節(jié)點 應(yīng)用層有數(shù)據(jù)發(fā)送請求，并且指向目的節(jié)點的路由有效，直接通過該路由發(fā)送數(shù)據(jù)包 如果沒有到達(dá)目的節(jié)點的有效路徑，則產(chǎn)生RREQ廣播幀，RREQ的序列號、ID字段加1，將源節(jié)點的IP、序列號，目的節(jié)點的IP、序列號等信息添加到該RREQ中，廣播至網(wǎng)絡(luò)n中間節(jié)點 如果中間節(jié)點路由表中記錄的到目的節(jié)點的路由有效，并且記錄的目的節(jié)點的序列號比RREQ中的目的節(jié)點序列號更新（大于或者等于），則

34、該中間節(jié)點可以產(chǎn)生路由應(yīng)答幀。如果該中間節(jié)點不產(chǎn)生應(yīng)答幀，更改RREQ中的目的節(jié)點序列號至當(dāng)前最大，跳數(shù)字段加1，然后轉(zhuǎn)發(fā)n目的節(jié)點 目的節(jié)點的序列號加1 產(chǎn)生RREP應(yīng)答幀（包括源節(jié)點的IP、目的節(jié)點的IP和更新后的序列號），單播發(fā)送至源節(jié)點 路由發(fā)現(xiàn)圖示ABDFCGERREQRREQRREQRREQRREQRREQRREQRREQRREQRREPRREPRREPSourceDestination路由維護(hù)nHello消息 Hello消息幀其實就是TTL=1時的RREP幀。TTL（Time-To-Live)為IP數(shù)據(jù)包字段，表示該幀的傳播跳數(shù)。 Hello消息幀用于監(jiān)測活躍路徑上相鄰節(jié)點的鏈接

35、狀況。 例如：當(dāng)活躍路徑上某節(jié)點ALLOWED_HELLO_LOSS * HELLO_INTERVAL毫秒時間內(nèi)沒有收到該路徑上的鄰居節(jié)點發(fā)送來的Hello消息幀或其他任何幀時，該節(jié)點就認(rèn)為與它與鄰居節(jié)點的鏈路已斷 只有當(dāng)某節(jié)點位于某活躍路徑之上時，它才能發(fā)送Hello消息幀n活躍路徑節(jié)點以HELLO_INTERVAL為周期發(fā)送Hello消息n在DELETE_PERIOD的時間內(nèi)沒有收到來自鄰居節(jié)點的Hello消息，則認(rèn)為該鏈路已失效n發(fā)起一次指向該鄰居節(jié)點的局部修復(fù)n路由修復(fù)超時以后，路由錯誤信息RERR向源節(jié)點和目的節(jié)點發(fā)送nRERR傳播過程中，各中間節(jié)點刪除該失效路徑上相應(yīng)的路由信息路由信息新舊判斷nAODV依賴網(wǎng)絡(luò)中每個節(jié)點維護(hù)自身的序列號n源節(jié)點在廣播路由請求幀RREQ之前要先更新自己的序列號，即將序列號加1n目的節(jié)點在產(chǎn)生RREP應(yīng)答幀之前也要將自身的序列號加1n每個節(jié)點在對各自的序列號加1的時候是將其視為無符號數(shù)進(jìn)行的n通過比較來自目的