第4章WSN通信与组网技术---03

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

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

3、转次数、延迟时间) )，进行评估比，进行评估比较；较； 将评估确定之后的最佳路由记录添加到此路径上各个设备的将评估确定之后的最佳路由记录添加到此路径上各个设备的路由表中。路由表中。3 3.WSN.WSN路由协议分类方法路由协议分类方法1 1）按源节点获取路径的方法按源节点获取路径的方法(1)(1)主动路由协议主动路由协议 (2)(2)按需路由协议按需路由协议 (3)(3)混合路由协议混合路由协议2 2）按节点参与通信的方式按节点参与通信的方式(1)(1)直接通信路由协议直接通信路由协议 (2)(2)平面路由协议平面路由协议 (3)(3)层次路由协议层次路由协议 3 3）按路由的发现过程按路由的

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

5、2 平面路由协议平面路由协议1 1. . Flooding and Grossing Flooding and Grossing协议协议 1 1） 洪泛路由协议洪泛路由协议洪泛路由协议洪泛路由协议(Flooding Protocol)(Flooding Protocol)是一种最早的路由协议，是一种最早的路由协议，接收到消息的节点以广播的彤式转发报文给所有的邻居节点。接收到消息的节点以广播的彤式转发报文给所有的邻居节点。洪泛法的优点和缺点都十分突出，其优点是实现简单，适用洪泛法的优点和缺点都十分突出，其优点是实现简单，适用于健壮性要求高的场合；其缺点是存在信息爆炸问题于健壮性要求高的场合；其缺

6、点是存在信息爆炸问题( (如图如图7-17-1所所示示) )、出现部分数据交迭的现象、出现部分数据交迭的现象( (如图如图7-27-2所示所示) )和盲目使用资源等。和盲目使用资源等。 2 2） 闲聊法闲聊法闲聊法闲聊法(Grossing)(Grossing)是洪泛法的改进版本。是洪泛法的改进版本。 在某一个节点发送数据时，不再像洪泛法那样给它的每个邻居节在某一个节点发送数据时，不再像洪泛法那样给它的每个邻居节点都发送数据副本，而是随机选择某个邻居节点，向它发送一份点都发送数据副本，而是随机选择某个邻居节点，向它发送一份数据副本。接收到数据的节点采用相同的方法，随机选择下一个数据副本。接收到数

7、据的节点采用相同的方法，随机选择下一个接收节点发送数据，如图接收节点发送数据，如图7-37-3所示。所示。2 2. . SPIN SPIN协议协议基于协商机制的传感器网络基于协商机制的传感器网络SPINSPIN协议协议(Sensor (Sensor Protocols for Information via Negotiation)Protocols for Information via Negotiation)是一种以数是一种以数据为中心的白适应通信方式，使用据为中心的白适应通信方式，使用3 3种类型的信息进行通信，种类型的信息进行通信，即即ADVADV、REQREQ和和DATADATA信

8、息。信息。图图7-47-4表示了表示了SPINSPIN协议的工作过程。在发送一个协议的工作过程。在发送一个TATATATA数据包数据包之前，一个传感器节点首先对外广播之前，一个传感器节点首先对外广播ADVADV数据包；如果某个邻居数据包；如果某个邻居节点在收到节点在收到ADVADV后有意愿接收该后有意愿接收该DATADATA数据包，那么它向该节点发数据包，那么它向该节点发送一个送一个REQREQ数据包，然后节点向该邻居节点发送数据包，然后节点向该邻居节点发送DATADATA数据包。类数据包。类似地进行下去，似地进行下去， DATADATA数据包可被传输到远方汇聚节点或基站。数据包可被传输到远方

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

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

11、的单跳邻居节点为根节点的多播树来实现传感器节点到邻居节点为根节点的多播树来实现传感器节点到SinkSink节点的多跳节点的多跳路径。该协议的特点是路由决策不仅要考虑到每条路径的能源，路径。该协议的特点是路由决策不仅要考虑到每条路径的能源，还要涉及端到端的延迟需求和待发送数据包的优先级。还要涉及端到端的延迟需求和待发送数据包的优先级。SARSAR的能的能量消耗较少，但不适用于大型的和拓扑频繁变化的网络。量消耗较少，但不适用于大型的和拓扑频繁变化的网络。 2 2）DDDD协议协议定向扩散路由定向扩散路由DDDD协议协议(Directed Diffusion)(Directed Diffusion)

12、是一种以数据为是一种以数据为中心的信息传播协议，与已有的路由算法有着截然不同的实现机中心的信息传播协议，与已有的路由算法有着截然不同的实现机制。运行制。运行DDDD协议的传感器节点使用基于属性的命名机制来描述数协议的传感器节点使用基于属性的命名机制来描述数据，并通过向所有节点发送对某个命名数据的据，并通过向所有节点发送对某个命名数据的Interest(Interest(任务描任务描述符述符) )来完成数据收集。来完成数据收集。 3 3）MCFAMCFA协议协议 最小开销前行算法最小开销前行算法MCFAMCFA协议协议(Minimum Cost For warding (Minimum Cost

13、 For warding Algorithm for Large Sensor Networks)Algorithm for Large Sensor Networks)充分利用了传感器网络充分利用了传感器网络中的数据传输不对称的特点，即大多的数据流都是从传感器节点中的数据传输不对称的特点，即大多的数据流都是从传感器节点向向SinkSink节点的方向传输。节点的方向传输。该算法根据能量和路径情况来灵活地测出节点的开销情况，该算法根据能量和路径情况来灵活地测出节点的开销情况，但是它存在着如下一些问题：首先它不得不考虑延迟、信道错误但是它存在着如下一些问题：首先它不得不考虑延迟、信道错误和节点失败

14、等问题，这就增大了算法的复杂度；其次，和节点失败等问题，这就增大了算法的复杂度；其次，SinkSink节点节点的数目不能太多，否则节点要存储大量到的数目不能太多，否则节点要存储大量到SinkSink节点的开销信息，节点的开销信息，会增大存储负担；再次，开销域的建立时间取决于网络的大小，会增大存储负担；再次，开销域的建立时间取决于网络的大小，如果网络太大的话，建立整个开销域的时间会让人无法忍受；最如果网络太大的话，建立整个开销域的时间会让人无法忍受；最后，网络负载不是很平衡，那些距离后，网络负载不是很平衡，那些距离SinkSink节点较近的开销较小的节点较近的开销较小的节点容易很快耗尽能量。节点

15、容易很快耗尽能量。4.84.8.3 .3 层次路由协议层次路由协议1 1. . LEACH LEACH 低功耗自适应聚类分级低功耗自适应聚类分级LEACHLEACH协议协议(LOW Energy Adaptive (LOW Energy Adaptive Clustering Hierarchy)Clustering Hierarchy)是无线传感器网络中最早提出的分层路是无线传感器网络中最早提出的分层路由算法。由算法。LEACHLEACH可以将网络整体生存时间延长可以将网络整体生存时间延长1515，其基本思想，其基本思想是通过随机循环地选择簇头节点将整个网络的能量负载平均分配是通过随机循环地

16、选择簇头节点将整个网络的能量负载平均分配到每个传感器节点中，从而降低网络能源消耗，提高网络整体生到每个传感器节点中，从而降低网络能源消耗，提高网络整体生存时间。存时间。 2 2. . PEGASIS PEGASIS高能效采集传感器信息系统高能效采集传感器信息系统PEGASISPEGASIS协议协议(Power(PowerEfficient Efficient Gathering in Sensor Information Systems)Gathering in Sensor Information Systems)是在是在LEACHLEACH协议上协议上提出的一种改进路由算法。提出的一种改进

17、路由算法。PEGASISPEGASIS路由协议在网络中选择一个路由协议在网络中选择一个节点作为起始节点建立一条最优回路链，起始节点将数据融合后节点作为起始节点建立一条最优回路链，起始节点将数据融合后的数据信息发送给的数据信息发送给SinkSink节点。由于起始节点的负载较重，节点。由于起始节点的负载较重，PEGASISPEGASIS采用了全网节点轮流作为回路链起始节点的方式来进行采用了全网节点轮流作为回路链起始节点的方式来进行均衡。均衡。 PEGASISPEGASIS的模型假设如下：的模型假设如下： 节点都知道其他节点的位置信息，每个节点都具有直接和基节点都知道其他节点的位置信息，每个节点都具

18、有直接和基站通信的能力：站通信的能力： 传感器节点不具有移动性；传感器节点不具有移动性； 其他模型假设和其他模型假设和LEACHLEACH中的相同。中的相同。该路由协议中使用了贪婪算法该路由协议中使用了贪婪算法(Greedy Algorithm)(Greedy Algorithm)来形成链，来形成链，如图如图7-57-5所示。在每一轮通信之前才形成链。为确保每个节点都所示。在每一轮通信之前才形成链。为确保每个节点都有其相邻节点，从离基站最远的节点开始构建，链中邻居节点的有其相邻节点，从离基站最远的节点开始构建，链中邻居节点的距离会逐渐增大，因为已经在链中的节点不能被再次访，当其中距离会逐渐增大

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

20、念。 由于报告时间以外的时间，节点都会关闭发射机，因此节约了由于报告时间以外的时间，节点都会关闭发射机，因此节约了能量。能量。TEENTEEN的模型中假设条件为：的模型中假设条件为：网络由一个基站和一个由传感器节点构成的网络组成，并且网络由一个基站和一个由传感器节点构成的网络组成，并且传感器节点都拥有相同的初始能量值；传感器节点都拥有相同的初始能量值； 基站拥有持续的能量补充，可以方便的向节点传送指令和数基站拥有持续的能量补充，可以方便的向节点传送指令和数据。据。 TEENTEEN利用利用LEACHLEACH的策略形成簇群，在每次簇群重组的时候，群的策略形成簇群，在每次簇群重组的时候，群头节点

21、除了广播数据属性以外，还要广播硬门限和软门限。其工作头节点除了广播数据属性以外，还要广播硬门限和软门限。其工作过程为：节点连续地感应周围的情况过程为：节点连续地感应周围的情况( (此时发射机处于关闭或者休眠此时发射机处于关闭或者休眠状态状态) )，当节点收集到的数据首次大于硬门限值时，节点就打开发射，当节点收集到的数据首次大于硬门限值时，节点就打开发射机向群头节点报告信息。感应到的数据保存在节点内部的一个状态机向群头节点报告信息。感应到的数据保存在节点内部的一个状态变量变量(State Viable(State Viable，SV)SV)。当最新感应到的数据值大于硬门限并且。当最新感应到的数据

22、值大于硬门限并且这个值和这个值和SVSV的差值大于或等于软门限时，节点才进行数据发送。的差值大于或等于软门限时，节点才进行数据发送。这个算法适用于实时性要求较高的应用场合，用户可以及时获取感这个算法适用于实时性要求较高的应用场合，用户可以及时获取感兴趣的信息。由于感应数据所耗能量比传输数据所耗能量要少得多，虽兴趣的信息。由于感应数据所耗能量比传输数据所耗能量要少得多，虽然节点一直处于感应状态，但是由于减少了很多不必要的数据传输，因然节点一直处于感应状态，但是由于减少了很多不必要的数据传输，因此相对来说还是节能的。该协议也有一些不足之处：此相对来说还是节能的。该协议也有一些不足之处： 门限值达不

23、到，节点就永远不会和簇头节点通信，用户就无法从门限值达不到，节点就永远不会和簇头节点通信，用户就无法从网络得到任何数据，即使节点已经死亡，用户也不知情；网络得到任何数据，即使节点已经死亡，用户也不知情； TDMATDMA机制的运用保证了群中不会出现数据冲撞的情况，但是如果机制的运用保证了群中不会出现数据冲撞的情况，但是如果一个节点没有数据要发送的话，属于它的时隙就浪费掉了，而其他节点一个节点没有数据要发送的话，属于它的时隙就浪费掉了，而其他节点却还在等待自己的时隙，这样会向系统中引入过多的时延，不适于实时却还在等待自己的时隙，这样会向系统中引入过多的时延，不适于实时性要求太高的场合；性要求太高

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

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

26、经历这个计数时间还没有发送数据，那么不管当前的数据是否满足软、硬门限的要求都会发送这个数据。数据是否满足软、硬门限的要求都会发送这个数据。APTEENAPTEEN可以可以通过改变计数时间来控制能量消耗。通过改变计数时间来控制能量消耗。 2 2）TTDDTTDD 双列数据分发双列数据分发TTDD(TWO-Tier Data Dissemination)TTDD(TWO-Tier Data Dissemination)，协议，协议假设节点静态，且各节点的位置信息已知。网络中可以存在多个假设节点静态，且各节点的位置信息已知。网络中可以存在多个SinkSink节点，节点，SinkSink节点可以在网络

27、中任意移动。网络中的节点以虚节点可以在网络中任意移动。网络中的节点以虚拟栅格的形式划分为若干区域，当监测区域发生事件，附近的多拟栅格的形式划分为若干区域，当监测区域发生事件，附近的多个节点将选择一个节点触发数据上报消息。发送数据上报消息的个节点将选择一个节点触发数据上报消息。发送数据上报消息的簇头节点将上报报文发送给栅格外的其他簇头节点将上报报文发送给栅格外的其他4 4个栅格的邻接节点，个栅格的邻接节点，由邻接节点转发给该栅格的另外由邻接节点转发给该栅格的另外3 3个邻接节点，最后将上报的数个邻接节点，最后将上报的数据报文发送到每一个栅格。这样无论据报文发送到每一个栅格。这样无论SinkSin

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

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

30、器的4 4种状态。算法依据两个节点间的能量消耗、延迟最种状态。算法依据两个节点间的能量消耗、延迟最优化等性能指标计算路径代价函数。簇头节点利用代价函数作为优化等性能指标计算路径代价函数。簇头节点利用代价函数作为链路成本，选择最小成本的路径作为节点与其通信的最优路径。链路成本，选择最小成本的路径作为节点与其通信的最优路径。经仿真分析，该协议在运行过程中具有很好的节能性、较高的吞经仿真分析，该协议在运行过程中具有很好的节能性、较高的吞吐量和较低的通信延迟。吐量和较低的通信延迟。5 5） 平面路由协议和层次路由协议比较平面路由协议和层次路由协议比较表表7-17-1为各种协议之间的简单对比，主要从移动

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

32、）计算相关的能量消耗计算相关的能量消耗 2 2. .能量路由能量路由能量路由是最早提出的传感器网络路由机制之一，根据节点能量路由是最早提出的传感器网络路由机制之一，根据节点的可用能量的可用能量(Power Available(Power Available，PA)PA)或传输路径上链路的能量需或传输路径上链路的能量需求，选择数据的转发路径。节点可用能量就是节点当前的剩余能求，选择数据的转发路径。节点可用能量就是节点当前的剩余能量。在如图量。在如图7-67-6所示的网络中，源节点是一般功能的传感器节点，所示的网络中，源节点是一般功能的传感器节点，完成数据采集工作。完成数据采集工作。汇聚节点是数据

33、发送的目标节点。大写字母表示节点，如节点汇聚节点是数据发送的目标节点。大写字母表示节点，如节点A A，节点右侧括号内的数字表示节点的可用能量。图中的双向线表示节点之节点右侧括号内的数字表示节点的可用能量。图中的双向线表示节点之间的通信链路，链路上的数字表示在该链路上发送数据消耗的能量。在间的通信链路，链路上的数字表示在该链路上发送数据消耗的能量。在图中，从源节点到汇聚节点的可能路径有图中，从源节点到汇聚节点的可能路径有4 4条。条。 路径路径1 1：源节点：源节点BABA汇聚节点，路径上所有节点汇聚节点，路径上所有节点PAPA之和为之和为4 4，在该，在该路径上发送分组需要的能量之和为路径上发

34、送分组需要的能量之和为3 3； 路径路径2 2：源节点：源节点CBACBA汇聚节点，路径上所有节点汇聚节点，路径上所有节点PAPA之和为之和为6 6，在，在该路径上发送分组需要的能量之和为该路径上发送分组需要的能量之和为6 6； 路径路径3 3：源节点：源节点DD汇聚节点，路径上所有节点汇聚节点，路径上所有节点PAPA之和为之和为3 3，在该路上，在该路上发送分组需要的能量之和为发送分组需要的能量之和为4 4； 路径路径4 4：源节点：源节点FEFE汇聚节点，路径上所有节点汇聚节点，路径上所有节点PAPA之和为之和为5 5，在该，在该路径上发送分组需要的能量之和为路径上发送分组需要的能量之和为

35、6 6。 能量路由选择策略主要有以下几种：最大可用能量路由、最小能量消耗能量路由选择策略主要有以下几种：最大可用能量路由、最小能量消耗路由、最少跳数路由和最大最小路由、最少跳数路由和最大最小PAPA节点路由。节点路由。3 3. .能量多路径路由能量多路径路由 能量多路径路由的主要流程描述如下：能量多路径路由的主要流程描述如下：(1)(1)发起路径建立发起路径建立目的节点广播路径建立消息，启动路径建立过程。广播消息中目的节点广播路径建立消息，启动路径建立过程。广播消息中包含一个代价域，表示发出该消息的节点到目的节点路径上的能量信包含一个代价域，表示发出该消息的节点到目的节点路径上的能量信息，设初

36、始值为零。息，设初始值为零。(2)(2)判断是否转发路径建立消息判断是否转发路径建立消息当某一个节点接收到邻居节点发送的路径建立消息时，与发送当某一个节点接收到邻居节点发送的路径建立消息时，与发送该消息的节点进行比较，如果自己距离源节点更近，并且距离目的节该消息的节点进行比较，如果自己距离源节点更近，并且距离目的节点更远的情况下，才转发该路径建立消息，否则丢弃该消息。点更远的情况下，才转发该路径建立消息，否则丢弃该消息。(3)(3)计算能量代价计算能量代价如果节点决定转发路径建立消息，需要计算新的代价值来替代如果节点决定转发路径建立消息，需要计算新的代价值来替代原来的代价值。原来的代价值。 (

37、4)(4)节点加入路径条件节点加入路径条件代价太大的路径对网络生存时间没有益处，因此并非每个路代价太大的路径对网络生存时间没有益处，因此并非每个路径都是可用的，节点需要丢弃代价太大的路径。径都是可用的，节点需要丢弃代价太大的路径。 (5)(5)节点选择概率计算节点选择概率计算为了均衡网络中节点的能量消耗，节点选择概率需与能量消为了均衡网络中节点的能量消耗，节点选择概率需与能量消耗成反比。耗成反比。 (6)(6)代价平均值计算代价平均值计算节点根据路由表中的能量代价和下一跳节点选择概率计算本节点根据路由表中的能量代价和下一跳节点选择概率计算本身到目的节点的代价。身到目的节点的代价。4.84.8.

38、5.5基于查询的路由基于查询的路由基于查询的路由协议，在需要不断查询传感器节点采集的数基于查询的路由协议，在需要不断查询传感器节点采集的数据的应用中，通信流量主要产生于查询节点和传感器节点之间的据的应用中，通信流量主要产生于查询节点和传感器节点之间的命令和数据传输，同时传感器节点的采样信息在传输路径上通常命令和数据传输，同时传感器节点的采样信息在传输路径上通常要进行数据融合，通过减少通信流量来节省能量。要进行数据融合，通过减少通信流量来节省能量。1 1. .定向扩散路由定向扩散路由定向扩散定向扩散(Directed Diffusion(Directed Diffusion，DD)DD)是一种基

39、于查询的路由是一种基于查询的路由机制，是专门为无线传感器网络设计的。机制，是专门为无线传感器网络设计的。 定向扩散路由机制包括周期性的兴趣扩散、梯度建立、数据定向扩散路由机制包括周期性的兴趣扩散、梯度建立、数据传播、路径加强等阶段传播、路径加强等阶段 。1 1）兴趣扩散阶段兴趣扩散阶段在兴趣扩散阶段，汇聚节点周期性在兴趣扩散阶段，汇聚节点周期性地向邻居节点广播兴趣消息。兴趣消息地向邻居节点广播兴趣消息。兴趣消息中含有任务类型、事件区域、数据发送中含有任务类型、事件区域、数据发送速率、时间戳等参数。每个节点在本地速率、时间戳等参数。每个节点在本地保存一个兴趣列表，对于每一个兴趣，保存一个兴趣列表

40、，对于每一个兴趣，列表中都有一个表项来记录该消息的邻列表中都有一个表项来记录该消息的邻居节点、数据发送速率和时间戳等任务居节点、数据发送速率和时间戳等任务相关信息，以建立该节点向汇聚节点传相关信息，以建立该节点向汇聚节点传递数据的梯度关系。递数据的梯度关系。 2 2）梯度建立阶段梯度建立阶段 DDDD协议需要在传感器节点和协议需要在传感器节点和SinkSink节点之间建立梯度，以保证节点之间建立梯度，以保证可靠的传输数据。网络中的节点从邻居节点接收到一个兴趣消息可靠的传输数据。网络中的节点从邻居节点接收到一个兴趣消息时，无法判断此消息是否是己处理过的，或者是否和另一个方向时，无法判断此消息是否

41、是己处理过的，或者是否和另一个方向的邻居节点所发来的兴趣消息相同，所以当兴趣消息在整个网络的邻居节点所发来的兴趣消息相同，所以当兴趣消息在整个网络扩散的时候，相邻的节点彼此都建立一个梯度。这样的优点是加扩散的时候，相邻的节点彼此都建立一个梯度。这样的优点是加快了无效路径的修复，有利于路径的加强，从而不会产生持久的快了无效路径的修复，有利于路径的加强，从而不会产生持久的环路，但同时也导致了一个节点可能会收到多个相同的兴趣消息，环路，但同时也导致了一个节点可能会收到多个相同的兴趣消息，造成消息在网络中的泛滥。造成消息在网络中的泛滥。3 3）数据传播阶段数据传播阶段 当传感器节点采集到与兴趣匹配的数

42、据时，把数据发送到梯当传感器节点采集到与兴趣匹配的数据时，把数据发送到梯度上的邻居节点，并按照梯度上的数据传输速率设定传感器模块度上的邻居节点，并按照梯度上的数据传输速率设定传感器模块采集数据的速率。由于可能从多个邻居节点收到兴趣消息，节点采集数据的速率。由于可能从多个邻居节点收到兴趣消息，节点向多个邻居节点发送数据，汇聚节点可能收到经过多个路径的相向多个邻居节点发送数据，汇聚节点可能收到经过多个路径的相同数据。中间节点收到其他节点转发的数据后，首先查询兴趣列同数据。中间节点收到其他节点转发的数据后，首先查询兴趣列表的表项。如果没有匹配的兴趣表项就丢弃数据；如果存在相应表的表项。如果没有匹配的

43、兴趣表项就丢弃数据；如果存在相应的兴趣表项，则检查与这个兴趣对应的数据缓冲区的兴趣表项，则检查与这个兴趣对应的数据缓冲区( (数据缓冲区数据缓冲区保存了最近转发的数据保存了最近转发的数据) )。如果在数据缓冲区中有与接收到的数据匹配的副本，说明已如果在数据缓冲区中有与接收到的数据匹配的副本，说明已经转发过这个数据，为避免出现传输环路将丢弃这个数据，否则，经转发过这个数据，为避免出现传输环路将丢弃这个数据，否则，检查该兴趣表项中的邻居节点信息。如果设置的邻居节点数据发检查该兴趣表项中的邻居节点信息。如果设置的邻居节点数据发送速率大于等于接收的数据速率，则全部转发接收的数据；如果送速率大于等于接收

44、的数据速率，则全部转发接收的数据；如果记录的邻居节点数据发送速率小于接收的数据速率，则按照比例记录的邻居节点数据发送速率小于接收的数据速率，则按照比例转发。对于转发的数据，数据缓冲区将保留一个副本，并记录转转发。对于转发的数据，数据缓冲区将保留一个副本，并记录转发时间。发时间。 4 4）路径加强阶段路径加强阶段定向扩散路由机制通过正向加强机制来建立优化路径，并根定向扩散路由机制通过正向加强机制来建立优化路径，并根据网络拓扑的变化修改数据转发的梯度关系。兴趣扩散阶段是为据网络拓扑的变化修改数据转发的梯度关系。兴趣扩散阶段是为了建立源节点到汇聚节点的数据传输路径，数据源节点以较低的了建立源节点到汇

45、聚节点的数据传输路径，数据源节点以较低的速率采集和发送数据，称这个阶段建立的梯度为探测梯度速率采集和发送数据，称这个阶段建立的梯度为探测梯度(probe (probe gradient)gradient)。汇聚节点在收到从源节点发来的数据后，启动建立。汇聚节点在收到从源节点发来的数据后，启动建立汇聚节点到源节点的加强路径，后续数据将沿着加强路径以较高汇聚节点到源节点的加强路径，后续数据将沿着加强路径以较高的数据速率进行传输，加强后的梯度称为数据梯度的数据速率进行传输，加强后的梯度称为数据梯度(data (data gradient)gradient)。2 2. .谣传路由谣传路由谣传路由谣传路

46、由(Rumor Routing)(Rumor Routing)，其路由的建立是由，其路由的建立是由SinkSink节点和节点和源节点共同发起并完成的。谣传路由借鉴了欧氏平面图上任意两源节点共同发起并完成的。谣传路由借鉴了欧氏平面图上任意两条曲线交叉几率很大的思想，当一个节点检测到一个事件，它将条曲线交叉几率很大的思想，当一个节点检测到一个事件，它将事件增加到该节点自身保存的表单，称为事件表。然后产生一个事件增加到该节点自身保存的表单，称为事件表。然后产生一个被称为代理被称为代理(agent)(agent)的生命期较长的数据包，代理消息沿着随机的生命期较长的数据包，代理消息沿着随机路径向外扩散传

47、播，同时汇聚节点发送的查询消息也沿随机路径路径向外扩散传播，同时汇聚节点发送的查询消息也沿随机路径在网络中传播。当代理消息和查询消息的传输路径交叉在一起时，在网络中传播。当代理消息和查询消息的传输路径交叉在一起时，就会形成一条汇聚节点到事件区域的完整路径，谣传路由的原理就会形成一条汇聚节点到事件区域的完整路径，谣传路由的原理如图如图7-87-8所示。所示。圈中区域表示发生事件的区域，圆点表示传感器节点，黑色圈中区域表示发生事件的区域，圆点表示传感器节点，黑色圆点表示代理消息经过的传感器节点，灰色圆点表示查询消息经圆点表示代理消息经过的传感器节点，灰色圆点表示查询消息经过的传感器节点，连接灰色节

48、点和部分黑色节点的路径表示事件过的传感器节点，连接灰色节点和部分黑色节点的路径表示事件区域到汇聚节点的数据传输路径。区域到汇聚节点的数据传输路径。谣传路由协议的执行过程如下：谣传路由协议的执行过程如下： 每个传感器节点维护一个邻居列表和一个事件列表。每个传感器节点维护一个邻居列表和一个事件列表。 当传感器节点在本地检测到一个事件时，就在事件列表中增当传感器节点在本地检测到一个事件时，就在事件列表中增加一个表项，设置相关的事件名称、跳数等，同时根据一定的概率加一个表项，设置相关的事件名称、跳数等，同时根据一定的概率产生一个代理消息。代理消息是一个包含生命期等事件信息的分组，产生一个代理消息。代理

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

50、重传、放弃或洪泛查询。区域，可以选择重传、放弃或洪泛查询。4.84.8.6.6地理位置路由地理位置路由1 1. . GEAR GEAR路由路由 1 1）GEARGEAR路由的基本思想路由的基本思想GEARGEAR采用查询驱动数据传送模式，根据事件区域的地理位置采用查询驱动数据传送模式，根据事件区域的地理位置信息，建立基站或者汇聚节点到事件区域的优化路径，避免泛洪信息，建立基站或者汇聚节点到事件区域的优化路径，避免泛洪查询消息，从而减少了路由建立的开销。查询消息，从而减少了路由建立的开销。GEARGEAR算法中提出，传感算法中提出，传感器网络中的数据经常包含了位置属性信息，利用这一信息，把在器网

51、络中的数据经常包含了位置属性信息，利用这一信息，把在整个网络中扩散的信息传送到适当的位置区域中。整个网络中扩散的信息传送到适当的位置区域中。2 2） GEAR GEAR中查询消息的传播中查询消息的传播 (1) (1) 查询消息传送到事件区域查询消息传送到事件区域 GEARGEAR路由用实际代价路由用实际代价(1earned cost)(1earned cost)和估计代价和估计代价(estimated (estimated cost)cost)两种代价值来表示路径代价。两种代价值来表示路径代价。GEARGEAR通过如图通过如图7-97-9所示的方式所示的方式来解决通信空洞问题，从而使路由进行下

52、去。来解决通信空洞问题，从而使路由进行下去。 (2) (2) 查询消息在事件区域内传播查询消息在事件区域内传播当查询命令被转发进入事件区域后，大多数情况下采用递归的、基当查询命令被转发进入事件区域后，大多数情况下采用递归的、基于地理信息的转发方式在事件区域内发布查询命令。如图于地理信息的转发方式在事件区域内发布查询命令。如图7-107-10所示，假所示，假设大矩形就是事件区域，当路由查询命令转发到了位于事件区域内的设大矩形就是事件区域，当路由查询命令转发到了位于事件区域内的N Ni i节点时，节点时，N Ni i发现自己就在事件区域内，于是把事件区域分成发现自己就在事件区域内，于是把事件区域分

53、成4 4个小矩形区个小矩形区域，把查询命令向这域，把查询命令向这4 4个子事件区域进行转发，在向子区域转发分组的时个子事件区域进行转发，在向子区域转发分组的时候同样遵循前面所讲的规则。重复这个区域划分和转发的过程，一直到候同样遵循前面所讲的规则。重复这个区域划分和转发的过程，一直到满足停止转发的时候为止。满足停止转发的时候为止。(3)GEAR(3)GEAR路由的性能路由的性能 GEARGEAR路由定义估计路由代价为节点到事件区域的距离和节路由定义估计路由代价为节点到事件区域的距离和节点剩余能量，并利用捎带机制获取实际路由代价，进行数据传输点剩余能量，并利用捎带机制获取实际路由代价，进行数据传输

54、的路径优化，从而形成能量高效的数据传输路径。的路径优化，从而形成能量高效的数据传输路径。GEARGEAR路由采用路由采用的贪婪算法是一个局部最优的算法，适合无线传感器网络中节点的贪婪算法是一个局部最优的算法，适合无线传感器网络中节点只知道局部拓扑信息的情况，其缺点是由于缺乏足够的拓扑信息，只知道局部拓扑信息的情况，其缺点是由于缺乏足够的拓扑信息，路由过程中可能遇到路由空洞，反而降低了路由效率。如果节点路由过程中可能遇到路由空洞，反而降低了路由效率。如果节点拥有相邻两跳节点的地理位置信息，可以大大减少路由空洞的产拥有相邻两跳节点的地理位置信息，可以大大减少路由空洞的产生概率。生概率。GEARGE

55、AR路由中假设节点的地理位置固定或变化不频繁，适路由中假设节点的地理位置固定或变化不频繁，适用于节点移动性不强的应用环境。用于节点移动性不强的应用环境。2 2. . GAF GAF路由路由地域自适应保真算法地域自适应保真算法GAF (Geographic Adaptive Fidelity)GAF (Geographic Adaptive Fidelity)是基于有限能量和位置信息的路由算法，它原本是为移动是基于有限能量和位置信息的路由算法，它原本是为移动Ad HocAd Hoc网络设计的，但同样可以应用于传感器网络，因为它的虚拟网格网络设计的，但同样可以应用于传感器网络，因为它的虚拟网格思想

56、为分簇机制提供了新思路。思想为分簇机制提供了新思路。GAFGAF在不影响路由有效性的情况在不影响路由有效性的情况下，通过关闭一幽不需要的节点来节省能量，同时还考虑了所有下，通过关闭一幽不需要的节点来节省能量，同时还考虑了所有节点能量消耗的均衡性。节点能量消耗的均衡性。GAFGAF协议中，网络被划分为若干固定区域，形成一个虚拟网协议中，网络被划分为若干固定区域，形成一个虚拟网格。节点通过格。节点通过GPSGPS定位获取自己在网格中所处的定位获取自己在网格中所处的“位置位置”，如果，如果两个节点处在相同两个节点处在相同“位置位置”，则认为它们在路由时是等价的，则认为它们在路由时是等价的( (分分组

57、转发能耗水平相等组转发能耗水平相等) )。等价节点中只需有一个处于工作状态，其余节点可以进入睡等价节点中只需有一个处于工作状态，其余节点可以进入睡眠，眠，GAFGAF通过这种办法来节约能量，如图通过这种办法来节约能量，如图7-117-11所示，因此，所示，因此，GAFGAF能能够有效地延长网络的生命周期。够有效地延长网络的生命周期。在图在图7-127-12中，节点中，节点2 2、3 3、4 4在同一个栅格在同一个栅格B B中，因此只需要保留其中，因此只需要保留其中一个节点处于工作状态，另外两个可以处于休眠状态。而这在中一个节点处于工作状态，另外两个可以处于休眠状态。而这在Ad HocAd Ho

58、c网络中是绝对不可取的，因为在网络中是绝对不可取的，因为在Ad HocAd Hoc网络中，即使是同网络中，即使是同一个栅格内的多个节点，也还是代表了不同的移动终端，根本不一个栅格内的多个节点，也还是代表了不同的移动终端，根本不能相互代替。但在能相互代替。但在WSNWSN中，这就是一个优点，相当于用中，这就是一个优点，相当于用1 1个节点代个节点代表了表了3 3个节点，类似于层次路由中的簇头节点，但这个类似于簇个节点，类似于层次路由中的簇头节点，但这个类似于簇头的代表节点却不进行栅格内的数据融合。节点间的数据通信只头的代表节点却不进行栅格内的数据融合。节点间的数据通信只能在相邻栅格间进行，即能在

59、相邻栅格间进行，即A A栅格内的节点栅格内的节点1 1只能与只能与B B栅格内的栅格内的2 2、3 3、4 4代表节点通信，而不能直接和代表节点通信，而不能直接和C C栅格内的节点栅格内的节点5 5通信。通信。GAFGAF算法的执行过程包括两个阶段。算法的执行过程包括两个阶段。第一阶段是虚拟网格的划分。根据节点的位置信息和通信半第一阶段是虚拟网格的划分。根据节点的位置信息和通信半径，将网络区域划分成若二干虚拟网格，保证相邻单元格中的任径，将网络区域划分成若二干虚拟网格，保证相邻单元格中的任意两个节点都能够直接通信。假设节点已知整个监测区域的位置意两个节点都能够直接通信。假设节点已知整个监测区域

60、的位置信息和本身的位置信息，节点可以通过计算得知自己属于哪个网信息和本身的位置信息，节点可以通过计算得知自己属于哪个网格。格。第二阶段是虚拟网格中簇头节点的选择。节点周期性地进入第二阶段是虚拟网格中簇头节点的选择。节点周期性地进入睡眠和工作状态，从睡眠状态唤醒之后与本单元其他节点交换信睡眠和工作状态，从睡眠状态唤醒之后与本单元其他节点交换信息，以确定自己是否需要成为簇头节点。息，以确定自己是否需要成为簇头节点。每个节点处于发现每个节点处于发现(discovery)(discovery)、活动、活动(active)(active)以及睡眠以及睡眠(sleeping)3(sleeping)3种状态