一種基于iBeacon改進型KNN位置指紋室內定位算法

韓非 千博

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

關鍵詞：iBeacon；室內定位；K近鄰算法；位置指紋

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

自從藍牙標準規范頒布以來，利用藍牙技術實現室內定位的研究一直都在進行，并且提出了很多基于藍牙的定位方法，比較典型的有基于路徑損耗模型的方法[2]、基于Cell-ID的方法[3]和基于指紋標定的方法[4]等。基于藍牙的典型室內定位算法對比如表1所示。

以上3種基于藍牙的典型室內算法的定位精度還不足以滿足室內環境下基于位置服務的各種需求。本文針對基于指紋標定方法中常用的KNN算法進行了改進，提出了一種W-KNN算法。在最終確定定位點位置時，使用定位點RSSI與參考點RSSI的歐氏距離倒數的歸一化值作為權值。仿真實驗結果表明，與傳統基于鄰近算法（ K-Nearest Neighbor，KNN）的指紋標定室內定位算法相比，定位精度提升了37. 6%。同時，本文還提出了一種空間過濾的算法，將與定位點信號強度差距較大的參考節點進行濾除，將本文提出的W-KNN計算速度提升了34.5%。

1 基于iBeacon的位置指紋室內定位技術方案

綜合考慮藍牙4.0標準的覆蓋范圍和一般樓房室內的基本布局和形狀，本文采用了如圖1所示的室內定位拓撲結構。本文中進行室內定位區域的形狀為長10.6 m，寬6m的矩形，在室內的4個角以及對角線交點上分別放置一個iBeacon節點，iBeacon使用的是藍牙4.0標準規范其覆蓋范圍達到100 m以上，能夠保證每個節點的信號都能覆蓋整個室內定位區域。綜合考慮定位精度和資源開銷，在室內定位區域范圍內每隔0.6 m設置一個參考節點，用于離線指紋庫的建立。

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

2 基于位置指紋的室內定位改進算法

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

2.1離線階段指紋庫的建立

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

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

2.2線上實時定位階段

用戶處于定位區域內接收每個Beacon基站發出的RSSI并保存數據到向量h1：

hi=[bi b2 …bj …bn]

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

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

2.3空間濾波算法

本文針對現有KNN匹配算法帶來的計算量較大進行了改進，縮短了定位時間，提高了定位的實時性。基于空間濾波的KNN算法的步驟如下：

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

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

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

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

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

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

3算法仿真

本文的仿真以驗證算法為主，且只驗證算法層面的有效性與合理性，使用MATLAB建立仿真環境平臺。設置室內區域大小為6 mX10.8 m的實驗室環境，部署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的長度標定一個參考點，共標定180個參考點。分別在每個參考點處采集5個Beacon基站RSSI值。實驗室實際場景下設置參考點和Beacon基站的分布，如圖l所示。

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

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

4結語

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

[參考文獻]

[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.