車載網中面向高速場景的路由算法

臧冠男+沈繼偉+林洋

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

關鍵詞： 連通概率； 路由； 移動模型； 路徑； 時延； 車聯網

中圖分類號： TN711?34； TP393 文獻標識碼： 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

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

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

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

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

1 網絡模型

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

2 CPB協議

CPB協議在傳輸數據時，總是選擇連通概率最高的路徑作為數據傳輸路由。

2.1 連通概率

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

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

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

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

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

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

3 性能分析

3.1 仿真場景

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

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

3.2 數值分析

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

3.2.1 端到端傳輸時延

平均速度越高，端到端時延越大。原因在于車速的提高，加劇了拓撲結構的動態變化，降低了路徑的連通率，使得路由不穩定。最終，就增加傳輸時延。相比于AODV和VADD路由算法，CPB算法的時延得到有效的縮減。這歸功于CPB算法依據路徑的連通率決策路由，避免了連通率的路徑作為數據傳輸，提高了路由的穩定性。平均時延隨平均車速的影響如圖5所示。

3.2.2 數據包傳遞率

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

吞吐量隨車速的增加而下降，這主要是因為車速的提高增加傳輸時延（如圖5所示），降低了傳輸效率，同時，又減少了數據包傳遞率（如圖6所示），最終導致數據吞吐量的下降。然而，由于CPB路由算法依據路徑連通率選擇路由，提高了應對動態拓撲變化的能力。

4 總 結

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

參考文獻

[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中基于鏈路的可持續時間路由方案[J].科學技術與工程，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路由協議研究[J].現代電子技術，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