一種基于藍(lán)牙室內(nèi)指紋定位的貝葉斯改進(jìn)算法

郭 英，馮茗楊，孫玉曦，2，姬現(xiàn)磊，劉清華

(1. 山東科技大學(xué)測(cè)繪科學(xué)與工程學(xué)院，山東 青島 266590； 2. 中國(guó)測(cè)繪科學(xué)研究院，北京 100830)

隨著社會(huì)經(jīng)濟(jì)的發(fā)展，用戶對(duì)于大型商場(chǎng)、辦公區(qū)域、機(jī)場(chǎng)、博物館等室內(nèi)環(huán)境的精確的基于位置的服務(wù)(location based service,LBS)需求越來越大[1]，從而多種室內(nèi)定位方法應(yīng)運(yùn)而生，如WiFi、射頻識(shí)別(RFID)、超寬帶(UWB)、藍(lán)牙等無線定位技術(shù)[2]，以及地磁、超聲波、視覺、慣性導(dǎo)航等非無線定位技術(shù)[3]?，F(xiàn)如今，無線定位技術(shù)已有許多應(yīng)用案例，UWB可以實(shí)現(xiàn)厘米級(jí)的定位精度[4]，基于WiFi信號(hào)接收強(qiáng)度(RSSI)的指紋定位精度可達(dá)到1～5 m，藍(lán)牙天線陣列和指紋識(shí)別定位分別可達(dá)到<1 m和2～5 m的精度[5]。其中，UWB和藍(lán)牙天線陣列技術(shù)需要專屬的設(shè)備，且價(jià)格昂貴，推廣難度大[6]；與前兩者相比，藍(lán)牙和WiFi基站的價(jià)格相對(duì)低廉，在推廣應(yīng)用上有巨大的優(yōu)勢(shì)。與WiFi相比，藍(lán)牙基站有如下優(yōu)勢(shì)：內(nèi)置電池(2～3年壽限)，可以通過設(shè)置發(fā)射功率調(diào)節(jié)藍(lán)牙信號(hào)覆蓋范圍(覆蓋半徑為10～100 m)，而且藍(lán)牙技術(shù)已經(jīng)廣泛集成于移動(dòng)設(shè)備中，更加易于推廣使用。因此，藍(lán)牙室內(nèi)定位成為當(dāng)前適用性最佳的技術(shù)之一[7]。

基于低成本設(shè)備的藍(lán)牙定位中，其算法以基于RSSI的藍(lán)牙指紋識(shí)別為主，最常見的有最近鄰法、K最近鄰法和貝葉斯算法[8]。其中，最近鄰算法和K最近鄰算法簡(jiǎn)單，易于實(shí)現(xiàn)，但是定位精度較低；貝葉斯算法的定位精度優(yōu)于近鄰算法[9]。然而，貝葉斯算法將每個(gè)參考點(diǎn)的先驗(yàn)概率視為等值[10]，在動(dòng)態(tài)定位過程中，前一定位結(jié)果會(huì)影響后續(xù)定位中參考點(diǎn)的先驗(yàn)概率[11]，并且先驗(yàn)概率對(duì)定位有很強(qiáng)的約束性[12]，因此貝葉斯算法的等值先驗(yàn)概率在動(dòng)態(tài)定位中不適用。對(duì)于該問題，許多研究人員提出在參數(shù)學(xué)習(xí)中融入先驗(yàn)知識(shí)，即加入約束條件[13]。文獻(xiàn)[14]采用動(dòng)態(tài)位置先驗(yàn)概率，通過最短距離矩陣確定參考點(diǎn)的先驗(yàn)概率，該算法平均定位誤差達(dá)到1.82 m；文獻(xiàn)[15]將確定性算法和概率性算法相融合，利用近鄰算法篩選參考點(diǎn)，定位準(zhǔn)確率比最近鄰算法提高了4%；文獻(xiàn)[16]將各區(qū)域建模以確定先驗(yàn)信息，在基站密度為30 m2/個(gè)時(shí)，誤差在2.6 m的可信度為95%。

在動(dòng)態(tài)定位中，距離參數(shù)和航向參數(shù)都是重要的先驗(yàn)條件，基于此，本文提出一種貝葉斯定位改進(jìn)算法。該算法在貝葉斯指紋算法的基礎(chǔ)上，引入陀螺儀的航向信息[17]，并利用航向信息對(duì)高斯核函數(shù)模型[18]進(jìn)行改進(jìn)，以改進(jìn)模型作為投票算法來確定先驗(yàn)概率；先驗(yàn)概率結(jié)合實(shí)時(shí)RSSI計(jì)算位于參考點(diǎn)上的后驗(yàn)概率，選取前n個(gè)概率最高的點(diǎn)，以概率為權(quán)重加權(quán)平均得到待測(cè)點(diǎn)坐標(biāo)。

1 貝葉斯指紋算法

離線采集階段，在定位區(qū)域以一定間隔布設(shè)參考點(diǎn)，使用采集設(shè)備在每個(gè)參考點(diǎn)同時(shí)采集n個(gè)iBeacon的主機(jī)唯一識(shí)別碼(universally unique identifier，UUID)、信號(hào)強(qiáng)度RSSI，并計(jì)算每個(gè)基站在對(duì)應(yīng)參考點(diǎn)的信號(hào)強(qiáng)度均值μ、標(biāo)準(zhǔn)偏差σ。以上數(shù)據(jù)結(jié)合已知的參考點(diǎn)坐標(biāo)構(gòu)成位置指紋庫(kù)L

Li=(xi,yi,UUIDn,μUUID,σUUID)

(1)

同一位置的RSSI分布可以近似用高斯概率分布來描述[19]，因此，其概率密度函數(shù)可以近似表示為

(2)

式中，x表示定位過程中接收到的信號(hào)強(qiáng)度值；μ表示信號(hào)強(qiáng)度的均值；σ表示信號(hào)強(qiáng)度的標(biāo)準(zhǔn)偏差。

在線定位階段，貝葉斯估計(jì)根據(jù)貝葉斯和全概率公式，由先驗(yàn)概率計(jì)算后驗(yàn)概率。定位區(qū)域內(nèi)有N個(gè)參考點(diǎn)，坐標(biāo)分別為Zi=(xi,yi)，RSSIi為參考點(diǎn)i的指紋數(shù)據(jù)。待測(cè)點(diǎn)實(shí)時(shí)信號(hào)強(qiáng)度為S(RSSI1，RSSI2，…，RSSIn)時(shí)，定位在參考點(diǎn)i的概率為

(3)

式中，p(Zi)為先驗(yàn)概率，貝葉斯算法將先驗(yàn)概率p(Zi)視為等值。利用參考點(diǎn)RSSI的均值和標(biāo)準(zhǔn)差通過式(3)計(jì)算信號(hào)指紋為S時(shí)定位在參考點(diǎn)i的概率，選取概率最高的n個(gè)參考點(diǎn)，計(jì)算待測(cè)點(diǎn)的最或然值。

2 改進(jìn)的貝葉斯算法

由于動(dòng)態(tài)定位過程中，前一定位結(jié)果會(huì)影響到后續(xù)定位中參考點(diǎn)的先驗(yàn)概率，因此貝葉斯算法的等值先驗(yàn)概率不適用。本文借助高斯核函數(shù)模型(式(4))的概率約束性，以及利用陀螺儀獲取的航向信息建立投票算法，計(jì)算參考點(diǎn)先驗(yàn)概率。

(4)

2.1 航向信息獲取

陀螺儀是智能手機(jī)必備的傳感器，可為用戶提供方向信息。基于陀螺儀數(shù)據(jù)的常用航向獲取方法有歐拉角法、方向余弦法和四元數(shù)法。相對(duì)比其他兩個(gè)方法，四元數(shù)法具有計(jì)算量少、易于操作，并且能避免出現(xiàn)歐拉角法中“奇點(diǎn)”問題的優(yōu)點(diǎn)，故本文選擇四元數(shù)法來解算航向信息。利用四元數(shù)法獲取陀螺儀航向信息的方法詳見文獻(xiàn)[17]，主要過程如下：利用二階龍格庫(kù)塔法更新解算四元數(shù)q(q0，q1，q2，q3)

(5)

獲取到實(shí)時(shí)的四元數(shù)信息后，即可推算出航向信息θ

(6)

2.2 先驗(yàn)概率的投票模型

由式(6)得到運(yùn)動(dòng)航向θ，人為設(shè)定檢索上限角度α，本文設(shè)定α為45°。根據(jù)這兩個(gè)參數(shù)確定一個(gè)扇形區(qū)域作為參考點(diǎn)的檢測(cè)區(qū)域，通過改進(jìn)的高斯核函數(shù)(式(7))計(jì)算該區(qū)域內(nèi)的參考點(diǎn)的投票概率g(x,y)，作為參考點(diǎn)的先驗(yàn)概率。

(7)

式中，(x0,y0)為前一點(diǎn)的坐標(biāo)；d為單位時(shí)間的平均移動(dòng)距離。本文d的初始值設(shè)定為0.9 m，計(jì)算得到待測(cè)點(diǎn)位置后，實(shí)時(shí)對(duì)d進(jìn)行更新。改進(jìn)的高斯核函數(shù)為模型的投票算法如圖1所示。

通過改進(jìn)高斯核函數(shù)，放大了投票中心的參考點(diǎn)的先驗(yàn)概率，使待測(cè)點(diǎn)近鄰區(qū)域的參考點(diǎn)擁有較大的先驗(yàn)概率。

2.3 待測(cè)點(diǎn)計(jì)算流程

在線定位階段，根據(jù)接收到的信號(hào)強(qiáng)度S(RSSI1，RSSI2，…，RSSIn)計(jì)算待測(cè)點(diǎn)定位在每個(gè)參考點(diǎn)的后驗(yàn)概率p(ZiS)，并將式(7)得到的先驗(yàn)概率g(Zi)代入式(3)，得

(8)

式中，Zi表示參考點(diǎn)的位置Z(xi,yi)；g(Zi)則表示待測(cè)點(diǎn)在點(diǎn)Zi處的先驗(yàn)概率，可由式(7)積分求得；p(SZi)表示信號(hào)強(qiáng)度為S時(shí)，待測(cè)點(diǎn)在Zi處的概率。由于各個(gè)基站的信號(hào)強(qiáng)度相互獨(dú)立[20]，故p(SZi)可以用聯(lián)合概率分布函數(shù)來描述

(9)

最后，取前m個(gè)概率最大的參考點(diǎn)(本文中設(shè)置m=4)，以概率作為權(quán)重，加權(quán)平均求得待測(cè)點(diǎn)最或然值

(10)

本文改進(jìn)算法的核心是確定先驗(yàn)概率的投票算法。在離線階段采集參考點(diǎn)指紋信息；在線階段，由航向信息確定某一檢索區(qū)域，再利用改進(jìn)的高斯投票算法計(jì)算檢索區(qū)域參考點(diǎn)的先驗(yàn)概率，根據(jù)實(shí)時(shí)信號(hào)強(qiáng)度計(jì)算參考點(diǎn)的后驗(yàn)概率；以概率定權(quán)，前m個(gè)概率最大的參考點(diǎn)坐標(biāo)的加權(quán)平均作為定位結(jié)果。算法的具體流程如圖2所示。

3 定位試驗(yàn)及分析

3.1 數(shù)據(jù)采集和指紋庫(kù)建立

貝葉斯指紋定位算法需要在離線階段建立指紋庫(kù)，本文選用的iBeacon可持續(xù)發(fā)射信號(hào)強(qiáng)度為-100～-50 dBm的信號(hào)。為完成指紋的采集工作，編寫了能夠采集信號(hào)強(qiáng)度、主機(jī)號(hào)、識(shí)別碼的APP，采集界面如圖3所示。試驗(yàn)場(chǎng)地位于山東科技大學(xué)測(cè)繪科學(xué)與工程學(xué)院S2實(shí)驗(yàn)樓二樓走廊區(qū)域，圓點(diǎn)表示參考點(diǎn)(如圖4所示)，其間隔為1 m，總共175個(gè)參考點(diǎn)。試驗(yàn)者手持智能手機(jī)分別在每個(gè)參考點(diǎn)位置采集參考點(diǎn)指紋信息(每個(gè)基站的信號(hào)強(qiáng)度、iBeacon主機(jī)號(hào)、識(shí)別碼)，采集頻率為1 Hz，每個(gè)點(diǎn)持續(xù)采集60 s，分別計(jì)算采集到的信號(hào)強(qiáng)度的均值和中誤差。

3.2 試驗(yàn)與分析

3.2.1 試驗(yàn)1

設(shè)置試驗(yàn)對(duì)改進(jìn)算法的精度進(jìn)行測(cè)試：在參考點(diǎn)布設(shè)區(qū)域設(shè)置長(zhǎng)120 m的閉合試驗(yàn)路線，試驗(yàn)者手持采集設(shè)備，按設(shè)計(jì)路線走，實(shí)時(shí)采集陀螺儀數(shù)據(jù)和藍(lán)牙數(shù)據(jù)；分別用本文的改進(jìn)算法和貝葉斯算法對(duì)該數(shù)據(jù)進(jìn)行處理，對(duì)得到的兩種結(jié)果進(jìn)行比較。

為了從整體上比較這兩種算法，分別計(jì)算兩種算法的定位路線(如圖5所示)，定位誤差(如圖6(a)所示)和誤差概率累計(jì)函數(shù)(如圖6(b)所示)，并將各類參數(shù)進(jìn)行統(tǒng)計(jì)(見表1)。本文將平均點(diǎn)位誤差、最大定位誤差和誤差累計(jì)概率作為衡量精度的標(biāo)準(zhǔn)。

從圖5看出，與貝葉斯算法相比，本文算法明顯改善了定位過程中位置跳變、“后退”的現(xiàn)象。由圖6及表1的測(cè)試結(jié)果可得，在動(dòng)態(tài)定位方面，本文算法明顯優(yōu)于原始算法。貝葉斯算法的平均定位誤差為2.17 m，誤差在1 m和2 m內(nèi)的可信度分別為30.3%和50.8%；而改進(jìn)算法的平均定位誤差為1.15 m，定位誤差在1 m和2 m內(nèi)的可信度分別為42.9%和96.1%；改進(jìn)算法最大定位誤差為2.09 m，原始算法最大誤差高達(dá)5.83 m。

表1 兩種算法精度對(duì)比

3.2.2 試驗(yàn)2

為了進(jìn)一步對(duì)本文提出的算法進(jìn)行測(cè)試，在走廊區(qū)域設(shè)置長(zhǎng)50 m的復(fù)雜變向路線(包括三角形、弧形線路)，比較改進(jìn)算法和原始算法的定位結(jié)果，以此來檢驗(yàn)算法在復(fù)雜路徑的適用性和穩(wěn)健性，本試驗(yàn)將平均定位誤差和定位標(biāo)準(zhǔn)差作為衡量標(biāo)準(zhǔn)；同時(shí)，提取試驗(yàn)路線的近鄰點(diǎn)，每次提取4個(gè)距離最近的點(diǎn)及其后驗(yàn)概率P，分別計(jì)算兩算法的近鄰點(diǎn)與對(duì)應(yīng)點(diǎn)的信息熵[21]，信息熵越大，近鄰點(diǎn)的概率離散程度越大。以信息熵為衡量標(biāo)準(zhǔn)驗(yàn)證投票算法的性能。信息熵計(jì)算方法如下

(11)

式中，Pi為第i個(gè)近鄰點(diǎn)的后驗(yàn)概率。

兩算法的復(fù)雜路線定位路線如圖7所示，定位誤差和累計(jì)概率如圖8所示，信息熵如圖9所示,各項(xiàng)衡量參數(shù)見表2。

/(%)1m2m3m/m/m/bit64.798.41000.861.261.1994.81001000.500.420.63

從圖7可以看出，改進(jìn)算法的定位路線的定位效果更佳；由圖8和表2可得，復(fù)雜路徑試驗(yàn)中，改進(jìn)算法的平均定位誤差為0.50 m，點(diǎn)位誤差的極差和標(biāo)準(zhǔn)偏差分別為1.30和0.24 m，與貝葉斯算法相比，定位誤差降低了41.9%，標(biāo)準(zhǔn)偏差減少了1.02 m。因此，通過綜合考慮定位精度、定位偏差及誤差累計(jì)分布情況，改進(jìn)算法優(yōu)于原始算法并且具有較強(qiáng)的穩(wěn)健性。從圖9可得，改進(jìn)算法的整體信息熵小于原始算法對(duì)應(yīng)的值，表2中改進(jìn)算法的平均信息熵比原始算法低0.56 bit，故投票算法所得的先驗(yàn)概率對(duì)參考點(diǎn)有更好的約束性，且有利于定位。

4 結(jié) 語

本文提出了一種基于藍(lán)牙的貝葉斯指紋改進(jìn)算法，利用陀螺儀獲取的航向信息和高斯核函數(shù)模型，建立先驗(yàn)概率投票算法，將先驗(yàn)概率權(quán)重集中在待測(cè)點(diǎn)近鄰區(qū)域，提高了先驗(yàn)概率對(duì)定位范圍的約束，提高了定位精度。與貝葉斯指紋算法相比，該定位算法的平均定位誤差有明顯的下降；在不規(guī)則路線定位中，本文算法展現(xiàn)了較好的精度和穩(wěn)健性。后續(xù)工作為減少算法的運(yùn)行時(shí)間，進(jìn)一步提高算法的實(shí)時(shí)性。