基于K-means++的WiFi指紋定位算法*

2019-05-07 11:45:02蘇明明魯照權尤海龍丁浩峰

傳感器與微系統 2019年5期

蘇明明，魯照權，陳龍，謝地，尤海龍，丁浩峰

(合肥工業大學電氣與自動化工程學院，安徽合肥 230009)

0 引言

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

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

1 WiFi指紋定位的一般原理

1.1 離線階段

離線時將各參考點的指紋存入指紋數據庫中。在待定位區域選擇L個參考點，在每個參考點位置采集WiFi的信號強度，假設在第i個參考點檢測到了m個AP的信號，則第i個參考點的指紋記作

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

(1)

式中xi,yi為參考點位置的坐標。在錄入到指紋庫時，將該區域所有能檢測到的N個AP的信號按一定的順序排列。當某個參考點處未檢測到其中的某些AP的信號時，則將該AP的信號強度值設為最低值，得到該點真正的指紋

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

(2)

1.2 在線階段

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

(3)

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

(4)

式中wi為待定位點與第i個參考點的權值；根據式(5)可求得位置結果

(5)

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

在復雜的室內環境下，根據指紋定位的一般算法雖然能夠得到待測點的位置坐標，但定位的可靠性很低且精度一般難以滿足要求。圖1所示為本文定位方法的流程。

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

2.1 數據的濾波處理

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

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

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

a.δ≤A,新值有效；

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

3)重復過程(2)，直到沒有新值。

4)計算濾波后的均值，構建指紋。

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

K-means++是一種無監督的學習方式，目的是為了把指紋庫中的所有指紋按相似度進行分簇，使得相似的點在一個簇中，不相似的點屬于不同的簇。

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

1)隨機選擇一個參考點，并將其坐標(x,y)作為初始的“種子點”；

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

3)取一個落在sum(D(x))中的隨機值Random=rand(sum(D(x)))，然后用Random-=D(x)，直到Random≤0，此時對應的坐標就是下一個“種子點”；

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

5)在這K個聚類中心下運行K-means算法。

2.3 有監督學習KNN

KNN分類的思想是，找到距離待定位點最近的K個參考點，則待測點就屬于這K個參考點中大多數所屬的簇。

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

(6)

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

當指紋庫中部分參考點在采集數據時因信號強度波動使其指紋偏離原本所屬的簇，KNN以這種投票的方式也能夠正確的分類，提高了可靠性。

3 試驗與結果分析

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

試驗前對UJIndoorLoc數據集進行2處預處理，該數據集將所有在參考點處未檢測到的AP信號強度設置為100，此處，均改WiFi信號強度的最低值-127，如此更符合實際情況[8]；對數據集中參考點的經緯度分別減去取值范圍的左邊界，用新的坐標值來標定。

3.1 數據的濾波效果

在TrainingData中，每個參考點處都采樣了10組RSS數據，觀察數據后發現WiFi信號強度并不穩定，因此，需要對原始的數據進行濾波處理。仔細觀察TrainingData后，選擇A為5對采樣數據作限幅濾波。如圖2所示為在1個參考點處2個不同AP的10組采樣數據濾波前后的對比，從圖中可以看出，限幅濾波消除了因偶然因素引起的大幅度波動，使得采樣值更加平滑、可靠，對濾波后的數據求均值更接近實際的RSS值。

圖2 對10次采樣值進行限幅濾波

3.2 K-means++聚類結果

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

圖3 按強度和位置聚類結果

3.3 定位結果分析

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

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