（信号与信息处理专业论文）vanets多路径路由协议通信性能研究.pdf

摘要 川舢删删洲 y 2 14 0 9 2 0 摘要 近些年在车辆自组织网络中，对复杂的车辆运动进行建模及分析在环境因 素影响下路由协议的通信性能是一项富有挑战性的工作。本文通过背景调研， 了解车辆自组织网络及其特点，对国内外车辆自组织网络研究工作现状做了比 较详细的说明与分析，确定了本文的研究方向。首先分析了单路径路由协议的 原理，然后根据单路径路由协议的类型分别对表驱动和按需路由协议在车辆自 组织网络中的应用做出了介绍。 随着车辆自组织网络的发展，传统的单路径路由协议在大数据量和实时性 方面的不足性越来越明显。本文在白组织网络按需距离矢量( a dh o co n d e m a l l d v e c t o r ，a o d v ) 路由协议的基础上，通过改进其部分功能模块，提出了一种增 强型自组织网络按需距离矢量( e n h a i l c e da dh o co n d e m a i l dv e c t o r ，e a o d v ) 路由协议，该路由协议以跳数作为选择路径的标准，在源节点和目的节点之间 建立多条路径。为了更好地对提出的改进路由协议的性能做评判，我们讨论了 车辆速度、移动模型及车辆密度等影响因子。更为直观地表现出协议的性能， 本文通过仿真平台n s 2 对单路径路由协议a o d v 和提出的多路径路由协议 e a o d v 进行的仿真实验，在设定的十字路口移动模型中，研究它们在不同影响 因子下的吞吐量、时延及丢包率。本文的研究工作可以为车辆自组织网络提供 科学依据。 关键字：车辆自组织网络；a o d v ；e a o d v ；n s 2 ； a b s t r a c t a b s t r a c t m o d e i i n gc o m p l i c a t e dv e h i c u l a rt r a 街cb e h a v i o ra 1 1 da n a l y z i n ge f r e c t so nt h e c o m m u n i c a t i o np e r f 0 姗a n c eo fr o u t i n gp r o t o c o i st a k e nb ye n v i r o n m e n t a lf a c t o r si n v a n e t i sac h a l l e n 百n gt a s ki nm ep a s ts e v e r a ly e a r s i nt h i sp a p e r ，w e 咖d yt h e b a c k 目o u n d ， u n d e r s t a l l d i n gv a n e t sa n di t sc h a r a c t e r i s t i c s ， g i v i n g ad e t a i l e d e x p l a n a t i o na n da n a l y s i sa b o u t 、厂a n e t s r e s e a r c hi nb o t hd o m e s t i ca i l df o r e i g n ， d e t e n i l i n i n gt h ed i r e c t i o no ft h j sp a p e r f i r s t l yw ea n a l y z ep r i n c i p l eo fs i n g l e p 批 r o u t i n gp r o t o c o l s ，t h e nr e s p e c t i v e l yi n 仃o d u c i n gt h et a b l e “v e na n do n d e m a l l d r o u t i n gp r o t o c o l s a p p l i c a t i o ni nv a n e t sb a s e do n 咖eo fs i n g l e 巾a t hr o u t i n g p m t o c o l s w i t ht h ed e v e l o p m e n to f 州e t s ，t h es h o r t c o m i n go ft r a d i t i o n a l s i n g l e p a 山 r o u t i n gp r o t o c o l si sm o r ea 1 1 dm o r eo b v i o u si na s p e c to f1 a 略ed a t aa i l dr e a l t i m e b a s e do na o d v r o u t i n gp r o t o c o l ，、ei m p r o v ei t sf u n c t i o n a lm o d u l e s ，p r o p o s i n ga n e n 1 a n c e da dh o co n d e m a j l dv e c t o rr o u t i n gp r o t o c 0 1 ，a j l dt h i s r o u t i n gp r o t o c o l c h o o s e sh o pc o u n ta sm e t r i co fc h o o s i n gp a m ，b u i l d i n gm u l t i p l ep a c l l sb e t w e e ns o u r c e a n dd e s t i n a t i o n t bb e t t e re v a l u a t et l l e p r o p o s e dr o u t i n gp r o t o c o l ，、v et a k ev e l l i c l e s s p e e d ，m o b i l i 够m o d u l e ，v e h i c l e sd e n s i t yi n t oc o n s i d e r a t i o n 1 bm o r ei n n l i t i v e l y d e m o n s t r a t ep e 而r m a n c eo ft h e p r o p o s e dr o u t i n gp r o t o c o l ，w ed os i i n u l a t i o n e x p e r i m e n t so ns i n g i e p a mr o u t i n gp r o t o c o la o d va i l dt h ep r o p o s e dr o u t i n g p r o t o c o l e a o d vt u 曲p l a t f o n l ln s 2 ，i nt h e m o b i l i 够m o d e lo fc r o s s m a d ，s m d y i n g t 1 1 r o u g h p u t ，d e l a ya n dp a c k e tl o s sr a t i ou r l d e rt h ee 行e c to fd i 丘e r e n tf a c t o r s t h er e s u l t o ft h j sp a p e rc a n p r o v i d et h e o r e t i c a lb a s i sf o r 觚u r es t u d yo f 埘e t s k e yw o r d s ：v a n e l s ；a o d v ；e a o d v ；n s 2 ； i l 第1 章绪论 第1 章绪论 1 1 课题的背景和意义 随着我国经济的快速发展，车辆数量持续增长，汽车在人们的生活中扮演 着越来越重要的角色。近些年，高速公路上发生的交通事故、民用机动车肇事 死亡人数、以及因违法行驶、违法装载导致的道路事故死亡人数都有明显的攀 升。交通事故的急剧增加，严重的交通堵塞等问题受到了人们很大的关注和重 视。公安部表示，中国交通事故死亡人数占全世界的1 6 左右，如何解决交通 面临的这些问题，提高交通的安全性是一个关系和谐经济发展的重要因素。这 些对交通安全的迫切需求就促使了一种新型的移动自组织网络的出现，即车辆 自组织网络( v e l l i c l ea dh o cn e 咖r k s ，w n e t s ) 。 蝌e t s 是基于移动自组织网络( m o b i l ea dh o cn e 铆o r k s ，m a n e t s ) 的一 种新型网络，有着和m a n e t s 相似的网络结构，但由于蝌e t s 自身的特点， 这使得与m a n e t s 有着不同之处。现有的基于m a n e t s 的研究结果和技术不能 直接用于w 心e t s ，特别是路由层。在a dh o c 和m a n e t s 中现有的路由协议 是否适应于k n e t s 以及这些协议在蝌e t s 中的性能评估对于设计、优化 e t s 路由协议是必要的。 在v a n e t s 中，由于干扰，路径损耗和信道衰落，网络的性能随着路径上 跳数的增加而降低。研究表明随着数据包长距离的传输，网络的吞吐量下降， 由于数据处理，信道争用和数据重传的原因，端到端的时延增大，丢包率随着 跳数的增加而变大。采用传统的单路径路由协议使得蝌e t s 的性能在吞吐 量、时延、丢包率和链路的可靠性等方面受到限制，近些年来许多研究人员都试 图通过各种技术来提高w 州e t s 的性能。在这些方法中，多路径路由是被认为 最有潜力的解决方法，其用于改善端到端时延和数据包的投包率。同单路径路 由比较，多路径路由具有降低时延、聚合带宽、平衡负载和提高可靠性等优点。 在蝌e t s 中采用多路径路由协议，源节点和目的节点之间的通信过程中，数 据包同时在多条路径上传输，吞吐量和端到端的时延将有明显的改善，而且投 包率也会增大【2 】。有研究【3 】通过联合多路径路由和编码方法提高网络的可靠性。 由于自组织网络的特性使得提供可靠的链接很困难，为了提高网络的性能，提 第1 章绪论 出了一种多路径和编码( m u l t i p l ed e s c r i p t i o nc o d i n g ，m d c ) 联合的方法，通过 将信息分割成为多个小块，在源节点和目的节点之间沿着不同的路径传输，在 目的节点处将这些小块连接起来，试图通过这样的方式来达到提高网络性能的 目的。 为了方便和有效地管理城市交通，减少交通堵塞和交通事故，提高城市交 通的便捷和安全，就需要w 州e t s 针对交通安全的需要提供相应的服务。研究 w n e t s 中的多路径路由协议仅仅在路由层面上提出相应的解决方案，使得 w n e t s 在吞吐量、时延、丢包率等方面的性能得到提升，让v a n e t s 能够满足 图像，视频等资源的共享，利用这些共享的资源信息来对交通进行管理。 蝌e t s 的应用将使得交通管理更加方便和有效，其中埘e t s 的应用主要 包括交通管理和多媒体信息共享。在交通管理方面，蝌e t s 可以提供道路堵塞， 交通事故等信息，帮助驾驶员避免碰撞，在十字路口和人群密度较高等位置进 行协调和引导，这样可以有效地提高行车安全，减少交通事故和道路堵塞，提 高管理城市交通的效率。在多媒体信息共享方面，在一定区域里面车辆之间可 以共享天气信息、加油站和空余停车位地理位置等信息。v a n e t s 还可以接入 i n t e m e t ，为用户提供导航、资讯信息和多种娱乐服务。 1 2 车辆自组织网络及其特点 车辆自组织网络通信主要是指车辆之间及车辆和路基设施之间的通信，可 以通过短距离通信技术实现。与传感器网络相比，车辆自组织网络主要有两个 优势，首先，网络成本较低，易部署和操作等。其次，从通信技术方面来看， 智能交通系统中很多信息都含有地理位置信息，车辆自组织网络能够方便地为 相邻车辆建立实时或非实时的短距离通信。 w 州e t s 可以看作m a n e t s 在特殊场景下的一个应用，或者说是智能交通 ( i n t e l l i g e mt r a l l s p o r ts y s t e m ，i t s ) 的组成部分，但是在交通安全方面，把 蝌e t s 作为一个新的研究领域还是很有必要的。同m a n e t s 相似，在e t s 中，没有中央节点及服务节点来指挥网络中的通信，节点以一种分布式的方式 自我组织和自我管理消息。在这样的网络中，节点既是服务器也是客户终端， 节点之间平等的交换和共享信息。除了这些特点之外，蝌e t s 还有一些不同于 m a n e t s 的特征： 2 第1 章绪论 ( 1 ) 快速变化的拓扑结构 在车辆自组织网络中，由于车辆快速和频繁的移动，导致网络的拓扑结构 快速和频繁的变化。在高速公路上，车辆的移动的速度为9 0 k m p h ( 2 5 州s ) 。假 定车辆之间的有效通信距离为2 5 0 m ，两车相对行驶，两车之间的链接最多持续 1 0 秒。这表明当车辆作为网络中的节点时，网络节点拓扑结构的变化是很快的， 并且能够保持有效链接的网络节点拓扑结构同样也是快速变化的。 ( 2 ) 不可靠的链接 网络拓扑结构的快速变化导致网络不能提供可靠的链接，在车辆进行通信 的过程中，由于拓扑结构的变化、建筑物的阻挡等容易造成链接断开。 ( 3 ) 车辆移动模型 车辆的移动受到道路、交通灯、限速、交通状况、驾驶员的习惯等影响。 移动场景和移动模型的正确建立对于v a n e t s 路由协议的设计和评估有着重要 的意义。 ( 4 ) 庞大的网络规模 e t s 可以覆盖一个城市、多个城市，甚至一个国家。为了w 州e t s 的实 用性，因此需要对v a n e t s 的伸缩性设计相关的协议。 ( 5 ) 基础设施的辅助 和m a n e t s 不同，蝌e t s 可以利用道路中的基础设施。这样可以使得 蝌e t s 中的协议表现出更好的性能。 ( 6 ) 丰富的资源 蝌e t s 中的车辆节点有充足的能量和计算资源。这将使得那些资源高需求 的协议变得可能。 1 3 国内外研究现状 在车辆自组织网络研究方面，国外的研究项目较多。安全行车通信( s e c u r e v e l l i c u l a rc o m m u i l i c a t i o n ，s e v e c o m 【4 1 ) 是一个欧洲赞助的项目，该项目研究车辆 通信安全定义和车辆交通安全的设备。s e v e c o m 认为为了提高道路安全和优化 道路交通，需要大范围的部署车辆间通信设施，并且强调车辆通信网络的安全 性，包括车辆之间的通信和车辆同基础设施之间通信的安全。它的目标就是对 这一类网络定义一个安全体系结构，并且在这些网络中对安全功能的融合提出 第1 章绪论 一个路线图。在广泛的安全威胁的情况下，为了增强未来蝌e t s 在道路应用 上的安全性，s e v e c o m 主要研究公路交通的通信，在该项目中岭j 分析车辆自组织 网络的连通性，通过仿真研究多个参数对网络性能的影响，包括车辆密度，无 线通信的范围，同时也研究了交通灯和路边设施的影响。研究对多种通信方式 进行了收集和分类，并且归纳了车辆自组织网络的特性【6 j 。最终提出了五种不同 通信方式，这五种通信方式几乎覆盖了w n e t s 中的所有应用。对于w 州e t s 中通信方式的研究将加深对w n e t s 的理解，可以进一步简化v a n e t s 通信系 统的建立。 研列7 j 展示了一个系统模型，在这个模型中包括一系列机制，通过这些机制 完善车辆通信的安全性和提高车辆通信系统用户地理位置的保密性。 s a f e s p o t 峭j 是一个综合研究项目，它由欧盟委员会信息社会技术部赞助。 s a f e s p o t 研究车辆间信息同路边基础设施之间的信息的结合，s a f e s p o t 旨 在创建了一个动态合作网络，在网络中车辆和道路基础设施可以相互通信，通 过共享道路上收集的信息提高驾驶员对车辆周边事物的观察力，对于潜在的危 险情况可以提前监测到，这样可以在时间和空间上增强驾驶员对周围情况的认 识。s a f e s p o t 的目标是通过路边基础设施为车辆发送安全信息建立一个开放、 灵活和模块化通信平台。 w 町c h o v e r p j 主要监测复杂的交通环境，往往在这样的交通环境中行人、 自行车和摩托车同其他车辆一同行驶。这就需要借助短程通信和视频传感技术 建立一个实时的监测系统，并且对复杂环境中的物体进行准确的定位。 近些年，人们针对不同的应用场景提出了多种路由协议【l0 | ，并且根据不同 的应用进行分类和比较。然而可以发现，大部分协议都是对单路径的路由协议 进行优化和扩展，如动态源路由( d y n 觚l i cs o u r c er o u t i l l g ，d s r ) 、自组织网络 按需距离矢量( a dh o co n d e m a l l dd i s t a n c ev e c t o r ，a o d v ) 等。由于单路径网 络延时和传输数据时控制包的开销都比较大，并且在负载较大时，将面临网络 堵塞的问题，尤其在视频传输方面，网络的传输延时不能保证视频服务质量。 多路径路由在上述方面都都有良好的表现，因此，多路径路由算法的研究越来 越多地受到人们的关注。 在有线传输网络中，多路径传输的机制经常使用。在有线网络中提出的基 于链路状态的表驱动多路径路由协议并不适合自组织网络。研究【】提出了一种 按需路由的方案s m r ( s p l i tm u l t i p a ：c 1 1r o u t i l l g ) ，通过建立最大不相交的多条路 4 第1 章绪论 径，实现在多条路径上传输数据。通过多个路由减小路由修复过程和控制消息 开销，同时将每个数据包分配到有效的多条路径上。这种数据包分配的方法有 效地利用网络可用的资源，并且阻止了路由路径上的节点由于负载过重而导致 的堵塞。文献【2 j 分析了在蝌e t s 中节点不相交多路径路由的性能，通过大量的 仿真实验研究不相交路径上节点的相互干扰的对网络性能的影响。同单路径路 由相比，节点不相交路径是否提升网络性能取决于路径的耦合和源节点到目的 节点的距离。并且指出当节点不相交路径正确选择，在蝌e t s 网络中应用节 点不相交多路径路由可以明显降低时延和提升投包率。 1 4 课题来源 本课题主要为2 0 1 0 年江西省研究生创新专项资金资助项目多载荷移动自 组织网络高性能接入协议研究n o y c l o a 0 3 2 、江西省自然科学基金多载荷 移动自组织网络的自主信息融合方法研究n o 2 0 1 0 g q s 0 1 5 3 中关于路由协议研 究与改进问题，为项目中的主题提供理论与技术基础。 1 5 本文研究内容 对于评估w 州e t s 协议及服务，最重要的是进行户外实验，如i e e e 8 0 2 1 1 p 和i e e e 8 0 2 1 6 等众多无线技术已经应用于无线通信中，大量的实验来评估检测 是必不可少的，实验中需要考虑全面，对各种情况都要包含，实验费用的开销 是很大的。由此可见，软件仿真对于模拟现实场景是一种非常重要的方法。 对于蝌e t s 的仿真可以分为模型仿真和网络仿真，网络仿真用来评估在 多种情况下的网络协议和应用，模型仿真主要是针对车辆和车辆移动的场景， 两种仿真独立工作但是满足w n e t s 需要，那么就需要将这些仿真结合起来满 足仿真实验的需要。众多仿真工具都试图解决埘e t s 中移动模型和网络仿真 的问题，但是每种方法都有自身的缺点，很少有仿真工具适用于蝌e t s ，那么 选择一个合适的仿真工具对于n e t s 仿真是一个需要解决的问题，本文将会 介绍网络仿真工具n s 2 。 在蝌e t s 中路由协议的通信性能容易受到环境因子的影响，在近些年， 分析这些环境因子对整个网络的影响及建立车辆移动模型一直就是一个难题。 在本文中，研究了单路径路由和多路径路由协议，然后分析了车辆节点密度， 5 第1 章绪论 车辆节点速度等对网络性能的影响。为了更好的理解，通过建立车辆移动模型， 将车辆移动模型添加到网络仿真工具n s 2 中，在不同的仿真参数情况下，仿真 分析白组织网络按需距离矢量路由协议和增强型自组织网络按需距离矢量路由 协议，处理仿真得到的数据，计算出w 州e t s 网络中吞吐量、丢包率和端到端 的平均时延。 第二章阐述了单路径路由协议的原理，从单路径路由协议的分类入手，分 别介绍了表驱动路由协议及按需路由协议，同时分别分析了表驱动路由协议和 按需路由协议在车辆自组织网络中的应用。为后面的多路径路由协议的设计提 供理论依据。 第三章对多路径路由协议进行研究，首先研究多路径在车辆自组织网络中 的应用，并且结合车辆自组织网络的特点提出了多路径路由协议的设计思想。 并且给出了多路径路由协议的主要模块，最后从定性和定量方面介绍了路由协 议的设计要求，为后续的仿真实验提供依据。 第四章将介绍仿真实验，在仿真工具、车辆自组织网络中的影响因子及网 络性能参数等方面进行分析并且提出可行的仿真实验方案，最后通过仿真实验 结果对提出的多路径路由协议做验证分析。 第五章总结本课题的工作及在研究本课题过程中取得的成果，并且提出了 今后研究的目标和方向。 6 第2 章单路径路由协议原理与分析 第2 章单路径路由协议原理与分析 近些年来，埘e t s 中的路由越来越受到人们的关注。作为m a n e t s 的特 例，蝌e t s 有着自身的特点：节点移动性，动态和约束的拓扑结构和较高的丢 包率。目前，已经提出了不少的路由解决方案，这些解决方案都是针对于 m a n e t s ，主要处理节点的移动性，创建路由表，发现路由，利用地理信息，利 用节点的移动性用于信息的传输，通过广播的方式进行消息的转发1 2 】。 2 1 单路径路由协议的分类 正如上文中所说，v a n e t s 和m a n e t s 有一些相同的特性，如不依赖基础 设施进行通信、自我组织网络、自我管理网络、低带宽和较短的无线传输范围。 因此大部分的a dh o c 网络中的路由协议仍然可以应用在v a n e t s 中，对于 v a n e t s 路由协议的分类可以参考a dh o c 中的分类。 2 1 1 表驱动路由协议 表驱动路由协议也被称为主动式路由协议【l4 1 。在该路由协议中，节点会维 护一张本地路由信息表，路由表中包含到达目的节点的路由信息，并且保持所 有路由信息一致。当源节需要发送数据时，通过查找本地路由表，可以快速获 得到达目的节点的路由信息。由于网络中节点的移动等原因，导致网络拓扑结 构发生变化时，通过表格驱动路由协议周期性地路由更新及转播更新，更新信 息将会传遍整个网络，通过节点之间相互交换信息来实时地维护网络中每个节 点的路由信息表。 表驱动路由协议的主要特点是，节点之间有无通信需求，节点都需要周期 性地路由信息交换。在表驱动路由协议中，不同的路由协议的差异性主要体现 在所需路由表的种类、数量不同，以及它们在更新路由表时所使用的方法不同。 当节点之间发送数据进行通信时，源节点查询本地路由表，若源节点发现本地 路由表中存在到达目的节点的路由，数据分组将从源节点出发沿着确定的路由 传输到目的节点，因此不需要发起路由寻找，端到端的时延就较小。可见表驱 动路由协议在端到端时延方面表现突出，能够保证网络通信时延较低，所以表 驱动路由协议适用于实时性要求较高和服务质量( q u a l 时o f s e r v i c e ，q o s 【l 川) 较为 7 第2 章单路径路由协议原理与分析 要求严格的通信中。在车辆自组织网络中，由于拓扑结构快速和频繁的变化， 为了保证路由信息的有效性，需要周期性地更新路由信息，这就需要路由更新 能够同当前网络拓扑变化保持一致。对于表驱动路由协议而言，这样快速和频 繁的路由更新将是一笔较大的开销。如果路由信息的更新速度不及网络拓扑结 构的变化，路由信息的有效性将得不到保证，这将导致路由信息的失效【l 引。 下面介绍两种表驱动路由协议。 ( 1 ) 目标序列距离矢量路由 目标序列距离矢量【”j ( d e s t i n a t i o n s e q u e n c e dd i s t a l l c e v e c t o r ，d s d v ) 路由 协议是典型的表驱动路由协议，由c p e r k i n s 和p b h a g w a t 于1 9 9 4 年提出，其是 在传统的贝耳曼福特【1 8 】( b e l l m a n f o r d ) 算法的基础上，通过优化和改进发展 而来。最早d s d v 通过修改和优化常规的i n t e m e t 路由协议以适应自组织网络， 随着d s d v 的发展，后来在路由信息协议( r o u t i n gi n f o m a t i o np r o t o c 0 1 ，r j p ) 的 基础上，引入了序列号机制，解决了计数无穷和路由环路的问题。同以往的路 由更新机制不同，在d s d v 中采用了事件驱动，时间驱动相结合的方法来更新 路由信息，这样就不是简单的周期性地更新路由信息，这样就减少了大量控制 消息对无线信道的占用【2 1j 。 d s d v 中由于采用时间驱动来更新路由信息，即使在网络闲置时也会消耗能 量和部分带宽。当网络的拓扑结构发生变化时，在网络收敛之前须分配新的序 列号，因此d s d v 不适合高速动态变化的网络。 目前d s d v 协议的应用范围并不大，许多协议都采用其他的方案，众所周 知的距离矢量协议a o d v ，作为反应式协议，不需要频繁的更新路由信息，因 此可以节省能量和带宽。 ( 2 ) 优化链路状态路由协议 优化链路状态路由协议( o p t i m i z el i n ks t a t er o u t i n g ，o l s r ) 是为移动a d h o c 网络开发的，它也可以应用于其他的无线a dh o c 网络。o l s r 是表驱动式 路由协议，通过h e l l o 和t o p o l o g yc o n 仃o l ( t c ) 消息来发现和广播整个移动 a dh o c 网络的链路状态信息。在o l s r 协议中的主要思想是多点中继( m u l t i p o i n t r e l a y ，m p r ) 。m p r 是专门选定的节点，在泛洪机制转发广播消息过程中，通 过m p r 节点转发控制消息，从而使控制消息泛洪的开销。这将大幅度减少消息 泛洪到网络中的所有节点所要求的转发次数。在0 l s r 协议中，链路状态信息 由被选为m p r 的节点产生，第二个优化就是减少在网络中洪泛的控制消息。因 8 第2 章单路径路由协议原理与分析 此，同经典的链路状态算法相比，部分链路状态信息分布在网络中。这些信息 将被用来进行路由计算。0 l s r 协议提供优化路由，由于采用m p r 技术，因此 在大而密集的网络中基本采用0 l s r 协议。 2 1 2 按需路由协议 在上述的表驱动路由协议中，基本上都是采用时间驱动来更新路由信息， 因此网络中的节点需要周期性地更新本地路由表信息。如果所处的网络中节点 数量较多，节点密度较大，如在车辆自组织网络中，由于车辆的移动性导致网 络拓扑结构快速频繁的变化，如果使用表驱动路由协议，为了保证路由信息的 有效性，需要大量的路由更新信息，这将会占用有限的信道资源，导致车辆之 间通信不畅。d a v i db j o l u l s o n1 9 9 6 年在c 锄e g i em e l l o n 大学研究出一种完全不 同于表驱动路由的方案：按需路由协议。之所以这种按需路由协议完全不同于 表驱动路由协议，主要体现在路由更新和路由发现方面，当网络采用按需路由 协议时，网络中的节点并不是周期性地更新路由表来维护本地路由表，只有在 节点之间相互通信需要发送数据时，才会促使路由发现并且寻找到达目的地的 路由 1 4 】。 ( 1 ) 动态源路由协议 动态源路由( d y n 锄i cs o u r c er o u t i n g ，d s r ) 协议属于按需路由协议，因 此其不需要周期性的进行路由维护，在d s r 中采用了源路由机制。确定源路由 需要在路由发现的过程中保存源节点和目的节点之间的每个节点的地址，通过 确定的路由来传送数据包。为了实现源路由，发送的每一个分组头部包含整条 路由中每个节点的地址信息。对于长距离的传输和节点密集网络，例如i p v 6 ， 这将导致大量的开销。为了避免使用源路由，d s r 允许数据包通过基于多跳的 转发。当消息到达目的节点时会触发路由回复，路由请求信息将会包含在路由 回复中。目的节点为了发送路由回复，目的节点必须有到达源节点的路由，如 果目的节点中存储有该路由线路，就可以直接使用该路由【2 引。否则，目的节点 将通过路由请求信息反转路由，建立目的节点到源节点的路由。在数据包传输 的过程中，当节点产生路由错误包时启动路由维护。错误跳将在节点路由缓存 中被删除，所有包含这个错误跳的路由将被截断。因此，路由发现将被启动来 确定最可行的路由。 d s r 协议采用的反应式方法，这与基于表驱动的主动式路由协议不同，d s r 9 第2 章单路径路由协议原理与分析 消除了在网络中周期泛洪路由表更新信息。在反应式方法中，当需要数据传输 时，路由将会被建立，因此这同在主动式方法中不同，反应式路由不需要实时 维护到网络中每个节点的路由。中间节点利用路由缓存信息有效的减小控制开 销。d s r 的不足就是路由维护机制不进行本地链路修复。陈旧的路由缓存信息 也可能在路由重建阶段导致故障，通常连接设置延迟要比表驱动协议要高。虽 然d s r 协议在静态和低速移动环境的性能表现良好，但是性能随着移动速度加 快迅速下降。此外，考虑到路由开销涉及在d s r 中采用的源路由机制，因此路 由开销同路径的长度成正比。 ( 2 ) 自组织网络按需距离矢量路由协议 2 0 0 1 年1 0 月互联网工程任务组织( i n t e m e te n g i n e e r i n gt a s kf o r c e ) 中的移 动a dh o c 工作组提出了第一个版本的a o d v 协议，该草案在2 0 0 3 年7 月的 r f c 3 5 6 1 中被提出。 a o d v 路由协议使用按需方法寻找路由，同采用时间驱动更新路由信息的 表驱动路由协议不同，在a o d v 中当节点之间需要通信时，若本地的路由信息 无效，源节点才在网络中发起路由请求并开始路由寻找。它采用目的序列号来 标明路径的新旧。a o d v 和d s r 协议最大的区别在于d s r 协议使用的是源路 由，在数据包中包含整条路径的路由信息，然而在a o d v 中源节点和中间节点 存储用于数据传输下一跳的信息。在按需路由协议中，源节点没有到达目的节 点的路由时，将在网络中洪泛路由请求包。a o d v 同其他按需路由协议的主要 区别是使用目标序列号来确定到达目的地最新路由。仅当接收的包的目标节点 序列号比自身存储的目标序列号大时，节点更新其路径信息。 a o d v 协议最大的优点是按需建立路由和通过目标序列号来确定到达目的 节点的最新路由。连接建立时延更短。a o d v 属于距离矢量路由协议，在距离 矢量协议中每个节点都知道其邻居节点，都有一张路由表，用来储存网络中的 所有节点、距离和下一跳地址，如表2 1 。 表2 1a o d v 路由表 1 0 第2 章单路径路由协议原理与分析 如果目的节点不可到达，则将路由表中的跳数设为无穷大。网络中每个节点周期的将 其路由表发送给其邻居节点。 2 2 表驱动路由协议在蝌e t s 中的应用 2 2 1d s d v 的应用与分析 在d s d v 中，网络中的每个节点维护一个路由表，每个路由表包括：目的 地址、下一跳节点地址、到达目的节点的跳数和目的节点相关序列号等，其中 目标序列号用来识别路由信息的新旧，节点根据路由信息的新旧进行路由更新 和分组转发。如下表2 2 简介d s d v 路由表示意图。 表2 2d s d v 路由表示意图 k 一一b ( ： 目的地下一跳跳数序列号目的地下一跳跳数序列号目的地下一跳跳数序列号 aa0a 一5 5 0 a a1a 5 5 0ab2a 5 5 0 b b 1b 一1 0 0 b b0b 1 0 0b b 1b 一1 0 0 c b 2c 一5 8 8cc1c 5 8 8cc0c 5 8 8 每个移动节点中都存储着这样的路由表，在蝌e t s 中数据包在节点之间 传递。埘e t s 中的每个节点周期地更新其自身的路由表，当网络拓扑结构发生 变化也会触发路由表的更新。 当网络拓扑结构变化被检测到，每个移动节点通过广播或者多播一个路由 表更新包来公告路由信息。更新包将会发送给直接相连接的节点，这表明每个 接收到路由表更新包的邻居节点距离发送节点只有一条的距离。这同传统的路 由算法不一样，在接收到更新包之后，邻居节点根据跳数的大小来更新其自身 的路由表。网络中所有节点都接收到一致度量值的更新包时，路由表的更新过 程将结束。更新数据将暂时保存，它用来协助节点发现到达指定目的节点的最 佳路由。如果节点在等待过程中收到同一个目的节点的多个更新包，根据转发 数据包的原则，节点将会选择序列号较新的路由，但是路由信息不会马上的进 行公告，仅当序列号发生变化时才会进行路由信息公告。如果对于同一个节点， 更新包有同样的序列号，将会使用较小度量值的更新包，现存的路由将会丢弃 或者作为备用路由存储。在这种情况下，更新包将会传递至网络中的每个移动 节点。 第2 章单路径路由协议原理与分析 i 、三卜二，一0 、 图2 1 自组织网络 每个节点路由表中参数值的动态变化和车载自组织网络的拓扑结构的变化 保持一致，为了保持一致，路由信息公告频率必须高，用以保证每个移动节点 在动态的移动网络中能够确定其他节点的位置。 图2 1 给出了一个在移动自组织网络中节点移动前后的例子。 图2 2 展示了在d s d v 中数据包传输过程。如图2 1 所示，节点h 4 有数据 发送给节点h 5 ，节点h 4 检查其自己的路由表，发现传输数据包的下一跳节点 是h 6 。如图2 2 ( 1 ) 所示，节点h 4 将数据包传输给节点h 6 。如图2 2 ( 2 ) ，当节 点h 6 收到节点h 4 的数据包后，在自己的路由表中查找目的节点为h 5 的路由， 也就是查找下一跳。如图2 2 ( 3 ) 所示，节点h 6 将根据路由表将数据包转发给节 点h 7 。路由过程将沿着路径重复下去，直到数据包最终到达目的节点h 5 。 下一踺垦鲢：随h 6 l h 6h 5数据 蜀懿地下一跳 l h 王h 4 附 珏2嚣釜 h 3h 4 h h 毒 h 5h 7 ( 1 ) 壬6h 7 1 2 第2 章单路径路由协议原理与分析 下一戳誊斡地h 6 h 6h 5数据 i 1 蚕的遮下一踺 h ih 连 卜 h 2 h 4 h 3h h h h 5h 7 h 6h 7 冈 1 _ j ( 2 ) 几：； 1 。一 图2 2 d s d v 数据包传输 表2 3 给出了节点h 6 在节点移动前自身的路由表。在路由表中的安置时间 项将决定何时删除过时的路由。 表2 3 节点h 6 的路由表 目的地下一跳跳数 序列号时间项 h 1h 43s 4 0 6 一h 1t 0 0 1 h 6 h 2h 42s 1 2 8 一h 2t 0 0 1 h 6 h 3h 43s 5 6 4 h 3t 0 0 1 一h 6 h 4h 41s 7 1 0 h 4t 0 0 2 h 6 h 5h 73s 3 9 2 h 5t 0 0 l - h 6 h 6h 60s 0 7 6 h 6t 0 0 1 一h 6 h 7h 71s 1 2 8 一h 7t 0 0 2 一h 6 h 8h 72s 0 5 0 一h 8t 0 0 2 一h 6 在路由信息更新过程中，节点会给每个更新包标记一个序列号用于区分更 1 3 第2 章单路径路由协议原理与分析 新包的新旧。序列号是单调递增数字，它将唯一确定给定节点的每个更新。 除了序列号和度量值外，更新的路由信息还包含目的节点的地址和到达目 的节点的下一跳节点地址。在d s d v 中有两种类型的更新包，一种称作全部转 储型，它包含全部可以利用的路由信息。另外一种称作增加型，它包含路由信 息变化的部分。表2 4 给出了节点处理一个增加型更新包的例子。 表2 4 ( 1 ) 节点h 7 更新包 目的地下一跳跳数序列号 h 7 h 7 0s 2 3 8 h 7 h 1h l1 s 5 1 6 h l h 2h 63 s 2 2 8 h 2 | h 3h 4 国 s 7 6 4 h 3 h 4h 62s 8 2 0 h 2 h 5h 8 圜 s 5 0 2 h 5 h 6h 61s 2 0 4 h 6 h 8 h 71 隆4 8 一h 到 在表2 4 ( 1 ) 中，节点h 7 公告其路由信息，同时广播其更新包。当节点h 6 接收到更新包，h 6 将检查更新包和其自身的路由表的每一项，然后更新其自身 的路由表。那些有较大序列号的项目将被更新到路由表中( 在表2 4 ( 1 ) 中，在更 新包中h 1 有更高的序列号s 5 1 6 h 1 。这个序列号将在路由更新后写入路由表中， 如表2 4 ( 3 ) 所示) ，这表明在更新路由表时首先考虑的是序列号的大小，而不是 跳数的大小。 表2 4 ( 2 ) 节点h 6 路由表 目的地下一跳跳数序列号时间项 h 1h 43 笛娴晦书到 t 0 0 1 h 6 h 2h 42 蟹蚓 t 0 0 1 h 6 h 3 h 4 国 s 7 6 4 h 3 t 0 0 1 h 6 h 4h 41s 8 2 0 一h 4t 0 0 2 h 6 h 5h 5 围 s 5 0 2 h 5 t 8 1 2 h 6 h 6h 60s 2 0 4 一h 6t 0 0 1 h 6 h 7h 71s 2 3 8 h 7t 0 0 2 h 6 h 8h 81 睡西阚 t 8 1 1 一h 6 1 4 第2 章单路径路由协议原理与分析 表2 4 ( 3 ) 节点h 6 更新路由表 目的地下一跳跳数序列号时间项 h 1 幽国 | s 5 1 6 h l l陌8 1 0 h6 l h 2h 42 | ：s 2 3 8 h 3 i t 0 0 1 一h 6 h 3h 4 国 s 7 6 4 h 3t 0 0 1 h 6 h 4h 41s 8 2 0 h 4t 0 0 2 一h 6 h 5h 5 固 s 5 0 2 一h 5t 8 1 2 h 6 h 6h 60s 2 0 4 h 6t 0 0 1 一h 6 h 7h 71s 2 3 8 h 7t 0 0 2 h 6 h 8h 7 1 匿! 鱼q 墨到 t 8 1 卜h 6 当序列号相同时，跳数较小的信息将会写入路由表中( 目的节点为h 5 ，在表 2 4 ( 1 ) 更新包中和表2 4 ( 2 ) 节点h 6 的路由表中有相同的序列号s 5 0 2 h 5 ，但是在 表2 4 ( 2 ) 中有较小的跳数，则表2 4 ( 2 ) 中h 5 的信息将更新至路由表中，如表2 4 ( 3 ) 所示) 。更新包中那些序列号较小的项目经常被丢弃掉( 如表2 4 ( 1 ) 中更新包中， 目的节点为h 2 和h 8 仅有较小的序列号，则他们都会被丢弃，如表2 4 ( 3 ) ) 。 2 2 2o l s r 的应用与分析 在o l s r 协议中，所有数据及其控制分组都采用统一的格式，0 l s r 的分组 格式如表2 5 所示。 在0 l s r 协议中，主要的特点是使用h e l l 0 消息，为了建立本地的链路信 息库和相邻区域的链路信息库，其方法就是在网络中定期性的交换h e l l o 消 息。下面简述h e l l o 消息机制。 表2 5o l s r 包格式 0 l s r 头部：包的长度包的序列号 消息类型有效时间 消息大小 源地址 消息： 生存时间跳数 消息序列号 消息 消息类型有效时间 消息大小 源地址 消息： 生存时间跳数 消息序列号 消息 1 5 第2 章单路径路由协议原理与分析 表2 6 h e l l o 消息 012345678 90123456789 o123456 789 o1 保留消息发送周期意愿 链路编码保留链路消息长度 相邻节点接口地址 相邻节点接口地址 链路编码保留链路消息长度 相邻节点接口地址 相邻节点接口地址 保留( r e s e r v e d ) 必须全设为o 。 消息发送周期( h t i m e ) 是指节点周期性发送h e l l o 消息的周期。 消息发送周期= c 术( 1 + 口1 6 ) 宰2 6 a 为高4 位所表示的整数，b 为低4 位所表示的整数。c 为比例因子。 意愿( w i l l i n g i l e s s ) 表示节点是否愿意承载和转发其他节点的信息。 链路编码( l i l l l ( c o d e ) 为链路编码信息，主要是针对发送接口和相邻节点接 口。 链路消息长度( l i l l l 【m e s s a g es i z e ) 为网络中表示链路状态信息的长度，以字 节为单位。 相邻节点接口地址( n e i g h b o ri n t e 妇ea d d r e s s ) 表示本节点的相邻节点中的 一个接口地址。 ( 1 ) 邻节点探测 显然o l s r 需要探测邻居节点和它们之间通信线路的状态，那么通过定期 发送h e l l 0 消息可以解决这一需求。邻居节点之间