（计算机应用技术专业论文）ad+hoc网络中的抢先式按需路由研究.pdf

摘要 摘要 现有的a dh o c 按需路由协议在路由发现过程中仅根据路由跳数和路由 f r e s h 程度等参数进行路由选择，而不考虑构成路由的各条链路的状态。这将增 加使用潜在的不可靠路由的可能，而使用不可靠路出的一个直接后果就是导致频 繁的路由失效。同时，现有的a d h o c 按需路由协议只有在确定原有路由已经失 效后才采取路由维护动作，这将导致确定路由失效以及进行路由重建的代价；而 在路由重建过程中，分组可能被延迟甚至被丢弃，这必然会严重影晌路由协议的 性能和网络的服务质量。 本论文提出了一种针对a dh o c 按需路由协议的抢先式扩展算法。该扩展算 法由链路状态分析、抢先式路由发现和抢先式路由维护三个部分构成，其中链路 状态分析是整个算法的核心。根据信号历史记录值，通过特定的预测算法可以获 得链路失效时间的预测值。而路由的失效时间等于构成该路由的所有链路的失效 时间的最小值。在路由发现过程中，进行路由选择时除了考虑路由跳数和其它的 传统参数外，还加入了路由失效时间作为另外一个参数。当链路失效时间的预测 值低于一定的阈值后，即认为该链路已进入危险期，节点需要采取相应的抢先式 路由维护动作，在路由真正失效前获得新的路由。这样就可以避免由于路由失效 而造成的延迟抖动和分组丢失。 我们在n s 2 下实现了针对a o d v 的抢先式扩展。对c b r 业务的仿真实验 结果表明，抢先式算法可以在很大程度上减少c b r 业务的路由失效次数提高 分组的投递率、降低分组投递延迟。同时，算法也将路由协议的开销控制在一个 可以接受的范围内。对于t c p 在抢先式路由中的性能，我们也进行了相应的仿 真实验并对仿真的结果进行了分析。 关键字：a dh o c ，按需路由， 链路状态分析，抢先式路由发现，抢先式 路由维护，a o d v a b s t r a c t a b s t r a c t e x i s t i n go n d e m a n da dh o cr o u t i n gp r o t o c o l sd or o u t es e l e c t i o no n l ya c c o r d i n g t ot h er o u t eh o p sa n dr o u t ef r e s hs t a t ea n ds o m e t h i n ge l s e t h es t a t eo fl i n k st h a t c o n s t r u c tt h er o u t ei sn o tc o n s i d e r e da ta 1 1 t h i sn e g l e c ti n c r e a s e st h er i s ko f u s i n ga p o t e n t i a lu n r e l i a b l er o u t e ，w h i c hr e s u l t si nf r e q u e n tr o u t eb r o k e n m e a n w h i l e ，e x i s t i n g o n d e m a n da dh o cr o u t i n gp r o t o c o l st a k er o u t em a i n t e n a n c ea c t i o n so n l ya f t e rap a t h b r e a k s ，i n c u r r i n gas i g n i f i c a n tc o s ti nd e t e c t i n gt h ed i s c o n n e c t i o na n de s t a b l i s h i n ga n e wr o u t e d u r i n gt h er o u t e r e c o n s t r u c t i o n ，p a c k e t s c a nb ed e l a y e do re v e nb e d r o p p e d ，w h i c hw i l l c a u s es i g n i f i c a n tp e r f o r m a n c ed e g r a d a t i o no fa dh o cr o u t i n g p r o t o c o la n da f f e c tt h eq o s o f t h en e t w o r k i nt h i st h e s i s ，w ep r o p o s e da p r e e m p t i v ee x t e n s i o nt oo n d e m a n da dh o cr o u t i n g p r o t o c o l s t h ee x t e n s i o nc o n s i s t so ft h r e em o d u l e s ：l i n ks t a t ea n a l y s i s ，p r e e m p t i v e r o u t e d i s c o v e r y a n d p r e e m p t i v e r o u t em a i n t e n a n c et h ee s s e n t i a l p a r t o ft h e p r e e m p t i v ee x t e n s i o ni st h el i n ks t a t ea n a l y s i sm o d u l e ，w h i c hi s a b l et op r e d i c tt h e b r o k e nt i m eo fal i n k t h ep r e d i c t i o ni sb a s e do nt h es i g n a lh i s t o r yo fal i n ka n d a c t i v a t e db yap r e d i c t i o na l g o r i t h m t h er o u t eb r o k e nt i m ei se q u a lt ot h em i n i m u m b r o k e nt i m eo ft h el i n k st h a tc o n s t r u c tt h e r o u t e d u r i n gt h er o u t ed i s c o v e r y , t h er o u t e s e l e c t i o nd e p e n d so nn o to n l yt h er o u t eh o p sa n dt h eo t h e rc o n v e n t i o n a lp a r a m e t e r s b u ta l s ot h ep r e d i c t e dr o u t eb r o k e nt i m e v v h e nap a t hi s l i k e l yt ob eb r o k e ns o o n ( w h i c h i si n d i c a t e db yt h e p r e d i c t e dl i n kb r o k e nt i m e ) ，ar o u t ew a r n i n gi ss e n tt ot h e s o u r c ei n d i c a t i n gt h el i k e l i h o o do ft h ed i s c o n n e c t i o n t h es o u r c ec a nt h e ns e l e c ta n e wr o u t et ou s eo ri n i t i a t ean e wr o u t ed i s c o v e r y s o ，an e wr o u t ec a l lb eg o tb e f o r e t h eo l dr o u t ea c t u a l l yb r o k e n ，p o t e n t i a l l ya v o i d i n gt h ed e l a y - j i t t e ra n dp a c k e t sl o s t b e c a u s eo f t h ed i s c o n n e c t i o n w eh a v ed o n ea ne x t e n s i o nt oa o d v p r o t o c o l ，u s i n g0 1 1 1 a l g o r i t h m 。al o to f s i m u l a t i o ne x p e r i m e n t sh a v eb e e nd o n eu n d e rn s 2 t h er e s u l to ft h es i m u l a t i o n s d e m o n s t r a t e st h a tt h ep r o p o s e dp r e e m p t i v er o u t ed i s c o v e r ya n dr o u t em a i n t e n a n c e m e c h a n i s ma d d e dt oa o d vs i g n i f i c a n t l yr e d u c e st h en u m b e ro fp a t h b r e a k s ， t h e r e f o r ee n h a n c e st h ep a c k e td e l i v e r yr a t i oa n dd e c r e a s e st h ep a c k e td e l a y , w i t ha s m a l li n c r e a s ei np r o t o c o lo v e r h e a d w ea l s os h o wa n da n a l y z es o m ee x p e r i m e n t a l r e s u l t so b t a i n e db y r u n n i n gt c p o nt o po f t h e p r e e m p t i v er o u t i n g s c h e m e s k e y w o r d s ：a dh o cn e t w o r k s ，o l ld e m a n d r o u t i n g ，l i n ks t a t ea n a l y s i s ，p r e e m p t i v er o u t e d i s c o v e r y , p r e e m p t i v er o u t em a i n t e n a n c e ，a o d v - i l - 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得鑫注本鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：彦毙l 签字日期：二口。弓年j 一月口| = = 1 学位论文版权使用授权书 本学位论文作者完全了解墨盗盘堂有关保留、使用学位论文的规定。 特授权鑫蓬盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：锄 签字日期：刎；年j 一月，f 1 导师虢苌誉通差 签字日期：2 笋5 月i j 同 第一章绪论 第一章绪论 1 1 无线网络的发展及研究现状 无线网络自从二十世纪七十年代出现以来，越来越受到计算机产业的重视。 尤其是最近十年间，由于无线网络与移动技术相结合，令其大受欢迎。当前存在 着两种移动无线网络：第一种是有基础设施( i n f r a s t r u c t u r e d ) 的网络，该网络由 若干移动节点和被称之为“基站”的基础设施组成，网络中的移动节点直接与其 通信半径之内的最近的基站连接并完成通信。当移动节点离开了某一基站的通信 范围而进入另一基站的通信范围时，原基站与新基站之间要进行转接( h a n d o f f ， 从而使移动节点可以不受妨碍地继续进行网络通信。第二类移动无线网络是无基 础设施的( i n f r a s t r u c t u r e l e s s ) ，通常被称为a dh o c 网络。随着无线技术的进一步 发展，a dh o c 网络以其方便灵活的特点越来越受到人们的重视，关于该网络中 的路由协议及其性能评价成为了当前研究的一个热点。 a dh o c 网络是一种不需要任何提前给定的基础设施就能进行组网的网络形 式。为了实现不在通信范围内的网络节点之间的通信，i e t f 的m a n e t 4 、组给出 了多种可以用于组成移动a dh o c 网络的路由协议，如d s r 、a o d v 、d s d v 和 t o r a 等。已经有很多人针对这些路由协议做了大量的性能分析和研究，如 j b r o c h 等在 2 】中分析了特定移动场景和业务场景下d s d v 、d s r 、a o d v 和t o r a 四种协议在丢包率、路由开销和路径长度方面的特性。pj o h a n s s o n 等在 3 7 的一 个扩展场景中比较了三种协议在丢包率、路由开销、吞吐率和延迟方面的特性。 1 2 背景和动机 在a dh o c 网络中，节点的移动性会导致频繁的路由失效。路由失效后需启 动路由重建过程。在路由重建过程中，待发送或者待转发分组被存放在缓冲区内， 如果存放分组的缓冲区溢出或者路由重建失败，分组就会被丢弃：同时由于分组 缓冲造成的分组延迟抖动对于有些实时业务如l i v ea u d i o 、l i v ev i d e o 等来既是 不能接受的，而分组丢弃会导致响应业务( 如t c p 业务) 的发送窗口降低，严 重影响网络的利用率和吞吐率。 路由失效会严重影响a dh o c 路由协议的性能，而现有的a dh o c 按需路由 协议都没有提供对路由失效的有效处理：路由发现仅根据路由f r e s h 程度和路由 跳数等参数进行路由选择，且只有当路由失效后才会采取路由维护动作。路由发 第一章绪论 现导致了使用潜在的不可靠路由，造成频繁的路由失效；路由维护造成分组延迟 的抖动和分组丢失。因此，需要提供一种机制来处理路由失效，以提高按需路由 协议的性能。本论文正是针对上述问题提出了一种解决的方法。 1 3 论文的主要工作 本论文提出了针对无线a d h o c 网络按需路由协议的一种扩展算法。算法的 基本思想是利用无线移动节点间的链路状态信息，在路由发现过程尽量保证路由 的可靠性，而在当路由中的某条链路进入危险期以后采取相应的抢先式动作，在 路由失效前完成路由的切换，避免由于路由失效造成的延迟抖动和分组丢失。该 算法由三个模块组成即链路状态分析模块、抢先式路由发现模块和抢先式路由维 护模块。链路状态分析是整个算法的基础，该模块通过对i e e e8 0 2 1 1 协议的扩 展来完成。抢先式路由发现和抢先式路由维护主要通过对路由协议层的扩展来完 成。本论文的主要工作如下： 1 根据已有的关于a d h o c 网络节点运动和节点间信号变化规律的理论分析6 ， 1 1 ，提出了一种针对无线链路的链路状态分析算法。仿真结果表明，该算法可 以较为精确的预测到绝大部分链路失效。 2 对a dh o c 按需路由协议的路由发现过程提出了一种改进方案，改进后的路 由发现机制综合地使用路由f r e s h 程度、路由失效时间和路由跳数等参数进行路 由选择，并不再允许任何中间节点发送路由应答。 3 参照已有的类似算法 1 ，7 ，8 ，9 ，并通过对算法的进一步改进，形成了一 种针对a dh o c 按需路由协议路由维护过程的抢先式算法，改进后的算法利用链 路状态分析的结果来对危险状态进行界定，同时在算法中还加入了相应的机制以 保证路由警告信息发送的顺利完成。仿真结果表明，上述的抢先式路由维护算法 通过在链路进入危险期后即提前采取路由维护动作，在路由真正失效前完成到新 路由的切换过程，可以在很大程度上降低由于路由失效而造成的不利影响。 4 在n s 中完成了上述算法的i e e e8 0 2 1 1 和a o d v 的扩展，并进行了相应的 仿真实验，对扩展前后的路由协议性能进行了比较和评价 1 4 论文结构 论文第二章介绍与本论文相关的背景知识，对a dh o c 无线移动网络进行了 综述，包括a d h o c 网络特点及其对路由协议的一些要求，同时还介绍了目前a d h o c 网络路由的研究现状和几种典型的a dh o c 按需路由协议。第三章详细论述 第一章绪论 了链路状态分析算法，对无线a dh o c 网络中节点的运动模型、无线信号的衰减 规律和链路失效时间预测算法等进行了说明，并给出了一个针对i e e e s 0 2 1 1 的 仿真结果。第四章是对抢先式路由发现过程的一个详细阐述，论述了抢先式路由 发现的基本思想、算法设计和实现细节。第五章详细论述了抢先式路由维护算法， 包括了抢先式路由维护的机制、过程和实现细节。第六章的主要内容包括针对 c b r 业务和t c p 业务的仿真结果及其分析。第七章对整个论文进行了总结并提 出了对今后研究的展望。 第二章a d h o c 路由协议简介 第二章a dh o c 路由协议简介 移动主机和其它无线设备的广泛使用推动了无线网络的发展。无线网络主要 有两种组织形式：一种被称为基础设施网络( i n f r a s t r u c t u r e n e t w o r k s ) ，即这种无 线网络依赖于已有的被称为接入点( a c c e s sp o i n t ) 的设备，网络中的移动单元 通过与通信范围内的最近的a p 通信而参与该网络。无线网络的另外种组织形 式被称之为a d h o c 网络，a d h o c 网络无需基础设施的支持，无线移动节点间直 接进行通信。本章着重介绍a dh o c 网络及其路由问题。 2 1 引言 我们经常提及的移动通信网络一般都是有中心的，要基于预设的网络设施才 能运行。例如，蜂窝移动通信系统要有基站的支持；无线局域网一般也工作在有 a p 接入点和有线骨干网的模式下。但对于有些特殊场合来说，有中心的移动网 络并不能胜任。比如，战场上部队快速展开和推进，地震或水灾后的营救，以及 临时会议等。这些场合的通信不能依赖于任何预设的网络设施，而需要一种能够 临时快速自动组网的移动网络。a dh o c 网络可以满足这样的要求，一个典型的 a d h o c 网络结构如图2 1 所示。 a dh o c 网络的前身是分组无线网( p a c k e tr a d i on e t w o r k ) 。对分组无线网的 第二章a dh o c 路由协议简介 研究源于军事通信的需要，并已经持续了近2 0 年。早在1 9 7 2 年，美国d a r p a ( d e f e n s ea d v a n c e dr e s e a r c hp r o j e c ta g e n c y ) 就启动了分组无线网( p r n e t ， p a c k e t r a d i o n e t w o r k ) 项目，研究分组无线网在战场环境下的数据通信中的应 用。项目完成之后，d a p r a 又在1 9 9 3 年启动了高残存性自适应网络( s u r a n ， s u r v i v a b l ea d a p t i v en e t w o r k ) 项目。研究如何将p r n e t 的成果加以扩展，以 支持更大规模的网络，还要开发能够适应战场快速变化环境下的自适应网络协 议。1 9 9 4 年，d a r p a 又启动了全球移动信息系统( g l o m o ，g l o b l em o b i l e i n f o r m a t i o ns y s t e m s ) 项目。在分组无线网已有成果的基础上对能够满足军事应 用需要的、可快速展开、高抗毁性的移动信息系统进行全面深入的研究，并一直 持续至今。1 9 9 1 年成立的i e e e 8 0 2 1 1 标准委员会采用了“a d h o c 网络”一词来描 述这种特殊的对等式无线移动网络。 在a dh o c 网络中，节点具有报文转发能力，节点间的通信可能要经过多个 中间节点的转发，即经过多跳( m u l t i h o p ) ，这是a dh o c 网络与其他移动网络 的根本区别之一。节点通过分层的网络协议和分布式算法相互协调，实现了网络 的自动组织和运行。因此a d h o c 网络也被称为多跳无线网络( m u l t i h o p w i r e l e s s n e t w o r k ) 、自组织网络( s e l fo r g a n i z e dn e t w o r k ) 或无固定设施的网络 ( i n f r a s t r u c t u r e l e s sn e t w o r k ) 。 2 2 无线a d h o c 网络中的路由 在a dh o c 网络中，移动节点通过多跳无线链路实现相互间的通信。整个网 络没有固定的基础设施，网内每一个节点都可作为路由器，向其它节点转发数据。 因此，开发一种能有效地找到节点问路由的动态路由协议就成为a dh o c 网络设 计的关键。 2 2 1a dh o c 路由协议分类 总的来说，a d h o c 网络中的路由协议大致可以分为两种类型：表驱动( t a b l e d r i v e n ) 路由协议和按需( o n d e m a n d ) 路由协议。 表驱动路由协议采用周期性的路由分组广播，来交换路由信息。每个节点维 护到达全网所有节点的路由。表驱动路由的优点是当节点需要发送一个到达其他 节点的数据分组时，只要路由存在，发送分组的延时就很小；缺点是表驱动路由 协议需花费较高代价( 如带宽、电源、c p u 资源等) ，使路由表能够跟上当前网络 拓扑结构的变化，但动态变化的拓扑结构又可能使高价得来的路由表中内容变成 无效信息，路由协议始终处于不收敛状态。目前，这种类型的无线a dh o c 网络 第二章a dh o c 路由协议简介 路由协议己提出了几种机制，用以改善这些方面的性能。 按需路由协议是根据发送节点的需要，按需进行路由发现过程，网络拓扑结 构信息和路由表内容也是按需建立的，所以其内容可能仅仅是整个网络拓扑结构 信息的一部分。按需路由的优点是不需要周期性的广播路由信息，节省了一定的 网络资源：缺点是在发送数据分组时，若没有到达目的节点的路由，要启动路由 发现过程来寻找路由，所以数据分组需要等待一定时间的延时，并且由于路由发 现过程通常采用在全网范围内的广播来完成，这在一定程度上也抵消了按需机制 带来的好处。从目前研究情况看，按需路由是未来的发展方向，无线网络具有与 有线网络不同的约束条件，按需路由更能满足需要。 目自u ，国内外的研究人员基于各种不同的角度提出了许多针对无线a dh o c 网的路由协议，其中一部分也提交到m a n e t ( m o b i l ea d h o cn e t w o r k ) 工作小 组成为r f c 草案。下面列举一些典型的a dh o c 网络路由协议： d s d v ( 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 o w r p ( w i r e l e s sr o u t i n gp r o t o c 0 1 ) d s r ( d y n a m i c s o u r c er o u t i n g ) a b r ( a s s o c i a t i v i t y b a s e d r o u t i n g ) z r p ( z o n er o u t i n gp r o t o c 0 1 ) a o d v ( a d h o co nd e m a n dd i s t a n c ev e c t o rr o u t i n g ) t o r a ( t e m p o r a l l y o r d e r e d r o u t i n ga l g o r i t h m ) l s q o s ( l i n k - s t a t eb a s e dq o sr o u t i n g ) 图2 - 2a dh o c 网络路由协议分类 第二章a dh o e 路由协议简介 使用表驱动路由的节点维护整个网络拓扑，而按需路由机制中的各个节点仅 维护当前正在进行使用的路由；表驱动路由进行周期性的信息更新保证路由的有 效性，而按需路由会将不再使用的路由从路由表中删除，而在需要进行通信但没 有路由可用时才动态的发现新的路由。下表是表驱动路由和按需路由之间的对 比 表驱动按需路路由协议 路由协议d s d v 、c g s r 、w r pa o d v 、d s r 、t o r a 、 a b r 、s s r 、l m r 路由获取延迟低高 一 控制负载局低 耗电量高低 带宽开销高低 表2 - 1 表驱动路由协议与按需路由协议比较 2 2 2 按需路由机制 按需是a dh o c 网络中的一种路由机制，按需路由基于如下的前提：如果所 有的问题和矛盾都可以被监测到，则解决这些问题或者消除这些矛盾的工作可以 被推迟到十分需要的时候。这也可以被视为是一种“懒惰的哲学” 4 0 。因此， 按需路由不使用周期性的路由信息更新而是仅在需要的时候刊进行路由信息的 更新。 按需路由主要由路由发现和路由维护两部分组成。当源节点欲发送信息到达 某个目的节点而路由表中并不存在到达该目的节点的路由时，节点会通过广播路 由请求分组发起一次新的路由发现过程，以发现到达目的节点的路由。当正在进 行通信的路由失效后，节点会通过路由维护过程进行路由的切换。有些a dh o c 路由协议可能会使用源路由机制，源路由是一种由数据分组的发送节点决定整个 传输过程中的完整路由的路由机制。到目前为止，已知的a d h o c 源路由协议只 有c m u m o n a r c h 工作组提出的d s r 4 1 。在本节其后的论述中，除非特殊指明， 否则均不考虑源路由机制的特殊处理。对于源路由的具体处理机制可参阅下一节 关于d s r 协议的论述和相关的论文 4 2 、4 3 、4 4 1 。 1 路由发现 路由发现的目的在于发现从源节点到达目的节点的路由，源节点通过广播路 由请求分组发起路由发现过程。路由发现过程可以划分为如下几个子过程：路由 请求发送、路由请求转发、路由应答发送、路由应答转发和路由选择策略。 第二章a dh o c 路由协议简介 路由请求发送过程由源节点发起，源节点在欲发送分组到达目的节点而此时 源节点路由表中不存在到达目的节点的路由，源节点就会通过广播路由请求分组 来发起一次新的路由发现过程，如果在一定时间间隔内源节点没有收到任何的路 由应答消息，源节点会尝试再次发送路由请求分组，如此过程直至到达规定的最 大重传次数或者其它的限制条件，即认为此次路由发现过程失败。 任何中间节点收到路由请求分组后，都应该进行相应的处理。为了防止同一 个节点多次收到同一个路由请求分组并进行多次处理，按需路由机制需要使用一 种策略来处理这种问题，最简单的方式就是使用一个数据结构，该数据结构中保 存了在过去一段时间内收到的路由请求分组的相关信息，该数据结构以源节点地 址和路由请求分组的m 作为索引。如a o d v 使用了b r o a d c a s ti d 链表而d s r 使用了路由请求表来完成上述的功能。如果节点刚刚收到的路由请求分组是以前 没有收到过的，则节点需要添加一条临时反向路由用来转发将来可能会存在的路 由应答。如果为目的节点或者虽然不是目的节点但是存在到达目的节点的路由， 则节点需要根据路由请求分组携带的信息和已有的路由信息构造并发送路由应 答，否则，节点应该再次转发该路由请求分组。 目的节点在发送路由应答时需要将路由请求中相关的信息体现在路由应答 中，如路由请求中源节点的信息、路由跳数等。如果使用源路由机制，目的节点 需要将路由请求中所包含的源路由反转以后作为发送路由应答的路由：否则，节 点只需使用路由请求分组到达的前一跳节点作为发送路由应答下一跳将路由应 答发送到下一跳节点即可。 中间节点在收到路由应答以后，首先需要更新到达目的节点的路由，该路由 将用来转发到达目的节点的数据分组。然后，节点需要根据在转发路由请求时添 加的临时反向路由转发该路由应答。依此类推，直至路由应答到达了发起路由请 求的源节点。 源节点在收到路由应答后，首先启动路由选择策略确定是否使用新发现的路 由。一般来讲，路由选择策略中主要的参数有路由f r e s h 程度和路由跳数。如果 路由表中不存在到达该目的节点的路由，或者虽然存在到达该目的节点的路由但 是该路由的f r e s h 程度不如新发现的路由，或者虽然已有路由和刚刚到达的路由 f r e s h 程度一样，但是刚刚到达的路由的路由跳数比已有路由的路由跳数小，则 源节点会使用刚刚得到的路由替换原有的路由。源节点在更新路由以后应该将正 在缓冲的发往该目的节点的数据分组通过刚刚得到的路由发送出去。其后发送的 到达该目的节点的分组将一直使用该路由，直至业务结束或者路由失效。若发生 路由失效，协议需要使用路由维护机制完成路由的切换。 第二章a dh o c 路由协议简介 2 路由维护 由于无线节点的移动而导致的网络拓扑变化，使得a dh o e 网络中的路由失 效成了种不可避免的现象。路由中的任何一条链路失效都将导致整条路由的失 效，因此协议需要监测每一跳链路的有效性。 为了监测链路的有效性，在发送或者转发分组时，路由协议需要保证分组被 下一跳节点正确接收。为了提供这种保证，有若干种方式：1 ) 显式a c k ：后继 节点在收到来自前驱节点的分组后，显式的向前驱节点发送一个应答a c k ；前 驱节点在发送分组后等待来自后继节点的a c k ，如果在指定的时间间隔内没有 收到来自后继节点的a c k ，则前驱节点会尝试重传该分组，直至到达规定的最 大重传次数，则认为该链路已经失效。2 ) 隐式a c k ：后继节点收到来自前驱节 点的分组时并不向前驱节点发送显式a c k ，而是由前驱节点通过使用混杂模式 监听后继节点向其下一跳转发该分组确定后继节点已经收到该分组。由于分组到 达目的节点后将不再被转发，因此，目的节点在收到分组后需要向其前驱节点发 送一个显式a c k 。3 ) 可以使用邻居节点间周期性的h e l l o 消息确定节点与邻居 节点闻的链路的是否有效。每个节点周期性的向其邻居广播h e l l o 消息，邻居 节点在收到h e l l o 消息后更新其相应的路由记录；如果节点在规定的时间间隔 内没有收到来自某个邻居节点的h e l l o 消息，则认为节点与该邻居节点间的链 路已经失效。4 ) 使用m a c 层信息：如果节点使用的m a c 层使用了a c k 机制( 如 i e e e 8 0 2 1 1 ) ，路由协议可以使用m a c 层的a c k 来确定它的后继节点是否正确 收到了该分组。如果m a c 层在发送数据后收到了后继节点m a c 层的a c k 则 认为该后继节点已经正确接收到了这个分组；否则在m a c 层重传次数到达最大 值以后，m a c 层会将这个链路错误通知给路由协议层。比较上述方案可见，使 用显式a c k 和h e l l o 消息会在很大程度上增加协议的开销，同时使用h e l l o 消息也不能完全保证发送的分组被其后继节点正确接收：使用隐式a c k 可以将 路由开销维持在一个较低的水平上，但是使用隐式a c k 需要节点使用混杂模式 监听。而混杂模式将会在很大程度上增加节点的运算开销和电池消耗：使用m a c 层a c k 无需增加额外的开销和其它的消耗，只需在m a c 层正常运作的基础上 增加一个层间通信机制即可。 当节点确定与某个邻居节点间的链路失效后，需要向源节点发送一个路由错 误消息，将此路由失效通知给源节点。由于一条链路失效将会导致所有包含该链 路的路由失效，因此协议需要将路由错误通知到所有包含该链路的路由的源节 点。发现路由失效的节点向其所有使用该链路的路由的前驱节点发送个路由错 误消息，前驱节点在收到路由错误消息后，再次将该路由错误消息发送给它的所 有前驱节点，依此类推，直至该路由错误到达所有使用该链路的路由的源节点。 第二章a dh o c 路由协议简介 源节点在收到路由错误消息后需要进行路由切换：如果路由表中存在另外的 到达该目的节点的路由，则动态的从中选择一条作为新的路由使用；否则，源节 点需要发起新的路由发现过程。 2 2 3 典型a dh o e 按需路由协议简介 本节将对几种典型的a d h o c 路由协议作简单的介绍，其中包括种典型的 表驱动路由协议d s d v 1 3 年i i 两种典型的按需路由协议d s r 4 1 干ha o d v 4 5 。 2 2 3 1d s d v d s d v 是在传统的b e l l m a n f o r d 路由算法的基础上提出的。d s d v 比传统的 距离矢量路由的主要优势在于，d s d v 使用了目的节点序列号的技术来避免形成 路由环路，d s d v 通过对于每一条路由记录设置个目的节点序列号来实现这一 技术。 每个使用d s d v 路由协议的节点都维护一个路由表，路由表中包含了关于 所有己知目的节点的路由项。用来描述一条路由的主要参数包括：目的节点、到 达目的节点的路由跳数、下一跳节点和目的节点序列号。 d s d v 使用周期性( p e r i o d i c ) 路由更新和触发式( t r i g g e r e d ) 路由更新相结 合的方式来维护路由信息的一致性。当d s d v 在传输信息过程中发现网络拓扑 的变化时，会使用触发式路由更新。为了防止这种更新产生太大的网络业务开销， d s d v 定义了两种类型的路由分组。第一种路由分组称为“f u l l d u m p ”，这种路 由分组中包含了所有路由信息，而所有的路由信息可能需要使用若干个网络协议 数据单元( n p d u ) ；第二种路由分组中仅仅包括自上次f u l l d u m p 以来发生的路 由变化，丽在绝大多数情况下自上次f u l l d u m p 以来发生的路由变化可以使用一 个n p d u 来携带。这样就在很大程度上减少了由于路由信息更新而造成的网络 负载。 节点的运动导致节点间的链路失效，当一个节点离开了另外一个节点的通信 范围时，就造成了它们之问的链路失效。当一个节点与其邻居节点间的链路失效 后该节点的所有使用该邻居节点作为下一跳的路由都将被赋与一个无穷跳数以 及一个更新后的序列号，这也是唯一的由其它节点而非目的节点更新序列号的情 形。由目的节点更新的序列号是偶数，而由其它节点更新的序列号是奇数。当一 个节点得知其邻居节点具有一条无穷参数的路由，而该节点本身存在一条相应的 并非无穷跳数的路由，则该节点发起一次触发式路由更新过程，原有的无穷跳数 路由将会被新的路由所替换。 第二二章a dh o c 路由协议简介 当一个节点收到一个新的路由更新消息后。将该路由更新消息中包含的路由 信息与该节点已有的相应的路e h 信息进行比较。节点根据如下的原则进行路由的 替换： 使用序列号较大的路由替换序列号较小的路由。 如果两条路由的序列号相同，则使用跳数较少的路由来替换跳数较多的 路由。 如果网络中有许多节点，而这些节点问异步的进行路由信息更新，这将可能 导致路由更新风暴。为了防止由于路由信息更新而造成的业务风暴，d s d v 使用 了“s e t t l et i m e ”机制，任何节点在广播路由更新信息前都必须等待一段很短的 时l 司。 为了保证到达任何目的节点的路由中不存在环路，同时尽可能减少路由跳 数，d s d v 需要定期的在全网范围内广播路由更新消息。随着节点数的增加，每 个节点的路由表长度增加，进而导致路由更新消息的长度也增加，同时消息广播 的范围也会随着节点的数增加而增大，这就使得更新路由消息所使用的网络资源 大大增加，而且这种开销几乎不受节点运动状态的影响。b r o e h 等人在文献【i o 的仿真中发现：在节点运动频率和运动速度较低的情形下，d s d v 的性能相当不 错，几乎可以保证分组投递率为1 0 0 ，而当节点运动频率和运动速度增加时， d s d v 的性能迅速下降。 2 2 3 2d s r d s r ( d y n a m i cs o u r c er o u t i n g ，动态源路由协议) 是由美国卡耐基梅隆大 学m o n a r c h 工作组提出的一种使用源路由思想的a d h o c 网络按需路由协议。使 用d s r 的节点只维护正在通信的路由信息，也不使用周期性的路由信息广播完 成路由信息的更新。当一个节点需要一条到某个目的节点的路由时，节点动态的 从路由缓存中选择一条或者通过路由发现过程发现一条新的路由；当节点发现与 某个邻居节点间的链路失效后，通过路由维护过程完成路由的切换。 源路由是一种由数据分组的发送节点决定整个传输过程中的完整路由的路 由机制。源节点在发送数据分组时将完整的路由路径显式的列在分组的头部，路 由路径中包含了该分组从源节点到达目的节点的路径中的每一跳的信息如口地 址、网络接口等等。使用源路由的一个突出的优点在于任何中f 司节点都无需维护 对应于转发分组的路由，中间节点在收到分组后只需要根据源路由的地址列表中 选择下一跳节点，然后将该分组转发到下一跳即可。不同于传统的路由算法， d s r 不使用周期性路由信息广播来完成路由信息的更新，这样就在很大程度上 降低了路由协议的开销，尤其是当节点的运动频率和运动速度较低的时候。 第二二章a dh o c 路由协议简介 d s r 协议主要包含两个过程即路由发现和路由维护。当一个节点欲发送分 组到某个目的节点时，节点首先查看其路由缓存中是否存在到达该目的节点的路 由。如果路由缓存中存在到达目的结点的路由并且该路由没有超时，则节点使用 该路由发送分组：否则，节点就需要通过广播路由请求分组来发起一次新的路由 发现过程，以发现到达该目的节点的路由。路由请求分组中包含了源节点地址、 目的节点地址和一个用来唯一标识该路由请求的d 号。每个节点维护一个路由 请求表，其中记录了在过去一段时间内收到的路由请求信息，这些记录以源地址 和路由请求号作为索引。当任何中间节点收到路由请求后，首先查看路由请 求表中是否已经包含了关于该路由请求的记录，如果是，则简单的将该路由请求 分组丢弃；否则，节点查看路由缓存中是否存在到达路由请求所表明的目的节点 的路由，如果是则通过路由请求中已有的源路由地址列表和路由缓存中的路由信 息形成一个路由应答并将该路由应答发送给路由请求发起的源节点，否则，将本 机的口地址添加在路由请求中已有的地址列表中，然后将该路由请求再次发送 出去。当路由请求到达目的节点并且目的节点的路由请求表中没有相应的记录 时，目的节点则根据路由请求中的地址列表加上本机p 构造一个路由应答并且 将该路由应答通过这条路由发送到发起路由请求的源节点。源节点在收到路由应 答后，会根据路由应答中包含的路径信息形成一条新的路由，用来发送已经缓冲 的和其后到达的发往该目的结点的分组。至此，就完成了一次路由发现过程。 在发送和转发分组的过程中，路由维护过程用来检测路由失效。节点在发送 或者转发分组时，都要保证分组被正确的传输到路由中表明的下一跳节点，如果 分组没有被正确的发送到下一跳节点，则认为该节点与下一跳节点之间链路出现 了失效，进而也就导致了整条路由的失效。因此，需要另外一条新的路由来完成 对于其后分组的传递。此时节点需要通过路由维护过程来完成路由切换。发现路 由失效的节点需要向业务的源节点发送一个路由错误分组，源节点在收到路由错 误分组后，首先查看路由缓存中是否存在另外一条到达该目的节点的路由，如果 是则使用新的路由进行分组的发送；否则，发起一次新的路由发现过程以发现到 达该目的节点的新的路由。 2 2 3 3a o d v a o d v ( a d h o co 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 ) 是c h a r l e se p e r k i n s 等人提出的一种典型的按需路由协议。a o d v 借鉴了d s d v 的路由维护机制同时 参考了d s r 的路由发现过程，是两者相结合的产物。若干仿真结果表明 2 ，a o d v 的性能在大多数场景中与d s r 性能不相上下而强于其它已有的路由协议，是一种 性能相当不错的a dh o c 按需路由协议。 第二章a dh o c 路由协议简介 每一个使用a o d v 路由协议的节点都维护一个路由表，其中包含了所有正 在进行通信的路由。路由表中的每条路由记录包含如下的信息：目的节点地址、 目的节点序列号、路由下一跳和到达目的节点的路由跳数。另外，与每一条路由 记录相关联的还有一个用束表明路由有效期的参数即路由生存期。如果在路出生 存期结束时该路由仍然没有被更新过而且也没有被使用过，则将该路由从路由表 中删除。与d s d v 类似，每个节点维护自己的节点序列号。与d s r 中的路由请 求i d 类似，a o d v 使用一个叫做广播标识b i d 的计数器。b i d 和源节点地址的 组合用来唯一标识一个路由请求