基于位置范圍限定的WiFi-KNN 室內(nèi)定位算法

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

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

1 WiFi 指紋的室內(nèi)定位方法

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

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

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

本文針對KNN 算法進(jìn)行了進(jìn)一步的研究，因?yàn)樗哂休^低的復(fù)雜度，更適合于實(shí)際生活中的使用。通常，KNN 算法需要計(jì)算當(dāng)前測量的指紋數(shù)據(jù)與數(shù)據(jù)庫中的各個指紋數(shù)據(jù)之間的距離，然后通過排序來確定K個距離最近的參考點(diǎn)，然后通過加權(quán)平均估算待定位點(diǎn)的位置。在KNN 中計(jì)算指紋距離時可以使用不同的距離度量，例如歐幾里得距離、曼哈頓距離和馬哈拉諾比斯距離等[16]。

盡管KNN 算法已在各類文獻(xiàn)中進(jìn)行了廣泛研究，但KNN 仍然面臨以下挑戰(zhàn)：

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

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

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

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

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

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

2 室內(nèi)定位系統(tǒng)模型

2.1 WiFi 室內(nèi)定位場景

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

2.2 經(jīng)典KNN 算法

利用式(1)計(jì)算當(dāng)前測試點(diǎn)l的指紋數(shù)據(jù)與數(shù)據(jù)庫中每個RP 數(shù)據(jù)之間的指紋距離：

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

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

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

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

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

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

最終指紋距離為

3 實(shí)驗(yàn)與分析

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

圖1 室內(nèi)RP 分布情況

在測試階段，對行人移動時的數(shù)據(jù)進(jìn)行采集，當(dāng)人在該區(qū)域環(huán)境內(nèi)移動時，設(shè)備可以記錄該行人在室內(nèi)某位置處的AP 指紋以及其他相關(guān)信息。

KNN 在位置指紋定位中需要確定最優(yōu)的K值，因?yàn)椴煌腒值對定位的結(jié)果也有影響，最優(yōu)的K值往往能降低定位誤差。找到最優(yōu)的K值后，選取K個最近鄰指紋，并對這K個指紋的位置坐標(biāo)求平均，以獲得定位結(jié)果。如何選擇最優(yōu)超參數(shù)K是降低算法計(jì)算效率的關(guān)鍵。通過對數(shù)據(jù)進(jìn)行預(yù)處理和交叉驗(yàn)證，可以繪制超參數(shù)K和評分之間的關(guān)系曲線。如圖2 所示，可以看出，K通常取小于20 的整數(shù)。在本文的實(shí)驗(yàn)中，K取14。

圖2 超參數(shù)K 的曲線

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

圖3 距離的誤差累計(jì)曲線

從圖中可以看出，LRL-KNN 算法的誤差累計(jì)曲線的曲率相比其它三者表現(xiàn)得更好。新算法的平均定位誤差為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 結(jié)論

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

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

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

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