计算机应用 ›› 2017, Vol. 37 ›› Issue (6): 1550-1554.DOI: 10.11772/j.issn.1001-9081.2017.06.1550

• 网络与通信 • 上一篇    下一篇

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

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

  1. 1. 东北大学 计算机科学与工程学院, 沈阳 110819;
    2. 东软公司 软件架构新技术国家重点实验室, 沈阳 110179
  • 收稿日期:2016-10-26 修回日期:2017-01-14 出版日期:2017-06-10 发布日期:2017-06-14
  • 通讯作者: 闻英友
  • 作者简介:张明洋(1989-),男,辽宁辽阳人,博士研究生,主要研究方向:无线网络、无线传感器网络、定位技术;陈剑(1980-),男,湖南邵阳人,副教授,博士,主要研究方向:无线传感器网络、定位技术、网络管理;闻英友(1974-),男,辽宁沈阳人,副教授,博士,主要研究方向:移动通信、网络安全;赵宏(1954-),男,河北河间人,教授,博士,主要研究方向:分布式多媒体信息处理、计算机网络、图像处理;王玉刚(1989-),男,山东德州人,硕士研究生,主要研究方向:无线定位技术。
  • 基金资助:
    国家863计划项目(2015AA016005);国家自然科学基金资助项目(61402096,61173153,61300196)。

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

ZHANG Mingyang1,2, CHEN Jian1,2, WEN Yingyou1,2, ZHAO Hong1,2, WANG Yugang1,2   

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

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

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)

中图分类号: