郭淑琴,薛益趙,徐步匯

(1.浙江工業(yè)大學 信息工程學院，浙江 杭州 310023；2.浙江工業(yè)大學 機械工程學院，浙江 杭州 310014)

一種基于Hadoop的分布式地圖匹配算法

郭淑琴1,薛益趙1,徐步匯2

(1.浙江工業(yè)大學 信息工程學院，浙江 杭州 310023；2.浙江工業(yè)大學 機械工程學院，浙江 杭州 310014)

摘要：浮動車數(shù)據(jù)是重要的交通數(shù)據(jù)之一,能為相關(guān)部門提供實時交通狀況信息.傳統(tǒng)地圖匹配算法難以直接適用于海量的浮動車數(shù)據(jù)匹配.因此在Hadoop的基礎(chǔ)上，設(shè)計了一種分布式并行地圖匹配系統(tǒng)，該系統(tǒng)加入了HashMap網(wǎng)格索引算法，能夠加快匹配初篩速度，達到并行處理的效果,同時結(jié)合海拔高程信息和道路模糊化函數(shù)提升匹配準確度.實驗結(jié)果表明所提算法具備較好的高效性和準確性.

關(guān)鍵詞：地圖匹配；浮動車；智能交通系統(tǒng)；云計算

Research on distributed map-matching algorithm based on Hadoop

GUO Shuqin1, XUE Yizhao1, XU Buhui2

(1.College of Information Engineering, Zhejiang University of Technology, Hangzhou 310023, China；

2.College of Mechanical Engineering, Zhejiang University of Technology, Hangzhou 310014, China)

Abstract:Floating car data is one of the most important traffic data, which can provide real-time traffic information for relevant departments. Traditional map-matching algorithm is difficult to directly apply to the numerous floating car. Based on the Hadoop, one kind of distributed parallel map-matching system is designed. It adds the HashMap grid index algorithm in order to accelerate the speed of matching screening and achieve the effect of parallel processing. At the same time, it can enhance matching accuracy through combining elevation information and road fuzzy matching function. The experimental result shows that the proposed method has higher efficiency and higher accuracy.

Keywords:map-matching; floatingvehicles; intelligent transportation system; Hadoop

隨著社會的發(fā)展和經(jīng)濟的增長，城市交通擁堵現(xiàn)象愈發(fā)嚴重.浮動車技術(shù)作為一種新型的城市出行規(guī)劃方式和路況信息獲取方式,已經(jīng)逐步成為研究熱點[1].地圖匹配技術(shù)是浮動車數(shù)據(jù)處理中最關(guān)鍵的內(nèi)容之一,只有判斷出車輛在哪條道路上行駛,才能將GPS數(shù)據(jù)轉(zhuǎn)化為有效的道路交通狀態(tài)信息[2].由于浮動車自身特點，在傳統(tǒng)的MPI和OpenMP分布式并行模型下,編程難度大，可擴展性差，浮動車數(shù)據(jù)進行地圖匹配耗費大量的計算時間，因此很難應用于海量浮動車數(shù)據(jù)處理.

筆者將從兩個方面改進匹配效果：1) 鑒于傳統(tǒng)并行方法編程難度大，可擴展性差的問題，設(shè)計一種能應用于Hadoop分布式平臺的地圖匹配方法提升匹配效率；2) 通過合理應用海拔高程信息提升匹配準確度，改進傳統(tǒng)方法在處理高架和地面道路重疊時的不足.

1基本算法

1.1建立HashMap網(wǎng)格索引

城市道路是錯綜復雜，同時也是分散在城市的各個區(qū)域上.當對一個待匹配點進行匹配計算時，如果將幾公里以外的道路也納入匹配范圍，可想而知將會嚴重影響整體的匹配效率，所以建立一個高效的索引算法對加快匹配速度顯得格外重要[3-4].傳統(tǒng)的網(wǎng)格索引和四叉樹索引的時間復雜度均為對數(shù)時間級，考慮到分布式環(huán)境下的高并發(fā)性要求，筆者設(shè)計一種新型的HashMap網(wǎng)格索引[5].

HashMap網(wǎng)格索引比起傳統(tǒng)的四叉樹索引優(yōu)勢在于：傳統(tǒng)四叉樹索引采用地理空間遞歸的方法劃分不同層次的樹結(jié)構(gòu)，但空間對象分布不均勻時，隨著地理空間對象的不斷插入，將形成一棵嚴重不平衡的四叉樹，從而導致查詢效率的急劇下降，在理想情況下時間開銷也是對數(shù)時間級，而HashMap索引通過數(shù)組Hash映射，將查找時間開銷降低到O(1)時間量級.HashMap網(wǎng)格索引同時將網(wǎng)格區(qū)域所對應的道路節(jié)點信息提前存儲到Hadoop分布式緩存上，而不是采用傳統(tǒng)的方法根據(jù)待匹配點為中心建立網(wǎng)格匹配區(qū)，通過改進這兩點大大的提高了算法在Hadoop分布式平臺上的高并發(fā)性.

如圖1(a)所示，根據(jù)城市最大外包矩形劃分網(wǎng)格，同時依據(jù)Taylor提出的在GPS定位中,以距原始定位點100 m內(nèi)的道路為計算路段,車輛位于這些路段的置信度為95%[6],將單個網(wǎng)格的長和高設(shè)置為100 m.對于待匹配點P，只需根據(jù)P點的經(jīng)度減去左上角頂點的經(jīng)度，以杭州為例左上角頂點經(jīng)度為119.698，然后除以100 m所對應的經(jīng)度范圍0.000 9后向下取整就可得到P點所在網(wǎng)格的列號.同理，P點的行號可以確定.當計算出行號和列號后，通過Hash映射就可以確定P點所在網(wǎng)格的確切位置[7].

圖1　HashMap網(wǎng)格索引示意圖Fig.1　Schematic diagram of the Hashmap grid index

在對待匹配點P進行匹配時發(fā)現(xiàn),當P點處在網(wǎng)格的邊緣，就有可能造成與P點相匹配的道路位于相鄰的其它網(wǎng)格內(nèi)，從而無法準確匹配.所以對單個網(wǎng)格內(nèi)部再進行了一次劃分，如圖1(b)所示，分成1區(qū)，2區(qū)，3區(qū)，4區(qū).對于待匹配點P需要計算的網(wǎng)格包括P點所在的網(wǎng)格，以及該網(wǎng)格相鄰上方網(wǎng)格的4區(qū)，右上角網(wǎng)格的3區(qū)和右相鄰網(wǎng)格的1區(qū).通過二次劃分大大提升了匹配的準確度.

1.2歸一模糊化的非高架/高架匹配算法

圖2為匹配算法的總流程圖，將匹配算法分為非高架匹配法和高架匹配法兩部分，因為高架匹配算法的計算量大于非高架匹配算法，所以通過判斷待匹配點所在網(wǎng)格緩沖區(qū)內(nèi)是否包含高架來提高匹配效率，并且能很好的解決高架與地面重疊、交疊、平行的情形.

非高架匹配算法采用車頭方向與路段方向之間夾角，待匹配點到路段垂直投影距離兩種因素的歸一模糊匹配系統(tǒng).高架匹配算法在此基礎(chǔ)上加入了高程差.歸一模糊系統(tǒng)框架如圖3所示.

在該框架內(nèi)我們引入歸一模糊化值函數(shù)λ：歸一模糊化值是描述浮動車GPS坐標位置與一條道路的匹配程度，使用(0,1)區(qū)間的浮點數(shù)進行歸一模糊化，歸一模糊化值越接近1，代表該待匹配點越有可能位于這條道路[8].

圖2　匹配算法總流程圖Fig.2　Flow chart of matching algorithm

圖3　歸一模糊系統(tǒng)框架Fig.3　Normalized fuzzy system framework

非高架歸一模糊化值函數(shù)為

(1)

式中：ΔGPS為GPS的平均誤差值；d為待匹配點到路段的垂直距離；θ為車頭方向與路段方向之間的夾角；μ1和μ2分別為距離和夾角在歸一模糊化值中的權(quán)重,且滿足μ1+μ2=1.

高架歸一模糊化值函數(shù)為

(2)

式中：h為待匹配點的高程；H為路網(wǎng)信息的高程；μ1，μ2和μ3分別為距離、夾角和高程在歸一模糊化值中的權(quán)重,且滿足μ1+μ2+μ3=1.

1.3候選匹配道路集合R

為了滿足Hadoop分布式平臺的高并發(fā)性，減少歸一模糊化值的計算量，在計算歸一模糊化值之前筆者引入候選匹配道路集合R，在候選道路集合R中定義閥值Κ，且Κ=ΔGPS，當待匹配點到道路的投影距離d-Κ<0時，就認為該道路是有可能的正確匹配路段，因此將該道路加入到候選匹配道路集合R中.當不滿足上述條件時，果斷拋棄該條道路，不在繼續(xù)計算夾角度量和高程差度量.

2Hadoop分布式平臺搭建

MPI，OpenMP和Hadoop是當前并行計算領(lǐng)域三個主流的并行系統(tǒng)框架，筆者采用Hadoop系統(tǒng)框架和map/reduce處理模式，Hadoop框架具有可擴展性好，編程難度低的特點，同時也是近年來研究的熱點.在三臺配置為Core i5-3320雙核2.60ghz CPUS，8G內(nèi)存，1T硬盤，Ubuntu系統(tǒng)上搭建小型Hadoop集群，該集群配有一個Namenode節(jié)點和兩個Datanode節(jié)點[9].NameNode節(jié)點相當于一個管理者，將輸入數(shù)據(jù)進行切片分塊，然后分發(fā)給下面的DataNode節(jié)點進行處理.DataNode節(jié)點相當于一個執(zhí)行者，它調(diào)用Map函數(shù)將接收到的數(shù)據(jù)塊進行匹配運算.

Map/Reduce過程是Hadoop框架的主要工作模式，在負責完成海量浮動車數(shù)據(jù)的地圖匹配計算任務圖4中，Map過程主要包括：1) 接收系統(tǒng)分發(fā)下來的浮動車數(shù)據(jù)塊；2) 解析出浮動車數(shù)據(jù)對應的哈希碼；3) 從系統(tǒng)分布式緩存中調(diào)取相應哈希碼的網(wǎng)格中的道路節(jié)點信息；4) 根據(jù)匹配規(guī)則進行歸一模糊化匹配計算；5) 將匹配結(jié)果輸出到Reduce過程.

Reduce過程主要包括：1) 接收從Map過程中計算后的匹配數(shù)據(jù)；2) 將匹配數(shù)據(jù)進行快速排序，輸出最大值作為最終匹配結(jié)果.

圖4　Map/Reduce處理過程Fig.4　Map/Reduce processing procedure

3算法評估及系統(tǒng)驗證

使用的浮動車數(shù)據(jù)來源于杭州市8 000多輛裝備有GPS設(shè)備的出租車(2012.06-2013.05)，以每20 s時間間隔向主服務器發(fā)送一次GPS數(shù)據(jù).數(shù)據(jù)的主要結(jié)構(gòu)包括車輛編號、地理位置、發(fā)送時間、經(jīng)度、緯度、行駛速度、行駛方向、高程及載客狀態(tài).路網(wǎng)數(shù)據(jù)來源于浙江銀江某研究院提供的杭州市GPS路網(wǎng)坐標信息，其中包括道路路段編號、道路起始點經(jīng)緯度坐標、道路終止點經(jīng)緯度坐標.

3.1同一浮動車的連續(xù)匹配評估舉例

筆者方法在對同一浮動車的連續(xù)匹配時有明顯的效果.由于考慮了車頭方向與路段方向之間的夾角，點到路段的垂直距離兩種因素，可以有效地避免在交叉路口處的錯誤匹配.圖5(a)為服務器對同一浮動車接收到的原始定位信息，從圖5中可以看出：原始定位信息不準確，大多數(shù)都偏離了道路.圖5(b)為經(jīng)過匹配算法矯正后的定位信息，相較與圖5(a)精確度大大提高，定位點基本位于道路的中心線上.

3.2地面道路與高架交疊情況下的匹配評估舉例

筆者方法在對地面道路與高架交疊情況下時有較準確的匹配效果.圖6(a)為處于地面道路與高架交疊路段時浮動車的原始定位信息，H表示高程值，通過合理利用浮動車高程信息將待匹配點準確的匹配到高架與地面道路上，如圖6(b)所示.

圖5　同一浮動車的連續(xù)匹配效果圖Fig.5　Continuous matching of the same floating car

圖6　地面道路與高架交疊情況下匹配效果圖Fig.6　Matching with the ground road and overhead road overlapping

3.3大批量浮動車數(shù)據(jù)的匹配評估舉例

筆者選取1 萬個原始浮動車數(shù)據(jù)輸入到Hadoop分布式平臺進行匹配計算，圖7為匹配前后某道路的對比圖，圖7(a)為原始浮動車數(shù)據(jù)，圖7(b)為匹配后的浮動車數(shù)據(jù).從圖7中看出：當該系統(tǒng)處理大批量浮動車數(shù)據(jù)時，依舊保持較高的準確度.

圖7　對1萬個數(shù)據(jù)點進行匹配前后部分對比圖Fig.7　Effect diagramof matching the ten thousand data points

同時，選取10 萬和20 萬個原始點分別輸入到Hadoop平臺和單機串行平臺中做比較，具體測試結(jié)果如表1所示.從表1看出：當數(shù)據(jù)量小時，單機串行平臺匹配效率更高.這是因為整個分布式平臺前期對網(wǎng)格索引的初始化處理和內(nèi)存的加載耗時，JobTracker會根據(jù)任務配置要求TaskTacker啟動JVM來處理map子任務或者reduce子任務耗時造成.但隨著數(shù)據(jù)量的增大，Hadoop平臺的優(yōu)勢將逐漸體現(xiàn).總體來說原本任務在單機上運行的計算量，通過Hadoop的Mapreduce機制進行有效的分攤.

表1Hadoop平臺和單機串行平臺性能比較

Table 1The comparison of the performance of Hadoop and single machine

浮動車數(shù)據(jù)量/萬條Hadoop分臺處理時間/s單機串行處理時間/s137.2516.001056.4977.322077.13132.26

4結(jié)論

針對海量浮動車數(shù)據(jù)的匹配環(huán)境，設(shè)計了一種基于Hadoop的分布式算法，達到并行處理的效果；設(shè)計了Hashmap網(wǎng)格索引方法，改進了傳統(tǒng)方法下實時性低的問題；通過合理利用高程信息，設(shè)計了高架/非高架算法，改進了傳統(tǒng)方法下處理高架與地面重疊、交疊、平行情形下的不足.實驗結(jié)果表明：筆者的算法在處理海量浮動車數(shù)據(jù)時具備較好的高效性和準確性.

參考文獻：

[1]章威，徐建閩，林綿峰.基于大規(guī)模浮動車數(shù)據(jù)的地圖匹配算法[J].智能交通系統(tǒng)與信息技術(shù),2007,7(2)：39-40.

[2]羅元，謝波，彭衛(wèi)兵，等.基于Vega Prime的虛擬現(xiàn)實車輛智能運動模擬[J].浙江工業(yè)大學學報，2013，41(4)：158-163.

[3]郭海鋒，方良君，俞立.基于模糊卡爾曼濾波的短時交通流量預測方法[J].浙江工業(yè)大學學報，2013，41(2)：218-221.

[4]辛飛飛，陳小鴻，林航飛.浮動車數(shù)據(jù)路網(wǎng)時空分布特征研究[J].中國公路報,2008,21(4):106.

[5]王為，姚明海.基于計算機視覺的智能交通監(jiān)控系統(tǒng)[J].浙江工業(yè)大學學報，2010，38(5)：174-179.

[6]朱麗云，郭繼孚，溫慧敏,等.一種適用于復雜城市路網(wǎng)的浮動車實時地圖匹配技術(shù)[J].交通與計算機，2007,25(6)：82.

[7]TAYLOR G, BLEWITT G. Road reduction filtering using GPS[C]// AGILE.The 3rd AGILE Conference on Geographic Information Science. Helsinki: AGILE,2000:114-120.

[8]吳偉.分布式并行地圖匹配系統(tǒng)研究與實現(xiàn)[D].廣州：中山大學，2012.

[9]XIA Yingjie, LI Yuncai.Quadtree-based domain decomposition for parallel map-matching on GPS data[C]//IEEE.InternationalIEEE Conference on Intelligent Transportation Systems. Anchorage:IEEE,2012：810-812.

(責任編輯：陳石平)

中圖分類號：U12

文獻標志碼：A

文章編號：1006-4303(2015)03-0332-04

作者簡介：郭淑琴(1970—)，女，山西夏縣人，教授，研究方向為光通信技術(shù)，E-mail：guosq@zjut.edu.cn.

收稿日期：2014-12-12