改進(jìn)粒子濾波的無線傳感器網(wǎng)絡(luò)目標(biāo)跟蹤算法*

丁婷婷， 高美鳳

(江南大學(xué) 輕工過程先進(jìn)控制教育部重點實驗室，江蘇 無錫 214122)

改進(jìn)粒子濾波的無線傳感器網(wǎng)絡(luò)目標(biāo)跟蹤算法*

丁婷婷， 高美鳳

(江南大學(xué) 輕工過程先進(jìn)控制教育部重點實驗室，江蘇 無錫 214122)

針對粒子濾波(PF)重采樣后造成的粒子枯竭現(xiàn)象的問題, 提出了一種基于改進(jìn)重采樣的粒子濾波無線傳感器網(wǎng)絡(luò)目標(biāo)跟蹤算法。該算法避免了殘差重采樣算法中的殘留粒子重采樣問題，減少了計算時間；通過產(chǎn)生新的粒子，增加了粒子的多樣性，從而改善了粒子枯竭現(xiàn)象。仿真實驗結(jié)果表明:改進(jìn)重采樣的粒子濾波算法提高了目標(biāo)跟蹤精度，降低了跟蹤誤差。

目標(biāo)跟蹤； 無線傳感器網(wǎng)絡(luò)； 粒子濾波； 重采樣； 粒子枯竭

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)是由部署在監(jiān)測區(qū)域內(nèi)的大量成本低、體積小、具有一定通信與計算能力的傳感器節(jié)點組成，且節(jié)點之間通過無線通信的方式形成一個多跳的自組織網(wǎng)絡(luò)系統(tǒng)。相較于具有很高的可靠性、魯棒性、精確性，但價格昂貴的復(fù)雜檢測技術(shù)，例如：雷達(dá)、通用分組無線業(yè)務(wù)(GPRS)等，WSNs部署隨機(jī)，具有自組織性、魯棒性和隱蔽性，因此WSNs非常適用于目標(biāo)的定位和跟蹤。在WSNs目標(biāo)跟蹤中，常用的跟蹤算法有：擴(kuò)展卡爾曼濾波(EKF)[1]、無跡卡爾曼濾波(UKF)[2]、粒子濾波(PF)[3]等?？柭鼮V波算法在非線性系統(tǒng)中難以應(yīng)用，擴(kuò)展卡爾曼濾波適用于非線性化程度比較低的應(yīng)用中，無跡卡爾曼濾波不能應(yīng)用于非高斯分布系統(tǒng)。而粒子濾波算法利用粒子集來表示概率，所以,可以很好地解決一些非線性非高斯估計問題。由于目標(biāo)跟蹤中目標(biāo)的運(yùn)動是不確定的，其實質(zhì)是一種非線性問題，因此，粒子濾波廣泛應(yīng)用于目標(biāo)跟蹤。

粒子濾波存在的最大問題是粒子退化，為了避免退化，Arulampalam M S等人[4]提出重采樣方法，重采樣雖然一定程度上緩解了粒子退化現(xiàn)象，但同時會造成粒子枯竭現(xiàn)象。針對粒子枯竭問題，文獻(xiàn)[5]提出一種基于權(quán)值選擇的粒子濾波的目標(biāo)跟蹤算法.該算法從眾多備選粒子中選出權(quán)值相對較大的粒子用于狀態(tài)估計，但易產(chǎn)生明顯的權(quán)值退化現(xiàn)象。文獻(xiàn)[6]是一種基于多通道多選擇(multiple-channel/multiple-choice,MCMC)粒子濾波算法，但該算法明顯增加了算法的計算時間。本文針對上述問題，從保持樣本多樣性和控制算法復(fù)雜度的角度出發(fā)， 提出了一種基于改進(jìn)重采樣的粒子濾波WSNs目標(biāo)跟蹤算法。其基本思想是：對粒子權(quán)重與總的粒子數(shù)的乘積累計求和后，再取整，求得累計粒子復(fù)制次數(shù)。當(dāng)某個粒子被多次(大于1次)選取時，不再單純地根據(jù)求得累計粒子復(fù)制次數(shù)進(jìn)行復(fù)制，而是將其和重采樣前的所有粒子的均值作為父代粒子用來產(chǎn)生新的粒子，然后將新的粒子用于下一時刻的迭代計算。

1 問題描述

WSNs由傳感器節(jié)點組成，所有節(jié)點隨機(jī)布置在監(jiān)測區(qū)域內(nèi)，每個傳感器節(jié)點位置已知。同時,傳感器節(jié)點之間可以進(jìn)行無線通信,且每個節(jié)點都知道其鄰居節(jié)點的位置。

X(k)=ΦX(k-1)+GW(k-1)

(1)

Z(k)=HX(k)+V(k)

(2)

式中Φ為狀態(tài)轉(zhuǎn)移矩陣，G為過程噪音驅(qū)動陣，W(k-1)為過程噪音，其方差為Q，H為量測矩陣，V(k)為觀測噪音，理想情況下為零均值的高斯白噪音，其方差為R。

2 WSNs中改進(jìn)粒子濾波目標(biāo)跟蹤算法

2.1 目標(biāo)跟蹤原理

WSNs中跟蹤目標(biāo)時，處于偵測狀態(tài)的傳感器節(jié)點探測到目標(biāo)之后，將探測到的信息數(shù)據(jù)包發(fā)送到匯聚節(jié)點。匯聚節(jié)點收到所有數(shù)據(jù)后進(jìn)行數(shù)據(jù)融合，得出該物體是否是需要被跟蹤的物體。如果是需要被跟蹤的物體，將使用一種跟蹤運(yùn)動目標(biāo)的算法，隨著目標(biāo)運(yùn)動，跟蹤算法將及時通知合適的傳感器節(jié)點參與跟蹤。

2.2 改進(jìn)的粒子濾波

粒子濾波的核心思想是利用一些離散隨機(jī)采樣點(粒子)來近似系統(tǒng)隨機(jī)變量的概率密度函數(shù)，以樣本均值代替積分運(yùn)算，從而獲得狀態(tài)的最小方差估計[7]。粒子濾波算法在經(jīng)過若干次迭代后，只有少部分的粒子具有較大的權(quán)值，而大部分粒子的權(quán)值很小，并趨向于零，這使得大量的運(yùn)算時間耗費在對系統(tǒng)狀態(tài)估計作用不大的粒子上。解決該問題有兩種方法[8]：一種是選擇好的重要性概率密度函數(shù)；另一種是使用重采樣。在粒子濾波算法框架中引入重采樣方法可以有效緩解退化現(xiàn)象，常用的重采樣算法有多項式重采樣、系統(tǒng)重采樣、殘差重采樣等。不同于其他兩種常用的重采樣，殘差重采樣的粒子復(fù)制次數(shù)絕大多數(shù)并不必通過隨機(jī)數(shù)來求取。

殘差重采樣的實質(zhì)是將各粒子的權(quán)值與1/N的整數(shù)倍進(jìn)行比較，得到的數(shù)近似可以看做粒子復(fù)制次數(shù)，但不一定相等，所以存在殘留粒子重采樣問題，其具體步驟可見參考文獻(xiàn) [9]。文獻(xiàn)[10]提出的改進(jìn)的殘差重采樣的基本思想為：權(quán)重與總的粒子數(shù)的乘積累計求和后，再取整，求得累計粒子復(fù)制次數(shù)，可以保證重采樣前后粒子數(shù)目不變。采用此方法可以避免殘差重采樣造成的殘留粒子重采樣問題，降低運(yùn)算的復(fù)雜度，從一定程度上減少了運(yùn)算時間。但文獻(xiàn)[10]的重采樣僅僅避免了殘差重采樣造成的殘留粒子重采樣問題，不能減緩重采樣造成的粒子枯竭現(xiàn)象。所以,本文在借鑒文獻(xiàn)[10]基礎(chǔ)上，在重采樣的過程再增加粒子的多樣性，即當(dāng)某個粒子被多次(大于1次)選取時，不再單純地進(jìn)行復(fù)制，而是將其和重采樣前的所有粒子的均值 作為父代粒子，用來產(chǎn)生新的粒子。本文采用的改進(jìn)殘差重采樣其具體步驟如下：

3)輸出子代粒子。

3 仿真實驗

在100 m×100 m的區(qū)域內(nèi)，假定當(dāng)前4個傳感器節(jié)點在感知范圍內(nèi)跟蹤目標(biāo)步長M=50,采樣周期T=1 s,對三種算法分別進(jìn)行1 000次仿真，為比較算法的性能，采用均方根誤差(RMSE)[11]和平均誤差(ARMSE)[11]作為衡量跟蹤精確度的指標(biāo)。

圖1(a)是本文改進(jìn)算法與殘差重采樣粒子濾波算法、文獻(xiàn)[10]進(jìn)的殘差重采樣粒子濾波算法跟蹤軌跡曲線。圖1(b)是目標(biāo)勻速直線運(yùn)動時三種算法跟蹤誤差曲線，在跟蹤誤差曲線圖中隨著時間的推移，粒子濾波跟蹤誤差逐漸增大，這是由于粒子枯竭等因素引起的。在25 s時文獻(xiàn)[10]中改進(jìn)的殘差重采樣粒子濾波算法跟蹤誤差比殘差重采樣粒子濾波算法跟蹤誤差降低了21 %，本文改進(jìn)算法跟蹤誤差比殘差重采樣粒子濾波算法跟蹤誤差降低了45.4 %。改進(jìn)算法是三種算法中跟蹤誤差增加最緩慢的，由此可見，改進(jìn)算法緩解了粒子枯竭現(xiàn)象。圖1(c)是目標(biāo)勻速直線運(yùn)動時三種算法運(yùn)行時間曲線，盡管三種算法的運(yùn)行時間動蕩不定，但均值相差不大。

圖1 目標(biāo)勻速直線運(yùn)動曲線Fig 1 Curves of uniform motion of target in a straightline

圖2(a)是目標(biāo)轉(zhuǎn)彎運(yùn)動時三種算法跟蹤軌跡曲線，在40 s之后除本文改進(jìn)算法外的其他兩種算法估計狀態(tài)偏離真實狀態(tài)。圖2(b)是目標(biāo)轉(zhuǎn)彎運(yùn)動時三種算法跟蹤誤差曲線，在50 s時文獻(xiàn)[10]中改進(jìn)的殘差重采樣粒子濾波算法跟蹤誤差比殘差重采樣粒子濾波算法跟蹤誤差降低了3.8 %，本文改進(jìn)算法跟蹤誤差比殘差重采樣粒子濾波算法跟蹤誤差降低了67.8 %?？梢姡櫿`差是逐漸增大的，但本文改進(jìn)算法跟蹤誤差是三種算法中增大的最慢的。圖2(c)是目標(biāo)轉(zhuǎn)彎運(yùn)動時三種算法運(yùn)行時間曲線，可見三種算法的運(yùn)行時間近似。

圖2 目標(biāo)轉(zhuǎn)彎運(yùn)動曲線Fig 2 Curves of target motion of turning

表1是三種粒子濾波算法的平均跟蹤誤差，從表中可見，殘差重采樣粒子濾波算法的誤差值最大，文獻(xiàn)[10]改進(jìn)的殘差重采樣粒子濾波算法的誤差值次之，本文改進(jìn)算法誤差最小。在直線運(yùn)動時，本文改進(jìn)算法跟蹤誤差比文獻(xiàn)[10]改進(jìn)的殘差重采樣粒子濾波算法的誤差減少0.250 7m，比殘差重采樣粒子濾波算法的誤差減少了1.052 8m。在轉(zhuǎn)彎運(yùn)動時，本文改進(jìn)算法跟蹤誤差比文獻(xiàn)[10]改進(jìn)的殘差重采樣粒子濾波算法的誤差減少0.206 3m，比殘差重采樣粒子濾波算法的誤差的減少了1.254 3m?？梢钥闯?，改進(jìn)重采樣粒子濾波與文獻(xiàn)[10]改進(jìn)的殘差重采樣粒子濾波算法和殘差重采樣粒子濾波算法相比，目標(biāo)跟蹤精度得到提高。重采樣實質(zhì)消除權(quán)值小的粒子，復(fù)制權(quán)值大的粒子，多次迭代后會造成粒子枯竭現(xiàn)象，從上述仿真中可以看出，本文改進(jìn)的算法跟蹤誤差在三種算法中最小，由此可以說明，在算法中產(chǎn)生新的粒子，增加粒子的多樣性，可以提高跟蹤精度。

4 結(jié)束語

粒子濾波存在退化現(xiàn)象，采用重采樣后存在粒子枯竭

表1 不同粒子濾波算法的平均跟蹤誤差Tab 1 Average tracking error of different PF algorithms

現(xiàn)象。對此，本文提出了一種基于改進(jìn)重采樣的粒子濾波無線傳感器網(wǎng)絡(luò)目標(biāo)跟蹤算法。該算法在重采樣的過程中，產(chǎn)生新的粒子，增加粒子的多樣性，另外該算法避免了殘差重采樣中殘留粒子重采樣問題。仿真結(jié)果表明，該算法提高了跟蹤精度。

[1] Hamouda Y E M,Phillips C.Adaptive sampling for energy-efficient collaborative multi-target tracking in wireless sensor networks[J].IET Wireless Sensor Systems,2011,1(1):15-25.

[2] Zhao Y,Chen W,Gao J.Advances in mechanical and electronic engineering [M].Berlin/Heidelberg:Springer,2012:387-391.

[3] 谷 靜,史健芳.分布式粒子濾波算法在目標(biāo)跟蹤中的應(yīng)用[J].傳感器與微系統(tǒng),2014,33(8):158-160.

[4] Arulampalam M S,Maskell S,Gordon N,et al.A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tra-cking[J].IEEE Transactions on Signal Processing,2002,50(2):174-188.

[5] 劉 剛,彭 力.權(quán)值選優(yōu)粒子濾波的無線傳感器網(wǎng)絡(luò)目標(biāo)跟蹤[J].傳感器與微系統(tǒng),2011,30(6):30-32.

[6] 席志紅,付存利.基于 MCMC 的改進(jìn)粒子濾波算法[J].計算機(jī)工程與設(shè)計,2014,5(9):3070-3074.

[7] 國 輝,敬忠良,胡洪濤.基于優(yōu)化組合重采樣的粒子濾波算法[J].上海交通大學(xué)學(xué)報,2006,40(7):135-139.

[8] 常天慶,李 勇,劉忠仁,等.一種改進(jìn)重采樣的粒子濾波算法[J].計算機(jī)應(yīng)用研究,2013,30(3):748-750.

[9] 馮 馳,王 萌,汲清波.粒子濾波器重采樣算法的分析與比較[J].系統(tǒng)仿真學(xué)報,2009,21(4):1101-1105.

[10] 馮 馳,趙 娜,王 萌.一種改進(jìn)殘差重采樣算法的研究[J].哈爾濱工程大學(xué)學(xué)報,2010,31(1):120-124.

[11] 黃小平,王 巖,陳冰潔.基于粒子濾波的分布式目標(biāo)跟蹤算法[J].計算機(jī)工程,2011,37(4):84-86.

Target tracking algorithm for WSNs based on improved particle filtering*

DING Ting-ting, GAO Mei-feng

(Key Laboratory of Advanced Process Control for Light Industry,Ministry of Education,Jiangnan University,Wuxi 214122,China)

Aiming at particle impoverishment phenomenon caused by particle filtering resampling,a target tracking algorithm for WSNs based on improved resampling particle filtering is presented for the WSNs.The proposed algorithm avoids residual particle resampling problem,thus reduces calculation time;by producing new particles,diversity of particles is increased,so particle impoverishment phenomenon is improved.Simulation experimental results show that the improved resampling particle filtering algorithm improves target tracking precision and reduce tracking error.

target tracking; wireless sensor networks(WSNs); particle filtering(PF); resampling; particle impoverishment

10.13873/J.1000—9787(2016)07—0140—03

2015—10—12

國家自然科學(xué)基金資助項目(61373126)

TP 393

A

1000—9787(2016)07—0140—03

丁婷婷(1990-)，女，安徽安慶人，碩士研究生，主要研究方向為檢測技術(shù)與自動化裝置。