基于改进WKNN的位置指纹室内定位算法

陈 空，宋春雷，陈家斌，杨黎明，尹静源

(1.广州汇智通信技术有限公司，广州510000；2.北京理工大学 自动化学院，北京100081； 3.华北光学仪器有限公司，北京100053；4.北京机电工程总体设计部，北京100039)

基于改进WKNN的位置指纹室内定位算法

陈 空1,2，宋春雷2，陈家斌2，杨黎明3，尹静源4

(1.广州汇智通信技术有限公司，广州510000；2.北京理工大学 自动化学院，北京100081； 3.华北光学仪器有限公司，北京100053；4.北京机电工程总体设计部，北京100039)

位置指纹算法是目前解决室内定位问题的主要方法，指纹特征和匹配算法为影响算法精度的两大因素。针对室内复杂环境下Wi-Fi信号强度波动较大的现象，提出了基于方差的加权距离以改进WKNN算法。在离线特征提取阶段，选择了均值和方差两个特征值，既反映该采样点的RSS幅值，也反映该点RSS的波动情况；在线阶段，根据方差提出了加权距离进行相似度的计算，查找距离最近的K近邻点，并以实际环境下采集的数据验证了改进WKNN算法在RSS波动大的情况下对定位效果的改善，在综合考虑了AP组合的影响后，实现了误差均值为1.456m的定位效果。

室内定位；位置指纹；接收信号强度；加权KNN

0 引言

随着智能移动终端的迅猛发展，基于位置的服务(Location Based Services, LBS)有了越来越广泛的应用，人们对位置信息及时、快速、准确获取的需求也越来越强烈。在室外开放性场所，定位技术的发展较为成熟，借助于全球卫星定位系统以及移动通信网络的广泛普及，LBS已经能为用户提供高精度、高稳定性的位置服务，并广泛应用于人们的生活。然而人类活动更多的是在室内环境，如教学楼、图书馆、机场、停车场、仓库、超市等，室内定位技术的研究对实现全球室内外无缝定位具有重要意义[1]。

Wi-Fi作为无线接入技术，它的流行为基于Wi-Fi的定位技术创造了条件。Wi-Fi 网络基础设施部署十分便捷且成本低廉，在城市中人类活动的热点区域，基本都实现了Wi-Fi覆盖。这种依托于Wi-Fi网络的定位技术具有系统成本低、终端数量巨大、传输速率高且通信能力良好等优点，是室内定位技术的研究热点[2]。

相较于室外环境的开阔，室内定位的环境更为复杂，Wi-Fi信号的非视距传播(NLOS)和多径效应使得传统的TOA、TDOA、AOA等几何定位技术的精度受限，而时间和角度测量需要添加相应的硬件设备，成本较高且不利于定位算法的推广[3]。

位置指纹算法采用终端可直接测量的接收信号强度(RSS)信息，利用位置不同的采样点由NLOS和多径效应造成的RSS差异构建唯一的位置指纹。待定位点通过指纹匹配实现位置估计，在Wi-Fi覆盖率足够的情况下，无需任何硬件的添加，通过纯软件即可实现定位，具有低成本、高精度的优点。

本文设计了一种改进的位置指纹室内定位算法，针对接入点信号强度不稳定的无线接入点(AP)，提出了一种WKNN的改进算法，根据采样点信号强度分布的方差信息，设计了距离的计算权值，通过加权距离计算定位点相似性，以削弱RSS不稳定的接入点对距离计算的影响，并进行了实验验证。

1 位置指纹算法

位置指纹算法[4]的基本思想是：将定位区域离散化，采集每个离散点的RSS信息，提取RSS特征向量作为其唯一的指纹信息，根据所有离散点的特征向量构建一个位置指纹库，与实际物理位置一一对应，称其为Radio Map。定位时，通过匹配算法找到Map中与待定位点RSS特征相似度最高的点进行位置估计。

位置指纹定位算法的实现一般分为离线训练阶段和在线匹配阶段，具体流程如图1所示。

图1 位置指纹定位流程图Fig.1 The flow chart of fingerprint algorithm

离线阶段的主要工作有：

1)为定位区域选取合适的采样点(Sample Point)密度，将连续的定位区域离散格点化，通过采集设备对所有的样本点进行RSS信息采集并存入数据库。

2)RSS信息的离群值剔除等预处理工作，并利用处理后的数据进行特征提取[5]，建立Radio Map。

利用RSS特征值建立的Radio Map应该具有如下形式

(1)

在线阶段采集待定位点实时的RSS信号向量，通过匹配算法实现位置估计。

匹配算法采用近邻法，近邻法分为最近邻算法(NearestNeighborhood,NN)、K近邻法(KNearestNeighborhood,NN)和基于K近邻法改进的加权K近邻法(KWeightedNearestNeighborhood,W-KNN)。总的来说，近邻法都是通过采集移动终端实时接收的Wi-Fi信号强度，组成待定位点的RSS向量，计算与指纹库中各个采样点对应的RSS向量的相似度，确定相似度最高的一个或几个采样点，采用平均或者加权平均各个采样点的位置得出用户的位置估计：

(2)

2 基于加权距离的WKNN算法

由于室内环境中墙壁隔断、人员流动、同频干扰等复杂环境的影响，采样点上采集到的RSS会有一定程度的波动，而对发射信号功率稳定性差的AP，这种波动尤为明显。针对信号强度不稳定的AP提出了一种改进的WKNN算法进行匹配。

近邻匹配算法的核心在于寻找与待定位点的RSS向量相似度最高的一个或几个采样点，而相似性的度量方式将影响最终的定位结果。

2.1 欧氏距离

传统的WKNN算法通过计算待定位点与指纹库中样本点的欧氏距离，寻找距离最小的K个点。

若待定位点j接收到N个AP的信号强度均值如式(3)

(3)

则待定位点i与采样点j的欧氏距离dij为两点在N个AP上的信号强度均值之差的平方和，如式(4)

(4)

使用欧氏距离进行相似性计算时，距离反映的是各个AP信号强度的差异，理想情况下为物理位置越接近的点，RSS之间的差值就越小。但是，实际情况中，信号强度的差值不一定完全由物理位置的远近造成，也可能由信号强度自身的波动造成，使得欧氏距离并不能真实反映实际的物理距离。

2.2 基于方差的加权距离

改进的WKNN算法使用了加权距离来寻找K个近邻点，权值的选取与指纹库中样本点的方差相关。

1)方差特征的提取

在离线阶段建立指纹库时，为了使指纹库中每个采样点的特征更为真实地反映其对应物理位置的RSS特征，会在每个采样点上进行多次的样本采集。每个采样点接收到每个AP的信号强度信息都是一个样本集，包含了在该点多次采集的信号强度，如采样点j接收到第t个AP的信号强度信息集为

(5)

其中，Z为每个采样点的样本量。

图2 指纹库特征提取Fig.2 Feature extraction for Radio Map

指纹库中任意采样点j的RSS向量为

其中，N为AP的个数。

由此，每个采样点的信息RSSj包含一个接收信号强度均值的向量rssj和一个接收信号强度方差的向量σj，二者如式(6)

(6)

2)加权距离的计算

加权欧氏距离是针对简单欧氏距离缺点的一种改进方案，相当于为n维向量的不同维度赋予了不同权重，权重与该采样点RSS的方差相关，使用加权距离计算待定位点i与采样点j的距离dij

(7)

(8)

方差反映样本数据分布的离散程度，方差大的采样点，RSS的波动越大，样本集中的样本点与均值差异较大的可能性也越高；方差小的采样点，RSS的分布越集中，任意时刻的信号强度都不会脱离均值太远。

使用加权欧氏距离进行相似性计算时，将方差的倒数作为系数加入到距离的计算中，降低方差大的AP的接收信号强度在距离计算时所占的权重，能一定程度上消除部分RSS波动带来的影响，提高最终的定位精度。

3 仿真与验证

3.1 实验平台

整个Wi-Fi环境搭建都在学校教学楼内，包括3个房间——会议室(左上)、老师办公室(左下)和学生实验室(右下)，和其间的走廊，是一个宽14m、长13m左右的室内区域，平面图如图3所示。

图3 定位区域室内平面图Fig.3 The indoor location area plan

定位区域内不同方位的采样点可扫描到的无线接入点的个数和种类都略有不同，选择了大部分采样点都能扫描到的9个AP，型号分别为NETGEARJNR3300、D-LinkDIR-81、TL-WR2041N，前两种为构成楼内原有的无线网络环境的AP，后一种是为了实现整个定位区域Wi-Fi的无缝隙覆盖所添加的AP。采集终端为联想智能手机LenovoA789，通过内置的网卡和自主编写的采集程序进行采集，软件界面如图4所示。

图4 手机采集软件界面Fig.4 The interface of Wi-Fi signal acquisition software on Android phone

采集软件可以实现对终端所有可搜索到的Wi-Fi信号进行可控次数的主动扫描，获取SSID、RSS以及Mac地址等信息，并将其存入指定文件。终端采样速度不确定，幅值在2次/s～3次/s之间。

根据定位需求和实际环境的分布，以平面图所示的方向建立坐标系，以第一个采样点的位置为原点，在待定位区域建立密度为1.2×1.2的网格采样密度分布。整个数据采集过程中，并未刻意排除人员等利用采集到的采样点的信号强度特征建立位置指纹。定位时，利用待定位点的信号强度信息与网格采样点，进行相似度匹配，以此定位。

样本点和测试点分布如图5所示，蓝点为样本点，每次采集的数据样本量为50条，红点为测试点，采集的数据样本量为10条，共77个采样点和64个测试点。

图5 定位区域样本点和测试点分布图Fig.5 The distribution of sample point and test point in location area

3.2 数据预处理

室内Wi-Fi的RSS具有很大的不确定性，采集过程中可能受到类似人员的流动、门的开闭等突发性的事件影响。在每个采样点具有一定样本量时，突发事件带来的RSS值的跳变可以通过数据对离群值的预处理进行滤除，一定程度上消除突变事件的影响，有助于建立更精确且反映实际信号特征的RadioMap。

离群值是指距离样本其他观察量较远的一个或几个观测量。常用的离群值剔除方法[6]有3σ检测法、格拉布斯(Grubbs)检测法和狄克孙(Dixon)检测法。本文主要采用3σ检测法进行预处理。

图6、图7为RSS的幅值变化曲线的对比，前者为使用3σ法去除离群值前，后者为去除离群值后。

图6 数据预处理前RSS的变化曲线Fig.6 The RSS curve before data pre-processing

图7 数据预处理RSS的变化曲线Fig.7 The RSS curve after data pre-processing

由图6和图7可见，RSS数据在进行预处理前，存在一个脱离大部分样本点的离群值，幅值为-77dBm；通过预处理成功地剔除了该离群值。

3.3 基于加权距离的WKNN算法

本次实验对比了利用欧氏距离进行相似性度量的WKNN和本文所提出的利用加权距离进行相似性度量的改进WKNN对最终定位效果的影响。

实验设备选择了方差较大、分布较为不稳定的5个AP的RSS信息作为匹配的RadioMap，通过对比几个测试点的定位效果如图8所示以及所有测试点的定位误差累积分布曲线如图9所示，展示了两种距离计算方法的定位误差分布情况。

图8 WKNN和改进WKNN定位效果对比Fig.8 Comparison of location result between WKNN and improved WKNN

图8显示了两个测试点以及WKNN算法和改进WKNN算法在K个近邻点选择上的不同结果和对最终定位效果带来的影响。可以看出，基于加权距离的WKNN算法有更好的定位效果。

为了验证改进算法对定位效果有普遍性提高，对所有测试点的定位误差进行统计，定位误差累积分布函数如图10所示。累积分布函数能描述变量的概率分布情况，它表示变量小于或等于某个数值的概率即F(x)=P(X≤x)，定位误差累积分布曲线上的点表示定位误差小于x的概率。

图9 误差累积分布对比图Fig.9 The error CDF comparisons chart between WKNN and the improved WKNN

图10 定位误差曲线Fig.10 The error curve comparisons chart of WKNN and the improved WKNN

从图8、图9、图10和表1都可以明显看出，当定位使用的AP的信号强度变化剧烈、分布不集中时，基于加权距离的改进WKNN算法的定位效果优于一般的WKNN算法。定位误差的最大值从10.14减小到了6.54，误差均值减小了0.72m，方差降到了1.3368。从分布上看，改进WKNN的误差集中在了1～4m的区间，几乎没有6m以上的误差，由此可以得出当使用的AP分布特性较为分散时，基于加权距离的改进WKNN算法有利于提高定位精度。

表1 WKNN与改进WKNN定位误差比对表

3.4 不同AP组合方式的影响

前次实验只选取了方差较大的5个AP进行定位，实际大部分采样点都能采集到9个AP的信号强度信息，为了探究不同AP组合方式建立的Radio Map对最终定位的影响，使用改进的WKNN算法在4种AP组合方式下进行匹配定位。具体的，Map1选择了4个AP，每个房间分布1个；Map2选择了定位区域内的6个AP；Map3选择了自主布置的5个AP和学校布置的2个AP；Map4为所有AP。所有组合方式的定位误差累积分布函数如图11，定位误差的均值、最大值、最小值和方差参数如表2。

图11 不同AP组合方式对定位效果的影响Fig.11 The influence of different AP combinations on location effect

表2 不同AP组合方式定位误差参数对比

从图11和表2中可以看出，在Map3的组合下，匹配算法具有总体来说最好的定位效果，90%的测试点定位误差在2.542m以下，误差均值为1.4564m，最大值为3.7127m。

显而易见，定位时Radio Map所包含的信息越多，AP的个数越多，定位效果也就越好，但当该定位区域AP过多且位置靠近时，可能会出现AP信息的冗余，多余的信息会对相似性的计算造成干扰，最终影响定位精度。因此，定位时需要选择分布较为分散，且能很好反映不同区域特征的AP进行Radio Map的建立，以在最小的计算复杂度下有最高的定位精度。

4 结论

针对信号强度分布不稳定的AP，提出了一种WKNN的改进算法作为匹配算法，在指纹库中添加了方差作为衡量AP信号可信度的特征。根据方差信息，以归一化的方差倒数作为近邻算法的距离计算中向量各个维度的权值，权值的选取削弱了RSS不稳定的接入点对距离计算的影响。在学校教学楼内搭建了Wi-Fi定位的实验环境，建立了与物理空间对应的Radio Map，通过实际数据验证了改进算法在AP信号稳定性差的情况下可以提高定位精度，并对比探讨了AP的组合方式对定位效果的影响。

最终实现在14m×13m的定位区域内，定位误差均值为1.4564m，最大值为3.7127m，90%的测试点定位误差在2.542m以下的定位效果。

在Wi-Fi信号广泛普及的室内环境中，基于Wi-Fi的室内定位技术因其无需硬件添加、系统成本低等优点，成为室内定位方法的重要发展方向。而Wi-Fi信息受环境影响大、不稳定性的特点是限制Wi-Fi定位精度的主要因素。本文提出的基于加权距离的WKNN算法，将信号的波动特征通过方差进行量化并作为权值加入定位算法的距离计算中，有效地降低了Wi-Fi信号不稳定性对定位效果的影响，提高了定位精度，且仅需要在离线阶段增加一定数量的信号强度样本的采集并提取方差加入距离计算，易于实现，具有一定的实用价值。

[1] 邓中亮, 余彦培.室内外无线定位与导航[M].北京邮电大学出版社, 2013：1-2.

[2] 杨铮，吴陈沭，刘云浩.位置计算：无线网络定位与可定位性[M].清华大学出版社,2014：113-115.

[3] 万群，郭贤生，陈章鑫.室内定位理论、方法和应用[M].北京：电子工业出版社，2012：34-36.

[4] Chhavi Sharma, Yew Wong, Soh Fai.Access point placement for fingerprint-based localization[C]//12thIEEE International Conference on Communication Systems，2010: 238-243.

[5] 张兴.WLAN室内定位信号特征提取算法研究[D].哈尔滨工业大学, 2013.

[6] 熊艳艳, 吴先球.粗大误差四种判别准则的比较和应用[J].大学物理实验, 2010, 23(1):66-68.

An Indoor Location Fingerprint Algorithm Based on Improved WKNN

CHEN Kong1,2, SONG Chun-lei2,CHEN Jia-bin2, YANG Li-ming3, YIN Jing-yuan4

(1.Guangzhou Huizhi Intelligence Communications Technology Co.Ltd, Guangzhou 510000, China; 2.School of Automation, Beijing Institute of Technology, Beijing 100081, China; 3.Huabei Optical Instrument Co.Ltd,Beijing 100053, China; 4.Beijing Electro-mechanical Engineering System Design Department, Beijing 100039, China)

Location fingerprint is the main technique to solve the problem of indoor positioning, which is affected by the extraction of fingerprint feature and the matching algorithm.As the fluctuation of Wi-Fi signal strength in complex indoor environment, a weighted distance based on variance to improve WKNN is proposed. On the offline feature extraction stage, the mean and variance of data set as a characteristic is selected, which can not only reflects the magnitude of the RSS of sampling point, but also the fluctuation.On-line stage, a weighted distance based on variance is presented to calculate the similarity and find the nearest K neighbors points.In an actual Wi-Fi environment, the improved WKNN algorithm is verified to improve the performance of the algorithm in the case of large fluctuation of RSS.Finally, after considering the impact of APs, the mean error of position is 1.456m.

Indoor location; Location fingerprint; RSS; WKNN

10.19306/j.cnki.2095-8110.2016.04.011

2015-09-16；

2015-12-26。

陈空(1992-)，女，硕士，主要从事基于WI-FI的室内定位方面的研究。E-mail:ckong1992@163.com

TN92

A

2095-8110(2016)04-0058-07