adhoc網(wǎng)絡(luò)的路由協(xié)議

1、無線自組織網(wǎng)絡(luò)無線自組織網(wǎng)絡(luò)路由協(xié)議路由協(xié)議2提綱提綱p路由協(xié)議概述pAd hoc網(wǎng)絡(luò)與Internet網(wǎng)絡(luò)路由設(shè)計的區(qū)別pAd hoc網(wǎng)絡(luò)路由協(xié)議分類 表驅(qū)動（Table Driven）路由協(xié)議 按需驅(qū)動（On-demand Driven）路由協(xié)議 混合式（Hybrid）路由協(xié)議p典型路由協(xié)議 DSR、AODV DSR路由仿真演示3應(yīng)用層傳輸層網(wǎng)絡(luò)層數(shù)據(jù)鏈路層(MAC)物理層需要確定從起始源節(jié)點到最終目的節(jié)點（端到端）的有效路由需要解決相鄰節(jié)點間(點到點)的信道接入問題231451168971014121315自組織網(wǎng)絡(luò)協(xié)議棧結(jié)構(gòu)自組織網(wǎng)絡(luò)協(xié)議棧結(jié)構(gòu)4路由協(xié)議概述路由協(xié)議概述p路由協(xié)議：通信

2、網(wǎng)絡(luò)中的一套將業(yè)務(wù)數(shù)據(jù)從源節(jié)點指引到目的節(jié)點的機制。p路由設(shè)計目標(biāo) 正確性、簡單性 健壯性（robustness）、穩(wěn)定性 公平性、最優(yōu)性p路由協(xié)議構(gòu)成： 路由生成（Path Generation） 路徑選擇（Path Selection） 路徑維護(hù)（Path Maintenance）5Ad hoc網(wǎng)絡(luò)網(wǎng)絡(luò)與與互聯(lián)網(wǎng)路由設(shè)計互聯(lián)網(wǎng)路由設(shè)計的區(qū)別的區(qū)別pAd hoc網(wǎng)絡(luò)中節(jié)點既是終端又是路由器，參與分組轉(zhuǎn)發(fā)；因特網(wǎng)中終端和路由器的角色由不同節(jié)點擔(dān)任。由于應(yīng)用環(huán)境和功能的差異，二者在路由協(xié)議設(shè)計上存在諸多區(qū)別： Ad hoc網(wǎng)絡(luò)中存在單向鏈路?；陔p向鏈路的傳統(tǒng)路由選擇算法在ad hoc網(wǎng)絡(luò)中已不

3、再適用。 無線環(huán)境中可能存在很多“多余”鏈路。傳統(tǒng)的有線網(wǎng)絡(luò)中，任意兩個網(wǎng)絡(luò)之間通常只會配置一個或均勻配置少量的路由器。而無線網(wǎng)絡(luò)中由于節(jié)點的移動性，某時刻源節(jié)點或轉(zhuǎn)發(fā)節(jié)點周圍可能會密集分布多個節(jié)點，這些節(jié)點均處于臨近節(jié)點的傳輸范圍內(nèi)，容易形成多條等效的轉(zhuǎn)發(fā)鏈路。這些鏈路的代價相同，可以認(rèn)為是多余的。6Ad hoc網(wǎng)絡(luò)網(wǎng)絡(luò)與與互聯(lián)網(wǎng)路由設(shè)計互聯(lián)網(wǎng)路由設(shè)計的區(qū)別的區(qū)別pAd hoc網(wǎng)絡(luò)與Internet網(wǎng)絡(luò)在路由協(xié)議設(shè)計上存在的區(qū)別： 無線節(jié)點通常是能量受限的終端。無線網(wǎng)絡(luò)中的節(jié)點通常依靠電池提供能量，因此節(jié)能很大程度上決定了無線節(jié)點的使用壽命。傳統(tǒng)Internet網(wǎng)絡(luò)中的路由協(xié)議大多需要路由器

4、間頻繁的信息交互，這對于有穩(wěn)定能量供應(yīng)的有線網(wǎng)絡(luò)而言可能無足輕重，而對于能量受限的無線節(jié)點而言卻是無法承受的。 無線環(huán)境中動態(tài)變化的網(wǎng)絡(luò)拓?fù)?。傳統(tǒng)的路由協(xié)議是針對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相對穩(wěn)定的有線網(wǎng)絡(luò)而設(shè)計的，當(dāng)應(yīng)用于無線網(wǎng)絡(luò)中時，會出現(xiàn)大量的問題。收斂速度是衡量路由協(xié)議性能的重要指標(biāo)。由于無線網(wǎng)絡(luò)中節(jié)點移動頻繁，需要交互更多的變化的拓?fù)湫畔?，路由協(xié)議的收斂相對較慢。7Ad hoc網(wǎng)絡(luò)路由協(xié)議的分類網(wǎng)絡(luò)路由協(xié)議的分類p現(xiàn)有Ad hoc網(wǎng)絡(luò)的路由協(xié)議根據(jù)發(fā)現(xiàn)路由的驅(qū) 動 方 式 的 不 同 可 分 為 表 驅(qū) 動 （ Ta b l e Driven）、按需驅(qū)動（On-demand Driven）和混合式

5、（Hybrid）路由協(xié)議三類。Ad Hoc網(wǎng)絡(luò)路由協(xié)議混合式路由協(xié)議DSDVWRPAODVDSRLAR按需驅(qū)動路由協(xié)議表驅(qū)動路由協(xié)議ZRP8Ad hoc網(wǎng)絡(luò)路由協(xié)議的分類網(wǎng)絡(luò)路由協(xié)議的分類 表驅(qū)動（Table Driven）路由協(xié)議又稱先驗式路由協(xié)議，主要是沿用了傳統(tǒng)有線網(wǎng)絡(luò)中路由協(xié)議的基本思想，即節(jié)點通過查詢預(yù)先配置的路由表來實現(xiàn)分組的轉(zhuǎn)發(fā)。節(jié)點間周期性地交互各自的路由信息，每個節(jié)點試圖維護(hù)到網(wǎng)絡(luò)中所有其他節(jié)點的路由信息。節(jié)點在檢測到周圍網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時，會及時地發(fā)送路由更新，收到路由更新的節(jié)點將更新自己的路由表。表驅(qū)動路由協(xié)議的時延較小，但路由協(xié)議的開銷較大。由于其先驗性，每個節(jié)點都必須

6、維護(hù)路由表，而通常網(wǎng)絡(luò)中只有少數(shù)節(jié)點承擔(dān)著數(shù)據(jù)分組的轉(zhuǎn)發(fā)任務(wù)，不會參與分組轉(zhuǎn)發(fā)的節(jié)點實際上并沒有維護(hù)路由表的必要，這樣就大大浪費了寶貴的無線帶寬資源。9Ad hoc網(wǎng)絡(luò)路由協(xié)議的分類網(wǎng)絡(luò)路由協(xié)議的分類 按需驅(qū)動（On-demand Driven）路由協(xié)議又稱反應(yīng)式路由或被動路由。節(jié)點無需實時維護(hù)整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息，其路由信息是按需建立的。當(dāng)節(jié)點有數(shù)據(jù)分組需要發(fā)送時，才嘗試發(fā)起路由發(fā)現(xiàn)過程。通常源節(jié)點采用洪泛（Flooding）的方式向鄰居節(jié)點廣播路由請求消息，目的節(jié)點收到該路由請求消息時，向源節(jié)點返回路由應(yīng)答，路由應(yīng)答消息中包含著從源節(jié)點到目的節(jié)點的全路由信息。按需路由不需要節(jié)點周期性的交

7、互各自的路由信息，節(jié)省了一定的帶寬資源，只需要參與轉(zhuǎn)發(fā)的節(jié)點維護(hù)部分網(wǎng)絡(luò)拓?fù)湫畔?，減少了內(nèi)存的占用。但是當(dāng)源節(jié)點沒有到達(dá)目的節(jié)點的路由時，要實時發(fā)起路由尋找過程，數(shù)據(jù)分組的傳輸有一定的延時，因而按需驅(qū)動的路由方式不利于數(shù)據(jù)的實時傳輸。10Ad hoc網(wǎng)絡(luò)路由協(xié)議的分類網(wǎng)絡(luò)路由協(xié)議的分類 混合式（Hybrid）路由協(xié)議很多具體的ad hoc網(wǎng)絡(luò)場合中，單純的采用按需驅(qū)動或表驅(qū)動的路由方式并不能完全解決路由問題。于是，許多研究工作嘗試結(jié)合按需驅(qū)動路由協(xié)議和表驅(qū)動路由協(xié)議各自的優(yōu)點來設(shè)計混合式路由協(xié)議。然而，混合式路由協(xié)議的具體實現(xiàn)也面臨著很多困難，如具體表驅(qū)動和按需驅(qū)動路由協(xié)議的搭配方式等問題。1

8、1p DSR（Dynamic Source Routing ） 基于源路由方式的按需路由協(xié)議。 節(jié)點需要發(fā)送數(shù)據(jù)分組時才進(jìn)行路由發(fā)現(xiàn)過程。 發(fā)送節(jié)點在路由分組中包含了源源-目的節(jié)點的目的節(jié)點的完整路由信息完整路由信息，該路由信息由網(wǎng)絡(luò)中的若干節(jié)點地址組成，各個節(jié)點按照該路由信息來轉(zhuǎn)發(fā)分組。 按需驅(qū)動路由協(xié)議按需驅(qū)動路由協(xié)議12pDSR（Dynamic Source Routing ） 節(jié)點不需要實時地維護(hù)網(wǎng)絡(luò)的拓?fù)湫畔?，那么在?jié)點需要發(fā)送數(shù)據(jù)時，如何獲知源-目的節(jié)點的路由？按需驅(qū)動路由協(xié)議按需驅(qū)動路由協(xié)議13p DSR（Dynamic Source Routing ）路由發(fā)現(xiàn)（Route Di

9、scovery）和路由維護(hù)（Route Maintenance）兩部分： 路由發(fā)現(xiàn)： -節(jié)點需要發(fā)送數(shù)據(jù)分組時才啟動； -幫助源節(jié)點獲得到達(dá)目的節(jié)點的路由。 路由維護(hù) -在源節(jié)點給目的節(jié)點發(fā)送數(shù)據(jù)時監(jiān)測當(dāng)前路由的可用情況； -當(dāng)網(wǎng)絡(luò)拓?fù)渥兓瘜?dǎo)致路由故障時，切換到另一條路由或者重新發(fā)起路由發(fā)現(xiàn)過程。按需驅(qū)動路由協(xié)議按需驅(qū)動路由協(xié)議14pDSR（Dynamic Source Routing ） 路由發(fā)現(xiàn)：（1）當(dāng)一個節(jié)點要發(fā)送分組給某一目的節(jié)點時，它會首先查看自己的路由緩存中是否已有現(xiàn)成的路由信息可以使用。如果存在一條到達(dá)目的節(jié)點的路由，并且其生存期沒有到期，則直接使用此路由發(fā)送分組；（2）如果路

10、由緩存中沒有通向目的節(jié)點的路由,則啟動路由發(fā)現(xiàn)(route Discovery)過程。路由發(fā)現(xiàn)過程使用洪泛路由（flooding routing）技術(shù)。按需驅(qū)動路由協(xié)議按需驅(qū)動路由協(xié)議15pDSR路由發(fā)現(xiàn)過程 路由發(fā)現(xiàn)的基本操作（1）源節(jié)點向鄰居節(jié)點廣播路由請求（RREQ）報文RREQ中包含以下信息：源節(jié)點地址；目的節(jié)點地址；路由記錄（按順序累積記錄此路由請求報文所經(jīng)過的節(jié)點的地址）；請求ID（由源節(jié)點自己產(chǎn)生的序號，同一個節(jié)點所發(fā)送的路由請求報文中的請求標(biāo)識均不同）。一組可以唯一確定一個路由請求報文。按需驅(qū)動路由協(xié)議按需驅(qū)動路由協(xié)議16pDSR路由發(fā)現(xiàn)過程 路由發(fā)現(xiàn)的基本操作（2）中間節(jié)點收

11、到路由請求報文后，需要進(jìn)行請求報文檢測。中間節(jié)點收到來自同一個源節(jié)點，并且請求ID相同的路由請求報文，則直接將該報文丟棄。按需驅(qū)動路由協(xié)議按需驅(qū)動路由協(xié)議17pDSR路由發(fā)現(xiàn)過程 路由發(fā)現(xiàn)的基本操作（2）中間節(jié)點收到路由請求報文后，需要進(jìn)行請求報文檢測。中間節(jié)點收到路由請求報文中的路由記錄已經(jīng)包含本中間節(jié)點，則直接將該報文丟棄。中間節(jié)點的緩存中已經(jīng)有到達(dá)目的節(jié)點的路由，直接向源節(jié)點發(fā)送路由應(yīng)答報文進(jìn)行應(yīng)答。按需驅(qū)動路由協(xié)議按需驅(qū)動路由協(xié)議18pDSR路由發(fā)現(xiàn)過程 路由發(fā)現(xiàn)的基本操作（2）中間節(jié)點收到路由請求報文后，需要進(jìn)行請求報文檢測。若路由請求報文是未處理過的，中間節(jié)點則：-將自己的地址附在

12、路由記錄中；-將該路由請求報文作為本地廣播分組發(fā)送給鄰居節(jié)點。按需驅(qū)動路由協(xié)議按需驅(qū)動路由協(xié)議19pDSR路由發(fā)現(xiàn)過程 路由發(fā)現(xiàn)的基本操作（3）如果接收節(jié)點就是目的節(jié)點，這時路由記錄字段中記錄的節(jié)點地址序列，就構(gòu)成了從源節(jié)點到目的節(jié)點的路由信息，把此路由信息加入到路由應(yīng)答報文中，并將此報文回送給源節(jié)點。按需驅(qū)動路由協(xié)議按需驅(qū)動路由協(xié)議20pDSR路由發(fā)現(xiàn)過程按需驅(qū)動路由協(xié)議按需驅(qū)動路由協(xié)議21pDSR路由發(fā)現(xiàn)過程：路由應(yīng)答 路由應(yīng)答的基本操作目的節(jié)點接收到路由請求后，把路由信息加入到路由應(yīng)答報文（RREP）中，并將此報文回送給源節(jié)點。如果目的節(jié)點路由緩存中有到達(dá)發(fā)起節(jié)點的路由，此時目的節(jié)點可以

13、直接使用該路由回送路由應(yīng)答。如果目的節(jié)點路由緩存中沒有到達(dá)發(fā)起節(jié)點的路由，此時需要考慮節(jié)點通信鏈路的方向性問題。如果源-目的是雙向通信鏈路，此時目的節(jié)點到發(fā)起節(jié)點的路由即為發(fā)起節(jié)點到目的節(jié)點路由的反向路由。如果源-目的是單向通信鏈路，目的節(jié)點就需要發(fā)起到源節(jié)點的路由發(fā)現(xiàn)過程，同時將路由應(yīng)答報文捎帶在新的路由請求中。源節(jié)點接收到RREP后在路由緩存中存儲路由信息。按需驅(qū)動路由協(xié)議按需驅(qū)動路由協(xié)議22pDSR路由發(fā)現(xiàn)過程：路由應(yīng)答按需驅(qū)動路由協(xié)議按需驅(qū)動路由協(xié)議23pDSR（Dynamic Source Routing ） 路由維護(hù)：（1）點對點證實方式，又稱為逐跳證實方式。在點對點證實方式中，相

14、鄰節(jié)點間通過數(shù)據(jù)鏈路層的消息或者應(yīng)用層DSR軟件之間的消息證實機制，來檢測路由中各相鄰節(jié)點的可達(dá)性。（2）端到端證實方式。在這種工作機制中，結(jié)點以混雜模式運行，當(dāng)結(jié)點傳送報文給相鄰結(jié)點時，它可以偵聽到它的相鄰結(jié)點所傳送的報文，并以此來判斷對方是否還在傳送范圍內(nèi)。按需驅(qū)動路由協(xié)議按需驅(qū)動路由協(xié)議24pDSR（Dynamic Source Routing ） 路由維護(hù)：如果一個分組的發(fā)送次數(shù)已經(jīng)達(dá)到最大重傳限制，但節(jié)點仍未證實其下一跳節(jié)點已經(jīng)成功地接收到該分組，那么該節(jié)點認(rèn)為從自身到其下一跳節(jié)點間的鏈路中斷，節(jié)點將刪除其路由緩存表中包含該鏈路的路由記錄，并向該分組的源節(jié)點返回一個路由錯誤（ROUT

15、E ERROR）。源節(jié)點收到該路由錯誤后，查找其路由緩存表中是否存在能到達(dá)目的節(jié)點的其他路由，若存在這樣的路由，則源節(jié)點用此新路由來發(fā)送分組。否則，源節(jié)點將啟動新一輪路由發(fā)現(xiàn)過程。按需驅(qū)動路由協(xié)議按需驅(qū)動路由協(xié)議25pDSR（Dynamic Source Routing ） 路由維護(hù)優(yōu)化：（1）分組搶修。中間節(jié)點檢測到下一跳鏈路已經(jīng)中斷時，除了發(fā)送路由錯誤外，還應(yīng)進(jìn)行路由搶修，查找其路由緩存表中是否存在到達(dá)分組目的節(jié)點的替代路由。若存在，則按照該新路由進(jìn)行分組的轉(zhuǎn)發(fā)。在搶救一個分組時，為該分組維護(hù)一個計數(shù)器，用于記錄該分組已經(jīng)被搶救的次數(shù)，以便防止一個分組被無休止的搶救。按需驅(qū)動路由協(xié)議按需驅(qū)

16、動路由協(xié)議26pDSR（Dynamic Source Routing ） 路由維護(hù)優(yōu)化：（2）路由縮短。如下圖所示，圖中節(jié)點D偵聽到節(jié)點B轉(zhuǎn)發(fā)給節(jié)點C的一個數(shù)據(jù)分組，該分組隨后將被轉(zhuǎn)發(fā)給節(jié)點D和節(jié)點E。在這種情況下，節(jié)點D將回送一個無請求路由應(yīng)答給節(jié)點A。該無請求路由應(yīng)答給出一條更短的路由，由兩部分合并而成：第一部分是從源節(jié)點到被偵聽分組的發(fā)送節(jié)點為止的部分源路由；第二部分則是從回送無請求路由應(yīng)答節(jié)點開始到分組目的節(jié)點的一段緩存路由。按需驅(qū)動路由協(xié)議按需驅(qū)動路由協(xié)議27pDSR（Dynamic Source Routing ） 優(yōu)點：（1）僅在需要通信的節(jié)點間維護(hù)路由，減少了路由維護(hù)的開銷；（

17、2）采用了路由緩存技術(shù)，路由發(fā)現(xiàn)的過程中，會產(chǎn)生多條到達(dá)目的節(jié)點的路徑，能減少路由發(fā)現(xiàn)的代價；（3）支持非對稱傳輸信道模式。 不足：（1）采用源節(jié)點路由，每個路由報文的頭部都要攜帶路由信息，增加了報文長度；（2）用于路由發(fā)現(xiàn)的控制報文可能會涉及全網(wǎng)各節(jié)點，造成較大的耗費；（3）過時或錯誤的緩存路由會對網(wǎng)絡(luò)中其他節(jié)點產(chǎn)生影響?！芭K”緩存路由的污染傳播。按需驅(qū)動路由協(xié)議按需驅(qū)動路由協(xié)議28pAODV（Ad Hoc On Demand Distance Vector Routing ）按需距離矢量路由協(xié)議 按需路由，機制與DSR相仿。 通往目的節(jié)點路徑上的各節(jié)點均建立和維護(hù)路由表，路由報文頭部不再需

18、要攜帶完整路徑，減少了報文頭部路由信息對信道的占用，提高了系統(tǒng)效率。 本地存儲下一跳路由信息：RREQ獲得反向路由信息，RREP獲得正向路由信息。 路由條目中包含“目的節(jié)點序列號”，序列號越大路由越新越有效，進(jìn)行信息及時更新，避免環(huán)路。 局部連接拓?fù)涮綔y：在一定時間內(nèi)沒有和一跳鄰居通信（任意數(shù)據(jù)/控制包），發(fā)送Hello（節(jié)點發(fā)送Hello不增加自己的序號）。按需驅(qū)動路由協(xié)議按需驅(qū)動路由協(xié)議29pAODV（Ad Hoc On Demand Distance Vector Routing ）按需距離矢量路由協(xié)議 AODV只支持雙向鏈路路由。在路由請求消息的廣播過程中需要建立反向路由，供路由響應(yīng)報文尋路，網(wǎng)絡(luò)要滿足雙向傳輸信道的要求； 路