VANET城市場景下基于車流特征的路由算法

張 智，張 劍，聶 鈴，李陸君

（上海工程技術大學 航空運輸學院，上海 201620）

0 引 言

當前社會中，汽車成為人們出行必不可少的交通工具，同時也引起了諸多的社會問題［1］。汽車數(shù)量的增多、駕駛員行為方式的差異，造成交通擁擠，以及各類道路交通傷害等。為改善此類事件的發(fā)生，智能交通系統(tǒng)（Intelligent Transportation System，ITS）應運而生。車載自組織網(wǎng)絡（Vehicle Ad-hoc Network，VANET）是智能交通系統(tǒng)的一種高級運用，車聯(lián)網(wǎng)VANET是由搭載了無線通信裝置的車輛作為節(jié)點而構成的一種特殊形式的移動自組織網(wǎng)絡（Mobile Ad Hoc Network，MANET）［2］。

由于VANET中節(jié)點移動速度快，網(wǎng)絡拓撲變化快速，特別是在城市環(huán)境中，節(jié)點移動路線固定，受道路拓撲影響；節(jié)點數(shù)量多且速度受限；建筑物高大密集，影響無線傳輸?shù)男阅艿纫蛩赜绊懀芏嗦酚蓞f(xié)議并不適用于城市環(huán)境中車輛之間的通信。因此，研究適合于城市環(huán)境VANET的路由算法，是當前VANET技術的熱點問題［3］。

1 相關工作

路由協(xié)議大體上分為兩大類：基于拓撲的路由協(xié)議和基于位置的路由協(xié)議。前者需要考慮整個網(wǎng)絡拓撲的信息，后者僅依賴于部分位置信息。目前，許多研究人員均對VANET相關路由協(xié)議進行了研究。文獻［4-6］中指出，AODV是一種基于拓撲的路由協(xié)議，該協(xié)議主要實現(xiàn)路由發(fā)現(xiàn)和路由維護［4-6］功能。當源節(jié)點需要向目的節(jié)點發(fā)送數(shù)據(jù)包時，啟動路由發(fā)現(xiàn)過程，并定期發(fā)送HELLO包進行路由維護［7］。對于城市環(huán)境下復雜的路況信息，AODV協(xié)議并不適用。GPSR是一種基于地理位置的路由協(xié)議，主要實現(xiàn)貪婪轉發(fā)算法和周邊轉發(fā)算法［8］。GPSR基于平面圖遍歷，動態(tài)性高，易引發(fā)路由循環(huán)問題，適用于節(jié)點分布均勻、場景開闊的空間，不適用于城市環(huán)境的VANET［9］。Hassan等人提出了一種針對城市環(huán)境的多度量地理路由（MGEDIR）。采用動態(tài)轉發(fā)技術，以接收信號強度、傳輸范圍邊界關鍵區(qū)域、車輛未來位置等指標來選擇下一跳車輛（NHV），在選擇NHV時考慮了最大的權衡因素［10］。Abbasi等人提出了一種可靠路徑選擇和分組轉發(fā)路由協(xié)議（RPSPF）的路由方案，采用基于錨的路由方法進行分組路由。RPSPF動態(tài)地選擇兩個直接交叉點來求解路徑靈敏度，通過短曲線距離指標選擇下一跳車輛［11］。

綜上所述，研究人員提出了不同的適用VANET路由算法，但這些路由算法在一定程度上易產(chǎn)生傳輸開銷和時延問題。為此，本文提出了一種基于車流特征的路由算法（TCR）。該算法利用車流特征等資源，設計了符合城市交通環(huán)境VANET的路由算法，保障車間通信的高效穩(wěn)定傳輸，提高道路上的交通效率和車輛行駛的安全性。

2 系統(tǒng)模型和約束條件

2.1 系統(tǒng)模型

本文對VANET網(wǎng)絡在城市環(huán)境下性能的研究，主要考慮城市場景中典型的道路模型，由十字路口和直路段道路建立而成。圖1所示為SUMO仿真軟件建立的城市道路模型圖。

圖1 城市道路模型圖Fig.1 Urban road model diagram

其中，Ii表示第i個十字路口，Si，j表示直路段，每個路段均有自己的屬性，包括長度、車道數(shù)、車流密度等。

2.2 約束條件

隨著計算機和車聯(lián)網(wǎng)技術的發(fā)展，車輛會成為可具備高計算處理能力的設備，本文提出的TCR路由算法的實施基于以下的前提和假設：

（1）以VANETs的城市場景為研究對象。

（2）每輛車預裝數(shù)字地圖和全球定位系統(tǒng)GPS，包括街道地圖和交通統(tǒng)計數(shù)據(jù)。

（3）每輛車均配備車載單元OBU，每個車輛具有至少300米的可訪問通信范圍，可通過信標交換獲取實時信息。包括車輛ID、速度、當前位置及所在道路位置。

（4）道路交叉路口配備路測單元RSU，RSU根據(jù)相鄰的兩個道路獲取實時信息，包括當前道路ID、長度、車輛數(shù)及車輛密度。

（5）車輛擁有協(xié)作感知消息（CAM）：節(jié)點會按照ETSI標準中指定的方式發(fā)送CAMs；包括狀態(tài)矢量信息，如物理位置、目的地、當前速度和方向。信息包報頭包括源節(jié)點ID、源節(jié)點位置、信息包生成時間、過期時間。

（6）將城市VANET抽象為G=｛V，E｝，V表示車輛，E表示通信鏈路。

3 TCR路由算法

3.1 最優(yōu)路段選擇

3.1.1 連通度計算

首先，定義輔助節(jié)點AN：每個道路段最外層的兩個節(jié)點，如圖1所示。AN節(jié)點將會幫助節(jié)點之間進行車輛密度信息交換和連接度值的估計。車輛周期性地廣播beacon消息，并與附近的車輛節(jié)點和路測單元RSU進行信息交換。隨著傳輸范圍的擴大，HELLO包消息定期更新相關的鄰居表，進行鄰居表的維護。所以車輛節(jié)點在進入到一個路段后，車輛會意識到自己的位置，判斷自身是否為AN節(jié)點，獲取該路段上的ID以及車輛密度，路段Si，j上的車輛密度ρi，j。計算公式如式（1）所示。

其中，Si，j表示十字路口Ii和十字路口Ij之間的路段；Ni，j表示路段Si，j上的車輛總數(shù)；Li，j表示路段Si，j的長度；n表示車道數(shù)。

AN節(jié)點收集RSU和其它候選節(jié)點的相關信息。其中包括路段ID、傳輸時間、傳輸范圍、路段上車輛密度等，并將這些信息傳送給附近可以傳輸?shù)腁N節(jié)點。AN節(jié)點根據(jù)收集到的相關信息選擇合適的路段。

一個路段可由兩個端點的元組表示［12］。一個道路的兩端路口可表示為（S，dS）和（S，dd），而網(wǎng)格區(qū)域內(nèi)各線段的結節(jié)點坐標可表示為：

3.1.2 車流分布偏差的計算

為進一步反映車流量，定義車輛的相對位置變量。對于車輛Vehm，其在路段Si，j上的相對位置為如式（3）所示。

偏差γij越小，表示車流分布越均勻。

為選出最優(yōu)的路段進行數(shù)據(jù)包轉發(fā)，通過預估的連通度和車流分布的偏差兩個參數(shù)，構成評價函數(shù)F，如式（7）所示。

其中α、β是權重因子，且α+β=1，α＞0、β＞0，具體參數(shù)值需要結合仿真調(diào)試獲得。通過預估連通度，計算有效節(jié)點間的連接性，盡可能地保證候選車輛在傳輸范圍內(nèi)；通過車流分布均勻性的計算，也保證了候選車輛的充分性。

評價函數(shù)F不僅考慮了源節(jié)點到目的車輛節(jié)點之間所有候選路徑的質(zhì)量，還考慮了源節(jié)點到目的車輛節(jié)點之間的跨路徑的分段連接。由式（7）可知，當連通度和車流分布都達到最好參數(shù)值時，評價函數(shù)F就會取得最大值，此時，所選的路段就是數(shù)據(jù)包轉發(fā)的最優(yōu)路段。

3.2 道路段內(nèi)數(shù)據(jù)包的轉發(fā)

道路段內(nèi)數(shù)據(jù)包轉發(fā)采用改進的貪婪轉發(fā)算法，與傳統(tǒng)的貪婪轉發(fā)算法比較存在3個方面的優(yōu)化：增加了鏈路狀態(tài)因子L、方向因子F、距離因子D，避免傳輸跳數(shù)和路由中斷次數(shù)的增加，進而減少端到端的時延，保證鏈路的穩(wěn)定性。

3.2.1 鏈路狀態(tài)因子L

城市VANET拓撲結構變化快速，大多是由車輛的速度和運行方向變化引起的，這些因素將影響鏈路的穩(wěn)定性。本文利用車輛節(jié)點之間的相對位移量來計算鏈路狀態(tài)，節(jié)點之間進行周期性地廣播信標消息，節(jié)點之間的距離通過式（8）即可獲得。

其中，R為常量，表示通信傳輸半徑，di（t）表示t時刻發(fā)送節(jié)點與一跳范圍內(nèi)鄰居節(jié)點的距離。通過式（9）可知，節(jié)點之間相對位移量變化越小，則鏈路越穩(wěn)定。同時，鏈路的維持時間也是鏈路可靠性的關鍵因素。本文通過節(jié)點之間發(fā)送的beacon數(shù)據(jù)包，計算鏈路的維持時間ti，如式（10）所示。

其中，vi表示鄰居節(jié)點的速度，vs表示發(fā)送數(shù)據(jù)包的節(jié)點速度。

為更準確地表示鏈路的維持時間ti，本文將其進行歸一化處理，如式（12）所示。

其中，Tmax表示最大持續(xù)時間。

根據(jù)上述度量指標，可得出鏈路狀態(tài)因子L，如式（13）所示。

3.2.2 方向因子F

本文算法定義車輛運行方向與數(shù)據(jù)分組的傳輸方向一致時，數(shù)據(jù)包標志位Flag標識為+1，反之，則標識為-1。如式（14）所示。相同方向的節(jié)點給予同樣的優(yōu)先權，同時對車輛行駛方向與數(shù)據(jù)分組傳輸方向相同的車輛節(jié)點給予更高的優(yōu)先權，這些車輛節(jié)點優(yōu)先作為候選的下一跳節(jié)點。

3.2.3 距離因子D

除上述鏈路狀態(tài)、車輛的行駛方向和數(shù)據(jù)分組的傳輸方向以外，本文算法還增加了車輛之間距離因子度量指標，如式（15）所示。在具有相同方向優(yōu)先級的情況下，優(yōu)先選擇距離目的節(jié)點最近的鄰居節(jié)點。

式中，(xD，yD)表示目的節(jié)點坐標；(xi，yi）表示一跳傳輸范圍內(nèi)的鄰居節(jié)點坐標；n表示具有相同優(yōu)先級節(jié)點的個數(shù)。應避免因城市VANET的高度動態(tài)性，造成邊緣節(jié)點下一跳移出通信范圍，從而引起鏈路中斷，造成數(shù)據(jù)包的丟失或重發(fā)。

3.2.4 轉發(fā)節(jié)點的選擇

在道路段內(nèi)進行數(shù)據(jù)包的轉發(fā)，本文結合鏈路狀態(tài)、方向因子、距離因子3個方面因素，權衡選取下一跳轉發(fā)節(jié)點，不僅保證了鏈路的穩(wěn)定性，同時也在傳輸方向優(yōu)先級相同的情況下，優(yōu)先選取距離目的節(jié)點更近的鄰居節(jié)點作為下一跳的轉發(fā)數(shù)據(jù)包節(jié)點。轉發(fā)節(jié)點的選擇如式（16）所示。

其中，L指發(fā)送節(jié)點s與鄰居節(jié)點i之間的鏈路狀態(tài)；F是節(jié)點的運行方向與數(shù)據(jù)包傳輸方向的一致性判定；D是鄰居節(jié)點與目的節(jié)點的最小距離判定；di指發(fā)送節(jié)點與鄰居節(jié)點之間的距離。由于本文只計算一跳范圍內(nèi)的鄰居節(jié)點，則di還包括一跳范圍內(nèi)的鄰居節(jié)點與發(fā)送節(jié)點之間的距離，其中權重系數(shù)ω1=ω2=ω3=0.33。

當Ra nk＞0時，根據(jù)式（16）選擇下一跳轉發(fā)節(jié)點；當Rank=0時，說明形成了局部最優(yōu)問題。此時只需發(fā)送節(jié)點攜帶數(shù)據(jù)包，繼續(xù)等待下一個合適的轉發(fā)節(jié)點進行轉發(fā)即可。等待時間T設定一個閾值ε，當T＞ε時，發(fā)送節(jié)點結束等待，放棄相應的數(shù)據(jù)包，源節(jié)點進行重發(fā)。

4 性能分析

為了更好地評估TCR算法的性能，對TCR算法進行仿真試驗，并與AODV、GPSR兩個協(xié)議進行對比。仿真主要是從數(shù)據(jù)傳輸成功率、平均端到端時延兩個方面進行性能的比較和分析。

4.1 仿真模型

本文利用SUMO和NS軟件建立仿真平臺，從OpenStreetMap官網(wǎng)上選擇上海松江大學城區(qū)域圖作為仿真地圖，如圖2所示。圖3為SUMO軟件可打開的對應場景拓撲圖。在SUMO中編寫車輛移動模型，利用NS2腳本調(diào)用SUMO中相關文件，并進行相應的參數(shù)和流量配置。經(jīng)過仿真實驗的不斷調(diào)試，對于最優(yōu)路段評價函數(shù)性能較佳時的權重參數(shù)選定為α=0.75，β=0.25，其它仿真參數(shù)詳見表1。

表1 仿真參數(shù)Tab.1 Simulation parameters

圖2 松江大學城區(qū)域圖Fig.2 Regional map of Songjiang University Town

圖3 松江大學城拓撲圖Fig.3 Topology of Songjiang University Town

4.2 仿真結果與分析

4.2.1 數(shù)據(jù)傳輸成功率

數(shù)據(jù)傳輸成功率，是指網(wǎng)絡中目的節(jié)點接收到的數(shù)據(jù)分組總數(shù)與源節(jié)點發(fā)送的數(shù)據(jù)分組總數(shù)之比，反映的是數(shù)據(jù)傳輸?shù)目煽啃浴?/p>

圖4反映了3種協(xié)議下數(shù)據(jù)傳輸成功率與車輛數(shù)的變化曲線關系。本研究設置車輛數(shù)為50、100、150、200、250、300。由圖可見，當車輛速度固定時，隨著車輛數(shù)的遞增，車輛節(jié)點之間鏈路數(shù)增多，傳輸成功率也隨之增加。3種協(xié)議中傳輸成功率最低的為AODV協(xié)議，其次為GPSR協(xié)議，本文提出的TCR協(xié)議的傳輸成功率明顯高于AODV與GPSR協(xié)議。由于AODV與GPSR協(xié)議都未考慮車流特征相關因素，而TCR協(xié)議結合車輛密度與車流分布情況，計算每個路段的連通度，選擇源節(jié)點與目的節(jié)點之間鏈路質(zhì)量最優(yōu)的路徑，不僅提升了數(shù)據(jù)包到達目的節(jié)點的概率，同時也提高了數(shù)據(jù)包的傳輸成功率。

圖4 數(shù)據(jù)傳輸成功率與車輛數(shù)關系圖Fig.4 Relationship between data transmission success rate and number of vehicles

圖5反映了3種協(xié)議下數(shù)據(jù)傳輸成功率與車輛速度之間的變化曲線關系。本研究設置車輛速度為10、20、30、40、50 km／h。由圖可見，當車輛節(jié)點固定時，3種協(xié)議的傳輸成功率都受車輛速度因素影響，隨著車輛速度的增加，數(shù)據(jù)傳輸成功率都有不同程度的下降，當車輛速度增加時，網(wǎng)絡拓撲結構變化大，車輛節(jié)點之間鏈路持續(xù)時間減少，鏈路穩(wěn)定性變差，易發(fā)生斷裂，數(shù)據(jù)包丟失概率增加，所以數(shù)據(jù)傳輸成功率相應下降。由于AODV協(xié)議是基于拓撲的路由協(xié)議，GPSR協(xié)議考慮因素單一，都不適合VANET。TCR協(xié)議權衡密度信息與全局搜索，選擇最佳路段，實時性較低，因此TCR協(xié)議數(shù)據(jù)傳輸成功率始終高于AODV與GPSR協(xié)議，且變化趨于平緩。

圖5 數(shù)據(jù)傳輸成功率與車輛速度關系圖Fig.5 Relationship between data transmission success rate and vehicle speed

4.2.2 端到端平均時延

平均端到端時延是指數(shù)據(jù)分組，從源節(jié)點到目的節(jié)點的平均發(fā)送時間，反映的是數(shù)據(jù)傳輸?shù)挠行浴?/p>

平均端到端時延與車輛數(shù)變化曲線關系如圖6所示。本研究設置車輛數(shù)為50、100、150、200、250、300。由此可見，當車輛速度固定時，隨著車輛數(shù)的增加，3種路由協(xié)議的平均端到端時延都有明顯的下降，TCR協(xié)議進行路段選擇時，計算各個路段以及跨路段的連通性，相比于AODV與GPSR協(xié)議，平均端到端延遲最少，且隨著車輛數(shù)的不斷增加，TCR的平均端到端延遲下降變化趨勢愈加平緩。

圖6 平均端到端時延與車輛數(shù)關系圖Fig.6 Relationship between average end-to-end delay and number of vehicles

圖7給出了平均端到端時延與車輛速度之間的變化曲線關系。本研究設置車輛速度為10、20、30、40、50 km／h。由圖中可知，當車輛節(jié)點固定時，車輛速度變大時，3種協(xié)議的時延都在增加。在車輛速度不斷增加的過程中，車輛節(jié)點位置快速發(fā)生變化，網(wǎng)絡拓撲結構快速改變，網(wǎng)絡中車輛節(jié)點之間的連通性不斷降低，在數(shù)據(jù)包轉發(fā)的過程中，車輛節(jié)點一跳范圍內(nèi)可選的下一個轉發(fā)節(jié)點概率在減少，數(shù)據(jù)包傳輸?shù)侥康墓?jié)點的時間就會增加，相應的平均端到端時延增加。TCR協(xié)議與AODV、GPSR協(xié)議相比，在保證鏈路可靠性的基礎上，增加了鏈路因子、方向因子、距離因子3方面因素的考慮，減少了平均端到端時延。

圖7 平均端到端時延與車輛速度關系圖Fig.7 Relationship between average end-to-end delay and vehicle speed

5 結束語

針對城市場景VANET的網(wǎng)絡特性，提出了基于車流特征的路由算法TCR，通過預估實時車輛密度信息和路段連通度，進行最優(yōu)路段選擇外，對道路段內(nèi)數(shù)據(jù)轉發(fā)進行了優(yōu)化改進。仿真表明，TCR算法在數(shù)據(jù)傳輸成功率和平均端到端時延方面都要優(yōu)于AODV、GPSR協(xié)議，能夠更好的滿足城市場景下VANET的通信需求。