【正文】 本身。當(dāng)節(jié)點轉(zhuǎn)發(fā)路由請求分組時，它會將其上游節(jié)點的標(biāo)志 ID錄入路由表，從而能構(gòu)建一條從目的節(jié)點到源節(jié)點的反向路由。NS 中， AODV 的實現(xiàn) 結(jié)合 DSR 和 DSDV 協(xié)議。 ⑷ 區(qū)域路由協(xié)議（ ZRP） Ad Hoc 網(wǎng)絡(luò)中 AODV 路由協(xié)議的研究與仿真 7 ZRP 協(xié)議是一個表驅(qū)動和按需源路由協(xié)議的組合，網(wǎng)絡(luò)內(nèi)的所有節(jié)點都有一個以自己為中心的虛擬區(qū)，區(qū)內(nèi)的節(jié)點數(shù)與設(shè)定的區(qū)半徑（按跳數(shù)計）有關(guān)，因此區(qū)是重疊的，這是與分級路由的區(qū)別。對區(qū)外節(jié)點的路由使用按需路由，利用區(qū)間路由選擇協(xié)議（ IERP）建立 路由 [14,15,16,17]。DSR 主要包括兩個過程：路由搜索和路由維護。具體過程如下：源節(jié)點 S 將使用洪泛法發(fā)送路由請求消息（ RREQ），RREQ 包含源和目的節(jié)點地址以及唯一的標(biāo)志號，中間節(jié)點轉(zhuǎn)發(fā) RREQ，并附上自己的節(jié)點標(biāo)識。此外，中間節(jié)點也可以使用路由緩存技術(shù)（ Routing Cache）來對協(xié)議作進一步優(yōu)化。因為反應(yīng)式路由協(xié)議更加適合 Ad Hoc 網(wǎng)絡(luò)的移動、動態(tài)、帶寬和功率等約束條件 [18,19,20,21]。 第三章在 NS2平臺下模擬了 AODV路由協(xié)議的在無線網(wǎng)絡(luò)上的性能 。 第五章提出了 AODV路由協(xié)議的改進思想。隨著協(xié)議的不斷發(fā)展和完善，現(xiàn)在 AODV的 hiternctDraft己經(jīng)有了 ，由 Nokia研究中心的 加利福尼亞大學(xué) Santa Barbara的 Elizabeth Cincinati大學(xué)的 Samir R Das等共同開發(fā)，被 IETF MANET工作組于 2020年 6月 18日正式公布為 Ad Hoc網(wǎng)絡(luò)路由協(xié)議的RFC標(biāo) 準(zhǔn)。 AODV在每個中間節(jié)點隱式保存了路由請求和應(yīng)答的結(jié)果，并利用擴展 環(huán)搜索的辦法來限制搜索發(fā)現(xiàn)過的目的節(jié)點的范圍。 和 DSDV保存完整的路由表不同的是， AODV通過建立基于按需路由來減 少路由廣播的次數(shù)，這是 AODV對 DSDV的重要改進。 AODV是一個 純粹的按需路由系統(tǒng)，那些不在路徑內(nèi)的節(jié)點不保存 路由信息，也不參與路由表的交換。 AODV的操作是無環(huán)路的，在避免了通常 Belmanford算法的無窮計數(shù)問題的同時，還提供了很快的收斂速度。目的序列號是 目 的節(jié)點創(chuàng)建 ，并在發(fā)給發(fā) 起節(jié)點的路由信息中使用的。 AODV使用 3種消息作為控制信息 ： RouteRequests(RREQs)， RouteReplies (RREPs)和RouteError(RERRs)。當(dāng) 源節(jié)點需要和目的節(jié)點通信時，如果在路由表中己經(jīng)存在了對應(yīng)的路由時， AODV不會進行任何操作。當(dāng)這個 RREQs到達目的節(jié)點 本身，或者是 一個擁有足夠新的到目的節(jié)點路由的中間節(jié)點時，路由就可以確定 了。 目 的節(jié)點或中間節(jié)點通過原路 返回一個 RREPs信息來向源節(jié)點確定路由的可用性。后者在路由時，只有源節(jié)點知道到目的節(jié)點的完整路由，而中 間節(jié)點都不知道有關(guān)的路由信息。同時，節(jié)點會監(jiān)視一個活動路由 (active roule，有限跳的，可用于數(shù)據(jù) 轉(zhuǎn)發(fā)的路由表 )中，下Ad Hoc 網(wǎng)絡(luò)中 AODV 路由協(xié)議的研究與仿真 9 一跳節(jié)點的狀況。在 RERRs消息中，指明了由于斷鏈而導(dǎo) 致無法達到目的節(jié)點。 AODV 路由算法原 理 AODV路由協(xié)議是一種按需改進的距離向量路由協(xié)議，具有按需路由協(xié)議的特點，即在 AODV路由協(xié)議中，網(wǎng)絡(luò)中的每個節(jié)點在需要進行通信時才發(fā)送路由分組，而不會周期性地交互路由信息以得到所有其它主機的路由 ； 同時具有距離向量路由協(xié)議的一些特點，即各節(jié)點路由表只維護本節(jié)點到其他節(jié)點的路由，而無須掌握全網(wǎng)拓?fù)浣Y(jié)構(gòu)。在數(shù)據(jù)傳輸過程中，當(dāng)中間節(jié)點檢測到一條正在傳輸數(shù)據(jù)的活動路由的下一跳鏈路斷開或者節(jié)點收到去往某個目的地節(jié)點的數(shù)據(jù)報文，而節(jié)點沒有到該目的地節(jié)點的有效路由時，中間節(jié)點向源節(jié)點單 播或多播路由錯誤消息 RERR，源節(jié)點收到 RERR后就知道存在路由錯誤，并根據(jù) RERR中指示的不可達目的地重新找路。每一個接收到 RREQ的節(jié)點都會保存到源節(jié)點的路由，當(dāng)?shù)侥康墓?jié)點的路由找到時就能用單播將 RREP傳回源節(jié)點 [22]。只有有效路由可以用來轉(zhuǎn)發(fā)用戶數(shù)據(jù)分組。一個廣播報文不是盲目轉(zhuǎn)發(fā)的，對它的轉(zhuǎn)發(fā)會有限制。 Destination(目的節(jié)點址 ) 用戶數(shù)據(jù)分組將要被發(fā)送到的 IP地址，有時候用這個地址來表示目的節(jié)點 。 Forwarding node(轉(zhuǎn)發(fā)節(jié)點 ) 同意轉(zhuǎn)發(fā)用戶數(shù)據(jù)分組至另一節(jié)點的中間節(jié)點 。 Forward route(轉(zhuǎn)發(fā)路由 ) 為了從發(fā)起路由查找操作的源節(jié)點發(fā)送用戶數(shù)據(jù)分組到目的節(jié)點而建立起的一條路由。無效路由表項雖然不可以用來轉(zhuǎn)發(fā)用戶數(shù)據(jù)分組，但它仍然會將路由信息存儲一段時間再刪除。 例如，發(fā)起路由查找過程并廣播 RREQ協(xié)議幀的節(jié)點稱為 RREQ的源節(jié)點 。 Sequence number(序列號 ) 一個不斷增加的數(shù)字，由每一個幀的源節(jié)點來維護。 AODV 路由協(xié)議數(shù)據(jù)報格式 RREP 協(xié)議幀格式 圖 Type 一標(biāo)志幀的類型， RREP 幀設(shè)為 2。 A 一需要應(yīng)答標(biāo)記，當(dāng)節(jié)點收到這個 RREP 幀后需要給于應(yīng)答 .這樣做是為了避免 單向鏈路的問題。 Ad Hoc 網(wǎng)絡(luò)中 AODV 路由協(xié)議的研究與仿真 11 Prefix Size 一這個字段用于分群的無線自組網(wǎng)。當(dāng)不為零的時候，具有相同 Prefix Size 的節(jié)點屬于同一個群。 Destination IP Address 一目的節(jié)點的 IP 地址。 Originator IP Address 一發(fā)起這個路由請求節(jié)點的 IP 地址。 RERR 協(xié)議幀格式 圖 幀 格式 Type一標(biāo)志幀的類型， RERR幀設(shè)為 3。當(dāng)節(jié)點進行了本地鏈路的修復(fù)，通知上游節(jié)點不要進行刪除動作時設(shè)置這個標(biāo)志。保留將來擴展時使用。 Unreachable Destination IP Address一由于鏈路斷開造成的不可達目的節(jié)點的護地 址 。在任何時候由于鏈路中斷，導(dǎo)致從該節(jié)點的鄰居到一個或多個目的節(jié)點變得不可達時，發(fā)送 RERR協(xié)議幀。通常在 存在單向鏈路情況下，用它來避免形成環(huán)路。 Reserved一發(fā)送時為 0，接收時忽略，保留給將來擴展時使用 。 這些消息數(shù)據(jù)是如何處理的。這一章節(jié)將對以上情況進行詳細描述。這一序列號稱為目的地序列 號。 AODV依賴在網(wǎng)絡(luò)中的每個節(jié)點擁有并維護自 身的目的序列號來避免到該節(jié)點的所有路由出現(xiàn)環(huán)路。 在目的節(jié)點產(chǎn)生一個 RREP對 RREQ進行應(yīng)答 之前，必須立即將自己的序列 號更新，更新值為當(dāng)前序列號與 RREQ報文序列號中的最大值 。為實現(xiàn)序列號 的循環(huán)，序列號采用 32比特?zé)o符號整數(shù)，當(dāng)序列號增加到最大可能值時，再增加則值變?yōu)?0。比較必須使用有符號 32比特算法進行，用收到 AODV消息中 的序列號的值與當(dāng)前存儲的序列號的值相減，所得值如果小于 0，則必須丟棄 AODV消息中該目的地的相關(guān)信息。 通往目的節(jié)點的下一跳鏈路丟失或過期時，節(jié)點也可以在它的路由表項中改變目的地序列號。 在這 種情況下，對于使用該下一跳的每一個目的地，節(jié)點增加它的序列號并將路由標(biāo)記為無效 。 節(jié)點在下列情況下可以改變路由表項中的目的地序列號 ； Ad Hoc 網(wǎng)絡(luò)中 AODV 路由協(xié)議的研究與仿真 13 節(jié)點本身是目的地節(jié)點，并為自己提供了一條新的路由 ； 節(jié)點收到 AODV控制消息，消息中具有關(guān)于目的節(jié)點序列號的較新信息 ； 通往目的地節(jié)點的路徑過期或中斷。在沒有該目的地的對應(yīng)表項的情況下，則建立表項，并利用控制報文記錄的源 IP地址和前一跳節(jié)點 IP地址建立到源節(jié)點的反向路由表項。路由僅在下列情況下進行更新 ： 新序列號高于路由表中的目的地序列號 ； 新序列號與路由表中序列號相等，但是跳數(shù) +1小于路由表中存在的跳數(shù) ； 路 由表序列號未知。 這一路由現(xiàn)在可以用來發(fā)送任何排隊等待數(shù)據(jù)報文， 完成任何沒有完成的路由請求。 由于我 們認(rèn)為源和目的地址之間的路由是對稱的，那么沿著逆向路徑返回源節(jié)點的前一跳 的有效路由生存期也同樣更新為大于等于當(dāng)前時間加上 ACTIVE_ROUTE_TMIEOUT。路由表項中的先驅(qū)列表就是使用了這條路由的所有鄰居節(jié)點 (一個或多個 )，在節(jié)點檢測到下一跳鏈路丟失的情況下，將會向先驅(qū)列表中的所有 節(jié)點發(fā)出通知 。 這種情況可能是 ： 目的節(jié)點之前對于當(dāng)前節(jié)點是未知的，或者曾經(jīng)有效的到目的節(jié)點的路由已經(jīng)過期或標(biāo)記為無效。如果源節(jié)點不 知道目的節(jié)點的序列號，必須設(shè)置未知序列號標(biāo)記。 RREQ ID字段為當(dāng)前節(jié)點上一次使 用的 RREQ ID號加 1。跳數(shù)字段設(shè)置為 0。以這種方式，如果節(jié)點再從它的鄰 居收到同樣的RREQ報文，它將不對此進行重新處理和轉(zhuǎn)發(fā) RREQ ID和發(fā)起者的 企地址 聯(lián)合起來標(biāo)志一個獨一無二的 RREQ報文。為了使之盡可能有效地發(fā)生，中間節(jié)點產(chǎn)生發(fā)往發(fā)起者節(jié)點的 RREP的同時，應(yīng)該附帶通知目的節(jié)點，告知目的節(jié)點返回發(fā)起節(jié)點的反向路由。 節(jié)點每秒鐘不應(yīng)該產(chǎn)生多于 RREQ RATELIMIT次的 RREQ消息。如果在NET_TRAVERSAL_TIME微秒的時間內(nèi)沒有獲得路由，則節(jié)點廣播另 一個 RREQ試圖重新進行路由發(fā)現(xiàn)過程，直到在最大 TTL值時達到了 RREQ_RETRIES的最大次數(shù)。 對于每一次新的嘗試，護頭中的 TTL字段根據(jù) 描述的機制進行設(shè)置，以對 RREQ每次發(fā)送的距離進行控制。這個緩存應(yīng)該是先進先出的 (FIFO)。 路由請求消息的控制傳播 為了防止不必要的網(wǎng)絡(luò)范圍的 RREQ傳播，發(fā)起者節(jié)點應(yīng)該使用擴展環(huán)搜索技 術(shù)。 如果 RREQ超時而沒有一個對應(yīng)的 RREP，發(fā)起者再一次廣播 RREQ，此時 TTL值 增加 TTL_INCREMENT。 當(dāng)希望所有的重試經(jīng)過整個網(wǎng)絡(luò)時，可以通過將 TTL_START和TTL_INCREMENT都配置成同樣的值 NETDIAMETER來實現(xiàn) 。 如果一段時間后需要到同一目的節(jié)點的新路由 (比如路由丟失的情況發(fā)生 )， RREQ的 IP頭中的 TTL初始化設(shè)置為跳數(shù)加上 TTL_INCREMENT。超過 TTL_THRESHOLD則 TTL的值設(shè)為 NETDIAMETER。 而且可以根據(jù)需要配置更長的路 由表項刪除間。 處理和轉(zhuǎn)發(fā)路由請求 當(dāng)節(jié)點收到 RREQ，它首先建立或更新到上一跳的無有效序列號的反向路由， 然后檢查確定在至少腳訂 HweDiscovery TIME時間內(nèi)，它是否收到帶有同樣發(fā)起 者 IP地址和 RREQ ID的 RREQ報文。 這一節(jié)的剩余部分描述沒有丟棄的 RREQ報文的處理。然后，節(jié)點使用 RREQAd Hoc 網(wǎng)絡(luò)中 AODV 路由協(xié)議的研究與仿真 15 中的發(fā)起者序列號 (作為路由表項中的目的地序列號 )，在路由表中建立或更新到發(fā)起者 IP地址的反向路由。 (增加了 1以后的值 ) 任何時候收到 RREQ消息，到發(fā)起者 IP地址的反向路由表項的生存期設(shè)置為 {現(xiàn)有生存期，最小生存期 }的最大值。 節(jié)點在下列兩種情況下才產(chǎn)生 RREP： 節(jié)點本身是目的地節(jié)點 ； 節(jié)點具有到目的地的有效路由，節(jié)點現(xiàn)有的到目的地節(jié)點的路由表項的目的地 序列號有效，并且大于或者等于 RREQ消息中的目的地序列號 。 否則，如果收到 RREQ消息的 IP報文頭的 TTL值大于 1，節(jié)點更新 RREQ，并向它的所有配置接口廣播 RREQ至 地址。 最后，設(shè) 置請求目的地的目的地序列號，值為 {收到 RREQ消息中的相應(yīng)值，節(jié)點當(dāng)前維護 的請求目的地節(jié)點的目的地序列號值 }的最大值。 產(chǎn)生路由應(yīng)答 如果節(jié)點收到對于某個目的地的路由請求，當(dāng)節(jié)點具有一條足夠新的路由來滿 足該路由請求 ，或者它本身就是目的地節(jié)點，那么這個節(jié)點產(chǎn)生一個 RREP消息， 節(jié)點拷貝 RREQ消息中的目的地 IP地址和發(fā)起者序列號 RREP的對應(yīng)字段 .根 據(jù)節(jié)點本身是請求目的地或者是具有足夠新路由的中間節(jié)點，處理過程略有不同，在下面的章節(jié)進行描述。 隨著 RREP被轉(zhuǎn)發(fā)回發(fā)起 RREQ消息的節(jié)點，跳數(shù)字段也在每一跳加 1。 如果產(chǎn)生 RREP的節(jié)點是目 的節(jié)點本身，假如 RREQ報文中的序列號等于目的地節(jié)點本身的序列號加 1，則節(jié)點必須把自己的序列號再加 1(RREQ報文中的序列 號大于目的地節(jié)點維護的自身序列號的情況 ： 某節(jié)點因為檢測到通往目的地的鏈路 中斷，將目的地序列號加1，然后重發(fā)路由請求 )。 目的節(jié)點將它的序列號何能是新增加的 )放入 RREP的 目的地序列號字段當(dāng)中，并把跳數(shù)字段值設(shè)置為 0。 如果產(chǎn)生 RREP的節(jié)點不是目的地節(jié)點，而是發(fā)起節(jié)點到目的地節(jié)點路徑上的一個中間節(jié)點，它將拷貝已知的目的地序列號 RREP消息中的目的地序列號字段。 中間節(jié)點 同時更新到RREQ發(fā)起者節(jié)點的路由表項，這一操作通過將通往目的地的下一跳放 入反向路由表項 (即RREQ消息中發(fā)起者 IP地址字段的表項 )的先驅(qū)表中實現(xiàn)。 RREP的生存期字段由路由表項的過期時間減去當(dāng)前時間計算得出。如果中間節(jié)點對每一個發(fā)出的RREQ進行應(yīng)答，目的節(jié)點就不能收到任何 RREQ的拷貝，也就不可能知道到發(fā)起者節(jié)點的路由 .這可能導(dǎo)致目的節(jié)點發(fā)起路由發(fā)現(xiàn) (比如，如果發(fā)起者節(jié)點 試圖建立 TCP會話