（信息与通信工程专业论文）基于视频业务的ad+hoc网络路由技术的研究.pdf

南京邮电大学硕士研究生学位论文摘要 摘要 a dh o c 网络由一系列能自我配置的无线节点组成，该网络不需要借助任何基础设施。当 前，随着无线网络的快速发展，人们势必希望在a dh o e 网络中能够支持无线视频业务，然而 在a dh o c 网络开展视频应用会遇到许多技术难题。视频应用的关键要求之一是能够在高速动 态变化的网络环境中提供可接受的视频质量。 论文首先对国内外学者在本课题方面的研究现状做了简要介绍，描述了适合a dh o e 网络 的编码方案和多径路由技术，引入了采用多径路由传输多描述编码的框架。采用基于m d c 编 码的多径路由技术是在a dh o c 网络中进行视频传输的有效方法。但是大多数多经路由技术没 有很好地针对视频业务带宽大，延迟小，容忍一定程度的丢包等特点进行考虑和优化。 本文针对基于目前m d c 编码的多径路由协议的不足之处提出了改进方案，首先提出了移 动a dh o c 网络中基于速率控制策略的视频传输的失真模型，将最小化端到端视频失真作为 多径路由的选路标准，以满足视频业务在带宽、时延和丢包率方面的要求以及多跳网络状态 的动态变化。同时提出了用多信道机制来消除多条从源节点到目的节点路径之间的相互干 扰。基于n s 2 ，本文实现了改进的路由协议并进行了一系列的仿真，证明了它的良好性能。 关键字：a dh o c 网络；视频传输；路由；多信道；失真模型 a b s t r a c t a na dh o ew i r e l e s sn e t w o r ki sac o l l e c t i o no fw i r e l e s sn o d e s t h a ts e l 仁c o n 6 9 u 鹏t of 0 珊a n e 帆r kw i t h o u tt h ea i do fa n ye s t a b l i s h e di n f r a s t r u c t u r e n o w a d a y s ，w i t h t h er a p i dg r o w mo f 、v 1 陀i e s sn e t w o r k s ，w i r e l e s sv i d e os e r v i c e sa r e e x p e c t e dt ob es u p p o r t e di na dh o ew i r e l e s s n 乩o r k s h o w e v e r ，t h e r ea r es i g n i f i c a n tt e c h n i c a lb a r r i e r st h a th i n d e rt h ew i d e s p r e a dd e p l o y m e n t o fv i d e oa p p l i c a t i o n si nw i r e l e s sa dh o e n e t w o r k s o n eo ft h ek e yr e q u i r e m e n t sf o ras u c c e s s f u l d 印j o y m e n to fv i d e oa p p l i c a t i o n si ns u c hn e t w o r ki st h ea b i l i t yt op r o v i d e a c c e p t a b l ev i d e oq u a l i t y u n d e ra h i g h l yd y n 锄i ce n v i r o 啪e n t 一 f i r s t , w eh a v eab r i e fi n t r o d u c t i o nt ot h ei s s u e si nt h i sa r e a , a n dd e s c r i b et h e e 1 1 c o d i n gs c h e m e a i l dm u l t l p a t hr o u t i n g ，a n dt h e nw e i n t r o d u c eaf r a m e w o r kf o rm u l t i p a t ht r a n s m i s s i o no fv i d e o u s i n g m u l t i p i ed e s c r i p t i o nc o d i n g u s i n gm u l t i p a t hr o u t i n gw i t hm d c i sa ne f f e c t i v ew a yt ot r a n s f e r v 1 d e ot r a f f i ci na dh o en e t w o r k m o s tm u l t i - p a t hr o u t i n gd o n t t a k ec a r eo f 觚l do p t i i l l i z em e t n a l l s m i s s i o no fv i d e ot r a f f i cw h i c hh a sc h a r a c t e r i s t i co fl a r g eb a n d w i d t h ，l o wd e l a y 。t o l e r 肌c eo f l o wp a c k e tl o s sr a t i o a ni m p r o v e ds c h e m ew a s p r o p o s e di nt h i sp a p e rw h i c hb a s e do 1m u l t i - p a t hr o u t i n gw i t l lm d c i nt h i sp a p e r , w ef i r s tp r o p o s e dav i d e o - d i s t o r t i o nm o d u l eb a s e d o nr a t ec o n t r o ls t r a t e g yf o rv i d e o t r a n s m i s s i o ni na dh o cn e t w o r k w e s e a r c h i n gf o rm u l t i p l ep a t h sb e t 、e e ns o u r c ea i l dd e s t i n a t i o n t om t m m l z ee n dt oe n dv i d e od i s t o r t i o n m e a n w h i l e ，i no r d e rt oe l i m i n a t ei n t e d 凫r e n c e b e t 、v e e n m u l t i p j er o u t e sf r o ms o u r c et od e s t i n a t i o n , w ea s s i g nad i f f e r e n tf r e q u e n c yb a n dt oe a c hr o u t e t h e p e n o h n a n c eo ft h ei m p r o v e ds c h e m ew a ss i m u l a t e di nn s 2 t h er e s u l t ss h o w e d i t ss u p e r i o r p e r f o r m a n c e k e yw o r d ：a dh o cn e t w o r k ；v i d e ot r a n s m i s s i o n ；r o u t i n g ；m u l t i c h a n n e l ；d i s t o r t i o nm o d e l i i 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及所取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其 它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均己在论文中做了明确的说明并表示了谢意。 研究生签名醴日期 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本人电子文档的内容和纸制论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。 论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签气圣避导师签名：黟魄 名：- 2 u 一日期： 7 南京屯大学碗q f 究生学位论文第一章绪论 1 1 a d h o e 网络 第一章绪论 a d h o c 网络 1 】是一种没有有线基础设施支持的移动网络，网络中的节点均由移动主机构 成。在a dh o c 网络中，当两个移动主机在彼此的通信覆盖范围内时，它们可以直接通信。 但是由于移动主机的通信覆盖范围有限，如果两个相距较远的主机要进行通信，则需要通过 它们之闯的其它移动主机的转发才能实现。因此在a dh o e 网络中，主机同时还是路由器， 担负着寻找路由和转发报文的工作。在a dh o c 网络中，每个主机的通信范围有限，因此路 由一般都由多跳组成，数据通过多个主机的转发才能到达目的地。故a dh o e 网络也被称为多 跳无线网络。其结构如图11 所示。 胁 磐 掣 囝 鼍 一p 蔬“。9 1 缸1 _ ( a ) 物理网络结构( b ) 逻辑网络结构 图1 1 移动自组网示意图 与传统有线通信网络相比，移动自组网具有以下显著特点： ( 1 ) 动态变化的网络拓扑：在自组网中，移动终端能够以任意速度和任意方式在网中移动，加 上无线芨送装置的天线类型多种多样、发送功率的变化、无线信道的互相干扰、地形和天 气等综合因素的影响，移动终端问通过无线信道形成的网络拓扑随时可能发生变化，而且 变化的方式和速度都是难以预测的。 ( 2 ) 无中心和自组织性：在自组网中没有绝对的控制中心，所有节点的地位平等，网络中的节 点通过分布式算法来调节彼此的行为，无需人工干预和任何其它预置的网络设施，可以在 任何时候任何地方快速展开并自动组网。由于网络的分布式特征、节点的冗余性以及不存 在单点故障点，使得网络的健壮性和抗毁性不是很好。 南京邮电大学硕七研究生学位论文第一章绪论 ( 3 ) 自动配置：自动配置是自组网的基本特征，节点必须检测其它节点以及它们可以提供服务。 由于网络动态变化，自动配置过程需要确保网络能够正常工作，这涉及到连接i n t e r n e t 的 网关节点的更换，簇头的更新等。在网络形成阶段，节点可以就网络拓扑进行协商( 星形、 环形、点到点、点到多点、平面和分级) ，这依赖于网络的类型、底层的无线技术和应用 的需求。 ( 4 ) 链路带宽受限、容量时变：a dh o c 网络采用无线传输技术作为底层通信手段，由于无线信 道本身的物理特征，它所能提供的网络带宽相对有线信道要低得多。考虑到竞争共享无线 信道产生的冲突、信号衰减、噪音和信道间干扰等因素，移动终端得到的实际带宽远远小 于理论上的最大带宽。另外，由于拓扑动态变化导致每个节点转发的非自身作为目的地的 业务量随时间而变化，因此与有线网络不同，它的链路容量表现出时变特征。 ( 5 ) 存在单向无线信道：由于地理位置或节点发射功率等因素，在采用无线通信的自组网环境 中，可能存在单向信道。两个移动终端a 和b ，a 由于发射功率较大所以能够到达b ，而 反之不行，即存在一条a 一 b 的单向信道。 ( 6 ) f l 皂量受限：自组网内的移动节点一般需要依靠电池提供能量，由于网络节点的移动特征， 能量会被不断消耗，在电池容量没有大幅度提高前，节省功率将是自组网技术中一个需要 高度重视的问题，在进行系统设计时节能就成为一个非常重要的指标。 ( 7 ) 物理上安全有限：自组网由于采用无线信道、有限电源、分布式控制等技术，使得它更加 容易受到被动窃听、主动入侵、拒绝服务、剥夺“睡眠 等网络攻击。信道加密、抗干扰、 用户认证和其它安全措施都需要特别考虑。还需要克服无线链路的安全弱点以及移动拓扑 所带来的新的安全隐患。 1 2 a dh o c 网络中进行视频传输研究背景和面临的挑战 a dh o e 网络起源于7 0 年代末美军对分组无线网的研究，当时主要研究基本的信道接入 机制和如何提供基本的数据业务以及如何进行组网等，对于再a dh o e 网络中传输视频等多媒 体业务的研究很少涉及。但是随着信息技术的迅速发展、多媒体应用的开展、网络规模的增 加和硬件技术的进步以及需要与其他网络进行互联，传统的数据业务已经见见不能满足人们 对a dh o c 网络的需要。人们自然的会产生在a dh o c 网络上传送综合业务的要求，并且希望 能像固定的有限或蜂窝无线网络一样为不同业务的服务质量提供保障。 与固定有线网络和传统蜂窝网络不同，对于拓扑经常发生变化、带宽很窄、能源和内存 非常受限的a dh o e 网络而言，提供视频传输是一个复杂而全新的课题。a dh o e 网络中存在 一2 一 堕室堕皇奎堂堡主竺塞竺堂垡笙奎笙二兰笙鱼 大量的背景噪声和干扰，主机可以自由移动，无线信道的质量差并且网络带宽很有限。同时 移动主机处理能力受限，通常靠电池供电，并且容易受地方的有意破坏和干扰，特别是当网 络规模较大时，这些问题将更加突出。 在传统网络中为了支持多媒体业务，链路状态信息，如时延、带宽和出错率等，通常需 要即时的维护：但这一点在a dh o c 网络中却难以实现，因为无线链路的状态随时可能随周围 环境的变化而改变，并且稀少的带宽资源和主机的随意移动使这个问题更加复杂。网络资源 的匮乏容易导致网络发生拥塞，同时无线信道质量较差会造成分组的传输错误率增加，虽然 采用冗余编码、增大信号强度和更换路由等方法可以提高无线信道的质量，但是这也进一步 减少了网络的可用资源。许多有关无线网络中提供多媒体业务的研究大多基于单跳的有中心 的蜂窝网络模型，这些体系结构和保障机制也无法直接应用于多跳动态变化的a dh o c 网络。 此外，引入大量控制分组的保障机制也不能被a dh o c 网络接受，因为这样会过多地占用宝贵 地带宽，并导致分组碰撞地增加，结果会降低系统地整体效率。拓扑结构地动态变化也给在 a dh o e 网络中进行视频传输带来很大的困难，要消除或减轻网络拓扑变化对服务质量的影 响，需要m a c 层的相应支持以及路由协议能快速生成新的路径。因此，为了实现在a dh o e 网络中传输视频业务，需要多层相互优化协调以及多种机制相互结合，特别是对路由技术的 改进。 i 3 本文主要工作和章节安排 本文重点研究了基于a dh o e 网络视频传输的路由方案。从a dh o e 网络路由协议的研究， 相关路由的改进，n s 的仿真，性能分析等方面进行了深入的探讨研究和初步的尝试。本文针 对基于目前m d c 编码的多径路由协议的不足之处提出了改进方案，首先提出了多跳网络中基 于速率控制策略的视频传输的失真模型，将最小化端到端视频失真作为多径路由的选路标准， 以满足视频业务在带宽、时延和丢包率方面的要求以及多跳网络状态的动态变化。同时提出 多信道机制来消除多条从源节点到目的节点路径之间的相互干扰。基于n s 2 ，本文实现了改进 的路由协议并进行了一系列的仿真，证明了它的良好性能。 第一章介绍了a dh o c 网络以及在a dh o e 网络中进行视频传输所面临的挑战。 第二章较为详细的介绍了a dh o e 网络路由协议的相关研究，主要可分为两类路由协议， 先验式路由协议，反应式路由协议，同时对两类路由协议的性能进行了仿真和比较。 第三章介绍了目前用于在a dh o e 网络中进行视频传输的路由协议：基于m d c 编码的多 径路由协议，同时提出将多信道机制应用到多径路由中，用以解决路径间的干扰和相关路径 南京邮电人学硕士研究生学位论文 第一章绪论 的影响，提高网络吞吐率和接受端图象质量，并对基于多信道的多径路由协议的性能进行了 仿真。 第四章对当前基于视频业务的a dh o e 网络路由协议进行了分析，指出了将视频失真模型 和路由选择结合的必要性，并对当前的视频失真一般模型进行了修改，提出了基于速率控制 机制的视频失真模型和基于改进视频失真模型的最佳多径路由协议。 第五章结合了前两章的研究结果，提出了基于双信道机制的改进最佳多径路由协议，并 且对其在视频传输中的性能进行了仿真。 第六章对全文进行了总结并指出了未来的工作重点。 南京邮电大学硕士研究生学位论文第二章a dh o e 网络路由协议及其性能分析 第二章a dh o e 网络路由协议及其性能分析 2 1a dh o c 网络路由协议 a dh o e 网络是有一组具有路由功能的节点组成的分布式无线自组织网络，它不依靠任何 预设的网络基础设施。因为多跳网络中的节点的传输范围有限，源节点在向目的节点发送数 据时，通常需要其他节点的辅助，所以路由协议是a dh o e 网络中不可缺少的一部分。路由协 议的主要设计目标是：满足应用需求的同时尽量降低网络开销，取得资源利用的整体有效性， 扩大网络的吞吐量。其中，应用需求一般包括时延、时延抖动、丢包率等诸多因素。 a dh o e 网络中的路由协议主要包括路径产生、路径选择和路由维护三项核心功能。其中， 路径产生是指根据集中式或分布式的网络状态信息和用户业务需求生成路径，网络状态信息 和用户业务信息选择适当的路径，路径产生和路由维护这两项功能通常合在一起成为路由发 现。路径维护实质对所选路径进行维护。由于a dh o e 网络是一种没有预设基础设施的网络， 它工作于无线环境，通信带宽受限，而且节点具有移动性，因此，路由协议还要充分考虑这 些因素所造成的影响。路由协议的定义和功能见图2 1 。 多跳网络特性 无线链路 节点移动性 无网络基础设施 业务要求 网络能力 图2 1 路由协议的定义和功能 路由功能 路径产生 路径选择 路径维护 多跳网络的路由协议采用了许多独特的技术方法，用以解决关键技术问题。这些结束 问题主要包括以下几个方面： 1 路由环路避免问题 南京邮电大学硕士研究生学位论文 第二荦a dh o e 网络路由协议及其性能分析 按照路由协议所依据的基本路由算法不同，a dh o c 网络路由协议可分为基于链路状态的 路由协议、基于距离矢量的路由协议、源路由协议和反向链路协议。 在原路由协议中，由于路由信息标记在数据消息和路由控制消息的头部，本身具有环路 避免的特性。反向链路协议又包括全链路翻转和部分链路翻转两种作法。由于有向无环图具 有无环路特性，在网络稳定的情况下，不会出现路由问题；链路状态协议是在得到全部网络 拓扑信息的条件下进行路由计算的，所以也不会产生环路问题。而对于距离矢量路由协议， 由于控制消息经过不同的路径，在网络中的延时不同，如果采用过期的控制消息进行路由计 算，很可能产生环路问题。所以在距离矢量路由协议中，路由环路问题是一个关键性的问题。 信息标识技术是一种解决路由环路的技术。在路由协议中，每一个消息可用二元组( 源 节点，序列号) 来唯一标识。其中的序列号是在源节点中与时间相关的唯一值，序列号越高， 消息越新。消息在路由过程中，会收到网络延迟。阻塞和链路通断的影响，因此在到达目的 节点时，会发生顺序颠倒和重复，而消息标识就是用来保证过滤重复消息和有序处理消息。 信息标识技术不仅可以应用来标识消息，也可以标识一个路由项等。在d s d v 和a o d v 协议中， 每个距离矢量兜带有一个直接序列信息标识，以确定距离向量生成顺序，解决路由环路问题。 2 控制开销问题 路由开销时衡量多跳网络路由协议性能的重要指标。路由开销可以用单位时间内路由控 制消息的传输量来表示，它是网络拓扑结构变化率的函数。a dh o e 网络路由协议的设计过程 就是一个路由优化的过程，即在满足消息传输要求的基础上尽量减少路由开销，从而提高网 络的吞吐量。路由协议设计和优化的基本思想如下： 减少路由协议的开销，从而提高网络的有效吞吐量。 提高路由消息的利用效率，从有限的信息中，发现更多有价值的网络状态信息。 采用自适应设计方法，根据网络状态，动态调整路由协议及参数。 解决路由控制开销问题，有以下几种典型方法。 ( 1 ) 多点中继技术 在许多路由协议中，都显示地或隐式地采用了洪泛技术。提高洪泛效率，减少洪泛开 销，是优化路由协议的有效途径。按照网络最小生成树进行有选择的广播是洪泛的最 优方式，这样可以避免广播冲突和重复广播。要计算网络最小生成树，就必须要知道 整个网络的拓扑结构，而这在许多情况下是不现实的。但是，通过局部链路状态信息 交换可获得局部区域的网络拓扑结构，进而可以计算出局部生成树。沿着局部生成树 进行消息广播，可以用最小的网络开销将消息传送到局部区域的边界节点。链路状态 消息不断地按局部生成树向外扩散，最终扩散到全网，其路由开销比纯洪泛方式小。 一6 一 堕塞唑皇盔堂堕主翌壅竺兰堡垒茎笙三童垒! 坚2 1 塑堑堕虫堡堡墨茎丝堂坌堑 当局部区域被限制为两跳时，该技术被称为“多点中继技术，o l s r 路由即使使用了该 方法对链路信息的洪泛进行优化。 ( 2 ) 多范围技术 在大规模的网络中，受传播延时和节点移动性的影响，距离节点越远的链路转台信息 准确性越差，对路由计算的意义越小。因此，路由协议应当区别对待不同距离的链路 状态信息。多范围的含义是：针对某个节点而言，距离自己越远的节点，了解到关于 它的路由信息应当越模糊；相反，距离自己越近的节点，了解到的关于它的路由信息 应当越精确。这样可以达到降低路由协议开销的目的。f s r 协议通过模仿鱼眼“对距 离越近的物体看得越清楚的生理特性，对不同距离范围内的链路状态信息采用了不 同的更新频率，在g s r 的基础上进一步降低了路由协议的控制开销。 ( 3 ) 增量消息技术 节点向邻居节点报告拓扑信息、路由表信息、邻接关系等信息时，只报告对应信息时， 只报告对应信息的变化部分，而不是每次都将全部信息报告给邻居节点。这样。可 以减少控制消息的长度，从而降低开销。这种技术在d s d v 协议上得到了广泛的应用。 3 对网络动态性的适应问题 网络拓扑的动态性是a dh o c 网络和固定i n t e r n e t 的一个重要区别。网络的高度动态性必 将导致路由失败。在网络动态变化十分剧烈的时候，路由只能通过洪泛来实现。但是，在网 络的动态变化不太剧烈的情况下，通常有三种方法对实效路由进行维护：备份路由、路由实 效点通知源节点重新计算路由和在路由实效节点进行局部路由修复。 在i n t e r n e t 路由协议中，当节点间的链路发生变化时，其设计思想是以最快的速度将变 化通知到网络中的其他节点，并重新调整和计算最短路由。链路状态变化越快，由此引起的 路由开销就越大。在多跳网络中，更适应采用局部修复技术，将这种变化限制在局部区域内。 不同的路由协议，所采用的具体技术也不同。在a b r 中，当源节点到目的节点的路径发 生中断时，整个路径并不需要立即重新建立，而是试图从中断节点开始，查找合适的路径， 修复断开的链路。在t o r a 路由协议中，链路的通断，会引起局部节点高度的调整，从而将变 化约束在一个小的区域内。局部链路修复技术实际上是放弃了对最优路径的追求，而是更注 重在保持路由连通性的前提下，减少路由开销，缩短路由恢复时间。 南京邮电大学硕士研究生学位论文第二章a dh o c 网络路由协议及其性能分析 2 2a dh o c 网络路由协议的分类 2 2 1 先验式路由协议 先应式路由协议又被称为表驱动( t a b l e - - d r i v e n ) 路由协议，它通过连续的检测链路质 量，时刻维护准确的网络拓扑和路由信息。其优点是发送数据包时可以立即得到正确的路由。 它的缺点是路由开销太大。大部分先应式路由协议都是从传统的链路状态路由中演变而来的。 1 ) 目的序号距离矢量协议d s d v ( d e s t i n a t i o ns e q u e n c ed i s t a n c e - - v e c t o r ) d s d v 路由协议是一种距离矢量路由协议，利用目的节点序列好来解决d b f 算法的路由环 路和无穷计数问题。 在d s d v 中，每个节点保存一张路由表，路由表维护本节点到网络内部所有可达的目的节 点的路由。路由条目中保存目的节点的序列号，用于区别新旧路由。为维护路由表，节点周 期性的广播路由更新消息。收到路由更新消息后，节点比较其中的目的节点序列号和自己保 存的同一目的节点的序列号，如果前者大，就更新自己的路由；如果路由序列号相同，则选 择具有较少跳数的路由。路由更新消息要延迟一段时间发送，以防止路由表波动。 2 ) 鱼眼状态路由协议( f i s h e y es t a t er o u t i n g ) “鱼眼 技术是k l e i nr o c k 和s t e v e n s 提出来的，这种技术可以用来减少表示图形图像 的数据。鱼眼能清晰地捕捉焦点附近的像素，但清晰度随着离焦点的距离增大而降低，“鱼眼” 技术在路由中用来维护精确的距离和路由质量信息，但也会随着距离的变大而逐渐不精确。 鱼眼状态路由f s r 是一个先应式表驱动的路由协议，在功能上与链路状态路由相似。它 使用了鱼眼技术，在不同鱼眼域中的节点以不同的频率( 这个频率是由节点距离决定的) 只向 邻居节点广播链路更新信息，这能够大大减少链路状态更新信息，从而降低了泛洪的开销。 3 ) 优化链路状态路由协议o l s r ( o p t i m i z e dl i n kr o u t i n gp r o t o c 0 1 ) o l s r 9 主要采用两种控制消息分组，h e l l o 分组和t c ( t o p o l o g y c o n t r 0 1 ) 分组。这两种 控制消息分组中都包含序列号，通过对序列号的比较，节点可以很容易的分辨出控制消息分 组是否为最新的，而不会受到分组重传的影响。h e l l o 消息用于建立一个节点的邻居表，报 文中可以包括邻居节点的地址以及本节点到邻居节点的延迟或开销，o l s r 采用周期性地广播 h e l l o 分组来侦听邻居节点的状态，节点之间无线链路状态包括：非对称链路，对称链路， 一般链路和失效链路；邻居状态有：对称邻居、m p r 邻居和非邻居。h e l l o 分组只在一跳的范 围内广播，不能被转发。如图2 2 所示，在初始化阶段，当节点a 收到一个来自于邻居节点 b 的h e l l o 分组，a 将b 放入自己的邻居集中，并将到b 的链路标记为非对称状态，然后，在 一8 一 堕室塑皇奎兰堡主堑壅生兰垡笙奎 笙三童垒! 坚! ! 堕丝堕叟堡坚垄茎竺些坌堑 a 向b 发送h e l l o 分组时，在h e l l o 分组中就包含有b 是a 的非对称状态的邻居节点的信息， 当b 收到该h e l l o 分组时，b 就将在邻居集中将a 的状态更新为对称状态，同理，在b 再次 向a 发送h e l l o 分组时，h e l l o 分组中就包含了a 是b 的对称状态的邻居节点的信息，当a 收到该h e l l o 分组时，a 就在邻居集中将b 的状态更新为对称状态。h e l l o 分组同时也用于向 邻居节点通告本节点的多点中继节点( m u l t i p o i n tr e l a y s ) 的选择。所以在前面的邻居通告 完成之后，a 、b 节点再分别计算自己的m p r ，再在后面交互的h e l l o 分组中包含各自的m p r 信息。 + 一b a 日b 卜a _ 圆卜b 叶a 上 瓮称，上 删韵 上 耐釉 图2 2o l s r 路由的邻居发现 与h e l l o 消息相反，t c 分组必须被广播到全网。每个m p r 节点使用t c 控制消息声明链 路状态信息，而且只需声明它与m p rs e l e c t o r ( m s ) 之间的链路状态信息，而不是声明它与所 有一跳邻居节点的链路状态信息。通过这种方式，压缩了t c 控制分组的长度。每个节点根据 收到的t c 分组和自己的邻居信息来计算出网络的拓扑图。只有被选为m p r 的邻居节点才负责 转发t c 控制消息。为了使得全网的节点建立起一张完整的网络拓扑图，必须将包含网络拓扑 消息的t c 分组洪泛到全网。同时，考虑到无线链路带宽的局限性，又必须对广播分组数量进 行控制，o l s r 不再采用传统的链路状态路由协议中的方法( 每个节点的邻居节点无选择性地 转发t c 分组) ，而是在该节点的邻居节点中选择一部分节点来转发t c 分组，这些被选中的节 点称为多点中继站( m p r ) 。每个节点在自己的跳邻居节点之中选择一部分节点作为多点中继 站m p r 。节点在从自己的一跳邻居节点中选择m p r 时，必须选择和自己存在双向对称链路的 节点。计算原则是：节点与m p r 之间必须是双向对称链路，节点所发送的分组通过m p r 的中 继，能够到达所有对称的两跳邻居节点，如果能够满足这一点，那么m p r 就能有效地进行t c 分组的转发，同时，应该使m p r 的数量尽量的少。采用这种对称链路策略形成的路由避免了 数据分组在单向链路上传送时如何获得分组接收确认的问题。如图2 3 所示，节点1 周期性 地发送t c 分组，在t c 分组中就包含了将该节点1 选为m p r 的邻居节点地址( 称为m p r s e l e c t o r ) ，当节点2 和节点3 收到节点l 发送的t c 分组时，节点2 和节点3 首先判断自己 是不是属于节点1 的m p r ，节点2 和节点3 都发现自己属于节点1 的m p r ，它们再根据t c 分组 一9 一 南京邮电大学硕士研究生学位论文 第二章a dh o c 网络路r h 协议及其性能分析 中的序列号来判断该t c 分组是否是最新的，如果是，则转发该t c 分组，否则丢弃该分组； 而其他的两个邻居节点都发现自己不属于节点l 的m p r ，则不转发该t c 分组。 邻居节点 o 两跳节点 图2 3 节点的两跳邻居节点和m p r 0 l s r 利用m p r 节点进行选择性洪泛，有效地减少了控制信息洪泛的规模。所以使用m p r 节点是为了减少网络中控制信息的转发而采用的一种优化方法，如图2 4 所示，采用m p r 机 制对路由控制消息进行选择性的洪泛可以有效地减少整个网络范围内的路由控制消息数量， 随着网络规模的扩大，节点数量的增加，节点密度的增加，采用m p r 机制的优势会更加明显。 通过m p r 机制来控制t c 分组在网络中广播的规模，减少控制分组给网络带来的负荷，同时避 免形成广播风暴。 图2 4 无选择洪泛和选择洪泛 o l s r 协议中一个或多个控制消息被封装成数据分组利用u d p 的端口6 9 8 进行通信。 o l s r 通过这些控制消息获得了路由计算所需要的两个信息表：邻居表和拓扑表，每个节点 由自己的邻居表和t c 消息形成的拓扑表，可以完成对当前时刻网络拓扑结构的大致了解， 但是由于m p r 节点转发的t c 消息包含的不是所有一跳邻居信息，所以这样的了解可能是不 完整的。 0 l s r 路由协议与传统的链路状态路由协议最重要的区别在于m p r 节点的引入，m p r 机制 大幅度地降低了路由控制消息的洪泛规模，同时能够有效地将路由控制消息洪泛到全网。节 1 0 南京邮电大学硕上研究生学位论文第二章a dh o c 网络路由协议及其性能分析 点需要能通过它的m p r 到达所有的两跳邻居节点，如图2 5m p r 的计算步骤如下： 图2 5 节点m 的m p r 计算过程 第一步：开始节点的m p r 集合不包含任何节点，开始计算m p r ； 第二步：从节点的邻居节点中选择n w i l l i n g n e s s ( 表示节点为其他节点转发分组的愿意 程度) 等于w i l l _ a l w a y s 的节点，再对这些节点分别计算其连接度( 连接度是指节点的邻居 节点以对称链路连接的两跳邻居节点个数如果一个节点的w i l l i n g n e s s 是w i l l _ n e v e r ，任 何节点都不会选择它作为m p r 。相反，如果一个节点的w i l l i n g n e s s 是w i l l _ a l w a y s ，那它 必然会被选为m p r 。在缺省状态，节点的w i l l i n g n e s s 为w i l l _ d e f a u l t ；) ，在邻居节点中 选择这样的节点二一本节点必须通过它们才能到达某些两跳邻居节点，将它们加入m p r ， 同时将能够通过m p r 到达的两跳邻居节点从两跳邻居节点集中移除； 第三步：如果此时在两跳邻居节点集中还存在没有被m p r 覆盖的节点，那么重复以下步骤， 使得所有的两跳邻居节点都能通过m p r 到达： ( a ) 对不是m p r 的每个邻居节点分别计算它能够覆盖的两跳邻居节点集中没有被m p r 覆盖的 节点个数，称为覆盖度。 ( b ) 选择具有最高n _ w i l l i n g n e s s 而且覆盖度最大的节点，如果有多个满足条件的节点，选 择连接度最高的节点，将节点加入m p r ，然后将这些能够通过m p r 到达的两跳邻居节点从两 跳邻居节点集中移除。如图2 5 所示，按照m p r 的计算步骤： 首先选择这样的节点本节点必须通过它们才能到达某些两跳邻居节点，节点4 入选， 将节点4 连接的两跳邻居节点从两跳邻居节点集中移除； 显然，此时两跳邻居节点集中还有没有被m p r 覆盖的节点，于是对不是m p r 的节点节 点1 ，节点2 ，节点3 ，节点5 ，节点6 分别计算覆盖度，具有最大覆盖度的是节点3 和节 点6 ，覆盖度均为2 ，两个节点的连接度也都为2 ，所以将节点3 和节点6 同时加入m p r ； 一1 1 一 南京邮电大学硕士矽f e 生学位论文 第二苹a df l o e 网络路由协议及其性能分析 此时两跳邻居节点集中的节点均被m p r 覆盖，m p r 的选举过程完成；节点l ，节点3 ，节点 6 成为节点m 的m p r ；选择m p r 的最终目的在于使得节点通过m p r 能够到达所有的两跳邻居 节点，上述步骤确保了所有的两跳邻居节点都能被m p r 所覆盖。 4 ) w r p 无线路由协议算法 w r p 是一个较早的自组网先验式路由协议。在w r p 中，节点保存的信息表、路由表、链 路开销表、分组重传列表4 个部分。节点通过获得邻节点的状态变化信息来维护自己的信息 表，并通知邻节点；收到来自邻节点的信息后，要更改保存的信息表。节点在一段时间内没 收到邻节点发送的任何分组，就认为和该节点间的链路失败。新节点加入网络系统时，如果 某个节点收到了新节点的h e l l o 分组，则把新节点信息填入信息表中，并且把它自己保存的 信息发送给新节点。w r p 通过记录到目的节点的距离信息和先驱节点信息，解决了路由环路 问题。所谓先驱节点是指在所选的到目的节点的路由上，目的节点的前一个节点，也称为“倒 数第二跳”节点。w r p 是一种链路状态算法，它对链路失败的情况有较好的适应性。 5 ) g s r 一全局链路状态路由算法 g s r 算法与d s d v 类似，但节点收到请求信息后，在转发信息包之前将自己的地址填写请 求信息数据包中。如果发现已经存在自己的地址，就把该数据包丢弃，避免了信息洪泛。每 个节点维护整个网络的拓扑信息，并在本地优化路由信息。拓扑表内容包括链路状态信息、 下一跳信息和信息时间。在移动性较强并且带宽有限的情况下，g s r 的应用效果较d s d v 和传 统的链路状态算法更好。 2 2 2 反应式路由协议 反应式路由协议，又称为按需路由协议，是一种当需要时才查找路由的路由选择方式。 节点不需要维护及时准确的路由信息，当需要发送数据时才发起路由查找过程。为了提高效 率，节点可以找到的路由保存在缓存中供后续发送使用。因此，拓扑结构和路由表内容是按 需建立的，它可能仅仅是整个网络拓扑结构信息的一部分。它的优点是不需要周期性的路由 信息广播，节省了一定的网络资源。缺点是发送数据分组时，如果没有去往目的节点的路由， 数据分组需要等待因路由发现而引起时延。现有按需路由协议分为a o d v 、d s r 、t o r a 、a b r 和 s s r 。目前提出的路由协议大多采用按需路由方式。下面就详细介绍一下上面提到的几种按需 路由协议。 1 ) a o d v ( a dh o eo nd 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 dh o co n - d e m a n dd i s t a n c ev e c t o ra l g o r i t h m ) 是在d s d v 协议基础上改进而来的， 采用与d s r 协议类似的按需路由机制，因此可以看作是二者的结合。在a o d v 中，路由表信息 一1 2 南京邮电大学硕士研究生学位论文第二章a dh o c 网络路由协议及其性能分析 是依赖于中间节点来建立和维护的，即类似于d s d v 中的路由表，路由报文中不带有源路由的 信息。采用超时删除路由的机制，并期性的更新。通过使用目的节点序列号的方式，有效的 防止了环路的产生和过时路由信息。 a o d v 的路由发现也采用洪泛的方式，由反向路由的建立和前向路由的建立两部分组成。 当源节点发出路由请求报文后，中间节点接收并转发的同时，记录其中的上游节点地址、请 求i d 等相关信息，以形成反向路由。同样，当目的节点收到请求报文后，采用类似的方式将 响应报文发给源节点，并在此过程中形成前向路由。 2 ) d s r ( d y n a m i cs o u r c er o u t i n g ) 路由协议 d s r 协议是一个典型的按需路由协议，也是最早采用按需路由思想的协议。节点需保留 存储节点所知的源路由的路由缓冲器。当新的路由被发现时，缓冲器内的条目随之更新。它 的最大特点是使用了源路由机制，每一个分组的头部都包含整条路由的信息。d s r 协议最大 的特点就是使用了源路由的路由机制，在分组的头部携带要经过的路由，路由器按照路由序 列来转发分组。d s r 协议包括两个过程：路由发现和路由维护。 路由发现：当一个节点要向目的节点发送数据，先查询路由缓冲器里是否有到目的节点 的路由，如果路由缓冲器中存在到达目的的路由，则利用这个路由发送数据；如果不存在， 则启动路由发现过程，这个过程使用泛洪。源节点广播路由请求分组，中间节点接收到这个 请求分组后，将检查自己是否有到目的节点的路由，如果有，则立即返回应答分组；如果没 有，先将自己的地址加到请求分组头部的路由序列中，并将这个分组继续向下面广播，若请 求分组头部的路由序列中含有自己的地址，则将这个请求分组丢弃，这样为了防止出现回环 路由。目的节点收到最先到达请求分组后，将按照请求分组头部的路由序列的顺序返回给源 节点一个应答分组，应答分组中也包含了这条路由所经历的节点地址。源节点收到这个应答 分组后就可以发送数据了。 路由维护：路由维护通过路由错误分组和确认分组来实现。当节点发送数据的时候发现 需要使用的邻接链路断开，它发送路由错误分组给这些断开路由的源节点，源节点收到分组 后，将失效路由从路由缓冲器中删除。沿途转发路由错误分组的节点也从自己的路由缓冲器 中删除包含该断开链路的所有路由。 3 ) t o r a ( t e m p o r a l l yo r d e r e dr o u t i n ga l g o r i t h m ) 临时序列路由算法 t o r a 协议用于移动性强，多节点转发的网络环境中。t o r a 协议是基于“逆向链路由协议， 能提供源节点到目的节点的多条路由，当拓扑发生变化时，它可以把控制信息限制在拓扑变 化点附近很小的范围内，从而降低开销。在t o r a 协议中，路由的最优性是次要的，为避免寻 找新路由的开销，经常会采用距离较长的路由。 一1 3 堕塞坚皇盔兰堡主堕窒竺堂竺堡奎笙三堡垒! 望竺! 塑竺堕虫堡坚垄茎丝堂坌堑 t o r a 协议的做法可以描述为水沿着管道下山到山脚的目的地。管道代表网络节点之间的 链路，管道的接口为节点，水代表流向目的节点的数据消息。和目的节点相比每一个节点都 有一定的高度，这个值由路由协议来计算。如果两个节点之间的管道阻塞，那么就把这个节 点的高度设置成比任何一个相邻节点的高度都要高，这样水就能倒流出来从而重新寻找新路 由。 4 ) a b r ( a s s o c i a b i l i t yb a s e dr o u t i n g ) 基于结合性的路由。 a b r ( a s s o c i a t i v i t y b a s e dr o u t i n g ) 协议定义了一个新的路由选择度量：联合稳定度， 即节点及其链路在时间和空间上的稳定程度。每个节点周期性地广播标志表明其存在，邻节 点收到标志后将路由稳定时间和路由信号强度作为路由选择的标准，每收到一次，相应节点 的稳定度就增加一点。稳定度值越高表示该节点移动越少，稳定度越低表示该节点移动性越 大。当节点移动引起链路中断时，联合稳定度将被重置。a b r 协议主要由三部分组成：路由 发现、路由重构和路由删除。a b r 协议通过节点间定期发送信标( b e a c o n ) 来标识节点的存在， 寻找移动自组网中生存期最长的路由是该算法最基本的设计目标。 5 ) 信号稳定性路由协议s s r ( s i g n a ls t a b i l i t yr o u t i n g ) 。 选择路由的标准是利用节点之间信号的强度和节点位置的稳定度。s s r 可分为两个相关 协议：动态路由d r