基于多視角聚類的WiFi指紋定位方法研究?

馬宗方呂麗萍田鴻朋王 艷

(西安建筑科技大學信息與控制工程學院，陜西 西安 710055)

據調查研究表明，人類有70%以上的活動時間是在室內。室外定位導航可由全球定位系統(Global Positioning System，GPS)定位技術得到有效解決[1]，而室內定位技術相較于室外定位技術還不成熟。近幾年，很多學者已在室內定位領域進行研究，常用的3類技術為:①鋪設相關特殊設備實現定位。例如射頻識別、無載波通信等[2－5]；②利用傳感器獲取相關位置信息。例如加速度計、陀螺儀等[6－8]；③借助已有的WiFi網絡覆蓋環境。例如指紋定位、測距技術等[9－10]。第3類技術相較于第1類和第2類技術，即節省了購買設備與搭建測試環境的費用，開發過程也十分便捷，相對更容易實現。同時，WiFi無線信號具有傳輸速率快、功耗低、通信能力強的優點。因此，對于WiFi指紋定位技術的深入研究具有重要的科研意義與工程應用價值。

目前很多學者從WiFi接收信號強度指示(Received Signal Strength Indication，RSSI)、信號穩定性校準、離線建庫方法等方向進行改進。比如，文獻[11]提出了一種根據環境變化動態更新指紋庫的方法，在降低成本的同時，有效提高了系統的穩定性與自適應性，但其定位精度準確度相對較低；文獻[12]提出了改進的K-means算法位置指紋定位技術，通過優化函數來獲取較優的指紋庫初始類中心，有效提高了分類效果和定位精度。文獻[13]提出了一種基于位置聚類結果的指紋定位算法，糾正了信號強度聚類的不合理，有效提高了算法性能，但指紋定位原理是采用實際采集的WiFi信號強度與指紋庫數據進行匹配，進而獲取位置，單純采用位置聚類會影響定位效果。綜上所述，以上方法均屬于單視角聚類定位，且對于定位系統的精度貢獻不明顯，即現有方法無法解決現存實際問題。

針對該類單視角聚類定位方法中普遍存在的聚類結果不合理性與聚類視角單一化問題，本文提出基于位置坐標信息與信號強度信息的多視角聚類方法，該方法選擇N個無線接入點(Access Point，AP)樣本，通過對樣本集進行閾值－均值濾波后，結合Kmeans聚類算法對多視角信號(強度和位置)進行區域劃分，并建立離線指紋庫，實時獲取待定位位置。一方面糾正信號強度聚類結果的不合理，另一方面解決位置聚類結果參考性小，準確度低的問題。

1 研究方法

1.1 WiFi指紋定位原理

WiFi指紋定位[14]技術的工作過程一般為兩個階段，離線建庫與在線匹配。其基本原理及工作流程如圖1所示。

圖1 指紋定位基本原理示意圖

離線建庫實際是預先將所有參考點的指紋錄入數據庫的過程。通常確定待定位區域后，需合理劃分待測區域空間并選擇M個參考點，每個參考點的中心點坐標即為指紋的參考點坐標，在每個參考點處采集WiFi信號強度，記錄參考點坐標與WiFi信號強度一一對應的值[15]。

假設在參考點m處檢測到了N個AP[16]，則參考點m的指紋庫可以表示為式(1):

式中:RPm為參考點m的指紋庫表示，xm，ym為參考點m的位置坐標，RSSIm1，RSSIm2，…，RSSImn，…，RSSImN為第m個參考點的N個AP對應的信號強度值，對應錄入相應WiFi指紋庫，得到離線指紋庫，可表示為式(2):

在線匹配時，每個定位點的位置估計可由實時采集的待定位目標的信號強度RSSI與指紋庫數據去唯一確定。具體過程是實時獲取待定位目標的RSSI值，并與離線指紋庫中的信號強度信息進行匹配得到估計的位置坐標，從而實現定位。其中最常用的方法為K近鄰(K-Nearest Neighbor，KNN)[17－18]匹配算法。其主要原理為計算實測點的信號強度與每個參考點的信號強度的距離，找到距離臨近的K個點，進一步進行實測點位置估計，也常用加權K近鄰[19－20]。

1.2 數據的濾波處理

為保證數據的有效性與后期算法的處理效果，本文采用閾值濾波與取平均值的方法對原始數據進行處理。由于原始數據量較大且無明顯規律，通過分析歸納后，統一歸一化處理測試樣本的經緯度信息；刪除信號強度信息微弱的AP點，RSSI值為－127表示WiFi信號幾乎沒有，用自然數100來代替WiFi信號微弱的點；經處理后的參考點數據波動較大，存在干擾點與異常點，需進一步閾值濾波處理，使得處理后的數據相對分布集中。每次對比新值與上次值的差值，差值記為δ，閾值記為A，并判斷:①δ≤A，新值有效；②δ>A，取新值與上次值的平均值；重復上述步驟直到沒有新值出現；最后對每一個參考點的20組數據求平均，確定每個參考點對應一組數據，并保存預處理后的數據。

1.3 多視角K-means聚類算法離線建庫

假設多視角聚類數據集為X，則多視角K-means聚類的目標函數為式(3):

式中:V為視角個數，C為聚類的類別個數，M為樣本個數，p為權重指數，通常取2，為第v個視角的權重向量，δim非0即1，當xm屬于第i類時為1，否則為0，x為樣本xm的第v個視角向量為第v個視角的第i類聚類中心向量。

利用拉格朗日乘子最優化方法最小化式(3)，得到多視角聚類算法的聚類中心，其迭代表達式如式(4):

權重向量wv的迭代表達式，如式(5):

式中:為樣本xm的第v′個視角向量，為第v′個視角的第i的中心向量。

多視角K-means聚類算法流程如表1所示。

表1 多視角K-means聚類算法流程

該表中輸入包括視角個數V，聚類個數C，樣本集X，權重指數p，值取2，迭代閾值τ。輸出為劃分聚類指數δ，類中心矩陣z，權重矩陣w。隨機初始化C個類中心，設定初始權重＝1/v；計算每個樣本到其類中心的歐式距離，按照最小距離分配標簽的原則，給所有樣本劃分標簽，確定劃分聚類指數δ，并利用式(4)更新迭代聚類中心矩陣z；利用式(5)更新計算權重矩陣w；利用式(3)更新計算目標函數JH；如果‖Jt＋1－Jt‖<τ，算法結束，輸出結果，否則重新利用式(4)更新迭代聚類中心矩陣z。

1.4 WKNN算法在線匹配

實時定位階段，每個測試樣本在選擇自己所屬類別時，用基礎分類器依據信號強度信息對待測樣本進行分類，選用KNN分類器。而后用WKNN算法實現類間找K個最近的距離，輔以權重W確定實際定位位置。

上述WKNN算法分類過程主要涉及三個步驟:K值選擇、距離計算、權重決策規則。

①K值選取

在WKNN分類算法中，近鄰個數K的選取對定位結果的穩定性有一定程度的影響，K值過大可能會導致選擇的近鄰中包含有噪聲數據，而K值過小可能無法找到真正的近鄰，因此本文K值的選擇區間為[3，7]，默認取值為3。

②距離計算

WKNN的距離度量標準為式(6):

式中:N為AP的個數，即特征向量的維數，其中p取2，表示歐氏距離，當然也可用其他距離度量方式。d m為某個待測點信號強度與所屬類中第m個參考點信號強度的距離，在求取待測點與類內所有參考點的距離后，選取K個最近距離。

③權重決策規則

當找到距離最臨近的K個點后，通過式(7)來計算這K個點對實測點位置估計的重要程度，即權值:

式中:wk為類內第k個參考點對待測位置的重要程度的體現，

最后，根據式(8)可求得實測的位置。

式中:，為實際的定位位置，xk，yk為K近鄰的位置信息。

2 實驗結果分析

2.1 數據濾波分析

實驗選用UJIndoorLoc數據集，其為一個多建筑多樓層的室內WiFi指紋定位數據庫，該數據集分為兩部分，訓練樣本TrainingData與測試樣本ValidationData。本文選取第0棟建筑的第0層數據來驗證本文的定位方法。

數據濾波過程為:歸一化測試樣本的經緯度信息；剔除沒有強度信號的AP點，用－127替換信號強度為100的值；對一個參考點的數據進行閾值濾波，使得濾波后的數據相對集中；對一個參考點的20組數據求平均，確定一個參考點對應一組數據。

由于WiFi信號強度的不穩定性，選取一個采樣點的20組數據進行閾值處理，如圖2濾波前－后對比圖所示，圖中方形與三角形表示濾波之后的數據，可以看出信號強度波動較大的參考點AP3與AP9進行閾值濾波后，其RSSI值的變化程度減小，使得同一采樣點的數據更加平滑、可靠，最后針對閾值濾波數據進行均值處理，保留每個參考點的一組預處理完的數據。

圖2 采樣點濾波前－后對比圖

2.2 多視角K-means聚類結果對比分析

為了驗證采樣點多視角聚類對于定位精度的影響，實驗過程分別對信號強度、位置以及多視角的聚類結果進行分析，在K-means聚類算法中，聚類中心個數K的選取對聚類結果有不同程度的影響，通過對不同K值聚類結果分析，最終選擇K取值為4。

圖3為單視角與多視角聚類結果圖，圖中劃分到不同類的樣本用不同的符號標記。由于單視角聚類中的信號強度聚類在結果上存在不合理性，實際距離比較遠而強度信號差異較小的會聚成一類，如圖3(a)信號強度聚類所示，圖中橢圓圈出為一類，分布于兩個小區域，理論上各數據不屬于同一類，但其與強度信號類中心的距離決定了各數據屬于同一類，所以聚類結果明顯存在不合理性。而位置聚類在聚類結果上沒有表現出明顯的不合理性，但指紋定位最后需要用在線采集的信號強度RSSI值來匹配指紋庫，進而確定待定位點的位置信息，這個過程會使其定位精度降低，如圖3(b)位置聚類所示，不能滿足定位精度要求。而從圖3(c)多視角聚類結果可以看出相近的點隸屬相同的類別，距離較遠的點分屬不同的類別，相應的彌補了信號強度與位置聚類的劣勢，聚類結果相對較好。由圖3分析可得，相對于單視角聚類而言，多視角聚類結果更合理、效果更好。

圖3 聚類結果

2.3 定位結果

為了更好的驗證本文算法的性能，對測試樣本進行了多次綜合試驗。分別對單視角信號(信號強度或位置)與多視角(信號強度與位置)信號進行聚類并建立離線指紋庫，使用基礎分類器WKNN對實測信號分類，待測信號依據分類結果在其所屬區域內估計K個鄰近信號點，用近鄰以及相應的權重值綜合確定該信號的實際位置。圖4為不同聚類方法定位結果的累積概率分布圖，從結果分析可知:本文的多視角聚類定位算法精度恒高于單視角(強度聚類或位置聚類)聚類定位算法，并且定位精度在4 m以內的概率為83%，相比于信號強度聚類和位置聚類定位的結果，定位精度在4 m內的概率提高了12%。圖5為本文算法定位的實際位置與真實位置的分布圖，結果證明本文算法基本滿足了定位場景的實際需求。

圖4 不同聚類方法定位結果的累積概率分布

圖5 定位位置與實際位置對比

3 結果與討論

本文針對指紋定位中方法單一及定位準確度低的問題，采用多視角(信號強度和位置)聚類方法實現了定位，得出多視角與單視角分類結果及其相對應的累積概率分布與最終解算出的實際位置。通過對比分析實驗結果，得出以下結論:

①多視角聚類糾正了WiFi信號強度聚類結果的不合理性，提高了位置聚類的分類準確度。相比較而言，基于多視角聚類的WiFi指紋定位方法可靠性更強。

②通過實驗對比，本文算法定位精度在4 m以內的概率為83%，相比于信號強度聚類和位置聚類定位的結果，定位精度在4 m以內的概率提高了12%，基本滿足了實際定位場景的應用需求。

③該研究的數據集采用公共數據集，考慮到定位系統的實用價值，后期可針對實際應用場景搭建實際的數據采集測試環境，進行更深入的應用研究修正。