基于核函數(shù)與卡爾曼濾波的室內(nèi)定位方法

張　旭,　張　裕,2,　鄭正奇,,　陳　雯

(1.華東師范大學(xué) 信息科學(xué)技術(shù)學(xué)院,上?！?00241;2.上海市計(jì)量測試技術(shù)研究院,上海　200120;3.空間信息和定位導(dǎo)航上海高校工程中心,上?！?00241)

?

基于核函數(shù)與卡爾曼濾波的室內(nèi)定位方法

張旭1,張?jiān)?,2,鄭正奇1,3,陳雯3

(1.華東師范大學(xué) 信息科學(xué)技術(shù)學(xué)院,上海200241;2.上海市計(jì)量測試技術(shù)研究院,上海200120;3.空間信息和定位導(dǎo)航上海高校工程中心,上海200241)

摘要：針對室內(nèi)定位中存在的定位精度不高、定位穩(wěn)定性較差的問題,提出了一種基于核函數(shù)與卡爾曼濾波結(jié)合的室內(nèi)定位算法.首先利用核函數(shù)作為匹配算法進(jìn)行初步定位,高斯核函數(shù)可以充分捕獲參考點(diǎn)指紋與測試點(diǎn)RSS之間的非線性相關(guān)性,取得比K最近鄰算法更好的匹配效果,再利用卡爾曼濾波對核函數(shù)的定位結(jié)果作濾波處理.實(shí)驗(yàn)結(jié)果表明,在真實(shí)無線局域網(wǎng)環(huán)境下,對核函數(shù)定位的結(jié)果作卡爾曼濾波處理后,均方根誤差降低了25%,2 m以內(nèi)的定位準(zhǔn)確度由75%提高到90%,定位穩(wěn)定性提高了29%.

關(guān)鍵詞：室內(nèi)定位; 定位準(zhǔn)確度; 高斯核函數(shù); 卡爾曼濾波

隨著當(dāng)今社會的發(fā)展,基于位置的服務(wù)變得越來越重要.室外定位技術(shù)以全球定位系統(tǒng)為基礎(chǔ),包括美國的GPS定位系統(tǒng),俄羅斯的GLONASS定位系統(tǒng)以及我國自主研制的北斗衛(wèi)星導(dǎo)航定位系統(tǒng),利用這些定位系統(tǒng)可以實(shí)現(xiàn)室外全天候的實(shí)時(shí)定位.然而,衛(wèi)星信號在室內(nèi)環(huán)境中強(qiáng)度較弱,如果在室內(nèi)仍采用衛(wèi)星信號進(jìn)行定位,定位誤差可達(dá)幾十米甚至上百米,這顯然無法滿足在室內(nèi)3m以內(nèi)定位精度的需求.考慮到目前室內(nèi)環(huán)境中普遍存在的WLAN信號[1-3],人們開始考慮采用WLAN信號來實(shí)現(xiàn)室內(nèi)定位.

室內(nèi)定位的研究始于20世紀(jì)90年代末,其中也涌現(xiàn)出一批優(yōu)質(zhì)的定位系統(tǒng)和定位算法.美國微軟研究院于2000年首次提出了基于WLAN的室內(nèi)定位系統(tǒng)RADAR[4],在空曠的室內(nèi)環(huán)境下,定位精度可達(dá)2～5m,但在復(fù)雜的室內(nèi)環(huán)境,定位精度并不理想.文獻(xiàn)[5]提出了Horus系統(tǒng),該系統(tǒng)采用概率統(tǒng)計(jì)模型,并首次將聚類分塊運(yùn)用于指紋庫的建立中,與RADAR系統(tǒng)相比,既提高了定位精度,同時(shí)也降低了系統(tǒng)的計(jì)算復(fù)雜度.在算法優(yōu)化方面,研究人員將人工神經(jīng)網(wǎng)絡(luò)[6](artificialneuralnetwork,ANN)、支持向量回歸[7](supportvectorregression,SVR),以及核函數(shù)[8]等算法應(yīng)用于室內(nèi)定位中,進(jìn)一步提高了定位精度.雖然上述定位系統(tǒng)和定位算法在室內(nèi)定位領(lǐng)域都取得了一定的成果,但仍存在定位精度不夠理想、定位穩(wěn)定性較差等問題[9].

為了進(jìn)一步提高定位精度,本文提出了基于核函數(shù)和卡爾曼濾波的室內(nèi)定位方法.首先采用核函數(shù)法進(jìn)行初步定位,針對實(shí)時(shí)定位過程中用戶移動(dòng)位置不平緩、定位穩(wěn)定性較差的問題,再利用卡爾曼濾波算法對核函數(shù)定位結(jié)果作濾波修正,實(shí)驗(yàn)結(jié)果表明濾波以后定位精度和定位穩(wěn)定性均有明顯改善.

1Kernel函數(shù)定位

(1)

如果定義在X×X上的函數(shù)K滿足:?x,z∈X,都有

(2)

則稱函數(shù)K(x,z)為核函數(shù),其中〈·〉為高維空間H中的內(nèi)積.核函數(shù)可以將低維空間線性不可分的模式映射到高維特征空間,從而在高維特征空間中挖掘出數(shù)據(jù)間的非線性相關(guān)性.

傳統(tǒng)的定位算法如K最近鄰(Knearestneighbor,KNN)算法[10],僅通過度量參考點(diǎn)和測試點(diǎn)間的接收信號強(qiáng)度(receivedsignalstrength,RSS)的歐式距離來實(shí)現(xiàn)定位,而未考慮到RSS之間可能存在的非線性相關(guān)性,雖然定位算法較簡單,但定位精度并不理想.

利用核函數(shù)可以度量在測試點(diǎn)采集的接入點(diǎn)(accesspoint,AP)的RSS樣本向量同每個(gè)參考點(diǎn)指紋的相似性,從中找出相似度最高的若干個(gè)指紋,再將這若干個(gè)指紋的位置坐標(biāo)進(jìn)行加權(quán)平均即可估算出待定位點(diǎn)的位置坐標(biāo).由于高斯核函數(shù)平滑性能較好,而且具有能夠逼近任意非線性函數(shù)的能力,故本文采用高斯核函數(shù)進(jìn)行定位,對應(yīng)的相似性權(quán)重系數(shù)為

(3)

式中:F(Pi)是一個(gè)L×n的矩陣,代表第i個(gè)參考點(diǎn)Pi的指紋信息,i=1,2,3,…,L;t為掃描次數(shù),t=1,2,3,…,n;r是一個(gè)L×1的矩陣,表示在測試點(diǎn)采集到的來自于L個(gè)AP的RSS;σ為核函數(shù)的寬度.由式(3)計(jì)算得出相似性權(quán)重最大的前k個(gè)指紋,則待定位點(diǎn)坐標(biāo)為

(4)

相較于KNN算法中取某個(gè)AP若干次掃描所得信號強(qiáng)度的平均值,核函數(shù)可以充分利用每個(gè)參考點(diǎn)上所有的RSS樣本信息,在核函數(shù)空間中可以較好地捕獲信號RSS的非線性相關(guān)性,因此可以獲得比KNN算法更好的定位效果.

2Kalman濾波

Kalman濾波[9,11-14]是一種線性最小方差估計(jì),算法采用狀態(tài)空間方法在時(shí)域內(nèi)設(shè)計(jì)濾波器,適用于對多維隨機(jī)過程進(jìn)行濾波,而且具有遞推性.當(dāng)模型足夠準(zhǔn)確且系統(tǒng)狀態(tài)和參數(shù)較為穩(wěn)定時(shí),濾波性能較好.利用卡爾曼濾波可以減少噪聲對系統(tǒng)的影響,從而達(dá)到提高定位精度的目的.

由于在實(shí)時(shí)定位過程中,一般要求在較短的時(shí)間內(nèi)計(jì)算出用戶的位置.然而較短的信號采集時(shí)間會導(dǎo)致采集到的信號樣本偏少,從而定位偏差較大,用戶移動(dòng)位置不平緩.本文提出一種基于Kernel-Kalman(KK)的室內(nèi)定位方法,首先利用核函數(shù)法對待測點(diǎn)進(jìn)行定位計(jì)算,再利用卡爾曼濾波對核函數(shù)定位結(jié)果作濾波修正,以此進(jìn)一步減小核函數(shù)定位的偏差,提高定位精度.

卡爾曼濾波的預(yù)測方程和觀測方程分別為

(5)

zk=Hkxk+mkk≥1

(6)

式中:xk為狀態(tài)向量;zk為觀測向量;Φk,k-1為狀態(tài)轉(zhuǎn)移矩陣;Hk為觀測矩陣;Γk-1為系統(tǒng)噪聲矩陣;wk-1與mk分別是過程噪聲和觀測噪聲,一般為高斯白噪聲,且它們滿足

式中:Q與R分別代表過程噪聲和觀測噪聲的方程矩陣；δ為沖激函數(shù).

初始條件為

(7)

(8)

卡爾曼濾波的時(shí)間更新方程為

(9)

測量更新方程為

(11)

式中,K為濾波增益.

定義用戶行走的二維模型如下:

(12)

(13)

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

分別利用仿真場景和真實(shí)場景將提出的KK算法與Kernel算法以及室內(nèi)定位中較常用的KNN算法進(jìn)行對比,通過定位結(jié)果的RMSE(均方根誤差)、定位誤差的CDF(累積分布函數(shù))及定位誤差的Std.(標(biāo)準(zhǔn)差)這3個(gè)方面的對比來驗(yàn)證本文所提出算法的有效性.

3.1仿真場景

3.1.1仿真場景的建立

首先利用Matlab仿真對本文提出的定位方法進(jìn)行了詳細(xì)的性能分析.定位區(qū)域面積為40m×40m,周圍共分布12個(gè)AP.參考點(diǎn)個(gè)數(shù)共計(jì)1 600個(gè),間距為1m.按照行走路徑選取測試點(diǎn)個(gè)數(shù)為200個(gè).仿真實(shí)驗(yàn)場景如圖1所示(圖中未標(biāo)出行走路徑).

圖1　仿真場景示意圖

對于某一位置Q處,第i個(gè)接入點(diǎn)APi在點(diǎn)Q處的信號RSS平均損耗為

(14)

式中:dAPi,Q表示接入點(diǎn)APi與采樣點(diǎn)位置Q間的距離;P(d0)表示在參考距離d0=1m處RSS信號傳播的路徑損耗;α表示路徑損耗系數(shù).若以Pt表示接入點(diǎn)的發(fā)射功率,則APi在采樣位置Q處的信號強(qiáng)度為

(15)

仿真實(shí)驗(yàn)的基本參數(shù)設(shè)置[15]如表1所示(見下頁).

為了與真實(shí)環(huán)境相接近,在本仿真實(shí)驗(yàn)中測試點(diǎn)所接收到的平均信號強(qiáng)度加入了均值為0,方差為1的高斯白噪聲.

3.1.2仿真實(shí)驗(yàn)結(jié)果

仿真實(shí)驗(yàn)結(jié)果如圖2所示(見下頁).其中,圖2(a)給出了3種算法定位結(jié)果的均方根誤差.當(dāng)選擇200個(gè)測試點(diǎn)時(shí),KNN,Kernel及KK的RMSE分別為1.21,0.95,0.72m.核函數(shù)法相比于KNN算法定位精度提高了22%,卡爾曼濾波可以進(jìn)一步將核函數(shù)法定位精度提高24%.

表1　基本參數(shù)

圖2　仿真場景下實(shí)驗(yàn)結(jié)果

圖2(b)展示了3種定位算法定位誤差的累積概率分布.可以看出核函數(shù)法定位性能要明顯優(yōu)于KNN算法,經(jīng)過卡爾曼濾波進(jìn)行濾波修正后,可以將核函數(shù)法1m以內(nèi)定位準(zhǔn)確率由69%提高至84%.

定位標(biāo)準(zhǔn)差可以反映定位算法的穩(wěn)定性,如圖2(c)所示.在定位的穩(wěn)定性方面,Kernel算法優(yōu)于KNN算法.經(jīng)過卡爾曼濾波以后,核函數(shù)的定位穩(wěn)定性有明顯改善,定位標(biāo)準(zhǔn)差由0.476m降為0.355m,定位穩(wěn)定性提高了25%.

3.2實(shí)際場景

3.2.1實(shí)際場景的搭建

圖3為實(shí)驗(yàn)真實(shí)環(huán)境的示意圖,位于上海市計(jì)量測試技術(shù)研究院某實(shí)驗(yàn)樓的4樓.實(shí)驗(yàn)場景的面積為50m×20m,場景內(nèi)包含13個(gè)AP,相鄰AP間的距離約為20m.參考點(diǎn)和測試點(diǎn)均位于走廊及兩側(cè)的樓廳.圖中黑色圓點(diǎn)代表參考點(diǎn),紅色圓點(diǎn)代表測試點(diǎn).黑色連線連接各個(gè)測試點(diǎn),表示測試者的行走軌跡,測試者從S點(diǎn)出發(fā),按箭頭所示路線行走至D點(diǎn)停止.

圖3　實(shí)際場景示意圖

本次實(shí)驗(yàn)選取了116個(gè)參考點(diǎn),60個(gè)測試點(diǎn).采集設(shè)備為一臺聯(lián)想e450筆記本電腦,配置為i5-4210U,8GBDDR3內(nèi)存,WiFi信號掃描軟件為inSSIDer,掃描頻率約為1次/s.實(shí)驗(yàn)者在參考點(diǎn)的采樣時(shí)間為180s,在線測試階段,每個(gè)測試點(diǎn)的采樣時(shí)間為30s,即每個(gè)測試點(diǎn)讀取信號強(qiáng)度約30次.數(shù)據(jù)處理平臺仍采用Matlab,包含數(shù)據(jù)文件解析、位置指紋庫的建立以及在線匹配運(yùn)算等模塊.

3.2.2實(shí)際場景的實(shí)驗(yàn)結(jié)果

圖4展示了真實(shí)場景下的實(shí)驗(yàn)結(jié)果,從圖4(a)中可以看出,隨著測試樣本的增多,定位算法的RMSE趨于穩(wěn)定.當(dāng)樣本個(gè)數(shù)為60時(shí),KK算法的均方根誤差為1.37m,而核函數(shù)法和KNN算法的RSME分別為1.83m和1.94m.核函數(shù)法的定位誤差低于KNN算法.卡爾曼濾波可以將核函數(shù)法的定位精度提高25%.

圖4　實(shí)際場景下實(shí)驗(yàn)結(jié)果

圖4(b)給出了KK算法、核函數(shù)法以及KNN算法三者的定位誤差累積概率分布.以2m以內(nèi)定位誤差百分比作為評價(jià)指標(biāo),卡爾曼濾波可以將核函數(shù)法定位準(zhǔn)確度由75%提高至90%,且由圖中可以看出,經(jīng)過卡爾曼濾波以后,定位的誤差可以基本保證在3m以內(nèi).

圖4(c)為實(shí)際場景中3種方法定位標(biāo)準(zhǔn)差的對比結(jié)果,隨著測試樣本數(shù)的增多,定位標(biāo)準(zhǔn)差趨向于穩(wěn)定.當(dāng)測試樣本數(shù)為60個(gè)時(shí),KNN和核函數(shù)法的定位標(biāo)準(zhǔn)差分別為1.12m和1.08m,而KK算法的定位標(biāo)準(zhǔn)差為0.76m.相比于KNN定位法,核函數(shù)法的定位穩(wěn)定性改善不夠明顯,猜想可能的原因是測試點(diǎn)個(gè)數(shù)較少,且實(shí)驗(yàn)場景只包含了走廊和樓廳的空白區(qū)域,所以測試數(shù)據(jù)無法完整地展現(xiàn)定位性能.但可以明顯看出,經(jīng)過卡爾曼濾波以后,核函數(shù)法的定位穩(wěn)定性提高了29%,定位性能有較大的改善.

4結(jié)論

提出了一種基于核函數(shù)與卡爾曼濾波結(jié)合的室內(nèi)定位算法,首先采用核函數(shù)對待測點(diǎn)作初步定位,再利用卡爾曼濾波對定位結(jié)果作濾波處理.核函數(shù)可以充分利用參考點(diǎn)的所有RSS樣本信息,較好地捕獲了信號RSS的非線性模式,能夠獲得比KNN算法更好的定位性能.針對室內(nèi)定位中用戶移動(dòng)位置不平緩、定位穩(wěn)定性較差的問題,卡爾曼濾波可以顯著降低定位位置波動(dòng),提高定位的穩(wěn)定性.實(shí)驗(yàn)結(jié)果表明,在對核函數(shù)定位的結(jié)果做卡爾曼濾波處理后,均方根誤差降低了25%,2m以內(nèi)的定位準(zhǔn)確度由75%提高到90%,定位穩(wěn)定性提高了29%.

隨著具有WiFi連接功能的智能手機(jī)的大量普及,本文提出的算法可以在基于智能移動(dòng)設(shè)備的室內(nèi)定位系統(tǒng)中廣泛運(yùn)用.未來的工作主要有:a.針對室內(nèi)WiFi信號波動(dòng)較大的問題,考慮用卡爾曼濾波對設(shè)備采集到的RSS作濾波處理,提高掃描的WiFi信號的穩(wěn)定性;b.從減少移動(dòng)設(shè)備定位計(jì)算量的角度出發(fā),采用K-means聚類及其改進(jìn)算法對位置指紋庫進(jìn)行聚類分析,從而降低系統(tǒng)的匹配計(jì)算量,提高定位系統(tǒng)的響應(yīng)速率.

參考文獻(xiàn)：

[1]BISIOI,CERRUTIM,LAVAGETTOF,etal.AtraininglessWiFifingerprintpositioningapproachovermobiledevices[J].IEEEAntennasandWirelessPropagationLetters,2014,13:832-835.

[2]CHONY,CHAH.LifeMap:asmartphone-basedcontextproviderforlocation-basedservices[J].IEEEPervasiveComputing,2011,10(2):58-67.

[3]LIUH,DARABIH,BANERJEEP,etal.Surveyofwirelessindoorpositioningtechniquesandsystems[J].IEEETransactionsonSystems,Man,andCybernetics,PartC(ApplicationsandReviews),2007,37(6):1067-1080.

[4]CHENLN,LIBH,ZHAOK,etal.AnimprovedalgorithmtogenerateaWiFifingerprintdatabaseforindoorpositioning[J].Sensors,2013,13(8):11085-11096.

[5]REHIMM.Horus:aWLAN-basedindoorlocationdeterminationsystem[M].Maryland:UniversityofMarylandatCollegePark,2004.

[6]FANGSH,LINTN.Indoorlocationsystembasedondiscriminant-adaptiveneuralnetworkinIEEE802.11environments[J].IEEETransactionsonNeuralNetworks,2008,19(11):1973-1978.

[7]WUZL,LICH,NGJKY,etal.Locationestimationviasupportvectorregression[J].IEEETransactionsonMobileComputing,2007,6(3):311-321.[8]KUSHKIA,PLATANIOTISKN,VENETSANOPOULOSAN.Kernel-basedpositioninginwirelesslocalareanetworks[J].IEEETransactionsonMobileComputing,2007,6(6):689-705.

[9]趙永翔,周懷北,陳淼,等.卡爾曼濾波在室內(nèi)定位系統(tǒng)實(shí)時(shí)跟蹤中的應(yīng)用[J].武漢大學(xué)學(xué)報(bào)(理學(xué)版),2009,55(6):696-700.

[10]FANGSH,LINT.PrincipalcomponentlocalizationinindoorWLANenvironments[J].IEEETransactionsonMobileComputing,2012,11(1):100-110.

[11]OUTEMZABETS,NERGUIZIANC.Accuracyenhance-mentofanindoorANN-basedfingerprintinglocationsystemusingKalmanfiltering[C]∥ProceedingsoftheIEEE19thInternationalSymposiumonPersonal,IndoorandMobileRadioCommunications.Cannes:IEEE,2008:1-5.

[12]CHIJN,QIANCF,ZHANGPY,etal.AnovelELMbasedadaptiveKalmanfiltertrackingalgorithm[J].Neurocomputing,2014,128:42-49.

[13]NGUYENHN,ZHOUJ,KANGHJ.AcalibrationmethodforenhancingrobotaccuracythroughintegrationofanextendedKalmanfilteralgorithmandanartificialneuralnetwork[J].Neurocomputing,2015,151:996-1005.

[14]CHENZ,ZOUH,JIANGH,etal.FusionofWiFi,smartphonesensorsandlandmarksusingtheKalmanfilterforindoorlocalization[J].Sensors,2015,15(1):715-732.

[15]張明華,張申生,曹健.基于無線局域網(wǎng)定位的誤差關(guān)鍵因素分析與仿真[J].系統(tǒng)仿真學(xué)報(bào),2009,21(15):4866-4869.

(編輯:丁紅藝)

Indoor Positioning Method Based on Kernel Function and Kalman Filtering

ZHANG Xu1,ZHANG Yu1,2,ZHENG Zhengqi1,3,CHEN Wen3

(1.SchoolofInformationScienceTechnology,EastChinaNormalUniversity,Shanghai200241,China;2.ShanghaiInstituteofMeasurementandTestingTechnology,Shanghai200120,China;3.EngineeringCenterofSHMECforSpaceInformationandGNSS,Shanghai200241,China)

Abstract：Against the problems that indoor positioning suffers from low accuracy and poor stability,an indoor positioning method based on kernel function and Kalman filtering was presented.The Gaussian kernel function was adopted for initial positioning,which can measure the nonlinear similarity between reference points’ fingerprint and test points’ RSS(received signal strength),so it will get better accuracy and stability than the K nearest neighbor algorithm.Then the Kalman filtering was used for filtering the positioning results.The experimental results show that in the real WLAN(wireless local area networks)environment,the RMSE(root mean square error)of kernel function positioning results processed by Kalman filtering is decreased by 25%,the positioning accuracy within 2 meters is increased from 75% to 90%,and the positioning stability is increased by 29%.

Keywords：indoor positioning; positioning accuracy; Gaussian kernel; Kalman filtering

文章編號：1007-6735(2016)03-0287-06

DOI：10.13255/j.cnki.jusst.2016.03.013

收稿日期：2015-11-20

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61372086,41201380);上海市科委科技創(chuàng)新計(jì)劃項(xiàng)目(13511500300);國家質(zhì)檢總局科技計(jì)劃項(xiàng)目(2014QK140)

通信作者：張?jiān)?1978-),男,博士后.研究方向:室內(nèi)定位.E-mail:zhangyu95900@163.com

中圖分類號：TP 393

文獻(xiàn)標(biāo)志碼：A

第一作者： 張旭(1991-),男,碩士研究生.研究方向:室內(nèi)定位.E-mail:zhangxuhs@163.com