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

會(huì)計(jì)學(xué)1adhoc網(wǎng)絡(luò)的路由協(xié)議2提綱路由協(xié)議概述Adhoc網(wǎng)絡(luò)與Internet網(wǎng)絡(luò)路由設(shè)計(jì)的區(qū)別Adhoc網(wǎng)絡(luò)路由協(xié)議分類表驅(qū)動(dòng)（TableDriven）路由協(xié)議按需驅(qū)動(dòng)（On-demandDriven）路由協(xié)議混合式（Hybrid）路由協(xié)議典型路由協(xié)議DSR、AODVDSR路由仿真演示第1頁/共31頁3應(yīng)用層傳輸層網(wǎng)絡(luò)層數(shù)據(jù)鏈路層(MAC)物理層需要確定從起始源節(jié)點(diǎn)到最終目的節(jié)點(diǎn)（端到端）的有效路由需要解決相鄰節(jié)點(diǎn)間(點(diǎn)到點(diǎn))的信道接入問題231451168971014121315自組織網(wǎng)絡(luò)協(xié)議棧結(jié)構(gòu)第2頁/共31頁4路由協(xié)議概述路由協(xié)議：通信網(wǎng)絡(luò)中的一套將業(yè)務(wù)數(shù)據(jù)從源節(jié)點(diǎn)指引到目的節(jié)點(diǎn)的機(jī)制。路由設(shè)計(jì)目標(biāo)正確性、簡單性健壯性（robustness）、穩(wěn)定性公平性、最優(yōu)性路由協(xié)議構(gòu)成：路由生成（PathGeneration）路徑選擇（PathSelection）路徑維護(hù)（PathMaintenance）第3頁/共31頁5Adhoc網(wǎng)絡(luò)與互聯(lián)網(wǎng)路由設(shè)計(jì)的區(qū)別Adhoc網(wǎng)絡(luò)中節(jié)點(diǎn)既是終端又是路由器，參與分組轉(zhuǎn)發(fā)；因特網(wǎng)中終端和路由器的角色由不同節(jié)點(diǎn)擔(dān)任。由于應(yīng)用環(huán)境和功能的差異，二者在路由協(xié)議設(shè)計(jì)上存在諸多區(qū)別：Adhoc網(wǎng)絡(luò)中存在單向鏈路?；陔p向鏈路的傳統(tǒng)路由選擇算法在adhoc網(wǎng)絡(luò)中已不再適用。無線環(huán)境中可能存在很多“多余”鏈路。傳統(tǒng)的有線網(wǎng)絡(luò)中，任意兩個(gè)網(wǎng)絡(luò)之間通常只會(huì)配置一個(gè)或均勻配置少量的路由器。而無線網(wǎng)絡(luò)中由于節(jié)點(diǎn)的移動(dòng)性，某時(shí)刻源節(jié)點(diǎn)或轉(zhuǎn)發(fā)節(jié)點(diǎn)周圍可能會(huì)密集分布多個(gè)節(jié)點(diǎn)，這些節(jié)點(diǎn)均處于臨近節(jié)點(diǎn)的傳輸范圍內(nèi)，容易形成多條等效的轉(zhuǎn)發(fā)鏈路。這些鏈路的代價(jià)相同，可以認(rèn)為是多余的。第4頁/共31頁6Adhoc網(wǎng)絡(luò)與互聯(lián)網(wǎng)路由設(shè)計(jì)的區(qū)別Adhoc網(wǎng)絡(luò)與Internet網(wǎng)絡(luò)在路由協(xié)議設(shè)計(jì)上存在的區(qū)別：無線節(jié)點(diǎn)通常是能量受限的終端。無線網(wǎng)絡(luò)中的節(jié)點(diǎn)通常依靠電池提供能量，因此節(jié)能很大程度上決定了無線節(jié)點(diǎn)的使用壽命。傳統(tǒng)Internet網(wǎng)絡(luò)中的路由協(xié)議大多需要路由器間頻繁的信息交互，這對于有穩(wěn)定能量供應(yīng)的有線網(wǎng)絡(luò)而言可能無足輕重，而對于能量受限的無線節(jié)點(diǎn)而言卻是無法承受的。無線環(huán)境中動(dòng)態(tài)變化的網(wǎng)絡(luò)拓?fù)洹鹘y(tǒng)的路由協(xié)議是針對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相對穩(wěn)定的有線網(wǎng)絡(luò)而設(shè)計(jì)的，當(dāng)應(yīng)用于無線網(wǎng)絡(luò)中時(shí)，會(huì)出現(xiàn)大量的問題。收斂速度是衡量路由協(xié)議性能的重要指標(biāo)。由于無線網(wǎng)絡(luò)中節(jié)點(diǎn)移動(dòng)頻繁，需要交互更多的變化的拓?fù)湫畔?，路由協(xié)議的收斂相對較慢。第5頁/共31頁7Adhoc網(wǎng)絡(luò)路由協(xié)議的分類現(xiàn)有Adhoc網(wǎng)絡(luò)的路由協(xié)議根據(jù)發(fā)現(xiàn)路由的驅(qū)動(dòng)方式的不同可分為表驅(qū)動(dòng)（TableDriven）、按需驅(qū)動(dòng)（On-demandDriven）和混合式（Hybrid）路由協(xié)議三類。第6頁/共31頁8Adhoc網(wǎng)絡(luò)路由協(xié)議的分類表驅(qū)動(dòng)（TableDriven）路由協(xié)議又稱先驗(yàn)式路由協(xié)議，主要是沿用了傳統(tǒng)有線網(wǎng)絡(luò)中路由協(xié)議的基本思想，即節(jié)點(diǎn)通過查詢預(yù)先配置的路由表來實(shí)現(xiàn)分組的轉(zhuǎn)發(fā)。節(jié)點(diǎn)間周期性地交互各自的路由信息，每個(gè)節(jié)點(diǎn)試圖維護(hù)到網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)的路由信息。節(jié)點(diǎn)在檢測到周圍網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí)，會(huì)及時(shí)地發(fā)送路由更新，收到路由更新的節(jié)點(diǎn)將更新自己的路由表。表驅(qū)動(dòng)路由協(xié)議的時(shí)延較小，但路由協(xié)議的開銷較大。由于其先驗(yàn)性，每個(gè)節(jié)點(diǎn)都必須維護(hù)路由表，而通常網(wǎng)絡(luò)中只有少數(shù)節(jié)點(diǎn)承擔(dān)著數(shù)據(jù)分組的轉(zhuǎn)發(fā)任務(wù)，不會(huì)參與分組轉(zhuǎn)發(fā)的節(jié)點(diǎn)實(shí)際上并沒有維護(hù)路由表的必要，這樣就大大浪費(fèi)了寶貴的無線帶寬資源。第7頁/共31頁9Adhoc網(wǎng)絡(luò)路由協(xié)議的分類按需驅(qū)動(dòng)（On-demandDriven）路由協(xié)議又稱反應(yīng)式路由或被動(dòng)路由。節(jié)點(diǎn)無需實(shí)時(shí)維護(hù)整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息，其路由信息是按需建立的。當(dāng)節(jié)點(diǎn)有數(shù)據(jù)分組需要發(fā)送時(shí)，才嘗試發(fā)起路由發(fā)現(xiàn)過程。通常源節(jié)點(diǎn)采用洪泛（Flooding）的方式向鄰居節(jié)點(diǎn)廣播路由請求消息，目的節(jié)點(diǎn)收到該路由請求消息時(shí)，向源節(jié)點(diǎn)返回路由應(yīng)答，路由應(yīng)答消息中包含著從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的全路由信息。按需路由不需要節(jié)點(diǎn)周期性的交互各自的路由信息，節(jié)省了一定的帶寬資源，只需要參與轉(zhuǎn)發(fā)的節(jié)點(diǎn)維護(hù)部分網(wǎng)絡(luò)拓?fù)湫畔?，減少了內(nèi)存的占用。但是當(dāng)源節(jié)點(diǎn)沒有到達(dá)目的節(jié)點(diǎn)的路由時(shí)，要實(shí)時(shí)發(fā)起路由尋找過程，數(shù)據(jù)分組的傳輸有一定的延時(shí)，因而按需驅(qū)動(dòng)的路由方式不利于數(shù)據(jù)的實(shí)時(shí)傳輸。第8頁/共31頁10Adhoc網(wǎng)絡(luò)路由協(xié)議的分類混合式（Hybrid）路由協(xié)議很多具體的adhoc網(wǎng)絡(luò)場合中，單純的采用按需驅(qū)動(dòng)或表驅(qū)動(dòng)的路由方式并不能完全解決路由問題。于是，許多研究工作嘗試結(jié)合按需驅(qū)動(dòng)路由協(xié)議和表驅(qū)動(dòng)路由協(xié)議各自的優(yōu)點(diǎn)來設(shè)計(jì)混合式路由協(xié)議。然而，混合式路由協(xié)議的具體實(shí)現(xiàn)也面臨著很多困難，如具體表驅(qū)動(dòng)和按需驅(qū)動(dòng)路由協(xié)議的搭配方式等問題。第9頁/共31頁11DSR（DynamicSourceRouting）

基于源路由方式的按需路由協(xié)議。節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)分組時(shí)才進(jìn)行路由發(fā)現(xiàn)過程。發(fā)送節(jié)點(diǎn)在路由分組中包含了源-目的節(jié)點(diǎn)的完整路由信息，該路由信息由網(wǎng)絡(luò)中的若干節(jié)點(diǎn)地址組成，各個(gè)節(jié)點(diǎn)按照該路由信息來轉(zhuǎn)發(fā)分組。

按需驅(qū)動(dòng)路由協(xié)議第10頁/共31頁12DSR（DynamicSourceRouting）

節(jié)點(diǎn)不需要實(shí)時(shí)地維護(hù)網(wǎng)絡(luò)的拓?fù)湫畔?，那么在?jié)點(diǎn)需要發(fā)送數(shù)據(jù)時(shí)，如何獲知源-目的節(jié)點(diǎn)的路由？按需驅(qū)動(dòng)路由協(xié)議第11頁/共31頁13DSR（DynamicSourceRouting）路由發(fā)現(xiàn)（RouteDiscovery）和路由維護(hù)（RouteMaintenance）兩部分：路由發(fā)現(xiàn)：

-節(jié)點(diǎn)需要發(fā)送數(shù)據(jù)分組時(shí)才啟動(dòng)；-幫助源節(jié)點(diǎn)獲得到達(dá)目的節(jié)點(diǎn)的路由。路由維護(hù)-在源節(jié)點(diǎn)給目的節(jié)點(diǎn)發(fā)送數(shù)據(jù)時(shí)監(jiān)測當(dāng)前路由的可用情況；-當(dāng)網(wǎng)絡(luò)拓?fù)渥兓瘜?dǎo)致路由故障時(shí)，切換到另一條路由或者重新發(fā)起路由發(fā)現(xiàn)過程。按需驅(qū)動(dòng)路由協(xié)議第12頁/共31頁14DSR（DynamicSourceRouting）路由發(fā)現(xiàn)：（1）當(dāng)一個(gè)節(jié)點(diǎn)要發(fā)送分組給某一目的節(jié)點(diǎn)時(shí)，它會(huì)首先查看自己的路由緩存中是否已有現(xiàn)成的路由信息可以使用。如果存在一條到達(dá)目的節(jié)點(diǎn)的路由，并且其生存期沒有到期，則直接使用此路由發(fā)送分組；（2）如果路由緩存中沒有通向目的節(jié)點(diǎn)的路由,則啟動(dòng)路由發(fā)現(xiàn)(routeDiscovery)過程。路由發(fā)現(xiàn)過程使用洪泛路由（floodingrouting）技術(shù)。按需驅(qū)動(dòng)路由協(xié)議第13頁/共31頁15DSR路由發(fā)現(xiàn)過程路由發(fā)現(xiàn)的基本操作（1）源節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播路由請求（RREQ）報(bào)文RREQ中包含以下信息：①源節(jié)點(diǎn)地址；②目的節(jié)點(diǎn)地址；③路由記錄（按順序累積記錄此路由請求報(bào)文所經(jīng)過的節(jié)點(diǎn)的地址）；④請求ID（由源節(jié)點(diǎn)自己產(chǎn)生的序號，同一個(gè)節(jié)點(diǎn)所發(fā)送的路由請求報(bào)文中的請求標(biāo)識均不同）。一組<源地址，請求ID>可以唯一確定一個(gè)路由請求報(bào)文。按需驅(qū)動(dòng)路由協(xié)議第14頁/共31頁16DSR路由發(fā)現(xiàn)過程路由發(fā)現(xiàn)的基本操作（2）中間節(jié)點(diǎn)收到路由請求報(bào)文后，需要進(jìn)行請求報(bào)文檢測。①中間節(jié)點(diǎn)收到來自同一個(gè)源節(jié)點(diǎn)，并且請求ID相同的路由請求報(bào)文，則直接將該報(bào)文丟棄。按需驅(qū)動(dòng)路由協(xié)議第15頁/共31頁17DSR路由發(fā)現(xiàn)過程路由發(fā)現(xiàn)的基本操作（2）中間節(jié)點(diǎn)收到路由請求報(bào)文后，需要進(jìn)行請求報(bào)文檢測。②中間節(jié)點(diǎn)收到路由請求報(bào)文中的路由記錄已經(jīng)包含本中間節(jié)點(diǎn)，則直接將該報(bào)文丟棄。③中間節(jié)點(diǎn)的緩存中已經(jīng)有到達(dá)目的節(jié)點(diǎn)的路由，直接向源節(jié)點(diǎn)發(fā)送路由應(yīng)答報(bào)文進(jìn)行應(yīng)答。按需驅(qū)動(dòng)路由協(xié)議第16頁/共31頁18DSR路由發(fā)現(xiàn)過程路由發(fā)現(xiàn)的基本操作（2）中間節(jié)點(diǎn)收到路由請求報(bào)文后，需要進(jìn)行請求報(bào)文檢測。④若路由請求報(bào)文是未處理過的，中間節(jié)點(diǎn)則：-將自己的地址附在路由記錄中；-將該路由請求報(bào)文作為本地廣播分組發(fā)送給鄰居節(jié)點(diǎn)。按需驅(qū)動(dòng)路由協(xié)議第17頁/共31頁19DSR路由發(fā)現(xiàn)過程路由發(fā)現(xiàn)的基本操作（3）如果接收節(jié)點(diǎn)就是目的節(jié)點(diǎn)，這時(shí)路由記錄字段中記錄的節(jié)點(diǎn)地址序列，就構(gòu)成了從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由信息，把此路由信息加入到路由應(yīng)答報(bào)文中，并將此報(bào)文回送給源節(jié)點(diǎn)。按需驅(qū)動(dòng)路由協(xié)議第18頁/共31頁20DSR路由發(fā)現(xiàn)過程按需驅(qū)動(dòng)路由協(xié)議第19頁/共31頁21DSR路由發(fā)現(xiàn)過程：路由應(yīng)答路由應(yīng)答的基本操作目的節(jié)點(diǎn)接收到路由請求后，把路由信息加入到路由應(yīng)答報(bào)文（RREP）中，并將此報(bào)文回送給源節(jié)點(diǎn)。如果目的節(jié)點(diǎn)路由緩存中有到達(dá)發(fā)起節(jié)點(diǎn)的路由，此時(shí)目的節(jié)點(diǎn)可以直接使用該路由回送路由應(yīng)答。如果目的節(jié)點(diǎn)路由緩存中沒有到達(dá)發(fā)起節(jié)點(diǎn)的路由，此時(shí)需要考慮節(jié)點(diǎn)通信鏈路的方向性問題。①如果源-目的是雙向通信鏈路，此時(shí)目的節(jié)點(diǎn)到發(fā)起節(jié)點(diǎn)的路由即為發(fā)起節(jié)點(diǎn)到目的節(jié)點(diǎn)路由的反向路由。②如果源-目的是單向通信鏈路，目的節(jié)點(diǎn)就需要發(fā)起到源節(jié)點(diǎn)的路由發(fā)現(xiàn)過程，同時(shí)將路由應(yīng)答報(bào)文捎帶在新的路由請求中。源節(jié)點(diǎn)接收到RREP后在路由緩存中存儲路由信息。按需驅(qū)動(dòng)路由協(xié)議第20頁/共31頁22DSR路由發(fā)現(xiàn)過程：路由應(yīng)答按需驅(qū)動(dòng)路由協(xié)議第21頁/共31頁23DSR（DynamicSourceRouting）路由維護(hù)：（1）點(diǎn)對點(diǎn)證實(shí)方式，又稱為逐跳證實(shí)方式。在點(diǎn)對點(diǎn)證實(shí)方式中，相鄰節(jié)點(diǎn)間通過數(shù)據(jù)鏈路層的消息或者應(yīng)用層DSR軟件之間的消息證實(shí)機(jī)制，來檢測路由中各相鄰節(jié)點(diǎn)的可達(dá)性。（2）端到端證實(shí)方式。在這種工作機(jī)制中，結(jié)點(diǎn)以混雜模式運(yùn)行，當(dāng)結(jié)點(diǎn)傳送報(bào)文給相鄰結(jié)點(diǎn)時(shí)，它可以偵聽到它的相鄰結(jié)點(diǎn)所傳送的報(bào)文，并以此來判斷對方是否還在傳送范圍內(nèi)。按需驅(qū)動(dòng)路由協(xié)議第22頁/共31頁24DSR（DynamicSourceRouting）路由維護(hù)：如果一個(gè)分組的發(fā)送次數(shù)已經(jīng)達(dá)到最大重傳限制，但節(jié)點(diǎn)仍未證實(shí)其下一跳節(jié)點(diǎn)已經(jīng)成功地接收到該分組，那么該節(jié)點(diǎn)認(rèn)為從自身到其下一跳節(jié)點(diǎn)間的鏈路中斷，節(jié)點(diǎn)將刪除其路由緩存表中包含該鏈路的路由記錄，并向該分組的源節(jié)點(diǎn)返回一個(gè)路由錯(cuò)誤（ROUTEERROR）。源節(jié)點(diǎn)收到該路由錯(cuò)誤后，查找其路由緩存表中是否存在能到達(dá)目的節(jié)點(diǎn)的其他路由，若存在這樣的路由，則源節(jié)點(diǎn)用此新路由來發(fā)送分組。否則，源節(jié)點(diǎn)將啟動(dòng)新一輪路由發(fā)現(xiàn)過程。按需驅(qū)動(dòng)路由協(xié)議第23頁/共31頁25DSR（DynamicSourceRouting）路由維護(hù)優(yōu)化：（1）分組搶修。中間節(jié)點(diǎn)檢測到下一跳鏈路已經(jīng)中斷時(shí)，除了發(fā)送路由錯(cuò)誤外，還應(yīng)進(jìn)行路由搶修，查找其路由緩存表中是否存在到達(dá)分組目的節(jié)點(diǎn)的替代路由。若存在，則按照該新路由進(jìn)行分組的轉(zhuǎn)發(fā)。在搶救一個(gè)分組時(shí)，為該分組維護(hù)一個(gè)計(jì)數(shù)器，用于記錄該分組已經(jīng)被搶救的次數(shù)，以便防止一個(gè)分組被無休止的搶救。按需驅(qū)動(dòng)路由協(xié)議第24頁/共31頁26DSR（DynamicSourceRouting）路由維護(hù)優(yōu)化：（2）路由縮短。如下圖所示，圖中節(jié)點(diǎn)D偵聽到節(jié)點(diǎn)B轉(zhuǎn)發(fā)給節(jié)點(diǎn)C的一個(gè)數(shù)據(jù)分組，該分組隨后將被轉(zhuǎn)發(fā)給節(jié)點(diǎn)D和節(jié)點(diǎn)E。在這種情況下，節(jié)點(diǎn)D將回送一個(gè)無請求路由應(yīng)答給節(jié)點(diǎn)A。該無請求路由應(yīng)答給出一條更短的路由，由兩部分合并而成：第一部分是從源節(jié)點(diǎn)到被偵聽分組的發(fā)送節(jié)點(diǎn)為止的部分源路由；第二部分則是從回送無請求路由應(yīng)答節(jié)點(diǎn)開始到分組目的節(jié)點(diǎn)的一段緩存路由。按需驅(qū)動(dòng)路由協(xié)議第25頁/共31頁27DSR（DynamicSourceRouting）優(yōu)點(diǎn)：（1）僅在需要通信的節(jié)點(diǎn)間維護(hù)路由，減少了路由維護(hù)的開銷；（2）采用了路由緩存技術(shù)，路由發(fā)現(xiàn)的過程中，會(huì)產(chǎn)生多條到達(dá)目的節(jié)點(diǎn)的路徑，能減少路由發(fā)現(xiàn)的代價(jià)；（3）支持非對稱傳輸信道模式。不足：（1）采用源節(jié)點(diǎn)路由，每個(gè)路由報(bào)文的頭部都要攜帶路由信息，增加了報(bào)文長度；（2）用于路由發(fā)現(xiàn)的控制報(bào)文可能會(huì)涉及全網(wǎng)各節(jié)點(diǎn)，造成較大的耗費(fèi)；（3）過時(shí)或錯(cuò)誤的緩存路由會(huì)對網(wǎng)絡(luò)中其他節(jié)點(diǎn)產(chǎn)生影響?！芭K”緩存路由的污染傳播。按需驅(qū)動(dòng)路由協(xié)議第26頁/共31頁28AODV（AdHocOnDemandDistanceVectorRouting）按需距離矢量路由協(xié)議按需路由，機(jī)制與DSR相仿。通往目的節(jié)點(diǎn)路徑上的各節(jié)點(diǎn)均建立和維護(hù)路由表，路由報(bào)文頭部不再需要攜帶完整路徑，減少了報(bào)文頭部路由信息對信道的占用，提高了系統(tǒng)效率。本地存儲下一跳路由信息：RREQ獲得反