胡 君,葉俊杰

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

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

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

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

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

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

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

1 LDPR路由

LDPR路由先依據(jù)節(jié)點(diǎn)運(yùn)動(dòng)信息估計(jì)鏈路連通時(shí)間。然后,再估計(jì)鏈路長度。

1.1 鏈路連通時(shí)間

LDPR路由利用節(jié)點(diǎn)間的相對(duì)速度矢量估計(jì)這兩個(gè)節(jié)點(diǎn)所連通的鏈路時(shí)間[7-8]。

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

Δ?=?j-?i

(1)

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

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

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

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

(2)

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

(3)

其中(xi,yi)、(xj,yj)分別表示節(jié)點(diǎn)i與節(jié)點(diǎn)j在時(shí)刻t1的位置坐標(biāo)。

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

(4)

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

(5)

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

Δ?=|Δ?|∠φ

(6)

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

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

θ=φ-β

(7)

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

(8)

1.2 雙路由機(jī)制

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

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

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

圖2 雙路由的網(wǎng)絡(luò)拓?fù)?/p>

從圖2可知,節(jié)點(diǎn)S至節(jié)點(diǎn)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í)延。

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

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

1.3 路由的生存時(shí)間

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

(9)

其中Tij表示鏈路ij的連通時(shí)間。

路由生成

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

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

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

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

2 仿真分析

2.1 仿真環(huán)境

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

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

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

2.2 數(shù)值分析

2.2.1 實(shí)驗(yàn)一

本次實(shí)驗(yàn)分析節(jié)點(diǎn)數(shù)對(duì)路由性能的影響。節(jié)點(diǎn)數(shù)從50變化至200,節(jié)點(diǎn)最大移動(dòng)速度為10 m/s。

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

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

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

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

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

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

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

2.2.2 實(shí)驗(yàn)二

本次實(shí)驗(yàn)分析節(jié)點(diǎn)移動(dòng)速度對(duì)路由性能的影響。節(jié)點(diǎn)數(shù)為200,節(jié)點(diǎn)最大移動(dòng)速度從5 m/s至30 m/s變化。

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

圖7 端到端傳輸時(shí)延隨節(jié)點(diǎn)移動(dòng)速度的變化情況

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

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

3 總結(jié)

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