一種基于AODV的改進協議的能量優化方案

方勝吉，李廣慶，黃 巖

吉林醫藥學院計算機教研室，吉林吉林 132013

0 引言

AdHoc 網絡中的節點具有移動性、多跳性及臨時性，并且節點本身是由電池供電，這就限制了AdHoc 網絡的持續時間。當部分網絡節點沒有能量時將會給網絡的整體性能帶來嚴重影響。所以，AdHoc 的能量問題廣受關注。

AODV 協議是一個建立在DSR 和DSDV 基礎上的按需路由協議，分別借鑒了DSDV 的目的節點序列號及DSR 的路由發現的思想。相比之下，AODV 協議有著更好的可擴展性，更適合在移動性強、負載高的網絡環境中使用。針對AODV 協議中移動節點能耗不均衡，結合AdHoc 網絡節點密度與能耗的關系，本文提出一種基于AODV 協議的改進協議能量優化方案。

1 AODV 協議詳述

AODV 協議具體通過路由發現和路由維護兩個過程實現的。

1）路由發現過程：AODV 協議中，當源節點需要與某個節點通信，并且未包含該點的路由信息時，會向所有相鄰節點發送RREQ 分組，路由發現過程開始。相鄰節點首先確認RREQ 分組是否來自自身以及之前是否收到過該分組信息，如果是則直接丟棄，否則會發送該RREQ 分組并建立反向路由。

在RREP 分組沿著反向路徑傳到源節點的過程中，中間節點都會刷新節點信息、生存時間和節點序號，其它反向路由會因超時而自動刪除。當源節點收到RREP 分組時，路由發現過程結束；

2） 路由維護過程： AODV 協議只維護處于活動狀態的路由。AdHoc 網絡中，當處于通信狀態的源節點移動到鄰節點通訊范圍外，鏈路就會中斷，源節點需重發路由請求，在活動路由上的中間節點一旦發現其到下一跳鄰節點的鏈路中斷，便會向其上端活躍節點發送RERR 分組。當源節點收到RERR 分組后，如果仍要與目的節點通信，則需重新發起路由發現過程。

3 Pro-AODV 協議

Pro-AODV 協議繼承了AODV 協議的按需特性，既節點只在有數據發送時才建立路由，更新路由表及網絡拓撲結構；Pro-AODV 協議的路由發現過程會盡量避免電量低的節點，選擇電量高的節點參加數據的轉發。與只將最小跳數作為衡量標準來選擇和維護路由信息的協議不同，Pro-AODV 協議同時考慮到了路徑整體上的能耗，與AODV 協議相比，路由維護過程不光在鏈路中斷的情況下進行，當偵測到路由鏈路上某個中間節點的剩余電量低于預設的門限值時，也會發起路由維護過程。

Pro-AODV 協議將路由的代價定義為了路徑上最大獨立節點剩余電量代價與路徑跳數的乘積。“式1”為路由代價的表達式 ：

其中L 為從源節點到目的節點的某條路由，hc 表示轉發跳數，i 表示中間節點，ci 表示i 點剩余電量代價。其中ci 并非節點剩余電量的倒數，而是用分段函數表示，如“式2”，式中E 為節點初始能量值，e(i)為節點剩余電量，Threshold 為節點剩余電量的門限值。初始階段，網絡中節點剩余電量很高，Pro-AODV 協議與AODV 協議的路由選擇方式相同，這樣做可保持網絡中各節點結余能量的均衡使用。

4 Pro-AODV 協議分組格式改進

為了實現Pro-AODV 協議，需對AODV 協議中的RREQ、RREP 分組進行擴充，擴充的RREQ 是在原有結構上增加一個16bit 的REQMK 字段用于記錄源節點到當前節點的最大剩余電池能量代價，擴充的RREP 是在原有結構上增加一個16 位的REPMK 用于記錄目的節點到當前節點的最大剩余電池能量代價。

5 Pro-AODV 協議操作過程

1）RREQ 分組的產生：與AODV 協議相同，在源節點發起路由發現過程時，會廣播一條RREQ 分組。區別是，Pro-AODV協議要對RREQ 分組中新增的REQMK 域進行設置，其初始值為0，表示RREQ 分組剛從源節點發出；

2）RREQ 分組的處理與轉發：首先，在節點的緩沖區中設置一個變量S，節點收到RREQ 分組后，對比S 與接收到相同RREQ 分組的次數，確定該RREQ 分組的處理方法，當S 等于1時，Pro-AODV 協議與AODV 協議對RREQ 分組的處理方式相同；當S 不等于1，且節點接收到相同RREQ 分組次數小于等于S 時，此分組將被后續的過程處理；若收到的RREQ 分組次數大于S，直接丟棄該RREQ 分組。當節點首次接收到RREQ 分組時，首先會將RREQ 消息中攜帶的源節點IP 地址等信息填入自身緩存中，然后根據分組內REQMK 域與跳數域中的信息計算出路由代價，并填入廣播ID 的緩存中[4]。若之后又收到相同且被處理次數小于S 的RREQ 分組，就對其所經歷路由的代價與廣播ID緩存中的路由代價做出對比，然后根據結果做出相應的處理。若RREQ 所經歷路由的代價小于廣播ID 緩存中的路由代價，就更新廣播ID 緩存中的路由代價；反之直接丟棄該RREQ 分組。RREQ 分組被節點接收后，也會與AODV 協議一樣建立反向路由

3）RREP 分組的產生：以下兩種情況會產生RREP 分組：

（1） 在目的節點收到RREQ 分組后產生；與AODV 協議對收到的第一個RREQ 分組直接進行回復不同，Pro-AODV 協議中，目的節點每收到一個RREQ 分組都會立即沿著RREQ 分組傳遞的路徑向源節點回復一個RREP 分組，這就會造成源節點先后可能收到多個RREP 分組的情況。此時，源節點會對比先后收到的多個RREP 分組，根據分組中攜帶的信息選出較優的一條路徑作為數據傳輸的路由。與AODV 協議不同，目的節點回復的RREP 分組中還需將REPMK 域的內容置為0，表示該RREP 分組是由目標節點發送的；

（2）中間節點接收RREQ 分組后產生：收到RREQ 分組后，它首先會判斷自身剩余電池能量與門限值Threshold 的大小關系。若小于門限值，則直接丟棄該RREQ 分組，反之則回復RREP 分組。

4）RREP 分組的接收與轉發：當節點收到RREP 分組后， Pro-AODV 協議首先會根據RREP 分組中目的節點序列號與路由表條目中相應序列號的大小關系決定是否更新路由表的條目：若兩者相等，會通過RREP 分組中REPMK 內容與轉發跳數內容的乘積來計算路由代價，對比后將相應路由表條目更新為較小的。若以上比較都相同，最后會判斷RREP 分組與路由表條目中路由跳數的大小，將路由表條目中的跳數更新為小的一項。當某一中間節點的正向路由建立或更新好后，會通過反向路由回傳RREP 分組。

6 結論

本文首先介紹了Ad Hoc 網絡節點密度對網絡能耗的影響。然后介紹了一種基于AODV 協議的路由改進協議——Pro-AODV協議。新協議改進了AODV 協議中的分組結構、路由發現及路由維護過程，縮減移動網絡節點的能耗，延長其生存時間，提高網絡的壽命。

[1]曾靜.移動Ad hoe多播中的節能技術研究[D].吉林大學，2007，3.

[2]趙迪.Ad Hoc網絡路由協議性能研究與AODV協議的優化[D].西南交通大學，2009.

[3]張學，陸桑璐，陳貴海，等.無線傳感器網絡的拓撲控制[J].軟件學報，2007(4)，18(4)：943-954.

[4]Newman M E J.Random graphs as models of networks//Bornholdt S，Schuster H G eds. Handbook of Graphs and Networks.Berlin： Wiley-VCH，2003：：35-68

[5]路綱，周明天，牛新征，等.無線網絡鄰近圖綜述[J]. 軟件學報，2008，19(4)：888-911.