（计算机应用技术专业论文）基于节能的aodv路由协议的改进.pdf

硕士学位论文 囊l a s t e r st h e s i $ 中文摘要 移动a dh o c 网络是一种高度动态的无线网络，路由成为其实际应用中必须解决 的关键问题。目前的路由协议在节能上大多表现得不好。由于组成非固定设施网络 a dh o c 网络的移动节点的电池能量十分有限，因此如何在a dh o e 网络中高效的使用 能量就变得非常重要。为了使a dh o e 网络的生存时间最大化，网络流量应该通过那 些既可以最小化总传输功率，又能避免使用低能量节点的路由来传送。此外，考虑 到a dh o e 网络的节点的移动性以及由此造成的网络拓扑的变化，反应式路由协议是 可选的最好的a dh o e 路由协议。但是，大多数已有的能量自适应路由算法都不符合 上述要求。虽然有些能量自适应路由算法试图在两个目标之间进行平衡，但它们没 法真正在反应式路由协议上进行应用。为此，在a o d v 协议的基础上本文提出一种基 于节能的改进路由协议。该协议提出了能量分级策略，并且改进了a o d v 算法的h e l l o 机制，从而尽可能的满足了最小总能量传输功率和能量消耗不平衡两方面的要求。 仿真结果和性能分析表明，在大型a dh o c 网络组网中，该路由协议能显著提高路由 效率，延长了网络的生存时间，同时提高了数据包的有效传输率。 关键词：a dh o e ；a o d v ；能量分级；节能；网络生存时间；最小化总传输功率； 低能量节点 a b s t r a c t a dh o em o b i l en e t w o r ki sah i g h l yd y n a n 正ew i r e l e s sn e t w o r k s ，r o u t i n gh a sb e e ni t s k e yi s s u e sw h i c hm u s tb ea d d r e s s e di nt h ep r a c t i c a la p p l i c a t i o n m o s tc u r r e n tr o u t i n g p r o t o c o l sp e r f o r mn o t w e l la te n e r g y - e f f i c i e n t a dh o en e t w o r k sa r en o n - f i x e d i n f l 峦t r u c t u r en e t w o r k sc o m p o s e do fm o b i l en o d e s a st h em o b i l en o d e sh a v ev e r y l i m i t e db a t t e r ye n e r g y , h o wt os p e n de n e r g ye f f i c i e n t l yi na dh o en e t w o r kh a sb e c o m e v e r yi m p o r t a n t i no r d e rt om a x i m i z et h el i f e t i m eo fa dh o en e t w o r k s ，t r a f f i cs h o u l db e s e n tv i aar o u t et h a tc a nb ea v o i dn o d e sw i t hl o we n e r g yw h i l em i n i m i z i n gt h et o t a l t r a n s m i s s i o np o w e r i na d d i t i o n ，c o n s i d e r i n gt h en o d e s m o b i l i t yo fa dh o en e t w o r k , o n - d e m a n dr o u t i n gp r o t o c o l sa r ep r e f e r r e df o ra dh o en e t w o r k s h o w e v e r , m o s te x i s t i n g e n e r g y - a w a r er o u t i n ga l g o r i t h md o e sn o tm e e tt h o s er e q u i r e m e n t s a l t h o u g hs o m e e n e r g y - a w a r er o u t i n ga l g o r i t h ma t t e m p t st oc o m p r o m i s eb e t w e e nt w oo b j e c t i v e s ，t h e y h a v ed i f f i c u l t yi ni m p l e m e n t a t i o ni n t oo n - d e m a n dv e r s i o n t ot h i se n d ，b yi m p r o v i n gt h e a o d vp r o t o c o l ，ar o u t i n gp r o t o c o l sb a s e do ne n e r g y - e f f i c i e n ti sp r o p o s e di nt h i sp a p e r t h i sp r o t o c o lp r o p o s e dc l a s s i f i c a t i o ns t r a t e g yf o re n e r g y , a n di m p r o v e dt h eh e l l o m e c h a n i s mi na o d v , w h i c h , a sf a ra sp o s s i b l et om e e tt h et w or e q u i r e m e n t so f m i n i l n u l nt o t a le n e r g yt r a n s m i tp o w e ra n di m b a l a n c eo fe n e r g yc o n s u m p t i o n s i m u l a t i o n r e s u l t sa n dp e r f o r m a n c ea n a l y s i ss h o w st h a ti na dh o en e t w o r k , t h er o u t i n gp r o t o c o lc a n s i g n i f i c a n t l yi m p r o v et h em u t i n ge f f i c i e n c ye x t e n dt h el i f e t i m eo ft h en e t w o r k , w h i l e i m p r o v i n gt h ee f f e c t i v ed a t ap a c k e td e l i v e r yr a t i o k 昭w o r d s ：a dh o e ；a o d v ；e n e r g yl e v e l s ；e n e r g y - a w a r e ；l i f e t i m e ；m i n i m u m t r a n s m i s s i o np o w e r ；l o we n e r g yn o d e 硕士擘位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名： 驰名 刁主铂 日期：加哆年6 月加日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版。，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同意华中 师范大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 作者弛：碧磊锄弛汛之乙 日期：扣四年占月i o 日日期：) o - 7 年6 月i o 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程一，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库 中全文发布，并可按“章程”中的 规定享受相关权益。圄童途塞握交蜃溢盾；旦坐生；旦= 生；旦三生发查：一 作者签名： 日期：如。7 年月f 。日日期罱 硕士学位论文 h l a s t e r st h e s i s 引言 在无线网络诞生的3 0 多年时间里，它在计算机领域里的发展可以说是一日千 里，特别在最近的十年里，无线移动通信技术的进步更是有目共睹。当前的无线移 动网络主要有两种：一种是介于固定网络设旌的，这种网络被称作无线局域网 ( w l a n ) ：另一种不需要固定网络设施的支持，被称作自组织网( a dh o c ) 。这种 网络不需要专门的路由器，网络中的移动节点通过自身的转发来进行通信。任何节 点自身同时承担路由器的功能，在网络中搜索并维护路由。自组织网最常用于灾害 救援，军事，移动会议等方面。 路由器则是提供一种方式将一个网络的数据包传送到另一个网络。这种方式就 是路由，路由实际上就是数据包发送的路径，而路由协议则是事先约定好的指导数 据包发送的规定与标准。 路由协议的工作主要是在路由器之问维护路由信息，将路由信息在路由器之间 传递，保证所有的路由器都知道如何到达其他路由器。路由器创建并维护路由表， 并由此描述网络拓扑结构。由于不同类型网络的特点不同，如何选择一个适合的路 由协议成为研究的重点。路由协议工作在传输层和应用层，路由协议作为t c p i p 协议栈中的最重要的成员之一，它的性能直接关系着这个网络的性能。 而对于自组织网来说，路由的选择更加重要。由于自组织网的特点，在一个移 动节点可通信范围内的节点都可以与它组成一条路由，因此，相对于固定设施的网 络来说，自组织网的路由选择更加复杂。 目前的路由协议大致分为这样的3 类，先验式( p r o a c t i v e ) 路由协议，反应 式( r e a c t i v e ) 路由协议还有混合式路由协议。先验式路由协议协议包括有：d s d v 、 c g s r 、w r p 等，反应式路由协议的按需路由协议有：d s r 、a o d v 、l m r 、t o r a 、a b r 、 s s r 等，而混合式路由协议主要是将两种协议的思想相综合而形成的路由协议。 其中a dh o c 按需距离矢量路由协议( a dh o co n d e m a n dd i s t a n c ev e c t o r r o u t i n g ，a o d v ) 是应用于自组织网的路由协议，它支持单播和多播路由，它属于 反应式路由协议，也称作按需协议。a o d v 路由协议是目前应用最广泛的a dh o c 路 由协议之一 由于a dh o c 网络特殊的用途以及网络环境，它对于能量使用的策略成为决定 a dh o c 应用发展的重要因素。为了减少a dh o c 网络节点的能源消耗n m h l 小瑚，对与 路由协议相关的物理和数据链路层以及网络层的相关研究工作已经展开并取得了 很多有效的成果。物理层可以根据节点之间的距离调整发射功率来节约能源。而在 硕士学位论文 m a s t e r st h e s i s 数据链路层，睡眠模式的运作使得节约能量成为可能。 提出基于节能的a dh o e 路由协议的目的是为了最大限度扩展网络生存时间。 网络生存时间的定义是网络中最后一个节点耗尽自身电池能量的时间，有时候也是 某些关键节点耗尽的时间。因为某些关键节点一旦死亡，整个网络可能产生分区或 者通信中断。基于节能的路由协议从整个网络和单个节点两个角度来考虑能量的消 耗。从整个网络的角度来看，最佳路由就是总传输功率最小的路由。然而从单个节 点的角度来看，最佳路由绝对是避免持续使用低能量节点的路由。我们很难同时实 现这两个目标。最小化总传输功率往往趋向于选择最小跳数的路由。但是，如果最 小跳数路由中一直包括某个较低能量的节点，这个节点的能量会比其他节点更快的 耗尽使得整个网络的生存时间减少。 本文就是在a o d v 路由协议的基础上，综合的考虑了最小化总传输功率和避免 低能量节点，并且将选择最小化总传输功率路由的方法进行了优化，从而提出一种 新的更加节能的a dh o e 路由算法。 2 硕士学位论文 m a s t e r st h e s i s 1 1 什么是a dh o c 网络 1 a dh o c 网络 a dh o c 网络【1 】是一种由移动主机构成的，基于无线基础设施支持的，由网络节 点组成的移动网络。a dh o c 网络最先是应用在军事方面的，研究是起源在战争环境 下的无线网络的数据通信的项目，这个项目是由d a r p a 资助的，后来，又在1 9 8 3 年和1 9 9 4 年进行了抵抗破坏的自适应的网络s u r a n ( s u r v i v a b l ea d a p t i v en e t w o r k ) 和全球定位系统g l o m o ( g l o b a li n f o r m a t i o ns y s t e m ) 项目的研究。在无线的技术 和终端技术的不断发展的情况下，a dh o c 网络也开始应用在民用方面上，在需要在 - 无线基础设施的地方进行信息交换时，搭建a dh o c 网络就会非常方便地实现这些 功能。 在a d h o c 网络中，如果两台移动主机( 图1 1 中a 和b ) 的信息交换范围彼此 可以覆盖时，它们就能直接信息交换。但是由于移动的功率有限，信息交换的范围 也有限，那么当两个距离比较远的主机( 图1 1 中的a 和c ) 需要进行信息交换的 时候，只能通过它们之间的移动主机b 来进行转发，如图所示。因此在a dh o c 网 络中，主机同时还兼任路由器的功能，同时担负着路由和信息转发的工作。在a dh o c 网络中，由于每个主机的信息交换范围有限，那么路由只能由多跳组成，信息只有 通过多个主机的代发才能到达目的地。其结构如图1 2 所示。 。一+ 一、，一。一j 一一一、， 、， 。 。 ff 器墨1l； j。aj bic i ，。+ 、一，、一。，、t ，一， 图1 1 主机b 作为主机a 和主机c 的中转 3 彳 基* 乏7 ， 自# 烈一 舀 台式机笔u ! 车1 m “ 自 机h $ i m a c 图1 2a dh v c 网络结构 a dh o c 网络被看作是移动信息交换与计算机网络的交叉。移动主机一般是便携 式计算机、个人数字助理( p d a ) 等移动装置。a dh o e 是不同于普通i n t e r n e t 里面 的移动i p 网络的。移动的计算机能经过固定的有线网络、无线链式结构和拨号线 路等方式接到i n t e r n e t ，在移动i p 网络里面，但a d h o c 网络中只存在也只能用无 线链路这种连接方式接入网络。移动主机会最先经过旁边的信号发射塔接到网络， 在移动i p 网络中，接下来，信号发射塔和信号发射塔( 代理和代理) 之间的连接 都是有线的，这些有线的却仍然用的是i n t e r n e t 中的老的路由协议，如r i p 等。 可是a dh o c 网络没有这些设施的支持。另外，普通移动i p 网络中移动计算机没有 路由这个功能，只是一个普通的信息交换计算机。网络的结构不会这样改变，当移 动计算机从一个信号发射塔的范围下移动到另一个信号发射塔的范围里时。但是如 果藐们移动a dh o c 网络中移动计算机，结构就会发生改变。 1 2 a dh o e 网络的特点 a dh o c ，有一群移动的计算机组成的，为了在特殊环境下进行某种特殊用途， 而临时组建的一种网络。由于a dh o c 不需要任何固定设备，随时随地自发进行组 织，网络中的每个结合点的地位都是平等的，没有中心的。a dh o c 使用的是两种 技术，移动信息交换技术和网络。一方面，它采用无线的方式进行信息交换，各个 移动主机可以自由的移动位置；另一方面，欣喜的交换用的是计算机网络中的信息 硕士学位论文 m a s t e r st h e s i s 交换机制，因此每个网络结合点都会有移动计算机的功能，还有路由器的功能。 a dh o e 有很多特点，我们可以这样来看： 它的结构变化很快，而且经常变化。a dh o e 中，移动计算机的移动是非常随机 的，它们可以从这儿移动到那儿，也可以断开电源或者插上电源。如果没有线路设 备信号功率的变化，或者线路设备之间信号的干扰或者地势的缘故，都会产生a dh o c 结构的变化，而且我们不知道这个变化几时会发生。 a dh o e 需要很多个中间的主机进行很多次的代发。例如，主机之间的距离在他 们可以进行信息交换的范围内，他们会直接进行信息交换，但是如果他们之间的距 离在信息交换的范围之外，他们就只能通过其他的主机进行代发。这就是与普通的 网络的不同，普通的网络通过路由器来做这些事情，a dh o e 通过他的主机来做这些 事。 信息交换的速度不是很快。由于无线设备的支持，a dh o e 所使用的信息交换方 式很不稳定，而且由于相互间的干扰，很难达到很好的速度，更加不可能达到一个 既稳定又很有速度的地步。这是个比较难解决的问题。 单向的连接。这个问题很简单，一个主机的覆盖范围非常小，但另一个主机的 覆盖范围却非常大，那么，当两台主机的距离在较小覆盖范围的主机的范围之外， 却在较大覆盖范围的主机的范围之内时，一台主机可以收到另一台主机的信息，另 台却无法收到这一台的，就造成了两台计算机之间的单向的连接。 a dh o e 技术从产生以来，其路由协议的设计就成为重要的问题。但是由于他的 一些特点不能借鉴固定网络的路由协议。需要很多次的中间计算机的代发，信息交 换的速度不快，一个方向的连接使得固定网络的路由协议不能直接在a dh o c 上使 用。移动的主机使得结构不断变化，而固定的网络不会准确的及时的反应当时的结 构，而且控制的消息会很频繁的进行发送，占用本就很慢的信息交换速度。最后， 固定的路由协议不会产生一个方向的连接，这也不适合a dh o c 协议。 1 3 a dh o e 网络的应用 1 9 9 7 年i e t f 成立了一个专门研究a dh o c 的工作组m a n e t ( m o b i l e a dh o c n e t w o r k s ) ，专门负责制定，开发，研究a dh o c 网络的标准。在最近几年，移动信 息交换和移动计算机技术发展得很快，使得a dh o c 超越最初的军事方面应用的思 路，也应用到了民用设施上，它的应用场合有以下这些l l l ： 5 1 31 地震等灾害方面 当人类遇到一些天灾人祸的时候，例如前年的冰雪灾害，大面积的停电，去年 的汶川大地震，在这种自然灾害的情况下，固定的设旖没有办法进行正常的工作， 那么只有使用a dh o c 这种技术。提供临时信息交换，这对抢先韭菜有很中啊歌谣 的意义。 1 3 2 军用方面的 军用方面的是a dh o c 起先希望进入的领域。因为在战时情况下，没有办法架 设固定的设备，并且在进入新区域后快速建立信息交换的渠道方面都是非常有用 的。在固定的设备遭到损毁时，a dh o c 可以很快重新组织进行信息交换，可以在作 战时获得很大作用，做出很大的贡献。 ki 不能大，便于移动。这些s e n s o r 会自己组成一个k dh o c ，用来一个接一个的转发， 最后到达控制的中心。在战争时，指挥部需要了解各支部队的情况，以及命令的下 发，给养的供给，这些s e n s o r 可以作为信息的收集点，通过转发汇合到一起，形 成一个完全的信息。在生化战争中，利用s e n s o r 及时的接收到爆炸的信息，发送 到指挥部，指挥部就会很快做出命令，尽可能的减少不必要的伤亡。而且在核爆试 验，或者一些生态环境监测中可以给出更大的应用，这些环境下也只能用s e n s o r 这种方式才能比较好的进行信息的交换。 1 3 4 移动会谈 图14 传感器网络 现在，智能手机，上网本，i p o d 等多媒体设备成为人们工作，时尚的必备物品。 如何利用这些设各进行即时的通讯就成为很重要的一个问题。利用a dh o c 就能很 轻松的达到这个目的。 1 3 5p e r s o n a la r e an e t w o r k i e e e s 0 2 1 5 提出个人域网络p n ( p e r s o n a la r e an e t v o r k ) 的概念，这些概念 是在下面这种情况下来进行应用的。我拥有一台p d a ，但此p d a 不能直接接入 i n t e r n e t ，我们就可以使用a dh o c 的方式转发至可以接入i n t e r n e t 的设备上，来 接入网络。 1 3 6 其它应用 a dh o c 网络还有很多应用的地方，例如与手机的蜂窝移动通信想结合，a dh o c 有转发的能力，那么可以通过多跳的转发，将蜂窝的一个一个c e l l 的范围进行延 伸。那么应用k dh o c 技术后，蜂窝的c e l l 的范围可以大大延伸，可以节省一定得 架设基站的费用。 1 4 与其他的系统相比较 我们来介绍几种常见的移动通信系统。 1 a 1c e l l u l a r s y s t e m 蜂窝系统就是我们用的晟多的手机的通信系统。这种系统是模仿蜂窝的结构。 蜂窝是一个一个像小房间一样的小蜂房组成的。每个蜂房里面都有一个基站。每一 个蜂房里面的手机用户都是通过基站来进行信息的交换。基站之间的通信是通过有 线的方式来进行的。所以蜂窝系统与a dh o c 是决然的不同的，它们的表现形式， 通讯方式都是不同的。 m 誊 ? 。 相基 图l _ 5 蜂窝网络 1 4 2c l u s t e r s y s t e m 集群系统，顾名思义，也是一种基于有线的系统。规模不会太大，也不像蜂窝 系统那样可以提供语音服务。 1 4 3 卫星通信系统 卫星通信系统也是比较常见的，例如电视，卫星电话，卫星定位等等很多的服 务都靠卫星通信系统来支持。每个卫星都会覆盖到地球的一个区域。有的卫星是相 对静止卫星，它始终在地球上一个固定区域的上空，相对静止。中轨道和低轨道主 要是根据绕地半径的不同，覆盖的区域也会不同。但是卫星通信系统发射的费用非 常高，而且通信的延迟很大。 *盛一 ，1， 基一 硕士学位论文 m a s t e r st h e s i s 以上提到的移动通信系统都是需要基于有线的。很多的设备，例如基站，卫星， 发射塔之类的。这样的设备消耗的资源是相当的大，电力，维护的人力，会造成非 常大的成本。要建设这些固定的设备，形成一定的规模也需要很长的时间。但是a d h o e 就有这样的好处，它是自组织的，主机之间通过一定机制在很短的时间里快速 的组成一个a dh o c 网络。而且，上面提到的那些通信网络，那些移动终端之间根 本不会直接进行通信，而都是通过基站，卫星等设备进行转发，而a dh o c 里的主 机都是既作为发送接收消息的终端，又作为转发数据的路由，这两种功能的设备。 但是由于a dh o c 其自身拓扑结构变化迅速，不能保持很稳定的数据交换速率，因 此不宜将其用作语音或者视频等实时通讯的应用。 2 a dh o c 路由协议 a dh o c 网络的路由协议【2 j ：现有的路由协议大致分为这样的3 类，先验式 ( p r o a c t i v e ) 路由协议，反应式( r e a c t i v e ) 路由协议还有混合式路由协议。 先验式路由协议也被称作表驱动路由协议，它让每个节点都维护一张路由表， 里面存放着从自身到其他节点的路由以及相关信息。当网络拓扑结构发生变化时， 节点会自动检测到，并向网络广播更新信息，收到这些信息的节点便会根据这些信 息更新自己的路由表，从而保证所有的路由信息都是及时的，一致的，准确的。一 旦某个节点需要发送报文，马上可以后的到达需要发送到几点的准确路由。但这样 带来一个问题，虽然这样一种路由协议时延较小，但是由于要经常的广播更新消息， 使得整个路由协议的开销变得很大。d i s t a n c e - v e c t o rp r o t o c o l 就是这样一种协议。 在先验式路由协议中，每一个被发送的报文都会马上知道到达目的节点的路径，不 会产生任何的延迟。但是由于这种路由协议需要周期性的进行广播来更新路由，这 种做法非常浪费带宽，特别在a dh o c 这种带宽不大，而且不稳定的情况下。但是更 新的周期又不能太长，这样会造成路由信息的不准确。 反应式路由协议，也称为按需路由协议，这种算法只有在需要发送数据的时候 才会去查询路由。在这种路由协议之中，节点是不会维护一个即时更新的路由表的， 而是当需要发送数据的时候，由源节点发起一个路由发现过程，寻找到需要的路由。 d s r 、z o n er o u t i 吨p r o t o c o l 、a o d v 这些都属于反应式路由协议。这类路由协议的 特点是需要的带宽较小，但是平均时延大。平均时延大是因为当发送数据的时候路 由表中查到的路由不一定是最新的，需要再次查找的缘故。 9 硕士学位论文 m a s t e r st b e s i s 反应式路由协议与先验式路由协议相比较，反应式路由协议有较小的开销，但 是数据传输的延迟较大。而在a dh o c 网络中，路由的问题比较复杂，无论是反应式 还是先验式的路由协议都有较明显的弱点，无法根本解决路由问题。由于a dh o c 网 络拓扑结构变化快，如果仅适用先验式路由协议，就会产生很多的控制包，充斥整 个网络，造成网络的阻塞；但如果只采用反应式路由协议，每个报文的发送都需要 查找路由，如果偶然碰到一组报文的目的节点路由都不存在于路由表中，就会对每 一个报文都发起路由查找过程，这也会造成相当大的延迟。因此，综合两种路由协 议的优点的混合式路由便产生了。它在局部使用先验式路由，以保证路由信息的准 确，也减小了控制包广播的范围，但在目的节点距离较远时，便采用反应是路由， 这样大大减小了路由协议的开销，也使得发送数据包的延迟得到了改善。 下面我们对几种主要的a dh o c 路由协议进行介绍嘲： 2 1 目的序列距离矢量路由协议( d s d v ) 目的序列距离矢量路由协议( d s d v ) 是对距离矢量路由算法( b e l l m a n f o r d r o u t i n ga l g o r i t h m ) 的改进。距离矢量路由算法( b e l i m a n f c l r dr o u t i n ga l g o r i t h m ) 也就是最大流量演算法( f o r d - f u l k e r s o na l g o r i t h m ) ，它属于距离向量协议中的 一个算法，如r i p ，b g p ，n o v e l li p x ，i s oi d r p 。使用该算法的路由器必须拥有一 张距离表，一个一维的数组，也是一个向量。这个距离表拥有每个节点最远和最近 的距离。这个距离表里的信息会根据邻居节点信息的改变而更新。表中数据的数量 等于网络中节点的数量减一，即除去自身。距离表中，列表示与其直接相连的节点， 而行表示网络中所有的节点。每一条数据包括从该节点到达所有网络中其他节点的 路径以及距离或者时间。这个距离或者时间被我们称为传输的成本。 d s d v 对b e l l m a n - - f o r d 路由算法进行了如下改进： 在d s d v 中，每个节点都必须为自己维护一张路由表。路由表中的信息主要有： 目的节点，跳数以及目的节点序号。目的节点需要时由目的节点分配的，主要用来 判断该路由是否过时，由此可防止路由环路的产生。每个节点会周期性的与邻居节 点进行路由信息的交换，另外，路由表的中路由条目的改变也会触发这一行为。路 由表更新有以下两种方式：一种为全部更新，即更新信息会更新整个路由表，这种 主要是用在网络拓扑结构变化特别快的情况；另一种为部分更新，更新信息中只包 括变化的部分，这种主要是用在网络拓扑结构变化比较慢的情况。假如在d s d v 的路 由表里发现有多条到达同一目的节点的路由时，只使用序列号最大的那条，如果序 列号也相同，便选择跳数最小的那条。对于具体的情况，当一个没有路由的分组到 1 0 硕士学位论文 n 【a s t e r st h e s i s 达节点后，首先节点会将它放入缓存，同时发出路由查询包，然后等待，直到接收 到路由响应包。如果没有找到路由的分组过多，而路由查询无法跟上进度，造成缓 存的溢出，那么新来的分组就会被丢弃。 2 2 动态源路由协议( d s r ) d s r q 是基于源路由概念上的按需路由协议。各个节点都需要存储该节点的源路 由的路由缓冲器。当发现新路由的时候，也随之更新缓冲器中的内容。 d s r 路由协议主要有两个过程：路由发现，路由维护。当一个节点需要发送数 据时，它会首先检查路由缓冲期中是否存有到达目的节点的路由。如果存在该路由， 即调用此路由发送数据，如果没有，源节点立即发起路由发现程序。 路由维护主要通过发送路由报错包( r o u t ee r r o r ) 和确认包来实现。一旦在 链路层发现传输问题，便会立刻发送一个路由报错包。当节点收到报错包后，该节 点会从路由存储缓冲器删除包含该出错跳的路由。确认包主要用来验证路由连接， 以保持连接的正确运行。 2 4a dh o c 按需距离矢量路由协议( a o d v ) a o d v 5 】是将d s r 协议与d s d v 协议思想的综合。它既有d s r 协议中的路由发 现和路由维护等机制，也有d s d v 中多跳间的路由选择，序列号高低比较，以及 周期性发送路由更新信息等机制。但它们之间也有很多不同，a o d v 不保存完整 的路由表，而只保存需要使用的路由表，使用按需的策略来管理路由。这是a o d v 对d s d v 的重大改进，这个改进会大大减少路由广播的次数。而与d s r 相比，a o d v 的优点是源路由不包含在每一个数据包里面，这样也会大大减小协议的开销。 同时，由于a o d v 是完全的按需路由协议，不需要参与路由的节点是不需要保存 任何路由信息的，这样也减少了这些节点的能量消耗。 2 5 无线路由协议( 卿) 无线路由协议( w r p ) 是用来维护网络上所有节点的路由信息的一种路由算法。 所有的路由信息都是基于表的，因此每一个节点都需要保存距离表，路由表，开销 表以及信息转发表等内容。 节点之间通过路由信息更新包来通知其他节点链路的变化情况。w r p 中，节点 存储到每一个目的节点的距离以及每一跳的路由信息。w r p 是一种比较特殊的路由 算法，它强迫每一个节点检查所有邻居节点发送的消息记录来避免反复计算直至无 硕士学位论文 m a s t e r st h e s i s 穷的情况。这样做的好处是，消除了环路现象，并且在链路断开时可以使路由更加 快速的收敛。 2 6 群首信关切换路由协议( c g s r ) c g s r 的特别之处在于它的寻址方式和网络的组织。c s g r 有不只一种路由选择 方式，并且它会对节点进行分群。在每一个群里面设置一个群首，通过群首来控制 群内节点。从而将各个群隔离，并通过这种方式分配路由和带宽。而信关就是两个 相邻群之间能够通讯的节点。群首信关切换路由协议的工作方式是，节点发送数据 包时，现将数据包传送到群首，然后通过信关传送到另一个群首。这样一步一步的 传送直到数据包被传送到目的节点所在的群首。最后，数据包被群首传送到目的节 点。因此，根据此机制，每个节点都必须维护一个群成员表还有一个路由表。而群 首方式的缺陷在于，如果群首的切换非常频繁时，节点就会忙于选择群首，而不是 关注于数据的转发，这样非常影响路由协议的效率。因为这个缺陷的缘故，另一个 协议又被提出，这就是最小群变化协议( l e a s tc l u s t e rc h a n g e ) 。在使用l l c 时， 当群内有两个群首或者一个节点远离所有群首的通讯范围时，群首才会切换。 2 7 几种路由协议的优缺点比较 很多研究者对a dh o c 路由协议的性能进行了分析比较，我们以一组研究数据 为例圆来说明几种路由协议的优缺点。下面是以分组投递率和路由开销为性能指标 对以上路由协议进行比较。 分组投递率就是接受端接收到所有分组数量与发送端发送所有分组数量之比。 分组投递率从一定程度上反映了该网络能支持的最大吞吐量，可以在一定程度上体 现被评价协议的完整性与正确性。 路由开销则是仿真中所传输的路由控制包的数量。路由开销主要用来对路由协 议的可扩展性、对网络拥塞的适应能力以及协议工作的效率进行评价。一般来说， 路由开销过大会使路由协议的效率变低，从而失去可扩展性。表l 中显示的是由测 试数据所得的对几种常用的路由协议的分组投递率与路由开销的比较。 表2 14 几种a d h o e 路由算法的性能比较 路由算法分组投递率路由开销( 分组) d s d v7 9 7 1 d s r1 0 0 3 t o r a9 8 1 2 0 0 1 2 硕士学位论文 l a s t e r st h e s i s 我们可以看到，对于分组投递率来说，在同样的测试环境下，反应时路由协议， 如d s r 、t o r a 、a o d v ，它们的分组投递率较高，接近l o o 。对比而言，d s d v 的分组 投递率最低，只有7 9 。这是由于d s d v 协议只为目的节点维护一条路由，因此，当 该路由失效后，无法及时寻找到替换的路由。 对于路由协议开销而言，四种路由协议的差别明显。由于几种按需路由协议的 路由机制特殊，它们的路由开销与节点的移动性成正比，同时也与网络负载成正比。 但是对于先验式路由协议d s d v 来说，它的的路由开销与节点的移动性无关。而且 d s r 与a o d v 两种协议的运作机制较为相似，因此体现出的路由开销也极为相似。 1 3 3 a o d v 路由协议算法描述 a o d v 路由协议“是一种按需的改进的距离向量路由协议，a o d v 路由协议可以在 h dh o c 移动网络中进行单播、广播或者多播。当源节点需要一条通往目的节点的路 径时，它在网络中发起一次路径发现过程。当找到一条路径或者所有可能的路径都 被检查过后，路经发现过程结束。路径一经建立，就被路由表维护起来，直到路径 不再需要或者路由失效或者超过生存期。 a o d v 使用广播的路由查找机制。除了源路由，a o d v 还依靠中问节点来动态建 立路出表项。该协议还借用d s d v 中的目的序列号机制，每个节点维护一个单调递 增的序列号计数器，用它来作为新路由代替缓存中的旧路由的判断标志。 a o d v 路由协议重点有以下四点： 1 当某一个移动节点发送的p a c k e t 在r o u t i n gt a b l e 找不到适合的路径可以 到达它所要传送的目的节点它就广播r o u t er e q u e s t s ( r r e q s ) 去找寻到达目的 节点的新路径。 2 当r r e q s 的消息到达它所指定的目的节点，便会传回r o u t er e p l i e s ( r r e p s ) 蛤原本发送r r r q s 的节点。 3 处理包在转发的途中发生找不到路径的情况时，那就会发出r o u t ee r r o r s ( r e r r s ) 。 4 h e l i om e s s a g e 所扮演的角色及功能。 r o u t er e q u e s t s ( r r e q s ) 的发送与处理： 当某一移动节点想传送包给某一个目的节点，p a c k e t 在i ph e a d e r 建立时，便会去 检查它的路由表，若找不到可到达的目的节点的r o u t ee n t r y ，此移动节点便会去 广播r o u t er e q u e s t s ( r r e q s ) 去寻找新路径。那么当收到r r e q s 的移动节点先去检 查看看此包的目的地址是否为自己，如果不是，则再看看此中间节点是否有一条 “足够新”的路径可以到达目的节点，如果没有，先依据该包已有的地址序列信息 修改路由表，再把它广播出去。 图3 1r 哪过程 每一个r r e q s 都配有一个i d ，当莱一个移动节点收到一个r r e q s 之后，先去给 它检查看看之前是否接收过，假如已经接收过了，就将此包丢弃，如此可以防止 r r e q s 的无限制转发，而且避免各个移动节点中路由表的路径形成环的情况。 r r e 0 的格式； 什么是“足够新鲜”的路径? 一个“足够新鲜”的路径对于目的节点来说，它是一个未到期的r o u t ee n t r y ， 而且它结合了序列编号来判断它到底是不是一个“足够新鲜”的路径，只有当目前 的序列编号至少丈于包含在r r e 母里面的序列编号，才是一个“足够新鲜”的路径。 路由表中的r o u t ee n t r y 的结构： r o u t er e p l i e s ( r r e p s ) 的发送与处理 当中问节点收到r r e q 的消息后，发现r r e q 中所记载的目的地址是自己，则先 依据r r e q 中所记载的地址序列去更改路由表，而且由于每一个移动节点接收了这 个r r 6 口的要求后，它们就舍去c a c h e 住一个踣由去返回到当初发出r r e o 要求的来 源端，然后利用单播的方法送出r o u t er e p l y ( r r e p ) 从目的节点到这个源节点，或 者从能够满足这个要求的任何一个中间节点返回到这个来源端，途中的移动节点根 据r r e p 中所记载的地址序列去更改路由表，最后源节点的路由表就含有到达目的 节点的e n t r y ，接下来就是真正的数据包开始传送了。 圈固岛固圆圆 r o u t e r e p l y - - - - - - - - - - - - 一 圈32r r e p 过程 腿p 的结构： r o u t ee r r o r s ( r e r r s ) 之确认与处理 一个移动节点会在下列的两种情况下，开始去发出一个r r e h 的消息。 i 假如有一个移动节点发现在它自己的路由表里有一个活动路由，而它无 法与此活动路由的下一跳沟通，也就是有一个链路断裂的情沉发生。 2 假如有一个移动节点获得一个数据包，它要去传送到某一个移动节点， 但它并没有一个活动路由，可以让它去做这样的传送。 鸯1 卜国翱 图33 发送r r 阻过程 雹 r e r r 的结构： 我们采用本地修复的方式，去出处理链路断裂的情况发生： 当有一个活动路由突然发生链路断裂，也就是说当某一个移动节点i ( m n i ) 可以 转发数据包给它临近的某一个移动节点2 ( m n 2 ) ，再经由它转发数据包蛤其它的移动 节点3 ( 州3 ) ，就这样一直做转发的动作就可到达目的节点但是3 突然移走了， 这个时候删2 就侦测到州3 ，于是就有链路断裂的情况发生，于是m n 2 就局部的广 播一个小范围的r r e q s ，去寻找删3 ，并且限制了r r e o s 所经过的节点数。即给定 跳数的一个上限值，跳数的值可视为一个可变动的参数，若网络拓扑变动很小，跳 数的值不必很大，反之跳数的值就必缓加大，不过网络拓扑的变化真的很剧烈，这 种方法就不在适用了。若发送了这个r r e q s 后还是找不到一条到达m n 3 的路径，则 可能借由别条路径来到达我们的目的节点。 h e l l om e s s a g e 的使用： 每一个移动节点会定期且局部性的去广播一些消息给它们邻近区域的移动节 点s ，而这样的动作就好像是向你的邻居们打声招呼，所以就称这些消息为h e l l o 硕士学位论文 m a s t e r st h e s i s m e s s a g e 。h e l l om e s s a g e 主要是去维护一个节点的连通性，当某一个节点邻近区域 的移动节点s 收到h e l l om e s s a g e s 时，这代表这些移动节点s 还是可以在下一跳 所能达到的范围。如果没有收到h e l l om e s s a g e s ，那么发出h e l l om e s s a g e s 的节 点可能要使用某些特殊的技巧，去泱定下一跳是否是在这个节点可以通讯的范围 内。而且我们也可以经由h e l l om e s s a g e 去得知在传输范围内是否有新的移动节点 加入，并将其加入到路由表中。 1 7 硕士学位论文 m a s t e r st h e s i s 4 几种基于能量的a dh o c 路由算法 当a dh o e 网络被配置为以电池为能量供给的节点组成时，如何让有限的能量带 来更长的网络生存时间和更好的综合性能表现成为一个非常重要的问题。对于传感 器网络来说，能量拥有更加的重要性，它直接关系到生存时间和工作效率。我们在