一種基于iBeacon改進(jìn)型KNN位置指紋室內(nèi)定位算法

韓非 千博

摘 要：iBeacon有著體積小、功耗低、覆蓋范圍廣等特點(diǎn)，因此其在室內(nèi)定位領(lǐng)域有著非常明顯的優(yōu)勢(shì)。文章提出了一種基于iBeacon的以定位點(diǎn)RSSI與參考點(diǎn)RSSI的歐氏距離倒數(shù)的歸一化值作為權(quán)值的改進(jìn)型KNN算法，同時(shí)提出了一種空間濾波算法，提升了算法效率。仿真實(shí)驗(yàn)結(jié)果表明，文章提出的改進(jìn)型KNN算法在定位精度上相比原KNN算法提升了43.6%。此外，文章提出的空間濾波算法提高算法的運(yùn)算速度約34%，使得在保證定位精度的同時(shí)，保證了定位的實(shí)時(shí)性。

關(guān)鍵詞：iBeacon；室內(nèi)定位；K近鄰算法；位置指紋

室內(nèi)定位技術(shù)被稱(chēng)為定位領(lǐng)域的“最后一公里”問(wèn)題，有著非常廣泛的應(yīng)用前景，高精度的室內(nèi)定位技術(shù)成為了近年來(lái)的熱點(diǎn)問(wèn)題。藍(lán)牙是一種短距離的無(wú)線(xiàn)通信技術(shù)，利用短距離、低成本的無(wú)線(xiàn)連接替代電纜連接，從而為現(xiàn)存的數(shù)據(jù)網(wǎng)絡(luò)和小型的外圍設(shè)備接口提供統(tǒng)一的連接[1]。目前，藍(lán)牙技術(shù)已經(jīng)在日常生活中隨處可見(jiàn)了，已經(jīng)被廣泛應(yīng)用到了手機(jī)、平板電腦、筆記本電腦、藍(lán)牙耳機(jī)等各種終端上。本文采用了使用藍(lán)牙4.0規(guī)范的iBeacon作為定位的節(jié)點(diǎn)。iBeacon有著體積小、功耗低、覆蓋范圍廣等特點(diǎn)，因此，其在室內(nèi)定位領(lǐng)域有著非常明顯的優(yōu)勢(shì)。

自從藍(lán)牙標(biāo)準(zhǔn)規(guī)范頒布以來(lái)，利用藍(lán)牙技術(shù)實(shí)現(xiàn)室內(nèi)定位的研究一直都在進(jìn)行，并且提出了很多基于藍(lán)牙的定位方法，比較典型的有基于路徑損耗模型的方法[2]、基于Cell-ID的方法[3]和基于指紋標(biāo)定的方法[4]等?；谒{(lán)牙的典型室內(nèi)定位算法對(duì)比如表1所示。

以上3種基于藍(lán)牙的典型室內(nèi)算法的定位精度還不足以滿(mǎn)足室內(nèi)環(huán)境下基于位置服務(wù)的各種需求。本文針對(duì)基于指紋標(biāo)定方法中常用的KNN算法進(jìn)行了改進(jìn)，提出了一種W-KNN算法。在最終確定定位點(diǎn)位置時(shí)，使用定位點(diǎn)RSSI與參考點(diǎn)RSSI的歐氏距離倒數(shù)的歸一化值作為權(quán)值。仿真實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)基于鄰近算法（ K-Nearest Neighbor，KNN）的指紋標(biāo)定室內(nèi)定位算法相比，定位精度提升了37. 6%。同時(shí)，本文還提出了一種空間過(guò)濾的算法，將與定位點(diǎn)信號(hào)強(qiáng)度差距較大的參考節(jié)點(diǎn)進(jìn)行濾除，將本文提出的W-KNN計(jì)算速度提升了34.5%。

1 基于iBeacon的位置指紋室內(nèi)定位技術(shù)方案

綜合考慮藍(lán)牙4.0標(biāo)準(zhǔn)的覆蓋范圍和一般樓房室內(nèi)的基本布局和形狀，本文采用了如圖1所示的室內(nèi)定位拓?fù)浣Y(jié)構(gòu)。本文中進(jìn)行室內(nèi)定位區(qū)域的形狀為長(zhǎng)10.6 m，寬6m的矩形，在室內(nèi)的4個(gè)角以及對(duì)角線(xiàn)交點(diǎn)上分別放置一個(gè)iBeacon節(jié)點(diǎn)，iBeacon使用的是藍(lán)牙4.0標(biāo)準(zhǔn)規(guī)范其覆蓋范圍達(dá)到100 m以上，能夠保證每個(gè)節(jié)點(diǎn)的信號(hào)都能覆蓋整個(gè)室內(nèi)定位區(qū)域。綜合考慮定位精度和資源開(kāi)銷(xiāo)，在室內(nèi)定位區(qū)域范圍內(nèi)每隔0.6 m設(shè)置一個(gè)參考節(jié)點(diǎn)，用于離線(xiàn)指紋庫(kù)的建立。

位置指紋室內(nèi)定位算法的過(guò)程分為離線(xiàn)指紋庫(kù)的建立和在線(xiàn)實(shí)時(shí)定位兩個(gè)階段。離線(xiàn)階段：在參考節(jié)點(diǎn)出采集每個(gè)Beacon基站的接收信號(hào)強(qiáng)度指示數(shù)據(jù)，得到的數(shù)據(jù)結(jié)合參考點(diǎn)的坐標(biāo)信息組合成一組數(shù)據(jù)，作為這個(gè)參考點(diǎn)的指紋數(shù)據(jù)。按照相同的步驟采集其他參考點(diǎn)的指紋數(shù)據(jù)，建立指紋庫(kù)。在線(xiàn)定位階段：終端用戶(hù)在定位區(qū)域內(nèi)，實(shí)時(shí)接收每個(gè)iBeacon基站的接收的信號(hào)強(qiáng)度指示（Received SignalStrength Indication，RSSI）值，采用合適的匹配算法與指紋數(shù)據(jù)庫(kù)中的數(shù)據(jù)比較，得到用戶(hù)的位置估算坐標(biāo)，最終完成對(duì)手機(jī)客戶(hù)端位置的確定。

2 基于位置指紋的室內(nèi)定位改進(jìn)算法

通常在使用KNN算法進(jìn)行指紋比對(duì)和篩選時(shí)，選出K個(gè)臨近位置指紋后，將K個(gè)位置指紋的位置的均值作為最終的定位結(jié)果。這種計(jì)算方法忽略了K個(gè)位置指紋在最終位置計(jì)算中的貢獻(xiàn)度問(wèn)題。本文將終端實(shí)時(shí)定位到RSSI向量和KNN算法計(jì)算出的K個(gè)位置指紋的RSSI向量的歐式距離的倒數(shù)的歸一化值作為最終確定位置的權(quán)值。同時(shí)，提出了一種基于RSSI距離特征，簡(jiǎn)單且易于計(jì)算的參考點(diǎn)過(guò)濾算法，提升改進(jìn)型算法的計(jì)算速度。

2.1離線(xiàn)階段指紋庫(kù)的建立

室內(nèi)定位區(qū)域內(nèi)中選擇K個(gè)參考點(diǎn)，在每個(gè)參考點(diǎn)出采集信號(hào)覆蓋范圍內(nèi)的各個(gè)Beacon基站的RSSI，并將該參考點(diǎn)的地理坐標(biāo)一起存入矩陣H：

其中：K為參考點(diǎn)的總個(gè)數(shù)；BKj為在參考點(diǎn)K處采集到第，個(gè)Beacon基站的RSSI；xk為參考點(diǎn)K處的橫坐標(biāo)；yK為參考點(diǎn)K處的縱坐標(biāo)。

2.2線(xiàn)上實(shí)時(shí)定位階段

用戶(hù)處于定位區(qū)域內(nèi)接收每個(gè)Beacon基站發(fā)出的RSSI并保存數(shù)據(jù)到向量h1：

hi=[bi b2 …bj …bn]

其中：b，為用戶(hù)所在位置處采集到第，個(gè)Beacon基站的接收信號(hào)強(qiáng)度指示。本文在在線(xiàn)匹配階段采用了經(jīng)典的K最近鄰匹配算法（ K-Nearest Neighbor，KNN）算法。KNN算法應(yīng)用在基于指紋庫(kù)的室內(nèi)定位算法中，位置指紋法可以看作是分類(lèi)或回歸問(wèn)題（特征是RSS向量，標(biāo)簽是位置），從數(shù)據(jù)中訓(xùn)練出一個(gè)從特征到標(biāo)簽的映射關(guān)系模型。在線(xiàn)階段采集的RSSI數(shù)據(jù)向量h1，針對(duì)每一個(gè)元素分別計(jì)算各元素與指紋庫(kù)中每個(gè)參考點(diǎn)的RSSI向量s1，s2…，SM的歐氏距離，并對(duì)歐氏距離進(jìn)行排序，選取較小的K個(gè)位置指紋（一個(gè)指紋是指一個(gè)參考點(diǎn)對(duì)應(yīng)一個(gè)RSSI向量）。將K個(gè)位置指紋的坐標(biāo)均值作為最終的定位結(jié)果。 直接使用位置指紋的坐標(biāo)的均值作為定位結(jié)果，雖然計(jì)算方便，但是卻沒(méi)有區(qū)分出KAI位置指紋在位置定位中的貢獻(xiàn)度。本文在選取K個(gè)位置指紋后，引入在線(xiàn)階段的RSSI數(shù)據(jù)向量h1與每個(gè)選取的位置指紋RSSI向量Sk的歐式距離的倒數(shù)作為計(jì)算最終定位位置的權(quán)重w：

其中，d為向量歐式距離的倒數(shù)。此處將權(quán)值做了歸一化處理。最終定位位置的計(jì)算公式為

2.3空間濾波算法

本文針對(duì)現(xiàn)有KNN匹配算法帶來(lái)的計(jì)算量較大進(jìn)行了改進(jìn)，縮短了定位時(shí)間，提高了定位的實(shí)時(shí)性?；诳臻g濾波的KNN算法的步驟如下：

首先對(duì)每一個(gè)參考點(diǎn)設(shè)置空間濾波閾值。

RSSI×（1- 10%）≤/3u≤RSSI×（1+10%）

其中：RSSL，表示在參考點(diǎn)i處收集到Beacon基站j處的RSSI；

i表示第i個(gè)參考點(diǎn)，j表示第l個(gè)Beacon基站。

（2）實(shí)時(shí)定位階段用戶(hù)收到的來(lái)自第，個(gè)Beacon基站的接收信號(hào)強(qiáng)度指示6與閡值比較。如果bj在此閾值范圍內(nèi)，將認(rèn)為此值沒(méi)有產(chǎn)生畸變，現(xiàn)場(chǎng)臨時(shí)環(huán)境變化少，則保留接收此基站RSSI的參考點(diǎn)。如果接收信號(hào)強(qiáng)度指示6，不在此閾值范圍內(nèi)，則說(shuō)明第j個(gè)Beacon基站此時(shí)受現(xiàn)場(chǎng)環(huán)境突變影響較大，即濾掉接收此基站RSSI的參考點(diǎn)，不參與后期的KNN處理。

經(jīng)過(guò)Beacon基站的過(guò)濾，由步驟（2）得，若第，個(gè)Beacon基站被過(guò)濾掉，則指紋庫(kù)中在任意一個(gè)參考點(diǎn)處采集到第，個(gè)Beacon基站的指紋數(shù)據(jù)也不參與KNN算法匹配。計(jì)算時(shí)將減少KXN個(gè)公式的平方計(jì)算。K是參考點(diǎn)的數(shù)量，N是被過(guò)濾掉的Beacon基站總數(shù)量。同時(shí)也是把相應(yīng)參考點(diǎn)向量中和這個(gè)基站有關(guān)的元素過(guò)濾掉，可避免實(shí)際場(chǎng)景中突發(fā)事件下各個(gè)Beacon基站產(chǎn)生的負(fù)面影響，濾掉沒(méi)有起到定位作用的基站。同時(shí)減少了KNN算法的計(jì)算量，加速數(shù)據(jù)的處理過(guò)程，縮短定位時(shí)間。現(xiàn)場(chǎng)環(huán)境突變條件下，提高了基于指紋庫(kù)室內(nèi)定位算法的定位精度和實(shí)時(shí)性。

3算法仿真

本文的仿真以驗(yàn)證算法為主，且只驗(yàn)證算法層面的有效性與合理性，使用MATLAB建立仿真環(huán)境平臺(tái)。設(shè)置室內(nèi)區(qū)域大小為6 mX10.8 m的實(shí)驗(yàn)室環(huán)境，部署5個(gè)Beacon基站分別位于實(shí)驗(yàn)室的4個(gè)角落和中心位置。5個(gè)Beacon基站分別為Beacon 9454 （0，0），Beacon～9556 （6，0），Beacon一9102（3， 5.4）， Beacon一7063 （0， 10.8）， Beacon一8C79 （6，10.8）。參考點(diǎn)的選擇要求是每隔0.6 m的長(zhǎng)度標(biāo)定一個(gè)參考點(diǎn)，共標(biāo)定180個(gè)參考點(diǎn)。分別在每個(gè)參考點(diǎn)處采集5個(gè)Beacon基站RSSI值。實(shí)驗(yàn)室實(shí)際場(chǎng)景下設(shè)置參考點(diǎn)和Beacon基站的分布，如圖l所示。

模擬實(shí)驗(yàn)室環(huán)境，在定位區(qū)域內(nèi)隨機(jī)分布一個(gè)待定位點(diǎn)，使用KNN算法、W-KNN算法、基于空間濾波的WKNN匹配算法進(jìn)行100次仿真實(shí)驗(yàn)，結(jié)果如圖2所示。

基于空間濾波的改進(jìn)型KNN算法定位誤差如圖3所示。分析實(shí)驗(yàn)所得數(shù)據(jù)，基于空間濾波的改進(jìn)型KNN算法的平均定位誤差為0.101 0 m，相比傳統(tǒng)KNN算法定位精度提升了43.6%。同時(shí)，空間濾波WKNN算法運(yùn)算速度相比WKNN算法提升了約34%。

4結(jié)語(yǔ)

基于iBeacon平臺(tái)，本研究提出了一種精度高，實(shí)時(shí)性好的基于空間濾波的改進(jìn)型KNN算法。主要改進(jìn)了KNN中K近鄰對(duì)最終計(jì)算結(jié)果的貢獻(xiàn)度區(qū)分問(wèn)題，以及提升了算法的效率，增強(qiáng)了算法的實(shí)時(shí)性。本研究在Matlab2016平臺(tái)上驗(yàn)證了算法的有效性。仿真實(shí)驗(yàn)結(jié)果表明，本文提出的改進(jìn)型KNN算法在定位精度上相比原KNN算法提升了43.6%。此外，本文提出的空間濾波算法提高算法的運(yùn)算速度約34%，使得在保證定位精度的同時(shí)，保證了定位的實(shí)時(shí)性。

[參考文獻(xiàn)]

[1]BHAGWAT P.Bluetooth： technology for short-range wireless apps [J].IEEE Internet Computing， 2001 （3） ： 96-103.

[2]ANASTASI G. BANDELLONI R. CONTI M. et aI.Experimenting an indoor bluetooth-based positioning service[C].Distributed

Computing Systems Workshops. 2003. Proceedings. 23rd International Conference on. IEEE. 2003 ： 480-483.

[3]RODAS J， ESCUDERO C J. IGLESIA D LBayesian filtering for a bluetooth positioning system[C].Wireless Conununication Systems.

2008. ISWCS'08. IEEE International Symposium on. IEEE. 2008 ： 618-622.

[4]SUBHAN F. HASBULLAH H. ROZYYEV A. et al.lndoor positioning in bluetooth networks using fingerprinting and lateration

approach[C].lnformation Science and Applications （ ICISA ）， 2011 International Conference on. IEEE. 2011： 1-9.