實時分布式地圖匹配系統的設計與實現

亢 麗，王洪玉

（大連理工大學信息與通信工程學院，遼寧 大連 116024）

0 引言

現今城市化進程越來越快，人們對于交通出行的需求不斷增加，汽車行業也在迅猛發展，2013年汽車產銷量已超過2000萬臺。汽車數量顯著增加的同時也給城市交通造成了巨大壓力，如何有效利用當前道路資源為出行者提供便利，已成為人們關注的焦點。在這種情況下，智能交通系統應運而生。

智能交通系統結合多種高新技術，如通信、信息處理、衛星定位、傳感、控制等，應用在城市道路交通系統中，旨在建立大范圍實時、準確、高效的交通運輸管理系統。通過收集城市交通信息，分析出當前路況的擁堵程度并進行發布，使出行者可及時獲知交通狀況，進行合理的路徑規劃。從20世紀60年代開始，美國、歐洲、日本等國家相繼開始進行智能交通系統（ITS）的研究[1]，20世紀以來，我國也大力投入智能交通系統建設，已在北京、深圳等地試點運行。

交通信息的采集和處理是智能交通系統的第一步，也是基礎性、關鍵性的步驟。獲取交通信息的方式、數量、實時性，處理數據的效率、準確度、魯棒性，信息的流動機制、速度和可靠性等，都決定了智能交通系統性能的優劣。傳統的交通信息采集方法主要為定點式采集，如地理式線圈檢測器、視頻檢測等。而浮動車采集技術因其具有覆蓋范圍廣、安裝和維護成本低、實時性強、抗干擾性強、信息精度高等優點，已成為新興主流的動態實時交通信息采集技術。本文中也選用浮動車數據作為道路交通信息源。

交通信息的處理，旨在將收集到的浮動車GPS點利用地圖匹配技術定位至電子地圖，結合道路的長度及浮動車運行的時間來估算路段行車的平均速度，判斷擁堵狀況。浮動車收集到的GPS信息具有GPS定位誤差、坐標轉換誤差等系統誤差，會出現地圖車輛軌跡曲線與實際行駛路線不吻合的現象，因此，應使用地圖匹配技術來減小匹配誤差，盡可能地還原車輛運行的真實軌跡。浮動車收集到的GPS點信息數量龐大且精度不一，城市中錯綜復雜的路網使得電子地圖也包含海量數據，要求地圖匹配算法具有較高匹配精度、匹配效率和良好的魯棒性，以面對大規模數據處理的挑戰。與此同時，出行者對獲取信息的實時性要求也越來越高，優化地圖匹配算法仍然無法解決實際吞吐量存在的瓶頸，匹配的實時性仍需提高。

本文針對上述問題，設計實現了基于實時浮動車數據的分布式地圖匹配系統[2]，增加信息處理的吞吐量，同時對地圖匹配算法進一步優化，提高了浮動車數據收集和處理整個過程的實時性、有效性和可靠性。

1 信息采集和分布式處理系統設計

數據采集和處理作為智能交通系統的基礎模塊，對整個系統的優劣有重要影響。隨著汽車數量的增多，出行量也逐漸增大，在一定時間內需要有效處理的浮動車數據顯著增加，只有提高數據處理的效率和吞吐量，才能滿足用戶的實時性需求。優化地圖匹配算法可提升處理速度，但仍然不能達到海量浮動車數據實時處理的要求，因此，建立分布式的信息處理系統，使地圖匹配同時在不同PC上并行實施，消除了單一處理的性能瓶頸，解決海量數據的處理難題，使系統達到實際用戶所期望的實時程度。

1.1 分布式機制分析及系統架構

浮動車上傳GPS數據后存至GPS數據中心，作為采集的信息源。信息處理系統需要從GPRS數據中心獲取數據統一存入中心處理器，然后分發至各分布式地圖匹配節點進行地圖匹配工作。分布式處理系統的框架及在智能交通系統中所處位置如圖1所示。矩形框內部分即為分布式匹配系統。

圖1 分布式地圖匹配系統架構

地圖匹配過程一般包含數據預處理、異常數據檢測過濾、網格和路段篩選、GPS點匹配等步驟。因此，分布式并行處理有以下兩種機制：機制①為每個節點進行某個步驟的處理，各步驟按照流水線進行；機制②為每個節點分別完成上述所有步驟，中心處理器將不同范圍的數據送至不同節點進行匹配。機制①的優點是每個節點任務單一、處理效率較高，但結合各步驟的復雜度和計算量可知，數據預處理階段數據量最大，而網格和路段篩選階段的計算復雜度最高、耗時最長，流水處理的機制一方面會造成各個計算節點負載不均衡，另一方面如果某個節點出現問題會影響后續節點的正常工作。因此，選用機制②作為分布式處理的方法。將所有浮動車數據按照浮動車編號進行均勻劃分，每個節點處理一定范圍的信息。在可靠性方面，各節點獨立運算，不存在順序和數據依賴關系，可達到較好的分布式效果；在網絡通信方面，中心處理器與節點只需在初始進行數據傳遞，減小了網絡負載量以及傳輸誤差；在負載均衡方面，每個節點的數據量和計算量幾乎接近，基本可達到負載均衡；并且隨著數據量的增加，可以動態增加節點個數，提高系統的效率以及可伸縮性。從上述分析可知，機制②的分布式處理方法基本滿足系統對實時性、可靠性、穩定性的要求[3]。

整個系統由GPRS數據中心、中心處理器和分布式地圖匹配節點PC構成。GPRS數據中心是浮動車GPS數據的來源，中心處理器負責從GPRS數據中心接收數據并進行數據的整合調度及多線程發送，分布式地圖匹配PC完成地圖匹配工作。

1.2 模塊功能簡介

在數據處理和采集系統中，GPRS數據中心、中心處理器與分布式地圖匹配PC之間需要進行通信和數據傳遞。為保證系統的可靠性、有效性和負載均衡，在中心處理器中設置數據接收、數據分配、數據共享緩沖和線程管理四個子模塊，在分布式地圖匹配PC中同時設立緩沖區，進行數據格式的轉化及預處理等。地圖匹配處理完成的數據存放在數據庫中，供后續的功能模塊使用。

圖2為系統模塊功能框圖[4]。中心處理器接收模塊與GPRS數據中心建立連接，源源不斷地從數據中心獲取實時浮動車數據。在接收模塊中，根據list鏈表和生產者消費者、模型建立接收緩沖區，不僅為接收模塊和后續的分配模塊建立統一的數據存取接口，同時保證數據接收與后續模塊之間速度匹配、不產生數據溢出，提高中心處理器處理海量數據的健壯性。浮動車數據從接收緩沖區取出后，進入數據分配模塊，按照要求把不同浮動車數據填入相應的數據共享區，發送至不同的地圖匹配節點進行匹配操作。數據共享緩沖模塊為分布式通信的緩沖區，每個分布式匹配節點在中心處理器中分別對應一個通信緩沖區，存放經過分配后的數據，緩沖區滿后，將GPS數據打包發送至地圖匹配節點。該緩沖區同樣采用生產者消費者模型，提供數據傳遞接口，保證數據不產生溢出，另外便于浮動車GPS數據打包發送，提高系統通信的效率。線程管理模塊管理多個線程[5]，包括浮動車數據的接收、分配、將對應數據送入分布式緩沖區、進行分布式通信傳入各地圖匹配節點等。該模塊不僅利用多線程實現各子模塊功能，同時利用線程池解決線程之間的同步和互斥問題，也為系統提供實時的子模塊和節點信息。既利用多線程提高了系統效率，又能做到線程的有效管理，是分布式系統的重要環節。

圖2 系統模塊功能框圖

分布式地圖匹配節點在地圖匹配之前，要接收數據存入緩沖區并進行預處理。根據配置信息的過濾條件和數據準確性判斷條件，可判斷GPS數據是否為有效記錄、是否重復、是否為跳點壞點、是否在采樣周期外、是否在經緯度誤差范圍和網格范圍外，對不符合要求的GPS數據進行剔除，可提高后續地圖匹配的精度和效率。GPS浮動車數據存入緩沖區，避免瞬時數據量過大造成溢出，還可配合地圖匹配的算法，使浮動車數據積累到所需的數量開始匹配，同時按照時間戳順序，有序插入List鏈表，使數據利用起來更加有效快捷。

2 地圖匹配算法簡介

地圖匹配節點是系統工作量最大的節點，將從浮動車上獲得的表示車輛當前位置的GPS點信息與電子地圖上的矢量化路段相匹配，尋找浮動車行駛道路，確定相對于電子地圖的車輛實際運行軌跡，并將GPS定位點投影到路段上。通過地圖匹配，可獲知車輛在道路上所處位置及行駛方向，再根據浮動車的時間和路段距離，進一步判斷道路的實時擁堵情況，并向出行者進行發布。地圖匹配算法的效果直接影響車輛定位的精度，因此要求算法有良好的匹配精度和魯棒性。在智能交通系統中，出行者需要在盡可能短的時間內獲知道路狀況，這也要求地圖匹配算法有較好的實時性。

2.1 常用地圖匹配算法

目前，地圖匹配算法主要分為位置點匹配和浮動車軌跡曲線匹配兩種。

位置點匹配算法包括基于電子地圖幾何特性的匹配、基于電子地圖拓撲結構的匹配及基于概率統計的點匹配[6]。基于地圖幾何特性的匹配，分為點到點的匹配、點到線的匹配和線到線的匹配三種。基于網絡拓撲結構的匹配分析前一次匹配結果和當前車輛的運行方向，利用道路的網絡拓撲關系，確定待匹配路段范圍和GPS匹配點。基于概率統計的匹配為每一個GPS浮動車數據設置置信區域，根據歷史匹配結果的概率統計確定匹配路段。浮動車軌跡曲線匹配是基于歷史數據的匹配方法，將GPS定位點與實際道路路網結合，在路網上尋找與GPS點軌跡最接近的路徑，作為浮動車的真實行車軌跡，并據此確定GPS匹配點。

近些年來，為了提高地圖匹配算法的精度，各種先進技術被應用到地圖匹配中，使匹配算法呈現出多樣化的特點。如基于卡爾曼和擴展卡爾曼濾波、模糊數學模型、神經網絡、概率方法、D—S證據理論、多交互模型、貝葉斯判別應用、狀態空間模型和粒子濾波算法等的地圖匹配算法[7]。

對比分析各種地圖匹配算法可知，點到點和點到線的匹配方法算法簡單、計算效率高、實時性強，但大多適于高速公路等簡單結構的路網，在道路密集路況復雜的城市路網中匹配的精度較低；線到線的匹配對異常點非常敏感，且在復雜路網（如立交匝道）匹配精度不高；基于電子地圖拓撲結構的匹配對電子地圖的依賴性太高，且不考慮速度方向等因素，同樣對異常點敏感；基于概率統計的點匹配考慮了道路的地形特性，但匹配精度仍不夠高。利用卡爾曼濾波等先進技術可以較好地提高匹配精度，但復雜算法的計算量和復雜度都大幅提高，實時性差，不適用于實時數據的地圖匹配[8]。以上算法主要考慮GPS定位點軌跡和路網結構的相似性，未考慮利用定位軌跡的連通性來提高匹配精度。利用浮動車軌跡曲線匹配可充分結合浮動車運行軌跡和路網信息，匹配的精度較高，但因需要調用歷史數據，實時性較差。因此，在保證匹配精度的情況下盡可能地提高數據處理實時性，還需要尋求更好的算法。

2.2 綜合地圖匹配算法研究

本文針對智能交通系統對實時性和匹配精度的要求，提出了一種基于道路網格和最短路徑的快速地圖匹配算法，算法流程如圖3所示。

圖3 地圖匹配流程圖

本文的地圖匹配算法利用GPS定位點軌跡，在電子地圖上尋找最接近真實行車軌跡的最短路徑，將GPS點投影到此路徑對應路段，作為匹配點。此算法利用城市路網的拓撲特性、車輛連續運動的軌跡、浮動車運行的角度等，運算時間復雜度為O（c），大大縮短了匹配處理的時間，且能夠達到智能交通系統實際運行所需的精度。

2.2.1 地圖數據的讀取和道路網絡網格的劃分

在此階段加載電子地圖數據，讀取相應的路段和路口信息。由于路段信息和路口信息數量龐大且被反復引用，因此利用字典結構保存，便于查找。按照一定標準（一般300～400m）為步長，將道路網絡從上到下、由左至右網格化均勻分塊，將道路網絡分為M×N個相同大小的網格，其中，M為網格行數，N為網格列數。M和N即為參數值的大小，直接影響地圖匹配的復雜度和精度，因此，進行反復實驗仿真確定最佳參數值。

2.2.2 網格候選路段的確定

劃分路網網格的目的，是為了更方便地確定浮動車GPS點附近的備選路段，因此需要記錄每個網格包含或相交的所有路段，將其編號作為索引值存入所在網格對應的數組中。根據2.2.1中的字典結構，可迅速查找到其他相關信息。由于需要將所有的網格和所有的路段相對應，因此，采用遍歷所有路段的方式，路段的起終點或者中間點與某網格相交，則該路段就作為此網格的候選路段。在地圖匹配過程中，只需要在啟動時刻進行一次掃描，即可將路段與網格對應，為后續匹配工作提供了便利。

2.2.3 浮動車GPS點候選路段的確定

浮動車GPS點候選路段，指在真實路網中此GPS點可能所處的路段。根據浮動車GPS點中所包含的經緯度信息，可確定此GPS點所在的網格，如網格左下角端點坐標為(x0,y0)，網格數量為M×N，每個網格尺寸為l×l，浮動車GPS點坐標為(x1,y1)，則其所在網格為Grid([(x1-x0)/l],[(y1-y0)/l])，以此網格為中心的相鄰九個網格中所包含的全部路段，即為此GPS地圖匹配的候選路段。

2.2.4 GPS點軌跡最短路徑的選擇

在尋找最短路徑時，以浮動車的一組GPS點軌跡作為一段旅程，在電子地圖上尋找最符合此運動軌跡的從起點到終點的路段，最終獲得的最短路徑作為浮動車的真實運動軌跡。

在此算法中，地圖匹配的目標函數[9]見式（1）：

式中：D為電子地圖中所有路段；l為路段長度；x表示是否為候選路段，如果是，則x取值為1，非候選路段x為0；P為地圖匹配路段的權重，P越高，代表所在路段成為最短路徑的概率越大。

這里利用二次網格的劃分和GPS點的角度[10]、路段附近GPS點的數量來修正P值，為每條候選路段計算權重總和，權重計算公式為：

P1為二次網格劃分權重值，在電子地圖初始化環節，一次道路網格劃分之后，進行精度更大的二次網格劃分（如一次劃分步長為l，二次劃分步長為l/10），GPS點所在網格為中心的周圍9個網格包含的路段，即為高權重路段。P2為GPS角度權值，GPS點周圍與GPS點行車方向夾角小于90°的路段設置較高角度權值。P3為GPS數量權值，在誤差范圍內某路段附近的浮動車GPS點數越多，則此路段設置越高數量權值。n為路段誤差范圍內GPS點的數量。權值的大小關系到最優路徑選擇的準確程度，因此，通過多次實驗仿真確定。

候選路段和路段的權值確定完畢后，完成從起點到終點最優路徑的選擇。最優路徑的確定采用Dijkstra算法[11]。

2.2.5 GPS點匹配

最短路徑選擇完成后，浮動車行駛經過的路段從而確定。GPS點的匹配采用最簡單高效的投影法，將GPS點投影到對應路段上，若垂足在路段內，則垂足為GPS匹配點；若垂足在路段外，則與GPS點距離最近的路段端點作為GPS匹配點。地圖匹配步驟完成后，即可進行后續的路徑融合、行程時間估計等工作。

基于道路網格和最短路徑的快速地圖匹配算法通過對道路網格的分塊處理，使地圖匹配基本不受道路網絡規模變化的影響，并且與整個路網相比，匹配候選路段數量非常少，極大程度地提高了匹配處理的實時性。而基于二次網格的劃分、路段周圍GPS點數量的判斷和GPS點方向的判斷對候選路段的權重進行修正，并結合Dijkstra算法確定浮動車軌跡的最短路徑，又提高了地圖匹配的精度。此種算法適合于智能交通系統的實際應用，兼顧實時性和匹配處理精度，可較好地處理海量的浮動車實時數據。

3 仿真結果及分析

3.1 地圖匹配算法參數選擇

在本文的地圖匹配算法中，網格劃分參數和權重值的設定對于地圖匹配的精度有著至關重要的影響。因此，需采用大量實驗來確定和修正權重值的取值。參數大小與算法本身、地圖數據和浮動車數據均有關。在本算法中，采用大連市地圖數據和大連市交管局浮動車數據進行仿真實驗。

經過大量仿真對比，最終確定第一次網格劃分的步長為300×300m，第二次網格劃分的步長為30×30m，權重值P1、P2、P3的設定如表1、表2、表3所示。

表1 地圖匹配算法權重P1取值表

表2 地圖匹配算法權重P2 取值表1取值表

表3 地圖匹配算法權重P3 取值表1取值表

3.2 實驗仿真及結果分析

本文對信息采集和分布式處理系統進行了仿真。GPRS數據中心、中心處理器和分布式處理節點均使用2.93GHz CPU，3G內存計算機，分布式處理節點為3個。各模塊之間的通信采用TCP/IP通信，socket編程[12]，利用線程池管理多個線程[13]。經統計，3個匹配節點完成大連市1000輛出租車約130萬個GPS點數據需要的時間為1min37s，算法的平均正確匹配率為93.3%。

大連市實時浮動車數據數量龐大，要求地圖匹配有較高的實時性，本文設計的分布式處理系統和基于道路網格、最短路徑的快速地圖匹配算法，能夠在很大程度上提高匹配效率，保證系統實時性。同時，地圖匹配的準確率能夠滿足實時系統的要求，適合智能交通系統中對海量數據的實時處理。

4 結論

本文在分析智能交通系統發展趨勢的基礎上，設計了基于實時浮動車數據的分布式地圖匹配系統，并提出了基于道路網格和最短路徑的快速地圖匹配算法，在保證地圖匹配處理精度的情況下較大程度地提高了系統的實時性。經仿真實驗可知，系統可高效穩定地運行，滿足大連市智能交通系統的處理要求，可應用在實際系統中。

[1]Bishop R.Floating car data projects worldwide:A selective review[C].Inidana,America:ITS America Annual Mtg,2004:192-197.

[2]王笑京，齊彤巖.智能交通系統體系框架原理與應用[M].北京：中國鐵道出版社，2004.

[3]朱小東.大規模計算機系統并行仿真技術研究[D].合肥：中國科學技術大學，2013.

[4]沈斌，蔣昌俊，章昭輝，等.一種基于海量GPS數據的分布式地圖匹配系統的設計與實現[J].小型微型計算機系統，2007，28（3）：479-481.

[5]Akhter S,Roberts J.Multi-core programming[M].Hills?boro:Intel press,2006.

[6]王美玲，程林.浮動車地圖匹配算法研究[J].測繪學報，2012，41（1）：133-138.

[7]劉培.基于浮動車數據的地圖匹配算法研究[D].北京：北京交通大學，2007.

[8]Quddus M A,Washington Y O,Robert B N.Integrity of map-matching algorithms[J].Transportation Research Part C,2006,14(4):283-302.

[9]Yanagisawa H An offline map matching via integer pro?gramming[C].Istanbul,Turkey:Pattern Recognition(ICPR),201020th International Conference on IEEE,2010:4206-4209.

[10]Miwa T,et al.Development of map matching algorithm for low frequency probe data[J].Transportation Research Part C:Emerging Technologies,2012,22(1):132-145.

[11]李元臣，劉維群.基于Dijkstra算法的網絡最短路徑分析[J].微型計算機應用，2004（5）：295-298.

[12]王靜，曲鳳娟.基于Socket的多用戶并發通信的設計[J].福建電腦，2007（3）：164-165.

[13]羅亞非.基于TCP的socket多線程通信[J].電腦知識與技術，2009（9）：563-566.