基于改進(jìn)BKM聚類算法的WiFi室內(nèi)定位方法

(上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620)

近幾年，移動手機(jī)越來越普及，人們生活方式發(fā)生顯著變化，基于用戶位置服務(wù)(Location Based Services，LBS)也得到快速發(fā)展，同時(shí)對于定位技術(shù)的要求也越來越高。在室外，目前應(yīng)用最為廣泛的是基于衛(wèi)星信號的定位技術(shù)，像谷歌地圖、百度地圖、高德地圖等一批較成熟的產(chǎn)品，在室外已經(jīng)可以給用戶提供高精度的定位服務(wù)。但是在室內(nèi)，都是密集的鋼筋建筑，衛(wèi)星信號會容易被削弱或阻擋，導(dǎo)致用戶無法進(jìn)行可靠的定位，而室內(nèi)又是人類活動的主要場所，用戶在室內(nèi)對于LBS的需求更大，同時(shí)針對復(fù)雜的室內(nèi)環(huán)境，對于定位技術(shù)的要求也更高，所以展開對室內(nèi)定位技術(shù)的相關(guān)研究具有重要的意義[1]。

目前常見的室內(nèi)定位技術(shù)有UWB、RFID、ZigBee等技術(shù)，雖然以上這些定位技術(shù)都能實(shí)現(xiàn)對室內(nèi)用戶終端的定位，但同時(shí)也都需要依靠一些特定的硬件設(shè)備，部署成本高，很難進(jìn)行大范圍的推廣。隨著WiFi技術(shù)的成熟，在很多場所已經(jīng)實(shí)現(xiàn)WiFi全覆蓋，尤其是在大型的商場、地下停車場等公眾場所。因?yàn)閃iFi具備自身部署成本低、響應(yīng)時(shí)間快的特點(diǎn)。WiFi已經(jīng)成為目前室內(nèi)定位應(yīng)用上普遍采用的技術(shù)之一，同時(shí)對WiFi定位技術(shù)的研究也越來越廣泛[2-3]。

通過WiFi在空間中的電磁接收信號強(qiáng)度(Received Signal Strength,RSS)，對室內(nèi)目標(biāo)進(jìn)行定位是當(dāng)前主要方法之一。其中，用的最多的是基于位置指紋的定位方法，通過利用WiFi電磁信號在空間中的分布規(guī)律作為定位基礎(chǔ)，實(shí)現(xiàn)方法簡單、定位精度高。文獻(xiàn)[4]提出一種K-means聚類算法運(yùn)用于WiFi室內(nèi)指紋數(shù)據(jù)庫的建立階段，改進(jìn)了指紋數(shù)據(jù)庫聚類中心選擇的復(fù)雜度，但是當(dāng)指紋數(shù)據(jù)之間的差異比較大時(shí)，該方法可能出現(xiàn)大的子類被過度分割反而降低定位的準(zhǔn)確度。文獻(xiàn)[5]提出了內(nèi)核K-means算法，并結(jié)合SVM，減少了非線性SVM的訓(xùn)練樣本，大大減少了采樣時(shí)間復(fù)雜度，但是這種方法也容易導(dǎo)致局部定位區(qū)域過擬合現(xiàn)象。文獻(xiàn)[6]～文獻(xiàn)[9]都是利用BKM聚類算法來優(yōu)化定位方法，提高了定位精度，但是BKM聚類算法和經(jīng)典的K-means聚類算法一樣，在聚類前都需要隨機(jī)的確定聚類個數(shù)，這樣導(dǎo)致聚類的結(jié)果容易受到聚類個數(shù)的影響。

針對BKM聚類算法在指紋定位過程中存在的不足，本文結(jié)合層次聚類的方法對BKM聚類算法進(jìn)行改進(jìn)，通過設(shè)置聚類準(zhǔn)則函數(shù)，不需要在聚類前就初始化聚類個數(shù)，可以自動確定聚類個數(shù)，并結(jié)合Chameleon聚類算法，對一些過度劃分的簇，以及偏移的點(diǎn)進(jìn)行歸并，優(yōu)化聚類效果，提高定位精度。

1 基于WiFi電磁指紋定位方法

位置指紋定位方法主要是分為兩個階段完成，分別是離線訓(xùn)練和在線匹配[10]。離線階段系統(tǒng)采集定位區(qū)域內(nèi)各個參考點(diǎn)接收來自不同無線訪問節(jié)點(diǎn)(Access Point,AP)反饋的RSS，與參考點(diǎn)的物理地址進(jìn)行一一映射，建立位置指紋向量并存儲在數(shù)據(jù)庫中；在線階段時(shí)采集待測點(diǎn)的位置指紋信息，與數(shù)據(jù)庫中指紋信息進(jìn)行匹配，最后估算出當(dāng)前用戶的位置，定位流程如圖1所示。

2 BKM聚類算法

BKM聚類算法基本思想如下：首先初始化簇表S，使S包含所有點(diǎn)組成的簇。然后，隨機(jī)從S中選取一個簇ci，通過K-means算法，對選定的簇ci二分，并計(jì)算每個簇的最小誤差值，選擇誤差最小的兩個簇，再將得到的兩個簇加入S中，更新簇表S。這樣反復(fù)下去，直到最終產(chǎn)生K個簇[11]。

這里通過誤差平方和(SSE)作為目標(biāo)函數(shù)，來衡量聚類質(zhì)量。SSE的定義如下：

圖1 位置指紋定位方法流程圖

(1)

式中,ci為簇的聚類中心，x為該簇中的一個樣本。

以上過程隱含著一個原則是：聚類性能是通過SSE值來進(jìn)行衡量的，所以SSE值越小越好，聚類效果也就越好。對上述簇的劃分過程不斷重復(fù)，直到最后簇?cái)?shù)目達(dá)到目標(biāo)值為止，與K-means算法相比，BKM算法可以加速K-means算法的執(zhí)行速度，能夠克服K-means收斂于局部最小的缺點(diǎn)，但是BKM聚類算法仍然受初始設(shè)定的聚類個數(shù)影響。

3 改進(jìn)的BKM聚類算法

BKM聚類算法與經(jīng)典K-means聚類算法相比，雖然在計(jì)算效率上有所提高，但是在計(jì)算過程中需要進(jìn)行多次K-menas聚類，增加了計(jì)算時(shí)間上的復(fù)雜度。所以，在此基礎(chǔ)上，本文對BKM算法進(jìn)行改進(jìn)，聚類前不需要初始設(shè)定聚類個數(shù)，通過二分聚類一次，就可以得到最小SSE的簇集。算法要求首先引入一個聚類測度函數(shù)f:

(2)

式中,xij為樣本(xi1,xi2,…,xin)中的對象，ci為簇中樣本的類中心。選擇一個樣本x={x1,x2,…,xn},樣本包含n個數(shù)據(jù)對象，分別給定迭代次數(shù)和測度函數(shù)一個初始值，然后隨機(jī)地在樣本中選擇一個ci，并將該ci作為聚類中心，加入到簇表s={s1,s2,…,sk}中。在簇表中選擇一個SSE最大的簇，然后在該簇中找出與該簇中心歐氏距離最大的一個樣本xi，再找出與樣本xi歐氏距離最大的樣本xj，同時(shí)將得到的兩個點(diǎn)，作為新的初始的聚類中心，生成兩個新簇，重新計(jì)算聚類中心為X1,X2，將其加到簇表中，同時(shí)刪除舊的聚類中心，并更新簇表，再計(jì)算測度函數(shù)ft的值，其中t表示迭代次數(shù)。

改進(jìn)后的BKM算法如下：

輸入 數(shù)據(jù)集x={x1,x2,…,xn}

輸出 聚類結(jié)果X={X1,X2,…,XK}

初始化：f=0.01，t=1,s={}

Begin

Repeat

選擇一個聚類中心，作為初始中心，并將該聚類中心加入到簇表中

選取SSE最大的簇

找出該簇中與簇中心最遠(yuǎn)的點(diǎn)以及與該點(diǎn)最遠(yuǎn)的點(diǎn)，將這兩個點(diǎn)作為新的聚類中心

將這兩個新的聚類中心加到簇集S中，刪除舊的簇中心

計(jì)算當(dāng)前聚類準(zhǔn)則函數(shù)的值，與判斷值進(jìn)行比較

Until

ε>Δ(閾值)

輸出所有聚類結(jié)果

初步改進(jìn)后BKM聚類算法通過設(shè)定合理的ε值和測度函數(shù)，可以自動確定聚類個數(shù)，這樣就不用和BKM聚類算法一樣，需要多次進(jìn)行K-means計(jì)算的過程。但是當(dāng)ε值選擇不合適的時(shí)候容易將數(shù)據(jù)集劃分過細(xì)，所以引進(jìn)Chameleon算法，根據(jù)相近程度合并這些劃分過細(xì)的簇。具體方法是通過計(jì)算簇表中任意兩個簇的互連性RI和緊密性RC這兩個指標(biāo)來判定，當(dāng)RI和RC的值都比較大時(shí)才合并這兩個簇[12]。

相對互聯(lián)度RI：

(3)

相對近似性RC：

(4)

R=RI(Ci,Cj)×RC(Ci,Cj)α

(5)

其中α為指數(shù)，通常大于1。

優(yōu)化后的算法如下：

輸入 二分聚類后的聚類結(jié)果X={X1,X2,…,XK}

輸出 輸出合并后的聚類結(jié)果

通過改進(jìn)BKM聚類算出新的聚類結(jié)果，將其中每一個簇看成一個整體

Begin

Repeat

計(jì)算每個簇與鄰近每個簇的RC和RI值，得到簇間相似度矩陣

構(gòu)造K-最近鄰圖，并對其進(jìn)行劃分

合并對于相似度函數(shù)具有最大值的簇

Until

滿足條件

輸出新的聚類結(jié)果

4 仿真與驗(yàn)證

4.1實(shí)驗(yàn)環(huán)境

本文通過實(shí)驗(yàn)來驗(yàn)證定位方法的提高，選擇的實(shí)驗(yàn)環(huán)境為本校1號實(shí)訓(xùn)樓的一層實(shí)驗(yàn)室及走廊，實(shí)驗(yàn)用的AP為該樓層現(xiàn)有的部分AP，且選取10個大部分采樣點(diǎn)都能接收到信號的AP。實(shí)驗(yàn)用的信號采集設(shè)備為聯(lián)想Lenovo天逸310筆記本，通過內(nèi)置無線網(wǎng)卡和自主開發(fā)的采集軟件進(jìn)行信號采集。

實(shí)驗(yàn)共選取了246個指紋采樣點(diǎn)，每個指紋采樣點(diǎn)處連續(xù)采集120組數(shù)據(jù)，時(shí)間間隔為1 s，以1.5 m×1.5 m作為采樣間隔，指紋采樣點(diǎn)分布如圖2所示。為了更好地量化定位效果，所以定義一個用來判斷誤差的函數(shù)為：

(6)

圖2 實(shí)驗(yàn)區(qū)指紋采樣點(diǎn)參考圖

4.2 數(shù)據(jù)預(yù)處理

因?yàn)樵趯?shí)驗(yàn)過程中會受到人員走動、開關(guān)門的影響，室內(nèi)的RSS具有不穩(wěn)定性，所以聚類前需要對每個采樣點(diǎn)采集到的多組數(shù)據(jù)進(jìn)行預(yù)處理，對數(shù)據(jù)中的離群值進(jìn)行剔除，保證數(shù)據(jù)指紋庫的穩(wěn)定性和可靠性，有利于建立更加精確的指紋數(shù)據(jù)庫。常用的數(shù)據(jù)預(yù)處理方法有3σ法、Chauvenet法、Grubbs法和狄克遜法。本文主要采用3σ法，對初始數(shù)據(jù)集進(jìn)行預(yù)處理。如圖3為預(yù)處理前后的RSS變化曲線對比。

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

本文主要通過三種算法進(jìn)行實(shí)驗(yàn)對比，分別是K-means、BKM和改進(jìn)BKM，表1為實(shí)驗(yàn)設(shè)定的相關(guān)參數(shù)。

為了直觀展示效果，對實(shí)驗(yàn)結(jié)果進(jìn)行量化，圖4給出了三種算法的定位誤差平均值，可以看出改進(jìn)的BKM的平均定位誤差為1.2125 m，要比K-meanc和BKM平均誤差降低48.6%和26.5%。

圖3 數(shù)據(jù)預(yù)處理前后的RSS變化曲線對比

實(shí)驗(yàn)區(qū)域數(shù)據(jù)集大小(n)聚類個數(shù)K經(jīng)典K-meansBKM改進(jìn)BKM區(qū)域176333區(qū)域298444區(qū)域372334

圖4 三種不同算法的平均定位誤差

圖5為不同算法的實(shí)際定位誤差累計(jì)概率圖，從圖中可以看出，改進(jìn)的BKM算法在定位結(jié)果中，有90%的定位目標(biāo)誤差范圍在2.5 m內(nèi)。作為比較，經(jīng)典的K-means和BKM在2.5 m范圍內(nèi)的定位誤差概率只有78%和82%。綜合以上所述，可以說明本文提出的改進(jìn)的BKM算法在定位精度上要比K-means和BKM算法好。

表2所示的是三種算法在3個不同區(qū)域上的平均定位時(shí)間。從表2中可以看出，BKM聚類在性能上要比經(jīng)典的K-means聚類算法好，在定位時(shí)間上平均快0.44 s，但是相較于BKM算法和經(jīng)典K-means算法都需要提前確定聚類個數(shù)，改進(jìn)的BKM聚類算法，不用提前指定聚類的個數(shù)K值，通過設(shè)置聚類準(zhǔn)則函數(shù)就

圖5 三種算法的定位誤差累計(jì)分布概率

表2 不同算法的平均定位時(shí)間 單位：s

5 結(jié)束語

在室內(nèi)復(fù)雜的環(huán)境下，WiFi電磁信號由于受到多徑效應(yīng)的影響，導(dǎo)致定位精度不高、誤差偏大。本文在分析經(jīng)典K-means聚類算法和BKM算法的基礎(chǔ)上，提出一種改進(jìn)的BKM聚類方法，在指紋庫構(gòu)建階段通過設(shè)置聚類測度函數(shù)，可以自動獲取聚類的個數(shù)，不需要初始化聚類個數(shù)，提高了指紋聚類的效果，同時(shí)引進(jìn)Chameleon算法對初步聚類后的結(jié)果進(jìn)行優(yōu)化，合并一些不合理的簇，提高指紋在線定位階段的可靠性和定位精度。實(shí)驗(yàn)結(jié)果表明，通過利用本文的改進(jìn)方法，能夠?qū)⒍ㄎ黄骄`差控制在1.2125 m左右，定位誤差在2.5 m以下的概率也達(dá)到了90%。

利用WiFi和位置指紋的定位技術(shù)，定位效率高、成本低，市場應(yīng)用廣泛。而本文提出的定位方法能夠在一定程度上提高定位精度，減少定位時(shí)間，增強(qiáng)用戶的定位體驗(yàn)，具有很好的現(xiàn)實(shí)意義。