一種基于AODV的改進(jìn)協(xié)議的能量?jī)?yōu)化方案

方勝吉，李廣慶，黃 巖

吉林醫(yī)藥學(xué)院計(jì)算機(jī)教研室，吉林吉林 132013

0 引言

AdHoc 網(wǎng)絡(luò)中的節(jié)點(diǎn)具有移動(dòng)性、多跳性及臨時(shí)性，并且節(jié)點(diǎn)本身是由電池供電，這就限制了AdHoc 網(wǎng)絡(luò)的持續(xù)時(shí)間。當(dāng)部分網(wǎng)絡(luò)節(jié)點(diǎn)沒有能量時(shí)將會(huì)給網(wǎng)絡(luò)的整體性能帶來嚴(yán)重影響。所以，AdHoc 的能量問題廣受關(guān)注。

AODV 協(xié)議是一個(gè)建立在DSR 和DSDV 基礎(chǔ)上的按需路由協(xié)議，分別借鑒了DSDV 的目的節(jié)點(diǎn)序列號(hào)及DSR 的路由發(fā)現(xiàn)的思想。相比之下，AODV 協(xié)議有著更好的可擴(kuò)展性，更適合在移動(dòng)性強(qiáng)、負(fù)載高的網(wǎng)絡(luò)環(huán)境中使用。針對(duì)AODV 協(xié)議中移動(dòng)節(jié)點(diǎn)能耗不均衡，結(jié)合AdHoc 網(wǎng)絡(luò)節(jié)點(diǎn)密度與能耗的關(guān)系，本文提出一種基于AODV 協(xié)議的改進(jìn)協(xié)議能量?jī)?yōu)化方案。

1 AODV 協(xié)議詳述

AODV 協(xié)議具體通過路由發(fā)現(xiàn)和路由維護(hù)兩個(gè)過程實(shí)現(xiàn)的。

1）路由發(fā)現(xiàn)過程：AODV 協(xié)議中，當(dāng)源節(jié)點(diǎn)需要與某個(gè)節(jié)點(diǎn)通信，并且未包含該點(diǎn)的路由信息時(shí)，會(huì)向所有相鄰節(jié)點(diǎn)發(fā)送RREQ 分組，路由發(fā)現(xiàn)過程開始。相鄰節(jié)點(diǎn)首先確認(rèn)RREQ 分組是否來自自身以及之前是否收到過該分組信息，如果是則直接丟棄，否則會(huì)發(fā)送該RREQ 分組并建立反向路由。

在RREP 分組沿著反向路徑傳到源節(jié)點(diǎn)的過程中，中間節(jié)點(diǎn)都會(huì)刷新節(jié)點(diǎn)信息、生存時(shí)間和節(jié)點(diǎn)序號(hào)，其它反向路由會(huì)因超時(shí)而自動(dòng)刪除。當(dāng)源節(jié)點(diǎn)收到RREP 分組時(shí)，路由發(fā)現(xiàn)過程結(jié)束；

2） 路由維護(hù)過程： AODV 協(xié)議只維護(hù)處于活動(dòng)狀態(tài)的路由。AdHoc 網(wǎng)絡(luò)中，當(dāng)處于通信狀態(tài)的源節(jié)點(diǎn)移動(dòng)到鄰節(jié)點(diǎn)通訊范圍外，鏈路就會(huì)中斷，源節(jié)點(diǎn)需重發(fā)路由請(qǐng)求，在活動(dòng)路由上的中間節(jié)點(diǎn)一旦發(fā)現(xiàn)其到下一跳鄰節(jié)點(diǎn)的鏈路中斷，便會(huì)向其上端活躍節(jié)點(diǎn)發(fā)送RERR 分組。當(dāng)源節(jié)點(diǎn)收到RERR 分組后，如果仍要與目的節(jié)點(diǎn)通信，則需重新發(fā)起路由發(fā)現(xiàn)過程。

3 Pro-AODV 協(xié)議

Pro-AODV 協(xié)議繼承了AODV 協(xié)議的按需特性，既節(jié)點(diǎn)只在有數(shù)據(jù)發(fā)送時(shí)才建立路由，更新路由表及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；Pro-AODV 協(xié)議的路由發(fā)現(xiàn)過程會(huì)盡量避免電量低的節(jié)點(diǎn)，選擇電量高的節(jié)點(diǎn)參加數(shù)據(jù)的轉(zhuǎn)發(fā)。與只將最小跳數(shù)作為衡量標(biāo)準(zhǔn)來選擇和維護(hù)路由信息的協(xié)議不同，Pro-AODV 協(xié)議同時(shí)考慮到了路徑整體上的能耗，與AODV 協(xié)議相比，路由維護(hù)過程不光在鏈路中斷的情況下進(jìn)行，當(dāng)偵測(cè)到路由鏈路上某個(gè)中間節(jié)點(diǎn)的剩余電量低于預(yù)設(shè)的門限值時(shí)，也會(huì)發(fā)起路由維護(hù)過程。

Pro-AODV 協(xié)議將路由的代價(jià)定義為了路徑上最大獨(dú)立節(jié)點(diǎn)剩余電量代價(jià)與路徑跳數(shù)的乘積。“式1”為路由代價(jià)的表達(dá)式 ：

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

4 Pro-AODV 協(xié)議分組格式改進(jìn)

為了實(shí)現(xiàn)Pro-AODV 協(xié)議，需對(duì)AODV 協(xié)議中的RREQ、RREP 分組進(jìn)行擴(kuò)充，擴(kuò)充的RREQ 是在原有結(jié)構(gòu)上增加一個(gè)16bit 的REQMK 字段用于記錄源節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最大剩余電池能量代價(jià)，擴(kuò)充的RREP 是在原有結(jié)構(gòu)上增加一個(gè)16 位的REPMK 用于記錄目的節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最大剩余電池能量代價(jià)。

5 Pro-AODV 協(xié)議操作過程

1）RREQ 分組的產(chǎn)生：與AODV 協(xié)議相同，在源節(jié)點(diǎn)發(fā)起路由發(fā)現(xiàn)過程時(shí)，會(huì)廣播一條RREQ 分組。區(qū)別是，Pro-AODV協(xié)議要對(duì)RREQ 分組中新增的REQMK 域進(jìn)行設(shè)置，其初始值為0，表示RREQ 分組剛從源節(jié)點(diǎn)發(fā)出；

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

3）RREP 分組的產(chǎn)生：以下兩種情況會(huì)產(chǎn)生RREP 分組：

（1） 在目的節(jié)點(diǎn)收到RREQ 分組后產(chǎn)生；與AODV 協(xié)議對(duì)收到的第一個(gè)RREQ 分組直接進(jìn)行回復(fù)不同，Pro-AODV 協(xié)議中，目的節(jié)點(diǎn)每收到一個(gè)RREQ 分組都會(huì)立即沿著RREQ 分組傳遞的路徑向源節(jié)點(diǎn)回復(fù)一個(gè)RREP 分組，這就會(huì)造成源節(jié)點(diǎn)先后可能收到多個(gè)RREP 分組的情況。此時(shí)，源節(jié)點(diǎn)會(huì)對(duì)比先后收到的多個(gè)RREP 分組，根據(jù)分組中攜帶的信息選出較優(yōu)的一條路徑作為數(shù)據(jù)傳輸?shù)穆酚伞ＥcAODV 協(xié)議不同，目的節(jié)點(diǎn)回復(fù)的RREP 分組中還需將REPMK 域的內(nèi)容置為0，表示該RREP 分組是由目標(biāo)節(jié)點(diǎn)發(fā)送的；

（2）中間節(jié)點(diǎn)接收RREQ 分組后產(chǎn)生：收到RREQ 分組后，它首先會(huì)判斷自身剩余電池能量與門限值Threshold 的大小關(guān)系。若小于門限值，則直接丟棄該RREQ 分組，反之則回復(fù)RREP 分組。

4）RREP 分組的接收與轉(zhuǎn)發(fā)：當(dāng)節(jié)點(diǎn)收到RREP 分組后， Pro-AODV 協(xié)議首先會(huì)根據(jù)RREP 分組中目的節(jié)點(diǎn)序列號(hào)與路由表?xiàng)l目中相應(yīng)序列號(hào)的大小關(guān)系決定是否更新路由表的條目：若兩者相等，會(huì)通過RREP 分組中REPMK 內(nèi)容與轉(zhuǎn)發(fā)跳數(shù)內(nèi)容的乘積來計(jì)算路由代價(jià)，對(duì)比后將相應(yīng)路由表?xiàng)l目更新為較小的。若以上比較都相同，最后會(huì)判斷RREP 分組與路由表?xiàng)l目中路由跳數(shù)的大小，將路由表?xiàng)l目中的跳數(shù)更新為小的一項(xiàng)。當(dāng)某一中間節(jié)點(diǎn)的正向路由建立或更新好后，會(huì)通過反向路由回傳RREP 分組。

6 結(jié)論

本文首先介紹了Ad Hoc 網(wǎng)絡(luò)節(jié)點(diǎn)密度對(duì)網(wǎng)絡(luò)能耗的影響。然后介紹了一種基于AODV 協(xié)議的路由改進(jìn)協(xié)議——Pro-AODV協(xié)議。新協(xié)議改進(jìn)了AODV 協(xié)議中的分組結(jié)構(gòu)、路由發(fā)現(xiàn)及路由維護(hù)過程，縮減移動(dòng)網(wǎng)絡(luò)節(jié)點(diǎn)的能耗，延長(zhǎng)其生存時(shí)間，提高網(wǎng)絡(luò)的壽命。

[1]曾靜.移動(dòng)Ad hoe多播中的節(jié)能技術(shù)研究[D].吉林大學(xué)，2007，3.

[2]趙迪.Ad Hoc網(wǎng)絡(luò)路由協(xié)議性能研究與AODV協(xié)議的優(yōu)化[D].西南交通大學(xué)，2009.

[3]張學(xué)，陸桑璐，陳貴海，等.無線傳感器網(wǎng)絡(luò)的拓?fù)淇刂芠J].軟件學(xué)報(bào)，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]路綱，周明天，牛新征，等.無線網(wǎng)絡(luò)鄰近圖綜述[J]. 軟件學(xué)報(bào)，2008，19(4)：888-911.