无线传感网路由协议

1、第四章 路由协议 lWSN路由协议概述 lWSN路由协议分类 l能量感知路由协议 l基于查询的路由协议 l集群结构路由协议 l地理位置路由协议 重要性：在传感节点和网络汇聚节点之 间建立高效的传输路径。 lWSN路由协议概述 lWSN路由协议分类 l能量感知路由协议 l基于查询的路由协议 l集群结构路由协议 l地理位置路由协议 n 定义： nWSN路由协议是一套将数据从源节点传输到目的节点的机制。 n 路由是WSN的核心技术之一 n WSN不适合设计通用的路由协议：能耗、 计算复杂度。 nWSN是无基础设施的网络，一般用电池供电、 无人看守，电池不能补充，要延长网络寿 命就必须降低能耗。 n

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

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

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

5、 数据内爆，但在较大规模网络中，ADV内爆仍然存在。 53 该协议考虑到了WSN中的数据冗余问题：临近的 节点所感知的数据具有相似性，通过节点间协商 (Nagotiation)的方式减少网络中数据的传输的 数据量。节点只广播其他节点所没有的数据以减 少冗余数据，从而有效减少能量消耗。 在SPIN协议中提出了元数据（mete data，是对 节点感知数据的抽象描述）的概念，元数据是原 始感知数据的一个映射，可以用来描述原始感知 数据，而且元数据所需的数据位比原始感知数据 要小，采用这种变相的数据压缩策略可以进一步 减少通信过程中的能量消耗。 54 SPIN协议采用三次握手协议来实现数据的交互，

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

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

8、组： ADV（相当于数据的索引，很短）、REQ、DATA n协商通过元数据进行协商通过元数据进行 元数据描述实数据 元数据与实数据一一对应 n协议消息协议消息 消息广播包：Advertise (ADV)Advertise (ADV) 数据请求包：Request (REQ)Request (REQ) 数据包：Data transfer (DATA)Data transfer (DATA) A A A A A A 节点A有新数据，通过ADV发 布新数据信息，使用元数据 B节点收到ADV后，发现自己 没有该数据，通过REQ向A请求 新数据 A节点向B节点传送源数据 B节点融合新数据，并通过 ADV发

9、布新数据消息 如果节点ADV中描述的数据的 副本就忽略该消息 图图 SPINSPIN协议工作流程协议工作流程 n通过和邻居节点的协商来通过和邻居节点的协商来减少减少FloodingFlooding带来的带来的内爆内爆 和重叠和重叠的影响的影响 n通过通过元数据元数据来完成协商过程来完成协商过程 元数据：一种对源数据的映射，比源数据短 避免传输冗余数据 n3 3步握手协议步握手协议(ADV-REQ-DATA)(ADV-REQ-DATA) nSPIN-2SPIN-2在在SPIN-1SPIN-1的基础上加入了能量阈值的基础上加入了能量阈值 当一个节点的剩余能量低于能量阈值后，减少其在协议中参 与的活

10、动。 SPIN2模式考虑了剩余能量值，当节点 能量值低于某个门限值时，该节点就不 再参与DATA报文的转发，只是接收报文 和发出REQ报文，进一步降低了能耗 模拟结果表明，SPIN2比传统方式节省 能耗一半以上 SPIN利用三步握手机制 （解决内爆） SPIN利用数据融合（DC），部分解决 了重叠问题 n优点 解决了内爆问题和部分解决了重叠问题 不需要进行路由维护 对网络拓扑变化不敏感，可用于移动WSN n缺点 本质上SPIN还是向全网扩散新消息，开销 比较大 当多个节点向同一个节点同时发送REQ时， 需要退避算法 SPIN协议还包括了4个协议： SPIN-BC：适合于广播信道的SPIN协议

11、SPIN-PP：适合于点对点信道的SPIN协议 SPIN-EC：在SPIN-PP基础上增加了能量限 制 SPIN-RL：考虑信道上存在分组丢失的SPIN 协议 DD:Directed DD:Directed DiffusionDiffusion 定向扩散定向扩散 思路：Sink节点周期性地广播一种称为 “兴趣”的分组，告诉其他节点，我要 收集什么兴趣。兴趣在扩散的过程中也 反向建立了路由路径，与“兴趣”匹配 节点通过路径传送数据到Sink节点 三个阶段： 兴趣扩散（采用泛洪）； 梯度建立（反向建立）； 强化路径（Sink节点会收到多条路径，选 最优路径，进行加强，以后的数据按照加 强路径传送）

12、 图 DD路由机制 nSink节点查询兴趣消息 兴趣消息采用泛洪的方法传播到网络 有和兴趣匹配数据的节点发送数据 兴趣扩散阶段建立节点到Sink的路径 n兴趣的定义： 由属性值对组成 type = four-legged animal / detect animal location interval = 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

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

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

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

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

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

18、转发，并记录 查询消息中的相关信息，形成查询消息的路径。 查询消息也具有一定的生存期，以解决环路问题。 79 lWSN路由协议概述 lWSN路由协议分类 l能量感知路由协议 l基于查询的路由协议 l集群结构路由协议 l地理位置路由协议 n地理位置信息路由协议要求每个节点地理位置信息路由协议要求每个节点知知 道自己在网络中的位置道自己在网络中的位置 n下列方法可确定节点位置下列方法可确定节点位置 GPS(Global Positioning System)Global Positioning System) 超声波三角定位系统 标定标定 n用途用途 地理位置信息作为其它路由算法的辅助 直接用于路

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

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

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

22、l Routing Algorithm)： 发生局部优化问题时通过泛洪查找到目的节点的路由 nf-GEDIR(f表示泛洪)和c-GEDIR ： 发生局部优化问题，采用尽最大努力发送的方式： f-GEDIR：向所有邻节点广播该分组 c-GEDIR：选择部分邻节点转发该分组 收到数据包的节点继续使用GPSR协议转发该数据分组 n2-hop GEDIR ： 节点保存一跳和两跳范围邻居节点的位置信息 nMFR(Most Forward within Radius)： 使到目的节点的 跳数最少 nNFP(Nearest with Forward Progress)： 使节点之间干扰 最少 nCR(Com

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

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

25、传送到Nmin的代价 n优点 利用了位置信息，避免了查询消息的Flooding； 考虑了消耗的能量和节点剩余能量，均衡消息； 路径选择可达到局部最优； 迭代地理转发对洪泛机制的补充； n缺点 可能出现路由空洞（局部信息）- 两跳信息； 不适合在移动WSN使用 n现阶段WSN路由设计主要关注下面几个 方面 提高能量效率，实现网络负载的平衡，延 长网络生存时间； 满足各种应用场景的参数指标(也就是 QOS)； 实现一定程度的数据安全性。 Joint Mobility and Routing for Lifetime Elongation in Wireless Sensor Networks n需要解决的问题 多源单汇数据流远远大于控制流 离汇聚节点近能量消耗快 需要解决流量和能量的均衡问题 n提出的方法 l最优移动策略 Sink节点在网络外边 界移动，左图为圆形 网络模型，灰色区域 是Sink节点移动区域。 汇聚节点移动 B为Sink