AD HOC 路由協(xié)議-20101020101034478完整版

AD-HOC路由協(xié)議在AdHoc網(wǎng)絡中，隨著節(jié)點移動，網(wǎng)絡拓撲結構在不斷變化。如何迅速準確地選擇到達目的節(jié)點的路由（即網(wǎng)絡的路由選擇問題），是AdHoc網(wǎng)絡的一個重要和核心的問題。1.AdHoc網(wǎng)絡與傳統(tǒng)移動通信系統(tǒng)在路由問題上的區(qū)別1．AdHoc網(wǎng)絡與蜂窩移動通信系統(tǒng)的區(qū)別蜂窩移動通信系統(tǒng)網(wǎng)絡結構比較穩(wěn)定。而在AdHoc網(wǎng)絡環(huán)境下，節(jié)點的頻繁隨意移動，造成網(wǎng)絡拓撲結構發(fā)生經(jīng)常性的變化，使得路由表項經(jīng)常改變。2．AdHoc網(wǎng)絡與無線局域網(wǎng)的區(qū)別無線局域網(wǎng)是一個單跳的網(wǎng)絡。而AdHoc網(wǎng)絡則是一個多跳的網(wǎng)絡。2.傳統(tǒng)Internet網(wǎng)絡路由協(xié)議目前在Internet中常用的內部網(wǎng)關路由協(xié)議主要有兩種。基于距離矢量的路由協(xié)議（如RIP協(xié)議）基于鏈路狀態(tài)的路由協(xié)議（如OSPF協(xié)議）。這兩類協(xié)議都是針對固定網(wǎng)絡而設計的，它們都需要周期性地交換信息維護網(wǎng)絡正確的路由表或網(wǎng)絡拓撲結構圖。AdHoc網(wǎng)絡帶寬有限、拓撲變化頻繁，這些傳統(tǒng)的用于固定網(wǎng)絡的路由協(xié)議不適用于AdHoc網(wǎng)絡，主要體現(xiàn)在以下幾個方面。（1）動態(tài)變化的網(wǎng)絡拓撲結構。（2）周期性地廣播拓撲信息會占用大量的無線信道資源，耗費電池能源，將會嚴重降低系統(tǒng)的性能。尤其是在拓撲變化頻繁的AdHoc網(wǎng)絡環(huán)境中，可能當路由算法還未收斂時，網(wǎng)絡的拓撲結構就又發(fā)生了變化。（3）單向的無線傳輸信道。3.AdHoc網(wǎng)絡路由協(xié)議的分類根據(jù)發(fā)現(xiàn)路由的驅動模式的不同，可以將這些路由協(xié)議分為表驅動路由協(xié)議（TableDrivenProtocols）在表驅動路由協(xié)議中，每個節(jié)點需要實時地維護路由信息，當網(wǎng)絡規(guī)模較大、拓撲變化較快的環(huán)境中，大量的拓撲更新信息會占用過多的信道資源，使得系統(tǒng)效率下降。按需路由協(xié)議（Source-InitiatedOn-DemandProtocols）按需路由協(xié)議的路由發(fā)現(xiàn)過程根據(jù)網(wǎng)絡拓撲結構的差異，又可以將它們分為平面結構的路由協(xié)議（FlatProtocols）分簇路由協(xié)議（ClusteredProtocols）。AdHoc網(wǎng)絡拓撲結構在平面結構的路由協(xié)議中網(wǎng)絡結構簡單網(wǎng)絡中的節(jié)點都處于平等的地位它們所具有的功能完全相同各節(jié)點共同協(xié)作完成節(jié)點間的通信。隨著網(wǎng)絡規(guī)模的逐步擴大，網(wǎng)絡中節(jié)點個數(shù)不斷增加，每個節(jié)點要想維護整個網(wǎng)絡的拓撲信息或選擇到遠端節(jié)點合適的路由將十分困難，由此產(chǎn)生了分簇式路由協(xié)議。在分簇式路由協(xié)議中，網(wǎng)絡節(jié)點按照不同的分簇算法分成相應的簇（或群）。簇中的每個節(jié)點完成的功能是不相同的簇首節(jié)點維護和管理本簇范圍內節(jié)點，負責簇內節(jié)點的通信，同時為簇間節(jié)點通信提供合適的路由信息；網(wǎng)關節(jié)點負責與相鄰簇節(jié)點通信。分簇式路由協(xié)議中分層結構圖4.評價AdHoc網(wǎng)絡路由協(xié)議的標準評價一種AdHoc網(wǎng)絡路由協(xié)議的性能主要包括以下幾個方面的指標端到端的數(shù)據(jù)吞吐量和時延：通過報文傳輸質量的好壞來衡量路由協(xié)議性能的好壞。路由請求的時間：即統(tǒng)計節(jié)點有數(shù)據(jù)需要發(fā)送到數(shù)據(jù)成功發(fā)送的時間，這主要用于按需路由方式的AdHoc網(wǎng)絡路由協(xié)議的性能評價；路由協(xié)議的效率：即完成路由任務的控制信息與用戶數(shù)據(jù)信息的比率。尤其是在控制信息與數(shù)據(jù)信息共享同一信道的情況下，該性能將直接影響到整個系統(tǒng)效率的高低。需要注意的是：即使是同一個路由協(xié)議，在不同的環(huán)境中，其性能好壞可能有很大的差異AdHoc網(wǎng)絡組網(wǎng)環(huán)境主要涉及的內容有：網(wǎng)絡的規(guī)模大小，即網(wǎng)絡中節(jié)點個數(shù)的多少；網(wǎng)絡的拓撲結構變化速度；節(jié)點的移動速度；信道的傳輸帶寬和單向信道的比率“休眠”節(jié)點的比率等。因此，在分析比較各種AdHoc網(wǎng)絡路由協(xié)議性能時,要注意環(huán)境因素對各路由協(xié)議的影響。5.幾種典型的AdHoc網(wǎng)絡路由協(xié)議DSDV（Destination-SequencedDistance-VectorRouting）路由協(xié)議DSDV協(xié)議是基于傳統(tǒng)Bellman-Ford路由選擇算法經(jīng)改良而發(fā)展出來的，是一個基于表驅動的路由協(xié)議，它的最大優(yōu)點是解決了傳統(tǒng)距離矢量路由協(xié)議中的無窮環(huán)路問題。在DSDV路由協(xié)議中，每個節(jié)點都維護一張路由表，該路由表表項包括目的節(jié)點跳數(shù)下一跳節(jié)點目的節(jié)點序號每個節(jié)點周期性地與鄰節(jié)點交換路由信息，或者根據(jù)路由表的改變來觸發(fā)路由更新。路由表更新有兩種方式：一種是全部更新（Fulldump），即拓撲更新消息中將包括整個路由表，主要應用于網(wǎng)絡變化較快的情況；另一種方式是部分更新（Incrementalupdate），更新消息中僅包含變化的路由部分，通常適用于網(wǎng)絡變化較慢的情況。在DSDV中只使用序列號最高的路由，如果兩個路由具有相同的序列號，那么將選擇最優(yōu)的路由（如跳數(shù)最短）。DSDV優(yōu)缺點DSDV路由協(xié)議中，節(jié)點維護著整個網(wǎng)絡的路由信息，這樣在有數(shù)據(jù)報文需要發(fā)送時，可以立即進行傳送，因而適用于一些對實時性要求較高的業(yè)務和網(wǎng)絡環(huán)境。但是在拓撲結構變化頻繁的無線網(wǎng)絡環(huán)境中，DSDV可能存在一定的問題，一是節(jié)點維護準確路由信息的代價高，要頻繁地交換拓撲更新信息；二是有的時候可能剛得到的路由信息隨即又失效了。因此，DSDV協(xié)議主要用于網(wǎng)絡規(guī)模不是很大，網(wǎng)絡拓撲變化相對不是很頻繁的網(wǎng)絡環(huán)境，而在拓撲變化頻繁的網(wǎng)絡中必須采用其他的方法。DSR（DynamicSourceRouting）路由協(xié)議DSR協(xié)議是一種基于源路由方式的按需路由協(xié)議。在DSR協(xié)議中，當發(fā)送者發(fā)送報文時，在數(shù)據(jù)報文頭部攜帶到達目的節(jié)點的路由信息，該路由信息由網(wǎng)絡中的若干節(jié)點地址組成，源節(jié)點的數(shù)據(jù)報文就通過這些節(jié)點的中繼轉發(fā)到達目的節(jié)點。與基于表驅動方式的路由協(xié)議不同的是，在DSR協(xié)議中，節(jié)點不需要實時維護網(wǎng)絡的拓撲信息，因此在節(jié)點需要發(fā)送數(shù)據(jù)時，如何能夠知道到達目的節(jié)點的路由是DSR路由協(xié)議需要解決的核心問題。DSR路由協(xié)議主要由路由發(fā)現(xiàn)和路由維護兩部分組成。路由發(fā)現(xiàn)過程主要用于幫助源節(jié)點獲得到達目的節(jié)點的路由。DSR協(xié)議通過路由維護過程來監(jiān)測當前路由的可用情況，當監(jiān)測到路由故障時，將調用新的一輪路由發(fā)現(xiàn)過程。如路由中的節(jié)點由于移動、關機等原因無法保證到達目的節(jié)點時，當前的路由就不再有效了。同時為了提高系統(tǒng)性能，在DSR協(xié)議中，還引入了一系列的優(yōu)化技術，如路由緩沖（RouteCache）等。下面分別介紹這三部分內容。1．路由發(fā)現(xiàn)節(jié)點通過路由發(fā)現(xiàn)過程獲得到達其他節(jié)點的路由。源節(jié)點首先向其鄰節(jié)點廣播“路由請求”（RouteRequest）報文。報文中包括“目的節(jié)點地址”、“路由記錄”以及“請求ID”等字段。其中“路由記錄”字段用于記錄從源節(jié)點到目的節(jié)點路由中的中間節(jié)點地址，當路由請求報文到達目的節(jié)點時，該字段中的所有節(jié)點地址即構成了從源節(jié)點到目的節(jié)點的路由?！罢埱驣D”字段由源節(jié)點管理分配中間節(jié)點維護<源節(jié)點地址，請求ID>序列對列表，<源節(jié)點地址，請求ID>序列用于惟一標識一個路由請求報文，防止收到重復的路由請求。中間節(jié)點在收到源節(jié)點的路由請求報文后，按照以下步驟處理報文：（1）如果路由請求報文的<源節(jié)點地址，請求ID>存在于本節(jié)點的序列對列表中，表明此請求報文已經(jīng)收到過，節(jié)點不用處理該請求；否則轉步驟（2）；（2）如果節(jié)點的地址已在路由記錄字段中存在，節(jié)點不用處理該請求；否則轉步驟3；（3）如果請求報文的目的節(jié)點就是本節(jié)點，則路由記錄節(jié)點中的節(jié)點地址序列構成了從源節(jié)點到目的節(jié)點的路由。節(jié)點向源節(jié)點發(fā)送“路由響應”報文，同時將該路由拷貝到“路由響應”報文中；否則轉步驟（4）；4）該節(jié)點是中間節(jié)點。將節(jié)點地址附在報文的“路由記錄”字段后，同時向鄰節(jié)廣播該路由請求。通過這種方法，路由請求報文將最終到達目的節(jié)點。如下圖所示為節(jié)點A到節(jié)點D的路由請求過程。虛線箭頭代表路由請求消息發(fā)送，括號中的內容代表消息中的路由記錄。DSR路由請求過程幾個注意的問題：（1）由于節(jié)點B已經(jīng)收到節(jié)點A的路由請求，因此不再處理節(jié)點F的路由請求消息；（2）節(jié)點D可能會同時收到節(jié)點C和E的路由請求消息，造成消息碰撞，反而收不到正確的路由請求，因此在AdHoc網(wǎng)絡中，廣播并非完全可靠?？梢圆捎靡欢ǖ牟呗詠肀苊猓绻?jié)點隨機延時發(fā)送，或者節(jié)點間采用證實機制等。目的節(jié)點根據(jù)收到的源節(jié)點路由請求報文回送“路由響應”報文。目的節(jié)點在將“路由響應”報文轉發(fā)到源節(jié)點時，需要考慮這樣幾種情況：（1）目的節(jié)點有到達源節(jié)點的路由。此時目的節(jié)點可以直接使用該路由回送響應報文；（2）如果目的節(jié)點沒有到源節(jié)點的路由，此時需要考慮節(jié)點通信信道問題：①如果網(wǎng)絡中所有節(jié)點間的通信信道是對稱的，此時目的節(jié)點到源節(jié)點的路由即為源節(jié)點到目的節(jié)點的反向路由；②如果信道是非對稱的，目的節(jié)點就需要發(fā)起到源節(jié)點的路由請求過程，同時將路由響應報文捎帶在新的路由請求中。如下圖所示為DSR的路由響應過程。假設信道是雙向信道，節(jié)點D根據(jù)最短路由原則選擇了路由（A-B-C-D）作為最終路由，將此信息通過反向路由發(fā)送至源節(jié)點A。DSR路由響應過程如果信道是單向呢？2．路由維護傳統(tǒng)的路由協(xié)議中通過周期性廣播路由更新消息將路由發(fā)現(xiàn)和路由維護過程合二為一。而在DSR協(xié)議中，由于沒有這種周期性的廣播，節(jié)點必須通過路由維護過程檢測路由的可用性。按照路由維護的不同檢測方法，可以將路由維護分為以下兩種：（1）點到點證實機制，又稱為逐跳證實機制。即相鄰節(jié)點間通過數(shù)據(jù)鏈路層的消息證實或者高層應用層之間的消息證實機制，來檢測路由中各鄰節(jié)點的可達性。當發(fā)現(xiàn)節(jié)點間的傳輸故障，即路由不再有效時，向上級節(jié)點發(fā)送“路由差錯”報文，收到路由差錯報文的節(jié)點根據(jù)此信息將該路由從本節(jié)點的路由緩沖區(qū)中刪除。（2）端到端證實機制。在有些應用中要求端到端節(jié)點間的證實，通過端到端的證實機制可以用來檢測整個路由的有效性。3．路由緩沖技術優(yōu)化策略在DSR協(xié)議中，為了提高系統(tǒng)效率，協(xié)議中采用了路由緩沖優(yōu)化策略。由于無線廣播信道的特點，節(jié)點可以處于“混合監(jiān)聽”狀態(tài)，即可以聽到相鄰節(jié)點發(fā)出的所有報文，包括路由請求、路由響應等。這些報文中攜帶了網(wǎng)絡的一些路由信息，節(jié)點通過緩存這些路由信息，可以盡量減少每次發(fā)送新報文時啟動的路由發(fā)現(xiàn)

過程，以提高系統(tǒng)的效率。如下圖所示，節(jié)點A通過發(fā)起目的節(jié)點為D的路由請求過程，獲得路由A-B-C-D，同時節(jié)點A也獲得了到達該路由中所有節(jié)點（如節(jié)點B、C）的路由，節(jié)點B等中間節(jié)點也獲得了到達節(jié)點D的路由。DSR路由緩沖技術同時，中間節(jié)點在收到源節(jié)點的路由請求時，如果本節(jié)點路由緩沖區(qū)中有到目的節(jié)點的路由，可以直接回復路由響應消息。如節(jié)點F在發(fā)起到節(jié)點D的路由請求時，當報文到達節(jié)點B時，節(jié)點B中有緩沖路由B-C-D，此時節(jié)點B可以直接回復路由響應（F-B-C-D）。這樣一方面加快了路由請求的響應，同時也減少了路由請求消息的廣播。盡管路由緩沖技術能夠在一定程度上提高系統(tǒng)的效率，但同時一些錯誤或過期的路由緩沖信息（如由于某些節(jié)點的移動使得路由失效）也會對網(wǎng)絡帶來負面影響，這些錯誤的路由信息可能會影響和感染其他節(jié)點。對此，可以采用一定的策略來減少其影響。如為緩沖路由設定有效期，超過有效期的路由將被認為無效，將其從緩沖區(qū)中刪除。4．DSR協(xié)議的優(yōu)缺點DSR協(xié)議具有以下幾個優(yōu)點：（1）僅在需要通信的節(jié)點間維護路由，減少了路由維護的代價；（2）路由緩沖技術可進一步減少路由發(fā)現(xiàn)的代價；（3）由于采用了路由緩沖技術，因此在一次路由的發(fā)現(xiàn)過程中，會產(chǎn)生多種到達目的節(jié)點的路徑；（4）支持非對稱傳輸信道模式。DSR協(xié)議存在一些問題和不足：（1）由于采用源節(jié)點路由，每個數(shù)據(jù)報文的頭部都要攜帶路由信息，增加了報文長度；（2）用于路由發(fā)現(xiàn)的控制報文可能會波及全網(wǎng)各節(jié)點，造成一定的耗費；一種可行的優(yōu)化方法是控制路由發(fā)現(xiàn)報文的傳輸距離（如跳數(shù)），如果本輪路由發(fā)現(xiàn)失敗，后續(xù)的路由發(fā)現(xiàn)過程中再加大傳輸距離；（3）“路由響應風暴”（RouteReplyStorm）問題。由于采用路由緩沖技術，中間節(jié)點根據(jù)自己的緩沖路由，對路由請求直接應答，源節(jié)點會同時收到多個路由響應，造成路由響應信息之間的競爭；（4）“錯誤”緩沖路由對其他節(jié)點的影響。如果中間節(jié)點的路由緩沖記錄已經(jīng)過時，當該節(jié)點根據(jù)緩沖路由回復路由請求時，其他監(jiān)聽到此“錯誤”路由的節(jié)點會更改自己的緩沖路由記錄，造成“錯誤”緩沖路由的污染傳播。LAR（Locationaidedrouting）路由協(xié)議在DSR中，用于路由發(fā)現(xiàn)的控制報文可能會波及全網(wǎng)各節(jié)點，造成一定的耗費。為了減少耗費，有些路由協(xié)議采用一定的策略來減少路由發(fā)現(xiàn)報文的廣播。LAR協(xié)議就是利用位置信息來減少路由發(fā)現(xiàn)的廣播。這些物理的位置信息可以通過GPS系統(tǒng)獲得。兩個重要的概念——“預期區(qū)域”和“請求區(qū)域”。預期區(qū)域（ExpectedZone）和請求區(qū)域（RequestZone）假設當前時間為t1，源節(jié)點S請求到目的節(jié)點D的路由。源節(jié)點S知道在t0歷史時刻（t0<t1）時目的節(jié)點D的位置為X。（1）預期區(qū)域：在t1時刻，節(jié)點D可能存在區(qū)域Y，如下圖中圓形陰影部分所示。源節(jié)點S通過在t0時刻目的節(jié)點D的位置和平均移動速率V來判定節(jié)點D的預期區(qū)域Y。其中，r是預期區(qū)域的半徑，r=(t1-t0)×V。預期區(qū)域Y就是以X為圓心，以r為半徑的圓形區(qū)域。（2）請求區(qū)域：請求區(qū)域主要用于限定源節(jié)點洪泛其路由請求消息的范圍，它包含源節(jié)點S和“預期區(qū)域”的區(qū)域，如下圖中的矩形框部分所示。2．LAR協(xié)議的基本思路LAR協(xié)議的基本思路是通過請求區(qū)域來限定路由請求報文的洪泛范圍。在路由請求報文頭部攜帶請求區(qū)域信息，網(wǎng)絡中節(jié)點都知道自己當前的物理位置。當收到鄰節(jié)點的路由請求報文時，首先判斷自己當前是否處在請求區(qū)域范圍中，如果不在請求范圍，則丟棄該路由請求報文。這樣就限定了路由請求報文的洪泛范圍，使得路由請求報文朝著正確的方向傳播。如下圖所示，節(jié)點A在收到節(jié)點S的路由請求報文時，由于它不在請求區(qū)域內，因此不再轉發(fā)該路由請求。需要注意的是，在某些情況下，僅僅依靠請求區(qū)域中的節(jié)點可能無法找到到達目的節(jié)點的路由。如下圖所示，節(jié)點S和節(jié)點B之間無法直接通信，必須通過節(jié)點A轉接，而節(jié)點A又不在請求區(qū)域中，因此節(jié)點S在一段時間后收不到路由響應報文時，必須擴大請求區(qū)域（如圖中的虛線矩形框所示），重新發(fā)起新的路由請求。在極端情況下，請求區(qū)域可能會包含整個網(wǎng)絡。LAR協(xié)議中擴大的請求區(qū)域LAR協(xié)議中的其他部分和DSR協(xié)議類似。與DSR協(xié)議相比，LAR協(xié)議利用位置信息在一定程度上減少了路由請求報文的洪泛。但是，考慮到一些特殊的情況，在LAR中路由請求可能需要多次。這樣，一方面延長了路由發(fā)現(xiàn)的時間，同時也增加了路由請求報文的發(fā)送次數(shù)，在某些極端情況下（如請求區(qū)域擴大至整個網(wǎng)絡），其性能可能還不如DSR協(xié)議，因此在LAR協(xié)議中，需要折衷考慮路由發(fā)現(xiàn)時延和路由請求消息的耗費問題。3．LAR協(xié)議的幾種變化和更新在LAR協(xié)議中，針對不同的環(huán)境，采用了一些技術更新，如自適應請求區(qū)域（AdaptiveRequestZone）、基于距離的轉發(fā)策略等。1）自適應請求區(qū)域：在傳統(tǒng)的LAR協(xié)議中，請求區(qū)域由源節(jié)點確定，在路由請求的過程中請求區(qū)域大小不變。而在自適應請求區(qū)域方式中，每個中間節(jié)點在收到路由請求報文時，根據(jù)自己的物理位置和目的節(jié)點的位置、移動速度等信息，重新計算請求區(qū)域，在轉發(fā)的路由請求報文頭部攜帶自己更新的請求區(qū)域。LAR協(xié)議中的自適應請求區(qū)域如下圖所示，實線矩形區(qū)域為源節(jié)點S的請求區(qū)域，虛線矩形區(qū)域為節(jié)點B的請求區(qū)域。相對于源節(jié)點，節(jié)點B更接近目的節(jié)點，其請求區(qū)域也更小。因此，通過更新請求區(qū)域，可以進一步縮小路由請求報文的洪泛范圍，使得路由請求報文朝著更加準確的方向傳播。（2）基于距離的轉發(fā)策略：傳統(tǒng)的LAR協(xié)議中，節(jié)點是否轉發(fā)路由請求報文完全取決于自己的物理位置是否在請求區(qū)域中。在基于距離的轉發(fā)策略中，則是通過比較本節(jié)點與目的節(jié)點間的距離來決定是否轉發(fā)路由請求報文。DISTi表示節(jié)點與目的節(jié)點之間的距離，（Xd,Yd）表示目的節(jié)點D在t0時刻的位置坐標，如下圖所示。節(jié)點I在向鄰節(jié)點轉發(fā)路由請求報文時，在報文頭部攜帶目的節(jié)點的坐標（Xd,Yd）以及到目的節(jié)點的距離DISTi等信息。節(jié)點J在收到上游節(jié)點I的路由請求報文時，根據(jù)目的節(jié)點的坐標計算本節(jié)點到目的節(jié)點的距離DISTj，并通過比較DISTi的大小來判斷是否應轉發(fā)該路由請求消息。如果DISTi＋δ≥DISTj（δ≥0），即節(jié)點J至多比節(jié)點I距離目的節(jié)點遠δ，節(jié)點J轉發(fā)該路由請求報文，同時用DISTj更新請求報文頭部的距離字段DISTi。當δ=0時，表示節(jié)點J比節(jié)點I更靠近目的節(jié)點。引入δ變量主要是針對在某些特殊情況下，如上圖中的節(jié)點A，需要采用局部的迂回來尋找路由（類似前面提到的擴展請求區(qū)域）。如果DISTi＋δ<DISTj（δ≥0），節(jié)點J丟棄該路由請求報文。（3）位置信息的獲得和更新：節(jié)點的位置信息以及速率等信息是LAR協(xié)議中的重要因素。節(jié)點在發(fā)起路由請求的過程中，需要知道目的節(jié)點的位置和移動速率，這些信息可以通過自己發(fā)起的或從網(wǎng)絡中監(jiān)聽到的路由請求以及路由響應等消息中獲得，位置信息隨著時間的變化實時更新，為以后的路由發(fā)現(xiàn)過程作準備。節(jié)點也可以在發(fā)送的任何消息中攜帶自己的位置信息節(jié)點也可以主動分發(fā)其位置信息。4．LAR協(xié)議的特點與DSR協(xié)議相比，LAR協(xié)議利用位置信息來限制路由請求消息的洪泛，從而在一定程度上減少了路由發(fā)現(xiàn)過程的耗費，這是LAR協(xié)議最主要的優(yōu)點。但是，從另一個方面來看，為了獲得這些位置信息，網(wǎng)絡中的節(jié)點需要引入相應的設備（如GPS等），增加位置信息的交互過程；4．LAR協(xié)議的特點同時這些位置信息也僅僅是物理坐標信息，并不能完全代表節(jié)點間的可達性，例如節(jié)點之間雖然位置靠近，但由于中間有障礙物阻擋，可能節(jié)點無法直接通信；考慮到一些特殊的網(wǎng)絡環(huán)境，LAR協(xié)議可能需要多次發(fā)起路由請求過程才能最終成功。因此路由發(fā)現(xiàn)的時延以及耗費等性能指標在某些情況下未必比DSR協(xié)議優(yōu)越。AODV（Ad-hocOn-DemandDistanceVectorAlgorithm）協(xié)議在DSR中，采用了源節(jié)點路由方式，每個數(shù)據(jù)報文頭部都攜帶路由信息，增加了報文長度，降低了傳輸效率，尤其是在數(shù)據(jù)報文本身很短的情況下，其耗費尤為明顯。在AODV協(xié)議中，路由中的每個節(jié)點都維護路由表，因而數(shù)據(jù)報文頭部不再需要攜帶完整的路由信息，從而提高了協(xié)議的效率。 1．路由發(fā)現(xiàn)過程AODV協(xié)議采用與DSR協(xié)議類似的廣播式路由發(fā)現(xiàn)機制。與DSR協(xié)議相比，AODV的路由依賴于中間節(jié)點建立和維護的動態(tài)路由表。AODV的路由發(fā)現(xiàn)過程由反向路由的建立和前向路由的建立兩部分組成。反向路由指從目的節(jié)點到源節(jié)點的路由，用于將路由響應報文回送至源節(jié)點。如下圖（a）所示，反向路由可能會有多條。前向路由指從源節(jié)點到目的節(jié)點方向的路由，用于以后數(shù)據(jù)報文的傳送。如下圖（b）所示。AODV的路由建立過程AODV的路由發(fā)現(xiàn)過程如下：（1）源節(jié)點首先發(fā)起路由請求過程，在發(fā)起的路由請求報文中攜帶以下信息字段：<源地址，源序列號，廣播ID，目的地址，目的序列號，跳數(shù)計數(shù)器>其中，序列對<源地址，廣播ID>惟一標識一個路由請求。（2）中間節(jié)點在收到路由請求報文時，比較本節(jié)點和目的節(jié)點的地址，①如果自己是目的節(jié)點，則回復路由響應報文。否則轉步驟②；②根據(jù)<源地址，廣播ID>判斷是否收到過該請求消息，如果收到過則丟棄該請求消息，否則轉向步驟③；③記錄相應的信息，以形成反向路由。記錄的信息包括：上游節(jié)點地址（即向本節(jié)點發(fā)送路由請求消息的節(jié)點）、目的地址、源地址、廣播ID、反向路由超時時長和源序列號等。同時跳數(shù)計數(shù)器加1，向鄰節(jié)點轉發(fā)該路由請求報文。2．路由表管理及維護AODV路由協(xié)議中的路由表主要包括目的節(jié)點下一跳節(jié)點距離目的節(jié)點的跳數(shù)目的節(jié)點序列號本路由的活躍鄰節(jié)點本路由的超期時長等信息。同時，在AODV協(xié)議中，節(jié)點還存儲一些與路由表相關的信息。以下幾點是其中比較重要的。（1）路由請求超時定時器：和反向路由相關的定時器，當定時器超期后，節(jié)點仍未收到路由響應報文時，節(jié)點則認為該反向路由無效，刪除該反向路由。（2）活躍超時時長：和前向路由相關的時長。當超過活躍時長時間后，節(jié)點仍然無數(shù)據(jù)利用該路由發(fā)送時，刪除該路由（即使該路由可能有效）。3．AODV協(xié)議的特點從前面介紹的DSDV協(xié)議和DSR協(xié)議來看，AODV協(xié)議綜合了兩者的特點。與基于表驅動方式的DSDV協(xié)議相比，AODV協(xié)議采用了按需路由的方式，即網(wǎng)絡中的節(jié)點不需要實時維護整個網(wǎng)絡的拓撲信息，而只是在發(fā)送報文且沒有到達目的節(jié)點的路由時，才發(fā)起路由請求過程；與DSR協(xié)議相比，在AODV協(xié)議中，由于通往目的節(jié)點路徑中的節(jié)點建立和維護路由表，數(shù)據(jù)報文頭部不再需要攜帶完整路徑，減少了數(shù)據(jù)報文頭部路由信息對信道的占用，提高了系統(tǒng)效率。因此，協(xié)議的帶寬利用率高，能夠及時對網(wǎng)絡拓撲結構變化作出響應，同時也避免了路由環(huán)路現(xiàn)象的發(fā)生。但是在AODV協(xié)議中也存在一些問題。（1）AODV協(xié)議僅適用于雙向傳輸信道的網(wǎng)絡環(huán)境。由于在路由請求消息的廣播過程中建立了反向路由，供路由響應報文尋路，因此網(wǎng)絡要滿足雙向傳輸信道的要求；（2）路由表中僅維護一條到指定的目的節(jié)點的路由，而在DSR協(xié)議中，源節(jié)點可以維護多條到目的節(jié)點的路由。如果節(jié)點間存在多條路由，當某條路由失效時，源節(jié)點可以選擇其他的路由而不需要重新發(fā)起路由發(fā)現(xiàn)過程，這在網(wǎng)絡拓撲結構變化頻繁的環(huán)境中尤其重要；（3）由于AODV協(xié)議采用了超時刪除路由的機制，因此即使路由未失效，在超過時限后也將被刪除。ZRP路由協(xié)議（ZoneRoutingProtocol）ZRP（ZoneRoutingProtocol）是一種利用集群結構、混合使用表驅動和按需路由策略的AdHoc網(wǎng)絡路由協(xié)議。在ZRP中，集群被稱作域（Zone）。為了綜合利用按需路由和表驅動路由的各自優(yōu)點，ZRP規(guī)定每個節(jié)點在區(qū)域內部采用表驅動路由協(xié)議，對于區(qū)域外節(jié)點的路由則采用類似于DSR中的按需路由機制尋找路由。ZRP中的區(qū)域、邊界節(jié)點。1．區(qū)域及邊界節(jié)點在ZRP中，域形成算法較為簡單，它是通過一個重要的協(xié)議參數(shù)——區(qū)域半徑（以跳數(shù)為單位），指定每個節(jié)點維護的區(qū)域大小，即所有距離不超過區(qū)域半徑的節(jié)點都屬于該區(qū)域。一個節(jié)點可能同時從屬于多個區(qū)域。如下圖所示，橢圓形虛線部分表示為節(jié)點A的半徑為2（即2跳之內）的區(qū)域，節(jié)點B、C、D、E、F都是節(jié)點A的域內節(jié)點，節(jié)點G則是域外節(jié)點。需要注意的是，節(jié)點E既可以由B轉接到達（距離節(jié)點A兩跳），也可以由C-F轉接到達（距離節(jié)點A三跳），由于協(xié)議約定最小距離小于或等于區(qū)域半徑的節(jié)點都歸屬于域內節(jié)點，因此節(jié)點E是節(jié)點A的域內節(jié)點。邊界節(jié)點是指最小距離正好等于區(qū)域半徑的節(jié)，在下圖中，節(jié)點D、E、F都是節(jié)點A的邊界節(jié)點。ZRP中的域及邊界節(jié)點（節(jié)點A，半徑為2）2．IARP和IERPZRP由兩個過程組成：（1