基于主成分分析和卡方距离的信号强度差指纹定位算法

周非 夏鹏程

摘 要：由于不同型号移动终端获取的接收信号强度（RSS）存在明显差异，传统的基于RSS位置指纹库的室内定位算法定位稳定性和精度不高，而现有的采用信号强度差（SSD）替代RSS构建位置指纹库的解决方案存在高数据维度、相关性冗余过高和K近邻（KNN）算法本身定位精度不高的问题。针对上述问题，提出了一种基于主成分分析（PCA）和卡方距离（CSD）的SSD指纹定位算法，使用PCA算法进行SSD数据降维和相关性冗余消除，并使用CSD度量降维后特征量间的相对距离进行位置匹配。仿真实验中，使用所提算法的SSD位置指纹库定位误差累积概率曲线高于原有RSS和SSD指纹库;相比传统的KNN算法和基于余弦相似度改进的KNN算法（COSKNN），所提算法的平均定位误差、定位误差方差均有明显减小，时间开销稍有增加。实验结果表明，所提算法可以有效提升原有SSD指纹定位方法的定位稳定性和定位精度，能够满足室内定位的实时性需要。

关键词：室内定位;位置指纹库;信号强度差;主成分分析;卡方距离

中圖分类号：TN929.5; TP393.1

文献标志码：A

Abstract： Due to the significant difference in Received Signal Strength （RSS） acquired by different types of mobile terminals， the traditional indoor localization algorithm based on RSS location fingerprint database has low localization stability and accuracy， existing solutions using Signal Strength Difference （SSD） instead of RSS to construct location fingerprint database has problems such as high data dimension， and high correlation redundancy， and KNearest Neighbors （KNN） algorithm has low positioning accuracy. Aiming at the above problems， an SSD fingerprint localization algorithm based on Principal Component Analysis （PCA） and ChiSquare Distance （CSD） was proposed. PCA algorithm was used to reduce the dimension of SSD data and eliminate correlation redundancy， and CSD was used to measure the relative distance between the feature quantities after dimension reduction to match the position. In the simulation experiments， the positioning error cumulative probability curve of the SSD location fingerprint database using the proposed algorithm is higher than that of the original RSS and SSD fingerprint database. Compared with the traditional KNN and the improved KNN algorithm based on Cosine Similarity （COSKNN）， the average positioning error and the positioning error variance of the proposed algorithm are both significantly reduced while time cost is slightly increased. The experimental results show that the proposed algorithm can further improve the positioning stability and positioning accuracy of the original SSD fingerprint localization algorithm effectively， and meets the realtime needs of indoor localization.

英文关键词Key words： indoor localization; location fingerprint database; Signal Strength Difference （SSD）; Principal Component Analysis （PCA）; ChiSquare Distance （CSD）

0 引言

近几年，随着移动通信技术的飞速发展和无线网络的全面普及，室内定位技术越来越受到人们的关注。随着微软公司提出首个基于位置指纹库的室内定位系统RADAR[1]，越来越多的研究者采用基于接收信号强度（Received Signal Strength， RSS）的位置指纹定位方法[2]，但是传统的指纹定位方法存在定位精度不高和定位稳定性较差等问题[3-4]。

基于位置指纹库的WLAN（Wireless Local Area Network）室内定位方法通常分为离线和在线两个阶段，利用在线阶段设备采集的RSS信号与离线阶段构建的位置指纹库进行匹配来估算用户位置，但是当在线阶段用于获取RSS信号值的采集终端与离线阶段型号不一致时，两者采集的RSS信号会产生明显的差异，从而导致定位结果与实际位置产生较大的偏差。为了解决此类问题，文献[5]采用线上实时调整两种设备RSS信号差异的方法，但该方法计算量大，定位耗时较长;文献[6]提出不同设备之间RSS信号变化特征存在线性关系，可以通过线性回归模型校正异构设备的RSS差异，但是为各种不同型号的设备建立线性关系模型需要耗费大量的人力和物力;文献[7]提出一种利用对数函数的方法，该方法根据对数函数的单调特性，将RSS值转换为对数函数值，并以此构建新的位置指纹数据库，通过仿真实验验证此方法可以减小异构设备环境下RSS数据的波动性，但是映射后的未经处理的数据在异构设备上仍有一定的差异性，因此在进行位置匹配时会降低定位精度;文献[8]提出采用信號强度差（Signal Strength Difference， SSD）来构建位置指纹库的方法，该方法是不用校正的稳健指纹方法，但是文献[8]并没有考虑到SSD代替RSS产生的数据量增加和相关性冗余问题; 文献[9]同样采用SSD构建位置指纹库，直接提取SSD数据有效成分，并未作数据处理，因此当在线定位阶段的接收设备与离线采集设备相同时，该方法和RSS指纹库相比反而会降低定位精度。除了异构设备RSS信号差异性的问题，传统的指纹定位方法采用K近邻（KNearest Neighbors， KNN）算法作为匹配算法，该算法定位精度不高。针对此问题，有学者提出使用相似度度量改进欧氏距离度量的方法，如：文献[10]提出使用余弦相似度改进传统的KNN算法，该方法在一定程度上提高了定位精度;文献[11]提出使用卡方距离（ChiSquare Distance， CSD）改进的KNN算法进行在线阶段的位置匹配，该方法采用卡方距离衡量RSS数据特征量的相关程度，提高了定位精度。还有学者提出使用监督学习的方法建立在线定位模型：文献[12]采用支持向量机回归算法估算用户位置，该方法可以实现较精确的定位;文献[13]提出使用循环神经网络训练离线采集的RSS数据以进行位置匹配，但是该方法需要大量的训练样本。类似上述监督学习的方法容易产生过拟合，因此泛化能力不强，无法适应多变的应用场景。

4 结语

本文提出了基于PCA和CSD的SSD指纹定位算法，使用PCA对SSD数据进行降维和消除相关性冗余，同时考虑到降维后数据特征量与原数据变化较大，使用卡方距离度量降维后SSD数据样本间特征量的相对距离以实现位置匹配。仿真实验结果表明，该算法提升了原有RSS和SSD指纹库的定位稳定性和定位精度，且可以满足室内定位的实时性需要。

由于本文所提算法需要在离线阶段进行PCA降维计算，当应用场景中用于构建指纹库的AP数量较多时，会增加离线阶段一定的计算成本，而且随着时间的推移和定位环境的改变，原参考点采集到的RSS数据会发生变化，这势必会影响已构建完成的SSD位置指纹库定位性能，所以如何对离线阶段的算法进一步优化和更新SSD指纹库将是下一步的工作重点。

参考文献 （References）

[1]     BAHL P， PADMANABHAM V N. RADAR： an inbuilding RFbased user location and system[C]// Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway， NJ： IEEE， 2000： 775-784.

[2]     马宽红. 基于位置指纹的WiFi室内定位技术研究[D]. 哈尔滨： 哈尔滨工业大学， 2017：8-12.（MA K H. WiFi indoor location technology based on the fingerprint[D]. Harbin： Harbin Institute of Technology， 2017： 8-12.）

[3]     王建平， 李程程， 李奇越，等. 基于WiFi的动态室内定位方法研究[J]. 传感器与微系统， 2017， 36（2）：49-52.（WANG J P， LI C C， LI Q Y， et al. Research on dynamic indoor positioning method based on WiFi[J]. Transducer and Microsystem Technologies， 2017，36（2）：49-52.）

[4]     HE S， CHAN S H G. WiFi fingerprintbased indoor positioning： recent advances and comparisons[J]. IEEE Communications Surveys & Tutorials， 2017， 18（1）：466-490.

[5]     FANG S H， WANG C H， CHIOU S M， et al. Calibrationfree approaches for robust WiFi positioning against device diversity： a performance comparison[C]// Proceedings of the 2012 IEEE 75th Vehicular Technology Conference. Piscataway， NJ： IEEE， 2012，15（3）：1-5.

[6]     王敬彬. 室内定位RSSI空间建模与接收设备偏差研究[D]. 成都：西南交通大学， 2017： 38-46.（WANG J B. Research on the RSSI spatial modeling and receiving equipment deviation of indoor position[D]. Chengdu： Southwest Jiaotong University， 2017： 38-46.）

[7]     MIKKEL B K， MUNK C V. Hyperbolic location fingerprinting： a calibrationfree solution for handling differences in signal strength[C]// Proceedings of the 2008 6th Annual IEEE International Conference on Pervasive Computing and Communications. Piscataway， NJ： IEEE， 2008： 110-116.

[8]     李军怀， 贾金朋， 王怀军，等. 基于信号强度差的RFID室内定位研究[J]. 计算机科学， 2015， 42（11）：154-157.（LI J H， JIA J P， WANG H J， et al. Research on SSDbased RFID indoor location method[J]. Computer Science， 2015， 42（11）：154-157.）

[9]     HOSSAIN A K M M， JIN Y， SOH W S， et al. SSD： a robust RF location fingerprint addressing mobile devices[J]. IEEE Transactions on Mobile Computing， 2013， 12（1）：65-77.

[10]    刘冰， 李文书. 基于余弦相似度的指纹匹配算法的室内定位方法[J]. 科技通报， 2017， 33（3）：198-202.（LIU B， LI W S. Indoor positioning method based on cosine similarity of fingerprint matching algorithm[J]. Bulletin of Science and Technology， 2017， 33（3）：198-202.）

[11]    陶峥， 王洪玉. 基于卡方距离改进的WLAN室内定位算法[J]. 计算机技术与发展， 2016， 26（9）：50-55.（TAO Z， WANG H Y. Improved WLAN localization algorithm based on Chisquare distance[J]. Computer Technology and Development， 2016， 26（9）：50-55.

[12]    张勇， 黄杰， 徐科宇. 基于PCALSSVR算法的WLAN室内定位方法[J]. 仪器仪表学报， 2015， 36（2）：408-414.（ZHANG Y， HUANG J， XU K Y. Indoor positioning algorithm for WLAN based on principal component analysis and least square support vector regression[J]. Chinese Journal of Scientific Instrument， 2015， 36（2）： 408-414.）

[13]    YUAN L， CHRISMANTO A R. Recurrent neural networks model for WiFibased indoor positioning system[C]// Proceedings of the 2017 International Conference on Smart Cities， Automation & Intelligent Computing Systems. Piscataway， NJ： IEEE， 2017：121-125.

[14]    崔斌，趙西安.一种基于传播模型和位置指纹的混合室内定位方法[J].测绘通报，2015（6）：35-38.（CUI B， ZHAO X A. A hybrid indoor positioning method based on propagation model and location fingerprint[J]. Bulletin of Surveying and Mapping， 2015（6）：35-38.）

[15]    TUTA J， JURIC M. A selfadaptive modelbased WiFi indoor localization method[J]. Sensors， 2016， 16（12）：2074.

[16]    莫云. 基于空间分区与降维技术的位置指纹室内定位方法研究[D]. 哈尔滨： 哈尔滨工业大学， 2016：54-69.（MO Y. Research on space division and dimension reduction techniques for fingerprinting indoor positioning method[D]. Harbin： Harbin Institute of Technology， 2016：54-69.）

[17]    SEONG J H， SEO D H. WiFi fingerprint using radio map model based on MDLP and Euclidean distance based on the Chi squared test[J]. Wireless Networks， 2018（2）：1-9.

[18]    谢红， 赵洪野. 基于卡方距离度量的改进KNN算法[J]. 应用科技， 2015， 42（1）：10-14.（XIE H， ZHAO H Y. An improved KNN algorithm based on Chisquare distance measure[J]. Applied Science and Technology， 2015， 42（1）：10-14.）