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

1.引言

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

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

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

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

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

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

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

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

3.1 AODV路由協(xié)議

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

AODV協(xié)議中有五類控制消息：路由查詢消息(RREQ)、路由回復(fù)消息(RREP)、路由錯誤消息(RERR)、RREP應(yīng)答消息(RREPACK)、HELLO消息。RREO消息主要用于節(jié)點(diǎn)在進(jìn)行路由查詢時向鄰居節(jié)點(diǎn)發(fā)送的消息，該消息的發(fā)送以廣播的方式實(shí)現(xiàn);RREP消息由目的節(jié)點(diǎn)或具有最新有效路由的中間節(jié)點(diǎn)發(fā)出，用于告知源節(jié)點(diǎn)通往目的節(jié)點(diǎn)的路由;RERR消息由檢測到路由失效的節(jié)點(diǎn)發(fā)出，用于通知所有使用失效路由的節(jié)點(diǎn)，使這些節(jié)點(diǎn)能夠及時的尋找新的路由;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)到每一個目的節(jié)點(diǎn)的路由。先驅(qū)表用來保存使用相對應(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ā)起路由請求時，由于源節(jié)點(diǎn)與目的節(jié)點(diǎn)肯定會存在于鏈路中，故它們的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ò)中每個節(jié)點(diǎn)可根據(jù)其負(fù)載狀況和可用能量決定轉(zhuǎn)發(fā)或丟棄收到的RREQ分組。

當(dāng)一個中間節(jié)點(diǎn)處于“癱瘓”狀態(tài)時，除非它是該鏈路的目的節(jié)點(diǎn)，否則將不處理任何路由請求，丟棄所有收到的RREQ,使其不能再成為中間節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)處于“擁塞”狀態(tài)時，只有當(dāng)它是該鏈路的目的節(jié)點(diǎn)或者其路由表中已經(jīng)存在了目的節(jié)點(diǎn)的路由信息，才會回復(fù)其路由請求，否則將丟棄該路由請求，以此來減少由于RREQ廣播造成的網(wǎng)絡(luò)負(fù)載和降低路由發(fā)現(xiàn)的端到端時延。當(dāng)節(jié)點(diǎn)處于“正常”狀態(tài)時，首先判斷它是否該路由的目的節(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)是由美國加州大學(xué)伯克利分校(UniversityofCalifornia,Berkley)開發(fā)的一種免費(fèi)、公開源代碼的網(wǎng)絡(luò)模擬軟件，其本質(zhì)上是一個面向?qū)ο蟮?、由離散事件驅(qū)動的網(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時，AODV和PS-AODV的分組傳送率下降不明顯，差距不大，但隨著負(fù)載增加，兩者的分組傳送率都急劇下降，但PS-AODV的下降幅度比AODV小。當(dāng)負(fù)載達(dá)到1440kb/s時，PS-AODV的分組傳送率比AODV高7%.圖3隨著網(wǎng)絡(luò)負(fù)載增加，兩者的平均端到端時延開始上升，PS-AODV的平均端到端時延總體低于AODV,當(dāng)負(fù)載達(dá)到1440kb/s時，PS-AODV比AODV的平均端到端時延低了240ms,該圖反映出PSAODV比AODV擁有更低的平均端到端時延。圖4隨著網(wǎng)絡(luò)負(fù)載增加，數(shù)據(jù)分組所占比例不斷提高，兩者的路由開銷降低。PS-AODV的路由開銷總體低于AODV,當(dāng)負(fù)載為1120kb/s時兩者差距達(dá)到最高的0.9.圖5顯示了在節(jié)點(diǎn)以5m/s速度隨機(jī)運(yùn)動的條件下，網(wǎng)絡(luò)生存時間隨網(wǎng)絡(luò)負(fù)載變化情況，在此項(xiàng)分析中，選用第一個節(jié)點(diǎn)與第n/2個節(jié)點(diǎn)死亡時間的中值作為網(wǎng)絡(luò)生存時間，這是因?yàn)楫?dāng)網(wǎng)絡(luò)中第n/2個節(jié)點(diǎn)死亡以后，整個網(wǎng)絡(luò)將會急劇惡化，失去其使用價值。當(dāng)網(wǎng)絡(luò)負(fù)載增加時，PS-AODV和AODV的網(wǎng)絡(luò)生存時間都降低，PS-AODV的網(wǎng)絡(luò)生存時間要長于AODV,這主要由于PS-AODV會根據(jù)節(jié)點(diǎn)負(fù)載情況選擇負(fù)載更小的節(jié)點(diǎn)，使整個網(wǎng)絡(luò)的能量消耗更加均衡，避免了網(wǎng)絡(luò)中心的節(jié)點(diǎn)過早耗盡的能量，從而延長了網(wǎng)絡(luò)的生存時間。

5.結(jié)束語

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