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

何富贵，杨铮，吴陈沭，赵姝，周先存

(1.皖西学院 电子与信息工程学院，安徽 六安 237012； 2. 清华大学 软件学院可信网络与系统研究所，北京 100084；3.安徽大学 智能计算与知识工程研究所，安徽 合肥 230039)

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

何富贵1，3，杨铮2，吴陈沭2，赵姝3，周先存1

(1.皖西学院 电子与信息工程学院，安徽 六安 237012； 2. 清华大学 软件学院可信网络与系统研究所，北京 100084；3.安徽大学 智能计算与知识工程研究所，安徽 合肥 230039)

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

室内定位；WiFi指纹；设备异构；无指纹校准；Levenshtein距离

中文引用格式：何富贵，杨铮，吴陈沭，等.一种层次Levenshtein距离的无指纹校准的室内定位方法[J]. 智能系统学报， 2017, 12(3): 422-429.

英文引用格式：HE Fugui，YANG Zheng，WU Chenshu, et al. An fingerprint calibrations-free indoor localization method based on hierarchical Levenshtein distance[J]. CAAI transactions on intelligent systems, 2017, 12(3): 422-429.

基于位置的服务，如路径导航、广告推荐和邻近社交网络等，随着智能手机的普及已变得尤为重要。在室内环境中GPS对卫星信号的接收较弱无法满足用户的需求，目前已有许多室内定位技术[1-3]涌现。随着IEEE802.11(WiFi)普及[4]，基于WiFi指纹室内定位技术已成为研究的热点。现有的WiFi指纹室内定位主流方案由两阶段组成：现场勘查和指纹匹配。

RADAR[5]在未考虑随机信号前提下对WiFi指纹利用欧氏距离和K近邻算法进行室内目标定位，Horus[6]在此基础上考虑RP信号概率分布进行定位估计。建立和更新指纹库是决定基于WiFi指纹定位精度高低的关键。通过专业人士来收集WiFi成本昂贵，基于众包模式[7]可明显降低指纹地图构建和维护成本，但会带来一些新的问题。

由于无线信号在传播过程存在多径效应，对环境的变化十分敏感，不同时间采集的数据都存在差异。环境动态对室内定位系统精度的影响是与生俱来的。对于设备异构的室内定位问题[8-9]，同一位置的异构设备检测到的RSSI值通常有不同的值，这严重降低了定位精度[10-11]。为了处理基于WiFi指纹识别的室内定位系统所遇到的设备异质性问题，已有不同的解决方案[8,10-15]。

由于用不同设备获取RSSI存在差异[10,16]，直接用WiFi信号强度进行预测定位无法达到在现场勘查和指纹匹配的过程中用相同的设备采集WiFi指纹的米级定位精度[5-6,17-18]。因此，仅依赖于绝对信号强度测量来实现异构设备的定位是不可行的，迫切需要开发一种替代绝对RSSI的鲁棒指纹定位技术。在文献[8,15]中提出了一些无校准方法，以避免每个测试设备使用繁琐的手动RSSI校准程序。协作映射通过训练在线测量的RSSI值来估计线性映射函数[15]。无监督的学习方法(如在线回归和期望最大化)已被用来学习映射函数[8]。 然而，以上无校准的指纹定位方法都需要耗时的在线处理过程。解决设备异构问题的另一种方式是定义和使用替代位置指纹，而不是绝对RSSI值。在文献[10]中提出信号强度差(SSD)，Yang[19]和Jiang[20]提出将RSSI测量向量转换为相对的RSS排序作为指纹，FreeLoc[19]使用Key-Value机制构造指纹。Jiang[20]提出使用长度为n

通过对WiFi指纹信息分析得知：1)对于同一位置，在容忍一定差异情况下，不同设备检测的AP的RSSI值形成的变化表现出很高的相似性；2)对于不同位置，在定位匹配过程中不同AP对其准确定位的贡献不同。不同AP在同一位置测量得到的RSSI值存在差异。其中一些AP对应的RSSI值较大，这些AP对定位的准确性影响较大。

为了实现无指纹校准的室内定位，考虑设备异构和环境动态的影响，本文提出基于层次Levenshtein距离的WiFi指纹距离计算算法。为了刻画同一位置不同设备检测的RSSI值的变化的相似性，将不同移动设备采集的RSSI信息按照从大到小进行降序排列索引，将绝对RSSI信息转化为相对的AP序列，以实现不同设备采集的数据量纲的一致性。同时，对于各数据采集点根据各AP对应的RSSI值的差异性计算其层次能级，将各个AP映射到不同层次能级上，以描述各AP对位置定位的影响等级。联合各AP层次能级，利用Levenshtein距离来计算AP序列间的距离，实现异构设备的指纹无校准比对。对于需定位的WiFi指纹RSSI信息，利用HLD算法获取K个近邻，采用WKNN算法进行预测定位。

1 问题描述

2 基于层次Levenshtein距离的距离算法

Levenshtein距离这个概念由Vladimir Levenshtein在1965年提出，通过最少编辑(修改、删除和插入)操作次数来计算字符串之间的相似度d(ai,bj)。

式中：ai，bj分别为长度为i，j字符串序列；ai，bj分别为ai，bj字符串中第i，j序号。

结论 在一定噪声范围内，接收信号强度之差小于ω，区域内AP序列顺序无差异。

证明 以实际环境中常用无线信号传输模型——Shadowing模型来论证。

不失一般性，现有接收端到发射机A和B距离分别为dA和dB,则有

对于同一区域的近邻位置，βA≈βB=β，将式(5)与式(6)相减，有

则有

由式(8)可知：在噪声存在的情况下，两接收信号强度差值大于阈值ω(其大小与环境噪声有关)时，才能区别dA和dB大小。故有两个接收信号强度之差小于ω，那么认为由这两个接收信号强度的排序得到的AP序列顺序无差异。证毕。

由于AP序列中各AP在WiFi指纹中的能级等级不同，删除和插入操作需要考虑AP的能级等级。由结论1可知，接收信号强度之差越小，AP序列SeqRPi顺序差异越小。修改操作距离通过修改前后两个AP的RSSI变化差异性来表现。对Levenshtein距离进行修正，得到基于Levenshtein距离的距离函数Dis(SeqRPi,SeqRPj)。

Dis(SeqRPi(m),SeqRPj(n))=

min(Dis(SeqRPi(m-1),SeqRPj(n))+α,

Dis(SeqRPi(m),SeqRPj(n-1))+β,

(9)

Dis(SeqRPi,SeqRPj)=min(Dis(SeqRPi(m-1),

SeqRPj(n))+α,Dis(SeqRPi(m),SeqRPj(n-1))+β,

(10)

(11)

3 性能评价

3.1 实验准备

我们在5种不同的安卓设备上测试算法性能，这5种设备分别为Huawei G9、Huawei M2、Samsung s6、Samsung note3、Nexus 5。分别对3种不同室内场景(实验室、图书馆和教室)进行实验。实验室的布局分布如图1(a)，总体布局为15 m×45 m；图书馆的布局分布如图1(b)，总体布局为78 m×95 m；教室的各层布局分布如图1(c)，平面总体布局为20 m×120 m，共3层。各实验场景的WiFi是事先已布置的，本次实验没有额外布置AP。考虑环境变化和不同实验操作者对采集信号的影响，5个志愿者在4个时间段(间隔一个星期、1个月和3个月)内手持上述5种不同的安卓设备各自独立在不同场景下采集WiFi的RSSI信息，并记录采集点的地理位置。各个采集点采集时间间隔不等，其跨度在10～25 s。为了客观评估定位性能，现场勘查的指纹数据库选择前3次采集的数据，对同一个位置的多条数据只随机保留一条记录，且保证各数据之间的地理位置距离大于等于1 m；定位测试数据选择第3、4次采集的数据。3个实验场景下4种不同时间的AP数量变化、指纹数据库和测试数据数量如表1所示。

表1 3个实验场景在4种不同时间的AP数量、指纹数据库和测试数据数量

Table 1 Number of AP in three experiment scenarios at four different times and number of fingerprint database, and test data

实验场景第1次AP数量第2次AP数量第3次AP数量第4次AP数量指纹数据库数量测试数据数量实验室1921192237050图书馆181718181450100教室262126246500300

(a)实验室

(b)图书馆

(c)教室图1 实验场景 Fig.1 Experiment building

3.2 实验结果

在实验中，本文提出的方法与3种经典室内定位方法进行对比。第一种方法是文献[5]提出的RADAR算法。因为不同设备获取的RSSI差异较大，无法用欧氏距离来计算各RP的相似度，在实验中将RADAR算法中欧氏距离替换为余弦距离计算各RP的相似度；第二种方法是文献[19]提出的FreeLoc算法，该算法的基本思想是通过Key-Value机制构造指纹来容忍诸如设备多样性和信号变化的环境动态；第三种方法是文献[23]提出的HED算法，该算法利用容错序列匹配策略来实现动态环境下WiFi指纹定位。采用平均定位误差和累计定位误差两种误差度量来对比4种室内定位方法的定位性能优越程度。

1)能量层级参数θ、近邻数目K选择

为了测试能量层级参数θ、近邻数目K对定位精度的影响，分别设定θ=3，4，4.5，5，5.5，6，7和K=2，3，4，5，6，对比在三种场景下的定位测试。对于不同场景，通过两个参数交叉验证。当θ=5时，算法达到最优。K=5时参数θ对预测定位的影响如图2所示。结合分析图3～5的累计定位误差和表2的平均定位误差:K=5时，在实验室和图书馆场景下，其算法达到最优；K=4时，在教室场景下，其算法达到最优。其原因是，实验室和图书馆场景是二维位置数据信息，教室的数据是立体地理位置。

表2 HLD算法在3种实验场景下不同K值情况的平均定位误差

Table 2 Average error of HLD algorithm under different K in three experiment scenarios m

图3 HLD算法在实验室环境下的不同K值的累计定位误差比较Fig.3 Cumulative localization error comparison of HLD algorithm under different K values in laboratory

图4 HLD算法在图书馆环境下的不同K值的累计定位误差比较Fig.4 Cumulative localization error comparison of HLD algorithm under different K values in library

图5 HLD算法在3层教室环境下的不同K值的累计定位误差比较Fig.5 Cumulative localization error comparison of HLD algorithm under differet K values in three floors classroom

2)与RADAR、FreeLoc和HED算法性能比较

在实验室和图书馆场景下，HED算法的K取值5；在教室场景下，HED算法的K取值4。RADAR算法中K值和HED算法相同。在3种实验场景下4种方法累计定位误差对比如图6～8所示，表3描述了3种实验场景下4种方法平均定位误差对比。RADAR对于平面环境下的定位误差在4～6 m，2 m内误差准确度在20%以下，基本达不到定位的效果；对三维环境下的定位效果更差。FreeLoc、HED对于平面环境下的定位误差在2～4 m，3 m内误差准确度在50%～60%，但在三维环境下的定位效果3 m内误差准确精度下降到40%左右。HLD算法整体的平均误差为1.5 m，2 m内误差准确度为70%～80%，对空间维度敏感度较低。

在定位过程中，与FreeLoc、HED算法执行效率进行比较，HLD算法时空复杂度比FreeLoc低40%，比HED空间复杂度高10%，时间复杂度相当。

图6 实验室环境下的4种方法累计定位误差比较Fig.6 Cumulative localization error comparison of four methods in laboratory

Tab 3 The average error comparison of four methods in three experiment scenarios m

图7 图书馆环境下的4种方法累计定位误差比较Fig.7 Cumulative localization error comparison of four methods in library

4 总结

本文讨论了设备异构和室内环境变化情形下的室内定位问题，提出了基于层次Levenshtein距离的WiFi指纹距离计算算法。在无校准情形下，将不同移动设备采集的RSSI信息转化为AP序列，以解决不同设备获取的RSSI信息的量纲一致性问题。根据AP对应的RSSI值的差异性计算其层次能级，结合Levenshtein距离计算WiFi指纹之间的距离，提供一种适应异构设备和动态环境下计算各RP间指纹距离的鲁棒性方法。对于需定位的WiFi指纹RSSI信息，采用WKNN算法进行预测定位。实验中，为了验证算法的鲁棒性和有效性，在3种不同类型的室内环境中用5种不同的移动设备来采集WiFi的RSSI信息，其定位的平均精度达1.5 m，2 m内误差准确度在70%～80%，对空间维度敏感度较低。

[1]GU Y, LO A, NIEMEGEERS I. A survey of indoor positioning systems for wireless personal networks[J]. IEEE commun. surveys and tutorials, 2009,11(1): 13-32.

[2]HARLE R. A survey of indoor inertial positioning systems for pedestrians[J]. IEEE commun. surveys & tutorials, 2013,15(3): 1281-1293.

[3]SUBBU K P. Analysis and status quo of smart-phone-based indoor localization systems[J]. IEEE wireless commun, 2014,21(4): 106-112.

[4]石柯,陈洪生,张仁同.一种基于支持向量回归的802.11无线室内定位方法[J].软件学报,2014,25(11): 2636-2651. SHI Ke, CHEN Hongsheng, ZHANG Rentong. Indoor location method based on support vector regression in 802.11 wireless environments[J]. Journal of software, 2014,25(11): 2636-2651.

[5]BAHL P, PADMANABHAN V. RADAR: an in-building rf-based user location and tracking system[C]//Proc. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Tel Aviv, Israel, 2000:775-784.

[6]YOUSSEF M, AGRAWALA A . The horus wlan location determination system[C]//Proceedings of the 3rdInternational Conferenceon Mobile Systems, Applications, and Services,Washington, USA, 2005: 205-218.

[7]WANG B, CHEN Q, YANG L T, et al. Indoor smartphone localization via fingerprint crowdsourcing: challenges and approaches[J]. IEEE wireless communication, 2016(6):82-89.

[8]TSUI A W, CHUANG Y H, CHU H H. Unsupervised learning for solving rss hardware variance problem in wifi localization[J].Mobile networks and applications, 2009,14(5): 677-691.

[9]CHENG H, WANG F, TAO R, et al. Clustering algorithms research for device-clustering localization[C]//2012 International Conference on Indoor Positioning and Indoor Navigation (IPIN),Sydney, Australia, 2012:1-7.

[10]MAHTAB HOSSAIN A , JIN Y ,SOH W S, et al. SSD: a robust RF location fingerprint addressing mobile devices heterogeneity[J]. IEEE transactions on mobile computing, 2013,12(1): 65-77.

[11]PARK J G, CURTIS D, TELLER S, et al. Implications of device diversity for organic localization[C]//The 30th IEEE International Conference on Computer Communications, Shanghai, China, 2011:3182-3190.

[12]FIGUERA C, ROJO-LVAREZ J L, MORA-JIMNEZ I, et al. Time-space sampling and mobile device calibration for wifi indoor location systems[J]. IEEE transactions on mobile computing, 2011,10(7):913-926.

[13]HAEBERLEN A, FLANNERY E, LADD A M, et al. Practical robust localization over large-scale 802.11 wireless networks[C]//Proceedings of the 10th Annual International Conference on Mobile Computing and Networking, Philadelphia, USA, 2004: 70-84.

[14]KJRGAARD M B. Indoor location fingerprinting with heterogeneous clients[J]. Pervasive and mobile computing, 2011, 7(1):31-43.

[15]DELLA ROSA F, LEPPAKOSKI H, BIANCULLO S, et al. Ad-hoc networks aiding indoor calibrations of heterogeneous devices for fingerprinting applications[C]//2010 International Conference on Indoor Positioning and Indoor Navigation (IPIN), Zurich, Switzerland, 2010: 1-6.[16]CHEN L H , WU E H K, JIN M H, et al. Homogeneous features utilization to address the device heterogeneity problem in fingerprint localization[J]. IEEE sensors journal, 2014,14(4): 998-1005.

[17]ZOU H , LU X , JIANG H,et al. A fast and precise indoor localization algorithm based on an online sequential extreme learning machine[J]. Sensors, 2015,15(1): 1804-1824.

[18]LYMBEROPOULOS D, LIU J, YANG X, et al. A realistic evaluation and comparison of indoor location technologies: experiences and lessons learned[C] //Proceedings of the 14th International Conference on Information Processing in Sensor Networks, Catania, Italy, ACM, 2015: 178-189.

[19]YANG S. Freeloc: calibration-free crowdsourced indoor localization[C]//The 32th IEEE International Conference on Computer Communications, Turin, Italy, 2013: 2481-2489.

[20]JIANG Y. Ariel: automatic wi-fi based room fingerprinting for indoor localization[C]//Proc ACM Conf. Ubiquitous Computing, Pittsburgh, Pennsylvania, United States, 2012:441-50.

[21]SHU Y, HUANG Y, ZHANG J, et al. Gradient-based fingerprinting for indoor localization and tracking[J]. IEEE transactions on industrial electronics, 2016,63(4):2424-2433.

[22]ZOU H, HUANG B, LU X, et al. Standardizing location fingerprints across heterogeneous mobile devices for indoor localization[C]//IEEE Wireless Communications and Networking Conference (WCNC 2016). Doha, Qatar, 2016:1-6.

[23]GU Y, CHEN M, REN F, et al. HED: handling environ-mental dynamics in indoor wifi fingerprint localization[C]//IEEE Wireless Communications and Networking Conference (WCNC 2016), Doha, Qatar, 2016: 5-10.

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

HE Fugui1,3， YANG Zheng2， WU Chenshu2， ZHAO Shu3， ZHOU Xiancun1

(1. School of Electronics and Information Engineering, West Anhui University, Lu’an 237012, China; 2. Institute of Trustworthy Network and System, School of Software, Tsinghua University, Beijing 100084, China; 3. Institute of Intelligent Computing and Knowledge Engineering, Anhui University, Hefei 230039, China)

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.

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 obtainKneighbors and the weightedKnearest 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.

indoor localization; WiFi fingerprint; heterogeneous device; fingerprint calibration-free; Levenshtein distance

10.11992/tis. 201704031

http://kns.cnki.net/kcms/detail/23.1538.TP.20170703.1854.014.html

2017-04-23. 网络出版日期：2017-07-03.

国家自然科学基金项目(61572366, 61303209, 61522110, 61402 006,61673020)；2016年安徽省高校优秀中青年骨干人才国内外访学研修重点项目(gxfxZD2016190)；安徽大学信息保障技术协同创新中心2015年度开放课题(ADXXBZ201504).

何富贵. E-mail：fuguihe@163.com.

TP181

A

1673-4785(2017)03-0422-08

何富贵，男，1982年生，副教授，主要研究方向为移动计算、室内定位和粒计算。发表学术论文10余篇。

杨铮，男，1983年生，副教授，博士生导师，研究方向为无线网络与移动计算，包括传感网、Mesh网络、室内定位、群智感知等。发表论文60余篇，其中CCF推荐A类论文40余篇；出版中、英文学术专著各1部。获得国家自然科学奖二等奖。

吴陈沭，男，1989年生，博士，研究方向为无线网络与移动计算，包括室内定位、群智感知等。