基于马尔可夫链蒙特卡罗算法的无线电定位

张敬平

(上海戏剧学院多媒体虚拟合成重点实验室，上海 200040)

0 引言

实时定位系统是新兴的室内定位应用系统，目前主要的实现方法包括测量信标无线电信号传输时间、信号传输角度以及信号强度等.其中，测量无线信标的信号传输角度(Angle Of Arrive，AOA)是重要的方法之一，被广泛应用于雷达信号跟踪、目标跟踪以及目标定位中.本文主要利用马尔可夫链蒙特卡罗算法，给出AOA定位方法的目标定位，应用于多媒体舞台剧中目标的跟踪定位，实现真实空间的目标与多媒体背景的虚拟空间元素间的互动.

1 无线电测向定位问题建模

粒子滤波是个实现递归的贝叶斯滤波(Bayesian approach)，其中最重要是使用马尔可夫链蒙特卡罗(Markov Chain Monte Carlo algorithm，MCMC)算法.MCMC算法广泛使用于雷达信号跟踪、目标跟踪以及目标定位中.对于信号噪声符合正态分布的模型，卡尔曼滤波(Kalman filter)是最佳的处理方法.但是，卡尔曼滤波在处理观测模式噪声不符合正态分布的情况时，往往结果不够理想.［1－3］

设现有1个通过无线电实现的目标跟踪系统，被跟踪者携带1个无线信号发生源，原地不动的跟踪者用有向天线测量被跟踪者的位置.由于跟踪者原地不动，只能测量出被跟踪目标的方位即角度.根据已知目标开始的位置和运动方向、速度，要求能够估计目标的位置坐标(x，y).由于人很难按直线行走，速度的方向和大小总在变，需用非线性方法求目标的位置坐标.图1所示为目标、跟踪定位模型.

图1 目标、跟踪定位模型

由图1可建立数学模型

式中:f(xt)为t时刻的状态，即运动目标的位置和速度方向.

在本例中，状态转换符合一定的规律，即存在不变形的函数

显然，系统的状态转变符合Markov过程，即xt的状态只取决于xt－1，应用概率密度函数表示，得

实际不存在理想的不变形函数，因此，系统实际的转换表示为

式(4)即为系统转换函数，式中:Ut为1个随机干扰或者其他很难用函数来描述的分布.被跟踪目标不可能保持匀速直线运动，总会走偏或快慢发生变化.

另外，需要考察测量模型.从该例可知系统有1个测量角度的方法.实际中，这些测量总是存在这样或那样的误差.可建立1个观测模型

式(4)和(5)中:fx和 fy均为已知，而 Ut和 Vt也为已知，但其分布是非正态分布或无法用解析表达式表达.可通过求解下式求平均预测值.

设

如果g(x)=x，即为求解均值.

2 MCMC算法

运用贝叶斯规则解决上述问题.

式中:p(xt|y0:t－1)可应用 Markov 假设，得

由式(8)可知，p(xt|y0:t－1)的计算是个递归迭代过程，即可通过迭代运算计算.但式(9)使用积分运算，由于Ut和Vt很难表示，不便于用积分运算，可用蒙特卡罗序列法计算.［4－6］

用MCMC算法处理上述模型.使用M个加权值的状态空间序列表示p(xt|y0:t－1)，这M个序列表示如下:

得

系统使用序列的分布见图2.

图2 系统使用序列分布

即随机从p(x|x0)中选取M个状态量，以其概率密度为权值进行归一化操作.

更新序列可采用如下方法:

经过式(13)的更新，最后得1个较坏的结果，即这些序列(粒子)中，只有极少数的权值有意义，具备“活力”，其他权值会变得非常非常小，不具备“活力”.因此，为避免这种情况，需要采用重采样的算法解决，即并不对每个例子进行“进化”操作，而是选择权值高的进行多次进化操作.这样，每次迭代的结果才能更加接近结果xt.

重采样算法对粒子进行进化的算法如下:

(1)计算序列矩阵.为方便进行随机选取，选取

(2)随机选取进化的粒子，权值大的粒子被进化多次，满足

式中:R为0～1的随机数.

(3)对m粒子进行如式(13)的进化.

(4)重新归一化权值.

通过上述算法，可保证有足够多的“活力”粒子.

图3为MCMC算法示意.

图3 MCMC算法示意

3 无线电测向定位算法实现

系统状态模型状态量

系统状态转换模型

系统观测模型

设观测者的位置为(0，0)，初始位置为(10，10)，观测者速度分别为x方向1 m/s，y方向1 m/s，每次的误差为方差=0.2的正态分布.无线电测向误差为0.001.

系统初始值

算法实现如下

(1)根据{x0，y0，vx0，vy0}初始值，计算初始分布和初始权值

(2)得到观测值Dt.计算序列矩阵，为方便进行随机选取，选取

随机选取进化粒子，权值大的粒子被进化多次

式中:R为0～1的随机数.

进行进化

(3)输出结果，得到预测的位置

(4)跳转到(2)进行迭代运算.

系统用Matlab进行仿真，运算结果见图4.

图4 系统仿真结果示意

由图4可知，1为目标实际路线，2为跟踪结果.即使在路线发生比较大的偏移时，系统还是可以比较可靠地跟踪目标所在的位置.

4 结束语

该无线电目标定位方法，在上海戏剧学院的多媒体互动舞蹈剧中得到很好的应用.通过跟踪舞台上的演员或道具等目标位置的变化，驱动多媒体舞台背景的虚拟场景元素的位置和形态进行变化，实现真实空间与虚拟空间的真正意义的互动，给观众带来全新的艺术享受.但该方法也存在不足，不易实现全方位6自由度的跟踪，这将是今后研究的方向.

［1］COMANICIU D，RAMESH V，MEER P.Real－time tracking of non－rigid objects using mean shift［C］//WERNER B.IEEE Int Proc Comput Vision ＆ Pattern Recognition.Stoughton:Printing House，2000:142－149.

［2］CHENG Y.Mean shift，mode seeking and clustering［J］.IEEE Trans on Pattern Anal＆ Machine Intelligence，1995，17(8):790－799.

［3］BLACK M J，JEPSON A D.A probabilistic framework for matching temporal trajectories:Condensation－based recognition of gestures and expressions［M］.Berlin:springer，1998:909－924.

［4］胡士强，敬忠良.粒子滤波算法综述［J］.控制与决策，2005，20(4):361－365.

［5］ARULAMPALAM M S，MASKELL S，GORDON N，et al.A tutorial on particle filters for online nonlinear non－Gaussian Bayesian tracking［J］.IEEE Int Semi Target Tracking:Algorithms ＆ Applications，2002，2(2):174－199.

［6］NUMMIARO K，KOLLER－MEIER E，van GOOL L J.Object tracking with an adaptive color－based particle filter［C］//Proc Deutsche Arbeitsgemeinschaft for Mustererkennung，Zurich，Switzerland，September 16－18，2002:25－29.