基于区域分割的快速KNN定位算法
|
摘要
针对位置指纹定位算法指纹匹配效率低、定位实时性差等问题,基于传统的K最近邻思想提出一种区域分割的方法。该算法在指纹匹配阶段根据区域分割的思想,逐步缩小对目标点的定位区域范围,选取该范围内所有的参考点作为待匹配的指纹,利用KNN算法进行最终的位置估计,实现目标的快速定位。这样的过程大幅度减小了KNN算法的指纹匹配功耗,使其能应用在较大的指纹数据库中。仿真实验结果表明,该算法在保证定位精度的情况下,定位的速度明显快于传统的KNN定位算法。
Aiming at the problems in location fingerprint algorithm such as the low fingerprint matching efficiency and poor real-time positioning,the paper proposes a method of region segmentation based on the traditional K-nearest neighbor algorithm. According to the idea of region segmentation,the proposed algorithm gradually narrowed the positioning space and selected all the reference points within the range as the fingerprint to be matched in order to achieve rapid positioning of the target. This process reduces the KNN algorithm fingerprint matching power consumption,which can make the proposed algorithm be applied to big data. The experimental results show that the accuracy of the proposed algorithm is similarity than the traditional KNN,but positioning speed has been significantly improved.
Aiming at the problems in location fingerprint algorithm such as the low fingerprint matching efficiency and poor real-time positioning,the paper proposes a method of region segmentation based on the traditional K-nearest neighbor algorithm. According to the idea of region segmentation,the proposed algorithm gradually narrowed the positioning space and selected all the reference points within the range as the fingerprint to be matched in order to achieve rapid positioning of the target. This process reduces the KNN algorithm fingerprint matching power consumption,which can make the proposed algorithm be applied to big data. The experimental results show that the accuracy of the proposed algorithm is similarity than the traditional KNN,but positioning speed has been significantly improved.
引文
[1]吴冲,苏兵,焦筱悛,等.基于改进动态RSSI算法的Wi Fi室内定位研究[J].常州大学学报(自然科学版),2014,26(1):32-36.
[2]SUN G,CHEN J,GUO W,et al. Signal processing techniques in network-aided positioning:a survey of state-of-the-art positioning design[J]. IEEE Signal Processing Magazine,2005,22(4):12-23.
[3]SELMI A Vervisch-Picois,SAMAMA N. Design of new codes for reducing interference between-like signals transmitted indoors[C]//Indoor Positioning and Indoor Navigation(IPIN),2013 International Conference on. Montbeliard-Belfort,2013:1-9.
[4] LI B,WANG Y,LEE H K,et al. Method for yielding a database of location fingerprints in WLAN[J].IEE Proceedings-Communications,2005,152(5):580-586.
[5]XIA M,CHEN J,SONG C,et al. The indoor positioning algorithm research based on improved location fingerprinting[C]//Control and Decision Conference. IEEE,2015.
[6] MILIORIS D,TZAGKARAKIS G,PAPAKONSTANTINOU A,et al. Low-dimensional signal-strength fingerprint-based positioning in wireless LANs[J]. Ad Hoc Networks,2012,12(1):100-114. doi:10.1016/j.adhoc.2011.12.006.
[7]FENG C. Received-signal-strength-based indoor positioning using compressive sensing[J].IEEE Transaction on Mobile Computing,2012,COM-11(12):1983-1993. 278-283.
[8]冯辰.基于压缩感知的室内定位系统的研究与实现[D].北京:北京交通大学,2010.
[9]刘洺辛,孙建利.基于能效的WLAN室内定位系统模型设计与实现[J].仪器仪表学报,2014,35(5):1169-1178.
[10]TAMURA K,PETERSON D,PETERSON N,et al. MEGA5:molecular evolutionary genetics analysis using maximum likelihood,evolutionary distance,and maximum parsimony methods[J]. Molecular Biology and Evolution,2011,28(10):2731-2739.
[11]FRANCE S L,CARROLL J D,XIONG H. Distance metrics for high dimensional nearest neighborhood recovery:compression and normalization[J]. Information Sciences,2012,184(1):92-110.
[2]SUN G,CHEN J,GUO W,et al. Signal processing techniques in network-aided positioning:a survey of state-of-the-art positioning design[J]. IEEE Signal Processing Magazine,2005,22(4):12-23.
[3]SELMI A Vervisch-Picois,SAMAMA N. Design of new codes for reducing interference between-like signals transmitted indoors[C]//Indoor Positioning and Indoor Navigation(IPIN),2013 International Conference on. Montbeliard-Belfort,2013:1-9.
[4] LI B,WANG Y,LEE H K,et al. Method for yielding a database of location fingerprints in WLAN[J].IEE Proceedings-Communications,2005,152(5):580-586.
[5]XIA M,CHEN J,SONG C,et al. The indoor positioning algorithm research based on improved location fingerprinting[C]//Control and Decision Conference. IEEE,2015.
[6] MILIORIS D,TZAGKARAKIS G,PAPAKONSTANTINOU A,et al. Low-dimensional signal-strength fingerprint-based positioning in wireless LANs[J]. Ad Hoc Networks,2012,12(1):100-114. doi:10.1016/j.adhoc.2011.12.006.
[7]FENG C. Received-signal-strength-based indoor positioning using compressive sensing[J].IEEE Transaction on Mobile Computing,2012,COM-11(12):1983-1993. 278-283.
[8]冯辰.基于压缩感知的室内定位系统的研究与实现[D].北京:北京交通大学,2010.
[9]刘洺辛,孙建利.基于能效的WLAN室内定位系统模型设计与实现[J].仪器仪表学报,2014,35(5):1169-1178.
[10]TAMURA K,PETERSON D,PETERSON N,et al. MEGA5:molecular evolutionary genetics analysis using maximum likelihood,evolutionary distance,and maximum parsimony methods[J]. Molecular Biology and Evolution,2011,28(10):2731-2739.
[11]FRANCE S L,CARROLL J D,XIONG H. Distance metrics for high dimensional nearest neighborhood recovery:compression and normalization[J]. Information Sciences,2012,184(1):92-110.