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

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

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

基于WiFi 指紋的室內(nèi)定位方法又可以分為確定性方法和概率性方法[6?7]。確定性方法是利用相似性度量來區(qū)分測(cè)量的信號(hào)數(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)，上述所有的定位方法都需要在離線階段收集指紋信息，然后將其與測(cè)試階段的測(cè)量數(shù)據(jù)進(jìn)行比較來達(dá)到定位的目的。

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 經(jīng)典KNN 算法

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

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

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

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

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

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

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

最終指紋距離為

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

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

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

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

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

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

在圖3 中，對(duì)比了KNN 算法、SVM 算法、聚類的KNN（clusterK-nearest neighbor，CKNN）算法[20]和本文提出的LRL-KNN 算法在定位時(shí)的誤差累計(jì)曲線，所有算法均使用RSS 的平均值作為指紋，連續(xù)采樣時(shí)間間隔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 種方法。從定位時(shí)間上看，LRL-KNN 算法雖然在定位時(shí)間上略遜于CKNN，但是它的定位精度卻比CNN 高很多。

表1 各個(gè)算法的誤差比

4 結(jié)論

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

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

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

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