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