基于藍牙的自回歸匹配室內定位算法

余成波,田林青,王艷麗

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

?

【信息科學與控制工程】

基于藍牙的自回歸匹配室內定位算法

余成波,田林青,王艷麗

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

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

藍牙；室內定位；自回歸

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

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

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

1 相關準備工作

1.1 k階近鄰算法

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

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

(1)

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

1.2 卡爾曼濾波原理分析

卡爾曼(kalman)濾波是一種利用線性狀態方程，通過系統輸入輸出觀測數據，對系統狀態進行最優估計的算法。由于觀測數據中包括噪聲和干擾，因此也將這種估計過程看作是濾波過程。卡爾曼濾波實際上是通過一種自回歸處理算法進行最優估計的過程。其數學思想包括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)是對待測值和最小均方誤差的預測，式(4)是kalman增益系數的定義，式(5)、式(6)是對待測值和最小均方誤差的最優估計；其中k、k-1代表時刻，u(k)是狀態控制量，通常取0；A為狀態轉移矩陣，H為觀測矩陣，通常都取1，AT、HT分別為A、H的轉置矩陣；Q，R分別是過程誤差和測量誤差，分別代表了預測時的方差和測量時的方差；z(k)是k時刻的測量值。x(k-1|k-1)是k-1時刻最優估計值，x(k|k-1)是由k-1時刻對k時刻的預測值，p(k-1|k-1)是k-1時刻最小均方誤差，p(k|k-1)是k-1時刻對k時刻的均方誤差估計；x(k|k)和p(k|k)是k時刻最優估計值和最優均方誤差估計。簡化后的公式為：

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

2 改進型非參數化室內定位算法

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

圖1 改進型非參數化室內定位算法流程

2.1 離線建庫階段

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

2.1.1 濾波

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

圖2 單點一次定位

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

圖3 多點多次定位

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

2.1.2 建庫

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

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

表1 指紋數據庫

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

2.2 在線定位階段

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

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

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

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值對應的坐標。z(k)=x1,x2,…,xN(作為橫坐標測量值)；z(k)=y1,y2,…,yN(作為縱坐標測量值)。

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

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

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

(12)

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

表2 單點多次最優定位

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

(13)

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

3 實驗結果與分析

3.1 實驗環境部署

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

表3 AP參數

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

圖4 空間格點化及藍牙節點布置

3.2 實驗結果

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

圖5 仿真坐標

4 結束語

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

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

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

[3] 萬國峰,鐘俊.改進的RSSI測距和定位算法[J].計算機應用研究,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] 江德祥,胡明清,陳益強,等.基于核嶺回歸的自適應藍牙定位方法[J].計算機應用研究,2010,27(9):3487-3489.

[6] 莫倩,熊碩.基于藍牙4.0的接近度分類室內定位算法[J].宇航計測技術,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] 韓旭海,夏文龍,周淵平.基于線性加權的藍牙室內定位算法[J].計算機系統應用,2015,24(1):119-122.

[9] 陳國平,馬耀輝,張百珂.基于指紋技術的藍牙室內定位系統[J].電子技術應用,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)；重慶市科技人才培養計劃(新產品研發團隊)資助項目(CSJC2013KJRC-TDJS40012)；重慶市高校優秀成果轉化資助項目(KJZH14213)

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

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

10.11809/scbgxb2017.04.021

余成波,田林青,王艷麗.基于藍牙的自回歸匹配室內定位算法[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