一種能量均衡的AODV路由協(xié)議研究

1.引言

無(wú)線(xiàn)自組網(wǎng)(Ad Hoc)是由一組帶有無(wú)線(xiàn)通信收發(fā)裝置的移動(dòng)終端節點(diǎn)組成的一個(gè)多跳、臨時(shí)和無(wú)中心的網(wǎng)絡(luò )，具有不依賴(lài)于固定基礎設施、抗毀性強、可快速展開(kāi)等優(yōu)點(diǎn)，適用于軍用和搶險救災的應急通信。

武警部隊是國家保障公民生命財產(chǎn)安全、反對恐怖主義和處置突發(fā)事件的重要力量，要求在事發(fā)地域能夠快速、有效地建立起應急通信保障平臺。本文在AODV路由協(xié)議的基礎上，提出了一種改進(jìn)的AODV路由協(xié)議，目的在于均衡網(wǎng)絡(luò )中每個(gè)節點(diǎn)的負載，提高網(wǎng)路的生存時(shí)間。

2.Ad hoc路由協(xié)議

目前針對Ad Hoc網(wǎng)絡(luò )提出的路由協(xié)議可以分為表驅動(dòng)(table driven)路由和按需路由(demand based)兩大類(lèi)。

表驅動(dòng)路由協(xié)議又稱(chēng)為先應式(proactive)路由協(xié)議，它的目的是為網(wǎng)絡(luò )中的每一個(gè)節點(diǎn)維護到所有其它節點(diǎn)的一致和最新的路由信息，因而要求每個(gè)節點(diǎn)維護一個(gè)或多個(gè)路由表來(lái)保存這些信息。當網(wǎng)絡(luò )拓撲發(fā)生變化(事件驅動(dòng))時(shí)，相關(guān)的節點(diǎn)在整個(gè)網(wǎng)絡(luò )中發(fā)布更新信息，來(lái)確保路由信息的一致性。此外，即使網(wǎng)絡(luò )拓撲沒(méi)有發(fā)生變化，每個(gè)節點(diǎn)也需要周期性地(時(shí)間驅動(dòng))廣播它的路由表。表驅動(dòng)路由協(xié)議的優(yōu)點(diǎn)是它減少了節點(diǎn)獲得路由的延遲，使源節點(diǎn)能夠立即判斷目的節點(diǎn)的可達性，缺點(diǎn)是消耗了較多的網(wǎng)絡(luò )資源，并且耗費了一些資源來(lái)建立和重建那些根本沒(méi)有被使用的路由。主要的表驅動(dòng)協(xié)議有：DSDV、WRP、CGSR、OLSR、FSR.

按需路由協(xié)議又稱(chēng)為需求驅動(dòng)(demanddriven)或反應式(reactive)路由協(xié)議。

當采用這種路由協(xié)議時(shí)，源節點(diǎn)只有在需要建立一條到達目的節點(diǎn)的路由時(shí)，才產(chǎn)生一個(gè)路由發(fā)現過(guò)程來(lái)建立相應的路由。建立了路由后，源節點(diǎn)產(chǎn)生一個(gè)路由維護過(guò)程來(lái)維護該路由，直到到目的端的每一條路由都不可達或者不再需要該路由時(shí)。按需路由的優(yōu)點(diǎn)是不需要花費資源來(lái)維護無(wú)用的路由，但路由發(fā)現過(guò)程的費用比較昂貴，而且源節點(diǎn)事先無(wú)法預測能否發(fā)現到目的節點(diǎn)的路由，此外發(fā)現路由的延遲與表驅動(dòng)路由協(xié)議中確定的查表時(shí)間相比，也是不可預測的。

3.改進(jìn)的AODV路由協(xié)議

3.1 AODV路由協(xié)議

AODV是一種按需的距離向量路由協(xié)議，它不僅具有按需路由協(xié)議的特點(diǎn)，即網(wǎng)絡(luò )中的每個(gè)節點(diǎn)只在需要進(jìn)行通信時(shí)才建立路由，而不用周期性的交換路由信息來(lái)獲得到網(wǎng)絡(luò )其它節點(diǎn)的路由信息;還具有距離向量路由協(xié)議的特性，即各個(gè)節點(diǎn)的路由表只維護本節點(diǎn)到其它節點(diǎn)的路由，而無(wú)需掌握全網(wǎng)拓撲結構。

AODV協(xié)議中有五類(lèi)控制消息：路由查詢(xún)消息(RREQ)、路由回復消息(RREP)、路由錯誤消息(RERR)、RREP應答消息(RREPACK)、HELLO消息。RREO消息主要用于節點(diǎn)在進(jìn)行路由查詢(xún)時(shí)向鄰居節點(diǎn)發(fā)送的消息，該消息的發(fā)送以廣播的方式實(shí)現;RREP消息由目的節點(diǎn)或具有最新有效路由的中間節點(diǎn)發(fā)出，用于告知源節點(diǎn)通往目的節點(diǎn)的路由;RERR消息由檢測到路由失效的節點(diǎn)發(fā)出，用于通知所有使用失效路由的節點(diǎn)，使這些節點(diǎn)能夠及時(shí)的尋找新的路由;RREPACK由源節點(diǎn)應目的節點(diǎn)的要求發(fā)出，主要用于應答目的節點(diǎn)的RREP消息;HELLO消息是一類(lèi)特殊的RREP消息，該消息用于節點(diǎn)保持和鄰居節點(diǎn)之間的有效鏈路。

AODV協(xié)議中規定節點(diǎn)保存的數據結構主要有：路由表、先驅表、單向鏈路黑名單(black list)。路由表中保存節點(diǎn)到每一個(gè)目的節點(diǎn)的路由。先驅表用來(lái)保存使用相對應的路由的所有鄰居節點(diǎn)，使得一旦出現鏈路失效，本節點(diǎn)能夠快速的通知到相關(guān)的鄰居節點(diǎn)。單向鏈路黑名單主要用于記錄于本節點(diǎn)間存在單向鏈路的上游節點(diǎn)。

3.2 改進(jìn)的AODV路由協(xié)議

在P改進(jìn)AODV協(xié)議中，只更改了RREQ和RREP消息的數據結構，在RREQ和RREP消息中新增了metric(M)項，修改后AODV的RREQ報文格式如表1、表2所示。

當源節點(diǎn)發(fā)起路由請求時(shí)，由于源節點(diǎn)與目的節點(diǎn)肯定會(huì )存在于鏈路中，故它們的metric值不作為路徑選擇因子，將RREQ中metric值置0,然后進(jìn)行廣播。中間節點(diǎn)收到RREQ后，根據節點(diǎn)的m值以及是否有目的節點(diǎn)的路由信息，決定該節點(diǎn)是否可以作為中間節點(diǎn)。節點(diǎn)有三種狀態(tài)：癱瘓、擁塞、正常。網(wǎng)絡(luò )中每個(gè)節點(diǎn)可根據其負載狀況和可用能量決定轉發(fā)或丟棄收到的RREQ分組。

當一個(gè)中間節點(diǎn)處于“癱瘓”狀態(tài)時(shí)，除非它是該鏈路的目的節點(diǎn)，否則將不處理任何路由請求，丟棄所有收到的RREQ,使其不能再成為中間節點(diǎn)。當節點(diǎn)處于“擁塞”狀態(tài)時(shí)，只有當它是該鏈路的目的節點(diǎn)或者其路由表中已經(jīng)存在了目的節點(diǎn)的路由信息，才會(huì )回復其路由請求，否則將丟棄該路由請求，以此來(lái)減少由于RREQ廣播造成的網(wǎng)絡(luò )負載和降低路由發(fā)現的端到端時(shí)延。當節點(diǎn)處于“正?！睜顟B(tài)時(shí)，首先判斷它是否該路由的目的節點(diǎn)或路由表中存在目的節點(diǎn)的路由信息。若是則回復RREP,若否，則比較節點(diǎn)md值與RREQ中的metric值，若md值大，則更新metric值，轉發(fā)該RREQ包，若metric值大，則直接轉發(fā)RREQ.如果是重復收到RREQ,則按前段所述處理。處理流程如圖1所示。