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

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

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

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

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

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