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

《WSN第4章、路由协议解析.ppt》由会员分享，可在线阅读，更多相关《WSN第4章、路由协议解析.ppt（107页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、同的路由，降低路由复杂度)以数据为中心WSN路由协议要求n 要求能量高效（协议简单&节省能量&均衡消耗）可扩展性（网络范围 & 节点密度）鲁棒性（节点变化 & 拓扑变化）快速收敛性 （在移动的节点时，更需要快速收敛）WSN路由协议关键技术 考虑网络和节点能量优化 节点能量限制，大部分能量用于通信，所以研究低功耗的通信协议，尤其是路由协议 具有高可扩展性 网络规模，节点上千个，节点越多，路由收敛越慢、路由越不稳定，Ad Hoc的路由不能照搬 网络拓扑变化强 节点移动、失效 & 无线信道 & 规模大，拓扑变化频繁，如何建立快速收敛、复杂度低的路由？） 传感器网络路由中使用数据融合技术（数据为中心）

4、 传统网络以点对点通信，保证数据“完整无误”；WSN强调数据汇聚，为了降耗，每个节点都进行数据融合，减小通信量 传感器网络中流量分布不对称 数据收集网络&多源单Sink，越接近Sink，流量越大 其他：冗余设计、定位、覆盖性、QoS等传感器网络路由协议的挑战自组织布撒（Ad hoc deployment）能量消耗（Energy consumption ）路由精度（Routing accuracy）计算能力（Computation capabilities）通信能力（Communication tolerance）容错能力（Fault tolerance）可扩展性（Scalability）控制负

5、载（Control overhead，带宽有限，重载情况下，如何保证QoS）内容提要lWSN路由协议概述 lWSN路由协议分类 l能量感知路由协议 l基于查询的路由协议 l集群结构路由协议 l地理位置路由协议路由协议分类（1）p按路由发现策略划分按路由发现策略划分 主动路由: 也叫表驱动(Table Driven)路由， 主动路由的路由发现策略与传统路由协议类似，节点通过周期性地广播路由信息分组，交换路由信息，主动发现路由， 节点必须维护去往全网所有节点的路由。 优点:当节点需要发送数据分组时，只要去往目的节点的路由存在，所需的延时就会很小。 缺点:需要花费较大开销，尽可能使得路由更新能够紧随

6、当前拓扑结构的变化，浪费了一些资源来建立和重建那些根本没有被使用的路由。12路由协议分类（1） 被动路由: 也叫按需(On Demand)路由 与主动路由相反，被动路由认为在动态变化的网络环境中，没有必要维护去往其它所有节点的路由。 仅在有去往目的节点路由的时候才“按需”进行路由发现。 被动路由协议根据网络分组的传输请求，被动地搜索从源节点到目的节点的路由。 当没有分组传递请求时，路由器处于静默状态，并不需要交换路由信息。 拓扑结构和路由表内容按需建立，它可能仅仅是整个拓扑结构信息的一部分。 优点:不需要周期性的路由信息广播，节省了一定的网络资源。 缺点:发送数据分组时，如果没有去往目的节点的

7、路由，数据分组需要等待因路由发现引起的延时。13路由协议分类（2）p按网络管理的逻辑结构划分 平面结构路由: 平面结构是指网络中各节点在路由功能上地位相同，没有引入分层管理机制。 优点：网络中没有特殊节点，网络流量均匀地分散在网络中，路由算法易于实现。 缺点：可扩张性小，在一定程度上限制了网络的规模。 典型路由：Flooding,Gossiping,SPIN,DD，Rumor14路由协议分类（2） 分层路由: 与平面路由协议相对应的是分层结构路由协议。 它采用簇的概念对传感器节点进行层次划分。 若干个相邻节点构成一个簇，每一个簇有一个簇首。簇与簇之间可以通过网关通信。 网关可以是簇首也可以是其

8、它簇成员。网关之间的连接构成上层骨干网，所有簇间通信都通过骨干网转发。 分层路由协议包括成簇协议、簇维护协议、簇内路由协议和簇间路由协议四个部分。 成簇协议解决如何在动态分布式网络环境下使移动节点高效地聚集成簇，它是分层路由协议的关键。 簇维护协议要解决在节点移动过程中的簇结构维护，其中包括移动节点退出和加入簇，簇的产生和消亡等功能。 分层路由协议比较适合于无线传感器网络，但成簇过程会产生一定的能源消耗，如何产生有效的簇类也正是各地学者深入研究的问题。15路由协议分类（2） 分层路由: 典型协议： LEACH, TTDD16路由协议分类（3） 地理信息路由协议 在目标跟踪类应用中，往往需要唤醒

9、距离跟踪目标最近的传感器节点，以得到关于目标的更精确位置等相关信息。 在这类应用中，通常需要知道目的节点的精确或者大致地理位置。 把节点的位置信息作为路由选择的依据，不仅能够完成节点路由功能，还可以降低系统专门维护路由协议的能耗。 节点知道自己的地理位置，利用位置进行路由 典型协议： GPSR, GEAR，GEM1718内容提要lWSN路由协议概述 lWSN路由协议分类 l能量感知路由协议 l基于查询的路由协议 l集群结构路由协议 l地理位置路由协议能量感知路由 p节点根据可用能量（power available，PA）或传输路径上的能量需求，选择数据的转发路径。节点可用能量就是节点当前的剩余

10、能量。能量路由算法示意图路径1：SBAD， PA=4，E=3；路径2：SCBAD， PA=6，E=6；路径3：SDD， PA=3，E=4；路径4：SFED， PA=5，E=6。功率最大PA优先：选路径2能量消耗最小优先：选路径1以数据为中心路由协议pFlooding协议和Gossiping协议pSPIN协议pDirected Diffusion协议pRumor协议(l)Flooding协议和Gossiping协议p泛洪是一种传统的路由技术。p泛洪算法的主要思想是由槽节点发起数据广播，然后任意一个收到广播的节点都无条件将该数据副本广播出去，每一节点都重复这样的过程直到数据遍历全网或者达到规定的最

11、大跳数。p算法不用维护网络拓扑结构和路由计算，实现简单。但是最主要的是内爆和重叠以及资源盲点等。23内爆现象 内爆现象如图所示，节点S通过广播将数据发送给自己的邻居节点A、B和C，A、B和C又将同样的数据包转发给D，这种将同一个数据包多次转发给同一个节点的现象就是内爆，这极大浪费节点能量。24重叠现象 重叠现象是无线传感器网络特有的，如图节点A和B感知范围发生了重叠，重叠区域的事件被相邻的两个节点探测到，那么同一事件被传给它们共同的邻居节点C多次，这也浪费能量。 重叠现象是一个很复杂的问题，比内爆问题更难解决。25Gossiping路由协议pGossiping协议是对Flooding协议的改进

12、p当节点收到数据包时，只将数据包随机转发给与其相邻的节点的某一个节点或几个，而不是所有节点。p当相邻节点收到数据包时，也采用同样的办法转发给与其相邻某一个节点。p优点：就降低了数据转发重叠的可能性，避免了信息内爆现象的产生; p缺点：点到点的时延较大 由于随机转发某一个节点的方向并不一定在距离目的节点更近的方向上，因此容易造成数据到达目的节点时间过长或者跳数己达到最大，而数据还没有到达目的节点，造成递送失败。 刚开始的很短的时间内发送速率很大，但是随着数据的发送，速度会明显降低，而且它并不能很好解决重叠的问题。26(2)SPIN协议p这是第1个基于数据的路由协议。该协议以抽象的元数据对数据进行

13、命名，命名方式没有统一标准。节点产生或收到数据后，为避免盲目传播，用包含元数据的ADV消息向邻节点通告，需要数据的邻节点用REQ消息提出请求，数据通过DATA消息发送到请求节点。协议的优点是： 小ADV消息减轻了内爆问题；通过数据命名解决了交叠问题；节点根据自身资源和应用信息决定是否进行ADV通告，避免了资源利用盲目问题。 与Flooding和Gossiping协议相比，有效地节约了能量。p其缺点是： 当产生或收到数据的节点的所有邻节点都不需要该数据时，将导致数据不能继续转发，以致较远节点无法得到数据，当网络中大多节点都是潜在sink点时，问题并不严重，但当sink点较少时，则是一个很严重的问

14、题；且当某sink点对任何数据都需要时，其周围节点的能量容易耗尽；虽然减轻了数据内爆，但在较大规模网络中，ADV内爆仍然存在。27（1）基本思想p该协议考虑到了WSN中的数据冗余问题：临近的节点所感知的数据具有相似性，通过节点间协商(Nagotiation)的方式减少网络中数据的传输的数据量。节点只广播其他节点所没有的数据以减少冗余数据，从而有效减少能量消耗。p在SPIN协议中提出了元数据（mete data，是对节点感知数据的抽象描述）的概念，元数据是原始感知数据的一个映射，可以用来描述原始感知数据，而且元数据所需的数据位比原始感知数据要小，采用这种变相的数据压缩策略可以进一步减少通信过程中

15、的能量消耗。28pSPIN协议采用三次握手协议来实现数据的交互，协议运行过程中使用三种报文数据，分别为ADV、REQ和DATA。ADV用于数据的广播，当某一个节点有数据可以共享时，可以用ADV数据包通知其邻居节点；REQ用于请求发送数据，当某一个收到ADV的节点希望接收DATA数据包时，发送REQ数据包；DATA为原始感知数据包，里面装载了原始感知数据。pSPIN协议还包括了4个协议： SPIN-BC：适合于广播信道的SPIN协议 SPIN-PP：适合于点对点信道的SPIN协议 SPIN-EC：在SPIN-PP基础上增加了能量限制 SPIN-RL：考虑信道上存在分组丢失的SPIN协议29以数据

16、为中心路由协议SPIN：Sensor Protocol for Information via NegotiationSPINp该协议是最早的一类WSN路由协议的代表，是对Flooding协议的改进p 考虑到WSN的数据冗余，临近节点所感知的数据具有相似性，通过节点间协商方式减少数据传输量，只广播其他节点没有的数据SPIN中的元数据（meta-data）p元数据：对节点感知数据的抽象，是原始感知数据的压缩，可以描述原始感知数据 （传元数据可以节省能耗）p SPIN协议有两种工作模式：SPIN1和SPIN2，（SPIN2在SPIN1 的基础上考虑了节点剩余能量）p SPIN采用三次握手机制，有三

17、种分组：ADV（相当于数据的索引，很短）、REQ、DATASPINn 协商通过元数据进行协商通过元数据进行元数据描述实数据元数据与实数据一一对应n 协议消息协议消息消息广播包：Advertise (ADV)数据请求包：Request (REQ)数据包：Data transfer (DATA)3步握手协议步握手协议AAAAAA节点A有新数据，通过ADV发布新数据信息，使用元数据B节点收到ADV后，发现自己没有该数据，通过REQ向A请求新数据A节点向B节点传送源数据B节点融合新数据，并通过ADV发布新数据消息如果节点ADV中描述的数据的副本就忽略该消息图图 SPIN协议工作流程协议工作流程SPIN

18、n 通过和邻居节点的协商来通过和邻居节点的协商来减少减少Flooding带来的带来的内爆和内爆和重叠重叠的影响的影响n 通过通过元数据元数据来完成协商过程来完成协商过程 元数据：一种对源数据的映射，比源数据短 避免传输冗余数据n 3步握手协议步握手协议(ADV-REQ-DATA)n SPIN-2在在SPIN-1的基础上加入了能量阈值的基础上加入了能量阈值 当一个节点的剩余能量低于能量阈值后，减少其在协议中参与的活动。pSPIN2模式考虑了剩余能量值，当节点能量值低于某个门限值时，该节点就不再参与DATA报文的转发，只是接收报文和发出REQ报文，进一步降低了能耗p 模拟结果表明，SPIN2比传统

19、方式节省能耗一半以上 解决内爆 pSPIN利用三步握手机制 （解决内爆）p SPIN利用数据融合（DC），部分解决了重叠问题SPIN协议评价n 优点解决了内爆问题和部分解决了重叠问题不需要进行路由维护对网络拓扑变化不敏感，可用于移动WSNn 缺点本质上SPIN还是向全网扩散新消息，开销比较大 当多个节点向同一个节点同时发送REQ时，需要退避算法 SPIN协议族（协议族（Protocol Family）pSPIN协议还包括了4个协议： SPIN-BC：适合于广播信道的SPIN协议 SPIN-PP：适合于点对点信道的SPIN协议 SPIN-EC：在SPIN-PP基础上增加了能量限制 SPIN-RL

20、：考虑信道上存在分组丢失的SPIN协议以数据为中心路由协议DD:Directed Diffusion定向扩散定向扩散Directed Diffusionp思路：Sink节点周期性地广播一种称为“兴趣”的分组，告诉其他节点，我要收集什么兴趣。兴趣在扩散的过程中也反向建立了路由路径，与“兴趣”匹配节点通过路径传送数据到Sink节点p三个阶段： 兴趣扩散（采用泛洪）； 梯度建立（反向建立）； 强化路径（Sink节点会收到多条路径，选最优路径，进行加强，以后的数据按照加强路径传送）Directed Diffusion图 DD路由机制Directed Diffusionn Sink节点查询兴趣消息兴趣消

21、息采用泛洪的方法传播到网络有和兴趣匹配数据的节点发送数据兴趣扩散阶段建立节点到Sink的路径n 兴趣的定义：由属性值对组成type = four-legged animal / detect animal locationinterval = 20 ms / send back events every 20 msduration = 10 seconds / . for the next 10 seconds rect = -100, i00, 200, 400 / from sensors within rectangle兴趣和梯度p Sink节点向全网查询兴趣 建立源节点和Sink间路径

22、 兴趣在全网中扩散 对每一个活动任务，Sink周期进行查询p 邻居更新自己的兴趣cache，并且转发p 兴趣cache中的条目(兴趣表项) 时间戳：指示接收到相关兴趣消息的最近时间 若干梯度域：每个梯度和其邻居节点相关联 （每条表项有多个梯度域） 一个梯度标示一个邻居 每个梯度中含有一个指定的数据传输率 持续时间：该兴趣消息的有效期Directed Diffusionn 查询消息的传播建立数据的传输梯度 Sink节点发送查询消息 兴趣消息：任务性质、数据采集/发送数率、时间戳等 中间节点：记录转发 梯度：表示了数据的传输方向加强路径修复问题n 加强路径上的节点可以触发和启动路径的加强过程 新路

23、径C和源节点之间路径断裂DD协议评价n 优点数据中心路由，定义不同任务类型/目标区域消息；路径加强机制可显著提高数据传输的速率；周期性路由：能量的均衡消耗；n 缺点周期性的洪泛机制-能量和时间开销都比较大；Sink周期性广播，不适用于大规模网络节点需要维护一个兴趣消息列表，代价较大；Directed Diffusion Familyn GBR路由(Gradient-Based Routing)协议： 梯度域扩展（传感器节点到Sink节点的跳数信息、无线链路评估信息）n EAR(Energy Aware Routing)路由协议 建立路由过程中加入能量评估机制； 路由路径的能量开销大于某一阈值不

24、采用；n CADR路由(Constrained Anisotropic Diffusion routing)协议 兴趣消息往指定方向发送谣传路由 (rumor routing）p有些传感器网络的应用中，数据传输量较少或者已知事件区域。定向扩散路由并不是高效的路由机制。 Boulis 等人提出了谣传路由,适用于数据传输量较小的传感器网络。p谣传路由机制引入了查询消息的单播随机转发，克服了使用洪泛方式建立转发路径带来的开销过大问题。它的基本思想是： 事件区域中的传感器节点产生代理（ agent ） 消息， 代理消息沿随机路径向外扩散传播。 同时汇聚节点发送的查询消息也沿随机路径在网络中传播。当代理

25、消息和查询消息的传输路径交叉在一起时， 就会形成一条汇聚节点到事件区域的完整路径。49rumor50rumorp谣传路由的原理如图所示，谣传路由的工作过程如下： 每个传感器节点维护一个邻居列表和一个事件列表。 事件列表的每个表项都记录事件相关的信息，包括事件名称、到事件区域的跳数和到事件区域的下一跳邻居等信息。 当传感器节点在本地监测到一个事件发生时，在事件列表中增加一个表项，设置事件名称、跳数（为零）等，同时根据一定的概率产生一个代理消息。51rumor 代理消息是一个包含生命期等事件相关信息的分组，用来将携带的事件信息通告给它传输经过的每一个传感器节点。 对于收到代理消息的节点，首先检查事

26、件列表中是否有该事件相关的表项，列表中存在相关表项就比较代理消息和表项中的跳数值，如果代理中的跳数小，就更新表项中的跳数值，否则更新代理消息中的跳数值。 如果事件列表中没有该事件相关的表项，就增加一个表项来记录代理消息携带的事件信息。然后，节点将代理消息中的生存值减 1 ，在网络中随机选择邻居节点转发代理消息，直到其生存值减少为零。 通过代理消息在其有限生存期的传输过程，形成一段到达事件区域的路径。52 网络中的任何节点都可能生成一个对特定事件的查询消息。 如果节点的事件列表中保存有该事件的相关表项，说明该节点在到达事件区域的路径上，它沿着这条路径转发查询消息。否则，节点随机选择邻居节点转发查

27、询消息。 查询消息经过的节点按照同样方式转发，并记录查询消息中的相关信息，形成查询消息的路径。 查询消息也具有一定的生存期，以解决环路问题。53内容提要lWSN路由协议概述 lWSN路由协议分类 l能量感知路由协议 l基于查询的路由协议 l集群结构路由协议 l地理位置路由协议集群结构路由协议LEACH : Low-Energy Adaptive Clustering Hierarchy集群结构路由原理p集群结构路由协议实际是分层结构路由协议，网络划分为多个簇，每个簇由一个簇头和簇成员组成，这些簇头形成高一级网络，在高一级网络中，可以再一次分簇，形成更高一级网络p簇头管理簇内节点，收集和融合簇内

28、信息和簇间数据的转发。p优点：扩展性好，适宜大规模网络集群结构路由协议LEACH : Low-Energy Adaptive ClusteringHierarchyLEACH算法n 每个节点直接和Sink节点通信：节点能量消耗过大节点密度较大时冲突过大，效率低n LEACH算法：最早的一种分层路由算法，主要考虑簇内节点能耗簇头作为一定区域所有节点的代理，负责和Sink的通信；非簇头节点可以使用小功率和簇头节点通信；簇头节点可以对所辖区域节点数据进行融合，减少网络中传输的数据；簇头选举算法的设计，要求保证公平性关键问题p使用Leach协议后，形成两级星形结构，如图5-9p簇内节点与簇头距离近，功

29、耗小；簇头进行数据融合，减少通信量p 簇头消耗大量能量，所以定期选举簇头簇头选举算法n 每个传感器节点选择0，1之间的一个随机数，如果选定的值小于某一个阈值，那么这个节点成为簇头节点，计算如下： N表示网络中传感器节点的个数，k为一个网络中的簇头节点数，r为已完成的回合数，G为网络生存期总的回合数。Gn 0)/mod()(如其它情况knrkNknTLEACH算法n 网络按照周期工作，每个周期分为两个阶段：簇头建立阶段： 节点运行算法，确定本次自己是否成为簇头（选簇）； 簇头节点广播自己成为簇头的事实； 其他非簇头节点按照信号强弱选择应该加入的簇头，并通知该簇头节点； 簇头节点按照TDMA的调度

30、，给依附于他的节点分配时间片；数据传输阶段： 节点在分配给他的时间片上发送数据；LEACH算法评价n 优点优化了传输数据所需能量；优化了网络中的数据量（簇头数据融合）；n 缺点节点硬件需要支持射频功率自适应调整；无法保证簇头节点能遍及整个网络；分簇与簇头选举 要公平LEACH Familyn LEACH-c： 簇头由Sink节点指定； 通过模拟退火算法选择簇头；n PEGASIS： 将网络中所有节点连成一条线； 每次只有一个簇头节点负责和Sink的通信，簇头在链上移动；集群结构路由协议TTDD: A Two-tier Data Dissemination Model for Large-sca

31、le Wireless Sensor NetworksTTDD 传感器节点不移动，Sink节点移动； 多Sink； 以源节点为中心建立格状网；（下图5-15） 最接近网格交叉点的节点为转发节点，转发节点保存了源节点的信息 运用代理，实现对移动Sink的透明传输；（非Sink节点不能移动，Sink节点可以移动） Sink通过泛洪查找最近的转发节点（直接转发节点）； 转发节点将查询送给源节点，源节点将信息通过查询建立的路径发送给Sink节点 Sink节点在等待查询数据时，可继续移动；Sink节点指定了代理，由代理转给Sink节点格状网的建立p 源节点B的坐标(x,y)；p 网格的边长为p B建立的

32、格状网的交叉点坐标为p B为中心建立网络的转发点选择与交叉点最近的点，如图中黑点p 成为转发节点的点启动下一级转发节点的选取过程, 21, 0,)*,*(jijyix图5-15 以B为源节点建立的格状网格状网构造和转发节点选取p 需要每个节点知道自己的地理位置，每个格子为边长为a的正方形，计算每个正方形的顶点位置p 源节点B广播公告消息，离交叉点最近的节点接收该公告消息，这样B的四个交叉点的转发节点建立起来，继续找离B两跳的交叉点的转发节点（每个交叉点均需要1个转发节点）p 转发节点的选取，距离交叉点小于a/2的节点才接收公告消息，并广播自己的地理位置，计算最近的节点为转发节点。p Sink节

33、点通过广播来查询，当某个转发节点需要响应该查询时，该转发节点就成为直接转发节点；p 直接转发节点就向其上游节点传送查询消息，查询消息一直到源节点；p 传播路径上的转发节点需要记录自己的下游节点的信息和Sink节点信息，作为为传输数据的路径p 如下图（图2-16）的G点，发往不同Sink节点的数据都经过G点，G点需要根据Sink节点以上区分。格状网建立时的上下游关系n 上游节点转发节点在格状网建立阶段由源节点或者其它转发节点选择，这个选择本转发节点的源节点或者转发节点称为本转发节点的上游节点 n 下游节点和上游节点的定义相反Sink节点查询过程p 所有的转发节点都包含有源节点的数据公告消息p S

34、ink通过泛洪方式发起查询请求，查询范围是一个网格区间p 匹配节点（直接转发节点）通过格状网建立时的上下游关系将查询传送到源节点p 源节点响应查询，沿查询消息的反向传输路径传送数据图5-16 TTDD网络数据流描述对移动Sink的支持n 直接转发节点 第一个响应Sink查询的格状网中的转发节点n 初级代理(PA) Sink节点指定的一个节点，负责接收直接转发节点发送过来的数据n 直接代理(IA) Sink节点移动时动态指定IA，PA将数据传送给IA，由IA将数据提交给Sink。PA和IA可以是同一个节点。当Sink移出距离太远，找不到IA时，Sink重新发起查询过程。TTDD路由协议评价n 优

35、点提出了一种新的应用场景 支持多Sink以及Sink移动的网络环境n 缺点需要地理位置信息的支持网格大小不容易确定内容提要lWSN路由协议概述 lWSN路由协议分类 l能量感知路由协议 l基于查询的路由协议 l集群结构路由协议 l地理位置路由协议地理位置信息n 地理位置信息路由协议要求每个节点地理位置信息路由协议要求每个节点知道自知道自己在网络中的位置己在网络中的位置n 下列方法可确定节点位置下列方法可确定节点位置GPS(Global Positioning System)超声波三角定位系统标定标定n 用途用途地理位置信息作为其它路由算法的辅助 直接用于路由的计算地理位置信息路由协议GPSR：

36、Greedy Perimeter Stateless RoutingGPSR 贪婪算法 利用节点的地理位置信息 转发节点（下一跳）选取： 选择邻居节点中离目的节点D最近的点作为转发节点贪婪算法的缺点：出现局部优化问题局部优化问题存在x到D的路径x的邻居w,y离D的距离比x大解决方法：边界转发空旷区域空旷区域边界转发n 平面图：二维空间结构；平面图中任意两条边都不相交；n GPSR算法中构造平面图的方法是删除网络拓扑图中交叉的边 n 算法：RNG(Relative Neighborhood Graph)GG(Gabriel Graph) RNGn 节点u，v之间存在边的条件是对于任意一个节点w，

37、u到v的距离要小于或等于u到w或是v到w的距离的最大值，用下式表示： ),(),(max),(:,wvdwudvudvuwGGn 节点u，v之间存在边的条件是在以d(u，v)为直径的圆中没有其它节点，用下式表示： ),(),(),(:,222wvdwudvudvuw边界转发时的右手法则 一个数据分组从节点y到达节点x； 下一条边的选择： 下一边是以x为顶点，沿(x，y)逆时针方向上的第一条边，图中为(x，z) 后续各边同样依次法则确定 Facen 平面图的边将整个图分成许多小的互不重叠的有界多边形和一些无界区域，这些有界多边形和无界区域统称为face。n 其中，有界区域称为内部face，无界区

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

39、时通过泛洪查找到目的节点的路由nf-GEDIR(f表示泛洪)和c-GEDIR ： 发生局部优化问题，采用尽最大努力发送的方式：f-GEDIR：向所有邻节点广播该分组 c-GEDIR：选择部分邻节点转发该分组 收到数据包的节点继续使用GPSR协议转发该数据分组n2-hop GEDIR ：节点保存一跳和两跳范围邻居节点的位置信息 常用的贪婪策略n MFR(Most Forward within Radius)：使到目的节点的跳数最少n NFP(Nearest with Forward Progress)： 使节点之间干扰最少n CR(Compass Routing) ：减小数据传输范围地理位置信息

40、路由协议GEAR ：Geographic and Energy Aware RoutingGEAR路由协议n 应用建立到特定区域的路由查询工作方式n 前提 已知目标区域的位置信息节点知道自己位置信息和剩余能量节点间无线链路是对称的GEAR路由过程n 分两个阶段：查询消息到达目的区域的路径查询消息在目标区域的传播n 选路依据 节点到查询区域通信能量能耗 节点本身的剩余能量 最小代价节点为转发节点GEAR路由过程n 查询命令传送到目标区域贪婪算法选择邻居节点到达指定区域的代价 估计代价： F(Ni ,R)=Distance( Ni , R) + (1)Left_Enery(Ni ) 实际代价：F(

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

42、的Flooding；考虑了消耗的能量和节点剩余能量，均衡消息；路径选择可达到局部最优；迭代地理转发对洪泛机制的补充；n 缺点可能出现路由空洞（局部信息）- 两跳信息；不适合在移动WSN使用WSN路由协议最新研究成果n现阶段WSN路由设计主要关注下面几个方面提高能量效率，实现网络负载的平衡，延长网络生存时间；满足各种应用场景的参数指标(也就是QOS)；实现一定程度的数据安全性。一种平衡网路能量和负载的路由协议Joint Mobility and Routing for Lifetime Elongation in Wireless Sensor Networks一种平衡网路能量和负载的协议n 需

43、要解决的问题多源单汇数据流远远大于控制流离汇聚节点近能量消耗快需要解决流量和能量的均衡问题一种平衡网路能量和负载的协议n 提出的方法l最优移动策略Sink节点在网络外边界移动，左图为圆形网络模型，灰色区域是Sink节点移动区域。汇聚节点移动B为Sink节点,Rm为其移动圆形轨迹半径，R为网络半径，最好RmR一种平衡网路能量和负载的协议n 路由方法mRR最好是取一个和Sink移动区节点数据Sink移动区外节点数据数据沿着以O为中心的环转发，直到该数据包到达OB(B为节点Sink所在的位置)线附近的一个节点，到达该节点后再沿着OB，采用最短路径算法到达Sink节点。直接采用最短路径路由算法到达Si

44、nk节点 。一种平衡网路能量和负载的协议n 优点 提出了一种新思路，通过Sink移动的方式从一定程度上削弱了网络中能耗和负载不平衡的现象n 缺点 大多数应用背景下要求Sink节点固定； 普通节点定位Sink节点的问题不能很好的解决；一种跨层设计路由协议Cross-Layer Scheduling for Power Efficiency in Wireless Sensor Networks一种跨层设计路由协议n 网络协议软件设计方法 分层设计比较成熟的方法，比如TCP/IP。分层的设计方法使协议设计规范化，但是效率不高。 跨层设计不成熟，设计复杂，但是效率高，系统优化性能强。传输控制层物理层

45、网络层数据链路层应用层一种跨层设计路由协议p 方法传感器采样事件(S，Sample)节点接收数据事件(R，Receive)节点发送数据事件(T，Transmit) 每个节点在事件发生时醒来工作，其他时间休眠一种跨层设计路由协议n时间片分配约束时间片的分配保证相邻节点的R与T事件互相配合。时间片调度要避免冲突6号节点接收事件与其邻居节点4和9的发送事件时刻匹配4号节点在发送数据时，其邻居节点2和5都不能接收(会发生隐终端的问题)和发送数据(会引起数据冲突)R与T的匹配自动建立路径一种跨层设计路由协议n 优点 无需路由维护，网络开销小； 节点休眠，节省了能量；n 缺点 需要比较精确的节点同步； 对拓扑变化敏感，不能快速调整节点的时间片调度；WSN路由协议未来的研究方向传感器网络路由协议未来的研究方向p 新型网络结构的提出p 节点密集部署及空间多样性的考虑p 网内存储及网内处理p 时间和位置的同步p 自组织与重配置p 主动传感器网络习题1、WSN路由协议与传统路由协议的异同。2、WSN路由协议的设计要求与关键技术。3、WSN路由协议的分类。4、能量感知路由。5、以数据为中心的路由协议。（Flooding协议、Gossiping协议、SPIN协议、Directed Diffusion协议、Rumor协议）