基于群组的WI-FI指纹室内定位研究

李树军 ，于建江

(1.盐城师范学院 信息科学与技术学院，盐城 224002；2.南京大学 软件学院，南京 210093)

全球定位系统GPS(Global Position System)是目前应用最广泛最成熟的定位系统。GPS通过卫星授时和测距对用户进行定位，具有定位精度高、实时性好、抗干扰能力强等优点。但是GPS只适用于无遮挡的室外环境，在室内环境中存在较大的误差。近年来，很多高校和研究机构对室内定位技术进行了研究，提出了 TOA[1]、TDOA[2]、AOA[3]、WI-FI RSSI指纹[4]等算法。

基于WI-FI信号强度(RSSI)的指纹识别(Fingerprinting)定位是目前室内和室外城市密集区的重要定位算法之一[5，6]。与其它定位算法相比，WI-FI RSS指纹定位存在很多优点。首先，WI-FI指纹定位成本低廉。它利用室内环境中已经存在的WI-FI接入点实现定位，而AOA等算法需要在室内环境中部署特殊的硬件设备。其次，WI-FI RSSI指纹定位可以使用大众化的智能手机实现无所不在的定位。最后，WI-FI指纹定位原理以及计算过程都非常简单。但是由于室内环境比较复杂，无线信号在室内环境极不稳定，WI-FI RSSI指纹定位存在较大的误差，这已成为RSSI指纹定位技术商业化的瓶颈，当前，国内外的研究热点集中在如何提高RSSI指纹定位的精度[7]。

在室内环境中(如商场、电影院)，人们总是喜欢结伴而行，形成一个群组。群组成员之间的物理距离通常较近，但是通过WI-FI RSSI指纹定位计算出来的位置可能相差较远，与现实的情况不符。基于以上观察，本文提出了基于群组的WI-FI RSSI指纹定位算法，利用群组成员相互之间的物理距离来提高WI-FI RSSI指纹定位精度。

1 相关工作

WI-FI RSSI指纹定位分为离线训练和在线定位两个阶段。如图1所示，假设在室内环境中存在{AP1，AP2，AP3…APN}N 个 WI-FI无线接入点。离线训练阶段，首先在室内均匀地选取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 }存入数据库。在线定位阶段，首先在待定位的地方获取每个AP的信号强度值(S1,S2,S3…Si…SM)，其中Si为接收到APi的信号强度值；然后采用公式(1)计算待定位处RSS向量与数据库中各点RSS向量之间的距离。

其中1≤i≤M,w取大于0的整数。最后根据上面的结果估计待测位置的坐标，通常的做法是采用神经网络、最近邻法(NN，Nearest Neighborhood)、K最近邻算法[8，9](KNN，K Nearest Neighbor)等。比较为业界所认可的是采用K最近邻算法，即选取K个距待测位置最近的点，按式(2)计算待测位置的坐标。

虽然存在很多优点，但是室内环境比较复杂，受室内物理以及来往行人的影响，信号传播会发生反射、衍射和散射，因此信号强度RSSI值会存在一定程度的波动。信号强度值的波动导致WI-FI指纹定位的误差较大，约为6～8m。近年来，大量工作都在探索如何减小WI-FI RSSI指纹定位的误差。

2 基于群组的定位

2.1 算法概述

人是一种群居动物，喜欢结队出行。比如在商场，男女朋友总是习惯手挽着手一起狂街。多个相互熟悉的人同时在室内行走时，通常会形成一个小组，我们称之为群组。在群组之内，人与人之间相隔很近，或者是前后相差一步，或者左右相差一步。本论文利用群组中人与人之间的这种物理间隔来减小WI-FI指纹定位的误差。

如图1所示，A，B，C，D是四个一起行走的好友，前后左右相差0.5m(一步的距离)。他们形成了一个群组。由于WI-FI指纹定位存在较大的误差，A、B、C、D通过定位算法计算出来的位置分别为A′、B′、C′、D′，不同程度地偏离了各自准确的位置。然而A′、B′、C′、D′四个点构成的形状不满足A、B、C、D四个人之间的物理距离。我们可以利用A、B、C、D之间的物理距离来修正WI-FI指纹定位的误差。

利用群组来提高WIFI指纹定位的精度分为两步。首先是群组的识别，本文通过编辑距离识别不同的群组；然后利用群组之间的物理距离计算群组成员的实际位置。

图2 多人定位误差

2.2 基于编辑距离的群组识别算法

最小编辑距离[6]是指两个字符串之间，由一个转成另一个所需要的最少编辑操作次数，允许的编辑操作包括：将一个字符替换成另一个字符，插入一个字符或者删除一个字符。最小编辑距离是一种衡量两个序列相似性的度量方法。

近年来，随着智能手机的普及，传感器设备已经无处不在。普通的智能手机上存在8、9种传感器，包括GPS、方向传感器、加速度传感器、温度计、环境光传感器等。本文利用智能手机上的加速度传感器和方向传感器发现群组。

在室内环境中，存在很多地方能够引起智能手机上传感器读数的强烈变化，我们将这些变化称之为事件。在电梯中，加速度传感器能够监测到电梯启动和停止导致的超重和失重，如图3所示。在室内的转角处，方向传感器随着人的身体发生转动，其读数也随着出现较大的波动，如图4所示。

图3 电梯中加速度传感器的变化值

设智能手机能够监测出的事件集合为S，其中S={E1,E2,E3,E4}。E1,E2,E3,E4分别表示超重、失重、向左转和向右转。在室内行走时，记录下监测到的事件。一段时间后，会形成由E1,E2,E3,E4组成的事件序列。如果两个人属于同一个群组，他们所监测到的事件序列会有很高的相似度，同时，通过WI-FI指纹定位算出的结果应大致处于同一个区域。

图4 方向传感器在转角处的读数变化

设A，B两人监测到的事件序列分别为traceA和traceB，通过WI-FI指纹计算的位置分别为A′、B′。我们通过下式判断A，B两人是否属于同一群组：

其中dis( A′，B′)为 A′和 B′的欧式距离，MED(traceA,traceB)为traceA和traceB之间的最小编辑距离，θ为阈值。当不等式成立时，A、B属于同一个群组，否者不属于一个群组。两个事件序列最小编辑距离算法的伪代码如下：

2.3 基于群组定位算法

在识别群组后，我们通过群组成员之间的物理距离修正WI-FI指纹定位产生的误差。为简化说明，假设一个群组中成员为A、B、C。A、B、C监测到的事件序列分别为 traceA，traceB和 traceC。traceABC为traceA、traceB、traceC的最大公共子序列。则A、B、C之间的距离可通过下面的式子估算。

其中L是traceABC最大公共子序列的长度，分别是A、B、C监测到traceABC中第i个事件的时间，ρ为人的步行速度。

设A，B，C采集到的WI-FI信号强度M个AP的信号强度向量分别为：

3 实验分析

为了验证算法的有效性，本文在智能手机上实现了定位算法，并在如图5所示的室内环境中进行了测试。

图5 实验环境

实验总共部署了15个AP，均匀分布在室内环境中。每平方米内，我们选取一个点进行WI-FI指纹训练。在线定位阶段，手持智能手机，分别组成2/3/4/5/6人群组，在室内各进行100次测试。群组识别的准确性如表2所示。

表2 群组识别正确率

基于群组的WI-FI指纹定位和WI-FI指纹定位算法的误差累计分布如图6所示。从图中，可以看出基于群组的WI-FI指纹定位算法能够明显地减小WI-FI指纹定位的误差。

图6 定位误差累计分布

4 结论

室内定位是位置感知计算和基于位置的服务的基础。WI-FI指纹定位是最常用的室内定位算法之一。但由于室内环境较复杂，无线信号的传播存在反射、衍射和散射，WI-FI指纹定位存在较大的误差。本文设计和实现了一种基于群组的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].传感技术学报，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.