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

1.引言

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

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

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

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

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

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

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

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

3.1 AODV路由協(xié)議

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

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

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

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

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

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

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