无线传感器网络路由协议(上)

无线传感器网络路由协议的目的是将分组从源节点(通常为传感节点)发送到目的节点(通常为汇聚节点)，只要完成两大功能：一是选择适合的优化路径，一是沿着选定的路径正确转发数据。尽管传统的无线局域网络或者移动Ad hoc网络基于提高服务质量Qos和公平性提出了很多路由协议，但这些协议的主要任务不是考虑网络能量消耗，而是追求端到端的延迟最小，网络利用率最高以及避免通信拥塞和均衡网络流量的最优路径。而无线传感器网络节点又具有能量限制，且考虑网络节点数目通常很大，节点只能获取局部拓扑信息来构建路由，再加上无线传感器网络较强的应用相关性和考虑到数据的融合处理，因此不仅传统无线网络路由协议不再适合，而且也很难设计一个适合无线传感器网络的通用路由协议。其中，无线传感器网络路由协议设计的一个主要目标就是在执行数据通信功能前提下尽可能延长网络的寿命，并通过积极的能量管理技术避免网络连接性因节点能量不足而造成的恶化。

针对无线传感器网络的特点，为了实现有效的通信，传感器网络路由协议应面临和克服一些设计问题和技术挑战。

    ①保证精度前提下的能耗问题。由于通常无线传感器网络节点数量较大，这种无线环境下为了确保监测或跟踪定位精度等，部分节点可以用光所有能量来执行计算和传输信息的任务，但由于节点采用有限能量电池供能，当一些节点电池寿命终结后直接导致网络拓扑发生变化，从而要求网络的重新组织和重新路由数据分组信息。

②网络节点的配置。无线传感器网络节点的配置是依赖于应用且影响网络路由协议的性能。通常配置有两种方式：确定配置和随机分布两种。前一种方式下传感器节点是通过人工布置的，且数据是通过预先定义的路径传播的。然而，在随机配置情况下，节点随机分布，通过Ad Hoc自组织方式建立基础通信设施。如果随机产生的节点分布不均匀，如要考虑网络连接性和有效节能运作的话，则很有必要采用优化分簇的策略。由于能量和带宽的限制，传感器节点间的通信通常都在较短的通信传输距离之内。因此，一条路由很可能包括多跳组成。

③以数据为中心的数据报告模型。无线传感器网络数据发送和报告依赖于应用和时间响应特性。数据报告模型可分为时间驱动、事件驱动、查询驱动和混合驱动四种。时间驱动模型适合于需要周期数据监控的应用。正因为如此，节点需要周期切换它们的感应和发射模块，以固定时间周期间隔来感知环境和发送需要的数据。对于事件驱动和查询模型，当某种事件发生或基站发起查询，节点会立即响应感知属性值的大的突发变化，因而比较适合时刻紧急应用。上述几种模型的组合就构成了混合模型。数据报告模型严重影响路由协议的路由稳定性和能耗。

④节点或链路的异构性。通常很多研究中，都假定传感器节点是同构的，如在计算、通信和能量都是相同的容量。然后，由于应用的不同，传感器节点可能担当不同的角色和执行不同的功能。异构传感器的存在提出了很多与数据路由相关的难题，如一些应用可能需要多种混合的传感器来监测温度、压力和周围环境的湿度，利用声音信号监测移动性，捕获移动物体的视频或图像等。另外，特殊的传感器要么独立配置，要么同一传感器集成了不同的功能。及时数据采集或报告由于多种服务质量需求都可能以不同速率传输，而且可能遵循多种数据报告模型。如分级协议就指定了不同于一般感应节点的簇头节点，从配置的节点中选出的簇头可能在能量、带宽和存储能力方面都比其他传感器节点功能更强大些。

⑤容错能力和鲁棒性。一些节点可能会由于能量用尽、物理损坏或环境干扰等因素造成故障或失效。节点失效不应当影响网络总的任务的执行。如果很多节点都失效了，则MAC和路由协议必须保证新的链路产生，并且将数据路由到数据采集基站。这可能要求节点主动调节发送功率和信号速率以减少能耗，或者通过网络能量更充足的区域重新路由分组。因此，在一个要求有容错能力和鲁棒性的无线传感器网络中有必要考虑多层次的冗余配置。

⑥网络动态和扩展性。尽管大多数传感器网络应用都是假定节点为静止的，仍然存在很多应用要考虑感应节点或基站的移动性。来自于移动节点的路由消息更具有挑战性，因为路由的稳定性直接影响路由消息的可靠传输。另外，感应现象也可能是动态的或者静态的，取决于具体应用，如动态目标跟踪和静态森林火灾预警监测等。对于不同感应现象路由协议设计时可以采用按需或主动模式的事件报告机制。由于监测区域范围或节点密度不同，配置的网络规模大小也不同，路由协议还必须适应在大量节点参与的环境条件下的正常工作。节点加入或撤出以及节点的移动，都会使网络拓扑发生变化，这就要求路由机制具有扩展性，能够适应网络结构的变化。

⑦路由相关的传输介质问题。通常，传感器网络数据业务要求的带宽较低，大致在1～100kbps数量级。设计路由时应当考虑下面的(如IEEE802.11)MAC层协议设计，一般来说，基于TDMA机制的协议相比基于竞争的CSMA机制的协议要更节能一些，如蓝牙技术。

⑧连接性和覆盖问题。通常传感器网络配置较高的节点密度以增强节点间的强连接性，尽管如此，由于节点故障或失效，整个网络拓扑的变化或网络规模大小不可避免要发生变化，从而影响原有的连接性，并且网络连接性跟节点分布(有可能是随机分布的)有关。此外，由于感应距离和精度的局限，无线传感器网络中每个节点感知的环境视图(View)都有限，因为它们只覆盖了有限的物理环境区域。因此，物理配置区域也是路由协议应该考虑的一个至关重要的因素。

⑨数据汇聚或融合问题。由于传感器网络节点产生大量冗余数据，多个类似的分组可以汇聚以便减少传输分组的数量。所谓数据汇聚就是根据某种汇聚功能，如双倍压缩、取最小化和最大化以及平均等处理，将不同源节点发来数据进行综合。数据融合通常是指采用信号处理方法，如利用波束形成技术综合接收的各种信号以减少信号的噪声，来产生一个更精确的信号。大量的无线传感器网络路由协议都采用了数据汇聚或融合技术来实现有效节能和数据传输优化的目标。

⑩面向应用和服务质量(Qos)。无线传感器网络应用环境千差万别，需要针对每一应用的具体要求设计相应的路由协议。服务质量问题，如一些时间受限的应用要求数据传输必须有限定的延迟。然而某些应用，考虑能量的节省(因为关系到网络的寿命)比数据传输质量更为重要。为了减少能耗和延迟网络寿命，不得不降低对传输数据质量的要求。

⑾算法的快速收敛性。由于网络拓扑的动态变化，节点能量和通信带宽资源的限制，因此要求路由协议算法能够快速收敛，以适应拓扑的动态变化，减少通信协议的开销，提高消息传输的效率。

1  路由协议分类

本节总结了无线传感器网络路由协议的现状，目前已有的分类方式如图3-10所示。如按照网络结构来分，路由协议可以分为基于平面的、基于分级的和基于位置的路由协议三大类。基于平面的路由协议，所有节点通常都具有相同的功能和对等的角色。而基于分级的路由节点通常扮演不同的角色。基于位置的路由，网络节点利用传感器节点的位置来路由数据。如果说路由协议对于当前网络条件或现有的能量状况是自适应的话，当且仅当系统某个参数是可控的。因基于位置路由书中后面章节专门详细讲解，这里只将平面路由和分级路由的特点做了一个宏观的比较，见表3-2，以便读者更清晰地理解这两种分类的特点。




此外，针对不同传感器网络应用，研究人员也提出了许多不同的路由协议，大体可分为基于多径和能量感知的路由、基于可靠的路由、基于查询的路由、基于协商的路由、基于QoS的路由和基于位置的路由等。除了上面分类外，像传统的无线Ad hoc网络和无线Mesh网络，无线传感器网络的路由协议还可分为主动的、按需的和混合的路由协议。还有一类特殊的路由协议叫协作路由(有的也叫基于相干的路由协议)，即节点发送数据到某个中心节点，在那儿进行数据汇聚和融合，因而可降低路由在能耗上面的代价。还有很多其他路由协议是依赖于时间和位置信息的。下面重点讲述几类传感器网络典型应用的路由协议。

2  基于多径的能量感知路由

能量感知就是根据节点的可用能量(即节点的当前剩余能量)或传输路径上的能量需求，选择数据转发的路径。能量感知路由策略主要有以下几种。

    ① 最大剩余节点能量路由。从数据源节点到汇聚节点的所有路径中选取节点剩余能量之和最大的路径。

② 最小能耗路由。从数据源节点到汇聚节点的所有路径中选取节点能耗之和最小的路径。

③ 最少跳数路由。从数据源节点到汇聚节点的所有路径中选取跳数最少的路径。

④ 最大最小剩余节点能量路由。每条路径上有多个节点，且节点的可用剩余能量不同，从中选取每条路径中可用能量最小的节点来表示这条路径的可用能量。

    上述能量感知路由算法策略需要节点掌握整个网络的全局信息，然而多数传感器网络节点只能获取局部信息，因此这些方法只能在理想情况下讨论。

传统网路的路由机制通常选择源节点到目的节点的最小跳数单径路由传输数据，但在无线传感器网络中，频繁使用同一条路径传输数据容易导致该路径上节点能耗过快而提前失效，从而整个网络分割成互不连接的孤立网络，造成网络寿命缩短。C.Rahul等人提出了基于多径的能量感知路由算法。该算法在源节点和目的节点建立了多条路径，根据路径上节点通信能耗和剩余能量状况给每条路径赋予一定选择概率，由于该概率与能量相关，可将通信能耗分散到多条路径上，从而使得数据传输可以均衡消耗整个网络的能量，最大限度延长网络的使用寿命。该多径能量感知路由协议包括三个阶段：路由建立阶段、数据通信或数据传播阶段和路由维护阶段。每个节点都知道到达目的节点的所有下一跳节点，需要计算选择每个下一跳节点传输数据的概率，该概率与节点能量通信代价的倒数成正比。概率的计算是通过节点到目的节点的通信代价来估算的。由于存在多径，所以该代价值应当是各个路径的加权平均值，用符号Cost(Ni)来表示节点i到目的节点的通信代价。该协议过程如下：   

    ① 目的节点广播路径请求消息，启动路径建立过程。其中，路径请求消息包含一个代价域，初值设为0，即Cost(ND)=0，表示发出该消息的节点到目的节点的路径上的能量消息。

② 当节点收到邻居节点发送的路径请求消息时，和该邻居节点相比，仅当自己距离源节点更近，且距目的节点更远情况下才需转发该请求，如式(3-3)，否则丢弃该请求消息。


③ 当节点准备转发路径请求消息时，需计算新的代价值以更新旧的值。如路由请求消息从节点Ni到Nj时，路径的通信代价为原节点Ni的代价加上两节点间的通信能耗，即

式中，CNi，Nj表示发送的数据经由节点Ni到目的节点的通信代价；Econsumed(Ni，Nj)表示节点Ni和Nj之间的能耗，其计算公式为


式中，eijα表示节点Ni到Nj之间的直接通信能耗，包括发送部分Etx和接收部分Erx，即eijα=Etx+Erx；Riβ表示节点Ni的剩余能量所占比例，即


。该度量准则同时考虑了邻居缓存数据的信息、节点的能量再生率和数据的相关性。

④节点丢弃通信代价高的路径，仅当邻居节点Ni更低代价的路径才会加入到节点Nj的转发路由表中FTj的条件是：

⑤ 节点Nj会为转发路由表中每个邻居Ni指定一个概率，该概率与通信代价成反比：

        ⑥ 每个节点Nj都由大量邻居数路由分组到目的地，Nj然后通过转发路由表中的邻居计算到达目的节点的平均通信代价，并更新原有消息中的代价值，然后向邻居节点广播该路由建立请求消息：


⑦平均代价Cost(Nj)在路由请求分组的代价域里设置，正如步骤②，并随着请求分组一路沿着向着源节点处的路径转发。

该协议在数据通信阶段，对于每个收到的分组，节点根据概率选择一个下一跳节点，并将分组转发给该节点。路由维护阶段是通过节点周期性从目的节点到源节点实施泛洪查询来维持所有路径的有效性。
3  基于查询路由

基于查询的路由通常是指目的节点通过网络传播一个来自某个节点数据查询消息(感应任务)，收到该查询数据消息的节点又将匹配该查询消息的数据发回给原来的节点。一般这些查询是以自然语言或者高级语言来描述的。

定向扩散(Directed Diffusion)就是一种基于查询的路由协议。基站节点或者汇聚节点发送兴趣消息(Interest Message)执行查询任务，通过泛洪方式传播消息给所有传感器节点。随着兴趣消息在整个网络传播，协议逐跳地在每个传感器节点上建立反向的从数据源节点到基站或汇聚节点的传输梯度。当源节点有感兴趣的数据时，就沿着兴趣消息梯度方向发送数据到基站或汇聚节点。定向扩散协议分为三个阶段：周期性的兴趣消息扩散阶段、传输梯度建立阶段和发送数据和路径加强阶段。如图3-11所示展示了定向扩散路由机制一个样例示意图。

    1．兴趣消息扩散阶段

基站或汇聚节点周期性地向周围邻居广播兴趣消息。消息中含有一些重要参数，如数据发送速率、任务类型、目标区域以及时戳等。每个节点都在本地保存一个兴趣列表，其中专门存在一个表项用来记录发送该兴趣消息的邻居节点、数据发送速率和时戳等相关信息，以建立该节点向汇聚或基站节点传输数据的梯度关系。每个兴趣消息可能对应多个邻居节点，每个邻居节点对应一个梯度信息。另外，该表项还存在一个字段用来表示该表项的有效时间，超过该时间，节点就删除该表项。当收到邻居节点发送的兴趣消息时，首先检查兴趣列表中是否存在参数类型与收到兴趣相同的表项，如果有，就更新表项有效时间值；如果仅仅是参数类型相同，但不包含发送该消息的邻居节点，就在对应表项中添加该邻居节点；对于其他情况，都需建立一个新表项来记录这个新的兴趣，如收到的兴趣消息和刚刚转发的一样，则丢弃该信息，以免消息循环，否则，就转发收到的兴趣消息。

2．传输梯度建立阶段

当源节点采集到的数据与执行查询任务的兴趣消息匹配时，就将其发送到梯度方向上的邻居节点，并按梯度上的数据传输速率设定相应的数据采集速率。由于传播兴趣消息是采用的广播机制，故基站或者汇聚节点可能会收到经过多个路径的相同数据。对于中间节点，如收到转发的数据时，首先检查兴趣列表的表项，如没有匹配项就丢弃该数据。如果有，则检查与该兴趣消息对应的数据缓存(Data Cache)。如缓存里面存在与接收数据相匹配的，表明已经转发过该数据，并将其丢弃；否则，再检查表项中的邻居信息。如记录的邻居节点发送速率超过接收的数据速率，就全部转发接收的数据；否则，按照比例转发。转发的数据都会在缓存中保留一个备份，且记录转发时间。

3．发送数据和路径加强阶段

当通过前面的兴趣扩散阶段，源节点到基站或汇聚节点的数据传输基本路径建立起来。然后，源节点以较低速率采集和发送数据以建立梯度，不过此时建立的梯度称为探测梯度(Probe Gradient)。当基站或汇聚节点收到源节点发来的数据后，立刻启动建立到源节点的加强路径，随后数据沿着加强路径以较高速率传输数据。加强后的梯度称为数据梯度(Data Gradient)或数据传播梯度。

路径加强优化的原理就是，当邻居节点收到路径加强消息(包含新设定的较高发送数据速率)时，如判断该消息是一个已有的兴趣，仅仅是增加了数据发送速率的话，就确定这是一跳路径加强消息，从而更新相应兴趣表项到邻居节点的数据发送速率。依次类推，采用同样方法选择加强路径的下一跳邻居节点。为了达到更低的能耗，在加强路径上面有必要采用数据汇聚方法进一步处理数据(如加倍压缩等)。值得注意的是路径加强标准有很多，如数据传输延迟、数据转发的业务流量以及数据传输的稳定性等。如果标准选得不同，可能对该协议性能带来显著的影响。

定向扩散路由协议是一种典型的以数据为中心的查询路由。为了适应拓扑和节点失效等网络状态变化，定向扩散路由协议采用了周期性的兴趣消息扩散、建立数据传输梯度和发送数据及加强路径三个阶段的策略。然而不足的是，路径建立时的兴趣消息扩散要执行一个泛洪广播操作，时间和能量开销较大，特别是当底层的MAC协议采用睡眠机制时可能造成兴趣消息建立的不一致。

另外一种基于查询的路由协议叫谣传路由(Rumor Routing)，是D.Braginsky等人提出的适用于数据传输量较小的无线传感器网络高效路由协议。在某些特定的应用场合，传感器节点采集或传输的数据量很少或者并不知道事件发生的区域，如果采用定向扩散路由机制，并不能实现高效路由的目的。而谣传路由由于采用了查询消息的单播随机转发机制，克服了泛洪广播消息建立转发路径带来大量路由开销的问题。该协议基本思想就是事件监测区域的感应节点产生代理消息(Agent)，代理消息沿着随机路径向邻居节点扩散传播，如图3-12所示。与此同时，基站或汇聚节点发送的查询消息也沿随机路径在网络中传播。当查询消息和代理消息的传播路径交叉在一起时，就会形成一条基站或汇聚节点到事件监测区域的完整路径。实质上谣传协议就是通过使用一系列生存期较长的代理(Long-lived Agents)来产生直接到达事件监测区域的路由路径。

下面详细介绍一下谣传路由协议的基本过程。

    ① 每个节点维护两个列表：邻居列表和事件列表。其中事件列表中每项都记录着事件相关的信息，包括事件名称、到事件区域的跳数和到事件区域的下一跳邻居等信息。当传感器节点在本地监测到一个事件发生时，就在事件列表中添加一个表项，并设置相应的事件名称和跳数等信息，同时根据一定的概率产生一个代理消息。

② 代理是指包含生存期等事件相关信息的分组，用来将携带的本地事件信息传播给它经过的每一个传感器节点，另外还有执行汇聚事件的功能。对于收到代理的节点，首先检查事件列表中是否有相关事件的表项。如存在相关表项就比较代理和表项中的跳数值，当代理中跳数小时，就更新表项中的跳数值，否则就更新代理中的跳数值。如事件列表中不存在该事件相关表项，就增加一个表项来记录代理消息携带的事件信息。然后，节点将代理中的生存期值减1，并在网络中随机选择邻居节点转发该代理，直到其生存期值减小为零。通过代理在其生存期传播过程，逐渐形成一段到达事件发生区域的路径。网络中任何节点都可产生一个对特定事件的查询消息。如果节点事件列表中存有该事件相关表项，表明节点处于到达事件区域的路径上，查询消息就可沿着该路径转发，否则节点随机选择邻居节点转发查询消息。与此类似原理，中间节点继续转发查询消息，并记录查询消息中的相关消息，从而形成了查询消息的路径。同样，查询消息也具有生存期，以避免环路问题。

③ 当代理与查询消息交叉时，交叉节点会沿着查询消息的反向路径将事件消息传送到查询节点。如查询节点在一段时期内没有收到事件消息，就认为查询消息没有到达事件区域，可选择重传或泛洪查询及放弃等方法，泛洪方法代价较高，一般不要轻易采用。

相比定向扩散路由，谣传路由协议最大的贡献就是减少了路由建立的开销。但由于采用随机方式产生的路由路径不一定是数据传输的最优路由，其中最优参数严重依赖于拓扑，并且可能产生环路路由问题。下面给出了谣传路由算法的主要伪代码，见表3-3。