車載網(wǎng)中面向高速場景的路由算法

臧冠男+沈繼偉+林洋

摘 要： 有效地傳輸數(shù)據(jù)是提高車聯(lián)網(wǎng)應(yīng)用性能的關(guān)鍵。而動(dòng)態(tài)的拓?fù)浣Y(jié)構(gòu)，給車聯(lián)網(wǎng)的數(shù)據(jù)傳輸提出了挑戰(zhàn)。為此，提出基于路徑連通概率的車聯(lián)網(wǎng)路由算法CPB。首先，依據(jù)高速公路場景，建立一維車輛移動(dòng)模型，然后再計(jì)算鏈路的連通概率，最后，計(jì)算路徑的連通概率，并選擇連通概率最高的路徑傳輸數(shù)據(jù)。仿真結(jié)果表明，提出的CPB算法能夠有效地提高數(shù)據(jù)包傳遞率、端到端傳輸時(shí)延以及吞吐量性能。

關(guān)鍵詞： 連通概率； 路由； 移動(dòng)模型； 路徑； 時(shí)延； 車聯(lián)網(wǎng)

中圖分類號： TN711?34； TP393 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2018）04?0164?05

Abstract： Effective data transmission is the key to improving the application performance of vehicular ad hoc networks （VANETs）. However， dynamic topology is a great challenge for VANETs′ data transmission. Therefore， a path connection probability based routing algorithm for VANETs is proposed. The one?dimensional vehicle mobility model is established according to the highway scenario. The link connection probability is computed. The path connection probability is computed， and the path with maximum connection probability is selected to transmit data. The simulation results show that the proposed CPB algorithm can effectively improve the performance in delivery ratio of data packet， end?to?end transmission delay and throughput.

Keywords： connection probability； routing； mobility model； path； delay； VANETs

目前，汽車已成為民眾出行的首選交通工具，汽車便捷民眾的日常出行，然而，隨著汽車數(shù)量的增加，道路擁塞、交通安全問題也日益突出。據(jù)不完全統(tǒng)計(jì)，交通事故已成第二大殺手。世界衛(wèi)生組織WMO指出每年約130萬人死于交通事故，約5 000萬人受傷[1]。據(jù)此，政府部門以及科研機(jī)構(gòu)開始商討、并提出利用智能交通概念，提高交通安全。作為智能交通系統(tǒng)的最有前景技術(shù)，車聯(lián)網(wǎng) （Vehicular Ad hoc Networks，VANETs）受到廣泛關(guān)注。典型的車聯(lián)網(wǎng)結(jié)構(gòu)如圖1所示。裝有OBU模塊的車輛能夠與其他車輛、路邊設(shè)施進(jìn)行通信。其中車與車之間的通信稱為車間通信V2V（Vehicle to Vehicle），而車與路旁設(shè)備通信稱為車?旁通信V2R（Vehicle to Roadside unit）。車輛間通過實(shí)時(shí)交互路狀信息，實(shí)現(xiàn)對事故的預(yù)警以及避讓，進(jìn)而提高交通管理效率以及交通安全。據(jù)美國交通局統(tǒng)計(jì)，通過車聯(lián)網(wǎng)技術(shù)平臺(tái)，能夠?qū)⒔煌ㄊ鹿事式档?2%。從技術(shù)層面而言，車聯(lián)網(wǎng)VANETs屬于移動(dòng)自組織網(wǎng)絡(luò)，但VANETs具有鮮明的特性，如動(dòng)態(tài)的拓?fù)洹⑹芟薜囊苿?dòng)模型、車輛的高速移動(dòng)。這些特性給VANETs的消息傳輸提出了挑戰(zhàn)。據(jù)此，眾多研究學(xué)者關(guān)注VANETs中的路由技術(shù)[2?4]。

值得注意的是，車輛移動(dòng)受限于道路的拓?fù)浣Y(jié)構(gòu)，并且道路的拓?fù)浣Y(jié)構(gòu)是靜態(tài)，至少在短時(shí)間內(nèi)道路結(jié)構(gòu)是不會(huì)變化的，這一特性給車輛移動(dòng)預(yù)測提供了基礎(chǔ)。通過對車輛移動(dòng)的預(yù)測，可有效地計(jì)算鏈路的連通特性，包括連通概率、連通持續(xù)時(shí)間等。

文獻(xiàn)[5]提出基于鏈路連接概率的路由協(xié)議。先計(jì)算鏈路連接概率，并由此估算鏈路連通時(shí)間，從而選擇最穩(wěn)定、可靠的路徑作為數(shù)據(jù)傳輸通道。文獻(xiàn)[6]提出面向高速道路場景的車輛移動(dòng)預(yù)測模型。此外，文獻(xiàn)[7]也提出基于移動(dòng)預(yù)測的MOPR路由協(xié)議。MOPR協(xié)議先預(yù)測車輛的下一時(shí)刻位置，然后再估算數(shù)據(jù)傳輸至此位置所需的時(shí)間。隨后，檢測鏈路在數(shù)據(jù)傳輸時(shí)間內(nèi)是否一直保持連接狀態(tài)。

本文基于上述文獻(xiàn)的分析，考慮到VANETs的移動(dòng)區(qū)域局限性、移動(dòng)信息的可預(yù)測性，提出基于路徑連通概率的VANETs路由算法CPB（Connected Probability?Based routing）。CPB算法通過路徑連通概率決策路由可提高路由應(yīng)對動(dòng)態(tài)拓?fù)涞聂敯粜浴?/p>

1 網(wǎng)絡(luò)模型

本文以高速公路為研究對象，并建立相應(yīng)的網(wǎng)絡(luò)模型。依據(jù)IEEE 802.p的標(biāo)準(zhǔn)，車輛的一跳通信半徑為300 m，其遠(yuǎn)大于道路寬度。據(jù)此，可將高速公路場景模擬成一維的網(wǎng)絡(luò)模型。

2 CPB協(xié)議

CPB協(xié)議在傳輸數(shù)據(jù)時(shí)，總是選擇連通概率最高的路徑作為數(shù)據(jù)傳輸路由。

2.1 連通概率

當(dāng)源節(jié)點(diǎn)（車輛）需要向目的節(jié)點(diǎn)傳輸數(shù)據(jù)時(shí)，源節(jié)點(diǎn)首先需要計(jì)算自己與下一跳節(jié)點(diǎn)間連通概率，換而言之，選擇連通概率最高的節(jié)點(diǎn)作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，如圖2所示。

由圖2可知，源節(jié)點(diǎn)A與目的節(jié)點(diǎn)C均沿左向右行駛。假定節(jié)點(diǎn)A，B和B，C間距離表示為[dAB]，[dBC]。相應(yīng)地，[dAC]表示節(jié)點(diǎn)A，C間的距離。如果距離[dAC]小于通信范圍[R]，則直接通信。反之，節(jié)點(diǎn)A需要選擇下一跳節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)。接下來，以圖2為例，分析選擇下一跳節(jié)點(diǎn)的過程。endprint

若節(jié)點(diǎn)A在時(shí)刻[t=0]進(jìn)入系統(tǒng)，而在時(shí)刻[t=t1]節(jié)點(diǎn)A的位置為[x]，且[x∈-2R，2R]。此時(shí)節(jié)點(diǎn)A與目的節(jié)點(diǎn)C構(gòu)建了數(shù)據(jù)傳輸路徑。由于它們彼此不在一跳鄰域通信范圍內(nèi)，需要通過中間轉(zhuǎn)發(fā)節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)數(shù)據(jù)。轉(zhuǎn)發(fā)區(qū)域?yàn)閳D2所示的陰影區(qū)域，即在[-R，x+R]區(qū)域?yàn)樗鼈兊霓D(zhuǎn)發(fā)區(qū)域[10]。若在該區(qū)域內(nèi)存在節(jié)點(diǎn)，則這些節(jié)點(diǎn)可成為轉(zhuǎn)發(fā)節(jié)點(diǎn)。

最后，源節(jié)點(diǎn)選擇連通概率最大的路徑作為數(shù)據(jù)傳輸通道。

以圖3為例，描述CPB協(xié)議的路由決策過程。源節(jié)點(diǎn)A首先發(fā)送路徑請求消息[Mes_req]，接收節(jié)點(diǎn)B先計(jì)算與節(jié)點(diǎn)A的連接概率，再將此概率值載入[Mes_req]，并轉(zhuǎn)發(fā)。每個(gè)接收節(jié)點(diǎn)均重復(fù)上述過程，直到目的節(jié)點(diǎn)F接收到此消息[Mes_req]。

由圖3可知，由[A→B→C→E→F]和[A→B→D→E→F]兩條路徑到節(jié)點(diǎn)F，并且這兩條路徑的連通概率[PPathl]分別為0.028 8，0.048。這表明路徑[A→B→D→E→F]比路徑[A→B→C→E→F]的連接時(shí)間更短，路徑更趨于穩(wěn)定。因此，節(jié)點(diǎn)F選擇路徑[A→B→D→E→F]，并沿著該路徑的反方向向源節(jié)點(diǎn)A回復(fù)ACK消息，如圖3b）所示。

3 性能分析

3.1 仿真場景

考慮長為[L=4 000 m]的三車道的高速場景，車輛通信半徑為300 m，如圖4所示，具體仿真參數(shù)見表1。

在仿真過程中，選擇VADD[12]和AODV[13]路由算法作為參考，并與CPB算法進(jìn)行比較。AODV路由是經(jīng)典的車聯(lián)網(wǎng)路由協(xié)議，而VADD路由也是以提高數(shù)據(jù)傳輸率為目的路由協(xié)議。這兩個(gè)路由與CPB路由具有可比性。此外，從吞吐量、數(shù)據(jù)傳輸?shù)亩说蕉藗鬏敃r(shí)延以及數(shù)據(jù)包傳遞率三方面分析路由算法的性能。

3.2 數(shù)值分析

接下來，分析車輛速度對端到端傳輸時(shí)延（E2E）、吞吐量（Throughput）以及數(shù)據(jù)包傳輸率的影響。

3.2.1 端到端傳輸時(shí)延

平均速度越高，端到端時(shí)延越大。原因在于車速的提高，加劇了拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)變化，降低了路徑的連通率，使得路由不穩(wěn)定。最終，就增加傳輸時(shí)延。相比于AODV和VADD路由算法，CPB算法的時(shí)延得到有效的縮減。這歸功于CPB算法依據(jù)路徑的連通率決策路由，避免了連通率的路徑作為數(shù)據(jù)傳輸，提高了路由的穩(wěn)定性。平均時(shí)延隨平均車速的影響如圖5所示。

3.2.2 數(shù)據(jù)包傳遞率

數(shù)據(jù)包傳遞率隨車速變化情況如圖6所示。平均車速越大，數(shù)據(jù)包傳遞率越低，這與圖5的數(shù)據(jù)相類似。車速越大，路徑越不穩(wěn)定，數(shù)據(jù)傳輸效率越低，最終降低了數(shù)據(jù)包傳遞率。所以本文提出的CPB算法數(shù)據(jù)包傳遞率優(yōu)于AODV和VADD路由算法。

吞吐量隨車速的增加而下降，這主要是因?yàn)檐囁俚奶岣咴黾觽鬏敃r(shí)延（如圖5所示），降低了傳輸效率，同時(shí)，又減少了數(shù)據(jù)包傳遞率（如圖6所示），最終導(dǎo)致數(shù)據(jù)吞吐量的下降。然而，由于CPB路由算法依據(jù)路徑連通率選擇路由，提高了應(yīng)對動(dòng)態(tài)拓?fù)渥兓哪芰Α?/p>

4 總 結(jié)

本文針對車聯(lián)網(wǎng)的數(shù)據(jù)傳輸問題，提出基于路徑連通概率的路由算法CPB。CPB算法考慮了車輛的高速移動(dòng)對路由穩(wěn)定性的影響，可計(jì)算鏈路的連通率，并估算路徑的連通概率。在決策路由時(shí)，總是選擇連通概率最高的路徑作為數(shù)據(jù)傳輸通道，進(jìn)而提高數(shù)據(jù)的傳輸效率。仿真結(jié)果驗(yàn)證了路由算法的性能。與AODV和VADD路由算法相比，CPB路由算法的端到端傳輸時(shí)延、吞吐量以及數(shù)據(jù)傳遞率性能均得到有效的提高。

參考文獻(xiàn)

[1] CASTEIGTS A， NAYAK A， STOJMENOVIC I. Communication protocols for vehicular ad hoc networks [J]. Wireless communications & mobile computing， 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. Opportunistic routing in multi?hop wireless networks [J]. ACM SIGCOMM computer communications review ， 2004， 34（1）： 69?74.

[4] HARRI J， FIORE M， FILALI F. Vehicular mobility simulation with VantMobiSim [J]. Simulation， 2011， 87（4）： 275?300.

[5] LI Y， CHEN W， ZHANG Z L. Optimal forwarder list selection in opportunistic routing [C]// Proceedings of the IEEE international conference on mobile ad hoc & sensor systems. Macau： IEEE， 2009， 62（124）： 670?675.

[6] NAMBOODIRI V， GAO L. Prediction?based routing for vehicular ad hoc networks [J]. IEEE transactions on vehicular technology， 2012， 56（4）： 2332?2345.

[7] MENOUAR H， LENARDI M， FILALI F. A movement prediction?based routing protocol for vehicle?to?vehicle communications [C]// Proceedings of International V2V Communications Workshop. San Diego： [s. n.]， 2005： 1?7.

[8] Hafeez K， Zhao L， Liao Z， et al. Impact of mobility on VANETs′ safety applications [C]// Proceedings of Global Telecommunications Conference. Miami： IEEE， 2010： 1?5.

[9] 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.

[10] 王佩雪，羅菁.VANETs中基于鏈路的可持續(xù)時(shí)間路由方案[J].科學(xué)技術(shù)與工程，2014，14（25）：267?271.

WANG Peixue， LUO Jing. Link?sustainable time?based routing in vehicular ad hoc networks [J]. Science technology and engineering， 2014， 14（25）： 267?271.

[11] 張莉華，張得生.基于連接概率的VANETs路由協(xié)議研究[J].現(xiàn)代電子技術(shù)，2016，39（7）：19?23.

ZHANG Lihua， ZHANG Desheng. Research on VANETs routing protocol based on connection probability [J]. Modern electronics technique， 2016， 39（7）： 19?23.

[12] ZHAO J， CAO G. VADD： vehicle?assisted data delivery in vehicular ad hoc networks [J]. IEEE transactions on vehicular technology， 2011， 57（3）： 1910?1922.

[13] XIA Zijun， LIU Chunfeng， ZHAO Zenghua. Routing algorithm in vehicular ad hoc network based on link prediction [J]. Computer engineering， 2012， 38（4）： 110?111.endprint