基于主成分分析和卡方距離的信號強度差指紋定位算法

周非 夏鵬程

摘 要：由于不同型號移動終端獲取的接收信號強度（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.）