Variance-based fingerprint distance adjustment
algorithm for indoor localization

Abstract: The multipath effect and movements of people in indoor environments lead to inaccurate localization. Through the test, calculation and analysis on the received signal strength indication (RSSI) and the variance of RSSI, we propose a novel variance-based fingerprint distance adjustment algorithm (VFDA).Based on the rule that variance decreases with the increase of RSSI mean, VFDA calculates RSSI variance with the mean value of received RSSIs. Then, we can get the correction weight. VFDA adjusts the fingerprint distances with the correction weight based on the variance of RSSI, which is used to correct the fingerprint distance. Besides, a threshold value is applied to VFDA to improve its performance further. VFDA and VFDA with the threshold value are applied in two kinds of real typical indoor environments deployed with several Wi-Fi access points. One is a quadrate lab room, and the other is a long and narrow corridor of a building.Experimental results and performance analysis show that in indoor environments, both VFDA and VFDA with the threshold have better positioning accuracy and environmental adaptability than the current typical positioning methods based on the k-nearest neighbor algorithm and the weighted k-nearest neighbor algorithm with similar computational costs.

With the development and widespread of mobile devices and technologies, the demand for location-based service is becoming higher in both indoor and outdoor environments. People are pursuing more and more efficient and accurate positioning technologies and novel solutions for location based services.

The global positioning system (GPS) has already been able to provide accurate positioning and navigation functions outdoors. However, it is not suitable for indoor localization. The current approaches of indoor localization are based on the infrared ray, the radio frequency identification (RFID), or the wireless fidelity (Wi-Fi), etc. Indoor localization has wide application prospect at complex and large public indoor environments, such as airports, hospitals, shopping malls and museums.

According to the difference of positioning principles,indoor positioning technologies can be roughly classified into three types: the positioning technologies based on hardware device, the positioning technologies based on the signal transmission model and the positioning technologies based on the received signal strength indication (RSSI)[1 – 4]. The positioning technologies based on hardware device usually need certain special auxiliary equipment,and calculate the physical location according to the information from the equipment, which easily leads to a cost increase and process complication. The positioning technologies based on the signal transmission model calculate the distance between the sender and the receiver by calculating the time of signal transmission. Thus, it can get the receiverrsquo;s physical location using a known emission source. Its limitation is that the signal does not always transmit along a straight line, because there are all kinds of obstacles between signal emission sources and receivers,which leads to complex reflection, refraction, diffraction and inaccurate positioning. The whole process of the positioning technologies based on RSSI can be divided into two phases: the training phase and the positioning phase.During the training phase, it is needed to collect RSSIs of access points (APs) with certain physical addresses at every reference point (RP), which will be stored in order to build a fingerprint database (FD). During the positioning phase, it is also needed to collect RSSIs to match information in the FD for the purpose of getting the optimum information and realizing the localization. The representative RSSI-based positioning technologies are based on the nearest neighbor (NN) algorithm or the k-nearest neighbor (KNN) algorithm, which are easily affected by the multipath effect [2,3]

To sum up, the performance of indoor localization technologies still has a huge improvement space, especially in positioning accuracy, environmental adaptability, hardware cost, and energy consumption.

In this paper, we are committed to develop a novel variance-based indoor fingerprint positioning method. The main contributions are summarized as follows

(i) We implement experiments in two typical positioning areas. We collect RSSIs, and analyze the relationship between the mean values and the variances. From the experimental results and the analysis, we find out that the mean values increase with the variance decreasing, which means that the mean values of RPs far from APs are smaller than the mean values of RPs close to APs.
(ii) From the further study on the relationship between mean values and variances for AP, we find out that this relationship is approximately linear. This relationship indicates that bigger signal values are more stable, and it can be used to decrease error of RSSIs.
(iii) Based on the above discoveries, we propose a novel variance-based fingerprint distance adjustment algorithm(VFDA). Different confidences are assigned to different
RPs according to the variance of current locations. Compared with the current typical positioning methods based on KNN and the weighted k-nearest neighbor (WKNN)algorithm, VFDA can greatly decrease positioning errors and improve the positioning performance.
(iv) It is possible that received signal strength values deviate from its real values due to few times of collecting RSSIs when positioning. We utilize a threshold value to avoid useless calculation of fingerprint distance, which can decrease the effect of occasional signal strength fluctuation, thus improving the positioning performance.

Positioning in indoor wireless environments is growing rapidly in import

全文共24267字，剩余内容已隐藏，支付完成后下载完整资料

基于方差的室内定位指纹距离调整算法

摘要：人们在室内环境中的多径效应和运动导致不准确的定位。通过对接收信号强度指示（RSSI）和RSSI方差的测试、计算和分析，我们提出一种新的基于方差的指纹距离调整算法（VFDA）。基于方差随着RSSI平均值的增加而减小的规则，VFDA使用接收到的RSSI的平均值计算RSSI方差。然后，我们可以得到校正权重。 VFDA基于RSSI的方差用校正权重来调整指纹距离，RSSI用于校正指纹距离。此外，阈值被应用于VFDA以进一步改善其性能。 VFDA和有阈值的VFDA应用于有多个Wi-Fi接入点的两种真实典型的室内环境。一个是方形实验室，另一个是建筑物的狭长走廊。实验结果和性能分析表明，在室内环境中，有阈值的VFDA和VFDA在相似计算成本下都比当前典型定位方法中基于k最近邻算法和加权k最近邻算法具有更好的定位精度和环境适应性。

随着移动设备和技术的发展和普及，对于基于位置的服务的需求在室内和室外环境中变得更高。人们正在追求越来越高效和精确的定位技术以及用于基于位置的服务的新颖解决方案。

全球定位系统（GPS）已经能够在户外提供精确的定位和导航功能。然而，它不适用于室内定位。室内定位的当前方法有基于红外线，射频识别（RFID）或无线保真（Wi-Fi）等。室内定位在复杂和大的公共室内环境（例如机场）具有广泛的应用前景，医院，商场和博物馆。

根据定位原理的不同，室内定位技术可大致分为三种类型：基于硬件设备的定位技术，基于信号传输模型的定位技术和基于接收信号强度指示（RSSI）的定位技术， [1 - 4]。基于硬件设备的定位技术通常需要一定的特殊辅助设备，并根据来自设备的信息计算物理位置，这很容易导致增加成本和过程复杂性。基于信号传输模型的定位技术通过计算信号传输的时间来计算发送器和接收器之间的距离。因此，它可以使用已知的发射源来获得接收器的物理位置。其限制是信号不总是沿着直线传输，因为在信号发射源和接收器之间存在各种障碍物，这导致复杂的反射，折射，衍射和不准确的定位。基于RSSI的定位技术的整个过程可以分为两个阶段：训练阶段和定位阶段。在训练阶段期间，需要在每个参考点处收集具有某些物理地址的接入点（AP）的RSSI （RP），其将被存储以构建指纹数据库（FD）。在定位阶段期间，还需要收集RSSI以匹配FD中的信息，以便获得最佳信息和实现定位。代表性的基于RSSI的定位技术基于最近邻（NN）算法或k-最近邻（KNN）算法，它们容易受到多径效应的影响[2,3]

综上所述，室内定位技术的性能还有很大的提高空间，特别是在定位精度，环境适应性，硬件成本和能耗方面。

在本文中，我们致力于开发一种新的基于方差的室内指纹定位方法。主要贡献总结如下

（i）我们在两个典型的定位领域实施实验。我们收集RSSI，并分析平均值和方差之间的关系。从实验结果和分析，我们发现平均值随方差的减小而增加，这意味着远离AP的RP的平均值小于接近AP的RP的平均值。

（ii）从关于AP的平均值和方差之间的关系的进一步研究，我们发现这种关系是近似线性的。该关系表明较大的信号值更稳定，并且它可以用于减小RSSI的误差。

（iii）基于上述发现，我们提出了一种基于方差的指纹距离调整算法（VFDA）。不同的置信度根据当前位置的方差被分配给不同的RP。与目前基于KNN和加权k最近邻（WKNN）算法的典型定位方法相比，VFDA可以大大降低定位误差，提高定位性能。

（iv）由于定位时收集RSSI的次数少，接收信号强度值可能偏离其实际值。我们利用阈值来避免指纹距离的无用计算，这可以减少偶尔的信号强度波动的影响，从而提高定位性能。在环境应用方面，在室内无线环境中的定位的重要性和商业利益正在迅速增长。

Milioris及其他人介绍了利用从AP收集的信号强度（SS）指纹的两种室内定位技术[1]。该方法通过考虑室内环境的离散的网格状形式并通过计算网格的每个单元处的概率分布签名，借助于多元高斯模型来采用所接收的SS测量的统计表示。在运行时，系统通过在它们相应的概率密度之间使用Kullbac-Leibler散度（KLD）来将未知位置处的签名与每个小区的签名进行比较。第二种方法应用压缩感测（CS）来执行基于稀疏性的准确室内定位，同时显着减少从具有有限功率，存储和处理能力的无线设备向中央服务器发送的信息量。

Ault 及其他人将NN和KNN引入定位[2]。如果k = 1，KNN将与NN相同。基于KNN的定位算法可以达到较高的定位精度。然而，在一些复杂的环境中，传输的信号可能被阻塞，并且多径效应使得远离AP的信号不稳定。信号的强烈波动可能导致在数据库中不正确地选择候选位置点，导致不准确的定位。

[3]和[4]研究了AP数量对室内定位性能的影响。 [3]中的实验结果表明AP的数量在测试阶段应该尽可能地等于或接近定位阶段中的AP的数量，AP的数量应该大于4，并且RP的距离应该至少为2米，否则定位结果可能不准确。 Koweerawong提出了一种从一组相邻的重新测量的RSSI指纹中估计特定位置的RSSI指纹的方法，称为“反馈”[5]。所提出的方法在截止区域中搜索新的反馈和一些必要的旧RSSI指纹，然后应用平面内插来计算特定位置的新的RSSI指纹。

参考文献[6]关注于基于ZigBee的无线传感器网络的RSSI的属性，其也可以用于实现室内定位系统。该研究在封闭的室内从基于ZigBee簇库框架的室内定位应用的实现收集一组测量样本。分析测量数据的统计参数。将结果与[6]中报道的无线局域网的RSSI的已知属性进行比较。在这项工作中获得的RSSI的属性的洞察可以用于改进使用基于ZigBee的无线传感器网络的本地化应用。Wu及其他人研究了RF未开发的信号特性，利用用户动作构建无线电平面图，然后设计了基于现成的Wi-Fi基础设施和手机的室内定位方法[7]。Lee及其他人提出了一种用于室内定位的基于RSSI的指纹数据库的映射系统[8]。映射系统已经实际开发用以实现快速和准确的无线电地图构造这两个主要目标。在[8]中采用扫描匹配，基于图的优化和采集的环境数据的概率中值滤波器提出了一种地图构建算法。

Li等人使用关键参考标签的概念来消除系统在实时定位阶段的冗余参考标签[9]。关键参考标签可以通过搜索在离线数据收集阶段建立的数据库来帮助获得所有参考标签的信号强度值。这种方法使用较少的RFID参考标签，而不会影响整体性能。 Ferdous等人调查了当前用于同时识别和本地化失能人员的技术和算法，并总结了基于摄像机，RFID和可穿戴设备的本地化方法[10]。在[11]中提出了一种基于到达时间（TOA）的定位算法，可以准确地计算从发射源到接收器的距离。 Tan指出，虽然TOA与信号不完全相关，但多径效应仍然导致不准确的定位[12]。也就是说，由于基站布局不良的不可避免的问题，基于TOA的定位算法可能容易导致非视线（NLOS）的问题。

王等人提出了一种基于RSSI的基础设施免费定位算法[13]，它基于Wi-Fi信号，能够降低数据库建设成本。通过选择热点，该算法可以有效地缓解来自附近区域的其他无线信号的干扰，并且还可以增强基于RSSI的匹配算法，从而提高定位精度。提出了一种用于定位平均误差的数学模型[14]，其中计算目标区域的数学期望的定位误差示出了接入点的数量，接入点的分布，网格间距和邻近数量的影响定位精度。

Fang等人提出使用RSSI的鲁棒参数来减少由多径效应引起的误差[15]，这可以在没有任何附加仪器的情况下将定位误差率从42％降低到29％。事实上，我们的灵感来自[15]进一步研究改进基于指纹的定位算法。 Lim等人提出从测量的RSSI中提取鲁棒的信号特征，从而可以有效地减轻多径效应[16]。在[17]中，流行的IEEE 802.11 WLAN与基于微机电系统（MEMS）的简化惯性传感器系统（RISS）一起使用，以提供基于Wi-Fi RSSI的建筑物内的轮式车辆的精确和平滑的定位系统。 Lin等人提供了在WiFi-Bluetooth共存环境中WiFi定位的初步结果[18]。引入RSSI作为应用于WiFi定位的观察。然后，[18]提出了WiFi定位的指纹识别方法和WiFi-Bluetooth共存环境中的干扰的基础。 Yeha等人提出了在无线异构网络中的自适应加权定位机制[19]，增强了GPS在建筑物中接收信号的能力和估计位置的精度。多径效应导致大的信号偏差，距离计算误差和定位误差。为了解决多径效应的问题，在文献[20]中提出了一种基于WKNN的定位方法，该方法为接收的每个RSSI分配权重，用于计算欧几里得距离作为指纹距离。当计算指纹距离时，较大的RSSI将被分配较大的权重。基于WKNN的定位的性能优于基于KNN的方法。

参考文献[21]介绍了RADAR，一种用于定位和跟踪建筑物内用户的基于RF的系统。 RADAR通过在被定位以在感兴趣的区域中提供重叠覆盖的多个基站处记录和处理信号强度信息来操作。它将经验测量与信号传播相结合

模型来确定用户的位置，从而启用位置感知服务和应用。

参考文献[22]介绍了Horus，WLAN定位系统的设计和实现。 Horus旨在实现两个目标：高精度和低计算成本。 Horus识别无线信道变化的不同原因并且解决它们以实现高精度。它使用位置聚类技术来减少算法的计算要求。轻量级Horus可以通过在客户端运行定位算法来支持大量用户。参考文献[22]介绍了Horus的不同组件，并评估其在两个测试台上的性能。实验结果表明，Horus平均误差小于0.6米，其计算成本优于其他WLAN定位系统。此外，Horus也可以应用于其他定位系统，以提高其准确性。

Wang 等人使用智能手机WiFi信号跟踪人的队列[23]，这需要最小的基础设施方法，因此利用单个监视器放置在服务区域附近与传输电话。该策略提取嵌入在信号轨迹中的独特特征以推断当人到达队列的头部并完成他/她的服务时的关键时间点，并且根据这些推断，可以导出人的等待和服务时间。

参考文献[24]表明，在移动环境中收集的无线数据为在诸如车辆自组织网络和移动社交网络的各种领域中构建新的应用提供了巨大的机会。将数据分散存储在无线设备中相对于集中式设备具有主要优点。为了促进对分布式数据存储中的无线数据的有效访问控制，在[24]中利用基于密码学的秘密共享方法提出了一个完全分散的密钥管理框架。秘密共享方法将密钥分割成多个共享并将它们分发到多个节点。然而，由于节点移动性，当它们需要用于密钥重构时，这些密钥份可能在邻域中不可用。为了应对这一挑战，郑等提出了传递预测（TRAP）协议[24]，其在一起旅行的设备之间分配关键共享，并且开发了利用嵌入在一起旅行的设备之间的相关关系的三个关键分发方案。密钥分发方案最大化成功密钥重构的机会并最小化通信开销。

3.1问题分析

首先，我们在真实的室内环境中实施几轮实验，以收集和分析由多径效应引起的参考位置处的信号波动的数据。在数据收集过程中，充分考虑对象移动和阻塞的因素，使测试更加现实可信。数据收集，测量和分析主要基于无线路由器作为AP和具有Wi-Fi功能的移动终端。移动终端可以自由移动，并连续扫描AP的RSSI值。使用部署的Wi-Fi接入点构建三个真实的室内环境。其中两个是方形房间，另一个是一个长而狭窄的走廊的建筑物。我们在两种情况下收集信号的数据，并分析信号的平均值和RSSI在任何RP的变化之间的关系。

Liu等人测试了由于人体对无线电信号的阻挡和反射，某些方向如何影响RSS读数，包括面向用户的方向，保持电话位置，在每个位置和每天的时间采集的样本数量[26]。 [26]中的实验结果表明，定位结果随这些因素的变化而变化。在我们的实验环境中，部署了5个AP，并构建了指纹数据库。 RP的距离设置为0.6 m和1 m，用于测试定位结果。每个RP在训练阶段收集300个RSSI值。在以下数据分析过程中，采用八个定位测试点来计算方差和平均值。在每个点，我们收集20组数据。我们还考虑一天的时间并在一天的不同时间进行实验，因为RSSI随时间变化而变化。

如图1所示。 1，在早晨和晚上，方差随着RSSI平均值的减小而增加。与AP接近的RP处的信号强度更强，信号波动更小。此外，在正方形房间中，远离AP的具有低RSSI值的位置点具有较大的RSSI波动，并且方差也较大。通过线性匹配，我们可以发现方差和平均值近似处于线性关系。

根据上述分析，我们可以得出结论，RSSI的方差随RSSI值和距离的差异而变化。如果移动终端远离AP，则在该点处测量的RSSI为低，具有大的方差并且变得不可靠。如果使用KNN来计算指纹距离，并且将基于所测量的平均值和方差给予不同的RSSI不同的置信度，则可以减小大方差的影响。这就是为什么在本文提出的VFDA，其确定基于RSSI方差和平均值之间的线性关系的调整权重，以便以高方差调整测量的RSSI。

3.2指纹距离

基于KNN的定位算法是基于RSSI。在测试阶段，AP的RSSI被收集并存储在指纹数据库中。在定位阶段，将计算存储在数据库中的RSSI和刚刚测量的RSSI之间的欧几里德距离，并将其用作指纹距离。然后选择指纹距离的最小k值及其对应的坐标，计算平均值作为定位结果[4]。从KNN的指纹距离定义，很容易发现收集的所有RSSI具有相同的配置。显然存在一个缺点，即如果由于多径效应，收集的RSSI远离其预期平均值，则最终指纹距离将更大，但是其他收集的值仍然正常。这种偶然的错误将使KNN无法选择最佳的k RP以实现精确的定位。由于测量的误差不能完全避免，因此我们需要减少误差测量的影响，并且依赖于这些RSSI值接近于在训练阶段并存储在指纹数据库中，使定位结果准确。当计算指纹距离时，有必要将高可信度分配给精确测量的RSSI值，并将低可信度分配给不准确的RSSI值。因此，可以有效地调整定位结果。我们有两个关键问题要处理：一是如何判断测量是否准确;另一个是如何获得最佳调整权重，以有效地减少指纹距离的误差。

3.4调整重量

调整权重的基

全文共6852字，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[144415]，资料为PDF文档或Word文档，PDF文档可免费转换为Word