Fingerprint matching indoor localization algorithm based on dynamic time warping distance for Wi-Fi network

doi:10.11772/j.issn.1001-9081.2017.06.1550

Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (6): 1550-1554.DOI: 10.11772/j.issn.1001-9081.2017.06.1550

Previous Articles Next Articles

Fingerprint matching indoor localization algorithm based on dynamic time warping distance for Wi-Fi network

ZHANG Mingyang^1,2, CHEN Jian^1,2, WEN Yingyou^1,2, ZHAO Hong^1,2, WANG Yugang^1,2

1. School of Computer Science and Engineering, Northeastern University, Shenyang Liaoning 110819, China;
2. State Key Laboratory of Software Architecture, Neusoft Corporation, Shenyang Liaoning 110179, China

Received:2016-10-26 Revised:2017-01-14 Online:2017-06-10 Published:2017-06-14
Supported by:
This work is partially supported by the National High Technology Research and Development Program (863 Program) of China (2015AA016005), the National Natural Science Foundation of China (61402096, 61173153, 61300196).

基于动态时间规整距离指纹匹配的Wi-Fi网络室内定位算法

张明洋^1,2, 陈剑^1,2, 闻英友^1,2, 赵宏^1,2, 王玉刚^1,2

1. 东北大学计算机科学与工程学院, 沈阳 110819;
2. 东软公司软件架构新技术国家重点实验室, 沈阳 110179

通讯作者: 闻英友
作者简介:张明洋(1989-),男,辽宁辽阳人,博士研究生,主要研究方向:无线网络、无线传感器网络、定位技术;陈剑(1980-),男,湖南邵阳人,副教授,博士,主要研究方向:无线传感器网络、定位技术、网络管理;闻英友(1974-),男,辽宁沈阳人,副教授,博士,主要研究方向:移动通信、网络安全;赵宏(1954-),男,河北河间人,教授,博士,主要研究方向:分布式多媒体信息处理、计算机网络、图像处理;王玉刚(1989-),男,山东德州人,硕士研究生,主要研究方向:无线定位技术。
基金资助:
国家863计划项目（2015AA016005）；国家自然科学基金资助项目（61402096，61173153，61300196）。

Abstract

Abstract: 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.

Key words: Wi-Fi network, indoor localization, time series, fingerprint matching, Dynamic Time Warping (DTW)

摘要： Wi-Fi网络中常规的基于指纹匹配室内定位算法面临信号时变现象或人为干扰的影响，导致定位精度不高。为此，提出基于动态时间规整（DTW）距离相似性指纹匹配的Wi-Fi网络室内定位算法。首先，该算法将定位区域的Wi-Fi信号特征按照采样的先后顺序转化为时间序列类型指纹，通过计算Wi-Fi信号指纹动态时间规整距离的大小来获取定位点与样本点的相似性；然后，根据采样区域结构特征，将Wi-Fi信号指纹采集问题划分为三类基本的动态路径采样方式；最后，结合多种动态路径采样方式增加指纹特征信息的准确性和完整性，从而提高指纹匹配的准确性和定位精度。大量实验结果表明，较瞬时指纹匹配定位算法，所提算法误差范围在3m以内定位的累积错误率：路径区域匀速运动提高了10%，变速运动提高了13%；开放区域交叉曲线运动提高了9%，S型曲线运动提高了3%。所提算法在实际室内定位应用中能有效提高指纹匹配的准确性和定位精度。

关键词: Wi-Fi网络, 室内定位, 时间序列, 指纹匹配, 动态时间规整

CLC Number:

TP393.17

ZHANG Mingyang, CHEN Jian, WEN Yingyou, ZHAO Hong, WANG Yugang. Fingerprint matching indoor localization algorithm based on dynamic time warping distance for Wi-Fi network[J]. Journal of Computer Applications, 2017, 37(6): 1550-1554.

张明洋, 陈剑, 闻英友, 赵宏, 王玉刚. 基于动态时间规整距离指纹匹配的Wi-Fi网络室内定位算法[J]. 计算机应用, 2017, 37(6): 1550-1554.

References

[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] 田增山,代海鹏. 基于曲面拟合的WiFi指纹数据库更新[J].计算机应用,2016,36(5):1192-1195.(TIAN Z S, DAI H P. WiFi 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 NLOS propagation 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]. ACM Transactions on Sensor Networks, 2006, 2(2):221-262.
[11] TOMIC S, BEKO M, DINIS R. Distributed RSS-AoA based localization with unknown transmit powers[J]. IEEE Wireless Communications Letters, 2016, 5(4):392-395.
[12] JAMALABDOLLAHI M, ZEKAVAT S. ToA 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, LI F 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, LUO H 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] 周瑞,李志强,罗磊.基于粒子滤波的WiFi行人航位推算融合室内定位[J].计算机应用,2016,36(5):1188-1191,1200.(ZHOU R, LI Z Q, LUO L. WiFi-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.

Fingerprint matching indoor localization algorithm based on dynamic time warping distance for Wi-Fi network

基于动态时间规整距离指纹匹配的Wi-Fi网络室内定位算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	LI Yangying, CHEN Zhijun, ZHANG Zihao, YOU Lan. Raw sugar demand forecasting model for sugar manufacturing enterprise based on modified Elman neural network [J]. Journal of Computer Applications, 2021, 41(7): 2113-2120.
[2]	LUAN Jianing, ZHANG Wei, SUN Wei, ZHANG Ao, HAN Dong. High-accuracy localization algorithm based on fusion of two-dimensional code vision and laser lidar [J]. Journal of Computer Applications, 2021, 41(5): 1484-1491.
[3]	LI Guorong, YE Jimin, ZHEN Yuanting. Time series clustering based on new robust similarity measure [J]. Journal of Computer Applications, 2021, 41(5): 1343-1347.
[4]	SHEN Chen, TAI Lingxiang, PENG Yuwei. Dynamic workload matching method for automatic parameter tuning [J]. Journal of Computer Applications, 2021, 41(3): 657-661.
[5]	CAO Yang, YAN Qiuyan, WU Xin. Ensemble classification algorithm for imbalanced time series [J]. Journal of Computer Applications, 2021, 41(3): 651-656.
[6]	ZHANG Lingzhe, HUANG Xiangdong, QIAO Jialin, GOU Wangminhao, WANG Jianmin. Two-stage file compaction framework by log-structured merge-tree for time series data [J]. Journal of Computer Applications, 2021, 41(3): 618-622.
[7]	ZHANG Xiaohan, FENG Aimin. Short-term traffic flow prediction based on empirical mode decomposition and long short-term memory neural network [J]. Journal of Computer Applications, 2021, 41(1): 225-230.
[8]	QIAN Bin, ZHENG Kaihong, CHEN Zipeng, XIAO Yong, LI Sen, YE Chunzhuang, MA Qianli. Time series imputation model based on long-short term memory network with residual connection [J]. Journal of Computer Applications, 2021, 41(1): 243-248.
[9]	XIAO Yong, ZHENG Kaihong, ZHENG Zhenjing, QIAN Bin, LI Sen, MA Qianli. Multi-scale skip deep long short-term memory network for short-term multivariate load forecasting [J]. Journal of Computer Applications, 2021, 41(1): 231-236.
[10]	GAO Shile, WANG Ying, LI Hailin, WAN Xiaoji. Prediction method on financial time series data based on matrix profile [J]. Journal of Computer Applications, 2021, 41(1): 199-207.
[11]	MA Tingting, JI Tianjiao, YANG Guanyu, CHEN Yang, XU Wenbo, LIU Hongtu. Incidence trend prediction of hand-foot-mouth disease based on long short-term memory neural network [J]. Journal of Computer Applications, 2021, 41(1): 265-269.
[12]	GUO Xiuting, ZHU Changsheng, ZHANG Shengcai, ZHAO Kuipeng. Application of fractal interpolation in wind speed time series [J]. Journal of Computer Applications, 2020, 40(9): 2628-2633.
[13]	XIA Lunteng, ZHANG Li. Networked cane system for blind people based on K-nearest neighbor and dynamic time warping algorithms [J]. Journal of Computer Applications, 2020, 40(8): 2441-2448.
[14]	HU Min, BAI Xue, XU Wei, WU Bingjian. Review of anomaly detection algorithms for multidimensional time series [J]. Journal of Computer Applications, 2020, 40(6): 1553-1564.
[15]	HUO Weigang, WANG Huifang. Time series anomaly detection method based on autoencoder and HMM [J]. Journal of Computer Applications, 2020, 40(5): 1329-1334.