基于卡方距离改进的WLAN室内定位算法

陶 峥，王洪玉

(1.大连理工大学电子信息与电气工程学部，辽宁大连 116024; 2.解放军92124部队，辽宁大连 116023)

基于卡方距离改进的WLAN室内定位算法

陶 峥1，2，王洪玉1

(1.大连理工大学电子信息与电气工程学部，辽宁大连 116024; 2.解放军92124部队，辽宁大连 116023)

基于WLAN的定位服务现今已成为智慧城市中一个很有吸引力的研究领域。在各种定位算法中，经典欧氏距离法的度量方式只考虑各实际位置点RSS向量之间的绝对距离，往往忽视各实际位置点RSS向量之间的相对距离;并且只能给各AP赋予相同的权重。为克服欧氏距离法的不足，提出了基于卡方距离及灵敏度法的WLAN室内定位方法(CSKNN)。该方法利用位置指纹信息建立参考点的指纹信息和测试点的指纹信息，然后利用更能反映特征量之间相对距离的卡方距离并结合灵敏度法对各AP权重进行修正，得出在当前定位环境中各AP在定位系统中的贡献，用加权后的卡方距离依据各参考点的指纹信息计算待定位点的位置。结果表明，该方法比传统的欧氏距离法精度高。

室内定位;无线局域网;位置指纹;卡方距离;灵敏度法

0 引言

当今，随着智能手机和平板电脑的兴起，基于位置的服务(Location Based Service，LBS)吸引了越来越多的IT企业参与定位系统的设计。传统的定位服务通常来自GPS或基站信号。虽然GPS的定位精度可以达到1～2 m，但当用户进入室内环境时GPS信号就会变得很弱。基站信号虽然可以从任何环境中获得，然而定位误差却往往大于1 km。因此，为了满足室内定位系统(比如大型地下车库车辆引导系统和商场导航系统)的需要，诸如基于RFID，WIFI和蓝牙等定位技术被相继提出。然而，由于智能移动终端设备硬件结构的限制，基于WIFI的定位技术被普遍应用于室内定位导航［1-3］。

人们经常用无线访问接入点(Access Point，AP)发射和接收信号并可在无线接收范围内测得信号强度。任何信号都会在传播过程中进行衰减以致人们能用它估计用户设备与信号源之间的距离，如果在各个方向上都有足够的AP，那么用户的当前位置就会被唯一确定。一般情况下，可以利用来自各个AP的信号强度值组成的向量，即RSS(Received Signal Strength)向量，作为每一个实际位置点的指纹信息(也称实际位置点RSS向量)。通过比较这些向量之间的距离就可以得到实际位置之间的距离［4-5］。假如用户能在一个特定的场景中采集到足够的位置指纹信息，就可以粗略地估计用户的实际位置。很多商业应用软件已经开始使用该技术来对用户进行定位和导航。然而，信号衰减受到天气、障碍物、气流等多种因素影响。这些影响有时会导致无法找到最优匹配的RSS向量以及定位错误［6］。

1 WLAN位置指纹定位方法

21世纪初，位置指纹定位技术开始应用于WLAN室内定位中。在无线局域网环境中，位置指纹定位技术利用信号强度来对用户的移动设备进行定位。该技术先利用参考点的RSS向量建立针对环境的位置指纹地图，然后利用该地图对持有移动设备的用户进行定位。

位置指纹定位技术分为两个阶段:离线训练阶段和在线定位阶段。如图1所示，在离线训练阶段，将N 个AP置于定位环境中，并在定位环境中均匀布置若干个参考点，参考点的数目和参考点之间的间隔由系统设计者决定。用户利用笔记本电脑将各参考点接收自每一个AP的信号强度值组成的RSS向量存储到数据库中。在在线定位阶段，待定位者可能在房间内任何一个位置，不一定在参考点上。在这个阶段定位系统将待定位者设备接收各AP获得的RSS向量和数据库中各参考点的RSS向量进行比较，然后选取离用户设备获得的RSS向量最接近的几个参考点对应的坐标经过加权计算后的值作为定位结果［7-8］。

1.1 经典位置指纹匹配算法

在位置指纹定位研究领域中，关于RSS向量匹配算法的研究成果比较丰富，诸如欧氏距离、概率分布、神经网络、支持向量机、稀疏表示等等。这里主要介绍欧氏距离法［9-10］。

传统的加权K近邻法通常使用欧氏距离作为距离的度量。欧氏距离给出两点之间的绝对距离，在二维空间如式(1)所示:

其中，(x1，y1)和(x2，y2)是两点坐标。

当用欧氏距离定位用户，式(1)就改进成式(2):

其中，si为待定位点用户设备测到第i个AP的信号强度;dij为位置指纹库中第j个参考点接收到第i个AP的信号强度。

在离线训练阶段，在定位区域内布置h个参考点并测量各参考点接收来自每一个AP的RSS值组成的RSS向量，利用这些参考点所获得的RSS向量及其对应的物理坐标一同构建位置指纹库。

在在线定位阶段，欧氏距离通过搜索位置指纹库中的每个参考点找到距离待定位点距离最近的那个参考点，即找到最小的Lj，此法称为最近邻法(NN)。在定位算法中，假定每一个获得的RSS向量都可以代表定位场所中的一个实际物理位置。

如果选取Lj值较小的K(K≥2)个参考点为预定位参考点，并计算其对应坐标的平均值作为定位结果，即为K近邻法(KNN)。计算方法如下:

与原始的最近邻法相比，该法引入了K个估计位置坐标来计算待定位点的位置，对定位精度有一定的提升。

进一步根据不同预定位参考点对定位结果的贡献不同，计算预定位参考点坐标加权后的和作为定位结果，即为加权K近邻法，如式(4)所示:

其中，wj为预定位参考点j的权重因子，其值主要取决于预定位参考点和待定位点之间的欧氏距离Lj，计算方法如式(5)所示:

如果wj计算结果为，即为K近邻法。

K近邻法因其简单和实用等特点已成为一种非常流行的定位算法。

然而，KNN定位算法在位置指纹定位工程应用中也存在一些问题:一是传统KNN定位算法应用的欧氏距离度量方式只考虑各RSS向量间的绝对距离，忽视了各RSS向量间的相对距离;二是AP的权重对分类精度的影响较大，不同AP对分类准确性的影响是不同的，而以往用于KNN分类计算的欧氏距离度量方式只能将不同AP赋予相同的权重，忽视了AP因素给定位造成的影响。忽视AP因素使经典KNN定位算法对环境噪声比较敏感，在某些待定位点上容易因为环境噪声的影响而导致误差偏大。

1.2 基于卡方距离及灵敏度法的位置指纹定位算法

针对这些问题，文中提出了基于卡方距离及灵敏度法的位置指纹定位算法(CSKNN)。首先利用位置指纹信息建立参考点的指纹信息和测试点的指纹信息，然后利用更能反映特征量之间相对距离的卡方距离并结合灵敏度法对AP权重进行修正，得出在当前定位环境下各AP在定位系统中的贡献，然后用加权后的卡方距离依据各参考点的指纹信息计算待定位点的实际位置。文中提出的定位算法包括离线训练和在线定位两个阶段。

1.2.1 离线训练阶段

在离线训练阶段，先利用卡方距离结合灵敏度法依据定位区域内的位置指纹信息修正AP的权值。

(1)卡方距离。

使用不同的距离定义方式，可以对分类算法的准确率造成直接影响。以往的距离计算方式如欧氏距离、L1范数等只考虑特征量之间的绝对距离，忽视了特征量之间的相对距离。实际上对于分类来说，相对距离往往更有实际意义。卡方距离可以有效反映特征量之间相对距离的变化，因此用卡方距离构建的分类算法可以获得更优的分类性能［11-13］。卡方距离还可以根据各特征量对分类算法的贡献不同，结合灵敏度法计算在卡方距离的计算方式下每个特征量的权重。

假设两个直方图X，Y是非负且有界的，构造相似度加权矩阵A，则X，Y之间的二次式距离如式(6):

如果矩阵A是X，Y协方差矩阵的逆，则该二次式距离就是马氏距离(Mahalanobis distance)。如果矩阵A是单位阵，则该二次式距离就是欧氏距离。将该二次式距离和卡方距离结合，就形成了二次卡方距离［14］(Quadratic Chi-squared distance，QC)，如式(7)所示:

从式(7)可以看出，二次卡方距离是二次式距离的标准形式，其中m为规格化参数，当A为单位阵且m=0.5时，式(7)可变成式(8):

式(8)就是卡方距离，当m=0时，式(7)就变成二次式距离。

从上面的推导可以看出，卡方距离和马氏距离、欧氏距离一样能够对特征量进行有效度量。

文献［14］还证明了卡方距离具有相似矩阵量化不变性(similarity matrix quantization invariance property)和稀疏不变性(sparseness invariance property)。

卡方距离已被应用到很多用距离描述的分类问题中，并且都取得了相当优异的效果。卡方距离如式(9)所示:

将该式变换到WLAN位置指纹定位工程应用领域，如式(10)所示:

其中，si为待定位点用户设备测到第i个AP的信号强度;dij为位置指纹库中第j个参考点接收到第i个AP的信号强度。

(2)灵敏度法。

在位置指纹定位的工程应用中，卡方距离体现了各实际位置点接收来自各AP的RSS值组成的RSS向量之间的相对关系，但是仍然对每个AP赋予相同的权重，在WLAN位置指纹定位的实际环境中不同AP对定位的贡献不同。因此，应在卡方距离的基础上采用灵敏度法，对不同的AP赋予不同的权重以降低环境噪声的影响，AP权重的计算方法如下所示:

利用采集的位置指纹信息建立位置指纹数据库，把位置指纹信息分为参考点的指纹信息和测试点的指纹信息。具体方法为，先在定位区域内布置参考点，采集参考点的指纹信息，然后在每一个参考点周围布置若干个测试点，采集测试点的指纹信息。

首先，利用卡方距离依据各参考点的指纹信息对离该参考点最近的若干个测试点进行定位，当某测试点获得的来自各AP的RSS向量和该参考点获得的来自各AP的RSS向量之间的卡方距离为最大，而它们的实际物理距离为非最小时，即视为该测试点定位错误。统计定位错误的测试点个数n。

每次在定位系统中去除第 i(i=1，2，…，R)个AP，再用上述方法对测试点进行定位，统计定位错误的测试点个数ni。

其中，wi满足wi=1。

1.2.2 在线定位阶段

在离线训练阶段采用卡方距离度量和灵敏度法计算在实际定位区域中不同AP的权重，在在线定位阶段应用新的距离度量函数依据参考点的指纹信息对用户设备进行定位，具体步骤如下所示:

第一步:采集待定位点用户移动设备接收来自各AP的RSS值，组成待定位点RSS向量。

第二步:根据权重修正后的卡方距离，计算待定位点RSS向量和各参考点RSS向量之间的距离，具体计算方式如式(12):

其中，wi为当前定位系统中第i个AP的权重;si为待定位点用户设备测到第i个AP的信号强度;dij为位置指纹库中第j个参考点接收到第i个AP的信号强度。

第三步:将第二步得到的距离按降序排列，选取Lj值较大的K(K≥2)个参考点作为预定位点，利用式(13)计算最终的定位结果。

其中，(xj，yj)为预定位参考点j的坐标。

总体来说，提出的CSKNN算法包括如下几点:

(1)在WLAN位置指纹定位中利用卡方距离替代欧氏距离进行定位运算。

(2)将定位系统分为离线训练和在线定位两个阶段。在离线训练阶段，把采集的位置指纹信息分为两类:参考点的指纹信息和测试点的指纹信息;利用参考点和测试点的指纹信息依据卡方距离和灵敏度法对AP的权重进行修正。

(3)在在线定位阶段，运用步骤2加权后的卡方距离依据参考点的指纹信息计算待定位点的坐标。

CSKNN定位算法在离线训练阶段和在线定位阶段的基本流程如图2和图3所示。

2实验

定位实验在大连理工大学创新园大厦C区2楼走廊处进行。实验区域包括一个长走廊，两个短走廊，若干办公室和实验室。该区域电子设备较多，工作日课间人员流动量大。

在实验区域共布置6个AP，AP的具体信息为TP -Link TL-WR340G+54 M单天线无线宽带路由器1台，思科WRVS4400N千兆三天线路由器2台，思科RV180W Wireless-N多功能路由器3台。实验所用AP为布置的6个AP。实验分析所采用的数据完全是真实测得，实验过程没有用到任何仿真数据。实验环境如图4所示。

实测设备为装配了D-Link DWA-125无线网卡和Netstumbler采集软件的阿图木X20A-W125上网本，实测的位置指纹信息为各参考点和测试点接收来自实验布置的6个AP(标记为MMCL1-MMCL6)的RSS值组成的RSS向量，单位为dBm。

采集位置指纹信息并建立位置指纹库，把位置指纹信息分为参考点的指纹信息和测试点的指纹信息，其中1/5为参考点的指纹信息，4/5为测试点的指纹信息。具体方法为先采集参考点的指纹信息，再在每个参考点周围选取4个点作为该参考点的测试点并采集指纹信息，在实验环境(图4网格区域)中共放置24个参考点和96个测试点，并标定好这些参考点和测试点的坐标。利用上述卡方距离结合灵敏度法的方法，修正在待测实验环境中每个AP在定位系统中的权重，在在线定位阶段利用加权后的卡方距离依据各参考点的指纹信息，计算待定位点的坐标。

为了验证文中方法，分别利用欧氏距离法和卡方距离结合灵敏度法依据实验环境中的位置指纹信息，对待定位点进行定位。

实验中分别计算上述二种定位方法在每一个待定位点上的定位误差，定位误差由计算位置和实际位置的欧氏距离度量，如式(14)所示:

其中，(xreal，yreal)为第m个待定位点的实际物理坐标;(xcalc，ycalc)为定位算法计算得出的第m个待定位点的坐标。

选出9级数据对比，如表1所示。

在位置指纹定位的工程应用中，常常采用累积分布函数(Cumulative Distribution Function，CDF)来评判位置指纹定位算法的优劣。累积分布函数主要用来表征定位误差门限以下的定位次数与总的定位次数之间的比值。累积分布函数也称作累积误差分布(Cumulative Error Distribution，CED)。

两种方法得到的累计误差分布曲线图见图5。

定位标准差用式(15)来衡量:

最终获得的定位结果:采用欧氏距离法获得的定位误差平均值为1.792 7 m，标准差为0.873 1 m;使用文中方法获得的定位误差平均值为1.414 6 m，标准差为0.814 8 m。

通过图5可以看出，欧氏距离法对环境噪声比较敏感，在受环境噪声影响较大的待定位点定位误差较大，利用文中提出的定位算法可以比欧氏距离更好地对抗环境噪声，以整体提高定位精度。

3 结束语

文中提出一种基于卡方距离和灵敏度法结合的算法(CSKNN)来实现人或物的WLAN定位。CSKNN算法是一种基于距离计算方式改进的KNN算法，其将距离的计算方法从欧氏距离变为了卡方距离。算法能够根据不同的室内环境特点在算法中给各AP赋予不同的权值，有效降低了复杂室内环境对定位精度的负面影响，整个定位系统不用添加任何额外的硬件即可实现。实验结果表明，该算法的定位精度明显优于原始的欧氏距离法。

［1］ Khan A U，Al-Akaidi M.A distributive algorithm for WLAN localization［C］//Proc of 6th international conference on emerging technologies.［s.l.］:IEEE，2010:388-393.

［2］ Gu Y，Lo A，Niemegeers I.A survey of indoor positioning systems for wireless personal networks［J］.IEEE Communications Surveys＆Tutorials，2009，11(1):13-32.

［3］ Zhou M，Zhang Q，Tian Z，et al.IMLours:indoor mapping and localization using time-stamped WLAN received signal strength［C］//Proc of wireless communications and networking conference.［s.l.］:IEEE，2015:1817-1822.

［4］ Ding G，Zhang J，Zhang L，et al.Overview of received signal strength based fingerprinting localization in indoor wireless LAN environments［C］//Proc of 5th international symposium on microwave，antenna，propagation and EMC technologies for wireless communications.［s.l.］:IEEE，2013:160-164.

［5］ 孙善武，王 楠，陈 坚.一种改进的基于信号强度的WLAN定位方法［J］.计算机科学，2014，41(6):99-103.

［6］ 徐玉滨，邓志安，马 琳.基于核直接判别分析和支持向量回归的WLAN室内定位算法［J］.电子与信息学报，2011，33(4):896-901.

［7］ 刘洺辛，孙建利.基于能效的WLAN室内定位系统模型设计与实现［J］.仪器仪表学报，2014，35(5):1169-1178.

［8］ 程金晶，魏东岩，唐阳阳.WLAN指纹定位中AP选择策略研究［J］.计算机技术与发展，2015，25(3):1-5.

［9］ Sohn I.Localization performance analysis of KNN in IEEE 802.11 TGn channel［C］//Proc of ICT convergence.［s.l.］: IEEE，2011:219-220.

［10］牛建伟，刘 洋，卢邦辉，等.一种基于Wi-Fi信号指纹的楼宇内定位算法［J］.计算机研究与发展，2013，50(3):568 -577.

［11］Bosch A.Image classification for a large number of object categories［D］.Girona:University of Girona，2007.

［12］贾世杰，孔祥维.一种新的直方图核函数及在图像分类中的应用［J］.电子与信息学报，2011，33(7):1738-1742.

［13］郑 倩，卢振泰，陈 超，等.基于邻域信息和高斯加权卡方距离的脊椎MR图像分割［J］.中国生物医学工程学报，2011，30(3):357-362.

［14］Pele O，Werman M.The quadratic-chi histogram distance family［C］//Proc of ECCV 2010.Berlin:Springer，2010:749-762.

Improved WLAN Localization Algorithm Based on Chi-square Distance

TAO Zheng1，2，WANG Hong-yu1
(1.Faculty of Electronic Information and Electrical Engineering，Dalian University of Technology，Dalian 116024，China; 2.PLA 92124 Unit，Dalian 116023，China)

WLAN-based localization service has become a hotspot for smarter city nowadays.Among the localization algorithms，the classical Euclidean distance solely keeps count of the absolute distance between the RSSI vector and overlooks the relative distance between the RSSI vector.And it can only give the same weight to every AP.In order to overcome the defects of Euclidean distance，a new algorithm based on Chi-square distance and sensitivity method for WLAN indoor localization is proposed.The algorithm uses fingerprinting technique to make training dataset and testing dataset，then uses Chi-square distance and sensitivity method to correct the training dataset which will be used in the online localization phase and get the weight of every AP in the algorithm in order to improve positioning accuracy.The results show that the proposed algorithm has better accuracy compared with the classical Euclidean distance.

indoor localization;WLAN;fingerprint;Chi-square distance;sensitivity method

TP391

A

1673-629X(2016)09-0050-06

10.3969/j.issn.1673-629X.2016.09.012

2015-11-30< class="emphasis_bold">修回日期:2

2016-03-08< class="emphasis_bold">网络出版时间:

时间:2016-08-01

国家自然科学基金资助项目(61172058);高等学校博士学科点专项科研基金(20120041110011)

陶 峥(1984-)，男，工程师，硕士，研究方向为WLAN室内定位技术;王洪玉，教授，博士研究生导师，研究方向为无线网络。

http://www.cnki.net/kcms/detail/61.1450.TP.20160801.0904.036.html