自组网路由协议模板.doc

-11-07 14:33 183人阅读 评论(0) 收藏 举报
与单跳无线网络不一样, 自组网节点之间需经过多跳数据转发机制进行数据交换, 每个节点都可能充当其它节点路由器。无线信道质量不规则改变, 节点移动、 加入和退出等均会引发网络拓扑结构动态改变。自组网路由协议作用就是在这种环境中, 监控网络拓扑结构变更, 交换路由信息, 定位目节点位置, 产生、 维护和选择路由, 提供网络连通性。路由协议是移动节点相互通信基础。
常规路由协议, 如路由信息协议（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无线网络中单纯采取表驱动或按需驱动路由协议都不能完全处理路由问题, 所以, 很多学者提出了结合表驱动和按需驱动路由协议优点混合式路由协议。
ZRP（zero routing protocol）协议[40]是一个表驱动和按需驱动路由协议组合, 网络内全部节点都有一个以自己为中心虚拟区。在区内使用表驱动路由算法, 中心节点使用区内路由协议IARP（Intra-zone Routing protocol）维持一个到区内其它组员路由表, 对区外节点路由使用按需路由, 利用区间路由协议IERP(Inter-zone Routing protocol)建立临时路由。
混合式路由协议在小范围局部区域内使用表驱动路由协议, 局部区域间则采取按需路由协议。这么可将表驱动路由协议周期性广播限定在一个局部区域内, 从而减轻由全网广播带来路由负荷。混合路由协议实现了按需路由协议和表驱动路由协议强弱互补, 含有相对低带宽消耗和路由发觉延迟。
2.1.4性能比较
衡量路由协议好坏两个关键指标是路由发觉延迟和路由开销。路由延迟是指源节点获取一个新抵达目节点路由所需时间。平均路由发觉延迟最小是表驱动路由协议, 其次是混合型路由协议, 按需路由协议最长。
文件[42]对比了DSDV、 AODV、 TORA、 DSR四种路由协议性能。显然, 在网络拓朴变更情况下, 表驱动DSDV协议路由开销是基础不变。在拓朴变更不显著情况下（pause time较大）, 按需驱动DSR、 AODV、 TORA协议路由开销远小于表驱动DSDV协议。实际上, 自组网总是要工作在拓朴变更较慢情况下。因为, 当拓扑结构改变快到一定程度时, 任何基于路由协议数据包转发已经成为不可能, 泛洪(flooding)方法成为数据包传输唯一选择, 而泛洪将会花费大量网络带宽。

表驱动路由协议负荷伴随节点运动加紧虽基础保持不变, 但在拓朴变愈加紧情况下, 无法立刻收敛, 从而造成大量不可靠路由和路由环, 引发丢包。图2.4给出报文发送率证实了这一点。当拓朴变更猛烈时, DSDV报文发送率急剧下降, 此时按需驱动路由协议表现很好。
       依据上面结果能够得出结论, 在路由开销和报文发送率方面, 按需方法路由算法要比表驱动路由算法在性能上有显著优势。假如某类网络对报文发送实时性要求不高, 能容忍路由发觉延迟, 则应优先考虑按需驱动路由协议。
2.2依据网络拓朴分类
按网络拓朴结构分, ad hoc网络路由协议可分为:
1)      平面结构路由
2)      层次结构路由
2.2.1平面结构路由
在平面结构中, 网络中全部节点都在同一水平位置而且节点地位是平等,相互之间没有层次概念, 不存在特殊节点, 路由协议鲁棒性好, 通信流量平均地分散在网络中, 这类协议关键用在小型网络中。DSR、 AODV、 ZRP、 TORA、 GSR、 DSDV等都是基于平面结构路由。平面结构路由缺点是当网络规模很大时, 可能会造成整个网络都充斥着路由信息报文,网络可扩展性差。
2.2.2层次结构路由
当网络变得很大时, 假如仅使用平面结构路由, 则每个节点要维护路由信息量很大, 路由信息抵达边缘节点也将花费很长时间。对于规模较大网络, 层次结构（基于簇）路由能够被用来处理上面问题。在层次结构路由中, 网络由多个簇组成, 节点分为三种类型: 一般节点、 簇首节点和网关, 处于同一簇簇首节点和一般节点共同维护所在簇内路由信息, 簇首节点负责所管簇拓扑信息处理, 簇间经过网关通信。分簇结构能够提升网络规模和降低路由开销, 可扩展性好, 符合人类管理大型系统习惯, 适合管理超大型网络。

分层协议关键包含成簇协议, 簇维护协议, 簇内路由算法和簇间路由协议。成簇协议处理怎样在动态分布式网络环境下使移动节点高效地聚集成簇, 它是分层路由协议关键。簇维护协议要处理在节点移动过程中簇结构维护, 其中包含移动节点退出簇和加入新簇, 而簇本身又会伴随节点加入和退出而产生和消亡。经典分层结构协议有CBRP（cluster based routing protocol）[43]、 CGSR(Cluster head Gateway Switch Routing)[44]等, 前者为按需驱动, 不然为表驱动。

2.3小结
依据路由触发时机, 自组网路由协议分为表驱动、 按需驱动路由协议以及表驱动和按需驱动融合模式路由协议。按需驱动是自组网路由协议引入新思想, 它只在源节点需要传输报文给目节点时才开启路由发觉过程, 不依靠于传统表驱动路由协议周期性路由交换, 而且只维护需要通信节点间路由, 减小了路由开销。其缺点是传输前需要等候路由建立。但假如数据传输实时性要求不高, 则能够忽略这个原因。
依据网络拓朴结构, 自组网路由协议分为平面结构和层次结构。对于小规模网络而言, 平面结构路由简单而有效; 但当网络拓朴变得很大时, 层次结构路由协议则更适合, 层次结构能够避免大规模网络结构中假如只采取平面结构路由则需要维护大量路由信息问题, 不过该结构也需要在簇形成和维护上付出开销。
今天先这些!