【文章內(nèi)容簡介】 如路邊單元可在節(jié)點稀少道路作為消息點，用來提供地理位置數(shù)據(jù)，或作為接入互聯(lián)網(wǎng)的網(wǎng)關(guān)。VANET是有其自身特點的特殊MANET，具有節(jié)點移動速度快、車輛受道路和交通規(guī)則限制拓?fù)涑使軤?、不斷變化的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、城市道路環(huán)境下障礙物阻隔造成通信域頻繁分割、鄉(xiāng)村道路環(huán)境下節(jié)點的密集程度不夠高導(dǎo)致在同一通信范圍內(nèi)的節(jié)點無法通信等特點一般情況下，車輛運動的速度比MANET節(jié)點運動的速度快。由于同一方向的車輛行駛速度基本相同，所以它們之間無線通信持續(xù)時間比反方向行駛的車輛間的持續(xù)時間長得多。由于VANET的獨有特性，為MANET開發(fā)的路由協(xié)議[19，20]并不能直接有效地應(yīng)用于VANET。因此由于VANET的預(yù)期潛在影響，研究人員已經(jīng)開發(fā)了許多適用于VANET的路由協(xié)議。文獻(xiàn)[2124]對VANET交通模式的影響和擁塞進(jìn)行了研究。文獻(xiàn)[2529]對VANET安全問題進(jìn)行了研究。通過使用仿真實驗來再現(xiàn)真實的城市和道路場景，對VANET路由協(xié)議仿真和試驗者來說是一個挑戰(zhàn)。文獻(xiàn)[3033]對專用于VANET仿真問題進(jìn)行了研究。文獻(xiàn)[34]對共享寬帶公平性進(jìn)行了研究。目前針對VANET所設(shè)計的路由協(xié)議主要可以分為四類，（1）基于位置的路由協(xié)議(Positionbased Routing，PBR)；（2）延時可容忍網(wǎng)絡(luò)路由協(xié)議(Delaytolerant Network Routing，DNR)；（3）服務(wù)質(zhì)量路由協(xié)議；（4）基于地圖的路由協(xié)議(Mapbased Routing，MBR)。本節(jié)分類闡述車載Ad hoc網(wǎng)絡(luò)路由協(xié)議研究現(xiàn)狀。在移動Ad hoc網(wǎng)絡(luò)中，由于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的頻繁變化、無線鏈路的有限帶寬、通信需要通過多跳、無固定的基礎(chǔ)設(shè)施等因素，傳統(tǒng)的TCP/IP協(xié)議中的路由協(xié)議已不再適用，需要研究新的路由協(xié)議。當(dāng)前的移動Ad hoc網(wǎng)絡(luò)路由協(xié)議種類繁多，可以從不同的角度進(jìn)行分類。根據(jù)路由發(fā)現(xiàn)策略，可以分為先應(yīng)式路由協(xié)議和反應(yīng)式路由協(xié)議。采用先應(yīng)式路由協(xié)議的網(wǎng)絡(luò)中每個節(jié)點維護(hù)一張包含到達(dá)其他節(jié)點路由信息的路由表，并根據(jù)網(wǎng)絡(luò)拓?fù)涞淖兓皶r更新該路由表，其代表協(xié)議有DSDV、HSR、GSR、WRP等；反應(yīng)式路由協(xié)議是一種當(dāng)節(jié)點需要發(fā)送數(shù)據(jù)時才發(fā)起路由請求的路由算法，節(jié)點不需要周期性的維護(hù)路由表，其代表協(xié)議有AODV、DSR、TORA等；根據(jù)網(wǎng)絡(luò)的邏輯結(jié)構(gòu)，可以分為平面路由協(xié)議和分級路由協(xié)議；根據(jù)尋址方式，可以分為基于網(wǎng)絡(luò)拓?fù)涞穆酚蓞f(xié)議和基于位置的路由協(xié)議?；谖恢玫穆酚蓞f(xié)議利用每個節(jié)點的位置信息計算該節(jié)點的鄰居節(jié)點到目的節(jié)點的距離，選擇離目的節(jié)點距離最近的鄰居節(jié)點作為數(shù)據(jù)轉(zhuǎn)發(fā)的下一跳，其代表協(xié)議有GPSR、LAR、GeoCast等。由于路由協(xié)議的種類繁多，這里結(jié)合車載Ad hoc網(wǎng)絡(luò)的特點簡要介紹一些適用于VANET的MANET路由協(xié)議。VANET的路由層必須有效地處理由不同的駕駛行為、車輛移動限制、車輛高速移動帶來頻繁的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化。分層路由協(xié)議在設(shè)計上非常復(fù)雜，路由維護(hù)代價太高，因此平面路由協(xié)議與基于位置的路由協(xié)議更加適合于車載Ad hoc網(wǎng)絡(luò)。在平面路由協(xié)議中，主動路由協(xié)議中的移動站點需要維護(hù)路由，有較大的路由開銷，按需路由協(xié)議在需要路由時才建立路由，因此按需路由在車載Ad hoc網(wǎng)絡(luò)優(yōu)勢也較明顯?；谖恢玫穆酚蓞f(xié)議也是車載Ad hoc網(wǎng)絡(luò)很好的選擇。DSR(Dynamic Source Routing)是一種使用源路由算法而不是逐跳(Hopbyhop)查找的路由協(xié)議，該路由協(xié)議包括路由發(fā)現(xiàn)和路由維護(hù)兩部分[35]。DSR在報文的頭部攜帶到達(dá)目的節(jié)點所要經(jīng)過節(jié)點的信息作為路由選擇的依據(jù)，中間節(jié)點按照該路由序列來轉(zhuǎn)發(fā)報文。具體流程如下，當(dāng)源節(jié)點向目的節(jié)點發(fā)送數(shù)據(jù)時，首先在自己的路由緩存中查找是否存在到達(dá)目的節(jié)點且未過時的路由，如存在，則立即使用此路由發(fā)送數(shù)據(jù)分組，否則啟動路由發(fā)現(xiàn)過程，使用洪泛法向所有鄰居節(jié)點廣播RREQ(Route Request)分組來找到一條到達(dá)該目的節(jié)點的可用路由。如果節(jié)點在發(fā)送數(shù)據(jù)時出現(xiàn)了鏈路斷裂，那么DSR就啟動路由維護(hù)機(jī)制。DSR支持主動應(yīng)答和被動應(yīng)答兩種鏈路狀態(tài)監(jiān)測方法。一旦發(fā)現(xiàn)鏈路斷裂，斷裂處的上游節(jié)點就向源節(jié)點發(fā)送錯誤分組RERR(Route Error)，源節(jié)點收到RERR分組后將該RERR分組中通知的失效路由從路由表中刪除，沿途轉(zhuǎn)發(fā)RERR分組的節(jié)點也從自己的路由表中刪除包含該斷開鏈路的所有路由。為了保證網(wǎng)絡(luò)性能而減少路由控制報文數(shù)量，DSR路由協(xié)議在路由請求分組中設(shè)置一個序號以及一個生存時間值即TTL值來避免重復(fù)轉(zhuǎn)發(fā)路由請求，并使用路由緩存和中間節(jié)點應(yīng)答機(jī)制使源節(jié)點能夠快速獲得到達(dá)目的節(jié)點的路由。在該機(jī)制中，中間節(jié)點如果存在到達(dá)目的節(jié)點的路由就直接向源節(jié)點回復(fù)RREP分組，但該機(jī)制會引起路由失效問題以及路由回復(fù)風(fēng)暴。反應(yīng)式路由協(xié)議AODV(Ad hoc On Demand Distance Vector Routing)根據(jù)業(yè)務(wù)需要建立和維護(hù)到達(dá)目的節(jié)點的路由[36]。與DSR路由協(xié)議一樣，只有當(dāng)節(jié)點需要發(fā)送數(shù)據(jù)的時候才廣播RREQ分組，收到該RREQ分組的節(jié)點創(chuàng)建到達(dá)源節(jié)點的反向路由。目的節(jié)點收到路由請求后以單播的方式向源節(jié)點響應(yīng)一個RREP分組，中間節(jié)點收到此RREP分組時建立到目的節(jié)點的正向路由。AODV綜合了DSDV(Destination Sequenced Distance Vector Routing)算法[37]各自的優(yōu)點，借鑒了DSR中路由發(fā)現(xiàn)和路由維護(hù)的思想以及DSDV中節(jié)點序列號機(jī)制，通過使用目的序列號有效地防止了路由環(huán)路以及過時路由的發(fā)生，并能判斷中間節(jié)點是否響應(yīng)了相應(yīng)的路由請求。AODV協(xié)議使用基于目的節(jié)點的路由表機(jī)制，有別于DSR使用節(jié)點的路由緩存來維護(hù)路徑信息的工作方式。該協(xié)議使用定期洪泛的HELLO信息分組來檢測其和鄰居節(jié)點之間的鏈路狀態(tài)并進(jìn)行更新鄰居狀態(tài)列表。雖然其控制包的總數(shù)量比DSDV協(xié)議的控制包數(shù)要少，但是周期性地廣播控制分組，仍然需要消耗掉一部分的網(wǎng)絡(luò)帶寬。OLSR(Optimized Link State Routing)算法要求每個節(jié)點維護(hù)著鄰居表、MPR(Multipoint Relay)表等多張控制信息表，并且通過周期性的交換HELLO分組和TC(Topology Control)分組來交換網(wǎng)絡(luò)信息，通過分布式計算來更新和建立自己的網(wǎng)絡(luò)拓?fù)鋱D[38]。OLSR與其他表驅(qū)動路由協(xié)議最大的不同在于采用了一種被稱為多點中繼的技術(shù)。當(dāng)一個節(jié)點要廣播TC分組時，不再是它的所有鄰居節(jié)點都轉(zhuǎn)發(fā)這個TC分組，而是在該節(jié)點的鄰居節(jié)點中選擇MPR來轉(zhuǎn)發(fā)。在OLSR算法中，中心節(jié)點N的TC分組只由其周圍四個MPR轉(zhuǎn)發(fā)就可以到達(dá)所有的兩跳節(jié)點，這樣就減少了網(wǎng)絡(luò)中廣播分組的數(shù)量，降低了控制分組給網(wǎng)絡(luò)帶來的負(fù)荷。同時，在TC分組中并沒有包含源節(jié)點所有鄰居節(jié)點的地址，而僅僅包含了將該節(jié)點選為MPR的鄰居節(jié)點地址(MPR selector)，這些信息足以讓網(wǎng)絡(luò)中的各個節(jié)點形成網(wǎng)絡(luò)拓?fù)鋱D，進(jìn)而獨立地計算路由表，從而縮小了控制分組的大小。Brad (Greedy Perimeter Stateless Routing)是一種典型的基于位置的路由協(xié)議[66]。GPSR協(xié)議假定網(wǎng)絡(luò)中各節(jié)點都能夠獲取自身的地理位置且被統(tǒng)一編址，利用貪婪算法盡量沿直線轉(zhuǎn)發(fā)數(shù)據(jù)即貪婪轉(zhuǎn)發(fā)。產(chǎn)生或收到數(shù)據(jù)的節(jié)點通過計算該節(jié)點的鄰節(jié)點到目的節(jié)點的歐氏距離，選擇距離目的節(jié)點最近的鄰居節(jié)點作為轉(zhuǎn)發(fā)數(shù)據(jù)的下一跳。在該路由協(xié)議中，每個節(jié)點必須獲得以下信息，節(jié)點自身的地理位置信息、鄰居節(jié)點的地理位置信息以及目的節(jié)點的地理位置信息。自身的位置可以通過GPS(Global Positioning System)獲得；鄰居節(jié)點的位置可以通過周期發(fā)送信標(biāo)信息獲得；目的節(jié)點的位置通過提供位置信息服務(wù)獲得。GPSR是無狀態(tài)的，即每個節(jié)點只需要知道節(jié)點本身和其鄰居的位置信息，即可做出路徑選擇，而不需要維護(hù)其它的狀態(tài)。這使得它具有非常好的可縮放性，能夠勝任節(jié)點數(shù)目非常多的網(wǎng)絡(luò)。但在GPSR協(xié)議中，如果所有鄰居節(jié)點到目的節(jié)點的距離都比當(dāng)前節(jié)點到目的節(jié)點的距離遠(yuǎn)，即中間轉(zhuǎn)發(fā)節(jié)點達(dá)到本地最優(yōu)時，存在一個空洞區(qū)域，這將導(dǎo)致數(shù)據(jù)分組無法傳遞。此時如果能夠探測到空洞周邊的節(jié)點，那么GPSR就采用右手定則沿著空洞的邊界進(jìn)行轉(zhuǎn)發(fā)，直到找到一個距離目的節(jié)點更近的節(jié)點，然后再采用貪婪算法轉(zhuǎn)發(fā)數(shù)據(jù)分組。該協(xié)議避免了在節(jié)點中建立、維護(hù)、存儲路由表，只依賴直接鄰節(jié)點進(jìn)行路由選擇，數(shù)據(jù)傳輸時延小，并能保證只要網(wǎng)絡(luò)連通性不被破壞，一定能夠發(fā)現(xiàn)可達(dá)路由。但當(dāng)網(wǎng)絡(luò)中源節(jié)點和目的節(jié)點分別位于兩個區(qū)域時，由于通信量不平衡易導(dǎo)致部分節(jié)點失效，從而破壞網(wǎng)絡(luò)連通性，造成分組無法投遞。這是網(wǎng)絡(luò)節(jié)點分布不均導(dǎo)致協(xié)議存在的固有缺陷，在延時可容忍網(wǎng)絡(luò)[6768]以及機(jī)會網(wǎng)絡(luò)(Opportunistic Networks)[69]中，國內(nèi)外許多學(xué)者對此進(jìn)行了研究，并提出了許多可行的解決方案。GPSR工作機(jī)制將在第三章進(jìn)行詳細(xì)闡述。在城市環(huán)境中，由于街道兩邊的障礙物導(dǎo)致節(jié)點間無法進(jìn)行通信。文獻(xiàn)[70]針對此問題，提出了一種新的路由協(xié)議GPCR(Greedy Perimeter Coordinator Routing)。GPCR也是一種基于位置的路由協(xié)議，但是GPCR不使用任何地理位置信息或外部信息如靜態(tài)街道地圖，而是使用了街道和十字路口形成平面圖這一自然特征。GPCR包括受限的貪婪轉(zhuǎn)發(fā)和修復(fù)策略兩個部分，在受限的貪婪轉(zhuǎn)發(fā)模式下，十字路口是路由決策的最佳位置，因此分組應(yīng)該總是轉(zhuǎn)發(fā)到十字路口節(jié)點而不是其他節(jié)點。修復(fù)策略使用街道和十字路口拓?fù)浣Y(jié)構(gòu)圖，因此并不需要平面圖算法。文獻(xiàn)[71]提出了一種適用于城市環(huán)境的基于位置的路由協(xié)議GSR(Geographic Source Routing)。GSR在位置服務(wù)機(jī)制和轉(zhuǎn)發(fā)策略兩個方面對GPSR進(jìn)行改進(jìn)。在位置服務(wù)機(jī)制方面，GSR使用反應(yīng)式的位置服務(wù)RLS使用一種廣播機(jī)制在需要的時候確定目的節(jié)點的位置。在轉(zhuǎn)發(fā)策略方面，GSR使用基于城市地圖建立一條由從源節(jié)點到目的節(jié)點的路徑上的交叉點的序列組成錨點路徑進(jìn)行源路由，錨點間仍使用貪婪算法進(jìn)行轉(zhuǎn)發(fā)。GSR通過靜態(tài)街道地圖和節(jié)點的位置信息計算到目的節(jié)點的路由，然后沿街轉(zhuǎn)發(fā)分組。源節(jié)點計算到達(dá)目的節(jié)點所必須經(jīng)過的路口序列，該路口序列可以放置在數(shù)據(jù)分組頭部字段內(nèi)或者由轉(zhuǎn)發(fā)節(jié)點決定，節(jié)點通過使用Dijkstra最短路徑算法計算源節(jié)點到和目的節(jié)點之間的路口序列。GSR是一種基于位置VANET重要的單播路由算法，但是該算法未考慮特定街道上的車輛密度，并且其需要外部實體提供靜態(tài)地圖。文獻(xiàn)[72]提出的AGF(Advanced Greedy Forwarding)算法可以顯著提高GPSR在VANET下的性能。AGF算法在GPSR的基礎(chǔ)上增加了對節(jié)點移動性的考慮，作了以下兩點補(bǔ)充。第一，源節(jié)點和目的節(jié)點通過位置發(fā)現(xiàn)服務(wù)把各自的速度矢量信息通知對方；第二，速度矢量還被添加到所有節(jié)點的HELLO信標(biāo)信息中。通過添加節(jié)點的速度矢量，轉(zhuǎn)發(fā)算法可以根據(jù)基于鄰居表中存儲的速度矢量信息來選擇下一跳節(jié)點。與GSR類似，文獻(xiàn)[73]提出的SAR(SpatiallyAware Packet Routing)路由協(xié)議也是為了克服GPSR恢復(fù)策略所導(dǎo)致的缺點而設(shè)計的。當(dāng)GPSR在網(wǎng)絡(luò)不能覆蓋的區(qū)域中達(dá)到本地最優(yōu)時，GPSR無狀態(tài)恢復(fù)策略將引起分組路由至網(wǎng)絡(luò)不能覆蓋的區(qū)域，并繼續(xù)使用該恢復(fù)策略，如果網(wǎng)絡(luò)經(jīng)常存在不可覆蓋區(qū)域，那么頻繁使用恢復(fù)策略會降低算法性能。SAR是一種依賴于靜態(tài)街道地圖的位置路由協(xié)議，其中靜態(tài)街道地圖用于構(gòu)造空間模式路由，在網(wǎng)絡(luò)不能覆蓋的區(qū)域，SAR用其來預(yù)測和恢復(fù)路由。在SAR中，節(jié)點通過其位置和街道信息來計算其到目的節(jié)點的最短路徑，當(dāng)分組路徑選定后，就將其寫入分組首部，但源路由中不包含中間節(jié)點，中間節(jié)點是基于錨點位置的信息，并且是一條基于物理位置固定的路徑。當(dāng)節(jié)點要轉(zhuǎn)發(fā)分組時，首先檢查分組首部，然后取得路由中下一個地理位置。SAR并沒有嚴(yán)格地使用貪婪策略，而是選擇分組首部路由中的鄰近節(jié)點。當(dāng)轉(zhuǎn)發(fā)節(jié)點不能找到預(yù)定路徑的節(jié)點，SAR建議采用下面的策略之一。第一，節(jié)點可以選擇將分組放入延遲緩存中，在沒有找到合適的轉(zhuǎn)發(fā)節(jié)點之前，將一直緩存分組。第二，該節(jié)點可使用貪婪轉(zhuǎn)發(fā)方式向目的節(jié)點轉(zhuǎn)發(fā)分組。第三，該節(jié)點還可以重新計算分組首部中的路由。但是作者在文獻(xiàn)中并沒有推薦一個恢復(fù)策略，也沒有指定節(jié)點如何選擇以上策略。在仿真實驗中，作者對SAR不使用恢復(fù)策略和使用延遲緩存策略兩種情況作了對比分析并得出結(jié)論，在節(jié)點稀疏網(wǎng)絡(luò)場景中，延遲緩存策略以增加分組延遲的方式獲得更高的分組投遞率。ASTAR (AnchorBased Street and Traffic Aware Routing)是專門為城市環(huán)境下的車輛間通信設(shè)計的一種基于位置的路由機(jī)制[74]。ASTAR在以下兩個方面對GPSR進(jìn)行改進(jìn)。第一，轉(zhuǎn)發(fā)策略使用加權(quán)重街道地圖信息來計算錨點路徑，并進(jìn)行源路由；第二，恢復(fù)策略通過計算一條新的錨點路徑來解決本地最優(yōu)問題。與其它基于位置的貪婪路由協(xié)議不同，為了提高分組投遞率，ASTAR使用城市公交線路尋找路由。ASTAR同樣是為了解決GPSR周邊模式選擇下一個鄰居節(jié)點而不是選擇最遠(yuǎn)的鄰居節(jié)點作為下一跳這一問題而設(shè)計的。作者在文獻(xiàn)[74]中指出，在本地最優(yōu)時，如果使用右手定則，會使節(jié)點轉(zhuǎn)發(fā)分組時偏向一個方向，而如果向相反的方向轉(zhuǎn)發(fā)，有時會得到到達(dá)目的節(jié)點更短的路由。ASTAR使用基于錨點的路由，向分組中插入能夠使分組從源節(jié)點路由至目的節(jié)點的節(jié)點轉(zhuǎn)發(fā)地理信息。與GSR類似，對于無線障礙如城市建筑周圍路徑信息，ASTAR也采用靜態(tài)街道地圖的方式來獲得。在城市環(huán)境中，一些街道比其它街道的交通流更密集，如果能利用這些環(huán)境特征，將有利于節(jié)點路由的選擇。ASTAR使用公交線路信息來輔助路由信息的獲取，其假定公交車通常會流入主干道，且主干道有更高車輛密度，每條街道分配一個與其公交車數(shù)量成反比的權(quán)值，然后使用Dijkstra的最小路徑算法來計錨點路由。當(dāng)分組達(dá)到本地最優(yōu)時，ASTAR恢復(fù)模式規(guī)定達(dá)到本地最優(yōu)的轉(zhuǎn)發(fā)節(jié)點計算沿錨點路徑的另外一條新路由，并將路由重新寫入分組首部。為了阻止其它分組達(dá)到相同的本地最優(yōu)，ASTAR