基于馬爾可夫鏈蒙特卡羅算法的無線電定位

張敬平

(上海戲劇學院多媒體虛擬合成重點實驗室，上海 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.