殷守林, 劉天華, 李 航

(沈陽師范大學(xué) 科信軟件學(xué)院, 沈陽 110034)

?

基于模擬退火算法的卡爾曼濾波在室內(nèi)定位中的應(yīng)用研究

殷守林, 劉天華, 李 航

(沈陽師范大學(xué) 科信軟件學(xué)院, 沈陽 110034)

卡爾曼濾波算法是用來解決定位中濾波的問題的一個(gè)重要內(nèi)容,但由于預(yù)測和測量值之間的誤差比較大,算法并沒有達(dá)到最優(yōu),因?yàn)樵谑覂?nèi)定位中溫濕度(高斯白噪聲)對其有影響,以及非平面中的位置信息影響人員物品的位置定位精確度。針對卡爾曼濾波算法的這一問題,引進(jìn)模擬退火算法。結(jié)合模擬退火算法的降溫思想,采用迭代選取最優(yōu)解,以此為基礎(chǔ),得到的最優(yōu)解用于卡爾曼的初始值;將得到的最優(yōu)距離作為對象,并以此建立鄰域,最后再用線性插值法得到坐標(biāo)。仿真實(shí)驗(yàn)表明,此種方法有效提高了室內(nèi)定位精確度,減小降低了各種因素的干擾。

模擬退火算法; 卡爾曼濾波算法; 室內(nèi)定位; 線性插值

0 引 言

定位實(shí)現(xiàn)過程中必須考慮的重要因素就是噪聲干擾。針對室內(nèi)定位中提出的一些濾波算法具有代表性的就是Rudolf Emil Kalman在他的博士論文中提出的卡爾曼濾波算法[1],把含噪聲的數(shù)據(jù)進(jìn)行處理之后得出相對真值,卡爾曼算法是以均方差為估計(jì)采用遞推估計(jì)理論的算法,由測量值來更正系統(tǒng)狀態(tài)向量,以“預(yù)測-實(shí)測-修正”的順序遞推。根據(jù)測量值來消除隨機(jī)干擾,出現(xiàn)新的系統(tǒng)狀態(tài)。關(guān)于定位的研究也有很多文章[6],但大部分以空間模型為基礎(chǔ)。而卡爾曼濾波采用信號與噪聲的狀態(tài)空間模型,它利用前一時(shí)刻的估計(jì)值和現(xiàn)在時(shí)刻的觀測值來更新對狀態(tài)變量的估計(jì),求出現(xiàn)時(shí)刻的估計(jì)值?？柭鼮V波有效的解決了在定位過程中出現(xiàn)的噪聲影響,大大提高了定位的精確度[2-6]。但是卡爾曼濾波算法的初始值選取比較困難,因此又出現(xiàn)了一些改進(jìn)的卡爾曼濾波[7-13],然而大部分都是在過程中進(jìn)行優(yōu)化。

模擬退火算法最早是由N.Metropolis等人于1953年提出的,是基于Monte-Carlo迭代求解策略的一種隨機(jī)尋優(yōu)的算法。模擬退火算法的基本思想是從某一較高對出事溫度出發(fā),伴隨著溫度參數(shù)的不斷下降,結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解,即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。模擬退火算法是一種通用的優(yōu)化算法[14-15],理論上算法具有概率的全局優(yōu)化性能。因此卡爾曼濾波需要一個(gè)優(yōu)質(zhì)的初始解,那么模擬退火算法得到的最優(yōu)解可以作為卡爾曼濾波的初始解。這種思想鮮有人提出,因此本文提出在室內(nèi)定位中的卡爾曼濾波,該濾波算法引進(jìn)模擬退火算法思想,避免高斯白噪聲影響數(shù)據(jù)采集的誤差偏大。由于在室內(nèi)無線網(wǎng)絡(luò)讀取的信號強(qiáng)度樣本比較小,目標(biāo)移動曲線受到客觀因素影響導(dǎo)致不平緩,使系統(tǒng)的穩(wěn)定性和準(zhǔn)確性受到嚴(yán)重影響。針對這一出現(xiàn)的問題,在深入理解基于卡爾曼濾波的室內(nèi)無線定位原理的基礎(chǔ)上,本文引入一種模擬退火卡爾曼濾波算法來對估算出的目標(biāo)位置信息進(jìn)行濾波處理,再通過線性插值法進(jìn)行誤差補(bǔ)償,最后通過仿真驗(yàn)證了該方法確定可行并提高了定位的精度。

1 基于模擬退火的卡爾曼濾波算法

在室內(nèi)定位中使用卡爾曼濾波進(jìn)行濾波處理,并提高定位精度,同時(shí)引進(jìn)模擬退火算法尋找優(yōu)化的初始解,跳出局部最優(yōu)解而搜索到全局最優(yōu)解。模擬退火算法的具體實(shí)施步驟如下:

第1步 數(shù)據(jù)初始化,初始溫度T(充分大),初始狀態(tài)S(算法迭代起點(diǎn)),每個(gè)T值的迭代次數(shù)L。

第2步 對K=1,2,3,…,L做第3步至第6步。

第3步 產(chǎn)生新解S′。

第6步 如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解,結(jié)束程序。終止條件通常取為連續(xù)若干個(gè)新解都沒有被接受時(shí)終止算法。

第7步T逐漸減少,且T→0,然后轉(zhuǎn)第2步。

模擬退火算法的基本思想分為3個(gè)部分:解空間、目標(biāo)函數(shù)、初始解部分。模擬退火算法由一個(gè)目標(biāo)函數(shù)產(chǎn)生一個(gè)位于空間的新解,計(jì)算新解與初始解的目標(biāo)函數(shù)差,使用接受準(zhǔn)則判斷新解是否符合當(dāng)前條件,進(jìn)行迭代運(yùn)算。最大的優(yōu)點(diǎn)就是與初始值無關(guān)?？柭鼮V波就是用來求得估計(jì)值的最佳解,通過引進(jìn)模擬退火算法,二者有效結(jié)合,能最終達(dá)到進(jìn)一步提高定位的精確度。

1.1 信號強(qiáng)度的初始化

信號強(qiáng)度的采樣:設(shè)Eij表示第i個(gè)采樣點(diǎn)接收到第j個(gè)AP的信號強(qiáng)度的平均值,在各個(gè)采樣點(diǎn)處測量。實(shí)時(shí)定位設(shè)Gj表示接收到來自第j個(gè)AP信號強(qiáng)度的平均值,具體的定位計(jì)算公式由明考斯基距離公式得:

當(dāng)q=1,dij表示曼哈頓距離。

當(dāng)q=2,dij表示歐式距離。由實(shí)驗(yàn)結(jié)果表明,當(dāng)q=2時(shí),系統(tǒng)的定位精度比較高。得到:

1.2 模擬退火算法的室內(nèi)定位流程圖

從圖1中可以得出,首先要確定一個(gè)初始信號強(qiáng)度,根據(jù)歐氏距離公式進(jìn)行計(jì)算,得到di的值,同時(shí)可以看出在精確未知點(diǎn)位置的時(shí)候,是以信號強(qiáng)度來定的,而信號強(qiáng)度的精確度是以具體的公式計(jì)算

圖1 模擬退火算法流程圖

得到。

1.3 濾波函數(shù)的設(shè)置

信號強(qiáng)度接收器接收的信號強(qiáng)度,可以直接測量出來。經(jīng)過多次測量,可以得到一個(gè)估計(jì)的強(qiáng)度,假如預(yù)測第k-1次的信號強(qiáng)度是RSSIk-1,那么在k時(shí)刻信號強(qiáng)度與k-1時(shí)刻的預(yù)測值相等,即RSSIk=RSSIk-1,同時(shí)該值的高斯白噪聲為ε0:

其中:RSSIMoptimal表示k-1時(shí)刻的最優(yōu)信號值偏差;RSSIforcast表示k時(shí)刻自己對信號強(qiáng)度的預(yù)測不確定值偏差。通過測量儀得到k時(shí)刻信號強(qiáng)度是RSSImeasure,同時(shí)該值的偏差是ε1:

其中:RSSIMoptimal表示測量值的最優(yōu)信號強(qiáng)度偏差;RSSIMforcast表示測量的不確定值偏差。

由此,得到均方誤差Herror,其表達(dá)式為:

因此估算出K時(shí)刻最優(yōu)信號強(qiáng)度RSSIKoptimal值為:

RSSIKoptimal=RSSIk-1+Herror×(RSSImeasure-RSSIk-1)

從而,卡爾曼濾波不斷地把均方誤差遞歸,能夠得到最優(yōu)的信號強(qiáng)度值,運(yùn)行速度快,且只保留上一時(shí)刻的方差。

1.4 模擬退火算法思想的具體實(shí)施

1.5 線性插值法

線性插值是數(shù)學(xué)、計(jì)算機(jī)圖形學(xué)等領(lǐng)域廣泛使用的一種簡單插值方法[16],如圖2所示。假設(shè)已知坐標(biāo)(x1,y1)和(x2,y2),要得到[x1,y2]區(qū)間內(nèi)某一位置x在直線上的y值。

圖2 線性插值法

2 仿真及結(jié)果分析

在MATLAB仿真平臺下進(jìn)行的仿真驗(yàn)證,通過在信號發(fā)射點(diǎn)半徑不變的圓上,布置不同的點(diǎn),測量接收到的信號強(qiáng)度計(jì)算出的距離值的誤差大小來判斷哪個(gè)方法更優(yōu),將未加入模擬退火的卡爾曼作為對比對象,2個(gè)算法仿真是在相同的參量,同一背景環(huán)境下進(jìn)行,仿真結(jié)果如圖3、圖4所示。

由圖3可以看出在10～100 s,卡爾曼濾波算法比其上下波動大,模擬退火卡爾曼優(yōu)勢很明顯,定位比其更加準(zhǔn)確。經(jīng)計(jì)算100 s之后,曲線也逐漸收斂,曲線走勢趨于平穩(wěn),濾波達(dá)到一種穩(wěn)定狀態(tài)。圖4表明這種算法的結(jié)合誤差變化會越來越穩(wěn)定,上下波動會越來越小,有效提高定位精確度。

圖3 卡爾曼與模擬退火卡爾曼的定位比較

圖4 模擬退火卡爾曼的誤差變化

從圖3和圖4可以看出模擬退火卡爾曼的整體高效性。經(jīng)過分析比較可以得到如下結(jié)論:

1) 使用模擬退火卡爾曼濾波算法,隨著時(shí)間的增加,該算法越來越收斂,誤差波動越來越小。

2) 在室內(nèi)定位中,單純的卡爾曼濾波可以完成此項(xiàng)工作,但是誤差較大,結(jié)合模擬退火算法之后,很明顯誤差波動范圍小,使定位趨于精確化。

3) 在室內(nèi)定位初值選取時(shí)候,各個(gè)點(diǎn)的坐標(biāo)初始位置直接精確化,對于后期目標(biāo)運(yùn)動軌跡位置確定有很大幫助,大大提高精確度。

3 結(jié) 論

本文提出的策略是模擬退火算法和卡爾曼濾波算法有效結(jié)合,在卡爾曼算法的基礎(chǔ)上引入模擬退火算法求解初始解,增加初始值的準(zhǔn)確性,降低了噪聲干擾,有效的解決了在定位系統(tǒng)中定位精確度受其他客觀因素影響地問題,仿真實(shí)驗(yàn)結(jié)果表明,該策略能夠能夠在室內(nèi)定位中更有效的提高精確度。部分實(shí)驗(yàn)數(shù)據(jù)具體見表1。

表1 實(shí)驗(yàn)數(shù)據(jù)測量值

注:k為時(shí)間段;p為隨時(shí)間變化模擬退火卡爾曼濾波位置誤差;m為隨時(shí)間變化卡爾曼算法的誤差;n為隨時(shí)間變化模擬退火卡爾曼濾波誤差。

在本文中選取50個(gè)點(diǎn),進(jìn)行了50次實(shí)驗(yàn)。采樣周期T=20 s,通過卡爾曼濾波方程以及新方法計(jì)算求得p、m、n。

[1]KALMAN R E.A new approach to linear filtering and prediction problems[J].J Fluids Eng, 1960,82(1):35-45.

[2]曹春萍,羅玲莉.基于卡爾曼濾波算法的室內(nèi)無線定位系統(tǒng)[J].計(jì)算機(jī)系統(tǒng)應(yīng)用, 2011(11):76-79.

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

[4]付夢印,鄧志宏,閆莉萍.Kalman濾波理論及其在導(dǎo)航系統(tǒng)中的應(yīng)用[M].北京:科學(xué)出版社, 2010.

[5]顧宗海.基于RSSI測距的室內(nèi)定位算法研究[D].鄭州:鄭州大學(xué), 2011.

[6]陳豫章.基于RSSI的室內(nèi)三維定位技術(shù)研究與實(shí)現(xiàn)[D].昆明:云南大學(xué), 2013.

[7]張明華,張申生,曹健.無線局域網(wǎng)中基于信號強(qiáng)度的室內(nèi)定位[J].計(jì)算機(jī)科學(xué), 2007(6):68-75.

[8]ZHANG D F, JIANG X P, HU Z C, et al.Rolling and annealing texture of 3004 aluminium alloy[C]∥Materials science forum, 2002,408:1477-1482.

[9]SHIEH L S, WAI W B, YATES R E.Approximate Kalman filters[C]∥Joint Automatic Control Conference, San Francisco, CA, 1980.

[10]CHUI C K, CHEN G.Kalman filtering[J].With real time applications, 1999.

[11]BISHOP G, WELCH G.An introduction to the kalman filter[J].Proc of SIGGRAPH, Course, 2001,8(27599-23175):41.

[12]CHRISTOFFERSEN P, DORION C, JACOBS K.Nonlinear Kalman filtering in affine term structure models[J].Management Science, 2012:2012-2014.

[13]SARKKA S, HARTIKAINEN J.Non-linear noise adaptive Kalman filtering via variational Bayes[C]∥Machine Learning for Signal Processing (MLSP), 2013 IEEE International Workshop on.IEEE, 2013:1-6.

[14]HAMZEEI M, FARAHANI R Z, RASHIDI-BEJGAN H.An exact and a simulated annealing algorithm for simultaneously determining flow path and the location of P/D stations in bidirectional path[J].J M anufsyst, 2013,32(4):648-654.

[15]INGBER L.Simulated annealing: Practice versus theory[J].Math Comput Mode, 1993,18(11):29-57.

[16]李培明,梅勝全,馬青坡.一種改進(jìn)的雙線性插值射線追蹤方法[J].石油地球物理勘探, 2013(4):553-558.

[17]BROWN A, RUSCHMANN M, DUFFY B .Simulated Annealing Maneuver Planner for Cluster Flight[C]∥24 th International Symposium on Space Flight Dynamics, Laurel, 2014.

[18]趙煌,彭勇.雙線性插值算法的優(yōu)化及其應(yīng)用[J].電視技術(shù), 2012,36(17):30-32.

Application of Kalman filtering in indoor location based on simulated annealing algorithm

YINShoulin,LIUTianhua,LIHang

(Software College, Shenyang Normal University, Shenyang 110034, China)

Kalman filtering algorithm is used to solve the problem of the positioning filter, however the error is relatively large between the measured value and predicted value.The algorithm does not reach the optimal solution because there exists temperature and humidity (we can call it Gaussian white noise) as well as the location information of non-planar affects positioning accuracy of human’s site in the indoor location.We introduce the simulated annealing algorithm to the significant difference of Kalman filtering algorithm.We combine the cooling of simulated annealing algorithm and use the iterative to select the optimum solution.On this basis, we can get the optimal solution for initial value of the Kalman.Getting the optimal as an object and we set up neighborhood based on the object.At the end we can get coordinate by linear interpolation method.Simulation experiments show that this method can improve effectively the positioning accuracy and reduce the interference of various kinds of factors.

simulated annealing algorithm; Kalman filtering algorithm; indoor localization; linear interpolation

2014-10-06。

國家自然科學(xué)基金資助項(xiàng)目(60970112)。

殷守林(1990-),男,河南濮陽人,沈陽師范大學(xué)碩士研究生; 劉天華(1966-),男,遼寧沈陽人,沈陽師范大學(xué)教授,博士,碩士研究生導(dǎo)師。

1673-5862(2015)01-0086-05

TP391.9

A

10.3969/ j.issn.1673-5862.2015.01.019