余成波,田林青,王艷麗

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

?

【信息科學(xué)與控制工程】

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

余成波,田林青,王艷麗

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

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

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

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

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

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

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

1.1 k階近鄰算法

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

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

(1)

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

1.2 卡爾曼濾波原理分析

卡爾曼(kalman)濾波是一種利用線性狀態(tài)方程，通過系統(tǒng)輸入輸出觀測數(shù)據(jù)，對系統(tǒng)狀態(tài)進(jìn)行最優(yōu)估計(jì)的算法。由于觀測數(shù)據(jù)中包括噪聲和干擾，因此也將這種估計(jì)過程看作是濾波過程。卡爾曼濾波實(shí)際上是通過一種自回歸處理算法進(jìn)行最優(yōu)估計(jì)的過程。其數(shù)學(xué)思想包括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)估計(jì)；其中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)估計(jì)值，x(k|k-1)是由k-1時刻對k時刻的預(yù)測值，p(k-1|k-1)是k-1時刻最小均方誤差，p(k|k-1)是k-1時刻對k時刻的均方誤差估計(jì)；x(k|k)和p(k|k)是k時刻最優(yōu)估計(jì)值和最優(yōu)均方誤差估計(jì)。簡化后的公式為：

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

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

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

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

2.1 離線建庫階段

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

2.1.1 濾波

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

圖2 單點(diǎn)一次定位

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

圖3 多點(diǎn)多次定位

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

2.1.2 建庫

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

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

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

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

2.2 在線定位階段

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

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

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

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

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

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

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

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

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

(12)

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

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

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

(13)

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境部署

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

表3 AP參數(shù)

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

圖4 空間格點(diǎn)化及藍(lán)牙節(jié)點(diǎn)布置

3.2 實(shí)驗(yàn)結(jié)果

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

圖5 仿真坐標(biāo)

4 結(jié)束語

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

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

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

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

[6] 莫倩,熊碩.基于藍(lán)牙4.0的接近度分類室內(nèi)定位算法[J].宇航計(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)的藍(lán)牙室內(nèi)定位算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2015,24(1):119-122.

[9] 陳國平,馬耀輝,張百珂.基于指紋技術(shù)的藍(lán)牙室內(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.

(責(zé)任編輯 楊繼森)

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

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

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

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

10.11809/scbgxb2017.04.021

余成波,田林青,王艷麗.基于藍(lán)牙的自回歸匹配室內(nèi)定位算法[J].兵器裝備工程學(xué)報(bào)，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