移動(dòng)Ad Hoc網(wǎng)絡(luò)基于路由協(xié)議的擁塞控制[圖]

移動(dòng)自組網(wǎng)MANET(Mobile Ad Hoc Network)[1]是由一組帶有無(wú)線通信收發(fā)裝置的移動(dòng)終端節(jié)點(diǎn)組成的一個(gè)多跳、臨時(shí)性無(wú)中心的網(wǎng)絡(luò)，整個(gè)網(wǎng)絡(luò)沒(méi)有固定的基礎(chǔ)設(shè)施,網(wǎng)中的每個(gè)終端都可以自由移動(dòng)、自由加入和退出網(wǎng)絡(luò)，各網(wǎng)絡(luò)節(jié)點(diǎn)地位相等。Ad Hoc網(wǎng)絡(luò)具有很高的靈活性，可以廣泛應(yīng)用于不易建立基礎(chǔ)設(shè)施的環(huán)境，如地震后的緊急搜救、軍用戰(zhàn)術(shù)環(huán)境和民用應(yīng)急通信。與單跳的無(wú)線網(wǎng)路不同，移動(dòng)自組網(wǎng)的節(jié)點(diǎn)之間通過(guò)多跳數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制進(jìn)行數(shù)據(jù)通信，需要中間節(jié)點(diǎn)進(jìn)行分組轉(zhuǎn)發(fā)決策。

移動(dòng)自組網(wǎng)路由協(xié)議的多數(shù)路由協(xié)議以單徑路由算法為基礎(chǔ)，而且在路由選擇時(shí)以跳數(shù)最少(或稱為路徑最短)作為選擇標(biāo)準(zhǔn)，沒(méi)有考慮網(wǎng)絡(luò)擁塞問(wèn)題。由于一條路徑的帶寬有限，當(dāng)很多節(jié)點(diǎn)都選擇跳數(shù)最少路徑作為路由路徑時(shí)，骨干節(jié)點(diǎn)連接繁忙，從而造成端到端時(shí)延和丟包率增大，網(wǎng)絡(luò)擁塞，影響網(wǎng)絡(luò)整體性能[2]，而且擁塞引起的路由控制消息丟失會(huì)觸發(fā)更多的路由請(qǐng)求和路由回復(fù)，從而加劇網(wǎng)絡(luò)擁塞。

1 AODV路由協(xié)議

網(wǎng)絡(luò)路由協(xié)議是實(shí)現(xiàn)網(wǎng)絡(luò)通信最關(guān)鍵和最核心的問(wèn)題。目前比較成熟透明的按需距離矢量路由AODV(Ad Hoc on-Demand Distance Vector Routing)[3]基于傳統(tǒng)的距離向量路由機(jī)制，具有簡(jiǎn)單易實(shí)現(xiàn)、防止循環(huán)發(fā)生、支持中間節(jié)點(diǎn)應(yīng)答等優(yōu)點(diǎn)，但也存在一定不足：每次由源節(jié)點(diǎn)發(fā)起路由請(qǐng)求均只得到一條路由、中間節(jié)點(diǎn)的應(yīng)答路由可能過(guò)時(shí)等。在AODV協(xié)議的仿真實(shí)驗(yàn)中發(fā)現(xiàn)，隨著網(wǎng)絡(luò)負(fù)荷的增加，網(wǎng)絡(luò)經(jīng)常出現(xiàn)局部擁塞，吞吐率下降很快。網(wǎng)絡(luò)中某些節(jié)點(diǎn)負(fù)荷很大，而節(jié)點(diǎn)的鏈路帶寬和處理能力有限，當(dāng)數(shù)據(jù)到達(dá)速率超過(guò)節(jié)點(diǎn)處理能力時(shí)，數(shù)據(jù)將阻塞在這些節(jié)點(diǎn)中等待傳輸。一旦這種狀況持續(xù)一段時(shí)間，節(jié)點(diǎn)緩沖區(qū)會(huì)很快溢出，從而造成數(shù)據(jù)分組丟失。而源節(jié)點(diǎn)因在規(guī)定時(shí)間內(nèi)沒(méi)有收到確認(rèn)而選擇重傳，這又將進(jìn)一步加劇該路徑節(jié)點(diǎn)的擁塞，導(dǎo)致這些節(jié)點(diǎn)成為影響網(wǎng)絡(luò)效率的瓶頸[4]。

為了緩解擁塞對(duì)網(wǎng)絡(luò)性能的影響，提出一種基于AODV路由協(xié)議，能夠緩解鏈路擁塞的路由算法LC-AODV。在擁塞節(jié)點(diǎn)的上游節(jié)點(diǎn)處建立能繞過(guò)擁塞節(jié)點(diǎn)的旁路，在網(wǎng)絡(luò)工作路由處于堵塞情況時(shí)啟動(dòng)備份路由分流，從而避免擁塞的發(fā)生。

2 LC-AODV路由協(xié)議

2.1 AODV路由協(xié)議的修改

在AODV路由協(xié)議中，路由查找過(guò)程只建立一條從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的跳數(shù)最少、距離最短的路由。為了緩解擁塞，在一次尋找路由過(guò)程中建立多條節(jié)點(diǎn)不相關(guān)路由，并在路由尋找過(guò)程中加入鏈路擁塞度。

定義1：節(jié)點(diǎn)不相關(guān)路由，指所建多條路由中，任何兩條路徑除了源節(jié)點(diǎn)和目的節(jié)點(diǎn)外，其他節(jié)點(diǎn)都不共用。

定義2：鏈路擁塞度，描述本節(jié)點(diǎn)與下一跳鄰居節(jié)點(diǎn)的擁塞狀態(tài)，取值為下一跳節(jié)點(diǎn)的MAC層接口緩存隊(duì)列中剩余空間占總隊(duì)列的比率。

具體修改操作如下：

(1)在AODV路由協(xié)議的基礎(chǔ)上，針對(duì)路由請(qǐng)求RREQ和路由應(yīng)答RREP控制包分別增加一個(gè)條目——鏈路擁塞度。在源節(jié)點(diǎn)需要傳輸數(shù)據(jù)時(shí)，發(fā)送路由請(qǐng)求RREQ消息，當(dāng)RREQ報(bào)文按照不同的路徑到達(dá)目的節(jié)點(diǎn)時(shí)，目的節(jié)點(diǎn)不是簡(jiǎn)單地只處理第一個(gè)到達(dá)的RREQ，對(duì)此后到達(dá)的RREQ回復(fù)相同的RREP，并建立源節(jié)點(diǎn)到目的節(jié)點(diǎn)的備份路由。

(2)在路由維護(hù)階段，周期性地傳輸Hello報(bào)文以確保鏈路的連接。但是在LC-AODV路由協(xié)議中，同樣在Hello消息中增加鏈路擁塞度這一條目，檢測(cè)該節(jié)點(diǎn)與鄰居節(jié)點(diǎn)之間鏈路的擁塞度，并加以動(dòng)態(tài)調(diào)整。

2.2 擁塞狀態(tài)檢測(cè)

在進(jìn)行數(shù)據(jù)傳輸過(guò)程中，當(dāng)傳到一個(gè)節(jié)點(diǎn)的包個(gè)數(shù)超過(guò)它的處理能力時(shí)，節(jié)點(diǎn)就會(huì)變得擁塞，由于節(jié)點(diǎn)隊(duì)列長(zhǎng)度有限，故包會(huì)根據(jù)隊(duì)列類型的方式開(kāi)始丟棄，用R來(lái)表示定義2描述的鏈路擁塞程度[5]。根據(jù)R值的不同，設(shè)定三種擁塞狀態(tài)。根據(jù)式(1)的劃分，LCD為0時(shí)表示鏈路不擁塞，顯示為綠色狀態(tài)；LCD為1時(shí)表示鏈路出現(xiàn)擁塞，但是不是很嚴(yán)重，顯示為黃色狀態(tài)；LCD為2時(shí)，鏈路出現(xiàn)嚴(yán)重?fù)砣�，顯示為紅色狀態(tài)。

2.3 LC-AODV工作原理

搭建一個(gè)移動(dòng)Ad Hoc網(wǎng)絡(luò)，如圖1所示，S為源節(jié)點(diǎn)，D為目的節(jié)點(diǎn)，其他為中間轉(zhuǎn)發(fā)節(jié)點(diǎn)。當(dāng)源節(jié)點(diǎn)有數(shù)據(jù)要向目的節(jié)點(diǎn)傳輸，而且S節(jié)點(diǎn)中沒(méi)有到目的節(jié)點(diǎn)的路由時(shí)，需要建立路由。源節(jié)點(diǎn)廣播路由請(qǐng)求RREQ，假設(shè)在路由建立過(guò)程中，找到了兩條路由分別為路由1：S-3-4-5-D和路由2：S-1-2-D。路由1先返回路由應(yīng)答，則路由2作為備份路由存在于網(wǎng)絡(luò)中。當(dāng)數(shù)據(jù)開(kāi)始傳輸一段時(shí)間后，節(jié)點(diǎn)3到節(jié)點(diǎn)4之間發(fā)生路由擁塞，則節(jié)點(diǎn)3啟動(dòng)局部修復(fù)，發(fā)現(xiàn)可通過(guò)節(jié)點(diǎn)6到達(dá)目的節(jié)點(diǎn)，則產(chǎn)生路由S-3-6-5-D，因?yàn)橥ㄟ^(guò)節(jié)點(diǎn)6進(jìn)行傳輸時(shí)，鏈路有輕微擁塞，則向上游節(jié)點(diǎn)通知備份路由，隨時(shí)準(zhǔn)備發(fā)送數(shù)據(jù)。如果修復(fù)不成功，則直接啟動(dòng)備份路由2進(jìn)行數(shù)據(jù)傳輸。當(dāng)所有路由都失效的情況下，源節(jié)點(diǎn)重新啟動(dòng)路由請(qǐng)求過(guò)程。

2.4 鄰居擁塞表

每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)鄰居擁塞表，記錄本節(jié)點(diǎn)所有鄰居節(jié)點(diǎn)(除去上一跳節(jié)點(diǎn))的擁塞狀態(tài)。例如在表1中，對(duì)于節(jié)點(diǎn)S而言，LCDs1的值為0。

3 實(shí)驗(yàn)仿真及結(jié)果分析

實(shí)驗(yàn)采用NS2[6]模擬平臺(tái)進(jìn)行模擬，將LC-AODV算法與AODV在相同網(wǎng)絡(luò)環(huán)境和高負(fù)載特性下進(jìn)行仿真和性能對(duì)比分析，以便有效評(píng)價(jià)本算法的性能。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)為50個(gè)移動(dòng)節(jié)點(diǎn)的網(wǎng)絡(luò)模型，各節(jié)點(diǎn)隨機(jī)分布在1200m×1000m的平面矩形區(qū)域，每一個(gè)節(jié)點(diǎn)的最大傳輸范圍為250m，隨機(jī)任意方向運(yùn)動(dòng)(Random Way Point) ，節(jié)點(diǎn)停留時(shí)間為0s，實(shí)驗(yàn)?zāi)�擬時(shí)間500s，運(yùn)動(dòng)最大速率為40m/s，連接為20個(gè)CBR，大小為512B數(shù)據(jù)流，數(shù)據(jù)流為3packets/s，最大連接數(shù)為20。物理層選用TwoRayGround無(wú)線傳播模型，MAC層采用802.11b DCF協(xié)議。仿真過(guò)程如圖2所示。通過(guò)數(shù)據(jù)包的成功傳輸率和平均端到端傳輸延遲2個(gè)指標(biāo)來(lái)比較。

3.1 數(shù)據(jù)包的成功傳遞率

數(shù)據(jù)包遞交率：目的節(jié)點(diǎn)收到的數(shù)據(jù)包數(shù)與源節(jié)點(diǎn)發(fā)送的總數(shù)據(jù)包數(shù)的比率。仿真結(jié)果如圖3所示。LC-AODV的正確傳輸率比AODV更高，因?yàn)椴扇】箵砣�措施，�?jié)點(diǎn)丟失包的幾率就會(huì)降低，導(dǎo)致到達(dá)目的節(jié)點(diǎn)的數(shù)據(jù)包增加。當(dāng)節(jié)點(diǎn)移動(dòng)速度不快時(shí)，網(wǎng)絡(luò)的節(jié)點(diǎn)位置變化不大，即拓?fù)浣Y(jié)構(gòu)較為穩(wěn)定，網(wǎng)絡(luò)數(shù)據(jù)包的正確傳遞率都處于高水平，但是隨著節(jié)點(diǎn)移動(dòng)速度增大，數(shù)據(jù)包丟失增多，網(wǎng)絡(luò)整體性能下降。而且隨著網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化的加快，兩種路由協(xié)議之間的差距在慢慢變小，這是因?yàn)楦倪M(jìn)后的路由協(xié)議在拓?fù)浣Y(jié)構(gòu)變化比較快時(shí)，路由經(jīng)常失效，抗擁塞措施作用有所下降。

3.2 平均端到端延遲

傳輸數(shù)據(jù)包所需的總延遲包括緩存數(shù)據(jù)包、新路由發(fā)現(xiàn)、在隊(duì)列中排隊(duì)、MAC層重傳、發(fā)送和傳播所用的時(shí)延總和。仿真結(jié)果如圖4所示。整體而言，LC-AODV的性能優(yōu)于AODV路由協(xié)議，這是因?yàn)椴扇×丝箵砣�措施，在�?shù)據(jù)傳輸?shù)臅r(shí)候選擇擁塞度低的鏈路，而且在傳輸過(guò)程中若遇到擁塞會(huì)及時(shí)地進(jìn)行鏈路轉(zhuǎn)移，使得傳輸更為順暢。而且在節(jié)點(diǎn)移動(dòng)速度較小時(shí)，拓?fù)渥兓�較小，備份路由存在時(shí)間長(zhǎng)，導(dǎo)致備份路由在節(jié)點(diǎn)移動(dòng)速度低時(shí)較節(jié)點(diǎn)移動(dòng)速度快時(shí)的利用率更高，從而速度低時(shí)兩路由協(xié)議的延遲差距更小。

本文針對(duì)移動(dòng)Ad Hoc網(wǎng)絡(luò)高負(fù)載情況下網(wǎng)絡(luò)路由不能很好適應(yīng)網(wǎng)絡(luò)環(huán)境的問(wèn)題，提出了一種抗擁塞的改進(jìn)AODV路由協(xié)議。改進(jìn)的LC-AODV協(xié)議是一個(gè)適用于動(dòng)態(tài)Ad Hoc網(wǎng)絡(luò)的擁塞適應(yīng)路由協(xié)議。利用鄰居擁塞表，節(jié)點(diǎn)能即時(shí)感知與鄰居之間的網(wǎng)絡(luò)擁塞度，并根據(jù)擁塞等級(jí)采取不同的策略，通過(guò)備份路由來(lái)快速重新傳輸數(shù)據(jù)。結(jié)果證明改進(jìn)后的路由協(xié)議可以緩解網(wǎng)絡(luò)的負(fù)載，提高了數(shù)據(jù)包正確傳輸率并降低端到端平均延遲。

參考文獻(xiàn)

[1] RAMANATHAN R，REDI J.A brief overview of mobile Ad Hoc networks: Challenges and direction[J].IEEE Communications Magazine, 2002, 40(5): 20-23.

　　[2] KLIAZOVICH D，GRANELLI F. Cross-layer congestion control in Ad Hoc wireless networks[J]. Ad Hoc Networks, 2006(4): 687-708.

　　[3] PERKINS C E，ROYER E M.Ad Hoc on demand and distance vector(AODV) routing[C]. The second IEEE workshop on mobile computing systems and applications. New Orleans. 1999:90-100.

　　[4] RAGHAVENDRA H.Congestion adaptive routing in mobile Ad Hoc networks[A]. IEEE Transactions on Parallel Distributed Systems[C].NJ, USA: IEEE Press,2006:1294-1305.

　　[5] 蔣道霞，劉鳳玉.Ad Hoc網(wǎng)絡(luò)中基于AODV的擁塞適應(yīng)路由協(xié)議[J]. 南京理工大學(xué)學(xué)報(bào)(自然科學(xué)版),2009, 33(4):411-416.

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

作者：徐祎 周少瓊 柏詩(shī)玉 合肥電子工程學(xué)院信息系 來(lái)源：《微型機(jī)與應(yīng)用》2011年04期