基于线性内插法改进的室内定位算法

张梦丹，卢光跃，王宏刚，刘继明

（西安邮电大学，陕西 西安710121）

基于线性内插法改进的室内定位算法

张梦丹，卢光跃，王宏刚，刘继明

（西安邮电大学，陕西 西安710121）

针对室内位置指纹定位技术存在的离线阶段工作量大、定位精度有限、顽健性较差的缺点，提出了一种基于线性内插法改进的指纹定位匹配算法。与传统位置指纹定位技术相比，该算法不仅降低了整体工作量，而且降低了多径效应造成的不利影响。最后搭建实验场景对该算法定位性能进行测试。实验数据显示，该算法与WKNN法相比，平均定位精度大约提高了34.25%，绝大部分待测点的定位误差在0.4 m以内，验证了所提算法在定位精度、顽健性和适应环境变化方面的优势。

室内定位；位置指纹；WKNN；PCA；线性内插法

1 引言

随着无线技术、移动计算机和互联网应用的不断增长，人们对位置敏感系统及其服务的需求越来越高。在室外，GPS系统被广泛用于提供定位信息与服务，其室外定位精度能够达到美国E911标准。但在室内复杂环境中，由于室内物品的干扰、非视距等因素，一般不采用GPS系统进行定位。现在常用的室内定位技术有Wi-Fi技术、蓝牙技术[1]、红外线室内定位技术、超声波定位技术等。这些技术有的成本较高、有的室内定位精度低，均不利于室内定位的广泛推广。而融入了蓝牙4．0的新技术，不仅增强了信号的稳定性及覆盖范围，而且降低了功耗，因此迅速成为室内定位领域的优选技术。

根据定位过程中是否需要实际测量节点间距离，室内定位方式可分为两类：即基于距离[2]和距离无关。目前，基于测距的定位技术主要有到达角度（angle of arrival，AOA）法、到达时间（time of arrival，TOA）法、到达时间差（time difference of arrival，TDOA）法等，而基于非测距定位主要是基于信号强度测量法定位[4]。基于信号强度测量法定位可分为位置指纹定位法和信号传输损耗法[5]，而现有利用位置指纹进行匹配的算法主要包括 WKNN（weighted K-nearest neighbor，加权K邻近）算法、神经网络算法、概率算法和支持向量机（SVM）算法等。WKNN算法遍历指纹点的接收信号强度指示（received signal strength indication，RSSI），找出最接近测试点RSSI的一个或多个指纹点，然后将这些指纹点位置的加权值作为测试点的估计位置。WKNN算法容易实现，但定位精度不高，且在实际的室内环境中，无线信号在传播过程中会受到多径效应的影响，因而在同一个位置上的接入点（access point，AP）的RSSI往往表现出复杂的时变特性，进而进一步降低了室内定位的精度。为此，本文应用主成分分析（principal component analysis，PCA）变换提取原始RSSI信号中的主要定位特征，以减少多径效应对定位的影响。另外，针对定位离线阶段工作量大的问题，本文应用线性插值法来重构离线指纹库，并对测试点进行定位。实验证明，所提算法具有较高的定位精度和较好的实时性，满足了室内定位的基本需求。

2 基于RSSI的位置指纹定位算法

2.1 指纹算法描述

位置指纹定位算法包括两个阶段：离线阶段和在线阶段。离线阶段的工作是在待定位区域内按照一定的间隔距离确定若干参考点，形成一个采样网格图，并将每个节点测得的信号强度值及其位置信息按照＜指纹，地点＞的格式存储在数据库中；在线阶段，通过移动终端对各个AP发出的信号强度进行实时采集，通过特定的匹配算法实现对移动设备位置的估计[7,8]。

2.2WKNN算法

WKNN法属于典型的确定性定位算法[9]。其定位思路为：首先构建离线指纹库，Fi=(fi1,fi2,fi3,…,fin)，fin表示在第i个参考点处接收到第n个AP的指纹信息，其次，移动终端用户获取在待测点位置处各个AP的信号强度值，记为向量 Rt=(r1,r2,r3,…,rn)，rn为移动设备接收到的第 n个 AP的信号强度，最后计算此向量与指纹库中向量的欧氏距离，为：

选择距离最小的前K个采样点，并按照每个参考点对待测点的贡献程度计算每个参考点的权值 wj[10]，如式（3）所示，定位点的估计位置是这K个点的加权质心。其中，K值可根据定位环境选取[11]。

其中，Dj表示第j个参考点与待测点的欧氏距离。由式（3）知，欧氏距离Dj越大，wj越小；相反欧氏距离Dj越小，wj越大。

3 改进的定位估计匹配算法

WKNN算法虽然能基本满足人们对位置的需求，但是仍存在一些问题：增加参考标签数目可以提高室内定位精度，但会增加额外的成本；在密集环境下，多径效应会给定位结果带来一定的影响。因此提出了一种基于子区域插值改进的指纹定位匹配算法。

3.1 主成分分析法

主成分分析法的基本原理是：根据K-L变换在测试空间中找到一组能最大限度表示出原始数据信息的正交向量，把原始数据从原来的空间投影到这组正交向量组成的空间上，其投影系数便构成新的特征矢量，从而完成对维数的压缩。

设T={(S1,L1),(S2,L2),…,(Sp,Lp),}，Sp∈Rm为参考点处的信号集。Sp为在位置p处接收到的AP的信号强度，Lp为位置p的二维位置坐标。假设 X=[S1,S2,…,Sp]T，则PCA变换为：Z=AT(X-E[X])，A=[u1,u2,…,uk]，A中的uk是由X的协方差矩阵CX=E{(X-X)(X-X)T}的特征值λk对应的特征向量按从大到小的顺序排列组成。经过PCA变换，Z中各个矢量间的相似性基本消除，其中，Z中前m个主成分占据了X的绝大部分信息，Z′=[S1′,S2′,…,Sp′]T，因m＜d，因此完成了对指纹数据维数的压缩。

3.2 线性内插法

线性内插法的基本思想是：在待定位区域内按照一定的间隔距离确定若干采样点，形成一个采样网格图，在网格图内进一步划分，将每个由4个参考标签覆盖的网格分为N×N个大小相同的虚拟网格单元，由于参考标签坐标已知，虚拟参考标签易得到，同时采用线性插值方法来获得虚拟参考标签的信号强度值。下面将详细地对该算法进行介绍。线性内插法原理如图1所示。

图1 线性内插法原理

如图1所示，其中，白色圆圈代表采样点，4个组成采样网格图，然后把网格划分成N×N个小网格，灰色圆圈代表划分好的虚拟参考点。根据实际参考点位置坐标可求得虚拟参考点的坐标。最后采用线性插值可以得到虚拟参考点处的接收信号强度值。

水平方向上的虚拟参考点接收信号强度值可以由式（4）求出：

垂直方向上的虚拟参考点接收信号强度值可以由式（5）求出：

其中，Sk(Ti,j)表示在第k个参考点坐标位置为(i,j)处读到的接收信号强度值，a=「i/n」，b=「j/n」，「」表示向下取整，0≤p=i%n≤n-1，0≤q=j%n≤n-1，n=N-1。

3.3 N值的选择

实际上，参考点处的RSSI值与距离的关系非线性，室内环境信道的大尺度衰落服从对数正态分布的特性，选用对数距离路径损耗模型获取虚拟参考点的RSSI值。“距离—损耗”计算式为：

其中，d0是参考距离；dij是第i个参考点到第 j个AP的实际距离；P0是终端和 AP的距离为 d0时接收到的RSSI；P是距离为 dij时接收到的 RSSI；n是路径损耗指数；ζ为遮蔽因子，是均值为0、标准差为σ的正态随机变量。

由此，可以得出：必然存在一个使定位误差达到最小的N值，下面将进一步进行理论论证。

以图1参考点为例进行线性插值，假设该网格的4个参考点为T1、T2、T3和T4，假设Rik为第i个参考点（包括实际参考点和虚拟参考点）处接收到的第k（k=1,2,3,4,5,6）个AP的RSSI值，Epk为相邻参考点RSSI的差值，p=0,1,2,…,N-1，则：为在参考点T1处接收到的节点APk的RSSI，R2k为在参考点T2处接收到的节点APk的RSSI，R0k为在位置d0处接收到的节点AP1的RSSI，参考点T1的坐标为(x1,y1)，T2的坐标为(x2,y1)，APk的坐标为(ak,bk)。

对Epk求N-1的导数，并令导数为零，可得：

其中

假设k=1，此时(ak,bk)=(a1,b1)=(0,0)，若p取1，分别遍历(x1,y1)和(x2,y1)，并将各个参数的值代入式（9）中，最终得到N值变化如图2所示。实验面积为14 m×10 m，参考点数为7×5，可见，理论上当N为5～6时，用线性内插法的误差达到最小值。

图2 N值变化折线

3.4 定位步骤

对于室内位置指纹定位算法来说，离线阶段数据库的构建以及室内环境存在多径效应的特点都对定位产生严重的影响。下面将详细介绍改进的定位估计匹配算法的步骤。对应的匹配算法流程如图3所示。

图3 基于线性内插和PCA改进的指纹定位匹配算法流程

步骤1 选取试验场景，搭建测试环境，并多次采集每个参考点处的RSSI值求平均，构建离线指纹数据库。

步骤2 选取N值，确定虚拟参考点的划分结构，利用第3.2节介绍的线性内插法求解虚拟参考点的位置坐标和各个虚拟参考节点的RSSI值，重新构建离线指纹数据库。

步骤3 对构建的离线指纹数据库进行主成分分析，去掉多径效应对信号造成的干扰，构建特征数据库。

步骤4 选取待测点，并用移动终端读取待测点的RSSI值，对待测点测量的数据进行PCA变换，提取特征，假设变换后的向量为Z′=[S1′,S2′,…,Sp′]T。

步骤5 选取指纹定位算法WKNN的K值，这里令K=4，然后计算Z′与特征数据库中每个参考点的欧氏距离，选取欧氏距离最小的前4个参考点，并分别计算对应的加权值wj。

步骤6 按照式（3）估算移动端的位置，实现对移动端的实时定位。

4 实验性能比较与结果分析

4.1 测试平台

本实验软件平台是基于Andriod开发的手机应用软件BLE Scanner，用于实现离线及在线阶段的RSSI数据采集。硬件平台采用的是iPhone 5和苹果公司的iBeacon产品。实验环境位于西安邮电大学长安区3号实验楼523房间。实验软件、硬件平台和实验场地实景如图4所示。实验环境参数选取见表1。

图4 软件、硬件平台和实验场地实景

表1 实验环境参数选取

4.2 性能比较与仿真分析

由第2.2节的介绍可知，当测试环境和K值一定的情况下，影响WKNN算法定位结果的主要因素是：离线阶段的参考点的数量太少，则造成定位精度下降；数量太大，耗时耗力，造成定位成本的增加。因此要根据具体的实验场景，合理地选择参考点的数量。对这种算法的参考点的数量选取不同的值进行MATLAB仿真，参考点的数量的选取及定位误差见表2，仿真结果如图5所示。由仿真结果可知，定位误差随着参考点数量的增加而减少。

表2 WKNN参考点数量的选取及定位误差

同理，由第3.2节对线性内插法的介绍可知，为了在不增加定位成本的情况下提高定位精度，在WKNN算法的基础上提出了线性内插法。当测试环境、K值以及参考点数量一定的情况下，影响基于线性内插法改进的WKNN算法定位结果的因素主要是N值的选取：N值太小，造成定位精度提高得不明显；N值太大，由于位置和接收信号强度的非线性关系造成定位精度降低。因此要根据具体的实验场景，合理地选择N值的大小。对这种改进算法的参考点数量取35个，对N选取不同的值进行MATLAB仿真，N的选取及定位误差分别见表3，仿真如图6所示。由仿真结果可知，定位误差并不是随着N的增大而增大，而是有一个最佳值，因此要根据试验场景，合理地选择N的大小，从而达到最佳定位效果。

图5 WKNN法不同参考点数量仿真结果对比

表3 基于线性内插法的WKNN不同N值及定位误差

图6 基于线性内插法的WKNN不同N值仿真结果对比

最后，根据第3.1节对PCA的介绍可知，为了减少多径效应对定位造成的影响，在基于线性内插法改进的WKNN算法的基础上增加了PCA，先对离线指纹库数据进行降维，去除干扰，再进行定位，此时，选择K=5，K=4，参考点的数目为35个，待测点数量为20个，并用MATLAB对比WKNN法和基于线性内插法改进的WKNN法，仿真结果如图7所示，各个算法的定位误差见表4。由仿真结果可知，PCA能进一步提高定位的精确度，精度提高了4%左右。

表4 不同算法相同条件情况下的定位误差

图7 不同算法相同条件下定位误差累计分布仿真对比

另外，对于WKNN法、基于线性内插法改进的WKNN法以及基于线性内插和PCA改进的WKNN法分别进行20次测试，定位误差对比如图8所示。由图8可知，基于线性内插和PCA的WKNN匹配算法的定位误差明显比WKNN法的定位误差低。

由上述对算法的仿真结果可知，基于线性内插和PCA改进的WKNN法能在减少定位成本的同时提高定位精度，该算法与WKNN法相比，平均定位精度大约提高了34.25%，但是，由于离线指纹库是根据线性内插法构建，计算势必带来定位时间的消耗，进而影响定位效率，用MATLAB中的tic和toc语句分别对WKNN法、基于线性内插法改进的WKNN法以及基于线性内插和PCA改进的WKNN法的效率进行仿真，仿真时间见表5，结果显示，该算法虽然以牺牲时间为代价提高定位精度，但消耗的时间处于可接受的范围内，说明在满足人们对定位的要求的同时提高了定位精度。

图8 不同算法相同条件下各个待测点处定位误差对比

表5 不同算法相同条件情况下的仿真时间

5 结束语

本文针对增加参考点耗时耗力以及多径干扰问题，在位置指纹定位算法的基础上提出一种基于线性内插和PCA改进的WKNN定位方法。该算法将划分好的网格点进行进一步的划分，利用线性内插法重新构建离线指纹数据库，并引入主成分分析法，减少多径效应对定位造成的影响。所提算法使用匹配定位估计，在减少定位成本的同时提高了定位精度。由仿真分析可知，所提算法的最大定位误差为0.391 9 m，最小定位误差为0.026 6 m，对于长14 m、宽10 m的定位环境而言，最大误差处于可接受范围内。

[1]陈锡剑,程良伦.基于RSSI的功率匹配定位算法的研究与实现[J].传感技术学报,2013,26(5):710-714. CHEN X J,CHENG L L.Research and implementation of power matching algorithm based on RSSI[J].Chinese Journal of Sensors and Actuators,2013,26(5):710-714.

[2]LU Y H,LAI C F.Path loss exponent estimation for indoor wireless sensor positioning[J].KSII Transactions on Internet and Information Systems,2010,4(3):243-256.

[3]PATWARI N,HERO A O,PERKINS M.Relative location estimation in wireless sensor networks[J].IEEE Transactions on Signal Processing,2003,51(8):2137-2147.

[4]叶蔚.室内无线定位的研究[D].广州:华南理工大学,2010. YE W.Study on indoor wireless location[D].Guangzhou:South China University of Technology,2010.

[5]杨东勇,顾东袁,傅晓婕.一种基于RSSI相似度的室内定位算法[J].传感技术学报,2009,22(2):264-268. YANG D Y,GU D Y,FU X J.An indoor location algorithm based on RSSI-similarity degree[J].Chinese Journal of Sensors and Actuators,2009,22(2):264-268.

[6]刘鹏,卢潭城,高翔.基于射频识别的室内定位技术综述[J].太赫兹科学与电子信息学报,2014(2):195-201. LIU P,LU T C,GAO X.A survey of indoor location technology based on radio frequency identification[J].Terahertz Science and Electronic Information,2014(2):195-201.

[7]梁莹.INS/地磁匹配组合导航系统技术研究 [D].哈尔滨:哈尔滨工程大学,2010. LIANG Y.Study ofINS/geomagnetic matching integrated navigation system technology [D].Harbin:Harbin Engineering University,2010.

[8]王欣.基于地磁场和RSSI的室内定位算法设计与实现[D].杭州:杭州电子科技大学,2014. WANG X.Design and implementation of indoor location algorithm based on geomagnetic field and RSSI[J].Hangzhou:Hangzhou University of Electronic Science and Technology,2014.

[9]JIANG S Y,PANG G S,WU M L.An improved K-nearest-neighbor algorithm for text categorization[J].Expert Systems with Applications,2012,29(1):1503-1509.

[10]詹杰,刘宏立,刘述钢,等.基于RSSI的动态权重定位算法研究[J].电子学报,2011,39(1):82-88. ZHAN J,LIU H L,LIU S G,et al.Study algorithm based RSSI’s dynamic weights location[J].Journal of Electronics, 2011,39(1):82-88.

[11]HUANG C N,CHAN C T.ZigBee-based indoor location system by k-nearest neighbor algorithm with weighted RSSI[J].Procedia Computer Science,2011(5):58-65.

An improved indoor location algorithm based on linear interpolation

ZHANG Mengdan,LU Guangyue,WANG Honggang,LIU Jiming
Xi’an University of Posts and Telecommunications,Xi’an 710121,China

Aiming at the shortcomings of heavy workload in the off-line phase,limited positioning accuracy and poor robustness of indoor location fingerprint positioning technology,an improved fingerprint matching algorithm based on linear interpolation was proposed.Compared with the traditional location fingerprint positioning technology,it reduced the overall workload as well as the bad effects caused by muti-path effect.At last,a lab scene was set up to test the positioning performance of this algorithm.It is shown by the test that the average positioning accuracy of this algorithm has been improved by 34.25%compared with that of WKNN method,and the positioning accuracy error ratio of most points to be test is within 0.4 m,the positioning accuracy,robustness and adaptability in environment change were demonstrated.

indoor location,location fingerprint,weighted K-nearest neighbor,principal component analysis,linear interpolation

TN961

A

10.11959/j.issn.1000-0801.2017020

张梦丹（1990-），女，西安邮电大学硕士生，主要研究方向为通信网技术。

卢光跃（1971-），男，博士，西安邮电大学通信工程学院教授，主要研究方向为现代移动通信中信号处理。

王宏刚（1977-），男，博士，西安邮电大学讲师，主要研究方向为物理层能源效率和通信协议的设计、RFID和无线定位。

刘继明（1964-），男，博士，西安邮电大学教授，主要研究方向为下一代软交换核心技术。

2016-07-29；

2017-01-10

陕西省工业科技攻关项目（No.2014K05-09）；陕西省教育厅科学研究计划项目（No.14JK1660）

Foundation Items：Shaanxi Industrial Science and Technology Project(No.2014K05-09),Shaanxi Science Research Program of Education Department(No.14JK1660)