黃繼海，趙 冰

(鄭州工程技術(shù)學(xué)院 信息工程學(xué)院,鄭州 450044)

車(chē)載自組織網(wǎng)路由技術(shù)研究綜述

黃繼海，趙 冰

(鄭州工程技術(shù)學(xué)院 信息工程學(xué)院,鄭州 450044)

車(chē)載自組網(wǎng)路由技術(shù)是近年來(lái)無(wú)線(xiàn)網(wǎng)絡(luò)以及智能交通領(lǐng)域的研究熱點(diǎn)之一，由于車(chē)載自組網(wǎng)節(jié)點(diǎn)密度大、拓?fù)渥兓斓忍卣鹘o路由技術(shù)研究帶來(lái)了巨大的挑戰(zhàn)。本文從車(chē)載自組網(wǎng)路由技術(shù)的研究意義和研究?jī)?nèi)容出發(fā)，介紹了路由技術(shù)基于的車(chē)載自組織網(wǎng)架構(gòu)，總結(jié)了車(chē)載自組織網(wǎng)的特點(diǎn)，對(duì)車(chē)載自組織路由模型進(jìn)行分類(lèi)介紹，對(duì)比了不同類(lèi)型路由協(xié)議的性能，最后探討了目前車(chē)載自組網(wǎng)路由技術(shù)中存在的問(wèn)題及未來(lái)的發(fā)展前景。

車(chē)載自組網(wǎng);路由技術(shù);路徑;轉(zhuǎn)發(fā)

1 引言

隨著我國(guó)經(jīng)濟(jì)的不斷發(fā)展，道路交通的規(guī)模越來(lái)越大， 問(wèn)題也越來(lái)越復(fù)雜，其導(dǎo)致的交通事故問(wèn)題也成為了人、物損失的重大災(zāi)難。車(chē)輛網(wǎng)絡(luò)概念在該需求背景下應(yīng)運(yùn)而生，2003年的汽車(chē)通信標(biāo)準(zhǔn)化會(huì)議上，相關(guān)專(zhuān)家提出了車(chē)載自組織網(wǎng)絡(luò)(VANET，Vehicle Ad-hoc NETworks)的概念[1]。作為車(chē)輛通信網(wǎng)絡(luò)的車(chē)載自組網(wǎng)將自組織網(wǎng)技術(shù)應(yīng)用于車(chē)輛網(wǎng)絡(luò)，使司機(jī)能夠在超視距的范圍內(nèi)獲得其他車(chē)輛或道路的狀況信息，包括：車(chē)速、方向、擁堵等。車(chē)載自組網(wǎng)的設(shè)計(jì)目標(biāo)是建立一個(gè)車(chē)輛間通信的平臺(tái)，在提高交通效率的同時(shí)，帶來(lái)可靠安全和多重便利[2]。

在VANET中，路由協(xié)議對(duì)研究車(chē)載自組網(wǎng)通信至關(guān)重要，路由協(xié)議的性能直接影響車(chē)輛之間通信的性能。但由于網(wǎng)絡(luò)拓?fù)涞念l繁變化，節(jié)點(diǎn)(車(chē)輛)移動(dòng)的高速性，導(dǎo)致自組織網(wǎng)路由問(wèn)題成為VANET中的一個(gè)難題。本文通過(guò)國(guó)內(nèi)外文獻(xiàn)的閱讀，對(duì)車(chē)載自組織網(wǎng)絡(luò)路由模型進(jìn)行了系統(tǒng)的研究和總結(jié)。

2 VANET基本網(wǎng)絡(luò)架構(gòu)與技術(shù)挑戰(zhàn)

在VANET中，汽車(chē)、路邊通信基站之間通信采用無(wú)線(xiàn)信道，其主要的系統(tǒng)組件包括：路邊組件(Road Side Component，RSC)、通信組件(Communication Component，CC)、應(yīng)用組件(Application Component，AC)。如圖1所示，單個(gè)移動(dòng)汽車(chē)嵌入CC和AC功能，汽車(chē)安裝多個(gè)傳感器，搜集、處理多方信息并發(fā)送消息給其它汽車(chē)或RSC，同時(shí)汽車(chē)可基于鏈路能力集成多種AC，RSC可連接互聯(lián)網(wǎng)或其它服務(wù)，并將多種服務(wù)提供給AC。CC用來(lái)交換信息，內(nèi)嵌處理器可實(shí)現(xiàn)內(nèi)存的讀寫(xiě)和數(shù)據(jù)的存儲(chǔ)和恢復(fù)，基于IEEE 802.11p或IEEE 802.11a/b/g/n無(wú)線(xiàn)技術(shù)的用戶(hù)接口實(shí)現(xiàn)不同CC間的通信或其它應(yīng)用，CC為AC提供通信服務(wù)并轉(zhuǎn)發(fā)數(shù)據(jù)包給其它CC，主要功能包括無(wú)線(xiàn)接入、自組織網(wǎng)、位置路由、網(wǎng)絡(luò)擁塞控制、可靠消息傳輸、數(shù)據(jù)安全傳輸和IP移動(dòng)。AC主要負(fù)責(zé)上層安全應(yīng)用、個(gè)人數(shù)據(jù)幫助(Personal Digital Assistant，PDA)，AC通過(guò)無(wú)線(xiàn)或有線(xiàn)連接CC并嵌入在一個(gè)單獨(dú)的物理模塊中與CC具有嚴(yán)格的邏輯區(qū)分，AC只能通過(guò)CC完成獨(dú)立的移動(dòng)和網(wǎng)絡(luò)功能。RSC是一個(gè)無(wú)線(xiàn)設(shè)備被靈活安置在路邊、 交叉路口或停車(chē)場(chǎng)，RSC裝備網(wǎng)絡(luò)設(shè)備并基于IEEE 802.11p radio無(wú)線(xiàn)技術(shù)，其目的是與CC和網(wǎng)絡(luò)通信，主要功能包括：通過(guò)不同CC和RSC的數(shù)據(jù)包轉(zhuǎn)發(fā)擴(kuò)展無(wú)線(xiàn)自組織網(wǎng)通信范圍，為CC提供互聯(lián)網(wǎng)連接，運(yùn)行安全應(yīng)用(如低橋警告、事故預(yù)警等)，并作為信息源廣播告知汽車(chē)節(jié)點(diǎn)。為實(shí)現(xiàn)不同組件間的通信，主要的無(wú)線(xiàn)接入技術(shù)包括GSM-2G/GPRS-2.5G，UMTS-3G，紅外線(xiàn)通信等，并通過(guò)增加新的接口協(xié)議適應(yīng)IEEE 802.11p。

圖1 VANET基本結(jié)構(gòu)圖

考慮到VANET的實(shí)際應(yīng)用，可總結(jié)其區(qū)別于MANET(Mobile Ad hoc NETwork)的特征如下：(1)具有可預(yù)測(cè)的移動(dòng)規(guī)律。由于VANET由道路拓?fù)錁?gòu)成，且遵守路標(biāo)指示和信號(hào)燈，并受到其它汽車(chē)的影響，因此可以預(yù)測(cè)其移動(dòng)的方向、路線(xiàn)和速度。(2)VANET中節(jié)點(diǎn)無(wú)電量限制。因?yàn)槠?chē)依靠蓄電池為網(wǎng)絡(luò)連接應(yīng)用提供持續(xù)的電量。(3)提供安全駕駛并改進(jìn)旅行舒適度。移動(dòng)節(jié)點(diǎn)之間通過(guò)網(wǎng)絡(luò)可實(shí)現(xiàn)直接通信，可將事故警告信息提供給駕駛員，通過(guò)消息廣播，乘客換可以獲得有關(guān)天氣、擁堵、生活服務(wù)和互聯(lián)網(wǎng)應(yīng)用等多種信息。(4)VANET網(wǎng)絡(luò)中節(jié)點(diǎn)密度大。節(jié)點(diǎn)密度主要來(lái)源于車(chē)流密度，尤其是在擁堵的城市道路或繁華的住宅區(qū)。(5)網(wǎng)絡(luò)拓?fù)涞淖兓?。由于無(wú)線(xiàn)鏈路帶寬導(dǎo)致的同向/反向鏈路的生存周期的差異，高速移動(dòng)的節(jié)點(diǎn)縮短了網(wǎng)絡(luò)直徑，切斷了點(diǎn)到點(diǎn)網(wǎng)絡(luò)連接，導(dǎo)致網(wǎng)絡(luò)拓?fù)涞目焖俑淖?。更進(jìn)一步說(shuō)，不同司機(jī)對(duì)所收到信息的不同反應(yīng)及處理方式影響著拓?fù)洹?6)單節(jié)點(diǎn)高計(jì)算能力需求。由于節(jié)點(diǎn)是汽車(chē)，為提供實(shí)時(shí)可靠地?zé)o線(xiàn)互聯(lián)和準(zhǔn)確的信息回饋，集成了高級(jí)天線(xiàn)技術(shù)、GPS導(dǎo)航、大量的傳感器、處理器和大規(guī)模緩存，對(duì)計(jì)算能力需求提高。

VANET以上特征，導(dǎo)致其產(chǎn)生一系列問(wèn)題，如信號(hào)衰竭、帶寬限制、網(wǎng)絡(luò)直徑、安全問(wèn)題等。在諸問(wèn)題中，影響數(shù)據(jù)包可靠到達(dá)、帶寬利用率、可接受端到端時(shí)延的路由問(wèn)題也是一個(gè)亟待解決的關(guān)鍵問(wèn)題，因?yàn)閂ANET中節(jié)點(diǎn)的高速移動(dòng)和網(wǎng)絡(luò)拓?fù)涞目焖僮兓?，使得設(shè)計(jì)一個(gè)有效的路由協(xié)議在極短周期內(nèi)傳輸包并保持極低丟包率是非常困難的，許多研究者已著力設(shè)計(jì)一個(gè)有效的路由協(xié)議可滿(mǎn)足高密度節(jié)點(diǎn)的傳輸需要，提高數(shù)據(jù)包傳輸率增強(qiáng)系統(tǒng)的魯棒性，保證組播路由請(qǐng)求的碰撞避免，可通過(guò)極短時(shí)間的包傳輸來(lái)應(yīng)對(duì)突發(fā)狀況。但現(xiàn)有VANET路由協(xié)議，由于其只依據(jù)單一的路由模型和算法，所以只能偏重于部分性能指標(biāo)要求，而非全部。下面將對(duì)現(xiàn)有路由協(xié)議進(jìn)行分類(lèi)總結(jié)，分析其優(yōu)缺點(diǎn)，對(duì)比其性能。

3 VANET路由模型的分類(lèi)

基于已有文獻(xiàn)的分類(lèi)和多種路由協(xié)議的分析，本文將VANET中的路由協(xié)議大致分為7類(lèi)：①基于拓?fù)?Topology Based,TB)的路由協(xié)議；②基于位置(Position Based，PB)的路由協(xié)議；③基于群組(Cluster Based，CB)的路由協(xié)議；④基于廣播(Broadcast Based，BB)的路由協(xié)議，⑤基于地理位置多播(Geocast Based，GB)的路由協(xié)議，⑥基于服務(wù)質(zhì)量(Quality of Svice Based，QoSB)的路由協(xié)議，⑦基于多路徑(Multi-Path Based，MPB)的路由協(xié)議。如圖2所示，其中列舉的協(xié)議只是各類(lèi)中的部分典型協(xié)議，而非全部。

3.1 TB路由協(xié)議

TB路由協(xié)議分為先應(yīng)式和觸發(fā)式兩大類(lèi)。先應(yīng)式路由協(xié)議保存集中的路由信息，為保持路徑，不斷的在節(jié)點(diǎn)間廣播洪泛路由包，從而在單節(jié)點(diǎn)構(gòu)建路由表可查到目的節(jié)點(diǎn)的下一跳。其優(yōu)點(diǎn)是可知下一跳的集中式的路由存儲(chǔ)省略了路徑發(fā)現(xiàn)過(guò)程，其缺點(diǎn)是保存大量無(wú)用路由，導(dǎo)致帶寬利用率低，無(wú)法滿(mǎn)足實(shí)時(shí)應(yīng)用的需求。典型的算法有FSR(Fisheye State Routing)[3]，該算法保存來(lái)自鄰近和本地鄰居節(jié)點(diǎn)的最新路由信息生成拓?fù)浔?，不同?jié)點(diǎn)間采用不同數(shù)據(jù)交換周期來(lái)減小大規(guī)模網(wǎng)絡(luò)的數(shù)據(jù)包長(zhǎng)度，隨著與目的節(jié)點(diǎn)距離的增加，單節(jié)點(diǎn)路由表項(xiàng)將通過(guò)鄰居節(jié)點(diǎn)升級(jí)。問(wèn)題是隨著網(wǎng)絡(luò)規(guī)模的增長(zhǎng)，路由表項(xiàng)也不斷增長(zhǎng)，導(dǎo)致對(duì)遠(yuǎn)距離目的節(jié)點(diǎn)的表項(xiàng)失準(zhǔn)。

反應(yīng)式路由協(xié)議又叫需求驅(qū)動(dòng)路由協(xié)議，只有當(dāng)節(jié)點(diǎn)有路由需求時(shí)才開(kāi)始尋路過(guò)程。典型路由協(xié)議包括DSR(Dynamic Source Routing)[4]，AODV(Ad Hoc on Demand Distance Vector)[5]和TORA(Temporally Ordered Routing Protocol)[6]。DSR是一種基于源路由的按需路由協(xié)議，它使用源路由算法而不是逐跳路由的方法。DSR主要包括路由發(fā)現(xiàn)和維護(hù)兩個(gè)過(guò)程。當(dāng)源節(jié)點(diǎn)向目的節(jié)點(diǎn)發(fā)送數(shù)據(jù)時(shí)，首先檢查緩存是否存在有效路由，如果存在，則直接使用該路由，否則啟動(dòng)路由發(fā)現(xiàn)過(guò)程：源節(jié)點(diǎn)使用洪泛法發(fā)送路由請(qǐng)求消息，該消息到達(dá)目的節(jié)點(diǎn)或任何一個(gè)中間節(jié)點(diǎn)(擁有目的節(jié)點(diǎn)路由)，則發(fā)送路由應(yīng)答消息，該消息包含源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由信息。DSR的優(yōu)點(diǎn)是節(jié)點(diǎn)僅需要維護(hù)與之通信的節(jié)點(diǎn)的路由，減少了協(xié)議開(kāi)銷(xiāo)；單次路由發(fā)現(xiàn)過(guò)程會(huì)產(chǎn)生并保存多條到目的節(jié)點(diǎn)的路由。DSR缺點(diǎn)是每個(gè)數(shù)據(jù)包的頭部都需要攜帶路由信息，數(shù)據(jù)包頭的額外開(kāi)銷(xiāo)較大；路由請(qǐng)求包采用洪泛方式，大大增加了傳播沖突和重復(fù)廣播的概率；過(guò)期路由會(huì)影響路由選擇的準(zhǔn)確性。AODV是DSDV(Destination Sequence Distance Vector)算法的改進(jìn)，但它與DSDV的區(qū)別在于它是反應(yīng)式路由協(xié)議。為了找到目的節(jié)點(diǎn)的路由，源節(jié)點(diǎn)廣播路由請(qǐng)求包，鄰居節(jié)點(diǎn)依次向周?chē)?jié)點(diǎn)擴(kuò)散該請(qǐng)求包直到被送到中間節(jié)點(diǎn)(知道目的節(jié)點(diǎn)路由)或目的節(jié)點(diǎn)，而后逆向路由回應(yīng)包，并更新正向路由表。如果中間節(jié)點(diǎn)移動(dòng)導(dǎo)致相鄰節(jié)點(diǎn)鏈路失效則會(huì)向其上游節(jié)點(diǎn)發(fā)送鏈路失效包進(jìn)而傳到源節(jié)點(diǎn)，而后源節(jié)點(diǎn)依需求重新發(fā)起路由發(fā)現(xiàn)過(guò)程。AODV的實(shí)現(xiàn)組合DSR和DSDV協(xié)議。它既具有DSR協(xié)議的路由發(fā)現(xiàn)和路由維護(hù)功能，同時(shí)又使用了DSDV采用的逐跳路由、序列號(hào)和Beacon消息。TORA(Temporally Ordered Routing Algorithm)采用循環(huán)圖的方式保證數(shù)據(jù)流的可到達(dá)所有節(jié)點(diǎn)，單節(jié)點(diǎn)通過(guò)廣播路由請(qǐng)求包查詢(xún)有向圖，在收到廣播包之后，如果該節(jié)點(diǎn)有可達(dá)目的地址的下行鏈路，則廣播回復(fù)包，節(jié)點(diǎn)收到回復(fù)包將升級(jí)其表項(xiàng)選擇所有回復(fù)包中可達(dá)路徑最短的，TORA優(yōu)點(diǎn)是可保證數(shù)據(jù)包到達(dá)所有目的節(jié)點(diǎn)，但維護(hù)路由表項(xiàng)的復(fù)雜度很高。

圖2 路由協(xié)議分類(lèi)圖

3.2 PB路由協(xié)議

PB路由協(xié)議采用圖位置信息來(lái)選擇轉(zhuǎn)發(fā)下一跳，數(shù)據(jù)包被發(fā)送到距離目的節(jié)點(diǎn)最近的下一跳鄰居，非常適合源到目的節(jié)點(diǎn)的全局路由的創(chuàng)建和維護(hù)。PB路由協(xié)議將貪婪策略與中間節(jié)點(diǎn)結(jié)合，將數(shù)據(jù)包轉(zhuǎn)發(fā)到更遠(yuǎn)的同向鄰居節(jié)點(diǎn)，貪婪策略需要中間節(jié)點(diǎn)擁有自身位置信息、鄰居位置信息和目的位置信息，該類(lèi)協(xié)議主要目的是最短時(shí)延內(nèi)將數(shù)據(jù)包傳輸?shù)侥康牡?。典型路由協(xié)議包括GSR(Geographic Source Routing)[7]，GPSR(Greedy Perimeter Coordinator Routing)[8]，CAR(Connectivity Aware Routing)[9]，LOUVRE(Landmark Overlays for Urban Vehicular Routing Environment)[10]。

GSR最早用在MANET，通過(guò)加入貪婪轉(zhuǎn)發(fā)適合VANET場(chǎng)景的應(yīng)用，該協(xié)議傳輸率和可擴(kuò)展特性比AODV和DSR好，但該協(xié)議無(wú)法適應(yīng)稀疏節(jié)點(diǎn)的網(wǎng)絡(luò)，由于采用Hello消息作為控制消息，所以該協(xié)議路由開(kāi)銷(xiāo)增大。GPSR采用周邊模式的路徑發(fā)現(xiàn)策略，該模式由兩部分組成，一部分采用分布式平面化算法通過(guò)移除冗余鏈路將連接圖轉(zhuǎn)化為平面圖，第二部分為實(shí)時(shí)路由算法來(lái)操作平面圖。由于高速節(jié)點(diǎn)移動(dòng)和路由跳數(shù)被引入，該模式將會(huì)散布長(zhǎng)路徑路由，所以GPSR僅限靜態(tài)街區(qū)地圖使用而無(wú)法適應(yīng)汽車(chē)密集的道路，且該協(xié)議過(guò)于依靠交叉路口節(jié)點(diǎn)。

在CAR中，路徑發(fā)現(xiàn)由AODV和廣播實(shí)現(xiàn)，一個(gè)節(jié)點(diǎn)生成路徑存儲(chǔ)頭節(jié)點(diǎn)代替前向節(jié)點(diǎn)，用來(lái)轉(zhuǎn)發(fā)路由回復(fù)包和路徑學(xué)習(xí)，目的節(jié)點(diǎn)在許多可達(dá)路徑中選擇一條時(shí)延小的最優(yōu)路徑，CAR利用頭節(jié)點(diǎn)將回復(fù)消息傳輸給源，守護(hù)節(jié)點(diǎn)用于回溯到達(dá)目的節(jié)點(diǎn)的路徑。CAR無(wú)需數(shù)字地圖，具有較高包傳輸率，且保證最短路徑連接。存在沒(méi)必要的頭節(jié)點(diǎn)選擇，且無(wú)法在環(huán)境變化時(shí)尋找到子路徑。

LOUVRE是基于位置貪婪鏈路狀態(tài)路由協(xié)議，采用道路長(zhǎng)度和密集度創(chuàng)建路由，采用Dijkstra路由算法構(gòu)建鏈路狀態(tài)表并存儲(chǔ)路由信息。LOUVRE采用路間路由和路內(nèi)路由，路間路由提供路由方向，路內(nèi)路由提供有保證的貪婪轉(zhuǎn)發(fā)。LOUVRE路由過(guò)程分為兩個(gè)階段，第一階段，節(jié)點(diǎn)不含任何路況信息，采用傳統(tǒng)的基于位置的路由協(xié)議轉(zhuǎn)發(fā)包。第二階段，基于第一階段路由升級(jí)，可獲得所有鄰居路況信息。兩種發(fā)現(xiàn)策略將會(huì)基于應(yīng)用類(lèi)型設(shè)計(jì)，對(duì)于時(shí)延敏感業(yè)務(wù)，將包轉(zhuǎn)發(fā)到至可達(dá)目的前驅(qū)節(jié)點(diǎn)。對(duì)于時(shí)延可容忍業(yè)務(wù)，采用承載轉(zhuǎn)發(fā)方法，節(jié)點(diǎn)存儲(chǔ)和承載數(shù)據(jù)包直到查表找到下一個(gè)可用節(jié)點(diǎn)。LOUVRE的時(shí)延和路徑跳數(shù)高于GPSR和CAR。

Li等提出了一種基于蟻群優(yōu)化PB路由協(xié)議VACO(Vehicular routing protocol based on Ant Colony Optimization)[11]，該協(xié)議結(jié)合先應(yīng)式和反應(yīng)式的功能分別保持最優(yōu)路徑，反應(yīng)式機(jī)制在接近于目的節(jié)點(diǎn)的交叉點(diǎn)轉(zhuǎn)發(fā)并回溯數(shù)據(jù)包，在每個(gè)交叉點(diǎn)選擇路由和下一個(gè)交叉點(diǎn)，同時(shí)分段評(píng)估延遲、帶寬和傳輸率三個(gè)QoS性能參數(shù)以決定最優(yōu)路徑選擇。仿真結(jié)果表明VACO比GPSR、CAR具有更優(yōu)的時(shí)延、吞吐率性能。

3.3 CB路由協(xié)議

CB路由協(xié)議節(jié)點(diǎn)聚類(lèi)創(chuàng)建虛擬網(wǎng)絡(luò)架構(gòu)，地理域被分成網(wǎng)格，如果節(jié)點(diǎn)進(jìn)入網(wǎng)格域，將被選舉為頭節(jié)點(diǎn)，主要負(fù)責(zé)內(nèi)部和外部群組協(xié)調(diào)，節(jié)點(diǎn)在同一群組直接通信，節(jié)點(diǎn)在不同的群組利用群組頭節(jié)點(diǎn)通信。源目的節(jié)點(diǎn)在不同的群組里直接發(fā)送數(shù)據(jù)包給鄰居群組頭節(jié)點(diǎn)，鄰居利用相同的策略轉(zhuǎn)發(fā)，直到到達(dá)目的地，CB路由協(xié)議內(nèi)存空間不緩存路由表從而增大了包傳輸率。典型路由協(xié)議有HCB(Hierarchical Cluster Based Routing)[12]，CBR(Cluster Based Routing)[13]和CBDRP(Cluster-Based Directional Routing Protocol)[14]

HCB采用雙層通信架構(gòu)適應(yīng)高速VANET，底層節(jié)點(diǎn)完成單一無(wú)線(xiàn)接口和多跳路徑尋路功能，上層則通過(guò)基站完成彼此通信的任務(wù)。該協(xié)議周期性的信息交互保證群組間路由，但數(shù)據(jù)包高丟失率導(dǎo)致很高的重傳率。CBR協(xié)議基于位置和群組方式將節(jié)點(diǎn)分成不同網(wǎng)格，網(wǎng)格內(nèi)采用位置信息轉(zhuǎn)發(fā)數(shù)據(jù)包，如果某節(jié)點(diǎn)被選舉為群組頭則會(huì)廣播一個(gè)到達(dá)信息給鄰居網(wǎng)格，如果該節(jié)點(diǎn)離開(kāi)本網(wǎng)格，則會(huì)廣播包括網(wǎng)格位置的離開(kāi)消息。優(yōu)點(diǎn)是路由開(kāi)銷(xiāo)小，缺點(diǎn)是該協(xié)議沒(méi)有考慮車(chē)輛的速度和方向。CBDRP基于CBR協(xié)議將車(chē)輛方向和速度參數(shù)引入到協(xié)議中。這樣做的優(yōu)點(diǎn)是提高了鏈路的穩(wěn)定性和可靠性，但重傳率和路由開(kāi)銷(xiāo)很高。

3.4 BB路由協(xié)議

在VANET中，廣播路由被頻繁的用于天氣、廣告、事故預(yù)警和通知等。廣播保證了包的傳輸可達(dá)，但卻導(dǎo)致了帶寬的浪費(fèi)和數(shù)據(jù)的重復(fù)收取，所以更適合小規(guī)模網(wǎng)絡(luò)。典型的廣播路由協(xié)議包括基于群組洪泛的BROADCOMM協(xié)議[15]、基于距離洪泛的UMB(Urban Multi-hop Broadcast)協(xié)議[16]、基于概率的洪泛V-TRADE(Vector Based Tracing Detection)協(xié)議[17]。BROADCOMM是一個(gè)基于分層結(jié)構(gòu)的高速網(wǎng)絡(luò)，在BRAODCOMM中，高速公路被分成虛擬單元，虛擬單元中的節(jié)點(diǎn)被分成兩個(gè)層次，第一個(gè)層次包括虛擬單元內(nèi)所有節(jié)點(diǎn)，第二個(gè)層次被指定接近單元中心的廣播發(fā)射節(jié)點(diǎn)，虛擬單元周期性廣播來(lái)自鄰居或節(jié)點(diǎn)成員的突發(fā)事件，方法類(lèi)似于洪泛。UMB有效的解決了多條廣播中的參照物、包碰撞和節(jié)點(diǎn)隱藏問(wèn)題，發(fā)送節(jié)點(diǎn)在無(wú)任何優(yōu)先拓?fù)湫畔⑾罗D(zhuǎn)發(fā)廣播包時(shí)選擇更遠(yuǎn)的節(jié)點(diǎn)，該協(xié)議在高負(fù)載和密集汽車(chē)流量條件下更適用。V-TRADE類(lèi)似于基于消息廣播協(xié)議的GPS，基本思想與任意廣播路由協(xié)議ZRP(Zone Routing Protocol)相識(shí)，V-TRADE將鄰居節(jié)點(diǎn)依據(jù)位置信息和移動(dòng)信息分成不同的轉(zhuǎn)發(fā)組信息分為不同的轉(zhuǎn)發(fā)組，每個(gè)組就是一個(gè)小的再?gòu)V播域，其改進(jìn)了帶寬利用率，路由開(kāi)銷(xiāo)主要來(lái)源于選擇每一跳的下一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)。

3.5 GB路由協(xié)議

GB路由協(xié)議是一個(gè)基于地理位置的組播路由，它從源到其他節(jié)點(diǎn)在指定的位置相關(guān)域ZOR(Zone of Relevance)傳輸數(shù)據(jù)包，并盡量避免廣播包到達(dá)ZOR之外造成浪費(fèi)，通常定義轉(zhuǎn)發(fā)域并洪泛數(shù)據(jù)包以減小消息開(kāi)銷(xiāo)并避免碰撞，在目的域通過(guò)任意播路由轉(zhuǎn)發(fā)數(shù)據(jù)包。典型的路由協(xié)議為：定向洪泛IVG(Inter-Vehicle Geocast)[18]和ROVER(Robust Vehicular Routing)[19]協(xié)議，非洪泛DG-CastOR(Direction-based GeoCast Routing Protocol)[20]協(xié)議。

IVG協(xié)議多用在高速公路上傳播告警信息，轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)為解決網(wǎng)絡(luò)拓?fù)渥兓芷谛詮V播設(shè)置定時(shí)器。ROVER采用在區(qū)域相關(guān)范圍內(nèi)向其他節(jié)點(diǎn)發(fā)送數(shù)據(jù)包，這種協(xié)議方式下控制包采用廣播的方式，數(shù)據(jù)包采用單播的方式。ROVER應(yīng)用了可靠的地理位置組播協(xié)議，不足之處是冗余數(shù)據(jù)帶來(lái)高時(shí)延，協(xié)議開(kāi)銷(xiāo)大。

DG-CastOR基于有效鏈路尺度基礎(chǔ)上的Geocast路由，主要思想是周期性評(píng)估具有相同運(yùn)動(dòng)軌跡的鄰居節(jié)點(diǎn)的通信能力，其中，單獨(dú)聚集域代表了一個(gè)廣播的路由域，聚集域間的源和鄰居將根據(jù)通信能力評(píng)估結(jié)果進(jìn)行路由。該協(xié)議可動(dòng)態(tài)適應(yīng)密集網(wǎng)絡(luò)和高速車(chē)輛，但評(píng)估過(guò)程需要大量的重傳。

3.6 QoSB路由協(xié)議

QoSB路由協(xié)議通過(guò)適當(dāng)?shù)馁Y源預(yù)留和網(wǎng)絡(luò)架構(gòu)保證良好的性能，在VANET網(wǎng)絡(luò)中，協(xié)議通過(guò)分析鏈路時(shí)延、鏈路穩(wěn)定性、車(chē)速、行車(chē)軌跡、車(chē)位置和車(chē)距來(lái)評(píng)估路由性能，盡力保持路由連接時(shí)間并減少鏈路恢復(fù)時(shí)間。MURU(MUlti-hop Routing for Urban)[21]協(xié)議基于汽車(chē)位置、速度和行車(chē)軌跡，采用EDD(Expected Disconnect Degree)度量尺度，優(yōu)化了源到目的間路由跳數(shù)并提供魯棒路由連接，EDD可以估計(jì)在規(guī)定時(shí)間內(nèi)路由重大的概率，選擇EDD小的路徑進(jìn)行轉(zhuǎn)發(fā)。

同時(shí)基于服務(wù)質(zhì)量參數(shù)指標(biāo)時(shí)延，可分為延遲不容忍路由協(xié)議和延遲可容忍路由協(xié)議，前者包括上文TB、PB和CB路由協(xié)議中提到的典型協(xié)議。后者主要被用作農(nóng)村區(qū)域的稀疏VANET網(wǎng)絡(luò)和密集區(qū)域的晚上的小車(chē)流場(chǎng)景，在這種情況下，由于很難找到轉(zhuǎn)發(fā)數(shù)據(jù)包的節(jié)點(diǎn)，建立時(shí)延保證的端到端路由幾乎不可能，因此引入時(shí)延可容忍的因素。該技術(shù)采用承載與轉(zhuǎn)發(fā)策略，自有當(dāng)鄰居節(jié)點(diǎn)或其它可路由節(jié)點(diǎn)獲得后才將數(shù)據(jù)包轉(zhuǎn)發(fā)，否則將一直保存并承載數(shù)據(jù)包。典型的路由協(xié)議有：VADD(Vehicle-Assisted Data Delivery)[22]、GeOpps(Geographical Opportunistic)[23]和MaxProp[24]。VADD采用承載與轉(zhuǎn)發(fā)策略路由數(shù)據(jù)包，其設(shè)計(jì)在道路交叉點(diǎn)來(lái)選擇最優(yōu)可能路徑，在轉(zhuǎn)發(fā)數(shù)據(jù)包前數(shù)據(jù)包一直被存儲(chǔ)在節(jié)點(diǎn)，期間路由路徑一直被計(jì)算。Gepps在稀疏網(wǎng)絡(luò)中采用機(jī)會(huì)路由和承載與轉(zhuǎn)發(fā)策略路由消息，并表現(xiàn)出良好的包到達(dá)率、鏈路利用率性能。MaxProp同樣應(yīng)用在稀疏網(wǎng)絡(luò)中，限制數(shù)據(jù)包傳輸幾率，將對(duì)路由操作分為鄰居發(fā)現(xiàn)、數(shù)據(jù)傳輸和存儲(chǔ)管理三個(gè)階段。

3.7 MPB路由協(xié)議

基于構(gòu)建路徑的路由協(xié)議包括單路徑(TB、PB和CB路由協(xié)議)、承載轉(zhuǎn)發(fā)路徑(QoSB路由協(xié)議)和多路徑三種。在單路徑中，鏈路失敗的路徑發(fā)現(xiàn)過(guò)程將增加時(shí)延和網(wǎng)絡(luò)開(kāi)銷(xiāo)，承載轉(zhuǎn)發(fā)路徑只適合于延遲可容忍網(wǎng)絡(luò)。

在單路徑路由中，路徑發(fā)現(xiàn)過(guò)程請(qǐng)求失敗的鏈路增加了時(shí)延和網(wǎng)絡(luò)開(kāi)銷(xiāo)。節(jié)點(diǎn)承載數(shù)據(jù)包并轉(zhuǎn)發(fā)給其他周邊節(jié)點(diǎn)的方法只適合于時(shí)延不敏感業(yè)務(wù)。另一方面，多路徑路由在首選路由失敗后提供了其他路由選擇，這就可以滿(mǎn)足錯(cuò)誤冗余降低路由發(fā)現(xiàn)過(guò)程開(kāi)銷(xiāo)。多路徑路由算法主要包括AOMDV(Ad hoc On-Demand Multi-path Distance Vector)[25]，S-AOMDV[26]，MMDSR(Multipath Multimedia Dynamic Source Routing Protocol)[27]具體描述如下。

AOMDV是AODV的擴(kuò)展，性能優(yōu)于AODV，AOMDV發(fā)現(xiàn)無(wú)循環(huán)不相交多路徑，它通過(guò)增加限制提供了鏈路不相交路徑和節(jié)點(diǎn)不相交路徑，但保持節(jié)點(diǎn)不相交路徑將會(huì)限制可選路徑的數(shù)量。S-AOMDV與AOMDV的不同之處在于：S-AOMDV通過(guò)發(fā)送額外的控制包能夠探測(cè)范圍內(nèi)所有節(jié)點(diǎn)的平均速度和跳數(shù)，從而選擇最優(yōu)傳輸路由，這些額外的包增加了流量，降低了帶寬利用率。MMDSR是DSR的改進(jìn)，但構(gòu)建路由的方式與MMDSR不同，每個(gè)節(jié)點(diǎn)記錄鄰居路由表去尋找路由，通過(guò)接收請(qǐng)求信息改進(jìn)路由，該協(xié)議保證每個(gè)節(jié)點(diǎn)在傳送數(shù)據(jù)時(shí)只加入一條路由。考慮到路由開(kāi)銷(xiāo)的增長(zhǎng)，實(shí)際中，MMDSR中同一時(shí)間的設(shè)計(jì)路徑不超過(guò)三條，當(dāng)標(biāo)簽了應(yīng)用區(qū)分的數(shù)據(jù)包到達(dá)時(shí)，將判斷其需求而選擇不同的路徑，且三種不同路徑可設(shè)置不同的尋路方式和Error處理方式，有效的解決了DSR重復(fù)廣播，過(guò)期路由準(zhǔn)確性差的問(wèn)題，但同時(shí)也增加了數(shù)據(jù)包頭的額外開(kāi)銷(xiāo)，且增大的傳播沖突概率。

4 VANET路由協(xié)議性能比較

在真實(shí)環(huán)境中測(cè)試和評(píng)估VANET的協(xié)議和應(yīng)用有很大難度，因此利用仿真工具進(jìn)行VANET研究和性能評(píng)估就成為了一種很有效的技術(shù)手段。第3節(jié)中提到的不同類(lèi)路由協(xié)議基本的轉(zhuǎn)發(fā)和路由方式包括：優(yōu)先轉(zhuǎn)發(fā)策略，數(shù)字地圖需求，虛擬化需求，真實(shí)交通流量，覆蓋策略、應(yīng)用場(chǎng)景等，對(duì)比如表1所示。

表1 路由協(xié)議基本的轉(zhuǎn)發(fā)和路由方式對(duì)比表

VANET路由協(xié)議的性能指標(biāo)主要包括：(1)平均端到端時(shí)延，該指標(biāo)表明一個(gè)數(shù)據(jù)包從源節(jié)點(diǎn)通過(guò)VANET到目的節(jié)點(diǎn)的平均時(shí)延。(2)包傳輸率。該指標(biāo)表明一個(gè)數(shù)據(jù)包從源節(jié)點(diǎn)通過(guò)VANET到目的節(jié)點(diǎn)的成功率，它是目的節(jié)點(diǎn)接收數(shù)據(jù)包數(shù)量與源節(jié)點(diǎn)發(fā)送相關(guān)數(shù)據(jù)包總量的比。(3)數(shù)據(jù)吞吐量，該指標(biāo)是源節(jié)點(diǎn)注入網(wǎng)絡(luò)總bits與到達(dá)目的節(jié)點(diǎn)的時(shí)間的比。(4)路由開(kāi)銷(xiāo)，該指標(biāo)描述數(shù)據(jù)包成功傳輸條件下路由協(xié)議額外產(chǎn)生的流量。定義為：路由協(xié)議額外復(fù)制的數(shù)據(jù)包數(shù)量與成功到達(dá)目的節(jié)點(diǎn)數(shù)據(jù)包數(shù)量的比。(5)可擴(kuò)展性，該指標(biāo)描述路由算法控制網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量增長(zhǎng)的能力。

本文采用網(wǎng)絡(luò)仿真軟件NS2建立仿真場(chǎng)景，采用MOVE快速生成真實(shí)運(yùn)動(dòng)模型，分別選擇每種協(xié)議類(lèi)型中的一個(gè)代表，為T(mén)ORA、LOUVRE、CBDRP、V-TRADE、DG-CastOR、MaxProp、AOMDV本文模型仿真的主要參數(shù)如表2所示。

表2 仿真場(chǎng)景指標(biāo)

鑒于文章篇幅，只對(duì)單個(gè)性能指標(biāo)中最大最小值進(jìn)行判定，仿真結(jié)果如表3所示，表中“—”代表間于最小與最大之間，一橫行中有多個(gè)最大或最小的情況表明兩協(xié)議在該指標(biāo)的多次仿真結(jié)果具有某范圍不穩(wěn)定性，無(wú)法區(qū)分大小。

表3 性能指標(biāo)對(duì)比表

5 結(jié)語(yǔ)

未來(lái)VANET路由協(xié)議性能需求可能包括改進(jìn)協(xié)議可靠性、降低數(shù)據(jù)包傳輸時(shí)延和重傳次數(shù)將成為VANET路由協(xié)議的主要挑戰(zhàn)；在路由協(xié)議的設(shè)計(jì)中司機(jī)行為的因素將被考慮在內(nèi)；設(shè)計(jì)有效的Geocast路由協(xié)議，滿(mǎn)足時(shí)延冗余能力和突發(fā)消息網(wǎng)絡(luò)帶寬預(yù)留。從VANET特點(diǎn)來(lái)看，應(yīng)用于車(chē)間通信的路由協(xié)議可以利用GPS系統(tǒng)、導(dǎo)航系統(tǒng)、電子地圖獲得節(jié)點(diǎn)的位置、道路拓?fù)湫畔⒑吐窂揭?guī)劃信息等，節(jié)點(diǎn)集、道路集和轉(zhuǎn)彎限制集等可有效支撐用戶(hù)和軟件的需求，使之能更快、更準(zhǔn)地計(jì)算出最佳路徑，未來(lái)VANET路由協(xié)議的發(fā)展方向應(yīng)該是位置與電子地圖相結(jié)合的路由協(xié)議。

[1]FIEBIG B． European Accidents and Purposed Solutions[R]．Proc of the ITU-T Workshop on Standardization in Telecommunication for Motor Vehicles,2015:24-25．

[2]Internet ITS consortium[EB/OL].http://www.internetits.org.2006.

[3]Pei G,Gerla M,Chen T W.Fisheye State Routing:A Routing Scheme for Ad Hoc Wireless Networks[S].Proc.ICC 2000,New Orleans,LA,June 2000:70-74.

[4]Perkins C,Belding-Royer E,Das S.Ad hoc On-Demand Distance Vector (AODV) Routing[S].Request for Comments:3561,2003:16-29.

[5]Johnson D B,Maltz D A.Dynamic Source Routing in Ad Hoc Wireless Networks[M].Mobile Computing.Mobile Computing,Edited by Tomasz Imielinski and Hank Korth,Kluwer Academic Publishers,1996,153-181.

[6]Park V D,Corson M S.A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks[C].INFOCOM ’97,Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies.Proceedings IEEE,1997,3(1):1405-1413.

[7]Lochert C,Hartenstein H,Tian J.A Routing Strategy for Vehicular Ad hoc Networks in City Environments[C].Intelligent Vehicles Symposium,2003,Proceedings.IEEE,June 2003:156-161.

[8]Lochert C,Mauve M,Fussler H.Geographic Routing in City Scenarios[J].SIGMOBILE Mob.Comput.Commun.Rev.,2005,9(1):69-72.

[9]Naumov V,Gross T R.Connectivity-Aware Routing (CAR) in Vehicular Ad-hoc Networks[C].INFOCOM 2007.26th IEEE International Conference on Computer Communications.IEEE,2007:1919-1927.

[10]Rondinone M,Gozalvez J.Contention-based Forwarding with Multi-hop Connectivity Awareness in Vehicular Ad-hoc Networks[J].Computer Neteons,2013,57(8):1821-1837.

[11]Guangyu Li,Lila Boukhatem.Adaptive Vehicular Routing Protocol Based on Ant Colony Optimization[J].Proceeding of the Tenth ACM International Workshop on Vehicular Inter-networking,Systems,and Applications,2013:95-98.

[12]Sharma D K,Kumar C,Mand S.An Efficient Cluster Based Routing Protocol for MANET[C].Advance Computing Conference (IACC),2013 IEEE 3rd International,Feb 2015:224-229.

[13]Luo Y Y,Zhang W,Hu Y Q.A New Cluster Based Routing Protocol for VANET[C].IEEE Wireless Communications and Trusted Computing,Apr 2010:176-180.

[14]Song T,Xia W,Song T C.A Cluster-based Directional Routing Protocol in VANET[C].International Conference on Communication and Mobile Computing,Nov 2010:1172-1175.

[15]Durresi M.Emergency Broadcast Protocol for Inter-vehicle Communications[C].Parallel and Distributed Systems,2005.Proceedings.11th International Conference on,Jul 2005:402-406.

[16]Korkmaz G.Urban Multi-hop Broadcast Protocol for Inter-vehicle Communication System[C].Proceedings of the 1st ACM International Workshop on Vehicular ad Hoc Networks,New York,NY,USA,2004:76-85.

[17]Tonguz O,Wisitpongphan N,Bai F.Broadcasting in VANET[C].Mobile Networking for Vehicular Environments,2007:7-12.

[18]Bachir A.A Multicast Protocol.in Ad hoc Networks Inter-vehicle Geocast[C].Vehicular Technology Conference,2003.VTC 2003-Spring.The 57th IEEE Semiannual,April 2003:2456-2460.

[19]Kihl M.Reliable Geographical Multicast Routing in Vehicular Adhoc Networks[C].5th International Conference,WWI,Coimbra,Portugal,2007:315-325.

[20]Atéchian T,Brunie L,Roth J.DG-castoR:Direction-based Geo-cast Routing Protocol for Query Dissemination in VANET[C].IADIS International Telecommunications,Networks and Systems,2008:1-7.

[21]Mo Z,Zhu H,Makki K.MURU:A Multi-hop Routing Protocol for Urban Vehicular Ad Hoc Networks[C].In Proceedings of 3rd International MOBIQUITOUS Conference,San Jose,CA,June 2006:1-8.

[22]Zhao J,Cao G.VADD:Vehicle-assisted Data Delivery in Vehicular Ad Hoc Networks[C].In Proceedings of 25th IEEE International Conference on Computer Communications,Barcelona,Spain,April 2006:1-12.

[23]Leontiadis I,Mascolo C.GeOpps:Geographical Opportunistic Routing for Vehicular Networks[C].In Proc.WoWMoM,Helsinki,Finland,June 2007:1-6.

[24]Burgess J,Gallagher B,Jensen D.MaxProp:Routing for Vehicle-based Disruption-tolerant Networks[C].In Proceedings of 25th IEEE International Conference on Computer Communications,Barcelona,Spain,April 2006:1-11.

[25]Mahesh M K,Das S R.On-demand Multipath Distance Vector Routing in Ad Hoc Networks[C].InProceedings of 9th IEEE Interna-tional Conference on Network Protocols,California,USA,Nov 2001:14-23.

[26]Yu F C,Zheng T X,Wei J.An Improved AOMDV Routing Protocol for V2V Communication[C].In Pro-ceedings of the IEEE Intelligent Vehicles Symposium,Xi an,China,June 2009:1115-1120.

[27]Hamzeh K.Performance Evaluation of a Game Theoretical Routing Protocol over Mobile Ad Hoc Networks[J].Universitat Politecnica de Catalunya,April 2013:41-47.

(責(zé)任編輯 趙冰)

A Survey on Routing Technology in Vehicular Ad Hoc NETwork

HUANG Ji-hai，ZHAO Bing

(College of Information Engineering,Zhengzhou Institute of Technology, Zhengzhou 450044, China)

Routing technology in Vehicular Ad hoc NETwork has the most remarkable aspects in the field of intelligent traffic in recent years. Routing technology faces most huge challenge because of the characteristic include larger node density, faster topology changing and so on. Based on the meanings and contents of Routing technology in Vehicular Ad hoc NETwork, this paper introduced the basic architecture of Vehicular Ad hoc NETwork for routing technology firstly. The characteristics of Vehicular Ad hoc NETwork was summarized secondly. Routing models were divided into different types and introduced about crucial details. The performance of different routing protocols was compared by each other. Finally, the problems and the development trend of routing technology in Vehicular Ad hoc NETwork were discussed.

Vehicular Ad Hoc Network; routing technology; path; forwarding

2016-12-24

河南省科技廳計(jì)劃基金資助項(xiàng)目(122102210142);河南省高等學(xué)校重點(diǎn)計(jì)劃項(xiàng)目(15A520066)

黃繼海(1977—)，男，河南臺(tái)前人，碩士，鄭州工程技術(shù)學(xué)院信息工程學(xué)院副教授，主要研究方向?yàn)橄乱淮W(wǎng)絡(luò)體系架構(gòu)。

10.13783/j.cnki.cn41-1275/g4.2017.02.027

TN929

A

1008-3715(2017)02-0117-07