第3期 何富贵，等：一种层次Levenshtein距离的无指纹校准的室内定位方法 ·423· 的WF指纹室内定位主流方案由两阶段组成：现场 该方法未考虑不同AP对位置定位的不同程度的影 勘查和指纹匹配。 响力。 RADAR[)在未考虑随机信号前提下对WFi指 通过对W指纹信息分析得知：1)对于同一位 纹利用欧氏距离和K近邻算法进行室内目标定位， 置，在容忍一定差异情况下，不同设备检测的AP的 Hous[6)在此基础上考虑RP信号概率分布进行定 RSSI值形成的变化表现出很高的相似性；2)对于不 位估计。建立和更新指纹库是决定基于WFi指纹 同位置，在定位匹配过程中不同AP对其准确定位 定位精度高低的关键。通过专业人士来收集WFi 的贡献不同。不同AP在同一位置测量得到的RSSI 成本昂贵，基于众包模式[)可明显降低指纹地图构 值存在差异。其中一些AP对应的RSSI值较大，这 建和维护成本，但会带来一些新的问题。 些AP对定位的准确性影响较大。 由于无线信号在传播过程存在多径效应，对环 为了实现无指纹校准的室内定位，考虑设备异 境的变化十分敏感，不同时间采集的数据都存在差 构和环境动态的影响，本文提出基于层次 异。环境动态对室内定位系统精度的影响是与生 Levenshtein距离的WiFi指纹距离计算算法。为了 俱来的。对于设备异构的室内定位问题-)，同一 刻画同一位置不同设备检测的RSSI值的变化的相 位置的异构设备检测到的RSSI值通常有不同的值， 似性，将不同移动设备采集的RSSI信息按照从大到 这严重降低了定位精度o-。为了处理基于Wi 小进行降序排列索引，将绝对RSSI信息转化为相对 指纹识别的室内定位系统所遇到的设备异质性问 的AP序列，以实现不同设备采集的数据量纲的一 题，已有不同的解决方案[8,10-51 致性。同时，对于各数据采集点根据各AP对应的 由于用不同设备获取RSSI存在差异[o,1),直 RSSI值的差异性计算其层次能级，将各个AP映射 接用WF信号强度进行预测定位无法达到在现场 到不同层次能级上，以描述各AP对位置定位的影 勘查和指纹匹配的过程中用相同的设备采集WF 响等级。联合各AP层次能级，利用Levenshtein距 指纹的米级定位精度[-6,7-1)。因此，仅依赖于绝对 离来计算AP序列间的距离，实现异构设备的指纹 信号强度测量来实现异构设备的定位是不可行的， 无校准比对。对于需定位的WFi指纹RSSI信息， 迫切需要开发一种替代绝对RSSI的鲁棒指纹定位 利用HLD算法获取K个近邻，采用WKNN算法进 技术。在文献[8,15]中提出了一些无校准方法，以 行预测定位。 避免每个测试设备使用繁琐的手动RSSI校准程序。 1问题描述 协作映射通过训练在线测量的RSSI值来估计线性 映射函数[1)。无监督的学习方法（如在线回归和期 对于室内定位系统，K个发射点(access point, 望最大化)已被用来学习映射函数]。然而，以上无 AP){AP,AP2,…,APx},对于每个接收点(receive 校准的指纹定位方法都需要耗时的在线处理过程。 point,RP)接收到信号强度为RP:= 解决设备异构问题的另一种方式是定义和使用替 (RSSI,RSSL,…,RSSI),其空间位置为f=(x,y 代位置指纹，而不是绝对RSSI值。在文献[10]中 :)。对于RP来说，不能获取到所有的AP信号强 提出信号强度差(SSD),Yang19和Jiangt2]提出将 度，故对未获取到的RSSI值设定为最小值，即 RSSI测量向量转换为相对的RSS排序作为指纹， -95dBm(分贝毫瓦)。在定位过程中，对于需要定 FreeLoct9使用Key-Value机制构造指纹。Jiang2o] 位的位置f通过距离函数Dis(RP:,RP)在指纹数 提出使用长度为n<W的有序AP索引向量的子序列 据库中匹配与其最近邻的V个指纹N(i),N近邻 作为房间指纹来实现房间级定位。GFT21]引入 对应的位置为{N,Y),…,Yw}。f的近 RSSI gradient替代RSSI信息。文献[22]利用 邻权重W与Dis(RP:,RP;)相关。对于所有需定位 Procrustes分析法将绝对RSSI值进行标准化来消除 位置，实际的定位位置与通过N近邻预测的位置 设备异构的影响。针对动态环境下WFi指纹定位， 以适应短期和长期指纹受环境变化，HED[2]提出基 立，=∑W,)差异越小，表明其定位系统的性能 于RSSI的AP索引向量的容错序列匹配方法。但 越好。的 ＷｉＦｉ 指纹室内定位主流方案由两阶段组成：现场 勘查和指纹匹配。 ＲＡＤＡＲ ［５］在未考虑随机信号前提下对 ＷｉＦｉ 指 纹利用欧氏距离和 Ｋ 近邻算法进行室内目标定位， Ｈｏｒｕｓ ［６］在此基础上考虑 ＲＰ 信号概率分布进行定 位估计。 建立和更新指纹库是决定基于 ＷｉＦｉ 指纹 定位精度高低的关键。 通过专业人士来收集 ＷｉＦｉ 成本昂贵，基于众包模式［７］ 可明显降低指纹地图构 建和维护成本，但会带来一些新的问题。 由于无线信号在传播过程存在多径效应，对环 境的变化十分敏感，不同时间采集的数据都存在差 异。 环境动态对室内定位系统精度的影响是与生 俱来的。 对于设备异构的室内定位问题［８－９］ ，同一 位置的异构设备检测到的 ＲＳＳＩ 值通常有不同的值， 这严重降低了定位精度［１０－１１］ 。 为了处理基于 ＷｉＦｉ 指纹识别的室内定位系统所遇到的设备异质性问 题，已有不同的解决方案［８，１０－１５］ 。 由于用不同设备获取 ＲＳＳＩ 存在差异［１０，１６］ ，直 接用 ＷｉＦｉ 信号强度进行预测定位无法达到在现场 勘查和指纹匹配的过程中用相同的设备采集 ＷｉＦｉ 指纹的米级定位精度［５－６，１７－１８］ 。 因此，仅依赖于绝对 信号强度测量来实现异构设备的定位是不可行的， 迫切需要开发一种替代绝对 ＲＳＳＩ 的鲁棒指纹定位 技术。 在文献［８，１５］中提出了一些无校准方法，以 避免每个测试设备使用繁琐的手动 ＲＳＳＩ 校准程序。 协作映射通过训练在线测量的 ＲＳＳＩ 值来估计线性 映射函数［１５］ 。 无监督的学习方法（如在线回归和期 望最大化）已被用来学习映射函数［８］ 。 然而，以上无 校准的指纹定位方法都需要耗时的在线处理过程。 解决设备异构问题的另一种方式是定义和使用替 代位置指纹，而不是绝对 ＲＳＳＩ 值。 在文献［１０］ 中 提出信号强度差（ ＳＳＤ），Ｙａｎｇ ［１９］ 和 Ｊｉａｎｇ ［２０］ 提出将 ＲＳＳＩ 测量向量转换为相对的 ＲＳＳ 排序作为指纹， ＦｒｅｅＬｏｃ ［１９］使用 Ｋｅｙ－Ｖａｌｕｅ 机制构造指纹。 Ｊｉａｎｇ ［２０］ 提出使用长度为 ｎ＜Ｎ 的有序 ＡＰ 索引向量的子序列 作为房间指纹来实现房间级定位。 ＧＩＦＴ ［２１］ 引入 ＲＳＳＩ ｇｒａｄｉｅｎｔ 替 代 ＲＳＳＩ 信 息。 文 献 ［ ２２ ］ 利 用 Ｐｒｏｃｒｕｓｔｅｓ 分析法将绝对 ＲＳＳＩ 值进行标准化来消除 设备异构的影响。 针对动态环境下 ＷｉＦｉ 指纹定位， 以适应短期和长期指纹受环境变化，ＨＥＤ ［２３］提出基 于 ＲＳＳＩ 的 ＡＰ 索引向量的容错序列匹配方法。 但 该方法未考虑不同 ＡＰ 对位置定位的不同程度的影 响力。 通过对 ＷｉＦｉ 指纹信息分析得知：１）对于同一位 置，在容忍一定差异情况下，不同设备检测的 ＡＰ 的 ＲＳＳＩ 值形成的变化表现出很高的相似性；２）对于不 同位置，在定位匹配过程中不同 ＡＰ 对其准确定位 的贡献不同。 不同 ＡＰ 在同一位置测量得到的 ＲＳＳＩ 值存在差异。 其中一些 ＡＰ 对应的 ＲＳＳＩ 值较大，这 些 ＡＰ 对定位的准确性影响较大。 为了实现无指纹校准的室内定位，考虑设备异 构 和 环 境 动 态 的 影 响， 本 文 提 出 基 于 层 次 Ｌｅｖｅｎｓｈｔｅｉｎ 距离的 ＷｉＦｉ 指纹距离计算算法。 为了 刻画同一位置不同设备检测的 ＲＳＳＩ 值的变化的相 似性，将不同移动设备采集的 ＲＳＳＩ 信息按照从大到 小进行降序排列索引，将绝对 ＲＳＳＩ 信息转化为相对 的 ＡＰ 序列，以实现不同设备采集的数据量纲的一 致性。 同时，对于各数据采集点根据各 ＡＰ 对应的 ＲＳＳＩ 值的差异性计算其层次能级，将各个 ＡＰ 映射 到不同层次能级上，以描述各 ＡＰ 对位置定位的影 响等级。 联合各 ＡＰ 层次能级，利用 Ｌｅｖｅｎｓｈｔｅｉｎ 距 离来计算 ＡＰ 序列间的距离，实现异构设备的指纹 无校准比对。 对于需定位的 ＷｉＦｉ 指纹 ＲＳＳＩ 信息， 利用 ＨＬＤ 算法获取 Ｋ 个近邻，采用 ＷＫＮＮ 算法进 行预测定位。 １ 问题描述 对于室内定位系统，Ｋ 个发射点（ ａｃｃｅｓｓ ｐｏｉｎｔ， ＡＰ）｛ＡＰ１ ，ＡＰ２ ，…，ＡＰ Ｋ ｝，对于每个接收点（ ｒｅｃｅｉｖｅ ｐｏｉｎｔ， ＲＰ ） 接 收 到 信 号 强 度 为 ＲＰｉ ＝ ＲＳＳＩ ｉ １ ，ＲＳＳＩ ｉ ２ ，…，ＲＳＳＩ ｉ Ｋ ( ) ，其空间位置为 ｆ ｉ ＝ （ｘｉ，ｙｉ， ｚｉ）。 对于 ＲＰ 来说，不能获取到所有的 ＡＰ 信号强 度，故 对 未 获 取 到 的 ＲＳＳＩ 值 设 定 为 最 小 值， 即 －９５ ｄＢｍ（分贝毫瓦）。 在定位过程中，对于需要定 位的位置 ｆ ｉ 通过距离函数 Ｄｉｓ（ＲＰｉ，ＲＰｊ ）在指纹数 据库中匹配与其最近邻的 Ｎ 个指纹 N（ ｉ），Ｎ 近邻 对应的位置为｛ Ｙ ｉ N(１ ) ，Ｙ ｉ N(２ ) ，…，Ｙ ｉ N(Ｎ) ｝。 ｆ ｉ 的近 邻权重 Ｗｉｊ与 Ｄｉｓ（ＲＰｉ，ＲＰｊ）相关。 对于所有需定位 位置，实际的定位位置 ｆ ｉ 与通过 Ｎ 近邻预测的位置 Ｙ ＾ ｂ ＝ ∑ Ｎ ｊ ＝ １ ＷｉｊＹ ｉ N(ｊ) 差异越小，表明其定位系统的性能 越好。 第 ３ 期 何富贵，等：一种层次 Ｌｅｖｅｎｓｈｔｅｉｎ 距离的无指纹校准的室内定位方法 ·４２３·