基于移动设备多传感器融合的室内定位系统.pdf 10页

'中国科技论文在线http://www.paper.edu.cn基于移动设备多传感器融合的室内定位系#统**张金，徐浩聪，高岩，宫晓利5（南开大学计算机与控制工程学院，天津300350）摘要：室内定位问题目前没有通用的解决方案，各种定位技术的适用场景和实施方式有着很大的差别，其中基于指纹匹配的室内定位方案以定位精度高，易于部署等特点成为近几年新兴的研究热点。由于移动设备自身的局限性，基于指纹匹配方案的实时性得不到很好的满足。本文通过提取室内环境的物理空间特征10和无线信号特征，并综合利用智能手机上的多种传感器设计了一种室内定位方案。在指纹训练阶段，本文提出了一种视距平均采样方法，通过将复杂环境抽象建模为直线连接，有效的降低了系统的复杂度。为了提高定位精度和稳定性，系统将Wi-Fi信号与FM信号进行融合作为指纹信息。为了简化指纹匹配过程，本文利用计步器采集的步长信息进行指纹标定和位置检索，在指纹中加入了计步信息，并在匹配时通过计步信息限定搜索范围以缩小匹配范围。最后本文在Android平台完成了系统的原型开发，实验表明融合指纹15方案的定位误差在0-5m之间，所需匹配指纹点数量相较于全局匹配平均减少了82%。关键词：室内定位；指纹匹配；移动设备；实时性中图分类号：TP391Multisensor-basedMobileIndoorLocalizationSystem20ZHANGJin,XUHaocong,GAOYan,GONGXiaoli(CollegeofComputerandControlEngineering,NankaiUniversity,Tianjin300350)Abstract:Extensiveresearchhasbeenperformedinindoorlocalization.Duetobetteraccuracyandeasierdeployment,fingerprintbasedsolutionsbecomeprevalent.WhilemostRSSfingerprintsolutionsbarelymeetthedemandofreal-timeduetothelimitationsofmobilephones.Toovercomethese25limitations,afterstudyingthefeaturesofindoorenvironmentandwirelesssignals,wepresentamobilephonebasedsystemthatexploresindoorlocalizationviamultiplebuilt-insensors.Inthetrainingphase,thispaperproposeanewsamplingmethodnamedLengthofSight(LOS)sampling.Bysimplifyingsystemmodeltostraightlinesegments,thecomplexityisdecreased.Forbetteraccuracyandstability,thissystemusesmultiplewirelesssignalsincludingWi-FiandFM.Tosimplifythematchingprocess,30systemutilizesstepinformationprovidedbypedometertomarkfingerprints,addingcountingstepstofingerprint.AccordingtopedometerinformatioMultisensor-basedMobileIndoorLocalizationSystemn,systemcannarrowdownfingerprintsamplestobematched.Intheend,thesystemisdeployedonanandroidsmartphone.Experimentshowsthatsystemcanachieveanaveragematchpointsreductionof82%.35Keywords:IndoorLocalization;Fingerprint;MobileDevices;Real-time0引言移动互联网的出现从方方面面改变着人们的生活，随着基于用户位置信息的相关技术的40应用和发展，位置服务已经成为人们日常工作、生活所必需的一项基本服务需求。在这个需求的推动下，定位技术特别是室内定位技术成为了研究的热点。研究者们提出了许多种技术[1][2]方案，这些方案根据具体的实现技术大致可以划分为基于信号测距、基于指纹匹配、基基金项目：高等学校博士学科点专项科研基金（20130031120028）作者简介：张金（1979年-），男，副教授、硕导，主要研究方向：物互联网金融;计算广告学;数据可视化;移动电子商务;联网与云计算通信联系人：宫晓利（1983年-），男，讲师，主要研究方向：嵌入式系统，移动云计算，物联网.E-mail:gongxiaoli@nankai.edu.cn-1- 中国科技论文在线http://www.paper.edu.cn[3][4]于惯性导航和基于传播模型等几种类型。其中基于指纹匹配的定位通过在定位空间中采集不同位置发出的信号特征参数建立指纹数据库，通过将实际接收信号与数据库中的信号特45征参数进行比对来实现目标的定位。该方案减少了对信号传播过程的依赖，定位精度较高，相对来说是一个较好的室内定位方案。[5]由于移动终端硬件存在局限性，因此在这些设备上部署指纹定位方案存在许多困难。以智能手机为例，首先，手机的接收能力相对较弱，导致定位时的信号差异较大。其次，手机上的计算资源有限，当指纹库变大时，进行全局匹配的耗时较长，定位系统的实时性需求50得不到满足，影响了用户的使用体验。针对这些问题，本文设计并实现了一个针对移动设备的室内定位方案。系统使用Wi-Fi和FM的融合信号作为指纹信息，相较于仅用Wi-Fi信号而言增加了指纹信息的维度，由于[6]Wi-Fi和FM信号的相关性较小，因此用FM信号辅助定位可以提高定位的精确度。在指纹建立过程中，通过提出一种基于视距平均采样的方法，提高了指纹之间的空间关联度，将55空间中的任意定位过程转化为路径查找过程，简化了系统模型。在定位阶段，系统利用提出的最小集匹配算法缩小了当前指纹库的搜索范围，和全局搜索相比减少了匹配过程的计算量并过滤了影响定位精度的离群点，提升了系统的实时性和精确度。最后本文在Android系统[7]平台上实现了定位系统的原型开发，通过分析实验数据对系统的有效性进行了验证。1基于视距平均采样的指纹库建立方法60在对室内环境空间特征进行分析的基础上，本节提出了一种视距平均采样的指纹训练方法，该方法增加了指纹间的关联度，简化了系统模型；同时为了解决信号抖动问题系统对指纹数据进行了预处理，具体过程如下文所述。1.1视距平均采样方法室内环境间具有许多相似性质，通过区域划分可以对其加以抽象。许多场景下，室内空65间常常被墙壁、家具等障碍物分隔开，并不是一片空白的自由空间。因此人在这种空间中能够驻留的点和区域是有限的，而且行进的路线可以简化为由多条直线组合而成。由于在这种环境约束较大的空间中定位的精准度要求并不苛刻，如果能够确定人员当前所处位置位于简化模型中的哪条直线上的哪块区域，那么在该区域通过目视就能轻松找到目标，因此针对这[6]类空间模型的简化是可行的。许多研究者也采用了这种简化模型，如文献中提出特别是对70于存在很多兴趣点的2D平面楼层环境，如办公区、商场等，兴趣点之间通过走廊连接，人们行走的路线受到周围环境的约束。图1.1展示了一个典型的室内平面路线图。-2- 中国科技论文在线http://www.paper.edu.cn图1.1典型的室内平面路线图Fig.1.1ATypicalIndoorPathwayMap75从图1.1中可以看出室内环境并不是全连通的，例如，走廊和房间之间存在门的阻隔，房间与房间之间存在墙壁的阻隔。这些阻隔切割了室内空间，形成了许多互相之间不连通的空间区域，因此本文根据空间上的连通性对室内的空间进行划分，并按照连通区域划分将指纹库进行聚合处理。根据室内环境的这些特征，系统模型得到了简化。由图1.2(a)可以看出，一个连通区域80中存在许多起点与终点相连通的直线路径，这些路径可以根据视距可达性进行划分。如果人在当前位置仅通过目视就能看到目标位置，那么该目标位置就是一个视距可达位置，具有视距可达性。这些视距可达位置中离用户当前所在位置最远的称作视距端点。(a)(b)85图1.2视距可达示意（a）和简化后的模型（b）Fig.1.2LOSIllustration(a)andSimplifiedModel(b)在图1.2中视距可达示意图中，假定人当前所在位置为图中十字交叉口，那么当前所在位置的视距端点如图1.2(a)中黑点所示。通过连接这些端点构成直线线段，如线段AB，室内模型可简化为图1.2(b)所示。在地图处理时，需要对路径相交的点进行坐标标记，因为在90交点处行走路径可能发生转换。基于上述简化模型，本文提出了视距平均采样方法，即针对简化模型中的每一条线段进行平均指纹采集并生成指纹索引，采集过程中利用智能手机中的计步传感控制平均指纹采集过程。具体过程如图1.3所示：首先，系统根据简化模型选择一条直线段按照步长打点采样，建立该线段的指纹索引。以线段AB为例，采集者首先记录线段端点A和B以及线段上所95有拐点M的空间坐标，然后从地图上的A点对应的位置保持相对均匀的步幅走到B点对应的位置，每走一步即在到达的位置停留一定时间采集信号，记录当前位置的信号强度值，最后记录从A走到B的步数总和，这些信息就构成了一条线段的指纹索引。在采样过程中，采样者步幅均匀，步长差异不大，整个过程可以近似的认为是对线段的平均打点，在已知线段端点坐标和步数总和的情况下，中间采样点的坐标可以根据步长的平-3- 中国科技论文在线http://www.paper.edu.cn100均值通过几何关系计算出来，因此不需要在采样时单独记录，省去了繁复的坐标标定过程，提高了指纹训练效率。另外，由于该采样方法建立了指纹点与线段之间的关联，因此在定位阶段指纹库匹配就转化为对这些指纹线段的搜索，简化了匹配模型。图1.3指纹采集过程105F.g.1.3ProcessofSamplingFingerprint1.2信号抖动问题与处理方案在室内环境中，Wi-Fi信号容易受到同频干扰、多径效应以及障碍物遮挡的影响而产生[8][6]明显的信号强度差异，因此为了提升信号的稳定性，需要加入一个辅助信号，根据文献的研究结果，本文选取FM作为辅助信号，采集多个AP信号强度信息和多个固定频段FM110信号强度信息，将两者进行融合作为指纹信息。融合的方式为将测量点测得的多个AP信号强度值与多个FM信号强度值经过数据预处理后共同组成一个指纹向量作为该点的指纹信息。鉴于Wi-Fi和FM信号测量单位和测量范围各不相同，为了构建Wi-Fi与FM的融合指纹，需要对它们进行数据标准化处理，使两者具有相同的影响因子。本文采用z-score方法rss115将两种信号强度进行数据标准化，遵循的原理为：rss"，其中rss表示原始值，rss"表示数据标准化后的值，表示数据的标准差。经过数据标准化之后，Wi-Fi指纹和FM指纹被映射到相同的取值范围内，两者联合构成了融合指纹。针对智能手机信号的波动性，本文对指纹信号进行了特殊处理，包括均值滤波以及双向采样。本文在每个指纹点重复采集20个左右的样本数据，将两者信号的均值滤波结果作为120最终的指纹向量。另外，为了解决因不同朝向导致同一点Wi-Fi信号强度偏差较大的问题，在系统信号采集时对两个信号进行了双向采样。即对指纹线段（如图1.3中AB）正向反向各采样一遍，得出两个方向的信号强度向量：iiiirssAB[rssrss12,,rssn]iiiirssBA[rssrss12,,,rssn]ii125正号表示正向采样，负号表示反向采样。rss和rss联合组成了AB区间内第i个视ABBAi距平均采样点的信号强度rss：ABiiirss={rss,rss}ABABBA-4- 中国科技论文在线http://www.paper.edu.cn2基于局部最小集匹配的定位过程根据1.1节所述，在指纹库建立阶段，系统依据连通性将空间划分为不同的聚类，处于130同一个连通区域内的指纹段属于一个聚类。本节通过对聚类内和聚类间指纹的位置关系进行分析，提出了差异化的指纹搜索策略，确定了需要搜索的最小指纹集合。在定位阶段，系统分别计算实时信号强度与最小指纹集合内指纹向量的余弦相似度，选择相似度最高的指纹点作为当前位置的估计点。2.1聚类内搜索135在指纹聚类内部，多个指纹段在现实空间中存在相交性，是一个连通的空间区域。指纹段的交点表征的是在室内环境中存在的拐点，在拐点附近可能发生路径转换。在室内环境中，受墙等障碍物对路径的约束作用，人的行走路线基本处于上文提出的简化模型中的线段上。图2.1聚类内搜索140Fig.2.1InnerClusterSearch如图2.1所示，在聚类C内，假设Q是用户当前坐在位置，空间坐标已知。从Q点出1发，设备通过计步器统计步长L，步长的最大阈值为S，则用户的最远运动距离为LS。线段AB和CD交于点M，若Q点与拐点M的长度小于整个行进路程LS，那么用户行进路线可能沿着AB线段往前或往后，也可能在拐点处发生拐弯，即从AB路径切换至CD路径。145所以在受到运动距离的限制下，聚类内只有一部分指纹段是可达的，而剩下的指纹段是不可达的。通过计算曼哈顿距离可以得出用户从当前位置出发可能到达这些指纹线段上的点的集合，聚类内的搜索算法伪代码如图2.2所示。图2.2聚类内搜索算法伪代码150Fig.2.2InnerClusterSearchAlgorithmPseudocode-5- 中国科技论文在线http://www.paper.edu.cn2.2聚类外搜索在当前位置可能发生空间转换时，即人从一个聚类穿越到另一个聚类，需要搜索除了当前所处聚类的匹配点之外，还需要搜索可能到达的其他聚类内的指纹点。155图2.3聚类外搜索Fig.2.3OuterClusterSearch如图2.3所示，假设用户的历史位置处于聚类C中，用户的运动路程为LS。以O点为2圆心，LS为半径画圆，理论可达区域覆盖了这两个聚类。由于历史位置O属于聚类C空间，2160C内的搜索空间利用上节的分析获得，而属于聚类C的搜索空间是曼哈顿距离不可达的，21可以通过求解圆与另一个聚类内指纹段交点获得。需要指出的是，由于两次定位的时间间隔较短，因此只有在具备发生空间转换条件时（用户位置靠近门等）才进行跨类搜索，否则只需要对聚类内的指纹进行搜索，聚类间搜索算法的伪代码如图2.4所示。165图2.4聚类间搜索算法伪代码Fig.2.4OuterClusterSearchAlgorithmPseudocode2.3基于最小集的定位过程根据2.1和2.2节的分析，我们可以得到当前位置需要匹配的指纹点最小集合。基于最170小集合的定位过程描述如下：①用户首先在定位点处停留足够的时间，在此过程中，用户的相对位置保持不变，系统收集该段时间内信号强度值，并利用均值滤波算法计算信号的平均值。②系统计算平均强度值与待匹配指纹集合的相似度，选取其中较相似的k个样本作为候选集来估计实时位置。175③定位人员移动到另外一个位置，在移动过程中利用计步器统计移动步数，系统重新计算候选集合并估计实时位置。-6- 中国科技论文在线http://www.paper.edu.cn④当定位结果的空间距离处在限定的阈值范围内，定位结果可以认为是相对准确的，系统进入到局部搜索阶段，接着重复这四个步骤。由于基于最小集的匹配算法需要根据历史位置来减小指纹空间的搜索范围，因而初始位180置的确定具有至关重要的作用。在定位系统启动时，系统对整个室内环境没有任何先验的空间认识，此时在步骤②需要对指纹库进行全局匹配来得到当前位置坐标。2.4动态热点筛选算法针对环境变化问题，本文提出一种热点筛选算法，它能够动态地选择Wi-Fi热点。由于定位系统很大程度依赖现场的环境信息，一旦环境发生变化，如某些AP暂时关闭使得定185位阶段与训练阶段的环境特征不一致，严重影响了定位的可靠性与准确性。Wi-Fi信号覆盖范围的局部性使得在固定位置可扫描到的热点总数较少，当信号强度较弱时，信号的失真率较高，导致相对较大的定位误差。为了减小弱信号的影响，本文根据Wi-Fi的信号强度大小对热点列表进行降序排列，从中选择前t(t≥3)个热点的信号作为指纹。该信号选择策略最大程度上保留了信号强度高的指纹信息，减小失真信号的影响。在定位阶190段，基于动态热点筛选算法的指纹匹配过程如下：①获取实时信号包含的热点集合S。②枚举集合S内的所有热点名称，若指纹样本中不存在此名称，则将缺省的强度值设为最小阈值。③计算实时信号与指纹样本的相似度，选取若干相似度较高的指纹点，据此估计实时195位置。3实验与系统验证[9]本文在Android平台上利用手机自带的传感器完成了室内定位系统原型的开发，并通过实验数据对定位系统进行测试和验证。采用的实验设备为HuaweiC8815，操作系统为Android4.1.2。测试地点选在南开大学计控学院5层的楼道和房间中进行，室内平面图如图2003.1所示，设备在走廊和两间房间内（536，537）共采集到153组信号强度样本作为指纹信息，覆盖区域面积大致为2.4m×65m，采样点间隔大致为42cm。实验选取了前10个强度最高的AP作为Wi-Fi信号采集样本，选取92.1MHz，97.2MHz，99.0MHz三个频段的FM信号。采样过程中共建立了14组指纹段。205图3.1实验环境平面图Fig.3.1FloorplanofEnvironment-7- 中国科技论文在线http://www.paper.edu.cn3.1指纹采集模块指纹向量由Wi-Fi信号强度和FM信号强度两部分构成，两种信号强度信息可以分别从手机内置的底层芯片中读取。图3.1中黑色三角所在位置的多个AP的信号强度分布如图3.2210所示。在黑色三角走廊的直线路径上，设备采集了空间上相邻的33个位置的三个频段FM信号，信号强度分布如图3.3所示。在Android系统中，Wi-Fi控制器可通过系统服务中的WIFI_SERVICE获得，包含无线信号强度，AP的MAC地址信息等。FM芯片提供了获取信号强度的硬件接口，用户通过编写驱动程序可以操纵整个FM芯片，读取到相关的硬件信息，但Android操作系统并没有为215用户组提供访问FM硬件的系统权限。本文通过反编译系统的收音机应用，修改源代码使得该系统应用能周期性调频和扫描，并将接收到的FM信号强度跨进程通信广播发送给接收程序。系统获取到WiFi、FM的信号强度信息之后，就可以建立完整的指纹信息，进而利用起点和终点坐标为指纹库建立段索引。220图3.2WiFi信号分布情况Fig.3.2WiFiSignalDistribution-8- 中国科技论文在线http://www.paper.edu.cn图3.3FM信号强度分布图225Fig.3.3FMSignalsDistribution3.2指纹定位精度测试本节对定位系统的精度进行实验分析。实验过程如下：用户手持移动设备在已经完成指纹标定的室内环境中采集Wi-Fi信号强度和FM信号强度，并通过点击地图的交互方式来标记实时室内坐标，信号强度和坐标构成一组测试样本。实验过程中共采集到167组样本。230采集结束后，本文分别利用Wi-Fi指纹和Wi-Fi与FM融合指纹对此样本集进行定位坐标的计算，并与样本的标定坐标进行比较，记录下两者坐标的差值。根据实验数据得出两者的累计误差函数分布，结果如图3.4所示，横坐标表示误差距离，纵坐标表示累积误差函数（CDF）。CDF表征了定位误差小于一定范围的概率分布，从总体上反映了定位系统的鲁棒性。从图中可以看出，在仅用Wi-Fi定位时，绝对定位误差最大在7m至8m左右，而加入FM信号235辅助定位后最大定位误差为5m，比Wi-Fi定位减小了2m。同时，融合指纹定位误差在82%的情况下小于4m，优于Wi-Fi指纹定位，定位精确度相比而言得到了提升。图3.4累积误差函数(CDF)Fig.3.4CDFComparison2403.3性能测试本文通过对比全局匹配算法和最小集匹配算法的所需匹配的指纹点数量来评估定位系统的实时效率。在实验过程中，系统分别采用全局匹配算法和基于指纹段索引的最小集匹配算法进行127次定位，并分别记录下两者所匹配集合中指纹点的数量。由于指纹库中的指纹点数量是固定的，因此全局匹配算法每次匹配的指纹点数量就是指纹库中指纹点的数量为245155，最小集匹配是动态搜索指纹集合进行匹配的，匹配指纹点数量对比如图3.5所示。-9- 中国科技论文在线http://www.paper.edu.cn图3.5最小集中指纹点数量Fig.3.5MinorSetFingerprintCount实验结果表明：基于最小集匹配算法的定位时间是动态变化的，最小集匹配算法相比于250全局匹配能够平均减少约82%的指纹匹配量，降低了指纹匹配时间，提高了系统的实时性。4总结本文提出了一种基于Wi-Fi与FM融合指纹和最小集匹配的室内定位方法，通过对室内环境的区域性特点进行分析，提出了一种利用视距平均采样原理建立指纹段索引的方法。在此基础上，系统根据空间连通性对指纹进行聚类划分，抽象地表征了现实环境中的路径可达255关系。在建立了指纹段索引的基础上，本文提出了最小集匹配算法。该算法在聚类内和聚类外采用不同的搜索策略，降低了指纹匹配过程的时间复杂度，提升了室内定位系统的实时性。最后，本文在Android平台上实现了定位系统的原型并通过实验对系统的有效性进行了验证，该系统在确保定位精度的前提下缩短了定位时间，提高了定位系统的实时性和可用性，适合在移动端进行部署实施。260[参考文献](References)[1]陈永光,李修和.基于信号强度的室内定位技术[J].电子学报,2004,32(9):1456-1458.[2]YoussefM,AgrawalaA.TheHoruslocationdeterminationsystem[J].WirelessNetworks,2008,14(3):357-374.[3]蔡敏敏.基于行人航位推算的室内定位技术综述[J].微型机与应用,2015(13):9-11.265[4]刘海.基于RSSI的室内信号衰减模型的研究[J].电脑开发与应用,2012,25(9):1-2.[5]Azizyan,Martin,Constandache,etal.SurroundSense:mobilephonelocalizationviaambiencefingerprinting[J].2009.[6]YoonS,LeeK,YunYC,etal.ACMI:FM-basedIndoorLocalizationviaAutonomousFingerprinting[J].IEEETransactionsonMobileComputing,2016,15(6):1-1.270[7]曾健平,邵艳洁.Android系统架构及应用程序开发研究[J].微计算机信息,2011(9):1-3.[8]MazuelasS,BahilloA,LorenzoRM,etal.RobustIndoorPositioningProvidedbyReal-TimeRSSIValuesinUnmodifiedWLANNetworks[J].IEEEJournalofSelectedTopicsinSignalProcessing,2009,3(5):821-831.[9]NakamuraM,MednieksZ,DorninL,etal.ProgrammingAndroid[M].O"ReillyMedia,2012.-10-'