基于最小值的多映射數據結構指紋庫定位算法

郭昕剛， 胡 朗

(長春工業大學 計算機科學與工程學院， 吉林 長春 130012)

0 引 言

近年來，隨著移動互聯時代的到來，人們對定位導航服務的需求越來越多。基于GPS的室外定位已經為人們提供了很大的便利，如汽車的定位跟蹤、高德地圖、滴滴打車應用等。對于室內環境，由于室內建筑物的遮擋、信號的多徑傳播等影響，GPS定位不能滿足室內對精度要求較高的定位需求。

針對室內WiFi的大量部署，WiFi室內定位技術已經成為當今室內定位的研究熱點。基于WiFi的室內定位主流方向通常分為：基于測距(range-based)和測距無關(range-free)兩種。基于測距的定位方法一般為通過待定位點與AP節點的距離或者角度來計算定位目標的位置，常見的有：接收信號強度指示(RSSI)、信號到達角度(AOA)、信號到達時間(TOA)以及信號到達時間差(TDOA)等[2]。而與測距無關的定位方法主要是依據對定位環境的場景特征分析，在定位時將待定位點的場景信息與參考點的場景信息進行對比實現定位，典型的應用算法是位置指紋法。該方法的主要優點是無需對AP節點位置和距離進行測量計算、無需添加額外的硬件設備。

在研究WiFi室內定位的過程中，基于位置指紋的定位方法是比較可行而且精度較高的定位方法，成為室內定位研究的熱門方向。位置指紋定位方法主要分為離線階段(off-line)和在線階段(on-line)兩個過程[3]。在離線階段，主要通過智能終端的WLAN無線接入點，采集室內各個AP的特征信息，把這些信息如MAC地址、RSSI信號強度值以及采集點的位置坐標作為指紋存入指紋庫中，遍歷室內所有的采集點便構成了完整的位置指紋庫。在線階段通過智能終端實時接收到各個AP的RSSI信號值，通過與離線數據庫的匹配找到與之相似的指紋參考點，進而估算出當前待定位點的位置坐標。

離線指紋庫的合理構建和在線匹配算法的選擇是影響WiFi室內定位精度和實時性的兩個主要因素。通過規劃和測量，按一定間距選取合適的參考點，在每個參考節點上測得各個AP的MAC地址和信號強度值。WiFi信號的時變性以及信號傳播的復雜性，使得測量的信號強度值并不能直接存儲，而是需要濾波之后再使用，避免各種奇異信號值和小概率信號值存儲到指紋庫中影響定位的穩定性[4]。實時在線階段，需要使用合適的匹配算法去尋找相關的指紋參考點，與待定位點的歐式距離越小，權值就越大，對目標位置的定位貢獻程度就越高。

對于上述問題，文中采用了多映射的數據結構來構建離線階段的位置指紋庫，使得每個參考點位置對應同一AP的一個或多個RSSI值，這樣在線匹配階段通過計算歐式距離最小值，找到與待定位點最匹配的K個參考點，用WKNN算法實現位置的估算。這種方法有利于提高指紋庫的準確性，減小定位誤差。

1 多映射數據結構的數據庫濾波算法

影響室內信號傳播的因素很多， 導致在采集信號的過程中同一位置對同一AP信號的不同時間RSSI值具有差異性[5]，因此需要對每個AP節點進行單獨的數據采集與分析。移動終端在同一參考點處多次采集所獲取的同一AP的RSSI信息,如圖1所示。

對同一AP距離下的RSSI值采樣分析發現，RSSI信號值并不是固定在某個值下不變的，而是隨著采樣時間的變化，RSSI值會發生波動[6]。由于室內環境存在多徑效應等影響，這種波動是隨機發生的，所以在構建指紋庫前，通常需要對信號進行濾波處理。

將采集到的同一AP樣本值{RSSI1,RSSI2,RSSI3,…,RSSIn}進行平均濾波：

(1)

依次遍歷所有參考點的各個AP，并將所得的結果存入數據庫，得到整個定位區間的離線指紋數據庫[7]：

(2)

但在匹配的過程中，平均濾波對定位精度的優化效果并不理想，原因主要是平均濾波對所有測得的RSSI值進行計算，這將引入一些對定位無關的RSSI值，這些值通常出現的概率很小,甚至不會出現[7]。而在線過程中，采樣時間很短，各種匹配算法都很難消除這些誤差，導致匹配的結果會偏離實際位置很多。

圖1 同一參考點所獲取的同一AP的RSSI變化圖

由于室內各個AP的獨立性，所以需要對各個AP進行單獨分析，對兩組不同AP進行采集所得的RSSI值概率分布，如圖2所示。

從圖中可以看出，RSSI值的波動呈現一種線性回歸狀態，即RSSI在一定范圍內波動，且具有上下限。若設置概率閾值為0.1，則圖2(a)中RSSI值集中在-49～-46 dBm之間，圖2(b)中RSSI值集中在-57～-55 dBm之間。

(a) 同一參考點接收到的AP1信號強度概率分布

(b) 同一參考點接收到的AP2信號強度概率分布

在室內環境復雜變化以及多徑效應影響的情況下，大多數值都在上下限范圍之內，極少情況會出現在范圍之外，這說明各AP的RSSI值滿足正態分布規律[8]。針對上述分析情況，文中提出了一種多映射的數據庫濾波算法，合理構建離線指紋數據庫，以提高在線匹配的精度。

針對各AP信號呈現的規律特征，在構建指紋庫之前，采用高斯濾波濾除RSSI信號值中的非常規數值，保留出現可能性較大的RSSI數值。對每組AP的RSSI值處理則有：

(3)

(4)

(5)

式中：μ——樣本信號強度RSSI的平均值；

σ——樣本信號強度RSSI的標準差。

將概率范圍在0.1≤f(x)≤1的RSSI信號值取出，濾除小概率的異常信號，經過高斯濾波之后的每組RSSI樣本值的集合為：

(6)

針對采樣信號RSSI值出現的頻數大小從左到右進行降序排序，得到排序后的信號RSSI值的集合：

(7)

式中：nk——每個RSSI信號值出現的頻數。

為了選取對定位有效的RSSI值存入到指紋庫，下面將通過對頻數排序后的RSSI信號值的集合進行篩選。首先選取出現次數最多的RSSI值的頻數與集合中的總頻數進行比較，所得的值如果大于概率閾值，則此次篩選結束，保留當前的RSSI值作為該點測得的RSSI信號值存入到指紋庫。否則，將下一出現次數多的RSSI值的頻數加到當前的RSSI值頻數中，累加到一起與集合總頻數比較，直到該占比大于概率閾值,并將這些累加的頻數對應的RSSI值存入到指紋庫。具體篩選的準則為：

(8)

式中：nk——對應RSSI值出現的頻數；

pthreshold——篩選的概率閾值。

該算法這樣篩選的目的是能最大限度地保留對定位有作用的RSSI值，在傳統的指紋庫中，同一位置點對應的同一AP僅僅只有一個值，而在該算法中往往可以得到同一位置對應的同一AP兩個或者多個RSSI值。這樣在定位匹配的過程中，可以找到與該位置最相近的RSSI值做比較。對應的指紋庫見表1。

表1 多映射指紋庫下參考點對應的RSSI分布表

室內定位范圍內終端搜索到的AP節點有3個，分別為AP1、AP2和AP3。參考點RP1位置處AP1值為-48、-46 dBm，AP2值為-62、-59、-58 dBm,AP3值為-50、-47 dBm，這樣RP1參考點存得的RSSI向量組合形式就有12種，在線匹配階段，可以找到歐式距離最小的向量組合去參與匹配，降低最后的定位誤差。

2 最小值的多映射數據結構在線匹配算法

在線定位階段，比較常用的定位算法有最近鄰算法(NN)、K近鄰算法(KNN)和加權K近鄰算法(WKNN)[9]。最近鄰算法根據定位終端實時采集到AP的RSSI值與位置指紋庫中的指紋信息進行匹配，找到相似度最大的位置指紋對應的參考點坐標作為待定位點坐標，而K近鄰算法是找到位置指紋庫中K個指紋點并求得對應參考點坐標的平均值。WKNN算法是在KNN算法上的改進，在找到K個指紋相似點之后，將每個相似點賦予不同的權重ωi，一般來說，離目標接近的指紋點對待定位點的貢獻大，相應的權重值大；反之，離目標稍遠的指紋點對帶定位點的貢獻小，相應的權重值小[10]。

為了找到對定位貢獻最大的指紋參考點，在計算歐式距離過程中，文中引入了最小歐式距離的計算方法，舍棄了傳統指紋庫同一位置對應的同一AP下的單個RSSI值對定位造成的誤差。具體步驟為：在線階段我們測得各個AP的RSSI信息值，通過均值濾波得到每個AP的平均值，依次遍歷所有AP就得到了該定位點的RSSI信息值。由于歐式距離的結果是兩者所有對應AP節點相似度差值的累加，在參與歐式距離計算的過程中，找到接近于實時測得的相應AP的RSSI值參與計算，這樣能夠在指紋庫中的多種向量組合中找到最接近定位的RSSI向量組合。

用RSSI={RSSI1,RSSI2,RSSI3,…，RSSIn}表示定位終端在待定位點測量到的n個AP的RSSI信號強度值，用rssij={rssi1,rssi2,rssi3，…,rssin}表示第j個指紋點存得的某一組合的信號強度，兩點的RSSI信號強度的相似度用歐式距離表示為：

(9)

每個參考點的權重表示為：

(10)

式中：ε——一個無限接近于0的整數，目的是防止分母出現0的特殊情況。

最終待定位點的估計位置為：

(11)

3 實驗與分析

文中提出的算法在長春工業大學計算機科學與工程學院實驗室走廊區域進行實驗驗證，事先在定位區域部署3個AP發射點，以1.6 m的間隔規劃一定的采樣點，采用智能手機APP采集WiFi信號。在每個采樣點處采集AP節點的RSSI信號值，并將每個AP采集樣本首先進行高斯濾波濾除小概率的噪聲值，然后對保留下來的每個RSSI依次排序并計算單個RSSI值的頻數占總體頻數的比值，設置概率閾值對其進行有效篩選，得到最終保留下來的單個AP的樣本值，依次遍歷所有AP就得到了該采樣點的指紋信息，將其保存在數據庫中。在線匹配的過程中，在線測得的待定位點的RSSI信息值與多映射數據結構的指紋庫進行匹配，找到歐式距離最小的K個指紋點信息，最后通過WKNN求得帶定位點的坐標。整個定位的過程具體流程如圖4和圖5所示。

圖4 多映射數據結構指紋庫構建流程 圖5 基于最小值的多映射數據結構在線定位流程

實驗結果采用誤差累計分布函數(Cumulated Denstiy Function, CDF)來衡量本定位算法相對于傳統指紋庫以及匹配算法的精度和穩定性，結果如圖6所示。

圖6 傳統指紋庫對應匹配算法和文中算法累計誤差圖

文中提出的算法能夠有效提高定位的精度，減小了WiFi信號的變化以及傳統指紋庫的局限性對定位造成的誤差。從圖中能夠看出，文中算法的誤差在3.5 m范圍內，同等誤差距離下，該算法累計誤差概率提高了將近10%，驗證了該算法的有效性和可行性。

4 結 語

針對傳統指紋庫單向量的構建形式造成的精度不高問題進行了深入分析，提出了一種多映射的數據結構指紋庫以及最小值在線匹配算法，改變了傳統指紋庫的采樣點對應每個AP的單個RSSI值的情況，以多個RSSI值映射同一個位置。在線匹配階段，通過最小歐式距離的選擇，能夠找到擬合度最高的RSSI向量組合，得到對待定位點貢獻大的參考點。實驗結果表明，文中提出的定位算法在精度以及穩定性方面具有一定的提升，對基于位置指紋的室內定位研究提供了一定的參考作用。