基于藍牙信標的k-means指紋定位算法研究

重慶郵電大學 蔡云騏

基于藍牙信標的k-means指紋定位算法研究

重慶郵電大學 蔡云騏

指紋定位技術是室內定位技術中的一個熱點。相較與基于wifi的指紋定位方法，藍牙信標設備體積較小，成本低，易于布置。傳統的knn指紋定位方法有計算量大，定位精度不高等缺陷。本文提出了一種基于k-means的指紋定位算法，先對指紋庫進行聚類并找到中心點，通過比較未知目標和中心點歐式距離確定未知目標屬于的類，然后在該類中對未知目標定位。最后在Android平臺上進行了實際測試，測試結果表明該算法能提高定位精度并縮短定位時間。

藍牙信標；k-means；指紋定位；聚類

1 室內定位技術

自上世紀末以來，基于位置的服務[1-3]（Location Based Services,LBS）迅猛發展，成為了人們日常生活中必不可少的一部分。而伴隨著小型智能移動終端的大規模普及，使得LBS有了更為廣闊的發展空間。而LBS的核心是定位技術。GPS定位系統，北斗衛星定位系統等成熟的定位系統已實現了覆蓋范圍大、精度較高的室外定位。而在室內定位中，由于極為復雜的室內環境因素，GPS信號會受到極大干擾，基本無法利用GPS定位系統實現室內定位[4]。

目前常用的室內定位方法除了指紋定位算發還有時間到達法[5]（TOA），時間到達差法[6]（TDOA），信號強度測距法[6]（RSSI），到達角度差法[8]（AOA）等，這幾種方法需要建立信號傳播模型并對其中的參數進行估計，而復雜的室內環境使信號的多徑傳播產生反射和折射，很難對其中的參數進行準確的估計，從而使這些方法的定位精度不高。而基于信號強度的指紋算法作為臨近關系定位技術的一種，在室內定位應用中由于其定位精度高而被廣泛使用[9]。

圖1 藍牙信標指紋定位圖原理

2 基于藍牙信標的指紋定位技術

2.1 藍牙信標指紋定位原理

基于無線信號指紋的定位技術是當前室內定位技術研究的重點。信號的多徑傳播對環境具有依賴性，呈現出非常強的特殊性,對于每個位置而言，該位置上信道的多徑結構是惟一的,終端發射的無線電波經過反射和折射，產生與周圍環境密切相關的特定模式的多徑信號，這樣的多徑特征可以認為是該位置的“指紋”。

基于藍牙信標的指紋定位就是在一個大區域布置n個藍牙信標，在某一位置記錄n個藍牙信標的信號強度（rssi）作為其指紋數據，這樣就可以在大區域得到m個指紋點作并建立指紋數據庫，再通過指紋定位算法對未知目標進行定位（見圖1）。

相較與基于wifi的指紋定位，采用低功耗藍牙4.0標準的室內定位方法具有成本低、部署、方案簡單、響應速度快等技術特點，加之手機設備廠商對藍牙標準規范的大力推廣，因而具有更好的發展前景[6]。

2.2 信號強度指紋定位算法

信號強度指紋算法指是目前最常用的指紋定位算法，它是基于室內環境復雜，信號反射折射所形成的在不同位置形成的不同的信號強度信息而提出的一套算法，利用已建立的指紋庫信息，通過一定的推理運算得到位置目標的近似位置。主要算法有最鄰近法法（NN）和K近鄰法（KNN）。

2．2．1 最鄰近法（NN，Nearest Neighborhood）

最鄰近法是最簡單的算法，首先確定參考節點個數并建立指紋數據庫，設參考節點有n個，用Fi表示第i個指紋點收到n個參考節點的信號強度，那么某個指紋，這樣就建立了指紋庫。然后在某未知目標得到n個參考節點的信號強度，即，通過下式計算S與Fi的距離Di，找到與S距離最小的那個指紋Fm，將Fm的坐標作為未知目標的定位結果。

式中Sj表示位置目標受到第j個參考節點的信號強度，fij表示第i個指紋點收到第j個參考節點的信號強度，n即為參考節點總個數，當q=1代表曼哈頓距離，q=2代表歐幾里得距離。q的取值不是固定的，可以根據具體情況來取q的值。

2．2．2 K鄰近法（KNN，K Nearest Neighborhood）

K鄰近法是在最鄰近法的基礎上做出的改進。K鄰近法不再是取與S距離最近的那個指紋點的坐標作為最終定位結果，而是取與S距離最近的K個指紋點，計算這K個指紋點的平均坐標(x,y)作為最終定位結果，并在計算取q=2即取歐氏距離，如下式：

找到K個最近指紋點后：

在計算中一般取K=3，即找到三個最近指紋點用它們的三角質心作為最終定位結果。

3 kNN指紋定位法

傳統的k均值指紋定位方法可以分為以下兩個階段。

第一階段為訓練/離線階段，在目標區域內采集n個指紋點建立指紋庫，每個指紋點到5個藍牙信標的信號并得到一個5維向量作為其指紋信息。

圖2 kNN指紋定位法原理圖

4 k-means指紋定位法

針對以上傳統knn指紋定位法的不足，本文提出了一種基于k-means聚類算法的指紋定位方法。

4.1 k-means聚類算法

K-means聚類算法是基于劃分的聚類方法，一般常見的做法是同時提取N種特征，將它們放在一起組成一個N維向量，從而得到一個從原始數據集合到N維向量空間的映射，通過不斷的迭代來實現聚類，當算法收斂到結束條件或者達到最大迭代次數時終止迭代過程，得出聚類結果。

這里ui表示分類Si的平均值。

其算法步驟一般如下：

①從D中隨機取k個元素，作為k個簇的各自的中心。

②分別計算剩下的元素到k個簇中心的相異度，將這些元素分別劃歸到相異度最低的簇。

③根據聚類結果，重新計算k個簇各自的中心，計算方法是取簇中所有元素各自維度的算術平均數。

④將D中全部元素按照新的中心重新聚類。

⑤重復第4步，直到聚類結果不再變化。

⑥將結果輸出。

4.2 k-means指紋定位法過程

k-means指紋定位法可以分為三個階段。

第一階段為建立指紋庫，同于傳統KNN指紋定位法。

第二階段為指紋庫聚類階段，如圖3所示，可以設k-means算法中的k為4，選取4個指紋點作為其初始類簇中心點。由于初始類簇中心點的選擇對最終聚類結果的影響非常大，在指紋庫中隨機選用4個指紋點作為初始類簇中心點容易造成局部收斂，與是采取的辦法是先首先隨機選擇一個點作為第一個初始類簇中心點，然后選擇距離該點最遠的那個點作為第二個初始類簇中心點，然后再選擇距離前兩個點的最近距離最大的點作為第三個初始類簇的中心點，以此類推，直至選出4個初始類簇中心點。這樣將n個指紋點分為A,B,C,D這4類，每一個指紋點都會被歸入一類，每一個類中計算出一個中心點。這時，求未知目標與4個中心點的歐式距離，找到與未知目標歐式距離最近的點并將位置目標歸入該類。

第三階段為位階段，定位時，只需要求未知目標與該類中的每個指紋點的歐式距離，找到該類中與未知目標歐式距離最近的三個指紋點求質心即可，這樣大大減小了運算量，縮短了定位時間。并且在一個類中的指紋點距離不會出現較大波動，在一定程度上減小了定位誤差。

圖3 k-means指紋定位法原理圖

5 實驗過程

實驗場所選取在一個長10米，寬8米大展廳，如圖3所示。三星GALAXY S5 G9008V手機作為藍牙信號接收設備，手機位置即為未知目標位置。選用brightbeacon作為信號發射設備。5個beacon布置在展廳的天花板上，位置如圖1所示。在展廳中取均勻分布的30個指紋點，并在每個指紋點取每個beacon的120次rssi均值作為其指紋數據，建立指紋數據庫。將beacon的發射頻率設置為100ms，理論上手機每秒可以收到每個beacon的10個rssi值，可以用10個rssi值的均值作為該位置的rssi位置信息與指紋庫的指紋點數據進行相應的定位計算。但是實際測量中，并不能保證在同一時間收到到每個beacon的rssi值個數一致，于是采用的方法是將手機在1s內收到的n次rssi值作均值作為位置目標的的指紋信息。按以上步驟，分別用knn算法和kmeans指紋定位法進行定位，得到數據如表1所示。