梁龍，姚金杰

（中北大學(xué) 信息探測與處理技術(shù)研究所 山西 太原030051）

0 引言

本文在AODV的基礎(chǔ)上，提出一種新的雙徑路由改進(jìn)方案。數(shù)據(jù)可以在一條路徑失效的情況下，通過備用路徑繼續(xù)傳輸。有效的降低了路由發(fā)現(xiàn)次數(shù)，減小了路由開銷，提高了網(wǎng)絡(luò)的健壯性，增強(qiáng)了網(wǎng)絡(luò)對拓?fù)渥兓倪m應(yīng)能力。

1 AODV算法

1.1 路由發(fā)現(xiàn)過程

當(dāng)有數(shù)據(jù)需要發(fā)送時(shí)，源節(jié)點(diǎn)首先廣播一個(gè)攜帶目的節(jié)點(diǎn)信息的路由分組（RREQ），其鄰居節(jié)點(diǎn)依次向周圍節(jié)點(diǎn)廣播此路由分組，廣播RREQ前會(huì)建立此節(jié)點(diǎn)到源節(jié)點(diǎn)的路由，直到路由分組到達(dá)目的節(jié)點(diǎn)或者一個(gè)包含到目的節(jié)點(diǎn)路由信息的中間節(jié)點(diǎn)，就不再廣播RREQ。此過程中，會(huì)建立一個(gè)從目的節(jié)點(diǎn)到源節(jié)點(diǎn)的反向路由，然后該節(jié)點(diǎn)將沿著反向路由發(fā)回一個(gè)RREP，RREP到達(dá)源節(jié)點(diǎn)后路由發(fā)現(xiàn)過程結(jié)束。為避免路由循環(huán)，每一個(gè)路由分組中都包含一個(gè)sequence ID(SID)作為唯一標(biāo)志，如果一個(gè)節(jié)點(diǎn)收到一個(gè)SID比它當(dāng)前保留的SID小的數(shù)據(jù)包，表明該數(shù)據(jù)包是過時(shí)的，它將不予處理，而是簡單的丟棄。發(fā)現(xiàn)多跳路由時(shí)，源節(jié)點(diǎn)會(huì)選擇一條SID大、跳數(shù)少的最優(yōu)路由[3]。

1.2 路由維護(hù)過程

由于節(jié)點(diǎn)移動(dòng)等導(dǎo)致鏈路斷開，其鄰居節(jié)點(diǎn)發(fā)現(xiàn)鏈路失效并向上游節(jié)點(diǎn)發(fā)送鏈路失效消息（RERR），一直傳到源節(jié)點(diǎn)，然后源節(jié)點(diǎn)重新發(fā)起路由發(fā)現(xiàn)，或者也可以由發(fā)現(xiàn)鏈路失效的節(jié)點(diǎn)發(fā)起路由發(fā)現(xiàn)。只要路由是活動(dòng)的，路由表就要一直維護(hù)下去。如果鏈路上不再有數(shù)據(jù)包傳遞，一段時(shí)間之后，鏈路就會(huì)過期，最終路由信息將從中間節(jié)點(diǎn)的路由表中刪除 。

2 AODV存在的問題

由以上AODV的工作過程中可以看出，AODV中路由表僅維護(hù)一條到指定目的節(jié)點(diǎn)的路由，當(dāng)某條路由失效時(shí)，源節(jié)點(diǎn)需重新發(fā)起路由發(fā)現(xiàn)過程。而在Ad Hoc網(wǎng)絡(luò)中由于節(jié)點(diǎn)的高移動(dòng)性和無線鏈路的不穩(wěn)定性，網(wǎng)絡(luò)拓?fù)湓诓粩嘧兓?，造成鏈路的頻繁失效，這樣網(wǎng)絡(luò)就會(huì)頻繁地啟動(dòng)路由發(fā)現(xiàn)過程，會(huì)帶來大量的路由負(fù)載，從而增加了網(wǎng)絡(luò)的負(fù)荷[4]。又節(jié)點(diǎn)的路由發(fā)現(xiàn)機(jī)制采用泛洪式，而在路由回復(fù)時(shí)只有最早收到請求的節(jié)點(diǎn)提供路由回復(fù)，這樣，很大一部分請求發(fā)送時(shí)占用的路由資源就白白浪費(fèi)了[5]。

3 AODV路由協(xié)議的改進(jìn)

3.1 對路由發(fā)現(xiàn)的改進(jìn)

如1.1中介紹，在路由發(fā)現(xiàn)過程中，當(dāng)源節(jié)點(diǎn)向鄰節(jié)點(diǎn)廣播RREQ時(shí)，RREQ包會(huì)被很多節(jié)點(diǎn)收到并轉(zhuǎn)發(fā)，但是只有一個(gè)RREP回復(fù)給源節(jié)點(diǎn)，這樣廣播的時(shí)候所占用的資源沒有得到利用，浪費(fèi)了很多的路由資源。本文提出在目的節(jié)點(diǎn)收到RREQ后，按不同的路徑回復(fù)兩個(gè)應(yīng)答信息RREP。對于有到目的節(jié)點(diǎn)有效路由的中間節(jié)點(diǎn)收到RREQ后，只要有一個(gè)中間節(jié)點(diǎn)回復(fù)RREP給源節(jié)點(diǎn)即可。這樣就意味著，源節(jié)點(diǎn)可以收到至少兩個(gè)到目的節(jié)點(diǎn)的RREP。改進(jìn)后算法在源節(jié)點(diǎn)保存最先到達(dá)的兩個(gè)RREP中的路由，然后存儲(chǔ)到路由表中。最先到達(dá)的RREP里保存的路由作為源節(jié)點(diǎn)發(fā)送數(shù)據(jù)給目的節(jié)點(diǎn)的主路由。第二個(gè)到達(dá)的RREP里保存的路由作為備用路由。如果主路由失效，源節(jié)點(diǎn)可以不必發(fā)起路由請求，直接調(diào)用備用路由即可。改進(jìn)后的雙徑路由模型如圖1所示。

圖1 雙徑路由模型

3.2 對路由維護(hù)的改進(jìn)

如1.2中介紹，由于節(jié)點(diǎn)的移動(dòng)性，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)也發(fā)生相應(yīng)的變化。如果移動(dòng)的節(jié)點(diǎn)不是要使用的路由上的節(jié)點(diǎn)，則不做任何處理。如果源節(jié)點(diǎn)移動(dòng)，則可以重新發(fā)起路由發(fā)現(xiàn)過程查找新的路由。當(dāng)目的節(jié)點(diǎn)或中間節(jié)點(diǎn)移動(dòng)時(shí)，發(fā)送一個(gè)RERR消息給源節(jié)點(diǎn)。如果下一跳無法到達(dá)，則由上一跳節(jié)點(diǎn)發(fā)送RERR消息，包含新的序列號(hào)并設(shè)置跳數(shù)為無窮大。節(jié)點(diǎn)收到RERR消息以后，將路由表中相應(yīng)的路由設(shè)置為無效，并采用相同的方式繼續(xù)傳播RERR消息。源節(jié)點(diǎn)收到RERR消息后，可以采用備用路由發(fā)送數(shù)據(jù)。如果沒有備用路由，將重新啟動(dòng)路由發(fā)現(xiàn)過程。

4 仿真結(jié)果及性能分析

仿真實(shí)驗(yàn)使用NS-2網(wǎng)絡(luò)仿真工具，版本為2.30，仿真環(huán)境為Cygin。仿真場景設(shè)置如下：30個(gè)節(jié)點(diǎn)隨機(jī)會(huì)分布在1000m×1000m的正方形區(qū)域內(nèi)；MAC層協(xié)議采用IEEE802.11；無線電傳播模型為TwoRayGround；天線模型為全向天線；使用CBR作為數(shù)據(jù)業(yè)務(wù)流，數(shù)據(jù)包大小為1000字節(jié)。本仿真中設(shè)置一對特定的數(shù)據(jù)流業(yè)務(wù)。根據(jù)運(yùn)動(dòng)模型，每個(gè)節(jié)點(diǎn)隨機(jī)地向一個(gè)目的地移動(dòng)，平均移動(dòng)速度為10m/s，仿真時(shí)間為100s。所有仿真結(jié)果均為多次實(shí)驗(yàn)的平均值。用NS2自帶的動(dòng)畫演示工具nam可以演示整個(gè)仿真過程，某時(shí)刻仿真場景如圖2所示。

圖2 nam演示的仿真場景圖

4.1 時(shí)延分析

端到端時(shí)延是指分組從源節(jié)點(diǎn)發(fā)送到達(dá)目的節(jié)點(diǎn)所經(jīng)歷的時(shí)間間隔，從圖3可以看出，在使用了改進(jìn)算法以后，分組的時(shí)延有一定程度的減小。這是由于改進(jìn)后的協(xié)議采用雙路由的策略，這樣當(dāng)一條路由失效后，可以從源節(jié)點(diǎn)找到另一條備用路由，就不需要源節(jié)點(diǎn)重新廣播來尋找新的路由，所以端到端的延遲減小了。 (圖中aodvg為改進(jìn)后的算法)

4.2 數(shù)據(jù)包丟失分析

數(shù)據(jù)包在傳送過程中要發(fā)生丟失現(xiàn)象，由發(fā)送數(shù)據(jù)包總數(shù)減去接收到的數(shù)據(jù)包總數(shù)所得。數(shù)據(jù)包丟失越少說明網(wǎng)絡(luò)的傳輸效率越高。由圖4可看出，改進(jìn)后的算法比原算法數(shù)據(jù)包丟失數(shù)目有一定程度的的減小。這是由于在節(jié)點(diǎn)移動(dòng)時(shí)，原算法由于鏈路斷開而重新泛洪請求時(shí)，信息大部分來自于鄰居節(jié)點(diǎn)而無法獲得最新的網(wǎng)絡(luò)信息，導(dǎo)致丟包數(shù)增加。而改進(jìn)后的算法在鏈路斷開時(shí)，可改用備選路徑，迅速建立鏈接。因此丟包數(shù)會(huì)較原協(xié)議減少[6]。

圖3 aodv與aodvg的時(shí)延比較

圖4 aodv與aodvg的數(shù)據(jù)包丟失比較

4.3 吞吐量分析

吞吐量由所接收的封包大小總和除以所花費(fèi)的時(shí)間得到。由圖5可以看到改進(jìn)后的算法較原算法吞吐量量有一定的增加。由4.1和4.2的分析可容易得出，延時(shí)減小，數(shù)據(jù)包丟失減少，吞吐量得到提升。

圖5 aodv與aodvg的吞吐量比較

5 結(jié)論和未來工作

針對AODV路由協(xié)議中對路由發(fā)現(xiàn)和路由維護(hù)存在的不足，本文提出一種新的Ad Hoc雙路徑路由機(jī)制。這種路由機(jī)制通過在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間建立兩條路徑來增強(qiáng)路由的健壯性，通過模擬測試顯示，該算法在端到端時(shí)延、 數(shù)據(jù)包丟失、 吞吐量等方面有較好的改善。但是針對Ad Hoc網(wǎng)絡(luò)的具體現(xiàn)實(shí)情況，如何將這些算法應(yīng)用到實(shí)際當(dāng)中去，這是一個(gè)值得探討的問題，也是以后工作的重點(diǎn)。

[1]米志超,鄭少仁.Ad hoc網(wǎng)絡(luò)技術(shù)講座[J].中國數(shù)據(jù)通信，2003，32（12）：84-85.

[2]李國強(qiáng),武穆清.Ad Hoc網(wǎng)絡(luò)中一種新的多徑路由機(jī)制研究[J].信息傳輸與接入技術(shù)，2008，34 （1）：22-24.

[3]Multi-path Routing in wireless Ad hoc networks[C].Proceedings of IEEE Local Computer Networks(LCN),2004(11),19-20.

[4]方路平,劉世華.NS-2網(wǎng)絡(luò)模擬基礎(chǔ)與應(yīng)用[M].北京：國防工業(yè)出版社,2008：147-148.

[5]楊少雯.基于NS2的無線自組網(wǎng)路由協(xié)議研究[D].哈爾濱：哈爾濱理工大學(xué)電氣與電子工程學(xué)院,2007：28-36.

[6]陳躍泉,郭曉峰.基于網(wǎng)絡(luò)最大流的Ad-Hoc多路徑路由算法[J].電子學(xué)報(bào),2004,32（8）：1329-1300.