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

doi:10.19665/j.issn1001-2400.2019.05.006

Abstract

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

CLC Number:

TN96

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.

Figures/Tables 10

参考点序号	位置坐标		来自第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$

References 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

Improved weighted k-nearest neighbor algorithm for WiFi fingerprint positioning

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 13

Related Articles 5

Metrics

Comments

Recommended 10

[1]	QIN Ningning,WU Yisong,YANG Le. Algorithm for multivariate similarity localization based on dynamic fuzzy matching [J]. Journal of Xidian University, 2021, 48(4): 27-35.
[2]	QIN Ningning,WANG Chao. Algorithm for recursive Bayesian localization triggered by temporalseries measurement information [J]. Journal of Xidian University, 2020, 47(4): 10-17.
[3]	LU Hang;CUI Weijia;BA Bin;LU Zhiyu. Visible light localization algorithm based on multi-measurements constraints [J]. Journal of Xidian University, 2017, 44(4): 156-161.
[4]	ZHAO Xiang;LIN Jiming. Theoretical limit of the indoor visible light-image sensor positioning system [J]. Journal of Xidian University, 2016, 43(4): 63-68.
[5]	WANG Yue;BA Bin;CUI Weijia;LU Zhiyu. Indoor positioning algorithm based on Markov Monte Carlo [J]. Journal of Xidian University, 2016, 43(2): 145-149.