（通信与信息系统专业论文）在两跳拓扑环境下对aodv协议的改进.pdf

摘要 摘要 随着科技的发展，便携式计算机和掌上型电脑日益普遍，无线通信技术得到 迅速发展。a dh o c 网络是移动网络的一种特殊形式，不需要固定的基站，由一组 带有无线收发装置的自主的无线节点或终端通过相互合作形成的网络，是一种自 创造、自组织和自管理的网络。 a dh o e 网络路由机制必须适应网络三个不断变化的基本特征：移动节点的总 体密度，节点到节点的拓扑，网络的使用模式。目前a dh o e 网络的路由协议有表 驱动路由协议和按需路由协议。从移动自组网的移动性，拓扑动态性，带宽受限， 功率约束等特点来看，按需驱动路由更能适应移动a dh o e 网络的需要。 本文首先阐述了课题研究的意义、目的和国内外研究现状及发展趋势。然后 基于无线移动自组织网的网络环境，对a dh o e 网络的一种a o d v 路由协议进行 深入分析。提出一种两跳拓扑结构的概念，采用a o d v 路由协议作为网络层协议， 并且改进了传统的a o d v 路由协议算法，形成了改进的2 h o p a o d v 路由协议算 法。 2 h o p a o d v 协议中，每个节点通过周期性的发送h e l l o 消息，掌握自己两 跳邻居范围内的拓扑结构，路由表添加了记录下两跳的域。这样，在路由发现过 程通过报文携带的信息，记录下正向路由及反向路由的前两跳信息。在发起路由 请求的过程中，一旦节点发现目的节点在自己的两跳范围内，立刻做出应答，从 而凭借这种提前应答，减少路由寻找时延，也就减少了分组交付时延。 本文采用目前流行的仿真平台n s 2 ，在此平台的基础上，实现了2 h o p a o d v 路由协议算法。通过仿真比较传统的a o d v 路由协议和改进的2 h o p a o d v 路由 协议的性能，验证了2 h o p a o d v 协议算法在时延方面的性能明显优于原a o d v 协议。 关键字：a dh o e ，a o d v ，两跳拓扑，按需路由，路由建立 a b s t r a c t a bs t r a c t w i t ht h ed e v e l o p m e n to fs c i e n c ea n dt e c h n o l o g y , p o r t a b l ec o m p u t e ra n dp a l m t o p c o m p u t e ra r ei n c r e a s i n g l yp r e v a l e n t ，a n d t h ew i r e l e s sc o m m u n i c a t i o nt e c h n o l o g y d e v e l o p sp r o m p t l y i tn e e d ss o m ec o m m u n i c a t i o nt e c h n o l o g y t h a tn e e d n td e p e n do na n y n e t w o r kf a c i l i t ye r e c t e db e f o r eh a n d t h e na dh o cn e t w o r ke m e r g e sa st h et i m e s r e q u i r e a dh o en e t w o r ki so n es p e c i a lk i n do fm o b i l en e t w o r k st h a td o n tn e e df i x e d b a s es t a t i o n i t sas e l f - c r e a t i o n ，s e l f - o r g a n i z a t i o na n ds e l f - s u p e r v i s o r yn e t w o r kt h a t f o r m e db yt h ec o o p e r a t i o no fab o o d l eo fa u t o n o m i cw i r e l e s sn o d e so rt e r m i n a l s t h er o u t em e c h a n i s mo fa dh o en e t w o r ks h o u l dc o n f o r mt ot h r e e b a s i c f e a t u r e s ：t h ep o p u l a i o nd e n s i t yo f m o b i l en o d e ，t h et o p o l o g yo fn o d e s ，a n dt h eo p e r a t i n g m o d eo fn e t w o r k t h e r ea r et w ok i n do f r o u t i n gp r o t o c o l s f o ra dh o e n e t w o r k ：t a b l e d r i v e na n dd e m a n dr o u t i n gp r o t o c 0 1 c o n s i d e r i n gt h em o b i l i t y , d y n a m i co f t o p o l o g y ，b a n d w i d t hl i m i t a t i o na n dp o w e rr e s t r i c t i o n ，o n d e m a n dr o u t i n gp r o t o c o l sa r e m o r es u i t a b l ef o ra dh o cn e t w o r k t h et h e s i sf i r s t l yd e s c r i b e st h es i g n i f i e a n c ea n di t s t a r g e t ，i ta l s od e s c r i b e st h e c u r r e n ts t a t u so ft h es c h e d u l e a n dt h e nt h r o u g ha n a l y z i n ga o d vr o u t i n gp r o t o c o l so f a dh o cn e t w o r k 。2 h o p a o d vi sp r e s e n t e dw h i c hi sp r e f o r m e db ya o d vm u t i n g p r o t o c 0 1 r o u t et a b l ei n2 h o p a o d vi s e x t e n d e db ya d d i n gt w of i e l d st os a v et h e p r e v i o u st w oh o p a n dt h e n ，a c c o r d i n gt ot h ed i s c o v e r i e dp a c k e t s ，m a r k e dd o w nt h e p r e v i o u st w oh o po ft h er o u t e ra n dt h er e v e r s er o u t e r o n c ean o d ef i n d st h a t t h e d e s t i n a t i o ni si ni t st w o n e i g h b o ra r e a , i tr e p l y s ，b yt h i sa h e a dr e s p o n s i o n ，t h ed e l a yo ft h e t i m ei nf i n d i n gr o u t ec a l lb er e d u c e dc l e a r l y s i m u l a t i o nw i t hd i f f e r e n ts c e n e si sc o m p l e t e l yb a s e do nn s 2 ，t h ep o p u l a rs i m u l a t e d f o r m w o r k ，a n dp e r f o r m a n c eo f2 h o p a o d vi ss u p e r i o rt ot h ea o d v i nd e l a y k e y w o r d s ：a dh o c ，a o d v , 2h o pt o p o l o g y , o n d e m a n dp r o t o c o l ，m u t i n ge s t a b l i s h e d i i 图目录 图2 1 图3 1 图3 2 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图5 1 图5 2 图5 3 图5 4 图5 5 图5 - 6 图5 7 图5 8 图5 - 9 图5 1 0 图6 1 图6 2 图7 1 图7 2 图7 3 图7 4 图7 5 图7 6 图7 7 图目录 移动自组网4 a o d v 路由请求过程13 a o d v 路由应答过程15 d c f 中r t s ，d 筒r a 的重传1 9 邻居侦听2 0 h e l l o 消息格式2 4 两跳邻居链表2 4 h e l l o 的滞后2 5 两跳邻居节点移动的感知2 6 无选择泛洪和选择性泛洪3 0 提前应答方式3 4 序列号更新交互问题3 7 i 冰e p 分组暴3 8 减少r r e p 分组数量3 9 提前应答造成的相同序列号4 0 基于两跳邻居的a o d v 路由协议操作举例4 1 路由请求过程4 3 路由应答过程4 5 路由修复4 6 n s 2 层次图4 8 n s 2 框架图4 9 1 0 个源节点的分组交付率5 7 2 0 个源节点的分组交付率5 8 3 0 个源节点的分组交付率5 8 1 0 个源节点的端到端时延5 9 2 0 个源节点的端到端时延6 0 3 0 个源节点的端到端时延6 0 1 0 个源节点的相对路由开销6 1 v i 图目录 图7 82 0 个源节点的相对路由开销6 2 图7 - 93 0 个源节点的相对路由开销6 2 v i i 表目录 表5 1 表5 2 表目录 r r e q 报文格式4 4 r r e p 报文格式4 5 v i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：隘超日期：妒脾6 月上日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：艋导师签名： 弘阑 日期：山莎年6 月日 第一章引言 1 1 研究背景 第一章引言 随着社会的进步，人们对灵活、快捷、方便的通信方式要求越来越高，而全 球化进程的加快又进一步刺激了通信与网络技术的发展，人们不断追求任何人可 以在任何时间、任何地点与任何人进行任何种类的信息交换【l 】。 无线网络以其较之有线网络更灵活方便的通信方式，已经成为现代通信系统 中发展最迅速的，应用前景最广的重要组成部分。前者需要固定基础设施的支持， 移动主机之间的通信通常借助固定设施( 基站) 来完成，例如常见的蜂窝移动通 信系统和无线局域网。但这种方式存在的主要问题是移动用户在基站间的切换问 题，这要求用户在切换的同时，不能有明显的延迟和数据丢失。这种模式的另一 个问题是它利用了蜂窝移动通信的基站等基础设施，虽然带来了方便，但也限制 了它可以实现有效通信的范围仅仅只能够在其覆盖范围之内。 移动a dh o c 2 】网络是无线网络的另一种组织方法。这种自组织对等式多跳移 动通信网络，不需要依赖于固定的基础结构，既可以与现有的网络结合形成多跳 网络，从而有效延伸传统网络的覆盖范围，同时也可以通过临时组网的方式在恶 劣环境中支持移动节点之间的数据、话音、图像和图形等业务的无线传输。这也 使得a dh o c 网络具有极大的灵活性和可扩展性，可以满足不同场合的特殊需要， 其应用范围可以覆盖工业、商业、医疗、家庭、办公环境、军事等各种场合和行 业。特别是在军事应用领域中，因其特有的无需架设网络设施、可快速展开、抗 毁性强等特点，a dh o c 网络己成为数字化战场通信的首选技术。 a dh o c 网络不论是军用还是民用，都有着广泛的应用价值和重要的研究意义。 在a d h o c 网络研究中，因为每个节点兼具路由器的功能，所以路由是一个非常重 要的研究问题。与固定的有线网络不同的是，a dh o c 网络的突出特点：带宽较低、 通信链路质量不好，节点能量受限等决定了其路由协议的研究将面临许多不同于 传统网络的新问题和挑战。 由于组网快速、灵活、使用方便，无线a d h o c 网络已经得到了国际学术界和 工业界的广泛关注，并正在得到越来越广泛的应用，已经成为移动通信技术向前 发展的一个重要方向，并将在未来的通信技术领域中占据重要地 电子科技大学硕士学位论文 1 2 本课题研究来源及意义 最近几年来，i n t e r n e t 的应用得到了飞速发展，连入网络的主机和用户逐年呈 指数增长。与此同时，移动计算机网络业务己逐渐成为人们日益关注的话题。在 网络中提供移动性支持可使网络用户在任何时刻、任何地点通过网络发送和接收 各种数据，实现人们提出的“a n y t i m e ，a n y w h e r e ，m o b i l en e t w o r k si ny o u rp o c k e t ” 的愿望。 移动自组网作为移动计算的一种特殊形式，由于它不需要固定的基站，各个 节点均可自由移动，且能实现动态的链接。加上其具有生存性极强，创建与移动 极为方便的特点，使之弥补了蜂窝系统与有线网络的不足，在许多特殊情况下有 着不可替代的作用，可广泛应用于国防战备、灾难援助、法律执行等无法得到有 线网络支持或某些只是临时需要通信但建立有线通信网络代价太大的环境，且可 以作为生存性极强的后备网络。其应用范围可以覆盖工业、商业、医疗、家庭、 办公环境、军事等各种场合，尤其在未来战场上，a dh o e 网络对于高技术武器装 备、集中指挥、协同作战和提高作战机动性等具有非常重要的意义。 作为影响网络性能的一个重要因素，强壮的路由协议是确保移动自组网络正 确运行的关键。本文将从移动a dh o c 网络中的邻居信息的交互和探测，路由的建 立这两个方面做比较深入的讨论，而主要针对路由的稳定性和网络的时延等参数 进行相关改进。该课题将会为移动a dh o c 网络中某些应用和网络性能的改进提供 重要的参考和依据。 1 3 本论文的安排 本论文将在第二章介绍移动a dh o c 网络的基本特点，以及相关的路由协议。 第三章中详细介绍按需距离矢量路由a o d v 协议。 第四章先对现有的一些路由协议的邻居探测方法进行介绍，再此基础上，提 出一种两跳拓扑结构环境，并详细阐述在这种两跳拓扑结构环境下的邻居探测。 第五章将在两跳拓扑结构环境下，对a o d v 路由协议的路由建立过程进行理 论研究，其中包括对r r e q 的广播以及建立反向路由方面的改进，以及出现的问 题分析。 第六章对n s 2 仿真工具进行详细介绍。 第七章对a o d v 路由协议以及在两跳拓扑环境下的a o d v 协议进行了详细的 2 第一章引言 仿真，具体分两个部分：不同移动环境和不同的网络负载。通过仿真结果，证明 了在两跳拓扑环境下对a o d v 的改进能够带来一定的性能提升。 第八章对整个论文的工作做了总结，得n t 基本的结论。并对下一步需要继 续研究的问题进行了简要的论述。 l uf 科技大学硕士学位论立 第二章移动a dh o c 网络的相关研究 21 移动a d h o c 网络概念 移动自组网也呵称为m a n e t ( m 0 5 i l e a d h o e n e t w o r k s ) 或a d h o c 网，是 由一组带有无线收发装置的移动终端组成的一个多跳的临时性自治系统口l 。移动白 组网中的各节点不仅具有普通移动终端所需的功能，而且具有报文转发能力。当 通信的源肯点与目的节点不在彼此的直接通信范围之内时，它们便可通过其他节 点转发报文进行通信。凶此，m a n e t 巾的每个移动终端设备兼具主机和路由器两 种功能：作为主机终端需要运行面向用户的应用程序；作为路由器。终端需要 运行相应的路由协议，根据路由策略和路由表进行分组转发和路由维护工作。 圈2i 给出了一个由丘个节点组成的简单的移动自组网。 a 黔曼，e ， 、 ，、 、 。毛悬，曳。 d 图2 - 1移动自组网 如图所示移动节点a 与移动节点b 之口j 可以直接通信，但当彼此相距较远 的两节点如节点a 与节点e 需要交换信息时，由于移动节点的通信覆盖范围有限， 凼此它们需要通过节点d 或b 的转发才能完成信息交换。这里的移动节点d 和b 就发挥了路由器的作用。 2 2 移动a dh o c 网络特点 与其它传统通信网络相比，移动a dh o c 网络具有显著特点h 心，主要特征 包括以下几个方面： 第二章移动a dh o e 网络的相关研究 分布式操作 由于移动a dh o c 网络节点不能够依靠固定基础设施或者中心管理，无线移动 a dh o c 网络中的用户节点都兼备独立路由和主机功能，不存在一个网络中心控制 点，用户节点之间的地位是平等的，网络路由协议通常采用分布式控制方式，因 而具有很强的鲁棒性和抗毁性。而在常规通信网络中，由于存在基站、网控中心 或路由器这样一类集中控制设备，用户终端与它们所处的地位不是对等的。 带宽有限、链路容量易变 链路的容量明显低于有线信道。无线环境具有带宽有限、比特误码率高、链 路质量和链路容量起伏波动等问题。考虑到多址访问、衰落、噪声、环境干扰等 因素的影响后，无线通信的实际吞吐量常常比最大无线传输速率低得多。 移动性与网络拓扑动态性 移动a dh o c 网络中，移动用户终端可以以任意速度和任意方式在网络中移动， 加上无线通信诸多不稳定因素影响，使得移动终端间通过无线信道形成的网络拓 扑结构随时可能发生变化，而且变化的方式和速度都很难预测。而对于常规网络 而言，网络拓扑结构则表现较为稳定。 能量受限的节点 移动节点通常依靠电池提供工作所需的能量，而节点的移动性必然要求电池 便于携带，这就造成能量有限。因此减少功耗将是影响网络协议设计的一个非常 重要的因素。 物理安全有限 移动a dh o c 网络是一种特殊的无线网络，由于采用无线信道、有限电源、分 布式控制等原因，会比有线网络更易受到安全性的威胁。这些安全性的攻击包括 窃听、电子欺骗和拒绝服务等攻击手段。 除此之外，移动a dh o c 网络本身结构特点就决定了它还具有以下4 个特征。 多跳通信 由于节点无线收发机的信号传播范围有限，节点的覆盖范围有限。当它要与 其覆盖范围之外的节点进行通信时，需要中间节点的转发。而且，移动a dh o c 网 络中的多跳路由是由普通节点协作完成的，而不是由专用的路由设备( 如路由器) 完成的。这种多跳通信也带来了隐藏终端、暴露终端和公平性等问题。 网络的可扩展性不强 目前的i n t e m e t 具有较强的网络可扩展性。但是动态变化的拓扑结构使得子网 技术所带来的可扩展性无法应用在移动a dh o e 网络环境中，并且动态变化的网络 电子科技大学硕士学位论文 环境下，路由协议比较复杂，将会占用过多的带宽和网络开销。 存在单向的无线信道 移动a dh o e 网络采用无线信道通信，由于地形环境或发射功率等因素影响可 能产生单向无线信道。在常规网络中，节点间通常基于双向的有线或无线信道进 行通信。 生存时间短 移动a dh o e 网络的组网通常是由于某个特定原因而临时创建的，使用结束后， 网络环境将会自动消失。移动a dh o c 网络的生存时间相对于固定网络而言是短暂 的。 2 。3 移动a dh o c 网络路由协议 在a dh o c 网络中，移动节点通过多跳无线连接进行通信，移动节点既是用户， 同时又是中转站，没有固定设施的参与，也就形成了a dh o e 网络动态拓扑、带宽 受限、能量一定以及安全性不高等特点，a dh o e 网络需要的路由协议能够动态的 决定路由和适应网络的动态拓扑，这同时也决定了a dh o e 网络协议必须是自适应 自组织的、足够健壮和高效的才能满足a dh o c 网络一系列与传统无线网络不同的 要求。所以，研究出一种适合a dh o c 网络移动节点之间路由的动态路由协议就变 得非常的重要和关键。 可以根据网络节点获取路由信息的方法来对移动a dh o e 网络的路由算法进行 分类，大致可以分为两大类：一类称作表格驱动类路由协议，一类称作源接点初 始化按需驱动类路由协议。 2 3 1 表驱动路由协议 表格驱动类路由协议又称作主动式路由协议。主动式路由协议尽力维护网络 中每个节点至所有其他节点的一致的最新路由信息。主动式路由协议要求网络中 的每个节点都建立和维护一个或多个存储路由信息的表格。主动式路由协议对于 网络拓扑变化的反应是：向整个网络传播路由更新信息，因而从网络一致性的观 点来达到维护整个网络路由信息的一致性。各个主动式路由协议的差异主要表现 在两个方面：一是跟路由选择有关的、所必需的路由表格的数量的差异；二是有 关由网络拓扑变化所引起的路由变化信息在整个网络中的传播方法的差异。属于 主动式路由协议类的有d s d v 、w r p 、o l s r 等。 6 第二章移动a dh o c 网络的相关研究 d s d v d s d v t 6 1 ( d e s t i n a t i o n s e q u e n c e dd i s t a n c e v e c t o r ) 协议是一个基于传统 b e l l m a n ，f o r d 算法的路由选择协议。该协议用目的端序列号来避免使用过时路由信 息而产生无效路由，通过对路由编号等措施来避免路由环路的产生。在协议的实 现过程中，节点周期性地向邻居广播一个路由分组，分组内容为节点路由表或表 中发生改变的表项，相关节点根据收到的路由分组更新路由表。d s d v 的主要优 点是消除了路由环路，加快了收敛速度， 在于周期性的广播分组增大了网络开销， o l s r 同时减少了控制信息的开销。它的不足 难以适应拓扑变化快的移动自组网。 o l s r 【，j ( o p t i m i z e dl i n ks t a t er o u t i n g ) 协议采用和d s d v 类似的逐跳路由， 数据包不指明完整的路径，由各中间节点根据自己的路由表选择路径，各节点需 要有规律的交换网络拓扑信息。被邻节点选为多点中继站( m p r ) 的节点需要周 期性地向网络广播拓扑控制信息t c ( t o p o l o g yc o n t r 0 1 ) ，控制信息中包含了将其 选为m p r 的那些节点的信息，以通知网络中其他节点它与哪些节点直接相连。只 有m p r 节点被用作路由节点并广播控制信息，非m p r 节点不参与路由计算也不 需要转发控制信息，但可以接受t c 信息，并用来建立自己的链路状态库。该协议 的优点在于：它只广播部分链路状态信息，且只在选出的部分节点中广播；除了 周期性的发送控制信息，o l s r 不需对链路失效和其他情况触发更新信息；周期性 的控制信息也不需可靠传输，因此大大减少了控制信息广播的开销，节约了移动 自组网有限的网络资源。 w r p w r p 8 j ( w i r e l e s sr o u t i n gp r o t o c 0 1 ) 协议中，每个节点需要维护距离表、路由 表、链路费用表和消息重传列表m r l ( m e s s a g er e t r a n s m i s s i o nl i s t ) 。该协议利用 去往目的节点的路径长度和相应路径的倒数第二跳节点信息加速路由协议收敛速 度。各节点通过其邻节点的最短路径生成树s s t ( s h o r t e s tp a t hs p a n n i n gt r e e ) 生 成自己的s s t ，然后再向邻节点传递更新信息。w r p 算法的独特之处在于：当它 每次检测到任一邻居节点的链路发生改变时，会检查所有邻居节点的一致性。以 这种方式进行的一致性检查有助于以一种更好的方式消除环路状况，且具有快速 收敛性，减少了无穷计算问题的发生。该协议的缺点是需要更新的信息较多，占 用了较多资源。 7 电子科技大学硕士学位论文 2 3 2 按需驱动路由协议 源节点初始化按需驱动类路由协议又称作反应式路由协议，或者简称为按需 路由协议。按需路由协议只有在源节点需要的时候，才创建路由，这也正是“按 需”的含义所在。当网络中的一个节点需要一条路由到达某个目的节点的时候， 源节点就初始化网络内的路由寻找进程，一旦找到一条路由或者所有可能的路由 重新排列都已检测完毕，则结束网络内路由寻找进程。一旦创建了一条路由，那 么就立即按照某种路由维护机制维护该条路由，直至出现下列情况之一时方才停 止该路由的维护： 沿着从源节点至目的节点的路径已无法再访问到目的节点( 路由异 常中断) ： 已不再需要该路由。 归入按需路由协议类的有a o d v 、d s r 、a b r 等。 a o d v a o d v 9 】( o n d e m a n dd i s t a n c ev e c t o rr o u t i n g ) 协议使用基于目的节点的路由 发现机制。源节点广播路由请求分组，收到路由请求分组的节点创建到达源节点 的反向路由。目的节点收到路由请求后响应路由回复分组，回复分组以单播方式 向源节点传播，沿途建立到目的节点的正向路由。有关该协议的机制和优缺点， 后文将有详细介绍。 d s r d s r 1 0 】( d y n a m i cs o u r c er o u t i n g ) 协议使用源路由算法，网络中每个节点需 要维护一已知路由表，当发现新的路由时则更新该表。每个路由分组的分组头都 包含该分组从源节点到目的节点途中所经过的中间节点信息，各节点缓存路由分 组头中携带的路径信息。d s r 的主要优点在于：使用缓存技术减少了路由发现的 开销；一次路由发现过程可以产生多条到达目的节点的路由，有助于路由选择。 d s r 的缺点在于：每个分组的头部都需要携带完整的路由信息，数据包的额外开 销较大；由于路由被缓存，过期路由会影响路由选择的准确性。 a b r a b r t l l 】( a s s o c i a t i v i t y b a s e dr o u t i n g ) 协议定义了一个新的路由选择度量：联 合稳定度，即节点及其链路在时间和空间上的稳定程度。每个节点周期性地广播 一标志表明其存在，邻节点收到标志后将路由稳定时间和路由信号强度作为路由 选择的标准，每收到一次，相应节点的稳定度就增加一点。稳定度值越高表示该 8 第二章移动a dh o c 网络的相关研究 节点移动越少，稳定度越低表示该节点移动性越大。当节点移动引起链路中断时， 联合稳定度将被重置。a b r 协议主要由三部分组成：路由发现、路由重构和路由 删除。a b r 协议通过节点间定期发送信标( b e a c o n ) 来标识节点的存在，寻找移 动自组网中生存期最长的路由是该算法最基本的设计目标。 9 电子科技大学硕士学位论文 第三章a o d v 的相关研究 3 1 移动a dh o c 网络路由协议面临的问题和要求 3 1 1 移动a dh o c 网络协议面临的问题 路由协议是自组网体系结构中不可或缺的重要组成部分，其主要作用是发现 和维护路由。具体的说主要有以下几个方面：监控网络拓扑结构的变化；交换路 由信息；确定目的节点的位置；产生、维护以及取消路由；选择路由并转发数据。 常规的路由协议主要有两种：一种是基于距离矢量的路由协议，如r i p 。一种 是基于链路状态的路由协议，如o s p f 。这两类协议都是针对有线固定网络而设计 的，它们的拓扑结构是固定的，不会出现大的网络结构变化。a dh o e 网络中由于 节点的任意移动性导致拓扑结构动态、随机且快速地变化，这样常规路由在拓扑 结构变化时，就会花很大的代价重新路由，而且协议状态将始终处于不收敛状态， 占用大量的网络资源，致使信息的传输无法实现。 另外，a dh o c 网络不能采用常规路由协议主要由于以下因素： a dh o c 网络中无线传输设备功率的差异以及无线信道中的大量干扰导致 单向信道的存在。 无线信道的广播特性使得常规路由的网络选路过程产生许多冗余链路。 常规路由的周期性广播路由更新分组会消耗大量的网络带宽。 常规路由协议周期性的路由更新分组会消耗大量的节点能源。 此外，某些常规路由协议需要的复杂计算使得c p u 始终处于很高的负载之下， 这也同样消耗了大量的能源，并将对有限的节点能源带来更多的压力。因此需要 适用于a d h o c 网络自身的路由协议。 3 1 2 移动a dh o c 网络对路由协议的要求 自组网路由协议的任务是实现路由，但由于自组网具有动态拓扑、有限带宽、 终端受限、存在单向信道等特点，对在其上运行的路由协议便提出了许多具体而 严格的要求。相对于有线网络，有些要求是自组网特有的，这些要求主要有【12 】： 收敛迅速：自组网的拓扑结构是动态的，随时处于变化之中，这就要求路 第三章a o d v 的相关研究 由协议必须对拓扑的变化具有快速反应能力，在计算路由时能够迅速收 敛，及时获得有效的路由，避免出现目的节点不可达的情况。 提供无环路由：无论在有线网络还是无线网络，提供无环路由都是对路由 协议的一项基本要求。但在自组网中，由于拓扑结构动态变化会导致大量 已有路由信息在短时间内作废，从而更容易产生路由环路。在自组网中提 供无环路由就显得尤为重要而且更难做到。 避免计数到无穷：经典的距离矢量算法在某条链路失效时，有可能出现计 数到无穷的情况。在自组网中，链路失效是经常发生的，这就要求在自组 网中运行的路由协议必须能够避免计数到无穷，不采用或者改进会出现计 数到无穷的算法。 控制管理开销小：自组网中无线传输带宽有限，传送控制管理分组不可避 免地会消耗掉一部分带宽资源。为了更有效地利用宝贵的带宽资源，需要 尽可能地减小控制管理的开销。 对终端性能无过高要求：无线移动终端使用可耗尽能源、c p u 性能、内 存大小、外部存储容量等都低于固定的有线终端，因此在自组网中不能对 端性能要求过高。有线网络中用计算的复杂度来换取路由协议性能的做 法，在自组网中不再适用。 支持单向信道：在自组网中，有可能出现单向信道。支持单向信道，也是 对路由协议的要求之一。 尽量简单实用：简单有助于提高可靠性，有助于减少各种开销。在实现路 由功能的前提下，力求简单，应是设计自组网路由协议的原则之一。 但目前提出的路由协议都未达到以上所有要求，提出一种适应性强的路由协 议是a dh o c 网络未来研究的一个具有挑战性的课题。 3 2a o d v 协议机制 3 2 1a o d v 概述 a o d v ( a dh o eo n d e m a n dd i s t a n c ev e c t o rr o u t i n g ) 是d s r 与d s d v 的结合。 它借用了d s r 中按需进行路由发现和路由维护机制，以及d s d v 中的逐跳路由、 序列号、定期广播。 a o d v 路由协议计算网络组成移动节点之间的动态、自启动、多跳路由，以 电子科技大学硕士学位论文 便用这些移动节点建立和维护一个a dh o e 网络。a o d v 路由协议给移动节点提供 快速获取到达新目的节点的路由能力，不要求节点维护到达那些没有处在通信状 态中的目的节点的路由。a o d v 路由协议给移动节点提供及时响应网络拓扑中的 链路变化和链路中断的能力。a o d v 路由协议的操作是开环的，在a dh o c 网络拓 扑变化之时，( 通常情况下，就是节点在网络内移动) ，通过避免b e l l m a n f o r d “无 穷计算”问题来提供快速收敛。当链路中断的时候，a o d v 路由协议使受到影响 的那些节点能够得到有关链路中断信息通知，这样，这些受影响的节点就能够将 使用该中断链的路由变成无效。 a o d v 路由协议的一个明显特征是每个路由条目均使用一个目的节点序列 号。目的节点序列号由目的节点产生，与目的节点发送给路由请求节点的任何路 由信息组合在一起。使用目的节点序列好能够确保路由是开环的。如果在到达同 一个目的节点的两条路由中选择一条，那么要求路由请求节点选择序列号较大的 那条路由。 a o d v 有3 种主要的控制报文：褂p , z q ( r o u t er e q u e s t ) 、r r e p ( r o u t er e l y ) 、 r e r r ( r o u t ee r r o r ) ，其信息都放在u d p 的上层使用端口6 5 4 来传送，r r e q 主 要信息有d s ti p 即目的地址i p 、o r gi p 即发出砒汪q 的源地址i p ；r r e p 主要信息 有d s ti p 即处理哪个d e s t i n a t i o n 的路由表项、o r gi p 即这个路由表项的下一跳；r e r r 主要信息有u n r e a c h a b l ed e s t i n a t i o ni p 即往哪一个目的地址的路径己无法到达。 3 2 - 2 路由发现 产生路由请求 当源节点需要与某目的节点进行通信时，它首先在本节点维护的路由表中查 找是否有到达该目的节点的路由。若路由表中已经包含了到达该目的节点的有效 路由，则立即使用此路由发送数据分组，否则它将向所有邻居广播r r e q 分组， 以启动一个路由发现过程来找到一条到达该目的节点的可用路由。 r r e q 分组主要由以下一些字段组成 。其中“分组i d ”与“路由请求r r e q 源节点i p 地址”用于唯一标示一 个路由请求，i d 字段的值要在源节点维护的最新i d 值基础上加一；“路由请求 第三章a o d v 的相关研究 r r e q 源节点序列号是正在使用的一个路由条目中的当前序列号，该条目是指向 本条路由请求r r e q 消息的源节点的，该字段值为源节点维护的当前序列号值加 一：“目的节点序列号”用来维护正向路由的有效性，若该路由发现是由于路由失 效引起的，则将源节点路由表项中原有的“目的节点序列号 加入r r e q ，否则将 “u n k n o w ns e q u e n c en u m b e rf l a g 标记置位；“跳数 用于计算r r e q 经过的节点 数，初始化为零。 处理和转发路由请求消息 一个节点接收到一个r r e q 分组后，首先建立或者更新到达前一跳的路由， 然后确定自己至少在最近的r a t hd i s c o b e r yt i m e 时间内是否已经收到具有 相同源节点i p 地址和相同路由请求识别码i d 的r r e q 分组。如果确定之前已经 接收过这样的r r e q 分组，那么该节点就将刚刚接收到的那个r r e q 分组丢掉。 否则，该节点先将其刚刚接收到的r r e q 分组中的跳数加一。然后该节点使用最 长前缀匹配来搜索一条到达该r r e q 分组源节点i p 地址的反向路由。假如需要的 话，该节点使用其路由表中来自该r r e q 分组的源节点序列号建立或者更新这条 反向路由。如果该节点接收到一个需要自己转发给该r r e q 分组源节点的r r e p 分组( 通过源节点i p 地址来识别) ，那么就需要这条反向路由来传输该r r e p 分组。 可以说，a o d v 中反向路由是在源节点广播r r e q 分组过程中建立起来的。 图3 1a o d v 路由请求过程 当前节点可以使用这条反向路由来转发数据分组，就如同路由表中任何其他 路由被用来转发数据分组一样。 路由应答消息的产生 电子科技大学硕士学位论文 一个节点满足以下条件之一就产生一个r r e p 分组： 该节点本身就是所需的目的节点； 该节点有一条到达所需目的节点的活动路由，并且该节点路由表中 当前存在该目的节点路由表条目，该条目中所记录的该目的节点序 列号有效，并且大于或者等于所接收到的该r r e q 分组中的目的节 点序列号，此外要求该r r e q 分组中的“d 标志为0 。 节点一旦产生了一个r r e p 分组，就按照源节点路由表条目指定的路由，按 照单目标方式将该r r e p 分组发送到通往该r r e q 分组源节点的路由的下一跳节 点。每当该r r e p 分组朝着源节点往回转发一跳的时候，其跳数域就被加一。因 此当该r r e p 分组到达源节点的时候，其跳数就表示从源节点到达目的节点的距 离。 目的节点产生的路由应答 如果产生r r e p 的分组就是目的节点本身，那么如果r r e q 分组中的目的节 点序列号正好等于目的节点当前自己的序列号加一的话，就必须将目的节点当前 自己的序列号加一。否则的话，目的节点在产生该r r e p 分组之前就不会改变其 序列号。 中间节点产生的路由应答 如果产生的r r e p 分组的节点不是目的节点，而是从源节点到达目的节点的 路径上的一个中间节点，那么该中间节点将其所知道的该目的节点序列号拷贝到 该r r e p 消息中的目的节点序列号域。 该中间节点更新转发路由条目，将最后一跳节点( 从其接收到该r r e q 分组， 由i p 头中的源节点i p 地址指定) 拷贝到该转发路由条目的预发送节点列表中。该 中间节点还要更新其路由表中该r r e q 分组源节点的路由表条目，将到达目的节 点的下一跳节点拷贝到反向路由条目的预发送节点列表中。 无请求路由应答r r e p 消息的产生 一个节点接收到一条r r e q 消息并对其用一条r r e p 消息做出应答响应之后， 丢掉该r r e q 消息。如果该r r e q 消息的“g 标志被置“1 ”，并且是一个中间 节点给源节点回送一条r r e p 消息，那么该中间节点必须按照单目标方式给该目 的节点发送一条无请求r r e p 消息。然后将该无请求r r e p 消息发送到通往其目 的节点的路由的下一跳节点，就好象该目的节点已经发送了一条r r e q 消息来寻 找该无请求的r r e p 消息源节点一样，这条无请求r r e p 消息是为了响应这条假 想的r r e q 消息而产生的。发送给该r r e q 源节点r r e p 消息也是相同的，而与 1 4 第三章a o d v 的相关研究 r r e q 消息的“g ”标准是否被置“1 ”无关。 路由应答消息的接收和转发 一个节点接收到一条r r e p 消息后，使用最长前缀匹配搜索到达前一跳的路 由。如果需要的话，则建立一条到达前一跳的路由，但是没有有效的序列号。然 后，该节点接着将该r r e p 消息中的跳数加一。假如已经不存在到达这个目的节 点的转发路由，则重新建立。否则的话，该节点对该r r e p 消息中的目的节点序 列号与自己所存储的该目的节点序列号进行比较，更新该到达该目的节点的路由 条目。随后，当前节点可以使用这条路由来将数据分组转发到该目的节点。前向 路由是在节点回送路由响应报文过程中建立起来的。 3 2 3 路由的维持 图3 2a o d v 路由应答过程 由于移动自组网具有动态拓扑的特点，网中任何节点的关闭或移动都会导致 部分现有链路的断裂和新链路的产生，对现有路由造成一定影响。因此移动自组 网的路由协议必须有维持路由、修复破损路由、拆除无效路由等机制。 a o d v 协议中，活动路由上的节点通过定期广播h e l l o 分组来检查该路由上 各段链路的连接情况，非活动路由上的节点则不需定期做这个工作。h e l l o 分组 其实就是一个t t l 值为1 的特殊r r e p 分组。由于t t l 值为1 ，因此该r r e p 分 组只能传播