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

周非 夏鵬程

摘 要：由于不同型號移動終端獲取的接收信號強度（RSS）存在明顯差異，傳統(tǒng)的基于RSS位置指紋庫的室內(nèi)定位算法定位穩(wěn)定性和精度不高，而現(xiàn)有的采用信號強度差（SSD）替代RSS構(gòu)建位置指紋庫的解決方案存在高數(shù)據(jù)維度、相關性冗余過高和K近鄰（KNN）算法本身定位精度不高的問題。針對上述問題，提出了一種基于主成分分析（PCA）和卡方距離（CSD）的SSD指紋定位算法，使用PCA算法進行SSD數(shù)據(jù)降維和相關性冗余消除，并使用CSD度量降維后特征量間的相對距離進行位置匹配。仿真實驗中，使用所提算法的SSD位置指紋庫定位誤差累積概率曲線高于原有RSS和SSD指紋庫;相比傳統(tǒng)的KNN算法和基于余弦相似度改進的KNN算法（COSKNN），所提算法的平均定位誤差、定位誤差方差均有明顯減小，時間開銷稍有增加。實驗結(jié)果表明，所提算法可以有效提升原有SSD指紋定位方法的定位穩(wěn)定性和定位精度，能夠滿足室內(nèi)定位的實時性需要。

關鍵詞：室內(nèi)定位;位置指紋庫;信號強度差;主成分分析;卡方距離

中圖分類號：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 引言

近幾年，隨著移動通信技術(shù)的飛速發(fā)展和無線網(wǎng)絡的全面普及，室內(nèi)定位技術(shù)越來越受到人們的關注。隨著微軟公司提出首個基于位置指紋庫的室內(nèi)定位系統(tǒng)RADAR[1]，越來越多的研究者采用基于接收信號強度（Received Signal Strength， RSS）的位置指紋定位方法[2]，但是傳統(tǒng)的指紋定位方法存在定位精度不高和定位穩(wěn)定性較差等問題[3-4]。

基于位置指紋庫的WLAN（Wireless Local Area Network）室內(nèi)定位方法通常分為離線和在線兩個階段，利用在線階段設備采集的RSS信號與離線階段構(gòu)建的位置指紋庫進行匹配來估算用戶位置，但是當在線階段用于獲取RSS信號值的采集終端與離線階段型號不一致時，兩者采集的RSS信號會產(chǎn)生明顯的差異，從而導致定位結(jié)果與實際位置產(chǎn)生較大的偏差。為了解決此類問題，文獻[5]采用線上實時調(diào)整兩種設備RSS信號差異的方法，但該方法計算量大，定位耗時較長;文獻[6]提出不同設備之間RSS信號變化特征存在線性關系，可以通過線性回歸模型校正異構(gòu)設備的RSS差異，但是為各種不同型號的設備建立線性關系模型需要耗費大量的人力和物力;文獻[7]提出一種利用對數(shù)函數(shù)的方法，該方法根據(jù)對數(shù)函數(shù)的單調(diào)特性，將RSS值轉(zhuǎn)換為對數(shù)函數(shù)值，并以此構(gòu)建新的位置指紋數(shù)據(jù)庫，通過仿真實驗驗證此方法可以減小異構(gòu)設備環(huán)境下RSS數(shù)據(jù)的波動性，但是映射后的未經(jīng)處理的數(shù)據(jù)在異構(gòu)設備上仍有一定的差異性，因此在進行位置匹配時會降低定位精度;文獻[8]提出采用信號強度差（Signal Strength Difference， SSD）來構(gòu)建位置指紋庫的方法，該方法是不用校正的穩(wěn)健指紋方法，但是文獻[8]并沒有考慮到SSD代替RSS產(chǎn)生的數(shù)據(jù)量增加和相關性冗余問題; 文獻[9]同樣采用SSD構(gòu)建位置指紋庫，直接提取SSD數(shù)據(jù)有效成分，并未作數(shù)據(jù)處理，因此當在線定位階段的接收設備與離線采集設備相同時，該方法和RSS指紋庫相比反而會降低定位精度。除了異構(gòu)設備RSS信號差異性的問題，傳統(tǒng)的指紋定位方法采用K近鄰（KNearest Neighbors， KNN）算法作為匹配算法，該算法定位精度不高。針對此問題，有學者提出使用相似度度量改進歐氏距離度量的方法，如：文獻[10]提出使用余弦相似度改進傳統(tǒng)的KNN算法，該方法在一定程度上提高了定位精度;文獻[11]提出使用卡方距離（ChiSquare Distance， CSD）改進的KNN算法進行在線階段的位置匹配，該方法采用卡方距離衡量RSS數(shù)據(jù)特征量的相關程度，提高了定位精度。還有學者提出使用監(jiān)督學習的方法建立在線定位模型：文獻[12]采用支持向量機回歸算法估算用戶位置，該方法可以實現(xiàn)較精確的定位;文獻[13]提出使用循環(huán)神經(jīng)網(wǎng)絡訓練離線采集的RSS數(shù)據(jù)以進行位置匹配，但是該方法需要大量的訓練樣本。類似上述監(jiān)督學習的方法容易產(chǎn)生過擬合，因此泛化能力不強，無法適應多變的應用場景。

4 結(jié)語

本文提出了基于PCA和CSD的SSD指紋定位算法，使用PCA對SSD數(shù)據(jù)進行降維和消除相關性冗余，同時考慮到降維后數(shù)據(jù)特征量與原數(shù)據(jù)變化較大，使用卡方距離度量降維后SSD數(shù)據(jù)樣本間特征量的相對距離以實現(xiàn)位置匹配。仿真實驗結(jié)果表明，該算法提升了原有RSS和SSD指紋庫的定位穩(wěn)定性和定位精度，且可以滿足室內(nèi)定位的實時性需要。

由于本文所提算法需要在離線階段進行PCA降維計算，當應用場景中用于構(gòu)建指紋庫的AP數(shù)量較多時，會增加離線階段一定的計算成本，而且隨著時間的推移和定位環(huán)境的改變，原參考點采集到的RSS數(shù)據(jù)會發(fā)生變化，這勢必會影響已構(gòu)建完成的SSD位置指紋庫定位性能，所以如何對離線階段的算法進一步優(yōu)化和更新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室內(nèi)定位技術(shù)研究[D]. 哈爾濱： 哈爾濱工業(yè)大學， 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的動態(tài)室內(nèi)定位方法研究[J]. 傳感器與微系統(tǒng)， 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] ??? 王敬彬. 室內(nèi)定位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室內(nèi)定位研究[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] ?? 劉冰， 李文書. 基于余弦相似度的指紋匹配算法的室內(nèi)定位方法[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室內(nèi)定位算法[J]. 計算機技術(shù)與發(fā)展， 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室內(nèi)定位方法[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] ?? 崔斌，趙西安.一種基于傳播模型和位置指紋的混合室內(nèi)定位方法[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] ?? 莫云. 基于空間分區(qū)與降維技術(shù)的位置指紋室內(nèi)定位方法研究[D]. 哈爾濱： 哈爾濱工業(yè)大學， 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.）