指纹定位应用于智能运输系统之可行性＊

陈志华 林邦晔 郭庭欢 罗济群

（国立交通大学资讯管理研究所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.