无线传感器网络 WSN第2章 路由协议讲解

1、无线传感器网络 第二章 路由协议 无线传感器网络 概述（什么是路由协议）概述（什么是路由协议） 路由协议负责将数据分组从源节点通过路由协议负责将数据分组从源节点通过 网络转发到目的节点，它主要包括两个网络转发到目的节点，它主要包括两个 方面的功能：方面的功能： 寻找源节点和目的节点间的优化路径寻找源节点和目的节点间的优化路径 （确定最佳路径）（确定最佳路径） 将数据分组沿着优化路径正确转发将数据分组沿着优化路径正确转发 （数据交换）（数据交换） 无线传感器网络 ad hocad hoc、 无线局域网等传统无线无线局域网等传统无线 网络特点网络特点 ad hoc、 无线局域网等传统无线网络的首无

2、线局域网等传统无线网络的首 要目标是提供高服务质量和公平高效地利要目标是提供高服务质量和公平高效地利 用网络带宽，用网络带宽， 这些网络路由协议的主要任这些网络路由协议的主要任 务是寻找源节点到目的节点间通信延迟小务是寻找源节点到目的节点间通信延迟小 的路径，同时提高整个网络的利用率，的路径，同时提高整个网络的利用率， 避避 免产生通信拥塞并均衡网络流量等，免产生通信拥塞并均衡网络流量等， 而能而能 量消耗问题不是这类网络考虑的重点。量消耗问题不是这类网络考虑的重点。 无线传感器网络 无线传感器网络路由协议特点 传感器网络具有很强的应用相关性，不同传感器网络具有很强的应用相关性，不同 应用中的

3、路由协议可能差别很大，没有一应用中的路由协议可能差别很大，没有一 个通用的路由协议。此外，传感器网络的个通用的路由协议。此外，传感器网络的 路由机制还经常与数据融合技术联系在一路由机制还经常与数据融合技术联系在一 起，通过减少通信量而节省能量。因此，起，通过减少通信量而节省能量。因此， 传统无线网络的路由协议不适应于无线传传统无线网络的路由协议不适应于无线传 感器网络。感器网络。 在无线传感器网络中，节点能量有限且一在无线传感器网络中，节点能量有限且一 般没有能量补充，般没有能量补充， 因此路由协议需要高效因此路由协议需要高效 利用能量，同时传感器网络节点数目往往利用能量，同时传感器网络节点数

4、目往往 很大，节点只能获取局部拓扑结构信息，很大，节点只能获取局部拓扑结构信息， 路由协议要能在局部网络信息的基础上选路由协议要能在局部网络信息的基础上选 择合适的路径。择合适的路径。 无线传感器网络 无线传感器网络的路由协议特点 （1） 能量优先。能量优先。 传统路由协议在选择传统路由协议在选择 最优路径时，最优路径时， 很少考虑节点的能量消耗很少考虑节点的能量消耗 问题。问题。 而无线传感器网络中节点的能量而无线传感器网络中节点的能量 有限，有限， 延长整个网络的生存期成为传感延长整个网络的生存期成为传感 器网络路由协议设计的重要目器网络路由协议设计的重要目 标，标， 因因 此需要考虑节点

5、的能量消耗以及网络能此需要考虑节点的能量消耗以及网络能 量均衡使用的问题。量均衡使用的问题。 无线传感器网络 （2） 基于局部拓扑信息。基于局部拓扑信息。 无线传感器无线传感器 网络为了节省通信能量，网络为了节省通信能量， 通常采用多跳通常采用多跳 的通信模式，的通信模式， 而节点有限的存储资源和而节点有限的存储资源和 计算资源，计算资源， 使得节点不能存储大量的使得节点不能存储大量的 由信息，由信息， 不能进行太复杂的路由计算。不能进行太复杂的路由计算。 在节点只能获取局部拓扑信息和资源有在节点只能获取局部拓扑信息和资源有 限的情下，限的情下， 如何实现简单高效的路由机如何实现简单高效的路由

6、机 制是无线传感器网络的一个基本问题。制是无线传感器网络的一个基本问题。 无线传感器网络 （3） 以数据为中心。以数据为中心。 传统的路由协议通常传统的路由协议通常 以地址作为节点的标识和路由的依据，无线传以地址作为节点的标识和路由的依据，无线传 感器网络中大量节点随机部署，感器网络中大量节点随机部署， 所关注的是所关注的是 监测区域的感知数据，监测区域的感知数据， 而不是具体哪节点获而不是具体哪节点获 取的信息，取的信息， 不依赖于全网惟一的标识。不依赖于全网惟一的标识。 传感传感 器网络通常包含多个传感器节点到数汇聚节点器网络通常包含多个传感器节点到数汇聚节点 的数据流，的数据流， 按照对

7、感知数据的需求、数据通按照对感知数据的需求、数据通 信模式和流向等，信模式和流向等， 以数据为中心成消息的转以数据为中心成消息的转 发路径。发路径。 无线传感器网络 （4） 应用相关。传感器网络的应用环境应用相关。传感器网络的应用环境 千差万别，千差万别， 数据通信模式不同，数据通信模式不同， 没有一个没有一个 路由机制适合所有的应用，路由机制适合所有的应用， 这是传感器网这是传感器网 络应用相关性的一个体现。络应用相关性的一个体现。 设计者需要针设计者需要针 对每一个具体应用的需求，对每一个具体应用的需求， 设计与之适应设计与之适应 的特定路由机制。的特定路由机制。 无线传感器网络 传感器网

8、络路由机制要求： （1） 能量高效。能量高效。 （2） 可扩展性。可扩展性。 （3） 鲁棒性。鲁棒性。 （4） 快速收敛性。快速收敛性。 无线传感器网络 路由协议分类 （1） 能量感知路由协议。能量感知路由协议。 高效利用网络能高效利用网络能 量是传感器网络路由协议的一个显著特征，早量是传感器网络路由协议的一个显著特征，早 期提出的一些传感器网络路由协议往往仅考虑期提出的一些传感器网络路由协议往往仅考虑 了能量因素。了能量因素。 为了强调高效利用能量的重要为了强调高效利用能量的重要 性，性， 在此将它们划分为能量感知路由协议。在此将它们划分为能量感知路由协议。 能量感知路由协议从数据传输中的能

9、量消耗出能量感知路由协议从数据传输中的能量消耗出 发，发， 讨论最优能量消耗路径以及最长网络生讨论最优能量消耗路径以及最长网络生 存期等问题。存期等问题。 无线传感器网络 （2） 基于查询的路由协议。基于查询的路由协议。 在诸如环境检测、在诸如环境检测、 战场评估等应用中，战场评估等应用中， 需要不断查询传感器节点采集需要不断查询传感器节点采集 的数据，的数据， 汇聚节点（查询节点）汇聚节点（查询节点） 发出任务查询命，发出任务查询命， 传感器节点向查询节点报告采集的数据。传感器节点向查询节点报告采集的数据。 在这类应在这类应 用中，通信流量主要是查询节点和传感器节点之间用中，通信流量主要是查

10、询节点和传感器节点之间 的命令和数据传输，的命令和数据传输， 同时传感器节点的采样信息在同时传感器节点的采样信息在 传输路径上通常要进行数据融合，传输路径上通常要进行数据融合， 通过减少通信流通过减少通信流 量来节省能量。量来节省能量。 无线传感器网络 （3） 地理位置路由协议。地理位置路由协议。 在诸如目标跟踪在诸如目标跟踪 类应用中，类应用中， 往往需要唤醒距离跟踪目标最近往往需要唤醒距离跟踪目标最近 的传感器节点，的传感器节点， 以得到关于目标的更精确位以得到关于目标的更精确位 置等相关信息。置等相关信息。 在这类应用在这类应用 中，中， 通常需要通常需要 知道目的节点的精确或者大致地理

11、位置。知道目的节点的精确或者大致地理位置。 把把 节点的位置信息作为路由选择的依据，节点的位置信息作为路由选择的依据， 不仅不仅 能够完成节点路由功能，还可以降低系统专能够完成节点路由功能，还可以降低系统专 门维护路由协议的能耗。门维护路由协议的能耗。 无线传感器网络 （4） 可靠的路由协议。无线传感器网络的可靠的路由协议。无线传感器网络的 某些应用对通信的服务质量有较高要求，某些应用对通信的服务质量有较高要求， 如如 可靠性和实时性等。可靠性和实时性等。 而在无线传感器网络中，而在无线传感器网络中， 链路的稳定性难以保证，链路的稳定性难以保证， 通信信道质量比较通信信道质量比较 低，低， 拓

12、扑变化比较频繁，拓扑变化比较频繁， 要实现服务质量保要实现服务质量保 证，证， 需要设计相应的可靠的路由协议。需要设计相应的可靠的路由协议。 无线传感器网络 能量感知路由 能量路由是最早提出的传感器网能量路由是最早提出的传感器网 路路由机制之一，路路由机制之一， 它根据节点的它根据节点的 可用能量（可用能量（power available， PA） 或传输路径上的能量需求，或传输路径上的能量需求， 选择数据的转发路径。选择数据的转发路径。 节点可用节点可用 能量就是节点当前的剩余能量。能量就是节点当前的剩余能量。 图图 2-1 所示的网络中，所示的网络中， 大写字大写字 母表示节点，母表示节点

13、， 如节点如节点 A， 节点节点 右侧括号内的数字表示节点的可右侧括号内的数字表示节点的可 用能量。用能量。 图中的双向线表示节点图中的双向线表示节点 之间的通信链路，之间的通信链路， 链路上的数字链路上的数字 表示在该链路上发送数据消耗的表示在该链路上发送数据消耗的 能量。能量。 源节点是一般功能的传感源节点是一般功能的传感 器节点，器节点， 完成数据采集工作。完成数据采集工作。 汇聚节点是数据发送的目标节点。汇聚节点是数据发送的目标节点。 无线传感器网络 能量路由策略主要有以下几种：能量路由策略主要有以下几种： （1） 最大最大 PA 路由：路由： 从数据源到汇聚节点的所从数据源到汇聚节点

14、的所 有路径中选取节点有路径中选取节点 PA 之和最大的路径。之和最大的路径。 （2） 最小能量消耗路由：最小能量消耗路由： 从数据源到汇聚节点从数据源到汇聚节点 的所有路径中选取节点耗能之和最少的路径。的所有路径中选取节点耗能之和最少的路径。 （3） 最少跳数路由：最少跳数路由： 选取从数据源到汇聚节点选取从数据源到汇聚节点 跳数最少的路径。跳数最少的路径。 （4） 最大最小最大最小 PA 节点路由：每条路径上有多节点路由：每条路径上有多 个节点，且节点的可用能量不同，个节点，且节点的可用能量不同， 从中选取每条从中选取每条 路径中可用能量最小的节点来表示这条路径的可用路径中可用能量最小的节

15、点来表示这条路径的可用 能量。能量。 无线传感器网络 能量多路径路由 传统网络的路由机制往往选择源节点到目的节点之传统网络的路由机制往往选择源节点到目的节点之 间跳数最小的路径传输数据，间跳数最小的路径传输数据， 但在无线传感器网络但在无线传感器网络 中，中， 如果频繁使用同一条路径传输数据，如果频繁使用同一条路径传输数据， 就会造就会造 成该路径上的节点因能量消耗过快而过早失效，成该路径上的节点因能量消耗过快而过早失效， 从从 而使整个网络分割成互不相连的孤立部分，而使整个网络分割成互不相连的孤立部分， 减少了减少了 整个网络的生存期。整个网络的生存期。 为此，为此，RahulC. Shah

16、 等人提等人提 出了一种能量多路径路由机制。出了一种能量多路径路由机制。 该机制在源节点和目的节点之间建立多条路径，该机制在源节点和目的节点之间建立多条路径， 根根 据路径上节点的通信能量消耗以及节点的剩余能量据路径上节点的通信能量消耗以及节点的剩余能量 情况，情况， 给每条路径赋予一定的选择概率，给每条路径赋予一定的选择概率， 使得数使得数 据传输均衡消耗整个网络的能量，据传输均衡消耗整个网络的能量， 延长整个网络的延长整个网络的 生存期。生存期。 无线传感器网络 能量多路径路由协议包括路径建立、数据传播和路能量多路径路由协议包括路径建立、数据传播和路 由维护三个过程。由维护三个过程。 路径

17、建立过程是该协议的重点内容。路径建立过程是该协议的重点内容。 每个节点需每个节点需 要知道到达目的节点的所有下一跳节点，要知道到达目的节点的所有下一跳节点， 并计算选并计算选 择每个下一跳节点传输数据的概率。择每个下一跳节点传输数据的概率。 概率的选择是概率的选择是 根据节点到目的节点的通信代价来计算的，根据节点到目的节点的通信代价来计算的， 在下面在下面 的描述中用的描述中用 Cost（Ni） 表示节点表示节点 i 到目的节点的到目的节点的 通信代价。通信代价。 因为每个节点到达目的节点的路径很多，因为每个节点到达目的节点的路径很多， 所以这个代价值是各个路径的加权平均值。所以这个代价值是各

18、个路径的加权平均值。 能量多能量多 路径路由的主要过程描述如下：路径路由的主要过程描述如下： 无线传感器网络 （1） 目的节点向邻居节点广播路径建立消息，目的节点向邻居节点广播路径建立消息， 启启 动路径建立过程。动路径建立过程。 路径建立消息中包含一个代价域，路径建立消息中包含一个代价域， 表示发出该消息的节点到目的节点路径上的能量信表示发出该消息的节点到目的节点路径上的能量信 息，息， 初始值设置为零。初始值设置为零。 （2） 当节点收到邻居节点发送的路径建立消息时，当节点收到邻居节点发送的路径建立消息时， 相对发送该消息的邻居节点，相对发送该消息的邻居节点， 只有当自己距源节点只有当自己

19、距源节点 更近，更近， 而且距目的节点更远的情况下，而且距目的节点更远的情况下， 才需要转发才需要转发 该消息，该消息， 否则将丢弃该消息。否则将丢弃该消息。 无线传感器网络 （3） 如果节点决定转发路径建立消息，如果节点决定转发路径建立消息， 需需 要计算新的代价值来替换原来的代价值。当路要计算新的代价值来替换原来的代价值。当路 径建立消息从节点径建立消息从节点 Ni 发送到节点发送到节点 Nj时，时， 该该 路径的通信代价值为节点路径的通信代价值为节点 i 的代价值加上两个的代价值加上两个 节点间的通信能量消耗，节点间的通信能量消耗， 即：即： ),()( ,ijiNjNi NNMetri

20、cNCostC 无线传感器网络 无线传感器网络 其中a为大于1的系统参数。 无线传感器网络 （5）节点为路由表中每个下一跳节点什算）节点为路由表中每个下一跳节点什算 选择概率，节点选择概率与能量消耗成反比。选择概率，节点选择概率与能量消耗成反比。 节点节点Ni使用如下公式计算选择节点使用如下公式计算选择节点Ni的概率：的概率： 无线传感器网络 无线传感器网络 RahulC Shah提出的能量多路径路由综合提出的能量多路径路由综合 考虑了通信路径上的消耗能量和剩余能量考虑了通信路径上的消耗能量和剩余能量 ，节点根据概率在路由表中选择一个节点，节点根据概率在路由表中选择一个节点 作为路由的下一跳节

21、点。由于这个概率是作为路由的下一跳节点。由于这个概率是 与能量相关的，可以将通信能耗分散到多与能量相关的，可以将通信能耗分散到多 条路径上，从百可实现整个网络的能量干条路径上，从百可实现整个网络的能量干 稳降级，最大限度地延长网络的生存期稳降级，最大限度地延长网络的生存期。 无线传感器网络 基于查询的路由基于查询的路由 无线传感器网络 定向扩散（定向扩散（directed diffusion，DD） 是一种基于是一种基于 查询的路由机制。查询的路由机制。 汇聚节点通过兴趣消息（汇聚节点通过兴趣消息（interest） 发出查询任务，采用洪泛方式传播兴趣消息到整个区发出查询任务，采用洪泛方式传播

22、兴趣消息到整个区 域或部分区域内的所有传感器节点。域或部分区域内的所有传感器节点。 兴趣消息用来表兴趣消息用来表 示查询的任务，表达网络用户对监测区域内感兴趣的示查询的任务，表达网络用户对监测区域内感兴趣的 信信 息，息， 例如监测区域内的温度、湿度和光照等环境信息。例如监测区域内的温度、湿度和光照等环境信息。 在兴趣消息的传播过程中，在兴趣消息的传播过程中， 协议逐跳地在每个传感器协议逐跳地在每个传感器 节点上建立反向的从数据源到汇聚节点的数据传输梯节点上建立反向的从数据源到汇聚节点的数据传输梯 度（度（gradient）。传感器节点将采集到的数据沿着梯）。传感器节点将采集到的数据沿着梯 度

23、方向传送到汇聚节点。度方向传送到汇聚节点。 无线传感器网络 定向扩散路由机制可以分为周期性的兴趣扩散、定向扩散路由机制可以分为周期性的兴趣扩散、 梯度建立以及路径加强三个阶段。图梯度建立以及路径加强三个阶段。图 2-2 显显 示了这三个阶段的数据传播路径和方向。示了这三个阶段的数据传播路径和方向。 无线传感器网络 DD协议内容：协议内容： 节点用一组节点用一组来命名它所生成的数据。来命名它所生成的数据。 1.建立路由时，建立路由时，sink(汇聚节点）汇聚节点）flooding(广播）包含属性列表、上报间隔、持续时间、广播）包含属性列表、上报间隔、持续时间、 地理区域等地理区域等 信息的查询请

24、求信息的查询请求Interest （该过程本质上是设置一个监测任务，（该过程本质上是设置一个监测任务， 通过分配不同属性通过分配不同属性 值来表示不同任务的描述符）。值来表示不同任务的描述符）。 2.每个传感器节点在收到嗜好（每个传感器节点在收到嗜好（Interest）后保存在各自的）后保存在各自的Cache中。每个嗜好项中。每个嗜好项 (interest entry)包含一个时间标签域包含一个时间标签域(timestamp field)和若干个梯度域和若干个梯度域(gradient field， 按成本最小化和能量自适应原则引导数据扩散的方向按成本最小化和能量自适应原则引导数据扩散的方向)。

25、 3.当一个嗜好传遍整个网络后，从源节点当一个嗜好传遍整个网络后，从源节点(即嗜好所在区域的传感器节点即嗜好所在区域的传感器节点)到到sink节点节点 或基站之间的梯度就建立起来了。或基站之间的梯度就建立起来了。 4.一旦源节点采集到嗜好所需的数据，那么源节点沿着该嗜好的梯度路径传输数据到一旦源节点采集到嗜好所需的数据，那么源节点沿着该嗜好的梯度路径传输数据到 sink节点或基站。其中，源节点采集的数据首先在本地采用数据融合技术进行整合，节点或基站。其中，源节点采集的数据首先在本地采用数据融合技术进行整合， 然后在网上传输。然后在网上传输。 右图描述右图描述DD路由路由 协议的工作原理协议的工

26、作原理 无线传感器网络 在在Directed Diffusion中，可以对路径进行修复。在建立多条数据源到中，可以对路径进行修复。在建立多条数据源到Sink节点的路节点的路 径之后，径之后，(探测梯度探测梯度)Sink节点可以选择增强其中的一条路径用于数据的传输，而同时保持另外节点可以选择增强其中的一条路径用于数据的传输，而同时保持另外 一条低速数据传输的路径一条低速数据传输的路径（数据梯度）（数据梯度）。当高速路径，也就是经过增强的路径出现故障时，。当高速路径，也就是经过增强的路径出现故障时，Sink 节点可以增强低速路径，保证源节点到节点可以增强低速路径，保证源节点到Sink节点的数据传输

27、。虽然保持低速路径的节点的数据传输。虽然保持低速路径的 过程需要消耗一些能量，但是在故障时，可以节省很多能量开销。对于故障比较频过程需要消耗一些能量，但是在故障时，可以节省很多能量开销。对于故障比较频 繁的网络，保持一条低速路径是很有好处的。繁的网络，保持一条低速路径是很有好处的。 DD路由协议的优点：路由协议的优点： 1.采用多路径采用多路径,健壮性好健壮性好; 2.节点只需要和邻居节点通信，因而不需要全局的地址机制，使用查询驱动机制按节点只需要和邻居节点通信，因而不需要全局的地址机制，使用查询驱动机制按 需建立路由需建立路由,避免了保存全网信息；避免了保存全网信息； 3.每个节点都可以进行

28、数据融合操作，能减少数据通信量，节省能量消耗；每个节点都可以进行数据融合操作，能减少数据通信量，节省能量消耗； 4.sink点根据实际情况采取增强或减弱方式能有效利用能量；点根据实际情况采取增强或减弱方式能有效利用能量； 5.节点不需要维护网络的拓扑结构，数据的发送是基于需求的，因此它是一个非常节点不需要维护网络的拓扑结构，数据的发送是基于需求的，因此它是一个非常 节能的路由协议。节能的路由协议。 DD路由协议的缺点：路由协议的缺点： 1.基于查询驱动模型的，不适用于环境监测的基于查询驱动模型的，不适用于环境监测的WSN； 2.Gradient的建立开销很大的建立开销很大,不适合多不适合多si

29、nk点网络；点网络； 3.数据聚合过程采用时间同步技术数据聚合过程采用时间同步技术,会带来较大开销和时延；会带来较大开销和时延； 4.不同的应用中需要定义不同的命名方案，也就是不同的应用中需要定义不同的命名方案，也就是对，从而限制了它对，从而限制了它 的应用。的应用。 无线传感器网络 Rumor 路由协议（谣传路由）：路由协议（谣传路由）： Rumor Routing是在是在Directed Diffusion的基础上演化而来的。通常情况下，的基础上演化而来的。通常情况下， Directed Diffusion协议需要向整个网络广播兴趣，而在某些应用中，只有少量的协议需要向整个网络广播兴趣，而

30、在某些应用中，只有少量的 数据需要从源节点传递到数据需要从源节点传递到Sink节点。在这种情况下，没有必要向整个网络广播兴节点。在这种情况下，没有必要向整个网络广播兴 趣。当趣。当WSN中的事件（对应着数据的传递）数量很少，而查询（对应着兴趣的广中的事件（对应着数据的传递）数量很少，而查询（对应着兴趣的广 播）数量很多的时候，可以采用广播事件的方法，以节省能量的消耗。播）数量很多的时候，可以采用广播事件的方法，以节省能量的消耗。Rumor Routing是一个介于事件广播（向整个网络广播事件）和兴趣广播（向整个网络广是一个介于事件广播（向整个网络广播事件）和兴趣广播（向整个网络广 播兴趣）之间

31、的一种路由协议播兴趣）之间的一种路由协议 Rumor Routing核心思想：核心思想： 1.借鉴了欧氏平面图上任意两条曲线交叉几率很大的思想借鉴了欧氏平面图上任意两条曲线交叉几率很大的思想 2.当节点监测到事件后将其保存，并创建称为当节点监测到事件后将其保存，并创建称为Agent的生命周期较长的包括事件和的生命周期较长的包括事件和 源节点信息的数据包，将其按一条或多条随机路径在网络中转发源节点信息的数据包，将其按一条或多条随机路径在网络中转发 3.收到收到Agent的节点根据事件和源节点信息建立反向路径，并将的节点根据事件和源节点信息建立反向路径，并将Agent再次随机发再次随机发 送到相邻

32、节点，并可在再次发送前在送到相邻节点，并可在再次发送前在Agent中增加其已知的事件信息中增加其已知的事件信息 4.sink点的查询请求也沿着一条随机路径转发点的查询请求也沿着一条随机路径转发,当两路径交叉时则路由建立当两路径交叉时则路由建立 5.如不交叉如不交叉,sink点可点可flooding查询请求查询请求 无线传感器网络 Rumor协议中Agent传播和Agent路径与查询路径的交叉 在多在多sink点、查询请求数目很大、网络事件很少的情况下，点、查询请求数目很大、网络事件很少的情况下，Rumor协议较为有效协议较为有效. 但如果事件非常多但如果事件非常多,维护事件表和收发维护事件表和

33、收发Agent带来的开销会很大带来的开销会很大。 无线传感器网络 地理位置路由 无线传感器网络 在传感器网络中，节点通常需要获取它的在传感器网络中，节点通常需要获取它的 位置信息，这样它采集的数据才有意义。位置信息，这样它采集的数据才有意义。 如在森林防火的应用中，消防人员不仅要如在森林防火的应用中，消防人员不仅要 知道森林中发生火灾事件，而且还要知道知道森林中发生火灾事件，而且还要知道 火灾的具体位置。地理位置路由假设节点火灾的具体位置。地理位置路由假设节点 知道自己的地理位置信息，以及目的节点知道自己的地理位置信息，以及目的节点 或者目的区域的地理位置，利用这些地理或者目的区域的地理位置，

34、利用这些地理 位置信息作为路由选择的依据，节点按照位置信息作为路由选择的依据，节点按照 一定策略转发数据到目的节点。地理位置一定策略转发数据到目的节点。地理位置 的精确度和代价相关，在不同的应用中会的精确度和代价相关，在不同的应用中会 选择不同精确度的位置信息来实现数据的选择不同精确度的位置信息来实现数据的 路由转发。路由转发。 无线传感器网络 GEAR ： GEAR路由协议路由协议 Geographic and Energy Aware Routing 无线传感器网络 GEAR GEAR ： GEARGEAR路由协议路由协议 Geographic and Energy Aware Routi

35、ngGeographic and Energy Aware Routing 应用 建立到特定区域的路由建立到特定区域的路由 查询工作方式查询工作方式 前提 已知目标区域的位置信息已知目标区域的位置信息 节点知道自己位置信息和剩余能量节点知道自己位置信息和剩余能量 节点间无线链路是对称的节点间无线链路是对称的 无线传感器网络 GEAR路由过程 分两个阶段： 查询消息到达目的区域的路径 查询消息在目标区域的传播 选路依据 节点到查询区域通信能量能耗 节点本身的剩余能量 最小代价节点为转发节点 无线传感器网络 GEAR路由过程 无线传感器网络 GEAR路由过程 查询在监测区域内传送：洪泛方式，迭代

36、地理转发 将目标区域分解为若干子区域、向子区域 的中心位置转发 无线传感器网络 无线传感器网络 无线传感器网络 GEM 路由 GEM（graphembedding）路由是一种适 用于数据中心存储方式的地理路由。 无线传感器网络 传感器网络存储监测数据方式 本地存储（localstorage） 外部存储（externalstorage） 数据中心存储（data- centricstorage） 无线传感器网络 本地存储方式 在本地存储方式中，节点首先将监测数据保存在在本地存储方式中，节点首先将监测数据保存在 本地存储器中，并在收到查询命令后，将相关数本地存储器中，并在收到查询命令后，将相关数 据

37、发送给汇聚节点。据发送给汇聚节点。 本地存储方式中，网络传输的数据都是汇聚节点本地存储方式中，网络传输的数据都是汇聚节点 感兴趣的数据，网络传输效率高，但是需要每个感兴趣的数据，网络传输效率高，但是需要每个 节点都具有相对较大的存储空间，数据融合只能节点都具有相对较大的存储空间，数据融合只能 在传输过程中进行，并且汇聚节点需要经过较长在传输过程中进行，并且汇聚节点需要经过较长 的延迟后才能获得查询数据。的延迟后才能获得查询数据。 无线传感器网络 外部存储方式 在外部存储方式下，节点在获得监测数据后，不在外部存储方式下，节点在获得监测数据后，不 论汇聚节点目前是否对该数据感兴趣，都主动地论汇聚节

38、点目前是否对该数据感兴趣，都主动地 把数据发送给汇聚节点。把数据发送给汇聚节点。 外部存储方式中，节点将采集数据及时传输给汇外部存储方式中，节点将采集数据及时传输给汇 聚节点，可以提高传感器网络对突发事件的反应聚节点，可以提高传感器网络对突发事件的反应 速度，但是监测数据不断发送给汇聚节点，一方速度，但是监测数据不断发送给汇聚节点，一方 面由于有些数据不是汇聚节点感兴趣的，造成了面由于有些数据不是汇聚节点感兴趣的，造成了 网络能量的浪费；另一方面容易使得汇聚节点附网络能量的浪费；另一方面容易使得汇聚节点附 近形成网络热点，降低传感器网络的吞吐率。近形成网络热点，降低传感器网络的吞吐率。 无线传

39、感器网络 数据中心存储方式 在数据中心存储方式下，首先对可能的监测事件进行命名，在数据中心存储方式下，首先对可能的监测事件进行命名， 然后按照一定的策略将每一个事件映射到一个地理位置上，然后按照一定的策略将每一个事件映射到一个地理位置上， 距离这个位置最近的节点作为该事件的负责节点。节点在距离这个位置最近的节点作为该事件的负责节点。节点在 监测到事件后，把相关数据发送到映射位置。负责节点接监测到事件后，把相关数据发送到映射位置。负责节点接 收数据，进行数据融合并存储在本地。收数据，进行数据融合并存储在本地。 数据中心存储方式在网络中选择不同的负责节点实现不同数据中心存储方式在网络中选择不同的负

40、责节点实现不同 事件监测数据的融合和存储，是介于本地存储和外部存储事件监测数据的融合和存储，是介于本地存储和外部存储 的之间的一种方式，在查询延迟、能量消耗和存储空间等的之间的一种方式，在查询延迟、能量消耗和存储空间等 多项指标间进行折中。由于传感器网络处理的事件往往有多项指标间进行折中。由于传感器网络处理的事件往往有 多种，数据中心存储方式能够将网络通信流量、处理流量多种，数据中心存储方式能够将网络通信流量、处理流量 和存储流量在网络中均匀分摊，从而有效避免了网络热点和存储流量在网络中均匀分摊，从而有效避免了网络热点 的产生。的产生。 无线传感器网络 GEM 路由 GEM（graphembe

41、dding）路由是一种适用于）路由是一种适用于 数据中心存储方式的地理路由。数据中心存储方式的地理路由。 GEM路由的基本思想是建立一个虚拟极坐标系统路由的基本思想是建立一个虚拟极坐标系统 （virtualpolarcoordinatesystem，VPCS），）， 用来表示实际的网络拓扑结构。网络中的节点形用来表示实际的网络拓扑结构。网络中的节点形 成一个以汇聚节点为根的带环树（成一个以汇聚节点为根的带环树（ringedree），）， 每个节点用到树根的跳数距离和角度范围来表示，每个节点用到树根的跳数距离和角度范围来表示， 节点间的数据路由通过这个带环树实现。节点间的数据路由通过这个带环树实

42、现。 无线传感器网络 虚拟极坐标系统 第一步： 生成树型结构。 第二步： 反馈子树大小。 第三步： 确定虚拟角度范围。 无线传感器网络 对网络拓扑变化的适应 除了汇聚节点外每个节点只有一个父节点； 每个节点的跳数值为父节点的跳数值加 1； 每个节点的角度范围是父节点的角度范围的子 集； 每个节点的子节点角度范围不相交。 无线传感器网络 基于虚拟极坐标系统的路由算法 无线传感器网络 边界定位的地理路由 在传感器网络的实际应用中，在传感器网络的实际应用中， 如果每个节点都需要知道如果每个节点都需要知道 自己的精确位置信息，自己的精确位置信息， 那么路由代价比较大。那么路由代价比较大。 地理位置地理

43、位置 路由研究中的一个重要方向就是如何在保证路由正确性的路由研究中的一个重要方向就是如何在保证路由正确性的 前提下，前提下， 尽量减少需要精确位置信息的节点数目，尽量减少需要精确位置信息的节点数目， 以及以及 路由机制对节点精确位置信息的依赖。路由机制对节点精确位置信息的依赖。 文献文献13提出了一种只需要少数节点精确位置信息就提出了一种只需要少数节点精确位置信息就 可以进行正确路由的地理路由机制。可以进行正确路由的地理路由机制。 其基本思想是首先其基本思想是首先 通过网络中知道自身位置信息的节点确定一个全局坐标系，通过网络中知道自身位置信息的节点确定一个全局坐标系， 然后确定其他节点在这个坐

44、标系中的位置，然后确定其他节点在这个坐标系中的位置， 最后根据节最后根据节 点在坐标系中的位置进行数据路由。知道自身位置信息的点在坐标系中的位置进行数据路由。知道自身位置信息的 节点通常是网络中较为特殊的信标节点。节点通常是网络中较为特殊的信标节点。 当所有节点的坐标位置信息确定后，当所有节点的坐标位置信息确定后， 协议使用贪婪算法协议使用贪婪算法 选择路由。选择路由。 因此，因此， 协议的关键部分是利用信标节点确定协议的关键部分是利用信标节点确定 全局坐标系以及确定其他节点在坐标系中的位置。全局坐标系以及确定其他节点在坐标系中的位置。 文献文献 13给出了下面三种策略。给出了下面三种策略。

45、无线传感器网络 边界节点均为信标节点 无线传感器网络 使用两个信标节点 在边界节点均为信标节点策略中在边界节点均为信标节点策略中 , 仍然需要网络边界上仍然需要网络边界上 所有节点都知道自己的精确地理位置所有节点都知道自己的精确地理位置 , 网络部署的成本仍网络部署的成本仍 然很高。本策略只使用两个信标节点然很高。本策略只使用两个信标节点 , 而而 不再不再 需要需要 所所 有边有边 界节界节 点的精点的精 确位确位 置信息置信息 , 从而大大减少了网络部从而大大减少了网络部 署的成本。署的成本。 在该策略中在该策略中 , 仍然将节点分为边界节点和仍然将节点分为边界节点和 非边界非边界 节点。

46、节点。 边界节边界节 点只点只 知道自知道自 己处己处 于网络的边缘于网络的边缘 , 但不知道自己但不知道自己 的精确位置信息。该策略的精确位置信息。该策略 首先首先 通过通过 边界节边界节 点间点间 的信息的信息 交换交换 机制建立全局坐标系机制建立全局坐标系 , 然后引入两个然后引入两个 beacon 节点节点 以以 减少减少 全局全局 坐标系坐标系 的误的误 差差 , 最后按最后按 照前照前 述方法计算述方法计算 非边界节点在全局坐标系中的位置。非边界节点在全局坐标系中的位置。 无线传感器网络 使用一个信标节点 上述策略中假设节点知道自己是边界节点上述策略中假设节点知道自己是边界节点 ,

47、 实际网络中节点的部署具有随机性实际网络中节点的部署具有随机性 , 不能不能 确定自己是否为实际的网络边界节点。本确定自己是否为实际的网络边界节点。本 策略策略 利用利用 一个一个 信标节信标节 点确点确 定一组定一组 边界边界 节点节点 , 然后采用上面第二种策略介绍的算然后采用上面第二种策略介绍的算 法确定全局法确定全局 坐标系坐标系 并计并计 算节点算节点 在坐在坐 标标 系系 中的位中的位 置信置信 息。息。 无线传感器网络 特点 与与 G EAR 路由相比路由相比 , 边界定位的路边界定位的路 由机由机 制只制只 需需 要很要很 少节少节 点知道点知道 精确精确 的位的位 置置 信息

48、信息 , 减少减少 了对传感器节点的功能要求了对传感器节点的功能要求 , 降低了传感器降低了传感器 网络网络 的的 部署部署 成本。但成本。但 为了为了 确定全确定全 局坐局坐 标系和节点标系和节点 在坐标系中的位置信息在坐标系中的位置信息 , 节点需要进行节点需要进行 大量大量 的的 信息信息 交换交换 , 通通 信开信开 销很大。销很大。 此外此外 , 由于算法由于算法 采用了迭代采用了迭代 过过 程程 确定确定 节节 点点 的的 位位 置置 , 计计 算算 出出 的的 节点节点 位位 置置 精精 度度 和迭和迭 代代 次次 数数 相相 关。关。 与与G E M 路由相比路由相比 , 边界

49、定位路由建立的全局边界定位路由建立的全局 坐标系坐标系 更加接更加接 近节点近节点 实际实际 位置位置 , 且对且对 于网于网 络络 拓扑的变化调整比较简单。拓扑的变化调整比较简单。 无线传感器网络 可靠路由协议 某些传感器网络应用对于数据传输的可靠某些传感器网络应用对于数据传输的可靠 性提性提 出了出了 比比 较高较高 的要的要 求求 , 因此传因此传 感器感器 网络路由中的一个重要方面网络路由中的一个重要方面 是研究可靠路由协议。传感器节点由于有限能量供应和工是研究可靠路由协议。传感器节点由于有限能量供应和工 作环境恶劣经常面临失效问题作环境恶劣经常面临失效问题 , 这为研究适合于传感器网

50、这为研究适合于传感器网 络的可靠路由协议增加了困难。络的可靠路由协议增加了困难。 目前目前 , 研究人员提出的可靠路由协研究人员提出的可靠路由协 议主议主 要从要从 两个方两个方 面考面考 虑虑 : 一是利一是利 用节用节 点的点的 冗冗 余性提供多条路径以保证余性提供多条路径以保证 通信可靠通信可靠 性性 ; 二是建二是建 立对立对 传输传输 可靠性可靠性 的估的估 计机制计机制 , 从从 而保而保 证每证每 跳传输的可靠性。另外跳传输的可靠性。另外 , 某些传感器网络某些传感器网络 应用需要应用需要 节点间节点间 通信通信 具有具有 一定的一定的 实时实时 性。性。 无线传感器网络 基于不

51、相交路径的多路径路由机制 在传感器网络中在传感器网络中 , 引入多路径路由是为了提高引入多路径路由是为了提高 数据数据 传输传输 的可靠的可靠 性和性和 实现网实现网 络负络负 载平衡。在载平衡。在 多路径路由中多路径路由中 , 如何建立数据源节点到如何建立数据源节点到 汇聚节汇聚节 点的点的 多条多条 路径是路径是 首要首要 问题。在问题。在 定向扩散路由定向扩散路由 中中 , 当有数据查询需要时当有数据查询需要时 , 汇聚节点汇聚节点 首先通首先通 过过 洪洪 泛兴趣泛兴趣 消息消息 形成形成 传输梯传输梯 度度 , 然后建立数据然后建立数据 源节点到汇聚节点的多条路径源节点到汇聚节点的多

52、条路径 , 最后通过最后通过 路径路径 加强加强 消息选消息选 择一择一 条主路条主路 径传径传 输数据。当主路输数据。当主路 径失败时径失败时 , 定向扩散路由需要使用周期性低速率定向扩散路由需要使用周期性低速率 的洪泛过程重新建立主路径。的洪泛过程重新建立主路径。 无线传感器网络 局部不相交路径的构建 无线传感器网络 缠绕多路径 无线传感器网络 ReInForM 路由 在传感器网络在传感器网络 中中 , 传传 感感 器器 节节 点点 是是 数数 据据 源源 , 把把 监测监测 数数 据据 发发 送送 给给 汇汇 聚聚 节节 点。点。 ReInForM( Reliable Informati

53、on Forwarding using Multiple paths) 路由从数路由从数 据源节点据源节点 开始开始 , 考虑可靠性需求、考虑可靠性需求、 信道质量信道质量 以及传感器节点到汇聚节点以及传感器节点到汇聚节点 的跳的跳 数数 , 决定需决定需 要的要的 传输传输 路径数路径数 目目 , 以及下一跳节点数目和以及下一跳节点数目和 相应的节点相应的节点 , 实现满足可靠要求的数据传输。实现满足可靠要求的数据传输。 无线传感器网络 SPEED 协议 在有些传感器网络应用中在有些传感器网络应用中 , 汇聚节点需要根据采集数据实汇聚节点需要根据采集数据实 时作出反应时作出反应 , 因此传感

54、器节点到汇聚节点的因此传感器节点到汇聚节点的 数据数据 通通 道要道要 保保 持持 一一 定的定的 传传 输输 速速 率。率。SP EE D 协议协议 33 是是 一一 个个 实实 时路时路 由由 协议协议 , 在一定程度上实现了端到端的传在一定程度上实现了端到端的传 输速率保证、网络拥塞控制以及负载平衡机制。为实现上输速率保证、网络拥塞控制以及负载平衡机制。为实现上 述目标述目标 , SP E ED 协议首先交换节协议首先交换节 点的点的 传输传输 延迟延迟 , 以以 得到得到 网网 络负络负 载情载情 况况 ; 然后节点利用局部地理信息和传然后节点利用局部地理信息和传 输速率信息作出路由决

55、输速率信息作出路由决 定定 , 同时通过邻居反馈机制保证网同时通过邻居反馈机制保证网 络传输速率在一个全局定义的传输速率阈值之上。节点还络传输速率在一个全局定义的传输速率阈值之上。节点还 通过反向压力路由变更机制避开延迟太大的链路和路由空通过反向压力路由变更机制避开延迟太大的链路和路由空 洞。洞。 无线传感器网络 SPEED 协议框架 (1) 延迟估计机制延迟估计机制 , 用来得到网络的负载情况用来得到网络的负载情况 , 判断网络是判断网络是 否发生拥塞否发生拥塞 ; ( 2) SNGF 算法算法 ( stateless non-deterministic geogr aphic forwa

56、rding , SN GF ) , 用来选择满足传输速率要用来选择满足传输速率要 求的下一跳节点求的下一跳节点 ; ( 3 ) 邻居反馈策略邻居反馈策略 ( neigh borhood feedback loop , NF L) , 是当是当 SNG F 路由算法中找不到满足传输速率要求的下路由算法中找不到满足传输速率要求的下 一跳节点时采取的补偿机制一跳节点时采取的补偿机制 ; ( 4) 反向压力路由变更机制反向压力路由变更机制 , 用来避免拥塞和路由空洞。用来避免拥塞和路由空洞。 无线传感器网络 . 延迟估计 在在 SPE ED 协议中协议中 , 节点记节点记 录录 到到 邻邻 居居 节点

57、节点 的的 通通 信信 延延 迟迟 , 用用 来来 表示表示 网网 络络 局局 部部 的通的通 信信 负载。这里的通信延迟主要是指发送延迟负载。这里的通信延迟主要是指发送延迟 , 而而 忽略传输延迟。在带宽有限的网络条件下忽略传输延迟。在带宽有限的网络条件下 , 如果用专门分组探测节点间的如果用专门分组探测节点间的 通信延迟通信延迟 , 开销比较大。开销比较大。SP E ED 协议采用数据包捎带协议采用数据包捎带 的方法的方法,得到节得到节 点之间的通信延迟点之间的通信延迟 , 具体过程如下具体过程如下 : 发发 送节点送节点 给数给数 据分组据分组 加上加上 时时 间间 戳戳 ; 接接 收收

58、 节节 点点 计计 算从算从 收收 到到 数数 据据 分分 组组 到到 发出发出 ACK 的时的时 间间间间 隔隔 , 并并 将将 其作其作 为一个为一个 字段字段 加入加入 ACK 报文报文 ; 发发 送节送节 点收到点收到 ACK 后后 , 从收发从收发 时间时间 差中差中 减去接减去接 收节收节 点的处点的处 理理 时时 间间 , 得得 到到 一一 跳跳 的的 通通 信信 延延 迟迟 。 在在 更更 新新 记记 录录 的的 延延 迟迟 值值 时时 , 综综 合合 考虑新计算的考虑新计算的 延迟值和原来记录延迟值和原来记录 的延迟值的延迟值, 更更 新的延迟值是二者的指数加新的延迟值是二者

59、的指数加 权平均权平均( exponen tial weighted moving average, EWMA )。 节点节点 将计将计 算出的通信算出的通信 延迟通延迟通 告邻告邻 居居 节节 点。假点。假 设节设节 点点 A 计算计算 出出 到到 节节 点点 B 的的 通通 信信 延延 迟迟 , 并并 将将 这这 个个 通通 信信 延延 迟迟 通通 告告 其其 邻邻 居居 节节 点点C, 则则 C 可可 以不以不 必计算必计算 到节到节 点点 B 的通信的通信 延迟延迟 , 而使用而使用 A 发送发送 来的来的 通信延通信延 迟直迟直 接与接与 节点节点 B通通 信。信。 无线传感器网络

60、SNGF 算法 节点将邻居节点分为两类节点将邻居节点分为两类 : 比自己距离目比自己距离目 标区域更近的节点和比自己标区域更近的节点和比自己 距离目距离目 标区域标区域 更远的节点。前者称为候选转发节点集合更远的节点。前者称为候选转发节点集合 ( for warding candidate set , F CS ) 。 节点节点 计算到其计算到其 F CS 集合中的每个节点的集合中的每个节点的 传输传输 速率。速率。 传输速传输速 率定率定 义为节义为节 点间点间 的的 距距 离除以离除以 节点节点 间间 通信延迟。通信延迟。 无线传感器网络 SNGF 算法 如果节点的如果节点的 F CS 集