基于鏈路時間預測的移動Ad Hoc網路由

胡 君,葉俊杰

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

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

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

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

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

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

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

1 LDPR路由

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

1.1 鏈路連通時間

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

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

Δ?=?j-?i

(1)

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

圖1 鏈路穩定性預測模型

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

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

(2)

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

(3)

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

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

(4)

接下來,結合圖1計算角度β:

(5)

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

Δ?=|Δ?|∠φ

(6)

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

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

θ=φ-β

(7)

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

(8)

1.2 雙路由機制

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

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

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

圖2 雙路由的網絡拓撲

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

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

當然,若擁有備份路由,就直接啟用備份路由。若沒有備份路由,就將數據緩存于隊列。并同時觸發發現路由工作。

1.3 路由的生存時間

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

(9)

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

路由生成

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

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

圖3 路由發現過程

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

2 仿真分析

2.1 仿真環境

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

表1 網絡仿真參數

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

2.2 數值分析

2.2.1 實驗一

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

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

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

圖4 路由開銷率隨節點數的變化情況

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

圖5 平均吞吐量隨節點數的變化情況

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

圖6 端到端傳輸時延隨節點數的變化情況

2.2.2 實驗二

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

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

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

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

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

3 總結

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