改进的蜂窝网室内定位匹配算法

2017-12-20田增山舒月月刘仪瑶李玲霞

重庆邮电大学学报(自然科学版) 2017年6期

关键词：降维离线定位精度

田增山，舒月月，刘仪瑶，李玲霞

(重庆邮电大学重庆市移动通信技术重点实验室，重庆 400065)

改进的蜂窝网室内定位匹配算法

田增山，舒月月，刘仪瑶，李玲霞

(重庆邮电大学重庆市移动通信技术重点实验室，重庆 400065)

针对无线信道的动态衰落特性，基于蜂窝网的室内定位存在较大误差，提出一种改进的蜂窝网室内定位匹配算法——基于主成分分析法(principal component analysis，PCA)的子空间匹配算法，不仅保证系统实时性，而且有效地剔除大误差点，提高定位精度。该算法利用无线蜂窝信号非视距传播造成的位置特性构建离线指纹数据库，根据在线接收信号从离线指纹库中提取子指纹库，利用PCA算法对在线实测数据及子指纹库进行有效地降维，构建子空间，并结合加权K近邻匹配算法(weighted K nearest neighborhood，WKNN)估计出多个位置坐标，利用3σ准则对这些位置做筛选，输出最终定位结果。实验结果表明，基于PCA的子空间匹配算法在保证定位实时性的前提下，能有效剔除大误差点，提高整体定位性能。

蜂窝网；子指纹库；子空间匹配；PCA；3sigma准则

0 引言

近年来，随着新型移动设备如手机、平板电脑、可穿戴设备的不断更新换代，基于位置感知的应用激增，位置服务的相关技术和产业逐渐转向室内发展。随着人们越来越关注自身及设备的精确位置信息，以及兴趣点的定位和导航[1]，室内定位逐渐成为定位技术的一个重要研究方向。

目前，被广泛关注的室内定位技术主要有基于蓝牙，RFID(radio frequency identification)，超声波，WLAN(wireless local area networks)，MEMS(micro-electro-mechanical system)，超宽带定位及蜂窝网指纹定位技术等[2-7]。与基于其他定位技术相比，蜂窝网指纹定位技术具有结构简单、能充分利用现有网络设施、不需要增加额外的硬件设备、不存在时间累积误差等优点。现有蜂窝网室内指纹定位技术通过把在线实测数据与离线指纹数据库(室内人为设置的网格点坐标联合接收信号强度组成指纹数据库)进行匹配，并把匹配算法的结果作为定位输出，在实际定位过程中，由于受到无线信道传播环境的影响，匹配算法估计出来的目标定位结果可能存在较大误差[8]。文献[9]中提出一种用于被动定位的子空间匹配算法，本文将子空间提取的思想用于蜂窝网主动定位中，对在线实测数据和离线指纹数据库采用子空间匹配算法，充分利用移动终端接收到的小区信息，有效剔除大误差点，提高定位精度。由于子空间匹配算法定位耗时过长，本文提出一种基于主成份分析法(principal component analysis,PCA)的子空间匹配算法，首先根据在线接收信号提取子指纹库，通过对子指纹库及在线实测数据进行降维处理后，构建子空间，分别进行加权K最近邻(weighted K nearest neighborhood，WKNN)匹配运算，对估计出的多个位置坐标进行3σ准则运算后输出最终估计位置坐标，从而有效剔除大误差点、提高整体精度、降低时间开销。

1 室内指纹定位技术

蜂窝网室内指纹定位技术一般分为2个阶段：离线阶段和在线阶段。离线阶段，在室内定位区域内各指纹点(即设置的网格点)处采集多个基站小区在该点处的接收信号强度(received signal strength indication，RSSI)，并与该指纹点处的位置坐标一起组合成指纹记录，建立位置指纹数据库，以下简称指纹库；在线阶段，移动终端向中心定位服务器发送从不同位置接收的小区RSSI值，服务器端通过与指纹库匹配计算出移动终端的位置信息。室内指纹定位技术基本原理如图1所示。

图1 室内指纹定位技术基本原理Fig.1 Fingerprint indoor positioning technology fundamentals

2 子指纹库提取及匹配定位

在线定位阶段中，常用的匹配算法主要有最近邻(nearest neighbor，NN)算法、K最近邻(K nearest neighbor，KNN)算法以及加权K最近邻(weighted K nearest neighborhood，WKNN)算法[10]。实测中由于某些小区信号太弱，终端无法接收，或因丢包造成终端无法解析出小区信息，使得这些小区的RSSI无法获取，从而导致实测数据与指纹数据库维度不匹配，因此，无法直接运用WKNN等算法进行定位。

假设实测RSSI与离线数据库的对应关系如表1所示。其中，RSSInm表示在离线指纹点n处接收到来自第m个小区的信号强度；Sm表示在实测点接收到来自第m个小区的信号强度；空缺处表示未接收到该小区的RSSI。

表1 实测RSSI与离线数据库的对应关系Tab.1 Corresponding relation of the measured RSSI and offline database

为使在线接收数据与指纹库维度一致，需要根据移动终端在线阶段所监测到的小区信息T(见(1)式)在离线指纹数据库中提取出相应小区的RSSI信息构成子指纹库U(见(2)式)。

(1)

(1)式中，Spj(j=1，…，m)表示移动终端实时采集的第pj个小区的接收信号强度。

(2)

成功提取子指纹库后，运用WKNN匹配算法依次计算移动终端实时采集的RSSI向量[sp1,sp2,…,spm]与子指纹库中第i个子指纹点处RSSI向量[RSSIi,p1,RSSIi,p2,…,RSSIi,pm]之间的欧氏距离

i=1,…,n

(3)

然后，挑选出K个Li值最小的指纹点，并求出这K个指纹点所对应的权重

(4)

(4)式中：ε是为防止Li等于零而设置的为正的极小量；1/(Li+ε)为测试点到第i个离线指纹点欧氏离的倒数。

(5)

WKNN匹配算法示意如图2所示。

3 子空间匹配算法

由于受到无线信道传播环境的影响，信号的多径传播可能引起移动终端接收到的某些小区信号强度值的巨大波动，并且实际采集时，可能接收不到某些小区的信号，从而导致定位结果存在较大误差。基于此，本文提出了子空间匹配算法，旨在剔除大误差点、提高定位精度。

图2 WKNN匹配算法示意图Fig.2 WKNN matching algorithm schematic

本文所提的子空间匹配算法，其处理流程如图3所示。

根据第2节提取出的子指纹库U和在线实测数据T构建子空间，并对相应的子空间矩阵运用WKNN匹配算法获得多个位置估计，利用3σ准则对这些位置做筛选，输出最终定位结果，具体步骤描述如下。

图3 子空间匹配算法流程图Fig.3 Subspace matching algorithm flow chart

(6)

(7)

(8)

4 基于PCA的子空间匹配算法

子空间匹配算法能够充分利用移动终端接收到的各小区信息，剔除大误差点，提高定位精度，但是子空间匹配算法也大大增加了时间开销。针对此问题，本文提出基于PCA的子空间的匹配算法，在运用子空间匹配算法之前，先对第3节提到的实测小区数据T和子指纹库U运用PCA进行数据降维处理，再对降维后的数据运用子空间匹配算法。基于PCA的子空间匹配算法相较于子空间匹配算法能够有效降低运算耗时。

4.1 主成分分析法

主成分分析法是一种最常用的特征提取和数据降维技术，被广泛应用于信号处理、模式识别、人工智能等领域。PCA是一种基于均方差意义上重建误差和最小的线性分析方法，它提供了将高维数据向低维空间映射的方法[12-13]。

主成分分析法的主要目的是进行数据的降维，将原来Rm维空间的数据投影到Rd维空间中 (m≥d)，并使得降维后的数据仅含原数据的主要成分。PCA的本质是在最小均方差意义下寻找最能代表数据特征的投影向量子空间。

PCA算法对数据进行降维的处理步骤如下。

步骤4对矩阵V进行特征分解，求取特征值λi和对应的特征向量wi，并降序排列特征值λi，使得λ1≥λ2≥…≥λm；

通过以上运算，每一个样本R均可投影到由Wd张成的空间中，实现对样本的降维。将PCA算法应用于蜂窝网室内指纹定位技术中，实现对高维指纹数据库的降维处理，有效缩短运算耗时。

4.2 基于PCA的子空间匹配算法

基于PCA的子空间匹配算法，实现对数据库降维处理后，利用子空间匹配算法，在保持高精度定位的同时，能够有效减小时间开销。

基于PCA的子空间匹配算法处理步骤如下。

步骤1构建实测矩阵T和子指纹库矩阵U。根据移动终端在线所监测到的小区信息，在离线指纹数据库中提取相应子指纹库构成矩阵为U。移动终端在线接收小区信息构成的实测矩阵为T。

步骤2对子指纹库矩阵U进行特征提取。求取特征值λi和对应的特征向量wi。根据具体需求，取特征值之和占总和一定比例α的前Δ′个特征值对应的特征向量构成特征矩阵W。

步骤3对实测矩阵T和子指纹库矩阵U进行降维处理。降维后的实测矩阵为Φ，Φ=TW。降维后的子指纹库矩阵为D，D=UW。矩阵Φ和矩阵D的列数维度都为Δ′。

步骤4对矩阵Φ和矩阵D采用子空间匹配算法，求得最终估计位置坐标输出。

5 算法验证与结果分析

5.1 实验环境

为了验证本文提出的基于PCA的子空间匹配算法的有效性和可靠性，选取面积64.6 m×18.5 m的重庆邮电大学行政楼一楼作为实测环境，如图4所示，测试环境共设置356个指纹点，左下角五角星为坐标原点。根据传播环境的不同将测试区域分为5个子区域，利用带有合格标识的10 m规格51系列的钢卷尺对5个子区域进行网格划分和每个指纹点坐标的测量，由于测量由多人进行读数和确认，且正确使用卷尺，因此，指纹点坐标误差在5 cm以内，几乎可以忽略不计。图4中1区、2区、4区指纹点间隔为0.6 m，3区、5区指纹点间隔为0.8 m。之后利用路测软件在各指纹点采集覆盖小区的信号强度参数，构建离线指纹数据库。测试时，Δ根据特征值之和占总和的不同比例α进行取值；δ取值为Δ-2；随机采集200组信号强度进行算法验证。

图4 重庆邮电大学行政楼一楼平面图Fig.4 First floor of administration building of CQUPT

信号采集平台及采集到的数据格式如图5和图6所示。测试中使用路测软件TEMS 9.1和索尼爱立信k800i手机进行数据采集。图6中，RSSI为信号强度，ARFCN为频点号，BSIC为基站识别色码，一对ARFCN与BSIC标志一个小区。

图5 信号采集平台Fig.5 Signal acquisition platform

图6 采集到的数据格式Fig.6 Collected data format

5.2 实验结果分析

针对上述实验环境，本文首先讨论WKNN中K值的选择，确定K值之后，分别从3个方面进行对比分析：①子空间匹配定位算法与WKNN匹配定位算法的定位精度及耗时；②基于PCA的子空间匹配定位算法在α取值不同情况下的定位精度及耗时；③基于PCA的子空间匹配算法与子空间匹配算法的定位精度及耗时。

本文首先讨论K值的选择，后面所有的实验都是基于此次选择的K值进行的比较。图7是不同K值下WKNN的定位误差。

图7 不同K值下WKNN的定位误差Fig.7 Positioning error of WKNN under different K values

由图7可知，当K=3时，系统的定位精度整体上优于其他K值的情况，虽然在小于4 m处的累计误差概率略低于K=1的概率，但对大误差点的抑制性能明显优于K=1的情况，因此，本文K取值为3。

得到K值之后，采用本文第3节所提出的子空间匹配算法进行定位。使用子空间匹配算法时，小区维度Δ的值为25，δ取值为Δ-2=23。WKNN匹配算法与子空间匹配算法的定位误差累积分布函数如图8所示。

图8 子空间匹配算法与WKNN匹配算法对比Fig.8 Comparison of the subspace and WKNN matching algorithm

WKNN匹配算法与子空间匹配算法定位精度及耗时对比如表2所示。

由图8及表2可以看出，子空间匹配算法相较于WKNN匹配算法定位效果提升明显，平均定位精度提升了0.9 m，67%误差精度提升了1.0 m，95%误差精度提升了3.2 m。综合以上分析可知，子空间匹配算法相较于WKNN匹配算法能够有效剔除大误差点，提升整体定位精度，尤其在定位误差较大时，子空间匹配算法定位效果提升更明显。但子空间匹配算法耗时过高，严重影响系统实时性。

表2 WKNN匹配算法与子空间匹配算法定位精度及耗时比较Tab.2 WKNN matching algorithm and subspace matching localization precision and time-consuming comparison

基于本文第4节提出的算法，对基于PCA的子空间匹配算法的定位效果进行分析。采用基于PCA的子空间匹配算法进行定位时，α值为进行数据库降维处理时选取的特征值之和占总和的比例。下面对α取值分别为1.00，0.95，0.90，0.85，0.80时的定位精度及耗时进行对比分析。图9是不同α下的定位误差比较。

由图9可以看出，α取值分别为0.90，0.85，0.80时，无论是从整体定位精度上还是对大误差的抑制效果上都明显低于α取值分别为1，0.95时的定位效果，这是因为若α取值过低，会损失较多有用信息，导致定位效果变差。α取值不同时的定位精度及耗时如表3所示。

表3的结果表明，在α取值为0.95时，基于PCA的子空间匹配算法定位精度虽然略低于单纯的子空间匹配算法，但耗时相比于原子空间匹配算法大大降低。因此，综合定位精度和耗时考虑，α取值为0.95时定位性能最优。

表3 α取值不同时的定位精度及耗时比较Tab.3 Positioning accuracy and time consuming comparison when α is different

最后，本文对WKNN匹配算法、子空间匹配算法、基于PCA的子空间匹配算法的定位效果从定位精度和耗时进行整体对比分析，如表4所示。

表4中，相较于WKNN匹配算法，子空间匹配算法能够有效剔除大误差点，尤其在WKNN匹配算法的定位误差较大时能够有效提高定位精度，并从整体上提升定位精度。但是，子空间匹配算法相较于WKNN匹配算法时间开销过高。基于PCA的子空间匹配算法保留了子空间匹配算法剔除大误差点、提升定位误差较大时定位精度的优点，并降低了耗时。从定位精度和耗时整体方面考虑，基于PCA的子空间匹配算法相较于WKNN匹配算法、子空间匹配算法具有更优的定位性能。

表4 3种匹配算法定位精度及耗时比较Tab.4 Three match algorithm positioning accuracy and time consuming comparison

6 结束语

本文针对蜂窝网室内指纹定位过程中估计出的用户位置误差较大的问题，采用子空间匹配算法，针对子空间匹配算法运算耗时严重的问题，提出基于PCA的子空间匹配算法，在可以接受的时间开销下，剔除大误差点，提升整体定位精度。实验结果表明，本文提出的基于PCA的子空间匹配算法可以提高定位精度，具有较好的整体定位性能。

[1] GU Y Y, LO A, NIEMEGEERS I. A survey of indoor positioning systems for wireless personal networks [J]. IEEE COMMUNICATIONS SURVEYS AND TUTORIALS, 2009, 11(1): 12-32.

[2] 赵锐，钟榜，朱祖礼，等.室内定位技术及应用综述[J]. 电子科技, 2014, 27(3):154-157.

ZHAO Rui, ZHONG Bang, ZHU Zuli, et al. Indoor positioning technology and application summary[J]. Electronic Technology, 2014, 27(3):154-157.

[3] SHOARINEJAD K, SOLTAN M, MOSHFEGHI M. RFID location systems and methods: US, 8294554 B2 [P]. 2012-10-23.

[4] TIAN Z S, ZHANG Y, ZHOU M, et al. Smartphone-based indoor integrated WiFi/MEMS positioning algorithm in a multi-floor environment[J]. Micromachines, 2014, 6(3): 1-9.

[5] 周先赞，熊剑，郭杭，等. 基于超声波/INS信息融合的室内定位方法[J]. 压电与声光，2016, 38(2): 316-319.

ZHOU Xianzan, XIONG Jian, GUO Hang, et al. The Indoor Position Method Based on Ultrasonic/INS Information Fusion [J]. Piezoelectrics and Acoustooptics, 2016, 38(2): 316-319.

[6] 杨小凤，陈铁军，黄志文，等. 基于超宽带的TOA-DOA 联合定位方法[J].重庆邮电大学学报：自然科学版，2016, 28(2):194-198.

YANG Xiaofeng, CHEN Tiejun, HUANG Zhiwen, et al. Hybrid TOA-AOA location method based on ultra-wideband[J].Journal of Chongqing University of Posts and Telecommunications: Natural Science Edition，2016, 28(2):194-198.

[7] WANG Y X, YE Q, CEHNG J, et al. RSSI-based bluetooth indoor localization[C]//IEEE.11th International Conference on Mobile Ad-Hoc and Sensor Networks. New York, USA：IEEE Press, 2015:165-171.

[8] LIU X D, HE W, TIAN Z S. The improvement of RSS-based location fingerprint technology for cellular networks[C]//IEEE.2012 International Conference on Computer Science & Service System (CSSS).New York, USA：IEEE Press, 2012:1267-1270.

[9] JIHOON H, TOMOAKI O. Device-free passive localization from signal subspace eigenvectors[C]//IEEE.Global Communications Conference (GLOBECOM).New York, USA：IEEE Press,2014: 430-435.

[10] 王磊，周慧，蒋国平，等. 基于WiFi的自适应匹配预处理WKNN算法[J]. 信号处理, 2015(9):1067-1074.

WANG Lei, ZHOU Hui, JIANG Guoping, et al. The adaptive matching pretreatment WKNN algorithm based on WiFi [J]. Signal Processing, 2015(9):1067-1074.

[11] 正态分布及3Sigma原理[EB/OL]. (2013-03-25)[2017-01-22].http://wenku.baidu.com/view/ef44d6d528ea81c758f578c5.html.

Normal distribution and 3Sigma principle [EB/OL]. (2013-03-25)[2017-01-22].http://wenku.baidu.com/view/ef44d6d528ea81c758f578c5.html.

[12] PUYATI W, WALAIRACHT A. Efficiency improvement for unconstrained face recognition by weightening probability values of modular PCA and wavelet PCA[C]//IEEE.International Conference on Advanced Communication Technology. New York, USA：IEEE Press, 2008:1449-1453.

[13] 杨开睿，孟凡荣，梁志贞. 一种自适应权值的PCA算法[J]. 计算机工程与应用,2012, 48(3):189-191.

YANG Kairui, MENG Fanrong, LIANG Zhizhen. An adaptive weighting of PCA algorithm[J].Computer engineering and application, 2012, 48(3):189-191.

s：The National Natural Science Foundation of China (61301126);The Fundamental and Frontier Research Project of Chongqing (cstc2013jcyjA40041,cstc2015jcyjBX0065);The Young Science Research Program of Chongqing University of Posts and Telecommunications(A2013-31)

Improvedindoorlocalizationmatchingalgorithmforcellularnetworks

TIAN Zengshan, SHU Yueyue, LIU Yiyao, LI Lingxia

Chongqing Key Lab of Mobile Communications Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, P.R. China)

Due to the dynamic fading characteristics of wireless channel, the localization performance will be dramatically deteriorated in cellular network. Therefore, a principal components analysis (PCA) based subspace matching algorithm for indoor localization within cellular networks is proposed, which not only guarantees the real-time localization requirement, but also effectively eliminates the large error points for the sake of accuracy enhancement. Specifically, the off-line fingerprint database is constructed firstly according to the positional characteristics caused by the non-line-of-sight propagation of the wireless cellular signal. Then the sub-fingerprint database is extracted in line with the

signal. Next, PCA algorithm is utilized to reduce the dimension of both on-line received signal strength and sub-fingerprint database, which then forms a new subspace. After that, the weighted K nearest neighbors (WKNN) is adopted for multiple-target localization. Finally, the targets are screened based on 3σrule in order to determine the final location. Experimental results show that the proposed approach can effectively eliminate the outliers and thus improve the overall on-line positioning performance under the premise of ensuring the real-time positioning.

cellular networks; sub-fingerprint database; subspace matching; PCA; 3sigma rule

10.3979/j.issn.1673-825X.2017.06.006

2016-12-21

2017-04-20

舒月月 675522567@qq.com

国家自然科学基金(61301126)；重庆市基础与前沿研究计划项目(cstc2013jcyjA40041,cstc2015jcyjBX0065)；重庆邮电大学青年科学研究项目(A2013-31)

TN 929.5

1673-825X(2017)06-0744-07