康 軍,2， 郭佳豪， 段宗濤,2， 唐 蕾， 張 凡

(1.長安大學(xué) 信息工程學(xué)院，陜西 西安 710064； 2.陜西省道路交通智能檢測(cè)與裝備工程技術(shù)研究中心，陜西 西安 710064)

城市計(jì)算是一種利用大數(shù)據(jù)技術(shù)解決城市治理問題的新興領(lǐng)域，而軌跡數(shù)據(jù)是城市計(jì)算應(yīng)用中最重要的數(shù)據(jù)源之一[1-2]。隨著相關(guān)問題的產(chǎn)生，以及計(jì)算性能的極大提升，對(duì)大規(guī)模軌跡數(shù)據(jù)的研究非常廣泛。如文獻(xiàn)[3]，第一次利用軌跡數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，分析出出租車司機(jī)普遍存在拒載現(xiàn)象，并且根據(jù)算法估計(jì)出北京市高收入出租車司機(jī)的拒載概率大約為8.25%。滴滴[4]每天有數(shù)百萬司機(jī)為上億用戶提供打車服務(wù)，針對(duì)訂單的分配問題就需要準(zhǔn)確、實(shí)時(shí)的司機(jī)與乘客的位置信息。

為了更好地利用大規(guī)模軌跡數(shù)據(jù)，車輛導(dǎo)航定位等技術(shù)非常重要，而地圖匹配正是車輛導(dǎo)航技術(shù)中的核心技術(shù)之一。目前對(duì)于地圖匹配算法的研究非常廣泛，如文獻(xiàn)[5]提出一種加權(quán)幾何地圖匹配算法，該方法利用水平精度因子、行駛速度、行進(jìn)距離來獲取動(dòng)態(tài)加權(quán)系數(shù)，利用加權(quán)系數(shù)與幾何特征值的乘積來選取匹配道路。文獻(xiàn)[6]和文獻(xiàn)[7]是兩種基于隱馬爾可夫模型的高級(jí)地圖匹配算法，這種方法主要針對(duì)路網(wǎng)復(fù)雜，軌跡采樣頻率低等復(fù)雜場(chǎng)景下的地圖匹配?，F(xiàn)有的研究主要針對(duì)地圖匹配的精度問題，而數(shù)據(jù)規(guī)模的增大，使得傳統(tǒng)的串行算法不再適用。文獻(xiàn)[8]提出了一種基于Hadoop的分布式地圖匹配算法，但實(shí)驗(yàn)的最大數(shù)據(jù)量為20萬個(gè)軌跡點(diǎn)，數(shù)據(jù)規(guī)模并不是很大。針對(duì)此問題，提出一種基于大規(guī)模軌跡數(shù)據(jù)的并行化地圖匹配算法，并利用基于GeoHash編碼的網(wǎng)格化地圖對(duì)候選道路的選取進(jìn)行了優(yōu)化。實(shí)驗(yàn)使用了大規(guī)模出租車軌跡數(shù)據(jù)，對(duì)比了該算法與文獻(xiàn)[8]的算法對(duì)同規(guī)模軌跡數(shù)據(jù)的運(yùn)行時(shí)間，并參考文獻(xiàn)[9]采用的3種并行計(jì)算的性能比較方式對(duì)本算法進(jìn)行測(cè)試。

1 問題分析

1.1 串行地圖匹配算法

地圖匹配算法主要有基于幾何的地圖匹配算法、基于拓?fù)涞牡貓D匹配算法、高級(jí)地圖匹配算法等。在眾多的地圖匹配算法中，選取一種動(dòng)態(tài)加權(quán)的地圖匹配算法[10]進(jìn)行并行化實(shí)現(xiàn)。該算法準(zhǔn)確率達(dá)到96.7%，并且算法的各個(gè)特征以及權(quán)值系數(shù)計(jì)算過程非常簡(jiǎn)單、易于實(shí)現(xiàn)，非常適合用于解決軌跡數(shù)據(jù)規(guī)模大的地圖匹配問題。

該算法的主要步驟是取候選道路，計(jì)算待匹配點(diǎn)與候選道路的投影距離、航向夾角、軌跡夾角這3個(gè)特征值，再分別計(jì)算每個(gè)特征的權(quán)值系數(shù)，最后加權(quán)求和，選取得分最小的道路作為候選道路，待匹配點(diǎn)在該道路上的投影點(diǎn)為修正后的軌跡點(diǎn)。得分的計(jì)算公式如下：

(1)

式中,di為投影距離;Δθheadi為航向夾角；Δθtraji為軌跡夾角;Wi為投影距離的動(dòng)態(tài)系數(shù);Whead為航向夾角的動(dòng)態(tài)系數(shù);Wtraji為軌跡夾角的動(dòng)態(tài)系數(shù);N為候選路段個(gè)數(shù)。

1.2 網(wǎng)格化地圖

在地圖匹配過程中首先要選取候選路段，然后在候選路段中根據(jù)不同的匹配算法選取最為匹配的路段。文獻(xiàn)[10]中選取經(jīng)緯度的L∞距離作為選取的距離度量，這種方法得到的范圍比歐式距離、曼哈頓距離得到的面積大，可以最大限度地選取候選路段。而此方法需要遍歷整個(gè)路網(wǎng)，由于真實(shí)路網(wǎng)的數(shù)據(jù)量很大，因此這種方法非常消耗時(shí)間。候選路段的選取問題可以抽象為一種空間索引問題。如文獻(xiàn)[11]采用了二級(jí)網(wǎng)格索引，可以將候選路段的搜索進(jìn)行優(yōu)化，但該方法需要將地圖數(shù)據(jù)劃分為兩個(gè)刻度不同的地圖數(shù)據(jù)，索引具體的網(wǎng)格也需要兩次完成。GeoHash[12]是一種有效的地理編碼方式，可以將經(jīng)緯度利用二分法進(jìn)行二進(jìn)制編碼，再用Base32編碼進(jìn)行壓縮。GeoHash將二維的經(jīng)緯度坐標(biāo)轉(zhuǎn)換為一維的字符串編號(hào),每個(gè)編碼代表一個(gè)矩形區(qū)域，編碼的長度決定矩形區(qū)域的大小，這種編碼方式非常適合網(wǎng)格化地圖問題。

原始的西安市地圖是一個(gè)左下角坐標(biāo)為(108.67,33.7)、右上角坐標(biāo)為(109.81,34.75)的矩形區(qū)域。將經(jīng)緯度分別按18位、17位進(jìn)行GeoHash編碼，如表1所示，此時(shí)的經(jīng)緯度誤差均為0.00136，可以將所有路網(wǎng)分割為邊長為0.00136°的矩形區(qū)域。這樣可以把這個(gè)區(qū)域分割為大約840×774個(gè)網(wǎng)格。每個(gè)網(wǎng)格是一個(gè)經(jīng)度邊長為0.00136°、緯度邊長為0.00136°的矩形區(qū)域，且每個(gè)網(wǎng)格剛好可以用一個(gè)GeoHash編碼的字符串表示。

表1 GeoHash編碼精度表

網(wǎng)格編碼過程如下。

① 根據(jù)對(duì)角線上兩個(gè)坐標(biāo)求平均值，可以得到網(wǎng)格中心點(diǎn)的坐標(biāo)；

② 利用二分法將中心點(diǎn)的坐標(biāo)轉(zhuǎn)為二進(jìn)制碼；

③ 將經(jīng)度放在奇數(shù)位，緯度在偶數(shù)位，這樣可將兩個(gè)二進(jìn)制碼合并成一個(gè)二進(jìn)制碼；

④ 最后進(jìn)行Base32編碼，得到最終的網(wǎng)格編號(hào)。

如圖1所示，點(diǎn)C為中間網(wǎng)格的中心點(diǎn)，點(diǎn)C對(duì)應(yīng)的編碼即為該網(wǎng)格的編碼，周圍的道路為Path1、Path2，其余的點(diǎn)為道路上的結(jié)點(diǎn)。

圖1 網(wǎng)格化地圖示意圖

1.3 軌跡數(shù)據(jù)預(yù)處理

原始軌跡數(shù)據(jù)主要包含車牌號(hào)、時(shí)間戳、經(jīng)度、緯度、速度、航向夾角和車輛狀態(tài)等字段。實(shí)驗(yàn)使用的數(shù)據(jù)為西安市出租車軌跡數(shù)據(jù)，采樣間隔為30 s，每輛車每天產(chǎn)生大約2880條軌跡數(shù)據(jù)。所有出租車每天大約產(chǎn)生2 GB左右的軌跡數(shù)據(jù)，最大實(shí)驗(yàn)數(shù)據(jù)約為14.7 GB。

首先需要對(duì)數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗，原始的軌跡數(shù)據(jù)是無序、且含有異常數(shù)據(jù)的。數(shù)據(jù)清洗包括以下幾步：數(shù)據(jù)去重；去除漢字；去除異常軌跡點(diǎn)；按車牌、時(shí)間排序。

在式(1)中參數(shù)Δθtraji為航向夾角特征，在數(shù)據(jù)清洗過程中，需要利用連續(xù)兩個(gè)軌跡點(diǎn)的軌跡距離判斷是否為異常點(diǎn)，這時(shí)可以直接計(jì)算出軌跡夾角，減小后續(xù)匹配的計(jì)算量。

在計(jì)算軌跡夾角之后，對(duì)每個(gè)軌跡點(diǎn)計(jì)算其對(duì)應(yīng)的GeoHash編碼，這個(gè)編碼就是該軌跡點(diǎn)所對(duì)應(yīng)的地圖網(wǎng)格的編號(hào)，這樣可以增強(qiáng)軌跡數(shù)據(jù)的內(nèi)聚性。編碼方式與網(wǎng)格化地圖的編碼方式一致。如軌跡點(diǎn)坐標(biāo)為(108.945652,34.184875)，編碼為wg27cbu，將該編碼也保留在原始數(shù)據(jù)中。

1.4 選取候選路段

當(dāng)匹配一個(gè)待匹配點(diǎn)時(shí)，先用GoeHash編碼計(jì)算該點(diǎn)在地圖中的網(wǎng)格編號(hào)，根據(jù)網(wǎng)格編號(hào)可以查找該網(wǎng)格的路段數(shù)據(jù)，以及周圍的8個(gè)網(wǎng)格的路段數(shù)據(jù)，字典型的查詢時(shí)間復(fù)雜度為O(1)。在進(jìn)行候選路段選取時(shí)，選擇待匹配點(diǎn)周圍9個(gè)網(wǎng)格中的數(shù)據(jù)進(jìn)行遍歷。這樣就把地圖數(shù)據(jù)規(guī)?？s小至原始地圖面積的0.00138%，極大地降低了時(shí)間復(fù)雜度。如圖2所示，小圓圈表示待匹配點(diǎn)，字符串分別表示9個(gè)網(wǎng)格的網(wǎng)格編號(hào)，虛線的網(wǎng)格為最終的候選路段范圍。

圖2 候選道路的選取

2 并行化地圖匹配算法

2.1 Spark介紹

隨著科技的發(fā)展，位置信息很容易被記錄下來，大規(guī)模的軌跡數(shù)據(jù)是城市計(jì)算的重要數(shù)據(jù)來源之一。而Spark等開源的大數(shù)據(jù)平臺(tái)的出現(xiàn)，使大規(guī)模數(shù)據(jù)的計(jì)算更加便捷。將動(dòng)態(tài)加權(quán)的地圖匹配串行算法改為Spark RDD的編程模型，可以快速地完成大規(guī)模地圖數(shù)據(jù)的地圖匹配任務(wù)，為城市計(jì)算等應(yīng)用提供了有力的保證。

2.2 分區(qū)方法

為了使并行計(jì)算更為有效，將網(wǎng)格化的地圖數(shù)據(jù)與帶有網(wǎng)格編號(hào)的軌跡數(shù)據(jù)利用HashPartitioner的方式進(jìn)行分區(qū)。設(shè)軌跡點(diǎn)A的GeoHash編碼為grid，grid的數(shù)據(jù)類型為字串類型，則軌跡點(diǎn)A利用Spark的HashPartitioner分區(qū)器進(jìn)行分區(qū)時(shí)，其分區(qū)編號(hào)key可表示為

key=String.hashcode(grid) modn

(2)

其中，String.hashcode()為字串類的hashcode函數(shù)；mod表示整數(shù)求余運(yùn)算；n表示設(shè)定的分區(qū)數(shù)目。將網(wǎng)格地圖數(shù)據(jù)分配給各個(gè)分區(qū)時(shí)，首先使用如式(2)所示的方法計(jì)算各個(gè)網(wǎng)格所對(duì)應(yīng)的分區(qū)編號(hào)；然后根據(jù)1.4節(jié)的候選路段選取辦法，確定當(dāng)前網(wǎng)格的其他8個(gè)相鄰網(wǎng)格；最后將上述9個(gè)網(wǎng)格對(duì)應(yīng)的網(wǎng)格-路段數(shù)據(jù)分發(fā)給選定分區(qū)。

2.3 算法介紹

如表2所示，并行化地圖匹配算法的輸入為地圖數(shù)據(jù)、預(yù)處理后的軌跡數(shù)據(jù)、分區(qū)數(shù)，輸出為匹配后的軌跡數(shù)據(jù)。

表2 并行化地圖匹配算法

首先將原始的地圖數(shù)據(jù)映射為網(wǎng)格編號(hào)為key的網(wǎng)格化地圖數(shù)據(jù)，再得到軌跡點(diǎn)的網(wǎng)格編號(hào)。然后分別對(duì)地圖數(shù)據(jù)和軌跡數(shù)據(jù)進(jìn)行分區(qū)，將相同key的軌跡數(shù)據(jù)和地圖數(shù)據(jù)進(jìn)行連接，得到該軌跡點(diǎn)對(duì)應(yīng)的候選路段數(shù)據(jù)。并行計(jì)算每個(gè)點(diǎn)對(duì)應(yīng)的每條候選道路的投影距離特征、航向夾角特征、軌跡夾角特征。計(jì)算最終得分，并對(duì)候選路段按得分進(jìn)行升序排列，取出得分最低的候選路段作為最終的匹配路段。最后對(duì)數(shù)據(jù)進(jìn)行重新合并，返回匹配后的軌跡數(shù)據(jù)。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)及環(huán)境

實(shí)驗(yàn)數(shù)據(jù)來源于西安市交通管理部門，為出租車1周產(chǎn)生的軌跡數(shù)據(jù)，數(shù)據(jù)量約2億條。軌跡數(shù)據(jù)的格式以及清洗過程如1.3節(jié)所示。電子地圖數(shù)據(jù)為西安市地圖數(shù)據(jù)，包含2.9萬條西安市城區(qū)道路。

實(shí)驗(yàn)使用的Spark集群包含13個(gè)Worker節(jié)點(diǎn)，252個(gè)Core，每個(gè)節(jié)點(diǎn)32 GB內(nèi)存，總內(nèi)存416 GB。原始數(shù)據(jù)存儲(chǔ)在HDFS平臺(tái)上，運(yùn)行的結(jié)果再保存到HDFS上。Spark的部署模式為Standalone模式，該模式具有容錯(cuò)性，且支持分布式部署等優(yōu)點(diǎn)，適用于真實(shí)場(chǎng)景下大規(guī)模數(shù)據(jù)的計(jì)算。

3.2 算法效率對(duì)比

在相同數(shù)據(jù)規(guī)模下，使用本方法與文獻(xiàn)[8]中的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比，如表3所示。顯然新的方法在性能方面取得了很大的提升，特別是當(dāng)數(shù)據(jù)量增大為20萬條時(shí)，新算法的運(yùn)行時(shí)間為舊算法的44%，比數(shù)據(jù)量小時(shí)性能提升的效果更好。原始方法并沒有在足夠大的規(guī)模下進(jìn)行試驗(yàn)，將數(shù)據(jù)上升至接近3000萬條，新的算法仍然高效。提升至2億余條，仍然可以在短時(shí)間內(nèi)完成匹配，最大數(shù)據(jù)規(guī)模是原始算法最大規(guī)模數(shù)據(jù)(20萬條)的1000倍以上，時(shí)間開銷僅用了其32倍。新的算法更加適合于大規(guī)模軌跡數(shù)據(jù)的地圖匹配問題。

表3 新算法與原算法效率對(duì)比

3.3 并行度優(yōu)化

在并行計(jì)算中，并行度對(duì)計(jì)算的效率有很大的影響，而Spark中分區(qū)數(shù)的選取決定并行度的大小。如果分區(qū)數(shù)過小，有的節(jié)點(diǎn)沒有分配到數(shù)據(jù)，會(huì)造成資源浪費(fèi)。如果分區(qū)數(shù)目太大，計(jì)算過程中各分區(qū)之間的Shuffle很大，也會(huì)降低計(jì)算的效率。分區(qū)數(shù)由100到1000(步長為100)，分別對(duì)同一天的軌跡數(shù)據(jù)進(jìn)行地圖匹配，數(shù)據(jù)量大約為3000萬個(gè)軌跡點(diǎn)，占內(nèi)存2 GB左右，實(shí)驗(yàn)的運(yùn)行時(shí)間測(cè)試結(jié)果如圖3所示。圖中橫軸代表分區(qū)數(shù)，縱軸代表運(yùn)行時(shí)間。由圖中可以看到，當(dāng)分區(qū)數(shù)為500時(shí)運(yùn)行時(shí)間最短，運(yùn)行時(shí)間為5.4 min，比最差的情況少用了38%的時(shí)間。由此可以看出分區(qū)的選取對(duì)于并行計(jì)算的效率影響很大，而不同數(shù)據(jù)規(guī)模最優(yōu)分區(qū)數(shù)不同，在進(jìn)行并行計(jì)算時(shí)可根據(jù)規(guī)模大小對(duì)分區(qū)數(shù)目做一些適當(dāng)調(diào)整。

圖3 不同分區(qū)數(shù)的運(yùn)行時(shí)間

3.4 規(guī)模增長性測(cè)試

隨著數(shù)據(jù)規(guī)模的增大，各個(gè)節(jié)點(diǎn)的負(fù)載會(huì)變大，而且節(jié)點(diǎn)之間的通信量也會(huì)變大，這時(shí)算法的性能會(huì)有所下降。因此，引入規(guī)模增長性這一指標(biāo)，對(duì)規(guī)模增長引發(fā)的并行性能變化情況進(jìn)行測(cè)試，如式(3)所示。

Sizeup(n)=Tn/T1

(3)

式中，T1為一天的數(shù)據(jù)量所需匹配時(shí)間；Tn為n天的數(shù)據(jù)所需匹配時(shí)間。

將1～7天規(guī)模的數(shù)據(jù)量分別測(cè)試運(yùn)行時(shí)間，根據(jù)式(3)進(jìn)行計(jì)算規(guī)模增長性，結(jié)果如圖4所示。顯然，隨著數(shù)據(jù)規(guī)模成倍的擴(kuò)大，規(guī)模增長性接近線性增長，并行算法性能上并沒有太大的下降，穩(wěn)定性比較高。

圖4 不同規(guī)模數(shù)據(jù)的運(yùn)行時(shí)間

3.5 加速比測(cè)試

在并行計(jì)算中，加速比這一指標(biāo)表示隨著節(jié)點(diǎn)數(shù)的增大，并行計(jì)算相對(duì)串行計(jì)算性能上的提高，如式(4)所示。

Speedup(p)=T1/Tp

(4)

式中，Speedup(p)為加速比；T1為單處理器下的運(yùn)行時(shí)間；Tp為P臺(tái)處理器的運(yùn)行時(shí)間。對(duì)不同節(jié)點(diǎn)數(shù)下，測(cè)試同一天軌跡數(shù)據(jù)的匹配時(shí)間。測(cè)試結(jié)果如圖5所示，橫軸代表使用節(jié)點(diǎn)數(shù)，左縱軸代表運(yùn)行時(shí)間，右縱軸代表加速比。隨著節(jié)點(diǎn)的增加，運(yùn)行時(shí)間下降，但下降的趨勢(shì)變慢；加速比在上升，但上升的趨勢(shì)趨于緩慢。這是由于節(jié)點(diǎn)數(shù)增加，節(jié)點(diǎn)之間的通信開銷增大。

圖5 加速比測(cè)試

3.6 可擴(kuò)展性測(cè)試

可擴(kuò)展性由加速比產(chǎn)生，代表著算法性能隨著節(jié)點(diǎn)的增大而提高的能力，如式(5)所示。

Scaleup(p)=Speedup(p)/p

(5)

式中，Scaleup(p)為可擴(kuò)展性；Scaleup(p)/p為節(jié)點(diǎn)數(shù)等于p時(shí)的加速比與節(jié)點(diǎn)數(shù)p的比值。測(cè)試結(jié)果如圖6所示?？梢?，隨著節(jié)點(diǎn)的增加，可擴(kuò)展性在緩慢降低。

圖6 可擴(kuò)展性測(cè)試

4 結(jié)束語

提出了一種基于大規(guī)模軌跡數(shù)據(jù)的并行化地圖匹配算法。在候選道路的選取中采用了一種基于GeoHash編碼的網(wǎng)格化地圖方法，將候選道路查詢的時(shí)間復(fù)雜度下降了一個(gè)量級(jí)。采用Spark平臺(tái)，實(shí)現(xiàn)了一種并行化的動(dòng)態(tài)加權(quán)地圖匹配算法。經(jīng)試驗(yàn)測(cè)試，該算法可以短時(shí)間內(nèi)完成大規(guī)模數(shù)據(jù)的地圖匹配任務(wù)，且穩(wěn)定性高，具有良好的可擴(kuò)展性。在很多真實(shí)應(yīng)用場(chǎng)景下，地圖匹配需要具有實(shí)時(shí)性。因此，下一步的研究應(yīng)該將批處理方式改進(jìn)為流處理，使該算法得到更加廣泛的應(yīng)用。