基于位置指纹室内定位算法研究

关于论文使用授权的说明本学位论文作者及指导教师完全了关于论文使用授权的说明本学位论文作者及指导教师完全了解辽宁工程技术大学有关保留使用学位论文的规定，同意辽宁工程技术大学保留并向国家有关部门机构送交论文的复印件和磁盘，允许论文被查阅和借阅，学校可以将位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、印或扫描等复制手段保存、汇编本学位论文。保密的学位论文在解密后应遵守此协学位论文作者签名： 导师签名： 年月日年月日致谢研究生生活转瞬即逝，这两年半中我的成长与收获与老师们的悉心指导和同学们的真心帮助是离不开的，我心中充满感谢之情。在读研的期间，我的导师李新春悉心指导我如何学习和创新，李老师渊博的知识和开阔的科研思路使我受益匪浅，让我在思考问题的层次有了颇大的提高，本篇论文的撰写也是在李老师的指导下完成。在此特向李老师表达我最美好的祝愿和最真挚的感谢！我还要感谢我实验室的同学们，也感谢同学们在学习和生活上对我的关心和帮助，致谢研究生生活转瞬即逝，这两年半中我的成长与收获与老师们的悉心指导和同学们的真心帮助是离不开的，我心中充满感谢之情。在读研的期间，我的导师李新春悉心指导我如何学习和创新，李老师渊博的知识和开阔的科研思路使我受益匪浅，让我在思考问题的层次有了颇大的提高，本篇论文的撰写也是在李老师的指导下完成。在此特向李老师表达我最美好的祝愿和最真挚的感谢！我还要感谢我实验室的同学们，也感谢同学们在学习和生活上对我的关心和帮助，最后，衷心感谢审阅论文和答辩组的老师们！摘要LWR-KNN摘要LWR-KNN算法，在离线阶段采集的位置指纹的基础上通过局部加权回归得到一个模拟射KNN定位算法的定位精度；针对提高室Robust-KNN定位算法和辅助排查定位系统异常的丢失接入点搜索算法。实验结果表明，LWR-KNN算法可以在参考点稀疏的情况下显著改善定位精度，Robust-KNN可以在部分接入点丢失的情况下仍提供较可靠的关键词：-IAsradiofingerprintaccuracy,ithasbecomeenhanceAsradiofingerprintaccuracy,ithasbecomeenhancetheaccuracybasedindoorpositioningapproachissimple,lowcost,highthefocusinindoorpositioningresearchfield.Inordertoindoorpositioningalgorithm,alocallyweightedbasedradiomapargumentapproachisproposed,whichiscalledLWR-KNNalgorithm.LWR-KNNmakeuseoftheradiofingerprintfromcalibrationpointscollectedinofflinephaseandthelocallyweightedregressionalgorithmtogeneratesyntheticpoints.Toimproverobustnessofindoorlocationalgorithm,anaccesspointlostpreventedpositioningalgorithmisproposed.ThedetectionofaccesspointlostisbasedontheKnearestneighborapproachaccordingtothedistortioninsignalspace.Thepossibilityofanaccesspointhasbeenlostisupdatedconstantlyandthedistancemetricismodifiedwhenaccesspointlostisdetected.ExperimentalresultsindicatethattheproposedLWR-KNNalgorithmcansignificantlyimprovetheaccuracyofKNNpositionalgorithm,especiallywhenthecalibrationpointsaresparse.TheRobust-KNNapproachcanprovidereliablelocationestimationevenapartofaccesspointshavebeenlost.Furthermore,alostaccesspointssetcanbedeterminedafterobtainedobservations,whichcanprovideabasisfortheindoorpositioningsystemtoeliminateKeyWords：indoorlost；--目录摘 TODO: 1绪 基于研究背景及意 室内定位目录摘 TODO: 1绪 基于研究背景及意 室内定位的国内外研究现 主要研究工 论文结 Wi-Fi的室内定位技 2基于Wi-Fi的定位算法分 几何定位 最大似然估计定位 近似定位 位置指纹定位 基于位置指纹的定位技 基本原 位置指纹数据库预处 位置指纹定位算 室内定位技术评价指 本章小 3高精度的Wi-Fi室内定位算法研 算法研究基 基于局部加权回归的射频指纹地图校 局部加权线性回归(LocallyWightedRegression, 留一交叉验证法(Leave-One-Out-Cross- LWR射频指纹地图校 实验及结果分 实验环 -III参考点密集情况下的LWR射频地图校 参考点密集情况下的LWR射频地图校 参考点稀疏情况下的LWR射频地图校 3.4本章小 高鲁棒性的Wi-Fi室内定位算法研 4异常条 传统算法定位精度变 算法描 接入点筛 异常检 信号空间距离修 丢失AP搜索算 算法工作流 算法结果及分 非异常条件下算法结 异常条件下算法结 本章小 5参总结与展 考文 者简 作学位论文原创性声 学位论文数据 -IV1绪研究背景及意义基于位置的服务1绪研究背景及意义基于位置的服务(LocationBasedService,LBS)是指由卫星定位系统、移动通信网络、无线局域网(WirelessLocalAreaNetworks,WLAN)等通过一组定位技术获得待定位节点的绝对位置(如经纬度坐标数据)或相对位置(如相对某参考位置的数据)提供给待定位终端本身、通信系统等以实现各种与位置相关业务的服务[1-3]。广域定位技术主要包含全球定位系统和蜂窝无线定位系统。20世纪70年代美国军方为实现陆海空三大领域提供全天候、实时的、全球的定位导航服务，研制了全球定位系统(GlobalPositioningSystem,GPS)，并在海湾战争中用于实战，开启了精准打击时代[4]。后因GPS的巨大实用价值，美国总统克林顿颁布法令，将GPS免费向民用领域开放。随之而来的是基于GPS的车辆定位系统、导航系统等服务的广泛应用。其他国家也陆续研究开发了自己的全球定位系统，其中包含俄罗斯的GLONASS定位系统、欧盟的Galileo定位系统以及我国的北斗卫星定位系统[5]。但是在室内环境下，GPS卫星发射的电磁信号强度太小、建筑物遮挡卫星信号传播等因素使得在室内环境中GPS无法给出令人满意的定位精度[6]。另一种广泛应用的广域定位系统是基于移动蜂窝网络的基站定位系统，即蜂窝无线定位，其定位精度依赖于基站信号覆盖范围的大小和基站位置的分布，在室内环境下，蜂窝无线定位系统也无法满足定位精度的要求[7]。基于传感器设备的定位技术通过将传感器设备事先部署到待定位区域中，通过对进入到待定位区域的待定位节点进行探测来实现位置的估测，主要包括基于射频标签的定位、基于红外线的定位、基于蓝牙的定位、基于地磁感应的定位等[8-17]。利用传感器设备的定位技术需要专门的感知设备支持，且受室内环境的影响程度颇高。为了满足一定的定位精度，需要大范围的传感器设备部署，实现成本和部署难度较高。因此，该种定位技术适用于范围较小、对成本控制要求不高的简单室内环20世纪末开始，WLAN技术作为一种高速无线通信技术发展起来，其结合了现代社会对办公、移动娱乐的需求，且具有部署方便、通信快速等优点。机场、会展中心、写字楼、各类型酒店等人们活动的主要室内环境都是Wi-Fi接入点的重点部署场合。Wi-Fi网络承载了人们的快速Internet接入，并非为定位而生，但是却在室内无线定位中扮演着十分重要的角色。基于Wi-Fi的室内定位技术复用已经广泛部-5署的Wi-Fi接入点和正在普及的智能移动终端设备，相较于广域定位技术和基于传感器的室内定位技术，具有颇高的实用价值。诸多署的Wi-Fi接入点和正在普及的智能移动终端设备，相较于广域定位技术和基于传感器的室内定位技术，具有颇高的实用价值。诸多知名企业Google、Apple和Microsoft等，都投入大量资源来研究基于Wi-Fi的室内定位技术。现有的Wi-Fi定位技术主要有基于信号到达时间的定位(TOA)、基于信号达到角度的定位(AOA)、基于信号到达时间差的定位(TDOA)以及基于信号强度的定位(RSSI)[18-21]。TOA、AOA、TDOA需要不同程度上改变硬件设备来进行时间同步或角度测量，而基于RSSI的定位只需要利用现有的无线网络资源并配合定位软件就可以实现位置估测，降低了成本，得到广泛定位技术研究者的热爱。基于RSSI的定位又分为信号传播模型损耗法和位置指纹定位法，其中传播模型损耗法难以精确定义信号传播模型，并受多径效应影响严重，这使得其定位精度受到限制；基于位置指纹的定位法则依靠识别目标位置信号特征来进行位置估测，可以较好地适应复杂的室内环境且不受信号传播模型准确程度的限制[22-24]。本文就是在这样的背景下对基于位置指纹的室内定位算法进行研究，试图从定位精度和定位系统的鲁棒性两个不同的角度对室内定位技术进行改进。定位精度的提高可以提供更精准的基于位置的服务，而定位系统的鲁棒性的改善可以在定位系统基础设施发生部分损坏时仍提供可靠的位置服务，这在恶劣的环境中，如火灾现场等，具有非常高的实际意义。室内定位的国内外研究现室内定位技术相较于室外定位技术起步较晚，却发展迅速。人们对室内环境下定位、导航的需求越来越大，促使国内外学者、研究机构对室内定位展开了广泛的一种室内定位方法是将室外定位技术引入到室内环境，但如上一节所述的那样，在室内环境下传统的室外定位技术无法满足对定位精度的要求。人们开始专注于其他的定位技术，给出了许多适合特定场景下的定位技术解决方案。如在工厂、仓库和商场中用于物品管理的射频标签定位技术，室内视距条件下定位精度很高的超声波定位技术，适用于人体定位的红外定位技术，适用于短距离定位的蓝牙定位技术，覆盖范围广的WLAN定位技术，适用于无线传感器网络(WirelessSensorNetwork,WSN)的ZigBee定位技术。此外，还有利用视频、图像、地磁、压力传感器等的定位技术。下面简要介绍几个比较有代表性的室内定位技术[25-32]。(1)基于红外线技术的室内定位-6基于红外线的室内定位技术的原理是，部署在室内的红外线接收器接收待定位节点携带的红外线标识每隔一段时间发出的红外线信号并对待定位节点的位置进行估计，代表的定位系统如AT&TCambridge基于红外线的室内定位技术的原理是，部署在室内的红外线接收器接收待定位节点携带的红外线标识每隔一段时间发出的红外线信号并对待定位节点的位置进行估计，代表的定位系统如AT&TCambridge设计的ActiveBadge系统[33]。ActiveBadge系统的用户携带的红外线发射终端设备每隔15秒向外发出一个全局标识号，当固定在室内的红外线接收设备收集到此类信号时，即可估计出携带着发射终端设备的用户所在的房间，因此该系统的定位精度只能达到房间级别。基于红外线的室内定位技术受视线约束，传播距离较短，易受环境干扰且需要部署专用于定位的信号发射设备和信号接收设备，系统的可扩展性较差，总体定位性能较差，应用范围(2)基于超声波技术的室内定位基于超声波的室内定位技术的原理是，通过测量超声波来估算信号的传播距离，进而通过三角定位等方法估计待定位节点所在的位置，代表的系统如ActiveBat系统、Cricket系统[34-35]。ActiveBat系统致力于结合无线电与超声波技术的研究，通过测量超声波的传播时延来确定传播距离，需要事先在天花板上设定好信号接收器的位置，然后按照设定好的位置安装信号接收器，待定位节点则必须配置相应的ActiveBat标签。ActiveBat具有非常高的定位精度，定位误差在9cm以内的概率高达95%。Cricket实际上是ActiveBat系统的一种改进，属于分布式的定位系统。Cricketv2版能够为移动用户端提供包括位置标识符、空间坐标和方向的多层次位置信息。在隐私保护方面，Cricket使用移动接收端来承担计算任务，可以更好的保护用户隐私。然而，基于超声波的室内定位技术受限于硬件设施和接收器的摆放位置，虽然有较高的定位准确率，但难以部署、不易于扩展、成本高，适用于对定位精度要求很高，但定位范围较小的特定环境，如仓储管理中对贵重物品的精确定基于射频标签技术的室内定位基于射频标签的室内定位技术的原理是，射频标签与读写器以非接触的方式进行数据传输，读写器通过射频标签的位置电子编码来确定携带着该标签的待定位节点的位置，代表的系统如ZebraTechnologyCompany设计的WhereNet定位系统[9]。WhereNet系统旨在提供室内和室外的实时定位，使用RFID来标识待定位节点并利用信号到达时间差(DifferentialTimeofArrival,TDOA算法来计算各个标签的相对位置和绝对位置。基于射频标签的室内定位技术依赖于专用的基础设施，系统可扩展性较差。基于超宽带技术的室内定位-7超宽带技术是基于极窄脉冲的无线电技术，具有GHz量级的带宽，不受视距传播约束，代表的系统如由AT&TCambridge超宽带技术是基于极窄脉冲的无线电技术，具有GHz量级的带宽，不受视距传播约束，代表的系统如由AT&TCambridge的工程师建立的UbisenseCompany设计的Ubisense系统[36]Ubisense系统使用信号到达时间差和信号到达角来计算待定位节点位置，可以在三维空间中提供15cm左右的定位精度。基于图像处理技术的室内定位基于图像处理的室内定位技术可用于在复杂室内环境下识别和定位待定位节点，不需要待定位节点携带任何特定设备，且能提供更丰富的基于位置的信息，如“张三正在坐在沙发上喝水”。代表的系统如MicrosoftResearchGroup设计的EasyLiving系统[37]。Wi-Fi技术的室内定位基于Wi-Fi的室内定位的基本原理是，Wi-Fi接入点(AccessPoint,AP)向周围周期性地发射无线信号，标识自己并广播自身的无线网络信息，包括无线信号强度、服务集标识码(ServiceSetIdentifier,SSID)等信息。待定位节点通过扫描周围的Wi-Fi信号，获得周围AP的无线信号信息，然后根据定位算法利用这些信息估算处相对位置信息，代表的定位系统如MicrosoftResearchGroup设计的RADAR定位系统。RADAR系统利用已有的Wi-Fi基础设施，先构建一张射频指纹地图(RadioMap)，当待定位节点采集到一个实时Wi-Fi信号向量后，使用信号空间最近邻法(NearestNeighborinSignalSpace,NNSS)在射频指纹地图中找出与该Wi-Fi信号向量的欧氏距离最小的参考点作为待定位节点的位置估计。RADAR系统在二维空间上定位精度达到4m的概率约50%[38]。RADAR系统开启了基于位置指纹室内定位的先河，国内外诸多学者对这种定位算法进行广泛而深入的研究。主要研究工先介绍了室内定位技术的发展现状，对不同定位技术进行了分类并介绍各自的基本原理以及特点。选择了部署成本低、定位精度较高、复杂度较低的KNN位置指纹定位算法作为本文的研究基础。针对如何提高基于位置指纹的KNN算法的定位精度，提出基于局部加权回归射频指纹地图校正的LWR-KNN算法。在待定位区域采集的少量的参考点位置指纹后通过一种搜索算法得出局部加权回归模型中的参数，然后通过局部加权回归对射频指纹地图进行校正，以期提高KNN算法的定位精度。针对如何提高基于位置指纹的KNN测以及信号空间距离修正的Robust-KNN-8生故障或被恶意损坏的情况下仍提供较可靠的位置估计。同时提出一种丢失接入点搜索的SLAP算法，在定位系统中部分接入点丢失的情况下，通过SLAP生故障或被恶意损坏的情况下仍提供较可靠的位置估计。同时提出一种丢失接入点搜索的SLAP算法，在定位系统中部分接入点丢失的情况下，通过SLAP算法对丢失接入点进行搜索，以期提供一个丢失接入点集合来辅助定位系统排查异常。在实际的室内环境下采集位置指纹，并在MATLAB中对采集的数据进行处理，LWR-KNN算法、Robust-KNN算法以及SLAP算法进行实验，以期通过实验结果来论证算法的可靠性。论文结第一章：绪论。先对本文的研究背景及意义进行了简短说明；紧接着又介绍了本课题国内外的研究现状；最后简单地介绍了本文的主要工作、文章结构安排以及创新点。第二Wi-Fi室内定位概述基Wi-Fi的室内定位技术进行分类述各类定位方法的基本原理、技术特点以及适用范围，指出基于位置指纹的定位技术具有很大的研究和实用价值，并以该技术作为本文的主要研究对象；然后对基于位置指纹的定位技术的基本原理进行详细分析；最后给出定位技术的评价指标，从中选取定位性能和定位系统鲁棒性作为研究方向。Wi-FiWi-Fi室内定位系统的精度进行Wi-Fi室内定位研究，针对如何提高Wi-Fi室内定位系统的鲁棒性第五章：全文总结与展望-92Wi-Fi的室内定位技基于Wi-Fi的室内定位技术以其经济性好、易于部署、使用方便等优点，成为目前室内定位技术研究的热点。本章介绍目前该技术的主要原理，为进一步的研究提2Wi-Fi的室内定位技基于Wi-Fi的室内定位技术以其经济性好、易于部署、使用方便等优点，成为目前室内定位技术研究的热点。本章介绍目前该技术的主要原理，为进一步的研究提供理论基础。本章对基于Wi-Fi的室内定位技术进行分类，阐述各类定位方法的基本原理、技术特点以及适用范围，指出基于位置指纹的定位技术具有很大的研究和实用价值，并以该技术作为本文的主要研究对象；然后对基于位置指纹的定位技术的基本原理进行详细分析；最后给出定位技术的评价指标，从中选取定位性能和定位系统鲁棒性作为研究方向。基于Wi-Fi的定位算法分类Wi-Fi几何定位几何定位利用待定位节点与AP之间的距离或AP信号到达待定位节点的角度，根据几何学的原理估算移动终端的位置，包括三边测量法、三角测量法和混合定位法三类。(1)三边测量法2-三边测量法原理图Figure2-1Diagramofthe-102-1Axaya、B(xb,yb、C(xc,yc，其中(xi,yi为参点的坐标，测得待定位D到2-1Axaya、B(xb,yb、C(xc,yc，其中(xi,yi为参点的坐标，测得待定位D到参考AB、C的距离分别为da、db、dc，设待定位节点D的坐标为(x,y)。在理想情况下，当测得待定位节点到一个参考点的距离d时，可认为待定位节点在以该参考点为圆心半径为d的圆上，则待定位节点与三个参考节点的距离后可以由三个相交xxy 2aaaxxy 2bbbxxy 2ccc由式(2-1)D2xx 2yy xxyyd x ac a 2xbxc yyxxyyd b 由式(2-2)可见，在xiyi已知的情况下，测量得到da、 APAP信号的度量指标进行转换得到的。常用的度量指标包括时间(TOA,TDOA)和接收信号强度RSSI传播速度即可估算出待定位节AP之间的距离，进而根据式(2-2)估算目标位置坐标；RSSI测量的三边定位则利用测得的接受信号强度，根据信号传播模型推算出待定位节点AP的距离，进而根据式(2-2)估算目标位置坐标，其关键在于如何得到一个普适性可得到如式(2-4)所表示的对数-常态分布模型[39]dP(d)P(d 10 0 d0-11P(d P(d 10nlgdP(d P(d 10nlgdd 000，均方差为的高斯随机变量，其取值范围为410其中，X为均值为路径损耗系数，根据不同环境其取值n5。Pr(d)Pr(d0分别表示距离和(d0一般作为参考距离1米处的信号强度值是与硬件相关的，可以根据实际测量来获得，然后根据式(2-4)可以计(2)三角测量ngleofrivl,)来定位，其中参考点预先设定，使用特定方法测量待定位节点到参考点的角度进而通过角度关系估算出待定位节点的位置坐标。2-2A、B的坐标xa,ya，xbybD的坐标为xy2-2三角测量法原理图Figure2-2DiagramoftheDA的角度为DB的角度为yaytan(xa式(2-ytan(xb由式(2-5)D-12y1y2tanx1tantany1y2tanx1tantantanx式(2-y1212tantanAOA的定位方法早已经应用在飞机导航等室外定位服务中，但是在室内定位方AOAAOAVOR室内定位系统基于地面传输信号的AOA的测距方法能够重复广播两种信号脉冲，且不依赖于信号采样的密度AOA值便可以进一步进行位置估计[41]。此外基于AOA的定位算法可以利用阵列天线，在同一个方向上测量阵列天线的RSSI并记录其角度，利用这RSSI以及角度的分布信息，进一步定位出待定位节点的位置。这种方法不仅提高了定位的准确度，同时可以减少定位时需要的AP数目。(3)混合定位方VenkatramanTOAAOA结合的定位方法，研究室内环境下非视距条件下的定位结合TOA和AOA的信息，实现对待定位节点的位置估计[44]。樊玉凤等则提出了一种将RSSI和波束切换智能天线相结合的联合定位算法[45]。 最大似然估计定位法kAPk3AP坐标为(xiyii1,2,3。设待定位节点D的坐标为(xy。通过任意一种测距方法测量得到D到各个APdi,i1,23,...k-132-3最大似然估计法原理图Figure2-3Diagramofthemaximumlikelihoodxxyy222111xxyy2222222-3最大似然估计法原理图Figure2-3Diagramofthemaximumlikelihoodxxyy222111xxyy222222xxyy222kkkx2y1yky2x2x2y2y2d2d xx2x2y2y2d2d,x,bA xyx y2y2d2 2yk k kk k k k在实际测量中存在测量误差ex2b对测量误差exxdex2AATx2Ab1-14近似定位近似法也叫最近AP法，类似于移动蜂窝网络定位中的Cell-ID近似定位近似法也叫最近AP法，类似于移动蜂窝网络定位中的Cell-ID定位法，根据待定位节点与一个或多个位置已知的物体的临近关系来进行位置估计。如图2-4Z1、Z2、Z3均为已知位置的区域，当待定位节点DZ1，就可以用Z1的位置来近似D的位置。在WLAN环境下，接入点是链接用户从无线通讯到有限通讯的桥梁，各接入点都有一定的信号覆盖范围，进入这一信号区域的待定位节点都可以通过与它连接实现网络。近似法的实现是通过接入点的位置来大致估计待定位节点的位置的，所以无需额外的硬件设备，实现简单，但在定位性能很大程度依赖于接入点的连接性能、覆盖范围、接入点位置信息的准确性。现有的民用的地图导航类应用，如高德地图，在已经收集到丰富的接入点数据库的基础上就会使用这种定位技术来对用户进行位置估计。但是这种定位技术的定位精度较低，通常只能适用于对精确度要求不高的场合或作为其他定位技术的辅助技术进行粗定位。2-4近似法原理图Figure2-4Diagramofthe位置指纹定位基于位置指纹的定位算法一般分为离线阶段(或称数据采集阶段)和在线定位阶段(或称实时定位阶段)，离线阶段定位系统将待定位区域的某些位置点作为参考点，采集各AP的接受信号强度(RSSI)-15纹都唯一对应一个位置坐标；在线定位阶段将待定位节点获得的指纹与离线阶段建立的指纹库中的指纹进行匹配，从而估计出待定位节点的位置坐标。位置指纹定位法可以利用已经广泛部署的Wi-Fi用硬件，不依赖于易受室内复杂环境影响的信号传播损耗模型，经济成本低，可以使用纯软件的方式实现，定位方法简单，能够很好的推广。 基于位置指纹的定位技术基本原理如图2-5纹都唯一对应一个位置坐标；在线定位阶段将待定位节点获得的指纹与离线阶段建立的指纹库中的指纹进行匹配，从而估计出待定位节点的位置坐标。位置指纹定位法可以利用已经广泛部署的Wi-Fi用硬件，不依赖于易受室内复杂环境影响的信号传播损耗模型，经济成本低，可以使用纯软件的方式实现，定位方法简单，能够很好的推广。 基于位置指纹的定位技术基本原理如图2-5lLixiyi,i1,...,lxiyi表示第i个参考点的二维物理空间坐标。n为待定区域AP总数，APj在i处测量对各APRSS得到一个参考数据AP的信号强度特征，对于扫描不到其烽火信号（不可见AP用一个低于网卡可识别的常量Const（本文使Const-99dBm）填充以保持对齐。然后将iri成一条记录i,ri存入指纹库。为了减少噪声和奇异值的影响，ri通常取在处多次测量的平均。在整个L上重复上述步骤以完成射频指纹库的构建。oo1o2on在在线定位阶段，在未知位置处获得一个RSSIo与ri的相似度来获得位置估 。实质上，这是将定位看作基于信号强度特征的模识别[46]图2-5基于位置指纹的定位原理-16Figure2-5Diagramofthelocationfingerprintbased指纹数据库预处理AP信号的强度特征信息以及对应的参考点的位置信息。而关于信号强度特征信息，信噪比(signaltonoiseratio,SNR)曾被UCLARobinNibble定位系统中[47]BahlRSSI比SNR具有更强的位置相关性。本文采用RSSI作为信号强度特征信息。(1)纹。于是位置指纹库中第i条指纹数据的记录可以表示为：lixi,yiFigure2-5Diagramofthelocationfingerprintbased指纹数据库预处理AP信号的强度特征信息以及对应的参考点的位置信息。而关于信号强度特征信息，信噪比(signaltonoiseratio,SNR)曾被UCLARobinNibble定位系统中[47]BahlRSSI比SNR具有更强的位置相关性。本文采用RSSI作为信号强度特征信息。(1)纹。于是位置指纹库中第i条指纹数据的记录可以表示为：lixi,yi其中rji2.12rtj Sample其中Sampleji表示在第i个采样点处接受到的第j个AP的采样数量 表示第i个rAPRSSI3.RSSI，rji表示在第ij直方图处理也是指纹数据库预处理的常见方法之一，在指纹数据库中可以将第ilixi,yiH1i,H2i,H3i,...,Hniri b, |tB,B / t1i i-17htrmax、r第tjAPjAPRSSI位置指纹定位算法基于位置指纹的Wi-Fi定位算法分为确定型定位算法和概率型定位算法两大类。确定型的位置指纹定位算法通常利用RSSI采样数据建立指纹库，主要包含k最近邻法、人工神经网络法和支持向量机法；概率型的位置指纹定位算法通常通过概率论方法建立指纹映射，并通过概率数据分析进行位置估计，主要为贝叶斯决策法。K最近邻法K最近邻法(KNearestNeighbors,KNN)算法是机器学习中比较成熟的方法，在模式识别领域中是一种无参数的分类回归方法，基于特征空间中的K个最相近邻的训练样本来预测对象值或划分类成员关系。算法的主要思想是一个对象通过它邻居的多数表决来确定分类结果，即该对象会被划分到与它最相邻的K个邻居所属的类中，当K=1时，即退化为最近邻法(NearestNeighbor,NN)，选择最接近的邻居对象所属类作为分类结果。人工神经网络法人工神经网络是一种类似于生物体神经网络的构造的计算模型，在机器学习和模式匹配领域广泛应用[48]。人工神经网络的学习过程就是通过训练样本对网络中每一层的权重进行校正而建立模型的过程，使得所得到的模型最终能够对给定的输入获得预测的结果，其中BP(ErrorBackPropagation)算法是目前最常用的学习算法之一，BP神经网络的典型三层结构模型如图2-6所示。BP算法主要分为数据的正向扩散阶段和差值的逆向传播阶段。在数据正向扩散阶段中，对于输入层传入的学习数据经隐藏层处理后，将由输出层得到的预测结果与真实结果比较，得到训练差值，如果训练差值超过限定值，则进入到差值反向传播过程。误差的反向传播是将训练差值通过隐藏层向输入层以某种形式逆向传播，并将误差分别分给每一层的网络单元，这样就得到每个单元的差值数据，该差值数据用来不断完善各个单元的权重。这种数据正向扩展、误差逆向传播的每一层的权重修改一直循环进行，直到误差小于某一个阈值或达到预先设定的学习次数上限。人工神经网络法将室内定位问题看成一个利用位置指纹模型对实时RSSI向量的分类问题，通过对离线阶段采样指纹和位置关系模型的训练学习来建立指纹库。人工神经网络法相比于KNN算法的定位精度略高，-18但算法的缺点是对匹配模型的训练学习时间较长，而且需要大量的样本数据，计算复杂度也较高。2-6BP神经网络三层结构模型Figure2-6Threelayer但算法的缺点是对匹配模型的训练学习时间较长，而且需要大量的样本数据，计算复杂度也较高。2-6BP神经网络三层结构模型Figure2-6ThreelayerBPneuralnetwork支持向量机法支持向量基(SupportVectorMachine,SVM)是一种基于统计学的机器学习方基于VC维理论来获得学习机最好的泛化能力，使得在有限的统计样本量中能得到较准确的统计规律。基于SVM的室内定位算法在离线采样阶段将地图划分成网格区域，将每个网格作为SVM的一类。通过每个网格采集的各APRSSI来构建基于网格的位置指纹库，并作为SVM的训练样本，建立SVM分类模型[49]。在在线定位阶段，待定位节点将接收到的RSSI向量作为输入，利用SVM在离线阶段得到的分类模型得到分类结果从而得到位置估计。基于SVM的定位算法的优势在于能够在训练样本有限的情况下，建立RSS指纹到位置信息的非线性映射关系，且SVM将定位问题看做分类问题，非常适合房间级别的室内定位场景[50]。但是SVM理论本身较复杂，实现难度较大。贝叶斯决策法贝叶斯决策法与基于SVM的定位算法类似，将指纹库按照每个采样点划分成若干类，但与其不同的是，贝叶斯决策法用概率性的算法来判断待定位节点实时接收到的RSSI向量所属的类，从而估算待定位节点的位置坐标。贝叶斯决策法基于贝叶斯定理：PAPPAB式(2-PB-19在基于位置指纹的定位算法中，贝叶斯决策法首先确定在待定位区域中 Ll1l2l3llRr1r2r3rl，每组样本lRSS向量样nAPRSS样本的均值，可以表示为rr1r2r3rn在基于位置指纹的定位算法中，贝叶斯决策法首先确定在待定位区域中 Ll1l2l3llRr1r2r3rl，每组样本lRSS向量样nAPRSS样本的均值，可以表示为rr1r2r3rn；在线阶段定位时，待定位节点收到来自nAP值作为一个观测值叶斯决策法可以计算出观测值o在指纹库中每个采样点出现的概率，即P根据贝叶斯定理可以推导出：oPoliPliPoPoliPliPo式(2-PoliPlili为在采样点li处采集到的RSS向量为o的概率，Pli为位置liPAPRSSPoliPo1liPliPli最后将后验概率最大的采样点作为位置估计的结果，即位置估计可表示为o在实际复杂场景下，P的计算可能需要通过大量的训练样本来得到较为准确Pli[51]1Plexpj1i应用场景定义模型参其中核方法需要确定，而直方图法中需要确定划分区间的大小室内定位技术评价指(1)安全性和隐私-20成GPS24Wi-Fi的室内定位系统来说，由于可以复用已WLAN基础设施，基础设施成本低。用户端成本通常指的是定位系统提供定位服务Wi-Fi的定位系统不需要额外部署传感器，使得部署和维护成本较延指的是从采集位置特征到估算出待定位节点位置再到将位置估计结果返回给用户所需的总时间。定位时延之所以作为评价定位性能的一个重要指标是因为：如果待定位节点在常定义为一个定位系统在给定的定位基础设施下能同时为其提供定位服务的待定位节点的数量。鲁棒高鲁棒性的定位系统指的是在定位系统的部分基础设施发生故障或者待定位区域环境发生变化时，仍能够进行可靠的位置估计的能力。基于红外线的定位技术依赖于待定位tiveadge-21复杂复杂Wi-Fi的定位系统可以利用已经广泛覆盖的用于通WLAN环境，可以通过少量的人工校正，如基于位置指纹的定位技术的离线采样，定位技术的用户友好性以及是否已经存在商业化的产品等方面都是评价其优劣的指标。如一个定位技术已经有较为成熟的商业化产品，则研究人员可以购买其定位系统并部署，进一步地研究其原理和存在的不足，以改进此定位技术。本章小本章对基于Wi-Fi的室内定位技术进行分类，阐述各类定位方法的基本原理、技术特点以及适用范围。基于位置指纹的定位技术由于其部署容易、定位性能高等特点具有很大的研究和实用价值，本文将这种定位技术作为研究对象。对基于位置指纹的不同定位算法做了简要介绍，并选取计算复杂度低的KNN算法作为本文的算法研究基础。定位技术的评价指标包含安全性、成本、性能、鲁棒性、复杂度等，各个指标之间存在相互联系、相关制约的关系。定位性能和定位系统鲁棒性作为最优考虑的两个指标，将成为本文的研究方向。-223高精度的Wi-Fi室内定位算法研究算法研究基如式(3-1)，KNN算法通常使用信号空间欧式距离来计算相似度，Di越小相似度越高。根据Di对指纹库中的3高精度的Wi-Fi室内定位算法研究算法研究基如式(3-1)，KNN算法通常使用信号空间欧式距离来计算相似度，Di越小相似度越高。根据Di对指纹库中的i,ri进行升序排序，并取前K个参考点的坐标根据Di加权平均得到位置估计ˆ，按式(3-2)和式(3-3)计算。noj2Di式(3-jK式(3-Dω式(3- DjjK通过多次实验选取一个最优值。值得一提的是，当K=1时，该算法退化为信号空间最近邻法(NearestNeighborinSignalSpace,NNSS)[7]；当K1i1K时，该算法退化为非距离加权的KNN；当为一个基于距离的加权函数时，KNN演进成DW-KNN(DistanceWeightedKNearestNeighbor,DW-KNN)。本文采DW-KNN作为研究基础，所述KNN均指DW-KNN，且固定K值为一个常数(K=3)基于局部加权回归的射频指纹地图校正-23AP的位置可以获得，射频信号传播模型的自适应性和可扩AP的位置，且无需构建信号传播模型，可以局部加权线性回归(LocallyWightedRegression,xi,yi,i1,2,xiAP的位置可以获得，射频信号传播模型的自适应性和可扩AP的位置，且无需构建信号传播模型，可以局部加权线性回归(LocallyWightedRegression,xi,yi,i1,2,xix1,x2,x3,...,xdyixxxx '''y'1234dFxa0ai相关系数a可以通过式(3-5)Faarg wn,ii ia其中wxquery留一交叉验证法(Leave-One-Out-Cross-交叉验证是一种用来评价一个统计分析的结果是否可以推广到一个独立的数据集上的技术。主要用于预测，即用于估计一个预测模型在实际应用中的准确度。它是一种统计学上将数据样本切割成较小子集的实用方法，可以现在一个子集上做分析，而其他子集用来作为后续对此分析的确认和验证[59]。一个交叉验证将样本数据集合分成两个互补的子集，一个子集用于训练分类器或者模型，该子集被称为训练集(trainingset)；另一个子集用于验证分类器或者模型-24分析有效性，该子集被称为测试集(testingset)。利用测试集来测试通过训练集得到的分类器或者模型，以此作为分类器或者模型的性能指标，期望得到预测精确度高德预测和低的预测误差。为了减少交叉验证结果的可变性，通常将一个样本数据集合进行多次不同的划分，得到不同的互补子集，进行多次交叉验证，并取多次验证的平均值作为验证结果。在给定的样本数据集合中，拿出大部分的样本作为训练集来进行分类器或者模型的构建，留一小部分的样本作为测试集，用已经建立的分类器或模型进行预测，求出测试集的预测误差，并记录它们的平方和。留一交叉验证作为交叉验证的一种，具体的做法是：假设有N个样本，则做分析有效性，该子集被称为测试集(testingset)。利用测试集来测试通过训练集得到的分类器或者模型，以此作为分类器或者模型的性能指标，期望得到预测精确度高德预测和低的预测误差。为了减少交叉验证结果的可变性，通常将一个样本数据集合进行多次不同的划分，得到不同的互补子集，进行多次交叉验证，并取多次验证的平均值作为验证结果。在给定的样本数据集合中，拿出大部分的样本作为训练集来进行分类器或者模型的构建，留一小部分的样本作为测试集，用已经建立的分类器或模型进行预测，求出测试集的预测误差，并记录它们的平方和。留一交叉验证作为交叉验证的一种，具体的做法是：假设有N个样本，则做N验证，每次取一个样本作为测试集，其余N-1个样本作为测试集，可以得到N个分类器或模型，N个预测结果。N个预测结果的误差平均值用于衡量分类型或者模型的性能。LOOCV的每一个分类器或模型都是用几乎所有的样本训练得到的，最接LWR射频指纹地图校正如前文所述，给定一个回归模型：Fqi01xi2相关系数向量0,1,2通过式(3-7)获得式(3-arg wq,qFn式(3-iii的序号，w为权重函数，qx,y为待预测点（模拟参考点其中j为被预测的的坐标。权重函数通过计算q与各参考点qi之间的距离来分别赋予各参考点不同的权重，越接近 的参考点获得越大的权重值。本文采用高斯函数作为权重函数：wq,qi其中为控制回归模型的局部性的系数，值越大，回归模型的局部性越强，当式(3-0时，该局部回归模型退化成一个全局的回归模型；为待预测点q到第i个参考点之间的归一化距离：dqqi式(3-dqq*d为欧式距离，q*为待预测点与各参考点的距离中的最大值，当q*qi时，1-25对于每一个AP需要确定一个最优的值，从而确定一个回归模型用于预测该AP在某个待预测点的RSS值。本文采用LOOCV来进行最优的做法如下：Rli,ri,i1,2,3,...l 将离线阶段进行采样的l个位置指纹分为l其中对于每一个AP需要确定一个最优的值，从而确定一个回归模型用于预测该AP在某个待预测点的RSS值。本文采用LOOCV来进行最优的做法如下：Rli,ri,i1,2,3,...l 将离线阶段进行采样的l个位置指纹分为l其中xiyi为各个采样点的位置坐标，i个采样点得到的一AP的RSSnAPj1BadStepConst1Const2Step2:jAPl组数据作为样本集Sjliriji1,2,3ljAP在各个采样点处的RSS值与对应的位置坐标组成的l个样本，并初始化0 m1Error0；m个样本作为测试集Testmlmrmjl1Sj作为训练集Trainmlirij1ilim，并通过与Trainm按照式(3-3)、式(3-4)(3-5)、式(3-6)建立一个回归模型F，然后将TestmlmF的输入，得到一个预测2rˆF，并计算预测的误remm Errorl次的平均误差Step5，直jStep6:Step4AP在控制参数值为时回归模型的预测性能指标，越小预测性能越优；Step6:记录迄今为止的最小值及对应的最优值，然后自增的值：Step3Step6，直到连续BadStepStep6中没有更新最优取此时的最优值作为第jAP的控制参数值，然后自增j的值：jj1Step2Step9，直到jn在确定每个AP的最优值后，给定一个待预测点的位置坐标，将整个离线阶段采集的位置指纹作为训练集，可以得到每个别得到各个AP在待预测点的RSS值。对于待定位区域中选定的p个待预测点， 的一个局部加权回归模型，从而分每个待预测点nAP分别建立局部加权回归模型，即为了得到一条预测出来的位置指纹(模拟位置指纹)需要进行n次建模和预测，为了在待定位区域得到p个模拟位置指纹需要进行pn次建模和预测。预测得到的p条位置指纹数据组成一张模拟射频指纹地图，该地图与实际采集获得的射频指纹地图的并集作为KNN算法的在线定位阶段计算时使用的射频指纹-26本文称上述的最优值搜索为LWR-LOOCVLWR射频地图校正的KNN定位算法为LWR-KNN 实验及结果分析实验环境实验区域为一个约900平方米的典型室内环境，包括12本文称上述的最优值搜索为LWR-LOOCVLWR射频地图校正的KNN定位算法为LWR-KNN 实验及结果分析实验环境实验区域为一个约900平方米的典型室内环境，包括12个办公室和1个走廊。实验区域平面图如图3-1所示区域内可见AP总数为65n65。离线阶段MacBook和在线定位阶段的数据采集使用同一台简化起见，数据在中进行处理。3-1实验区域平面图3-1Layoutofthetestbed如图3-1所示，离线阶段在实验区域内共选定了100个参考点即l=100。两个最近邻参考点间距最小为1米，最大为4.8米，平均为2.5米。参考点最少有3个可见。在每个参考点以的频率采集次数据取平均得到一条参考数据与位置信息组成一条射频指纹存入射频指纹库。离线阶段完成后得到一张射频指纹地图RM-27在在线定位阶段，选取了40个测试点（含测试起点和测试终点）。每次测试由测试起点开始，以一条固定的路径在实验区域内移动，每经过一个测试点采集一个观测值并将对应的位置信息保存以便于计算定位误差，进入房间后均以原路返回。一次测试中所有测试点均被经过280个观测值，共进行了3240个观测值。 参考点密集情况下的LWR射频地图校正3-1LOOCV进行各AP最优值的搜索：将65个AP在100个参考点的位置指纹BadStepConst110，IncrementConst2在在线定位阶段，选取了40个测试点（含测试起点和测试终点）。每次测试由测试起点开始，以一条固定的路径在实验区域内移动，每经过一个测试点采集一个观测值并将对应的位置信息保存以便于计算定位误差，进入房间后均以原路返回。一次测试中所有测试点均被经过280个观测值，共进行了3240个观测值。 参考点密集情况下的LWR射频地图校正3-1LOOCV进行各AP最优值的搜索：将65个AP在100个参考点的位置指纹BadStepConst110，IncrementConst210按照LWR-LOOCVStep1至Step9APAP的最优值如表3-13-1参考点密集情况下部分AP的最优Table3-ofalphavaluesin123AP0如图3-152个模拟参考点，各模拟参考点通过选取部分实际采样参考点之间较稀疏的两点之间的中点获得。将每个模拟参考点作为待预测点，将总体样本集R作为训练集，根据Alphas与LWR算法得到模拟参考点的RSS向量。值得一提的是，在通过LWR模型进行预测时，可能会出现预测值小于-99dBm的情况，此时取预测值为-99dBm。将模拟参考点位置信息与通过LWR模型得到的RSS向量建立成一张模拟射频RMsRMs与离线阶段实际采样得到的RM的并集作为在线定位RMRMRMs。通过KNN算法对所有测试点进行位置估计，得到的结果如图3-2和表3-2所示。表3-2参考点密集情况下的定位误差比3-2the定位算法LWR---3-2参考点密集情况下的累积误差分布Figure3-2Cumulativeerroroftheintensive由图3-2和表3-2可以看出，LWR-KNN的累积误差分布在定位误差3.803-2参考点密集情况下的累积误差分布Figure3-2Cumulativeerroroftheintensive由图3-2和表3-2可以看出，LWR-KNN的累积误差分布在定位误差3.80米以内始KNN，但差别较小LWR-KNN定位算法的平均定位精KNN算法有较小提高，平均定位误差减小了0.30米。但在参考点密集情况下，LWR-KNN算法对定位精度的改善并不显著，那是否说明LWR校正对改善定位精度并没有明显效果呢？来看接下来对参考点稀疏的情况下KNNLWR-KNN的对比。参考点稀疏情况下的LWR射频地图校为了模拟参考点选取较稀疏的情况，将离线阶段选取的参考点进行稀疏化。在待定位区域的各个房间内仅保留13个参考点的位置指纹，且优先选择靠近房间几何中心的参考点进行保留，得到25个保留参考点；将非保留参考点的位置指纹从RM中移除，得到一张仅包含25条位置指纹记录的射频指纹地图RMr若用平均每平方米参考点个数来描述参考点的密集程度，如式(3-SparityCcalibration_points式(3-SCcalibration_point为待定位区域总参考点个数，S为待定位区域总面积，则在进行参其考点稀疏化前，待定位区域的参考点密集程度为 ，稀疏化后的密集程度为2.78%，仅为原来的密集程度的25%将稀疏化后得到的射频指纹地图RMr的一组新的最优Alphasi,i1,2,3,...,n，部AP的最优值如表3-3-293-3参考点稀疏情况下部分AP的最优Table3-PartthealphavaluesinthespareAP12300003-1中所示的52LWR预测，得到一张新的模拟射频指纹地图，记作RMs。将RMs与稀疏化采样点后得到的3-3参考点稀疏情况下部分AP的最优Table3-PartthealphavaluesinthespareAP12300003-1中所示的52LWR预测，得到一张新的模拟射频指纹地图，记作RMs。将RMs与稀疏化采样点后得到的的并集作为在线定位阶段的射频指纹地图，记作RMRMrRMs。重新对所有测试点进行位置估计，到的结果如图3-3和表3-4得3-3参考点稀疏情况下的累积误差分布Figure3-3Cumulativeerrordistributionofthespare3-3可以看出，在参考点稀疏的条件下，LWR-KNN算法较KNN算法的累计误差分布改善显著。LWR-KNN算法的定位误差以高达90%的概率小于5.00米，KNN算法的定位误差小于5.00米的概率仅为60%，若以5.00米作为最大可接受则LWR-KNN较KNN算法的定位精度提高了50%表3-4参考点稀疏情况下的定位误差比Table3-4ofthe定位算法LWR-由表3-4可以看出，LWR-定位算法的定位误差最小值、最大值、平均值、中值以及均方差都小于KNN算法。从平均定位误差来看，LWR-KNN算法在参考-30点高度稀疏的情况下，仍保持较高的定位精度，平均定位误差为2.57米，而同等情况下的KNN算法的平均定位误差高达4.32点高度稀疏的情况下，仍保持较高的定位精度，平均定位误差为2.57米，而同等情况下的KNN算法的平均定位误差高达4.32米，相比之下，LWR-KNN算法的定位精度改善了1.75米，高达41%。可见，在参考点稀疏的情况下，LWR-KNN算法可以显著地提高定位精度。作为扩展的，LWR射频指纹地图校正可以用于减少离线阶段采集位置指纹的工作量，通过少量的实际采样的参考点位置指纹，可以通过LWR射频指纹地图校正来提供模拟参考点位置指纹。本章小本章针对如何提高基于Wi-Fi室内定位系统的定位精度进行了研究，以KNN算法作为研究基础，提出了LWR-KNN定位算法，通过已有指纹库中的位置指纹数据对各个AP进行LWR-LOOCV最优回归模型参数搜索，然后对模拟参考点进行LWR预测得到多个模拟位置指纹。实验结果表明，模拟位置指纹的引入，扩大了原有的射频指纹地图，在参考点密集的情况下可以较小地提高KNN算法的定位精度，在参考点稀疏的情况下可以显著地提高KNN算法的定位精度。LWR射频指纹地图校正法可以用于改善定位精度的同时，还可以用于减小离线阶段采集参考位置指纹-314高鲁棒性的Wi-Fi室内定位算法研本章针对如何提高Wi-FiAP信号丢失的情况下仍可以提供可靠的位置估计时，认为这种算法是具有强鲁棒性的。以KNN算法的基础上提出增强鲁棒性的KNN算法(Robust-KNN)，期望达到以下两个目的：在部分AP丢失的条件下仍可提供可靠的位置估计；当系统存在异常时，可以确定一个异常AP4高鲁棒性的Wi-Fi室内定位算法研本章针对如何提高Wi-FiAP信号丢失的情况下仍可以提供可靠的位置估计时，认为这种算法是具有强鲁棒性的。以KNN算法的基础上提出增强鲁棒性的KNN算法(Robust-KNN)，期望达到以下两个目的：在部分AP丢失的条件下仍可提供可靠的位置估计；当系统存在异常时，可以确定一个异常AP集合，为系统排除异常提供参考。异常条自微软提出RADAR定位算法的精度和减小离线训练的工作量进行了研究[60-64]，针对如何增强定位系统的鲁棒性的研究较少[65-68]。但在某些异常条件下，例如定位阶段某些AP的信号发生大幅度波动甚至丢失（待定位节点扫描不到 发出的烽火信号），定位算法的定位精度将发生明显衰减，文献[65]的作者通过实验证明了这一点，并在文献[66]中提出通过显著性检验来检测恶意攻击，但并未给出在检测到恶意攻击后仍提供可靠的位置估计的方法；文献[67]通过使用基于中值的最近邻法(Median-NNSS)并引入冗余节点来防止异常情况下定位精度的大幅下降；文献[68]提出的系统通Mica2节点来检测节点（接入点）异常，并使用自适应的距离参数，但该方法依靠接入点来检测异常，不适用于一般WLAN环境。本文将异常限定为AP信号的丢如前文所述，KNN算法使用信号空间欧式距离来计算相似度，Di越小相似度越高。根据Di对指纹库中的i,ri进行升序排序，并取前K个参考点的坐标根据Di加权平均得到位置估计ˆ，按式(3-2)和式(3-3)计算。定义观测值o值不为Const的（可见）Aoi处参考数RSSConstriAPAriA，可将式(3-AP通常只能覆盖待定位区域的一部分，所以重写为式(4-1)A，iDi2dijdij式(4- dr -32假设在离线阶段，在参考点125一个指纹库如表4-1RSS数据，然后建立 表4-1射频指纹库举 12345---------假设在离线阶段，在参考点125一个指纹库如表4-1RSS数据，然后建立 表4-1射频指纹库举 12345------------最近邻的Unknown1处获得观测值30304-2，信号空间上的Di将得到一个正确的参考点排序24513最近邻点为r2，若按式(4-1)后根据式(3-2)和式(3-3)将得到一个可靠的位置估计。 表4-2观测值举 AP2 --- - - Const30,69，若仍按式(4-1)计算Di，AP1将进入AoD22到错误的参考点排序3,5,1,4,2，此时将造成定位误差大幅增大。本文在原始观测值中将丢失APAP并不会影响所有观测值，例如处的观测值为Const60,30AP1丢失对这个观测值没有影响。为便于描述，在考虑异常条件对定位算法精度的影响和检测异常时，将在观测值的角度上对Ao丢失AP时，将使Unknown1处观测值中AP1Const而使Unknown2处观测值中AP2为Const此时对这两个观测值来说分别是33%50%AP丢失。传统算法定位精度变定义定位误差为实际位置与位置估 在物理空间上的欧式距离，式(4-不为整数的情况进行高斯取在每个观测值中引入%的丢失APKNN算法的定位误差的均值和标准差变化如图33中的误差棒表示标准差。4-1KNN在异常条件下定位误差大幅增大。20%时平均定位误差增大至4.21米，相比非异常条件下增大了96%AP丢失比例增大-33时，平均定位误差还在持续增大，当%时，平均误差高达14.70米。而对于所有观测值来说，20%AP丢失最多仅2AP丢失时，平均定位误差还在持续增大，当%时，平均误差高达14.70米。而对于所有观测值来说，20%AP丢失最多仅2AP丢失（13个可见AP丢失能力的定位算法是必要的。图4-1异常条件下传统KNN的定位误差变化算法描本文提出的Robust-KNN算法先进行接入点筛选，然后在传统KNN算法基础上进行异常检测、信号空间距离修正以及丢失AP搜索。先对各部分分别进行描述，然后给出算法在在线定位阶段的工作流程。接入点筛不稳定AP不仅不会改善定位精度反而会降低定位精度，所以先对AP进行筛选[6][10]。这里仅根据AP在指纹库中出现的次数进行筛选，给定一个阈值一个AP在指纹库中出现的次数小于时，将其在指纹库中剔除，在线定位阶段该AP不参与匹配计算。本文选取8小于参考点个数的10%)，经过筛选后，n34。如图4-2所示，虽然射频指纹的维度由原来的6534，但是定位误差并无明显衰减（与文献[6]中得出的结论一致）。-34图4-2筛选AP前后累积误差分布AP筛选为搜索丢失AP奠定了一定基础，因为若一个AP在指纹库中出现次数过AP丢失时，将没有足够信息来确定该AP是否已经丢失。异常图4-2筛选AP前后累积误差分布AP筛选为搜索丢失AP奠定了一定基础，因为若一个AP在指纹库中出现次数过AP丢失时，将没有足够信息来确定该AP是否已经丢失。异常检测定义在Lo中的最近邻点，异常状态指示变量为S，检测正确率为所有的异常观测值中被正确地检测为异常的比例，误检率为所有非异常观测值中被错误地检测为异常的比例。R中一个元素可视为n维信号空间上的一点，而R可视为信号空间上这些点的集合。假设在信号空间上R被拟合成一个n维曲面Surface（当然，并不需要得到这个曲面），o也对应信号空间一点。因为在L上总可以找到一点与o的获取位置的距离为零或者在一定范围内，所以非异常条件下o在Surface表面或者到Surface的最短距Dmin在一定范围内；在异常条件下Dmin将增大至超过一定阈值oAP比例越大，Dmin的增大越明显，本文称Dmin的这种变化为信号空间畸变，Dmin可o中存在or之间的信号空间距离来近似。当则AP丢失，S 式(4-false,if -35KNN中是已经得到了的，于是只需确定阈值即可完成异常检测机制Dmin的建立，可由实验手段根据非异常条件下的累积分布选取。一次测试的个观测值在非异常条件和异常条件下的KNN中是已经得到了的，于是只需确定阈值即可完成异常检测机制Dmin的建立，可由实验手段根据非异常条件下的累积分布选取。一次测试的个观测值在非异常条件和异常条件下的Dmin4-3所示(AP后)4-3可见，当观测值中存在APDmin的累积分布曲线向右移动，丢比例越大右移越明显。若取25dBm，则当观测值中5%、10%、15%、20%30%、40%、50%的AP丢失时，理论上将分别以28%、50%、81%、96%、100%100%、100%的正确率检测到，对应的误检率为3%。当减小时，检测正确率将增大，但误检率也增大。值得一提的是，文献[66]恶意放大或衰减，本文所提的AP丢失是信号衰减的一种特例。AP信号被图4-3AP丢失造成的信号空间畸变本文最终选择25dBm5%10%AP丢失的检测正确率较小，但由图4-1可以看出5%10%AP丢失对定位误差的影响也相对较小。信号空间距离修正当观测值中存在AP丢失时，如果仍通过式(4-1)计算信号空间距离Di，则丢失AP将有可能进入集合ArAoDi进行排序得到的K个最近邻点不再可靠。所以当StrueDi进行修正，修正后的Di如式(4-4)所示。Didij式(4-APjAri式(4-4)将式(4-1)中的第二项移除，防止丢失APDi的排序。Ar\Ao位置估计仍按式(3-2)和式(3-3)计算。虽然式(4-4)对不同位置的射频指纹的区分能力-36较式(4-1)oAP丢失比例在一定范围内时，式(4-4)足够区分不同位置从而提供可靠的位置估计，代价是修正信号空间距离后需要重新计算一次Di丢失APAPAr\Ao不断更新各AP的丢失可能性，逐渐确定丢失AP集合，本文称这种搜索为SLAP(SearchLostAccessPoint,SLAP)算法。值得一提的是，这里是从系统的角度考虑丢失AP。丢失可能性集合Plostp1p2pn在线定位阶段开始时初始化一个p较式(4-1)oAP丢失比例在一定范围内时，式(4-4)足够区分不同位置从而提供可靠的位置估计，代价是修正信号空间距离后需要重新计算一次Di丢失APAPAr\Ao不断更新各AP的丢失可能性，逐渐确定丢失AP集合，本文称这种搜索为SLAP(SearchLostAccessPoint,SLAP)算法。值得一提的是，这里是从系统的角度考虑丢失AP。丢失可能性集合Plostp1p2pn在线定位阶段开始时初始化一个pi1AAP均有可能丢A已丢失的可能性。初始化失且丢失可能性相等。oO ,j1,2,...其中 , ,..., 每得到一个观测值 都需要更 PjjjjSfalse(4-5)Strueˆj与前一次位置估计ˆj1不同时，按式(9)更新。pi0ifAPi式(4-jifAPi0j式(4-ppiifAPA\iijj其中A表示 的信号空间最近邻点r的可见AP集合jj式(4-5)中仅将本次观测值的可见APpi置零，因为假定异常检测机制是有效的，则当Sfalse时，说明oobs没有受到丢失AP的影响，即oobs没有携带丢失j仅用于确定未丢失AP是合理的。j有关的信息，那么j式(4-6)oobs的可见AP的对应的丢失可能性置零。当Strueoobsjj到了丢失AP的影响，所 \Aobs中的AP已丢失的可能性较大。但是并不能确 AP全都是丢失AP，而且并不能保证式(4-4)一定可以找出正确的r\Ajˆj1)来oj1，然后通过多处观测值ˆArAobsAPojPlost中的值，这也使得SLAP算法仅在待定位节点不断移动时才有效。给定一个AP丢失确认阈值，则获取若干不同位置处的观测值后，可以得到一APi|pi。系统可以通过实时监控或者定时查询AlostAP-37空来辅助排除异常。本文取8，以保证理论上至多在所有参考点均被作为一次最近邻点后SLAP就可以找到丢失AP算法工作流4-4给出了Robust-KNN算法的流程图，在提供位置估计的同时，SLAPPlost中元素的值。每获取一个观测值，先通过式(4-1)Dmin空来辅助排除异常。本文取8，以保证理论上至多在所有参考点均被作为一次最近邻点后SLAP就可以找到丢失AP算法工作流4-4给出了Robust-KNN算法的流程图，在提供位置估计的同时，SLAPPlost中元素的值。每获取一个观测值，先通过式(4-1)Dmin新Di，然后通过判SStrue时，通过式(4-4)否大于异常检测阈值来设置行位置估计。Di图4-4Robust-KNN 算法结果及分析非异常条件下算法结果在非异常条件下对KNN算法（AP后）Robust-KNN算法的定位误差进行实验，得到结果如表4-34-非异常条件下传统KNN与Robust-KNN定位误差3数均值最小值中值最大值Robust-4-3可见，非异常条件下，Robust-KNN算法的定位误差相比传统KNNAlostPlost元素除p161-38异常条件下算法结果首先，通过在240个观测值中引入丢失APKNN异常条件下算法结果首先，通过在240个观测值中引入丢失APKNN算法（AP后）Robust-KNN算法的平均定位误差变化如图4-5所示。每个观测值发生%的AP丢失并不等同于系统的%个AP丢失，本文用这种方式来验证Robust-KNN的鲁棒性，而不关心这种设置下SLAP