《无线传感器网络技术原理及应用ppt课件 第4章.ppt》由会员分享，可在线阅读，更多相关《无线传感器网络技术原理及应用ppt课件 第4章.ppt（186页珍藏版）》请在三一办公上搜索。
1、第4章 路由层协议,4.1 概述4.2 以数据为中心的路由协议4.3 分层结构的路由协议4.4 地理位置信息路由协议4.5 可靠路由协议4.6 按需路由协议小结,本章目标了解路由协议的特点及分类。理解路由协议的关键技术。理解以数据为中心的路由协议。理解分层结构的路由协议。掌握地理位置信息的路由协议。了解可靠的路由协议。掌握按需路由协议。,学习导航,无线传感器网络是一种无基础设施的网络，由多个传感器节点以自组织方式构成，其目的是协作感知、采集和处理覆盖区域中感知对象的信息。通常情况下无线传感器网络中所有节点的地位都是平等的，没有预先指定的中心。各节点通过分布式算法来相互协调，通过自组织形成一个测
2、量网络。,4.1 概述,无线传感器网络中的节点一般采用电池供电，节点能量受限。这种情况下要延长网络寿命就必须降低节点的工作能耗。由第3章可知，节点能量的大部分消耗在无线通信模块上。要减少节点能量的消耗就必须减小节点的有效传输半径，而有效传输距离的减小必然导致单节点的覆盖面积减小。因此，为了实现传感器节点大范围的覆盖，必须使用多跳中继的方法来传输数据，这就需要相应的路由协议来支持。,4.1.1 功能和特点无线传感器网络路由协议从功能上来讲是将数据从源节点传输到目的节点的机制。无线传感器路由协议的主要设计目标是在满足应用需求的同时降低网络开销，取得资源利用的整体有效性，扩大网络容量，提高网络吞吐量
3、。与传统网络的路由协议相比，无线传感器网络的路由协议具有以下特点：能量受限。传统的路由协议在选择最优路径时，很少考虑节点的能量消耗问题。,而无线传感器网络中节点的能量有限，延长整个网络的生存期成为传感器网络路由协议设计的重要目标，因此需要考虑节点的能量消耗以及网络能量均衡使用的问题。基于局部拓扑信息。无线传感器网络为了节省通信能量，通常采用多跳通信模式，而节点有限的存储资源和计算资源，使得节点不能存储大量的路由信息，不能进行太复杂的路由计算。在节点只能获取局部拓扑信息和资源有限的情况下，如何实现简单高效的路由机制是无线传感器网络的一个基本问题。,以数据为中心。传统的路由协议通常以地址作为节点的
4、标识和路由的依据，是以地址为中心的路由协议。无线传感器网络中大量节点随机部署，所关注的是监测区域的感知数据，而不是具体哪个节点获取的信息，所以无线传感器网络是以数据为中心的路由协议。以数据为中心的路由协议通常包含多个传感器节点到汇聚节点的数据流，按照对感知数据的需求、数据通信模式和流向等，以数据为中心形成消息的转发路径。应用相关。传感器网络的应用环境千变万化，数据通信模式不同，没有一个路由机制适合所有应用，这是传感器网络应用相关性的一个体现。,4.1.2 关键技术针对无线传感器网络路由协议的基本特点，在设计无线传感器网络中需要满足下列传感器网络路由协议的要求：能量高效。传感器网络节点能量受限使
5、节能成为路由协议最主要的优化目标。传感器网络路由协议不仅要选择能量消耗小的消息传输路径，而且要从整个网络的角度考虑，选择使整个网络能量均衡消耗的路由。传感器网络路由协议要能够简单而且高效地实现信息传输。,可扩展性。在无线传感器网络中，检测区域范围或节点密度不同，造成网络规模大小不同；节点失败、新节点加入以及节点移动等，都会使得网络拓扑结构动态发生变化，这就要求路由机制具有可扩展性，能够适应网络结构的变化。鲁棒性。能量用尽或环境因素造成传感器节点失败、周围环境影响无线链路的通信质量以及无线链路本身的缺点等，这些无线传感器网络的不可靠性要求路由协议具有一定的容错能力。,快速收敛性。传感器网络的拓扑
6、结构动态变化，节点能量和通信带宽等资源有限，因此要求路由协议能够快速收敛，以适应网络拓扑的动态变化，减少通信协议开销，提高消息传输的效率。数据融合技术。在传感器网络运行过程中，从传感器节点探测到的数据往往在逐次转发过程中不断被加工处理，以达到降低网络开销、节省能量等目的。也就是说，数据在传输过程中已经被修改，并不是原封不动地从源端传送到目的端，这与传统网络以实现端到端无失真的信息传输的目标是不同的。,在无线传感器网络中，传感器节点没有必要将数据以端到端的形式传送给中心节点处理节点，只要有效数据最终汇集到汇聚节点就达到了目的。因此，为了减少流量和能耗，传输过程中的转发节点经常将不同的入口报文融合
7、成数目更少的出口报文转发给下一跳，这就是数据融合的基本含义。流量分布。传感器网络是一个数据采集网络，绝大部分流量由各个传感器节点流向汇聚节点，因此流量分布极不均匀，以汇聚节点为目的的数据远远超过以它为源的控制流。,这种流量分布特点造成的结果是：越接近汇聚节点，链路的流量越高，相应节点的负载越重，寿命就越短。流量分布不均匀造成功耗分布不均匀，并直接导致网络生存时间的缩短。,4.1.3 分类路由协议的分类多种多样，针对不同的传感器网络应用，研究人员提出了不同的路由协议，目前还没有一个统一的分类方法。本书根据不同的应用将路由协议分为五类：以数据为中心的路由协议。分层结构的路由协议。地理位置信息的路由
8、协议。可靠的路由协议。按需路由协议。,1. 以数据为中心的路由协议以数据为中心的路由协议对感知的数据按照属性命名，对相同属性的数据在传输过程中进行融合操作，减少网络中冗余数据传输。这类协议同时集成了网络路由任务和应用层数据管理任务。,2. 分层结构的路由协议分层结构的路由协议主要特征是将传感器节点按照特定的规则划分为多个簇，通过该簇的头节点汇聚簇内感知数据或者转发其他簇头节点的数据。具体可分为以下两种模式：单层模式：路由协议仅对传感器节点进行一次簇划分，通常假设每个簇头节点都能与汇聚节点通信，如图4-1所示。多层模式：路由协议将对传感器节点进行多次簇划分，即簇头节点将再次进行簇划分，如图4-2
9、所示。,图4-1 单层模式,图4-2 多层模式,3. 地理位置信息的路由协议地理位置信息路由协议假定传感器节点能够知道自身地理位置或者通过基于部分标定节点的地理位置信息计算自身的地理位置。节点的地理位置信息可以作为一个辅助条件，用来改善一些已有的路由算法的性能，比如将采集的数据或者查询请求发送到指定方向从而减少数据的无效传输问题，也可以直接使用地理位置信息来实现路由。,4. 可靠的路由协议无线传感器网络的某些应用对通信的服务质量有较高要求，如可靠性和实时性等。而在无线传感器网络中，链路的稳定性难以保证，通信信道质量比较低，拓扑变化比较频繁，要实现服务质量保证，需要设计相应可靠的路由协议。,5.
10、 按需路由协议按需路由协议又称反应式路由协议或被动路由协议，是一种当需要时才进行路由发现的路由选择方式。与主动式路由协议相比，按需路由协议中的节点平时并不实时地维护网络路由，只有在节点有数据要发送时才激活路由发现机制。由源节点在网络中发起路由查找过程，找到相应的路由后，才开始发送分组。,4.1.4 发展路由协议是无线传感器网络当前研究的热点之一，传感器网络由于其自身资源受限的特点，对路由协议的要求非常高，设计一个通用的路由协议比较困难。一般传感器网络路由协议的设计专门针对特定的应用场景，传感器网络应用场景的专一性为设计高效专用的路由协议带来了可能性。但是还有一些根本性的问题需要进一步解决。,1
11、. 全局最优路由策略在Internet路由协议中，当节点链路发生变化的时候，其设计思想是以最快的速度将该变化通知网络中的其他节点，并重新调整和计算最短路由。链路变化越快，由此引起的路由开销越大。无线传感器网络不适合这种方法，一方面是因为无线链路的不稳定性，节点间链路发生变化的频率太高，维护起来代价太大；另一方面是因为无线传感器网络中节点的能量有限，处理能力低，无线通信带宽窄，而且存储空间也小，及时获得整个网络拓扑改变的信息几乎是不可能的。,无线传感器网络不适合采用传统的全局中心控制式路由算法精确计算优化路径以达到全局优化，适合无线传感器网络的是一些基于局部优化的分布式算法。这要求网络中的每个节
12、点在只与有限范围内的节点交互的前提下，实现局部优化。,2. 路由算法的安全性无线传感器网络通过无线链路来传送数据，无线通信的广播特性使其更容易受到窃听、假冒、篡改等攻击。无线传感器网络中的数据通过多跳广播的方式进行传输，没有受到保护的路由信息很容易遭受多种形式的攻击，因此路由算法的安全性也是一个考虑的因素。无线传感器网络中的节点的地位都是平等的，不存在所谓的中心节点，,而且网络的拓扑结构经常变化，这些都是传统的网络安全机制无法解决的问题。同时由于无线传感器网络的节点处理和存储能力的限制，一些比较好的加密算法也无法在无线传感器网络中使用。由于无线传感器网络的这些特点，设计一套可以在无线传感器网络
13、中使用的安全机制是一项具有挑战性的工作。,3. 能源有效路由策略能源有效性是传感器网络设计中要考虑的重要因素，由于无线传感器网络节点能量有限，所以路由协议设计必须将有效利用能源放在第一位，将服务质量放在第二位。能量有限性是传感器节点最显著的特点，无线传感器节点体积小、价格低，大多采用电池作为能源的供应者。在特定的环境中一旦电池耗尽将无法更换电池，因此设计有效的路由协议来节约节点能源并提高网络的生命周期就成为无线传感器网络的核心问题。,无线传感器网络是一种以数据为中心的网络，以数据为中心的路由协议是无线传感器网络路由协议中最早被讨论的一类路由协议。比较有代表性的以数据为中心的路由协议是：SPIN
14、路由协议和DD路由协议。,4.2 以数据为中心的路由协议,4.2.1 SPIN协议SPIN(Sensor Protocol for Information via Negotiation，协商的路由协议)是最早的一类无线传感器网络路由协议的代表，是一种以数据为中心的自适应路由协议。其目标是通过使用节点间的协商制度和资源自适应机制解决无线传感器网络中的数据冗余问题。,1. 基本思想SPIN路由协议通过节点间协商的方式来减少网络中数据的传输数据量。节点只广播其他节点所没有的数据以减少冗余数据，从而有效减少能量消耗。在SPIN协议中提出了元数据(Meta-data，是对节点感知数据的抽象描述)的概念
15、，元数据是原始感知数据的一个映射，可以用来描述原始感知数据，而且元数据所需的数据位比原始感知数据要小，采用这种变相的数据压缩策略可以进一步减少通信过程中的能量消耗。,SPIN协议采用三次握手协议来实现数据的交互，协议运行过程中使用三种报文数据：ADV、REQ和DATA。三种报文的主要功能如下：ADV用于数据的广播，当某一个节点有数据可以共享时，可以用ADV数据包通知其邻居节点。REQ用于请求发送数据，当某一个节点收到ADV并希望接收DATA数据包时，发送REQ数据包。DATA为原始感知数据包，装载了原始感知数据。,SPIN有两种工作模式：SPIN1和SPIN2。在SPIN1中，当节点A感知到新
16、事件之后，主动给其邻居节点广播描述该事件的元数据ADV报文，如图4-3(a)所示。收到该报文的节点B检查自己是否拥有ADV报文中所描述的数据。如果没有，节点B就向节点A发送REQ报文，在REQ报文中列出需要节点A给出的数据列表，如图4-3(b)所示。当节点A收到了REQ请求的报文后，它就将相关的数据发送给节点B，如图4-3(c)所示。同样节点B发送ADV报文通知其邻居节点(包括节点A)自己有新消息，如图4-3(d)所示。,由于节点A中保存有ADV的内容，节点A不会响应节点B的ADV消息。没有保存ADV消息的节点向节点B回复REQ报文，如图4-3(e)所示。然后节点B向回复REQ报文的节点发送D
17、ATA数据包，如图4-3(f)所示。协议按照以上所述的方式进行，实现SPIN1的算法。SPIN2模式考虑了节点剩余能量值，当节点剩余能量值低于某个门限值就不再参与任何报文转发，仅能够接收来自其他邻居节点的报文和发出REQ报文。在SPIN协议下，节点不需要维护邻居节点的信息，一定程度上能适应节点移动的情况。不过该算法不能确保数据一定能到达目的节点，尤其是不适用于高密度节点分布的情况。,2. 关键技术SPIN协议通过节点之间的协商，解决了Flooding(泛洪协议)和Gossiping(谣传协议)的内爆和重叠现象。“泛洪协议”是一种原始的无线通信路由协议。该协议规定，每个节点接收来自其他节点的信息
18、，并以广播的形式发送给邻居节点。如此继续下去，最后数据将传输到目的节点。但是容易引起信息的“内爆”和“重叠”，造成资源的浪费。内爆现象如图4-4所示。,节点A通过广播将自己的数据转发给节点B和节点C，节点B和节点C通过广播将数据传给同一个节点D，这样同一个数据包多次转发给同一个节点的现象就是内爆。内爆极端浪费节点的能量。重叠现象是传感器网络特有的，如图4-5所示。,图4-3 SPIN协议工作流程,图4-4 内爆现象,图4-5 重叠现象,节点A和节点B感知范围发生了重叠，重叠区域C的事件被相邻的两个节点探测到，那么同一事件被多次传给它们共同的邻节点C，这样造成了能量的浪费。重叠现象是一个比较复杂
19、的现象，比内爆现象更难解决。谣传协议是泛洪协议的改进，它传播数据的方法是随机地选择一个邻居节点作为数据的接收点，获得数据的邻居节点以同样的方法随机地选择下一节点进行数据转发。这种方式避免了以广播方式进行信息传播的能量消耗，代价是延长了信息的传递时间。虽然谣传协议在一定程度上解决了内爆现象，但是重叠现象依然存在。,SPIN协议采用数据融合的思想。数据融合的思想是以数据为中心的无线传感器网络所特有的。数据融合操作可以在MAC层实现，它不同于传统的以地址为中心的网络。在以地址为中心的传感器网络路由协议中，每个源节点沿着到汇聚节点的最短路径转发数据，是不考虑数据冗余性和相关性的，如图4-6所示。以数据
20、为中心的无线传感器网络路由协议中，在数据转发的过程中，中间节点并未各自寻找最短的路径，而是在中间节点A处对数据进行了融合，如图4-7所示。,图4-6 以地址为中心的路由协议,图4-7 以数据为中心的路由协议,SPIN协议具有以下优点：SPIN协议通过协商机制很好地解决了内爆问题，对于重叠问题也进行了一定的处理。特别是SPIN协议支持数据融合，SPIN2进一步地引入了能量管理的概念，一定程度上优化了网络负载，延长了网络生存时间。SPIN协议是一种不需要了解网络拓扑结构的路由协议，由于它几乎不需要了解一跳范围内节点的状态，网络的拓扑改变对它的影响有限，因此该协议也适合节点在可以移动的无线传感器网络
21、中使用。,SPIN协议通过协商机制和能量自适应机制，节省了能量，解决了内爆的问题。引进了元数据的概念，并且通过这种数据压缩方法来减少数据的传输量，是一种值得借鉴的方法。,4.2.2 DD协议 DD(Directed Diffusion，定向扩散)协议是一种基于查询的路由方法，查询的路由协议需要不断查询传感器节点采集的数据。查询命令由汇聚节点(即查询节点)发出，传感器节点向查询节点报告采集的数据。DD算法是一种基于数据相关的路由算法，汇聚节点周期性地通过泛洪的方式广播一种称为“兴趣”的数据包，“兴趣”在网络中扩散的时候也建立起路由路径，采集到和“兴趣”相关数据的节点并通过“兴趣”扩散阶段建立的路
22、径将采集到的“兴趣”数据传送到汇聚节点。,1. 基本思想DD路由协议中引入了几个基本概念：兴趣、梯度和路径加强。整个过程可以分为兴趣扩散、梯度建立和路径加强三个阶段。路径的建立过程由汇聚节点发起，汇聚节点周期性地广播一种称为“兴趣”的数据包，告诉网络中的节点它需要收集什么样的信息。这个过程称为兴趣扩散阶段，DD路由协议机制如图4-8所示。,图4-8 DD路由协议机制,图4-8(a)所示为“兴趣扩散”阶段，该阶段采用泛洪的方式传播汇聚节点的“兴趣”消息到网络中的所有节点。在“兴趣”消息的传播过程中，协议逐跳地在每个传感器节点上建立反向的从数据源节点到汇聚节点的梯度场，传感器节点将采集到的数据沿着
23、梯度场将数据传送到汇聚节点。图4-8(b)所示为“梯度建立”，梯度场的建立根据成本最小化和能量自适应原则。“兴趣”扩散完成之后，网络的梯度建立过程也就完成了。当网络中的传感器节点采集到相关的匹配数据之后，向所有感兴趣的邻居节点转发这个数据，收到该数据的邻居节点，如果不是汇聚节点，采取同样的方式转发该数据。,这样汇聚节点会收到从不同路径上传送过来的相同数据，在收到这些数据以后，汇聚节点选择一条最优路径作为强化路径，后续的数据将沿着这条路径传输，如图4-8(c)所示。,2. 关键技术DD路由协议的核心问题是解决兴趣扩散阶段的梯度建立过程、强化路径的选择和建立过程以及路由的维护过程。1) 兴趣扩散阶
24、段在兴趣扩散阶段，汇聚节点周期性地向邻居节点广播“兴趣消息”。“兴趣消息”中包含任务类型、目标区域、数据传输率、时间戳(即与数据有关的时间参数)等参数。每个节点在本地保留一个“兴趣列表”，“兴趣列表”中的每项对应着不同的“兴趣”，每一个“兴趣列表”中都有一个表项记录发来该“兴趣消息”的邻居节点、,数据发送速率和时间戳等任务相关信息，以建立该节点向汇聚节点传递数据的梯度关系(指示和该兴趣消息有联系的邻居节点所需的数据传输速率和数据发送方向，即感兴趣的邻居节点)。每个兴趣可能对应多个邻居节点，每个邻居节点对应一个梯度信息。通过定义不同的梯度相关参数，可以适应不同的应用需求。每个表项还有一个字段用来
25、表示该项的有效时间值，超过这个时间后节点将删除这个表项。,当一个节点收到一个“兴趣”时，按照以下三条原则来处理该“兴趣”：在“兴趣列表”中检查是否存在相同的“兴趣表项”，如果没有，就根据接收到的“兴趣信息”创建一个新的“兴趣表项”，该表项建立一个唯一的梯度域和该邻居节点对应，梯度域中记录了发送该“兴趣消息”的邻居节点以及相关的数据传输速率。如果该节点有相同的“兴趣表项”存在，但是没有“兴趣”来源的梯度信息，节点会以指定的数据传输速率增加一个梯度域，并更新“兴趣表项”的时间信息和持续时间字段。,如果该节点有相同的“兴趣表项”和“兴趣来源”的梯度信息，那么只是简单进行时间信息和持续时间字段的更新。
26、,2) 数据传播阶段当传感器节点采集到与“兴趣”匹配的数据时，把数据发送到梯度上的邻居节点，并按照梯度上的数据传输速率设定传感器模块采集数据的速率。由于每个节点可能从多个邻居节点收到“兴趣消息”，节点要向多个梯度域的邻居节点发送数据，汇聚节点可能收到经过多个路径的相同数据。其过程如下：中间节点收到其他节点转发的数据后，首先查询“兴趣列表”的表项，如果没有匹配的“兴趣表项”就丢弃数据。如果存在相应的“兴趣表项”，则检查与这个兴趣对应的数据缓冲区。数据缓冲区用来保存最近转发的数据。,如果在数据缓冲区中有与接收到的数据匹配的副本，说明已经转发过这个数据，为避免出现重复传输的现象需丢弃这个数据；否则检
27、查该兴趣表项中的邻居节点信息。如果设置的邻居节点数据发送速率大于或者等于接收的数据速率，则全部转发接收的数据。如果记录的邻居节点数据发送速率小于接收的数据速率，则按照比例转发。对于转发的数据，数据缓存区保留一个副本并记录转发时间。,3) 路径加强阶段DD路由协议机制通过正向加强机制来建立优化路径，并根据网络拓扑的变化修改数据转发的梯度关系。兴趣扩散阶段是为了建立源节点到目的节点的数据传输路径，并且数据源节点以较低的速率采集和发送数据，称这个阶段建立的梯度为探测梯度。汇聚节点在收到从源节点发来的数据后，启动建立到源节点的加强路径，后续数据将沿着加强路径以较高的数据速率进行传输。加强后的梯度称为数
28、据梯度。,假设将数据传输延时作为强化路径的选择标准，汇聚节点选择最先传送过来新数据的邻居节点作为强化路径的下一跳节点，并向该邻居节点发送路径加强消息，通过分析，确定该消息中包含新设定的较高的发送速率值。收到路径加强消息的邻居节点，通过分析，确定该消息描述的是一个已有的兴趣，只是增加了发送速率，则断定这是一条路径强化消息，从而更新相应路由表中的数据发送速率。按照同样的规则选择强化路径的下一跳邻居节点。当建立了到源节点的强化路径后，后续数据将沿着强化路径以较高的数据速率进行传输。,在DD路由协议中，为了对失效路径进行修复和重建，规定已经加强过的路径上的节点都可以触发和启动路径的加强过程，如图4-9
29、所示。节点C能正常收到来自邻居节点的事件，可是长时间没有收到来自数据源的事件，节点C就断定它和数据源之间的路径出现故障。于是节点C将主动触发一次路径加强过程，重新建立它和源节点数据之间的路径。,图4-9 路径本地修复,在DD算法中采用了数据融合的方法，数据融合包括梯度建立阶段兴趣消息的融合和数据发送阶段的数据融合，这两种融合方法都需要缓存数据，DD中的兴趣融合基于事件的命名方式，类型相同、检测区域完全覆盖的“兴趣”在某些情况下可以融合为一个“兴趣”；DD中数据融合采用的是一种副本的方法，即记录转发过的数据，收到重复的数据不予转发。DD中采用的这些数据融合方法，实现起来简单，与路由技术结合能够有
30、效地减少网络中的数据量，节省节点能量，提高利用率。,分层结构的路由协议通常将网络的节点划分为不同的簇，每个簇由一个簇头和多个簇成员组成，这些簇头形成高一级的网络，在这个高一级的网络中还可以再次进行分簇，形成更高一级的网络。这个过程可以一直进行下去，直到最高级。簇头节点负责簇内成员节点的管理，并且完成簇内节点信息的收集和融合操作，同时还负责簇间数据的转发。典型的分层路由协议有LEACH、PEGASIS、TTDD、TEEN和APTEEN。,4.3 分层结构的路由协议,4.3.1 LEACH协议LEACH(Low-Energy Adaptive Clustering Hierarchy，低能自适应聚
31、类层次结构)协议是最早提出的分层路由协议，出发点主要考虑一簇内节点的能量消耗问题，目的是为了延长节点的工作时间，并且实现节点的能耗平衡。,1. 基本思想LEACH是为无线传感器网络设计的低功耗自适应算法路由协议。其基本思想是网络周期性地随机选择簇头，其他的非簇头节点以就近原则加入相应的簇头，形成虚拟簇。簇内节点将感知到的数据直接发送给簇头，由簇头转发给汇聚节点，簇头节点可以将本簇内的数据进行融合处理以减少网络传输的数据量。,2. 关键技术LEACH中每个节点都可以和汇聚节点通信，但是由于节点距离太大，导致与汇聚节点直接通信的能量消耗增大，或者有些节点不在汇聚节点通信范围之内，不能与汇聚节点直接
32、通信。图4-10所示为LEACH路由协议的网络结构图。LEACH路由协议可以形成一个两级的星型网络。每个星型网络称为簇，每个簇都有一个簇头，簇内节点直接和簇头通信，由簇头节点和汇聚节点通信。并且簇内节点和簇头的距离较近，比节点直接和汇聚节点通信的能量消耗要小很多。,同时簇头还可以进行数据融合处理，减少网络数据量。但是簇头节点消耗了大量能量，为了避免某些节点过早的死亡，需要定期更换簇头，以延长整个网络的寿命。,图4-10 LEACH协议网络结构图,簇头节点的选择依据网络中所需的簇头节点数和每个节点已成为簇头的次数来决定。具体的选择办法是：每个传感器节点选择0，1之间的一个随机数，如果选定的值小于
33、规定的阈值T(n)，那么这个节点就称为簇头节点。T(n)的计算公式为 (4-1),式中，N为网络中传感器连接节点的个数，k为网络中的簇头节点个数，r为已完成的周期数，G为网络生存期的周期。一个周期分为两个阶段：簇的建立和稳定的数据传输阶段，稳定传输阶段的持续时间要大于簇建立所需要的时间。选定簇头以后，簇头节点通过广播告知整个网络自己成为簇头的事实，网络中的非簇头节点根据接收信号的强度决定从属的簇，并通知相关的簇头，最后簇头节点采用TDMA方式为簇中每个节点分配传输数据的时隙。,LEACH协议从传输数据的能量和数量上进行了优化，提高了网络的生存时间，但是还是有一些问题需要解决。首先，它需要网络协
34、议和硬件支持射频功率的自适应和动态调整；其次，协议无法保证簇头节点能遍及整个网络，很可能出现被选的簇头节点集中在网络中某一区域的现象。,4.3.2 PEGASIS协议PEGASIS(Power Efficient Gathering in Sensor Information System，高效数据聚合协议)路由协议是在LEACH协议基础上发展起来的，是分层结构的路由协议中常见的一种路由协议。,1. 基本思想PEGASIS协议中的节点在进行数据传输之前先发送测试信号，通过检测应答来确定离自己最近的相邻节点并作为自己的下一节点，在整个网络中的所有节点按照这种方式最终形成一条链，如图4-11所示。
35、,图4-11 PEGASIS协议网络结构图,通过这种方式网络中的所有节点都只是与相邻的节点通信，如果有传感器节点电源耗尽，链便更新一次，所以每个节点都以最小的功率发送数据分组。同时，各节点接收上个节点的数据，并完成必要的数据融合，减少了数据冗余。链中只有一个节点充当簇头节点的角色，而且簇头节点在链中顺序游走，实现节点的能耗平衡。PEGASIS协议只有充当簇头的节点和距离较远的基站通信，其他节点的发送距离较小，进一步减少了功耗。,2. 关键技术PEGASIS协议的实现过程可以分为两个阶段： 成链阶段。从距离基站最远的节点开始，各节点依次找到与其最近的节点，该节点就作为链上的下一节点，依次遍历全网
36、形成网络链，数据传输只在链上相邻的两个节点之间进行传输，大大减小了传输距离。 数据传输阶段。数据传输从链的两端开始，各节点都知道自己在链上的位置，每一轮中都选出一个节点作为簇头。各节点接收邻居节点的数据并与自身的数据进行融合后传向下一邻居节点，最终由簇头节点传向基站。传感器节点之间必须保持同步。,4.3.3 TTDD协议TTDD(Two-Tier Data Dissemination，两层数据发布)路由协议提出了一种新的应用背景，该应用场景中，传感器节点不动，而汇聚节点移动，且一个网络中有多个汇聚节点。TTDD路由协议针对这个场景，从能耗和功能上给出了较好的解决方法。,1. 基本思想TTDD是
37、一个两层路由协议，只能用在存在多个汇聚节点以及汇聚节点可以移动的网络中。当多个传感器节点探测到事件发生时，选择一个节点作为发送数据源节点，源节点以自身作为格状网的一个交叉点构造出一个格状网，如图4-12所示。,以节点A为源节点建立的格状网。源节点先计算出四个相邻交叉点位置，请求最接近交叉点位置的节点称为转发节点，转发节点继续这个过程，直至请求任务超时或者到达网络边缘。转发节点保存了事件和源节点信息，是以后进行数据传输的参与者。汇聚节点在本地通过泛洪方式查询附近的转发节点，转发节点如果有相关的数据记录，该转发节点就将查询请求通过周围的转发节点传送到源节点。源节点收到查询请求后，通过查询请求消息建
38、立的传输路径传送请求数据到汇聚节点。,汇聚节点在等待请求数据时，可继续移动，为了保证数据在汇聚节点移动的时候还能达到汇聚节点，汇聚节点为自己指定了一个代理节点。所有传送给汇聚节点的数据必须先传给代理节点，由代理节点转发给汇聚节点，这样可以从一定程度上保证最后一段路径的稳定性。,图4-12 以节点A为源节点建立的格状网,2. 关键技术TTDD路由协议需要解决三个问题：格状网的构造和转发节点的选取；对汇聚节点移动的支持；节点失效时格状网的维持。1) 格状网的构造和转发节点的选取以图4-12所示的格状网为例，它是以节点A为源节点建立的一个格状网。TTDD需要地理位置信息的支持，网络中每个节点都知道自
39、己的位置(汇聚节点可以不用知道自己的位置)，假设节点A的坐标为LA=(x，y)，每个格子的边长为a，那么以节点A为中心的网络中所有的交叉点的坐标LP=(xi，yi)，其坐标计算如下：,xi=x+i*a，yi=y+j*a；i，j=0，1，2， (4-2)节点A广播数据消息，离节点A的交叉位置最近的节点接收该消息，这样节点A的四个交叉点处的交叉数据就建立起来了。转发节点继续相同的操作，寻找离节点A两跳距离的交叉点处的转发节点，这一过程一直继续，直到遇到网络边界或者任务超时为止。,这里需要解决的问题就是如何确定离交叉点最近的节点，TTDD采用的方法是：离交叉点距离小于a/2的节点接收数据信息，距离大
40、于a/2的节点不接收数据消息，这些收到消息的节点通过广播发送自己的位置和与本次广播相匹配的数据源信息，这样所有接收到数据消息的节点就知道了所有可以作为交叉点转发节点的位置信息，以最短距离标准可以决定哪个节点是最优的。,2) 对汇聚节点移动的支持格状网建立起来后就可以响应汇聚节点的查询任务了。在TTDD算法中，汇聚节点的查询任务可以分为以下几步：汇聚节点通过泛洪来实现查询，但是泛洪的区间限制在一个很小的范围内，一般是一个网格单元，这样可以保证至少可以找到一个转发节点，泛洪区间的大小可以视情况适当地放大。当某个转发节点需要响应该查询时，就将该转发节点作为发起本次查询的汇聚节点的直接转发节点。,当直
41、接转发节点收到查询消息后，通过建立格状网时建立的路径向自己的上游节点传送查询消息，查询消息一直被传送到源节点。查询消息传播路径上的转发节点需要保存自己的下游节点以及相应的查询发起节点的信息，这些信息用于以后将数据发往正确的汇聚节点。当直接转发节点接收到多个汇聚节点对同一个数据的查询消息时，它只向自己上游节点转发一次查询消息。同样地，转发节点如果从不同的下游节点接收到对同一数据的查询，那么也只向上游节点转发一次查询消息。,当查询消息到达源节点后，源节点通过查询消息传播的反向路径将数据发送到直接转发节点。 注意 上游节点的定义是每个转发节点均在格状网建立时由源节点或其他转发节点指定，这个指定本转发
42、节点的源节点或其他转发节点称为本转发节点的上游节点，相对地，本转发节点为它们的下游节点。每个汇聚节点和两个虚拟的节点相关，称为初级代理节点和直接代理节点(在开始的时候，初级代理节点和直接代理节点可以是同一个节点)。,由汇聚节点选取邻居节点作为代理节点。汇聚节点发送查询消息时，查询消息包含初级代理节点的位置信息。当直接转发节点收到源节点发往汇聚节点的数据后，将数据转发给初级代理节点，由初级代理节点将数据转交给直接代理节点，再由直接代理节点将数据发给汇聚节点。当汇聚节点将要移出现在的直接代理节点的通信范围内时，汇聚节点将重新选取一个新的直接代理节点，并且将新的直接代理节点的位置信息发送给初级代理节
43、点。为了保证发送给原来直接代理节点的数据不丢失，新的直接代理节点的位置信息也被发送给原来的直接代理节点，,如果原来的直接代理节点还没有要转发的数据，这些数据通过新的直接代理节点发送给汇聚节点。当新的直接代理节点选定后，初级代理节点将直接转发节点收到的数据交给直接代理节点，由直接代理节点和汇聚节点交互。,3) 节点失效时格状网的维持由数据源建立的格状网也有自己的生存时间，数据源在数据消息中加入网格生存时间，如果在源节点规定的时间内，形成格状网的相关节点没有收到任何修改生存时间的消息，那么在超时的时候，节点就会取消自己的角色，网络也就不存在了。针对节点失效的情况，TTDD算法提出了上游信息复制的方
44、法。每个转发节点都从自己的邻居节点中选择一个或多个节点作为自己的备份节点，在这些备份节点中保存本转发节点的上游节点的位置。,当这个转发节点失效以后，从它的下游邻居节点发送来的上游节点的修正信息(该修正信息为数据请求消息)会被备份节点响应，该备份节点会向上游节点发送上游数据请求消息。当备份节点收到上游节点发送过来的数据后，由于它不知道下游邻居节点的信息，将简单地向自己的三个交叉点的转发节点转发该数据包，发起请求的那个节点会响应该数据。这个过程一直重复，备份节点通过反复学习，建立自己的上下游节点位置信息，并且将自己提升为该交叉点的转发节点。汇聚节点的直接转发节点的失效由汇聚节点探测，当汇聚节点发送
45、数据请求多次超时，汇聚节点会重新发起一次泛洪查询过程，重新建立路由路径。,TTDD路由协议以源节点为中心展开，整个网络变成数据源节点捕捉汇聚节点的一个格状网，和以汇聚节点为中心建立路由的场景完全不同。不过TTDD算法中节点必须知道自身的位置信息，非汇聚节点位置不能移动，而且要求网络节点密度较大，最难确定的是网络单元大小，这个参数对网络性能有很大的影响。,4.3.4 TEEN与APTEEN协议TEEN(Threshold-Sensitive Energy Efficient Protocols，门限敏感能量有效协议)和APTEEN(Adaptive Periodic TEEN，自适应周期TEEN
46、)都是LEACH协议的改进，TEEN是针对LEACH算法实时性不强的问题提出的一种解决方案，但是TEEN不能周期性地采集数据，然而LEACH协议主要是实现周期性地对环境采集数据。APTEEN算法综合了LEACH和TEEN的思想，提出了一种既可以周期性地采集数据，又可以实时采集数据的方法。,1. 基本思想TEEN采用与LEACH相同的多簇结构和运行方式。不同的是，在簇的建立过程中，随着簇首节点的选定，簇首除了通过TDMA方法实现对节点的调度外，还向簇内成员广播有关数据的硬阈值和软阈值两个参数。硬阈值是被检测数据所不能逾越的阈值，软阈值则规定被测数据的变动范围。在簇的稳定阶段，节点通过传感器不断地
47、感知其周围环境，当节点首次检测到数据达到硬阈值时，便打开收发器进行数据传送，同时将该检测值存入节点内部变量。,节点再次进行数据传送时要满足两个条件：当前检测值大于硬阈值；当前的检测值与内部变量的差异大于或者等于软阈值。只要节点发送数据，内部变量便置为当前的检测值。在簇重构过程中，如果新一轮的簇首已经确定，该簇首将重新设定和发布以上两个参数。通过设置硬阈值和软阈值两个参数，TEEN能够大大地减少数据传送次数，比LEACH算法更节能。TEEN协议的优点是适用于实时应用系统，能对突发时间做出快速反应；缺点是不适用于需要持续采集数据的应用环境。,为了满足周期性采集数据和实时响应特殊事件应用场合的需求，
48、APTEEN协议结合了LEACH算法和TEEN算法的优点，是一种结合了响应型策略和主动型策略的混合型网络路由协议。响应型策略：在APTEEN协议下，节点在检测到突发事件数据时会采用与TEEN相同的机制。主动型策略：为了改变TEEN不能周期发送数据的缺点，APTEEN在TEEN的基础上定义了一个计数器，,节点每发送一次数据就将该计数器清零，当计数器时间到达时，不管当前的数据是否满足软、硬阈值的要求都会发送这个数据。APTEEN提出三种查询的概念：历史数据查询、当前网络的一次查询和持续监控某一事件的连续查询。,2. 关键技术APTEEN簇头的建立采用集中式控制的思想，由汇聚节点决定簇头节点的个数并
49、且指定簇头节点。一旦簇头建立起来，每个簇头节点就向簇内节点广播以下参数：属性：用来表示用户期望获取信息的一组物理参数。阈值：该参数由硬阈值和软阈值组成，具体用法和TEEN协议相同。调度：采用TDMA调度方式，为簇内每个节点分配相应的时隙，注意节点之间不需要时间同步。技术时间：表示一个节点成功发送报告的最大时间周期。,APTEEN算法支持以下三种查询方式：(1) 历史数据查询。接收到查询消息的节点，在自己的时隙内向簇头发送与查询相关的数据。簇头融合所有数据，再分配给它的时隙发送这些数据到汇聚节点。汇聚节点收到这些数据以后，检查消息类型，给响应查询消息的传感器节点发送应答消息。(2) 当前网络的一
50、次查询。传感器节点在自己的时隙将查询响应数据发送给自己的簇头，汇聚节点收到该数据。如果查询是关于特殊事件的，而且汇聚节点已经收到过该数据，,那么汇聚节点就给发送查询响应消息的节点发送应答消息；否则，如果汇聚节点没有收到过相关的数据，那么汇聚节点就给所有处于监听状态的节点发送查询消息。(3) 持续监控某一事件的连续查询。这是当前网路的一次查询的多次重复，第一轮的时延和当前网络的一次查询相同时，就延时一个TDMA帧长度。,在无线传感器网络中，节点通常需要知道它本身的位置信息，这样采集的数据才有意义。例如监测某一区域的环境信息，不仅要知道感知的数据，而且还要知道这一感知数据的位置信息。,4.4 地理
