丁婷婷， 高美鳳

(江南大學(xué) 輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 無(wú)錫 214122)

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

丁婷婷， 高美鳳

(江南大學(xué) 輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 無(wú)錫 214122)

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

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

0 引 言

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

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

1 問(wèn)題描述

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

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

(1)

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

(2)

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

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

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

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

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

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

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

3)輸出子代粒子。

3 仿真實(shí)驗(yàn)

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

現(xiàn)象。對(duì)此，本文提出了一種基于改進(jìn)重采樣的粒子濾波無(wú)線(xiàn)傳感器網(wǎng)絡(luò)目標(biāo)跟蹤算法。該算法在重采樣的過(guò)程中，產(chǎn)生新的粒子，增加粒子的多樣性，另外該算法避免了殘差重采樣中殘留粒子重采樣問(wè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ú)線(xiàn)傳感器網(wǎng)絡(luò)目標(biāo)跟蹤[J].傳感器與微系統(tǒng),2011,30(6):30-32.

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

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

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

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

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

[11] 黃小平,王 巖,陳冰潔.基于粒子濾波的分布式目標(biāo)跟蹤算法[J].計(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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61373126)

TP 393

A

1000—9787(2016)07—0140—03

丁婷婷(1990-)，女，安徽安慶人，碩士研究生，主要研究方向?yàn)闄z測(cè)技術(shù)與自動(dòng)化裝置。