殷守林, 劉天華, 李 航

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

?

基于模擬退火算法的卡爾曼濾波在室內定位中的應用研究

殷守林, 劉天華, 李 航

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

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

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

0 引 言

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

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

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

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

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

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

第3步 產生新解S′。

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

第7步T逐漸減少,且T→0,然后轉第2步。

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

1.1 信號強度的初始化

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

當q=1,dij表示曼哈頓距離。

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

1.2 模擬退火算法的室內定位流程圖

從圖1中可以得出,首先要確定一個初始信號強度,根據歐氏距離公式進行計算,得到di的值,同時可以看出在精確未知點位置的時候,是以信號強度來定的,而信號強度的精確度是以具體的公式計算

圖1 模擬退火算法流程圖

得到。

1.3 濾波函數的設置

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

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

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

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

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

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

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

1.4 模擬退火算法思想的具體實施

1.5 線性插值法

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

圖2 線性插值法

2 仿真及結果分析

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

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

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

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

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

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

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

3) 在室內定位初值選取時候,各個點的坐標初始位置直接精確化,對于后期目標運動軌跡位置確定有很大幫助,大大提高精確度。

3 結 論

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

表1 實驗數據測量值

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

在本文中選取50個點,進行了50次實驗。采樣周期T=20 s,通過卡爾曼濾波方程以及新方法計算求得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]曹春萍,羅玲莉.基于卡爾曼濾波算法的室內無線定位系統(tǒng)[J].計算機系統(tǒng)應用, 2011(11):76-79.

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

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

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

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

[7]張明華,張申生,曹健.無線局域網中基于信號強度的室內定位[J].計算機科學, 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].石油地球物理勘探, 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)化及其應用[J].電視技術, 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。

國家自然科學基金資助項目(60970112)。

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

1673-5862(2015)01-0086-05

TP391.9

A

10.3969/ j.issn.1673-5862.2015.01.019