基于網(wǎng)絡(luò)均衡的AODV協(xié)議改進(jìn)

張世顯，梁 俊

（空軍工程大學(xué) 電訊工程學(xué)院，西安 710077）

1 AODV路由協(xié)議

AODV路由協(xié)議是在DSDV協(xié)議基礎(chǔ)上結(jié)合類似DSR中的按需路由機(jī)制進(jìn)行改進(jìn)后提出的，既借用了DSR的路由發(fā)現(xiàn)和路由維護(hù)機(jī)制，又利用了DSDV的逐跳路由、順序編號和路由維持階段的周期性更新，還加入了對組播路由QoS的支持，其最顯著的特點是為路由表中每個項都使用了目的序列號，因而還可以避免環(huán)路的發(fā)生，并且很容易編程實現(xiàn)。基于上述優(yōu)點，AODV成為自組網(wǎng)路由協(xié)議研究中的熱點。

當(dāng)源節(jié)點想與另外一個節(jié)點通信，而它的路由表中又沒有相應(yīng)的路由信息時，它就會發(fā)起路由發(fā)現(xiàn)過程，發(fā)送RREQ消息分組。當(dāng)RREQ消息分組從一個源節(jié)點轉(zhuǎn)發(fā)到不同的目的地時，沿途所經(jīng)過的節(jié)點都要自動建立到源節(jié)點的反向路由。節(jié)點通過記錄收到的第一個RREQ分組的鄰居地址來建立反向路由，這些反向路由將會維持一定的時間，該段時間足夠RREQ分組在網(wǎng)內(nèi)轉(zhuǎn)發(fā)以及產(chǎn)生的RREP分組返回源節(jié)點。當(dāng)分組到達(dá)了目的節(jié)點,目的節(jié)點就會產(chǎn)生分組，并利用建立的反向路由來轉(zhuǎn)發(fā)RREP。

2 AODV協(xié)議中路由存在的問題

如上節(jié)所述，AODV路由協(xié)議是按最快到達(dá)目的節(jié)點的RREQ消息分組所經(jīng)多的路徑，即最小延時路徑，不考慮網(wǎng)絡(luò)的傳播時延，就是最小跳數(shù)路由。

圖1 路由選擇方式

如圖1(a)所示的一個簡單的Ad Hoc網(wǎng)絡(luò)中，假設(shè)節(jié)點3要向節(jié)點7發(fā)送數(shù)據(jù)，如果采用最小跳數(shù)路由算法，則選擇的路徑為3-4-7，且節(jié)點3向節(jié)點7發(fā)送的數(shù)據(jù)量很大，使得節(jié)點4的鏈路層緩存接近飽和。此時，若節(jié)點3也要向節(jié)點6發(fā)送數(shù)據(jù)，根據(jù)AODV算法，節(jié)點選擇其中跳數(shù)最小的路徑2-4-6，這樣，兩條路徑均通過節(jié)點4，使得網(wǎng)絡(luò)中的所有數(shù)據(jù)都將通過節(jié)點4，因此可能會出現(xiàn)下面兩種不利情況：

1）由于節(jié)點4要轉(zhuǎn)發(fā)網(wǎng)絡(luò)中的所有數(shù)據(jù)，因此其能量消耗遠(yuǎn)大于網(wǎng)絡(luò)中的其他節(jié)點，一旦節(jié)點中的能量耗盡，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)就會發(fā)生改變，如圖1(b)所示，此時，節(jié)點與網(wǎng)絡(luò)中其它節(jié)點的連接就會中斷，且不能發(fā)送或者接收任何數(shù)據(jù)，這樣無論是對整個網(wǎng)絡(luò)還是對節(jié)點而言，顯然都不希望出現(xiàn)這種情況；

2）當(dāng)源節(jié)點產(chǎn)生大量數(shù)據(jù)使得數(shù)據(jù)到達(dá)節(jié)點的速率超過了鏈路層處理數(shù)據(jù)的速率，此時數(shù)據(jù)將在鏈路層的緩沖隊列中排隊等待，隨著緩沖隊列中數(shù)據(jù)的增加,分組延時也將增加。如果一直保持該狀態(tài)，將使鏈路層存儲數(shù)據(jù)的緩存隊列發(fā)生溢出，造成分組丟失，而源節(jié)點在規(guī)定的時間內(nèi)沒有收到目的節(jié)點發(fā)回的確認(rèn)消息，將繼續(xù)保留并重傳該分組，從而進(jìn)一步加劇了該路徑上各節(jié)點的擁塞，最終造成鏈路中斷。

3 基于網(wǎng)絡(luò)均衡的優(yōu)化度量

從以上分析中不難看出，AODV算法中采用的以最小跳數(shù)作為路由選擇的度量方式會導(dǎo)致網(wǎng)絡(luò)中某些“中心定位節(jié)點”被過多的選用。當(dāng)大量數(shù)據(jù)通過少量節(jié)點時,將造成網(wǎng)絡(luò)阻塞，從而增大數(shù)據(jù)包的發(fā)送時延,甚至造成數(shù)據(jù)包丟失。同時，這些節(jié)點在多于其他節(jié)點幾倍的接收和轉(zhuǎn)發(fā)任務(wù)下，能量會迅速消耗殆盡，最終可能促使網(wǎng)絡(luò)分裂成幾個相互難以覆蓋的“子網(wǎng)”，使網(wǎng)絡(luò)過早地陷于癱瘓。

因此,在路由算法的設(shè)計中有必要考慮各節(jié)點的負(fù)載狀況，對網(wǎng)絡(luò)的負(fù)載進(jìn)行均衡，使網(wǎng)絡(luò)保持連續(xù)、高效、穩(wěn)定的運行，網(wǎng)絡(luò)的綜合性能達(dá)到最優(yōu)。

實現(xiàn)均衡網(wǎng)絡(luò)負(fù)載的路由算法稱為負(fù)載均衡路由算，目前已經(jīng)提出了一些負(fù)載均衡路由算法，比如DLAR、LBAR和LSR，它們對網(wǎng)絡(luò)節(jié)點負(fù)載定義也不一樣。DLAR將輸出排隊中分組的個數(shù)定義為網(wǎng)絡(luò)節(jié)點負(fù)載；LBAR將節(jié)點負(fù)載定位為經(jīng)過自己和鄰居節(jié)點的路由數(shù)目；LSR將網(wǎng)絡(luò)負(fù)載定義為節(jié)點和鄰居節(jié)點上輸出排隊的分組個數(shù)之和，通過在選路過程中將負(fù)載作為路徑選擇優(yōu)化函數(shù)，在一定程度上實現(xiàn)了負(fù)載均衡。本文定義節(jié)點負(fù)載為節(jié)點輸出排隊中分組個數(shù)，設(shè)一條路由l包含節(jié)點ni，i=1:N，每個節(jié)點負(fù)載為：

根據(jù)網(wǎng)絡(luò)均衡的優(yōu)化度量準(zhǔn)則，提出一種NBAODV（Network Balance Aodv）的協(xié)議。

4 基于網(wǎng)絡(luò)均衡的協(xié)議(NB-AODV)實現(xiàn)

4.1 消息結(jié)構(gòu)修改

如表1所示，對AODV的RREQ消息報文添加了路由負(fù)載一項參數(shù)。其定義為RREQ消息經(jīng)過的所有節(jié)點的負(fù)載最大數(shù)，即中間節(jié)點接到RREQ消息分組，先判斷自己是否是目的節(jié)點，如果不是，判斷本節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)緩沖隊列分組個數(shù)與消息中的路由負(fù)載哪個大，分組個數(shù)大，把消息中的路由負(fù)載用分組個數(shù)替代，進(jìn)行轉(zhuǎn)發(fā)，如果不是，原樣轉(zhuǎn)發(fā)。

表1 RREQ報文格式

4.2 路由尋找過程

源節(jié)點發(fā)送RREQ消息分組，中間節(jié)點收到的第一個RREQ分組時，啟動一個定時器，在定時器規(guī)定的時間內(nèi),節(jié)點從所有的路由請求RREQ消息分組中選擇路由負(fù)載值最小的鄰居地址來建立反向路由，并利用建立的反向路由來轉(zhuǎn)發(fā)RREP。

4.3 仿真比較

為了比較NB-AODV、AODV、DLAR協(xié)議之間的性能差別，搭建了基于OPNET的仿真平臺。網(wǎng)絡(luò)覆蓋面積為：1000m×800m，移動節(jié)點速率為10m/s，節(jié)點個數(shù)為50個，改變分組發(fā)送速率分別為1、2、4、6、8和10packets/s，從數(shù)據(jù)成功接收率、平均端到端延時兩個方面對路由算法進(jìn)行比較。

圖2 數(shù)據(jù)成功接收率

圖3 平均端到端延時

5 結(jié)束語

本文對現(xiàn)有AODV協(xié)議中的最小延時路由問題進(jìn)行了分析和仿真，并提出基于網(wǎng)絡(luò)均衡度量優(yōu)化準(zhǔn)則的改進(jìn)方案，給出具體實現(xiàn)方法。該改進(jìn)方案避免了最小延時路由帶來的“中心節(jié)點”負(fù)載過重，延時較大的問題，仿真結(jié)果表明，新方案的數(shù)據(jù)分組成功接收率和平均端到端延時的性能指標(biāo)比AODV明顯增強(qiáng)，提高了網(wǎng)絡(luò)數(shù)據(jù)的傳輸效率。

[1] 王新生,張昕.MANET環(huán)境下AODV協(xié)議的研究和改進(jìn)[J].微機(jī)發(fā)展,2005,12.

[2] Johnson J,Maltz D. Dynamic source routing in Ad hoc wireless networks [M].Kluwer Academic: Mobile Computing,1996.

[3] Lee S J,Mario G.AODV-BR: Backup Routing in Ad hoc Networks[C].Wireless Communications and Networking Conference, 2000.WCNC. 2000 IEEE,2000,3:1311-1316.

[4] 王翠榮,陳書義,楊孝宗.基于AODV協(xié)議的動態(tài)路由管理算法[J].東北大學(xué)學(xué)報(自然科學(xué)版),2005,11.

[5] 朱金華,于寧寧.無線自組織網(wǎng)絡(luò)AODV路由協(xié)議研究[J].微計算機(jī)信息.2007,18.

[6] 朱西平,魯榮波,李宗壽,李方軍.基于NS2移動自組網(wǎng)路由協(xié)議性能評價的仿真實現(xiàn)[J].中南林學(xué)院學(xué)報,2004,02.

[7] 任智,郭偉;多跳無線網(wǎng)路由協(xié)議研究進(jìn)展[J].電信科學(xué),2003,08.