基于最小值的多映射數(shù)據(jù)結(jié)構(gòu)指紋庫定位算法

郭昕剛， 胡 朗

(長春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 吉林 長春 130012)

0 引 言

近年來，隨著移動互聯(lián)時(shí)代的到來，人們對定位導(dǎo)航服務(wù)的需求越來越多?；贕PS的室外定位已經(jīng)為人們提供了很大的便利，如汽車的定位跟蹤、高德地圖、滴滴打車應(yīng)用等。對于室內(nèi)環(huán)境，由于室內(nèi)建筑物的遮擋、信號的多徑傳播等影響，GPS定位不能滿足室內(nèi)對精度要求較高的定位需求。

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

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

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

對于上述問題，文中采用了多映射的數(shù)據(jù)結(jié)構(gòu)來構(gòu)建離線階段的位置指紋庫，使得每個(gè)參考點(diǎn)位置對應(yīng)同一AP的一個(gè)或多個(gè)RSSI值，這樣在線匹配階段通過計(jì)算歐式距離最小值，找到與待定位點(diǎn)最匹配的K個(gè)參考點(diǎn)，用WKNN算法實(shí)現(xiàn)位置的估算。這種方法有利于提高指紋庫的準(zhǔn)確性，減小定位誤差。

1 多映射數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)庫濾波算法

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

對同一AP距離下的RSSI值采樣分析發(fā)現(xiàn)，RSSI信號值并不是固定在某個(gè)值下不變的，而是隨著采樣時(shí)間的變化，RSSI值會發(fā)生波動[6]。由于室內(nèi)環(huán)境存在多徑效應(yīng)等影響，這種波動是隨機(jī)發(fā)生的，所以在構(gòu)建指紋庫前，通常需要對信號進(jìn)行濾波處理。

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

(1)

依次遍歷所有參考點(diǎn)的各個(gè)AP，并將所得的結(jié)果存入數(shù)據(jù)庫，得到整個(gè)定位區(qū)間的離線指紋數(shù)據(jù)庫[7]：

(2)

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

圖1 同一參考點(diǎn)所獲取的同一AP的RSSI變化圖

由于室內(nèi)各個(gè)AP的獨(dú)立性，所以需要對各個(gè)AP進(jìn)行單獨(dú)分析，對兩組不同AP進(jìn)行采集所得的RSSI值概率分布，如圖2所示。

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

(a) 同一參考點(diǎn)接收到的AP1信號強(qiáng)度概率分布

(b) 同一參考點(diǎn)接收到的AP2信號強(qiáng)度概率分布

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

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

(3)

(4)

(5)

式中：μ——樣本信號強(qiáng)度RSSI的平均值；

σ——樣本信號強(qiáng)度RSSI的標(biāo)準(zhǔn)差。

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

(6)

針對采樣信號RSSI值出現(xiàn)的頻數(shù)大小從左到右進(jìn)行降序排序，得到排序后的信號RSSI值的集合：

(7)

式中：nk——每個(gè)RSSI信號值出現(xiàn)的頻數(shù)。

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

(8)

式中：nk——對應(yīng)RSSI值出現(xiàn)的頻數(shù)；

pthreshold——篩選的概率閾值。

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

表1 多映射指紋庫下參考點(diǎn)對應(yīng)的RSSI分布表

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

2 最小值的多映射數(shù)據(jù)結(jié)構(gòu)在線匹配算法

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

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

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

(9)

每個(gè)參考點(diǎn)的權(quán)重表示為：

(10)

式中：ε——一個(gè)無限接近于0的整數(shù)，目的是防止分母出現(xiàn)0的特殊情況。

最終待定位點(diǎn)的估計(jì)位置為：

(11)

3 實(shí)驗(yàn)與分析

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

圖4 多映射數(shù)據(jù)結(jié)構(gòu)指紋庫構(gòu)建流程 圖5 基于最小值的多映射數(shù)據(jù)結(jié)構(gòu)在線定位流程

實(shí)驗(yàn)結(jié)果采用誤差累計(jì)分布函數(shù)(Cumulated Denstiy Function, CDF)來衡量本定位算法相對于傳統(tǒng)指紋庫以及匹配算法的精度和穩(wěn)定性，結(jié)果如圖6所示。

圖6 傳統(tǒng)指紋庫對應(yīng)匹配算法和文中算法累計(jì)誤差圖

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

4 結(jié) 語

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