摘 要: 為解決Ad Hoc網(wǎng)絡(luò)的AODV路由協(xié)議在通信過程中存在的擁塞問題,提出了改進(jìn)AODV路由協(xié)議的思想,。根據(jù)網(wǎng)絡(luò)鏈路擁塞度的大小采取不同措施和節(jié)點路由,,建立不相關(guān)多徑路由分流以避免擁塞。仿真結(jié)果表明,,改進(jìn)后的路由協(xié)議有效地減少了發(fā)生擁塞的幾率,,從而提高了移動Ad Hoc網(wǎng)絡(luò)的性能。
關(guān)鍵詞: Ad Hoc網(wǎng)絡(luò),;路由協(xié)議,;鏈路擁塞
移動自組網(wǎng)MANET(Mobile Ad Hoc Network)[1]是由一組帶有無線通信收發(fā)裝置的移動終端節(jié)點組成的一個多跳、臨時性無中心的網(wǎng)絡(luò),,整個網(wǎng)絡(luò)沒有固定的基礎(chǔ)設(shè)施,網(wǎng)中的每個終端都可以自由移動,、自由加入和退出網(wǎng)絡(luò),各網(wǎng)絡(luò)節(jié)點地位相等,。Ad Hoc網(wǎng)絡(luò)具有很高的靈活性,,可以廣泛應(yīng)用于不易建立基礎(chǔ)設(shè)施的環(huán)境,如地震后的緊急搜救,、軍用戰(zhàn)術(shù)環(huán)境和民用應(yīng)急通信,。與單跳的無線網(wǎng)路不同,移動自組網(wǎng)的節(jié)點之間通過多跳數(shù)據(jù)轉(zhuǎn)發(fā)機制進(jìn)行數(shù)據(jù)通信,,需要中間節(jié)點進(jìn)行分組轉(zhuǎn)發(fā)決策,。
移動自組網(wǎng)路由協(xié)議的多數(shù)路由協(xié)議以單徑路由算法為基礎(chǔ),而且在路由選擇時以跳數(shù)最少(或稱為路徑最短)作為選擇標(biāo)準(zhǔn),,沒有考慮網(wǎng)絡(luò)擁塞問題,。由于一條路徑的帶寬有限,當(dāng)很多節(jié)點都選擇跳數(shù)最少路徑作為路由路徑時,,骨干節(jié)點連接繁忙,,從而造成端到端時延和丟包率增大,網(wǎng)絡(luò)擁塞,,影響網(wǎng)絡(luò)整體性能[2],,而且擁塞引起的路由控制消息丟失會觸發(fā)更多的路由請求和路由回復(fù),從而加劇網(wǎng)絡(luò)擁塞,。
1 AODV路由協(xié)議
網(wǎng)絡(luò)路由協(xié)議是實現(xiàn)網(wǎng)絡(luò)通信最關(guān)鍵和最核心的問題,。目前比較成熟透明的按需距離矢量路由AODV(Ad Hoc on-Demand Distance Vector Routing)[3]基于傳統(tǒng)的距離向量路由機制,具有簡單易實現(xiàn),、防止循環(huán)發(fā)生,、支持中間節(jié)點應(yīng)答等優(yōu)點,但也存在一定不足:每次由源節(jié)點發(fā)起路由請求均只得到一條路由,、中間節(jié)點的應(yīng)答路由可能過時等,。在AODV協(xié)議的仿真實驗中發(fā)現(xiàn),,隨著網(wǎng)絡(luò)負(fù)荷的增加,網(wǎng)絡(luò)經(jīng)常出現(xiàn)局部擁塞,,吞吐率下降很快,。網(wǎng)絡(luò)中某些節(jié)點負(fù)荷很大,而節(jié)點的鏈路帶寬和處理能力有限,,當(dāng)數(shù)據(jù)到達(dá)速率超過節(jié)點處理能力時,,數(shù)據(jù)將阻塞在這些節(jié)點中等待傳輸。一旦這種狀況持續(xù)一段時間,,節(jié)點緩沖區(qū)會很快溢出,,從而造成數(shù)據(jù)分組丟失。而源節(jié)點因在規(guī)定時間內(nèi)沒有收到確認(rèn)而選擇重傳,,這又將進(jìn)一步加劇該路徑節(jié)點的擁塞,導(dǎo)致這些節(jié)點成為影響網(wǎng)絡(luò)效率的瓶頸[4],。
為了緩解擁塞對網(wǎng)絡(luò)性能的影響,,提出一種基于AODV路由協(xié)議,能夠緩解鏈路擁塞的路由算法LC-AODV,。在擁塞節(jié)點的上游節(jié)點處建立能繞過擁塞節(jié)點的旁路,,在網(wǎng)絡(luò)工作路由處于堵塞情況時啟動備份路由分流,從而避免擁塞的發(fā)生,。
2 LC-AODV路由協(xié)議
2.1 AODV路由協(xié)議的修改
在AODV路由協(xié)議中,,路由查找過程只建立一條從源節(jié)點到目的節(jié)點的跳數(shù)最少、距離最短的路由,。為了緩解擁塞,,在一次尋找路由過程中建立多條節(jié)點不相關(guān)路由,并在路由尋找過程中加入鏈路擁塞度,。
定義1:節(jié)點不相關(guān)路由,,指所建多條路由中,任何兩條路徑除了源節(jié)點和目的節(jié)點外,,其他節(jié)點都不共用,。
定義2:鏈路擁塞度,描述本節(jié)點與下一跳鄰居節(jié)點的擁塞狀態(tài),,取值為下一跳節(jié)點的MAC層接口緩存隊列中剩余空間占總隊列的比率,。
具體修改操作如下:
(1)在AODV路由協(xié)議的基礎(chǔ)上,針對路由請求RREQ和路由應(yīng)答RREP控制包分別增加一個條目——鏈路擁塞度,。在源節(jié)點需要傳輸數(shù)據(jù)時,,發(fā)送路由請求RREQ消息,當(dāng)RREQ報文按照不同的路徑到達(dá)目的節(jié)點時,,目的節(jié)點不是簡單地只處理第一個到達(dá)的RREQ,,對此后到達(dá)的RREQ回復(fù)相同的RREP,,并建立源節(jié)點到目的節(jié)點的備份路由。
(2)在路由維護(hù)階段,,周期性地傳輸Hello報文以確保鏈路的連接,。但是在LC-AODV路由協(xié)議中,同樣在Hello消息中增加鏈路擁塞度這一條目,,檢測該節(jié)點與鄰居節(jié)點之間鏈路的擁塞度,,并加以動態(tài)調(diào)整。
2.2 擁塞狀態(tài)檢測
在進(jìn)行數(shù)據(jù)傳輸過程中,,當(dāng)傳到一個節(jié)點的包個數(shù)超過它的處理能力時,,節(jié)點就會變得擁塞,由于節(jié)點隊列長度有限,,故包會根據(jù)隊列類型的方式開始丟棄,,用R來表示定義2描述的鏈路擁塞程度[5]。根據(jù)R值的不同,,設(shè)定三種擁塞狀態(tài),。根據(jù)式(1)的劃分,LCD為0時表示鏈路不擁塞,,顯示為綠色狀態(tài),;LCD為1時表示鏈路出現(xiàn)擁塞,但是不是很嚴(yán)重,,顯示為黃色狀態(tài),;LCD為2時,鏈路出現(xiàn)嚴(yán)重?fù)砣?,顯示為紅色狀態(tài),。
2.3 LC-AODV工作原理
搭建一個移動Ad Hoc網(wǎng)絡(luò),如圖1所示,,S為源節(jié)點,,D為目的節(jié)點,其他為中間轉(zhuǎn)發(fā)節(jié)點,。當(dāng)源節(jié)點有數(shù)據(jù)要向目的節(jié)點傳輸,,而且S節(jié)點中沒有到目的節(jié)點的路由時,需要建立路由,。源節(jié)點廣播路由請求RREQ,,假設(shè)在路由建立過程中,找到了兩條路由分別為路由1:S-3-4-5-D和路由2:S-1-2-D,。路由1先返回路由應(yīng)答,,則路由2作為備份路由存在于網(wǎng)絡(luò)中。當(dāng)數(shù)據(jù)開始傳輸一段時間后,節(jié)點3到節(jié)點4之間發(fā)生路由擁塞,,則節(jié)點3啟動局部修復(fù),,發(fā)現(xiàn)可通過節(jié)點6到達(dá)目的節(jié)點,則產(chǎn)生路由S-3-6-5-D,,因為通過節(jié)點6進(jìn)行傳輸時,,鏈路有輕微擁塞,則向上游節(jié)點通知備份路由,,隨時準(zhǔn)備發(fā)送數(shù)據(jù),。如果修復(fù)不成功,則直接啟動備份路由2進(jìn)行數(shù)據(jù)傳輸,。當(dāng)所有路由都失效的情況下,,源節(jié)點重新啟動路由請求過程。
2.4 鄰居擁塞表
每個節(jié)點維護(hù)一個鄰居擁塞表,,記錄本節(jié)點所有鄰居節(jié)點(除去上一跳節(jié)點)的擁塞狀態(tài),。例如在表1中,對于節(jié)點S而言,,LCDs1的值為0,。
3 實驗仿真及結(jié)果分析
實驗采用NS2[6]模擬平臺進(jìn)行模擬,將LC-AODV算法與AODV在相同網(wǎng)絡(luò)環(huán)境和高負(fù)載特性下進(jìn)行仿真和性能對比分析,,以便有效評價本算法的性能。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)設(shè)計為50個移動節(jié)點的網(wǎng)絡(luò)模型,,各節(jié)點隨機分布在1 200 m×1 000 m的平面矩形區(qū)域,,每一個節(jié)點的最大傳輸范圍為250 m,隨機任意方向運動(Random Way Point) ,,節(jié)點停留時間為0 s,,實驗?zāi)M時間500 s,運動最大速率為40 m/s,,連接為20個CBR,,大小為512 B數(shù)據(jù)流,數(shù)據(jù)流為3 packets/s,,最大連接數(shù)為20,。物理層選用TwoRayGround無線傳播模型,MAC層采用802.11b DCF協(xié)議,。仿真過程如圖2所示,。通過數(shù)據(jù)包的成功傳輸率和平均端到端傳輸延遲2個指標(biāo)來比較。
3.1 數(shù)據(jù)包的成功傳遞率
數(shù)據(jù)包遞交率:目的節(jié)點收到的數(shù)據(jù)包數(shù)與源節(jié)點發(fā)送的總數(shù)據(jù)包數(shù)的比率,。仿真結(jié)果如圖3所示,。LC-AODV的正確傳輸率比AODV更高,因為采取抗擁塞措施,,節(jié)點丟失包的幾率就會降低,,導(dǎo)致到達(dá)目的節(jié)點的數(shù)據(jù)包增加,。當(dāng)節(jié)點移動速度不快時,網(wǎng)絡(luò)的節(jié)點位置變化不大,,即拓?fù)浣Y(jié)構(gòu)較為穩(wěn)定,,網(wǎng)絡(luò)數(shù)據(jù)包的正確傳遞率都處于高水平,但是隨著節(jié)點移動速度增大,,數(shù)據(jù)包丟失增多,,網(wǎng)絡(luò)整體性能下降。而且隨著網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化的加快,,兩種路由協(xié)議之間的差距在慢慢變小,,這是因為改進(jìn)后的路由協(xié)議在拓?fù)浣Y(jié)構(gòu)變化比較快時,路由經(jīng)常失效,,抗擁塞措施作用有所下降,。
3.2 平均端到端延遲
傳輸數(shù)據(jù)包所需的總延遲包括緩存數(shù)據(jù)包、新路由發(fā)現(xiàn),、在隊列中排隊,、MAC層重傳、發(fā)送和傳播所用的時延總和,。仿真結(jié)果如圖4所示,。整體而言,LC-AODV的性能優(yōu)于AODV路由協(xié)議,,這是因為采取了抗擁塞措施,,在數(shù)據(jù)傳輸?shù)臅r候選擇擁塞度低的鏈路,而且在傳輸過程中若遇到擁塞會及時地進(jìn)行鏈路轉(zhuǎn)移,,使得傳輸更為順暢,。而且在節(jié)點移動速度較小時,拓?fù)渥兓^小,,備份路由存在時間長,,導(dǎo)致備份路由在節(jié)點移動速度低時較節(jié)點移動速度快時的利用率更高,從而速度低時兩路由協(xié)議的延遲差距更小,。
本文針對移動Ad Hoc網(wǎng)絡(luò)高負(fù)載情況下網(wǎng)絡(luò)路由不能很好適應(yīng)網(wǎng)絡(luò)環(huán)境的問題,,提出了一種抗擁塞的改進(jìn)AODV路由協(xié)議。改進(jìn)的LC-AODV協(xié)議是一個適用于動態(tài)Ad Hoc網(wǎng)絡(luò)的擁塞適應(yīng)路由協(xié)議,。利用鄰居擁塞表,,節(jié)點能即時感知與鄰居之間的網(wǎng)絡(luò)擁塞度,并根據(jù)擁塞等級采取不同的策略,,通過備份路由來快速重新傳輸數(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é)報(自然科學(xué)版),2009, 33(4):411-416.
[6] 方路平,劉世華,,陳盼,,等. NS-2網(wǎng)絡(luò)模擬基礎(chǔ)與應(yīng)用
[M]. 北京:國防工業(yè)出版社,2008.