WLAN定位技术

标签:
wlan核心思想分校幻灯片实时it |
分类: 网界评论 |
WLAN定位技术
阎啸天温亮生武威
(中国移动通信有限公司研究院业务所)
摘
关键词无线局域网,定位技术,性能指标,误差分析,指纹定位,传播模型
1. 引言
随着无线网络、移动通信、终端数据处理和普适计算(Pervasive Computing或Ubiquitous Computing,也称泛在计算)等技术的发展及其应用领域的扩大,结合先进移动通信和网络技术的位置服务(Location Based Services, LBS)及位置感知计算(或上下文感知计算, Location/Context-aware Computing)随之成为最具市场前景和发展潜力的移动互联网增值业务之一。典型的LBS服务的例子有周边人物和资源查找、兴趣点推荐、旅游导航、会 议指南等。从技术角度讲,LBS中的核心任务是目标人或物的定位。无论是在空旷还是遮挡的室内外环境下,LBS中快速准确地获得移动终端位置并继而提供相 应定制化、高质量信息和服务的需求日益提高。
全球定位系统(Global Positioning System, GPS)是迄今应用最为成功的定位系统,它通过GPS卫星信号接收机捕获、测量来自至少4颗在轨卫星的广播信号到达延迟时间来估算终端位置,可以提供覆盖 全球范围以及高精度、全天候的连续定位能力。但在室内和高楼密布的城区等信号遮挡严重的密集环境中,由于接收机捕获不到足够强度的卫星信号,GPS的定位 质量难以得到保证甚至无法完成定位,使其可用性受到严重制约。
基于IEEE 802.11a/b/g/n通信协议、具有较灵活拓扑架构的无线局域网(WLAN)在机场、校园、医院、商业区、餐饮娱乐场所和住宅小区等各种场景中的泛 在分布,以及在PDA、笔记本、上网本、MP4、智能手机等移动终端设备中的广泛支持使得基于WLAN的定位技术具有成本低、覆盖广、精度高等优势。 WLAN定位技术中尤以基于接收信号强度的定位为其主要研究和应用方向,该类技术与基于信号到达时间(TOA)和信号到达角度(AOA)等传统几何原理的 WLAN定位相比,它不需要添加额外的硬件设备来进行时间和角度的精确同步与测量,能充分利用现有覆盖广泛的无线局域网设施,便捷高效地将高质量定位的应 用范围延伸到密集城区和室内,进一步降低了部署成本。
本文首先介绍了WLAN中定位尤其是基于接收信号强度定位技术的研究进展和发展应用现状,详细阐述现有基于接收信号强度定位中两种具代表性系统和技术:指 纹识别和传播模型方法的工作原理、整体及其各功能模块流程,并对其各自特点进行归纳、比较和分析,并对算法的精准度、稳定性、复杂度等方面性能进行综合分 析和评估。最后对现有技术进行归纳总结。
2. 无线局域网(WLAN)定位技术概述
无线局域网(WLAN)基于IEEE802.11协议,是以无线信道作传输媒介的计算机局域网络,是计算机网络与无线通信技术相结合的产物,它以无线多址 信道作为传输媒介,提供传统有线局域网的功能,能够使用户真正实现随时、随地、随意的宽带网络接入。移动用户对信息的即时性和就地性的需求越来越强烈,这 就给基于WLAN系统的位置服务提供了广阔的发展空间。WLAN系统中定位技术主要有GPS卫星定位、基于RSSI或TOA/TDOA/AOA的三角定 位、信号强度定位等技术。其中,信号强度定位技术主要包括信号强度指纹/信号传播模型定位等两类方法。
2.1WLAN定位场景
如前所述,由于GPS技术的使用需要对卫星信号的捕获和接收,而卫星信号在高楼林立的密集城区(Dense Urban)或室内(Indoor)环境中易于被建筑等各种障碍物所阻挡。所以GPS终端在此类环境中接收卫星导航电文数据易于缺失,效果较差;其次,无 线电信号遇到建筑物、车辆以及其他物体时会发生反射,造成多径效应,从而导致多路信号同时到达接收天线使得接收端难于筛选出有效信息完成精确的测量和计算 准确的位置。相比之下,WLAN用户凭借轻量级可移动的计算设备(如笔记本电脑、掌上电脑和个人数字助理等),在WLAN灵活高效的网络覆盖下,可以获得 更高质量的接入,随时随地接入互联网。并且,WLAN定位系统测量的无线信号强度所受到障碍物的影响较小,可以满足密集城区、室内等环境下对信号强度的要 求。因此,在密集或室内环境下,GPS的定位方式并非足够有效。
2.2基于时间/角度测量的定位
WLAN定位系统中也可以基于TOA/TDOA,AOA,RSSI等进行三角测量和定位。然而,跟蜂窝网络环境不同的是,在WLAN低功率无线设备组成的 高密度网中,由于各设备之间的同步很难实现,利用TDOA估计距离也很难实现。尽管可以通过测量TOA来估计距离,但是障碍密集地区如室内等环境中用户之 间的距离较短,AP的覆盖范围往往不超过100米,无线电波的传输时延可以忽略不计,并存在较严重的衍射和绕射等非直线传播情况,而且同一用户信号的各条 多径分量在时间上相当接近,需要对设备的分辨率进行改进以区分时间上如此接近的各条多径。所以,精确的TOA或者TDOA估计,需要借助于更先进的数字信 号处理技术来实现。另外,墙壁、人体等影响信号传播的障碍物很多,无线信号存在反射和散射现象,到达接收机的信号是发射信号经过多个传播路径(存在非视 距)之后各分量的叠加。不同路径分量的幅度、相位、到达时间和入射角各不相同,使接收的复合信号在幅度和相位上都产生了严重的失真,因此,AOA也不适于 室内无线定位。
2.3基于信号强度的定位技术
近似感知、三角测量和场景分析是求解位置的三种基本原理。在基于信号强度的WLAN定位方法中,基于这三种原理的具体定位技术分别是最强基站法、传播模型法和位置指纹法。WLAN网络环境中基于信号强度的定位系统原理和架构可以参考图表 1。
最简单的定位方法是将无线终端用于数据通信的接入热点的位置,近似地作为无线终端的估计位置,此即最强基站法。该方法的精度受限于AP的覆盖范围,难以精确定位。
指纹定位是在WLAN网络环境保持不变的条件下,根据空间某位置处不同时刻无线信号强度变化趋势相同的时间一致性规律,基于场景分析原理,通过匹配实测信 号与信号采集指纹之间相似度来确定用户终端位置。传播模型定位是根据接收信号强度随传播距离远近而改变的空间变化性规律(即信号强度路径传播损耗规律)来 确定WLAN热点与用户终端之间物理距离,从而利用三角测量和计算原理完成定位的。
WLAN中用户终端网卡主动扫描或被动监听其接收范围内各WLAN信道上AP的信号,通过被动监听或主动扫描所接收到的某种IEEE 802.11协议数据帧中的MAC地址和SSID来辨识所有AP,并收集记录其相应的数据,如AP的RSSI值大小以及AP是否加密等。表格 1中是WLAN终端扫描或监听所返回AP及其相关属性的典型示例。WLAN中研究和应用最为广泛的信号强度定位技术便是以上述无线信号扫描和监听结果为基 础展开的。
表格 1
http://labs.chinamobile.com/upload/images/%E6%9C%AA%E5%91%BD%E5%90%8D5.bmp图表
1
2.3.1位置指纹定位
WLAN中首个定位系统RADAR由微软研究院的Bahl等人于2000年设计提出。RADAR系统使用的是信号强度指纹定位技术。位置指纹法工作流程主要可以分为离线勘测和在线定位两个阶段。主要原理和流程如图表 2所示。http://labs.chinamobile.com/upload/images/%E6%9C%AA%E5%91%BD%E5%90%8D(11).bmp
图表 2
(A:离线;B:在线;MU:移动终端;database: 指纹数据库;RP:参
http://labs.chinamobile.com/upload/images/%E6%9C%AA%E5%91%BD%E5%90%8D2(4).bmp
图表 3离线阶段原理(RL—参考位置)
在线定位阶段,将实时接收测量的可见AP信号强度信息与位置指纹数据库中的信号强度记录数据进行比较,取信号相似度最大,即信号强度最接近的采样点的位置作为位置估计结果。换个角度讲,位置指纹法也可以看作是让计算机先学习信号强度与位置间的内在规律,然后再推理的过程。
根据位置指纹记录在数据库中的保存形式,指纹定位又可以分为确定性和概率分布等两大类方法。确定性方法在每条位置指纹记录中保存一定采样时间内接收信号强 度的平均值;概率分布法保存的则是一定时间内信号强度的概率分布特征。概率分布法多使用各种概率论和数理统计理论和方法来处理RSSI测量中的不确定性。
相比较而言,确定性方法比概率分布法更简单且实现更方便;而概率分布法对信号中噪声的抗干扰性较好,因此准确度相对更高。
2.3.1.1 位置指纹数据库
在WLAN位置指纹定位技术中,位置指纹数据库中存储了离线阶段各采样点处对应的位置坐标,及其以位置的函数存在的该采样点位置可见AP信号强度特征信 息,如接收信号强度。除了RSS外,一些指纹定位技术和系统中也使用了其他指标作为接收AP信号强度特征信息,如Robin等人在UCLA大学的 Nibble定位系统中使用了信噪比(SNR),但是Bahl、郎昕培等人的研究结果表明RSS更适于被作为AP接收信号强度的特征信息来使用,因为 RSS相比SNR具有更强的位置相关性。
2.3.1.1.1 原始数据
在离线采集阶段,终端于一段时间在第i个采样点处周期性连续观测和记录自身位置以及可见AP的信号强度特征信息等原始数据,并以特定格式存入指纹数据库。其中第j次观测所得的原始数据M(j)可以描述为下述形式:
http://labs.chinamobile.com/upload/images/%E6%9C%AA%E5%91%BD%E5%90%8D5(1).bmp
其中,“[·]”表示集合或列表,一般其元素之间具有顺序要求(用于实现时参考)。A:B代表A和B之间的映射关系。http://labs.chinamobile.com/upload/images/%E6%9C%AA%E5%91%BD%E5%90%8D(52).bmp表示第i个采样点第j次测量的可见AP集合大小。
2.3.1.1.2 均值
最常见也是最简单的指纹数据库数据预处理方法是计算和存储所测得AP心情的特征数据的均值,其典型的应用案例是RADAR定位系统。均值处理方法最简单之处在于其只需要存储http://labs.chinamobile.com/upload/images/%E6%9C%AA%E5%91%BD%E5%90%8Dff.bmp
其中,http://labs.chinamobile.com/upload/images/%E6%9C%AA%E5%91%BD%E5%90%8Dfffff(1).bmp表示第i个采样点处经筛选处理后所得可见AP集合的大小。
2.3.1.1.3 均值/方差
唯独只存储均值数据固然简洁,但是却完全忽视了误差的随机波动即准确度相关的信息,Kaerusi等人通过扩展指纹数据库预处理数据,引入统计方差结果来考虑统计结果的离散程度。则对于某个采样点,第j个可见AP的接收信号强度统计方差可表述如下:
http://labs.chinamobile.com/upload/images/%E6%9C%AA%E5%91%BD%E5%90%8Dggg.bmp
其中,http://labs.chinamobile.com/upload/images/%E6%9C%AA%E5%91%BD%E5%90%8Dfffff(2).bmp必须大于1次。另外指纹数据库的记录格式和各采样点处RSS均值的计算可参考式(2)。
2.3.1.1.4 直方图数据
除均值、方差外一种近来研究应用更为热门的接收信号强度原始数据统计预处理方法是直方图方法。指纹数据库中相应第i个采样点的记录可以表示如下:
http://labs.chinamobile.com/upload/images/%E6%9C%AA%E5%91%BD%E5%90%8D(12).bmp
其中,http://labs.chinamobile.com/upload/images/%E6%9C%AA%E5%91%BD%E5%90%8D(13).bmp分别代表第i个采样点第j个AP的信号强度直方图、直方图bin宽度、第j个AP第t个RSS相应的直方图、第j个AP RSS观测量最大最小值。
2.3.1.2 确定性方法
确定性方法是一种比较简单的位置指纹定位技术。它最早出现在RADAR定位系统中,位置指纹数据库针对每个采样点保存相应位置处各可见AP的信号强度平均 值。通过采用欧氏几何距离或其他类型距离(如Manhattan距离)度量测量值与位置指纹之间的差异,并取差异值最小的指纹位置作为估计位置。可以描述 成如下数学形式:http://labs.chinamobile.com/upload/images/%E6%9C%AA%E5%91%BD%E5%90%8D(14).bmp
其中,http://labs.chinamobile.com/upload/images/%E6%9C%AA%E5%91%BD%E5%90%8D(16).bmp为实测数据或位置指纹中第i, i=1…n个AP的信号强度均值。
2.3.1.3 概率分布法
确定性定位算法在定位阶段中通常只使用采样信息均值来计算信号空间距离,单纯使用均值将导致原始数据中方差信息未能得到充分发掘和利用。基于概率分布的位 置指纹定位技术是目前WLAN定位算法研究的热点,该方法的核心思想是:在实测接收信号强度的基础上,计算得出用户位于各采样点的条件概率或后验概率,最 终取条件概率最大的一个得到对终端位置的最大后验概率估计http://labs.chinamobile.com/upload/images/%E6%9C%AA%E5%91%BD%E5%90%8D(23).bmp,或对多个MAP采样点进行相应统计平均处理得出终端位置。设:用户位置和终端可见AP信号强度抽象而成的随机变量分别为x和y,则概率分布法可以用数学方式描述如下:
http://labs.chinamobile.com/upload/images/%E6%9C%AA%E5%91%BD%E5%90%8D(17).bmp
为计算似然函数http://labs.chinamobile.com/upload/images/%E6%9C%AA%E5%91%BD%E5%90%8D(22).bmp,现有两种非参数方法,即核方法和直方图方法。
另外一种基于概率分布的位置指纹法是基于贝叶斯网络技术,最早由UCLA大学Castro等人提出,应用在Nibble系统中,以提供WLAN网络环境下的室内定位服务。贝叶斯网络是一个联合概率分布的图形化表示,可以清楚地说明分布中各随机变量间的依赖关系。
KNN和Histogram等三种最常用指纹算法的性能测试结果如下图所示。图表 5(a)是定位结果的均方根误差均值随训练样本数量的变化特性曲线。图表 5(b)是三种算法累积误差分布随定位误差的变化趋势。表格 2是针对三种算法的各项误差统计分析数据对比关系。http://labs.chinamobile.com/upload/images/%E6%9C%AA%E5%91%BD%E5%90%8D(18).bmp
图表 5(a)均方根误差均值vs样本数
表格
2
http://labs.chinamobile.com/upload/images/%E6%9C%AA%E5%91%BD%E5%90%8D(19).bmp
WLAN位置指纹定位技术虽然无需知道AP的具体位置、周围的WLAN信号传播环境,但另一方面,无线信号环境通常也会随着AP的变动如位置的轻微改动或 发射功率的调整而发生较大变化,使得对于在位置指纹采集之后发生改变的AP而言,其覆盖区域内需要重新进行离线指纹样本的采集整理。因此,位置指纹数据库 需要定期更新。而且指纹定位技术的精度严重受制于指纹采集的密度和人体的阻挡(占人体成分90%以上的水的共振频率同为2.4GHz)。综上,指纹定位技 术一般只适用于无线环境易于保持的小范围区域。
2.3.2信号传播模型定位
为了减轻离线采样的工作量,通过对无线信号在室内范围的传播衰减模型进行研究。以及对常用模型适用条件和特点的比较,有人提出了考虑墙壁影响因素的无线信号衰减模型:http://labs.chinamobile.com/upload/images/%E6%9C%AA%E5%91%BD%E5%90%8D(20).bmp
其中n表示信号强度随距离增加的衰减速度,P(d0)表示在参考距离d0处的信号强度,d表示信号发送方和接收方之间的距离。C表示衰减因子能够分辨出的最大墙壁数,nW表示信号发送方和接收方之间的墙壁数,WAF指信号经过墙壁的衰减因子。他们研究的模型没有直接用于估计用户的位置,只是用来自动生成定位区域的无线信号图。
美国加州大学圣迭戈(San Diego)分校于2002年设计的ActiveCampus系统使用了与RADAR系统不同、被称为信号传播模型的定位技术。此类传播模型定位系统中记 录了AP的精确位置,根据WLAN信号路径传播损耗规律,并结合三角测量原理来计算WLAN终端位置。这类方法的定位准确性主要依赖于路径传播损耗模型是 否足够准确,是否足够适合定位区域的物理环境。根据传播损耗模型的来源,传播模型方法又可以分为物理模型法和实验模型法,即物理模型由信号传播损耗的物理 特性得到,实验模型由大量实验数据回归拟合获取。实验模型法得到的传播模型更适合待定位的具体环境,但它普遍性、灵活性不足,使这类定位系统实用性有限, 推广难度较大。
如前所述,信号传播模型定位至少需要预知AP的标识及其位置信息即建立AP数据库,相比位置指纹技术大量的位置指纹采集工作。建立AP位置数据库的方法主 要有两种:站址登记和路测推算。站址登记较为简单,即为集中部署时登记各个AP的位置,适合企业、机场、医院、学校等便于集中管理和控制的公共场合。这种 方法的AP数据库适用期较长,但是网络覆盖固定,使得定位的使用范围受限。
通过路测建立AP数据库一般是使用装配了GPS/AGPS定位数据源(如GPSD)和WLAN扫描工具(802.11ABG无线网卡,Kismet等嗅探 工具)的路测车,通过多处扫描各可见AP并记录自身位置来推算AP的具体位置。路测法相比集中部署控制更加机动灵活,利于快速扩展覆盖范围和建立大规模 AP数据库。
http://labs.chinamobile.com/upload/images/%E6%9C%AA%E5%91%BD%E5%90%8D(21).bmp
图表 6
基于RSSI测量的信号传播模型方法存在不可忽视的缺陷,其相比指纹定位虽然步骤简捷,但其定位精度受到AP位置精度和路径传播损耗模型精度的影响。而 且,此方法中忽视了AP天线的发射信号强度在各方向的分布并不均匀的实际情况,即AP天线周围不同方向的终端虽接收到AP的信号强度相同,但与AP的距离 可能并不相同。上述这些因素(包括人体遮挡)都会对信号传播模型定位精度产生不同程度的影响。
前人对位置指纹定位技术(RADAR)、信号传播模型定位中确定性技术(Trilateration, Simplified path loss model)与概率分布技术(Proposed)的定性能测试情况进行了对比研究,测试场景是小范围室内环境。由图7可见,指纹定位的性能相比传播模型定 位具有一定优势。基于概率统计传播模型的建模技术在经过与RADAR的整合后,整体性能实现显著的提升。
综上,将WLAN中信号强度指纹和信号强度模型两种定位技术的特性总结于表格 3。
表格 3
技 术 |
信号强度指纹 |
信号传播模型 |
精 度 |
室内:1-5 m (80%~90%);室外:<50m |
室内:10-20 m;室外:70-100m |
覆盖范围 |
楼宇,小型校园,城区,需802.11覆盖和指纹数据库 |
结合路测建立AP数据库,需要对目标区域建立传播模型 |
网络侧建设成本 |
除802.11 AP外不需额外基础设施。建立指纹数据库较耗时,AP添加和移动时需重建 |
除802.11 AP外不需额外基础设施。建立AP数据库工作量较指纹法少,传播模型建立成本较高 |
终端成本 |
只需要针对802.11无线网卡的软件 |
同左 |
用户隐私 |
定位由终端完成时较好,由网络侧完成时较差 |
同左 |
应用环境 |
室内资产和人员跟踪;室内外导航、导游、绘图,指纹采集不受环境影响 |
室内外特定范围的导航、导游等活动,建模受环境影响严重 |
3. 结论
WLAN的部署为蜂窝网络中AGPS、Cell等定位技术提供了有力的补充。由于特征测量方法面临与蜂窝网络中相同甚至更为严重的误差影响,WLAN定位 方法研究和应用的重点方向是基于信号强度的技术。其中,指纹技术最关键之处在于通过离线数据训练和在线匹配识别分阶段实施来引入机器学习和统计学习理论方 法中多样而高效的工具手段对记录和观测数据进行融合预测或分类比较;建模技术则是通过建立AP数据库和信号传播模型来替代大数据量指纹数据库的建立。在实 际应用中,传播模型技术难以建立通用且准确的信号传播模型,因而实用性受环境的影响较为严重;相比之下,指纹定位技术不仅可以实现更好的定位性能,而且在 用户侧收集和周期性路采的辅助下,具有更强的实用性和更广的适用范围。
参考文献
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]Kamol Kaemarungsi and Prashant Krishnamurthy. Properties of indoor received signal strength for WLAN location fingerprinting. Mobile and Ubiquitous Systems, Annual International Conference on, 0:14–23, 2004.
[11]Guolin Sun and Wei Guo. Robust mobile geo-location algorithm based on LS-SVM. IEEE Transactions on Vehicular Technology, 54(3):1037–1041, 2005.
[12]C.
[13]Michael Wallbaum and Stefan Diepolder. Benchmarking wireless lan location systems. In WMCS ’05: Proceedings of the Second IEEE International Workshop on Mobile Commerce and Services, pages 42–51, Washington, DC, USA, 2005. IEEE Computer Society.
[14]Yu
[15]Andreas Haeberlen, Eliot
Flannery, Andrew
[16]William
[17]Alan Bensky. Wireless Positioning Technologies and Applications. Artech House, 685 Canton Street Norwood, MA., 2008.
[18]Anthony LaMarca and Eyal
de
[19]M.
[20]Mauro Brunato and Roberto Battiti. Statistical learning theory for location fingerprinting in wireless LANs. Comput. Netw. ISDN Syst., 47(6):825–845, 2005.