畢京學(xué)，甄 杰，汪云甲，劉笑笑

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

?

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

畢京學(xué)1，甄 杰2，汪云甲1，劉笑笑1

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

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

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

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

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

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

1 KNN室內(nèi)定位

1.1 基于無(wú)線接收信號(hào)強(qiáng)度(RSSI)指紋匹配定位原理

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

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

1.2 KNN室內(nèi)定位

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

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

(1)

以歐氏距離作為參考點(diǎn)與待測(cè)目標(biāo)點(diǎn)相似性的衡量，歐氏距離越小，兩點(diǎn)越臨近。假設(shè)待測(cè)點(diǎn)掃描到m個(gè)AP且與第i個(gè)參考點(diǎn)的位置指紋庫(kù)中AP的MAC地址均一致，則歐氏距離計(jì)算公式為

(2)

(3)

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

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

2.1 降噪處理

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

(4)

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

(5)

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

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

(6)

(7)

2.3 加權(quán)均值

選取K個(gè)最近鄰歐氏距離對(duì)應(yīng)的參考點(diǎn)，利用式(8)計(jì)算得到加權(quán)坐標(biāo)均值

(8)

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

(1) 計(jì)算掃描指紋到參考點(diǎn)的歐氏距離:

for i=1 to n

di=0

for j=1 to m

ifFingerPrinticontains mac

else

end

end

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

for i=1 to n

從歐氏距離序列中刪除di，刪除對(duì)應(yīng)參考點(diǎn)

end

對(duì)新的歐氏距離序列取均值和中誤差，得到K個(gè)最近鄰距離Dknn及對(duì)應(yīng)坐標(biāo)Pknn。

(3) 標(biāo)準(zhǔn)化及定權(quán)處理:

for i=1 to K

end

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

3 試驗(yàn)測(cè)試

3.1 試驗(yàn)描述

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

圖3 試驗(yàn)區(qū)域

圖4 指紋采集軟件

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

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

圖5 定位誤差累計(jì)概率分布

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

從表1可以看出，3種算法定位誤差最大值均高于5.7 m，這是因?yàn)橄词珠g、會(huì)議室附近AP布設(shè)稀疏，采集參考點(diǎn)數(shù)目較少，計(jì)算過(guò)程中引入多余參考點(diǎn)增大了定位誤差；從定位誤差均值看來(lái)，GWKNN定位效果要比WKNN和KNN好。

表1 定位誤差對(duì)比 m

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

4 結(jié) 語(yǔ)

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

[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] 王培重, 鄭南山, 張言哲. 基于動(dòng)態(tài) K 值及 AP MAC 地址篩選的室內(nèi)定位算法[J]. 計(jì)算機(jī)科學(xué), 2016, 43(1): 163-165.

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

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

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

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

引文格式： 朱添翼，范強(qiáng)，杜漫飛.一種遙感圖像建筑物直線特征提取算法[J].測(cè)繪通報(bào)，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

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

10.13474/j.cnki.11-2246.2017.0179.

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

畢京學(xué)(1991—)，男，博士生，研究方向?yàn)槭覂?nèi)外無(wú)縫定位。E-mail:bjx1050@163.com

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

P228

A

0494-0911(2017)06-0009-04