基于藍牙的自回歸匹配室內(nèi)定位算法

余成波,田林青,王艷麗

(重慶理工大學 遠程測試與控制研究所，重慶 400054)

?

【信息科學與控制工程】

基于藍牙的自回歸匹配室內(nèi)定位算法

余成波,田林青,王艷麗

(重慶理工大學 遠程測試與控制研究所，重慶 400054)

互聯(lián)網(wǎng)和移動終端的普及推動著LBS向ILBS的發(fā)展，而藍牙與移動終端良好的契合使其成為室內(nèi)定位技術(shù)的首選。介紹了常用的室內(nèi)定位算法，結(jié)合kalman濾波自回歸思想提出了一種改進型的非參數(shù)化室內(nèi)定位算法。實驗結(jié)果表明，改進后的定位算法定位精度在1m以內(nèi)，能夠滿足通常應(yīng)用環(huán)境對定位精度的要求，具有廣泛的市場價值。

藍牙；室內(nèi)定位；自回歸

近幾年，LBS(基于位置信息服務(wù))技術(shù)已經(jīng)在人們生活中得到廣泛應(yīng)用，比如通過GPS來獲得位置信息。然而，隨著互聯(lián)網(wǎng)和移動終端的普及和發(fā)展，推動著LBS向ILBS(基于室內(nèi)位置服務(wù))的過渡。一些景點、商場、博物館、機場等公共場所需要室內(nèi)定位提供精確的位置信息。而GPS等室外定位技術(shù)由于信號在室內(nèi)衰減快，不能用作室內(nèi)定位。室內(nèi)定位技術(shù)主要有藍牙、ZigBee、wifi、射頻識別、超寬帶等。由于藍牙和移動終端的良好契合以及藍牙4.0版本推出以來的低功耗、低成本、高性價比等優(yōu)點，使得藍牙技術(shù)成為移動終端室內(nèi)定位技術(shù)[1]的首選。

室內(nèi)定位算法可以分為參數(shù)化和非參數(shù)化兩種。參數(shù)化室內(nèi)算法是通過計算用戶和節(jié)點之間的距離建立數(shù)學模型進行室內(nèi)定位，通常有基于到達時間(TOA)、信號到達時間差(TDOA)、信號的到達時間角度(DOA)等方式。但是這種定位方式太依賴數(shù)學模型的建立而忽略了環(huán)境的復(fù)雜度，對于環(huán)境引起的多徑傳播等實際情況未考慮。因此,參數(shù)化室內(nèi)定位算法在實際定位中效果較差。非參數(shù)化室內(nèi)定位算法是把定位環(huán)境信息作為待定位目標的坐標函數(shù)進行估計，是一種環(huán)境感知的定位思想?；赗SSI指紋庫的室內(nèi)定位匹配算法是一種典型的非參數(shù)化室內(nèi)定位算法，分為離線建庫和在線匹配兩個階段，其原理是將在線定位階段的RSSI與離線建庫中的RSSI匹配定位。而用得最廣泛的匹配算法是k階近鄰算法。

本研究介紹了經(jīng)典匹配算法(k階近鄰算法)，根據(jù)k階近鄰算法存在的缺點結(jié)合kalman濾波自回歸思想對算法做了改進，提出一種基于藍牙的自回歸匹配室內(nèi)定位算法。實驗結(jié)果表明，改進后的算法定位精度高，可廣泛用于景點、商場等公共室內(nèi)定位環(huán)境[2]。

1 相關(guān)準備工作

1.1 k階近鄰算法

k階近鄰(k-Nearest Neighbour，KNN)算法[3]理論上比較成熟，也是簡單的機器學習算法。該方法的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。通俗點說，k階近鄰即是為了從樣本空間中找到k個最相似的樣本。

在k階近鄰匹配算法中，這個樣本空間便是前期所建立的RSSI指紋數(shù)據(jù)庫。通過在線定位階段的RSSI樣本與指紋庫中的樣本依次進行相似匹配，從中選出k個樣本[4]。匹配的思想是利用歐式距離進行篩選。假設(shè)實時定位某時刻獲得的RSSI信號強度為R=[R1,R2…Rn]，其中n表示藍牙節(jié)點數(shù)。數(shù)據(jù)庫中坐標點(x,y)對應(yīng)的信號強度值為R(x,y)=[R1(x,y),R2(x,y),…,Rn(x,y)]。通過公式

(1)

找到最小的k個L對應(yīng)的坐標(x,y)，對這k個坐標求質(zhì)心便得定位坐標。

1.2 卡爾曼濾波原理分析

卡爾曼(kalman)濾波是一種利用線性狀態(tài)方程，通過系統(tǒng)輸入輸出觀測數(shù)據(jù)，對系統(tǒng)狀態(tài)進行最優(yōu)估計的算法。由于觀測數(shù)據(jù)中包括噪聲和干擾，因此也將這種估計過程看作是濾波過程。卡爾曼濾波實際上是通過一種自回歸處理算法進行最優(yōu)估計的過程。其數(shù)學思想包括5個核心公式:

x(k|k-1)=A×x(k-1|k-1)+B×u(k)

(2)

p(k|k-1)=A×p(k-1|k-1)×AT+Q

(3)

Kg(k)=p(k|k-1)HT/(H×p(k|k-1)×HT+R)

(4)

x(k|k)=x(k|k-1)+Kg(k)(z(k)-H×x(k|k-1))

(5)

p(k|k)=(1-Kg(k)H)p(k|k-1)

(6)

式(2)、式 (3)是對待測值和最小均方誤差的預(yù)測，式(4)是kalman增益系數(shù)的定義，式(5)、式(6)是對待測值和最小均方誤差的最優(yōu)估計；其中k、k-1代表時刻，u(k)是狀態(tài)控制量，通常取0；A為狀態(tài)轉(zhuǎn)移矩陣，H為觀測矩陣，通常都取1，AT、HT分別為A、H的轉(zhuǎn)置矩陣；Q，R分別是過程誤差和測量誤差，分別代表了預(yù)測時的方差和測量時的方差；z(k)是k時刻的測量值。x(k-1|k-1)是k-1時刻最優(yōu)估計值，x(k|k-1)是由k-1時刻對k時刻的預(yù)測值，p(k-1|k-1)是k-1時刻最小均方誤差，p(k|k-1)是k-1時刻對k時刻的均方誤差估計；x(k|k)和p(k|k)是k時刻最優(yōu)估計值和最優(yōu)均方誤差估計。簡化后的公式為：

x(k|k-1)=x(k-1|k-1)

(7)

p(k|k-1)=p(k-1|k-1)+Q

(8)

Kg(k)=p(k|k-1)/(p(k|k-1)+R)

(9)

x(k|k)=x(k|k-1)+Kg(k)(z(k)-x(k|k-1))

(10)

p(k|k)=(1-Kg(k))p(k|k-1)

(11)

整個kalman濾波過程相當于是在預(yù)測值x(k|k-1)和測量值z(k)之間權(quán)衡，這種權(quán)衡不是簡單地求平均，而是通過kalman增益Kg進行最優(yōu)估計。并且最小均方誤差p(k|k)的不斷更新讓整個自回歸運算進行下去，從而得到各個時刻的最優(yōu)估計值。能夠看出，一旦初始預(yù)測值x(k-1|k-1)、最小初始均方誤差p(k-1|k-1)和測量值z(k)確定。影響最優(yōu)估計結(jié)果x(k|k)的就在于Q、R的取值。

2 改進型非參數(shù)化室內(nèi)定位算法

k階近鄰算法是用得最多的RSSI指紋庫匹配算法，但是簡單地根據(jù)歐式距離匹配k(通常取3或者4)個點求質(zhì)心就決定了算法的定位效果不夠好。因為無論是建庫階段還是實時定位所測數(shù)據(jù)都存在噪聲和干擾，而簡單通過幾個點求質(zhì)心的方法沒能消除噪聲和干擾，就會造成定位效果不好或者定位波動過大?；诖?，結(jié)合卡爾曼濾波的自回歸思想，提出一種基于藍牙的自回歸匹配定位算法，消除定位過程中的環(huán)境誤差和干擾，進行更準確地定位[5]。圖1是改進算法的流程圖。

圖1 改進型非參數(shù)化室內(nèi)定位算法流程

2.1 離線建庫階段

離線建庫的優(yōu)劣決定了后期在線匹配的精度。在離線建庫階段先對接收信號進行濾波處理，再將處理后的信號存入數(shù)據(jù)庫。

2.1.1 濾波

引入kalman濾波對接收信號強度值進行處理。取第一次掃描到節(jié)點n的信號強度值Rn為初始值x(k-1|k-1)；p(k-1|k-1)=0；第二次及以后掃描到節(jié)點n的信號強度值作為z(k)；過程誤差Q和測量誤差R按經(jīng)驗分別取10-6和10-1。隨著掃描進行，不斷更新最小均方誤差p(k|k)讓整個濾波過程進行下去，這樣采集到的信號強度值便是濾波之后的信號強度。將坐標點(5,4)一次定位采集到的藍牙節(jié)點1的100組經(jīng)濾波后的信號強度值導(dǎo)入Matlab中仿真，如圖2所示。

圖2 單點一次定位

圖2中單點一次定位所接收的信號強度值穩(wěn)定。這種穩(wěn)定的效果不難得到，只要Q/R比值足夠小，輸出結(jié)果就會趨近于預(yù)測值x(k-1|k-1)。為了驗證這種濾波方式對不同坐標點采集信號強度值的差異性，需要對多個坐標進行多次定位來對比?，F(xiàn)分別對3個坐標進行10次定位，采集節(jié)點1對應(yīng)的信號強度值導(dǎo)入Matlab，仿真結(jié)果如圖3所示。

圖3 多點多次定位

圖3中3條曲線從上到下依次對應(yīng)坐標(5,4)、(4,5.5)、(6.5,7)。圖3中第一條曲線的三角即對應(yīng)圖2中的單點(5,4)一次定位。從圖3中可以看出對單點的多次定位采集的信號強度值存在一定的波動，為了盡可能消除這種波動，通過單點不同時間段多次采集求平均的方法更新數(shù)據(jù)庫中的信號強度值即可；并且不同的坐標點之間采集的RSSI存在差異性，這為后期在線定位階段對不同坐標點進行準確定位提供了可能。

2.1.2 建庫

藍牙節(jié)點AP(Access Point)的廣播數(shù)據(jù)主要由唯一標識符UUID、主要值major、次要值minor、信號強度RSSI、設(shè)備名稱iBeaconName組成[6]。

假如定位空間內(nèi)有n個藍牙節(jié)點(AP1到APn)，定義坐標為(xi,yi)的定位節(jié)點AP(不屬于n個藍牙節(jié)點)接收到來自藍牙節(jié)點n的信號強度值為Rn(xi,yi)。將定位節(jié)點坐標及其接收到的來自n個節(jié)點的信號強度值(濾波之后的)存入數(shù)據(jù)庫中。最終建立指紋數(shù)據(jù)庫如表1所示。

表1 指紋數(shù)據(jù)庫

表1中APn(n=1,2,3,…,n)對應(yīng)列表示坐標接收到來自節(jié)點n的信號強度值。相比于k階近鄰算法的指紋庫，加入kalman濾波后建立的指紋庫的信號強度值更加準確和穩(wěn)定。

2.2 在線定位階段

在線定位階段是在離線建庫階段完成后進行的。此階段就是將定位點接收到的藍牙信號強度值與數(shù)據(jù)庫中進行匹配完成定位。通常采用的匹配算法是1.1中介紹的k階近鄰算法，雖然簡單有效，但定位精度不夠高。針對定位過程中存在噪聲和誤差，結(jié)合卡爾曼濾波的自回歸思想對定位坐標進行最優(yōu)估計，提出一種自回歸匹配室內(nèi)定位算法。具體思路如下：

1) 利用k階近鄰算法中的歐式距離公式匹配出N個最小的L值。按L值由小到大，其對應(yīng)的坐標依次為(x1,y1)(x2,y2)…(xn,yn)。

2) 定位坐標(x,y)的橫縱坐標x,y應(yīng)當分開進行最優(yōu)估計。

3) 令最小均方誤差p(k-1|k-1)=0。

4) x(k-1|k-1)=(x1+x2+x3)/3(橫坐標的初始估計值)；x(k-1|k-1)=(y1+y2+y3)/3(縱坐標初始估計值)。

5) 測量值z(k)用N個最小L值對應(yīng)的坐標。z(k)=x1,x2,…,xN(作為橫坐標測量值)；z(k)=y1,y2,…,yN(作為縱坐標測量值)。

6) 令Q=10-6，kk=R/Q。

可以看出，自回歸匹配定位算法是通過N個點來對定位點橫縱坐標分別進行最優(yōu)估計。通過對方程中某些參數(shù)的一些賦值，最后存在兩個重要變量，N和kk。N是經(jīng)歐式距離公式匹配出來的坐標點個數(shù)，kk是型定義的比值變量，Q值確定后，kk決定著R值的大小。N和kk不能簡單地對其賦值，應(yīng)該通過實際情況來具體決定。

下面對坐標點(5,4)在不同時間段進行累計20次定位。以N和kk為自變量(由于N值過大會造成定位誤差，kk過大會造成仿真時間長并且kk大于103后影響不大，因此給自變量設(shè)定范圍很有必要)，每次定位結(jié)果與坐標點之間的距離s作為因變量[7-8]。當s取得最小值時，求出相應(yīng)N和kk值

(12)

其中(x0,y0)為實際坐標，(x,y)為定位坐標。當s取得最小時，得到相應(yīng)的kk和N。

表2 單點多次最優(yōu)定位

如表2所示。n表示定位次數(shù)，kk和N是定位結(jié)果和實際位置之間的距離s取最小smin時得到的值[9]。從表2可以看出，N值變化不大，通過求平均得到N=14。但kk是一個跨度較大的變量，不能簡單求平均取值，因此

(13)

表示n次定位結(jié)果和實際定位點距離之和。當N=14時，S取最小值時便能得到kk值。仿真結(jié)果顯示當kk=34時，S最小，Smin=26.637 0。

3 實驗結(jié)果與分析

3.1 實驗環(huán)境部署

本實驗采用Android設(shè)備作為離線建庫和實時定位階段的實驗設(shè)備。藍牙節(jié)點選取ibeacon4.0設(shè)備，具體參數(shù)如表3所示。

表3 AP參數(shù)

在實驗區(qū)域(10 m×8 m)范圍內(nèi)總共布置6個藍牙發(fā)射節(jié)點，逆時針依次為(3,0)、(7,0)、(10,4)、(7,8)、(3,8)、(0,4)6個點。在區(qū)域內(nèi)每0.5m進行采樣取點，總共320個采樣點。每個采樣點分別在不用時間段采集共50組數(shù)據(jù)求平均存入數(shù)據(jù)庫。藍牙節(jié)點布置如圖4所示。

圖4 空間格點化及藍牙節(jié)點布置

3.2 實驗結(jié)果

根據(jù)搭好的環(huán)境，在實驗區(qū)域內(nèi)選取定位點。對定位點進行十次掃描定位，將定位點數(shù)據(jù)導(dǎo)入Matlab中進行仿真。為了體現(xiàn)改進算法定位的優(yōu)越性，引入k階近鄰算法進行對比[10]。仿真結(jié)果如圖5所示。向下的三角形為實際坐標，圓圈為通過k階近鄰算法定位的結(jié)果(10次定位存在幾個重合點，因此圖5中只有8個圓圈點)，星號為改進算法定位點?？梢钥闯鰇階近鄰算法定位結(jié)果誤差較大，縱坐標跨度1.5 m左右，橫坐標跨度2.5 m左右。而改進后的定位算法橫縱坐標跨度大致都在1 m以內(nèi)，具有較好的精確度。并且將不同坐標點的定位數(shù)據(jù)導(dǎo)入改進算法進行定位，定位效果明顯優(yōu)于k階近鄰算法，定位誤差大致都在1 m以內(nèi)。

圖5 仿真坐標

4 結(jié)束語

本文針對當前熱門的基于藍牙4.0的室內(nèi)定位技術(shù)，在室內(nèi)定位算法上做了改進。實驗結(jié)果表明，通過引入卡爾曼濾波對接收信號進行處理(尤其是建庫階段)之后再通過自回歸匹配算法進行定位的效果明顯優(yōu)于k階近鄰匹配算法，定位精度高、穩(wěn)定性好，可廣泛用于商場、博物館、旅游景點等室內(nèi)定位領(lǐng)域，具有很大市場價值。

[1] 趙銳,鐘榜,朱祖禮,等.室內(nèi)定位技術(shù)及應(yīng)用綜述[J].電子科技,2014(3):154-157.

[2] 石志京,徐鐵峰,劉太君,等.基于iBeacon基站的室內(nèi)定位技術(shù)研究[J].移動通信,2012，39(7):88-91.

[3] 萬國峰,鐘俊.改進的RSSI測距和定位算法[J].計算機應(yīng)用研究,2012(11):4156-4158.

[4] MOHAMED ER RIDA.Indoor location position based on Bluetooth Signal Strength[C]//International Conference on Information Science and Control Engineering.[S.l.]:[s.n.],2015.

[5] 江德祥,胡明清,陳益強,等.基于核嶺回歸的自適應(yīng)藍牙定位方法[J].計算機應(yīng)用研究,2010,27(9):3487-3489.

[6] 莫倩,熊碩.基于藍牙4.0的接近度分類室內(nèi)定位算法[J].宇航計測技術(shù),2014(6):66-70.

[7] SANGWOO LEe.Range-free Indoor Positioning System Using Smartphone with Bluetooth Capability [D].Department of Electronics and Computer Engineering,Hanyang University,Seoul,Korea,2014.

[8] 韓旭海,夏文龍,周淵平.基于線性加權(quán)的藍牙室內(nèi)定位算法[J].計算機系統(tǒng)應(yīng)用,2015,24(1):119-122.

[9] 陳國平,馬耀輝,張百珂.基于指紋技術(shù)的藍牙室內(nèi)定位系統(tǒng)[J].電子技術(shù)應(yīng)用,2013,39(3):104-107.

[10]ZHANG S,WANG J,LIU X,et al.Range-free selective multilateration for anisotropic wireless sensor networks[C]//in Proc.IEEE SECON.[S.l.]:[s.n.],2012:299-307.

(責任編輯 楊繼森)

Recursive Matching Indoor Positioning Algorithm Based on Bluetooth

YU Cheng-Bo，TIAN Lin-Qing，WANG Yan-Li

(Institute of Remote Test and Control, Chongqing University of Technology, Chongqing 400054, China)

The popularity of the Internet and mobile terminal promotes the development of LBS to ILBS. A good combination with mobile terminal makes it the first choice of indoor positioning technology for bluetooth. This paper introduced the common indoor positioning algorithm and proposed an improved non-parametric indoor positioning algorithm combining recursive theory of kalman filtering. The experimental results show that the precision of the improved indoor positioning algorithm is less than 1m, which can meet the requirements of the general application environment for indoor positioning accuracy and has great market value.

bluetooth; indoor positioning; recursive

2016-11-15；

2016-12-15

國家自然科學基金資助項目(61402063)；重慶市科技人才培養(yǎng)計劃(新產(chǎn)品研發(fā)團隊)資助項目(CSJC2013KJRC-TDJS40012)；重慶市高校優(yōu)秀成果轉(zhuǎn)化資助項目(KJZH14213)

余成波(1965—)，男，博士，教授，主要從事遠程測試與控制技術(shù)、信號與信息處理研究。

田林青(1991—)，男，碩士研究生，主要從事基于藍牙低功耗的室內(nèi)定位技術(shù)、無線傳感網(wǎng)絡(luò)研究，E-mail：792085369@qq.com。

10.11809/scbgxb2017.04.021

余成波,田林青,王艷麗.基于藍牙的自回歸匹配室內(nèi)定位算法[J].兵器裝備工程學報，2017(4):95-99.

format:YU Cheng-Bo，TIAN Lin-Qing，WANG Yan-Li.Recursive Matching Indoor Positioning Algorithm Based on Bluetooth[J].Journal of Ordnance Equipment Engineering,2017(4):95-99.

TP98

A

2096-2304(2017)04-0095-05