丁婷婷， 高美凤

(江南大学 轻工过程先进控制教育部重点实验室，江苏 无锡 214122)

改进粒子滤波的无线传感器网络目标跟踪算法*

丁婷婷， 高美凤

(江南大学 轻工过程先进控制教育部重点实验室，江苏 无锡 214122)

针对粒子滤波(PF)重采样后造成的粒子枯竭现象的问题, 提出了一种基于改进重采样的粒子滤波无线传感器网络目标跟踪算法。该算法避免了残差重采样算法中的残留粒子重采样问题，减少了计算时间；通过产生新的粒子，增加了粒子的多样性，从而改善了粒子枯竭现象。仿真实验结果表明:改进重采样的粒子滤波算法提高了目标跟踪精度，降低了跟踪误差。

目标跟踪； 无线传感器网络； 粒子滤波； 重采样； 粒子枯竭

0 引 言

无线传感器网络(wireless sensor networks，WSNs)是由部署在监测区域内的大量成本低、体积小、具有一定通信与计算能力的传感器节点组成，且节点之间通过无线通信的方式形成一个多跳的自组织网络系统。相较于具有很高的可靠性、鲁棒性、精确性，但价格昂贵的复杂检测技术，例如：雷达、通用分组无线业务(GPRS)等，WSNs部署随机，具有自组织性、鲁棒性和隐蔽性，因此WSNs非常适用于目标的定位和跟踪。在WSNs目标跟踪中，常用的跟踪算法有：扩展卡尔曼滤波(EKF)[1]、无迹卡尔曼滤波(UKF)[2]、粒子滤波(PF)[3]等。卡尔曼滤波算法在非线性系统中难以应用，扩展卡尔曼滤波适用于非线性化程度比较低的应用中，无迹卡尔曼滤波不能应用于非高斯分布系统。而粒子滤波算法利用粒子集来表示概率，所以,可以很好地解决一些非线性非高斯估计问题。由于目标跟踪中目标的运动是不确定的，其实质是一种非线性问题，因此，粒子滤波广泛应用于目标跟踪。

粒子滤波存在的最大问题是粒子退化，为了避免退化，Arulampalam M S等人[4]提出重采样方法，重采样虽然一定程度上缓解了粒子退化现象，但同时会造成粒子枯竭现象。针对粒子枯竭问题，文献[5]提出一种基于权值选择的粒子滤波的目标跟踪算法.该算法从众多备选粒子中选出权值相对较大的粒子用于状态估计，但易产生明显的权值退化现象。文献[6]是一种基于多通道多选择(multiple-channel/multiple-choice,MCMC)粒子滤波算法，但该算法明显增加了算法的计算时间。本文针对上述问题，从保持样本多样性和控制算法复杂度的角度出发， 提出了一种基于改进重采样的粒子滤波WSNs目标跟踪算法。其基本思想是：对粒子权重与总的粒子数的乘积累计求和后，再取整，求得累计粒子复制次数。当某个粒子被多次(大于1次)选取时，不再单纯地根据求得累计粒子复制次数进行复制，而是将其和重采样前的所有粒子的均值作为父代粒子用来产生新的粒子，然后将新的粒子用于下一时刻的迭代计算。

1 问题描述

WSNs由传感器节点组成，所有节点随机布置在监测区域内，每个传感器节点位置已知。同时,传感器节点之间可以进行无线通信,且每个节点都知道其邻居节点的位置。

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

(1)

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

(2)

式中Φ为状态转移矩阵，G为过程噪音驱动阵，W(k-1)为过程噪音，其方差为Q，H为量测矩阵，V(k)为观测噪音，理想情况下为零均值的高斯白噪音，其方差为R。

2 WSNs中改进粒子滤波目标跟踪算法

2.1 目标跟踪原理

WSNs中跟踪目标时，处于侦测状态的传感器节点探测到目标之后，将探测到的信息数据包发送到汇聚节点。汇聚节点收到所有数据后进行数据融合，得出该物体是否是需要被跟踪的物体。如果是需要被跟踪的物体，将使用一种跟踪运动目标的算法，随着目标运动，跟踪算法将及时通知合适的传感器节点参与跟踪。

2.2 改进的粒子滤波

粒子滤波的核心思想是利用一些离散随机采样点(粒子)来近似系统随机变量的概率密度函数，以样本均值代替积分运算，从而获得状态的最小方差估计[7]。粒子滤波算法在经过若干次迭代后，只有少部分的粒子具有较大的权值，而大部分粒子的权值很小，并趋向于零，这使得大量的运算时间耗费在对系统状态估计作用不大的粒子上。解决该问题有两种方法[8]：一种是选择好的重要性概率密度函数；另一种是使用重采样。在粒子滤波算法框架中引入重采样方法可以有效缓解退化现象，常用的重采样算法有多项式重采样、系统重采样、残差重采样等。不同于其他两种常用的重采样，残差重采样的粒子复制次数绝大多数并不必通过随机数来求取。

残差重采样的实质是将各粒子的权值与1/N的整数倍进行比较，得到的数近似可以看做粒子复制次数，但不一定相等，所以存在残留粒子重采样问题，其具体步骤可见参考文献 [9]。文献[10]提出的改进的残差重采样的基本思想为：权重与总的粒子数的乘积累计求和后，再取整，求得累计粒子复制次数，可以保证重采样前后粒子数目不变。采用此方法可以避免残差重采样造成的残留粒子重采样问题，降低运算的复杂度，从一定程度上减少了运算时间。但文献[10]的重采样仅仅避免了残差重采样造成的残留粒子重采样问题，不能减缓重采样造成的粒子枯竭现象。所以,本文在借鉴文献[10]基础上，在重采样的过程再增加粒子的多样性，即当某个粒子被多次(大于1次)选取时，不再单纯地进行复制，而是将其和重采样前的所有粒子的均值 作为父代粒子，用来产生新的粒子。本文采用的改进残差重采样其具体步骤如下：

3)输出子代粒子。

3 仿真实验

在100 m×100 m的区域内，假定当前4个传感器节点在感知范围内跟踪目标步长M=50,采样周期T=1 s,对三种算法分别进行1 000次仿真，为比较算法的性能，采用均方根误差(RMSE)[11]和平均误差(ARMSE)[11]作为衡量跟踪精确度的指标。

图1(a)是本文改进算法与残差重采样粒子滤波算法、文献[10]进的残差重采样粒子滤波算法跟踪轨迹曲线。图1(b)是目标匀速直线运动时三种算法跟踪误差曲线，在跟踪误差曲线图中随着时间的推移，粒子滤波跟踪误差逐渐增大，这是由于粒子枯竭等因素引起的。在25 s时文献[10]中改进的残差重采样粒子滤波算法跟踪误差比残差重采样粒子滤波算法跟踪误差降低了21 %，本文改进算法跟踪误差比残差重采样粒子滤波算法跟踪误差降低了45.4 %。改进算法是三种算法中跟踪误差增加最缓慢的，由此可见，改进算法缓解了粒子枯竭现象。图1(c)是目标匀速直线运动时三种算法运行时间曲线，尽管三种算法的运行时间动荡不定，但均值相差不大。

图1 目标匀速直线运动曲线Fig 1 Curves of uniform motion of target in a straightline

图2(a)是目标转弯运动时三种算法跟踪轨迹曲线，在40 s之后除本文改进算法外的其他两种算法估计状态偏离真实状态。图2(b)是目标转弯运动时三种算法跟踪误差曲线，在50 s时文献[10]中改进的残差重采样粒子滤波算法跟踪误差比残差重采样粒子滤波算法跟踪误差降低了3.8 %，本文改进算法跟踪误差比残差重采样粒子滤波算法跟踪误差降低了67.8 %。可见，跟踪误差是逐渐增大的，但本文改进算法跟踪误差是三种算法中增大的最慢的。图2(c)是目标转弯运动时三种算法运行时间曲线，可见三种算法的运行时间近似。

图2 目标转弯运动曲线Fig 2 Curves of target motion of turning

表1是三种粒子滤波算法的平均跟踪误差，从表中可见，残差重采样粒子滤波算法的误差值最大，文献[10]改进的残差重采样粒子滤波算法的误差值次之，本文改进算法误差最小。在直线运动时，本文改进算法跟踪误差比文献[10]改进的残差重采样粒子滤波算法的误差减少0.250 7m，比残差重采样粒子滤波算法的误差减少了1.052 8m。在转弯运动时，本文改进算法跟踪误差比文献[10]改进的残差重采样粒子滤波算法的误差减少0.206 3m，比残差重采样粒子滤波算法的误差的减少了1.254 3m。可以看出，改进重采样粒子滤波与文献[10]改进的残差重采样粒子滤波算法和残差重采样粒子滤波算法相比，目标跟踪精度得到提高。重采样实质消除权值小的粒子，复制权值大的粒子，多次迭代后会造成粒子枯竭现象，从上述仿真中可以看出，本文改进的算法跟踪误差在三种算法中最小，由此可以说明，在算法中产生新的粒子，增加粒子的多样性，可以提高跟踪精度。

4 结束语

粒子滤波存在退化现象，采用重采样后存在粒子枯竭

表1 不同粒子滤波算法的平均跟踪误差Tab 1 Average tracking error of different PF algorithms

现象。对此，本文提出了一种基于改进重采样的粒子滤波无线传感器网络目标跟踪算法。该算法在重采样的过程中，产生新的粒子，增加粒子的多样性，另外该算法避免了残差重采样中残留粒子重采样问题。仿真结果表明，该算法提高了跟踪精度。

[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] 谷 静,史健芳.分布式粒子滤波算法在目标跟踪中的应用[J].传感器与微系统,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] 刘 刚,彭 力.权值选优粒子滤波的无线传感器网络目标跟踪[J].传感器与微系统,2011,30(6):30-32.

[6] 席志红,付存利.基于 MCMC 的改进粒子滤波算法[J].计算机工程与设计,2014,5(9):3070-3074.

[7] 国 辉,敬忠良,胡洪涛.基于优化组合重采样的粒子滤波算法[J].上海交通大学学报,2006,40(7):135-139.

[8] 常天庆,李 勇,刘忠仁,等.一种改进重采样的粒子滤波算法[J].计算机应用研究,2013,30(3):748-750.

[9] 冯 驰,王 萌,汲清波.粒子滤波器重采样算法的分析与比较[J].系统仿真学报,2009,21(4):1101-1105.

[10] 冯 驰,赵 娜,王 萌.一种改进残差重采样算法的研究[J].哈尔滨工程大学学报,2010,31(1):120-124.

[11] 黄小平,王 岩,陈冰洁.基于粒子滤波的分布式目标跟踪算法[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

国家自然科学基金资助项目(61373126)

TP 393

A

1000—9787(2016)07—0140—03

丁婷婷(1990-)，女，安徽安庆人，硕士研究生，主要研究方向为检测技术与自动化装置。