《第三章无线传感器网络 通信与组网技术 网络层ppt课件.ppt》由会员分享，可在线阅读，更多相关《第三章无线传感器网络 通信与组网技术 网络层ppt课件.ppt（78页珍藏版）》请在三一办公上搜索。
1、第3章,传感器网络的通信与组网技术,2,3.3 路由协议,3.3.1 路由协议概述,因特网 (Internet),数据传输路径,路由器,分组交换网的示意图,H1,A,互联网,B,D,E,C,H5,H6,H4,H2,H3,H1 向 H5 发送分组,H2 向 H6 发送分组,注意分组路径的变化！,路由器,主机,网络层, 负责对在传输层协议控制下建立的连接或者会话中的每个数据包进行寻址和路由。, 在网络层，消息将被分解为多个数据包，每个数据包都带有源端和目的端的地址。, 网络层用于在一个站点与另一站点之间传输数据包。,路由协议特点：寻找最佳路径，提高网络利用率，避免通信堵塞，均衡网络流量，不考虑能耗
2、。,5,WSN路由协议概述,在无线传感器网络中,由于受能量限制，节点之间往往无法直接通信，通常需要借助中间节点以多跳路由的方式将源数据传送至目的节点。,无线传感器网络是一种信息采集网络, 自组织通信是其中实现多跳的信息回传和进行网络,控制的手段。, 为了实现信息采集，无线传感器网络的业务大都发生在数据汇聚节点（Sink）和普通传感器节点之间 下行业务：包括Sink节点到传感器节点的下行业务（如查询指令下达）, 上行业务：传感器节点到Sink的上行业务（如采集信息的回传)；, 传感器节点之间的横向业务所占比例较小，主要是,网络的控制信息和网内信息处理所需要的信息,7,WSN路由协议功能,无线传感
3、器网络的网络层主要负责路由的发现和维护。 路由选择是指选择互连网络从源节点向目的节点传输信息的行为，并且信息至少通过一个中间节点。 路由协议负责将数据分组从源节点通过网络转发到目的节点，它包括两个功能： 路径选择：寻找源节点和目的节点间的优化路径； 数据转发：将数据分组沿着优化路径正确转发。,WSN路由协议定义及设计目标,WSN路由协议：一套将数据从源节点传输到目的节点的机制 。,设计目标： 满足应用需求低网络开销 资源利用的整体有效性网络高吞吐率,9,与传统网络的路由协议相比，无线传感器网络的路由协议具有以下特点：,（1）能量优先（2）基于局部拓扑信息（3）以数据为中心（数据冗余性）（4）应
4、用相关,WSN路由协议特点,10,（1）能量优先,由于传感器节点的能量非常有限，无线传感器网络路由协议设计的一个重要目标便是延长整个网络的生存时间，因此必须考虑节点的能量消耗和网络能量均衡使用的问题。路由协议设计要求：协议简单、节省能量、均衡消耗,11,（2）基于局部拓扑信息,为了尽量节省通信能量，无线传感器网络路由协议通常采用多跳的通信模式，而网络中节点数目通常较多，节点资源有限，使得节点无法存储大量的路由信息。无线传感器网络的一个基本问题就是，如何在节点只能获取局部拓扑信息和能量有限的情况下，实现简单高效的路由机制。,12,（3）以数据为中心,无线传感器网络关注的是监测区域内的感知数据及其
5、位置，而不是具体由哪个节点获取的信息。传感器网络通常包含多个传感器节点到少数汇聚节点的数据流，按照对感知数据的需求、数据通信模式和流向等，以数据为中心形成消息的转发路径。传感器网络路由中使用数据融合技术,13,（4）应用相关,无线传感器网络是和应用相关的网络，其应用环境千差万别，数据通信模式不同，没有一个路由机制能够适合所有的应用；在设计路由协议时需要针对每一个具体应用的需求，设计出合适应用的特定路由。,14,在根据具体应用设计路由协议时，必须满足如下要求：,（1）能量高效（2）可扩展性（3）稳健性（4）快速收敛性,15,1）能量高效,传感器网络路由协议设计最重要的优化目标是能量高效性，路由过
6、程中不仅要选择能量消耗小的消息传输路径，而且要针对整个网络的情况选择使整个网络能量均衡消耗的路径。传感器节点能量有限，传感器网络的路由机制要能够简单而且高效地实现信息传输。,16,2）可扩展性,能量限制、环境干扰和人为破坏等因素造成传感器节点的损坏失效，以及新结点加入和结点移动，使网络拓扑结构动态变化，要求路由机制具有扩展性，能适应网络的动态变化。,17,3）快速收敛性,传感器节点能量和通信带宽资源有限，网络拓扑结构动态变化等这些不确定因素要求路由机制能够快速收敛；适应网络拓扑动态变化，减少通信协议开销，提高消息传输的效率。,18,4）数据处理技术,为了减少数据通信量，转发结点在传输数据过程中
7、经常将不同的入口报文融合成数目更少的出口报文转发给下一跳，这就是数据融合的基本涵义。采用数据融合技术意味着路由协议需要做出相应的调整。,19,5）鲁棒性,传感器网络中，链路稳定性难于保证，通信信道质量较低，拓扑变化较频繁，路由协议会遇到各种非正常或不可预料的网络环境，路由器节点一旦出现故障将可能会影响整个网络。传感器网络本身的不可靠性希望其路由机制具有一定的容错能力。好的路由协议应该具备较强可靠性，能够通过各种网络环境下的测试验证。,20,6）优化能力,网络资源状况随时会发生变化，传感器网络路由协议需要具备能够依据当前网络资源状况选择最合适路径的能力。,21,我们从各种应用的角度出发，将路由协
8、议分为四类：,（1）能量感知路由协议,高效利用网络能量是传感器网络路由协议的一个显著特征。为了强调高效利用能量的重要性，这里将它们划分为能量感知路由协议。能量感知的路由协议从数据传输的能量消耗出发，讨论最少能量消耗和最长网络生存期等问题。典型协议：Energy aware routing，GEAR,等,路由协议分类,22,（2）以数据为中心的路由-基于查询的路由协议,在环境检测、战场评估等应用中，需要不断查询传感器节点采集的数据。在汇聚节点（查询节点）发出任务查询命令，传感器网络的终端探测节点向监控中心报告采集的数据。 这类应用中，通信流量主要是查询节点和传感器探测节点间的命令和数据传输，传感
9、器探测节点的采集信息通常要进行数据融合，通过减少通信流量来节省能量，即数据融合技术与路由协议的设计相结合。,以数据为中心的平面路由, 传统网络作为以通信为目的的对等网络，所使用的路由协议通常以地址作为节点的标识和路由依据 ，完成任意两个节点间的通信任务。, 而无线传感器网络作为以数据收集为目的的数据汇聚型网络，所关注的是节点监测区域的感知数据 ，而不是具体哪个节点获取的信息。, 一般传感器网络将大量节点的随机部署，网络中通常包含多个传感器节点与少数汇聚节点的数据流，按照对感知数据的要求，数据通信模式和流向等，以数据为中心形成消息的转发路径。,DC，Data-centric,AC，Address
10、-centric,地址中心网络和数据中心网络,DC网络可进行数据融合，减少网络中的数据量, 平面路由中所有节点具有相同的地位和功能，节点间协同工作完成感知任务。 由于节点数量庞大，分布密度高，相邻节点间的数据采集又大多面向同一监测点，因此在传输数据时会经常出现冗余现象。 需要构建以数据为中心的平面路由协议，即汇聚节点向某些区域发送查询并等待来自于这些区域内的节点所采集的相关数据。,以数据为中心的平面路由,平面路由的特点:结构简单,鲁棒性较好缺乏对通信资源的优化管理，对网络动态变化的反应速度较慢典型协议：DD，Rumor-routing，TTDD，支持查询的近似路由算法等,以数据为中心的平面路由
11、,如下：汇聚节点只对温度高于21的地区感兴趣。因此，传感器读数符合此要求的节点会被处理。,以数据为中心的路由-举例,（a）温度无线传感器,以数据为中心的路由,（b）汇聚结点初始化一个查询（t70F）,以数据为中心的路由-举例,（C）匹配读数的结点被定位,以数据为中心的路由,（d）产生路由,29,（3）地理位置路由协议,在目标跟踪的应用问题中，需要唤醒离被跟踪目标最近的传感器节点，以便得到关于目标的更精确位置等相关信息。 这类与坐标位置有关的应用问题中，需要知道目的节点的精确或者大致地理位置。把节点的位置信息作为路由选择的依据，不仅能够完成节点的路由选择功能，还可以降低系统专门维护路由协议的能耗
12、。,地理位置信息的路由协议, 在前面介绍的路由协议中，节点仅仅知道自己的逻辑名称（如地址信息等），通过路由探测可以获得网络节点之间的连接关系和链路特征，由此确定路由。, 随着定位技术的发展，节点可以方便地获得自己的地理位置信息， 利用位置信息，可以改善WSN路由协议的性能，研究使用地理位置信息的路由是一项很有意义的工作。,地理位置信息的路由协议, 无线传感器网络中很多应用都和节点的位置信息有关。某些应用必须知道节点的位置信息后，传感器节点采集的数据才有真正的价值和意义，如水源监测和河流保护、森林防火及煤矿安全事故预警监测等。, 例如，在森林防火的应用里，消防人员不仅要知道森林中发生了火灾事件，
13、而且还要知道火灾的具体位置。, 地理位置信息既可用于寻找达到基站或汇聚节点的最短路径，又可用于形成虚拟的网络，使得一次只有少量的节点处于激活工作状态。,地理位置路由, 地理位置路由假设：,节点知道自己的位置信息，也知道目的节点和目的监测区域的地理位置。利用这些地理位置信息作为路由选择的依据，节点按照一定的策略转发数据到目的节点。, 利用节点的位置信息，就能够将信息发布到指定区域，有效减小了数据传输的开销。,地理位置信息的路由协议,下列方法可确定节点位置,GPS(Global Positioning System)超声波三角定位系统信标定位,用途,作为其它路由算法的辅助直接用于路由的计算,典型协
14、议：基于地理位置的距离贪心路由协议，基于地理位置的角度贪心路由协议，GEM、MAP、 LCR等,34,（4）可靠的路由协议,传感器网络的某些应用对通信的服务质量有较高要求，可能在可靠性和实时性等方面有特别要求。 采用视频传感器进行战场环境监测时，希望传输的视频图像能够尽可能的流畅些。 传感器网络的无线链路稳定性一般难以保证，通信信道质量比较低，网络拓扑变化频繁，要考虑可靠的路由协议设计技术来满足这些的服务质量指标。,为止。,协议内容：1、一节点S希望发送一块数据给节点D，节点S首先通过网络将数据副本传送给它的每一个邻居节点，每一个邻居节点又将其传输给各自的每一个邻居节点，除了刚刚给它们发送数据
15、副本的节点S外。2、如此继续下去，直到将数据传输到目标节点D为止或者为该数据所设定的生命期限（在传感器网络里面通常定义为最大跳数）变为零为止或者所有节点拥有此数据。,洪泛法(Flooding)是一种传统的网络路由协议，不需要知道网络拓扑结构和使用任何路由算法。,1、洪泛路由(Flooding),3.3.2 典型路由协议,为止。,不足：存在信息爆炸(Implosion)问题，即出现一个节点可能得到一个数据多个副本的现象出现部分重叠(Overlap)现象，如果处于同一观测环境的两个相邻同类传感器节点同时对一个事件作出反应，二者采集的数据性质相同，数值相近，那么，这两个节点的邻居节点将收到双份数据副
16、本,优点：实现简单不需要为保持网络拓扑信息和实现复杂的路由发现算法而消耗计算资源适用于健壮性要求高的场合,洪泛路由(Flooding),Flooding 的Implosion (内爆）和overlap（重叠）,2、Gossiping路由协议,Gossiping协议是对Flooding协议的改进当节点收到数据包时，只将数据包随机转发给与其相邻的节点的某一个节点或几个，而不是所有节点。当相邻节点收到数据包时，也采用同样的办法转发给与其相邻某一个节点。,38,Gossiping路由协议优缺点,优点：就降低了数据转发重叠的可能性，避免了信息内爆现象的产生; 缺点：点到点的时延较大由于随机转发某一个节点
17、的方向并不一定在距离目的节点更近的方向上，因此容易造成数据到达目的节点时间过长或者跳数己达到最大，而数据还没有到达目的节点，造成传递失败。刚开始的很短的时间内发送速率很大，但是随着数据的发送，速度会明显降低，而且它并不能很好解决重叠问题。,39,3、SPIN,该协议是最早的一类WSN路由协议的代表，是对Flooding协议的改进 考虑到WSN的数据冗余，临近节点所感知的数据具有相似性，通过节点间协商方式减少数据传输量，只广播其他节点没有的数据,SPIN中的元数据（meta-data）,元数据：对节点感知数据的抽象，是原始感知数据的压缩，可以描述原始感知数据 （传元数据可以节省能耗） SPIN协
18、议有两种工作模式：SPIN1和SPIN2，（SPIN2在SPIN1 的基础上考虑了节点剩余能量） SPIN采用三次握手机制，有三种分组：ADV（相当于数据的索引，很短）、REQ、DATA,SPIN,协商通过元数据进行元数据描述实数据元数据与实数据一一对应协议消息消息广播包：Advertise (ADV)数据请求包：Request (REQ)数据包：Data transfer (DATA),3步握手协议,A,A,A,A,A,A,（1）节点A有新数据，通过ADV发布新数据信息，使用元数据（2）B节点收到ADV后，发现自己没有该数据，通过REQ向A请求新数据（3）A节点向B节点传送源数据（4）B节点
19、融合新数据，并通过ADV发布新数据消息（5）如果其他节点有ADV中描述的数据的副本就忽略该消息；若没有，就发送REQ请求数据（6）B结点发送数据整个网络中对此数据感兴趣的结点都将收到此数据。,SPIN协议工作流程,SPIN,3步握手协议(ADV-REQ-DATA)通过和邻居节点的协商来减少Flooding带来的内爆SPIN利用数据融合（DC），部分解决了重叠问题通过元数据来完成协商过程元数据：一种对源数据的映射，比源数据短避免传输冗余数据SPIN-2在SPIN-1的基础上加入了能量阈值当一个节点的剩余能量低于能量阈值后，减少其在协议中参与的活动。,SPIN2模式考虑了剩余能量值，当节点能量值低
20、于某个门限值时，该节点就不再参与DATA报文的转发，只是接收报文和发出REQ报文，进一步降低了能耗 模拟结果表明，SPIN2比传统方式节省能耗一半以上,SPIN协议评价,优点解决了内爆问题和部分解决了重叠问题不需要进行路由维护对网络拓扑变化不敏感，可用于移动WSN缺点本质上SPIN还是向全网扩散新消息，开销比较大 当多个节点向同一个节点同时发送REQ时，需要退避算法,47,4、定向扩散路由,定向扩散（Directed Diffusion，DD）路由协议,基于查询的路由协议, 在诸如环境监测、战场评估等应用中，汇聚节点（Sink)发出任务查询命令，传感器节点向汇聚节点报告采集的数据。, 通信流量
21、主要是汇聚节点和传感器节点之间的命令和数据传输 ，同时 传感器节点要在传输路径上进行数据融合 ，通过减小通信流量来节能。,48,定向扩散路由,扩散节点通过兴趣信息发出查询任务，采用洪泛方式传播兴趣信息到整个区域或部分区域内的所有传感器节点。兴趣信息用来表示查询的任务，表达了网络用户对监测区域内感兴趣的具体内容，例如监测区域内的温度、湿度和光照等数据。, DD中采用了 以数据为中心的查询机制。, 查询是通过定期全网广播兴趣包来实现的，如果查询频率过高，会引起广播风暴问题，造成能量的快速消耗。,定向扩散模型DD, 定向扩散模型DD是一种以数据为中心的信息传播协,议，是专门为无线传感器网络设计的路由
22、策略, 主要思想:,将来自于不同源节点所发送的数据聚合起来, 目的：,减少数据冗余,缩减数据被传递的大小和次数,保存网络能量和延长网络生命周期, 运行DD的传感器节点使用基于属性的命名机制来描述,数据,50,定向扩散路由,在兴趣信息的传播过程中，协议将逐跳地在每个传感器节点上建立反向的从数据源到汇聚节点的数据传输梯度，传感器探测节点将采集到的数据沿着梯度方向传送给汇聚节点。,51,定向扩散路由机制可以分为周期性的兴趣扩散、梯度建立和路径加强三个阶段:,（a）兴趣扩散 （b）梯度建立 （c）路径增强,52,（1）兴趣扩散阶段,兴趣扩散阶段，汇聚节点周期性地向邻居节点广播兴趣消息。兴趣消息中含有任
23、务类型、目标区域、数据发送速率、时间戳等参数。 各节点在本地保存一个兴趣列表，对每个兴趣内容，列表中都有一个表项记录发来该兴趣消息的邻居节点、数据发送速率和时间戳等任务相关信息，以建立该节点向汇聚节点传递数据的梯度关系。每个兴趣可能对应多个邻居节点，每个邻居节点对应一个梯度信息。,53,（2）数据传播阶段,当传感器探测节点采集到与兴趣匹配的数据时，把数据发送到梯度上的邻居节点，并按照梯度上的数据传输速率，设定传感器模块采集数据的速率。 由于可能从多个邻居节点收到兴趣消息，节点向多个邻居发送数据，汇聚节点可能收到经过多个路径的相同数据。,54,（3）路径加强阶段,定向扩散路由机制通过正向加强机制
24、来建立优化路径，并根据网络拓扑的变化来修改数据转发的梯度关系。,55,两种梯度,兴趣扩散阶段建立的梯度为探测梯度,加强后的梯度成为数据梯度,兴趣消息（interest）, Sink节点周期性查询兴趣消息, 兴趣消息采用泛洪的方法传播到网络兴趣扩散阶段建立节点到Sink的路径有和兴趣匹配数据的节点发送数据, 兴趣消息，由属性值对组成 ：, 查询内容（温度、湿度等）, 查询要求（如上报间隔、持续时间等）,type = four-legged animal / detect animal locationinterval = 20 ms / send back events every 20 msd
25、uration = 10 seconds / . for the next 10 seconds,rect = -100, 100, 200, 400 / from sensors within rectangle,兴趣转发, 邻居更新自己的兴趣cache，并且转发 兴趣cache中的条目,时间戳：指示接收到相关兴趣消息的最近时间若干梯度域：每个梯度和其邻居节点相关联,每个梯,度中含有一个指定的数据传输率持续时间：该兴趣消息的有效期,网络梯度, 在兴趣消息的传播过程中，协议逐跳地在每个节点上建立反向的从数据源到汇聚节点的数据传输梯度。, 信息梯度类似于反向路由条目（从当前节点到Sink的路由）
26、，它既包含了下一跳节点（发来查询的相邻节点）和时间戳，也包含了信息采集相关的内容（如数据采集内容、采集速率等）,网络梯度, 节点用一组标量值表示它的选择，值越大意味着向该方向继续搜索获得匹配数据的可能性越大，匹配数据可以沿“梯度”最大的方向中继回Sink节点。 Sink节点发出的查询业务也用属性的组合表示,逐级扩散,最终遍历全网,找到所有匹配的原始数据.,DD（Directed Diffusion）路由,定向扩散路由举例-Interest的传播,Interest的任务命名（naming）,Interests的区分和汇聚,Interests缓存,定向扩散路由举例-路径梯度（Gradient）,定
27、向扩散路由举例-加强（reinforced）路径,路径加强, 查询发出一段时间后，sink开始从多条路径收到回传的信息。, 此时，它从中选择最优路径（如回传信息的时延最小），向相应的相邻节点发送“路径加强”消息。, “路径加强”消息也是一个查询命令，与前一个不同的是它包含了更大的信息采集速率。“路径加强”消息沿最优路径逐跳传输到被查询的传感器节点，这条路径成为“主路径”，而其他路径相应的成为备用路径。 传感器节点接收到“路径加强”消息后，根据要求提高信息采集速率。,68,路径加强的标准,路径加强的标准不是唯一的。,吞吐量：在一定时间内发送数据最多的结点稳定性：数据传输最稳定的结点传输时延：首先
28、发来最新数据包的结点,选择,作为,路径加强的下一跳结点,定向扩散协议评价,优点,数据中心路由，定义不同任务类型/目标区域消息；路径加强机制可显著提高数据传输的速率；周期性路由：能量的均衡消耗；,缺点,周期性的洪泛机制: 能量和时间开销都比较大； 尤其是当底层MAC协议采用休眠机制时，有时可能造成兴趣建立的不一致；节点需要维护一个兴趣消息列表，代价较大；,平面结构路由算法的缺点,每个节点直接和Sink节点通信节点能量消耗过大节点密度较大时冲突过大，效率低,集群结构路由原理,集群结构路由协议实际是分层结构路由协议，网络划分为多个簇，每个簇由一个簇头和簇成员组成，这些簇头形成高一级网络，在高一级网络
29、中，可以再一次分簇，形成更高一级网络簇头管理簇内节点，收集和融合簇内信息和簇间数据的转发。优点：扩展性好，适宜大规模网络,典型的集群结构路由协议,LEACH : Low-Energy Adaptive ClusteringHierarchy低功耗自适应分簇协议,LEACH算法,LEACH算法：最早的一种分层路由算法，主要考虑簇内节点能耗簇头作为一定区域所有节点的代理，负责和Sink的通信；非簇头节点可以使用小功率和簇头节点通信；簇头节点可以对所辖区域节点数据进行融合，减少网络中传输的数据；簇头选举算法的设计，要求保证公平性,关键问题,使用Leach协议后，形成两级星形结构簇内节点与簇头距离近，
30、功耗小；簇头进行数据融合，减少通信量 簇头消耗大量能量，所以定期选举簇头,簇头选举算法,每个传感器节点选择0，1之间的一个随机数，如果选定的值小于某一个阈值T（n），那么这个节点成为簇头节点，阈值计算如下： p=网络中的簇头节点数/网络中传感器节点的个数，p是成为簇头的概率，r为当前的轮数，G为在上一个1/P轮循环中未当选过簇头的结点的集合。,LEACH算法工作原理,网络按照周期工作，每个周期分为两个阶段：簇头建立阶段：节点运行算法，确定本次自己是否成为簇头（选簇）；簇头节点广播自己成为簇头的事实；其他非簇头节点按照信号强弱选择应该加入的簇头，并通知该簇头节点；簇头节点按照TDMA的调度，给依附于他的节点分配时间片；数据传输阶段：节点在分配给他的时间片上发送数据；,LEACH算法评价,优点优化了传输数据所需能量；优化了网络中的数据量（簇头数据融合）；缺点节点硬件需要支持射频功率自适应调整；无法保证簇头节点能遍及整个网络；分簇与簇头选举 要公平,78,小结,路由协议的概念、功能WSN路由协议的特点WSN路由协议的分类定向扩散路由协议的三个阶段，以及优缺点,
