基于電信數(shù)據(jù)的室外定位技術(shù)研究*

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

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

1 引言

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

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

3 室外定位算法

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

3.1 基本概念

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

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

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

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

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

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

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

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

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

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

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

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

3.3 基于隨機(jī)森林的定位模型

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

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

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

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

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

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

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

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

與使用隨機(jī)森林模型相似，我們分別建立回歸模型與分類模型?；贛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]，以保證輸出的是落入各個(gè)柵格里的概率并且相加等于 1。最終選擇概率最大的柵格作為用戶所在的柵格，并將柵格的中心坐標(biāo)作為用戶的GPS坐標(biāo)。構(gòu)建分類MLP時(shí)，柵格的邊長設(shè)置為30 m，隱藏層的激活函數(shù)選擇Relu，神經(jīng)網(wǎng)絡(luò)迭代次數(shù)設(shè)置為20次。

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

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

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

3.5.1 異常點(diǎn)檢測

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

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

3.5.2 基于聚類的錨點(diǎn)

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

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

(1)

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

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

4 實(shí)驗(yàn)與評估

4.1 實(shí)驗(yàn)設(shè)置

4.1.1 實(shí)驗(yàn)環(huán)境

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

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

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

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

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

信號制式數(shù)據(jù)量/條手機(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)計(jì)

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

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

S=2×arcsin

(2)

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

4.1.4 實(shí)驗(yàn)流程

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

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

首先，我們對不同方法的預(yù)測精度進(jìn)行比較，作為一個(gè)基準(zhǔn)實(shí)驗(yàn)(Benchmark)。如圖3和圖4所示，圖中橫軸表示定位誤差，即預(yù)測點(diǎn)與真實(shí)點(diǎn)之間的直線距離，單位為m；縱軸表示各階段誤差數(shù)據(jù)比例的累計(jì)分布函數(shù)值。舉例來說，縱軸(CDF)取0.5表示中位誤差，此時(shí)橫軸對應(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

分析實(shí)驗(yàn)結(jié)果可以得出以下結(jié)論：

(1)首先從圖中可以看出，2G數(shù)據(jù)與4G數(shù)據(jù)有相同的規(guī)律：很明顯RF的定位精度要遠(yuǎn)遠(yuǎn)高于MLP與Cellsense的定位精度，而MLP與Cellsense相比較，只有少部分?jǐn)?shù)據(jù)的Cellsense預(yù)測精度要比MLP的預(yù)測精度好，而當(dāng)比較整體的預(yù)測精度時(shí)(超過53%的數(shù)據(jù))，MLP還是要比Cellsense更勝一籌。這是因?yàn)镃ellsense是一種基于統(tǒng)計(jì)的方法，需要能夠明確地區(qū)分各個(gè)柵格，收集數(shù)據(jù)時(shí)的路徑實(shí)際上是一個(gè)環(huán)狀的，環(huán)內(nèi)部的基站信號強(qiáng)度數(shù)據(jù)并沒有收集到，在構(gòu)建各個(gè)柵格的指紋時(shí)，有一些柵格因?yàn)閿?shù)據(jù)稀少或者缺失，無法構(gòu)建能有效區(qū)分自己與其他柵格的指紋，因此定位時(shí)只有一些特征很明顯的MR數(shù)據(jù)才被預(yù)測到了正確的柵格里，而其他的MR數(shù)據(jù)由于不同柵格太相似，在預(yù)測時(shí)出現(xiàn)了錯(cuò)誤，導(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%的精度提升。這是因?yàn)樵跂鸥窕?，每一?每個(gè)柵格)數(shù)據(jù)的共性能夠更好地被發(fā)現(xiàn)，因此預(yù)測數(shù)據(jù)屬于哪個(gè)柵格比預(yù)測其具體GPS坐標(biāo)要準(zhǔn)確得多。

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

4.3 不同方法運(yùn)行時(shí)間的比較

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

Figure 5 Efficiency of different approaches圖5 不同方法運(yùn)行時(shí)間

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

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

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

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

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

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

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

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

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

針對基站特征和地磁數(shù)據(jù)特征，一共進(jìn)行了四種特征組合的實(shí)驗(yàn)：(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對定位的作用更大，這是因?yàn)榛镜奈恢门c基站ID恒定不變，而地磁信號變化則大得多。

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

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

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

在3.5節(jié)，我們參考Dejavu系統(tǒng)提出了檢測數(shù)據(jù)異常點(diǎn)和聚類的后處理方法。實(shí)驗(yàn)發(fā)現(xiàn)，針對不同子數(shù)據(jù)集RSSI聚類得到的聚類點(diǎn)分布相差較大，因此由RSSI聚類尋找錨點(diǎn)的方法不可行。而針對不同的子數(shù)據(jù)集進(jìn)行異常檢測后得到的異常點(diǎn)分布相對來說，要稍微有規(guī)律一些，對異常點(diǎn)處的數(shù)據(jù)進(jìn)行線性插值，將這種新的數(shù)據(jù)稱為修復(fù)數(shù)據(jù)。對MR數(shù)據(jù)中主連接基站信號強(qiáng)度(RSCP_1)實(shí)施異常點(diǎn)檢測，對比修復(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ù),隨機(jī)森林分類)

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

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

4.7 實(shí)驗(yàn)總結(jié)

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

5 結(jié)束語

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

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

參考文獻(xiàn):

[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.