基于智能终端的室内定位系统研究与实现

黄 璐，甘兴利，李雅宁

(1.哈尔滨工程大学 信息与通信工程学院，黑龙江 哈尔滨 150000； 2.卫星导航系统与装备技术国家重点实验室，河北 石家庄050081)

基于智能终端的室内定位系统研究与实现

黄 璐1，甘兴利2，李雅宁2

(1.哈尔滨工程大学 信息与通信工程学院，黑龙江 哈尔滨 150000； 2.卫星导航系统与装备技术国家重点实验室，河北 石家庄050081)

针对全球定位系统GPS不能提供令人满意的室内定位结果，提出一种基于接收信号强度的WLAN指纹匹配定位技术，采用一种创新式的指纹库构建方式，改进加权K近邻算法，同时利用指纹匹配的优点来校准行人航位推算的累积误差，提高定位精度，设计完成一套基于智能终端的绝对定位系统。实验结果表明，与传统无线定位算法相比较，改进的无线指纹匹配定位平均误差为1.66 m，无线修正航位推算平均定位误差为0.56 m，达到了室内定位精度的标准，验证了改进算法的有效性及导航系统的实效性。

室内定位；航位推算；无线指纹；智能终端

0 引言

根据近几年的统计，人们80%～90%的生活时间处于室内环境中，包括在商场、机场、图书馆和大学校园等场所，同时70%的移动电话和80%的蜂窝数据传输来自于室内[1]，这些引起了人们对基于位置服务(LBS)与位置感知的室内定位的浓厚兴趣，例如在正在建设中的建筑物中导航与规划、资产跟踪，还有一些老年人辅助生活(AAL)等。为了使这些应用能够被广泛地接收，室内定位需要一个准确可靠的位置估计方案。在室外使用GPS系统，然而在室内GPS信号较弱甚至接收不到，不能得到准确的定位结果，这导致在进入陌生的环境需要耗费很多时间和精力去熟悉环境，大大降低了效率，甚至在特殊环境中带来各种潜在的危险[2]。

由于室内环境多变复杂，存在多种干扰，造成传统的基于到达时间和到达角度的方式很难得到准确的定位结果，而且虽然无线网络广泛存在于室内环境中，但是鲁棒性强的室内定位系统需要离线采集到的指纹信息长期稳定不变，这对传统的指纹匹配算法来说是一个很大的挑战。针对上述问题，本文提出了一种改进的无线指纹定位算法，并设计了一种融合多种方式的定位系统。

1 行人航位推算

惯性导航系统[2](Inertial Navigation System，INS)一般分为2类：

① 基于双积分的方式[3]，根据牛顿力学的原理，通过对三轴加速度数据积分处理，得出相应的行进速度和行进距离，理论较为成熟，但在实际应用中，由于传感器精度受限，加上长时间定位累积误差较大没有得到推广；

② 航位推算法，已知初始位置，利用传感器数据获得行进方向与移动速度，推算下一步的位置，该方法是目前用于室内定位最常用的连续自主导航定位方式[4]。

近年来，惯性导航系统逐渐从稳定平台技术转向捷联技术，应用范围也由早先的车船拓展到航天器导航。随着微机电系统(Micro-Electro-Mechanical Systems，MEMS)[5]技术水平的提升，基于MEMS的捷联惯性导航系统逐渐成为室内定位技术的研究热点。行人航位推算原理图如图1所示。

图1 PDR算法原理

加速度计的测量值用来检测步数，陀螺仪、磁力计用来检测方向的，当PDR的步伐检测算法检测到行人行走一步时，步长和行进方向估算算法开始运行并估计出第K步的步Lk及行进方向θk行人的位置可以通过下式进行更新：

2 改进无线指纹定位算法修正航迹推算结果

2.1 传统加权K近邻算法

在室内定位技术探索与发展的过程中，基于无线指纹匹配技术是应用最广泛的，最成熟也是最易于推广使用的绝对定位方式。目前各大商场、机场和博物馆等大型场所均已覆盖无线网络，可以利用这些无线信号确定行人在环境中的位置，实现室内定位[6]。

指纹匹配技术又称场景分析法[7]，是基于匹配思想的一种定位方法，通过某一场景下实时接收到的场景信息与指纹数据库中的信息进行匹配，得到最优估计。在室内环境下，特别是大型建筑物，无线电波在传输的过程中，经过传播损耗、反射、折射、绕射以及多径传播[8]，每次接触到阻碍物就会有一部分能量被吸收，室内环境虽然复杂，但格局基本保持不变，设施几乎也不会有太大的移动，因此只要信源不作变化，在特定位置上形成的无线信号特征(信号数目、强度和相位)就会呈现出较高的特殊性。如果把这一特征和位置的坐标进行关联，则该信号特征可以表征该点位置，这是位置指纹定位技术成立的必要条件。

WLAN无线定位系统包括组网阶段、离线阶段和在线阶段[9]。组网阶段包括建立室内传播模型、AP的布置；离线阶段包括指纹采集及数据库预处理；在线阶段包括测试点信号的实时采集及预处理、定位算法匹配指纹数据库等。传统无线指纹匹配总体框图如图2所示。

图2 指纹库匹配示意

虽然无线指纹匹配技术已经在室内定位领域中得到广泛应用，但是定位精度还远远不足，因此本文提出一种改进的加权K近邻算法用于指纹库定位，同时提出一种新的指纹构建模式，使用指纹定位结果来修正PDR的累计误差。现实生活中几乎任何建筑中都存在Wi-Fi网络，这使得可以根据接收到的来自各种路由器的Wi-Fi信号强度值区分不同的位置，本文可以将接收到的信号构建指纹库用于室内定位，基于位置指纹库的定位系统通常包括离线采样和在线测试[6]这2个阶段。

离线采样阶段，利用了AP热点的独一无二的特性，每一个AP热点都有自己的标示符BSSID，同样在已知位置处接收到的信号强度值rssi虽然随着距离的增加会越来越弱，但是在10m之内，仍然可以获得到每一个AP热点广播的信号强度值，在采样点处记录来自m个不同AP的信号强度值RSSI，构建Wi-Fi指纹地图Radio Map，n个参考点的存储结构为：

(qi,ri)i=1,2,…,n，

式中，qi=(xi,yi)，qi为第i个位置的地理坐标；ri=(ri1,ri2,…,rim)，为位置i处接收到来自m个AP的信号强度值。

在线测量阶段，在待定位点处搜集并记录接收到的指纹信息，使用定位估计算法结合离线阶段构建的Radio Map解算出位置坐标作为Wi-Fi单点定位的结果。

本文利用改进的加权KNN算法进行Wi-Fi位置解算得到Wi-Fi定位结果。传统加权KNN算法在线测量阶段，首先通过计算n个参考点与定位点信号强度值的欧氏距离，然后递增排列距离d，取前k个值及其坐标计算定位点坐标，具体实现步骤如下：

① 在RadioMap中找到k个最近的参考点。

输入：n个参考点的信息(q1,r1),(q2,r2),…,(qn,rn)，未知点的接收RSSI为r。

输出：k个最近的参考点。

步骤：通过公式计算未知点rssi与n个参考点的rssi的欧氏距离，按照递增的顺序排列，返回前k个位置点(q1,r1),(q2,r2),…,(qk,rk)。

② 计算当前待定位点的坐标。

输入：最近邻的k个参考点的信息，包括位置坐标和该位置接收到的各个AP的信号强度值r。

输出：待定位点的坐标。

步骤：计算位置坐标

这里所有的权重均是非负的，

式中，d为信号强度值之间的欧氏距离；qj为第j个位置的坐标。

加权K近邻算法有一个调整参数k，这个k用来控制计算的位置坐标，当k=1时，算法就相当于在一个列表中查找一个位置坐标，当k值很大时，计算的位置坐标就会估算到在这些参考点附近。考虑到现实的一些影响因素[7]：

① 抖动的接收信号强度，导致在相同位置处信号强度值差异较大；

②AP可靠性，考虑到定位应该是长期性整体性的系统，所有AP应该是长期可利用的或者新加入AP会影响系统的稳定性。

③ 用户的身体朝向，人体中的水分会严重影响用户接收到的信号强度值[10]。

2.2 改进的加权K近邻算法

无线信号在空间中传输会受到建筑物、人和电磁场等造成各种干扰，这些干扰会造成获得的RSSI不准确，进而影响到定位结果[11]。所以，针对存在的种种问题提出了一系列解决方案。首先，在离线训练阶段采集数据时同时采集每个AP一段时间内的最大值、最小值及平均值。通过编写的数据采集软件，在采样点的1m2范围内走动，身体朝向不同的方向采集信息持续30～40s，将数据保存到手机SD存储卡上，同时将文件名设置成该采样点的位置坐标。在线阶段通过程序编写算法可以增量式的添加新的AP，以离线采样的格式存储，实时更新指纹信息库，增强定位系统的稳定性。其中对定位算法影响较大的是权值计算，传统的加权K近邻算法单一地使用信号强度值的欧氏距离作为权值，由于信号强度值的不稳定性导致错误的权重分配，比如某段时间内原本离的很近的参考位置点权重变的很低，原本很远的点权重很高，最终导致定位误差增大，所以为了解决这个问题，提出了一种优化权值的新方法，在某种程度上解决了路径损耗带来的误差，具体实现步骤如下：

① 离线采样阶段，为了解决在一个固定区域内搜索到很多个AP热点的强度值的无法区分的问题，使用BSSID和RSSI的最大最小值，及固定时间内的平均值采样，建立一个RadioMap选择建筑物内的一些位置点作为采样参考点，数据库的存储格式为：

(BSSIDrssi_maxrssi_minrssi_mean)。

② 在线测量阶段，在使用KNN算法计算出k个最近邻的参考点后，这里的权重增加匹配率m，分别判断这k个位置点的指纹库与待定位点指纹信息的匹配程度，通过程序编写计算k个位置点的匹配率，程序伪码如下：

1for(ArrayListtable:Table){

2 for(Datad:dtable){

3 for(Info i:table){

4 if(i.getBSSID().equals(d.getBSSID())){

5 if(d.getLevel()i.getLowestlevel()){

6 result[Table.indexOf(table)]++;

7 }

8 }

9 }

10 }

11r[Table.indexOf(table)]=((float)result[Table.indexOf(table)]/(float)table.size())*100;

12 }

匹配率高的分得更大的权重再结合rssi的欧式距离，最终提高定位精度，改进后的计算公式为：

图3 改进算法流程

3 航位推算结果的修正与路径约束

传统的Wi-Fi指纹库匹配算法修正PDR推算结果均是在计算机上仿真实现的，本文将利用改进的加权K近邻算法在智能终端上实时修正PDR推算结果，实现完整的定位跟踪系统，同时会在智能手机屏幕上实时显示用户轨迹及校准点位置，真正意义上实现了移动终端独立定位跟踪的技术[12]。具体实现步骤如下：

步骤1 通过JavaOpenStreetMap(JOSM)编辑器绘制出导航路径与实验路径图[13]，由于该软件绘制的路径是由经纬度表示的，所以需要将经纬度通过墨卡托投影转换成大地坐标，最后将大地坐标与室内地图XY坐标对应，存储为map3.osm，通过编写程序解析出路径信息并显示在手机屏幕上[14]；

步骤2 根据实际应用环境规划行走路径，通过实验分析标定参考点位置；

步骤3 在标定参考点处采集指纹信息同时对接收信号强度值进行预处理，预处理的主要目的是消除奇异值[15]、噪声等因素的影响，主要包括均值滤波和高斯滤波2种方法。

① 均值滤波

均值滤波是取同一参考点处多次采集数据的平均值作为该参考点信号强度的估计值，计算公式为：

② 高斯滤波

由于均值滤波是用采集数据的均值作为信号的估计值，所以引入了小概率信号误差，高斯滤波就是为了消除小概率信号的影响而引入的一种RSS预处理方法[16]。高斯滤波通过概率门限降低小概率信号误差，提高信号估计的准度。根据工程中经验值得出高概率发生区为概率大于0.6的区域，经高斯滤波后，移动终端RSS的取值范围应为[0.15σ+μ,3.09σ+μ]，其中σ和μ分别为测得数据的标准差和均值。最后取出高概率范围内的RSS值再计算其平均值，即可得到最终的RSS值。

步骤4 通过使用改进的算法得到无线定位结果作为PDR推算的初始位置；

步骤5 使用者手持智能终端沿着规划路径以正常速度行走，终端屏幕显示路径轨迹。

步骤6 定位结果分析，计算定位误差。

4 实验结果与分析

实验环境选择卫星导航系统与装备技术国家重点实验室，环境大小为20m×82m。在实验环境中布置5个AP热点，在试验路径周围每1m设置一个参考点，并在参考点处采集指纹信息构建指纹数据库，在以参考点为中心，1×1邻域内行走，每个参考点采集2～3min。每隔2m设置一个测试点，实验数据采集完成后，将指纹信息与位置坐标一一对应，文件名为位置坐标，内容包括物理地址和信号强度值的最大、最小以及平均值。存储格式如图4所示。

图4 指纹库存储格式

实验对比分析传统的无线定位算法，包括传统K近邻算法、传统加权K近邻算法和本文提出的改进WKNN定位算法，使用绘图工具将采集到的真实数据处理分析得到如图5和图6所示的定位误差结果。

图6 无线定位算法误差累计分布函数

从图5和图6可以看出，传统的KNN算法由于权值分配过程中存在信号强度值不稳定导致定位误差波动较大，传统WKNN算法在K=3时的参考点的指纹信息分配权重定位误差相对稳定，当信号强度值波动较大时权重分配就会不准确，造成定位误差仍旧很大，本文提出的新算法整体误差稳定，平均误差也有了一定的提高，结果如表1所示，对3种不同无线定位手段进行对比实验，表1中的对比数据为了保证数据的可靠性和普遍性，均是经过多次真实实验收集到的数据。实验验证了算法的有效性。

表1 不同定位方式结果比较

从表1中可以看出，传统的无线定位算法与本文提出的定位算法在定位精度上有显著差别，传统KNN与WKNN算法，误差波动较大，定位结果不稳定，平均定位误差分别为5.90和2.35，5 m内的定位精度分别达到52.9%和90.7%。改进后的加权KNN算法平均定位误差为1.66 m，5 m内的定位精度达到98.7%，在一些特定场合完全符合室内定位的标准，但是最大误差与最小误差差距仍在7 m以上，定位不稳定，所以本文通过改进的定位算法与PDR算法相融合，使用绝对位置来修正PDR的累计误差，建立了一个稳定的定位系统，同时提出一种路径约束方式约束PDR的定位系统。实验通过使用者手持智能终端在设定好的路径起点走到终点，实验分为2种对比模式：单独PDR和无线指纹算法单点修正PDR，实验结果如图7、图8、图9和图10所示。

图7 传统PDR定位跟踪真实轨迹

图8 改进的加权KNN修正PDR真实轨迹

图9 2种定位方式误差对比

图10 2种方式误差累计误差分布函数

由图7中可以看出，实验人员手持智能终端在实验环境中按照规划好的路径行走，传统PDR推算的真实路径图。图7中弯曲轨迹是PDR推算轨迹，直线轨迹是规划好的真实路径，可以清晰地看到在开始阶段PDR推算较为准确，在第一个转弯处由于方向的检测存在误差导致路径开始偏移，继续行走累计误差越来越大。由图8中可以看出，在PDR行走的偏差较大处通过改进的无线定位手段进行修正，将位置校准到真实路径上，整体轨迹较为准确，基本达到室内定位标准。由图9和图10可以看出，传统PDR定位算法在定位初期较稳定且误差较小，随着时间的增长误差开始发散，最大误差为4.12 m，平均误差为1.44 m，在某些空间较小的室内环境下，PDR跟踪定位可以单独使用。经过改进的无线单点定位算法修正PDR的结果最大定位误差在1.52 m，平均定位误差在0.56 m，消除了累计误差。

仿真实验是在处理器型号为Intel-i5-4200H，主频为2.80 GHz，内存为4 G，操作系统为Windows 8.1中文版的PC机上使用Matlab2010以及Eclipse两种软件实现，真实实验是在搭载Android 4.0操作系统的三星Note2、红米2A加强版和华为荣耀4智能手机上实现。

5 结束语

通过对传统PDR存在的不足之处进行改进，包括步数估计方面采用自适应阈值校正的方式，采用方向补偿方式优化了设备方向的检测。针对传统无线定位手段采用各种滤波方式融合PDR数据难以在智能手机上单独实现的问题，提出了一种基于智能终端的改进的加权K近邻无线定位算法单点修正传统PDR累计误差的定位方式，通过实验得到平均定位精度达到0.56 m，基本满足室内定位的精度要求。

结合本文提出的室内定位方式，未来将会设计一种室内外无缝切换的高精度定位系统，比如在一些大型场所可以用过智能手机开启定位系统，室外使用GPS/BD，室内使用无线定位结合PDR及路径约束方式进行定位与导航。

[1] TANCHAROEND,AIZAWA K.Wearable Video Retrieval and Navigation System Using GPS Data[J].IEEE Int.Can Computer and Information Technology,2010,23(10):62-67.

[3] RAOMGD,ROENG T.Using the ADXL202 in Pedometer and Personal Navigation Applications[J].Application Note AN602,Analog Devices,2013,6(2):23-24,56.

[4] BAHLP,PADMANABHAN V N.RADAR:An In-building RF-based User Location and Tracking System[J].Microsoft Research,2000,4(1):10-16.

[5] MAJ,LI X,TAO X,et al.Cluster Filtered KNN:a WLAN-based Indoor Positioning Scheme[J].International Symposium on a World of Wireless,Mobile and Multimedia Networks,2008(8):1-8.

[6] YOUSSEFM A,AGRAWALA A,SHANKAR A U.WLAN Location Determination via Clustering and Probability Distributions[J].IEEE International Conference on Pervasive Computing and Communications,2003(4):143-150.

[7] SAHAS,CHAUDHURI K,SANGHI D,et al.Location Determination of a Mobile Device Using IEEE 802.11b Access Point Signals[C]∥In Proc.IEEE WCNC,2003(3):66-67.

[8] PRASITHSANGAREEP,KRISHNAMURTHY P,CHRYSANTHIS P K.On Indoor Position Location with Wireless LANs[C]∥ In Proc.IEEE PIMRC,2002(9):78.

[9] JIM′ENEZA,SECO F,PRIETO C,et al.A Comparison of Pedestrian Dead-reckoning Algorithms Using a Low-Cost MEMS IMU[C]∥In Intelligent Signal Processing,IEEE International Symposium on,2009:37-42.

[10] AZIZYANM,CONSTANDACHE L,CHOUDHURY R R.SurroundSense:Mobile Phone Localization via Ambience Finger Printing[J].In Proceedings of 15th ACM Mobile Com.,2009(6):261-272.

[11] RALLAPALLIS,QIU L,ZHANG Y,et al.Exploiting Temporal Stability and Low-rank Structure for Localization in Mobile Networks[J].In Proceedings of 16th ACM MOBICOM,2010(10):161-172.

[12] STEINHOFFU,SCHIELE B.Dead Reckoning from the Pocket[C]∥ In Proceedings of 8th IEEE PerCom,2010(5):162-170.

[13] GRAUD,CALDAS C H,HAAS C T,et al.Assessing the Impact of Materials Tracking Technologies on Construction Craft Productivity[J].Autom.Constr.2009,18(7):903-911.

[14] RAZAVI S N,HAAS C T.Multisensor Data Fusion for On-site Materials Tracking in Construction[J].Autom.Constr.2010,19(8):1 037-1 046.

[15] RAZAVI S N,HAAS C T.Reliability-based Hybrid Data Fusion Method for Adaptive Location Estimation in Construction[J].Comput.Civ.Eng.2012,26(1):1-10.

[16] DING L Y,ZHOU C,DENG Q X,et al.Real-time Safety Early Warning System for Cross Passage Construction in Yangtze Riverbed Metro Tunnel Based on the Internet of Things[J].Autom.Constr.2013,3(6):25-37.

Research and Implementation of Indoor Positioning System Based on Intelligent Terminal

HUANG Lu1,GAN Xing-li2,LI Ya-ning2

(1.HarbinEngineeringUniversity,InformationandCommunicationEngineeringInstitute,HarbinHeilongjiang150000,China; 2.TheStateKeyLaboratoryofSatelliteNavigationSystemandEquipmentTechnology,ShijiazhuangHebei050081,China)

Considering that it is unable to provide satisfactory indoor positioning results by using Global Positioning System(GPS),a WLAN fingerprinting positioning technology based on

signal strength is proposed.The weighted K nearest neighbor algorithm is improved;an innovative fingerprint structuring method is proposed,and the positioning accuracy is increased.A set of absolute positioning system based on smart phones is designed.The experimental results show that as compared with the traditional wireless positioning algorithm,the average error of the improved wireless single point positioning method is 1.66 m,the average error of wireless positioning single point correction navigation calculation is 0.56 m,which reaches the standard of indoor positioning accuracy,and verifies the effectiveness of the improved algorithm and the navigation system.

indoor positioning;dead-reckoning;wireless fingerprint;intelligent terminal

10.3969/j.issn.1003-3106.2017.09.09

黄璐,甘兴利,李雅宁.基于智能终端的室内定位系统研究与实现[J].无线电工程,2017,47(9):44-50.[HUANG Lu,GAN Xingli,LI Yaning.Research and Implementation of Indoor Positioning System Based on Intelligent Terminal[J].Radio Engineering,2017,47(9):44-50.]

TP311.52

A

1003-3106(2017)09-0044-07

2016-12-03

“十三五”国家重点研发计划基金资助项目(SQ2016YFGX040104)。

黄 璐 男，(1991—)，硕士研究生。主要研究方向：室内定位与导航。

甘兴利 男，(1981—)，高级工程师。主要研究方向：卫星导航。