（计算机软件与理论专业论文）基于ns2的aodv路由协议算法性能对比研究.pdf

硕士学位论文 m a s t e r st h e s i s 摘要 近几年来随着移动用户的持续增长，a dh o c 网络越来越多的受到人们的关注。 a dh o c 网络具有自组织，多跳，无中心特性。具有无线通讯设备的自治节点不需要 任何已有的设施就能组网。网络中的每个节点既可以是主机也可以是路由器。a dh o c 网络的拓扑结构是不断变化的，同时移动节点有能量和传播范围等限制。传统的路 由协议已无法满足它的要求。更适合移动节点特性的路由协议不断的被讨论，其中 最流行的就是按需路由协议。 a o d v u u 是在现实环境中实现的a o d v 路由协议，本文将a o d v - u u 和n s - 2 中已有的 模拟环境中的a o d v 协议做了性能对比。 o d v - u u 在包处理等机制上与后者有很大的 不同。本文的主要内容安排如下： 首先介绍a o d v 路由协议的基本原理，包括协议帧的类型，协议的路由建立过程 和维护操作。并介绍了现实环境中实现协议所需做的改进。然后介绍了i e t f 在研究 a dh o c 网络时所使用的a o d v - u u 。a o d v - u u 是a o d v 协议在l i n u x 下的协议实现，使用c 语言编写并在g n u 公共通用许可证下发布。a o d v - u u 支持i p v 6 和组播并和r f c 3 5 6 1 完 全兼容。本文重点分析a o d v u u 的软件模块和包处理方式。软件模块分为内核相关 模块和内核无关模块。包分为控制包和数据包，包处理方式按照包的类别分别处理。 接着介绍网络模拟器n s - 2 无线模拟核心移动节点的配置，模拟场景的设置，以 及模拟输t f l t r a c e 文件的格式分析和处理数据工具g a w k 及其对应的数据处理代码。最 后用n s - 2 对a o d v 和a o d v u u 分别从分组投递率，端到端的平均延迟和路由开销这 三方面进行了对比性能分析，通过结果可以看出a o d v u u 整体性能要优于a o d v 。 关键词：a dh o e 网络；a o d v ；a o d v - u u ；n s - 2 仿真 硕士学位论文 m a s t e r st h e s i s a b s t r a c t d u r i n gr e c e n ty e a r s ，w i t ht h em o b i l i t yo f u s e r sc o n t i n u e st oi n c r e a s e ，m o b i l ea dh o e n e t w o r kh a sb e i n gg a i n e dm o r ea n dm o r ea t t e n t i o n a dh o en e t w o r ki s s e l f - b u i l t , m u l t i - h o p ，d i s t r i b u t e d a u t o n o m o u sn o d e sw i t hw i r e l e s sc o m m u n i c a t i o ne q u i p m e n tf o r m an e t w o r kw i t h o u ta n yp r e e x i s t i n gi n f r a s t r u c t u r e e a c hn o d ei na dh o cn e t w o r kc a nb e u s e da sr o u t e ra sw e l la san o d e a dh o en e t w o r k t o p o l o g yi sc o n s t a n t l yc h a n g i n g a t t h es a m et i m e ，t h em o b i l en o d eh a sr e s t r i c t i o n so nt h ee n e r g ya n dt h es c o p eo f d i s s e m i n a t i o n t r a d i t i o n a lr o u t i n gp r o t o c o l sh a v eb e e nu n a b l et om e e ti t sr e q u i r e m e n t s r o u t i n gp r o t o c o lw h i c hi sm o r es u i t a b l ef o rc h a r a c t e r i s t i c so fm o b i l en o d ec o n t i n u o u s l y b e e nd i s c u s s e d ，t h em o s tp o p u l a ro n ei so n d e m a n dr o u t i n gp r o t o c 0 1 t 1 1 ef o l l o w i n ga r e t h em a i nc o n t e n t so ft h i sp a p e r a o d v 二u ui so n eo fa o d vp r o t o c 0 1 w h i c hi s i m p l e m e n t e di nr e a lw o r l d e n v i r o n m e n t t l l i st h e s i sc o m p a r e dt h ep e r f o r m a n c eb e t w e e na o d v - u ua n dp r o t o c o l w h i c hi sa l r e a d ye x i s t si nn s 2s i m u l a t i o ne n v i r o n m e n t a o d v - u ui sv e r yd i f f e r e n tf r o m t h el a t e rp r o t o c o li np a c k e th a n d l i n g 强ef o l l o w i n ga r et h em a i nc o n t e n t so ft h i sp a p e r t h eb a s i cp r i n c i p l e so fa o d vi si n t r o d u c e di nt h i st h e s i sf i r s t l y , i n c l u d i n gt h et y p e o f p r o t o c o lm e s s a g e ，t h ep r o c e s so fe s t a b l i s h i n ga n dt h eo p e r a t i o no fm a i n t e n a n c ea n dt h e r e q u i r e m e n to fi m p r o v e m e n ti nr e a l w o r l de n v i r o n m e n tt oi m p l e m e n tt h ep r o t o c 0 1 a o d v 二u uw h i c hi sar o u t i n gp r o t o e o lt r a d e ri n v e s t i g a t i o nb yt h ei e t ff o ru s ei na dh o e n e t w o r k si si n t r o d u c e d a o d v - u ui sal i n u xi m p l e m e n t a t i o na o d vp r o t o c 0 1 i tw a s w r i t t e ni nt h ecp r o g r a m m i n gl a n g u a g ea n dh a sb e e nr e l e a s e du n d e rt h eg n ug e n e r a l p u b l i cl i c e n s e ( g p l ) a o d v 二u us u p p o r t si p v 6a n dm u l t i c a s t i n ga n di sc o m p l i a n tw i t h r f c 3 5 61 t h ef o c u so fa o d v 二u ui nt h i st h e s i si ss o f t w a r em o d u l e sa n dp a c k e t p r o c e s s i n g t h es o f t w a r em o d u l e sd i v i d ei n t on o n k e r n e l 。r e l a t e da n dk e r n e l r e l a t e d s i m i l a r l y , p a c k e t sd i v i d ei n t oc o n t r o lp a c k e t sa n dd a t ap a c k e t s m o b i l en o d ew h i c hi st h ec o r ep a r to fn e t w o r ks i m u l a t o rn s 2i nw i r e l e s ss i m u l a t i o n i sp r e s e n t e dt h e n f o l l o w e db ys i m u l a t i o ns c e n a r i os e t t i n g sa n dt h ef o r m a ta n a l y s eo f t r a c ef i l e f u r t h e r m o r e ，t h ep r o c e s s i n gc o d eo ft h ed a t ai nt r a c ef i l e sw h i c hi s p r o g r a m m i n gi na w ki si n t r o d u c e d f i n a l l yu s i n ga s 一2t os e p a r a t e l ys i m u l a t ea o d va n d a o d v - u uf r o mp a c k e td e l i v e r yr a t e a v e r a g ee n dt oe n dd e l a ya n dr o u t eo v e r h e a d ，a n d c o n c l u d et h a ta o d v _ u uh a sab e t t e rp e r f o r m a n c et h a na o d v k e yw o r d s ：a dh o cn e t w o r k ；a o d v ；a o d v - u u ；a s 一2s i m u l a t i o n 硕士学位论文 m a s t e r st 珏e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名： 骼常钫 1 日期： 6 月罗日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同意华中 师范大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 v 7 作挂名：阱念导师始钐硌午 喊呷月弓日 呐：州年月罗日 作者签名：睬沸惫导师签名：0 佩毫 日期：1 年月弓日 日期矽川年6 月多日 硕士学位论文 m a s t e r st h e s i s i i 选题背景 第一章引言 移动节点联机组成a dh o c 网络的想法是在d a r p a 研究无线分组网络时提出来 的。近期由于免授权和便携式电脑用户可以彼此使用无线通讯设备交流而更受关 注。a dh o c 网络是由多个装备有无线通讯和具有网络功能的移动节点组成的。每 个节点既可以做为移动主机也可以做为路由器使用。术语”a dh o c 指的就是根据 手头上的任务按不同的形式组织的网络。也即指a dh o c 网络的高适应性。 a dh o c 网络最大的特性是它不依靠任何已有的网络设施，当节点彼此靠的足够 近的时候，节点之间就可以按照需要组网。这就消除了对像路由器和基站等固定不 动的网络组件以及布线和中央管理的需求。a dh o c 网络中的节点要依靠其他节点来 转发网络通信。所以a dh o c 网络的功能和作用很大程度上依赖参与转发的节点特 征。从只提供参与节点的连接来而不提供到额外网络如因特网的连接来看，a dh o c 网络通常是自治的。理论上，多连接节点做为网络中的网关没有任何问题。 a dh o c 网络的另外一个重要特性是它的动态拓扑。由于拓扑结构频繁变动，以 及节点周围环境的变化，选择节点的路由协议需要特别考虑。传统路由协议如o s p f 和r i p 不能够有效适应这种动态拓扑。因此，需要针对a dh o c 网络的特定路由协 议。 a o d v 路由算法是为a dh o c 移动网络设计的一个路由协议，a o d v 是d s r 和d s d v 的综合，依赖中间节点建立和维护动态路由表，使用序列号来避免路由环路，支持 组播功能和q o s 。目前对于多是对各种a dh o c 路由协议如a o d v 、d s r 、d s d v 和o l s r 等在i i s 一2 下进行模拟做对比研究，以及a o d v 与改进a o d v 协议如a o m d v 、q a o d v 等 的对比研究。对某个特定协议的实现和模拟做对比研究较少，如a o d v - u u 与a o d v 。 1 2 路由协议研究现状 在a dh o c 网络中，一个包可能需要多跳到达目的节点。路由协议的主要目的就 是建立和维护路由表，包含包为到达目的节点下需要发送的下一站信息，节点使用 这个信息转发它们收到的包。 路由并不是计算机网络中的新问题。链路状态路由和距离矢量路由已经存在了 硕士学位论文 m a s t e r st h e s i s 很长时间并在传统网络中被广泛使用。尽管如此，它们并不是非常适合在移动a dh o c 网络中使用，主要有以下原因： 它们是专门为准静态拓扑设计的。在a dh o c 网络中，网络拓扑结构频繁变 化，这些路由协议可能很难达到一个稳定状态。 它们是专门为有线网络设计的。在这样的网络中，链接被认为是双向的。 在移动无线网络中，情况并不总是这样；不同的无线网络硬件节点和无线 电信号波动可能引起单向链接。 它们试图维护到所有可达目的节点的路由。在有非常大数量节点的移动a d h o c 网络中，如大规模无线传感网络，因为会导致非常多的实体数量而变得 不可行。 在移动a dh o c 网络中，由于所有节点竞争访问无线介质，定期的泛洪路由 相对来说是昂贵的。 因此，a dh o c 网络需要特定路由协议。 a dh o c 路由协议通常按他们使用的维护和更新路由表的方法来分类。两个主 要的方法是： 先应式( 表驱动) 操作：在这个方法中，路由协议试图维护到网络中所有其 他节点路由的路由表。网络拓扑的改变通过更新在整个网络中传播，以确 保所有节点的网络信息是一致的。这种方法的优点是可以在任何时候在任 意可用的源一目的节点对之问路由。缺点是如果网络很大路由表将占用大量 的空间，并且频繁更新导致低网络资源的效率使用。 后验式( 需求驱动) 操作：在这个方法中，到目的节点的路由以按需方式路 由发现处理获得。获取的路由被路由维护处理知道路由不再需要或者变得 无效。这种方法的优点是可以避免不必要的路由信息交换，为其他网络流 量留出更多的网络资源。缺点是路由建立要花一定时间。根据不同的应用， 这可能是也可能不是能被接受的。 同样存在混合路由，将先应式和后验式方法混合。 如前面所述，针对a d - h o c 网络的特点路由协议需要包括如下的特定性质： 分布式操作：这是移动a d - h o c 网络的实质。因为移动a d - h o c 网络不依赖于任 何已有的设施，它的操作应该是分布式和去中心化的。 无环的：通常期望这样，虽然可能不是严格期望。确保没有环路可以帮助避免 最坏的场景，如包在网络中循环任意时间。 基于需求操作：路由协议可以按照它们的需求来发现路由。这可以避免浪费网 2 硕士学位论文 m a s t e r st h e s i s 络带宽。 先应式操作：如果基于需求的寻找路由开销对应用来说是不可接受的，并且网 络资源和节点允许。可以使用先应式操作。 安全：最好是路由有能力利用安全技术避免协议操作的中断和修改。 休眠时间操作：由于在移动a dh o c 网络中节点通常有限制的能量数量。所以 最好是路由协议有能力让节点可以暂时关闭来节约能量。 支持单向链接：因为无法保证在移动a d h o c 网络是双向链接的，所以能在双 方都使用单独的单向链接来代替双向链接是很有必要的。 i e t f 工作组m a n e t 开发了许多a d - h o c 协议。其中一个工作组专注于移动a dh o c 网络。他们近期的目标是标准化一个或者多个域内单播路由协议，当前，它们已经 发布了九个a d - h o c 路由协议草案，包括a o d v ( a dh o c 按需距离矢量) 、d s r ( 动态源 路幽) 、z r p ( 区域路幽协议) 、o l s r ( 最优链路状态协议) 、l a n m a r ( 界标路南协 议) 、f s r ( 鱼眼状态路由) 、i e r p ( 区域内路由协议) 、i a r p ( 区域问路由协议) 、 t b r p f ( 基于反向路径转发的拓扑广播) 。 1 3 本文所做工作 通过将现实环境下的路由协议和模拟环境下的路由协议在分组投递率，端到端 的平均延迟和路由开销这三方面做对比性能分析。总结这两者之问的表现区别，并 为现实协议移植到模拟环境中的性能变化，以及模拟环境与真实环境中的区别做比 较分析。 1 4 论文章节安排 本文共分为五章，各章的组织结构如下： 第一章为引言部分。介绍本课题研究背景和国内外研究动态和论文的主要目标 与论文框架。 第二章介绍a o d v 路由协议算法的工作原理 第三章介绍现实环境中实现协议所需做的修改以及a o d v - u u 实现框架。对每个 模块功能和相关函数进行了介绍。 第四章是a o d v 路由算法对比模拟研究。在模拟环境下分别对a o d v 与a o d v - u u 进行对比仿真并得出测试结果。 第五章为总结和展望。 3 硕士学位论文 m a s t e r st h e s i s 2 1 介绍 第二章a o d v 路由协议 a o d v ( a dh o co nd e m a n dd i s t a n c ev e c t o r ) 路由算法是为a dh o c 移动网络 设计的一个路由协议。a o d v 协议既可以单播也可以组播。它是一个按需算法，就是 说它只在源节点所期望的节点之间建立路由。只要源节点需要它就保持这些路由。 此外，a o d v 协议的生成树连接组播成员。树组成了组成员和需要连接这些成员的 节点。a o d v 协议使用序列号确保路线的更新。a o d v 是无环路，自启动，并可扩展 到大量移动节点的路由协议。 a o d v 协议用一个路由请求路由应答查询周期建立路由。当源节点需要一个还 没有路由信息到达的目的节点时，它在整个网络广播路由请求( r r e q ) 包。收到 此数据包的节点更新自己的关于源节点的信息，并建立向后指向源节点的路由表。 此外，除了包含源节点的i p 地址，当前的序列号，和广播i d 外，r r e q 包还包含源 节点已知的目的节点的最新的序列号。收到r r e q 的节点如果是目的节点，或它有 一个相应的序列号大于或等于r r e q 中的到目的节点的路由。它就单播一个r r e p 包 回到源节点。否则的话，它就转播这个r r e q 包。节点跟踪r r e q 的源i p 地址和广 播i d 。如果他们收到它们已经处理的r r e q 包，就丢弃不转发这个包。 当r r e p 包传播回源节点，节点就建立了到目的节点的路径。当源节点收到r r e p 包，它可能会开始转发到目的节点的数据包。如果源节点后来收到一个有更大或相 同序列号但有更小跳数的r r e p 包，它可以更新其到目的节点路由信息并开始使用 的这个更好的路由。 只要路由仍然是活动的，将继续得到保持。只要有数据包定期通过这条路由从 源节点到目的节点，那么这条路由认为是活动的。一旦源节点停止发送数据包，链 路将过期，并最终从中间节点路由表中删除。如果当路由是活动的时候一个链接中 断，其上游节点传播路由错误( r e r r ) 包给源节点向它通报现在无法目的节点。 在收到r e r r 包后，如果源节点仍然期望这条路由，它可以重新发起路由发现。 组播路由以相似的方式建立。一个希望加入组播组的节点广播r r e q 包，其目的 节点i p 地址设置为组播组的i p 地址并设置j ( 加入) 标志以表明它想加入该 组播组。任何收到此r r e q 包，并有一个非常新的序列号的组播成员节点可发送一 个r r e p 包。当r r e p 包传播回到源节点，节点在组播路由表中设置转发项。当源 4 硕士学位论文 m a s t e r st h e s i s 节点收到r r e p 包后，它继续追踪最新的序列号的路由，及最小跳数的下一个组播 组成员。在一定的发现周期后，源节点单播一个组播启动( m a c t ) 的信息到其选 择的下一跳。此消息的目的是启动路由。没有收到此消息的节点，将在已建立的多 播路由中使指向超时并删除这个指向。如果接收m a c t 包的节点还不是多播树的一 部分，它也将一直追踪从r r e p 包收到的最佳路径。因此，它也必须单播一个m a c t 包到其下一跳，并依此类推，直至达到以前的一名成员组播树节点为止。 2 1 1 与传统网络的比较 传统网络或多或少由固定设施组成，节点、路由器、交换机、网关、网桥、基 站和其他网络设备都是有线连接。这些网络的主要特点就是他们的拓扑结构基本是 固定不变的。任何重新构造网络或者添加网络设备都需要物理层参与。此外，网络 的管理通常是中心化的。因为许多节点依靠中心提供存储、访问和处理数据的服务。 一般的无线网络和某些a dh o e 网络可以解决这个问题，通过使用无线通讯来代 替固定电缆解决了电缆的配置和因此而造成的停机。理想情况下，a dh o e 网络和传 统有线网络相比可以实质上的无障碍安装和操作。同样，因为a dh o e 网络由节点自 身构成，网络拓扑结构可能频繁变化，中心化管理也不像传统网络那样常见。 在传统网络中，地址和其他网络参数或者是手动分配或者是交由特定的协议如 d h c p 处理。网络接口的硬件地址可以用地址定位实体检查，并可以指派i p 地址到 节点。在a dh o c 网络中，因为没有明显中心管理来负责地址的处理，所以编址问 题变得更加复杂。此外，由于节点的移动性，不能保证完全根据节点的地理位置编 址。 在传统网络中，路由依靠特定的路由器，可以是专门的基于硬件的路由器，或 者是装备几个网络接口并配备软件来实现实际路由的计算机。在a dh o e 网络中，路 由靠参与的节点自身实现。每个节点都有转发其他节点通信的能力。这使得通信通 过多跳传送成为可能。不像传统网络中的固定路由器，a dh o e 网络节点不需要配备 多个网络接口，因为所有通讯通常都是通过单无线信道传输的。另外一个区别是在 a dh o c 网络中没有划分子网的假设，而是使用平面编址结构。在传统网络中，路由 表通常包括网络前缀以及网络接口标识符。 2 1 2a dh o e 网络存在的问题 由于移动无线a dh o e 网络使用无线介质进行数据传输，访问介质必须控制以 防止节点试图同时传输数据，m a c 协议如8 0 2 1 1 提供这种控制。无线网络中一个著 5 硕士学位论文 m a s t e r st h e s i s 名的问题是隐藏终端问题。当在各自无线电范围之外的两个节点，同时试图向在它 们无线电范围之内的中间节点传送数据时发生。没有节点意识到另外节点的发送， 从而在中间节点处发生冲突。为了避免这个问题，可以使用握手协议，如r t s c t s 握手协议。试图发送数据的节点发送r t s 帧到接收节点请求获得发送许可，接收节 点然后回复c t s 帧授权这个请求。c t s 帧可以被所有在接受节点无线电范围之内的 节点收到，指示它们不要使用这个无线介质。然后请求的节点可以发送数据到接收 节点。 另外一个问题是暴露节点问题。当一个节点收到其他节点的传送从而限制发送 任何数据，即使这个通讯因为节点的无线电范围限制不会发生冲突。很明显，暴露 节点问题带来无线介质的次优化利用。一些提议的解决方案是使用定向天线或者是 分别为控制和数据设置信道，为了平衡节点间的传输能力，减少接口的同时可以节 省节点能量。 另一个研究领域是为节点分配独一无二的标识符问题。需要分配多大的地址空 间并不是很显而易见的，因为事实上节点网络可以变成很大并且节点的移动可能非 常快。可能的解决方案是节点随机选择它们自己的i p 地址，并使用a r p 将网络硬 件地址转换成i p 地址，反之亦然。通过侦听来自其他节点的a r p 通信来检测地址 冲突，确定任何尝试使用已经被占的i p 地址。因为任何想单播发送数据包的节点 都需要分配唯一的地址，所以地址分配在当今的a dh o c 网络中仍然是一个主要的 问题。 在a dh o e 网络中，网络安全也是很重要的问题。靠未知中间节点转发敏感 数据是很不合适的甚至是致命的。需要采取对策来防止敏感数据在a dh o e 网络中曝 光。可以是使用传统的封装。尽管如此，因为缺乏网络设施和当局的信任，钥交换 技术和公用密钥体系应用在a dh o e 网络中会比较困难。网络安全同样包括处理a d h o e 网络中的d o s 攻击或者欺诈攻击。 2 2a o d v 路由算法 在a o d v 路由中，不在活动路径上的节点既不维护任何路由信息也不参与任何 周期性的路由交换。此外，节点不需要发现和维护到其他节点的路由直到这两节点 需要通讯或者前面的节点作为中问转发站提供另外两个节点的连接。 当移动节点对本地连接感兴趣，每个节点可以通过一些技术让其他邻居节点知 道，包括认为是本地广播的h e l l o 帧。在邻居内的节点路由表被组织成对本地移动的 优化反应时间和提供建立新路由的快速反应时间。算法的主要目标有： 6 硕士学位论文 m a s t e r st h e s i s 只有当需要时才广播发现包 区别本地连接管理和一般拓扑维护 传播本地连接的改变信息到需要这些信息的邻居移动节点 a o d v 使用和d s r 算法一样的广播路由发现机制。尽管如此，不同于源路由，a o d v 依靠中间节点动态建立路由表项。这种不同当有大量的节点时取得成功，因为在每 个数据包中携带源路由有更大的开销。为了维护节点间最新的路由信息，我们借用 了d s d v 中的目的节点序列号这一概念。与d s d v 不同的是，每个a dh o c 节点维护 单调增加的序列号来取代过时的路由信息。这些技术组合所产生的算法有效的利用 带宽并减少控制和数据通信的网络负载，对拓扑变化做出快反应并确保路由无环。 2 2 1 路径发现 当源节点需要和另外节点通讯而存路由表中又没有到该节点的路由信息时，就 会发起路径发现。每个节点维护两个单独计数器：节点序列号和广播i d 源节点通 过给邻居广播路由请求( r r e q ) 帧来发起路径发现。r r e q 帧包含以下字段： 对唯一标识了一个r r e q 帧。每个邻居要么返回到 源的r r e p 帧来答复r r e q 帧要么在增加h o p _ c n t 值后重新广播r r e q 帧到自己的邻 居节点。一个节点可能收到多个邻居的同样的路由广播包的多份副本。当中间节点 收到r r e q 帧，如果它已经收到一样的广播i d 和源地址的r r e q 帧，它就丢弃多余 的r r e q 帧并且不重新广播它。如果节点不能答复r r e q 帧，它就保持随后的跟踪信 息，目的是完成反向路径的建立。当建立转发路径的同时也最终会传送r r e p 帧。 反向路径建立 在r r e q 帧中除了广播i d 外还有两个序列号：源序列号和最新的到源的目的序 列号。源序列号用来维护到源的反向路由的新旧度，目的序列号指定到目的的路由 在被源接受之前有多新。 当r r e q 从源节点传送到多个目的节点，它自动建立每个节点到源节点的反向路 径。为建立反向路径节点记录收到r r e q 帧第一份拷贝的邻居地址。这些反向路由 项被维护足够长的时间以便r r e q 帧在网络中传送并产生到发送端的应答。 转发路径建立 最终r r e q 帧将到达拥有当前到目的节点路由的节点，这个节点也可能是目的节 点本身。接收节点先检查通过双向连接收到的r r e o 帧，如果中间节点有到期望的 7 硕士学位论文 m a s t e r 。st h e s i s 目的节点的路由项，它通过比较自己路由项中的目的节点序列号和r r e q 帧中的目 的节点序列号来判定路由是否是新的。如果r r e q 帧中的目的节点序列号比中间节 点的记录大，中间节点就不能用记录的路由来回复r r e q 帧。而是重新广播这个r r e q 帧。中问节点只有当它的路由中的序列号等于或大于r r e q 帧中的序列号时才回复。 如果它确实有最新的到目的节点的路由并且r r e q 帧先前没有被处理，节点就给收 到r r e q 帧的邻居单播路由回复帧( r r e p ) 。r r e p 帧包含下面的信息： 当包到达可以提供到目的节点路由的节点时，就建立源的反向路径。随着r r e p 传送回源，沿路的节点建立到发送r r e p 帧节点的转发指针，更新它的路由项中到 源节点和目的节点的超时信息并记录请求目的节点的最新的序列号。r r e p 帧决定的 不在路径上的节点的将在a c t i v er o u t et i m e o u t ( 3 0 0 0 m s e c ) 后超时并删除反向指 针。 收到r r e p 帧的节点传播第一个从给定源节点到源端的r r e p 帧。如果它后来又 收到r r e p 帧，只有当r r e p 帧比以前r r e p 帧有更大的目的节点序列号或者有相同 的序列号但是有更小的跳数时，它才更新它的路由信息并传播这个r r e p 帧。它阻 止任何其他收到的r r e p 包。这样就减少了传播到源的r r e p 帧数量并确保最新和最 快的路由信息。源节点当第一个r r e p 帧收到后就可以发送数据包，并可以在知道 更好的路由后更新路由信息。 2 2 2 路由表管理 除了源序列号和目的序列号，路由表项还存储其他有用信息。伴随着反向路由 项的是计时器。计时器的目的是清除不在源节点到目的节点路径上的反向路由表 项。a dh o c 网络的大小决定了过时时间。另外一个重要的伴随路由表项的参数是路 由缓存时间，或者是说路由被认为无效的时间。 在每个路由表项中，通过接收到给定目的节点包得到的活动邻居地址也被维护。 如果邻居节点至少在最近的a c t i v e 时间内发起或转发一个包，那么就认_timeout 为是活动的。维护这个信息是为了当到目的节点的沿路连接出现中断时可以通知所 有的活动源节点。被用于任何活动邻居的路由项都认为是活动的。从源节点到目的 节点沿着活动活动路由项发送的路径被认为是活动路径。和d s d v 一样，所有路由 表中的路由都用目的节点序列号标记，这样可以保证即使在极端乱序包和高节点移 动性的情况下，不会出现路由环路。 移动节点维护每个感兴趣的目的节点的路由表项。每个路由表项包含下面的信 3 硕士学位论文 m a s t e r st h e s i s 息： 目的节点 下一跳 跳数( 单位米) 目的节点序列号 路由活动邻居 路由表项的过期时间 每次用于从源传输数据到目的节点的路由项，路由项中的超时被设置为当前时 间+ a c t i v e _ r o u t e t i m e o u t 。 如果提供移动节点的新路由，移动节点比较新路由与当前路由的目的节点序列 号。有更大的序列号的路由将被选中。如果序列号是一样的，只有当新路由有更小 的距离度量或者更小的跳数才被选择。 2 2 3 路径维护 如果源节点在活动会话期间移动，它可以重新发起路由发现过程来建立到目的 节点的新路由。当目的节点或者中间节点移动时，特别的r r e p 帧被发往受影响的 源节点。定期的h e l l o 帧可以用来确保同步连接，也可以用来检测连接中断。相反， 如果只有很少的延迟，这个错误可以用链路层应答检测到。当试图发往下一跳失败 时也可以检测到链路中断。 一旦下一跳变得不可到达，中断的上游节点就主动传播具有更大序列号的r r e p 帧并将活动上游邻居的跳数设置为无穷。这些节点继续转发该帧到它们的邻居，一 直这样继续下去，直到所有活动源节点都被通知到。因为a o d v 只维护无环路由并 且在a dh o c 网络中只有有限个节点，最终它会终止。 当收到中断连接的通知，源节点如果还需要到目的节点的路由可以重启路由发 现。为决定路由是否还需要，节点检查路由是否在近期被使用，同样检查上层协议 控制块看是否还在使用标示的到目的节点的连接。如果源节点或者其他在先前路由 中的节点决定重建到目的节点的路由，它就发送比以前已知的序列号更大的r r e q 帧，确保建立一个新的可行的路由并且认为以前路由合法的节点做出应答。 2 2 4 本地连接管理 无论何时当节点收到邻居的广播，它将更新自己的本地连接信息以确保包含这 个邻居。在h e ll o _ i n t e r v a l 时间内没有给下行邻居发送任何包的情况下，节点广 9 硕士学位论文 m a s t e r st h e s i $ 播h e ll o 帧( 一个特殊的主动r r e p 帧) 到邻居节点。h e ll o 传输中节点的序列号是不 变的。这个h e l l o 帧禁止被广播到其他节点的邻居，因为他包含的t t l 值为1 。收 到包的邻居更新节点的本地连接信息。收到广播或者新邻居的h e l l o 帧，或者无法 从先前邻居节点收到a l l o w e d _ h e l l o l o s s 个连续的h e l l o 帧，就表示本地连接已 经改变。无法收到不活动的邻居的h e ll o 帧不会触发协议行为。如果不是从活动路 径的下一跳收到的h e l l o 帧，活动邻居用一下跳发送连接中断的通知。 带h e l l o 帧的本地连接管理也可以用来确保只有双向连接的几点才被认为是邻 居。出于这个目的，节点对它所侦听到节点列表中的每个节点发送h e l l o 帧，节点 确保它只使用听到h e l l o 帧节点的邻居路由。为节约本地带宽，只有当显式配置节 点时才执行这样的检查。 2 2 5 组播 当网络节点加入一个组播组，一个由组播组成员组成的二叉共享树和需要连接 组成员的中间节点就被创建了。每个组播组伴随着它的组领导。组播领导的基本功 能是维护和传播组播序列号。这个序列号是用来维持组播组中路由信息的新1 日度。 希望加入一个组播组的节点可以广播一个设置加入标志的r r e q 帧。任何是组播 树成员的节点可以通过单播一个返回r r e q 发起者的r r e p 帧来做出应答。节点加入 组需要等待一段发现时期。在此期间收集r r e p 帧。任何转发r r e p 帧的节点必须保 持到组播树的最优路由轨迹。在发现时期的结尾，请求节点选择到组播树的最短路 由，并沿路由下一跳单播组播活动( m a c l ) 帧。当下一跳收到这个帧，它激活到组 播路由表的连接。如果这个节点已经是树成员，新树分支就完成了。否则，下一跳 依次单播m a c t 帧到朝向组播树的下一跳的邻居。过程按这种方式继续进行直到节 点已经是组播树的成员并且添加到组播分支完成。 l o 硕士学位论文 m a s t e r st h e s i s 第三章a o d v u u 3 1 实现协议所需做的修改 a o d v 在高负载网络中产生大量的路由开销并且时延也不断增加，这是其明显的 缺点。a o d v 中的路由开销主要包括路由请求( r r e q ) 、路由应答( r r e p ) 和路由错误 ( r e r r ) 包，本论文从路由发现和路由保持两个方面对a o d v 进行改进，通过减少各 分组的传送次数和降低路由过期时间来减少路由开销并降低时延。在路由发现过程 中，中间节点仅获得很少的路由信息，这就使得a o d v 需要经常的启动路由发现过 程。同时，由于网络拓扑结构的不断变化，路由需要进行不断的更新，但由于节点 的移动和拓扑的变化都会使得某些路由无效，从而造成r r e q 的多次重传。 3 i i 协议修改 a o d v 协议已经在用户态中作为路由守护进程实现。进程通过使用套接字和 l i n u x 内核通讯。在初始化过程中，a o d v 协议开放到内核的u d p 套接字。这种套接 字用于传送和接收a o d v 协议的控制包。a o d v 协议已使用端口号为6 5 4 ，因此当开 放套接字时使用这个端口。其他的通讯渠道包括i g m p 组播套接字，和n e t l i n k 路 由表更新套接字。这些套接字将在后面进行详细描述。 在a o d v 协议的实现开发过程中，在许多情况下会出现需要修改a o d v 协议或 l i n u x 内核。有些出于简化a o d v 路由协议模拟的变动是必要的，而另外的由于a o d v 协议与l i n u x 内核不兼容的变动也是必要的。以下将详细分析这些所需要的变动。 路由应答 a o d v 协议一个最基本的变动是其中r r e p 包的转发。当一个节点收到r r e q 帧， 如果它是目的节点或者有到目的节点的路由，节点将做出应答。在模拟中， r r e p 包原本只是从响应节点单播到源节点。随着r r e p 包的传送，中间节点更新路由表， 以包括一个到目的节点的路由。然而在实现中，这样并不起作用，因为如果r r e p 帧从响应节点单播到源节点，中间节点使用i p 转发，并不对包进行处理。因此， 协议需要做相应的修改以便r r e p 帧是以逐跳为基础的单播。此外，源节点i p 地址 字段添加到r r e p 帧以便最终目的节点的r r e p 帧将其保留。 当中间节点发送一个回复到源节点，目的节点不知道到源节点的路由，因为它 没有收到该路由请求。如果所有的路由请求都是由中间节点回复并最终导致目的节 硕士学位论文 m a s t e r st h e s i s 点从来没有收到一个r r e q 帧，那么目的节点将永远不会知道到源节点的路由。这 将对希望建立一个t c p 连接的源节点不利。为了让目的节点知道到源节点的路由， a o d v 协议所做的修改是使中间节点单播r r e p 帧到源节点来响应r r e q 帧的同时也发 送一个免费r r e p 帧到目的节点让其知道这条新路由。中间节点将目的节点i p 地址 填入r r e p 帧中的源i p 字段并将源节点i p 地址填入到目的节点i p 地址字段，由于 已经存在路由的节点。中间节点将从源节点的距离填入到h o p c o u n t 字段，并单播 这个r r e p 帧到目的节点。当目的节点收到这个r r e p 帧，它会知道一个到源节点 的路由。这个过程的一个例子如图3 - 1 所示。 酝薯基0 购尹宇姗帧 图3 1 免费r r e p 帧 为了减少免费r r e p 帧所带来的额外开销，我们在r r e q 帧中添加了一个( ；r a t r r e p 标志。如果会话将建立在t c p 上或者目的节点由于其他原因应收到免费r r e p 帧，源节点就设置这个标志。否则不设置这个标志。收到r r e q 帧并应答r r e p 帧的 节点只有当这个标志被设置才传送到目的节点的免费r r e p 帧。 d e l e t e _ p e r i o d 当一个节点重新启动，节点就会丢失其所有的路由信息，其中包括节点的序列 号值。当这个节点重新启动可能会造成路由环路。这是因为这个节点的邻居节点可 能仍然当这个重启的节点为到一个或多个目的节点的下一跳。如果重新启动的节点 尝试发现其中的一个目的节点，邻近节点可能作出应答，从而建立一条路由。为防 止这种情况，每个节点重启后在对任何路由信息做出应答之前等待一个 d e l e t e _ p e r i o d 时间。如果在此期间它收到数据包，由于它已经没有路由信息所以 就发送一个r e r r 帧到目的节点。此外，它重置等待定时器为当前时间加上 d e l e t e _ p e r i o d 以确保把它做为下一跳的所有路由都过期。 路由表 a o d v 路由守护进程通过使用n e t li n k 套接字来改变i p 路由表。每当a o d v 协议 添加，修改或者删除一条路由，它通过这个套接字传送到i p 的包，路