一种基于预测策略的目标跟踪算法研究*

任 静，熊庆宇，石为人

(重庆大学自动化学院，重庆 400030)

无线传感器网络由于节点体积小、能耗低、隐蔽性好等优点［1］，非常适合用于移动目标的跟踪［2］。但是由于其节点能量有限，要求在保证跟踪精度的同时还要考虑其它因素，例如网络生存时间［3］、能量消耗等。传感器节点的计算能力和存储能力有限要求我们在设计算法时要平衡网络生存时间和能量有限，高精度和低计算能力［4］之间的关系。基于测距的定位算法［5］可以得到较精确的目标位置，它是根据一些属性模型得到节点和目标之间的距离，这些往往不是它们之间的真实距离，容易造成积累误差。

目前用于目标跟踪的预测方法主要有粒子群滤波、卡尔曼滤波［6］等，这些方法的共同特点就是需要大量的数据迭代计算，适合于集中式系统，不适合在资源有限的传感器节点上进行。在某一时刻移动节点不可能全部被节点感知到，而且距离移动目标近的节点感知信号强度［7］要比距离移动目标远的节点的感知强度大，本文提出了一种基于预测策略的目标跟踪算法。该算法采用静态网格网络结构，当目标进入监控区域后，节点携带的震动传感器感知到目标，簇头节点根据节点检测目标信号强度值来计算目标位置，目标位置计算采用一种基于检测信号强度的加权质心定位算法;簇头节点根据目标移动的已知信息来预测移动目标未来的位置，利用分段线性拟合的思想，将整个网络的轨迹预测分为簇内预测以及相邻簇间的预测，降低了目标预测的计算时间复杂度;当跟踪簇头节点发现目标丢失，根据传感网络结构提出了目标恢复机制。

1 目标跟踪算法

1.1 算法思想

本文论述的无线传感器网络系统是采用静态分簇网络结构。整个监控区域被划分成不同的虚拟单元格，每个节点根据自身地理位置信息被划分到不同的单元格。监控区域的节点被分成边界簇头节点、簇头节点和簇内节点，每个节点都有三种状态即跟踪状态、侦测状态和睡眠状态。每个传感器节点携带振动传感器，当移动目标进入到监控区域时，节点便可监测到信号能量强度。

目标跟踪流程图如图1所示。

图1 目标跟踪流程图

算法的具体实现步骤:

步骤1网络初始化 整个监控区域被划分成不同的虚拟单元格，每个单元格称为一簇。在没有跟踪任务时，监控区域只有边界簇头节点处于侦测状态，其余节点则处于睡眠状态，每个边界簇每隔一段时间更新一次簇头节点。

步骤2目标跟踪 当边界簇头节点侦测到未知目标出现时，激活其簇内节点对目标进行定位计算，边界簇头节点根据其簇内节点发回的信息计算未知目标的位置信息和路径，从而预测目标下一时刻的位置并唤醒附近节点继续跟踪。

步骤3下一时刻节点的唤醒 当未知目标运动区域超出一簇监控范围时，簇头节点计算目标下一时刻的位置信息并通知相应簇头节点启动跟踪，休眠当前簇头节点及监测信号强度值低的节点。

步骤4 目标恢复 如果目标意外丢失，则启动相应的恢复唤醒机制。

1.2 目标定位

目标信号的强度是随着传输距离的增加而呈指数衰减的［8］，当目标进入监控区域后，节点i在t时刻的采样信号强度值ei(t)可用式(1)所示:

式中:s是目标信号源的强度;α是信号强度的衰减指数(α约等于2);di(t)是t时刻节点i与跟踪目标之间的距离;ni～N(0，σ2)是测量噪声，可近似为高斯白噪声。由式(1)可知，当目标经过节点i时，一般是一个由远到近再到远的过程，同一节点在不同时刻监测到的信号强度值也是不相同的。同理，在同一时刻不同节点所监测到的信号强度值也是不相同的。当检测强度值大于某一阈值时，便可参与到定位计算中。

信号峰值意味着此时目标位于距离节点i最近，i所对应的信号强度值ei(t)也为最大。据此，本文提出了基于检测信号强度值的目标位置定位算法，基本思想是:跟踪节点检测到目标强度值相互之间的比值之和作为加权质心定位算法的加权值。具体表述为:设目标在t时刻的位置为L(xt，yt)，此时监控区域有n个参考节点(n≥3)，这些节点的坐标分别为{(x1，y1)，(x2，y2)…(xn，yn)}，t时刻这些节点检测到的目标信号强度分别为e1(t)，e2(t)…en(t)。根据检测到的目标信号强度对跟踪节点进行从大到小排序，并选取前k个(3≤k≤6)跟踪节点建立参考节点集合，G={(x1，y1)，(x2，y2)…(xk，yk)}。它们彼此互相独立，各个跟踪节点的加权因子分别为w1，w2…wk，则加权质心定位计算得到的跟踪目标在t时刻的位置L(xt，yt)为:

定义Bij为t时刻，跟踪节点i，j分别检测到的目标信号强度值的比值，即:

定义权值为:

根据权值信息，代入到式(2)中即可得到跟踪目标在t时刻的位置。

1.3 目标位置预测

目前用于目标跟踪的预测方法主要有粒子群滤波、卡尔曼滤波等［9－10］，这些方法的共同特点就是需要大量的数据迭代计算，对节点的处理模块要求比较高，不适合应用在资源有限的传感器节点上。本文利用分段线性拟合［11］思想，把目标在监控区域的运动分为在若干个簇内的运动，假设目标在一簇内做直线运动，设目标进入当前簇的起始位置为L(xk，yk)，下一时刻的感知位置坐标为(xk+1，yk+1)，采样间隔时间为Δt，则在初始感知目标的速度vk和加速度ak如式(5)、式(6)所示:

目标的运动速度和方向决定了目标在当前簇内的停留时间和移动距离，设目标在当簇内感知到m个位 置 信 息 为 (xk，yk)，(xk+1，yk+1) … (xk+m－1，yk+m－1)，利用目标的这些位置信息可以构建目标做直线运动的直线方程y=ax+b，由最小二乘法求直线方程的参数a和b的值。设当前目标跟踪簇的簇头节点为坐标原点，当前监控区域边界曲线方程如式(7)所示:

tstqv是移动目标在当前簇的停留时间，如式(9):

根据以上预测数据，当前跟踪簇的簇头节点在一定的时间内唤醒边界节点进行目标跟踪。如果移动目标的运动范围超出了当前簇的监控范围，则目标在当前簇的最终位置作为相邻簇的初始位置，唤醒预测邻居簇头节点启动跟踪任务。

1.4 目标恢复机制

由于目标的运动速度、方向存在一定程度的误差并且在预测时间内，目标的一些运动特性会突然发生较大的改变，致使目标离开当前的监控区域，这种现象称作是目标丢失，为了能够快速的重新跟踪目标，我们提出了一种有效的目标恢复唤醒算法。

目标丢失检测 被唤醒的节点检测到目标时会向前一监控节点发送确认消息，否则在一周期内没有发现目标则自动进入睡眠状态，如果前一监控节点在规定时间内没有收到唤醒节点发送的确认消息，则表明目标丢失，启动目标恢复机制。

目标恢复 目标恢复分为两个过程，首先当前跟踪簇头节点洪泛命令，唤醒其簇内所有节点搜索其监测范围内的所有目标信息，所有当前簇内节点在一个周期内上传其检测信息，若当前簇头节点监测到移动目标，则休眠不相关节点继续进行跟踪;若没有发现目标说明移动目标已经离开当前簇，当前簇头节点休眠其簇内节点并且洪泛消息到一跳范围的相邻的簇头节点，相邻簇头节点再启动搜索任务。

2 算法仿真分析

为了验证本文算法的有效性以及在定位精度和目标丢失率方面的优势，利用MATLAB软件对本文算法进行仿真实验。仿真场景的基本设置为:400个节点随机分布在100 m×100 m的二维监控平台，节点的传输半径R=30 m，从文献［12］可以知道簇的半径与传感器节点传输半径之间的关系，如式(10)所示，可以计算出当前监控区域半径r的范围。

各个节点根据其地理位置信息被划入分成半径为8 m的监控区域。目标信号源强度s=100，衰减指数 α=2，噪声分布ni～N(0，σ2)，检测阈值e0=1，目标做直线运动，其中v=10 m/s，a=±cos(t)m/s2。仿真分别对本文算法、基于预测策略的能量高效目标跟踪算法(PES)［13］和基于无线传感器网络动态簇的目标跟踪算法［14］进行了10次仿真，跟踪性能对比图如图2～4所示，图中的数据为对应参数10次仿真所得结果的平均值。

首先对本文提出的目标定位算法与质心算法，DV-Hop算法进行了对比，分别对其进行五次仿真，每次的仿真定位误差方差如下表1所示。

表1 本文、质心、DV-Hop定位误差

分析表1可知，由于受到许多不确定性的干扰，质心算法和DV-Hop算法的定位误差较大，而本文定位算法精度比较高，这是由于本文算法中的加权值充分利用了各个位置检测目标信号强度值，使离目标近的节点在目标位置中的权值大，与目标距离远的节点在目标位置结算中所占的权值小，其结果更接近目标的真实位置。

图2显示了本文算法跟踪目标的结果，并与基于预测策略的能量高效目标跟踪算法(PES)进行了对比，结果显示，两种算法都能够很好的近似模拟目标实际运动轨迹，特别是当目标做直线运动时，算法基本和目标运动轨迹吻合;但当目标突然改变方向时，PES算法由于只有一个节点跟踪目标，所以在目标突然改变方向时不能够很好的做出反应，实时性比较差，而本文算法有多个节点协作跟踪目标，能比PES以更快的速度做出改变，从而实时跟踪目标。本文的定位算法能够很好的计算出移动目标位置，采用基于分段线性拟合预测策略很好的拟合了目标的运动轨迹，拟合度较高。

图2 曲线轨迹跟踪结果

图3所示为目标丢失率随着速度的增加而变化的曲线，目标丢失率是指在跟踪过程中，无效的定位次数在本次目标跟踪中总的定位次数的比值。

图3 目标丢失率对比图

从图3可以看出，当目标运动速度较低时，三种算法都比较稳定，目标丢失率比较低;随着目标运动速度的增加，尤其是当目标运动速度达到15 m/s时，PES算法由于无法快速唤醒节点导致其目标丢失率显著增加，动态簇算法和本文算法都能较好的适应速度的变化，目标丢失率变化不大，本文算法由于采用了静态分簇以及合理的目标恢复机制，当目标丢失时能够迅速找到目标，从而降低目标丢失率。

图4所示为分别对PES算法，动态簇算法和本文算法随速度变化的能耗进行了仿真，由于动态簇算法组簇的能耗比较大，所以虽然目标运动速度较慢，但是能耗依然较大;但随着速度的增大，PES算法的目标丢失率相应增大，找回目标所需的能耗更大。从图中可以看出本文算法能耗随速度的变化比较稳定，这可以说明本算法采用的节点调度机制能够在不影响跟踪精度的同时减少能耗。

图4 能量消耗对比图

3 结论

目标跟踪是无线传感器网络主要应用之一，同时也是目前传感器网络研究的重要课题。本文在提出的网络结构基础上，提出了基于加权质心算法的目标位置计算方法，可以在不增加计算量的情况下提高目标跟踪的精度。针对其他预测方法需要大量的数据迭代计算，改进了分段线性拟合预测方法，算法仿真结果表明该算法可以很好的预测目标的位置，降低目标丢失的概率，另外目标丢失时，还给出了目标意外丢失时的目标恢复机制，从而进一步减低目标丢失率。

［1］孙利民，李建中，陈渝，等.无线传感器网络［M］.北京:清华大学出版社，2005:8－10.

［2］Guojun Wang，Huan Wang，Jiangnong Cao，et al.Energy-Efficient DualPrediction Based Data Gathering for Environmental MonitoringApplications［C］//IEEE Communication Society subject matter experts for publication in the WCNC 2007 proceedings:3516－3521.

［3］Bhattacharya A，Das S K.Lezi-Update:An Information Theoretic Framework for Personal Mobility Tracking in PCS Networks［J］.ACM/KluWer Journal on Wireless Networks)，March－May 2002，8(2－3):121－135.

［4］Jeongkeun Lee，Kideok Cho，Seungjae Lee.Distributed and Energy-Efficient Target Localization and Tracking in Wireless Sensor Networks［J］.Computer Communications，2006，(29):2494－2505.

［5］任倩倩，李建中，李金宝，等.无线传感器网络中一种能源有效的移动对象跟踪方法［J］.通信学报，2009，30(4):50－59.

［6］Lee W C，Xu Y.On Localized Prediction for Power Efficient Object Tracking in Sensor Networks［C］//Proceedings of the 23rd Inter-national Conference on Distributed Computers Systems Workshops，434－439，2003.

［7］Kawuu W Lin，Ming Hua Hsieh，Vincent S Tseng.A Novel Prediction-Based Strategy for Object Tracking in Sensor Networks by Mining Seamless Temporal Movement Patterns［J］.Expert Systems with Applications，2010，(37):2799－2807.

［8］Wang G，Wang T，Jia W，et al.Local Update-Based Routing Protocol in Wireless Sensor Networks with Mobile Sinks［C］//Proceedings of the 2007 IEEE International Conference on Communications(ICC 2007)，Glasgow，Scotland，UK，June 2007.

［9］曾明，危阜胜，陈冠升，等.面向目标跟踪的WSN协同调度策略及拓扑控制［J］.华南理工大学学报(自然科学版)，2010，38(6):60－65.

［10］石为人，贾传江，梁焕焕.一种改进的无线传感器网络DV-Hop定位算法［J］.传感技术学报，2011，24(1):83－87.

［11］危阜胜，胥布工，高焕丽，等.基于无线传感器网络的分布式处理目标跟踪系统［J］.传感技术学报，2009，(10).132－137.

［12］潘旭武，杨东勇.一种面向目标跟踪的无线传感器网络拓扑结构［J］.计算机系统应用，2007，(12):37－40.

［13］Winter J，Lee W C，Xu Y，Prediction Based Strategies for Energy-Saving in Object Tracking Sensor Networks，Proc.2004 IEEE International conference on Mobile Data Management，346－57，2004.

［14］邓克波，刘中.基于无线传感器网络动态簇的目标跟踪［J］.兵工学报，2008，29(10):1197－1202.