關(guān)于VANETs路由協(xié)議的研究現(xiàn)狀與進展*

，

(1.廣州大學 機械與電氣工程學院，廣東 廣州 510006；2.廣州大學 計算機科學與教育軟件學院，廣東 廣州 510006)

0 引 言

車載自組網(wǎng)絡(luò)(vehicle Ad Hoc networks,VANETs)是移動網(wǎng)絡(luò)的一個特例。VANETs可實現(xiàn)車與車之間、車與路邊基礎(chǔ)設(shè)施通信。該通信可實現(xiàn)信息共享，有助于事故預警、交通信息查詢等多種應用[1]。隨著各項技術(shù)日益成熟，VANETs也將成為物聯(lián)網(wǎng)的典型應用之一[2]。

由于VANETs網(wǎng)絡(luò)動態(tài)性強，車輛移動快速，拓撲結(jié)構(gòu)變化不定，傳統(tǒng)的路由算法難于適應VANETs。另外，由于VANETs應用環(huán)境多樣化，車輛密度隨時間、地點變化迅速，導致車輛間的連通性呈機會性。在上下班高峰時區(qū)，道路上的車輛較多，車輛連通性高。然而，在午夜時區(qū)，道路上的車輛稀少，車輛連通性極低。此外，高速行駛的車輛，相遇交互時間甚短，研究表明：車輛通信的窗口平均時長為15 s。VANETs的這些鮮明的特性給設(shè)計VANETs的路由協(xié)議提出挑戰(zhàn)。

為此，研究者在設(shè)計VANETs路由時，應充分利用VANETs這些特點，可從車輛移動性、通信的連通率、路邊的基礎(chǔ)設(shè)施、節(jié)點的地理位置方面去決策路由方案。

在VANETs中，節(jié)點相互安裝收發(fā)器，形成通信的連通。如經(jīng)典的按需路由AODV[3]、動態(tài)源路由(DSR)[4]，其是將移動自組網(wǎng)(mobile Ad Hoc networks，MANETs)的路由技術(shù)擴展到VANETs。文獻[5～8]均屬基于連通性路由。

VANETs節(jié)點具有快速移動性、移動范圍大、移動空間受限等特性(交通規(guī)則)，許多路由方案均利用這些特性去預測路由，PBR[9]，Abedi[10],NiuDe[11],文獻[12]利用車輛的移動參數(shù)建立路由。

研究者也借鑒蜂窩網(wǎng)絡(luò)的理論，利用路邊基礎(chǔ)設(shè)施輔助VANETs車輛通信，如蜂窩基站、日用的公交巴士等。特別在車輛稀疏區(qū)域，借助于路邊的基礎(chǔ)設(shè)施在實現(xiàn)數(shù)據(jù)包的傳遞，從而增強通信的健壯性、魯棒性、安全性。如文獻[13～16]。

隨著全球定位系統(tǒng)(global positioning system,GPS)日益普及和電子地圖廣泛應用，這為基于地理位置路由協(xié)議應用提供了條件。基于地理位置路由利用車輛的地理位置信息而不是拓撲的連通信息去構(gòu)建路由,例如：文獻[17～20]。

由于VANETs節(jié)點通信呈機會性，不少學者將概率理論應用于VANETs，其充分利用節(jié)點移動信息和鏈路機會性。為此，研究人員提出基于概率統(tǒng)計理論的路由策略。文獻[21～24]均利用概論理論構(gòu)建路由。

本文依據(jù)VANETs網(wǎng)絡(luò)特性將路由協(xié)議分成基于基礎(chǔ)設(shè)施、移動預測、地理位置、概率以及連通的路由。

1 VANETs路由

1.1 基于連通路由

基于連通路由廣泛采取廣播的形式，如泛洪路由，通過節(jié)點不斷廣播傳遞數(shù)據(jù)包，節(jié)點收到數(shù)據(jù)包后，向鄰居車輛廣播，直至數(shù)據(jù)傳遞到目的地才停止廣播，泛洪簡單,易實施，操作性強。如果是單播消息，目的節(jié)點只有一個，泛洪就不再適用，因為不斷地廣播會增加網(wǎng)絡(luò)負擔，但如果目的節(jié)點均在一跳通信范圍內(nèi)，采用泛洪路由可提高路由性能，因為泛洪總是能將數(shù)據(jù)傳遞到目的節(jié)點。然而，在VANETs網(wǎng)絡(luò)中，往往數(shù)據(jù)需要經(jīng)多跳傳遞才能到達目的節(jié)點，隨著多跳通信數(shù)目的增加，網(wǎng)絡(luò)的性能快速下降，當節(jié)點的數(shù)量較大時，會引發(fā)廣播風暴。

Li X等人[6]提出節(jié)點不相交的多路徑路由(node-disjoint multipath routing，NDMR) 算法。NDMR結(jié)合了定向圖理論，采用廣播方式傳遞控制消息，轉(zhuǎn)發(fā)節(jié)點根據(jù)控制消息決策路由，有效地降低了路由開銷。Korkmaz G等人[7]采用城市多跳廣播路由方案,通過電子地圖獲取道路信息，并針對道路交叉口、非交叉口應用不同的廣播模式。交叉口廣播模式應用交叉口處，而定向廣播應用于非交叉口處。

在CAID[8](context-adaptive information diffusion)中，采用節(jié)點與數(shù)據(jù)包的相關(guān)性實施數(shù)據(jù)包轉(zhuǎn)發(fā),相關(guān)性大的節(jié)點具有轉(zhuǎn)發(fā)數(shù)據(jù)包的權(quán)限,節(jié)點融合數(shù)據(jù)包、車輛移動信息計算相關(guān)性。此方案提高了數(shù)據(jù)包的傳輸效率和通信資源利用率。

1.2 基于移動預測路由

快速移動是VANETs的顯著特點,這個特點加速了網(wǎng)絡(luò)拓撲結(jié)構(gòu)不穩(wěn)定性，并減少了鏈路的使用壽命，降低了路徑穩(wěn)定性。

盡管節(jié)點的高速移導致VANETs路由性能下降，但節(jié)點的移動具有一定的規(guī)律性，在一定程度上可以預測其移動信息,如在高速公路上移動的節(jié)點(車輛)，其行駛軌跡局限于道路，同時速度也限定于交通規(guī)則范圍內(nèi)。因此，節(jié)點的移動信息具有可預見性，在設(shè)計路由協(xié)議時，應充分利用這一特點，通過預先獲取節(jié)點的移動速度、方向等數(shù)據(jù)，計算潛在鏈路的信息，如鏈路的可用的時間，使路徑趨于穩(wěn)定,這就是基于移動預測路由的基本理論。

在決策路由時，先預測鏈路的生命周期，選取生命周期長的鏈路組建路徑，并對即將斷裂的鏈路進行了修復或替換。根據(jù)節(jié)點速度、方向、加速度等運動參數(shù)，計算鏈路的生命周期。

針對高速公路場景，Namboodiri V[9]提出預測移動模型。該通信模型預測鏈路的使用壽命，在鏈路未斷裂前，進行維護，從而保證數(shù)據(jù)成功地傳遞。同時，針對節(jié)點快速移動，Abedi O[10]提出AODV的優(yōu)化方案,根據(jù)方向、位置、速度等運動參數(shù)決策路由,在3個參數(shù)中，方向參數(shù)的權(quán)值最大，這主要是因為由同一方向的節(jié)點所建立的路徑，比處于不同方向的節(jié)點所構(gòu)建的路徑更趨于穩(wěn)定、路徑可用持續(xù)時間更長。Niu Z等人[11]采用數(shù)學理論，提出基于鏈路的生命周期、交通密度信息的可靠鏈路數(shù)學模型。Noppakum Y等人[12]提出基于權(quán)值系數(shù)的路由算法，該方案通過電子地圖獲取道路拓撲結(jié)構(gòu)，并結(jié)合節(jié)點速度和交通時況，計算鏈路的權(quán)值，只有滿足條件的鏈路，將就此鏈路加入到可用路由路徑表中。

1.3 基于基礎(chǔ)設(shè)施路由

基于基礎(chǔ)設(shè)施路由的思想就是將路邊基礎(chǔ)設(shè)施RSU作為通信的中繼節(jié)點，由于RSU位置固定，可有效提高通信的穩(wěn)定性。通過RSU，有助于數(shù)據(jù)的可靠傳輸，提高VANETs通信的連通率?；诨A(chǔ)設(shè)施路由常用RSU形成主干鏈路，一旦通信鏈路斷裂，可實施存儲—轉(zhuǎn)發(fā)機制。當然，利用RSU輔助節(jié)點通信有著明顯的優(yōu)勢，但也存在 2個問題：一是在道路邊如何部署RSU，巨大的道路面積，不可能沿道路邊全部部署RSU；二是即使部署了RSU，一旦RSU損壞，如地震，數(shù)據(jù)傳輸線路將破壞，網(wǎng)絡(luò)將面臨癱瘓。

DRR(differentiated reliable routing)[13]方案將RSU作為虛擬設(shè)備。在通信過程中，RSU與道路中的節(jié)點建立通信，實時更新節(jié)點信息,同時，節(jié)點與RSU保持同步。在文獻[14]中作者針對城市環(huán)境，采用了面積的街道的路由協(xié)議SARC。該方案實施了節(jié)點隱私保護環(huán)節(jié)，分別在路由發(fā)現(xiàn)、數(shù)據(jù)轉(zhuǎn)發(fā)2個階段對節(jié)點的位置隱私進行保護。

文獻[15]提出靜態(tài)點輔助路由協(xié)議SADV方案。SADV主要由鏈路延時更新(link delay update,LDU)、多路徑數(shù)據(jù)分發(fā)(multipath data dissemination,MPDD)以及靜態(tài)點輔助轉(zhuǎn)發(fā)(static node assisted routing,SNAR)組成，分別實現(xiàn)傳輸時延更新、延遲最小路徑的計算、多路徑數(shù)據(jù)分發(fā)。同時，SADV針對節(jié)點所在的位置，實施路段模式和交叉口模式交替的方式轉(zhuǎn)發(fā)數(shù)據(jù)包。Kitani T等人[16]提出基于公交巴士消息擺渡方案,實施收集消息、存儲—轉(zhuǎn)發(fā)(carry and forward)的策略。

1.4 基于地理位置路由

Karp B等人[17]于2000年率先提出基于貪婪算法的地理位置路由(greedy perimeter stateless routing，GPSR)協(xié)議。在GPSR方案中，實施貪婪轉(zhuǎn)發(fā)、周邊轉(zhuǎn)發(fā)2種模式，分別使用于不同的情況。前者通過距離值選擇下一跳節(jié)點，離目標節(jié)點最近節(jié)點作為下一跳節(jié)點。一旦貪婪模式不能轉(zhuǎn)發(fā)數(shù)據(jù)包時，就選用周邊轉(zhuǎn)發(fā)模式，與貪婪模式不同的是，其采用右手法則轉(zhuǎn)發(fā)數(shù)據(jù)包。然而，GPSR具有局限性，在遇到路由空洞時，GPSR就不再適用。

如圖1所示，轉(zhuǎn)發(fā)節(jié)點S向目的節(jié)點D傳遞數(shù)據(jù)。在數(shù)據(jù)傳遞到節(jié)點B時，節(jié)點B采用貪婪轉(zhuǎn)發(fā)無法找到下一跳節(jié)點，將這種情況稱為路由空洞。為此，文獻[18]提出存儲—轉(zhuǎn)發(fā)。在遇到路由空洞時，節(jié)點先將數(shù)據(jù)包存儲，等待下一轉(zhuǎn)發(fā)節(jié)點進入其通信范圍。一旦有節(jié)點，將恢復原來GPSR的轉(zhuǎn)發(fā)機制，將數(shù)據(jù)包傳遞目標節(jié)點。

圖1 節(jié)點B遭遇局部最優(yōu)化

Giudici F等人[19]提出STAR算法。網(wǎng)絡(luò)中的節(jié)點建立交通流量和鄰居信息表,節(jié)點在決策路由時根據(jù)表內(nèi)信息、選擇最短路徑，并采用貪婪轉(zhuǎn)發(fā)。仿真表明：STAR的路由性能優(yōu)于GPSR,但是STAR是以占用更多資源為代價的。GyTAR(improved greedy traffic aware routing)[20]方案利用車輛密度信息，并在協(xié)議中設(shè)置錨點，通過錨點的數(shù)據(jù)信息決策路由。同時，錨點間通信基于貪婪算法，若遇到路由空洞，啟用緩存轉(zhuǎn)發(fā)機制。

1.5 基于概率路由

由于VANETs拓撲結(jié)構(gòu)不斷變化，節(jié)點通信呈機會性,為此，研究人員結(jié)合概率統(tǒng)計理論，提出基于概率路由方案。通過計算無線鏈接可用時間分布，或已存在的鏈接在一段時間后仍然未斷裂的概率?；诟怕事酚傻膶嵤┦且栽谝欢僭O(shè)為條件,其需要建立網(wǎng)絡(luò)傳播模型，通過這些模型才能統(tǒng)計相關(guān)變量的分布信息。

Jiang H等人[21]提出REAR(reliable and efficient alarm message routing),REAR通過計算無線信道所收到的警告信息的概率，并以此信息為依據(jù)決策路由。VADD(vehi-cle-assisted data delivery)[22]融合移動車輛的位置和方向信息，計算數(shù)據(jù)包傳遞到目的節(jié)點的概率。針對節(jié)點所處位置的不同，實施Straightway,Intersection以及Destination轉(zhuǎn)發(fā)模式。在道路交叉口使用Intersection模式,離開道路交叉口使用Straightway模式，靠近目標的節(jié)點使用Destination模式。由于節(jié)點的快速移動，VADD所計算的數(shù)據(jù)包轉(zhuǎn)發(fā)的概率往往滯后節(jié)點的移動。

Wu Z等人[25]提出DTSG(dynamic time-stable geocast)方案。將網(wǎng)絡(luò)區(qū)域劃分為相關(guān)區(qū)域(zone of relevance，ZOR)、轉(zhuǎn)發(fā)區(qū)域(zone of forwarding，ZOF)。前者是指目標節(jié)點所在的區(qū)域，后者是指轉(zhuǎn)發(fā)節(jié)點所在的區(qū)域。該方案首先在ZOR廣播數(shù)據(jù)包，并將廣播持續(xù)到預設(shè)的時間?？筛鶕?jù)不同應用環(huán)境，設(shè)置不同的廣播時長。

2 五類路由特點比較

五類路由協(xié)議特點如表1所示[23]。

表1 各類路由協(xié)議的優(yōu)缺點

3 結(jié) 論

路由協(xié)議應具有適應各種環(huán)境，并將數(shù)據(jù)穩(wěn)定、可靠、安全地進行傳輸，因此，應從以下要求設(shè)計路由：

1)穩(wěn)定性：將數(shù)據(jù)可靠、穩(wěn)定傳輸是路由協(xié)議的根本任務，特別是安全信息，路由協(xié)議的穩(wěn)定性顯得尤為關(guān)鍵。

2)自適應性：由于VANETs,所處環(huán)境復雜多變，路由協(xié)議應能適應各種環(huán)境，在不同網(wǎng)絡(luò)環(huán)境下應具魯棒性，面對復雜環(huán)境自我調(diào)整。另外，網(wǎng)絡(luò)中的突變[31]如數(shù)據(jù)包的碰撞、信號誤碼等，嚴重影響路由協(xié)議性能，因此，協(xié)議的自適性是重要的參數(shù)。

3)安全性：現(xiàn)有的大多數(shù)路由協(xié)議在設(shè)計路由協(xié)議時，并沒有考慮節(jié)點信息的保護問題，而節(jié)點的隱私信息的保護在VANETs中特別重要，為此，在路由協(xié)議中如何保護數(shù)據(jù)的安全性需要解決的問題。

參考文獻:

[1] Perkins C E,Royer E M.Ad Hoc on-demand distance vector routing[C]∥Proc of IEEE Workshop on Mobile Computing Systems and Applications (WMCSA),2011:90-100.

[2] Lee J H,Chilmakurti N.Performance analysis of PMIPv6 based network mobility for intelligent transportation systems[C]∥IEEE Transaction on Vehicular Technology,2011:23-32.

[3] Lochert C,Hartenstein H,Tian J.A routing strategy for vehicular Ad Hoc networks in city environments[C]∥Intelligent Vehicles Symposium,2012:156-161.

[4] Johnson D B,Maltz D A,Hu Y C.The dynamic source routing protocol for mobile Ad Hoc networks[C]∥Published Online,IETF MANET Working Group,Tech Rep 2007：153-181.

[5] Perkins C E,Bhagwat P.Highly dynamic destination-sequenced distance-vector routing for mobile computers[J].SIGCOMM Comput Commun Rev,1994,24(4): 234-244.

[6] Li X,Cuthbert L.On-demand node-disjoint multipath routing in wireless Ad Hoc network[C]∥Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks,LCN’04,Washington DC,USA,IEEE Computer Society,2004:419-420.

[7] Korkmaz G,Ekici E,Ozguner F,et al.Urban multi-hop broadcast protocol for intervehicular communication systems [C]∥Procee-dings of the 1st ACM International Workshop on Vehicular Ad Hoc Network,2004:76-85.

[8] Adler C,Eichler S,Kosch T,et al.Self-organized and context-adaptive information diffusion in vehicular Ad Hoc network-s[C]∥Proceedings of the 3rd International Symposium on Wireless Communication Systems,2006:307-311.

[9] Namboodiri V,Gao L.Prediction-based routing for vehicular Ad Hoc networks[J].IEEE Transactions on Vehicular Technology,2007,56( 4): 2332-2345.

[10] Abedi O,Fathy M,Taghiloo J.Enhancing AODV routing protocol using mobility parameters in vanet [C]∥Proceedings of the 2008 IEEE/ACS International Conference on Computer Systems and Applications:IEEE Computer Society,2008:229-235.

[11] Niu Z,Yao W,Ni Q,et al.Dereq:A QOS routing algorithm for multimedia communications in vehicular Ad Hoc networks [C]∥Proceedings of the 2007 International Conference on Wireless Communications and Mobile Computing,New York,2007:393-398.

[12] Noppakum Y,Phongsak K.AODV improvement for vehicular networks with cross layer technique and mobility prediction[J].Intelligent Signal Processing and Communication Systems,2011,8(2):89-95.

[13] He R,Rutagemwa H,Shen X.Differentiated reliable routing in hybrid vehicular Ad Hoc networks[C]∥IEEE International Conference on Communications(ICC),2008:2353-2358.

[14] Kim H,Paik J,Lee B,et al.Sarc: A street-based anonymous vehicular Ad Hoc routing protocol for city environment[C]∥Proceedings of the 2008 IEEE/IFIP International Conference on Embedded and Ubiquitous Computing,Washington,2008:324-329.

[15] Ding Y,Wang C,Xiao L.A static-node assisted adaptive routing protocol in vehicular networks[C]∥Proceedings of the Fourth ACM International Workshop on Vehicular Ad Hoc Networks,2007:59-68.

[16] Kitani T,Shinkawa T,Shibata N,et al .Efficient vanet-based tra-ffic information sharing using buses on regular routes [C]∥Vehicular Technology Conference,2008:3031-3036.

[17] Karp B,Kung H T.GPSR: Greedy perimeter stateless routing for wireless networks[C]∥Proc of 6th Annual International Confe-rence on Mobile Computing and Networking,2000:243-254.

[18] Naumov V,Gross T R.Connectivity-aware routing in vehicular Ad Hoc networks[C]∥Proc of 6th IEEE International Conference on Computer Communications,2007:1919-1927.

[19] Giudici F,Pagani E.Spatial and traffic-aware routing for vehicular systems[J].Lecture Notes in Computer Science,2005,3726:77-86.

[20] Jerbi M,Meraihi R,Senouci S M,et al.GyTAR:Improved greedy traffic aware routing protocol for vehicular Ad Hoc networks in city environments[C]∥Proceedings of the 3rd International Workshop on Vehicular Ad Hoc Networks,2006:88-89.

[21] Jiang H,Guo H,Chen L.Reliable and efficient alarm message routing in vanet[C]∥Proceedings of the 2008 International Conference on Distributed Computing Systems Workshops,ICDCSW’08,Washington DC,USA,IEEE Computer Society,2008:186-191.

[22] Zhao J,Cao G.VADD: Vehicle-assisted data delivery in vehicular Ad Hoc Networks[J].IEEE Transactions on Vehicular Technology,2008,2(5):123-128.

[23] 徐會彬，夏 超.VANETs路由綜述[J].計算機應用研究,2013,30(1):1-6.

[24] Junichiro F.A probabilistic protocol for multi-hop routing in VANETs[C]∥IEEE International Conference on Communications Workshops,2009:345-352.

[25] Wu Z,Yang Y,Guo X,et al.Analysis of collision probability in IEEE 802.11 based VANETs[J].Acta Electronica Sinica,2010,19(1E):187-190.