方勝吉，李廣慶，黃 巖

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

0 引言

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

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

1 AODV 協(xié)議詳述

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

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

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

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

3 Pro-AODV 協(xié)議

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)論

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

[1]曾靜.移動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é)報，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é)報，2008，19(4)：888-911.