马尔可夫蒙特卡罗的室内定位算法

王 跃,巴 斌,崔维嘉,逯志宇

(解放军信息工程大学信息系统工程学院,河南郑州 450002)



马尔可夫蒙特卡罗的室内定位算法

王 跃,巴 斌,崔维嘉,逯志宇

(解放军信息工程大学信息系统工程学院,河南郑州 450002)

摘要:针对无线局域网室内定位中接收功率受干扰影响导致位置估计精度偏低的问题,构建基于传播损耗模型的似然函数模型,采用马尔可夫蒙特卡罗抽样方法进行位置估计.该方法将干扰因素构建到模型中,运用随机抽样的方法解决估计问题,具有收敛速度快、估计精度高的优势.理论推导了该模型下坐标估计的克拉美罗界,并在仿真实验中,给出克拉美罗界在定位空间的分布.仿真实验表明,马尔可夫蒙特卡罗抽样方法可精确估计出目标位置,在相同仿真条件下,与共轭梯度法相比,马尔可夫蒙特卡罗抽样方法估计精度高、复杂度低.

关键词:无线局域网室内定位;似然函数模型;蒙特卡罗;克拉美罗界

目前,位置服务已成为日常生活工作必不可少的基础服务.随着地铁机场等公共设施的大量建设,人们在公共安全,应急救援等方面对室内定位的需求不断提高,室内定位成为近年来的研究热点[1-2].由于室内的多径条件较为复杂,基于时间特征信息的测量方法难以分辨用户,并且需要专用的测量设备,因此系统复杂度和构建成本较高[3].基于无线局域网(Wireless Local Area Network,WLAN)的室内定位技术由于采用了802.11协议的标准硬件,因此以成本低、覆盖广和系统布设简单等优势成为室内定位的首选技术[4].

室内定位技术的主要方法分为两类:确定性方法和概率性方法.确定性方法中的经典算法有最近邻法(Nearest Neighbor,NN)、K近邻法(K Nearest Neighbor,KNN)和加权的K近邻法(Weighted K Nearest Neighbor,WKNN),这类算法在设计中只考虑了信号特征均值,没有考虑方差以及环境因素的影响,因而定位的误差较大.与确定性算法相比,概率性算法基于数理统计的思想,能更好地解决由环境影响所带来的特征信息的不确定性问题.概率性方法主要分为两类:通过大量的测量数据,计算最大后验概率位置点,典型方法有直方图[5]和核函数法[6];建立似然函数的模型,通过相关算法进行位置估计,目前通常采用共轭梯度法(Fletcher Reeves,FR)进行位置估计[7-8].

基于共轭梯度法的位置估计算法的全局收敛性与初始值的设置密切相关,且其定位精度和算法收敛性又受到搜索步长的影响,因而算法性能受初始值设置和搜索步长选择的限制.为此,笔者提出一种基于马尔可夫蒙特卡罗进行似然估计的算法,该算法利用传播损耗模型推导似然函数模型,采用马尔科夫链蒙特卡罗(Markov Chain Monte-Carlo,MCMC)方法对似然函数进行抽样,取样本均值作为定位坐标的估计值,算法性能不受初始值选取与搜索步长的影响.仿真结果表明,该算法性能优于共轭梯度法.

1 MCMC定位算法

1.1 定位模型

在室内定位环境下,由于地板、天花板、墙壁等遮挡物产生的反射、绕射,使接收信号功率(Received Signal Power,RSP)不仅与传播距离d有关,而且与室内的各种干扰有关;又因为在传播损耗模型中的遮蔽因子是随机变量,可将其考虑为室内环境的噪声干扰,所以,利用传播损耗模型中的遮蔽因子来刻画室内定位环境下的干扰因素,并构建似然函数模型.具体的接收功率特性如下:

其中,Pr(d)为距信号发射源接入点(Access Point,AP)的距离为d时接收到的功率;Pr(d0)为参考功率,一般取距AP为1 m时的接收功率;η为路径损耗指数即信道衰减系数;v是遮蔽因子,服从均值为0、方差为δ2的正态分布.v的概率密度函数为

假设定位区域内有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),又由于发射源应用802.11协议的不叠加性,各AP到接收点的信号相互独立,所以,得到似然函数为

假设目标定位点的坐标为(x,y),各个AP的坐标为{(x1,y1),(x2,y2),…,(xn,yn) } ,得到目标点到各个AP的距离为

将式(4)代入式(3),得到目标点(x,y)的似然函数为

1.2 定位算法的实现方法

蒙特卡罗算法是一种以概率统计为指导,利用统计随机抽样的方法近似求解问题.文中定位算法的设计正是利用MCMC的算法思想[9-10],并将其引入到室内定位的最大似然估计中,从而估计出目标的位置坐标.

首先,确定平稳分布函数π(x,y),对式(5)进行化简并取对数,得到似然函数为

为使似然函数的全局最大值更加精确,取似然函数L(x,y)的指数值[11],得到平稳分布函数为

其中,参数ρ是常数.在一定范围内,ρ取值越大,平稳分布函数在估计位置越尖锐,当分布函数在估计位置更加锐利时,估计值更加精确.

然后,选取马尔可夫链的转移核函数,文中选取Metropolis-Hastings(M-H)算法作为MCMC构造核函数的方法,其核心思想是,选择提议函数q(·),并在提议函数中任意抽取一点作为初始样本x0,在抽取次数i≥1的条件下,从提议函数中抽取备选样本x*,并计算接受概率,即

最后,以接收概率和随机变量u进行判断是否接受当前状态.u服从均匀分布U(0,1),当u≤a(x,x*) 时,接受当前状态,即xi=x*;否则,xi=xi-1,并重新抽取x*进行计算.

(1)选取提议函数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*;否则,保持原状态xi=xi-1,yi=yi-1,并跳转到步骤(3)继续判断.

1.3 克拉美罗界的推导

根据式(5)给出的似然函数,求得

当前，高校英语数字化教学资源建设缺乏统一的技术标准和课程标准。高校之间缺乏交流与沟通，英语数字化教学资源建设缺乏统一的技术标准，统一的资源分类规则和相应的文件格式，这样不利于不同平台间数据的查找和利用。此外，高校开发的英语数字化教学资源大多数都是自主开发，与企业、行业的联动不多，校、企、行共同开发的英语数字化教学资源较少。已开发的英语数字化教学资源中，由于缺乏对企业、行业的实际需求调查，没有基于统一的行业标准，造成数字化教学资源存在类型单一,低水平重复建设,与教学的耦合度低等现象。

根据式(1)得到v=pi+10ηlg(dd0),因为v服从均值为0、方差为δ2的正态分布.得到Fisher函数为

因为似然函数中估计参数x与y对称,所以得到

并得到下坐标估计的克拉美罗界(Cramer-Rao Lower Bound,CRLB)为

2 算法性能分析

2.1 仿真实验

为验证文中提出的室内定位算法的性能,实验构建了一个室内模拟环境,并基于该环境采用MCMC算法对室内目标位置进行估计,以CLRB作为性能评价标准与共轭梯度方法进行对比分析,同时为验证估计值均方误差与空间内位置的关系,给出了在整个空间的估计坐标的CLRB分布.

模拟环境设置如下:实验在40 m×40 m的空间内进行,坐标(0,0),(0,39),(39,0),(39,39)处各放置一个AP,设置距AP1 m处的功率为-18 dBm.设置平稳分布函数中的参数ρ=5,设置路径损耗指数η=5,并且取定位目标坐标为(4,5).

在分析估计精度的实验中,取遮蔽因子的方差δ2的值为1到10,为使实验更具有真实性,对每个δ2的值取随机变量v的100个随机值,进行100次独立统计实验,计算出估计方差.设定FR算法的搜索初始值坐标为(1,1),搜索步长为0.01,为设置相同的对比条件,取每次FR的迭代次数作为MCMC的抽样次数.

图1给出了在不同方差δ2条件下,MCMC算法与FR算法估计结果的均方误差,同时给出了该模型的CRLB.因为FR算法设置的搜索步长决定定位精度和迭代次数,为使对比结果更加精确,设置MCMC算法的抽样次数与FR算法的迭代次数相同.通过对结果分析得到,利用MCMC算法进行位置估计的均方误差始终小于FR算法的.当遮蔽因子方差δ2较大时,两种算法的均方误差相差较小.随着δ2的减小,MCMC算法估计的均方误差逼近CRLB,并且始终优于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 结束语

通过对室内环境的分析,利用传播损耗模型建立了似然函数模型,运用马尔可夫蒙特卡罗算法对似然函数中的位置坐标进行估计,通过随机抽样的方法代替了复杂的求导计算过程,避免了FR算法初始值设置导致局部收敛并影响定位精度的问题.并且推导了该模型下的克拉美罗界并进行了复杂度分析.通过仿真实验给出了模拟定位环境中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日,我校软件学院与中航工业第六三一研究所“天脉联合实验室”成立暨揭牌仪式在我校软件学院举行.双方将努力探索教学实践平台合作建设的途径,打造好天脉联合实验室,在平台基础上开展更多深层次合作.

摘自《西电科大报》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