一种改进的粒子滤波在WSN目标跟踪中的应用

黄小平，王岩，李超，邵靖宇

(北京航空航天大学 自动化与电气工程学院，北京，100191)

摘要：根据无线传感器网络(WSN)的特性，提出了一种改进的粒子滤波算法。该算法首先利用极大似然算法估计移动目标最新时刻的位置，再用卡尔曼滤波得到更为准确的目标状态信息和方差，为粒子滤波提供参考分布，能有效改善滤波器的性能。仿真实验结果表明：改进的滤波算法不易发散且跟踪精度较高，与其他改进算法相比实时性有较大的提高。

关键词：无线传感器网络；粒子滤波；卡尔曼滤波；极大似然；目标跟踪

中图分类号：TP393          文献标志码：A         文章编号：1672-7207(2011)S1-0895-05

Application of an improved particle filter algorithm for target tracking in WSN

HUANG Xiao-ping, WANG Yan, LI Chao, SHAO Jing-yu

(School of Automation Science and Electrical Engineering, Beihang University, Beijing 100191, China)

Abstract: A novel PF algorithm was proposed. In this algorithm, the maximum likelihood (ML) was firstly used to estimate the latest position of mobile target, then the Kalman filter (KF) was used to get the more accurate state (their instantaneous locations and velocities) information and covariance of mobile target, which eventually provide a proposal distribution for PF. The simulation indicates that this improved PF has not only a higher tracking accuracy but also a better characteristic of real-time.

Key words: wireless sensor network (WSN); particle filter (PF); Kalman filter (KF); maximum likelihood (ML); target tracking

无线传感器网络是由多个节点组成的面向任务的无线自组织网络。传感器节点体积小，价格低廉，采用多跳的无线通信方式，以及网络化的随机部署，具有自组织、鲁棒性等特点。无线传感器网络的应用价值已被广泛关注，如智能交通、野生动物保护、机器人、战场信息收集等。其中，对目标的实时定位和跟踪是一个关键问题^[1]。

目标跟踪是一个非线性过程，且观测数据受噪声干扰，采用合适的滤波算法能够有效降低噪声的干 扰。很多研究者将扩展卡尔曼(EKF)^[2]，无迹卡尔曼(UKF)^[3]等非线性滤波器用于无线传感器网络目标跟踪中，这些算法的跟踪精度较低，且都是假设系统噪声为高斯白噪声。Gordon等^[4-6]提出的粒子滤波^]算法克服了线性高斯模型的约束，理论上能对任何状态分布进行准确估计，但是，该方法经过几次递推计算以后会出现粒子集多样性散失问题，最终会导致滤波发散现象。因此很多学者提出了一些改进的粒子滤波算法，如高斯和粒子滤波(GSPF)^[6]、扩展卡尔曼粒子滤波(EPF)^[7]和无迹卡尔曼粒子滤波(UPF)^[8-10]。用EKF为EPF粒子滤波提供建议密度分布时，存在一阶近似带来的非线性误差问题。近年来很多学者提出了UPF算法，它是UKF和PF的结合，利用UKF产生建议密度分布，能够很好地近似后验概率。由于UKF也是一种递推的最小均方差估计，无需对非线性方程线性化，可以精确到状态估计的二阶距，因而，精度得到大大提高。但是，UPF计算复杂度有所增加，实时性比较差。

本文作者对无线传感器网络作了进一步的分析和讨论，提出了一种改进的新算法。该方法首先用极大似然法估计目标的位置，再用递推卡尔曼滤波得到更精确的目标状态以及协方差，为粒子滤波算法提供参考分布。由于极大似然法和递推卡尔曼提供的建议密度包含目标最新的观测信息，因而能较大程度地提高跟踪精度。与EPF和UPF相比，该算法的复杂度有所降低，实时性更好。

1  目标跟踪的描述

利用无线传感器网络进行目标跟踪，实质上是一个多传感器节点协作的过程。通常将该过程分为侦测、定位、预测和消息通知等几个阶段，即在目标未出现时所有节点处于侦测状态；目标出现后，选取相应的节点对目标定位，建立轨迹方程，并用滤波算法估计目标状态和预测目标下一时刻的位置，通过消息通知维持对目标的跟踪。

1.1  网络模型

图1所示为采用等级的网络结构。将传感器节点分为普通节点(sensor node, SN)和簇头节点(cluster head, CH)。

图1  网络结构示意图

Fig.1  Schemic of WSN structure

所有的SN节点负责监测目标，一旦探测到目标就开始采集数据，并将采集的信息发送到CH节点。CH节点根据各个节点的数据，用跟踪算法计算目标的位置、速度等信息，维持对目标的跟踪。这里假设所有的SN节点在初始化的时候都能得到自己的真实位置信息，在一个簇内，SN节点都能在一跳的范围内与CH节点通信。

1.2  系统方程的建立

设目标在二维平面上运动，目标的位置为(x, y)，传感器节点的位置为(x_i, y_i)，则可以得到目标运动的状态方程：

         (1)

其中：

, 。

Φ为状态转移矩阵；Γ为过程噪声驱动；w(k)为过程噪声，其方差为Q，目标运动状态为 ；T为采样时间，传感器节点的观测方程为：

    (2)

其中：v为观测噪声，其方差为R。很显然，观测方程是严重非线性的，采用非线性滤波器能够有效地提高跟踪精度。

2  粒子滤波及其改进算法

2.1  粒子滤波的基本原理

粒子滤波不要求系统一定要线性高斯模型，适合非线性目标跟踪，它是基于蒙特卡洛原理的递推贝叶斯滤波。其基本思想是通过从当前系统状态分布中抽取一系列加权的粒子，对系统的下一状态进行估计和更新。随着粒子数目的增加，粒子的概率密度函数逐渐逼近状态的概率密度函数。其具体计算过程如下。

(1) 初始化。当k=0时，生成服从p(x₀)分布的N个样本。

(2) 采样和权值更新。当k=1，2，…时，对N个

样本按式(1)重复计算得到样本集，它服从以为概率密度函数的分布。

(3) 在获得新的测量z_k后计算权值并将权值归一化：

         (3)

(4) 重采样。对样本重新采样，使近似服从以为概率密度函数的分布，重新设定粒子的权值为1/N。

(5) 状态更新：

             (4)

粒子滤波算法的缺点是容易出现粒子集退化现象，避免该现象的有效方法是增加采样点、重采样、选择参考分布函数。增加采样点会加重计算量，影响实时性；重采样会降低粒子集的多样性，最终也会影响滤波器的性能。因此，选择合理的参考分布函数是较为理想的选择。

2.2  改进的粒子滤波算法

在传感器网络一个簇内有3个或者3个以上的传感器节点对目标距离进行观测时候，可以用极大似然法得到目标的位置：

             (5)

其中：Y=[x, y] ^T为目标的位置，(x_i, y_i)为节点位置，z_i为传感器观测距离，

将上述位置信息Y再经过一次卡尔曼滤波运算，可以得到更为精确的目标状态信息。卡尔曼预测的基本公式如下：

          (6)

      (7)

  (8)

          (9)

         (10)

其中：为状态X(k)对于观测值Y(k)

的增益；P(k)为协方方差矩阵；ε(k)为观测向量与预测向量之间的误差；K为卡尔曼增益；Ф为状态转移矩阵；R为观测噪声协方差。用上述状态和方差可以构造参考分布函数，为粒子滤波提供参考分布，这样能改善基本粒子滤波因多次迭代丧失料子多样性的问题，从而改善粒子滤波的性能。

改进后算法的步骤可以归纳为：

(1) 初始化：k=0，从先验概率p(X₀)中抽取N个状样本；

(2) 重要性采样：k=1, 2, …。用极大似然和卡尔曼滤波得到均值和方差

采样：

；

设置：

，。

权值计算并归一化：

    (11)

(3) 重采样。按照重要性权值的大小，从中独立地抽取N个粒子。

(4) 状态更新：

           (12)

3  仿真实验

在1个100 m×100 m的监测场地上，随机地部署了J(J=6)个传感器节点，设每个节点都能侦测到区域内的目标。目标运动过程中的过程噪声为Q=  diag[q  q]，当q设置成不同值时可以比较各个算法在目标机动情况下的跟踪效果。观测噪声R=5，采样时间T=1 s。初始状态为X₀=[1  2  20  1.2] ^T, 采样点数M=50。为了便于比较，这里同时用PF，EPF，UPF和本文改进算法MPF进行仿真分析。图2所示为改进算法MPF与PF，EPF和UPF的跟踪轨迹比较结果。

3.1  跟踪精度比较

为了从微观上比较跟踪精度，引入了最小均方根误差(RMSE, E_RMS)的概念，其定义为：

  (13)

其中：为滤波器k时刻的估计值；(x(k),  y(k))为目标k时刻的实际位置。图3所示为在过程噪声非常小的情况下(q=0.000 1)，大部分粒子集中在真实值附近，因而基本粒子滤波非常稳定，性能也非常好。这时用EKF和UKF等方法为粒子滤波提供参考分布反而使滤波器性能下降。因为用这些方法提供的参考分布不是完全准确的，它会分散原来集中在真实值附近的粒子，在这种情况下改进算法MPF，EPF和UPF不如基本粒子滤波算法。在过程噪声加大(q=0.001)时，如图4所示，基本粒子滤波的跟踪精度已经不如UPF和MPF，因为参考分布起了作用。随着过程噪声的再次加大(q=0.01)，如图5所示，基本粒子滤波已经开始出现滤波发散现象，而用EKF，UKF和ML-KF算法改进的滤波器能较好地对目标进行跟踪。

图2  跟踪轨迹曲线

Fig.2  Curves of tracking trajectory

图3  RMSE比较(q=0.000 1)

Fig.3  Comparison of RMSE

另外，为了衡量跟踪过程中的整体性能，本文引入平均误差概念，其定义如下：

         (14)

图4  RMSE比较(q=0.001)

Fig.4  Comparison of RMSE

图5  RMSE比较(q=0.01)

Fig.5  Comparison of RMSE

表1  误差E_ARMS比较

Table 1  Comparison of ARMSE

由表1可以看出，随着噪声的加大，E_ARMS也随着增大，但是基本粒子滤波很快就发散了，改进算法EPF，UPF和MPF较为稳定，且MPF的E_ARMS最小，跟踪精度最好。

3.2  实时性比较

目标跟踪过程是一个实时动态过程，一个跟踪任务需要算法在规定的时间内完成，否则就无法跟踪目标。图6所示为实时性比较结果。从图6可以看出：基本粒子滤波算法耗时最少，大约需要0.13 s；而UPF和EPF需要更多的计算时间(每周期大约0.26 s)，主要是UPF需要进行UT变换，EKF需要计算雅可比行列式或海塞矩阵，这些都要大量的计算时间。而MPF算法虽然用了ML和KF 2种方法，但是它们计算相对简单，无需复杂的矩阵运算，计算量之和仍然小于UKF与EKF的计算量。

图6  实时性比较

Fig.6  Comparison of real-time characteristic

4  结论

(1) 粒子滤波不要求系统的状态方程和观测方程是线性的，对任意分布的噪声都适用。

(2) 极大似然估计实现简单，能够有效地估计目标最新的位置信息，经过卡尔曼滤波后能获得更为准确的状态和方差，为粒子滤波提供参考分布，能有效改善粒子滤波的性能。

(3)在过程噪声较大的情况下，改进算法的跟踪精度较高，改善效果明显。本文算法在实时性方面虽然优于UPF，但是，要实现更快速的粒子滤波跟踪算法，有待进一步研究。

参考文献：

[1] Boukerche A, Oliveira H A B, Nakamura E F, et al. Localization systems for wireless sensor networks[J]. Wireless Communica- tions, IEEE, 2007, 14(6): 6-12.

[2] LIU Yang, SUN Zhen-dong. EKF-based adaptive sensor scheduling for target tracking[C]//International Symposium on Information Science and Engineering. Guangzhou: South China University of Technology, 2008: 171-174.

[3] ZHOU Yan, LI Jian-xun, WANG Dong-li. Unscented Kalman Filtering based quantized innovation fusion for target tracking in WSN with feedback[C]//International Conference on Machine Learning and Cybernetics. Shanghai: Shanghai Jiao Tong University, 2009: 1457-1463.

[4] Gordon N J, Salmond D J, Smith A F M. Novel approach to non-linear/non-Gaussuan Bayesian state estimation[J]. IEEE Proceedings on Radar and Signal Processing, 1993, 140(2): 107-113.

[5] Sanjeev Arulampalam M, Simon M, Neil G, et al. A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking[J]. IEEE Transactions on Signal Processing, 2002, 50(2): 174-188.

[6] Ahmed N, Rutten M, Bessell T, et al. Detection and tracking using particle filter based wireless sensor networks[J]. IEEE Transaction on Mobile Computing, 2010(9): 1-15

[7] Katsuji U, Toshiharu H. Nonlinear state estimation by evolution strategies based gaussian sum particle filter[J]. Lecture Notes in Artifical Intelligence, 2005, 3681: 635-642.

[8] LI Liang-qun, JI Hong-bing, LUO Jun-hui. The iterated extended Kalman particle filter[C]//IEEE international Symposium on Communications and Information Technology. Xi’an: Xidian Univesity, 2005, (2): 1213-1216.

[9] Olama M M, Djouadi S M, Papageorgiou I G, et al. Estimation of mobile station position and velocity in multipath wireless networks using the unscented particle filter[C]// Proceedings of the 46th IEEE Conference on Decision and Control. LA, USA: New Orleans, 2007: 4590-4595.

[10] XUE Feng, LIU Zhong, SHI Zhang-song. Unscented particle filter for bearings-only tracking with out-of-sequence measurements in sensor networks[C]//Proceedings of the Sixth International Conference on Intelligent Systems Design and Applications. Wuhan: Naval Univ of Eng, 2006(2): 540-545.

(编辑 李向群)

收稿日期：2011-04-15；修回日期：2011-06-15

基金项目：国家自然科学基金资助项目(60674053, 61004023, 61074057)

通信作者：王岩(1975-)，女，黑龙江佳木斯人，副教授，从事网络控制、无线传感器网络研究；电话：010-82338691; E-mail: w-yan@buaa.edu.cn