无线传感网络第七章课件

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,7,章,无线传感器网络的路由协议,7.1,路由协议概述,无线传感器网络路由协议的考虑因素,设计无线传感器网络的路由要考虑的因素很多，大致分为以下两种类型。,(1),网络特征：无线传感器网络具有与众不同的特征，应用于路由协议设计时，主要应该考虑能量损耗、节点部署和网络拓扑变化。,(2),数据传输特征：无线传感器网络的数据采集和传输要求与其他网络不同，因此路由协议设计时也需要加以区别，主要考虑数据传输方式、无线传输手段以及数据融合技术等。,路由的过程,无线传感器网络的路由过程主要分为以下,4,个步骤：,某一个设备发出路由请求命令帧，启动路由发现过程；,对应的接收设备收到该命令后，回复应答命令帧；,对潜在的各条路径开销,(,跳转次数、延迟时间,),，进行评估比较；,将评估确定之后的最佳路由记录添加到此路径上各个设备的路由表中。,无线传感器网络路由协议分类方法,1,按源节点获取路径的方法,主动路由协议、按需路由协议、混合路由协议,2,按节点参与通信的方式,直接通信路由协议、平面路由协议、层次路由协议,3,按路由的发现过程,以位置信息为中心的路由协议、以数据为中心的路由协议,4,按路由选择是否考虑服务质量,(QoS),约束,保证,QoS,的路由协议是指在路由建立时，考虑时延、丢包率等,QoS,参数，从多条可行的路由中选择一条最适合,QoS,应用要求的路由；或者根据业务类型，保证满足不同业务需求的,QoS,路由协议。,7.2,平面路由协议,7.2.1 Flooding and Grossing,协议,1.,洪泛路由协议,洪泛路由协议,(Flooding Protocol),是一种最早的路由协议，接收到消息的节点以广播的彤式转发报文给所有的邻居节点，,(,如图,7-1,2,所示,),。,2.,闲聊法,闲聊法,(Grossing),是洪泛法的改进版本。,如图,7-3,所示,7.2.2 SPIN,协议,基于协商机制的传感器网络,SPIN,协议,(Sensor Protocols for Information via Negotiation),是一种以数据为中心的白适应通信方式，使用,3,种类型的信息进行通信，即,ADV,、,REQ,和,DATA,信息。图,7-4,表示了,SPIN,协议的工作过程。,SPIN,协议的缺点是没有考虑节能和多种信道条件下的数据传输问题。因此，后续又出现了,SPIN-PP(Point to Point,，点到点的通信模式,),、,SPIN-EC(Energy Control,，点到点模式下的节能路由,),、,SPIN-RL(Route Lossy,，点到点通信中的信道衰减模式,),、,SPIN-BC(Broadcast Channel,，广播信道模式,),等在,SPIN,基础上改进的路由协议。,7.2.3 SAR,、,DD,和,MCFA,协议,1,SAR,协议,顺序分配路由,SAR,协议,(Sequential Assignment Routing),是第一个具有,QoS,意识的路由协议。该协议通过构建以,Sink,的单跳邻居节点为根节点的多播树来实现传感器节点到,Sink,节点的多跳路径。,2,DD,协议,定向扩散路由,DD,协议,(Directed Diffusion),是一种以数据为中心的信息传播协议，与已有的路由算法有着截然不同的实现机制。,3,MCFA,协议,最小开销前行算法,MCFA,协议,(Minimum Cost For warding Algorithm for Large Sensor Networks),充分利用了传感器网络中的数据传输不对称的特点，即大多的数据流都是从传感器节点向,Sink,节点的方向传输。,7.3,层次路由协议,7.3.1 LEACH,低功耗自适应聚类分级,LEACH,协议,(LOW Energy Adaptive Clustering Hierarchy),是无线传感器网络中最早提出的分层路由算法。,LEACH,可以将网络整体生存时间延长,15,，其基本思想是通过随机循环地选择簇头节点将整个网络的能量负载平均分配到每个传感器节点中，从而降低网络能源消耗，提高网络整体生存时间。,7.3.2 PEGASIS,高能效采集传感器信息系统,PEGASIS,协议,(Power,Efficient Gathering in Sensor Information Systems),是在,LEACH,协议上提出的一种改进路由算法。,PEGASIS,路由协议在网络中选择一个节点作为起始节点建立一条最优回路链，起始节点将数据融合后的数据信息发送给,Sink,节点。由于起始节点的负载较重，,PEGASIS,采用了全网节点轮流作为回路链起始节点的方式来进行均衡。,该路由协议中使用了贪婪算法,(Greedy Algorithm),来形成链，如图,7-5,所示。在每一轮通信之前才形成链。为确保每个节点都有其相邻节点，从离基站最远的节点开始构建，链中邻居节点的距离会逐渐增大，因为已经在链中的节点不能被再次访，当其中一个节点失效时，链必须重构。,7.3.3 TEEN,阈值敏感的高效传感器网络,TEEN,协议,(Threshold Sensitive Energy Efficient Sensor Network),，是一个基于簇群的路由协议，也是由,LEACH,发展而来，在这个协议中定义了硬门限和软门限两个概念。,这个算法适用于实时性要求较高的应用场合，用户可以及时获取感兴趣的信息。由于感应数据所耗能量比传输数据所耗能量要少得多，虽然节点一直处于感应状态，但是由于减少了很多不必要的数据传输，因此相对来说还是节能的。该协议也有一些不足之处：,门限值达不到，节点就永远不会和簇头节点通信，用户就无法从网络得到任何数据，即使节点已经死亡，用户也不知情；,TDMA,机制的运用保证了群中不会出现数据冲撞的情况，但是如果一个节点没有数据要发送的话，属于它的时隙就浪费掉了，而其他节点却还在等待自己的时隙，这样会向系统中引入过多的时延，不适于实时性要求太高的场合；,没有相应的机制去区分那些没有感应到足够大变化的节点和处于关闭状态的节点。群头节点的接收机要时刻处于激活状态，以便接收任何时候由成员节点传来的数据，在某种程度上增加了簇头节点的负担。,7.3.4 APTEEN,、,TTDD,和,EARSN,协议,1,APTEEN,APTEEN(Adaptive Periodic FEEN),协议是对,TEEN,的扩展，它是一种结合响应型和主动型传感器网络策略的混合型网络路由协议，可以根据用户需要和应用类型来设定协议的周期性和相关阀值，即可以周期性采集数据又可以对突发事件作出快速反应。,APTEEN,在,TEEN,的基础上定义了一个计数时间，当节点从上一次发送数据开始经历这个计数时间还没有发送数据，那么不管当前的数据是否满足软、硬门限的要求都会发送这个数据。,APTEEN,可以通过改变计数时间来控制能量消耗。,2,TTDD,双列数据分发,TTDD(TWO-Tier Data Dissemination),，协议假设节点静态，且各节点的位置信息已知。网络中可以存在多个,Sink,节点，,Sink,节点可以在网络中任意移动。网络中的节点以虚拟栅格的形式划分为若干区域，当监测区域发生事件，附近的多个节点将选择一个节点触发数据上报消息。发送数据上报消息的簇头节点将上报报文发送给栅格外的其他,4,个栅格的邻接节点，由邻接节点转发给该栅格的另外,3,个邻接节点，最后将上报的数据报文发送到每一个栅格。这样无论,Sink,节点移动到网络中的任何地方，都能够从距离最近的节点上收到上报的数据报文。,7.3.4 APTEEN,、,TTDD,和,EARSN,协议,3,EARSN,簇头固定的分簇结构路由协议,EARSN(Energy Aware Routing for Cluster Based Sensor Network),是基于三层体系结构的路由协议。该协议要求网络运行前由终端用户将传感器节点划分成簇，并通知每个簇头节点的,ID,标识和簇内所分配节点的位置信息。传感器节点可以以活动方式和备用的低能源方式两种方式运行，并可以感知、转发、感知并转发和休眠,4,种方式之一存在。与其他路由协议不同的是，该协议的簇头不受能量的限制。它作为网络的中心管理者，可以监控节点的能量变化，决定并维护传感器的,4,种状态。算法依据两个节点间的能量消耗、延迟最优化等性能指标计算路径代价函数。簇头节点利用代价函数作为链路成本，选择最小成本的路径作为节点与其通信的最优路径。经仿真分析，该协议在运行过程中具有很好的节能性、较高的吞吐量和较低的通信延迟。,7.3.4 APTEEN,、,TTDD,和,EARSN,协议,7.3.5,平面路由协议和层次路由协议比较,表,7-1,为各种协议之间的简单对比，主要从移动性、能量需求、路径长度、扩展性、路由状态复杂度、计算和通信所需开销、数据融合技术等多方面进行了分析比较。,总体来看，由于网络结构的不同，平面路由和层次路由体现出了以下几处差异。,移动性,能量使用,路由选择,可拓展性,开销,7.3.5,平面路由协议和层次路由协议比较,7.4,能量感知路由,7.4.1,能量消耗源,1,通信相关的能量消耗,通信相关的能耗包括对传输器、中转器和接收器的使用。,2,计算相关的能量消耗,计算相关的能耗主要涉及协议的处理，主要包括对CPU、主要存储器、一个很小的外设、磁盘或其他一些组成部分的使用。同样的，数据压缩技术在减少数据包长度的同时也因为计算量的增大而增加了能量消耗。,能量路由,在如图,7-6,所示的网络中，源节点是一般功能的传感器节点，完成数据采集工作。,汇聚节点是数据发送的目标节点。大写字母表示节点，如节点,A,，节点右侧括号内的数字表示节点的可用能量。图中的双向线表示节点之间的通信链路，链路上的数字表示在该链路上发送数据消耗的能量。在图中，从源节点到汇聚节点的可能路径有,4,条。,路径,1,：源节点,B,A,汇聚节点，路径上所有节点,PA,之和为,4,，在该路径上发送分组需要的能量之和为,3,；,路径,2,：源节点,C,B,A,汇聚节点，路径上所有节点,PA,之和为,6,，在该路径上发送分组需要的能量之和为,6,；,路径,3,：源节点,D,汇聚节点，路径上所有节点,PA,之和为,3,，在该路上发送分组需要的能量之和为,4,；,路径,4,：源节点,F,E,汇聚节点，路径上所有节点,PA,之和为,5,，在该路径上发送分组需要的能量之和为,6,。,能量路由选择策略主要有以下几种：最大可用能量路由、最小能量消耗路由、最少跳数路由和最大最小,PA,节点路由。,能量多路径路由,能量多路径路由的主要流程描述如下：,(1),发起路径建立,(2),判断是否转发路径建立消息,(3),计算能量代价,(4),节点加入路径条件,(5),节点选择概率计算,(6),代价平均值计算,7.5,基于查询的路由,基于查询的路由协议，在需要不断查询传感器节点采集的数据的应用中，通信流量主要产生于查询节点和传感器节点之间的命令和数据传输，同时传感器节点的采样信息在传输路径上通常要进行数据融合，通过减少通信流量来节省能量。,定向扩散路由,定向扩散,(Directed Diffusion,，,DD),是一种基于查询的路由机制，是专门为无线传感器网络设计的。,定向扩散路由机制包括周期性的兴趣扩散、梯度建立、数据传播、路径加强等阶段。,1,兴趣扩散阶段,2