基于藍(lán)牙信標(biāo)的k-means指紋定位算法研究

重慶郵電大學(xué) 蔡云騏

基于藍(lán)牙信標(biāo)的k-means指紋定位算法研究

重慶郵電大學(xué) 蔡云騏

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

藍(lán)牙信標(biāo)；k-means；指紋定位；聚類

1 室內(nèi)定位技術(shù)

自上世紀(jì)末以來(lái)，基于位置的服務(wù)[1-3]（Location Based Services,LBS）迅猛發(fā)展，成為了人們?nèi)粘Ｉ钪斜夭豢缮俚囊徊糠帧６殡S著小型智能移動(dòng)終端的大規(guī)模普及，使得LBS有了更為廣闊的發(fā)展空間。而LBS的核心是定位技術(shù)。GPS定位系統(tǒng)，北斗衛(wèi)星定位系統(tǒng)等成熟的定位系統(tǒng)已實(shí)現(xiàn)了覆蓋范圍大、精度較高的室外定位。而在室內(nèi)定位中，由于極為復(fù)雜的室內(nèi)環(huán)境因素，GPS信號(hào)會(huì)受到極大干擾，基本無(wú)法利用GPS定位系統(tǒng)實(shí)現(xiàn)室內(nèi)定位[4]。

目前常用的室內(nèi)定位方法除了指紋定位算發(fā)還有時(shí)間到達(dá)法[5]（TOA），時(shí)間到達(dá)差法[6]（TDOA），信號(hào)強(qiáng)度測(cè)距法[6]（RSSI），到達(dá)角度差法[8]（AOA）等，這幾種方法需要建立信號(hào)傳播模型并對(duì)其中的參數(shù)進(jìn)行估計(jì)，而復(fù)雜的室內(nèi)環(huán)境使信號(hào)的多徑傳播產(chǎn)生反射和折射，很難對(duì)其中的參數(shù)進(jìn)行準(zhǔn)確的估計(jì)，從而使這些方法的定位精度不高。而基于信號(hào)強(qiáng)度的指紋算法作為臨近關(guān)系定位技術(shù)的一種，在室內(nèi)定位應(yīng)用中由于其定位精度高而被廣泛使用[9]。

圖1 藍(lán)牙信標(biāo)指紋定位圖原理

2 基于藍(lán)牙信標(biāo)的指紋定位技術(shù)

2.1 藍(lán)牙信標(biāo)指紋定位原理

基于無(wú)線信號(hào)指紋的定位技術(shù)是當(dāng)前室內(nèi)定位技術(shù)研究的重點(diǎn)。信號(hào)的多徑傳播對(duì)環(huán)境具有依賴性，呈現(xiàn)出非常強(qiáng)的特殊性,對(duì)于每個(gè)位置而言，該位置上信道的多徑結(jié)構(gòu)是惟一的,終端發(fā)射的無(wú)線電波經(jīng)過(guò)反射和折射，產(chǎn)生與周圍環(huán)境密切相關(guān)的特定模式的多徑信號(hào)，這樣的多徑特征可以認(rèn)為是該位置的“指紋”。

基于藍(lán)牙信標(biāo)的指紋定位就是在一個(gè)大區(qū)域布置n個(gè)藍(lán)牙信標(biāo)，在某一位置記錄n個(gè)藍(lán)牙信標(biāo)的信號(hào)強(qiáng)度（rssi）作為其指紋數(shù)據(jù)，這樣就可以在大區(qū)域得到m個(gè)指紋點(diǎn)作并建立指紋數(shù)據(jù)庫(kù)，再通過(guò)指紋定位算法對(duì)未知目標(biāo)進(jìn)行定位（見圖1）。

相較與基于wifi的指紋定位，采用低功耗藍(lán)牙4.0標(biāo)準(zhǔn)的室內(nèi)定位方法具有成本低、部署、方案簡(jiǎn)單、響應(yīng)速度快等技術(shù)特點(diǎn)，加之手機(jī)設(shè)備廠商對(duì)藍(lán)牙標(biāo)準(zhǔn)規(guī)范的大力推廣，因而具有更好的發(fā)展前景[6]。

2.2 信號(hào)強(qiáng)度指紋定位算法

信號(hào)強(qiáng)度指紋算法指是目前最常用的指紋定位算法，它是基于室內(nèi)環(huán)境復(fù)雜，信號(hào)反射折射所形成的在不同位置形成的不同的信號(hào)強(qiáng)度信息而提出的一套算法，利用已建立的指紋庫(kù)信息，通過(guò)一定的推理運(yùn)算得到位置目標(biāo)的近似位置。主要算法有最鄰近法法（NN）和K近鄰法（KNN）。

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

最鄰近法是最簡(jiǎn)單的算法，首先確定參考節(jié)點(diǎn)個(gè)數(shù)并建立指紋數(shù)據(jù)庫(kù)，設(shè)參考節(jié)點(diǎn)有n個(gè)，用Fi表示第i個(gè)指紋點(diǎn)收到n個(gè)參考節(jié)點(diǎn)的信號(hào)強(qiáng)度，那么某個(gè)指紋，這樣就建立了指紋庫(kù)。然后在某未知目標(biāo)得到n個(gè)參考節(jié)點(diǎn)的信號(hào)強(qiáng)度，即，通過(guò)下式計(jì)算S與Fi的距離Di，找到與S距離最小的那個(gè)指紋Fm，將Fm的坐標(biāo)作為未知目標(biāo)的定位結(jié)果。

式中Sj表示位置目標(biāo)受到第j個(gè)參考節(jié)點(diǎn)的信號(hào)強(qiáng)度，fij表示第i個(gè)指紋點(diǎn)收到第j個(gè)參考節(jié)點(diǎn)的信號(hào)強(qiáng)度，n即為參考節(jié)點(diǎn)總個(gè)數(shù)，當(dāng)q=1代表曼哈頓距離，q=2代表歐幾里得距離。q的取值不是固定的，可以根據(jù)具體情況來(lái)取q的值。

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

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

找到K個(gè)最近指紋點(diǎn)后：

在計(jì)算中一般取K=3，即找到三個(gè)最近指紋點(diǎn)用它們的三角質(zhì)心作為最終定位結(jié)果。

3 kNN指紋定位法

傳統(tǒng)的k均值指紋定位方法可以分為以下兩個(gè)階段。

第一階段為訓(xùn)練/離線階段，在目標(biāo)區(qū)域內(nèi)采集n個(gè)指紋點(diǎn)建立指紋庫(kù)，每個(gè)指紋點(diǎn)到5個(gè)藍(lán)牙信標(biāo)的信號(hào)并得到一個(gè)5維向量作為其指紋信息。

圖2 kNN指紋定位法原理圖

4 k-means指紋定位法

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

4.1 k-means聚類算法

K-means聚類算法是基于劃分的聚類方法，一般常見的做法是同時(shí)提取N種特征，將它們放在一起組成一個(gè)N維向量，從而得到一個(gè)從原始數(shù)據(jù)集合到N維向量空間的映射，通過(guò)不斷的迭代來(lái)實(shí)現(xiàn)聚類，當(dāng)算法收斂到結(jié)束條件或者達(dá)到最大迭代次數(shù)時(shí)終止迭代過(guò)程，得出聚類結(jié)果。

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

其算法步驟一般如下：

①?gòu)腄中隨機(jī)取k個(gè)元素，作為k個(gè)簇的各自的中心。

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

③根據(jù)聚類結(jié)果，重新計(jì)算k個(gè)簇各自的中心，計(jì)算方法是取簇中所有元素各自維度的算術(shù)平均數(shù)。

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

⑤重復(fù)第4步，直到聚類結(jié)果不再變化。

⑥將結(jié)果輸出。

4.2 k-means指紋定位法過(guò)程

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

第一階段為建立指紋庫(kù)，同于傳統(tǒng)KNN指紋定位法。

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

第三階段為位階段，定位時(shí)，只需要求未知目標(biāo)與該類中的每個(gè)指紋點(diǎn)的歐式距離，找到該類中與未知目標(biāo)歐式距離最近的三個(gè)指紋點(diǎn)求質(zhì)心即可，這樣大大減小了運(yùn)算量，縮短了定位時(shí)間。并且在一個(gè)類中的指紋點(diǎn)距離不會(huì)出現(xiàn)較大波動(dòng)，在一定程度上減小了定位誤差。

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

5 實(shí)驗(yàn)過(guò)程

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