周非 夏鵬程

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

關(guān)鍵詞：室內(nèi)定位;位置指紋庫(kù);信號(hào)強(qiáng)度差;主成分分析;卡方距離

中圖分類號(hào)：TN929.5; TP393.1

文獻(xiàn)標(biāo)志碼：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.

英文關(guān)鍵詞Key words： indoor localization; location fingerprint database; Signal Strength Difference （SSD）; Principal Component Analysis （PCA）; ChiSquare Distance （CSD）

0 引言

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

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

4 結(jié)語

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

由于本文所提算法需要在離線階段進(jìn)行PCA降維計(jì)算，當(dāng)應(yīng)用場(chǎng)景中用于構(gòu)建指紋庫(kù)的AP數(shù)量較多時(shí)，會(huì)增加離線階段一定的計(jì)算成本，而且隨著時(shí)間的推移和定位環(huán)境的改變，原參考點(diǎn)采集到的RSS數(shù)據(jù)會(huì)發(fā)生變化，這勢(shì)必會(huì)影響已構(gòu)建完成的SSD位置指紋庫(kù)定位性能，所以如何對(duì)離線階段的算法進(jìn)一步優(yōu)化和更新SSD指紋庫(kù)將是下一步的工作重點(diǎn)。

參考文獻(xiàn) （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è)大學(xué)， 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的動(dòng)態(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空間建模與接收設(shè)備偏差研究[D]. 成都：西南交通大學(xué)， 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] ??? 李軍懷， 賈金朋， 王懷軍，等. 基于信號(hào)強(qiáng)度差的RFID室內(nèi)定位研究[J]. 計(jì)算機(jī)科學(xué)， 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]. 科技通報(bào)， 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] ?? 陶崢， 王洪玉. 基于卡方距離改進(jìn)的WLAN室內(nèi)定位算法[J]. 計(jì)算機(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]. 儀器儀表學(xué)報(bào)， 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].測(cè)繪通報(bào)，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è)大學(xué)， 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] ?? 謝紅， 趙洪野. 基于卡方距離度量的改進(jìn)KNN算法[J]. 應(yīng)用科技， 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.）