基于中心矩改进的WiFi室内定位算法

于　洋　陈　光　单志勇　陈　艳

(东华大学信息科学与技术学院　上海 201620)

0　引　言

目前，影响最大、定位覆盖最广的定位系统是美国的全球卫星定位系统GPS[1]，它以全方位、全天候、高精度、高效率作为其独特优点。但是，在室内如商场、医院、博物馆及地下停车场等公共场所，由于GPS卫星发射的无线电信号无法穿透建筑物墙壁，以致于使用全球卫星定位系统来进行精确的室内定位存在着很大的局限性。

针对GPS在室内定位中存在的问题，各种室内定位技术如RFID[2]定位技术、红外线[3]定位技术、ZigBee[4]定位技术、超声波[5]定位技术、WiFi[6-7]定位术、 蓝牙[8]定位技术、地磁[9]定位技术应运而生，并已经成功地应用于民用和商业领域中。其中，比较典型的有微软研究院的RADAR[6]定位系统，美国马里兰大学的Horus[7]定位系统，加利福亚大学的Nibble[10]定位系统，麻省理工学院的Cricket[11]定位系统，北京航空航天大学的Weyes[12]定位系统，以及清华大学的WILL[13]定位系统等。

在这些定位技术中，基于WiFi的室内定位技术由于WiFi网络的广泛普及和通信能力强优点，已经成为目前主流、也是未来最具发展潜力的室内定位技术。WiFi定位技术的独特优势在于WiFi芯片已经在各类用户智能终端，诸如智能手机、平板电脑中得到广泛普及，并且随着“无线城市”的发展，国内各大城市的运营商在众多公共场所均已安装了大量的WiFi热点，通过利用现有的这些WiFi设施，能够显著降低建设与长期维护成本[14]。

针对室内环境下接受信号强度RSS值波动较大问题，本文根据参考点RP(Reference Point)信号强度分布的中心矩特征值，设计了一种改进的WKNN定位算法。

1　定位系统

基于WiFi指纹的定位系统如图1所示。它包括离线阶段和在线匹阶段两部分。其中，离线阶段负责采集参考点上信号强度的均值和二阶矩以建立指纹数据库；在线阶段将当前采集的数据，采用匹配算法来与数据库中的数据进行匹配，找出最相似的参考点坐标作为定位点位置的估算值。

图1　WiFi指纹定位系统

1.1　指纹数据库建立

在离线阶段，首先将室内场景划分为等间距的方形网格，一般网格间距为1～2 m，此时将各个网格相交的点作为参考点，然后在每个参考点上依次采集来自不同AP(Access Point)的信号强度，同时记录该参考点的坐标，以建立指纹数据库。

第i个参考点RP测得来自第j个AP的信号强度可以表示成一个数集：

rssij={sijt,t=1,2,…,T}

(1)

式中：t代表单位采样时间，由于环境的时变性，有可能会出现采集来自AP信号强度值不稳定的情况，根据大数定律，当样本数据量很大的时候，平均结果将趋于某一稳定值。则第i个参考点RP来自第j个AP的信号强度为：

(2)

式(2)表示在第i个参考点RP测得来自第j个接入点AP的信号强度的均值。则所有参考点RP来自每个AP的信号强度可以表示为一个矩阵：

(3)

1.2　经典指纹匹配算法

在线定位时，用户终端在定位场景中移动并实时获取当前来自每个AP的信号强度值，同时将该数据上传至定位服务器与指纹数据库的数据进行在线匹配，从而获得该点的估算位置，并返回至终端。其中常见的匹配算法有最邻近NN[15]算法、K最邻近KNN[16-17]算法、加权K邻近WKNN[18]算法。

NN算法通过计算当前采集的信号强度向量与指纹数据库的每个参考点的信号强度向量的欧式距离度量，然后将计算结果中的最小值所对应的参考点坐标最为定位位置。

KNN算法与NN算法类似，NN算法在于找出计算结果中一个最小值，而KNN算法则是找出计算结果中K个(K一般取4[19])最小值所对应的K个参考点坐标值，然后将坐标取平均作为定位位置。

WKNN算法是对KNN算法的改进，该算法不是简单地对K个位置坐标取均值，而是对于每个位置设定一个权值，权值的大小决定其在定位所占的比重[20]。

2　改进的WKNN 算法

由于室内环境的时变性，因此，参考点采集的信号强度会产生一定的波动。而对发射信号功率稳定性差的AP，这种波动尤为明显[21]。针对采集来自AP的信号强度不稳定问题，在已有的WKNN算法基础上本文提出了一种改进的 WKNN 算法以提高定位精度。

2.1　中心矩特征值的提取

指纹数据库中在第i个参考点RP上的信号强度可以表示为一均值向量，如式(4)所示。

rssi=rssiji=1,2,…,Mj=1,2,…,N

(4)

式中：M表示RP的数量，N表示AP的数量，rssij表示在第i个参考点RP测得来自第j个AP的信号强度均值向量，根据式(1)和式(2)，可进一步表示为：

(5)

根据采集到的信号强度集合式(1)和n阶中心矩式(6)计算参考点上的信号强度中心矩。式(6)中，E(rssijt)表示在第i个参考点测得来自第j个AP的信号强度均值，rssijt表示每隔单位时间t采集来自AP的信号强度值，cij表示信号强度的n阶中心距。

cij=E{[rssijt-E(rssijt)]n}t=1,2,…,T

(6)

由于二阶中心矩是用来衡量随机变量与均值之间的偏离程度，故n取值为2，则计算第i个参考点来自第j个AP的信号强度二阶中心矩向量cij如式(7)。

cij=(ci1,ci2,…,ciN)i=1,2,…,Mj=1,2,…,N

(7)

通过式(5)和式(7)，指纹数据库式(3)可以进一步表示为信号强度向量和二阶中心矩向量，如式(8)所示。

R=(rssij,cij)i=1,2,…,Mj=1,2,…,N

(8)

2.2　加权距离的计算

改进WKNN算法采用加权欧式距离来寻找与定位点最近的K个参考点，而权值的大小取决于数据库中每个参考点上采集的信号强度的二阶中心矩。

假设移动终端在定位场景中某点x所获取的信号强度矢量为：

rssxj=(rssx1,rssx2,…,rssxj)j=1,2,…,N

(9)

加权欧氏距离是在已有欧氏距离的基础上对它作出的一种改进，改进的欧氏距离在n维信号强度向量的每一维度赋予了不同权重，权重与参考点上的信号强度二阶中心矩相关， 则使用改进加权距离计算用户终端定位点x与参考点i的距离dxi为：

(10)

式中：ωik是参考点i在第k个AP处的权值系数，与该参考点采集到的AP信号强度的中心矩有关，并以中心矩的倒数作为系数，然后将该系数归一化处理，如公式所示：

(11)

二阶中心矩大的参考点，说明RSS的波动越大，

采集的信号强度与其均值相离越远；二阶中心矩小的参考点，说明RSS的分布越紧凑，采集的信号强度都会在其均值附近波动。

使用改进的加权欧氏距离进行在线匹配计算时，此算法将中心矩的倒数作为权系数加入到欧式距离的计算中，能大大地降低中心矩较大的AP的RSS值在欧式距离计算时所占的比重，能够在一定程度上消除大部分由于环境的实时变化而造成RSS值产生一定波动带来的影响，进而提高用户终端的定位精度。

3　实验测试

3.1　测试环境

实验环境选择了室内8 m×8 m区域，首先在该区域划分若干个网格，然后选择其中有16个点作为参考点RP，3个点作为接入点AP，其中，图2为实际场景，图3为仿真场景。

图2　定位场景

图3　仿真场景

离线阶段，用户终端依次在每个参考点RP每隔1秒钟采集一次信号强度，共采集50次来自每个接入点AP的信号强度，然后将原始数据进行预处理，得到信号强度的均值和二阶中心矩以建立指纹数据库。

在线定位阶段时，在上述8 m×8 m区域内随机选定10个点作为定位测试点，如图4所示。

图4　AP=3的场景分布

然后依次将该场景中分布的AP分别增加至5个和7个。其中，AP分布如图5和图6所示，最后在上述10个同样的测试点再次进行在线定位。

图5　AP=5的场景分布

图6　AP=7的场景分布

3.2　性能分析

在上述三种不同AP数量分布的场景下，通过定位结果分析，当AP的数量为5时，定位误差达到最小。其中，各测试点的定位结果见表1和表2，场景定位结果如图7所示。

表1　定位结果

表2　定位结果

图7　AP=5的定位结果

在上述10个同样的测试点分别进行在线定位，三中不同场景下的AP分布的定位误差如图8所示。从定位误差分析，当场景中AP的数量为5时，定位误差最小。

图8　定位误差比较

图9是NN算法，KNN算法，WKNN算法与改进WKNN算法的实验仿真的累计误差分布直方图，其中，K=4。从图中可明显看出采用改进WKNN算法的累计误差距离是最小的。因此，实验证明采用改进WKNN算法进行在线匹配能够有效提高室内定位精度。

图9　不同算法的CDF比较

4　结　语

本文针对WiFi室内定位系统在线阶段匹配精度低问题，在已有的WKNN算法基础上，提出了一种改进的WKNN算法。并通过理论分析和实验测试，在不同AP数量的分布以及不同定位算法的选择下对定位结果进行了分析。实验结果证明：采用改进的WKNN算法将信号强度的二阶矩作为权值加入到计算欧式距离中，有效地降低了室内环境实变性而造成RSS值产生一定波动带来的影响，提高了定位的精度。此外，该系统无需增加额外的硬件设备，易于实现，具有潜在的实用价值。

[1] Enge P,Misra P.Special Issue on Global Positioning System[J].Proceedings of the IEEE,1999,87(1):3-15.

[2] Ni L M,Liu Y,Lau Y C,et al.LANDMARC:Indoor Location Sensing Using Active RFID[C]//IEEE International Conference on Pervasive Computing and Communications.IEEE,2003:407-415.

[3] Want R,Hopper A,Gibbons J.The active badge location system[J].Acm Transactions on Information Systems,1992,10(1):91-102.

[4] Sugano M,Kawazoe T,Ohta Y,et al.Indoor Localization System using RSSI Measurement of Wireless Sensor Network based on ZigBee Standard[C]//The 6th IASTED International Multi-Conference on Wireless and Optical Communications,Wireless Sensor Networks.DBLP,2006:1-6.

[5] Ward A,Jones A,Hopper A.A new location technique for the active office[J].Personal Communications IEEE,1997,4(5):42-47.

[6] Bahl P,Padmanabhan V N.RADAR:an in-building RF-based user location and tracking system[C]//INFOCOM 2000.Nineteenth Joint Conference of the IEEE Computer and Communications Societies.Proceedings.IEEE.IEEE Xplore,2000:775-784.

[7] Youssef M,Agrawala A.The Horus WLAN location determination system[C]//International Conference on Mobile Systems,Applications,and Services.ACM,2005:205-218.

[8] Hallberg J,Nilsson M,Synnes K.Positioning with Bluetooth[C]//International Conference on Telecommunications.IEEE,2003,2:954-958.

[9] Boles L C,Lohmann K J.True navigation and magnetic maps in spiny lobsters[J].Nature,2003,421(6918):60.

[10] Castro P,Chiu P,Kremenek T,et al.A Probabilistic Room Location Service for Wireless Networked Environments[C]//International Conference on Ubiquitous Computing.Springer-Verlag,2001:18-34.

[11] Priyantha N B.The Cricket indoor location system[J].Architecture,2005,16(2001):199.

[12] 郎昕培,许可,赵明.基于无线局域网的位置定位技术研究和发展[J].计算机科学,2006,33(6):21-24.

[13] Wu C,Yang Z,Liu Y,et al.WILL:Wireless Indoor Localization without Site Survey[J].IEEE Transactions on Parallel & Distributed Systems,2013,24(4):839-848.

[14] 杜晓黎.基于WIFI的室内定位系统[D].东南大学,2015.

[15] Cover T M.Rates of convergence for nearest neighbor procedures[C]//Hawaii International Conference on System Sciences,1968.

[16] Short R D,Fukunaga K.A new nearest neighbor distance measure[C]//1980.

[17] Hastie T,Tibshirani R.Discriminant Adaptive Nearest Neighbor Classification[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1996,18(6):607-616.

[18] Brown T,Koplowitz J.The weighted nearest neighbor rule for class dependent sample sizes (Corresp.)[J].IEEE Transactions on Information Theory,1979,25(5):617-619.

[19] Mitchell H B,Schaefer P A.A “soft” K-Nearest Neighbor voting scheme[J].International Journal of Intelligent Systems,2001,16(4):459-468.

[20] 任睿.基于数据库相关算法的位置指纹定位技术[J].铁道通信信号,2012,48(3):49-51.

[21] 陈空,宋春雷,陈家斌,等.基于改进WKNN的位置指纹室内定位算法[J].导航定位与授时,2016,3(4):58-64.