一种基于EKF的双节点协作目标跟踪协议

1、小 型 微 型 计 算 机 系 统 2010年月第期journal of chinese computersystems vol. no. 2010一种基于ekf的双节点协作目标跟踪协议仝亮，陈兵(南京航空航天大学 计算机科学与技术学院，江苏 南京 210016)e-mail:tongliangnjit摘 要：无线传感器网络的目标跟踪应用中，动态跟踪组是一种有效的跟踪方式，但该方式下簇头的能耗较大，而且簇头失效易导致目标丢失。针对以上问题，本文提出一种双节点协作跟踪协议tnct，该协议通过簇头与辅助节点的协作实现目标变速时采样周期的自适应，以及簇头失效时的快速移交。为提高跟踪精度，辅助节点采用

2、ekf算法对目标轨迹进行估计和预测。仿真结果表明，tnct协议下跟踪系统的网络能耗更加均衡，目标丢失概率大大降低。关键词：无线传感器网络；目标跟踪；辅助节点；ekf中图分类号：tp393 文献标识码：a文章编号：a ekf-based two-node collaborative target tracking protocoltong liang, chen bing(college of computer science and technology, nanjing university of aeronautics and astronautics, nanjing 210016, c

3、hina)abstract: in the target tracking application of wsn, dynamic tracking group is an effective way, however, the energy consumption of the cluster head (ch) is relatively high in this tracking mode, and the failure of the ch easily leads to loss of target. to solve the problem above, a two-node co

4、llaborative tracking protocol (tnct) is proposed in this paper, by means of the chs collaboration with the auxiliary node, tnct implements the adaptive sampling period in response to the mutative speed of target, and the fast transfer of ch while its invalid. to improve the tracking accuracy, the ek

5、f algorithm is executed in the auxiliary node to evaluate and predict the targets trajectory. simulation results show that the tracking system using tnct achieves more balanced energy consumption, and the target loss probability is greatly reduced.key words: wsn; target tracking; auxiliary node; ekf

6、收稿日期：2011-9-12 作者简介：仝亮，男，1987年生，硕士研究生，主要研究方向是计算机网络；陈兵，男，1970年生，博士，教授，研究生导师，主要研究方向是计算机网络、通信与安全. 1 期仝亮等：一种基于ekf的双节点协作目标跟踪协议 51 引言移动目标跟踪是无线传感器网络中的一个重要课题，被广泛应用于环境监测、灾难预报和抢险救灾等诸多领域1。由于能量受限，单个传感器节点无法有效地跟踪目标，目标跟踪算法一般采用节点间的协同信号处理来定位各时刻目标位置。为了提高定位精度，当目标进入监测区域时需要唤醒多个节点进行目标监测，但若唤醒了不必要的节点，就会引起能量的额外开销2。因此，需要在跟踪精

7、度和能量消耗之间做出权衡，本文引进动态簇结构3作为跟踪组。动态簇结构是一种动态集中式的局部节点自组织方式，由动态产生的簇头和成员节点组成。在每个采样时刻，簇成员将感知数据发送给簇头，簇头进行数据融合。在目标离开簇头侦测范围后，按照一定规则产生新簇头。动态簇具有良好的灵活性和可扩展性，本文在此基础上提出一种基于预测机制的双节点协作跟踪协议，对簇头节点进行负载均衡和容错处理，在保持目标跟踪精度的前提下，降低能耗，减少目标丢失概率。2 研究现状目标跟踪是传感器网络研究的一个热点，国内外很多学者在该领域做了大量工作。按照跟踪目标的数量可以分为单目标跟踪和多目标跟踪，本文着重讨论单目标跟踪算法。文献4提

8、出了一种基于簇的目标跟踪算法cbot，该算法中各传感器节点自组织成簇并选举簇头，簇成员负责收集目标的位置信息，簇头负责数据融合并将处理结果发送给sink节点或基站。针对簇头负载问题，该算法提出各簇成员随机轮流担当簇头，以此来均衡簇间能量消耗，但cbot算法在簇头选举时未考虑能量因素，会导致低能量节点当选簇头死亡的情况。文献5设计了一种正方形簇状结构，处于方形中心的簇头发现目标时激活周围的8个簇成员进行目标定位跟踪。目标移动超出设定范围时，簇头按照距离目标最近原则指定新簇头，该方式省略了新簇头的选举过程，一定程度上减少了通信开销，但该算法对播种算法要求较高。文献6，7提出两种基于预测机制的目标跟

9、踪算法pes和dpr，在任意时刻仅当前节点对目标进行监测和预测，若当前节点预测目标将移动到其邻居节点探测范围内，唤醒邻居节点，自己进入睡眠状态。该算法的缺点是只有一个节点负责目标监测，跟踪精度无法保证，而且目标速度较快时容易发生丢失。针对目标丢失问题，文献8对目标丢失概率进行分析，提出一种唤醒半径自适应的节点唤醒机制来动态调整跟踪节点个数，从而减少目标丢失概率。本文重点在于对跟踪组的结构进行改进，提出一种新的簇状结构，使用扩展卡尔曼滤波算法9,10作为预测算法保证跟踪精度，通过辅助节点与簇头的协作进一步地均衡簇内能量消耗，延长网络生存周期，在目标加速或簇头失效时可以有效地降低目标丢失概率。3

10、tnct协议的提出与描述3.1 tnct协议的提出目标跟踪应用中，动态簇的簇头是重要的节点，它需要负责簇的维护以及目标探测信息的融合和提交。在基于预测机制的跟踪算法中，簇头还需要运行计算量较大的预测算法来提高跟踪精度，能量消耗较大，能量耗尽或节点故障均会导致簇头失效，此时若目标速度较快，则容易导致目标丢失。因此本文提出一种基于扩展卡尔曼滤波的双节点协作跟踪协议tnct，针对簇头的能耗以及失效问题进行负载均衡和冗余备份。同时为了解决目标变速问题，本文提出一种基于ekf目标位置估计的目标速度预测方法。3.2 tnct协议的描述tnct协议采用gaf11算法进行分簇，将监测区域划分为若干虚拟单元格，

11、将节点按照位置信息划入相应的单元格。每个单元格中选举一个节点作为虚拟簇头，它负责监测目标是否进入单元格，其他节点进入睡眠状态以节省能量。目标进入某单元格时，虚拟簇头以r/2(r为节点通信半径)为半径唤醒邻居节点进行簇头选举，在tnct协议中，簇头的能耗负载较轻，因此簇头选举原则为距离目标最近的节点成为簇头。tnct协议对动态簇的结构进行了改进，从簇成员中选取辅助节点与簇头进行协作跟踪。tnct协议主要包含辅助节点选择，双节点协作跟踪算法以及跟踪组容错机制，下面对跟踪协议的各组成部分进行详细描述。3.2.1 辅助节点选择为实现目标跟踪，簇头需要维护所在虚拟网格的节点信息，包含节点编号，节点状态，

12、节点坐标，剩余能量和感知目标距离。节点状态集合status=ch，an，cm，idle，sleep，dead，分别对应节点的簇头状态，辅助节点状态，簇成员状态，等待状态，睡眠状态和失效状态。节点处于ch、an和cm状态时激活所有功能模块，idle状态下节点仅开启感知模块，sleep状态下节点关闭所有功能模块，dead状态表明节点由于能量耗尽等原因导致无法正常工作。节点的状态转换以及相应的触发事件如图1所示。图1 节点状态转换图 fig.1 the state transition of nodes触发节点状态转换的事件集合e=e1，e2，e3，e4，e5，e6，e7，e8，e9，e10，其中e

13、1=节点满足簇头条件；e2=节点满足簇成员条件；e3=节点接收到簇头的辅助节点任命消息；e4=目标移动超出节点探测阈值，退出动态簇；e5=目标移动超出簇头探测阈值，触发簇头移交过程；e6=节点不满足簇成员条件；e7=节点收到唤醒消息；e8=簇头移交后，节点仍满足新簇的成员要求；e9=簇头失效，辅助节点成为新簇头；e10=节点能量耗尽。辅助节点承担ekf算法和目标变速自适应算法的执行，需要与ch进行数据交互完成协作跟踪，因此节点的剩余能量以及与ch间的距离是辅助节点选择的关键因素，使用能效指数来衡量节点担任辅助节点的优劣，t时刻节点的能效指数定义如下：（1）其中，由上式可知，因此可以使用能效指数

14、作为节点担任辅助节点的概率。设t时刻动态簇的辅助节点为s，s的能效指数需满足以下条件： （2）其中为t时刻ch的n个簇成员的集合；表示节点的剩余能量；表示节点与ch的距离，其中是ch位置坐标，是节点位置坐标。，是权重系数，分别体现剩余能量和距离在辅助节点选择中的重要程度。缩短ch与辅助节点间的距离可以降低通信开销，然而各成员与ch距离差别较小，而且辅助节点负载计算任务，能耗较高，依据能量优先的原则设定。两者的值经过多次试验动态调整，本文取=0.8, =0.2。3.2.2 双节点协作跟踪算法辅助节点使用ekf算法对目标状态进行估计和预测。ekf算法提供一种高效可计算的方法来估计过程的状态，并使估

15、计均方误差最小。ekf只需保存前一时刻状态的后验估计，当观测到新数据时，通过过程的状态转移方程即可算出新的估计量。为简化ekf算法的复杂度，本文采用p(position)模型来表示目标的状态向量，目标动态系统离散线性化后的近似状态方程为（3）式中为第个采样时刻的目标状态向量；为节点采样周期，；为状态转移矩阵；为模型噪声。令，其中表示时刻目标位置。假定在时刻观测节点为，测量方程为（4）其中是测量函数；为测量噪声；为节点观测的目标位置向量。假定和相互独立且服从零均值白高斯分布，其协方差矩阵分别为和。已知时刻目标状态的后验估计为，协方差矩阵为，时刻目标状态及其协方差的先验估计分别为 （5）（6）假定

16、时刻节点的测量向量为，测量向量的预测值为，定义测量向量的一步预测误差为 （7）其协方差可表示为 （8）其中表示测量函数在时刻对求偏导后的雅克比矩阵。引入上述测量函数，可以获得ekf的测量更新方程如下 （9） （10） （11）式中为增益矩阵；和分别表示状态向量和协方差矩阵在时刻的后验估计。tnct跟踪算法使用ekf对目标的位置和速度进行预测和估计，在跟踪过程中需要着重考虑两个问题：跟踪组簇头何时移交，跟踪算法如何适应目标速度的变化。1) 簇头移交时刻，簇成员对目标进行测距，将探测距离发送给簇头，探测消息包含节点编号和探测距离。簇头使用三边测量法(trilateration)计算目标位置估计，将

17、发送给辅助节点，辅助节点执行ekf算法，通过公式(10)(11)对时刻目标位置的先验估计进行滤波，更新后的后验估计为，通过公式(5)(6)计算时刻目标位置的先验估计，假设时刻簇头的位置向量为，节点的探测半径为d，辅助节点作以下判断：若，表明目标在时间内位置变动较小，辅助节点无需向sink节点提交时刻的目标位置信息，是决定辅助节点是否提交更新数据的阈值，合理地设置该阈值可以在目标减速或静止时降低跟踪组的通信开销。若，表明目标将移出簇头的有效探测范围，需要选择一个更优的节点作为新簇头组建动态簇。此时，辅助节点向簇头发送移交消息，消息包含，和。簇头接收到移交消息后，唤醒附近节点，将跟踪信息发送给新簇

18、头节点，在接收到新簇头的目标发现消息后，向簇成员节点发送簇解散消息，簇成员接收到解散消息后转入sleep状态。2) 目标变速的处理目标在移动过程中可能会变速，跟踪组若采用固定的采样周期，则会出现以下问题：目标加速时，若在下一个采样时刻到来之前移出节点探测范围，则会导致目标丢失；目标减速或静止时，节点仍按照原先的采样周期测距则会造成跟踪组不必要的能耗开销。tnct提出一种速度自适应的机制，对目标平均速度进行估计、预测，动态调整跟踪组的采样周期。定义目标在时间内的平均速度为 （12）定义目标在时间内的预测平均速度为 （13）定义一步预测速度增长率为 （14）表示辅助节点预测目标将加速，表示预测目标

19、将减速。依据实验经验，当时，跟踪组需要及时调整采样周期以适应目标变速所产生的影响，按照公式(15)计算跟踪组新的采样周期，并向簇头发送目标变速消息，变速消息包含新的采样周期。簇头将该消息转发给各成员节点，动态组按照新的采样周期对目标进行探测。 （15）3.2.3 跟踪组容错机制在目标监测过程中，由于电源耗尽或其他原因，监测节点会意外死亡，这将导致目标跟踪精度降低甚至目标丢失。跟踪组容错机制可以有效地降低跟踪节点死亡所产生的影响，保证跟踪的持续性。wsn中通常采用周期发送心跳消息和增加冗余节点的方式实现节点容错，tnct协议提出一种轻量级容错机制，即只对簇头和辅助节点进行容错处理。该机制执行如下

20、步骤：1) 簇头选择辅助节点后向其发送簇头备份消息，该消息包含簇头当前维护的节点信息列表和当前采样周期。2) 辅助节点启动一个长度为的定时器timer_an，若在定时器超时前未收到簇头的目标测距消息，则认为簇头失效，否则重置该定时器。判定簇头失效后，辅助节点向节点列表中状态为cm的节点发送簇头变更消息，辅助节点成为新簇头。 3）簇成员加入或退出时，簇头更新节点信息列表，并向辅助节点发送成员变更消息，消息包含节点编号，节点状态，接收到该消息后，辅助节点更新备份的节点信息列表。4） 簇头节点在发送完目标测距消息后，启动一个长度为2.5的定时器timer_ch，若在定时器超时前未接收到辅助节点的目标

21、位置估计更新消息，则认为辅助节点失效，否则重置timer_ch。目标位置估计更新消息包含目标当前的位置估计和协方差估计。判定辅助节点失效后，簇头使用公式(1)(2)选择新的辅助节点，向其发送前一采样时刻目标位置估计和协方差估计。4 协议仿真与性能分析为验证tnct协议在跟踪精度和能量消耗上优于其他基于簇的跟踪算法，我们将其与cbot和pes算法进行比较，分析tnct协议的跟踪优势。仿真实验环境为omnet+4.1，mixim2.1。移动目标使用一个具有移动特性的节点表示，仿真参数设置如表1所示。表1 仿真参数设置表table1 simulation parameter名称参数值名称参数值区域大

22、小300*300sink节点位置(0,0)节点个数300辅助节点选择时, = 0.8 = 0.2节点初始能量2j采样周期调整时0.5节点感知半径d15m初始采样周期1sec节点通信半径r30m数据提交阈值1m目标速度0-30m/s发射电路能量消耗50nj/bit1) 网络能量消耗首先本文对tnct协议的能量消耗进行了比较分析。图2为在300个节点的情况下，tnct与cbot和pes算法的平均网络能量消耗对比情况。从图中可以看出，tnct协议的平均网络能耗低于pes算法，pes能耗低于cbot算法。随着仿真的推进，tnct的能耗优势更加明显。tnct协议通过辅助节点预测目标下一时刻位置来唤醒跟踪

23、节点，并且在目标减速时延长采样周期，因此网络能耗较低。图2 节点平均能量消耗对比图fig.2 comparison of average energy consumption图3为tnct与cbot和pes算法的死亡节点个数比较，tnct中的辅助节点负载了簇头节点的数据计算和数据提交任务，因此动态簇的能耗负载更加均衡，首个死亡节点出现时间也较cbot和pes算法晚。图3 死亡节点个数对比图fig.3 comparison of dead nodes2) 目标速度预测其次本文对tnct协议的目标速度预测进行了分析。目标在移动过程中，速度在030m/s范围内变化。图4为目标真实速度和tnct预测速

24、度的对比情况，由于tnct速度预测方法是基于ekf算法的目标位置预测值，因此在目标变速时，速度预测值波动较大，目标恒速时，误差值较小，且预测值较平稳。图4目标速度预测值与真实值对比图fig.4 comparison of speeds estimate and real value3) 目标丢失最后本文对tnct协议下目标丢失次数与cbot和pes算法进行了分析比较。图5为目标在不同速度下三种算法的目标丢失次数对比图。从图中可以看出目标速度在15m/s之后cbot和pes算法的丢失目标次数增幅较大，而tnct则基本平稳。自适应的采样周期以及跟踪组容错机制是tnct协议能够适应速度较高的目标跟踪

25、应用的主要原因。图5目标丢失次数对比图fig.5 the comparison diagram of target loss5 结束语在基于传感器网络的分布式目标跟踪系统中，跟踪精度和网络能耗是设计跟踪算法时需要考虑的两个关键问题，本文在扩展卡尔曼滤波算法的基础上提出一种双节点协作跟踪协议tnct，对跟踪组的结构进行改进，辅助节点的设计使得跟踪组的负载更加均衡，延长了网络生存周期；基于ekf位置估计的速度预测方法使得跟踪组可以及时地调整采样周期，很好地解决了目标加速导致的跟踪丢失问题。references:1 sun li-min, li jian-zhong, chen yu,et al.

26、wireless sensor networksm. beijing:tsinghua university press, 2005.2 aysegul alaybeyoglu, orhan dagdeviren, aylin kantarci,et al. a distributed wakening based target tracking protocol for wireless sensor networksc. ninth international symposium on parallel and distributed computing, 2010,33:165-172.

27、3 wang wei-dong, zhu qing-xin. a hierarchical clustering algorithm and cooperation analysis for wireless sensor networksj. journal of software, 2006,17(5) :57-67.4 w.r.heizelman, a.chandrakasan, h.balakrishnam. energy efficient communication protocol for wireless microsensor networksc. proceedings o

28、f the 33rd hawaii international conference on system sciences,2000,2:1110-1120.5 a.manaviat, m.fathy, m.nikzad. tracking a mobile target using bright square in wireless sensor networkc. 2rd international conference on future computer and communication,2010,2: 208-214.6 xu ying-qi, julian winter, wang-chien lee. prediction-based strategies for energy saving in object tracking sensor networksc. proceedings of the 2004 ieee international conference on mobile data management,