（电工理论与新技术专业论文）无线ad+hoc网络分层路由问题研究.pdf

a b s t r a c t w i r e l e s sa dh o cn e t w o r k i n gp o s s e s s e st h ec h a r a c t 即o fa c c n t r i c ，s e l f - o r g a n i z e d , a u t o n o m o u s f a s td e p l o y a b l ea n dm o b i l e i tc a nb ef l e x i b l ya n dq u i c k l yd e p l o y e df o r m a n ya p p l i c a t i o n s s u c ha sd e c i s i o n m a k i n g i nt h e b a t t l e f i e l d , e m e r g e n c y s e a r c h - a n d - r e s c u eo p e r a t i o n s ，a n dd a t aa c q u i s i t i o no p e r a t i o n si ni n h o s p i t a b l et e r r a i n , c i t e n ee m e r g e n c eo fw i r e l e s sa dh o en e t w o r k sh a sa r i s e ng r e a ti n t e r e s to fm i l i t a r y d e p a r t m e n t s ，i n d u s t r i a lc o m m u n i t i e sa n da c a d e m i ci n s t i t u t i o n si nt h ew o r l d u n l i k ew i r e dn e t w o r k so rc e l l u l a rn e t w o r k s ，n op h y s i c a lb a k e b o n ei n f r a s l x t t e t u r e i si n s t a l l e di nw i r e l e s sa dh o cn e t w o r k s t h e r e f o r e h i e r a r c h i c a lr o u t i n gm e c h a n i s m w i t hav i r t u a lb a c k b o n ei sb e c o m i n gr e s e a r c hb o t s p o t b e c a u s eo fm o v i n gt h ep r e s e n t h i e r a r c h i c a lr o u t i l l gm a k ed e m a n d so i lh i 曲u p d a t ea n dm a i n t e n a n c eo fav i r t u a l b a c k b o n e w i t ht h er e s u l tt h a th i 曲c o n t r o lp a c k e t so v e r h e a da n de n e r g yw a s t ew o u l d b ca r i s e n t os o l v et h i sp r o b l e m , b a s e do nt h ee o f i c e p to fg r a p ht h e o r yw eg i v eaf e w m o d e l sa n da r i t h m e t i cd e s i g n so fv i r t u a lb a c k b o n ei nt h ee n v i r o n m e n to fd i f f e r e n t a p p l i c a t i o n , a n dp r o p o s et h ec o r r e s p o n d i n gr o u t i n gm e c h a n i s mw i t l lt h e s ev i r t u a l b a c k b o n e s t h em a j o ra c h i e v e m e n t sa r eo u t l i n e da sf o l l o w s ： 髓es t a t eo fh o s t sp o w e ro rt h et i m eo fh o s t so n l i n ep l a y sa l li m p o r t a n tr o l ei n k e e p i n gs t a b i l i t yo fav i r t u a lb a c k b o n e w i t hav i e wt o t h i sf e a t u r e ，t h ep a p e r i n t r o d u c e sas i m p l ea n de f f i c i e n th e u r i s t i ca l g o d t h mf o rc a l c u l a t i n gt h ev i r t u a l b a c k b o n eb ys e e k i n gam i n i m u mc o n n e c t e dd o m i n a t i n gs e tw i t hm a x i m a lw e i g h t n l e m a x i m a l i t yo ft h ew e i g h t b a s e dc h o i c eo fb a c k b o n en o d e sg u a r a n t e e st h a tt h em o s t s u i t a b l en o d e sh a v eb e e nc h o s e nf o rt h er o l eo fb a e k b o n en o d e ss ot h a tt l l e yc a n p r o p e r l yc o o r d i n a t ea l lt h eo t h e rn o d e sa n dk e e ps t a b i l i t yo ft h ev i r t u a lb a c k b o n ei n t h en e t w o r k 1 1 尬m i n i m a l i t yo ft h ev i r t u a lb a c k b o n ei sa s s u r e db yd e s i g n i n g o p t i m i z a t i o na l g o r i t h m a sar e s u l t , i t 啪e f f e c t i v e l yd e c r e a s et h eo v e r h e a do f c o n t r o l p a c k e t sd i s s e m i n a t i o n s i m u l a t i o nr e s l u t ss h o wt h ec o r r e c t n e s sa n dt h ea b i l i t yo f s e l f - r e n o z v c o n s i d e r i n gt h ec h a r a c t e r i s t i co ff a s t - m o v i n gi nw i r e l e s sa dh o en e t w o r k s ，w e c o n s t r u c tav i l t l l a lb a c k b o n ew i 也ai n d e p e n d e n td o m i n a t i n gs e t , t 1 1 i sm e t h o dc a n a v o i ds u s t a i n i n gc o n n e c t i v i t yb e t w e e nb a c k b o n en o d e sa n dt h eb a k e b o n en e t w o r kc a n b cr a p i d l yr e c o m t r u e t e da st o p o l o g yc h a n g e b ya d o p t i n gt h em e c h a n i s mo f d y n a m i c o n d e m a n dr o u t i n g ，t h eb a c k b o n en o d e sa r ep r e v e n t e df r o mk e e p i n gr o u t i n gt a b l e 一l v t h em i n i m a l i n d e p e n d e n td o m i n a t i n g s e ti ss e t t l e d b yc a l c u l a t i n gm a x i m a l i n d e p e n d e n ts e t i nv i e wo ft r a i to f o n l yt r a n s m i t t i n gd a t ai nw i r e l e s sa dh o cs e n s o rs y s t e m s w c c r e a t eav i r t u a lb a c k b o n ew i t has p a n n i n gr o o tt r e eo fr e l a ys e tw i t hm a x h m lw e i g h t a n dp r o p o s eae n e r g y a w a r em u l t i l e v e lc l u s t e rt r e ea l g o r i t h m ( e a m c n b y o p t i m u m s e e k i n gm e t h o d , t h en o d e sw i t hh i 曲r e s i d u a le n e r g ya n d l o wc o m m u n i c a t i o nc o s ta r eg i v e n f i r s tp r i o n t yt oc l u s t c r h e a d s a n db yu t i l i z i n gp e r i o d i c a lr o t a t i o no fl o c a lc l u s t e r h e a d s a n dm o t i o no fb a s es t a t i o nt oe v e n l yd i s t r i b u t et h ee n e r g yl o a da m o n gt h es e n s o l 暑i n t h en e t w o r ka n dp r o l o n gn e t w o r kl i f e t i m e s i m u l a t i o nr e s u l t sd e m o n s t r a t et h a to u r a p p r o a c hw o u l ds i g n i f i c a n t l yi n c r e a s et h el i f e t i m eo ft h es e = l l s o rn e t w o r ka n db e a p p l i e dt ot h ed e s i g no fs e v e r a lt y p e so fs e n s o rn e t w o r kp r o t o c o l st h a tr e x l u i me n e r g y e f f i c i e n c y ，s c a l a b i l i t y ，l o wd e l a y f o rt h es a k eo f s o l v i n gt h ep r o b l e mo f e n e r g yw a s t ea sd i s t a n c ei n c r e a s e da m o n g c l u s t e r i n gh e a d s ，b a s e do ne a m c tw eg i v ear o u t i n gm e c h a n i s mw i t he a m c t - g ( e n e r g y - a w a r em u l t i l e v e lc l u s t e rt r e ew i t hg a t e w a y ) b yi n t r o d u c i n gs o m eg a t e w a y n o d e sa sr e l a yt r a n s m i s s i o ni n t o c l u s t e r i n gh e a d s ，n e t w o r kl i f e t i m e i sf u r t h e t i n o r e p r o l o n g e d s i m u l a t i o nr e s u l t sd e m o n s t r a t ev a l i d i t yo f e a m c t - g k e y w o r d ：w i r e l e s sa dh o cn e t w o r k s ，v i r t u a lb a c k b o n en e t w o r k s ，h i e r a r c h i c a lr o u t i n g , d o m i n a t i n gs e t , i n d e p e n d e n ts e t , r o o tt r e e ，c l u s t e rt r e e v 独创性声明 本人声明所里交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得丞洼太堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：( 虱唠签字吼埘年g 月r 日 学位论文版权使用授权书 本学位论文作者完全了解丢洼塞堂有关保留、使用学位论文的规定。 特授权云洼太堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：门弘芳新签名：乃雨别 签字日期：哆年彦月f 日签字日期：嘶孑月日 u 第一章绪论 1 1 无线a d h o e 网络简介 第一章绪论 由于有线通信方式对应用范围的限制，使得无线移动通信的发展非常迅速。 按照移动通信系统是否有基础设施，可以把移动无线网络分成两类【i 】。 第一种类型是具有基础设施的网络，如图1 - 1 所示。移动主机借助于通信范 围内最近的基站实现通信。该类型的典型例子有蜂窝无线系统和办公室无线局域 网等。在这种网络中，移动主机相当于移动终端，不具备路由功能，而只有移动 交换机负责路由和交换功能。这说明移动终端之间的通信需要固定网络的支持， 也需要类似基站或访问服务点这样的中心控制设备。但这些特点使现有移动通信 系统在特殊场合中并不适用，如在野外环境临时通信和应急状态下的快速通信 等。于是就产生了第二种无基础设施的移动网络，也就是本文要重点研究的无线 a d h o e 网络。 图1 1 有基础设施的无线移动网 1 1 1 无线a dh o e 网络的概念 无线a dh o e 网络【2 】是一种无中一t l , 、 的特殊对等式网络，使用无线通信技术， 自组织、自适应、可快速展开、可移动 是现存移动网络必要的和有益的补充。 天津大学博士学位论文 它是由一些带有无线收发装置的移动主机组成的一个临时自治系统，其物理网络 结构如图l - 2 所示。从网络层角度来看的逻辑视图，即网络的拓扑结构如图1 3 所示，图中的节点分别对应各个无线移动主机；每条边则表示相连的两个主机彼 此都在对方的无线发射范围内。 图l - 2a d h o e 物理嘲络结构 图l - 3a d h o e 逻辑网络结构 a dh o e 网络是移动通信和计算机网络的交叉。一方面，网络的信息采用了 计算机网络中的分组交换机制，而不是电话交换网中的电路交换机制；另一方面， 用户终端可以是移动的便携式，如笔记本电脑、p d a 、掌上型电脑、车载机等， 配置有相应的无线收发设备，能随意移动或处于静止状态。在a dh o e 网络中， - 第一章绪论 移动主机的功能不仅仅是发射和接收，同时也具有路由选择和存储转发的功能。 一方面，作为主机，终端需要运行各种面向用户的应用程序，比如编辑器、浏览 器等；另一方面，作为路由器，终端需要运行各种相应的路由协议，根据路由策 略和路由表完成数据的分组转发和路由维护工作。在部分通信网络遭破坏后，这 种分布式控制和无中心的网络结构能维持剩余的通信能力，确保重要的通信指挥 畅通，因而具有很强的鲁棒性和抗毁性。 在a d h o c 网络中，由于终端的无线覆盖范围的有限性，两个无法直接进行通 信的主机可能要经过多个中间主机的分组转发，如图1 3 中的彳和厢信要经过曰、 e 的转发，这是a dh o c 网络与其他网络的最根本区别。a dh o c 网络中的信息流采 用分组数据格式，传输采用包交换机制，基于t c p i p 协议族。主机通过分层的网 络协议和分布式算法相互协调，实现了网络的自动组织和运行。因此a d h o c 网络 也被称为多跳无线网( m u l t i h o pw i r e l e s sn e t w o r k ) 或自组网( s e l f - o r g a n i z e d n e t w o r k ) 。随着无线技术的发展，有望成为4 g 未来关键技术的无线自组网正成为 研究的热点。 1 1 2a d h o c 网络的特征 与其他通信网络相比，自组网具有以下特，征【卜5 l ： 1 网络的自组性：无需依赖任何预设的网络设施，a d h o c 网络可在任何时 刻任何地点布设或展开。节点开机后就可以通过分层协议和分布式算法协调各自 的行为，快速、自动地组成一个独立的网络。节点可以随时加入和离开网络。任 何节点的故障不会影响整个网络的运行，具有很强的抗毁性，这对应付突发事件 和缓解热点地区的通信压力十分有利。 2 动态的拓扑结构：移动用户可以以任意的速度和任意方式在网中移动， 加上无线发送装置发送功率的变化、无线信道问的相互干扰、地形因素等的影响， 节点间通过无线信道形成的网络拓扑结构随时都会发生变化，这些特点使得a d h o c 网络在体系结构、网络组织、协议设计等方面都与普通的蜂窝移动通信网络 和固定通信网络有着显著的区别。 3 多跳组网方式：多跳特性增加了路由选择的复杂性，对移动终端在功耗、 电池屏蔽、便携性、灵活性和设计成本等方面都是巨大的挑战。但同时它的这一 3 天津大学博士学位论文 特性也使得中继节点可以更灵活地选择路由，避开干扰严重的地区，可以在一定 程度上消除建筑物阴影造成的影响，同时也可以解决城区周边地区信号质量较差 的问题。另外，由于收发主机可以使用比两者直接通信小得多的功率进行通信， 因此大大节约了电池能量的消耗。 4 有限的无线传输带宽：无线信道本身的物理特性使自组网的网络带宽相 对有线方式要低得多。另外还要考虑无线信道竞争时所产生的信号衰落、碰撞、 阻塞、噪声干扰等因素，使得移动终端实际得到的带宽较最大理论值要小得多。 5 有限的覆盖范围：一方面，较短的传输距离使路由的更新跟不上移动所 带来的拓扑结构的变化；另一方面，过多的中继可能使路由变得很脆弱。但因每 个用户的覆盖范围非常有限，可使得频率复用成倍地提高，从而增加了容量。 6 移动终端的有限性：如移动用户终端内存小、c p u 处理能力低、所带电 源有限等，使得自组网的应用程序设计开发更加困难，要求设计的软件算法必须 简单适用，而不能像通常路由器软件那样复杂精巧。 7 移动带来的丢包：由于移动所带来的路由改变而不得不重新选路，以及 设备存储器容量的限制等原因，无线a dh o e 网络中的节点在移动过程中的丢包 率会明显增加。 8 传输错误带来的丢包：无线传输的差错率要远远高于有线传输，像t c p 这样的高层协议在这样的链路上工作，效率会大大降低。 9 安全性差：自组网的无线链路使其很容易受到链路层的攻击，包括被动 窃听和主动假冒、信息重放和信息破坏；节点在敌意环境漫游时缺乏物理保护； 由于网络成员的经常变化，自组网没有值得信任的第三方的证书的帮助；网络中 包含成百上千个节点，需要采用具有扩展性的安全机制。 1 0 网络的分布式：自组网中的移动节点都兼有独立路由和主机功能，不存 在类似于基站的网络中心控制点，节点地位平等，采用分布式控制方式，增强了 网络健壮性和抗毁性。 1 1 单向无线信道的存在：无线传输设备功率的差异、地形环境的影响以及 无线信道中的大量干扰可能导致单向信道的存在，即两节点只能进行单方向通 信。单向信道给常规路由带来三个严重的影响：认知单向性、路由单向性和汇点 不可达。因此，常规路由协议计算出来的路由不能准确反映自组网的拓扑结构， - 第一章绪论 也无法有效利用单向信道。对于需要逐条确认的数据分组也由于单向信道的存在 而无法实现。 1 2 无线媒体的广播特性：常见的隐蔽节点和暴露节点问题。 1 3 生存时问短：组网通常是由于某个特定原因而临时创建的，使用结束后， 网络环境将会自动消失。自组网的生存时间相对于固定网络而言是短暂的。 1 4 有限的可扩展性：自组网属于采用全向天线的非协作网络，节点间的相 互干扰造成网络容量下降，各节点吞吐量随网络节点总数的增加而下降，还有网 络中各种协议造成的附加开销，如路由的获取、业务定位、加密密钥的交换等对 网络资源的消耗随节点数增加而急剧增加，从而也限制了网络的扩展。采用t c p 口协议中的子网技术使得i n t e m e t 具有好的可扩展性，而自组网动态变化的拓 扑结构使得具有不同子网地址的移动终端可能处于一个自组网中，因而子网技术 所带来的网络可扩展性很难得到应用。本文将采用基于虚拟骨干子网的路由机制 来提高自组网的可扩展性。 1 1 3a d h o c 网络的应用领域 由于a dh o e 网络的特殊性，它的应用领域与普通的通信网络有着显著的区 别。它适合被用于无法或不便预先铺设网络设施的场合、需快速自动组网的场合 等。针对a dh o e 网络的研究是因军事应用而发起的。因此，军事应用仍是a dh o e 网络的主要应用领域。但在民用方面，a dh o e 网络也有非常广泛的应用前景。 它的应用场合主要有以下几类【1 4 l ： 1 军事应用：因其特有的无需架设网络设施、可快速展开、抗毁性强等特 点，它是数字化战场通信的首选技术。a dh o e 网络技术已经成为美军战术互联 网的核心技术。美军的近期数字电台和无线互联网控制器等主要通信装备都使用 了a d h o e 网络技术。 2 传感器网络：传感器网络是a dh o e 网络技术的另一大应用领域。对于很 多应用场合来说传感器网络只能使用无线通信技术。而考虑到体积和节能等因 素，传感器的发射功率不可能很大。使用a dh o e 网络实现多跳通信是非常实用 的解决方法。分散在各处的传感器组成a dh o e 网络，可以实现传感器之间和与 控制中心之间的通信。这在爆炸残留物检测等领域具有非常广阔的应用前景。 5 天津大学博士学位论文 3 紧急和临时场合：在发生了地震、水灾、强热带风暴或遭受其它灾难打 击后，固定的通信网络设施( 如有线通信网络、蜂窝移动通信网络的基站等网络 设施、卫星通信地球站以及微波接力站等) 可能被全部摧毁或无法正常工作，对 于抢险救灾来说，这时就需要a dh o e 网络这种不依赖任何固定网络设施又能快 速布设的自组织网络技术。类似地，处于边远或偏僻野外地区时，同样无法依赖 固定或预设的网络设施进行通信。a dh o e 网络技术的独立组网能力和自组织特 点，是这些场合通信的最佳选择。 4 个人通信：个人局域网( p a n ，p e r s o n a la r e a n c t w o r k ) 是a dh o e 网络技术 的另一应用领域。不仅可用于实现p d a ( p e r s o n a ld a t ea g e n t ) 、手机、手提电脑 等个人电子通信设备之间的通信，还可用于个人局域网之间的多跳通信。蓝牙技 术中的超网就是一个典型的例子。 5 与移动通信系统的结合：在实际应用中，a dh o c 网络除了可以单独组网 实现局部的通信外，它还可以作为末端子网通过接入点接入其他的固定或移动通 信网络，与a dh o e 网络以外的主机进行通信。利用移动台的多跳转发能力扩大 蜂窝移动通信系统的覆盖范围、均衡相邻小区的业务、提高小区边缘的数据速率 等。因此，a dh o c 网络也可以作为各种通信网络的无线接入手段之一。它的应用 和发展将使人们获得更大的自由，充分享受移动通信带来的方便。 1 1 4a d h o c 网络的研究难点 由1 1 3 可知，多跳无线自组网在使用上有很多优点，但优点和缺点总是相 辅相成的，使用时的优点在设计时却成为难点。与基于基站的无线网不同，多跳 无线网的每个节点都是可以移动的组合设备，既是路由器，又是终端，还有无线 收发设备，各个节点通过空中链路进行通信。设计网络时就必须考虑满足动态拓 扑结构、带宽受限、链路的容量不稳定、功率受限、无线频谱辐射的安全防护等 约束条件。目前关于a dh o e 网络研究中的主要难剧5 】问题为路由协议、服务质 量【9 2 1 、m a c 协议 1 3 , 1 4 1 、功率控制”5 1 、安全问题、网络互连和网络资源管理等。 其中开发良好的路由协议是建立a dh o e 网络的首要问题，同时也是主要的研究 热点和难点。本论文的目的就是针对路由机制问题进行研究。 一6 - 第一章绪论 1 2 无线a d h o e 网络路由问题 与单跳的无线网络不同，自组网节点之间是通过多跳数据转发机制进行数据 交换，需要路由协议进行分组转发决策。无线信道变化的不规则性、节点的移动、 加入、退出等也会引起网络拓扑结构的动态变化。路由协议的作用就是在这种环 境中，监控网络拓扑结构变化，交换路由信息，定位目的节点位置，产生、维护 和选择路由。并根据选择的路由转发数据，提供网络的连通性。它是移动节点互 相通信的基础，因此成为当前自组网体系结构中的研究热点。i e t f 于1 9 9 6 年成 立了自组网工作小组( m a n e t w g ) ，其目前的核心任务就是研究自组网环境 下基于p 协议的路由协议规范和接口设计1 6 j 。 传统的距离矢量路由协议( 如r x p ) 和链路状态路由协议( 如o s p f ) 都是针对 固定网络而设计的，它们都需要周期性地交换信息来维护网络正确的路由表或网 络拓扑结构图，并不适合于带宽较窄、拓扑结构高度动态变化的a dh o e 网络。 开发一种能有效地找到节点间的动态路由协议就成为当前a dh o e 网络研究的一 个重点问题 1 , 7 , s l 。 1 2 1a d h o e 网络路由协议性能要求 针对a dh o e 网络的特点，除了应满足传统的路由协议要求，如最优性、简 单、低开销、健壮、稳定、快速聚敛、适用性强等外，还应当满足以下的特性要 求：分布式运行方式、提供无环路由、按需进行协议操作( 在必要时需要主动式 操作的辅助) 、安全性、能够支持设备“睡眠”操作特性以节省电源、对终端性 能无过高要求、对单向信道的支持、控制管理开销小、尽量简单实用等。但就目 前所提出的路由协议来看都尚未达到以上所有要求，提出一种适应性强的路由协 议是a dh o e 网未来研究中一个具有挑战性的课题。 1 2 2a d h o e 网络路由协议的目标 a dh o e 网络路由协议的目标是快速、准确、高效、可扩展性好。快速指的 是查找路由的时间要尽量短，减d , i 3 1 入的额外时延；准确指路由协议要能够检测 天津大学博士学位论文 到网络拓扑结构的变化，提供准确的路由信息；高效的含义比较复杂；其一指要 能提供最佳路由，其二指维护路由的控制消息应尽量少，以降低路由协议的开销， 其三指路由协议应能根据网络的拥塞状况和业务的类型选择路由，避免拥塞并提 供q o s 保证；可扩展性指路由协议要能够适应网络规模增长的需要。 1 2 3a dh o e 网络路由协议的性能衡量指标 对一个白组网路由协议定量衡量，比较的指标应该包括：端到端的数据吞吐 量和平均时延；分组的平均递交率( 成功分组接收率) ；路由协议开销；路由获 得时间、路由的准确性等。 1 2 4a d h o e 网络路由协议分类 自2 0 世纪7 0 年代美军d a r p a 资助研究的分组无线网项目开始以来，目前 许多研究人员基于不同的角度提出了一系列的a dh o e 网络路由协议【1 6 - 5 7 1 。根据 发现路由的策略，可以将这些协议分为主动路由协议和按需路由协议；根据网络 逻辑结构，可以将其分为平面结构和分级( 群) 结构。从网络逻辑视图的角度出发， 可分为平面路由协议和分级路由协议，几种路由技术的比较【1 l 见表1 1 。 下面分别介绍不同类型路由协议的特点。 1 2 4 1 主动路由协议 主动路由协议也被称为表驱动路由协议( o n - t a b l ed r i v e np r o t o c 0 1 ) 、先应式路 由协议( p r o a r t i v ep r o t o c 0 1 ) 。在该协议中，每个节点都维护一张或几张到网络中其 他节点的路由信息表，不管有无通信需求，都要进行路由信息交换。当网络拓扑 结构发生变化时，节点通过交互信息来实时地维护网络路由信息表。不同路由协 议所需要的路由表的种类、数量及更新路由信息使用的方法不同。主动路由的路 由发现策略与传统路由协议类似，当节点需要发送数据分组时，只要去往目的节 点的路由存在，所需的延时很小。主动路由协议比较适合有实时和q o s 要求的 网络通信。 第一章绪论 表1 - 1 路由技术的比较 分类角度路由类型优点缺点典型协议 当节点需要发送数花费开销较大，应尽可能使 d s d v ，纾冗只 据分组时，只要到目路由更新紧随拓扑结构变 s t a r a , o s i t , 的节点的路由存在， 化，但动态变化的拓扑结构 f s 凡h s r 从 主动路由 所需的延时很小可能使路由更新信息变得过 路 时，路由协议始终处于不收 z h l s 由 发 敛状态。 现 策 略 无需周期性路由信发送数据分组时，如果没有a o d 、d s r 的 息广播，节省了一定 到目的节点的路由，需进行 角 按需路由t o r a 乒b r 度 的网络资源。路由发现，数据分组的发送 因路由发现过程而被延时。 s s i 乙c b r p , 无特殊节点，网络中可扩展性较差，限制了网络a o d v , d s & 业务流平均分散，路的规模。 t o r a ，d s d v , 从 由协议鲁棒性较好， w r p , s t a r a ， 网 平面路由 无需进行节点移动 络 l a r 逻 性管理。 辑 视 网络由多个分群组群首节点的可靠性和稳定性c g s c b r p 图 成，可扩展性较好，对全网性能影响较大，为支c e d a r ，z r p , 的 分级路由 角 适合大规模的自组持节点在不同分群之间漫游 度 网环境。 所进行的移动管理将产生一 定的协议开销。 下面介绍两种典型的主动路由协议。 d s d v 博l ( 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 ) ，目标序列距离矢量路 由协议是基于传统的b e l l m a n f o r d 路由选择机制的表驱动算法，被认为是最早的 自组网路由协议。d s d v 的特点是通过引入序列号机制解决了“路由环路”和 “计数到无穷”问题；通过用“时间驱动”和“事件驱动”机制更新路由信息， 尽量减少路由等控制信息对无线信道的占用，以提高系统效率。它的缺点是不适 应变化速度快的自组网，不支持单向信道。 w r p 1 9 1 ( w i r e l e s sr o u t i n gp r o t o c 0 1 ) ，也是一种距离向量路由协议，每个 节点包含距离表、路由表、链路权值表和消息重传表。该协议是在路径发现算法 ( p a t hf i n d i n ga l g o r i t h m ，p f a ) 【2 0 】【g m 9 7 】基础上改进设计的。p f a 利用去往目 标节点的路径长度和相应路径的倒数第二跳节点信息加速路由协议收敛速度，改 善路由环路问题。w r p 对p f a 的改进之处在于当节点i 监测到与邻居节点，的 g 天津大学博士学位论文 链路发生变化时，i 会检查所有邻居节点关于倒数第二跳节点信息的一致性，而 p f a 只会检查节点，关于倒数第二跳节点信息的一致性。这种方式可以进一步地 减少出现路由环路的次数，加快算法的收敛速度。虽然表面上只是用一条路经， 但是维护了使用多径所需要的路由信息，但是协议中维护最短路径的扩张树以及 对邻居节点链路失败的响应都需要很大的网络开销。 1 2 4 2 按需路由协议 按需路由协议( o n - d e m a n dp r o t o c 0 1 ) 也被称为反应式路由协议( r e a c t i v e p r o t o c 0 1 ) 、源驱动按需路由协议( s o u r r e i n i t i a t e do n d e m a n dd r i v e n ) 。与主动式路 由协议不同的是，按需路由仅在有数据发送需要路由时才由源节点创建 2 l 2 2 ，因 此，拓扑结构和路由表内容是按需建立的，它可能仅仅是整个拓扑结构信息的一 部分。通信过程中维护路由，通信完毕后便不再进行维护。这样可有效地节省带 宽和内存，特别是当网络负荷不是很重时，节省的开销更加可观。以下介绍几种 现有的按需路由协议。 d s r ( d y n a m i c s o u r c er o u t i n g ，动态源路由) 1 2 3 是一种源点选路路由协 议，是最早采用按需路由思想的路由协议。每个主机不需构建任何路由表，只需 维护一个高速缓冲器( c a c h e ) 保留存储所知道的源路径。当新的路由被发现时， 缓冲器内的条目随之更新。它的主要特点是使用了源路由机制，报文的头部携带 要经过的路由，经由主机按照该路由序列来转发报文。这种机制最初是i e e e 8 0 2 5 协议用于在网桥互连的多个令牌环网中节点寻找路由。d s r 协议借鉴了这种机 制，并加入了按需思想。协议包括两部分：路由发现和路由维护。 d s r 的优点是主机不需要周期性的发送报文、更新路由表，能自然而完全 地消除路由环路，而且还能同时提供多条路由，可用于单向信道。节省了电池能 源和网络带宽，尤其是当没有主机要发送数据时，网络中没有通信开销，支持主 机睡眠。它的缺点是每个数据分组都携带了完整的路径信息，造成协议开销较大， 降低了网络带宽的利用率。而且也不适合网络直径大的自组网，网络可扩展性不 强，也会出现过时路由问题。 目前，通过一些优化措旆，d s r 得到了部分改进：当链路出错时，出错点的 中间主机可以从自己的路由列表中选出另一个可选路由，完成到目的主机的传 - 1 0 第一章绪论 输；将出错信息加载到源节点重新发出的路由请求信息中，以更新网络中含有该 出错链路的主机的路由信息；当中间主机发现其路由表中含有到目的主机的路由 信息时，可直接向源节点返回应答信息。主机采用混杂监听模式，可获得大量的 路由信息。 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 r ) t 2 4 ，a dh o c 按需距离矢量路由 是在d s d v 协议基础上结合类似d s r 中的按需路由机制进行改进后提出的，通 过随选路由来降低d s d v 中控制报文的数目，从而提高系统效率。不同之处在 于a o d v 采用了逐跳转发分组方式，而d s r 是源路由方式。因此，a o d v 在 每个中间节点隐式保存了路由请求和回答的结果，而d s r 将结果显式保存在路 由请求和路由回答分组中。此外，a o d v 的另一个显著特点是它加入了组播路 由协议扩展，并支持q o s 。它的缺点是不支持单向链路和多径。 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 g a l g o r i t h m ) 1 2 5 1 ，临时预定路由算法是 在有向无环图( d i r e c t e d a c y c l i c g r a p h i c ，d a g ) 算法i 矧的基础上提出的一种源初 始化按需路由选择协议，具有高度自适应、高效率和较好的扩展性，能同时支持 按需和主动路由发现策略。它比较适合高度动态移动、多跳的无线网络，能提供 多条路由。t o r a 的特色在于当有链路的改变时，相邻节点所产生的控制消息被 限在改变发生处的局部。t o r a 协议的缺点主要是协议的有效运行依赖于网络的 高连通度提供路由维护所需的多条备选路径，协议开销比其他按需路由协议大， 它也不支持单向信道，需要全局同步时钟的支持，而且具有潜在的振荡可能。 a b r ( a s s o c i a f i v i t yb a s e dr o u t i n g ，联合稳定度路由) 【2 7 1 中路由的选择是 以节点间的连接稳定性作为度量依据的。a b r 有两个独特之处：一是依据路由的 持久性和质量来选择路由，另一个是路由失效时通过路由重组来快速查找路由。 a b r 协议的优点是选择的路由持久性和质量比较高，因路由维护中采用了局部查 找，不像d s r 总是让源主机查找路由，这样可以减小路由恢复的时间和路由维护 的开销。在路由查找中必须由目的主机选择路由，可以避免过时路由问题。但这 样做会增加源获得路由的等待时间。另外路由重组中需要合理设置上游主机的局 部查找范围，若上游主机在给定的有限范围内没有找到路由，要回溯查找，这会 增加新路由查找的延迟和开销。 l a r ( l o c a t i o na i d e dr o 砸n 曲【2 8 】协议是一个基于预测节点当前位置算法 天津大学博士学位论文 来控制路由查询范围的协议。l a r 的优点是将路由查找限制在请求区中，在请求 区之外的主机不受路由请求的干扰，因此路由查找速度快、开销小、网络的扩展 性能好，另外它只提出策略，不拘泥于某一种确定的协议，适用范围广。缺点是 它必须依靠g p s 系统才能正常工作，限制了其应用范围。 总之，按需路由是以路由建立时延的增加为代价的，不适用于时延敏感型应 用。考虑到路由建立过程是靠泛洪方式广播路由信息，这在一定程度上使其优点 有所削弱。 1 2 4 3 分级路由协议 基于网络逻辑结构视图角度，可分为平面型( f l a t ) 和分级( 层) 型( h i e r a r c h i c a l ) 两种路由协议。在平面型路由( 如以上介绍的所有路由) 中，节点地位平等，优 点是路由协议的鲁棒性较好，交通流量平均地分散在网络中。但最大缺点是网络 规模受限，因为在平面结构中，每一个节点都需要知道到达其它所有节点的路由。 由于节点的移动性维护这些动态变化的路由信息需要大量的控制消息。另外， 由于平面结构是完全的分布式结构，有些控制功能也很难实现。解决的办法之一 便是采用分级路由方案以获得可扩展的有效路由。 l 艄e r 2 i 甜e r b 图l - 4 一个3 层分级逻辑拓扑图例 分级型路由协议中，网络被划分为簇( 或群) ( c l u s t e r ) ，每个簇由一个簇头 第一章绪论 ( c l u s t e rh e a d ，c h ) 和多个簇成( c l u s t e rm e m b e r ) 组成，这些簇头形成了高一 级的网络，在高一级网络中，又可以分簇，再次形成更高一级的网络，直至最高 级。图1 4 给出了一个3 层分级逻辑拓扑的图仞j 【1 9 1 。为了实现簇头之间的通信， 要有网关( g a t e w a y ) 节点( 同时属于两个簇的节点) 的支持。簇头和网关形成了高 一层的网络，称为虚拟主( 骨) 干网( v i r t u a lb a c k b o n e ) 。 无线分级路由的基本思想是把节点划分为不同的分簇并对簇内外的节点指 定不同的功能，其主要目的有两个：一是减少参与路由计算的节点数( 只有簇头 节点参与) ，减少节点路由表中的尺寸，降低交换路由信息所需的通信开销和维 护路由表所需的内存开销；二是通过某种分簇形成策略，产生一个较为稳定的骨 干网络，减少拓扑结构变化对路由协议带来的影响。下面将介绍几种典型的分层 路由协议，并着重分析分层形成策略。 c b r p ( c l u s t e rb a s e dr o u t i n gp r o t o c o l ，基于分簇结构的路由协议1 是基于 分簇结构的按需分级式a dh o e 路由协议，该协议可用于非对称链路。c b r p 将网 络分成互不重叠的簇，每个簇中有且只有一个簇头，由节点号最小的节点担 任，并维