《无线传感器网络路由协议ppt课件.ppt》由会员分享,可在线阅读,更多相关《无线传感器网络路由协议ppt课件.ppt(43页珍藏版)》请在三一办公上搜索。
1、无线传感器网络的路由协议,路由协议概述,无线传感器网络的路由协议主要任务是确保数据由源节点准确高效地传输到目的节点,即寻找数据的最优路径以及沿最优路径发送数据。,能耗:WSN中,路由协议的制定受能耗的限制。邻居发现过程:邻居节点间交换信息会消耗能量,交换数据越大,能耗越大。处理过程:数据传输过程的计算和通信会消耗能量,通信的能耗大于计算。,可扩展性:路由协议需能满足网络拓扑形态的变化,即使发生变化,节点也能有效把握网络传输路径情况。,编址:用户对来自多个节点的整合后信息感兴趣,而非单个节点,因此唯一编址方式不适合WSN,健壮性:防止由于部分节点故障失效造成的信息丢失,以及信道不稳定造成的信息受
2、损和丢失。,路由协议概述,拓扑:路由协议需能适应WSN的拓扑变化。预订拓扑:节点相对固定,可实现高效路由协议。随机拓扑:网络自组织,可利用拓扑发现作为路由计算的前提,路由协议也需适应节点或观测目标的移动。,设计目的:网络的目的(上层应用)的不同导致路由协议原则的不同。,路由协议概述,WSN路由协议的分类,能量感知路由,WSN网络是能量受限的网络,节省能量是路由设计需考虑的重要因素。能量路由是WSN最基本的路由协议之一能量路由是根据节点可用能量(Power Available,PA)或传输路径上的能量需求(E),选择数据的转发路径。节点可用能量就是节点当前的剩余能量。,基本能量路由,能量感知路由
3、,基本能量路由,路径1:源BA目标,PA=4,E=3;路径2:源CBA目标,PA=6,E=6;路径3:源D目标,PA=3,E=4;路径4:源FE目标,PA=5,E=6。最大PA路由:路径2最小能耗路由:路径1最少条数路由:路径3最大平均路由:路径4,能量感知路由,能量多径路由,能量多径路由基本思想在源节点和目标节点之间建立多条数据传输路径根据每条路径上节点的剩余能量和传输消耗的能量来给每条路径赋予一定的选择概率依概率在多条路径中选择传输路径,均衡消耗节点能量,延长网络生存期,传统能量路由频繁通过某一路径传输数据,易导致该路径上节点能量消耗过快,节点提早失效。,能量感知路由,能量多径路由,路径建
4、立建立从源节点到目的节点的多条路径计算出各条路径的选择概率,主要过程,数据传输对于接收到的每组数据,节点根据概率从所有下一跳节点中选择一个节点,路由维护周期性从目的节点到源节点进行洪泛查询以维护路径的有效性和活跃性,能量感知路由,能量多径路由,路径建立具体过程,目的节点向邻居广播路径建立消息,邻居收到消息,如处于目的节点和源节点之间则转发,否则丢弃,如节点决定转发(加入路由集合),则更新转发消息中的代价值,如选择某一邻居代价太高,则放弃选择,路由集合中的节点计算下一跳各选择的概率,概率与代价成反比,节点根据选择概率和能量消耗计算自己到目的节点的传输代价,泛洪是一种传统的路由技术。泛洪算法的主要
5、思想是由某节点发起数据广播,然后任意一个收到广播的节点都无条件将该数据包广播出去,每一节点都重复这样的过程直到数据遍历全网或者达到规定的最大跳数。数据包像洪水一样漫过所有地方,因此称为洪泛协议。算法不用维护网络拓扑结构和路由计算,实现简单。但是最主要的是内爆和重叠以及资源盲点等。,洪泛(Flooding)协议,以数据为中心的路由协议,洪泛(Flooding)协议,以数据为中心的路由协议,内爆现象:洪泛机制允许大量冗余消息,节点会收到来自多个邻居节点转发的相同消息。,重叠现象:监测同一区域的节点容易产生相同的信息,造成传播过程中的信息冗余,消耗大量能量。,谣言协议是对洪泛协议的改进。当节点收到数
6、据包时,只将数据包随机转发给与其相邻的节点的某一个节点或几个,而不是所有节点。选定的邻居也采用同样的办法转发下去。优点:降低数据转发重叠的可能性,减少内爆现象的发生。缺点:点到点的时延较大随机转发某一个节点的方向并不一定在距离目的节点更近的方向上,易造成数据超时或者跳数己达最大,导致递送失败。开始的短时间内发送速率很大,随着数据的发送,速度明显降低。,谣言(Gossiping)协议,以数据为中心的路由协议,SPIN协议,以数据为中心的路由协议,信息协商传感器(SPIN)协议是 最基本的一类WSN路由协议,是对Flooding协议的改进。考虑到WSN的数据冗余,临近节点所感知的数据具有相似性,通
7、过协商和能量自适应来减少数据传输量,解决洪泛协议存在的不足。SPIN协议采用了两种机制:在数据发送前通过协商确定是否发送 节点监测自己的能量并进行能量感知决策SPIN协议假定两点间的通信不受到其他节点的干扰,分组不会丢失,功耗无限制进。SPIN协议包括三种类型的消息:广告消息(Advertise,ADV)、请求发送消息(Request,REQ)、数据消息(Data transfer,DATA),SPIN协议,以数据为中心的路由协议,三次握手机制(点对点模式,即SPIN-PP)节点A向邻居B发送ADV,ADV消息对DATA消息进行了描述。如果B对DATA消息感兴趣,则发送REQ消息给A节点。A收
8、到REQ后,将DATA消息发送给B节点。,SPIN协议,以数据为中心的路由协议,三次握手机制(点对多点模式)节点B向多个邻居节点发送ADV。有部分收到ADV的节点对DATA感兴趣,回复REQ。B节点向回复REQ的节点发送DATA。,SPIN协议,以数据为中心的路由协议,SPIN-EC机制(在SPIN基础上加入能量感知功能)当一个节点的可用能量低于阈值,该节点不参与DATA消息的转发。低能量节点只接收消息。通过减少参与转发活动,能耗可降低10%。,SPIN协议,以数据为中心的路由协议,SPIN-BC机制当一个节点发送REQ时,其他节点可以听到此与DATA有关的REQ,则放弃此次发送REQ等待DA
9、TA消息。源节点收到REQ,会将DATA广播出去,感兴趣的节点可以收到这个DATA。,SPIN-RL机制如一节点对DATA感兴趣,但由于信道错误等原因,未收到DATA消息。该节点可以向其他可能收到DATA消息的邻居节点发起传输请求,获得DATA消息。,优点解决了内爆问题和部分解决了重叠问题不需要进行路由维护对网络拓扑变化不敏感,可用于移动WSN缺点本质上SPIN还是向全网扩散新消息,开销比较大 当多个节点向同一个节点同时发送REQ时,需要退避算法,SPIN协议,以数据为中心的路由协议,定向扩散协议,以数据为中心的路由协议,定向扩散(Directed Diffusion)协议:汇聚节点接到上层应
10、用的查询任务后,将兴趣消息通过洪泛方式周期性地广播出去,即告诉其他节点我要收集什么兴趣。在传输过程中建立从数据源节点到汇聚节点的传输梯度。在区域内“兴趣”匹配节点沿着梯度方向通过路径传送数据到汇聚节点。四个阶段:兴趣扩散(采用泛洪);梯度建立(反向建立);强化路径(汇聚节点会收到多条路径,选最优路径,进行加强,以后的数据按照加强路径传送)数据传输,汇聚节点向全网查询兴趣,邻居节点更新自己的兴趣缓存,并且转发兴趣缓存中的条目(兴趣表项)时间戳:指示接收到相关兴趣消息的最近时间梯度:当前节点从哪个邻居收到兴趣消息以及相应的数据传输率 持续时间:该兴趣消息的有效期,定向扩散协议,以数据为中心的路由协
11、议,路径增强:在多条对应的梯度路径中,汇聚节点可以对某一条路径经行梯度增强。沿这条路径再次发送兴趣消息当前节点选定下一跳,兴趣消息只会发送给选定的下一跳节点逐跳传导下去,即形成一条专门的路径,定向扩散协议,以数据为中心的路由协议,反向路径增强:如之前的某条路径遭到破环,汇聚节点需“增强”另一条路径就可以改变数据的路由向之前的路径发送反向增强消息,抑制节点使用之前路径传输数据GBR路由(Gradient-Based Routing)协议:梯度域扩展(传感器节点到Sink节点的跳数信息、无线链路评估信息)EAR(Energy Aware Routing)路由协议:建立路由过程中加入能量评估机制;路
12、由路径的能量开销大于某一阈值不采用;CADR路由(Constrained Anisotropic Diffusion routing)协议:兴趣消息往指定方向发送,定向扩散协议,以数据为中心的路由协议,定向扩散协议,以数据为中心的路由协议,优点数据中心路由,定义不同任务类型/目标区域消息;路径加强机制可显著提高数据传输的速率;周期性路由:能量的均衡消耗;缺点周期性的洪泛机制-能量和时间开销都比较大;Sink周期性广播,不适用于大规模网络 节点需要维护一个兴趣消息列表,代价较大;,分层路由协议,分层路由基本思想网络划分为多个簇,每个簇由簇头和簇成员组成簇头组成更高一级的网络,簇头管理簇内节点,收
13、集融合簇内信息簇头节点间还可以再次分簇分层结构扩展性较好,适合大规模网络使用,扁平结构路由协议容易使汇聚节点及周围形成性能瓶颈,加重这些节点能量消耗,缩短网络生命周期。,LEACH协议,分层路由协议,LEACH协议是最早最基本的一种分层路由算法,主要考虑簇内节点能耗使用Leach协议后,形成两级星形结构簇头作为一定区域所有节点的代理,负责和Sink的通信簇头节点可以对所辖区域节点数据进行融合,减少网络中传输的数据;簇内节点与簇头距离近,使用小功率与簇头节点通信,功耗小簇头消耗大量能量,所以定期选举簇头,簇头选举算法的设计,要求保证公平性,LEACH协议,分层路由协议,网络按照周期工作,每个周期
14、分为两个阶段:簇头建立阶段:节点运行算法,确定本次自己是否成为簇头(选簇);簇头节点广播自己成为簇头的事实;其他非簇头节点按照信号强弱选择应该加入的簇头,并通知该簇头节点;簇头节点按照TDMA的调度,给依附于他的节点分配时隙;稳定工作阶段:节点在分配给他的时隙上发送数据;,LEACH协议,分层路由协议,稳定工作阶段:只有簇头节点一直保持活跃状态 簇成员节点按需要保持活跃或者在不发送数据时进入睡眠状态稳定工作状态结束后,所有节点进入下一周期,重新建立簇并通信,优点每个节点都有机会担任簇头,能耗平均消耗;优化了传输数据所需能量;优化了网络中的数据量(簇头数据融合);延长了网络寿命;缺点节点硬件需要
15、支持射频功率自适应调整;无法保证簇头节点能遍及整个网络;分簇与簇头选举 要公平,LEACH协议,分层路由协议,PEGASIS协议,分层路由协议,PEGASIS协议是对于LEACH的一种改进,节点间不再组成簇,而是组成链PEGASIS协议基本原理:1.假定传感器节点是同构和相对静止的 2.节点通过发送能量递减的测试信号,确定相邻节点的位置 3.进而了解网络的全局信息 4.节点选择其最近的邻居作为链上的下一跳 5.节点只需维护自己上一跳和下一跳的邻居信息,PEGASIS协议,分层路由协议,链上的通信按照节点顺序进行,下一跳节点汇聚来自上一跳的数据,直到链头汇聚了链上所有节点的数据链头节点通过传递令
16、牌来控制节点间的通信次序,PEGASIS协议,分层路由协议,优点不需要周期性选举簇头节点;采用最佳链路进行数据传输;采用数据融合技术,减少了整体数据的发送和接收;降低能耗,相对LEACH协议降低50%75%;延长网络寿命。缺点节点维护位置信息需要额外资源;链头通信量大,其失效会导致路由失败;成链算法要求节点知道其他节点位置,开销较大;如果链过长,传输时延会增大。,TEEN协议,分层路由协议,TEEN协议按照分层结构组织节点,利用过滤方式减少数据传输量,即用来提供基于事件的数据传递。TEEN协议基本原理:1.采用与LEACH协议相同的聚簇方式,但簇头根据与汇聚节点的距离形成层次结构 2.聚簇完成
17、后,汇聚节点通过簇头向全网广播两个阈值(即硬阈值和软阈值)以过滤数据的传输 3.在节点第一次监测到数据超过硬阈值时,节点向簇头上报数据,并将当前监测数据保存为监测值(SV)4.此后只有当监测到的数据大于硬阈值而与SV之差不小于软阈值时,节点才向簇头上报数据,并更新SV,TEEN协议,分层路由协议,硬阈值规定了什么情况下需要传输数据,即事件。软阈值设置了事件发生时数据的传输频率。通过引入两个阈值限制,TEEN协议大幅减少了数据传输的次数。,TEEN协议,分层路由协议,优点通过硬阈值和软阈值减少了数据传输量;多层次型簇头结构不要求节点具有大功率通信能力;能耗低,适用于事件响应型应用。缺点如某节点的
18、监测数据始终未达到硬阈值,则无法获得该节点任何数据,也无法掌握该节点状况,是否失效;不适用于需周期性采样的应用。,GEAR协议,基于地理位置的路由协议,GEAR协议中,已知目标区域的位置信息,节点知道自身位置信息和可用的能量信息。GEAR协议基本原理:1.查询消息到达目标区域的路径:节点选择传输代价最小的邻居作为下一跳并转发数据 2.查询命令到达事件区域后,采用递归转发或受限洪泛方式进行传输 3.节点会更新传输代价,GEAR协议,基于地理位置的路由协议,节点利用贪心算法选择邻居节点到达指定区域的代价估计代价:C(Ni,R)=Distance(Ni,R)+(1)Left_Enery(Ni)实际代
19、价:C(Ni,R)=Enery_Cost(Ni,R)+(1)Left_Enery(Ni)Ni为有转发需求的节点的邻居节点,R为目标区域的中心位置。当N不知道Ni的实际代价时使用估计代价。,GEAR协议,基于地理位置的路由协议,在递归转发方式中,目标区域分成4个子区域,将查询命令转发至子区域中心子区域再次划分并进行转发,知道子区域只剩下一个节点,则该节点收到查询命令后不再转发,GEAR协议,基于地理位置的路由协议,路由空洞邻居节点传输代价都比本地节点大;选择邻居节点中代价最小的作为转发节点;修改本地节点的转发代价;C(N,R)=C(Nmin,R)+C(N,Nmin)C(N,Nmin)表示将数据包
20、从N传送到Nmin的代价,优点利用了位置信息,避免了查询消息的洪泛传输;考虑了消耗的能量和节点剩余能量;路径选择可达到局部最优;递归地理转发对洪泛机制的补充。缺点可能出现路由空洞(局部信息);不适合在移动WSN使用。,GEAR协议,基于地理位置的路由协议,SAR协议,基于QoS的路由协议,SAR是第一种保证QoS的主动路由协议。SAR协议基本原理:1.汇聚节点的一跳邻居节点都已自己为根创建生成树 2.在创建生出数的过程中除考虑节点能量因素外,还考虑节点的时延、丢包率等QoS参数 3.各节点反向建立到汇聚节点的具有不同QoS参数的多条路径 4.节点根据路径QoS参数和数据包优先级在多跳路径中选择最优路径进行转发,优点能够提供QoS保证,适合对QoS有要求的应用场合。缺点节点中会产生大量冗余路由信息,耗费大量存储资源;路由信息的维护、节点QoS信息和能量信息的更新会增大系统开销。,SAR协议,基于QoS的路由协议,CTP协议构造并维护最小传输代价树来传递数据,以汇聚节点的一跳邻居作为根生成代价树最小代价路径转发协议以跳数或能耗作为代价尺度,代价最小化为最终目的SPEED协议一个基于位置的实时路由协议,在一定程度上保障了端到端的传输速率、拥塞控制和负载均衡,其他路由协议,路由协议的比较,