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

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

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

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

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

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

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

2 BKM聚類算法

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

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

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

(1)

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

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

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

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

(2)

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

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

選取SSE最大的簇

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

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

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

Until

ε>Δ(閾值)

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

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

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

(3)

相對(duì)近似性RC：

(4)

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

(5)

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

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

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

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

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

Begin

Repeat

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

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

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

Until

滿足條件

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

4 仿真與驗(yàn)證

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

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

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

(6)

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

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

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

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

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

為了直觀展示效果，對(duì)實(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變化曲線對(duì)比

實(shí)驗(yàn)區(qū)域數(shù)據(jù)集大小(n)聚類個(gè)數(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%。綜合以上所述，可以說(shuō)明本文提出的改進(jìn)的BKM算法在定位精度上要比K-means和BKM算法好。

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

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

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

5 結(jié)束語(yǔ)

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

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