基于高斯過程的無線信號指紋定位算法

韋春玲 王步飛

(黃岡師范學院物理與電子信息學院 湖北 黃岡 438000)

0 引 言

基于位置服務LBS(Location Based Service)的快速發(fā)展推動了室內(nèi)定位研究的興起。但是，目前為止仍然沒有一種室內(nèi)定位技術被大規(guī)模商業(yè)化，因為很多技術依賴于基礎設施、特定硬件，以及室內(nèi)環(huán)境頻繁變化導致定位誤差變大。隨著無線網(wǎng)絡的普及，基于無線網(wǎng)絡接收信號指紋的室內(nèi)定位技術獲得廣泛關注。

無線信號指紋定位主要包括兩個步驟：離線訓練與在線定位。離線訓練階段的工作是創(chuàng)建信號指紋數(shù)據(jù)庫，也就是將處于不同位置的參考點RP(Reference Point)采集到的信號指紋信息保存在數(shù)據(jù)庫中，無線信號源可以是Wi-Fi[1]、GSM[2]、FM[3]、DTMB[4]或者地磁場信號等，信號指紋可以是信號強度、信號分布或者信號方差等。在線定位階段，將用戶當前測量到的信號指紋與數(shù)據(jù)庫中的信號指紋進行對比，用戶應處于最匹配的信號指紋對應的參考點位置。隨著Wi-Fi設備的普及，基于Wi-Fi無線信號指紋定位使用普通智能手機就能夠?qū)崿F(xiàn)，具有部署代價低、定位精度較高等優(yōu)點，目前已經(jīng)有很多商業(yè)產(chǎn)品，例如Google Map Indoor、WiFiSlam[5]和Rtmap等。

基于信號指紋的室內(nèi)定位精度主要依賴于信號指紋數(shù)據(jù)庫中參考點密度和數(shù)據(jù)庫時效。相同一片區(qū)域參考點密度越高，則定位越精確；數(shù)據(jù)庫更新的越頻繁，定位精度也越高。但是，創(chuàng)建與維護高密度信號指紋數(shù)據(jù)庫需要成本較高，而且有時候難以做到。例如，若要為100 m×100 m的室內(nèi)區(qū)域創(chuàng)建信號指紋數(shù)據(jù)庫，參考點密度為1個/平米，則一共需要采集10 000個參考點的信號指紋信息。在每一個參考點，都需要進行數(shù)次測量以獲取可靠的信號指紋。對于更大區(qū)域，參考點數(shù)量將以指數(shù)增長。對于某些區(qū)域，測量時可能難以到達，從而造成信號指紋的缺失。因此，在現(xiàn)實中通常難以構(gòu)建高密度信號指紋數(shù)據(jù)庫。另外，為了保持數(shù)據(jù)庫的時效性，需要定期進行更新，維護成本同樣非常巨大，造成了很多商業(yè)產(chǎn)品在實際中不可用。例如，谷歌公司聲稱采集了超過10萬個場館的信號指紋數(shù)據(jù)，但是在實際使用時，僅有少部分場館可定位[6]，Rtmap實測定位精度也遠沒有達到理論精度。

即使已經(jīng)構(gòu)建了高密度的數(shù)據(jù)庫，定位過程中同樣會帶來其他問題。用戶每次定位時，都會測量當前的信號指紋，并將其發(fā)送到位置服務器。服務器將用戶指紋與數(shù)據(jù)庫中的所有數(shù)據(jù)進行匹配，尋找最相似的參考點，參考點密度越高，數(shù)據(jù)庫規(guī)模越龐大，尋找過程耗時越長。當有大量用戶同時進行位置請求，定位實時性將受到影響。

總之，無線信號指紋定位具有部署容易、算法簡單等優(yōu)點，但是也存在高密度指紋數(shù)據(jù)庫構(gòu)建與維護成本高、定位時間長的問題。針對上述問題，本文提出一種基于高斯過程的兩階段信號指紋定位算法。本文提出的算法可有效降低數(shù)據(jù)庫構(gòu)建成本，縮短定位時間，提高定位精度。

1 研究現(xiàn)狀

針對信號指紋定位過程中數(shù)據(jù)庫構(gòu)建與維護的問題，人們提出了很多方法。除了采用人工方法逐點測量，大致有下列四種算法。

第一種算法稱為群智感知(Crowd-sourcing)[7]。群智感知中的用戶既是定位算法使用者，也是指紋數(shù)據(jù)庫的創(chuàng)建者與更新者。用戶測量到的最新信號指紋數(shù)據(jù)將會被上傳到位置服務器，服務器采用一定策略估計用戶位置，并將其作為新的參考點加入信號指紋數(shù)據(jù)庫。這種算法能夠有效利用用戶產(chǎn)生的數(shù)據(jù)創(chuàng)建指紋數(shù)據(jù)庫，并能夠及時更新數(shù)據(jù)庫中的數(shù)據(jù)。但是，設計有效的用戶貢獻機制仍有待研究[8]。

第二種算法采用數(shù)學模型來估計參考點信號指紋。給定參考點坐標和信號源位置以及信號發(fā)射功率，就能夠采用一定的數(shù)學模型計算出參考點處信號強度。使用最廣泛的信號強度估計模型是指數(shù)衰減LDPL(Log-Distance Path Loss)[9]，還有基于混合半監(jiān)督流形學習和3次樣條插值的研究[10]以及基于曲面擬合的數(shù)據(jù)庫構(gòu)建研究[11]。這類算法優(yōu)點是可以計算任意位置信號指紋，能夠大幅度降低創(chuàng)建高密度數(shù)據(jù)庫成本。但是室內(nèi)環(huán)境非常復雜，難以使用一個或者幾個簡單模型刻畫信號在復雜室內(nèi)傳播過程，導致信號強度估計存在較大誤差，只有在信號源附近的參考點信號估計較為準確。

第三種算法為光線追蹤(Ray-Tracing)[12]。這種算法在計算參考點信號強度時，將室內(nèi)布局考慮在內(nèi)，計算準確度較高，因此獲取的信號指紋數(shù)據(jù)庫精度較高。但是該算法需要事先獲取室內(nèi)詳細的三維模型，一旦室內(nèi)環(huán)境發(fā)生變化，例如增加或者減少家具以及家具位置移動等，此時就需要重新計算。同時，該算法計算復雜性較高，較為耗時。

第四種常用算法是即時定位與地圖構(gòu)建SLAM(Simultaneous Localization And Mapping)[13]。用戶一邊定位一邊創(chuàng)建地圖。通常的做法是：使用慣性傳感設備估計位置，將估計的位置與測量到的信號指紋進行關聯(lián)保存在數(shù)據(jù)庫中。由于慣導定位存在誤差積累，因此這種算法構(gòu)建的數(shù)據(jù)庫誤差較大。

本研究基于高斯過程，在訓練數(shù)據(jù)基礎上創(chuàng)建高密度虛擬數(shù)據(jù)庫，并針對虛擬數(shù)據(jù)庫，提出更加合理的位置估計算法，充分利用兩個數(shù)據(jù)庫的特點，提高定位精度、縮短定位時間。

2 兩階段信號指紋定位算法

2.1 基本原理

在計算機圖形學中，為了降低圖形渲染計算量，實現(xiàn)三維圖形的實時渲染，采用層次化細節(jié)技術LOD(Level Of Detail)[14]：當用戶與對象距離較遠，只渲染包含較少細節(jié)的圖層；當用戶靠近對象，則將渲染層次調(diào)整為細節(jié)更為豐富的圖層，從而在不影響用戶體驗條件下降低計算量，如圖1所示。

圖1 層次化細節(jié)技術基本原理

在圖1中，所有瓦片分辨率相同，但是層次1比層次2覆蓋范圍更廣，因此包含的對象細節(jié)更少。當用戶與對象距離較遠(d1)，則渲染包含細節(jié)較少的層次1圖層;當用戶與對象距離較近(d2)，則渲染包含細節(jié)較多的層次2圖層。

與之類似，兩階段信號指紋定位算法基本原理如圖2所示。

圖2 兩階段信號指紋定位算法基本原理

從圖2可以看出，在構(gòu)建數(shù)據(jù)庫過程中，采用高斯過程在訓練數(shù)據(jù)庫基礎上，生成虛擬信號指紋數(shù)據(jù)庫。虛擬信號指紋數(shù)據(jù)庫密度較高，含較多參考點。在定位過程中，先使用低密度的訓練數(shù)據(jù)庫進行粗略定位，能夠在較短時間內(nèi)確定用戶可能范圍；隨后，使用高密度的虛擬數(shù)據(jù)庫更新定位結(jié)果，定位過程中只需要在上一步確定的范圍內(nèi)進行搜索，因而搜索時間也較短。通過兩次定位，一方面減少定位過程中搜索量，另一方面提高了定位精度。

2.2 基本過程

2.2.1基于高斯過程的虛擬數(shù)據(jù)庫構(gòu)建算法

高斯過程是一種非參數(shù)化估計算法，能夠較好地逼近非線性傳播模型。高斯過程除了能給出估計量的大小，還能夠給出估計量的不確定性。因此，選擇使用高斯過程估計無線信號強度。

高斯過程的核心假設是：位置相近的參考點信號強度具有相關性，即：

(1)

(2)

k(xi,xj)為核函數(shù)，使用最廣泛的核函數(shù)是高斯核函數(shù)：

(3)

給定一組訓練數(shù)據(jù)(X,Y)={(xi,yi)i=1,2,…,n}，則可以基于高斯過程估計空間中任意一點x的信號強度y的概率分布：

(4)

(5)

式中：kx為n×1的向量，向量中的元素分別是未知點x與訓練數(shù)據(jù)中所有點的相關系數(shù)：

kx(i,0)=k(xi,x)xi∈X

(6)

(7)

式中：K為n×n矩陣，矩陣中的元素為訓練數(shù)據(jù)之間的相關性：

K(i,j)=k(xi,xj)xi,xj∈X

(8)

2.2.2兩階段KWNN定位算法

采用上述算法就能夠構(gòu)建高密度虛擬指紋數(shù)據(jù)庫。定位過程中為了充分利用虛擬數(shù)據(jù)庫提高定位精度、縮短定位時間，基于KWNN(K Weighted Nearest Node)提出兩階段KWNN定位算法。

假設用戶t時刻測量到的信號指紋為RSSt，RSSt={RSSt,i,i=1,2,…,b}，其中RSSt,i表示時刻t測量到的第i個信號源的信號強度，b表示信號源總數(shù)。

在第一階段，首先使用訓練數(shù)據(jù)庫DB(tr)進行粗略定位，計算RSSt與DB(tr)中所有參考點的信號距離：

(9)

采用式(9)計算出用戶測量的信號與數(shù)據(jù)庫DB(tr)中所有參考點的信號距離，選擇其中距離最小的K個參考點，構(gòu)成訓練集TS。

下面進入第二階段，基于TS創(chuàng)建用戶該時刻可能所處的范圍St：

St={(x,y)x?[min{xi},max{xi}],

y?[min{yj},max{yj}]

(xi,yi),(xj,yj)∈TS}

(10)

計算過程可用圖3說明。

圖3 創(chuàng)建定位范圍

定位過程中，對DB(v)中St范圍內(nèi)所有參考點，計算與用戶測量信號的距離：

(11)

選擇其中距離最小的K個參考點，用戶位置采用下式計算：

(12)

(13)

式中：p為可調(diào)參數(shù)，通過調(diào)節(jié)p獲得最佳估計值。

位置估計的方差為：

(14)

至此，通過兩個步驟得到用戶位置以及位置估計方差：1) 基于訓練數(shù)據(jù)庫縮小搜索范圍；2) 采用高密度虛擬數(shù)據(jù)庫進行精確定位。

由于第一階段使用的數(shù)據(jù)庫密度較低，有可能出現(xiàn)較大的誤差，用戶真實位置不在距離最小的K個參考點構(gòu)成訓練集TS所處的范圍St內(nèi)，導致第二階段無論如何都不可能準確定位，為了應對這種情況，將K設定為訓練數(shù)據(jù)庫DB(tr)參考點密度ρ(tr)的函數(shù)：

K=a+b/ρ(tr)

(15)

式中：a,b>0，則ρ(tr)越小，K越大，確保訓練數(shù)據(jù)庫密度ρ(tr)越小，選擇的參考點K越多，覆蓋范圍St盡可能大，從而降低用戶處于第一階段定位范圍以外的概率，確保算法在縮短定位時間的同時，提高定位精度。

3 實驗驗證

為了驗證算法的有效性，采用AWE公司的光線追蹤工具WinPro建立室內(nèi)信號指紋數(shù)據(jù)庫。數(shù)據(jù)庫覆蓋范圍約為800平方米，設置了8個Wi-Fi熱點，一共計算了3 018個均勻分布的參考點信號指紋，室內(nèi)環(huán)境以及信號熱點分布如圖4所示。

圖4 室內(nèi)平面結(jié)構(gòu)圖與信號源分布圖

從原始信號指紋數(shù)據(jù)庫中隨機選擇40個參考點作為訓練數(shù)據(jù)庫DB(tr)，也就是說訓練數(shù)據(jù)庫參考點密度僅為0.05個/平方米。基于訓練數(shù)據(jù)庫建立虛擬數(shù)據(jù)庫DB(v)，密度為1個/平方米，也就是說包含800個參考點。下面分別采用訓練數(shù)據(jù)庫和虛擬數(shù)據(jù)庫進行定位，對比其定位精度和定位耗時。

為了保證結(jié)果有效性，一共進行200組仿真實驗。在每一組仿真實驗中，隨機選擇40個參考點構(gòu)成訓練數(shù)據(jù)庫；定位時，從先期生成的3 018個參考點中隨機抽取1 000個參考點進行位置估計，抽取的參考點的信號強度為真實信號強度加上均值為0，標準差為2 dBm的正態(tài)分布誤差[15]。其他仿真參數(shù)設置如下：a=2，b=0.05，p=3，q=1。一共對比三種定位算法，分別是使用訓練數(shù)據(jù)庫的KWNN定位算法、使用虛擬信號指紋數(shù)據(jù)庫的KWNN算法和本文提出的兩階段定位算法。這樣設置的原因是：使用訓練數(shù)據(jù)庫的KWNN算法與新算法可以對比定位精度的提高；使用虛擬信號指紋數(shù)據(jù)庫的KWNN定位與新算法可以對比定位時間的縮短。

首先，使用基于訓練數(shù)據(jù)庫的KWNN算法與新算法進行對比，主要從定位精度和定位耗時角度進行比較。圖5給出了不同算法的累積誤差分布曲線CDF(Cumulative Distribution Function)。

圖5 基于訓練數(shù)據(jù)庫的KWNN算法與新算法CDF對比

在圖5中，曲線上的每一點(x,y)表示定位過程中精度小于x米的概率為y。可以看出，本文提出的兩階段信號指紋定位算法定位精度遠遠高于僅使用訓練數(shù)據(jù)庫進行定位。兩階段定位算法定位精度小于3.5米的概率為80%，而僅使用訓練數(shù)據(jù)庫定位時，精度小于3.5米的概率僅為17.5%。

圖6給出了兩種定位算法平均定位精度和平均定位時間。

圖6 基于訓練數(shù)據(jù)庫的KWNN算法與新算法平均定位精度和平均定位時間對比

由圖6可以看出：從平均定位精度上對比，本文提出的無線定位算法平均定位精度為2.53米，直接使用訓練數(shù)據(jù)庫進行定位的精度達到13.98米，本文算法定位精度提高了81.9%；從平均定位時間上對比，本文提出算法平均定位時間為0.13毫秒，直接使用訓練數(shù)據(jù)庫平均定位時間為0.34毫秒，本文提出的算法定位所需時間較多，多出的時間來自于第二階段定位耗時，因此本文定位算法是一種時間換精度的策略。

接下來，使用基于虛擬數(shù)據(jù)庫KWNN定位與新算法進行對比。圖7給出了兩種定位算法平均定位精度和平均定位時間。

圖7 基于虛擬數(shù)據(jù)庫KWNN定位與新算法平均定位精度和平均定位時間對比

從圖7可以看出：在定位精度方面，本文提出的算法平均定位精度為2.53米，直接使用虛擬數(shù)據(jù)庫進行定位的精度約為2.54米，二者差距不大；在定位時間方面，本文提出算法平均定位時間為0.34毫秒，直接使用虛擬數(shù)據(jù)庫平均定位時間為2.45毫秒，新算法定位時間縮短了86%。主要原因是在新算法的第二階段減小搜索范圍，從而極大縮短了搜索時間。從仿真結(jié)果可以看出，新算法可有效減少定位時間、提高定位精度。

4 結(jié) 語

基于無線信號的指紋定位隨著Wi-Fi設備的普及而獲得研究人員的廣泛關注，但是信號指紋定位存在數(shù)據(jù)庫構(gòu)建與維護成本高、定位實時性差的問題。本文提出一種基于高斯過程的兩階段無線信號指紋定位算法：利用高斯過程，在原始信號指紋數(shù)據(jù)庫基礎上，生成高密度虛擬信號指紋數(shù)據(jù)庫；定位過程中首先使用訓練數(shù)據(jù)庫確定大致范圍，然后使用虛擬數(shù)據(jù)庫進行精確定位。仿真結(jié)果顯示，相對于標準KWNN定位算法，新算法定位精度提高81.9%，定位時間平均減少86%。下一步工作將深入研究虛擬數(shù)據(jù)庫密度設置以及多層虛擬信號指紋數(shù)據(jù)庫定位問題，繼續(xù)推動無線信號指紋定位進入實際應用。