（计算机应用技术专业论文）无线ad+hoc网络中多径源路由协议的实现和性能评价.pdf

摘要 无线遥信技术彝诗簿枧列终技术的发展为无线移动a dh o e 阚终的产生奠定 了基础。而无线移动a dh o c 网络由于麒不需要集中式的网络管理和基础设施的 显著特点在近年来受至# 越来越多的关注，各裂，a dh o c 瓣络路出协议兹提出及樱 关的性能分析评价也成为学术界的研究热点。由于无线a dh o e 网络中带宽及能 曩有照的特性，使缛如倪平衡a dh o c 嬲络负载提赢网络路径有效性成为a dh o c 网络路由协议研究的主要目标。在众多a dh o c 网络协议中，种由卡内基梅隧 大学提出的被称为d s r ( 动态源路由) 的路由协议具有相对较好灼性能，本文中 所实现的m s r ( 多径源潞由) 虢怒以d s r 协议为基础的、通过运用多径概念来实现 上述目标的一幂中薪型无线h dh o e 网络路由协议。 本文的目标是在实际系统环境中实现m s r 协议并辩其的可行性进行初步的 验汪，所以区别于当前绝大多数研究所采用的仿真实验方法，本文的研究采用了 实验霖( t e s t - - b e d ) 的方法朝在实际酌l i n u x 操作系统上实现髂r 协议，然后 在实际的场景中进行实验和测盥，最后通过分析测量结果并和仿真结果相比较来 得出结论，飙箍基本上印证了鹣r 方法静可行褴。这种实验藤静方法掰褥到麓数 据较仿真方法更使人信服，而且也为仿舆方法的结论提供了有力的支持。 笑键词：a dh o c 网络 源路囊 d s r 7 m s r多径 路径搽溯 a b s t r a c t w j t hr e c e n t p e r f o r m a n c e a d v a n c e m e n t si n c o m p u t e r a n dw i r e l e s s c o m m u n i c a t i o n st e c h n o l o g i e s ，a d v a n c e dm o b i l ew i r e l e s sc o m p u t i n gi se x p e c t e dt os e e i n c r e a s i n g l yw i d e s p r e a d u s ea n d a p p l i c a t i o n ，a n dt h e a dh o cm o b i l ew i r e l e s s n e t w o r ki sr e c e i v i n gi n c r e a s i n ga t t e n t i o nf r o ma l ll i n e sd u et oi t sc h a r a c t e r sw i t h o u t n e t w o r ka d m i n i s t r a t i o na n di n f r a s t r u c t u r e v a r i o u sr o u t i n gp r o t o c o l st h a ta r et a i l o r e d t oa dh o cn e t w o r k sh a v eb e e n p u tu pi nr e c e n ty e a r sb yr e s e a r c h e r sa r o u n dt h ew o r l d ， a n dr e l a t e d a n a l y s e sa r eb e i n gd o n ef r o md i f f e r e n ta s p e c t s f o rt h e l i m i to ft h e b a n d w i d t ha n de n e r g yo ft h ea dh o cn e t w o r k ，h o wt ob a l a n c et h e p a y l o a da n d i m p r o v et h ev a l i d i t yo f t h er o u t i n gh a sb e c o m et h em a i nt a r g e t so ft h ee v a l u a t i n gt h e r o u t i n gp r o t o c o lp e r f o r m a n c e a m o n g a dh o c r o u t i n gp r o t o c o l s ，o n e n a m e d d s r ( d y n a m i cs o u r c er o u t i n g ) p r o p o s e db yc a r n e g i em e l l o nu n i v e r s i t yh a sab e t t e r p e r f o r m a n c et h a no t h e r s m s r ( m u l t i p a t hs o u r c er o u t i n g ) ，p r o p o s e di nt h i sp a p e r , i s b a s e do nd s ra n d u s i n gt h ec o n c e p t i o no fm u l t i - p a t ht og a i nt h et a r g e t sw ei n v o l v e d a b o v e w h i l et h et a r g e to ft h i sp a p e ri st oi m p l e m e n ta n dv a l i d a t et h ef e a s i b i l i t yo fm s r o nt h er e a ls y s t e m ，u n l i k em o s t l ys i m u l a t i o nm e t h o d s ，w eu s et e s t b e dt oe v a l u a t et h e p e r f o r m a n c eo f m s r f i r s t ，w ec o m p l e t e dt h em s r o nl i n u xo p e r a t i o ns y s t e m t h e n ， m s ri st e s t e da n dm e a s u r e di nar e a le n v i r o n m e n t a t l a s t ，w ea n a l y z e dt h er e s u l ta n d c o m p a r e i tw i t ht h er e s u l to fs i m u l a t i o na n d g e tt h ec o n c l u s i o nt h a tm s r i saf e a s i b l e p r o t o c o li na d h o cn e t w o r k a n dt h i st e s t - b e dm e t h o di sm o r e p e r s u a d a b l ea n dg i v e s as t r o n g l ys u p p o r tt ot h es i m u l a t i o n k e y w o r d s ：a dh o cn e t w o r k s o u r c er o u t i n g d s rm s r m u l t i p a t h p a t hp r o b i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得盘壅盘璺或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：方嘲 签字f | 期：聊工年肛月，厂f = 1 学位论文版权使用授权书 本学位论文作者完全了解鑫注盘鲎有关保留、使用学位论文的规定。 特授权：叁凄盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者虢亥嗣 导师签名：臻蝤 签字同期：) t 啦年肛月1 rr 签字日期：a 年，月，硐 第谭绪论 第一章绪论 1 1 无线网络的发展及研究现状 自从二_ 卜世纪七十年代出现以来，无线网络越来越受到计算机产业的重卒见。 茏英楚最近卡年阉，国予无线瓣络与移动接拳糖结合，令其大受欢趣。当蘸存在 着两种移动无线网络：第一种是有基础设施( i n f r a s t r u c t u r e d ) 的网络，该网络由 若干移动管患稃毅稔之舞“萋菇”豹蒸穑设麓缝残，翻络中懿移动节森壹接与其 通讯半径之内的最近基站进行连接与通讯。当移动节点离开某基站的通讯范围 舔避入另一蘩站的逶谣范髫辩，逶过爨基菇与凝基蘩之阉匏转接( h a n d o f f ) ，渡 移动”箝点可以不受妨碍地继续进行网络通讯。第二类移动无线网络是无基础设施 豹，邋翥称为a dh o c 飘络。 骧萋无线技术懿送一步笈震，这爨a dh o c 丽终暖 其方便灵活的特点越来越受到人们的壤视，关于该网络上的路豳协议及其性能的 谖赞迄残为了当蘩麴一个疆突热点。 a dh o c 网络是- 9 十不需疆任何撼前给定的基础设施就能进行组网的网络形 式。凳了实魏翘络节点之闽瓣逶识，i e t f 豹m a n e t 小缝绘出了多耪磷数罔予绸 成移幼a dh o e 网络的路由协议，如d s r 、a o d v 、d s d v 和t o r a 等。当前已经 煮覆多人针剥这些捺议骰了大餐豹毪缝分辑黟磺究，魏j ，b r o c h 等 1 5 分撰了特定 移动和业务场景下d s d v 、d s r 、a o d v 和t o r a 四种协议在薏包率、路由信息 开销魏路径长度方嚣戆特性。r j o h a n s s o n 等 2 7 1 在一个扩展的场景中比较了三羊孛 协议在丢包率、路由开销、吞吐率和延迟方丽的特性。 此外，出于a dh o e 路出块议主要应用在以小电波组为能嫩来源的够动设麓 上，近来关于如何均衡网络上的负载，如何减少能量消耗等问题也逐步受到人们 豹关注。 1 2m s r 简介 通过对a dh o c 网络的动态源路由协议d s 燃行扩展，即在a dh o c 网络中嶷 现一种多径潞出方法，我翻褥翔一稀多径路由协议称为m s r ( m u l t i 。p a t hs o u r c e r o u t i n g ，多襁源路由) 。m s r 是以延迟作为路径规格的度量，遄过主动探测的方 式感知潞径静袄态，采溺蒂裰整静循环调度葬法，把数耩流量分摊在多条互辐独 立的路径上，从而达到充分利用a dh o c 网络资源、提高节点通讯质掇的目的的 a dh o c 翳络路蠡协媛。 第一章绪论 。2 多经路峦 路由麴鼹重要的功能就是为源节点与目的节点选择一个可用链赡以便最小 化网络延迟。多径机制试图通过将网络业务尽可能的分配到可用的网络资源上以 获缛墩大的网络吞吐攘。 1 2 ，1 。1 定义 多径路囱模垄为任意一对节点同f l 亨提供多祭可嗣的路径，并允许节点主梳选 择如何使用这些路径。多径路由算法为节点间提供多条路径，并确保发往其中任 意一条路径静数摇经囊该鼹校掰这鏊熬逮。多经路由嗣络是箕中韵舔盘嚣执行多 径路由算法的网络。 1 2 1 2 优点 平蕊蕊终受载，茂纯系统经戆，据离瓣终懿裂耀率：蔓三瓿对薅径豹霞蠲 权自主，它可以通过探测各路径的状况( 比如丢包率) 猜测网络的拥瓣程度，据 魏谖熬各臻经豹投重及缓蓦l 频疫，麸瓣在褥到鼹延迟戆霹列达到提裹瓣络列鼹攀 的目的。 t i t 降低巍予无线键路豹不稳定镁帮兹蛰不颧变熊蠢绘露络逶氮豢采教受嚣 影响：在a dh o c k 络中，由于节点的移动性。使得无线链路具有不稳定、拓扑 变化频繁鲍撼性，囊袋雳多经卷蓝予减少由于上述壤我爨遥残鹣铸簸镶误飙蠢提 高故障维护的能力。 改善艉壁澄糕瓣不均筑性：枣予移动设蛋多以，l 、型电池组为缝爨来源菠 能最有限，当某个节点上的能量过度消耗或耗尽届就会造成链路断路或拓扑变 讫，因此遥过使援多经垮网络受载分熬到多袈路径上，可以达到糖能爨消耗麸馨 条链路分散到多条链路上的目的。 。2 。 + 3 缺煮 乱序：乱序闻题虽不飚多径本身所特商的问题，但是使用多投机制有可 能会加剧乱序的问题。但是我们认为可以通过程分配效率和乱序程度之间作一个 折衷寐减少由于多径所带来的嚣l 序问题。 实现困难：由于a d h o c 络的移动佳和多径路由的特点，使得关于多经 路e h 的绝大多数性能评价都是在仿真环境中樽到的。因此，在实际的系统中实观 m s r 蒺有一定的难度，丽其毪麓分析也会由于受到实际实验环境、条件的限制m 黼 增加难度。 第一章绪论 3 课题鹜景稻论文i l j - c 终 3 ， 课题背景 本项目憨在出教育部科技司主持的现代远程教育凭线接入网络教育研究专 题项融的支持卜进行的。该项目的重点是研究在集中式无线接入教室、移动学习 和讨论式学习这三种无线接入方式下，各种网络学习系统的有效方式。 在讨沦式学习中，经常需爱在多个人之间进行交流或信息、数据共享，铡如 计算机文档( 如课件、文献或习题答案等) 的传送和课程内容的展示等。这时绷 建一个不需要进行布线，方便、侠蕤掰置不受场所限翩的临时a dh o c 瓣络是 个很好的方案。只要进行通信的双方在无线网卡信号裰盖范围之内就可姒直接进 行逶谲；当联方不在藏围之内翻，我们霹鞋通过一定的鼯由协议稠魇它们之间存 在的若干中间节点为麒进行数据的转发，从而使双方自够进行正常通信。 谣本文兹主要舔究内容就楚为讨论式学习捷侯霹络支跨，帮研究多个穆韵节 点组成的a dh o c 网络中的路由问题以达到提高网络中业务的传输质量和改善潮 络髓辘翡譬斡。 1 ，3 。2 论文的工住 通过对多径特性的分析并结合无线a dh o c 网络的特点给出了多径路幽 静可行程算法。 在实际的l i n u x 系统上实现基于a dh o c 网络源路由协议d s r 的多径源路 鑫协议m s r 。该协议疆延迟俸为路径簸格豹废慧，逶避主动搽溺静方式戆知潞径 的状态，采用带权重的循环调度算法，把数据流量分摊在多条互相独立的路径上， 麸两达蜀充分翻瘸a dh o e 网络资源、撵高繁赢逶谲覆爨敢叠懿。 利用开发的实验床，在实际场景中通过实验测餐对d s r * i i m s r 的协议性 琵送行了毙较。壤据获褥鹣嚣豢数蕹讨论了m s 鬏在实嚣系统上瓣霹行缓及萁参数 的优化选择，并通过将真实数据的分析结果与仿真分析结果进行对比说明t m s r 懿逶蠲巧境及蒺耱议拳荸牲，最篱褥窭戳下结砉 ：在中载瓣络孛，s r 餮议熬霞爨 不会增加网络的总体负载，并能在一定的程度上降低数据包的传输延遐。 1 4 论文结构 论文的第二二章介绍与本论文相关的背景知谈，对秃线移动a dh o c 网络进行 了综述，包括a d h o c 网络特点及其对鼹由协议豹一些要求，嗣对还介纠了髫魏 a dh o e 网络路由的研究现状。第三章阐述了我们提出的自适成多径源路由协议 第一，章绪论 m s r ，解释了握出m s r 静囊辊与鏊舔，莠飘源路奎、多径巍瓣期性霖测三令方 面对m s r 的机制进行详细的说明并翁重介绍了m s r 中涉及的关键算法，在该 章最艨麓要逡分绍了在仿宾环壤中m s r 协议掰髂瑗烈鹣性黢。接下来夔第嚣辈 中首先介绍了实验床( t e s t - - b e d ) 开发所使用的技术，然后阐述了实现m s r 中 谴蠲熬主要数据结稳，著在该牵兹最疆给出了m s r 系统中分缀接收嚣 发送粒基 本流程。第五章给出了在t e s t - - b e d 上测得的实验结果，并通过与d s r 进行对比， 绘出了m s r 的蛙麓分辑与评价。在最爱豹第六章中绘毖了在嬲终中载辩多径鼹 由具有一定优势的研究结论井指出了m s r 当前的不足与改进方向。 第二章a dt t o c 网络路由概述 第二奄a dh o c 网络路由概述 2 1a dh o c 网络的定义及其适用环境 2 。1 ，1 定义 a dh o c 网络是内若干无线移动节点组成的集合，这些节点可以动态的任意 移动，它们之闽我链接可爨隧避闽连续交让，盥阚终不拨赖于建设好的基础缎织 ( e s t a b l i s h e di n f r a s t r u c t u r e ) ，不存在集中式的网络管理。因此a dh o c 网络中不 存在躺定的鼹由器：艨有豹节点都是埘移动的，并且埘以动态地自由遴接；每个 节点都具备蹄由功能，负责发现并维护通往其它节点的路径。 2 ，2 运雳环境 a dh o c 网络以其鸯奏驰方便和灵活性，逐步受到人们的海辣，其适用的环 境如下： 紧急搜索救援 亍动； 人们希望快速交流信息的会议； 不适台居住地区约数据获取： 2 2a dh o c 路由的基本要求 由于a dh o c 网络应用于无线传输网络，因此在设计一个适用于a dh o c 网 络的路由协议时必须考虑良下躲凡点黉求： 链路的单向性：有可能仅仅因为物理因素对无线媒介的影响而导致一个 无线链路哭在个单穗方囱土是连逶瀚，双嚣茬不能赛魏双蠢避镪，困就设诗露凑 协议时有必要考虑单向链路的问题： 1 1 1 有效瓣控翻戆篷溃糕：在一黧黻枣电游缝荛熬羹寒源豹设备上绸豁手攀 计算机等，能熊消耗怒一个非常重要的问题，因此选用的路由协议应该做到最大 程度豹簿低协议垂隽开镑鞋节省能量； 平衡网络负载：考虑副能量消耗，路由协议威该分散负载以减少单个节 点上豹笺量大塞游耗，否裂交子能量糕尽两美簿豹节点哥憨弓 起据羚懿分裁，麓 时可能导致不可达路径的出现，因此协议可以考虑利用多径的特性来实现负载的 平囊； 第二章a dh o c 网络路由概述 安全经：当翦豹a dh o c 爨盘耱议善遮缺乏安全蛙，崮鼍二无线绥覆菲鬻荔 受攻击，凶此在物理层上可以通过使用编码或跳频、扩频等技术来避免拒绝服务 玫毒，蠢在黪基层上必须为嬲络逶谖：箨点提供燕密认诞寒逮受鼹麦欺骟； 按需特性：为了尽量减少路由协议自身所带来的开销，一个蹋由协议应 该更多熬镬蠲按震瓿划瑟不袋麓弱欺瞧播； 服务质量( q o s ) 要求：路由协议应该知道源与目的对之l 司的延迟和番 吐率，并必须操涯睦期有效，以便一令实对应爆程序糍够司纛工作； 2 3 现有几种a dh o c 路嬲翕绍 2 3 1a dh o c 路幽协议分类 i e t f 的m a n e t ( m o b i l ea d h o c n e t w o r k ) 工作组 2 1 提出了多种不同的路由 协议，这些魏、议怠髂羔分为紊驱费路囊按议鞠滚发起豹隧选驱动鼹由泌议两鞭。 在介蜊具体的路由协议之前，我们先来介绍一下这两种分类的特点。 23 、 。1 衰g l 动路由协议 裳驱动的鼹由协议试图维护网络中从各个节点到所寿其余i 点熬最新路幽 信息，所有路由信息保持一致。这类协议要求每个节点维护一个或多个路由信息 表，当网络括扑变化时，更新信息被传遍整个网络以维护一致的网络视图。这类 协议之间的不同之处在于：必需的路融相关表的数量不同，网络结构变化信息的 传攒方法不问。主要代表裔：d s d v ( 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 r o u t i n g ) 、c g s r ( c l u s t e r h e a dg a t e w a y s w i t c h r o u t i n g ) 和w r p ( t h e w i r el e s s r o u t i n gp r o t o c 0 1 ) 。 2 3 ，1 2 源发起的随选驱动路由协议 与表驱动路盘漭谈不嗣，滚发趁瓣淹选驱韵秘议灵骞当添节点需耍辩才开始 寻找路径。当源节点需要一条通往目的节点的路径时，它在网络中发起一次路径 发臻过程。当我蘩一条籍径嚣或者所露霹裁豹潞径都被检查遥后，路径发溪过程 结柬。路径经建立，它就被某个路豳维护程序所维护，直至目的节点无法经由 任俺鼹径囊达或者该骚径不器授需要。源发栽熬随选鹱动螫议靛饯襄v | 鸯议有： 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 rr o u t i n g ) 、d s r ( d y n a m i cs o u r c e r o u t i n g ) 、t o r a ( t e m p o r a l l y - o r d e r e dr o u t i n ga l g o r i t h m ) 、 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 ) 和s s r ( s i n g l es t a b i l i t yr o u t i n g ) 。 第二章a dh o e 网络路由概述 黼2 - 1a d h o c 踺枣谤议靛分类 2 3 2 鹫耪a dh o c 路由按议内寨余绍 强众多的a dh o c 网络路由协议中，我们选取了四个比较有代表饿并被广泛 使用的协议d s d v 、d s r 、a o d v 和r a 来徽一个筒单的概念经介缮。 1 ) 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 rr o u t i n g ) ：目的序列距离矢 量路由协议 1 3 】。它最在傣统b e l l m a n * f o r d 鼹内选择舞法静鏊稀t 改嶷发蘸蠢 l 来 的，娥个以路由表为基础的通讯协议。该协议要求缚一个移动节点必须存储 个路程l 表，其中记录了瑟寄与该节点霹能送行连接的节点帮鞭离( 搿数) 。鼹由 表内的每一条记录同时包含了个序列号，用于判断路径信息是否过时。该l 办议 要求每个繁点透过掰络定麓濑发送黍l 铃搔路翻信息来维护黎囱表静一羧注。溺 此，使用d s d v 协泌将产生大量的控制包在网络中传输。 2 ) d s r ( d y n a m i c s o u r c er o u t i n g ) ：动态滚藩交耱议 1 7 l 。每一个羧黄稳魏 包都携带一个要到达目的地所必经的节点的完整序列，即要求发送者知道到达目 戆节患豹完整路径，这个特瞧裁是源鼹蠹。d s r 凌浚藏莛采爱了这耪滚热枣黪 方法，将路饺信息真接记录程每一个包中。此协议由两个基础过程组成：( a ) 路 径发瑷过程( b ) 路经维护避程。箕中终经发蜣过程怒按霉的( o n d e m a n d ) ，朝 只有当需要菜个路径时才开始寻找路径。路径发现过糨是从源端以广播的方式来 魂态发现瑟黪经。路缎维护过程主要黪工俸是掇援路囊落悬寒通知各个节点整个 网络拓扑的变化让节点更新路径缓存。相较予d s d v 协议，其在网络上只有用 予路後笈瑗翻维护骚瓣戆很少量控到镪。 3 ) a o d v ( a d h o co n d e m a n dd i s t a n c ev e c t o o ：按需的距离矢黛路由协议 【6 3 。该协议毽爝td s r 中的按嚣路由发现和路由维护规割，又媸鉴了d s d v 中 第二章a dh o c 网络路由概述 逐跳路由和序列号的距离向量技术。在该协议中当个节点需要和另一个节点通 信时才以按需的方式建立路径。相较于d s r 使用节点的路由缓存来维护路径信 息，a o d v 使用了和d s d v 相同的传统路由表形式。同时它也使用了序列号机 制来防止环路和过时路径信息的出现。该协议使用定期的h e l l o 信息包来检测 其和邻居节点之i 词的链路状态并进行更新。因此，a o d v 虽然也使用了按需机 制但相较于d s r 增加了一些必须的h e l l o 控制包，但其控制包的总数量要大 大少于d s d v 协议的控制包数。 4 ) t o r a ：当时规则的路由算法 3 5 。它是通过当有链路发生改变时，相邻 节点所产生的控制消息被局限在改变发生处的局部的方法来减少协议在网络中 的负载。t o r a 完成了三个主要过程：( a ) 按需的路径生成过程( b ) 路径维方。 过程( c ) 消除路径过程。消除路径过程主要是消除不正确的路径，它是通过一 个用于检测网络划分的节点来进行初始化的。对于路径的维护，是通过定期在传 输方和接收方之间发送一个b e a c o n h e l l o 信息序列号来实现从一个节点到 其所有邻居的节点的可靠控制信息传送。 2 3 3 四种协议的特性比较 表2 - 1 是上面四种协议在满足a d h o e 路由协议期望特性上的个粗略比较。 表2 - 1 四种a dh o c 路由协议特性比较 肋议特性d s d vd s ra o d vt o r a 单向链路否是否是 功率意识否否否否 多径支持否是否否 安全性否否否可能 周期性广播是否是是 q o s 支持 否否否否 组播支持否否是否 2 34 研究现状 随着a dh o c 网络的进一步发展，关于其网络中所使用的路由协议的性能评 价也越来越受到关注。当前已经有很多人针对这些协议做了大量的性能分析和研 究。如j o s hb r o c h 。d a v i d a m a l t z 等人通过大量的仿真实验对四种a d h o c 网络 路由协议的性能进行了比较和分析【1 5 。这四种协议是：d s d v 、t o r a 、d s r 和a o d v ，其中既包括t a b l e d r i v e n 的需要周期进行路由广播的协议，也有 第：章a d h o e 网络路由概述 o l l d e m a n d 翁依靠鼹鑫l 发褒过程豹蛰议。荬穗囊鲍a d h o e 琢境是5 0 今穆凌主规， 并在不同的移动频率和移动速度下对上述四种协议进行比较。他们得出的结沦 是：每一种协议都可以在菜些情况下工作缀缀好，而在是一些情况下煮各自的缺 陷。“d s d v 的性能很规律：当节点的移动频率低且速度慢时，d s d v 几乎成功 传送了赝有蜒数据包：嚣当节点豹穆动频率亵速度增大时，d s d v 按议不毙汇聚。 t o r a 从路由开销方面来讲是实验的各种协议中最差的，但是当数据源为1 0 到 2 0 个( 邸嘲缀处于轻载状态) 对，t o r a 也成功传送了9 0 阻上的数据包。当 数据源增i j h - n3 0 个( 即网络处于重载状态) 簸，网络无法应付路南协议所带来 的通讯量开锬，这时脊很大比例的数据包被丢彝。尽管d s r 因使用源路由耐增 加了跆由协议开销的字节数，但是它仍然在实验中所尝试的各种移动颓率利移动 速度场景中具有非常好的性熊。a o d v 在各平中移动频率和移动速度场最中的性 能与d s r 几乎一样好，同时又实现了降低路由字节开销的目标，但麓它要求发 送大攫的路由信息包，所以当节点移动频繁快速时，a o d v 实际上比d s r 招致 了更多的踌由开销。” 1 5 】。运说明了每一种协议都可以在某些情况下工作得很 好，而在另些情况下有各自的缺陷。但是总体来说，d s r 舆有相对优秀的性 能。因此这也楚我们选择d s r 协议傩为a dh o e 路由协议的研究切入点的原因之 一1 。 髓着研究的迸一步深入，久们已经不满鬣予仅仅使用傍囊的手段对各种a d h o c 网络路由协议进行性能分析和评价。有越米越多的基于不同操作系统平台的 实验寐被开发出来。由于在众多协议中竣d s r 和a o d v 协议的性能袋凝最好， 因此大多数的实验床的开发都是针对这两种协议进行的。当前，国际上开发比较 戒熬翁实验臻有c m u 在f r e e b s d 2 ，2 7 操作系统上实凌的d s r 协议实验靡，瀵 大利丑e 的昆士兰州大学的a l e xs o n g 在l i n u x 上开发的d s r 协议实验床以及美国 国家标准局在l i n u x 系统上并发a o d v 诲议豹实验床等。本文中所完袋的m s r 实验床是以本课题组自己开发d s r 实验床为切入点，在l i n u x 操作系统上开发 稻完成戆。 第三辩多径路韵协议( m s r ) 研究 鸶三章够径源路由协议( m s r ) 研究 慰然关f 有线网络上的多径研究女n 2 8 1 已经有很多，但是a dh o c 网络拓扑的 动态变化使鬻有线网络中的多径技术不能煮接应用到a dh o e 网络中。 2 0 a 酋 次提出了将多径的思想应用予a dh o c 网络的m s r 协议，并使用仿真手段列该 协议进行了饿能的分析和评价。区莉于 4 2 】f 4 3 l 的彷囊方法，本文使溺的是在实 际l i n u x 系统上建立实验床( t e s t - - b e d ) 的方法来对该m s r 进行性能评价和分 析。戳诧，在本章中主要锌对m s r 实验床实糯过程中所涉及懿主要思想秘舅法 进行洋细的阐述。 3 1 问题的提出 由于无线a dh o c 网络带宽受限，相较于容易造成路径振荡的单径路由协议， 多径蘧疰 搀议杰充分翻蠲嗣络燮源、捷裹节患遵适矮璧等方亵具有更大豹忧势。 同时，d s r 的源路由特性也降低了多径路由实现的复杂性。 3 1 a dh o c 网络单径路由的缺陷 a d h o c 无线移动瓣终中豹爨塞憨建攘当鸯限；势越，嚣i n t e r n e t 一撵，在缝 路上以及在路由器处的拥塞鼹造成a d h o c 网络中大延迟的主溪原因。所以，在 a d h o c 弼终中，宠分铡臻网终荣宽l 三乏及避开翱塞链鼹鞠掇塞鼹凌器戴疆为重要。 在a dh o c 网络中使用单径路由协议，不但不能谯轻载时充分利用资源，而 且当嘲络发生拥塞或卷穗路酝舞彝也不能缀好地重瑟选择台逶路径。这是因为髫 的节点相同的数据包全部都从闻一条路径上发送，当巢条链路拥塞或者断开时， 通过该键路发送鼹所蠢数据都必须盘鞭豹路经发送，蹶造成了嬲终的不稳定，鼯 且在移动网络中也相潞费时。 3 2 多径路壶麓够秀a dh o c 蕊终提 慧更旒酌性琵 在a dh o c 网络中，由予套个节点部具有路虫功黪，因两从任翅一令溪节点 到目的节点的路径通常会有多条。如果能够同时使用多条相互独立的路径，则节 点对之闯的实际带宽农阚终辍载丑寸等予各条路径的豢宽帮。这撵裁充分剥弱了劂 络资源，改善了通讯性能。 d s r 是静态( i # 状态依赖) 路融，它使用的是最短路原则。当我们加入路 径探测功能后则成为动态( 状态依赖) 路由，可以对网络状态做出反成。单径的 第i 肇多径路由协议( m s r ) 研究 动态鼹由易使稻络产生震荡，比魏以缓路拥塞菠搏为鼹出度爨：当菜祭链路发生 拥塞时，各个源节点探测到邀一隋况后都绕开该链路，于是该链路从过载变为空 载；继丽各个源节点搽测到滚链路菲卷空阂，于是不约嚣同都选择该链路，该链 路又从空载变为过载。多径的动态路由探测到某条链路的状态改变时，并不撼全 部遗躐量都穆进或穆出该链嬷，丽是通过增减路径的投重来转移部分通讯量。通 过这样的逐渐蛹整，使网络的通讯趋于平衡潞免了网络震荡。 此外，出于a d h o c 路由协议主要应用在以小电滟组为能爨来源黥移动设罄 上，旦网络中某一个节点由于能璧耗尽而关闭就会对整个网络造成很坏的影 昀。灏在使用最短路域最小延迟为路径选择机制的路幽协议中，某些：宵点由于需 要支持镁多条路径( 如较高的转发负载) 使褥这些节点持续消耗能囊，萁能量漓 耗量将明显的高予其他节点并很快被耗尽。在使用多径之后，我们将原本集中在 一一条路径上的负载分黼到了几条不同的路径上，减少了该路径上中闻蒂点的能鬟| = 消耗，从而降低了由于能量消耗殆尽母致的网络分割戚拓扑变化发生的概率。 然两，多径路宙也有缺点：它赡于实现；要求歪大的路蠹信息存锫空闯；潞 由计算更复杂。但是d s r 自身的源路由特性降低了多径路由的实现难度，这将 在下节中邋行详述。 3 1 ，3 在a dh o c 嬲终d s r 携议抟基础上实现多径路巍的可行性 在a dh o c 无线网环境中，由于熄无线，所以当主机数量够多( 比如5 0 个， 这也蹙较实爝豹节点数量) 时，灌在的可焉鼹由稻对于有线阏褥言更多，豁繁隧 够有效地实现多径路由，则可以充分利用网络带宽。其次，在移动环境中，路径 静交纯毪强，鲡采畿够溺薅後掰多条鼹径磊不蹩在路霸错谖穰惑返露之懿仅仅集 中使用最优路径( 在d s r 中是指最短路径，即跳数最少的路径) ，则数据包尤奠 是无连接豹数摇毽到达鼙栎主橇麴置率藏可蔽霆稳定，旋磊疆麓逶撬袋羹。第三， 多径的使用可以使网络中每个节点所消耗的能量较为均衡以减少或避免由于禁 令节煮髭量_ i 霪菠游糕嚣给嚣终簧输造成危害麴绪凌袋黛。 由于d s r 采用源路由方法，属于基于源的( s o u r c e - - b a s e d ) 路由协议，源 主橇确定圭建知道它有瀑婆可敬至g 这謦褥主礁筑路径，可良蠡交撼铁中选箨合逶f l 冬 路径来发送数据包。这就使税d s r 上的多裰路由相对于在逐跳的( h o p - b y - h o p ) 路垂| 魏、议上豹多径路塞燮受麓攀，量免除了路径上冬节点为镖掩黠多经熬 一致认知而需要进行的额外通信和计算。 垂是d s r 本身豹俊秀蛙貔表瑗以及源鼹豢豹特级捷我蠢j 决定选择d s r 避行 扩展以便在a d h o c 网络中实现多径路由，并将扩展后的多径路由协议称为m s r ( m u l t i p a t hs o u r c er o u t i n g ，多经溪簿由) 。 第三颦多径蹄由协议( m s r ) 研究 3 。2d s r 奔缓 为了要好麴摇述m s r 鼹主要罂想；我翻营是筠零套缨一下d s r 协议规铡。 3 ，2 1d s r 协议撅述 为了将信息包发送至另主机，发送节点在信恳包的头部构造个源蹄径 ( s o u r c er o u t e ) ，它矮旁轹嘲偿惠氢发送至瓣熬苇点辨爨要经过熬各个孛阐节点 的地址。接着发送节点从它的无线网络接口中将信息德传送蕊源路径中指明的第 一个：疆点。当菜节点接收到该数据氢时，宅毙检查自己是否楚数据包瓣最终疆的 地，如果不撼，它就按照包头内的源路径将藏发送至下一跳。数据包只有在刘达 其最终銎豹地对，才会被递交给强数主扭豹网络层处理。 a dh o c 阅络中的每一个节点都必须维护一个路囱缓存( r o u t ec a c h e ，蒸中 缓存蕊它掰收集到熬鼹经。当源节点准鍪翔魁的节点发送信息包对，蓠先要瞧：营 路南缓存，如莱在路由缓存申我虱了通往目的节点酌路径，它就甭这条路径撩送 信息包。如果在缓存中找不剥通往目的节点的路经，源节点可以通过踌出发观协 议( r o u t ed i s c o v e r yp r o t o c 0 1 ) 来寻我路径。程等待路自发现宠成豹过程审，源节 点既可以继续处理其它的工作也可以与其它节点通讯。源节点可以缓存该信息 毽，簿漪赢黢蕊过程找掰路径之后霉将其发送撼去：源节点也可以丢弃该藩惠镪， 然后依靠高腰协议软件进行必要的羹传。路由缓存中的每一条路径都有一个生存 赣，当越过该薅滔鹾，稽应豹路径就被获缓存孛释除。 在节点使用某一条源路径的过程当中，节点要对该路径的正确性进行监控。 秘翔，磐粟源路经中瑟标骥瓣滚节点、莲憨节点、袋任一中麓节点移动凄了其上 一跳绒下一跳节点的无线传播半径，该源路径就不能继续被用来向目的：符点发送 痞总毽。霜撵，当瀛鼹径上靛任露一个繁熹凑瑗藏障葳关霹时，该嚣潞径遣不畿 再继续使用。这种对路径正确性的监控称为路由维护( r o u t em a i n t e n a n c e ) 。当路 塞黎护搽溅剃正在镬爝孛嚣赡径窭褒勰题对，嬉峦发现过程裁可憨蔽窟凄，戳发 现新的正确路径。 3 2 2d s rj 生a dh o c 丽络中的慌点 襁对于传统薅巍穗谨，舞骞线潮孛夫囊镁爱戆鼹褰矢羹协议蠢璇鼹菰态癸 议，d s r 在a d h o c 网络环蟪中具有许多优势。首先，d s r 不使用周期性的路由 广溪，降 鑫了薅丽终鬻宽戆颧努开链，燕冀楚在瓣终中翡繁点浚鸯显蓉穆裁辩。 这悬因为在a d h o c 网络环境中不可能存在固定的路由配置，所有的通讯都只能 逶道广撩方式进嚣，嚣鞋嗣麓缝遗路嶷广播将在赘蠢消耗方蕊躲c p u 占趸方蘸 第三章多柽鼹由秘议( m s r ) 麟究 绘a dh o e 阚络带来过多豹不必要负掇。周对，因为节点既不需要发送也不需爱 接收路由广撩，从而减少了移动节点的电池电璧酶攒耗。 其次，蕊子距离矢量协议鄹链路状态协议的传统路虫协议可能会计算出一些 不熊在a dh o c 丽络中工作鹩蹒径：在无线环境中，一对主视可能在福辩筑两个 方内上穆输效果不样，因为在遮两个主机周围可能存在不同的传播模式 ( p r o p a g a t i o np a t t e r n ) 或干虢模式( i n t e r f e r e n c ep a t t e r n ) 。蕊辩距离矢黧谚议，尽 管主枫a 能够收到主机b 发出的路出一告( r o u t i n g a d v e r t i s e m e n t ) ，但是从a 向 b 传送筋信患色帮有可髓无法弼达b 。尽管当m a c 艨耱议熊够骰豳船藏豹像 歪 时d s r 也会使用双向传输，但d s r 不要求主机之间的传输必须是双向的。 矮后，倭绞路交协议不怒镑对a dh o c 霞络中存在懿囊态拓癸变纯爵设诗戆。 在传统有线网络中，路由器之间的链路会偶尔断开( g od o w n ) 或恢复( c o m e u p ) ， 链鼹栈挽( c o s t ) 有瓣毽会瓣攘塞甄变讫，毽是鼹崮嚣是不会裂楚移动鼹。在移 动节点作为路由器的坏境中，传统路融协议尤其是躐离矢量婚由协议，在网络辐 势结携动态变诧之后再商赫翦稳定路径汇黎静过程可簸会设缓漫。禳较甜言d s r 协议能够迅遵适应节点移动借带来的拓扑变化，而且在没有节点移动情况下不增 嚣鬏癸靛蘸瞧开镑。 3 2 3d s r 对于不嗣移动速度麴遭应性 总的说米，在无线移动网络中，当节点移劫得非常迅速频繁时，任何路由协 议掰憩采蘧的楚爨繁酶魏燕姆鼗据包鞋洪泛的方式焱遮全瓣，鞋麓移动带点可竣 撞到数据包的大量拷贝之一。另一方面，当节点移动逮度很慢或者移动频率很低 霹，露为蓬盘僖惠没蒋发生变侥，掰塔最理憋蕊实魏蓬无薅寝开锾。d s r ( 黎态 源路由协议，d y n a m i cs o u r c er o u t i n g ) 以路由请求的发起频率为驱动，在上进两 静锩况之间趣庆调整。如采聪菜个快速移凄筑节点有逶透露求，刚援结鑫协议将 以洪泛方式向整个网络发送路由请对之，一旦找到目标节点并返回了路由应答，就 立攀发送数据逸。郡塑封该抉速移动繁点无遴谖嚣袋的苇点公蕾銎熬泛秘路豳谴 求占用了一部分可用网络带宽，但是它们的路径不会髓影响。同样，肖节点移动 遴凄减馒麓，路径失效静频率会簿低，路垄开镑瞧随饕鼹虫发现的发起次数酌减 少而降低。 3 3 i f l s r 的生要愚想 m s r ( m u l t i p a t hs o u r c e r o u t i n g ，多径添潞由) 氍延迟俸持潞径瓣格静寝爨， 通过主动探测的方式感知路径的状态，采用带权重的循环调度算法，把数据流量 第三：鬻多径踌由协议( m s r ) 研究 分捧在多祭鱼攘罄窥蕊臻经上，簸_ | l l ；达型充分蕊| 爨a dh o c 劂终资繇、握齑涉点 通讯质量的蚓的。该协议的主要思想包含：茹径、源路由和主动探测。 3 ，3 ， 多程路由 雾径嫠穗摸鍪为任褰一慰节熹嗣时提供雾条酉爝鳃潞径。劳竞教：源节点邀搀 如何使嗣这魉路径。多径路由算法为节点间撼供多条路径，并确保发往其中条 爨径麓鼗搽经寤该爨径窭| 这翅静熟。多径路囊网络载楚嬲终中鼹垄嚣执行多径鼹 由算法的网络。 关子多衽豹甓点+ 我粕融经在节3 1 ，2 中骰了洋纲的贪缨崔这里就不再重复。 当前，关于a dh o c 网络中多径的研究有很多。黼值得说明的一点是，不同 予f l 中辑提臻匏只谯主路经失黢对才选择蚕髑路径瓣多经方式，我们掰提出 多径链同时使用多祭路径来谶行通讯。 3 3 2 漂路交 每一个数传输麴趣都携带个要剿达弱弱爨要必经豹节点鹣完熬的穿列，期 要求发送者知道到达舀的节点的完撼的路径，这个特性就是灏路由。 源路幽的忧点主要是麓单，易予实现，避免了中间节点的复杂控制，不存在 路径附循环简题。在源节点就可对业务选用辩路径进行完全掇制，这样穰容翁实 现负载平籀，同时也避免了邵路的出现。缺点是踺由信息都记录在数据包中，造 成了较大的通讯开锖，尤其鼹瓣于较大规模的嚼络雯为踞显，筒既冀褥扩震褴要 受到定的嫩制。 3 3 3o n - - d e m a n d 路由 o n - - d e m a n d 路瞄只有褒需要路强对方避彳亍罨径，不需餮褥期性她迸行蹁海 广播及路虫信息交换，因面大大降低了路由黝开销；缺点是反应时间较漫，信息 更新不及时。与之糯对静基予表稽的路由，海于路径被使精之前就爵经诗算好， 所以发映时间短。假是最近的研究【l o 】f 1 6 1 7 淡明如果充分有效地利用踌由缓撵 ( c a c h e ) ，那么o n d e m a n d 潞由在a dh o c 蹰络中可l ；i 得巍很离躬往麓。 3 ；3 4 提交m s r 鼢动撬 m s r 通过以上三者豹结念来充分利用蚤强的优点 o n - - d e m a n d 特性降低了 多裰的通信和计算歼销：