第4章 WiFi 定位.ppt

1 无线定位系统 主编 梁久祯 2 第4章Wi Fi定位 4 1Wi Fi基础4 2无线信道 传播与衰落4 3位置指纹法4 4定位工具集案例4 5HTML5中的定位功能 3 4 1Wi Fi基础 4 1 1IEEE802 11系列标准概述WLAN WirelessLAN 的两个典型标准分别是由电气电子工程师协会 TheInstituteofElectricalandElectronicsEngineers IEEE 802标准化委员会下第11标准工作组制定的IEEE802 11系列标准和欧洲电信标准化协会 EuropeanTelecommunicationsStandardsInstitute ETSI 下的宽带无线电接入网络 BroadbandRadioAccessNetworks BRAN 小组制定的HiperLAN系列标准 IEEE802 11系列标准由Wi Fi联盟 官方网址 www wi fi org 负责推广 本章所有研究仅针对IEEE802 11系列标准 并且用Wi Fi代指IEEE802 11技术 4 4 1 2IEEE802 11系列标准历史1997年 IEEE为无线局域网制定了第一个版本标准 IEEE802 11 1999年加上了两个补充版本 802 11a和802 11b 之后 802 11工作小组还继续推出了一系列的标准 直到目前为止 802 11工作小组仍然在制定新的标准其中比较常见的几个标准是 在2003年被批准使用的802 11g 以及2009年被批准使用的802 11n 在经历一段时间的发展之后 IEEE802 11工作组会对IEEE802 11标准进行一次综合 比如最近的一次是2012年的802 11 2012 在原有标准的基础上 包含了k n p r s u v w y z这10个修正版 5 4 1 3Wi Fi网络成员与结构IEEE802 11主要规定了两种不同类型的基本架构 有基础架构的无线局域网络 InfrastructureWirelessLAN 和无基础架构的无线局域网络 AdHocWirelessLAN 在Wi Fi定位中常用的架构是有基础架构 如下图所示 6 4 1 4Wi Fi信道截至目前 802 11工作组划分了三个独立的频段 2 4GHz 3 7GHz以及5GHz 每个频段又划分为若干信道802 11b和802 11g将2 4GHz的频段区分为14个重复 标记的频道 每个频道的中心频率相差5兆赫兹 MHz 具体如下图所示 对于802 11工作组划分的不同信道频段 每个国家自己制定政策如何使用这些频段 在中国 2 4GHz频段可用信道为1 13信道 7 4 1 5Wi FiMAC帧格式首先我们先看一下一般的802 11MAC帧格式 其中比较重要的一个字段是FrameControl 帧控制 字段 其各位表示的内容如下所示 8 4 1 6Wi Fi扫描使用任何网络之前 首先必须找到网络的存在 在所在区域识别现有的网络过程称为扫描 scanning 在Wi Fi网络里面有两种扫描方式 被动扫描和主动扫描 在被动扫描中 工作站会在信道列表 channellist 所列的各个信道之间不断切换并静候Beacon帧的到来 在主动扫描 activescanning 中 工作站扮演着比较积极的角色 在每个信道上 工作站都会发出ProbeRequest帧来请求某个特定网络予以回应 9 被动扫描的整个过程 10 主动扫描的整个过程 11 4 2无线信道 传播与衰落 4 2 1概述在无线通信中 电波传播指的是无线电从发射机到接收机的传播 就像光波一样 电磁波受反射 折射 衍射 吸收 极化 偏振 和散射这些物理现象影响 由于这些物理现象 电磁波的传播是一个很复杂 很难预测的过程 在无线信道里面有一个现象叫做衰落 fading 也就是信号的幅度会随时间 频率发生变化 衰落现象大体上可以分为两类 大尺度衰落和小尺度衰落 12 衰落信道类型的划分 13 4 2 2大尺度衰落模型常用的大尺度衰落情况下的路径损耗模型有三种 自由空间传播模型 对数距离路径损耗模型以及对数正态模型 三个模型的公式如下 14 4 3位置指纹法 4 3 1概述在室外环境下 无论是Wi Fi或者是GSM都可以使用一定的传播模型的方法来进行定位 然而在室内环境下 由于电波的传播极其复杂 所以人们就发明了位置指纹法 配合上Wi FiAP通常都是在室内搭建 智能手机通常又都是在室内接收Wi Fi信号 这种方法就自然地吸引了很多的研究和应用 15 什么是位置指纹 一个位置指纹通常是指 一个MS 移动站点 手机 笔记本 在某个特定位置 采集不同AP发送过来的信号构成与特定位置相关的信号特征 下图便是某特定位置采集不同位置RSSI 接收信号强度 构成的一个指纹 位置指纹法的工作机制位置指纹法通常都是一个两阶段的工作模式 1 离线阶段 使用移动设备采集各AP发出来的RSSI 接收信号强度 关联上采集时的位置信息 构建一个位置指纹数据库 2 在线阶段 用用户采集到的各AP的RSSI去搜索位置指纹数据库 然后估算用户位置 位置指纹数据库 指纹匹配 17 4 3 2位置指纹数据库位置指纹数据库 LFDB 的构建是在离线阶段完成 位置指纹数据库是由众多数据库元素组成 数据库元素表述如下 18 位置指纹数据库的构建通常可以使用RSSI测量法 电波模型法以及混合法 RSSI测量法 LFDB可以整个地用RSSI测量法来构建 这通常需要一个MS 一个运行在MS上的收集和处理RSSI测量的软件 在室外环境下我们还需要一个GPS接收器 通过MS或者AP RSSI被周期性地测量得到 每一组被测得的RSSI集合都和真实的位置进行关联 该真实位置或通过GPS获取 或通过平面图获取 MS的参考坐标和其上测得的RSSI集合就构成了LFDB里面的一个元素 电波模型法 使用电波模型法构建LFDB 就是使用我们上一节介绍的电波传播模型 代入发射机的发射功率 通常在Wi Fi网络中发射机的功率是100mW 然后根据环境选择电波模型 比如说室外环境我们就可以使用对数正态模型甚至是自由空间模型 室内环境我们也可以使用对数正态模型 或者加上墙面衰减因素的电波传播模型 然后计算出各个位置的指纹存入LFDB 19 20 21 遗传算法 遗传算法GA GeneticAlgorithms 是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法 由J H Holland教授于1975年提出 它简单通用鲁棒性强 适于并行处理 因此在过去的20多年中遗传算法已在很多领域得到了应用受到了人们的广泛关注 将遗传算法用在解RF指纹搜索空间的缩减问题上时 每一个个体就是位置点 每一个位置点有一个用于评估个体适应度的参考RF指纹 于是遗传算法的步骤就是 初始化第一代种群 随机地从搜索空间中选择个体 估计当前种群中每一个个体的适应度 使用相关函数 建立染色体 将个体坐标转换成二进制格式 使用基因操作 选择 交叉 突变 建立新的种群 将染色体转换成整数格式 如果停止准则被满足 将适应度最高的个体对应的坐标返回作为MS位置 否则转到步骤2 22 23 24 25 神经网络方法 目前应用到Wi Fi定位的神经网络算法主要为BP神经网络算法 BP神经网络采用的是并行网络结构 包括输入层 隐含层和输出层 输入层的输入经过加权和偏置处理将信号传递给隐含层 在隐含层通过一个转移函数 有时也称为激活函数 将信号向下一个隐含层 网络可以有多个隐含层 也可以只有一个隐含层 或者直接通过输出层产生输出 26 Kolmogorov定理己经证明BP神经网络具有强大的非线性映射能力和泛化功能 任一连续函数或映射均可采用三层网络加以实现 一个典型的具有输入 输出和隐含层的BP神经网络如下图所示 27 BP算法可以通过以下具体过程实现 l 建立网络模型 初始化网络及学习参数 2 提供训练模式 选实例作为学习训练样本 训练网络 直到满足学习要求 3 前向传播过程 对给定训练模式输入 计算网络的输出模式 并与期望模式比较 若误差不能满足精度要求 则误差反向传播 否则转到 2 4 反向传播过程 28 在Wi Fi定位中我们还可以使用SVM 支持向量机 来作为一种非参数化非线性的估算位置的分类器 SVM方法已经被认为是来自统计学习理论的一种工具 使用SVM方法我们可以通过观察来导出位置的函数依赖关系 这种依赖关系在Wi Fi定位中就是RF指纹和位置信息之间的关系 SVM方法的基本想法是基于结构风险最小化 SRM StructuralRiskMinimization 原则来最小化期望风险泛函或者泛化误差的边界 风险泛函被定义为损失函数的期望值 损失函数是近似模式映射和实际模式映射差异的一个度量 总风险函数的边界被经验风险函数和VC Vapnik Chervonenkis 置信区间限定 SVM方法 使用SVM方法的分类操作可以简单地总结成以下两步 使用一个称为核的函数将RF指纹向量向一个称为特征空间的更高维数空间映射过去 有很多的SVM核函数可以被使用 比如说多项式函数 径向基函数 RBF radialbasisfunction S型函数 SVM算法在特征空间里面建立一个最优分割超平面或者说是决策面 然后使用这个超平面来进行分类 分割超平面通常不是唯一的 而当它和最近的训练集点有最大距离的时候 它就是最优化的 而支持向量就是那些用来定义超平面的训练向量 换句话说 支持向量机就是基于支持向量的学习算法 29 30 4 3 5位置估算方法的优化之前所说的四种方法是位置估算方法比较基本的算法思想 然而在实际使用时 通常我们还会根据实际情况 对算法进行一些优化补充 基于历史信息的Viterbi like算法 由于用户在一小段的时间里面位置的变动是不会很大的 所以我们可以连续存储用户一小段时间里面多个邻居的位置记录 然后利用这些历史位置信息清除掉一些位置相差很远的歧义点 以此提高了定位的精度 Viterbi like算法就是这样的一种算法 31 观察环境变化因素的AP自适应算法 由于Wi Fi信号会受人员移动 障碍物变化等因素的影响 与环境有很大的相关性 所以我们可以在一个固定区域里面准备多个LFDB 比如办公室忙季一个 办公室闲季一个 然后定位时恰当地选择出合适的LFDB来进行定位 以此来适应环境的变化 这种方法的网络结构如下 这种定位模式需要在两种设备上运行定位程序 一个是MS 另外一个则是某个AP 由AP4分别使用多个LPDB对自己进行定位 由于AP4位置已知 所以AP4可以判断出使用哪个LPDB定位精度最高 AP4判断出使用哪个LPDB库定位精度最高以后就把这个信息发给移动设备 移动设备也就使用当前环境下最优的LPDB对自己进行定位 32 4 4 1工具集概述Loc lib trace eva ana 工具集由德国曼海姆大学的ThomasKing等人开发 并且对外公开源码 工具集源码可从http pi4 informatik uni mannheim de pi4 data content projects loclib downloads html下载 该工具集一共包含了6个组件 它们分别是Loclib Loctrace Loceva Locana Locutil1以及Locutil2 4 4定位工具集案例 33 4 4 2LoclibLoclib被组织成了3个层 传感器数据收集层 数据转换层 定位程序接口层 下图展示了Loclib的组织以及分层结构 34 4 4 3LoctraceLoctrace只包含了一个程序 Tracer Tracer被用来收集构建指纹数据库的数据 为了实现这个目标 Tracer建立在Loclib之上直接收集传感器数据 例如 Wi Fi网络中通信范围之内的AP的RSSI值 它包括一个图形用户界面 GUI 来方便配置 例如 选择一个扫描模式和设备 35 4 4 4LocevaLoctrace产生的追踪文件可以交由Loceva来评估各种不同类型的定位算法 目前版本的Loceva已经实现了很多的定位算法 为了方便比较不同的定位算法 Loceva包含了一个管理部分来设置和选择不同的场景进行仿真 这样 Loceva利用Loctrace产生的追踪文件来仿真一个特殊的场景 这样的一个仿真场景就可以用在对比不同的定位算法 这样就确定了 不同的定位结果是基于不同的定位算法而不是由于环境的变化造成的 36 下面这张类图包含了Loceva所实现算法的关系图 37 4 4 5LocanaLocana对Loctrace和Loceva产生的结果进行可视化 很多这样的工具被组织到了Locana包中 Locana包含了很多特定用途的小工具 大部分很多工具都对Loctrace和Loceva的输出结果进行验证 或者是列出追踪文件中的一些特定对象 比如说 有一个名为AccessPointLister的工具就可以打印出所有的AP以及它们在追踪文件中出现的次数 Locana还包含了一个工具叫做Radiomap Radiomap提供了两种操作模式 loctrace模式和loceva模式 如下图所示 38 随着位置服务的日益火热 HTML5也专门添加了一个位置服务的api 俗称HTML5GeoLocationAPI 拿出笔记本 连入Wi Fi网络 打开浏览器 输入 4 5HTML5中的定位功能 39 4 5 1HTML5GeoLocation的使用首先必须要检查浏览器是否支持HTML5Geolocation JavaScript脚本如下 其次 可以使用如下语句进行位置的获取 40 之后便可调用successCallback 当然 对于错误处理我们也需要书写相应方法 41 4 5 2GoogleChromium剖析为了能了解 HTML5GeoLocation的实现细节 我们以Google的Chromium项目来查看其实现情况 网址 http src chromium org svn trunk src content browser geolocation 便是chromium对GeoLocation接口的实现了 截图如下 42 其中的一个重要文件是wifi