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

1.引言

無(wú)線自組網(wǎng)(Ad Hoc)是由一組帶有無(wú)線通信收發(fā)裝置的移動(dòng)終端節(jié)點(diǎn)組成的一個(gè)多跳、臨時(shí)和無(wú)中心的網(wǎng)絡(luò)，具有不依賴于固定基礎(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)兩大類。

表驅(qū)動(dòng)路由協(xié)議又稱為先應(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ù)浒l(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é)議又稱為需求驅(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é)議中有五類控制消息：路由查詢消息(RREQ)、路由回復(fù)消息(RREP)、路由錯(cuò)誤消息(RERR)、RREP應(yīng)答消息(RREPACK)、HELLO消息。RREO消息主要用于節(jié)點(diǎn)在進(jì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消息是一類特殊的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)處于“正常”狀態(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所示。

4.NS2仿真實(shí)驗(yàn)

NS2[6,7](Network Simulator)是由美國(guó)加州大學(xué)伯克利分校(UniversityofCalifornia,Berkley)開(kāi)發(fā)的一種免費(fèi)、公開(kāi)源代碼的網(wǎng)絡(luò)模擬軟件，其本質(zhì)上是一個(gè)面向?qū)ο蟮?、由離散事件驅(qū)動(dòng)的網(wǎng)絡(luò)模擬器。

仿真參數(shù)如表3所示。

實(shí)驗(yàn)中兩種路由協(xié)議的性能比較如圖2~5,改進(jìn)后的AODV路由協(xié)議為PS-AODV.

圖2隨著網(wǎng)絡(luò)負(fù)載的增加，兩者的分組傳送率都在下降，當(dāng)負(fù)載在0到480kb/s時(shí)，AODV和PS-AODV的分組傳送率下降不明顯，差距不大，但隨著負(fù)載增加，兩者的分組傳送率都急劇下降，但PS-AODV的下降幅度比AODV小。當(dāng)負(fù)載達(dá)到1440kb/s時(shí)，PS-AODV的分組傳送率比AODV高7%.圖3隨著網(wǎng)絡(luò)負(fù)載增加，兩者的平均端到端時(shí)延開(kāi)始上升，PS-AODV的平均端到端時(shí)延總體低于AODV,當(dāng)負(fù)載達(dá)到1440kb/s時(shí)，PS-AODV比AODV的平均端到端時(shí)延低了240ms,該圖反映出PSAODV比AODV擁有更低的平均端到端時(shí)延。圖4隨著網(wǎng)絡(luò)負(fù)載增加，數(shù)據(jù)分組所占比例不斷提高，兩者的路由開(kāi)銷(xiāo)降低。PS-AODV的路由開(kāi)銷(xiāo)總體低于AODV,當(dāng)負(fù)載為1120kb/s時(shí)兩者差距達(dá)到最高的0.9.圖5顯示了在節(jié)點(diǎn)以5m/s速度隨機(jī)運(yùn)動(dòng)的條件下，網(wǎng)絡(luò)生存時(shí)間隨網(wǎng)絡(luò)負(fù)載變化情況，在此項(xiàng)分析中，選用第一個(gè)節(jié)點(diǎn)與第n/2個(gè)節(jié)點(diǎn)死亡時(shí)間的中值作為網(wǎng)絡(luò)生存時(shí)間，這是因?yàn)楫?dāng)網(wǎng)絡(luò)中第n/2個(gè)節(jié)點(diǎn)死亡以后，整個(gè)網(wǎng)絡(luò)將會(huì)急劇惡化，失去其使用價(jià)值。當(dāng)網(wǎng)絡(luò)負(fù)載增加時(shí)，PS-AODV和AODV的網(wǎng)絡(luò)生存時(shí)間都降低，PS-AODV的網(wǎng)絡(luò)生存時(shí)間要長(zhǎng)于AODV,這主要由于PS-AODV會(huì)根據(jù)節(jié)點(diǎn)負(fù)載情況選擇負(fù)載更小的節(jié)點(diǎn)，使整個(gè)網(wǎng)絡(luò)的能量消耗更加均衡，避免了網(wǎng)絡(luò)中心的節(jié)點(diǎn)過(guò)早耗盡的能量，從而延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間。

5.結(jié)束語(yǔ)

本文提出了一種能量均衡的路由協(xié)議PS-AODV.通過(guò)對(duì)該路由協(xié)議的分析和性能仿真，該路由協(xié)議在平均端到端的延遲、平均端到端的吞吐量、網(wǎng)絡(luò)生存時(shí)間、路由開(kāi)銷(xiāo)方面都比已有的經(jīng)典路由協(xié)議如AODV更具優(yōu)越性。筆者將在后續(xù)工作中采用不同的移動(dòng)速度和移動(dòng)模型該路由協(xié)議進(jìn)行性能分析，比較試驗(yàn)結(jié)果。