基于改進(jìn)WKNN的位置指紋室內(nèi)定位算法

陳 空，宋春雷，陳家斌，楊黎明，尹靜源

(1.廣州匯智通信技術(shù)有限公司，廣州510000；2.北京理工大學(xué) 自動化學(xué)院，北京100081； 3.華北光學(xué)儀器有限公司，北京100053；4.北京機(jī)電工程總體設(shè)計部，北京100039)

基于改進(jìn)WKNN的位置指紋室內(nèi)定位算法

陳 空1,2，宋春雷2，陳家斌2，楊黎明3，尹靜源4

(1.廣州匯智通信技術(shù)有限公司，廣州510000；2.北京理工大學(xué) 自動化學(xué)院，北京100081； 3.華北光學(xué)儀器有限公司，北京100053；4.北京機(jī)電工程總體設(shè)計部，北京100039)

位置指紋算法是目前解決室內(nèi)定位問題的主要方法，指紋特征和匹配算法為影響算法精度的兩大因素。針對室內(nèi)復(fù)雜環(huán)境下Wi-Fi信號強(qiáng)度波動較大的現(xiàn)象，提出了基于方差的加權(quán)距離以改進(jìn)WKNN算法。在離線特征提取階段，選擇了均值和方差兩個特征值，既反映該采樣點(diǎn)的RSS幅值，也反映該點(diǎn)RSS的波動情況；在線階段，根據(jù)方差提出了加權(quán)距離進(jìn)行相似度的計算，查找距離最近的K近鄰點(diǎn)，并以實(shí)際環(huán)境下采集的數(shù)據(jù)驗證了改進(jìn)WKNN算法在RSS波動大的情況下對定位效果的改善，在綜合考慮了AP組合的影響后，實(shí)現(xiàn)了誤差均值為1.456m的定位效果。

室內(nèi)定位；位置指紋；接收信號強(qiáng)度；加權(quán)KNN

0 引言

隨著智能移動終端的迅猛發(fā)展，基于位置的服務(wù)(Location Based Services, LBS)有了越來越廣泛的應(yīng)用，人們對位置信息及時、快速、準(zhǔn)確獲取的需求也越來越強(qiáng)烈。在室外開放性場所，定位技術(shù)的發(fā)展較為成熟，借助于全球衛(wèi)星定位系統(tǒng)以及移動通信網(wǎng)絡(luò)的廣泛普及，LBS已經(jīng)能為用戶提供高精度、高穩(wěn)定性的位置服務(wù)，并廣泛應(yīng)用于人們的生活。然而人類活動更多的是在室內(nèi)環(huán)境，如教學(xué)樓、圖書館、機(jī)場、停車場、倉庫、超市等，室內(nèi)定位技術(shù)的研究對實(shí)現(xiàn)全球室內(nèi)外無縫定位具有重要意義[1]。

Wi-Fi作為無線接入技術(shù)，它的流行為基于Wi-Fi的定位技術(shù)創(chuàng)造了條件。Wi-Fi 網(wǎng)絡(luò)基礎(chǔ)設(shè)施部署十分便捷且成本低廉，在城市中人類活動的熱點(diǎn)區(qū)域，基本都實(shí)現(xiàn)了Wi-Fi覆蓋。這種依托于Wi-Fi網(wǎng)絡(luò)的定位技術(shù)具有系統(tǒng)成本低、終端數(shù)量巨大、傳輸速率高且通信能力良好等優(yōu)點(diǎn)，是室內(nèi)定位技術(shù)的研究熱點(diǎn)[2]。

相較于室外環(huán)境的開闊，室內(nèi)定位的環(huán)境更為復(fù)雜，Wi-Fi信號的非視距傳播(NLOS)和多徑效應(yīng)使得傳統(tǒng)的TOA、TDOA、AOA等幾何定位技術(shù)的精度受限，而時間和角度測量需要添加相應(yīng)的硬件設(shè)備，成本較高且不利于定位算法的推廣[3]。

位置指紋算法采用終端可直接測量的接收信號強(qiáng)度(RSS)信息，利用位置不同的采樣點(diǎn)由NLOS和多徑效應(yīng)造成的RSS差異構(gòu)建唯一的位置指紋。待定位點(diǎn)通過指紋匹配實(shí)現(xiàn)位置估計，在Wi-Fi覆蓋率足夠的情況下，無需任何硬件的添加，通過純軟件即可實(shí)現(xiàn)定位，具有低成本、高精度的優(yōu)點(diǎn)。

本文設(shè)計了一種改進(jìn)的位置指紋室內(nèi)定位算法，針對接入點(diǎn)信號強(qiáng)度不穩(wěn)定的無線接入點(diǎn)(AP)，提出了一種WKNN的改進(jìn)算法，根據(jù)采樣點(diǎn)信號強(qiáng)度分布的方差信息，設(shè)計了距離的計算權(quán)值，通過加權(quán)距離計算定位點(diǎn)相似性，以削弱RSS不穩(wěn)定的接入點(diǎn)對距離計算的影響，并進(jìn)行了實(shí)驗驗證。

1 位置指紋算法

位置指紋算法[4]的基本思想是：將定位區(qū)域離散化，采集每個離散點(diǎn)的RSS信息，提取RSS特征向量作為其唯一的指紋信息，根據(jù)所有離散點(diǎn)的特征向量構(gòu)建一個位置指紋庫，與實(shí)際物理位置一一對應(yīng)，稱其為Radio Map。定位時，通過匹配算法找到Map中與待定位點(diǎn)RSS特征相似度最高的點(diǎn)進(jìn)行位置估計。

位置指紋定位算法的實(shí)現(xiàn)一般分為離線訓(xùn)練階段和在線匹配階段，具體流程如圖1所示。

圖1 位置指紋定位流程圖Fig.1 The flow chart of fingerprint algorithm

離線階段的主要工作有：

1)為定位區(qū)域選取合適的采樣點(diǎn)(Sample Point)密度，將連續(xù)的定位區(qū)域離散格點(diǎn)化，通過采集設(shè)備對所有的樣本點(diǎn)進(jìn)行RSS信息采集并存入數(shù)據(jù)庫。

2)RSS信息的離群值剔除等預(yù)處理工作，并利用處理后的數(shù)據(jù)進(jìn)行特征提取[5]，建立Radio Map。

利用RSS特征值建立的Radio Map應(yīng)該具有如下形式

(1)

在線階段采集待定位點(diǎn)實(shí)時的RSS信號向量，通過匹配算法實(shí)現(xiàn)位置估計。

匹配算法采用近鄰法，近鄰法分為最近鄰算法(NearestNeighborhood,NN)、K近鄰法(KNearestNeighborhood,NN)和基于K近鄰法改進(jìn)的加權(quán)K近鄰法(KWeightedNearestNeighborhood,W-KNN)?？偟膩碚f，近鄰法都是通過采集移動終端實(shí)時接收的Wi-Fi信號強(qiáng)度，組成待定位點(diǎn)的RSS向量，計算與指紋庫中各個采樣點(diǎn)對應(yīng)的RSS向量的相似度，確定相似度最高的一個或幾個采樣點(diǎn)，采用平均或者加權(quán)平均各個采樣點(diǎn)的位置得出用戶的位置估計：

(2)

2 基于加權(quán)距離的WKNN算法

由于室內(nèi)環(huán)境中墻壁隔斷、人員流動、同頻干擾等復(fù)雜環(huán)境的影響，采樣點(diǎn)上采集到的RSS會有一定程度的波動，而對發(fā)射信號功率穩(wěn)定性差的AP，這種波動尤為明顯。針對信號強(qiáng)度不穩(wěn)定的AP提出了一種改進(jìn)的WKNN算法進(jìn)行匹配。

近鄰匹配算法的核心在于尋找與待定位點(diǎn)的RSS向量相似度最高的一個或幾個采樣點(diǎn)，而相似性的度量方式將影響最終的定位結(jié)果。

2.1 歐氏距離

傳統(tǒng)的WKNN算法通過計算待定位點(diǎn)與指紋庫中樣本點(diǎn)的歐氏距離，尋找距離最小的K個點(diǎn)。

若待定位點(diǎn)j接收到N個AP的信號強(qiáng)度均值如式(3)

(3)

則待定位點(diǎn)i與采樣點(diǎn)j的歐氏距離dij為兩點(diǎn)在N個AP上的信號強(qiáng)度均值之差的平方和，如式(4)

(4)

使用歐氏距離進(jìn)行相似性計算時，距離反映的是各個AP信號強(qiáng)度的差異，理想情況下為物理位置越接近的點(diǎn)，RSS之間的差值就越小。但是，實(shí)際情況中，信號強(qiáng)度的差值不一定完全由物理位置的遠(yuǎn)近造成，也可能由信號強(qiáng)度自身的波動造成，使得歐氏距離并不能真實(shí)反映實(shí)際的物理距離。

2.2 基于方差的加權(quán)距離

改進(jìn)的WKNN算法使用了加權(quán)距離來尋找K個近鄰點(diǎn)，權(quán)值的選取與指紋庫中樣本點(diǎn)的方差相關(guān)。

1)方差特征的提取

在離線階段建立指紋庫時，為了使指紋庫中每個采樣點(diǎn)的特征更為真實(shí)地反映其對應(yīng)物理位置的RSS特征，會在每個采樣點(diǎn)上進(jìn)行多次的樣本采集。每個采樣點(diǎn)接收到每個AP的信號強(qiáng)度信息都是一個樣本集，包含了在該點(diǎn)多次采集的信號強(qiáng)度，如采樣點(diǎn)j接收到第t個AP的信號強(qiáng)度信息集為

(5)

其中，Z為每個采樣點(diǎn)的樣本量。

圖2 指紋庫特征提取Fig.2 Feature extraction for Radio Map

指紋庫中任意采樣點(diǎn)j的RSS向量為

其中，N為AP的個數(shù)。

由此，每個采樣點(diǎn)的信息RSSj包含一個接收信號強(qiáng)度均值的向量rssj和一個接收信號強(qiáng)度方差的向量σj，二者如式(6)

(6)

2)加權(quán)距離的計算

加權(quán)歐氏距離是針對簡單歐氏距離缺點(diǎn)的一種改進(jìn)方案，相當(dāng)于為n維向量的不同維度賦予了不同權(quán)重，權(quán)重與該采樣點(diǎn)RSS的方差相關(guān)，使用加權(quán)距離計算待定位點(diǎn)i與采樣點(diǎn)j的距離dij

(7)

(8)

方差反映樣本數(shù)據(jù)分布的離散程度，方差大的采樣點(diǎn)，RSS的波動越大，樣本集中的樣本點(diǎn)與均值差異較大的可能性也越高；方差小的采樣點(diǎn)，RSS的分布越集中，任意時刻的信號強(qiáng)度都不會脫離均值太遠(yuǎn)。

使用加權(quán)歐氏距離進(jìn)行相似性計算時，將方差的倒數(shù)作為系數(shù)加入到距離的計算中，降低方差大的AP的接收信號強(qiáng)度在距離計算時所占的權(quán)重，能一定程度上消除部分RSS波動帶來的影響，提高最終的定位精度。

3 仿真與驗證

3.1 實(shí)驗平臺

整個Wi-Fi環(huán)境搭建都在學(xué)校教學(xué)樓內(nèi)，包括3個房間——會議室(左上)、老師辦公室(左下)和學(xué)生實(shí)驗室(右下)，和其間的走廊，是一個寬14m、長13m左右的室內(nèi)區(qū)域，平面圖如圖3所示。

圖3 定位區(qū)域室內(nèi)平面圖Fig.3 The indoor location area plan

定位區(qū)域內(nèi)不同方位的采樣點(diǎn)可掃描到的無線接入點(diǎn)的個數(shù)和種類都略有不同，選擇了大部分采樣點(diǎn)都能掃描到的9個AP，型號分別為NETGEARJNR3300、D-LinkDIR-81、TL-WR2041N，前兩種為構(gòu)成樓內(nèi)原有的無線網(wǎng)絡(luò)環(huán)境的AP，后一種是為了實(shí)現(xiàn)整個定位區(qū)域Wi-Fi的無縫隙覆蓋所添加的AP。采集終端為聯(lián)想智能手機(jī)LenovoA789，通過內(nèi)置的網(wǎng)卡和自主編寫的采集程序進(jìn)行采集，軟件界面如圖4所示。

圖4 手機(jī)采集軟件界面Fig.4 The interface of Wi-Fi signal acquisition software on Android phone

采集軟件可以實(shí)現(xiàn)對終端所有可搜索到的Wi-Fi信號進(jìn)行可控次數(shù)的主動掃描，獲取SSID、RSS以及Mac地址等信息，并將其存入指定文件。終端采樣速度不確定，幅值在2次/s～3次/s之間。

根據(jù)定位需求和實(shí)際環(huán)境的分布，以平面圖所示的方向建立坐標(biāo)系，以第一個采樣點(diǎn)的位置為原點(diǎn)，在待定位區(qū)域建立密度為1.2×1.2的網(wǎng)格采樣密度分布。整個數(shù)據(jù)采集過程中，并未刻意排除人員等利用采集到的采樣點(diǎn)的信號強(qiáng)度特征建立位置指紋。定位時，利用待定位點(diǎn)的信號強(qiáng)度信息與網(wǎng)格采樣點(diǎn)，進(jìn)行相似度匹配，以此定位。

樣本點(diǎn)和測試點(diǎn)分布如圖5所示，藍(lán)點(diǎn)為樣本點(diǎn)，每次采集的數(shù)據(jù)樣本量為50條，紅點(diǎn)為測試點(diǎn)，采集的數(shù)據(jù)樣本量為10條，共77個采樣點(diǎn)和64個測試點(diǎn)。

圖5 定位區(qū)域樣本點(diǎn)和測試點(diǎn)分布圖Fig.5 The distribution of sample point and test point in location area

3.2 數(shù)據(jù)預(yù)處理

室內(nèi)Wi-Fi的RSS具有很大的不確定性，采集過程中可能受到類似人員的流動、門的開閉等突發(fā)性的事件影響。在每個采樣點(diǎn)具有一定樣本量時，突發(fā)事件帶來的RSS值的跳變可以通過數(shù)據(jù)對離群值的預(yù)處理進(jìn)行濾除，一定程度上消除突變事件的影響，有助于建立更精確且反映實(shí)際信號特征的RadioMap。

離群值是指距離樣本其他觀察量較遠(yuǎn)的一個或幾個觀測量。常用的離群值剔除方法[6]有3σ檢測法、格拉布斯(Grubbs)檢測法和狄克孫(Dixon)檢測法。本文主要采用3σ檢測法進(jìn)行預(yù)處理。

圖6、圖7為RSS的幅值變化曲線的對比，前者為使用3σ法去除離群值前，后者為去除離群值后。

圖6 數(shù)據(jù)預(yù)處理前RSS的變化曲線Fig.6 The RSS curve before data pre-processing

圖7 數(shù)據(jù)預(yù)處理RSS的變化曲線Fig.7 The RSS curve after data pre-processing

由圖6和圖7可見，RSS數(shù)據(jù)在進(jìn)行預(yù)處理前，存在一個脫離大部分樣本點(diǎn)的離群值，幅值為-77dBm；通過預(yù)處理成功地剔除了該離群值。

3.3 基于加權(quán)距離的WKNN算法

本次實(shí)驗對比了利用歐氏距離進(jìn)行相似性度量的WKNN和本文所提出的利用加權(quán)距離進(jìn)行相似性度量的改進(jìn)WKNN對最終定位效果的影響。

實(shí)驗設(shè)備選擇了方差較大、分布較為不穩(wěn)定的5個AP的RSS信息作為匹配的RadioMap，通過對比幾個測試點(diǎn)的定位效果如圖8所示以及所有測試點(diǎn)的定位誤差累積分布曲線如圖9所示，展示了兩種距離計算方法的定位誤差分布情況。

圖8 WKNN和改進(jìn)WKNN定位效果對比Fig.8 Comparison of location result between WKNN and improved WKNN

圖8顯示了兩個測試點(diǎn)以及WKNN算法和改進(jìn)WKNN算法在K個近鄰點(diǎn)選擇上的不同結(jié)果和對最終定位效果帶來的影響。可以看出，基于加權(quán)距離的WKNN算法有更好的定位效果。

為了驗證改進(jìn)算法對定位效果有普遍性提高，對所有測試點(diǎn)的定位誤差進(jìn)行統(tǒng)計，定位誤差累積分布函數(shù)如圖10所示。累積分布函數(shù)能描述變量的概率分布情況，它表示變量小于或等于某個數(shù)值的概率即F(x)=P(X≤x)，定位誤差累積分布曲線上的點(diǎn)表示定位誤差小于x的概率。

圖9 誤差累積分布對比圖Fig.9 The error CDF comparisons chart between WKNN and the improved WKNN

圖10 定位誤差曲線Fig.10 The error curve comparisons chart of WKNN and the improved WKNN

從圖8、圖9、圖10和表1都可以明顯看出，當(dāng)定位使用的AP的信號強(qiáng)度變化劇烈、分布不集中時，基于加權(quán)距離的改進(jìn)WKNN算法的定位效果優(yōu)于一般的WKNN算法。定位誤差的最大值從10.14減小到了6.54，誤差均值減小了0.72m，方差降到了1.3368。從分布上看，改進(jìn)WKNN的誤差集中在了1～4m的區(qū)間，幾乎沒有6m以上的誤差，由此可以得出當(dāng)使用的AP分布特性較為分散時，基于加權(quán)距離的改進(jìn)WKNN算法有利于提高定位精度。

表1 WKNN與改進(jìn)WKNN定位誤差比對表

3.4 不同AP組合方式的影響

前次實(shí)驗只選取了方差較大的5個AP進(jìn)行定位，實(shí)際大部分采樣點(diǎn)都能采集到9個AP的信號強(qiáng)度信息，為了探究不同AP組合方式建立的Radio Map對最終定位的影響，使用改進(jìn)的WKNN算法在4種AP組合方式下進(jìn)行匹配定位。具體的，Map1選擇了4個AP，每個房間分布1個；Map2選擇了定位區(qū)域內(nèi)的6個AP；Map3選擇了自主布置的5個AP和學(xué)校布置的2個AP；Map4為所有AP。所有組合方式的定位誤差累積分布函數(shù)如圖11，定位誤差的均值、最大值、最小值和方差參數(shù)如表2。

圖11 不同AP組合方式對定位效果的影響Fig.11 The influence of different AP combinations on location effect

表2 不同AP組合方式定位誤差參數(shù)對比

從圖11和表2中可以看出，在Map3的組合下，匹配算法具有總體來說最好的定位效果，90%的測試點(diǎn)定位誤差在2.542m以下，誤差均值為1.4564m，最大值為3.7127m。

顯而易見，定位時Radio Map所包含的信息越多，AP的個數(shù)越多，定位效果也就越好，但當(dāng)該定位區(qū)域AP過多且位置靠近時，可能會出現(xiàn)AP信息的冗余，多余的信息會對相似性的計算造成干擾，最終影響定位精度。因此，定位時需要選擇分布較為分散，且能很好反映不同區(qū)域特征的AP進(jìn)行Radio Map的建立，以在最小的計算復(fù)雜度下有最高的定位精度。

4 結(jié)論

針對信號強(qiáng)度分布不穩(wěn)定的AP，提出了一種WKNN的改進(jìn)算法作為匹配算法，在指紋庫中添加了方差作為衡量AP信號可信度的特征。根據(jù)方差信息，以歸一化的方差倒數(shù)作為近鄰算法的距離計算中向量各個維度的權(quán)值，權(quán)值的選取削弱了RSS不穩(wěn)定的接入點(diǎn)對距離計算的影響。在學(xué)校教學(xué)樓內(nèi)搭建了Wi-Fi定位的實(shí)驗環(huán)境，建立了與物理空間對應(yīng)的Radio Map，通過實(shí)際數(shù)據(jù)驗證了改進(jìn)算法在AP信號穩(wěn)定性差的情況下可以提高定位精度，并對比探討了AP的組合方式對定位效果的影響。

最終實(shí)現(xiàn)在14m×13m的定位區(qū)域內(nèi)，定位誤差均值為1.4564m，最大值為3.7127m，90%的測試點(diǎn)定位誤差在2.542m以下的定位效果。

在Wi-Fi信號廣泛普及的室內(nèi)環(huán)境中，基于Wi-Fi的室內(nèi)定位技術(shù)因其無需硬件添加、系統(tǒng)成本低等優(yōu)點(diǎn)，成為室內(nèi)定位方法的重要發(fā)展方向。而Wi-Fi信息受環(huán)境影響大、不穩(wěn)定性的特點(diǎn)是限制Wi-Fi定位精度的主要因素。本文提出的基于加權(quán)距離的WKNN算法，將信號的波動特征通過方差進(jìn)行量化并作為權(quán)值加入定位算法的距離計算中，有效地降低了Wi-Fi信號不穩(wěn)定性對定位效果的影響，提高了定位精度，且僅需要在離線階段增加一定數(shù)量的信號強(qiáng)度樣本的采集并提取方差加入距離計算，易于實(shí)現(xiàn)，具有一定的實(shí)用價值。

[1] 鄧中亮, 余彥培.室內(nèi)外無線定位與導(dǎo)航[M].北京郵電大學(xué)出版社, 2013：1-2.

[2] 楊錚，吳陳沭，劉云浩.位置計算：無線網(wǎng)絡(luò)定位與可定位性[M].清華大學(xué)出版社,2014：113-115.

[3] 萬群，郭賢生，陳章鑫.室內(nèi)定位理論、方法和應(yīng)用[M].北京：電子工業(yè)出版社，2012：34-36.

[4] Chhavi Sharma, Yew Wong, Soh Fai.Access point placement for fingerprint-based localization[C]//12thIEEE International Conference on Communication Systems，2010: 238-243.

[5] 張興.WLAN室內(nèi)定位信號特征提取算法研究[D].哈爾濱工業(yè)大學(xué), 2013.

[6] 熊艷艷, 吳先球.粗大誤差四種判別準(zhǔn)則的比較和應(yīng)用[J].大學(xué)物理實(shí)驗, 2010, 23(1):66-68.

An Indoor Location Fingerprint Algorithm Based on Improved WKNN

CHEN Kong1,2, SONG Chun-lei2,CHEN Jia-bin2, YANG Li-ming3, YIN Jing-yuan4

(1.Guangzhou Huizhi Intelligence Communications Technology Co.Ltd, Guangzhou 510000, China; 2.School of Automation, Beijing Institute of Technology, Beijing 100081, China; 3.Huabei Optical Instrument Co.Ltd,Beijing 100053, China; 4.Beijing Electro-mechanical Engineering System Design Department, Beijing 100039, China)

Location fingerprint is the main technique to solve the problem of indoor positioning, which is affected by the extraction of fingerprint feature and the matching algorithm.As the fluctuation of Wi-Fi signal strength in complex indoor environment, a weighted distance based on variance to improve WKNN is proposed. On the offline feature extraction stage, the mean and variance of data set as a characteristic is selected, which can not only reflects the magnitude of the RSS of sampling point, but also the fluctuation.On-line stage, a weighted distance based on variance is presented to calculate the similarity and find the nearest K neighbors points.In an actual Wi-Fi environment, the improved WKNN algorithm is verified to improve the performance of the algorithm in the case of large fluctuation of RSS.Finally, after considering the impact of APs, the mean error of position is 1.456m.

Indoor location; Location fingerprint; RSS; WKNN

10.19306/j.cnki.2095-8110.2016.04.011

2015-09-16；

2015-12-26。

陳空(1992-)，女，碩士，主要從事基于WI-FI的室內(nèi)定位方面的研究。E-mail:ckong1992@163.com

TN92

A

2095-8110(2016)04-0058-07