基于位置的服务，如路径导航、广告推荐和邻近社交网络等，随着智能手机的普及已变得尤为重要。在室内环境中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) {AP₁, AP₂, …, AP_K}，对于每个接收点(receive point, RP)接收到信号强度为RP_i= RSSI₁ⁱ, RSSI₂ⁱ, …, RSSI_Kⁱ，其空间位置为f_i=(x_i, y_i, z_i)。对于RP来说，不能获取到所有的AP信号强度，故对未获取到的RSSI值设定为最小值，即-95 dBm(分贝毫瓦)。在定位过程中，对于需要定位的位置f_i通过距离函数Dis(RP_i, RP_j)在指纹数据库中匹配与其最近邻的N个指纹$\mathbb{N}$(i)，N近邻对应的位置为{Y_{$\mathbb{N}$(1)}ⁱ, Y_{$\mathbb{N}$(2)}ⁱ, …, Y_{$\mathbb{N}$(N)}ⁱ}。f_i的近邻权重W_ij与Dis(RP_i, RP_j)相关。对于所有需定位位置，实际的定位位置f_i与通过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(a_i, b_j)。

$ 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)

式中：a_i，b_j分别为长度为i，j字符串序列; a_i，b_j分别为a_i，b_j字符串中第i，j序号。

对RP_i和RP_j按照RSSI值进行降序排列后得到AP序列Seq_RPi=(N₁^RP_i, N₂^RP_i, …, N_K^RP_i)，Seq_RPj=(N₁^RP_j, N₂^RP_j, …, N_K^RP_j)。利用Levenshtein距离计算Dis(Seq_RPi, Seq_RPj)。

对于∀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(d₀)表示接收端到发射机参考距离为d₀时接收到的信号能量; β为路径损耗系数，与环境和建筑物的类型相关联; X_dB∈[-Max_noise, Max_noise]是服从均值为0的高斯分布变量。

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

$ {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) 可知：在噪声存在的情况下，两接收信号强度差值大于阈值ω(其大小与环境噪声有关)时，才能区别d_A和d_B大小。故有两个接收信号强度之差小于ω，那么认为由这两个接收信号强度的排序得到的AP序列顺序无差异。证毕。

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

对于Seq_RPi=(N₁^RP_i, N₂^RP_i, …, N_K^RP_i)，Seq_RPj=(N₁^RP_j, N₂^RP_j, …, N_K^RP_j):

当|Seq_RPi|=0和|Seq_RPj|=0时，Dis(Seq_RPi, Seq_RPj)=0;

当N_m^RP_i=N_n^RP_j(1≤m, n≤K)时，

$ \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)

当N_m^RP_i≠N_n^RP_j(1≤m, n≤K)时，

$ \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)

式中：α受序号N_n^RP_j的AP约束，根据level_RPj来计算，α=$\frac{1}{{l_n^{{\rm{R}}{{\rm{P}}_j}}}}$; β受序号N_m^RP_i的AP约束，根据level_RPi来计算，β=$\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中序号分别为NmRPi、NnRPj的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所示。

3.2 实验结果

本文的定位方法过程是：对于每个接收点通过不同类型的移动设备接收到RSSI₁ⁱ, RSSI₂ⁱ, …, RSSI_Kⁱ，并标记其空间位置(x_i, y_i, z_i)。用HLD算法，对各RP_i的RSSI信息降序排列得到AP序列Seq_RPi，计算层次能级level_RPi。对于定位预测节点RP_j，计算Dis(Seq_RPi, Seq_RPj)后获取K个近邻，采用WKNN算法进行预测定位。WKNN算法中的权重设置为1/Dis(Seq_RPi, Seq_RPj)。其定位方法过程涉及两个参数：能量层级参数θ和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) 与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%，时间复杂度相当。

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