基于鏈路時間預測的移動Ad Hoc網(wǎng)路由

胡 君,葉俊杰

(1.湖南科技職業(yè)學院軟件學院,長沙 410004;2.湖南科技大學商學院,湖南 湘潭 411100)

移動Ad Hoc網(wǎng)絡(luò)MANETs(Mobile Ad Hoc Networks)是由移動節(jié)點組成的無中心無線網(wǎng)絡(luò)[1]。MANETs未采用任何固定的基礎(chǔ)設(shè)施,屬于自治系統(tǒng)、能夠自行組網(wǎng),已應用于抗險救災、科學考察等領(lǐng)域。MANETs內(nèi)的節(jié)點既可充當主機,又具有路由功能。

然而,節(jié)點的自由移動導致網(wǎng)絡(luò)拓撲呈動態(tài)變化。這就使得節(jié)點間的通信鏈路不穩(wěn)定。為此,研究人員對MANETs路由協(xié)議進行了大量研究?，F(xiàn)有的MANETs路由可分兩大類:①反應式按需路由;②先應式表驅(qū)路由。而按需距離矢量AODV(Ad Hoc On-demand Distance Vector)[2]就典型的反應式按需路由。

然而,若鏈路斷裂或發(fā)現(xiàn)更短的路徑時可能會發(fā)生路由重建,而依照AODV的路由策略,重建路由的成本過高[3]。此外,一旦鏈路已斷裂,再去重建路由往往會導致數(shù)據(jù)包的丟失。而鏈路的連通時間直接反映了鏈路能否連通或斷裂。因此,可通過預測鏈路的連通時間,提前判斷鏈路是否能完成數(shù)據(jù)包的傳輸,進而提高數(shù)據(jù)包傳輸成功率。

據(jù)此,研究人員針對鏈路預測問題,進行了較深入研究。例如,文獻[4]通過計算節(jié)點移動速度差對AODV進行改進。先用速度差最小的鏈路構(gòu)建路由,進而提高路由的穩(wěn)定性。文獻[5]針對鏈路斷裂問題,采用鏈路時間預測及路由重建方案,并引用鏈路備份機制。文獻[5]提出基于冗余機制的AODV路由RAODV(Reduntant AODV)。RAODV路由引用多路徑路由。文獻[6]引用牛頓均差插值多項式預測鏈路的鏈路的連通時間,并預測節(jié)點的剩余時間。

盡管這些方案考慮了鏈路連通時間,并從預測鏈路連通時間角度,緩解鏈路斷裂問題。但是,在構(gòu)建路由時,只考慮鏈路連通時間是遠遠不夠。路由的穩(wěn)定性受多個因素影響。

為此,針對MANETs的路由,提出基于節(jié)點運動信息的鏈路穩(wěn)定路由LDPR。LDPR路由利用節(jié)點的運動信息估計鏈路的生存時間,并考慮雙路由機制。再通過鏈路生存時間構(gòu)建路由,選擇路由生存時間長的路由傳輸數(shù)據(jù),進而提高路由的穩(wěn)定性。

1 LDPR路由

LDPR路由先依據(jù)節(jié)點運動信息估計鏈路連通時間。然后,再估計鏈路長度。

1.1 鏈路連通時間

LDPR路由利用節(jié)點間的相對速度矢量估計這兩個節(jié)點所連通的鏈路時間[7-8]。

以節(jié)點i和節(jié)點j為例,分析估計它們間鏈路的連通時間。令節(jié)點i和節(jié)點j在時刻t1的速度矢量?i和?j。它們的相對矢量矢量可表示為:

Δ?=?j-?i

(1)

為了簡化分析,將節(jié)點i視為固定不動,節(jié)點j以相對速度矢量Δ?進行移動。在時刻t1,節(jié)點j在節(jié)點i的通信范圍內(nèi)[9-10]。當節(jié)點j運動了一段時間t,節(jié)點j可能會離開節(jié)點i的通信范圍,移動至位置A,如圖1所示。

圖1 鏈路穩(wěn)定性預測模型

令?表示節(jié)點j在時間t內(nèi)所移動的距離。依據(jù)余弦定理,可建立方式(2):

R2=?2+d2-2?dcos(π-θ)?=(?+dcosθ)2+(dsinθ)2

(2)

其中R表示節(jié)點的通信半徑。d為在時刻t1節(jié)點i與節(jié)點j間的距離。而距離d可用式(3)進行計算:

(3)

其中(xi,yi)、(xj,yj)分別表示節(jié)點i與節(jié)點j在時刻t1的位置坐標。

對式(2)進行變換,可求解?,使其成為關(guān)于d、θ和R的函數(shù)。

(4)

接下來,結(jié)合圖1計算角度β:

(5)

此外,用另一種形式表述相對速度矢量Δ?:

Δ?=|Δ?|∠φ

(6)

其中|Δ?|表示Δ?的幅度,∠φ表示兩個速度的角度值。

而三個角度φ、β和θ滿足式(7):

θ=φ-β

(7)

最后,可利用?(d,θ)和|Δ?|計算鏈路的生存時間T:

(8)

1.2 雙路由機制

由于節(jié)點的移動性,單一路由往往難以成功地傳輸數(shù)據(jù)。而一旦路由斷裂,又需重新啟動路由機制[11],增加了網(wǎng)絡(luò)開銷和數(shù)據(jù)傳輸時延。為此,LDPR路由引用雙路由機制。源節(jié)點同時維護兩條路由,一條路由作為主路由,另一條路由作為備份路由。當主路由斷裂,就啟用備份路由傳輸數(shù)據(jù)。

LDPR路由先預測鏈路的生存時間,并在鏈路斷開之前啟動備份路由,減少了路由切換以及重新發(fā)現(xiàn)路由的時間。

如圖2所示,假定節(jié)點S需要向節(jié)點D傳輸數(shù)據(jù)Data。首先,節(jié)點S向鄰居廣播路由請求控制包RREQ。當節(jié)點D接收了RREQ包后,節(jié)點D就依著傳輸RREQ路徑返回RREP包。

圖2 雙路由的網(wǎng)絡(luò)拓撲

從圖2可知,節(jié)點S至節(jié)點D有兩條路徑:S→1→2→3→D和S→1→4→5→6→D。將S→1→2→3→D作為主路由,而S→1→4→5→6→D作為備份路由。一旦主路由斷開,就直接啟用備份路由,而無需又重新發(fā)現(xiàn)路由,縮短了傳輸時延。

在使用主路由傳輸數(shù)據(jù)時,監(jiān)測每條鏈路的生存時間。一旦預測鏈路即將斷裂,就啟用備份路由。如圖2所示,假定預測鏈路1→4斷裂,就在斷裂的同時,啟用備份路由。

當然,若擁有備份路由,就直接啟用備份路由。若沒有備份路由,就將數(shù)據(jù)緩存于隊列。并同時觸發(fā)發(fā)現(xiàn)路由工作。

1.3 路由的生存時間

每條路由可能由一條或多條鏈路構(gòu)成。而路由的生存時間取決于多條鏈路的連通時間的最小值。具體而言,假定路由Ln-1由n-1條鏈路構(gòu)成。這n-1條鏈路由n個節(jié)點構(gòu)成。鏈路ij表示由節(jié)點i與節(jié)點j所構(gòu)成的鏈路,i=1,2,…,n,且i≠j。因此,路由Ln-1的生存時間ETn-1可表示為:

(9)

其中Tij表示鏈路ij的連通時間。

路由生成

當源節(jié)點S需要向目的節(jié)點D傳輸數(shù)據(jù)時,源節(jié)點S就廣播RREQ。當接收了RREQ包,首先判斷是否之前已接收過此RREQ包。若已接收,則直接丟棄,否則就繼續(xù)向鄰居節(jié)點轉(zhuǎn)播[12],直至將RREQ包傳輸至目的節(jié)點D。

當目的節(jié)點D接收了RREQ,就沿著傳輸RREQ包的路徑返回RREP包。當源節(jié)點S接收到RREP包,源節(jié)點就能獲取連至目的節(jié)點路徑。RREQ包和RREQ包的傳輸過程如圖3所示。

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

當構(gòu)建了路由之后,源節(jié)點就計算路由的生存時間,并從中選擇生存時間長的兩條路由,將生存時間最長的路由作為主用路由,另一條路由作為備份路由。

2 仿真分析

2.1 仿真環(huán)境

為了更好地分析LDPR路由,利用NS-2.35軟件進行分析。令50至200個移動節(jié)點隨機分布于1 000 m×300 m的矩形中,其中10個節(jié)點作為源節(jié)點,它們周期地產(chǎn)生數(shù)據(jù)包,且數(shù)據(jù)包大小為512 byte。每個節(jié)點的傳輸半徑250 m。節(jié)點的最大移動速度為30 m/s。具體地仿真參數(shù)如表1所示。

表1 網(wǎng)絡(luò)仿真參數(shù)

選用RAODV和AODV-P[13]作為參照,并分析它們的路由開銷、吞吐量和數(shù)據(jù)傳輸時延。同時,考查節(jié)點移動速度對路由性能的影響。每次實驗獨立重復50次,取均值繪制圖。

2.2 數(shù)值分析

2.2.1 實驗一

本次實驗分析節(jié)點數(shù)對路由性能的影響。節(jié)點數(shù)從50變化至200,節(jié)點最大移動速度為10 m/s。

圖4顯示了路由開銷率隨節(jié)點數(shù)的變化情況。路由開銷率等于成功傳輸一個數(shù)據(jù)包數(shù)與所需傳輸指控制包的數(shù)之比。

從圖4可知,路由開銷率隨節(jié)點數(shù)的增加而上升。這主要是因為:節(jié)點數(shù)的增加,加大了節(jié)點對信道的競爭。競爭越激烈,構(gòu)建路由越困難。這就使得需要多次傳輸控制包,可能才會建立一條路由。與RAODV和AODV-P路由相比,提出的LDPR路由有效地控制了路由開銷。

圖4 路由開銷率隨節(jié)點數(shù)的變化情況

圖5顯示平均吞吐量隨節(jié)點數(shù)的變化情況。從圖5可知,平均吞吐量隨節(jié)點數(shù)增加而下降。原因在于:節(jié)點數(shù)越多,信道越擁塞,數(shù)據(jù)傳輸越不流暢。這必然限制了網(wǎng)絡(luò)吞吐量。此外,相比于RAODV和AODV-P路由,LDPR路由的吞吐量得到提高,略高于AODV-P路由。

圖5 平均吞吐量隨節(jié)點數(shù)的變化情況

圖6顯示了三個協(xié)議的端到端傳輸時延。從圖6可知,節(jié)點數(shù)的增加提高了數(shù)據(jù)傳輸時延。但是,相比RAODV和AODV-P路由,LDPR路由的傳輸時延較低。這歸功于,LDPR路由提前預測鏈路連通時間,避免了因路由斷裂而重新構(gòu)建路由的時間。

圖6 端到端傳輸時延隨節(jié)點數(shù)的變化情況

2.2.2 實驗二

本次實驗分析節(jié)點移動速度對路由性能的影響。節(jié)點數(shù)為200,節(jié)點最大移動速度從5 m/s至30 m/s變化。

圖7顯示了端到端傳輸時延隨移動速度的變化情況。從圖7可知,三個路由協(xié)議的端到端傳輸時延隨風節(jié)點最大速度地增加而上升。原因在于:節(jié)點移動速度越快,網(wǎng)絡(luò)拓撲變化激烈,路由連通時間就短,這就增加了數(shù)據(jù)傳輸時延。此外,相比于RAODV和AODV-P路由,LDPR路由的時延得到有效控制。這歸功于:LDPR路由提高了路由的穩(wěn)定性,降低路由中斷頻率。

圖7 端到端傳輸時延隨節(jié)點移動速度的變化情況

圖8顯示三個協(xié)議的路由開銷率隨節(jié)點移動速度的變化情況。從圖8可知,節(jié)點移動速度增加,加大了路由開銷率。原因在于:節(jié)點移動越快,路由斷裂概率越高,這就需要頻繁地重建路由,必然增加路由開銷。相比于RAODV和AODV-P路由,LDPR路由開銷率得到有效控制。

圖8 平均路由開銷率隨節(jié)點移動速度的變化情況

3 總結(jié)

節(jié)點的移動加劇了移動Ad Hoc網(wǎng)絡(luò)拓撲變化,這給路由設(shè)計提出了挑戰(zhàn)。本文提出基于鏈路連通時間預測路由LDPR。LDPR路由先依據(jù)節(jié)點運動信息預測鏈路的生成時間,并引用雙路由機制傳輸數(shù)據(jù)包。實驗數(shù)據(jù)表明,提出的LDPR路由縮短了傳輸時延,并控制了路由開銷。后期,將擴大應用場景,如車聯(lián)網(wǎng)。車聯(lián)網(wǎng)是移動Ad Hoc網(wǎng)絡(luò)的特例。在車聯(lián)網(wǎng)中,車輛移動較快,對路由要求更嚴格。后期,將LDPR路由應用于車聯(lián)網(wǎng),這將是后期的研究方向。