隱馬爾可夫模型路網匹配的MapReduce實現

陸　健　王　鵬

(復旦大學計算機科學技術學院　上海 200433)

0　引　言

隨著科技發展，傳感器尤其是位置傳感器已經可以出現在幾乎所有的可移動設備上。現在市面上的大部分家用汽車幾乎都裝載有GPS導航器，通過GPS，人們可以相對準確地了解自己所處的位置，導航軟件基于此給予司機最優的道路選擇。

GPS就是將物體當前在地球上的坐標(對于地面上的物體來說，即為二維經緯度坐標)測量出來。對于在道路中通行的汽車來說，尤其在路網密集的城市地區，一個二維坐標具體在城市的哪條道路上至關重要，在距離很小的范圍內的不同道路能通達的方向可能完全不同。將GPS數據映射到一個更為準確合理的道路上去是大部分基于軌跡信息計算的一個基礎。這也就是常說的路網匹配算法。路網匹配算法可以分為兩個大類——增量算法和全局算法。前者對每一個新讀到的軌跡點坐標立即產生一個匹配結果，不考慮后續的軌跡點數據，后者則對整個軌跡數據進行整合分析。前者更好地處理日常類似汽車導航的實時應用，如果對準確性要求更高，則一般考慮使用全局算法。

城市規模的擴大及新型交通模式，網約車的誕生，手機地圖交通類APP的普及，乃至呼之欲出的自動駕駛汽車，定位和導航需求變得越來越集中化，為數據的大規模集中提供可能的同時，也對研究城市的路網規劃，或者道路擁擠情況的調查帶來了便利，這種研究會獲得數量巨大的軌跡數據。類似這些對于大規模軌跡數據的路網匹配工作，實時性不是一個重要的考量，效率和準確性是這種離線路網匹配場景更要考慮的問題。在這種情況下要優先地考慮準確性更好的全局算法。我們稱呼這種已經獲得軌跡完整數據的路網匹配工作為離線路網匹配。

并行計算框架的使用可以提高大規模數據計算的效率并節約編碼成本。現時已經有一些研究著力于使用MapReduce框架來實現大規模軌跡數據的離線路網匹配，使用分而治之的思想簡化計算的同時，減少對其他資源的使用，減少I/O開銷。但全局路網匹配算法顧名思義是要通過全局考量整個軌跡，這與MapReduce分而治之是一個根本性的矛盾。另一方面，由于地區的不同、路網的密集程度、汽車的使用量不論在世界的哪一國家都有著明顯的差異，對于MapReduce框架來說，基于地理位置的分而治之很容易造成工作流和I/O流的不平衡問題，這對計算效率有著很大的問題。這些問題都使得繼續對使用分布式計算框架進行離線路網匹配的討論變的很有意義。

本文為了克服前述兩種需求的潛在矛盾，提出了全新的基于MapReduce和隱馬爾可夫模型的路網匹配框架。主體包括：

(1) 分布式計算隱馬爾可夫模型的框架分布式路網匹配和傳統全局匹配相比主要的缺陷是分而治之和全局最優求解的矛盾。將軌跡按照地理位置排序的結果是將軌跡打碎丟失前后連接信息。本研究將軌跡拆分為一段段長度限定的線段，將分布式處理的線段在最后整合起來，得到全局最優解。而這都基于路網匹配的隱馬爾可夫模型。隱馬爾可夫模型是路網匹配工作中非常流行的全局算法，它有著直觀準確且抗噪聲能力強大的特點。我們的研究通過將這個算法實現在MapReduce上來實現分布式計算和全局算法的平衡。

(2) 大規模地圖數據的分組預處理系統當要讓路網匹配在一個較大的地圖空間內運行時(如全中國)，對于地圖文件的預處理并不是一件容易的事情。基于地理位置的正方形分區是極為常用的地圖文件組織形式，但在正方形邊長和文件數量上有著難以調和的矛盾，進一步將地圖分區按照地理位置分組會帶來文件I/O和匹配操作負載不均衡的問題。我們提出了一個新的大規模地圖數據分組預處理系統，通過地圖冗余、隨機分組和緩沖區的應用，將混雜的地圖數據進行分區分組，保證匹配的正確性和負載均衡。

1　背景知識

1.1　已有的路網匹配算法

大多數現存的路網匹配算法使用各種權值算法從候選點中決定正確的位置[1-3]。權值可以由很多信息來決定，比如GPS信號到候選點的距離，當前的前進方向，道路的拓撲結構，物體的瞬時矢量速度以及前序后續的GPS信號。雖然有的軌跡數據可以在GPS信號以外提供前述的其他信息，但為了滿足算法的通用性，包括我們的研究在內，大部分研究都集中于僅有時間和GPS信號的軌跡數據。

權值算法主要分為兩類：增量算法和全局算法。增量算法例如文獻[4]和文獻[5]，它們每次讀入一個最新的軌跡數據，根據且只根據包括這個新輸入在內的所有已知軌跡點來確定新數據對應所有候選點的權值。增量算法由于可以實時地給出匹配的結果，被廣泛地用于實時應用場景，例如汽車導航。但當采樣率比較低的時候，匹配準確率下降非常顯著，也難以應付城市路網的復雜環境。

全局算法例如文獻[6]和文獻[7]則將一整段軌跡數據進行整體分析，所以可以將后續數據一并利用來確定每一個點的最佳選擇。在不大規模增加時間復雜度的情況下，離線路網匹配使用全局算法又能獲得更加準確的匹配結果[8]。

1.2　分布式路網匹配算法

MapReduce是一個運行在集群上的并行，分布式處理和生成大規模數據的計算框架和它的相關實現[9]。在Huang等的研究中，提出了將MapReduce應用到路網匹配的工作當中去[10]。方法是使用兩次MapReduce。第一次MapReduce的Map函數讀入分布式文件系統中的軌跡數據，將軌跡先拆分成單獨的軌跡點對所有的軌跡點定位其所屬的地圖分區，以地圖分區編號作為key輸出鍵值對，這樣經過shuffle機制，每個Reduce程序只需讀入一次相應的地圖文件就可以完成所有來自不同軌跡但同屬于一個地圖分區的所有點的匹配操作，輸出所有在范圍內的候選道路。在第二次MapReduce中將屬于一個軌跡的所有軌跡點的匹配結果通過shuffle機制重歸到一個Reduce程序當中排序并進行最優路徑求解。這個框架的確成功地將MapReduce應用到分布式路網匹配上，但由于將軌跡分開匹配，匹配結束后只輸出候選道路的編號(或道路名)和匹配距離，道路連通性這一在路網匹配中重要的元素無法被考慮在內。另外，由于地理上的不均衡分布，按照地理位置的分布式計算一定會有負載不均衡的問題。

1.3　基于隱馬爾可夫模型的路網匹配

隱馬爾可夫模型HMM(Hidden Markov Model)是一個描述一個含有隱含未知參數的馬爾可夫過程統計模型，其數學模型由Baum等[11]發展出來。Newson等在文獻[12]中提出了將隱馬爾可夫模型應用到路網匹配當中去。做法是將軌跡點作為HMM模型的觀察集，軌跡點的候選道路投影作為HMM求解的對象——隱狀態(實狀態)。使用信號誤差計算發射概率，用路徑差值求解轉移概率。隱馬爾可夫模型是路網匹配工作中非常流行的全局算法，它有著直觀準確且抗噪聲能力強大的特點。

定義1軌跡是一個移動的物體在地理空間內移動生成的路徑。一般由一連串按照時間排列的點構成。例如：p1,p2,…,pn，其中的每一個點有一組空間坐標(x代表經度，y代表緯度)和時間戳t構成。

T:{p1,p2,…,pn}

pi=〈xi,yi,ti〉，t1

路網是地圖上所有道路的集合，一般用無向圖R=〈V,E〉表示。V為路網中由兩個端點間的直線段代表的道路集，抑或稱作線段集(在下文中，兩詞意義相同)，E是所有直線段的端點集。

定義2路網匹配可以看作一個以軌跡序列為輸入和輸出的函數。令Tn代表長度為n的軌跡，則定義基于路網R的路網匹配如下：

MR為映射：

一般來說，路網匹配的難點是如何選擇軌跡點對應的多個候選道路。

定義3點p到道路v的距離D(p,v)是v上任意一點到p的最短距離。

D(p,v)=min(d(p,pv))pv∈v

式中:pv是v上任意一點。d為地圖上兩點的大圓距離。

定義4點p到道路v的投影Pp,v是v上到p距離最近的點。

一般來說，在路網匹配中，將軌跡點到附近道路的投影作為候選點。使用隱馬爾可夫模型求解路網匹配的核心是求解候選道路投影表現出觀測軌跡點的發射概率和軌跡點候選的道路投影序列前后的轉換概率。前者描述汽車處于某條候選道路上被觀測到已知軌跡點的可能性，后者描述汽車在前后兩個候選道路間行駛并被觀測到已知軌跡序列的可能性。

顯然，發射概率反映了軌跡信號的誤差，理應隨候選道路投影s到觀測值o的距離變大而減小。我們假定其概率分布為標準正態分布。

(1)

式中:σ為GPS測量誤差的標準差。

(2)

2　基本構想

2.1　分段匹配

同前作[10]一樣，分布式處理的意義仍然是通過拆散軌跡分散到各個地圖的塊來集中匹配以達到集中匹配減少I/O操作的目的。但將軌跡分而治之的想法與離線路網匹配的最初目標——更高的準確性。因為如前一章所述，將已匹配的點重新聚合在一起無法知道前后兩點的候選道路的連通性。而忽略連通性的路網匹配無法應對城市復雜路網。

故我們提出，為了能讓軌跡的匹配考慮道路的連通性，在根本上與前作的點匹配不同，我們將軌跡數據進行碎片化，進行段匹配。第一個MapReduce的Map函數不再是簡單地將每個軌跡的每個點單獨作為value值發射，而是將一對前后連續的軌跡點(pi,pi+1)作為value值發射。

而在之后的Reduce操作中，路網匹配不只是在路網中尋找距離接近的道路作為候選道路記錄在匹配結果序列里以待第二次MapReduce整合。對于Map給出的點對(pi,pi+1)不僅要給出這兩個點的所有候選道路及其距離(這在隱馬爾可夫路網匹配模型里代表了發射概率)，還要給出所有前后兩個軌跡點在兩個候選道路集對應的所有投影點之間的最短路徑長度(對應隱馬爾可夫模型中的轉移概率)。通過這種方式，維特比算法中需要概率模型就被完全計算清楚了。在第二次MapReduce的Reduce中，被排序規整到同一軌跡序列后，就可以執行動態規劃算法，計算概率最大的可能路徑，給出匹配結果。

2.2　地圖冗余

實現上一節所述的軌跡段匹配，難度要比以前的點匹配大得多，因為不同于點匹配的對象，段匹配的對象是一對點，必然出現很多時候軌跡的連續兩個點事跨越不同的分區邊界的情況。而由于我們不僅要匹配軌跡點對應的候選道路，還要在路網中計算候選道路投影間的最短路徑。所以，我們要保證一對連續的軌跡點要在同一個地圖分區內都被匹配到。當這樣的軌跡段的長度有限時，我們可以通過對地圖分區做冗余來保證這一點。地圖冗余具體來說包括如下的兩項：

(1) 處于分區邊界的道路道路本身可能會貼近邊界，那么落在一個分區內的軌跡點很有可能需要跨區域匹配到邊界附近的道路，所以將邊界附近的道路重復存儲顯然是必要的。

(2) 長度較長跨網格的道路一些道路本身比較長且道路筆直，在路網中使用較長的線段表示，而且由于正方形分組的頂點位置為四區交界，很容易出現道路跨區域的情況。如果想要匹配能在一個區域內完成就必須要將跨區域的道路重復存儲在不同的分區當中。

2.3　隨機地圖分組

當要處理的地圖規模很大(例如全中國)時，如何用文件保存數量龐大的正方形地圖分區會成為一個問題。地圖分區的邊長基于匹配的需要不能很大，否則分區內道路很多嚴重影響匹配效率。當地圖的數據規模很大時，地圖分區的數量很大，所以必然需要將分區進行分組。

而地圖數據和軌跡數據基于位置相鄰的分組不可避免地會出現偏斜，比如城市擁有更密集的路網，城市有更大的汽車保有量，市中心的道路會比郊區更加擁堵。所以對于按照等面積分區的地圖文件組織方式，軌跡的匹配必然會遇到負載不均衡的情況，具體來說，會體現在以下兩點：

(1) 不同地圖分區的I/O效率不同，浪費I/O資源。

(2) 不同地圖分區的匹配任務負載不同。

MapReduce任務需要等待最慢的一個Reduce的完成。

而只要地圖的劃分是基于地理的接近，就沒有辦法打破這種數據分布的不均。所以，我們提出了將地圖按方形切割的前提下將地圖分區隨機打亂再整合成較大的分組，每個Reduce從對應一個分區到對應一次分組，I/O操作直接調取整個分組內的所有地圖分區。

如圖1所示，不同的分組由不同的顏色灰度和格子編號字體的不同來區分(前四個分組灰度不同，最后一個使用斜體和下劃線)。兩個灰色輪廓橢圓為交通流量的密集區域(也同樣是路網數據的密集區域)，雖然地圖被網格等分開來，但相鄰的組并不一定要在一個分組內。可以看到右側的統計，每個分組之內的密集流量匹配區域數量是大體一致的，這種機制不僅讓每次I/O獲得的地圖數據大小基本一致，也讓即使偏斜度很大的軌跡數據的計算強度得到了均勻。

圖1　地圖分區和地圖分組

2.4　軌跡插點

我們之前的討論都基于一個假設，那就是軌跡的長度都在一個可控的范圍之內。根據這種假設，當對地圖做切割的方塊大小足夠大的時候(譬如邊長達到2千米)，我們可以在其邊界上加上一定的冗余，讓到正方形中心距離在更大范圍內的邊也納入這個分區。

但對于長度較長的軌跡段，長度超過可以接受的范圍時，即使地圖冗余也終究無法匹配一個越界的軌跡段。所以，我們將軌跡進行插值切割，以分割成長度小于一定閾值的軌跡段。對于長度較大的軌跡段的插值不可避免地會引入誤差，畢竟汽車在兩個軌跡點之間的運動不必然是接近直線的，但由于：

(1) 隱馬爾可夫模型是一個對軌跡誤差容忍度很高的模型。

(2) 在軌跡數據時間間隔接近不變的前提下，長度較長的軌跡段，往往暗示汽車的行駛速度非常高，也就是說，在這段軌跡中會較少出現曲折。

所以，我們采用了前后兩點線性平均分的切割方法，至于采取更復雜的插點分割方法，例如根據前后序列的方向使用曲線擬合插值，或者使用前后方向相交點的插值，我們留作將來繼續討論研究。

綜上所述，在這些機制下，我們保證了在將一個軌跡段進行必要的插值切割后，其中的每一個軌跡段，都一定可以在一個正方形網格地圖塊內完成。

3　系統架構

3.1　系統框架

本系統大致分為兩個預處理模塊和MapReduce模塊，如圖2所示。一個預處理模塊對軌跡數據進行去噪聲和軌跡分割，將預處理的數據存于分布式文件系統或者分布式數據庫中等待匹配。另一個預處理模塊對大規模地圖數據的分區分組。對于我們的系統來說，地圖預處理使得對于大規模軌跡數據在大規模地圖空間下的路網匹配成為可能的同時，確保各個地圖分組文件的大小基本一致，匹配的I/O操作負載和計算負載得到均衡。MapReduce的前半模塊執行碎片化軌跡和軌跡預匹配過程，也就是對于軌跡進行分而治之，將軌跡打碎后按照地理位置的不同分組，再分配到相應的組內進行路網匹配。后半模塊執行第二次MapReduce的匯總和軌跡生成，將匹配到候選道路的軌跡點重新按照軌跡聚集起來，計算最有可能的路網匹配結果。

圖2　系統框架

3.2　工作流程

接下來簡述整個基于MapReduce和隱馬爾可夫模型的路網匹配的工作流程。算法整體分為兩個階段。第一個階段為數據預處理，在該階段，我們將地圖和軌跡進行預處理。第二個階段包含兩個MapReduce作業，完成對一個批次的軌跡數據的路網匹配。

首先，在系統準備階段，由地圖預處理系統將整個地圖數據讀入。將路網按照網格存儲到不同的分區當中，對于網格的邊界和跨越網格的道路，則將它們冗余存放到多個相關分區當中去。隨后，將大量的網格隨機分組到一個小數量級的分組內，任何一個分區進入任何一個分組的概率都是隨機均勻分布。將得到的地圖分組以一個文件的形式存儲于文件系統中。

軌跡數據首先要經過預處理，首先將軌跡數據以停留點作為中斷分割開來，以車牌號連接軌跡開始時間作為數據的主鍵，以連續的軌跡點坐標作為值存入分布式文件系統或者分布式數據庫例如Hbase。在這個工作中，還用了簡單的速度規則去除了異常軌跡點。

之后進行MapReduce計算，在第一次MapReduce過程中，Map程序從文件系統中讀入網格劃分的映射表。從分布式文件系統或者分布式數據庫中讀取每一條軌跡，以先后順序掃描軌跡，當前后兩點的距離小于閾值時，直接定位前后兩個點中點所在的網格編號，在網格劃分映射表中找到網格所在的分組號作為鍵，軌跡段序號和軌跡段本身作為值輸出。

在Reduce中，從分布式文件系統中讀入鍵值對應的這個分組下所有分區的地圖數據。對于每一段軌跡碎片，讀入對應的地圖數據進行匹配計算：1) 前后兩點所有的路網候選投影;2) 前后兩個候選投影集之間的最短路經。以軌跡碎片所在軌跡id為鍵，以軌跡碎片id，軌跡碎片兩端點的所有候選投影和所有轉移距離作為值輸出。

在第二步MapReduce中，以前一步Reduce的輸出作為讀入。Map程序不改變鍵值對的內容。經過shuffle，Reduce程序將鍵對應的軌跡的碎片段匹配結果匯總起來，通過已經算出的候選路網投影和候選投影間的最短路徑計算維特比算法中的轉移概率發射概率，最后計算出最可能的路徑。

4　地圖預處理

4.1　地圖分區

基于正方形網格劃分，我們討論如何保證網格包含所有落在網格內的有限長度的軌跡碎片在原地圖數據中匹配到的候選路段。

定義5軌跡碎片

對于軌跡P:{p1,p2,…,pn}

軌跡碎片segi=(pi,pi+1),1≤i≤n-1，pi,pi+1分別是軌跡碎片的兩個端點。對于軌跡碎片的兩個端點，它們在臨近道路上的投影是路網匹配結果的候選項，也就是隱馬爾可夫模型里的隱狀態。

定義6線段距離和線段投影

對于點p和線段v的線段距離：

即線段距離點p到線段v任意一點的最短距離。取到最短距離的點e即為線段投影Proj(p,v)。

如圖3所示,點p到線段(也就是道路)v的投影和p點到道路v所在直線投影的區別就是當點p到線v段所在的直線投影不在線段v上時，線段投影會取被投影線段v兩個端點中離p更近的作為線段投影的結果。

圖3　線段距離和線段投影

對于距離閾值D及地圖R=〈V,E〉，定義一個點的候選道路集。

定義7候選道路集：C(p)={v∨d(p,v)

D代表了一條道路可能是軌跡點對應的候選道路的最大距離閾值。

定義8對于我們的匹配對象軌跡碎片來說，定義軌跡碎片的候選道路集C(segi)為兩個端點候選道路集的并：

C(segi)=C(pi)∪C(pi+1)

我們將任意一個正方形地圖分區標記為B，對應的分區中心c，正方形邊長為α。設有軌跡碎片集合SG，mid(seg)為軌跡片段的中點。

證明：顯然，從c到軌跡片段中心，從軌跡片段中心到軌跡端點，從軌跡端點到候選道路的線段投影構成了一條從c到候選道路v的通路，由線段距離的定義，這條通路的長度一定大于等于線段距離。所以由：

得證。

地圖分區對地圖里的所有道路都要檢查其離附近的地圖分區中心距離是否小于閾值，臨近分區的數量和道路長度成正比，地圖大小|R|，道路平均長度為|v|為所以時間復雜度為O(|R||v|)。

4.2　地圖分組

為了將讀地圖的I/O負載和路網匹配的工作負載均勻地分布在集群的機器上，我們將地圖分區隨機分布到數量級小很多的地圖分組里去。實現方法是依編號遍歷所有網格，對于給定的地圖分組數量N，生成一個1～N-1的隨機數k，并將這個網格添加到k號分組Gk之內，并保存這個網格序號到分組序號的映射關系到地圖分組映射表MapR之內，映射表對于分區編號的映射結果就是分區所屬的分組號，即：

對于地圖分組，要將所有地圖分區掃描一遍。計算復雜度為O(|grid|)，|grid|為分區數量。

5　基于MapReduce的隱馬爾可夫模型

5.1　軌跡碎片化和分布式匹配

第一次MapReduce的Map程序完成對大規模軌跡數據的碎片化并分發到各個Reduce進行路網匹配。

‖seg‖l～

段在進行定位。

定位碎片段分為兩步，如圖4所示。首先計算軌跡碎片中點落于哪個地圖網格。計算得到網格編號gridNo后(在圖中由數字57表示)，再讀取之前地圖預處理時保存的映射文件MapR(圖1)，查詢到這個網格所處的分組號groupNo=MapR(gridNo)(在圖中以分組顏色表示)。對于來自軌跡編號trajNo的第i軌跡碎片segi:(pi,pi+1)，使用碎片中點mid(segi)查詢到屬于網格編號gridNo，和網格所處分組號groupid。Map程序的輸出為：

Key：groupNo

Value：gridNo，trajNo，i，pi，pi+1

圖4　碎片段定位

Map程序會將鍵值相同的鍵值對集中起來發射出去。而一個Reduce程序收到且只收到所有鍵值擁有同樣的鍵值對。Reduce根據這個唯一的鍵也就是一個地圖網格組的分組號groupid，從分布式文件系統中讀取這個組的地圖數據。其中包括所有落在這個組內的所有地圖網格。之后對于收到的值序列：gridNo，trajNo，i，pi，pi+1，根據gridNo讀出分組GgridNo中在這次匹配中需要利用的地圖分組Bgridid。在這個分組中遍歷所有的道路，將距離點坐標pi:(xi,yi)和pi+1:(xi+1,yi+1)距離小于距離閾值D的道路v和對應的線段投影Proj(p,v)組成值對：〈v,Proj(p,v)〉，添加到前后兩點的候選道路集backCandidate，forwardCandidate。之后依據組內的地圖信息和最短路算法計算前后兩個候選道路集的線段投影間的最短距離，存入連接結果集合Route，如果在圖中沒有連接通路，則記錄不能連通標志“unlinked”。Route集合顯然應該有|backCandidate|×|forwardCandidate|個元素。Reduce的計算結果要作為第二次MapReduce的輸入，第二次MapReduce的目標是把軌跡碎片重新拼接起來，所以需要先將同一段軌跡的碎片帶著同樣的鍵值被shuffle排序并分發到不同的Reduce。所以第一次Reduce的輸出應當如下：

Key:trajNo

Value:i,pi，pi+1，backCandidate，forwardCandidate，Route

5.2　最優求解

第二次MapReduce將碎片化的軌跡重新規整起來，Map將上一次MapReduce的結果讀入并直接輸出，shuffle機制將鍵值相同也就是同一段軌跡的所有碎片聚集到一個Reduce里。

在一個Reduce當中，首先將所有收集到的已匹配碎片進行排序，這里除了軌跡的首尾兩點以外，每個軌跡點都會有兩個候選道路集，在絕大部分情況下，前后候選集都是一致的，所以可以直接合并。之后對于任意軌跡點的候選集中遍歷候選項〈v,Proj(p,v)〗〉，根據式(1)通過候選點v到軌跡點p的距離計算發射概率，再根據式(2)通過Route集合內的最短路徑與前后軌跡點之間的距離差值計算轉移概率。其次計算維特比算法：先前向計算所有可能通路的最大概率，再根據動態規劃的結果反向得到最大概率對應的道路和道路投影的序列。最后要去掉在第一步Map中加入的插值點的匹配結果，輸出完整的匹配結果到分布式文件系統或者分布式數據庫。

6　實　驗

6.1　實驗環境

實驗在一個包含七臺服務器的集群上，每臺服務器硬件配置相同，都擁有64 GB內存，CPU為Intel(R) Xeon(R) CPU E5-2403 v2 @ 1.80 GHz。服務器運行Ubuntu系統，版本號為12.04。Java版本為JDK1.8。集群上運行Hadoop2.7.2。

對于分布式計算的測試在整個集群上進行，對于單機版匹配的對比在其中一臺服務器上進行。

6.2　實驗數據

軌跡數據為一組包含1 402個csv表格文件的軌跡數據，每一個csv表格文件代表一輛汽車在一定時間的行駛記錄。這些文件大小不一，文件總大小為41.5 GB。所有的軌跡都在中國境內行駛。

地圖數據來自OpenStreetMap的開源地圖。分為31個json文件，對應每一個中國大陸省級行政單位。地圖文件總共為3.18 GB。

6.3　地圖預處理

雖然我們討論過地圖預處理階段對地圖進行分區分組的計算復雜度，但事實上預處理階段大部分的時間開銷其實會用在I/O文件的操作上。因為在預處理階段，由于地圖數據很大，而我們需要將地圖分區設置得比較小(否則在匹配的過程中每匹配一條道路，相應的一個分區的道路需要被全部遍歷來計算點到道路的距離，非常耗費時間)，整個地圖分區的文件數量就會大得驚人。如表1所示，將整個中國作為地圖范圍的話，由于分區數量反比于邊長的平方，隨著分區的邊長(以經緯度表示)的減小，分區數量增長地很迅速。0.02的經緯度邊長相當于正方形邊長大約在2.2千米的分組。

表1　分區邊長與分區數量

由于沒有辦法將所有分區全部存儲在內存中進行分組，我們就需要將5.1節獲得的所有分區以文件的形式存儲下來。而分區數量過多無法用單一文件存儲(文件數量和I/O操作太大)，我們將序號相連的分區存儲到一個分區集合中去作為緩沖，在進行5.2節的地圖分組過程中在遍歷這些文件來讀取地圖分區。我們將每個集合包含的分區數量設定為相同，記為F。

另一方面，道路在地圖數據中存在的順序是混亂的，在道路確定分區的過程中要使用緩沖區暫時保留一定的讀寫任務，使得對于分區集合的一次讀寫能寫入更多的道路，不然，對于分區的集合式文件讀寫會使得I/O負擔加重。以下以只處理河南省的地圖為例。我們將正方形分組的經緯度邊長固定在0.02。這樣，整個河南省地圖會產生87 904個地圖分區，我們測試不同的分區集合包含分區的數量F和緩沖區Buffer大小(一次讀寫存儲道路的數量)對預處理時間的影響。

如圖5測試結果所示，不同的折線代表不同緩沖區大小，橫軸代表分區集合大小的變化，縱軸是耗時變化。顯然緩沖區越大，折線越處于低位，也就是耗時最短，寫入緩沖區一定能使預處理的時間縮短，在內存允許的情況下應盡量加大緩沖區。而分區集合的大小則要更加復雜，顯然過小的分區集合使得文件變多，I/O次數比較大，在x軸右側的耗時隨著分區集合大小的縮小快速增長。而分區集合特別大時，文件本身數量已經很少，減少文件數量帶來的I/O開銷的降低并不明顯，由于道路在地圖數據中本身有區域的偏斜，可能在一段時間內處理的道路恰巧只在某幾個分區集合當中不涉及大部分的文件。也就是說集合分區數量F過大甚至會導致更多不必要地圖分區在一個文件I/O中被一并讀取，使得時間開銷更大，當緩沖區小的情況下這種情況更容易觀察到。

圖5　地圖預處理時間

6.4　計算效率

盡管基于隱馬爾可夫模型的路網匹配有著高精度的特征，但是運算速度慢是其一個很根本的特點。以往基于隱馬爾可夫模型路網匹配所研究的數據集和地圖文件大小都在一個非常小的范圍內[12-13]。為了證明我們的實現加快了匹配的效率，我們之后在單臺機器上對同樣的數據集進行單機版的匹配，并和集群比較效率。

圖6展示了在分區邊長分別在0.01和0.02經緯度下的匹配時間。可以看到集群的運算耗時大致和輸入的軌跡點數量呈正比(這里列舉的軌跡點數量分別為隨機抽取的0.1%、0.2%、0.4%、0.8%的總軌跡數據，即數據量以2的指數增長)。而根據增長趨勢估算，集群的處理數據效率為每秒3 300個數據點。

圖6　匹配時間

還可以看到，在地圖覆蓋范圍不變的情況下，分區邊長對匹配效率的影響很大。分區邊長增大，則分區數量減少，能加快地圖預處理速度，但在路網匹配時，需要遍歷整個分區的道路來確定候選集合，也就是更大的分區對應更慢的匹配速度。0.01經緯度邊長的地圖分區匹配效率要比0.02經緯度邊長匹配效率平均快上一倍以上。但分區會使得預處理更加困難，占用更多內存，大部分情況下，為了匹配速度的對于大規模軌跡數據匹配的持續獲利，屬于一次性開銷的地圖預處理時間的增長是可以接受的。

由于不知道合適的并行度，要估計對等情況下本地隱馬爾可夫路網匹配的效率則更加復雜，我們需要對單機先進行并行度負載測試。并行度指在一臺機器上運行多少個相同的匹配進程我們要測試并行度在單機上最高可以達到多少。結果如表2所示，第一列表示單臺機器上運行的同樣的路網匹配進程數量，第二列表示這些進程的平均處理速度，第三列表示在相應的單擊并行度下偽集群的整體效率。這里第三列對應于我們7個節點的Hadoop集群，我們模擬一個7個節點的偽集群，效率由單節點效率(也就是并行度乘以單進程平均處理速度)乘以7獲得。可以看到，當并行度剛剛增加的時候，單進程處理速度反而會變快，這可能是因為多個進程讀寫硬盤的過程中會利用到其他進程讀寫的磁盤緩存，使得整體效率提高。但隨著進程進一步增長，系統變得很難處理如此頻繁且分布未知的隨機文件讀寫，所以效率并不能隨著并行度一直上升。當并行度達到7左右時，2 500軌跡點/秒大約就是效率的頂峰。相比之下，我們可以得出結論，我們的系統在大規模數據上可以給出相比于本地匹配30%～40%的效率提升。

表2　單機版隱馬爾可夫匹配效率

6.5　分布式特性

負載均衡的情況在圖7可以非常直觀地看到，最耗時的第一個MapReduce的各個Reducer其中包含基本相等數量的地圖分組，地圖分組又是基于地圖分區隨機劃分的。所以每個Reducer的負載都比較均衡，沒有出現一些Reducer特別快，一些特別滯后的情況。在我們的實驗中，Reducer的平均負載標準差僅為5%。

圖7　各個Reducer的負載

最后我們測試集群節點數量對計算效率的影響，同樣對于0.5%的數據和基于0.01為正方形分組邊長的匹配進行測試，然后嘗試改變MapReduce節點數量。

如表3所示，隨著節點變多，運算時間顯著減少，證明了Hadoop集群的易擴展性可以為運算提速提供很大的方便。在三個節點的情況下，等效單機運算效率已經下降到160條記錄/秒，而單機版在并發度為7時運算效率都超過350條記錄/秒。也就是說，在節點很少的情況，選擇使用Hadoop集群運算隱馬爾可夫模型并不是一個明智的選擇。

表3　節點數量與運算時間

[1] Liu Siyuan, Liu Ce, Luo Qion, et al. Calibrating Large Scale Vehicle Trajectory Data[C]// IEEE, International Conference on Mobile Data Management. IEEE, 2012:222-231.

[2] Ghys K, Kuijpers B, Moelans B, et al. Map matching and uncertainty: an algorithm and real-world experiments[C]// ACM Sigspatial International Conference on Advances in Geographic Information Systems. ACM, 2009:468-471.

[3] Abdallah F, Nassreddine G, Denoeux T. A Multiple-Hypothesis Map-Matching Method Suitable for Weighted and Box-Shaped State Estimation for Localization[J]. IEEE Transactions on Intelligent Transportation Systems, 2011, 12(4):1495-1510.

[4] Civilis A, Jensen C S, Pakalnis S. Techniques for efficient road-network-based tracking of moving objects[J]. IEEE Transactions on Knowledge & Data Engineering, 2005, 17(5):698-712.

[5] Chen Y K, Jiang K, Zheng Y, et al. Trajectory simplification method for location-based social networking services[C]// International Workshop on Location Based Social Networks, Lbsn 2009, November 3, 2009, Seattle, Washington, Usa, Proceedings. DBLP, 2009:33-40.

[6] Alt H, Efrat A, Rote G, et al. Matching planar maps[J]. Journal of Algorithms, 2003, 49(2):262-283.

[7] Brakatsoulas S, Pfoser D, Salas R, et al. On map-matching vehicle tracking data[C]// International Conference on Very Large Data Bases. VLDB Endowment, 2005:853-864.

[8] Zheng Yu. Trajectory Data Mining: An Overview[J]. Acm Transactions on Intelligent Systems & Technology, 2015, 6(3):1-41.

[9] Dean J, Ghemawat S. MapReduce: simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113.

[10] Huang J, Qiao S, Yu H, et al. Parallel map matching on massive vehicle gps data using mapreduce[C]// High Performance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing (HPCC_EUC), 2013 IEEE 10th International Conference on. IEEE, 2013: 1498-1503.

[11] Baum L E, Petrie T. Statistical Inference for Probabilistic Functions of Finite State Markov Chains[J]. Annals of Mathematical Statistics, 1966, 37(6):1554-1563.

[12] Newson P, Krumm J. Hidden Markov map matching through noise and sparseness[C]// Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems. ACM, 2009: 336-343.

[13] Koller H, Widhalm P, Dragaschnig M, et al. Fast hidden Markov model map-matching for sparse and noisy trajectories[C]// Intelligent Transportation Systems (ITSC), 2015 IEEE 18th International Conference on. IEEE, 2015: 2557-2561.