基于模糊聚類和動態K值的室內定位算法

董世鵬，吳韶波

（北京信息科技大學 信息與通信學院，北京 100101）

0 引 言

基于WiFi的指紋定位由于具有低成本、易部署、非視距等優點，已成為室內定位領域研究的熱點[1]。目前典型的WiFi指紋匹配算法是K近鄰（KNearest Neighbor, KNN）算法及其改進算法，通過比較待測點與指紋庫中參考點指紋強度距離，推算出待測點位置。但在室內環境中受多徑及障礙物遮擋等因素影響，WiFi信號強度存在波動，導致單純基于信號強度的定位算法將錯誤參考點歸入近鄰點中，增加定位誤差[2]。

文獻[3]在離線階段根據參考點空間位置進行聚類，在線匹配時在同一類簇參考點中選擇近鄰點，避免將偏離空間中心的參考點加入到近鄰點，但離線階段和在線階段聚類標準的不同無法保證在線聚類匹配的準確性。文獻[4]采用改進的組合加權指紋定位算法，剔除偏離幾何中心的近鄰點，將滿足條件的近鄰點結合實際位置與歐氏距離進行加權，沒有考慮不同歐氏距離下近鄰點定位可靠性，使估算出的幾何中心與測試點實際位置的距離較遠。

由于基于K近鄰的定位算法需要計算測試點與指紋庫中所有參考點的距離，當指紋庫中參考點數量過多時，難以保證定位實時性。因此，通常需要對指紋進行聚類，減少在線定位階段需要計算的參考指紋數量，提高定位效率。文獻[5]中提出基于FCM聚類及KNN算法的指紋定位方法，文獻[6]中提出一種基于親和力傳播聚類的定位方法，文獻[7]利用層次聚類對指紋庫進行劃分，均有效地降低了計算復雜度。但以上方法都沒有考慮到聚類邊緣處參考點選取問題。文獻[8]在二分K-means聚類的基礎上，根據聚類中心與樣本點歐氏距離閾值選擇類簇，將滿足條件類簇的所有指紋數據添加到參考點中，提高聚類邊緣處定位精度，但會引入過多指紋。文獻[9]中對數據在不同聚類的隸屬度差值進行劃分，但不適合樣本位于多個聚類邊緣處的情況。

針對以上問題，本文提出了一種結合改進FCM聚類與動態K值定位的改進算法。離線階段在傳統FCM聚類的基礎上，將隸屬度大于閾值的參考指紋添加到對應類中，降低聚類邊緣處指紋數據不足引起的誤差。結合指紋強度信息與近鄰點空間位置，剔除距離預測中心點較遠的近鄰點，并根據WKNN算法得出定位結果。

1 WiFi指紋定位算法

WiFi指紋定位可以分為離線指紋庫構建和在線定位兩個階段。離線指紋庫構建階段，采集并保存在各參考點采集到的指紋信息；在線定位階段，根據離線指紋庫及測試點采集到的指紋信息推算測試點位置。

1.1 離線指紋庫構建

在待定位區域按照一定間隔設置參考點，并建立相應坐標系。記錄每一個參考點處采集到的指紋信息強度及對應坐標，并保存到指紋庫FP中，如下式：

其中：（xi,yi）表示第i個參考點的坐標；Rij表示在第i個參考點接收到的第j個AP的指紋強度。

1.2 在線定位匹配

由于KNN算法[10]及WKNN算法[11]都是選取固定K個近鄰點，在判定近鄰點時容易引入信號距離較遠的點，導致定位精度降低。EWKNN算法[12]通過設定指紋強度距離閾值確定定位時的近鄰點及K值，有效避免了相似度較小近鄰點的引入，提高了定位精度。故在線定位階段本文選擇在傳統EWKNN算法的基礎上進行改進，通過結合指紋強度距離與空間距離對近鄰點進行二次篩選，進一步提高定位精度。

2 FCM聚類算法及改進

2.1 FCM算法原理

FCM聚類算法是一種模糊理論與HCM算法結合的軟聚類算法，使用[0，1]之間的隸屬度來表示數據屬于某個類的概率，并且樣本對于所有類簇的隸屬度之和為1。樣本在類簇中具有越高隸屬度，則屬于該類的可能越大，并將隸屬度最高的類作為樣本所屬聚類[13]。

FCM算法中代價函數定義為：

其中：J為代價函數；N為數據個數；c為聚類個數；uij為第i個數據對于第j個聚類的隸屬度；m為權重系數；||xi-cj||2為數據xi到聚類中心cj的距離。

通過拉格朗日公式對代價函數求導，最終可以得到聚類中心點和隸屬度的迭代公式分別為：

2.2 FCM算法步驟

FCM聚類算法的基本流程如圖1所示。

離子液體是由離子組成的有機鹽化合物，在室溫下多為流動狀態的液體，對纖維素等聚合物具有良好的溶解性能。在纖維素向5-HMF的催化轉化過程中，離子液體被廣泛采用[12]。

圖1 FCM聚類流程

2.3 基于隸屬度最小值的聚類劃分

當測試樣本在指紋聚類邊緣處時，近鄰點可能被劃分到不同聚類中，使聚類邊緣處的測試樣本無法獲得足夠參考點造成定位精度降低。由于在FCM算法中聚類邊緣處的樣本對于相鄰類別都有較高隸屬度，故在FCM聚類算法中加入最小隸屬度閾值對指紋數據進行劃分。

在傳統FCM聚類中加入最小隸屬度閾值m，當樣本i在該類簇中隸屬度值最大或隸屬度大于固定閾值m時，將樣本i加入到該類中，使在多個類簇中有較高隸屬度的樣本可以劃分到不同聚類。

3 結合模糊聚類的動態K值定位

為解決WiFi指紋定位中聚類邊緣處參考點不足造成定位精度降低及部分近鄰點偏離空間中心導致的定位精度下降的問題，提出了一種結合最小隸屬度的FCM聚類和動態K值的定位算法。算法的整體流程如圖2所示。

圖2 改進算法流程

針對傳統指紋定位算法進行在線定位時部分近鄰點偏離空間中心較遠導致定位精度降低問題，提出一種基于歐氏距離和近鄰點之間空間距離的K值確定方法，對近鄰點進行二次篩選。具體算法步驟如下：

（1）將設備從周圍接入點收集到的信號強度序列與指紋數據庫中的指紋序列進行計算，得到測試點信號強度與所有參考指紋序列的距離為：

其中：Aj為第j個AP的RSSI；Ri,j為第i個參考點處第j個AP的RSSI；M為指紋庫中參考點個數；N為指紋庫中AP個數。

（2）將Di按照升序排列，即Di中最小值為D1，最大值為DL，設定閾值D，將序列中大于D的點篩除，得到G個參考點。用Sg表示D1和Dg之間的差（g=2, 3,...,G）。計算Sg的平均值為：

篩除Sg大于E(S)的參考點，并將剩余參考點數目設置為K，按照升序排列為[D1,D2,...,DK]，作為待篩選近鄰點。

（3）定義初始中心坐標為（xcen,ycen），且有：

（4）計算坐標D1(x1,y1)與中心點坐標（xcen,ycen）距離，若小于閾值L則將中心坐標更新為（x1,y1），否則剔除近鄰點D1并對近鄰點D2進行判斷。若滿足閾值要求，將中心坐標更新為（x2,y2）并執行步驟（6），若不滿足則執行步驟（5）。

（5）計算D1與D2坐標均值（x12,y12）與中心點坐標（xcen,ycen）距離，若小于閾值L則將中心坐標更新為（x12,y12）。

（6）計算下一個近鄰點與中心坐標距離：

（7）若l＜L，則將近鄰點Di添加到指紋序列d中，并更新中心點坐標為：

其中：k為滿足閾值條件的近鄰點個數；xj和yj為指紋序列d中的近鄰點。

（8）重復步驟（6）和步驟（7），判斷其余近鄰點。

（9）對滿足條件的近鄰點序列[d1,d2,...,dk]，通過WKNN算法估計測試樣本位置（xcen,ycen）。

4 實驗結果與分析

4.1 實驗環境

實驗設置在學院教學樓6樓走廊進行，實驗場地為50 m×2 m的長方形區域，以1 m×1 m采樣間隔構建離線指紋庫。使用紅米Note7手機進行WiFi信號采集，并使用MATLAB2016a軟件對算法有效性進行驗證。實驗環境如圖3所示。

圖3 實驗區域平面

離線階段：使用自主開發的WiFi信息采集APP在每個參考點處采集WiFi指紋信息，共采集100個參考點，每個參考點采集RSSI信號數據30次，將數據進行高斯均值濾波后存儲到指紋數據庫中。

在線階段：在實驗區域內隨機選擇60個測試點，每個測試點采集RSSI信號10次，將經過均值濾波處理后的數據存儲為測試樣本。

4.2 實驗結果與分析

為驗證本文提出的動態K值定位算法，分別使用基于傳統FCM聚類的WKNN算法、EWKNN算法和本文提出的動態K值算法對測試點進行位置估計，其中改進定位算法閾值L設定為3，定位結果如圖4及表1所示。基于傳統FCM聚類的動態K值算法平均誤差為1.25 m，達到累計概率80%時的誤差為2.06 m，均低于EWKNN和WKNN算法，其中平均定位誤差分別降低12%和24%。

圖4 三種算法定位誤差

表1 三種算法定位誤差對比

對于聚類邊緣處缺少近鄰點導致的定位精度下降問題，選取不同的m值進行多次實驗，發現當m取0.1時基于最小隸屬度的FCM聚類效果最好。故取隸屬度最小閾值m為0.1，并對基于傳統FCM的改進EWKNN算法及本文所提算法進行位置估計，實驗結果如圖5及表2所示。與基于傳統FCM聚類的動態K值定位方法比較，本文改進算法定位平均誤差及達到相同累計概率的定位誤差均有所降低，分別減少了5%和3%。

圖5 聚類效果比較

表2 聚類效果比較

將本文改進算法與基于傳統FCM聚類的WKNN算法及EWKNN算法進行對比，平均定位誤差分別降低27%和16%，累計概率達到80%時的定位誤差分別降低26%和15%，提高了定位精度。

5 結 語

針對傳統指紋定位中近鄰點選擇及聚類邊緣處精度下降問題，本文提出了一種結合最小閾值聚類與動態K值的指紋定位算法。在離線階段，根據最小隸屬度閾值對樣本進行聚類，將傳統聚類邊緣點處的樣本點劃分到多個類別中，降低聚類邊緣處因缺少參考點而導致的定位誤差。針對在線階段，提出了一種結合指紋強度與參考點位置的動態加權K近鄰算法，對具有較低指紋序列相似度及偏離空間中心的近鄰點進行剔除，有效提高了定位精度。實驗結果表明，本文提出的改進算法雖然在一定程度增加了計算復雜度，但相較傳統算法定位精度有了較大提升，驗證了算法的有效性。