基于位置指紋的WiFi室內定位算法研究

劉業輝

摘 要：本文主要探討分析基于位置指紋的WiFi室內定位算法，該算法主要是通過層次聚類方式劃分測試環境區域，再匹配對應的WiFi信號指紋信息，之后利用加權計算確定定位位置。按照此次研究結果顯示，在充足的WiFi熱點數量之下，對比分析k-means-KNN算法以及原始KNN算法，位置指紋室內定位算法在地位給精準度以及準確率方面表現良好，此外，還分析加權最近鄰算法和最近鄰算法等相關內容，希望可以為位置指紋的WiFi室內定位算法研究提供參考性價值。

關鍵詞：位置指紋 WiFi 室內定位算法 加權最近鄰算法 最近鄰算法

中圖分類號：TP393 文獻標識碼：A 文章編號：1672-3791（2018）01（b）-0044-02

隨著全面普及的無線網絡以及移動通信技術，相應提升了對定位服務的需求。需要實現實時位置跟蹤以及路線導航等。基于以上發展現狀，在人們日常生活當中已經逐漸凸顯出定位計算和服務的重要性。針對室外定位技術，現階段比較主流的技術就是全球定位技術，在戶外活動方面被廣泛應用。然而在室內區域，建筑物會遮擋或者屏蔽信號，在室內定位當中無法充分發揮全球定位系統的作用。所以，在室內怎樣實現定位技術已經成為現階段研究的熱點話題之一。當前，有較多室內定位方式都是借助于基礎設備具備的某些技術完成定位，廣泛應用無線基礎設施，無線信號可以全面覆蓋到城市建筑當中，所以，通過無線網絡實現室內定位技術得以快速發展。

1 聚類在定位算法當中的應用

常規的位置定位算法主要是能夠計算所有鄰居，全面估算較多鄰居的位置。在實際計算期間可以篩選所有的鄰居，這樣能夠獲取更加準確的結果，降低估算時間。在空間當中，設備信號源與設備接受信號的強度呈正相關。所以，可以按照鄰居的物理位置將其分為多個獨立的簇，主要是通過聚類技術實現，自后選擇其中一個簇作為代表，這樣就可以過濾掉其他簇。

k-means聚類算法主要是劃分空間數據實現的，有關學者對于k-means算法的定位方案，算法的思維主要是按照信號的強度進行聚類，之后將相似接收相似信號強度定位參考點分組情況，這樣能夠降低定位計算工作量。然而由于經典的k-means聚類算法是在空間數據集內部各個子類具有較大差異性時，為了縮小誤差平方和，需要有效分割最大子類，這樣就使得該種算法限度局部最優解，難度全部進行最優解。為了處理該種現象，需要使用優化的聚類準則函數來進行計算。

2 最近鄰算法

該種方式是最基本的位置指紋定位算法。在定位時采用最近臨算法時，存在m個WiFi熱點，這樣就使移動終端設備接收m個熱點的信號強度值的集合為S=（RSSI1，RSSI1…RSSIm），之后將該離線收集的數據匹配具有歷史指紋庫的某一房間的位置數據指紋Ai，之后計算Ai與S之間的距離，在獲取Ai與S的最小距離之后需要將該數據對應的房間號作為定位結果。其最小距離的計算公式如下所示：

…3 （1）

如果式（1）的q值為1時，Di表示的是曼哈頓距離，當q值為2時，Di表示的是歐幾里得距離，此次研究將q值定為2，因此兩者之間采用的是歐幾里得距離。

首先需要計算在線實時數據和離線指紋數據庫當中的歷史數據距離，之后在對其進行比較計算最小距離對應的區域號。由于具有龐大的指紋數據庫，因此，需要較長時間進行匹配，在此次期間還會出現較多個距離相同的值數，在產生該種情況時需要再進行比較和計算。首先需要統計每個房間數據最小值的數量，之后再將取得較多最小值數量的房間進行定位，之后需要將該房間號作為定位結構。

3 加權最近鄰算法

3.1 加權最近鄰算法的原理

由于在此次研究當中不適用K近鄰算法，因此，需要提出加權最近鄰法。加權最近鄰算法是在最近鄰算法基礎之上進行改進。加權最近鄰算法的實時采樣信號強度值也是S=（RSSI1，RSSI1…RSSIm），并且該離線收集的數據匹配具有歷史指紋庫的某一房間的位置數據指紋Ai，其具有較低的定位準確率，因此，使用加權最近鄰算法可以有效改善該種情況。

一般情況下，移動設備會接收的熱點信號之間存在不相同的RSSI值，按照信號傳播的運力，能夠得知信號發射點經過的距離較短時，就會減慢信號衰落，降低衰減速度，這樣就使得移動設備接收的信號強度比較大。因此，在實際定位期間，移動信號要距離較大RSSI值熱點近，這樣最近距離熱點就會較大影響定位結果，具有較強的決定性。在對距離進行計算時，需要在離線指紋數據對應的RSSI值與熱點實時采集的差值與加權系數的乘積，之后再將m個距離的最小值應對區域與加權和作為移動設備的定位結果。以下公式就是加權最近鄰算法：

（2）

由式（2）可以看出，加權最近鄰算法與最近鄰法的最大差別在于加權系數，主要是通過每一熱點計算整個距離的權重值，在此時加權系數的取值主要有3種方式：（1）按照移動設備在固定時間內接受的m個熱點的RSSI值的平均值；（2）按照移動設備在固定時間內接受的m個熱點的RSSI值的方差；（3）按照信號的隨機性和波動性，得出每一個熱點與距離計算行為具有相同的貢獻，因此，導致所有熱點占據的權重都是1/m。前兩種方式的具有相同的原理和思想，并且具有較小的準確率相差情況。因此，本次研究主要是通過平均值作為加權系數的計算標準。

3.2 劃分區域類

為了確保數據的準確性和可靠性，因此，需要在離線階段多次進行采樣，這樣就會形成較大的位置指紋信息庫，盡管可以提升數據的準確性，然而卻進行長時間的匹配。這主要是因為實時定位期間的匹配都是通過歷史數據和實時數據實現的，如果存在較大的數據庫，相應會增加計算次數。如果在實際定位期間可以減少匹配時間，這樣就可以降低計算距離，不斷減小匹配范圍。其次，還存在較高便利性的計算方式，主要是通過數據處理之后得出的平均值，并且每一房間內的歷史數據只存在一行，這樣就會減少匹配時間。然而該種匹配方式無法確保結果的準確性，主要是因為該種方式存在較強的絕對性，只能明確大致的發展方向，無法確保細節方面，需要不斷促進定位目標的準確性。

4 結語

綜上所述，本文主要是探討分析基于位置指紋的WiFi室內定位算法，并且從聚類在定位算法當中的應用，最近鄰算法，以及加權最近鄰算法等方面進行闡述，其中加權最近鄰算法主要是分析了加權最近鄰算法的原理和劃分區域類等。通過對以上方面的分析研究，可以全面了解和掌握基于位置指紋的WiFi室內定位算法。

參考文獻

[1] 高富，賀艷軍.基于WiFi技術的煤礦井下人員定位系統研究[J].煤炭工程，2017（S2）：160-162.

[2] 王恩良，孟志斌，徐湘寓，等.一種基于WiFi指紋特征匹配的加權K近鄰室內定位算法[J].桂林電子科技大學學報，2017，37（4）：276-281.

[3] 韋信相，張文輝.基于Android的室內WiFi指紋定位系統及KNN定位算法的設計[J].大眾科技，2017，19（8）：14-16，31.

[4] 何富貴，吳陳沭，周先存，等.一種層次Levenshtein距離的無指紋校準的室內定位方法[J].智能系統學報，2017，12（3）：422-429.

[5] 許微，查峰，李豹.基于Android平臺的位置指紋室內定位系統研究與設計[J].艦船電子工程，2016，36（5）：50-55.