（通信与信息系统专业论文）基于分组的移动ad+hoc网络混合路由协议研究.pdf

武汉理工大学硕士学位论文 摘要 战场通信一直以来都是被世界各军事强国所重视的一个领域，其中移动a d h o e 网络以其独有的特性从诞生初期就与军事应用结下了不解之缘，而路由技术 又是移动a dh o e 网络最为重要的技术之一。当前a dh o e 网络中的各种重要路 由协议主要基于表驱动路由策略、按需路由策略和混合路由策略。经过研究发 现，这些已有的路由协议在节点规模和数据流量较大的网络场景中会产生大量 的控制开销，进一步消耗有限的网络带宽资源，这将导致网络发生拥塞，数据 包可能被延迟甚至破丢弃，这必然会严重影响路由协议的性能和网络的服务的 质量。 针对战场的特殊应用环境，本文提出了一种采用固定组成员数分组，组与 组之间采用按需路由策略而组内节点采用表驱动路由策略的分层、多信道路由 协议一基于分组的混合路由协h g r ( h i e r a r c h i e a lg r o u pr o u t i n g ) 。h g r 协议主要 包括组的形成与维护和路由两大部分。h g r 协议采用了固定的分组方式，把a d h o e 网络中的所有节点划分为三类：高级指挥节点、组长节点和组员节点。网络 中有若干个组和若干个高级指挥节点，每个组有一个组长节点和多个组员节点。 组长节点和高级指挥节点之间可以直接进行通信，采用按需路由策略；组内节 点之间通信采用一跳的表驱动路由策略；组内节点需要与组外其它节点进行通 信时需由其所在组的组长节点负责转发。不同层采用不同的通信信道。这样做 一方面可以提高组内成员之间通信的效率，另一方面可以对传输的数据进行有 效地区分。 本文使用n s 2 软件对h g r 协议进行了仿真。对c b r 业务的仿真试验结果 表明，h g r 协议具有在组内部通信时通信效率高、通信实时性好，组与组之间 通信时稳定性好等特点，比较适合战场这一特殊、特定环境下的应用。 关键字：a dh o e 网络，混合路由，分组，战场通信，固定组成员数 武汉理工大学硕士学位论文 a b s t r ac t b a t t l e f i e l dc o m m u n i c a t i o n sh a sb e e nt h ew o r l d 。sm i l i t a r yp o w e r sa r ev a l u e db y a na r e ai nw h i c hm o b i l ea dh o cn e t w o r k s 、析mi t su n i q u ec h a r a c t e r i s t i c sf r o mt h e e a r l yb i r t ho ft h ei n d i s s o l u b l eb o n d 诵t l lt h em i l i t a r ya p p l i c a t i o n s ，a n dr o u t i n gf o r m o b i l ea dh o cn e t w o r ki st h em o s ti m p o r t a n tt e c h n o l o g i e s t h ec u r r e n ta dh o c n e t w o r kr o u t i n gp r o t o c o l si nav a r i e t yo fi m p o r t a n tr o u t i n gs t r a t e g yi sb a s e do n t a b l e - d r i v e n ，o n d e m a n dr o u t i n gs t r a t e g i e sa n dh y b r i dr o u t i n gs t r a t e g y a f t e rt h e s t u d yw ef o u n dt h a tt h e s ee x i s t i n gr o u t i n gp r o t o c o l sa n dd a t at r a f f i ci nt h en o d es i z e l a r g e rn e t w o r ks c e n a r i o sw i l lp r o d u c eal o to fc o n t r o lo v e r h e a d ，f u r t h e rc o n s u m p t i o n o fl i m i t e dn e t w o r kb a n d w i d t hr e s o u r c e s ，w h i c hw i l l l e a dt on e t w o r kc o n g e s t i o n , p a c k e t sm a yb ed e l a y e de v e nb r e a ka w a y ，w h i c hi sb o u n dt os e r i o u s l ya f f e c tt h e p e r f o r m a n c eo fr o u t i n gp r o t o c o l sa n dn e t w o r kq u a l i t yo f s e r v i c e s p e c i a la p p l i c a t i o n sf o rt h eb a t t l e f i e l d ，t h i sp a p e rp r o p o s e saf i x e dn u m b e ro f g r o u pm e m b e r sg r o u p ，b e t w e e nt h eg r o u p su s i n go n - d e m a n dr o u t i n gs t r a t e g yg r o u p n o d e s u s i n g h i e r a r c h i c a lt a b l e - d r i v e n r o u t i n gs t r a t e g y ，m u l t i c h a n n e lr o u t i n g p r o t o c o l s p a c k e t - b a s e dh y b r i dr o u t i n gp r o t o c o lh g r ( h i e r a r c h i c a lg r o u pr o u t i n g ) 。 h g r p r o t o c o li n c l u d i n gg r o u pf o r m a t i o na n dm a i n t e n a n c e ，a n dr o u t i n go f t w op a r t s h g rp r o t o c o lu s e saf i x e dg r o u p i n g ，t h ea dh o cn e t w o r ka l ln o d e sa r ed i v i d e di n t o t h r e ec a t e g o r i e s ：h i g h - l e v e lc o m m a n dn o d e s ，h e a dn o d e sa n dn o d em e m b e r s t h e r e a r es e v e r a ln e t w o r kg r o u p sa n dan u m b e ro fs e n i o rc o m m a n dn o d e s ，e a c hg r o u ph a sa l e a d e rn o d ea n dt h en o d en u m b e ro fm e m b e r s h e a do ft h es e n i o rc o m m a n dn o d e s a n db e t w e e nn o d e sc a nc o m m u n i c a t ed i r e c t l y ，o n - d e m a n dr o u t i n gs t r a t e g y ；g r o u p h o p sb e t w e e nn o d e sc o m m u n i c a t eu s i n gt h et a b l e - d r i v e nr o u t i n gs t r a t e g y ；g r o u p 、们t l l t h eg r o u p ，t h en o d en e e d st oc o m m u n i c a t e 谢t ho t h e rn o d e sr e q u i r e db yn o d ew h e r e t h el e a d e ro ft h et e a mr e s p o n s i b l ef o rf o r w a r d i n g d i f f e r e n tl a y e r su s i n gd i f f e r e n t c o m m u n i c a t i o nc h a n n e l s i ns od o i n g ，t h eg r o u pc a ni n c r e a s et h ee f f i c i e n c yo f c o m m u n i c a t i o nb e t w e e nm e m b e r so ft h eo t h e rd a t ac a nb et r a n s m i t t e de f f e c t i v e l y d i s t i n g u i s h 武汉理工大学硕士学位论文 w eu s et h en s 2s o t h ，a r eh g rp r o t o c o ls i m u l a t i o n t h ec b rb u s i n e s s s i m u l a t i o nr e s u l t ss h o wt h 她h g rp r o t o c o lt oc o m m u n i c a t e 谢t l lt h eg r o u po f i n t e r n a lc o m m u n i c a t i o ne f f i c i e n c y ，c o m m u n i c a t i o n , r e a l - t i m e ，c o m m u n i c a t i o n b e t w e e nt h eg r o u p sw h e nt h eg o o ds t a b i l i t y ，m o r es u i t a b l ef o rt h i sp a r t i c u l a rb a t t l e ， t h es p e c i f i ce n v i r o n m e n t k e yw o r d s ：a dh o en e t w o r k s ；h y b r i dr o u t i n g ；p a c k e t ；b a t t l e f i e l de o m m u n i c a t i o m ；f i x e d n u m b e ro fg r o u pm e m b e r s i i i 武汉理工大学硕士学位论文 1 1 引言 第1 章绪论 随着移动数字平台技术的不断发展，移动装置不仅体积越来越小、价格越 来越便宜、使用越来越方便、功能越来越强大，我们也逐步从“个人计算机时 代 过渡到了“随遇计算时代”。在随遇计算时代，一个用户能够随时随地根据 需要通过各种数字平台访问所需要的各种信息。而无线网络就为这种特性提供 了最简单、最便捷的实现方法。 在移动装置的所有应用和服务中 5 , 1 0 1 ，网络连接和相应的数据服务毫无疑问 的是移动用户最迫切需要的服务。当前，无线装置之间的大多数连接通过固定 基础设施服务提供方或者专用网络来实现。例如，两部蜂窝手持电话之间通过 蜂窝网络中的b s c 和m s c 来建立连接，手提电脑则是通过无线访问点连接至 互联网络。但是固定基础设施的建立可能会花费大量的时间和很高的代价；例 如，在地震、海啸等自然灾害发生，固定通信设施被摧毁后，救灾人员在进入 灾区抢险需要进行通信和网络连接时，如何快速、协调的进行网络组建就成为 了一种挑战。 军事作战的动态性也意味着战场军事通信不能依靠访问固定的、预先建立 好的通信基础设施。 这些问题首先涉及移动问题；第二涉及不需要基础设施支持的问题；第三 涉及动态自组织组网问题；第四涉及网络必须能够快速展开的问题。为此，研 究人员提出了不需要基础设施支持的移动a dh o c 解决方案。即通过自动配置使 移动装置互相连接，建立既灵活功能又强大的移动a dh o e 网络( m o b i l e a dh o e n e t w o r k ，m a n e t ) 。 1 2 国内外研究现状 国际上，1 9 9 6 年i e t f 成立了m a n e t 工作组阳1 ，致力于m a n e t 路由协议 的研究工作，国外的研究人 员基于各种不周的角度提出了许多路由协议，其中有些提交到m a n e t 工 武汉理工大学硕士学位论文 作组成为r f c 草案，这些路由协议可归结为表驱动路由协议、按需路由协议和 混合路由协议三种形式。1 9 9 8 年以来，虽然国内外研究人员对a dh o c 网络网络 层的路由协议研究已取得较大的进展，但是对于a dh o c 网络的安全路由方面的 研究还较为缓慢，并且安全路由协议的i e t f 标准也未见公布。 目前对于安全路由的研究主要是在基本a dh o c 路由协议上进行的，提出的 主要安全路由协议有s e a d ( s e c u r ee f i c i e n ta dh o cd i s t a n c ev e c t o rr o u t i n g ) 、 a r a n ( a u t h e n t i c a t e dr o u t i n gf o ra dh o cn e t w o r k s ) 、s a r ( s e c u r i t ya w a r ea dh o c r o u t i n g ) 、s a d s r ( s e c u r i t y - a w a r ea d a p t i v ed s r ) 、s a o d v ( s e c u r ea o d v ) 等。还 有的学者致力于应用i p s e c ( i ps e c u r i t y ) 来解决a dh o c 网络的安全路由。近年来， 国内不少院校、研究所、实验室也加大了对a dh o c 网络安全路由的研究，并在 某些方面取得了一定的研究成果。 c a r n e g i em e l l o n 大学的m o n a r c h 小组也在进行无线a dh o c 网络的研究，并 通过n s 2 进行了一系列的仿真和测试。另外，m o n a r c h 小组还在n s 2 模拟平台 基础上进行了扩展，并支持四种主要无线a dh o c 网络环境下的协议设计、执行， 性能评估等工作。 中国科技大学信息处理中心和信息网络实验室，主要研究无线a dh o c 网络 在民事和军事领域中的网络应用，如战术互联网的网络应用等，目前研究主要 集中在网络层协议及安全，同时也研究无线a dh o c 网络节能、q o s 、i p 地址的 动态分配、网络监视、节点移动性管理、抗毁性管理和无线a dh o c 网络的安全 管理等。 t e m i n o d e 组织从2 0 0 0 年起致力于t e m i n o d e 项目的研究。该项目旨在研究 和模拟大规模、自组织的无线移动a dh o c 网络，其研究领域包括从物理层到应 用层的所有层面，以及层间的相互作用，如路由算法、移动性管理、不使用g p s 定位、节点相互协作的激励机制和安全策略等。 加州大学洛杉矶分校m a r i o g e r l a 教授所领导的“无线自适应移动性实验室 ( t h ew a m ( w i r e l e s sa d a p t i v e ，m o b i l i t y ) l a b ，h t t p ：w w w c s u c l a e d u n r l w i r e l e s s ) 。研究方向包括a dh o c 网络路由协议、多播协议、多跳网络q o s 、m a c 协 议、功率控制、蓝牙网络等。 康奈尔大学z y g m u n t j h a s s 教授所领导的“无线网络实验室 ( w i r e l e s s n e t w o r k sl a b o r a t o r y ，h t t p ：w n l g e e c o m e l l e d u ) 。研究方向包括a dh o c 网络重 构、m a c 协议、路由协议、网络安全等。 2 武汉理工大学硕士学位论文 伊利诺大学u r b a n a - c h a m p a i g n 分校n i t i nv a i d y a 教授( h t t p ：w w w c r h c u i u c e d u n h v ) 所领导的a dh o c 网络研究小组( 现在伊利诺大学u r b a n a c h a m p a i g n 分校e c e 系) 。研究方向包括a dh o e 网络的定向m a c 协议、定向路由协议、 网络调度等。 马里兰大学s a t i s h k t r i p a t h i 教授所领导的“移动计算与多媒体实验室”( t h e m o b i l ec o m p u t i n ga n dm u t i m e d i a l a b o r a t o r y ( m c m l ) ，h t t p ：w w w c s u m d e d u p r o j e c t s m c m l ) 。研究方向包括a dh o c 网络路由协议、q o s 等。 加州大学圣巴巴拉分校e l i z a b e t h m b e l d i n g r o y e r 教授所领导的“移动性管 理和联网实验室 ( t h em o b i l i t ym a n a g e m e n ta n dn e t w o r k i n g ( m o m e n t ) l a b ， h t t p ：m o m e n t c s u c s b e d u ) 。研究方向包括a dh o e 网络路由协议、多播协议、地 址重构、安全性、q o s 、可伸缩性和适应性等。 加州大学圣克鲁兹分校j j g a r c i a - l u n a a c e v e s 教授所领导的“计算机通信 研究小组 ( t h ec o m p u t e rc o m m u n i c a t i o i l sr e s e a r c hg r o u p ，h t t p ：w w w c s e r c s c e d u r e s e a r c h c c r g h o m e h t n a ) 研究方向包拓无线网络的信道接入等。 1 3 课题研究目的 由于移动a dh o c 网络所具有的许多优良特性，它被广泛的应用于各个领域， 比如：会议、个人区域网络、紧急事件服务、传感器尘埃、军事通信等。 现代战场上，情况瞬息万变，置身于战场上的每一个作战单元都不太可能 在“眼盲 、“耳聋 的情况下生存很久，那种一个排只有一部电台的情况已经 不再符合现代战争的要求。 从前面的介绍中已经知道，移动a dh o e 网络从诞生初期就与军事应用有着 密不可分的联系，它的节点移动性、网络拓扑结构可变性等特点正好符合现代 战场的要求，但也正是这些特点使得传统的路由协议不再适用于a dh o e 网络。 这些年来，研究人员针对a dh o e 网络的特点，从不同的角度提出了许多不 同策略的路由协议，比如d s r 、a o d v 、t o r a 、z r p 、c b r p 、c g s r 等。虽 说这些路由协议比传统的路由协议可以更好地适应移动a dh o e 网络，但针对战 场通信中高实时性、高抗毁性、高自愈性等特点又或多或少的存在一些不足。 鉴于此，本文的目的就是提出一种改进的路由协议，使它可以符合战场这一特 殊环境的要求。 武汉理工大学硕士学位论文 1 4 论文结构 第二章从网络特性、发展过程、存在问题等方面简单介绍了移动a dh o e 网 络。 第三章对目前提出的移动a dh o e 网络路由协议进行分析比较。 第四章针对战场这一特殊环境提出一种改进的分层移动a dh o e 网络路由协 议h g r ( h i e r a r c h i c a lg r o u pm u t i n g ) ，并对其工作方式进行详细阐述。 第五章通过n s 2 仿真模拟软件对提出的路由协议h g r 的端到端平均延迟、 封包投递比例、路由表收敛速度等指标进行仿真，得出新的路由协议比较适合 战场这种特殊环境的应用。 第六章指出h g r 路由协议还存在的不足，并给出将来的研究方向。 4 武汉理工大学硕士学位论文 第2 章a dh o c 网络概述 2 1 移动a dh o c 网络 移动a dh o e 1 】网络由一组无线节点组成，是一种不需要依靠现有固定通信 网络基础设施的、能够迅速展开使用的网络体系，所需人工干预最少，是没有 任何中心实体、自组织、白愈的网络；各个网络节点相互协作、通过无线链路 进行通信、交换信息，实现信息和服务的共享：网络节点能够动态的、随意的、 频繁的进入和离开网络，而常常不需要事先预警或通知，而且不会破坏网络中 其他节点的通信。 移动a dh o c 网络是对等网络【6 】，在网络中任何两个节点之间的无线传播条 件受制于这两个节点的发射功率，当这个无线传播条件足够充分时，这两个节 点之间就可以直接进行通信。假如源节点和目的节点之间没有直接的链路，那 么就使用多跳路由( 如图2 1 所示) 。 图2 1 多跳a dh o c 通信 武汉理工大学硕士学位论文 在多跳路由中，一个分组从一个节点转发到另一个节点，直到该分组到达 目的节点为止。当然，为了在源节点和目的节点之间寻找路由，甚至为了确定 存在还是不存在一条至目的节点的路由，合适的路由协议是必需的。 2 2 分组无线网络发展简介 移动a dh o c 网络技术不是一种新技术哺1 。以前，移动a dh o e 网络的研究 和开发大多数由美国政府，尤其是美国国防部高级计划研究局( 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 t s a g e n c y ，d a r p a ) 来支持。 移动a dh o c 网络的思想最早可追溯到1 9 6 8 年的a l o h a 网络。a l o h a 网 络的研究目标是为了将夏威夷的教育设备连接在一起。a l o h a 采用固定基站和 分布式信道访问管理，为之后分布式信道访问技术的研究和开发提供了基础。 a l o h a 协议是单跳协议，不支持路由功能。 d a r p a 在1 9 3 7 年开始研制分组无线网络( p a c k e tr a d i on e t w o r k ，p r n e t ) 。 p r n e t 的研究目标是为了将数据分组交换技术引入到无线环境中，开发军用无 线数据分组网络。p r n e t 是多跳网络，提供集中式和分布式的操作管理机制。 抗毁无线网络( s u r v i v a b l er a d i on e t w o r k ，s u r a n ) 是美国d a r p a 于1 9 8 3 年开发的，主要解决p r n e t 遗留的问题、网络扩展性、安全、处理能力，以及 能量管理。s u r a n 的主要研究目标是开发网络算法，采用这些网络算法使网络 能够扩大到数万个节点；能够对抗安全攻击；能够采用低成本、低功耗小型电 台支持复杂的分组无线网络协议。 到了2 0 世纪8 0 年代后期和9 0 年代初期，为了使全球信息基础设施支持无 线移动环境，d o d 在1 9 9 4 年启动了d a r p a 全球移动信息( g l o b a lm o b i l e ， g l o m o ) 系统计划。g l o m o 计划的研究目标是支持无线装置之间随时随地的以 以太类多媒体连接：解决所谓的移动a dh o c 网络的m 3 ( 移动( m o b i l e ) 、多跳 ( m u l i t i h o p ) 、多媒体( m u l t i m e d i a ) ) 问题。 1 9 9 7 年6 月成立了i n t e m e t 工程任务组( i n t e r n e te 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 工作组( 简称i e t fm a n e t 工作组) ，该工作组的任务十分 关键，这是应为i e t fm a n e t 工作组是当前唯一能够确保通过引入一种广泛采 纳的网络协议而实现移动a dh o e 网络协议互操作性的组织。i e t fm a n e t 工作 组的工作目标如下： ( 1 ) 将各个领域的单个目标的路由协议标准化： 6 武汉理工大学硕士学位论文 ( 2 ) 解决在预定应用环境中的安全问题； ( 3 ) 在可能解决层次化的更为先进的服务问题，如在原有路由技术之上进 行多目标传输和服务质量q o s 的扩展。 2 3 移动a dh o c 网络的特点 一个移动a dh o e 网络有若干移动平台订1 ( 例如：带有多个主机和无线通信 装置的路由器) 组成，这里将移动平台称为“节点 ，各个节点自由的随处任意 移动，移动a dh o e 网络至少具有以下共同特性和要求： ( 1 ) 分布式操作： 由于移动a dh o c 网络节点不能够依靠固定基础设施或者管理中心，所以移 动a dh o c 网络节点必然是分布的； ( 2 ) 带宽有限、链路容量易变 无线链的容量明显低于有线信道。无线环境具有带宽有限、比特误码率高、 链路质量和链路容量起伏波动等问题。考虑到多址访问、衰落、噪声、环境干 扰等因素的影响后，无线通信的实际吞吐量常常比最大无线传输速率低得多； ( 3 ) 移动性与网络拓扑动态性 移动a dh o e 网络节点自由的任意移动，这必然导致网络拓扑的动态变化。 因此，网络拓扑( 通常是多跳的) 可能随机、迅速、不可预测的变化，并且可 能由双向链和单向链组成； ( 4 ) 设备限制 假如不考虑诸如汽车、战舰、以及战士之类的不同传达手段，那么剩下需 要考虑的就是诸如传感器之类的手持设备，或者更小的设备。这些小设备受到 设备本身的若干特性的限制，包括电池能量、设备的处理能力； ( 5 ) 物理安全 移动无线网络比一般固定网络更加易受物理安全威胁，偷听、哄骗、拒绝 服务攻击的可能性也远远高于其他网络。 2 4 移动a dh o c 网络中的问题 移动a dh o e 网络n h 堙3 在提供了应用可能性的同时，也面临着诸多挑战和许 多亟待解决的问题。 武汉理工大学硕士学位论文 ( 1 ) 消费者应用 移动a dh o c 网络在消费者市场很有潜力，但是在这种可能性变成现实之前 还有许多难题必须解决。目前不存在移动a dh o c 网络的覆盖范围，即使在移动 a dh o e 网络登录大市场之后其覆盖范围也是不规则的； ( 2 ) 外部系统连接 很多应用都需要连接到某些外部系统，尤其是连接到i n t e m e t 。但是，将 i n t e m e t 连接到移动a dh o e 网络中的任意一个节点是极不确定的，因此，获得 典型的i n t e r n e t 服务、集中授权和集中管理功能是有问题的； ( 3 ) 带宽有限 与有线固定连接相比，无线带宽是一种非常宝贵的资源。除了有效传输速 率较低以外，还引起了路由协议设计的问题，因为带宽必须尽可能多的留给真 正的数据传输； ( 4 ) 扩展性 动态网络拓扑可能缺乏累加性引起了直接扩展性问题，缺乏累加性导致路 由表更大，而为了维护路由表就必须将控制信息发送到网络中。当节点相互之 间快速移动的时候，还必须发送更多的控制信息，控制信息的增多减少了有效 带宽，这就限制了网络扩展性； ( 5 ) 电池能量极其有限 大多数移动a dh o c 网络设备都是小体积的手持式装置，其电池供电能力极 其有限。通过改变发射功率可以控制电池的使用，虽然使用较小的发射功率引 起多跳问题，可以节省能量，但是多跳网络使得路由算法更加苛刻，其操作需 要消耗更多的功率； ( 6 ) 安全问题 移动a dh o c 网络主要面临以下三种不同的威胁：首先，无线媒介使得移动 a dh o c 网络在面对从被动偷听到主动干扰范围内的许多攻击显得非常脆弱；其 次，移动a dh o c 网络节点是自治的，能够独立的到处随机移动，这就使得自己 变成比较容易被捕捉的目标；最后，移动a dh o c 网络采用分布式决策、缺乏集 中式基础设施、缺乏集中式安全证书颁发机制。 武汉理工大学硕士学位论文 2 5 小结 本章从a dh o e 的网络特性、发展过程、存在问题等方面简单介绍了移动 a dh o c 网络。从其特性中可以了解到对它的研究热点主要集中在q o s 问题、对 组播的支持、网络的安全性、与i n t e r a c t 互联、路由协议等几个方面。而路由协 议又是上述问题的基础，因此它是研究的重点。 9 武汉理工大学硕士学位论文 第3 章移动a dh o c 网络路由协议分析 移动a dh o e 网络路由协议的分类方式大概有以下几种： ( 1 ) 按照路由发现机制可以分为表格驱动路由协议、按需路由协议和混合 路由协议； ( 2 ) 按照网络结构可以分为平面网络路由协议和分层网络路由协议； ( 3 ) 按照到达目的节点的路径可以分为单径路由协议和多径路由协议； ( 4 ) 按照目的节点的数目可以分为单目标路由协议和多目标路由协议。 下面将按照不同的分类方式对移动a dh o e 网络的路由协议进行分析。 3 1 表格驱动路由协议和按需路由协议 3 1 1 表格驱动路由协议 表格驱动路由协议又称为预先( p r o a c t i v e ) 路由协议，它的路由发现策略与传 统路由协议类似，节点通过周期性地广播路由信息分组，交换路由信息，主动 发现路由。同时，节点必须维护全网所有节点的路由。表格驱动路由协议需要 在每个节点维护一个或多个路由表，其中包含了该节点到网络中所有其他节点 的一致的、最新的路由信息。为了维护这样的路由表，每个节点要定期向网络 广播拓扑信息，以保持路由表信息与网络拓扑的变化之间的一致性。 采用不同的路由表和不同的广播策略便形成了不同的具体路由协议，下面 介绍几个典型的表格驱动路由协议。 ( 1 ) d s d v 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 r ) 汹1 协议是在距离向量算法的基 础上进行改进设计的。它基于经典的b e l l m a n f o r d 路由机制。d s d v 的特点是 采用了序列号机制用于区分路由信息的新旧程度，防止距离矢量算法可能产生 的路由环路。 在d s d v 中，网络中的每个节点维护一张路由表，表中记录所有可能目的 结点的下一跳地址和路径的跳数。路由表中的信息周期性地更新，以维持网络 中所有路由表的一致性。为了减少这种周期性的路由更新增加的网络流量，路 1 0 武汉理工大学硕士学位论文 由更新信息可以采用增量方式。即完全更新( 发送整个路由表的信息，因此可能 用到多个网络层协议数据单元) 或增量更新( 仅发送上次完全更新以来变动的路 由信息，只是用一个网络层协议数据单元) 。完全更新在节点偶然移动的情况下 不用频繁发送，这使得路由协议的开销减少。但节点也需要另外维护一张增量 路由信息表，用以保存增量更新发送的路由信，g 。d s d v 的缺点是它不支持单向 信道，不适应变化速度快的a dh o e 网络。 ( 2 ) 哪 w r p ( w i r e l e s sm u t i n gp r o t o c 0 1 ) 刚协议是一个利用表来维护网络中节点路 由信息的协议。每个节点需要维护四个表：距离表、路由表、链路代价表、消 息转发列表( m r l ) 。w i 冲属于路径发现算法( p f a ) 的一种，它通过强制每个节点 对所有来自其邻接点的信息进行一致性检查来避免“无穷计算问题“，可以减 少出现路由环路的次数，从而加快算法的收敛速度。移动节点使用更新消息通 知每一条链路的变化，更新消息仅在邻接点间传递。节点通过接收应答和其他 消息来感知其相邻节点的存在。如果一个节点没有消息要发送，它必须定期发 送h e l l o 消息以声明其存在。 ( 3 ) f s r f s r ( f i s h e y es t a t er o u t i n g ) 油1 协议是链路状态型协议，它使用了鱼眼技术， 在不同鱼眼域中的节点以不同的频率( 由节点距离决定的) 只向邻居节点广播链 路更新信息，这能够大大减少链路状态更新信息，从而降低了路由信息流量。 为了减少控制包的开销，f s r 在以下三个方面对链路状态算法进行了修改：首 先仅在邻节点间交换链路状态信息，而不是将链路状态信息广播到整个网络； 其次，链路状态信息交换是由时间触发，而不由事件触发的；第三，对于路由 表中不同的记录，采用不同的时间间隔交换链路状态信息。对于较近的节点( 根 据预先定义的范围) 用较短间隔交换链路状态信息，对于较远的节点用较长的间 隔交换状态信息。这些修改简化了控制包，降低了传输频率。因此，f s r 的伸 缩性较好。但是，随着移动性的增强，到达远距离目的结点的路由精确程度会 有所降低。 ( 4 ) t b r p f t b r p f ( t o p o l o g yb r o a d c a s tr e v e r s ep a t hf o r w a r d i n g ) 啪1 协议也是基于链路状 态的路由协议，它采用了逐跳( h o p b y h o p ) 路由。t b i 冲f 在传播更新信息包是使 用了反向路径转发( r p f ) 的概念，即生成更新信息包的源节点到所有节点的最短 武汉理工大学硕士学位论文 路径构成了生成树，而更新信息包是沿着生成树的相反方向进行传播的。在这 种路由策略中，每个节点都会利用改进的d i j k s t r a 算法对拓扑表中保存的部分网 络拓扑信息进行计算，得出一棵用以获取到达所有目的结点路径的源树。在 t b r p f 中，每个节点通过仅仅把其源树上的部分节点信息报告给邻接点来减少 控制包开销，这个报告工作是通过周期性地发送不同的h e l l o 包完成的。而且， h e l l o 包只包含相邻节点的状态变化情况。因此，t b i 冲f 协议中的h e l l o 包比其 他协议中的那些包含全部链路状态信息的h e l l o 包小。 3 1 2 按需路由协议 按需路由又称为反应式路由协议，它认为由于a dh o c 网络的动态变化性， 没有必要维护去往其他所有节点的路由，而是仅在源节点没有去往目的节点路 由的时候才进行路由发现。因此，节点的拓扑结构和路由表内容是按需建立的， 一般来说它仅仅是整个拓扑结构信息的一部分。它不需要周期性地广播路由信 息，节省了一定的网络资源。按需路由协议通常由路由发现和路由维护两个过 程组成。当一个节点需要向某个目标节点发送数据时，它会首先查询其路由表， 如果发现没有去往该目的节点的路由，就启动一个路由发现过程：源节点在a d h o c 网络中广播一个路由请求( r r e q ) 分组，当合适的路由被找到( 请求包到达目 的结点或者拥有至目的节点路径的中间节点) 时，就会返回一个路由请求应答 ( r r e p ) 分组。路由建立后，它就由路由维护过程进行维护，直到该路由不再需 要，或者通过任何路径都无法访问目标节点。当拓扑结构发生变化时，通过路 由维护过程删除失效路由，重新发起路由请求过程。路由维护通常依靠底层提 供的链路失效检测机制进行触发。接下来介绍几个典型的按需路由协议。 ( 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 ) n 3 1 协议是最早采用按需路由思想的路由协议 之一，它的主要特点是使用源路由机制进行分组转发。d s r 采用了路由缓存技 术，用于存储源路由信息，当学习到新的路由时则修改路由缓存内容。 d s r 协议采用路由错误报文和确认报文进行路由维护。d s r 协议中节点不 需要周期性地发送报文，节省了能源和网络带宽，还可以支持节点睡眠。由于 采用了源路由机制，中间节点不用维护去往全网所有节点地路由信息，而且可 以避免出现路由环路。但是，由于每个数据分组都携带了路径信息，造成协议 开销较大。特别是当路径较长时，分组的净载荷率较低，因此d s r 不适合节点 1 2 武汉理工大学硕士学位论文 较多的a dh o e 网络，网络的可扩展性不强。 ( 2 ) a o d v a o d v ( a dh o eo nd e m a n dd i s t a n c ev e c t o r ) n 铂协议是在d s d v 协议基础上 结合类似d s r 中的按需路由机制进行改进后提出的。a o d v 协议借用了d s r 中按需进行路由发现和路由维护机制以及d s d v 中的逐跳路由、序列号、定期 触发广播。在源节点和目的节点问路径上的中间节点隐式保存了路由请求和相 应的结果，而所有不在这条路径上的节点不需要维护路由信息和参与路由表交 换。 a o d v 通过周期性地广播h e l l o 报文来监视链路状态。若节点在使用某个链 路时发现该链路断开，节点将从路由表中删除该链路的路由，并发送路由出错 ( r r e r ) 分组通知那些因链路断开而不可达的主机将对应路由从路由表中删除， 沿途转发r r e r 的主机也删除自己路由表中的对应路由。 a o d v 协议基于传统的距离向量路由机制，通过使用目的序列号有效地防 止了循环的发生，解决了传统的基于距离向量路由协议存在的无限计数问题。 它支持中间节点相应请求，能使源节点快速获得路由，但是需要周期性地广播 报文，要消耗一定的能源和网络带宽，还存在过时路由问题。a o d v 协议基于 双向信道的假设工作，路由响应分组直接沿着路由请求的反方向回到源节点， 所以它不支持单向信道。 ( 3 ) t o r a t o r a ( t e m p o r a l l y o r d e r e dr o u t i n ga l g o r i t h m ) n 明协议是在有向无环图d a g 算法的基础上提出的采用逆向链路的按需路由协议。 t o r a 在路由响应中采用了改进的d a g 算法，算法的具体实现是通过路由 响应分组( 在t o r a 协议中称为更新分组) 在回到源节点的过程中完成的。为了在 拓扑结构发生变化时能够迅速重新生成路由，并将产生的协议分组限制只在受 到影响的节点中扩散。t o r a 协议仍然会采用上述算法重新构造失效的d a g 。 t o r a 协议的优点是能够将控制信息局限在拓扑结构发生变化的少量节点 中，支持组播；不足之处是会产生临时性的无效路由信息。 3 1 3 混合路由协议 混合路由协议既包括表格驱动路由又包括按需路由，它通过把相互邻近的 节点组织在一起形成一个组，而这些组之间形成一个全网的主干结构，从而降 武汉理工大学硕士学位论文 低路由发现的开销，达到增强网络可扩展性的目的。在混台路由协议中，邻近 节点之间一般使用表格驱动路由，而较远的节点间通信则采用了按需路由策略。 一般说来，混合路由协议是基于分区的，网络被分成了不同的区，它们属于平 面路由协议，典型的有z r p ，z h l s 等。还一些混合路由协议是基于树或者簇的， 它们属于分层路由协议。本节主要讲的是平面路由协议，所以，在这里将着重 介绍基于分区的混合路由协议。 z r p ( z o n er o u t i n gp r o t o c 0 1 ) 1 1 6 是一个分区路由协议，它巧妙地结合了表 格驱动路由协议和按需路由协议的长处。在z r p 中，每个节点根据指定的区域 半径( 以跳数为单位) ，采用距离矢量算法维护指定区域内节点间的路由，而采用 按需路由机制发现去往区域外节点的路由。 z r p 的性能依赖于区域半径参数值，而区域半径由网络特征如节点密度、 节点移动速度等来确定。小的区域半径适合在移动速度较快的节点组成的密集 网络中使用；大的区域半径适合在移动速度慢的结点组成的稀疏网络中使用。 3 1 4 表格驱动路由与按需驱动路由的比较 表格驱动路由协议类似于分组转发的无连接法，与何时需要路由，以及需 要路由的频次无关。表格驱动路由协议的基本工作机制是路由表更新机制，这 种机制需要经常( 或者周期性的) 传播路由信息。路由信息被经常传播和维护， 一个网络节点到达网络中所有其它节点( 如果可达) 的路由总是几乎可以立即 获得。这种路由特性对于数据包、自组织包的传递非常有用。 而使用按需路由协议，在一个网络节点需要一条到达其目的节点的路由， 只有等到寻找到这样一条路由的时候，才能够使用该条路由进行通信。 以下是按需路由协议的三个特点： ( 1 ) 按需路由协议只有在有分组需要转发到目的节点的时候才会尝试寻找 到达该目的节点的路由。必须在可以发送分组之前完成这种按需路由寻找，但 是这就增加了分组交付的时延。 ( 2 ) 如果没有另外的信息，那么按需路由