基于能量和負載均衡的AODV路由協議改進

摘 要:在Ad Hoc網絡中AODV路由協議是一個比較成熟且廣泛接收的路由協議，具有較低的內存和處理開銷，實現簡單，但是AODV協議在能量和負載方面卻存在著很大問題;針對這個問題提出無線Ad Hoc網絡中基于AODV路由協議的能量和負載均衡的B-AODV協議。B-AODV協議考慮了節點的剩余能量和節點的已使用緩沖區大小兩個度量，使之支持能量均衡和負載均衡，仿真結果表明B-AODV協議有效地均衡了AODV路由協議的能量消耗和節點的負載，延長了網絡的生存時間，提高了包的傳輸率，充分利用了網絡資源。

關鍵詞:Ad Hoc網絡; AODV協議; 能量消耗; 負載均衡; B-AODV協議

中圖分類號:TN915文獻標識碼:A

文章編號: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

無線Ad Hoc[1]網絡是指一組帶有無線收發裝置的移動節點組成的一個多跳的臨時性的自治系統。整個網絡沒有固定的基礎設施，也沒有固定的路由器，所有節點都是移動的，并且都可以以任何方式動態地保持與其他節點的聯系，廣泛應用于軍事領域、自然災害、緊急通信等領域。在Ad Hoc網絡中AODV路由協議[2]是一個比較成熟且廣泛接收的路由協議，具有較低的內存和處理開銷，實現簡單。本文考慮了節點的剩余能量和節點的已使用緩沖區大小兩個度量，提出了基于AODV路由協議的能量和負載均衡的B-AODV協議，B-AODV協議有效地降低并均衡了AODV路由協議的能量消耗和負載均衡，延長了網絡的生存時間，提高了包的傳輸率，充分利用了網絡資源。

1 AODV路由協議簡介

AODV(Ad Hoc on Demand Distance Vector)協議實質上就是DSR[3]和DSDV[4]的綜合。在AODV算法中，為找到通往目的節點的路由，源節點將廣播一個路由請求分組RREQ，收到RREQ的中間節點根據RREQ中的消息，建立到源節點的路由，在路由表增加一個路由條目，稱為“反向路由”，然后它再向周圍節點廣播此分組。如果目的節點收到RREQ則向源節點回復路由應答分組RREP，RREP沿著剛剛建立的反向路由向源節點傳送，在此過程中，收到RREP的節點建立到目的節點的路由，在路由表中增加一個路由條目，稱為“正向路由”。正向路由條目的目的節點是RREP的源節點，下一跳將是RREP發送給本節點的鄰節點。

當一個節點檢測到其到鄰居節點的路由不再有效時，觸發路由維護過程。它要刪除路由表中的該路由表項，發送一個鏈路失敗消息，這時，一個路由應答消息通知正在使用該路由的鄰居節點該路由不可用。接收到該消息的鄰居節點也要重復上述過程，直到到達該消息的源節點。源節點可以選擇終止數據發送或通過發送一個新的RREQ來發現新路由。

2 B-AODV路由協議

在改進的AODV協議中，發現和維護進程使用了兩個度量，這兩個度量根據每個節點上保留的本地信息來更新。節點剩余能量是通過計算節點剩余電池能量來計算的，節點的負載是根據它的發送緩存區的被占用大小來表示。根據文獻[5]定義綜合評價指標，即一條路徑的開銷函數由式(1)給出:

f(P)=w0POWER+1+w1BUF

(1)

式中:POWER是節點的剩余電量值;BUF是已使用緩存區大小值;w0，w1為一組權值，滿足w0+w1=l。式(1)為一條路徑的綜合評價指標，其中節點的剩余電量屬于加法尺度，節點的已使用緩存區大小符合凹性尺度[6]。因此對于路徑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)

分項值加1是為了防止POWER為0。

由綜合評價指標可知，若相同的源節點、目的節點對之間存在兩條路徑P1和P2，若f(P1)

B-AODV協議與AODV協議的區別與改進在于路由的發現過程。在路由的請求報文RREQ中增加了新域:節點剩余能量及已使用緩存區大小。節點的剩余能量用節點電池剩余壽命來表示，節點的電池剩余壽命由文獻[7]中的解釋來衡量。

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

B-AODV協議的路由維護過程和AODV協議的路由維護[8]過程一樣，都采用源節點路由重建和本地修復兩種維護方式。

3 仿真結果及分析

使用Linux系統下NS 2[9]來模擬網絡環境，把B-AODV和AODV進行對比分析。仿真網絡環境:拓撲結構:600 m×600 m;節點數目:50;節點最快移動速度:20 m/s;模擬時間:200 s;節點功率范圍:250 m;節點的初始能量10 J;發送功率600 mW。

圖1比較了B-AODV和AODV耗盡能量的節點數。起初每個節點的能量都是滿的，但隨著模擬時間的延長，B-AODV和AODV路由協議中死亡節點數都急劇地增加，原因是隨著死亡節點的增加，未死亡節點有更大的分組傳輸負荷，導致消耗更多的能量，從而加速了節點能量的消耗。隨著時間的延長，B-AODV路由協議和AODV路由協議的死亡節點數的差距越來越大，因為B-AODV路由協議能根據節點的剩余能量來選路，平衡了節點能量的消耗，使耗盡能量的節點數降低，從而延長了網絡的生存時間。

圖1 隨時間耗盡能量的節點數

圖2比較了B-AODV路由協議和AODV路由協議的包傳輸率，可以看到B-AODV路由協議的包傳輸率比AODV的包傳輸率有了很大的提高，原因是隨著模擬時間的延長，死亡節點的增加，其他節點的傳輸負荷的加大，導致了丟包率的增加，并最終導致了網絡分割[10]。B-AODV路由協議在尋路時考慮了節點的剩余能量和節點的已使用緩存區的大小兩個度量，相比于AODV路由協議提高了包的傳輸率。

圖2 傳輸率的比較

4 結 語

提出一個基于節點剩余能量和節點負載的AODV路由協議B-AODV，通過在路由的請求報文RREQ中增加新域:節點剩余能量及已使用緩存區大小。在RREQ經過的每個節點，將節點的節點剩余能量和緩存區大小的值加入RREQ分組中的節點剩余能量及已使用緩存區大小域中，然后轉發此RREQ分組，在RREQ

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

參考文獻

[1]陳林星，曾曦，曹毅.移動Ad Hoc網絡 [M].北京:電子工業出版社，2006.

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

[3]孫寶林.無線移動Ad Hoc網絡的路由技術研究[J].武漢科技學院學報，2003，16(4):35-39.

[4]趙根喜，張愛紅，孫偉.Ad Hoc路由協議綜述[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網絡技術[M].北京:人民郵電出版社，2005.

[8]梅輝，羅文茂.無線Ad Hoc網絡[J].電信技術，2003，16(6):47-50.

[9]佚名.網絡仿真器[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.