无线传感网络第七章

1、第第7 7章章 无线传感器网络的路由协议无线传感器网络的路由协议 7.1 7.1 路由协议概述路由协议概述7.1.17.1.1无线传感器网络路由协议的考虑因素无线传感器网络路由协议的考虑因素 设计无线传感器网络的路由要考虑的因素很多，大致分为以下两设计无线传感器网络的路由要考虑的因素很多，大致分为以下两种类型。种类型。 (1)(1)网络特征：无线传感器网络具有与众不同的特征，应用网络特征：无线传感器网络具有与众不同的特征，应用于路由协议设计时，主要应该考虑能量损耗、节点部署和网络拓于路由协议设计时，主要应该考虑能量损耗、节点部署和网络拓扑变化。扑变化。(2)(2)数据传输特征：无线传感器网络的

2、数据采集和传输要求数据传输特征：无线传感器网络的数据采集和传输要求与其他网络不同，因此路由协议设计时也需要加以区别，主要考与其他网络不同，因此路由协议设计时也需要加以区别，主要考虑数据传输方式、无线传输手段以及数据融合技术等。虑数据传输方式、无线传输手段以及数据融合技术等。7.1.27.1.2路由的过程路由的过程无线传感器网络的路由过程主要分为以下无线传感器网络的路由过程主要分为以下4 4个步骤：个步骤： 某一个设备发出路由请求命令帧，启动路由发现过程；某一个设备发出路由请求命令帧，启动路由发现过程； 对应的接收设备收到该命令后，回复应答命令帧；对应的接收设备收到该命令后，回复应答命令帧； 对

3、潜在的各条路径开销对潜在的各条路径开销( (跳转次数、延迟时间跳转次数、延迟时间) )，进行评估比，进行评估比较；较； 将评估确定之后的最佳路由记录添加到此路径上各个设备的将评估确定之后的最佳路由记录添加到此路径上各个设备的路由表中。路由表中。7.1.37.1.3无线传感器网络路由协议分类方法无线传感器网络路由协议分类方法1 1按源节点获取路径的方法按源节点获取路径的方法主动路由协议、按需路由协议主动路由协议、按需路由协议 、混合路由协议、混合路由协议2 2按节点参与通信的方式按节点参与通信的方式直接通信路由协议、平面路由协议、层次路由协议直接通信路由协议、平面路由协议、层次路由协议3 3按路

4、由的发现过程按路由的发现过程 以位置信息为中心的路由协议、以数据为中心的路由协议以位置信息为中心的路由协议、以数据为中心的路由协议4 4按路由选择是否考虑服务质量按路由选择是否考虑服务质量(QoS)(QoS)约束约束 保证保证QoSQoS的路由协议是指在路由建立时，考虑时延、丢包率等的路由协议是指在路由建立时，考虑时延、丢包率等QoSQoS参参数，从多条可行的路由中选择一条最适合数，从多条可行的路由中选择一条最适合QoSQoS应用要求的路由；或者根据应用要求的路由；或者根据业务类型，保证满足不同业务需求的业务类型，保证满足不同业务需求的QoSQoS路由协议。路由协议。 7.2 7.2 平面路由

5、协议平面路由协议7.2.1 Flooding and Grossing7.2.1 Flooding and Grossing协议协议1. 1. 洪泛路由协议洪泛路由协议洪泛路由协议洪泛路由协议(Flooding Protocol)(Flooding Protocol)是一种最早的路由协议，接收到消是一种最早的路由协议，接收到消息的节点以广播的彤式转发报文给所有的邻居节点，息的节点以广播的彤式转发报文给所有的邻居节点， ( (如图如图7-1,27-1,2所示所示) )。 2. 2. 闲聊法闲聊法闲聊法闲聊法(Grossing)(Grossing)是洪泛法的改进是洪泛法的改进版本。版本。如图如图7

6、-37-3所示所示7.2.2 SPIN7.2.2 SPIN协议协议基于协商机制的传感器网络基于协商机制的传感器网络SPINSPIN协议协议(Sensor Protocols for (Sensor Protocols for Information via Negotiation)Information via Negotiation)是一种以数据为中心的白适应通信方式，是一种以数据为中心的白适应通信方式，使用使用3 3种类型的信息进行通信，即种类型的信息进行通信，即ADVADV、REQREQ和和DATADATA信息。图信息。图7-47-4表示了表示了SPINSPIN协议的工作过程。协议的工作

7、过程。 SPIN SPIN协议的缺点是没有考虑节能和多种信道条件下的数据传输问题。协议的缺点是没有考虑节能和多种信道条件下的数据传输问题。因此，后续又出现了因此，后续又出现了SPIN-PP (Point to PointSPIN-PP (Point to Point，点到点的通信模式，点到点的通信模式) )、SPIN-EC (Energy ControlSPIN-EC (Energy Control，点到点模式下的节能路由，点到点模式下的节能路由) )、SPIN-RL (Route SPIN-RL (Route LossyLossy，点到点通信中的信道衰减模式，点到点通信中的信道衰减模式) )

8、、SPIN-BC (Broadcast ChannelSPIN-BC (Broadcast Channel，广播信道模式广播信道模式) )等在等在SPINSPIN基础上改进的路由协议。基础上改进的路由协议。7.2.3 SAR7.2.3 SAR、DDDD和和MCFAMCFA协议协议1 1SARSAR协议协议顺序分配路由顺序分配路由SARSAR协议协议(Sequential Assignment Routing)(Sequential Assignment Routing)是第一个具是第一个具有有QoSQoS意识的路由协议。该协议通过构建以意识的路由协议。该协议通过构建以SinkSink的单跳邻居

9、节点为根节点的的单跳邻居节点为根节点的多播树来实现传感器节点到多播树来实现传感器节点到SinkSink节点的多跳路径。节点的多跳路径。2 2DDDD协议协议定向扩散路由定向扩散路由DDDD协议协议(Directed Diffusion)(Directed Diffusion)是一种以数据为中心的信是一种以数据为中心的信息传播协议，与已有的路由算法有着截然不同的实现机制。息传播协议，与已有的路由算法有着截然不同的实现机制。3 3MCFAMCFA协议协议 最小开销前行算法最小开销前行算法MCFAMCFA协议协议(Minimum Cost For warding Algorithm (Minimum

10、 Cost For warding Algorithm for Large Sensor Networks)for Large Sensor Networks)充分利用了传感器网络中的数据传输不对称的充分利用了传感器网络中的数据传输不对称的特点，即大多的数据流都是从传感器节点向特点，即大多的数据流都是从传感器节点向SinkSink节点的方向传输。节点的方向传输。7.3 7.3 层次路由协议层次路由协议7.3.1 LEACH7.3.1 LEACH 低功耗自适应聚类分级低功耗自适应聚类分级LEACHLEACH协议协议(LOW Energy Adaptive (LOW Energy Adaptive

11、 Clustering Hierarchy)Clustering Hierarchy)是无线传感器网络中最早提出的分层路是无线传感器网络中最早提出的分层路由算法。由算法。LEACHLEACH可以将网络整体生存时间延长可以将网络整体生存时间延长1515，其基本思想，其基本思想是通过随机循环地选择簇头节点将整个网络的能量负载平均分配是通过随机循环地选择簇头节点将整个网络的能量负载平均分配到每个传感器节点中，从而降低网络能源消耗，提高网络整体生到每个传感器节点中，从而降低网络能源消耗，提高网络整体生存时间。存时间。 7.3.2 PEGASIS7.3.2 PEGASIS高能效采集传感器信息系统高能效采

12、集传感器信息系统PEGASISPEGASIS协议协议(Power(PowerEfficient Efficient Gathering in Sensor Information Systems)Gathering in Sensor Information Systems)是在是在LEACHLEACH协议上提出的协议上提出的一种改进路由算法。一种改进路由算法。PEGASISPEGASIS路由协议在网络中选择一个节点作为起始路由协议在网络中选择一个节点作为起始节点建立一条最优回路链，起始节点将数据融合后的数据信息发送给节点建立一条最优回路链，起始节点将数据融合后的数据信息发送给SinkSink

13、节点。由于起始节点的负载较重，节点。由于起始节点的负载较重，PEGASISPEGASIS采用了全网节点轮流作采用了全网节点轮流作为回路链起始节点的方式来进行均衡。为回路链起始节点的方式来进行均衡。 该路由协议中使用了贪婪算法该路由协议中使用了贪婪算法(Greedy Algorithm)(Greedy Algorithm)来形成链，如图来形成链，如图7-57-5所示。在每一轮通信之前才形成链。为确保每个节点都有其相邻节所示。在每一轮通信之前才形成链。为确保每个节点都有其相邻节点，从离基站最远的节点开始构建，链中邻居节点的距离会逐渐增大，点，从离基站最远的节点开始构建，链中邻居节点的距离会逐渐增大

14、，因为已经在链中的节点不能被再次访，当其中一个节点失效时，链必须因为已经在链中的节点不能被再次访，当其中一个节点失效时，链必须重构。重构。7.3.3 TEEN7.3.3 TEEN阈值敏感的高效传感器网络阈值敏感的高效传感器网络TEENTEEN协议协议(Threshold Sensitive Energy (Threshold Sensitive Energy Efficient Sensor Network)Efficient Sensor Network)，是一个基于簇群的路由协议，也是由，是一个基于簇群的路由协议，也是由LEACHLEACH发展发展而来，在这个协议中定义了硬门限和软门限两个

15、概念。而来，在这个协议中定义了硬门限和软门限两个概念。 这个算法适用于实时性要求较高的应用场合，用户可以及时获取感兴趣的这个算法适用于实时性要求较高的应用场合，用户可以及时获取感兴趣的信息。由于感应数据所耗能量比传输数据所耗能量要少得多，虽然节点一直处信息。由于感应数据所耗能量比传输数据所耗能量要少得多，虽然节点一直处于感应状态，但是由于减少了很多不必要的数据传输，因此相对来说还是节能于感应状态，但是由于减少了很多不必要的数据传输，因此相对来说还是节能的。该协议也有一些不足之处：的。该协议也有一些不足之处： 门限值达不到，节点就永远不会和簇头节点通信，用户就无法从网络得门限值达不到，节点就永远

16、不会和簇头节点通信，用户就无法从网络得到任何数据，即使节点已经死亡，用户也不知情；到任何数据，即使节点已经死亡，用户也不知情； TDMATDMA机制的运用保证了群中不会出现数据冲撞的情况，但是如果一个节机制的运用保证了群中不会出现数据冲撞的情况，但是如果一个节点没有数据要发送的话，属于它的时隙就浪费掉了，而其他节点却还在等待自点没有数据要发送的话，属于它的时隙就浪费掉了，而其他节点却还在等待自己的时隙，这样会向系统中引入过多的时延，不适于实时性要求太高的场合；己的时隙，这样会向系统中引入过多的时延，不适于实时性要求太高的场合； 没有相应的机制去区分那些没有感应到足够大变化的节点和处于关闭状没有

17、相应的机制去区分那些没有感应到足够大变化的节点和处于关闭状态的节点。群头节点的接收机要时刻处于激活状态，以便接收任何时候由成员态的节点。群头节点的接收机要时刻处于激活状态，以便接收任何时候由成员节点传来的数据，在某种程度上增加了簇头节点的负担。节点传来的数据，在某种程度上增加了簇头节点的负担。 7.3.4 APTEEN7.3.4 APTEEN、TTDDTTDD和和EARSNEARSN协议协议 1 1APTEENAPTEENAPTEEN (Adaptive Periodic FEEN)APTEEN (Adaptive Periodic FEEN)协议是对协议是对TEENTEEN的扩展，的扩展，它

18、是一种结合响应型和主动型传感器网络策略的混合型网络路由它是一种结合响应型和主动型传感器网络策略的混合型网络路由协议，可以根据用户需要和应用类型来设定协议的周期性和相关协议，可以根据用户需要和应用类型来设定协议的周期性和相关阀值，即可以周期性采集数据又可以对突发事件作出快速反应。阀值，即可以周期性采集数据又可以对突发事件作出快速反应。APTEENAPTEEN在在TEENTEEN的基础上定义了一个计数时间，当节点从上一次发的基础上定义了一个计数时间，当节点从上一次发送数据开始经历这个计数时间还没有发送数据，那么不管当前的送数据开始经历这个计数时间还没有发送数据，那么不管当前的数据是否满足软、硬门限

19、的要求都会发送这个数据。数据是否满足软、硬门限的要求都会发送这个数据。APTEENAPTEEN可以可以通过改变计数时间来控制能量消耗。通过改变计数时间来控制能量消耗。 2 2TTDDTTDD 双列数据分发双列数据分发TTDD(TWO-Tier Data Dissemination)TTDD(TWO-Tier Data Dissemination)，协议，协议假设节点静态，且各节点的位置信息已知。网络中可以存在多个假设节点静态，且各节点的位置信息已知。网络中可以存在多个SinkSink节点，节点，SinkSink节点可以在网络中任意移动。网络中的节点以虚节点可以在网络中任意移动。网络中的节点以虚

20、拟栅格的形式划分为若干区域，当监测区域发生事件，附近的多拟栅格的形式划分为若干区域，当监测区域发生事件，附近的多个节点将选择一个节点触发数据上报消息。发送数据上报消息的个节点将选择一个节点触发数据上报消息。发送数据上报消息的簇头节点将上报报文发送给栅格外的其他簇头节点将上报报文发送给栅格外的其他4 4个栅格的邻接节点，个栅格的邻接节点，由邻接节点转发给该栅格的另外由邻接节点转发给该栅格的另外3 3个邻接节点，最后将上报的数个邻接节点，最后将上报的数据报文发送到每一个栅格。这样无论据报文发送到每一个栅格。这样无论SinkSink节点移动到网络中的任节点移动到网络中的任何地方，都能够从距离最近的节

21、点上收到上报的数据报文。何地方，都能够从距离最近的节点上收到上报的数据报文。7.3.4 APTEEN7.3.4 APTEEN、TTDDTTDD和和EARSNEARSN协议协议 3 3EARSNEARSN 簇头固定的分簇结构路由协议簇头固定的分簇结构路由协议EARSN (Energy Aware EARSN (Energy Aware Routing for Cluster Based Sensor Network)Routing for Cluster Based Sensor Network)是基于三层体系是基于三层体系结构的路由协议。该协议要求网络运行前由终端用户将传感器节结构的路由协议。

22、该协议要求网络运行前由终端用户将传感器节点划分成簇，并通知每个簇头节点的点划分成簇，并通知每个簇头节点的IDID标识和簇内所分配节点的标识和簇内所分配节点的位置信息。传感器节点可以以活动方式和备用的低能源方式两种位置信息。传感器节点可以以活动方式和备用的低能源方式两种方式运行，并可以感知、转发、感知并转发和休眠方式运行，并可以感知、转发、感知并转发和休眠4 4种方式之一种方式之一存在。与其他路由协议不同的是，该协议的簇头不受能量的限制。存在。与其他路由协议不同的是，该协议的簇头不受能量的限制。它作为网络的中心管理者，可以监控节点的能量变化，决定并维它作为网络的中心管理者，可以监控节点的能量变化

23、，决定并维护传感器的护传感器的4 4种状态。算法依据两个节点间的能量消耗、延迟最种状态。算法依据两个节点间的能量消耗、延迟最优化等性能指标计算路径代价函数。簇头节点利用代价函数作为优化等性能指标计算路径代价函数。簇头节点利用代价函数作为链路成本，选择最小成本的路径作为节点与其通信的最优路径。链路成本，选择最小成本的路径作为节点与其通信的最优路径。经仿真分析，该协议在运行过程中具有很好的节能性、较高的吞经仿真分析，该协议在运行过程中具有很好的节能性、较高的吞吐量和较低的通信延迟。吐量和较低的通信延迟。7.3.4 APTEEN7.3.4 APTEEN、TTDDTTDD和和EARSNEARSN协议协

24、议7.3.5 7.3.5 平面路由协议和层次路由协议比较平面路由协议和层次路由协议比较表表7-17-1为各种协议之间的简单对比，主要从移动性、能量需求、路为各种协议之间的简单对比，主要从移动性、能量需求、路径长度、扩展性、路由状态复杂度、计算和通信所需开销、数据径长度、扩展性、路由状态复杂度、计算和通信所需开销、数据融合技术等多方面进行了分析比较。融合技术等多方面进行了分析比较。总体来看，由于网络结构的不同，平面路由和层次路由体现总体来看，由于网络结构的不同，平面路由和层次路由体现出了以下几处差异。出了以下几处差异。 移动性移动性 能量使用能量使用 路由选择路由选择 可拓展性可拓展性 开销开销

25、 7.3.5 7.3.5 平面路由协议和层次路由协议比较平面路由协议和层次路由协议比较7.4 7.4 能量感知路由能量感知路由7.4.1 7.4.1 能量消耗源能量消耗源 1 1通信相关的能量消耗通信相关的能量消耗 通信相关的能耗包括对传输器、中转器和接收器的使用。 2 2计算相关的能量消耗计算相关的能量消耗 计算相关的能耗主要涉及协议的处理，主要包括对CPU、主要存储器、一个很小的外设、磁盘或其他一些组成部分的使用。同样的，数据压缩技术在减少数据包长度的同时也因为计算量的增大而增加了能量消耗。7.4.27.4.2能量路由能量路由在如图在如图7-67-6所示的网络中，源节点是一般功能的传感器节

26、点，完成数据采所示的网络中，源节点是一般功能的传感器节点，完成数据采集工作。集工作。汇聚节点是数据发送的目标节点。大写字母表示节点，如节点汇聚节点是数据发送的目标节点。大写字母表示节点，如节点A A，节点右，节点右侧括号内的数字表示节点的可用能量。图中的双向线表示节点之间的侧括号内的数字表示节点的可用能量。图中的双向线表示节点之间的通信链路，链路上的数字表示在该链路上发送数据消耗的能量。在图通信链路，链路上的数字表示在该链路上发送数据消耗的能量。在图中，从源节点到汇聚节点的可能路径有中，从源节点到汇聚节点的可能路径有4 4条。条。 路径路径1 1：源节点：源节点B BA A汇聚节点，路径上所有

27、节点汇聚节点，路径上所有节点PAPA之和为之和为4 4，在该路径上发送分组需要的能量之和为，在该路径上发送分组需要的能量之和为3 3； 路径路径2 2：源节点：源节点C CB BA A汇聚节点，路径上所有节汇聚节点，路径上所有节点点PAPA之和为之和为6 6，在该路径上发送分组需要的能量之和为，在该路径上发送分组需要的能量之和为6 6； 路径路径3 3：源节点：源节点D D汇聚节点，路径上所有节点汇聚节点，路径上所有节点PAPA之之和为和为3 3，在该路上发送分组需要的能量之和为，在该路上发送分组需要的能量之和为4 4； 路径路径4 4：源节点：源节点F FE E汇聚节点，路径上所有节点汇聚节

28、点，路径上所有节点PAPA之和为之和为5 5，在该路径上发送分组需要的能量之和为，在该路径上发送分组需要的能量之和为6 6。 能量路由选择策略主要有以下几种：最大可用能量路能量路由选择策略主要有以下几种：最大可用能量路由、最小能量消耗路由、最少跳数路由和最大最小由、最小能量消耗路由、最少跳数路由和最大最小PAPA节点节点路由。路由。7.4.37.4.3能量多路径路由能量多路径路由 能量多路径路由的主要流程描述如下：能量多路径路由的主要流程描述如下： (1) (1)发起路径建立发起路径建立 (2) (2)判断是否转发路径建立消息判断是否转发路径建立消息 (3) (3)计算能量代价计算能量代价 (

29、4) (4)节点加入路径条件节点加入路径条件 (5) (5)节点选择概率计算节点选择概率计算 (6) (6)代价平均值计算代价平均值计算7.57.5基于查询的路由基于查询的路由基于查询的路由协议，在需要不断查询传感器节点采集的数基于查询的路由协议，在需要不断查询传感器节点采集的数据的应用中，通信流量主要产生于查询节点和传感器节点之间的据的应用中，通信流量主要产生于查询节点和传感器节点之间的命令和数据传输，同时传感器节点的采样信息在传输路径上通常命令和数据传输，同时传感器节点的采样信息在传输路径上通常要进行数据融合，通过减少通信流量来节省能量。要进行数据融合，通过减少通信流量来节省能量。7.5.

30、17.5.1定向扩散路由定向扩散路由定向扩散定向扩散(Directed Diffusion(Directed Diffusion，DD)DD)是一种基于查询的路由是一种基于查询的路由机制，是专门为无线传感器网络设计的。机制，是专门为无线传感器网络设计的。 定向扩散路由机制包括周期性的兴趣扩散、梯度建立、数据定向扩散路由机制包括周期性的兴趣扩散、梯度建立、数据传播、路径加强等阶段传播、路径加强等阶段 。 1 1兴趣扩散阶段兴趣扩散阶段 2 2梯度建立阶段梯度建立阶段 3 3数据传播阶段数据传播阶段 4 4路径加强阶段路径加强阶段7.5.27.5.2谣传路由谣传路由谣传路由谣传路由(Rumor R

31、outing)(Rumor Routing)，其路由的建立是由，其路由的建立是由SinkSink节点和节点和源节点共同发起并完成的。谣传路由的原理如图源节点共同发起并完成的。谣传路由的原理如图7-87-8所示。所示。谣传路由协议的执行过程如下：谣传路由协议的执行过程如下： 每个传感器节点维护一个邻居列表和每个传感器节点维护一个邻居列表和一个事件列表。一个事件列表。 当传感器节点在本地检测到一个事件当传感器节点在本地检测到一个事件时，就在事件列表中增加一个表项，设置相时，就在事件列表中增加一个表项，设置相关的事件名称、跳数等，同时根据一定的概关的事件名称、跳数等，同时根据一定的概率产生一个代理消

32、息。代理消息是一个包含率产生一个代理消息。代理消息是一个包含生命期等事件信息的分组，用来携带相关的生命期等事件信息的分组，用来携带相关的信息通告给它传输经过的每一个传感器节点。信息通告给它传输经过的每一个传感器节点。 网络的任何节点都可以对一个特定的事件生成查询消息。网络的任何节点都可以对一个特定的事件生成查询消息。 若查询消息和代理消息的路径出现交叉的情况，交叉节点会沿着查若查询消息和代理消息的路径出现交叉的情况，交叉节点会沿着查询消息的反方向将事件信息传送到查询节点。如果查询节点在一段时间内询消息的反方向将事件信息传送到查询节点。如果查询节点在一段时间内没有收到事件消息，就认为查询消息并没

33、有到达事件区域，可以选择重传、没有收到事件消息，就认为查询消息并没有到达事件区域，可以选择重传、放弃或洪泛查询放弃或洪泛查询7.67.6地理位置路由地理位置路由7.6.1 GEAR7.6.1 GEAR路由路由1.GEAR1.GEAR路由的基本思想路由的基本思想GEARGEAR采用查询驱动数据传送模式，根据事件区域的地理采用查询驱动数据传送模式，根据事件区域的地理位置信息，建立基站或者汇聚节点到事件区域的优化路径。位置信息，建立基站或者汇聚节点到事件区域的优化路径。2.GEAR2.GEAR中查询消息的传播中查询消息的传播 (1) (1) 查询消息传送到事件区域查询消息传送到事件区域 GEARGE

34、AR路由用实际代价路由用实际代价(1earned cost)(1earned cost)和估计代价和估计代价(estimated cost)(estimated cost)两种代价值两种代价值来表示路径代价。来表示路径代价。GEARGEAR通过如图通过如图7-97-9所示所示的方式来解决通信空洞问题，从而使路由的方式来解决通信空洞问题，从而使路由进行下去。进行下去。 (2) (2) 查询消息在事件区域内传播查询消息在事件区域内传播当查询命令被转发进入事件区域后，大多数当查询命令被转发进入事件区域后，大多数情况下采用递归的、基于地理信息的转发方式在事情况下采用递归的、基于地理信息的转发方式在事件

35、区域内发布查询命令。如图件区域内发布查询命令。如图7-107-10所示。所示。2.GEAR2.GEAR中查询消息的传播中查询消息的传播(3)GEAR(3)GEAR路由的性能路由的性能 GEARGEAR路由定义估计路由代价为节点到事件区域的距离和节点剩路由定义估计路由代价为节点到事件区域的距离和节点剩余能量，并利用捎带机制获取实际路由代价，进行数据传输的路径优化，余能量，并利用捎带机制获取实际路由代价，进行数据传输的路径优化，从而形成能量高效的数据传输路径。从而形成能量高效的数据传输路径。GEARGEAR路由采用的贪婪算法是一个局部路由采用的贪婪算法是一个局部最优的算法，适合无线传感器网络中节点

36、只知道局部拓扑信息的情况，其最优的算法，适合无线传感器网络中节点只知道局部拓扑信息的情况，其缺点是由于缺乏足够的拓扑信息，路由过程中可能遇到路由空洞，反而降缺点是由于缺乏足够的拓扑信息，路由过程中可能遇到路由空洞，反而降低了路由效率。低了路由效率。7.6.2 GAF7.6.2 GAF路由路由地域自适应保真算法地域自适应保真算法GAF (Geographic Adaptive Fidelity)GAF (Geographic Adaptive Fidelity)是基是基于有限能量和位置信息的路由算法于有限能量和位置信息的路由算法，GAFGAF算法的执行过程包括两个阶段。算法的执行过程包括两个阶段

37、。 第一阶段是虚拟网格的划分。根据节点的位置信息和通信半径，将网络区第一阶段是虚拟网格的划分。根据节点的位置信息和通信半径，将网络区域划分成若二干虚拟网格，保证相邻单元格中的任意两个节点都能够直接通信。域划分成若二干虚拟网格，保证相邻单元格中的任意两个节点都能够直接通信。假设节点已知整个监测区域的位置信息和本身的位置信息，节点可以通过计算假设节点已知整个监测区域的位置信息和本身的位置信息，节点可以通过计算得知自己属于哪个网格。得知自己属于哪个网格。 第二阶段是虚拟网格中簇头节点的选择。节点周期性地进入睡眠和工作状第二阶段是虚拟网格中簇头节点的选择。节点周期性地进入睡眠和工作状态，从睡眠状态唤醒

38、之后与本单元其他节点交换信息，以确定自己是否需要成态，从睡眠状态唤醒之后与本单元其他节点交换信息，以确定自己是否需要成为簇头节点。为簇头节点。每个节点处于发现每个节点处于发现(discovery)(discovery)、活动、活动(active)(active)以及睡眠以及睡眠(sleeping)3(sleeping)3种状态，如图种状态，如图7-137-13所示。所示。 7.6.3 GPSR7.6.3 GPSR路由路由 GPSR (Greedy Perimeter Stateless Routing)GPSR (Greedy Perimeter Stateless Routing)路由协议是

39、贪婪算法路由协议是贪婪算法(Greedy)(Greedy)和图形算法的结合，它不需要维护路由表，是一种无状态的路由协议。和图形算法的结合，它不需要维护路由表，是一种无状态的路由协议。 GPSRGPSR协议具有贪婪转发协议具有贪婪转发(Greedy Forwarding)(Greedy Forwarding)和周界转发和周界转发(Perimeters (Perimeters Forwarding)Forwarding)两种分组转发方式。两种分组转发方式。1. 1. 贪婪转发算法贪婪转发算法 贪婪转发算法是一种基于地理信息的路由算法。贪婪转发算法的前提是每贪婪转发算法是一种基于地理信息的路由算法。

40、贪婪转发算法的前提是每个分组都已包含其目的节点位置或目标区域位置，每个节点都已知自己及自接个分组都已包含其目的节点位置或目标区域位置，每个节点都已知自己及自接邻节点的位置。邻节点的位置。 贪婪转发算法总是朝距离目的节点最近的邻节点转发分组，如图贪婪转发算法总是朝距离目的节点最近的邻节点转发分组，如图7-147-14所示。所示。2 2周界转发周界转发 如图如图7-157-15所示，采用周界转发所示，采用周界转发方式时，通常采用右手规则确定转方式时，通常采用右手规则确定转发的路径。发的路径。 7.6.3 GPSR7.6.3 GPSR路由路由 图图7-167-16给出了右手规则的基本原理。当给出了右

41、手规则的基本原理。当一个数据分组从节点一个数据分组从节点x x到达节点到达节点y y时，它经过下时，它经过下一边时以一边时以y y为顶点，沿为顶点，沿(y,x)(y,x)逆时针方向上的第逆时针方向上的第一条链路，如图所示的为一条链路，如图所示的为(y,z)(y,z)，后续的同样，后续的同样依照此规则来确定，直到数据到达目的节点为依照此规则来确定，直到数据到达目的节点为止。止。 GPSRGPSR路由协议同时采用了贪婪算法和周界路由协议同时采用了贪婪算法和周界转发来对数据分组进行传送。在完整的拓扑图转发来对数据分组进行传送。在完整的拓扑图中采用贪婪转发，当贪婪转发找不到下一跳节中采用贪婪转发，当贪

42、婪转发找不到下一跳节点时，则在平面图中采用周界转发决定数据分点时，则在平面图中采用周界转发决定数据分组的下一跳。组的下一跳。7.6.4 GEM7.6.4 GEM和和MECNMECN路由路由1 1GEMGEM路由路由 GEM (Graph Embedding)GEM (Graph Embedding)路由协议是一种适用于数据中心存储路由协议是一种适用于数据中心存储(Data (Data Centric Storage)Centric Storage)方式的基于位置的路由协议。其基本思想是建立一个方式的基于位置的路由协议。其基本思想是建立一个虚拟极坐标系统，用来表示实际的网络拓扑结构虚拟极坐标系统

43、，用来表示实际的网络拓扑结构。2.MECN2.MECN路由路由 MECN (Minimum Energy Communication Network)MECN (Minimum Energy Communication Network)和和SMECN SMECN (Small MECN)(Small MECN) 协议的主要思想是构建子网，每个子网有一个主站协议的主要思想是构建子网，每个子网有一个主站(Master (Master Site)Site)，相当于层次路由中的簇头节点，要求子网内部所含节点数目少并且，相当于层次路由中的簇头节点，要求子网内部所含节点数目少并且任意两个节点之间传输数据都

44、消耗更少的能量。任意两个节点之间传输数据都消耗更少的能量。MECNMECN的实现分两个阶段完成。的实现分两个阶段完成。 (1)(1)第一阶段：获取位置信息，由节点内部的计算来构建包含所有发送第一阶段：获取位置信息，由节点内部的计算来构建包含所有发送节点外围的外围图；节点外围的外围图； (2)(2)第二阶段：在外围图中搜索最优路径，采用以能量消耗作为度量代第二阶段：在外围图中搜索最优路径，采用以能量消耗作为度量代价的分布式最短路径算法来实现。价的分布式最短路径算法来实现。7.7 7.7 可靠路由协议可靠路由协议7.7.17.7.1不相交多路径路由机制不相交多路径路由机制不相交多路径的建立过程如图

45、不相交多路径的建立过程如图7-177-17所示，其基本思想是：首先所示，其基本思想是：首先由汇聚节点发出主路径增强消息，建立一条由汇聚节点到源节点的由汇聚节点发出主路径增强消息，建立一条由汇聚节点到源节点的主路径主路径P P，如图，如图7-17(a)7-17(a)所示；然后进行备用路径的建立。汇聚节点所示；然后进行备用路径的建立。汇聚节点向其次优节点向其次优节点A A发出次优路径增强消息，节点发出次优路径增强消息，节点A A再将该消息发给自己再将该消息发给自己的最优节点的最优节点B B。 缠绕多路径的建立如图缠绕多路径的建立如图7-187-18所示。理想的缠绕所示。理想的缠绕多路径由一组缠绕路

46、径构成，如图多路径由一组缠绕路径构成，如图7-18(a)7-18(a)所示，在所示，在主路径上的每个节点都能找到一条不包括本身的从主路径上的每个节点都能找到一条不包括本身的从源节点到目的节点的最优路径源节点到目的节点的最优路径( (实际上是次优路径实际上是次优路径) )。而局部缠绕多路径则是经过运算后有可能在某些主而局部缠绕多路径则是经过运算后有可能在某些主路径的节点处找不到能绕过该节点的理想路径，如路径的节点处找不到能绕过该节点的理想路径，如图图7-18(b)7-18(b)所示。所示。 缠绕多路径可以克服主路径缠绕多路径可以克服主路径E E单个单个节点失败的问题。节点失败的问题。 缠绕多路径

47、的建缠绕多路径的建立如图立如图7-187-18所示。理想的缠绕多路径所示。理想的缠绕多路径由一组缠绕路径构成，如图由一组缠绕路径构成，如图7-18(a)7-18(a)所所示，在主路径上的每个节点都能找到示，在主路径上的每个节点都能找到一条不包括本身的从源节点到目的节一条不包括本身的从源节点到目的节点的最优路径点的最优路径( (实际上是次优路径实际上是次优路径) )。而局部缠绕多路径则是经过运算后有而局部缠绕多路径则是经过运算后有可能在某些主路径的节点处找不到能可能在某些主路径的节点处找不到能绕过该节点的理想路径，如图绕过该节点的理想路径，如图7-18(b)7-18(b)所示。所示。 7.7.17.7.1不相交多路径路由机制不相交多路径路由机制7.7.2 ReInForM7.7.2 ReInForM路由路由可靠多路径信息转发可靠多路径信息转发ReInForM (Reliable Information ReInForM (Reliable Information Forwarding us