无线网路由协议分类概述v12.doc

无线网路由协议分类概述版本时间描述作者v1.22010-07-24初稿王陈浩1路由概述1.1传统路由概述1.1.1基本概念路由：是把信息从源穿过网络传递到目的地的行为，就是指导IP数据包发送的路径信息。路由器：提供了异构网互联的机制，实现将一个网络的数据包发送到另一个网络。路由协议：就是在路由指导IP数据包发送过程中事先约定好的规定和标准。可路由协议：是定义数据包内各个字段的格式和用途的网络层封装协议，该网络层协议允许将数据包从一个网络设备转发到另一个网络设备。路由表：路由器或者其他互联网网络设备上存储的表，该表中存有到达特定网络终端的路径在某些情况下，还有一些与这些路径相关的度量。网络拓扑结构：指用传输媒体互连各种设备的物理布局，就是用什么方式把网络中的计算机等设备连接起来。拓扑图给出网络服务器、工作站的网络配置和相互间的连接，它的结构主要有星型结构、环型结构、总线结构、分布式结构、树型结构、网状结构、蜂窝状结构以及它们的混合拓扑结构等。网关：在采用不同体系结构或协议的网络之间进行互通时，用于提供协议转换、路由选择数据交换等网络兼容功能的设施。metric：路由算法用以确定到达目的地的最佳路径的计量标准如路径长度、可靠性、路由延迟等。具体来说，路由协议通过在路由器之间共享路由信息来支持可路由协议。路由信息在相邻路由器之间传递，确保所有路由器知道到其它路由器的路径。总之，路由协议创建了路由表，描述了网络拓扑结构；路由协议与路由协同工作，执行路由选择和数据包转发功能。1.1.2传统路由分类路由分为静态路由和动态路由，其相应的路由表称为静态路由表和动态路由表。静态路由表由网络管理员在系统安装时根据网络的配置情况预先设定，网络结构发生变化后由网络管理员手工修改路由表。动态路由随网络运行情况的变化而变化，路由器根据路由协议提供的功能自动计算数据传输的最佳路径，由此得到动态路由表。静态路由静态路由表在开始选择路由之前就被网络管理员建立，并且只能由网络管理员更改，所以只适于网络传输状态比较简单的环境。静态路由具有以下特点： 静态路由无需进行路由交换，因此节省网络的带宽、CPU的利用率和路由器的内存。 静态路由具有更高的安全性。在使用静态路由的网络中，所有要连到网络上的路由器都需在邻接路由器上设置其相应的路由。因此，在某种程度上提高了网络的安全性。 有的情况下必须使用静态路由，如DDR、使用NAT技术的网络环境。 静态路由也有以下局限性： 管理者必须真正理解网络的拓扑并正确配置路由。 网络的扩展性能差。如果要在网络上增加一个网络，管理者必须在所有路由器上加一条路由。 配置烦琐，特别是当需要跨越几台路由器通信时，其路由配置更为复杂。 动态路由根据路由算法，动态路由协议可分为距离向量路由协议（Distance Vector Routing Protocol）和链路状态路由协议（Link State Routing Protocol）。距离向量路由协议基于Bellman-Ford算法，主要有RIP、IGRP（IGRP为 Cisco公司的私有协议）；链路状态路由协议基于图论中非常著名的Dijkstra算法，即最短优先路径（Shortest Path First， SPF）算法，如OSPF。在距离向量路由协议中，路由器将部分或全部的路由表传递给与其相邻的路由器；而在链路状态路由协议中，路由器将链路状态信息传递给在同一区域内的所有路由器。根据路由器在自治系统（AS）中的位置，可将路由协议分为内部网关协议（Interior Gateway Protocol，IGP）和外部网关协议（External Gateway Protocol，EGP，也叫域间路由协议）。域间路由协议有两种：外部网关协议（EGP）和边界网关协议（BGP）。EGP是为一个简单的树型拓扑结构而设计的，在处理选路循环和设置 选路策略时，具有明显的缺点，目前已被BGP代替。1. 距离向量（DV）协议 距离向量指协议使用跳数或向量来确定从一个设备到另一个设备的距离。不考虑每跳链路的速率。 距离向量路由协议不使用正常的邻居关系，用两种方法获知拓扑的改变和路由的超时 当路由器不能直接从连接的路由器收到路由更新时； 当路由器从邻居收到一个更新，通知它网络的某个地方拓扑发生了变化。 在小型网络中（少于100个路由器，或需要更少的路由更新和计算环境），距离向量路由协议运行得相当好。当小型网络扩展到大型网络时，该算法计算新路由的收敛速度极慢，而且在它计算的过程中，网络处于一种过渡状态，极可能发生循环并造成暂时的拥塞。再者，当网络底层链路技术多种多样，带宽各不相同时，距离向量算法对此视而不见。 距离向量路由协议的这种特性不仅造成了网络收敛的延时，而且消耗了带宽。随着路由表的增大，需要消耗更多的CPU资源，并消耗了内存。 2. 链路状态（LS）路由协议 链路状态路由协议没有跳数的限制，使用“图形理论”算法或最短路径优先算法。 链路状态路由协议有更短的收敛时间、支持VLSM（可变长子网掩码）和CIDR。 链路状态路由协议在直接相连的路由之间维护正常的邻居关系。这允许路由更快收敛。链路状态路由协议在会话期间通过交换Hello包（也叫链路状态信息）创建对等关系，这种关系加速了路由的收敛。 不像距离向量路由协议那样，更新时发送整个路由表。链路状态路由协议只广播更新的或改变的网络拓扑，这使得更新信息更小，节省了带宽和CPU利用率。另外，如果网络不发生变化，更新包只在特定的时间内发出（通常为30min到2h）。总的来说，一般小型网络适合采用基于距离向量算法的路由协议，而大型网络则适合采用链路状态算法的路由协议。1.2 Ad hoc网络中路由概述Ad hoc网络是由无线移动节点构成的自组织网络，没有基站、路由器那样的静态网络结构，所有节点都可以随机地、自由地移动，其网络拓扑结构是动态变化的。在Ad hoc网络中只有相邻节点之间才能进行通信，若2个节点之间的距离超出传输范围时(一般为150-250 m)，那么必须通过一个或多个中间节点以“多跳”的方式来转发信息，因此Ad hoc网络的关键问题之一是设计有效的、自适应的路由协议，保证任意2个移动节点在网络拓扑变化以后仍能实现高质量的通信。Ad hoc网络在军事、紧急救助和探险等领域具有非常重要的应用前景。传统的路由算法主要基于距离矢量(distance vector)或链路状态(1ink state)，距离矢量路由中，每个节点维持所有可能到达节点的距离矢量表，并向周围节点周期性地广播自己的路由表，同时根据相邻路由表接收到的值来计算自身路由表的更新值。通过比较到每一个相邻节点的距离，路由器可以确定将哪个节点作为它的“下一跳(next hop)”，以便于具有最短路径；链路状态路由中，每个路由表维持一个完整的全网拓扑图。每个节点管理到相邻节点链路的损耗，并周期性地广播更新的链路信息。根据每一条链路的信息，每个节点路由表计算到所有可能的目的端的最短路径。由于这两种路由算法所消耗的CPU时间负荷和网络带宽都比较大，因此不能直接应用于Ad hoc网络。Ad hoe网络中的移动节点使用电池供电，节点之间的无线干扰严重限制了网络吞吐量，节点的移动性难以管理，因此在路由算法的设计中需要主要解决减少能量消耗、减小延迟、提高吞吐量等问题。现存Ad hoc网络路由协议可以分为2类：表驱动(tabledriven)和源发起按需驱动(sourceinitiated on-demand routing)。1.1 表驱动路由协议表驱动路由协议(tabledriven routing protocols)是有线网络路由协议向Ad hoc网络的移植。网络中的每个节点维持一个或多个表格来存储其它节点的路由信息，通过广播更新信息来保持路由表信息与网络拓扑的变化之间的一致性。典型的表驱动路由协议包括：DSDV (destinationsequenced distancevector routing)、CGSR (cluster head gateway switch routing)和WRP (wireless routing protoco1)等。表驱动路由协议虽然可以很快地获得到其它所有节点的路由，但是不可避免地存在信号拥塞和能量过度消耗的问题，而且表驱动路由协议逐渐被需驱动路由协议所替代。 1.2 源发起按需路由按需路由协议不需要像表驱动路由协议那样实时地维持每个节点的路由信息，而只在源节点需要路由的时候才发起路由，从而降低了对网络带宽和能量的过度消耗。当源节点需要一个到达某一目的节点的路由时，它在网络中发起一个路由发现过程；路由建立之后，会由一个路由维护程序进行维护，直到每条路径都断裂或不再需要路由为止。典型的源发起按需路由包括：AODV (Ad hoc ondemand vector routing)、DSR (dynamic source routing)、TORA (temporally ordered routing algorithm)等。下面一章会介绍到有关协议。1.3 无线传感器网络中路由概述随着微电子技术、计算技术和无线通信技术的进步，多功能传感器快速发展，进而使无线传感器网络（wireless sensor network, WSN）成为目前研究热点。WSN 是由部署在检测区域内的大量廉价微型传感器节点组成，形成一个多跳的自组织网络系统，使其在小体积内集成信息采集、数据处理和无线通信等功能，其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并提供给终端用户。WSN 能够广泛应用于军事、环境检测和预报、健康护理、智能家居、建筑物状态监控、复杂机械监控、城市交通、空间探索、大型车间和仓库管理、以及机场、大型工业园区的安全检测和其他商业等领域，且将逐渐深入到人类生活的各个领域。无线传感器网络的路由协议不同于传统网络的协议，它具有能量优先、基于局部的拓扑信息、以数据为中心和应用相关四个特点，因而，根据具体的应用设计路由机制时，从四个方面衡量路由协议的优劣：（1）能量高效传统路由协议在选择最优路径时，很少考虑节点的能量问题。由于无线传感器网络中节点的能量有限，传感器网络路由协议不仅要选择能量消耗小的消息传输路径，更要能量均衡消耗，实现简单而且高效的传输，尽可能地延长整个网络的生存期。（2）可扩展性无线传感器网络的应用决定了它的网络规模不是一成不变的，而且很容易造成拓扑结构动态发生变化，因而要求路由协议有可扩展性，能够适应结构的变化。具体体现在传感器的数量、网络覆盖区域、网络生命周期、网络时间延迟和网络感知精度等方面。（3）鲁棒性无线传感器网络中，由于环境和节点的能量耗尽造成传感器的失效、通信质量的降低使网络变得不可靠，所以在路由协议的设计过程中必须考虑软硬件的高容错性，保障网络的健壮性。（4）快速收敛性由于网络拓扑结构的动态变化，要求路由协议能够快速收敛，以适应拓扑的动态变化，提高带宽和节点能量等有限资源的利用率和消息传输效率。 而关于无线传感器网络路由协议的分类，研究人员针对不同的标准，形成了多种分类方法，目前还没有统一的分类标准。第三章会对无线传感器网络中的路由协议的分类比较进行详细地介绍。2.适用于MANET的路由简介下面介绍三个适用于MANET中的三个经典路由协议，况且hsn包中也包含有DSDV和AODV协议的内容，所以放到这里来做介绍很有意义。DSDV目的序列距离矢量协议DSDV(Destination Sequenced Distance Vector) （详见11）是基于经典的Bellman-Ford路由算法, 通过修改路由信息协议RIP得到的, 它是一种先应式的路由协议（而DSR和AODV都是按需的）。AODV和DSR都是需要路由时，通过路由发现过程来建立路由，而DSDV则是通过路由表。每个移动节点都在本地保存一张路由表，其中记录了所有与该节点可能进行连接的目标节点、下一跳、跳数和该路由序列号等信息，路由序列号用于区别新旧路由以避免环路的产生, 优先采用序列号大的路由, 如果序列号相同, 则优先采用跳距小的路由。因为DSDV的路由表信息是通过Bellman-ford这一经典的单源最短路径算法得到的，所以这边简单介绍一下（详见19）。Bellman-Ford算法在一般情况下，能解决单源最短路径问题。无线传感器网络中的路径可以看作是有向路径，因为消息的传输都是有向的，且来回的开销等参数也不尽相同。通过某种标准（譬如说能量开销）对路径进行函数加权，这样如果没有负权回路的话，算法就能得到各节点的最短路径和权值。一般Bellman-ford算法分三个过程：（1）初始化；（2）迭代求解：反复对边集E中的每条边进行松弛操作（详见19），使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离（运行|v|-1次）；（3）检验负权回路：对负权回路进行检查，并返回布尔值。为了便于说明，以下图来分析。如下图所示，S节点为源节点，定点内为最短路径估计值，每条边为有向加权值，最后的加粗线为到各个节点的最短路径。（a）为对边进行松弛操作前的情况，然后每一趟按如下顺序对边进行松弛：（A,C）,(A,B),(A,D),(C,A),(B,C),(B,D),(D,C),(D,S),(S,A),(S,B)。（b）（e）为每一次连续对边进行松弛操作后的情况。（e）为进行了5-1=4次（因为有五个节点）后的最终结果。因为最后不存在负权回路，能得到各节点的最短路径，所以算法的布尔返回值为TRUE。DSDV则通过这种算法最后得到与某节点所有可能连接的目标节点、跳数等路由信息，存入当地的路由表，以供在传输数据包时使用。55555-4-3-2206ABCDS7879(a)-4-3-220676ABCD7879(b)-4-3-22024726ABCD7879(d)-4-3-220247-26ABCD7879(e)-4-3-22064726ABCD7879(c)SSSS图 Bellman-Ford算法执行过程由于DSDV的路由信息都保存在路由表中，所以路由表的更新则是一个很关键的问题。DSDV 采用时间驱动和事件驱动结合控制路由表更新的传送, 每个节点周期性地将路由更新信息传送给相邻节点； 或者当其路由表发生变化时, 也会将路由更新信息传给相邻节点。为了减少控制信息的开销，DSDV 把路由更新信息分为两类, 一类称为完整路由更新(full dump ) , 包含了该节点的路由表中所有的路由信息。另一种称为增量路由更新(incremental) , 携带的是从上次full dump 以后改变的路由信息。一个增量路由更新的大小应该小于一个网络协议数据单元(NPDU) 的大小, 当增量的路由信息达到或大于一个NPDU的大小时, 就应该发送完整路由更新, 否则只是发送增量路由更新。由于节点经常会先后收到多个到同一目的地并具有相同序列号的路由更新信息, 而且往往先收到跳距较大的路由信息, 这会触发节点频繁的发送路由更新信息, 浪费了带宽。一种解决办法就是, 在节点收到第一条需要采用的路由更新时, 当经过该节点到目的节点的跳数比自己所保存的路由信息中的跳数大时, 节点并不马上触发自己发送路由更新, 而是随机等待片刻, 尽量收完多个路由更新, 选取最优的更新自己的路由表，再发送自己的路由更新。该协议要求每个节点定期地通过网络发送和传播路由信息来维护路由表的一致性。因此，DSDV协议下有大量的控制包在网上传输。这也是DSDV的一个缺点。AODV因为hsn包下也有AODV的协议，所以下面作较为详细的介绍（详见10和12）。可以说AODV结合了DSDV目标序列号和DSR按需路由的特性，使其在路由协议中地位不一般。AODV协议是一种按需路由协议，共涉及四种消息包：RREQ，RRER，RERR和HELLO。而路由过程则分为路由发现和路由维护两个阶段。RREQ是路由发现阶段，通过广播路由请求RREQ来发起路由发现；而RRER则是进行路由发现的回复，以确定路由；当发现链路断裂或节点的移动而不可达时，通过RERR报文的发送来重新进行路由发现；HELLO信息则是用来进行本地链接管理和路由的维护工作。分路由发现和路由维护两个阶段来说明原理：路由发现阶段：设A为源节点，E为目标节点，B、C、D是路径上的三个中间节点。和DSR一样，每次发起一个新的RREQ时，则序列号则加1。如图所示，A先向邻居节点广播RREQ请求包，邻居节点B收到后，先比较以前收到的广播包的源地址和ID（源地址和广播ID唯一确定一个RREQ），如相同则视为过时，丢弃之，同时检查有没有到目标节点E的路由，有则直接发送RREP给A，否则继续向邻居节点转发，同时在路由表中记录下A作为前驱节点，并记下广播ID且跳数也增加1。图 AODV路由ABCDERREQ路径RREP路径同理，C收到RREQ信息后，作法和B完全一致，更新了路由表后，继而转发RREQ至D，D作法也如前，假如也没到目标节点E的路由，则RREQ发送到目标节点E，当E收到RREQ，首先比较自己已收到的包的目标序列号和RREQ中的目标序列号，如果RREQ中的大则表明收到的RREQ是最新的，则更新已有的目标序列号，并记下上游节点和广播ID，之后进行RREP报文回复，如果收到的目标序列号相同则根据跳数hop最小来决定取舍，hop小的回复RREP报文。RREP回复包沿着每个节点记录下的路由路径反向回到原节点，同时经过每个节点时在路由表的后继即下一跳栏中记下传递RREP包的节点，同样当RREP包到达A点，A比较收到的RREP包的源序列号是否最新，如果最新且跳数小则最后确认路径来更新自己路由表中的值。其中，RREQ和RREP报文的格式如下：RREQ报文（源地址，SeqNumber源，广播ID，目的地址，SeqNumber目的，hop）RREP报文（源地址，SeqNumber源，广播ID，目的地址，SeqNumber目的，hop，生存期）路由维护阶段AODV的路由方案是在非活动路径上的节点的移动对路径没有影响，如果源节点移动了，就会重新发起路由发现来建立一条到目标地址的路径。如果目标节点或者路径中的节点的位置发生了改变，一个RERR就会被发送到源节点。周期性的HELLO消息可以用来检测链路失效。当发起RERR的节点检测到链路失效时，就会通知所有利用该链路的邻居节点链路失效。同时沿着RREP的反方向将RERR传送到源节点，所有收到RERR的节点都将清除自己路由表中该路径的表项，当源节点收到RERR后，如果任然需要到目标节点的路由，就会重新发起路由发现。图 AODV路由重建数据流图ABCDERREQ路径RERR路径如上图所示，A是源节点，E是目的节点，B、C、D是中间节点，假如C节点周期性检测到D节点不可达，则向它的上跳C节点回复RERR报文，B节点接到RERR，清除掉自己路由表中的相应项目，继续把RERR传送给上跳节点A，源节点A收到RERR，则根据需要重新发起新的路由查找。DSR动态源路由协议DSR (Dynamic Source Routing）（详见18）是一种基于源路由的按需路由协议，它使用源路由算法，发送方知道应该经过哪些中间节点一跳一跳地到达目的地，这些路由都存储在一个缓存中。源路由的特点是每一个被传输的包都携带一个要到达目的节点的完整路径。网络中从源节点到目的节点这条路径上的所有节点按照数据分组头中提供的路由信息，依次转发该数据分组，直至该数据分组到达目的节点。DSR路由协议的优点是所有“中间”节点不必保存转发数据分组所必需的最新路由信息，因为数据分组头中能够提供足够的路由信息。不过，源节点需要知道数据分组所要经过的所有中间节点序列。DSR获得路由信息的过程分为路由发现和路由维护，这和上面的AODV中的机制其实是一样的，AODV其实是吸取了DSR的这个特点。总的来说，实现这样一个过程：当节点S向节点D发送数据时，它首先检查缓存是否存在未过期的到目的节点的路由，如果存在，则直接使用可用的路由，否则启动路由发现过程，具体过程如下：源节点S将使用洪泛法发送路由请求消息(RREQ)，RREQ包含源和目的节点地址以及唯一的标志号，中间节点转发RREQ，并附上自己的节点标识。当RREQ消息到达目的节点D或任何一个到目的节点路由的中间节点时(此时，RREQ中已记录了从S到D或该中间节点的所经过的节点标识)，D或该中间节点将向S发送路由应答消息(RREP)，该消息中将包含S到D的路由信息，并反转S到D的路由供RREP消息使用。源节点将此路由写入自己的缓存中以备今后使用。而在路由维护阶段，因为在DSR 协议中路由的维护是按需的，不需要周期的广播。一旦某个路由正在使用，路由维护程序会监控运行情况，并把错误信息传送到源节点。如果数据分组传送路径上的某个中间节点发现错误，那么它会回传一个路由错误分组。源节点收到路由出错分组后，将触发一次新的路由建立过程。优点：（1）仅需要维护与之通信的节点的路由，减少了协议开销；（2）使用路由缓存技术减少了路由建立的开销；（3）支持到目的节点的多条路径；（4）能正确地计算出非双向链路的路由。缺点：（1）每个数据分组的头部都需要携带路由信息，数据分组额外开销较大；（2）路由请求消息采用洪泛方式，相邻节点路由请求消息可能发生传播冲突和重复广播；（3）由于采用路由缓存，过期路由会影响路由选择的准确性。通过比较，DSR和AODV有如下区别：AODV通过目标序列号的标识，可以让中间节点在路由表中记录下最新路由信息，而使源节点在发送数据包时能通过中间节点传输；而DSR则是通过路由发现过程后，源节点收集完路由信息，然后把它加到数据分组头中，这样中间节点就不需要对产生的新路由进行记忆，因为数据包中已经包含完整的路由信息，来沿着路由传输。其次，在路由维护方面，DSR和AODV也不一样，AODV通过周期性的广播HELLO消息，对路由进行维护；而DSR则是按需的，当节点发现路径发生传输错误时，将重新进行路由发现。最后，在能耗方面，因为AODV需要周期性的广播HELLO包的开销，AODV的能量消耗还是大于DSR的，但是AODV和DSR都是按需路由，它们的能量开销还是远小于DSDV的，这样看来，按需路由在能耗方面还是占很大优势的。而在一些学者的试验研究看来，AODV的大多数性能都要优于DSR的，如吞吐率、发送成功率以及端对端延时等。3.无线传感网中的路由协议2.1概述无线传感器网络中节点的能量资源、计算能力和带宽都非常有限，而且无线传感器网络通常由大量密集的传感节点构成，这就决定了无线传感器网络协议栈各层的设计都必须以能源有效性为首要的设计要素。网络层的主要设计目标是能源有效性路径的建立；可靠数据转发机制的形成；最长网络生命周期的实现。无线传感器网络路由协议设计与传统的无线ad hoc 网络有很多不同，无线传感器网络路由设计的重要目标是降低节点能源损耗，提高网络生命周期；而传统的无线ad hoc 网络的路由协议设计的首要任务是移动条件下高服务质量的提供。这些不同导致了传统的无线ad hoc 网络路由协议不能直接用于无线传感器网络中，许多新的适用于无线传感器网络的路由协议得到提出，它的研究已经成为无线传感器网络研究中的热点。WSN路由协议和MANET比较：与MANET相比，WSN具有自身的特点，这使得必须根据WSN的特点设计其路由协议，以适应网络规模大、拓扑易变化、能量有限的WSN的需要，延长网络的生存周期。下面介绍WSN的特点及其路由协议设计的关键问题：1)WSN较之MANET的节点数目更为庞大(上千甚至上万)，节点分布更为密集，这使得必须为WSN设计适于大规模网络的路由协议；2)由于环境和能量的影响，WSN节点更容易出现故障，容易造成网络拓扑的变化，这使得WSN的路由协议要有更强的自适应性和鲁棒性；3)WSN节点的能量、处理能力、存储能力和通信能力都十分有限，这使得为WSN设计的路由协议必须简单且节能；4)MANET采用点对点传输模式，而WSN的数据传输遵循多对一或一对多模式，这使得WSN路由协议的设计必须考虑负载均衡；5)通常情况下，MANET中节点移动性很强，而大多数传感器节点是固定不动的；6)MANET是以地址为中心进行路由，而WSN是以数据为中心的路由；且邻近节点间采集的数据具有相似性，需进行数据融合；7)MANET的首要设计目标是提供高服务质量和有效带宽利用，其次才考虑能源，而WSN的首要设计目标是能源的高效使用，这使得必须为WSN设计能量有效的路由协议；8)WSN的路由协议是基于特定应用而设计的，很难设计具有通用性的路由协议。2.2无线传感网中的路由协议设计Sink 可以通过Internet 或通信卫星实现传感器网络与任务管理节点通信。无线传感器网络体系结构中存在着下列影响路由协议设计的因素：1网络动态：大部分网络体系结构都假设传感节点是静态的，而Sink 是可移动的。观察对象的移动或静止则处决于不同应用程序的要求。2网络拓扑：分为固定和自组织两种拓扑配置方式。固定情况下，手动配置节点，数据通过预定路径传送；自组织情况下，节点以ad hoc 方式随机散布。3数据发送模式：根据不同的应用程序，可将数据发送模式分为连续模式，事件驱动模式，查询驱动模式和混合模式。4节点类型：通常所有的传感节点都为同构的。在需要不同功能的传感器的应用中，也存在异构的传感节点。近来还有人提出采用特殊的能源局限性弱的节点来充当兼具转发，传感和聚集数据三种功能的传感节点。5路径选择：存在多跳和单跳两种选择方式。无线射频的发送能量与距离的平方成正比，多跳路径的能源消耗比单跳路径少，故多采用多跳路径。但由于多跳路径的拓扑管理和链路连接开销大，在传感节点同Sink 节点距离短的情况下，单跳路径反而更有效。评价一个无线传感器网络的路由设计是否成功，往往采用如下的性能标准：1能源有效性/生命周期：能源有效性是传感器网络设计中要考虑的重要因素。尽可能降低能源消耗，从而延长网络生命周期，是我们设计的首要目标。2可靠性/容错性：传感节点容易因为能源耗尽或环境干扰而失效。部分传感节点的失效不应影响整个网络的任务。3可扩展性：在一些应用中可能需要成百上千个传感节点，路由设计应能满足大量节点协作。4时延性：传感器网络的延迟时间是指观察者发出请求到收到应答信息所需时间。我们必须尽可能减少时延。无线传感器网络路由协议的设计极负挑战性，它与传统的无线adhoc 网络有着许多不同的特色：1无全局标识：传感节点数量庞大，维护全局标识需要大量的开销，因此不同于传统的基于IP 的路由协议，在传感器网络中一般不采用全局标识；2多对一通信：不同于传统网络的点对点通讯，在传感器网络中几乎所有的应用都要求多个源传感节点将传感到的数据流传送至特定的Sink；3数据冗余大：多个源传感节点在许多场景下都有可能获得大量相似的数据，因此传感器网络的冗余数据大；4资源局限强：传感节点的资源限制很大，发送功耗，板上能源，处理能力和存储量都局限在很低的范围内。2.3无线传感网中的路由协议分类关于无线传感器网络路由协议的分类方法现在有很多，研究学者依据不同的标准对其进行分类。目前还没有一个统一的标准，下面对这些分类进行总结一下并列出一些比较经典的路由协议。2.3.1依据网络的逻辑结构可分为平面路由和层次路由。平面路由平面路由中各节点都将收集到的数据传送到汇聚节点，所有节点具有相同的地位和功能，节点间相互协作共同完成感知和数据处理任务。典型的平面路由协议有Flooding，SPIN，DD，Rumor和SAR等。FloodingFlooding是一种传统的洪泛路由技术，无线传感器网络路由协议的研究最早也是从Flooding开始的。它实现简单，不需要为保持网络拓扑信息和实现复杂的路由算法消耗计算资源，适用于健壮性要求高的场合。但是，它也有很大的缺陷：内爆（节点几乎同时从邻节点收到多份相同数据）、交叠（节点先后收到监控同一区域的多个节点发送的几乎相同的数据）、资源盲目利用（节点不考虑自身资源限制，在任何情况下都转发数据）。协议假设：节点没有能量方面的限制，适用于健壮性要求高的场合。具体实现（详见21）：节点A希望发送数据给节点B，节点A首先通过网络将数据包传给其每一个邻居节点，每一个邻居节点又将其传给除A外的其他的邻居节点，直到将数据包传送到B为止或者为该数据设定的生命期限变为零为止。优缺点分析：优点显而易见，实现简单，不需要复杂的路由算法，但如上所说，内爆、交叠和资源盲目性是其固有的缺陷。DD定向路由扩散DD（Directed Diffusion）通过泛洪方式广播兴趣消息给所有的传感器节点，随着兴趣消息在整个网络中传播，协议逐跳地在每个传感器节点上建立反向的从数据源节点到基站或者汇聚节点的传输梯度。该协议通过将来自不同源节点的数据聚集再重新路由达到消除冗余和最大程度降低数据传输量的目的，因而可以节约网络能量、延长系统生存期。然而，路径建立时的兴趣消息扩散要执行一个泛洪广播操作，时间和能量开销大。协议假设：路由建立前sink节点并不知道数据源所在的具体位置，不适合多sink点网络，不适合环境监测等应用。具体实现(详见1第二章)：首先是兴趣消息扩散，每个节点都在本地保存一个兴趣列表，其中专门存在一个表项用来记录发送该兴趣消息的邻居节点、数据发送速率和时间戳等相关信息，之后建立传输梯度。数据沿着建立好的梯度路径传输。如下图所示。Sink节点首先扩散兴趣消息，遍历全网，找到所有匹配的数据，用一个梯度标量值来反映网络中间节点对匹配请求条件的数据源的近似判断，值越大表示向该方向继续搜索获得匹配数据的可能性越大，这样形成一个临时的梯度场，匹配数据沿梯度最大的方向返回Sink节点如（c）所示，形成传输路径。优缺点分析：协议采用多路径,健壮性好;使用数据聚合能减少数据通信量;sink点根据实际情况采取增强或减弱方式能有效利用能量;使用查询驱动机制按需建立路由,避免了保存全网信息。因此它是一种高能源有效性的协议。它的缺点是，在需要连续数据传送的应用中（环境监测等）不能很好的应用；数据命名只能针对于特定的应用预先进行；初始查询的扩散开销大。0.50.50.51.01.01.01.00.30.50.8SinkSourceSourceSourceSinkSink（a）兴趣扩散（b）梯度场建立（c）数据传输SPINSPIN（Sensor Protocols for Information via Negotiation）是第1个基于数据的路由协议。该协议以抽象的元数据对数据进行命名,命名方式没有统一标准。节点产生或收到数据后,为避免盲目传播,用包含元数据的ADV消息向邻节点通告,需要数据的邻节点用REQ消息提出请求,数据通过DATA消息发送到请求节点。协议假设：协议假定网络中所有节点都是sink 节点，每一个节点都有用户需要的信息，而且相邻的节点拥有类似的数据，适用于中小规模的、特别是传感器节点是运动的应用环境。具体实现（详见22）：SPIN 采用了3 种数据包来通信：ADV 用于新数据的广播，当节点有数据要发送时，利用该数据包向外广播；REQ 用于请求发送数据，当节点希望接收数据时，发送该报文；DATA 包含带有Meta-data 头部数据的数据报文；当一个传感器节点在发送一个DATA 数据包之前，首先向其邻居节点广播式地发送ADV 数据包，如果一个邻居希望接收该DATA 数据包，则像该节点发送REQ 数据包，接着节点向其邻居节点发送DATA 数据包。下图表示了SPIN协议的路由建立与数据传输。优缺点分析：协议的优点是:小ADV消息减轻了内爆问题;通过数据命名解决了交叠问题;节点根据自身资源和应用信息决定是否进行ADV通告,避免了资源利用盲目问题。与Flooding相比,有效地节约了能量。但其缺点是:当产生或收到数据的节点的所有邻节点都不需要该数据时,将导致数据不能继续转发,以致较远节点无法得到数据,当网络中大多节点都是潜在sink点时,问题并不严重,但当sink点较少时,则是一个很严重的问题;且当某sink点对任何数据都需要时,其周围节点的能量容易耗尽;虽然减轻了数据内爆,但在较大规模网络中,ADV内爆仍然存在。AADVREQDATAADVREQDATA(a)ADV扩散(b)数据请求(c)数据传送(d)ADV扩散(e)数据请求(f)数据传送图 SPIN的路由建立与数据传输Rumor RoutingD. Braginsky等人提出的适用于数据传输量较小的无线传感器网络高效路由协议。其基本思想是时间监测区域的感应节点产生代理消息，代理消息沿着随机路径向邻居节点扩散传播。同时，基站或汇聚节点发送的查询消息也沿着随机路径在网络中传播。当查询消息和代理消息的传播路径交叉在一起时就会形成一条基站或汇聚节点到时间监测区域的完整路径。如下图所示。汇聚节点事件区域发起路径：节点：查询路径：事件发生区域：图 谣传路由原理图协议假设：假定事件数比较少且不存在路由环路问题，适用于数据传输量较小的无线传感器网络高效路由协议。具体实现(详见1第二章)：每个传感器节点维护一个邻居列表和一个事件列表，当传感器节点监测到一个事件发生时，在事件列表中增加一个表项并根据概率产生一个代理消息，代理消息是一个包含事件相关信息的分组，将事件传给经过的节点，收到代理消息的节点检查表项进行更新和增加表项的操作。节点根据事件列表到达事件区域的路径，或者节点随机选择邻居转发查询消息。 优缺点分析：谣传路由机制引入了查询消息的单播随机转发，克服了使用洪泛方式建立转发路径带来的开销过大问题，但是由于谣传路由使用随机方式生成路径，所以数据传输路径不是最优路径，并且可能存在路由环路问题。总的来说，平面路由算法易于实现，但维护路由的开销大，数据传输跳数多，可扩展性差，只适用于小规模的网络。随着网络规模的扩大，单层网络中传感器节点的密度增大，导致汇聚节点负载过重；而且，由于传感器节点能量受限，不适宜长距离通信，只能通过多跳方式到达汇聚节点，单个汇聚节点的结构会成为WSN可扩展性的瓶颈。层次路由早期的层次路由中传感器节点按照不同的分簇方法分成相应的簇，每个簇中选举一个簇头节点，通过节点的多跳通信和数据融合来减少信息发送次数，以节约能耗，延长网络的生存周期。典型的层次路由协议有LEACH，PEGASIS和分层PEGASIS，TEEN 和At-EEN，以及Younis等人提出的能量感知的分簇路由协议等。层次路由可扩展性好，适合大规模网络，但簇的重构及维护开销大，且簇头是路由的关键节点，其失效将导致路由失败。LEACH无线传感器网络的一种分簇路由算法，其基本思想是以循环的方式随机选择簇头节点，平均分配整个网络的能量到每个传感器节点，从而可以降低网络能源消耗，延长网络生存时间。簇头的产生是簇形成的基础，簇头的选取一般基于节点的剩余能量、簇头到基站或汇聚节点的距离、簇头的位置和簇内的通信代价。簇头的产生算法可以被分为分布式和集中式两种，这里不予介绍。协议假设：假定所有的节点都能直接与簇头节点和终端节点通讯，不适用于需要监测面积范围大的应用。具体实现（详见23）：LEACH 不断地循环执行簇的重构过程，可以分为两个阶段：一是簇的建立，即包括簇头节点的选择、簇头节点的广播、簇头节点的建立和调度机制的生成。二是传输数据的稳定阶段。每个节点随机选一个值，小于某阈值的节点就成为簇头节点，之后广播告知整个网络，完成簇的建立。在稳定阶段中，节点将采集的数据送到簇头节点，簇头节点将信息融合后送给汇聚点。一段时间后，重新建立簇，不断循环。具体LEACH算法选举簇头的过程如下：节点产生一个01之间的随机数，如果这个数小于阈值T(n),则发布自己是簇头的公告消息。在每轮循环中，如果节点已经当选过簇头，则把T（n）设置为0，这样该节点不会再次当选为簇头。对于未当选过簇头的节点，则将以T(n)的概率当选；随着当选过簇头的节点数目增加，剩余节点当选簇头的阈值T(n)随之增大，节点产生小于T(n)的随机数的概率随之增大，所以节点当选簇头的概率增大。当只剩下一个节点未当选时，T(n)=1，这表示这个节点一定当选。T(n)可表示为其中，P是簇头在所有节点中所占的百分比，r是选举轮数，r mod（1/p)代表这一轮循环中当选过簇头的节点个数，G是这一轮循环中未当选过簇头的节点集合。节点当选簇头以后，发布通告消息告知其他节点自己是新簇头。非簇头节点根据自己与簇头之间的距离来选择加入哪个簇，并告知该簇头。当簇头接收到所有的加入信息后，就产生一个TDMA定时消息，并且通知该簇中所有节点。为了避免附近簇的信号干扰，簇头可以决定本簇中所有节点所用的CDMA编码。这个用于当前阶段的CAMA编码连同TDMA定时一起发送。当簇内节点收到这个消息后，它们就会在各自的时间槽内发送数据。经过一段时间的数据传输，簇内节点收齐簇内节点发送的数据后，运行数据融合算法来处理数据，并将结果直接发送给汇聚节点。优缺点分析：采用LEACH 方法使因能量耗尽而失效的节点呈随机分布状态，因而与一般的多跳路由协议和静态聚类算法相比，LEACH 可以将网络生命周期延长15%。但是LEACH 假设所有的节点都能直接与簇头节点和终端节点通讯，采用连续数据发送模式和单跳路径选择模式，因此在需要监测面积范围大的应用中不适用，而且动态分簇带来了拓扑变换和大量广播这样的额外开销。PEGASIS 这是在LEACH协议基础上建立的协议。协议假设：假定每个节点都知道网络中其他节点的位置，且都具有与sink节点通信的能力，适用范围与LEACH一样。具体实现（详见24）：仍然采用动态选举簇头的思想,但为避免频繁选举簇头的通信开销，采用无通信量的簇头选举方法，且网络中所有节点只形成一个簇，称为链。该协议要求每个节点都知道网络中其他节点的位置，通过贪心算法选择最近的邻节点形成链。动态选举簇头的方法很简单： 设网络中N个节点都用1N的自然数编号，第j轮选取的簇头是第i个节点，i=j mod N (i为0时，取N)。簇头与sink点一跳通信，利用令牌控制链两端数据沿链传送到簇头本身，在传送过程中可聚合数据。当链两端数据都传送完成时，开始新一轮选举与传输。C0C1C2C3C4sink图 PEGASIS协议沿链进行数据传输优缺点分析：该协议通过避免LEACH协议频繁选举簇头带来的通信开销以及自身有效的链式数据聚合，极大地减少了数据传输次数和通信量；节点采用小功率与最近距离邻节点通信，形成多跳通信方式，有效地利用了能量，与LEACH协议相比能大幅提高网络生存时间。但单簇方法使得簇头成为关键点，其失效会导致路由失败，且要求节点都具有与sink点通信的能力，如果链过长，数据传输时延将会增大，不适合实时应用，成链算法要求节点知道其他节点位置，开销非常大。下图表示了PEGASIS协议沿链进行数据传输的情况。TEEN TEEN和LEACH的实现机制非常相似,只是前者是响应型的,而后者属于主动型传感器网络。该协议采用与LEACH协议相同的聚簇方式，但簇头根据与sink点距离的不同形成层次结构。协议假设：协议假定簇头节点不会失效，不适合需要周期性上报数据的应用。具体实现（详见25）：聚簇完成后，sink点通过簇头向全网节点通告两个门限值(分别称为硬门限和软门限)来过滤数据发送。在节点第1次监测到数据超过硬门限时，节点向簇头上报数据，并将当前监测数据保存为监测值(sensed value，简称SV)。此后只有在监测到的数据比硬门限大且其与SV之差的绝对值不小于软门限时，节点才向簇头上报数据，并将当前监测数据保存为SV。该协议通过利用软、硬门限减少了数据传输量，且层次型簇头结构不要求节点具有大功率通信能力。但由于门限设置阻止了某些数据上报，不适合需周期性上报数据的应用。下图表示了TEEN协议中由聚簇构成的层次结构。 Sink High level cluster head Low level cluster head Normal sensor node Clustering图 TEEN协议中由聚簇构成的层次结构 优缺点分析：因为用户大多数情况下不需要所有的数据，所以周期性的传输数据是不必要的， 因此TEEN 比LEACH节省了许多的数据传输。NS2平台上的仿真研究结果表明TEEN 比LEACH更有效。TEEN 的缺点是：如果数据的属性值一直达不到门限，节点不会发送数据，用户将接收不到网络的任何数据，并且不能得知所有节点是否死亡。上面根据网络的逻辑结构对WSN路由协议进行了分类，通过以上分析，可从路由策略、路由协议的特点、性能几个方面对各类路由协议进行对比分析：路由分类路由协议路由策略维护多路径路由关键点网关节点负载均衡性网络生存时间可扩展性平面路由Flooding，DFlooding,SP