基于RSS空间线性相关的WLAN位置指纹定位算法

徐小良，高健，黄河，马哲

（1.杭州电子科技大学计算机学院，浙江 杭州 310018；2.中浙信科技咨询有限公司，浙江 杭州 310007）

基于RSS空间线性相关的WLAN位置指纹定位算法

徐小良1，高健1，黄河2，马哲2

（1.杭州电子科技大学计算机学院，浙江 杭州 310018；2.中浙信科技咨询有限公司，浙江 杭州 310007）

针对RSS（接收信号强度）时变性以及不同终端信号接收能力的差异性，导致WLAN位置指纹定位不稳定的问题，基于RSS空间线性相关性提出一种新颖的位置指纹定位算法。在每个参考点分别采集多组RSS样本形成特征矩阵，并构建离线位置指纹数据库。定位时，通过计算实时RSS矩阵与指纹库参考点相关性，得到最相关的k个参考点，利用二次加权质心算法计算用户的最终位置。为了有效降低信号时变性的影响，采样时进行了滤波、排序等处理，构建离线指纹数据库时尽量增加采样次数，但需要对样本进行聚合处理以适应定位相关性计算。实验结果表明，该算法在保证较高定位准确度的同时，针对不同终端有更好的定位稳定性。

室内定位；位置指纹；线性相关；加权质心算法

1 引言

随着无线网络的广泛普及和移动智能终端的迅猛发展，室内定位受到越来越多的关注。由于室内空间比较狭小，无线电波的传播方式非常复杂，大多数的定位方法难以实现稳定的定位效果。

目前用于室内定位的主要方法有基于信号到达时间（time ofarrival，TOA）[1]、基于信号到达时间差（time difference of arrival，TDOA）[2]、基于信号到达角度（angle ofarrival，AOA）[3]、基于接收信号强度（received signal strength，RSS）和基于信道状态信息（channel state information，CSI）[4]等。基于RSS的定位方法是根据信号强度随传播距离变化的规律实现定位，相比于其他定位方法，开发成本低、定位精度较高，是现今主流的室内定位方法[5]。

研究人员已经针对RSS定位方法开展了大量的研究工作，并取得了一定的研究成果。参考文献[6]提出一种考虑室内环境布局等因素的无线传播模型，有利于提高定位精度；参考文献[7]根据目标AP（access point，接入点）距离采用简单质心算法与加权质心算法进行定位计算，解决测试点距离AP位置较远时准确性不高的问题；参考文献[8]提出基于矩阵相关（matrix correlation，MC）的位置指纹定位算法，算法能充分利用RSS样本信息，具有较精确的定位效果；参考文献[9]提出了一种抗多径和阴影的视距指纹定位算法，降低了环境对室内定位精准度的影响；参考文献[10]提出一种基于主成分分析 （principal component analysis，PCA）白化RSS的聚类算法，以增强指纹库稳定性，使定位误差在2 m内的概率提高44.8%。上述方法虽然在特定环境下提高了室内定位的精确度，但针对不同终端，由于硬件及采用的无线技术不同，使得定位稳定性较差。参考文献[11]提出使用同一位置不同 AP的信号强度差值（signal strength difference，SSD）来消除环境的干扰，可以在一定程度上降低终端异质的影响，但定位精准度受到影响。

上述研究工作并未针对不同终端下定位稳定性差的问题做出深入的研究和探索，导致现有的室内定位方法在不同终端情况下稳定性较差。本文针对此问题，充分利用信号强度信息，结合室内定位基本流程提出一种新颖的位置指纹定位算法。将RSS空间线性相关性作为定位度量标准，通过计算实时采集的 RSS数据与指纹样本数据的线性相关系数，选取候选参考点利用二次加权质心算法进行定位，该算法不仅能保证定位精度，在不同终端定位时有更好的稳定性。

2 RSS特性分析

将某一位置采集到的多个AP信号强度信息称为RSS样本，当室内环境能够收到足够数目（如4个以上）的 AP信号时，在任意两个位置上获取的RSS样本和位置的物理距离存在很强的相关性，这种相关性会随着位置间距的增大而减小，同时也受终端设备差异性的影响。本节分析了不同位置、不同终端下RSS的空间线性相关性，为本文提出的定位算法提供理论基础。

2.1 不同位置RSS空间线性相关性

RSS能在一定程度上描述两个位置点环境的近似程度[9]，对一个具体的AP、MT（mobile terminal，移动终端）组合，假定P（d）和P（d0）分别表示与AP相距任意距离d和参考距离d0处的接收信号强度，则有：

其中，PAP是 AP的发送功率；GAP是AP的天线增益；GMT是 MT的天线增益；f是系统损耗因子；λ是无线信号的波长；β是路径损耗因子；X是一个正态随机变量，X～N（0，σ2）。

由式（1）可知，假设外界环境相同，即硬件参数、系统损耗等因素不变，RSS主要依赖于终端与AP的距离d。当它们位置比较接近时，终端所能采集的RSS样本也比较相似，本文利用皮尔逊相关系数来描述这种空间相关性。计算相邻位置RSS样本相关系数，由于RSS样本比较相似，所以计算出的相关系数趋于1，把这种相邻位置RSS样本强相关称为空间线性相关。

可是实际情况下，RSS受到AP和MT的硬件参数以及外界环境的影响而产生波动。为了更有效地表示RSS空间线性相关性，需要对测量的RSS进行滤波处理，并用多组RSS样本信息构建矩阵来描述位置点的指纹信息。

2.2 不同终端下RSS空间线性相关性

目前大多数的移动终端都具有测量AP RSS的能力，由于不同终端所采用的无线技术及硬件存在差异，同一位置每次所获取的AP RSS往往有波动，这就对室内定位造成了一定的难度。

根据式（1），两个不同终端在同一位置对某AP的RSS观测值如下：

由P（d）1-P（d）2可得：

从式（3）可以看出，对不同终端RSS值做差后，结果和AP配置几乎无关，尽管结果受到终端天线增益G、系统损耗因子f、路径损耗因子β、随机变量X等因素的影响，但当外界条件相同时，这些配置一般是保持不变的，因此，不同终端的差值趋于一个常量。由此可知，各终端所采集的RSS样本值是线性相关的，将这种特性作为定位度量标准可以有效屏蔽终端的差异性。

为了验证这个结论，在杭州电子科技大学第一教学楼403实验室，利用3种不同移动终端分别采集接收到的20个AP的强度，进行了实验对比，结果如图1所示，图1中每一个点是对相应AP进行多次RSS测量的均值，实验也表明了RSS的线性相关性。从图1中还可以分析出，当RSS较强时，这种相关性比较明显；当RSS较弱时，相关性不太明显，因此在定位阶段，应该做好AP的选择，摒弃较弱的AP。

3 基于RSS空间线性相关定位方法

3.1 概述

由第2节分析可知，RSS具有显著的空间线性相关性，对于不同终端，虽然信号接收能力存在差异，但是采集的RSS样本也存在这种空间线性相关性，充分说明了RSS空间线性相关性对室内定位具有积极的意义。

在室内定位系统中，如何克服终端设备的差异性对定位精度以及稳定性的影响，进而实现精确、稳定的定位系统是室内定位领域的重点和难点。基于RSS位置指纹定位技术包括离线指纹库构建和在线定位两个阶段[12]。本文将RSS空间线性相关性应用于上述两个阶段，在每个参考点采集多组RSS样本形成特征矩阵，充当指纹，通过皮尔逊相关系数计算实时RSS数据与指纹库 RSS信息相关系数，最后利用二次加权质心算法计算最终位置。总体框架如图2所示。

基于RSS空间线性相关性的室内定位算法的过程可概括如下。

（1）离线指纹数据库构建阶段

该阶段主要工作是进行数据采集，构建能够描述位置信息的指纹数据库。其中包括数据采集、数据过滤和数据处理。针对数据采集，首先在目标定位环境中设计若干个参考点，通过移动设备在每个参考点采集多组RSS样本信息，得到原始训练数据集；针对数据过滤，由于室内环境比较复杂以及信道拥塞，导致移动设备接收的RSS信息存在时变性，因此需要采用数据过滤规则对原始RSS数据集进行过滤处理，提高训练样本质量，本文采用限幅平均滤波法对RSS信息进行过滤处理；针对数据处理，首先对 RSS样本进行排序处理，以增强与在线采集的RSS数据的相关性，其次，为了保证与在线RSS数据有相同的维度，需要对RSS样本进行聚合处理，最终得到参考点指纹信息。

（2）在线定位阶段

图1 同一位置不同终端分别采集多个AP的RSS样本对比

图2 定位系统总体框架

该阶段的主要工作是通过比较终端实时获取的RSS数据与指纹库中的RSS数据，将信号强度最相似的参考点的位置估计为目标定位结果。其中包括RSS信息采集、数据过滤、空间线性相关性计算和最终位置估算。针对 RSS信息采集，在现阶段连续采集多组RSS样本信息，作为待预测位置的原始 RSS特征信息；针对数据预处理，对原始RSS样本信息进行滤波和排序处理，得到描述待预测位置的RSS特征矩阵；针对空间线性相关性计算，通过计算待预测位置 RSS特征矩阵与离线指纹库各参考点指纹皮尔逊相关系数，确定最相似的k个参考位置点；针对位置估算，由于最终确定的k个相似位置点中常存在偏离用户当前位置较远的参考点，这些点会严重影响定位精度，所以利用二次加权质心算法进行位置估算，得到用户的最终位置。

3.2 离线指纹数据库构建阶段

由第3.1节可知，离线阶段首先需要RSS数据采集以及数据处理。假设目标定位环境有 P个 AP用于定位，移动设备在物理位置l处第n次采集的RSS样本信息为其 中 p= 1,2，…,P，rssl,n,p表示参考点l处第n组RSS样本中第p个AP的信号强度。

对参考点 l多次采集的 RSS样本进行过滤后，得到N组RSS样本序列，用矩阵Fl表示：

其中，rssl,n,p表示参考点 l第 n组 RSS信息中第 p个AP的RSS值。

Fl的第p行表示参考点l对第p个AP的多次RSS信息采集，为了增强离线指纹库与在线RSS数据的相关性，对同一AP多次采集的RSS进行排序，即对矩阵Fl每一行排序，使矩阵满足：

离线指纹库构建时，采集的RSS组数越多，越能形象描述参考位置空间特性，定位精确度越高。在实时定位时，终端也需要采集相应组数RSS样本，这就使得定位速度缓慢。要做到快速定位，需要对矩阵Fl聚合处理，使得定位阶段需要采集的RSS样本较少。

3.3 在线定位阶段

离线阶段通过数据过滤与处理，去除了训练样本中不稳定、非正常的RSS数据，得到能较准确描述参考位置的离线指纹数据库。在线定位过程中，采集到待定位的实时RSS数据，也要对RSS数据进行滤波、排序等处理，然后对比实时RSS数据与参考点指纹相关性，通过皮尔逊相关系数描述这种相关性，对最相关的k个参考点，利用二次加权质心算法计算用户的最终位置。

3.3.1 基于RSS线性相关系数计算

在待定位区域，终端采集m组通过滤波处理的RSS样本，构建成一个P×M维的RSS测量矩阵，对RSS测量矩阵的每一行进行排列，需要和指纹库构建时排序规则相同，即可得到需要的在线RSS矩阵F*：

根据皮尔逊相关系数计算在线终端接收样本与指纹数据库样本的线性相关系数rl，为：

将所述Q个相关系数计算好后，对其进行降序排序，从大到小取k个相关系数所对应的参考点{P1P2…Pk}，Pk=（xkykrk）。Pk表示所述Q个相关系数降序排序后的第k个相关系数所对应的参考点信息，（xk，yk）分别是第k个相关系数所对应的坐标值，rk表示第k个相关系数。然后，运用加权质心算法，求出用户的最终位置点。

3.3.2 二次加权质心算法进行位置估算

质心算法是将最终确定的 k个相似参考点组成多边形，用该多边形质心代表估算位置。由于该k个相似位置点中常存在偏离用户当前位置较远的参考点，采用传统的质心算法会受到这些点的干扰，影响定位精度。如图3所示，参考点 A、B、C、D、E在待定位位置S周围呈不均匀分布，质心算法结果将最终位置定位在I点。在图 3所示的3种情况中，均是参考点A和E离待定位位置S的实际距离较远，由于其产生的负面作用，使得估算出的位置I不同程度地偏向A和E点，待定位位置的实际位置距A和E越远，偏离程度越大。

本文用二次加权质心算法来计算用户的最终位置，第一次质心算法预算出初始位置，第二次质心算法中，首先将距离初始位置较远的坐标归并为有用的参考点，然后再进行一次加权质心算法估算用户最终位置，如图4所示，将A、E归并为F点，再利用B、C、D、F组成的多边形的质心I充当定位的位置。

二次加权质心算法具体计算过程如下。

（1）一次加权质心算法计算

将k个相似参考点信息拆分为两个数组VX和VY：

其中，VX和VY表示所述k个相关系数所对应的参考点信息中x坐标数组和y坐标数组，vxk和vyk表示第k个相关系数对应参考点的x坐标和y坐标信息。

对所述 k个位置节点利用加权质心算法进行第一次计算，算出初始位置坐标质心算法如下：

图3 参考点分布不均匀时定位误差示意

图4 二次加权质心处理原理

其中，k表示所述Q个相关系数降序排序后取得的参考点数量，ri表示第 i个参考点所对应的相关系数，（xi，yi）分别表示第i个参考点对应的位置坐标信息。

（2）二次加权质心算法计算

4 实验与结果分析

对于本文所提出的算法，搭建了实际环境并进行了相应的实验，实验环境部署在杭州电子科技大学第一教学楼403实验室，为长22.5 m、宽14 m的矩形场地，室内布置4个AP，分别在4个角落。对加权K近邻（W K NN）定位算法[13]、矩阵相关定位算法[8]和基于信号强度差定位算法[9]与本文定位新算法进行比较实验。

（1）实验1

定位与指纹库构建阶段，采用相同终端情况下，采用不同的参考点间距，分别测试4种定位算法平均误差，如图5所述。定位误差定义为：

其中，（xi，yi）表示第 i个测试点的实际物理坐标，（xi,1oc，yi,1oc）表示第 i个测试点的估算位置坐标。

图5 W K NN、MC、SSD与本文算法定位误差比较

图5中可以看出当距离为 0.5～1.5 m时，4种定位算法精度都较高，其中本文算法定位误差最小，当大于1.5 m时，定位误差明显增大。考虑到采样间距太小会使得采集指纹的工作量增大，因此后续的实验采取1 m作为构建离线指纹库时采样点间距。当取1 m作为采样间距时，本算法的平均定位误差为1.96 m，相比W K NN算法2.37 m与SSD算法2.45 m有较大的提升，比MC算法的2.13 m提升了0.17 m。

（2）实验2

定位与指纹库构建阶段，采用相同终端情况下，对不同位置定位误差波动性进行对比实验。

图6给出了W K NN、MC、SSD与本算法在25个采样点的误差对比结果。从整体上看，相比于W K NN算法和SSD算法，本算法定位误差波动性较小，相比于MC算法，定位误差波动相似。

（3）实验3

定位与指纹库构建阶段，采用不同终端进行对比实验。指纹库构建采用华为荣耀7手机，定位时分别采用华为荣耀7、红米Note 2、中兴u956手机。图7分别给出了W K NN、MC、SSD与本算法定位误差累计概率的比较结果。

从图7可以看出，本文算法在误差距离为 5 m时，定位误差累计概率趋于1，而SSD算法、W K NN算法和MC算法分别需要误差距离达到7 m、6.5 m和5.5 m，这也就验证了实验1的结论。在不同终端条件下，图7显示了使用W K NN算法时，不同终端差异化比较明显，说明该算法受终端异质的影响较大，而MC算法和SSD算法相对于W K NN算法，受终端异质的影响较小，而本文提出的算法受终端异质影响最小。因此可以得出，本文算法相对于其他3种算法，在不同终端定位下有更好的稳定性，并且相比于W K NN算法和SSD算法，在定位精度方面有明显的优势。

图6 W K NN、MC、SSD与本文算法在各个定位点误差

图7 不同算法下不同终端定位误差累计概率比较

5 结束语

针对RSS时变性以及不同终端信号接收能力差异性的问题，本文提出了基于RSS空间线性相关的WLAN室内定位算法，该算法利用特征矩阵充当参考点的指纹信息，利用相关系数作为相似性度量标准，采用二次加权质心算法估算用户的最终位置。通过实验结果可以看出，本文算法有较高的定位精度，平均定位误差可以达到1.96 m，并且本算法可以有效降低不同终端信号接收能力差异性对定位性能的影响。考虑到目前的智能终端都内置很多先进的传感器原件，因此在后续的研究中，计划将多传感器与位置匹配算法融合来进一步提升定位的精度。

[1]AL-JAZZAR S,CAFFERY J J,YOU H R.A scattering model based approach to NLOS mitigation in TOA location systems[C]// IEEEVehicularTechnology Conference,May6-9,2002,Birmingham, England.New Jersey:IEEE Press,2002:861-865.

[2]YAMASAKIR,OGINO A,TAMAKIT,etal.TDOA location system for IEEE 802.11b WLAN[C]//IEEE Wireless Communications and Networking Conference,March 13-17,2005,New Orleans, USA.New Jersey:IEEE Press,2005:2338-2343.

[3]XIE Y Q,WANG Y,ZHU C,et al.Grid search based hybrid TOA/AOA location techniques for NLOS environments[J].IEEE Communications Letters,2009,13(4):254-256.

[4]HALPERIN D,HU W,SHETH A,et al.Predictable 802.11 packet delivery from wireless channel measurements[J].ACM Sigcomm Computer Communication Review,2010,40(4): 159-170.

[5]HOSSAIN A K M M,SOH W S.A survey of calibration-free indoor positioning systems[J].Computer Communications,2015(66):1-13.

[6]NARZULLAEV A,PARK Y,YOO K,et al.A fast and accurate calibration algorithm for real-time locating systems based on the received signal strength indication[J].AEU-International Journal of Electronics and Communications,2011,65(4):305-311.

[7]刘畅,张迅.WLAN接入点的室内定位技术 [J].电信科学, 2015,31(2):135-139．LIUC,ZHANGX.WLANaccesspointindoorpositioningtechnology[J]. Telecommunications Science,2015,31(2):135-139.

[8]SUNYL,XUYB.Errorestimation method formatrixcorrelation-based W i-Fi indoor localization[J].KSII Transactions on Internet& Information Systems,2013,7(11):2657-2675.

[9] 陈永乐,朱红松,孙利民.一种抗多径和阴影的视距指纹定位算法[J].计算机研究与发展,2013,50(3):524-531. CHEN Y L,ZHU H S,SUN L M.A line of sight fingerprint localization algorithm resisting multipath and shadow[J].Journal of Computer Research and Development,2013,50(3):524-531.

[10]杨明极,刘恺怿,邵丹.用于WLAN室内定位的PCA聚类算法[J].电信科学,2016,32(7):21-26. YANG M J,LIU K Y,SHAO D.PCA clustering algorithm for indoor positioning in WLAN[J].Te lecommunications Science, 2016,32(7):21-26.

[11]CHANG N,RASHIDZADEH R,AHMADI M.Robust indoor positioning using differential wi-fi access points [J].IEEE Transactions on Consumer Electronics,2010,56(3):1860-1867.

[12]GENTILE C,ALSINDI N,RAULEFS R,et al.Geolocation techniques:principles and applications[M].Berlin:Springer Publishing Company,2014:64-70.

[13]XUYB,ZHOUM,MENGWX,etal.Optimal K NNpositioning algorithm via theoreticalaccuracy criterion in WLAN indoor environment[C]// 2010 IEEE Global Telecommunications Conf,Dec 6-10,2010, Miami,USA.New Jersey:IEEE Press,2010:1-5.

Fingerprint localization algorithm based on linear spatial dependence of WLAN RSS

XU Xiaoliang1,GAO Jian1,HUANG He2,MA Zhe2
1.School of Computer Science and Technology,Hangzhou Dianzi University,Hangzhou 310018,China 2.Zhongzhexin Consulting Co.,Ltd.,Hangzhou 310007,China

Due to RSS time-varying and difference of signal receiving ability of different terminals,the performance of RSS-based technologies is usually instability.In order to solve such problem,a novel fingerprint localization algorithm based on linear spatial dependence of RSS was proposed.Multiple sets of RSS samples were collected at each reference point to form a feature matrix and an offline location fingerprintdatabase was conducted.When the real-time RSS matrix was used to calculate the correlation between the real-time RSS matrix and the reference point of the fingerprint library, the k-reference points were obtained,and the final position of the user was calculated by the quadratic weighted centroid algorithm.In order to effectively reduce the influence of signal time-varying,the sampling and sorting process were carried out,and the number of sampling times increased as much as possible when constructing the offline fingerprint database,but the samples needed to be aggregated to fit the positioning correlation calculation.Experiment results show that the proposed algorithm can guarantee the high positioning accuracy and also achieve the better stability for different term inal.

indoor localization,location fingerprint,linear dependence,weighted centroid algorithm

TN911

：A

10.11959/j.issn.1000-0801.2017064

徐小良（1976-），男，杭州电子科技大学计算机学院教授、硕士生导师，主要研究方向为无线网络、大数据处理、人工智能等。

高健（1991-），男，杭州电子科技大学计算机学院硕士生，主要研究方向为无线与移动通信。

黄河（1991-），男，中浙信科技咨询有限公司工程师、技术经理，主要研究方向为数据通信。

马哲（1982-），男，博士，中浙信科技咨询有限公司工程师，主要研究方向为大数据分析。

2017-01-10；

2017-03-03

国家青年科学基金资助项目（No.61602410）

Foundation Item:The National Science Foundation for Young Scientists of China(No.61602410)