（计算机应用技术专业论文）基于wsn的分布式定位跟踪算法研究.pdf

硕士论文 基于w s n 的分布式定位跟踪算法研究 摘要 传感器网络是计算机技术、通信技术中一个新的研究领域，它采用无线通信技术， 由微小的传感器组成，节点具备感应能力、信息处理能力和无线通信能力。无线传感器 网络可应用于军事、环境、医疗保健、空间探索、减灾救灾以及各种商业领域。目标跟 踪是无线传感器网络研究的重点，研究热点主要包括：降低节点能量功耗，延长网络生 命周期；提高节点定位精度；目标丢失等。如何解决这些问题，是一个值得研究的课题。 本文首先讨论了无线传感器网络与目标跟踪的研究现状与背景，接着总结了目标跟 踪过程中涉及到的问题以及目前几种典型的目标跟踪算法，并进行分类和详细比较。最 后，建立目标跟踪模型，提出一种分布式跟踪算法( d t a ) ，节省传感节点能量并使能量 负载更加平衡，延长网络生命周期，同时提高对目标的定位精度。 d t a 算法重点考虑了节点部署，将整个网络监测区域划分成多个虚拟网格，部署两 种不同状态的传感节点，节省不必要的能量消耗，为以后动态簇的形成提供重要保证。 动态簇随着目标的移动而动态更新，及时唤醒目标周围的节点，这样就避免了盲目唤醒 不必要节点造成的能量消耗；并且将节点剩余能量和感应强度作为簇头的选择标准，这 样使能量消耗更加均衡，延长网络生命周期。同时，对簇内成员信息提交的时间间隔进 行分析，将时间间隔与目标运动轨迹相联系，提高定位精度，节省不必要的能量消耗。 对于簇间通信，直接通信并非为最佳选择，针对此情况，算法中的信息提交部分考虑了 节点间接通信，节省节点能量。 最后，在o m n e t + + 平台上对整个目标跟踪算法进行仿真测试。仿真结果表明，该 算法的组簇性能有很大优越性，能够有效减少节点能量消耗，延长网络生命周期，并且 跟踪精度比c b o t 算法有较大提高，传送数据包的平均能量消耗要低于g e a r 算法， 达到了预期效果。 关键词：无线传感器网络，动态簇，分布式跟踪，o m n e t + + 仿真 a b s t i d c t 硕士论文 a b s t r a c t s e n s o rn e t w o r ki san e wr e s e a r c ha r e ao fc o m p u t e rs c i e n c ea n dt e c h n o l o g y , w h i c h c o n s i s t so fm a n yt i n ys e n s o r su s i n gw i r e l e s sc o m m u n i c a t i o nt e c h n o l o g i e s t h ew i r e l e s ss e n s o r n e t w o r kn o d eh a st h ea b i l i t yo fs e n s i n g ，d a t ap r o c e s s i n ga n dw i r e l e s sc o m m u n i c a t i o n t h e w i r e l e s ss e n s o rn e t w o r kh a sa 、析d er a n g eo fa p p l i c a t i o np r o s p e c t sa n dc a nb eu s e di n m i l i t a r y , e n v i r o n m e n t ，h e a l t h , s p a c ee x p l o r a t i o n a n dm a n yo t h e rk i n d so fc o m m e r c i a l a p p l i c a t i o n s t a r g e tt r a c k i n gi sa f u n d m e n t a la n dc r u c i a li s s u ef o rw i r e l e s sn e t w o r ko p e r a t i o n a n dm a n a g e m e n t t a r g e tt r a c k i n ga i m st ob eg r e a t e re n e r g ye f f i c i e n c y ，m o r et r a c k i n g a c c r u a c y ，m o r el o n gl i f e t i m eo fn e t w o r k s ，t a r g e tl o s ta n ds oo n h o w t os o l v et h ep r o b l e m s m a yb er e s e a r c h f u l i nt h i s p a p e r , f i r s t l y , w e d i s c u s st h ev a l u eo ft a r g e t t r a c k i n g i nw i r e l e s ss e n s o r n e t w o r k a n dt h e r e s e a r c hs t a t u sa n df o c u so fw i r e l e s ss e n s o rn e t w o r ki s a n a l y z e d n e x t ，s e v e r a lk e yt e c h n o l o g i e sa r ep o i n t e do u ta b o u tt a r g e tt r a c k i n gi nw i r e l e s s n e t w o r k w h a t s m o r e ，i ta n a l y z e sa n dc o m p a r e s s e v e r a ld o m i n a n t t a r g e t t r a c k i n g a l g o r i t h m s l a s t l y , am o d e li sc o n s t r u c t e da n dan e wd i s t r i b u t e dt a c k i n ga l g o r i t h m ( d t a ) i s p r o p o s e d i tm a k e st h el o a db e t w e e nn o d e sm o r eb a l a n c e d ，p r o l o n g st h el i f e t i m eo fn e t w o r k a n di m p r o v e st h et r a c k i n ga c c u r a c y d t af o c u so nt h er e s e a r c ho fn o d e st o p o l o g y , m a k e st h ei n s p e c t e da r e ai n t os o m ev i r t u a l 西d t w od i f f e r e n t s t a t u sm a k e st h en o d es a v es o m ee x t r ae n e r g ya n dg i v ea ni m p o r t a n t g u a r a n t e ef o rt h ed y n a m i cc l u s t e r d y n a m i cc l u s t e ru p d a t e sw i t ht a r g e t sm o v i n g ，w a k e su pt h e n e i g h b o rn o d e si nt i m ew h i c ha v o i d sw a k i n gu pu n n e c e s s a r yn o d e s a tt h es a m et i m e ，o d d e n e r g ya n dr s s ia r ei n t r o d u c e da st h ep r i n c i p l eo fc l u s t e r - h e a ds e l e c t e dw h i c hm a k e se n e r g y m o r eb a l a n c e da n dp r o l o n g sn e t w o r k s1 i f e t i m e w h a t sm o r e ，s u b m i t t e dt i m ei n t e r v a lo f c l u s t e r - m e m b e ri s a n a l y z e d w h i c ha i m st os a v e e n e r g y a n d i m p r o v e st r a c k i n g a c c u r a c y l a s t l y , p r o p o s i n gu n d i r e c tc o m m u n i c a t i o nm a y b eb e t t e rt h a nd i r e c tc o m m u n i c a t i o n f i n a l l y , w es i m u l a t ed t aw i t ho m n e t + + ，t h er e s u l t i n d i c a t e st h a td t ah a sm a n y a d v a n t a g e si nt e r m so fs a v i n ge n e r g y , p r o l o n g i n gn e t w o r k sl i f e t i m e ，m o r ea c c u r a c yt h a n d p t , l e s se n e r g yc o n s u m p t i o nt h a ng e a r w h i c ha n t i c i p a t e so u rp r e d i c t i o n k e yw o r d s ：w i r e l e s s s e n s o rn e t w o r k ，d y n a m i cc l u s t e r , d i s t r i b u t e dt r a c k i n g ， o n 心m t 抖s i m u l a t e i i 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名： 毯、殇击 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名： 7 年7 月朋 硕士论文基于w s n 的分布式定位跟踪算法研究 1 绪论 1 1 研究背景 1 1 1 无线传感器网络 随着传感技术与通信技术的融合与发展，大规模的传感网络开始逐步发展。传感节 点具有成本低、功耗低、能量有限、通信范围有限以及存储能力有限等特点。在一个传 感网络中，有成百上千的微小传感节点分布在整个物理区域中，位于传感网络中的每一 个节点都能够及时收集压力、温度、辐射以及其它相关的环境信息。各个传感节点通过 邻居节点的转接将收集的数据信息传送到负责处理数据信息的目的节点，这些及时的数 据信息用来反映周围环境的变化。传感器网络的一个典型应用为，大量的传感节点随机 散布在一个战争区域或边界区域用于监测敌方入侵或对移动目标等物体进行监测，比 如，动物，机动车，野火或生化材料等。 在过去的数十年中，我们已经目睹了网络的巨大发展，它能够将分散在各地的信息 有效地进行共享，并因此引发了一场商业革命，对我们的工业、科学、教育以及生活方 式产生了重大影响。而无线传感网络代表一个新的计算方法，传感器网络的到来将会带 领人们进入充满计算的世界，大量的传感节点能够及时地获得真实环境中的各种信息。 从长远发展看，和其它网络一样，传感网络的发展也会对整个世界的发展产生深远的影 响，提供给我们大量的有关物理世界的观测信息，使我们能够更加透彻地了解物理世界。 随着传感网络的广泛应用，它将大大改善人们的生活，并且对生产率的提高产生巨大的 推动作用。 传感器网络具有自组织、容错性等独特的特征，作为一种新的信息收集的工具，无 线传感网络已经广泛的应用于医疗、环境控制、食品安全等各个领域。在过去的几年中， 许多传感器网络已经成功应用于真实世界当中。传感网络的最初功能局限于定位、跟踪 与目标监测等，除了军事领域的应用以外，无线传感器网络也广泛应用于栖息地以及环 境监测等民用领域。另外，有关移动传感节点的研究也取得了重大发展，大量移动节点 的应用能够更有效的对监测区域实现覆盖。 通过以上分析，我们可以看出，无线传感器网络的应用具有非常广阔的前景，但对 于研究者来说，无线传感器网络的应用也存在许多的挑战，具体表现如下： ( 1 ) 数据存储：传感节点对周围环境不断地进行监测，由于节点的存储能力有限， 其不能保存大量的监测数据。节点存储数据需要其它节点的压缩、过滤或融合，过时的 数据需要及时从该节点的存储信息中删除。 ( 2 ) 能量效率：用电池提供能量的节点。部署大规模的网络目的是为了能够使网络 1 绪论硕士论文 长时间的运行，基于能耗有效性的算法能够节省节点能量从而延长网络生命周期。能量 节省的实现可以位于网络中的多个层次，比如物理层、应用层等。 ( 3 ) 容错性：早期的传感网络中，网络瘫痪有很大的可能性。在大部分的传感器应 用领域中，当环境恶劣时，大量的传感节点会失效，人工修复或取代失效节点基本是不 现实的。因此我们提供的系统必须满足：当部分节点由于外界原因失效或死亡时，整个 网络系统应该能够正常运行。 ( 4 ) 定位性：利用传感网络对目标进行定位或跟踪的应用是一个重要的研究方向。 许多的传感网络协议或应用都需要假定每个节点都知道自身的位置信息，但要如何实现 昵? 如果每个节点都装有一个g p s 系统，传感节点就会消耗大量的能量，这是不可行的； 如果只有一小部分节点知道自身位置信息，那么又如何保证存活的节点知道自身位置信 息。 ( 5 ) 网络规模：在将来，有关传感器网络的应用将需要部署成千上万的节点，如何 实现节点自组织以及节点间的协作将是一个很大的挑战。在一定网络规模下，分布式算 法要优于集中式算法，但大量微小设备的控制和管理将是研究者面临的一个重要问题。 ( 6 ) 安全性：无线传感器网络的应用存在安全风险。信息被监听以及因网络拥塞而 拒绝提供服务是传感网络受攻击的两个重要方面。而如何保证传感网络的可访问性、可 靠性以及隐私性。 1 1 2 目标跟踪研究 有关无线传感器网络的研究中，目标跟踪已经作为研究的一个重要方向，它可以广 泛应用于军事领域以及各种民用领域。在军事领域的应用包括对犯罪分子的跟踪，消防 中的救援等等；在民用领域中的应用小到娱乐，大到关系人的生命安全等领域。由此我 们可以看出，在未来有关传感器网络的研究中，目标跟踪的问题的研究将会越来越受到 研究者的关注。 目标跟踪作为科学发展的一个重要研究方向，有关这方面的研究开始于第二次世界 大战前夕。当前的目标跟踪主要集中在不同环境下对单目标的跟踪，随着科学发展和现 代战略的需要，由一个传感节点对一个目标进行跟踪逐步发展成为一个节点对多个目标 同时进行跟踪将会成为研究的热点。作为当今国际热门研究的领域之一，在过去的几十 年中，有关多目标跟踪理论的研究已经取得了突破性的进展，并且许多研究成果都已经 得到广泛地应用。 综上分析可以得出，我们对目标跟踪问题的研究将会有很大的实用价值，其研究成 果将会给我国带来巨大的经济效益和社会效益，能够对人民生活水平的改善提供强有力 地支持。 2 硕士论文基于w s n 的分布式定位跟踪算法研究 1 2 研究现状与动向 1 2 1 节点定位研究 定位问题已经在许多相关研究领域提出，包括移动机器人的自动遥控系统以及车辆 导航系统，虚拟现实系统以及在细胞网络中的用户定位和跟踪系统等。众所周知，全球 定位系统( g p s ) 是一种获得广泛应用的定位技术，虽然我们可以通过在每个节点中安装 g p s 来发现传感网络中每个节点的位置，但是将g p s 系统应用于传感网络中是基本不 可行的，主要是基于以下三个方面的考虑： 一方面，g p s 有一定的适用范围，比如，在室内、水下、地下等环境中，它就不能 得到很好的应用。另一方面，由于传感节点成本较低，如果每个节点都安装g p s 接收 器就会大大提高传感节点的成本。最后，传感节点是要低功耗的，而g p s 接收器则需 要很高的功耗，这样会大大缩短传感网络的生命周期。 基于以上讨论，对传感网络定位系统进行深入研究具有很大的价值。考虑到传感网 络的应用特征，为传感网络设计定位系统的难度要远远高于为其他系统设计定位系统。 传感节点一般被设计成微小、有限计算能力以及有限能量的节点，大量节点被随机散布 在广大区域中，之后，各个传感节点自组织成传感网络。理想的传感定位系统需要低计 算能力以及低功耗，并且能够在拓扑结构发生变化时仍然具备定位能力和自组织能力。 同时，定位系统需要包括大量的传感节点并且能够适应系统和环境的动态变化。 1 2 2 目标跟踪问题的研究 对于目标跟踪过程的研究，跟踪的精度是需要考虑的一个重要因素，该问题已经受 到许多研究者的重视，一些研究者将所有节点都置于活跃状态，用监测节点的位置来估 计目标的位置，以此来减少节点间的数据传输数量。c h a k r a b a r t y 等提出了通过不同区 域内的节点来决定目标位置的方法，该方法中要求每个网格都要由一系列的节点覆盖， 在参考文献 1 】中，只要监测到一个新的目标，就会启动软件移动代理，该代理将会选 择距离目标最近的节点作为监测节点，同时，它会唤醒其它节点来和该节点协作，共同 完成对目标的跟踪任务。在文献 2 中，g u o 和z h o u 提出了一种将整个监测区域划分成 一个个的小监测区域的监测机制，该目标跟踪通过目标移动的历史信息来对目标实现定 位。还有其它的一些技术，运用三个或多个独立的节点来跟踪给定目标，它通过目标的 移动来动态决定哪些节点处于唤醒状态，该方法能够权衡跟踪精度和能耗。 最近，一些研究者提出了一种新的跟踪技术来预测目标的位置。在文献 5 7 中，l i u 等人提出了基于传感观察角度的目标定位，在该方法中，如果在t 时刻，雷达节点a 监测到距离为d 。，角度为0 。的目标，则移动传感节点b 对目标的监测角度为0 日，并且 目标的位置将会通过节点b 对e 。一系列估计得到，而节点a 来完成分布式跟踪数据的 3 1 绪论硕上论文 融合。在此方法中，通过减少节点间的数据通信来达到节约通信能耗的目的。 1 3 论文的主要研究内容 本文主要是对基于无线传感器网络的分布式跟踪系统的研究，具体体现在以下几个 方面： ( 1 ) 对当前各种典型的跟踪模型进行分析，提出新的跟踪模型，详细描述新模型的建 立过程，并在模拟实验平台上用程序实现； ( 2 ) 提出新的动态簇形成机制，以均衡各节点之间的能量，提高对目标的定位精度， 并且延长网络的生命周期； ( 3 ) 深入研究目标位置估计方法，考虑簇内数据融合、目标位置估计与预测、目标丢 失检测、目标恢复等因素； ( 4 ) 在最短路径的基础上，综合考虑能耗和距离，重点分析无线传感器网络路由算法 中节点通信消耗，减少节点能量消耗，延长网络生命周期。 1 4 论文的组织结构 第一章绪论，主要概述无线传感器网络与目标跟踪的研究背景以及研究现状与动 向，同时讨论了有关节点定位的研究和目标跟踪问题的研究，最后总结叙述了本论文主 要研究的内容。 第二章首先介绍目标跟踪算法中几个重要的研究热点并对不同的研究热点进行分 析，然后分析目标跟踪算法中的几个指标，接着分析几种典型的目标跟踪算法，并对这 几种典型算法进行综合比较。 第三章主要分析一种无线传感器网络目标跟踪算法，详细介绍网络模型中动态簇的 簇头和簇成员的选择，对移动目标的定位、位置预测以及数据传输的路由算法，分析目 标跟踪过程中可能出现的问题并给出相应的解决方法。 第四章具体实现第三章中论述的目标跟踪算法，给出每个模块的流程图，具体分析 每个模块的实现，并给出相应的伪代码。 第五章实验结果和分析，简单介绍仿真工具，接着分析仿真过程中具体参数和标准 的确定，最后通过实验数据给出相应的结果和分析。 第六章对本文所做的工作进行总结与展望，分析目前的研究工作中还有待于进一步 完善的地方，以及今后要深入研究的内容和方向。 4 硕士论文基于w s n 的分布式定位跟踪算法研究 2 对移动目标跟踪问题的研究 无线传感器网络定位技术包括自身定位和目标定位( 跟踪) 。节点自身定位就是在无 线传感器网络中的节点部署以后，节点能够通过某种手段实时地确定自身的位置。目标 跟踪则是指无线传感器网络节点在知道自身位置信息的基础上通过一定的机制来确定 目标的位置，如果目标是移动的，则对移动目标的定位称为对移动目标的跟踪。本文是 在各个传感器节点已知自身位置信息的前提下来研究对移动目标的跟踪。 对移动目标的跟踪主要涉及到局部动态簇的生成和分布式数据信息通过各个簇头将 数据监测信息上报到基站的路由算法；其中动态簇的实现主要包括簇的大小选择、簇成 员选择以及簇头选择，对于一个固定大小的区域来说，如果动态簇形成过大，则采集的 数据过多，对数据融合的过程会消耗更多的能量，并且距离移动目标过远的传感器节点 对移动目标的监测信息也不太准确，因此，如何形成最优的动态簇，实现各个节点之间 协作成为对目标跟踪问题研究亟需解决的问题。 2 1 目标跟踪算法的关键技术 基于w s n 的目标跟踪算法涉及到许多关键技术【3 i ，主要涉及到传感节点的组织， 目标的定位和预测以及数据信息上报的路由算法等，对这些问题的研究具有重要的意 义。 2 1 1 传感器节点的组织和路由 对于传感器网络来说，网络中的节点功能相同，没有集中的管理节点。由于传感节 点的能量是受限制的，对目标的跟踪的任务就不能由一个节点单独完成，就需要各个传 感节点间相互协作，并且对某一时刻的所有信息进行有效融合，共同完成对目标的跟踪 任务，这就需要解决节点间的组织和路由问题。 单点式：在整个跟踪过程中，任意时刻，只有一个传感节点对移动目标进行监测 5 4 1 。 无论何时都有一个节点负责对目标位置进行估计并对相应信息进行处理。当目标要离开 时，该监测节点将目标信息传送给自己的邻居节点，由该邻居节点来完成对目标的跟踪 任务，而自己却由监测状态恢复到空闲状态。该方法的实现是基于距离移动目标最近的 节点的，虽然节省了能量，但也大大降低了对目标的跟踪精度。 静态局部集中式：与单点式方法不同，该方法中引进一些具有处理能力的节点，我 们称之为簇头，其中，簇成员节点将数据信息发送给簇头节点，而簇头节点负责完成数 据融合和将数据传送到s i n k 节点的任务【4 1 。该方法是比较好的层次型方法，但在只能 通过自动控制来实现节点部署的情况下，由于节点的功能不同，当簇头因能量耗尽而死 2 对移动目标跟踪问题研究 硕士论文 亡时，该算法却失去了有效性。 动态局部集中式：与静态局部集中式方法相比，该算法中的所有节点都具有相同的 功能，但簇头的产生根据目标的移动按一定得规则从多个节点间动态产生，而不是由人 工部署与其它节点功能不同的簇头【5 3 】。当目标进入某监测区域时，该动态簇负责监测 目标的任务，簇成员节点将监测信息发送给簇头节点；而当目标离开该监测区域时，相 应的区域会产生新的簇及簇头来完成对目标的跟踪任务，而先前负责监测任务的簇头恢 复到休闲状态。不过在目标频繁出现时，由于簇头的负担过重，该方法很容易引起网络 “黑洞( 没有任何节点监测到目标，导致目标丢失) 。另一方面，簇头之间的频繁切换， 也会造成许多不必要的能量消耗。 2 1 2 监控区域的形成或初始簇头的选择 当目标进入到某监测区域时，有可能被多个节点同时感知到，而如何实现多个传感 节点间的协作感知，并且如何对各个节点的监测数据进行融合，是无线传感器网络中对 目标跟踪进行研究的过程中，亟需解决的重要问题。 监控区域的形成以及簇头的选择一般遵循这样的原则：在保证对目标跟踪精度的同 时，应该尽量减少信息量少的节点或信息有冗余的节点参与到目标跟踪过程中，同时， 也应该考虑整个监测区域的通信能量的消耗。也即在尽可能使信息收益最大化的情况 下，优化网络的能耗。 对于以上情况，通常解决的方法是形成一个监测区域，也叫协同组或树。各个传感 节点对移动目标独立进行监测，当节点对目标的监测值超过系统预设值时，则发送加入 信息而成为协同组或树成员，然后在组( 树) 内进行簇头( 根) 节点的选举，以及数据 的融合等工作。 2 1 3 目标定位 当各个传感节点监测到移动目标时，节点需要根据对目标的监测信息估计出目标的 大概位置，而监测信息量的多少与监测节点和移动目标之间的距离相关。对移动目标的 跟踪一般分为两个步骤进行，即对目标进行定位的同时对目标进行跟踪，目前主要的定 位方法为： ( 1 ) 主动模式( p r o a c t i v e ) 基于距离的定位：对传感节点间距离或角度进行估计的常用方法为：到达角度 a o a ( a n g l eo fa r r i v e ) ，到达时间差t d o a ( t i m ed i f f e r e n c eo fa r r i v e ) ，到达时间 t o a ( t o a ，t i m eo f a n i v e ) ，接收信号强度指示r s s i ( r e c e i v e ds i g n a ls t r e n g t hi n d i c a t o r ) ， 由于节点间的距离可以通过r s s i 来估计节点间的距离，因此，研究者常用r s s i 来对 移动目标进行跟踪定位。 基于距离的定位方法一般的情况下能对目标位置进行较为准确的估计，但是该方法 6 硕上论文 基于w s n 的分布式定位跟踪算法研究 需要各节点间保持严格的时间同步，并且跟踪精度的提高是以更多的能量消耗为代价 的。 ( 2 ) 被动模式( r e a t i v e ) 对移动目标进行定位时，有的是与距离无关的定位方法，该方法的实现，要么是通 过对移动目标与节点间的距离进行估计以后，通过似然估计方法或三边测量法对移动目 标进行定位；要么用最简单的方法，即将距离目标最近的节点位置作为移动目标的真正 估计位置p 。 2 1 4 目标轨迹的估计和预测 ( 1 ) 数据表达 常用的对目标位置进行估计有以下几种表示方法：精确坐标值表示、位置范围表示 以及概率分布表示。由于坐标表示需要的精度较高，因此会产生较大的误差，并且该误 差会随着跟踪过程的进行不断扩大，因此当对跟踪精度有较高要求时，该方法就失去了 有效性；而范围表示和概率分布表示则与其不同，它们都是基于目标多个位置的概率来 考虑的，因此能够有较大的可信度，但同时，由于该两种方法中的数据均不确定，因此 对数据的正确表达和计算产生较大的难度。 ( 2 ) 轨迹的估计 对目标运动轨迹的估计，其实就是通过一定得估计方法，将不同时刻的所有对目标 进行监测的数据信息进行处理，进而估计出目标运动的真实轨迹。对目标轨迹进行估计 的比较简单方法为：平均值法、最小方差法或者极大似然估计方法，但这些算法对目标 的轨迹估计精度有待提高，当对目标的位置需要较为精确地估计时，以上方法就失去了 有效性。基于以上考虑，序惯算法能够有效提高对目标轨迹的估计精度。尤其是对于对 目标跟踪的应用来说，该算法能够提供较好的应用。序惯算法对目标位置信息进行顺序 处理或者非成批的处理，整个过程包括预测与更新。常用的方法有最小二乘估计，序惯 贝叶斯滤波估计【5 4 1 ，卡尔曼滤波、粒子滤波【5 5 】等方法。 2 1 5 数据信息上报路由算法 无线传感器网络是与应用相关的网络，与其相关的路由协议机制随着不同的应用目 标而变化。随着应用目标和路由机制的变化，研究者对路由机制提出了相应的分类方法。 总的来说，目前主要有以下几类：层次和平面路由；主动型、被动型和主动被动混合型 路由；以数据为中心类型路由；基于位置的路由协议；可靠的路由协议；多路径和单路 径的路由协议。由于本文研究动态簇方法实现对目标的跟踪，因此，我们重点讨论基于 位置的路由协议和层次型路由协议。 根据是否以地理位置来标识目的地，路由计算中是否利用地理位置信息，可分为基 于位置的路由协议和非基于位置的路由协议。有大量的传感器网络应用需要知道突发事 7 2 对移动目标跟踪问题研究硕士论文 件的地理位置，这是基于位置的路由协议的应用基础，但需要g p s 定位系统或者其它 定位方法协助节点计算位置信息和利用位置信息。数据传送根据位置信息到指定的区域 而不是整个网络，可用来降低能量消耗和信息传输量。这类协议主要有g e a r t 4 3 1 ， g a ft 3 7 1 ，m e c n s m e c nt “1 等。 在w s n 体系结构中，根据节点间的通信方式，路由协议可以分成四类：直接通信 型协议，洪泛式路由协议，平坦型路由协议，层次型路由协议。前三种协议中的所有节 点功能相同，我们将其平等对待，这些协议的实现通过节点之间的信息反馈来实现。典 型的路由协议有泛洪( f l o o d i n g ) 和闲聊( g o s s i p i n g ) 一1 、d d ( d i r e c t e dd i f f u s i o n ) 1 、 s a r ( s e q u e n t i a la s s i g n m e n tr o u t i n g ) 1 8 1 、s p i n ( s e n s o rp r o t o c o l sf o r i n f o r m a t i o nv i a n e g o t i a t i o n ) p 1 。其优点是实现比较简单，易扩展，不需要维护整个网络的拓扑结构和路 由计算。但同时这些路由协议也存在一些缺点，一方面缺乏对整体网络能量的优化管理， 没有考虑传感节点能源有限等特点的限制，节点会又有能量耗尽而较快死亡；另外更重 要的一个缺点是如果要对路由变化进行维护需要大量的控制信息，因而此类协议不能及 时对网络的动态变化做出响应。然而在层次式路由协议里，各个传感节点自组织成动态 簇，簇成员节点将所有数据信息提交到簇头节点，簇头将所有的簇成员提交信息进行处 理，去除冗余数据信息并将最终的处理数据信息提交到s i n k 节点或控制中心。典型协 议如l e a c h t l 0 1 、t e e n t 1 和p e g a s i s i l 2 1 等。 其中，g e a r ( g e o g r a p h i ca n de n e r g y a w a r er o u t i n g ) 是一种基于位置的路由协议，其 充分考虑了能量有效性，与其它基于位置的路由协议相比，它能够更好地应用于无线传 感器网络中。g e a r 算法采用了查询驱动数据传送的方式，将传感器网络中所有信息传 送到合适的目的地。该算法的实现时，对数据的传送主要包括两个阶段，即数据在域内 的传送以及数据传送到目标域。当节点将数据信息传送到目标域的过程为：某监测节点 将数据信息发送到距离目标域更近的邻居节点，而收到数据信息的邻居节点继续进行数 据转发，直到数据到达目标域。 2 2 目标跟踪算法的指标要求 理想的传感器网络跟踪系统应该具有可扩展性、渐进精度性、实时性、可靠性、自 适应性、节能效率高等优点。整个网络中的节点对移动目标进行跟踪的过程中，需要考 虑的指标有节点能量消耗、对目标的跟踪精度、跟踪算法的鲁棒性以及跟踪信息的及时 性等。 整个网络中的节点能量消耗主要部分有数据接收、数据发送、接收信息信息处理、 节点间其它通信，其中最主要的能量消耗是通信能量消耗。在对移动目标的跟踪的整个 过程中为了降低节点的能量消耗，需要考虑节点的监测时间，设计有效的算法来减少对 接收数据进行处理的能耗，同时也要考虑节点间通信的次数以及节点间的通信数据量。 8 硕士论文基于w s n 的分布式定位跟踪算法研究 然而，如果要想提高对目标的跟踪精度，就需要获得更多的目标信息，同时也需要更多 的节点来对目标进行监测，我们就需要更复杂的算法来对数据信息进行处理，节点间也 需要较多的通信量。综上分析可以得出，如何实现对移动目标进行跟踪的研究就是要解 决跟踪精度和能量消耗之间的矛盾。算法的鲁棒性是指当传感网络中的部分节点死亡或 网络拓扑发生变化时，整个算法仍然能够正常运行；跟踪算法的实时性是指，当中心需 要获得目标的位置信息时，相应的信息能够经过及时反馈到控制中心( 如s i n k 节点、 基站或用户终端) 。 2 3 典型的目标跟踪算法 传感器节点不仅存收到许多硬件资源方面的限制，还很容易受到外界环境等多方面 的影响，比如无线链路容易受到干扰，传感网络的拓扑结构动态变化且可能发生变化的 频率较高，而传感网络对目标跟踪的算法需要对目标跟踪有较高的实时性，显然，传统 的网络跟踪算法不能满足此条件。国内外许多学者都对无线传感器网络对目标的跟踪进 行了深入地研究并提出了许多跟踪算法，目前比较典型的几种目标跟踪算法主要分为以 下几类： ( 1 ) 直接通信( d c ) 算法【1 4 】 有关对目标跟踪的算法当中，此算法的实现最为简单。该算法的主要思想为，整个 传感网络中的所有节点都处于活跃状态，并且直接将数据信息发送到s i n k 节点，而s i n k 节点将各个节点发送来的信息进行处理，进而对目标的位置、速度、运动方向等信息进 行估计或预测。虽然该算法的实现比较简单，并且能保证数据信息的及时性。但基于传 感节点能量有限的限制，并且主要的能量消耗在节点的通信能耗上，而通信能耗又与通 信距离有直接的关系，因此，这种算法会导致大量的传感节点在短时间内因能量耗尽而 死亡，从而缩短传感网络的生命周期。此外，直接与s i n k 节点通信，会造成大量的数 据冗余，不仅引起不必要的能量消耗还可能由于多个节点同时与s i n k 节点通信而引起 发送数据信息的冲突。 ( 2 ) x 2 元检测协作( d d c ) 算法1 1 9 我们也可以将该算法称之为“0 ”、“1 监测法，该算法在对移动目标进行跟踪的过 程中，所有的传感节点只可能处于两种状态，即目标要么处于节点对目标的感应范围之 内，要么处于节点对目标的感应范围之外。整个跟踪算法的检测模型如图2 3 1 所示： 9 2 对移动目标跟踪问题研究硕士论文 图2 3 1 双元检测算法目标监测模型 如图2 3 1 所示，r 表示某传感节点所处的位置，如果移动目标处于距离传感节点 的r e 的范围之内，则该节点能够监测到目标的出现；如果目标处于距离传感节点的 r - e 到i h e 之间的范围时，该节点能够以一定的概率监测到目标的出现；而当移动目标 处于距离节点r + e 的的范围之外时，传感节点则不能监测到目标。该算法的整个实现 过程如下： ( 1 ) 每个传感器节点记录移动目标在自身监测区域内持续的时间； ( 2 ) 节点与所有邻居节点交换自身位置信息以及目标在自身监测范围内的持续时间； ( 3 ) 在相应的时间间隔内，根据每个节点在位置估算中的权重估算出节点的位置； ( 4 ) 根据不同时间间隔内的目标位置估计信息，拟合出目标真实运动轨迹。 在对目标的位置进行估计时，该算法是以移动目标在各个节点的监测范围内做匀速 直线运动为前提的，并且根据移动目标在各个传感节点的监测范围之内的连续时间来考 虑各个节点在对目标位置进行估计时，该节点信息所占的权重。在计算该权重时，根据 需要，出现了三种不同的方法，具体如下： 第一种方法为所有的传感节点赋予相同的权重，即所有传感节点的质心就为移动目 标的估计位置。当节点的分布密度比较大且比较均匀时，对目标位置的估计有较高的精 度，否则，对目标的位置估计就会产生较大的误差。 第二种方法为根据目标处于节点监测范围的的时间长短赋予各个节点不同的权重。 当目标处于节点监测范围的时间较长时，对节点赋予较大的权重，否则，对节点赋予较 小的权重，该方法的整个实现原理如图2 3 2 所示： l o 硕士论文基于w s n 的分布式定位跟踪算法研究 图2 3 2 双兀检测权重计算不意图 如图2 3 2 所示，圆心为传感节点所处的位置，当目标处于传感节点的监测范围之 内时，如果d 越大，则表示移动目标的运动轨迹( 已经假设为直线) 距离圆心传感器节 点越近，在对目标位置进行估计时，应该对该节点的监测信息赋予较大的比重；否则为 该节点信息赋予较小的比重。如果节点对目标位置信息的提取频率为f ，则监测信息提 取的时间间隔为_ i t ，我们可以得到式( 2 3 1 ) - ) 一d一122 v ，一) ( 2 3 1 )“ 厂7 、7 通过图2 3 2 与式( 2 3 1 ) ，我们可以得到式( 2 3 2 ) ，= 厣= f 两 亿3 力 由此可以得出各个节点监测信息的权重如式( 2 3 3 ) - ( 2 3 3 ) 其中；即为传感器节点在对目标位置进行估计时所占的权重；r 为某个传感器节点 的监测范围大小；v 为对移动目标速度的估计值；t 为移动目标在节点i 监测范围内持 续的时间；f 节点对目标位置信息的提取频率。 第三种方法与第二种方法相似，同样是权重方法，但该方法没有比较严格的推理过 程，因为根据直觉，上如果目标在传感节点i 的监测范围内持续停留的时间f 越大，则 传感器节点i 对目标的位置进行估计时所占的比重越大，因此令，= l n q ，) 。 双元检测算法中所有的节点都不能计算出节点与目标的距离，只能根据对目标的感 应情况来判断节点是否位于自己的监测范围之内。监测到目标的节点只能确保目标位于 自己的监测范围，但如果想确定目标的真正位置，则需要多个节点间相互合作，取出所 2 对移动目标跟踪问题研究 硕士论文 有传感节点监测范围的交集。当有多个节点同时监测到目标的出现时，该算法能够对目 标位置的估计能够达到较高的精度，但当节点部署比较稀疏时，对要求较高精度的应用 来说，该算法就失去了有效性。该算法比较简单，并且体现了多个节点间的协作感知， 当节点密度比较大并且对精度要求比较低时，能收到比较好的效果。但该算法中需要节 点知道自身位置信息的同时，也要求所有节点要保持时间同步。 3 ) 改进的二进制探测的目标跟踪算法 b p s ( b i n a r yp r o x i m i t ys e i l s o r s ) 算法 在二进制探测目标跟踪算法的基础上，根据w s n 中对移动目标进行跟踪的需要加 州大学的w o o y o u n g 和伊利诺大学的m e c h i t o v 提出一种相应的跟踪算法，该算法中要 求传感网络中的所有节点用l b i t 的信息来确定目标是否处于节点自身监测范围之内。 与二进制探测目标跟踪算法相比，该算法中对目标运动的假设更接近于自然运动，因而 也具有更好的实际意义。该算法中假设移动目标的运动方向和运动速度可以任意改变， 算法通过对目标某一段时间内的运动轨迹进行估计( 即假定目标在该小段时间内做匀速 直线运动) 而逐渐拟合出目标的整个运动轨迹的方法来实现对目标的跟踪，该算法在保 持对目标跟踪精度的同时，降低了算法的复杂度，从而节省了节点能量。该跟踪算法将 所有的传感节点分为两类：探测节点和跟踪节点。其中探测节点主要负责对目标进行监 测，收集相关的目标信息；而跟踪节点主要负责对目标监测信息的计算工作。 在此跟踪算法实现的过程中，根据对传感节点赋值权重的不同，我们可以建立不同 的跟踪系统。而每种跟踪算法性能的好坏直接与对节点赋予权重的方法相关。同样，目 标的移动轨迹与传感节点的位置越接近，则目标在该节点的监测区域内停留的时间越 长。根据移动目标在传感节点监测区域内连续停留时间的长短，我们可以对节点监测信 息赋予的权重采取简化法、距离期望法、路径距离法三种基于节点目标接近度( 距离) 的方法。 ( 4 ) 基于簇的无线传感器网络目标跟踪( c b o t ) 算法【1 7 】 对于基于簇的w s n 目标跟踪算法，最具有代表性的算法是h e l m s m a n 等学者提出 的目标跟踪算法。该算法的实现中要求各个传感节点自组织成簇并选出该簇的簇头，其 中簇成员节点负责收集目标的位置信息，而簇头负责对簇成员的监测目标信息进行融合 并将处理结果发送到s i i l l ( 节点或基站。由此我们可以看出，如果我们人工预先确定簇 头并给出簇头节点固定的能量，簇头会因为处理过多的簇成员提交的数据信息而将能量 耗尽，最终导致簇成员无法将信息向簇头提交而导致算法失效。基于以上问题，该算法 提出：各个簇成员节点之间随机轮流担当簇头，负责簇内数据信息的处理工作，以此来 平衡簇间能量的消耗，延长整个簇的生命周期。该算法在具体的实现过程中不断地选择 簇头，具体选择簇头的方法如式( 2 3 4 ) 所示。 1 2 硕士论文基于w s n 的分布式定位跟踪算法研究 f 一 ! ! ，c ：1 p ( c 。) = n k 木( ，m o d n k ) 。二，、 ( 2 3 4 ) 【0 f 刮 其中，尸( c ，) 为传感节点i 成为该簇簇头的概率，n 为整个传感网络中的所有传感 节点总数，k 是算法预期的整个网络中的簇头总数，n l 【是节点周期成为簇头的轮数， 如果传感节点i 已经当选过簇头，则c ，= 0 ；否则，c ，= 1 。每个负责监测的传感节点 随进产生0 1 之间的一个数值，如果如果该数值小于尸( c ，) 的值，则该传感节点成为本 簇的簇头节点。在算法循环执行的整个过程中，如果节点i 当选过该簇的簇头，则 尸( e ) = 0 ，这样就避免该节点在下次循环的过程中重新成为簇头，而其它从未当选 过本簇簇头的传感节点会以概率p ( c ，)