基于K-means聚類(lèi)的藍(lán)牙室內(nèi)定位算法研究

余曄

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

1 引 言

隨著經(jīng)濟(jì)社會(huì)的發(fā)展，人們對(duì)位置信息的需求越來(lái)越多。同時(shí)，現(xiàn)階段人們的生產(chǎn)生活大多數(shù)都是在室內(nèi)環(huán)境下進(jìn)行的，因此室內(nèi)定位技術(shù)也越來(lái)越重要[1]。相比于室外衛(wèi)星定位，例如中國(guó)的北斗以及美國(guó)的GPS，在室內(nèi)環(huán)境下由于建筑物的遮擋，衛(wèi)星信號(hào)衰減嚴(yán)重，因此在室內(nèi)環(huán)境下難以利用衛(wèi)星信號(hào)進(jìn)行定位[2]。室內(nèi)定位技術(shù)作為衛(wèi)星定位的補(bǔ)充，旨在解決室內(nèi)環(huán)境下位置信息計(jì)算的問(wèn)題。由于現(xiàn)階段人們的生產(chǎn)生活主要集中在室內(nèi)環(huán)境下，人們對(duì)室內(nèi)位置信息的需求越來(lái)越多，室內(nèi)定位技術(shù)越來(lái)越得到人們的重視。與此同時(shí)，室內(nèi)定位技術(shù)對(duì)智能家居、智慧城市、智慧醫(yī)療以及智慧工廠都有著重要的作用[3，4]。

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

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

2 藍(lán)牙指紋定位原理

由于低功耗藍(lán)牙4.0的廣泛使用，使得使用藍(lán)牙信號(hào)的指紋定位系統(tǒng)具有成本低、部署方便、操作簡(jiǎn)單的優(yōu)點(diǎn)。與此同時(shí)，隨著智能手機(jī)的普及及手機(jī)廠商對(duì)藍(lán)牙標(biāo)準(zhǔn)的大力支持與推廣，使得藍(lán)牙指紋定位技術(shù)有著更好的應(yīng)用前景。指紋定位技術(shù)是一種場(chǎng)景匹配技術(shù)[8]。在室內(nèi)環(huán)境下信號(hào)傳播具有多徑效應(yīng)，因此每個(gè)位置點(diǎn)的多徑分量不同，由于多徑的不同造成了接收節(jié)點(diǎn)RSS存在差異，這種差異代表了每個(gè)位置的差異性即“指紋特性”。對(duì)于目標(biāo)定位就是要與每個(gè)位置的RSS進(jìn)行匹配，從而將相似度最大的指紋點(diǎn)作為估計(jì)的位置。

圖1 室內(nèi)指紋網(wǎng)格示意圖

指紋定位方法通常有兩個(gè)階段：離線階段和在線階段。在離線階段建立每個(gè)位置點(diǎn)與RSS的映射即指紋數(shù)據(jù)庫(kù)。在如圖1所示的室內(nèi)環(huán)境下，可以對(duì)其劃分為M個(gè)網(wǎng)格點(diǎn)稱為參考點(diǎn)，定位區(qū)域內(nèi)使用N個(gè)節(jié)點(diǎn)。在每個(gè)參考點(diǎn)上對(duì)來(lái)自N個(gè)節(jié)點(diǎn)的RSS進(jìn)行采集。從每個(gè)參考點(diǎn)上的指紋RSS一個(gè)N維向量，同時(shí)還包括了對(duì)應(yīng)參考點(diǎn)的坐標(biāo)，RSS指紋數(shù)據(jù)庫(kù)可以利用矩陣來(lái)表示為：

(1)

圖2為在其中一個(gè)測(cè)試點(diǎn)采集到的不同基站的RSS分布，表1為具體的統(tǒng)計(jì)數(shù)值。從圖2可以發(fā)現(xiàn)，在同一個(gè)測(cè)試點(diǎn)上接收到的不同藍(lán)牙基站的RSS分布狀況有著明顯的差異；從表1可以看出，同一物理位置上不同基站的RSS統(tǒng)計(jì)數(shù)值也呈現(xiàn)著差異。因此，利用不同位置上的不同藍(lán)牙基站的RSS的差異來(lái)表征不同的物理位置，將信號(hào)特性與物理位置進(jìn)行映射并存儲(chǔ)就構(gòu)成了指紋數(shù)據(jù)庫(kù)。

圖2不同藍(lán)牙基站RSS概率分布

不同基站的RSS數(shù)值統(tǒng)計(jì) 表1

實(shí)際在數(shù)據(jù)采集的過(guò)程中會(huì)引入噪聲，這些噪聲會(huì)使得采集的RSS產(chǎn)生波動(dòng)，影響最終的定位結(jié)果，因此在建立指紋數(shù)據(jù)庫(kù)之前需要對(duì)采集到的RSS數(shù)據(jù)進(jìn)行預(yù)處理。RSS預(yù)處理主要目的是消除奇異值、噪聲等因素對(duì)參考點(diǎn)處測(cè)試數(shù)據(jù)的影響，可以采用均值濾波取同一參考點(diǎn)處多次采集數(shù)據(jù)的平均值作為該參考點(diǎn)信號(hào)強(qiáng)度的估計(jì)值，計(jì)算公式如下：

(2)

其中，K為采樣次數(shù)。在線階段，可以對(duì)實(shí)時(shí)采集到的RSS序列與每個(gè)指紋點(diǎn)進(jìn)行相似度計(jì)算進(jìn)而實(shí)現(xiàn)定位，相似度常用的就是在RSS信號(hào)空間的歐幾里得距離，因此相似度越高RSS空間中的兩個(gè)向量距離就越近。

3 基于K-means的指紋庫(kù)劃分

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

(3)

其中，K為類(lèi)的個(gè)數(shù)且需要預(yù)先進(jìn)行指定，Xn為第n個(gè)類(lèi)中心。算法主要工作流程如表2所示。

K-means指紋聚類(lèi)算法 表2

然而，聚類(lèi)算法中類(lèi)的個(gè)數(shù)需要預(yù)先指點(diǎn)。本文首先在定位區(qū)域內(nèi)間隔采集定位點(diǎn)，然后利用定位點(diǎn)在2～N范圍內(nèi)的整數(shù)進(jìn)行遍歷，選取統(tǒng)計(jì)誤差最小的整數(shù)作為類(lèi)個(gè)數(shù)。

4 基于位置加權(quán)的定位算法

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

(4)

(5)

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

(6)

其中，wj為第j個(gè)最鄰近的參考點(diǎn)坐標(biāo)權(quán)重，計(jì)算方法為：

(7)

其中，σj為參考點(diǎn)j在同一位置t次定位后坐標(biāo)方差，該方差為二維位置分量方差和。本文實(shí)驗(yàn)定位時(shí)數(shù)據(jù)采集 30 s，然后利用1秒鐘的數(shù)據(jù)進(jìn)行一次定位，則一次定位可以獲得30次定位結(jié)果，然后利用多次的定位結(jié)果求取WKNN的定位結(jié)果。

5 實(shí)驗(yàn)結(jié)果與分析

在圖1所示的室內(nèi)環(huán)境下進(jìn)行數(shù)據(jù)采集，本文選用CC2540作為藍(lán)牙基站芯片。藍(lán)牙基站作為定位節(jié)點(diǎn)主要功能是發(fā)送藍(lán)牙廣播報(bào)文，本文中設(shè)置藍(lán)牙廣播報(bào)文的發(fā)送頻率為 10 Hz。本文定位終端為智能手機(jī)，通過(guò)Android操作系統(tǒng)中提供的藍(lán)牙掃描模塊進(jìn)行RSS測(cè)量值的獲取，Android操作系統(tǒng)在4.3及以后版本開(kāi)始支持藍(lán)牙4.0。將實(shí)驗(yàn)環(huán)境中的平面均勻地劃分為若干個(gè)正方形網(wǎng)格，將參考點(diǎn)選在網(wǎng)格的中心。

5.1 網(wǎng)格大小影響分析

實(shí)驗(yàn)中分別將網(wǎng)格的邊長(zhǎng)選為0.4 m、0.8 m、1.2 m、1.6 m、2.0 m來(lái)分析不同網(wǎng)格尺寸對(duì)定位精度的影響，同時(shí)選取最優(yōu)的網(wǎng)格尺寸。按照事先標(biāo)點(diǎn)好的網(wǎng)格點(diǎn)進(jìn)行數(shù)據(jù)采集，對(duì)每個(gè)參考點(diǎn)采集2分鐘的RSS數(shù)據(jù)，然后將采集到的數(shù)據(jù)進(jìn)行預(yù)處理。隨機(jī)采集測(cè)試點(diǎn)利用KNN算法進(jìn)行位置估計(jì)，最后計(jì)算定位誤差，圖3為選取不同網(wǎng)格尺寸的定位精度CDF圖。

圖3 不同網(wǎng)格尺寸的定位CDF圖

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

5.2 藍(lán)牙節(jié)點(diǎn)數(shù)量影響分析

藍(lán)牙基站數(shù)量越多每個(gè)參考點(diǎn)上的指紋特性越豐富，同時(shí)基站數(shù)量越多對(duì)數(shù)據(jù)庫(kù)的采集時(shí)間以及系統(tǒng)成本都有影響，因此研究基站數(shù)量對(duì)定位精度的影響有著重要的意義。在選定網(wǎng)格尺寸為 0.8 m的前提下，將區(qū)域內(nèi)的藍(lán)牙基站數(shù)量從7個(gè)減少到4個(gè)，然后隨機(jī)采集測(cè)試點(diǎn)利用KNN算法計(jì)算定位誤差，圖4為不同藍(lán)牙基站數(shù)量下的定位誤差CDF圖。

從圖4中可以看出，當(dāng)藍(lán)牙基站的數(shù)量增加定位精度隨之提高，當(dāng)藍(lán)牙基站的數(shù)量從3個(gè)提高到4個(gè)時(shí)定位精度提升很大，當(dāng)基站數(shù)量從4提高到6個(gè)時(shí)定位精度提升不大?？梢园l(fā)現(xiàn)3個(gè)基站的中值誤差為 6.5 m，4個(gè)基站的中值誤差為 4.4 m，5個(gè)基站的中值誤差為 3.2 m，6個(gè)的中值誤差為 2.3 m。因此，在實(shí)驗(yàn)區(qū)域內(nèi)選擇6個(gè)基站進(jìn)行后續(xù)的測(cè)試與分析。

圖4 不同藍(lán)牙基站數(shù)量定位精度CDF圖

5.3 K-means指紋庫(kù)劃分影響分析

為了驗(yàn)證有指紋數(shù)據(jù)庫(kù)劃分對(duì)定位精度的提升，在測(cè)試區(qū)域內(nèi)隨機(jī)選擇測(cè)試點(diǎn)。通過(guò)3種傳統(tǒng)算法(NN、KNN和WKNN)與指紋劃分后的定位進(jìn)行對(duì)比。四種基于不同匹配算法的指紋定位算法的定位CDF結(jié)果如圖5所示。

圖5 不同指紋定位算法定位結(jié)果對(duì)比圖

由圖5可知，基于K-Means指紋的藍(lán)牙定位算法的定位精度明顯高于傳統(tǒng)指紋定位算法?；贙-Means聚類(lèi)的中值誤差為 2.01 m，而傳統(tǒng)指紋匹配算法的最優(yōu)中值誤差(WKNN)為 2.35 m，特別是NN匹配算法的誤差數(shù)據(jù)中 10 m以上的誤差大于8%。

6 結(jié) 論

本文提出一種基于K-means聚類(lèi)的藍(lán)牙室內(nèi)定位算法，利用K-均值聚類(lèi)對(duì)定位區(qū)域的指紋數(shù)據(jù)庫(kù)進(jìn)行劃分得到不用區(qū)域的類(lèi)中心；然后，在線定位時(shí)將接收到的藍(lán)牙信號(hào)強(qiáng)度與不同的類(lèi)中心進(jìn)行比較得到定位區(qū)域；最后，在匹配到的子區(qū)域內(nèi)利用WKNN進(jìn)行定位，其中WKNN中的權(quán)重選取是利用多次定位結(jié)果的方差決定。實(shí)驗(yàn)結(jié)果表明利用區(qū)域劃分和基于位置方差加權(quán)的WKNN算法可以有效提高定位精度。