，

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

0 引 言

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

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

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

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

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

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

隨著全球定位系統(tǒng)(global positioning system,GPS)日益普及和電子地圖廣泛應(yīng)用，這為基于地理位置路由協(xié)議應(yīng)用提供了條件?；诘乩砦恢寐酚衫密囕v的地理位置信息而不是拓?fù)涞倪B通信息去構(gòu)建路由,例如：文獻(xiàn)[17～20]。

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

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

1 VANETs路由

1.1 基于連通路由

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

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

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

1.2 基于移動(dòng)預(yù)測(cè)路由

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

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

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

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

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

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

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

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

1.4 基于地理位置路由

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

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

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

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

1.5 基于概率路由

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

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

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)。前者是指目標(biāo)節(jié)點(diǎn)所在的區(qū)域，后者是指轉(zhuǎn)發(fā)節(jié)點(diǎn)所在的區(qū)域。該方案首先在ZOR廣播數(shù)據(jù)包，并將廣播持續(xù)到預(yù)設(shè)的時(shí)間?？筛鶕?jù)不同應(yīng)用環(huán)境，設(shè)置不同的廣播時(shí)長。

2 五類路由特點(diǎn)比較

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

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

3 結(jié) 論

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

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

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

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

參考文獻(xiàn):

[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] 徐會(huì)彬，夏 超.VANETs路由綜述[J].計(jì)算機(jī)應(yīng)用研究,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.