（通信与信息系统专业论文）移动ad+hoc网络中路由算法的研究.pdf

北京邮电大学硕士学位论文 摘要 移动a dh o e 网络中路由算法的研究 摘要 自上世纪9 0 年代以来，移动通信和移动终端技术均取得了飞跃式的发展， 但目前的移动通信系统大多需要有线基础设施( 如基站) 的支持才能实现。为了 能够在没有固定基站的地方进行通信，一种新的网络技术a dh o c 网络技术 应运而生。 m a n e t 网络( m o b i l ea d h o en e t w o r k ) 是由一组无线移动主机组成的一个无 需基础设施和集中管理设备的临时网络。m a n e t 网络作为一种新的组网方式， 由于其拓扑结构动态变化、带宽有限和主机能源有限等特点，传统的距离向量和 链路状态路由协议并不适用于该网络，因此建立良好的路由协议是构建m a n e t 网络的首要问题，同时也是当前m a n e t 网络研究中主要的热点和难点之一。 本文在路由协议方面，对现有的路由算法进行了详细的介绍和分析，并在此 基础上提出了一种新的源端多路由发现算法。全文分为五章，其中第一章介绍了 本文的研究背景和本文的主要工作。第二章集中地介绍了m a n e t 网络的概念， m a n e t 网络的特点、应用以及m a n e t 网络的关键技术。第三章重点介绍了目 前m a n e t 网络中路由算法的分类，详细介绍和分析了几种典型的路由算法，并 通过分析，比较了各类路由算法的优缺点。第四章针对m a n e t 网络的特点，在 d s r ( d y n a m i cs o u r c er o u t i n g ) 的基础上提出了一种新的m s r ( m u l t i - p a t hs o u r c e r o u t i n g ) 路由发现算法r r e q d m s r 算法，此算法旨在发现多条相关性最小 的路径，并在这些路径上进行业务最分配。仿真实验结果表明，与d s r 相比， 该算法可以有效地改进数据包的传输率和网络节点的负载均衡性。 最后，在第五章中展望了姒n e t 网络路由协议的研究方向，并针对研究中发 现的一些问题提出了下一步的工作。 【关键词】移动a d h o c 网络，路由算法，多路由 北京邮电大学硕士学位论文a b s t r a c t r e s e a r c ho n r o u t i n ga l g o r i t h m s i nm o b i l ea dh o cn e t w o r k a b s t r a c t m o b i l et e l e c o m m u n i c a t i o na n dm o b i l et e r m i n a lt e c i m o l o g i e sh a v eb e e n g o i n gu p r a p i d l ys i n c e 19 9 0 s p r e e x i s t i n gi n i a s 仃u c n l r e ( t h eb a s es t a t i o n f o r e x a m p l e ) i s n e c e s s a r yi nm o s t o ft h ec u r r e n tm o b i l et e l e c o m m u n i c a t i o ns y s t e m s a san e wk i n do f n e t w o r kt e c h n o l o g y , t h ea dh o cn e t w o r kt e c h n o l o g yc 趾e s t a b l i s han e t w o r ki nt h e c a s eo f l a c k i n gi ns t a t i o n a r yh l f a s 缸u c t i m o b i l ea dh o en e t w o r k s ( m a n e t ) a r es e l f - o r g a n i z i n gn e t w o r k st h a tc a nb e o r g a n i z e da n y w h e r ea n d a ta n yt i m ew i t h o u tt h ea i do f a n ye s t a b l i s h e di n f r a s t r u c t l l r e a n dc e n t r a l i z e da d m i n i s t r a t i o n b e c a u s eo fi t sc h a r a c t e r i s t i c ss u c ha s d y n a m i c t o p o l o g i c a l ，m u l t i h o pc o m m u n i c a t i o n ，l i m i t e db a n d w i d t ha n dl i m i t e de n e r g y i n m o b i l eh o s t s ，t r a d i t i o n a ld i s t a n c ev e c t o ra n dl i n ks t a t em u t i n g p r o t o c o l sa r en o ta d e p t t om a n e t a n ym o r e s om o s to ft h er e s e a r c hw o r k sa r ef o c u s e do nt h er o 砸n g a i g o f i t h m si nr e c e n t r e s e a r c h i nt h i sd i s s e r t a t i o n ，a f t e ra n a l y z i n ge x i s t e dm u t i n ga i g o r i t h m s ，an o v e lr o u 缸g d i s c o v e r ya l g o r i t h m i sp r o p o s e d t h i sd i s s e r t a t i o nc o n s i s t so ff i v ec h a p t e r s c h a p t e ri g i v e sb o t ht h eb a c k g r o u n do f t h er e s e a r c ha n dt h em a i nc o n t e n ti nt h i sd i s s e r t a t i o n c h a p t e r 2d e s c r i b e st h ec o n c e p t ，c h a r a c t e r i s t i c s ，a p p l i c a t i o n sa n dt h ek e yt e c h n o l o g i e s o f m a n e t c h a p t e r3p r e s e n t sap a r t i c u l a ra n a l y s i so nc u r r e n tr o u t i n ga l g o r i t h m s c h a p t e r4p r o p o s e san o v e lr o u t ed i s c o v e r ya i g o r i t h mo fm s r ( m u l t i p a t hs o u r c e r o u t i n g ) n a m e dr r e q d m s r f o rm a n e t t h er r e q d m s r a i g o r i t h mp r o p o s e sa m e t h o dt of i n dm u l t i p l ed i s j o i n tp a t h st h es a m et i m e p e r - p a c k e ta i i n c a t i o ns c h e m ei s u s e di nt h er r e q d m s rt od i s t r i b u t ed a t ap a c k e t si n t om u l t i p l ep a t h s s i m u l a t i o n r e s u l t ss h o wt h a tr r e q d m s ra l g o r i t h m c a n e f f i c i e n t l yi m p r o v e t h en e t w o r k r e s o u r c e su t i l i z a t i o nc o m p a r e dw i t ht h ed s r c h a p t e r5p r e s e n t sb o t ht h er e s e a r c ht r e n do nm a n e tr o 嘶n gp r o t o c o l sa n d s o m ei d e a st oi m p r o v et h ep e r f o r m a n c e so f r r e q d m s ri nt h ef u t u r e k e y w o r d s m a n e t , r o u t i n g a l g o r i t h m s ，m u l t i - p a t hr o u t i n g - i i - 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均己在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：日期： 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：日期： 导师签名：日期 北京邮电大学硕士学位论文 第一章绪论 1 1 引言 第一章绪论 随着人们对移动通信要求的增强，蜂窝移动通信系统得n - ；迅速普及。但蜂 窝移动通信系统是集中式控制的( 有中心的) ，网络的运行要基于预先架设好的网 络设施。这使得蜂窝移动通信系统对有些特殊场合来说并不适用，例如，战场上 部队快速展开和推进、发生地震或水灾后的营救。这些场合的通信不能依赖于任 何预先架设的网络设施，基于健壮性考虑也不能采取有中心的控制方式。此时， 需要一种特殊的通信系统，这种通信系统的运行不能基于任何预先架设好的网络 设施，要能实现l | 缶时快速自动组网，节点要能移动。m a n e t 网络的出现满足了 这些要求。 m a n e t 网络的起源可以追溯到1 9 6 8 年的a l o h a 网络和1 9 7 3 年d a r p a 开始研究的分组无线电网络。a l o h a 网络协议支持单跳网络( 网络中的每一个 节点都可以到达其它所有的节点) 的分布式信道接入，1 9 7 3 年d a r p a 开始研究 多跳的分组无线网络协议。成立于1 9 9 1 年5 月的i e e e 8 0 2 1 1 标准委员会采用了 “a dh o e 网络”一词来描述这种特殊的无线通信网络，i e t f 则将a dh o e 网络 称为移动a dh o e 网络。19 9 7 年i e t f 成立了m a n e t ( m o b i l ea dh o en e t w o r k ) 工 作组，专门负责对具有数百个节点的m a n e t 网络的路由算法的研究，并制定了 相应的标准。 m a n e t 网络可以看作是移动通信和计算机网络的交叉。在m a n e t 网络中， 一方面使用计算机网络的分组交换机制；另一方面，通信的主机一般是便携式计 算机、个人数字助理( p d a ) 等移动终端设备。 1 2m a n e t 网络研究热点 自上世纪九十年代以来，m a n e t 网络的研究在世界范围内方兴未艾，已经 从无线通信领域中的一个小分支逐渐扩大到相对较独立的领域。许多标准化组织 和研究机构对m a n e t 网络做了各方面的研究。总结国内外研究现状，m a n e t 网络的研究成果主要集中在以下几个方面： 北京邮电大学硕士学位论文 第一章绪论 ( 1 ) 提出新的路由协议。目前，一般普遍得到认可的代表性成果有d s d v 、 w r p 、a o d v 、d s r 、t o r a 和z r p 等。源头性的创新性研究主要集中在2 0 0 1 年以前，后续的成果多为这些协议的改进。路由协议的研究仍然是当前m a n e t 网络研究成果中最为集中的部分，不过这些协议离实用性还有一定的距离。 ( 2 ) 提出基于m a n e t 网络的媒体按入控制( m a c ) 协议。主要是解决隐藏 终端和暴露终端问题，影响比较大的有m a c a 协议，即r t s c t s a c k 方案、 控制信道和数据信道分裂的双信道方案和基于定向天线的m a c 协议，以及一些 改进类的m a c 协议。有一些研究则是侧重于将i e e e8 0 2 1 l 的m a c 协议移植 到m a n e t 网络中。基于定向天线的m a c 协议虽然在理论上性能较为优越，但 在技术实现上难度较大。 ( 3 ) m a n e t 网络与蜂窝移动通信网的互联互通。文献 2 4 】 2 5 】 2 6 】研究并提出 了一种i c a r ( i n t e m e t c e l l u l a ra n d a d h o c r e l a y ) 系统，提供蜂窝小区内信号的 补盲。该方案给出了在加入补盲点之后系统性能改善的性能评价，从结果来看， 该系统只是针对目前的2 g 系统，尚无法和基于口方式的分组网络互联。最近， 文献 2 7 】提出了一种在蜂窝网上覆盖一个无线多跳网络的方案，其中用一些无线 路由器来代替蜂窝网络中的一些节点。该结构与 2 4 】 2 5 2 6 】所提基本一致，该结 构通过优化路由、信道规划和功率控制等方法，使系统在发射功率受限的情况下 达到系统吞吐量最大化，其他方面没有太多的贡献。 ( 4 ) 基于m a n e t 网络的多播组播协议、t c p 协议、地址分配、功率控制、安 全性问题、分布式算法、q o s 等方面有一些研究成果，但各部分的数量相对较少。 ( 5 ) 国内学者所发表的m a n e t 网络的研究成果较少。从2 0 0 1 年起开始有少 量成果发表，主要成果基本上集中在路由协议的一些改进，少量成果涉及m a c 协议的研究。 ( 6 ) 标准化问题。这里所说的标准主要涉及物理层到网络层。目前m a n e t 网络还没有相应的标准，只有涉及路由协议的相关草案。标准的制定对于 m a n e t 网络的推广使用有着重要的作用。有了标准，来自不同厂商的移动终端 之间才有互联组网的基础，开放性的产品之间才有竞争性，才有批量生产的可能， 从而降低其成本和价格。 北京邮电大学硕士学位论文 第一章绪论 1 3 研究k 舳n e t 网络活跃的机构 目前，国际上在m a n e t 网络方面研究较为活跃的几个研究机构有： ( 1 ) 加州大学洛杉矶分校m a r i og e r l a 教授所领导的“无线自适应移动性实验 室”( t h e w a m ( w i r e l e s s a d a p t i v em o b i l i t y ) l a b ) 。研究方向包括m a n e t 网络 路由协议、多播协议、多跳网络q o s 、m a c 协议、功率控制、蓝牙网络等。 ( 2 ) 康奈尔大学z y g m u n tj h a s s 教授所领导的“无线网络实验室”( t h e w i r e l e s sn e t w o r k sl a b o r a t o 啪。研究方向包括m a n e t 网络重构、m a c 协议、 路由协议、网络安全等。 ( 3 ) 伊利诺基大学u r b a n a - c h a m p a i g n 分校n i t i n v a i d a y a 教授所领导的m a n e t 网络研究小组( 现在伊利诺大学u r b a n a - c h a m p a i g n 分校e c e 系) 。研究方向包 括m a n e t 网络的定向m a c 协议、定向路由协议、网络调度等。 ( 4 ) 马里兰大学s a t i s hk t d p a t h i 教授所领导的“移动计算与多媒体实验室” ( 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 ) ，研究方向包括m a n e t 网 络路由协议、q o s 等。 ( 5 ) j n , ) q 。i 大学圣巴巴拉分校e l i z a b e t h m b e l d i n g - r o y e r 教授所领导的“移动性 管理和网络实验室”( t h e m o b i l i t y m a n a g e m e n t a n d n e t w o r k i n g l a ”。研究方向包 括m a n e t 网络路由协议、多播协议、地址重构、安全性、q o s 、可伸缩性和适 应性等。 ( 6 ) 加州大学圣克鲁兹分校j j g a r c i a - l u n a - a e 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 n sr e s e a r c hg r o u p ) 。研究方向主要包 括无线网络的信道接入等。 其他比较活跃的机构还包括美国陆军、海军和一些企业的研究机构。 1 4 本文的主要工作 目前m a n e t 网络路由协议仍是m a n e t 网络的研究热点之一，本文针对 现有的m a n e t 网络路由协议做了详尽的分析，在此基础上提出了一种新的源端 多路由发现算法，并做了计算机仿真研究，仿真实验结果表明，与d s r 相比， 该算法可以有效地改进数据包的传输率和网络节点的负载均衡性。 北京邮电大学硕士学位论文第一章绪论 本论文的各章节具体介绍了以下内容： 第二章主要介绍了m a n e t 网络的概念、m a n e t 网络的特点、应用以及其 中的关键技术。 第三章首先介绍了目前m a n e t 网络中路由算法的分类和几种典型算法，其 中重点介绍了目前关注最多的按需驱动型算法d s r 、a o d v ，并分析比较了各类 算法的优缺点；接着分析当前多路由算法的研究情况，指出基于d s r 的几个多 路由算法由于控制信息包比较多，导致最后得到的多路由相关性不强的问题，并 以此指出了本文研究的切入点。 第四章主要描述了我们提出的r r e q d m s r 算法。它是一种源端多路由算 法，通过对r r e q d m s r 算法进行计算机模拟仿真，仿真实验结果表明，与d s r 相比而言，r r e q d m s r 算法能够提高数据包的传输率和网络的负载均衡性。 第五章展望了m a n e t 网络路由协议的未来研究方向，并针对研究中发现的一 些问题提出了下一步的工作。 北京邮电大学硕士学位论文 第二章m a n e t 网络及其关键技术 第二章m a n e t 网络及其关键技术 移动a dh o e 网络( m a n e t ) 是由无线移动节点构成的自组织网络。本章比 较详细地介绍了m a n e t 网络的概念、m a n e t 网络的特点、m a n e t 网络应用 以及其中的关键技术。 2 1 1m a n e t 网络概念 移动a dh o e 网络( m a n e t ) 是一种由若干工作于无固定结构的环境下的移 动节点所临时组建的无中心结构专用无线网络。在m a n e t 网络中，没有基站、 路由器那样的静态网络结构，所有节点都可以随机自由移动，其阿络拓扑结构是 动态变化的。如图2 1 所示，在m a n e t 网络中，每一个节点兼备主机和路由器 两种角色，这些节点作为同等实体相互连接，实现信息包的转发，它们都参与路 由的发现和维护过程，从而构成了一个m a n e t 网络。与有中心网络相比， m a n e t 网络有良好的鲁棒性和健壮性，不需要提供固定的基础设施，用户就可 以建立和操作分组无线网络。 图2 - 1m a n e t 网络结构 在m a n e t 网络中，每一个移动节点都有自己的无线收发器，使之可以在一 北京邮电大学硕士学位论文 第二章m a n e t 网络及其关键技术 定范围内与其它节点通信，一个节点也可以同时配备几个收发装置，使得它可以 连接在固定网络上，成为与固定网络联接的一个接口。除非采用了间接通信机制， 否则一个节点是无法与在其通信范围之外的其它节点通信的。节点间的通信可以 通过一个节点链来实现，链上的相邻节点是可以直接通信的，数据可以沿着这条 链路以“多跳”的方式进行传输。因此所有节点都必须具备路由和转发数据的功 能。m a n e t 网络可以不必在路由层进行手工配置，它是自发地建立连接的。而 且，m a n e t 网络的路由层具备当节点移动导致拓扑结构变化时重新配置路由的 能力。 2 1 2m a n e t 网络的特点 在原有的网络构架技术中，移动无线通信网络通常包括蜂窝移动通信网和无 线局域网。蜂窝移动通信网中，移动终端接入固定网络是基于基站的中心接入方 式：而无线局域网则是通过接入点( a p ) 完成终端接入固定网络的。这两种网 络都是单跳网络。a dh o c 技术所标称的是一种有别于中心接入和单跳的特征、 强调多跳和无中心接入的网络，移动终端不仅具有主机的功能，还具有路由器的 功能。 在任一时刻，m a n e t 网络中由一些带有无线收发装置的移动节点间都可以 通过无线信道连接形成一个网状的拓扑结构。节点移动时，网络拓扑结构也随之 发生变化。在这种环境中，由于终端的无线通信覆盖范围的有限性，两个无法直 接通信的用户终端可以借助其它终端的分组转发机制进行数据通信。它可以在没 有或不便利用现有的网络基础设施的情况下提供一种通信支撑环境，从而拓宽了 移动通信网络的应用环境。 由此可以看出，与其他通信网络相比，基于a dh o e 技术的m a n e t 网络具 有以下特征： ( 1 ) n 络的自组性。m a n e t 网络可以在任何时刻任何地方构建，而不需要现 有的信息基础网络设施的支持。它是一个可以自由移动的通信网络。 ( 2 ) 动态变化的网络拓丰卜结构。m a n e t 网络中，从网络层来看，移动用户可 以以在网中自由移动，加上无线发送装置发送功率的变化、无线信道间的相互干 扰、地形因素等的影响，节点间通过无线信道形成的网络拓扑结构随时都会发生 北京邮电大学硕士学位论文 第二章m a n e t 网络及其关键技术 变化。 ( 3 ) 有限的无线传输带宽。无线信道本身的物理特性使m a n e t 网络的网络 带宽相对有线方式要低得多，另外还要考虑无线信道竞争时所产生的信号衰落、 碰撞、阻塞、噪声干扰等因素，这使得实际带宽要比理论带宽小许多。 ( 4 ) 移动终端的有限性。m a n e t 网络中的移动用户终端内存小、c p u 处理 能力低、所带电源有限等特点使得m a n e t 网络的设计更加困难。 ( 5 ) 安全性差。m a n e t 网络结构采用的是一种无线方式的分布式结构，所以 更加容易被窃听、入侵、遭受网络攻击和拒绝服务等。 ( 6 ) 网络的分布式。m a n e t 网络中的移动节点兼有路由器和主机的功能。不 存在类似于基站的网络中心控制点。网络中节点地位平等，采用分布式控制方式， 具有较强的网络健壮性。 ( 7 ) i n 络的可扩展性不强。i n t e m e t 由于采用了t c p i p 协议中的子网技术而具 有较好的可扩展性，而m a n e t 网络动态变化的拓扑结构使得子网技术所带来的 网络可扩展性不能得到应用。 ( 8 ) 单向无线信道的存在。m a n e t 网络采用无线信道通信，由于地形环境或 发射功率等因素的影响，可能产生单向无线信道 ( 9 ) 生存时间短。组网通常是由于某个特定原因而临时创建的，使用结束后， 网络将会自动消失。m a n e t 网络相对于圆定网络而言其生存时间是短暂的。 m a n e t 网络可以看作是移动通信和计算机网络的交叉。这一点在m a n e t 网络中的体现是：一方面，网络的信息采用了计算机网络中的分组交换机制；另 一方面，用户终端是便携式的，比如笔记本电脑、p d a 、掌上电脑、车载台等， 并配置有相应的无线收发设各，可以在网内自由移动。 2 1 3m a n e t 网络的应用 “a dh o e ”这一词语来源于拉丁语，字面意思是“为特定目的或场合的”或 “仅为这种情况的”。m a n e t 网络在过去主要用于战场或者灾区这些无法或不 便于预先铺设网络设施的场合。现在随着无线技术的成熟，m a n e t 网络的商用 前景也越来越被看好，各种便携设备如笔记本、移动电话、p d a 、m p 3 播放器 都可以用在m a n e t 网络中进行互联。可以预测，m a n e t 网络在未来移动通信 北京邮电大学硕士学位论文 第二章m a n e t 网络及其关键技术 的市场上将扮演非常重要的角色。m a n e t 网络潜在的应用很多，可分为以下几 类： ( 1 ) 移动会议：在室外临时环境中，工作团体的所有成员可以通过a dh o c 方 式组成一个临时网络来协同完成一项大的任务，或协同完成某个计算任务。在室 内办公环境中，办公人员携带的装备了a d h o c 收发器的p d a 可以通过无线方式 自动从台式机上下载电子邮件，更新工作日程表等。 ( 2 ) 家庭网关：通过移动联网的方式把办公室的办公环境延伸到家庭，必要 时在家庭办公。或者利用我们随身携带的个人无线a dh o c 设各与装备了a dh o c 收发器的家庭电器通信，自动完成开锁、开灯、打开娱乐设备、调节空调等操作。 ( 3 ) 紧急服务：由于停电或其他灾害出现，网络基础设施遭到破坏时，组建 一个m a n e t 网络，可以帮助紧急救援人员完成必要的通信工作。 ( 4 ) 传感器网络：最近，人们开始关注大量分布的传感器协调工作问题。传 感器可以工作在危险的环境( 如化学有害物质泄漏现场) ，通过在传感器上装备 位置指示器、a d h o c 收发器等，将传感器所在现场的信息传送到危险现场以外， 避免救援人员进入现场，收集和辨别事故信息。 ( 5 ) 个人域网络：通过m a n e t 网络把个人通信、娱乐、办公等设备联网， 这些设备可以或不需要与因特网相连，但在执行用户的某项活动时肯定需要彼此 通信，在这种情况下，移动性不是主要问题。 ( 6 ) 军事无线通信：在现代化战场上，各种军事车辆之间、士兵之间、士兵 与军事车辆之间都需要保持密切的联系，以完成集中指挥，协调作战。这样的通 信网络是一种典型的m a n e t 网络。据报道，在最近的伊拉克战争中，m a n e t 网络已经得到有效的应用。 ( 7 ) 其他商业应用：如未来装备a dh o c 收发设备的机场预约和登机系统可以 自动地与乘客携带的个人无线a dh o c 设备通信，完成目前的换登机牌等手续。 商场内商品上面的廉价r f 标签可以通过无线接口由a dh o c 设备动态刷新，顾 客若携带手持无线设备。可以很容易地找到某种商品和价格。n c r 公司已经生 产了这种设备。 以下介绍一个m a n e t 网络在军事上的研究与应用实例f 自愈式雷场系 统”。系统采用智能化的移动反坦克地雷阵来挫败敌人对地雷防线的突破。这些 北京邮电大学硕士学位论文第二章m a n e t 网络及其关键技术 地雷均配备无线通信与自组织联网单元，布撒之后迅速构成m a n e t 网络。在遭 到敌方坦克突破之后，这种地雷通过对拓扑结构的判断以及自动弹跳功能迅速 “自愈”，即通过网络重构恢复连通。如此反复，直到系统无法重构为止，最后 自行引爆。 2 2m a n e t 网络关键技术 与传统的有线和蜂窝网络相比，m a n e t 网络没有基础设施，每个节点都可 能随时进入和离开网络，整个网络分布式运行。然而，传统网络中对连接性和业 务传输的基本需求，在m a n e t 中也同样需要得到满足。以上介绍的关于m a n e t 网络的特点决定了网络研究中的主要难点问题有路由协议、媒体接入控n ( m a c ) 协议、接入技术、节点定位、节点的功率控制、移动性管理、服务质量、网络管 理和网络安全等问题。 2 2 1 路由协议 良好的路由协议是建立m a n e t 网络的首要条件，同时也是m a n e t 网络 研究中主要的热点和难点之一。传统的距离向量和链路状态路由协议并不适用于 拓扑结构高度动态变化的m a n e t 网络。理想的m a n e t 网络的路由协议应该 具有以下性能：分布式运行、无环路、按需运行、考虑安全性、高效地利用电池 能量、支持单向链路、维护多条路由等。图2 - 2 描绘了由网络自身特点所决定的 m a n e t 网络路由协议所具有的特点。 北京邮电大学硕士学位论文第二章m a n e t 网络及其关键技术 拓扑变t 出快速反 自态性强， 络不可预 路由技术 更新路由信 冒栗篙薹黟( 效率是关箍用不同算法“”“” 需要多种算法 常常共享链路 引起过多开销 控制传输参数 集成多种功能于一体的算法，1 ￥，而且可能会破坏分层系统结 图2 - 2m a n e t 网络路由协议的特点 m a n e t 网络的路由协议可以分为表驱动路由和源发起按需路由两大类。在 表驱动路由协议中，每个节点试图维护到所有已知目的节点的路由表，节点之间 采用两种方式来交换路由信息，一种是周期性交换路由信息，另一种是在网络拓 扑结构发生变化时交换路由信息。在表驱动路由协议中，源节点能够立即判断目 的节点的可达性，获得路由的延迟较小，但消费了较多的网络资源，此外还浪费 了一些资源来建立和重建那些根本没有被使用的路由。在按需路由协议中，节点 不需要花费资源来维护无用的路由，但路由发现过程费用比较昂贵而且不可预 测；与表驱动路由协议中恒定的查表时间相比，路由延迟更加多变。 目前表驱动路由协议中d s d v 研究的比较多，按需路由协议中研究较多的 有d s r 、a o d v 和t o r a 。其中d s r 路由协议已经在装有i e e e 8 0 2 i lw a v e l a n 卡的笔记本电脑组成的m a n e t 网络中得以实现。此外还有一些多播路由协议， 但是所有路由协议至今还没有一个能完全符合m a n e t 的要求。 本文主要针对路由算法做了大量的研究工作，以下几章还有详细的论述。 2 2 2 媒体接入控制( m a c ) 协议 媒体接入控制协议主要分为以下五类： ( 1 ) 基于单信道的m a c 协议 基于单信道的m a n e t 网络信道接入协议用于只有一个共享性信道的m a n e t 北京邮电大学硕士学位论文 第二章m a n e t 网络及其关键技术 网络。所有的控制报文和数据报文都在同一个信道上发送和接收。受传播时延、 隐终端和节点移动等因素的影响。单信道的m a n e t 网络中有可能发生控制报文之 间、控制报文和数据报文之间、数据报文之间的冲突。一般而言，数据报文要比 控制报文长得多，数据报文的冲突会严重影响信道的利用率，所以这种信道接入 协议的主要目标之一就是通过使用控制报文尽量减少甚至消除数据报文的冲突。 典型的基于单信道的m a n e t 网络信道接入协议有c s m a c a 、m a c a 、m a c a w 等 ( 2 ) 基于双信道的m a c 协议 基于双信道的m a n e t 网络信道接入协议用于有两个共享信道的m a n e t 网络。 两个信道分别为控制信道和数据信道。控制信道只传送控制报文，而数据信道只 传送数据报文。因为使用了两个不同的信道，控制报文不会与数据报文发生冲突。 通过适当的控制机制，可以完全消除隐终端和暴露终端的问题。d b t m a ( d u a lb u s y t o n em u l t i p l ea c c e s s ) 协议将信道分为两个子信道：控制报文( r t s c t s ) 在 控制信道上传输，另外在控制信道上增加了两个彼此频带分开的窄带忙音b t r ( 接收忙音) 和b t t ( 发送忙音) ，分别用来指示某站正在数据信道上接收和发 送数据。 ( 3 ) 基于多信道的m a c 协议 基于多信道m a n e t 网络信道接入协议用于具有多个信道的m a n e t 网络，由于 网络中有多个信道，相邻的结点可以使用不同的信道进行通信，在使用多信道的 情况下，接入控制更加灵活，可以使用其中一个信道作为公共控制信道，也可以 让控制报文和数据报文在一个信道上混合传送。 ( 4 ) 具有节能作用的m a c 协议 以上讨论的几种m a c 协议的目标都是减少分组冲突、消除隐终端和暴露终端 以及改善信道接入的公平性，但是他们都没有考虑如何减少终端的能耗问题。为 此提出了p a m a s ( p o w e ra w a r em u l t i - a c c e s sp r o t o c o lw i t hs i g n a l i n g ) 协议， 它的目标是在解决信道接入问题的基础上尽量节约能量。在m a n e t 网络中，由于 使用的是无线广播信道，处于发送范围内的站点都能接收到发送信号，但是实际 的接收者只有一个，因此造成了电能的很大浪费，p a m a s 协议的特点是当节点没 有处于发送或接受状态时，智能地将节点关闭，以节省节点功率的消耗。 北京邮电大学硕士学位论文 第二章m a n e t 网络及其关键技术 ( 5 ) 定向m a c 协议 此类协议主要有o r t s - - o c t s 协议( 使用波速切换天线) 、d r t s - - o c t s 协议、 d r t s d c t s 协议( 使用自适应天线) 和多跳r t s 协议。 2 2 3 接入技术 利用i n t e m e t 上的固定路由器作为外部代理以及m a n e t 网络的接入网关， 通过改进的移动d 协议可以实现m a n e t 网络和i n t e m e t 网络的互联。其中，可 以利用隧道机制实现移动节点和固定外部代理之间的互联，也可以将m a n e t 网络看作i n t e m e t 的一个子网，对它进行统一的网络编址和默认路由计算，还可 以利用移动节点间相互竞争产生的中心节点作为代理，通过该中心代理实现 m a n e t 网络和i n t e m e t 的互联，这种方案既不需要对传统的移动i p 协议进行大 的改进，还可以保证接入的灵活性以及m a n e t 网络的自组性和整体移动性。此 外，该方法还用于具有不同内部路由协议的多个m a n e t 网络的同时接入。 2 2 4 节点定位 在m a n e t 网络中，节点是自由移动的，因而准确快速的定位就显得至关重 要。通常可以采用g p s 进行室外的有效定位，而在室内的定位一般采用短距离 无线电和红外传感器。 在没有g p s 或g p s 不可用的情况下，也可以采用s p a ( s e l f p o s i t i o na l g o r i t h m ) 定位移动节点 3 0 】。s p a 利用节点间的距离信息建立网络坐标系统( n c s ) ，它可 以提供足够的定位信息和精度。具体算法如下：首先，节点测量到它所有邻节点 的距离，并将该信息发给其所有邻节点；然后节点建立它的本地坐标系统( l c s ) ， 并计算邻节点在l c s 中的位置；接下来节点计算它的n 跳邻节点个数。具有最 多n 跳邻节点个数的节点就组成定位基准组，另外还要计算n c s 的中心和方向； 最后，各个节点分别计算它们的n c s 的位置。 在m a n e t 网络中，通过获取准确、实时的定位信息，可以进行更有效的路 由，如l a r 、g r i d 等协议可以完成本功能。 北京邮电大学硕士学位论文 第二章m a n e t 网络及其关键技术 2 2 5 节点的功率控制 节点的功率控制问题涉及无线网络中的各层。节点功率控制可以分为通信费 用和计算费用两部分。通信费用是指无线网络接口消费的能量。在m a n e t 网络 中，移动节点可以处于发射、接收和空闲( 旁路) 三种模式，其中发射模式的功率 消费最大，空闲模式的功率消费最小，缺省模式为空闲模式。计算费用指协议处 理方面消费的能量。通常在这两者之间存在一个折衷，降低通信费用的技术可能 增加计算费用，反之亦然。 在目的端能正确接收分组的前提下，减少节点的能量消费可以延长节点和网 络的寿命；减少对邻居节点的干扰，提高网络的吞吐量；减少数据被窃听的可能 性，提高通信的安全性。 硬件层次的技术，如低功率的c p u 、显示器和能量有效的算法等都得到了 应用；在物理层可以通过调整节点的发射功率来减少网络的能量消费；m a c 层 的主要措施是减少数据发送的冲突，避免重传和使节点进入睡眠状态：在网络层 可以采用功率控制路由算法，而不是以最短跳数和最小延迟作为路由度量。 2 2 6 移动性管理 m a n e t 网络不需要固定基础设施支撑，不需要预先配置主机，节点具有高 度的移动性。因此，如何快速有效地组织和管理移动终端也成为人们关注的焦点。 下面将讨论m a n e t 网络移动性管理的三种方法。 ( 1 ) 自适应分群 m c d o n a l d 等人提出了自适应分群的网络框架，将m a n e t 网络中的节点动 态分群。该分群策略的基本思想是：利用( q ，t ) 的分群算法( ( a ，t ) 表示路径在t 内 的可用概率至少为旺) ，同时，还采用了群路由算法，其中包括群间路由算法和 群内路由算法。采用这种自适应分群的网络框架，可以对m a n e t 网络中的节点 进行有效的组织和管理。 另外，还可以通过对基于最小i d 分群算法的移动分群算法和分群保持策略 实现m a n e t 网络的快速部署和自适应跟踪拓扑变化。其中，利用重叠群方案来 实现分群大小的优化和增加每个节点的最大通信容量，同时还利用了智能网关控 北京邮电大学硕士学位论文第：章m a n e t 网络及其关键技术 制协议来提高网络的信道利用率。 ( 2 ) v h r 算法 t e r m i n o d e 组织致力于t e r m i n o d e ( t e r m i n a l + n o d e ) 项目的研究 3 0 】【3 l 】，采用 了v h r ( v i a u a lh o m er e g i o n ) 算法管理移动终端。移动性管理由三部分执行： t l r 、l d a 和定位机制。t l r ( t e r m i n o d e l o c a lr o u t i n g ) 能够在转发节点的附近跟 踪目的节点；l d a ( l o c a t i o n - d e p e n d e n ta d d r e s s ) 管理要能够在m a n e t 网络内以 动态、范围可变、安全和公平的方式发送定位信息；同时要求在会话中的主机能 够相互跟踪彼此的定位信息。定位机制主要包括基于定时的定位更新机制、基于 距离的定位更新机制和基于距离的定位预测机制；其中，基于定时的定位更新机 制规定，每个节点周期性地将其定位更新信息发送给v h r 。而基于距离的定位 更新机制则规定，每个节点从上一次更新时就要跟踪它移动的距离。在基于距离 的定位预测机制中，节点要向v h r 报告其位置和移动速度，通过得到这些信息， 就可以预测节点的位置。 ( 3 ) 移动终端激励机制 在t e r m i n o d e 项目的研究中，还采用了一种移动终端相互协作的激励算法， 即虚拟货币的机制。该机制假定每个终端节点初始时就具有虚拟货币，每个节点 对给其提供服务的节点必须支付虚拟货币。以转发分组作为节点提供的服务为 例，该服务可以由源节点或目的节点付费均可。由发送分组的源节点支付虚拟货 币的方法称为p a c k e t p u r s e m o d e l ( p p m ) ，而由接收分组的目的节点支付虚拟货币 的方法称为p a c k e tt r a d e m o d e l 口r m ) 。 2 2 7 服务质量q o s q o s 是指当源端向目的端发送分组流时，网络向用户保证提供一组满足预先 定义的服务性能约束，如端到端的延迟、带宽、分组丢失率等。显然，为了提供 q o s 保证，首要的任务就是在源和目的节点之间寻找一条满足q o s 要求的路由， 其次，对于特定的流，一旦路由被选择后，必须为该流预留必要的资源( 如带宽、 路由器中的缓存空间等) 。可以提供通过选择路由来满足q o s 要求，这样q o s 保 证问题就转换为提供q o s 路由的问题。 图2 3 给出一个简单的m a n e t 网络中支持q o s 路由的例子，节点a 想与 北京邮电大学