《WLAN定位技术》word版.doc

【学习】WLAN定位技术原文作者：阎啸天温亮生武威(中国移动通信有限公司研究院业务所)内容来源：定位技术摘要介绍了无线局域网(WLAN)中定位技术的发展现状,在对现有WLAN定位系统和技术进行分类的基础上着重介绍、比较和分析各种WLAN定位技术的特点、整体及其各功能流程的原理，详细综述了位置指纹定位和传播模型定位等两类基于接收信号强度的WLAN定位算法，最后总结展望了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.11 a/b/g/n通信协议、具有较灵活拓扑架构的无线局域网(WLAN)在机场、校园、医院、商业区、餐饮娱乐场所和住宅小区等各种场景中的泛在分布，以及在PDA、笔记本、上网本、MP4、智能手机等移动终端设备中的广泛支持使得基于WLAN的定位技术具有成本低、覆盖广、精度高等优势。WLAN定位技术中尤以基于接收信号强度的定位为其主要研究和应用方向，该类技术与基于信号到达时间(TOA)和信号到达角度(AOA)等传统几何原理的WLAN定位相比，它不需要添加额外的硬件设备来进行时间和角度的精确同步与测量，能充分利用现有覆盖广泛的无线局域网设施，便捷高效地将高质量定位的应用范围延伸到密集城区和室内，进一步降低了部署成本。本文首先介绍了WLAN中定位尤其是基于接收信号强度定位技术的研究进展和发展应用现状，详细阐述现有基于接收信号强度定位中两种具代表性系统和技术：指纹识别和传播模型方法的工作原理、整体及其各功能模块流程，并对其各自特点进行归纳、比较和分析，并对算法的精准度、稳定性、复杂度等方面性能进行综合分析和评估。最后对现有技术进行归纳总结。2.无线局域网(WLAN)定位技术概述无线局域网(WLAN)基于IEEE 802.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终端扫描所返回的AP及其属性列表示例图表1 WLAN基于信号强度定位系统的原理架构2.3.1位置指纹定位WLAN中首个定位系统RADAR由微软研究院的Bahl等人于2000年设计提出。RADAR系统使用的是信号强度指纹定位技术。位置指纹法工作流程主要可以分为离线勘测和在线定位两个阶段。主要原理和流程如图表2所示。图表2指纹定位离线和在线阶段原理(A：离线；B：在线；MU：移动终端；database：指纹数据库；RP：参离线勘测阶段的主要任务是在待定位区域里按照一定的间隔距离确定若干采样点，形成以一定密度覆盖待定位区域的采样点网格，并将每个采样点处测得的全部可见AP的MAC地址及其信号强度连同该采样点的位置等信息一同作为一条记录保存到数据库里，这些位置采样点对应的数据库记录信息被称为位置指纹或无线信号图。离线阶段的工作原理和示例。图表3离线阶段原理(RL-参考位置)图表4在线阶段系统原理在线定位阶段，将实时接收测量的可见AP信号强度信息与位置指纹数据库中的信号强度记录数据进行比较，取信号相似度最大，即信号强度最接近的采样点的位置作为位置估计结果。换个角度讲，位置指纹法也可以看作是让计算机先学习信号强度与位置间的内在规律，然后再推理的过程。根据位置指纹记录在数据库中的保存形式，指纹定位又可以分为确定性和概率分布等两大类方法。确定性方法在每条位置指纹记录中保存一定采样时间内接收信号强度的平均值；概率分布法保存的则是一定时间内信号强度的概率分布特征。概率分布法多使用各种概率论和数理统计理论和方法来处理RSSI测量中的不确定性。相比较而言，确定性方法比概率分布法更简单且实现更方便；而概率分布法对信号中噪声的抗干扰性较好，因此准确度相对更高。位置指纹数据库在WLAN位置指纹定位技术中，位置指纹数据库中存储了离线阶段各采样点处对应的位置坐标，及其以位置的函数存在的该采样点位置可见AP信号强度特征信息，如接收信号强度。除了RSS外，一些指纹定位技术和系统中也使用了其他指标作为接收AP信号强度特征信息，如Robin等人在UCLA大学的Nibble定位系统中使用了信噪比(SNR)，但是Bahl、郎昕培等人的研究结果表明RSS更适于被作为AP接收信号强度的特征信息来使用，因为RSS相比SNR具有更强的位置相关性。.1原始数据在离线采集阶段，终端于一段时间在第i个采样点处周期性连续观测和记录自身位置以及可见AP的信号强度特征信息等原始数据，并以特定格式存入指纹数据库。其中第j次观测所得的原始数据M(j)可以描述为下述形式：其中，表示集合或列表，一般其元素之间具有顺序要求(用于实现时参考)。A：B代表A和B之间的映射关系。表示第i个采样点第j次测量的可见AP集合大小。.2均值最常见也是最简单的指纹数据库数据预处理方法是计算和存储所测得AP心情的特征数据的均值，其典型的应用案例是RADAR定位系统。均值处理方法最简单之处在于其只需要存储个数值来作为位置指纹，即对于每一个AP而言只需要一个接收信号强度的平均数值即可。则指纹数据库中第i条记录，即第i个采样点处的信号强度均值可表示为：其中，分别代表第i个采样点的纬经(或符号)坐标、以及第j个AP接收信号强度的统计平均值。表示第i个采样点处经筛选处理后所得可见AP集合的大小。.3均值/方差唯独只存储均值数据固然简洁，但是却完全忽视了误差的随机波动即准确度相关的信息，Kaerusi等人通过扩展指纹数据库预处理数据，引入统计方差结果来考虑统计结果的离散程度。则对于某个采样点，第j个可见AP的接收信号强度统计方差可表述如下：其中，分别表示第i个采样点处第j个可见AP的时间轴取样数量、第j个可见AP第t次取样中所得的接收信号强度数值、第j个可见AP接收信号强度的统计均值。需要注意的是：取样次数必须大于1次。另外指纹数据库的记录格式和各采样点处RSS均值的计算可参考式(2)。.4直方图数据除均值、方差外一种近来研究应用更为热门的接收信号强度原始数据统计预处理方法是直方图方法。指纹数据库中相应第i个采样点的记录可以表示如下：其中，分别代表第i个采样点第j个AP的信号强度直方图、直方图bin宽度、第j个AP第t个RSS相应的直方图、第j个AP RSS观测量最大最小值。确定性方法确定性方法是一种比较简单的位置指纹定位技术。它最早出现在RADAR定位系统中，位置指纹数据库针对每个采样点保存相应位置处各可见AP的信号强度平均值。通过采用欧氏几何距离或其他类型距离(如Manhattan距离)度量测量值与位置指纹之间的差异，并取差异值最小的指纹位置作为估计位置。可以描述成如下数学形式：其中，或为实测数据或位置指纹中第i,i=1n个AP的信号强度均值。概率分布法确定性定位算法在定位阶段中通常只使用采样信息均值来计算信号空间距离，单纯使用均值将导致原始数据中方差信息未能得到充分发掘和利用。基于概率分布的位置指纹定位技术是目前WLAN定位算法研究的热点，该方法的核心思想是：在实测接收信号强度的基础上，计算得出用户位于各采样点的条件概率或后验概率，最终取条件概率最大的一个得到对终端位置的最大后验概率估计，或对多个MAP采样点进行相应统计平均处理得出终端位置。设：用户位置和终端可见AP信号强度抽象而成的随机变量分别为x和y，则概率分布法可以用数学方式描述如下：为计算似然函数，现有两种非参数方法，即核方法和直方图方法。另外一种基于概率分布的位置指纹法是基于贝叶斯网络技术，最早由UCLA大学Castro等人提出，应用在Nibble系统中，以提供WLAN网络环境下的室内定位服务。贝叶斯网络是一个联合概率分布的图形化表示，可以清楚地说明分布中各随机变量间的依赖关系。KNN和Histogram等三种最常用指纹算法的性能测试结果如下图所示。图表5(a)是定位结果的均方根误差均值随训练样本数量的变化特性曲线。图表5(b)是三种算法累积误差分布随定位误差的变化趋势。表格2是针对三种算法的各项误差统计分析数据对比关系。图表5(a)均方根误差均值vs样本数(b)累积平均误差表格2 KNN/Histogram/Kernel算法误差统计分析WLAN位置指纹定位技术虽然无需知道AP的具体位置、周围的WLAN信号传播环境，但另一方面，无线信号环境通常也会随着AP的变动如位置的轻微改动或发射功率的调整而发生较大变化，使得对于在位置指纹采集之后发生改变的AP而言，其覆盖区域内需要重新进行离线指纹样本的采集整理。因此，位置指纹数据库需要定期更新。而且指纹定位技术的精度严重受制于指纹采集的密度和人体的阻挡(占人体成分90%以上的水的共振频率同为2.4GHz)。综上，指纹定位技术一般只适用于无线环境易于保持的小范围区域。2.3.2信号传播模型定位为了减轻离线采样的工作量，通过对无线信号在室内范围的传播衰减模型进行研究。以及对常用模型适用条件和特点的比较，有人提出了考虑墙壁影响因素的无线信号衰减模型：其中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.11 ABG无线网卡，Kismet等嗅探工具)的路测车，通过多处扫描各可见AP并记录自身位置来推算AP的具体位置。路测法相比集中部署控制更加机动灵活，利于快速扩展覆盖范围和建立大规模AP数据库。图表6 Manhattan岛上所有AP信息图表7指纹/传播模型定位性能对比关系基于RSSI测量的信号传播模型方法存在不可忽视的缺陷，其相比指纹定位虽然步骤简捷，但其定位精度受到AP位置精度和路径传播损耗模型精度的影响。而且，此方法中忽视了AP天线的发射信号强度在各方向的分布并不均匀的实际情况，即AP天线周围不同方向的终端虽接收到AP的信号强度相同，但与AP的距离可能并不相同。上述这些因素(包括人体遮挡)都会对信号传播模型定位精度产生不同程度的影响。前人对位置指纹定位技术(RADAR)、信号传播模型定位中确定性技术(Trilateration,Simplified path loss model)与概率分布技术(Proposed)的定性能测试情况进行了对比研究，测试场景是小范围室内环境。由图7可见，指纹定位的性能相比传播模型定位具有一定优势。基于概率统计传播模型的建模技术在经过与RADAR的整合后，整体性能实现显著的提升。综上，将WLAN中信号强度指纹和信号强度模型两种定位技术的特性总结于表格3。表格3 WLAN信号强度定位技术性能比较技术信号强度指纹信号传播模型精度室内：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数据库和信号传播模型来替代大数据量指纹数据库的建立。在实际应用中，传播模型技术难以建立通用且准确的信号传播模型，因而实用性受环境的影响较为严重；相比之下，指纹定位技术不仅可以实现更好的定位性能，而且在用户侧收集和周期性路采的辅助下，具有更强的实用性和更广的适用范围。参考文献1M.Youssef.Horus：A WLAN-based Indoor Location Determination System.PhD thesis,Univ.of Maryland,2004.2Hui Liu,H.Darabi,P.Banerjee,and Jing Liu.Survey of wireless indoor positioning techniques and systems.Systems,Man,and Cybernetics,Part C：Applications and Reviews,IEEE Transactions on,37(6)：1067 1080,October 2007.3V.Honkavirta,T.Perala,and S.Ali.A comparative survey of wlan location fingerprinting methods.In Proc.of the 6th Workshop on Positioning,Navigation and Communication 2009(WPNC09),pages 243 251,2009.4孙巍，王行刚.移动定位技术综述.电子技术应用,29(6)：6 9,2003.5Fernando Seco,Antonio R.Jimenez,Carlos Prieto,Javier Roa,and Katerina Koutsou.A survey of mathematical methods for indoor localization.In 6th IEEE International Symposium on Intelligent Signal Processing,WISP,page August,Budapest,Hungary,2009.6A.Kushki,K.N.Plataniotis,A.N.Venetsanopoulos,and C.S.Regazzoni.Radio map fusion for indoor positioning in wireless local area netw orks.In Information Fusion,2005 8th International Conference on,volume 2,pages 1311 1318,2005.netstumbler.7P.Bahl and V.N.Padmanabhan.RADAR：an in-building rf-based user location and tracking system.In INFOCOM 2000.Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies.Proceedings.IEEE,volume 2,pages 775 784 vol.2,2000.8LBS组.定位技术策略.内部交流文档(幻灯片),March 2009.9Teemu Roos,Petri Myllymaki,Henry Tirri,Pauli Misikangas,and Juha Sievanen.A probabilistic approach to WLAN user location estimation.International Journal of Wireless Information Networks,9(3)：155 164,July 2002.10Kamol 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.11Guolin Sun and Wei Guo.Robust mobile geo-location algorithm based on LS-SVM.IEEE Transactions on Vehicular Technology,54(3)：1037 1041,2005.12C.Philipp Schl oter and Hamid Aghajan.Wireless symbolic positioning using support vector machines.In IWCMC06：Proceedings of the 2006 international conference on Wireless communications and mobile computing,pages 1141 1146,New York,NY,USA,2006.ACM.13Michael Wallbaum and Stefan Diepolder.Benchmarking wireless lan location systems.In WMCS05：Proceedings of the Second IEEE International Workshop on Mobile Commerce and Services,pages 42 51,Washington,DC,USA,2005.IEEE Computer Society.14Yu C.Cheng,Yatin Chawathe,Anthony Lamarca,and John Krumm.Accuracy characterization for metropolitan-scale Wi-Fi localization.In Proceedings of the Third International Conference on Mobile Systems,Applications,and Servic