海量車牌識別數(shù)據(jù)集上基于時空劃分的旅行時間計算方法

趙卓峰,丁維龍,張　帥

(1.北方工業(yè)大學(xué)云計算研究中心,北京 100144;2.大規(guī)模流數(shù)據(jù)集成與分析技術(shù)北京市重點實驗室,北京 100144)

?

海量車牌識別數(shù)據(jù)集上基于時空劃分的旅行時間計算方法

趙卓峰1,2,丁維龍1,2,張帥1

(1.北方工業(yè)大學(xué)云計算研究中心,北京 100144;2.大規(guī)模流數(shù)據(jù)集成與分析技術(shù)北京市重點實驗室,北京 100144)

城市路段旅行時間計算是智能交通領(lǐng)域的一個研究熱點.車牌識別數(shù)據(jù)作為近年來新興的一種針對城市道路行駛車輛的實時監(jiān)測數(shù)據(jù),具有持續(xù)生成且數(shù)據(jù)量大、時間空間相關(guān)等特性.為了利用車牌識別數(shù)據(jù)集進行高效、準確的旅行時間計算,給出了基于車牌識別數(shù)據(jù)集的旅行時間計算定義,在此基礎(chǔ)上提出一種基于時空劃分的流水線式并行計算模型,并給出了該模型基于實時MapReduce的實現(xiàn).通過一組基于海量真實車牌識別數(shù)據(jù)集的實驗表明,本文方法在億級車牌識別數(shù)據(jù)集上的旅行時間計算性能方面相對于直接基于Hadoop的實現(xiàn)可以提高3倍以上,同時具有適合細粒度劃分及受路網(wǎng)規(guī)模影響小的特點.

旅行時間;時空劃分;流水線并行;實時MapReduce;車牌識別數(shù)據(jù)

1　引言

路段旅行時間作為城市交通出行信息的關(guān)鍵指標,是智能交通系統(tǒng)的重要基礎(chǔ),對其的研究一直是智能交通領(lǐng)域的熱點.城市路段旅行時間可以直接用來評判城市道路的運行狀況和擁堵水平,有效的旅行時間監(jiān)測與分析也可以為城市路網(wǎng)規(guī)劃、城市道路交通管理與控制、公眾出行路線選擇提供合理依據(jù).

以往,路段旅行時間主要采用基于樣本車輛監(jiān)測數(shù)據(jù)的測算方式,即采用樣本車輛的旅行時間來測算相關(guān)道路的旅行時間[1].目前,樣本車輛監(jiān)測數(shù)據(jù)的采集主要采用基于浮動車的數(shù)據(jù)采集方式.浮動車一般是指安裝了車載GPS定位裝置并行駛在城市主干道上的公交汽車和出租車,它可以通過車載GPS和無線通信接口周期性的采集車輛行駛數(shù)據(jù)[2].但由于浮動車數(shù)據(jù)涉及的樣本主要為特種車輛,其由于均具有特定的出行行為,因此會造成數(shù)據(jù)覆蓋面有限的問題,同時GPS數(shù)據(jù)往往與道路路段關(guān)系不能直接匹配,數(shù)據(jù)質(zhì)量也缺乏保障,因此在計算路段旅行時間上存在一定的不足.

車牌識別技術(shù)是近年來新興的一種城市通行車輛信息采集技術(shù),它通過對部署在城市道路的攝像頭所采集的車輛圖像信息進行識別來提取車輛的車牌信息,并在此基礎(chǔ)上形成包含車輛標識、出現(xiàn)地點、時間等內(nèi)容的車牌識別數(shù)據(jù).相比浮動車等車輛信息采集技術(shù),基于車牌識別數(shù)據(jù)的車輛信息采集技術(shù)具有工作連續(xù)性強、數(shù)據(jù)與道路關(guān)系精確度高、檢測樣本量大、覆蓋車輛范圍廣等優(yōu)點[3].因此,基于車牌識別數(shù)據(jù)的旅行時間計算成為當(dāng)前測算路段旅行時間的一個新途徑,對其的研究具有重要的應(yīng)用價值和學(xué)術(shù)意義.

基于車牌識別數(shù)據(jù)的路段旅行時間計算包括兩種情況,即基于實時車牌識別數(shù)據(jù)的實時旅行時間計算和基于歷史車牌識別數(shù)據(jù)的歷史旅行時間計算.其中,基于實時車牌識別數(shù)據(jù)的實時旅行時間計算按照一定的周期利用實時接收到車牌識別數(shù)據(jù)計算城市道路不同路段的實時旅行時間,其結(jié)果可用于實時路況信息服務(wù);基于歷史車牌識別數(shù)據(jù)的歷史旅行時間計算則主要針對已積累大量歷史車牌識別數(shù)據(jù)而尚未被利用計算旅行時間的情況,來批量處理得到城市道路不同路段歷史上的旅行時間數(shù)據(jù),其結(jié)果可被用來支持對出行規(guī)律、道路擁堵特點等的分析.本文重點解決后一種情況的旅行時間計算問題.

由于車牌識別數(shù)據(jù)來源于對城市道路行駛車輛的實時監(jiān)測,其包含車輛標識、監(jiān)測時間、地理位置等時間、空間以及車輛對象相關(guān)的信息,具有典型的時空相關(guān)、時序連續(xù)、位置可測的特征.此外,考慮到隨著車牌識別攝像頭在城市道路大范圍部署,車牌識別數(shù)據(jù)集的規(guī)模將大大超過傳統(tǒng)采樣方法獲得數(shù)據(jù)集的規(guī)模.當(dāng)前,一個大型城市部署的帶車牌識別數(shù)據(jù)的攝像頭可達到5000個,假設(shè)高峰期每個攝像頭車牌識別數(shù)據(jù)的采集頻率可達1條/秒,若每天的交通高峰折算率按0.33計,則一年將累積車輛識別數(shù)據(jù)記錄數(shù)超過500億條,數(shù)據(jù)存儲量超過2T.這些數(shù)據(jù)可構(gòu)成規(guī)模龐大的車牌識別數(shù)據(jù)集,僅對如此龐大的數(shù)據(jù)集進行順序掃描(按80M/s的速度計)也需要近7個小時.為此,為滿足基于車牌識別數(shù)據(jù)的路段旅行時間計算需求,迫切需要設(shè)計一種針對海量車牌識別數(shù)據(jù)集上旅行時間計算的高效方法.

本文主要針對海量車牌識別數(shù)據(jù)集上的路段旅行時間計算的需求,給出了基于車牌識別數(shù)據(jù)的路段旅行時間形式化定義,并按照該定義分析了海量車牌識別數(shù)據(jù)集上路段旅行時間計算的關(guān)鍵問題.在此基礎(chǔ)上,利用車牌識別數(shù)據(jù)的時空相關(guān)、對象相關(guān)等特征,采取數(shù)據(jù)劃分和任務(wù)流水的思路,提出一種基于時空劃分的流水線式旅行時間并行計算模型,并給出了一種基于改進的MapReduce模型的計算實現(xiàn)和基于真實車牌識別數(shù)據(jù)集的驗證分析.

2　路段旅行時間計算問題

2.1問題定義

定義1受測道路路網(wǎng).受測道路路網(wǎng)指由部署在城市道路上監(jiān)測點及其之間涉及的路段構(gòu)成的道路結(jié)構(gòu),可表示為R=(N,S),其中N為道路監(jiān)測點集合,S為路段集合.

定義3路段.路段指連接兩個相鄰監(jiān)測點之間的一條道路,路段si可表示為兩個監(jiān)測點的有序?qū)?np,nq>,np和nq分別表示路段si的起始點和終止點,si∈S.

時間區(qū)間δj指用于度量路段旅行時間的一個時間跨度,我們可以將給定的待測時間范圍內(nèi)按照時間周期劃分為不同的時間區(qū)間δj,所有的時間區(qū)間集合為δ.在現(xiàn)有的旅行時間研究中,一般選取每1小時、每15分鐘和每5分鐘三個時間周期進行時間區(qū)間劃分以對路段旅行時間進行度量[1].例如每15分鐘的時間周期中,將對0:00-0:15、0:15-0:20、……、23:45-24:00等一天中的96個時間區(qū)間進行旅行時間計算.

根據(jù)單車旅行時間獲得路段旅行時間還可以通過求平均值或加權(quán)平均值的方法來計算,但這里考慮到實際車輛出行中的一些特殊因素,如車輛在路段中的臨時停留或路邊停車以及套牌車等,這些因素下得到的單車旅行時間都會有較大的失真,并會給平均值方法計算路段旅行時間的準確性帶來一定的影響.為此,這里我們選擇中位數(shù)方法來獲得路段旅行時間,以屏蔽不合理的單車旅行時間帶來的影響.此外,這種方法下,路段旅行時間計算一般要求在特定時間區(qū)間內(nèi)通過該路段的車輛數(shù)(即計算得到的單車旅行時間數(shù))大于5輛,以避免由于車輛數(shù)過少而造成的中位數(shù)代表的旅行時間不精確問題.在單車旅行時間數(shù)小于5條時,將直接將前一時間周期計算得到的路段旅行時間作為當(dāng)前實際周期的路段旅行時間.

根據(jù)上述定義可以看出,相對于傳統(tǒng)基于浮動車采樣數(shù)據(jù)的旅行時間計算方法需要進行路段復(fù)合計算以及建立區(qū)分擁堵、非擁堵和路口排隊等情況的計算模型[4],基于車牌識別數(shù)據(jù)的路段旅行時間計算模型則相對簡單和直觀,只是在路段所采集的車牌識別數(shù)據(jù)較少時可能存在一定的旅行時間計算誤差而不得不采取復(fù)制前一時間區(qū)間旅行時間的計算方式.實際上,在這種情況下,可以綜合浮動車數(shù)據(jù)進行旅行時間計算,而且此時由于路段車流量不大,不存在前述基于浮動車采樣數(shù)據(jù)的旅行時間復(fù)雜計算情況.此外,基于車牌識別數(shù)據(jù)的路段旅行時間計算由于使用覆蓋范圍更廣的車牌識別數(shù)據(jù),相對與采樣性的浮動車數(shù)據(jù),其數(shù)據(jù)規(guī)模會更大,因此如何在海量車牌識別數(shù)據(jù)集(億級數(shù)據(jù)記錄)基礎(chǔ)上計算符合上述定義的路段旅行時間成為一個亟待解決的關(guān)鍵問題.

2.2問題分析

如圖1所示,按照上述路段旅行時間計算定義,在計算時首先需要對車牌識別數(shù)據(jù)集中的所有車牌識別數(shù)據(jù)按照時間區(qū)間(假設(shè)有j個時間區(qū)間,如圖1橫坐標δ1至δj,其中的點lix為一條車牌識別數(shù)據(jù))進行劃分,對同一劃分中的數(shù)據(jù)(假設(shè)每個劃分中數(shù)據(jù)為k條)兩兩比對,若兩條數(shù)據(jù)屬于同一輛車并且兩條數(shù)據(jù)中涉及的兩個監(jiān)測點(如圖縱坐標n1和n2)是受測道路路網(wǎng)中的路段,則求出并保存該路段在該歷史時間區(qū)間的單車旅行時間(如圖1中l(wèi)11、l22等為同一車牌的數(shù)據(jù),即同一車輛);最后,再對所有路段的不同時間區(qū)間上全部單車旅行時間取中位數(shù),得到最終道路歷史旅行時間結(jié)果集,該算法的復(fù)雜度為O(j×k2).在實際情況中,當(dāng)需要計算一個大型城市一年的歷史數(shù)據(jù)(車牌識別數(shù)據(jù)上億甚至百億)、計算時間周期為5分鐘時,j為105120,k最大約為150萬左右.此外,上述計算還受到路網(wǎng)中路段數(shù)量的影響,當(dāng)受測路網(wǎng)中路段數(shù)達到1000時,一年的路段旅行時間計算結(jié)果集數(shù)據(jù)條目數(shù)也將過億.輸入、緩存及產(chǎn)生如此大規(guī)模數(shù)據(jù),都將使得旅行時間計算的執(zhí)行時間將急劇增加.

為提高如上所述規(guī)模的車牌識別數(shù)據(jù)集基礎(chǔ)上路段旅行時間計算的性能,需要解決以下兩方面關(guān)鍵問題:

(1)如何根據(jù)前述路段旅行時間問題的定義并結(jié)合具有時空相關(guān)等特性的車牌識別數(shù)據(jù)特征設(shè)計旅行時間計算的并行化模式；(2)如何進行有效的車牌識別數(shù)據(jù)劃分,以便于將原始數(shù)據(jù)和中間結(jié)果動態(tài)分布到不同節(jié)點上處理,并可以盡量避免旅行時間計算過程中跨節(jié)點的數(shù)據(jù)訪問.

針對上述問題,本文利用車牌識別數(shù)據(jù)的時空相關(guān)、對象相關(guān)等特征,采取數(shù)據(jù)劃分和任務(wù)流水的思路,提出一種基于時空劃分的流水線式并行處理模型來解決基于海量車牌識別數(shù)據(jù)的路段旅行時間高效計算問題.

3　基于時空劃分的流水線式旅行時間并行計算模型

3.1模型描述

根據(jù)前文對路段旅行時間計算的分析可以看出,該計算的處理邏輯主要是針對不同時間區(qū)間的車牌識別數(shù)據(jù),先計算所有路段上的單車旅行時間再通過求單車旅行時間中位數(shù)來計算路段旅行時間.基于此,可以從時間和空間兩個角度來對原始車牌識別數(shù)據(jù)進行劃分與組織,而計算過程可以區(qū)分為相關(guān)車牌識別數(shù)據(jù)加載、單車旅行時間計算、單車旅行時間中位數(shù)計算三個階段的子任務(wù).同時,根據(jù)旅行時間計算定義可以看出,在具體計算過程中需要進行車輛對象和空間關(guān)系(即一條路段所涉及的兩個監(jiān)測點)的判定比對.而為了減少后續(xù)分布式旅行時間計算過程中跨節(jié)點的數(shù)據(jù)傳輸,為此要求在數(shù)據(jù)劃分時能夠減少跨數(shù)據(jù)劃分分區(qū)的計算,特別是頂層的數(shù)據(jù)劃分方法應(yīng)盡量避免跨分區(qū)的計算.因此,在這里,針對旅行時間計算涉及的時間、空間和對象三個維度,在車牌識別數(shù)據(jù)劃分時應(yīng)首先從與后續(xù)單車旅行時間計算等無關(guān)的時間維度進行劃分,以確保據(jù)此分布到各計算節(jié)點的數(shù)據(jù)不必為了相關(guān)計算而進行跨節(jié)點的傳輸.

按照上述認識,我們設(shè)計了如圖2所示的基于時空劃分的流水線式路段旅行時間并行計算模型.在該模型中,車牌識別數(shù)據(jù)首先可以劃分為時間維上區(qū)分的數(shù)據(jù)組,每組數(shù)據(jù)都包含一定數(shù)量的不同時間區(qū)間的數(shù)據(jù)子集;進一步某一時間區(qū)間的數(shù)據(jù)子集還可以根據(jù)所屬路段劃分為區(qū)域相關(guān)的數(shù)據(jù)子集,區(qū)域內(nèi)數(shù)據(jù)可以進一步按照車輛數(shù)據(jù)對象進行組織;在上述兩級數(shù)據(jù)劃分基礎(chǔ)上,由于相關(guān)車牌識別數(shù)據(jù)加載、單車旅行時間計算、單車旅行時間中位數(shù)計算三個子任務(wù)的計算結(jié)果間不具有直接的因果相關(guān)性,即每個子任務(wù)僅依賴于特定的中間結(jié)果,而不一定必須是其上游任務(wù)的輸出結(jié)果.因此路段旅行時間的計算可以對此三個子任務(wù)進行階段化劃分,從而可以以流水線方式針對不同劃分的數(shù)據(jù)子集來完成路段旅行時間計算.此外,在按區(qū)域劃分數(shù)據(jù)時除了先按路段劃分再按車輛對象組織外,還可以選擇先按車輛對象劃分再按路段組織,在文章后續(xù)部分我們將通過實驗來驗證這兩種劃分方式下旅行時間計算性能方面的差異并分析相關(guān)原因.

上述模型從總體層面看遵循了單控制流多數(shù)據(jù)流(SPMD,singleprocessandmultipledata)的并行模式[5],而在數(shù)據(jù)并行方面結(jié)合車牌識別數(shù)據(jù)的時空特征可以進一步從時間維和空間維兩級劃分,在計算任務(wù)方面則可以利用旅行時間計算步驟的細分形成流水線式并行.

3.2基于實時MapReduce的模型實現(xiàn)

為實現(xiàn)上述基于時空劃分的流水線式路段旅行時間并行處理模型,采用我們之前提出的實時MapReduce計算模型[6]思路并在其基礎(chǔ)上來實現(xiàn)時空劃分的數(shù)據(jù)并行化及流水線式的計算任務(wù)并行化.實時MapRedcue計算模型的核心思想是通過在傳統(tǒng)MapReduce實現(xiàn)中引入中間結(jié)果的緩存機制和Map及Reduce任務(wù)的流水線式處理來提高MapReduce模型的處理性能.

在本文中,我們按照上述時空劃分的流水線并行計算模型,通過設(shè)計適于時空劃分處理的分布式HashB樹緩存數(shù)據(jù)結(jié)構(gòu)來優(yōu)化本地中間結(jié)果的高并發(fā)讀寫性能,并進一步通過定義路段旅行時間計算的流水線處理階段來實現(xiàn)階段化的流水線式MapReduce處理以提高旅行時間計算性能.

具體的模型實現(xiàn)機制如下:

(1)基于分布式HashB樹的數(shù)據(jù)緩存

對于旅行時間計算中涉及的海量歷史車牌識別數(shù)據(jù),我們采用HashB樹來進行內(nèi)存中的緩存.在該結(jié)構(gòu)中,首先為支持時間區(qū)間劃分采用時間區(qū)間作為Key,相同時間區(qū)間的車牌識別數(shù)據(jù)在Hash表的同一項中用B樹組織;其次,監(jiān)測點作為空間劃分基礎(chǔ)并用來組織最終的車牌識別數(shù)據(jù),每個監(jiān)測點的車牌識別數(shù)據(jù)在B樹的葉節(jié)點用鏈表按照時間順序進行組織.

對于計算過程中產(chǎn)生的大量單車旅行時間計算結(jié)果,我們同樣采用類似的結(jié)構(gòu)來進行緩存,主要區(qū)別就是將上述HashB樹中葉節(jié)點由監(jiān)測點識別數(shù)據(jù)替換為特定車輛在不同路段的旅行時間鏈表.

此外,在緩存機制方面,進一步還可利用B樹在平均搜索性能和平衡性方面的特征,使用多路搜索方式提升了B樹的并發(fā)查詢性能,并且利用讀寫開銷估算和緩沖區(qū)信息改造外存SSTable文件讀寫策略和內(nèi)外存替換機制.由于篇幅所限,更多的計算中間結(jié)果緩存機制細節(jié)可以參見我們之前在文獻[7]中給出的介紹.

(2)階段化流水線處理

針對旅行時間計算處理邏輯中涉及的相關(guān)車牌識別數(shù)據(jù)加載、單車旅行時間計算、單車旅行時間中位數(shù)查找三個子任務(wù),可采用兩次MapReduce迭代以及Map和Reduce階段的流水線控制機制來實現(xiàn)階段化流水線處理.其中,第一次MapReduce處理中的Map函數(shù)完成車牌識別數(shù)據(jù)的劃分讀入和如前所述的數(shù)據(jù)結(jié)構(gòu)組織,得到形如的鍵值對,Reduce函數(shù)根據(jù)路段信息對中間結(jié)果按照車牌號進行重組織得到形為的鍵值對;第二次MapReduce處理中的Map函數(shù)僅計算單車路段旅行時間而不做數(shù)據(jù)變換,Reduce函數(shù)進行所有單車旅行時間中位數(shù)查找,最后得到鍵值對.一個路段旅行時間計算結(jié)果示例形如<201310020830+LD0014[JCD06,JCD07],360>,該示例表示在2013年10月2號8點30分到8點45分的時間區(qū)間,0014號路段(即監(jiān)測點JCD06到監(jiān)測點JCD07的路段)的旅行時間為360s.通過上述描述可以看到,基于區(qū)域路段的劃分方式下旅行時間計算通過兩次循環(huán)對監(jiān)測點Map列表中的key值進行兩兩比對,判斷是否為路段基礎(chǔ)表中數(shù)據(jù).然后通過對于路段兩個上下游監(jiān)測點對應(yīng)的過車記錄列表進行對比,找出相同車輛及其通過的時間,并將得到的屬性值整合成的鍵值對形式,其算法時間復(fù)雜度為O(n×m2),其中m為全路網(wǎng)中路段監(jiān)測點數(shù)目,n為一個時間區(qū)間下通過一個監(jiān)測點的車輛數(shù).

4　實驗與分析

4.1實驗設(shè)置

實驗環(huán)境采用的是在五臺服務(wù)器上搭建的集群環(huán)境,并在其上部署我們基于Hadoop擴展了中間結(jié)果緩存和流水線處理機制后的路段旅行時間計算實現(xiàn).其中,Master節(jié)點配置為4核CPU、4G內(nèi)存,master節(jié)點同時也被當(dāng)作計算節(jié)點;另外四臺Slave節(jié)點配置為2核CPU、4G內(nèi)存,作為計算節(jié)點.此外,每臺服務(wù)器的有效容量為80G,集群總存儲容量為400G.實驗中采用的數(shù)據(jù)為北京市一千多個帶識別功能的攝像頭2012-10-17到2013-01-04這80天采集到的真實車牌識別數(shù)據(jù),總數(shù)據(jù)量近5億條.

為了從性能對比、關(guān)鍵參數(shù)影響和擴展性三方面對本文提出的旅行時間計算方法進行驗證分析,以及考察旅行時間計算中路段數(shù)目(代表受測路網(wǎng)規(guī)模)、車牌識別數(shù)據(jù)記錄數(shù)和Hadoop集群節(jié)點數(shù)三個參數(shù)對旅行時間計算的不同影響,我們設(shè)計了如下的一組實驗:實驗1考察在5個計算節(jié)點、路段數(shù)目固定為210的情況下,分別測試從5000萬到4億等不同數(shù)量的車牌識別數(shù)據(jù)集下5分鐘、15分鐘和1小時三個時間周期路段旅行時間計算性能情況.并選取直接基于Hadoop實現(xiàn)的旅行時間計算方法(LMR)[8]作為比較對象,與本文方法(CMR)進行性能比較.

實驗2對兩種數(shù)據(jù)二次劃分方式進行對比,(1)CMR方法中最終采取的先按路段劃分再按車輛對象組織方式(記為RegionList方式),(2)先按車輛對象劃分再按路段組織方式(記為VehicleList方式).實驗在5個計算節(jié)點、路段數(shù)目不變的情況下,通過輸入不同數(shù)量的車牌識別數(shù)據(jù),考察兩種劃分方式下路段旅行時間計算性能差異.

實驗3考察受測路網(wǎng)中的路段數(shù)目對路段旅行時間計算方法性能的影響.選取20天的車牌識別數(shù)據(jù)(約1億條)作為原始計算數(shù)據(jù)集,在5個計算節(jié)點下,對受測路網(wǎng)中的路段數(shù)目從10到210進行調(diào)整,并分別測試5分鐘、15分鐘和1小時三個時間周期下的計算性能情況.

4.2實驗結(jié)果分析

(1)計算性能對比分析

通過實驗1得到如圖3所示結(jié)果.從圖中可看出,隨著參與計算的車牌識別數(shù)據(jù)集數(shù)據(jù)量的增加,兩種計算方法的計算時間均呈線性增加.但CMR方法在計算效率上比LMR方法有較高的提升,并且CMR方法受時間周期差異的影響比LMR方法小很多,5分鐘、15分鐘和1小時三個不同時間周期下計算時間的差異均在100秒以內(nèi).

此外,從圖中還可以看到,LMR方法在計算時間周期越短(即時間段劃分粒度越細)的情況下,計算時間越長,5分鐘周期下的計算時間最長,而CMR方法恰好相反,在計算時間周期變短的情況下,計算時間反而會略微減少,5分鐘周期下的計算時間最短.究其原因,主要因為當(dāng)計算時間周期較小時,需要計算旅行時間的時間區(qū)間數(shù)量會大幅增加,使得Hadoop運行態(tài)中的Map和Reduce任務(wù)大增并帶來較大的任務(wù)執(zhí)行調(diào)度代價,傳統(tǒng)LMR方法由于未根據(jù)車牌識別數(shù)據(jù)進行劃分優(yōu)化,執(zhí)行中需要大量的Map和Reduce任務(wù)間的同步等待,從而使得小時間周期下的計算時間變長.而CMR方法通過時空劃分和流水線執(zhí)行避免了無必要Map和Reduce任務(wù)間由于數(shù)據(jù)依賴的同步等待,同時優(yōu)化了執(zhí)行效率,這樣單個Map和Reduce任務(wù)一次處理的數(shù)據(jù)量(受時間區(qū)間大小影響)成為影響計算時間的主要因素,因此使得短時間周期下的計算時間反而變短.由此可見,CMR方法更能適應(yīng)細粒度時間周期的旅行時間計算.

(2)不同數(shù)據(jù)劃分方式的對比分析

通過圖4所示的實驗2結(jié)果可以看出,兩種不同的數(shù)據(jù)劃分方法下的旅行計算時間均隨數(shù)據(jù)量增加線性增長,但是隨著數(shù)據(jù)量增加,在計算效率上先按路段劃分再按車輛對象組織(RegionList)的劃分方式比先按車輛對象劃分再按路段組織(VehicleList)的劃分方式表現(xiàn)出更好的性能.通過分析可以看出,在單車旅行時間求解步驟中的第一種劃分方式的計算復(fù)雜度主要依賴全路網(wǎng)中監(jiān)測點數(shù)目和一個時間區(qū)間下通過一個監(jiān)測點的車輛數(shù),而第二種劃分方式的計算復(fù)雜度則依賴于一個時間區(qū)間下一輛車經(jīng)過檢測點數(shù)目和全路網(wǎng)中車輛數(shù).由于實際情況中,全路網(wǎng)中車輛數(shù)的量級明顯大于其它參數(shù)的量級,因此先按路段劃分再按車輛對象組織的區(qū)域劃分方式能更好的適應(yīng)路網(wǎng)中存在大規(guī)模車輛的情況.

(3)關(guān)鍵參數(shù)影響對比分析

由實驗3我們得到如圖5所示的實驗結(jié)果.從實驗結(jié)果可看出,隨著受測路網(wǎng)中路段數(shù)目的增加,本文CMR計算方法的計算時間基本平滑,而LMR方法則在路段數(shù)增大時表現(xiàn)出計算時間線性增長的趨勢.這表明CMR計算方法的計算性能基本不受路段數(shù)目的影響,當(dāng)我們增加受測路網(wǎng)規(guī)模(即增加路段數(shù))時,并不影響旅行時間計算的計算性能.其中的主要原因在于,路段數(shù)在旅行時間計算中主要影響是會增大計算中間結(jié)果的規(guī)模,CMR方法由于采用基于分布式Hash B樹緩存結(jié)構(gòu)優(yōu)化了中間結(jié)果的處理,因此其受路段數(shù)變化的影響較小.

5　相關(guān)工作

旅行時間計算一直是智能交通研究中的一個熱點問題.文獻[3]利用十余個道路交叉口的車牌識別數(shù)據(jù),應(yīng)用假設(shè)檢驗的方法研究城市快速路及主干道的旅行時間.然而上述工作使用的采樣數(shù)據(jù)僅為1小時內(nèi)數(shù)據(jù),數(shù)據(jù)量較小,在考慮城市所有路段旅行時間計算時,這種分布估計方法很難適用.文獻[8]通過Hadoop實現(xiàn)了基于海量車牌識別數(shù)據(jù)的城市道路旅行時間實測計算,支持自定義路段集下不同時間區(qū)間的道路旅行時間計算.但該工作中并未根據(jù)車牌識別數(shù)據(jù)的時空特性進行專門設(shè)計,僅直接運用Hadoop給出了旅行時間計算的樸素實現(xiàn).文獻[9]將MapReduce分布式計算框架應(yīng)用于道路交通流量統(tǒng)計計算中,證明了利用Hadoop技術(shù)進行交通數(shù)據(jù)存儲和處理是合理、可行、高效的,但該工作僅適用于簡單的數(shù)據(jù)統(tǒng)計計算,對于旅行時間計算這種需考慮到數(shù)據(jù)時空特性的計算還需對現(xiàn)有MapReduce模型進行相應(yīng)修改才能提高計算效率.

近年來,很多研究者根據(jù)不同應(yīng)用需求對MapReduce模型及其開源實現(xiàn)Hadoop進行改進,以適應(yīng)不同類型大數(shù)據(jù)的處理需求.文獻[10]設(shè)計并實現(xiàn)了G-Hadoop,在此平臺上可以應(yīng)用MapReduce編程框架在多個集群上進行并行計算.與本文思路相似,文獻[11]按照重用MapReduce處理過程中中間結(jié)果的思路設(shè)計了一種Hadoop擴展實現(xiàn)的HaLoop,HaLoop提供了在MapReduce基礎(chǔ)上表達循環(huán)式處理的編程模型以及可保證多次循環(huán)中任務(wù)可以調(diào)度到同一節(jié)點的執(zhí)行調(diào)度器,基于這種設(shè)計MapReduce處理過程中的中間結(jié)果可以被緩存與重用.同樣,文獻[12]在集中式處理基礎(chǔ)上,設(shè)計了一個支持可擴展的并行分布式流處理系統(tǒng),也能響應(yīng)流式數(shù)據(jù)上的連續(xù)的查詢請求.為了提升MapReduce對迭代執(zhí)行類的程序的支持能力,文獻[13]設(shè)計了一種擴展的MapReduce框架,與HaLoop工作的不同之處在于該框架還支持對Map任務(wù)的異步執(zhí)行同時允許每次迭代不必充分創(chuàng)建Map/Reduce任務(wù).Spark[14]是近兩年興起的一類新的分布式計算框架,其采用基于內(nèi)存的方式來提升迭代式MapReduce作業(yè)的計算效率,在中間結(jié)果處理的設(shè)計思路上與我們的工作有相似之處,但是本文工作的主要特點是在計算中結(jié)合交通數(shù)據(jù)特征融入具有時空特性的數(shù)據(jù)模型進行優(yōu)化,更適于實現(xiàn)基于時空劃分的旅行時間流水線式計算.

綜上,現(xiàn)有的相關(guān)工作大都集中在通用的計算平臺,在時空對象數(shù)據(jù)劃分及執(zhí)行優(yōu)化方面缺乏從交通數(shù)據(jù)及其計算特征方面的針對性設(shè)計,因此不能直接用來解決具有周期性批數(shù)據(jù)處理特點的旅行時間計算問題.相對于上述工作,本文則是利用車牌識別數(shù)據(jù)的時空特性并參考上述相關(guān)工作,重點通過數(shù)據(jù)的時空劃分和計算任務(wù)的流水線設(shè)計實現(xiàn)對旅行時間計算模型進行優(yōu)化,以達到提高旅行時間計算性能的目的.

6　結(jié)束語

海量車牌識別數(shù)據(jù)集上的旅行時間計算是當(dāng)前智能交通應(yīng)用建設(shè)中一個新的探索.本文針對該問題,定義了基于車牌識別數(shù)據(jù)的旅行時間計算概念,提出一種基于時空劃分的流水線式并行計算模型,并給出了該模型基于實時MapReduce的實現(xiàn).通過一組基于海量真實車牌識別數(shù)據(jù)集的實驗表明,相對于傳統(tǒng)的旅行時間計算方式,本文方法表現(xiàn)出了較高的性能,同時具有適合細粒度劃分及受路網(wǎng)規(guī)模影響小等特點.下一步的工作包括在百億記錄級模擬數(shù)據(jù)上的實驗測試以及時空并行計算模型在其它交通應(yīng)用中的適用性驗證與分析.

[1]朱愛華.基于浮動車數(shù)據(jù)的路段旅行時間預(yù)測研究[D].北京:北京交通大學(xué),2008.

Zhu Aihua.Research on link travel time prediction method based on data collected by floating car[D].Beijing Jiaotong University,2008.(in Chinese)

[2]廖律超,等.一種支持軌跡大數(shù)據(jù)潛在語義相關(guān)性挖掘的譜聚類方法[J].電子學(xué)報,2015,43(5):956-964.

Liao Lvchao,et al.A spectral clustering method for big trajectory data mining with latent semantic correlation[J].Acta Electronica Sinica,2015,43(5):956-964.(in Chinese)

[3]姜桂艷,等.基于車牌識別數(shù)據(jù)的交通擁堵識別方法[J].哈爾濱工業(yè)大學(xué)學(xué)報,2011,43(4):131-135.Jang Jiayan,et al.Traffic congestion identification method based on license plate recognition data[J].Journal of Harbin Institute of Technology,2011,43(4):131-135.(in Chinese)

[4]劉好德.基于浮動車數(shù)據(jù)的城市交通狀態(tài)判別與行程時間計算[R].同濟大學(xué),博士后出站報告,2010.

Liu Haode.Estimation of urban traffic status and prediction of travel time based on floating car data[R].Research Report for Post-Doctor,Tongji University,2010.(in Chinese)

[5]朱定局.并行時空模型[M].北京:科學(xué)出版社,2009.

Zhu Dingjun.Parallel Space-Time Model[M].Beijing,Science Press,2009.(in Chinese)

[6]亓開元,趙卓峰,房俊,馬強.針對高速數(shù)據(jù)流的大規(guī)模數(shù)據(jù)實時處理方法[J].計算機學(xué)報,2012,35(3):477-490.Qi Kaiyuan,Zhao Zhuofeng,Fang Jun.Real-time processing for high speed data stream over large scale data[J].Chinese Journal of Computers,2012,35(3):477-490.(in Chinese)

[7]亓開元,韓燕波,趙卓峰,等.支持高并發(fā)數(shù)據(jù)流處理的MapReduce中間結(jié)果緩存.計算機研究與發(fā)展,2013,50(1):111-121.

Qi Kaiyuan,Han Yanbo,Zhao Zhuofeng,et al.MapReduce intermediate result cache for concurrent data stream processing[J].Journal of Computer Research and Development,2013,50(1):111-121.(in Chinese)

[8]張帥,趙卓峰,丁維龍.基于MapReduce的城市道路旅行時間實測計算[J].計算機與數(shù)字工程,2014,42(9):1542-1546.

Zhang Shuai,Zhao Zhuofeng,Ding Weilong.Urban road trip time measured calculation based on mapReduce[J].Computer & Digital Engineering,2014,42(9):1542-1546. (in Chinese)

[9]廖飛,黃晟,龔德俊.基于Hadoop的城市道路交通流量數(shù)據(jù)分布式存儲與挖掘分析研究[J].公路與汽運,2013,27(5):82-86.

Liao Fei,Huang Sheng,Gong Dejun.Distributed storage and data mining analysis of urban road traffic based on hadoop[J].Highways & Automotive Applications,2013,27(5):82-86.(in Chinese)

[10]Lizhe Wang,et al.G-Hadoop:MapReduce across distributed data centers for data-intensive computing[J].Future Generation Computer Systems,2013,29(3):739-750.

[11]Yingyi Bu,Bill Howe,Magdalena Balazinska,et al.The haLoop approach to large-scale iterative data analysis[J].VLDB Journal,2012,21(2):169-190.

[12]張鵬,劉慶云,譚建龍,等.流水行云:支持可擴展的并行分布式流處理系統(tǒng)[J].電子學(xué)報,2015,43(4):639-646.

Zhang Peng,Liu Qingyun,Tan Jianlong,et al.SPSPS:A scalable parallel-distributed stream processing system[J].Acta Electronica Sinica,2015,43(4):639-646.(in Chinese)

[13]Yanfeng Zhang,et al.iMapReduce:A distributed computing framework for iterative computation[J].Journal of Grid Computing,2012,10:47-68.

[14]Matei Zaharia.An Architecture for fast and general data processing on large clusters[R].University of California,Berkeley,Technical Report No.UCB/EECS-2014-12,2014.

趙卓峰男,1977年5月出生,山東濟南人.博士,現(xiàn)為北方工業(yè)大學(xué)云計算研究中心副研究員、副主任.研究方向為云計算、流數(shù)據(jù)處理、服務(wù)計算、智能交通.

E-mail:edzhao@ncut.edu.cn

丁維龍男,1983年3月出生,山東泰安人.博士,現(xiàn)為北方工業(yè)大學(xué)云計算研究中心助理研究員.主要研究方向為流數(shù)據(jù)處理、流計算及分布式系統(tǒng).

E-mail:dingweilong@ncut.edu.cn

A Travel Time Calculation Method Based on Spatio-Temporal Data Partition of Large-Scale License Plate Recognition Data Set

ZHAO Zhuo-feng1,2,DING Wei-long1,2,ZHANG Shuai1

(1.CloudComputingResearchCenter,NorthChinaUniversityofTechnology,Beijing100144,China; 2.BeijingKeyLaboratoryonIntegrationandAnalysisofLarge-ScaleStreamData,Beijing100144,China)

The calculation of travel time of city roads is an important issue in the domain of the intelligent transportation system research.License plate recognition data is one kind of monitoring data for vehicles running on urban roads,which has some new features,such as high volume,high velocity and spatio-temporal correlation.In order to achieve travel time calculations on massive license plate recognition data collection,we present the formal definition of travel time calculation based on license plate recognition data set,and propose a pipelined parallel computing model based on spatio-temporal data partition.Moreover,the implementation of the computing model is given based on a real-time MapReduce computing system.The corresponding experiments based on real license plate recognition data set show that,the computing performance on million-level data sets of our method can achieve three times increasing compared to traditional travel time calculation methods.Meanwhile our method is more suitable for fine-grained partition and large scale traffic network.

travel time;spatio-temporal partition;parallel pipeline;real-time mapreduce;large-scale license plate recognition data

2014-11-24;

2015-10-19；責(zé)任編輯：馬蘭英

北京市自然科學(xué)基金(No.4131001,No.4162021);北京市屬高等學(xué)校創(chuàng)新團隊建設(shè)項目(No.IDHT20130502)；北方工業(yè)大學(xué)?？蒲谢?/p>

TP301

A

0372-2112 (2016)05-1227-07

電子學(xué)報URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.05.031