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

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

基于改進WKNN的位置指紋室內定位算法

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

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

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

室內定位；位置指紋；接收信號強度；加權KNN

0 引言

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

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

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

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

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

1 位置指紋算法

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

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

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

離線階段的主要工作有：

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

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

利用RSS特征值建立的Radio Map應該具有如下形式

(1)

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

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

(2)

2 基于加權距離的WKNN算法

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

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

2.1 歐氏距離

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

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

(3)

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

(4)

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

2.2 基于方差的加權距離

改進的WKNN算法使用了加權距離來尋找K個近鄰點，權值的選取與指紋庫中樣本點的方差相關。

1)方差特征的提取

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

(5)

其中，Z為每個采樣點的樣本量。

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

指紋庫中任意采樣點j的RSS向量為

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

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

(6)

2)加權距離的計算

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

(7)

(8)

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

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

3 仿真與驗證

3.1 實驗平臺

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 基于加權距離的WKNN算法

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

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

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

圖8顯示了兩個測試點以及WKNN算法和改進WKNN算法在K個近鄰點選擇上的不同結果和對最終定位效果帶來的影響?？梢钥闯?，基于加權距離的WKNN算法有更好的定位效果。

為了驗證改進算法對定位效果有普遍性提高，對所有測試點的定位誤差進行統(tǒng)計，定位誤差累積分布函數(shù)如圖10所示。累積分布函數(shù)能描述變量的概率分布情況，它表示變量小于或等于某個數(shù)值的概率即F(x)=P(X≤x)，定位誤差累積分布曲線上的點表示定位誤差小于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都可以明顯看出，當定位使用的AP的信號強度變化劇烈、分布不集中時，基于加權距離的改進WKNN算法的定位效果優(yōu)于一般的WKNN算法。定位誤差的最大值從10.14減小到了6.54，誤差均值減小了0.72m，方差降到了1.3368。從分布上看，改進WKNN的誤差集中在了1～4m的區(qū)間，幾乎沒有6m以上的誤差，由此可以得出當使用的AP分布特性較為分散時，基于加權距離的改進WKNN算法有利于提高定位精度。

表1 WKNN與改進WKNN定位誤差比對表

3.4 不同AP組合方式的影響

前次實驗只選取了方差較大的5個AP進行定位，實際大部分采樣點都能采集到9個AP的信號強度信息，為了探究不同AP組合方式建立的Radio Map對最終定位的影響，使用改進的WKNN算法在4種AP組合方式下進行匹配定位。具體的，Map1選擇了4個AP，每個房間分布1個；Map2選擇了定位區(qū)域內的6個AP；Map3選擇了自主布置的5個AP和學校布置的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%的測試點定位誤差在2.542m以下，誤差均值為1.4564m，最大值為3.7127m。

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

4 結論

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

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

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

[1] 鄧中亮, 余彥培.室內外無線定位與導航[M].北京郵電大學出版社, 2013：1-2.

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

[3] 萬群，郭賢生，陳章鑫.室內定位理論、方法和應用[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室內定位信號特征提取算法研究[D].哈爾濱工業(yè)大學, 2013.

[6] 熊艷艷, 吳先球.粗大誤差四種判別準則的比較和應用[J].大學物理實驗, 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的室內定位方面的研究。E-mail:ckong1992@163.com

TN92

A

2095-8110(2016)04-0058-07