适用于MANET的路由简介.doc

适用于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点根据实际情况采取增强或减弱方式能有效利用能量;使用查询驱动机制按需建立路由,避免了保存全网信息。因此它是一种高能源有效性的协议。它的缺点是，在需要连续数据传送的应用中（环境监测等）不能很好的应用；数据命名只能针对于特定的应用预先进行；初始查询的扩散开销大。1.01.01.01.0SinkSourceSourceSourceSinkSink（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,SPIN,DD,Rumor,SAR按需SPIN，DD，SAR无无不好较好受限层次路由LEACH,PEGASIS,TEEN,CDCS,交叠簇法主动否簇交叠法无簇交叠法有好好好2.3.2依据应用场合WSN的路由协议的一个很重要的特点是应用相关性很强，都是基于特定的应用而设计的，依据应用场合分类，将其路由协议分为能量感知路由、基于查询的路由、地理位置路由和可靠路由四种类型。(这种分类在孙利民的传感器网络中第二章“路由协议”有详细的介绍)能量感知路由能量路由能量路由(详见1第二章)从数据传输中的能量消耗出发，讨论最优能量消耗路径以及最长网络生存期等问题。包括最大PA(power available,PA)路由，最小能量消耗路由，最少跳数路由，最大最小PA节点路由以及由Shah等人提出的能量多路径路由。协议假设：能量路由算法假定节点知道网络的全局信息，适用于仅考虑能量因素的应用。通过下图来阐述能量路由的几个机制： 汇聚节点a1=1a3=2a4=2E(PA=1)A(PA=2)a2=1B(PA=2)a8=2C(PA)=2a7=1a9=2源节点a5=2D(PA=3)a6=2F(PA=4)a10=2图 能量路由算法示意图大写字母表示节点，节点右侧括号内的数字表示节点的可用能量。图中的双向线表示节点之间的通信链路，链路上的数字表示在该链路上发送数据消耗的能量。源节点是一般功能的传感器节点，完成数据采集工作。汇聚节点是数据发送的目标节点。在图中，从源节点到汇聚节点的可能路径有：路径1：源节点BA汇聚节点，路径上所有节点PA之和为4，在该路径上发送分组需要的能量之和为3；路径2：源节点CBA汇聚节点，路径上所有节点PA之和为6，在该路径上发送分组需要的能量之和为6；路径3：源节点D汇聚节点，路径上所有节点PA之和为3，在该路径上发送分组需要的能量之和为4；路径4：源节点FE汇聚节点，路径上所有节点PA之和为5，在该路径上发送分组需要的能量之和为6。而能量路由策略主要有以下几种：（1） 最大PA路由：从数据源到汇聚节点的所有路径中选取节点PA之和最大的路径。在图中，路径2的PA之和最大，但路径2包含了路径1，因此不是高效的从而被排除，选择路径4。（2） 最小能量消耗路由：从数据源到汇聚节点的所有路径中选取节点耗能之和最少的路径。图中选取路径1。（3） 最少跳数路由：选取从数据源到汇聚节点跳数最少的路径。图中选择路径3。（4） 最大最小PA节点路由：每条路径上有多个节点，且节点的可用能量不同，从中选取每条路径中可用能量最小的节点来表示这条路径的可用能量。如路径4中节点E的可用能量最小为1，所以该路径的可用能量是1。最大最小PA节点路由策略就是选择路径可用能量最大的路径。图中选择路径3。优缺点分析：上述能量路由算法需要节点知道整个网络的全局信息，由于传感器网络存在资源约束，节点只能获取局部信息，因此上述能量路由算法只是理想情况下的路由策略。Shah等人提出的能量多路径路由该协议的目的主要在于改善Directed Diffusion协议的耗能情况，采用地理位置和数据类型(即节点类型)标识节点。Shah等人认为该协议是按需路由协议，但其含义更多的是查询驱动的，我们将其与Directed Diffusion都列为主动路由协议。协议假设：网络模型假设所有节点有较低的失效率，网络具有较稳定的拓扑结构，适用于对网络生存期要求较高的应用场合。具体实现(详见1第二章)：sink点(Cost(sink)=0)利用受控的flooding发起建立路由请求，产生或转发路由请求节点Ni的所有邻节点Nj测量与Ni的通信开销以及Ni的剩余能量:Metric(Nj，Ni)。Nj根据式(a)计算代价CNj,Ni，Nj节点选择CNj,Ni较小的一些邻节点反向构造路由表FTj，邻节点Ni被赋予由式(b)计算的路由概率PNj，Ni，此后Nj节点由式(c)计算自身代价Cost(Nj)，然后，Nj转发包含自身代价信息的请求。在通信阶段，节点Nj根据PNj，Ni选择一条路径进行数据发送。与Directed Diffusion相比，该协议虽然存在多条路径，但只选用一条，能够有效节约能源40%以上;随机选择路由方式平衡了通信量。优缺点分析：能量多路径路由综合考虑了通信路径上的消耗能量和剩余能量，节点根据概率在路由表中选择一个节点作为路由的下一跳节点。由于这个概率是与能量相关的，可以将通信能耗分散到多条路径上，从而可实现整个网络的能量平稳降级，最大限度地延长网络的生存期。其缺点是，sink点需要周期性flooding维护路由信息;需要进行节点间收发开销和剩余能量测量;根据概率随机选择一条路径导致其可靠性不如Directed Diffusion协议。基于查询的路由在诸如环境监测、战场评估等应用中，需要不断查询传感器节点采集的数据。在这类应用中，通信流量主要是查询节点和传感器节点之间的命令和数据传输，同时传感器节点的采样信息在传输路径上通常要进行数据融合，通过减少通信流量来节省能量。典型的基于查询的路由协议有DD、Rumor、CADR和ACQUIRE等。该类路由协议是基于按需查询驱动的数据采集模型，不适用于需要连续采集数据的场合。此外，选择与查询相匹配的数据会使传感器节点消耗更多的能量。基于查询的路由比较经典的是DD和Rumor，前面已经做过了介绍，这里不再说了。地理位置路由在一些WSN的应用中，需要知道节点的地理位置信息。地理位置路由假设节点知道自己的地理位置，以及目的节点或者目的区域的地理位置，利用这些地理位置信息作为路由选择的依据，节点按照一定策略转发数据到目的节点。典型的地理位置路由协议有MECN，GAF和GEAR等。该类路由协议将查询信息或数据仅发布到指定区域，从而有效地减少了数据传输次数，节约了能耗，并可以降低专门维护路由协议的能耗。但一般都需要定位技术的支持，在节点数据较多的情况下，增加了大量额外的开销。下面对比较经典的GEAR和GEM路由协议进行介绍下。GEARGEAR（geographical and energy aware routing）路由机制根据事件区域的地理位置信息，建立汇聚节点到事件区域的优化路径，避免了洪泛传播方式，从而减少了路由建立的开销。协议假设：GEAR协议假设已知事件区域的位置信息，每个节点知道自己的位置信息和剩余能量信息，适用于节点移动性不强的应用环境。具体实现（详见1第二章）：GEAR协议假设每个节点知道自己的位置信息和剩余能量信息，并通过一个简单的Hello消息交换机制知道所有邻居节点的位置信息和剩余能量信息。将数据分组传送到目标域中所有的节点分两个阶段：目标域数据传送和域内数据传送。在目标域数据传送阶段，当节点接收到数据分组，它将邻接点同目标域的代价和自己与目标域的代价相比较，代价更小，则选择最小代价的邻接点作为下一跳节点；若不存在更小代价，则认为存在路由空洞“hole”，节点将根据邻居的最小代价来选择下一跳节点。在域内数据传送阶段，可通过域内直接洪泛和迭代的目标域数据传送这两种方式让数据在域内扩散直到目标域剩下唯一的节点。优缺点分析：GEAR的优点是：它将网络中扩散的信息局限到适当的位置区域中，减少了中间节点的数量，从而降低了路由建立和数据传送的能源开销，进而更有效地提高了网络的生命周期。其缺点是依赖节点的GPS定位信息，成本较高。GEMJ. Newsome 和D. Song 提出了建立一个虚拟极坐标系统（VPCS, Virtual Polar 的Coordinate System）GEM（graph embedding） 路由协议，用来代表实际的网络拓扑结构。整个网络节点形成一个以基站或汇聚节点为根的带环树（Ringed Tree）。每个节点用距离树根的跳数距离和角度范围两个参数表示。协议假设：传感器网络拓扑结构相对稳定，适用于拓扑结构相对稳定的传感器网络。具体实现（详见1第二章）：首先建立虚拟极坐标系统，主要有三个阶段：由跳数建立路由并扩展到整个网络形成生成树型结构，再从叶节点开始反馈子树的大小，即树中包含的节点数目，最后确定每个子节点的虚拟角度范围。建立好系统之后，利用虚拟极坐标算法发送消息，即节点收到消息检查是否在自己的角度范围内，不在就向父节点传递，直到消息到达包含目的位置角度的节点。另外，当实际网络拓扑结构发生变化时，需要及时更新，比如节点加入和节点失效。优缺点分析：GEM是一种适用于数据中心存储方式的地理路由，数据中心存储方式能够将网络通信流量、处理流量和存储流量在网络中均匀分摊，从而有效避免了网络热点的产生。而采用虚拟极坐标的方法能够简单地将网络实际拓扑信息映射到一个易于进行路由处理的逻辑拓扑中，而且不改变节点间的相对位置。但是，由于采用了带环树结构，实际网络拓扑发生变化时，树的调整比较复杂，因此GEM路由适用于拓扑结构相对稳定的传感器网络。可靠路由WSN的某些应用对通信服务质量有较高的要求，如可靠性和实时性等，特别是在传递视频和音频数据时。而在WSN中，链路的稳定性难以保证，通信信道质量比较低，拓扑变化比较频繁，要实现服务质量保证，需要设计相应的可靠的路由协议。典型的可靠路由协议有基于不相交路径的多路径路由HREEMR，ReInForM 路由，SPEED 协议等。下面只介绍ReInForM和SPEED协议。ReInForM在传感器网络中，传感器节点是数据源，把监测数据发送给汇聚节点。ReInForM（Reliable Information Forwarding using Multiple paths）路由从数据源节点开始，考虑可靠性要求、信道质量以及传感器节点到汇聚节点的跳数，决定需要的传输路径数目，以及下一跳节点数目和相应的节点，实现满足可靠要求的数据传输。协议假设：假设每个节点到所有邻居节点的信道质量是相同的，适用于对通信服务质量有较高的要求的网络。 具体实现 (详见1第二章) ：ReInForM路由的基本过程是：首先，数据源节点根据传输的可靠性要求计算需要的传输路径数目；然后，在邻居节点中选择若干节点作为下一跳转发节点，并给每个节点按照一定比例分配路径数目；最后数据源节点将分配的路径数作为数据报头中的一个字段发给邻居节点。邻居节点在接收到数据源节点的数据后，将自己视作数据源节点，重复上述数据源节点的选路过程。优缺点分析：因为每一步传输都保证了源节点的可靠性要求，所以整个传输过程保证了数据传输的可靠性要求。SPEEDSPEED(详见1)是由Virginia大学计算机科学系实时与嵌人式实验室的TianHe等人于2003年在Hermes项目中提出的一种专门为传感器网络设计的实时通信协议，它利用节点的地理位置信息进行局部的路由决策。协议假设：假定知道节点的地理信息，适用于需要根据采集数据实时作出反应的网络。具体实现：（详见1第二章）SPEED协议主要由以下几部分组成：（1） 延迟估计机制，用来得到网络的负载情况，判断网络是否发生拥塞；（2） SNGF算法（stateless non-deterministic geographic forwarding, SNGF）,用来选择满足传输速率要求的下一跳节点；（3） 邻居反馈策略（neighborhood feedback loop, NFL）,是当SNGF路由算法中找不到满足传输速率要求的下一跳节点时采取的补偿机制；（4） 反向压