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

蔡震

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)：

[1] 邢世寶.基于道路時(shí)延和車流量的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ò)路由機(jī)制研究[D].北京郵電大學(xué)，2013.

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