蘇明明， 魯照權(quán)， 陳 龍， 謝 地， 尤海龍， 丁浩峰

(合肥工業(yè)大學(xué) 電氣與自動(dòng)化工程學(xué)院，安徽 合肥 230009)

0 引 言

WiFi[1,2]指紋法通過信號(hào)強(qiáng)度與位置的映射關(guān)系建立指紋數(shù)據(jù)庫，再使用匹配算法估計(jì)目標(biāo)的位置。在匹配算法中的確定性算法—加權(quán)K最近鄰(weighted K nearest neighbour,WKNN)法[3]，因其復(fù)雜度低、易于實(shí)現(xiàn)且定位精度較高而被廣泛使用。而聚類的使用又能大幅度提高WKNN的計(jì)算效率且改善定位的精度，Yousself M等人[4]提出的顯式聚類算法是最早用于指紋定位的聚類算法，但該方法只適用于定位區(qū)域較小且AP數(shù)量少的情況；Borenovic M等人[5]提出了區(qū)域分割算法，該算法人為地將定位區(qū)域分割成大小相同的子區(qū)域，因此受到室內(nèi)格局的限制；Chen Y等人[6]提出了K-means算法并應(yīng)用于指紋定位。K-means是通過對由接收信號(hào)強(qiáng)度(received signal strength,RSS)均值組成的特征向量進(jìn)行聚類，其因訓(xùn)練快、易實(shí)現(xiàn)等優(yōu)點(diǎn)成為較受歡迎的聚類算法，但初始點(diǎn)的選擇和異常點(diǎn)的出現(xiàn)對其聚類的結(jié)果有很大影響。

本文在使用K-means++聚類算法的基礎(chǔ)上，提出了一種基于參考點(diǎn)位置聚類的算法。在位置聚類結(jié)果的基礎(chǔ)上，每個(gè)指紋都擁有一個(gè)類別。選擇M個(gè)最大均值A(chǔ)P并計(jì)算定位點(diǎn)與各參考點(diǎn)的距離[7]，然后利用K最近鄰(K nearest neighbour,KNN)對定位點(diǎn)分類，消除了偶然誤差，最后根據(jù)WKNN匹配算法即可得到位置結(jié)果。

1 WiFi指紋定位的一般原理

1.1 離線階段

離線時(shí)將各參考點(diǎn)的指紋存入指紋數(shù)據(jù)庫中。在待定位區(qū)域選擇L個(gè)參考點(diǎn)，在每個(gè)參考點(diǎn)位置采集WiFi的信號(hào)強(qiáng)度，假設(shè)在第i個(gè)參考點(diǎn)檢測到了m個(gè)AP的信號(hào)，則第i個(gè)參考點(diǎn)的指紋記作

(RSSIi1,RSSIi2,…,RSSIim,xi,yi)

(1)

式中xi,yi為參考點(diǎn)位置的坐標(biāo)。在錄入到指紋庫時(shí)，將該區(qū)域所有能檢測到的N個(gè)AP的信號(hào)按一定的順序排列。當(dāng)某個(gè)參考點(diǎn)處未檢測到其中的某些AP的信號(hào)時(shí)，則將該AP的信號(hào)強(qiáng)度值設(shè)為最低值，得到該點(diǎn)真正的指紋

(RSSIi1,RSSIi2,…,RSSIiN,xl,yl)

(2)

1.2 在線階段

在線時(shí)將實(shí)時(shí)的RSS特征向量上傳到上位機(jī)，與指紋庫進(jìn)行匹配得到估計(jì)的位置結(jié)果。一般多采用WKNN匹配算法，其原理是：計(jì)算待定位點(diǎn)與每個(gè)參考點(diǎn)的距離，找到距離最近的K個(gè)點(diǎn)用作位置估計(jì)，其中距離為

(3)

式中disti為待定位點(diǎn)與第i個(gè)參考點(diǎn)的距離；N為所有AP的個(gè)數(shù)，也即特征向量的維數(shù)；當(dāng)p為1時(shí)，該距離為曼哈頓距離，而一般p取2，即歐氏距離。當(dāng)找到距離最小的K個(gè)點(diǎn)后，通過式(4)來計(jì)算這K個(gè)點(diǎn)對待定位點(diǎn)位置計(jì)算的重要程度，即權(quán)值

(4)

式中wi為待定位點(diǎn)與第i個(gè)參考點(diǎn)的權(quán)值；根據(jù)式(5)可求得位置結(jié)果

(5)

2 基于K-means++的定位算法

在復(fù)雜的室內(nèi)環(huán)境下，根據(jù)指紋定位的一般算法雖然能夠得到待測點(diǎn)的位置坐標(biāo)，但定位的可靠性很低且精度一般難以滿足要求。圖1所示為本文定位方法的流程。

圖1 基于位置聚類的指紋定位法流程

2.1 數(shù)據(jù)的濾波處理

為減小誤差，本文使用限幅濾波和求均值的方法對數(shù)據(jù)進(jìn)行濾波處理，流程如下所示：

1)觀察采樣數(shù)據(jù)，確定2次采樣的允許的最大偏差值，并設(shè)為A。

2)每次檢測到新的時(shí)，計(jì)算新值和上次的偏差，記作δ，并判斷：

a.δ≤A,新值有效；

b.δ>A新值無效，取上次值。

3)重復(fù)過程(2)，直到?jīng)]有新值。

4)計(jì)算濾波后的均值，構(gòu)建指紋。

2.2 使用K-means++對指紋分類

K-means++是一種無監(jiān)督的學(xué)習(xí)方式，目的是為了把指紋庫中的所有指紋按相似度進(jìn)行分簇，使得相似的點(diǎn)在一個(gè)簇中，不相似的點(diǎn)屬于不同的簇。

對指紋庫中的指紋按位置聚類，把所有指紋分成了K個(gè)簇(C1,C2,…,CK)。在分簇的基礎(chǔ)上，使用KNN分類法找到待定位點(diǎn)所屬的分簇Ci，從而可以在該簇中估算其位置。算法流程如下所示：

1)隨機(jī)選擇一個(gè)參考點(diǎn)，并將其坐標(biāo)(x,y)作為初始的“種子點(diǎn)”；

2)對每個(gè)參考點(diǎn)計(jì)算其與最近的一個(gè)“種子點(diǎn)”的距離D(x)，并把這些距離加起來得到sum(D(x))；

3)取一個(gè)落在sum(D(x))中的隨機(jī)值Random=rand(sum(D(x)))，然后用Random-=D(x)，直到Random≤0，此時(shí)對應(yīng)的坐標(biāo)就是下一個(gè)“種子點(diǎn)”；

4)重復(fù)步驟(2)和步驟(3)直到選出K個(gè)聚類中心；

5)在這K個(gè)聚類中心下運(yùn)行K-means算法。

2.3 有監(jiān)督學(xué)習(xí)KNN

KNN分類的思想是，找到距離待定位點(diǎn)最近的K個(gè)參考點(diǎn)，則待測點(diǎn)就屬于這K個(gè)參考點(diǎn)中大多數(shù)所屬的簇。

由于并不是所有AP都適合用于定位，且MM法的AP選擇方式簡單又有較高的定位精度。因此，在選擇M個(gè)最大均值A(chǔ)P的情況下，通過式(6)計(jì)算定位點(diǎn)與L個(gè)參考點(diǎn)的距離

(6)

將計(jì)算所得的disti按從小到大排序，則前K個(gè)參考點(diǎn)被用來投票分類。這K個(gè)參考點(diǎn)在K-means++聚類后都有自己的分簇C，則定位點(diǎn)就屬于這K個(gè)參考點(diǎn)大多數(shù)所屬的簇。

當(dāng)指紋庫中部分參考點(diǎn)在采集數(shù)據(jù)時(shí)因信號(hào)強(qiáng)度波動(dòng)使其指紋偏離原本所屬的簇，KNN以這種投票的方式也能夠正確的分類，提高了可靠性。

3 試驗(yàn)與結(jié)果分析

試驗(yàn)采用UJIndoorLoc數(shù)據(jù)集，其為一個(gè)基于WiFi指紋的多建筑多層室內(nèi)定位數(shù)據(jù)集。該數(shù)據(jù)集包括訓(xùn)練集TrainingData和測試樣本ValidationData。選取其中部分樣本(第0棟建筑的第0層的訓(xùn)練樣本和測試樣本)用于測試所提出的算法，在100 m×100 m的范圍內(nèi)，總共53個(gè)參考點(diǎn)以及37個(gè)測試點(diǎn)。

試驗(yàn)前對UJIndoorLoc數(shù)據(jù)集進(jìn)行2處預(yù)處理，該數(shù)據(jù)集將所有在參考點(diǎn)處未檢測到的AP信號(hào)強(qiáng)度設(shè)置為100，此處，均改WiFi信號(hào)強(qiáng)度的最低值-127，如此更符合實(shí)際情況[8]；對數(shù)據(jù)集中參考點(diǎn)的經(jīng)緯度分別減去取值范圍的左邊界，用新的坐標(biāo)值來標(biāo)定。

3.1 數(shù)據(jù)的濾波效果

在TrainingData中，每個(gè)參考點(diǎn)處都采樣了10組RSS數(shù)據(jù)，觀察數(shù)據(jù)后發(fā)現(xiàn)WiFi信號(hào)強(qiáng)度并不穩(wěn)定，因此，需要對原始的數(shù)據(jù)進(jìn)行濾波處理。仔細(xì)觀察TrainingData后，選擇A為5對采樣數(shù)據(jù)作限幅濾波。如圖2所示為在1個(gè)參考點(diǎn)處2個(gè)不同AP的10組采樣數(shù)據(jù)濾波前后的對比，從圖中可以看出，限幅濾波消除了因偶然因素引起的大幅度波動(dòng)，使得采樣值更加平滑、可靠，對濾波后的數(shù)據(jù)求均值更接近實(shí)際的RSS值。

圖2 對10次采樣值進(jìn)行限幅濾波

3.2 K-means++聚類結(jié)果

為了驗(yàn)證對參考點(diǎn)的位置聚類有更高的可靠性，本文分別對強(qiáng)度和位置的聚類結(jié)果進(jìn)行了分析。其中，聚類中心個(gè)數(shù)K的選擇對定位性能的優(yōu)劣有直接的影響，通過對不同K值的定位結(jié)果分析，最終選取K為4。如圖3(a)中可以看出，第4個(gè)分簇在空間位置上有明顯差別，空間位置的差別導(dǎo)致其由信號(hào)強(qiáng)度組成的特征向量是有差別的，理論上各量并不屬于一個(gè)簇，但其與聚類中心的距離卻決定了各量屬于一個(gè)簇。而從圖3(b)可以看出相鄰位置的點(diǎn)屬于一個(gè)簇，而距離遠(yuǎn)的點(diǎn)分屬不同的簇。

圖3 按強(qiáng)度和位置聚類結(jié)果

3.3 定位結(jié)果分析

為了驗(yàn)證本文算法的性能，在同一個(gè)指紋庫下對37個(gè)測試樣本進(jìn)行了多次定位試驗(yàn)。在選擇M個(gè)最大均值A(chǔ)P的情況下(本文M取4)[9]，分別對未聚類、強(qiáng)度聚類和位置聚類的指紋庫使用WKNN算法(本文K取3)計(jì)算測試集的坐標(biāo)；在位置聚類下，對指紋庫使用線性插值法插入2個(gè)指紋并計(jì)算測試集的坐標(biāo)，從定位結(jié)果可以看出，對指紋庫的合理聚類提高了可靠性和降低了最大誤差。其中強(qiáng)度聚類相對未聚類平均誤差降低了21.35 %，而位置聚類與強(qiáng)度聚類相較平均誤差又降低了7.31 %，本文提出的聚類方法有效地提高了定位的性能。另外，在觀察參考點(diǎn)位置的過程中發(fā)現(xiàn)有些地方指紋稀疏，有可能是障礙物的存在導(dǎo)致無法采樣，從而影響了定位的精度。為了降低誤差，在合適的位置插值很有必要。本文使用線性插值在位置空白處插入了2個(gè)指紋，從結(jié)果來看同樣降低了定位的平均誤差。

不同聚類方法下定位精度概率累積分布以及位置聚類下測試集實(shí)際位置與定位位置如圖4所示。從圖中可以看出：本文算法的定位精度累積概率一直領(lǐng)先于強(qiáng)度聚類的方法，且達(dá)到了5 m以內(nèi)89.19 %的概率，最大誤差也控制在9 m以內(nèi)，基本滿足了對定位的要求。

圖4 定位精度概率累計(jì)分布和定位結(jié)果

4 結(jié)束語

本文在傳統(tǒng)對信號(hào)強(qiáng)度聚類的指紋定位基礎(chǔ)上，提出了對參考點(diǎn)位置聚類的方法。經(jīng)過對試驗(yàn)數(shù)據(jù)的定位，驗(yàn)證了該方法在定位可靠性和定位精度方面都有較大提高。

但是本文方法中聚類的使用并沒有降低計(jì)算量，測試點(diǎn)仍要與每一個(gè)參考點(diǎn)計(jì)算距離來正確分類。針對這一問題，可以在大區(qū)域定位時(shí)先進(jìn)行強(qiáng)度聚類降低計(jì)算量，在小區(qū)域中再使用本文提出的方法提高定位性能。