改进动态K 的WKNN 的室内定位方法

敬振宇，熊兴中，张 维，谢 伟

（1.四川轻化工大学 人工智能四川省重点实验室，四川 宜宾 644000；2.四川信息职业技术学院，四川 广元 628000）

0 引 言

室内定位服务（Indoor Positioning Service，IPS），作为一种基于位置的服务，它主要利用无线通信、射频识别、惯性导航等技术获取移动端的位置信息，完成对室内环境中人员或物体的位置确定[1]。随着射频技术和无线通信技术的快速发展，室内定位服务在日常生活的重要性愈加凸显。WiFi 的普及以及5G 技术等基站的部署[2]，使得快速传输无线数据成为了可能，加之室内定位与人们实际生活息息相关，拥有巨大的商业价值和应用潜力，这些都推动了室内定位的发展。近些年来室内无线定位技术也取得了一些成果，技术不断推陈出新，定位精度也越来越高；但从整体来看，室内定位如果应用于实际环境中，实现一定精度的定位仍是巨大挑战。

无线室内定位技术根据信号类型可分为A-GPS 室内定位[3]、行人航位推算室内定位[4]、射频识别室内定位[5]和WiFi 室内定位[6]。其中，随着无线网络的普及，绝大部分室内环境都可利用WiFi 实现定位，并且WiFi 模块的硬件成本较低，可被集成到各种电子设备中，为室内定位打下硬件基础。因此，WiFi 定位在室内定位领域中具有举足轻重的地位。许多研究学者投身于WiFi室内定位技术研究和相关应用，并且提出了多种解决方案。总体来说，WiFi 室内定位方法一般分为两种，一种基于理论模型的信号强度定位，另一种则是基于指纹库匹配的定位。由于理论模型的应用受环境限制较大，大多数WiFi 室内定位系统都选择指纹库方式[7]。在指纹库定位中，加权K-最近邻（Weighted K-nearest Neighbor，WKNN）算法[8]应用最为广泛。该方法利用在线阶段得到多个匹配点的位置信息，对获取的位置信息进行权重计算，最终得到估计点的位置坐标。但实际中K值的确定并不简单，因此大部分文献都选择固定K值或者选取多个K值进行对比。文献[9]中将K值固定为4；文献[10-11]中将K值固定为3；文献[12]中K值固定为4；文献[13]中选择了多个K值并对比不同K值下的定位情况；文献[14]在传统的WKNN 算法上进行改进，并对改进后的算法在不同K值下进行对比；RADAR[15]对WKNN 中的不同K值对比，并分析不同K值对定位精度的影响，得出结论：定位精度随着K值的增大而变高，但当K值达到某个值后，定位精度会随着K值的增加而降低。

上述文章中，都需要对不同K值对比才能确定一个较好的K值。但在实际环境中，同一环境下也可能由于参考点布设位置差异、测试点高度不同等，同一K值的定位效果并不一致。如果K固定一个较大值，可能会将较远的参考点接纳进来，对最终结果产生影响；若K固定一个较小值，可能会使有贡献点被忽略，同样也对结果产生影响。因此，不能选择同一固定K值用于定位，需要动态选择适当的K值。文献[16]中提出EWKNN（Enhanced Weighed K-Nearest Neighbor），即动态自适应K，采用欧氏距离的均值动态确定K的取值。文献[17]在其基础上增加了对K值为1 的判断和处理。虽然提出的自适应动态K的方法确实提升了定位精度，但仍旧存在欧氏距离的均值并不能够最优表示阈值的问题。文献[16]中，通过RT进行初步的参考点筛选结果对K的获取影响较大，从而影响最终的定位精度；文献[17]在此基础上提出“多雷达搜索策略”的方法确定K值，在某种程度上降低了文献[16]中RT的影响，但整体定位时间大量增加、性能较差，并且文献[16]未曾考虑在线阶段仅匹配一个的情况，而是直接考虑K≥2 的情况，反而可能会引入误差。

本文针对上述问题提出了一种改进的自适应动态K的WKNN 室内定位方法。首先通过高斯滤波优化离线指纹库，接着，在线阶段采用KNN 匹配得到当前匹配点后，利用加入改进泰勒级数展开法滤除误差较大的匹配点，从而实现对K值的确定，最终得出定位结果。本文提出的算法较传统的EWKNN 方法和文献[17]中的方法性能更优，在定位精度上也高于前者，而且整体定位耗时较短。

1 定位算法分析

1.1 WKNN 算法

指纹定位算法是基于信号强度和距离一一对应的室内定位方法，工作主要可以分为前期建立指纹库和匹配阶段。首先在室内环境部署指纹点，根据各指纹点接收到的信号强度和当前的物理位置信息构建位置指纹数据库。在第二阶段，实时获得待测点的RSSI 值，将此信息与位置指纹数据库中的指纹数据依次对比，选择与其特征值最接近的指纹点作为待测点的估计位置。传统的位置指纹算法常用最近邻法对待测点信息和数据库指纹录入，但NN 算法将与指纹点特征信息最接近的点作为待测点的估计信息。由于无线信号的传播特性，该算法容易受噪声干扰，而K 近邻算法在NN 算法的基础上进行改进，相比NN 算法只选择与待测点特征属性最接近的指纹点作为待测点的估计信息，提出了选择K个与待测点特征属性最接近的指纹点，并将K个指纹点特征信息的均值作为待测点的估计信息。随着位置指纹算法的发展与改进，在KNN 的基础上引入了权重思想，将K 近邻点的特征值加权平均作为待测点的估计信息。改进后的加权K 近邻算法较传统的指纹定位算法在定位精度及稳定性方面都有大幅提高。如式（1）所示：

式中：xi是第i个点的横坐标；yi是第i个点的纵坐标；k为匹配点的个数；x,y是待测点的横纵坐标；ωi为第i个点的权值[18]。

1.2 泰勒级数展开法

泰勒级数展开法是一种迭代算法，一般用于非线性方程的最优估计问题。主要步骤是在给定的初始值处进行泰勒展开，将锚节点和未知节点之间的测量距离和当前计算出的距离的差值，作为计算未知节点坐标校正量的依据。具体过程如下：定位算法中存在N个确定位置的已知点，坐标分别为(x1,y1)，(x2,y2)，…，(xi,yi)，而待定位节点的真实位置为(x,y)。而测得待定位节点到已知点的实际距离分别为d1，d2，…，di，到已知点的测量距离分别为：D1，D2，…，Di。此时有Di=di+εi，εi为测量误差。假设未知点的初始估计坐标为(x0,y0)，此时有下述等式：

估计值与真实值有如下关系：

对上式在估计初值(x0,y0)处泰勒展开，去掉高次项后有以下式子：

用矩阵表示为：B=Aδ。

其中：

由矢量矩阵可知，δ=A-1B。判断当前的δ是否小于设定的门限，如果小于设定门限，此时停止迭代，得到未知点的估计坐标；如果δ大于设定的门限，那么就继续迭代直到小于门限或迭代次数用尽。

2 定位算法改进

针对在使用指纹库方式进行测距时，无法避免匹配多个值所带来的误差，尤其在指纹库较大时更容易出现误差的情况，此时若采用泰勒级数展开法对当前匹配值反馈校正，即可对匹配中误差较大的值进行滤除，从而提升测距精度。设计思想是基于WKNN 取出欧氏距离最小的前K条指纹后，继续对前K条指纹进行处理，整个算法分为离线采集阶段和在线定位阶段。

离线阶段中，在定位区域放置m个已知节点，在每一个测量点得出当前已知点的rssi 值，由于rssi 值易受环境影响和易波动的情况，将原本指纹库经由高斯滤波得到新的指纹库，如下式所示：

式中：(xn,yn)为测量点的位置，n为测量点的标号；m为已知点的标号；rssinm代表第n个测量点处接收到标号为m的已知点的rssi 值。而在测距阶段中，当前未知点接收到的rssi 值为[xx yxrssix1rssix2… rssixm]，其中，xx，yx为未知点的坐标，使用当前接收到的rssi 值与指纹库进行匹配。具体步骤如图1 所示。

图1 改进算法流程图

步骤1：离线阶段采集每个测量点的rssi 值，建立离线指纹库，并进行高斯滤波，保留出现概率较高的rssi值，提升匹配精度，降低匹配时间。

步骤2：在线阶段，根据接收到的rssi 值，与指纹库中的指纹匹配得到式（11），在指纹库中采用WKNN 方式进行匹配，保留前k个指纹点。

将当前未知点收到的rssi 值与指纹库中的每一行rssi值求欧氏距离，即：

式中：Oj代表未知点和第j个测量点的欧氏距离；rssixi为当前未知点接收到的第i个已知点的rssi 值，rssiji则意为指纹库中在第j个测量点收到第i个已知点的rssi 值。接着，对求得的Oj进行从小到大排序，仅保留前k个，即：

步骤3：根据前k个指纹点和已知点求出距离di，即其中(xj,yj)为当前指纹库里已知点坐标，(xi,yi)为未知点估计坐标。di为当前未知点和已知点的测量距离。

步骤4：由泰勒级数展开式可得[19]：

考虑在实际定位中，欧氏距离越小的已知点对实际定位贡献度越大。因此，采用一正定对角矩阵体现：式（14）变为：

Q为权重矩阵，其相应行对矩阵B中不同测距信息产生影响，从而对最终估计点坐标产生影响，如此可达到提高精度的目的。矩阵A，B，δ分别如式（7）～式（9）所示，此时Q为：

步骤5：解得δ若小于门限值[20]，保留未知点的估计坐标。此时依据距离差公式，由未知点的估计坐标和匹配的指纹点坐标再次求距离为门限值，此时该点为干扰点。

步骤6：最终剩下的匹配点按照欧氏距离取权重，得出最终的未知点估计坐标。

3 仿真分析与讨论

本文通过实地测试来评估当前算法的定位性能。测试环境为一室内环境。室内环境：实验区域为20×20的方形区域，有书桌等障碍物，使用i(i=2,3,…,6)个参考点，分别为信标1（0，0），信标2（10，0），信标3（20，0），信标4（0，20），信标5（10，20），信标6（20，20）。具体分布示意图如图2 所示。

图2 测试空间分布图

如图2 所示：黑色图形代表参考点的位置，黑色点代表未知点。在离线阶段每隔1 m 取一个指纹点。接下来将和文献[16-17]中的定位方法进行定位性能对比。随机选取10 个点，每个点测量100 次，取其平均值。测试结果如表1 所示。

接着，在测试环境中任意选取100 个未知节点，分别采用文献[16-17]中的自适应动态K和WKNN 改进算法估计坐标值，并与实际坐标值计算估计定位误差进行比较。不同算法实际测试结果如图3 所示。

从图3 的结果可以得出，改进算法的定位误差相较于文献[16-17]中的算法更小并且集中。在此测试环境下，文献[16]的平均定位误差为1.81 m，文献[17]中的算法的定位误差为1.34 m，而改进的WKNN 定位算法定位误差为0.89 m。测试结果表明，改进算法有效地减少了定位误差。

最后，分析整体定位测试的误差分布，如图4 所示是文献[16-17]及改进WKNN 算法的误差范围概率分布图。其中，横坐标是误差范围，纵坐标是误差范围内的概率分布。

表1 待测点的估计坐标和实际坐标

图3 不同算法实际测试结果图

实际测试可知，文献[16]中的算法定位误差最大，而改进的WKNN 算法的定位误差最小。由图4 可得，当定位误差在1.5 m 内时，文献[16]的概率分布大概是0.37，而改进的WKNN 算法的概率分布大概是0.80。显然，在误差距离相同时，改进算法比WKNN 具有更好的概率分布。

4 结 语

本文针对固定K值所带来的额外误差及传统EWKNN 方式所存在的定位性能问题，分析研究WKNN算法和泰勒级数展开法，将这两种方法结合，提出新的动态自适应K值确定方案，研究表明提出的算法比文献[16-17]的动态K算法定位误差更小，且平均定位精度更高，而且定位时间开销增加不大。但文中信标节点布置是比较规范的，并未考虑到随机布设信标节点的情况。下一步需要研究如何在信标节点随机分布时减少未知节点的定位误差。

图4 不同算法实际测试CDF 结果图