韓非 千博

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

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

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

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

以上3種基于藍(lán)牙的典型室內(nèi)算法的定位精度還不足以滿足室內(nèi)環(huán)境下基于位置服務(wù)的各種需求。本文針對基于指紋標(biāo)定方法中常用的KNN算法進(jìn)行了改進(jìn)，提出了一種W-KNN算法。在最終確定定位點位置時，使用定位點RSSI與參考點RSSI的歐氏距離倒數(shù)的歸一化值作為權(quán)值。仿真實驗結(jié)果表明，與傳統(tǒng)基于鄰近算法（ K-Nearest Neighbor，KNN）的指紋標(biāo)定室內(nèi)定位算法相比，定位精度提升了37. 6%。同時，本文還提出了一種空間過濾的算法，將與定位點信號強度差距較大的參考節(jié)點進(jìn)行濾除，將本文提出的W-KNN計算速度提升了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ū)域的形狀為長10.6 m，寬6m的矩形，在室內(nèi)的4個角以及對角線交點上分別放置一個iBeacon節(jié)點，iBeacon使用的是藍(lán)牙4.0標(biāo)準(zhǔn)規(guī)范其覆蓋范圍達(dá)到100 m以上，能夠保證每個節(jié)點的信號都能覆蓋整個室內(nèi)定位區(qū)域。綜合考慮定位精度和資源開銷，在室內(nèi)定位區(qū)域范圍內(nèi)每隔0.6 m設(shè)置一個參考節(jié)點，用于離線指紋庫的建立。

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

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

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

2.1離線階段指紋庫的建立

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

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

2.2線上實時定位階段

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

hi=[bi b2 …bj …bn]

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

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

2.3空間濾波算法

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

首先對每一個參考點設(shè)置空間濾波閾值。

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

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

i表示第i個參考點，j表示第l個Beacon基站。

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

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

3算法仿真

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

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

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

4結(jié)語

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

[參考文獻(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.