基于近鄰法的WIFI室內(nèi)定位改進(jìn)算法研究

田家英，張志華

(1.蘭州交通大學(xué) 測(cè)繪與地理信息學(xué)院，甘肅 蘭州 730070；2.甘肅省地理國(guó)情監(jiān)測(cè)工程實(shí)驗(yàn)室，甘肅 蘭州 730070)

隨著無(wú)線電通信技術(shù)、移動(dòng)互聯(lián)網(wǎng)技術(shù)的發(fā)展以及移動(dòng)終端設(shè)備硬件性能的提升，基于位置的服務(wù)(Location Based Service，LBS)正逐漸成為移動(dòng)互聯(lián)網(wǎng)時(shí)代的一顆新星[1]。隨著服務(wù)能力的增強(qiáng)，LBS已在醫(yī)院、商場(chǎng)智能家居等眾多領(lǐng)域發(fā)揮了重要作用。相對(duì)傳統(tǒng)室外定位，室內(nèi)定位環(huán)境復(fù)雜，信號(hào)受建筑物遮擋和多徑效應(yīng)的影響，全球衛(wèi)星導(dǎo)航系統(tǒng)(Global Navigation Satellite System，GNSS)定位精度受到嚴(yán)重制約，無(wú)法滿足室內(nèi)位置服務(wù)的需要。因此，如何提供高質(zhì)量的室內(nèi)位置服務(wù)已經(jīng)成為當(dāng)今的研究熱點(diǎn)。

當(dāng)前，基于藍(lán)牙、紅外線、地磁、超帶寬、WIFI等技術(shù)實(shí)現(xiàn)的室內(nèi)定位系統(tǒng)已在特定的范圍內(nèi)得到一定的應(yīng)用[2]。相對(duì)于其它技術(shù)，覆蓋范圍廣、部署成本低和較高定位精度使得基于WIFI的室內(nèi)定位成為當(dāng)前室內(nèi)定位的主流技術(shù)。國(guó)內(nèi)外學(xué)者針對(duì)WIFI室內(nèi)定位做了大量研究。文獻(xiàn)[3]從目前主流室內(nèi)定位技術(shù)的定位原理、技術(shù)分類體系和定位方法對(duì)室內(nèi)定位做了一個(gè)宏觀的研究。文獻(xiàn)[4]從信號(hào)特征提取上提出改進(jìn)粒子濾波信號(hào)強(qiáng)度提取法，減小噪聲對(duì)定位精度的影響。文獻(xiàn)[5]提出結(jié)合室內(nèi)影響因素約束的權(quán)重改正模型，提高基于三角形定位法的定位精度。文獻(xiàn)[6]針對(duì)室內(nèi)復(fù)雜環(huán)境，提出基于方差的加權(quán)距離改進(jìn)的加權(quán)K近鄰法，得到更高的定位精度。文獻(xiàn)[7]提出基于余弦相似度的指紋匹配算法，在保證定位精度有效的前提下降低指紋匹配算法的復(fù)雜度。現(xiàn)階段，基于位置指紋的WIFI室內(nèi)定位存在離線建庫(kù)工作量大、指紋數(shù)據(jù)受噪聲干擾、指紋匹配算法效率低等問(wèn)題。本文在分析現(xiàn)有基于位置指紋的室內(nèi)定位方法的基礎(chǔ)上，在離線建庫(kù)階段，通過(guò)對(duì)定位區(qū)域空間網(wǎng)格化，基于參考點(diǎn)空間關(guān)系對(duì)指紋數(shù)據(jù)分級(jí)。在線定位階段通過(guò)對(duì)指紋數(shù)據(jù)逐級(jí)匹配，提高匹配效率，減小定位誤差，并通過(guò)實(shí)驗(yàn)進(jìn)行驗(yàn)證。

1 室內(nèi)定位方法概述

目前，室內(nèi)定位技術(shù)從原理上來(lái)講可以分為兩類：基于信號(hào)傳播模型和基于位置指紋的定位[8]?；谛盘?hào)傳播模型的定位方法主要是通過(guò)測(cè)量待測(cè)目標(biāo)與參考節(jié)點(diǎn)之間的距離或角度信息建立合適的數(shù)學(xué)模型(如三角定位模型、圓周定位模型等)

解算出待測(cè)點(diǎn)的位置，常用的測(cè)距方法有基于信號(hào)到達(dá)時(shí)間 (Time of Arrival, TOA)、基于信號(hào)到達(dá)時(shí)間差 (Time Difference of Arrival, TDOA)、基于信號(hào)到達(dá)角度 (Angle of Arrival, AOA)和基于接收信號(hào)強(qiáng)度指示(Received Signal Strength Indication, RSSI)[9]等；基于位置指紋的定位方法不直接依賴待測(cè)目標(biāo)和參考節(jié)點(diǎn)之間的距離或角度關(guān)系，而是將不易測(cè)量的位置信息和容易測(cè)量的信號(hào)特征(如信號(hào)強(qiáng)度)建立映射關(guān)系，間接確定待測(cè)目標(biāo)的空間位置。

2 WIFI位置指紋定位

2.1 WIFI室內(nèi)定位原理

由AP發(fā)射信號(hào)的路徑損耗傳播模型[10]可知，RSSI會(huì)隨著傳播距離的增加逐漸衰減，當(dāng)室內(nèi)存在障礙物時(shí)，信號(hào)會(huì)受到遮擋，強(qiáng)度的衰減也不再規(guī)律，不同位置獲取AP的RSSI也存在差異。通常在某一固定位置，能同時(shí)獲取到多個(gè)AP的RSSI數(shù)據(jù)?；谏鲜鎏匦?，實(shí)現(xiàn)基于WIFI的室內(nèi)定位，按照定位原理可分為兩類，二者比較詳見(jiàn)表1。由于位置指紋算法無(wú)需AP的具體位置和發(fā)射功率信息即可實(shí)現(xiàn)定位，定位方式較為靈活，因此，該方法已經(jīng)成為基于WIFI室內(nèi)定位的主流技術(shù)，本文主要以位置指紋算法原理為基礎(chǔ)對(duì)基于WIFI的室內(nèi)定位技術(shù)進(jìn)行研究。

2.2 位置指紋室內(nèi)定位流程

基于位置指紋定位算法的室內(nèi)定位通常分為兩個(gè)階段：離線建庫(kù)階段和在線定位階段，定位原理如圖1所示。

離線建庫(kù)階段：

1)將連續(xù)的定位區(qū)域離散格點(diǎn)化，選擇合適的采樣間隔設(shè)置參考點(diǎn)并采集參考點(diǎn)處的相關(guān)信息；

2)通常采集到的RSSI數(shù)據(jù)都含有噪聲，通過(guò)高斯濾波、均值濾波等方法對(duì)數(shù)據(jù)進(jìn)行預(yù)處理；

3)將處理后的RSSI信息和空間位置信息建立映射關(guān)系，存入指紋數(shù)據(jù)庫(kù)，建立信號(hào)無(wú)線地圖(Radio Map, RM)。

表1 基于WIFI的室內(nèi)定位技術(shù)比較

在線定位階段：將待測(cè)點(diǎn)處的RSSI信息與指紋數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行匹配，將相似度最高的指紋數(shù)據(jù)對(duì)應(yīng)的位置作為待測(cè)點(diǎn)處的空間位置。常見(jiàn)的指紋定位算法主要有近鄰法、樸素貝葉斯法、最大似然概率法、核函數(shù)法、神經(jīng)網(wǎng)絡(luò)法和支持向量回歸法等[11]。

圖1 位置指紋定位原理

2.3 位置指紋定位算法

在線定位階段，將在待測(cè)點(diǎn)采集到的RSSI信息與指紋庫(kù)中的數(shù)據(jù)進(jìn)行匹配，實(shí)現(xiàn)在線定位。目前用于指紋定位的算法較多，近鄰算法具有實(shí)現(xiàn)簡(jiǎn)單、普適性強(qiáng)且不需要考慮參數(shù)和諸多的假設(shè)問(wèn)題等優(yōu)點(diǎn)，因此，本文選擇近鄰法作為數(shù)據(jù)匹配的算法。

近鄰算法[12]分為最近鄰法(Nearest Neighborhood，NN)、K近鄰法(K Nearest Neighborhood，KNN)和加權(quán)K近鄰法(Weighted K Nearest Neighborhood，WKNN)。NN是求出待測(cè)點(diǎn)處的RSSI向量與指紋庫(kù)的RSSI向量間的矢量歐幾里得距離[13](簡(jiǎn)稱歐式距離)最小的指紋數(shù)據(jù)，將其對(duì)應(yīng)的空間位置信息作為待測(cè)點(diǎn)的位置信息；KNN是在NN的基礎(chǔ)上求出K個(gè)歐式距離最小的指紋數(shù)據(jù)，將其對(duì)應(yīng)的空間位置取平均值作為待測(cè)點(diǎn)的位置信息；單純的求均值無(wú)法有效的表達(dá)K個(gè)指紋數(shù)據(jù)各自所占的權(quán)重，因此WKNN在KNN的基礎(chǔ)上將均值改為權(quán)重，進(jìn)一步提高定位的精度。近鄰算法的核心思想是通過(guò)計(jì)算待測(cè)點(diǎn)處的RSSI向量與指紋庫(kù)中的指紋向量的相似度，將相似度最高的K(K≥1)個(gè)指紋數(shù)據(jù)對(duì)應(yīng)的空間位置求均值或加權(quán)均值的結(jié)果作為待測(cè)點(diǎn)的空間位置，算式為

(1)

3 基于數(shù)據(jù)分級(jí)的位置指紋室內(nèi)定位

3.1 離線建庫(kù)階段

3.1.1 RSSI數(shù)據(jù)預(yù)處理

離線建庫(kù)階段采集參考點(diǎn)處接收到AP的RSSI值，建立RSSI特征向量。由于室內(nèi)環(huán)境較為復(fù)雜，干擾因素較多，采集到的數(shù)據(jù)中存在噪聲影響，RSSI會(huì)出現(xiàn)一些偏差較大的奇異點(diǎn)。因此，本文將采集的RSSI數(shù)據(jù)先進(jìn)行高斯濾波[14]處理，濾除小概率數(shù)據(jù)，然后進(jìn)行均值濾波處理。

高斯濾波處理：由于RSSI受干擾產(chǎn)生波動(dòng)，其總體呈現(xiàn)正態(tài)分布的特點(diǎn)，因此，采用高斯濾波對(duì)RSSI進(jìn)行初步處理，濾除小概率數(shù)據(jù)。通過(guò)實(shí)際環(huán)境采集實(shí)驗(yàn)數(shù)據(jù)，本文選取概率在90%以內(nèi)的數(shù)據(jù)，即RSSI∈(μ-1.65σ,μ+1.65σ)，其中μ為均值，σ為標(biāo)準(zhǔn)差。

(2)

均值濾波處理：將經(jīng)高斯濾波處理后的多個(gè)RSSI值求算術(shù)平均值。

(3)

3.1.2 基于空間位置關(guān)系的數(shù)據(jù)分級(jí)

通常一條指紋數(shù)據(jù)由兩部分組成：參考點(diǎn)處的空間坐標(biāo)信息和多個(gè)AP信號(hào)的RSSI組成的信號(hào)強(qiáng)度向量。本文在此基礎(chǔ)上增加RSSI數(shù)據(jù)級(jí)別，基于參考點(diǎn)的空間位置關(guān)系對(duì)數(shù)據(jù)進(jìn)行分級(jí)。

離線建庫(kù)時(shí)對(duì)定位區(qū)域按照適當(dāng)?shù)拈g隔設(shè)置參考點(diǎn)?；赪IFI路徑損耗傳播模型，本文將參考點(diǎn)設(shè)置如圖2所示(以兩級(jí)數(shù)據(jù)為例)。在指紋數(shù)據(jù)建庫(kù)時(shí)根據(jù)采樣間隔將參考點(diǎn)P1,P3,P5,P11,P13,P15,P21,P23,P25數(shù)據(jù)設(shè)為1級(jí)，其它數(shù)據(jù)設(shè)為2級(jí)。假設(shè)采集第i個(gè)參考點(diǎn)數(shù)據(jù)，需要記錄該點(diǎn)的空間坐標(biāo)位置(xi,yi)和多個(gè)AP信號(hào)的RSSI組成的信號(hào)強(qiáng)度向量RSSIi=(rssi1,rssi2,…,rssin)以及基于空間位置關(guān)系設(shè)置的數(shù)據(jù)級(jí)別level，將坐標(biāo)信息、數(shù)據(jù)級(jí)別和RSSI值建立映射關(guān)系存入數(shù)據(jù)庫(kù)中，如式(4)所示。

(4)

圖2 定位區(qū)域參考點(diǎn)設(shè)置示意圖

3.2 在線定位階段

在線定位階段，將定位終端n次掃描獲取多個(gè)RSSI值進(jìn)行均值濾波處理，得到待測(cè)點(diǎn)處的RSSI強(qiáng)度向量，然后與指紋庫(kù)中數(shù)據(jù)進(jìn)行最近鄰匹配，尋找相似度最高的指紋數(shù)據(jù)。本文實(shí)驗(yàn)中指紋匹配采用WKNN算法，WKNN算法中K的取值影響定位結(jié)果[15]，基于本文數(shù)據(jù)分級(jí)的特性，選擇K=4的WKNN算法進(jìn)行位置求解。

由于指紋數(shù)據(jù)庫(kù)中的數(shù)據(jù)增加了數(shù)據(jù)級(jí)別屬性，改進(jìn)算法后的在線定位流程如下：

1)將待測(cè)點(diǎn)處的RSSI向量數(shù)據(jù)基于NN算法與指紋庫(kù)中數(shù)據(jù)級(jí)別為1的指紋數(shù)據(jù)進(jìn)行計(jì)算，獲取歐式距離最小的前4個(gè)值。4個(gè)指紋數(shù)據(jù)通常會(huì)出現(xiàn)如下3種情況：

(1)分布在以1級(jí)數(shù)據(jù)對(duì)應(yīng)采樣間隔di為邊長(zhǎng)的矩形上，如圖2中P1,P3,P11,P13。

(2)其中3個(gè)指紋點(diǎn)分布在以di為邊長(zhǎng)的矩形上，如圖2中P1,P3,P11,P23，此時(shí)舍棄P23同時(shí)將P13作為補(bǔ)償點(diǎn)。

(3)零散的分布在以2di為邊長(zhǎng)的矩形上，如圖2中P1,P3,P23,P25，若P1歐式距離小于P25，則將P25舍棄，同時(shí)添加P21作為補(bǔ)償點(diǎn)，反之將P1舍棄，添加P5作為補(bǔ)償點(diǎn)。

2)通過(guò)1)中確定4個(gè)歐式距離最小的1級(jí)指紋點(diǎn)，通過(guò)對(duì)應(yīng)的空間位置信息確定最小外包矩形，獲取空間位置在矩形范圍內(nèi)的2級(jí)指紋數(shù)據(jù)。

3)將待測(cè)點(diǎn)處的RSSI向量數(shù)據(jù)與2)中獲取的2級(jí)指紋數(shù)據(jù)匹配，求出歐式距離。

4)將1)中修正后的和2)中計(jì)算得到的歐式距離進(jìn)行排序，選擇歐式距離最小的4個(gè)值，通過(guò)WKNN算法求出待測(cè)點(diǎn)的坐標(biāo)信息。

基于WKNN算法改進(jìn)后的位置指紋在線定位階段流程如圖3所示。

圖3 改進(jìn)后的在線定位流程

4 實(shí)驗(yàn)分析和評(píng)估

針對(duì)本文實(shí)驗(yàn)方案開(kāi)發(fā)設(shè)計(jì)了基于WIFI位置指紋定位系統(tǒng)原型，由于位置指紋匹配是一個(gè)比較消耗資源的過(guò)程，因此系統(tǒng)采用當(dāng)前主流的B/S(Browser/Server，瀏覽器/服務(wù)器模式)架構(gòu)[16]。服務(wù)端以MyEclipse作為開(kāi)發(fā)環(huán)境，采用Java語(yǔ)言編寫(xiě)，開(kāi)發(fā)基于Java+Tomcat+MySQL模式的原型系統(tǒng)?？蛻舳瞬捎肁ndroid系統(tǒng)的小米MI 5S手機(jī)。該系統(tǒng)主要分為兩大功能模塊：離線數(shù)據(jù)采集模塊和在線定位模塊。

4.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)采集

本文選取8 m×12 m的辦公樓大廳作為實(shí)驗(yàn)區(qū)域，實(shí)驗(yàn)區(qū)域內(nèi)不同參考點(diǎn)可以掃描到AP的個(gè)數(shù)存在差異，本文選擇大部分參考點(diǎn)都能掃描到的6個(gè)AP作為RSSI信號(hào)發(fā)射源，參考點(diǎn)間隔1.2 m，選取81個(gè)參考點(diǎn)，18個(gè)測(cè)試點(diǎn)。在采集數(shù)據(jù)過(guò)程中，為盡量減小因單向采集和人體遮擋所帶來(lái)的影響，分別在參考點(diǎn)4個(gè)方向上每次采樣40次，共計(jì)160次，采樣間隔設(shè)為10 s。圖4為室內(nèi)定位原型系統(tǒng)的離線數(shù)據(jù)采集界面。

圖4 離線數(shù)據(jù)采集界面

軟件數(shù)據(jù)采集功能模塊可以自主的設(shè)置采樣間隔、采樣次數(shù)，實(shí)現(xiàn)自動(dòng)采集。采集到的數(shù)據(jù)結(jié)構(gòu)如表2所示。

表2 采樣信息數(shù)據(jù)結(jié)構(gòu)

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

由于室內(nèi)環(huán)境復(fù)雜，存在障礙物等因素，室內(nèi)環(huán)境中采集到WIFI的RSSI信息包含隨機(jī)噪聲。本文先采用高斯濾波處理，濾除小概率數(shù)據(jù)，然后再采用均值濾波處理。雙重濾波處理從一定程度上減少噪聲的影響，使指紋庫(kù)數(shù)據(jù)更能反映實(shí)際信號(hào)特征。圖5為RSSI高斯濾波前后分布對(duì)比圖。通過(guò)圖5可見(jiàn)，RSSI數(shù)據(jù)通過(guò)高斯濾波處理后其概率分布曲線更逼近真實(shí)值分布曲線，經(jīng)高斯濾波后將小概率數(shù)據(jù)濾除，有效的減小高斯噪聲的影響。

圖5 RSSI高斯濾波處理前后分布對(duì)比

4.3 在線定位實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)過(guò)程中通過(guò)位置估計(jì)的精度、可靠度以及鄰近點(diǎn)搜索的可靠度3個(gè)指標(biāo)[17]來(lái)評(píng)價(jià)本次的實(shí)驗(yàn)結(jié)果。定位階段，分別采用WKNN算法和本文提出的改進(jìn)算法進(jìn)行實(shí)驗(yàn)對(duì)比，實(shí)驗(yàn)結(jié)果見(jiàn)圖6。從兩種算法定位對(duì)比分析(見(jiàn)表3)可以看出，改進(jìn)后的算法指紋數(shù)據(jù)匹配次數(shù)大幅減少，平均定位誤差減小0.5 m，有效提高定位精度。

表3 兩種算法定位對(duì)比分析表

圖6 實(shí)驗(yàn)結(jié)果對(duì)比數(shù)據(jù)

5 結(jié)束語(yǔ)

本文在總結(jié)分析當(dāng)前室內(nèi)定位技術(shù)的基礎(chǔ)上，提出了一種基于近鄰法改進(jìn)的室內(nèi)定位算法。離線建庫(kù)階段，使用高斯濾波和均值濾波對(duì)RSSI雙重濾波處理，提高位置指紋數(shù)據(jù)庫(kù)的可信度；通過(guò)對(duì)定位區(qū)域網(wǎng)格化，基于參考點(diǎn)空間分布關(guān)系對(duì)指紋數(shù)據(jù)分級(jí)。在線定位階段，通過(guò)數(shù)據(jù)級(jí)別縮小匹配范圍，減小指紋數(shù)據(jù)匹配工作量的同時(shí)提高定位精度。但基于位置指紋算法實(shí)現(xiàn)的室內(nèi)定位的離線建庫(kù)工作量較大，如何在保證定位精度的前提下減小離線建庫(kù)工作量將是今后的研究方向。