毕业设计-基于地磁指纹的室内定位系统设计与实现

盐城师范学院毕业设计毕业设计基于地磁指纹的室内定位系统设计与实现学生姓名学院专业班级学号指导教师2016年05月30日PAGEIV基于地磁指纹的室内定位系统设计与实现摘要当前，人们对定位服务的要求越来越高，其中基于手机中地磁传感器的室内指纹定位技术受到研究人员的广泛关注。然而，目前大多数基于手机移动定位的方法精度不够理想，同时还需要限定手机移动的方向，这使得它们的鲁棒性和实用性较差。本文设计了一个基于启发式粒子滤波的室内定位系统Maloc。首先，采用动态步长估算算法来最小化动作上的误差并提高粒子滤波的稳定性。然后，结合磁强指纹模型和已有的幅值指纹模型设计了混合型测量模型，来改善系统性能，避免不同型号手机磁力计的校准问题。最后，提出重采样模型实现启发式粒子重采样，改进了传统的粒子滤波算法精度。同时，针对运动估计中存在的问题，本系统提出一个定位错误检测机制来解决“KidnappedRobotProblem”。实验结果表明，本系统可以实现精度为0.8-1.2m内的室内定位。【关键词】室内定位；地磁；粒子滤波；指纹定位

DesignandImplementationofIndoorLocalizationsystembasedonMagneticFingerprintingAbstractAtpresent,peopleareincreasinglydemandinginthequalityoflocation-basedservices.Amongthem,theindoorfingerprintlocalizationtechnologybasedonthegeomagneticsensorinthemobilephoneiswidelyconcernedbyresearchers.However,mostofthecurrentmethodsbasedonmobilephoneaccuracyisnotidealandalsoneedtodefinethedirectionofmobilephone,whichmakesthemlessrobustandpractical.Inthispaper,anindoorlocalizationsystembasedonheuristicparticlefilterisdesigned,Maloc.Insideit,severalinnovationsaremadeonthemotionmodel,themeasurementmodelandtheresamplingmodeltoenhancethetraditionalparticlefilter.Theparticlefilterisaugmentedwithadynamicsteplengthestimationalgorithmtominimizeerrorsinmotionestimationandimprovetherobustnessofparticlefilter.Ahybridmeasurementmodelisusedwhichcombinesanewmagneticfingerprintingmodelandtheexistingmagnitudefingerprintingmodeltoimprovethesystemperformanceandavoidcalibratingdifferentsmartphonemagnetometers.Aheuristicparticleresamplingalgorithmisproposedtoimprovetheaccuracyofthetraditionalparticlefilteralgorithm.Inaddition,aimingattheproblemofmotionestimation,alocalizationfailuredetectionmethodispresentedtoaddressthe“KidnappedRobotProblem”.OurexperimentalstudiesshowthatMalocachievesalocalizationaccuracyof0.8-1.2monaverageinalargebuilding.[Keywords]IndoorLocalization,Magnetic,ParticleFilter,Smartphone

目录摘要 IAbstract II目录 III1选题背景及意义 11.1研究背景 11.2研究目的 11.3研究内容 21.4本文贡献和组织结构 22相关工作 32.1国内外研究现状 32.2磁信号定位的可行性 32.3磁场定位基本思想 42.4粒子滤波技术 53Maloc系统 63.1Maloc的整体结构 73.2运动模型 93.2.1计算步数 93.2.2动态步长估计 103.2.3航向变化 103.3磁测模型 113.3.1混合型磁测模型 113.3.2指纹数据库构建 123.4重采样模型 133.4.1启发式自适应重采样算法 133.4.2航向偏移 143.5定位故障检测 154实验 164.1步数误差影响 174.2启发式重采样算法的性能 184.3不同类型观测值的影响 184.4定位质量估计的性能 194.5基于自适应重采样算法的聚集度评估 204.6Maloc的总体性能 205总结 22参考文献 23致谢 26第27页，共26页1选题背景及意义本章简要介绍提出该选题的原因，以及主要研究的内容和论文的结构。1.1研究背景现有的Wi-Fi指纹识别方法利用了广泛存在的Wi-Fi这一基础设施，不需要任何专门的硬件或额外的基础设施支持。然而，在实际定位时，设备需要频繁的进行Wi-Fi扫描，耗电十分严重。此外，Wi-Fi指纹定位的有效性取决于很多因素，比如Wi-Fi接入点的数量配置、空间性、以及无线环境的时间稳定性[1]。随着智能手机的广泛普及，基于手机地磁传感器的指纹识别方法受到研究人员的关注[2-4]。这类定位方法的基本理论是：在室内环境中，磁场由自然环境和人为环境（例如：钢筋混凝土结构和电力系统）双重因素的组成，其特征表现为起伏不定且不均匀。利用了这种起伏现象，通过读取磁场的三维向量(X轴，Y轴和Z轴)可以根据磁场指纹进行定位。虽然基于磁场指纹的定位方式与Wi-Fi指纹定位类似，但是具有更多的优点[4-8]:（1）它独立于Wi-Fi基础设施；（2）比Wi-Fi更可靠；（3）磁场的改变具有十分重大的意义，可以用于精确定位；（4）能量消耗更少。1.2研究目的地磁传感器读数与手机位置有关，需要采集一个位置上[6,9]所有方向的磁读数才能精确定位，这导致了收集指纹的成本高昂。另外，当手机方向或用户坐标系发生变换[3]时，采集的数据会发生偏差，这也就导致了定位精度不高。现有的研究[2,3,9]大都致力于采用粒子滤波方法来解决上述问题，其基本原理是使用随机样本（即参照系，例如：用户的位置和方向）来表示用户的状态，然后根据磁性指纹及其空间相关性，利用粒子滤波算法通过递归方式重新采样粒子，以达到准确定位的目的。粒子滤波的性能主要依赖于：（1）运动估计；（2）指纹测量和磁性指纹定位模型；（3）重采样。目前的基于磁场的粒子滤波定位方法有以下三个问题：一是，粒子滤波过程容易受到外界因素的影响，而基于手机中内置的传感器则更易被干扰。例如，用户走动幅度不是很明显时，无法有效滤波；现有的大多数粒子滤波定位算法[2,3,9]大都要求用户行走方向和手机方向一致，否则就会出现较大偏差。因此，需要设计一个动态的运动模型来减小这些干扰。二是，地磁传感器读数与手机位置有关，需要采集一个位置上[6,9]所有方向的磁读数才能精确定位，这导致了收集指纹的成本高昂。此外，不同的智能手机的磁传感器必须在使用前进行精确校准，否则会导致硬件同步误差等。因此，需要有一个更合适的磁测模型和磁力指纹模型。三是，由于粒子滤波的计算开销与粒子数成正比，当大量的用户同时运行定位算法时，服务器上的计算开销会非常高。因此，需要在满足定位质量的前提下，尽可能的减少粒子数，让其实现自适应的采样。另外，因为现有的粒子滤波方法来源于著名的“KidnappedRobotProblem”[12]，这使得运动估计方法容易出错[10,11]。所以，即便定位已经失败，系统可能还无法及时的反馈出来。因此，系统需要一个快速的故障检测机制来监控它。1.3研究内容为解决上述问题，本文设计了一个基于地磁指纹识别的室内定位系统Maloc，包括运动识别、磁测校准和能量优化三个部分。为提高系统的普适性，本文进行了定位故障检测。本文的具体工作如下：（1）为了提高系统的精确度，确保不受步数误差的影响达到最小化估计误差的目的。本文提出了一个运动模型，用来解决定位时，用户步数、步长和行走方向上的误差。（2）为提高系统的校准度和扩展系统的普适性，本文提出了一个混合测量模式。该模型提取地磁向量中的水平部分和垂直部分，并结合磁指纹的梯度相关性，避免了不同的手机地磁传感器的校准问题。（3）为减小系统能耗，本文提出了一个自适应的重采样模型。具体来说，就是采用了启发式采样来调整粒子数目，以达到自适应粒子滤波的目的。最后，本文进一步基于粒子聚集度提出定位故障检测机制。该机制能够发现93.5%的定位错误可以减半计算开销。实验结果表明本系统的定位精度为0.8-1.2m米，并且它比基于Wi-Fi的指纹定位方法更节能。1.4本文贡献和组织结构本文设计了一种启发式粒子滤波来改善系统性能和增强系统的鲁棒性，其贡献如下：（1）提出了一个动态步长估计方法，以补偿用户的真正步长的不确定性。（2）提出了一个启发式粒子重新采样机制，来解决用户方向偏移的问题。（3）提出了一个混合计量模式，不需要限制手机本身的方向和避免了不同手机磁场传感器的校准。本文的组织结构如下。第1部分讲述了选题的背景。第2部分介绍了相关工作，并且证实了磁场定位的可行性。第3部分介绍了整个Maloc系统，分别介绍运动模型、磁测模型以及自适应重采样算法和定位故障检测算法。第4部分为实验部分，第5节总结全文。2相关工作本章简要介绍了国内外研究现状，本定位系统所使用的粒子滤波技术以及磁传感器的特性。2.1国内外研究现状当前许多定位方法大都建立在特殊的基础设施之上，例如红外[13]，声学[14]和蓝牙[15]等。显然，部署这些基础设施通常成本是非常高昂的。另一方面，一些系统利用现有的且广泛使用的基础设施，如GSM[21]，无线网络和频率调制（FrequencyModulation,FM）。其中，基于Wi-Fi的指纹识别系统成为目前的研究热点。基于Wi-Fi的定位方法是使用Wi-Fi接入点（AP）的接收信号强度（ReceivedSignalStrength,RSS）来确认接收器的位置[16]。al[18]首先实现了基于Wi-Fi指纹识别，其定位精度是3-5米。ssef[19]进一步将定位精度提升至2米。然而，上述方法往往要求预先知道AP的具体位置，同时由于多径效应的影响，RSS对环境非常敏感，会随着时间的变化而变化，限制了定位精度。因此，Se[1]进行跨层设计，利用物理层将定位的准确度提高到了1m，但是定位过程需要消耗大量的能耗。e等人[20]使用的FM信号虽然比上述方法节能，但其定位过程只能在室温条件下才能实现。为了更加方便快捷的实现定位，本文采用手机中的磁传感器获取磁信号进行定位，其定位过程使用粒子滤波技术。2.2磁信号定位的可行性室内磁场是结合地磁场和环境磁场的组合磁场。图1显示了一个室内磁场图谱，该图谱是连续监测一个月所得到的。可以看出，磁场随着时间的推移相当稳定，而随着位置变化显著改变。进一步，本文研究了智能手机在不同高度时的磁场值，如图2所示。手机高度分别为0.5m、1m、1.5m。实验结果显示，手机高度对磁场值影响不大。此外，其他行人或者区域内已有的物体被移动后造成的磁场变化是非常有限的[4-7]，因此本文使用手机的磁力计进行定位是可行的。图2由不同高度的智能手机抓获的磁场数图1室内磁场图谱图2由不同高度的智能手机抓获的磁场数图1室内磁场图谱2.3磁场定位基本思想首先，由智能手机的磁力计测量获取包括了地磁场和环境磁场的室内磁场值。然后，将旋转角度（旋转角为x，y，z轴的旋角ψ，θ，φ）获得。当没有噪声时，和的表达式分别为：（2-1）（2-2）其中Rz(ψ)，Ry(θ)的Rx(φ)是相应的旋转矩阵。当有噪音时，Hard-iron[26]（V）和Soft-iron[26]（W）后，的表达式为（2-3）V是偏移矢量，W是一个变形矩阵。当智能电话在固定位置被转动时，噪音导致磁性读数的轨迹是一个椭圆形，如图3所示。校准噪声后，轨迹接近于球体。校准磁力仪主要是为了找到V和W。如校准方法[26-29]所述。不同的智能手机具有不同类型的磁力仪，它们在敏感度上是不同的。即使同一类型的智能手机在相同的位置也可能读取到不同磁值。图4显示了由两个GalaxyNexus的智能手机沿着50米长的走廊捕捉的磁性值。它们在相同的位置波动，但是曲线的梯度保持相当恒定。这表明，可以用指纹代替原始指纹值的梯度，以避免校准不同的磁力。图3磁读数与最佳椭圆体拟合轨迹重叠图3磁读数与最佳椭圆体拟合轨迹重叠图4由两个智能手机以及一个50米长的走廊拍摄2.4粒子滤波技术粒子滤波技术指的是通过寻找一组在状态空间中传播的随机样本来近似的表示概率密度函数，用样本均值代替积分运算，进而获得系统状态的最小方差估计的过程。在定位方面，该技术一般需要使用磁场信号值作为粒子状态的参数。基于粒子滤波的磁场定位的基本思想如下：1:GenerateNrandomparticlesfromaninitialarea.

2:foreachstepdo

3:Estimateland∆θ.

4:foreachparticledo

5:UpdatepositionandheadingbymotionmodelasEquation(3-3)and(3-4).

6:EvaluatetheweightofparticlesbymeasurementmodelasEquation(3-6).

7:endfor

8:DecidetheamountofparticlesforeachresamplingmethodNdandNh.(N=Nd+Nh)

9:ResampleNdparticlesfromoldparticlesaccordingtothedistributionoftheirweights.

10:ResampleNhparticlesbyourheuristicmethod.

11:Normalizetheweights.

12:Predicttheuser’sstatebyEquation(10).

13:Estimatethequalityoflocalization.

14:ifdetectlocalizationfailedthen

15:Runrecoverprocedure.

16:endif

17:ResizeparticlenumbersN.18:endfor注：表达式（3-3）为；（3-4）为；（3-6）为。在粒子滤波定位研究领域，Haverinen[2]等使用粒子滤波器在建筑物的走廊内进行定位，但要求用户的方向必须与走廊保持一致。Chung[6]等提出了一种基于磁场的粒子滤波算法方法，它需要测量所有方向的地磁读数，可以达到4.7米的精度，然而该系统的实现成本相当高。目前，由于智能手机的普及，研究人员开始关注使用手机磁力计。Subbu[4]提出了基于手机的磁性模型，实现了小范围的室内定位，但该系统被限制在一维环境，如走廊等。Bilke[9]提出了一种二维环境下的定位系统，其平均定位误差为4米，但它的实现成本非常高。文献[3]设计的定位系统可以在二维环境中运行，并且通过坐标变化，避免了测量所有方向数据。然而，它放大了矩阵变化时方位估计误差，定位导致极易出错。在文献[2,3,9]中提出的粒子滤波定位技术通常需要智能手机的方向与用户方向保持一致。同时，文献[23,24]中的定位系统使用了加速度传感器，它们在用户航向推算时，传感器上的误差会在定位计算时被成倍放大。为此，本文提出了启发式粒子滤波技术并设计了相应的定位系统，它包含了动态步长估计模型、混合磁测模型和启发式重采样模型，解决上述问题。进一步，本文在提高精确度和速度的同时，通过定位故障检测提高了系统的容错性。3Maloc系统本文设计了一个基于地磁信号的室内定位系统Maloc，该系统使用了启发式粒子滤波技术。具体来说，本文首先提出了一个运动模型用于动态地计算用户的步长和识别用户的行走方向，然后，设计了一个混合磁测模型用于精确识别指纹。为提高系统的定位速度，本文进一步提出启发式粒子重采样，以实时调整粒子数量，在不影响定位效果的前提下，提高运行速度。为进一步提高了系统的容错性，本文对系统进行了定位故障的检测。3.1Maloc的整体结构Maloc被建立在一个启发式的粒子过滤器上，使用一组粒子来预测后续粒子的分布。用户状态以用户的位置和方向来表示。粒子包含了用户的状态和权重，其用户状态表达式为（3-1）其中，x，y代表该用户的位置，θ是用户的方向。相应的，粒子的表达式为（3-2）其中是粒子的权重。权重大意味着它更接近真实状态，并用来表示用户状态的后续粒子分布。该系统主要包含三个基本组成部分：运动模型，磁测模型和重采样模型。该系统的准确度完全取决于三种模型的构建。其中，运动模型通过惯性传感器预估用户运动来更新每个粒子的状态；磁测模型重新评估粒子的权重；重采样模型用残存粒子更新系统态作为后续粒子。由于这三个过程形成递归操作，预测状况将会越来越接近真实状态。下面简要阐述上述三种模型。运动模型基于用户方向和用户位置，本文构建了运动模型，表达式为（3-3）（3-4）其中是步长，是用户连续两个步骤之间的航向变化，和是高斯噪声。不同于已有的研究[2,3,9,17,30]，步骤长度在Maloc中不是常数，而是在定位中被动态估计。不同用户的步长是不同的，甚至同一用户的步长也可以是不同的。不准确的步长度估计会导致较大的定位误差，从而导致定位失败。系统提供了一个动态的步长估计算法来有效地解决这些不确定性。该算法也使得步数的错误在Maloc中是可容忍的。是智能手机的陀螺仪传感器的参数变化值。通过和来放大粒子的差异。磁测模型本文使用地磁指纹作为主要的测量数据，用字母z表示。P（z|s）为z在状态s上的概率，这取决于在该位置上磁场变化的强度和采集指纹之间的时间差。当P（z|s）比较难获取时，高斯分布[2,3,9]将被使用，如等式（3-5）：（3-5）其中n是z的维数，V是协方差，obv(s)是一个函数，用于获取当前状态(s)在指纹数据库中的测量值。obv(s)将返回最接近送地理位置的指纹。本文设计了一种分层数据结构。系统根据其地理位置将指纹数据库的数据分割到一个网格中。然后，就可以建立一个哈希函数映射到该组指纹网格中。同时，系统拥有一个时间复杂度为O(1)的方法grid(s)，它可以在短时间内发现网格中s的状态。因此，系统首先需要找到在数据库中最近状态s的指纹，建立起对应的网格，然后找到在这个网格中最接近的指纹。总时间复杂度为O(m)+O(1)其中m是一个网格的大小。与K-D树相比，它更容易维护。考虑到缓存，数据结构将比K-D树更有效。由于不同的智能手机磁读数是不同的，本文用等式(3-6)来评价每个粒子，而不是用贝叶斯过滤模型，或者直接用来表示粒子。公式(3-6)这种表达方式使得Maloc更稳定，同时又避免了校准磁读数的问题。(3-6)（3）重采样模型在启发式重采样模型中，首先重采样本身就是为了摆脱低权重粒子，保留接近真实状态的粒子。在这项工作中，本文利用离散概率分布根据权重（即传统的重采样方法）从旧粒子中重新取样。当然，环境是存在噪声（例如，手机正在通话）的，粒子就会产生误差，导致定位故障。为了解决这个问题，系统结合了启发式重采样与传统重采。利用当前状态的权重为当前粒子群的权重赋上均值，如等式（3-7）所示：（3-7）粒子滤波算法比Wi-Fi指纹定位图谱映射的开销大得多。因为在粒子滤波中有许多粒子在当前状态是相似的，造成了大量的计算浪费，所以在定位精度已经很高的情况下，系统并不需要太多粒子。因此，Maloc会在每一次迭代时，会根据当前状态重置粒子数，实现自适应采样。可以看到是，当前粒子来源于上一轮定位粒子。也就是说，即使大多数粒子接近真实状态，但存在一个错误粒子，定位就可能失败。为了更好地解决这个问题，在下文中，根据目前的定位精度提出了一个定位故障检测系统。在定位故障时Maloc运行一个恢复的过程，以保证系统的高可用性。3.2运动模型在本节中，介绍了计步参数、动态步长估计和航向变化估算的方法。通过动态步估计提高粒子过滤器的稳健性。3.2.1计算步数系统使用智能手机上的加速计来获取步数。由于智能手机可以在任何方向上被用户使用，加速度传感器仅显示读数的幅值，这就意味着过滤器还要进一步处理该数据。如图5所示，本文利用智能手机采集了不同情况下的加速度数据，分别为拿在手上、放在衬衫口袋里、放在裤子口袋里。实验结果表明计数器的峰值和谷值无法判断用户是否走步。目前有许多步数计算方法[25,31]，本文采用一种低开销的计步算法，其主要思想是通过设置4个阀值：来过滤错误事件，保证步数计算的准确度。其中，是相邻的波峰和波谷间加速方差的上下边界，是相邻波峰与波谷时间间隔的上下边界。图5在不同位置由智能手机拍摄的加速度读数的大小图5在不同位置由智能手机拍摄的加速度读数的大小3.2.2动态步长估计估计用户步长的精确程度对定位精度有很大的影响，简单地步长估计可以为每个用户设置一个恒定的步长。然而，因为每个人的步长都是不同的，甚至同一用户的步长也会发生改变，因此本文设计了一种动态的步长估计算法。当粒子通过运动模型更新时，每个粒子演变到下一轮的粒子都会生成不同的步长。所以，平均的长度为。然而，重采样之后，所有的粒子会被重新评估。具有较高权重的粒子更接近真实状态，这种粒子的步长也更加接近真正的步长。所以，加权平均后步长的表达式为（3-8）其中Nd是从旧粒子中的采样粒子数。如果粒子滤波定位结果准确，将趋向于真正的步长。当然，如果粒子滤波不能准确定位，则表示所计算的值是有误差的。为此，本文设计了一个动态的步长估计算法。除了使用作为一个步长，算法定义了一个队列Q来缓存的历史数据。然后，将它们的均值作为下一轮定位的步长。考虑到当用户的航向发生变化时，其步长可能会产生一些变化，导致步长估计不正确，算法不会把该部分放到上述队列中。因此，本文算法保证了定位过程的准确收敛。与文献[23,25]中的步长估计方法相比，该算法可以实时更新步长，而且不依赖于检测的精度。3.2.3航向变化在识别航向（用户行走方向）变化的过程中，由于用户的行走方向不同于手机方向，所以即使指南针传感器在室内环境中在精确，也很难被正确识别。而且在定位过程中用户可能会受到其他任务操作的干扰，导致定位失败。因此要识别航向的变化，存在两个问题要解决：（1）估计在任意方向上两个连续步骤之间，手机方向的变化；（2）消除航向变化引起的误差。由此，可以考虑使用智能手机上的指南针和陀螺仪两个传感器解决估计两个相邻步骤间方向变化的问题。如图6所示，本文首先比较了指南针和陀螺仪在方位变化估计上的性能。在实验过程中，用户沿着直线行走，然后经过一个直角。实验记录了指南针和陀螺仪两个传感器的数据变化。结果表明，指南针在室内环境中明显不能正常工作。因此，本文使用陀螺仪来解决航向变化问题。智能手机上的陀螺仪能够测量手机周围的x，y和z轴的角度变化。但由于手机的方向是未知的，系统不能直接由此获得用户行走方向的变化。所以，本文又利用手机的重力传感器，获得了重力方向的角度变化（重力方向的角度变化与x，y和z轴的角度变化是一致的），然后通过矩阵变化就可以计算出用户行走方向上的变化。虽然误差会存在，但误差在一步内是很小的，甚至可以忽略。因为实际过程中，每一个粒子本身就会增加了高斯噪音来保证它的独立性。图6指南针和陀螺仪沿走廊行走和转90度角时捕获的角度的变化。图6指南针和陀螺仪沿走廊行走和转90度角时捕获的角度的变化。3.3磁测模型磁测模型是基于智能手机采集到的磁场观测值来估计粒子，并以此生成地磁指纹数据库。3.3.1混合型磁测模型上文中提到的磁力计读数由三维矢量，分别表示沿手机的x，y和z轴的磁值。一般来说，基于有三种观测方法。第一种，直接采用作为观察Z[2,3,6,9]。这种方法需要收集当前位置上各个方向的磁场读数，这将导致样本空间变大，不仅增加了成本，同时也降低了精度。第二种，采用的幅值B作为观测值[2,4]。B是旋转不变的标量而且相对稳定。然而，这样的话每个指纹上的元素都将从三个下降到一个的，大大减少了每个指纹的唯一性。在大型的室内环境，粒子过滤器可能需要更多的时间来收敛到正确的位置。第三种，提取的水平分量和垂直分量作为观测值[7]。智能手机上的重力感应器提供了重力的方向（即垂直方向）。借此，系统可以提取的垂直部分和水平部分构造一个新的观察值（名为HV指纹）。图7显示了室内区域中和磁场图。这比幅值指纹更独特，这种指纹模型使粒子滤波器更快地收敛到正确的位置。该指纹模式在参考文献[7]中提到过，但是没有实际的基于磁指纹识别的室内定位系统。因为其中存在一个问题，当用户移动时，噪音被引入重力传感器的精确度就会受到影响，甚至定位失败。综合考虑，本系统将幅值B和结合使用设计成一种混合计量模式。HV指纹具有更完美的唯一性，它使粒子滤波更快地收敛到正确的位置。但是，它并不像幅值那样稳定。因此，当定位开始时，系统使用HV指纹加速Maloc时的收敛，然后将其切换到磁幅值指纹进行“跟踪”。在实际运用过程中，如果让手机自己校准磁力的偏移，代价是非常高昂的。所以，本文使用两个连续的步骤间指纹值的变化（梯度）来代替使用指纹本身，以避免校准不同的磁力。如之前所提到的，它在垂直方向的磁场变化和沿着时间的变化不大灵敏。这也是使用公式（3-6）来评价粒子的原因之一。另外一个是，虽然使用贝叶斯过滤器模型来评估粒子会使粒子滤波收敛得更快速并且有利于揭露失败的定位，但这也使粒子滤波本身变得对噪声非常敏感，定位容易失败。在一个非常大的室内环境中，这些指纹模型或计量模型可能不适用于定位，因为粒子过滤器将需要更多的粒子和更长的时间才能收敛，这招致较高的计算开销降低了可用性。为了解决这个问题，制作了一个简单的粗粒定位方法[3,6]（与15m~30m或房间级精度），这种方法只是在初始阶段缩小了搜索空间。3.3.2指纹数据库构建在本文中，使用了众包形式来实现快速，廉价的磁场指纹的采集。这种方法从IndoorAtlas[34]得那到的启发。如图8所示，数据收集器需要沿着这些路线覆盖一个区域。在每一行，设置了起点、航向方向和路径长度。然后，以慢速的、恒定的速度沿着这条路径步行。在这个过程中，应用程序将记录由智能手机上的磁传感器捕获的数据。每一个磁场指纹将以的形式被存储。然后，从中计算出它的幅值。假设数据收集器工作在一个恒定的速度下。每个磁性指纹都可以很容易的映射到它的位置。为了避免出现较大的映射错误，每行不应该太长。每行都收集相对密集的磁场指纹，例如一个指纹长0.1米；在实验中，两条线之间的距离是约0.6米。然后，通过插值填充这块区域的指纹。最后，获得一个个规模为0.1米×0.1米磁场指纹。图8指纹采集方式（左）与指纹采集APP界面图8指纹采集方式（左）与指纹采集APP界面图7在16.3米x5.4米室内面积内磁场地图水平分量（左）和垂直分量（右）3.4重采样模型本章节中，介绍了一种自适应的启发式重采样算法，该算法能实现实时更新粒子数目，提高运行效率的同时，还能帮助解决航向偏移的问题。3.4.1启发式自适应重采样算法与Wi-Fi指纹定位相比，Maloc的计算开销是相当高的。由于粒子滤波器的计算开销与粒子数目成正比，最直接的方法就是减少粒子数。然而，当粒子数减少时，粒子过滤器的稳定性将会被弱化。因此可以在计算开销和粒子过滤器性能之间进行折衷，即动态地调整粒子数目，以达到自适应粒子滤波。在文献中有两个主要的自适应采样算法。一种方法是基于似然的自适应采样[10]。但是，这种方法在对称环境或者在高似然性环境中将失效，因为在许多不同的状态可能有同样的观测值。因此，它不适用于地磁定位系统。另一个是KLD-Sampling(基于交叉熵值的适应性采样)[32]。它引入了Kullback-Leibler距离(KL-Distance)来确定样本大小。KL-Distance首先需要一个后验粒子群，由当前粒子群通过一个离散的、分段的常数分布（如离散密度树或多维直方图）产生，然后基于前后两批粒子群计算出它们之间的距离。所以，当大多数粒子都集中在一个特定区域时，KL-Distance是很小的，用少量的粒子就能覆盖。反之，如果粒子分布在一个较大的地区，KL-Distance也将变大，那么就需要更多的粒子来覆盖这些区域。KL-Distance和本文的聚集度颇为相似。然而，计算KL-Distance远远比计算聚集度复杂多。更重要的是，聚集度在质量评估阶段已经可获得了。因此，本文在这里提出了一种新的自适应采样算法。当聚集度超过阈值，并且智能手机的航向变化也低于阈值，那么就降低样本规模。随机减少个粒子，时间复杂度为（3-9）其中是控制降低率的参数。原有粒子数不能小于最少粒子数。当聚集度低于阈值或智能手机的航向变化超过阈值，那么就需要增加粒子数。用传统重采样算法采样获得，用启发式采样算法采样获得。和都正比于当前粒子数，目的是为了平稳地增加粒子。（3-10）（3-11）（3-12）其中和参数来控制粒子增长的速率。系统也为和设置了一个下边界。这是因为，当需要增加粒子时，如果N太小，增加率也将非常低，这不利于快速定位。3.4.2航向偏移航向偏移引起的误差对传统的粒子滤波算法具有很大的影响。例如，当走路的时候用户接听电话，用户的航向保持不变，但手机的方向可能会被改180度。这种行为扭转所有粒子的方向，定位误差会变得更大，从而导致定位失败。因此，直接去检测手机方向的变化是不明智的。所以，提出了一个启发式重采样算法来解决这个问题，灵感来自于随机粒子滤波[12]，其中当粒子总体权重下降时，它会随机取样新粒子而不是只从旧粒子中再采样。如何产生新的粒子，以及有多少粒子都与这一步中手机方向的变化有关。本系统定义了以下规则。其中，新的粒子的数目与成正比，为了在Maloc中实现它，本文提出了以下公式（3-9）：（3-13）其中p是控制灵敏度（通常为参数从[0.5，0.85]中选择），N是粒子的总数量。新的粒子的位置是随机从上一预测位置的的r米范围内采样的。r是一个恒定值。新粒子的方向也是随机从范围或范围中取样。是以上一预测位置的航向。启发式重采样算法可以增加粒子的多样性，这将使得粒子过滤器更强大，能够容忍更多的运动估计误差，从而降低定位精度的成本。3.5定位故障检测基于本文算法的粒子滤波器在定位过程中的故障检测是非常重要的。因为在通常情况下，只有当系统中所有粒子的权重为零或者系统崩溃，系统才会意识到定位失败。在此期间，系统可能已经定位失败很长时间了。情况是这样的，在重采样阶段，过多的噪音形成的虚假粒子可能在两三个循环后将真实状态的粒子干掉。而在接下来的重采样阶段，一些粒子的权重碰巧大于零，那么系统将运行更长的时间来检测定位故障。在此期间，定位结果是任意的[12]，这种现象被称为“KidnappedRobotProblem”。在Maloc中，这个问题变得更严重，因为系统使用一个宽松的模型而不是贝叶斯滤波器模型来评估粒子，而且启发式重采样方法会增加粒子的多样性，这会导致粒子滤波器的故障需要更多时间来揭露。在实验中，分析了正常的粒子滤波和被“绑架”了的粒子滤波之间的差异，发现正常情况下粒子将收敛到真实状态的周围。如图9所示，在初始阶段中的粒子被均匀地初始化。经过一系列的步骤，粒子收敛集中到真实状态的周围。我们称这个区域的规模为区域聚集度。如果运动模型和测量模型是精确的，聚集度将始终保持很小。但是，在本系统中运动估计或测量模型中的误差会带来一定的虚假状态粒子。这些虚假粒子可能会收敛到不同的方向。如果虚假粒子的数量相对较少，它们将在下一次的重采样阶段被消灭。如果虚假粒子的数量过多，它可能需要很长时间才被消灭，或者干脆因为虚假粒子数量过于庞大，直接干掉了真实粒子。这两种情况都将导致聚集度扩大，尤其是后者。这种扩大现象可能随着更多的重采样很快消失。因此，使用聚集度来预测当前的定位误差。基于在这个定位误差估计法，可以试探性地检测定位故障：如果预测误差e超出了阈值T，则定位可能已经失败。在Maloc中，对聚集度做了如下定义：以当前预测的位置为中心，最小半径r的圆，90%以上的粒子的位置都在这个圆内。在定位过程中，定位的数据将被实时记录在Maloc中，其中包括预测结果，航向变化角与观测的值z。当检测定位故障时，系统进行数据回滚，将定位点回滚到上一状态。图9在不同定位质量下的集群程度变化图9在不同定位质量下的集群程度变化4实验本文对该系统进行了充分的实验验证，图10是实验场所平面图。实验涉及到7名志愿者和多种类型的智能手机，包括三星Galaxy，HTC，MOTO。本文主要关注：Maloc能容忍多少步数误差；动态步长估计的性能；如何实现启发式采样算法；不同类型观测值的影响；如何实现准确定位质量评估和定位故障检测算法。然后，评估整体Maloc的性能，包括在不同条件下的整体定位精度，不同行走路径下的定位精度和相比于基于Wi-Fi指纹定位的能量消耗。图10实验建筑平面图图10实验建筑平面图4.1步数误差影响图11误计数发生时两粒子滤波定位结果图12不同的初始步长的两个粒子过滤器的性能本文首先评估步数误差所带来的影响。图11显示在传统粒子滤波(PF)和本文的启发式粒子滤波(AugPF)计步数错误时出现的定位误差。在该实验中，志愿者大约走了300步，用户的步长约0.6~0.65m。当误计步数达到10步时，由启发式粒子过滤器测得的平均步长是0.68米。当误计步数上升到50步时，其平均步长会延长到0.77米。结果显示，启发式重采样方法增加了粒子的多样性，同时动态步长估计可以弥补误计步数。图11误计数发生时两粒子滤波定位结果图12不同的初始步长的两个粒子过滤器的性能4.2动态步长估计的性能本文采用动态步长估计测试粒子过滤器的性能。在该实验中，设置为0.2，为5。用户真正的步长大约是0.6到0.65m。图12显示出，当将步长设置为不同的值（即0.5米，0.6米，0.7米和0.8米）时，启发式粒子滤波（没有启发式重采样）与传统粒子滤波的定位错误。如该图所示，当设置的初始步长值比传统粒子滤波的真正步长偏差较大时，定位精度就变的较差。步长被设置为0.8米时传统的粒子滤波已经无法定位。初始步长值对加入动态步长估计后的启发式粒子过滤器无特殊要求。实验表明，无论初始步长设置为多少，该定位过程中平均步长会趋于一个大致固定的值（实验中为0.7米）。这意味着系统运行在一段时间后，就可以准确的推断用户的平均步长。当然，在系统Maloc中若刚好设置了平均步长作为初始值，则动态步长估计过程的运行时间也会大大减少。4.2启发式重采样算法的性能本文从两个方面评估启发式重采样算法：处理航向变化估算的误差和处理航向偏移时的误差。首先，分别用精确步数和恒定步长来运行粒子滤波器100次。传统的粒子过滤器四次不能定位。相反，启发式重采样算法粒子滤波器能够全部正确定位。然后，验证两个粒子滤波器在航向偏移发生时的处理能力。通过用户沿24米走廊一边行走一边接听电话的行为，本文比较了传统的粒子滤波和启发式粒子滤波器的定位性能。结果如图13所示，虽然航向偏移变化对定位精度只有短暂的影响，但它会导致传统的粒子滤波器收敛到错误的位置，而启发式粒子滤波器则没有发生这个问题。4.3不同类型观测值的影响为了比较使用不同的磁场观测值所产生的性能差别。本文在一个大厅里进行实验，其中传统的粒子滤波将需要更长的时间来进行收敛。图14显示了在Maloc中使用三种不同的指纹模型作为观测值产生的定位结果。如图所示，HV指纹对用户的转向动作非常敏感，并且收敛的更快。使用磁场幅值是很稳定，但是它比HV指纹的收敛速度低很多。上述实验证明，混合模式更具优势。图14用不同类型观测值的MaLoc的性能图14用不同类型观测值的MaLoc的性能图13航向偏移变化的两个粒子滤波的定位结果4.4定位质量估计的性能本文使用定位质量评价方法估计定位误差并且比较预测误差与真实错误。在42840次定位结果中，真实误差和预测误差之间的平均差值约为0.96米。为了评估定位失败的检测方法，实验分析了所有的定位失败案例。为了避免影响自适应采样算法，所有这些实验都是不改变粒子数的前提下进行的。149例中有138例是由本文的故障检测方法检测到的（实验中=7米），实现92.6％的准确监测。在收集的194个成功的定位案例中，误报率为8.2％。图15分别显示出了两个实验中的真正定位误差和预测定位误差。实验2描绘了成功定位，实验1显示了定位失败。图15真实的定位误差和预测的定位误差图15真实的定位误差和预测的定位误差图16当定位时，粒子数目的变化4.5基于自适应重采样算法的聚集度评估实验在用户每次行走的最后，系统将调整粒子数目。如图16显示，当用户沿着第二层走廊走动时的粒子数变化。这三个实验都取得不错的成绩，他们的平均定位精度是0.88米（=1.5），0.89米（=2.0）和0.84米（=2000）。为了测试基于自适应重采样算法的聚集度是如何有效的，设计了另一个实验。设置最大粒子数从1000至5000，然后看看平均每次迭代时的变化。如图17显示。图17粒子数与平均定位错误图17粒子数与平均定位错误这里存在一个疑问，自适应采样算法和故障检测算法是否存在冲突。直观上认为，如果样本量过小，聚集度也始终保持非常小。因此，当定位失败时，聚集度恐怕不会超过阈值。然而，在实验中，发现事实并非如此。其预测误差几乎和Maloc中的粒子数是一样的。那是因为即使粒子数较小，当噪音被加入时，聚集度就会增长。而且这将导致自适应采样算法增加粒子数。因此，当定位质量不是很好时，粒子数也不会过小。在4.5节中也做了同样实验。其中有201处定位故障，188处被检测，精度是93.5％。4.6Maloc的总体性能首先，系统在不同的场景里评估Maloc：大厅里，会议室，办公区（主要是走廊）和图书馆，实验显示了它在大厅里的性能稍差。原因有两个，一个是其他三个场景的地面布置比大厅相要复杂，这就带来了更多行动上的限制，这些限制提高了定位精度。另一个复杂的建筑物环境存在着更为复杂的电磁环境，所以像大厅这样的环境中，磁场的唯一性变得不明显。在这个实验中，测试了运动估算和磁测量中的噪声对定位准确度和精度影响。系统进行了五个实验：一个用户用五种不同的姿势拿着自己的手机，其中包括：1）把手机保持和自己的朝向一致；2）把手机放在自己的上衣口袋里；3）把手机放在自己的裤子口袋里；4）稍微不停地左右摇晃；5）用手拿着，走路的时候随着手臂晃动。然后，比较Maloc与基于Wi-Fi指纹定位的结果。结果表明，情景一精确度最高，因为在运动估计和磁测量中干扰最少。其次是，走路时将手机放在上衣口袋里、裤子口袋里或摇晃它会导致准确度和精密度的降低。其中，基于Wi-Fi指纹定位的定位误差在2.5m~4.5m，而且平均定位精度为3.5米。当拿着手机时，Maloc的50％，80%错误的结果和平均精度在0.8-1.2m之间。即使在最坏的情况下（即把手机放在裤子口袋），Maloc的平均定位精度为2.5米，这也是比Wi-Fi指纹好得多。在最后的实验中，本文对Maloc评估能量消耗。用三星GalaxyNexus智能手机进行实验，并在三个场景中比较能量消耗：不运行什么，只运行Maloc的追踪收集应用程序和只运行Wi-Fi扫描应用程序。为了防止智能手机进入休眠模式，在实验过程中保持智能手机的屏幕亮着。如图18所示。图18不同情况下的运行时间图18不同情况下的运行时间从结果中观察到，运行Maloc跟踪收集应用程序比运行Wi-Fi扫描应用程序节省了约1小时的电池寿命。因此，本文得出结论：6小时内Maloc比Wi-Fi扫描节省约220mA·H的能量。5总结综上，本文提出了基于启发式粒子滤波的室内定位系统Maloc。它利用磁传感器和惯性传感器采集数据，通过启发式粒子过滤器进行运算，不对用户使用和手机方向做任何限制。在该系统中，采用了动态步长估算算法来最小化动作上的误差并提高粒子滤波的稳定性。然后，结合磁强指纹模型和已有的幅值指纹模型设计了混合型测量模型，来改善系统性能，避免不同型号手机磁力计的校准问题。最后，利用重采样模型实现启发式粒子重采样，改进了传统的粒子滤波算法精度。同时，针对运动估计中存在的问题，本系统提出一个定位错误检测机制来解决“KidnappedRobotProblem”。实验结果表明，本系统可以实现精度为0.8-1.2m内的室内定位。

参考文献S.Se,.aic,..r,ad.ia,“uareacigtemalisa:stlcalizatinsigylaerifrmati”inMisys.,,..J.HerienadA.emaie,“Glalirself-lcalizatinasednteamietmaeticfiel”Rticsdtmsystems,l.,.,.,.E.LeGradadS.Tr,“-aismaeticfieldmaigadfsinfrirlcalizati”inMFI.IEEE,,..K..S,.Gzic,ad.Dat,“Lcateme:aetic-fiels-asedirlcalizatinsigsmartes”TIT,l.,.,.,.Aerma,.Frassl,.Diec,.J.Jlia,ad.erts,“aracterizatinfteirmaeticfieldfralicatisinlcal-izatinadmai”inIPI.IEEE,,..J.gadDae,“Irlcatinsesigsige-maetism”inMisys.,,...Li,.Gallae,A.G.Demste,ad.izs,“Hwfeasileistesefmaeticfieldalefrirsitii?”inIPI.IEEE,,..W.Strms,J.Scl,adJ.aet,“aeticfieldiatininanireirmet”inUPILB.IEEE,,..A.ileadJ.Siec,“Usigtemaeticfieldfrirlcalisatinnamilee”inLcti-Bsedervices.Srie,,..D.,.ar,.Dellaert,adS.Tr,“tecarlolcalizati:Eficietsitinestimatinfrmilerts”AAAI/IAAI,l.,.,.S.Tr,D.,.ar,ad.Dellaert,“stmtecarlolcalizatinfrmilerts”Artifcilitelliece,l.,.,.,.S.Tr,.ar,adD.