无线传感器网络原理及应用第5章-目标跟踪技术课件.ppt

第5章 目标跟踪技术 第5章 目标跟踪技术 5.1 目标跟踪的基本原理及跟踪策略目标跟踪的基本原理及跟踪策略 设计要考虑的问题设计要考虑的问题 5.2 点目标跟踪点目标跟踪 5.3 面目标跟踪面目标跟踪 5.4 小结小结 第5章 目标跟踪技术 5.1 目标跟踪的基本原理及跟踪策略设计要考虑的问题目标跟踪的基本原理及跟踪策略设计要考虑的问题5.1.1 无线传感器网络中目标跟踪的基本原理无线传感器网络中目标跟踪的基本原理传感器网络由大量体积小、成本低，具有感测、通信、数据处理能力的传感器节点构成，并将大量的传感器节点部署在监测区域内。自组织成网络后，经过多条路由将数据传输到数据中心，供用户使用。传感器网络体系通常包括传感器节点、汇聚节点和管理节点。在不同的应用中传感器网络节点的组成不同，但传感器节点都有传感器模块、处理器模块、无线通信模块和能量供应模块，其中处理器大都选用嵌入式CPU，通信模块采用休眠/唤醒机制。各模块由一个微型操作系统控制。第5章 目标跟踪技术 传感器网络由大量部署在监测区域内的传感器节点组成，当有目标进入监测区域时，由于目标的辐射特性(通常是红外辐射特征)、声传播特征和目标运动过程中产生的地面震动特征，传感器会探测到相应的信号。我们假定把N个传感器节点部署在监控区域为S的区域内，网络总的延时为T。传感器最大探测半径为R。任一时刻t，当有目标以速度u进入传感器节点探测半径内时，传感器检测为“1”；否则检测为“0”。当网络探测到目标后便开始利用特定的跟踪算法与通信方式进行目标定位跟踪。第5章 目标跟踪技术 下面定性地讨论现有的三种跟踪策略，以比较其跟踪目标的有效性、节能性以及网络寿命。(1)完全跟踪策略：网络内所有探测到目标的传感器节点均参与跟踪。显然，这种策略消耗的能量很大，造成了较大的资源浪费，为数据融合与消除冗余信息增加了负担，但同时这种方法提供了较高的跟踪精度。(2)随机跟踪策略：网络内每个节点以其概率参与跟踪，整个跟踪以平均概率进行跟踪。显然，这种策略由于参与跟踪的节点数目得到了限制，因而可以降低能量消耗，但是不能保证跟踪精度。第5章 目标跟踪技术 第5章 目标跟踪技术 为了对跟踪策略有一个基本的理解，首先简单说明一个目标被跟踪的情况。假定一个物体进入了事先布置和组织好的无线传感器网络监测区域，如果感测信息超出了门限，这时每一个处于侦测状态的节点传感器都能探测到物体，然后把探测信息数据包发送给汇聚节点。汇聚节点从网络内收集到数据后对信息进行融合，得出物体是否需要被跟踪的结论，如果目标的确需要被监控，传感器网络在监测区域内将使用一个跟踪运动目标的算法，随着目标的运动，跟踪算法将及时通知合适的节点参与跟踪，简要过程如下：(1)网络内节点以一定的时间间隔从休眠状态转换到监测状态，侦测是否有目标出现。第5章 目标跟踪技术(2)传感器节点检测到目标进入探测范围后，通过操作系统唤醒通信模块并向网络内广播信息包，记录下目标进入区域所持续的时间。信息包中含有传感器节点身份号码和传感器位置坐标以及目标在探测范围内持续的时间。(3)当汇聚节点接收到K个节点发送的信息后，由目标跟踪公式计算出目标位置。(4)汇聚节点根据接收到的信息和融合信息，通过使用跟踪算法启动相应的节点参与跟踪。(5)当目标离开监测区域时，节点向汇聚节点报告自己的位置信息以及目标在节点探测范围内所持续的时间。汇聚节点综合历史数据和新信息形成目标的运动趋势。第5章 目标跟踪技术 5.1.2 无线传感器网络跟踪策略设计要考虑的问题无线传感器网络跟踪策略设计要考虑的问题传感器网络跟踪目标涉及到目标探测、目标定位、通信、数据融合、跟踪算法的设计等很多方面的问题。在跟踪过程中，如果选择不合适的节点参与跟踪，不但跟踪精度较低甚至有可能丢失目标，并且会过多地消耗不必要的能量。同时算法的优劣也直接影响着跟踪的效果。衡量一个跟踪策略是否具有较好的跟踪效果，需要考虑以下问题：(1)跟踪精度。跟踪精度是目标跟踪中首先要考虑的一个问题，当然也并不是跟踪精度越高就越好，精度越高意味着算法融合的数据越多，这样会增加能量消耗，所以还要结合能量消耗，综合评价跟踪算法的优劣。第5章 目标跟踪技术 第5章 目标跟踪技术(3)跟踪的可靠性。网络的可靠性对目标跟踪的质量有很大的影响。当前应用于目标跟踪的方法主要有集中式和分布式，集中式方法要求所有网络节点在探测到目标后都要向汇聚节点发回探测结果，不但引入的通信开销大，而且计算开销也增加很多，这样网络的可靠性下降很快。分布式方法是一种较好的选择，但是也要充分考虑跟踪算法的鲁棒性，能适应环境的变化，以增强网络的可靠性。(4)跟踪的实时性。在实际应用中跟踪的实时性是一个很重要的指标，实时性能主要由硬件性能、算法的具体设计以及网络拓扑等多方面决定，在硬件技术飞速发展的今天，算法的实时性与网络拓扑结构的选择便越发显得重要。第5章 目标跟踪技术 5.2 点点目目标标跟跟踪踪5.2.1 双元检测协作跟踪双元检测协作跟踪传感器节点具有体积小和价格低的特点，它的传感器模块功能比较弱。下面介绍最简单的情况，即传感器节点只能进行双元检测(binary-detection)时的目标跟踪。第5章 目标跟踪技术 第5章 目标跟踪技术 图5-1双元检测传感器模型 第5章 目标跟踪技术 第5章 目标跟踪技术 由于目标运动具有随机性，要跟踪这样不规则的运动轨迹十分困难。在不影响跟踪结果的条件下，假设目标在节点的侦测范围内匀速运动，从而将目标运动轨迹近似为一条折线。由于单个传感器节点的侦测范围比较小，这样的假设很接近目标的真实运动轨迹。通过大量节点的协作可以进一步提高跟踪精度。双元检测协作跟踪的基本过程如下：(1)当节点侦测到目标进入侦测区域时，唤醒自身的通信模块并向邻居节点广播检测到目标的消息。消息中包含节点ID以及自身位置信息。同时该节点开始记录目标出现的持续时间。第5章 目标跟踪技术(2)如果节点检测到目标出现，同时接收到两个或两个以上节点发送的通告消息，则节点计算目标位置。计算时采用目标在节点侦测范围内的持续时间作为权重。(3)当目标离开侦测区域时，节点向汇聚节点发送自己的位置信息以及目标在自己侦测区域内的持续时间信息。汇聚节点根据已有的历史数据和当前获得的最新数据进行线性拟合，计算移动目标的运动轨迹。第5章 目标跟踪技术 第5章 目标跟踪技术 图5-2目标持续时间长度与计算权重的关系 第5章 目标跟踪技术 5.2.2 信息驱动协作跟踪信息驱动协作跟踪对移动目标的侦测、分类、跟踪通常需要在传感器节点间进行协作。对节点跟踪数据的融合能够有效地提高跟踪精度。通过选择合适的节点进行协作能降低节点间的数据通信量，从而节省节点能量和通信带宽。协作跟踪的关键在于如何通过节点间交换跟踪信息实现对目标运动轨迹较为精确的跟踪，同时尽量减少节点的能量消耗。协作跟踪的关键问题包括确定让哪些节点进行跟踪，需要获取哪些侦测数据以及节点间必须交换哪些信息。根据综合考虑节点获得的跟踪信息的有效性和精确度，以及节点完成跟踪任务需要的能量代第5章 目标跟踪技术 价来决定哪些传感器节点应参与跟踪过程以及跟踪节点间的协作方式。信息驱动(information-driven)协作跟踪的核心思想就是传感器节点利用自己侦测到的信息和接收到的其他节点的侦测信息判断目标可能的运动轨迹，唤醒合适的传感器节点在下一时刻参与跟踪活动。由于使用了合适的预测机制，信息驱动的协作跟踪能够有效地减少节点间的通信量，从而节省节点有限的能量资源和通信资源。第5章 目标跟踪技术 1信息驱动的协作跟踪方法信息驱动的协作跟踪方法由于目标运动轨迹没有规律，而且目标还可能作加速或减速运动，因此通过预先选定的一些传感器节点进行目标跟踪会产生一些问题。首先是不能保证有效的跟踪，其次是跟踪效率较低，有些不在目标运动轨迹附近的节点也要参与跟踪。为此，有些学者提出了基于信息驱动的协作跟踪方法，使传感器节点能够通过交换局部信息来选择合适的节点检测目标并传递信息。图5-3表示了一个信息驱动的协作跟踪实例。网络中包括两类传感器节点，分别装有角度传感器和距离传感器。图中的粗线表示目标穿过传感器网络的轨迹，虚线边界圆形第5章 目标跟踪技术 区域为传感器节点的侦测范围，用户通过汇聚节点(如图5-3中节点Q)查询目标跟踪信息，要求传感器网络每隔一段时间报告一次目标位置。任何时刻传感器网络中至少有一个节点处于活动状态，负责存放当前目标跟踪状态信息，这个节点称为跟踪节点。随着目标的移动，当前跟踪节点负责唤醒并将现有的跟踪信息传递给下一个跟踪节点。目标进入传感器区域时，离目标最近的节点a获得目标位置的初始估计值，并计算出下一时刻节点b进行跟踪时能够保证侦测数据的精度，使自己到节点b的通信代价在规定的范围内，则将获得的目标位置估计值传给节点b。b使用相同的标准选择下一个跟踪节点c，这个过程不断重复直到目标离开传感器网络侦测区域。每隔一段时间节点就将目标的位置信息返回给汇聚节点。第5章 目标跟踪技术 第5章 目标跟踪技术 2.跟踪节点的选择跟踪节点的选择信息驱动的协作跟踪的核心问题是如何选择下一时刻的跟踪节点。如果选择了不合适的节点，传感器网络可能会丢失跟踪目标或者产生多余的通信代价。选取下一时刻最优跟踪节点的策略需要综合考虑该节点侦测数据对结果的影响以及当前节点到该节点的通信代价，如何以较小的能量消耗代价来提高目标位置估计的准确性。第5章 目标跟踪技术 1)侦测精度评估结合附近传感器节点的数据，能提高当前目标位置估计结果的精确性。传感器节点并不是都能提供可靠的信息，而且有些数据信息虽然有效，却是冗余的。因此就要寻找一个最优化的节点子集，并且确定这些节点数据加入目标位置估计过程的最佳顺序。第5章 目标跟踪技术 通过计算传感器节点到当前目标的有效估测范围的均值，可以评价节点数据的有效性。假设目标位置的估计服从高斯分布，则可以用不确定性椭圆表示。如图5-4所示，实线椭圆表示当前目标位置估计，虚线椭圆表示在下一时刻结合了传感器节点S1或S2的测量值后的目标位置估计。结合传感器节点S1或S2的测量值都可能提高对当前目标状态估计的精确性，但由于传感器节点S1，S2位置不同，得到的估计结果也不同。虽然分别结合这两个节点侦测数据后的估计结果都会减少不确定性椭圆的面积，但大小不同，选择令椭圆面积更小的节点作为下一个跟踪节点。若减少了相同面积，但如果结合节点S2侦测数据后不确定性椭圆仍然有很长的长轴，而结合节点S1侦测数据后椭圆的长轴大大缩短，考虑到高斯分布中不确定性椭圆的长轴越长则表示不确定性越高，因此选取S1作为新的跟踪节点能够得到对目标位置更加精确的估计。第5章 目标跟踪技术 第5章 目标跟踪技术 2)代价评估选择下一时刻的跟踪节点需要考虑该节点的通信代价、该节点获取目标位置信息的消耗代价以及该节点结合自身侦测结果和接收到的侦测结果时的能量消耗。这三部分能量消耗分别是通信能量消耗、感应能量消耗和计算能量消耗，其中通信能量消耗是主要部分。一般来说，对于传感特征相同的节点，相互距离越近这些代价将越小。因此跟踪节点选择令目标位置估计不确定性椭圆面积减少最多的邻居节点作为下一个跟踪节点，将能以较小的能量消耗来提高目标位置估计的准确性。第5章 目标跟踪技术 基于信息驱动的目标跟踪方法在保证跟踪精度的同时尽量减少由于节点间不必要的通信带来的能量消耗。衡量节点间的不确定性是估计一个节点是否能增加侦测精度的一种可行方法。而在考虑节点跟踪精度的同时也要考虑节点间能量消耗。如何更好地结合这两个因素是未来信息驱动跟踪中的一个重要问题。由于节点能够智能地决定后继跟踪节点，所以信息驱动的跟踪方法能够大幅地减少参加跟踪活动的节点数量，从而减少整个网络的能量消耗。第5章 目标跟踪技术 第5章 目标跟踪技术 图5-5表示通过传送树进行目标跟踪的过程。如图5-5(a)所示，目标进入侦测区域时，在探测到目标的传感器节点中选出一个根节点，并构造出初始传送树。传送树上每个节点周期性发出侦测信息，并传送到根节点。根节点收集传送树上所有节点的侦测报告，进行数据融合处理，并将处理结果发送到汇聚节点。随着目标的移动，传送树删除那些距离目标越来越远的节点，唤醒目标移动方向上的节点并将其加入传送树。当目标与根节点的距离超过一定阈值时，需要重新选出根节点并重新构造传送树，如图5-5(b)所示。第5章 目标跟踪技术 图5-5基于动态传送树的目标跟踪第5章 目标跟踪技术 为了节省传感器节点的能量，传感器网络采用网格状的分簇结构。簇内节点周期性地担任簇头节点。当该网格没有侦测事件发生时，只有簇头节点处于工作状态，普通节点则处于休眠状态。当移动目标进入网格时，簇头节点负责唤醒单元格中的其他节点。传送树跟踪算法包括如下3个关键问题：当目标第一次出现在监视区域中时，构造一棵初始传送树；随着目标的移动对传送树进行调整；当根节点距离目标超过阈值时重新选出根节点并重构传送树。第5章 目标跟踪技术 1.初始传送树的建造初始传送树的建造当目标第一次进入传感器网络的侦测区域时，它附近的簇头节点会探测到目标，并且立刻唤醒网格内的其他节点。被唤醒的节点相互交换自己到目标的距离，并选出当前距离目标最近的节点作为传送树的根节点。如果几个节点到目标的距离相同，就选择节点号小的节点作为根节点。第5章 目标跟踪技术 选举根节点的过程分为两个阶段：第一阶段中，每个工作节点都广播一个选举消息给所有的邻居节点，选举消息包括本节点到目标的距离以及节点号信息。如果某个节点在所有邻居节点中到目标的距离最短，则该节点成为根节点的候选者；否则，它就放弃竞选根节点并选择邻居中距离目标最近的节点作为父节点。第二阶段，每个根节点候选者向整个网络广播胜利者消息，胜利者消息仍然包括自己到目标的距离以及节点号信息。如果某个候选者收到一个胜利者消息，而且该胜利者到目标的距离比自己到目标的距离小，它就放弃竞选根节点并且选择转发胜利者消息的节点作为父节点。最终选出距离目标最近的节点成为传送树的根节点，其他能够侦测到目标的节点都连接至该传送树。第5章 目标跟踪技术 2.传送树的调整传送树的调整由于目标的移动，传送树上有些节点不再能够侦测到目标，而另外一些处于目标移动方向上的节点需要加入传送树。当传送树上的节点发现自己不能侦测到目标时，向父节点发出通告，父节点将其从传送树上删除。为了确定需要加入传送树的节点，目前提出了保守机制和预测机制两种方法。这两种方法都由根节点计算需要增加的节点。第5章 目标跟踪技术 在如图5-6(a)所示的保守机制中，到当前目标位置的距离小于的节点都将包含在传送树中。其中，vt是目标当前的移动速度，是一个全局参数，ds是节点监控区域的半径。这个方案假设目标以小于的速度向任意方向移动。为了令下一时刻凡侦测到目标的节点都位于传送树上，参数应该足够大。但如果过大，传送树将包含许多冗余节点。第5章 目标跟踪技术 为减少保守机制中的冗余节点，有些学者提出了一种预测机制。该机制假设可以通过一定的方向预测技术判断出目标未来的位置。只有处在预测监控范围内的节点才能加入传送树。如图5-6(b)所示，只有那些到目标预测位置的距离小于ds的节点才会加入传送树。由于目标的移动方向不会频繁的改变，所以预测机制能够在大大减少冗余节点的同时保证对目标的跟踪。确定需要加入传送树的节点后，根节点向这些节点所在网格的簇头节点发送通告信息，并由簇头节点唤醒它们。这些节点将选择自己邻居中到目标距离最近的节点作为父节点。第5章 目标跟踪技术 图5-6 基于动态传送树的目标跟踪第5章 目标跟踪技术 3.传送树的重构传送树的重构当目标到根节点的距离超过一定阈值时，需要重构传送树以保证对目标的跟踪。这个阈值为dm+a+vt。其中dm表示最小的重构距离，vt为t时刻的目标速度，a为一个小数。重构传送树仍旧按照上述算法选举距离目标最近的节点作为新的根节点。当新的根节点选出后，要进行根的迁移。由于当前根节点只知道新的根节点离目标较近，所以原先的根节点先寻找目标当前的单元格，然后向该单元格的头节点发送迁移请求。收到请求后，头节点把这个消息发给新的根节点。在根节点改变后，网络需要重构传送树以使收集各节点数据的能量消耗最小。新的根节点先广播一个重组消息给第5章 目标跟踪技术 它的邻居。收到重组消息的节点在重组信息包中加入自身的位置信息和与根节点通信的代价信息，并继续广播。当其余任何节点收到重组消息后，都等待一定的时间以便收集所有发送给自己的重组消息。然后，每个节点选择与根节点的通信代价最小的邻居节点作为自己的父节点。这个过程将持续到监控区域内的所有节点都加入到树中为止。第5章 目标跟踪技术 传送树是传感器节点协作跟踪的一种可行方案，移动目标附近的节点通过加入传送树将侦测信息汇聚到树根节点。通过增加和删除适当的节点以及重构传送树，可以保证对目标的有效跟踪。选择距离目标最近的节点作为根节点，并且每个节点只将自己的数据传送给父节点，从而降低了数据传输的冗余性。使用分簇的拓扑结构也减少了整个网络的能量消耗。但是根节点需要进行数据融合和新节点的计算，能量消耗比较大。第5章 目标跟踪技术 5.3 面面目目标标跟跟踪踪传感器网络跟踪中，很多情况下需要跟踪面积较大的目标，例如森林火灾中火灾边缘的推进轨迹，台风的行进路线等。在这种情况下仅仅通过局部节点的协作无法侦测到完整的目标移动轨迹，为此有些学者提出使用对偶空间转换的方法决定由哪些节点参与跟踪，以保证对目标移动轨迹的完整侦测。第5章 目标跟踪技术 5.3.1 对偶空间转换对偶空间转换考虑初始二维空间的直线，它由和两个参数唯一确定，其中表示斜率，表示截距。定义这条直线的两个参数在初始空间的对偶空间中用点表示。同样地，初始空间中的点(a，b)定义了对偶空间中的一条直线=a+b。这是一个一一映射关系，如图5-7所示。第5章 目标跟踪技术 图5-7初始空间与对偶空间的映射关系第5章 目标跟踪技术 假设将面积较大的目标看成一个半平面，则它的边界就是一条直线。对偶空间变换就是将每个传感器节点映射为对偶空间中的一条直线，将目标的边界映射为对偶空间中的一个点。这样，在初始空间中无规律分布的传感器节点在对偶空间中便成为许多相交的直线，并将对偶空间划分为众多子区域，而跟踪目标的边界映射到对偶空间中则是一个点，并处于某个子区域中，如图5-8所示。这个子区域对应的几条相交直线就是离目标最近的传感器节点，再通过到初始空间的逆变换确定此时需要的跟踪节点。第5章 目标跟踪技术 图5-8对偶空间映射 第5章 目标跟踪技术 通过对偶跟踪的方法，跟踪问题转换为在对偶空间中寻找包括目标边界映射点的子区域。当目标移动时，映射点会进入其他子区域，这时需要唤醒新区域中的节点进行跟踪，而让原有区域中不再属于新区域的节点转入休眠状态。第5章 目标跟踪技术 5.3.2 对偶空间跟踪算法对偶空间跟踪算法假设传感器节点知道自己是否处于跟踪目标的半平面内，并且处于该半平面内的节点将自己标记为0，不在该半平面内的节点将自己标记为1。如图5-9所示，假设节点P1坐标为(x1，y1)，目标边缘L的方程为y=ax+b，由于点P1处于直线L上方，因此有(5-1)当节点P1和直线L都映射到对偶空间后，P1对应直线y=x1x+y1，对应坐标点(-a，b)，因此有(5-2)第5章 目标跟踪技术 图5-9 节点与目标边缘关系第5章 目标跟踪技术 即在对偶空间中，点P1处于直线L的下方。每个节点都进行这样的计算，从而可以得到一组线性不等式，通过这组线性不等式可以计算出目标映射点在对偶空间中的子区域。对偶空间跟踪算法是一种集中式算法，需要一个计算中心计算当前需要的跟踪节点，并向这些节点发出指令。只有那些包含映射点的传感器节点才需要被激活。通过数学方法可以证明，在由任意多个传感器节点形成的任何直线集合中，确定一个子区域的平均直线数量至多是4个。所以对偶空间跟踪算法需要较少的跟踪节点就能完成跟踪任务，从而有效地节省能量。第5章 目标跟踪技术 仅通过局部传感器节点的协作很难有效地跟踪大面积目标。通过将侦测目标转换为寻找目标边界的行进轨迹，可以有效地简化跟踪目标的难度。利用对偶空间转换，将边界变换为点，将传感器节点转换为直线，能够有效地确定跟踪节点。但是这种方法需要一个中心节点来实现算法并进行调度，增大了网络传输负载，也缺乏足够的实时性。第5章 目标跟踪技术 5.4 小小 结结当前的目标跟踪算法主要针对不同环境下的单目标跟踪。如何以最低的能量代价高效地融合有效信息是各种算法的核心问题。若要提高目标跟踪精度，必然需要融合较多节点的数据，这就会带来较高的能量开销。而若要节省能量，就只能在有限范围内进行通信和计算，那么结果精度就会受到影响。实际中需要根据对结果精确度的要求和能量消耗等方面进行综合考虑，以选择合适的跟踪策略。第5章 目标跟踪技术 传感器网络目标跟踪涉及目标检测、定位、运动轨迹预测、预警等重要问题。在研究过程中需要综合考虑传感器网络的自治性、低存储和计算能力、数据传送的鲁棒性、通信延迟、可靠性等特点，并要在节省能耗、增大测量精度、延长生存期等性能指标的提高上进行更深入的研究。