【文章內(nèi)容簡介】 用利用二元指數(shù)后退算法。即節(jié)點第一次發(fā)送RREQ時，等待NET_TRAVERSAL_TIME毫秒，隨后的每次嘗試等待的時間都是前一次等待時間乘2。 路由請求消息的控制傳播為了防止的RREQ分布擴展至整個網(wǎng)絡(luò)，源節(jié)點將使用擴展環(huán)式搜索技術(shù)。在這種技術(shù)，為源節(jié)點的RREQ分組的IP中初始化一個TTL=TTL_START，并設(shè)置收到RREP時間為RING_TRAVERSAL_TIME毫秒。用來計算RING_TRAVERSAL_TIME的TTL_VALUE設(shè)置為IP頭中TTL的值。當RREQ超時，重發(fā)RREQ時，TTL增加TTL_INCREMENT。如此繼續(xù)，直到TTL達到TTL_THRESHOLD，此后的重試中設(shè)TTL=NET_DIAMETER。每一次等待RREQ的計時時間都為RING_TRAVERSAL_TIME，當需要重試的分組跨越整個Ad hoc網(wǎng)時，可以把TTL_START和TTL_INCREMENT都設(shè)為NET_DIAMETER。當需要對同一個目的節(jié)點啟動新的路由發(fā)現(xiàn)時，RREQ中的TTL將被初始化，成為原有失效的跳數(shù)加上TTL_INCREMENT。一個過期的路由表項在DELETE_PERIOD的時間內(nèi)都不能被擦除。另外還能夠設(shè)置更長的擦除時間。任何一個正在等待RREQ的路由表項在2*NET_TRAVERSAL_TIME的時間內(nèi)都不能被擦除。 處理和轉(zhuǎn)發(fā)路由請求當一個節(jié)點接收到RREQ消息時，它首先創(chuàng)建或更新沒有有效的路由表項。然后查看在至少PATH_DISCOVERY_TIME是否收到相同的源IP地址和RREQ ID消息的RREQ分組，如果有的話，忽略目前收到的RREQ分組。當收到的RREQ不被忽略時，首先把RREQ中的跳數(shù)增1，然后在路由表中搜尋到源節(jié)點的反向路徑，使用最長匹配原則，如果有需要，則創(chuàng)建新的反響路由表項，或者用RREQ中的源節(jié)點序列號更新原有路由表項。當反向路徑被創(chuàng)建或更新時，將會執(zhí)行下面的操作：。(1) 將RREQ消息源節(jié)點序號的和相對應(yīng)的反向路由中的目的節(jié)點序列號作比較，如果前者比后者大，前者將取代后者。(2) 路由項的有效序列號域被設(shè)為真。(3) 路由項的下一條設(shè)為向該節(jié)點傳送RREQ的節(jié)點，這個從IP頭部中的源地址IP中獲得。不管何時收到一個RREQ,反向路由項的生存期都會被設(shè)為ExistingLifetime和MinimalLifetime中的較大者，其中MinimalLifetime=(當前時間+2*NET_TRAVERSAL_TIME.2*HopCount*NODE_TRAVERSAL_TIME).如果一個節(jié)點不產(chǎn)生一個RREP，且收到的RREQ的IP頭中的TTL大于1。這些RREQ的TTL減1，而跳數(shù)則增1。最后，目的節(jié)點接收到RREQ分組設(shè)置為自己的節(jié)點和目的節(jié)點序列號中最大的序列號值。然而，即使收到的RREQ目標節(jié)點序列，它比目前的保存自己的目標序列號大，也不能修改其保存的值。如果一個節(jié)點會產(chǎn)生RREP，則可忽略它收到的RREQ。注意，如果一個中間節(jié)點對每一個RREQ都作出回復(fù)，那么目的節(jié)點可能收不到任何路由發(fā)現(xiàn)的信息。在這種情況下，目標節(jié)點無法從RREQ分組中獲取源節(jié)點的路由。這將導(dǎo)致目標節(jié)點也該發(fā)起路由發(fā)現(xiàn)過程。為了避免這種情況，當目的節(jié)點可能需要一條到源節(jié)點的路徑時，源節(jié)點會設(shè)置RREQ中的G標志域。當一個節(jié)點收到設(shè)置了G域的RREQ，當它回復(fù)RREP給源節(jié)點時，它也必須同時單播一個非必要RREP給目的節(jié)點。 節(jié)點收到RREQ處理過程 產(chǎn)生路由應(yīng)答一個節(jié)點在以下2種情況會產(chǎn)生RREP：(1) 它本身就是目的節(jié)點(2) 它有一個有效的路由到達目的節(jié)點，而路由表項的目標序號大于等于RREQ消息序列數(shù)目，且D標志未設(shè)置。當產(chǎn)生RREP時，節(jié)點復(fù)制RREQ中的目的節(jié)點IP地址和源節(jié)點序列號到RREP中的相應(yīng)域中，其余的操作，視上述兩種情況有細微的不同，下面將作仔細的說明。因為RREP是反向發(fā)送到源節(jié)點，因此在每一跳的過程中，跳數(shù)都會被增1。因此，當RREP到達源節(jié)點，源節(jié)點跳數(shù)表示到目的節(jié)點的距離。 目的節(jié)點產(chǎn)生的RREP當節(jié)點本身是目的節(jié)點時，如果它自身的序列號增1后與RREQ中的序列號相等，則將自身序列號增1，否則，在產(chǎn)生RREP之前不改變自身的序列號。然后目的節(jié)點把自己的序列號復(fù)制到RREP中，并把跳數(shù)設(shè)為0，把MY_ROUTE_TIMEOUT復(fù)制到RREP的生存期域中。每個節(jié)點都可以重新設(shè)置它們的MY_ROUTE_TIMEOUT值。 中間節(jié)點產(chǎn)生的RREP當節(jié)點是中間節(jié)點時，它復(fù)制它所知道目的節(jié)點序列號到RREP中，并把它收到的RREQ中指示的上一跳節(jié)點添加到指向目的節(jié)點的路由項的前驅(qū)表中，而把去往目的節(jié)點的下一跳節(jié)點添加到指向源節(jié)點的反向路由項的前驅(qū)表中。最后，中間節(jié)點把目的節(jié)點的跳數(shù)復(fù)制到RREQ分組當中，而生存范圍設(shè)置成路由項的到期時間減去當前時間。 產(chǎn)生非必要RREP如果節(jié)點收到的RREQ設(shè)置了G標志位，它必須單播一個被必要RREP給目的節(jié)點。非必要RREP包含了以下表中，：跳數(shù)到源節(jié)點的跳數(shù)目的節(jié)點IP地址發(fā)送RREQ的源節(jié)點的IP地址目的節(jié)點序列號RREQ中的源節(jié)點序列號源節(jié)點IP地址RREQ中目的節(jié)點IP地址生存期到達RREQ的源節(jié)點的的路徑的生存期 RREP內(nèi)容注解RREP非必要，然后被發(fā)送到目的節(jié)點的下一跳，如果目標節(jié)點發(fā)送一個RREQ分組到源節(jié)點，而RREP分組對RREQ分組相同。而發(fā)往源節(jié)點的RREP不管RREQ有無設(shè)置G標志位都一樣。 接收和轉(zhuǎn)發(fā)路由應(yīng)答當一個節(jié)點收到RREP,它首先在路由表中搜尋到上一跳的路由項，如有需要，會創(chuàng)建一條新的表項，但不包含有效的序列號。然后節(jié)點把RREP中的跳數(shù)增1，并稱這個值為“新跳數(shù)”。如果去往目的節(jié)點的路徑尚不存在則創(chuàng)建一條新的，否則把RREP中的目的節(jié)點序列號和已有的相比較。經(jīng)過比較后，只有在以下幾種情況中會更新已有的路由項：(1) 原路由項中的序列號被標志為無效；(2) RREP中的序列號大于原有的序列號；(3) 兩個序列號相等，不過這條路徑被標志為不活動的；(4) 序列號相等，但是新的跳數(shù)比原有的要小。如果去往的目的節(jié)點的路由項被創(chuàng)建或更新，會執(zhí)行以下的操作：。(1) 路徑被標志為活躍的(2) 目的節(jié)點序列號被標志為有效的(3) 下一跳設(shè)為傳來RREP的那個節(jié)點(4) 跳數(shù)設(shè)為“新跳數(shù)”(5) 過期時間設(shè)為現(xiàn)在的時間加上RREP中的生存時間(6) 目的節(jié)點序列號設(shè)置成為RREP中的序列號如果當前節(jié)點不是RREP中的源節(jié)點，它會查詢路由表以決定RREP的下一跳。如果節(jié)點發(fā)送的RREP的鏈路有錯誤或是單向的，節(jié)點會設(shè)置其中的A標志位，以使RREP的接收方會回復(fù)一個RREPACK。任何轉(zhuǎn)發(fā)RREP的節(jié)點，都會把發(fā)送RREP的下一跳加入到去往目的節(jié)點的路由項前驅(qū)表中，在同一時間，修改源節(jié)點路徑的生存期為現(xiàn)有的生存與（當前時間+ ACTIVE_ROUTE_TIMEOUT）的較大值。 節(jié)點收到RREP的處理過程 單向鏈路上的操作當鏈路為單向的時候，RREP的傳送有可能會失敗，如果源節(jié)點收不到RREP，在計時結(jié)束后，會重新嘗試發(fā)起路由發(fā)現(xiàn)的過程。然而，這種情形可能一直重復(fù)而得不到任何改善，即使重復(fù)嘗試仍然不能得到任何路徑。在AODV中有對應(yīng)糾正的操作，即節(jié)點只對第一個具有相同RREQ ID的RREQ做出回應(yīng)，其他后續(xù)的RREQ都將被忽略。然而這又將產(chǎn)生新的問題，即第一個RREQ可能經(jīng)過的路徑中包含單向鏈路，但后續(xù)的RREQ可能經(jīng)過雙向鏈路到達，而它們將會被忽略。為了避免這種情況，當一個節(jié)點檢測到一個RREP傳輸失敗，它建立一個黑名單將剛剛傳送的RREP的下一跳記錄到其中。每個節(jié)點將忽略節(jié)點中黑名單所羅列的RREQ分組。黑名單中的節(jié)點在經(jīng)過BLACKLIST_TIMEOUT后會從名單中移除。RREP ACK數(shù)據(jù)包不包含有關(guān)的信息的RREP。這個信息只是為了告訴發(fā)送方鏈路當前是雙向的。 Hello消息一個節(jié)點由當?shù)貜V播Hello報文節(jié)點提供連接信息。每隔HELLO_INTERVAL毫秒，該節(jié)點將檢查其是否在此期間發(fā)送了一個廣播數(shù)據(jù)包，如果不是，它會廣播TTL= 1的RREP，并稱為Hello分組，它的格式如下設(shè)置，：Destination IP Address節(jié)點本身的IP地址Destination Sequence Number節(jié)點最新序列號Hop Count0LifetimeALLOWED_HELLO_LOSS*HELLO_INTERVAL hello分組的格式一個節(jié)點通過監(jiān)聽來自鄰居的分組來決定連通性。如果在過去DELETE_PERIOD時間之內(nèi)，節(jié)點已經(jīng)收到了鄰居的數(shù)據(jù)包，然后ALLOWED_HELLO_LOSS* HELLO_INTERVAL毫秒從未收到任何來自這個鄰居的數(shù)據(jù)包，它就會認為到該鄰居的鏈路當前已經(jīng)中斷。當一個節(jié)點收到鄰居的一個Hello分組時，它會認為它有一條到達鄰居活躍路徑。如果這條路徑已經(jīng)存在，它會延長相應(yīng)節(jié)點的生存期，如有必要，可至少設(shè)為ALLOWED_HELLO_LOSS*HELLO_INTERVAL，并復(fù)制Hello分組中最新的目的節(jié)點序列號到相應(yīng)路由項中。 維護本地連接性節(jié)點應(yīng)該持續(xù)監(jiān)測活躍下一跳和在（ALLOWED_HELLO_LOSS*HELLO_INTERVAL）時間內(nèi)接收到過Hello分組的鄰居連通性。一個節(jié)點使用以下的鏈路或網(wǎng)絡(luò)層機制來維護上述相關(guān)節(jié)點的連通性的準確信息。(1) 任何合適的鏈路層通知，例如每次給活躍下一跳發(fā)送數(shù)據(jù)包時IEEE ，可以用來判定鏈路連通性。還有例如鏈路層ACK的缺失，或發(fā)送RTS后收不到CTS，甚至于達到重傳次數(shù)的最大值時，都提示了鏈路層的中斷。(2) 如果沒有可用的上述通知信息，使用被動通知的方法。即當預(yù)期下一跳會轉(zhuǎn)發(fā)分組時，監(jiān)聽嘗試傳送的信道，如果再NEXT_HOP_WAIT毫秒內(nèi)監(jiān)聽不到傳送或下一跳就是目的節(jié)點時，使用下面的其中一種方法來判定連通性：①收到任何來自下一跳的分組；②單播一個RREQ給下一跳，詢問到下一跳的路徑③單播一個ICMP響應(yīng)請求給下一跳如果使用上面的任何方法都不能監(jiān)測到到達下一跳節(jié)點的鏈路，那么這條鏈路則被認定為是丟失的。 RERR消息，路由過期和路由刪除對路由錯誤和鏈路中斷的處理一般包含下面幾步：(1) 把現(xiàn)有的相關(guān)路徑置為失效；(2) 列出受影響的的目的節(jié)