廖山河，趙欽佩，李江峰，饒衛(wèi)雄

(同濟大學(xué)軟件學(xué)院，上海 201804)

1 引言

近年來，手機已深入大眾生活，隨著越來越多的智能手機應(yīng)用需要位置信息來提供基于位置的服務(wù)，室外定位已經(jīng)成為生活中不可或缺的一部分。

目前使用最廣泛的定位方式是GPS(Global Positioning System)定位，普通手機上的GPS傳感器平均定位精度能夠達到10 m左右。但是GPS定位技術(shù)還存在幾個方面的缺陷：(1)能量消耗迅速[1]；(2)在高樓林立的市區(qū)、地下及室內(nèi)等地方信號不好；(3)一些手機沒有GPS模塊；(4)定位通過手機端的GPS傳感器模塊才能獲得?？紤]到GPS定位的這些缺點，不依賴GPS的定位方式被不斷提出。

特別值得注意的是，電信運營商雖然為手機用戶提供通話和數(shù)據(jù)服務(wù)，但卻無法知曉用戶手機端的精確GPS位置，比如用戶在通過4G數(shù)據(jù)網(wǎng)絡(luò)使用百度地圖或高德地圖等手機端應(yīng)用程序進行導(dǎo)航時，即使用戶開啟了GPS傳感器，運營商后臺也無法獲取手機端的GPS經(jīng)緯度位置。因此，工業(yè)界和學(xué)術(shù)界提出了不少定位算法，利用電信數(shù)據(jù)來獲取手機用戶端的位置信息。

電信數(shù)據(jù)指的是手機接收到的基站的各種信息，主要包括基站ID信息和基站信號強度信息兩類，在用戶通話或者使用流量上網(wǎng)時，運營商的后臺可以獲取這些數(shù)據(jù)。相比于GPS定位，利用電信數(shù)據(jù)進行定位的優(yōu)點在于：(1)能耗低，手機其實是隨時都在接收基站信號的，收集這些信息的額外能耗接近于零；(2)網(wǎng)絡(luò)覆蓋范圍好，在室內(nèi)或地下也可能有基站信號；(3)普適性好，幾乎所有的手機都能接收基站信號；(4)數(shù)據(jù)的便捷性，運營商后臺和用戶手機端都能直接獲取電信數(shù)據(jù)。如果能夠利用好電信數(shù)據(jù)的這些優(yōu)勢，并通過一些新的算法來提高基于電信數(shù)據(jù)的室外定位的精度，那么將會有非凡的意義。

基于上述，本文的主要工作是利用電信數(shù)據(jù)，通過不同方法實現(xiàn)手機端的室外定位并進行實驗評估。具體來說，本文的貢獻包括以下幾個方面：

(1)實現(xiàn)了一種指紋定位算法與兩種機器學(xué)習(xí)的方法，在真實數(shù)據(jù)的實驗基礎(chǔ)上綜合各種方法的優(yōu)點，得到了一種定位效果非常好的機器學(xué)習(xí)模型——基于區(qū)域柵格化的隨機森林分類模型，使用該模型在我們收集到的數(shù)據(jù)上能夠達到平均誤差15～20 m，中位誤差10 m的定位精度。

(2)通過對收集數(shù)據(jù)時不同的運動模式及建模時不同的特征進行對比，證明了基站信號相較于其他傳感器數(shù)據(jù)——地磁傳感器信號，更加適合作為定位的依據(jù)。

(3)基于對數(shù)據(jù)的異常檢測和聚類，探索了修復(fù)原始采樣數(shù)據(jù)的方法。

本文內(nèi)容安排如下，第2節(jié)概述國內(nèi)外相關(guān)工作取得的成果和不足；第3節(jié)給出五種定位算法的具體實現(xiàn)；第4節(jié)進行實驗與評估；最后，第5節(jié)總結(jié)本文工作及對未來工作進行展望。

2 相關(guān)工作

由于室外定位在現(xiàn)實中扮演著無法替代的角色，所以國內(nèi)外在這方面都有大量的研究工作。針對GPS耗電量高的缺點，可以采用間隔啟用GPS或者按需啟用GPS的形式，Paek等人[2]在2010年時提出了針對智能手機應(yīng)用的速率自適應(yīng)定位系統(tǒng)RAPS(Rate-Adaptive Positioning System)，RAPS使用一系列技術(shù)巧妙地確定何時打開GPS，它還采用了celltower-RSS(Received Signal Strength)黑名單來檢測GPS的不可用性(例如在室內(nèi))，并避免在這些情況下打開GPS，最終RAPS可以在GPS始終處于開啟狀態(tài)的情況下將手機待機時間提高3.8倍以上。

對于在室外時不使用GPS，利用基站進行定位的研究，目前大概有三類解決問題的方法。

第一類是基于測量計算的方法[3]。其基本思想是通過估計點對點絕對值距離或估計基站信號的角度來計算位置。經(jīng)典方法包括到達角方法AOA(Angle of Arrival)[4]、到達時間方法TOA(Time of Arrival)[5]和基于接收信號強度(RSS)的單源定位[6]。具體地，Yang等人[7]進行了基于基站的三角定位實驗，但是實驗結(jié)果并不令人滿意。Quattrone等人[8]于2015年提出一種綜合了測距方法(Range-based)與無測距方法(Range-free)的兩層定位模型，基于測距的方法依賴于采用幾何技術(shù)的可靠測量，實際應(yīng)用中測量非常容易受到誤差的影響，無測距的方法不考慮實際的距離，而是比較傳感器的幅度，但可能導(dǎo)致錯誤的累積。因此，該論文綜合兩者，首先使用基于測距的方法來確定近似位置，然后采用無測距的方法來進一步優(yōu)化定位。Perera等人[9]也于同年提出了一種利用手機的主連接基站推斷用戶運動軌跡的方法，該方法只需要用戶連接的主基站位置、時間和速度這幾種信息，便可以計算出用戶行進的距離，以此來推斷軌跡的直線段和轉(zhuǎn)折點。本方法的好處是不需要任何歷史軌跡信息或訓(xùn)練，降低了存儲和計算成本，但其缺點在于要想確定一條軌跡需要至少三個連續(xù)基站服務(wù)范圍的信息，而用戶需要定位時顯然不可能移動這么遠的距離，因此該方法無法直接用于定位。總的來說，這些方法的計算往往不是很復(fù)雜，但是需要高精度的測量，因此實際應(yīng)用中定位精度較弱。

第二類是基于指紋識別的方法[10]。所謂指紋是指用于區(qū)分不同位置或區(qū)域的唯一依據(jù)。Quoc Vo和De兩位IEEE成員[11]在2015年的文章中總結(jié)了當(dāng)時所有的基于指紋識別的室外定位系統(tǒng)，它們使用通過傳感器(如加速度計、麥克風(fēng)、羅盤甚至日志)收集的數(shù)據(jù)來建立標(biāo)識用戶設(shè)備的唯一簽名，并統(tǒng)計大量的數(shù)據(jù)建立指紋數(shù)據(jù)庫，隨后采用指紋識別的方法來定位用戶設(shè)備。該論文中總共提出了三類指紋：一是視覺指紋，數(shù)據(jù)來源于照片或者視頻，可以通過手機攝像頭采集；二是運動指紋，數(shù)據(jù)來源包括通過加速度計得到的運動狀態(tài)信息(運動或靜止)，和通過電子羅盤或陀螺儀得到運動方向信息(直行或轉(zhuǎn)彎)；三是信號指紋，數(shù)據(jù)來源包括WIFI接入點的信號、基站信號強度等。利用信號指紋進行定位不僅計算速度快，而且耗電量小，Cellsense是其中的代表方法[12]，它將城市區(qū)域劃分成一個個小的柵格，使用各個柵格里的基站信號強度RSSI(Received Signal Strength Indicator)的分布作為該柵格里的指紋。

第三類是基于機器學(xué)習(xí)的方法[13]。該類方法通過訓(xùn)練帶位置信息標(biāo)簽的數(shù)據(jù)得到一個模型，之后就能利用該模型預(yù)測新數(shù)據(jù)的位置。在最近的工作中，Zhu等人[14]提出了一個基于Spark/Hadoop電信大數(shù)據(jù)平臺的上下文感知回歸模型，該模型是一個兩層的隨機森林模型，能夠達到110 m的平均誤差和80 m的中位誤差。近期工作[15]提出定位后位置修復(fù)步驟，進一步優(yōu)化定位精度。

目前不使用GPS進行定位的方法取得了很多成果，但是也存在不足，詳細地比較各類方法能夠幫助我們選擇合適的方法進行移動定位[16]。普通手機GPS的定位精度能達到10 m，而上述提到的第一類方法，由于實際使用中的誤差，精度遠遠達不到這個級別。第二類方法中綜合使用多種類型的指紋可以使定位精度達到十幾米，但僅僅使用基站信號強度作指紋的精度仍然在40 m左右?；拘盘枏姸戎讣y與其他類型指紋的區(qū)別在于，其他類型的指紋數(shù)據(jù)只能在手機端收集，而基站信號強度指紋不僅可以在手機端收集，也可以在運營商的后臺獲取，兩端可以獨立地進行定位，這是它的一個巨大優(yōu)勢。對于第三類方法，我們利用機器學(xué)習(xí)模型(例如隨機森林、神經(jīng)網(wǎng)絡(luò)等)進行室外定位的預(yù)測和對比，并且綜合考慮第二類與第三類方法，既然指紋法可以將區(qū)域劃分成柵格，并以柵格為目標(biāo)進行定位預(yù)測，那么使用機器學(xué)習(xí)方法時也能利用該思路，將區(qū)域劃分成柵格，從而不同于前期工作直接預(yù)測GPS經(jīng)緯度位置的回歸模型，而是根據(jù)分類的機器學(xué)習(xí)模型(預(yù)測用戶位置在哪個柵格里)來解決定位的問題。

3 室外定位算法

本節(jié)首先簡介本文工作的整體框架及相關(guān)術(shù)語，在3.2節(jié)中將會敘述如何實現(xiàn)一種基于指紋的定位方法Cellsense，這種方法將區(qū)域劃分成大小相等的網(wǎng)格，預(yù)測時通過選擇概率最大的網(wǎng)格來確定目標(biāo)所在的位置。3.3節(jié)和3.4節(jié)分別介紹隨機森林與多層感知器兩種模型的應(yīng)用，基于這兩種模型我們使用了分類和回歸兩種方法。成功建立模型并預(yù)測之后，在3.5節(jié)探索了兩種數(shù)據(jù)的后處理方法。

3.1 基本概念

本文所用的術(shù)語如表1所示，定位工作的數(shù)據(jù)全部由Android手機平臺采集，整體流程框架如圖1所示。

當(dāng)手機與運營商的網(wǎng)絡(luò)連接時，MR數(shù)據(jù)記錄了手機的連接信息，這種連接信息包含基站(BS)的信息和信號強度數(shù)據(jù)。每條MR記錄都包含至少一個基站的信息，通常情況下一條MR記錄中有1到6個基站。其中，當(dāng)前與手機連接的基站稱

Figure 1 Framework of telecom data-based outdoor positioning圖1 利用電信數(shù)據(jù)進行室外定位的框架

術(shù)語含義MR測量報告(MeasurementReport)數(shù)據(jù),指的是手機所收集到的和基站有關(guān)的數(shù)據(jù)BSBaseStation,即基站IMSIInternationalMobileSubscriberIdentity,國際移動用戶識別碼RSSIRadioSignalStrengthIndex,基站信號強度值RFRandomForest,隨機森林MLPMultilayerPerceptron,多層感知器CDFCumulativeDistributionFunction,累積分布函數(shù)

為主連接基站，而其他非主連接基站則稱為鄰接基站。手機的服務(wù)由主連接基站提供，當(dāng)手機的持有者移動而使得手機超出當(dāng)前主連接基站的服務(wù)范圍時，主連接基站會從當(dāng)前基站切換至鄰接基站中的某一個。在本文所使用到的數(shù)據(jù)中，保證MR記錄中基站列表里的第一個基站即是主連接基站。本文所使用到的MR數(shù)據(jù)格式如表2所示，Longitude和Latitude字段來自于手機GPS傳感器，作為標(biāo)簽(Label)用于訓(xùn)練模型和測試時評估誤差；MRTime記錄采集的時間；IMSI用于區(qū)分不同的電話卡，在實際情況下，電話卡與手機之間往往是綁定關(guān)系，因此也同時區(qū)分了不同的手機；而以加數(shù)字結(jié)尾的字段均是基站信號的相關(guān)測量值，其中數(shù)字從1到6表示6個鄰接基站(包括主連接基站)。

3.2 基于指紋識別的定位方法

指紋是用于識別某個特定位置或區(qū)域的依據(jù)。基于指紋識別的移動定位方法就是利用收集的數(shù)據(jù)構(gòu)建不同地點的指紋，預(yù)測時將MR記錄與各個不同的指紋進行比較，選擇指紋最相符的地點作為預(yù)測位置。

Cellsense[12]是目前最先進的一種基于指紋識別的移動定位方法。它將城市區(qū)域劃分為小網(wǎng)格，每個網(wǎng)格由該網(wǎng)格內(nèi)手機連接到的每個基站的RSSI分布組成的指紋表示。對于網(wǎng)格中的每個基

Table 2 Example of MR data表2 MR數(shù)據(jù)示例

站，將其RSSI分布設(shè)置為正態(tài)分布。當(dāng)訓(xùn)練數(shù)據(jù)不足時，通過正態(tài)分布填充缺失值。Cellsense具體可以按照以下步驟實現(xiàn)：

(1)確定預(yù)測區(qū)域的范圍，將預(yù)測區(qū)域劃分為若干個正方形的柵格。

(2)訓(xùn)練模型：①將每條MR數(shù)據(jù)轉(zhuǎn)換為三元組〈基站列表，RSSI列表，GPS坐標(biāo)〉；②利用前面的結(jié)果，判斷每條MR數(shù)據(jù)落在哪個柵格里，以此構(gòu)建每個柵格各自的數(shù)據(jù)集合；③在每個柵格里，分別對每個基站對應(yīng)的RSSI列表計算概率分布函數(shù)，如果一個柵格里有K個基站，那么就會有K個概率分布函數(shù)。

3.3 基于隨機森林的定位模型

隨機森林(RF)是一種由多個獨立的決策樹組成的模型，在本文工作中，我們利用MR數(shù)據(jù)中的信號測量作為特征，將位置點或位置網(wǎng)格用作訓(xùn)練機器學(xué)習(xí)模型的標(biāo)簽。位置點(即經(jīng)度和緯度)可以通過回歸模型預(yù)測，位置網(wǎng)格可以通過分類模型預(yù)測。

隨機森林不需要用到MR數(shù)據(jù)的全部特征，但需要對特征做適當(dāng)?shù)奶幚?，因此在?xùn)練模型之前要先進行特征提取的工作。特征提取的來源分為兩部分，來源之一是手機所收集到的MR數(shù)據(jù)，來源之二是運營商提供的工參表數(shù)據(jù)，主要包含了每個基站的GPS坐標(biāo)(經(jīng)度和緯度)。將基站的經(jīng)緯度加入，豐富特征，能夠提高預(yù)測的效果。

回歸模型根據(jù)MR數(shù)據(jù)和工參表提取的特征直接預(yù)測用戶GPS坐標(biāo)。

建立RF回歸模型時，根據(jù)多次實驗結(jié)果確定隨機森林的參數(shù)，樹的數(shù)量設(shè)置為100，樹分裂時選取的特征數(shù)量設(shè)為總特征數(shù)的60%，評判分裂的效果時使用均方誤差MSE(Mean Square Error)，生成樹使用bootstrap方法。

利用隨機森林進行定位的另一種方法是建立分類模型。與利用指紋識別進行定位時的思想相似，將整個目標(biāo)區(qū)域劃分成多個柵格，此時預(yù)測目標(biāo)從GPS經(jīng)緯度變?yōu)轭A(yù)測用戶在哪個柵格里，也從回歸問題變成了分類問題。假設(shè)柵格的邊長為D，并取柵格的中心作為每個柵格里所有數(shù)據(jù)的GPS坐標(biāo)，那么在預(yù)測正確的情況下，預(yù)測值與真實值之間的誤差最大大約為0.7*D，因此可以通過調(diào)整柵格的邊長參數(shù)來實現(xiàn)定位精度與模型復(fù)雜度之間的取舍。

建立RF分類模型時，根據(jù)多次實驗結(jié)果確定參數(shù)，柵格的邊長設(shè)置為30 m，樹的數(shù)量設(shè)置為100，樹分裂時選取特征數(shù)量設(shè)為總特征數(shù)量的平方根，評價分裂效果時使用信息增益(Information Gain)作為指標(biāo)，生成樹使用bootstrap方法。

3.4 基于多層感知器的定位模型

多層感知器(MLP)是一種簡單的前饋神經(jīng)網(wǎng)絡(luò)，本文使用了一個由一個輸入層、一個隱藏層、一個輸出層組成的三層MLP，用到的兩種激活函數(shù)如圖2所示。在隱藏層中，我們使用Relu(Rectified linear units)作為激活函數(shù)[17]。

與使用隨機森林模型相似，我們分別建立回歸模型與分類模型?；贛LP的回歸模型直接根據(jù)輸入特征預(yù)測用戶的GPS坐標(biāo)，因此輸出層不需要使用激活函數(shù)。Keras包提供了現(xiàn)成的工具來構(gòu)造神經(jīng)網(wǎng)絡(luò)，本文使用Theano[18]做后端，隱藏層的激活函數(shù)選擇Relu，神經(jīng)網(wǎng)絡(luò)迭代次數(shù)設(shè)置為20次。

基于MLP的分類模型建立在區(qū)域柵格化的基礎(chǔ)上，為了應(yīng)用到MLP中，輸出層使用Softmax作為激活函數(shù)[19]，以保證輸出的是落入各個柵格里的概率并且相加等于 1。最終選擇概率最大的柵格作為用戶所在的柵格，并將柵格的中心坐標(biāo)作為用戶的GPS坐標(biāo)。構(gòu)建分類MLP時，柵格的邊長設(shè)置為30 m，隱藏層的激活函數(shù)選擇Relu，神經(jīng)網(wǎng)絡(luò)迭代次數(shù)設(shè)置為20次。

3.5 數(shù)據(jù)的后處理

上面的工作實現(xiàn)了基于兩種模型通過MR數(shù)據(jù)預(yù)測用戶位置的方法，它們都能從訓(xùn)練集學(xué)習(xí)一個模型用于預(yù)測。但是，預(yù)測結(jié)果誤差小的前提是手機收集到的MR數(shù)據(jù)是真實的，或者說因為設(shè)備原因造成的測量誤差在允許范圍內(nèi)，如果用于訓(xùn)練的MR數(shù)據(jù)本身是不準(zhǔn)確的，那么訓(xùn)練得到的模型自然就會出現(xiàn)偏差，用于實際應(yīng)用時，因為設(shè)備不同造成測量值不同，進一步造成預(yù)測得到的結(jié)果不準(zhǔn)確。另外，考慮到除了基站信號以外，手機內(nèi)置的傳感器還能收集地磁信號等數(shù)據(jù)，基站信號強度數(shù)據(jù)和地磁信號數(shù)據(jù)在物理環(huán)境中的分布是否有特定的規(guī)律，以及這種規(guī)律是否可以用于提高定位的精度，也是一個值得探索的問題。

因此，數(shù)據(jù)的后處理部分主要包括兩方面：(1)針對MR數(shù)據(jù)和地磁信號數(shù)據(jù)的測量值，用一種異常檢測的辦法找出與絕大多數(shù)數(shù)據(jù)相差比較大的采樣點，并對這些采樣點的數(shù)據(jù)進行修復(fù)；(2)對MR基站信號數(shù)據(jù)進行聚類，探索是否存在一種固定的聚類模式，能夠反映RSSI在物理環(huán)境中的分布情況，即每次聚類的中心點是否是大致確定的。對于以上兩方面，異常檢測得到的異常點和聚類得到的類中心點，如果它們存在一定的固定規(guī)律，能夠用于定位大致位置，則將其稱之為錨點(Anchor Point)。這部分工作參考了Dejavu系統(tǒng)[20]，該系統(tǒng)是國外已有的成功案例。

3.5.1 異常點檢測

錨點定義為多個點中的特異點，與絕大多數(shù)點的數(shù)據(jù)差異較大，本文中利用異常檢測尋找錨點的思路為：

找出異常的特征值后，可以對這些點的數(shù)據(jù)以線性插值的方式進行修復(fù)。

3.5.2 基于聚類的錨點

每條MR記錄構(gòu)成一個向量v=([CID1,RSSI1],…,[CIDN,RSSIN])，通過計算兩個基站信號強度向量的距離可以將所有的數(shù)據(jù)聚成不同的類，此為第一層聚類。之后，在不同的類簇中，依據(jù)MR記錄的位置進行空間聚類，把在同一塊區(qū)域中的MR數(shù)據(jù)聚到一起，此為第二層聚類。

第一層聚類時，使用層次聚類的方法，不同MR向量之間的距離計算公式如式(1)所示：

(1)

其中，A表示在兩條MR記錄中出現(xiàn)的基站的并集，fi(a)表示基站a在MR記錄i中對應(yīng)的RSSI值，如果在MR記錄i中未接受到基站a，則fi(a)=0。式(1)的取值在0～1。計算類與類之間的距離時使用平均連接法(Average Linkage Method)，當(dāng)距離小于某個設(shè)定的閾值時停止聚類，本文中取值為0.3。

經(jīng)過第一層聚類后，即使是相同的類，點之間的實際距離也可能相差很遠，因此需要在每個類中再進行空間聚類，以便把同一區(qū)域中的相似點聚到一起。為了減少異常值的影響，在兩層聚類中都只有在類中點的數(shù)量足夠多時才接受。在第二層聚類時，也使用了層次聚類的方法，設(shè)定一個區(qū)分不同類的最大距離閾值，超過這個距離之后不再聚到同一個類中，在本文的工作中，該距離設(shè)置為20 m。聚類完成后，取每個類中所有點的中心作為該類的代表位置。

4 實驗與評估

4.1 實驗設(shè)置

4.1.1 實驗環(huán)境

實驗的軟硬件參數(shù)如表3所示。

Table 3 Experiment settings表3 實驗環(huán)境設(shè)置

4.1.2 數(shù)據(jù)集描述

實驗所用到的數(shù)據(jù)收集于同濟大學(xué)嘉定校區(qū)，如圖2所示，收集數(shù)據(jù)時使用了7部手機以及走路(Walk)、跑步(Run)、騎自行車(Bicycle)、開車(Car)四種運動模式，并針對不同的信號制式(2/3/4G網(wǎng)絡(luò))進行了收集。數(shù)據(jù)的總量一共有149.1 MB，包含了55個子數(shù)據(jù)集，每個子數(shù)據(jù)集對應(yīng)一次數(shù)據(jù)收集工作，覆蓋的路徑長度為4.5 km。因為工參表只有2/4G基站的參數(shù)，因此在實驗中使用的是2/4G的數(shù)據(jù)，在實驗前，先對2/4G數(shù)據(jù)進行基本的統(tǒng)計，表4展示了2/4G數(shù)據(jù)MR記錄的統(tǒng)計結(jié)果，表5展示了2/4G基站的統(tǒng)計結(jié)果。

Figure 2 Locations of sampling points圖2 數(shù)據(jù)采集點分布示意圖

信號制式數(shù)據(jù)量/條手機到主基站距離中位值/m主基站RSSI平均值/dBmGSM(2G)32813977.88-75.12LTE(4G)16491453.79-85.96

Table 5 Statistics of 2/4G base stations表5 對2/4G基站的統(tǒng)計

4.1.3 評估標(biāo)準(zhǔn)

在實驗中我們使用預(yù)測位置和真實位置之間的地球表面距離來判斷定位效果的好壞，將其稱為定位誤差。由GPS經(jīng)緯度坐標(biāo)計算兩點間距離的方法如式(2)所示。

S=2×arcsin

(2)

其中，lat1、lat2分別表示兩個點的緯度，a=lat1-lat2為兩點緯度之差，b=lon1-lon2為兩點經(jīng)度之差，r為地球近似半徑，取6 378.137 km。

4.1.4 實驗流程

本節(jié)首先對各種方法進行實驗，給出各個方法效果的一個直觀印象，包括定位精度和運行時間；之后會選擇效果好的方法，進一步對收集數(shù)據(jù)時的運動模式、采用的特征的影響進行實驗；最后，比較經(jīng)過后處理的數(shù)據(jù)與原數(shù)據(jù)的定位精度。進行實驗時，每種方法都采用十次交叉驗證的方式得到最后的結(jié)果，并且結(jié)果以表格或者CDF曲線的形式展現(xiàn)。

4.2 不同方法定位精度的比較

首先，我們對不同方法的預(yù)測精度進行比較，作為一個基準(zhǔn)實驗(Benchmark)。如圖3和圖4所示，圖中橫軸表示定位誤差，即預(yù)測點與真實點之間的直線距離，單位為m；縱軸表示各階段誤差數(shù)據(jù)比例的累計分布函數(shù)值。舉例來說，縱軸(CDF)取0.5表示中位誤差，此時橫軸對應(yīng)的誤差值為E，則意味著50%的數(shù)據(jù)定位誤差在E以下。該圖對應(yīng)的數(shù)值結(jié)果可以參照表6，p67為171.22 m表示67%的數(shù)據(jù)定位誤差在171.22 m以下，p80與p90同理。表中加粗的數(shù)據(jù)為每階段最好的結(jié)果。

Figure 3 Localization accuracy of different methods on 2G data圖3 不同方法在2G數(shù)據(jù)上的定位誤差

Figure 4 Localization accuracy of different methods on 4G data圖4 不同方法在4G數(shù)據(jù)上的定位誤差

信號制式方法平均誤差/m中位誤差/mp67/mp80/mp90/m2GCellsense180.1970.80171.22328.41526.422GRFclassification19.1510.0813.1516.9825.412GRFregression31.6320.6229.5640.9260.432GMLPclassification92.0154.6089.40143.80223.202GMLPregression157.22130.40180.80234.60305.104GCellsense159.45106.58206.32290.41359.984GRFclassification14.508.9712.2916.0426.364GRFregression31.7220.6829.7240.9560.734GMLPclassification127.84110.95157.30205.20244.004GMLPregression156.46129.10182.30238.50300.40

分析實驗結(jié)果可以得出以下結(jié)論：

(1)首先從圖中可以看出，2G數(shù)據(jù)與4G數(shù)據(jù)有相同的規(guī)律：很明顯RF的定位精度要遠遠高于MLP與Cellsense的定位精度，而MLP與Cellsense相比較，只有少部分?jǐn)?shù)據(jù)的Cellsense預(yù)測精度要比MLP的預(yù)測精度好，而當(dāng)比較整體的預(yù)測精度時(超過53%的數(shù)據(jù))，MLP還是要比Cellsense更勝一籌。這是因為Cellsense是一種基于統(tǒng)計的方法，需要能夠明確地區(qū)分各個柵格，收集數(shù)據(jù)時的路徑實際上是一個環(huán)狀的，環(huán)內(nèi)部的基站信號強度數(shù)據(jù)并沒有收集到，在構(gòu)建各個柵格的指紋時，有一些柵格因為數(shù)據(jù)稀少或者缺失，無法構(gòu)建能有效區(qū)分自己與其他柵格的指紋，因此定位時只有一些特征很明顯的MR數(shù)據(jù)才被預(yù)測到了正確的柵格里，而其他的MR數(shù)據(jù)由于不同柵格太相似，在預(yù)測時出現(xiàn)了錯誤，導(dǎo)致誤差很大。相比之下，MLP學(xué)習(xí)得到的模型雖然在一些位置的預(yù)測精度比不上Cellsense的預(yù)測精度，但從整體來看，它能更深層次地挖掘特征與位置的關(guān)系，因此總體效果更好。

(2)其次，比較分類與回歸方法可以看出，不管是RF模型還是MLP模型，分類的效果都要優(yōu)于回歸的效果，例如,RF classification與RF regression相比,在2G和4G數(shù)據(jù)上分別有39.46%和54.28%的精度提升。這是因為在柵格化之后，每一類(每個柵格)數(shù)據(jù)的共性能夠更好地被發(fā)現(xiàn)，因此預(yù)測數(shù)據(jù)屬于哪個柵格比預(yù)測其具體GPS坐標(biāo)要準(zhǔn)確得多。

(3)最后，對比2G與4G兩種信號制式可以發(fā)現(xiàn)，同一種方法對4G數(shù)據(jù)的定位精度要高于2G數(shù)據(jù)的定位精度，參照表4和表5可以發(fā)現(xiàn)，這是因為4G的基站到手機的距離以及基站之間的距離都比2G的小，即基站密度更大，在這種情況下，即使4G的信號弱于2G，定位精度也比2G高。

4.3 不同方法運行時間的比較

如圖5所示是五種方法在2/4G數(shù)據(jù)上進行實驗各自的運行時間，橫軸表示不同的信號制式和不同的方法，縱軸表示算法運行的時間，以s為單位。由于實驗中均采用十次交叉驗證的方式，因此由每種方法運行時間除以10作為單次運行時間。很明顯，MLP classification方法所用的時間最長，其次是Cellsense，而隨機森林模型不管是進行分類還是回歸，運行時間都很短。

Figure 5 Efficiency of different approaches圖5 不同方法運行時間

另外，不管是RF還是MLP，分類方法的運行時間都大于回歸方法的，這也可以理解，因為分類方法在訓(xùn)練之前需要先劃分柵格，以及將訓(xùn)練集數(shù)據(jù)的GPS坐標(biāo)轉(zhuǎn)換為柵格的編號，預(yù)測之后又要將預(yù)測值從柵格編號轉(zhuǎn)換回GPS坐標(biāo)。

根據(jù)4.2節(jié)和本節(jié)的實驗可以清楚地發(fā)現(xiàn)，不論是2G數(shù)據(jù)集還是4G數(shù)據(jù)集，隨機森林分類模型在各方面都表現(xiàn)得非常優(yōu)秀，因此為了表述簡潔，后面進一步的實驗都只用隨機森林分類模型進行展示。

4.4 不同數(shù)據(jù)收集模式定位精度的比較

收集數(shù)據(jù)時采用了走路(Walk)、跑步(Run)、騎自行車(Bicycle)、開車(Car)四種運動模式，本節(jié)的實驗主要研究運動模式對預(yù)測精度的影響。圖6展示了RF分類方法對于2G數(shù)據(jù)不同運動模式的數(shù)據(jù)的預(yù)測結(jié)果，圖7是4G數(shù)據(jù)相應(yīng)的結(jié)果。

Figure 6 Effect of motion modes(2G data,RF classification)圖6 運動模式的影響(2G數(shù)據(jù)，隨機森林分類)

Figure 7 Effect of motion modes(4 Gdata,RF classification)圖7 運動模式的影響(4G數(shù)據(jù)，隨機森林分類)

很明顯，走路(Walk)與跑步(Run)的結(jié)果要優(yōu)于騎自行車(Bicycle)和開車(Car)的結(jié)果，這是因為收集數(shù)據(jù)的時間間隔是固定的，速度越快所收集數(shù)據(jù)的密度也就越低，在一塊很小的區(qū)域內(nèi)，可能就只有一兩條數(shù)據(jù)甚至沒有數(shù)據(jù)，自然定位誤差也就更大了。具體到不同的運動方式，速度關(guān)系為v(走路)

4.5 不同特征定位精度的比較

第二次收集的數(shù)據(jù)包含了地磁信號，考慮到地球磁場是有規(guī)律的，那么手機收集到的地磁信號數(shù)據(jù)是否存在一定的規(guī)律，能夠用來提升定位的精度呢？為了探究地磁信號對定位精度的影響，本節(jié)對地磁信號數(shù)據(jù)和基站信號數(shù)據(jù)的不同組合進行實驗，以對比不同特征對定位精度的影響。

針對基站特征和地磁數(shù)據(jù)特征，一共進行了四種特征組合的實驗：(1)以基站ID(CellID)和RSSI值作為特征；(2)以基站ID、RSSI值和地磁信號(geomag)作為特征；(3)以基站ID和地磁信號數(shù)據(jù)作為特征；(4)僅以地磁信號作為特征。從圖8和圖9可以看出，總的來說，加入地磁數(shù)據(jù)對提升定位精度并沒有顯著效果。在原本的特征上加上地磁數(shù)據(jù)作為新增的特征，最后得到的新CDF曲線與原曲線幾乎重合，表明地磁特征的引入無明顯作用；另一方面，對比CellID + Geomag曲線和Geomag曲線可以發(fā)現(xiàn)，相比于地磁數(shù)據(jù)，CellID對定位的作用更大，這是因為基站的位置與基站ID恒定不變，而地磁信號變化則大得多。

Figure 8 Effect of features(2G data,RF classification)圖8 特征對定位精度的影響(2G數(shù)據(jù),隨機森林分類)

Figure 9 Effect of features(4G data,RF classification)圖9 特征對定位精度的影響(4G數(shù)據(jù),隨機森林分類)

4.6 后處理對定位精度的影響

在3.5節(jié)，我們參考Dejavu系統(tǒng)提出了檢測數(shù)據(jù)異常點和聚類的后處理方法。實驗發(fā)現(xiàn)，針對不同子數(shù)據(jù)集RSSI聚類得到的聚類點分布相差較大，因此由RSSI聚類尋找錨點的方法不可行。而針對不同的子數(shù)據(jù)集進行異常檢測后得到的異常點分布相對來說，要稍微有規(guī)律一些，對異常點處的數(shù)據(jù)進行線性插值，將這種新的數(shù)據(jù)稱為修復(fù)數(shù)據(jù)。對MR數(shù)據(jù)中主連接基站信號強度(RSCP_1)實施異常點檢測，對比修復(fù)數(shù)據(jù)和原數(shù)據(jù)的定位效果如圖10和圖11所示。

Figure 10 Effect of RSCP_1 Repair(2G data,RF classification)圖10 異常修復(fù)RSCP_1數(shù)據(jù)(2G數(shù)據(jù),隨機森林分類)

Figure 11 Effect of RSCP_1 Repair(4G data,RF classification)圖11 異常修復(fù)RSCP_1數(shù)據(jù)(4G數(shù)據(jù),隨機森林分類)

從圖10和圖11中的結(jié)果可以看出，修復(fù)后的數(shù)據(jù)對定位精度的提升很小，只在2G數(shù)據(jù)上總體定位精度的最差情況下有少許提升。究其原因，是因為修復(fù)的數(shù)據(jù)量在總數(shù)據(jù)量中占比太少，實際上，對原來的每個子數(shù)據(jù)集，異常檢測得到的點少的只有幾個，多的也只有幾十個，相對于總的數(shù)據(jù)量來說，這些點的值即使修復(fù)了，對整體的影響也很小。

4.7 實驗總結(jié)

本節(jié)對收集到的數(shù)據(jù)進行了各種實驗。首先對比了五種方法：Cellsense、RF分類、RF回歸、MLP分類和MLP回歸，得到了各個方法效果的直觀印象，RF無疑是最優(yōu)的模型，而MLP和Cellsense相較而言效果要差一些，其中MLP的總體誤差比Cellsense更小，而分類的效果要好于回歸，當(dāng)然分類方法預(yù)測精度更高的代價是運行時間更長。之后我們又針對收集數(shù)據(jù)時的運動模式和建模時使用的特征進行了大量實驗并選取隨機森林分類模型展示實驗結(jié)果：對比不同運動模式，我們發(fā)現(xiàn)速度越慢、數(shù)據(jù)越密集的運動模式定位精度越高；對比不同的特征，發(fā)現(xiàn)地磁信號對定位精度的提升沒有明顯作用，這是因為手機上的地磁傳感器精度較差，且不同手機測得的數(shù)值差別也很大。最后，我們比較了經(jīng)過后處理的數(shù)據(jù)與原數(shù)據(jù)的定位精度，發(fā)現(xiàn)由于后處理修復(fù)的點的數(shù)量太少，因此前后定位精度相差很小。

5 結(jié)束語

為了實現(xiàn)基于電信數(shù)據(jù)的移動定位工作，本文基于收集的真實數(shù)據(jù)，選取Cellsense、RF分類、RF回歸、MLP分類和MLP回歸五種方法進行實驗。經(jīng)過大量的實驗，最終得到了隨機森林分類模型是在電信定位中效果最好的模型，不管是定位誤差還是運行速度都遠遠優(yōu)于Cellsense和多層感知器模型。在實際的應(yīng)用中，定位精度能夠達到25 m，在好的情況下甚至可以達到10 m。這種方法不僅定位精度高，而且只需要基站信號強度數(shù)據(jù)就可以實現(xiàn)，因此普適性非常好；同時相比于GPS定位，收集基站數(shù)據(jù)的耗電量也很少；此外，由于基站信號數(shù)據(jù)本身的便捷性，既可以在用戶的手機上利用該方法進行定位，也可以在運營商的后臺實現(xiàn)。我們通過實驗還證明了數(shù)據(jù)越密集，定位精度越高，因此可以通過調(diào)整數(shù)據(jù)采樣頻率進行精度與能耗的平衡。手機地磁數(shù)據(jù)對定位精度的提升不大，因為相較于基站信號的穩(wěn)定性，地磁信號的分布規(guī)律更難確定，且不同手機由于硬件的差異使得地磁測量值相差很多。

在本文的工作基礎(chǔ)上，未來還有以下幾個可以繼續(xù)研究的方面：(1)本文數(shù)據(jù)的覆蓋范圍還不夠大，只在特定區(qū)域進行實驗，下一步計劃在廣泛區(qū)域進行驗證；(2)目前根據(jù)GPS軌跡判斷運動模式的方法已經(jīng)很成熟了[21]，基于現(xiàn)有的工作，進一步地可以嘗試根據(jù)基站MR數(shù)據(jù)來判斷運動模式；(3)在定位的基礎(chǔ)上，可以進一步研究運動軌跡推測與軌跡地圖匹配。

參考文獻:

[1] Carroll A, Heiser G.An analysis of power consumption in a smartphone[C]∥Proc of USENIX Annual Technical Conference,2010:21.

[2] Paek J, Kim J,Govindan R.Energy-efficient rate-adaptive GPS-based positioning for smartphones[C]∥Proc of the 8th ACM International Conference on Mobile Systems,Applications,and Services,2010:299-314.

[3] Patwari N, Ash J N,Kyperountas S,et al.Locating the nodes:Cooperative localization in wireless sensor networks[J].IEEE Signal Processing Magazine,2005,22(4):54-69.

[4] Swales S C,Maloney J E,Stevenson J O.Locating mobile phones and the US wireless E-911 mandate[C]∥Proc of IEE Colloquium on Novel Methods of Location and Tracking of Cellular Mobiles and Their System Applications,1999:2/1-2/6.

[5] Lopes L,Viller E,Ludden B.Gsm standards activity on location[C]∥Proc of IEE Colloquium on Novel Methods of Location and Tracking of Cellular Mobiles and Their System Applications,1999:7/1-7/7.

[6] Vaghefi R M,Gholami M R,Str?m E G.RSS-based sensor localization with unknown transmit power[C]∥Proc of 2011 IEEE International Conference on Acoustics,Speech and Signal Processing(ICASSP),2011:2480-2483.

[7] Yang J,Varshavsky A,Liu H,et al.Accuracy characterization of cell tower localization[C]∥Proc of the 12th ACM International Conference on Ubiquitous Computing,2010:223-226.

[8] Quattrone A,Kulik L,Tanin E.Combining range-based and range-free methods:A unified approach for localization[C]∥Proc of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems,2015:49.

[9] Perera K,Bhattacharya T,Kulik L,et al.Trajectory inference for mobile devices using connected cell towers[C]∥Proc of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems,2015:23.

[10] Koshima H,Hoshen J.Personal locator services emerge[J].IEEE Spectrum,2000,37(2):41-48.

[11] Vo Q D,De P.A survey of fingerprint-based outdoor localization[J].IEEE Communications Surveys & Tutorials,2016,18(1):491-506.

[12] Ibrahim M,Youssef M.CellSense:An accurate energy-efficient GSM positioning system[J].IEEE Transactions on Vehicular Technology,2012,61(1):286-296.

[13] Witten I H,Frank E,Hall M A,et al.Data mining:Practical machine learning tools and techniques[M].2nd Edition. San Francisco:Morgan Kaufmann Publisher Inc,2016.

[14] Zhu F,Luo C,Yuan M,et al.City-Scale localization with Telco Big Data[C]∥Proc of the 25th ACM International Conference on Information and Knowledge Management,2016:439-448.

[15] Zhang Yi-ge,Rao Wei-xiong,Yuan Ming-xuan,et al.Confidence model-based data repair for telco localization[C]∥Proc of 2017 18th IEEE International Conference on Mobile Data Management(MDM),2017:186-195.

[16] Huang Yu-kun,Rao Wei-xiong,Zhu Fang-zhou,et al.Experimental study of telco localization methods[C]∥Proc of 2017 18th IEEE International Conference on Mobile Data Management(MDM),2017:299-306.

[17] Hahnloser R H R,Sarpeshkar R,Mahowald M A,et al.Digital selection and analogue amplification coexist in a cortex-inspired silicon circuit[J].Nature,2000,405(6789):947-951.

[18] Bergstra J,Breuleux O,Bastien F,et al.Theano:A CPU and GPU math compiler in Python[C]∥Proc of the 9th Python in Science Conference,2010:1-7.

[19] Anzai Y. Pattern recognition and machine learning[M].San Francisco:Morgan Kaufmann,2012.

[20] Aly H,Youssef M.Dejavu:An accurate energy-efficient outdoor localization system[C]∥Proc of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems,2013:154-163.

[21] Zheng Y, Liu L,Wang L,et al.Learning transportation mode from raw gps data for geographic applications on the web[C]∥Proc of the 17th International Conference on World Wide Web,2008:247-256.