基于近鄰法的WIFI室內定位改進算法研究

田家英，張志華

(1.蘭州交通大學 測繪與地理信息學院，甘肅 蘭州 730070；2.甘肅省地理國情監測工程實驗室，甘肅 蘭州 730070)

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

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

1 室內定位方法概述

目前，室內定位技術從原理上來講可以分為兩類：基于信號傳播模型和基于位置指紋的定位[8]。基于信號傳播模型的定位方法主要是通過測量待測目標與參考節點之間的距離或角度信息建立合適的數學模型(如三角定位模型、圓周定位模型等)

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

2 WIFI位置指紋定位

2.1 WIFI室內定位原理

由AP發射信號的路徑損耗傳播模型[10]可知，RSSI會隨著傳播距離的增加逐漸衰減，當室內存在障礙物時，信號會受到遮擋，強度的衰減也不再規律，不同位置獲取AP的RSSI也存在差異。通常在某一固定位置，能同時獲取到多個AP的RSSI數據。基于上述特性，實現基于WIFI的室內定位，按照定位原理可分為兩類，二者比較詳見表1。由于位置指紋算法無需AP的具體位置和發射功率信息即可實現定位，定位方式較為靈活，因此，該方法已經成為基于WIFI室內定位的主流技術，本文主要以位置指紋算法原理為基礎對基于WIFI的室內定位技術進行研究。

2.2 位置指紋室內定位流程

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

離線建庫階段：

1)將連續的定位區域離散格點化，選擇合適的采樣間隔設置參考點并采集參考點處的相關信息；

2)通常采集到的RSSI數據都含有噪聲，通過高斯濾波、均值濾波等方法對數據進行預處理；

3)將處理后的RSSI信息和空間位置信息建立映射關系，存入指紋數據庫，建立信號無線地圖(Radio Map, RM)。

表1 基于WIFI的室內定位技術比較

在線定位階段：將待測點處的RSSI信息與指紋數據庫中的數據進行匹配，將相似度最高的指紋數據對應的位置作為待測點處的空間位置。常見的指紋定位算法主要有近鄰法、樸素貝葉斯法、最大似然概率法、核函數法、神經網絡法和支持向量回歸法等[11]。

圖1 位置指紋定位原理

2.3 位置指紋定位算法

在線定位階段，將在待測點采集到的RSSI信息與指紋庫中的數據進行匹配，實現在線定位。目前用于指紋定位的算法較多，近鄰算法具有實現簡單、普適性強且不需要考慮參數和諸多的假設問題等優點，因此，本文選擇近鄰法作為數據匹配的算法。

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

(1)

3 基于數據分級的位置指紋室內定位

3.1 離線建庫階段

3.1.1 RSSI數據預處理

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

高斯濾波處理：由于RSSI受干擾產生波動，其總體呈現正態分布的特點，因此，采用高斯濾波對RSSI進行初步處理，濾除小概率數據。通過實際環境采集實驗數據，本文選取概率在90%以內的數據，即RSSI∈(μ-1.65σ,μ+1.65σ)，其中μ為均值，σ為標準差。

(2)

均值濾波處理：將經高斯濾波處理后的多個RSSI值求算術平均值。

(3)

3.1.2 基于空間位置關系的數據分級

通常一條指紋數據由兩部分組成：參考點處的空間坐標信息和多個AP信號的RSSI組成的信號強度向量。本文在此基礎上增加RSSI數據級別，基于參考點的空間位置關系對數據進行分級。

離線建庫時對定位區域按照適當的間隔設置參考點。基于WIFI路徑損耗傳播模型，本文將參考點設置如圖2所示(以兩級數據為例)。在指紋數據建庫時根據采樣間隔將參考點P1,P3,P5,P11,P13,P15,P21,P23,P25數據設為1級，其它數據設為2級。假設采集第i個參考點數據，需要記錄該點的空間坐標位置(xi,yi)和多個AP信號的RSSI組成的信號強度向量RSSIi=(rssi1,rssi2,…,rssin)以及基于空間位置關系設置的數據級別level，將坐標信息、數據級別和RSSI值建立映射關系存入數據庫中，如式(4)所示。

(4)

圖2 定位區域參考點設置示意圖

3.2 在線定位階段

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

由于指紋數據庫中的數據增加了數據級別屬性，改進算法后的在線定位流程如下：

1)將待測點處的RSSI向量數據基于NN算法與指紋庫中數據級別為1的指紋數據進行計算，獲取歐式距離最小的前4個值。4個指紋數據通常會出現如下3種情況：

(1)分布在以1級數據對應采樣間隔di為邊長的矩形上，如圖2中P1,P3,P11,P13。

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

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

2)通過1)中確定4個歐式距離最小的1級指紋點，通過對應的空間位置信息確定最小外包矩形，獲取空間位置在矩形范圍內的2級指紋數據。

3)將待測點處的RSSI向量數據與2)中獲取的2級指紋數據匹配，求出歐式距離。

4)將1)中修正后的和2)中計算得到的歐式距離進行排序，選擇歐式距離最小的4個值，通過WKNN算法求出待測點的坐標信息。

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

圖3 改進后的在線定位流程

4 實驗分析和評估

針對本文實驗方案開發設計了基于WIFI位置指紋定位系統原型，由于位置指紋匹配是一個比較消耗資源的過程，因此系統采用當前主流的B/S(Browser/Server，瀏覽器/服務器模式)架構[16]。服務端以MyEclipse作為開發環境，采用Java語言編寫，開發基于Java+Tomcat+MySQL模式的原型系統?？蛻舳瞬捎肁ndroid系統的小米MI 5S手機。該系統主要分為兩大功能模塊：離線數據采集模塊和在線定位模塊。

4.1 實驗環境及數據采集

本文選取8 m×12 m的辦公樓大廳作為實驗區域，實驗區域內不同參考點可以掃描到AP的個數存在差異，本文選擇大部分參考點都能掃描到的6個AP作為RSSI信號發射源，參考點間隔1.2 m，選取81個參考點，18個測試點。在采集數據過程中，為盡量減小因單向采集和人體遮擋所帶來的影響，分別在參考點4個方向上每次采樣40次，共計160次，采樣間隔設為10 s。圖4為室內定位原型系統的離線數據采集界面。

圖4 離線數據采集界面

軟件數據采集功能模塊可以自主的設置采樣間隔、采樣次數，實現自動采集。采集到的數據結構如表2所示。

表2 采樣信息數據結構

4.2 數據預處理

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

圖5 RSSI高斯濾波處理前后分布對比

4.3 在線定位實驗結果及分析

實驗過程中通過位置估計的精度、可靠度以及鄰近點搜索的可靠度3個指標[17]來評價本次的實驗結果。定位階段，分別采用WKNN算法和本文提出的改進算法進行實驗對比，實驗結果見圖6。從兩種算法定位對比分析(見表3)可以看出，改進后的算法指紋數據匹配次數大幅減少，平均定位誤差減小0.5 m，有效提高定位精度。

表3 兩種算法定位對比分析表

圖6 實驗結果對比數據

5 結束語

本文在總結分析當前室內定位技術的基礎上，提出了一種基于近鄰法改進的室內定位算法。離線建庫階段，使用高斯濾波和均值濾波對RSSI雙重濾波處理，提高位置指紋數據庫的可信度；通過對定位區域網格化，基于參考點空間分布關系對指紋數據分級。在線定位階段，通過數據級別縮小匹配范圍，減小指紋數據匹配工作量的同時提高定位精度。但基于位置指紋算法實現的室內定位的離線建庫工作量較大，如何在保證定位精度的前提下減小離線建庫工作量將是今后的研究方向。