何兆成，陳展球，范秋明，褚俊飛

（中山大學 工學院智能交通研究中心，廣州510000）

基于手機基站數(shù)據(jù)的混合地圖匹配算法研究

何兆成＊，陳展球，范秋明，褚俊飛

（中山大學 工學院智能交通研究中心，廣州510000）

基于移動通信的交通信息采集是智能交通系統(tǒng)中新興的應用技術之一，將車載手機定位到電子地圖上是其應用的基礎，而地圖匹配技術則是解決車載手機定位的關鍵.本文通過對車載手機行駛在不同的路網(wǎng)時所產(chǎn)生的基站切換數(shù)據(jù)信息，分析得到車載手機實際運行時基站切換的基本規(guī)律；并結合電子地圖的數(shù)據(jù)結構特點，對使用基站切換數(shù)據(jù)進行地圖匹配時需解決的難點問題展開研究；在使用基站切換對代替道路穩(wěn)定切換序列的方法的基礎上，提出了結合切換對和基站源址的混合地圖匹配算法.此算法可以縮小待選路段集，有效處理交叉口和平行路段等復雜情況，提高匹配準確率.最后,選取廣州大學城為實地測試區(qū)域，驗證了此算法的可行性.

智能交通；基站切換對；混合地圖匹配算法；交通信息采集；地圖匹配

1 引言

交通信息是智能交通系統(tǒng)建設的基礎，在交通信息采集中常用的有路面檢測器和GPS浮動車技術[1].近年來，基于移動通信的交通信息采集技術得到廣泛關注和發(fā)展，這種方法是將車載手機看成在路檢測器，通過基站切換序列等來估算區(qū)間速度和行程時間，和GPS浮動車技術一樣，方法依賴于地圖匹配，但是手機定位精度差，相關地圖匹配算法不成熟限制了技術的應用[2].目前，國內(nèi)外在這一領域也做了許多研究，但是這些研究的實際定位數(shù)據(jù)較難獲得，而且大部分都是采用仿真實驗，地圖匹配精度較差[3，4].當前面向交通應用的基站定位地圖匹配方法主要有兩種，一是基于基站切換序列的方法，其基本原理是通過追蹤的目標手機在通信網(wǎng)絡層的變化模式來反推其在實際的道路網(wǎng)絡層變化模式[5]，這種方法的路網(wǎng)標定過程復雜，數(shù)據(jù)維護工作量大，平行或相近路段干擾嚴重；另一種是基于基站源址的匹配方法，這是一種單個基站的定位技術，即根據(jù)手機連接的基站的物理位置來判斷手機的當前位置，但是在城市道路中，它的匹配誤差非常大[6].同時對這兩種方法來說，較少采用實際路網(wǎng)，尤其是復雜城市路網(wǎng)的數(shù)據(jù)進行分析[7].本文在分析這兩種地圖匹配方法的基礎上提出了一種新的道路混合地圖匹配算法.

2 混合地圖匹配算法設計

2.1 基站切換對基礎數(shù)據(jù)庫的建立

設計混合地圖匹配算法的首要任務是建立切換對基礎數(shù)據(jù)庫.建立基礎數(shù)據(jù)庫之前，首先要引入基站切換對概念：手機注冊到通信網(wǎng)絡后，隨著車輛的移動，車載手機逐漸遠離當前服務基站，這會導致手機接收到的基站信號強度逐漸下降，當信號強度低于預先設定的閾值時，通信網(wǎng)絡會將手機的連接信號從當前的服務基站轉移到另一個信號強度較高的基站，從而保證通信服務的質量，這個過程就是基站切換現(xiàn)象.切換一般發(fā)生在兩個基站邊緣交界的地方，車載手機在道路上運行的時候會獲取到切換序列，定義相鄰兩次切換的基站序號組成一個切換對，如圖1所示，道路上的手機在進入A基站范圍時候發(fā)生一次切換，離開A基站服務范圍進入到B基站時發(fā)生一次切換，即可獲得一個切換對A→B.

假如對A→B這一切換對，經(jīng)過多次實驗之后，由于產(chǎn)生A→B這一切換對的路段可能不是唯一的，因此給每個基站切換對設定頻率字段，該頻率代表切換對在對應路段上的可能性.即A→B切換對可能的m條道路集合為(l1,l2,...,lm)，其中每條道路的發(fā)生頻率為(λ1,λ2,...,λm)，頻率的計算公式如式（1）所示.

圖1 基站切換對示意圖Fig.1 Handover pair of cell-towers on the schematic

通過多次實驗將每個切換對、切換對可能在的道路及在該道路上出現(xiàn)的頻率存儲在數(shù)據(jù)庫中，形成基站切換對數(shù)據(jù)庫，基站切換對數(shù)據(jù)庫存儲格式如表格1所示，其中的中括號表示該切換對經(jīng)過的路段和發(fā)生頻率，小括號內(nèi)的是經(jīng)過的路段的ID集合.

表1 基站切換對數(shù)據(jù)庫片段Table1 Handover pair of cell-towers database fragments

2.2 混合地圖匹配算法描述

建立好切換對基礎數(shù)據(jù)庫后，就可以開始實現(xiàn)應用于復雜路網(wǎng)的混合地圖匹配算法.圖2所示是一個具有14個節(jié)點，20條Link的路網(wǎng)，車載手機的出行軌跡如圖中箭頭線段所示，為L1→L2→L3→L4→L5，獲得的基站切換序列為A→B→C→D→E.

這里以該次出行為例，展示混合地圖匹配算法的實現(xiàn)步驟，其實現(xiàn)步驟如圖3所示.

圖2 混合地圖匹配算法示例路網(wǎng)Fig.2 Hybrid algorithm road network example

圖3 混合地圖匹配算法實現(xiàn)步驟Fig.3 Hybrid algorithm implementation steps

(1)采用基站源址確定候選路段集.

對圖2的每個基站點，由經(jīng)驗緩沖區(qū)通過相交判斷獲得每個基站Celli（i=1,2,...,n）待選路段集合，如圖4.其中經(jīng)驗緩沖區(qū)是指：通過實地跟車實驗獲取基站數(shù)據(jù)，計算在路手機所連接的基站與所在道路的投影距離，把多次實驗獲得的投影距離最大值作為緩沖區(qū)的半徑長度，以基站點為圓心畫圓得到經(jīng)驗緩沖區(qū)，經(jīng)驗緩沖區(qū)如圖5所示，其中Dempiric為半徑長度.

圖4 單個基站的待選路段Fig.4 A single base station Candidate sections set

圖5 緩沖區(qū)示意圖Fig.5 Buffer schematic

然后確定兩兩基站之間的候選路段集G.其規(guī)則如下：對連續(xù)的兩個基站Celli和Celli+1，取出各自的待選路段集合和，同時將Celli和Celli+1轉換為帶經(jīng)緯度信息的定位點，由這兩個定位點的經(jīng)緯度加入偏移量后得到兩個新的點，兩點連線作為對角線可以確定矩形限制區(qū)域，引入拓撲連通性規(guī)則即可得到這兩個連續(xù)基站間的待選連接路段集G.G中的元素必須符合規(guī)則：起點路段在集合中，終點路段在中；所有路段在限制區(qū)域內(nèi)；符合拓撲連通性.

如果通過以上規(guī)則找不到連接路段，則用最短路算法確定連續(xù)兩個基站點間的連接路段，放入G，保證G非空.對序列{Cell1,Cell2,...,Celln}的所有的連續(xù)兩個基站都進行以上操作，可得到由整個切換基站序列中任意兩個連續(xù)基站間的連續(xù)路段集組成的有向圖.將所得結果可視化畫出如圖6所示.

圖6 基站源址確定候選路段集Fig.6 Cell of origin identifying candidate sections set

(2)采用切換對確定候選路段集.

基站切換序列為A→B→C→D→E，將序列分隔，共獲得4個切換對A→B、B→C、C→D和D→E，由基站切換對數(shù)據(jù)庫可以獲得每個切換對對應的所有路段和頻率信息，如表2所示.

將表格中從基站切換數(shù)據(jù)庫得到路段集信息轉化為連通圖G'，將所得結果可視化畫出如圖7所示，其中D→E切換對在基站切換對數(shù)據(jù)庫中沒有對應數(shù)據(jù)信息，因此G'中D和E之間沒有連接路徑.

表2 切換對對應路段信息Table2 Handover pair of cell-towers corresponding link information

圖7 切換對確定候選路段集Fig.7 Handover pair of cell-towers identifying candidate sections

(3)獲得縮小的候選路段集.

對圖6和圖7進行處理，首先對G和G'進行比對分析，通過以下原則獲得連續(xù)兩個基站Celli到基站Celli+1間的縮小連接路段集：

①G'非空，G和G'有相同路段，將相同的路段帶權重放入G''；

②G'非空，G和G'沒有相同路段，將G'中最大權重的路段帶權重放入G''；

③G'為空，取G中到達Celli+1基站位置投影距離最短的路段放入G''，最短投影距離放入G''.

將G和G'按照順序提取出連續(xù)的兩個基站，進行以上操作，可以獲得由任意兩個連續(xù)基站的縮小連接路段集組成的有向圖，得到連續(xù)基站間由帶權重的和不帶權重的路段所構成的縮小范圍的待選路段集G''，將所得結果可視化畫出如圖8所示.

圖8 縮小候選路段集合Fig.8 Reduced candidate sections set

(4)獲得總體匹配路徑.

圖9 分割示意圖Fig.9 Segmentation Schematic diagram

找出連接路段是唯一確定的連續(xù)兩個基站，如圖9所示的D→E，從圖中劃虛線的D處進行分割，可以得到帶權重的子圖，如圖10所示，還有不帶權重的部分，如圖11.

圖10 帶權重有向圖Fig.10 Directed graph with weights

圖11 不帶權重子圖Fig.11 Subgraph without weights

針對如圖10所示的帶權重有向圖，將問題轉化為符合拓撲連通情況下最大權重出行路徑的求解問題.從而確定該有向圖對應的車載手機出行路徑為L1→L2→L3→L4→L5，將各部分拼接后可以獲得總體出行路徑為L1→L2→L3→L4→L5→L6→L7.

3 實驗分析

實驗的目的主要是驗證混合地圖匹配算法的可行性及準確性，實驗路線選取廣州大學城內(nèi)環(huán)、中四路、外環(huán)、中一路這個環(huán)形區(qū)域代表城市道路，其實測路線如圖12黑色線路所示.

3.1 實驗條件

為了保證實驗樣本充足，對實驗區(qū)域的所有道路反復做15次的跑車實驗來建立切換對基礎基站，然后再沿著加黑的矩形路線做5次跑車實驗收集切換序列作為待匹配切換序列.

3.2 實驗結果分析

對上述的5次待匹配切換序列，分別用基站源址方法，基站切換序列方法和混合地圖匹配方法進行地圖匹配，并對它們的匹配結果進行分析，分析結果如下：

3.2.1 和基于基站源址地圖匹配方法對比

（1）匹配效果對比.

圖13展示的是使用基站源址方法和使用混合匹配算法對同一數(shù)據(jù)進行匹配處理的匹配效果.可以看到，相比基站源址的匹配方法，混合匹配算法可以更準確地辨識出實驗路線經(jīng)過的路段，匹配效果良好.

圖12 實測實驗線路Fig.12 Measured experimental route

圖13 基站源址方法和混合匹配算法效果對比Fig.13 Cell of origin and hybrid algorithm effect of contrast

（2）匹配指標對比.

點有效匹配率和目標道路覆蓋率，計算方法如式（2）和式（3）所示.

將兩個方法的點有效匹配率和道路覆蓋率進行實驗對比，基站源址方法的匹配指標如表3所示，混合匹配算法的匹配指標如表4所示.從表中可以看到，使用混合算法對基站定位數(shù)據(jù)進行處理，相對于基站源址方法，無論是點有效匹配率和目標道路覆蓋率都得到了較大提高.

表3 基站源址方法匹配結果Table3 Cell of cell of origin matching effect

表4 混合算法匹配結果Table4 Hybrid algorithm matching effect

3.2.2 和基于基站切換序列地圖匹配方法對比

（1）匹配效果對比.

使用基于基站切換序列和混合算法對同一次實驗數(shù)據(jù)匹配，結果如圖14所示.其中使用基站切換序列進行匹配的效果如圖14的B部分所示，可以發(fā)現(xiàn)該方法待匹配序列中有較多的數(shù)據(jù)在穩(wěn)定切換序列中沒有對應數(shù)據(jù)，從而出現(xiàn)多處無法匹配的空缺路段.由于存在其他道路的干擾，出現(xiàn)了誤匹配的情況.總體匹配效果差，直接觀測到結果中正確匹配部分較少；圖14中A部分是混合算法的匹配結果，對比可知，相比基于基站穩(wěn)定序列的匹配方法，混合匹配算法匹配效果更好.

圖14 基站切換序列方法和混合匹配算法效果對比Fig.14 Base station switching sequence and hybrid algorithm effect of contrast

（2）匹配指標對比.

在進行指標對比之前，先引入穩(wěn)定切換序列這個概念：將n(n＞1)次實地實驗采集到切換序列都看成有向路徑并疊加在一起，可以得到一個從起始基站到終止基站的有向圖，有向圖中的每個有向邊出現(xiàn)的次數(shù)為i（i=1,2,…,n），將每條邊出現(xiàn)的次數(shù)i作為這條邊的權重，得到從起始基站到終止基站的帶權重有向圖.從而將問題轉化為經(jīng)典的帶權重有向圖最大路徑問題，利用最大權重路徑方法計算得到起始基站到終止基站總權重最大的序列即為該條實驗道路的穩(wěn)定切換序列.將當前獲得的切換序列和穩(wěn)定切換序列進行比較，假如在穩(wěn)定序列中的n個基站和當前序列中的m個基站中有k(k＜n,k＜m)個相同基站，同時相鄰切換集合中共有l(wèi)(l＜n-1,l＜m-1)個相同相鄰切換，設λ1表示相同基站的概率，λ2表示相同相鄰切換的概率，其計算方法如式（4）和式（5）所示.

則有當前切換序列和穩(wěn)定序列的相似概率λ的計算方法如式（6）所示.

用相似度計算方法對每次實驗數(shù)據(jù)進行計算，計算結果如表5所示，使用切換序列方法和混合匹配算法處理以上實測路線中五次實驗數(shù)據(jù)，可得到兩種方法下的正確匹配路段數(shù)據(jù)，然后計算得到各自的平均目標道路覆蓋率，結果如表6所示.從表中可以看到，在同樣進行五次路網(wǎng)標定獲得基礎數(shù)據(jù)庫的情況下，使用混合算法對基站定位數(shù)據(jù)進行處理，相對于切換序列方法，目標道路覆蓋率得到較大的提高.

表5 實測路線相似度分析Table5 Measured route similarity analysis

表6 混合匹配算法和基于切換序列方法的匹配指標比較Table6 Base station switching sequence and hybrid algorithm matching index contrast

4 研究結論

本文設計出一種新的混合地圖匹配，它把切換序列拆分成切換對，就是將切換序列化整為零，得到更小粒度和更強的對應關系，在基站密集的地方采用基站源址的方法，在基站稀疏的地方則采用模式匹配方法.此方法方便靈活，很好地結合了基站源址和模式匹配這兩種方法的優(yōu)點.既解決了基于切換序列地圖匹配算法中路網(wǎng)標定工作量大的問題，又提高了基于基站源址的地圖匹配算法中的點有效匹配率和目標道路匹配率；最后，通過選取廣州大學城的某一區(qū)域作為實驗區(qū)域驗證此方法的可行性，結果表明，此方法準確性高.

[1]Ferman M A,Blumenfeld D E,Dai X.A simple analyti?cal model of a probe-based traffic information system [C]//Intelligent Transportation Systems,2003.Proceed?ings.2003 IEEE.IEEE,2003,1:263-268.

[2]張赫,楊兆升.無檢測器交叉口交通流量預測方法綜合研究[J].公路科技，2002，19（01）：91-95.[ZHANG H,YANG Z S.Study on forecast of traffic volume at nondetector intersections[J].Journal of Highway and Trans?portation Research and Development,2002,19(01)：91-95.]

[3]Ygnace J L,Remy J G,Bosseboeuf J L,et al.Travel time estimates on Rhone corridor network using cellular phones as probes:phase 1 technology assessment and preliminary results[J].INRETS report,2000.

[4]Cayford R,Johnson T.Operational parameters affecting the use of anonymous cell phone tracking for generating traffic information[C]//Institute of transportation studies for the 82th TRB Annual Meeting,2003,1(3):03-20.

[5]楊飛,惠英.基于手機切換變化模式的道路匹配方法[J].系統(tǒng)工程,2007,25(011):6-13.[YANG F,HUI Y. The map matching method based on cell phone hando?ver pattern[J].Systems Engineering,2007,25(011):6-13.]

[6]范秋明,何兆成.基于手機基站定位數(shù)據(jù)的地圖匹配研究[J].交通信息與安全,2011,29(4):52-57.[FANG Q M,HE Z C.Map matching based on GSM positioning data[J].Journal of Transport Information and Safety, 2011,29(4):52-57.]

[7]趙力萱.基于移動通信數(shù)據(jù)的高速公路交通信息采集與交通狀態(tài)判別研究[D].中山大學,2009.[ZHAO L X. Freeway traffic information collection and identification of traffic state based on mobie communications data[D]. Sun Yat-Sen University,2009.]

Hybrid Map Matching Algorithm Based On Mobile Base Station Data

HE Zhao-cheng，CHEN Zhan-qiu，F(xiàn)AN Qiu-ming，CHU Jun-fei
（Institute of Intelligent Transportation Research Center,Sun Yat-sen University,Guangzhou 510000,China）

Traffic information collection based on mobile communication is one of the emerging technologies of intelligent transportation system,the foundation of this method is positioning the vehicle-mounted mobile phone on electronic map,and the key to solve vehicle-mounted mobile positioning is the map matching technology.The basic rules of switching behavior is obtained form vehicle-mounted mobile phone,via analyzing the actual handover data of cell-towers generated from vehicle-mounted mobile phone which running on different network.To study the key problem of map matching by using handover data of cell-towers, combining with the data structure characteristic of the electronic map.On the basic of using handover pair of cell-towers instead of stability switching sequence,a hybrid algorithm is put forward which combines coordinates of base station with pattern sequences matching to narrow the chosen sections set,deal with the intersection and parallel sections,and improve correct matching rate.Finally,Guangzhou Higher Education Mega Center is selected for the test area,it verifies the algorithm is feasible.

intelligent transportation;handover pair of cell-towers;hybrid map matching algorithm;traffic information collection;map matching

1009-6744（2014）03-0034-09

U268.6

A

2013-10-16

2013-11-24錄用日期：2013-12-06

何兆成（1977-），男，廣東梅州人，副教授，碩士生導師.*通訊作者:hezhch@mail.sysu.edu.cn