基于离散系数改进的VWKNN位置指纹定位算法

许甜; 何泾沙; 朱娜斐; 邓万航; 吴霜; 他永君

doi:10.13700/j.bh.1001-5965.2021.0019

基于离散系数改进的VWKNN位置指纹定位算法

doi: 10.13700/j.bh.1001-5965.2021.0019

北京工业大学信息学部, 北京 100124

基金项目:

国家重点研发计划 2019QY(Y)0601

山东省自然科学基金 ZR2020MF029

详细信息

通讯作者:
朱娜斐, E-mail: znf@bjut.edu.cn

中图分类号: TN92
计量
- 文章访问数: 340
- HTML全文浏览量: 142
- PDF下载量: 34
- 被引次数: 0
出版历程
- 收稿日期: 2021-01-14
- 录用日期: 2021-05-07
- 网络出版日期: 2021-06-18
- 整期出版日期: 2022-07-20

VWKNN location fingerprint positioning algorithm based on improved discrete coefficient

Faculty of Information Technology, Beijing University of Technology, Beijing 100124, China

Funds:

National Key R & D Program of China 2019QY(Y)0601

Shandong Provincial Natural Science Fundation ZR2020MF029

More Information

Corresponding author: ZHU Nafei, E-mail: znf@bjut.edu.cn

摘要

摘要:
位置指纹算法是研究室内定位技术的主要方法，其中在线阶段的匹配算法是影响室内定位精度的主要因素之一。目前，在线阶段的匹配算法有最近邻算法、K近邻算法以及加权K近邻算法。其中，最近邻算法和K近邻算法都没有考虑到不同参考点和待定位点之间的欧氏距离对定位精度的影响，而加权K近邻算法虽然考虑到了欧氏距离对定位精度的影响，对最终的定位结果采用欧氏距离归一化处理进行加权，却没有考虑到AP信号的波动性对定位结果也会产生很大的影响。因此，针对在线阶段的匹配算法作出改进，提出了基于离散系数改进的加权K近邻算法。在离线阶段建立位置指纹数据库，在在线阶段使用离散系数来反映各AP信号的稳定性，进而对待定位点与参考点之间的欧氏距离进行加权，计算出所有的加权欧氏距离后，从中选取距离最近的k个参考点，估算出待定位点的物理位置。实验结果表明：基于离散系数改进的加权K近邻算法可以实现平均定位精度比K近邻算法提高15%~17%，较加权K近邻算法提高了11%~13%的定位效果。
- 室内定位 /
- 位置指纹 /
- AP信号强度 /
- 加权K近邻 /
- 离散系数
Abstract:
The location fingerprint algorithm is the main method to study the indoor positioning technology, and the online matching algorithm is one of the main factors affecting the indoor positioning accuracy. At present, the matching algorithms in online stage include the nearest neighbor algorithm, K-nearest neighbor algorithm and weighted K-nearest neighbor algorithm. However, these three algorithms do not take into account the influence of the fluctuation of AP signal on the positioning result. In order to improve the matching algorithm in online stage, a weighted K-nearest neighbor algorithm based on the improved discrete coefficient is proposed. In offline stage the purpose is to establish a fingerprint database, in the online stage using discrete coefficient to reflect the stability of the various AP signal and treat the anchor point with weighted Euclidean distance between the reference point, calculate all the weighted Euclidean distance, choose the nearest k reference points, so as to estimate the physical location of pending sites. Finally, experiments show that the weighted K-nearest neighbor algorithm based on the improved discrete coefficient can achieve an average positioning accuracy which is 15%-17% higher than the K-nearest neighbor algorithm and 11%-13% higher than the weighted K-nearest neighbor algorithm.
- indoor positioning /
- location fingerprint /
- AP signal strength /
- weighted K-nearest neighbor /
- discrete coefficient

HTML全文

图 1 位置指纹算法定位原理

Figure 1. Positioning schematic diagram of location fingerprint algorithm

下载: 全尺寸图片幻灯片

图 2 VWKNN算法流程

Figure 2. Flowchart of VWKNN algorithm

下载: 全尺寸图片幻灯片

图 3 实验区域参考点及待定位点分布

Figure 3. Reference points and distribution map of pending sites in experimental area

下载: 全尺寸图片幻灯片

图 4 KNN算法在不同k值下的定位误差

Figure 4. Positioning errors of KNN algorithm under different k values

下载: 全尺寸图片幻灯片

图 5 WKNN算法在不同k值下的定位误差

Figure 5. Positioning errors of WKNN algorithm under different k values

下载: 全尺寸图片幻灯片

图 6 VWKNN算法在不同k值下的定位误差

Figure 6. Positioning errors of VWKNN algorithm under different k values

下载: 全尺寸图片幻灯片

图 7 三种定位算法的定位误差比较

Figure 7. Comparison of positioning errors of three positioning algorithms

下载: 全尺寸图片幻灯片

图 8 定位误差累积分布概率对比

Figure 8. Comparison of cumulative distribution probability of positioning error

下载: 全尺寸图片幻灯片

图 9 不同部署方式下3种定位算法的平均定位误差对比

Figure 9. Comparison of average positioning error of three positioning algorithms under different deployment modes

下载: 全尺寸图片幻灯片

表 1 KNN算法的平均定位误差

Table 1. Average positioning error of KNN algorithm

k	平均定位误差/m
1	2.63
2	2.47
3	2.25
4	2.41
5	2.40
6	2.57

下载: 导出CSV

表 2 WKNN算法的平均定位误差

Table 2. Average positioning error of WKNN algorithm

k	平均定位误差/m
2	2.37
3	2.26
4	2.14
5	2.32
6	2.33

下载: 导出CSV

表 3 VWKNN算法的平均定位误差

Table 3. Average positioning error of VWKNN algorithm

k	平均定位误差/m
2	2.23
3	2.13
4	1.91
5	2.12
6	2.24

下载: 导出CSV

表 4 三种定位算法的平均定位误差

Table 4. Average positioning error of three positioning algorithms

定位算法	平均定位误差/m
KNN算法	2.25
WKNN算法	2.14
VWKNN算法	1.91

下载: 导出CSV

表 5 不同部署方式下3种定位算法的平均定位误差

Table 5. Average positioning error of three positioning algorithms under different deployment modes

定位算法	平均定位误差/m
定位算法	1 m间隔	2 m间隔	3 m间隔
KNN算法	2.25	2.53	2.66
WKNN算法	2.14	2.41	2.59
VWKNN算法	1.91	2.09	2.25

下载: 导出CSV

参考文献(21)

[1]	YANG Q, CHEN Y Q, YIN J, et al. LEAPS: A location estimation and action prediction system in a wireless LAN environment[C]//Proceedings of network and Parallel Computing, 2004, 3222: 584-591.
[2]	SKOV-PETERSEN H, BARKOW B, LUNDHEDE T, et al. How do cyclists make their way?-A GPS-based revealed preference study in Copenhagen[J]. International Journal of Geographical Information Science, 2018, 32(7): 1469-1484. doi: 10.1080/13658816.2018.1436713
[3]	MAINETTI L, PATRONO L, SERGI I. A survey on indoor positioning systems[C]//Proceedings of 201422nd International Conference on Software. Piscataway: IEEE Press, 2015: 111-120.
[4]	刘琚, 李静. 一种在非视距环境中的TDOA/AOA混合定位方法[J]. 通信学报, 2005, 26(5): 63-68. https://www.cnki.com.cn/Article/CJFDTOTAL-TXXB200505010.htm LIU J, LI J. A hybrid TDOA/AOA localization method in a non-line-of-sight environment[J]. Journal of Communications, 2005, 26(5): 63-68(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-TXXB200505010.htm
[5]	赵强, 王敬东, 刘云霄, 等. 基于粒子群TOA室内定位的系统误差修正[J]. 电子测量技术, 2017, 40(8): 189-192. doi: 10.3969/j.issn.1002-7300.2017.08.042 ZHAO Q, WANG J D, LIU Y X, et al. Systematic error correction based on particle swarm TOA indoor positioning[J]. Electronic Measurement Technology, 2017, 40(8): 189-192(in Chinese). doi: 10.3969/j.issn.1002-7300.2017.08.042
[6]	LUO M Z, CHEN X, CAO S, et al. Two new shrinking-circle methods for source localization based on TDoA measurements[J]. Sensors, 2018, 18(4): 1274-1279. doi: 10.3390/s18041274
[7]	田增山, 张千坤, 周牧, 等. 基于CFR虚拟阵列天线的AOA室内定位[J]. 电子学报, 2018, 46(6): 1468-1474. TIAN Z S, ZHANG Q K, ZHOU M, et al. AOA indoor positioning based on CFR virtual array antenna[C]//Acta Electronica Sinica, 2018, 46(6): 1468-1474(in Chinese).
[8]	REMPEL P, BORISOV A, SIEMENS E, et al. Local system of positioning using a WiFi network[C]//MATEC Web of Conferences, 2018, 155: 01014.
[9]	PRASITHSANGAREE P, KRISHNAMURTHY P, CHRYSANTHIS P K. On indoor position location with wireless LANs[C]//Proceedings of IEEE International Symposium on Personal. Piscataway: IEEE Press, 2002: 720-724.
[10]	王文森. 变异系数-一个衡量离散程度简单而有用的统计指标[J]. 中国统计, 2007(6): 41-42. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGTJ200706024.htm WANG W S. Coefficient of variation-A simple and useful statistical measure of dispersion[J]. China Statistics, 2007(6): 41-42(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-ZGTJ200706024.htm
[11]	WANG Q, FENG Y, ZHANG X, et al. IWKNN: An effective bluetooth positioning method based on isomap and WKNN[J]. Mobile Information Systems, 2016, 2016: 876585.
[12]	薛伟, 陈璟, 张熠. 基于深度学习的Wi-Fi与iBeacon融合的室内定位方法[J]. 计算机工程与应用, 2019, 55(1): 29-34. https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201901005.htm XUE W, CHEN J, ZHANG Y. Indoor positioning method based on deep learning fusion of Wi-Fi and iBeacon[J]. Computer Engineering and Applications, 2019, 55(1): 29-34(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201901005.htm
[13]	田家英, 张志华. 基于近邻法的WIFI室内定位改进算法研究[J]. 测绘工程, 2018, 27(12): 34-39. https://www.cnki.com.cn/Article/CJFDTOTAL-CHGC201812007.htm TIAN J Y, ZHANG Z H. Research on improved WIFI indoor localization algorithm based on nearest neighbor method[J]. Engineering of Surveying and Mapping, 2018, 27(12): 34-39(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-CHGC201812007.htm
[14]	吴虹, 王国萍, 彭鸿钊, 等. 一种基于KNN的室内位置指纹定位算法[J]. 南开大学学报(自然科学版), 2020, 53(6): 5-9. https://www.cnki.com.cn/Article/CJFDTOTAL-NKDZ202006002.htm WU H, WANG G P, PENG H Z, et al. An indoor location fingerprint algorithm based on KNN[J]. Acta Scientiarum Naturalium Universitatis Nankaiensis, 2020, 53(6): 5-9(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-NKDZ202006002.htm
[15]	田洪亮, 钱志鸿, 梁潇, 等. 离散度WKNN位置指纹Wi-Fi定位算法[J]. 哈尔滨工业大学学报, 2017, 49(5): 94-99. https://www.cnki.com.cn/Article/CJFDTOTAL-HEBX201705015.htm TIAN H L, QIAN Z H, LIANG X, et al. Dispersion WKNN position fingerprint Wi-Fi location algorithm[J]. Journal of Harbin Institute of Technology, 2017, 49(5): 94-99(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-HEBX201705015.htm
[16]	BAI H, YAN W. Application of NN-KNN algorithm combined with cloud-based indoor positioning[J]. Metallurgical and Mining Industry, 2015, 7(5): 383-388.
[17]	卢选民, 院文乐, 邱杨, 等. 一种改进的基于KNN的动态预测指纹定位算法[J]. 计算机应用研究, 2017, 34(7): 63-66. https://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ201707022.htm LU X M, YUAN W L, QIU Y, et al. An improved dynamic predictive fingerprint location algorithm based on KNN[J]. Application Research of Computers, 2017, 34(7): 63-66(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ201707022.htm
[18]	王亚涛, 王新珩, 董育宁, 等. 基于Kmeans和动态WKNN的两层Wi-Fi改进定位方法[J]. 南京邮电大学学报(自然科学版), 2017, 37(5): 41-47. https://www.cnki.com.cn/Article/CJFDTOTAL-NJYD201705008.htm WANG Y T, WANG X H, DONG Y N, et al. Improved localization method for two-layer Wi-Fi based on Kmeans and dynamic WKNN[J]. Journal of Nanjing University of Posts and Telecommunications(Natural Science Edition), 2017, 37(5): 41-47(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-NJYD201705008.htm
[19]	YEN L, YAN C H, RENU S, et al. A modified WKNN indoor Wi-Fi localization method with differential coordinates[C]//Proceedings of 2017 International Conference on Applied System Innovation (ICASI). Piscataway: IEEE Press, 2017: 1822-1824.
[20]	WANG B, GAN X, LIU X, et al. A novel weighted KNN algorithm based on RSS similarity and position distance for Wi-Fi fingerprint positioning[J]. IEEE Access, 2020, 8: 30591-30602.
[21]	ALIPPI C, VANINI G. A RSSI-based and calibrated centralized localization technique for wireless sensor networks[C]//Proceedings of IEEE International Conference on Pervasive Computing & Communications Workshops. Piscataway: IEEE Press, 2006: 301-305.