基于大數(shù)據(jù)的VANET擁塞檢測研究

李佩君，侯大有，趙正平，肖卓磊，史曉鳳，劉淑影

（阜陽師范大學(xué) 計算機(jī)與信息工程學(xué)院，安徽 阜陽 236037）

車聯(lián)網(wǎng)（vehicular Ad hoc networks，VANETs）從 MANET(mobile Ad-hoc networks)中派生出來。二者有相同的基礎(chǔ)和不同的特點。例如，MANET網(wǎng)絡(luò)中節(jié)點的移動仍是隨機(jī)的，而VANET網(wǎng)絡(luò)是根據(jù)先前設(shè)計的移動模型組織的[1]。其次MANET中節(jié)點的速度相對于VANET有所降低。這會影響網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，使其不斷變化。因此，對變化拓?fù)涞墓芾砑仁且粋€需要解決的問題，也是車載網(wǎng)的特點。VANET中的通信分為兩類：車輛對車輛（vehicular to vehicular，V2V）車輛對路邊單位（road side unit，RSU）[2]。每次車輛的重新組合，就形成一個VANET網(wǎng)絡(luò)。其中車輛被視為路由器或范圍在100～300 m的無線節(jié)點，超出范圍的車輛斷開網(wǎng)絡(luò)連接[3]。

VANET中交通容量和流量是造成交通擁塞的主因。對于這些數(shù)據(jù)的利用有利于交通同步流、安全保障和解決以后的問題[3]。尤其對于大城市的超大車載網(wǎng)，這些數(shù)據(jù)量是巨大的，并沒有被100%利用。由于這些非結(jié)構(gòu)化數(shù)據(jù)的數(shù)量和復(fù)雜性都呈指數(shù)性增長，因此不能由傳統(tǒng)的數(shù)據(jù)庫管理，需要設(shè)計強(qiáng)大的處理工具。而Hadoop[4]是大規(guī)模分布式的數(shù)據(jù)處理平臺，可實現(xiàn)高密度存檔的分布式面向?qū)ο缶幊?。它可把元?shù)據(jù)處理和分析成兩種形式：結(jié)構(gòu)化元數(shù)據(jù)和復(fù)雜的非結(jié)構(gòu)化元數(shù)據(jù)。

借助Hadoop的特點，首先解決數(shù)據(jù)的結(jié)構(gòu)化問題，再分析數(shù)據(jù)，以檢測道路上的交通擁塞。將道路狀態(tài)生成時間函數(shù)，再通過儀表板顯示出來為以后的解決方案提供依據(jù)，最終形成存儲該地區(qū)所有道路準(zhǔn)確路況的擁塞檢測系統(tǒng)。本文利用SUMO(simulation of urban mobility)建立城市流動模型，再整合到NS-2中，利用Hadoop提取分析跟蹤文件，就可檢測道路上的擁塞間隔和高峰期。

1 相關(guān)工作

關(guān)于道路擁塞的問題，一些研究人員已經(jīng)提出了解決辦法。文獻(xiàn)[5]提出了一種結(jié)合了V2V和V2I兩種通信方式的道路擁塞檢測系統(tǒng)。系統(tǒng)采用Cassandra算法改進(jìn)的，使用歐姆網(wǎng)絡(luò)和SUMO模擬器進(jìn)行測試和驗證，通過處理和分析存儲的數(shù)據(jù)，以便識別交通堵塞并為后行車輛指示可變更的路線。文獻(xiàn)[6]將城市地區(qū)分為兩類：擁擠的和無障礙的。車輛可以根據(jù)其行程區(qū)分不同的區(qū)域，并自動轉(zhuǎn)向無障礙區(qū)域。由丹尼爾等人設(shè)計的模型[7]旨在利用算法來實時高效分析給定道路上的車輛密度。文獻(xiàn)[8]針對自動駕駛車輛提出了使用大數(shù)據(jù)挖掘技術(shù)選擇安全車道的方法。其中，人為干預(yù)只涉及在車輛開始上路時的駕駛偏好。文獻(xiàn)[9-10]結(jié)合了基于分類的信息融合模糊和D.S證據(jù)推理，提出了VANET網(wǎng)絡(luò)中基于多層信息融合的道路擁塞檢測方法。其中基于分類的信息融合模糊從D.S證據(jù)推理機(jī)制中繪制出主要特征來檢測交通擁塞情況，優(yōu)點在于節(jié)省帶寬。譚國平等人提出一種基于車輛到車輛通信的簡化合作擁塞檢測機(jī)制[11-13]，進(jìn)而降低車輛擁塞概率。文獻(xiàn)[14-16]提出了一種基于網(wǎng)絡(luò)效用最大化理論的分布式擁塞控制策略，在控制信道擁塞的同時，又減小了傳輸時延。文獻(xiàn)[17-18]針對基于固定監(jiān)測設(shè)備的高速公路擁堵檢測方法在檢測時間和檢測范圍的不足，提出了基于浮動車數(shù)據(jù)的檢測方法。

綜上所述，本研究利用大數(shù)據(jù)工具處理海量數(shù)據(jù)，快速生成道路歷史曲線并顯示目前交通狀態(tài)，以定位到最擁擠路段和高峰時期，有效避免車輛陷入擁塞之中。

2 道路交通擁塞檢測方法

正如前面提到的，VANET網(wǎng)絡(luò)生成的非結(jié)構(gòu)化信息沒被有效利用，有必要使用強(qiáng)大的工具來分析和處理，以解決包括擁塞在內(nèi)的幾個問題[19]。路線由起點和終點坐標(biāo)標(biāo)識，車輛由時標(biāo)和坐標(biāo)共同定位。例如某車輛t時刻在某道路上通行。環(huán)境視為變量，道路視為常量。其中，擁塞間隔和高峰時刻是判斷道路是否擁塞的關(guān)鍵。因此，在Hadoop環(huán)境中設(shè)置車輛穿過道路的檢測場景如圖1(a)，車輛位置隨時間的變化如圖1(b)。

圖1 道路交通狀態(tài)圖。(a)道路交通示意圖；（b）交通網(wǎng)絡(luò)變化圖

因此，該區(qū)域的狀態(tài)可看成是道路網(wǎng)絡(luò)的瞬時快照序列。車輛有四個基本要素：車輛標(biāo)識符（V1L），維度（X），經(jīng)度（Y）和時標(biāo)（t）。假設(shè)道路有兩個車道，一個用于出站，另一個用于返回。路線的基本要素有：路線標(biāo)識符（RID），車道1（X1,Y1）和車道 2（X2,Y2）。

本文提出的方法基于大量歷史數(shù)據(jù)的重組和分析，其檢測可能出現(xiàn)擁塞的步驟如圖2。首先，對環(huán)境進(jìn)行初始化，包括道路的坐標(biāo)、網(wǎng)絡(luò)大小、車輛數(shù)量和時標(biāo)等。其次，將空間和時間的軌跡分組，把車輛定義為該區(qū)域上時間的函數(shù)。這樣根據(jù)時間檢測擁塞，提取有關(guān)擁塞時間和地點的準(zhǔn)確信息。算法1根據(jù)已知通過市區(qū)的每條路線的車輛數(shù)量推斷出最擁擠的道路。算法3可識別每條路線的峰值時間間隔。算法4則給出了識別峰值時間的可能性。

圖2 道路擁塞檢測策略

算法1：車輛數(shù)量1:V←0.2 2:V n←0 3:f o r E a c h r o a d V ID∈V d o 4:i f V ID∈R ID t h e n 5: V n←V n+V ID 6:e n d i f 7:e n d f o r

算法2：擁塞檢測1：C r←C 2:R r←0 3:f o r E a c h r o a d i∈R r d o 4:i f Δ V n i n Δ R i＞T h r e s h o l d t h e n 5: C r←C r+R 1 6:e n d i f 7:e n d f o r

算法3：高峰時間間隔1：V←0 2：V n←0 3：I N T V A L S←0 4：f o r E a c h r o a d Δ V ID∈V d o 5：i f V ID i s i n R o a d X i n I N T V A L X t h e n 6： V n←V n+V ID 7：e n d i f 8：e n d f o r 9：i f n u m b e r o f v e h i c l e i n V n i n R o a d X＞T h r e s h o l d t h e n 1 0： I N T V A L S←I N T V A L S+I N T V A L X 1 1：e n d i f

算法4：實時峰值時間1：V←0 2：V n←0 3：I N S A N T S ←0 4：f o r E a c h r o a d V ID∈V d o 5：i f V ID i s i n R o a d X a t I N T V A L t t h e n 6： V n←V n+V IL 7：e n d i f 8：e n d f o r 9：i f n u m b e r o f v e h i c l e s i n V n i n R o a d X＞T h r e s h o l d t h e n 1 0： I N S T A N T S←I N S T A N T S+I N S T A N T X 1 1：e n d i f

其中：V是車輛總數(shù)：Vn是道路n上的車輛數(shù)量；Cr是擁塞道路的集合；RΔ是所有道路的集合。給定路線的門限Q通過等式Q=K*U計算，K是路線容量，U是流動的速度。這里假設(shè)路線的容量是相同的，速度定義為場景參數(shù)。

3 仿真與結(jié)果

為了評估和驗證本文提出的方法，采用SUMO微觀交通模擬器來生成一個城市的移動模型[20]。然后，用NS-2模擬器整個該模型，最后，分析記錄所有事件的跟蹤文件。每輛車定義自己達(dá)到目的地的路線。還要定義很多和網(wǎng)絡(luò)接入點、車輛入口點、交叉口、交通信號燈和環(huán)島等，這些因素為提出的方法提供了可信度。SUMO生成的道路交通的移動模型如圖3所示。

將生成的模型與NS-2模擬器集成，以獲取包含該場景的記錄和實踐的跟蹤文件。再使用Hadoop工具處理這些文件。本文處理三個具有相同移動模型的場景，分別是40輛車，80輛車和160輛車。圖4顯示了模擬期內(nèi)每個場景的道路狀態(tài)。由此可以很容易地區(qū)分出經(jīng)歷了更多交通量的道路，但無法確定這些道路何時會有更多的交通量。所以這些統(tǒng)計數(shù)據(jù)仍然很籠統(tǒng)，需要更多關(guān)于給定路線的細(xì)節(jié)。仿真的主要參數(shù)如表1。

圖3 道路拓?fù)鋱D

表1 仿真參數(shù)

圖4 三種場景下道路狀態(tài)

圖5把道路R23在整個模擬過程中的活動看作關(guān)于時間的函數(shù)。曲線顯示了道路上車輛的實時數(shù)量。曲線上的擁塞間隔有利于確定準(zhǔn)確地?fù)砣麜r間。為了得知每條道路的狀態(tài)，可以生成每條道路的歷史曲線。再通過創(chuàng)建儀表板來分析當(dāng)前狀態(tài)，為將來可能的道路擁塞提供解決方案。本文提出的方法是基于大數(shù)據(jù)工具提供的數(shù)據(jù)特征，以處理車載網(wǎng)絡(luò)在通信期間產(chǎn)生的海量數(shù)據(jù)。通過分析這種類型的網(wǎng)絡(luò)可看出來這些工具的功能強(qiáng)大。與大城市的真實環(huán)境相比，該仿真只是一個小樣本。總而言之，城市會產(chǎn)生大量的原數(shù)據(jù)，傳統(tǒng)的處理方法已凸顯出局限性。

圖5 路線R23的交通細(xì)節(jié)

4 小結(jié)

如今，大數(shù)據(jù)工具的應(yīng)用越來越廣泛，其作用也日益凸顯。傳統(tǒng)工具是無法管理和處理VANET的案例中大規(guī)模原數(shù)據(jù)。本研究認(rèn)為車輛產(chǎn)生的實時數(shù)據(jù)對于解決如交通擁塞一類的問題非常有用，提出了一種基于大數(shù)據(jù)工具處理車輛數(shù)據(jù)的方法。通過分析三個場景，采用先進(jìn)的SUMO模擬器和Hadoop軟件監(jiān)測該區(qū)域的車輛活動情況以及每條道路的交通細(xì)節(jié)，有助于檢測每條道路在模擬期內(nèi)的流通高峰期，幫助駕駛員及時選擇非擁堵路段，緩解交通壓力。