陸　健　王　鵬

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院　上海 200433)

0　引　言

隨著科技發(fā)展，傳感器尤其是位置傳感器已經(jīng)可以出現(xiàn)在幾乎所有的可移動(dòng)設(shè)備上?，F(xiàn)在市面上的大部分家用汽車幾乎都裝載有GPS導(dǎo)航器，通過GPS，人們可以相對準(zhǔn)確地了解自己所處的位置，導(dǎo)航軟件基于此給予司機(jī)最優(yōu)的道路選擇。

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

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

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

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

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

(2) 大規(guī)模地圖數(shù)據(jù)的分組預(yù)處理系統(tǒng)當(dāng)要讓路網(wǎng)匹配在一個(gè)較大的地圖空間內(nèi)運(yùn)行時(shí)(如全中國)，對于地圖文件的預(yù)處理并不是一件容易的事情?；诘乩砦恢玫恼叫畏謪^(qū)是極為常用的地圖文件組織形式，但在正方形邊長和文件數(shù)量上有著難以調(diào)和的矛盾，進(jìn)一步將地圖分區(qū)按照地理位置分組會(huì)帶來文件I/O和匹配操作負(fù)載不均衡的問題。我們提出了一個(gè)新的大規(guī)模地圖數(shù)據(jù)分組預(yù)處理系統(tǒng)，通過地圖冗余、隨機(jī)分組和緩沖區(qū)的應(yīng)用，將混雜的地圖數(shù)據(jù)進(jìn)行分區(qū)分組，保證匹配的正確性和負(fù)載均衡。

1　背景知識(shí)

1.1　已有的路網(wǎng)匹配算法

大多數(shù)現(xiàn)存的路網(wǎng)匹配算法使用各種權(quán)值算法從候選點(diǎn)中決定正確的位置[1-3]。權(quán)值可以由很多信息來決定，比如GPS信號(hào)到候選點(diǎn)的距離，當(dāng)前的前進(jìn)方向，道路的拓?fù)浣Y(jié)構(gòu)，物體的瞬時(shí)矢量速度以及前序后續(xù)的GPS信號(hào)。雖然有的軌跡數(shù)據(jù)可以在GPS信號(hào)以外提供前述的其他信息，但為了滿足算法的通用性，包括我們的研究在內(nèi)，大部分研究都集中于僅有時(shí)間和GPS信號(hào)的軌跡數(shù)據(jù)。

權(quán)值算法主要分為兩類：增量算法和全局算法。增量算法例如文獻(xiàn)[4]和文獻(xiàn)[5]，它們每次讀入一個(gè)最新的軌跡數(shù)據(jù)，根據(jù)且只根據(jù)包括這個(gè)新輸入在內(nèi)的所有已知軌跡點(diǎn)來確定新數(shù)據(jù)對應(yīng)所有候選點(diǎn)的權(quán)值。增量算法由于可以實(shí)時(shí)地給出匹配的結(jié)果，被廣泛地用于實(shí)時(shí)應(yīng)用場景，例如汽車導(dǎo)航。但當(dāng)采樣率比較低的時(shí)候，匹配準(zhǔn)確率下降非常顯著，也難以應(yīng)付城市路網(wǎng)的復(fù)雜環(huán)境。

全局算法例如文獻(xiàn)[6]和文獻(xiàn)[7]則將一整段軌跡數(shù)據(jù)進(jìn)行整體分析，所以可以將后續(xù)數(shù)據(jù)一并利用來確定每一個(gè)點(diǎn)的最佳選擇。在不大規(guī)模增加時(shí)間復(fù)雜度的情況下，離線路網(wǎng)匹配使用全局算法又能獲得更加準(zhǔn)確的匹配結(jié)果[8]。

1.2　分布式路網(wǎng)匹配算法

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

1.3　基于隱馬爾可夫模型的路網(wǎng)匹配

隱馬爾可夫模型HMM(Hidden Markov Model)是一個(gè)描述一個(gè)含有隱含未知參數(shù)的馬爾可夫過程統(tǒng)計(jì)模型，其數(shù)學(xué)模型由Baum等[11]發(fā)展出來。Newson等在文獻(xiàn)[12]中提出了將隱馬爾可夫模型應(yīng)用到路網(wǎng)匹配當(dāng)中去。做法是將軌跡點(diǎn)作為HMM模型的觀察集，軌跡點(diǎn)的候選道路投影作為HMM求解的對象——隱狀態(tài)(實(shí)狀態(tài))。使用信號(hào)誤差計(jì)算發(fā)射概率，用路徑差值求解轉(zhuǎn)移概率。隱馬爾可夫模型是路網(wǎng)匹配工作中非常流行的全局算法，它有著直觀準(zhǔn)確且抗噪聲能力強(qiáng)大的特點(diǎn)。

定義1軌跡是一個(gè)移動(dòng)的物體在地理空間內(nèi)移動(dòng)生成的路徑。一般由一連串按照時(shí)間排列的點(diǎn)構(gòu)成。例如：p1,p2,…,pn，其中的每一個(gè)點(diǎn)有一組空間坐標(biāo)(x代表經(jīng)度，y代表緯度)和時(shí)間戳t構(gòu)成。

T:{p1,p2,…,pn}

pi=〈xi,yi,ti〉，t1

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

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

MR為映射：

一般來說，路網(wǎng)匹配的難點(diǎn)是如何選擇軌跡點(diǎn)對應(yīng)的多個(gè)候選道路。

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

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

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

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

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

顯然，發(fā)射概率反映了軌跡信號(hào)的誤差，理應(yīng)隨候選道路投影s到觀測值o的距離變大而減小。我們假定其概率分布為標(biāo)準(zhǔn)正態(tài)分布。

(1)

式中:σ為GPS測量誤差的標(biāo)準(zhǔn)差。

(2)

2　基本構(gòu)想

2.1　分段匹配

同前作[10]一樣，分布式處理的意義仍然是通過拆散軌跡分散到各個(gè)地圖的塊來集中匹配以達(dá)到集中匹配減少I/O操作的目的。但將軌跡分而治之的想法與離線路網(wǎng)匹配的最初目標(biāo)——更高的準(zhǔn)確性。因?yàn)槿缜耙徽滤?，將已匹配的點(diǎn)重新聚合在一起無法知道前后兩點(diǎn)的候選道路的連通性。而忽略連通性的路網(wǎng)匹配無法應(yīng)對城市復(fù)雜路網(wǎng)。

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

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

2.2　地圖冗余

實(shí)現(xiàn)上一節(jié)所述的軌跡段匹配，難度要比以前的點(diǎn)匹配大得多，因?yàn)椴煌邳c(diǎn)匹配的對象，段匹配的對象是一對點(diǎn)，必然出現(xiàn)很多時(shí)候軌跡的連續(xù)兩個(gè)點(diǎn)事跨越不同的分區(qū)邊界的情況。而由于我們不僅要匹配軌跡點(diǎn)對應(yīng)的候選道路，還要在路網(wǎng)中計(jì)算候選道路投影間的最短路徑。所以，我們要保證一對連續(xù)的軌跡點(diǎn)要在同一個(gè)地圖分區(qū)內(nèi)都被匹配到。當(dāng)這樣的軌跡段的長度有限時(shí)，我們可以通過對地圖分區(qū)做冗余來保證這一點(diǎn)。地圖冗余具體來說包括如下的兩項(xiàng)：

(1) 處于分區(qū)邊界的道路道路本身可能會(huì)貼近邊界，那么落在一個(gè)分區(qū)內(nèi)的軌跡點(diǎn)很有可能需要跨區(qū)域匹配到邊界附近的道路，所以將邊界附近的道路重復(fù)存儲(chǔ)顯然是必要的。

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

2.3　隨機(jī)地圖分組

當(dāng)要處理的地圖規(guī)模很大(例如全中國)時(shí)，如何用文件保存數(shù)量龐大的正方形地圖分區(qū)會(huì)成為一個(gè)問題。地圖分區(qū)的邊長基于匹配的需要不能很大，否則分區(qū)內(nèi)道路很多嚴(yán)重影響匹配效率。當(dāng)?shù)貓D的數(shù)據(jù)規(guī)模很大時(shí)，地圖分區(qū)的數(shù)量很大，所以必然需要將分區(qū)進(jìn)行分組。

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

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

(2) 不同地圖分區(qū)的匹配任務(wù)負(fù)載不同。

MapReduce任務(wù)需要等待最慢的一個(gè)Reduce的完成。

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

如圖1所示，不同的分組由不同的顏色灰度和格子編號(hào)字體的不同來區(qū)分(前四個(gè)分組灰度不同，最后一個(gè)使用斜體和下劃線)。兩個(gè)灰色輪廓橢圓為交通流量的密集區(qū)域(也同樣是路網(wǎng)數(shù)據(jù)的密集區(qū)域)，雖然地圖被網(wǎng)格等分開來，但相鄰的組并不一定要在一個(gè)分組內(nèi)?？梢钥吹接覀?cè)的統(tǒng)計(jì)，每個(gè)分組之內(nèi)的密集流量匹配區(qū)域數(shù)量是大體一致的，這種機(jī)制不僅讓每次I/O獲得的地圖數(shù)據(jù)大小基本一致，也讓即使偏斜度很大的軌跡數(shù)據(jù)的計(jì)算強(qiáng)度得到了均勻。

圖1　地圖分區(qū)和地圖分組

2.4　軌跡插點(diǎn)

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

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

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

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

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

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

3　系統(tǒng)架構(gòu)

3.1　系統(tǒng)框架

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

圖2　系統(tǒng)框架

3.2　工作流程

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

首先，在系統(tǒng)準(zhǔn)備階段，由地圖預(yù)處理系統(tǒng)將整個(gè)地圖數(shù)據(jù)讀入。將路網(wǎng)按照網(wǎng)格存儲(chǔ)到不同的分區(qū)當(dāng)中，對于網(wǎng)格的邊界和跨越網(wǎng)格的道路，則將它們?nèi)哂啻娣诺蕉鄠€(gè)相關(guān)分區(qū)當(dāng)中去。隨后，將大量的網(wǎng)格隨機(jī)分組到一個(gè)小數(shù)量級的分組內(nèi)，任何一個(gè)分區(qū)進(jìn)入任何一個(gè)分組的概率都是隨機(jī)均勻分布。將得到的地圖分組以一個(gè)文件的形式存儲(chǔ)于文件系統(tǒng)中。

軌跡數(shù)據(jù)首先要經(jīng)過預(yù)處理，首先將軌跡數(shù)據(jù)以停留點(diǎn)作為中斷分割開來，以車牌號(hào)連接軌跡開始時(shí)間作為數(shù)據(jù)的主鍵，以連續(xù)的軌跡點(diǎn)坐標(biāo)作為值存入分布式文件系統(tǒng)或者分布式數(shù)據(jù)庫例如Hbase。在這個(gè)工作中，還用了簡單的速度規(guī)則去除了異常軌跡點(diǎn)。

之后進(jìn)行MapReduce計(jì)算，在第一次MapReduce過程中，Map程序從文件系統(tǒng)中讀入網(wǎng)格劃分的映射表。從分布式文件系統(tǒng)或者分布式數(shù)據(jù)庫中讀取每一條軌跡，以先后順序掃描軌跡，當(dāng)前后兩點(diǎn)的距離小于閾值時(shí)，直接定位前后兩個(gè)點(diǎn)中點(diǎn)所在的網(wǎng)格編號(hào)，在網(wǎng)格劃分映射表中找到網(wǎng)格所在的分組號(hào)作為鍵，軌跡段序號(hào)和軌跡段本身作為值輸出。

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

在第二步MapReduce中，以前一步Reduce的輸出作為讀入。Map程序不改變鍵值對的內(nèi)容。經(jīng)過shuffle，Reduce程序?qū)㈡I對應(yīng)的軌跡的碎片段匹配結(jié)果匯總起來，通過已經(jīng)算出的候選路網(wǎng)投影和候選投影間的最短路徑計(jì)算維特比算法中的轉(zhuǎn)移概率發(fā)射概率，最后計(jì)算出最可能的路徑。

4　地圖預(yù)處理

4.1　地圖分區(qū)

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

定義5軌跡碎片

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

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

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

對于點(diǎn)p和線段v的線段距離：

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

如圖3所示,點(diǎn)p到線段(也就是道路)v的投影和p點(diǎn)到道路v所在直線投影的區(qū)別就是當(dāng)點(diǎn)p到線v段所在的直線投影不在線段v上時(shí)，線段投影會(huì)取被投影線段v兩個(gè)端點(diǎn)中離p更近的作為線段投影的結(jié)果。

圖3　線段距離和線段投影

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

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

D代表了一條道路可能是軌跡點(diǎn)對應(yīng)的候選道路的最大距離閾值。

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

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

我們將任意一個(gè)正方形地圖分區(qū)標(biāo)記為B，對應(yīng)的分區(qū)中心c，正方形邊長為α。設(shè)有軌跡碎片集合SG，mid(seg)為軌跡片段的中點(diǎn)。

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

得證。

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

4.2　地圖分組

為了將讀地圖的I/O負(fù)載和路網(wǎng)匹配的工作負(fù)載均勻地分布在集群的機(jī)器上，我們將地圖分區(qū)隨機(jī)分布到數(shù)量級小很多的地圖分組里去。實(shí)現(xiàn)方法是依編號(hào)遍歷所有網(wǎng)格，對于給定的地圖分組數(shù)量N，生成一個(gè)1～N-1的隨機(jī)數(shù)k，并將這個(gè)網(wǎng)格添加到k號(hào)分組Gk之內(nèi)，并保存這個(gè)網(wǎng)格序號(hào)到分組序號(hào)的映射關(guān)系到地圖分組映射表MapR之內(nèi)，映射表對于分區(qū)編號(hào)的映射結(jié)果就是分區(qū)所屬的分組號(hào)，即：

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

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

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

第一次MapReduce的Map程序完成對大規(guī)模軌跡數(shù)據(jù)的碎片化并分發(fā)到各個(gè)Reduce進(jìn)行路網(wǎng)匹配。

‖seg‖l～

段在進(jìn)行定位。

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

Key：groupNo

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

圖4　碎片段定位

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

Key:trajNo

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

5.2　最優(yōu)求解

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

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

6　實(shí)　驗(yàn)

6.1　實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)在一個(gè)包含七臺(tái)服務(wù)器的集群上，每臺(tái)服務(wù)器硬件配置相同，都擁有64 GB內(nèi)存，CPU為Intel(R) Xeon(R) CPU E5-2403 v2 @ 1.80 GHz。服務(wù)器運(yùn)行Ubuntu系統(tǒng)，版本號(hào)為12.04。Java版本為JDK1.8。集群上運(yùn)行Hadoop2.7.2。

對于分布式計(jì)算的測試在整個(gè)集群上進(jìn)行，對于單機(jī)版匹配的對比在其中一臺(tái)服務(wù)器上進(jìn)行。

6.2　實(shí)驗(yàn)數(shù)據(jù)

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

地圖數(shù)據(jù)來自O(shè)penStreetMap的開源地圖。分為31個(gè)json文件，對應(yīng)每一個(gè)中國大陸省級行政單位。地圖文件總共為3.18 GB。

6.3　地圖預(yù)處理

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

表1　分區(qū)邊長與分區(qū)數(shù)量

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

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

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

圖5　地圖預(yù)處理時(shí)間

6.4　計(jì)算效率

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

圖6展示了在分區(qū)邊長分別在0.01和0.02經(jīng)緯度下的匹配時(shí)間?？梢钥吹郊旱倪\(yùn)算耗時(shí)大致和輸入的軌跡點(diǎn)數(shù)量呈正比(這里列舉的軌跡點(diǎn)數(shù)量分別為隨機(jī)抽取的0.1%、0.2%、0.4%、0.8%的總軌跡數(shù)據(jù)，即數(shù)據(jù)量以2的指數(shù)增長)。而根據(jù)增長趨勢估算，集群的處理數(shù)據(jù)效率為每秒3 300個(gè)數(shù)據(jù)點(diǎn)。

圖6　匹配時(shí)間

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

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

表2　單機(jī)版隱馬爾可夫匹配效率

6.5　分布式特性

負(fù)載均衡的情況在圖7可以非常直觀地看到，最耗時(shí)的第一個(gè)MapReduce的各個(gè)Reducer其中包含基本相等數(shù)量的地圖分組，地圖分組又是基于地圖分區(qū)隨機(jī)劃分的。所以每個(gè)Reducer的負(fù)載都比較均衡，沒有出現(xiàn)一些Reducer特別快，一些特別滯后的情況。在我們的實(shí)驗(yàn)中，Reducer的平均負(fù)載標(biāo)準(zhǔn)差僅為5%。

圖7　各個(gè)Reducer的負(fù)載

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

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

表3　節(jié)點(diǎn)數(shù)量與運(yùn)算時(shí)間

[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.