无线传感器网络原理及应用 无线传感器网络关键技术.pptx

本身具有较强的应用相关性，再考虑到数据的融合处理，因此不仅传统无线网络路由协议不再适合，而且也很难设计一个适合的无线传感器网络的通用路由协议。其中，无线传感器网络路由协议设计的一个主要目标就是在执行数据通信功能的前提下尽可能地延长网络的寿命，并通过积极的能量管理技术避免网络连接性因节点能量不足而造成的恶化。与传统网络的路由协议相比，无线传感器网络的路由协议具有以下特点：第1页/共187页(1)能量优先。传统路由协议在选择最优路径时，很少考虑节点的能量消耗问题。而无线传感器网络中节点的能量有限，如何延长整个网络的生存期成为传感器网络路由协议设计的重要目标，因此需要考虑节点的能量消耗以及网络能量均衡使用的问题。(2)基于局部拓扑信息。无线传感器网络为了节省通信能量，通常采用多跳的通信模式，而节点有限的存储资源和计算资源使得节点不能存储大量的路由信息，不能进行太复杂的路由计算。在节点只能获取局部拓扑信息和资源有限的情况下，如何实现简单、高效的路由机制是无线传感器网络的一个基本问题。第2页/共187页(3)以数据为中心。传统的路由协议通常以地址作为节点的标识和路由的依据，而无线传感器网络中大量的节点随机部署，所关注地是监测区域的感知数据，而不是具体由哪个节点获取的信息，因此是不依赖于全网的唯一的标识。传感器网络通常包含多个传感器节点到少数汇聚节点的数据流，按照对感知数据的需求、数据通信模式和流向等，形成以数据为中心的消息的转发路径。(4)应用相关。传感器网络的应用环境千差万别，数据通信模式各不相同，没有一个路由机制适合所有的应用，这是传感器网络应用相关性的一个体现。设计者需要针对每一个具体应用的需求，设计与之适应的特定路由机制。第3页/共187页针对传感器网络路由机制的上述特点，在根据具体应用设计路由机制时，要满足下面的传感器网络路由机制的要求：(1)高效地使用能量。传感器网络路由协议不仅要选择能量消耗小的消息传输路径，而且要从整个网络的角度考虑，选择使整个网络能量均衡消耗的路由机制。传感器节点的资源有限，传感器网络的路由机制要能够简单而且高效地实现信息传输。(2)可扩展性。在无线传感器网络中，检测区域范围或节点密度不同，造成网络规模的大小不同；节点失败、新节点加入以及节点移动等，都会使得网络拓扑结构动态发生变化，这就要求路由机制具有可扩展性，能够适应网络结构的变化。第4页/共187页(3)鲁棒性。能量用尽或因环境因素造成传感器节点信息传输的失败、周围环境对无线链路的通信质量的影响以及无线链路本身的缺点等，这些无线传感器网络的不可靠特性要求路由机制具有一定的容错能力。(4)快速收敛性。由于传感器网络的拓扑结构动态变化，节点能量和通信带宽等资源有限，因此要求路由机制能够快速收敛，以适应网络拓扑的动态变化，减少通信协议开销，提高消息传输的效率。第5页/共187页3.1.1 路由协议的分类在无线传感器网络中，由于网络内节点的资源有限、应用背景特殊，数据包的传输需要通过多跳通信方式到达目的节点，因此路由协议的设计是无线传感器网络中的一项基本支撑技术。传统无线网络的路由设计以避免网络冲突、保证网络的连通性以及提供高质量的网络服务为主要目的，在路由协议的实现过程中，首先利用网络层定义的逻辑上的网络地址来区别不同节点以便实现数据交换，然后通过路由选择算法决定到达目的节点的最佳路径。与传统网络不同，虽然无线传感器网络与Ad Hoc网络极为相似，但是在网络特点、通信模式和数据传输要求等方面却还是有较大差异。第6页/共187页虽然当前Ad Hoc网络路由协议的研究相对比较成熟了，但是传统的Ad Hoc网络路由协议不能适用于无线传感器网络。具体表现在如下几个方面：(1)无线传感器网络是以数据为中心进行路由的网络，类似于分布式网络数据库，要查询的数据分布在全部或者部分节点中，而不同于Ad Hoc网络的点对点通信模式。(2)无线传感器网络随应用需求而变化，因此无线传感器网络的路由协议是基于特点应用进行设计的，所以很难设计出通用性强的路由协议。第7页/共187页(3)无线传感器网络邻近节点间采集的数据具有相似性，存在冗余信息，需要经过数据融合(Data Fusion)处理后再进行路由。(4)传统网络(包括有线和无线网络)每一个节点都具有唯一的标识号(ID)。而无线传感器网络是基于属性进行寻址(Attribute-Based Ad-Dressing)的，不需要给每一个节点分配唯一的地址。(5)由于无线传感器网络节点能量有限，所以路由设计一般将“能效高”放在第一位，将“服务质量(QoS)”放在第二位考虑，因此无线传感器网络必须设计新的讲究高能效的路由协议。第8页/共187页(6)无线传感器网络的一个重要特征就是资源受限，网络内的每个传感器节点通常使用能量有限、不便于更换的电池，而且由于受节点规格大小的限制，节点的处理能力、存储能力、通信能力均为有限。(7)在无线传感器网络中由于能量有限及环境的干扰，节点本身比较脆弱易损，节点的失效概率比较大；再加上节点间进行无线通信也要消耗能量，随着能量的消耗，每个节点的通信能力下降、通信范围减小，因此无线传感器网络的拓扑结构不确定，而是动态变化的。第9页/共187页根据无线传感器网络的特点，要求路由协议的设计必须要以节能为首要目的，使用户在延长网络寿命的同时获得较优的网络吞吐率，降低网络的通信延迟。通过对无线传感器网络路由协议特点的分析可以看出，一个好的无线传感器网络体系结构中的网络层路由协议应该满足如下几个条件：(1)高效利用有限的节点能量，在满足无线传感器网络通信的前提下，最大限度地延长网络寿命，使低网络能耗均匀地分布在每个节点上。(2)满足无线传感器网络拓扑结构的动态变化，提高网络的鲁棒性，路由协议尽量分布式运行。第10页/共187页(3)尽可能减少节点间通信负载的冗余，节约有限的能量和通信资源；路由协议设计时以数据为中心，采用数据融合等技术降低通信负载。(4)满足无线传感器网络的可扩展性，由于无线传感器的网络节点数目众多、网络规模大、网络节点易损，要保证传感器节点的随时加入和退出不会影响到全局任务的执行，路由协议的设计必须具备鲁棒性和可扩展性。(5)在路由协议的设计中需要考虑网络和数据的安全，在提高网络通信可靠性的同时，降低遭受攻击的可能性。第11页/共187页在无线传感器网络的体系结构中，网络层中的路由协议非常重要。网络层主要的目标是寻找用于无线传感器网络高能效路由的建立和可靠的数据传输方法，从而使网络寿命最长。由于无线传感器网络有几个不同于传统网络的特点，因此它的路由协议设计非常具有挑战性。首先，由于节点众多，不可能建立一个全局的地址机制；其次，产生的数据流有显著的冗余性，因此可以利用数据聚合来提高能量和带宽的利用率；再次，节点能量和处理存储能力有限，需要精细的资源管理；最后，由于网络拓扑变化频繁，需要路由协议有很好的鲁棒性和可扩展性。目前，从可以获得的文献资料来看，无线传感器网络基本处于起步阶段，从具体应用出发，根据不同应用对无线传感器网络的各种特性的敏感度不同，大致可将路由协议分为四种：第12页/共187页(1)能量感知路由协议。高效利用网络能量是传感器网络路由协议的一个显著特征，早期提出的一些传感器网络路由协议往往仅考虑了能量因素。为了强调高效利用能量的重要性，在此将它们划分为能量感知路由协议。能量感知路由协议从数据传输中的能量消耗出发，讨论最优能量消耗路径以及最长网络生存期等问题。(2)基于查询的路由协议。在诸如环境检测、战场评估等应用中，需要不断地查询传感器节点采集的数据，汇聚节点(查询节点)发出任务查询命令，传感器节点向查询节点报告采集的数据。在这类应用中，通信流量主要是查询节点和传感器节点之间的命令和数据传输，同时传感器节点的采样信息在传输路径上通常要进行数据融合，由此通过减少通信流量来节省能量。第13页/共187页(3)地理位置路由协议。在诸如目标跟踪类应用中，往往需要唤醒距离跟踪目标最近的传感器节点，以得到关于目标的更精确的位置等相关信息。在这类应用中，通常需要知道目的节点的精确或者大致地理位置。把节点的位置信息作为路由选择的依据，不仅能够完成节点路由功能，还可以降低系统专门维护路由协议的能耗。(4)可靠的路由协议。无线传感器网络的某些应用对通信的服务质量有较高的要求，如可靠性高和实时性强等。但在无线传感器网络中，链路的稳定性难以保证，通信信道的质量比较低，拓扑变化比较频繁，因此要实现较高的服务质量，需要设计相应的可靠的路由协议。第14页/共187页3.1.2 能量感知路由协议高效地利用网络能量是无线传感器网络路由协议的最重要特征。能量感知路由协议从数据传输中的能量消耗出发，讨论最优能量消耗路径以及最长网络生存期等问题，其最终目的是实现能量的高效利用。1能量路由能量路由的基本思想是根据节点的可用能量(Power Available，PA)，即根据节点的剩余能量或传输路径上的能量需求来选择数据的转发路径。第15页/共187页在图3-1所示的网络中，圆圈表示节点，括号内的数据为该节点的可用能量。图中双向线段表示节点间的通信链路，链路上的数字表示在该链路上传输数据所消耗的能量。源节点可以选取下列任意一条路径将数据传送至汇聚节点。路径一：源节点BA汇聚节点，此路径的可用能量之和为4，所需要消耗的能量之和为3；路径二：源节点CBA汇聚节点，此路径的可用能量之和为6，所需要消耗的能量之和为6；路径三：源节点D汇聚节点，此路径的可用能量之和为3，所需要消耗的能量之和为4。路径四：源节点FE汇聚节点，此路径的可用能量之和为5，所需要消耗的能量之和为6。第16页/共187页能量路由策略主要有以下几种：(1)最大可用能量路由。从源节点到汇聚节点的所有路径中选取节点的可用能量之和最大的路径。在图3-1中路径二的可用能量之和最大，但路径二包含了路径一，因此不是高效的路径，从而被排除，最终选择路径四。(2)最小能量消耗路由。从源节点到汇聚节点的所有路径中选取节点耗能之和最小的路径。在图3-1中选择路径一。(3)最少跳数路由。选取从源节点到汇聚节点跳数最少的路径。在图3-1中选择路径三。第17页/共187页(4)最大最小可用能量节点路由。每条路径上有多个节点，且节点的可用能量不同，从中选取每条路径中可用能量最小的节点来表示这条路径的可用能量。如路径四中节点E的可用能量最小为1，所以该路径的可用能量是1。最大最小可用能量节点路由策略就是在多条路径中，选择路径可用能量最大的路径。在图3-1中选择路径三。上述能量路由算法需要节点知道整个网络的全局信息。由于传感器网络存在资源约束，节点只能获取局部信息，因此上述能量路由方法只是理想情况下的路由策略。第18页/共187页2.能量多路径路由无线传感器网络中如果频繁使用同一路径传输数据，会造成该路径上的节点因能量消耗过快而提早失效，缩短了网络生存时间。为此，研究人员提出了一种能量多路径路由机制。该机制在源节点和目的节点之间建立多条路径，根据路径上节点的能量消耗以及节点的剩余能量状况，给每条路径赋予一定的选择概率，使得数据传输均衡地消耗整个网络的能量。能量多路径路由协议包括路由建立、数据传播和路由维护三个阶段。第19页/共187页(1)路由建立阶段：这一阶段是该协议的重点。每个节点需要知道到达目的节点的所有下一跳节点，并根据节点到目的节点的通信代价来计算选择每个下一跳节点传输数据的概率。记节点Nj发送的数据经由本地路由表FTj中的节点Ni到达目的节点的通信代价为C(Nj，Ni)，则可以通过公式(3-1)计算节点Ni作为节点Nj的下一跳节点的选择概率节点将下一跳节点选择概率作为加权系数，根据路由表中每项的能量代价计算自身到目的节点的代价，并替代消息中原有的代价值，然后向邻节点广播该路由建立的消息。(3-1)第20页/共187页(2)数据传播阶段：对于接收数据，节点根据选择概率从多个下一跳节点中选择一个节点，并将数据转发给该节点。(3)路由维护阶段：周期性地从目的节点到源节点实施洪泛查询，维持所有路径的活动性。能量多路径协议综合考虑了通信路径上的消耗能量和剩余能量，节点根据选择概率在路由表中选择一个节点作为路由的下一跳节点。由于这个概率是与能量相关的，因此可以将通信能耗分散到多条路径上，从而可实现整个网络的能量平稳降级，最大限度地延长网络的生存期。第21页/共187页3.1.3 基于查询路由1.定向扩散路由基于查询的路由通常是指目的节点通过网络传播一个来自某个节点的数据查询消息(感应任务)，收到该查询数据消息的节点又将匹配该查询消息的数据发回给原来的节点。一般这些查询是以自然语言或者高级语言来描述的。第22页/共187页定向扩散(Directed Diffusion，DD)是一种基于查询的路由机制。汇聚节点通过兴趣消息(Interest Message)发出查询任务，采用洪泛方式将兴趣消息传播到整个区域或部分区域内的所有传感器节点。兴趣消息用来表示查询的任务，表达了网络用户对监测区域内感兴趣的信息，例如监测区域内的温度、湿度和光照等环境信息。在兴趣消息的传播过程中，协议逐跳地在每个传感器节点上建立反向的从数据源到汇聚节点的数据传输梯度(gradient)。传感器节点将采集到的数据沿着梯度方向传送到汇聚节点。定向扩散路由机制可以分为周期性的兴趣扩散、数据传播以及路径加强三个阶段。图3-2显示了这三个阶段的数据传播路径和方向。第23页/共187页图3-2 定向扩散路由机制 第24页/共187页1)兴趣扩散阶段在兴趣扩散阶段，汇聚节点周期性地向邻居节点广播兴趣消息。兴趣消息中含有任务类型、目标区域、数据发送速率、时间戳等参数。每个节点在本地保存一个兴趣列表，对于每一个兴趣，列表中都有一个表项记录发来该兴趣消息的邻居节点、数据发送速率和时间戳等相关信息，以建立该节点向汇聚节点传递数据的梯度关系。每个兴趣可能对应多个邻居节点，每个邻居节点对应一个梯度信息。通过定义不同的梯度相关参数，可以适应不同的应用需求。每个表项还有一个字段用来表示该表项的有效时间值，超过这个时间后，第25页/共187页节点将删除这个表项。当节点收到邻居节点的兴趣消息时，首先检查兴趣列表中是否存有参数类型与收到兴趣相同的表项，而且对应的发送节点是该邻居节点。如果有对应的表项，就更新表项的有效时间值；如果只是参数类型相同，但不包含发送该兴趣消息的邻居节点，就在相应表项中添加这个邻居节点；对于任何其他情况，都需要建立一个新表项来记录这个新的兴趣。如果收到的兴趣消息和节点刚刚转发的兴趣消息一样，为避免消息循环则丢弃该信息，否则，转发收到的兴趣消息。第26页/共187页2)数据传播阶段当传感器节点采集到与兴趣匹配的数据时，把数据发送到梯度上的邻居节点，并按照梯度上的数据传输速率设定传感器模块采集数据的速率。由于可能从多个邻居节点收到兴趣消息，节点也向多个邻居节点发送数据，汇聚节点可能收到经过多个路径的相同数据。中间节点收到其他节点转发的数据后，首先查询兴趣列表的表项，如果没有匹配的兴趣表项就丢弃数据；如果存在相应的兴趣表项，则检查与这个兴趣对应的数据缓冲池(Data Cach)，数据缓冲池用来保存最近转发的数据。如果在数据缓冲池中有与接收到的数据匹配的副本，说明已经转发过这个数据，为避免出现传输环路则丢弃这个数据；否则，检查该兴趣表项中的邻居节点信息。如果设置的邻居节点数据发送速率大于等于接收的数据速率，则全部转发接收的数据；如果记录的邻居节点的数据发送速率小于接收的数据速率，则按照比例转发。对于转发的数据，数据缓冲池保留一个副本，并记录转发时间。第27页/共187页3)路径加强阶段定向扩散路由机制通过正向加强机制来建立优化路径，并根据网络拓扑的变化修改数据转发的梯度关系。兴趣扩散阶段是为了建立源节点到汇聚节点的数据传输路径，数据源节点以较低的速率采集和发送数据，称在这个阶段建立的梯度为探测梯度(Probe Gradient)。汇聚节点在收到从源节点发来的数据后，启动建立到源节点的加强路径，后续数据将沿着加强路径以较高的数据速率进行传输。加强后的梯度称为数据梯度(Data Gradient)。假设以数据传输延迟作为路由加强的标准，汇聚节点选择首先发来最新数据的邻居节点作为加强路径的下一跳节点，并向该邻居节点发送路径加强消息。第28页/共187页路径加强消息中包含新设定的较高的发送数据速率值。邻居节点收到消息后，经过分析确定该消息描述的是一个已有的兴趣，只是增加了数据发送速率，则断定这是一条路径加强消息，从而更新相应兴趣表项中的到邻居节点的发送数据速率。同时，按照同样的规则选择加强路径的下一跳邻居节点。路由加强的标准不是唯一的，可以选择在一定的时间内发送数据最多的节点作为路径加强的下一跳节点，也可以选择数据传输最稳定的节点作为路径加强的下一跳节点。在加强路径上的节点如果发现下一跳节点的发送数据速率明显减小，或者收到来自其他节点的新位置的估计值，则推断加强路径的下一跳节点失效，这时就需要使用上述的路径加强第29页/共187页机制重新确定下一跳节点。定向扩散路由是一种经典的以数据为中心的路由机制。汇聚节点根据不同的应用需求定义不同的任务类型、目标区域等参数的兴趣消息，通过向网络中广播兴趣消息启动路由建立过程。中间传感器节点通过兴趣表建立从数据源到汇聚节点的数据传输梯度，自动形成数据传输的多条路径。按照路径优化的标准，定向扩散路由使用路径加强机制生成了一条优化的数据传输路径。为了动态地适应节点失效、拓扑变化等情况，定向扩散路由周期性地进行兴趣扩散、数据传播和路径加强三个阶段的操作。但是，定向扩散路由在路由建立时需要一个兴趣扩散的洪泛传播，它的能量消耗和时间开销都比较大，尤其是当底层MAC协议采用休眠机制时可能造成兴趣建立的不一致。第30页/共187页2.谣传路由在有些传感器网络的应用中，数据传输量较少或者已知事件区域，如果采用定向扩散路由，需要经过查询消息的洪泛传播和路径增强机制才能确定一条优化的数据传输路径。因此，在这类应用中，定向扩散路由并不是高效的路由机制。Boulis等人提出了谣传路由(Rumor Routing)，适用于数据传输量较少的传感器网络。第31页/共187页谣传路由机制引入了查询消息的单播随机转发，克服了使用洪泛方式建立转发路径带来的开销过大的问题。它的基本思想是：事件区域中的传感器节点产生代理(agent)消息，代理消息沿随机路径向外扩散传播，同时汇聚节点发送的查询消息也沿随机路径在网络中传播。当代理消息和查询消息的传输路径交叉在一起时，会形成一条汇聚节点到事件区域的完整路径。谣传路由的原理如图3-3所示，灰色区域表示发生事件的区域；圆点表示传感器节点，其中黑色圆点表示代理消息经过的传感器节点，灰色圆点表示查询消息经过的传感器节点；连接灰色圆点和部分黑色圆点的路径表示事件区域到汇聚节点的数据传输路径。第32页/共187页图3-3 谣传路由原理图 第33页/共187页谣传路由的工作过程如下：(1)每一个传感器节点维护一个邻居列表和一个事件列表。事件列表的每一个表项都记录了与该事件相关的信息，包括事件名称、到事件区域的跳数和到事件区域的下一跳邻居等信息。当传感器节点在本地监测到一个事件发生时，在事件列表中增加一个表项，设置事件名称、跳数(为零)等，同时根据一定的概率产生一个代理消息。第34页/共187页(2)代理消息是一个包含生命期等事件相关信息的分组，用来将携带的事件信息通告给它传输经过的每一个传感器节点。对于收到代理消息的节点，首先检查事件列表中是否有与该事件相关的表项，列表中存在相关表项就比较代理消息和表项中的跳数值，如果代理消息中的跳数小，就更新表项中的跳数值，否则更新代理消息中的跳数值。如果事件列表中没有与该事件相关的表项，就增加一个表项来记录代理消息携带的事件信息，然后，节点将代理消息中的生存值减1，在网络中随机选择邻居节点转发代理消息，直到它的生存值减小为0。通过代理消息在它的有限生存期的传输过程，形成一段到达事件区域的路径。第35页/共187页(3)网络中的任何节点都可能生成一个对特定事件的查询消息。如果节点的事件列表中保存有该事件的相关表项，则说明该节点在到达事件区域的路径上，它沿着这条路径转发查询消息。否则，节点随机选择邻居节点转发查询消息。查询消息经过的节点按照同样的方式转发，并记录查询消息中的相关信息，形成查询消息的路径。查询消息也具有一定的生存期，以解决环路问题。第36页/共187页(4)如果查询消息和代理消息的路径交叉，交叉节点会沿查询消息的反向路径将事件信息传送到查询节点。如果查询节点在一段时间内没有收到事件消息，就认为查询消息没有到达事件区域，可以选择重传、放弃或者洪泛查询消息。由于洪泛查询机制的代价过高，一般作为最后的选择。与定向扩散路由相比，谣传路由可以有效地减少路由建立的开销。但是，由于谣传路由使用随机方式生成路径，所以数据传输路径不是最优路径，并且可能存在路由环路问题。第37页/共187页3.1.4 地理位置路由无线传感器网络的许多应用都需要传感器节点的位置信息。例如，在森林防火的应用里，消防人员不仅要知道森林中发生了火灾事件，而且还要知道火灾的具体位置。地理位置路由是假设节点知道自己的地理位置信息，以及目的节点或者目的区域的地理位置，利用这些地理位置信息作为路由选择的依据，节点将按照一定的策略转发数据到目的节点。这样，利用节点的位置信息，就能够将信息发布到指定区域，有效地减少了数据传输的开销。第38页/共187页1.GEARGEAR(Geographic and Energy Aware Routing)是一种典型的地理位置路由协议。它根据实践区域的地理位置信息，建立汇聚节点到事件区域的优化路径，由于只需要考虑向某个特定区域发送兴趣消息，从而能够避免洪泛传播，减少路由建立的开销。GEAR路由假设已知事件区域的位置信息，每个节点知道自己的位置信息和剩余能量信息，并通过一个简单的“Hello”消息交换机制知道所有邻居节点的位置信息和剩余能量信息。在GEAR路由中，节点间的无线链路是对称的。GEAR要求每个节点维护一个预估路径代价(Estimated cost)第39页/共187页和一个通过邻节点到达目的节点的实际路径代价(Learned cost)。预估路径代价要结合节点的剩余能量和到目的节点的距离综合计算，实际路径代价则是对网络中环绕在“洞(Hole)”周围路由所需预估代价的改进。所谓“洞”现象，是指某个节点的周围没有任何邻节点比它到事件区域的路径代价更大。如果没有“洞”现象产生，那么预估路径代价就等于实际路径代价。每当一个数据包成功地到达目的地时，该节点的实际路径代价就要被传播到上一跳，以便对下一个数据包的路由建立调整。GEAR协议的运行包括以下两个阶段：第40页/共187页(1)向事件区域传送查询消息。从汇聚节点开始的路径建立过程采用贪婪算法。节点在邻节点中选择到事件区域代价最小的节点作为下一跳节点，并将自己的路径代价设置为该下一跳节点的路径代价加上到该节点一跳通信的代价。当有“洞”现象发生时，如图3-4所示，节点C是节点S的邻节点中到目的节点T代价最小的节点，但节点G、H、I为失效节点，节点C的所有邻节点到节点T的代价都比节点C大，这就陷入了路由空洞。可用如下办法解决这个问题，节点C选择邻节点中代价最小的节点B作为下一跳节点，并将自己的代价值设为节点B的代价值加上节点C到节点B的一条通信代价，同时将这个新代价通知节点S。当节点S再次转发查询命令到节点T时，就会选择节点B而不是节点C作为下一跳节点。第41页/共187页(2)查询消息在事件区域内传播。当查询消息传送到事件区域后，采用迭代地理路由转发策略。如图3-5所示，事件区域内首先受到查询命令的节点将事件区域分为若干子区域，并向所有子区域的中心位置转发查询命令。在每个子区域中，最靠近区域中心的节点(图3-5中的节点N)接收查询命令，并将自己所在的子区域再划分为若干子区域并向各个子区域中心转发查询命令。该消息的传播过程是一个迭代过程，当节点发现自己是某个子区域内唯一的节点，或者某个子区域没有节点存在时，则停止向这个子区域发送查询命令。当所有子区域转发过程全部结束时，整个迭代过程终止。第42页/共187页GEAR协议通过维护预估路径代价和实际路径代价对数据传输的路径进行优化，形成能量高效的路由。它所采用的贪婪算法是一个局部最优算法，适合于节点只知道局部拓扑信息的情况。其缺点是由于缺乏足够的拓扑信息，路由过程可能遇到“洞”现象，反而降低了路由效率。另外，GEAR假设节点的地理位置固定或者变化不频繁，适用于节点移动性不强的应用。第43页/共187页 图3-4 “洞”现象的解决办法 第44页/共187页图3-5 事件区域内的迭代地理转发 第45页/共187页2.GEM GEM(Graph Embedding)是一种适用于数据中心存储方式的地理路由，其基本思想是建立一个虚拟极坐标系统来表示实际的网络拓扑结构。由于汇聚节点将角度范围分配给每个子节点，例如0，90，每个子节点得到的角度范围正比于以该节点为根的子树大小。每个子节点按照同样的方式将自己的角度范围分配给它的子节点。这个过程一直持续进行，直到每个叶节点都分配到一个角度范围。这样，节点可以根据一个统一规则(如顺时针方向)为子节点设定角度范围，使得同一级节点的角度范围顺序递增或递减，于是到汇聚节点时，跳数相同的节点就形成了一个环形结构，整个网络则形成一个以汇聚节点为根的带环树。第46页/共187页GEM路由机制是当节点在发送消息时，如果目的节点位置的角度不在自己的角度范围内，就将消息传送给父节点；父节点按照同样的规则处理，直到该消息到达角度范围包含目的节点位置的某个节点，这个节点是源节点和目的节点的共同祖先。消息再从这个节点向下传送，直至到达目的节点，如图3-6(a)所示。上述算法需要上层节点转发消息，开销比较大，因此可作适当地改进，即节点在向上传送消息之前，首先检查邻节点是否包含目的节点位置的角度，如果包含，则直接将消息传送给该邻节点而不再向上传送，如图3-6(b)所示。更进一步的改进算法是利用前面提到的带环树结构，即节点检查相邻节点的角度范围是否离目的地的位置更近，如果更近就将消息传送给该邻节点，否则才向上层传送，如图3-6(c)所示。第47页/共187页图3-6 GEM路由机制 第48页/共187页GEM路由不依赖于节点精确的位置信息，所采用的虚拟极坐标的方法能够简单地将网络实际拓扑信息映射到一个易于进行路由处理的逻辑拓扑中，而且不改变节点间的相对位置。但是由于采用了带环树结构，实际网络拓扑发生变化时，树的调整比较复杂，因此GEM路由适用于拓扑结构相对稳定的无线传感器网络。第49页/共187页3.1.5 基于QoS的路由无线传感器网络的某些应用对通信质量有较高的要求，如可靠性高和实用性强等；而由于网络链路的稳定性难以保证，通信信道质量比较低，拓扑变化比较频繁，要在无线传感器网络中实现一定服务质量的保证，需要设计基于QoS的路由协议。第50页/共187页1.SPEEDSPEED协议是一种有效的可靠路由协议，在一定程度上实现了端到端的传输数率的保证、网络拥塞的控制以及负载的平衡机制。该协议首先在相邻节点之间交换传输延迟以得到网络负载的情况；然后利用局部地理信息和传输速率信息选择下一跳节点；同时通过邻居反馈机制保证网络传输畅通，并通过反向压力路由变更机制避开延迟太长的链路和“洞”现象的发生。SPEED协议主要由四部分组成。第51页/共187页(1)延迟估计机制。在SPEED协议中，延迟估计机制用来得到网络的负载状况，判断网络是否发生拥塞。节点记录到邻节点的通信延迟以表示网络的局部通信负载。具体过程是，发送节点给数据分组并加上时间戳；接收节点计算从收到数据分组到发出ACK的时间间隔，并将其作为一个字段加入ACK报文；发送节点收到ACK后，从收发时间差中减去接收节点的处理时间，得到一跳的通信延迟。第52页/共187页(2)SNGF算法。SNGF算法用来选择满足传输速率要求的下一跳节点。邻节点分为两类：比自己距离目标区域更近的节点和比自己距离目标区域更远的节点，前者称为“候选转发节点集合(FCS)”。节点计算到FCS集合中的每个节点的传输速率。FCS集合中的节点又根据传输速率是否满足预定的传输速率阈值，再分为两类：大于速率阈值的邻节点和小于速率阈值的邻节点。若FCS集合中有节点的传输速率大于速率阈值的，则在这些节点中按照一定的概率分布选择下一跳节点。节点的传输速率越高，被选中的概率越大。第53页/共187页(3)邻居反馈机制。当SNGF路由算法中找不到满足传输速率要求的下一跳节点时，为了保证节点间的数据传输满足一定的传输速率要求，引入邻居反馈机制(NFL)，如图3-7所示。由图3-7可知，MAC层收集差错信息，并把到邻节点的传输差错率通告给转发比例控制器。转发比例控制器根据这些差错率计算出转发概率，方法是节点首先查看FCS集合的节点，若某节点的传输差错率为0(存在满足传输要求的节点)，则设置转发概率为1，即全部转发；若FCS集合中所有节点的传输差错率大于0，则按一定的公式计算转发概率。第54页/共187页图3-7 邻居反馈机制 第55页/共187页对于满足传输速率阈值的数据，按照SNGF算法决定的路由传输给邻节点，而不满足传输速率阈值的数据则由邻居反馈机制计算转发概率。这个转发概率表示网络能够满足传输速率要求的程度，因此节点将按照这个概率进行数据转发。(4)反向压力路由变更机制。反向压力路由变更机制在SPEED协议中用来避免拥塞和出现“洞”现象。当网络中某个区域发生事件时，若节点不能够满足传输速率的要求，则体现在通信数据量突然增多，传输负载突然加大，此时节点就会使用反向压力信标消息向上一跳节点报告拥塞，以此表明拥塞后的传输延迟，上一跳节点则会按照上述机制重新选择下一跳节点。第56页/共187页2.SAR有序分配路由SAR(Sequential Assignment Routing)协议33也是一个典型的具有QoS意识的路由协议。该协议通过构建以汇聚节点的单跳邻节点为根节点的多播树来实现传感器节点到汇聚节点的多跳路径，即汇聚节点的所有一跳邻节点都以自己为根创建生成树，在创建生成树的过程中考虑节点的时延、丢包率等QoS参数的多条路径。节点发送数据时选择一条或多条路径进行传输。SAR的特点是路由决策不仅要考虑每条路径的能源，还要涉及端到端的延迟需求和待发送数据包的优先级。仿真结果表明，与只考虑路径能量消耗的最小能量度量协议相比，SAR的能量消耗较少。该算法的缺点是不适用于大型的和拓扑频繁变化的网络。第57页/共187页3.ReInForMReInForM(Reliable Information Forwarding using Multiple paths)34路由从数据源节点开始，考虑到可靠性要求、信道质量以及传感器节点到汇聚节点的跳数，决定需要的传输路径数目，以及下一跳节点数目和相应的节点，实现满足可靠性要求的数据传输。ReInForM路由的建立过程是，首先，源节点根据传输的可靠性要求计算需要的传输路径数目；其次，在邻节点中选择若干节点作为下一跳转发节点，并将每个节点按照一定的比例分配路径数目；最后，源节点将分配的路径作为数据报头中的一个字段发给邻节点，邻节点在接收到源节点的数据后，将自身视作源节点，重复上述源节点的选路过程。第58页/共187页3.1.6 路由协议自主切换前面已经提到过，传感器网络中的路由协议和具体的应用紧密相关，没有一个能适用于所有应用的路由协议。而传感器网络可能需要在相同的监测区域内完成不同的任务，此时如果为每种任务部署专门的传感器网络，将增加传感器网络的成本。为了能够适用于多种任务，传感器网络需要根据应用环境和网络条件自主选择适用的路由协议，并在各个路由协议之间自主切换。路由协议自主切换正是为了这个目的引入的。路由协议自主切换机制是根据应用变化自主选择合适的路由协议，并将这一过程封装起来，向上层应用提供统一的可编程路由服务。一个路由服务的通信模型如图3-8所示，上层通过路由服务接口配置路由服务，路由服务根据此配置以及具体网络情况自主选择合适的协议。第59页/共187页图3-8 路由服务通信模型 第60页/共187页Y.He 等人提出了一个可编程的传感器网络框架，包括了目前的主流路由协议。这个框架的体系结构如图3-9所示，路由服务将路由协议封装为状态收集模块和数据转发模块，并提供给上层一个统一的网络层接口。配置服务根据上层应用的要求为不同模块选择不同的路由协议，并将这些配置信息传达到整个网络，以保持路由协议在网络中的一致性。在路由服务中通过定义三种组件来描述路由协议：状态信息、访问模式和选路标准。状态信息用来搜集局部网络信息；访问模式描述路由的转发方式；选路标准描述下一跳节点的选择标准。这三种组件的具体内容见表3-1。第61页/共187页图3-9 可编程路由体系结构 第62页/共187页表3-1 路由配置组件及内容 第63页/共187页汇聚节点首先完成路由服务的配置，然后利用配置服务将路由配置信息传播到整个网络。配置服务通过洪泛或者受限洪泛的方法传送配置信息。为了减少传输的数据量，同时也为了减少其他节点配置路由的计算量，可将路由服务的一些公共部分，如状态信息收集、选路标准等做到操作系统中，这样只需要传送少量的配置信息即可，而且生成的路由协议代码量也比较少。由于无线传感器网络的信道错误率较高，同时MAC层的延迟比较长，所以如何保证路由配置在网络中的一致性也是一个重要的问题，可以通过使用配置版本机制实现一致性控制。第64页/共187页3.1.7 小结由于无线传感器网络资源有限且与应用高度相关，研究人员采用多种策略来设计路由协议，其中较好的协议应具有以下特点：针对能量高度受限的特点，高效利用能量几乎是设计的第一策略；针对包头开销大、通信能耗高、节点有合作关系、数据有相关性、节点能量有限等特点，采用数据聚合、过滤等技术；针对流量特征、通信耗能等特点，采用通信量负责平衡技术；针对节点少移动的特点，不维护其移动性；针对网络相对封闭、不提供计算等待点，只在Sink节点考虑与其他网络互连；针对网络节点不常编址的特点，采用基于数据或基于位置的通信机制；针对节点易失效的特点，采用多路径机制。通过对当前的各种路由协议进行的分析与总结，可以看出将来无线传感器网络路由协议采用的某些研究策略与发展趋势：第65页/共187页(1)减少通信量以节约能量。由于无线传感器网络中数据通信最为耗能，因此应在协议中尽量减少数据通信量。例如，可在数据查询或者数据上报中采用某种过滤机制，抑制节点上传不必要的数据；采用数据聚合机制，在数据传输到Sink节点前就完成可能的数据计算。(2)保持通信量负载平衡。通过更加灵活地使用路由策略让各个节点分担数据传输，平衡节点的剩余能量，提高整个网络的生存时间。例如，可在分层路由中采用动态簇头；在路由选择中采用随机路由而非稳定路由；在路径选择中考虑节点的剩余能量。第66页/共187页(3)路由协议应具有容错性。由于无线传感器网络节点容易发生故障，因此应尽量利用节点容易获得的网络信息计算路由，以确保在路由出现故障时能够尽快地得到恢复，并可采用多路径传输来提高数据传输的可靠性。(4)路由协议应具有安全机制。由于无线传感器网络的固有特性，其路由协议极易受到安全威胁，尤其是在军事应用中。目前路由协议很少考虑安全问题，因此在一些应用中必须考虑设计具有安全机制的路由协议。(5)无线传感器网络路由协议将继续向基于数据、基于位置的方向发展。这是无线传感器网络一般不统一编址和以数据、位置为中心的特点决定的。第67页/共187页3.2 无线传感器网络的链路层技术无线传感器网络除了需要传输层机制实现高等级误差和拥塞控制外，还需要数据链路层功能。总体而言，数据链路层主要负责多路数据流、数据结构探测、媒体访问和误差控制，从而确保通信网络中可靠的点对点(Point-to-Point)与点对多点(Point-to-Mul