WSN第4章、路由协议解析.ppt

1、第五章 路由协议,内容提要,WSN路由协议概述 WSN路由协议分类 能量感知路由协议 基于查询的路由协议 集群结构路由协议 地理位置路由协议,内容提要,WSN路由协议概述 WSN路由协议分类 能量感知路由协议 基于查询的路由协议 集群结构路由协议 地理位置路由协议,路由协议概述 路由协议功能,定义： WSN路由协议是一套将数据从源节点传输到目的节点的机制。 路由是WSN的核心技术之一 WSN不适合设计通用的路由协议：能耗、计算复杂度。 WSN是无基础设施的网络，一般用电池供电、无人看守，电池不能补充，要延长网络寿命就必须降低能耗。 能耗主要用户数据无线传输上，所以单跳传输距离不能太远，要实现W

2、SN大范围覆盖，就需要多跳中继，即路由,设计目标 满足应用需求 （WSN路由与应用相关） 低网络开销 （内存、计算复杂度、节能） 资源利用的整体有效性 网络高吞吐率,WSN使用环境恶劣 无线信道不稳定 节点的移动与失效 WSN拓扑结构随时可能变化，这与传统Internet不同，因此传统路由不能用于WSN,WSN路由协议特点,与传统网络不同： （传统网络（如GSM）放在QoS上；WSN重点在能耗上） WSN特点 自组织的网络（随机部署） 数据的冗余性（多节点监测同一事件，需要数据融合） 基于局部拓扑信息（硬件限制） 网络功能：数据收集，多对一 （一个sink节点） WSN路由与应用相关，(不同的

3、应用采用不同的路由，降低路由复杂度) 以数据为中心,WSN路由协议要求,要求 能量高效（协议简单 缺点：点到点的时延较大 由于随机转发某一个节点的方向并不一定在距离目的节点更近的方向上，因此容易造成数据到达目的节点时间过长或者跳数己达到最大，而数据还没有到达目的节点，造成递送失败。 刚开始的很短的时间内发送速率很大，但是随着数据的发送，速度会明显降低，而且它并不能很好解决重叠的问题。,26,(2)SPIN协议,这是第1个基于数据的路由协议。该协议以抽象的元数据对数据进行命名，命名方式没有统一标准。节点产生或收到数据后，为避免盲目传播，用包含元数据的ADV消息向邻节点通告，需要数据的邻节点用RE

4、Q消息提出请求，数据通过DATA消息发送到请求节点。协议的优点是： 小ADV消息减轻了内爆问题；通过数据命名解决了交叠问题；节点根据自身资源和应用信息决定是否进行ADV通告，避免了资源利用盲目问题。 与Flooding和Gossiping协议相比，有效地节约了能量。 其缺点是： 当产生或收到数据的节点的所有邻节点都不需要该数据时，将导致数据不能继续转发，以致较远节点无法得到数据，当网络中大多节点都是潜在sink点时，问题并不严重，但当sink点较少时，则是一个很严重的问题；且当某sink点对任何数据都需要时，其周围节点的能量容易耗尽；虽然减轻了数据内爆，但在较大规模网络中，ADV内爆仍然存在。

5、,27,（1）基本思想,该协议考虑到了WSN中的数据冗余问题：临近的节点所感知的数据具有相似性，通过节点间协商(Nagotiation)的方式减少网络中数据的传输的数据量。节点只广播其他节点所没有的数据以减少冗余数据，从而有效减少能量消耗。 在SPIN协议中提出了元数据（mete data，是对节点感知数据的抽象描述）的概念，元数据是原始感知数据的一个映射，可以用来描述原始感知数据，而且元数据所需的数据位比原始感知数据要小，采用这种变相的数据压缩策略可以进一步减少通信过程中的能量消耗。,28,SPIN协议采用三次握手协议来实现数据的交互，协议运行过程中使用三种报文数据，分别为ADV、REQ和D

6、ATA。ADV用于数据的广播，当某一个节点有数据可以共享时，可以用ADV数据包通知其邻居节点；REQ用于请求发送数据，当某一个收到ADV的节点希望接收DATA数据包时，发送REQ数据包；DATA为原始感知数据包，里面装载了原始感知数据。 SPIN协议还包括了4个协议： SPIN-BC：适合于广播信道的SPIN协议 SPIN-PP：适合于点对点信道的SPIN协议 SPIN-EC：在SPIN-PP基础上增加了能量限制 SPIN-RL：考虑信道上存在分组丢失的SPIN协议,29,以数据为中心路由协议,SPIN：Sensor Protocol for Information via Negotiati

7、on,SPIN,该协议是最早的一类WSN路由协议的代表，是对Flooding协议的改进 考虑到WSN的数据冗余，临近节点所感知的数据具有相似性，通过节点间协商方式减少数据传输量，只广播其他节点没有的数据,SPIN中的元数据（meta-data）,元数据：对节点感知数据的抽象，是原始感知数据的压缩，可以描述原始感知数据 （传元数据可以节省能耗） SPIN协议有两种工作模式：SPIN1和SPIN2，（SPIN2在SPIN1 的基础上考虑了节点剩余能量） SPIN采用三次握手机制，有三种分组：ADV（相当于数据的索引，很短）、REQ、DATA,SPIN,协商通过元数据进行 元数据描述实数据 元数据与

8、实数据一一对应 协议消息 消息广播包：Advertise (ADV) 数据请求包：Request (REQ) 数据包：Data transfer (DATA),3步握手协议,A,A,A,A,A,A,节点A有新数据，通过ADV发布新数据信息，使用元数据 B节点收到ADV后，发现自己没有该数据，通过REQ向A请求新数据 A节点向B节点传送源数据 B节点融合新数据，并通过ADV发布新数据消息 如果节点ADV中描述的数据的副本就忽略该消息,图 SPIN协议工作流程,SPIN,通过和邻居节点的协商来减少Flooding带来的内爆和重叠的影响 通过元数据来完成协商过程 元数据：一种对源数据的映射，比源数据

9、短 避免传输冗余数据 3步握手协议(ADV-REQ-DATA) SPIN-2在SPIN-1的基础上加入了能量阈值 当一个节点的剩余能量低于能量阈值后，减少其在协议中参与的活动。,SPIN2模式考虑了剩余能量值，当节点能量值低于某个门限值时，该节点就不再参与DATA报文的转发，只是接收报文和发出REQ报文，进一步降低了能耗 模拟结果表明，SPIN2比传统方式节省能耗一半以上,解决内爆,SPIN利用三步握手机制 （解决内爆） SPIN利用数据融合（DC），部分解决了重叠问题,SPIN协议评价,优点 解决了内爆问题和部分解决了重叠问题 不需要进行路由维护 对网络拓扑变化不敏感，可用于移动WSN 缺点

10、 本质上SPIN还是向全网扩散新消息，开销比较大 当多个节点向同一个节点同时发送REQ时，需要退避算法,SPIN协议族（Protocol Family）,SPIN协议还包括了4个协议： SPIN-BC：适合于广播信道的SPIN协议 SPIN-PP：适合于点对点信道的SPIN协议 SPIN-EC：在SPIN-PP基础上增加了能量限制 SPIN-RL：考虑信道上存在分组丢失的SPIN协议,以数据为中心路由协议,DD:Directed Diffusion 定向扩散,Directed Diffusion,思路：Sink节点周期性地广播一种称为“兴趣”的分组，告诉其他节点，我要收集什么兴趣。兴趣在扩散的

11、过程中也反向建立了路由路径，与“兴趣”匹配节点通过路径传送数据到Sink节点 三个阶段： 兴趣扩散（采用泛洪）； 梯度建立（反向建立）； 强化路径（Sink节点会收到多条路径，选最优路径，进行加强，以后的数据按照加强路径传送）,Directed Diffusion,图 DD路由机制,Directed Diffusion,Sink节点查询兴趣消息 兴趣消息采用泛洪的方法传播到网络 有和兴趣匹配数据的节点发送数据 兴趣扩散阶段建立节点到Sink的路径 兴趣的定义： 由属性值对组成,type = four-legged animal / detect animal location interval

12、 = 20 ms / send back events every 20 ms duration = 10 seconds / . for the next 10 seconds rect = -100, i00, 200, 400 / from sensors within rectangle,兴趣和梯度,Sink节点向全网查询兴趣 建立源节点和Sink间路径 兴趣在全网中扩散 对每一个活动任务，Sink周期进行查询 邻居更新自己的兴趣cache，并且转发 兴趣cache中的条目(兴趣表项) 时间戳：指示接收到相关兴趣消息的最近时间 若干梯度域：每个梯度和其邻居节点相关联 （每条表项有多个梯

13、度域） 一个梯度标示一个邻居 每个梯度中含有一个指定的数据传输率 持续时间：该兴趣消息的有效期,Directed Diffusion,查询消息的传播建立数据的传输梯度 Sink节点发送查询消息 兴趣消息：任务性质、数据采集/发送数率、时间戳等 中间节点： 记录 转发 梯度：表示了数据的传输方向,加强路径修复问题,加强路径上的节点可以触发和启动路径的加强过程,DD协议评价,优点 数据中心路由，定义不同任务类型/目标区域消息； 路径加强机制可显著提高数据传输的速率； 周期性路由：能量的均衡消耗； 缺点 周期性的洪泛机制-能量和时间开销都比较大； Sink周期性广播，不适用于大规模网络 节点需要维护

14、一个兴趣消息列表，代价较大；,Directed Diffusion Family,GBR路由(Gradient-Based Routing)协议： 梯度域扩展（传感器节点到Sink节点的跳数信息、无线链路评估信息） EAR(Energy Aware Routing)路由协议 建立路由过程中加入能量评估机制； 路由路径的能量开销大于某一阈值不采用； CADR路由(Constrained Anisotropic Diffusion routing)协议 兴趣消息往指定方向发送,谣传路由 (rumor routing）,有些传感器网络的应用中，数据传输量较少或者已知事件区域。定向扩散路由并不是高效的

15、路由机制。 Boulis 等人提出了谣传路由,适用于数据传输量较小的传感器网络。 谣传路由机制引入了查询消息的单播随机转发，克服了使用洪泛方式建立转发路径带来的开销过大问题。它的基本思想是： 事件区域中的传感器节点产生代理（ agent ） 消息， 代理消息沿随机路径向外扩散传播。 同时汇聚节点发送的查询消息也沿随机路径在网络中传播。当代理消息和查询消息的传输路径交叉在一起时， 就会形成一条汇聚节点到事件区域的完整路径。,49,rumor,50,rumor,谣传路由的原理如图所示，谣传路由的工作过程如下： 每个传感器节点维护一个邻居列表和一个事件列表。 事件列表的每个表项都记录事件相关的信息，

16、包括事件名称、到事件区域的跳数和到事件区域的下一跳邻居等信息。 当传感器节点在本地监测到一个事件发生时，在事件列表中增加一个表项，设置事件名称、跳数（为零）等，同时根据一定的概率产生一个代理消息。,51,rumor,代理消息是一个包含生命期等事件相关信息的分组，用来将携带的事件信息通告给它传输经过的每一个传感器节点。 对于收到代理消息的节点，首先检查事件列表中是否有该事件相关的表项，列表中存在相关表项就比较代理消息和表项中的跳数值，如果代理中的跳数小，就更新表项中的跳数值，否则更新代理消息中的跳数值。 如果事件列表中没有该事件相关的表项，就增加一个表项来记录代理消息携带的事件信息。然后，节点将

17、代理消息中的生存值减 1 ，在网络中随机选择邻居节点转发代理消息，直到其生存值减少为零。 通过代理消息在其有限生存期的传输过程，形成一段到达事件区域的路径。,52,网络中的任何节点都可能生成一个对特定事件的查询消息。 如果节点的事件列表中保存有该事件的相关表项，说明该节点在到达事件区域的路径上，它沿着这条路径转发查询消息。否则，节点随机选择邻居节点转发查询消息。 查询消息经过的节点按照同样方式转发，并记录查询消息中的相关信息，形成查询消息的路径。 查询消息也具有一定的生存期，以解决环路问题。,53,内容提要,WSN路由协议概述 WSN路由协议分类 能量感知路由协议 基于查询的路由协议 集群结构

18、路由协议 地理位置路由协议,集群结构路由协议,LEACH : Low-Energy Adaptive Clustering Hierarchy,集群结构路由原理,集群结构路由协议实际是分层结构路由协议，网络划分为多个簇，每个簇由一个簇头和簇成员组成，这些簇头形成高一级网络，在高一级网络中，可以再一次分簇，形成更高一级网络 簇头管理簇内节点，收集和融合簇内信息和簇间数据的转发。 优点：扩展性好，适宜大规模网络,集群结构路由协议,LEACH : Low-Energy Adaptive Clustering Hierarchy,LEACH算法,每个节点直接和Sink节点通信： 节点能量消耗过大 节点

19、密度较大时冲突过大，效率低 LEACH算法： 最早的一种分层路由算法，主要考虑簇内节点能耗 簇头作为一定区域所有节点的代理，负责和Sink的通信； 非簇头节点可以使用小功率和簇头节点通信； 簇头节点可以对所辖区域节点数据进行融合，减少网络中传输的数据； 簇头选举算法的设计，要求保证公平性,关键问题,使用Leach协议后，形成两级星形结构，如图5-9 簇内节点与簇头距离近，功耗小；簇头进行数据融合，减少通信量 簇头消耗大量能量，所以定期选举簇头,簇头选举算法,每个传感器节点选择0，1之间的一个随机数，如果选定的值小于某一个阈值，那么这个节点成为簇头节点，计算如下： N表示网络中传感器节点的个数，

20、k为一个网络中的簇头节点数，r为已完成的回合数，G为网络生存期总的回合数。,LEACH算法,网络按照周期工作，每个周期分为两个阶段： 簇头建立阶段： 节点运行算法，确定本次自己是否成为簇头（选簇）； 簇头节点广播自己成为簇头的事实； 其他非簇头节点按照信号强弱选择应该加入的簇头，并通知该簇头节点； 簇头节点按照TDMA的调度，给依附于他的节点分配时间片； 数据传输阶段： 节点在分配给他的时间片上发送数据；,LEACH算法评价,优点 优化了传输数据所需能量； 优化了网络中的数据量（簇头数据融合）； 缺点 节点硬件需要支持射频功率自适应调整； 无法保证簇头节点能遍及整个网络； 分簇与簇头选举 要公

21、平,LEACH Family,LEACH-c： 簇头由Sink节点指定； 通过模拟退火算法选择簇头； PEGASIS： 将网络中所有节点连成一条线； 每次只有一个簇头节点负责和Sink的通信，簇头在链上移动；,集群结构路由协议,TTDD: A Two-tier Data Dissemination Model for Large-scale Wireless Sensor Networks,TTDD,传感器节点不移动，Sink节点移动； 多Sink； 以源节点为中心建立格状网；（下图5-15） 最接近网格交叉点的节点为转发节点，转发节点保存了源节点的信息 运用代理，实现对移动Sink的透明传输

22、；（非Sink节点不能移动，Sink节点可以移动） Sink通过泛洪查找最近的转发节点（直接转发节点）； 转发节点将查询送给源节点，源节点将信息通过查询建立的路径发送给Sink节点 Sink节点在等待查询数据时，可继续移动；Sink节点指定了代理，由代理转给Sink节点,格状网的建立,源节点B的坐标(x,y)； 网格的边长为 B建立的格状网的交叉点坐标为 B为中心建立网络的转发点选择与交叉点最近的点，如图中黑点 成为转发节点的点启动下一级转发节点的选取过程,图5-15 以B为源节点建立的格状网,格状网构造和转发节点选取,需要每个节点知道自己的地理位置，每个格子为边长为a的正方形，计算每个正方形

23、的顶点位置 源节点B广播公告消息，离交叉点最近的节点接收该公告消息，这样B的四个交叉点的转发节点建立起来，继续找离B两跳的交叉点的转发节点（每个交叉点均需要1个转发节点） 转发节点的选取，距离交叉点小于a/2的节点才接收公告消息，并广播自己的地理位置，计算最近的节点为转发节点。,Sink节点通过广播来查询，当某个转发节点需要响应该查询时，该转发节点就成为直接转发节点； 直接转发节点就向其上游节点传送查询消息，查询消息一直到源节点； 传播路径上的转发节点需要记录自己的下游节点的信息和Sink节点信息，作为为传输数据的路径 如下图（图2-16）的G点，发往不同Sink节点的数据都经过G点，G点需要

24、根据Sink节点以上区分。,格状网建立时的上下游关系,上游节点 转发节点在格状网建立阶段由源节点或者其它转发节点选择，这个选择本转发节点的源节点或者转发节点称为本转发节点的上游节点 下游节点 和上游节点的定义相反,Sink节点查询过程,所有的转发节点都包含有源节点的数据公告消息 Sink通过泛洪方式发起查询请求，查询范围是一个网格区间 匹配节点（直接转发节点）通过格状网建立时的上下游关系将查询传送到源节点 源节点响应查询，沿查询消息的反向传输路径传送数据,图5-16 TTDD网络数据流描述,对移动Sink的支持,直接转发节点 第一个响应Sink查询的格状网中的转发节点 初级代理(PA) Sin

25、k节点指定的一个节点，负责接收直接转发节点发送过来的数据 直接代理(IA) Sink节点移动时动态指定IA，PA将数据传送给IA，由IA将数据提交给Sink。PA和IA可以是同一个节点。,当Sink移出距离太远，找不到IA时，Sink重新发起查询过程。,TTDD路由协议评价,优点 提出了一种新的应用场景 支持多Sink以及Sink移动的网络环境 缺点 需要地理位置信息的支持 网格大小不容易确定,内容提要,WSN路由协议概述 WSN路由协议分类 能量感知路由协议 基于查询的路由协议 集群结构路由协议 地理位置路由协议,地理位置信息,地理位置信息路由协议要求每个节点知道自己在网络中的位置 下列方法

26、可确定节点位置 GPS(Global Positioning System) 超声波三角定位系统 标定 用途 地理位置信息作为其它路由算法的辅助 直接用于路由的计算,地理位置信息路由协议,GPSR： Greedy Perimeter Stateless Routing,GPSR,贪婪算法 利用节点的地理位置信息 转发节点（下一跳）选取： 选择邻居节点中离目的节点D最近的点作为转发节点,贪婪算法的缺点：出现局部优化问题,局部优化问题,存在x到D的路径 x的邻居w,y离D的距离比x大,解决方法：边界转发,空旷区域,边界转发,平面图： 二维空间结构； 平面图中任意两条边都不相交； GPSR算法中构造

27、平面图的方法是删除网络拓扑图中交叉的边 算法： RNG(Relative Neighborhood Graph) GG(Gabriel Graph),RNG,节点u，v之间存在边的条件是对于任意一个节点w，u到v的距离要小于或等于u到w或是v到w的距离的最大值，用下式表示：,GG,节点u，v之间存在边的条件是在以d(u，v)为直径的圆中没有其它节点，用下式表示：,边界转发时的右手法则,一个数据分组从节点y到达节点x； 下一条边的选择： 下一边是以x为顶点，沿(x，y)逆时针方向上的第一条边，图中为(x，z) 后续各边同样依次法则确定,Face,平面图的边将整个图分成许多小的互不重叠的有界多边形

28、和一些无界区域，这些有界多边形和无界区域统称为face。 其中，有界区域称为内部face，无界区域称为外部face。图中xD通过3个有界face和一个无界face。,边界转发,数据包在x点进入边界转发模式，通过face边界向目的节点D转发，这些face都被xD穿越； 转发边的选择采用右手法则，初始边为xD； 数据包在同一个face中转发时采用右手法则，当碰到与xD相交的边时，进行face切换，进入下一个face；,GPSR协议评价,优点 采用局部最优的贪婪算法，不需要维护网络拓扑，路由开销小； 可适用于静态和移动的WSN网络； 缺点 需要地理位置信息的支持； 需要维护邻居节点位置信息；,GPS

29、R Family,GRA（Geographical Routing Algorithm)： 发生局部优化问题时通过泛洪查找到目的节点的路由 f-GEDIR(f表示泛洪)和c-GEDIR ： 发生局部优化问题，采用尽最大努力发送的方式： f-GEDIR：向所有邻节点广播该分组 c-GEDIR：选择部分邻节点转发该分组 收到数据包的节点继续使用GPSR协议转发该数据分组 2-hop GEDIR ： 节点保存一跳和两跳范围邻居节点的位置信息,常用的贪婪策略,MFR(Most Forward within Radius)： 使到目的节点的跳数最少 NFP(Nearest with Forward Pr

30、ogress)： 使节点之间干扰最少 CR(Compass Routing) ： 减小数据传输范围,地理位置信息路由协议,GEAR ： Geographic and Energy Aware Routing,GEAR路由协议,应用 建立到特定区域的路由 查询工作方式 前提 已知目标区域的位置信息 节点知道自己位置信息和剩余能量 节点间无线链路是对称的,GEAR路由过程,分两个阶段： 查询消息到达目的区域的路径 查询消息在目标区域的传播 选路依据 节点到查询区域通信能量能耗 节点本身的剩余能量 最小代价节点为转发节点,GEAR路由过程,查询命令传送到目标区域 贪婪算法选择邻居 节点到达指定区域的

31、代价 估计代价： F(Ni ,R)=Distance( Ni , R) + (1)Left_Enery(Ni ) 实际代价： F(Ni ,R)=Enery_Cost(Ni ,R)+(1)Left_Enery(Ni ) Ni为有转发需求的节点的邻居节点，R为目标区域的中心位置。当N不知道Ni的实际代价时使用估计代价。,GEAR路由过程,查询在监测区域内传送：洪泛方式，迭代地理转发 将目标区域分解为若干子区域、 向子区域的中心位置转发）,路由空洞问题,路由空洞 邻居节点传输代价都比本地节点大； 选择邻居节点中代价最小的作为转发节点； 修改本地节点的转发代价； F(N ,R)= F(Nmin,R)+

32、C(N,Nmin) ， C(N,Nmin)表示将数据包从N传送到Nmin的代价,GEAR路由评价,优点 利用了位置信息，避免了查询消息的Flooding； 考虑了消耗的能量和节点剩余能量，均衡消息； 路径选择可达到局部最优； 迭代地理转发对洪泛机制的补充； 缺点 可能出现路由空洞（局部信息）- 两跳信息； 不适合在移动WSN使用,WSN路由协议最新研究成果,现阶段WSN路由设计主要关注下面几个方面 提高能量效率，实现网络负载的平衡，延长网络生存时间； 满足各种应用场景的参数指标(也就是QOS)； 实现一定程度的数据安全性。,一种平衡网路能量和负载的路由协议,Joint Mobility and Routing for Lifetime Elongation in Wireless Sensor Networks,一种平衡网路能量和负载的协议,需要解决的问题,多源单汇,数据流远远大于控制流,离汇聚