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

2021-05-04 11:10:40李陸君

智能計算機與應用 2021年11期

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

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

0 引言

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

由于VANET中節點移動速度快，網絡拓撲變化快速，特別是在城市環境中，節點移動路線固定，受道路拓撲影響；節點數量多且速度受限；建筑物高大密集，影響無線傳輸的性能等因素影響，很多路由協議并不適用于城市環境中車輛之間的通信。因此，研究適合于城市環境VANET的路由算法，是當前VANET技術的熱點問題［3］。

1 相關工作

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

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

2 系統模型和約束條件

2.1 系統模型

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

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

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

2.2 約束條件

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

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

（2）每輛車預裝數字地圖和全球定位系統GPS，包括街道地圖和交通統計數據。

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

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

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

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

3 TCR路由算法

3.1 最優路段選擇

3.1.1 連通度計算

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

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

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

一個路段可由兩個端點的元組表示［12］。一個道路的兩端路口可表示為（S，dS）和（S，dd），而網格區域內各線段的結節點坐標可表示為：

3.1.2 車流分布偏差的計算

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

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

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

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

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

3.2 道路段內數據包的轉發

道路段內數據包轉發采用改進的貪婪轉發算法，與傳統的貪婪轉發算法比較存在3個方面的優化：增加了鏈路狀態因子L、方向因子F、距離因子D，避免傳輸跳數和路由中斷次數的增加，進而減少端到端的時延，保證鏈路的穩定性。

3.2.1 鏈路狀態因子L

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

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

其中，vi表示鄰居節點的速度，vs表示發送數據包的節點速度。

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

其中，Tmax表示最大持續時間。

根據上述度量指標，可得出鏈路狀態因子L，如式（13）所示。

3.2.2 方向因子F

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

3.2.3 距離因子D

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

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

3.2.4 轉發節點的選擇

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

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

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

4 性能分析

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

4.1 仿真模型

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

表1 仿真參數Tab.1 Simulation parameters

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

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

4.2 仿真結果與分析

4.2.1 數據傳輸成功率

數據傳輸成功率，是指網絡中目的節點接收到的數據分組總數與源節點發送的數據分組總數之比，反映的是數據傳輸的可靠性。

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

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

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

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

4.2.2 端到端平均時延

平均端到端時延是指數據分組，從源節點到目的節點的平均發送時間，反映的是數據傳輸的有效性。

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

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

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