李连亮（重庆邮电大学信息无障碍工程研发中心,重庆　400065）

基于LANDMARK系统的KNN室内定位改进算法

李连亮
（重庆邮电大学信息无障碍工程研发中心,重庆400065）

摘要：针对LANDMARC系统中传统k最近邻算法（KNN）中定位精度不高计算量大的问题，提出了一种改进的定位算法，通过利用MICA2传感网络协助，把整个定位区域分成若干个分区，利用传感网络确定目标节点在哪一个分区，消除远离目标节点的参考节点，缩小了k值的选取范围，在分区内再采用基于泰勒级数展开法的KNN算法计算出目标节点的坐标提高精度，并依据改进后的算法开发出了相应的软件界面实测表明本文提出的算法在精度上比原算法有了明显的提高。

关键词：射频识别技术（RFID）;无线传感网络;最近邻算法（KNN）;接收信号强度指示（RSSI）

0　引言

随着物联网的发展，位置服务（LPS）受到人们越来越多的关注，对移动目标定位方法的研究也随之深入。针对室内复杂环境的定位技术一直是研究的难点。目前，RFID定位技术[1]以其非接触、非视距、高灵敏度和低成本的优点，正在成为室内定位系统的优选技术，受到了更多的关注。目前，出现了许多利用RFID进行定位的定位系统，如LANDMARC[2]、SpotOn[3]、BVIRE等。K-最近邻算法（KNN）作为常用的定位算法，通过比较目标节点信号强度值（RSSI）与各个参考节点信号强度值（RSSI）的相对大小，计算目标节点的坐标。由于RSSI容易受环境中温度和噪声的影响，在选择K个参考节点时常常会包含那些偏离目标节点较远的参考节点，对定位精度造成很大影响。本文针对K-最近邻算法存在的这些问题提出一种改进方法，首先利用传感器信息建立网络协助，确定目标节点所在的区域，计算目标节点的初步坐标，最后利用Taylor级数展开方法对坐标迭代，得到目标节点的精确位置，提高定位精度。

1　K-最近邻定位算法

假设有m个读写器和n个参考节点以及u个目标节点。对任一目标节点，其场强值向量表示为，其中Tj代表第j个读写器采集到的目标节点场强值；对第i个参考节点，其场强值向量表示为，其中代表第j个读写器采集到的参考节点i的场强值。为了判断参考节点与目标节点之间的差值程度，对于任一目标节点p，，有

在公式（1）中Ei表示第i个参考节点与目标节点之间的距离大小，Ei越小表示距离越近，。通过比较Ei值的大小，将K个离目标节点最近的参考节点（即最近邻节点）放入同一集合，并定义K个最近邻节点的权值为

2　改进KNN算法

2.1利用传感器建立网络协助

首先利用传感器信息将环境区域划分为多个分区。在初始化阶段中，首先在静态环境（没有定位目标和噪声的干扰）下，通过传感节点建立静态表（即在静态环境下传感节点与其它传感节点之间的平均信号强度），并存储静态RSSI值。当待定位的目标节点在传感网络覆盖区域内时，传感节点之间的RSSI值会出现波动。当无待定位目标节点时，RSSI会出现3～5dBm的波动；当有目标节点时，RSSI值在18～20dBm之间波动。所以根据RSSI值的波动值大小确定有效链路。如果某一链路的RSSI波动值大于18dBm值，表示该链路为一个有效的链路[4]。

定位阶段利用交叉方法确定待定位目标节点所在分区，当某一分区内存在多条有效链路，则表示待定位目标节点在该分区内。通过对每个分区分配权值，权值越大则越靠近待定位目标节点。对所有交点的权值取平均值来计算定位节点的位置。

假设传感器网格有c个分区，每分区的权值Wi，对于所有分区的权值可以表示为一组，则Wi表示为：

2.2Taylor级数展开法

为使公式整洁，上式（6）中后两项的Fi表示。当测量距离与估计距离之间距离差为足够小时说明估计点准确，于是可将（6）式写成矩阵形式：

3　实验验证

在实验室构建实时定位系统，传感节点选择MICA2。选择MICA2的原因是一是其具有很强的路由能力；二是MICA2的频率是870MHz，这样不会与RFID收发信号造成干扰。传感器节点以广播的形式周期性地发送信号，默认时间间隔为0.3s。在10m×10m的实验环境下，参考节点、读写器和传感节点摆放方式如图1所示。在测试环境下对20个定位节点（其中①②③位于边界）进行测试，定义误差为，其中表示目标节点的实际位置，表示目标节点的系统得出的估计位置。其中参考节点间距为1.5m。为评估本文提出的定位方法，通过和KNN[5]对照来评估本文提出方法的性能。

通过图2可以看到，在同样环境下，使用最近邻居算法定位的平均估计误差是1.34m，最大平均估计误差是2.2m；使用本文改进算法定位的平均估计误差是0.95m，最大平均估计误差是1.8m。同时对位于边界的（①②③｡｠）节点的两种定位方法误差进行对比，可以看出，本文提出的算法跟最近邻算法相比在边界定位方面同样具有很好的效果。而通过图3可以看到，对比LANDMARC系统的最近邻算法和本方法可以发现，统计误差小于1m，仅用KNN算法的累积误差概率为82.5%，而本文提出的方法为89.2%，由此看出后者具有较好的定位精度。之后还对两种算法的计算效率进行了对比，利用KNN定位算法和本文提出的定位算法计算100个目标节点，各自所需时间如图4所示

从图4可以看出本文提出的改进算法比典型的KNN算法在计算时间明显减少很多，而且参考节点数目越多，效果越显著。实验结果表明，KNN算法通过计算目标节点的最近邻节点数目进行定位，参考节点越多，计算花费时间越多，而本文提出的改进方法利用建立传感网络协助，这样就减少要计算的参考节点数目，进而减少了所需计算时间，提高了算法的效率。

4　结束语

本文基于最近邻定位算法，提出了一种改进算法，直接消除了远离目标节点的参考节点，缩小了k值的选取范围，克服了随机误差，减少了算法的计算量，并对边界定位具有很好的效果。本文的测试是在实验室的环境下模拟真实的环境中进行的，贴近实际应用的室内环境。实测表明本文提出的改进算法精度在1.5m以内，定位的最大误差减小，且平均精度较之原算法有了很大的提高。

参考文献：

[1]李程,钱松荣.射频识别动态定位方法[J].通信学报,2013, 34(04):144-148.

[2]秦爽.参数化多维标度定位方法研究[D].成都：电子科技大学,2013.

[3]SANSANAYUTHT,SUKSOMPONGP,CHAREONLARPNOPPARUTC,etal. RFID2D-localizationimprovementusingmodif iedLANDMARCwi th l inearMMSEest imation[C].Communicat ionsandInformat ion Technologies(ISCIT),201313thInternationalSymposiumon. IEEE,2013:133-137.

[4]朱剑,赵海,张希元等.基于LQI量度的无线链路质量评估模型[J].东北大学学报:自然科学版,2008,29(09):1262-1265.

[5]闫保中,姜琛,尹伟伟.基于RFID技术的室内定位算法研究[J].计算机仿真,2010(02):320-324.

作者简介:李连亮(1987-)，男，山东菏泽人，硕士研究生，主要研究方向：射频识别，无线定位。