第4章 WiFi 定位

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,无线定位系统,主编：梁久祯,2,第,4,章,Wi-Fi,定位,4.1,Wi-Fi,基础,4.2,无线信道：传播与衰落,4.3,位置指纹法,4.4,定位工具集案例,4.5 HTML5,中的定位功能,3,4.1,Wi-Fi,基础,4.1.1,IEEE 802.11,系列标准概述,WLAN(Wireless,LAN),的两个典型标准分别是由电气电子工程师协会,(The Institute of Electrical and Electronics Engineers,，,IEEE)802,标准化委员会下第,11,标准工作组制定的,IEEE 802.11,系列标准,和欧洲电信标准化协会,(European Telecommunications Standards Institute,，,ETSI),下的宽带无线电接入网络,(Broadband Radio Access Networks,，,BRAN),小组制定的,HiperLAN,系列标准,。,IEEE 802.11,系列标准由,Wi-Fi,联盟,(,官方网址：,www.wi-fi.org,),负责推广，本章所有研究仅针对,IEEE 802.11,系列标准，并且用,Wi-Fi,代指,IEEE 802.11,技术。,4,4.1.2,IEEE 802.11,系列标准,历史,1997,年,IEEE,为无线局域网制定了第一个版本标准,-IEEE 802.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.3,Wi-Fi,网络成员与结构,IEEE 802.11,主要规定了两种不同类型的基本架构：有基础架构的无线局域网络,(Infrastructure Wireless LAN),和无基础架构的无线局域网络,(Ad Hoc Wireless LAN),。,在,Wi-Fi,定位中常用的架构是,有基础架构,，如下图所示：,6,4.1.4,Wi-Fi,信道,截至目前，,802.11,工作组划分了三个独立的频段，,2.4 GHz,，,3.7GHz,以及,5 GHz,。每个频段又划分为若干信道,802.11b,和,802.11g,将,2.4 GHz,的频段区分为,14,个重复、标记的频道,;,每个频道的中心频率相差,5,兆赫兹,(MHz),，具体如下图所示：,对于,802.11,工作组划分的不同信道频段，每个国家自己制定政策如何使用这些频段。在中国，,2.4GHz,频段可用信道为,113,信道,7,4.1.5,Wi-Fi,MAC,帧格式,首先我们先看一下一般的,802.11 MAC,帧格式,Frame,Control,Duration,/ID,Address,1,Address,2,Address,3,Sequence,Control,Address,4,QoS,Control,HT,Control,Frame,Body,FCS,2,2,6,6,6,2,6,2,4,0 - 7951,4,其中比较重要的一个字段是,Frame Control(,帧控制,),字段，其各位表示的内容如下所示：,0-1,2-3,4-7,8,9,10,11,12,13,14,15,Protocol Version,Type,Subtype,To DS,From DS,More,Frag,Retry,Pwr,Mgmt,More Data,Protected Frame,Order,2,2,4,1,1,1,1,1,1,1,1,8,4.1.6,Wi-Fi,扫描,使用任何网络之前，首先必须找到网络的存在。在所在区域识别现有的网络过程称为扫描,(scanning),。,在,Wi-Fi,网络里面有两种扫描方式：,被动扫描,和,主动扫描,。,在被动扫描中，工作站会在信道列表,( channel list),所列的各个信道之间不断切换并静候,Beacon,帧的到来。,在主动扫描,(active scanning),中，工作站扮演着比较积极的角色。在每个信道上，工作站都会发出,Probe Request,帧来请求某个特定网络予以回应。,9,被动扫描的整个过程：,10,主动扫描的整个过程：,11,4.2,无线信道：传播与衰落,4.2.1,概述,在无线通信中，电波传播指的是无线电从发射机到接收机的传播。就像光波一样，电磁波受反射、折射、衍射、吸收、极化,(,偏振,),和散射这些物理现象影响。由于这些物理现象，电磁波的传播是一个很复杂、很难预测的过程。,在无线信道里面有一个现象叫做衰落,(fading),，也就是信号的幅度会随时间、频率发生变化。衰落现象大体上可以分为两类：大尺度衰落和小尺度衰落。,12,衰落信道类型的划分,13,4.2.2,大尺度衰落,模型,常用的,大尺度衰落情况下的路径损耗模型,有三种：,自由空间传播模型,，,对数距离路径损耗模型,以及,对数正态模型,。三个模型的公式如下：,14,4.3,位置指纹法,4.3.1,概述,在室外环境下，无论是,Wi-Fi,或者是,GSM,都可以使用一定的传播模型的方法来进行定位。然而在室内环境下，由于电波的传播极其复杂，所以人们就发明了,位置指纹法,，配合上,Wi-Fi,AP,通常都是在室内搭建，智能手机通常又都是在室内接收,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( Genetic Algorithms),是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，由,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,，,Structural Risk Minimization),原则来最小化期望风险泛函或者泛化误差的边界。风险泛函被定义为损失函数的期望值。损失函数是近似模式映射和实际模式映射差异的一个度量。总风险函数的边界被经验风险函数和,VC(Vapnik-Chervonenkis,),置信区间限定。,SVM,方法,：,使用,SVM,方法的分类操作可以简单地总结成以下两步：,使用一个称为核的函数将,RF,指纹向量向一个称为特征空间的更高维数空间映射过去。有很多的,SVM,核函数可以被使用，比如说多项式函数、径向基函数,(RBF,，,radial basis function),、,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,工具集概述,Loclib,trace,eva,ana,工具集由德国曼海姆大学的,Thomas King,等人开发，并且对外公开源码，工具集源码可从,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.2,Loclib,Loclib,被组织成了,3,个层：传感器数据收集层、数据转换层、定位程序接口层。,下图,展示了,Loclib,的组织以及分层结构。,34,4.4.3,Loctrace,Loctrace,只包含了一个程序：,Tracer,。,Tracer,被用来收集构建指纹数据库的数据。为了实现这个目标，,Tracer,建立在,Loclib,之上直接收集传感器数据,(,例如，,Wi-Fi,网络中通信范围之内的,AP,的,RSSI,值,),。它包括一个图形用户界面,(GUI),来方便配置,(,例如，选择一个扫描模式和设备,),。,35,4.4.4,Loceva,Loctrace,产生的追踪文件可以交由,Loceva,来评估各种不同类型的定位算法。目前版本的,Loceva,已经实现了很多的定位算法。,为了方便比较不同的定位算法，,Loceva,包含了一个管理部分来设置和选择不同的场景进行仿真。这样，,Loceva,利用,Loctrace,产生的追踪文件来仿真一个特殊的场景。这样的一个仿真场景就可以用在对比不同的定位算法。这样就确定了，不同的定位结果是基于不同的定位算法而不是由于环境的变化造成的。,36,下面这张类图包含了,Loceva,所实现算法的关系图,37,4.4.5,Locana,Locana,对,Loctrace,和,Loceva,产生的结果进行可视化。很多这样的工具被组织到了,Locana,包中。,Locana,包含了很多特定用途的小工具。大部分很多工具都对,Loctrace,和,Loceva,的输出结果进行验证，或者是列出追踪文件中的一些特定对象。比如说，有一个名为,AccessPointLister,的工具就可以打印出所有的,AP,以及它们在追踪文件中出现的次数。,Locana,还包含了一个工具叫做,Radiomap,。,Radiomap,提供了两种操作模式：,loctrace,模式和,loceva,模式。,如下图所示：,38,随着位置服务的日益火热，,HTML5,也专门添加了一个位置服务的,api,，俗称,HTML5,GeoLocation,API,。,拿出笔记本，连入,Wi-Fi,网络，打开浏览器，输入,http:/,/,，在出现的,Google,地图左上角的小人上面有个小点，点击它，就可以看到效果了。,4.5 HTML5,中的定位功能,39,4.5.1 HTML5,GeoLocation,的使用,首先必须要检查浏览器是否支持,HTML5,Geolocation,，,JavaScript,脚本如下：,其次，,可以使用如下语句进行位置的获取,40,之后便可调用,successCallback,当然，对于错误处理我们也需要书写相应方法：,41,4.5.2 Google Chromium,剖析,为了能了解，,HTML5,GeoLocation,的实现细节，我们以,Google,的,Chromium,项目来查看其实现情况。网址：,http:/,src.chromium.org/svn,/,trunk/,src/content/browser/geolocation,/,便是,chromium,对,GeoLocation,接口的实现了,。截图如下：,42,其中的一个重要文件是,wifi_data_provider_common_win.cc,，其中的一段代码如下：,从代码中我们可以看出在,Windows,环境下，,Google,浏览器目前只是获取了,AP,的,MAC,地址和信号强度,(,也就是之前讲的,RSSI),，这也表明了,Google,浏览器采用的,Wi-Fi,定位手段就是基于,RSSI,的。,43,Chromium,只是,Google,WiFi,定位服务的一个客户端，而实际上为了构建位置指纹数据库，每年,Google,还会派出很多街景车，一方面拍摄图街景，一方面采集位置指纹。,左图便是，,Google,的街景车，而右图则是在街景车上运行的位置指纹采集程序框架。,习题,IEEE 802.11,的第一个版本是在哪一年被制定的？,Wi-Fi,联盟又是哪一年成立的？,802.11b,的工作频段是几,GHz,？,802.11a,、,802.11g,、,802.11n,的工作频段又分别是多少？,根据,802.11 MAC,帧的,Frame Control,字段里面的,Type,取值，,MAC,帧可以被分为哪几种类型？,现有一个,802.11 MAC,帧它的,Frame Control,字段的值为,0x0080,。请判断它是属于什么类型的帧（精确到子类型）。,Wi-Fi,扫描的扫描类型有哪两种？,习题,假设离线阶段，,9,个不同位置对,4,个,AP,采样得到的均值结果。如右表所示，在线阶段时，某移动设备采集到的,4,个,AP,的,RSSI,从,AP1AP4,分别为,(-33,-34,-36,-36),，试用最近邻算法估算出移动设备的位置坐标。,假设在某位置上对,4,个,AP,进行采样的采样情况如右下表所示，试画出位置上各,AP,采得的,RSSI,值的归一化平面分布直方图。,