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

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

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

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

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

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

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

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

1 引言

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

2 混合地圖匹配算法設(shè)計(jì)

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

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

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

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

通過多次實(shí)驗(yàn)將每個(gè)切換對、切換對可能在的道路及在該道路上出現(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 混合地圖匹配算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖10 帶權(quán)重有向圖Fig.10 Directed graph with weights

圖11 不帶權(quán)重子圖Fig.11 Subgraph without weights

針對如圖10所示的帶權(quán)重有向圖，將問題轉(zhuǎn)化為符合拓?fù)溥B通情況下最大權(quán)重出行路徑的求解問題.從而確定該有向圖對應(yīng)的車載手機(jī)出行路徑為L1→L2→L3→L4→L5，將各部分拼接后可以獲得總體出行路徑為L1→L2→L3→L4→L5→L6→L7.

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

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

3.1 實(shí)驗(yàn)條件

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

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

（1）匹配效果對比.

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

圖12 實(shí)測實(shí)驗(yàn)線路Fig.12 Measured experimental route

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

（2）匹配指標(biāo)對比.

點(diǎn)有效匹配率和目標(biāo)道路覆蓋率，計(jì)算方法如式（2）和式（3）所示.

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

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

表4 混合算法匹配結(jié)果Table4 Hybrid algorithm matching effect

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

（1）匹配效果對比.

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

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

（2）匹配指標(biāo)對比.

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

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

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

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

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

4 研究結(jié)論

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

[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]張赫,楊兆升.無檢測器交叉口交通流量預(yù)測方法綜合研究[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ī)切換變化模式的道路匹配方法[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]范秋明,何兆成.基于手機(jī)基站定位數(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]趙力萱.基于移動(dòng)通信數(shù)據(jù)的高速公路交通信息采集與交通狀態(tài)判別研究[D].中山大學(xué),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-），男，廣東梅州人，副教授，碩士生導(dǎo)師.*通訊作者:hezhch@mail.sysu.edu.cn