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

第二章路由协议概述（什么是路由协议）路由协议负责将数据分组从源节点通过网络转发到目的节点，它主要包括两个方面的功能：寻找源节点和目的节点间的优化路径（确定最佳路径）将数据分组沿着优化路径正确转发（数据交换）

adhoc、无线局域网等传统无线网络特点adhoc、无线局域网等传统无线网络的首要目标是提供高服务质量和公平高效地利用网络带宽，这些网络路由协议的主要任务是寻找源节点到目的节点间通信延迟小的路径，同时提高整个网络的利用率，避免产生通信拥塞并均衡网络流量等，而能量消耗问题不是这类网络考虑的重点。无线传感器网络路由协议特点传感器网络具有很强的应用相关性，不同应用中的路由协议可能差别很大，没有一个通用的路由协议。此外，传感器网络的路由机制还经常与数据融合技术联系在一起，通过减少通信量而节省能量。因此，传统无线网络的路由协议不适应于无线传感器网络。在无线传感器网络中，节点能量有限且一般没有能量补充，因此路由协议需要高效利用能量，同时传感器网络节点数目往往很大，节点只能获取局部拓扑结构信息，路由协议要能在局部网络信息的基础上选择合适的路径。无线传感器网络的路由协议特点（1）能量优先。传统路由协议在选择最优路径时，很少考虑节点的能量消耗问题。而无线传感器网络中节点的能量有限，延长整个网络的生存期成为传感器网络路由协议设计的重要目标，因此需要考虑节点的能量消耗以及网络能量均衡使用的问题。（2）基于局部拓扑信息。无线传感器网络为了节省通信能量，通常采用多跳的通信模式，而节点有限的存储资源和计算资源，使得节点不能存储大量的

由信息，不能进行太复杂的路由计算。在节点只能获取局部拓扑信息和资源有限的情下，如何实现简单高效的路由机制是无线传感器网络的一个基本问题。（3）以数据为中心。传统的路由协议通常以地址作为节点的标识和路由的依据，无线传感器网络中大量节点随机部署，所关注的是监测区域的感知数据，而不是具体哪节点获取的信息，不依赖于全网惟一的标识。传感器网络通常包含多个传感器节点到数汇聚节点的数据流，按照对感知数据的需求、数据通信模式和流向等，以数据为中心成消息的转发路径。（4）应用相关。传感器网络的应用环境千差万别，数据通信模式不同，没有一个路由机制适合所有的应用，这是传感器网络应用相关性的一个体现。设计者需要针对每一个具体应用的需求，设计与之适应的特定路由机制。传感器网络路由机制要求：（1）能量高效。（2）可扩展性。（3）鲁棒性。（4）快速收敛性。路由协议分类（1）能量感知路由协议。高效利用网络能量是传感器网络路由协议的一个显著特征，早期提出的一些传感器网络路由协议往往仅考虑了能量因素。为了强调高效利用能量的重要性，在此将它们划分为能量感知路由协议。能量感知路由协议从数据传输中的能量消耗出发，讨论最优能量消耗路径以及最长网络生存期等问题。

（2）基于查询的路由协议。在诸如环境检测、战场评估等应用中，需要不断查询传感器节点采集的数据，汇聚节点（查询节点）发出任务查询命，传感器节点向查询节点报告采集的数据。在这类应用中，通信流量主要是查询节点和传感器节点之间的命令和数据传输，同时传感器节点的采样信息在传输路径上通常要进行数据融合，通过减少通信流

量来节省能量。

（3）地理位置路由协议。在诸如目标跟踪类应用中，往往需要唤醒距离跟踪目标最近的传感器节点，以得到关于目标的更精确位置等相关信息。在这类应用中，通常需要知道目的节点的精确或者大致地理位置。把节点的位置信息作为路由选择的依据，不仅能够完成节点路由功能，还可以降低系统专门维护路由协议的能耗。

（4）可靠的路由协议。无线传感器网络的某些应用对通信的服务质量有较高要求，如可靠性和实时性等。而在无线传感器网络中，链路的稳定性难以保证，通信信道质量比较低，拓扑变化比较频繁，要实现服务质量保证，需要设计相应的可靠的路由协议。能量感知路由能量路由是最早提出的传感器网路路由机制之一，它根据节点的可用能量（poweravailable，PA）或传输路径上的能量需求，选择数据的转发路径。节点可用能量就是节点当前的剩余能量。图2-1所示的网络中，大写字母表示节点，如节点A，节点右侧括号内的数字表示节点的可用能量。图中的双向线表示节点之间的通信链路，链路上的数字表示在该链路上发送数据消耗的能量。源节点是一般功能的传感器节点，完成数据采集工作。汇聚节点是数据发送的目标节点。能量路由策略主要有以下几种：

（1）最大PA路由：从数据源到汇聚节点的所有路径中选取节点PA之和最大的路径。（2）最小能量消耗路由：从数据源到汇聚节点的所有路径中选取节点耗能之和最少的路径。（3）最少跳数路由：选取从数据源到汇聚节点跳数最少的路径。（4）最大最小PA节点路由：每条路径上有多个节点，且节点的可用能量不同，从中选取每条路径中可用能量最小的节点来表示这条路径的可用能量。能量多路径路由传统网络的路由机制往往选择源节点到目的节点之间跳数最小的路径传输数据，但在无线传感器网络中，如果频繁使用同一条路径传输数据，就会造成该路径上的节点因能量消耗过快而过早失效，从而使整个网络分割成互不相连的孤立部分，减少了整个网络的生存期。为此，RahulC.Shah等人提出了一种能量多路径路由机制。该机制在源节点和目的节点之间建立多条路径，根据路径上节点的通信能量消耗以及节点的剩余能量情况，给每条路径赋予一定的选择概率，使得数据传输均衡消耗整个网络的能量，延长整个网络的生存期。能量多路径路由协议包括路径建立、数据传播和路由维护三个过程。路径建立过程是该协议的重点内容。每个节点需要知道到达目的节点的所有下一跳节点，并计算选择每个下一跳节点传输数据的概率。概率的选择是根据节点到目的节点的通信代价来计算的，在下面的描述中用Cost（Ni）表示节点i到目的节点的通信代价。因为每个节点到达目的节点的路径很多，所以这个代价值是各个路径的加权平均值。能量多路径路由的主要过程描述如下：（1）目的节点向邻居节点广播路径建立消息，启动路径建立过程。路径建立消息中包含一个代价域，表示发出该消息的节点到目的节点路径上的能量信息，初始值设置为零。（2）当节点收到邻居节点发送的路径建立消息时，相对发送该消息的邻居节点，只有当自己距源节点更近，而且距目的节点更远的情况下，才需要转发该消息，否则将丢弃该消息。（3）如果节点决定转发路径建立消息，需要计算新的代价值来替换原来的代价值。当路径建立消息从节点Ni发送到节点Nj时，该路径的通信代价值为节点i的代价值加上两个节点间的通信能量消耗，即：其中a为大于1的系统参数。（5）节点为路由表中每个下一跳节点什算选择概率，节点选择概率与能量消耗成反比。节点Ni使用如下公式计算选择节点Ni的概率：RahulCShah提出的能量多路径路由综合考虑了通信路径上的消耗能量和剩余能量，节点根据概率在路由表中选择一个节点作为路由的下一跳节点。由于这个概率是与能量相关的，可以将通信能耗分散到多条路径上，从百可实现整个网络的能量干稳降级，最大限度地延长网络的生存期。基于查询的路由定向扩散（directeddiffusion，DD）是一种基于查询的路由机制。汇聚节点通过兴趣消息（interest）发出查询任务，采用洪泛方式传播兴趣消息到整个区域或部分区域内的所有传感器节点。兴趣消息用来表示查询的任务，表达网络用户对监测区域内感兴趣的信

息，例如监测区域内的温度、湿度和光照等环境信息。在兴趣消息的传播过程中，协议逐跳地在每个传感器节点上建立反向的从数据源到汇聚节点的数据传输梯度（gradient）。传感器节点将采集到的数据沿着梯度方向传送到汇聚节点。定向扩散路由机制可以分为周期性的兴趣扩散、梯度建立以及路径加强三个阶段。图2-2显示了这三个阶段的数据传播路径和方向。DD协议内容：节点用一组<属性，值>来命名它所生成的数据。1.建立路由时，sink(汇聚节点）flooding(广播）包含属性列表、上报间隔、持续时间、地理区域等信息的查询请求Interest（该过程本质上是设置一个监测任务，通过分配不同属性值来表示不同任务的描述符）。2.每个传感器节点在收到嗜好（Interest）后保存在各自的Cache中。每个嗜好项(interestentry)包含一个时间标签域(timestampfield)和若干个梯度域(gradientfield，按成本最小化和能量自适应原则引导数据扩散的方向)。3.当一个嗜好传遍整个网络后，从源节点(即嗜好所在区域的传感器节点)到sink节点或基站之间的梯度就建立起来了。4.一旦源节点采集到嗜好所需的数据，那么源节点沿着该嗜好的梯度路径传输数据到sink节点或基站。其中，源节点采集的数据首先在本地采用数据融合技术进行整合，然后在网上传输。右图描述DD路由协议的工作原理在DirectedDiffusion中，可以对路径进行修复。在建立多条数据源到Sink节点的路径之后，(探测梯度)Sink节点可以选择增强其中的一条路径用于数据的传输，而同时保持另外一条低速数据传输的路径（数据梯度）。当高速路径，也就是经过增强的路径出现故障时，Sink节点可以增强低速路径，保证源节点到Sink节点的数据传输。虽然保持低速路径的过程需要消耗一些能量，但是在故障时，可以节省很多能量开销。对于故障比较频繁的网络，保持一条低速路径是很有好处的。DD路由协议的优点：1.采用多路径,健壮性好;2.节点只需要和邻居节点通信，因而不需要全局的地址机制，使用查询驱动机制按需建立路由,避免了保存全网信息；3.每个节点都可以进行数据融合操作，能减少数据通信量，节省能量消耗；4.sink点根据实际情况采取增强或减弱方式能有效利用能量；5.节点不需要维护网络的拓扑结构，数据的发送是基于需求的，因此它是一个非常节能的路由协议。DD路由协议的缺点：1.基于查询驱动模型的，不适用于环境监测的WSN；2.Gradient的建立开销很大,不适合多sink点网络；3.数据聚合过程采用时间同步技术,会带来较大开销和时延；4.不同的应用中需要定义不同的命名方案，也就是<属性，值>对，从而限制了它的应用。Rumor路由协议（谣传路由）：RumorRouting是在DirectedDiffusion的基础上演化而来的。通常情况下，DirectedDiffusion协议需要向整个网络广播兴趣，而在某些应用中，只有少量的数据需要从源节点传递到Sink节点。在这种情况下，没有必要向整个网络广播兴趣。当WSN中的事件（对应着数据的传递）数量很少，而查询（对应着兴趣的广播）数量很多的时候，可以采用广播事件的方法，以节省能量的消耗。RumorRouting是一个介于事件广播（向整个网络广播事件）和兴趣广播（向整个网络广播兴趣）之间的一种路由协议RumorRouting核心思想：1.借鉴了欧氏平面图上任意两条曲线交叉几率很大的思想2.当节点监测到事件后将其保存，并创建称为Agent的生命周期较长的包括事件和源节点信息的数据包，将其按一条或多条随机路径在网络中转发3.收到Agent的节点根据事件和源节点信息建立反向路径，并将Agent再次随机发送到相邻节点，并可在再次发送前在Agent中增加其已知的事件信息4.sink点的查询请求也沿着一条随机路径转发,当两路径交叉时则路由建立5.如不交叉,sink点可flooding查询请求

Rumor协议中Agent传播和Agent路径与查询路径的交叉在多sink点、查询请求数目很大、网络事件很少的情况下，Rumor协议较为有效.但如果事件非常多,维护事件表和收发Agent带来的开销会很大。地理位置路由在传感器网络中，节点通常需要获取它的位置信息，这样它采集的数据才有意义。如在森林防火的应用中，消防人员不仅要知道森林中发生火灾事件，而且还要知道火灾的具体位置。地理位置路由假设节点知道自己的地理位置信息，以及目的节点或者目的区域的地理位置，利用这些地理位置信息作为路由选择的依据，节点按照一定策略转发数据到目的节点。地理位置的精确度和代价相关，在不同的应用中会选择不同精确度的位置信息来实现数据的路由转发。GEAR：GEAR路由协议

GeographicandEnergyAwareRoutingGEAR：GEAR路由协议

GeographicandEnergyAwareRouting应用建立到特定区域的路由查询工作方式前提已知目标区域的位置信息节点知道自己位置信息和剩余能量节点间无线链路是对称的GEAR路由过程

分两个阶段：查询消息到达目的区域的路径查询消息在目标区域的传播选路依据节点到查询区域通信能量能耗节点本身的剩余能量最小代价节点为转发节点GEAR路由过程GEAR路由过程查询在监测区域内传送：洪泛方式，迭代地理转发将目标区域分解为若干子区域、向子区域的中心位置转发GEM路由

GEM（graphembedding）路由是一种适用于数据中心存储方式的地理路由。传感器网络存储监测数据方式本地存储（localstorage）外部存储（externalstorage）数据中心存储（data-centricstorage）本地存储方式在本地存储方式中，节点首先将监测数据保存在本地存储器中，并在收到查询命令后，将相关数据发送给汇聚节点。本地存储方式中，网络传输的数据都是汇聚节点感兴趣的数据，网络传输效率高，但是需要每个节点都具有相对较大的存储空间，数据融合只能在传输过程中进行，并且汇聚节点需要经过较长的延迟后才能获得查询数据。外部存储方式在外部存储方式下，节点在获得监测数据后，不论汇聚节点目前是否对该数据感兴趣，都主动地把数据发送给汇聚节点。外部存储方式中，节点将采集数据及时传输给汇聚节点，可以提高传感器网络对突发事件的反应速度，但是监测数据不断发送给汇聚节点，一方面由于有些数据不是汇聚节点感兴趣的，造成了网络能量的浪费；另一方面容易使得汇聚节点附近形成网络热点，降低传感器网络的吞吐率。数据中心存储方式在数据中心存储方式下，首先对可能的监测事件进行命名，然后按照一定的策略将每一个事件映射到一个地理位置上，距离这个位置最近的节点作为该事件的负责节点。节点在监测到事件后，把相关数据发送到映射位置。负责节点接收数据，进行数据融合并存储在本地。数据中心存储方式在网络中选择不同的负责节点实现不同事件监测数据的融合和存储，是介于本地存储和外部存储的之间的一种方式，在查询延迟、能量消耗和存储空间等多项指标间进行折中。由于传感器网络处理的事件往往有多种，数据中心存储方式能够将网络通信流量、处理流量和存储流量在网络中均匀分摊，从而有效避免了网络热点的产生。GEM路由GEM（graphembedding）路由是一种适用于数据中心存储方式的地理路由。GEM路由的基本思想是建立一个虚拟极坐标系统（virtualpolarcoordinatesystem，VPCS），用来表示实际的网络拓扑结构。网络中的节点形成一个以汇聚节点为根的带环树（ringedree），每个节点用到树根的跳数距离和角度范围来表示，节点间的数据路由通过这个带环树实现。虚拟极坐标系统第一步：生成树型结构。第二步：反馈子树大小。第三步：确定虚拟角度范围。对网络拓扑变化的适应除了汇聚节点外每个节点只有一个父节点；每个节点的跳数值为父节点的跳数值加1；每个节点的角度范围是父节点的角度范围的子集；每个节点的子节点角度范围不相交。基于虚拟极坐标系统的路由算法边界定位的地理路由在传感器网络的实际应用中，如果每个节点都需要知道自己的精确位置信息，那么路由代价比较大。地理位置路由研究中的一个重要方向就是如何在保证路由正确性的前提下，尽量减少需要精确位置信息的节点数目，以及路由机制对节点精确位置信息的依赖。文献［13］提出了一种只需要少数节点精确位置信息就可以进行正确路由的地理路由机制。其基本思想是首先通过网络中知道自身位置信息的节点确定一个全局坐标系，然后确定其他节点在这个坐标系中的位置，最后根据节点在坐标系中的位置进行数据路由。知道自身位置信息的节点通常是网络中较为特殊的信标节点。当所有节点的坐标位置信息确定后，协议使用贪婪算法选择路由。因此，协议的关键部分是利用信标节点确定全局坐标系以及确定其他节点在坐标系中的位置。文献［13］给出了下面三种策略。边界节点均为信标节点

使用两个信标节点

在边界节点均为信标节点策略中,仍然需要网络边界上所有节点都知道自己的精确地理位置,网络部署的成本仍然很高。本策略只使用两个信标节点,而不再需要所有边界节点的精确位置信息,从而大大减少了网络部署的成本。在该策略中,仍然将节点分为边界节点和非边界节点。边界节点只知道自己处于网络的边缘,但不知道自己的精确位置信息。该策略首先通过边界节点间的信息交换机制建立全局坐标系,然后引入两个beacon节点以减少全局坐标系的误差,最后按照前述方法计算非边界节点在全局坐标系中的位置。使用一个信标节点

上述策略中假设节点知道自己是边界节点,实际网络中节点的部署具有随机性,不能确定自己是否为实际的网络边界节点。本策略利用一个信标节点确定一组边界节点,然后采用上面第二种策略介绍的算法确定全局坐标系并计算节点在坐标系中的位置信息。特点

与GEAR路由相比,边界定位的路由机制只需要很少节点知道精确的位置信息,减少了对传感器节点的功能要求,降低了传感器网络的部署成本。但为了确定全局坐标系和节点在坐标系中的位置信息,节点需要进行大量的信息交换,通信开销很大。此外,由于算法采用了迭代过程确定节点的位置,计算出的节点位置精度和迭代次数相关。与GEM路由相比,边界定位路由建立的全局坐标系更加接近节点实际位置,且对于网络拓扑的变化调整比较简单。可靠路由协议

某些传感器网络应用对于数据传输的可靠性提出了比较高的要求,因此传感器网络路由中的一个重要方面是研究可靠路由协议。传感器节点由于有限能量供应和工作环境恶劣经常面临失效问题,这为研究适合于传感器网络的可靠路由协议增加了困难。目前,研究人员提出的可靠路由协议主要从两个方面考虑:一是利用节点的冗余性提供多条路径以保证通信可靠性;二是建立对传输可靠性的估计机制,从而保证每跳传输的可靠性。另外,某些传感器网络应用需要节点间通信具有一定的实时性。基于不相交路径的多路径路由机制

在传感器网络中,引入多路径路由是为了提高数据传输的可靠性和实现网络负载平衡。在多路径路由中,如何建立数据源节点到汇聚节点的多条路径是首要问题。在定向扩散路由中,当有数据查询需要时,汇聚节点首先通过洪泛兴趣消息形成传输梯度,然后建立数据源节点到汇聚节点的多条路径,最后通过路径加强消息选择一条主路径传输数据。当主路径失败时,定向扩散路由需要使用周期性低速率的洪泛过程重新建立主路径。局部不相交路径的构建缠绕多路径

ReInForM路由

在传感器网络中,传感器节点是数据源,把监测数据发送给汇聚节点。ReInForM(ReliableInformationForwardingusingMultiplepaths)路由从数据源节点开始,考虑可靠性需求、信道质量以及传感器节点到汇聚节点的跳数,决定需要的传输路径数目,以及下一跳节点数目和相应的节点,实现满足可靠要求的数据传输。SPEED协议

在有些传感器网络应用中,汇聚节点需要根据采集数据实时作出反应,因此传感器节点到汇聚节点的数据通道要保持一定的传输速率。SPEED协议[33]是一个实时路由协议,在一定程度上实现了端到端的传输速率保证、网络拥塞控制以及负载平衡机制。为实现上述目标,SPEED协议首先交换节点的传输延迟,以得到网络负载情况;然后节点利用局部地理信息和传输速率信息作出路由决定,同时通过邻居反馈机制保证网络传输速率在一个全局定义的传输速率阈值之上。节点还通过反向压力路由变更机制避开延迟太大的链路和路由空洞。SPEED协议框架(1)延迟估计机制,用来得到网络的负载情况,判断网络是否发生拥塞;(2)SNGF算法(statelessnon-deterministicgeographicforwarding,SNGF),用来选择满足传输速率要求的下一跳节点;(3)邻居反馈策略(neighborhoodfeedbackloop,NFL),是当SNGF路由算法中找不到满足传输速率要求的下一跳节点时采取的补偿机制;(4)反向压力路由变更机制,用来避免拥塞和路由空洞。.延迟估计

在SPEED协议中,节点记录到邻居节点的通信延迟,用来表示网络局部的通信负载。这里的通信延迟主要是指发送延迟,而忽略传输延迟。在带宽有限的网络条件下,如果用专门分组探测节点间的通信延迟,开销比较大。SPEED协议采用数据包捎带的方法,得到节点之间的通信延迟,具体过程如下:发送节点给数据分组加上时间戳;接收节点计算从收到数据分组到发出ACK的时间间隔,并将其作为一个字段加入ACK报文;发送节点收到ACK后,从收发时间差中减去接收节点的处理时间,得到一跳的通信延迟。在更新记录的延迟值时,综合考虑新计算的延迟值和原来记录的延迟值,更新的延迟值是二者的指数加权平均(exponentialweightedmovingaverage,EWMA)。节点将计算出的通信延迟通告邻居节点。假设节点A计算出到节点B的通信延迟,并将这个通信延迟通告其邻居节点C,则C可以不必计算到节点B的通信延迟,而使用A发送来的通信延迟直接与节点B通信。SNGF算法

节点将邻居节点分为两类:比自己距离目标区域更近的节点和比自己距离目标区域更远的节点。前者称为候选转发节点集合(forwardingcandidateset,FCS)。节点计算到其FCS集合中的每个节点的传输速率。传输速率定义为节点间的距离除以节点间通信延迟。SNGF算法

如果节点的FCS集合为空,意味着分组走到了路由空洞中。这时节点将丢弃分组,并使用下一节介绍的反向压力信标(backpressurebeacon)消息通告上一跳节点,以避免分组再走到这个路由空洞中。SNGF算法根据传输速率是否满足预定的传输速率阈值,FCS集合中的节点又分为两类:大于速率阈值的邻居节点和小于速率阈值的邻居节点。若FCS集合中有节点的传输速率大于速率阈值,则在这些节点中按照一定的概率分布选择下一跳节点,节点的传输速率越大,被选中的概率越大;若FCS集合内所有节点传输速率都小于速率阈值,则使用下一节介绍的NFL算法计算一个转发概率,并按照这个概率转发分组。如果决定转发分组,FCS集合内的节点按照一定的概率分布选择为下一跳节点。反馈机制

为了保证节点间的数据传输满足一定的传输速率要求,引入邻居反馈环机制NFL。在邻居反馈环机制中,数据丢失和低于传输速率阈值的传送都视作传输差错。邻居反馈环机制如图2-12所示。反