一种层次Levenshtein距离的无指纹校准的室内定位方法

An fingerprint calibrations-free indoor localization method based on hierarchical Levenshtein distance

随着移动计算领域的兴起,基于位置的服务越来越受青睐。目前各种室内定位的方法层出不穷,由于室内广泛部署了无线基础设施,基于WiFi指纹信息的室内定位技术是其主流方法。设备异构和室内环境变化是影响定位精度的主要因素。本文针对以上两个问题,提出一种层次Levenshtein距离(HLD)的WiFi指纹距离计算算法,实现异构设备的指纹无校准比对。将不同移动设备采集的RSSI信息转化为AP序列,根据AP对应的RSSI值的差异性计算其层次能级,结合Levenshtein距离计算WiFi指纹之间的距离。对于需定位的WiFi指纹RSSI信息,利用HLD算法获取K个近邻,采用WKNN算法进行预测定位。实验中,为了验证算法的鲁棒性和有效性,在3种不同类型的室内环境中采用5种不同的移动设备来采集WiFi的RSSI信息,其定位的平均精度达1.5 m。

In the era of mobile computing,location-based services have become extremely important for a wide range of applications,and various wireless indoor localization techniques have been emerging. Amongst these techniques,WiFi fingerprint-based indoor localization is one of the most attractive because of the wide deployment and availability of WiFi infrastructure. The accuracy of indoor localization is affected by two main factors:equipment heterogeneity and environmental dynamics. To solve the obove two problems,an algorithm based on hierarchical Levenshtein distance( HLD) was proposed to realize calibration-free fingerprint comparison of heterogeneous devices. Received signal strength indication( RSSI) information collected via different mobile devices was transformed into an AP sequence. The difference in the Received signal strength indication RSSI values was used to calculate the hierarchical energy level of each access point( AP). Next,the distance between the WiFi fingerprints was calculated using the Levenshtein distance. To locate WiFi fingerprint RSSI information,the HLD algorithm was used to obtain K neighbors and the weighted K nearest neighbor(WKNN) algorithm was used to predict its position. Five different mobile devices were used to collect WiFi RSSI information in three different types of indoor environments to verify the robustness and effectiveness of the algorithm. The average localization accuracy was 1.5 m.