指紋定位應用于智能運輸系統之可行性＊

陳志華 林邦曄 郭庭歡 羅濟群

（國立交通大學資訊管理研究所1） 新竹 300） （中華電信研究院2） 桃園 326）（國立中山大學資訊工程學系3） 高雄 804）

0 引 言

1 系統方法設計與分析

根據前述之研究背景、動機與國內外重要文獻探討，本研究在利用行動網絡追蹤用戶手機位置的方法上將針對GSM／General Packet Radio Service（GPRS）／UMTS異質網絡進行網絡接口訊號擷取與分析.首先，將于網絡端選定數個網絡接口，如：A－bis，Iub等界面.再設計結合指紋定位的智能型運輸系統擷取由手機傳送到核心網絡的基地臺訊號測量報告（measurement report，MR）、主呼（call origination）訊號、被呼（call ter－mination）訊號等，來分析終端使用者的移動狀況，進而評估實時交通路況.

由于目前大部分的電信業者之設備仍是GSM，GPRS，UMTS共存的狀況，因此本研究主要將針對A－bis，Iub等接口依不同的事件擷取訊號之位置ID（location identifiers）及時間點，以進行后續分析.并設計結合指紋定位的智能型運輸系統，系統架構圖如圖1所示.智能型運輸系統透過電信業者之設備收集A－bis，Iub等網絡接口依不同的事件擷取訊號之位置ID（location identifiers）及時間點進行擷取與分析.其中，智能型運輸系統主要包含指紋定位算法和云計算服務，主要將收集行動網絡訊號，并擷取手機之各個基地臺訊號測量報告，依此測量報告結合指紋辨識算法（fingerprint positioning algorithm，FPA），進行手機定位，并由2次定位取得車速信息.最后，再結合云計算的特性，對指紋辨識算法進行平行運算，加快處理效率，提供實時交通信息予用路人決策參考.

圖1 結合指紋定位技術的智能型運輸系統架構

1.1 結合指紋定位之車速評估方法

在目前GSM／UMTS標準下，當手機通話中時將持續偵測其附近基地臺的訊號強度之測量報告予網絡端，以供網絡進行換手程序之評估依據.因此，本研究之智能型運輸系統將于現有網絡基礎下，于A－bis，Iub接口擷取測量報告之網絡訊號，并進行指紋定位算法分析手機的位置.本研究將擷取該手機于其開始通話（call arrival，CA）時所發出的該通話第一個測量報告和結束通話（call completion，CC）時所發出的該通話最后一個測量報告，依此測量報告取得2個不同位置的定位，依其地理空間距離差與時間差評估車速.

1.1.1 指紋定位算法 首先，本研究運用手機紀錄和收集每個訓練位置L＝｛l1，l2，…，lm｝的基地臺訊號強度集合之訊標B＝｛b1，b2，…，bn｝.在每一個訓練位置li，本研究測量其每一個基地臺的訊號強度集合為，并將其紀錄于數據庫中，將位置和訊號強度進行對應.其中，為第j個基地臺之訊號強度bj，j＝1，…，n.當手機移動時，手機可以測量其附近的基地訊號強度集合s＝｛s1，s2，…，sn｝，并將s與數據庫中所有位置及其訊號強度集合進行比對，評估手機當時可能的位置.

本研究使用指紋定位算法評估每一個訊號強度集合s之位置l（r）.運用Euclidean距離運算方法，采用式（1）將訊號強度集合s＝｛s1，s2，…，sn｝與數據庫中的每一個位置li及其其訊號強度集合｝進行距離計算.

針對每一個訓練位置進行Euclidean距離運算，并使用式（2）找出訊號強度最接近的位置h1.

因此，本研究可以挑選訊號強度最接近的k個位置h ＝ ｛h1，h2，…，hk｝，然后運用式（3）之距離權重kNN規則計算出手機的位置l（s）.

吳邦偉在民國時期歷任國民體育委員會委員、教育廳督學、省立體育場場長，創辦期刊、編撰書籍，對當時的社會體育事業做出了卓越的貢獻；許多思想在今天看來都具有超越時代性和前瞻性；對其社會體育思想的深入探討，不僅是對老一輩體育人的深切懷念，更是從歷史的發展中探尋前人的智慧，為當下全民健身與全民健康深入融合提供借鑒意義。

1.1.2 車速評估方法 在車速評估上，主要透過手機開始通話與結束通話測量報告之訊號和指紋定位方法，估計出手機的位置，再依位置的距離和時間差進行車速評估，詳細作法如下：（1）運用指紋定位方法估計手機開始通話的位置l（s1）；（2）運用指紋定位方法估計手機結束通話的位置l（s2）；（3）取得這2次指紋定位之時間差［t1，t2］；（4）依指紋定位方法得到之第1次位置ls1和第2次位置ls2分別將其對應至地理空間中，并計算出兩個位置的地理空間距離 D［l（s1），l（s2）］和時間差［t1，t2］，再以式（4）評估車速v1，2.

1.1.3 車速信息回報率分析 在研究中本研究將考慮通話行為模式、交通路況、以及兩次指紋定位得到車速之方法，提出車速信息回報率分析模型.圖2顯示車輛移動與通話行為之時間示意圖，其中手機沿著道路移動在時間點t0時撥了一通電話，并在時間點t1時進入到目標路段的范圍.而且，手機在它離開目標路段的范圍前（時間點time t4），分別在時間點t2時撥了一通電話和在時間點t3時結束該通電話.

圖2 車輛移動與通話行為之時間示意圖

在此模型中，本研究提出以下的假設：（1）每臺移動的車子中都有一支手機；（2）開始通話（call arrival）訊號（包含撥話（call origination）和受話（call termination）訊號）之機率密度分布為泊松過程（poisson process），其中平均通話率為（call／hr）；（3）通話間隔時間 （call inter－arrival time）之隨機變量τ其機率密度分布為指數分布（exponential distribution），其中平均通話間隔時間為1／λ［4］；（4）通話時間（call holding time）之隨機變量t其機率密度分布為指數分布（exponential distribution），其中平均通話時間為1／μ［4］；（5）由車輛偵測器量測到目標路段上之真實平均車速為v、真實交通流量為f；（6）手機從進入目標路段前1次通話到進入目標路段的間隔時間（即［t0，t1］）為x；（7）目標路段長度為d.

根據上述假設，本研究提出公式（5）評估采用兩次指紋定位產生車速的數量r（意即車速信息回報率），依此將可以觀察當此方法實測部署到電信業者機房中時，預期此方法可以得到的信息量，并以此與目前實際已部署的車輛偵測器進行比較.

1.2 云計算算法

行動網絡充斥著大量且繁雜的訊號，以及指紋定位算法將會因為基地臺數量和訓練位置數量而造成的大量運算，有鑒于執行效能考慮，因此本研究將采用云計算進行平行處理，以Hadoop平臺進行Map Reduce程序［9］實作，將每個訓練位置的訊標獨立分別執行，以快速地提供使用者定位使用.

在每一筆數據中，本研究將紀錄每一個位置li（包含其位置ID和經緯度坐標）及其訊號強度集合｝，并將測試數據之訊號強度集合s＝｛s1，s2，…，sn｝建立于每個訓練數據中，以計算取得測試數據與每個訓練位置的訊號強度之歐幾里得距離d（s，li）.實作上本研究采用 Hadoop平臺，并以MapReduce程序進行平行運算.

步驟1 分別建立Mapper及Reducer的類別的對象，設定運算工作的內容并設置key和value的數據型態，以便存放數據集合，并進行歐幾里得距離.其中，本研究把位置li設為key，而該位置所對應之訊標｝和測試資料的訊標s＝｛s1，s2，…，sn｝設為value，后續將依各個訓練位置分別進行獨立運算.

步驟2 設定完成后，數據源會依格式的設定取得，并分割轉換為一組組的（key，value）序對，交由不同的 Mapper同時進行運算.Mapper將運算的結果輸出為一組組的（key，value）序對，也稱為中介數據（intermediate），系統會將這些暫時的結果排序并暫存起來，等到所有Mapper的運算工作結束之后，依照不同的key值傳送給不同的Reducer匯整，所有同一key值的中介數據的value值，會放在一個容器里傳給同一個Reducer處理.在本研究，本研究將把測試資料的訊標Map到各個訓練位置中，之后再于Reducer進行計算.

步驟3 Reducer依序取得不同value值，快速地完成結果整理，再依格式的設定輸出為檔案.在本研究中，于Reducer實作歐幾里得距離，為每個訓練位置之訊標ci與測試數據之訊標s進行運算，以評估測試數據與每筆訓練位置的關系，并進行定位.

2 實驗環境與結果

本研究主要分析定位精確度和車速估計精確度，以長12.2km之快速道路66號路段進行實際路測.在路測實驗中，每趟于車上設置1支手機（例如，搭配Android platform 2.2之 HTC Desire手機），同時搭配GPS接收器收集經緯度坐標，在實驗路段往返行駛，并持續收集該手機附近的基地臺訊號強度.在實驗中手機進行12趟的路測，連結到96個不同的細胞（cell）.

2.1 位置評估準確率

在實驗路段共來回路測12趟以提供指紋定位算法來進行模式訓練，其中在實驗中共收集6 299筆資料.采用 k－fold cross－validation方法來進行系統效能評估，將每筆數據分別進行交叉訓練和測試評估，其中數據筆數共6 299筆.首先，取出一筆數據為測試數據，其他6 298筆數據進行模式訓練；當訓練結束后，再將測試數據輸入進行評估，并判斷正確率.依上述方式將每筆數據進行測試，累計重復執行6 299回.

實驗采用指紋定位算法和3GPP定義標準中的cell ID定位等方法進行效能評估，實驗數據如表1.實驗結果顯示若采用指紋定位算法，其在k設為1～4時，位置評估平均誤差分別為38.46，36.11，37.14和40.66m；但分別采用Handover和Cell ID定位方法后，其位置評估平均誤差則分別為293.54和714.07m.由結果顯示指紋定位算法相較于Handover和Cell ID定位方法將可提供顯著的定位準確率，因此本研究將采用指紋定位算法進行位置評估.

表1 位置評估準確率比較表

2.2 車速評估準確率

在車速估計準確度的部分，收集連續2次指紋定位方法取得之位置和時間差，運用公式（4）評估車速（ve）.在實驗中，將同時收集GPS手機之GPS定位信息作為真實的車速（va），并運用式（6）計算車速評估的誤差率（R）.

實驗采用指紋定位算法和3GPP定義標準中的Cell ID定位等方法進行效能評估，實驗數據如表2.實驗結果顯示若采用指紋定位算法，其在k設為1～4時，車速評估平均誤差分別為3.95%，3.39%，4.52%和9.50%；但采用 Handover和Cell ID定位方法后，其車速評估平均誤差則分別為77.98%和85.32%.由結果顯示指紋定位算法相較于Handover和Cell ID定位方法將可提供顯著的車速評估準確率，因此本研究將采用指紋定位算法進行車速評估.

表2 車速評估準確率比較表

2.3 車速信息回報率分析

在國道1號北上方向41.5km處的車輛偵測器收集了2008年7月每天從0時到24時的資料，假設通話到達率為1call／h，平均通話時間為1 min／call，這是一般的通話行為.目標路段為5km，此為高速公路上之交流道間的平均距離，以此作為路段間距.該車速信息回報率與車速呈反比，這意味著當交通擁塞或交通流量很低時，車速信息回報率相對會較高.其中當嚴重交通擁塞時，預期的車速信息回報率可能每5min有8個以上.因此當交通擁塞時，越能實時反應出塞車路況.而且依2008年7月每天從0時到24時的數據仿真可得平均每5min有3.27次車速信息回報，故此方法相較于車輛偵測器每5min回報1次更為實時.

2.4 云計算效率分析

本研究主要采用2組數據集合進行云計算環境效率，分別為小數據集合（6 299列×96欄）和大數據集合（100 000列×5 000欄），并將數據停存為文本文件格式放置到Hadoop平臺上，依此數據進行指紋定位算法計算.其中，由于此實驗主要進行效率分析，故在大數據集合的部分主要采用隨機產生的方式取得.最后，設計3個實驗環境，分別為：（1）單機執行；（2）一個Data Node＋多個 Worker Nodes、；（3）多個Data Nodes＋多個Worker Nodes，以進行云計算之效率測試，分述如下.

數據集合主要可分為2組：（1）小數據集合（6 299列×96欄）：以4.1之于實驗路段共來回路測12趟取得的6 299筆資料之各個細胞的訊號強度，其中共鏈接到96個不同的細胞（cell）；（2）大數據集合（100 000列×5 000欄）：以隨機的方式產生100 000筆數據，并分別產生各個細胞的訊號強度，令數據總共鏈接到5 000個不同的細胞（cell）.

本研究設計3個實驗環境：（1）單機執行，采用1臺中央處理器為4核心2.5GHz且主存儲器4GB之計算機進行運算；（2）1個Data Node＋多個Worker Nodes：將訓練數據儲存成1個文本文件，并將此文本文件放置到Hadoop平臺上，最后采用3.2之云計算算法，由多個 Worker Nodes進行指紋定位算法計算；（3）多個Data Nodes＋多個Worker Nodes：將訓練資料切割成多個文本文件，并將此文本文件放置到Hadoop平臺上，且觀察每個檔案存放的Data Node位置，確認文本文件分別存放于不同的Data Nodes上，最后再采用3.2之云計算算法，以多個 Worker Nodes進行指紋定位算法計算.

實驗中采用的Hadoop平臺主要以國網中心所提供之Hadoop環境進行實作，其中共包含了16個Nodes.將3.2之云計算算法進行實作，并放置到國網中心Hadoop平臺執行［10］，當執行完成后可于系統中觀察每個Job的運行時間，如圖3所示，并以此時間作為效率比較的依據.

圖3 車速評估準確率比較表

表3為2組數據集合于3個不同的實驗環境之執行效率比較，由實驗結果可以觀察到當在小數據集合時，采用單機執行將會比Hadoop平臺執行來得有效率.其中，當小數據集合時，其實驗環境2（一個Data Node＋多個 Worker Nodes）和實驗環境3（多個Data Nodes＋多個 Worker Nodes）之運行時間相同，故可以觀察出國網中心Hadoop運行時間最少需花21s，因此若該程序在單機執行低于21s可以完成的話，則此程序不需建置到Hadoop平臺上.而當大數據集合時，其在單機執行將花費大量的計算時間，而此時Hadoop平臺執行效將可以被突顯出來，由實驗數據顯示實驗環境3（多個Data Nodes＋多個Worker Nodes）的27s將可以比實驗環境1（單機執行）的176s快6.5倍.其中，又由于實驗環境2（1個Data Node＋多個Worker Nodes）將數據存放于同1個Data Node，造成其他Worker Nodes要向同1個Node取得數據，故使得執行效率較實驗環境3（多個Data Nodes＋多個 Worker Nodes）來得差.因此，由實驗數據可知，在Hadoop平臺執行程序時，需將數據存放在多個Data Nodes，并且當大數據集合才具效率.

表3 云計算環境效率比較表 s

3 結束語

本研究提出一個結合指紋定位的智能型運輸系統，運用行動網絡中的位置服務訊號，并提出指紋定位算法，在實驗中以快速道路66號路段進行實際路測，先針對單一手機進行驗證，其指紋定位算法位置估計誤差的可達36.11km，車速評估的平均誤差可達3.39%，提供較3GPP于標準中所定義之Cell ID定位方法更準確的位置和車速準確度.此外，采用云計算進行平行處理，可有效改善指紋定位算法需要大量運算的限制，以提供實時且可靠的交通信息，予以用路人參考.

未來的研究方向可以針對交通信息收集范圍擴大至全臺灣，收集全臺灣各地的行動網絡訊號，并依本研究所提出之云計算以平行處理方式進行指紋定位算法，以有效提供各地區之實時交通信息.并且，可于此實時交通信息上建構行動導航相關的加值服務與應用，提供使用者到達目的地的最適路徑規劃，以避開壅塞路段，提高用路品質.

［1］CACERES N，WIDEBERG J P，BENITEZ F G.Deriving origin－destination data from a mobile phone network［J］.IET Intelligent Transport Systems，2007（1）：15－26.

［2］CACERES N，WIDEBERG J P，BENITEZ F G.Review of traffic data estimations extracted from cellular networks［J］.IET Intelligent Transport Systems，2008（3）：179－192.

［3］MAERIVOET S，LOGGHE S.Validation of travel times based on cellular floating vehicle data［C］∥The 6th European Congress and Exhibition on Intelligent Transport Systems and Services（ITS），Aalborg，Denmark，June 18－20，2007.

［4］CHEN CH，CHANG H C，SU C Y，et al.Traffic speed estimation based on normal location updates and call arrivals from cellular networks［J］.Simula－tion Modelling Practice and Theory，2013，35（1）：26－33.

［5］CHEN C H，LIN B Y，LIN C H，et al.A green positioning algorithm for campus guidance system［J］.International Journal of Mobile Communications，2012，10（2）：119－131.

［6］CHEN C H，LIN B Y，CHANG H C，LO C C.The novel positioning algorithm based on cloud computing－a case study of intelligent transportation systems［J］.Information－An International Interdisciplinary Journal，2012，15（11（A））：4519－4524.

［7］BAR－GERA H.Evaluation of a cellular phone－based system for measurements of traffic speeds and travel times：a case study from Israel［J］.Transportation Research Part C，2007，15（6）：380－391.

［8］GUNDLEG?ARD D，KARLSSON J M.Handover location accuracy for travel time estimation in GSM and UMTS［J］.IET Intelligent Transport Systems，2009，3（1）：87－94.

［9］DEAN J，GHEMAWAT S.Mapreduce：simplified data processing on large clusters［J］.Communication of ACM，2008，51（1）：107－113.

［10］國網中心 Hadoop公用實驗叢集（2012）［M／OL］.http：／／hadoop.nchc.org.tw／，Retrieved February，2013.