基于KWAP-KNN分區聚類算法的室內定位分析

（河南工業貿易職業學院，信息工程系，河南鄭州市，450000）張海霞

隨著科技發展，定位技術發展越來越快，幾乎延伸到了各行各業，人們對定位要求越來越精準，僅憑借全球定位系統（GPS）的室外定位已經無法滿足人們需求[1-3]。因為移動通訊設備和Wi-Fi信號的廣泛覆蓋，基于Wi-Fi的室內定位算法憑借其成本低、定位精度高且無需其他外設等優點，逐漸成為現階段的研究熱點之一[4]。該定位方法在定位收集信號的過程中，基于Wi-Fi的室內定位僅依靠信號接受強度指示（RSSI）就可以完成定位，但由于障礙物遮擋、環境變化等多重因素引起的時效性、多徑效應等問題，RSSI信號存在誤差，在極大程度上影響著室內定位的精度[5]。因此，對基于Wi-Fi的室內定位研究十分必要。

1 分區聚類算法

1.1 WAP聚類算法

目前，通常可以選擇在無線傳感器網絡（Wireless sensor network，WSN）應用系統中加入移動節點的方法來實現更加靈活地完成現場監測過程，但是如何對動態過程采用具備低能耗與高精度的WSN節點進行定位是現階段眾多研究人員需要解決的問題等。

AP聚類算法中以p作為節點為聚類中心的度量。由于環境、人員流動、多徑效應等因素的影響，不同信號接收裝置接收到RSSI信號值存在差異，僅憑借歐氏距離計算S，選取矩陣中值或者均值作為相似性度量，會導致定位結果不準確。針對上述問題，本文引入熵值法對S相似度進行優化后，對優化后的p進行加權處理，已獲得更加準確的粗定位結果。

熵值法用來判斷指標的離散程度。將每個節點的一組RSSI值作為輸入計算權重，并將得到的權重作為不同信號接收裝置對該節點的影響因子。其中，針對異質特征維數同質化問題，需要將特征維數的標準化處理。首先歸一化處理數據，計算正向特征維數和負向特征維數數值。

正向特征維數：

負向特征維數：

將一組RSSI值作為輸入，熵值法具體計算公式如下：

其中，RSSIij為指紋庫中第i個數據點的第j個RSSI值，i=1，2，…，n；j=1，2，…，N，n為樣本數，N為RSSI值數，j表示權重。則節點i，k之間的相似度計算方式為：

通過得到的權值計算數據點之間的相似度，對相似度進行均值加權處理，則p的值為：

1.2 基于KWAP-KNN算法原理及流程

距離信號發射裝置越近，則RSSI信號接收更準確。且RSSI信號值在空間上區分能力有限，通常都在1m以上，所以為了避免相鄰指紋信息在位置上二異性，兩個信號發射裝置布置距離應該在1m以上。以信號接收裝置為圓心，根據實際環境確定覆蓋區域半徑，盡量保障大部分區域在劃分的覆蓋區域范圍內。

區域劃分依據為位置信息，選擇K-means進行分區，該方法簡單且容易實現，選取信號發射裝置所在位置為K個聚類中心的位置，通過聚類對未覆蓋區域和交叉區域進行分區。當對未知節點進行區域劃分時，根據RSSI值差異確定歸屬區域，如果屬于覆蓋區域，直接進行WAP聚類，如果屬于未覆蓋或者交叉區域，通過K-means重新進行歸類，當所有的節點被劃分到不同區域時，劃定小區域。最后通過KNN聚類在小區域內獲取粗定位結果。整個區域劃分及定位流程如圖1所示。

圖1 區域劃分流程圖

2 實驗結果及分析

區域劃分以實際室內環境和信號發射裝置布置為準，以信號發射裝置位置為圓心，固定距離為圓心，劃分區域。實驗在14m×11m的區域進行，現場布置了共6個路由器作為信號發射裝置。

通過Matlab軟件來仿真驗證本文的定位算法。進行仿真測試時，按照表1數據來設定各項參數。在100m的范圍內以隨機方式設置共60個節點，將節點的通信半徑設定為20m。節點分布圖如圖2所示。

表1 參數設置

圖2 節點分布圖

圖3為AP聚類和WAP兩種聚類的效果圖。

圖3 聚類效果圖

選取一百組測試點進行實驗，未進行區域劃分之前，分別使用KNN、AP-KNN、WAP-KNN三種算法進行定位。可以得到如圖4所示的誤差累積圖。圖中可以看出，隨著節點數目增加，WAP-KNN累積定位誤差低于其余兩種定位方法。

圖4 平均誤差累積

圖5為三種定位方法誤差累積分布圖。100個參考點中，定位誤差小于2.5m的概率，KNN、APKNN、WAP-KNN算中算法分別為72%、67%、62%，其中KNN算法概率最高。但是WAP-KNN算法所有參考點的定位誤差均小于3.45m，AP-KNN均小于4.00m，WAP-KNN總體定位誤差較小。而且APKNN和WAP-KNN這兩種方法定位沒有出現誤差較大的點。之后對三種方法求解平均定位誤差，并對其最小最大誤差進行分析，可得如表2所示的定位誤差表。從表中數據看出，WAP-KNN算法的平均誤差、最大最小誤差值都比其余兩種算法要小。

圖5 三種定位方法誤差累積分布圖

表2 三種定位算法定位誤差表

3 結語

綜上所述，針對單一聚類算法存在的多種問題，提出一種基于KWAP-KNN的分區聚類算法。實驗結果證明，無論從樣本點的之間相似性，還是從聚類時間來講，WAP聚類算法都比AP聚類算法低，聚類效果更好。區域劃分后，KWAP-KNN算法得到的粗定位結果更準確，定位精度可達到1.8m左右。