余曄

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

1 引 言

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

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

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

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

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

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

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

(1)

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

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

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

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

(2)

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

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

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

(3)

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

K-means指紋聚類算法 表2

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

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

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

(4)

(5)

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

(6)

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

(7)

其中，σj為參考點(diǎn)j在同一位置t次定位后坐標(biāo)方差，該方差為二維位置分量方差和。本文實(shí)驗(yàn)定位時數(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ī)，通過Android操作系統(tǒng)中提供的藍(lán)牙掃描模塊進(jìn)行RSS測量值的獲取，Android操作系統(tǒng)在4.3及以后版本開始支持藍(lán)牙4.0。將實(shí)驗(yàn)環(huán)境中的平面均勻地劃分為若干個正方形網(wǎng)格，將參考點(diǎn)選在網(wǎng)格的中心。

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

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

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

從圖3中可以看出，不同的網(wǎng)格尺寸對定位誤差有著較大的影響。隨著網(wǎng)格尺寸的增加定位誤差也隨之增加。當(dāng)網(wǎng)格的尺寸在 0.4 m～1.2 m之間時定位誤差下降幅度較小，當(dāng)超過 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ù)庫的建立時間以及定位精度，后續(xù)實(shí)驗(yàn)選取網(wǎng)格尺寸為 0.8 m的指紋數(shù)據(jù)庫進(jìn)行實(shí)驗(yàn)分析。

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

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

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

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

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

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

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

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

6 結(jié) 論

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