无线传感网络第七章.ppt

第7章,无线传感器网络的路由协议,7.1路由协议概述,7.1.1无线传感器网络路由协议的考虑因素设计无线传感器网络的路由要考虑的因素很多，大致分为以下两种类型。(1)网络特征：无线传感器网络具有与众不同的特征，应用于路由协议设计时，主要应该考虑能量损耗、节点部署和网络拓扑变化。(2)数据传输特征：无线传感器网络的数据采集和传输要求与其他网络不同，因此路由协议设计时也需要加以区别，主要考虑数据传输方式、无线传输手段以及数据融合技术等。,7.1.2路由的过程,无线传感器网络的路由过程主要分为以下4个步骤：某一个设备发出路由请求命令帧，启动路由发现过程；对应的接收设备收到该命令后，回复应答命令帧；对潜在的各条路径开销(跳转次数、延迟时间)，进行评估比较；将评估确定之后的最佳路由记录添加到此路径上各个设备的路由表中。,7.1.3无线传感器网络路由协议分类方法,1按源节点获取路径的方法主动路由协议、按需路由协议、混合路由协议2按节点参与通信的方式直接通信路由协议、平面路由协议、层次路由协议3按路由的发现过程以位置信息为中心的路由协议、以数据为中心的路由协议4按路由选择是否考虑服务质量(QoS)约束保证QoS的路由协议是指在路由建立时，考虑时延、丢包率等QoS参数，从多条可行的路由中选择一条最适合QoS应用要求的路由；或者根据业务类型，保证满足不同业务需求的QoS路由协议。,7.2平面路由协议7.2.1FloodingandGrossing协议,1.洪泛路由协议洪泛路由协议(FloodingProtocol)是一种最早的路由协议，接收到消息的节点以广播的转发报文给所有的邻居节点，(如图7-1,2所示)。,2.闲聊法闲聊法(Grossing)是洪泛法的改进版本。如图7-3所示,洪泛路由协议,洪泛路由算法是一个简单有效的路由算法，其基本思想是每个节点都是用广播转发收到的数据分组，若收到重复分组则进行丢弃处理。洪泛协议会导致数据分组以源节点为中心进行扩散，为了不造成大面积的扩散占用过多的网络资源以及使扩散收敛，需要设定合适的TTL值（IP包被路由器丢弃之前允许通过的最大网段数量），保证数据分组只经过有限跳路由；此外为了进行重复分组检测，每个节点需要维护一个数据分组序号SEQ和一张路由表，源节点每发送一个数据分组则将SEQ增1，并将该SEQ添加到数据分组的IP头部，其余节点收到数据分组后会将该SEQ记录到路由表并根据该SEQ进行重复分组检测。,洪泛路由协议,洪泛算法最大的问题是会产生大量的重复分组，占用网络资源，使路由器和链路的资源过于浪费，以致效率很低。但是洪泛路由算法是一个最简单和最可靠的路由算法，在节点运动剧烈、进出网络频繁变化的场景下，全网洪泛是有效的方式，其具有极好的健壮性，可用于军事应用，也可以作为衡量标准评价其他的路由算法。,Grossing（闲聊）路由协议,Grossing（闲聊）路由协议在Flooding协议的基础上进行了改进，节点对于产生或收到的数据并不是无条件转发，而是随机转发，因此在一定程度上解决了Flooding协议广播风暴的问题。但是随机转发数据增加了信息传输的平均时延，导致传输速度变慢，并且无法解决部分交叠和盲目利用资源问题。,7.2.2SPIN协议,基于协商机制的传感器网络SPIN协议(SensorProtocolsforInformationviaNegotiation)是一种以数据为中心的白适应通信方式，使用3种类型的信息进行通信，即ADV、REQ和DATA信息。图7-4表示了SPIN协议的工作过程。,SPIN协议的缺点是没有考虑节能和多种信道条件下的数据传输问题。因此，后续又出现了SPIN-PP(PointtoPoint，点到点的通信模式)、SPIN-EC(EnergyControl，点到点模式下的节能路由)、SPIN-RL(RouteLossy，点到点通信中的信道衰减模式)、SPIN-BC(BroadcastChannel，广播信道模式)等在SPIN基础上改进的路由协议。,7.2.3SAR、DD和MCFA协议,1SAR协议顺序分配路由SAR协议(SequentialAssignmentRouting)是第一个具有QoS意识的路由协议。该协议通过构建以Sink的单跳邻居节点为根节点的多播树来实现传感器节点到Sink节点的多跳路径。2DD协议定向扩散路由DD协议(DirectedDiffusion)是一种以数据为中心的信息传播协议，与已有的路由算法有着截然不同的实现机制。3MCFA协议最小开销前行算法MCFA协议(MinimumCostForwardingAlgorithmforLargeSensorNetworks)充分利用了传感器网络中的数据传输不对称的特点，即大多的数据流都是从传感器节点向Sink节点的方向传输。,7.2.3SAR、DD和MCFA协议,1SAR协议顺序分配路由SAR协议(SequentialAssignmentRouting)是第一个具有QoS意识的路由协议。该协议通过构建以Sink的单跳邻居节点为根节点的多播树来实现传感器节点到Sink节点的多跳路径。2DD协议定向扩散路由DD协议(DirectedDiffusion)是一种以数据为中心的信息传播协议，与已有的路由算法有着截然不同的实现机制。3MCFA协议最小开销前行算法MCFA协议(MinimumCostForwardingAlgorithmforLargeSensorNetworks)充分利用了传感器网络中的数据传输不对称的特点，即大多的数据流都是从传感器节点向Sink节点的方向传输。,7.3层次路由协议,7.3.1LEACH低功耗自适应聚类分级LEACH协议(LOWEnergyAdaptiveClusteringHierarchy)是无线传感器网络中最早提出的分层路由算法。LEACH可以将网络整体生存时间延长15，其基本思想是通过随机循环地选择簇头节点将整个网络的能量负载平均分配到每个传感器节点中，从而降低网络能源消耗，提高网络整体生存时间。,7.3层次路由协议,LEACH在运行过程中不断的循环执行簇的重构过程，每个簇重构过程可以用回合的概念来描述。每个回合可以分成两个阶段：簇的建立阶段和传输数据的稳定阶段。为了节省资源开销，稳定阶段的持续时间要大于建立阶段的持续时间。簇的建立过程可分成4个阶段：簇头节点的选择、簇头节点的广播、簇头节点的建立和调度机制的生成。簇头节点的选择依据网络中所需要的簇头节点总数和迄今为止每个节点已成为簇头节点的次数来决定。具体的选择办法是：每个传感器节点随机选择0-1之间的一个值。如果选定的值小于某一个阈值，那么这个节点成为簇头节点。选定簇头节点后，通过广播告知整个网络。网络中的其他节点根据接收信息的信号强度决定从属的簇，并通知相应的簇头节点，完成簇的建立。最后，簇头节点采用TDMA方式为簇中每个节点分配向其传递数据的时间点。稳定阶段中，传感器节点将采集的数据传送到簇头节点。簇头节点对簇中所有节点所采集的数据进行信息融合后再传送给汇聚节点，这是一种较少通信业务量的合理工作模型。稳定阶段持续一段时间后，网络重新进入簇的建立阶段，进行下一回合的簇重构，不断循环，每个簇采用不同的CDMA代码进行通信来减少其他簇内节点的干扰。,LEACH协议特点,1为了减少传送到汇聚节点的信息数量，簇首节点负责融合来自簇内不同源节点所产生的数据，并将融合后的数据发送到汇聚点。2LEACH采用基于TDMA/CDMA的MAC层机制来减少簇内和簇间的冲突。3由于数据采集是集中的和周期性的，因此该协议非常适合于要求连续监控的应用系统。4对于终端使用者来说，由于它并不需要立即得到所有的数据，因此协议不需要周期性的传输数据，这样可以达到限制传感器节点能量消耗的目的。5在给定的时间间隔后，协议重新选举簇首节点，以保证无线传感器网络获取统一的能量分布。,LEACH局限性,1由于LEACH假定所有节点能够与汇聚节点直接通信，并且每个节点都具备支持不同MAC协议的计算能力，因此该协议不适合在大规模的无线传感器网络中应用。2协议没有说明簇头节点的数目怎么分布才能及于整个网络。因此，很可能出现被选的簇头节点集中在网络某一区域的现象，这样就会使得一些节点的周围没有任何簇头节点。3由于LEACH假定在最初的簇头选择回合中，所有的节点都携带相同的能量，并且每个成为簇头的节点都消耗大致相同的能量。因此，协议不适合节点能量不均衡的网络。,7.3.2PEGASIS,高能效采集传感器信息系统PEGASIS协议(PowerEfficientGatheringinSensorInformationSystems)是在LEACH协议上提出的一种改进路由算法。PEGASIS路由协议在网络中选择一个节点作为起始节点建立一条最优回路链，起始节点将数据融合后的数据信息发送给Sink节点。由于起始节点的负载较重，PEGASIS采用了全网节点轮流作为回路链起始节点的方式来进行均衡。该路由协议中使用了贪婪算法(GreedyAlgorithm)来形成链，如图7-5所示。在每一轮通信之前才形成链。为确保每个节点都有其相邻节点，从离基站最远的节点开始构建，链中邻居节点的距离会逐渐增大，因为已经在链中的节点不能被再次访，当其中一个节点失效时，链必须重构。,7.3.3TEEN,阈值敏感的高效传感器网络TEEN协议(ThresholdSensitiveEnergyEfficientSensorNetwork)，是一个基于簇群的路由协议，也是由LEACH发展而来，在这个协议中定义了硬门限和软门限两个概念。这个算法适用于实时性要求较高的应用场合，用户可以及时获取感兴趣的信息。由于感应数据所耗能量比传输数据所耗能量要少得多，虽然节点一直处于感应状态，但是由于减少了很多不必要的数据传输，因此相对来说还是节能的。该协议也有一些不足之处：门限值达不到，节点就永远不会和簇头节点通信，用户就无法从网络得到任何数据，即使节点已经死亡，用户也不知情；TDMA机制的运用保证了群中不会出现数据冲撞的情况，但是如果一个节点没有数据要发送的话，属于它的时隙就浪费掉了，而其他节点却还在等待自己的时隙，这样会向系统中引入过多的时延，不适于实时性要求太高的场合；没有相应的机制去区分那些没有感应到足够大变化的节点和处于关闭状态的节点。群头节点的接收机要时刻处于激活状态，以便接收任何时候由成员节点传来的数据，在某种程度上增加了簇头节点的负担。,7.3.4APTEEN、TTDD和EARSN协议,1APTEENAPTEEN(AdaptivePeriodicTEEN)协议是对TEEN的扩展，它是一种结合响应型和主动型传感器网络策略的混合型网络路由协议，可以根据用户需要和应用类型来设定协议的周期性和相关阀值，即可以周期性采集数据又可以对突发事件作出快速反应。APTEEN在TEEN的基础上定义了一个计数时间，当节点从上一次发送数据开始经历这个计数时间还没有发送数据，那么不管当前的数据是否满足软、硬门限的要求都会发送这个数据。APTEEN可以通过改变计数时间来控制能量消耗。,2TTDD双列数据分发TTDD(TWO-TierDataDissemination)，协议假设节点静态，且各节点的位置信息已知。网络中可以存在多个Sink节点，Sink节点可以在网络中任意移动。网络中的节点以虚拟栅格的形式划分为若干区域，当监测区域发生事件，附近的多个节点将选择一个节点触发数据上报消息。发送数据上报消息的簇头节点将上报报文发送给栅格外的其他4个栅格的邻接节点，由邻接节点转发给该栅格的另外3个邻接节点，最后将上报的数据报文发送到每一个栅格。这样无论Sink节点移动到网络中的任何地方，都能够从距离最近的节点上收到上报的数据报文。,7.3.4APTEEN、TTDD和EARSN协议,3EARSN簇头固定的分簇结构路由协议EARSN(EnergyAwareRoutingforClusterBasedSensorNetwork)是基于三层体系结构的路由协议。该协议要求网络运行前由终端用户将传感器节点划分成簇，并通知每个簇头节点的ID标识和簇内所分配节点的位置信息。传感器节点可以以活动方式和备用的低能源方式两种方式运行，并可以感知、转发、感知并转发和休眠4种方式之一存在。与其他路由协议不同的是，该协议的簇头不受能量的限制。它作为网络的中心管理者，可以监控节点的能量变化，决定并维护传感器的4种状态。算法依据两个节点间的能量消耗、延迟最优化等性能指标计算路径代价函数。簇头节点利用代价函数作为链路成本，选择最小成本的路径作为节点与其通信的最优路径。经仿真分析，该协议在运行过程中具有很好的节能性、较高的吞吐量和较低的通信延迟。,7.3.4APTEEN、TTDD和EARSN协议,表7-1为各种协议之间的简单对比，主要从移动性、能量需求、路径长度、扩展性、路由状态复杂度、计算和通信所需开销、数据融合技术等多方面进行了分析比较。,7.3.5平面路由协议和层次路由协议比较,总体来看，由于网络结构的不同，平面路由和层次路由体现出了以下几处差异。移动性能量使用路由选择可拓展性开销,7.3.5平面路由协议和层次路由协议比较,7.4能量感知路由,7.4.1能量消耗源1通信相关的能量消耗通信相关的能耗包括对传输器、中转器和接收器的使用。2计算相关的能量消耗计算相关的能耗主要涉及协议的处理，主要包括对CPU、主要存储器、一个很小的外设、磁盘或其他一些组成部分的使用。同样的，数据压缩技术在减少数据包长度的同时也因为计算量的增大而增加了能量消耗。,7.4.2能量路由,在如图7-6所示的网络中，源节点是一般功能的传感器节点，完成数据采集工作。汇聚节点是数据发送的目标节点。大写字母表示节点，如节点A，节点右侧括号内的数字表示节点的可用能量。图中的双向线表示节点之间的通信链路，链路上的数字表示在该链路上发送数据消耗的能量。在图中，从源节点到汇聚节点的可能路径有4条。,路径1：源节点BA汇聚节点，路径上所有节点PA之和为4，在该路径上发送分组需要的能量之和为3；路径2：源节点CBA汇聚节点，路径上所有节点PA之和为6，在该路径上发送分组需要的能量之和为6；路径3：源节点D汇聚节点，路径上所有节点PA之和为3，在该路上发送分组需要的能量之和为4；路径4：源节点FE汇聚节点，路径上所有节点PA之和为5，在该路径上发送分组需要的能量之和为6。能量路由选择策略主要有以下几种：最大可用能量路由、最小能量消耗路由、最少跳数路由和最大最小PA节点路由。,7.4.3能量多路径路由,能量多路径路由的主要流程描述如下：(1)发起路径建立(2)判断是否转发路径建立消息(3)计算能量代价(4)节点加入路径条件(5)节点选择概率计算(6)代价平均值计算,7.5基于查询的路由,基于查询的路由协议，在需要不断查询传感器节点采集的数据的应用中，通信流量主要产生于查询节点和传感器节点之间的命令和数据传输，同时传感器节点的采样信息在传输路径上通常要进行数据融合，通过减少通信流量来节省能量。,7.5.1定向扩散路由,定向扩散(DirectedDiffusion，DD)是一种基于查询的路由机制，是专门为无线传感器网络设计的。定向扩散路由机制包括周期性的兴趣扩散、梯度建立、数据传播、路径加强等阶段。1兴趣扩散阶段2梯度建立阶段3数据传播阶段4路径加强阶段,DD路由算法,该算法实现的过程包括三个阶段：兴趣扩散，梯度建立以及路径加强。兴趣扩散：Sink节点查询兴趣消息，兴趣消息采用泛洪的方法传播到网络，来通知整个网络中的其他节点它需要的信息。梯度建立：在兴趣消息扩散的同时相应的路由路经也建立完成。有“兴趣消息”相关数据的普通节点将自己采集的数据通过建立好的路径传送到Sink节点。路径加强：最后sink节点选择一条最优路径作为强化路径。优点：数据中心路由，定义不同任务类型/目标区域消息；路径加强机制可显著提高数据传输的速率；周期性路由：能量的均衡消耗；缺点：周期性的洪泛机制-能量和时间开销都比较大；节点需要维护一个兴趣消息列表，代价较大；不能用于大规模的网络以及网络拓扑结构不断变化的网络。,7.5.2谣传路由,谣传路由(RumorRouting)，其路由的建立是由Sink节点和源节点共同发起并完成的。谣传路由的原理如图7-8所示。,谣传路由协议的执行过程如下：每个传感器节点维护一个邻居列表和一个事件列表。当传感器节点在本地检测到一个事件时，就在事件列表中增加一个表项，设置相关的事件名称、跳数等，同时根据一定的概率产生一个代理消息。代理消息是一个包含生命期等事件信息的分组，用来携带相关的信息通告给它传输经过的每一个传感器节点。,网络的任何节点都可以对一个特定的事件生成查询消息。若查询消息和代理消息的路径出现交叉的情况，交叉节点会沿着查询消息的反方向将事件信息传送到查询节点。如果查询节点在一段时间内没有收到事件消息，就认为查询消息并没有到达事件区域，可以选择重传、放弃或洪泛查询,7.6地理位置路由7.6.1GEAR路由,1.GEAR路由的基本思想GEAR采用查询驱动数据传送模式，根据事件区域的地理位置信息，建立基站或者汇聚节点到事件区域的优化路径。,2.GEAR中查询消息的传播(1)查询消息传送到事件区域GEAR路由用实际代价(1earnedcost)和估计代价(estimatedcost)两种代价值来表示路径代价。GEAR通过如图7-9所示的方式来解决通信空洞问题，从而使路由进行下去。,(2)查询消息在事件区域内传播当查询命令被转发进入事件区域后，大多数情况下采用递归的、基于地理信息的转发方式在事件区域内发布查询命令。如图7-10所示。,2.GEAR中查询消息的传播,(3)GEAR路由的性能GEAR路由定义估计路由代价为节点到事件区域的距离和节点剩余能量，并利用捎带机制获取实际路由代价，进行数据传输的路径优化，从而形成能量高效的数据传输路径。GEAR路由采用的贪婪算法是一个局部最优的算法，适合无线传感器网络中节点只知道局部拓扑信息的情况，其缺点是由于缺乏足够的拓扑信息，路由过程中可能遇到路由空洞，反而降低了路由效率。,7.6.2GAF路由,地域自适应保真算法GAF(GeographicAdaptiveFidelity)是基于有限能量和位置信息的路由算法，,GAF算法的执行过程包括两个阶段。第一阶段是虚拟网格的划分。根据节点的位置信息和通信半径，将网络区域划分成若二干虚拟网格，保证相邻单元格中的任意两个节点都能够直接通信。假设节点已知整个监测区域的位置信息和本身的位置信息，节点可以通过计算得知自己属于哪个网格。第二阶段是虚拟网格中簇头节点的选择。节点周期性地进入睡眠和工作状态，从睡眠状态唤醒之后与本单元其他节点交换信息，以确定自己是否需要成为簇头节点。,每个节点处于发现(discovery)、活动(active)以及睡眠(sleeping)3种状态，如图7-13所示。,7.6.3GPSR路由,GPSR(GreedyPerimeterStatelessRouting)路由协议是贪婪算法(Greedy)和图形算法的结合，它不需要维护路由表，是一种无状态的路由协议。GPSR协议具有贪婪转发(GreedyForwarding)和周界转发(PerimetersForwarding)两种分组转发方式。1.贪婪转发算法贪婪转发算法是一种基于地理信息的路由算法。贪婪转发算法的前提是每个分组都已包含其目的节点位置或目标区域位置，每个节点都已知自己及自接邻节点的位置。贪婪转发算法总是朝距离目的节点最近的邻节点转发分组，如图7-14所示。,2周界转发如图7-15所示，采用周界转发方式时，通常采用右手规则确定转发的路径。,7.6.3GPSR路由,图7-16给出了右手规则的基本原理。当一个数据分组从节点x到达节点y时，它经过下一边时以y为顶点，沿(y,x)逆时针方向上的第一条链路，如图所示的为(y,z)，后续的同样依照此规则来确定，直到数据到达目的节点为止。GPSR路由协议同时采用了贪婪算法和周界转发来对数据分组进行传送。在完整的拓扑图中采用贪婪转发，当贪婪转发找不到下一跳节点时，则在平面图中采用周界转发决定数据分组的下一跳。,7.6.4GEM和MECN路由,1GEM路由GEM(GraphEmbedding)路由协议是一种适用于数据中心存储(DataCentricStorage)方式的基于位置的路由协议。其基本思想是建立一个虚拟极坐标系统，用来表示实际的网络拓扑结构。,2.MECN路由MECN(MinimumEnergyCommunicationNetwork)和SMECN(SmallMECN)协议的主要思想是构建子网，每个子网有一个主站(MasterSite)，相当于层次路由中的簇头节点，要求子网内部所含节点数目少并且任意两个节点之间传输数据都消耗更少的能量。,MECN的实现分两个阶段完成。(1)第一阶段：获取位置信息，由节点内部的计算来构建包含所有发送节点外围的外围图；(2)第二阶段：在外围图中搜索最优路径，采用以能量消耗作为度量代价的分布式最短路径算法来实现。,7.7可靠路由协议7.7.1不相交多路径路由机制,不相交多路径的建立过程如图7-17所示，其基本思想是：首先由汇聚节点发出主路径增强消息，建立一条由汇聚节点到源节点的主路径P，如图7-17(a)所示；然后进行备用路径的建立。汇聚节点向其次优节点A发出次优路径增强消息，节点A再将该消息发给自己的最优节点B。,缠绕多路径的建立如图7-18所示。理想的缠绕多路径由一组缠绕路径构成，如图7-18(a)所示，在主路径上的每个节点都能找到一条不包括本身的从源节点到目的节点的最优路径(实际上是次优路径)。而局部缠绕多路径则是经过运算后有可能在某些主路径的节点处找不到能绕过该节点的理想路径，如图7-18(b)所示。,缠绕多路径可以克服主路径E单个节点