（系统分析与集成专业论文）ad+hoc网络的建模与性能分析.pdf

2 0 0 5 年上海大学硕士学位论文 a dh o c 网络是一种特殊的无线网络，它不需要任何基础设施和集中管 理设备的支撑，具有高度动态变化的拓扑结构网络中各节点可任意移动， 兼备路由器和终端两种功能节点问往往通过中间节点的多跳转发完成通 信，每个节点必须支持一个路由协议以便发现与其它节点通信的路由 泛洪距离是评价a dh o c 网络性能的重要参数之一，它不仅与路由选择 的延迟和平均耗费有关，而且也与路由的稳定性和可靠性关系密切本文 以d s r 协议为基础，针对路由发现和路由维护两个阶段，分别建立空间复 用的随机图模型和马氏模型，着重分析泛洪距离这一重要网络性能参数 主要工作如下t 引入空间复用的机制在一般的a dh o c 网络中，由于许多节点可能不 在相互的传送半径之内，因此这些节点能够同时发送信息而不相互干扰， 这就是空间复用情形这一机制的引入大大缩短了泛洪距离，提高了路由 选择效率 考虑路由请求分组带有步跳限制在路由发现过程中，d s r 协议限制 了泛洪过程中路由请求分组的最大步跳数，以此来控制路由请求分组的延 展，避免多余路由请求分组备份的产生，有效利用路由缓存器 考虑每次泛洪过程都有时间限制在实际情形中，泛洪过程不可能无限 制地进行下去，d s r 协议规定了每次路由发现泛洪过程所用时间的上界 这一限制在一定程度上减少了路由发现的延迟时间，减轻了网络负荷，加 快了有效路由的建立 从节点的相对距离变化入手，并与时间紧密联系起来，使之能用生灭过 程来描述，建立了a dh o c 网络的马氏模型，方便了路由维护过程的研究， 并为a dh o c 网络性能参数的研究开辟了一条可行途径 采取定量的分析方法，明确给出泛洪距离的条件期望，条件概率母函 数以及路由回复平均次数等一些重要参数的解析公式；并比较空间复用和 无空间复用的差别，证明在泛洪距离的意义下，前者的路由寻路效率优于 后者 本文得到的一系列结果不仅对a dh o c 网络路由协议的评价和优化具 2 0 0 5 年上海大学硕士学位论文i i 有理论上的指导意义，而且为设计更有效的路由算法提供了新的思路 关键词：a dh o c 网络，路由协议，空间复用，随机图模型，马氏模型，生 灭过程，泛洪距离 2 0 0 5 年上海大学硕士学位论文i i i a b s t r a c t am o b i l ea dh o en e t w o r ki sak i n do fs p e c i a lw i r e l e s sn e t w o r k i td o e s n t n e e dt h ed 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 rc e n t r a | i z e da d m i n i s t r a t i o n ， a n dh a st h eh i g hr a t eo ft o p o l o g i c a lc h a n g e s i ns u c han e t w o r k ，e a c hm o b i l e n o d ec a nm o v er a n d o m l y ，a n do p e r a t e sn o to n l y ah o s tb u ta l s o ar o u t e r ， f o r w a r d i n gp a c k e t sf o ro t h e rm o b i l en o d e si nt h en e t w o r kt h a tm a yn o tb ei n d i r e c tw i r e l e s st r a n s m i s s i o nr a n g eo fe a c ho t h e r e a c hn o d ep a r t i c i p a t e si na n a dh o cr o u t i n gp r o t o c o lt h a t a l l o w si tt od i s c o v e rm u l t i h o pp a t h st h r o u g ht h e n e t w o r kt oa n yo t h e rn o d e t h ef l o o d i n gd i s t a n c ei so n eo ft h em o s ti m p o r t a n tp e r f o r m a n c ep a r a m e t e r s o fam o b i l ea dh o cn e t w o r k w h i c hr e l a t e sn o to n l yt ot h ee f f i c i e n c yo far o u t e d i s c o v e r y , b u ta l s ot ot h es t a b i l i t ya n dr e l i a b i l i t yo far o u t e b a s e do nd s k ，w e a d o p tr e s p e c t i v e l yt h er a n d o mg r a p hm o d e lw i t hs p a t i a lr e u s ea n dm a r k o v i a n m o d e lf o rr 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 ，a a dm a i n l ya n a l y z et h ep a - r a m e t e ro ft h ef l o o d i n gd i s t a n c ei nt h i sp a p e r t h ed i s s e r t a t i o nm a i n l yc o v e r st h e w o r ka sf o f l o w s ： i n t r o d u c et h em e c h a n i s mo fs p a t i a lr e u s e i ng e n e r i ca dh o cn e t w o r k s ，s e v ， e r a ln o d e sc a ns i m u l t a n e o u s l yd e l i v e rp a c k e t sw i t h o u td i s t u r b a n c e ，b e c a u s et h e y m a yn o tb ei nd i r e c tw i r e l e s st r a n s m i s s i o nr a n g eo fe a c ho t h e r t h i sm e c h a n i s m s h o r t e n st h ef l o o o d i n gd i s t a n c et oag r e a te x t e n ta n di m p r o v e st h ee f f i c i e n c yo f r o u t i n g c o n s i d e rt h er o u t er e q u e s t sw i t hh o pl i m i t i no r d e rt oc o n t r o lt h es p r e a d o far o u t er e q u e s ta n da v o i dm a n yr e d u n d a n tc o p i e so ft h er o u t er e q u e s td u r i n g ar o u t ed i s c o v e r ya t t e m p t ，t h ea b i l i t yi sa d d e df o rt h ed s ri n i t i a t o ro ft h er o u t e r e q u e s tt os p e c i f yi nt h er e q u e s tp a c k e tt h em a x i m u mn u m b e ro fh o p so v e rw h i c h t h ep a c k e tm a yb ep r o p a g a t e d c o n s i d e rt h et i m el i m i to f e a z hf l o o d i a g i nf a c t ，t h el a t e n c yt i m ef o rar o u t e d i s c o v e r yc a nb eu pb o u n d e db yl e t t i n g ap e r i o df o rt h er o u t ed i s c o v e r yi ne a c h a t t e m p tb es h o r tt i m e t h i sl i m i tr e d u c e st h ed e l a yo f t h er o u t ed i s c o v e r y ，l i g h t e n s 2 0 0 5 年上海大学硕士学位论文i v t h eb u r d e no ft h en e t w o r ka n dq u i c k e n st h ee f f i c i e n c yo ft h er o u t ed i s c o v e r y c o n s i d e r i n gh i g h l yc h a n g i n gw i t ht i m eo ft h et o p o l o g y , w em o d e lam o b i l e a dh o en e t w o r ks ot h a tt h el e n g t ho fe a c hl i n ki nt h en e t w o r ki sc o n s i d e r e da sa b i r t h d e a t hp r o c e s s t h i sc o n v e n i e n c e st h es t u d yo ft h er o u t em a i n t e n a n c ea n d p r o v i d e saf e a s i b l ea p p r o c hf o rt h ep e r f o r m a n c er e s e a r c ho ft h em o b i l ea dh o c n e t w o r k a d o p tq u a n t i t a t i v ea n da n a l y t i c a lm e t h o d w eg i v et h ea n a l y t i c a lf o r m u l a s f o rs o m ei m p o r t a n tp a r a m e t e r ss u c h “t h ec o n d i t i o n a la v e r a g ef l o o o d i n gd i s - t a n c e ，i t sc o n d i t i o n a lp r o b a b i l i t yg e n e r a t i n gf u n c t i o n ，t h ea v e r a g et i m e so fr o u t e r e c o v e r y ，e t c f u r t h e r m o r e ，w ec o m p a r et h er e s u l t sf o rt h em o d e la l l o w i n gs p a - t i a lr e u s ew i t ht h o s ef o rt h em o d e lw i t hn os p a t i a lr e u s e ，a n dp r o v et h ef o r m e r s u p e r i o rt ot h el a t e rf o rt h ef l o o d i n gd i s t a n c e t h er e s u l t so b t a i n e di nt h i sd i s s e r t a t i o np r o v i d en o to n l yg u i d i n gm e a n i n g i nt h e o r e t i c a ls t u d i e si na s s e s s m e n ta n do p t i m i z a t i o no fa dh e cn e t w o r k s ，b u ta l s o n e wi d e a si nt h ed e s i g no fm o r ee f f e c t i v er o u t e k e yw o r d s ：m o b i l ea dh o en e t w o r k s ，r o u t i n gp r o t o c o l 8 ，p e r f o r m a n c ea n a l y s i s ，s p a t i a lr e u s e ，r a n d o mg r a p hm o d e l s ，m a r k o vm o d e l s ，b i r t h - d e a t hp r o - c e s s ，f l o o d i n gd i s t a n c e 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：彝送盎。日期2 ：2 虹。：丝 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 第一章前言 近年来，便携式计算机在便携性、移动性、内存容量和磁盘存储容量等性能上 不断改进和提高，并配备了大容量磁盘、高分辨率彩显、指针设备和无线网络适配 器等，得到了广泛应用便携式计算机的主要特点是采用电池提供能量，没有导线 的约束，用户可以自由移动无绳计算机的快速发展，引发了移动用户信息共享的 自然需求目前，移动主机之间的通信大多是通过已有网络基础设施来实现的然 而，人们时常需要在不能利用或不便利用已有设施的情况下通信例如，当发生地 震或洪水等自然灾害时。需要快速调配援救人员；当进行科学考察、探险时，需要 通信联络；在战场上，需要实现动态过程中的协同通信等因此，人们提出了一种 不需要固定基站支撑，由一组带有无线网络接口的移动主机组成，组构和撤出十分 灵活的无线网络，a dh o c 网络 a dh o c 网络的研究始于2 0 世纪7 0 年代美国国防高级计划局( d a r p a ：d e f e n s e a 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 ) 的研究项目一分组无线网络作为一种新型无线 移动网络，a dh o c 网络不需要任何已建网络设施的支撑，具有广阔的应用前景 1 1 a dh o e 网络的特点 a dh o c 网络主要用于媒体会议、抢险、救灾、探险、军事行动、传感网络等 网络中各个主机的地位平等，兼备终端和路由器两种功能由于无线电波的能量限 制和频道利用率等问题，移动主机之间的通信往往通过若干中介移动主机构成一条 多跳转发路径来完成与传统的有线固定网络和普通的无线网络相比，a dh o e 隅 络具有以下特点( 【1 ，2 ，3 ，4 】) ： ( 1 ) 无中心；a dh o c 网络没有集中的控制中心，所有节点地位平等，是一个对 等式网络节点可以随时加入或离开网络，任何节点的故障不会影响整个网络的运 行，具有很强的抗毁性 ( 2 ) 网络的自组性一 a dh o e 网络的布设或展开无需任何预设的网络设施节点 通过分层协议和分布式算法协调各自的行为，可以在任意时刻、任意地点快速自动 地构建一个移动通信网络 ( 3 ) 动态变化的网络拓扑结构：a dh o e 网络是一个动态的网络网络节点的移 动具有很大的随机性，加上无线发射装置发送功率的变化、无线信道间的互相干扰 2 0 0 5 年上海大学硕士学位论文2 以及地形等综合因素的影响，网络拓扑结构可能随时发生变化 ( 4 ) 多跳路由：当节点要与其传输覆盖范围之外的节点进行通信时，需要中间 节点的多跳转发与固定节点的多跳不同，a dh o c 网络中的多跳路由是由普通的 网络节点完成，而不是由专用的路由设备( 如路由器) 完成 ( 5 ) 有限的传输带宽： a dh o c 网络采用无线传输技术作为通信手段，而无线 信道本身所能提供的网络带宽相对较低，再加上竞争共享无线信道带来的信号冲 突、衰减及干扰等多种因索的影响，移动终端可得到的有效带宽将远小于理论上的 最大带宽 ( 6 ) 移动终端的局限性： a dh o c 网络中的用户终端( 如笔记本和手持终端，车 载计算机等) 虽然具有灵巧、便携的特点，但它们主要靠电池供电，并且c p u 性能 较低，内存较小 1 2 a dh o c 网络路由协议性能评价的研究 近十几年来，a dh o c 网络的研究形成了热点，经历了一个快速发展阶段a d h o c 网络不同于传统有线固定网和普通无线网络的特点使得传统的路由协议已不能 满足a dh o c 网络的要求，必须改进已有的路由算法或针对a dh o c 网络提出新的 协议设计方案在上世纪九十年代前期和中期，人们的注意力主要放在路由协议的 研究上，大致形成了先应式( p r o a c t i v e ) 和反应式( r e a c t i v e ) 两大协议簇( 【5 ，6 ，7 1 ) 随着路由协议研究的深入，关于路由协议的性能比较和评价的研究也日益凸显 出重要性由于a dh o c 网络具有节点移动、带宽受限和能源约束等诸多特性，使 得a dh o c 网络比有线固定网络更为复杂，因此对a dh o c 网络性能进行理论建模 分析变得非常困难 早期的性能比较研究大多采用了对特定网络情景进行模拟试验的研究方法 1 9 9 8 年，b r o c h 等人( 【8 】) 对网络模拟器n s 一2 进行了扩充，使扩充詹的模拟器对 m a c 层和物理层提供行为支持，并适合i e e e8 0 2 1 1 无线网络标准，这种新的仿真 环境为a dh o c 网络协议和其它无线网络协议的评价和应用提供了一个强有力的工 具；他们通过运用新的仿真环境，详细分析比较了d s r 、a o d v 、d s d v 和t o r a 四个a dh o c 网络路由协议的性能 1 9 9 9 年，j o h a n s s o n 等人( 【9 】) 在文【8 】的启发 下，以随机性节点运动扩充了模拟环境，并引入新的移动性度量和三种真实的网络 环境，通过数据包延迟，网络吞吐量等比较了d s d v ，a o d v ，d s r 三个a dh o c 网 2 0 0 5 年上海大学硕士学位论文 3 络路由协议的性能 2 0 0 1 年，p e r k i n s 等人( 【1 0 】) 以文 8 】中扩充的n 8 2 模拟器 为基础，对无线局域网、路由协议及网络通信量和移动性等做了详细模拟，专门对 比研究两个最为典型的反应式路由协议td s r 和a o d v 的性能，得出协议的性能 依赖于协议机制另外，还有如文献f 1 1 ，1 2 】所做的工作等 随着模拟实验研究的开展，人们也开始了理论研究j a c q u e t 和l a o u i t i 在这方 面做了开创性的工作，他们分析了小区域环境( 各节点的有效传输范围能够覆盖其 它所有节点) 下稠密a dh o e 网络的性能( 【1 3 】) ，基于i e e e8 0 2 1 1 无线网络标准和信 号衰减模型，对a dh o c 网络作了合理假设，建立了随机图模型，分析比较反应式 路由协议d s r 和先应式路由协议o l s r 的一些重要性能参数并给出了一些参数的 解析公式 a r o n 等人( 【1 4 】) 在反应式路由协议错误恢复机制的比较与分析方面也 作了非常重要的工作最近，方建超、王汉兴等( 【1 5 】) 建立了a dh o c 网络的离散时 间马氏链模型，给出了模型的平稳分布，分析了节点相邻的概率、节点的平均邻居 数、平均泛洪距离等网络重要参数，并给出了转移概率矩阵的一个具体定义方法； 他们还分析了小区域a dh o c 网络路由发现过程的特点( 1 1 6 1 ) ，构建了s m a h f 描述性模型，论述了s m a h f 模拟器的设计和实现，模拟并讨论了平均泛洪距离 等网络参数与n ，p ( 网络规模、连通概率) 之间的关系。并将实验数据与理论结果作 了比较 1 3 本文工作概要 j a c q u e t 和l a o u i t i 建立了a dh o c 网络的随机图模型( 【1 3 】) ，以d s r 协议为基 础，给出了无限泛洪时泛洪距离的期望和概率母函数的极限结果然而，他们未考 虑空间复用和路由请求分组带有步跳限制的情形 本文在文【1 5 】和【1 6 】所做工作的启发下，研究空间复用情况下，反应式路由协 议的典型代表一一d s r 协议的性能评价，着重分析泛洪距离这一重要的网络性能 参数所谓空间复用是指t 在一般的a dh o c 网络中，由于许多节点可能不在相互 的传送半径之内，因此这些节点能够同时发送信息而不相互干扰 在路由发现过程中，为了限制路由建立的延迟，控制路由请求分组的传播和避 免产生多余的请求分组备份，d s r 协议规定了每次泛洪所用时间的上界，泛洪过 程中路由请求分组的最大步跳数，以及对同一个目的节点路由尝试的最大次数因 此，对a dh o c 网络我们考虑请求分组带有步跳限制的空间复用随机图模型，在两 2 0 0 5 年上海大学硕士学位论文4 节点能建立链接的条件下，分析路由协议性能评价的重要参数之泛洪距离， 得到其条件期望和条件概率母函数的数学公式；引入路由r 一时有效的概念，得到 路由r 一时有效( 或对称) 的条件概率和发现一条有效路由所需的平均时闻；比较空 间复用和无空间复用的差别，证明在泛洪距离的意义下，前者的路由寻路效率优于 后者 另外，考虑到网络拓扑改变与时间的紧密联系，我们从节点间的相对距离变化 入手，并与时间紧密联系起来，用马氏生灭过程来描述a dh o c 网络，建立请求分 组带有步跳限制的空间复用马氏模型；引入链边有效的概念，推导链边有效概率和 有效平均时间的解析公式，并在此基础上着重分析d s r 协议路由维护过程的一些 重要性能参数，如链边有效的平均时间和路由恢复的平均次数等 本文的组织如下t 第一章为前言，主要介绍a dh o c 网络的特点，路由协议性 能评价的研究以及本文概要第二章详细介绍a dh o c 网络几个重要的路由选择协 议，并对反应式路由协议和先应式路由协议进行了比较第三章描述a dh o c 网络 的随机图模型，分析d s r 协议路由发现过程的一些重要性能参数，给出泛洪距离 条件期望和条件概率母函数的解析公式，比较空间复用和无空间复用的差别第四 章介绍a dh o c 网络的马氏模型，着重阐述该模型下d s r 协议路由维护的性能分 析，给出链边有效概率、有效平均时间和路由恢复平均次数的解析公式第五章是 结论，主要是对本文工作的总结和对未来研究的展望 第二章a dh o c 网络的路由协议 a dh o c 网络中，节点可以随意移动，网络结构的动态性非常强，传统的路由算 法在这种环境下如果根据网络拓扑进行快速反应。将会使路由变得非常不稳定，同 时会产生大量的路由更新信息，极大地增加网络负担但是，如果路由算法不根据 拓扑变化进行快速反应则会出现路由错误等问题，影响数据转发因此传统的路 由算法已不能满足a dh o c 网络的要求，必须改进已有的路由算法或提出新的路由 协议设计方案根据a dh o c 网络的特点其路由协议应满足以下条件。1 ) 对拓扑 变化具有快速反应能力，并且要避免路由环路的发生；2 ) 高效地利用带宽资源，尽 可能压缩开销；3 ) 尽可能缩短发射时间和减少发射数据量，以节约能源；4 ) 维护 闭络拓扑的链接 1 9 9 7 年宽带移动无线网络研究的主要组织i n t e r n e t 工程任务组( i e t f ) 成立了 一个专门的移动工作组( m a n e t ：m o b i ! ea d - h o cn e t w o r k i n g ) ，对a dh o c 网络的路由 算法进行研究目前，针对a di t o c 网络已经提出了许多基于不同策略的路由算法 ( f 1 7 ，1 8 ，1 9 、2 0 ，2 1 ，2 2 ，2 3 ，2 4 ，2 5 ，2 6 】) 根据对网络拓扑变化的不同反应，大致可分为 先应式路由协议和反应式路由协议两大类本章主要介绍a dh o c 网络几个重要的 路由协议 2 1 先应式路由协议 先应式路出协议通常是用表驱动的f t a b l e - d r i v e n ) 这类协议中，网络虑每个节点 都保持一张或多张到其它节点相对稳定的最新路由表当网络拓扑发生变化时，移动 节点将把相关的路由信息都传播给它的邻近节点这些路由更新信息将触发其它节 点重新计算自己的路由表，并把相关信息进一步传播出去，从而改变网络拓扑映象 ( 路由表) - 采用不同数量和内容的路由表以及不同的传播策略。形成了各种不同的路 由协议典型的先应式路由协议包括目的序号距离向量路由协议( d s d v ：d e s t k m t l o n - s e q u e n c e dd 1 s t 8 】1 c v e c t 。rr o u t i n g ) ( 1 7 ) 和优化链路状态路由协议( o l s r ：o p t i m i z e d l i n ks t a t er o u t i n g ) ( f 1 8 ) 1 _ d s d v 协议 d s d v 协议基于传统的距离向量路由机制，同时也被稀为消除路由环路的b e l l m a n - f o r d 路由算法在d s d v 协议中，每个节点都维护一张路由表。其中记录了该节点 f u r d 路由算法在d s d v 协议中，每个节点都维护一张路由表其中记录了该节点 第二章a dh o c 网络的路由协议 a dh o c 网络中，节点可以随意移动，网络结构的动态性非常强，传统的路由算 法在这种环境下如果根据网络拓扑进行快速反应，将会使路由变得非常不稳定，同 时会产生大量的路由更新信息，极大地增加网络负担但是，如果路由算法不根据 拓扑变化进行快速反应，则会出现路由错误等问题，影响数据转发因此传统的路 由算法已不能满足a dh o c 网络的要求，必须改进已有的路由算法或提出新的路由 协议设计方案根据a dh o c 网络的特点其路由协议应满足以下条件1 ) 对拓扑 变化具有快速反应能力，并且要避免路由环路的发生；2 ) 高效地利用带宽资源，尽 可能压缩开销；3 ) 尽可能缩短发射时间和减少发射数据量，以节约能源；4 ) 维护 网络拓扑的链接 1 9 9 7 年宽带移动无线网络研究的主要组织i n t e r n e t 工程任务组( i e t f ) 成立了 一个专门的移动工作组( m a n e t ：m o b i l ea d h o cn e t w o r k i n g ) ，对a dh o c 网络的路由 算法进行研究目前，针对a dh o c 网络已经提出了许多基于不同策略的路由算法 ( 1 7 ，1 8 ，1 9 ，2 0 ，2 1 ，2 2 ，2 3 ，2 4 ，2 5 ，2 6 】) ，根据对网络拓扑变化的不同反应，大致可分为 先应式路由协议和反应式路由协议两大类本章主要介绍a dh o c 网络几个重要的 路由协议 2 1 先应式路由协议 先应式路由协议通常是用表驱动的( t a b l e - d r i v e n ) 这类协议中，网络内每个节点 都保持一张或多张到其它节点相对稳定的最新路由表当网络拓扑发生变化时，移动 节点将把相关的路由信息都传播给它的邻近节点这些路由更新信息将触发其它节 点重新计算自己的路由表，并把相关信息进一步传播出去，从而改变网络拓扑映象 ( 路由表) 采用不同数量和内容的路由表以及不同的传播策略，形成了各种不同的路 由协议典型的先应式路由协议包括目的序号距离向量路由协议( 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 rl ：i d u t i n g ) ( 1 7 ) 和优化链路状态路由协议( o l s r ：o p t i m i z e d l i n ks t a t er o u t i n g ) ( 1 s ) 1 _ d s d v 协议 d s d v 协议基于传统的距离向量路由机制，同时也被称为消除路由环路的b e l l m a n f o r d 路由算法在d s d v 协议中，每个节点都维护一张路由表，其中记录了该节点 5 2 0 0 5 年上海大学硕士学位论文6 可到达的所有其它网络节点以及到达这些节点的跳数每个节点从它的邻近节点获 得路由信息，然后根据这些路由信息计算出到网络中其它节点的最短路径当计算 出一个新的路由表时，节点把这个新的路由表广播给它所有的邻近节点这样可能 促使它的邻近节点重新计算路由表，并进一步把路由的变化传播出去，直到最后整 个网络的路由表变得稳定 路由表中的记录由目的节点指定的顺序号标识，该顺序号隐藏时间顺序信息以 区分新旧路由，并由此避免环路产生为了降低网络流量，将更新信息分为两类t 一类是“完整”信息，包括路由表中所有信息；另一类称为“增量”信息，只包含 自上一次广播“完整”信息之后的更新内容，“增量”信息比“完整”信息的内容 少得多通过这种方法，可以从一定程度上减少路由更新信息对网络造成的负荷 d s d v 协议使用目的节点顺序号来避免因使用过时路由信息而产生的无效路 由，同时通过使用触发性路由更新，在网络路由状态改变时收敛较快，但周期性的 广播分组增大了网络开销 2 o l s r 协议 o l s r 协议是由i e t fm a n e t ( m o b i l ea dh o cn e t w o r k ) 工作组提出的一种优化 的链路状态路由协议，节点之间需要周期性地交换各种控制信息，通过分布式计算 来更新和建立自己的网络拓扑图被邻节点选为多点中继站( m u l t i p o i n tr e l a y , m p r ) 的节点需要周期性地向网络广播控制信息，控制信息中包含了把它选为m p r 的那 些节点的信息( 称为m p rs e l e c t o r ) ，以告诉网络中其它节点与这些节点直接相连 只有m p r 点被用作路由选择节点，非m p r 节点不参与路由计算 o l s r 还利用 m p r 节点有效地广播控制信息，非m p r 节点不需要转发控制信息这样可能会导 致通信负荷过分集中在m p r 节点上 2 2 反应式路由协议 反应式路由协议又称为随选型路由协议，是针对a dh o c 网络的特点而专门 提出来的与先应式路由协议不同，该协议并不事先维持网络拓扑的全局映像， 仅当节点需要时才l 临时建立路由反应式路由协议一般包括路由发现和路由维护 两个重要过程当源节点需要向目的节点发送数据时，首先查询其路由表，如果不 存在所需路由，则启动一个路由发现程序，通常是泛洪( f l o o d i n g ) 一个路由请求分 组r r e q ( r o u t er e q u e s t ) ，当合适的路由被找到，目的节点返回一个路由应答分组 2 0 0 5 年上海大学硕士学位论文7 r r e p ( r o u t er e p l y ) ，或所有可能的路由排列都已经检查过，该过程就终止路由 建立后，由某种路由维护程序进行维护，直到该路由不再需要为止 1 d s r 协议 d s r ( d y n a m i cs o u r c er o u t i n g ) 协议( 1 9 ，2 0 1 ) 基于源路由算法，能够快速适应网 络拓扑的变化，是反应式路由协议的典型代表其数据分组头部包含了完整的路由 信息，中间节点不需要维护路由信息 d s r 协议包括两个重要阶段：路由发现和路由维护当一个节点需要发送数据 时，首先检查它的路由缓冲器，如果没有发现相应的路由信息，就要启动路由发现 机制，广播路由请求分组当一个节点收到一个路由请求分组时，首先检查源地址 和标识号是否已经收到过，如果收到过，丢弃这个分组如果目的节点是自己或缓 冲器中有相应路由，复制路由记录表到路由应答分组r r e p 中，并反向发送到源节 点否则，将自己的地址加入到路由记录表，重新广播这个路由请求分组，直至源 节点收到目的节点的路由应答分组，将路由信息存入路由缓冲器，路由发现过程结 束 在路由维护中，d s r 利用两种类型的分组进行路由保持：路由差错分组r e r r 和路由确认a c k 中间节点如果发现路由表中显示的下一跳节点链路层不可达，就 向源节点发送一个r e r r 源节点从路由缓冲条目中删除所有不可到达的链路( 这 条路径的中间节点也利用这个信息更新路由缓冲器) ，并将重新启动路由发现过程 a c k 分组用来确认正确的路由条目。 d s r 协议的优点：节点仅需要维护与之通信的节点间的路由。减少了协议开 销；使用路由缓冲技术减少了路由发现的耗费；一次路由发现过程可能会产生多条 到目的节点的路由缺点：每个数据报文的头部都需要携带路由信息，数据分组的 额外开销较大；路由请求消息采用泛洪方式，相邻节点路由请求分组可能发生传播 冲突并可能产生重复的广播；由于缓存，过期的路由会影响路由选择的准确性 2 a o d v 协议 a o d v 协议( 【2 l 】) 是d s d v 算法的改进，使用按需驱动的机制来减少路由维护 的开销，非活动路径上的主机不稿要维护和交换任何控制信息为了找到通往目的 节点的路由，源节点将广播一个路由请求分组r r e q 如果邻节点不是目的节点也 不具有到目的节点的路由时，它将重新广播这个r r e q 分组即使邻节点具有到目 的节点的路由，但相应路由信息的序列号小于r r e q 分组中携带的序列号时，也将 重新广播r r e q 如果邻节点是目的节点或者是中间节点但具有的路由信息的序列 2 0 0 5 年上海大学硕士学位论文8 号不小于r r e q 分组中的序列号，那么邻节点就可以沿着相反的路径给源节点发 送一个包含有本机目的节点序列号的r r e p 分组 节点将丢弃重复收到的路由请求分组，分组中的序列号用来防止路由环路，并 判断中间节点是否响应了相应的路由请求当节点转发请求分组时，它将上游节点 的标志i d 录入路由表，从而建立一条从目的节点到源节点的反向路由当源节点 移动时，它会重新发起路由发现算法；如果中间节点移动，其邻节点会发现链路失 效并向其上游节点发送链路失效消息且一直传到源节点，而后源节点根据情况重新 发起路由发现过程 3 t o r a 协议 t o r a ( t e m p o r a l l yo r d e r e dr o u t i n ga l g o r i t h m ) ( 2 2 ) 是一个基于链路反转方法的 自适应分布式路由算法，主要用于高速动态的多跳无线网络作为一个由源端发起 的按需路由协议，它可以找到从源节点到一个目的节点的多条路由t o r a 的主要 特点是当拓扑发生改变时，控制消息只在拓扑发生改变的局部范围传播，节点只需 维护相邻节点的路由信息协议由三部分构成；路由产生、路由维护和路由删除 初始化时，目的节点的高度( 即传播序列号) 设置为0 ；然后由源端广播一个含有 目的节点i d 的q r y 分组，一个高度不为0 的节点响应一个u d p 分组；收到u d p 分组的节点的高度将比产生该u d p 分组的高度大1 ，并且具有较大高度值的节点 被规定为上游节点通过这种方式能够建立一个从源节点到目的节点的有向无环路 图( d a g ) 当节点移动时，路由需要重建在路由删除阶段，t o r a 通过广播一个 c l r 分组来删除无效路由t o r a 存在的问题是：当多个节点同时进行选路和删 除路由时会产生路由震荡现象 4 a b r 协议 a b r ( a s s o c i a t i v i t y - b a s e dr o u t i n g ) ( 2 3 ) 采用了联合稳定度的路由机制联合稳 定度表征了节点之间在时空上连接的稳定程度，移动性强则稳定度低，反之则稳定 度高a r b 协议由三个阶段组成，路由发现、路由重建和路由拆除 a r b 协议 结合广播和点到点路由选择算法，并采用面向连接的分组传送方式它以联合稳定 度作为路由选择度量，因而获得生存时间最长的路由由于重构次数少，a r b 协 议的吞吐量较大，且支持q o s a r b 协议需要在足够小的时间间隔内周期地标志路 由，由此会带来额外的带宽和功率开销 5 s s a 协议 s s a ( s i g n a ls t a b i l i t y b a s e da d a p t i v er o u t i n g ) ( 2 4 1 ) 是基于信号强度的随选型自适 2 0 0 5 年上海大学硕士学位论文9 应路由协议该协议的特点是选择连接性最强的路由 s s a 由两个互相合作的协 议构成：动态路由协议( d r p ) 和转发协议( f p ) d r p 负责维护信号稳定度表( s s t ) 和路由表( r t ) ，且记录邻节点的信号强度信号强度通过接受链路层发出的周期性 信标获得f p 进行查找路由表并转发数据包到下一条节点 s s a 不支持单向链 路 2 3 先应式与反应式路由协议的比较 先应式路由协议基于路由表机制，更新间隔对性能的影响很大间隔太大，协议 将不能快速反应拓扑结构的变化；间隔太小，网络则可能因为充满路由表更薪消息 而阻塞当网络中活动的源目通信对数太大时该类协议更有效，因为浪费的路由 开销相对减少反之利用率较低，每个节点到达其它任何节点的路由总是就绪的， 不管它是否确实需要，这将导致持续的路由信息传播，加重网络载荷，同时将增加 能量消耗，造成严重的局限性当网络规模和移动性增加( 超过一定的阈值) 时，大 部分先应式路由协议的方案将不可行，原因是仅用于保持与拓扑变化一致而需要传 送的路由更新消息将消耗大部分的网络容量和节点处理能力 反应式路由协议并不维护尚未需要的路由，且路由请求应答( r r e q r r e p ) 控制分组通常比先应式路由协议中用于路由表更新的控制数据分组要小，因此所产 生的控制信息比先应式协议少但是，由于在数据开始传输之前必须建立路由，因 此会产生路由建立延迟，这在先应式路由协议中没有 在网络负荷不太重、节点移动速度不太大的情况下，即使对于非常大型的网络， 反应式路由协议通常能显示出低路由信息荷载和低存储要求的优点但随着移动性 的增强，正在传输数据的路由可能会中断，需要再次调用路由发现过程在高度移 动性和重载荷( 有大量通信对) 的情况下，路由高速缓存会变得无效，路由控制流量 趋于快速增长( 【1 0 】) 在均匀流的情况下，对于1 0 0 个节点和4 0 个源节点的情况， d s r 和a o d v 产生的路由信息流量大于网络的实际吞吐量( 【9 ，l o 】) 总之，反应式路由协议更适合于a dh o c 网络，因为该类路由协议是专门针对 a dh o c 网络特点而设计的 第三章a dh o c 网络路由发现过程的建模与分析 泛洪是a dh o c 网络建立路由的重要手段【2 7 ，28 】反应式路由协议大都是通过 泛洪路由请求分组( r p m q ) 来实现路由发现的近年来，人们提出了多个基于泛洪 方法的路由协议，如d s r ，a o d v ，a b r ，s s a 等其中最具代表性的就是d s r 协 议，它通过泛洪路由请求分组( r r e q ) 来发现路由，然后将路由信息标记在每个数 据分组的分组头，以“源启动”的方式来递送信息 迄今为止，没有哪个路由协议能够在所有a dh o c 网络环境中都保持优良因 此，研究不同a dh o c 网络环境的网络特性是非常有意义的对于路由发现而言， 不同的a dh o c 环境，节点的数量及移动模式可能有很大差异。反映在泛洪寻路上 就是不同的寻路效率和不同的寻路延迟因此，泛洪距离是路由协议性能评价的重 要参数之一，它既与路由发现的延迟和平均耗费关系密切，也与路由的稳定性和可 靠性有关无限泛洪是指网络中所有节点都转发分组，即泛洪距离不受限制 j a c q u e t 和l a o u i t i 对a dh o c 网络的一种特殊情形一一小区域a dh o c 网络进行 了分析( 【1 3 】) ，建立了随机图模型，并且以d s r 协议为基础，给出了无限泛洪情况 下泛洪距离的期望和概率母函数的解析公式然而，他们未考虑空间复用和路由请 求分组带有步跳限制的情形 事实上，