基于动态时间规整距离指纹匹配的Wi-Fi网络室内定位算法
|
摘要
Wi-Fi网络中常规的基于指纹匹配室内定位算法面临信号时变现象或人为干扰的影响,导致定位精度不高。为此,提出基于动态时间规整(DTW)距离相似性指纹匹配的Wi-Fi网络室内定位算法。首先,该算法将定位区域的Wi-Fi信号特征按照采样的先后顺序转化为时间序列类型指纹,通过计算Wi-Fi信号指纹动态时间规整距离的大小来获取定位点与样本点的相似性;然后,根据采样区域结构特征,将Wi-Fi信号指纹采集问题划分为三类基本的动态路径采样方式;最后,结合多种动态路径采样方式增加指纹特征信息的准确性和完整性,从而提高指纹匹配的准确性和定位精度。大量实验结果表明,较瞬时指纹匹配定位算法,所提算法误差范围在3m以内定位的累积错误率:路径区域匀速运动提高了10%,变速运动提高了13%;开放区域交叉曲线运动提高了9%,S型曲线运动提高了3%。所提算法在实际室内定位应用中能有效提高指纹匹配的准确性和定位精度。
Focusing on the low accuracy problem of regular fingerprint matching indoor localization algorithm for Wi-Fi network confronted with signal fluctuation or jamming,the fingerprint matching indoor localization algorithm based on Dynamic Time Warping( DTW) similarity for Wi-Fi network was proposed. Firstly,the Wi-Fi signal characteristics in localization area were converted to the time-series fingerprints according to the sequence of sampling. The similarity between the locating data and sampling data was obtained by computing the fingerprint DTW distance of Wi-Fi signal. Then,according to the structural characteristics of the sampling area,the fingerprint sampling problem of Wi-Fi signal was divided into three kinds of basic sampling methods based on dynamic path. Finally,the accuracy and completeness of the fingerprint feature information were increased by the combination of multiple dynamic path sampling methods,which improved the accuracy and location precision of fingerprint matching. The extensive experimental results show that,compared with the instantaneous fingerprint matching indoor localization algorithm,within the location error of 3 m,the cumulative error frequency of the proposed localization algorithm,was 10% higher for uniform motion and 13% higher for variable motion within routing area,and 9% higher for crossed curvilinear motion and 3% higher for S-type curvilinear motion within open area. The proposed localization algorithm can improve accuracy and location precision of fingerprint matching effectively in real indoor localization applications.
Focusing on the low accuracy problem of regular fingerprint matching indoor localization algorithm for Wi-Fi network confronted with signal fluctuation or jamming,the fingerprint matching indoor localization algorithm based on Dynamic Time Warping( DTW) similarity for Wi-Fi network was proposed. Firstly,the Wi-Fi signal characteristics in localization area were converted to the time-series fingerprints according to the sequence of sampling. The similarity between the locating data and sampling data was obtained by computing the fingerprint DTW distance of Wi-Fi signal. Then,according to the structural characteristics of the sampling area,the fingerprint sampling problem of Wi-Fi signal was divided into three kinds of basic sampling methods based on dynamic path. Finally,the accuracy and completeness of the fingerprint feature information were increased by the combination of multiple dynamic path sampling methods,which improved the accuracy and location precision of fingerprint matching. The extensive experimental results show that,compared with the instantaneous fingerprint matching indoor localization algorithm,within the location error of 3 m,the cumulative error frequency of the proposed localization algorithm,was 10% higher for uniform motion and 13% higher for variable motion within routing area,and 9% higher for crossed curvilinear motion and 3% higher for S-type curvilinear motion within open area. The proposed localization algorithm can improve accuracy and location precision of fingerprint matching effectively in real indoor localization applications.
引文
[1]孙利民.无线传感器网络[M].北京:清华大学出版社,2005:135-156.(SUN L M.Wireless Sensor Networks[M].Beijing:Tsinghua University Press,2005:135-156.)
[2]WEN Y Y,GAO R,ZHAO H.Energy efficient moving target tracking in wireless sensor networks[J].Sensors,2016,16(1):Article No.29.
[3]田增山,代海鹏.基于曲面拟合的Wi Fi指纹数据库更新[J].计算机应用,2016,36(5):1192-1195.(TIAN Z S,DAI H P.Wi Fi fingerprint database updating based on surface fitting[J].Journal of Computer Applications,2016,36(5):1192-1195.)
[4]MAJEED K,SOROUR S,AL-NAFFOURI T Y,et al.Indoor localization and radio map estimation using unsupervised manifold alignment with geometry perturbation[J].IEEE Transactions on Mobile Computing,2016,15(11):2794-2808.
[5]YANG H,ZHANG R,BORDOY J,et al.Smartphone-based indoor localization system using inertial sensor and acoustic transmitter/receiver[J].IEEE Sensors Journal,2016,16(22):8051-8061.
[6]TSALOLIKHIN E,BILIK I,BLAUNSTEIN N.A single-base-station localization approach using a statistical model of the NLOSpropagation conditions in urban terrain[J].IEEE Transactions on Vehicular Technology.2011,60(3):1124-1137.
[7]SCHLOEMANN J,DHILLON H S,BUEHRER R M.A tractable metric for evaluating base station geometries in cellular network localization[J].IEEE Wireless Communications Letters,2016,5(2):140-143.
[8]JIANG Q D,MA Y T,LIU K H,et al.A probabilistic radio map construction scheme for crowdsourcing-based fingerprinting localization[J].IEEE Sensors Journal,2016,16(10):3764-3774.
[9]XU X L,TANG Y,WANG X H,et al.Variance-based fingerprint distance adjustment algorithm for indoor localization[J].Journal of Systems Engineering and Electronics,2015,26(6):1191-1201.
[10]ZHOU G,HE T,KRISHNAMURTHY S,et al.Models and solutions for radio irregularity in wireless sensor networks[J].ACMTransactions on Sensor Networks,2006,2(2):221-262.
[11]TOMIC S,BEKO M,DINIS R.Distributed RSS-Ao A based localization with unknown transmit powers[J].IEEE Wireless Communications Letters,2016,5(4):392-395.
[12]JAMALABDOLLAHI M,ZEKAVAT S.To A ranging and layer thickness computation in nonhomogeneous media[J].IEEE Transactions on Geoscience and Remote Sensing,2017,55(2):742-752.
[13]李石荣,李飞腾.基于RSSI概率统计分布的室内定位方法[J].计算机工程与应用,2016,52(11):119-124.(LI S R,LIF T.Method for indoor positioning based on RSSI statistical probability distribution[J].Computer Engineering and Applications,2016,52(11):119-124.)
[14]赵方,罗海勇,马严,等.基于公共信标集的高精度射频指纹定位算法[J].计算机研究与发展,2012,49(2):243-252.(ZHAO F,LUOH Y,MA Y,et al.An accurate fingerprinting localization algorithm based on common beacons[J].Journal of Computer Research and Development,2012,49(2):243-252.)
[15]张明洋,陈剑,闻英友,等.基于滑动窗口最长公共子序列Wi-Fi指纹定位算法[J].东北大学学报(自然科学版),2014,35(10):1390-1394.(ZHANG M Y,CHEN J,WEN Y Y,et al.Wi-Fi fingerprint localization algorithm based on sliding window combined with longest common subsequence[J].Journal of Northeastern University(Natural Science),2014,35(10):1390-1394.)
[16]YIU S,YANG K.Gaussian process assisted fingerprinting localization[J].IEEE Internet of Things Journal,2016,3(5):683-690.
[17]ROMANIUK S,AMBROZIAK L,GOSIEWSKI Z,et al.Real time localization system with extended Kalman filter for indoor applications[C]//Proceedings of the 2016 21st International Conference on Methods and Models in Automation and Robotics.Piscataway,NJ:IEEE,2016:42-47.
[18]周瑞,李志强,罗磊.基于粒子滤波的Wi Fi行人航位推算融合室内定位[J].计算机应用,2016,36(5):1188-1191,1200.(ZHOU R,LI Z Q,LUO L.Wi Fi-pedestrian dead reckoning fused indoor positioning based on particle filtering[J].Journal of Computer Applications,2016,36(5):1188-1191,1200.)
[19]王少鹏,闻英友,李志,等.一种关于数据流区间Disjoint查询的快速处理算法[J].计算机研究与发展,2014,51(5):1136-1148.(WANG S P,WEN Y Y,LI Z,et al.A fast processing algorithm on section disjoint query of data stream[J].Journal of Computer Research and Development,2014,51(5):1136-1148.)
[20]ESLING P,AGON C.Time-series data mining[J].ACM Computing Surveys,2012,45(1):Article No.12.
[21]LE-KHAC N A,BUE M,WHELAN M,et al.A clustering-based data reduction for very large spatio-temporal datasets[C]//ADMA'10:Proceedings of the 6th International Conference on Advanced Data Mining and Applications,LNCS 6441.Berlin:Springer,2010:43-54.
[22]TOYODA M,SAKURAI Y,ISHIKAWA Y.Pattern discovery in data streams under the time warping distance[J].The VLDB Journal,2013,22(3):295-318.
[2]WEN Y Y,GAO R,ZHAO H.Energy efficient moving target tracking in wireless sensor networks[J].Sensors,2016,16(1):Article No.29.
[3]田增山,代海鹏.基于曲面拟合的Wi Fi指纹数据库更新[J].计算机应用,2016,36(5):1192-1195.(TIAN Z S,DAI H P.Wi Fi fingerprint database updating based on surface fitting[J].Journal of Computer Applications,2016,36(5):1192-1195.)
[4]MAJEED K,SOROUR S,AL-NAFFOURI T Y,et al.Indoor localization and radio map estimation using unsupervised manifold alignment with geometry perturbation[J].IEEE Transactions on Mobile Computing,2016,15(11):2794-2808.
[5]YANG H,ZHANG R,BORDOY J,et al.Smartphone-based indoor localization system using inertial sensor and acoustic transmitter/receiver[J].IEEE Sensors Journal,2016,16(22):8051-8061.
[6]TSALOLIKHIN E,BILIK I,BLAUNSTEIN N.A single-base-station localization approach using a statistical model of the NLOSpropagation conditions in urban terrain[J].IEEE Transactions on Vehicular Technology.2011,60(3):1124-1137.
[7]SCHLOEMANN J,DHILLON H S,BUEHRER R M.A tractable metric for evaluating base station geometries in cellular network localization[J].IEEE Wireless Communications Letters,2016,5(2):140-143.
[8]JIANG Q D,MA Y T,LIU K H,et al.A probabilistic radio map construction scheme for crowdsourcing-based fingerprinting localization[J].IEEE Sensors Journal,2016,16(10):3764-3774.
[9]XU X L,TANG Y,WANG X H,et al.Variance-based fingerprint distance adjustment algorithm for indoor localization[J].Journal of Systems Engineering and Electronics,2015,26(6):1191-1201.
[10]ZHOU G,HE T,KRISHNAMURTHY S,et al.Models and solutions for radio irregularity in wireless sensor networks[J].ACMTransactions on Sensor Networks,2006,2(2):221-262.
[11]TOMIC S,BEKO M,DINIS R.Distributed RSS-Ao A based localization with unknown transmit powers[J].IEEE Wireless Communications Letters,2016,5(4):392-395.
[12]JAMALABDOLLAHI M,ZEKAVAT S.To A ranging and layer thickness computation in nonhomogeneous media[J].IEEE Transactions on Geoscience and Remote Sensing,2017,55(2):742-752.
[13]李石荣,李飞腾.基于RSSI概率统计分布的室内定位方法[J].计算机工程与应用,2016,52(11):119-124.(LI S R,LIF T.Method for indoor positioning based on RSSI statistical probability distribution[J].Computer Engineering and Applications,2016,52(11):119-124.)
[14]赵方,罗海勇,马严,等.基于公共信标集的高精度射频指纹定位算法[J].计算机研究与发展,2012,49(2):243-252.(ZHAO F,LUOH Y,MA Y,et al.An accurate fingerprinting localization algorithm based on common beacons[J].Journal of Computer Research and Development,2012,49(2):243-252.)
[15]张明洋,陈剑,闻英友,等.基于滑动窗口最长公共子序列Wi-Fi指纹定位算法[J].东北大学学报(自然科学版),2014,35(10):1390-1394.(ZHANG M Y,CHEN J,WEN Y Y,et al.Wi-Fi fingerprint localization algorithm based on sliding window combined with longest common subsequence[J].Journal of Northeastern University(Natural Science),2014,35(10):1390-1394.)
[16]YIU S,YANG K.Gaussian process assisted fingerprinting localization[J].IEEE Internet of Things Journal,2016,3(5):683-690.
[17]ROMANIUK S,AMBROZIAK L,GOSIEWSKI Z,et al.Real time localization system with extended Kalman filter for indoor applications[C]//Proceedings of the 2016 21st International Conference on Methods and Models in Automation and Robotics.Piscataway,NJ:IEEE,2016:42-47.
[18]周瑞,李志强,罗磊.基于粒子滤波的Wi Fi行人航位推算融合室内定位[J].计算机应用,2016,36(5):1188-1191,1200.(ZHOU R,LI Z Q,LUO L.Wi Fi-pedestrian dead reckoning fused indoor positioning based on particle filtering[J].Journal of Computer Applications,2016,36(5):1188-1191,1200.)
[19]王少鹏,闻英友,李志,等.一种关于数据流区间Disjoint查询的快速处理算法[J].计算机研究与发展,2014,51(5):1136-1148.(WANG S P,WEN Y Y,LI Z,et al.A fast processing algorithm on section disjoint query of data stream[J].Journal of Computer Research and Development,2014,51(5):1136-1148.)
[20]ESLING P,AGON C.Time-series data mining[J].ACM Computing Surveys,2012,45(1):Article No.12.
[21]LE-KHAC N A,BUE M,WHELAN M,et al.A clustering-based data reduction for very large spatio-temporal datasets[C]//ADMA'10:Proceedings of the 6th International Conference on Advanced Data Mining and Applications,LNCS 6441.Berlin:Springer,2010:43-54.
[22]TOYODA M,SAKURAI Y,ISHIKAWA Y.Pattern discovery in data streams under the time warping distance[J].The VLDB Journal,2013,22(3):295-318.