基于位置范圍限定的WiFi-KNN 室內定位算法

哈爾濱工程大學 信息與通信工程學院，黑龍江 哈爾濱 150001

隨著基于位置服務(location based service,LBS)的快速發展，導致人們對定位服務的需求與日俱增。在全球定位系統(global positioning system，GPS)等室外定位技術完善的情況下，人們對室內定位的需求也得到了進一步的提升。特殊人群的監護、大型館場的管理、商場人流的統計、火災時的救援行動等，都需要用到用戶準確的室內位置信息。現如今最常用的幾種室內定位技術有WiFi 定位[1]、藍牙定位[2]、超寬帶定位[3]、射頻識別定位等。本文的主要目的是利用WiFi 信號強度實現高精度的室內定位。通常，WiFi 室內定位方法可以分為2 類：一類是基于信號衰減的傳播模型，它根據WiFi 傳播信號時的衰減模型，利用基于到達時間（time of arrival，TOA）[4]或基于到達角（angle of arrival，AOA）[5]的方法來估計目標的位置；另一類是基于WiFi 指紋的室內定位方法，它的特點是要建立WiFi 指紋庫。通過將參考點(reference point，RP)處的指紋信息存儲起來，再根據待定位點處采集到的指紋數據，通過指紋匹配算法在指紋庫中估計目標的位置。由于WiFi 信號在室內空間中傳播時有強烈的多徑效應，導致很難獲得精確的信號衰減傳播模型。因此指紋識別方法更適合基于WiFi 的室內定位。但是傳統的基于WiFi 指紋庫的K近鄰（K-nearest neighbor，KNN）室內定位算法，在定位時因為誤差的波動較大，所以該方法并不能滿足定位精度的需求。本文提出基于位置范圍限定的WiFi-KNN 室內定位算法，該算法可以很好地減小傳統WiFi 室內定位方法誤差大的問題。

1 WiFi 指紋的室內定位方法

基于WiFi 指紋的室內定位方法又可以分為確定性方法和概率性方法[6?7]。確定性方法是利用相似性度量來區分測量的信號數據和數據庫中的指紋數據，然后將指紋數據庫中最接近的指紋數據所處的位置估計為用戶的位置。這一類室內定位方法的典型代表有人工神經網絡[8?9]（artificial neural networks,ANN）,支持向量機[10]（support vector machine，SVM）和K近鄰[11?12](KNN)，上述所有的定位方法都需要在離線階段收集指紋信息，然后將其與測試階段的測量數據進行比較來達到定位的目的。

在這些算法中，ANN 可以選擇激活函數，通過調整權重來對數據進行非線性估計，以達到對目標的位置估計。盡管該方法能獲得最高的精確度，但是它本質上是復雜的，并且在訓練階段需要極高的計算復雜度[13]。與之相反的是SVM，雖然SVM 比ANN 更簡單，但算法復雜度仍然相對較高。與SVM 和ANN 相比，KNN 具有最低的復雜度，同時它的精確度卻可與SVM 相提并論。

概率性方法都是利用貝葉斯法則，然后根據指紋庫中的指紋數據和待定位點處測量到的指紋數據來推斷位置信息。一些概率性方法將接收信號強度（received signal strength，RSS）的概率密度函數假定為經驗參數分布[14?15](例如高斯、雙峰高斯等)。這有可能因為沒有很好地模擬實際情況而導致大量的本地化錯誤。

本文針對KNN 算法進行了進一步的研究，因為它具有較低的復雜度，更適合于實際生活中的使用。通常，KNN 算法需要計算當前測量的指紋數據與數據庫中的各個指紋數據之間的距離，然后通過排序來確定K個距離最近的參考點，然后通過加權平均估算待定位點的位置。在KNN 中計算指紋距離時可以使用不同的距離度量，例如歐幾里得距離、曼哈頓距離和馬哈拉諾比斯距離等[16]。

盡管KNN 算法已在各類文獻中進行了廣泛研究，但KNN 仍然面臨以下挑戰：

1)空間歧義性：與當前位置相比，某些物理上遙遠的位置可能具有相似的指紋或相似的指紋距離。這可能會誤導KNN 算法，從而提高定位誤差。

2) RSS 不穩定性：運動的物體、周圍環境中電磁波等的不斷變化，天線的方向性和射頻干擾等，都會導致WiFi 信號的大幅波動。因此，在測試階段采集到的某個位置的指紋可能與訓練階段中收集到的指紋不匹配。

3)待定位點處數據采集時間短：通常可以通過采集某個待定位點處大量的RSS 數據，然后利用這些數據來獲得較穩定的指紋數據。但是，由于定位目標在定位時處于移動狀態，該目標在某一定位點處停留的時間較短，這就導致在測量階段，每個待定位點處的RSS 數據采集通常少于2 s。在這段時間內，只能收集到少量的RSS 數據，這會影響定位的精度。

4)繁重的初始訓練階段：良好的指紋數據庫可以大大提升定位的精確度。構建高精度的指紋數據庫，需要大量的RP[17]和大量的數據，這既費時又費力。

由于用戶在室內環境中的移動速度和移動范圍是有限制的，基于距離范圍限定的KNN 算法(location range limitK-nearest neighbor，LRLKNN)是通過利用參考點和錨點(用戶的先前位置)之間的物理距離組成的懲罰函數，在計算指紋距離時加入該懲罰函數，從而達到目標位置的估計。該方法可以減小空間歧義性問題。

此外，本文通過使用直方圖和多個指紋的組合，例如均值、RSS 的差異、RSS 的等級等，以降低RSS 數據的不穩定性并提高定位精度。

2 室內定位系統模型

2.1 WiFi 室內定位場景

WiFi 指紋定位系統通常分為2 個階段：訓練階段(離線階段)和測試階段(在線階段)。在訓練階段，將收集到的每個RP 位置處的WiFi 信號強度和這些RP 對應的位置坐標存儲到數據庫中。在這里，假設采樣區域有P個接入點(access point，AP)和M個RP。對于第i個RP，其位置坐標li(xi,yi)處對應的指紋數據矢量可以表示為是位置i處的第j個RSS。在訓練階段，可以在每個參考點處采集多組RSS 指紋數據，以此來提高指紋庫的穩定性。測試階段，利用待定位點處采集到的指紋數據，通過指紋匹配算法，來實現位置的推算。

2.2 經典KNN 算法

利用式(1)計算當前測試點l的指紋數據與數據庫中每個RP 數據之間的指紋距離：

式中：fj是測試位置i處的第j個指紋特征；N是可用指紋特征的數量。然后選擇距離最小的K個位置作為該位置的最近鄰位置數據。最后，通過取所有K個最近鄰位置的平均值來確定用戶的位置l。

2.3 基于位置范圍限定的KNN 算法(LRL-KNN)

由于用戶的移動速度受到限制，并且在連續的測量時間內，用戶無法從一個位置移動到另一個距離該位置很遠的位置。故此，最簡單的形式就是通過利用用戶先前的位置信息，以該位置坐標為原點畫圓，以期將最近鄰數據限制在該圓內，該限制圓的半徑可由用戶2 次連續測量之間的移動速度和持續時間確定。本文沒有使用該硬性的范圍限制條件，而是在指紋距離計算中設計了一種新穎的距離范圍限制因素，在該距離范圍內用戶先前位置附近的位置被賦予更高的可選擇性，使其可以成為K個最近鄰的候選對象之一。為此，可以將式(1)修改為

為了進一步提升定位精度，本文在如下2 個方面進行了改進：

1)指紋組合：WiFi 指紋方法中，指紋越穩定，定位精度越好。然而，由于動態變化的環境(例如人為阻擋和移動、來自其他設備的干擾、接收器天線方向等)，客戶端設備收集的RSS 經常會經歷較大的波動。因此，本文提出使用一組不同指紋的組合來確保每個位置具有足夠的穩定性和獨特的值。最常用的指紋是RSS 的平均值，該平均值由于前面提到的影響而顯出波動。相反，更可靠的指紋之一是一對AP 之間RSS 的平均差。Dong等[18]使用2 個設備，即筆記本電腦和智能手機，在固定位置收集RSS。

2)RSS 直方圖：如上所述，某個位置的原始RSS 讀數不穩定，波動幅度最大可達10 dB[19]。因此，它們可能無法很好地代表每個位置的RSS 數據。為了降低這個問題帶來的影響，可以在指紋距離計算中加入RSS 的直方圖，該直方圖定義了第j個AP 的原始RSS 讀數在RP 處落入[Rj?0.5 dBm,Rj+0.5 dBm]的概率。計算方法為

最終指紋距離為

3 實驗與分析

實驗選擇的位置是一個15 m×25 m的矩形實驗室。房間的西南角作為坐標原點。東方向是x軸的正方向，北方向是y軸的正方向，在房間的外圍邊緣部署了6 個無線路由器組成6 個AP。這6 個AP 節點的坐標分別為：(0，0)，(12.5，0)，(25，0)，(0，15)，(12.5，15)，(25，15)。6 個AP 的SSID 用于區分在同一位置處接收到的信號強度。房間被分成1×1的網格，并且信號在采樣設備上被接收。信號強度采樣軟件可在每個網格的頂點(共375 個RP)上采樣RSS 值，每個RP 持續3 min，然后在此期間將每個AP 的RSS 平均值作為AP 在RP 的信號強度值。在每個RP 分別采集各個AP發射的RSS 值。需要注意的是，實驗人員在每個RP 采集RSS 信號強度時，由于工作人員在實驗環境中測量時會干擾信號強度，所以采集數據時需要在每一個RP 分別采集東南西北4 個方向的信號強度，然后對其取平均值，最后將處理后的數據及RP 位置坐標存入指紋數據庫。室內RP 的分布情況如圖1 所示。

圖1 室內RP 分布情況

在測試階段，對行人移動時的數據進行采集，當人在該區域環境內移動時，設備可以記錄該行人在室內某位置處的AP 指紋以及其他相關信息。

KNN 在位置指紋定位中需要確定最優的K值，因為不同的K值對定位的結果也有影響，最優的K值往往能降低定位誤差。找到最優的K值后，選取K個最近鄰指紋，并對這K個指紋的位置坐標求平均，以獲得定位結果。如何選擇最優超參數K是降低算法計算效率的關鍵。通過對數據進行預處理和交叉驗證，可以繪制超參數K和評分之間的關系曲線。如圖2 所示，可以看出，K通常取小于20 的整數。在本文的實驗中，K取14。

圖2 超參數K 的曲線

在圖3 中，對比了KNN 算法、SVM 算法、聚類的KNN（clusterK-nearest neighbor，CKNN）算法[20]和本文提出的LRL-KNN 算法在定位時的誤差累計曲線，所有算法均使用RSS 的平均值作為指紋，連續采樣時間間隔t=1 s。

圖3 距離的誤差累計曲線

從圖中可以看出，LRL-KNN 算法的誤差累計曲線的曲率相比其它三者表現得更好。新算法的平均定位誤差為1.80 m，而KNN 算法的平均定位誤差為2.13 m，SVM 的平均定位誤差為2.36 m，CKNN 算法的平均定位誤差為2.20 m。

從表1 中可以看出，LRL-KNN 定位算法的平均定位誤差為1.80 m，相比于KNN 算法，平均定位精度提升了15.6%；相比于SVM 算法，平均定位精度提升了23.7%；相比于CKNN 算法，平均定位精度提升了17.4%。誤差≤2 m 所占比誤差≤3 m所占比率都高于其它3 種方法。從定位時間上看，LRL-KNN 算法雖然在定位時間上略遜于CKNN，但是它的定位精度卻比CNN 高很多。

表1 各個算法的誤差比

4 結論

通過上面的分析與論證，得出如下結論：

1)本文提出的基于位置范圍限定的WiFi-KNN室內定位算法，在平均定位精度上優于KNN、CKNN 和SVM 算法。

2)本文提出的方法在定位時間上相較于傳統的KNN 方法和SVM 方法有所縮短，但是定位的時間相比于CKNN 來說還是較長。

3)從整體定位性能上來看，LRL-KNN 定位的性能在這些方法中是最好的。雖然本文提出的方法在定位精度上是最高的，但是定位所花費的時間卻不是最短的，如何在保證定位精度的情況下減小定位的時長也是值得去研究的一個方向。