基于群智感知的无线室内定位-博士学位论文

基于群智感知的无线室内定位 申请清华大学工学博士学位论文 培 养 单 位 计算机科学与技术系 学科 计算机科学与技术 研究生 吴 陈 沭 指 导 教 师 刘 云 浩 教 授 二 一五 年 六 月 Wireless Indoor Localization via Crowdsensing Dissertation Submitted to Tsinghua University in partial fulfi llment of the requirement for the degree of Doctor of Philosophy by Wu Chenshu Computer Science and Technology Dissertation Supervisor Professor Liu Yunhao June 2015 关于学位论文使用授权的说明 本人完全了解清华大学有关保留 使用学位论文的规定 即 清华大学拥有在著作权法规定范围内学位论文的使用权 其中 包括 1 已获学位的研究生必须按学校规定提交学位论文 学校 可以采用影印 缩印或其他复制手段保存研究生上交的学位论文 2 为教学和科研目的 学校可以将公开的学位论文作为资料在图 书馆 资料室等场所供校内师生阅读 或在校园网上供校内师生浏览 部分内容 3 根据 中华人民共和国学位条例暂行实施办法 向国家图书馆报送可以公开的学位论文 本人保证遵守上述规定 保保保密密密的的的论论论文文文在在在解解解密密密后后后应应应遵遵遵守守守此此此规规规定定定 作者签名 导师签名 日期 日期 摘要 摘要 位置信息 是移动互联网的最基本要素 是物联网中最重要的感知信息 和 人们的生产生活密切相关 人类80 以上的时间在室内环境中活动 致使室内定 位市场蓬勃发展 需求持续攀升 近十五年来 各种各样的室内定位技术层出不 穷 无线网络的大范围覆盖和移动设备的全球性普及 令基于WiFi的智能手机定 位逐渐被广泛认可和采纳 但迄今为止尚无任何一种主导室内的全球性 全天候 定位服务 目前最主流的WiFi指纹定位方法在实际应用中也面临着诸多挑战 指 纹定位中不可缺失的人工现场勘测环节导致系统部署代价居高不下 长期部署过 程中静态的指纹地图无法适应动态的环境变化导致精度下降 在移动环境中定位 精度有限性能不稳 等等 针对WiFi指纹定位的上述指纹地图构建难 指纹地图 更新弱 位置估计精度低三大问题 本论文研究基于群智感知的无线室内定位理 论与方法 设计低硬件成本 低部署成本 低维护成本的高精度定位 使得室内 定位在实际应用中大规模部署 长时间运行 高精度定位成为可能 具体来说 本文的主要研究内容和创新成果包括 1 无线信号指纹地图的自动构建 利用移动群智感知的思想 应用大量普通 用户的移动性 设计无线信号指纹地图自动构建技术 将原本需要专业人 士持专用设备执行专门任务才能完成的现场勘测任务 通过大量普通用户 以普通设备无意识参与的方式得以完成 成功取消了指纹定位中耗时费力 的人工现场勘测环节 大幅降低了指纹定位方法的部署代价 真实环境中 的实验验证了自动构建的指纹地图与人工勘测的性能相当 2 无线信号指纹地图的自适应更新 通过对移动用户日常行为规律的分析 利用普通移动设备的 静止性 将其作为可移动参考节点用于收集实时指纹 数据 并提出了路径匹配算法来获取可移动参考点的精确位置 基于这些 数据 通过建模相邻位置的指纹之间的关系模型更新整个指纹地图 所提 出的方法无需额外的硬件部署和人力成本 实现了指纹地图自动 及时 连续的更新 使得静态构建的指纹地图能够动态适应长期运行过程中可能 产生的环境变化 实验结果自适应更新的地图的有效性和准确性 证明由 此带来的精度比使用静态指纹地图提升近两倍 3 移动环境下的高精度定位算法 深入探索和分析了造成移动环境下智能 手机定位精度低劣的深层次原因 发现了造成指纹定位误差但此前却未受 重视甚至未被发现的AP表征能力差异性 指纹不一致性 指纹 错位 现象 I 摘要 三大问题 针对这些问题 论文设计了一套适用于智能移动终端的指纹生 成 描述与匹配算法 其中定义了表征因子来量化不同AP的表征能力 应 用稳健回归技术对抗异常指纹的误匹配问题 提出 幻影指纹 克服移动设备 上的指纹伪新和错位问题 实际环境中的实验结果表明该算法相比于多种 传统方法定位误差降低了一半以上 关键词 位置 室内定位 指纹 智能手机 群智感知 II Abstract Abstract Location contexts act as a primary element of mobile internet and a fundamental type of sensing data for Internet of Things and thus plays a crucial role in our every day life People spend more than 80 of their time indoors stimulating the fl ourish ing markets and increasing demand of Location based Services LBS During the past decades various indoor location technologies have been proposed WiFi based localiza tion for smartphones among others becomes attractive and popular thanks to the wide availability of wireless networks as well as the global popularization of smartphones A predominant location system that provides worldwide and round the clock services how ever still lacks Even the mainstream WiFi fi ngerprint based scheme encounters critical challenges in practice Particularly its applicability is extremely limited by severe draw backs including high deployment costs due to the cumbersome site survey biased radio maps caused by environmental dynamics especially during long term running and unsat isfactory performance in mobile environments etc This dissertation targets at the above problems and studies crowdsensing based wireless indoor localization by designing a high accuracy system at low hardware costs low deployment costs and low maintenance costs which enables wireless indoor localization deployable at large scale runnable over long term and applicable with high accuracy In summary the major results and core contributions are as follows 1 Automatic construction of radio maps Leveraging crowdsensed user mobility we design an automatic method for radio map construction method which eliminates the eff orts of time consuming and labor intensive site survey by the participatory sensing of a number of mobile users The proposed scheme signifi cantly decreases the deployment costs of fi ngerprint based localization Results from real experi ments demonstrate that comparable performance can be achieved by automatically built radio maps compared with manually calibrated ones 2 Adaptable self updating of radio maps An automatic and continuous radio map self updating service is proposed for wireless indoor localization which exploits the static behaviors of mobile devices By accurately pinpointing mobile devices with a novel trajectory matching algorithm we employ them as mobile reference points to collect real time RSS samples when they are static With these fresh refer III Abstract ence data the complete radio map is adapted by learning an underlying relationship of RSS dependency between nerghboring locations which is expected to be rela tively constant over time The eff ectiveness is validated through real experiments which show 2 improvement in location accuracy by appropriately adapting the radio maps 3 An accurate localization algorithm for mobile environments This dissertation in vestigates fi ngerprint based localization in mobile environments and reveals crucial observations that act as the root causes of location errors yet are surprisingly over looked or not adequately addressed previously Specifi cally we recognize APs diverse discrimination for fi ngerprinting a specifi c location observe the RSS in consistency caused by signal fl uctuations and human body blockages and uncover the transitional fi ngerprint problem on commodity smartphones Inspired by these insights we devise a unifi ed scheme of fi ngerprint generation representation and matching for mobile devices which defi nes a discrimination factor to quantify dif ferent APs discrimination incorporates robust regression to tolerate outlier mea surements and reassembles diff erent normal fi ngerprints to cope with transitional fi ngerprints Extensive experiments validate that the location errors are decreased by more than 50 compared to several state of the art schemes Key words Location Indoor Localization Fingerprint Smartphones Crowdsensing IV 目录 目录 第 1 章绪论 1 1 1研究背景与意义 1 1 2研究问题与现状 3 1 3研究内容与贡献 7 1 4论文结构 9 第 2 章相关研究工作 10 2 1无线室内定位技术原理 10 2 1 1基于测距的室内定位 10 2 1 2基于指纹的室内定位 12 2 2无线指纹地图的自动构建 13 2 2 1基于群智感知的指纹地图自动构建 13 2 2 2同时定位与地图创建技术 14 2 3无线指纹地图的自适应更新 14 2 4高精度的无线室内定位技术 15 2 5移动计算中的群智感知 17 2 6小结 19 第 3 章无线信号指纹地图自动构建 20 3 1引言 20 3 2方法概述 22 3 2 1数据收集 22 3 2 2方法架构 23 3 3无应力平面图与指纹空间 24 3 3 1无应力平面图的生成 24 3 3 2指纹空间的构建 26 3 4空间映射 31 3 4 1特征抽取 31 3 4 2参考点提取与匹配 33 3 4 3空间变换 34 3 5实验验证与性能评估 35 3 5 1实验设置 35 3 5 2性能评估 36 3 6讨论与展望 40 3 6 1建筑类型 41 V 目录 3 6 2设备异质性 41 3 6 3全局参考点与多楼层问题 42 3 6 4室内平面图自动构建 42 3 7小结 42 第 4 章无线信号指纹地图自适应更新 44 4 1引言 44 4 2背景知识与测量分析 46 4 2 1RSS波动性测量 46 4 2 2基于参考点的指纹地图更新 47 4 3问题挑战与算法概述 48 4 4指纹地图自适应更新算法设计 49 4 4 1大头针数据收集 50 4 4 2基于路径匹配的参考点位置估计 53 4 4 3近邻RSS关系模型与指纹地图更新 55 4 5实验验证与性能评估 57 4 5 1实验设置 57 4 5 2性能评估 59 4 6讨论与展望 62 4 7小结 64 第 5 章移动环境下的高精度定位算法 66 5 1引言 66 5 2问题描述与测量 68 5 2 1问题描述 68 5 2 2测量与观察 69 5 3DorFin算法设计 73 5 3 1表征因子 74 5 3 2幻影指纹 75 5 3 3稳健回归 77 5 3 4指纹匹配 79 5 4实验验证与性能评估 79 5 4 1实验环境 79 5 4 2性能评估 82 5 4 3原型系统实施 87 5 5讨论与展望 88 5 6小结 89 VI 目录 第 6 章结论与展望 90 6 1工作总结 90 6 2研究展望 91 参考文献 93 致谢 102 声明 104 个人简历 在学期间发表的学术论文与研究成果 105 VII 主要符号对照表 主要符号对照表 LBS基于位置的服务 Location based Services GPS全球定位系统 Global Positioning System RSS接收信号强度 Received Signal Strength WLAN无线局域网 Wireless Local Area Network CSI信道状态信息 Channel State Information MEMS微机电系统 Micro Electro Mechanical System IMU惯性感知单元 Inertial Measurement Unit AP无线热点 Access Point KNNK近邻 K Nearest Neighbors MDS多维标度法 Multidimensional Scaling FSM有限状态机 Finite State Machine PLSR偏最小二乘回归 Partial Least Square Regression RSD RSS差 RSS Diff erence LMS最小中值方差 Least Median Square VIII 第 1 章 绪论 第1章绪论 1 1研究背景与意义 位置 与人类社会的生产生活息息相关 自 2010 年以来 伴随传统网络向 物理世界延伸的大趋势 位置信息成为物联网最基础的感知信息 是沟通物理 世界和数字世界的桥梁 近年来 移动互联网的异军突起 也令位置信息的关 键作用愈发凸显 2011 年 著名风险投资公司 KPCB Kleiner Perkins Caufi eld 3 4 2 fi pk i 1 3 5 其中 1和 2只有一种映射方式是符合真实情况的 我们利用无应力平面图 33 第 3 章 无线信号指纹地图自动构建 和指纹空间中均能体现的关键点间的间距约束来消除映射方式的二义性 定 义无应力平面图上关键参考点之间的距离间距为l l1 l2 lk 1 其中li pi 1 pi 同样的 指纹空间中关键参考点的间距l 定义为l l 1 l 2 l k 1 and l i fi 1 fi li与l i的值分别根据距离矩阵D与D 确定 则l和l 的余弦相似度为 s1 l l l l 3 6 类似地 l和逆序后的l 之间的余弦相似度记作s2 如果s1 s2 则 1更可能是真 实的映射 反之 则应采取 2映射 不失一般性 在本章后续讨论中默认将 1选 作较佳映射方式 确定映射方式之后 就得到了一组指纹 FD 的位置标签 PD 关键参考 点的映射将进一步用于标注所有其他指纹的真实位置 3 4 3空间变换 本小节讨论通过楼层级变换和房间级变换将指纹 指纹空间中的点 与位置 无应力平面图上的点 最终映射到一起 从图3 6和图3 12所示无应力平面图和 指纹空间的可视化结果可见 他们在结构上除了微小的平移和旋转以外 整体呈 现极高的相似性 我们采用变换矩阵来寻找他们之间点到点的映射关系 设指纹fi FD的坐标为xi x1 i x2 i xd i T 其中d是指纹空间的维度 fi在无 应力平面图中对应的位置pi PD的坐标为yi y1 i y2 i yd i T 记A为d d的变换矩 阵 B b1b2 bd T 可得k FD 个形式如下的等式 yi Axi B 3 7 上述k个等式可以重写为 Hiz Gi 3 8 其中Hi xT i 1 z A B T Gi yT i 将k个等式写成矩阵形式 有 Hz G 3 9 其中 Hi和Gi分别为H和G的第ith行 根据最小二乘法求解上述k个等式 得到最 小化 G Hz 的解析解为 z HTH 1HTG 3 10 由此 变换矩阵A和B可以从 z得到 从而可以将指纹空间中的任意指纹映射到无 应力平面图的固定位置上 对坐标为x x1x2 xd T的指纹f 它所对应的采样 34 第 3 章 无线信号指纹地图自动构建 位置即为无应力平面图上坐标最接近Ax B的采样点位置 3 4 3 1楼层级变换 然而 如果在楼层级做整体变换 其误差往往较大 指纹映射精度受限 因 此 我们提出房间级的变换 进一步提升映射效果 前文已有提及 房间门和来 自其附近的指纹之间以关键参考点的形式相互关联 这意味着某一个房间的位置 与来自该房间的指纹之间也可以相互关联到一起 因为每一扇门仅属于一个房 间 换言之 门到房间的映射是单射 这使得我们不仅可以进行楼层级映射 还可以进一步在房间级别做更精准的映射 利用MDS算法 来自同一个房间内部的指纹可以变换到某个d维空间中 同 样 来自对应房间的采样位置也可以映射到d维无应力空间中 利用房间门与房 间角落作为参考点 采用与楼层级变换相同的变换方式 可以实现某一个房间的 采样位置与来自该房间的指纹之间的映射 对无应力平面图中的每一个房间都重 复这个步骤 最终通过多次房间级变换得到所有指纹的位置标注 3 5实验验证与性能评估 3 5 1实验设置 我们在越来越流行的安卓操作系统上开发了LiFS的原型 利用Google Nexus S手机进行实验数据采集 实验在清华大学的一栋典型的校园办公楼中进行 定 位区域总长约70米宽约23米 覆盖面积约1600平方米 如图3 2所示 实验区域 包括16间办公室 其中5间大房间面积约为140平方米 7间小房间 此外四间房 间为仓库 机房等普通用户禁止进入的房间 实验区域一共有26个无线AP 其 中15个已知位置的已标注在图3 2中 但需要注意的是 本章所提出的方法完全不 依赖AP位置 首先 我们以大约每4平方米一个采样点 即2 2米大小的网格 对定位区 域进行采样 在所有开放区域内共设置292个采样点 尽管对于不同区域不同的 位置精度需求 应该采用不同的采样密度 但采用一个典型的采样密度能够为大 部分应用场景提供足够的精度 随后 我们应用MDS算法得到无应力平面图 其 在二维和三维上的可视化结果已经呈现在图3 5和图3 6中 实验由4位志愿用户在两天内进行了总长达5个小时的数据收集 每位志愿用 户手持智能手机在定位区域内行走 LiFS程序则在后台自动记录加速度数据以计 算步数 并采集移动路径沿途的RSS指纹 加速度传感器有两种工作模式 当检 测到用户在移动时 以高频率感知惯性数据 否则 采用较低的采样频率 用来 35 第 3 章 无线信号指纹地图自动构建 051015 0 0 2 0 4 0 6 0 8 1 Error m Percent of training fingerprints 20 30 40 50 60 70 80 90 100 图 3 15不同指纹相似度阈值 下的位 置误差CDF 20406080100 0 10 20 30 40 50 Error room rate 20406080100 0 400 800 1200 1600 2000 Point number Room error Point number 图3 16房间误差与指纹相似度阈值 的 关系 监测用户是否移动 而RSS指纹则仅在检测到用户移动时记录 采样频率大约 为0 5Hz 实验一共收集了600多条用户路径 共计16498条指纹记录 不同的路径长短 不一 所覆盖的区域也各不相同 所有用户路径大致覆盖了实验楼层的全部公共 区域 每个小房间至少有5条路径覆盖 而大房间则至少10条路径穿过 此外 有超过500路径均经过走廊 原始数据经过基本的平滑等预处理 其中一半用于 训练阶段 即用于构建指纹数据库 剩余一半用于运行阶段的查询以测试自动的 指纹地图的性能 3 5 2性能评估 3 5 2 1指纹空间生成效果 指纹空间的每一个点实际上包含多条指纹 具有高RSS相似度的指纹被归为 同一个点 而差异较大的两条指纹则分别被归到不同点上 由于用户移动路径在 室内环境下不可避免会有交叉 因此来自不同路径上的指纹可能实际上属于同一 个点 同时由于RSS自身的波动性 来自同一个位置的指纹测量反而可能被归到 不同的点上 因此 指纹相似度阈值 在指纹空间生成中影响甚巨 为计算一个合适的 值 我们首先收集来自同一个位置不同时刻的指纹数据 并计算这些指纹相互之间的最大不相似度 随机选择多个位置重复此步骤 最 后 的值设定为这些位置各自的指纹最大不相似度的平均值 这代表了定位区域 内某一个位置上指纹最大不相似度的平均水平 我们定义位置误差 Location Error 与房间误差 Room Error 来评估指纹 不相似度阈值 的有效性 Location Error L f L f 3 11 36 第 3 章 无线信号指纹地图自动构建 图 3 17基于介数中心性抽取出的候选 走廊数据点的最小生成树 图 3 18走廊数据点的最小生成树 Room Error 1 N f F I R f R f 3 12 其中f表示一条指纹 L f R f 与L f R f 则表示指纹f在物理空间中对 应的真实位置 房间 F表示指纹集合 I则是一个取值0或1的示性函数 在 指纹空间中隶属于同一个点的多条指纹 他们将被标注为相同的真实位置 房 间 位 置 误 差 的 累 积 分 布 函 数 Cumulative Distribution Function CDF 如 图3 15所示 对房间误差和指纹空间规模大小的影响如图3 16所示 由图可 见 随着 从10到100逐渐增大 位置误差与房间误差均逐渐增大 而指纹空间中 的点数在从1600降到1 过大或过小的 会造成指纹点聚类效果下降 本章后续的 实验中 我们采用 30 此时80 以上的指纹的都可以被正确聚类 作为数据预处理的另外一个重要步骤 基于加速度传感器的本地阈值计步方 法也在真实数据下进行了评估 采用不同长度的路径 从5步到200步 进行的实 验结果表明 计步的误差可以控制在2 以内 进一步 为了测试在长路径下的 性能 我们收集了不同用户走动300步所产生的加速度数据进行测试 步行过程 中 用户的手机可能拿在手上 也可能放在兜里或背包里 实验结果表明90 的 测试路径计步误差在5步以内这个精度足以支撑LiFS所需的距离估计 最终 以 30为阈值 共产生795个数据点 构成指纹空间 赋予这些数 据点相互之间的步行距离 运行Floyd Warshall最短路径算法 得到所有指纹点对 之间的距离 所生成的指纹空间在二维和三维情况下的结构如图3 11及图3 12所 示 3 5 2 2指纹地图构建误差 指纹空间的最小生成树如图3 13所示 计算其中每个点的介数中心性 按 大小排序后如图3 14所示 从中筛选出大于介数中心性阈值 在本章实验中 37 第 3 章 无线信号指纹地图自动构建 30 20 10 0 10 20 20 10 0 10 10 5 0 5 10 15 图 3 19对移除走廊数据点之后的指纹 空间进行k均值聚类得到的结果 20 1001020 5 0 5 Corridors in floor plan 20 15 10 5051015 5 0 5 10 Recognized corridors in fingerprint space 图 3 20室内平面图走廊与推断的指纹 空间走廊数据点 带有 X 标记的点为关 键参考点 取8000 的点 作为走廊数据点的候选 如图3 17所示 大部分走廊的数据点均 被正确地筛选出来 但有一部分房间的点则混在其中 且少量来自走廊的数据点 则没有被包含进来 为此 我们迭代式地生成最小生成树并过滤掉那些介数中心 性较低的点 直到所有候选点形成的最小生成树是一条直线 其依据是实验中的 无应力平面图中走廊是没有分叉的一条直线 即在最小生成树中每个点只有最 多一个父节点和最多一个子节点 最终筛选出来的走廊数据点如图3 18所示 剩余的指纹数据点大部分都收集自房间 采用k均值聚类算法将他们聚 成12类 对应12个真实平面图上的房间 聚类结果如图3 19 其中不同的颜色 表示一个类 如图可见 大部分房间对应的指纹点都被正确识别和区分出来了 只要少量走廊的数据点混淆在内 对 于 每 一 个 聚 类 寻 找 走 廊 中 的 一 个 指 纹 点 使 得 其 到 该 类 中 所 有 点 的 指 纹 距 离 最 短 由 此 选 出 的12个 类 的12个 关 键 参 考 点 如 图 3 20所 示 图 3 20也 给 出 了 室 内 平 面 图 上 连 接 房 间 和 走 廊 的 关 键 点 具 体 地 室 内 平 面 图 与 指 纹 空 间 的 关 键 参 考 点 序 列 的 间 距 依 次 为l 2 37 3 36 9 40 1 18 1 16 8 07 1 17 3 82 2 51 2 55 1 25 和 l 0 33 2 12 12 98 1 31 1 31 10 17 1 24 10 17 1 24 5 99 3 69 1 18 0 令l 为l 的逆 序序列 则l与l 和l与l 的余弦相似度分别为 s1 0 97 和 s2 0 67 由于 s1 s2 推测l 是与真实平面图上走廊正确对应的序列 接下来 根据已经得到的物理平面图的房间与指纹空间的聚类之间的一一对 应关系 进行房间级别的空间变换 图3 21呈现了在二维空间中指纹聚类与各个 房间的对应关系 其中蓝色的奇数列均表示无应力平面图中各个房间 及走廊 内的位置采样在二维平面内的MDS结果 彩色偶数列的图则表示指纹空间中各个 聚类的指纹点通过MDS生成的二维分布 由图可见 二维空间中MDS生成的无应 38 第 3 章 无线信号指纹地图自动构建 202 1 0 1 Room121 202 2 0 2 Cluster1 202 2 0 2 Room115 4 2024 2 0 2 Cluster2 202 1 0 1 Room110 50510 2 0 2 Cluster3 202 2 0 2 Room117 4 2024 2 0 2 Cluster4 202 1 0 1 Room102 505 2 0 2 Cluster5 202 1 0 1 Room108 4 2024 2 0 2 Cluster6 202 1 0 1 Room120 4 202 2 0 2 Cluster7 202 2 0 2 Room112 4 202 2 0 2 Cluster8 202 1 0 1 Room101 202 1 0 1 Cluster9 202 2 0 2 Room105 4 2024 2 0 2 Cluster10 202 1 0 1 Room116 4 2024 6 4 2 0 2 Cluster11 202 2 0 2 Room107 4 2024 2 0 2 Cluster12 15 10 5051015 1 0 1 Corridor in floor plan 15 10 5051015 1 0 1 Corridor in fingerprint space 图 3 21指纹聚类与物理房间 力平面图与原始的室内平面图一致 而二维指纹空间中的点 特别是那些来自小 房间的点 则相对紊乱 这是因为同一个指纹聚类中的数据点实际上可能来自于 不止一个房间 而这些数据点相互之间的距离度量本身又伴有误差 指纹聚类中的点到对应房间的采样位置的映射通过选取最近邻居点的方式完 成 如图3 22所示 96 以上的数据点映射误差都在4米以内 而平均映射误差仅 为1 33米 由于室内平面图的位置采样密度是 2m 2m 这个平均误差实际上小于 采样间隔 这表明通过空间映射自动构建的指纹地图可以达到与人工勘测的版本 相当的效果 可以在实际中应用 3 5 2 3定位误差 我们通过实验测试和对比了相同定位算法在使用自动构建的指纹地图和人工 勘测的指纹地图时的性能差异 定位误差由两个具体指标来衡量 位置误差和房 间误差 其中 位置误差是指位置估计与真实位置之间的欧氏距离 房间误差则 指的是指纹被关联到的房间与真实对应房间不一致的指纹占全部指纹的比例 评 价定位误差时 RSS波动性以及指纹地图构建的误差的影响也都被包含在内 我 们根据真实采集的数据生成了8249次位置查询 每次查询包含一条指纹而LiFS对 每条查询均返回一个位置估计 39 第 3 章 无线信号指纹地图自动构建 0481216 0 0 2 0 4 0 6 0 8 1 Error m Percent of fingerprint points 图 3 22空间映射误差CDF 由于LiFS主要关注自动构建的指纹数据库是否能达到与人工勘测的指纹数据 库相当的定位精度造成 而非定位算法带来的精度提升 故我们在实验中采用 经典的指纹定位算法RADAR 分别比较基于LiFS自动构建和人工勘测的指纹地 图的定位效果 如图3 23所示 LiFS的房间区分误差仅10 91 从图3 23还可以 看出 采用LiFS自动构建的指纹数据库 定位误差为5 88米 80 以上的定位误 差均小于9米 而60 以上误差均小于6米 尽管这个平均误差大于采用人工勘测 指纹地图的平均误差 3 42米 但与此前许多最新的定位方法均相当 23 且这 个精度水平是合情合理的 因为自动构建的指纹地图必然包含一部分误差而不 如人工勘测的指纹地图精确 但同时又是令人诧异的 因为LiFS完全不需要专 门的人工现场勘测 也不需要额外的硬件 却自动构建出了与人工勘测指纹地 图性能相当的指纹地图 更可喜的是 如果部署更高级精确的定位算法 定位 精度有望得到大幅提升 例如我们初步测试了基于连续移动路径匹配 trajectory matching 的定位算法 记作LiFS TM 即使采用用户的历史移动轨迹的时序 数据而非单个位置的一条查询指纹来定位用户的当前位置 基于路径匹配的定位 算法在本文第4中还会详细提到 本章不复作细致说明 图3 24显示了在自动构建 的指纹地图上应用连续路径匹配算法的基本性能 可以看到 平均定位误差降到 了2米而最大误差则被限制在8米以内 跟基于单条指纹匹配的方法相比 分别降 低了60 和50 表格3 2进一步对比了LiFS与同期其他相关的定位系统各方面的 优缺点 可以看出LiFS的系统依赖较小 且仅需要少量的传感器 事实上 只需 加速度传感器 而精度却与其他算法不相上下 这个结果更加有力表明了LiFS自 动构建出的指纹地图可以取代人工勘测的指纹地图 满足实际的定位需求 3 6讨论与展望 本小节讨论LiFS在实际应用中面临的一些局限性以及可能的解决思路 40 第 3 章 无线信号指纹地图自动构建 0 369121518 0 0 2 0 4 0 6 0 8 1 Error m Percent of queries LiFS RADAR 图 3 23RADAR算法在LiFS自动构建 的指纹地图 LiFS 和人工构建的指 纹地图 RADAR 上的定位误差CDF 024681012 0 0 2 0 4 0 6 0 8 1 Error m CDF LiFS TM RADAR 图 3 24在LiFS自动构建的指纹地图 应用连续路径匹配算法 LiFS TM 和RADAR算法 RADAR 的定位性能 表 3 2LiFS与其他定位系统的比较 属性 方法EZ 6 Zee 52 Unloc 53 LiFS 方法类别测距指纹指纹指纹 传感器 GPSA G CGPS A M G CA 依赖室内平面图否是否是 考虑设备多样性是否否否 实验区域 整个建筑 办公建筑 仅走廊 办公建筑 整个建筑 办公与商场 整个建筑 办公建筑 报告中值精度 2米 小区域 7米 大区域 7米 Horus based 1 7米 4 5m LiFS 1 5m LiFS TM 报告 80 精度 3 3米 小区域 10米 大区域 13米 Horus based 3 5米 7m LiFS 3 5m LiFS TM A Accelerometer G Gyroscope C Compass M Magnetometer 3 6 1建筑类型 本章进行实验的区域是典型的现代教学楼 这种建筑的结构特点是中间的走 廊连接着两旁的办公室 基于这样的平面结构 我们应用用户的移动路径来识别 走廊和房间 这种方案适用于绝大多数现代办公楼宇 但在一些大型开放建筑中 可能会失效 比如音乐厅 体育馆 博物馆等在这些地方 用户的移动特性 更难捕捉和建模 在未来工作中 尝试识别不同功能的区域 进行根据用户在该 区域内的行为特点建立相应的移动模型 有望拓展LiFS在这些开阔区域的应用 3 6 2设备异质性 设备异质性是所有WiFi定位方法长期面临的一个巨大挑战 即使处在相同的 无线环境下 不同的设备由于硬件差异所测量的无线信号也会有所不同 在移动 41 第 3 章 无线信号指纹地图自动构建 群智应用中 大量用户使用多种多样的设备参与数据收集 这个问题变得更加突 出 在本章的研究中 得益于用户的移动性可以视为无线信号指纹之外一个新的 信息维度 LiFS对设备差异的容忍性优于传统工作 但必须承认的是 设备异质 性的问题在目前的实现中尚未得到解决 未来需要在这个问题上作进一步的探 究 3 6 3全局参考点与多楼层问题 全局参考点包括手机最近一次上报的GPS坐标 AP位置 具有独特特征的区 域等 尽管在LiFS的设计中没有考虑全局参考点 LiFS的运行也不需要参考点的 支撑 但是全局参考点可以用以辅助LiFS以保障更精确和鲁棒的映射结果 全局 参考点同时也是LiFS在完全对称的建筑或者定位场景包含多个楼层的情形下得以 应用的关键突破点 由于用户自动收集的指纹可能来自不同楼层 因此结合全局 参考点以及一些现有的工作如SkyLoc 103 可以自动区分楼层 近期的一些研究工 作表明 用户利用电梯 扶梯或者楼梯上下楼层的移动行为可以被惯性传感器捕 捉并通过复杂的算法检测出来 53 104 105 在实际应用中 LiFS可以集成这些技术 来确定指纹数据是否来自同一个楼层 3 6 4室内平面图自动构建 室内平面图在许多普适和移动应用中都是非常基础的信息 然而室内平面图 的在线收集却并不方便 甚至可以说代价昂贵 例如百度地图在推广室内地图服 务时 均是派遣专门的工程人员结合自动化软件逐一绘制特定建筑的室内平面 图 结合以人为中心的感知和群智感知计算 或许有望实现室内平面图的自动构 建 近期的一些工作已经在这方面做出了探索 54 55 106 其基本思想是 大量用户 的移动数据可以反映出室内建筑的平面结构 同时 由于用户在不同区域 比如 楼梯 走廊 电梯 办公室 咖啡屋 餐厅等 的行为特征各不相同 因此融合 智能手机丰富的感知信息可以进一步判别不同区域的功能 这些高层次的语义信 息无疑将赋予基于位置的服务更广阔的想象空间 3 7小结 本章介绍了一种基于群智感知思想的室内定位指纹地图自动构建技术LiFS 其核心是利用用户移动性反映出来的RSS指纹的空间地理关联性 构建具有移动 距离约束的指纹空间 在此基础之上 设计和部署了一套基于商用WiFi架构和普 通智能手机的定位系统 所开发的原型系统在真实环境下的实验结果表明 所提 42 第 3 章 无线信号指纹地图自动构建 出的方法将原本需要专业人士持专用设备专门进行的人工现场勘测 通过大量普 通用户的移动设备在无意识参与的情况下自动完成 实现了在极低人力投入的情 况下迅速部署室内定位系统 并保障可观的定位精度 本章的研究工作突破了指 纹定位在实际中大规模部署的最大软肋 同时也为未来无线指纹定位方法提供了 一种新的研究思路 43 第 4 章 无线信号指纹地图自适应更新 第4章无线信号指纹地图自适应更新 无线室内定位的一个基础性挑战就是对抗环境的动态变化 近些年来 无线 指纹定位得到了广泛的研究 但针对长期部署中指纹地图对环境变化的适应和 更新问题的研究尚很匮乏 本章提出一种自动和连续的指纹地图自适应更新算 法AcMu 本章首先介绍指纹地图动态更新的基本方式和基本原理 然后从移动 设备的静止形态出发 将处于静止的移动设备作为可移动参考点 用于收集实时 指纹数据 继而通过建模相邻位置的指纹之间的依赖关系 得到近邻指纹关系模 型 并基于此模型更新整个指纹地图 本章最后描述了跨时6个月的实验测量 实验结果验证了AcMu的有效性和准确性 4 1引言 无线室内定位技术发展到今天 所面临的基础难题 包括现场勘测代价高 昂 定位精度低劣等问题都得到深入而全面的研究和探讨 大量的原创工作先 后涌现 例如 对于现场勘测的问题 在本文上一章提到的许多研究工作 包 括LiFS 已经初步证实了通过群智感知的方式自动完成指纹地图构建的可行性 对于精度的短板 许多研究工作借助智能手机惯性传感器捕获的用户移动性 或 者利用手机之间的协作配合 成功将实验精度提高到米级甚至亚米级 24 25 70 本 文第5章将着重介绍无线指纹定位的精度问题 这些工作使得无线指纹定位渐 趋成熟可用 但在走向真正实用之前 有一个关键问题尚待进一步解决 即指纹 地图在长期部署中的更新问题 室内环境不是一成不变的 而环境变化会对无线信号传播造成强烈的影响 环境的动态性既包括如房门开关 用户移动等短短短时时时干干干扰扰扰 也包括诸如光照 温 度 湿度及其它天气条件改变而造成的长长长期期期变变变化化化 RSS对环境变化十分敏感 在微小的环境变动下也可能发生显著的幅值波动 而无线信号在复杂的室内环 境下密集的多径传播更加剧了这种波动程度 因此 在定位运行阶段实时测量 的RSS指纹可能会偏离训练阶段构建的初始指纹地图 换言之 在长期运行过程 中 初始构建的静态指纹地图会因为不能适应动态的环境变化而逐渐偏离实时指 纹甚至最后失效 其结果是定位系统的定位精度随着时间的推移而大幅降低 解决这个问题的一种直观思路是定期重复执行训练阶段进行的现场勘测重新构 建指纹数据库 很显然 这种方式过于笨重 耗时费力 可行性太低 稍作改 进的解决方案通过在特定位置上大量部署参考节点来收集和上报实时的指纹数 44 第 4 章 无线信号指纹地图自适应更新 据 11 19 21 62 这些方法所需要的参考节点数量有的多一些或有的少一些 但无 论如何都需要部署额外的硬件设备 这使得这些方法造价高昂部署不易 丢失 了指纹定位方法本身的优势 近年来 基于群智感知而构建的指纹地图具备自 动更新的潜力 但已有的工作绝大多数都是针对指纹地图自动构建而非连续更 新 51 52 54 因此到目前为止 尚没有一种具体而实际可行的方案出现 为改变这种现状 本章探索如下关键问题 能否仅仅利用移动设备实现自 动 连续地更新无线信号指纹地图 而不依赖于任何额外的硬件部署或者特意的 人力参与 移动计算的飞速发展为这个问题给出了一个颇为积极的响应信号 特别地 我们注意到在人们日常使用过