韋春玲 王步飛

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

0 引 言

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

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

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

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

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

1 研究現(xiàn)狀

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

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

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

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

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

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

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

2.1 基本原理

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

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

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

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

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

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

2.2 基本過程

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

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

高斯過程的核心假設(shè)是：位置相近的參考點(diǎn)信號強(qiáng)度具有相關(guān)性，即：

(1)

(2)

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

(3)

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

(4)

(5)

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

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

(6)

(7)

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

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

(8)

2.2.2兩階段KWNN定位算法

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

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

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

(9)

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

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

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

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

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

(10)

計(jì)算過程可用圖3說明。

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

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

(11)

選擇其中距離最小的K個(gè)參考點(diǎn)，用戶位置采用下式計(jì)算：

(12)

(13)

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

位置估計(jì)的方差為：

(14)

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

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

K=a+b/ρ(tr)

(15)

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

3 實(shí)驗(yàn)驗(yàn)證

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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