基于能量高效动态分簇的目标跟踪算法

陆 娴,彭 勇

(江南大学物联网工程学院,江苏无锡214122)

基于能量高效动态分簇的目标跟踪算法

陆 娴,彭 勇

(江南大学物联网工程学院,江苏无锡214122)

目标跟踪是无线传感器网络中的一项基本应用,如何在保证高跟踪精度的前提下降低网络能耗、延长网络生命周期是目标跟踪的核心问题。为此,提出一种基于能量高效动态分簇的目标跟踪算法。从最大限度节省能量的角度出发,设计动态簇生成方法,利用无迹粒子滤波算法对目标进行跟踪,预测下一时刻目标的位置坐标,并根据预测结果给出簇头更换策略。仿真结果表明,与PPF和DPF算法相比,该算法不仅具有较高的目标跟踪精度,而且能有效降低网络能耗,延长网络寿命。

无线传感器网络;目标跟踪;无迹粒子滤波算法;动态分簇;接收信号强度指示模型;无迹卡尔曼滤波算法

1 概述

无线传感器网络(Wireless Sensor Network, WSN)由大量具有信息感知、采集、处理和无线通信能力的传感器节点组成[1]。由于传感器组成的网络具有自组织性、鲁棒性和隐蔽性等特点,使得无线传感网非常适合移动目标的跟踪,同时其也为目标跟踪技术提供了一种全新的解决方案和研究方向。

无线传感器网络有集中式和分布式 2种结构[2-3]。集中式跟踪[4]是全部参与目标跟踪的传感器节点将局部量测信息传送到计算中心,再由计算中心完成对目标的状态估计;分布式跟踪[5]是参与目标跟踪的传感器节点之间相互交换和协调局部量测信息,并在本地完成对目标的状态估计。前者结构简单但易使单个节点能量耗尽,导致网络节点分布不均匀而影响整个网络的跟踪性能;后者结构复杂但能均衡网络能耗,因此本文在分布式结构的基础上提出一种新的动态簇生成方法,从而降低网络能耗。

在通常情况下,目标跟踪系统是非线性非高斯的,并且大部分传统的目标跟踪算法存在对参数过于敏感的缺点[6-7],而粒子滤波不受线性化误差和高斯噪声假设的限制,适用于大多数环境下的状态转换或测量模型[8],因此粒子滤波算法应用在目标跟踪中的思想应运而生。虽然粒子滤波算法适合处理非线性非高斯系统的状态估计问题,但它存在着粒子退化的缺陷。针对粒子滤波的缺陷,目前处理较好的是无迹粒子滤波(Unscented Particle Filtering,UPF)算法,本文采用该算法来实现簇对目标的跟踪。

为进一步提高网络能量利用率、延长网络寿命,本文提出一种基于能量高效动态分簇的目标跟踪算法,设计动态簇生成方法和簇头更换策略,从而在确保较高跟踪精度的基础上,降低整个网络能耗。

2 模型与假设

2.1 网络模型

由于无线网络中的传感器节点受到资源限制和环境噪声的影响,因此为了更好模拟现实环境,本文采用了接收信号强度指示(Received Signal Strength Indications,RSSI)模型[9]。假设无线传感器网络中的传感器节点是随机部署在监测区域内的,并且每个传感器节点都装有接收信号强度指示器。感知节点可以通过接收的信号强度值来探测目标并估计自身到目标的距离。现假设运动目标在监测区域内运动,则在k时刻第i个传感器节点从目标接收的信号强度为:

2.2 目标运动模型

目标运动模型是跟踪算法的基础,跟踪的目的是估计出目标的状态。对于无线传感器网络中的单目标跟踪,本文采用状态空间模型来表示目标运动模型[9]:假设随机部署N个传感器节点在网络中,每个节点的位置坐标已知,为(xi,yi),i∈{1,2,…,N},则目标运动模型可以表示为:

其中,Xk为目标在k时刻的状态向量,Xk=(xk,yk,vx,k,vy,k)T;(xk,yk)为目标在k时刻的位置坐标; (vx,k,vy,k)表示目标在k时刻的速度;F为状态转移矩阵,即表示目标在k时刻与k+1时刻的状态转换关系;wk为系统噪声。

传感器节点对目标的观测方程为:

其中,Zk为k时刻节点对目标的观测向量;H为观测模型矩阵;vk表示观测噪声。

3 能量高效的动态分簇

3.1 新的动态簇生成方法

传统网络动态分簇的基本思想是[10]:当多个感知节点检测到运动目标时,感知节点之间通过相互交换信息选取出离运动目标最近的节点作为簇头,并以簇头为中心,簇头最大通信距离为半径的范围内的所有感知节点组成一个簇。虽然传统动态簇结构可以降低网络能耗,但并不是一种能量高效的方法,并没有最大限度的节省网络节点能量。传统动态分簇方法易产生对运动目标跟踪无实际贡献的感知节点仍处于工作状态而浪费能量的问题,从而使得网络能量利用率低,如图1所示。其中,L为感知节点跟踪目标达到跟踪精度要求的一个距离阈值;D为簇头到运动目标的距离;R为簇头节点最大的通信半径,以簇头为中心;R为半径的圆内所有的感知节点组成一个簇。

图1 传统动态分簇策略

可以看出,节点1～节点4到运动目标的距离超过了阈值L,这些节点实质上对目标的跟踪无意义,甚至会降低跟踪的精度。从节省能量的角度出发,这些节点也不应该处于工作状态,浪费能量。文献[11-12]是通过设定阈值来降低能耗的,但阈值的选取本身就有难度,取得偏大或偏小都会影响跟踪性能,针对以上问题,本文提出了新动态簇生成方法。

新动态簇生成方法使得对目标跟踪无实际贡献的感知节点不被划分在动态簇内,从而节省网络能量。该方法设计思路如下:当运动目标进入监测区域时,多个感知节点均能检测到运动目标,感知节点间通过相互交换信息,选取出从运动目标接收的信号强度最大和次大的节点作为主簇头和次簇头,再分别以主簇头和次簇头为中心,感知节点的最大通信距离为半径,作2个圆,最后使两圆的相交区域内的所有感知节点组成一个簇,如图2所示。其中,S1为主簇头从目标接收的信号强度;S2为次簇头从目标接收的信号强度;R为网络中感知节点的最大通信半径;虚线表示的区域为以S1,S2为中心,R为半径的两圆的交集,该区域内的所有感知节点组成一个簇,该簇使得跟踪节点只占所有能探测到目标节点的一部分,从而减少了无贡献节点的能耗和通信能量。

图2 动态分簇方法示意图

上述新的动态分簇方法从节省能量的角度避免了在目标跟踪过程中无实际意义的感知节点仍处于工作状态的问题,生成了一个能量高效的动态簇结构。该结构使得跟踪节点只占所有能探测到目标节点的一部分,降低了跟踪簇的能量消耗,从而提高了整个网络的能量利用率,同时在一定程度上也提高了跟踪精度。

3.2 簇头更换策略

假设在时刻k,动态簇结构为:

Cluster(k)={FCH(k),SCH(k),cn1,cn2,…,cnn}其中,FCH(k)为主簇头;SCH(k)为次簇头;其余节点为簇内成员,当簇结构处于跟踪状态时,次簇头等同于普通簇成员。在目标跟踪时,簇内各成员节点分别利用UPF算法估计目标的状态信息,并把估计结果传递给主簇头节点,主簇头对这些数据进行融合,估计出目标的位置坐标和运动速度等状态信息,并预测出k+1时刻目标的位置坐标,最后根据预测的位置值决定簇头节点是否更换。

假设预测的目标位置坐标为Tk+1(Txk+1,Tyk+1),则根据以下规则来更新簇头:

规则1 如果Tk+1既位于主簇头的覆盖范围之内,又位于次簇头的覆盖范围之内,则不更新主簇头和次簇头,仍在当前簇内对目标进行跟踪。

规则2 如果Tk+1位于主簇头的覆盖范围之外,则不考虑预测的目标位置与次簇头的关系,直接唤醒与k+1时刻目标位置最近和第二近的节点,作为新的主簇头节点FCH(k+1)和次簇头节点SCH(k+1),并按3.1节介绍的方法重新构建簇结构,选择新的簇成员节点。同时当前主簇头FCH(k)将当前时刻的跟踪参数传递给新的主簇头节点FCH(k+1)。

规则3 如果Tk+1位于主簇头的覆盖范围之内但位于次簇头的覆盖范围之外,则不更换主簇头,但要更新次簇头,以及重新构建簇结构。即唤醒在主簇头覆盖范围内离目标位置最近的节点作为新的次簇头节点SCH(k+1),并按3.1节介绍的方法生成新簇来更新当前簇结构。新的簇结构在k+1时刻对目标进行跟踪。

图3给出了簇头更换策略的具体情况,其中,图3(a)表示规则1发生的情况;图3(b)表示规则2发生,主次簇头更换的情况;图3(c)表示规则3发生,次簇头更新的情况。

图3 簇头更换策略示意图

本文给出的簇头更换策略能随着目标的运动,及时地更新簇头和选择新的簇成员节点,从而能够对目标进行准确、连续的跟踪。

4 动态分簇目标跟踪算法

上文详细论述了能量高效的动态分簇方法,本节重点介绍基于该方法的目标跟踪算法。由3.1节生成的动态簇采用UPF算法对目标进行跟踪。UPF算法[13-14]利用无迹卡尔曼滤波(Unscented Kalman Filtering,UKF)算法[15]产生重要性分布函数来改进粒子滤波,从而得到更为接近真实结果的后验概率分布。

假设k时刻分配到簇成员节点i上的粒子数目为N,Xj表示粒子j的状态值,Wj为粒子j的权值,Zj表示粒子j的观测值,则动态分簇目标跟踪算法具体实现流程如下:

(1)初始化

假设k=0时刻,目标进入传感器网络,网络中检测到该目标的感知节点通过相互交换信息选取出主簇头和次簇头,并按3.1节介绍的方法生成簇。在簇处于跟踪状态时,次簇头节点等同于普通簇成员节点,探测目标并将数据传递给主簇头。假设当前簇内有n个成员节点,主簇头节点分配给每个成员节点的粒子数目为N,则有:

(2)粒子重要性采样

从重要性分布函数中抽取粒子,即新样本:

计算k时刻每个粒子的权值:

(3)成员节点状态估计

第i个成员节点根据得到的新样本的序列和样本权值分别计算出N个样本的加权和、协方差以及权值和:

(4)节点信息上传

(5)重采样

如果有效粒子数低于指定阈值时,则重采样粒子集,各成员节点收到重采样消息后,独立进行采样过程:

(6)簇头节点数据融合

主簇头将每个簇成员节点传送来的状态信息进行融合处理:

(7)预测k+1时刻的目标位置

主簇头节点在完成数据融合后,计算k+1时刻目标位置的预测值xk+1|k:

(8)簇的动态更新

主簇头节点根据预测的目标位置值xk+1|k和3.2节介绍的簇头更换策略来判定簇是否需要更新。如果簇结构不需要更新,转到步骤(2)继续在当前簇内对目标进行跟踪,否则更换主次簇头节点并在新建的簇结构内跟踪目标。同时,当前簇的主簇头节点将状态信息{xk,wk}传送给新的主簇头节点,并解散簇,簇成员节点关闭通信模块,转入休眠状态,新的簇在下一时刻对目标进行跟踪。

整个算法的框架如图4所示,其中,(Lx1,Ly1), (Lx2,Ly2)分别表示主簇头、次簇头的坐标。

图4 基于能量高效动态分簇的目标跟踪算法框架

5 仿真实验与结果分析

仿真实验中,仿真场景为在1 000 m×1 000 m的方形区域中随机部署200个传感器节点组成无线传感网,并假设网络中的所有节点具有相同的功能和性能,节点的通信半径为50 m。假设存在一目标节点,该目标运动符合2.2节介绍的模型,则目标节点X轴方向上的运动状态为:

Y轴方向上的运动状态为:

其中,t为采样间隔,取1 s;Xk-1′(t),Yk-1′(t)分别为X,Y方向上的状态更新方程;a(t),v(t)分别表示加速度和速度;ω取0.02;αk-1,βk-1为运动过程产生的噪声,其中αk-1～N(0,10),βk-1～N(0,5)。目标起始位置的状态向量为[x0,y0]=[600,100],传感器节点测量模型如 2.2节所述,测量噪声vk服从N(0,1)分布。

利用Matlab仿真工具对本文算法、分布式粒子滤波(Distributed Particle Filtering,DPF)跟踪算法以及并行粒子滤波(Parallel Particle Filtering,PPF)跟踪算法[16]进行仿真实验和对比。研究了目标跟踪过程中3种跟踪算法在不同步长和传感器节点个数下的跟踪精度和网络能耗,其中跟踪精度用平均均方根误差(Root Mean Square,RMS)[16]来描述。对于不同情况,本文分别进行50次仿真,然后对仿真结果进行统计,取平均值作为最后的结果。节点分布和目标轨迹如图5所示。

图5 节点分布和目标轨迹

在不同步长下,本文提出的算法与DPF和PPF算法在x,y轴上的误差对比如图6所示。其中,图6(a)表示x方向的误差对比;图6(b)为y方向的误差对比。可以看出,3种算法在x,y方向上的的估计误差整体上随着步长的增长而减小,但本文算法的估计误差明显小于其他2种算法。

图6 位置估计误差对比

图7为3种算法的均方根误差对比。可以看出,DPF算法的RMS误差值最大,本文算法的RMS误差值最小。在目标作直线运动时,本文提出的算法与PPF算法的RMS误差相差不大,但在目标转弯处,本文算法的RMS明显小于PPF算法,因而跟踪精度更高。

图7 均方根误差对比

图8所示是不同传感器节点个数下,不同算法的目标跟踪延迟时间对比。这几种算法的跟踪延迟时间均随着节点个数的增加而增长,但由图可见, DPF算法的反应时间呈指数增长,本文算法和PPF算法的反应时间呈线性增长。在同样的节点个数下,本文算法的平均反应时间是PPF算法的60%,是DPF算法的45%,因而节省了网络能量,提高了能量使用率。

图8 跟踪延迟对比

图9表示主簇头节点在不同传感器节点个数情况下的能量消耗对比。可以看出,本文算法、DPF算法和PPF算法的主簇头节点能量消耗均随着节点个数增加而增多,但本文算法的簇头能量消耗最少,这是由本文簇结构算法所引起的,相比于DPF的簇结构,本文算法减少了簇头与无贡献节点的通信量。PPF的簇头能耗与本文算法相差不大,是由其并行性所引起的。

图9 主簇头能量消耗对比

6 结束语

由于无线传感器网络中的传感器节点能量有限并且部署随机,因此如何获得高跟踪精度并且在高精度的基础上降低网络能耗,提高能量的利用率是WSN中目标跟踪的核心问题。本文针对该问题提出了一种基于能量高效动态分簇的目标跟踪算法,从动态簇生成方法和簇头更换策略2个方面对动态分簇算法进行了描述,并结合无迹粒子滤波算法对目标进行跟踪,从而提高了跟踪精度,降低了整个网络能耗。

[1] 王 殊,阎毓杰,胡富平,等.无线传感器网络的理论及应用[M].北京:北京航空航天大学出版社,2007.

[2] Sheng X,Hu Y H.Distributed ParticleFiltersfor Wireless Sensor Network Target Tracking[C]//Proc.of 2005 IEEE InternationalConferenceon Acoustics, Speech,and Signal Processing.Philadelphia,USA:IEEE Press,2005:845-848.

[3] Chen Weipeng,Hou J C,Sha L.Dynamic Clustering for Acoustic Target Tracking in Wireless Sensor Networks [J].IEEE Transactions on Mobile Computing,2004, 3(3):258-271.

[4] Djuric P M,Vemula M,Bugallo M F.Target Tracking by Particle Filtering in Binary Sensor Networks[J]. IEEE Transactions on Signal Processing,2008,56(6): 2229-2237.

[5] 邓克波,刘 中.基于无线传感器网络动态簇的目标跟踪[J].兵工学报,2008,29(10):1197-1202.

[6] Baggio A,Langendoen K.Monte-Carlo Localization for MobileWirelessSensorNetworks[J].Ad Hoc Networks,2008,6(5):718-733.

[7] Míguez J,Artés-Rodríguez A.Particle Filtering Algorithms for Tracking a Maneuvering Target Using a Network of Wireless Dynamic Sensors[J].EURASIP Journal on Applied Signal Processing,2006,2006:1-16.

[8] 张军辉.粒子滤波跟踪算法研究[D].开封:河南大学,2009.

[9] Teng Jing,Snoussi H,Zhou Rong,et al.Distributed Variational Filtering for Simultaneous Sensor Localization and Target Tracking in Wireless Sensor Networks[J].IEEE Transactions on Vehicular Technology,2012,61(5):2305-2318.

[10] 李 迅,李洪峻.基于簇结构的无线传感器网络移动目标精确跟踪[J].传感技术学报,2009,22(12): 1813-1817.

[11] 刘立阳,张金成,吴中林.基于分布式动态簇结构的WSN自适应目标跟踪算法[J].传感技术学报,2012, 25(1):111-113.

[12] 林金朝,李国军,周晓娜,等.基于动态能量管理的无线传感网络动目标定位跟踪方法[J].通信学报, 2010,31(12):91-93.

[13] Payne O,Marrs A.An Unscented Particle Filter for GMTI Tracking[C]//Proc.of 2004 IEEE Aerospace Conference.[S.l.]:IEEE Press,2004:1869-1875.

[14] Rui Yong,Chen Yunqiang.BetterProposalDistributions:Object Tracking Using Unscented Particle Filter [C]//Proc.of 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.[S.l.]: IEEE Press,2001:786-793.

[15] Angrisani L,Baccigalupi A,Meriel-lo R S L.On the Use of Unscented Kalman Filter for Improving UItrasonic Timeof-flight Measurement[C]//Proc.of Instrumentation and Measurement Technology Conference.Ottawa,Canada: [s.n.]:17-19.

[16] 屈剑锋,柴 毅,郭茂耘.无线传感器网络下的并行粒子滤波目标跟踪算法[J].电子科技大学学报,2011, 40(2):232-233.

编辑 金胡考

Target Tracking Algorithm Based on Energy-efficient Dynamic Clustering

LU Xian,PENG Yong
(School of Internet of Things Engineering,Jiangnan University,Wuxi 214122,China)

Target tracking is a basic application in Wireless Sensor Network(WSN).It is a core problem to make a high tracking precision with low energy consumption and prolong the network’s life cycle.Aiming at this problem,a target tracking algorithm based on energy-efficient dynamic clustering is proposed.It firstly presents a new method of generating the dynamic cluster from the view of greatly saving energy.Then,the generated cluster structure uses the Unscented Particle Filtering(UPF)algorithm to track the target and predict the location coordinates in next moment. Finally,according to the predicted results,this paper puts forward a cluster head replaced policy.Simulation results show that,compared with PPF algorithm and DPF algorithm,this algorithm not only has higher target tracking precision,but also effectively reduces the network energy consumption and extends the network lifetime.

Wireless Sensor Network(WSN);target tracking;Unscented Particle Filtering(UPF)algorithm;dynamic clustering;

Signal Strength Indications(RSSI)model;Unscented Kalman Filtering(UKF)algorithm

1000-3428(2014)10-0098-06

A

TP393

10.3969/j.issn.1000-3428.2014.10.019

江苏省交通运输厅基金资助项目(2012X08-2)。

陆 娴(1988-),女,硕士研究生,主研方向:WSN目标定位与跟踪;彭 勇,副教授。

2013-10-08

2013-11-28E-mail:youmeiluxian@163.com

中文引用格式:陆 娴,彭 勇.基于能量高效动态分簇的目标跟踪算法[J].计算机工程,2014,40(10):98-103,108.

英文引用格式:Lu Xian,Peng Yong.Target Tracking Algorithm Based on Energy-efficient Dynamic Clustering[J]. Computer Engineering,2014,40(10):98-103,108.