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

蔡震

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

關(guān)鍵詞：VANETs；GyTAR；道路連通性預(yù)測

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

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

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

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

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

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

當(dāng)發(fā)送到第一個區(qū)域中心范圍內(nèi)且離中心位置最近的車輛時，此車輛便把當(dāng)前其鄰居車輛的數(shù)量更新到CDP中，并繼續(xù)向后轉(zhuǎn)發(fā)數(shù)據(jù)包，同時把自己標(biāo)志為CDP車輛。

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

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

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

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

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

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

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

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

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

參考文獻：

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

[2] 雷亞星，李劍峰. 城市環(huán)境下VANET路由協(xié)議的研究[J].2011.

[3] 胡畔.城市環(huán)境下基于位置的車載自組網(wǎng)路由協(xié)議研究[D].武漢理工大學(xué)， 2014.

[4] 司桂芳.基于城市環(huán)境的車載自組織網(wǎng)絡(luò)路由協(xié)議研究[D].南京郵電大學(xué)， 2013.

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

[6] 金曉燁.基于城市環(huán)境的車載網(wǎng)絡(luò)路由機制研究[D].北京郵電大學(xué)，2013.

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