李樹軍 ，于建江

(1.鹽城師范學院 信息科學與技術(shù)學院，鹽城 224002；2.南京大學 軟件學院，南京 210093)

全球定位系統(tǒng)GPS(Global Position System)是目前應用最廣泛最成熟的定位系統(tǒng)。GPS通過衛(wèi)星授時和測距對用戶進行定位，具有定位精度高、實時性好、抗干擾能力強等優(yōu)點。但是GPS只適用于無遮擋的室外環(huán)境，在室內(nèi)環(huán)境中存在較大的誤差。近年來，很多高校和研究機構(gòu)對室內(nèi)定位技術(shù)進行了研究，提出了 TOA[1]、TDOA[2]、AOA[3]、WI-FI RSSI指紋[4]等算法。

基于WI-FI信號強度(RSSI)的指紋識別(Fingerprinting)定位是目前室內(nèi)和室外城市密集區(qū)的重要定位算法之一[5，6]。與其它定位算法相比，WI-FI RSS指紋定位存在很多優(yōu)點。首先，WI-FI指紋定位成本低廉。它利用室內(nèi)環(huán)境中已經(jīng)存在的WI-FI接入點實現(xiàn)定位，而AOA等算法需要在室內(nèi)環(huán)境中部署特殊的硬件設備。其次，WI-FI RSSI指紋定位可以使用大眾化的智能手機實現(xiàn)無所不在的定位。最后，WI-FI指紋定位原理以及計算過程都非常簡單。但是由于室內(nèi)環(huán)境比較復雜，無線信號在室內(nèi)環(huán)境極不穩(wěn)定，WI-FI RSSI指紋定位存在較大的誤差，這已成為RSSI指紋定位技術(shù)商業(yè)化的瓶頸，當前，國內(nèi)外的研究熱點集中在如何提高RSSI指紋定位的精度[7]。

在室內(nèi)環(huán)境中(如商場、電影院)，人們總是喜歡結(jié)伴而行，形成一個群組。群組成員之間的物理距離通常較近，但是通過WI-FI RSSI指紋定位計算出來的位置可能相差較遠，與現(xiàn)實的情況不符?；谝陨嫌^察，本文提出了基于群組的WI-FI RSSI指紋定位算法，利用群組成員相互之間的物理距離來提高WI-FI RSSI指紋定位精度。

1 相關工作

WI-FI RSSI指紋定位分為離線訓練和在線定位兩個階段。如圖1所示，假設在室內(nèi)環(huán)境中存在{AP1，AP2，AP3…APN}N 個 WI-FI無線接入點。離線訓練階段，首先在室內(nèi)均勻地選取P={P1，P2，P3…PM}M個點(如圖1中的訓練點所示)，其坐標分別為{( x1,y1),(x2,y2),(x3,y3)…(xM,yM)} ；然后，分別在每個點Pi(1≤i≤M)處采集各個AP的信號強度作為該點的指紋，記為RSSi=(RSSi1,RSSi2…RSSij…RSSiN)，其中RSSij是點 Pi處接收到APj的信號強度值；最后，將每個點的坐標和指紋{(xi,yi),(RSSi1,RSSi2…RSSij…RSSiN),1≤i≤M }存入數(shù)據(jù)庫。在線定位階段，首先在待定位的地方獲取每個AP的信號強度值(S1,S2,S3…Si…SM)，其中Si為接收到APi的信號強度值；然后采用公式(1)計算待定位處RSS向量與數(shù)據(jù)庫中各點RSS向量之間的距離。

其中1≤i≤M,w取大于0的整數(shù)。最后根據(jù)上面的結(jié)果估計待測位置的坐標，通常的做法是采用神經(jīng)網(wǎng)絡、最近鄰法(NN，Nearest Neighborhood)、K最近鄰算法[8，9](KNN，K Nearest Neighbor)等。比較為業(yè)界所認可的是采用K最近鄰算法，即選取K個距待測位置最近的點，按式(2)計算待測位置的坐標。

雖然存在很多優(yōu)點，但是室內(nèi)環(huán)境比較復雜，受室內(nèi)物理以及來往行人的影響，信號傳播會發(fā)生反射、衍射和散射，因此信號強度RSSI值會存在一定程度的波動。信號強度值的波動導致WI-FI指紋定位的誤差較大，約為6～8m。近年來，大量工作都在探索如何減小WI-FI RSSI指紋定位的誤差。

2 基于群組的定位

2.1 算法概述

人是一種群居動物，喜歡結(jié)隊出行。比如在商場，男女朋友總是習慣手挽著手一起狂街。多個相互熟悉的人同時在室內(nèi)行走時，通常會形成一個小組，我們稱之為群組。在群組之內(nèi)，人與人之間相隔很近，或者是前后相差一步，或者左右相差一步。本論文利用群組中人與人之間的這種物理間隔來減小WI-FI指紋定位的誤差。

如圖1所示，A，B，C，D是四個一起行走的好友，前后左右相差0.5m(一步的距離)。他們形成了一個群組。由于WI-FI指紋定位存在較大的誤差，A、B、C、D通過定位算法計算出來的位置分別為A′、B′、C′、D′，不同程度地偏離了各自準確的位置。然而A′、B′、C′、D′四個點構(gòu)成的形狀不滿足A、B、C、D四個人之間的物理距離。我們可以利用A、B、C、D之間的物理距離來修正WI-FI指紋定位的誤差。

利用群組來提高WIFI指紋定位的精度分為兩步。首先是群組的識別，本文通過編輯距離識別不同的群組；然后利用群組之間的物理距離計算群組成員的實際位置。

圖2 多人定位誤差

2.2 基于編輯距離的群組識別算法

最小編輯距離[6]是指兩個字符串之間，由一個轉(zhuǎn)成另一個所需要的最少編輯操作次數(shù)，允許的編輯操作包括：將一個字符替換成另一個字符，插入一個字符或者刪除一個字符。最小編輯距離是一種衡量兩個序列相似性的度量方法。

近年來，隨著智能手機的普及，傳感器設備已經(jīng)無處不在。普通的智能手機上存在8、9種傳感器，包括GPS、方向傳感器、加速度傳感器、溫度計、環(huán)境光傳感器等。本文利用智能手機上的加速度傳感器和方向傳感器發(fā)現(xiàn)群組。

在室內(nèi)環(huán)境中，存在很多地方能夠引起智能手機上傳感器讀數(shù)的強烈變化，我們將這些變化稱之為事件。在電梯中，加速度傳感器能夠監(jiān)測到電梯啟動和停止導致的超重和失重，如圖3所示。在室內(nèi)的轉(zhuǎn)角處，方向傳感器隨著人的身體發(fā)生轉(zhuǎn)動，其讀數(shù)也隨著出現(xiàn)較大的波動，如圖4所示。

圖3 電梯中加速度傳感器的變化值

設智能手機能夠監(jiān)測出的事件集合為S，其中S={E1,E2,E3,E4}。E1,E2,E3,E4分別表示超重、失重、向左轉(zhuǎn)和向右轉(zhuǎn)。在室內(nèi)行走時，記錄下監(jiān)測到的事件。一段時間后，會形成由E1,E2,E3,E4組成的事件序列。如果兩個人屬于同一個群組，他們所監(jiān)測到的事件序列會有很高的相似度，同時，通過WI-FI指紋定位算出的結(jié)果應大致處于同一個區(qū)域。

圖4 方向傳感器在轉(zhuǎn)角處的讀數(shù)變化

設A，B兩人監(jiān)測到的事件序列分別為traceA和traceB，通過WI-FI指紋計算的位置分別為A′、B′。我們通過下式判斷A，B兩人是否屬于同一群組：

其中dis( A′，B′)為 A′和 B′的歐式距離，MED(traceA,traceB)為traceA和traceB之間的最小編輯距離，θ為閾值。當不等式成立時，A、B屬于同一個群組，否者不屬于一個群組。兩個事件序列最小編輯距離算法的偽代碼如下：

2.3 基于群組定位算法

在識別群組后，我們通過群組成員之間的物理距離修正WI-FI指紋定位產(chǎn)生的誤差。為簡化說明，假設一個群組中成員為A、B、C。A、B、C監(jiān)測到的事件序列分別為 traceA，traceB和 traceC。traceABC為traceA、traceB、traceC的最大公共子序列。則A、B、C之間的距離可通過下面的式子估算。

其中L是traceABC最大公共子序列的長度，分別是A、B、C監(jiān)測到traceABC中第i個事件的時間，ρ為人的步行速度。

設A，B，C采集到的WI-FI信號強度M個AP的信號強度向量分別為：

3 實驗分析

為了驗證算法的有效性，本文在智能手機上實現(xiàn)了定位算法，并在如圖5所示的室內(nèi)環(huán)境中進行了測試。

圖5 實驗環(huán)境

實驗總共部署了15個AP，均勻分布在室內(nèi)環(huán)境中。每平方米內(nèi)，我們選取一個點進行WI-FI指紋訓練。在線定位階段，手持智能手機，分別組成2/3/4/5/6人群組，在室內(nèi)各進行100次測試。群組識別的準確性如表2所示。

表2 群組識別正確率

基于群組的WI-FI指紋定位和WI-FI指紋定位算法的誤差累計分布如圖6所示。從圖中，可以看出基于群組的WI-FI指紋定位算法能夠明顯地減小WI-FI指紋定位的誤差。

圖6 定位誤差累計分布

4 結(jié)論

室內(nèi)定位是位置感知計算和基于位置的服務的基礎。WI-FI指紋定位是最常用的室內(nèi)定位算法之一。但由于室內(nèi)環(huán)境較復雜，無線信號的傳播存在反射、衍射和散射，WI-FI指紋定位存在較大的誤差。本文設計和實現(xiàn)了一種基于群組的WI-FI指紋定位算法。該算法利用群組成員之間的物理距離減小WI-FI指紋定位的誤差。實驗表明，該算法能夠有效地提高WI-FI指紋定位的精度。

[1]Guvenc I，Chong C C.A survey on TOA based wireless localization and NLOS mitigation techniques[J].Communications Surveys&Tutorials，IEEE，2009，11(3)：107-124.

[2]Musicki D，Kaune R，Koch W.Mobile emitter geolocation and tracking using TDOA and FDOA measurements[J].IEEE Transactions on，Signal Processing，2010，58(3)：1863-1874.

[3]Chang A C，Chang J C.Robust Mobile Location Estimation Using Hybrid TOA/AOA Measurementsin CellularSystems[J].WirelessPersonal Communications，2012，65(1)：1-13.

[4]Yang Q，Pan S J，Zheng V W.Estimating location using wi-fi[J].IEEE Intelligent Systems，2008，23(1)：8-13.

[5]孟磊，丁恩杰，馮啟言，等.基于Wi-Fi與WebGIS的井下移動目標定位與歷史軌跡提取[J].地理與地理信息科學，2012，28(3)：109-110.

[6]劉曉文，張秀均，郝麗娜，等.基于WI-FI的井下定位算法研究[J].傳感技術(shù)學報，2012，25(6)：854-858.

[7]Fang S H，Wang C H.A dynamic hybrid projection approach for improved Wi-Fi location fingerprinting[J].IEEE Transactions on，Vehicular Technology，2011，60(3)：1037-1044.

[8]Weinberger K Q，Saul L K.Distance metric learning for large margin nearest neighbor classification[J].The JournalofMachine Learning Research，2009，10：207-244.

[9]Triguero I，Derrac J，Garcia S，et al.A taxonomy and experimental study on prototype generation for nearest neighbor classification[J].IEEE Transactions on，Systems，Man，and Cybernetics，Part C：Applications and Reviews，2012，42(1)：86-100.