馬爾可夫蒙特卡羅的室內定位算法

王 躍,巴 斌,崔維嘉,逯志宇

(解放軍信息工程大學信息系統(tǒng)工程學院,河南鄭州 450002)

?

馬爾可夫蒙特卡羅的室內定位算法

王 躍,巴 斌,崔維嘉,逯志宇

(解放軍信息工程大學信息系統(tǒng)工程學院,河南鄭州 450002)

摘要:針對無線局域網室內定位中接收功率受干擾影響導致位置估計精度偏低的問題,構建基于傳播損耗模型的似然函數模型,采用馬爾可夫蒙特卡羅抽樣方法進行位置估計.該方法將干擾因素構建到模型中,運用隨機抽樣的方法解決估計問題,具有收斂速度快、估計精度高的優(yōu)勢.理論推導了該模型下坐標估計的克拉美羅界,并在仿真實驗中,給出克拉美羅界在定位空間的分布.仿真實驗表明,馬爾可夫蒙特卡羅抽樣方法可精確估計出目標位置,在相同仿真條件下,與共軛梯度法相比,馬爾可夫蒙特卡羅抽樣方法估計精度高、復雜度低.

關鍵詞:無線局域網室內定位;似然函數模型;蒙特卡羅;克拉美羅界

目前,位置服務已成為日常生活工作必不可少的基礎服務.隨著地鐵機場等公共設施的大量建設,人們在公共安全,應急救援等方面對室內定位的需求不斷提高,室內定位成為近年來的研究熱點[1-2].由于室內的多徑條件較為復雜,基于時間特征信息的測量方法難以分辨用戶,并且需要專用的測量設備,因此系統(tǒng)復雜度和構建成本較高[3].基于無線局域網(Wireless Local Area Network,WLAN)的室內定位技術由于采用了802.11協議的標準硬件,因此以成本低、覆蓋廣和系統(tǒng)布設簡單等優(yōu)勢成為室內定位的首選技術[4].

室內定位技術的主要方法分為兩類:確定性方法和概率性方法.確定性方法中的經典算法有最近鄰法(Nearest Neighbor,NN)、K近鄰法(K Nearest Neighbor,KNN)和加權的K近鄰法(Weighted K Nearest Neighbor,WKNN),這類算法在設計中只考慮了信號特征均值,沒有考慮方差以及環(huán)境因素的影響,因而定位的誤差較大.與確定性算法相比,概率性算法基于數理統(tǒng)計的思想,能更好地解決由環(huán)境影響所帶來的特征信息的不確定性問題.概率性方法主要分為兩類:通過大量的測量數據,計算最大后驗概率位置點,典型方法有直方圖[5]和核函數法[6];建立似然函數的模型,通過相關算法進行位置估計,目前通常采用共軛梯度法(Fletcher Reeves,FR)進行位置估計[7-8].

基于共軛梯度法的位置估計算法的全局收斂性與初始值的設置密切相關,且其定位精度和算法收斂性又受到搜索步長的影響,因而算法性能受初始值設置和搜索步長選擇的限制.為此,筆者提出一種基于馬爾可夫蒙特卡羅進行似然估計的算法,該算法利用傳播損耗模型推導似然函數模型,采用馬爾科夫鏈蒙特卡羅(Markov Chain Monte-Carlo,MCMC)方法對似然函數進行抽樣,取樣本均值作為定位坐標的估計值,算法性能不受初始值選取與搜索步長的影響.仿真結果表明,該算法性能優(yōu)于共軛梯度法.

1 MCMC定位算法

1.1 定位模型

在室內定位環(huán)境下,由于地板、天花板、墻壁等遮擋物產生的反射、繞射,使接收信號功率(Received Signal Power,RSP)不僅與傳播距離d有關,而且與室內的各種干擾有關;又因為在傳播損耗模型中的遮蔽因子是隨機變量,可將其考慮為室內環(huán)境的噪聲干擾,所以,利用傳播損耗模型中的遮蔽因子來刻畫室內定位環(huán)境下的干擾因素,并構建似然函數模型.具體的接收功率特性如下:

其中,Pr(d)為距信號發(fā)射源接入點(Access Point,AP)的距離為d時接收到的功率;Pr(d0)為參考功率,一般取距AP為1 m時的接收功率;η為路徑損耗指數即信道衰減系數;v是遮蔽因子,服從均值為0、方差為δ2的正態(tài)分布.v的概率密度函數為

假設定位區(qū)域內有N個AP,目標點與AP的距離D=[d1,d2,…,dn],接收功率Pr=[pr1,pr2,…,pr n],令 pr(di)-pr(d0)=pi,得到P=[p1,p2,…,pn].將式(1)變換為v=Pr(d)-Pr(d0)+10ηlg(dd0),得到v=P+10ηlg(dd0),將其代入式(2),又由于發(fā)射源應用802.11協議的不疊加性,各AP到接收點的信號相互獨立,所以,得到似然函數為

假設目標定位點的坐標為(x,y),各個AP的坐標為{(x1,y1),(x2,y2),…,(xn,yn) } ,得到目標點到各個AP的距離為

將式(4)代入式(3),得到目標點(x,y)的似然函數為

1.2 定位算法的實現方法

蒙特卡羅算法是一種以概率統(tǒng)計為指導,利用統(tǒng)計隨機抽樣的方法近似求解問題.文中定位算法的設計正是利用MCMC的算法思想[9-10],并將其引入到室內定位的最大似然估計中,從而估計出目標的位置坐標.

首先,確定平穩(wěn)分布函數π(x,y),對式(5)進行化簡并取對數,得到似然函數為

為使似然函數的全局最大值更加精確,取似然函數L(x,y)的指數值[11],得到平穩(wěn)分布函數為

其中,參數ρ是常數.在一定范圍內,ρ取值越大,平穩(wěn)分布函數在估計位置越尖銳,當分布函數在估計位置更加銳利時,估計值更加精確.

然后,選取馬爾可夫鏈的轉移核函數,文中選取Metropolis-Hastings(M-H)算法作為MCMC構造核函數的方法,其核心思想是,選擇提議函數q(·),并在提議函數中任意抽取一點作為初始樣本x0,在抽取次數i≥1的條件下,從提議函數中抽取備選樣本x*,并計算接受概率,即

最后,以接收概率和隨機變量u進行判斷是否接受當前狀態(tài).u服從均勻分布U(0,1),當u≤a(x,x*) 時,接受當前狀態(tài),即xi=x*;否則,xi=xi-1,并重新抽取x*進行計算.

(1)選取提議函數q(·),其作用是在搜索區(qū)間中對x和y進行隨機抽樣,文中采用獨立馬爾可夫抽樣方法,使提議函數q(·)服從均勻分布U[0,max(·)],即q(·)～U[0,max(·)].

(2)利用提議函數分別抽取樣本初始化參數x0和y0,并代入式(8),得到π(x0,y0).

(3)利用提議函數抽取候選樣本x*和y*,并代入式(8),得到π(x*,y*),將π(x*,y*)與π(xi-1,yi-1)代入式(9),計算接受概率函數(a (x,y),(x*,y*)).

(4)產生隨機數u服從均勻分布U[0,1].判斷是否接受樣本,當u≤(a (x,y),(x*,y*))時,接受當前樣本,得到xi=x*yi=y*;否則,保持原狀態(tài)xi=xi-1,yi=yi-1,并跳轉到步驟(3)繼續(xù)判斷.

1.3 克拉美羅界的推導

根據式(5)給出的似然函數,求得

當前，高校英語數字化教學資源建設缺乏統(tǒng)一的技術標準和課程標準。高校之間缺乏交流與溝通，英語數字化教學資源建設缺乏統(tǒng)一的技術標準，統(tǒng)一的資源分類規(guī)則和相應的文件格式，這樣不利于不同平臺間數據的查找和利用。此外，高校開發(fā)的英語數字化教學資源大多數都是自主開發(fā)，與企業(yè)、行業(yè)的聯動不多，校、企、行共同開發(fā)的英語數字化教學資源較少。已開發(fā)的英語數字化教學資源中，由于缺乏對企業(yè)、行業(yè)的實際需求調查，沒有基于統(tǒng)一的行業(yè)標準，造成數字化教學資源存在類型單一,低水平重復建設,與教學的耦合度低等現象。

根據式(1)得到v=pi+10ηlg(dd0),因為v服從均值為0、方差為δ2的正態(tài)分布.得到Fisher函數為

因為似然函數中估計參數x與y對稱,所以得到

并得到下坐標估計的克拉美羅界(Cramer-Rao Lower Bound,CRLB)為

2 算法性能分析

2.1 仿真實驗

為驗證文中提出的室內定位算法的性能,實驗構建了一個室內模擬環(huán)境,并基于該環(huán)境采用MCMC算法對室內目標位置進行估計,以CLRB作為性能評價標準與共軛梯度方法進行對比分析,同時為驗證估計值均方誤差與空間內位置的關系,給出了在整個空間的估計坐標的CLRB分布.

模擬環(huán)境設置如下:實驗在40 m×40 m的空間內進行,坐標(0,0),(0,39),(39,0),(39,39)處各放置一個AP,設置距AP1 m處的功率為-18 dBm.設置平穩(wěn)分布函數中的參數ρ=5,設置路徑損耗指數η=5,并且取定位目標坐標為(4,5).

在分析估計精度的實驗中,取遮蔽因子的方差δ2的值為1到10,為使實驗更具有真實性,對每個δ2的值取隨機變量v的100個隨機值,進行100次獨立統(tǒng)計實驗,計算出估計方差.設定FR算法的搜索初始值坐標為(1,1),搜索步長為0.01,為設置相同的對比條件,取每次FR的迭代次數作為MCMC的抽樣次數.

圖1給出了在不同方差δ2條件下,MCMC算法與FR算法估計結果的均方誤差,同時給出了該模型的CRLB.因為FR算法設置的搜索步長決定定位精度和迭代次數,為使對比結果更加精確,設置MCMC算法的抽樣次數與FR算法的迭代次數相同.通過對結果分析得到,利用MCMC算法進行位置估計的均方誤差始終小于FR算法的.當遮蔽因子方差δ2較大時,兩種算法的均方誤差相差較小.隨著δ2的減小,MCMC算法估計的均方誤差逼近CRLB,并且始終優(yōu)于FR算法的.這是因為MCMC算法采用隨機抽樣的方式,估計值可無限逼近真實值.對于FR算法,因為受到能否收斂和復雜度等條件的限制,搜索步長不能設置無限小,所以估計精度受到影響.圖1顯示兩種算法的均方誤差都隨著遮蔽因子方差的增大而增加,這是因為在該模型下,接收功率的變化受測量點到AP的距離和遮蔽因子方差的影響,當方差增大時,接收功率的干擾增加,從而最大似然函數模型中的干擾因素也隨之增加,所以計算目標點的位置的均方誤差變大.

圖1 位置坐標估計的精度比較　

圖2 CRLB的全局分布

圖2表示δ2=3的全局CRLB,顯示出了均方誤差大小隨空間中位置的變化趨勢.從圖2可以看出,在空間邊緣上的誤差高于空間中心位置的誤差,且距離AP越近,估計精度越高.在中心位置估計誤差隨著各個AP位置向空間中心方向增大,各個空間邊緣誤差隨著空間中心方向不斷減小.

2.2 復雜度分析

復雜度對比是在計算次數N相同的條件下,對兩種算法運算中的乘法、加法、對數運算、指數運算以及求導和解方程的運算次數進行對比.運算中的對比運算設為加法運算,除法運算設為乘法運算.算法的復雜度對比如表1所示,MCMC算法的加法、乘法、求導和解方程的計算次數都小于FR算法的.但MCMC算法比FR算法多出N次指數運算,通過表格無法明顯對比.所以文中將兩種算法的對數運算和指數運算通過泰勒級數展開,轉換為加法與乘法運算進行對比.如表1所示,FR算法迭代1次進行4次對數運算,轉換后包含2n2+2n次乘法和4n次加法.MCMC算法抽樣1次包含1次指數運算和1次對數運算,轉換后對數與指數運算共包含(3n2+3n)2次乘法和2n次加法.綜上所述,在計算次數N相同的條件下,MCMC算法的復雜度低于FR算法的.

表1 復雜度對比

3 結束語

通過對室內環(huán)境的分析,利用傳播損耗模型建立了似然函數模型,運用馬爾可夫蒙特卡羅算法對似然函數中的位置坐標進行估計,通過隨機抽樣的方法代替了復雜的求導計算過程,避免了FR算法初始值設置導致局部收斂并影響定位精度的問題.并且推導了該模型下的克拉美羅界并進行了復雜度分析.通過仿真實驗給出了模擬定位環(huán)境中CRLB的分布,同時仿真結果的均方誤差逼近克拉美羅界,與FR算法相比性能有較大提升.

參考文獻:

[1]WANG K.Location-based Services Deployment and Demand:a Roadmap Model[J].Electronic Commerce Research,2011,11 (1):5-29.

[2]蘇軍峰.室內無線定位參數估計算法研究[D].北京:北京交通大學,2013.

[3]WANG T.Novel Sensor Location Scheme Using Time-of-arrival Estimates[J].IET Signal Processing,2012,6(1):8-13.

[4]PARK K H.A Cooperative Clustering Protocol for Energy Saving of Mobile Devices with WLAN and Bluetooth Interfaces[J].IEEE Transactions on Mobile Computing,2011,10(4):491-504.

[5]王賽偉,徐玉濱,鄧志安,等.基于概率分布的室內定位算法研究[J].計算機科學,2009,36(4A):45-47.WANG Saiwei,XU Yubin,DENG Zhian,et al.An Indoor Positioning Algorithm Research Based on Probability Distribution[J].Computer Science,2009,36(4A):45-47.

[6]FANG S H,LIN T.Principal Component Localizationin Indoor WLAN Environments[J].IEEE Transactions on Mobile Computing,2012,11(1):100-110.

[7]徐鳳燕,單杭冠,王宗欣.一種帶參數估計的基于接收信號強度的室內定位算法[J].微波學報,2008(2):67-72.XU Fengyan,SHAN Hangguan,WANG Zongxin.An Indoor Location Algorithm Based on Received Signal Strength with Parameter Estimation[J].Journal of Microwaves,2008(2):67-72.

[8]余俊.基于RSSI的室內無線定位算法研究[D].武漢:華中科技大學,2013.

[9]NG W,REILLY J P,KIRUBARAJAN T,et al.Wideband Array Signal Processing Using MCMC Methods[J].IEEE Transactions on Signal Processig,2005,53(2):411-426.

[10]羅亮,馮象初,霍雷剛,等.非局部MCMC采樣和低秩逼近的圖像去噪算法[J].西安電子科技大學學報,2013,40 (6):140-146.LUO Liang,FENG Xiangchu,HUO Leigang,et al.Image Denoising Method Based on Non-local Markov-chain Monte Carlo Sampling and Low Rank Approximation[J].Journal of Xidian University,2013,40(6):140-146.

[11]MASMOUDI A,BELLILI F,AFFES S,et al.A Maximum Likelihood Time Delay Estimator in a Multipath Environment Using Importance Sampling[J].IEEE Transactions on Signal Processing,2013,61(1):182-193.

(編輯:齊淑娟)

簡 訊

2015年11月7日,我校軟件學院與中航工業(yè)第六三一研究所“天脈聯合實驗室”成立暨揭牌儀式在我校軟件學院舉行.雙方將努力探索教學實踐平臺合作建設的途徑,打造好天脈聯合實驗室,在平臺基礎上開展更多深層次合作.

摘自《西電科大報》2015.11.14

Indoor positioning algorithm based on Markov Monte Carlo

WANG Yue,BA Bin,CUI Weijia,LU Zhiyu
(Information System Eng.Inst.,PLA Information Engineering Univ.,Zhengzhou 450002,China)

Abstract:The interference in the received power leads to the problem of the low estimation accuracy of WLAN indoor positioning,so a new method is proposed which constructs the maximum likelihood model and uses the Markov Chain Monte-Carlo sampling method to estimate position coordinates.The method considers taking the interference factor into the model,and uses the random sampling method to solve the estimation problem,which has the advantage of fast convergence and high estimate precision.Furthermore,the Cramer-Rao lower bound (CRLB)of the model is derived.In simulation experiment,the distribution of Cramer-Rao Bound in locating space is given.Finally,simulations show that the MCMC method can estimate the target location accurately.Under the same simulation conditions,the MCMC method achieves greater estimated precision and has a lower computational complexity than the Fletcher-Reeves Method(FR).

Key Words:WLAN indoor positioning;likelihood model;Monte-Carlo;Cramer-Rao lower bound

作者簡介:王 躍(1986-),男,解放軍信息工程大學碩士研究生,E-mail:wangyue302@126.com.

基金項目:國家863計劃資助項目(2012AA01A502,2012AA01A505)

收稿日期:2014-12-25 網絡出版時間:2015-05-21

doi:10.3969/j.issn.1001-2400.2016.02.025

中圖分類號:TN911.72

文獻標識碼:A

文章編號:1001-2400(2016)02-0145-05

網絡出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20150521.0902.022.html