模糊聚类下的接入点选择匹配定位算法

doi:10.19665/j.issn1001-2400.2022.04.009

摘要/Abstract

摘要：

针对指纹定位中传统聚类方法难以有效划分物理空间以及信号源不稳定导致定位误差大的问题,为降低数据库存储成本与提高指纹质量,提出了一种基于模糊聚类的精简接入点匹配定位算法。该算法在离线阶段将面积较大的目标区域按信号源特征划分为多个重叠模糊分区,综合考量各分区中信号源的稳定可见性及冗余性等多尺度特征,建立区域最小接入点辨识集合,在提高定位实时性的同时削弱不稳定接入点信号带来的匹配失准的缺陷。在位置计算阶段结合区域接入点稳定性特征分配近邻点权重,以此对传统欧氏距离进行改进,同时依靠待定位用户运动过程中相邻时刻间的速度约束关系筛选定位野值,克服环境和信号源变化对定位结果带来的不利影响,降低定位误差。经实测场景测试,所提算法在对接入点进行有效筛选的前提下降低了定位算法的运算消耗,在显著减少离线数据存储量的同时,将定位场景的平均定位误差控制在了1 m以内,较已有经典定位方法,其定位精度提高了15%以上。

关键词: 室内定位, 指纹定位, 模糊聚类, 接入点选择

Abstract:

Considering the problem that it is difficult for the traditional clustering method to divide physical space effectively,and that the positioning error is large due to instability of the signal source,aiming at reducing the storage cost of database and improving the quality of the fingerprint,this paper proposes a simplified access point matching location algorithm based on fuzzy clustering.According to the proposed algorithm,in the offline stage,the target space of a large area is divided into multiple overlapping fuzzy partitions by the characteristics of the signal source,the stability,visibility,redundancy and other multi-scale characteristics of the signal source in each partition are comprehensively considered,the smallest access point identification set in the area is established,the positioning speed is improved and the defects of mismatch caused by the unstable access point are decreased.In the position calculation stage,the traditional Euclidean distance is improved by assigning the weight of the neighbor points in combination with the stability characteristics of the regional access points,and the speed constraint relationship between adjacent moments during the movement of the user to be located is used to filter the positioning outliers,to overcome the changes in the environment and signal sources.The unfavorable influence of the locating error is reduced.Tested on actual scenes,the proposed algorithm reduces the computational consumption of the positioning algorithm on the premise of effectively screening the access points,while significantly reducing the offline data storage and controlling the average positioning error of the positioning scene within 1m.Compared with the existing classic positioning methods,the positioning accuracy of this algorithm is improved by more than 15%.

Key words: indoor positioning, fingerprint positioning, fuzzy clustering, access point selection

中图分类号:

TN96

秦宁宁,张臣臣. 模糊聚类下的接入点选择匹配定位算法[J]. 西安电子科技大学学报, 2022, 49(4): 71-81.

QIN Ningning,ZHANG Chenchen. Access point selection matching localization algorithm based on fuzzy clustering[J]. Journal of Xidian University, 2022, 49(4): 71-81.

图/表 11

图1

图2

图3

图4

表1

图5

图6

表2

表3

图7

表4

参考文献 18

[1]	SHEN Z, LI J, WU Q. Data-Driven Interference Localization Using a Single Satellite Based on Received Signal Strength[J]. IEEE Transactions on Vehicular Technology, 2020, 69(8):8657-8669. doi: 10.1109/TVT.2020.2998795
[2]	王博远, 刘学林, 蔚保国, 等. WiFi指纹定位中改进的加权k近邻算法[J]. 西安电子科技大学学报, 2019, 46(5):41-47.
	WANG Boyuan, LIU Xuelin, WEI Baoguo, et al. Improved Weighted k-Nearest Algorithm for WiFi Fingerprint Positioning[J]. Journal of Xidian University, 2019, 46(5):41-47.
[3]	KAN C, DING G, WU Q, et al. Robust Relative Fingerprinting-Based Passive Source Localization via Data Cleansing[J]. IEEE Access, 2018, 6:19295-19269. doi: 10.1109/ACCESS.2018.2795803
[4]	马鑫迪, 马建峰, 高胜. 室内定位系统中指纹库的优化方法[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.
[5]	田洪亮, 钱志鸿, 梁潇, 等. 离散度WKNN位置指纹Wi-Fi定位算法[J]. 哈尔滨工业大学学报, 2017, 49(5):94-99.
	TIAN Hongliang, QIAN Zhihong, LIANG Xiao, et al. Discrete Degree WKNN Location Fingerprinting Algorithm Based on Wi-Fi[J]. Journal of Harbin Institute of Technology, 2017, 49(5):94-99.
[6]	胡久松, 刘宏立, 肖郭璇, 等. 应用于WiFi室内定位的自适应仿射传播聚类算法[J]. 电子与信息学报, 2018, 40(12):2889-2895.
	HU Jiusong, LIU Hongli, XIAO Guoxuan, et al. Adaptive Affine Propagation Clustering Algorithm Applied for WiFi Indoor Positioning[J]. Journal of Electronics and Information, 2018, 40(12):2889-2895.
[7]	吕娜, 单志龙, 张凡, 等. 基于接入点的泰森多边形指纹聚类定位算法[J]. 传感技术学报, 2017, 30(12):1941-1947.
	LV Na, SHAN Zhilong, ZHANG Fan, et al. Voronoi Based on Access Point Fingerprint Clustering Localization Algorithm[J]. Journal of Sensor Technology, 2017, 30(12):1941-1947.
[8]	薛卫星, 李清泉, 周宝定. 虚拟AP支持的室内非线性约束区域定位[J]. 测绘学报, 2021, 50(5):569-579.
	XUE Weixing, LI Qingquan, ZHOU Baoding. Virtual AP Based Indoor Localization in Area without Linear Constraints[J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(5):569-579.
[9]	KUSHKI A, PLATANIOTIS K, VENETSANOPOULOS A. Kernel-Based Positioning in Wireless Local Area Networks[J]. IEEE Transactions on Mobile Computing, 2007, 6(6):689-705. doi: 10.1109/TMC.2007.1017
[10]	YOUSSEF M A, AGRAWALA A, UDAYA SHANKAR A. WLAN Location Determination via Clustering and Probability Distributions[C/OL]. [2021-02-20]. https://ieeexplore.ieee.org/document/1192736.
[11]	CHEN Y, YANG Q, YIN J, et al. Power-Efficient Access-Point Selection for Indoor Location Estimation[J]. IEEE Transactions on Knowledge & Data Engineering, 2006, 18(7):877-888.
[12]	MA L, TAN X Z, GUO S Z, et al. A Novel Algorithm Based on Clustering and Access Points Selection for Indoor Fingerprint Localization[C/OL]. [2021-02-20]. https://chem.ckcest.cn/Proceeding/Details?id=302133.
[13]	杨锦朋, 常俊, 余江, 等. 免校准的跨异构设备的室内定位方法[J]. 计算机工程与应用, 2020, 56(2):248-254.
	YANG Jingpeng, CHANG Jun, YU Jiang, et al. Calibration-Free Indoor Location Method for Across Heterogeneous Devices[J]. Computer Engineering and Applications, 2020, 56(2):248-254.
[14]	WELCH B L. The Significance of the Difference Between Two Means When the Population Variances Are Unequal[J]. Biometrika, 1938, 29(3):350-362. doi: 10.1093/biomet/29.3-4.350
[15]	ZHOU M, LI Y, MUHAMMAD J, et al. Integrated Statistical Test of Signal Distributions and Access Point Contributions for Wi-Fi Indoor Localization[J]. IEEE Transactions on Vehicular Technology, 2021, 70(5):5057-5070. doi: 10.1109/TVT.2021.3076269
[16]	YU L, LIU H. Efficient Feature Selection via Analysis of Relevance and Redundancy[J]. The Journal of Machine Learning Research, 2004, 5:1205-1224.
[17]	李静星, 杨有龙. 针对高维数据的马尔科夫毯特征选择[J]. 计算机工程与应用, 2021, 57(6):58-66.
	LI Jingxing, YANG Youlong. Feature Selection of Markov Blanket for High Dimensional Data[J]. Computer Engineering and Applications, 2021, 57(6):58-66.
[18]	TAO Y, ZHAO L. Fingerprint Localization with Adaptive Area Search[J]. IEEE Communications Letters, 2020, 24(7):1446-1450. doi: 10.1109/LCOMM.2020.2985706

子区域	P	γ	ρ/m	E_AP
Ω₂	9	0.00	0.62	P_A1,P_A3,P_A4,P_A31等8个接入点
Ω₄	25	0.22	0.90	P_A2,P_A3,P_A20,P_A31等13个接入点
Ω₆	15	0.23	0.77	P_A5,P_A6,P_A26,P_A36等14个接入点
Ω₁₂	15	0.00	0.75	P_A9,P_A10,P_A14,P_A25等15个接入点

有无接入点修正	平均值/m	最小值/m	最大值/m	方差值	1 m以内误差占比/%
有修正	0.977	0.095	3.765	0.499	63.2
无修正	0.995	0.150	3.764	0.498	61.9

定位检验	数据量	平均值/m	最小值/m	最大值/m	误差方差
有	357	0.943	0.095	3.343	0.461
无	370	0.977	0.095	3.765	0.500

定位算法	平均值 /m	最小值 /m	最大值 /m	误差方差
SAFC	0.977	0.095	3.765	0.500
AAS	1.303	0.130	8.082	1.445
WKNN	1.162	0.003	5.760	0.756
DDWKNN	1.292	0.004	10.927	1.306