«上一篇
文章快速检索     高级检索
下一篇»
  智能系统学报  2017, Vol. 12 Issue (3): 422-429  DOI: 10.11992/tis.201704031
0

引用本文  

何富贵, 杨铮, 吴陈沭, 等. 一种层次Levenshtein距离的无指纹校准的室内定位方法[J]. 智能系统学报, 2017, 12(3): 422-429. DOI: 10.11992/tis.201704031.
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. DOI: 10.11992/tis.201704031.

基金项目

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

通信作者

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

作者简介

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

文章历史

收稿日期:2017-04-23
网络出版日期:2017-07-03
一种层次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距离    
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
Abstract: 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.
Key words: indoor localization    WiFi fingerprint    heterogeneous device    fingerprint calibration-free    Levenshtein distance    

基于位置的服务,如路径导航、广告推荐和邻近社交网络等,随着智能手机的普及已变得尤为重要。在室内环境中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 < N的有序AP索引向量的子序列作为房间指纹来实现房间级定位。GIFT[21]引入RSSI gradient替代RSSI信息。文献[22]利用Procrustes分析法将绝对RSSI值进行标准化来消除设备异构的影响。针对动态环境下WiFi指纹定位,以适应短期和长期指纹受环境变化,HED[23]提出基于RSSI的AP索引向量的容错序列匹配方法。但该方法未考虑不同AP对位置定位的不同程度的影响力。

通过对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 问题描述

对于室内定位系统,K个发射点(access point, AP) {AP1, AP2, …, APK},对于每个接收点(receive point, RP)接收到信号强度为RPi= RSSI1i, RSSI2i, …, RSSIKi,其空间位置为fi=(xi, yi, zi)。对于RP来说,不能获取到所有的AP信号强度,故对未获取到的RSSI值设定为最小值,即-95 dBm(分贝毫瓦)。在定位过程中,对于需要定位的位置fi通过距离函数Dis(RPi, RPj)在指纹数据库中匹配与其最近邻的N个指纹$\mathbb{N}$(i),N近邻对应的位置为{Y$\mathbb{N}$(1)i, Y$\mathbb{N}$(2)i, …, Y$\mathbb{N}$(N)i}。fi的近邻权重Wij与Dis(RPi, RPj)相关。对于所有需定位位置,实际的定位位置fi与通过N近邻预测的位置${\hat Y^b} = \sum\limits_{j = 1}^N {{W_{ij}}Y_{\mathbb{N}\left(j \right)}^i} $差异越小,表明其定位系统的性能越好。

$ \begin{array}{l} {\rm{Mininize}}\sum\limits_i {\left| {{f_i} - \sum\limits_{j = 1}^N {{W_{ij}}Y_{\mathbb{N}\left( j \right)}^i} } \right|} \\ {\rm{Subject to}}\sum\limits_{j = 1}^N {{W_{ij}}} = 1 \end{array} $ (1)

通常情况下,距离函数Dis(RPi, RPj)可通过欧氏距离、余弦距离或Procrustes氏距离等距离函数来计算。由于设备异构、环境的动态性,无法直接用绝对RSSI值来计算。本文用相对RSSI排序的AP序列替代RSSI绝对的信息,先对RPi=(RSSI1i, RSSI2i, …, RSSIKi)按照RSSI值进行降序,记录对应的AP序列SeqRPi=(N1RPi, N2RPi, …, NKRPi),其中RSSINjRPii≥RSSINj+1RPii。则有距离函数Dis(RPi, RPj)调整为Dis(SeqRPi, SeqRPj)来求解式(1):Dis(SeqRPi, SeqRPj)的性能将决定定位精度,在第2部分介绍如何计算两个AP序列的距离。

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

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

$ d\left( {{\boldsymbol{a}_i},{\boldsymbol{b}_j}} \right) = \left\{ \begin{array}{l} 0,{\rm{ }}i = 0,{\rm{ }}j = 0\\ \min(d({\boldsymbol{a}_{i - 1}},{\boldsymbol{b}_j}) + 1,d({\boldsymbol{a}_i},{\boldsymbol{b}_{j - 1}}) + 1,d({\boldsymbol{a}_{i - 1}},{\boldsymbol{b}_{j - 1}})){\rm{ }},{a_i} = {b_j}\\ \min(d({\boldsymbol{a}_{i - 1}},{\boldsymbol{b}_j}) + 1,d({\boldsymbol{a}_i},{\boldsymbol{b}_{j - 1}}) + 1,d{\rm{ }}({\boldsymbol{a}_{i - 1}},{\boldsymbol{b}_{j - 1}}) + 1),{\rm{ }}{a_i} \ne {b_j} \end{array} \right. $ (2)

式中:aibj分别为长度为ij字符串序列; aibj分别为aibj字符串中第ij序号。

对RPi和RPj按照RSSI值进行降序排列后得到AP序列SeqRPi=(N1RPi, N2RPi, …, NKRPi),SeqRPj=(N1RPj, N2RPj, …, NKRPj)。利用Levenshtein距离计算Dis(SeqRPi, SeqRPj)。

对于∀k, ∃RSSINkRPii≥RSSINk+1RPii,表示RPi从APNkRPi获得的RSSI值要大于等于从APNk+1RPi获得的。在定位匹配过程中发现,不同AP对位置准确定位的贡献不同,RSSI值越大对该位置定位的精度影响越大,通过层级能级来刻画各AP对RP的贡献。从理论上证明,在一定噪声范围内,接收信号强度之差小于ω,区域内AP序列顺序无差异。

为了区别RSSI值差异性,对SeqRPi=(N1RPi, N2RPi, …, NKRPi)依据RSSI值差别大小分成不同层次能级,记为levelRPi=(l1RPi, l2RPi, …, lKRPi)。规定两个相邻AP对应的RSSI值RSSINj-1RPii与RSSINjRPii之差小于阈值θ,其层次能级相同。考虑到连续出现相邻RSSI值差小于阈值θ,最大与最小值差很大,故对最大与最小值差大于2θ的情况,最小值的AP的层次能级加1。两个相邻AP对应的RSSI值RSSINj-1RPii与RSSINjRPii之差在阈值θ~2θ之间,RSSINjRPii层级能级为RSSINj-1RPii加1;以此类推,当两个相邻AP对应的RSSI值RSSINj-1RPii与RSSINjRPii之差大于阈值4θ,RSSINjRPii层级能级为RSSINj-1RPii加4。对于接收点RPi,具体层级能级计算方法见式(3)。阈值θ取值大小通过实验来验证。

$ \begin{array}{l} j = 1;{\rm{ }}l_j^{{\rm{R}}{{\rm{P}}_i}} = 1;{\rm{ }}j = 2,3, \ldots ,K;\\ {\rm{RSSI}}_{N_{j - 1}^{{\rm{R}}{{\rm{P}}_i}}}^i - {\rm{RSSI}}_{N_j^{{\rm{R}}{{\rm{P}}_i}}}^i \le \theta ,{\max _{l_k^{{\rm{R}}{{\rm{P}}_i}} = l_{j - 1}^{{\rm{R}}{{\rm{P}}_i}}}}{\rm{RSSI}}_{N_k^{{\rm{R}}{{\rm{P}}_i}}}^i - {\rm{RSSI}}_{N_j^{{\rm{R}}{{\rm{P}}_i}}}^i \le \\ 2\theta ,l_j^{{\rm{R}}{{\rm{P}}_i}} = l_{j - 1}^{{\rm{R}}{{\rm{P}}_i}};\\ {\rm{RSSI}}_{N_{j - 1}^{{\rm{R}}{{\rm{P}}_i}}}^i - {\rm{RSSI}}_{N_j^{{\rm{R}}{{\rm{P}}_i}}}^i \le \theta {\rm{ }},\max{_{l_k^{{\rm{R}}{{\rm{P}}_i}} = l_{j - 1}^{{\rm{R}}{{\rm{P}}_i}}}}{\rm{RSSI}}_{N_k^{{\rm{R}}{{\rm{P}}_i}}}^i - {\rm{RSSI}}_{N_j^{{\rm{R}}{{\rm{P}}_i}}}^i > \\ 2\theta ,l_j^{{\rm{R}}{{\rm{P}}_i}} = l_{j - 1}^{{\rm{R}}{{\rm{P}}_i}} + 1;\\ \theta < {\rm{RSSI}}_{N_{j - 1}^{{\rm{R}}{{\rm{P}}_i}}}^i - {\rm{RSSI}}_{N_j^{{\rm{R}}{{\rm{P}}_i}}}^i \le 2\theta ,l_j^{{\rm{R}}{{\rm{P}}_i}} = l_{j - 1}^{{\rm{R}}{{\rm{P}}_i}} + 1;\\ 2\theta < {\rm{RSSI}}_{N_{j - 1}^{{\rm{R}}{{\rm{P}}_i}}}^i - {\rm{RSSI}}_{N_j^{{\rm{R}}{{\rm{P}}_i}}}^i \le 3\theta ,l_j^{{\rm{R}}{{\rm{P}}_i}} = l_{j - 1}^{{\rm{R}}{{\rm{P}}_i}} + 2;\\ 3\theta < {\rm{RSSI}}_{N_{j - 1}^{{\rm{R}}{{\rm{P}}_i}}}^i - {\rm{RSSI}}_{N_j^{{\rm{R}}{{\rm{P}}_i}}}^i \le 4\theta ,l_j^{{\rm{R}}{{\rm{P}}_i}} = l_{j - 1}^{{\rm{R}}{{\rm{P}}_i}} + 3;\\ {\rm{RSSI}}_{N_{j - 1}^{{\rm{R}}{{\rm{P}}_i}}}^i - {\rm{RSSI}}_{N_j^{{\rm{R}}{{\rm{P}}_i}}}^i > 4\theta ,l_j^{{\rm{R}}{{\rm{P}}_i}} = l_{j - 1}^{{\rm{R}}{{\rm{P}}_i}} + 4。\end{array} $ (3)

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

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

$ P\left( d \right)\left| {_{{\rm{dBm}}}} \right. = {\rm{ }}P({d_0})\left| {_{{\rm{dBm}}}} \right. - 10\beta \lg \left( {\frac{d}{{{d_0}}}} \right) + {X_{{\rm{dB}}}} $ (4)

式中:P(d)表示接收端到发射机距离为d时接收到的信号强度; P(d0)表示接收端到发射机参考距离为d0时接收到的信号能量; β为路径损耗系数,与环境和建筑物的类型相关联; XdB∈[-Maxnoise, Maxnoise]是服从均值为0的高斯分布变量。

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

$ {P_{\rm{A}}}\left( {{d_{\rm{A}}}} \right)\left| {_{{\rm{dBm}}}} \right. = {\rm{ }}{P_{\rm{A}}}({d_0})\left| {_{{\rm{dBm}}}} \right. - 10{\beta _{\rm{A}}}\lg \left( {\frac{{{d_{\rm{A}}}}}{{{d_0}}}} \right) + X_{{\rm{dB}}}^{\rm{A}} $ (5)
$ {P_{\rm{B}}}\left( {{d_{\rm{B}}}} \right)\left| {_{{\rm{dBm}}}} \right. = {\rm{ }}{P_{\rm{B}}}({d_0})\left| {_{{\rm{dBm}}}} \right. - 10{\beta _{\rm{B}}}\lg \left( {\frac{{{d_{\rm{B}}}}}{{{d_0}}}} \right) + X_{{\rm{dB}}}^{\rm{B}} $ (6)

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

$ \begin{array}{l} {\left( {\frac{{{P_{\rm{A}}}\left( {{d_{\rm{A}}}} \right)}}{{{P_{\rm{A}}}({d_0})}}} \right)_{{\rm{dB}}}} - {\left( {\frac{{{P_{\rm{B}}}\left( {{d_{\rm{B}}}} \right)}}{{{P_{\rm{B}}}({d_0})}}} \right)_{{\rm{dB}}}} - \left( {X_{{\rm{dB}}}^{\rm{A}} - X_{{\rm{dB}}}^{\rm{B}}} \right) \approx \\ -10\beta \lg \left( {\frac{{{d_{\rm{A}}}}}{{{d_{\rm{B}}}}}} \right) < 0 \end{array} $ (7)

则有

$ \left| {{{\left( {\frac{{{P_{\rm{A}}}\left( {{d_{\rm{A}}}} \right)}}{{{P_{\rm{A}}}({d_0})}}} \right)}_{{\rm{dB}}}} - {{\left( {\frac{{{P_{\rm{B}}}\left( {{d_{\rm{B}}}} \right)}}{{{P_{\rm{B}}}({d_0})}}} \right)}_{{\rm{dB}}}}} \right| > 2{\rm{Ma}}{{\rm{x}}_{{\rm{noise}}}} $ (8)

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

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

对于SeqRPi=(N1RPi, N2RPi, …, NKRPi),SeqRPj=(N1RPj, N2RPj, …, NKRPj):

当|SeqRPi|=0和|SeqRPj|=0时,Dis(SeqRPi, SeqRPj)=0;

NmRPi=NnRPj(1≤m, nK)时,

$ \begin{array}{*{20}{l}} {{\rm{Dis}}\left( {{\rm{Se}}{{\rm{q}}_{{\rm{R}}{{\rm{P}}_i}}}\left( m \right),{\rm{Se}}{{\rm{q}}_{{\rm{R}}{{\rm{P}}_j}}}\left( n \right)} \right) = }\\ {\min ({\rm{Dis}}\left( {{\rm{Se}}{{\rm{q}}_{{\rm{R}}{{\rm{P}}_i}}}\left( {m - 1} \right),{\rm{Se}}{{\rm{q}}_{{\rm{R}}{{\rm{P}}_j}}}\left( n \right)} \right) + \alpha ,}\\ {{\rm{Dis}}\left( {{\rm{Se}}{{\rm{q}}_{{\rm{R}}{{\rm{P}}_i}}}\left( m \right),{\rm{Se}}{{\rm{q}}_{{\rm{R}}{{\rm{P}}_j}}}\left( {n - 1} \right)} \right) + \beta ,}\\ {{\rm{Dis}}\left( {{\rm{Se}}{{\rm{q}}_{{\rm{R}}{{\rm{P}}_i}}}\left( {m - 1} \right),{\rm{Se}}{{\rm{q}}_{{\rm{R}}{{\rm{P}}_j}}}\left( {n - 1} \right)} \right));} \end{array} $ (9)

NmRPiNnRPj(1≤m, nK)时,

$ \begin{array}{*{20}{l}} {{\rm{Dis}}\left( {{\rm{Se}}{{\rm{q}}_{{\rm{R}}{{\rm{P}}_i}}}\left( m \right),{\rm{Se}}{{\rm{q}}_{{\rm{R}}{{\rm{P}}_j}}}\left( n \right)} \right) = \min ({\rm{Dis}}({\rm{Se}}{{\rm{q}}_{{\rm{R}}{{\rm{P}}_i}}}\left( {m - 1} \right),}\\ {{\rm{Se}}{{\rm{q}}_{{\rm{R}}{{\rm{P}}_j}}}\left( n \right)) + \alpha ,{\rm{Dis}}\left( {{\rm{Se}}{{\rm{q}}_{{\rm{R}}{{\rm{P}}_i}}}\left( m \right),{\rm{Se}}{{\rm{q}}_{{\rm{R}}{{\rm{P}}_j}}}\left( {n - 1} \right)} \right) + \beta ,}\\ {{\rm{Dis}}\left( {{\rm{Se}}{{\rm{q}}_{{\rm{R}}{{\rm{P}}_i}}}\left( {m - 1} \right),{\rm{Se}}{{\rm{q}}_{{\rm{R}}{{\rm{P}}_j}}}\left( {n - 1} \right)} \right) + \delta )} \end{array} $ (10)

式中:α受序号NnRPj的AP约束,根据levelRPj来计算,α=$\frac{1}{{l_n^{{\rm{R}}{{\rm{P}}_j}}}}$; β受序号NmRPi的AP约束,根据levelRPi来计算,β=$\frac{1}{{l_m^{{\rm{R}}{{\rm{P}}_i}}}}$; $\delta = \left\{ \begin{array}{l} \gamma, 0 \le \gamma < 1\\ 1, \gamma \le 1 \end{array} \right.$

$ {\gamma = \frac{{\left| {{\rm{RSSI}}_{N_m^{{\rm{R}}{{\rm{P}}_{{v_i}}}}}^i - {\rm{RSSI}}_{N_n^{{\rm{R}}{{\rm{P}}_j}}}^j} \right|}}{{\left| {{\rm{Avg}}\left( {{\rm{RSSI}}_{N_m^{{\rm{R}}{{\rm{P}}_i}} \sim N_n^{{\rm{R}}{{\rm{P}}_j}}}^i} \right) - {\rm{Avg}}\left( {{\rm{RSSI}}_{N_m^{{\rm{R}}{{\rm{P}}_i}} \sim N_n^{{\rm{R}}{{\rm{P}}_j}}}^j} \right)} \right|}}} $ (11)

式中:RSSINmRPii表示在RPi中序号为NmRPi的AP的RSSI值; RSSINnRPjj表示在RPj中序号为NnRPj的AP的RSSI值; Avg(SSINmRPi~NnRPji)为在RPi的RSSI值降序序列中RPi中序号为NmRPi的AP到与RPj中序号为NnRPj的AP之间的RSSI值的平均值; Avg(RSSINmRPi~NnRPjj)为在RPj的RSSI值降序序列中RPi中序号为NmRPi的AP到与RPj中序号为NnRPj的AP之间的RSSI值的平均值; γ表示在RPi、RPj中序号分别为NmRPiNnRPj的AP对应的RSSI值的相对差异量。

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 实验场景 Fig.1 Experiment building
表 1 3个实验场景在4种不同时间的AP数量、指纹数据库和测试数据数量 Tab.1 Number of AP in three experiment scenarios at four different times and number of fingerprint database, and test data
3.2 实验结果

本文的定位方法过程是:对于每个接收点通过不同类型的移动设备接收到RSSI1i, RSSI2i, …, RSSIKi,并标记其空间位置(xi, yi, zi)。用HLD算法,对各RPi的RSSI信息降序排列得到AP序列SeqRPi,计算层次能级levelRPi。对于定位预测节点RPj,计算Dis(SeqRPi, SeqRPj)后获取K个近邻,采用WKNN算法进行预测定位。WKNN算法中的权重设置为1/Dis(SeqRPi, SeqRPj)。其定位方法过程涉及两个参数:能量层级参数θ和WKNN算法的近邻数目K

在实验中,本文提出的方法与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 K=5时不同参数θ平均定位误差对比 Fig.2 The average error comparison under different θ parameters in K=5
图 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 HLD算法在3种实验场景下不同K值情况的平均定位误差 Tab.2 Average error of HLD algorithm under different K in three experiment scenarios

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%,对空间维度敏感度较低。

图 6 实验室环境下的4种方法累计定位误差比较 Fig.6 Cumulative localization error comparison of four methods in laboratory
图 7 图书馆环境下的4种方法累计定位误差比较 Fig.7 Cumulative localization error comparison of four methods in library
图 8 3层教室环境下的4种方法累计定位误差比较 Fig.8 Cumulative localization error comparison of four methods in three floors classroom
表 3 3种实验场景下4种方法的平均误差对比 Tab.3 The average error comparison of four methods in three experiment scenarios

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

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. DOI:10.1109/SURV.2009.090103 (0)
[2] HARLE R. A survey of indoor inertial positioning systems for pedestrians[J]. IEEE commun. surveys & tutorials, 2013, 15(3): 1281-1293. (0)
[3] SUBBU K P. Analysis and status quo of smart-phone-based indoor localization systems[J]. IEEE wireless commun, 2014, 21(4): 106-112. DOI:10.1109/MWC.2014.6882302 (0)
[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. (0)
[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. (0)
[6] YOUSSEF M, AGRAWALA A. The horus wlan location determination system[C]//Proceedings of the 3rd International Conferenceon Mobile Systems, Applications, and Services, Washington, USA, 2005: 205-218. (0)
[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. (0)
[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. DOI:10.1007/s11036-008-0139-0 (0)
[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. (0)
[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. DOI:10.1109/TMC.2011.243 (0)
[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. (0)
[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(3): 913-926. DOI:10.1109/TMC.2011.84 (0)
[13] HAEBERLEN A, FLANNERY E, LADD A M, et al. Practical robust localization over large-scale 802[J]. 11 wireless networks[C]//Proceedings of the 10th Annual International Conference on Mobile Computing and Networking, Philadelphia, USA, 2004: 70-84. (0)
[14] KJRGAARD M B. Indoor location fingerprinting with heterogeneous clients[J]. Pervasive and mobile computing, 2011, 7(1): 31-43. DOI:10.1016/j.pmcj.2010.04.005 (0)
[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. (0)
[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. DOI:10.1109/JSEN.2013.2290736 (0)
[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. DOI:10.3390/s150101804 (0)
[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. (0)
[19] YANG S. Freeloc: calibration-free crowdsourced indoor localization[C]//The 32th IEEE International Conference on Computer Communications, Turin, Italy, 2013: 2481-2489. (0)
[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. (0)
[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. DOI:10.1109/TIE.2015.2509917 (0)
[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. (0)
[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. (0)