（计算机应用技术专业论文）车载自组织网络按需地理位置路由协议研究.pdf

摘要车载自组织网络的一个重要特征是车辆节点具有很快的移动速度，尤其在高速公路场景中。车辆节点的快速移动特性，造成车载网络拓扑结构的动态变化，导致自组织网络中多跳( m u l t i h o p ) 路由的频繁断开，进而对路由算法的可靠性和数据传输的质量带来很大的挑战。本文提出了一种用于车载自组织网络的基于位置的路由算法一按需地理位置路由算法( o d g r ，o n d e m a l l dg e o g r a p m ci 沁u t i i l g ) 。o d g r 算法提出两个新的机制，以确保选择下一跳路由时采用的目的信息和邻居表信息的有效性和准确性，进而确保路由算法的可靠性。这两个机制分别是：( 1 ) 使用两种相互独立的消息实现对目的节点的位置信息的更新；使用这种更新机制，可以应对网络分割的情况，确保各个节点中记录的信息的一致性。( 2 ) 区别于主动建立邻居表的思想，o d g r 把按需的思想用在邻居表的建立方式上；o d g r 以按需的方式建立邻居表，可以消除节点的快速移动造成的邻居表的更新负担和信息的不准确。本研究在网络仿真工具n s 2 上，使用由节点移动模型仿真器、，狮e t m o b i s i i n产生的接近车辆真实轨迹的节点运动场景，比较了路由算法a o d v 和o d g r 性能。实验结果表明：在高速公路上，当车辆节点以至多4 9 1 1 1 s 2 的加速度和最高5 0 i i l s 的速度高速移动时，在端到端的丢包率和吞吐量这两个指标下，o d g r 路由算法的性能优于a o d v 算法。因此，o d g r 算法可以提供更好的数据传输质量。关键词：车载自组织网络基于位置路由按需多跳路由节点移动模型a b s t r a c to n ei m p o r t a n tf e a t u r eo fv e l l i c u l a ra dh o cn e t w o r ki 8l l i g hm o b i l i t ) ro fv e l l i c u l a rn o d e ，e s p e c i a u yi i li l i g h w a ys c e n 撕o s h i 曲m o b i l i 够o fv e l l i c u l a rn o d em a k e sk g hd y n a l t l i c so ft o p o l o g i cs 仰c t u r ef o rv e l l i c u l a rn e t 、o r k ，a n df m a l l yl e a d st o 丘e q u e n t l yd i s c o 蛐e c t i o no fm u l t i - h o pr o u t ei 1 1a dh o cn e 帆o r k 舢lo ft l l 锄b r i n gb i gc h a l l e n g e st or e l i a b i l 毋o fr o u t i n ga l g o r i m ma l l dq u a l 时o fd a t a 仃a 1 1 s 嘶s s i o n i i lt h i sp a p e r ，ap o s i t i o n - b a s e dr o u t i i l g a l g o r i t l l l nf o r 蝌e tc a l l e do n d e m a i l dg e o 伊a p l l i cr o u t i n g ( o d g r ) i sp r o p o s e d 0 d g ru s e s 觚on e wm e c h a i l i s m st om a k e跚r ei n f o 珊a t i o na b o u tp o s i t i o l l so ft h ed e s t 血a t i o nn o d e sa i l dn e i g h b o r sv a l i da i l dv e r a c 时w h e i lc h 0 0 s i n gn e x th o pr o u t e ，a i l df i n a l l yg u a r a i l t e et h er e l i a b i l 时o fr o u t i n ga l g o r i t h m t h et w om e c h 撕s m sa r el i s t e da sf o l l o w s ：( 1 )o d g ru s e st w oi n d e p e n d e n tm e s s a g e st or e a l i z eu p d a t eo fp o s i t i o ni 1 1 f o m l a t i o na b o u tt h ed e s t i n a t i o n t l l i sw a yo fu p d a t ec a nd e a lw i t ht h es i t u a t i o no fn e 帆o r kd i s c o n n e c t i o na i l dm a k es u r ec o n s i s t e n c yo fp o s i t i o ni i l f o m a t i o nr e c o r d e di nv a r i o u sn o d e s ( 2 ) d i n e 胤t6 i o mp r o a c t i v e l ys e t t i i l gu pt h en e i g h b o rt a b l e ，o d g ru s e st h ei d e ao fo n d e m a n dt ob u i l dt h en e i g h b o r 讪l e b yt h i sw a yo fs e t t i n gu pt h en e i g h b o rt a b l e ，i ti sa b l et 0e l i m i i l a t eu p d a t eb d e na n di n v e r a c i t ) ro fi 1 1 f o m a t i o nw h i c hi sc a u s e db yn o d e sh i g hm o b i l i 吼i i l 吐l i sr e s e a r c l l ，w ec o m p a r et h ep e o m a n c eo fa o d va n do d g ru s i n gn e 似o r ks i i i l u l a t o rn s - 2 as p e c i a l i z e dn o d em o b i l i 够m o d e ls i i i l u l a t o rc a l l e dv _ 锄e t m o b i s i mi su s e dt op r o d u c er e a l i s t i cv e l l i c u l a rm o v e m e n t 仃a c e t h ef i n a lr e s u l t so ft h er e s e a r c hp r o v et h a t ：o nt h em 曲w a y ，w h e nn o d em o v e sa tm a xa c c e l e r a t i o no f4 9 l i l a 1 1 da tm a xs p e e do f5 0 州s ，o d g ro 岬e 渤m sa o d va b o u tq u a l 时o fd a t at i a n s m i s s i o n k e yw o r d s ：v e l l i c u l a ra dh o cn e t w o r k ，p o s i t i o n - b a s e dr o u t i l l g ，o n d e m a i l d ，m u l t i - h o pr o u t e ，n o d em o b i l i t ym o d e l独创性声明本人声明所呈交的学位论文是本人在导师指导f 进行的研究：e 作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得基鲞盘堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名：建雪签字同期：刎9 年6 月7 同学位论文版权使用授权书本学位论文作者完全了解：叁鲞盘堂有关保留、使用学位论文的规定。特授权丕盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。( 保密的学位论文在解密后适用本授权说明)学位论文作者签名：吏雪导师签名：之舒f签字f 期：妒g 年6 月乡同签字h 期：臃5 月乡同第一章绪论1 1 背景和意义第一章绪论弟一早三百下匕2 0 世纪9 0 年代，随着计算机网络在生产和生活中的广泛应用，人们对网络通信提出了更高要求，希望在移动的环境下仍然能够享用网络资源。这个可移动通信的需求的推动了无线局域网( w l a n ，w i r e l e s sl o c a l 心e an e t 、) l ，o r k ) 技术的发展。区别于传统的有线网络，w l a n 不受网线限制，可以随时建立和拆除，它允许在移动范围内的用户随时都可以访问网络资源。1 9 9 7 年6 月，i e e e 发布了8 0 2 1 1 标准，为，a n 的物理层和m a c 层制定了统一的标准，这个标准的制定进一步推动了w l a n 的迅速发展【1 】。w l a n 网络的组建方式有两种：基于基础设施的模式( i n 仔a s n l l c m r e _ b a s e dm o d e ) 和自组织模式( a dh o cm o d e ) 。其中，以a dh o c 模式组建的移动自组织网络( m a n e t ，m o b i l ea dh o cn e 觚o r k ) 无需基础设施的支持，能够更加灵活方便的组建网络，拓宽了移动通信的应用领域，具有更广阔的发展前景嵋】。本研究涉及的车载自组织网络是移动自组织网络在车辆间通信的一个具体应用。在当代社会中，车辆一直在人们生活中发挥着巨大的作用。车辆的使用在给人们的生活带来便利的同时，也带来些让人头疼的问题，如频繁发生的交通事故、交通拥堵等。这些问题直接威胁着人们的生命，给人们的生活带来很大的困扰，成为各国政府亟待解决的问题。因此，关于如何消除交通事故隐患和改善交通质量的研究和尝试，日益引起人们的重视。随着无线通信技术的迅速发展和汽车电子技术的不断进步，很多政府和研究机构都尝试通过建立车辆间的通信( c ，i n t e r - v e h i c l ec o 眦眦i l i c a t i o n ) 系统来解决这些问题。2 0 0 3 年，国际电信联盟( i t u ) 在瑞士日内瓦召开的关于车辆通信标准化的会议上，有学者预计到2 0 1 0 年用于安全智能车辆的信息通信技术可以把交通事故发生的概率减少5 0 【3 j 。车辆间通信的需求和蕴含的巨大价值，推动了车载自组织网络( 蝌e t ，v e l l i c l ea dh o cn e 铆o r k ) 的出现和发展。车辆间通信在时间和地点上具有很大的随意性，因此v a n e t 网络是使用w l a n 技术，以a dh o c 模式建立起来的一种车辆间通信网络。具体的说，v a n e t是由装备了无线通信收发装置的车辆组成的一个多跳的临时性的自组织网络。v a n e t 网络的目的是为了提高行车的安全性和效率。蝌e t 具有极高的应用前景和研究价值。具体来说，在e t 上开发的第一章绪论应用和服务，根据它们不同的用途可以分为以下四类 4 】：( 1 ) 安全告警类应用。这类应用是在有事故发生或者存在事故隐患时，通过在车辆间及时的交互信息，使驾驶者可以及时的对突发的事故做出反应，避免造成更严重的事故。这类应用对时延的要求很高，因为能否有效地避免和减少交通事故，取决于事故告警信息能否快速、无差错地传播。目前，在v a n e t 领域进行的研究大多都是针对这类应用。( 2 ) 协同驾驶。这类应用的目的是帮助驾驶员快速、安全的通过十字路口、高速公路入口及出口等敏感地段。( 3 ) 分布式交通信息发布。这类应用是为了给驾驶者提供交通状况查询，如道路拥堵、车辆密度等信息，从而可以提高道路交通效率，改善车辆驾驶条件。这类应用对时延要求不高。( 4 ) 信息服务类应用。这类应用是为用户提供i n t e m e t 服务，如多媒体信息、移动办公和联网游戏等。这类应用在提供多样化服务的同时，也将加重网络负载，对车载网络的带宽提出了更高的要求。v a n e t 网络因为它独特的应用环境，存在着许多m a n e t 网络所不具备的特征，如快速移动的车辆节点、车辆移动受道路条件以及驾驶者行为影响等。这些特征使得m a n e t 的通信体系结构很难在蝌e t 网络中有让人满意的表现。在m a n e t 网络中使用的网络协议要么在v a n e t 中效率低下，要么根本就不可利用。因此，v a n e t 网络需要设计一套适合自身特征的通信体系结构。本研究课题涉及的是v a n e t 的通信体系结构中网络层的路由协议的设计。1 2 国内外研究现状车载自组织网络的研究，最早开始于2 0 世纪8 0 年代初的日本。随后，欧美多个国家和机构陆续开展了多个项目和一系列活动进行车载自组织网络的研究。2 0 0 0 年由欧盟( e u ) 资助开展的d r j v e ( d y n a 商cr a d i of o ri p s e i c e si nv e l l i c u l a re n v 的1 1 1 1 1 e m s ) 项目是在异构的多媒体无线环境下进行频谱有效的高质量的无线i p 通信，以实现车辆间的多媒体服务传输 5 】of l e e t n e t i n t 锄e to nt h er o a d 项目，是由6 个公司和3 个大学组成的联盟在2 0 0 0 年9 月启动，部分由德国的教育和科研机构资助，目的在于开发一个车辆间通信的平台，该平台可以用于协作的司机辅助系统、分散的移动的车辆数据应用和i m e m e t 通信服务 6 】。2 0 0 0年至2 0 0 3 年进行的c h a u f f e u ri i 项目是c h a u f f e u ri 项目的一个延续，这个项目的目标是建立一个c h a u f f e u r 辅助系统，使驾驶者能够在一个安全的距离内行驶在任何一个其他车辆的后面 7 1 。2 0 0 3 年在w e b 上已经可以获取2第一章绪论c h a u f f e u r2 的d 锄。演示。2 0 01 年至2 0 0 4 年欧洲进行了a d a s ei i ( a d v a n c e dd r i v e ra s s i s t a n c es y s t e m si 1 1e u r o p e ) 项目，目的是为了提高道路行车的安全性，效率和舒适性瞵j 。a d a s ei i 通过主动安全系统与道路两旁的基础设施相连接来实现这一目的。2 0 0 4 年，美国马里兰州立大学进行的t r a f j i c v i e w 项目，定义了一个架构来散布和收集在道路上行驶的车辆的信息【9 】o2 0 0 5 年，欧洲的6 家汽车制造商( b m w 、d a i 枷e 疋h 巧s l e r 和v o 墩s w a g e n 等) 成立了车辆问通信联盟( c 2 c c c ，c a r 2 c a rc o m m u l l i c a t i o nc o n s o r t i u m ) ，该联盟的目的是开发利用w l a n 技术的车辆间通信系统，以及车辆与基础设备间通信的欧洲通用标准【l o 】。2 0 0 4 年，德国继f l e e n e t 之后又开展了n o w ( n e 觚o r ko nw h e e l ) ，该项目的主要目标是解决在车辆通信中的通信协议和如何保证数据安全性【1 1 】。此外，还有欧洲开展的c a r t a l l c 2 0 0 0 项目等。国内在车载自组织网络方面的研究起步较晚。2 0 0 4 年，南京邮电学院的研究人员对当时用于车辆间通信的基于位置的路由协议进行了分析，并对存在的问题进行了探讨【i2 1 。2 0 0 7 年，武汉大学的江吴等人开展了v a n e t 网络中的传输控制协议的研究，提出了v a n e t 网络中传输控制协议的设计目标和设计要素【l3 1 。2 0 0 7 年，清华大学的向勇等也进行了关于蝌e t 的研究，他们对v a n e t 的特征、研究现状以及物理层、m a c 层和路由层的设计进行较全面的总结【1 4 】。除了以上项目之外，多个学术会议还开展了关于v a n e t 的专题研讨会。i e e e从1 9 9 2 年至2 0 0 7 年多次召开了智能车辆研讨会( i n t e l l i g e n tv e h i c l e ss y m p o s i u m ，i v ) ，讨论该领域的最新发展情况【】5 j 。2 0 0 4 年至2 0 0 7 年，m o b i c o m 专门召开了4 次专题研讨会，讨论v a n e t 上的应用开发情况以及路由协议设计等问题。2 0 0 6 2 0 0 7 年，i n f o c o m 也召开了关于v a n e t 研究的研讨会。1 3 本文工作文中首先分析了w n e t 网络具有的独特的特征，这些特征对应用于w 州e t网络的路由协议提出了特定的要求。其中，车辆节点的快速移动特性，因为其对网络拓扑的动态性产生的影响，成为在设计适用于v a n e t 网络的路由协议时必须要考虑的重要因素。目前为止，一些研究人员尝试用在烈e t 中的路由协议主要可以归结为两类：基于拓扑的路由协议和基于地理位置的路由协议。而在这两个类别中现存的路由协议，以a o d v 和g p s r 为典型代表，在应对节点的快速移动特性方面，都存在一些不足之处。本文所作的工作是提出了一种可以适应山e t 中节点的快速移动特性的路由算法，即按需的地理位置路由( o d g r ，o n d e m a i l dg e o 莎a p l l i cr o u t i n g ) 。o d g r第一章绪论是一种基于地理位置的路由算法；它与同类型的其他协议的不同之处在于，通过以下两个特征来解决由于节点的快速移动带来的信息不准确的问题：( 1 ) 为了应对网络分割的情况，使用两种互相独立的消息机制对目的节点的位置信息进行维护，一种消息在目的节点和它的邻居节点之间交互，另一种消息在除了目的节点之外的节点之间交互；( 2 ) 使用按需的思想来建立邻居表，即当需要访问邻居表时才临时的请求建立邻居表；通过这种方式，来消除节点的快速移动给通过主动的方式建立的邻居表带来的更新负担和不准确。o d g r 通过上述两个特征来确保计算下一跳路由时使用的目的节点的位置信息和邻居表中信息的准确性，进而保证数据传输的质量和可靠性。由于时间和资源的限制，本研究使用仿真工具来对提出的算法的性能进行评估。本研究使用仿真软件n s 2 对a o d v 和o d g r 这两种路由协议进行比较。同时，为了确保实验的准确性和可信度，在实验中所用的表示节点运动轨迹的运动文件是通过专门的车辆业务仿真工具( c a r 们伍cs i r n u l a t o r ) v a n e t m o b i s i m 产生的，由v a n e t m o b i s i l l l 产生的节点移动昀c e 是经过验证的接近于车辆的真实移动轨迹。1 4 章节安排本文内容可以分为三个部分，第一部分介绍课题背景、意义以及目前存在的各种路由技术的综述。第二部分，给出了本文提出的o d g r 算法的描述、以及仿真实验和结果分析。最后一部分是结论和展望。具体的安排如下：第一章是绪论部分，介绍n e t 网络产生的背景和意义，州e t 领域的研究现状，以及本文所作的工作内容。第二章，概要的介绍了目前可以应用于埘e t 网络的各种路由协议，以及各自的优缺点。第三章，详细分析了蝌e t 网络的特征给路由协议的设计带来的挑战，现存的协议在处理节点快速移动特征带来的问题时存在的不足；然后给出了o d g r 算法的解决方案，以及o d g r 算法中关键部分的工作流程，数据结构和使用的消息类型等。第四章，介绍了本课题的实验环境和工具，以及所作的仿真实验和实验结果的分析。第五章，结论与展望，对本文所作的工作和成果进行总结，同时指出了未来还可以继续尝试的改进方向等。4第二章v a n e t 网络中的路由技术第二章v a n e t 网络中的路由技术蝌e t 网络可以看作是m a n e t 网络的一个子类。但是，在n e t 网络中，车辆节点具有较快的移动速度，同时车辆节点的移动受到驾驶者行为的影响以及道路的约束，所有这些特征导致n e t 网络的行为与m a n e t 的行为存在很大的差别。因此，州e t 网络的体系结构的设计，包括物理层、m c 层和路由层，必须要考虑到这些特征。本章重点概述和分析了埘e t 网络的路由层的相关技术。在展开对路由层技术的讨论之前，下面首先对州e t 网络的物理层和m a c 层的各种技术进行简单的介绍。2 1v a n e t 网络中其他层技术的简述2 1 1v a n e t 网络的物理层的技术目前，w 州e t 网络中采用的物理层技术主要有两种：i e e e8 0 2 1 l b 标准和u t r at d da dh o c 技术。u t r at d da dh o c 指的是以a dh o c 模式运作的u t r at d d 技术。由于u t r at d d 是为蜂窝网络开发的，因此需要对u t r a t d d 进行一些修改使得移动节点能够以a dh o c 的模式通信，即u t r at d da dh o c 【1 6 】。表2 1 是u t r a t d da dh o c 和i e e e8 0 2 1 1 b 的物理层参数的比较。从表2 1 中可以看出，u t r a t d da dh o c 可以支持多码传输，提供超过1 m的通信距离，而且支持最大4 0 0 k n ：l l l 的移动速度等，因此u t r at d da dh o c 技术的性能比8 0 2 1 1 b 技术更好。此外，德国的学者通过链路级的仿真实验对u t r at d da dh o c 技术和8 0 2 1 1 b 技术的性能进行了比较，实验结果表明【1 7 】：在车载环境下，使用u t r at d da dh o c 技术，不论在高速公路还是在城市场景下，性能都优于8 0 2 1 1 b 技术。v 心e t 网络的物理层的选择除了受到以上技术性因素影响之外，还有一个很重要的非技术因素：为了有利于州e t 网络的普及应用，它的物理层需要工作在无需授权的频段内。2 0 0 3 年，美国的联邦通信委员会专门为车辆间通信划分了一个7 5 z 的免费频段用于专用短距离通信。欧洲的邮政电信组织( c e p t )也已经为u t r a t d d 技术提供了免除执照发放的2 0 1 0 到2 0 2 0 m h z 频段。综合上述因素，8 0 2 1 1 b 由于其价格便宜、实现简单、广泛普及而且工作在第二章、，a n e t 网络中的路由技术2 4 g h z 的免费频段等特点，广泛被科研实验所采用；如c 2 c 联盟就主张使用改进后的8 0 2 1 1 b 技术。而u t r a t d da dh o c 的性能更好，但是实现复杂并且造价较高；f l e e t n e t 项目采用了u t r a t d da dh o c 技术。表2 1u r r a t d da d h o c 和i e e e8 0 2 1 1 b 的物理层参数参数urntat d da dh o ci e e e8 0 2 1 1 b ( 1 m i t s )载波频率2 g h z2 。4 g h z系统带宽1 6 7m h z2 2m h z码片速率1 2 8m c p sl lm c p s扩频因子1 6 ( o v s f 码)1 l ( b a r k e r 码)多码传输1 1 6n 0调制o p s kd b p s k脉冲整形根升余弦( f 0 2 2 )频率掩模码率1 2o r1 3 ( 卷积码o r t u r b o 码)l ( n o f e c )最大输出功率( 欧洲)3 0d b m ( e i i 潆)2 0d b m ( e i l 冲)室外3 0 0 m ，室内l o o m最大传输距离超过1 k i n( 无障碍物)最大移动速度4 0 0 k n 讹只支持步行2 1 2v a n e t 网络的m a c 层的技术气n e t 网络的m a c 层的研究包括帧结构和接入方式的选择。由于w 州e t的物理层一般是基于8 0 2 1 1 标准和u r r at d d 技术，因此，建立在物理层之上的m a c 层的帧结构相应的也有两种类型。当物理层选用8 0 2 1 1 b 模块时，对应的m a c 层的帧的控制【l 副是：通过设置不同时间长度的帧间隔( i f s ) 来实现不同优先级别的信道接入机制，当传输优先级高的服务时使用短的帧间隔。而完整的u t r at d da dh o c 帧的结构由两部分组成【l9 】：一部分用于高优先级的服务；剩下的部分称作按需动态预留阶段( o n d e m a n dd y n 锄i cr e s e a t i o np h a s e ) ，这部分可以被不同的站动态的分配和预留，用于各种低优先级的服务。这种模式导致一个电路交换广播信道( c s b c ，c 沁u i t s w i t c h e db r o a d c a s tc h a l l l l e l ) 被引入，c s b c 主要被用于信令的目的，但是也可以被用于用户数据分组的传输。蝌e t 网络中采用的接入方式有以下几种：( 1 ) 8 0 2 1 1 d c f 【2 0 j ，该协议是目前自组织网络中广泛采用的m a c 协议，是一种基于c s m a c a 的异步竞争式6第二章l n e t 网络中的路由技术m a c 协议；8 0 2 1 1 d c f 是为支持分组突发业务而设计的，它不支持实时业务。( 2 ) r r a l o h a 【2 l j ( r e l i a b l er e s e a t i o na l o h a ) 协议，该协议是针对车载自组织网络的特点提出的一种新的随机接入方式，它是在r a l o h a 的基础上改进得到的，是一种基于时隙的同步预约式m a c 协议。( 3 ) 令牌环( t o k e i l 血g ) ，在具有g p s 系统的车辆间可以使用基于非竞争性的令牌环接入方式( 如w t r p协议【冽) ，可以提高信道的利用率，避免信道冲突，能够更好的满足车辆间安全预警通信的时延要求。除了以上m a c 协议之外，国内的一些研究机构也提出了一些针对车载自组织网络的m a c 协议，如郑州解放军信息工程大学的学者提出的b r - t d m “2 3 】和c c r a l o h a 【2 4 1 等。2 2 e t 网络中路由技术的概述目前，对州e t 网络的研究中最受关注的是对路由层的研究。在网络体系结构中的路由层的技术最容易受到应用环境和应用需求的影响，因此，在蝌e t网络中的路由协议的设计有更多的研究空间和研究价值。本文的研究就是针对路由协议的设计展开的。v a n e t 网络的路由协议，根据路由建立的方式可以大致划分为三种类型：( 1 ) 基于拓扑的路由协议( t o p o l o g y - b a s e dp r o t o c 0 1 ) ；( 2 ) 基于位置信息的路、由协议( p o s i t i o n - b a s e di i 怕册a t i o n p r o t o c 0 1 ) ；( 3 ) 基于地图的路由协议( m a p - b a s e dp r o t o c 0 1 ) 。下面分别对这三种路由协议进行介绍。2 2 1 基于拓扑的路由协议基于拓扑的路由协议的共同特点是在传输数据之前，需要建立和维持一条从源节点到目的节点的路径。a o d v 是这类协议的典型代表。2 2 1 1a o d v 路由协议a o d v 【2 5 ( a dh o co n d e m a n dd i s t a n c ev e c t o rr o u t i n g ) 是一种基于拓扑的路由协议。在a o d v 路由协议中，数据分组是根据预先建立好的路径在网络中传递的。同时a o d v 也是一种按需式的路由协议，“按需”意味着在a o d v 算法中的路径仅仅在需要的时候才被建立。a o d v 的一个显著特征是每个路由项都使用一个目的序列号，使用这个目的序列号可以避免路由循环( 1 0 0 p 一仔e e ) 。a o d v 路由协议由路由发现( r o u t ed i s c o v e r y ) 和路由维护( r o u t em a h n e n a n c e )第二章n e t 网络中的路由技术两部分组成。标准的a o d v 在路由发现时使用的广播机制是盲目泛洪( b l i n df l o o d i l l g ) 的广播机制。当路由失效时，a o d v 使用重新发起路由请求的方式进行路由维护。a o d v 的优点是：以按需方式( 即反应式的方式) 建立路由，这种方式可以减少网络中管理负载的数量，避免在网络规模扩大时增加网络拥塞的概率。它的不足是：a o d v 使用盲目泛洪的方式建立路由，将产生大量的冗余发送，增加管理负载的数量；随着网络规模的扩大，不断增加的管理负载会极大影响a o d v 的性能。2 2 1 2d r n s 路由协议方向路由节点选择，即d r n s ( d i r e c t e dr o u t e dn o d es e l e c t i o n ) ，这个方法尤其适用于车辆节点高速移动的高速公路的场景。在这种场景下，事先建立的路由会因为包含有以相反方向运动的节点而经常断开。d r n s 是对a o d v 作一个简单的扩展。d r n s 通过在路由请求中加入发送节点的方向，来确保所建立的路由中的所有节点以相同的方向运动。这样一个扩展的好处是可以最小化链路的断开；但是，这种方法弱化了自组织网络本身的连通性，增加了路由建立失败的可能。2 2 1 3a o d v p g b 路由协议标准a o d v 算法存在的一个问题是使用盲目泛洪的方式进行广播。瑞士苏黎世联邦理工学院( e t hz 谢c h ) 的研究人员提出了一种新的广播机制p g b 2 7 1 ( p r e f e 丌e dg r o u pb r o a d c a s 血g ) ，来代替在标准a o d v 中使用的盲目泛洪广播。图2 1p g b 广播中的节点集第二章v a n e t 网络中的路由技术p g b 的基本思想是根据感知的信号强度把接收到广播分组的节点分成三类：( 1 ) p r e f e r r e dg r o u p ( p g ) ，即最佳节点集，这个集合中的节点信号强度是适中的；( 2 ) i ng r o u p ，与p g 中节点相比，这个集合是信号更强的节点的集合；( 3 )o u tg r o u p ，与p g 中节点相比，这个集合是信号更弱的节点的集合。p g b 中节点的分类方式，如图2 1 所示。在确定一个节点是否可以作为转播( r e b r o a d c a s t ) 节点时，p g 组中的节点有最高优先级。p g b 通过把转播限制在某些节点上以达到两个设计目标：( 1 )减少冗余发送，从而减少控制消息开销；( 2 ) 获取更稳定的路由。使用p g b 作为广播机制，可以明显减少进行路由所需的管理负载，但是p g b在实现时有较高的复杂度。2 2 1 4a o d v d f r 路由协议a o d v d f r 【2 8 路由算法主要在a o d v 路由算法的基础上添加了以下两个特征：( 1 ) 当目的节点接收到通信请求时，周期性的发送路由更新，以减小节点的移动性带来的影响，尽可能的确保其他节点上保存的目的节点的位置的准确性；( 2 ) 当路由表中的下一跳失效时，( d i r e c t i o n a lf o r w a r d i n gr o u t i n g ) 方法，作为下一跳。为了缩短路由重构的时间，使用d f r选择在目的方向上最有前途的那个节点当路由失效时，使用d f r 来选择下一跳，可以缩短路由重构的时间，但是它的缺陷在于：这种确定下一跳的方法不能保证数据分组最终一定能够到达目的节点。2 2 1 5 本节小结总的来说，基于拓扑的路由协议，如a o d v 、a o d v p g b 等，它们的优点是：只要在源和目的之间存在着一条路径，基于拓扑的路由协议最终都能够成功的找到这条路径。这类协议存在的问题是路由建立和路由维护时需要很大的控制开销和耗费较多的时间；此外，路由维护时收敛的速度，即是否能够快速重构，会极大影响数据传输的质量。2 2 2 基于位置信息的路由协议与基于拓扑的路由协议的本质区别是：基于位置信息的路由协议不需要事先建立完整的路径，也不需要路由维护的过程；在基于位置的路由协议中，数据分组在到达目的节点的过程中经过的每一跳( p e r h o p ) 都是即时地独立地确定的。基于位置信息的路由协议一般由两部分组成：( 1 ) 位置服务( 1 0 c a t i o ns e i c e ) ，9第二章v a n e t 网络中的路由技术用来确定目的节点的位置；( 2 ) 转发策略( f o 九矾i n gs 仃a t e g y ) ，根据目的节点和直接邻居节点的位置来确定转发的下一跳。g p s r 路由协议是基于位置的路由协议的典型代表。2 2 2 1g p s r 路由协议g p s r 俐( g r e e d yp 耐m e t e rs t a t e l e s sr o m i i l g ) 是一种基于位置的路由协议。g p s r 的位置服务【3 0 】有以下几种类型：( 1 ) d r e a m 架构：每个节点都维护一个存储了所有其他节点的位置信息的数据库；它的信息准确程度依赖位置更新的频率。( 2 ) q u o n 蛐一b a s e d 位置服务：节点的位置更新被发送给某个可利用的子集( q u o n 蛐) ，位置请求都被定向到这些子集；为了确保一个节点能够找到所有其他节点的位置，这些子集必须有交集。( 3 ) g r i d 位置服务：a dh o c 网络区域被划分为若干个由方块组成的层次，每个节点维护相同层次的方块区域内的节点的位置信息。( 4 ) h o m e z o n e 位置服务，每个节点的位置都存储在它的h o m e z o n e中，这个h o m e z o n e 的位置可以通过在节点的i d 上应用一个h a s h 函数得到。，一- - - - 、f 、_ ：、jj人i x 1 ： j 7图2 2 贪婪转发dg p s r 采用的转发策略称为“贪婪转发 ( g f ，g r e e d yf o n ) i r a r d i i l g ) 。贪婪转发的思想是：当一个中间节点需要转发分组时，选择距离目的节点最近的那个邻居节点作为路由的下一跳，如图2 2 所示。理想情况下，这个转发的过程迭代进行直到数据分组到达接收端。在这种机制下进行转发将使数据包越来越接近目的节点，直到最终到达目的节点。贪婪转发存在的一个问题是：可能出现“局部最大”( 1 0 c a lm a ) 【m m ) 的情形。“局部最大”指一个节点的邻居节点中，没有比该节点更接近目的节点的邻居节点存在。g p s r 使用周界路由( p e 血n e t e rr o u t m g ) 策略来解决转发遇到的局部最大问题。g p s r 使用周界模式来解决局部最大时存在以下问题：使用右手规则时对一个特定方向的偏爱，可能导致选择一个跳数过多的路径。1 0第二章v ! f l n e t 网络中的路由技术此外，g p s r 没有考虑节点的移动性对路由带来的影响。一方面，g p s r 维护的邻居表的信息不保证是最新的；另一方面，关于目的的位置信息被添加到分组头部之后，在分组的转发过程中没有再被更新。而且，g p s r 的位置服务机制都很复杂，难于实现。2 2 2 2g s r 路由协议g s r 【3 l 】( g e o 伊a p m cs o u r c er o u t i i l g ) 是专门针对城市环境中的车辆通信提出的一种基于位置的路由协议。g s r 的特点是充分利用车辆的导航系统。具体的说，g s r 在以下两个方面对g p s r 进行改进：( 1 ) 位置服务：反应式的位置服务( i 也s ，r e a c t i v el o c a t i o ns e r v i c e ) ，使用一种广播机制在需要的时候确定另一个通信方的位置，这种位置请求的方法类似于a o d v 中的路径发现过程；( 2 ) 转发策略，基于通过导航系统获得的城市地图，建立一条a n c h o r 路径( 由从源节点到目的节点的路径上的十字路口的序列组成) ，进行源路由；在a 1 1 c h o r 点之间仍使用贪婪转发。g s r 的主要不足在于，使用计算出的a 1 1 c h o r 路径不能保证一定可以到达目的节点，因为在两个十字路口之间的街道上未必有足够数目的车辆来提供连通性( c o 皿e c t i v 埘) ；此外，a s t a r 进行源路由，需要在分组头部存储整个a n c h o r路径信息，可扩展性差，效率不高。2 2 2 3a s 吖凰路由协议a s t a r 【3 2 1 ( a m c h o 卜b a s e ds 仃e e ta n dt r a m ca w a r er o u t i n g ) 是专门为城市环境下的车辆间通信设计的一种基于位置的路由机制。a s t a r 在以下两个方面对g p s r 进行改进：( 1 ) 转发策略，使用加了权重的街道地图信息来计算a 1 1 c h o r 路径，进行源路由；( 2 ) 恢复策略，通过计算一条新的a n c h o r 路径来解决局部最大问题。a s w 瓜算法跟g s r 算法一样，需要建立a n c h o r 路径，而且进行源路由，因此也存在无法确保a 1 1 c h o r 路径的连通性，以及扩展性差的缺点。2 2 2 4g p s r - a g f 路由协议g p s r a gf 【2 7 1 ( a d v a n c e dg r e e d yf o 刑a r d 证g ) 算法在g p s r 的基础上增加了对节点移动性的考虑，作以下两点补充：( 1 ) 源和目的在位置发现服务的帮助下把各自的速度矢量( 包括运动方向和速度大小) 通知对方；( 2 ) 速度矢量还被添加到所有节点的h e l l o 信标消息中。通过添加节点的速度矢量，转发算法可以基于在邻居表中存储的速度矢量信息计算节点的当前位置，然后根据节点的当前位置来选择下一跳节点。第二章v a n e t 网络中的路由技术g p s r - a g f 算法与g p s r 算法相比，虽然考虑了节点移动性的对路由带来的影响，但是这种方法只是尝试来确保邻居节点的位置坐标的准确性，没有去判断计算后得到的邻居节点的位置是否还在节点s 的有效传输范围内。2 2 2 5c a r 路由协议c a r 【3 3 】( c o m e c t i v i 够a w a r er o u t i n g ) 是专门为车辆间通信设计的一个基于位置的路由协议。c a r 有两个显著特征：( 1 ) 可以不使用位置服务来发现目的的位置；能够在定位目的位置的同时，找到源和目的之间连通的a n c h o r 路径，进行源路由。( 2 ) 借助“g u 矾 机制，路径一旦建立之后，可以在拓扑发生变化的情况下自动做出调整，不需要新的路径发现过程。c a r 的g u a r d 机制，存在实现复杂度高的问题；此外，它还存在无法确保a n c h o r 路径的连通性和扩展性差的这两个方面的问题。2 2 2 6 本节小结基于位置的路由协议，如g p s r 、g s r 等，它们的优点是：数据分组从源节点到达目的节点的过程中经过的每一跳都是单独地即时地决定的，因此节省了基于拓扑的路由协议中建立路由和维护路由时花费的时间。但是，这个优点的代价是基于位置的路由协议需要一个管理位置信息的系统，建立这个位置信息管理系统的难点在于如何确保它提供的位置信息既及时又准确。2 2 3 基于地图的路由协议v a n e t 是应用在车辆间通信的移动自组织网络，它的组成要素车辆节点本身是没有能量限制的，因此车辆上可以安装很多电子设备，如车载g p s 系统、电子地图和导航系统等。而应用于车辆间通信的路由协议在选择路由时，就可以利用这些设备提供的信息。例如，g p s 系统和电子地图可以帮助节点获知自己的位置、邻居节点和道路拓扑信息，再利用导航系统中具备的路径规划等功能，就可以得到由节点集、道路集和转弯限制集等几个有限集合所描述和预知的整个网络的全局拓扑情况。这个全局拓扑信息能够对路由的建立提供强有力的支持，可以帮助路由算法更快、更准确地计算出从源到目的节点的最佳路径。基于地图的路由协议就是建立在由g p s 系统、电子地图等提供的信息的基础上的。基于地图的路由协议是一个崭新的研究课题，目前还没有学者提出这种类1 2第二章v a n e t 网络中的路由技术型的具体的协议。但是，基于地图的路由协议可以充分利用车载的电子设备来确保选择最佳的路由。因此，未来的车载自组织网络的路由协议的发展方向应该是位置与