高斯函數(shù)定權(quán)的改進KNN室內(nèi)定位方法

畢京學，甄 杰，汪云甲，劉笑笑

(1. 中國礦業(yè)大學，江蘇 徐州 221116； 2. 中國測繪科學研究院，北京 100830)

?

高斯函數(shù)定權(quán)的改進KNN室內(nèi)定位方法

畢京學1，甄 杰2，汪云甲1，劉笑笑1

(1. 中國礦業(yè)大學，江蘇 徐州 221116； 2. 中國測繪科學研究院，北京 100830)

室內(nèi)某些區(qū)域無線訪問接入點(AP)布設稀疏，以及信號指紋的時變特性等因素，均使得無線信號接收信號強度(RSSI)序列與射電地圖(radio map)相應RSSI序列完全相同成為可能，計算得到信號空間的歐氏距離為0或非常小。利用歐氏距離定權(quán)的加權(quán)質(zhì)心算法解算會出現(xiàn)錯誤，無法得到定位結(jié)果；取K個參考點坐標均值的KNN算法以1/K為權(quán)值，定位精度相對較低。本文提出了高斯函數(shù)定權(quán)的KNN定位算法，對K個最近鄰歐氏距離進行了標準化處理，利用高斯函數(shù)分配權(quán)值，得到加權(quán)坐標值。與KNN和WKNN算法的定位結(jié)果相比，該方法提高了魯棒性和定位精度。

信號接收強度；歐氏距離；高斯函數(shù)；定權(quán)；K最近鄰；室內(nèi)定位

室內(nèi)定位技術(shù)是基于位置服務的研究熱點，許多研究機構(gòu)、公司和大學利用紅外線[1]、超聲波[2]、射頻識別[3](radio frequency identification，RFID)、ZigBee[4]、無線局域網(wǎng)[5](wireless local area network，WLAN)、藍牙[6]、微機電系統(tǒng)(micro electro mechanical systems，MEMS)傳感器[7]、超寬帶[8](ultra-wideband，UWB)、地磁[9]、可見光通信[10]、計算機視覺[11]、偽衛(wèi)星[12](Pseudolites)等技術(shù)開展了大量研究工作，開發(fā)了相應的室內(nèi)定位系統(tǒng)，并結(jié)合文獻[13]總結(jié)了不同定位技術(shù)的定位精度，如圖1所示。

自微軟研究院推出基于WiFi技術(shù)的RADAR[14]室內(nèi)定位系統(tǒng)以來，基于WiFi接收信號強度室內(nèi)定位技術(shù)由于不需要添加額外設備，容易開展試驗，且方便推廣，在理論和商業(yè)應用方面取得了較大成果。其中，K最近鄰(K-nearest neighbor,KNN)算法由于算法簡單、易于實現(xiàn)被廣泛研究。在KNN定位算法的基礎上，有些研究人員對KNN算法在權(quán)值分配和自適應K值作了改進。Dudani[15]首先將加權(quán)投票機制引入KNN中，稱為距離加權(quán)KNN。Lionel[16]等在KNN算法的基礎上提出了K加權(quán)近鄰法(weighted K nearest neighbors，WKNN)，以待測點與參考點之間在信號空間的歐氏距離分配權(quán)重進行加權(quán)處理得到加權(quán)均值坐標，提高了定位精度。但是該算法中的K值固定不變，無法兼顧所有測試點的定位精度，Beomju[17]測試發(fā)現(xiàn)在KNN和WKNN算法中以K值取5時的定位結(jié)果最優(yōu)；同時，針對固定K值會引入實際距離偏離待定點較遠的參考點問題，提出了動態(tài)加權(quán)EWKNN算法，該算法設定了初始閾值，動態(tài)選擇K值，提高了定位精度[18]。陳國良[19]將聚類分析方法應用到指紋定位，有效縮短了計算時間；王磊[20]利用平均加權(quán)KNN算法與地圖約束相結(jié)合，提升了30%的定位精度；牛建偉[21]提出了屬性加權(quán)K近鄰算法，將無球訪問接點(access point,AP)之間的相關性用于權(quán)值分配上，在AP數(shù)量較多的情況下有較好的定位效果。但是忽略了歐氏距離很小或為0的情況，而且指紋庫幾何位置邊緣或參考點稀疏區(qū)域權(quán)值分配不合理。本文提出基于高斯函數(shù)定權(quán)的KNN室內(nèi)定位方法，對K個歐氏距離進行標準化處理，利用高斯函數(shù)分配權(quán)值，以提高定位精度。

圖1 已有室內(nèi)定位技術(shù)定位精度示意圖

1 KNN室內(nèi)定位

1.1 基于無線接收信號強度(RSSI)指紋匹配定位原理

RSSI(received signal strength indicator,RSSI)指紋匹配定位分離線(offline phase)與在線(online phase)兩個階段，如圖2所示。離線階段主要是信息采集和樣本訓練，利用參考點的已知位置數(shù)據(jù)和接收到的接入點的RSSI信號特征值(RSSI、MAC地址、最值、均值、方差、方向、概率等)建立位置—指紋數(shù)據(jù)庫，從而建立空間位置與RSSI序列的映射關系；在線定位過程則是利用接收到的目標點RSSI序列與位置指紋數(shù)據(jù)庫進行匹配，運用某一定位算法，解算出待定點的位置信息。

圖2 基于RSSI指紋匹配定位原理

1.2 KNN室內(nèi)定位

Bahl[14]等首次將KNN法應用到基于RSSI的室內(nèi)定位研究中，利用實測RSSI均值與位置指紋數(shù)據(jù)庫進行搜索匹配運算，計算出參考點與待測目標在信號空間(signal space，SS)中的距離，選擇K個最小信號空間距離對應的參考點坐標取均值作為當前待測目標的估計位置。

RSSI均值作為特征量，構(gòu)建位置指紋數(shù)據(jù)庫D=(Li,Fi)，i=1，2，…,n，n為參考點個數(shù)。其中，Li為第i個參考點的坐標向量，F(xiàn)i為第i個參考點的RSSI信號特征矩陣，mac為搜索到AP的硬件地址(medium access control，MAC)，μ為RSSI均值，由于AP布設、建筑物結(jié)構(gòu)的不同，不同參考點可搜索到的AP在名稱與個數(shù)上不一致，因此Fi應是變維矩陣。

(1)

以歐氏距離作為參考點與待測目標點相似性的衡量，歐氏距離越小，兩點越臨近。假設待測點掃描到m個AP且與第i個參考點的位置指紋庫中AP的MAC地址均一致，則歐氏距離計算公式為

(2)

(3)

2 高斯函數(shù)定權(quán)的KNN

提出的高斯函數(shù)定權(quán)KNN方法有以下幾個步驟：計算歐氏距離、降噪處理、標準化處理、高斯函數(shù)定權(quán)、加權(quán)均值。

2.1 降噪處理

利用指紋匹配定位原理可得到信號空間的歐氏距離di(i=1,2,…,n)，n為當前指紋庫的參考點個數(shù)，如果指紋庫是經(jīng)過聚類處理的，則n為聚類指紋庫中參考點的個數(shù)。由于移動終端掃描到的RSSI為隨機信號，因此計算得到的歐氏距離是隨機變量。假設歐氏距離服從正態(tài)分布，計算均值和中誤差的公式分別為

(4)

以2倍中誤差作為偶然誤差的允許誤差，剔除式(5)范圍內(nèi)的歐氏距離和參考點坐標，生成新的歐氏距離和參考點序列，并利用式(4)重新計算均值μd和中誤差σd。

(5)

2.2Z-score標準化和高斯函數(shù)定權(quán)

利用式(6)對K個近鄰歐氏距離進行Z-score標準化處理，其中j=1,2,…,K，則符合標準正態(tài)分布，利用高斯函數(shù)式(7)計算權(quán)值

(6)

(7)

2.3 加權(quán)均值

選取K個最近鄰歐氏距離對應的參考點，利用式(8)計算得到加權(quán)坐標均值

(8)

高斯函數(shù)定權(quán)的KNN定位算法偽代碼如下

(1) 計算掃描指紋到參考點的歐氏距離:

for i=1 to n

di=0

for j=1 to m

ifFingerPrinticontains mac

else

end

end

(2) 降噪處理(得到了n個歐氏距離序列):

for i=1 to n

從歐氏距離序列中刪除di，刪除對應參考點

end

對新的歐氏距離序列取均值和中誤差，得到K個最近鄰距離Dknn及對應坐標Pknn。

(3) 標準化及定權(quán)處理:

for i=1 to K

end

(4) 加權(quán)均值為

3 試驗測試

3.1 試驗描述

試驗場設置在北京市東直門內(nèi)北小街北京帝測科技有限公司，安裝有14個2.4 Hz/5 Hz雙頻AP，可以實現(xiàn)公司辦公區(qū)域內(nèi)信號全覆蓋，如圖3所示，黑色五角星代表部署的AP。利用自主開發(fā)的指紋采集軟件掃描并存儲數(shù)據(jù)，如圖4所示。由于含有辦公桌椅，并不是嚴格按照2 m間隔取點。在離線采樣階段，以1 s的頻率采集AP的RSSI，每次采集30 s，取其均值作為信號特征值存儲到指紋數(shù)據(jù)庫中，參考點共有150個。

圖3 試驗區(qū)域

圖4 指紋采集軟件

3.2 試驗結(jié)果與分析

在利用KNN指紋匹配法計算歐氏距離時，若指紋庫中無掃描到AP，將RSSI值設定為-95 dBm[22]參與計算。如圖5所示，在展覽區(qū)、辦公區(qū)A和B、會議室、休息區(qū)、總經(jīng)理辦公室等位置選取了20個測試點進行靜態(tài)測試，與指紋采集時朝向一致。設定K為5，分別利用KNN、WKNN與GWKNN算法計算，比較定位結(jié)果并進行分析。

圖5 定位誤差累計概率分布

從圖5中可以看出，GWKNN算法定位精度優(yōu)于3 m的概率約為74%，而WKNN和KNN定位精度優(yōu)于3 m分別為60%和40%；這是由于辦公區(qū)域內(nèi)布局復雜，含有桌椅等用品，同時，參考點分布不均勻，人員走動頻繁，定位結(jié)果表現(xiàn)較差。

從表1可以看出，3種算法定位誤差最大值均高于5.7 m，這是因為洗手間、會議室附近AP布設稀疏，采集參考點數(shù)目較少，計算過程中引入多余參考點增大了定位誤差；從定位誤差均值看來，GWKNN定位效果要比WKNN和KNN好。

表1 定位誤差對比 m

由此可知，本文提出的GWKNN算法相對于WKNN和KNN算法，盡管算法復雜度提高了，但無論在定位穩(wěn)定性還是在定位精度方面都有顯著提高。

4 結(jié) 語

本文提出了高斯函數(shù)定權(quán)的加權(quán)KNN室內(nèi)定位算法，該方法通過對歐氏距離進行降噪處理剔除允許誤差(2倍中誤差)外的歐氏距離和參考點，標準化處理后，利用高斯函數(shù)對K個最近鄰歐氏距離分配權(quán)重，加權(quán)取均值。與KNN和WKNN室內(nèi)定位算法相比，避免了直接利用歐氏距離定權(quán)的計算錯誤，提高了定位精度。試驗中K取值為5，指紋庫幾何位置邊緣或參考點稀疏區(qū)域會引入定位誤差，自適應K值室內(nèi)定位方法還需進一步研究。

[1] WANT R, HOPPER A, FALCAO V, et al. The Active Badge Location System[J]. ACM Transactions on Information Systems, 1992, 10(1): 91-102.

[2] PRIYANTHA N B, CHAKRABORTY A, BALAKRISH-NAN H. The Cricket Location-support System[C]∥Proceedings of the 6th Annual International Conference on Mobile Computing and Networking. [S.l.]: ACM, 2000: 32-43.

[3] CHAWLA K, MCFARLAND C, ROBINS G, et al. Real-time RFID Localization Using RSS[C]∥2013 International Conference on Localization and GNSS (ICL-GNSS). [S.l.]: IEEE, 2013: 1-6.

[4] SUGANO M, KAWAZOE T, OHTA Y, et al. Indoor Localization System Using RSSI Measurement of Wireless Sensor Network Based on ZigBee Standard[C]∥International Multi-conference on Wireless Optical Communications. Banff: IASTED/ACTA Press,2000.

[5] MAZUELAS S, BAHILLO A, LORENZO R M, et al. Robust Indoor Positioning Provided by Real-time RSSI Values in Unmodified WLAN Networks[J]. IEEE Journal of Selected Topics in Signal Processing, 2009, 3(5): 821-831.

[6] FELDMANN S, KYAMAKYA K, ZAPATER A, et al. An Indoor Bluetooth-Based Positioning System: Concept, Implementation and Experimental Evaluation[C]∥Proceedings of the International Conference on Wireless Networks. Las Vegas: [s.n.], 2003: 109-113.

[7] GLANZER G, BERNOULLI T, WIESSFLECKER T, et al. Semi-autonomous Indoor Positioning Using MEMS-based Inertial Measurement Units and Building Information[C]∥6th Workshop on Positioning Navigation and Communication, WPNC 2009. Hannover: IEEE, 2009: 135-139.

[8] ALAVI B, PAHLAVAN K. Modeling of the TOA-based Distance Measurement Error Using UWB Indoor Radio Measurements[J]. IEEE Communications Letters, 2006, 10(4): 275-277.

[9] INDOORATLAS L. Ambient magnetic field-based indoor location technology: Bringing the compass to the next level[J]. IndoorAtlas Ltd, 2012.

[10] ZHOU Z, KAVEHRAD M, DENG P. Indoor Positioning Algorithm Using Light-emitting Diode Visible Light Communications[J]. Optical Engineering, 2012, 51(8): 5009.

[11] WERNER M, KESSEL M, MAROUANE C. Indoor Po-sitioning Using Smartphone Camera[C]∥International Conference on Indoor Positioning Indoor Navigation. [S.l.]: IEEE, 2011: 1-6.

[12] BARNES J, RIZOS C, WANG J, et al. Locata: A New Positioning Technology for High Precision Indoor and Outdoor Positioning[J]. Journal of Chemical Physics, 2003, 118(15): 6717-6719.

[13] LIU H, DARABI H, BANERJEE P, et al. Survey of Wireless Indoor Positioning Techniques and Systems[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2007, 37(6): 1067-1080.

[14] BAHL P, PADMANABHAN V N. RADAR: An In-building RF-based User Location and Tracking System[C]∥ Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. [S.l.]: IEEE, 2000: 775-784.

[15] DUDANI S A. The Distance-weighted K-Nearest-Neighbor Rule[J]. IEEE Transactions on Systems, Man and Cybernetics, 1976, 6(4): 325-327.

[16] NI L M, LIU Y, LAU Y C, et al. LANDMARC: Indoor Location Sensing Using Active RFID[J]. Wireless Networks, 2004, 10(6): 701-710.

[17] SHIN B, LEE J H, LEE T, et al. Enhanced Weighted K-nearest Neighbor Algorithm for Indoor Wi-Fi Positioning Systems[C]∥2012 8th International Conference on Computing Technology and Information Management (ICCM). [S.l.]: IEEE, 2012: 574-577.

[18] 王培重, 鄭南山, 張言哲. 基于動態(tài) K 值及 AP MAC 地址篩選的室內(nèi)定位算法[J]. 計算機科學, 2016, 43(1): 163-165.

[19] 陳國良, 張言哲, 汪云甲, 等. WiFi-PDR 室內(nèi)組合定位的無跡卡爾曼濾波算法[J]. 測繪學報, 2015, 44(12): 1314-1321.

[20] 王磊, 周慧, 蔣國平, 等. 基于 WiFi 的自適應匹配預處理 WKNN 算法[J]. 信號處理, 2015, 31(9):1067-1074.

[21] 牛建偉,劉洋,盧邦輝,等.一種基于Wi-Fi信號指紋的樓宇內(nèi)定位算法[J].計算機研究與發(fā)展,2013,50(3):568-577.

[22] 楊凱, 郭英, 畢京學. 基于安卓平臺的室內(nèi)實時定位[J]. 測繪科學, 2015, 40(6): 125-128.

引文格式： 朱添翼，范強，杜漫飛.一種遙感圖像建筑物直線特征提取算法[J].測繪通報，2017(6)：36-39.DOI:10.13474/j.cnki.11-2246.2017.0185.

The Method of Enhanced Gaussian Function Weighted KNN Indoor Positioning

BI Jingxue1，ZHEN Jie2，WANG Yunjia1，LIU Xiaoxiao1

(1. China University of Mining and Technology, Xuzhou 221116, China; 2. Chinese Academy of Surveying and Mapping, Beijing 100830, China)

Because of less deployed APs in some indoor areas and signal fingerprint time-varying characteristics, it is possible for the currently scanning RSSI vector to be similar to corresponding RSSI sequence which is stored with location in radio map. In these cases, the calculated Euclidean distance is usually 0 or very small. Error will occur when the Euclidean distance is used for weight value in weighted centroid algorithm, and no result will be obtained. And KNN algorithm, which supposes the value 1/Kas weight, will get the average of coordinates ofKreference points along with relative low positioning accuracy. Therefore, Gaussian weighted KNN (GWKNN) localization algorithm is proposed: standardization processes forKnearest Euclidean distances were made, then corresponding weights were distributed by Gaussian function, at last, the weighted positioning result is obtained. Compared with the positioning results of KNN and WKNN algorithm, this positioning method can get higher robustness and positioning accuracy.

RSSI；Euclidean distance；Gaussian function；assign weights；KNN； indoor positioning

畢京學，甄杰，汪云甲,等.高斯函數(shù)定權(quán)的改進KNN室內(nèi)定位方法[J].測繪通報，2017(6)：9-12.

10.13474/j.cnki.11-2246.2017.0179.

2016-09-20 基金項目： 國家重點研發(fā)計劃(2016YFB0502102)；國家863計劃(2013AA12A201)；江蘇省普通高校學術(shù)學位研究生創(chuàng)新計劃(KYLX16_0544)

畢京學(1991—)，男，博士生，研究方向為室內(nèi)外無縫定位。E-mail:bjx1050@163.com

汪云甲。E-mail:wyj4139@cumt.edu.cn

P228

A

0494-0911(2017)06-0009-04