（计算机应用技术专业论文）无线自组织网络中容错动态源路由协议研究.pdf

硕上学位论文 摘要 无线自组织网络( a dh o e ) 是一种由移动终端组成的无线无固定设备的分布 式网络。此网络的路由技术是保证无线网络质量的关键技术之一，但是由于其网 络中节点位置不固定以及节点移动速度、方向不可预测的特点，导致路由失效的 问题频繁产生。而路由失效的问题会使得无线网络显示出比较差的性能，因此如 何设计一种针对当前动态变化的网络情况能及时做出调整与适应的容错路由协议 将是这个方面的研究热点之一。 动态源路由( d s r ) 协议是一种非常流行的无线自组织网络路由协议，由于 它属于一种反应式路由协议，没有固定周期的更新网络拓扑情况，所以它在路由 失效而导致网络出错的处理上还存在着一些问题。因此，如何解决动态源路路由 协议容忍路由失效错误，保证在网络拓扑结构变化频繁的条件下，无线网络拥有 较高的性能将是本文研究的重点。 本文首先详细介绍了动态源路由协议的原理，包括路由发现、路由维护和协 议包头内容部分。然后通过分析无线自组织网络在节点移动条件下，其网络性能 变化的情况，来发现节点移动对路由失效问题所产生的影响。接着针对动态源路 由协议存在的一些问题提出了两种优化策略，即信息反馈策略和路由预测策略。 信息反馈策略是利用无线网络中数据包捎带的原理来提高节点掌握网络拓扑情况 的能力，提高路由发现的能力。路由预测策略是一种主动的路由维护机制，它通 过相邻节点的位置信息、移动信息来估计链路存活的时间，提前来通知源节点主 动进行路由替换而减少路由维护的时间，最终使动态源路由协议对因为节点移动 而导致的路由失效问题产生较大的错误容忍，保证无线网络在拓扑变化频繁条件 下的性能。 本文应用网络仿真软件n s 2 对这两种策略进行了实现和性能分析。通过实 验结果表明经过优化的动态源路由协议在节点的移动条件下，其吞吐量、平均端 到端时延以及丢包率的性能上都有显著的改善，利用及时的路由替换方法能够对 无线网络中路由失效问题产生较高的容忍。 关键词：无线自组织网络：移动性；动态源路由协议；容错 无线自组织网络中容错动态源路由协议研究 a b s t r a c t am o b i l ea dh o cn e t w o r ki sac o l l e c t i o no fw i r e l e s sm o b i l en o d e sf o r m i n ga t e m p o r a r yn e t w o r kw i t h o u tt h eu s eo fa n ye x i s t i n gn e t w o r ki n f r a s t r u c t u r eo r c e n t r a l i z e da d m i n i s t r a t i o n t h i sn e t w o r k r o u t i n gt e c h n o l o g yi s o n eo ft h ek e y t e c h n o l o g i e st oe n s u r et h eq u a l i t yo ft h ew i r e l e s sn e t w o r k h o w e v e rf o rt h er e a s o n t h a ti t sn e t w o r kn o d ep o s i t i o n sa r en o tf i x e d ，a n dm o b i l en o d e ss p e e da n dd i r e c t i o na r e u n p r e d i c t a b l e ，t h er o u t i n gh a v ef r e q u e n t l yl e dt ot h ef a i l u r e t h ef a i l u r eo fr o u t i n g w i l ls h o wp o o rp e r f o r m a n c ei nw i r e l e s sn e t w o r k s oh o wt od e s i g naf a u l t t o l e r a n t r o u t i n gp r o t o c o lt of i tt h ec u r r e n ts i t u a t i o nc h a n g e sa n da d j u s t m e n t sw i l lb eo n eo ft h e h o ts p o t s d y n a m i cs o u r c er o u t i n g ( ds r ) p r o t o c o li s av e r y p o p u l a rs e l f - o r g a n i z i n g w i r e l e s sn e t w o r kr o u t i n gp r o t o c 0 1 a si ti sar e a c t i o nr o u t i n gp r o t o c o l sa n dn e t w o r k t o p o l o g yi sn o tu p d a t ei np e r i o dt i m e ，d s rh a v es o m ep r o b l e mi nd e a l i n gw i t ht h e n e t w o r kw r o n gt h a td u et or o u t i n gf a i l u r e t h e r e f o r e ，h o wt ot o l e r a t et h ef a u l to ft h e d s r p r o t o c o lp a t hr o u t i n gf a i l u r e ，a n de n s u r eh i g h e rp e r f o r m a n c eo fw i r e l e s sn e t w o r k i nf r e q u e n tc h a n g e si nn e t w o r kt o p o l o g yw i l lb et h ef o c u so ft h i sp a p e r t h i sp a p e ri n t r o d u c e dt h ep r i n c i p l eo fd s r p r o t o c o l ，i n c l u d i n gr o u t i n gf o u n d ， r o u t i n g m a i n t a i na n dt h ec o n t e n to fp a c k e t h e a d e r t h r o u g ha n a l y z i n g t h e p e r f o r m a n c ec h a n g e so fw i r e l e s sn e t w o r k si nt h ec o n d i t i o n so fm o b i l en o d e s ，w e d i s c o v e r e dt h ei m p l i c a t i o n sa r i s i n gf r o mt h ef a i l u r eo ft h er o u t i n g w ep r e s e n tt w o o p t i m i z i n gs t r a t e g yi n c l u d i n gi n f o r m a t i o nf e e d b a c ks t r a t e g ya n dr o u t i n gp r e d i c t i o n s t r a t e g yi nd s rp r o t o c 0 1 i n f o r m a t i o nf e e d b a c ks t r a t e g yc a ni m p r o v et h ea b i l i t yo f r o u t i n gf o u n db yu s i n gt h ep r i n c i p l eo fd a t ap a c k e t s p a s s i n gt h er e d u n d a n ti n f o r m a t i o n r o u t i n gp r e d i c t i o ns t r a t e g y i sap r o a c t i v em e c h a n i s mo fr o u t i n gm a i n t e n a n c e t h r o u g he s t i m a t i n gt h es u r v i v a lt i m eb yl o c a t i o n b a s e di n f o r m a t i o no ft h ea a ja c e n t n o d e sa n dm o b i l i t yi n f o r m a t i o n ，i tc a nr e d u c et h er o u t i n gm a i n t e n a n c et i m eb y n o t i c i n ga d v a n c en o d et oi n i t i a t et h er o u t i n gr e p l a c e m e n t b e c a u s eo ft h et o l e r a n c eo f r o u t i n gf a i l u r e ，i tg u a r a n t e e sw i r e l e s sn e t w o r kp e r f o r m a n c eu n d e rt h ec o n d i t i o n so f f r e q u e n tc h a n g e si nt o p o l o g y i nt h i s p a p e r ，n s - 2n e t w o r ks i m u l a t i o ns o f t w a r ew a su s e dt or e a l i z et w o s t r a t e g i e sa n dt om a k ep e r f o r m a n c ea n a l y s i s t h ee x p e r i m e n tr e s u l t si n d i c a t e dt h a tt h e p e r f o r m a n c eo fo p t i m i z e dd s rp r o t o c o lh a db e e ni m p r o v e d s i g n i f i c a n t l y i n i i 硕上学位论文 t h r o u g h p u t ，t h ea v e r a g ee n d - t o e n dd e l a ya n dp a c k e tl o s sr a t e ，a n di nt h em o b i l en o d e c o n d i t i o n s ，t h ew i r e l e s sn e t w o r kw o u l dt o l e r a n tt h ef a u l to fi n v a l i dr o u t i n gb yu s i n g t i m e l yr o u t i n gr e p l a c e m e n t k e yw o r d s ：w i r e l e s sa dh o en e t w o r k ；m o b i l i t y ；d s r ；f a u l tt o l e r a n c e i i i 无线自组织网络中容错动态源路由协议研究 插图索引 1 1 典型的a dh o c 网络2 2 1d s r 协议路由发现过程8 2 2 简单的a dh o c 分组转发示意图一9 2 3d s r 分组结构1 0 2 4d s r 头部结构1 0 2 5 路由请求选项结构一1 1 2 6 路由应答选项结构一1 1 2 7 路由错误选项结构一1 1 2 8 确认请求选项结构1 2 2 9 确认选项结构一1 2 2 1 0 源路由选项结构1 3 3 1n s - 2 网络模拟的过程1 9 3 2 吞吐量比率的变化2 2 3 3 转发包数量变化2 3 3 4 丢包数量变化2 3 3 5 平均端到端时延变化一2 4 4 1 路由缓存处理流程一2 8 4 2 反馈信息接收处理流程2 9 4 3t r a c e 文件部分状态参数3 0 4 4 平均端到端时延比较结果3 1 4 5 丢包率比较结果3 2 4 6 吞吐量比较结果3 2 5 1 预测策略在路由发现中的流程3 5 5 2 预测策略在路由维护中的流程一3 6 5 3 预测策略的吞吐量比较一3 7 5 4 预测策略的丢包率比较3 7 5 5 预测策略的平均端到端时延比较：一3 8 i v 图图图图图图图图图图图图图图图图图图图图图图图图图图图 硕上学位论文 附表索引 表3 1 节点移动的参数2 l 表3 2 传输模式参数2 l 表4 一d s r f t 实现文件3 0 v 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体己经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名： 叶弛 日期：2 。 年r 月彩日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ”) 作者签名： 导师签名： 砷盼 硕士学位论文 第1 章绪论 1 1 无线自组织网络概述 随着计算机网络的广泛使用，人们可以通过i n t e r n e t 网络相互交流和共享 信息，人们的生活和思维方式也随之产生了变化，并且这种改变还会随着 i n t e r n e t 的发展而更加深远。而无线自组织网络就是其中具有代表性的产物。 1 1 1 无线自组织网络的产生和发展 最初i n t e r n e t 上的主机和路由器都是不能移动的，但由于便携式电脑的广 泛使用，以及无线通讯的迅速发展产生了通过便携式电脑随时随地上网的需要， 无线网络便应运而生。最开始的无线网络中主机可以移动，但是网络中的互连需 要基站，所以只能在提供无线移动服务的地区才能进行通信。在这样的网络里移 动节点相当于移动终端，它不具备路由功能而只有通过基站才能完成路由交换功 能。这种类型网络的典型例子有蜂窝无线系统，办公室无线局域网等。由于其不 适合那些没有基础设施或者架设基础设施的费用太昂贵的地方以及在某些情况下 通信只是暂时的场所。所以，后来便产生了无线自组织网络。 无线自组织网络概念的提出最早可以追述到1 9 6 8 年，当时在美国本土和夏威 夷建立了a l o h a 网，a l o h a 网络协议是一种单跳网络协议。1 9 7 3 年出现了p r 网 ( p a c k e tr a d i o ) ，这是一种多跳网络( m u l t i - h o p ) 。p r 网中的结点能够帮助其 它结点传递数据包这种方式突破了网络节点之间的距离瓶颈。在开发i e e e 8 0 2 1 l 标准时，电子工程协会i e e e 提出将p r 网络改名为无线自组织网络。随着人们对无 线自组织网络的热情越来越高和笔记本电脑性能的提高，为此i n t e r n e t e n g i n e e r i n gt a s kf o r c e ( i e t f ) 专门成立了一个移动无线自组织网络( m a n e t ) 工作组用来制定这方面的协议规范，这个工作组主要任务就是解决路由问题【l 】。在 i e t f 中m a n e t 是这么定义的，一个移动无线自组织网络( m a n e t ) 就是一个由移动 路由器通过无线链路组成的自治系统，路由器可以任意移动形成任意的拓扑结构， 并且这个拓扑结构可以迅速但不可预测的动态变化，这个网络可以作为一个独立 的网络存在或者和i n t e r n e t 互联。因为无线自组织网络巨大的潜在应用价值和市 场前景，m a n e t 工作组负责其网络路由协议标准的研究、讨论和制定。目前已经提 出了d s r 、a o d v 、t o r a 和z r p 等多种路由协议草案，但由于m a n e t 本身的复杂性至今 仍未确定一个正式的路由协议。 无线白组织网络中容错动态源路由协议研究 1 1 2 无线自组织网络的特点和应用 无线自组织网络相对常规通信网络而言，最大的区别就是可以在任何时刻任 何地点不需要现有基础网络设施的建立或者拆除，同时它也不必同i n t e r n e t 相连。 在无线自组织网络中每个用户终端兼备路由器和主机两种功能，而在常规网络中 路由器和主机通常是由两个独立的设备完成的。一方面作为主机用户终端需要运 行面向用户的应用程序比如编辑器、浏览器等，另一方面作为路由器用户终端需 要运行相应的路由协议，根据路由策略和路由表进行数据分组转发工作和路由维 护。下图1 1 为一个典型的无线自组织网络，图中终端s ，d 之间无法直接通信，但 是可以借助其他中间结点对于数据包的转发在路径s - e - f - j - d 或者s c g k - d 上进 行通信。 s 逻辑网络结构 图1 1 典型的 dh o c 网络 如上图中，工作中的无线自组织网络具有以下特点： 1 ) 网络的白组织性。无线自组织网络可以在任何时刻任何地方构建而不需 要现有的网络信息基础设施的支持就可以形成一个自由移动的通信网络。 2 ) 动态变化的拓扑结构。网络的拓扑结构是指从网络层角度来看物理网络 的逻辑视图。在无线自组织网络中移动用户可以以任意的速度和任意方式在网中 移动，加上无线发送装置发送功率的变化、无线信道间的相互干扰因素、地形因 素等的影响，节点间通过无线信道形成的网络拓扑结构随时都会发生变化。 3 ) 有限的无线传输带宽。无线信道本身的物理特性使无线自组织网络的网 络带宽相对有线方式要低的多。另外还要考虑无线信道竞争时所产生的信号衰落 碰撞阻塞噪声干扰等因素，这使得实际带宽要小得多。 4 ) 移动终端的有限性。无线自组织网络中的移动用户终端通常以p d a 掌上型 电脑或手提式电脑等为主要形式。这些移动终端往往内存小，c p u 处理能力低，所 带电源有限使得无线自组织网络的协议和应用程序设计更加困难。 5 ) 安全性差。无线自组织网络是一种无线方式的分布式结构，所以更加容 易受到窃听入侵、剥夺“睡眠 或者拒绝服务等网络攻击。 6 ) 网络的可扩展性不强。由于采用t c p i p 协议中的子网技术使得i n t e r n e t 2 硕上学位论文 具有网络的可扩展性，而无线自组织网络动态变化的拓扑结构使得子网技术所带 来的网络可扩展性不能得到应用。 7 ) 单向无线信道的存在。无线自组织网络采用无线信道通信由于地形环境 或发射功率等因素影响可能产生单向无线信道，例如如图1 1 中，由于笔记本电脑 a 的发功率一般笔记本电脑b 大，所以有可能b 可以接收到来自a 的信号，而a 无法接 收到来自b 的信号，即存在一条从a 至i j b 的单向信道。 8 ) 生存时间短。无线自组织网络通常是由于某个特定原因而临时创建的， 使用结束后网络环境将会自动消失。 1 2 无线自组织网络路由协议设计面临的问题 传统网络中存在的安全威胁在无线自组织网络中同样存在，而且由于自身的 特点，移动无线自组织网络又面临着许多新的威胁2 】【3 儿4 儿5 儿6 】【7 】。移动无线自组织 网络里没有事先设置好的固定基站，所有节点分布运行，并且要兼职充当路由器 功能，所有的网络服务都是动态产生，因此快速变化的网络连接是移动无线自组 织网络内在的弱点，与有线网络和蜂窝无线网络相比，移动无线自组织网络的拓 扑结构更容易改变，网络连接快速恢复的问题更为突出。虽然在无线自组织网络 中存在主动和被动的威胁，但是无线自组织路由协议设计的目标与传统网络中的 目标哺j 基本上是一致的，但是两者却有着不同的内涵。下面就分别描述其面临的 威胁以及路由协议设计时需要注意的问题。 1 2 1 无线自组织网络路由面临的威胁 对无线自组织网络的威胁可分为两类：被动干扰和主动攻击。 1 ) 被动干扰。在被动干扰下，正常的网络行为可能没有被刻意干扰，而仅 仅是由于正常的网络现象而受到影响。由于无线自组织网络使用的是无线信道， 所以这种影响比较隐蔽，一般无法检测到。比如，如果去往某个特定节点的路由 请求比到其它节点的路由请求要频繁，那么该特定节点比较重要，该节点的移动、 能量耗尽等行为就会威胁整个网络的性能。另外整个网络拓扑信息也会随着变化， 当频繁改变时，整体网络的性能就会随之被影响。 2 ) 主动攻击。主动攻击就是网络攻击者通过一定方式干扰网络的正常行为 达到攻击的目的。比如攻击者向网络广播一些特定的消息，使得别的节点以为经 过该节点的路由最短或代价最小，这样受到攻击的节点都会将数据包发送给该节 点，从而形成一个吸收数据的“黑洞，攻击者也可以通过不停地发送虚假路由 信息使得被攻击节点的路由表溢出，从而使得正常的路由信息无法及时更新：攻 击者还可以发送错误的路由信息和重复发旧的路由信息，使网络出现分割和拥塞。 在被动干扰和主动攻击中，被动干扰往往是影响路由协议性能的关键问题， 3 无线自组织网络中容错动态源路由协议研究 而主动攻击却是影响路由协议安全的因素。 1 2 2 无线自组织网络路由协议设计的目标 其目标主要包括以下几点： 1 ) 稳定性。稳定性是指既使受到攻击，节点仍然能够在必要的时候提供有 效的服务。稳定性是与网络安全相关的一个关键特性。稳定性保证网络服务操作 正常并能容忍故障。在网络层，路由信息很可能被破坏而使网络无法互连。对于 移动终端，稳定性还涉及电源问题。一旦没有能源，节点将完全陷于瘫痪。为了 节省能源，通常会考虑让主机在空闲时处于睡眠状态，而在必要时将其唤醒。但 是，攻击者可以设法通过某种合法方式与节点交互，使其始终处于通信状态，目 的是消耗节点的有限能源，这种攻击被称为“剥夺睡眠攻击”。与其他攻击相比， 这种攻击可能更为致命。因此需要通过强认证机制来确保通信终端的合法性，并 应考虑在资源有限的情况下首先满足优先级较高的任务，从而保证网络的稳定。 2 ) 完整性：完整性保证信息在发送过程中不会被中断，并且保证节点接收 的信息应与发送的信息完全一样。如果没有完整性保护，网络中的恶意攻击或无 线信道干扰都可能使信息遭受破坏，从而变得无效。此外，还需要特别考虑存储 在用户设备中的数据的完整性，防止数据被篡改。 3 ) 安全性：每个节点需要能够确认与其通信的节点身份，同时要能够在没 有全局认证机构的情况下实施对用户的鉴别。如果没有认证，攻击者很容易冒充 某一节点，从而得以获取重要的资源和信息，并干扰其他节点的通信。只采用认 证通常是不够的，认证只负责证明某人的身份，因此还需要通过授权来决定某种 身份是否被允许做某些事情。由于无线自组织网络没有固定的管理域，所以难以 实施防火墙技术。 4 ) 确定性：确定性用来确保一个节点不能否认它已经发出的信息。它对检 查和孤立那些被占领节点具有特别重要的意义，当节点a 接收到来自被占领节点 b 的错误信息时，确定性保证节点a 能够利用该信息告知其他节点b 己被占领。 1 2 3 容错路由需要解决的问题 路由协议是移动节点互相通信的基础，因此容错路由成为当前无线自组织网 络研究的热点。目前提出的多种路由协议各有所长，但没有一种适用于所有的环 境。一个理想的无线白组织网络容错路由协议应当满足能在网络路由失效时，快 速发现问题并且能及时地进行恢复，来保证数据传输的连贯性。 但是，在容错路由协议的设计上面临一些难点： 1 ) 路由信息的收集。在动态变化的网络拓扑结构中，如何相互通信来收集 反映网络情况的路由信息。 2 ) 信息的反馈。在出现路由问题时，需要通知哪些必要的节点来及时更新 4 硕上学位论文 网络的拓扑情况。 3 ) 失效路由的提前预测。如何预测哪条路有即将失效，将是保证快速恢复 的关键。 4 ) 失效路由的替换。当发现失效路由采用何种替换方法进行快速的替换。 在设计与改进路由算法时，这都是本文需要面对与解决的。 1 3 本文所做的主要工作 无线自组织网络协议的设计目标是正确，高效的建立路径连接，及时的传递 数据，并且能够尽量的减小协议在带宽上的开销。在诸多的无线自组织路由协议 中，动态源路由协议在带宽上的开销最小，顺应了无线自组织网络对于带宽方面 的要求。本文所做的主要工作包括以下几点： 1 ) 首先，对动态源路由协议设计和实现方法做出了分析，并且对n s - 2 中实 现动态源路由协议所使用的数据结构、实现方法做出了解释，再对近几年来无线 自组织路由协议的安全容错相关研究进行的分析比较，提出对d s r 协议进行改进 的想法和出发点。 2 ) 然后，需要分析节点在移动条件下对无线网络产生的影响。通过介绍仿 真软件n s 一2 的基本体系结构和功能，利用n s 一2 模拟实验验证了在随机环境下， 节点移动速度递增对动态源路由协议性能参数指标的影响。本文主要分析了平均 端到端时延( d e l a y ) 、端到端吞吐量( t h r o u g h o u t ) 、以及丢包率的实验数据， 并以此为基础做出了在这种变化条件下的分析结果。通过n s - 2 模拟实验表明，以 上3 个参数能正确反应节点移动在动态源路由协议下对无线网络的影响。 3 ) 最后，针对节点移动性对无线网络的影响，提出了优化动态源路由协议 的方案：信息反馈策略与路由预测策略。对动态源路由协议的优化算法是在n s - 2 的实验环境下进行了仿真。证明了改进后的动态源路由协议比原协议不仅能保证 移动条件下数据的基本传输，而且对大部分路由失效问题能及时发现并解决。 1 4 论文组织结构 本文共分五章。第一章是绪论，概述了无线自组织网络、路由协议设计的相 关问题，以及本文所做的主要工作。第二章详细分析了动态源路由协议的实现方 法和数据结构，并介绍了近几年来无线自组织路由协议的安全容错相关研究。第 三章介绍了网络模拟工具n s 一2 ，并且在n s 一2 网络模拟工具中，讨论结点移动对无 线网络动态源路由协议中的平均端到端时延( d e l a y ) 、端到端吞吐量 ( t h r o u g h o u t ) 、以及丢包率三个性能指标的影响。第四章讨论了信息反馈策略 思想在动态源路由协议中的实现，并做出了仿真和实验比较。第五章讨论了路由 5 无线白组织网络中容错动态源路由协议研究 预测策略对动态源路由协议中失效路由的预测与替换带来的性能提高，并做出了 仿真试验和比较分析。最后是结论，总结全文并展望未来的研究工作。 6 硕士学位论文 第2 章无线自组织网络中动态源路由协议概述 2 1 动态源路由协议概述 无线自组织网络的路由协议大致可以分为先验式( p r o a c t i v e ) 路由协议、 反应式( r e a c t i v e ) 路由协议以及混合式路由协议。动态源路由( d y n a m i cs o u r c e r o u t i n g ) 协议属于反应式路由协议的一种。 2 1 1 动态源路由协议介绍 动态源路由协议是由美国卡耐基梅隆大学m o n a r c h i 作组提出的一种基于源 路由的按需路由协议，属于反应式协议的一种。它是专门为多跳的移动无线自组 织网络设计的简单而高效的路由协议。使用动态源路由协议，网络可以在没有任 何已有基础设施和管理的条件下实现完全的自组织和自配置。网络中的各个节点 都尽力帮助其它节点转发数据包从而实现数据包在源、目的节点间的多跳传递。 动态源路由协议允许节点在无线自组织网路中动态地发现一条通向任何目 的节点的多跳路由。每个从源节点到目的节点的数据包的头部都携带了一个从源 节点到目的节点所要经过的所有中间节点的列表，这样其它所有转发此数据包的 节点或侦听到这个数据包的节点都可以从中获得有用的路由信息并保存到自己的 路由缓存中备用。使用d s r 的节点只维护正在通信的路由信息，不使用周期性的路 由信息广播完成路由信息的更新。当一个节点需要一条到某个目的节点的路由时， 节点动态的从路由缓存中选择一条或者通过路由发现过程发现一条新的路由，当 节点发现与某个邻居节点间的链路失效后，通过路由维护过程完成路由的切换。 所以d s r 协议由两个重要的机制组成：路由发现( r o u t ed is c o v e r y ) 和路由维护 ( r o u t em a i n t e n a n c e ) 。 2 1 2 路由发现原理 d s r “路由发现过程 ( r o u t er e q u e s tp r o c e s s ) 的目的在于发现从源节点 到达目的节点的路由，源节点通过广播“路由请求分组 ( r o u t er e q u e s t ) 来完 成路由发现全过程。 当有数据包要发送时，源节点先检查缓存中是否有到达信宿的路由信息，若 有一个非过期的路由。则节点采用一定的路由选择策略，例如选择最少跳数的一 条路由来发送分组。如果没有这样的路由，就广播一个路由请求分组来发起一个 新的路由发现过程。路由请求中包含了“目的节点地址 、“路由记录 和一个 唯一的“请求i d ”字段。 7 无线自组织网络中容错动态源路由协议研究 再广播r r e p 请求 图2 1d s r 协议路由发现过程 如图2 1 中的虚线表示采用广播的传输方式，进行路由的初始化，而图中的 s ，e ，f ，j 就表示从源端到所有经过的中间结点标识符的记录。中间节点收到后， 判断其是否有到目的节点的路由，若没有，则将其地址附加到分组的路由记录中， 再转发给邻近点。当目的节点进行应答时，它将路由记录信息从路由请求分组中 复制到应答分组中。在返回应答过程中必须注意的是，需要先检查路由缓存中是 否有到源节点的路由，如果网络链路是对称的，则可采用反向解析获得。否则， 节点必须发起新的路由发现过程去获得通往信源的路由。源节点在收到路由应答 后，会根据路由应答中包含的路径信息形成一条新的路由，用来发送已经缓存到 发送缓冲区的和其后生成的发往该目的节点的分组。至此，就完成了一次路由发 现过程。 2 1 3 路由维护原理 由于无线节点的移动或者其信号受到干扰而导致的网络拓扑变化，使得无线 自组织网络中的路由失效成了一种不可避免的现象。路由中的任何一条链路失效 都将导致整条路由的失效，因此路由协议需要监测每一跳链路的有效性，若发现 了链路失效，就要通知使用路由的源节点，这个监测和通知的过程就是路由维护。 在动态源路由协议中，没有任何周期信息辅助完成路由维护功能。路由维护 首先要监测到路由错误，发现路由错误可由以下方法获得。 1 ) 链路监测。无线信道相对于有线信道的可靠性要差一些，因此通常在无 线网络的数据链路层上选择逐跳( h o p - b y - h o p ) 确认的方式进行监测，以取得分 组转发成功与否的判断功能。在数据链路层取得路由链路的监测功能是比较方便 的，因为在相隔一跳的两个节点之间，节点可以通过转发分组监测另外的一个节 点是否正常工作。假如转发分组的一个节点在数据链路层检测到转发故障并且不 能恢复，它将会生成一个“错误分组 ( e r r o rp a c k e t ) 通知给上层软件。 2 ) 如果有些无线网络不能提供数据链路层这样低层的监测功能，一种叫做 被动确认( p a s s i v ea c k n o w le d g e m e n t ) 的机制可以提供链路监测的功能。如图2 2 ， 8 硕士学位论文 节点a 如果可以侦听到节点b 将分组转发给节点c ，那么节点a 就能确定a - b 链路是正 常工作的，从a 转发给b 的分组是成功到达了b 。 厂 厂 广 a 卜刊b 卜_ 刊c i 一i 一1 一 图2 2 简单的a dh o c 分组转发示意图 另外一种方法就是发送确认分组，在图2 2 中，节点a 转发分组给节点b ，随后 a 可以发送一个请求分组给b ，要求b 回应一个明确的应答。a 如果能在某个指定时 间内收到b 的应答，则表示a b 是正常工作的。 d s r 的路由维护具体过程是这样的：当节点在发送或者转发数据分组( 非d s r 控制分组) 时，都要把分组先存到“重传缓冲区”( r e t r a n s m is s i o nb u f f e r ) 中， 然后将分组按照其头部所携带的源路由信息发送到指定的下一跳节点，下一跳节 点在收到该分组后，必须向发送给它分组的上一跳节点回复一个a c k 分组，上一跳 节点收到这个a c k 后会将其对应的数据分组从重传缓冲区中删除，如果在指定时间 内，节点没有收到下一跳所发回的某一数据分组所对应的a c k 分组，则重传缓冲区 中的该数据分组会被重传，若超过一定次数的重传后节点仍旧没有收至s j a c k ，则节 点认为它与下一跳节点之间的链路已经失效。于是，该节点会删除其路由缓存中 所有包含该失效节点的路由信息，然后构造一个“路由错误分组 ( r o u t ee r r o r ) ， 并将此错误分组回传给发出数据分组的源节点，中间所有转发错误分组的节点也 都会将包含有该错误分组报告的失效节点的路由删除。当源节点收到该错误分组 并删除了所有包含该失效节点的路由后，它会从其路由缓存中另外选取一条新的 路由继续发送其数据分组，如果其路由缓存中已经没有到目的节点的别的路由了， 则源节点会重新发起一次路由发现过程。 2 2 动态源路由协议数据分组格式 动态源路由协议使用一个d s r 头结构来携带控制信息，这个d s r 头可以被任何 已经存在的i p 分组携带。d s r 头的开始部分是一个固定尺寸的结构体，其后跟随若 干个携带选项信息的d s r 选项结构体。整个d s r 头的结束由包含在开始部分固定结 构体中的头部长度来指示。d s r 头应该被插入到现存i p 分组的i p 头和任何的传输层 协议头之间。d s r 分组结构如图2 3 所示。 插入d s r 头以后，i p 头的结构无需改动但i p 头中的若干个域需要修改以区别 d s r 包与普通i p 包：i p 头中的协议域需要修改为d s r 协议标识，由于d s r 信息的插入， 整个数据包的长度即i p 头中的总长度域也要被修改。i p 头的目的地址应该被修改 为d s r 源路由中的下一跳地址，如果是d s r 路由请求包则应该将其置为本地广播地 址，i p 头中任意其它域的改动都会引起头部校验和的变化，需要用函数重新计算。 9 无线白组织网络中容错动态源路由协议研究 啦版本玳首部8 位服务类型 1 啦总长度( 字节数) 号长度( t o s ) 1 6 位标识3 位标志1 3 位片偏移 8 位生存时间f f t l )8 0 协议1 6 位首部校验和 3 2 位源i p 地址 3 2 位目的i p 地址 选项( 如果有) i p 、 8 位d s r 头固定部分d s r o p t i o n 部分 数 传输层协议头部分 据 包 载 荷 区、 ， 图2 3d s r 分组结构 2 2 1d s r 头( 固定部分) d s r 头携带了每个d s r 数据包中所必有的一些信息。它的格式如下图2 4 所示。 l ，1 字节、，1 9 节、， 2 9 节 、 l n e x th e a d e r r e s e r v e d p a y l o a dl e n g t h o p t i o n 图2 4d s r 头部结构 其中n e x th e a d e r 域指示紧跟在d s r 头后面的是哪个协议头。p a y l o a dl e n g t h 域指示d s r 头中整个o p t i o n 域的长度。o p t i o n 域是一个变长的数据区，各种d s r 选 项在需要时都被插入到这个o p t i o n 域中传输。 2 2 2 路由请求选项( r o u t er e q u e s to p t i o n ) 路由请求选项的格式如下图2 5 n 示。 当d s r 头中包含路由请求选项时，承载这个d s r 包的i p 数据包的源地址应该被 置为发送这个路由请求的源节点地址，在这个数据包的传播过程中，源地址域不 能被改动，目的地址应该被置为广播地址( 2 5 5 2 5 5 2 5 5 2 5 5 ) 。选项类型( o p t i o n t y p e ) 域为2 ，o p td a t al e n 为除过选项类型和长度域外，路由请求选项中其它内 容的长度。标志符( i d e n t i f i c a t i o n ) 域是一个由发出这个路由请求的源节点产 生的一个区别于其它的唯一值，用来区别该路由请求和本节点发出的其它路由请 求。目的节点地址( t a r g e ta d d r e s s ) 域记录着该路由请求所要查询的目的节点 地址，后面紧跟着的是该路由请求从源节点到目的节点前所经过的中间节点的地 址列表。 l o 硕十学位论文 。! 主堇，l 。! 主堇，l 。 兰皇堇 ， o p t i o nt y p eo p t d a t a l e n l d e n t i f i c a t i o n t a r g e ta d d r e s s a d d r e s s 1 】 a d d r e s s 2 a d d r e s s 【n 】 图2 5 路由请求选项结构 2 2 3 路由应答选项( r o u t er e p l yo p t i o n ) 路由应答选项的格式如图2 6 所示。 。! 主堇，l 。! 皇堇，i 。 呈皇堇 ， o p t i o nt y p e o p td a t a lr e s e r r e d i d e n t i f i c a t i o n l e n a d d r e s s 1 a d d r e s s 2 a d d r e s si n 图2 6 路由应答选项结构 当d s r 头中包含路由应答选项时，承载这个d s r 包的i p 数据包的源地址应该被 置为发送这个路由应答的源节点地址，目的地址和收到的承载路由请求的i p 包的 源地址相同。选项类型( o p t i o nt y p e ) 域为3 ，o p td a t al e n 为除过选项类型和 长度域外，路由应答选项中其它内容的长度。外部最后一跳( l a s th o pe x t e r n a l ) 指示由该路由应答所返回的路由的最后一跳的节点是一个d s r 子网外部的节点。标 志符( i d e n t i f i c a t i o n ) 域的值和引起该路由应答的路由请求的标志符域的值相 同，后面紧跟着的是从以承载该路由应答的i p 包的目的地址域的地址所指示的节 点到它所查询的目标节点的源路由列表，a d d r e s s n 即为它所查询的目表节点的 地妇 = 。 2 2 4 路由错误选项( r o u t ee r r o ro p t i o n ) 路由错误选项的格式如图2 7 所示。 f ， 1 字节 、 1 字节 2 字节 o p t i o nt y p eo p td a t al e n e r r o rt y p er es e r v e ds a l v a g e e r r o r s o u r c ea d d r e s s e r r o rd e s t i n a t i o i la d d r e s s t y p e s p e c i f i ci n