缪 颖，朱正伟，诸燕平

(常州大学微电子与控制工程学院，江苏 常州 213164)

1 引言

室内定位这一技术一直以来都是基于位置服务的研究热点，并且在快速发展着，由于在室内或荫蔽处无法接收到卫星信号，所以GPS和北斗等卫星导航定位系统无法在室内使用[1]。为了实现“最后一公里”的精确导航，各种室内定位技术成为近年来大量科研工作者的研究热点[2]。

按照传输信号不同，室内定位技术可以分为基于WiFi、RFID、ZigBee、蓝牙、超宽带、红外线、磁场、超声波、伪卫星等多种定位方式[3]。其中基于WiFi的定位技术由于WiFi硬件的普及而受到重视[4]。在基于WiFi技术的室内定位中，K近邻(K-nearest neighbor，KNN)凭借其算法简单且易于实现的优势而得到广泛的研究，早在2000年的时候，微软就开始进行WiFi指纹室内定位的研究工作，并将KNN方法首次运用到室内定位中。

微软研究院的Bahl等人[5]提出使用KNN方法进行指纹定位，将待测指纹与指纹库进行匹配得到K个最相似的指纹实现定位。基于KNN算法，香港科技大学的Lionel 、Liu 、Lau等人[6]提出了加权K近邻法(weighted K-nearest neighbors，WKNN)，按照待测指纹和离线数据库在信号空间上的欧氏距离分配权重，定位精度得到了提升。韩国世宗大学的Beomju等人[7]提出了改进加权EWKNN算法，通过改变K值来提高指纹识别的准确性，同样改善了定位效果。北京航空航天大学的牛建伟[8]等人提出了属性加权KNN算法，将无线接入点(access point，AP)之间的相关性运用到权重调配中，得到较好的定位成果。中国矿业大学的毕学京[9]等人提出了高斯函数定权的GWKNN室内定位方法，这种方法有效改善了定位精度。文献[10]基于K近邻算法提出了一种监督特征选择方法，结合了距离加权和属性加权的优点进行特征选择，具有较好的预测性能，本文借鉴了该论文利用最近邻的最相关属性确定目标变量的思想，提出了基于距离和属性加权的室内定位方法FWKNN。利用主特征RSS的权重计算加权距离，由该距离取代传统的欧式距离，对K个最近邻加权距离分配权重，在此基础上利用卡尔曼滤波精确定位结果，有效提高了定位精度。

2 KNN室内定位

2.1 基于RSS的WiFi指纹定位技术

WiFi指纹定位算法分为离线采样和在线定位两个阶段。在离线阶段，按网格点采集对应RSS值，构建离线指纹数据库。在在线阶段，实时获取当前RSS值，运用某种定位算法，通过与离线数据库进行匹配来定位，如图1所示。

图1 基于RSS WiFi指纹定位技术原理

2.2 KNN室内定位

KNN室内定位算法是将在线测试点处的RSS值与离线数据库中的RSS值进行匹配，先计算测试点和参考点的RSS距离，然后选取K个最小距离，以及其对应的参考点，最后对其坐标取均值由此得出在线测试点的估计位置。

在离线阶段要完成离线数据库的构建，将定位区域分为n个网格点，第i个网格点由坐标Li(xi，yi)表示，i=1，2，…，n，假设该区域由m个WiFi AP覆盖，在第i个网格点接收到的RSS值表示为Fi(ri1，ri2，…，rim)，rim表示该样本中接收到来自第m个AP的RSS值，由此构建离线指纹数据库D=(Li，Fi)。

(1)

(2)

3 距离和属性加权的FWKNN

3.1 距离加权

距离加权的KNN算法的基本思想是：在线测试点与离线样本的距离越小关系越密切，根据它们之间的距离大小给离线样本赋予不同的权重，距离越小权重越大。权重是通过函数w(·)实现的距离变换而得到的。那么，用于预测的式(2)可以重写为式(3)

(3)

对距离进行权重赋值最简单的方法就是权重定义为距离的倒数，但是这种方法在距离很小时权重会很大甚至无限大，对算法造成干扰。为了克服这种缺点，选择使用高斯函数来进行权重计算，其形式如下

本文使用其标准正态分布形式，即b=0，c=1。为了保证距离为0时权重为1，令a=1，即函数w(·)可以表示为式子(4)，距离与权重的关系图像如图2所示。

(4)

图2 距离与权重关系图像

函数w∈[0，1]，满足一下性质

1)w(0)=1

2)函数w(·)递减(较大的距离意味着较低的函数值)

3)limd→infw(d)=0

3.2 属性加权

按属性加权的KNN算法的基本思想是：当属性比较多的时候，这些属性对结果的影响并不相同，可能会有一些无贡献的属性，所以不能对这些属性一视同仁，如果没有区别的去对待它们，那么在计算欧式距离时，一些关键属性对结果的影响就会被削弱，使得最终结果出现较大偏差，所以需要对不同的属性赋予不同的权重[8]。

把定位点接收到的RSS称为主特征，因为RSS在定位中是十分重要的，如图3，假设有六个AP，一个定位点可以接收到来自六个AP的RSS值，即六个主特征，但这六个特征对定位结果的贡献并不相同，如图所示b点与AP6之间有障碍物的阻挡，此时b点接收到的来自AP6的RSS值并不准确，会影响近邻点a的选择，造成定位结果的偏差。当b点位于靠近AP6的角落时，受墙壁的折射影响也会更大，接收到来自AP6的RSS值同样对定位结果的贡献不大，会对更相关的主特征RSS定位造成影响。

图3 RSS对定位性能的影响

受属性加权思想的启发，对Fi(ri1，ri2，…，rim)中的所有主特征分配一个权重，该权重确定主特征对于预测测试点坐标的可靠性，这个可靠性使用在线测试点和离线样本对应RSS值的差(特征距离)来衡量，对不同的特征距离赋予不同的权重，特征距离越大所赋予的权重就越小，减小不相关主特征RSS对定位性能的影响。

(5)

采用高斯函数确定不同距离的特征的权重，即为特征权重，表示为式(6)

(6)

3.3 距离和属性

本文提出的距离和属性加权定位方法FWKNN结合了距离加权和属性加权两种方法的优点，由最近邻的最相关主特征RSS来预测在线测试点的位置。

(7)

此距离用于选择最近邻的K个坐标Lj(j=1，2，…，K)，加权距离能够更准确的计算各点的距离并选择合适的最近邻点。

利用式(8)计算预测坐标

(8)

为了说明所提出的加权距离的优势，本文基于仿真数据对传统欧式距离和加权距离进行了比较。考虑4个测试点，2个参考点和4个WiFiAP接入点，由仿真获取各点的坐标及RSS值并进行计算，如图4所示。分别计算测试点与两个参考点之间的实际坐标距离比值rd，信号欧式距离比值ed、加权距离比值wed。表1是4个测试点与2个参考点间的信号欧氏距离和加权距离的比较。可以看出，与欧式距离相比，测试点和参考点间的加权距离的比值更接近于实际坐标距离的比值，因此使用加权距离来选择近邻点是优于传统欧式距离的。

图4 仿真获取数值进行计算

表1 信号欧式距离和加权距离

FWKNN算法的流程图如图5所示。

图5 FWKNN算法流程图

由上述定位方法可以得到在线测试点的一个位置估计，然后可以根据上一时刻的位置和速度来预测出当前位置。综合这个预测位置和定位方法所得的估计位置，对它们做一个加权平均作为最终定位结果，权值的大小由估计位置和预测位置的不确定性程度决定，本文按照卡尔曼滤波的方法做加权，由此得到一个更加精确的定位结果。

卡尔曼滤波器预测原理如下：

1)由上一时刻的状态加上外界的输入预测当前状态。

2)预测过程增加的新的不确定性，加上之前存在的不确定性构成预测结果的不确定性。

3)计算卡尔曼增益(权重)，根据预测值和观测值的不确定性来计算。

4)对预测值和观测值这两个结果做加权平均，得到当前的一个状态估计。

5)更新本次状态估计的不确定性。

4 实验

4.1 获取RSS数据

本文使用实际测量的RSS数据建立离线指纹数据库进行定位算法的验证分析，定位环境设置在某实验楼五楼实验室，实验室放置了6个WiFiAP用于RSS数据的采集。定位区域长为9.6m，宽为6.6m，测量时每隔0.3m进行RSS数据测量，共673个参考点，以1s的频率采集RSS值，在每个参考点处测量20s，然后取20次测量数据的平均值作为该参考点的测量结果，建立离线指纹库。另外又测量了五个行走轨迹作为测试数据，每个轨迹包含40个测试点，如图6所示。

图6 定位区域示意图

4.2 实验结果与分析

本文采用距离误差作为性能指标，对KNN、GWKNN[9]和FWKNN等定位算法进行计算和比较，并且比较了FWKNN算法在卡尔曼滤波前后的结果，同时将FWKNN算法与多种定位模型进行了比较。

图7 不同数量最近邻点下的平均定位误差

为了验证所提出的算法能够显著提高定位精度，以轨迹1为测试数据进行验证。首先对最近邻点个数以及WiFiAP个数对定位性能的影响进行探究。图7是FWKNN算法在不同数量的最近邻点下的平均定位误差，从图中可以看出结果随着近邻点个数的不同呈现出一个波动的状态，过大过小都会导致误差增大，当最近邻点数为9时平均定位误差最优。图8显示了不同数量的WiFiAP对不同定位方法影响，可以看出6个AP足以用来进行定位算法的验证比较。当选取的最近邻点个数为9时，FWKNN、GWKNN和KNN的定位误差累计概率分布如图9所示，从概率分布图中可以得出FWKNN的平均误差在2m以内的概率约为70%，GWKNN的平均误差在2m以内的概率约为50%，KNN的平均误差在2m以内的概率为40%左右。

图8 AP数量的影响

图9 定位误差累积概率分布图

以轨迹1为测试数据，最近邻点数为9对KNN、GWKNN和FWKNN进行具体分析。表2是三种算法的定位误差。从表中可以看出，从均值和最大值误差来看，FWKNN方法都是优于KNN和GWKNN的，误差最小值较KNN和GWKNN大，但也没有相差多少。以轨迹1为测试数据，就平均定位误差而言，本文所提出的距离和属性加权的定位方法FWKNN的定位精度与GWKNN相比提升了27.5%，与KNN相比提升了37.1%。

表2 定位误差对比 m

本文尝试使用卡尔曼滤波方法来精确FWKNN算法的定位结果，图10为FWKNN在卡尔曼滤波前后的定位误差累积概率分布图对比，测试数据为轨迹1，最近邻点数为9。表3是滤波前后定位误差。经卡尔曼滤波后的FWKNN算法虽然定位误差均值较滤波前大，但是从定位误差累积概率分布图中可以看出，在2m内的定位精度滤波后较滤波前是有明显提升的，滤波后FWKNN算法的定位精度在2m以内的概率提升到80%左右，而滤波前只有70%左右。

图10 卡尔曼滤波前后定位误差累积概率分布图

表3 滤波前后定位误差对比 m

为了更直观的显示本文所提出的FWKNN算法能有效提高定位精度，以五个行走轨迹为测试数据，对KNN、GWKNN和FWKNN等定位算法进行计算和比较，图11给出了测试点数为40～200时不同算法的平均定位误差。从图中可以看出，FWKNN算法的定位误差始终低于其它两种算法。总体而言，当选取的最近邻点个数为9，测试点个数为200时，本文所提出的FWKNN算法的平均定位误差为1.96m，与KNN和GWKNN相比分别提升了34.6%和27.1%。

图11 不同个数测试点的平均定位误差比较

表4是当测试点个数为200时，本文提出的FWKNN定位算法与多种定位模型的定位均值误差表。由表4可以看出本文提出的FWKNN定位算法的定位精度优于支持向量回归等多种定位模型。

表4 多种定位方法的均值误差比较 m

5 结语

本文提出了距离和属性加权的KNN室内定位方法FWKNN，结合了距离加权和属性加权这两者的优点，利用主特征RSS的权重计算加权距离，该距离取代了传统的欧式距离，对K个最近邻加权距离分配权重，加权均值，由最近邻的最相关主特征RSS预测测试点坐标。与KNN、GWKNN等定位算法相比，考虑到了主特征RSS的权重，能够更准确的计算各点的距离并选择合适的最近邻点，平均定位精度分别提高了34.6%和27.1%。并且实验证明了卡尔曼滤波能够精确定位结果，滤波后FWKNN算法的平均定位误差在2m以内的概率由原来的70%左右提升到80%左右。同时实验结果还表明，FWKNN算法与其它多种定位模型相比都具有一定优势。