（通信与信息系统专业论文）ad+hoc网络路由协议的研究.pdf

， 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名： 导师签名：至燃日期：墨堕：堑：丛 山东大学硕士学位论文 中文摘要 a dh o e 网络是近年来发展起来的一种无线移动分组网络，它具有动态变化 的拓扑结构，网络中的节点可以任意移动，也可以动态的加入或退出网络a d h o e 网络无任何中心和固定基础设施，网络中各个节点的地位平等，每个节点都 具有主机与路由器的双重功能，形成了一个以中间主机节点为中继的多跳的分布 式网络结构 路由技术是a dh o e 网络的关键技术，也是影响网络整体性能最重要的因素 之一传统的固定网络中的路由协议已经不再适应a dh o e 网络动态变化的拓扑 结构，必须设计新的a dh o e 路由协议。近年来，出现了一些专门适用于a dh o e 网络的路由协议，如a o d v 、d s r ，d s d v 等，但就整体而言，a dh o c 路由技 术，特别是具有q o s 保障的路由技术，仍处于探索阶段，尚无成熟的协议标准， 还有待于进一步的深入研究 本文从a dh o e 网络的基本概念入手，对a dh o c 网络的路由协议进行了详 细的分析研究。通过n s 仿真。比较分析了几种常见路由协议在不同环境下的性 能交化；并对a o d v 路由协议进行了基于m a c 层退避算法的改进。仿真表明， 改进后的a o d v 路由协议在较大的网络负载下具有更好的开销性能。 文中通过对a d h o e 路由协议的比较分析，提出了一种新的基于位置预测的 a dh o c 路由协议s q r p o p ( as t e a d yq o s r o u t i n gp r o t o c o lb a s e do np r e d i c t i o n f o ra dh o en e t w o r k s ) 。s q r p o p 通过对节点的位置进行预测，选择最稳定路径 进行数据传输，降低了路由破裂与重构次数，提高了数据成功传送率；采用带宽 限制定向洪泛的路由算法和资源预留机制为数据的传输提供了可靠的q o s 保障。 降低了路由开销。 本文内容主要有以下几个部分： 第一章简要介绍了a d h o e 网络和a d h o c 路由技术的基本概念和发展现状。 第二章全面比较分析了现有各种a dh o c 路由协议的性能和优缺点，在此基 础上，提出了一些路由协议的性能优化方案。 第三章使用n s 仿真软件在不同环境下对常见a dh o e 路由协议进行了仿真 分析和性能比较：对a o d v 路由协议进行了详细的仿真性能分析，提出了一种 基于m a c 层退避算法的a o d v 改进方案。 3 山东大学硕士学位论文 第四章对q o s 路由技术和基于位置预测的路由协议进行了详细的比较分析， 总结了协议的优缺点并给出了相应的改进方案：在比较分析的基础上，提出了一 种基于位置预测的a dh o e 网络q o s 路由协议s q r p - o p ，给出了具体的协议描 述和算法实现过程，并对s q r p - o p 路由协议的性能进行了定性分析 第五章总结全文，对a dh o e 路由技术的进一步研究与发展进行了展望。 关键词：a dh o c 网络；a dh o c 路由协议；服务质量；位置预测；网络仿真 4 山东大学硕士学位论文 a b s t r a c t a dh o en e t w o r ki sak i n do fw i r e l e s sa n dm o b i l en e t w o r kd e v e l o p si nr e c e n t y e a r s i th a sac l y n a m i ea n dv a r i a b l et o p o l o g y , e a c hn o d en o to n l yc a ni n o v l ：b u t 啪 j o i no re x i tt h en e t w o r kf r e e l y i th a s 矩a c e n t r i ca n di n f r a s t r u e t u r e l e s sd i s t r i b u t e d m u l t i h o ps t r u c t u r e a l ln o d e sh a v e 锄e q u a ls t a t u sa n da c ta st w or o l e s - r o u t e ra n d n o d ei t s e l f r o u t i n gt e c h n i q u ei st h ek e yt e c h n i q u eo fa dh o e n e t w o r ka n do n e ：o ft h em o s t i m p o r t a n tf a c t o r sa f f e c tt h ep e r f o r m a n c eo f t h en e t w o r k a st h ed y n a m i ca n dv a r i a b l e t o p o l o g y , t h o s et r a d i t i o n a lr o u t i n gp r o t o c o l sc a l ln o tb ea p p l i c a b l et oa dh o en e t w o r k a n dn e wr o u t i n gp r o t o c o lm u s tb ed e s i g n e d i nr e c e n ty e a r s , s o m es p e c i a lr o u t i n g p r o t o c o l sf o ra dh o cn e t w o r ka p p e a r e ds u e l a 鹬a o d v , d s r a n dd s d v b u tt ot h e w h o l ef i e l d so fa dh o er o u t i n gt e c h n i q u e se s p e c i a l l yq o sr o u t i n gt e c h n i q u e ，s t i l lh a s al o n gw a yt og o a l lt h o s er o u t i n gp r o t o c o l sa r en e e dt ob ei m p r o v e da st h e r ei sn o a n ys t a n d a r dp r o t o c o le x i s t sf o ra dh o en e t w o r k a dh o er o u t i n gt e e l m i q u en c e d sa f 1 1 l 吐c l rr e s e a r c ha n dd e v e l o p m e n t t h ed i s s e r t a t i o ns t u d i e da dh o er o u t i n gp r o t o c o l si nd e t a i l w ea n a l y z e da n d c o m p a r e dt h ep e r f o r m a n c eo fs e v e r a la dh o er o u t i n gp r o t o c o l sw i t hn s 2u n d e r d i f f e r e n tn e t w o r ke n v i r o n m e n t i no r d e rt oe n i l a l l c et h ep e r f o r m a n c eo fr o u t i n g p r o t o c o la o d v , w em a d e 跹i m p r o v e m e n tb a s e do i lr e t r e a ta l g o r i t h mo nm a cl a y e r t h ei m p r o v e d - a o d vh a sab e t t e rp e r f o r m a n c eo nr o u t i n gs p e n d i n gt h a nt r a d i t i o n a l a o d vw h e nt h en e t w o r kh a sa b i g l o a d i nt h et e x t , w ep u tf o r w a r do n en e wa dh o er o u t i n gp r o t o c o lc a l l e ds q m , - o p ( a s t e a d yq o sr o m i l l gp r o t o c o lb a s e do np r e d i c t i o nf o ra dh o en e t w o r k s ) s q r i - o l c h o o s et h em o s ts t a b l ep a t ht r a n s m i td a t ab a s e d0 1 1t h ep r e d i c t i o nt on o d e s l o c a t i o n , i t d e c r e a s e st h ep r o b a b i l i t yo fr o u t i n gb r o k e na n dr e c o n s t r u c t i o na n de 1 1 h a n c e 5d a t a s u c c e s s f u lt r a n s m i s s i o n 撇t h ei , , o , o c o lu s ead i r e c t i o n a lf l o o d i n gr o u t i n ga l g o r i t h m w i t hb a n d 1 i m i t e da n dl - * 学o u l c er e s e r v a t i o ns c h e m et of o u n das u c c e s s f u lr o u t e ，s oi t c 蛆p r o v i d et h ed a t at r a m m i s s i o nw i t hr e l i a b l eq o sg u a r a n t e ea n d d e c r e a s e st o u l i d g s p e n d i r l g 5 山东大学硕士学位论文 一i _ t h ec o n t e n to f t h ed i s s e r t a t i o nm a i n l yi n c l u d i n gf i v ep a r t sa sf o l l o w s ： i nc h a p t 盯o n e ，w e # v eab r i e fi n l z _ o d u c t i o nt ot h ec o n c e p ta n dd e v e l o p m e n to f a dh o cn e t w o r ka n dr o u t i n gp r o t o c o l s i nc h a p t e rt w o ，w ec o m p a r e dt h ep e r f o r m a n c eo fa dh o cr o u t i n gp r o t o c o l si n & t a i la n dp r o p o s e ds o m es c h e m e sw h i c hc a ni m p r o v et h ep e f o r m a n c co fa dh o c n e t w o r k s i nc h a p t e rt h r e e ，w ec o m p a r e da n da n a l y z e dt h ep e r f o r n m c eo fs e v e r a la dh o c r o u t i n gp r o t o c o l st h r o u g hn e t w o r ks i m u l a t i o nw i t hn s - 2 ，a n dw ea l s op r o v i d ea n i m p r o v e ds c h e m e sf o ra o d v b a s e do nr e t r e a ta l g o r i t h mo nm a cl a y e ri nt h i sp a r t i nc h a p t e rf o r e , f i r s t l y , w ea n a l y z e da dh o cq o sr o u t i n gt e c h n i q u e sa n da dh o c r o u t i n gp r o t o c o l st h a tb a s e do np r e d i c t i o nt on o d e s l o c a t i o n t h e n , w ep u tf o r w a r d o n ea dh o cq o sm u t i n gp r o t o c o lb a s e do np r e d i c t i o nc a l l e ds q r p 0 1 , t h e d e s c r i p t i o no ft h ep r o t o c o la n da l g o r i t h mw a sg i v e na sf o l l o w s a tl a s t , w ed i da a n a l y s i st ot h ep r o t o c o ls q r p - o r t h ef i f t hc h a p t e ri st h el a s tp a r to ft b ed i s s e r t a t i o n , w ed r a wac o n c l u s i o no ft h e w h o l ed i s s e r t a t i o na n dm a d ea ne x p e c t a t i o nt o 缸 t h o rr e s e a r c ha n dd e v e l o p m e n to f a dh o cm u t i n gt e c h n i q u e k e yw o r d s ：a dh o cn e t w o r k ；a dh o cr o u t i n gp r o t o c o l ；q o s ；l o c a t i o np r e d i c t i o n ； n e t 、v o r ks i m u l a t i o n 6 山东大学硕士学位论文 1 1 a d h o e 网络简介 第一章引言 2 0 世纪7 0 年代初，美国国防部高级研究计划局( d a 船a ) 启动了d a 砌狐 p r n e t ( p a c k e tr a d i on e t w o r k ) 计划，开始研究移动分组无线网络( p r n 】盯) ， m a n e t ( m o b i l ea dh o cn e t w o r k ) 即有d a r p ap r n e t 演化而来i l 】m a n e t 又称a dh o c 网络，a dh o c 一词来源于拉丁语，字面上的意思是“为特定目的或 场合的”或“仅为这种情况的”，它是一种无中心和任何基础设施的无线移动自 组网络( a ni n f r a s t m c t u r e l e s sw h - e l e s s & m o b i l es e l f - o r g a n i z e d n e t w o r k ) 。它与有 线网络或其它无线网络最大的区别是动态变化的拓扑结构，节点可以动态的加入 或离开网络。分布式的网络拓扑结构和无线节点发射功率的有限性要求网络中每 个主机具有路由器和主机双重功能，形成了以中间主机为中继的多跳( m u l t i - h o p ) 网络。近年来，随无线通信技术与网络技术的发展，移动a dh o c 网络得到了深 入的研究并取得了相当的成绩，为此，正t f ( i n t e m e te n g i n e e r i n g & t a s kf o r c e ) 专门成立了m a n e t - i 作小组负责m 绁瞧t 标准的制定和规范，进一步促进了 该领域的研究发展。 普通节点( 簇成员) 簇首 冈关 图1 1 a d h o c 网络的拓扑结构 ( i i ) a d h o c 网络是一种特殊的无线移动自组网络，拓扑结构如图1 1 所示，图i 7 山东大学硕士掌位论文 m l _ _ _ _ _ - _ _ _ _ - _ _ _ _ _ _ _ - _ _ - - _ - _ _ _ - _ - _ _ _ _ _ _ _ _ - _ 一 和分别为a dh o c 网络的平面与分级结构。与传统的固定网络相比，a dh o c 网络主要有以下一些特点【2 】： 自组性与分布式拓扑结构a dh o c 网络可以在任何时刻、任何地方自组织 构建，而不需要现有的信息基础网络设施的支持自组性和鲁棒性要求网络 中各个节点的地位平等，必须采用分布式的拓扑结构。 动态变化的拓扑结构a dh o e 网络中节点可以随意的移动，也可以动态的 加入或者退出整个网络，因此网络具有动态变化的拓扑结构 有限的无线传输带宽无线移动信道具有十分恶劣的通信环境，信号的衰落、 各种噪声的干扰以及信道的共享与竞争都给无线传输带宽带来了挑战。 移动终端的有限性a dh o c 网络中移动终端内存小，c p u 处理能力低，所 带电源和发射功率也十分有限，使网络的设计更加困难。 安全性差无线信道的安全性较差，容易被窃听、入侵、攻击，此外，a dh o c 网络采用分布式结构也进一步降低了网络的安全性。 此外，可扩展性不强，单向链路的存在，网络生存时间短等也都是a dh o c 网络区别于一般网络的特点因此，a dh o c 网络面临比传统固定网络更大的技 术困难，到目前为止，尚无成熟的商业a dh o c 网络出现，大多数技术问题还处 于理论探讨阶段，与实际应用还有一定的距离。 目前，该领域的研究热点和难点主要集中在以下几个方面： 路由技术。开发良好的路由协议是a dh o c 网络要解决的首要问题，路由协 议也是目前最主要的研究热点和难点网络动态变化的拓扑结构是路由协议 的最大困难，传统的路由协议难以满足动态变化的拓扑结构，必须开发新的 适用于高度动态变化的a dh o c 网络的路由协议。同时，分布式算法、高效 及时、按需运行、安全和能耗等都是路由协议设计需要考虑的问题，路由技 术已成为a dh o c 网络中最关键的技术。 接入控制技术。a dh o c 网络m a c 层面临着隐终端和暴露终端的问题。如何 设计好的m a c 协议和退避算法使无线信道的报文冲突尽可能减小，对于提 高信道利用率、降低开销、提高网络的整体性能都有重要意义。 q o s 技术a d h o c 网络的无线资源相当有限，因此，为数据提供可靠的q o s ，4 山东大学硕士学位论文 1 ii i ii ii i i i i i i - _ _ _ _ _ _ _ - - 一 保障就变得十分困难，哥前该领域的研究还相当的初步q o s 路由技术是 a df l o c 网络中一种提供q o s 保障的方案，通过查找符合q o s 条件的路径来 保障传输数据的服务质量 电源能耗问题电源能耗也是a di - l o c 网络需要面对的一个重要问题过量 的电源损耗不仅会降低发射功率，造成单向链路，还可能因局部节点的过旱 的撤离网络而造成网络分割，形成残桩( s t u b ) 网络，中断通信的进行由 于移动节点的电源十分有限，如何设计节能的协议并尽可能的减少芯片的运 算就变的相当重要，协议和算法应该尽可能简单，额外开销要少 安全性问题。安全性问题是所有网络需要面对的重要问题，也是实际应用所 必须解决的一个问题。无线网络开放的链路十分容易受到攻击包括被动窃 听、主动伪装、信息重发与破坏等一系列的安全闯题都需要解决，分布式的 网络结构和节点的随机运动进一步增加了安全保障的困难。 位置预测与管理。a di - l o c 网络技术中面临的最大困难就是解决节点随机移 动和拓扑结构变化带来的问题，如何获取节点的位置信息，有目的的进行路 由和数据传输具有重要意义基于位置预测的路由技术可以提高路由的有效 性和可靠性，增加路由的成功率，降低报文开销。 t 除此之外，移动组网技术、异构网络的通信、单向链路以及高层的传输服务 等都是a di - i o c 网络的重要研究内容。 a dh o c 网络一种极有前途的无线网络，有着广阔的应用前景军事上的战 地移动网络，民用设施中各种抢险救灾、会议，庆典等临时场合都为a dl - i o c 网 络的发展提供了空问。组建迅速，造价小，抗毁性强等是a df l o c 网络的主要优 点，也是目前a dh o c 网络成为研究热点的重要原因。 1 2a dh o c 路由技术的发展 路由技术在固定网络中的重要性已是众所周知，a dh o c 网络的特殊性进一 步增加了路由设计的困难和网络对路由技术的依赖，路由技术已成为a dh o c 网 络中最急需解决的问题，也是目前研究的难点和重点 动态交化的网络拓扑结构要求路由必须建立及时迅速，有限的无线网络资源 9 山东大学硕士学位论文 liiiiii _ 和电能要求路由协议岿须具有较小的开销和能耗传统的路由技术已无法适应 a d i - l o c 网络动态变化的拓扑结构，必须设计新的适合a d l - i o c 网络特点的路由协 议。 目前，国内外许多相关的大学和科研机构都开始了a dh o c 网络特别是a d h o c 路由技术的研究上个世纪九十年代中后期，各研究机构向m a n e t7 - 作组 提交了许多路由选择协议孔，如卡耐基马龙大学提交的动态源路由d s p t q ，c - k t o h 提交的a b r 【5 1 等这些路由协议各自基于不同的出发点和度量。通过按需机 制解决了动态变化的拓扑结构带来的问题。早期的许多工作都是基于各种路由协 议的性能比较与分析，但因为缺乏统一的评价标准，而且许多路由协议都基于不 同的开发环境与仿真平台。a dh o c 路由协议的性能分析与比较具有很大的局限 性 近几年。随着研究的进一步深入和各种仿真软件的出现( 如n s - 2 、o p n e t 等) ，极大的方便了a dh o e 路由协议的开发和性能的分析比较。在性能分析的 基础上出现了一些针对早期路由协议的改进方案嘲聊1 3 】，这些方案从不同的角度 出发，结合该领域的一些相关技术( 如电源节能、位置定位等) ，对协议中存在 的各种问题提出了改进，提高了路由的有效性和可靠性，使网络豹整体性能得到 了进一步的提高。 q o s 路由技术是一项极具有挑战的工作，在a dh o e 网络中建立完全可靠的 具有q o s 保障的路由几乎是不可能的，主要原因是快速变化的网络拓扑结构和 有限的无线带宽无法提供足够的资源保证。尽管如此，该领域仍然取得了可喜的 成绩，许多基于不同出发点的q o s 路由解决方案已被提出【9 l 【。目前该领域的 研究还刚刚开始，提供可靠的q o s 保障还有相当的困难需要解决。 尽管出现了各种路由选择协议和不同的改进方案，但并不代表a d h o c 路由 技术的成熟。目前尚无m a n e t - r 作组认定的a d h o c 路由协议标准，提交的各 种路由协议都是作为草案( d r a f t ) 加以讨论，因此，a dh o c 路由技术就整体而 言还处于起步阶段，需要迸一步的深入研究和探讨 山东大学硕士掌位论文 第二章a dh o e 网络路由协议 a dh o e 网络自身的特殊性决定了路由协议的特殊性和重要性本章首先从 a d h o c 路由协议的设计要求出发，介绍了一些基本的a d h o c 路由协议，然后分 类详细分析了a dh o c 路由协议的性能和优缺点，最后就a dh o e 路由协议存在 的问题给出了一些性能优化方案。 a dh o e 路由协议包括单播路由协议和组播路由协议，论文主要讨论了a d h o c 单播路由协议，以后如无特殊说明，a dh o c 路由协议都指a dh o c 单播路由 协议。 2 1a dh o e 路由协议概述 a dh o c 网络自身的特殊性使得传统固定网络中的各种路由协议己不再适 用，必须设计新的适用于a dh o c 网络特殊要求的路由协议理想的a dh o c 网 络路由协议需要具有以下几个特点： 分布式路由算法a dh o c 网络是一种无中心分布式结构的网络，为了保证 网络良好的鲁棒性和路由查找的有效性，协议必须采用分布式的路由算法。 较少的路由开销。这主要是保证路由的有效性a dh o e 网络的资源十分有 限，大量的路由报文不仅会造成网络局部的拥塞，还会占用宝贵的无线带宽， 降低网络的带宽利用率。此外，大量的路由报文会还会降低电源的利用率， 这对采用电池供电的a dh o e 网络来说是极为不利的。 具有良好的可伸缩性也就是说，路由协议本身对于网络的大小应该是相对 透明的当网络规模较大时，不能出现网络整体性能的急剧下降 具有自适应性，可适应快速变化的网络拓扑结构。这主要是对路由协议可靠 性的要求a dh o c 网络中节点可以随意移动，网络的拓扑结构不断变化， 因此，路由协议必须能够适应这种变化，并为源节点找到合适的传输路径 较低的电能损耗电池供电的移动终端要求协议具有较少的开销和较低的算 法复杂度，以降低有限的电源损耗，提高电源利用率，从而延长网络生存时 间。 山东大学硕士学位论文 常见a dh o c 路由协议主要有d s d v 、w r p 、d s r 、a o d v 、c g s r 、a b r 等几种孔，其中，d s d v 、w r p 为表驱动路由协议，d s r 、a o d v 为按需驱动路 由协议，c g s r 为分级路由协议，a b r 是一种基于联合度量的路由协议。下面 就这些常见a dh o c 路由协议的基本工作原理和优缺点进行简要介绍 d s d v ( d e s t i n a t i o ns e q u e n c e dd i s t a n c ev e c t o rr o u t i n g ，目的节点排序距离向 量路由协议) d s d v 是一个基于传统的b e l l m a n - f o r d 算法的路由选择算法，通过对路由编 号来避免路由环路的发生【l i 】。d s d v 是典型的表驱动路由协议，每个节点维持一 个到其它节点的路由表，表的内容为路由的下一条节点。d s d v 的创新之处是为 每一条路由设置一个序列号，序列号大的为优选路由，序列号相同时，跳数少的 路由为优选路由。 d s d v 的优点是通过序列号的设置避免了计数到无穷的问题，避免了路由环 路的发生。但由于路由表的维护，节点需要周期性的向相邻节点发送本地信息， 因此开销较大，降低了带宽利用率 w r p ( w i r e l e s sr o u t i n gp r o t o c o l ，无线路由协议) 无线路由协议w r p 是一个以在网络所有节点中都保存路由信息为目标的表 驱动路由协议f 1 2 1 网络中的每个节点维持四个表：距离表、路由表、连接成本 表和报文重发表( m e s s a g er c t r a n s m i s s i o nl i s t ，m r l ) ，通过其相邻节点的最短 路径生成树s s t ( s h o r t e s tp a t hs p a n n i n gt r e e ) ，生成自己的s s t ，然后再向相邻 节点传递更新信息。节点间通过定期发送h e l l o 报文来探测链路是否正常或者是 否有新的节点加入。w r p 通过强迫每个节点必须对其所有相邻节点发来的信息 进行一致性检查来避免无限重复计算的问题，从而减少了当路径中断时出现循环 的情况并加速了路由收敛 d s r ( d y n a m i cs o u r c er o u t i n g ，动态源路由协议) 区别于d s d v 和w r p ，d s r 是一种按需驱动的源路由协议，每个分组的分 山东大学硕士学位论文 i i i i 一 i - 组头中都包含着一条从源节点到目的节点的完整路由信息【4 】源路由协议的最大 优势就在于分组中包含了所有的路由信息，任何中间节点都不需要维持当前路由 信息 d s r 是一种典型的按需驱动路由协议，不需要周期性的发送更新报文协 议还支持主机睡眠功能，节省了网络开锖和电池能量，对于负载小的a dh o c 两 络有较好的性能表现。协议的另一个优点是支持路由缓存和中间主机应答，有利 于快速建立路由并从一定程度上减少了洪泛报文的开销，当然，缓存的引入会增 加网络的开销，中间应答机制还会产生过时路由问题。就整体性能而言，d s r 是比较成功的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 e v e c t o r ，a dh o e 按需距离向量协议) a o d v 是d s r 和d s d v 的一个结合，它采用了d s r 的路由发现和路由保 持反应机制，保持了d s d v 的逐跳路由、序列编号和周期性的更新机制l 。a o d v 与d s r 的区别是a o d v 没有了路由缓存的概念，引入了d s d v 中的路由表，而 且分组中不再带有源路由的信息a o d v 采用按需查找路由机制，是一种按需 驱动路由协议 a o d v 路由协议是基于传统的距离向量的按需路由协议，协议思路简单、 易懂，通过使用目的节点序列号有效的防止了环路的产生和过时路由信息，解决 了传统的基于距离向量路由协议存在的无限计数的问题。 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 g a l g o r i t h m ，临时排序路由算法) t o r a 协议是一种基于反向链路的路由算法唧1 算法采用了类似于“势能” 的概念，对于某一目标节点，网络中每个节点都保留了相对于它的“势能”，势 能可以通过从目标节点的反向广播来获得。离目标节点越远的节点势能越高，目 标节点的势能最低在数据传播过程中，数据包从高势能的节点向低势能的节点 转发，最终流向目标节点当局部链路发生变化时，只需要局部势能调整( 断裂 处节点的势能增加，路由报文沿原路返回一跳) ，这种改变不会影响到全局。反 向链路状态算法具有路由信息利用率高，适应能力强的优点，缺点是要为每一个 山东大学硕士学位论文 目标节点建立一套“势能”数据，占有的节点内存较大，计算复杂度较高。 c g s r ( c l u s t e r e d g a t e w a y s w i t c h r o m m g ，簇头网关交换路由) c g s r 是一种分级结构的路e b 协议，协议中引入了簇的概念【1 4 1 协议根据簇 首选择算法选择部分节点作为簇首，并根据簇首对网络进行簇的划分，簇首负责 簇内节点的路由与通信，簇首与簇首之间通过网关进行通信。簇首并不固定，簇 、，一 首与簇成员在一定条件下是可以相互转化的，具体方法由簇首选择算法决定。 、 c g s r 协议将d s d v 协议作为底层的路由机制，每个簇首维护一个簇成员表，并 周期性的更新表中成员信息。 簇成员 一 簇首 。网关 图2 1c g s r 路由协议的路由机制 d 如图2 1 所示，当源节点s 进行路由时，首先将路由报文交给簇首a ，a 首 先找自身簇成员列表，若目的节点d 不在簇内，则转交给网关c ，继而到达下 一个簇头b ，直至报文转交给目的节点d 。若目的节点n 与源节点s 在同一簇 内，则直接由簇首转发，但s 不能直接转发报文至n ，即使在直接通信范围之内 该协议采用了分层的路由查找机制，当网络规模较大时避免了大量路由查找 报文的泛洪，绝大多数报文只在簇首间进行转发，一定程度上降低了查找报文的 开销，并具有良好的可扩展性缺点是引入了簇的概念，增加了算法复杂度和簇 首的维护开销，在网络规模较小时优势并不明显 a b r ( a s s o e i a t i v i t y - b a s e dr o u t i n g ，基于联合稳定度的路由协议) a b r 是一个基于新的选择度量一联合稳定度的路由选择协议嘲联合稳定 山东大学硕士学位论文 i _ _ _ _ - - _ _ _ _ _ - - _ _ - - _ - _ _ _ _ _ _ _ _ _ _ - 度，也即节点及相应链路在时间和空间上的稳定程度。每个节点周期性的广播一 个信标表明其存在，邻接点收到该报文后，根据路由稳定的时间( 持久性) 和路 由信号的强度( 质量) 作为路由选择的度量。每收到一次信标报文，相应的节点 稳定度就增加一点，稳定度越高，表明节点的移动性越低，相应的路由越稳定 当节点移动引起链路中断时，联合稳定度会重新设置。路由协议采用按需驱动， 包括路由发现和路由重构。 a b r 区别于以上各种路由协议的是采用了新的度量进行路由选择。a b r 选 择的路由具有较高的路由持久性和传输质量，提高了数据的成功传输率，并降低 了路由破裂和重构的次数，减少了因此所带来的开销。a b r 的另一个特点是采 用了局部查找机制，减少了路由查找的开销和路由重构时间。协议的缺点是周期 性信标报文的发送和稳定度计算会带来一些额外开销，带宽利用率和电源利用率 会有一定的下降，局部查找一定程度上弥补了这种开销 方便进一步的研究，我们给出以上几种a dh o e 路由协议的实现机制比较， 这些协议也是目前研究最多的典型a d h o e 路由协议代表，见表2 1 这里我们有必要对复杂度的概念进行一下简要介绍。时间复杂度和通信复杂 度是路由协议评价的两个重要指标，鉴于a dh o c 网络的低开销和低能耗需要， 复杂度高的路由协议将对网络整体性能带来较大影响。时间复杂度的定义为执行 一次协议操作所需要运行的步数( 跳数) ，通信复杂度是指执行协议操作所需要 传送的信息数，表2 1 所指的皆为最差情况下的复杂度。 对于d s d v 和c o s r 两种表驱动路由协议，链路故障时将引起路由表的更 新，路由表中信息的传播最坏情况下将穿越整个网络，所以时间复杂度为网络直 径数量级的，即o ( d ) 。w r p 使用的是生成树算法，所以时间复杂度为生成树 高度数量级的，即0 ( h ) 对于表驱动路由算法，一个节点或链路的改变将引起 整个网络内所有节点的路由表更新，所有通信复杂度都为网络节点数数量级的， 即0 ( n ) d s r 、a o d v 、t o r a 和a b r 四种为按需路由协议，源节点发出路 由查找分组后，目的节点需要返回一个路由应答信息，路由报文需要来回穿越网 络两次，因而时间复杂度为2 d 数量级的，即o ( 2 d ) ，路由查询是在各个节点分 布式同时进行的，所有通信复杂度为o ( 2 n ) 。 山东大学硕士学位论文 表2 1 中有两点问题需要注意，首先对于按需驱动路由协议，存在路由建立 与路由维护两种机制，其时间复杂度和通信复杂度是不同的( 如d s r ，路由维 护时若存在缓存路由，时间复杂度为o ) ，为方便比较，表中指的都是路由建立 过程的复杂度。其次，按需路由协议中，目的节点发出的应答报文是按己建立的 路由进行反向传输的，一般不会在全网中进行洪泛，所以严格的说通信复杂度是 小于0 ( 2 n ) 的。 表2 1 典型a dh o c 路由协议实现机制比较 d s d vd s ra o d vt o r aw r pc g s ra b r 时间复杂 o ( d )o ( 2 d )o ( 2 d )o ( 2 d )o ( h ) o ( d )o ( 2 d ) 度 通信复杂o ( n )o ( 2 n )o ( 2 n )o ( 2 n )o ( n )o ( n )o ( 2 n ) 度 逻辑结构 平面 平面平面平面平面 分级 平面 驱动方式表驱动按需按需按需表驱动表驱动按需 路由测度最短最新最短路径最短最新最短路径最短路径最短路径联合最稳 路径路径最短路径 路由断裂重新查找缓存路由源节点重链路翻转重新查找重新查找局部修复 与维护路由表 或重建建路由修复 路由表路由表 路由缓存无有无无无无无 2 2a dh o c 路由协议的分类性能研究 目前出现的a dh o c 路由协议远远不止以上几种，为了方便进一步的分析研 究。通常对路由协议进行分类，并对它们的性能进行比较分析。a dh o e 网络路 由协议根据不同的分类原则可以从多个角度进行分类。本文从以下四个方面进行 分类研究，对不同类型a dh o c 路由协议的性能进行分析。 按路由获取的时机。可分为表驱动路由协议、按需路由协议和混和路由协议。 按算法类型，可分为基于距离矢量的路由协议，基于链路状态的路由协议， 基于源路由的路由协议和基于反向链路的路由协议，还有一些协议采用了混 和算法 按逻辑组织结构，可分为分级结构路由协议和平面结构路由协议 山东大学硕士学位论文 i l l _ 按协议的功能，可分为是否支持q o s ，是否支持多播与组播功能，以及是否 支持单向链路功能等不同路由协议 下面分别就四种不同分类原则对a dh o c 网络路由协议的性能进行详细地比 较分析。 2 1 1 按路由获取时机分类 a dh o c 网络最常见的分类法就是将协议分为表驱动路由协议和按需驱动路 由协议【3 l 。表驱动路由协议又称为预先路由协议，路由协议通过定期的路由信息 交换来维持和更新一张关于网络拓扑和各个节点信息的路由表，节点之间通过互 相发送周期性的“问候报文”参与路由信息交换。它的优点是通过节点维护的路 由表可以及时的了解网络拓扑结构的变化和节点位置信息在数据发送时可以直 接根据路由表中的信息进行数据传输，不需额外的路由建立等待时间，常见的表 驱动路由协议有d s d v 、w r p 、f s r 、o l s r 等。 ， 在带宽资源有限，拓扑结构不断变化的a dh o c 网络环境中，每一个节点都 维护一张全网路由信息表是没有必要的，考虑到可扩展性，甚至是不可能的。而 且，这些给网络带来大量开销的路由表中的信息大都是无用的，这也是表驱动路 由协议的最大缺点。网络规模越大，节点移动越迅速，这种缺点就越为明显，资 源的浪费就越严重。按需驱动路由就是针对这种情况提出的，按需驱动路由只在 有数据发送时才进行路由的查找与建立，大大的节省了路由表带来的开销问题。 按需路由协议是a dh o c 网络特有的路由协议类型，它可以降低表驱动路由 协议中不必要的路由查找开销，提高网络的吞吐量和带宽利用率。按需路由协议 主要有路由发现和路由维护两个过程构成。当某节点需要获取到目的节点的路由 时，路由发现机制被激活节点采用洪泛的方式向相邻节点发送路由请求报文， 中间节点根据协议的具体机制进行部分获全部转发，直到目的节点收到该请求报 文然后，目的节点根据请求报文的信息选择一条合适的路径反向转发路由应答 报文，当源节点收到完整的应答报文后，整个路由建立完毕随着拓扑的变化， 当路径上的某个链路发生中断时，路由维护机制被启动 按需路由协议是目前a d h o c 网络中研究最广、种类最多的一类路由协议， 1 7 山东大学硕士学位论文 - - - - _ - _ _ _ _ _ _ _ _ _ - - _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ 一i _ _ _ _ _ _ - _ _ - - _ _ - _ - 常见的按需路由协议有d s r 、a o d v 、t o r a 、a b r 、s s a 等 图2 2 为按需驱动路由的路由建立示意图。 。烈二- 少。 混和路由协议是对按需路由协议和预先路由协议的综合它将一个较大的网 络分成若干较小的区域。在小范围的局部区域内使用表驱动路由机制，区域之间 采用按