（计算机软件与理论专业论文）Ad+Hoc网络路由协议的设计与仿真.pdf

郑州人学硕i ：学位论史 摘要 无线移动自组网( a dh o e ) 是一种特殊的无线移动通信网络，网络中的所有移动终 端地位平等、自组织、无需事先布置任何网络设施或中心控制节点，具有网络拓扑结构 动态变化、网络带宽与能量受限等特点。无线移动自组网成为近几年研究热点，对其媒 体接入控制和路由协议的研究存在着巨大的挑战。 本文研究了a dh o e 网络路由协议与技术，重点讨论了几种典型的路由协议：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 ，a dh o e 按需距离向量协议) 、d s r ( d y n a m i cs o u r c er o u t i n gp r o t o c o l ，动态源路由协议) 、d s d v ( d e s t i n a t i o ns e q u e n c e d d i s t a n c e v e c t o r ，目的节点排序距离向量路由协议) 和t o r a ( t e m p o r a r y o r d e r e d r o u t i n g a l g o r i t h m ，临时排序路由算法) ，深入研究了上述路由协议算法。针对不同网络模式、 不同移动场景和不同的传输负载对以上路由协议进行了模拟，选取延迟、包投递率、路 由开销、网络系统生存时间作为参数，在网络仿真平台n s 2 上进行了协议仿真，对仿真 结果进行了详尽的分析，分析结果对a dh o c 网络工程应用、网络部署具有现实的指导 意义。 本文还针对a dh o c 网络中能量受限的特点，研究了基于能量保护的路山协议，给 出了一种基于能量有效的路由协议e e r p ( e n e r g y e f f i c i e n t r o u t i n g p r o t o c 0 1 ) ，定义了延 迟公式，从而有效延长网络系统生存时间。通过在n s 2 上仿真测试，e e r p 较a o d v 具有更好的系统生存时间，验证了设计思想，为进一步研究a dh o e 网络提供了参考和 借鉴。 关键字：移动自组网；路由协议；网络模拟；n s 2 第11 i ( 郑州人学顾i ：学位论文 a b s t r a c t t h ew i r e l e s sm o b i l ea dh o en e t w o r k ( w m a n e t ) i sas p e c i a lw i r e l e s sm o b i l e c o m m u n i c a t i o nn e t w o r k i ti ss od u et ot h a ta l lm o b i l et e r m i n a l si nt h en e t w o r ka r ee q u a la n d s e l f - o r g a n i z e d ，t h e r ei sn on e e dt op r e - d e p l o ya n yi n f r a s t r u c t u r eo rc 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 et o p o l o g yi sd y n a m i c a l l yc h a n g i n g ，t h eb a n d w i d t ha n de n e r g ya r ea l s ol i m i t e d ，e t e t h u s ， t h er e s e a r c ho nt h ew m a n e t , i np a r t i c u l a r , t h er e s e a r c ho l li t sm a ca n dr o u t i n gp r o t o c o l s h a sb e e ni m m e n s e l yc h a l l e n g i n g i ti sh a r d ，h o w e v e r ，t od e p l o yar e a ln e t w o r ki nt h ep h a s eo f r e s e a r c h i n g g e n e r a l l y , n e t w o r ks i m u l a t i o ni so n eb a s i cm e a n st os p r e a dt h er e s e a r c ho nt h e n e t w o r kt e c h n o l o g i e s b a s e do nt h es t u d ya n dr e s e a r c ho nb a s i ck n o w l e d g ea n dr o u t i n gt e c h n o l o g yi na dh o e n e t w o r k s ，e m b e d d e dr e s e a r c ho ns e v e r a lt y p i c a lr o u t i n gp r o t o c o ls u c ha sa o d v , d s d s d va n dt o r ah a sb e e nd o n ei n t h i sp a p e r a n dm a i n l yd i s c u s s e st h er o u t i n gp r o t o c o l s i m u l a t i o ni m p l e m e n t a i o ni na dh o en e t w o r k sb a s e do nn s 2 a n do nt h eb a s i so ft h i sm o d e l f o rd i f f e r e n tn e t w o r k s ，d i f e r e n ts c e n e sa n dd i f e r e n tm o b i l et r a n s m i s s i o ni o a do nt h er o u t i n g p r o t o c o li n t r o d u c e da b o v e t h ep a p e rs e l e c td e l a y , p d r ( p a c k a g ed e l i v e r yr a t i o ) ，r o u t e s p e n d i n g ，s y s t e mt i m ea sp a r a m e t e ro nn s 2 ，p r o v i d e st h es i m u l a t er e s u l t so fp r o t o c o l s m e n t i o n e da b o v ea n dm a k e sap a r t i c u l a ra n a l y s i s ，i th a sm u c h p r a c t i c a lg u i d a n c em e a n i n go n p r o j e c ta p p l i c a t i o na n dn e t w o r kd e p l o y i n g a tl a s t ，c o n c e r n i n ge n e r g yl i m i t e di na dh o c n e t w o r k , e n e r g yp r o t e c t i n gr o u t i n gp r o t o c o l h a sb e e ns t u d i e di nt h i sp a p e r w ed e f i n e dt h ed e l a yf o r m u l aa n dp r e s e n tt h ee n e r g ye f f i c i e n t r o u t i n gp r o t o c o l ( e e r p ) w es i m u l a t et h i sp r o t o c o li nn s 2 ，i ts h o w se e r ph a sl o n g e rs y s t e m t i m et h a na o d v b a s e do nt h i s ，w ev a l i d a t et h ed e s i g na n dt h i so f f e r sr e f e r r e n c et os t u d ya d h o en e t w o r k k e yw o r d s ：a dh o cn e t w o r k , r o u t i n gp r o t o c o l ，n e t w o r ks i m u l a t i o n ，n s 2 第2 负 郑州人学颀i ：学位论文 第一章绪论 1 1 研究背景 1 1 1 移动自组织网络的概念及特性 移动自组织网络( m o b i l e a dh o en e t w o r k s ，m a n e t s ) 是由若干无线移动节点在不 依赖任何固定基础设施或集中组织管理机构的条件下构建的一种多跳自组织临时性自 治系统【l , 2 1 。由于移动自组织网络缺乏固定的路由基础设施和稳定的无线链路，网络节点 必须通过协作建立动态路径以完成数据的临时传输。在这种网络环境下，受无线收发装 置功率限制，节点的无线传输覆盖范围有限。如果两个节点恰好位于对方的无线传输覆 盖范围之内，那么它们可以直接通信。否则，两个节点必须借助网内其它节点的中继功 能才能实现通信。 因此，每个节点兼具主机和路由器两种角色。一方面，节点作为主机运行相关的协 同应用程序；另一方面，节点作为路由器需要运行相关的路由协议，执行路由发现、路 由维护等常规路由操作，对接收到的目的地不是自己的数据包进行转发。移动自组织网 络能够在没有或者不便于利用现有网络基础设施的条件下提供一种通信网络，从而拓宽 了移动通信网络的应用环境。 如上所述，移动自组织网络是由移动节点组成的自治系统。这个自治系统既可以独 立运行，也可以经过网关连接到其它的固定网络( 如因特网) 中【3 1 。在后一种情况下， 自组织网络通常是以“未端网络”的形式接入现有网络。它只允许产生于或者目的地是 该自组织网络内部节点的信息进出，而不会让其它信息穿越该网络。 移动t h 组织网络与传统的有线网络和无线网络相比，具有以下特性【3 - 5 】： 网络的自组性 移动自组织网络的最大特性之一是没有基础设施 6 1 。这里所指的基础设施主要有三 类： 路由基础设施：用于实现节点互连，如路由器、交换机等专用设备以及静态通信链 路。 服务基础设施：用于向节点提供服务，如d n s 服务器、d h c p 服务器或者c a 服 务器等。 组织管理基础设施：用于处理节点注册、证书颁发以及其它网络配置任务等。 任意移动自组织网络都缺乏固定的路由基础设施。然而，根据具体应用情况，某些 移动自组织网络可能存在后两类基础设施，特别是组织管理基础设施可以存在于多种应 用领域。 出于缺乏固定的网络基础设施支持，移动自组织网络通常采用动念自适应组网技 第1 页 郑州人学颂l ：学位论文 术。网络节点通过分层协议和分布式算法协调各自的行为，快速、自动地构成一个独立 的移动无线通信网络。 多跳路由 当节点要与其无线传输覆盖范围之外的节点进行通信时，需要中间节点的多跳转 发，而传统无线网络中的移动节点不具有路由功能。与有线网络采用专用路由设备实现 多跳路由不同，移动自组织网络的多跳路由是通过普通节点协作实现的。 动态的网络拓扑结构 网络的拓扑结构指的是从网络层角度反映物理网络的逻辑视图( 如图1 1 所示) 。 在任意时刻，移动自组织网络都可采用随机图作为其数学模型，图中顶点代表节点，顶 点间的有向边代表对应节点之间的无线信道。受节点移动的随意性、无线收发装置功率 的变化、无线信道之间的干扰和地形变化等因素的影响，网络的拓扑结构随时都可能发 生变化，并且很难预测这些变化的方式和速度。具体表现为随机图中顶点或者有向边的 增加或者消失、随机图的分割与合并等操作。而对于传统的有线网络和蜂窝无线网络来 说，网络拓扑结构则表现得较为稳定。 图1 - 1 移动臼组织网络的随机图模型 有限的无线传输带宽和信道质量 由于移动自组织网络采用无线传输技术作为基本通信手段，而无线信道本身的物理 特性，使得其所能提供的网络带宽相对于有线信道要低的多，信道质量也比有线信道差 的多。 此外，考虑到竞争共享无线信道时产生的冲突、信号衰减、噪声干扰、信道问干扰 等种种不利因素，节点能够得到的实际带宽远远小于理论上的最大带宽。 存在单向的无线信道 移动自组织网络采用无线信道通信，由于地形环境或者发射功率等因素影响可能会 出现单向无线信道。例如，节点a 的发射功率较节点b 的大，节点b 可以接收到来自 节点a 的信号，节点a 却无法接收到来自节点b 的信号。这时即存在一条从节点a 到 节点b 的单向无线信道( 如图l - 2 所示) 。而在传统的有线网络或者无线网络中，节点 之白j 通常基于双向的有线或者无线信道进行通信。 第2 页 郑州人学顾i ：学位论文 节点电能受限 一般情况下，移动自组织网络中的节点都是依靠电池提供电能。因此，在进行系统 设计时必须考虑如何有效地节省电能。 网络的分布式控制 移动自组织网络中的节点都兼有主机和路由器功能，不存在类似于基站这样的网络 集中式控制设备，各节点之间的地位平等。网络的控制和管理多采用分布式控制方式， 由网络中多个( 或者全体) 节点协作完成，在一定程度上避免了因单点被破坏而影响全网 的正常运作，因此具有很强的抗毁性和强健性。而在传统的有线网络和无线网络中，通 常存在基站、路由器、交换机等集中式控制设备，网内普通节点和这些设备的地位不对 等。 ，_ ，- _ 。一。，、，、 ，、 i，一、! ； a o0 0 ) j l 出， ， 、 一一一， ? 、 、7 ，- 。- _ _ ，一， 图l - 2 移动自组织网络中的单向信道问题 有限的安全性 移动自组织网络是一种特殊的无线网络，由于采用无线信道、电池供电、分布产控 制等技术和方式，所以更加容易受到被动窃听、主动入侵、拒绝服务、剥夺睡眠等多种 攻击。 网络生存期短 移动自组织网络通常是由于某个特定原因而临时创建的。当使用结束后，网络将会 自动消失，其生存期相对于其它类型的网络来说是短暂的。 由上述特点可知，移动自组织网络是一种可适应特殊环境的移动计算机通信网络， 是移动通信和计算机网络的交叉，也是移动互联网的一种构建方式 3 1 。一方面，自组织 网络采用计算机网络中分组交换机制实现信息交换；利用t c p f l p 协议族，由一组移动 节点构建起独立的无线i p 网络。另一方面，自组织网络中的节点多是配置有相应无线 收发装置的便携式设备，如笔记本电脑、手机、车载电台等，具有自由移动能力。 1 1 2 移动自组织网络起源及发展 自组织网络技术最早起源于二十世纪六十年代未的a l o h a 网络和七十年代初的美 第3 页 郑州人学顾i ：学位论文 国军事通信领域【5 1 。早在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 ( d e f e n s ea d v a n c e d r e s e a r c h p r o j e e t a g e n c y ) 和o n r ( u s a r m ya n d o f f i c e o f n a v a l r e s e a r c h ) 的大力支持垆“。 1 9 7 2 年，d a r p a 资助了分组无线电台网络( p a c k e tr a d i on e t w o r k ，p r n e t ) 研究计划， 即让报文交换技术在不受固定或有限的基础设施限制的环境下运行。其最初的动机之一 就是探索在战术环境下的数据通信网络技术与应用问题，以满足战场生存的军事需求。 在战场恶劣环境下，通信设备不可能信赖已经敷设的通信基础设施。一方面这些基础设 施可能根本不存在，另一方面这些基础设施也会随时遭到破坏。因此，能快速部署的、 具有自组织特性的移动基础设施是这种网络区别于其它商业蜂窝系统的基本要素。在结 构上，这种网络是一系列移动节点组成，它不依赖于任何已有的网络基础设施，网络中 的节点动态变化且任意分布，节点之间通过无线方式互连，它将分组交换网络的概念延 伸至广播网络的范畴。1 9 8 3 年，d a r p a 又制定了s u r a n ( s u r v i v a b l e a d a p t i v en e t w o r k ) 研究计划【_ 7 1 ，其目的是进一步拓展p r n e t 的应用技术，以支持可生存与自适应的大规 模无线军事通信网络的建立。s u r a n 重点研究了战术环境条件下网络拓扑动态变化的 自适应网络协议与实现技术。1 9 9 4 年，为满足战术环境下数据通信与信息系统的应用， d a r p a 又制定了g l o m o ( g l o b a lm o b i l ei n f o r m a t i o ns y s t e m s ) 研究计划【，重点研究在快 速展开条件下，具有抗毁性的战术信息系统的若干关键技术，包括网络自组织、自愈算 法、平面分层网络结构下的多跳路由算法等。2 0 0 0 年，d a r p a 又在g l o m o 、 c a j q ( a i r b o m ec o m m u n i c a t i o nn o d e ) 、s u o ( s m a l lu n i to p e r a t i o n s ) 研究计划的基础上， 制定了m o s a i c ( m o b i l e ，o n - t h e m o v e ，s u r v i v a b l e ，a d a p t i v e ，i n t e g r a t e dc o m m u n i c a t i o n ) 研 究计划1 9 1 ，其目的是在前面研究计划的基础上，通过相关技术和设备的研究，从整体上 建立面向二十一世纪的军事战术无线通信基础设施。 自组织网络技术在军事通信领域发展的同时，也引起了民用领域的极大兴趣。1 9 9 1 年，i e e e 在丌发i e e e 8 0 2 1 l 无线局域网( w i r e l e s sl o c a la r e an e t w o r k ，w l a n ) 标准 时【lo 】，将分组无线网络改称为“a dh o e 网络”。这一名称表明i e e e 希望这种网络成为 一种为特定目的而临时构建并短期存在的网络。需要指出的是，i e e e 8 0 2 1 l 标准定义的 自组织网络是采用分柿式对等组网方式，仅由那些通过无线介质能够互相进行直接通信 的站构建的网络，即独立的基本服务集( i n d e p e n d e mb a s i cs e r v i c es e t ，i b s s ) l 。i b s s 不 含无线接入点( a c c e s sp o i n t ，a p ) ，是一种单跳自组织网络，但目前人们所研究的自组织 第4 负 郑州人学硕i ：学位论文 网络通常是多跳网络。最早从事民用多跳自组织网络研究的组织是1 e t f ( i n t e m e t e n g i n e e r i n gt a s kf o r c e ) ，其研究工作始于1 9 9 5 年对军用战术网络、军用卫星网络和无 线局域网的技术研究，重点研究在高速动念环境下支持i p 业务的网络互联和路由问题、 利用多跳无线分组网络构建一个基于i p 的移动互联网络以及通过i p 实现与固定互联网 络的无缝连接等。随着自组织网络技术研究的发展，1 9 9 7 年i e t fj 下式成立了移动自组 织网络( m o b i l e a dh o en e l w o r k s ，m a n e t ) - i 作组( w o r k i n gg r o u p ，w g ) 【1 2 j 。当前， i e t f m a n e t w g 的研究任务是自组织网络的路由协议标准化和网络接口标准化【5 ，“1 。 此外，欧洲瑞士洛桑联邦技术学院t e r m i n o d e 组织也制定了一项长期研究计划，即 t e r m i n o d e s 计划 1 3 - 1 4 1 ，时间跨度从2 0 0 0 年到2 0 1 0 年，该计划旨在研究和设计一个大范。 围、自组织的移动自组织网络，并应用于商业以及其它潜在的社会环境中，其研究领域 包括从物理层到应用层的所有网络层面，以及各层之问的相互作用。如路由算法、移动 性管理、不使用g p s 的定位、节点相互协作的激励机制和安全策略等。由于移动自组 织网络的特性，国际标准化组织3 g p p ( t h i r dp a r t yp a m e r s h i pp r o j e c t ) ”j 和3 g p p 2 ( t h r i d p a r t yp a r t n e r s h i pe r o j e e t2 ) 【l6 】也已经开始将其作为下一代移动通信系统( 4 g ) 的一种应 用方案，并将其作为一项重要的标准化工作【l “”j 。 除此之外，目前国际上移动自组织网络研究方面比较活跃的机构包括一些著名高校 的研究机构，如康奈尔大学的无线网络实验室( w i r e l e s sn e t w o r k sl a b o r a t o r y ) 、马里兰大 学的移动计算与多媒体实验室( t h em o b i l ec o m p u t i n ga n dm u l t i m e d i al a b o r a t o r y ) 、加州 大学洛杉矶分校的无线自适应移动实验室( t h ew i r e l e s sa d a p t i v em o b i l i t yl a b ) 、伊利诺 斯大学u r b a n a - c h a m p a i g n 分校的自组织网络研究组( a dh o en e t w o r k sr e s e a r c hg r o u p ) 等，以及美国军方的一些研究机构。 1 1 3 移动白组织网络的应用 移动自组织网络的应用领域与传统的通信网络有着显著区别。这种类型的网络适用 于无法或不便预先敷设固定网络基础设施的场合、需要快速自动组网的场合等。针对自 组织网络的研究是因军事通信应用而发起的。因此，军事应用仍然是移动自组织网络最 主要的应用领域。同时，移动自组织网络在民用和商用领域也有着广阔的应用前景，它 可以支持移动会议、移动办公、抢险救灾、突发社会事件过程中的信息交换以及临时性 交互通信等。可以预测，移动自组织网络必将在未来的移动通信领域扮演极为重要的角 色。 军事通信 军事应用是移动自组织网络的主要应用领域。移动自组织网络特有的无需敷设固定 网络基础设施、可快速展丌以及抗毁性强等特点，使其成为遂行数字化战场通信的首选 技术。 自组织网络技术已经成为美军战术互联网( t a c t i c a li n t e m e t ) 的核心技术1 1 9 1 ；美军的近 第5 负 郑州人学硕i ：学位论文 期数字电台( n e a r - t e r md i g i t a lr a d i o ，n t d r ) 和无线互联网控制器等主要通信装备都使 用了自组织网络技术。我军很早就丌始移动自组织网络的研究，将其作为野战环境下我 军通信网络的重要组成部分。从“七五”后期丌始，“八五”、“九五”和“十五”期间 都下达了和移动自组织网络军事应用相关的研究课题。 移动商务 移动商务利用各种移动设备，通过无线网络收发信息，从而完成各种交换。它不是 当前有线网络中电子商务的简单模仿，由于移动商务的概念和商务活动无所不在的特点 有着天然的耦合性，因此移动商务必然会在不久的将来成为传统电子商务的有力竞争 者，向消费者提供无线信息服务、无线网络接入服务、基于位置信息的服务和数字化内 容服务。 移动会议 目前，越来越多的人携带笔记本电脑、个人数字助理等各种便携式设备参加各种会 议。如果与会者不用借助路由器、交换机或者基站等网络基础设施，就能够将各种移动 终端快速地组建成临时性自组织网络，从而完成提问、交流、资料分发等各种任务，无 疑将具有重要的实用意义。当在室外某个环境时，同样可以借助于移动自组织网络技术 来协同完成某项任务。 紧急和临时场合 当发生地震、水灾等自然灾害或者因为其它原因导致原有固定的通信网络基础设施 被破坏或无法f 常工作时，迅速恢复通信是非常重要的。借助于移动自组织网络技术， 救援人员可以快速构建起临时通信网络，从而为抢险救灾争取时间，减少损失。类似地， 在同样无法依赖固定或者预设的通信网络基础设施进行通信的偏远或者野外地域，移动 自组织网络是实现通信的最佳选择。 个人局域网 个人局域网是移动自组织网络技术的另一大应用领域。通过自组织网络技术，可以 实现p d a 、手机、笔记本电脑等个人电子通信设备之自j 的通信，蓝牙微网就是这种应用 的典型代表。 与移动通信系统的结合 自组织网络还可以与蜂窝移动通信系统相结合，利用移动节点的多跳转发能力扩大 蜂窝移动通信系统的网络覆盖范围，均衡相邻小区的业务流量、提高小区边缘的数据速 度等。 1 2a dh o e 网络路由技术研究热点 由于a d h o e 网络( 又称为m a n e t 网络，m o b i l e a d h o e n e t w o r k ) 具有广阔的应 用| j 景，它吸引了越来越多网络研究人员的关注。国际上对a dh o e 网络的研究早己成 第6 硪 郑州人学颀i ：学位论文 为无线计算机网络研究的热点，因此i n t e m e t 工程工作组( i e t f ) 也成立了m a n e tt 作小组，大量研究人员通过这个组织协作研究m a n e t 的路由协议等多方面内容。美国 加州大学洛杉矶分校的“无线自适应移动实验室”、康奈尔大学的“无线网络实验室”、 伊利诺基大学u r b a n a - c h a m p a i g n 分校的a dh o e 网络研究小组，马里兰大学的“移动计 算与多媒体实验室”都是m a n e t 研究比较活跃的研究团队。其它关注m a n e t 研究的 团队还包括美国陆军、海军和一些企业的研究机构。近几年来，国内各著名大学、科研 院所也相继加入了a dh o e 网络的研究行列，比如北京邮电大学、清华大学、国防科技 大学等，并己取得不少成果。总结国内外研究现状，a dh o e 网络的研究成果主要在以 下几个方面： ( 1 ) 现有a dh o e 网络的路由协议的研究与优化，包括对i e t f 的m a n e t 工作组 提出的m a n e t 路由协议草案和i 江c 进行研究并具体实现，构建实验和应用网络。目 前，在i e t f 网上，公布的r f c 文档有： m o b i l ea dh o en e t w o r k i n g ( m a n e t ) ：r o u t i n gp r o t o c o lp e r f o r m a n c ei s s u e sa n d e v a l u a t i o nc o n s i d e r a t i o n s ( r f c2 5 0 1 ) ( 2 8 9 1 2b y t e s ) a dh o eo nd e m a n dd i s t a n c ev e c t o r ( a o d v ) r o u t i n g ( r f c3 5 6 1 ) ( 9 0 3 5 6b y t e s ) o p t i m i z e dl i n ks t a t er o u t i n gp r o t o c o l ( r f c 3 6 2 6 ) ( 1 6 1 2 6 5b y t e s ) t o p o l o g yd i s s e m i n a t i o nb a s e do nr e v e r e p a t hf o r w a r d i n g ( t b r p f ) ( r f c3 6 8 4 ) ( 1 0 7 9 6 3b y t e s ) ( 2 ) 节能路由 在a dh o e 网络中，所有结点都依靠有限的电池能量操作。一旦电池耗尽，移动结 点将随即失效，并可能导致网络分割甚至不可用。虽然随着工业技术的进步，电池寿命 有所增加，但还远远满足不了需要。因此，在a dh o e 网络中有效的节省能量非常重要， 在协议栈的各个层次可以使用不同的方法来达到这个目的t 2 0 1 。目前网络层的节能路由协 议主要可分为两类：一是最小化传送包流的能量消耗率；二是最大化系统生存时间。 ( 3 ) 多播路由 在典型的a dh o e 环境中，网络结点按组工作以完成给定的任务，因此多播在a dh o e 网络中扮演了重要的角色2 2 1 。a dh o e 网络固有的资源的限制和结点移动性使得多播路 由协议的设计尤其具有挑战性。且前提出的多播路由协议有m a o d v , o d m r p , c a m p 等。 ， ( 4 ) 基于地理位置信息的路由 a dh o e 网络中节点的移动性给设计路由算法带来了很大的困难，而现在的定位技 术( 如g p s ) 已经比较先进。将二者结合，在自组网中利用位置信息，可以使节点在寻 找路由时避免简单的洪泛；利用相邻节点或目的节点的位置信息，可以提高路由寻找的 效率脚j 。典型的利用地理位置信息的路由协议有l a rg p s rd r e a m ，g r i d 等。 第7 页 郑州人学顾i ：学位论文 ( 5 ) 路由协议的安全性 由于a dh o e 网络利用无线信道传输信息，使得自组网比固定网络更容易遭到入侵 破坏。a dh o e 网络中对路由协议的攻击通常分为两类：路由破坏攻击和资源消耗攻击。 在路由破坏攻击中，攻击者通过发送伪造的路由包试图引起合法的数据包以紊乱的方式 被转发，而不能到达它们的目的地，如创建路由循环、路由黑洞等。在资源消耗攻击中， 攻击者向网络中插入包试图消耗宝贵的网络资源或结点资源。1 9 9 9 年1 月发布的r f c 2 5 0 1 明确提出，自组网路由协议必须提供安全机制。 ( 6 ) 多路径路由技术 大多数己提出的m a n e t 路由协议没有考虑公平性，它们倾向于把重的负载分布到 源一目的对的路径最短的主机上。结果，超重负载的主机会迅速耗尽能源，这将导致网 络分离，应用会话失败。多路径路由在有效使用带宽、对付拥塞和突发流量、增加传输 可靠性方面是有效的。多路径路由的目标是在源一目的对之间建立多条路径，要求更多 的主机来承担路由任务，它作为一个最短路径的替代而被提出用来分布流量，减轻拥塞。 在多路径路由中，流量通过多条路径分流传输到目标。换句话说，多路径路由是用多条 好的路径来代替单条最好的路径 2 4 1 。多路径路由可分为两大类：一类是在同一时刻对于 每个源一目的对只能在一个连接上发布流量，当这条路径中断时，可以用其他备用路径 来发送数据，一般称之为备份多路径：另一类是同时使用两条或两条以上的路径来传输 流量，一般称之为并行多路径。此外，还出现了一些安全多路径路由的研究。 ( 7 ) q o s 路由 在a dh o e 网络中，由于频繁的网络拓扑的改变和不准确的路由状态信息，使得选 择满足q o s 需求的路由是困难的但又是重要的。q o s 路由的工作包括两个方面：一是 选择一条能满足一定q o s 需求( 带宽、延迟、能量等) 的网络路径，二是提高网络资源 的利用率。广义的q o s 要求针对不同的业务需求，尽量提供最优的服务【2 5 】。典型的q o s 路由协议有c e d a r , q o s o l s r ，t b p 等。 1 3 主要工作与内容 a dh o e 网络不依赖于固定网络设施，网络组织灵活，节点不会因为移动到基站发 射距离之外而要越区切换，由于节点的发射距离有限，节点之间的通信往往要经过中间 节点转发，因而研究a dh o e 网络多跳路由十分必要。a dh o e 网络性能强烈的依赖于自 身的高度自组织性，节点的自组织带来了网络的网络结构到网络协议实现的复杂性。本 论文主要工作如下： ( 1 ) 全面研究a d h o e 网络的路由协议。 ( 2 ) 使用网络仿真软件n s 2 进行a d h o e 网络路有协议仿真。 ( 3 ) 选取四个网络性能评价参数( 延迟、包投递率、路由丌销、网络生存时自j ) 第8 负 郑州人学顾j ：学位论文 对四个典型的路由协议( a o d v ，d s r ，d s d v 和t o r a ) 进行仿真分析对比。特别是考 虑网络的生存时间，使仿真更接近现实，具有实际的参考意义。 ( 4 ) 提出基于能量有效选路的路由协议e e r p 。e e r p 能有效的延长网络生存时间， 在能量受限的网络中有较好的应用价值。并且在n s 2 上对比a o d v 对e e r p 进行仿真， 验证设计的正确性。 1 4 论文组织 论文按以下方式组织： 第一章绪论。介绍课题研究背景、a dh o c 网络路由技术研究热点、研究内容与主 要工作以及论文组织结构。 第二章无线a dh o 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 ev e c t o r ，目的节点序列距离矢量路由协议) 、 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 gp r o t o c o l ，a dh o c 网络按需距离矢量 路由协议) 、d s r ( d y n a m i cs o u r c er o u t i n gp r o t o c o l ，动念源路由协议) 、t o r a ( t e m p o r a r y o r d e r e dr o u t i n g a l g o r i t h m ，临时排序路由选择) 和z r p ( z o n er o u t i n gp r o t o c o l ，区域路由 协议) 等。分析比较了上述协议的特点及性能。 第三章a dh o e 路由协议仿真及性能研究。对几种典型的路由协议在网络仿真软件 n s 2 上进行仿真，并选取四个网络性能参数( 延迟、包投递率、路由丌销、网络生存时 间) 对结果数据进行分析。 第四章一种基于能量有效的a dh o c 网络路由协议。考虑到a dh o c 网络节点的能 量有限，为了延长网络的生存时间，我们在选择路由的时候应该有效的利用整个网络的 能量。本章主要介绍节能路由协议的度量标准，并提出基于能量有效选路的路由协议 ( e e r p ) 。e e r p 协议尽可能选择节点能量较多的路径，以达到延长网络生存时间的目 的。并于本章最后在n s 2 平台上对e e r p 和a o d v 进行仿真对比，验证设计的正确性。 第五章总结全文。分析研究工作中的关键技术，对课题研究工作进行总结，并提 出下一步的工作计划。 第9 页 郑州人学顾i ：学位论文 第二章无线a d h o c 网络路由技术 在a dh o c 网络环境中某一特定节点发出的应用数据包很有可能需要经过几个节点 才能到达目的节点。所有的节点都拥有自己的路由表，用以转发不以其为目的节点的网 络流量。 本章首先介绍传统路由协议的特点，然后分析其在a dh o c 网络中所面临的问题， 最后详细介绍常用a dh o e 网络路由协议。 2 1 路由概述 在o s i 参考模型中，网络层定义网络操作系统通信用的协议，为信息确定地址，把 逻辑地址和名字翻译成物理地址。它也确定从源节点到目标节点的路由选择，并处理业 务流问题，例如交换、路由和对数据分组阻塞的控制。网络层也许是o s i 参考模型中最 复杂的一层，部分原因在于，现有的各种通信子网事实上不遵循o s i 网络层服务定义。 同时，网络互联问题也为网络协议的制定增加了很大难度。 路由器的功能在网络层实现。路由器可以将子网连接在一起，它依赖于网络层将子 网之间的流量进行路由。数据链路层协议是相邻两直接连接节点自j 的通信协议，它不能 解决数据经过通信子网中多个转接节点的通信问题。设置网络层的主要目的就是要为数 据分组，以最佳路径通过通信子网到达目的节点提供服务，而网络用户不必关心网络的 拓扑结构与所使用的通信介质。路由是在i p 网络中用来实现分组的f 确转发的进程， 把信息从源穿过网络到目的的行为，在传输途中至少遇到一个中问节点。路由与桥接相 比，似乎完成同样的事，它们的主要区别在于桥接发生在o s i 参考模型的第2 层( 链路 层) ，而路由发生在第3 层( 网络层) 。这一区别使二者在传递信息的过程中使用不同的 信息，从而以不同的方式完成其任务。 2 1 1 路由算法的类型 首先，我们介绍t c p i p 网络中广泛采用的两种自适应路由协议。它的一些设计思 想被应用在许多网络中，包括a dh o e 网络。 一、距离矢量路由算法( d i s t a n c ev e c t o r a l g o r i t h m ，d v a ) 大部分路由协议是基于d b f ( d i s t r i b u t e db e l l m a nf o r d ) 和l s ( l i n ks t a t e ) 设计的。距 离矢量路由算法也称为b e l l m a n e sf o r d 算法和f o r df u l k e r s o n 算法，是根据丌发者的名 字命名的。它最初用于a 鼬) a n e t 路由协议中，并用于因特网的早期版本，称为r i p 。 由于d b f 具有分布式的特点，因此它简单而且计算效率较高，a dh o e 网络路由协议及 性能研究这是它的优势，但其路由收敛较慢，而且有形成环形路由的可能，因此不适合 拓扑高度变化的a dh o c 网络【2 6 】。虽然有些方案已解决了环形路由问题，但是到目的为 第1 0 ) i c 郑州人学颂i ：学位论文 止还没有解决d b f 收敛较慢这一难题。 1 d v a 的基本原理如下： 路由度量 在d v a 中，路由度量采用距离。距离表示本节点到达目的节点的地址所需的费用。 这个距离可以是跳数，或队列长度，或时延。 网络信息发布 周期性地向其邻居节点进行广播，发布的内容直接来源于本节点的路由表。经过相 互交换，每个节点获得网络中所有节点的距离信息。 路由选择 基于所获得的距离信息，以最短距离为标准，选择到信宿的下一跳节点。 路由表 每个节点维护一个路由表，表项包括信宿地址、到信宿下一跳、到信宿节点的费用 等表项。 2 限制路由更新丌销的技术： s p l i t h o r i z o n ( 水平分割) 。不向接收到路由更新信息的接口重复发送路由信息。 p o i s o nr e v e l s e ( 毒性翻转) 。路径崩溃后，最早广播此路径的路由i j 缀的代价标 记为无穷大，从而提高路由表构造算法的收敛速度。 t r i g g e r e d u p d a t e ( 触发更新) 。当路由器发现某个接口停止的事件发生时，它将立 即传送一个路由通告，说明原来提供一条无穷大距离的路经。 3 距离矢量路由算法存在问题： 第一由于延迟度量是队列长度，所以在选择路径的时候并没有考虑线路的带宽。当 然，将延迟度量做以下修改，把线路带宽作为一个因素考虑进去也是有可能的。但是第 二个问题依然存在，即距离矢量路由算法需要很长的时问才能收敛到稳定状态( 无穷计 数问题) 。由于这些原因，距离矢量路由算法被一个全新的算法所替代，该算法称为链 路状态路由算法。 二、链路状态路由算法( l i n ks t a t e a l g o r i t h m ，l s a ) 由于d b f 存在的问题，人们开始使用l s 。在l s 路由协议中，每个节点都维护着 一个全局拓扑结构表，因而很容易避免环形路由。而且链路的任何变化都会立即触发链 路更新，这样收敛到新的拓扑结构所需要的时间远远小于d b f 。但是l s 依靠泛洪去分 发路由更新信息，可能会带来过多的带宽丌销，特别是在链路变化频繁的无线a dh o e 网络中，大量的更新信息会占用相当多的宝贵带宽2 7 1 。在各种路由协议中，链路状态路 ，由算法得到了广泛应用。 1 l s a 基本思想 邻居节点发现与测试：各节点主动测试所有与之相邻的节点的状态。方法是周期性地 第1 l 页 郑州人学硕 ：学位论文 向邻居节点广播间断的查询报文，通过接收邻居节点的晌应报文来获取邻居的状态信 息。 2 链路状态信息发布 根据收集到的状态信息，构造一个包含所有邻居列表在内的分组l s ，并通过洪泛 法通告给算法作用域内的所有节点。为了保证消息的可靠发布，不同协议可能采用不同 的手段。例如，给每个分组标以3 2 位的顺序号和生存时间；一个链路状态分组洪泛到 一个节点时，并不立即发送，可在一