基于K-means聚類的藍牙室內定位算法研究

余曄

(重慶市勘測院，重慶 401121)

1 引 言

隨著經濟社會的發展，人們對位置信息的需求越來越多。同時，現階段人們的生產生活大多數都是在室內環境下進行的，因此室內定位技術也越來越重要[1]。相比于室外衛星定位，例如中國的北斗以及美國的GPS，在室內環境下由于建筑物的遮擋，衛星信號衰減嚴重，因此在室內環境下難以利用衛星信號進行定位[2]。室內定位技術作為衛星定位的補充，旨在解決室內環境下位置信息計算的問題。由于現階段人們的生產生活主要集中在室內環境下，人們對室內位置信息的需求越來越多，室內定位技術越來越得到人們的重視。與此同時，室內定位技術對智能家居、智慧城市、智慧醫療以及智慧工廠都有著重要的作用[3，4]。

近幾年來，室內定位技術得到了快速發展，出現了許多新的定位技術。總的來說，現有的室內定位技術主要包括：①基于信號強度(Received Signal Strength，RSS)的定位技術[5]；②基于到達角(Angle of Arrival，AOA)的定位技術[6]；③基于到達時間(Time of Arrival，TOA)的定位技術[7]。對于AOA的定位技術而言，基站需要使用陣列天線對多徑信號進行分辨，然后利用直達路徑進行定位，同時基站通道之間的幅度和相位誤差需要人工校正，因此基于AOA的室內定位技術有著極大的不便。基于TOA的定位技術則需要精確的時鐘同步，對于米級的定位精度則需要納秒級別的時間同步精度，那么對于現有的商用設備有著很高的要求。如果使用高精度的時鐘，則系統的成本將會很高，因此基于TOA的定位技術很難得到實際應用。相較而言，基于RSS的定位技術則具有成本低、通用性強的優點，RSS不需要特殊的硬件設備且采集較為容易，因此基于RSS的定位技術仍然是較為理想的選擇。同時，由于藍牙信號傳輸距離短、區域性強，能夠獲得較好的定位精度。

基于此，本文提出了一種基于K-means聚類的藍牙指紋定位算法。為減小指紋數據庫中奇異數據點，提出了利用聚類算法對指紋數據庫進行劃分，將每個類的中心點以及對應所屬類的指紋數據劃分為不同的區域。在線定位時，計算采集的RSS序列與各個類中心的歐式距離，將其劃分到距離最近的類中；并在對應的子區域內采用加權k-最鄰近(Weight K-Nearest Neighbor，WKNN)對目標進行定位；最后，實驗結果表明利用劃分區域的方法能夠有效地提高定位精度。

2 藍牙指紋定位原理

由于低功耗藍牙4.0的廣泛使用，使得使用藍牙信號的指紋定位系統具有成本低、部署方便、操作簡單的優點。與此同時，隨著智能手機的普及及手機廠商對藍牙標準的大力支持與推廣，使得藍牙指紋定位技術有著更好的應用前景。指紋定位技術是一種場景匹配技術[8]。在室內環境下信號傳播具有多徑效應，因此每個位置點的多徑分量不同，由于多徑的不同造成了接收節點RSS存在差異，這種差異代表了每個位置的差異性即“指紋特性”。對于目標定位就是要與每個位置的RSS進行匹配，從而將相似度最大的指紋點作為估計的位置。

圖1 室內指紋網格示意圖

指紋定位方法通常有兩個階段：離線階段和在線階段。在離線階段建立每個位置點與RSS的映射即指紋數據庫。在如圖1所示的室內環境下，可以對其劃分為M個網格點稱為參考點，定位區域內使用N個節點。在每個參考點上對來自N個節點的RSS進行采集。從每個參考點上的指紋RSS一個N維向量，同時還包括了對應參考點的坐標，RSS指紋數據庫可以利用矩陣來表示為：

(1)

圖2為在其中一個測試點采集到的不同基站的RSS分布，表1為具體的統計數值。從圖2可以發現，在同一個測試點上接收到的不同藍牙基站的RSS分布狀況有著明顯的差異；從表1可以看出，同一物理位置上不同基站的RSS統計數值也呈現著差異。因此，利用不同位置上的不同藍牙基站的RSS的差異來表征不同的物理位置，將信號特性與物理位置進行映射并存儲就構成了指紋數據庫。

圖2不同藍牙基站RSS概率分布

不同基站的RSS數值統計 表1

實際在數據采集的過程中會引入噪聲，這些噪聲會使得采集的RSS產生波動，影響最終的定位結果，因此在建立指紋數據庫之前需要對采集到的RSS數據進行預處理。RSS預處理主要目的是消除奇異值、噪聲等因素對參考點處測試數據的影響，可以采用均值濾波取同一參考點處多次采集數據的平均值作為該參考點信號強度的估計值，計算公式如下：

(2)

其中，K為采樣次數。在線階段，可以對實時采集到的RSS序列與每個指紋點進行相似度計算進而實現定位，相似度常用的就是在RSS信號空間的歐幾里得距離，因此相似度越高RSS空間中的兩個向量距離就越近。

3 基于K-means的指紋庫劃分

在室內環境下由于噪聲及環境的影響，會使得指紋庫中存在異常指紋點，進而會產生較大的定位誤差，因此數據庫建立之后可以利用聚類算法對指紋庫進行聚類，劃分為不同的子區域，然后對每個子區域的異常離群點進行剔除。與此同時，對指紋庫進行聚類劃分以后還可以減小查詢計算量，同時減小大的定位誤差點。K-means算法通過不斷迭代來實現聚類[9]，當算法滿足收斂條件或者達到最大迭代次數則停止迭代，輸出聚類中心以及所屬類數據點。對于指紋數據庫D={RSSi，i=1，…，N}，就是要找到D的一個劃分使得目標函數最小，目標函數為：

(3)

其中，K為類的個數且需要預先進行指定，Xn為第n個類中心。算法主要工作流程如表2所示。

K-means指紋聚類算法 表2

然而，聚類算法中類的個數需要預先指點。本文首先在定位區域內間隔采集定位點，然后利用定位點在2～N范圍內的整數進行遍歷，選取統計誤差最小的整數作為類個數。

4 基于位置加權的定位算法

對于相似度計算最為常用的是歐式距離，主要原因是歐式距離計算簡單且物理意義明確，采樣點i與參考點j在RSS空間的歐式距離為：

(4)

(5)

其中，(xj，yj)中第j個最鄰近的參考點坐標，(x，y)為最終定位坐標，該方法為k鄰近算法(K-Nearest Neighborhood，KNN)[11]。除此之外，還可以對k個參考點坐標進行加權，稱為WKNN。本文提出使用多次定位結果中k個坐標的方差作為權重，具體方法如下：

(6)

其中，wj為第j個最鄰近的參考點坐標權重，計算方法為：

(7)

其中，σj為參考點j在同一位置t次定位后坐標方差，該方差為二維位置分量方差和。本文實驗定位時數據采集 30 s，然后利用1秒鐘的數據進行一次定位，則一次定位可以獲得30次定位結果，然后利用多次的定位結果求取WKNN的定位結果。

5 實驗結果與分析

在圖1所示的室內環境下進行數據采集，本文選用CC2540作為藍牙基站芯片。藍牙基站作為定位節點主要功能是發送藍牙廣播報文，本文中設置藍牙廣播報文的發送頻率為 10 Hz。本文定位終端為智能手機，通過Android操作系統中提供的藍牙掃描模塊進行RSS測量值的獲取，Android操作系統在4.3及以后版本開始支持藍牙4.0。將實驗環境中的平面均勻地劃分為若干個正方形網格，將參考點選在網格的中心。

5.1 網格大小影響分析

實驗中分別將網格的邊長選為0.4 m、0.8 m、1.2 m、1.6 m、2.0 m來分析不同網格尺寸對定位精度的影響，同時選取最優的網格尺寸。按照事先標點好的網格點進行數據采集，對每個參考點采集2分鐘的RSS數據，然后將采集到的數據進行預處理。隨機采集測試點利用KNN算法進行位置估計，最后計算定位誤差，圖3為選取不同網格尺寸的定位精度CDF圖。

圖3 不同網格尺寸的定位CDF圖

從圖3中可以看出，不同的網格尺寸對定位誤差有著較大的影響。隨著網格尺寸的增加定位誤差也隨之增加。當網格的尺寸在 0.4 m～1.2 m之間時定位誤差下降幅度較小，當超過 1.2 m后定位誤差增幅較大。網格尺寸為 0.4 m的中值誤差為 2.3 m，網格尺寸為 0.8 m的平均定位誤差為 2.6 m，網格尺寸為 1.2 m的中值誤差為 3.5 m，網格尺寸為 1.6 m的中值誤差為 4.4 m，網格尺寸為 2.0 m的中值誤差為 6.5 m。因此，在考慮指紋數據庫的建立時間以及定位精度，后續實驗選取網格尺寸為 0.8 m的指紋數據庫進行實驗分析。

5.2 藍牙節點數量影響分析

藍牙基站數量越多每個參考點上的指紋特性越豐富，同時基站數量越多對數據庫的采集時間以及系統成本都有影響，因此研究基站數量對定位精度的影響有著重要的意義。在選定網格尺寸為 0.8 m的前提下，將區域內的藍牙基站數量從7個減少到4個，然后隨機采集測試點利用KNN算法計算定位誤差，圖4為不同藍牙基站數量下的定位誤差CDF圖。

從圖4中可以看出，當藍牙基站的數量增加定位精度隨之提高，當藍牙基站的數量從3個提高到4個時定位精度提升很大，當基站數量從4提高到6個時定位精度提升不大。可以發現3個基站的中值誤差為 6.5 m，4個基站的中值誤差為 4.4 m，5個基站的中值誤差為 3.2 m，6個的中值誤差為 2.3 m。因此，在實驗區域內選擇6個基站進行后續的測試與分析。

圖4 不同藍牙基站數量定位精度CDF圖

5.3 K-means指紋庫劃分影響分析

為了驗證有指紋數據庫劃分對定位精度的提升，在測試區域內隨機選擇測試點。通過3種傳統算法(NN、KNN和WKNN)與指紋劃分后的定位進行對比。四種基于不同匹配算法的指紋定位算法的定位CDF結果如圖5所示。

圖5 不同指紋定位算法定位結果對比圖

由圖5可知，基于K-Means指紋的藍牙定位算法的定位精度明顯高于傳統指紋定位算法。基于K-Means聚類的中值誤差為 2.01 m，而傳統指紋匹配算法的最優中值誤差(WKNN)為 2.35 m，特別是NN匹配算法的誤差數據中 10 m以上的誤差大于8%。

6 結 論

本文提出一種基于K-means聚類的藍牙室內定位算法，利用K-均值聚類對定位區域的指紋數據庫進行劃分得到不用區域的類中心；然后，在線定位時將接收到的藍牙信號強度與不同的類中心進行比較得到定位區域；最后，在匹配到的子區域內利用WKNN進行定位，其中WKNN中的權重選取是利用多次定位結果的方差決定。實驗結果表明利用區域劃分和基于位置方差加權的WKNN算法可以有效提高定位精度。