（信号与信息处理专业论文）基于时延的融合网络路由技术的研究.pdf

南京邮电大学2 0 0 5 级硕士研究生学位论文摘要 摘要 a d h o c 网络自其诞生以来，就以其无需固定基础设施支持即可实现便捷有效通信的优 异特性，广泛应用于军事和民用领域。随着研究的不断深入，a dh o c 技术越来越显现着其 独特的魅力，它已经开始被当作下一代移动通信网络的一种应用方案。a dh o e 网络与蜂窝 网络融合就是其中的一大研究热点。a d h o c 网络和传统蜂窝网技术的互补性以及通信频率 的不相关性使得两种网络的融合成为可能并相得益彰。因此，a dh o e 和蜂窝网的融合技术 已受到越来越多专家和学者的关注。 融合网络互联首先要解决的问题是路由协议的问题，a o d v + 是一种融合网络的路由协 议，它包括a o d v 路由协议和基站发现机制，由于a o d v 协议本身的时延性能，a o d v + 仅仅传输一些“尽力而为 ( b e s t e f o r t s ) 等级的业务。随着网络的发展和用户需求的不断提 高，一些业务不仅要求能够通信，同时要求网络能够在时延、带宽等方面提供保证，以保 证这些特殊业务的开展。于是本文提出了基于时延的融合网络的路由方案，通过加入一些 时延限制来提高a o d v + 路由协议的时延特性。基于n s 2 ，本文实现了改进的协议并进行 了一系列的仿真，证明了此方案可以很好的改善a o d v + 的时延性能并没有引入很大的开 销。 关键字：a dh o e 网络，蜂窝网，融合网络，路由协议，时延 南京邮i 乜人学2 0 0 5 级帧i j 研究生学位论义a b s t r a c t a b s t r a c t a dh o cn e t w o r kh a sb e e na p p l i e dw i d e l yi n m i l i t a r ya n dc i v i la r e a ss i n c ei te m e r g e d ， b e c a u s ei tc a ns u p p o r te f f e c t i v ea n dc o n v e n i e n tc o m m u n i c a t i o nw i t h o u ta n yi n f r a s t r u c t u r e s w i t h f u r t h e rr e s e a r c h e so na dh o c ，a dh o ct e c h n o l o g yh a sm o r ea n dm o r ea d v a n t a g e sa n di sa p p l i e d i nt h en e x tg e n e r a t i o nw i r e l e s sm o b i l en e t w o r k ，t h ei n t e g r a t i o no fa dh o cn e t w o r kw i t hc e l l u l a r n e t w o r ki sah o ts p o to ft h er e s e a r c h e s t h ei n t e g r a t i o ni sf e a s i b l ea n dp r o f i t a b l eb e c a u s eo f c o m p l e m e n t a r yt e c h n o l o g i e sa n di r r e l e v a n tc o m m u n i c a t i o nf r e q u e n c yb a n d su s e db yt w o n e t w o r k s a sa l lt h er e a s o n sa b o v e ，m o r ea n dm o r er e s e a r c h e sa r ef o c u s i n go nh y b r i dn e t w o r k s t u d y o n eo ft h ep r i m a r yc o n c e r n si n h y b r i dn e t w o r kr e s e a r c hl i e s i n i t sr o u t i n gp r o t o c o l s a o d v + h y b r i dr o u t i n gp r o t o c o li st h ee x t e n s i o no fa o d vr o u t i n gp r o t o c o l ，i tc o n t a i n sa o d v r o u t i n gp r o t o c o la n db a s es t a t i o nd i s c o v e r ym e c h a n i s m b e c a u s eo ft h eb a dd e l a yp e r f o r m a n c eo f a o d v ，a o d v + c a no n l yt r a n s p o r ts o m e “b e s t e f f o r t s ”t r a f f i c s w i t hb o t ht h ed e v e l o p m e n to f n e t w o r ka n dt h ei n c r e a s e m e n to fu s e r s r e q u i r e m e n t ，s o m et r a f f i c sn o t o n l yr e q u i r et h e a v a i l a b i l i t yo fc o m m u n i c a t i o n ，b u ta l s on e e ds u p p o r ti ns o m ep e r f o r m a n c e ss u c ha sd e l a ya n d b a n d w i d t ht od e v e l o pt h e m i nt h i sa r t i c l e ，ah y b r i dn e t w o r k r o u t i n gm e c h a n i s mb a s e do nd e l a y i sb r o u g h tf o r w a r d ，i ti m p r o v e st h ed e l a yp e r f o r m a n c eo fa o d v + h y b r i dr o u t i n gp r o t o c o lb y a d d i n gs o m ed e l a yl i m i t s t h ed e l a yl i m i t e dp r o t o c o li si m p l e m e n t e di nn s 2a n dp r o v e dt h i s m e c h a n i s mc a ni m p r o v et h ed e l a yp e r f o r m a n c eal o ti n h y b r i dn e t w o r kb u to n l ya d dl i t t l e o v e r h e a d k e yw o r d s ：a dh o c ；c e l l u l a rn e t w o r k ；h y b r i dn e t w o r k ；r o u t i n gp r o t o c o l ；d e l a y i l 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：狃亟墨五日期：2 盟型笪 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：馘 1 哆? 导师签名：二弓乙日期：导师签名：芝 弘日期： 南京邮电大学2 0 0 5 级硕1 j 研究生学位论文第一章绪论 1 1a dh o e 网络简介 第一章绪论 a dh o c 网络( m a n e t ) ，是指一组带有无线收发装置的移动节点组成的多跳自组织系 统。整个网络没有固定的基础设施，也没有特定的路由器。网络内的所有节点地位平等， 它们既是终端又是路由器。网络的拓扑结构是动态变化的，其内部节点可以以任何方式动 态地保持与其他节点的联系。这种无中心又不依赖固有的基础设施的结构使得它的组网十 分方便快捷。因此特别适用于某些特殊紧急场合，如：战时出现重要线路故障需要临时进 行无线联络，灾难现场营救及医院急诊等。a dh o e 网络的典型结构如图1 1 所示。 甚苫 a ：一。t 、 摹：f 巨p 阻曩台 1 2 蜂窝网络简介 巨 l k 。夕| 壹g 车载台。 ( a ) 物理网络结构 l c b ) 逻辑网络结构 图1 1 a dh o c 网络经典结构 蜂窝网络是最重要和最基本的一种无线移动通信方式。它把一个城市按蜂窝网形状划 分成若干互相靠近的六角形区( c e l l ) ，在蜂窝的中心设立无线电基站( b s ) ，区内所有移 动终端( m s ) 可以单跳接入基站与其他移动终端联系。 全向天线辐射的覆盖区是个圆形。为了不留空隙地覆盖整个平面的服务区，一个个圆 形辐射区之间一定含有很多的交叠。在考虑了交叠之后，实际上每个辐射区的有效覆盖区 是一个多边形。可以证明，要用币多边形无空隙、无重叠地覆盖一个平面的区域，可取的 形状只有f 三角形、正方形和正六边形这三种。在辐射半径r 相同的条件下，计算出三种 形状小区的邻区距离、小区面积、交叠区宽度和交叠区面积就可以知道，在服务区面积一 致d c 南京邮l 乜人学2 0 0 5 级顺卜研究生学位论文 “ 第一章绪论 定的情况下，正六边形小区的形状最接近理想的圆形，用它覆盖整个服务区所需的基站数 最少，也就最经济。正六边形构成的网络形同蜂窝，因此把小区形状为六边形的小区制移 动通信网称为蜂窝网。但实际的小区形状与正六边形小区有很大的不同，它取决于地形、 建筑物的分布、天线的方向性和辐射功率等因素影响。 采用正六边形的蜂窝状小区来实现区域覆盖的主要目的是实现所谓频率( 或信道) 再 用，即在不同的小区内使用相同的频率，提高频率利用率，以便扩大服务范围，增加系统 的通信容量。然而事情并非如此，由于无线信道的开放特点，在相邻小区工作于同一频道 的电台之问会产生相互干扰，这种干扰称为同频道干扰。为了保证通信质量，信号与干扰 的功率比必须大于某一个门限值。在频分多址( f d m a ) 情况下，同一频率不可能应用于 相邻小区，必须间隔一定空间距离，或者说跳过若干小区后，同一频率才能再用。为了实 现这一点，将若干相邻的小区组成一个区群。区群内的各个小区使用不同的频率组，而每 个区群能够使用所提供的全部无线频道。用相同频率配置的区群来覆盖整个服务区，就实 现了频率再用。 图1 2 示出了频率再用的含义。由7 个小区( a 、b 、c 、d 、e 、f 、g ) 构成1 个区群。 小区8 与小区l 均使用a 频道( 或频道组) ，再用距离为d = 3 ，- = 2 1 ，。 图1 2 频率复用示意图 频率再用是蜂窝系统的重要概念，也是蜂窝系统的显著特征。为了实现频率再用，除 了正确的频率配置外，在小区内应限制基站发射功率。为此，蜂窝系统普遍使用功率控制 技术，避免过大的发射功率对同频道小区造成干扰。在蜂窝通信系统设计中，一般均规定 信号与同频道干扰比的门限值。 蜂窝移动系统的另一个重要特征是越区切换。将服务区域划分成小区所带来的一个很 自然的问题是并非所有的移动中通话都能在单个小区内完成，例如，一辆快速行驶的汽车 在一次通话中可能通过若干小区。移动节点在小区范围内用所分配的频率与基站建立了无 2 南京邮电大学2 0 0 5 级硕l - 研究生学位论文第一章绪论 线链路，通过基站连接到移动交换中心，然后再连接到公用网或其它小区的基站。当移动 节点从一个小区进入相邻的小区时，其频道( 或信道) 是不同的，这就需要在一次通话过 程中将移动节点的工作频率和接续控制从其离开的小区交换给正在进入的小区，这个过程 就称为越区切换。越区切换是在系统控制下完成的，用户往往是感觉不出来的。当移动节 点到达小区边界附近时，该小区基站能测试出移动节点信号变弱，而相邻小区基站能测试 到这个移动节点信号逐步变强。移动交换中心收集到有关基站传送来的信息，便可做出判 决。当需要进行越区切换时，系统就发出相应的指令，正在越过边界的移动节点就将工作 频率和无线链路从一个小区切换到另一个小区，整个切换都是自动完成的，也不会影响正 在进行的通话。 蜂窝系统的第三个特征是小区分裂。用小区分裂的方式可增加系统的容量。当用户数 增加并达到每个小区所能提供服务的最大数量时，在一定服务质量前提下，可以采取把小 区分割成更小的蜂窝状区域，并使用频率再用模式。同时在新小区基站必须降低发射功率 以减小共道干扰。理论上讲，一旦新的小区所能支持的用户数又达到饱和，还可将这些小 区进一步分裂。但实际上，小区半径过小时，基站位置受限，往往会偏离理想位置。另外， 小区半径过小，过境切换频繁，系统的复杂性和服务质量将受影响。一般说来，小区半径 越小，基站数量越多，系统的容量也就越大。目前，在用户密集的市区，蜂窝系统正向微 蜂窝发展，其半径仅达数百米。 1 3 融合网络分析 在原有蜂窝网的基础上，处于蜂窝网中的移动节点可以通过a dh o e 的方式进行相互 通信，利用a dh o c 网络的特点来有效地解决现有蜂窝系统的一些难题。首先，现有蜂窝 网络中总存在一些覆盖缺点，被称为“死区 ，在蜂窝系统中引入自组织的方式，可以弥 补这些覆盖缺点，这是蜂窝网络和a dh o e 网络结合的首要原因。其次，流量转移也是在 蜂窝系统中引入a dh o c 的一个重要原因。流量转移可以缓解热点区域因为容量饱和而造 成的呼叫阻塞和切换断链，a dh o e 网络中的动态中继转发功能可以有效的调整热点区域的 流量，实现流量的动态分配，提高热点小区的服务能力和服务质量。第三，支持a dh o c 网络后，在蜂窝系统中引入一种新的通信方式“局域网 方式。该方式至少能带来两 个好处：一是对于近在咫尺的局部业务可以直达或经数跳可达；二是当没有基础设施支持 或基础设施毁坏( 例如灾后救援) 时依然可以支持一定程度的通信。从这三点可以看出， 蜂窝网络和a dh o e 网络相结合后的无线网络具有许多性能优势，因而也成为目前移动通 南京邮电大学2 0 0 5 级侦i j 研究生学位论文第一章绪论 信领域研究的热点。 1 4 本文主要工作和章节安排 本文重点研究了a dh o c 网络和蜂窝网络融合的一种新的基于时延的路由方案。论文 从a dh o c 网络路由协议的研究，相关路由的改进，n s 的仿真，性能分析等方面进行了深 入的探讨研究和新的尝试。 第一章介绍了a dh o c 网络、传统蜂窝网络和融合网络；第二章较为详细的介绍了现 有的对a dh o c 网络路由协议的相关研究，主要可以分成五类路由协议，先验式路由协议， 反应式路由协议，利用地理位置信息的路由协议，q o s 路由协议和功率感知的路由协议； 第三章首先简要地介绍了几种融合体系结构，包括c a m a ，i c a r ，u c a n ，m c n ，p a r c e l s ， m a c a ，a g s m ，s p h i n x 和s o p r a n o ，接着详细介绍了三种融合网络的路由技术：d a r p 、 m s g p r 和a o d v + ：第四章针对a o d v + 协议提出了一种新的基于时延的融合网络路由方 案，并就时延问题进行了分析；第五章在n s 下对原a o d v + 程序进行了优化并给出了优 化日 后a o d v + 的性能比较：第六章对全文进行了总结并指出了未来的工作重点。 4 南京邮电大学2 0 0 5 级硕上研究生学位论文第二章a dh o c 网络路由协议 第二章a dh o e 网络路由协议 2 1a dh o e 网络路由协议概述 a dh o e 网络是由一组具有路由功能的节点组成的分布式无线自组织网络，它不依靠任 何预设的网络基础设施。因为多跳网络中节点的传输范围有限，源节点在向目的节点发送 数据时，通常需要其他节点的辅助，所以路由协议是a dh o c 网络中不可缺少的一部分。 路由协议的主要设计目标是：满足应用需求的同时尽量降低网络开销，取得资源利用的整 体有效性，扩大网络的吞吐量。其中，应用需求一般包括时延、时延抖动、丢包率等诸多 因素。 a dh o e 网络中的路由协议主要包括路径产生、路径选择和路径维护三项核心功能。其 中，路径产生是指根掘集中式或分布式的网络状态信息和用户业务需求生成路径，网络状 态信息和用户业务信息选择最适当的路径，路径产生和路径维护这两项功能通常合在一起 称为路由发现。路径维护是指对所选路径进行维护。由于a dh o e 网络是一种没有预设基 础设施的网络，它工作于无线环境，通信带宽受限，而且节点具有移动性，因此，路由协 议还必须充分考虑这些因素所造成的影响。路由协议的定义和功能见图2 1 。 业务要求 多跳网络特性 无线链路 + 点移动性 无网络基础设施 网络能力 路由功能 路径产生 路径选择 路径维护 图2 1 路由协议的定义和功能 多跳网络的路由协议采用了许多独特的技术方法，用以解决关键技术问题。这些技术 问题主要包括一下几个方面： 1 ) 路由环路避免问题 按照路由协议所依据的基本路由算法不同，a dh o e 网络路由协议可分为基于链路 状态( l s ) 的路由协议、基于距离矢量( d v ) 的路由协议、源路由( s r ) 协议和反向 南京邮电人学2 0 0 5 级颂l ：研究生擎位论文第二章a dh o e 网络路由协议 链路( l r ) 协议。 在源路由协议中，由于路由信息标记在数据消息和路由控制消息的头部，本身具 有环路避免的特性。反向链路协议又包括全链路翻转和部分链路翻转两种作法。由于 有向无环图( d a g ) 具有无环路特性，在网络稳定的情况下，不会出现路由问题；链 路状态协议是在得到全部网络拓扑信息的条件下进行路由计算的，所以也不会产生环 路问题。而对于距离矢量路由协议，由于控制消息经过不同的路径，在网络中的时延 不同，如果采用过期的控制消息进行路由计算，很可能产生环路问题。所以在距离矢 量路由协议中，路由环路问题称为一个关键性问题。 信息标识技术是一种解决路由环路的技术。在路由协议中，每一个消息可用二元 组( 源节点，序列号) 来唯一标识。其中的序列号是在源节点中与时间相关的惟一值， 序列号越高，消息越新。消息在路由过程中，会受到网络延迟、阻塞和链路通断的影 响，因此在到达目的节点时，会发生顺序颠倒和重复，而消息标识就是用来保证过滤 重复消息和有序处理消息。信息标识技术不仅可以应用来标识消息，也可以标识一个 路由项等。在d s d v 和a o d v 协议中，每个距离向量都带有一个直接序列信息标识， 以确定距离向量生成顺序，解决路由环路问题。 2 ) 控制开销问题 路由开销是衡量多跳网络路由协议性能的重要指标。路由开销可以用单位时间内路 由控制消息的传输量来表示，它是网络拓扑结构变化率的函数。a dh o c 网络路由协议 的设计过程就是一个路由优化的过程，即在满足消息传输要求的基础上尽量减少路由 开销，从而提高网络的吞吐量。路由协议设计和优化的基本思想如下： 减少路由协议的开销，从而提高网络的有效吞吐量。 提高路由消息的利用效率，从有限的信息中，发现更多有价值的网络状态信 息。 采用自适应设计方法，根据网络状态，动态调整路由协议及其参数。 解决路由协议的控制丌销问题，有以下几种典型方法。 1 、多点中继技术 在许多路由协议中，都显式或隐式地采用了洪泛技术。提高洪泛效率，减少洪 泛丌销，是优化路由协议的有效途径。按照网络最小生成树进行有选择的广播是 洪泛的最优方式，这样可以避免广播冲突和重复广播。要计算网络最小生成树， 就必须要知道整个网络的拓扑结构，而这在许多情况下是不现实的。但是，通过 局部链路状态信息交换可获得局部区域的网络拓扑结构，进而可以计算出局域生 6 南京邮电人学2 0 0 5 级硕i j i j 究生学位论文第二二章a dh o c 网络路由协议 成树。沿着局部生成树进行消息广播，可以用最小的网络丌销将消息传送到局部 区域的边界节点。链路状态消息不断地按局部生成树向外扩散，最终扩散到全网， 其路由开销比纯洪泛方式小。当局部区域被限制为两跳时，该技术被称为“多点 中继( m u l t i p o i n tr e l a y ) 技术，o l s r 路由就是使用了该方法对链路信息的洪泛 进行优化。 2 、多范围技术 在大规模的网络中，受传播时延和节点移动性的影响，距离节点越远的链路状 态信息准确性越差，对路由计算的意义越小。因此，路由协议应当区别对待不同 距离的链路状态信息。多范围的涵义是：针对某个节点而言，距离自己越远的节 点，了解到关于它的路由信息应当越模糊；相反，距离自己越近的节点，了解到 的关于它的路由信息应当越精确。这样可以达到降低路由协议控制开销的目的。 f s r 协议通过模仿鱼眼“对距离越近的物体看得越清楚的生理特性，对不同距 离范围内的链路状态信息采用了不同的更新频率，在g s r 的基础上进一步降低 了路由协议的控制丌销。 3 、增量消息技术 节点向邻居节点报告拓扑信息、路由表信息、邻接关系等信息时，只报告对应 信息的变化部分，而不是每次都将全部信息报告给邻居节点。这样，可以减少控 制消息的长度，从而降低开销。这种技术在d s d v 协议上得到广泛应用。 3 ) 对网络动态性的适应问题 网络拓扑的动态性是a dh o c 网络和固定的i n t e m e t 的一个重要区别。网络的高度动态 性必将导致路由失败。在网络动态变化十分剧烈的时候，路由只能通过洪泛来实现。但是， 在网络的动态变化不太剧烈的情况下，通常有3 种方法对失效路由进行维护：备份路由、 路由失效点通知源节点重新计算路由和在路由失效节点进行局部路由修复。 在i n t e m e t 路由协议中，当节点间的链路发生变化时，其设计思想是以最快的速度将该 变化通知到网络中的其他节点，并重新调整和计算最短路由。链路状念变化越快，由此引 起的路由开销就越大。在多跳网络中，更适合采用局部修复技术，将这种变化限制在一个 局部区域内。 不同的路由协议，所采用的具体技术也不同。在a b r 中，当源节点到目的节点的路径 发生中断时，整个路径并不需要立即重新建立，而是试图从中断节点开始，查找合适的路 径，修复断开的链路。在t o r a 路由协议中，链路的通断，会引起局部节点高度的调整， 从而将变化约束在一个小的区域内。局部链路修复技术实际上是放弃了对最优路径的追 南京邮电大学2 0 0 5 级硕上研究生学位论文 第二章a dh o c 网络路由协议 求，而更注重在保持路由连通性的前提下，减少路由开销，缩短路由恢复时间。 2 2a dh o c 网络路由协议的分类 2 2 1 先验式路由协议 先验式路由协议又被称为表驱动路由协议，是一种基于表格的路由协议。在这种路由 协议中，每个节点维护一张包含到达节点的路由信息的表格，并根据网络拓扑的变化随时 更新路由表，所以路由表可以准确地反映网络的拓扑结构，源节点一旦要发送报文，可以 立即获得到达目的节点的路由。不同的先验式路由协议的区别在于拓扑更新消息在网络中 传播的方式和需要存储的表的类型。先验式路由协议不断地检测网络拓扑和链路质量地变 化，根据这些变化更新路由表，因此路由表可以准确地反映网络的拓扑结构。图2 2 就是 现有的部分先验式路由协议。 图2 2 先验式路由协议 1 ) 目的序号距离矢量协议d s d v ( d e s t i n a t i o ns e q u e n c ed i s t a n c e v e c t o r ) d s d v 协议是一种距离矢量路由协议，利用目的节点序列号来解决d b f 算法的路由环 路和无穷计数问题。 在d s d v 中，每个节点保存一张路由表，路由表维护本节点到网络内部所有可达的目 的节点的路由。路由条目中保存目的节点的序列号，用以区别新旧路由。为维护路由表， 节点周期性的广播路由更新消息。收到路由更新消息后，节点比较其中的目的节点序列号 和自己保存的同一目的节点的序列号，如果前者大，就更新自己的路由；如果路由序列号 相同，则选择具有较少跳数的路由。路由更新消息要延迟一段时间发送，以防止路由表的 波动。 2 ) 无线路由协议w r p ( w i r e l e s sr o u t i n gp r o t o c 0 1 ) 8 南京邮电大学2 0 0 5 级硕 j 研究生学位论文 第二章a dh o c 网络路由协汉 w r p 也是距离矢量路由协议。每个节点都维持一个距离表、路由表、链路开销表和报 文重传表，节点通过获得邻居节点的状态变化信息来维护自己的信息表，并通知邻节点； 收到来自邻节点的信息后，要更改保存的信息表。由于无线链路特性或网络拥塞，更新消 息有可能丢失或者过期，需要采用重传机制来保证更新消息的可靠传输。当节点正确的接 收到更新消息时，需要发送一个回复消息说明已经收到并处理了某个更新消息。如果节点 没有转发数据或是更新消息，则要定期的发送h e l l o 消息，以确保节点间的连通性。发 送两个h e l l o 消息之间的间隔时间成为h e l l o i n t e r v a l 。节点在一段时间内没收到邻节点发 送的任何消息，就认为和该邻节点间的链路失败。新节点加入网络时，如果某个节点收到 了新节点h e l l o 消息，则把新节点信息填入信息表中，并且把它自己保存的信息发送给 新节点。w r p 通过记录到目的节点的距离信息和先驱节点信息，解决了路由环路问题。所 谓先驱节点就是指所选的到目的节点的路由上，目的节点的前一个节点，也成为“倒数第 二跳”( s e c o n d t o 1 a s th o p ) 节点。这种方法的特点是当检测到任意相邻节点变化时，则检 查所有相邻节点的坚固性以消除回路，具有较快的收敛性。 3 ) 群首网关交换路由协议c g s r ( c l u s t e r g a t e w a ys w i t c hr o u t i n gp r o t o c 0 1 ) c g s r 协议是一种先验式的分群路由协议，它基于基本的d s d v 协议并对其进行了修 改，以提高扩展性。在c g s r 使用的网络模型中，网络被划分为重叠的群，在每个群中选 出一个群首，管理群中的其他成员，控制对信道的访问，进行路由及带宽分配等等。所有 在群首通信范围一跳内的节点都属于该群，在两个以上群首通信范围一跳内的节点称为网 关节点，两个群首不能直接通信，必须通过网关节点。这样，一个群众就有3 类节点：一 个群首、一个或多个网关节点及零个或多个普通节点。c g s r 路由协议与d s d v 不同之处 在于：只有群首和网关节点才能转发消息，减少了路由中涉及的节点个数。 4 ) 全局状态路由协议g s r ( g o b a ls t a t er o u t i n g ) g s r 是链路状态路由协议，路由表的信息每个节点存储邻居列表、拓扑表、下一跳表 和距离表4 张表格，仅维护邻节点的状态信息( 这意味着该路由信息变化不是很大) ，即 下一跳节点和信息时间戳。路由表的更新邻节点的链路状态改变则立即更新。在移动性较 强且带宽有限时，该算法更好。g s r 与d s d v 类似，但节点收到请求信息后，在转发请求 信息包前将自己的地址填写到请求信息数据包的路由中。如果发现自己的地址已经存在， 就把该请求信息包丢弃。避免了信息洪泛。但该算法需要传播的路由信息数量随网络节点 的增多呈指数级增长。 5 ) 鱼眼状态路由协议f s r ( f i s h e y es t a t er o u t i n g ) f s r 协议是对g s r 协议进行了改造。f s r 协议综合采用了距离矢量和链路状态两种 9 南京邮电大学2 0 0 5 级烦i ：研究生学位论文第二章a 6h o c 网络路由协 义 协议的思想。它使用了“鱼眼 ( f i s h e y e ) 技术，模仿鱼眼的功能，通过对不同距离的节 点采用不同的路由更新频率，使得距离越近的节点，掌握的路由信息越准确。另外，它的 路由更新消息仅在邻节点之i 日j 交换，减少了用于路由控制丌销。模仿鱼眼的生理特性，f s r 协议采用了以下作法：一是划分节点不同层次的鱼眼范围( s c o p eo f f i s h e y e ) ，二是在不同 的鱼眼范围内采用不同的路由更新频率，由此维护远近不同精度的路由信息。f s r 采用周 期性发送链路状态信息消息的方法来更新路由表。鱼眼的范围不同，路由的更新频率也不 同，鱼眼范围越小，其路由更新频率越高，这样可以大大降低路由的开销。 6 ) h s r ( h i e r a r c h i c a ls t a t er o u t i n g ) h s r 协议是一种用于分级网络的路由协议，它基于组移动模型将网络中的节点划分为 不同的组，每个组形成一个逻辑子网。h s r 协议不仅根据节点的物理位置使用分布式分群 思想划分物理分群，动态生成节点的物理层次地址，以决定数据消息的转发路径，而且还 根据节点的逻辑地址对其位置进行管理。在每个逻辑子网内至少存在一个归属代理( h o m e a g e n t ) ，负责管理本子网内节点逻辑地址与当前物理地址之间的对应关系，并为所管理的 节点转发数据消息。节点需要向归属代理进行注册，通告最新的物理地址。 7 ) 分层链路状态路由协议z h l s ( z o n e b a s e dh i e r a r c h i c a ll i n ks t a t e ) z h l s 路由协议是一种基于区域的路由协议。网络被分割成不重叠的区域，区域与群 不同，它没有首领。并定义了两级拓扑：节点级和区域级。节点级拓扑指一个区域内的节 点的物理连接。区域级拓扑指各个区域如何互相连接。网络中存在两种链路状态报文：节 点链路状态报文和区域链路状态报文。节点链路状态报文包含节点的邻居信息，只在区域 内传播。区域链路状态报文包含区域问的链路状态，在全网中传播。通过分区可以减少路 由控制报文的个数。 8 ) o l s r ( o p t i m i z e dl i n ks t a t er o u t i n 9 1 o l s r 协议也是一种链路状态路由协议，是对纯链路状态算法进行优化而形成的。它 采用m p r ( m u l t i p o i n tr e l a y s ) 机制减小了控制消息的洪泛范围。o l s r 对纯链路状念算法所 做的优化有：( 1 ) 采用多点中继机制减小了控制消息的洪泛范围；( 2 ) 缩减了控制消息 的大小。节点周期地交换信息来维护网络拓扑，协议还要求每一个节点保护它到网络中所 有可达地目的节点地路由，因此它特别适用于网络舰模大、节点分布密集地网络。 2 2 2 反应式路由协议 反应式路由协议，又称为按需路生l ( o nd e m a n dr o u t i n g ) 协议，是一种当需要时才查找 l o 南京邮电大学2 0 0 5 级硕士研究生学位论文第二章a dh o c 网络路由协议 路由的路由选择方式。节点不需要维护及时准确的路由信息，当需要发送数据时才发起路 由查找过程。为了提高效率，节点可以将找到的路由保存在缓存中供后续发送使用。图2 3 就是现有的部分反应式路由协议。 图2 3 反应式路由协议 1 ) 按需驱动距离矢量路由协议a o d v a o d v 是由n o k i a 研究中心的c h a r l e se p e r k i n s 和加利福尼亚大学s a n t ab a r b a r a 的 e l i z a b e t hm b e l d i n g r o r y e r 以及c i n c i n n a t i 大学s a m i rr d a s 等共同开发，已经被i e t f m a n e t 工作组于2 0 0 3 年7 月正式公布为自组网路由协议的r f c 标准。a o d v 在每个中 间节点隐式保存了路由请求和应答的结果，并利用扩展环搜索的办法来限制搜索发现过的 目的节点的范围。a o d v 通过建立基于按需路由来减少路由广播的次数，而且源路由并不 需要包括在每一个数据消息中，这样会使路由协议的_ 丌销有所降低。a o d v 协议可以实现 在移动终端间动态的、自发的路由，使移动终端很快获得通向所需目的的路由，同时又不 用维护当前没有使用的路由信息，并且还能很快对断链的拓扑变化做出反应。a o d v 的操 作是无环路的，在避免了通常b e l l m a n f o r d 算法的无穷计数问题的同时，还提供了很快的 收敛速度。a o d v 的路由表中每个项都使用了目的序列号( d e s t i n a t i o ns e q u e n c e n u m b e r ) 。 目的序列号是目的节点创建，并在发给源节点的路由信息中使用的。使用目的序列号可以 避免环路的发生。 a o d v 使用三种消息作为控制信息：r o u t e r e q u e s t ( r r e q ) ，r o u t e r e p l y ( r r e p ) 和 r o u t e e r r o r ( r e r r ) 。 当源节点需要和目的节点通信时，如果在路由表中已经存在了对应的路由时，a o d v 不会迸行任何操作。当源节点需要和新的目的通信时，它就会发起路由发现过程，通过广 播r r e q 信息束查找相应路由。当这个r r e q 到达目的节点本身，或者是一个拥有足够新 的到目的节点路由的中间节点时，路由就可以确定了。所谓“足够新 就是通过目的序列 南京邮电人学2 0 0 5 级顾i j 研究生学位论文第二章a dh o c 网络路由协议 号来判断的。目的节点或中间节点通过原路返回一个r r e p 信息来向源节点确定路由的可 用性。在维护路由表的过程中，当路由不再被使用时，节点就会从路由表中删除相应的项。 同时，节点会监视一个活动路由( a c t i v e r o u t e ，有限跳的，可用于数据转发的路由表) 中，下 一跳节点的状况。当发现有链路断开的情况时，节点就会使用r e r r 通知上游的节点，而 上游的节点就会使用该r e r r 消息拷贝通知更上游的节点。在r e r r 消息中，指明了由于 断链而导致无法达到目的节点。每个节点都保留了一个“前驱列表”( p r e c u r s o rl i s t ) 来帮助 完成错误报告的功能，这个列表中保存了把自己作为到当前不可达节点的下一跳的相邻节 点( 可以通过记录r e r r 很容易地获得) 。在路由表中，针对每一个表项，需要记录相应的 的特征内容。其中，序列号是防止路由环路的关键所在。当发生断链时，通过增加序列号 和度量值( 跳数) 来使路由表项无效。 ( 室) a o d v 路由协议的运行方式： ( a ) a o d v 路由发现 a o d v 路由协议是一种典型的按需驱动路由协议，该算法可被称为纯粹的需求路由获 取系统，那些不在活跃路径上的节点不会维持任何相关路由信息，也不会参与任何周期路 由表的交换。此外，节点没有必要去发现和维持到另一节点的路由，除非这两个节点需要 进行通信。移动节点间的局部连接性可以通过几种方法得到，其中包括使用局部广播h e l l o 消息。这种算法的主要目的是：在需要时广播路由发现消息一般的拓扑维护：区别局部连 接管理( 邻居检测) 和一般的拓扑维护；向需要连接信息的邻居移动节点散播拓扑变化信息。 a o d v 使用广播路由发现机制，它依赖中间节点动态建立路由表来进行消息的传送。为了 维持节点间的最新路由信息，a o d v 使用了序列号的思想，利用这种机制就能有效地防止 路由环的形成。当源节点想与另外一个节点通信，而它的路由表中又没有相应的路由信息 时，它就会发起路由发现过程。每一个节点维持两个独立的计数器：节点序列号计数器和 广播标识。源节点通过向自己的邻居广播r r e q ( r o u t er e q u e s t s ) 消息束发起一次路由发现 过程。 ( b ) 反向路由的建立 在尉砸q 消息中包含了两个序列号：源节点序列号和源节点所知道的最新的目的序列 号。源节点序列号用于维持到源的反向路由的特性，目的序列号表明了到目的地的最新路 由。当p d 王e q 消息从一个源节点转发到不同的目的地时，沿途所经过的节点都要自动建立 到源节点的反向路由。节点通过记录收到的第一个r r e q 消息的邻居地址来建立反向路由， 这些反向路由将会维持一定时间，一该段时间足够r r e q 消息在网内转发以及产生的 r r e p 消息返回源节点。当刚也q 消息到达了目的节点，目的节点就会产生r r e p 消息， 1 2 南京邮电大学2 0 0 5 级硕l j 研究生学位论文第二章a dh o c 网络路由协议 并利用建立的反向路由来转发r r e p 。 ( c ) 正向路由的建立 r r e q 消息最终将到达一个节点，该节点可能就是目的节点，或者这个节点有到达目 的节点的路由。如果这个中问节点有到达目的的路由项，它就会比较路由项旱的目的序列 号和r r e q 消息里的目的序列号的大小来判断自己已有的路由是否是比较新的。如果 r r e q 消息早的目的序列号比路由项中的序列号大，则这个中间节点不能使用已有的路由 来响应这个r r e q 消息，只能是继续广播这个r r e q 消息。中间节点只有在路由项中的目 的序列号不小于r r e q 中的目的序列号时，才能直接对收到的r r e q 消息做出响应。如果 节点有到目的地的最新路由，而且这个r r e q 还没有被处理过，这个节点将会沿着建立的 反向路由返回r r e p 消息。 在r r e p 转发回源节点的过程中，沿着这条路径上的每一个节点都将建立到目的节点 的同向路由，也就是记录下r r e p 是从哪一个邻居节点来的地址，然后更新有关源和目的 路由的定时器信息以及记录下r r e p 中目的节点的最新序列号。对于那些建立了反向路由， 但r r e p 消息并没有经过的节点，它们中建立的反向路由将会在一定时间 a c t i v e r o u t e t i m e o u t ) 后自动变为无效。收到r r e p 消息的节点将会对到某一个源节点的 第一个r r e p 消息进行转发，对于其后收到的到同一个源的r r e p 消息，只有当后到的 r r e p 消息中包含了更高的目的序列号或虽然有相同的目的序列号但所经过的跳数较少 时，节点才一会重新更新路由信息，以及把这个r r e p 消息转发出去。这种方法有效地抑 制了向源节点转发的r r e p 消息数，而且确保了最新及最快的路由信息。源节点将在收到 第一个r r e p 消息后，就丌始向目的节点发送数据消息。如果以后源节点了解到的更新的 路由，它就会更新自己的路由信息。 a o d v 路由表的管理 节点的路由中除了存储源和目的节点的序列号外，还存储了其他有用的信息，这些信 息成为有关路由项的软状态。与反向路由相关的是路由请求定时器，这些定时器的目的是 清除一定时间内没有使用的反向路由项。定时器的设置依赖于自组网的规模大小，与路由 表相联系的另外一个重要的参数是路由缓存时间，即在超过这个时间之后，对应的路由表 就变为无效。 此外，在每一个路由表中，还要记录本节点用于转发消息的活跃邻居。如果节点在最 近一次活跃期间( a c t i v e t i m e o u t ) 发起或转发了到某个目的节点的消息，那么就可以称这个 节点为活跃节点。这样，当到达某一个目的节点的链路有问题时，所有与这条链路有关的 活跃节点都可以被通知到。一个路由表还有活跃邻居在使用，就可以认为是有效的。通过 南京邮电火学2 0 0 5 级倾i ：研究生学位论义第二章a dh o c 网络路由协议 各个活跃路由项所建立的源节点到目的节点的路径，也就是一条活跃路径。路由表中的目 的节点序列号，可以在无序消息的传送和节点高度移动的极端条件下避免路由环路的产 生。 移动节点为每一个相关的目的节点维护了一个路由表。每一个路由表包含以下些信 息：目的地址、下一跳地址、跳数、目的序列号及路由项的生存时间。路由表在每一次被 用来传送一个消息时，它的生存时间都要重新开始计算，也就是用当前时间加上 a c t i v e r o u t e t i m e o u t 。如果一个移动节点被提供了到达某一个目的节点的新路由，那么它 就会把这个新路由的目的序列号与自己路由表中己有的目的序列号做比较，并将目的序列 号大的作为到达目的节点的路由表。如果目的序列号相同，则采用到目的节点所经过的节 点数( 跳数) 最少的那个路由。 a o d v 路由维护 如果节点的移动不是沿着活跃路径进行的，那么就不会影响已经建立的路由。如果一 个源节点在活跃路径上移动，它就要向目的节点重新发起一次路由发现过程。如果移动的 节点是中间节点或目的节点，那么一个特殊的r r e p 消息将转发到那些受移动影响的源节 点。周期性发送的h e l l o 消息可以