无线网络中的动态源路由协议 董玫 （湖北黄冈职业技术学院电子信息学院 黄冈４３８００２） 摘要在无线网络迅速发展的今天，为实现无线网络中节点间的正常通讯，路由技术成为研究的关键。本文介绍了新型的无线 移动网络——Ａｄ ＨｏＣ网络的工作原理；分析了Ａｄ Ｈｏｅ网络中常见的两种路由机制：表驱动路由协议（Ｔａｂｌｅ—Ｄｒｉｖｅｎ Ｒｏｕｔｉｎｇ）和 按需驱动路由协议（Ｏｎ—Ｄｅｍａｎｄ，ＤＳＲ）；着重对典型的按需（Ｏｎ—ｄｅｍａｎｄ）ＡＤ Ｈｏｃ网络路由协议（Ｄｙｎａｍｉｃ Ｓｏｕｒｃｅ Ｒｏｕｔｉｎｇ，ＤＳＲ） 进行了分析和研究，并详细介绍了ＤＳＲ协议进行通讯的各节点需要维护的四个数据结构：路由缓存（ｒｏｕｔｅ ｃａｃｈｅ）、发送缓冲区 （ｓｅｎｄ Ｂｕｆｉｅｒ）、路由请求表（ｒｏｕｔｅ ｒｅｑｕｅｓｔ）和路由应答表（ｒｏｕｔｅ ｒｅｐｌｙ ｔａｂｌｅ）的设计与实现。 关键词无线Ａｄ Ｈｏｃ网络 路由发现 路由维护 动态源路由协议 中图分类号ＴＰ３９３ 文献标识码Ａ 文章编号１ １０９１３—５８８６ Ａ Ｒｅｖｉｅｗ ｏｆ Ｄｙｎａｍｉｃ Ｓｏｕｒｃｅ Ｒｏｕｔｉｎｇ Ｐｒｏｔｏｃｏｌ ｉｎ Ｗｉｒｅｌｅｓｓ Ｎｅｔｗｏｒｋ Ｄｏｎｇ Ｍｅｉ （Ｅｌｅｃｔｒｏｎｉｃ Ｉｎｆｏｒｍａｔｉｏｎ Ｉｎｓｔｉｔｕｔｅ，Ｈｕａｎｇｇａｎｇ Ｐｏｌｙｔｅｃｈｅｎｉｃ Ｃｏｌｌｅｇｅ，Ｈｕｂｅｉ Ｐｏｓｔｃｏｄｅ ４３８００２） （Ｈｕａｎｇｇａｎｇ Ｐｏｌｙｔｅｃｈｎｉｃ Ｃｏｎｅｇｅ Ｈｕａｎｇｇａｎｇ ４３８００２） Ａｂｓｔｒａｃｔ Ｗｉｔｈ ｔｈｅ ｑｕｉｃｋ ａｄｖａｎｃｅ ｏｆ ｗｉｒｅｌｅｓｓ ｎｅｔｗｏｒｋ ｉｎ ｔｈｅ ｃｕｒｒｅｎｔ ｄｅｃａｄｅ．ｒｏｕｔｉｎｇ ｔｅｃｈｎｏｌｏｇｙ ｗｉｌｌ ｂｅｃｏｍｅ ｔｈｅ ｋｅｙ ｉＳ— ｓｕｅ ｔｏ ｋｅｐｐ ｔｈｅ ｎｏｒｍａｌ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｗｏｒｋ ａｍｏｎｇ ｄｉｆｆｅｒｅｎｔ ｎｏｄｅｓ ｉｎ ｗｉｒｅｌｅｓｓ ｎｅｔｗｏｒｋ．Ｔｈｉｓ ｐａｐｅｒ ｒｅｖｉｅｗｓ ｔｈｅ ｎｅｗｅｓｔ ＡＤ Ｈｏｃ ｗｉｒｅｌｅｓｓ ｍｏｂｉｌｅ ｎｅｔｗｏｒｋ ｗｏｒｋｉｎｇ ｔｈｅｏｒｉｅｓ，ａｎｄ ａｎａｌｙｚｅｓ ｔｈｅ ｔｗｏ ｐｏｐｕｌａｒ ｒｏｕｔｉｎｇ ｓｃｈｅｍｅｓ ｃａｌｌｅｄ ｔａｂｌｅ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ ａｎｄ ｏｎ—ｄｅｍａｎｇ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏ１．Ａｓ ｏｎｅ ｔｙｐｉｃａｌ ｏｎ－ｄｅｍａｎｄ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ，ｔｈｅ ｄｙｎａｍｉｃ ｓｏｕｒｃｅ ｒｏｕｔｉｎｇ（ＤＳＲ）ｈａｓ ｂｅｅｎ ａｎａｌｙｚｅｄ ａｎｄ ｓｔｕｄｉｅｄ ｓｐｅｃｉａｌｌｙ．Ｔｈｅ ｄｅｓｉｇｎ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｔｈｅｓｅ ｆｏｕｒ ｄａｔａ ｓｔｒｕｃｔｕｒｅ：ｒｏｕｃｅ ｃａｃｈｅ，ｓｅｎｄ ｂｕｆｆｅｒ，ｒｏｕｔｅ ｒｅｑｕｅｓｔ ａｎｄ ｒｏｕｔｅ ｒｅｐｌｙ ｔａｂｌｅ，ｗｈｉｃｈ ｒａｅ ｒｅｑｕｉｒｅｄ ｔｏ ｂｅ ｍａｉｔａｉｎｅｄ ｆｏｒ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｎｏｄｅｓ ｏｆ ＤＳＲ ｐｒｏｔｏ— ｃｏ１．ａｒｅ ａｌｓｏ ｉｎｔｒｏｄｕｃｅｄ ｉｎ ｔｈｅ ｆｉｎａ１． Ｋｅｙｗｏｒｄｓ Ｗｉｒｅｉｅｓｓ ＡＤ Ｈｏｃ ｎｅｔｗｏｒｋ Ｒｏｕｔｅ ｍａｉｎｔｅｎａｃｅ ＤＳＲ 一、引言 二、动态源路由协议 目前存在着两种无线网络： 种是有基础设施的网络，这种 动态源路由协议（Ｄｙｎａｍｉｃ Ｓｏｕｒｃｅ Ｒｏｕｔｉｎｇ，ＤＳＲ）是一种典型 网络由若干个移动节点和被成为“基站”的基础设施组成，网络 的按需ｏｎ ｄｅｍａｎｄ）ＡＤ Ｈｏｃ网络路由协议，同时ＤＳＲ使用源路 中的移动节点直接与其通讯范围内的最近基站进行连接和通 由，即每个分组头部显式地包含了从源节点到达目的节点的完整 讯。另一种是没有基础设施的，通常称为ＡＤ Ｈｏｃ网络。 节点序列，使用源路由的任何中间节点都无需进行复杂的路由操 无线ＡＤ Ｈｏｃ网络是一种新型的无线移动网络，是由一组 作而只需根据分组头部的路由信息将分组转发到下一个节点即 具有路由交换功能的节点所组成的自治系统。在一个无线ＡＤ 可。ＤＳＲ协议只要由两部分组成的：路由发现（Ｒｏｕｔｅ Ｄｉｓｃｏｖｅｒｙ）和 Ｈｏｃ网络中，节点之间通过多条无线链路互相通信，所有的节点 路由维护（Ｒｏｕｔｅ Ｍａｉｎｔｅｎａｎｃｅ）。路由发现和路由维护协同工作保 利用共享的无线媒介互相联系。在这里没有基站等基础设施，每 证了节点维持的到达目的节点的路由的及时和有效性。 个节点不仅是接收和发送信息的终端，而且还为其他节点间的 路由发现允许处于ＡＤ Ｈｏｃ网络的节点动态地发现通往其 通信提供数据包的转发功能（即路由功能）。ＡＤ Ｈｏｃ网络的这些 它节点的路由信息，而不论目的节点是否在直接无线传输范围 特点，使得路由技术成为这种网络的关键技术之一。 内还是经过一个或多个中间节点。当源节点Ｓ要发送一个数据 从路由机制来划分，ＡＤ Ｈｏｃ网络中的路由可以分为表 分组到目的节点Ｄ，但是源节点并不知道到达目的节点的路由 驱路由协议（Ｔａｂｌｅ—Ｄｒｉｖｅｎ Ｒｏｕｔｉｎｇ）和按需驱动路由协议 信息时，源节点就会发起一个路由发现过程。为了建立一条路 （Ｏｎ—Ｄｅｍａｎｄ Ｒｏｕｔｉｎｇ）两大类。表驱动路由协议就是在网络 由，源节点广播一个路由请求（Ｒｏｕｔｅ Ｒｕｑｕｅｓｔ），当该请求分组到 中维持路由驱动表，当网络拓扑发生变化，网络就会更新路 达目的节点，或者是到达某个中间节点且该节点具有到达目标 由信息，并且这个更新的信息传遍整个网络。按需驱动路由 节点的路由信息时，这些节点就向源节点发送一个包含着ｓ到 协议就是只有在需要时才去寻找路径的。在源发起的随选 Ｄ的完整路由信息应答（Ｒｏｕｔｅ Ｒｅｐｌｙ）分组，源节点ｓ就会根据 驱动路由协议中，只有当源节点需要一条通往目的节点的 这些信息建立新的路由。 路径时，它才在网络中发起一次路由发现。路由建立以后由维 由于网络中各节点的移动性，网络拓扑随时会发生变化，一 护程序进行维护。 条路径中的某两个节点可能会因距离超出双方的传输半径或其 ＝ｈ ＼Ｉ与争＋１』 士 ．ｄ１． 它的原因诸如中间节点故障等而导致现存路由信息的失效。当 路由维护指明某个源路由失效时，就使用路由错误（ｒｏｕｔｅ ｅｒｒｏｒ） （２）此节点发起路由请求的时间； （３）自收到有效的通往目的节点的路由应答以来，向目的节 分组通知源节点Ｓ，源节点Ｓ就会尝试使用其它可以到达目的 点发起的路由发现的次数； 节点Ｄ的路由路径，或者再发起一次路由发现过程来寻找一条 （４）节点下次向目的节点发起新的路由发现的剩余时间。节 新的路由，这个过程被称为路由维护。 点应该在每次的路由发现中按照指数后退法来决定下一次的路 三、ＤＳＲ协议的数据结构分析 使用ＤＳＲ协议进行通讯的任何节点需要维护如下四个概 由时间。 ４、路由应答表 此表保存了本节点发送的Ｇｒａｔｕｉｔｏｕｓ路由应答的信息。节点 念性数据结构，即路由缓冲（ｒｏｕｔｅｃａｃｈｅ）、发送缓冲区（ｓｅｎｄ ｂｕｆｆｅｒ）、路由请求表（ｒｏｕｔｅ ｒｅｑｕｅｓｔ）和路由应答表（ｒｏｕｔｅ ｒｅｐｌｙ 利用此表来限制它发往同一个源节点的Ｇｒａｔｕｉｔｏｕｓ路由应答信 ｔａｂｌｅ）。 １、路由缓存 一个使用ＤＳＲ参与ＡＤ Ｈｏｃ网络的节点所需要的所有路由 信息都存储在路由缓存中。 ． 网络中的每个节点维护自己的路由缓存。当一个节点听到 ＡＤ Ｈｏｃ网络中节点之间的新链路时会将该信息添加进路由缓 存中；同样地当一个节点得知现存路由信息失效时，将会从路由 缓存中删除该信息，如果路由缓存溢出，需要采用ＬＲＵ（Ｌａｓｔ Ｒｅｃｅｎｔｌｙ Ｕｓｅｄ）算法或者ＦＩＦＯ（Ｆｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）算法来进行淘汰 处理。 每当节点把新的路由信息加入到它的路由缓存中时，节点 应该检查在发送缓冲区ｓｅｎｄ ｂｕｆｆｅｒ）中的每一个包来看是否在 路由缓存（ｒｏｕｔｅ ｃａｃｈｅ）中有此包的目的节点的路由信息，如果有 的话，则应该发送此包，然后把它从发送缓冲区中删除。 路由缓存应该包括支持为每一个目的地址保存多条路由。 可以把目的地址做为索引来查找路由信息。 （１）每一个节点应该选择一个算法来查找路由缓存以及最 佳路由； （２）如果存在到达目的地的多条路由的话，算法应该优先 选择Ｅｘｔｅｒｎａｌ Ｆｌａｇ没有置位的路由； （３）此外，任何选择好的路由决不含有Ｅｘｔｅｒｎａｌ未被置位， 除了第一跳，最后一跳或者两者都有，也就是说任何中间节点的 Ｅｘｔｅｒｎａｌ位不应该置位。 ２、发送缓冲区 节点的发送缓冲区是一些由于该节点没有一个到达目的节 点的源路由而不能被该节点发送的分组组成的队列。一般来讲， 节点在将分组插入发送缓冲区的同时就会发起一个路由发现过 程，如果路由发现过程成功的话，这些分组就会被发送出去。在 发送缓冲区中的每个分组都标记了它进入发送缓冲区的时间， 当在被放入ＳＥＮＤ—ＢＵＦＦＥＲ—ＴＩＭＥＯＵＴ秒后，它将被丢弃，如果 必须的话，可以采用先进先出（ＦＩＦ０）策略将分组在没有超时时 将其丢弃以防止发送缓冲区的溢出。 ３、路由请求表 如果某节点发送或转发了发往某目的节点的路由请求分 组，则在接下来的ＤＳＲ—ＲＥＱ—ＴＩＭＥ—ＯＵＴ时间间隔内，该节点将 不允许再次向这个目的节点发送路由请求分组。节点的路由请 求表是最近该节点发出的或转发的路由请求分组的集合，其中 每一个条目都记录了其被插入路由请求表的时间，当超时后这 些条目将会被删除，如果路由请求表溢出，需要采用ＬＲＵ算法 来进行淘汰处理。此表一ＩＰ地址作为索引，路由请求表每一项 记录了如下的信息： （１）路由请求包中的ｒＩＴＩ’Ｌ字段，此节点发起到目的节点的 路由发现的上一次的路由请求； ・４２‘ 办公自动化杂志 息。表中的每一个条目包含了如下的字段： （１）路由应答所要发送到的源节点的地址； （２）本节点监听到的触发路由应答的那个包的发送节点的 地址； （３）此条目在表中的在过期前的剩余时间。当过期时，要把 它从此表中删除。当节点创建了一个新的条目往表中加入时，它 要把超时时间设置为ＧｒａｔＲｅｐｌｙＨｏｌｄｏｆ。 （４）当节点侦听到一个可能引发Ｇｒａｔｕｉｔｏｕｓ路由应答的包的 时候，首先检查在表中是否存在相应的条目，如果有的话，则此 节点不应该再发送路由应答了。否则的话，节点应该创建一个新 的条目并把它加入到表中。 四、ＤＳＲ在Ａｄ Ｈｏｃ网络环境中的优势 总而言之，相对于传统路由协议，ＤＳＲ在Ａｄ Ｈｏｃ网络环境中 具有许多优势。首先，ＤＳＲ不使用周期性的路由广播，降低了网 络宽带的额外开销，尤其是在网络中节点没有显著移动时。 其次，基于距离矢量和链路状态协议的传统路由协议可能 会计算出一些不能在Ａｄ Ｈｏｃ网络中工作的路径：在无线环境 中，一对主机可能在相应的两个方向沙锅内传输效果不一样，因 为在这两个主机周围可能存在不同的传播模式或干扰模式。例 如距离矢量协议，尽管主机Ａ能够收到主机Ｂ发出的路由广 告，但是从Ａ到Ｂ传送的信息却有可能无法到达Ｂ。尽管当物 理层协议能够做出如此的保证时，ＤＳＲ也会使用双向传输，但 是ＤＳＲ不要求主机之间的传输必须是双向。 最后，传统路由协议不是针对Ａｄ Ｈｏｃ网络中存在的动态拓 扑变化而设计的。ＤＳＲ协议能够迅速适应节点移动后带来的拓扑 变化，而且在没有节点移动腈况下不添加额外的路由开销。 矽 参考文献 ［１】李光成．动态源路由协议（ＤＳＲ）在Ｌｉｎｕｘ下的实现ｆＪ１．天 津大学电子信息工程学报，２００３，２２：１－５． 『２］Ｊｏｈｎｓｏｎ Ｄ Ｂ，Ｍａｈｚ Ｄ Ａ．Ｄｙｎａｍｉｃ Ｓｏｕｒｃｅ Ｒｏｕｔｉｎｇ ｉｎ Ａｄ Ｈｏｃ Ｗｉｒｅｌｅｓｓ Ｎｅｔｗｏｒｋｓ［Ａ］．Ｉｍｉｅｌｉｎｓｋｉ；Ｔ，Ｋｏｒｔｈｅｄｓ Ｈ，ｉｎ Ｍｏｂｉｌｅ Ｃｏｍｐｕｔ— ｉｎｇ［Ｃ］．Ｉｓ．１．］：Ｋｌｕｗｅｒ Ａｃａｄｅｍｉｃ Ｐｕｂｌｉｓｈｅｒｓ．１９９６．１５３—１８１． ［３］Ｇａｌｌａｇｅｒ Ｒ，Ａ ｍｉｎｉｍｕｍ ｄｅｌａｙ ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｕｓｉｎｇ ｄｉｓ— ｔｒｉｂｕｔｅｄ ｃｏｍｕｔａｔｉｏｎ『Ｊ］．ＩＥＥＥ Ｔｒａｎｓ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，１ ９９７．２５（１）： ７３－８５． 【４】刘元安．Ａｄ Ｈｏｃ网络中的路由算法 北京邮电大学 报，２００４，２７（２）：１－７ 【５］朱雁辉．Ｗｉｎｄｏｕｗｓ防火墙与网络封包截获技术【Ｍ］．北 京：电子工业出版社，２００２．３９—７７． 作者简介 董玫（１９７２．１１．２０），女，湖北省黄冈市蕲春县人，实验师， 双师型教师，主要研究计算机应用技术及非线性编辑技术。