（计算机应用技术专业论文）能量受限的ad+hoc网络路由协议的仿真与研究.pdf

武汉理工大学硕士学位论文 摘要 移动a dh o c 网络是由一组带有无线通信收发装置的移动节点组成的一个 临时、多跳的网络。不需要中央控制设施。网络中的节点既是路由器，又是主 机，作为对等实体连接在一起。非相邻的两两节点间的通信必须通过网络中的 其他节点进行转发才能实现，如何在节点间实现通信是移动a dh o e 网络的核心 问题之一。 目前比较经典的路由算法如距离向量路由协议d s d v 和其他三种按需路由 协议a o d v 、d s r 、t o r a 都是最短路由，即最小跳数路由，没有考虑能量因 素。但是a d h o e 网络中的节点是由电池供电，整个网络是一个能量受限系统， 如何节省节点的能量，尽可能延长网络的可操控时间逐渐成为衡量路由协议性 能的重要指标。特别是在紧急营救、军事行动、商务会议等情况下显得尤其重 要。从能量的角度来看，最短路由并不一定是最佳的路由。相反，用一些短跳来代 替相对较长的跳，可能是更好的节能选择。 目前a dh o c 中的节能路由算法主要有两个思路：第一个是使发送每个数据 包耗费的能量最小；第二个就是尽可能的延长网络的存活时间。第一个思路的 路由算法通过发现最小发射功率的路由，使发送每个数据包所耗费的能量最小， 达到节省能量的目的。但是它还是保留了原先路由算法中的一个问题，就是在选 定了一条路由后，会一直用下去，直到数据发完或是拓扑变化触动路由更新，这样， 同最小跳数路由协议一样，容易使某些关键节点因为过度使用而能量耗尽，导致 网络过早分裂。第二个思路的路由算法就是针对这个问题提出的，通过保护剩余 能量小的节点来达到推迟网络分裂、延长网络存活时间的目的。本文的算法正 是根据第二个思路提出的，利用提出的请求延时机制，根据节点能量的不同级 别，采用不同的转发策略，一方面，使得生成的路由尽可能经过剩余能量较大 的节点，降低能耗，延长网络的存活时间，另一方面，避免了r d r p 协议延时 过长的缺陷。 本文首先介绍了移动a dh o c 网络的特点，对现有的移动a dh o e 网络的路 由协议进行了详细阐述，结合移动模型和能量模型，对移动_ a dh o e 网络中的典 型路由协议进行了仿真与性能评价，在此基础上，进一步分析了移动a dh o e 网 络中的连通度问题。结合请求延时机制和能量分级思想，对比较经典的a o d v 和m a o d v 进行了扩展和改进，改进后的协议分别称之为e l b r p 和e c b m r , 武汉理工大学硕士学位论文 并基于n s 2 仿真软件，对改进后的算法与原有算法进行了性能分析与比较。仿 真结果表明，改进的算法是有效、可行的。 本文共分为6 章，各章内容可归纳如下： 第1 章引入了a dh o e 网络的概念，介绍了a dh o c 网络的特点及应用前景， 同时介绍了本课题的来源及研究意义，最后讲述了本文的工作和创新点。 第2 章介绍了a dh o e 网络的常规路由协议。 第3 章分四个方面对a dh o e 网络中的经典路由协议进行了仿真分析，并提 出了一种a dh o e 网络的仿真模型。 第4 章利用请求延时机制和能量分级的思想，研究了a dh o e 网络中能量受 限的路由协议，并对原有的a o d v 协议进行了改进，仿真结果表明改进后的算 法效率较传统算法大大提高。 第5 章将第4 章的思想扩展到多播方面，详细介绍了多播树的生成、合并、 分裂，在n s 2 上实现了该算法，并与m a o d v 进行了性能比较。 第6 章对全文进行了总结，并对未来的工作进行了展望。 本文得到了国家自然科学基金资助项目( 批准号：9 0 3 0 4 0 1 8 。6 0 6 7 2 1 3 7 ) 的 资助和教育部博士点基金资助项目+ ( 批准号：2 0 0 6 0 4 9 7 1 0 5 ) 的资助 关键字：移动自组织网络，能量模型，路由协议，服务质量，网络仿真 武汉理工大学硕士学位论文 a b s t r a c t m 0 _ b i l ea dh o cn e t w o r k sc o m p o s e do fm o b i l en o d e sw i t hw i r e l e s s c o m m u n i c a t i o nd e v i c e sa r et y p i c a l l yc h a r a c t e r i z e db yt h e i rm u l t i h o p ，t e m p o r a r ya n d u n - c e n t e r e a c hn o d ei nt h en e t w o r ka l s oa c t sa sa r o u t e r , f o r w a r d i n gd a t ap a c k e t sf o r o t h e rn o d e s h o wt oc o m m u n i c a t ew i t he a c ho t h e ri so n eo ft h ek e yp r o b l e m si na d h o cn e t w o r k s t h et y p i c a lr o u t i n gp r o t o c o l sp r e s e n t e db yt h em a n e to fi e t fa r ea l ls h o r t e s t r o u t i n g , t h a ti s ，t h el e a s th o p sr o u t i n g , w h i c hd on o tc o n s i d e rt h ee n e r g ya w a r e p r o b l e m h o w e v e r , t h ep o r t a b l ec o m m u n i c a t i o nd e v i c e si na dh o cn e t w o r k sa r e u n t e t h e r e d , b a t t e r i e so p e r a t e da n dh a v el i m i t e de n e r g y , s ot h en e t w o r ki s a n e n e r g y c o n s t r a i n e ds y s t e m h o wt op r e s e r v et h en o d e se n e r g ya n dp r o l o n gt h e l i f e t i m eo ft h es y s t e mg r a d u a l l y p l a y s a ni m p o r t a n tr o l eo ne v a l u a t i n gt h e p e r f o r m a n c eo fa dh o cn e t w o r kr o u t i n gp r o t o c o l s t h ee n e r g yc o n s e r v a t i o no ft h e n e t w o r ks y s t e mi sa k e yp r o b l e me s p e c i a l l yi nt h es i t u a t i o n ss u c ha sm i l i t a r ya r e a s ， d i s a s t e rr e f i e c l a s s r o o m sa n dc o n f e r e n c e s w h e r et h et i m ea n dt h ed e v i c e si s c o n s t r a i n e d f r o mt h ep e r s p e c t i v eo fe n e r g y , t h es h o r t e s tp a t hi sn o ta l w a y st h e o p t i m a lp a t h o nt h ec o n t r a r y , u s i n gt h es h o r t e rh o p st or e p l a c et h er e l a t i v e l yl o n g e r h o p sm a y b eab e t t e rc h o i c et op r e s e r v et h ee n e r g y w h i kav a r i e t yo fa p p r o a c h e st oe n e r g y - a w a r er o u t i n gp r o t o c o l si na dh o c n e t w o r k sh a v eb e e np r o p o s e d , d e p e n d i n go nd e s i r e dg o a l s , t h e yc 姐b ec l a s s i f i e d i n t ot w ot y p e s t h eg o a lo ft h ef i r s tt y p ei sf o c u s i n go nm i n i m i z i n gt h et o t a l c o n s u m e de n e r g yw h e n t r a n s m i t t i n gp a c k e t s ，w h i c h m i n i m i z e st h e e n e r g y c o n s u m p t i o np e rp a c k e to rf l o w h o w e v e r t h e s ea p p r o a c h e sm a ys u f f e rt h es a m e p r o b l e ma st h ea b o v e - m e n t i o n e dr o u t i n gp r o t o c o l sw i t h o u tc o n s i d e r a t i o no fe n e r g y c o n s e r v a t i o n , i ft h es a m ep a t h sa r eb e i n gu t i l i z e dr e p e a t e d l yd u et ot h e i rm i n i m a l e n e r g yc o n s u m p t i o n , t h en o d e se n e r g ya l o n gt h e s er o u t e sa r ec o n s u m e dq u i c k l ya n d m a yc a u s et h et o p o l o g yp a r t i t i o n e de a r l i e ra st h ec l a s s i c a lr o u t i n gp r o t o c o l s t h e g o a lo ft h es e c o n dt y p ei st om a x i m i z et h es y s t e ml i f e t i m ew h i c hi sd e f i n e da s d u r a t i o nf r o mt h eb e g i n n i n go ft h es e r v i c et ot h ef i r s tt i m eo fs o m en o d e se n e r g y d e p l e t i o nb yp r e s e r v i n gt h es m a l l e re n e r g yl e f tn o d e st op r o l o n gt h et i m eo fs y s t e m s p l i t ，w h i c hp u tm o r ef o c u so nl o a db a l a n c i n ga m o n gn o d e st ol e n g t h e ns e r v i c et i m e m t h e rt h a nm i n i m i z a t i o no fe n e r g yf o ri n d i v i d u a lp a c k e tt r a n s m i s s i o n b a s e do nt h e r e q u e s td e l a ym e c h a n i s ma n dt h en o d e se n e r g yl e f t , o n ra l g o r i t h mi sp r e s e n t e dj u s t u l 武汉理工大学硕士学位论文 b yt h es e c o n di d e a o nt h eo n eh a n d ，t h er o u t i n gp a s s e sb yt h eb i g g e re n e r g yl e f t n o d e s ，w h i c hp r o l o n gt h es y s t e ml i f e t i m e o nt h eo t h e rh a n d ，t h em e c h a n i s ma v o i d s t h es h o r t c o m i n go ft h el o n g e rd e l a yt i m eo fr d r e f i r s t l y , t h i st h e s i sd e s c r i b e st h eb a s i cc h a r a c t e r i s t i co fa dh o en e t w o r k sa n d i n t r o d u c e st h ee x i s t i n gr o u t i n gp r o t o c o l si nd e t a i l c o m b i n e at h em o b i l em o d e la n d e n e r g ym o d e l ，w ee v a l u a t et h ec l a s s i c a lr o u t i n gp r o t o c o l si na dh o en e t w o r k sa n d s t u d yt h ep r o b l e mo fc o n n e c t i v i t yb a s e d o l lt h es i m u l a t i o nr e s u l t s u s e dt h er e q u e s t d e l a ya n dt h ei d e a so fe n e r g yl e v e l ，w ei m i p l e m e n ta n di m p r o v et h ec l a s s i cr o u t i n g p r o t o c o l so fa o d va n dm a o d v , n a m e dt h ee l b r pa n de c b m rr e s p e c t i v e l y s e c o n d e l y , w ec o m p a r et h ep e r f o r m a n c eo fe x i s t i n gp r o t o c o l sa o d v , r d r p , m a o d va n dp r o p o s e de l b r p , e c b m rv i as i m u l a t i o nw i t hn s 2 t h es t u d i e ss h o w t h a tt h ei m p r o v e dr o u t i n gp r o t o c o l sa r ei m p l e m e n t e da n da v a i l a b l e 啦t h e s i sh a ss i xc h a p t e r sa sb e l o w ， c h a p t e r1i n t r o d u c e st h ec o n c e p t , t h ec h a r a c t e r i s t i ca n dr e s e a r c hh o t s p o to fa d h o en e t w o r k sa n di n t r o d u c e st h e5 9 ) u r c ea n dr e s e a r c hm e a n i n go ft h i sa r t i c l e ，t h e w o r k i n ga n di n n o v a t i o no f w h i c h a r eg i v e nf i n a l l y c h a p t e r2d e s c r i b e so f t h ec l a s s i cr o u t i n gp r o t o c o l si na dh o en e t w o r k s c h a p t e r3s i m u l a t e st h e f o u rr o u t i n gp r o t o c o l si nd i f f e r e n t a n g e l sa n dp u t f o r w a r das i m u l a t i o nm o d e lf o ra dh o en e t w o r k s c h a p t e r4d e s c r i b e st h ei d e a so fe l b r p ( e n e r g yl e v e lb a s e dr o u t i n gp r o t o c 0 1 ) i nd e t a i lw i t ht h ei d e a so fr e q u e s td e l a ya n de n e r g yl e v e l t h es i m u l a t i o nr e s u l t ss h o w t h ee l b r ph a sab e t t e re f f e c t i v e n e s st h a na o d va n dr d r p c h a p t e r5i n t o r d u c c st h ee c b m r ( e n e r g yc o n s u m p t i o nb a l a n c em u l t i c a s t r o u t i n g ) ，w h i c hi si m p l e m e n t e df r o mt h ei d e a so fe l b r p , a n dd e s c r i b e st h ee r e a t ， t h es p l i ta n dt h ec o m b i n a t i o no fm u l t i c a s tt r e e a ss a m ea sc h a p t e r4 - w e ：g a v ea c o m p a r e so fm a o d v a n de c b m rw i t hs i m u l a t i o n c h a p t e r6s u m m a r i z e st h i sp a p e ra n ds u g g e s t i n gt h ef u t u r ew o r k 1 1 l i st h e s i si ss u p p o r t e db yn a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o n 伊r o j e c t sn o 9 0 3 0 4 0 1 8 ，6 0 6 7 2 1 3 7 ) a n dt h em i n i s t r yo fe d u c a t i o np h d f o u n d a t i o n ( p r o j e c t sn o 2 0 0 6 0 4 9 7 1 0 5 ) o fp r c h i n a k e y w o r d s ：m a n e t , e n e r g ym o d e l ，r o u t i n gp r o t o c o l ，q o s ，n e t w o r ks i m u l a t i o n s i v 武汉理工大学硕士学位论文 1 1 引言 第1 章绪论 随着计算机网络的日益普及，能否快速方便地获取所需要的信息显得越来 越重要。移动通信技术为人们无论在何时何地获取信息提供了一条有效的途径， 并逐步成为了计算机网络领域研究的一个热点问题。移动通信网络按照有无基 础设施的支持可以分为两大类：有固定基础设施支持的网络和没有固定基础设 施支持的网络。 目前需要固定基础设施支持的移动通信骨干网已被世界上广泛应用，例如 g s m ( g l o b a ls y s t e mm o b i l cc o m m u n i c a t i o n ) 、c d m a ( c o d ed i v i s i o nm u l t i p l e a c c e s s ) 等网络。但上述这些网络仅适应于已有骨干网络的区域，对于原本不存 在骨干网的区域或者骨干网遭到重大破坏的区域，例如在大海上、沙漠中，以 及灾区、战场、临时会议、军事行动等特殊场所，上述移动通信网络就不能满 足要求。在某些紧急情况下，需要临时、快速地建立一个新的移动通信网络【1 1 ， 以便实现信息的传送。为了满足这种要求，作为移动通信的另一种特殊形式一 移动a dh o c 网络( m o b h e a dh o cn e t w o r k ，m m 唧”1 ) 也就应运而生了。 1 2 移动a dh o c 网络( m a n e t ) 移动a dh o c 是一种特殊的无线网络，不需要中央控制设施。网络中的节点 既是路由器，又是主机，作为对等实体连接在一起。非相邻的两两节点问的通 信必须通过网络中的其他节点进行转发才能实现，从而组成一个多跳的 ( m u l t i h o p ) 无线移动网络【3 l 。图1 1 描述了一个由三个节点组成的简单移动a d h o c 网络。 图1 1 一个简单的移动a d h o c 网 武汉理工大学硕士学位论文 在该图中，节点主机a 不在节点主机c 的传输范围内，同时节点主机c 也 不在节点主机a 的传输范围内，而a ，c 都在节点主机b 的传输范围之内，故 a 、c 之间要想进行信息传输，必须通过中间节点b 进行数据包的转发，从而 在a 、c 之间组成一个两跳的a d h o e 网络。 1 3 移动a d h o c 网络的特点 移动a d h o e 网络与固定网络以及蜂窝无线网络相比，具有不同的特点： ( 1 ) 动态拓扑结构，这是a dh o c 网络最显著的特点。因为在a dh o e 网中的 节点可以随意地移动，导致网络的拓扑结构也会随之变化。另外移动通信单元 发射和接收特性( 如功率) 的变化也会影响拓扑结构。 ( 2 ) 网络中移动节点通过无线信道连接，每个节点都具有路由功能，构成无 线路由器。整个网络就是由无线路由器组成的一个自治系统。a dh o e 网络具有 全分布特性，不需要基站等核心通信设施的支持，就可快速布设。 ( 3 ) 链路带宽受限，容量可变，具有低速、高误码率、带宽资源有限等特征； a dh o c 网可能工作在一个带宽与延迟等变化、通信链路不可靠的环境中。 ( 4 ) 单向信道的存在1 6 j 。节点的发射功率、电池能量以及地理位置等因素的变 化可能使单向链路存在。如图1 2 所示，若节点a ，b 发射功率不同，a 发射的信 号b 能接收到，但b 发射的信号a 却不能接收到。 图1 2 节点主机a ，b 发射功率不同的情况 ( 5 ) a d h o e 网中的节点要依靠电池来供电，操作过程中电能受限。 ( 6 ) 残存性强。因为移动a dh o e 网没有集中控制管理中心，故当某一节点出 现故障时，并不会使整个网络瘫痪。 f 7 ) 生存时间短。这里有两层意思，其一是指单个链路之间由于节点的移 2 武汉理工大学硕士学位论文 动使得链路的生存时间短，其二是指移动a dh o c 网络一般是为了满足某种临时 需要而建立的，当任务完成后将被撤除。 ( 8 ) 安全有限。由于移动节点之间通过无线信道相连，没有专门的路由器， 由节点自身充当路由器，也没有命名服务、目录服务等功能，这些特点使得传 统有线网络的路由协议和安全措施不再适用于a dh o c 网络川。 1 4 移动a dh o c 网络的应用领域 移动a dh o e 网络的应用领域很多，大体可以分为以下几类： ( 1 ) 传感器网络：最近，人们开始关注大量分布的传感器协同工作问题。传 感器可以工作在危险的环境( 如化学有害物质泄露现场、灾区) ，通过在传感器 上装配位置指示器、a dh o c 收发器等，可以将现场的信息传送到危险场所以外， 从而避免人员进入现场，收集和辨别事故信息。 ( 2 ) 移动会议：在室外临时环境中，工作团体的所有成员可以通过a dh o c 方 式组成一个临时网络来协同完成一项大的任务，或协同完成某个计算任务。在 室内办公环境中，办公人员携带的包含a dh o c 收发器的p d a 可以通过无线方 式自动从台式机上下载电子邮件，更新工作日程表等。 ( 3 ) 家庭网关：通过移动联网的方式把办公室的办公环境延伸到家庭，必要时 在家庭办公。或者利用我们随身携带的个人无线a dh o c 设备与装备了a dh o e 收发器的家庭电器通信，自动完成开锁、开灯、打开娱乐设备、调节空调等操 作。 ( 4 ) 紧急服务：由于停电或其他灾害出现，网络基础设施遭到破坏时，组建一 个a dh o c 网络帮助紧急救援人员完成必要的通信工作。 ( 5 y 个人域网络：通过a dh o c 网络把个人通信、娱乐、办公等设备联网，这 些设备可以或不需要与因特网相连，但在执行用户的某项活动时肯定需要彼此 通信。在这种情况下，移动性不是主要问题。 ( 6 ) 军事无线通信：在现代化战场上，各种军事车辆之间、士兵之间、士兵与 军事车辆之间都需要保持密切的联系，以完成统一指挥，协调作战。这样的通 信网络是一种典型的a dh o c 网络。据报道，在最近的伊拉克战争中，移动a dh o c 网络得到有效的应用。 其他商业应用：如未来装备a dh o c 收发设备的机场预约和登机系统可以 3 武汉理工大学硕士学位论文 自动地与乘客携带的个人无线a dh o c 设备通信，完成目前的换登机牌等手续。 再如商场内商品r f 标签，廉价的r f 标签可以通过无线接口由a dh o c 设备动 态刷新。顾客若携带手持无线设备可以很容易地找到某种商品和价格，这种设 备己由n c r 公司生产。 1 5 本课题的来源及研究意义 1 5 1 所选课题的题目及课题来源 能量受限的a dh o c 网络路由协议的仿真与研究，受国家自然科 学基金资助项目( 批准号：9 0 3 0 4 0 1 8 ，6 0 6 7 2 1 3 7 ) 的资助和教育部博士点基金资 助项目( 批准号：2 0 0 6 0 4 9 7 1 0 5 ) 的资助。 1 5 2 课题研究的目的及意义 m a n e t 是指一组带有无线收发装置的移动节点组成的一个多跳的临时性 的自治系统。在这种环境中，由于节点的无线通信覆盖范围有限，两个无法直 接通信的移动节点可以借助其他节点进行分组转发实现数据通信。与其他移动 通信网络相比，它不需要固定基站支持，具有网络a dh o c f i 、动态变化的网络拓 扑结构、存在单向的无线信道等特点。因此，m a n e t 网络可以通过临时组网的 方式在恶劣环境中支持移动节点之间的数据、语音、图像和图形等业务的无线 传输，应用范围可以覆盖工业、商业、医疗，家庭、办公环境、军事等各种场合， 所有行业几乎无所不在其中，尤其在未来战场上，m a n e t 网络对于高技术武器 装备、集中指挥、协同作战和提高作战机动性等具有非常重要的意义。 与单跳的无线网络不同，a dh o c 网节点之间是通过多跳数据转发机制进行 数据交换，需要路由协议进行分组转发决策。无线信道变化的不规则性、节点 的移动、加入、退出等也会引起网络拓扑结构的动态变化。路由协议的作用就 是在这种环境中，监控网络拓扑结构的变化，交换路由信息，定位目的节点位 置，产生、维护和选择路由，并根据选择的路由转发数据，提供网络的连通性。 它是移动节点互相通信的基础，因此成为当前a dh o c 网体系结构中的研究热 点。 由于m a n e t 路由协议主要应用在以小电池组为能量来源的移动设备上， 4 武汉理工大学硕士学位论文 能量消耗也是m a n e t 路由协议性能分析的一个非常重要的方面。如何有效地 减少电池能量消耗，延长整个网络的生存时间成为路由协议性能评价中的一个 新的研究热点。此外，由于多媒体业务的应用越来越频繁，如何在m a n e t 中 提供对多媒体业务的0 0 s 支持显得日益迫切。 1 6 研究工作和本文的贡献 由于m a n e t 路由协议主要应用在以小电池组为能量来源的移动设备上，能 量消耗也是m a n e t 路由协议性能分析的一个非常重要的方面。如何有效地减少 电池能量消耗，延长整个网络的生存时间成为路由协议性能评价中的一个新的 研究热点。本课题在对m a n e t 网络的路由协议和节能策略深入研究和学习的基 础上，提出一种具有节点能量负载平衡的路由协议，从而解决在电池容量提高 不济的情况下，降低节点的能量消耗，延长节点和网络寿命的问题。 本文的创新性工作可体现在一下几个方面： ( 1 ) 引入连通度作为评价路由协议性能的一个指标，并基于能量模型，提 出a dh o e 网络保持连通的临界传输范围的数学模型。 ( 2 ) 基于节点能量级别和请求延时机制，对a o d v 路由协议进行了改进， 从而解决在电池容量提高不济的情况下，降低节点的能量消耗，延长节点和网 络寿命的问题。并在n s 2 平台上进行仿真实验。对m a n e t 网络的实际应用有一 定的推动作用。 ( 3 ) 提出一种具有节点能量负载平衡的多播路由协议，重点解决多播树的 最小能耗问题。 5 武汉理工大学硕士学位论文 第2 章移动a d h o c 网络中的常规路由协议 目前移动a dh o c 网络工作组【8 j 已经提出了一些协议草案及标准，比如d s r 、 a o d v 、o l s r 等。此外，研究人员还发表了许多关于a dh o c 网路由协议的学 术论文，比如d s d v 、w r p 、s t a r a 等。这些a dh o c 网路由协议根据不同的 角度可以进行不同的分类和比较【9 1 。根据路由发现策略的角度，可分为先验式 路由和反应式路由两种类型【1 肌1 1 1 。 2 1 先验式路由 先验式路由的路由发现策略与传统路由协议类似，节点通过周期性地广播 路由信息报文，交换路由信息，主动发现路由。同时，节点必须尽可能地维护 通往全网所有节点的路由信息。它的优点是当节点需要发送数据报文时，只要 去往目的节点的路由存在，所需的延时很小。缺点是先验式路由需要花费较大 开销，尽可能使得路由更新能够紧随当前拓扑结构的变化。然而，动态变化的 拓扑结构可能使得这些路由更新成为陈旧的路由信息，从而使得路由协议始终 处于不收敛状态1 1 2 1 。 在a dh o c 网路由协议的研究初期，主要思路是修改有线网络的路由协议以 适应在a d h o c 网络环境中运行。这些路由协议大多属于先验式路由。在下面的 各种先验式路由协议的过程描述中，将着重说明如何对传统路由协议的改进以 适应a dh o c 网络环境中运行。 2 1 1d s d v d s d v ”i ( 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 中，每个移动节点都需要维护一张路由表。路由表表项包括 目的节点、跳数和目的地序列号，其中目的地序列号由目的节点分配，主要用 于判别路由是否过时，并可防止路由环路的产生。每个节点周期性地与邻居节 点交换路由信息，并且根据路由表的改变来触发路由更新。路由表更新有两种 方式：一种是全部更新( f u l l d u m p ) ，即拓扑更新消息中将包括整个路由表，主 6 武汉理工大学硕士学位论文 要应用于网络变化较快的情况；另一种方式是部分更新( i n c r e m e n t a lu p d a t e ) ， 更新消息中仅包含变化的路由部分，通常适用于网络变化较慢的情况。在d s d v 中只使用序列号最高的路由，如果两个路由具有相同的序列号，那么将选择最 优的路由( 如跳数最短) 。它的缺点是不适应变化速度快的a dh o c 网络，不支 持单向信道。 2 1 2f s r f s r 唧s h e y es t a t er o u t i n g ) 1 4 】是先验式链路状态路由协议，其目的是通过鱼 眼效应( 近处的物体清晰，远处的物体模糊) 减少信息流量。它对传统的链路状 态算法进行了修改： ( 1 ) 将链路状态的更新信息局限于邻居节点之问。 ( 2 ) 链路状态信息的交换由时间触发，而不是由事件触发。 ( 3 ) 对于路由表中的不同记录采用不同的时间问隔交换链路状态信息。? 对 于较近的节点用较短的时间间隔交换链路状态信息，对于较远的节点用较长的 时间间隔交换链路状态信息。通过这些措施减少了控制报文的传播范围，提高 了路由协议的性能。但时，随着节点移动性的增加，到达较远节点的路由信息 精确度有所下降。 2 1 3 哏p w r p 【1 5 l ( w i r e l e s sr o u t i n gp r o t o c 0 1 ) 协议是在路径发现算法p f a ( p a t hf i n d i n g a l g o r i t h m ) 基础上改进的。p f a 与d v a 不同，它利用通往目的节点的路径长度 和相应路径的倒数第二跳节点信息加速路由协议收敛速度，改善d v a 中路由环 路问题。w r p 对p f a 的改进之处在于当节点i 监测到与邻居节点j 的链路发生 变化时，i 会检查所有邻居节点关于倒数第二跳节点信息的一致性，而p f a 只 会检查节点j 关于倒数第二跳节点信息的一致性。这种方式可以进一步地减少 出现路由环路的次数，加快算法的收敛速度。 2 1 4s 1 = f 气r a s t a r a 1 6 1 ( s y s t e ma n dt r a f f i cd e p e n d e n ta d a p t i v er o u t i n ga l g o 枷加) 协议采 用最短路径算法计算路径，但“最短”路由度量采用了平均延时时间，而不是 7 武汉理工大学硕士学位论文 常用的跳数，也就是说s t a r a 在进行分组路由时，考虑了无线链路的容量和 排队延时等因素。每个节点i 采用改进的端到端确认协议为每一对源和目的节 点( i ，d ) 计算平均延时d 。m o ) ，方法如式( 2 1 ) 所示。其中， 【o ，1 】，为遗忘 因子，用于调整历史延迟值和当前延迟值的权重关系：七，n 表示节点i 一 跳可以到达的所有邻居节点的集合。然后根据式( 2 2 ) 所示，将经过的交通流量 分配给不同的邻居节点，目标是使得所有可用的路径具有相同的延时。需要特 别指出的是，这种路径平均延时估测机制并不需要双向信道和节点间的时钟同 步的支持。 d 4 t ( 0 - 击荟碟o - 1 ) ( 2 1 ) p 。d ( f ) ，p ：o 一1 ) + 口( f ) ( d f ( f ) 一d 2 0 ) )( 2 2 ) 2 1 5o l s r 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 g ) 1 1 是一种优化的链路状态路由协议，其 研究者一直积极参与i e t f 会议，已经有l i m l x 上的协议实现，其源代码可以从 相应的网站( h t t p ：h i p e r c o m i n d a f t o l s o 得到。与其它表驱动的先验式路由协议一 样，节点间需要有规律地交换网络拓扑信息。被邻节点选为多点中继站 ( m u l t i - p o i n t - r e l a y , m p r ) 的节点需要周期性地向网络广播控制信息，控制信息中包 含了把它选为m p r 的那些节点的信息，以告诉网络中其它节点与这些节点直接 相连。只有m p r 节点被用做路由节点，非m p r 节点不参与路由计算。0 l s r 还利用m p r 节点有效地广播控制信息，非m p r 节点不需转播控制信息。不过， 这样做的后果可能导致通信负荷过分集中于m p r 节点上。 2 2 反应式路由 与先验式路由策略相反，反应式路由认为在动态变化的a dh o c 网络环境 中，没有必要维护通往其他所有节点的路由。它仅在路由表中没有通往目的节 点路由的时候才“被动地”进行路由发现。因此，拓扑结构和路由表内容是反 应式建立的，它可能仅仅是整个拓扑结构信息的一部分。它的优点是不需要周 期性的路由信息广播，节省了一定的网络资源。缺点是发送数据分组时，如果 8 武汉理工大学硕士学位论文 没有去往目的节点的路由，数据分组需要等待因路由发现所引起的延时。 反应式路由协议通常由路由发现和路由维护两个阶段组成。当源节点发现 没有通往目的节点的路由时，触发路由发现过程。它一般由路由请求报文和路 由回复报文组成。当网络拓扑结构发生变化时，通过路由维护过程删除失效路 由，并重新发起路由请求过程。路由维护通常依靠底层提供的链路失效检测机 制进行触发。 2 2 1a o d v a o d v 墙】( a dh o co nd e m a n dd i s t a n c ev e c t o r ) 是一种按需路由协议，基于传 统的距离向量路由机制，思路简单，易于编程实现，结合了d s d v 和d s r 的 优点。通过使用目的序列号有效地防止了路由循环的发生，解决了传统的基于 距离向量路由协议存在的无限计数问题。支持中间主机回答，能使源主机快速 获得路由，a o d v 同时还支持多址通信。协议由两部分组成：路由请求和路由 维护。此外，a o d v 的另一个显著特点是它加入了组播路由协议扩展，并支持 ( 1 0 s 。它的缺点是不支持单向信道，原因是a o d v 协议基于双向信道的假设工 作，路由回答报文直接沿着路由请求的反方向回到源节点。 2 2 1 1 路由请求阶段 当某个源节点s 希望建立通向某个目的节点d 的路径时，源节点发起一个 路由发现过程，它广播路由请求分组( r r e q ) 给它的邻居节点( 相互处于对方的 无线电发射范围之内的相邻为单跳的节点) ，r r e q 再被这些邻近节点转发，直 到p , r e q 到达目的节点或一个拥有到达目的节点的足够新鲜路径的中间节点。 在转发p , r e q 的时候，中间节点修改它们的路由表，将目的字段修改为r r e q 的初始发起者，将到达r r e q 的初始发起者的下一跳修改为第一个转发给它们 r r e q 拷贝的邻居节点的地址，通过这样的方式来建立一条由d 到s 的反向路 径。一旦r r e q 到达了目的地或拥有一条通向目的节点足够新的路径的中间节 点，则目的节点中间节点通过建立的反向路径单播一个路由响应分组( r r e p ) 给转发给它r r e q 拷贝的邻居节点。在p , p , e p 通过反向路径发送给源节点的过 程中，这条路径上的节点修改它们各自的路由表，将路由表的目的字段修改为 i l r e p 的初始发起者，将到达p , r e p 的初始发起者的下一跳修改为转发给它们 i l r f _ p 拷贝的邻居节点的地址，通过这样的方式在它们的路由表中建立起通向 9 武汉理工大学硕士学位论文 目的节点的正向路径。这样就形成了s 到d 的一条正向路径和一条d 到s 的反 向路径。 2 2 1 2 路由维护阶段 a o d v 通过周期性的广播h e l l o 报文来监视链路状态，若节点在使用某个 链路时发现该链路断开，节点将在d e l e t e _ p e r i o d 之后从路由表中删除包含 该断开链路的路由，并发送“路由出错”报文( r r e r ) 通知那些因链路断开而不 可达的节点将对应路由从路由表中删除，沿途转发r r e r 的节点也删除自己路 由表中的对应路由。如果断链处的上游节点与目的节点之间的距离小于 m a xr e p a i rt r l 跳，则该节点启用生存时间比较小的r r e q 广播来修复路 由，即采用局部修复机制来降低延迟，否则由源端节点发起r r e q 来进行修复。 2 2 2d s r d s r 1 9 ( d y n a m i cs o u r c er o u t i n g ) 协议是最早采用反应式路由思想的路由协 议。它包括路由发现和维护两个过程，协议操作与上节描述的过程基本一样。 它的主要特点是使用了源路由机制进行分组转发。这种机制最初是i e e e 8 0 2 5 协议用于在网桥互连的多个令牌环网中节点寻找路由。d s r 协议借鉴了这种机 制，并加入了反应式思想而形成。 d s r 的优点是中间节点不用维护通往全网所有