基于室内地图环境信息的多楼层WiFi定位技术研究

黎海涛，齐 双



基于室内地图环境信息的多楼层WiFi定位技术研究

黎海涛，齐 双

(北京工业大学电子信息与控制工程 北京朝阳区 100124)

针对多楼层环境的室内定位需求，提出了一种基于地图环境先验信息的WiFi指纹定位方法。首先在离线阶段建立地图环境信息模型并对指纹进行仿射传播聚类，然后在线阶段采用RSSI阈值的楼层判别算法确定楼层，并结合地图信息模型和最大后验估计方法计算出终端位置。实验结果表明，相比于传统的指纹定位方法，室内定位技术不仅能提高定位精度，并且降低了在线阶段指纹匹配计算的复杂度。

仿射传播聚类; 指纹; 楼层判别; 室内定位; 地图信息

随着移动互联网的高速发展和智能移动终端的普及，移动用户对实时、准确的位置信息需求与日剧增。基于位置的服务(LBS)在民用、商用、军用、应急救援中具有广阔应用前景而受到人们普遍关注。目前国内外LBS应用大多采用GPS卫星定位，由于信号强度受到建筑物、墙壁等的影响而大大衰减，导致GPS接收机在高楼密集的城市或者室内运行时，定位精度降低甚至不能完成定位过程。

基于WiFi的室内定位技术利用移动终端从无线接入点(AP)接收到的信号来确定用户位置，能提高现有设备的利用率，低成本地实现便捷高效的定位服务，成为近年来室内定位技术研究的热点。在WIFi室内定位技术中，相比于基于信号到达时间(TOA)、信号到达角度(AOA)等方法，基于接收信号强度指示(RSSI)的指纹定位技术由于其对设备要求低、实现简单而被普遍采用。

由于WiFi信号传播的时变特性和环境因素的影响，使得终端在线接收RSSI的测量值与离线指纹库存在较大差异。此外，一般的WiFi指纹定位计算需要遍历所有参考点指纹，其在多楼层环境中应用时，定位系统中指纹数量增多，导致匹配计算的复杂度成倍增加。

研究表明，通过利用定位区域环境的先验信息可以降低信号传播过程中由于障碍物导致的信号非视距(NLOS)偏差等而提高定位精度[1-3]。文献[4]应用地图信息建立了用于室内定位的衰减系数(AF)模型，但此模型不适用于指纹定位方法，且缺少基于这种模型的位置估计算法的结果验证，因此在实际应用中其准确性和有效性无法保证。在楼层判别方面，文献[5]提出了联合加速度传感器和气压计计算高度从而判别楼层的方法，然而气压计需要定期校准且其测量值受环境影响较大，因此无法获得稳定的楼层判别准确率。

针对上述问题，本文提出基于地图环境先验信息的WiFi指纹定位方法，首先，建立地图环境信息的统计模型，并采用仿射传播聚类算法对指纹进行离线训练，以减小定位阶段的计算复杂度。进一步，为了弥补WiFi定位在高度上的误差导致楼层判别准确率低，提出了基于RSSI阈值的楼层判别算法，以提高多楼层定位的准确率。最后，利用基于地图信息模型的位置估计算法定位，以减少NLOS偏差、干扰、噪声等的影响，提高WiFi定位的精度和稳定性。

1 基于地图环境信息的WiFi室内定位系统

1.1 WiFi指纹室内定位

WiFi指纹定位包括离线阶段和在线阶段两个步骤，首先在离线阶段建立定位区域的指纹库，使得指纹库尽可能准确地表达每个参考点的信号特征；然后在线阶段通过测量用户终端当前位置的RSSI，利用合适的搜索或匹配算法确定终端位置。下面详细介绍各个阶段的操作步骤。

表1 指纹图

现有的指纹匹配计算方法可分为确定性匹配算法(如K-最近邻居算法，K-NN)和概率匹配算法(如最大后验估计MAP，或最小均方根误差MMSE)[6-7]。K-NN算法作为典型的确定性匹配算法被普遍使用。其基本原理是通过计算当前信号指纹与指纹库中各个参考点的指纹的欧式距离，选出与当前指纹距离最近的个参考点，取其坐标平均值作为终端位置。具体计算步骤如下。

1)计算当前位置指纹FP与指纹图中所有参考点指纹的欧式距离。设RSSI向量表示指纹FP中来自个AP的RSSI向量，与指纹图中参考点RP的RSSI向量之间的欧式距离为：

2) 对m进行升序排序，选出前个指纹并平均其平面位置坐标()，得到当前位置坐标。

(2)

1.2 室内地图环境建模

为了利用地图环境的先验信息进行WiFi定位，需要建立地图环境的数学模型，包括：1) 定位区域模型；2) AP覆盖区域模型；3) 终端与AP之间的距离模型。

1) 定位区域模型

图1 地图定位区域

2)AP覆盖区域模型

3) 终端与AP的距离模型

1.3 基于地图环境的WiFi定位

根据建立的室内地图环境模型，提出的多楼层WiFi室内定位系统如图2所示，具体施步骤如下。

图2 提出的WiFi定位系统

1) 离线阶段：完成定位区域的地图环境信息建模、指纹图的建立与指纹聚类。

①地图环境建模，具体步骤见1.2节。

②建立指纹图。

与一般WiFi指纹定位技术相同，包含指纹采集与指纹的平均。记录AP的位置坐标，将定位区域内的坐标与存为一组，其中坐标表示所在楼层。并把参考点测量到的第个AP的RSSI的平均值记为，为参考点标号。

③指纹聚类。

通过在指纹定位方法中加入指纹聚类，可以降低定位的计算复杂度，提高定位算法的实时性以及精度。文献[8]采用模糊c-均值聚类(FCM)算法对指纹聚类，但此种聚类方法在指纹点个数较大时，会导致计算量大大增加。文献[9]采用经典的k-均值(k-means)算法将指纹聚类，此方法需要通过随机方式选择初始类首，聚类结果依赖于初始聚类中类首的选择，容易陷入局部极值。仿射传播聚类[10]无需随机选择类首，且算法收敛速度快，更适于RSSI指纹图的预处理。

本文利用仿射传播聚类算法对所采集的指纹聚类，聚类结果如图3所示，聚类完成后将此189个指纹点划分为17个类。其中每个颜色的圆点属于一类，类首与类成员间通过直线连接。从图中可以看出，通过指纹聚类，可将物理位置相近的点划分在一个类中。在定位时，为避免指纹匹配到错误的类中，需选择少数个类作为位置计算的参考类。定位算法利用参考类的类首及其类成员的位置信息计算终端位置。通过指纹聚类将定位计算的指纹搜索区域缩小至少数类中，既降低了指纹匹配计算的复杂度，也提高了定位精度。

图3 指纹聚类结果

在计算复杂度方面，基于K-NN的全局匹配算法的计算复杂度为，其中为参考点个数，为每个参考点的信号强度维度。而基于仿射传播聚类的匹配算法的计算复杂度为，其中为类首个数，表示类成员个数。由于，故基于仿射传播聚类的匹配算法大大减少了匹配计算的复杂度。

2) 在线阶段：包含楼层判别和基于地图环境模型的位置估计两部分。

楼层判别中，利用RSSI在楼层间的衰落特征，并通过建立RSSI阈值与AP数量的关系，确定当前终端所在楼层，算法具体步骤见第2节。

采用MAP算法估计终端位置，结合地图建模所得的终端定位区域模型、AP覆盖区域模型以及终端与AP连接的距离模型，得到终端位置估计的概率密度函数[11]为：

2 楼层判别

研究表明，WiFi无线信号穿过建筑墙体时，由于通常楼层间墙壁常使用金属加强的混凝土，信号强度可能出现较大的衰减(15～20 dBm)[12]。此现象表明：1) 当物理距离相等时，来自同楼层的AP的RSSI强于其他楼层AP的RSSI；2) 根据三角定理，当不同AP的平面投影即坐标相同时，终端与同楼层的AP距离更短。综上两个条件，使得平面位置即坐标相同时，来自其他楼层的AP的RSSI明显的低于来自于本楼层AP的RSSI。利用楼层间RSSI的差异，提出的楼层判别算法实现步骤如下。

2) 设置RSSI阈值0，统计各个楼层的阈值内AP数量，并返回最大值对应的楼层F：

3 位置估计

3.1 模型参数估计

室内环境中，终端的接收信号功率可表示为[13]：

(9)

图4 模型参数估计方法

偏差均值模型为：

距离误差标准差模型为：

把式(10)～式(12)中得到的估计参数，即NLOS偏差均值及方差和距离误差方差代入式(6)，得到基于地图环境信息的位置估计概率密度函数为：

3.2 MAP位置估计

采用MAP位置估计算法得到终端位置为：

1) 利用第1节中指纹匹配算法K-NN得到当前楼层中与当前指纹最近的个类首及其所在位置区域；

2) 利用式(3)和贝叶斯准则，得到基于地图环境信息模型的终端位置估计为：

4 实验结果与分析

为了验证所提算法的定位效果，本文在Eclipse平台上利用JAVA语言开发了基于Android 4.0操作系统的定位客户端，以及基于Windows 7系统的定位服务器端。在每个参考点，客户端扫描AP信号并记录其RSSI与MAC地址，并与参考点位置坐标一起上传到服务器。定位服务器建立指纹图后对所有指纹进行聚类，并完成位置估计。

本次实验选取三层办公楼为实验场所，其中12个AP分布在3个楼层内，各个参考点分布在3个楼层的走廊内，两个相邻参考点之间的距离约为2 m，利用信号采集端对每个点进行30次间隔为1 s的采样。并在聚类算法中，将偏向设为相似度中值。

4.1 楼层判别准确率

为了研究基于RSSI阈值的楼层判别算法的效果，本文测试了不同AP分布情况下阈值0改变时的楼层判别准确率，如图5所示。

图5 不同AP分布情况下楼层判别正确率曲线

从图5中可以看到，当AP在楼层间分布均匀时，且阈值0取在-82dBm附近时，基于RSSI阈值的楼层判别方法的准确率能够达到99%；当AP在楼层间分布不均匀，且阈值0取在-80dBm附近时，算法依然能够达到97.2%的准确率。对于全局匹配算法，当AP在楼层间分布均匀时准确率为78.2%，而当AP在楼层间分布不均匀时准确率为67.8%。

由此可见，本文提出的楼层判别算法由于考虑了RSSI在楼层中的衰减特性，相比较于传统全局匹配算法，极大提高了楼层判断的准确率。需要说明的是，楼层间高度不同时AP与用户的距离会发生变化，所以对定位精度也会有影响。

4.2 定位精度

为了分析定位计算时参考类的个数对定位精度的影响，图6给出了参考类个数从1至17时算法的定位精度变化。从图中可以看出，参考类类个数取在4附近时定位精度较高，当过大时定位精度降低，并且其均方根误差与K-NN算法的均方根误差接近。从图中还可以看出，当参考类个数为1时，定位精度反而更低，这是由于当两个类相邻时边界位置的指纹可能被聚到错误的类中。因此，选择少数几个类作为WiFi指纹法位置计算的参考类，会提高定位精度。

图6 不同参考类数目对定位精度对比

为了分析本文基于地图环境信息模型的定位算法准确性，图7所示为不同算法定位误差的累计分布函数(CDF)曲线。从图7中可以看出，与传统的K-NN算法相比，基于仿射传播聚类的定位算法降低了整体的定位误差以及最大误差，并且在引入地图环境信息模型后，定位误差得到进一步降低。

图7 不同方法误差累计分布比较

为了分析所提基于地图环境信息模型的定位算法的定位精度，图8示出了不同定位算法的均方根误差(RMSE)。可以看到，本文算法的RMSE值低于其他K-NN等未利用地图环境信息方法的RMSE值。

图8 不同方法均方根误差RMSE对比

5 结束语

本文首先基于定位区域环境建立了地图信息模型，并利用仿射传播聚类算法对指纹进行离线训练，减少了指纹的时变特性影响和定位阶段匹配计算的复杂度。进一步，基于信号在楼层间的衰减特性，提出基于RSSI阈值的楼层判别算法。最后，提出基于地图信息模型的位置估计算法，以降低非视距偏差对定位效果的影响。实验结果表明，所提的多楼层WiFi定位方法能够有效提高定位精度和楼层判别的准确率，并减少了匹配算法计算复杂度。

[1] DAVIDSON P, COLLIN J, TAKALA J. Application of particle filters for indoor positioning using floor plans[C]// Ubiquitous Positioning Indoor Navigation and Location Based Service. Kirkkonummi, Finland: IEEE, 2010.

[2] 周瑞. 应用室内结构布局提高Wi-Fi定位精度和稳定性[J]. 电子科技大学学报, 2013, 42(2): 295-299.

ZHOU Rui. Improving of WiFi positioning precision and stability based on indoor structure and layout[J]. Journal of University of Electronic Science and Technology, 2013, 42(2): 295-299.

[3] SANGWOOK B, SEOKSEONG J, YU Chan-su, et al. Characteristics of a large-scale WiFi radiomap and their implications in indoor localization[C]//International Conference on Network of the Future. Paris, France: IEEE, 2013.

[4] LOTT M, FORKEL I. A multi-wall-and-floor model for indoor radio propagation[C]//International Conference on Vehicular Technology. Rhodes, Greece: IEEE, 2001.

[5] YUNKI K, SEUNGHWAN C, LEE J. Height estimation scheme of low-cost pedestrian dead-reckoning system using Kalman filter and walk condition estimation algorithm[C]// IEEE/ASME International Conference on Advanced Intelligent Mechatronics (AIM). Wollongong, Australia: IEEE, 2013.

[6] HUANG Yung-fa，ZHENG You-ting. Performance of an MMSE based indoor localization with wireless sensor networks[C]//International Conference on Networked Computing and Advanced Information Management (NCM). Gyeongju, South Korea: IEEE, 2010.

[7] HARA S, ANZAI D. Use of a simplified maximum likelihood function in a wlan-based location estimation[C]// IEEE Conference on Wireless Communications and Networking. Budapest, Hungary: IEEE, 2009.

[8] SUROSO D J, SOORAKSA P. Fingerprint-based technique for indoor localization in wireless sensor networks using fuzzy c-means clustering algorithm[C]//International Symposium on Intelligent Signal Processing and Communications Systems (ISPACS). Chiang Mai, Thailand: IEEE, 2011.

[9] THERDPHAPIYANAK J, PIROMSOPA K. An analysis of suitable parameters for efficiently applying K-means clustering to large TCP dump data set using Hadoop framework[C]//International Conference on Electrical Engineering, Computer, Telecommunications and Information Technology. Krabi, Thailand: IEEE, 2013.

[10] FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814): 972-977.

[11] PORRAT D, COX D C. UHF propagation in indoor hallways[C]//International Conference on Communications. Anchorage Alaska, USA: IEEE, 2003.

[12] WU C S, ZHENG Y, LIU Y H, et al. WILL: Wireless indoor localization without site survey[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(4): 64-72.

[13] MONTORSI F, MAZUELAS S, VITETTA G M, et al. On the performance limits of map-aware localization[J]. IEEE Transactions on Information Theory, 2013, 59(8): 5023- 5038.

编 辑 税 红

Indoor Map Information Based WiFi Positioning Technology for Multi-Floor Buildings

LI Hai-tao and QI Shuang

(College of Electronic Information and Control Engineering, Beijing University of Technology Chaoyang Beijing 100124)

In order to implement multi-floor buildings accurate location, the map information based indoor position scheme is proposed in this paper. Firstly, the map information model and affinity propagation method for fingerprints clustering are explored in offline phase. Then, the received signal strength indication (RSSI) threshold based floor identification method is put forward. Finally, the terminal positions are obtained by using the map information model and maximum posteriori position estimation method. Experimental results show that the proposed indoor position scheme can effectively enhance the location estimation accuracy and reduce the computation complexity for multi-floor buildings.

affinity propagation clustering; fingerprinting; floor-identification; indoor position; map information

TN92

A

10.3969/j.issn.1001-0548.2017.01.006

2014-11-26；

2016-07-07

电子系统综合技术重点实验室和航空科学基金联合资助项目(2013ZC15003)

黎海涛(1972-)，男，博士，副教授，主要从事通信、信号处理方面的研究.