【智能系统】一种层次Levenshtein距离的无指纹校准的室内定位方法

第12卷第3期 智能系统学报 Vol.12 No.3 2017年6月 CAAl Transactions on Intelligent Systems Jun.2017 D0I:10.11992/is.201704031 网络出版地址：http:/kns.cmki.ne/kcms/detail/23.1538.TP.20170703.1854.014.html 一种层次Levenshtein距离的无指纹 校准的室内定位方法 何富贵13，杨铮2，吴陈沭2，赵姝3，周先存 (1.皖西学院电子与信息工程学院，安徽六安237012：2.清华大学软件学院可信网络与系统研究所，北京100084： 3.安徽大学智能计算与知识工程研究所，安徽合肥230039) 摘要：随着移动计算领域的兴起，基于位置的服务越来越受青睐。目前各种室内定位的方法层出不穷，由于室内 广泛部署了无线基础设施，基于WF指纹信息的室内定位技术是其主流方法。设备异构和室内环境变化是影响定 位精度的主要因素。本文针对以上两个问题，提出一种层次Levenshtein距离(HLD)的WFi指纹距离计算算法，实 现异构设备的指纹无校准比对。将不同移动设备采集的RSSI信息转化为AP序列，根据AP对应的RSSI值的差异 性计算其层次能级，结合Levenshtein距离计算WiFi指纹之间的距离。对于需定位的Wifi指纹RssI信息，利用HLD 算法获取K个近邻，采用WKNN算法进行预测定位。实验中，为了验证算法的鲁棒性和有效性，在3种不同类型的 室内环境中采用5种不同的移动设备来采集WiFi的RSSI信息，其定位的平均精度达1.5m。 关键词：室内定位：WiFi指纹：设备异构：无指纹校准：Levenshtein距离 中图分类号：TP181 文献标志码：A文章编号：1673-4785(2017)03-0422-08 中文引用格式：何富贵，杨铮，吴陈沭，等.一种层次Levenshtein距离的无指纹校准的室内定位方法[J].智能系统学报，2017,12 (3):422-429. 英文引用格式：HEFugui,.YANG Zheng,WU Chenshu,ctal.An fingerprint calibrations--free indoor localization method based on hierarchical Levenshtein distance[J].CAAI transactions on intelligent systems,2017,12(3):422-429. An fingerprint calibrations-free indoor localization method based on hierarchical Levenshtein distance HE Fugui3,YANG Zheng,WU Chenshu2,ZHAO Shu',ZHOU Xiancun' (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. Keywords:indoor localization;WiFi fingerprint;heterogeneous device;fingerprint calibration-free; Levenshtein distance 基于位置的服务，如路径导航、广告推荐和邻近社交网络等，随着智能手机的普及已变得尤为重 收稿日期：2017-04-23.网络出版日期：2017-07-03. 要。在室内环境中GPS对卫星信号的接收较弱无 基金项目：国家自然科学基金项目(61572366,6130B209,61522110,61402 法满足用户的需求，目前已有许多室内定位技 006,61673020):2016年安徽省高校优秀中青年骨干人才国内外 访学研修重点项目(Z①2016190)：安徽大学信息保障技术协 术1-别涌现。随着EEE802.11(WiFi)普及，基于 同创新中心2015年度开放课题(ADXXBZ201504). 通信作者：何富贵.E-mail:fuguihe@163.com. W指纹室内定位技术已成为研究的热点。现有

第 １２ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．３ ２０１７ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１７ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ． ２０１７０４０３１ 网络出版地址：ｈｔｔｐ： ／ ／ ｋｎｓ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１７０７０３．１８５４．０１４．ｈｔｍｌ 一种层次 Ｌｅｖｅｎｓｈｔｅｉｎ 距离的无指纹 校准的室内定位方法 何富贵１，３ ，杨铮２ ，吴陈沭２ ，赵姝３ ，周先存１ （１．皖西学院 电子与信息工程学院，安徽 六安 ２３７０１２； ２． 清华大学 软件学院可信网络与系统研究所，北京 １０００８４； ３．安徽大学 智能计算与知识工程研究所，安徽 合肥 ２３００３９） 摘 要：随着移动计算领域的兴起，基于位置的服务越来越受青睐。 目前各种室内定位的方法层出不穷，由于室内 广泛部署了无线基础设施，基于 ＷｉＦｉ 指纹信息的室内定位技术是其主流方法。 设备异构和室内环境变化是影响定 位精度的主要因素。 本文针对以上两个问题，提出一种层次 Ｌｅｖｅｎｓｈｔｅｉｎ 距离（ＨＬＤ）的 ＷｉＦｉ 指纹距离计算算法，实 现异构设备的指纹无校准比对。 将不同移动设备采集的 ＲＳＳＩ 信息转化为 ＡＰ 序列，根据 ＡＰ 对应的 ＲＳＳＩ 值的差异 性计算其层次能级，结合 Ｌｅｖｅｎｓｈｔｅｉｎ 距离计算 ＷｉＦｉ 指纹之间的距离。 对于需定位的 ＷｉＦｉ 指纹 ＲＳＳＩ 信息，利用 ＨＬＤ 算法获取 Ｋ 个近邻，采用 ＷＫＮＮ 算法进行预测定位。 实验中，为了验证算法的鲁棒性和有效性，在 ３ 种不同类型的 室内环境中采用 ５ 种不同的移动设备来采集 ＷｉＦｉ 的 ＲＳＳＩ 信息，其定位的平均精度达 １．５ ｍ。 关键词：室内定位；ＷｉＦｉ 指纹；设备异构；无指纹校准；Ｌｅｖｅｎｓｈｔｅｉｎ 距离 中图分类号：ＴＰ１８１ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０３－０４２２－０８ 中文引用格式：何富贵，杨铮，吴陈沭，等．一种层次 Ｌｅｖｅｎｓｈｔｅｉｎ 距离的无指纹校准的室内定位方法［ Ｊ］． 智能系统学报， ２０１７， １２ （３）： ４２２－４２９． 英文引用格式：ＨＥ Ｆｕｇｕｉ，ＹＡＮＧ Ｚｈｅｎｇ，ＷＵ Ｃｈｅｎｓｈｕ， ｅｔ ａｌ． Ａｎ ｆｉｎｇｅｒｐｒｉｎｔ ｃａｌｉｂｒａｔｉｏｎｓ⁃ｆｒｅｅ ｉｎｄｏｏｒ ｌｏｃａｌｉｚａｔｉｏｎ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｈｉｅｒａｒｃｈｉｃａｌ Ｌｅｖｅｎｓｈｔｅｉｎ ｄｉｓｔａｎｃｅ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１７， １２（３）： ４２２－４２９． Ａｎ ｆｉｎｇｅｒｐｒｉｎｔ ｃａｌｉｂｒａｔｉｏｎｓ⁃ｆｒｅｅ ｉｎｄｏｏｒ ｌｏｃａｌｉｚａｔｉｏｎ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｈｉｅｒａｒｃｈｉｃａｌ Ｌｅｖｅｎｓｈｔｅｉｎ ｄｉｓｔａｎｃｅ ＨＥ Ｆｕｇｕｉ １，３ ， ＹＡＮＧ Ｚｈｅｎｇ ２ ， ＷＵ Ｃｈｅｎｓｈｕ ２ ， ＺＨＡＯ Ｓｈｕ ３ ， ＺＨＯＵ Ｘｉａｎｃｕｎ １ （１． Ｓｃｈｏｏｌ ｏｆ Ｅｌｅｃｔｒｏｎｉｃｓ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｗｅｓｔ Ａｎｈｕｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｌｕ’ ａｎ ２３７０１２， Ｃｈｉｎａ； ２． Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｒｕｓｔｗｏｒｔｈｙ Ｎｅｔｗｏｒｋ ａｎｄ Ｓｙｓｔｅｍ， Ｓｃｈｏｏｌ ｏｆ Ｓｏｆｔｗａｒｅ， Ｔｓｉｎｇｈｕａ Ｕｎｉｖｅｒｓｉｔｙ， Ｂｅｉｊｉｎｇ １０００８４， Ｃｈｉｎａ； ３． Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｉｎｔｅｌｌｉｇｅｎｔ Ｃｏｍｐｕｔｉｎｇ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｅｎｇｉｎｅｅｒｉｎｇ， Ａｎｈｕｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｈｅｆｅｉ ２３００３９， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｔｈｅ ｅｒａ ｏｆ ｍｏｂｉｌｅ ｃｏｍｐｕｔｉｎｇ， ｌｏｃａｔｉｏｎ⁃ｂａｓｅｄ ｓｅｒｖｉｃｅｓ ｈａｖｅ ｂｅｃｏｍｅ ｅｘｔｒｅｍｅｌｙ ｉｍｐｏｒｔａｎｔ ｆｏｒ ａ ｗｉｄｅ ｒａｎｇｅ ｏｆ ａｐｐｌｉｃａｔｉｏｎｓ， ａｎｄ ｖａｒｉｏｕｓ ｗｉｒｅｌｅｓｓ ｉｎｄｏｏｒ ｌｏｃａｌｉｚａｔｉｏｎ ｔｅｃｈｎｉｑｕｅｓ ｈａｖｅ ｂｅｅｎ ｅｍｅｒｇｉｎｇ． Ａｍｏｎｇｓｔ ｔｈｅｓｅ ｔｅｃｈｎｉｑｕｅｓ， ＷｉＦｉ ｆｉｎｇｅｒｐｒｉｎｔ⁃ｂａｓｅｄ ｉｎｄｏｏｒ ｌｏｃａｌｉｚａｔｉｏｎ ｉｓ ｏｎｅ ｏｆ ｔｈｅ ｍｏｓｔ ａｔｔｒａｃｔｉｖｅ ｂｅｃａｕｓｅ ｏｆ ｔｈｅ ｗｉｄｅ ｄｅｐｌｏｙｍｅｎｔ ａｎｄ ａｖａｉｌａｂｉｌｉｔｙ ｏｆ ＷｉＦｉ ｉｎｆｒａｓｔｒｕｃｔｕｒｅ． Ｔｈｅ ａｃｃｕｒａｃｙ ｏｆ ｉｎｄｏｏｒ ｌｏｃａｌｉｚａｔｉｏｎ ｉｓ ａｆｆｅｃｔｅｄ ｂｙ ｔｗｏ ｍａｉｎ ｆａｃｔｏｒｓ： ｅｑｕｉｐｍｅｎｔ ｈｅｔｅｒｏｇｅｎｅｉｔｙ ａｎｄ ｅｎｖｉｒｏｎｍｅｎｔａｌ ｄｙｎａｍｉｃｓ． Ｔｏ ｓｏｌｖｅ ｔｈｅ ｏｂｏｖｅ ｔｗｏ ｐｒｏｂｌｅｍｓ， ａｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｈｉｅｒａｒｃｈｉｃａｌ Ｌｅｖｅｎｓｈｔｅｉｎ ｄｉｓｔａｎｃｅ （ ＨＬＤ） ｗａｓ ｐｒｏｐｏｓｅｄ ｔｏ ｒｅａｌｉｚｅ ｃａｌｉｂｒａｔｉｏｎ⁃ｆｒｅｅ ｆｉｎｇｅｒｐｒｉｎｔ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｄｅｖｉｃｅｓ． Ｒｅｃｅｉｖｅｄ ｓｉｇｎａｌ ｓｔｒｅｎｇｔｈ ｉｎｄｉｃａｔｉｏｎ（ＲＳＳＩ） ｉｎｆｏｒｍａｔｉｏｎ ｃｏｌｌｅｃｔｅｄ ｖｉａ ｄｉｆｆｅｒｅｎｔ ｍｏｂｉｌｅ ｄｅｖｉｃｅｓ ｗａｓ ｔｒａｎｓｆｏｒｍｅｄ ｉｎｔｏ ａｎ ＡＰ ｓｅｑｕｅｎｃｅ． Ｔｈｅ ｄｉｆｆｅｒｅｎｃｅ ｉｎ ｔｈｅ Ｒｅｃｅｉｖｅｄ ｓｉｇｎａｌ ｓｔｒｅｎｇｔｈ ｉｎｄｉｃａｔｉｏｎ ＲＳＳＩ ｖａｌｕｅｓ ｗａｓ ｕｓｅｄ ｔｏ ｃａｌｃｕｌａｔｅ ｔｈｅ ｈｉｅｒａｒｃｈｉｃａｌ ｅｎｅｒｇｙ ｌｅｖｅｌ ｏｆ ｅａｃｈ ａｃｃｅｓｓ ｐｏｉｎｔ（ＡＰ）． Ｎｅｘｔ， ｔｈｅ ｄｉｓｔａｎｃｅ ｂｅｔｗｅｅｎ ｔｈｅ ＷｉＦｉ ｆｉｎｇｅｒｐｒｉｎｔｓ ｗａｓ ｃａｌｃｕｌａｔｅｄ ｕｓｉｎｇ ｔｈｅ Ｌｅｖｅｎｓｈｔｅｉｎ ｄｉｓｔａｎｃｅ． Ｔｏ ｌｏｃａｔｅ ＷｉＦｉ ｆｉｎｇｅｒｐｒｉｎｔ ＲＳＳＩ ｉｎｆｏｒｍａｔｉｏｎ， ｔｈｅ ＨＬＤ ａｌｇｏｒｉｔｈｍ ｗａｓ ｕｓｅｄ ｔｏ ｏｂｔａｉｎ Ｋ ｎｅｉｇｈｂｏｒｓ ａｎｄ ｔｈｅ ｗｅｉｇｈｔｅｄ Ｋ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ（ＷＫＮＮ） ａｌｇｏｒｉｔｈｍ ｗａｓ ｕｓｅｄ ｔｏ ｐｒｅｄｉｃｔ ｉｔｓ ｐｏｓｉｔｉｏｎ． Ｆｉｖｅ ｄｉｆｆｅｒｅｎｔ ｍｏｂｉｌｅ ｄｅｖｉｃｅｓ ｗｅｒｅ ｕｓｅｄ ｔｏ ｃｏｌｌｅｃｔ ＷｉＦｉ ＲＳＳＩ ｉｎｆｏｒｍａｔｉｏｎ ｉｎ ｔｈｒｅｅ ｄｉｆｆｅｒｅｎｔ ｔｙｐｅｓ ｏｆ ｉｎｄｏｏｒ ｅｎｖｉｒｏｎｍｅｎｔｓ ｔｏ ｖｅｒｉｆｙ ｔｈｅ ｒｏｂｕｓｔｎｅｓｓ ａｎｄ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ． Ｔｈｅ ａｖｅｒａｇｅ ｌｏｃａｌｉｚａｔｉｏｎ ａｃｃｕｒａｃｙ ｗａｓ １．５ ｍ． Ｋｅｙｗｏｒｄｓ： ｉｎｄｏｏｒ ｌｏｃａｌｉｚａｔｉｏｎ； ＷｉＦｉ ｆｉｎｇｅｒｐｒｉｎｔ； ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｄｅｖｉｃｅ； ｆｉｎｇｅｒｐｒｉｎｔ ｃａｌｉｂｒａｔｉｏｎ⁃ｆｒｅｅ； Ｌｅｖｅｎｓｈｔｅｉｎ ｄｉｓｔａｎｃｅ 收稿日期：２０１７－０４－２３． 网络出版日期：２０１７－０７－０３． 基金项目：国家自然科学基金项目（６１５７２３６６， ６１３０３２０９， ６１５２２１１０， ６１４０２ ００６，６１６７３０２０）；２０１６ 年安徽省高校优秀中青年骨干人才国内外 访学研修重点项目（ｇｘｆｘＺＤ２０１６１９０）；安徽大学信息保障技术协 同创新中心 ２０１５ 年度开放课题（ＡＤＸＸＢＺ２０１５０４）． 通信作者：何富贵． Ｅ⁃ｍａｉｌ：ｆｕｇｕｉｈｅ＠ １６３．ｃｏｍ． 基于位置的服务，如路径导航、广告推荐和邻 近社交网络等，随着智能手机的普及已变得尤为重 要。 在室内环境中 ＧＰＳ 对卫星信号的接收较弱无 法满足 用 户 的 需 求， 目 前 已 有 许 多 室 内 定 位 技 术［１－３］涌现。 随着 ＩＥＥＥ８０２．１１（ＷｉＦｉ）普及［４］ ，基于 ＷｉＦｉ 指纹室内定位技术已成为研究的热点。 现有

第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(ｊ) 差异越小，表明其定位系统的性能 越好。 第 ３ 期 何富贵，等：一种层次 Ｌｅｖｅｎｓｈｔｅｉｎ 距离的无指纹校准的室内定位方法 ·４２３·

·424· 智能系统学报 第12卷 Mininize） RSSIvpr,≥RSSI即。则有距离函数Dis(RP:,RP,)调 整为Dis(Seqr,Seqe)来求解式(1)：Dis(Seqr, Subject to (1) Sqr)的性能将决定定位精度，在第2部分介绍如 何计算两个AP序列的距离。 通常情况下，距离函数Dis(RP:,RP,)可通过欧 氏距离、余弦距离或Procrustes氏距离等距离函数 2 基于层次Levenshtein距离的距离 来计算。由于设备异构、环境的动态性，无法直接 算法 用绝对RSSI值来计算。本文用相对RSSI排序的 Levenshtein距离这个概念由Vladimir AP序列替代RSSI绝对的信息，先对RP,=(RSSI, Levenshtein在l965年提出，通过最少编辑（修改、删 RSSL,…,RSSI)按照RSSI值进行降序，记录对应 除和插入)操作次数来计算字符串之间的相似 的AP序列Sq,=（N",N,…,N),其中 度d(a,b)。 0,i=0,j=0, d(a,b,)=min(d(a-1,b)+1,d(a:,b-)+1,d(a-1,b-i),a:=b (2) min(d(a-1,b)+1,d(a:,b-1)+1,d(a-i,b-i)+1),a:≠b 式中：a:,b分别为长度为i,j字符串序列；a,b分 RP:,具体层级能级计算方法见式(3)。阈值0取值 别为a,b字符串中第i,j序号。 大小通过实验来验证。 对RP,和RP,按照RSSI值进行降序排列后得 j=1;=1;j=2,3,…,K 到AP序列Seqm,=(N",N",,N),Seq= RSS-RSST≤6，mae,=RSS-RSS"≤ (,N,…,N)。利用Levenshtein距离计算 20,1m4=1 Dis(SeqRP,Seq,）o RsS-RSS",≤9，ma"=RS-RSS"> 对于Hk,3RSSI即，≥RSSI即：，表示RP:从 20,=+1; AP即，获得的RSSI值要大于等于从AP,吧：获得的。 在定位匹配过程中发现，不同AP对位置准确定位 940,=+4。(3) 为了区别RSSI值差异性，对Seqm,=(", 结论在一定噪声范围内，接收信号强度之差 N,…,N)依据RSSI值差别大小分成不同层次 小于w,区域内AP序列顺序无差异。 能级，记为levelge,=(,,…,)。规定两个 证明以实际环境中常用无线信号传输模 相邻AP对应的RSSI值RSSI脚：与RSSIYwr,之差小 型一Shadowing模型来论证。 于阈值0，其层次能级相同。考虑到连续出现相邻 P(d)laBm =P(do)laB -10Blgl d +XB(4) RSSI值差小于阈值0，最大与最小值差很大，故对 最大与最小值差大于20的情况，最小值的AP的层 式中：P(d)表示接收端到发射机距离为d时接收 次能级加1。两个相邻AP对应的RSSI值RSSI 到的信号强度：P(d。)表示接收端到发射机参考距 与RSST即：之差在阈值9~20之间，RSSIN,层级能 离为d。时接收到的信号能量；B为路径损耗系数， 级为RSSI,脚加1；以此类推，当两个相邻AP对应 与环境和建筑物的类型相关联；XB∈[-Maxoise, Maxo]是服从均值为0的高斯分布变量。 的RSSI值RSSI即与RSSI,之差大于阈值46， 不失一般性，现有接收端到发射机A和B距离 RSSI即：层级能级为RSSI即：加4。对于接收点 分别为da和d,则有

Ｍｉｎｉｎｉｚｅ∑ｉ ｆ ｉ － ∑ Ｎ ｊ ＝ １ Ｗｉｊ Ｙ ｉ N(ｊ) Ｓｕｂｊｅｃｔ ｔｏ∑ Ｎ ｊ ＝ １ Ｗｉｊ ＝ １ （１） 通常情况下，距离函数 Ｄｉｓ（ＲＰｉ，ＲＰｊ）可通过欧 氏距离、余弦距离或 Ｐｒｏｃｒｕｓｔｅｓ 氏距离等距离函数 来计算。 由于设备异构、环境的动态性，无法直接 用绝对 ＲＳＳＩ 值来计算。 本文用相对 ＲＳＳＩ 排序的 ＡＰ 序列替代 ＲＳＳＩ 绝对的信息，先对 ＲＰｉ ＝ （ＲＳＳＩ ｉ １ ， ＲＳＳＩ ｉ ２ ，…，ＲＳＳＩ ｉ Ｋ ）按照 ＲＳＳＩ 值进行降序，记录对应 的 ＡＰ 序 列 ＳｅｑＲＰｉ ＝ （ Ｎ ＲＰｉ １ ， Ｎ ＲＰｉ ２ ， …， Ｎ ＲＰｉ Ｋ ）， 其 中 ＲＳＳＩ ｉ ＮＲＰ ｉ ｊ ≥ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ＋１ 。 则有距离函数 Ｄｉｓ（ＲＰｉ，ＲＰｊ）调 整为 Ｄｉｓ（ ＳｅｑＲＰｉ ，ＳｅｑＲＰｊ ） 来求解式（１）：Ｄｉｓ（ ＳｅｑＲＰｉ ， ＳｅｑＲＰｊ ）的性能将决定定位精度，在第 ２ 部分介绍如 何计算两个 ＡＰ 序列的距离。 ２ 基于层次 Ｌｅｖｅｎｓｈｔｅｉｎ 距离的距离 算法 Ｌｅｖｅｎｓｈｔｅｉｎ 距 离 这 个 概 念 由 Ｖｌａｄｉｍｉｒ Ｌｅｖｅｎｓｈｔｅｉｎ 在 １９６５ 年提出，通过最少编辑（修改、删 除和插入） 操作次数来计算字符串之间的相似 度ｄ（ａｉ，ｂｊ）。 ｄ（ａｉ，ｂｊ） ＝ ０， ｉ ＝ ０， ｊ ＝ ０， ｍｉｎ（ｄ（ａｉ－１ ，ｂｊ） ＋ １，ｄ（ａｉ，ｂｊ－１ ） ＋ １，ｄ（ａｉ－１ ，ｂｊ－１ ））， ａｉ ＝ ｂｊ ｍｉｎ （ｄ（ａｉ－１ ，ｂｊ） ＋ １，ｄ（ａｉ，ｂｊ－１ ） ＋ １，ｄ（ａｉ－１ ，ｂｊ－１ ） ＋ １）， ａｉ ≠ ｂｊ ì î í ï ï ï ï （２） 式中：ａｉ，ｂｊ 分别为长度为 ｉ，ｊ 字符串序列；ａｉ，ｂｊ 分 别为 ａｉ，ｂｊ 字符串中第 ｉ，ｊ 序号。 对 ＲＰｉ 和 ＲＰｊ 按照 ＲＳＳＩ 值进行降序排列后得 到 ＡＰ 序列 ＳｅｑＲＰｉ ＝ （Ｎ ＲＰｉ １ ，Ｎ ＲＰｉ ２ ，…，Ｎ ＲＰｉ Ｋ ） ， ＳｅｑＲＰｊ ＝ （Ｎ ＲＰｊ １ ， Ｎ ＲＰｊ ２ ，…， Ｎ ＲＰｊ Ｋ ） 。 利用 Ｌｅｖｅｎｓｈｔｅｉｎ 距离计算 Ｄｉｓ（ＳｅｑＲＰｉ ，ＳｅｑＲＰｊ ） 。 对于 ∀ｋ，∃ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｋ ≥ ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｋ＋１ ，表示 ＲＰｉ 从 ＡＰ Ｎ ＲＰ ｉ ｋ 获得的 ＲＳＳＩ 值要大于等于从 ＡＰ Ｎ ＲＰ ｉ ｋ＋１ 获得的 。 在定位匹配过程中发现，不同 ＡＰ 对位置准确定位 的贡献不同，ＲＳＳＩ 值越大对该位置定位的精度影响 越大，通过层级能级来刻画各 ＡＰ 对 ＲＰ 的贡献。 从 理论上证明，在一定噪声范围内，接收信号强度之 差小于 ω，区域内 ＡＰ 序列顺序无差异。 为了区别 ＲＳＳＩ 值差异性，对 ＳｅｑＲＰｉ ＝ （ Ｎ ＲＰｉ １ ， Ｎ ＲＰｉ ２ ，…，Ｎ ＲＰｉ Ｋ ） 依据 ＲＳＳＩ 值差别大小分成不同层次 能级，记为 ｌｅｖｅｌＲＰｉ ＝ （ ｌ ＲＰｉ １ ，ｌ ＲＰｉ ２ ，…，ｌ ＲＰｉ Ｋ ） 。 规定两个 相邻 ＡＰ 对应的 ＲＳＳＩ 值 ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ－１ 与 ＲＳＳＩ ｉ ＮＲＰ ｉ ｊ 之差小 于阈值 θ ，其层次能级相同。 考虑到连续出现相邻 ＲＳＳＩ 值差小于阈值 θ ，最大与最小值差很大，故对 最大与最小值差大于 ２θ 的情况，最小值的 ＡＰ 的层 次能级加 １。 两个相邻 ＡＰ 对应的 ＲＳＳＩ 值 ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ－１ 与 ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ 之差在阈值 θ ～２θ 之间， ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ 层级能 级为 ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ－１ 加 １；以此类推，当两个相邻 ＡＰ 对应 的 ＲＳＳＩ 值 ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ－１ 与 ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ 之差大于阈值 ４θ， ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ 层级能级为 ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ－１ 加 ４。 对于接收点 ＲＰｉ ，具体层级能级计算方法见式（３）。 阈值 θ 取值 大小通过实验来验证。 ｊ ＝ １； ｌ ＲＰｉ ｊ ＝ １； ｊ ＝ ２，３，…，Ｋ； ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ－１ － ＲＳＳＩ ｉ Ｎ ＲＰｉ ｊ ≤ θ，ｍａｘｌＲＰ ｉ ｋ ＝ ｌ ＲＰ ｉ ｊ－１ ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｋ － ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ ≤ ２θ，ｌ ＲＰ ｉ ｊ ＝ ｌ ＲＰ ｉ ｊ－１ ； ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ－１ － ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ ≤ θ ，ｍａｘｌ ＲＰ ｉ ｋ ＝ ｌ ＲＰｉ ｊ－１ ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｋ － ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ ＞ ２θ，ｌ ＲＰｉ ｊ ＝ ｌ ＲＰｉ ｊ－１ ＋ １； θ ＜ ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ－１ － ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ ≤ ２θ，ｌ ＲＰ ｉ ｊ ＝ ｌ ＲＰ ｉ ｊ－１ ＋ １； ２θ ＜ ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ－１ － ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ ≤ ３θ，ｌ ＲＰ ｉ ｊ ＝ ｌ ＲＰ ｉ ｊ－１ ＋ ２； ３θ ＜ ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ－１ － ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ ≤ ４θ，ｌ ＲＰ ｉ ｊ ＝ ｌ ＲＰ ｉ ｊ－１ ＋ ３； ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ－１ － ＲＳＳＩ ｉ Ｎ ＲＰ ｉ ｊ ＞ ４θ，ｌ ＲＰ ｉ ｊ ＝ ｌ ＲＰｉ ｊ－１ ＋ ４。 （３） 结论 在一定噪声范围内，接收信号强度之差 小于 ω，区域内 ＡＰ 序列顺序无差异。 证明 以实际环境中常用无线信号传输模 型———Ｓｈａｄｏｗｉｎｇ 模型来论证。 Ｐ（ｄ） ｄＢｍ ＝ Ｐ（ｄ０ ） ｄＢｍ － １０βｌｇ ｄ ｄ０ æ è ç ö ø ÷ ＋ ＸｄＢ （４） 式中： Ｐ(ｄ) 表示接收端到发射机距离为 ｄ 时接收 到的信号强度； Ｐ ｄ０ ( ) 表示接收端到发射机参考距 离为 ｄ０ 时接收到的信号能量； β 为路径损耗系数， 与环境和建筑物的类型相关联； ＸｄＢ ∈ ［ － Ｍａｘｎｏｉｓｅ， Ｍａｘｎｏｉｓｅ］ 是服从均值为 ０ 的高斯分布变量。 不失一般性，现有接收端到发射机 Ａ 和 Ｂ 距离 分别为 ｄＡ 和 ｄＢ ，则有 ·４２４· 智 能 系 统 学 报 第 １２ 卷

第3期 何富贵，等：一种层次Levenshtein距离的无指纹校准的室内定位方法 ·425· P(d)laB=P(do)lAB -10Balg +X Dis(SeqBP,(m -1),SeqRP,(n -1)));(9) 当W≠N(1≤m,n≤K)时， (5) Dis(SeqRP,SeqRP,)=min(Dis(SeqgP,(m -1), Pe (dB)laB P8(do)laB-10Balg do +X SeqRr,(n))+a,Dis(SeqRP (m),SeqRr (n -1))+B, (6) Dis(SeqRP,(m-1),SeqRe,(n -1))+5)(10) 对于同一区域的近邻位置，B≈B.=B,将式(5) 式中：a受序号N的AP约束，根据levelge来计算， 与式(6)相减，有 ：B受序号的AP约束，根据leve,来计 Q=- P(da） (PE(dg) -(X-X)≈ P (do) B P(d) 、y,0≤y<1 d -101g <0 (7) 1,y≤1 RSST-RSSE w, 则有 Y-TAvg(RSST)-Avg(RSSE)I Pa (d) 2Max(8) (11) 由式(8)可知：在噪声存在的情况下，两接收信 式中：RSS,表示在RP:中序号为N的AP的 号强度差值大于阈值ω（其大小与环境噪声有关） RSSI值；RSSI,表示在RP,中序号为N的AP的 时，才能区别d,和d大小。故有两个接收信号强 RSSI值；Avg(RSSIjw-)为在RP:的RSSI值降 度之差小于w,那么认为由这两个接收信号强度的 序序列中RP:中序号为N的AP到与RP,中序号 排序得到的AP序列顺序无差异。证毕。 为N"的AP之间的RSSI值的平均值； 由于AP序列中各AP在WFi指纹中的能级等 Avg(RSS-A)为在RP,的RSSI值降序序列中 级不同，删除和插入操作需要考虑AP的能级等级。 RP:中序号为N的AP到与RP,中序号为N的 由结论1可知，接收信号强度之差越小，AP序列 AP之间的RSSI值的平均值；Y表示在RP:、RP中 Sq,顺序差异越小。修改操作距离通过修改前后 序号分别为N:、N的AP对应的RSSI值的相对 两个AP的RSSI变化差异性来表现。对 差异量。 Levenshtein距离进行修正，得到基于Levenshtein距 离的距离函数Dis(Seqr,SeqRr）。 3性能评价 对于Seqe,=(N,N",,N）,Seqm= 3.1实验准备 我们在5种不同的安卓设备上测试算法性能， (N,N,…,N): 这5种设备分别为Huawei G9、Huawei M2、Samsung 当|Seqrr,|=0和|Seqr|=0时，Dis(Seqr, s6,Samsung note3、Nexus5。分别对3种不同室内场 Seqe）=0; 景（实验室、图书馆和教室）进行实验。实验室的布 局分布如图1(a),总体布局为15m×45m:图书馆 当N=N"(1≤m,n≤K)时， 的布局分布如图1(b),总体布局为78m×95m:教 Dis(SeqRP,(m),SeqRP,(n))= 室的各层布局分布如图1(c),平面总体布局为 20m×120m,共3层。各实验场景的Wii是事先 min(Dis(Seqge (m -1),SeqRP (n))+a, 已布置的，本次实验没有额外布置AP。考虑环境变 Dis(SeqRe,(m),SeqRP,(n-1))+B, 化和不同实验操作者对采集信号的影响，5个志愿

ＰＡ（ｄＡ） ｄＢｍ ＝ ＰＡ（ｄ０ ） ｄＢｍ － １０ βＡ ｌｇ ｄＡ ｄ０ æ è ç ö ø ÷ ＋ Ｘ Ａ ｄＢ （５） ＰＢ （ｄＢ ） ｄＢｍ ＝ ＰＢ （ｄ０ ） ｄＢｍ － １０ βＢ ｌｇ ｄＢ ｄ０ æ è ç ö ø ÷ ＋ Ｘ Ｂ ｄＢ （６） 对于同一区域的近邻位置，βＡ≈βＢ ＝ β，将式（５） 与式（６）相减，有 ＰＡ ｄＡ ( ) ＰＡ ｄ０ ( ) æ è ç ö ø ÷ ｄＢ － ＰＢ ｄＢ ( ) ＰＢ ｄ０ ( ) æ è ç ö ø ÷ ｄＢ － Ｘ Ａ ｄＢ － Ｘ Ｂ ｄＢ ( ) ≈ － １０βｌｇ ｄＡ ｄＢ æ è ç ö ø ÷ ＜ ０ （７） 则有 ＰＡ ｄＡ ( ) ＰＡ ｄ０ ( ) æ è ç ö ø ÷ ｄＢ － ＰＢ ｄＢ ( ) ＰＢ ｄ０ ( ) æ è ç ö ø ÷ ｄＢ ＞ ２Ｍａｘｎｏｉｓｅ （８） 由式（８）可知：在噪声存在的情况下，两接收信 号强度差值大于阈值 ω （其大小与环境噪声有关） 时，才能区别 ｄＡ 和 ｄＢ 大小。 故有两个接收信号强 度之差小于 ω ，那么认为由这两个接收信号强度的 排序得到的 ＡＰ 序列顺序无差异。 证毕。 由于 ＡＰ 序列中各 ＡＰ 在 ＷｉＦｉ 指纹中的能级等 级不同，删除和插入操作需要考虑 ＡＰ 的能级等级。 由结论 １ 可知，接收信号强度之差越小，ＡＰ 序列 ＳｅｑＲＰｉ 顺序差异越小。 修改操作距离通过修改前后 两 个 ＡＰ 的 ＲＳＳＩ 变 化 差 异 性 来 表 现。 对 Ｌｅｖｅｎｓｈｔｅｉｎ 距离进行修正，得到基于 Ｌｅｖｅｎｓｈｔｅｉｎ 距 离的距离函数 Ｄｉｓ（ＳｅｑＲＰｉ ，ＳｅｑＲＰｊ ） 。 对于 ＳｅｑＲＰｉ ＝ （ Ｎ ＲＰｉ １ ， Ｎ ＲＰｉ ２ ， …， Ｎ ＲＰｉ Ｋ ）， ＳｅｑＲＰｊ ＝ （Ｎ ＲＰｊ １ ，Ｎ ＲＰｊ ２ ，…，Ｎ ＲＰｊ Ｋ ）： 当 ＳｅｑＲＰｉ ＝ ０ 和 ＳｅｑＲＰｊ ＝ ０ 时， Ｄｉｓ （ ＳｅｑＲＰｉ ， ＳｅｑＲＰｊ ）＝ ０； 当Ｎ ＲＰｉ ｍ ＝Ｎ ＲＰｊ ｎ （１≤ｍ，ｎ≤Ｋ）时， Ｄｉｓ（ＳｅｑＲＰｉ （ｍ），ＳｅｑＲＰｊ （ｎ）） ＝ ｍｉｎ（Ｄｉｓ（ＳｅｑＲＰｉ （ｍ － １），ＳｅｑＲＰｊ （ｎ）） ＋ α， Ｄｉｓ（ＳｅｑＲＰｉ （ｍ），ＳｅｑＲＰｊ （ｎ － １）） ＋ β， Ｄｉｓ（ＳｅｑＲＰｉ （ｍ － １），ＳｅｑＲＰｊ （ｎ － １）））； （９） 当Ｎ ＲＰｉ ｍ ≠Ｎ ＲＰｊ ｎ （１≤ｍ，ｎ≤Ｋ）时， Ｄｉｓ（ＳｅｑＲＰｉ ，ＳｅｑＲＰｊ ） ＝ ｍｉｎ（Ｄｉｓ（ＳｅｑＲＰｉ （ｍ － １）， ＳｅｑＲＰｊ （ｎ）） ＋ α，Ｄｉｓ（ＳｅｑＲＰｉ （ｍ），ＳｅｑＲＰｊ （ｎ － １）） ＋ β， Ｄｉｓ（ＳｅｑＲＰｉ （ｍ － １），ＳｅｑＲＰｊ （ｎ － １）） ＋ δ） （１０） 式中：α 受序号Ｎ ＲＰｊ ｎ 的 ＡＰ 约束，根据ｌｅｖｅｌＲＰｊ来计算， α＝ １ ｌ ＲＰｊ ｎ ；β 受序号Ｎ ＲＰｉ ｍ 的 ＡＰ 约束，根据ｌｅｖｅｌＲＰｉ 来计 算，β ＝ １ ｌ ＲＰｉ ｍ ；δ ＝ γ， ０≤γ＜１ １， γ≤１ { γ ＝ ＲＳＳＩ ｉ ＮＲＰｖ ｉ ｍ －ＲＳＳＩ ｊ ＮＲＰ ｊ ｎ Ａｖｇ ＲＳＳＩ ｉ ＮＲＰ ｉ ｍ ～ＮＲＰ ｊ ｎ ( ) －Ａｖｇ ＲＳＳＩ ｊ ＮＲＰ ｉ ｍ ～ＮＲＰ ｎ ｊ ( ) （１１） 式中：ＲＳＳＩ ｉ ＮＲＰ ｍ ｉ 表示在 ＲＰｉ 中序号为 Ｎ ＲＰｉ ｍ 的 ＡＰ 的 ＲＳＳＩ 值； ＲＳＳＩ ｊ ＮＲＰ ｊ ｎ 表示在 ＲＰｊ 中序号为 Ｎ ＲＰｊ ｎ 的 ＡＰ 的 ＲＳＳＩ 值； Ａｖｇ ＲＳＳＩ ｉ ＮＲＰ ｉ ｍ ～ ＮＲＰ ｊ ｎ ( ) 为在 ＲＰｉ 的 ＲＳＳＩ 值降 序序列中 ＲＰｉ 中序号为 Ｎ ＲＰ ｉ ｍ 的 ＡＰ 到与 ＲＰｊ 中序号 为 Ｎ ＲＰｊ ｎ 的 ＡＰ 之 间 的 ＲＳＳＩ 值 的 平 均 值； Ａｖｇ ＲＳＳＩ ｊ ＮＲＰ ｉ ｍ ～ ＮＲＰ ｊ ｎ ( ) 为在 ＲＰｊ 的 ＲＳＳＩ 值降序序列中 ＲＰｉ 中序号为 Ｎ ＲＰｉ ｍ 的 ＡＰ 到与 ＲＰｊ 中序号为 Ｎ ＲＰｊ ｎ 的 ＡＰ 之间的 ＲＳＳＩ 值的平均值； γ 表示在 ＲＰｉ、ＲＰｊ 中 序号分别为 Ｎ ＲＰｉ ｍ 、Ｎ ＲＰｊ ｎ 的 ＡＰ 对应的 ＲＳＳＩ 值的相对 差异量。 ３ 性能评价 ３．１ 实验准备 我们在 ５ 种不同的安卓设备上测试算法性能， 这 ５ 种设备分别为 Ｈｕａｗｅｉ Ｇ９、Ｈｕａｗｅｉ Ｍ２、Ｓａｍｓｕｎｇ ｓ６、Ｓａｍｓｕｎｇ ｎｏｔｅ３、Ｎｅｘｕｓ ５。 分别对 ３ 种不同室内场 景（实验室、图书馆和教室）进行实验。 实验室的布 局分布如图 １（ａ），总体布局为 １５ ｍ×４５ ｍ；图书馆 的布局分布如图 １（ ｂ），总体布局为 ７８ ｍ×９５ ｍ；教 室的各层布局分布如图 １ （ ｃ），平面总体布局为 ２０ ｍ×１２０ ｍ，共 ３ 层。 各实验场景的 ＷｉＦｉ 是事先 已布置的，本次实验没有额外布置 ＡＰ。 考虑环境变 化和不同实验操作者对采集信号的影响，５ 个志愿 第 ３ 期 何富贵，等：一种层次 Ｌｅｖｅｎｓｈｔｅｉｎ 距离的无指纹校准的室内定位方法 ·４２５·

·426· 智能系统学报 第12卷 者在4个时间段（间隔一个星期、1个月和3个月） 数据库选择前3次采集的数据，对同一个位置的多 内手持上述5种不同的安卓设备各自独立在不同场 条数据只随机保留一条记录，且保证各数据之间的地 景下采集WFi的RSSI信息，并记录采集点的地理 理位置距离大于等于1m;定位测试数据选择第3、4次 位置。各个采集点采集时间间隔不等，其跨度在 采集的数据。3个实验场景下4种不同时间的AP数 10~25s。为了客观评估定位性能，现场勘查的指纹 量变化、指纹数据库和测试数据数量如表1所示。 表13个实验场景在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数量指纹数据库数量测试数据数量 实验室 19 21 19 22 370 50 图书馆 18 17 18 18 1450 100 教室 26 21 26 24 6500 300 3.2实验结果 本文的定位方法过程是：对于每个接收点通过 不同类型的移动设备接收到 (RSSI,RSS,…,RSSI),并标记其空间位置(x, y:,)。用HLD算法，对各RP,的RSSI信息降序排 列得到AP序列Seqe,计算层次能级levelgr,。对 于定位预测节点RP,,计算Dis(Seqr,Seqe)后 获取K个近邻，采用WKNN算法进行预测定位。 WKNN算法中的权重设置为l/Dis(Seqr,Seqe)。 其定位方法过程涉及两个参数：能量层级参数日和 WKNN算法的近邻数目K。 在实验中，本文提出的方法与3种经典室内定 位方法进行对比。第一种方法是文献[5]提出的 RADAR算法。因为不同设备获取的RSSI差异较 大，无法用欧氏距离来计算各RP的相似度，在实验 (a)实验室 中将RADAR算法中欧氏距离替换为余弦距离计算 各RP的相似度：第二种方法是文献[19]提出的 FreeLoc算法，该算法的基本思想是通过Key-Value 办公室 办公 机制构造指纹来容忍诸如设备多样性和信号变化的 17平方米 14平方米 环境动态：第三种方法是文献[23]提出的HED算 办公 法，该算法利用容错序列匹配策略来实现动态环境 (b)图书馆 下WFi指纹定位。采用平均定位误差和累计定位 误差两种误差度量来对比4种室内定位方法的定位 性能优越程度。 (c)教室 1)能量层级参数0、近邻数目K选择 图1实验场景 为了测试能量层级参数0、近邻数目K对定位 Fig.1 Experiment building 精度的影响，分别设定0=3,4,4.5,5,5.5,6,7和K=

者在 ４ 个时间段（间隔一个星期、１ 个月和 ３ 个月） 内手持上述 ５ 种不同的安卓设备各自独立在不同场 景下采集 ＷｉＦｉ 的 ＲＳＳＩ 信息，并记录采集点的地理 位置。 各个采集点采集时间间隔不等，其跨度在 １０～２５ ｓ。 为了客观评估定位性能，现场勘查的指纹 数据库选择前 ３ 次采集的数据，对同一个位置的多 条数据只随机保留一条记录，且保证各数据之间的地 理位置距离大于等于 １ ｍ；定位测试数据选择第 ３、４ 次 采集的数据。 ３ 个实验场景下 ４ 种不同时间的 ＡＰ 数 量变化、指纹数据库和测试数据数量如表 １ 所示。 表 １ ３ 个实验场景在 ４ 种不同时间的 ＡＰ 数量、指纹数据库和测试数据数量 Ｔａｂｌｅ １ Ｎｕｍｂｅｒ ｏｆ ＡＰ ｉｎ ｔｈｒｅｅ ｅｘｐｅｒｉｍｅｎｔ ｓｃｅｎａｒｉｏｓ ａｔ ｆｏｕｒ ｄｉｆｆｅｒｅｎｔ ｔｉｍｅｓ ａｎｄ ｎｕｍｂｅｒ ｏｆ ｆｉｎｇｅｒｐｒｉｎｔ ｄａｔａｂａｓｅ， ａｎｄ ｔｅｓｔ ｄａｔａ 实验场景 第 １ 次 ＡＰ 数量 第 ２ 次 ＡＰ 数量 第 ３ 次 ＡＰ 数量 第 ４ 次 ＡＰ 数量 指纹数据库数量 测试数据数量 实验室 １９ ２１ １９ ２２ ３７０ ５０ 图书馆 １８ １７ １８ １８ １４５０ １００ 教室 ２６ ２１ ２６ ２４ ６５００ ３００ （ａ）实验室 （ｂ）图书馆 （ｃ）教室 图 １ 实验场景 Ｆｉｇ．１ Ｅｘｐｅｒｉｍｅｎｔ ｂｕｉｌｄｉｎｇ ３．２ 实验结果 本文的定位方法过程是：对于每个接收点通过 不 同 类 型 的 移 动 设 备 接 收 到 ＲＳＳＩ ｉ １ ，ＲＳＳＩ ｉ ２ ，…，ＲＳＳＩ ｉ Ｋ ( ) ，并标记其空间位置 （ｘｉ， ｙｉ，ｚｉ） 。 用 ＨＬＤ 算法，对 各ＲＰｉ 的 ＲＳＳＩ 信息降序排 列得到 ＡＰ 序列 ＳｅｑＲＰｉ ，计算 层次能级 ｌｅｖｅｌＲＰｉ 。 对 于定位预测节点 ＲＰｊ ， 计算 Ｄｉｓ ＳｅｑＲＰｉ ，ＳｅｑＲＰｊ ( ) 后 获取 Ｋ 个近邻，采用 ＷＫＮＮ 算法进行预测定位。 ＷＫＮＮ 算法中的权重设置为 １ ／ Ｄｉｓ ＳｅｑＲＰｉ ，ＳｅｑＲＰｊ ( ) 。 其定位方法过程涉及两个参数：能量层级参数 θ 和 ＷＫＮＮ 算法的近邻数目 Ｋ。 在实验中，本文提出的方法与 ３ 种经典室内定 位方法进行对比。 第一种方法是文献［ ５］ 提出的 ＲＡＤＡＲ 算法。 因为不同设备获取的 ＲＳＳＩ 差异较 大，无法用欧氏距离来计算各 ＲＰ 的相似度，在实验 中将 ＲＡＤＡＲ 算法中欧氏距离替换为余弦距离计算 各 ＲＰ 的相似度；第二种方法是文献［ １９］ 提出的 ＦｒｅｅＬｏｃ 算法，该算法的基本思想是通过 Ｋｅｙ⁃Ｖａｌｕｅ 机制构造指纹来容忍诸如设备多样性和信号变化的 环境动态；第三种方法是文献［２３］ 提出的 ＨＥＤ 算 法，该算法利用容错序列匹配策略来实现动态环境 下 ＷｉＦｉ 指纹定位。 采用平均定位误差和累计定位 误差两种误差度量来对比 ４ 种室内定位方法的定位 性能优越程度。 １）能量层级参数 θ 、近邻数目 Ｋ 选择 为了测试能量层级参数 θ 、近邻数目 Ｋ 对定位 精度的影响，分别设定 θ ＝ ３，４，４．５，５，５．５，６，７ 和 Ｋ ＝ ·４２６· 智 能 系 统 学 报 第 １２ 卷

第3期 何富贵，等：一种层次Levenshtein距离的无指纹校准的室内定位方法 ·427. 2,3,4,5,6,对比在三种场景下的定位测试。对于不 1.0m 同场景，通过两个参数交叉验证。当0=5时，算法 0.9 0.8 达到最优。K=5时参数0对预测定位的影响如图2 0.7 所示。结合分析图3~5的累计定位误差和表2的 0.6 0.5 平均定位误差：K=5时，在实验室和图书馆场景下， 0.4 -K=2 其算法达到最优：K=4时，在教室场景下，其算法达 0.3 =4 0.2 到最优。其原因是，实验室和图书馆场景是二维位 =5 0.1 …+…K=6 置数据信息，教室的数据是立体地理位置。 0 2 34 56 定位误差/m 表2ⅢD算法在3种实验场景下不同K值情况的平均定位误差 图4 HD算法在图书馆环境下的不同K值的累计定 Table 2 Average error of HLD algorithm under different K 位误差比较 in three experiment scenarios Fig.4 Cumulative localization error comparison of HLD 场景 algorithm under different K values in library K=2 K=3 K=4 K=5 K=6 1.01 实验室 3.08 2.40 1.88 1.46 3.14 0.9 0.8 图书馆 2.37 2.31 2.01 1.35 2.57 0.7 0.6 教室 2.74 2.27 1.45 1.58 2.86 0.5 0.4 K=2 0.3 K=4 4.5 0.2 4.0 0.1 3.5 0 3.0 4 6 2.5 定位误差m 2.0 图5HLD算法在3层教室环境下的不同K值的累计 .s 定位误差比较 1.0 Fig.5 Cumulative localization error comparison of HLD 0.5 algorithm under differet K values in three floors 3.04.04.55.05.56.07.0 classroom 2)与RADAR、FreeLoc和HED算法性能比较 图2K=5时不同参数0平均定位误差对比 在实验室和图书馆场景下，HED算法的K取值 Fig.2 The average error comparison under different 6 parameters in K=5 5:在教室场景下，HED算法的K取值4。RADAR算 法中K值和HED算法相同。在3种实验场景下4 种方法累计定位误差对比如图6~8所示，表3描述 1.0 0.9 了3种实验场景下4种方法平均定位误差对比。 0.8 RADAR对于平面环境下的定位误差在4~6m,2m 0.7 0.6 内误差准确度在20%以下，基本达不到定位的效果： 05 0 -K=2 对三维环境下的定位效果更差。FreeLoc、HED对于 ◆-K=3 0.3 平面环境下的定位误差在2~4m,3m内误差准确 0.2 -K=5 -*-=6 0.1 度在50%~60%，但在三维环境下的定位效果3m 0 内误差准确精度下降到40%左右。HLD算法整体 3 6 定位误差/m 的平均误差为1.5m,2m内误差准确度为70% 图3皿D算法在实验室环境下的不同K值的累计定 80%,对空间维度敏感度较低。 位误差比较 在定位过程中，与FreeLoc、HED算法执行效率 Fig.3 Cumulative localization error comparison of HLD 进行比较，HLD算法时空复杂度比FreeLoc低40%， algorithm under different K values in laboratory 比HED空间复杂度高10%，时间复杂度相当

２，３，４，５，６，对比在三种场景下的定位测试。 对于不 同场景，通过两个参数交叉验证。 当 θ ＝ ５ 时，算法 达到最优。 Ｋ ＝ ５ 时参数 θ 对预测定位的影响如图 ２ 所示。 结合分析图 ３ ～ ５ 的累计定位误差和表 ２ 的 平均定位误差：Ｋ ＝ ５ 时，在实验室和图书馆场景下， 其算法达到最优；Ｋ ＝ ４ 时，在教室场景下，其算法达 到最优。 其原因是，实验室和图书馆场景是二维位 置数据信息，教室的数据是立体地理位置。 表２ ＨＬＤ 算法在３种实验场景下不同Ｋ 值情况的平均定位误差 Ｔａｂｌｅ ２ Ａｖｅｒａｇｅ ｅｒｒｏｒ ｏｆ ＨＬＤ ａｌｇｏｒｉｔｈｍ ｕｎｄｅｒ ｄｉｆｆｅｒｅｎｔ Ｋ ｉｎ ｔｈｒｅｅ ｅｘｐｅｒｉｍｅｎｔ ｓｃｅｎａｒｉｏｓ ｍ 场景 Ｋ＝ ２ Ｋ＝ ３ Ｋ＝ ４ Ｋ＝ ５ Ｋ＝ ６ 实验室 ３．０８ ２．４０ １．８８ １．４６ ３．１４ 图书馆 ２．３７ ２．３１ ２．０１ １．３５ ２．５７ 教室 ２．７４ ２．２７ １．４５ １．５８ ２．８６ 图 ２ Ｋ＝ ５ 时不同参数 θ 平均定位误差对比 Ｆｉｇ．２ Ｔｈｅ ａｖｅｒａｇｅ ｅｒｒｏｒ ｃｏｍｐａｒｉｓｏｎ ｕｎｄｅｒ ｄｉｆｆｅｒｅｎｔ θ ｐａｒａｍｅｔｅｒｓ ｉｎ Ｋ＝ ５ 图 ３ ＨＬＤ 算法在实验室环境下的不同 Ｋ 值的累计定 位误差比较 Ｆｉｇ．３ Ｃｕｍｕｌａｔｉｖｅ ｌｏｃａｌｉｚａｔｉｏｎ ｅｒｒｏｒ ｃｏｍｐａｒｉｓｏｎ ｏｆ ＨＬＤ ａｌｇｏｒｉｔｈｍ ｕｎｄｅｒ ｄｉｆｆｅｒｅｎｔ Ｋ ｖａｌｕｅｓ ｉｎ ｌａｂｏｒａｔｏｒｙ 图 ４ ＨＬＤ 算法在图书馆环境下的不同 Ｋ 值的累计定 位误差比较 Ｆｉｇ．４ Ｃｕｍｕｌａｔｉｖｅ ｌｏｃａｌｉｚａｔｉｏｎ ｅｒｒｏｒ ｃｏｍｐａｒｉｓｏｎ ｏｆ ＨＬＤ ａｌｇｏｒｉｔｈｍ ｕｎｄｅｒ ｄｉｆｆｅｒｅｎｔ Ｋ ｖａｌｕｅｓ ｉｎ ｌｉｂｒａｒｙ 图 ５ ＨＬＤ 算法在 ３ 层教室环境下的不同 Ｋ 值的累计 定位误差比较 Ｆｉｇ．５ Ｃｕｍｕｌａｔｉｖｅ ｌｏｃａｌｉｚａｔｉｏｎ ｅｒｒｏｒ ｃｏｍｐａｒｉｓｏｎ ｏｆ ＨＬＤ ａｌｇｏｒｉｔｈｍ ｕｎｄｅｒ ｄｉｆｆｅｒｅｔ Ｋ ｖａｌｕｅｓ ｉｎ ｔｈｒｅｅ ｆｌｏｏｒｓ ｃｌａｓｓｒｏｏｍ ２）与 ＲＡＤＡＲ、ＦｒｅｅＬｏｃ 和 ＨＥＤ 算法性能比较 在实验室和图书馆场景下，ＨＥＤ 算法的 Ｋ 取值 ５；在教室场景下，ＨＥＤ 算法的 Ｋ 取值 ４。 ＲＡＤＡＲ 算 法中 Ｋ 值和 ＨＥＤ 算法相同。 在 ３ 种实验场景下 ４ 种方法累计定位误差对比如图 ６ ～ ８ 所示，表 ３ 描述 了 ３ 种实验场景下 ４ 种方法平均定位误差对比。 ＲＡＤＡＲ 对于平面环境下的定位误差在４～ ６ ｍ，２ ｍ 内误差准确度在 ２０％以下，基本达不到定位的效果； 对三维环境下的定位效果更差。 ＦｒｅｅＬｏｃ、ＨＥＤ 对于 平面环境下的定位误差在 ２ ～ ４ ｍ，３ ｍ 内误差准确 度在 ５０％ ～ ６０％，但在三维环境下的定位效果 ３ ｍ 内误差准确精度下降到 ４０％左右。 ＨＬＤ 算法整体 的平均误差为 １．５ ｍ，２ ｍ 内误差准确度为 ７０％ ～ ８０％，对空间维度敏感度较低。 在定位过程中，与 ＦｒｅｅＬｏｃ、ＨＥＤ 算法执行效率 进行比较，ＨＬＤ 算法时空复杂度比 ＦｒｅｅＬｏｃ 低 ４０％， 比 ＨＥＤ 空间复杂度高 １０％，时间复杂度相当。 第 ３ 期 何富贵，等：一种层次 Ｌｅｖｅｎｓｈｔｅｉｎ 距离的无指纹校准的室内定位方法 ·４２７·

428. 智能系统学报 第12卷 1.0 0.9 4 总结 0.8 0.7 本文讨论了设备异构和室内环境变化情形下的 0.6 室内定位问题，提出了基于层次Levenshtein距离的 0.5 0.4 -◆-RADAR WF指纹距离计算算法。在无校准情形下，将不同 0.3 -HED 0.2 -.-FreeLoc 移动设备采集的RSSI信息转化为AP序列，以解决 -HLD 0.1 不同设备获取的RSSI信息的量纲一致性问题。根 04 345 78 据AP对应的RSSI值的差异性计算其层次能级，结 定位误差m 合Levenshtein距离计算WiFi指纹之间的距离，提供 图6实验室环境下的4种方法累计定位误差比较 一种适应异构设备和动态环境下计算各RP间指纹 Fig.6 Cumulative localization error comparison of four 距离的鲁棒性方法。对于需定位的WFi指纹RSSI methods in laboratory 表33种实验场景下4种方法的平均误差对比 信息，采用WKNN算法进行预测定位。实验中，为 Tab 3 The average error comparison of four methods in 了验证算法的鲁棒性和有效性，在3种不同类型的 three experiment scenarios m 室内环境中用5种不同的移动设备来采集Wi的 RSSI信息，其定位的平均精度达1.5m,2m内误差 场景 RADAR FreeLoc HED HLD 准确度在70%~80%，对空间维度敏感度较低。 实验室 4.25 3.11 3.57 1.46 图书馆 5.70 2.97 3.27 1.35 参考文献： 教室 9.56 5.02 6.78 1.45 [1]GU Y,LO A,NIEMEGEERS I.A survey of indoor positioning 1.0 systems for wireless personal networks[J].IEEE commun. 0.9 surveys and tutorials,2009,11(1):13-32 0.8 0.7 [2]HARLE R.A survey of indoor inertial positioning systems for 0.6 pedestrians[]].IEEE commun.surveys tutorials,2013, 15(3):1281-1293 0.4 -RADAR 0.3 -HED [3]SUBBU K P.Analysis and status quo of smart-phone-based 0.2 ---FreeLoc --HLD indoor localization systems J].IEEE wireless commun, 0.1 2014.21(4)：106-112. 0 2 345 6 78 「41石柯.陈洪生，张仁同.一种基于支持向量回归的802.11 定位误差m 图7 图书馆环境下的4种方法累计定位误差比较 无线室内定位方法[J].软件学报，2014,25(11)： 2636-2651. Fig.7 Cumulative localization error comparison of four SHI Ke,CHEN Hongsheng,ZHANG Rentong.Indoor location methods in library method based on support vector regression in 802.11 wireless environments[]].Journal of software,2014,25 (11 ) 1.0 2636-2651 0.8 [5]BAHL P,PADMANABHAN V.RADAR:an in-building rf- 0.7 based user location and tracking system[C]//Proc.Nineteenth 0.6 0.5 Annual Joint Conference of the IEEE Computer and 0.4 Communications Societies.Tel Aviv,Israel,2000:775-784. 0.3 RADAR HED [6]YOUSSEF M,AGRAWALA A The horus wlan location 0.2 FreeLoc HLD determination system[C]//Proceedings of the 3 International 2 3 6 78 Conferenceon Mobile Systems,Applications,and Services, 定位误差m Washington,USA,2005:205-218. 图83层教室环境下的4种方法累计定位误差比较 [7]WANG B,CHEN Q,YANG L T,et al.Indoor smartphone Fig.8 Cumulative localization error comparison of four localization via fingerprint crowdsourcing:challenges and methods in three floors classroom approaches[J].IEEE wireless communication,2016(6):

图 ６ 实验室环境下的 ４ 种方法累计定位误差比较 Ｆｉｇ．６ Ｃｕｍｕｌａｔｉｖｅ ｌｏｃａｌｉｚａｔｉｏｎ ｅｒｒｏｒ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｆｏｕｒ ｍｅｔｈｏｄｓ ｉｎ ｌａｂｏｒａｔｏｒｙ 表 ３ ３ 种实验场景下 ４ 种方法的平均误差对比 Ｔａｂ ３ Ｔｈｅ ａｖｅｒａｇｅ ｅｒｒｏｒ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｆｏｕｒ ｍｅｔｈｏｄｓ ｉｎ ｔｈｒｅｅ ｅｘｐｅｒｉｍｅｎｔ ｓｃｅｎａｒｉｏｓ ｍ 场景 ＲＡＤＡＲ ＦｒｅｅＬｏｃ ＨＥＤ ＨＬＤ 实验室 ４．２５ ３．１１ ３．５７ １．４６ 图书馆 ５．７０ ２．９７ ３．２７ １．３５ 教室 ９．５６ ５．０２ ６．７８ １．４５ 图 ７ 图书馆环境下的 ４ 种方法累计定位误差比较 Ｆｉｇ．７ Ｃｕｍｕｌａｔｉｖｅ ｌｏｃａｌｉｚａｔｉｏｎ ｅｒｒｏｒ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｆｏｕｒ ｍｅｔｈｏｄｓ ｉｎ ｌｉｂｒａｒｙ 图 ８ ３ 层教室环境下的 ４ 种方法累计定位误差比较 Ｆｉｇ．８ Ｃｕｍｕｌａｔｉｖｅ ｌｏｃａｌｉｚａｔｉｏｎ ｅｒｒｏｒ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｆｏｕｒ ｍｅｔｈｏｄｓ ｉｎ ｔｈｒｅｅ ｆｌｏｏｒｓ ｃｌａｓｓｒｏｏｍ ４ 总结 本文讨论了设备异构和室内环境变化情形下的 室内定位问题，提出了基于层次 Ｌｅｖｅｎｓｈｔｅｉｎ 距离的 ＷｉＦｉ 指纹距离计算算法。 在无校准情形下，将不同 移动设备采集的 ＲＳＳＩ 信息转化为 ＡＰ 序列，以解决 不同设备获取的 ＲＳＳＩ 信息的量纲一致性问题。 根 据 ＡＰ 对应的 ＲＳＳＩ 值的差异性计算其层次能级，结 合 Ｌｅｖｅｎｓｈｔｅｉｎ 距离计算 ＷｉＦｉ 指纹之间的距离，提供 一种适应异构设备和动态环境下计算各 ＲＰ 间指纹 距离的鲁棒性方法。 对于需定位的 ＷｉＦｉ 指纹 ＲＳＳＩ 信息，采用 ＷＫＮＮ 算法进行预测定位。 实验中，为 了验证算法的鲁棒性和有效性，在 ３ 种不同类型的 室内环境中用 ５ 种不同的移动设备来采集 ＷｉＦｉ 的 ＲＳＳＩ 信息，其定位的平均精度达 １．５ ｍ，２ ｍ 内误差 准确度在 ７０％ ～８０％，对空间维度敏感度较低。 参考文献： ［１］ＧＵ Ｙ， ＬＯ Ａ， ＮＩＥＭＥＧＥＥＲＳ Ｉ． Ａ ｓｕｒｖｅｙ ｏｆ ｉｎｄｏｏｒ ｐｏｓｉｔｉｏｎｉｎｇ ｓｙｓｔｅｍｓ ｆｏｒ ｗｉｒｅｌｅｓｓ ｐｅｒｓｏｎａｌ ｎｅｔｗｏｒｋｓ ［ Ｊ ］． ＩＥＥＥ ｃｏｍｍｕｎ． ｓｕｒｖｅｙｓ ａｎｄ ｔｕｔｏｒｉａｌｓ， ２００９，１１（１）： １３－３２． ［２］ＨＡＲＬＥ Ｒ． Ａ ｓｕｒｖｅｙ ｏｆ ｉｎｄｏｏｒ ｉｎｅｒｔｉａｌ ｐｏｓｉｔｉｏｎｉｎｇ ｓｙｓｔｅｍｓ ｆｏｒ ｐｅｄｅｓｔｒｉａｎｓ［Ｊ］． ＩＥＥＥ ｃｏｍｍｕｎ． ｓｕｒｖｅｙｓ ＆ ｔｕｔｏｒｉａｌｓ， ２０１３， １５（３）： １２８１－１２９３． ［３］ＳＵＢＢＵ Ｋ Ｐ． Ａｎａｌｙｓｉｓ ａｎｄ ｓｔａｔｕｓ ｑｕｏ ｏｆ ｓｍａｒｔ⁃ｐｈｏｎｅ⁃ｂａｓｅｄ ｉｎｄｏｏｒ ｌｏｃａｌｉｚａｔｉｏｎ ｓｙｓｔｅｍｓ ［ Ｊ ］． ＩＥＥＥ ｗｉｒｅｌｅｓｓ ｃｏｍｍｕｎ， ２０１４，２１（４）： １０６－１１２． ［４］石柯，陈洪生，张仁同．一种基于支持向量回归的 ８０２．１１ 无线室 内 定 位 方 法 ［ Ｊ ］． 软 件 学 报， ２０１４， ２５ （ １１ ）： ２６３６－２６５１． ＳＨＩ Ｋｅ， ＣＨＥＮ Ｈｏｎｇｓｈｅｎｇ， ＺＨＡＮＧ Ｒｅｎｔｏｎｇ． Ｉｎｄｏｏｒ ｌｏｃａｔｉｏｎ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｒｅｇｒｅｓｓｉｏｎ ｉｎ ８０２．１１ ｗｉｒｅｌｅｓｓ ｅｎｖｉｒｏｎｍｅｎｔｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｓｏｆｔｗａｒｅ， ２０１４， ２５ （ １１ ）： ２６３６－２６５１． ［５］ ＢＡＨＬ Ｐ， ＰＡＤＭＡＮＡＢＨＡＮ Ｖ． ＲＡＤＡＲ： ａｎ ｉｎ⁃ｂｕｉｌｄｉｎｇ ｒｆ⁃ ｂａｓｅｄ ｕｓｅｒ ｌｏｃａｔｉｏｎ ａｎｄ ｔｒａｃｋｉｎｇ ｓｙｓｔｅｍ［Ｃ］ ／ ／ Ｐｒｏｃ． Ｎｉｎｅｔｅｅｎｔｈ Ａｎｎｕａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｆ ｔｈｅ ＩＥＥＥ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｓｏｃｉｅｔｉｅｓ． Ｔｅｌ Ａｖｉｖ， Ｉｓｒａｅｌ， ２０００：７７５－７８４． ［６ ］ ＹＯＵＳＳＥＦ Ｍ， ＡＧＲＡＷＡＬＡ Ａ ． Ｔｈｅ ｈｏｒｕｓ ｗｌａｎ ｌｏｃａｔｉｏｎ ｄｅｔｅｒｍｉｎａｔｉｏｎ ｓｙｓｔｅｍ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ３ ｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅｏｎ Ｍｏｂｉｌｅ Ｓｙｓｔｅｍｓ， Ａｐｐｌｉｃａｔｉｏｎｓ， ａｎｄ Ｓｅｒｖｉｃｅｓ， Ｗａｓｈｉｎｇｔｏｎ， ＵＳＡ， ２００５： ２０５－２１８． ［７］ＷＡＮＧ Ｂ， ＣＨＥＮ Ｑ， ＹＡＮＧ Ｌ Ｔ， ｅｔ ａｌ． Ｉｎｄｏｏｒ ｓｍａｒｔｐｈｏｎｅ ｌｏｃａｌｉｚａｔｉｏｎ ｖｉａ ｆｉｎｇｅｒｐｒｉｎｔ ｃｒｏｗｄｓｏｕｒｃｉｎｇ： ｃｈａｌｌｅｎｇｅｓ ａｎｄ ａｐｐｒｏａｃｈｅｓ［ Ｊ］． ＩＥＥＥ ｗｉｒｅｌｅｓｓ ｃｏｍｍｕｎｉｃａｔｉｏｎ， ２０１６（ ６）： ·４２８· 智 能 系 统 学 报 第 １２ 卷

第3期 何富贵，等：一种层次Levenshtein距离的无指纹校准的室内定位方法 .429. 82-89 [19]YANG S.Freeloc:calibration-free crowdsourced indoor [8]TSUI A W,CHUANG Y H,CHU HH.Unsupervised localization[C]//The 32th IEEE International Conference on learning for solving rss hardware variance problem in wifi Computer Communications,Turin,Italy,2013:2481-2489. localization[J].Mobile networks and applications,2009,14 [20]JIANG Y.Ariel:automatic wi-fi based room fingerprinting (5):677-691 for indoor localization[C]//Proc ACM Conf.Ubiquitous [9]CHENG H,WANG F.TAO R,et al.Clustering algorithms Computing,Pittsburgh,Pennsylvania,United States, research for device-clustering localization[C/012 Intemational 2012:441-50. Conference on Indoor Positioning and Indoor Navigation (IPIN), [21]SHU Y,HUANG Y,ZHANG J,et al.Gradient-based Sydney,Australia,2012:1-7. fingerprinting for indoor localization and tracking[J].IEEE [10]MAHTAB HOSSAIN A,JIN Y .SOH W S,et al.SSD:a transactions on industrial electronics,2016,63(4): robust RF location fingerprint addressing mobile devices 2424-2433. heterogeneity[].IEEE transactions on mobile computing, [22]ZOU H,HUANG B,LU X,et al.Standardizing location 2013,12(1):65-77. fingerprints across heterogeneous mobile devices for indoor [11]PARK J G,CURTIS D,TELLER S,et al.Implications of localization C]//IEEE Wireless Communications and device diversity for organic localization[C]//The 30th IEEE Networking Conference WCNC 2016).Doha,Qatar, International Conference on Computer Communications, 2016:1-6. Shanghai,China,2011:3182-3190. [12]FIGUERA C,ROJO-LVAREZ J L.MORA-JIMNEZ I,et [23]GU Y,CHEN M,REN F,et al.HED:handling environ- al.Time-space sampling and mobile device calibration for mental dynamics in indoor wifi fingerprint wifi indoor location systems J].IEEE transactions on localization[C]//IEEE Wireless Communications and mobile computing,2011,10(7):913-926. Networking Conference WCNC 2016),Doha,Qatar, [13 HAEBERLEN A,FLANNERY E,LADD A M,et al. 2016:5-10. Practical robust localization over large-scale 802.11 wireless 作者简介： networks[C]//Proceedings of the 10th Annual Intemational 何富贵，男，1982年生，副教授，主 Conference on Mobile Computing and Networking, 要研究方向为移动计算、室内定位和粒 Philadelphia,USA,2004:70-84. 计算。发表学术论文10余篇。 [14 KJRGAARD M B.Indoor location fingerprinting with heterogeneous clients[.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 杨铮，男，1983年生，副教授，博 devices for fingerprinting applications[C]//2010 Intemational 士生导师，研究方向为无线网络与移动计 Conference on Indoor Positioning and Indoor Navigation 算，包括传感网、Mesh网络、室内定位、群 (IPIN),Zurich,Switzerland,2010:1-6. 智感知等。发表论文60余篇，其中CCF [16]CHEN L H WU E H K,JIN M H,et al.Homogeneous 推荐A类论文40余篇：出版中英文学术 features utilization to address the device heterogeneity 专著各1部。获得国家自然科学奖二 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 吴陈沭，男，1989年生，博士，研究 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

８２－８９． ［８］ ＴＳＵＩ Ａ Ｗ， ＣＨＵＡＮＧ Ｙ Ｈ， ＣＨＵ Ｈ Ｈ． Ｕｎｓｕｐｅｒｖｉｓｅｄ ｌｅａｒｎｉｎｇ ｆｏｒ ｓｏｌｖｉｎｇ ｒｓｓ ｈａｒｄｗａｒｅ ｖａｒｉａｎｃｅ ｐｒｏｂｌｅｍ ｉｎ ｗｉｆｉ ｌｏｃａｌｉｚａｔｉｏｎ［Ｊ］．Ｍｏｂｉｌｅ ｎｅｔｗｏｒｋｓ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ， ２００９，１４ （５）： ６７７－６９１． ［９］ ＣＨＥＮＧ Ｈ， ＷＡＮＧ Ｆ， ＴＡＯ Ｒ， ｅｔ ａｌ． Ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｒｅｓｅａｒｃｈ ｆｏｒ ｄｅｖｉｃｅ⁃ｃｌｕｓｔｅｒｉｎｇ ｌｏｃａｌｉｚａｔｉｏｎ［Ｃ］／ ／ ２０１２ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｄｏｏｒ Ｐｏｓｉｔｉｏｎｉｎｇ ａｎｄ Ｉｎｄｏｏｒ Ｎａｖｉｇａｔｉｏｎ （ＩＰＩＮ）， Ｓｙｄｎｅｙ， Ａｕｓｔｒａｌｉａ， ２０１２：１－７． ［１０］ＭＡＨＴＡＢ ＨＯＳＳＡＩＮ Ａ ， ＪＩＮ Ｙ ，ＳＯＨ Ｗ Ｓ， ｅｔ ａｌ． ＳＳＤ： ａ ｒｏｂｕｓｔ ＲＦ ｌｏｃａｔｉｏｎ ｆｉｎｇｅｒｐｒｉｎｔ ａｄｄｒｅｓｓｉｎｇ ｍｏｂｉｌｅ ｄｅｖｉｃｅｓ ｈｅｔｅｒｏｇｅｎｅｉｔｙ［Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｍｏｂｉｌｅ ｃｏｍｐｕｔｉｎｇ， ２０１３，１２（１）： ６５－７７． ［１１］ＰＡＲＫ Ｊ Ｇ， ＣＵＲＴＩＳ Ｄ， ＴＥＬＬＥＲ Ｓ， ｅｔ ａｌ． Ｉｍｐｌｉｃａｔｉｏｎｓ ｏｆ ｄｅｖｉｃｅ ｄｉｖｅｒｓｉｔｙ ｆｏｒ ｏｒｇａｎｉｃ ｌｏｃａｌｉｚａｔｉｏｎ［Ｃ］ ／ ／ Ｔｈｅ ３０ｔｈ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｓｈａｎｇｈａｉ， Ｃｈｉｎａ， ２０１１：３１８２－３１９０． ［１２］ ＦＩＧＵＥＲＡ Ｃ， ＲＯＪＯ⁃ＬＶＡＲＥＺ Ｊ Ｌ， ＭＯＲＡ⁃ＪＩＭＮＥＺ Ｉ， ｅｔ ａｌ． Ｔｉｍｅ⁃ｓｐａｃｅ ｓａｍｐｌｉｎｇ ａｎｄ ｍｏｂｉｌｅ ｄｅｖｉｃｅ ｃａｌｉｂｒａｔｉｏｎ ｆｏｒ ｗｉｆｉ ｉｎｄｏｏｒ ｌｏｃａｔｉｏｎ ｓｙｓｔｅｍｓ ［ Ｊ ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｍｏｂｉｌｅ ｃｏｍｐｕｔｉｎｇ， ２０１１，１０（７）：９１３－９２６． ［１３ ］ ＨＡＥＢＥＲＬＥＮ Ａ， ＦＬＡＮＮＥＲＹ Ｅ， ＬＡＤＤ Ａ Ｍ， ｅｔ ａｌ． Ｐｒａｃｔｉｃａｌ ｒｏｂｕｓｔ ｌｏｃａｌｉｚａｔｉｏｎ ｏｖｅｒ ｌａｒｇｅ⁃ｓｃａｌｅ ８０２．１１ ｗｉｒｅｌｅｓｓ ｎｅｔｗｏｒｋｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １０ｔｈ Ａｎｎｕａｌ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍｏｂｉｌｅ Ｃｏｍｐｕｔｉｎｇ ａｎｄ Ｎｅｔｗｏｒｋｉｎｇ， Ｐｈｉｌａｄｅｌｐｈｉａ， ＵＳＡ， ２００４： ７０－８４． ［ １４ ］ ＫＪＲＧＡＡＲＤ Ｍ Ｂ． Ｉｎｄｏｏｒ ｌｏｃａｔｉｏｎ ｆｉｎｇｅｒｐｒｉｎｔｉｎｇ ｗｉｔｈ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｃｌｉｅｎｔｓ［Ｊ］． Ｐｅｒｖａｓｉｖｅ ａｎｄ ｍｏｂｉｌｅ ｃｏｍｐｕｔｉｎｇ， ２０１１， ７（１）：３１－４３． ［１５］ＤＥＬＬＡ ＲＯＳＡ Ｆ， ＬＥＰＰＡＫＯＳＫＩ Ｈ， ＢＩＡＮＣＵＬＬＯ Ｓ， ｅｔ ａｌ． Ａｄ⁃ｈｏｃ ｎｅｔｗｏｒｋｓ ａｉｄｉｎｇ ｉｎｄｏｏｒ ｃａｌｉｂｒａｔｉｏｎｓ ｏｆ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｄｅｖｉｃｅｓ ｆｏｒ ｆｉｎｇｅｒｐｒｉｎｔｉｎｇ ａｐｐｌｉｃａｔｉｏｎｓ［Ｃ］ ／ ／ ２０１０ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｄｏｏｒ Ｐｏｓｉｔｉｏｎｉｎｇ ａｎｄ Ｉｎｄｏｏｒ Ｎａｖｉｇａｔｉｏｎ （ＩＰＩＮ）， Ｚｕｒｉｃｈ， Ｓｗｉｔｚｅｒｌａｎｄ， ２０１０： １－６． ［１６］ＣＨＥＮ Ｌ Ｈ ， ＷＵ Ｅ Ｈ Ｋ， ＪＩＮ Ｍ Ｈ， ｅｔ ａｌ． Ｈｏｍｏｇｅｎｅｏｕｓ ｆｅａｔｕｒｅｓ ｕｔｉｌｉｚａｔｉｏｎ ｔｏ ａｄｄｒｅｓｓ ｔｈｅ ｄｅｖｉｃｅ ｈｅｔｅｒｏｇｅｎｅｉｔｙ ｐｒｏｂｌｅｍ ｉｎ ｆｉｎｇｅｒｐｒｉｎｔ ｌｏｃａｌｉｚａｔｉｏｎ ［ Ｊ ］． ＩＥＥＥ ｓｅｎｓｏｒｓ ｊｏｕｒｎａｌ， ２０１４，１４（４）： ９９８－１００５． ［１７］ＺＯＵ Ｈ ， ＬＵ Ｘ ， ＪＩＡＮＧ Ｈ，ｅｔ ａｌ． Ａ ｆａｓｔ ａｎｄ ｐｒｅｃｉｓｅ ｉｎｄｏｏｒ ｌｏｃａｌｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ａｎ ｏｎｌｉｎｅ ｓｅｑｕｅｎｔｉａｌ ｅｘｔｒｅｍｅ ｌｅａｒｎｉｎｇ ｍａｃｈｉｎｅ［Ｊ］． Ｓｅｎｓｏｒｓ， ２０１５，１５（１）：１８０４－１８２４． ［１８］ＬＹＭＢＥＲＯＰＯＵＬＯＳ Ｄ， ＬＩＵ Ｊ， ＹＡＮＧ Ｘ， ｅｔ ａｌ． Ａ ｒｅａｌｉｓｔｉｃ ｅｖａｌｕａｔｉｏｎ ａｎｄ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｉｎｄｏｏｒ ｌｏｃａｔｉｏｎ ｔｅｃｈｎｏｌｏｇｉｅｓ： ｅｘｐｅｒｉｅｎｃｅｓ ａｎｄ ｌｅｓｓｏｎｓ ｌｅａｒｎｅｄ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １４ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ ｉｎ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ， Ｃａｔａｎｉａ， Ｉｔａｌｙ， ＡＣＭ， ２０１５： １７８－１８９． ［ １９ ］ ＹＡＮＧ Ｓ． Ｆｒｅｅｌｏｃ： ｃａｌｉｂｒａｔｉｏｎ⁃ｆｒｅｅ ｃｒｏｗｄｓｏｕｒｃｅｄ ｉｎｄｏｏｒ ｌｏｃａｌｉｚａｔｉｏｎ［Ｃ］ ／ ／ Ｔｈｅ ３２ｔｈ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｔｕｒｉｎ， Ｉｔａｌｙ， ２０１３： ２４８１－２４８９． ［２０］ＪＩＡＮＧ Ｙ． Ａｒｉｅｌ： ａｕｔｏｍａｔｉｃ ｗｉ－ｆｉ ｂａｓｅｄ ｒｏｏｍ ｆｉｎｇｅｒｐｒｉｎｔｉｎｇ ｆｏｒ ｉｎｄｏｏｒ ｌｏｃａｌｉｚａｔｉｏｎ［Ｃ］ ／ ／ Ｐｒｏｃ ＡＣＭ Ｃｏｎｆ． Ｕｂｉｑｕｉｔｏｕｓ Ｃｏｍｐｕｔｉｎｇ， Ｐｉｔｔｓｂｕｒｇｈ， Ｐｅｎｎｓｙｌｖａｎｉａ， Ｕｎｉｔｅｄ Ｓｔａｔｅｓ， ２０１２：４４１－５０． ［２１］ ＳＨＵ Ｙ， ＨＵＡＮＧ Ｙ， ＺＨＡＮＧ Ｊ， ｅｔ ａｌ． Ｇｒａｄｉｅｎｔ⁃ｂａｓｅｄ ｆｉｎｇｅｒｐｒｉｎｔｉｎｇ ｆｏｒ ｉｎｄｏｏｒ ｌｏｃａｌｉｚａｔｉｏｎ ａｎｄ ｔｒａｃｋｉｎｇ［Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｄｕｓｔｒｉａｌ ｅｌｅｃｔｒｏｎｉｃｓ， ２０１６， ６３ （ ４ ）： ２４２４－２４３３． ［２２］ ＺＯＵ Ｈ， ＨＵＡＮＧ Ｂ， ＬＵ Ｘ， ｅｔ ａｌ． Ｓｔａｎｄａｒｄｉｚｉｎｇ ｌｏｃａｔｉｏｎ ｆｉｎｇｅｒｐｒｉｎｔｓ ａｃｒｏｓｓ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｍｏｂｉｌｅ ｄｅｖｉｃｅｓ ｆｏｒ ｉｎｄｏｏｒ ｌｏｃａｌｉｚａｔｉｏｎ ［ Ｃ ］ ／ ／ ＩＥＥＥ Ｗｉｒｅｌｅｓｓ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ａｎｄ Ｎｅｔｗｏｒｋｉｎｇ Ｃｏｎｆｅｒｅｎｃｅ （ ＷＣＮＣ ２０１６ ）． Ｄｏｈａ， Ｑａｔａｒ， ２０１６：１－６． ［２３］ＧＵ Ｙ， ＣＨＥＮ Ｍ， ＲＥＮ Ｆ， ｅｔ ａｌ． ＨＥＤ： ｈａｎｄｌｉｎｇ ｅｎｖｉｒｏｎ⁃ ｍｅｎｔａｌ ｄｙｎａｍｉｃｓ ｉｎ ｉｎｄｏｏｒ ｗｉｆｉ ｆｉｎｇｅｒｐｒｉｎｔ ｌｏｃａｌｉｚａｔｉｏｎ［Ｃ］ ／ ／ ＩＥＥＥ Ｗｉｒｅｌｅｓｓ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ａｎｄ Ｎｅｔｗｏｒｋｉｎｇ Ｃｏｎｆｅｒｅｎｃｅ （ ＷＣＮＣ ２０１６ ）， Ｄｏｈａ， Ｑａｔａｒ， ２０１６： ５－１０． 作者简介： 何富贵，男，１９８２ 年生，副教授，主 要研究方向为移动计算、室内定位和粒 计算。 发表学术论文 １０ 余篇。 杨铮，男，１９８３ 年生，副教授，博 士生导师，研究方向为无线网络与移动计 算，包括传感网、Ｍｅｓｈ 网络、室内定位、群 智感知等。 发表论文 ６０ 余篇，其中 ＣＣＦ 推荐 Ａ 类论文 ４０ 余篇；出版中、英文学术 专著各 １ 部。 获得国家自然科学奖二 等奖。 吴陈沭，男，１９８９ 年生，博士，研究 方向为无线网络与移动计算，包括室内 定位、群智感知等。 第 ３ 期 何富贵，等：一种层次 Ｌｅｖｅｎｓｈｔｅｉｎ 距离的无指纹校准的室内定位方法 ·４２９·