摘 要:在Ad Hoc網(wǎng)絡(luò)中AODV路由協(xié)議是一個(gè)比較成熟且廣泛接收的路由協(xié)議，具有較低的內(nèi)存和處理開(kāi)銷(xiāo)，實(shí)現(xiàn)簡(jiǎn)單，但是AODV協(xié)議在能量和負(fù)載方面卻存在著很大問(wèn)題;針對(duì)這個(gè)問(wèn)題提出無(wú)線Ad Hoc網(wǎng)絡(luò)中基于AODV路由協(xié)議的能量和負(fù)載均衡的B-AODV協(xié)議。B-AODV協(xié)議考慮了節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)的已使用緩沖區(qū)大小兩個(gè)度量，使之支持能量均衡和負(fù)載均衡，仿真結(jié)果表明B-AODV協(xié)議有效地均衡了AODV路由協(xié)議的能量消耗和節(jié)點(diǎn)的負(fù)載，延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間，提高了包的傳輸率，充分利用了網(wǎng)絡(luò)資源。

關(guān)鍵詞:Ad Hoc網(wǎng)絡(luò); AODV協(xié)議; 能量消耗; 負(fù)載均衡; B-AODV協(xié)議

中圖分類(lèi)號(hào):TN915文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1004-373X(2010)15-0080-02

Improvement of AODV Routing Protocol Based on Energy and Load Balancing

MAO Xi-long1， FENG Chao1，2 ， PENG Zhang-xing3

(1.College of Computer Science， National University of Defense Technology， Changsha 410073， China;

2.CAPF Guangzhou Commanding Academy， Guangzhou 510440， China; 3.Navy Unit No.92155， Sanya 572021， China)

Abstract: AODV (Ad hoc On-Demand Distance Vector) routing protocol with small memory and low processing overhead is a mature and wide rang protocol in Ad Hoc networks. A B-AODV protocol based on AODV routing protocol in wireless Ad Hoc is proposed for solving the problems about energy consumption and load balancing of AODV protocol. To address those issues， B-AODV protocol considered the residual energy and buffer capacity of each node. The simulation results show that B-AODV can efficiently improve the energy consumption and load balancing， and extend the whole network's survive time.

Keywords: Ad Hoc network;AODV protocol;energy consumption; load balancing; B-AODV protocol

收稿日期:2010-03-19

無(wú)線Ad Hoc[1]網(wǎng)絡(luò)是指一組帶有無(wú)線收發(fā)裝置的移動(dòng)節(jié)點(diǎn)組成的一個(gè)多跳的臨時(shí)性的自治系統(tǒng)。整個(gè)網(wǎng)絡(luò)沒(méi)有固定的基礎(chǔ)設(shè)施，也沒(méi)有固定的路由器，所有節(jié)點(diǎn)都是移動(dòng)的，并且都可以以任何方式動(dòng)態(tài)地保持與其他節(jié)點(diǎn)的聯(lián)系，廣泛應(yīng)用于軍事領(lǐng)域、自然災(zāi)害、緊急通信等領(lǐng)域。在Ad Hoc網(wǎng)絡(luò)中AODV路由協(xié)議[2]是一個(gè)比較成熟且廣泛接收的路由協(xié)議，具有較低的內(nèi)存和處理開(kāi)銷(xiāo)，實(shí)現(xiàn)簡(jiǎn)單。本文考慮了節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)的已使用緩沖區(qū)大小兩個(gè)度量，提出了基于AODV路由協(xié)議的能量和負(fù)載均衡的B-AODV協(xié)議，B-AODV協(xié)議有效地降低并均衡了AODV路由協(xié)議的能量消耗和負(fù)載均衡，延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間，提高了包的傳輸率，充分利用了網(wǎng)絡(luò)資源。

1 AODV路由協(xié)議簡(jiǎn)介

AODV(Ad Hoc on Demand Distance Vector)協(xié)議實(shí)質(zhì)上就是DSR[3]和DSDV[4]的綜合。在AODV算法中，為找到通往目的節(jié)點(diǎn)的路由，源節(jié)點(diǎn)將廣播一個(gè)路由請(qǐng)求分組RREQ，收到RREQ的中間節(jié)點(diǎn)根據(jù)RREQ中的消息，建立到源節(jié)點(diǎn)的路由，在路由表增加一個(gè)路由條目，稱(chēng)為“反向路由”，然后它再向周?chē)?jié)點(diǎn)廣播此分組。如果目的節(jié)點(diǎn)收到RREQ則向源節(jié)點(diǎn)回復(fù)路由應(yīng)答分組RREP，RREP沿著剛剛建立的反向路由向源節(jié)點(diǎn)傳送，在此過(guò)程中，收到RREP的節(jié)點(diǎn)建立到目的節(jié)點(diǎn)的路由，在路由表中增加一個(gè)路由條目，稱(chēng)為“正向路由”。正向路由條目的目的節(jié)點(diǎn)是RREP的源節(jié)點(diǎn)，下一跳將是RREP發(fā)送給本節(jié)點(diǎn)的鄰節(jié)點(diǎn)。

當(dāng)一個(gè)節(jié)點(diǎn)檢測(cè)到其到鄰居節(jié)點(diǎn)的路由不再有效時(shí)，觸發(fā)路由維護(hù)過(guò)程。它要?jiǎng)h除路由表中的該路由表項(xiàng)，發(fā)送一個(gè)鏈路失敗消息，這時(shí)，一個(gè)路由應(yīng)答消息通知正在使用該路由的鄰居節(jié)點(diǎn)該路由不可用。接收到該消息的鄰居節(jié)點(diǎn)也要重復(fù)上述過(guò)程，直到到達(dá)該消息的源節(jié)點(diǎn)。源節(jié)點(diǎn)可以選擇終止數(shù)據(jù)發(fā)送或通過(guò)發(fā)送一個(gè)新的RREQ來(lái)發(fā)現(xiàn)新路由。

2 B-AODV路由協(xié)議

在改進(jìn)的AODV協(xié)議中，發(fā)現(xiàn)和維護(hù)進(jìn)程使用了兩個(gè)度量，這兩個(gè)度量根據(jù)每個(gè)節(jié)點(diǎn)上保留的本地信息來(lái)更新。節(jié)點(diǎn)剩余能量是通過(guò)計(jì)算節(jié)點(diǎn)剩余電池能量來(lái)計(jì)算的，節(jié)點(diǎn)的負(fù)載是根據(jù)它的發(fā)送緩存區(qū)的被占用大小來(lái)表示。根據(jù)文獻(xiàn)[5]定義綜合評(píng)價(jià)指標(biāo)，即一條路徑的開(kāi)銷(xiāo)函數(shù)由式(1)給出:

f(P)=w0POWER+1+w1BUF

(1)

式中:POWER是節(jié)點(diǎn)的剩余電量值;BUF是已使用緩存區(qū)大小值;w0，w1為一組權(quán)值，滿(mǎn)足w0+w1=l。式(1)為一條路徑的綜合評(píng)價(jià)指標(biāo)，其中節(jié)點(diǎn)的剩余電量屬于加法尺度，節(jié)點(diǎn)的已使用緩存區(qū)大小符合凹性尺度[6]。因此對(duì)于路徑P=(i，j，k，…，l，m):

POWER(P)=POWER(i，j)+POWER(j，k)+

…+POWER(l，m)

(2)

BUF(P)=max{BUF(i，j)，BUF(j，k)，…，BUF(l，m)}

(3)

分項(xiàng)值加1是為了防止POWER為0。

由綜合評(píng)價(jià)指標(biāo)可知，若相同的源節(jié)點(diǎn)、目的節(jié)點(diǎn)對(duì)之間存在兩條路徑P1和P2，若f(P1)

B-AODV協(xié)議與AODV協(xié)議的區(qū)別與改進(jìn)在于路由的發(fā)現(xiàn)過(guò)程。在路由的請(qǐng)求報(bào)文RREQ中增加了新域:節(jié)點(diǎn)剩余能量及已使用緩存區(qū)大小。節(jié)點(diǎn)的剩余能量用節(jié)點(diǎn)電池剩余壽命來(lái)表示，節(jié)點(diǎn)的電池剩余壽命由文獻(xiàn)[7]中的解釋來(lái)衡量。

當(dāng)某一源節(jié)點(diǎn)向某一目標(biāo)節(jié)點(diǎn)發(fā)送分組時(shí)，如果路由緩存區(qū)中沒(méi)有可用的路徑，則節(jié)點(diǎn)將啟動(dòng)路由發(fā)現(xiàn)過(guò)程，發(fā)送路由請(qǐng)求分組(RREQ)。發(fā)送的RREQ分組中包含源節(jié)點(diǎn)本身的節(jié)點(diǎn)剩余能量和緩存區(qū)大小的值，當(dāng)其他節(jié)點(diǎn)接收到RREQ分組時(shí)，如果它不是路由發(fā)現(xiàn)的目標(biāo)，這時(shí)即便該節(jié)點(diǎn)擁有到達(dá)目標(biāo)節(jié)點(diǎn)的路由，也不向源節(jié)點(diǎn)發(fā)送RREP分組，而是將本節(jié)點(diǎn)的節(jié)點(diǎn)剩余能量和緩存區(qū)大小的值加入RREQ分組中的節(jié)點(diǎn)剩余能量及已使用緩存區(qū)大小域中，然后轉(zhuǎn)發(fā)此RREQ分組，在RREQ分組到達(dá)目的節(jié)點(diǎn)后，目的節(jié)點(diǎn)不會(huì)立即回復(fù)路由應(yīng)答分組RREP，而是等待3*NODE_TRAVERAL_TIME時(shí)間，接收從別的路徑傳遞給此節(jié)點(diǎn)的其他RREQ，比較接收到的各RREQ中的f(P)值，目的節(jié)點(diǎn)沿著f(P)值最小的RREQ分組到達(dá)的相反路徑單播RREP分組。

B-AODV協(xié)議的路由維護(hù)過(guò)程和AODV協(xié)議的路由維護(hù)[8]過(guò)程一樣，都采用源節(jié)點(diǎn)路由重建和本地修復(fù)兩種維護(hù)方式。

3 仿真結(jié)果及分析

使用Linux系統(tǒng)下NS 2[9]來(lái)模擬網(wǎng)絡(luò)環(huán)境，把B-AODV和AODV進(jìn)行對(duì)比分析。仿真網(wǎng)絡(luò)環(huán)境:拓?fù)浣Y(jié)構(gòu):600 m×600 m;節(jié)點(diǎn)數(shù)目:50;節(jié)點(diǎn)最快移動(dòng)速度:20 m/s;模擬時(shí)間:200 s;節(jié)點(diǎn)功率范圍:250 m;節(jié)點(diǎn)的初始能量10 J;發(fā)送功率600 mW。

圖1比較了B-AODV和AODV耗盡能量的節(jié)點(diǎn)數(shù)。起初每個(gè)節(jié)點(diǎn)的能量都是滿(mǎn)的，但隨著模擬時(shí)間的延長(zhǎng)，B-AODV和AODV路由協(xié)議中死亡節(jié)點(diǎn)數(shù)都急劇地增加，原因是隨著死亡節(jié)點(diǎn)的增加，未死亡節(jié)點(diǎn)有更大的分組傳輸負(fù)荷，導(dǎo)致消耗更多的能量，從而加速了節(jié)點(diǎn)能量的消耗。隨著時(shí)間的延長(zhǎng)，B-AODV路由協(xié)議和AODV路由協(xié)議的死亡節(jié)點(diǎn)數(shù)的差距越來(lái)越大，因?yàn)锽-AODV路由協(xié)議能根據(jù)節(jié)點(diǎn)的剩余能量來(lái)選路，平衡了節(jié)點(diǎn)能量的消耗，使耗盡能量的節(jié)點(diǎn)數(shù)降低，從而延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間。

圖1 隨時(shí)間耗盡能量的節(jié)點(diǎn)數(shù)

圖2比較了B-AODV路由協(xié)議和AODV路由協(xié)議的包傳輸率，可以看到B-AODV路由協(xié)議的包傳輸率比AODV的包傳輸率有了很大的提高，原因是隨著模擬時(shí)間的延長(zhǎng)，死亡節(jié)點(diǎn)的增加，其他節(jié)點(diǎn)的傳輸負(fù)荷的加大，導(dǎo)致了丟包率的增加，并最終導(dǎo)致了網(wǎng)絡(luò)分割[10]。B-AODV路由協(xié)議在尋路時(shí)考慮了節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)的已使用緩存區(qū)的大小兩個(gè)度量，相比于AODV路由協(xié)議提高了包的傳輸率。

圖2 傳輸率的比較

4 結(jié) 語(yǔ)

提出一個(gè)基于節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)負(fù)載的AODV路由協(xié)議B-AODV，通過(guò)在路由的請(qǐng)求報(bào)文RREQ中增加新域:節(jié)點(diǎn)剩余能量及已使用緩存區(qū)大小。在RREQ經(jīng)過(guò)的每個(gè)節(jié)點(diǎn)，將節(jié)點(diǎn)的節(jié)點(diǎn)剩余能量和緩存區(qū)大小的值加入RREQ分組中的節(jié)點(diǎn)剩余能量及已使用緩存區(qū)大小域中，然后轉(zhuǎn)發(fā)此RREQ分組，在RREQ

分組到達(dá)目的節(jié)點(diǎn)后，目的節(jié)點(diǎn)需要繼續(xù)等待3*NODE_TRAVERAL_TIME時(shí)間后，接收從別的路徑傳遞給此目的節(jié)點(diǎn)的其他RREQ，再比較接收到的各RREQ中的f(P)值，目的節(jié)點(diǎn)沿著f(P)值最小的RREQ分組到達(dá)的相反路徑單播RREP分組。通過(guò)此方法使得B-AODV支持能量和負(fù)載均衡。通過(guò)NS 2的仿真以及對(duì)仿真結(jié)果的分析得出，B-AODV路由協(xié)議相比于AODV路由協(xié)議在網(wǎng)絡(luò)的生存時(shí)間、包的傳輸率上都得到了提高和改進(jìn)，充分利用了網(wǎng)絡(luò)資源。

參考文獻(xiàn)

[1]陳林星，曾曦，曹毅.移動(dòng)Ad Hoc網(wǎng)絡(luò) [M].北京:電子工業(yè)出版社，2006.

[2]策力木格，胡其吐.基于NS 2的AODV路由協(xié)議的研究[J].內(nèi)蒙古科技與經(jīng)濟(jì)，2005(10): 112-113，175.

[3]孫寶林.無(wú)線移動(dòng)Ad Hoc網(wǎng)絡(luò)的路由技術(shù)研究[J].武漢科技學(xué)院學(xué)報(bào)，2003，16(4):35-39.

[4]趙根喜，張愛(ài)紅，孫偉.Ad Hoc路由協(xié)議綜述[J].內(nèi)蒙古科技與經(jīng)濟(jì)，2003(8):45-54.

[5]CHEN Xue， PENG Ge-xin. Analysis and application ofwireless Ad HOC network multicast protocols[J]. Computer Engineering， 2003(3): 3428-3488.

[6]HONG Xiao-yan， XU Kai-xin， GERLA M. Scalable routing protocols for mobile ad hoc networks[J]. IEEE Network Magazine，2002(7/8): 10-21.

[7]鄭少仁，王海濤，趙志峰，等.Ad Hoc網(wǎng)絡(luò)技術(shù)[M].北京:人民郵電出版社，2005.

[8]梅輝，羅文茂.無(wú)線Ad Hoc網(wǎng)絡(luò)[J].電信技術(shù)，2003，16(6):47-50.

[9]佚名.網(wǎng)絡(luò)仿真器[EB/OL]. [2005-07-25]. http://www.isi.edu/nsnam/ns.

[10]HU Y C， PERRIG A. Ariadne:a secure on-demand routing protocol for Ad Hoc networks[C]//MobiCom′02. Atlanta: [s.n.]， 2002: 23-26.