馬爾可夫蒙特卡羅的室內(nèi)定位算法

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

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

?

馬爾可夫蒙特卡羅的室內(nèi)定位算法

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

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

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

關(guān)鍵詞:無線局域網(wǎng)室內(nèi)定位;似然函數(shù)模型;蒙特卡羅;克拉美羅界

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

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

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

1 MCMC定位算法

1.1 定位模型

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

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

假設(shè)定位區(qū)域內(nèi)有N個AP,目標(biāo)點與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ā)射源應(yīng)用802.11協(xié)議的不疊加性,各AP到接收點的信號相互獨立,所以,得到似然函數(shù)為

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

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

1.2 定位算法的實現(xiàn)方法

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

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

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

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

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

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

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

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

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

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

1.3 克拉美羅界的推導(dǎo)

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

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

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

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

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

2 算法性能分析

2.1 仿真實驗

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

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

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

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

圖1 位置坐標(biāo)估計的精度比較　

圖2 CRLB的全局分布

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

2.2 復(fù)雜度分析

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

表1 復(fù)雜度對比

3 結(jié)束語

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

參考文獻:

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

[2]蘇軍峰.室內(nèi)無線定位參數(shù)估計算法研究[D].北京:北京交通大學(xué),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]王賽偉,徐玉濱,鄧志安,等.基于概率分布的室內(nèi)定位算法研究[J].計算機科學(xué),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]徐鳳燕,單杭冠,王宗欣.一種帶參數(shù)估計的基于接收信號強度的室內(nèi)定位算法[J].微波學(xué)報,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的室內(nèi)無線定位算法研究[D].武漢:華中科技大學(xué),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].西安電子科技大學(xué)學(xué)報,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日,我校軟件學(xué)院與中航工業(yè)第六三一研究所“天脈聯(lián)合實驗室”成立暨揭牌儀式在我校軟件學(xué)院舉行.雙方將努力探索教學(xué)實踐平臺合作建設(shè)的途徑,打造好天脈聯(lián)合實驗室,在平臺基礎(chǔ)上開展更多深層次合作.

摘自《西電科大報》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-),男,解放軍信息工程大學(xué)碩士研究生,E-mail:wangyue302@126.com.

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

收稿日期:2014-12-25 網(wǎng)絡(luò)出版時間:2015-05-21

doi:10.3969/j.issn.1001-2400.2016.02.025

中圖分類號:TN911.72

文獻標(biāo)識碼:A

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

網(wǎng)絡(luò)出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20150521.0902.022.html