第13章-物联网通信技术(曾宪武)LXX20147

1、第13章无线传感器网络的路由协议1 1 第13章无线传感器网络的路由协议13.1WSN路由协议的特点和性能指标本路由协议的特点和性能指标本13.2能量感知路由能量感知路由13.3查询路由查询路由13.4地理位置路由地理位置路由13.5可靠路由协议可靠路由协议本章小结本章小结第13章无线传感器网络的路由协议2 213.1 WSN路由协议的特点和性能指标路由协议的特点和性能指标13.1.1 WSN路由协议的特点路由协议的特点对于一般的无线网络， WSN路由协议主要用于提供较高的服务质量， 均等、 高效地利用网络带宽传送数据。 因此， 网络路由协议的主要任务是寻找一条高质量的、 带宽利用率高的源节点

2、到目的节点的通信路由， 并且所寻找到的路由还应具有避免网络拥塞、 均衡网络流量的性能。一般不考虑或极少考虑节点能量的消耗。第13章无线传感器网络的路由协议3 3在WSN中， 各节点的能量是有限的。 节点的能量消耗完， 一般无法补充， 该节点随之死亡。 因此， WSN的路由需要考虑节点的能量消耗问题， 使节点能量的消耗尽量要小。 另外， WSN中的节点数量往往很大， 各节点一般无法获得整个网络拓扑结构的信息， 只能得到局部拓扑结构信息， 因此， WSN的路由协议应在有限的局部网络拓扑信息的基础上选择合适的数据传输路径。第13章无线传感器网络的路由协议4 4还有， WSN具有很强的应用相关性。 由

3、于不同应用所采用的路由协议可能差别很大， 因此无法采用一个通用的路由协议来满足其应用相关性的要求。 此外， WSN中的节点在通信时还需进行数据融合， 以减少通信负荷， 节省传输能量。 与一般传统无线网络的路由协议相比， WSN路由协议具有以下特点： 第13章无线传感器网络的路由协议5 5（1） 节点的能量消耗小且均衡。 由于WSN中的节点能量有限， 且一般无法补充。 当WSN中的某些节点由于能量的耗尽而死亡时， 可能导致整个网络无法运行， 以致死亡。 因此， 尽量减小节点能量的消耗， 使整个WSN中所有节点尽可能均衡地消耗能量（也就是尽量减少某些节点的能量消耗过快， 而其他节点的能量消耗过慢）

4、， 从而延长整个网络的生存期， 这是WSN路由协议设计的重要目标。第13章无线传感器网络的路由协议6 6（2） 网络拓扑信息、 计算资源有限。 WSN为了节省通信时节点的能量， 通常采用多跳的通信模式。 另外， 由于WSN的节点是低成本的， 不具有较高的存储能力和计算能力， 也无法存储太多包括拓扑结构在内的网络信息， 节点所存储的拓扑信息是局部的。 因此， 节点无法进行太复杂的计算， 得到全局优化路由。 为此， 如何实现简单有效的路由机制就成为WSN的基本问题。第13章无线传感器网络的路由协议7 7（3） 以数据为核心。 WSN中的节点采集的数据， 将向汇聚节点传输。 转发节点所转发的数据很可

5、能是采集的同一个信息， 因此会出现数据的冗余的现象， 需要在转发节点进行数据融合， 以降低数据的冗余率， 减少转发的数据量， 从而降低能耗。 第13章无线传感器网络的路由协议8 8另外， WSN的网络规模较大， WSN的节点一般采用随机部署的方式获取有关监测区域的感知数据。 整个系统更关心的是感知数据， 而不是具体哪个节点获取的信息， 因而WSN信息的获得不依赖于节点的地址信息， 而是局部区域内所感知的信息。 所以WSN的通信协议是以数据为中心的。 第13章无线传感器网络的路由协议9 9（4） 与应用密切相关。 由于WSN应用目的不同、 应用环境也不同， 这就决定了WSN模式的不同， 因此无法

6、找到一个路由机制能适合所有的应用目的和应用环境， 这是WSN应用相关性的一个体现。 这就要求应用者应从实际出发， 结合具体的应用需求， 设计与之适应的特定路由机制。 第13章无线传感器网络的路由协议10 1013.1.2 WSN路由协议的性能指标及分类路由协议的性能指标及分类1. 性能指标WSN路由协议的设计目标是： 延长网络生命周期， 提高路由的容错能力， 形成可靠的数据转发机制。 评价一个WSN路由协议设计的性能指标一般包括WSN的生命周期、 传输延迟、 鲁棒性、 可扩展性等。 第13章无线传感器网络的路由协议11 11（3） 鲁棒性。 一个系统的鲁棒性是指该系统在一定的参数摄动（变化）下

7、， 能维持系统性能稳定的能力。 WSN的路由算法应具备自适应性和容错性， 在部分节点因为能源耗尽或受环境干扰而死亡或失效的情况下， 整个WSN能正常运行。 （4） 可扩展性。WSN应该能够方便地进行规模扩展。 节点的加入和退出都将导致网络规模的变动， 优良的路由协议应该体现很好的扩展性， 节点数量的变动不至于影响网络的性能和通信质量。第13章无线传感器网络的路由协议12 122. WSN路由协议的分类从具体应用的角度出发， 根据不同应用对WSN各种特性的敏感度不同， 可将路由协议分为四种类型： （1） 能量感知型。能量感知型路由协议从数据传输中的能量消耗出发， 讨论最优能量消耗路径以及最长网络

8、生存时间等问题。 第13章无线传感器网络的路由协议13 13（2） 查询型。 在诸如环境检测、 战场评估等应用中， 需要不断查询传感器节点采集的数据， 查询节点（汇聚节点）发出查询命令， 传感器节点向查询节点报告采集的数据。 在这类应用中， 通信流量主要是查询节点和传感器节点之间的命令和数据传输， 同时传感器节点的采集信息在传输路径上通常要进行数据融合， 以减少通信负荷， 节省能量。第13章无线传感器网络的路由协议14 14（3） 地理位置型。 在诸如目标跟踪类应用中， 往往需要唤醒距离跟踪目标最近的传感器节点， 以得到关于目标的精确位置等相关信息。 在这类应用中， 通常需要知道目的节点的精确

9、或者大致地理位置。 把节点的位置信息作为路由选择的依据， 不仅能够完成节点路由功能， 还可以降低系统专门维护路由协议的能耗。 第13章无线传感器网络的路由协议15 15（4） 可靠型。 WSN的某些应用对通信的服务质量有较高要求， 如可靠性和实时性等。 在WSN中， 链路的稳定性难以保证， 通信信道质量比较低， 拓扑变化比较频繁， 要保证服务质量， 需要设计相应的可靠的路由协议。 第13章无线传感器网络的路由协议16 1613.2 能量感知路由能量感知路由 13.2.1 能量路由能量路由能量路由是根据节点的可用能量(Power Available, PA)或传输路径上的能量需求， 选择数据的转

10、发路径。 节点可用能量就是节点当前的剩余能量。 第13章无线传感器网络的路由协议17 17图13.2.1中的大写字母表示节点， 字母右侧括号内的数字表示节点可用能量， 双向线表示节点之间的通信链路，链路上的数字表示在该链路上发送数据所消耗的能量。 源节点是具有数据采集功能的一般性节点， 汇聚节点是数据传送到达的目标节点。 从图13.2.1可以得到如表13.2.1所示的从源节点到汇聚节点的传输路径。 第13章无线传感器网络的路由协议18 18图13.2.1 一个WSN能量路由算法示意图第13章无线传感器网络的路由协议19 19第13章无线传感器网络的路由协议2020能量路由策略主要包括以下几点：

11、 （1） 最大可用能量(PA)路由。路由策略： 从源节点到汇聚节点的所有路径中选取节点可用能量PA之和最大的路径。 在图13.2.1中路径2的PA之和最大（PA=6）， 但路径2包含了路径1， 因此该路径不是高效的路径， 从而被排除。 于是， 只有选择路径4（PA=5）作为最大可用能量(PA)路由。第13章无线传感器网络的路由协议21 21（2） 最小能量消耗路由。 路由策略： 从源节点到汇聚节点的所有路径中， 选取节点耗能之和最小的路径。 在图13.2.1中， 由于路径1所消耗的能量最小， 仅为3， 所以选择路径1作为最小能量消耗路由。 （3） 最少跳数路由。路由策略： 选取从源节点到汇聚节

12、点间跳数最少的路径。 在图13.2.1中， 由于路径3仅有1跳， 所以选择路径3作为最少跳数路由。 第13章无线传感器网络的路由协议2222（4） 最大最小PA节点路由。路由策略：每条路径上有多个节点， 且节点的可用能量不同， 从中选取每条路径中可用能量最小的节点来表示这条路径的可用能量， 并且选择可用能量最大的路径为最大最小PA节点路由。 在图13.2.1中， 路径1的最小PA节点为PA=2， 路径2的最小PA节点为PA=2， 路径3中最小PA节点为PA=3， 路径4中最小PA节点为PA(E)=1。 4条路径中PA最大的为路径3，所以选择路径3作为最大最小PA节点路由。 最大最小PA节点路由

13、策略就是选择路径可用能量最大的路径。 第13章无线传感器网络的路由协议232313.2.2 能量多路径路由能量多路径路由传统网络的路由机制往往选择源节点到目的节点之间跳数最小的路径来传输数据。 但在WSN中， 如果多次使用同一条路径传输数据， 就会造成该路径上的节点因能量消耗过快而过早死亡， 从而造成整个网络的分割现象。 第13章无线传感器网络的路由协议2424WSN可分割成互不相连的几个孤立部分， 以缩短整个网络的生命周期。 为此， 可采用能量多路径路由机制来解决该问题。 这种机制是在源节点和目的节点之间建立多条路径， 根据路径上节点的通信能量消耗以及节点的剩余能量情况， 给每条路径赋予一定

14、的选择概率， 使得数据传输均衡消耗整个网络的能量， 从而延长整个网络的生命周期。第13章无线传感器网络的路由协议2525能量多路径路由协议由路径建立、 数据传输和路由维护三个过程构成。 其中， 路径建立过程是该协议的重点内容。 在能量多路径机制中， 每个节点需要知道到达目的节点的所有下一跳节点， 并计算选择每个下一跳节点传输数据的概率。 概率的选择是根据节点到目的节点的通信代价来计算的， 可用Cost(Ni)来表示节点i到目的节点的通信代价。 由于每个节点到达目的节点的路径很多， 所以这个代价值是各个路径的加权平均值。 第13章无线传感器网络的路由协议2626能量多路径路由的主要算法描述如下：

15、 （1） 启动路径建立。 目的节点向邻居节点广播路径建立消息， 启动路径建立过程。 路径建立消息中包含一个代价域， 表示发出该消息的节点到目的节点路径上的能量信息， 初始值设置为零。 （2） 确定消息转发。 当节点收到相邻节点发送的路径建立消息时， 相对发送该消息的相邻节点只有当自己距源节点更近， 而距离目标节点更远的情况下， 才需要转发该消息， 否则将丢弃该消息。第13章无线传感器网络的路由协议2727（3） 计算信能量消耗。 如果该节点决定转发路径建立消息， 那么需要计算新的代价值来替换原来的代价值。 当路径建立消息从节点Ni发送到节点Nj时， 该路径的通信值为节点i的代价值加上两个节点间

16、通信能量消耗， 即(13.2.1)式中， CNj, Ni表示节点Nj发送数据经节点Ni路径到达目的节点的代价， Metric(Nj, Ni)表示节点Nj到节点Ni的通信能量消耗， 可用下式计算：第13章无线传感器网络的路由协议2828式中， eij表示节点Nj和节点Ni直接通信的能量消耗，Ri表示节点Ni剩余能量， 、 为常数。 这个度量综合考虑了节点的能量消耗以及节点的剩余能量。 (13.2.2)第13章无线传感器网络的路由协议2929（4） 计算与添加本地路由表。 节点要放弃能量消耗代价很大的路径。 节点 j 将节点i加入到本地路由表FTj中的条件为(13.2.3)式中， 为大于1的系统参

17、数。 第13章无线传感器网络的路由协议3030（5） 计算下一跳选择概率。 节点对路由表中每个下一跳计算选择概率， 节点选择概率与能量消耗成反比。 节点Nj采用下式计算选择节点Ni的概率：（13.2.4）第13章无线传感器网络的路由协议31 31（6） 计算能量代价及广播消息。 节点根据路由表中每项的能量代价和下一跳节点选择概率计算本节点到目的节点的代价Cost（Nj）， 它被定义为经由路由表中节点到达目的节点的代价的平均值， 即节点Nj将用Cost(Nj)值替换消息中原有的代价值， 然后向相邻节点广播该路由建立消息。 第13章无线传感器网络的路由协议3232 13.3 查查 询询 路路 由由

18、13.3.1 定向扩散路由定向扩散路由定向扩散(Directed Diffusion, DD)路由是一种查询机制的路由。 汇聚节点以兴趣消息(Interest Information)向WSN发布查询任务。 兴趣消息的传送采用洪泛方式传播到整个区域或部分区域内的所有传感器节点处。 第13章无线传感器网络的路由协议3333兴趣消息表示查询任务， 并发送网络用户对监测区域内感兴趣的信息， 例如监测区域内的环境信息。 在兴趣消息的传播过程中， 协议逐跳地在每个传感器节点上建立反向的从源节点到汇聚节点的数据传输梯度(Gradient)。 传感器节点将采集到的数据沿着梯度方向传送给汇聚节点。 定向扩散路

19、由机制可以分为兴趣扩散、 梯度建立以及路径加强三个阶段， 如图13.3.1所示。 第13章无线传感器网络的路由协议3434图13.3.1 定向扩散路由机制第13章无线传感器网络的路由协议35351. 兴趣扩散阶段在兴趣扩散阶段， 汇聚节点周期性地向相邻节点广播兴趣消息。 兴趣消息中含有任务类型、 目标区域、 数据发送速率、 时间戳等参数。 每个节点在本地保存一个兴趣列表， 对于每个兴趣， 列表中都有一表项， 用来记录发送该兴趣消息的邻居节点、 数据发送速率和时间戳等与任务相关的信息， 以建立该节点向汇聚节点传递数据的梯度关系。第13章无线传感器网络的路由协议3636每个兴趣可能对应多个相邻节点

20、， 每个相邻节点对应一个梯度信息。 通过定义不同的梯度相关参数， 可以满足不同的应用需求。 每个表项还有一个字段， 用来表示该表项的有效时间值， 若超过这个时间值， 节点将删除这个表项。 第13章无线传感器网络的路由协议3737当节点收到相邻节点的兴趣消息时， 首先检查兴趣列表中是否存有参数类型与刚收到的兴趣消息相同的表项， 且该表项对应的发送节点是该相邻节点， 如果有对应的表项， 就更新表项的有效时间值； 如果只是参数类型相同， 但不包含发送该兴趣消息的相邻节点， 就在相应表项中添加这个相邻节点； 对于任何其他情况， 都需要建立一个新表项来记录这个新的兴趣消息。第13章无线传感器网络的路由协

21、议38382. 梯度建立阶段当传感器节点采集到与兴趣匹配的数据时， 会把数据发送到梯度上的相邻节点， 并按照梯度上的数据传输速率设定传感器模块传输数据的速率。 由于可能从多个相邻节点收到兴趣消息， 节点向多个相邻节点发送数据， 汇聚节点可能收到经过多个路径的相同数据。 第13章无线传感器网络的路由协议3939中间节点收到其他节点转发的数据后， 首先查询兴趣列表的表项， 如果没有匹配的兴趣表项就丢弃数据； 如果存在相应的兴趣表项， 则检查这个兴趣对应的数据缓冲池(Data Cache)。 数据缓冲池用来保存最近转发的数据。 如果在数据缓冲池中有与接收到的数据匹配的副本， 就说明已经转发这个数据。

22、 第13章无线传感器网络的路由协议4040为避免出现传输回环， 应丢弃这个数据； 否则， 检查该兴趣表项中相邻节点的信息， 如果设置的相邻节点的数据传输速率大于等于接收的数据传输速率， 则全部转发接收的数据； 如果设置的相邻节点的数据传输速率小于接收的数据传输速率， 则按照比例转发。 对于转发的数据， 数据缓冲池保留一个副本， 并记录转发时间。 第13章无线传感器网络的路由协议41 413. 路径加强阶段定向扩散路由机制以正向加强机制来优化路径， 并根据网络拓扑的变化修改数据转发的梯度关系。 兴趣扩散阶段是为了建立源节点到汇聚节点的数据传输路径， 数据源节点以较低的速率采集和发送数据， 这个阶

23、段建立的梯度称为探测梯度(Probe Gradient)。 汇聚节点在收到从源节点发来的数据后， 启动建立源节点的加强路径， 后续数据将沿着加强路径以较高的数据传输速率进行传输。 加强后的梯度称为数据梯度(Data Gradient)。 第13章无线传感器网络的路由协议4242如果用传输延迟作为路由加强的标准， 则汇聚节点首先选择发送来最新数据的相邻节点作为加强路径的下一跳节点， 并向该相邻节点发送路径加强消息。 路径加强消息中包含新设定的较高的发送数据传输速率值。 相邻节点收到该消息后， 经过分析确定该消息描述的是一个已有的兴趣消息， 仅是为了增加数据传输速率， 于是断定这是一条路径加强消息

24、， 从而更新相应兴趣表项得到相邻节点的数据传输速率。 同时， 按照同样的规则选择加强路径下一跳的相邻节点第13章无线传感器网络的路由协议4343路由加强的标准不是唯一的。 可以选择在一定时间内发送数据最多的节点作为路径加强的下一跳节点， 也可以选择数据传输最稳定的节点作为路径加强的下一跳节点。 加强路径上的节点如果发现下一跳节点的传输数据速率明显减小， 或者收到来自其他节点的新位置估计，推断加强路径的下一跳节点可能失效， 就需要使用上述的路径加强机制重新确定下一跳节点。 第13章无线传感器网络的路由协议444413.3.2 谣传路由谣传路由在数据传输量较少或者已知事件区域的情况下， 如果采用定

25、向扩散路由， 则需采用查询消息的洪泛传播和路径增强机制， WSN才能确定一条优化的数据传输路径。 因此， 在这种情况下， 路由效率不高， 而需采用其他高效率的路由机制。 谣传路由(Rumor Routing)较适合于这类数据量传输较小的情况。 谣传路由机制采用了查询消息的单播随机转发方式， 避免了洪泛方式建立转发路径带来的开销过大问题。 第13章无线传感器网络的路由协议4545谣传路由机制的基本思想是： 事件区域中的传感器节点产生代理(Agent)消息， 代理消息沿随机路径向外扩散传播， 同时汇聚节点发送的查询消息也沿随机路径在WSN中传播。 当代理消息和查询消息的传输路径交叉在一起时， 就会

26、形成一条汇聚节点到事件区域的完整路径。谣传路由机制的原理如图13.3.2所示。 第13章无线传感器网络的路由协议4646图图13.3.2 谣传路由机制原理图谣传路由机制原理图第13章无线传感器网络的路由协议4747谣传路由的建立经过以下几个过程： （1） 相邻节点列表与事件列表的维护。 每个传感器节点维护一个相邻WSN节点列表和一个事件列表。 事件列表的每个表项都记录事件相关的信息， 主要包括事件名称、 事件区域的跳数、 事件区域的下一跳相邻节点等信息。 当传感器节点在本地监测到一个事件发生时， 在事件列表中增加一个表项， 用来设置事件名称、 跳数（此时跳数为零）等， 同时根据一定的概率产生一

27、个代理消息。 第13章无线传感器网络的路由协议4848（2） 代理消息的传输。 代理消息中包含了与生命期等事件相关的分组信息， 将携带的事件信息通告给传输中经过的每个传感器节点。 对于收到代理消息的节点， 首先检查事件列表中是否有与该事件相关的表项， 如果列表中存在相关表项， 就比较代理消息和表项中的跳数值， 如果该节点中列表的跳数值小， 就更新表项中的跳数值， 否则更新代理消息中的跳数值。 如果事件列表中没有该事件相关的表项， 就增加一个表项来记录代理消息携带的事件信息。 第13章无线传感器网络的路由协议4949（3） 查询消息的转发。 WSN的任何节点都可能生成一个对特定事件的查询消息。

28、如果节点的事件列表中保存有该事件的相关表项， 说明该节点在到达事件区域的路径上， 它沿着这条路径转发查询消息， 否则， 节点随机选择相邻节点转发查询消息。 查询消息经过的节点按照同样方式转发， 并记录查询消息中的相关信息， 形成查询消息的路径。 查询消息也具有一定的生命期， 以解决环路问题。 第13章无线传感器网络的路由协议5050（4） 谣传路由的形成。 如果查询消息和代理消息的路径交叉， 交叉节点就会沿查询消息的反向路径将事件信息传送到咨询节点， 并形成谣传路由。 如果查询节点在一段时间内没有收到事件消息， 就认为查询消息没有到达事件区域， 可以选择重传、 放弃或者洪泛查询消息的方法。 由

29、于洪泛查询机制的代价过高， 一般作为最后的选择。 第13章无线传感器网络的路由协议51 5113.4 地理位置路由地理位置路由在WSN中， 节点通常需要获取自身的位置信息， 这样它采集的数据才有意义。 地理位置路由假设节点知道自己的地理位置信息， 以及目的节点或者目的区域的地理位置。 WSN利用这些地理位置信息作为路由选择的依据， 节点按照一定策略转发数据到目的节点。 地理位置的精确度和代价相关， 在不同的应用中会选择不同精确度的位置信息来实现数据的路由转发。第13章无线传感器网络的路由协议5252GEAR(Geographical and Energy Aware Routing)路由是根据

30、事件区域的地理位置信息， 建立汇聚节点到事件区域的优化路径的。 该机制可避免洪泛传播方式带来较大的路由建立的开销， 降低节点的能量消耗。 GEAR路由假设已知事件区域的位置信息， 每个节点知道自己的位置信息和剩余能量信息， 并通过一个简单的Hello消息交换机制知道所有相邻节点的位置信息和剩余能量信息。 在GEAR路由中， 节点间的通信链路是对称的。 第13章无线传感器网络的路由协议5353 GEAR路由中， 查询消息传播分为两个阶段。 第一阶段， 汇聚节点发出查询命令， 并根据事件区域的地理位置将查询命令传送到区域内距汇聚节点最近的节点； 第二阶段， 该节点将查询命令传输到区域内的其他所有节

31、点， 监测数据沿查询消息的反向路径向汇聚节点传送。 第13章无线传感器网络的路由协议54541. 查询消息传送到事件区域GEAR路由用实际代价(Learned Cost)和估计代价(Estimate Cost)两种代价值表示路径代价。 当路径未建立时， 中间节点使用估计代价来决定下一跳节点。 估计代价定义为归一化的节点到事件区域的通信所消耗的能量和节点的剩余能量之和。 节点到事件区域的距离用节点到事件区域几何中心的距离来表示。 第13章无线传感器网络的路由协议5555由于所有节点均知道自己的位置和事件区域的位置， 因而所有节点都能够计算出自己到事件区域几何中心的距离。节点计算自身到事件区域估计

32、代价值为c（N， R）=d（N， R）+（1）e（N）（13.4.1)式中， c(N, R)为节点N到事件区域R的估计代价， d(N, R)为节点N到事件区域R的距离， e(N)为节点N的剩余能量， 为比例参数。 d(N, R)和e(N)均为归一化后的值。 第13章无线传感器网络的路由协议5656查询信息到达事件区域后， 事件区域内的节点沿查询路径的反方向传输监测数据， 该数据携带每跳节点到事件区域的实际能量消耗值。 对于数据传输所经过的各节点， 节点首先记录携带的能量代价， 然后对所记录的能量代价进行更新（即消息中的能量代价+本节点发送该数据到下一跳节点的能量消耗）， 将更新后的能量消耗值连

33、同其他数据转发出去。 节点下一次转发查询消息时， 用刚才记录的与事件区域通信消耗的实际能量代价代替式(13.4.1)中的d(N, R)， 计算其到汇聚节点的实际代价值。 节点用调整后的实际代价选择到达事件区域的优化路径。 第13章无线传感器网络的路由协议5757以汇聚节点开始的路径建立过程一般采用贪婪算法。 节点在相邻节点中选择到事件区域路由代价最小的节点作为下一跳节点， 并将自己的路由代价设为下一跳节点的路由代价加上与该节点一跳通信的代价。 如果节点的所有相邻节点到事件区域的路由代价都比自己的大， 则陷入了路由空洞(Routing Void)， 如图13.4.1所示。第13章无线传感器网络的

34、路由协议5858图13.4.1中， S为汇聚节点， T为目的节点， M7、 M8、 M9为死亡（失效）节点。 节点M3是S的相邻节点中到目的节点的路由代价最小的节点， 但节点M3的所有相邻节点到目的节点T的路由代价都比M3到T的路由代价要大， 并且M7、M8、 M9为死亡（失效）节点， 这就造成了路由空洞。 第13章无线传感器网络的路由协议5959图13.4.1 路由空洞情况示意第13章无线传感器网络的路由协议6060解决的方法为： M3选取路由代价最小的邻居节点M2作为下一跳节点， 并将自己的代价值设置为M2节点的路由代价加上M3节点到M2节点的下一跳的路由代价。 同时， 节点M3将这个新的

35、代价值通知汇聚节点S， S再转发查询命令给节点T时， 选择节点M2作为下一跳节点， 而不选择节点M3。 第13章无线传感器网络的路由协议61 612. 查询消息在事件区域内传播当查询命令传送到事件区域后， 可以洪泛方式传播到事件区域内的所有节点。 但当WSN节点密度较大时， 洪泛方式的能量开销比较大， 这时可以采用迭代地理转发机制， 如图13.4.2所示。 第13章无线传感器网络的路由协议6262图13.4.2 区域内的迭代地理转发示意图第13章无线传感器网络的路由协议6363事件区域内首先收到查询命令的节点， 将事件区域分为若干子区域， 并向所有子区域的中心位置转发查询命令， 在每个子区域中

36、， 靠近区域中心的节点(如图13.4.2中的 Ni)接收查询命令， 并将自己所在的子区域再划分为若干个子区域后向各个子区域中心转发查询命令。 该消息传播过程是一个迭代过程， 当节点发现自己是某个子区域内唯一的节点或某个子区域没有节点存在时， 停止向这个子区域发送查询命令。 当所有子区域转发过程全部结束时， 整个迭代过程终止。 第13章无线传感器网络的路由协议6464当事件区域节点数较多时， 迭代地理转发的消息转发次数少， 而节点较少时使用洪泛策略的路由效率高。 GEAR路由可以使用如下方法在两种机制中作选择： 当查询命令到达区域内的第一个节点时， 如果该节点的相邻节点数量大于一个预设的阈值，

37、则使用迭代地理转发机制， 否则使用洪泛机制。 第13章无线传感器网络的路由协议656513.5 可靠路由协议可靠路由协议13.5.1 不相交的多路径路由机制不相交的多路径路由机制不相交多路径是指从源节点到目的节点之间任意两条路径都没有相交的节点。 其建立过程如图13.5.1所示。 第13章无线传感器网络的路由协议6666图13.5.1 不相交多路径的建立示例第13章无线传感器网络的路由协议6767 汇聚节点首先通过主路径增强消息来建立主路径， 然后发送次优路径增强消息给次优点节点A， 节点A再选择自己的最优节点B， 将次优路径增强信息传递下去。 如果B在主路径上， 则B发回否定增强消息给A，

38、A向次优节点传递次优路径增强信息； 如果B不在主路径上， 则B继续传递次优路径增强信息， 直到构造出一条次优路径。 按照同样的方式， 可继续构造下一条次优路径。第13章无线传感器网络的路由协议6868在不相交多路径中， 备用路径可能比主路径长得多， 为此引入了缠绕多路径(Braid Multipath)的概念。 缠绕多路径可以克服主路径上单个节点死亡（失效）问题。 理想的缠绕多路径是由一组缠绕路径形成的。 一条缠绕路径对应于主路径上的一个节点， 在网络不包括这些节点时， 形成了从源节点到目的节点的优化备用路径。 缠绕路径可作为主路径的一条备用路径， 而主路径上的每个节点都有一条对应的缠绕路径，

39、 这些缠绕路径构成了从源节点到目的节点的缠绕多路径。第13章无线传感器网络的路由协议6969在理想缠绕多路径中， 节点需要知道全局网络拓扑。 对于局部缠绕多路径， 具有如下生成算法： （1） 建立主路径。 （2） 发送备用路径增强消息。 在建立主路径后， 主路径上的每个节点（除了源端和靠近源端的节点以外）都要发送备用路径增强消息给自己的次优节点（记为A）， 次优节点A再寻找其最优节点（记为B）， 传播该备用路径增强消息。 第13章无线传感器网络的路由协议7070（3） 否定增强， 并继续构造。 如果B在主路径上， 则B发回否定增强消息给A， A向次优节点传递次优路径增强信息； 如果B不在主路径

40、上， 则B继续传递次优路径增强信息， 直到构造出一条次优路径。 按照同样的方式， 继续构造下一条次优路径。 备用路径之间具有不同的优先级。 当主路径失效时， 次优路径将被激活成为新的主路径。第13章无线传感器网络的路由协议71 7113.5.2 ReInForM路由路由ReInForM(Reliable Information Forwarding Multiple Path)路由是从数据源节点开始考虑的， 即考虑可靠性需求、 信道质量以及WSN节点到汇聚节点的跳数， 来决定需要的传输路径数目， 以及下一跳节点数目和相应的节点， 从而实现满足可靠要求的数据传输。 第13章无线传感器网络的路由协

41、议7272ReInForM路由机制的基本思路是： 首先， 源节点根据传输的可靠性要求计算需要的传输路径数目； 其次， 在相邻节点中选择若干节点作为下一跳转发节点， 并给每个节点按照一定比例分配路径数目； 然后， 源节点将分配的路径数目作为数据报头中的一个字段发送给邻居节点。 邻居节点在接收到源节点的数据后， 将自己作为数据的源节点并重复上述数据源节点的选路过程。 以下介绍其实现过程。 第13章无线传感器网络的路由协议73731. 主路径的建立根据路由策略， 选择路由算法， 建立源节点到目的节点的主路径。在ReInForM路由中， 定义了一个可靠性参数rs, 0rs1。 该参数表示系统要求的源节

42、点发送数据分组到汇聚节点的成功概率。 每个节点都知道自己到邻居节点的信道质量， 用信道差错率es表示， 0es1， 并假设每个节点到其所有相邻节点的信道质量都相同。 第13章无线传感器网络的路由协议7474传感器节点通过如下机制知道自己到汇聚节点的跳数hs： 汇聚节点周期性地广播路由更新消息， 其中包括一个到汇聚节点跳数的域， 节点收到路由更新消息后， 将消息中的到汇聚节点跳数加1， 并广播这个消息。 这样， 每个节点都能知道自己到达汇聚节点的跳数以及其相邻节点到达汇聚节点的跳数。 源节点根据参数rs、 es和hs就可决定需要多少条传输路径才能保证数据分组可靠地到达汇聚节点。 第13章无线传感

43、器网络的路由协议7575由于es为一条传输链路的错误率， 对于源节点， 经过hs跳后数据分组到达汇聚节点的概率为(1es)hs， 经过P条路径后数据分组不能到达汇聚节点的概率为1(1es)hsP=1rs， 于是(13.5.1)如果需要的成功传输的路径数P大于源节点的相邻节点数目， 则需要某些相邻节点发送多份数据拷贝来满足可靠性要求。 第13章无线传感器网络的路由协议76762. 下一跳节点的选择和路径分配当源节点计算出需要的转发路径数后， 就需在相邻节点中选择下一跳的节点， 并对其分配相应的转发路径。 根据源节点到汇聚节点的跳数， 可将相邻节点分为三类： 与自己到达汇聚节点跳数相同的节点； 比

44、自己到达汇聚节点跳数少一个的节点； 以及比自己到达汇聚节点跳数多一个的节点， 分别用H0、 H、 H+表示。 源节点首先在H中选择一个作为默认的下一跳节点， 默认的下一跳节点转发数据分组的概率为1。 第13章无线传感器网络的路由协议7777由于源节点到默认下一跳节点的数据分组发送成功率为1es， 这条路程相当于1es条成功转发路径。 如果1es大于或等于按照式(13.5.1)计算得到的路径数， 则表明源节点只需要默认下一跳节点转发数据分组就能够满足可靠性要求； 否则， 还需要额外的转发节点， 需要的额外路径数为(13.5.2)第13章无线传感器网络的路由协议7878额外路径应优先从H中选取。

45、只有当按照式(13.5.2)计算的P大于H 时， 需要从H0中选取节点。 只有当P大于(H +H ）时， 才需要从H+中选取。 被选中的节点都要为源节点创建足够的路径数， 以确保所有选中节点能够提供路径总数为P。 我们可用PH 、 PH0和PH+分别表示从H0、 H 和H+所选择的节点作为下一跳为源节点创建的路径数目。 第13章无线传感器网络的路由协议7979设H0、H和H+中所选择的节点数目分别为NH、 NH0和NH+， 于是有(13.5.3)PH、 PH0和PH+按照如下比例进行分配： (13.5.4)第13章无线传感器网络的路由协议80803. 相邻节点的路径重新计算源节点s在发送的数据

46、分组头部加上PH、 es和hs这三个参数。相邻节点i在收到分组后， 按照与路径数相同的概率决定是否转发分组。 如果确定转发该分组， 则节点i将自己作为源节点， 并按照式(13.5.2)， 用本节点的ri、 ei和hi重新计算所需的路径数。 第13章无线传感器网络的路由协议81 81这里的ri是节点i为了保证s指定的可靠性而重新计算出的可靠性值， 按照下式计算：ri=1(1(1ei)hi1)PH(13.5.5)式中， (1ei)hi1表示从节点i成功传送数据分组到汇聚节点的概率， (1(1ei)hi1)PH表示从所有的P条路径都不能成功传送数据分组到汇聚节点的概率。 第13章无线传感器网络的路由

47、协议828213.5.3 SPEED协议协议SPEED协议为一个实时路由协议， 可在一定程度上保证端到端的传输速率、 网络拥塞控制以及负载平衡。 为实现实时性目标， SPEED协议首先交换节点的传输延迟， 以得到网络负载情况； 然后节点利用局部地理信息和传输速率信息进行路由决策， 同时又通过相邻节点的反馈机制以保证网络传输速率不低于一个全局定义的阈值。 第13章无线传感器网络的路由协议8383 SPEED协议主要由以下几部分组成： 第一部分为延迟估计机制， 该机制用来估计WSN的负载情况， 并判断WSN是否发生拥塞。 第二部分为SNGF算法(Stateless Nondeterministic

48、 Geographic Forwarding, SNGF)，用来选择满足传输速率要求的下一跳节点。 第13章无线传感器网络的路由协议8484第三部分为邻居反馈机制(Neighborhood Feedback Loop, NFL)， 是当SNGF路由算法中找不到满足传输速率要求的下一跳节点时采取的补偿机制。 第四部分为反向压力路由变更机制， 用来避免拥塞和路由空洞。 SPEED协议中各部分之间的关系如图13.5.2所示。 第13章无线传感器网络的路由协议8585图13.5.2 SPEED协议框架及组成部分间的关系第13章无线传感器网络的路由协议86861. 延迟估计机制在SPEED协议中， 节点

49、记录了其到达相邻节点的通信延迟， 用来表示WSN局部的通信负载。 通信延迟主要是指在忽略传输延迟的情况下的发送延迟。 在带宽有限的条件下， 如果用专门分组监测节点间的通信延迟， 则开销比较大。 SPEED协议采用数据包捎带的方法得到节点之间的延迟估计机制， 其算法如下： 第13章无线传感器网络的路由协议8787发送节点给数据分组加上时间戳， 接收节点计算从收到数据分组到发出ACK的时间间隔， 并将其作为一个字段加入ACK报文， 发送节点收到ACK后， 从收发时间差中减去接收节点的处理时间， 得到一跳的通信延迟。 在更新记录的延迟值时， 综合考虑新计算的延迟值和原来记录的延迟值， 更新的延迟值是

50、二者的指数加权平均。 节点将计算出的通信延迟通告相邻节点。 假设节点A计算出到节点B的通信延迟， 并将这个通信延迟通告其相邻节点C， 则节点C可以不必计算到节点B的通信延迟， 而使用节点A发送来的通信延迟直接与节点B通信。 第13章无线传感器网络的路由协议88882. SNGF算法节点将相邻节点分为两类： 比自己距离目标区域近的节点和比自己距离目标区域远的节点， 前者称为候选转发节点集合(Forwarding Candidate Set， FCS)。 节点计算到其FCS集合中的每个节点的传输速率。 传输速率定义为节点间的距离除以节点间的通信延迟。 第13章无线传感器网络的路由协议8989如果节

51、点的FCS集合为空， 意味着分组走到了路由空洞中。 这时节点将丢弃分组， 并使用反向压力信标(Backpressure Beacon)消息告诉上一跳节点， 以避免分组再次走到这个路由空洞中。 根据传输速率是否满足预定的传输速率阈值， FCS集合中的节点又分为两类： 大于速率阈值的和小于速率阈值的相邻节点。 第13章无线传感器网络的路由协议9090如果在FCS集合中， 节点的传输速率大于阈值， 则在这些节点中按一定概率分布选择下一跳节点。 节点的传输速率越大， 被选中的概率就越大。 若FCS集合中所有节点的传输速率都小于阈值， 则采用NFL算法， 计算一个转发概率， 并按照该概率转发分组。 如果

52、决定转发分组， FCS内的节点就按照一定的概率分布选择下一跳节点。 第13章无线传感器网络的路由协议91 913. 邻居反馈机制为了保证节点间的数据传输满足一定的传输速率要求， 引入NFL机制。 在NFL机制中，数据丢失和低于传输速率阈值的传送都视为传输差错。 MAC层收集差错信息， 并把到相邻节点的传输差错率通告给转发比例控制器(Relay Ratio Controller)， 转发比例控制器根据这些差错率计算出转发概率， 供SNGF路由算法做出选路决定。 第13章无线传感器网络的路由协议9292满足传输速率阈值的数据按照SNGF算法决定的路由传输出去， 而不满足传输速率阈值的数据传输由邻居NFL计算转发概率。 该转发概率表示网络能够满足传输速率要求的程度， 因此节点按照这个概率进行数据转发。第13章无线传感器网络的路由协议9393节点查看FCS集合中的节点时， 如果存在节点的传输差错率为零， 则表明存在满足传输速率要求的节点， 因而设转发概率为1。 如果FCS集合中所有节点的传输差错率都大于零， 则按照下式计算转发概率：(13.5.6)式中， ei表示到FCS