（电磁场与微波技术专业论文）高速环境下移动ad+hoc网络的路由协议改进与性能优化.pdf

摘要 移动a dh o c 网络是一种特殊结构的无线通信网络，它可以在任何时间、任何地点不 需要固定基础设施的支持，提供一种通信支撑平台。由于网络中的节点能够任意移动，链 路随时都有断裂的可能，从而导致路由具有不可靠、不稳定的特性，这使得传统的被动路 由协议难以适应节点快速运动而引起的拓扑动态变化。 本文针对被动路由协议中路由发现机制在高速环境下的不足，设计了一种基于信号功 率的可靠路由发现( s p r r d ：s i g n a l p o w e r - b a s e dr e l i a b l er o u t ed i s c o v e r y ) 算法，该算法 利用无线信号传播模型和信号功率获得节点移动状态信息。s p r r d 算法主要包含三个部 分：可靠距离机制、请求次序时延机制以及“本节点与邻居节点的距离表”更新机制。在 可靠距离机制中，如果相邻节点间的距离增加，并且当前距离大于随相对速度动态变化的 可靠距离，则当前链路状态不稳定，不能用于构建路由。该机制使得在路由发现过程中建 立的路由更加可靠，但同时会引起路由跳数的增加。随后引入的请求次序时延机制能够减 小路由长度，用于弥补可靠距离机制的缺陷。另外为了辅助上述两个机制，需要更新距离 表以记录节点间距离信息。 本文将s p r r d 算法与普通a o d v ( a dh o co n d e m a n dd i s t a n c ev e c t o r ) 协议相结合， 形成改进a o d v 协议，并且在仿真软件n s 2 ( n e t w o r ks i m u l a t o rv e r s i o n2 ) 中实现并测试 该改进的协议。仿真结果表明，s p r r d 算法能够明显提升原有协议在高速坏境下的性能， 特别是在平均端到端时延、归一化路由丌销、r e r r 分组数以及路由发现频率方面。 关键词：移动a dh o c 网络被动路由协议信号功率可靠路由a o d v a b s t r a c t m o b i l ea dh o en e t w o r ki so n eo ft h ew i r e l e s sc o m m u n i c a t i o nn e t w o r k sw i t hs p e c i a l s t r u c t u r e s ，w h i c hc a na f f o r dac o m m u n i c a t i o np l a t f o r mw i t h o u ta n yu n d e r l y i n gi n f r a s t r u c t u r e a n y t i m ea n da n y w h e r e l i n kb r e a km a k e st h er o u t eu n r e l i a b l ea n di n s t a b l ed u et ot h er a n d o m m o v e m e n to fi n t e r m e d i a t en o d e si nt h en e t w o r k a sar e s u l t ，t h ec o n v e n t i o n a lr e a c t i v er o u t i n g p r o t o c o l sa r et o od i f f i c u l tt op r o p e r l yr e a c tw h e nt h et o p o l o g yc h a n g e sd y n a m i c a l l yc a u s e db y n o d e s h i g hm o b i l i t y a c c o r d i n gt ot h ed r a w b a c k so fr o u t ed i s c o v e r ym e c h a n i s mi nt h er e a c t i v er o u t i n gp r o t o c o l s u n d e rh i g hm o b i l i t yc o n d i t i o n ，as i g n a l p o w e r - b a s e dr e l i a b l er o u t ed i s c o v e r y ( s p r r d ) a l g o r i t h m i s d e s i g n e d i n t h i st h e s i s t h i sa l g o r i t h m ，w h i c hu t i l i z e st h ew i r e l e s s s i g n a l p r o p a g a t i o nm o d e la n ds i g n a lp o w e rt oo b t a i nn o d e s m o b i l i t yi n f o r m a t i o n ，i sm a i n l yc o m p o s e d o ft h r e es e g m e n t s ：t h es c h e m eo fr e l i a b l ed i s t a n c e ，r e q u e s to r d e r i n gd e l a ya n du p d a t i n gat a b l eo f d i s t a n c ef o rt h en e i g h b o r s i ft h et w oa d j a c e n tn o d e sa r em o v i n ga p a r ta n dt h ec u r r e n td i s t a n c e b e t w e e nt h e mi sl a r g e rt h a nt h er e l i a b l ed i s t a n c ew h i c hv a r i e sd y n a m i c a l l yw i t hr e l a t i v es p e e d ， t h el i n kb e t w e e nt h e mi sc o n s i d e r e dt ob ei n s t a b l ef o rc o n s t r u c t i n gr o u t ei nt h er e l i a b l ed i s t a n c e s c h e m e c o n s e q u e n t l y , t h eb u i l tr o u t e sa r em o r er e l i a b l ed u r i n gr o u t ed i s c o v e r yp r o c e s sa tt h e s a c r if i c eo fr o u t eh o p - c o u n t s i no r d e rt or e d u c er o u t el e n g t h ，t h er e q u e s to r d e r i n gd e l a ys c h e m e i ss u b s e q u e n t l yi n t r o d u c e dt oa l l e v i a t et h es h o r t c o m i n go fr e l i a b l ed i s t a n c es c h e m e m o r e o v e r ， f o rt h es a k eo fa s s i s t i n gt h et w om e n t i o n e dm e c h a n i s m s ，at a b l eo fd i s t a n c es h o u l db eu p d a t e dt o m a i n t a i nt h ed i s t a n c eb e t w e e nn e i g h b o r i n gn o d e s t h ei m p r o v e da o d v ( a dh o co n - d e m a n dd i s t a n c ev e c t o r ) p r o t o c 0 1 w h i c hi st h e c o m b i n a t i o no fs p r r da l g o r i t h ma n dc o n v e n t i o n a la o d v p r o t o c o l ，i si m p l e m e n t e da n dt e s t e d o nt h en e t w o r ks i m u l a t o rn s 2 ( n e t w o r ks i m u l a t o rv e r s i o n2 ) i nt h i st h e s i s t h es i m u l a t i o n r e s u l t ss h o wt h a ts p - r r da l g o r i t h mc a ns i g n i f i c a n t l ye n h a n c et h ep e r f o r m a n c e so fo r i g i n a l r o u t i n gp r o t o c o li nt h eh i g hm o b i l i t ye n v i r o n m e n t ，e s p e c i a l l yi nt e r m so fa v e r a g ee n d - t o - e n d d e l a y , n o r m a l i z e dr o u t i n go v e r h e a d ，n u m b e ro fr e r ra n dr o u t ed i s c o v e r yf r e q u e n c y k e y w o r d s ：m o b i l ea dh o cn e t w o r k ，r e a c t i v er o u t i n gp r o t o c o l ，s i g n a lp o w e r ，r e l i a b l er o u t e ， a o d v 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得南 京邮电大学或其它教育机构的学位或证书而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示 了谢意。 研究生签名：同期： 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本 人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其它复 制手段保存论文。本文电子文档的内容和纸质论文的内容相一致。除在 保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权南京邮电大学研 究生部办理。 研究生签名：导师签名：同期： 南京l l l i ；l u 人学领1 1 i j f 究生学位论史 第一审绪论 1 1 移动a dh o e 网络概述 第一章绪论 1 1 1 移动a dh o c 网络的定义及其历史发展 移动a dh o e 网络，其英文是m o b i l ea dh o en e t w o r k ，也称为m a n e t t l 】或移动自组织 网络。a dh o e 来源于拉丁语，其字面上的意思是“特别的，专门的”。移动a dh o c 网络 是由一组具有无线收发功能的移动节点所组成的、无需任何网络基础设施的多跳自治系 统。网络中的每个节点兼具路由器和主机的功能。移动a dh o e 网络可以独立运行( 如图 1 1 所示) ，也可以与i n t e m e t 或者蜂窝无线网络连接。在后一种情况下，移动a dh o c 网络 通常作为终端子网的形式接入现有网络【2 】。 闩p 凰直名耋 图1 1移动a dh o e 网络示意图 移动a dh o c 网络起源于2 0 世纪7 0 年代美国国防部高级研究规划署( d a r p a ：d e f e n s e a d v a n c e dr e s e a r c hp r o j e c ta g e n c y ) 启动的报文无线网( p r n e t ：p a c k e tr a d i on e t w o r k ) 项引引，它主要是种服务于军方的无线分组网络，实现基于这种网络的无线数据通信。 在此之后，d a r p a 于1 9 8 3 年启动了高生存性自适应网络( s u r a n ：s u r v i v a b l ea d a p t i v e n e t w o r k ) 项目，研究如何将p r n e t 的成果加以扩展，以支持更大规模的网络。1 9 9 4 年 d a r p a 又资助了全球移动信息系统( g l o m o ：g l o b a lm o b i l ei n f o r m a t i o ns y s t e m s ) 项目的 研究，以便能够建立满足军事应用需要、可快速展丌、高抗毁性的移动信息系统。成立于 1 南京蛐川! 人学彤il j 研究5 - 学位沦文第一孽绪论 1 9 9 1 年5 月的i e e e 8 0 2 1 l 标准委员会采用了“a dh o c 网络”一词来描述这种特殊的、自 组织、对等式多跳移动通信网络，移动a dh o c 网络就此诞生。1 9 9 7 年互联网j t = 程任务组 ( i e t f ：t h ei n t e r n e te n g i n e e r i n gt a s kf o r c e ) f 式成立了移动无线自组织网络工作组，专 门负责对这种网络使用的路由协议进行研究和丌发，并制定了一系列的协议与草案。 1 1 2 移动a dh o c 网络的主要特点 与其它传统的无线通信网络和固定网络相比，移动a dh o c 网络具有以下特点【2 】- 【4 】： ( 1 ) 无中心：与其它蜂窝网、无线局域网等不同，移动a dh o c 网络中没有严格的控 制中心，所有节点的地位平等，组成一个对等式的网络。节点可以随时加入和离丌网络， 任何节点的故障都不会影响整个网络的运行，与有中心的网络相比具有很强的健壮性和抗 毁性。 ( 2 ) 网络自组织：移动a dh o c 网络可以在任何时刻、任何地点不需要现有基础网络 设施的支持，通过节点之间的自我组织，快速和灵活地建立一个自由移动的通信网络。 ( 3 ) 动态拓扑结构：由于移动用户终端可以在网络中以任意的速度和方向移动，加 上无线发信装置发送功率的变化、无线信道间的相互干扰以及地形和天气等综合因素的影 响，移动终端间通过无线信道形成的网络拓扑结构随时可能发生变化，而且变化的方式和 速度都是不可预测的。因此需要开发专门的路由协议，以适应这种动态拓扑网络的环境。 ( 4 ) 多跳路由：在移动a dh o c 网络中，由于节点发射功率的限制，节点的无线覆盖 范围是有限的。当节点要与其无线覆盖范围外的节点进行通信时，必须经过多个中间节点 转发才能完成，即要经过多跳，这类似于i n t e m e t 而有别于蜂窝网、无线局域网等单跳网 络。但是与i n t e m e t 网络不同，移动a dh o c 网络中节点兼有主机和路由器两种作用，其多 跳是通过普通的网络节点完成的，而不需要使用专用的路由设备。 ( 5 ) 有限的无线信道带宽：移动a dh o c 网络采用无线传输技术作为底层通信手段， 由于无线信道本身的物理特性，它所提供的网络带宽相对有线信道要低得多。如果再考虑 到竞争共享无线信道产生的冲突、信号衰减、噪音和信道| 日j 的干扰等因素，移动终端所获 得的实际带宽远远小于理论上的最大带宽。 ( 6 ) 单向信道的存在：移动a dh o c 网络中所有终端采用无线信道通信，由于地形和 发射功率等因素的影响，可能产生单向的无线传输信道，即一个节点可以成功地向另一个 节点发送分组，而反向则无法通信。 ( 7 ) 移动终端的局限性：移动用户终端相对于台式机而言，在带来移动性、灵巧、 2 南京| l | j i u 人学坝l j 研究生学位论文第一章绪论 轻便等好处的同时，由于其固有的特性，如内存小、c p u 处理能力低、依靠电池供电能源 有限等，给移动a dh o c 网络下路由协议和应用程序的设计丌发带来一定的难度。 ( 8 ) 有限的网络安全：移动a dh o c 网络工作在无线共享广播信道，与有线网络相比， 存在更加严重的安全性问题，容易被窃听、入侵、网络攻击和拒绝服务等。 1 1 3 移动a dh o c 网络的应用场景 移动a dh o c 网络可以快速部署，不需要固定基础设施的支持，能够在不能或不便利 用现有网络基础设施的情况下提供一种通信支撑平台，从而拓宽了移动通信网络的应用场 合。一般来说它的应用场景主要有以下几类【2 】【3 】： ( 1 ) 军事应用：军事应用是移动a dh o c 网络技术的主要应用领域。在现代化战场上， 装备了移动通信装置的军事人员、军事车辆以及各种军事装备之间都需要保持密切的联 系，以完成集中指挥、协调作战。这样的通信网络是一种典型的移动a dh o e 网络。 ( 2 ) 无线传感器网络：无线传感器网络( w i r e l e s ss e n s o rn e t w o r k ) 是一种特殊的移 动a dh o e 网络。它由大量的无线传感器节点组成，节点的发射功率小，地理位置较为分 散，因此移动a dh o c 网络特有的无线多跳通信是非常合适的解决方案。分散在各处的传 感器节点在自动组网之后，可以实现传感器之间，以及与控制中心之间的通信。 ( 3 ) 个人通信：个域网( p a n ：p e r s o n a la r e an e t w o r k ) 是移动a dh o e 网络的又一个 重要应用领域，它可以运用于实现手机、笔记本等多种个人通信设备之间的通信。同时考 虑到电磁波辐射问题，个域网络通信设备的无线发射功率应尽量小，这种情况下移动a d h o c 网络的多跳通信特点将再次展现它的独特优势。 ( 4 ) 紧急服务和抢险救灾：在自然灾害或其它原因导致网络基础设施出现故障或无 法f 常工作时，当处于偏远或野外地区无法依赖固定或预设的网络进行通信时，移动a d h o c 网络技术的独立组网能力和自组织特点，可以快速地建立临时通信网络，是这些场合 通信的最佳选择。 ( 5 ) 与其它移动通信系统的结合：移动a dh o c 网络还可以与蜂窝移动通信系统相结 合，利用移动台的多跳转发能力扩大蜂窝移动通信系统的覆盖范围、均衡相邻小区的业务 和提高小区边缘的数据速率等。 1 2 移动a dh o e 网络中的关键技术 移动a dh o c 网络的特殊性使得传统有线网络和蜂窝数字移动通信网中使用的各种协 3 塑垒! ! ! ! ! ! 坚叁兰竺! 型! ! ! 竺兰丝笙苎笙二垦笪堡 议和技术无法直接使用，需要为移动a dh o c 网络设计专门的协 义和技术。目前移动a dh o c 网络技术研究的重点主要集中在以下几个方面： ( 1 ) 多址接入技术 多址接入技术是一种用来解决多个用户共享一个通信信道的技术【5 】，多址接入技术是 否设计得当直接影响到无线资源的利用率和通信质量。目前移动a dh o c 网络的多址接入 协议通常都足基于载波侦听多址接入冲突避免( c s m a c a ：c a r r i e r - s e n s em u l t i p l e a c c e s s c o l l i s i o na v o i d a n c e ) 机制【6 1 。但是在移动a dh o c 网络中，由于节点的无线覆盖范 围有限，只有在发送节点传输距离内的节点爿能检测到信道中的载波，这样将导致隐藏终 端( h i d d e nt e r m i n a l ) 和暴露终端( e x p o s e dt e r m i n a l ) 问题。为了克服这两个问题，许多 学者在c s m a c a 协议的基础上提出了新的协议，这些协议大致可以分为两类：一类是在 数据分组发送之前，采用r t s c t s ( r e q u e s t - t o s e n d c l e a r - t o s e n d ) 短分组握手机制进行 信道预约。另一类是将r t s c t s 短分组握手机制与忙音多址接入技术相结合起来，典型的 代表是z j h a a s 等人提出的双忙音多址接入( d b t m a ：d u a lb u s yt o n em u l t i p l e a c c e s s ) 协议i 川。 ( 2 ) 路由技术 针对移动a dh o c 网络的路由协议设计也是学术界广泛关注的热点问题之一。在缺少 固定基础设施支持、节点随机运动、无线链路不可靠以及供电设备能量有限等情况下，路 由协议的设计必须综合考虑多方面因素。首先，必须没计高效的分布式路由算法来支持网 络拓扑的迅速变化。其次，为了建立和维护路由，节点间需要交换大量的路由控制分组， 尤其在各种干扰存在时，己建立的路由会很容易失效，导致频繁的对路由进行维护。因此 在无线带宽受限的情况下，如何减少路由控制分组，提高数据分组的成功传输率，是设计 路由协议的重点问题。再者，由于移动用户终端c p u 、内存和能源等方面的限制，路由协 议必须能高效利用能源，同时节省存储空间。目前研究人员已经为移动a dh o c 网络提出 了许多路由协议，但都尚有一定的不足之处，有待进一步研究。 本论文重点针对已经提出的路由协议在节点快速移动环境下的不足之处，进行详细分 析和讨沦，并且设计了一种基于信号功率的可靠路由发现算法。在路由发现过程中，浚算 法能够使得建立的路由更加可靠、生存时间更长，从而更加适应节点快速运动的场景，实 现优化路由协议在高速移动环境下性能的目标，这将在后续章节中给予详细介绍。 ( 3 ) 功率控制 功率控制一直是无线网络中比较难以解决的问题，在移动a dh o c 网络更是如此。在 移动a dh o c 网络中，功率控制主要考虑两方面的问题【4 】：第一，降低能耗，尽量延长节点 4 南京i l l l 1 e 人学帧m j f 了生学位沦文第一嚣绪论 和网络的寿命；第二，在保证网络连通性的条件卜，按照一定的方案调整移动节点的功率， 增大无线资源的空间复用度，减小对邻近节点的干扰，达到提高网络吞吐量的目的。 ( 4 ) 服务质量( q o s ：q u a l i t yo fs e r v i c e ) 保证 q o s 足指网络为用户提供一组可以测量的预先定义的服务性能参数，如端到端延迟、 可用带宽和分组丢失率等。近年来随着多媒体应用的普及和移动a dh o c 网络在商业应用 的发展，人们更多地需要在移动a dh o c 网络上传送综合业务，并且希望为不同业务的服 务质量提供保证。在移动a dh o c 网络中服务质量保证是一个系统性问题，不同的层都要 提供相应的机制【2 j ，例如应用层要提供自适应信源编码和压缩技术，网络层要提供q o s 路 由等。而且考虑到网络自身的特点，如网络拓扑变化频繁、节点资源受限等，在移动a dh o c 网络中提供q o s 保证将面临许多不同于传统网络的新问题和挑战。 ( 5 ) 安全问题 安全性也是决定移动a dh o c 网络的潜能能否得到充分施展的一个关键所在，特别是 在军事上和商业上的应用。在移动a dh o c 网络中，无线信道使得窃听随处可在，节点的 移动性使得网络内部和外部的边界变得模糊，防火墙无法应用。移动a dh o c 网络比固定 网络更容易遭受各种安全威胁，如窃听、入侵、网络攻击等。因此需要研究适用于移动a d h o c 网络的安全体系结构和安全技术。 1 3 主要研究内容和创新点 本论文来源于国家9 7 3 课题认知协同与网络容量优化理论，主要工作是对移动a d h o c 网络中被动路由协议的路由发现机制进行深入分析，重点研究了节点高速随机移动的 特性对被动路由协议造成的影响。然后在此基础上设计了一种基于信号功率的可靠路由发 现( s p r r d ：s i g n a l p o w e r - b a s e dr e l i a b l er o u t ed i s c o v e r y ) 算法。该算法通过在路由发现 过程中寻找更加稳定的链路用于建立从源节点到目的节点的路由，从而提高路由的可靠 性，使得路由协议更加适应节点高速运动的环境。接着将s p r r d 算法应用于普通a o d v 协议中，形成改进a o d v 协议，并且在网络仿真软件n s 2 中实现了该改进的仂、议。最后 建立不同的仿真模拟环境，通过比较普通a o d v 协议和改进a o d v 协议之间性能参数的 差异，验证了s p r r d 算法具有显著优化路由协议在高速移动环境下性能的特点。 本沦文的主要创新点如下： ( 1 ) 设计了一种基于信号功率的可靠路由发现s p r r d 算法。该算法通过引入可靠 距离机制，判断节点间链路的实时状态。可靠距离机制充分考虑了相邻节点的不同运动情 南京l i i l ；i u 人学颁l ! 研究生学位论文第一章绪论 况对它们之| 、日j 链路状态的影响，并且利用随节点间相对速度动态变化的可靠距离以及：常点 间距离变化的信息，选择稳定的链路用于建立路由，提高了路由在高速环境下的可靠性。 此外，s p r r d 算法又加入请求次序时延机制，降低了可靠距离机制所引起的路由跳数增 加的影响。凶此s p r r d 算法能够使得传统的被动路由协议更加适用于高速环境下的移动 a dh o c 网络。同时由于本算法利用无线信号传播模型和无线网卡提供的信号功率就可以工 作，不需要g p s ( g l o b a lp o s i t i o n i n gs y s t e m ) 等额外设备的支持，具有简单性的特点。 ( 2 ) s p r r d 算法主要针对路由发现过程进行修改，而且不需要扩充任何路由控制分 组，故具有可以很方便地应用于移动a dh o c 网络已有的被动路由协议的特点。根据该特 点，利用s p r r d 算法对普通a o d v 协议进行改进，并且在网络仿真软件n s 2 中实现了 改进a o d v 协议。 根据上述内容，本论文的章节安排如下： 第一章为绪论，主要介绍了移动a dh o c 网络的定义、历史发展、关键技术以及应用 场景等背景知识。 第二章阐述了移动a dh o c 网络下常用路由协议的原理和优缺点等，并且对各类协议 的不同性能进行了比较。其中重点对被动路由协议中的d s r ( d y n a m i cs o u r c er o u t i n g ) 和 a o d v 的工作机制，以及它们的改进方案进行详细分析。 第三章分析了被动路由协议的路由发现机制在高速环境下的缺点，并且讨论现有的一 些路由发现算法，归纳总结它们的特点。随后设计了一种基于信号功率的可靠路由发现 s p r r d 算法，对该算法的各个组成部分以及它们的特点进行详细分析和描述。最后阐述 了s p r r d 算法的具体流程及其优点。 第四章首先确定了在a o d v 协议中实现s p r r d 算法的总体架构，形成了改进a o d v 协议。然后介绍了网络仿真软件n s 2 ，并且详细分析了a o d v 协议在n s 2 中的具体实现 机制。最后在该软件中实现了改进a o d v 协议。 第五章在n s 2 中建立不同的仿真环境，对比和分析改进a o d v 协议和普通a o d v 协 议在多个性能参数上的差异。 第六章对全文进行总结，并展望了未来的工作。 6 柯京i 吣i b 人学顺i ：m 究生学位论文第_ 二誊移动a dt o c 网络路吐l 协议分析。j 比较 第二章移动a dh o c 网络路由协议分析与比较 传统的路由协议主要分为基于距离矢量的路由协议( 如r i p ：r o u t i n gi n f o r m a t i o n p r o t o c 0 1 ) 8 1 和基于链路状态的路由协议( 如o s p f ：o p e ns h o r t e s tp a t h ) 9 1 ，它们都是针对 有线固定网络设计的，其拓扑固定，不会出现大的网络结构变化。而在移动a dh o c 网络 中，由于节点的任意移动以及无线信道的衰耗、干扰等原因导致网络拓扑结构动态、随机 地变化，使得常规的路由协议要花费很大的代价重建和维护路由，这将会占用大量的无线 信道资源，严重降低系统的性能。因此路由协议的设计成为当前移动a dh o c 网络研究中 的一个重点问题。 近二十年来，人们在移动a dh o c 网络路由协议研究方面做了大量的探索，提出了很 多适用于该网络的路由协议。如图2 1 所示，这些协议大致可以分为三类【5 】：平面路由( f l a t r o u t i n g ) 协议、分层路由( h i e r a r c h i c a lr o u t i n g ) 协议和地理位置辅助的路由( g e o g r a p h i c p o s i t i o na s s i s t e dr o u t i n g ) 协议。 图2 1 移动a dh o c 网络路由协议分类 1 平面路由协议适用于较小规模的网络，在这类协议中网络的所有节点处于同一层次 上，各节点以相同的方式发送和响应路由控制分组。平面路由协议可以分为主动( p r o a c t i v e ) 路由协议和被动( r e a c t i v e ) 路由协议。它的主要优点是不存在特殊节点，通信量平均地 分散在网络中，路由算法易于实现；其主要缺点是可扩展性差，在一定程度上限制了网络 的规模。 7 南京邮l 【1 人学顺i ：f i j f 究生学位论文 第二章移动a dh o c 网络路由坍c 义分析j 比较 2 分层路由洳议，即将m 络中节点进行分组，然后分别给组内和组外节点不同的职能。 路由信息和更新信息仪仅针对网络的一部分节点，而不是整个网络，减少了路由表更新分 组的大小，从而降低了网络的丌销，并且具有良好的扩充性。但缺点是增加了网络整体的 路由复杂度。 3 地理位置辅助的路由协议，即网络中的每个节点都通过精确定位和测量装置获得自 身地理位置和移动状态信息，利用这些信息可将路由控制分组的传播限定在有限的区域 内，从而有效地减少网络中路由控制分组的丌销。 2 1 主动路由协议 主动路由协议又称为表驱动( t a b l e d r i v e n ) 路由协议或先应式路由协议，这种协议的 基本特点是无论有无数据通信要求，网络中的所有节点总是主动发现路由，试图维护到所 有已知目的节点的路由表。为此节点之间定期或者在网络拓扑结构发生变化时交换路由信 息，实时地维护网络拓扑信息。其主要的代表协议有d s d v ( d e s t i n a t i o n - s e q u e n c e d d i s t a n c e v e c t o r ) 、w r p ( w i r e l e s sr o u t i n gp r o t o c 0 1 ) 、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 ) 在盘 守0 2 1 1 目标序列距离矢量路由协议 目标序列距离矢量( d s d v ) i 0 1 路由协议是在距离矢量算法基础上改进设计的，被认 为是最早的移动a dh o c 网络路由协议。在d s d v 协议中，每个节点都要维护它所能到达 的所有目的节点的路由表，其中列出了所有可能到达的目的节点、到达目的节点的跳数和 由目的节点分配的序列号。每条路由都有一个序列号，主要用于判别路由是否过期，并可 防止路由坏路的产生。在d s d v 中只使用序列号最大的路由，如果两条路由具有相同的序 列号时，那么它将使用度量值最小的路由。路由表的信息交换采用时间驱动和事件驱动两 种模式：每个节点周期性地与相邻节点交换路由消息；或者当节点路由表发生变化时，将 其路由信息传给相邻：节点。路由表的更新采用两种方式：一种是全部更新( f u l ld u m p ) ， 即拓扑更新消息中将包括整个路由表；另一种方式是增量更新( i n c r e m e n t a lu p d a t e ) ，更新 消息中仅包含变化的路由部分。当网络相对稳定的时候增量更新可以避免额外的通信量， 有利于减轻网络的负担。但是在一个快速变化的网络中，增量更新包将变得很大，因此经 常会用到全部更新。 d s d v 协议中，节点维护着整个网络的路由信息，当有数据分组需要发送时，可以立 8 南京邮i u 人学f 吹i j 研( 生学位论文第一二常移功a di i o c m 络路由议分析j 比较 即发送，凶而适用于一些对实时性要求较高的、i k 务和网络环境。但是当网络拓扑结构变化 频繁时，节点需要频繁地交换拓扑更新消息，而且有时候可能刚获得的路由信息立刻又失 效了。同时由于需要周期性地更新消息，d s d v 将产生大量的网络丌销，这种丌销是随着 o ( n x n ) 来增长的，其中为网络节点数。因此d s d v 协议主要用于网络规模不足很大， 网络拓扑变化相对不是很频繁的网络环境。 2 1 2 无线路由协议 无线路由协议( w r p ) 【l i 】是另一种主动路由协议。在w r p 中，每个节点保存的信息 包括距离表、路由表、链路代价表和信息重传表。节点i 的距离表是一个矩阵，对于每一 个目的节点j 和i 的每一个邻接点k ，该距离表保存了经过邻接点k 到j 的距离d 和该路 径上j 的上一跳节点p 。节点i 的路由表包含从i 到每个目的节点j 的距离、此路径上i 的 下一跳和j 的上一跳信息、以及标志位用来说明此路径是简单路径、环路、或者是无效路 由。链路代价表包含了至此节点的每个邻居节点的链接代价，以及从那个邻居节点收到无 错信息后的超期次数。信息重传表用于记录= 宵点已发送过的更新消息，让节点知道它的哪 个邻居节点没有应答更新消息，它将向该邻居节点重传此更新消息。 节点通过周期性地或者链路状态触发来与其邻居节点交换路由消息。如果自从上次更 新后路由表没有变化，则节点被要求发送一个“h e l l o ”消息来确保与邻居节点的连接性。当 收到一个更新消息后，节点修改其距离表，并且利用新信息来查找更好的路径，任何发现 的更好的路径将被传回给其原节点以便同步更新路由表。 w r p 的优点是通过记录到目的节点的距离信息和目的节点的上一跳节点信息，解决了 路由环路问题。但是由于w r p 要求节点维护4 张路由表，这就使得当网络规模扩大时， 节点将产生大量的存储歼销。而且利用“h e l l o ”消息保持连接性，消耗了网络的带宽，同时 也不允许节点处于睡眠状态，导致电池能量的耗费。 2 1 3 优化链路状态路由协议 优化链路状态路由( o l s r ) 1 2 1 协议是为了适应移动a dh o c 网络的需求，对传统的链 路状态算法进行优化而形成的路由协议。在o l s r 中，每个节点周期性地控制信息交换和 分布式计算，更新和维护网络拓扑。o l s r 协议的核心在于采用了多点中继( m p r ： m u l t i p o i n tr e l a y ) 机制。为了挑选m p r 集，每个节点用“h e l l o ”消息周期性地广播其一跳 邻居节点列表。每个节点从其一跳邻居节点中选择m p r 集，使得该节点通过这个集合转 9 南京1 1 1 1 1 1 u 人学f i ! ；! i ：o r j f 生学化论爻第一二章移功a dh o c i , 4 - 1 3 路协汉分析讣匕较 发的分组能够覆盖该节点所有的两跳节点。只有被选为m p r 的节点才能转发该= 爷点发送 的路由控制分组，其它的邻居节点收到该节点发送的分组后，只进行处理而不转发。凶此 o l s r 显著减少了网络中广播控制分组的数量，并且由于参与链路状态交换的节点规模减 小，更新分组的人小也得到了缩减。 2 2 被动路由协议 被动路山协议又称为按需( o n 。d e m a n d ) 路由协议或反应式路由协议。在这类协议中， 节点平时没有数据通信需求时不维护网络的全局拓扑信息和自身到网络中所有节点的路 由信息，而只在有数据通信需求，即源节点有数据分组需要发送的时候，才发起路由发现 过程以寻找到目的节点的有效路由。通信过程中对路由进行维护，长时间没有通信则删除 路由。本文的主要研究对象是被动路由协议，且在后面章节介绍的可靠路由发现算法就是 针对被动路由协议中路由发现机制的不足而设计的，为此本章将详细研究被动路由协议的 工作机制。 2 2 1 动态源路由协议 动态源路由( d s r ：d y n a m i cs o u r c er o u t i n g ) 1 3 】协议是一种基于源路由方式的被动路 由协议，它的显著特点是每个要发送的数据分组都携带到达目的节点的完整路由消息( 即 包含源节点、中问节点和目的节点的一张完整地址列表) 。d s r 协议主要包含路由发现和 路由维护两个部分，前者用于帮助源节点获得到达目的节点的路由，而后者则用于当路径 中的节点由于移动、关机等原因而使路由失效时检测当前路由的可用性。同时为提高系统 性能，在d s r 中还引入了路由缓存( r o u t ec a c h e ) 机制，节点可以在缓存中存贮多条路 由。下面对d s r 协议进行具体介绍。 路由发现( r o u t ed i s c o v e r y ) 机制：以图2 2 和2 3 为例描述d s r 的路由发现机制。 当源节点a 有数据分组要发送到目的节点f 时，首先检查其路由缓存表中是否有到达目的 节点的有效路由，如果存在的话，那么直接利用这条有效路由丌始发送数据分组，否则启 动路由发现机制。源节点a 首先生成并在网络中广播路由请求( r r e q ：r o u t er e q u e s t ) 分组，r r e q 分组中主要包括源节点地址、目的节点地址、路由记录以及请求i d 等域。其 中路由记录域用于记录从源节点到目的节点路径上的中| 、口j 节点地址，请求i d 域由源节点 管理， 用于唯一标识一个r r e q 分组。同时每个节点维护一张历 史r r e q 列表，以防止节点收到重复的r r e q 分组。如图2 2 所示为节点a 到节点f 的路 1 0 南京i i l l 1 人学帧i j 研究生学位论爻 第一：章移动a d | i o c m 络路f j l 协议分忻j 比较 由请求过程，虚线箭头代表r r e q 分组的发送，方框中的内容代表路由记录域。 o 甲 图2 2d s r 路由请求过程示例 q 。 每一个中间节点在接收到源节点的r r e q 分组之后，按照下列步骤来处理该分组： ( 1 ) 如果r r e q 分组中的 存在于当前节点的历史r r e q 列表中， 表明此r r e q 分组已经收到过，则丢弃该分组，不做任何处理； ( 2 ) 如果当前节点地址出现在路由记录域中，为防止出现路由环路，则丢弃该分组，不 做任何处理； ( 3 ) 如果当前节点就是该r r e q 分组的目的节点f 或者当前节点的路由缓存中存在到目 的节点f 的有效路由，则根据该r r e q 分组中路由记录的节点地址序列和路由缓存， 构造源节点a 到目的节点f 的路由。同时利用这条建立的路由生成一个路由应答 ( r r e p ：r o u t er e p l y ) 分组，并单播给源节点a 。如图2 3 所示为路由响应过程， 虚线箭头代表r r e p 分组的发送，方框中的内容为r r e p 分组中的源节点到目的节 点的最终路由； ( 4 ) 否则，将当前节点地址添加到此r r e q 分组中路由记录域的后面，然后向其邻居节 点广播该更新后的r r e q 分组。 。 o t l i 图2 3d s r 路由响应过程示例 八 u 一u 一囟 -、，_-ij、圈 塑堕堕! 堡叁兰竺! ：型! 壅竺兰垡堕茎笙二主堡垫垒! ! ! 竺型堑堕虫坐坚坌堑! 韭! 墼 在上述的步骤( 3 ) 中，目的节点f 或者中i b 节点在唯播r r e p 分组给源节点a 时， 需要考虑以下几种情况：。 ( 1 )发送r r e p 分组的当前节点如果在其路由缓存中存在到达源节点的有效路由时，它 将利用这条有效路由刚送r r e p 分组： ( 2 ) 否则，如果网络中的链路是双向的，则直接将r j t e q 分组中的路由记录反转作为到 达源节点的有效路由；如果链路不是双向的，则当前节点就需要向源节点发起路由 请求过程，并在新的e d 之e q 分组中捎带r r e p 的信息。由此可见，d s r 考虑了单向 链路的情况。 在上述过程中，目的节点f 可能收到具有相同源节点地址和请求i d ，但路由记录不同 的r r e q 分组，这说明源节点a 和目的节点f 之间存在多条路径。目的节点f 都将这些 路由记录存储到自己的路由缓存中，而在路由响应过程中，根掘最短原则选择跳数最小的 路由作为最终路由。如图2 3 所示，目的节点f 选择路由( a cdf ) 作为最终路由。 路由维护( r o u t em a i n t e n a n c e ) 机制：一旦节点在发送数据分组时发现需要使用的邻 接链路断歼，那么该节点会发送一个路由错误( r e r r ：r o u t ee r r o r ) 分组给这些断丌路由 的节点