13522895871
自组网路由协议
发布者:mesh自组网电台浏览次数:发布时间:2020-09-25

与单跳的无线网络不同,自组网节点之间需通过多跳数据转发机制进行数据交换,每个节点都可能充当其它节点的路由器。无线信道质量的不规则变化,节点的移动、加入和退出等均会引起网络拓扑结构的动态变化。自组网路由协议的作用就是在这种环境中,监控网络拓扑结构的变更,交换路由信息,定位目的节点位置,产生、维护和选择路由,提供网络的连通性。路由协议是移动节点互相通信的基础。

常规的路由协议,如路由信息协议(RIP)[29]和开放式最短路径互连(OSPF)[30]是为有线网络而设计的,它们的拓扑结构相对固定,不会出现大的网络结构变化。自组网结构则是动态变化的,若仍使用常规路由协议,则将会在路由发现和维护上付出很大的代价,而全网路由也可能始终处于不收敛状态。除此之外,自组网不能采用常规路由协议还包含如下几种方面的原因:

(1)     自组网中主机间的无线信道可能是单向的;

(2)     若仍使用常规路由,则无线信道的广播特性将产生许多冗余链路;

(3)     常规路由协议路由信息的周期性广播更新报文会消耗大量的网络带宽。由于无线信道本身的物理特性,它所能提供的网络带宽相对有线信道要低得多。此外,考虑到竞争共享无线信道产生的碰撞、信号衰减、噪音干扰、信道间干扰等多种因素,节点可得到的实际带宽是远远小于理论上的最大带宽值;

(4)     无线移动终端的局限性。移动终端在带来移动性、灵巧、轻便等好处的同时,其固有的特性,例如采用电池一类可耗尽能源提供电源,内存较小,CPU性能较低等要求路由算法简单有效,实现的程序代码短小精悍,需要考虑如何节省能源等。而常规路由协议通常基于高性能路由器作为运行的硬件平台,没有上述的限制。

由于自组网路由协议对自组网的重要性,它便成了研究的一个热点。到目前为止,已经有相当多的标准和草案推出。当前提出的自组网路由协议可依两种标准进行分类,一是以触发时机进行分类,一是以网络拓扑结构进行分类。

2.1依据触发时机分类

根据路由触发原理,目前的路由协议可分为三类:

1)基于路由表驱动(Table Driven)的路由协议

2)按需驱动(On-Demand Driven)的路由协议

3)表驱动和按需驱动的混合

2.1.1表驱动路由

表驱动路由(又称先验路由、主动路由)继承了传统的路由算法,但在消除路由环路和已过时路由等方面进行了适应于自组网特性的改进。传统有线网络的经典路由算法包括链路状态协议和距离矢量两种。链路状态协议中每个节点都要保存整个网络的拓扑信息以及每条链路的开销,为了使所有节点中保存的路由保持一致,每个节点必须周期性地广播其与周围邻居节点的路由信息,其它节点在收到这些信息时更新网络拓扑,以最短路径算法来计算到达目的节点的下一跳节点。然而,某些节点保存的路由可能因为传播的延迟等原因与实际网络中的状态不一致,这时就可能会在网络中生成路由环路。距离矢量算法也会导致路由环路的生成。路由环路问题在无线环境下表现地更为明显,所以继承传统路由协议的表驱动路由协议需在此方面进行了改进。

表驱动路由协议中无论路由是否被用到,每个节点都要进行周期性地路由信息交换以维护路由表。表驱动路由协议的优点是在有信息传送时不需要等待建立路由,源节点一旦要发送报文,可以立即获得到达目的节点的路由。而其在无需通信节点之间的路由维护则浪费了大量的网络带宽。常见的表驱动路由协议DSDV[31]HSR[32]GSR[33]WRP[34]FSR[35]等。

DSDV(Destination-Sequenced Distance-Vector Routing)协议通过修改RIP协议而得到,它基于Bellman-Ford算法。DSDV在每条路由信息中加人由目的节点产生的序列号,以避免路由环。

DSDV协议中,每个节点周期性地广播它当前的路由表(路由信息包括对应于每个目的节点的距离及最大序列号,还包含发送者自身的序列号,每广播一次就自动加1)。每个收到该广播报文的节点将报文中的对应各目的节点的序列号与自身路由表中相应表项比较,如果报文中的序列号较高,则更新自己的路由表,将发送者指定为下一跳,并将距离增加一跳。在序列号相等但是报文中路由距离更小的情况下,节点也要更新自己的路由表。

当一个节点发现链路失效时,它将所有通过该节点转发的路由的距离设为无穷并将其序列号加1。由于更新了序列号,因此这一消息会传播到整个网络。这样所有这些目的路由指向的目的节点都有效地与此节点断开,直到有新的序列号产生并包含新的路由信息。

HSR(Hierarchical State Routing)是一种用于分级网络的路由协议,高级节点保存它所有子孙节点的位置信息,沿从最高级的根节点到最低级的叶节点的路径为节点分配逻辑序列地址,可以用序列地址进行节点寻址。

GSR(Global State Routing)协议的工作原理与DSDV协议类似,在该算法中,每个节点维护邻居列表、拓扑表、下一跳节点表和距离表。邻居列表记录所有能侦听到该节点信息的节点列表。对于每个目标节点,拓扑表记录链路状态信息和该信息的时间戳(timestamp),下一跳节点表记录分组转发的下一跳节点,而距离表则记录到达目的节点的最短路径。当链路的状态发生变化时,通过比较报文与本地拓扑表中的目的节点路由序列号大小,决定网络拓扑表的修改,若拓扑表发生变化则广播给其它节点。

GSR协议中,较长的路由修改报文会浪费相当大的网络带宽,针对这一缺陷,FSR(Fisheye State Routing)对GSR进行了修改,FSR的路由信息报文中并不包含所有节点的信息,因此可大大缩短报文的大小。与中心节点的距离越近,信息交换越频繁,每个节点都可获得其邻近节点准确详尽的信息;而随着与中心节点距离的加大,交换频率开始减小,超过节点的鱼眼范围时,信息的准确性降低,但并不影响路由的正确选择。通过这种算法,可大大降低路由修改信息对网络的负荷。这种算法的拓扑组织结构像鱼的眼睛,所以称之为FSR。

WRP(Wireless Routing Protocol) 是一种距离向量路由算法,每个节点维护距离表、路由表、链路开销表和信息重传列表。信息重传节点列表记录信息更新报文中需要传送的信息序列以及需要对该信息更新报文作出确认的节点列表。节点周期性或者在链路状态改变的情况下交换路由表,信息更新报文中反馈节点列表中的节点需要确认其接收。如果从上次广播更新报文后节点没有新的路由信息需广播,则其需发送HELLO报文,以确认节点之间的连通性。如果节点没有发送HELLO信息,则认为节点的链路信息无效。当节点收到来自邻居节点的信息更新报文后,修改自身的距离表依据该报文寻找更好的路由。如果某个移动节点收到了新节点的HELLO信息,则把新节点信息填入路由表,并且把它自己的路由表发给新节点。

2.1.2按需驱动路由

与表驱动路由相反,源始发的按需驱动路由(又称反应路由)认为在动态变化的自组网环境中,没有必要维护去往其它所有节点的路由。按需驱动路由因其更适合自组网特性,近些年来更被关注。按需路由一般分为路由建立和路由维护两个过程。它仅在需要给目的节点发送报文而又没有去往目的节点路由的时候才按需进行路由发现。因此,路由表是按需建立的,它可能仅仅是整个拓扑结构信息的一部分。它的优点是不需要周期性的路由信息广播,节省了一定的网络资源。缺点是发送数据分组时,如果没有去往目的节点的路由,数据分组需要等待因路由发现引起的延时,不适合于实时性要求高的应用。

常用的按需驱动路由协议有DSR[36]AODV[37]TORA[38]LAR[39]等。

DSR(Dynamic Source Routing)协议是最早被提出的按需驱动路由协议。DSR的路由发现过程如图2.2所示,当源节点没有到达目的节点的路由时,它广播一个路由请求报文。每个收到该报文的中间节点附上自身的ID然后重新广播。当路由请求到达目的节点(或者某个知道某条到达目的节点的路由的中间节点)时,它就可以决定一条到达目的节点的完整的源路由。目的节点(或中间节点)将所得的源路由包含在路由响应报文中,然后沿着所得路由反向发送回源节点,也可以附带在目的节点的路由请求报文中。源节点收到路由响应报文后,它将源路由存人缓存,并置入每个数据报的报头。中间节点根据数据报头中的路由信息中转数据报文。

路由维护过程也需要使用缓存信息。如果数据报在逐跳传输过程中发现链路失败,则可以由中间节点用缓存中的可用路由来代替报头中含有失效链路的路由,同时向源节点发送一个路由错误报文。和其它路由控制报文一样,路由错误报文可以被中间节点监听到,并且根据它将中间节点中的失效路由删除掉。这样可以使缓存中的错误路由信息的影响最小。如果路由失效,源节点则重新开始一个新的路由发现过程。

AODV(Ad hoc On demand Distance Vector Routing)协议是在DSDV协议的基础上结合类似DSR中按需驱动的思想而提出的。它与DSR协议的不同之处在于报头并不携带路由信息,中继节点依据自身的路由表逐跳转发。因为在AODV协议中,各节点隐式地将路由请求和路由应答分组中的路由信息保存于自身的路由表中,而DSR却将完整地路由信息显示地保存在分组中。AODV基于双向路径的假设,不支持单向路径。

TORA(temporarily-ordered routing algorithm)协议是在有向无环图DAG(directed acyclic graphic)算法的基础上提出的一种按需驱动路由协议。它分为路由发现,路由维护,路由消除三个过程。TORA协议与其它按需驱动路由协议一样,首先在网中发送路由请求分组,但是在路由应答部分,则采用了DAG算法。其主要思想是:对于某一目标节点,网络中每个节点都保留了相对于它的“势能”。势能可以通过从目标节点的反向广播来获得。离目标节点越远的节点,势能越高,目标节点势能最低。在数据传播过程中,数据包会从高势能的节点向低势能的节点转发,最终流向目标节点。当局部链路发生变化时,只需要局部势能的调整,这种改变一般不会影响到全局。TORA协议的主要特点是控制报文定位在最靠近拓扑变化的一小部分节点处,因此节点只保留邻近点的路由信息。该算法中路由不一定是最优的,常常使用次优路由以减少发现路由的开销。

LAR(location aided routing)协议是一种依据节点物理位置信息而获得路由信息的算法。LAR协议从GPS获得位置信息,且每个节点需知道其它节点的平均运动速度。在路由请求分组中携带寻径范围信息,寻径范围依据位置信息和节点平均运动速度而得到。这样,只有在寻径范围内的节点才转发路由请求分组。当源节点在当前寻径范围内寻径失败时,它将扩大寻径范围。LAR协议的优点是在小范围内寻径,减少了寻径开销;缺点是依赖GPS提供的位置信息,限制了其应用范围。

2.1.3混合式路由协议

Ad hoc无线网络中单纯采用表驱动按需驱动路由协议都不能完全解决路由问题,因此,许多学者提出了结合表驱动和按需驱动路由协议优点的混合式路由协议。

ZRPzero routing protocol)协议[40]是一个表驱动和按需驱动路由协议的组合,网络内的所有节点都有一个以自己为中心的虚拟区。在区内使用表驱动路由算法,中心节点使用区内路由协议IARPIntra-zone Routing protocol)维持一个到区内其它成员的路由表,对区外节点的路由使用按需路由,利用区间路由协议IERP(Inter-zone Routing protocol)建立临时的路由。

混合式路由协议在小范围局部区域内使用表驱动路由协议,局部区域间则采用按需路由协议。这样可将表驱动路由协议的周期性广播限定在一个局部区域内,从而减轻由全网广播带来的路由负荷。混合路由协议实现了按需路由协议和表驱动路由协议强弱互补,具有相对低的带宽消耗和路由发现延迟。

2.1.4性能比较

衡量路由协议好坏的两个重要指标是路由发现延迟和路由开销。路由延迟是指源节点获取一个新的到达目的节点的路由所需的时间。平均路由发现延迟最小的是表驱动路由协议,其次是混合型路由协议,按需路由协议最长。

文献[42]对比了DSDVAODVTORADSR四种路由协议的性能。显然,在网络拓朴变更的情况下,表驱动的DSDV协议的路由开销是基本不变的。在拓朴变更不明显的情况下(pause time较大),按需驱动的DSRAODVTORA协议的路由开销远小于表驱动的DSDV协议。实际上,自组网总是要工作在拓朴变更较慢的情况下。因为,当拓扑结构变化快到一定程度时,任何基于路由协议的数据包转发已经成为不可能,泛洪(flooding)方式成为数据包传输的唯一选择,而泛洪将会耗费大量的网络带宽。

 

表驱动路由协议的负荷随着节点运动的加快虽基本保持不变,但在拓朴变更加快的情况下,无法及时收敛,从而造成大量的不可靠路由和路由环,引起丢包。图2.4给出的报文发送率证明了这一点。当拓朴变更剧烈时,DSDV的报文发送率急剧下降,此时按需驱动的路由协议表现较好。

       根据上面的结果可以得出结论,在路由开销和报文发送率方面,按需方式的路由算法要比表驱动的路由算法在性能上有明显的优势。如果某类网络对报文发送的实时性要求不高,能容忍路由发现延迟,则应优先考虑按需驱动的路由协议。

2.2依据网络拓朴分类

按网络的拓朴结构分,ad hoc网络路由协议可分为:

1)      平面结构路由

2)      层次结构路由

2.2.1平面结构路由

在平面结构中,网络中的所有节点都在同一水平位置并且节点的地位是平等的,彼此之间没有层次概念,不存在特殊节点,路由协议的鲁棒性好,通信流量平均地分散在网络中,此类协议主要用在小型网络中。DSR、AODV、ZRP、TORA、GSR、DSDV等都是基于平面结构的路由。平面结构路由的缺点是当网络规模很大时,可能会导致整个网络都充斥着路由信息报文,网络的可扩展性差。

2.2.2层次结构路由

当网络变得很大时,如果仅使用平面结构路由,则每个节点要维护的路由信息量很大,路由信息到达边缘节点也将花费很长的时间。对于规模较大的网络,层次结构(基于簇)路由可以被用来解决上面的问题在层次结构的路由中,网络由多个簇组成,节点分为三种类型:普通节点、簇首节点和网关,处于同一簇的簇首节点和普通节点共同维护所在簇内的路由信息,簇首节点负责所管簇的拓扑信息处理,簇间通过网关通信。分簇结构可以提高网络规模和减少路由开销,可扩展性好,符合人类管理大型系统的习惯,适合管理超大型网络。

分层协议主要包括成簇协议,簇维护协议,簇内路由算法和簇间路由协议。成簇协议解决如何在动态分布式网络环境下使移动节点高效地聚集成簇,它是分层路由协议的关键。簇维护协议要解决在节点移动过程中的簇结构维护,其中包括移动节点退出簇和加入新簇,而簇本身又会随着节点的加入和退出而产生和消亡。典型的分层结构协议有CBRPcluster based routing protocol[43]CGSR(Cluster head Gateway Switch Routing)[44]等,前者为按需驱动,否则为表驱动。
2.3小结

根据路由触发的时机,自组网路由协议分为表驱动、按需驱动路由协议以及表驱动和按需驱动融合模式路由协议。按需驱动是自组网路由协议引入的新思想,它只在源节点需要传输报文给目的节点时才启动路由发现过程,不依赖于传统表驱动路由协议的周期性路由交换,而且只维护需要通信节点间的路由,减小了路由开销。其缺点是传输前需要等待路由建立。但如果数据传输的实时性要求不高,则可以忽略这个因素。

根据网络拓朴结构,自组网路由协议分为平面结构和层次结构。对于小规模网络而言,平面结构路由简单而有效;但当网络拓朴变得很大时,层次结构路由协议则更适合,层次结构可以避免大规模网络结构中如果只采用平面结构路由则需要维护大量路由信息的问题,但是该结构也需要在簇形成和维护上付出开销。
 
本文转自2001年的《通信学报》清华大学史美林与英春的论文《自组网路由协议综述》。

友情链接

友链合作