WiFi指纹定位中改进的加权k近邻算法

doi:10.19665/j.issn1001-2400.2019.05.006

摘要/Abstract

摘要：

针对WiFi指纹定位中传统的信号欧氏距离不能很好地反映各位置点间物理距离的问题,提出了改进的加权k近邻定位算法。首先,在信号距离的计算中引入接收信号强度的方差;然后,根据接收信号强度和物理距离之间的非线性关系引入加权系数,设计了一种信号加权欧氏距离;最后,利用信号加权欧氏距离进行指纹匹配和位置估计,改进了加权k近邻算法。在真实环境下的实验结果表明,信号加权欧氏距离能够更准确地衡量各点之间的物理距离并选择更合理的最近邻参考点。与现有的加权k近邻算法相比,改进的加权k近邻算法能够明显地提高WiFi指纹定位的精度。

关键词: 室内定位, 指纹定位, 加权欧氏距离, 加权k近邻

Abstract:

In WiFi fingerprint positioning, the traditional Euclidean distance of signals cannot well reflect the physical distance between position points. To solve this problem, the weighted k-nearest neighbor positioning algorithm is improved. First, the variance of received signal strength is introduced into the calculation of the signal distance, and a weighted Euclidean distance of signals is designed according to the nonlinear relationship between received signal strength and physical distance. Finally, the weighted Euclidean distance of signals is used for the fingerprint matching and the position estimation, and an improved weighted k-nearest neighbor algorithm is proposed. Experimental results in real environment show that the weighted Euclidean distance of signals can be used to measure the physical distance between points more accurately and select more reasonable nearest neighbor reference points. Compared with the existing weighted k-nearest neighbor algorithms, the improved weighted k-nearest neighbor algorithm can significantly improve the accuracy of WiFi fingerprint positioning.

Key words: indoor positioning, fingerprint positioning, weighted Euclidean distance, weighted k-nearest neighbor

中图分类号:

TN96

王博远,刘学林,蔚保国,贾瑞才,甘兴利,黄璐. WiFi指纹定位中改进的加权k近邻算法[J]. 西安电子科技大学学报, 2019, 46(5): 41-47.

WANG Boyuan,LIU Xuelin,YU Baoguo,JIA Ruicai,GAN Xingli,HUANG Lu. Improved weighted k-nearest neighbor algorithm for WiFi fingerprint positioning[J]. Journal of Xidian University, 2019, 46(5): 41-47.

图/表 10

表1

指纹库数据格式"

参考点序号	位置坐标		来自第1个无线接入点的信号强度统计值		来自第2个无线接入点的信号强度统计值		…	来自第M个无线接入点的信号强度统计值
参考点序号	X轴坐标	Y轴坐标	接收信号强度均值	接收信号强度方差	接收信号强度均值	接收信号强度方差	…	接收信号强度均值	接收信号强度方差
1	$X 1$	$Y 1$	$S 11$	$V 11$	$S 12$	$V 12$	…	$S 1 M$	$V 1 M$
2	$X 2$	$Y 2$	$S 21$	$V 21$	$S 22$	$V 22$	…	$S 2 M$	$V 2 M$
…	…	…	…	…	…	…	…	…	…
N	$X N$	$Y N$	$S 1 N$	$V 1 N$	$S 2 N$	$V 2 N$	…	$S N M$	$V N M$

表1

图1

表2

图2

图3

图4

表3

图5

图6

表4

参考文献 13

[1]	WANG B, LIU X, YU B , et al. Pedestrian Dead Reckoning Based on Motion Mode Recognition Using a Smartphone[J]. Sensors, 2018,18(6):1811.
[2]	WU C, YANG Z, XIAO C . Automatic Radio Map Adaptation for Indoor Localization Using Smartphones[J]. IEEE Transactions on Mobile Computing, 2018,17(3):517-528.
[3]	BAHL P, PADMANABHAN V N. RADAR: an In-building RF-based User Location and Tracking System[C]// Proceedings of the 2000 19th Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway: IEEE, 2000: 775-784.
[4]	齐小刚, 袁列萍, 刘立芳 . 误差修正的声源目标混合定位算法[J]. 西安电子科技大学学报, 2019,46(1):1-7.
	QI Xiaogang, YUAN Lieping, LIU Lifang . Hybrid Location Algorithm for the Acoustic Source Based on Error Correction[J]. Journal of Xidian University, 2019,46(1):1-7.
[5]	BI J, WANG Y, LI X , et al. An Adaptive Weighted KNN Positioning Method Based on Omnidirectional Fingerprint Database and Twice Affinity Propagation Clustering[J]. Sensors, 2018,18(8):2502.
[6]	王跃, 巴斌, 崔维嘉 , 等. 马尔可夫蒙特卡罗的室内定位算法[J]. 西安电子科技大学学报, 2016,43(2):145-149.
	WANG Yue, BA Bin, CUI Weijia , et al. Indoor Positioning Algorithm Based on Markov Monte Carlo[J]. Journal of Xidian University, 2016,43(2):145-149.
[7]	马鑫迪, 马建峰, 高胜 . 室内定位系统中指纹库的优化方法[J]. 西安电子科技大学学报, 2015,42(6):81-87.
	MA Xindi, MA Jianfeng, GAO Sheng . Fingerprint Optimization Method for the Indoor Localization System[J]. Journal of Xidian University, 2015,42(6):81-87.
[8]	ABUSARA A, HASSAN M S, ISMAIL M H . Reduced-complexity Fingerprinting in WLAN-based Indoor Positioning[J]. Telecommunication Systems, 2017,65(3):407-417.
[9]	Niu J, WANG B, SHU L , et al. ZIL: an Energy-efficient Indoor Localization System Using ZigBee Radio to Detect WiFi Fingerprints[J]. IEEE Journal on Selected Areas in Communications, 2015,33(7):1431-1442.
[10]	XUE W, HUA X, LI Q , et al. A New Weighted Algorithm Based on the Uneven Spatial Resolution of RSSI for Indoor Localization[J]. IEEE Access, 2018,6(99):26588-26595.
[11]	LUO R C, HSIAO T J . Dynamic Wireless Indoor Localization Incorporating with an Autonomous Mobile Robot Based on an Adaptive Signal Model Fingerprinting Approach[J]. IEEE Transactions on Industrial Electronics, 2019,66(3):1940-1951.
[12]	ALSHAMI I H, AHMAD N A, SAHIBUDDIN S , et al. Adaptive Indoor Positioning Model Based on WLAN-fingerprinting for Dynamic and Multi-floor Environments[J]. Sensors, 2017,17(8):1789.
[13]	SEIDEL S Y, RAPPAPORT T S . 914MHz Path Loss Prediction Models for Indoor Wireless Communications in Multifloored Buildings[J]. IEEE Transactions on Antennas and Propagation, 1992,40(2):207-217.

接入点	实际位置/m	接收信号强度/dBm	与参考点物理距离的比值	与参考点的信号欧氏距离/ dBm	与参考点的信号加权欧氏距离/ dBm		与参考点信号加权欧氏距离的比值
1个接入点	0
2个接入点	10
1个参考点	15	(-64.16, -50.99)
2个参考点	25	(-70.28, -64.16)
1个测试点	16	(-64.93, -53.18)	0.111 1	(1.64, 8.64)	(1.57, 8.45)	0.189 8	0.185 8
2个测试点	18	(-66.35, -56.63)	0.428 6	(4.27, 6.01)	(4.12, 5.91)	0.710 5	0.697 1
3个测试点	20	(-67.61, -59.30)	1.000 0	(6.36, 3.92)	(6.16, 3.86)	1.622 4	1.595 9
4个测试点	22	(-68.75, -61.49)	2.333 3	(8.10, 2.18)	(7.87, 2.15)	3.715 6	3.660 5
5个测试点	24	(-69.79, -63.33)	9.000 0	(9.59, 0.68)	(9.34, 0.67)	14.102 9	13.940 3

方法	测试点的真实坐标 /m		最近邻参考点的坐标/m															估计的位置/m		定位误差/m
方法	测试点的真实坐标 /m		第1个	第2个		第3个		第4个		第1个	第2个		第3个		第4个			估计的位置/m		定位误差/m
基于欧氏距离的加权k近邻	(4.2, 25.8)	(3.6, 27.6)			(2.4, 30.0)		(3.6, 28.8)		(2.4, 33.6)			0.11		0.26		0.17	0.46		(5.3, 29.6)	3.96
	(39.0, 3.6)	(40.8, 2.4)			(42.0, 6.0)		(39.6, 4.8)		(38.4, 4.8)			0.19		0.41		0.26	0.14		(40.9, 2.3)	2.30
	(10.2, 1.2)	(9.6, 1.2)			(9.6, 0.0)		(12.0, 0.0)		(13.2, 1.2)			0.08		0.19		0.31	0.42		(11.3, 0.6)	1.25
	(25.8, 0.6)	(24.0, 1.2)			(21.8, 0.0)		(28.8, 1.2)		(22.8, 0.0)			0.15		0.32		0.28	0.25		(28.5, 1.7)	2.92
	(0.6, 10.2)	(0.0, 13.2)			(0.0, 8.6)		(0.0, 18.0)		(1.2, 6.0)			0.18		0.12		0.45	0.25		(1.1, 13.5)	3.34
改进的加权k近邻	(4.2, 25.8)	(3.6, 26.4)			(2.4, 28.8)		(3.6, 28.8)		(2.4, 32.4)			0.07		0.21		0.29	0.43		(3.2, 28.1)	2.51
	(39.0, 3.6)	(40.8, 3.6)			(39.6, 4.8)		(38.4, 3.6)		(42.0, 1.2)			0.20		0.28		0.15	0.37		(40.4, 2.9)	1.57
	(10.2, 1.2)	(9.6, 1.2)			(9.6, 0.0)		(13.2, 1.2)		(13.2, 0.0)			0.08		0.17		0.31	0.44		(10.8, 0.9)	0.67
	(25.8, 0.6)	(24.2, 0.0)			(23.0, 1.2)		(28.8, 0.0)		(22.8, 1.2)			0.16		0.22		0.29	0.33		(26.7, 2.1)	1.75
	(0.6, 10.2)	(0.0, 8.4)			(1.2, 13.2)		(0.0, 7.2)		(1.2, 16.8)			0.12		0.20		0.27	0.41		(1.3, 12.2)	2.12

方法	50%定位误差	75%定位误差	平均定位误差	均方根定位误差
改进的加权k近邻算法	1.35	2.48	1.82	1.51
基于欧氏距离的加权k近邻算法	1.76	2.91	2.29	1.95
基于曼哈顿距离的加权k近邻算法	1.81	3.69	2.61	2.14