毕业设计（论文）基于众包的低开销室内定位关键技术研究及原型实现.doc

河 北 工 业 大 学 毕业设计说明书作 者： 学 号： 113042 学 院： 计算机科学与软件学院 系(专业)： 软件工程 题 目： 基于众包的低开销 室内定位关键技术研究及原型实现 指导者： 软件工程 讲师 (姓 名) (专业技术职务)评阅者： (姓 名) (专业技术职务) 年 月 日毕业设计（论文）中文摘要基于众包的低开销室内定位关键技术研究及原型实现摘要： 随着建筑物规模越发庞大，结构愈发复杂，人们在其中活动时经常容易迷失方向，难以确定自己的位置，因此室内定位技术受到极大的关注。本文对基于众包的地磁室内定位技术进行研究，首先对地磁特征进行研究，确定后续研究的可行性；然后讲述地磁空间和物理空间的映射，根据DTW算法计算出的曲线相似度，采用K-means算法对数据进行分类并将每一类进行融合，通过完成地磁空间和物理空间的映射实现地磁指纹数据库的建立；接下来研究了物理空间拓扑结构挖掘，用AP聚类算法处理采集的数据，经过融合处理得到物理空间拓扑结构图；最后介绍系统实现，实验表明采用众包建立的地磁指纹数据库进行定位时，误差在3m以内的概率高达80%，效果良好。关键词：众包；室内定位；映射；地磁指纹数据库；物理拓扑结构毕业设计（论文）外文摘要Title Indoor positioning based crowd-sourcing with low cost key technology research and prototype implementationAbstractAs more and more large-scale buildings structures become complex, people is often easy to get lost when people do activities in buildings and it is difficult to determine their position.Therefore the indoor positioning technology is getting more and more attention. In this paper,we do research on the indoor positioning technology based on magnetic crowd-sourcing. Firstly,we make a study on geomagnetic characteristics to determine the feasibility of the next research.Secondly mapping the geomagnetic space and physical space, employing K-means algorithm to cluster all crowd-sourcing magnetic fingerprints based on the DTW (Dynamic Time Warping) similarity criteria. After clustering each category are fused.Achieving the establishment of geomagnetic fingerprint database by completing the mapping geomagnetic space and physical space; Next study is physical space topology mining. Using AP clustering algorithm to deal with the collected data.Giving physical space topology after the fusion process.Finally,system implementation. Experiments show that the probability of error is less than 3m up to 80% when establishing geomagnetic fingerprint database to locate using crowd-sourcing.The effect is good.Keywords:crowd-sourcing;indoor positioning;mapping;magnetic fingerprint database;Physical topology目 录1 绪论11.1 定位技术的背景11.2 国内外定位技术的发展状况11.3 本课题的贡献以及研究意义21.4 论文组织结构32 室内地磁特征研究42.1 地磁三轴特性52.2 不同物理路径的地磁分布特性72.3 不同高度的地磁分布特性72.4 不同姿势采集的地磁分布特性92.5 同一路径不同方向地磁分布特性112.6 本章小结123 基于众包的地磁指纹空间与物理空间的位置映射133.1 拐弯检测133.2 地磁轨迹单一化143.3 基于地磁的分类153.4 建立地磁空间与物理空间的位置映射183.5 本章小结204 基于众包采样的物理空间拓扑结构挖掘204.1 基于众包的AP算法的聚类204.2 物理空间拓扑结构挖掘234.3 本章小结245 NaviStone定位系统255.1 NaviStone系统结构255.2 NaviStone系统定位流程265.3 系统评测275.4 本章小结28总结29参考文献31致 谢341 绪论 1.1 定位技术的背景无线室内定位是人们一直以来十分关注的一项技术，实际应用中也有非常重要的意义。随着大型建筑物数量不断增加以及智能移动终端设备的逐渐普及，人们对室内定位服务的需求正在不断的增加。大型建筑物规模比较庞大，内部布局相对复杂，因此公共安全管理问题比较突出，人们在里面进行各项活动时经常容易迷失方向，难以确定自己的位置并快速准确地找到目的地，由此，人们存在较强的定位导航需求。GPS定位是目前应用最为广泛的定位技术，利用GPS进行定位的优势在于卫星有效覆盖范围大，且定位导航信号免费。然而当GPS接收机在室内工作时，由于信号受建筑物的影响而大大衰减，定位精度也很低，要想达到室外一样直接从卫星广播中提取导航数据和时间信息是不可能的，由此GPS定位技术在室内定位方面是不可行的。为此，国内外许多公司、高等院校和科研机构都围绕室内定位技术展开研究。当前，室内定位技术主要有ZigBee定位技术、蓝牙室内定位技术、超宽带定位技术、WIFI室内定位技术、超声波定位技术、LED定位技术和计算机视觉定位技术等。从技术推广程度看来，WIFI定位和蓝牙定位实现方式较为容易，也是未来最具有发展潜力的室内定位方法。近些年，基于指纹的匹配并利用地磁信息进行室内定位已经成为一个新的研究方向。地磁场信息在空旷的地方，呈现的差异性并不大，但在现代建筑中，室内磁场则由于电器设备、钢筋混凝土等影响，强度和方向都发生较大改变。根据这一特征，室内每条路径因其环境不同而产生不同的磁场信息，从而可以建立磁场与位置的指纹信息，使高精度的室内定位成为可能。1.2 国内外定位技术的发展状况关于室内定位技术已有许多试验方案，如伪信标技术、GPS转发技术以及网络定位技术。1992年，英国剑桥ORL的Active Badge系统是最早期的室内定位系统之一。它是一种使用红外线收发器、无需测位的定位系统，系统的缺点是不容易部署大规模网络，且红外线容易受到光线的干扰，尤其在户外。基于位置指纹的Wi-Fi定位的算法最早期由微软研究院研究人员提出，2000年，他们开发了相应的室内定位系统RADAR。RADAR定位系统利用“指纹识别”技术定位，它是基于RSSI技术的室内无线射频定位系统，利用信号传播模型和经验测试相结合的场景法进行定位。 Horus系统是基于RSS（Received Signal Strength）指纹算法的一种定位系统。它是由马里兰大学计算机系MIND实验室设计的，在定位位置计算中，它引入了概率分布模型，希望通过概率分布情况更好的反应信号强度分布情况，利用信号强度的差异区分不同的位置点。2000年，MIT实验室研发了Cricket系统，Cricket系统是由被定位端携带的接收机和若干个固定在建筑物内的信标节点组成。每一个信标拥有唯一的标示，辨别自身所处的位置信息。通常，这类的系统需要在墙壁上提前布设RF设备和超声波设备，并采用TDOA(Time Difference of Arrive)的方式进行定位。2005年1月，美国宾夕法尼亚大学医院采用室内定位系统（IPS）来寻找误放的设备。IPS是全球定位系统的延伸，把由电池供电的RFID标签附在医院设备上，该标签不会对医疗设备造成干扰。在国内，目前从事室内定位技术研究的机构主要在科研院所和高校，复旦大学对现有的“路径-损耗”模型进行修正，并提出室内CDMA用户定位方法和基于接收信号强度测量的室内定位方法；中国科学院地理科学与自然资源研究所从事室内定位的普适计算等技术的研究；西安交通大学从事基于实验场景的概率指纹定位算法研究；西南交通大学从事射频识别室内定位算法研究；东华大学着力研究室内位置感知技术和普适计算。1.3 本课题的贡献以及研究意义本课题的研究内容主要包括室内地磁特征分析、地磁指纹空间与物理空间的位置映射、室内物理空间位置挖掘以及系统模型的实现，本文的主要贡献和创新之处包括如下几个方面：对室内地磁特征进行全方位分析，首先对地磁的三轴特性进行研究，从实验结果上确定了后续实验的研究方向地磁的一维特性（地磁强度）。由于众包采集数据具有多样性的特点，课题又从多个方面进行室内地磁特征的研究，其中包括不同采集路径地磁分布特征、不同采集高度地磁分布特征、不同采集姿势地磁分布特征以及不同采集方向地磁分布特征。通过大量的实验说明利用室内地磁进行定位的可行性。传统的建立地磁指纹数据库的方法需要在离线阶段人为的建立关键点的物理位置和该点上收到的地磁指纹的映射关系。该方法有明显的弊端，不仅需要大量的专业人士提前在室内环境部署相关的关键点，还需要避免由于操作不当造成的脏数据的录入问题。基于此本文提出一种基于众包的关键点的提取和采集方法，该方法利用手机中的加速传感器、惯导设备以及航迹推算算法，推算下一时刻的位置，自动的获取地磁指纹空间中的关键点，并建立地磁指纹空间与物理空间的位置映射关系。传统的定位系统需要在室内定位导航前，向定位系统中导入地图信息，这样不仅需要事先大量的采集工作，还需要专业人士按比例绘制工程地图，同样也是耗费大量的人力物力。本文的一个研究点即是利用众包指纹采样来挖掘物理空间。现有的空间位置挖掘算法往往存在如下这两个问题:1.需要大量的人为干预，单纯的物理空间挖掘显得难度过大。2.市面上可以通用的物理空间位置挖掘的系统较少，有些系统往往仅仅针对单个或者某几个特定的物理场景，能适用于任何物理空间位置挖掘的软件几乎不存在。根据本文提出的算法，课题成员在原来版本的定位系统NaviStone上进行了一些修改，其中地磁采集数据通过众包采集的方式获得，然后利用众包采集的数据进行地磁指数据库的建立，最后对基于众包的室内定位进行误差分析，虽然在精度上和标准定位存在误差，但是误差在3m以内的概率高于90%，可以应用于一些室内场景。1.4 论文组织结构本文利用众包采集地磁数据的方法，通过采集室内地磁数据建立“物理位置-地磁指纹”映射关系，从而实现确室内定位。全文分为6章，安排如下：第一章，绪言。简要介绍了室内定位技术的背景，并说明现有室内定位技术种类以及基于地磁的室内定位技术的发展前景，国内外室内定位技术的发展情况以及本课题研究的意义及内容等。第二章，室内地磁特征分析。首先对地磁的三轴特性进行实验，由实验结果确定后续对地磁的研究内容地磁强度，然后课题分析了不同路径、不同高度、不同姿势以及不同方向等地磁采集数据的特征，从而说明利用室内地磁进行定位的可行性。第三章，基于众包的地磁指纹空间与物理空间的位置映射。本章主要研究地磁指纹空间到物理空间的映射，通过K-means聚类算法将不同路径的采集数据进行分类，在分类过程中会用到DTW算法计算两条曲线之间的相似度。分类完成后，将每一类的曲线进行融合，形成一条曲线，然后建立地磁指纹空间与物理空间的映射，从而完成数据库的建立。此外还对本课题使用的拐弯检测技术进行简单的介绍，说明其进行拐弯检测的可行性。第四章，基于众包采样的物理空间位置挖掘。本章主要研究通过众包的方式挖掘物理空间拓扑结构，首先通过 众包的方式大量采集数据文件，将采集的数据文件进行DTW处理，得到两条曲线之间的相似度，然后通过AP算法进行聚类，再将每一类中的曲线进行融合，得到物理空间的简单拓扑结构。第五章，NaviStone定位系统。本章简单介绍NaviStone室内定位系统的基本框架结构，然后讲述了整个系统的定位流程，最后进行系统的检测，评测系统的定位精度并画出相应的CDF曲线，再将基于众包采集数据建立的地磁指纹数据库与标准点采集数据建立的地磁指纹数据库进行比较，观察两种方法的差异。第六章，总结与展望。该章主要总结本文的研究内容，对取得的一些成果进行总结。然后提出现有系统的不足以及需要改进的方向。2 室内地磁特征研究近年来，基于磁场的室内定位技术一直都是研究热点。研究表明，磁场普遍存在于我们周围，是一种无形的具有波粒辐射特性的物质，具有看不见摸不着的特点。任何磁体周围都会产生磁场，并且与其它磁体产生的磁场相互作用，从而改变由单一磁体产生的磁场强度。本文实验采用众包的方法采集地磁数据，得到的地磁数据具有多样性。本课题在地磁的三轴特性、分布特性，采集地磁数据持手机的姿势、高度、方向以及采集地磁数据的时间和地点等方面进行一些实验，进而探究室内地磁特征。本文实验均以中科院计算所7层作为实验场地，其平面图如图2.1所示。图2.1 中科院计算所7楼平面图2.1 地磁三轴特性通过阅读一些文章了解到，通常情况下，手机中的地磁传感器获得的地磁三轴信息，受地磁采集姿势和地磁采集设备的影响较大，没有统一的模式，但是其三轴合成标量（,为地磁传感器三轴分量），即地磁强度大小，则相对稳定。为进一步印证这个理论，本课题进行了一次实验，在同一条路径采用不同的持手机姿势(竖向放置和横向放置)重复采集数据两次，分别获取地磁三轴的数值，然后将对应分量进行比较，实验结果如图2.2所示。再将他们的模（地磁强度大小）进行比较，实验结果如图2.3所示。 图2.2 地磁三轴分量测试图图2.3 地磁三轴分量合成图通过对上述实验结果的观察，不难发现本次实验很好的印证了理论。在图2.2中，观察不同姿势获得的三轴分量，会发现x，y，z三个对应分量的曲线不但走势不同而且数值差异较大，对应分量之间也不存在一定的规律。反观图2.3中的曲线，两条曲线不但走势相同而且数值大小相近，曲线波峰波谷互相对应，有一定的规律。基于此实验，可以说明地磁三维特性的研究相对困难，而一维特性的研究则相对简单。本课题也只是对地磁的一维特性（地磁强度大小）进行了研究和分析。2.2 不同物理路径的地磁分布特性在室内环境中，由于钢筋混凝土结构、机房等设备会对磁场造成局部紊乱现象，因此理论上讲室内场景不同的区域，其地磁强度观测结果应当具有良好的可区分性。为验证理论的正确性，本课题进行了如下实验，选取实验场地中7条路径进行采样，采样频率为50Hz（以下实验均在此频率下采集地磁数据），将采集的地磁数据进行处理，得到实验结果如图2.4所示。 图2.4 室内地磁空间分布测试图从图2.4中可以清楚的发现7条路径的地磁波形差异比较大，地磁强度大小也迥乎不同，地磁分布形式各异，因此不同路径之间具有较好的区分性，同时每条路径具有多个波峰波谷，可以作为局部突出特征。由此可见，室内地磁分布具有很好的地理差异性，适合用来室内定位，但定位效果需要进一步进行验证。2.3 不同高度的地磁分布特性用众包的方式进行数据的采集，无可厚非会遇到由于采集者身高差别，持手机高度不同，从而采集同一条路径的地磁数据但结果不一致的问题，但持手机高度不同是否对地磁的分布产一定的影响呢？为验证这个问题的正确性，本课题采取如下实验，用同一款手机对同一条路径重复采集4次数据，每次采集数据持手机高度均不同，分别为115cm、135cm、145cm和155cm，实验结果二维平面图如图2.5所示，三维立体图如图2.6所示。图2.5 不同高度地磁分布平面图图2.6 不同高度地磁分布立体图从图2.5中可以观察到不同持手机高度采集的地磁数据，虽然其大小存在一些差异，但曲线的走势基本相同，其中存在一些超前或滞后的地方（波峰波谷并不是完全对应），这是因为在采集数据的过程中，由于人的行走速度不是固定的，同一条路径同一地点不同时刻行走时的速度也是不相同的，从而导致同一物理空间点采集的地磁数据个数不相同，从而图像的波峰波谷也不是完全对应。图2.6将不同高度采集的地磁数据分别显示在相应的高度，这样使每条曲线的走势观察的更清楚。为了进一步说明不同高度采集的地磁值虽然大小不同，但是其走势大体相同，我们对四条曲线的数据进行了差分处理，实验结果如图2.7所示· 图2.7 不同高度差分图从图中可以看到，经过差分处理后的四条曲线在形状上基本上是一致的，出现超前和滞后的原因和前面相同（人的行走速度不固定），由此充分说明曲线的走势是一样的。在后续建立指纹数据库的工作中不用再考虑由于采集高度不同而带来的问题。2.4 不同姿势采集的地磁分布特性由于众包技术采集到的数据具有多样性的特点，那么持手机姿势的不同对采集的地磁数据是否有影响呢？为了解决这个疑问，本课题进行了如下实验，使用同一手机对同一路径重复采集四次数据，每次采集数据持手机的姿势均不同，分别为平放、下垂、口袋中和背面向上，将采集到的数据进行处理，结果如图2.8所示。 图2.8 不同采集姿势的地磁数据测试图通过对图2.8进行观察，可以发现不同的采集姿势所获得的地磁曲线不仅在形状上相似，而且在地磁大小上也非常相近。在一定程度上可以说，采集姿势和采集到的地磁数据是无太大关联的。为了进一步观察曲线的走势，同样我们对数据进行了差分处理，结果如图2.9所示。图2.9 不同姿势差分图通过观察实验结果，可以说明四条地磁曲线的走势是大体相同的，其中也出现了上个实验中的现象，曲线出现超前或滞后的情况，波峰波谷并不是一一对应，同样也是由于人的行走速度不固定引起的。通过本次实验可以说明不同采集姿势采集到的地磁数据其曲线特征具有一定的相似性，在进行分类时同一路径不用再考虑采集姿势不同带来的数据问题。2.5 同一路径不同方向地磁分布特性在一个现实的场景中，由于人的需求不同，到达的目的地不同，因此同一条物理路径会出现不同的行走方向，猜测同一物理路径不同行走方向采集的地磁数据也可能存在差异。基于这个疑问，本课题进行了一次实验，这次实验的场地有两个，一个是中科院计算所7楼的一个会议室，会议室中间是一个会议桌，采集数据时沿着会议桌行走，分为顺时针行走和逆时针行走，每个行走方向采集3次数据；另一个是中科院计算所7楼的一个主干道，同样也是分为两个方向采集地磁数据，每个方向采集3次。场地一的实验结果如图2.10所示，场地二的实验结果如图2.11所示。 图2.10 同一房间不同方向地磁分布测试图 图2.11 同一路径不同行走方向地磁分布测试图通过上图两个场地的实验结果展示，可以清楚的发现同一物理路径不同的行走方向所采集的地磁数据，虽然其在大小上有一定的差异，但是地磁曲线的形状是相似的。在一定程度上可以说，同一物理路径不同采集方向所获得的地磁曲线在趋势上是相同的，同时在进行分类处理时，同一路径不用再考虑采集方向而带来的问题。2.6 本章小结本章主要研究室内地磁的分布特征，首先通过众包的方式采集大量的地磁数据，然后对这些地磁数据进行全面的分析，其中包括对不同采集路径的地磁特性分析，不同采集高度的地磁特性分析，不同采集姿势的地磁特性分析以及不同采集方向的地磁特性分析。这样全面的分析有助于发现地磁的分布特点，从而提出更好的定位算法。另外还从地磁的三维特性和一维特性方面进行了简单的研究，地磁的三维特性变化没有一定的规律，研究起来比较复杂，其一维特性相对简单，具有一定的规律性。通过进行大量的实验，充分说明了利用地磁进行定位的可行性。3 基于众包的地磁指纹空间与物理空间的位置映射定位技术的实现无可厚非会遇到拐弯检测的问题，本章开头首先对本课题采用的拐弯技术进行实验并阐述，以此证明使用该拐弯技术在实现拐弯检测上的可行性。物理空间内的每一点都存在地磁，通过手机中的地磁传感器可以获得每一点附近的地磁值，这里将其命名为地磁指纹数据。人工输入地磁指纹数据不仅耗费大量的人力物力，而且极易出现输入错误，从而给系统带来脏数据。本课题研究的一个目标是，运用众包的思想，自适应的建立地磁指纹空间与物理空间的位置映射关系，从而达到不需要专门人员更新指纹数据库的目标。要达到上述目标需要进行三个步骤的处理，第一步，对长的轨迹数据进行单一化处理，将长的轨迹分割成短的轨迹，每一段短轨迹之间没有任何的拐角点；第二步，运用K-means聚类算法将相似的地磁轨迹进行分类，两条地磁之间的相似度可以根据DTW(Dynamic Time Warping, 动态时间归整)算法计算得到；第三步，采用航迹推算的方法建立地磁指纹空间与物理空间的映射关系。3.1 拐弯检测目前对室内定位的研究越来越多，相应的拐弯检测技术也层出不穷。本文利用陀螺仪和加速度传感器来判断拐角点。理论上讲，检测到拐弯是很容易的，因为现有的智能手机中存在加速度传感器和地磁传感器，通过它们能够轻松获得手机的方位角（Azimuth）。人在正常行走情况下，由于不断摇摆，方位角会出现一定变化，但变化量一般在 以内，如果前一个方位角和后一个方位角差值超过阈值（）即可被认为是拐角点。为验证利用陀螺仪和加速度传感器能够完成拐弯检测的功能，本课题进行了如下实验，在计算所7层选取6条路径作为实验路径，其中包含5个拐角点，如图3.1所示。将采集的数据进行处理，得到如图3.2实验结果，其中图中出现的峰值表示拐角点的位置（前一个方位角和后一个方位角的差值超过20度）。 图3.1 拐弯检测采样路径 图3.2 拐弯检测样本通过上图实验结果可以发现，人在进行行走时由于不断的摇晃方向角也会发生一定的变化，但角度变化一般在10度以内，进行拐弯时，方向角会发生较大的变化（图中波峰的点）。在一定程度上说，运用此方法进行拐弯检测具有一定的可靠性。3.2 地磁轨迹单一化 在对地磁轨迹进行分类前，考虑到采集的地磁轨迹长短不一，长轨迹地磁数据较多，短轨迹地磁数据较少这个问题，直接对地磁轨迹进行分类开销比较大，而且使用DTW算法进行相似度计算时常常也是做了一些不必要的工作。所以在进行分类前，需要将地磁轨迹数据进行单一化处理，将长地磁轨迹分割成一段段短轨迹。在本文中，利用室内环境中某些拐弯的节点作为自然分割点。3.3 基于地磁的分类由于航迹推算算法有一定的误差性，因此进行一次数据采样获得的坐标数据和该地理位置真正的坐标数据存在误差。基于此，需要对每条路径采集多次数据，然后运用K-means算法对采集的数据进行分类，每一类中每条数据的坐标值相加再除以数据条数作为该点的坐标值，这样能减小了坐标误差，从而使坐标数据更准确。K-means算法的基本思想是：以空间中k个点作为中心进行聚类，对最靠近他们的对象进行归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果，具体算法如下：假设要把样本集分为k个类别：（1）适当选择k个类的初始中心；（2）在第n次迭代中，对任意一个样本，求其到k个中心的距离，将该样本归到距离（欧几里得距离）最短的中心所在的类；（3）利用均值的方法更新该类的中心值；（4）对于所有的k个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。在地磁轨迹单一化后，采用K-means分类算法，将地磁轨迹相似的路径划分为一类。在分类过程中，需要计算两条曲线的相似度，课题采用DTW（Dynamic Time Wrapping）算法完成相似度的计算。DTW算法的核心思想是通过计算两个时序序列中最佳的匹配点，获取整个序列的最短匹配距离。例如两条路径获取的磁场序列为和，其中和不一定相等，用表示的前个数据和的前个数据进行匹配时的最短距离，然后通过式（3.1） （3.1）其中 表示 和 之间的欧式距离，这样最终得到的， 即是两条路径进行匹配的最短距离，它将作为两条路径匹配度的间接衡量指标。本课题对上面两种算法进行结合，算法流程图如下图3.3所示。图3.3 地磁分类算法流程图上图简要描述了本章地磁分类算法的流程，下面对流程中的关键步骤再进行进一步说明：1.这里的DTW算法的返回值不再是两个序列的最短距离，而是对最短距离进行了简单处理，处理后的数据本文将其定义为两条曲线的相似度。上述DTW算法返回的是两条曲线的相似度。2.这里的K-means算法不再是根据欧氏距离的大小进行分类，而是根据DTW算法计算出的两条曲线的相似度进行分类。3.分类完成的标准是每一类中所有曲线与聚类中心的相似度均大于0.5，如果一条曲线和每一类的聚类中心曲线的相似度均小于0.5，则认为该数据为脏数据。为了验证上述算法的分类效果，本课题实施了如下实验，在中科院计算所7层选取三条路径进行地磁数据采集，每条路径重复采集3次数据，如图3.4所示。实验室的平面图中3条带箭头的直线表示3条数据采集路径。 图3.4 地磁采样示意图地磁数据采集完毕后，通过K-means算法和DTW算法对数据实施分类，图3.5展示了本次实验分类的结果。从图中实验结果来看，达到了理想的分类结果，所有地磁曲线被分成3类，每一类包含3条地磁曲线，这与实际采集路径完全吻合，在一定程度上可以说，使用本算法可以完成地磁曲线分类的任务，其具有一定的可靠性。 图3.5 K-means 算法分类结果图3.4 建立地磁空间与物理空间的位置映射地磁轨迹分类完成后，接下来需要将同一类中的地磁轨迹与数据库中存储的标准轨迹进行匹配，并将地磁轨迹中的数据与地理空间中的点相对应。从而完成地磁空间到物理空间的映射。其具体的实施过程如下:第一步：利用聚类的簇心曲线（K-means算法迭代完成后每一类都会存在一个中心曲线）数据和数据库中所有的物理路径地磁数据进行匹配。如果簇心曲线与某条物理路径地磁数据相似度很高，则认为这条簇心曲线的数据是在该条物理路径上采集的。第二步：在轨迹匹配结束后，将同一类的地磁轨迹进行融合，建立地磁空间与物理空间的映射关系。融合的过程与计算DTW相似度的过程基本相同，即找出轨迹中“物理空间”最为接近的两点，并将该点的地磁认为是对应物理空间的地磁。这里的“物理空间”最接近的两点不是笛卡尔坐标系中最接近的点，而是在DTW推算过程中，推导出某一点的前面所有点。一般情况下，一个物理空间点对应一个地磁轨迹点，也可能出现单个物理空间点与多个地磁轨迹点相对应，如图3.6（示意图，不是实际的路线）所示，上面的曲线代表地磁曲线（存储的是地磁数据），下面的曲线代表物理空间的曲线（存储坐标数据）。在建立地磁指纹库的过程中，只需要将多个地磁点求平均值，即得到该物理点的地磁数据。 图3.6 地磁轨迹点与物理空间点映射图为了进一步验证曲线融合策略是否有效，本小节利用上一小结中分类完成的结果（3条路径共9条曲线通过K-means + DTW算法分为3类），将同一类中的所有地磁数据进行融合，融合结果如图3.7所示。 图3.7 曲线融合图从上图的融合实验结果来看，融合曲线1和3与实际轨迹更加吻合，融合曲线2出现了稍许偏差，由于行走路径具有一定的宽度，所以出现这样的融合曲线具有一定的可接受性，从而说明运用此方法建立地磁指纹数据库是可行的。3.5 本章小结本章主要讲述了建立地磁空间到物理空间映射的方法，此外还简单介绍了一下本课题所采用的加速度传感器和陀螺仪判定拐弯技术。之后详细介绍了空间映射步骤，并采集数据进行实验，从实验结果来看，该算法比较令人满意，而且能够较好的实现数据的分类，具有一定的可靠性。4 基于众包采样的物理空间拓扑结构挖掘本课题研究的另一个目标是：利用众包的思想挖掘物理空间拓扑结构，生成物理空间拓扑图。达到这一目标同样需要进行三个步骤的处理，第一步，对轨迹进行单一化处理；第二步，运用AP(Affinity Propagation)聚类算法对地磁轨迹进行聚类(由于事先不能判定具体分为几类，所以不能采用K-means等聚类算法)；第三步，根据采集的地磁数据，构造物理空间拓扑结构。4.1 基于众包的AP算法的聚类由于事先无法确定这些采集的路线数据应当被划分成几类，因此在物理空间位置挖掘的过程中，不能采用诸如K-means这样事先需要设定划分类别数目的算法。本实验采用基于AP(Affinity Propagation)聚类算法的的轨迹聚类。AP聚类算法的核心是利用识别的数据中心点来形成围绕该中心点的簇，初始时将所有的点均视为潜在的中心点，然后数据点之间不断的交换信息直至形成符合要求的中心点和簇。在AP聚类算法中，首先计算两两数据点之间的相似度，构成初始相似度矩阵S，为数据点i和数据点j的相似度，在本文中利用两条曲线进行匹配时的DTW值作为两条轨迹的相似度，DTW值越大说明两条轨迹越相似；矩阵S对角线的值作为判断点能否成为聚类中心的标准。之后数据之间互相传递信息，其中包括两种信息：吸引度R(Responsibility)和归属度A(Availability)，如图4.1所示。数据点数据点ResponsibilityAvailability图4.1 AP算法数据传递消息在该算法中， 表示从数据点发送到候选聚类中心的数值消息,反映点是否适合作为点的聚类中心。 则表示从候选聚类中心发送到数据点的数值消息,反映点是否选择作为其聚类中心。与越大，则点作为聚类中心的可能性就越大,并且点隶属于以k点为聚类中心的聚类的可能性也越大。AP算法在迭代过程中通过不断更新每一个数据点的吸引度R和归属度A的值,从而达到产生个高质量聚类中心的目标,同时根据的值将其余的数据点分配到相应的聚类中。初始时，设定，后续迭代过程如下所示 （4.1） （4.2） （4.3）同时AP算法引入了起收敛作用的阻尼系数 ，在迭代时，对R和A进行加权更新，公式如下： （4.4） （4.5）通过上述公式计算后，根据 的值来判断数据点k是否为聚类中心 (当时，通常认为数据点是一个聚类中心)。当迭代次数超过算法指定的最大值或者当聚类中心连续多次迭代不发生改变时，终止算法，完成聚类。AP算法在解决事先无法确定分类数目的聚类问题方面无疑是一个较好的方法。为了验证其可靠性，本章进行了如下实验，以计算所7层作为实验场景，选取7条路径进行数据采集，总共采集20条地磁数据，然后利用AP聚类算法对这些地磁数据进行聚类，聚类结果如图4.2所示，图中每个点代表一条地磁轨迹，两点间的连线表示这两条地磁轨迹属于同一类，每一类的中心为簇心。由实验结果可以发现，聚类的结果和实际路径采集是吻合的，图中一共有7类，对应7个路径，每个分类中的数量也与实际采集路径条数相对应，为了实验结果便于观察，本实验设定了生成每个点的坐标。通过这个实验，可以说AP算法在处理本文问题中起到了相对较好的效果，其具有一定的可靠性。图4.2 地磁轨迹AP聚类结果图另外，上图的实验结果和传统的AP聚类结果有所不同，因为本AP算法中不再是根据欧氏距离的大小进行分类，而是根据两条曲线的相似度进行分类，传统的AP聚类算法是根据两点之间欧氏距离的大小进行分类，如图4.3所示，每一种颜色代表一类，每一类的中心为簇心，随机生成点根据两点间的欧式距离进行划分类别。图4.3 传统AP聚类结果图4.2 物理空间拓扑结构挖掘在上一节中，已经验证了AP算法在解决分类问题上的有效性，本小节主要讲述在地磁轨迹分类的基础上进行物理空间拓扑结构的挖掘。在上一小节中，通过使用AP聚类算法已经完成了对地磁轨迹的分类，接下来需要做的就是将每一类中的地磁数据进行融合，融合的方法和前面相似，首先取出每一类中的簇心曲线，然后将同一类中的其他曲线与簇心曲线进行DTW运算，在DTW运算过程中，会记录簇心曲线上的点对应同一类中其他曲线上的点，然后求得所有对应点的和，除以点的个数，作为该簇心曲线坐标下的地磁值，X、Y坐标的确定所采用的方法和该方法相同，得到融合曲线后，将每条曲线的坐标数据进行处理，得到简单的空间拓扑图。采用上述提出的基于地磁的物理空间拓扑结构挖掘算法，本课题进行了一次实验。在实验环境中，可以将实验场地的空间大致分为两类：主干道、不连通区域（如隔板、墙体、办公桌等）。采集地磁数据的路径和数量和上一小节中的AP聚类实验的地磁数据相同，实验结果如图4.4所示，图中每一种颜色的曲线代表一条主干道，其他白色的区域表示不连通区域，为了更好的观察实验结果，在进行绘图的过程中，对坐标数据进行了简单的处理，图中显示的坐标为相对图中原点的坐标，并不是实际采集的坐标。图4.4 物理空间拓扑结构图从上图来看，实验结果大致展现出了物理空间的拓扑结构，并且和实际采集路径也恰好匹配，从而说明本章提出的算法在物理空间拓扑结构挖掘上具有一定的可行性和可靠性。4.3 本章小结本章主要介绍了物理空间拓扑结构挖掘的一种方法基于众包采样的物理空间拓扑结构挖掘。首先简单描述了该方法的基本流程，分为3个步骤：第一步：地磁轨迹单一化处理；第二步：AP算法进行聚类；第三步：构建物理空间拓扑结构图；然后详细介绍了基本流程中的各个环节，最后进行实验得到实验结果。物理空间拓扑结构挖掘是一项相对困难的任务，本章只是在小范围内进行实验，虽然得到的结果差强人意，但是仍需要其他学者进一步的研究，使算法的鲁棒性更强。5 NaviStone定位系统N