一種基于GyTAR道路連通性預測模型的改進算法

蔡震

摘 要：基于路口的VANETs路由協議GyTAR，其道路連通性預測模型方法設計新穎，但在CDP發送車輛的選取上存在一定缺陷，導致預測結果在實時性和準確性上效果不佳。針對此缺陷，本文進行了改進，在車輛進入道路后按照其先后時間選取CDP車輛，得以有效的控制CDP之間的發送時間間隔，提升了連通性模型的準確性和實時性，并通過仿真實驗驗證其效果。

關鍵詞：VANETs；GyTAR；道路連通性預測

1）基于路口的VANETs路由形式能很好地適應城市環境[ 1-6 ]。這些路由協議均由處于路口車輛來進行路由決策，路由道路選擇的判定因素有如下兩點：

a.下一路口距離目的節點的距離，沿更短距離的道路傳送數據包將會有效減少連接斷開的幾率；

b.待選道路上多跳鏈接的連通性預測或延遲時間預測，即道路上是否有足夠多的繼車輛節點使數據包在最短時間內成功傳送到下一路口。

GyTAR[ 7 ]采用了一種比較新穎的連通性預測方法，在準確性和實時性上均表現不錯，但其也存在一定的缺陷，本文將針對這些缺陷，提出一個新的改進算法。

2）GyTAR（Improved Greedy Traffic Aware Routing）中，在道路上行駛的車輛將自身的地理坐標位置通過信息交換，實時維護周圍鄰居車輛節點列表，其中鄰居車輛的位置、行駛速度、行駛方向。路口節點通過其收集到的信息，會為每條道路通往的下一個路口計算出分數，公式如下：

此公式考慮了道路長度、每個區域的車輛數以及各個區域車輛數量分布是否均勻。公式的關鍵是如何有效獲得每個區域的實時車輛數Ni，GyTAR的方法如下：按照車輛信號傳輸距離（通常VANETs為250m）每條道路被分為若干區域，處于每個區域中心范圍（GyTAR模擬實驗采用的是半徑40m的圓）內且離中心位置最近的為未來發送CDP的車輛（以下簡稱CDP車輛），當每輛CDP車輛離到達下一路口時，便向后方發送一個CDP，其中包含道路ID、發包時間和此道路的區域列表（區域名稱、區域中心位置、區域內車輛數）。

當發送到第一個區域中心范圍內且離中心位置最近的車輛時，此車輛便把當前其鄰居車輛的數量更新到CDP中，并繼續向后轉發數據包，同時把自己標志為CDP車輛。

換言之，只有更新過CDP的車輛在離開當前道路時，才會生成一個新的CDP向后發送。以此類推，當CDP傳送至上一路口時，路口車輛節點便得到了整條道路上每個區域的車輛數量，然后可以按照以上模型公式，結合道路長度，進行分數計算。當有數據包到達此路口時，便可以以此分數來判斷最佳的路由線路。

3）GyTAR應用從備選路口發回到當前路口的CDP控制信息獲取道路車輛數，以此建立連通性模型，相較于從第三方獲取以往某時段的平均車流量來說，更具有數據的實時性和可靠性。但其本身也存在的一些缺陷，如圖1。

當CDP傳送至C2區域時，處于中心位置的V-A更新本區域的車輛數到CDP，然后把自己標志為CDP車輛，當其向右繼續行駛并駛離道路時，便會生成一個新的CDP數據包向后傳送，這是一個標準的程序過程；但當CDP傳送至C1區域時，車輛V-B把本區域的車輛數更新到CDP，但由于自身行駛方向并不是備選路口方向，所以其無法標志自己為CDP車輛，致使最終CDP發送時間間隔偏差較大，對用于車輛密度信息的實時性造成影響。

針對此問題，本文進行了改進：處于每個區域中心范圍的車輛只負責更新CDP，不再標志自己為CDP車輛，我們規定在車輛進入一條道路后，通過“hello”信息查看處于道路前方的鄰居車輛有無CDP車輛，如果沒有則標記自己為CDP車輛，當其到達下個路口時，向后發送CDP進行更新；同時對于路口節點的道路車輛密度信息設置有效時間。

TTL=（信號傳輸距離 / 道路上車輛平均速度） * α

其中α為可調參數，當TTL過期后，信息將不被采用。改進后，雖然可能會增加一定的CDP數量（按照250m的信號傳輸距離計算，CDP增加最大值為原來的1倍），但可以有效控制每個CDP之間的發送時間間隔，從而提升連通性模型的準確性和實時性，下章中模擬實驗數據可以顯示其優越性。

4）本文采用SUMO（Simulation of Urban MObility）設計了兩條同樣的8車道雙向城市道路，假定為道路路由候選，并使用原GyTAR和本文的改進算法進行道路連通性預測計算，根據各自的道路連通性得分選擇其中之一，并通過MATLAB仿真得出該道路實時數據包的傳輸延遲時間，觀察其路由選擇的對比效果，模擬環境參數如表1。

如圖2所示，其中最佳結果為每次皆選取實際延遲時間小的道路而得出的平均延遲時間，最差結果則為相反情況。圖中可看出，因為改進算法在CDP發送的時間間隔上相對比較穩定，且道路車輛信息保存時間固定，不會出現過期數據的情況，所以道路延遲時間預測的實時性和準確性較原GyTAR有明顯提高，實際數據包延遲時間明顯減少。

5）總結：本文分析了基于路口的VANETs路由協議GyTAR的工作機制，指出了其因CDP發送車輛選取不均勻而容易導致的道路連通性預測實時性和準確性不高的缺陷，針對此問題進行了改進，并且通過模擬實驗證明此改進算法在道路連通性預測的準確度較原GyTAR有了明顯提高。

參考文獻：

[1] 邢世寶.基于道路時延和車流量的VANET路由協議研究[D].吉林大學，2015.

[2] 雷亞星，李劍峰. 城市環境下VANET路由協議的研究[J].2011.

[3] 胡畔.城市環境下基于位置的車載自組網路由協議研究[D].武漢理工大學， 2014.

[4] 司桂芳.基于城市環境的車載自組織網絡路由協議研究[D].南京郵電大學， 2013.

[5] 柳長青.城市VANET路由協議研究[D].天津大學，2012.

[6] 金曉燁.基于城市環境的車載網絡路由機制研究[D].北京郵電大學，2013.

[7] M.Jerbi et al.“An Improved Vehicular Ad Hoc Routing Protocol for City Environments，”IEEE ICC07，pp.3972-79.