【正文】 前那條路徑可用，刪除在可用路徑中受影響最少的分組。如上所述，SNAR廣泛使用優(yōu)化路徑。使用靜態(tài)道路地圖和路徑轉(zhuǎn)發(fā)期望時延的權(quán)值來決定優(yōu)化路徑。SADV通過使用實時交通流密度信息來產(chǎn)生路徑轉(zhuǎn)發(fā)期望時延。LDU模式使用靜態(tài)節(jié)點間的分組投遞延遲來動態(tài)維持延遲矩陣。當靜態(tài)節(jié)點收到分組時，分組頭中打一個時間戳，然后轉(zhuǎn)發(fā)該分組。當該分組到達下一個靜態(tài)節(jié)點時，節(jié)點同樣能夠獲得各入口方向分組的時間延遲。在一個特定時間內(nèi)，節(jié)點計算入口方向的平均時延并向鄰居靜態(tài)節(jié)點廣播該分組。當交通流很低時，SADV的MPDD模式使用多徑路由。為了降低對車輛的協(xié)議棧的影響，只有靜態(tài)節(jié)點才使用多徑路由投遞分組。在MPDD模式下，靜態(tài)節(jié)點為每條分組選擇最好的兩條路徑，并向兩條路徑轉(zhuǎn)發(fā)分組。為了避免路由環(huán)產(chǎn)生過量的路由開銷，靜態(tài)節(jié)點記錄一定時間內(nèi)其發(fā)送過的分組，在這段時間中丟棄收到的分組副本。作者在仿真實驗中并沒有涉及單向街道的場景。因為單向街道場景分組沿交通流相反方向進行傳輸效率并不高，因此單向街道場景將影響到SADV性能 。與其它為容忍時延網(wǎng)絡(luò)所設(shè)計的路由算法一樣，文獻[43]提出的GeOpps(Geographical Opportunistic Routing)算法也使用機會路由和儲存轉(zhuǎn)發(fā)方式來為節(jié)點稀疏網(wǎng)絡(luò)路由分組。其特點在于使用導航信息來有效的路由分組。GeOpps假定，車輛能通過GPS獲得其位置信息、導航系統(tǒng)能提供到達目的節(jié)點的路由以及靜態(tài)路邊單元的位置信息。在GeOpps協(xié)議中，當源節(jié)點向目的節(jié)點發(fā)送一條分組時，中間節(jié)點使用以下方式選擇下一跳，利用導航系統(tǒng)提供的路由來計算到目的節(jié)點最近的鄰居車輛節(jié)點，使用導航系統(tǒng)的應(yīng)用功能來計算到達轉(zhuǎn)發(fā)節(jié)點的時間，選擇投遞包最快或最接近目的節(jié)點的車輛作為下一跳。GeOpps考慮了一些特殊情況，如果司機不使用導航系統(tǒng)提供的路由，那么節(jié)點將向所有鄰居轉(zhuǎn)發(fā)分組。如果車輛停留超過一定的時間或引擎關(guān)閉，那么車輛攜帶的所有分組將轉(zhuǎn)發(fā)至下一跳可用車輛。該算法不要求所有的車輛都配備導航系統(tǒng)，此時使用貪婪算法來路由分組。在節(jié)點稀疏、容忍時延網(wǎng)絡(luò)應(yīng)用中，GeOpps有較優(yōu)的性能。對GeOpps路由協(xié)議，客戶導航系統(tǒng)之間的差異將給設(shè)計帶來困難，困難程度取決于導航系統(tǒng)所考慮的限制因素(如速度限制、交通流狀況、道路類型和平均駕駛速度)。文獻[44]提出的另一種容忍時延網(wǎng)絡(luò)路由算法MaxProp使用存儲轉(zhuǎn)發(fā)和分組優(yōu)先級來提高分組投遞率。MaxProp已經(jīng)在UMass DieselNet網(wǎng)絡(luò)中實現(xiàn)，部署在公車上，允許公車相遇時與無線訪問點或者其它公車進行通信以交換位置和功能信息。該算法是早期路由算法MV的擴展，并要求節(jié)點能夠通過GPS獲得其位置信息。MaxProp有三種基本模式，鄰居發(fā)現(xiàn)模式、數(shù)據(jù)傳輸模式以及存儲管理模式。分組開始傳輸之前，節(jié)點使用鄰居發(fā)現(xiàn)模式來發(fā)現(xiàn)其他節(jié)點。數(shù)據(jù)傳輸模式用來在節(jié)點間傳輸受限數(shù)據(jù)。節(jié)點使用存儲管理來管理其緩存，根據(jù)優(yōu)先級算法刪除分組。在默認情況下，下一個鄰居發(fā)現(xiàn)模式開始之前節(jié)點一直攜帶分組。如果分組沒有超時，那么在遇到其他可用節(jié)點時轉(zhuǎn)發(fā)此分組，在數(shù)據(jù)傳輸模式中通過ACK來確保分組的正確投遞。存儲管理模式下緩存滿時刪除分組。數(shù)據(jù)傳輸模式下，MaxProp按照高優(yōu)先級優(yōu)先的原則來投遞分組。在存儲管理模式下，按照低優(yōu)先級優(yōu)先的原則來刪除分組。存儲在節(jié)點中的分組用其投遞分組至目的節(jié)點的代價來確定優(yōu)先級。為了確定投遞代價，MaxProp中的節(jié)點記錄遇到其他節(jié)點的概率值。MaxProp使用加權(quán)平均法來修改概率值。在每次相遇時，節(jié)點交換這些概率值。有了這些值就可以通過加上路由中每條連接發(fā)生與否的概率來計算投遞分組的代價。代價至少應(yīng)該在已計算出價的路由范圍之內(nèi)。當數(shù)據(jù)傳輸開始，以先前確定的次序來投遞分組。第一步投遞前往鄰居節(jié)點的分組；第二步在節(jié)點間傳輸節(jié)點間相遇概率信息；第三步傳輸確認分組，以保證節(jié)點緩存的已投遞分組被安全刪除；第四步不管投遞分組的代價傳輸具有短跳數(shù)的分組；最后根據(jù)他們優(yōu)先級和代價投遞還沒有被投遞的緩存分組。MaxProp有兩種不同優(yōu)先級實現(xiàn)方式。根據(jù)緩存中的分組的跳數(shù)是否比門限值小來進行區(qū)分。如果跳數(shù)比動態(tài)設(shè)置的門限值小，就通過它們的跳數(shù)來確定優(yōu)先級；如果跳數(shù)比動態(tài)設(shè)置的門限值大，就通過投遞代價來確定優(yōu)先級。存儲管理模式維護節(jié)點有限緩存，當緩存滿時刪除分組。首先刪除已經(jīng)投遞且收到確認的分組。這些確認分組分布在整個網(wǎng)絡(luò)中，用來清理緩存在節(jié)點中的分組副本。再刪除跳數(shù)大于的分組以便最高投遞代價的分組優(yōu)先投遞。最后如果緩存仍然是滿的，刪除跳數(shù)低于的分組以便長跳數(shù)的分組優(yōu)先投遞。MaxProp的創(chuàng)新點在于分組優(yōu)先級、緩存管理以及計算節(jié)點相遇概率。作者在文獻中表明，在一個具有30輛公車的網(wǎng)絡(luò)中，確認分組和計算節(jié)點相遇的概率的方式是可行的技術(shù)，但是這些方式在網(wǎng)絡(luò)規(guī)模非常大時擴展性并不好。根據(jù)國際電信聯(lián)盟(International Telemunications Union，ITU)的定義，服務(wù)質(zhì)量(Quality of Service，QoS)是業(yè)務(wù)性能的綜合效果，決定了用戶的滿意程度。它是由業(yè)務(wù)的可保證性、易獲得性、完善性、可操作性以及安全性等性能因素來綜合描述的。QoS 機制的基本要求是可以度量的性能參數(shù)，典型的參數(shù)有可利用帶寬、丟包率、時延、跳數(shù)和鏈路的可靠性。無線Ad hoc網(wǎng)中各種多媒體業(yè)務(wù)的傳輸要求網(wǎng)絡(luò)提供相應(yīng)的QoS保障機制。考慮QoS要求的路由協(xié)議簡稱QoS路由協(xié)議。QoS路由協(xié)議是QoS保障機制的重要組成部分，其主要任務(wù)是找尋一條滿足多媒體業(yè)務(wù)QoS要求的路由，同時與接納控制、資源預留機制相配合。在VANET中使用術(shù)語服務(wù)質(zhì)量路由協(xié)議來描述此類協(xié)議，服務(wù)質(zhì)量路由協(xié)議為各種性能級提供保障，通?？赏ㄟ^資源預留以及足夠的基礎(chǔ)設(shè)施來解決，但在無線Ad hoc網(wǎng)絡(luò)中，保證服務(wù)質(zhì)量是一件非常困難的任務(wù)。除了路邊單元具有保證服務(wù)質(zhì)量的潛能之外，就沒有其他的基礎(chǔ)設(shè)施能夠保證了，由于無線自組織網(wǎng)絡(luò)拓撲結(jié)構(gòu)經(jīng)常變化以及其他相關(guān)的特性使得預留資源不可行。QoS路由算法目的是在車輛間提供健壯的路由，其鏈路時延、節(jié)點速度和運行路徑、節(jié)點位置、節(jié)點間距離以及鏈路可靠性等因素都會導致特定路由的穩(wěn)定性，可以使用估計路由連接持續(xù)時間的算法和優(yōu)化路由中斷后重新建立連接的時間等算法來保障車載路由服務(wù)質(zhì)量。文獻[45]提出的MURU(MultiHop Routing Protocol for Urban VANET)算法就包含了節(jié)點位置和QoS因素，其目的是使路由跳數(shù)最小化，提供健壯的路由連接。為了達到此目的，引入一種新的基于位置、速度和路徑的度量機制EDD(Expected Disconnection Degree)來估計路由的質(zhì)量。MURU需要每輛車都通過位置服務(wù)獲得其位置信息和一張靜態(tài)街道地圖。EDD是一種估計路由可能在一個給定的時間內(nèi)會中斷的度量。度量值EDD越小路由越可靠。如果節(jié)點知道了其位置、速度和路徑，就能估算路由所經(jīng)過節(jié)點的穩(wěn)定性。顯然，沿著同樣的方向以同樣的速度運動的節(jié)點維持路由比較穩(wěn)定。作者認為，在考慮車輛流量情況下，EDD值非常小和非常大的路由分組出錯率越高。計算EDD的公式使用這些因素來預測路由的中斷時間。在MURU算法中，RREQ分組累積儲存分組經(jīng)過的路徑的EDD值。如果節(jié)點收到RREQ分組立即重新廣播該分組，那么分組開銷將迅速增大。為了避免此種情況發(fā)生，MURU協(xié)議為允許節(jié)點延遲轉(zhuǎn)發(fā)RREQ分組的路由請求提供一種剪裁機制。節(jié)點收到RREQ分組將等待一個經(jīng)過計算的退避時間后才廣播，該退避時間與之前RREQ分組轉(zhuǎn)發(fā)節(jié)點和當前節(jié)點間的EDD值成比例。(如果EDD值越大，當前節(jié)點轉(zhuǎn)發(fā)延遲也就越大，這樣就存在找到具有更小EDD值的路徑的可能性)。退避期間，節(jié)點監(jiān)聽在其他節(jié)點的RREQ分組。如果節(jié)點監(jiān)聽到本節(jié)點收到的從同一源節(jié)點具有相同的序號的RREQ分組的副本，并且EDD值比本節(jié)點的EDD值小，那么該節(jié)點將丟棄該RREQ分組(這使得沿途收到RREQ分組被鏈路很可能斷掉的節(jié)點丟棄)。如果在退避期間節(jié)點沒有丟棄RREQ分組，那么就重新把該RREQ分組向由當前節(jié)點位置和目的節(jié)點位置限制的矩形區(qū)域廣播。這樣經(jīng)過每次迭代，每次重新廣播RREQ，矩形廣播域變得越來越小。當目的節(jié)點最終收到不同路由的RREQ分組，就選擇具有最小EDD值的路由。作者在文獻中表明，MURU是無環(huán)路由且總是在初始化和修復路由時選擇一條從源節(jié)點到目的節(jié)點具有最小EDD值的路由。由于在MURU中使用了矩形廣播域，易于本地最優(yōu)化。如果矩形廣播域受轉(zhuǎn)發(fā)節(jié)點和目的節(jié)點的限制，會發(fā)生這樣的問題僅有的可用下一跳節(jié)點位于矩形廣播域之外。MURU目的是控制開銷和時延來供質(zhì)量路由來提高分組投遞率。有許多算法都針對VANET車對車通信的，而文獻[46]提出的PBR(PredictionsBased Routing)算法重點研究如何向車輛提供互聯(lián)網(wǎng)連接。建設(shè)路邊靜態(tài)網(wǎng)關(guān)基礎(chǔ)設(shè)施需要大量的費用，特別是城市區(qū)域以外。相反，PBR利用具有無線局域網(wǎng)連接的移動網(wǎng)關(guān)能夠充當其他車輛網(wǎng)關(guān)的這一特性，尤其是在高速公路場景下。PBR算法首先假定每輛車都可以通過GPS或者其他的方式獲得自己的位置信息。該算法利用高速公路上少量車輛運動方式來預測從客戶車輛到移動網(wǎng)關(guān)車輛生存時間。僅當失效路由被預測之前，PBR才搶先地尋找一條新的路由來避免服務(wù)中斷。為了和互聯(lián)網(wǎng)上目的節(jié)點進行通信，和許多MANET反應(yīng)式路由一樣，節(jié)點首先檢查其路由表看是否有到目的節(jié)點的現(xiàn)存路由。如果節(jié)點沒有找到到達目的節(jié)點的現(xiàn)存路由，那么節(jié)點就廣播一條限定跳數(shù)的RREQ報文。移動網(wǎng)關(guān)收到此RREQ報文時，通過存儲在RREQ的節(jié)點序列向源節(jié)點返回一條RREP報文。由于車載路由具有低生存周期性，緩存了網(wǎng)關(guān)路由信息的中間節(jié)點將不發(fā)送RREP分組。如果發(fā)現(xiàn)多個網(wǎng)關(guān)，源節(jié)點選擇最小跳數(shù)的路由，大多數(shù)節(jié)點移動方向和源節(jié)點移動方向一致。如果發(fā)現(xiàn)相同方向的多條路由，那么就選擇具有最長預測生存周期的路由。一旦建立了到網(wǎng)關(guān)的路由，就開始通信。如果路由仍然保持活躍狀態(tài)，那么僅當在預測失效路由前，PBR才試圖建立一條到達網(wǎng)關(guān)的新路由。RREP分組用來預測路由的生存周期。當網(wǎng)關(guān)收到RREQ分組時，就向源節(jié)點發(fā)送一條包含其位置、速度信息和最大生存周期的RREP分組。每個中間節(jié)點處理RREP分組，并使用通信范圍，運動方位，節(jié)點速度以及節(jié)點間的距離來估計自己和前驅(qū)節(jié)點的連接時間。如果生存周期小于儲存在RREP分組中的生存周期值，那么就用更小的生存周期值來更新分組。當源節(jié)點收到RREP分組，它就可以估計路由的有效時間?；诘貓D的路由(Mapbased Routing，MBR)協(xié)議目前為止還沒有提出具體的協(xié)議來，然而從車載自組網(wǎng)的特點來看，應(yīng)用于車間通信的路由協(xié)議可以利用車輛的特性，例如配備車載GPS系統(tǒng)和電子地圖的車輛，不僅可以獲知自己的位置、鄰居節(jié)點和道路拓撲信息，還可以利用導航系統(tǒng)中具備的路徑規(guī)劃等功能。未來的車載自組網(wǎng)路由協(xié)議的發(fā)展方向是位置與電子地圖相結(jié)合的基于地圖路由協(xié)議。由節(jié)點集、道路集和轉(zhuǎn)彎限制集等幾個有限集合來描述和預知整個網(wǎng)絡(luò)的全局拓撲情況，這都對路由的建立提供了有力支持，更快、更準地計算出從源到目的節(jié)點的最佳路徑。本文深入研究和分析了車載環(huán)境下基于位置的路由協(xié)議和位置服務(wù)機制，找出移動Ad hoc網(wǎng)絡(luò)中位置服務(wù)機制用于車載Ad hoc網(wǎng)絡(luò)中存在的問題，并提出了相應(yīng)的位置服務(wù)機制。本文主要完成了以下工作：第一，通過閱讀國內(nèi)外相關(guān)文獻，闡述了車輛間通信研究的背景、意義和無線通信技術(shù)的發(fā)展狀況，分析了車輛間通信當前所面臨的挑戰(zhàn)和發(fā)展趨勢，綜述了國內(nèi)外已提出的適用于車載Ad hoc網(wǎng)絡(luò)的路由協(xié)議，并深入研究和分析了車載Ad hoc網(wǎng)絡(luò)中基于位置的路由協(xié)議以及位置服務(wù)機制。第二，使用網(wǎng)絡(luò)仿真工具NS2對基于拓撲結(jié)構(gòu)的路由協(xié)議AODV、DSR和基于位置的路由協(xié)議GPSR協(xié)議進行了仿真。通過對仿真實驗數(shù)據(jù)的分析和比較得出如下結(jié)論，在相同的網(wǎng)絡(luò)環(huán)境下，節(jié)點的移動速度對AODV和DSR的網(wǎng)絡(luò)性能影響較大，對基于位置的路由協(xié)議GPSR網(wǎng)絡(luò)性能影響較小，并且GPSR在分組丟包率、平均端到端時延和網(wǎng)絡(luò)吞吐量方面都是最優(yōu)的。第三，提出了一種新的適用于車載Ad hoc網(wǎng)絡(luò)的位置服務(wù)機制—道路交叉路口位置服務(wù)機制ILSV。ILSV充分利用了車載網(wǎng)絡(luò)環(huán)境的特點如存在十字路口，受交通規(guī)則約束等，將網(wǎng)絡(luò)中節(jié)點的位置信息分布地存儲在位于十字路口的位置服務(wù)器上。當位于十字路口的位置服務(wù)器離開十字路口時，將其所持有的車輛節(jié)點位置信息表廣播給該十字路口的其它位置服務(wù)器。各十字路口按照一定的算法選擇一個最優(yōu)節(jié)點定期發(fā)送位置信息組更新分組交換車輛節(jié)點位置信息表。第四，在網(wǎng)絡(luò)仿真平臺NS2下實現(xiàn)了位置服務(wù)ILSV，將其與基于位置的路由協(xié)議如無狀態(tài)路由協(xié)議GPSR進行整體融合，并進行了大量的仿真實驗。在大規(guī)模城市仿真場景下的仿真結(jié)果表明，與GLS和HLS相比，ILSV獲得較高的查詢成功率和較低的查詢時延，并且在網(wǎng)絡(luò)半徑很大的情況下具有較優(yōu)的可縮放性。第五，對交通仿真平臺SUMO進行了二次開發(fā)生成用于車載網(wǎng)絡(luò)仿真的城市場景文件。第一章 緒論。通過閱讀國內(nèi)外相關(guān)文獻，闡述了車輛間通信研究的背景、意義和無線通信技術(shù)的發(fā)展狀況，分析了車輛間通信當前所面臨的挑戰(zhàn)和發(fā)展趨勢，綜述了國內(nèi)外已提出的適用于車載Ad hoc網(wǎng)絡(luò)的路由協(xié)議。然后介紹了本文的研究目的、研究內(nèi)容和主要工作。最后簡要介紹了本文的研究內(nèi)容和章節(jié)安排。第二章 車載Ad hoc網(wǎng)絡(luò)架構(gòu)。主要對車載Ad hoc網(wǎng)的體系結(jié)構(gòu)、相關(guān)設(shè)計方法以及VANET的關(guān)鍵技術(shù)進行了論述，并給出了基于MANET的車載Ad hoc網(wǎng)絡(luò)架構(gòu)模式。第三章 基于位置的路由協(xié)議。首先簡要詳細了基于位置的路由協(xié)議相關(guān)工作，從理論和仿真實驗角度對基于拓撲結(jié)構(gòu)和基于位置的路由協(xié)議兩類路由協(xié)議進行性能分析比較。通過對仿真實驗數(shù)據(jù)的分析和比較得出如下結(jié)論，在相同的網(wǎng)絡(luò)仿真環(huán)境下，節(jié)點的移動速度對AODV和DSR的網(wǎng)絡(luò)性能影響較大，對基于位置的路由協(xié)議GPSR網(wǎng)絡(luò)性能影響較小，并且GPSR在分組丟包率、平均端到端時延和網(wǎng)絡(luò)吞吐量方面都是最優(yōu)的。第四章 一種新的適用于VANET的位置服務(wù)機制。首先闡述了當前幾種比較典型的MANET位