李 璞, 彭鵬菲

(海軍工程大學， 湖北 武漢 430000)

隨著無線網(wǎng)絡(luò)的發(fā)展,Ad hoc[1-3]越來越受到人民的關(guān)注,Ad hoc是一種無中心、自組織、多跳路由的動態(tài)網(wǎng)絡(luò),路由維護過程中需要根據(jù)鏈路通信狀況及網(wǎng)絡(luò)拓撲結(jié)構(gòu),運用合適的路由算法來提高通信的穩(wěn)定性。

在Ad hoc中,路由協(xié)議分為表驅(qū)動路由協(xié)議、按需路由協(xié)議和混合式路由協(xié)議,其中按需路由協(xié)議是指在需要給目的節(jié)點發(fā)送信息時才查找路由,按需路由協(xié)議雖然發(fā)送時延大于其他路由協(xié)議,但其在網(wǎng)絡(luò)開銷,路由修復(fù)速度方面有優(yōu)勢,比較適合路由修復(fù)。DSR[4-8]協(xié)議是當前典型的按需路由協(xié)議,但是在確認鏈路中斷以后才發(fā)起路由修復(fù),且在路由修復(fù)過程中都是采用洪泛機制解決路由發(fā)現(xiàn)的。

本文在分析DSR協(xié)議的基礎(chǔ)上,提出了鏈路質(zhì)量檢測,預(yù)先發(fā)起路由修復(fù)來彌補DSR路由時延過大的缺陷,同時結(jié)合節(jié)點的位置信息,提出扇形轉(zhuǎn)發(fā)域的路由查找修復(fù)算法,可以大大降低了路由控制開銷。

1 DSR協(xié)議

DSR是基于源路由的按需路由協(xié)議。DSR包括路由發(fā)現(xiàn)和路由維護兩個過程,只有源節(jié)點要給目的節(jié)點發(fā)送數(shù)據(jù)時且不存在到達目的節(jié)點路由的情況下才啟動路由發(fā)現(xiàn)。路由發(fā)現(xiàn)過程采用泛洪方式全網(wǎng)廣播路由請求。中間節(jié)點收到路由請求,首先查看自己是否是目的地址,如果不是則以同樣的方式廣播轉(zhuǎn)發(fā),如果是則向源節(jié)點發(fā)送路由請求應(yīng)答消息,這樣就完成了源節(jié)點到目的節(jié)點的路由建立。數(shù)據(jù)轉(zhuǎn)發(fā)過程中,鏈路中斷時才啟動路由維護過程。路由維護過程采用源節(jié)點修復(fù)機制,即中斷節(jié)點向源節(jié)點發(fā)送中斷報告,然后源節(jié)點在發(fā)起新的路由發(fā)現(xiàn)。

DSR協(xié)議存在以下缺點:一是確認鏈路中斷才發(fā)起新的路由發(fā)現(xiàn),增加了路由修復(fù)時間過長;二是當源節(jié)點和中斷節(jié)點有多跳距離,這時通過源節(jié)點啟動路由發(fā)現(xiàn)會導致路由發(fā)現(xiàn)時延過長;三是路由發(fā)現(xiàn)采用泛洪方式全網(wǎng)廣播方式,影響網(wǎng)絡(luò)性能。

2 局部路由修復(fù)算法

2.1 路由質(zhì)量檢測

2.1.1 穩(wěn)定域

每個節(jié)點都有以自己當前位置為圓心,以最大通信距離R為半徑的有效傳輸。當接受節(jié)點在有效傳輸圓區(qū)域時,它們之間就存在可通信的鏈路;否則不可點對點通信。有效傳輸包括穩(wěn)定域和非穩(wěn)定域兩個部分,定義穩(wěn)定域為機器可靠傳輸區(qū),定義非穩(wěn)定域為不可靠傳輸區(qū)。穩(wěn)定域的大小取決于可靠傳輸半徑r。當r較小時,穩(wěn)定域也小,這樣可能導致有些鏈路不通。當r較大時,穩(wěn)定域也大,容易造成鏈路不穩(wěn)定。假設(shè)在穩(wěn)定域和非穩(wěn)定域之間的閾值接收功率為Pth,修復(fù)當前非穩(wěn)定鏈路所需的時間為Tr,那么對于信號功閾值的最優(yōu)設(shè)置應(yīng)為:恰好在鏈路失效前Tr向本地節(jié)點發(fā)送質(zhì)量檢測報告。

2.1.2 檢測與質(zhì)量判斷

根據(jù)相關(guān)文獻[6],本地節(jié)點對發(fā)送節(jié)點的接收功率為

(1)

式中，d代表兩通信節(jié)點的距離,Ps代表節(jié)點發(fā)送功率,n依賴具體網(wǎng)絡(luò)環(huán)境,通常取值為2-4。

不考慮具體網(wǎng)絡(luò)環(huán)境下與鏈路質(zhì)量的具體關(guān)系。因此,對于網(wǎng)絡(luò)環(huán)境參數(shù)取3，根據(jù)上面(1)公式可得

(2)

若圖1中非穩(wěn)定區(qū)的寬度為θ,則θ=R-r,根據(jù)前面所講的最優(yōu)閾值功率設(shè)置得

θ=ΔVmaxTr

(3)

式中ΔVmax代表兩節(jié)點之間最大相對速度,Tr為本地路由修復(fù)時間,根據(jù)給出的修復(fù)時間、最大相對運動速度、最大通信半徑等參數(shù)就可以計算出最優(yōu)閾值功率Pth。當接受功率Pr,

2.2 基于地理位置信息路由發(fā)現(xiàn)

如圖2所示,網(wǎng)絡(luò)中各通信節(jié)點的地理位置已知,某時刻,網(wǎng)絡(luò)中的節(jié)點D根據(jù)業(yè)務(wù)分組接收功率得知上游鏈路質(zhì)量變差即將失效,那么該節(jié)點將向上游節(jié)點E發(fā)送路由質(zhì)量檢測報告。為確保解的多樣性,采用單次轉(zhuǎn)發(fā)雙次上傳的方式。接收到該報告的本地節(jié)點A成為自愈節(jié)點。接收到路由的修復(fù)請求分組的節(jié)點B,將立即根據(jù)節(jié)點A、B、D的位置坐標信息計算出A對節(jié)點B與目的節(jié)點D的張角∠BAD。根據(jù)節(jié)點A(X1,Y1),B(X2,Y2),節(jié)點D(X3,Y3)的位置信息可以計算出:節(jié)點AB,節(jié)點AD,節(jié)點BD之間的距離:

(4)

(5)

(6)

cos∠BAD=(|AB|2+|AD|2-|BD|2)/2 |AB||AD|

(7)

根據(jù)余弦公式可以計算出張角∠BAD為a,若計算結(jié)果滿足a≤a0,那么就意味著接收到分組的節(jié)點B位于修復(fù)區(qū)域之內(nèi),此時,該節(jié)點重新廣播。若計算結(jié)果滿足a>a0,那么意味著B位于修復(fù)區(qū)域之外,此時該節(jié)點將丟棄來自節(jié)點A的分組信息。

圖3給出了給出了局部路由修復(fù)算法的實現(xiàn)過程。

當某時刻節(jié)點D接收到的平均功率低于閾值功率,則上游節(jié)點C發(fā)送質(zhì)量檢測報告,并初始化報告中的跳數(shù)計數(shù)器Counter。因為采用單次轉(zhuǎn)發(fā)雙次上傳的機制,因此節(jié)點B轉(zhuǎn)發(fā)路由的同時會增加跳數(shù)計數(shù)器Counter。節(jié)點A收到檢測報告后,根據(jù)計數(shù)器的跳數(shù)值為1判斷自己為本地修復(fù)節(jié)點,然后發(fā)起本地路由修復(fù)。節(jié)點A以泛洪的方式發(fā)送包含目的節(jié)點D及本身節(jié)點A的位置信息的路由修復(fù)請求。一跳范圍節(jié)點E會根據(jù)三個節(jié)點坐標信息計算夾角∠EAD,然后判斷夾角∠EAD是否小于或等于設(shè)定的夾角a0,如果小于或等于則以同樣方式轉(zhuǎn)發(fā),如果大于則丟棄路由修復(fù)請求不處理。

文中預(yù)設(shè)的扇形頂角a0依賴網(wǎng)絡(luò)中節(jié)點的密度、節(jié)點間的距離、節(jié)點通信距離、節(jié)點運動速度等因素,且a0∈(0,π]以保證搜索區(qū)域的頂角滿足2a0∈(0,2π]。當扇形區(qū)域擴展為圓,此時就變成了傳統(tǒng)泛洪情況,頂角設(shè)置越大,路由修復(fù)過程中需要轉(zhuǎn)發(fā)的節(jié)點就越多,因此因修復(fù)而影響到的節(jié)點就越多,控制開銷越大。局部路由修復(fù)算法的處理過程如圖4所示。

3 仿真實驗及結(jié)果分析

本文采用LINUX環(huán)境下NS-2的2.34版本對基于DSR協(xié)議的局部路由修復(fù)算法的性能進行驗證和分析。節(jié)點隨機分布在800m*800m的網(wǎng)絡(luò)中,無線接口帶寬2M,功率半徑為200m,MAC層協(xié)議選擇IEEE 802.11 DCF。仿真時間持續(xù)100s。初始扇形夾角a0統(tǒng)一設(shè)定為π/3。

由圖5可以看出當節(jié)點數(shù)較少時,改進后的路由修復(fù)算法需要設(shè)置較大的扇形夾角,因此數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點數(shù)比較接近傳統(tǒng)的泛洪方式。當節(jié)點數(shù)較多時,設(shè)置較少的扇形夾角就可以完成路由修復(fù),因此轉(zhuǎn)發(fā)節(jié)點比傳統(tǒng)的泛洪方式大大減少。

4 結(jié)束語

本文提出一種局部路由修復(fù)方案,該方案通過鏈路質(zhì)量檢測預(yù)先發(fā)起路由修復(fù),彌補了傳統(tǒng)路由協(xié)議需要在確認鏈路失效后才發(fā)起路由修復(fù)請求導致的路由修復(fù)時延過長問題,提高了網(wǎng)絡(luò)的穩(wěn)定性,同時通過設(shè)計基于地理位置信息的路由查找算法,大大減少轉(zhuǎn)發(fā)節(jié)點,降低了對網(wǎng)絡(luò)的影響。

[1] 顏利平.Ad-hoc網(wǎng)絡(luò)中改進AODV路由協(xié)議的研究[D]. 哈爾濱:哈爾濱工業(yè)大學,2011:1-3.

[2] 易燕.基于移動代理的Ad hoc網(wǎng)絡(luò)DSR路由協(xié)議問題研究[D].云南:云南師范大學,2007:4.

[3] 曹亮.基于按需算法的Ad hoc網(wǎng)絡(luò)路由協(xié)議研究與改進[D].上海:上海交通大學,2008:8-10.

[4] 呂秋冬.基于DSR協(xié)議的區(qū)域路由研究[D].天津:天津大學,2005:18-19.

[5] 鮑傳山.Ad-hoc網(wǎng)絡(luò)中DSR路由協(xié)議的研究與改進[D].南京:南京郵電大學,2011:4-10.

[6] 賈站峰.Ad-hoc網(wǎng)絡(luò)按需路由算法優(yōu)化研究[D].哈爾濱:哈爾濱工程大學,2010:22-25.

[7] 阮穎平.基于Ad hoc的DSR協(xié)議與仿真[D].杭州:浙江工業(yè)大學,2009:21-25.

[8] 邵慧美.基于鏈路預(yù)測的無線自組網(wǎng)按需路由協(xié)議研究[D].哈爾濱:哈爾濱工業(yè)大學,2008:25-27.