面向高速場景的基于路徑連通概率路由協議*

尹鴻坦

(黃淮學院信息工程學院,河南 駐馬店 463000)

面向高速場景的基于路徑連通概率路由協議*

尹鴻坦*

(黃淮學院信息工程學院,河南 駐馬店 463000)

有效地傳輸數據是提高車聯網VANETs(Vehicular Ad Hoc Networks,)應用性能的關鍵。而動態的拓撲結構,給VANETs的數據傳輸提出了挑戰。為此,提出基于路徑連通概率的車聯網路由算法CPR(Connected Probability-Based Routing)。首先,依據高速公路場景,建立一維車輛移動模型,然后再計算鏈路的連通概率,最后,計算路徑的連通概率,并選擇連通概率最高的路徑傳輸數據。仿真結果表明,提出的CPB算法能夠有效地提高數據包傳遞率、端到端傳輸時延以及吞吐量性能。

連通概率;路由;移動模型;車聯網

目前,汽車已成為民眾出行的首選交通工具,汽車便捷民眾的日常出行。然而,隨著汽車數量的增加,道路擁塞、交通安全問題也日益突出。據不完全統計,交通事故已成第2大殺手。世界衛生組織WMO指出每年約130萬人死于交通事故,約5 000萬人受傷[1]。據此,政府部門以及科研機構開始商討、并提出利用智能交通概念,提高交通安全。作為智能交通系統的最有前景技術,車聯網 VANETs(Vehicular Ad Hoc Networks)受到廣泛關注。

典型的車聯網結構如圖1所示。裝有OBU模塊的車輛能夠與其他車輛、路邊設施進行通信。其中車與車之間的通信稱為車間通信V2V(Vehicle to Vehicle),而車與路旁設備通信稱為車-旁通信V2R(Vehicle to Roadside unit)。車輛間通過實時交互路狀信息,實現對事故的預警以及避讓,進而提高交通管理效率以及交通安全。據美國交通局統計,通過車聯網技術平臺,能夠將交通事故率降低82%。

圖1 VANET的網絡模型

從技術層面而言,車聯網VANETs屬于移動自組織網絡,但VANETs具有鮮明的特性,如動態的拓撲、受限的移動模型、車輛的高速移動。這些特性給VANETs的消息傳輸提出了挑戰。據此,眾多研究學者關注VANETs中的路由技術[2-5]。

值得注意得是,車輛移動受限于道路的拓撲結構,并且道路的拓撲結構是靜態,至少在短時間內道路結構是不會變化,這一特性給車輛移動預測提供了基礎。通過對車輛移動的預測,可有效地計算鏈路的連通特性,包括連通概率、連通持續時間等。

文獻[6]提出基于鏈路連接概率的路由協議。先計算鏈路連接概率,并由此估算鏈路連通時間,從而選擇最穩定、可靠的路徑作為數據傳輸通道。文獻[7]提出面向高速道路場景的車輛移動預測模型。此外,文獻[8]也提出基于移動預測的MOPR路由協議。MOPR協議先預測車輛的下一時刻位置,然后再估算數據傳輸至此位置所需的時間。隨后,檢測鏈路在數據傳輸時間內是否一直保持連接狀態。

本文基于上述文獻的分析,考慮到VANETs的移動區域局限性、移動信息的可預測性,提出基于路徑連通概率的VANETs路由算法CPB。CPB算法通過路徑連通概率決策路由,提高路由應對動態拓撲的魯棒性。

1 網絡模型

以高速公路為研究對象,并建立相應的網絡模型。依據IEEE802.p的標準,車輛的一跳通信半徑為300 m,其遠大于道路寬度。據此,可將高速公路場景模擬成一維的網絡模型。

在高速公路的場景中,車輛駛入公路服從泊松分布[9]。假定泊松分布的參數為λ,那么在時間[0,t]范圍內,有m輛車駛入道路的概率Pr:

(1)

式中:N(t)在時間[0,t]駛入公路的車輛數。

當公路上有多輛車時,車與車之間的間隔服從指數分布,且參數為α。假定第i個間隔為Ti,那么在時間[0,t]內可容納的間隔數為M(t),且M(t)服從參數為αt的泊松分布。

對于個體車輛υk,它以vi,k速度在第i個間隔Ti,k內移動。車輛υk所移動的距離Si,k=vi,k×Ti,k。因此,在時間[0,t]內,車輛υk移動的距離Sk(t):

(2)

依據統計學知識,Sk(t)服從復合泊松過程[10]。相應地,它的均值、方差可依式(3)、(4)計算。

E[Sk(t)]=αtE[Si,k]=μt

(3)

(4)

為了簡化描述,根據中心極限定理[9],將Sk(t)分布視為正態分布。在道路中,車輛間的狀態可通過其觀察車輛進入道路時間差進行描述。仍假定車輛υk,其觀察車輛進入道路的時間為t,并且它們進入道路的時差為τ。

若τ大于零,則意味著觀察車輛先進入道路,若τ小于零,則說明觀察車輛后進入道路。據此,Sk(t+τ)等于在時間[0,t]內車輛υk所移動的距離,且服從正態分布,其中均值、方差分別如式(5)、式(6)所示:

E[Sk(t+τ)]=μ(t+τ)

(5)

(6)

利用車輛υk與觀察車輛所移動距離差,表征它們的相對距離,即Dr=S(t+τ)-S(t)。它的均值、方差如式(7)、式(8)所示:

E[Dr]=μτ

(7)

(8)

(9)

2 CPB協議

CPB協議旨在提高網絡連通率,保證數據傳輸傳遞率。為此,CPB協議先計算節點間的連通率(鏈路連通率),然后再計算路徑連通率,最后選擇路徑連通率最高的路徑傳輸數據包。整個CPB協議工作流程如圖2所示。

圖2 CPB協議建立數據傳輸路徑

2.1 連通概率

當源節點(車輛)需要向目的節點傳輸數據時,源節點首先需要計算自己與下一跳節點間連通概率,換而言之,選擇連通概率最高的節點作為下一跳轉發節點。

圖3 在建立鏈路時期內的兩跳間接通信

如圖3所示,源節點A與目的節點C均沿著左向右行駛。假定節點A、B和B、C間距離表示為dAB、dBC。相應地,dAC表示節點A、C間的距離。如果距離dAC小于通信范圍R,則直接通信。反之,節點A需要選擇下一跳節點作為轉發節點。接下來,以圖3為例,分析選擇下一跳節點的過程。

若節點A在時刻t=0進入系統,而在時刻t=t1節點A的位置為x,且x∈[-2R,2R]。此時節點A與目的節點C構建了數據傳輸路徑。由于它們彼此不在一跳鄰居通信范圍內,需要通過中間轉發節點進行轉發數據。轉發區域如圖3所示的陰影區域,即在[-R,x+R]區域為它們的轉發區域[11]。若在該區域內存在節點,則這些節點可成為轉發節點。

接下來,估計轉發區域內的節點(車輛)進入[-R,x+R]區域的時間,與目的節點C的時間差為τ的概率Pτ1(x),即在t=t1時刻建立連通的概率。依據式(9),可計算Pτ1(x):

(10)

由于車輛駛入時刻t服從(-t1/2,t1/2)區域的均勻分布。如果τ?(-t1/2,t1/2),則意味著車輛在時刻t=t1駛入區域[-R,x+R]的概率太小,換而言之,區域[-R,x+R]內沒有節點能與目的節點C建立連通。在這種情況,源節點A只能采取存儲-轉發策略,直至轉發區域內有節點才進行轉發。

當然,或許在時刻t=t1有m輛車駛入道路。在這種情況下,任意一輛車出現在[-R,x+R]的區域的概率

(11)

依據式(11)可知,在區域[-R,x+R]內無任何車輛的概率可表示為1-Pt1(x)。

(12)

exp(-λtPt1(x))

(13)

最后,將式(13)代入(12)便可計算連通概率:

(14)

2.2 路由決策

提出的CPB算法是以選擇連通概率最高的路徑為原則進行路由決策。當源節點需要傳輸數據時,首先計算每條通往目的節點路徑的連通概率[12],然后從中選擇概率最高的路徑作為數據傳輸通道。

對于每一條路徑(假定為路徑l),若該條路徑Pathl由n條鏈路組成。而每條鏈路的連通概率表示為Ph(h=1,2,…,n)。據此,整條路徑Pathl的連通概率:

(15)

最后,源節點選擇連通概率最大的路徑作為數據傳輸通道。

圖4 路由發現流程

2.3 路由發現流程

當節點需要傳輸數據包時,節點就先鄰居廣播請求數據包RREQ。一旦接收了RREQ包,節點就先判斷是否之前已接收了RREQ,若是,則丟棄,否則,就依據式(14)計算連通概率,并加載到RREQ,再轉發。重復上述過程,直到目的節點接收了RREQ包。目的節點可能接收了來自多條路徑傳輸的RREQ包。為此,目的節點依據式(15)計算每條路徑的連通率,再選擇連通率最大的路徑作為數據傳輸通路。然后,目的節點依據所選擇的路徑回復ACK。當源節點接收了ACK后,再依據此路徑向目的節點傳輸數據包。整個路由發現流程如圖4所示。

以圖5為例,描述CPB協議的路由決策過程。源節點A首先發送路徑請求消息Mes_req。接收節點B先計算與節點A的連接概率,再將此概率值載入Mes_req,并轉發。每個接收節點均重復上述過程,直到目的節點F接收到此消息Mes_req。

圖5 路由選擇過程

由圖5可知,由{A→B→C→E→F}、{A→B→D→E→F}兩條路徑到節點F,并且這兩條路徑的連通概率PPathl分別為0.028 8、0.048 0。這表明路徑{A→B→D→E→F}比路徑{A→B→C→E→F}的連接時間更短,路徑更趨于穩定。因此,節點F選擇路徑{A→B→D→E→F},并沿著該路徑的反方向向源節點A回復ACK消息,如圖5(b)所示。

3 性能分析

3.2 仿真場景

為了更好地分析CPB路由性能,利用NS2.35建立仿真平臺。考慮長為L=4 000 m的三車道的高速場景,車輛的通信半徑為300 m,如圖6所示。具體的仿真參數如表1所示。

圖6 高速公路仿真場景

參數數值公路長度4000m車道數3最小車速40km/h最大車速120km/h車輛通信范圍250m仿真時間100s

在仿真過程中,選擇VADD[13]和AODV[14]路由算法作為參考,并與CPB算法進行比較。AODV路由是經典的車聯網路由協議,而VADD路由也是以提高數據傳輸率為目的路由協議。這兩個路由與CPR路由具有可比性。此外,從吞吐量、數據傳輸的端到端傳輸時延以及數據包傳遞率3方面分析路由算法的性能。

3.2 數值分析

接下來,分析車輛速度對端到端傳輸時延(E2E)、吞吐量(Throughput)以及數據包傳輸率的影響。其中,端到端傳輸時延是指數據包從源節點傳輸至目的節點的平均時延;而數據包傳輸率是指數據包傳輸成功率,其等于目的節點所接收的數據包數;吞吐量是指單位時間內網絡內所傳輸的數據量。

實驗以隨機方式產生數據包源節點(車輛)和目的節點(車輛),并考慮變化車速對路由協議性能的影響。

①端到端傳輸時延

平均速度越高,端到端時延越大。原因在于車速的提高,加劇了拓撲結構的動態變化,降低了路徑的連通率,使得路由不穩定。最終,增加數據包傳輸時延。

從圖7可知,相比于AODV和VADD路由算法,CPB算法的時延得到有效地縮減。例如,當平均車速在70 km/h時,CPB的端到端時延約為3 s,而VADD和AODV時延分別為3.5 s和4.75 s。這歸功于CPB算法依據路徑的連通率決策路由,避免了連通率低的路徑作為數據傳輸,提高了路由的穩定性。而AODV和VADD發現路由時并沒有從路由穩定性角度出發。對于拓撲變化的車聯網而言,路由的不穩定性是制約路由性能的關鍵因素。

圖7 平均時延隨平均車速的影響

②數據包傳遞率

數據包傳遞率隨車速變化情況如圖8所示。平均車速越大,數據包傳遞率越低。原因在于,車速的提高了,加速了網絡拓撲的動態變化性,最終導致路徑不穩定,進而降低了數據包傳輸率。與AODV和VADD路由相比,CPB路由數據包傳遞率得到有效地提高。例如,在平均車速在80 km/h時,CPB路由的所接收的數據包數達到43,而AODV協議只有32個。

圖8 數據包傳輸率隨車平均速度的變化

③吞吐量

最后,分析了車速對吞吐量的性能影響,實驗數據如圖9所示。從圖9可知,吞吐量隨車速的增加而下降。這主要是因為車速的提高,增加傳輸時延,降低了傳輸效率,同時,又減少了數據包傳遞率,最終導致數據吞吐量的下降。然而,由于CPB路由算法依據路徑連通率選擇路由,提高了應對動態拓撲變化的能力。

圖9 吞吐量隨車平均速度的影響

圖10 平均路由開銷隨車平均速度的影響

④路由開銷

最后,利用路由開銷反映算法復雜性。路由開銷越大,說明路由算法越復雜。路由開銷是每接收一個數據包所產生的控制包個數。從圖10可知,CPB的路由開銷低于AODV路由協議,但高于VADD協議。原因在于:CPB路由協議在發現路由時,采用了請求包和控制包,這增加了路由開銷。

4 總結

本文針對車聯網的數據傳輸問題,提出基于路徑連通概率的路由算法CPB。CPB算法考慮了車輛的高速移動對路由穩定性的影響。CPB算法計算鏈路的連通率,并估算路徑的連通概率。在決策路由時,總是選擇連通概率最高的路徑作為數據傳輸通道,進而提高數據傳輸效率。仿真結果驗證路由算法的性能。與AODV和VADD路由算法相比,CPB路由算法的端到端傳輸時延、吞吐量以及數據傳遞率性能均得到有效地提高。

[1]Casteigts A,Nayak A,Stojmenovic I. Communication Protocolsfor Vehicular Ad Hoc Networks[J]. Wireless Communication Mobile Computer,2011,11(5):567-582.

[2]Shafiee K,Leung V C M. Connectivity-Aware Minimum-Delay Geographic Routing with Vehicle Tracking in VANETs[J]. Ad Hoc Networks,2011,9(2):131-141.

[3]Biswas S,Morris R. ExOR:Opportunistic Routing in Multi-Hop Wireless Networks[C]//Proc ACM SIGCOMM,2012:133-144.

[4]徐子豪,張騰飛. 基于語音識別和無線傳感網絡的智能家居系統設計[J]. 計算機測量與控制,2012,12(1):12-18.

[5]周凱,孟利民,華驚宇. 基于Grover路由策略的無線傳感網絡剩余容量構造與研究[J]. 傳感技術學報,2015,28(2):249-253.

[6]Li Y,Chen W,Zhang Z L. Optimal Forwarder List Selection in Opportunistic Routing[C]//Proc IEEE MeshTech,2010:670-675.

[7]Namboodiri V,Gao L. Prediction-Based Routing for Vehicular Ad Hoc Networks[J]. IEEE Transactions on Vehicular Technology,2012,56(4):2332-2345.

[8]Menouar H,Lenardi M,Filali F. A Movement Prediction Based Routing Protocol for Vehicle to Vehicle Communication[C]//Proc V2VCOM,San Diego,CA,Jul. 2015:75-82.

[9]Hafeez K,Zhao L,Liao Z,et al. Impact of Mobility on VANETs’ Safety Applications[C]//Global Telecommunications Conference(GLOBECOM 2010),2010 IEEE,Dec. 2010:1-5.

[10]Zhao M,Li Y,Wang W. Modeling and Analytical Study of Link Properties in Multi-Hop Wireless Networks[J]. IEEE Transactions on Communications,2012,60(2):445-455.

[11]王佩雪,羅菁. VANETs中基于鏈路的可持續時間路由方案[J]. 科學技術與工程,2014,14(25):267-272.

[12]張莉華,張得生. 基于連接概率的VANETs路由協議研究[J]. 現代電子技術,2016,39(7):19-24.

[13]Zhao J,Cao G. VADD:Vehicle-Assisted Data Delivery in Vehicular Ad Hoc Networks[J]. IEEE Transactions Vehicular Technology,2011,57(3):1910-1922.

[14]Xia Zijun,Liu Chunfeng,Zhao Zenghua. Routing Algorithm in Vehicular Ad Hoc Network Based on Link Prediction[J]. Computer Engineering,2012,38(4):110-114.

Connected Probability-Based Routing for HighwayScenario Vehicular Ad Hoc Networks*

YINHongtan*

(College of Information Engineering,HuangHuai University,Zhumadian He’nan 463000,China)

To transmit effectively data is key issue of improving the application performance of Vehicular ad hoc networks(VANETs). However,dynamic topology is great challenge for transmitting data. Therefore,Connected Probability-Based routing(CPR)was proposed in this paper. Firstly,according to highway scenario,the one-dimension vehicle mobile model was established. Secondly,the connected probability of link was estimated. Finally,the connected probability of path was computed,and the path with maximum connected probability was selected to transmit data. Simulation results show that the proposed CPB algorithm has better performance in terms of packet delivery ratio,end-to-end delay and throughput.

connected probability;routing;mobility model;VANETs

尹鴻坦(1987-)，男，河南汝南人，碩士，研究方向為云計算，大數據。

項目來源:河南省科技廳項目(162102110119);國家自然科學基金項目(51406140)

2017-01-18 修改日期:2017-05-05

TP393

A

1004-1699(2017)08-1281-06

C:7230

10.3969/j.issn.1004-1699.2017.08.025