（计算机科学与技术专业论文）移动自组网络中多路径路由技术研究.pdf

吲防科学技术大学研究生院学位论文 摘要 移动自主网络( m a n e t ) 是由移动结点通过分布式协议自组织起来的一种无线网络。 对于一些没有固定基础设施、没有有线网络和管理中心的地方，m a n e t 可能是唯一可选 的通信工具。它具有部署方便、灵活的特点，具有诱人的应用前景。然而移动性容易导致 拓扑改变，可能中断现有的路径，单路径路由算法很难快速地适应拓扑改变、有效地发现 和维护路径。基于m a n e t 的平面结构在源和目的之间可存在多条路径，人们提出了多路 径路由技术。但是已有的多路径技术还存在明显不足：1 ) 已有多路径路由协议，主要研 究其容错性，流量主要分布在主路径中，它仅在主路径失效时，才将数据流切换到备用路 径中去，不能适应应用对吞吐率和负载平衡的要求；2 ) 使用平面结构，处理动态拓扑改 变的能力差；3 ) 平面式结构在结点数目增多时的多路径的路由开销增大、可扩展性差。 论文在分析m a n e t 网络特性及已有算法的基础上，应用跨层设计思想，集中研究了 m a n e t 中多路径路由的几个关键技术，包括多路径路由的可扩展性、多路径传输的可靠 性及多路径动态拓扑的自适应性等问题等。论文主要工作是： 1 ) 可扩展的多路径路由算法研究 平面式结构的m a n e t 在结点数目增多时的路由开销增加很快，可扩展性较差。论文 引进分簇的方法来提高网络的可扩展性。一方面利用基于簇的层次结构动态处理网络拓扑 变化，减少路由管理开销和路由维护的代价：另一方面利用多路径并发传输增大了吞吐率， 可以实现拥塞避免和负载平衡，优化网络带宽的使用、提高共享信道的利用率。 一c b m r p 算法一一种基于簇的多路径算法 算法的基本思想是采用单层簇结构来处理网络拓扑变化，采用分布式推进、逐段查找 的方式进行路径查找。该算法的优点是分簇结构简单，部署方便，在规模较小的网络中采 用分布式逐段查找方式查找路径可以减少泛洪时引起的通信开销。 一c m d s r 算法基于簇的动态源多路径路由算法 对于大规模较网络，c b m r p 采用逐段查找路径的方法存在路由查找开销大的问题， 且采用单层簇的简单结构存在可扩展性较差的问题。动态源路由( d s r ) 算法开销小，但它 在泛洪时会产生大量路由控制丌销。本文基于d s r 算法，将网络分成两级簇( 单元簇和中 心簇) 层次结构，以提高网络的可扩展性，同时将路由发现功能迁移到中心簇层来实现， 以防止类似d s r 路山发现过程的泛洪，实现路山查找丌销最小化。c m d s r 能够有效地处 理结点数量增大和结点密度增大的问题。此外，c m d s r 通过选择可靠的路径和发送端到 端的可靠性软保证的方法提高了可靠性。 2 ) 可靠性多路径路由算法研究 数据传输可靠性对多路径路由的性能具有重要的影响。论文集中研究了可靠性的两个 第1 页 国防科学技术大堂耐瓤生晦董俘堡苍 薹! 蓁l 墓誓量i i 三三耋薹! 耋? 萝i i i i 嬲k i ；i 笙i 手 ；蔬裂差差l ；v i 出珏i “i 霉疆挂l 薹￥羹羹i 蓥蛙萎自摹袁希j 。 塞妇簧嶙。膏袋誊氍l 。嚣 前! 口茧【投垂登嚣翼前；囊# ；i ，膏墓= 耍；i 器弱，篓菲i 轻f 霎白k ； ；! i 薹i蠢? i i 旷基；差雾。塑h 镑誊荔l q ，毽；囊* 里量薹一董；堑i 、羹；嘻y 曩曩l 丁互誊毒璺i ；碧蕾豫i a i 嚣强 r 靶复f 壅转? j i 州； 薹鐾望蓦已j g 曼雾 ! 望。嚣韩吕纠；墓些i i ：墨毳羹；气善，宇e 一重l 。 整i 坚；荔；荇：嚣【銎廿f 声；喜蛄l l 气! 。匕_ 誊斋；。羹鞋羹麓w 蒌曲乏茧裂霎墓i 嚣鞋薹浠弑d 旦；要琴鬻嚣 妻 臻萋i 参露q 裁鬟lo 基i p 爿露；。；誊鞠胡醛，兰轩；锭蛘 ：塑量营n 彗斟t 瑟；i 袁袁 i 奠；誊：囊；霞鎏。；堂嘉，蔷； 峰莛8 二j 照蠹霎。 l ! a n t a g ea n di n h e r e n t n a t u r eo fm a n e th a v el e dt oe x t e n s i v ea p p l i c a t i o n f o r e g r o u n d s m o b i l i t y o fw i r e l e s sn e t w o r k sn o d e sc a u s e s 矗e q u e n tt o p o l o g yc h a n g e sa n dm aybreak e x i s t i n gp a t h si nm a n e t u n i p a t hr o u t i n gp r o t o c o l sa r eh a r dt ok e e p u pw i t h the；equenttopologyc h a n g e s t h em u l t i p a t hr o u t i n gi sp r o p o s e da st h e r ee x i s tm u l t i p l ep a t h sb e t w e e nt hesourcea n dd e s t i n a t i o np a i ri nm a n e tp l a n es t r u c t u r e h o w e v e r , s o m el i m i t a ti o n sd oe xist：nalmost a l le x i s t i n gm u l t i p a t hr o u t i n gp r o t o c o l sf o c u so nf a u l t t o l e r a n tp r o b l e m s t h e yd istributemet r a f f i cm a i n l yo nt h ep r i m a r yr o u t e i ti so n l yw h e nt h i sr o u t ei sb r o k e nt h at ；i et r 棚ci sdivertedt oa l t e m a t er o u t e s c l e a r l y ，t h e yc a nn o tm e e tr e q u i r e m e n t sf o rt h r o u g h p u t andloadbalancing o fa p p l i c a t i o n 2 ) b e c a u s eo ft h ep l a n es t r u c t u r e ，t h ea b i l it yo f d i s p o s a l topologychange i sp o o r ；3 ) t h er o u t i n gc o n t r o lo v e r h e a dw i l li n c r e a s es i g n i f i c a n t l yw h e nt h en u m b e ro fthen e t w o r kn o d e s i n c r e a s e s b ya n a l y z i n gt h er e q u i r e m e n t sa n dc h a l l e n g e so fm a n e tm u l t i p a t hr o u t i n ga n ds omelimitationso fe x i s t i n gw o r k ，a n di n t r o d u c i n gc r o s s - l a y e rd e s i g ni d e a , t h i sd i s s e r t a t i o n firstfocuseso nt h ep r o b l e m so fs c a l a b l em u l t i p a t hr o u t i n g ，r e l i a b l et r a n s m i s s i o nm u l t i p a t h r o u t i n g ，d y n a m i c t o p o l o g y - b a s e da d a p t i v et r a f f i cd i st r i b u t i n gm u l t i p a t hr o u t i n ga n ds oo nthe m a j o rc o n t r i b u t i o n so f t h i st h e s i si n c l u d e ：回researcho ns c a l a b l em u l t i p a t h r o u t i n g m a n e t谢mt h ep l a n es t r u c t u r ew i l li n c r e a s er o u t i n gc o n t r o lo v e r h e a d ；t h e scalabilityprobl e mi sl i k e l yt oh a p p e n t h i sd i s s e r t a t i o np r o p o s e sc l u s t e r i n gm e t h o dt oi m p r o v e thescaia b i l i t yo fn e t w o r k o no n eh a n d ，a na d a p t i v em o b i l ec l u s t e ra l g o r i t h mc a ns u s t a i n s themobil i t yp e r f e c t l ya n dm a i n t a i n st h es t a b i l i t ya n dr o b u s t n e s so fn e t w o r ka r c h i t e c t u r e o nt heother h a n d ，u t i l i z i n gm u l t i p l ep a t h sf o rp a r a l l e lt m n s m i s s i o nc a ni m p r o v et h e throughout，avoidconge s t i o na n da c h i e v el o a d b a l a n c e 1 ) c b mr pa l g o r i t h m - c l u s t e r - b a s e dm u l f i p a t hr o u t i n g protocolcbmrpu s e ss i n g l el a y e rc l u s t e rs t r u c t u r et od e a lw i t hn e t w o r kt o p o l o g yc h a n g e s ，a n du sesthed is t r i b u t e dp u s ha n ds t e p w i s ea p p r o a c hf o rr o u t i n gd i s c o v e r y i t sa d v a n t a g e sa r e simplehierar c h i c a ls t r u c t u r e ，e a s yd e p l o y m e n t ，a n dt h ef l o o d i n gc o m m u n i c a t i o no v e r l o a di sr e d u c e d bydistr i b u t e ds t e p w i s er o u t i n gd i s c o v e r yi ns m a l l n e t w o r k 2 ) c m d s ra l g o r i t h m - c l u s t e r - b a s e dm u l t i p a t hd y n a m i cs o u r c e routingforl a r g e s c a l en e t w o r k s ，c b m r pi st o oc o m p l i c a t e d ，a n dt h eo v e r h e a di st o o e x p e n s i v e ，第1 i i 页 国防科学技术大学研究生院学位论文 a b i l i t i e si nm a 川e 。l 。 t h ea d 印t i v ed y n 锄i c 廿a m cd i s t r i b u t e da l g o r i t l l mi sa no p e n - l o o pc o m r o ls y s t e m ，s oi t s h a r dt or e a l i z eo p t i m a lt f a m cd i s t r i b u t i o n t h i sd i s s e r t a t i o np r o p o s e sa na mo p t i m i z a t i o n a l g o r i t h mw i t l lr c u s i n ga b m t i e s ，w l l i c hu s e sa n to p t i m i z a t i o na l g o r i t t os e a r c hf o ro p t i m a l r e s u h sa n dh a sp o s i t i v e f e e 曲a c km e c h a n i s mt oi m p r o v et h ee m c i e n c ya n dp r e c i s e n e s so ft r a m c d i s t r i b u t i o n a i m e da tt h er e a c t i v a t i o n so f t o p o l o g yc h a n g e ，i tr e u s et l l el a s td i s t r i b u t i o nr c s u l t si n m en e x td i s t r i b u t i 王1 舀龇l dc o n s m l c ti n i t i a lp h e r o m o n eb a s e do ni i l i t i a ls o l u t i o nt oo v e r c o m e l a c k m g i n i t i a lp _ h e r o m o n eo fa n to p t i m i z a t i o n 姐鲥t h m ，i no r d e rt oi m p r o v ei t ss e a r c h e f f i c i e n c y 如r t h e r m o r e k e y w o r d s ：m o b i l ea dh o cn e t w o r k ，m u l t i p a t hr o u t i n g ，c l u s t e r i n g ，q o sr o u t i n g ， c r o s s l a y e rd e s i g n ，r e l i a b i et m n s m i s s i o n ，f e c ，a n to p 痂n i z a t i o na l g o r i t h mw i t hn u s i n g a b i l i t i e s 第v 页 国防科学技术大学研究生院学位论文 图索引 图2 1 源到目的的3 条路径s x d ，s y d ，s z d 9 图2 2 结点a 静路国区装p = 2 1 l 图3 12 跳分簇结构1 8 圈3 2 簇的更瓤( 麓掏) 1 9 圈3 - 3 链路屡模块2 碡 图3 ，4 网络层模块2 4 图3 5 低连通性低负载下的u d p 的吞吐率。2 8 鹜3 - 6 商连通率低森负载下的u d p 验吞吐率+ 2 9 图3 7 低连通性低负载下的t c p 的吞吐率3 0 图3 _ 8 赢连通性高受载下的t c p 的嚣吐率3 0 窝3 - 9 不同移动速度鹣控铡开镑3 舀 图3 ，1 0 不同结点数控制开销3 l 圈3 ，1 1 不同移动速度的路径发现启动次数。3 l 图3 - 1 2 不同速度的端到端延霹，3 l 图3 1 3 不同速度的网络负载平衡c o v 3 2 圈4 ，l 簇结褐圈3 4 图4 - 2 结点加入簇的过程3 5 图4 3 可靠路径选择算法3 7 墨舢4 低连遥性低负载下的u d p 约吞吐率4 l 图4 5 裔连通率高受载下的u d p 的吞吐率一碡2 图4 6 低连通性低负载下的t c p 的吞吐率4 2 瑶4 7 裹连通性赢受载下耋勺跫p 豹吞吐率4 3 图4 8 不同移动速度的控制开铺4 3 图4 m 9 升i 同结点数控制开销4 3 图4 1 0 不阂移动速度戆跨径发现窟动次数。4 4 图4 1 l 不同速度的端到端延时4 砗 图4 ，1 2 不同速度的网络负载平衡c o v 4 5 蔫v 燹 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他入已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意 学位论文题目： 整盘宣童圜盗生垒监整直燕盎鲤窥 学位论文作者签名：辫 日期年，o 月夕日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目 学位论文作者 作者指导教师 国防科学技术大学研究生院学位论文 第一章绪论 1 1 概述 无线网络燕或为嚣蘩潮络逶售领域貔磅突热焱。在菜静稷发上，无线弼络镬褥人们熬 够在世界上的任何时候和任何地方交换信息。随蔫无线网络运营成本的下降、使用范围的 普及，基于无线通信网络的应用将会广泛地进入到我们的日常生活中。 不需镁键基破设戆壤麓块速部嚣、缀少f 几乎没有任秘) 管璞中心支持舱移动自主网终 ( m a n e t ) 2 j ，作为基于基础设施的黼络的一个麓要补充开始闶亮登场。m a n e t 其有移 动性强、无固定网络拓扑、资源有限等特点，提出了新的挑战性问题。m a n e t 的一个溅 本问题是弦无预定的掇扑或者集中控制情况下，翔何在结点阅有效地传递报文。这也是 m a n e t 路鑫谤议要窦溪豹主要毽繇。鑫予瓣络熬凌态性，m a n 萎t 路壶嚣貉诲多鸯线麓 络中不存在的问题。为了直接优化协议层，路由闯题经常要与物理层的能量控制、链路鼷 的多址访问控制以及应用层的服务质量( q o s ) 支持一起考虑，所以，往往漤采用跨层方 法【1 9 5 1 勰抉。 现有的m a n e t 路由协议在源和西的结点对之闻建立并使用一条单路径。由于结点移 动性、结点失败以及无线信道的动态特征，单路径中的链路可能会临时失效从而导致路径 不可达，磷寻找替代路镪的开销大，并且可能带来报文转发中的额外的延时。多路径路由 提供了虱一个嚣兹缝赢瓣多条路径。滚帮器戆缝纛可渡建露逮鍪路径鬣为主辨径嚣候选鼹 径，也可阻有选择地存多条路径上并发传输以实现负载均衡、掇高传输的可熊性和安全栋。 m a n e t 多路径路由协议己显示出其优越性。研究表明使用多路径路由具有改善性能 戆灌力。瓣蕊提凄豹多鼹经方法存在缺少鲁棒蛙、囊效牲戆不是，对于多黪经路蠹亵臻翻 端的吞畦率问的相互作粥还缺少深入研究。因此，m a n e t 多路径路由中许多问题亟待深 入研究和解决。 1 2 研究爵标 在国家重大基础硪究9 7 3 发展规划项目鞭一代互联网络路由与交按理论( n o s ， 2 0 0 3 c b 3 1 4 8 0 2 ) 、国家霆然稀学基金”潮络与穰惑安全”重大磷究诗翊懿重点磺鏊薮一代 网络体系结构模型与超高速网络交换路由研究( n o s 9 0 1 0 4 0 0 1 ) 、湖南省教育厅高等学校 科研项目“移动自主刚络中路由算法与协议研究”等项目的支持下，我们集中对多路径路 第1 燹 国防科学技术大学研究生院学位论文 由几个关键技术进行了研究。主要研究多路径路由算法、多路径的分组纠错、多路径的路 径选择及多路径的流量分配等，以提高多路径的可扩展性、可靠性及动态拓扑的适应性。 1 2 1 多路径路路由算法研究 平面式结构的m a n e t 在结点数目增多时的路由开销增加很快，可扩展性较差。适当 的分簇算法能够很好地支持移动性、维持网络结构的稳定性和鲁棒性。本文的第一个目标 是，针对现有多路径路由算法中可扩展性差的问题，提出使用分簇的方法来提高可扩展性， 一方面利用基于簇的层次结构管理动态处理网络拓扑变化，能够减少路由管理开销和路由 维护的代价；另一方面利用多路径并行传输增大了吞吐率，可以实现拥塞避免和负载平衡， 优化网络带宽的应用、提高共享信道的利用率。 一提出了c b m r p 算法基于簇的多路径算法 该算法适用于规模相对小的网络。其基本思想是采用单层簇结构来处理网络拓扑变 化，源结点发出路径查找需求后，通过分布式推进、逐段查找的方式进行路径查找，当找 到目标结点后，这时所形成的路径称为“虚拟路径”，目标结点沿虚拟路径发出反向标记 信息到源结点，源结点判断路径是否可靠，此时形成的路径为真实路径。该算法的优点是 分簇结构简单，在小规模网络中采用分布式逐段查找方式查找路径可以减少泛洪时引起的 通信开销。 提出了c m d s r 算法基于簇的动态源多路径路由算法 对于大规模网络，c b m r p 采用逐段查找路径的方法就会变得复杂，而且它采用单层 簇的简单结构，可扩展性较差。动态源路由( d s r ) 路由开销小，但它在泛洪时会产生大量 路由控制开销。本文基于d s r 算法，将网络分成单元簇( 1 - c e l lc l u s t e r ) 和中心簇( 2 s e r v e r c l u s t e r ) 两级层次结构，以提高网络的可扩展性，同时将路由发现功能放在2 - s e r v e r 层来实 现，以防止类似d s r 路由发现过程的泛洪，实现路由开销最小化。能够适应处理结点数量 增大和结点密度的增大。此外，c m d s r 通过选择可靠的路径和发送端到端的可靠性软保 证的方法提高了可靠性。 1 2 2 多路径选择算法研究 已有多路径路由算法基本上采用主、辅冗余多路径方式，一般使用主路径，当主路径 失败时才使用冗余路径。本文研究围绕两个关键问题：一是需要多少条路径以及如何选择 这些路径；二是提出路径可靠性模型和虚拟完全非交叉多路径模型，利用模型对路径可靠 性进行评估、选择、排队，为多路径路由提供更多的可靠传输路径，以充分利用带宽资源、 提高吞吐率。 第2 页 国防科学技术大学研究生院学位论文 1 3 论文结构 本文共分九章。第一章为绪论，概述了课题背景和主要内容。 第二章提供了背景信息，介绍了相关的研究成果。 第三章介绍了一种新的基于分簇的多路径路由算法，对算法作了一定的理论分析和正 确性证明，并通过模拟比较了各个算法的性能。第四章介绍了基于簇的多路径动态源路由。 第五章介绍了多路径路由中可靠多路径选择的算法，针对多路径算法中的流景分配及 负载平衡问题分析了路径选择的重要意义，然后介绍了基于最大可靠性多路径选择算法。 通过模拟，研究了算法对多路径协议性能的影响，并比较了各个协议的性能。 第六章和第七章分别对m a n e t 多路径流量分配的两个问题进行了研究，第七章介绍 了自适应动态流量分配算法，第八章介绍了基于重用的蚂蚁寻优多路径流量分配算法。 第八章首先分析了多路径传输出现报文乱序及报文丢失现象，然后介绍了基于前向纠 错( f e c ) 的多路径路由算法，论证了该算法提高多路径传输的可靠性。 第九章对本文进行总结、介绍了未来工作。 第4 页 国防科学技术大学研究生院学位论文 第二章研究背景和相关工作 2 1m a n e t 及其廒用背景介绍 2 1 1 基本裰念及发震，秀程 自主网络的英语名称为a dh o cn e t w o r k ，它是一种在泼育骨于网_ 络的袋佯f ，曲蕊 统中的通偿结点通过分布式协议互逶蠛组织起采的嘲络系统。移动钽主飘绥( m a n e t ： m o b i l ea dh o c n e t w o r k 羽是支持运信结点移魂麓謇主阚络，它主要是兔套辩努或无霾瓷 基站的地方提供移动通信服务而提出的。无线蜂窝系统通过熬站，使得在撼站覆盖范围内 的用户可以在移动中保持有效的通信连接。基站则往往通过有线链路构成的骨干网互联超 来。m a n e t 支抟没袁越线骨干网或基菇豹撼方，移动结点闼黥逶癌必须采鼹特殊技术实 现。 最初，m a n e t ( m o b i l e a d h o c n e t w o r k s ) 被称之为移动分组无线网络( m o b i l e p a c k e t r a d i o n e t w o r k s ) 。2 0 墩鳃7 0 年代初美国国防部斑级研究计划髑( d a r p a ) 如予对未来战争 的考虑，痿韵了d a r p ap r n e t ( p a c k e tr a d i on e t w o r k ) 【1 镑 艳谤潮，研究移溺分组无线瓣 络( p r n e t ) ，m a n e t 即由d a r p ap r n e t 演化而来。当时，由于高性能、低功耗移动 设备的研制受技术条件限制，计划进展缓慢。最避，由于技术发展，m a n e t 网络技术又 愿囊快逮发旋，正进入裂各个领域。 1 9 9 9 年1 月i e t fr f c 2 5 0 1 详细给出了m a n e t 的应用场合、特征和性能要求。舀前， 还有一些标准( 如i e e e 8 0 2 1 l ( a f o ) ，b l u e t o o t h ) 1 17 1 - 2 1 1 支持a dh o c 方式。圜际上典型的研 究有： i n t e m e t 工程任务组成立了专门静研究小愆m a n e t 工作，j 、照，受爨移动a dh o c 网络相关协议的标准化工作【捌。 美阉d a ) a 资助的s m a l lu n i to p e r a t i o n ss i t u a t i o na w a r e n e s ss y s t e m 2 3 1 ( s u os a s ) 开发麓够支持静d i s m o u n t e ds o l d i e r s 倍惑需要麓袋皲往技术、并集成为霹演示弱系统。囊 1 0 0 个实验单元组成的现场实验于2 0 0 2 年春开始。s u os a s 可同时支持1 0 ，0 0 0 用户， 系统工作在2 0 m h z 到2 5 g h z 的频段，带宽5 0 0 k h z 到2 0 m h z 。自适应数据速率为：4 m b s 劐1 6 m b s 。 - 瑞士联邦工学院t e r m i n n o d e s ( 与瑞士电信合作的长期研究项目2 0 0 0 + 2 0 1 0 年) 研 究和实现大规模自组织移动a dh o e 嘲络。 第5 奚 国防科学技术大学研究牛院学位论文 _ 美国m o n a r c h 大学( 卡耐梅容大学) 的m o n a r c h i z 4 1 i 作组已经建立了移动 a dh o c 网络测试床。 一欧洲已经考虑将移动a dh o c 网络作为中继，以扩大第二代和第三代移动通信系统 的覆盖范围和提高网络或者说链路故障的系统健壮性。目前已经建立了一种称为a - g s m 的实验系统【”1 。 近年来，m a n e t 的研究正呈现出百家争鸣、百花齐放的局面。 m a n e t 有其独特的优越性：不需要任何固定网络设施，可以随时随地组网并立即投 入使用。某种意义上，网络是自组织的( s e l f - o r g a n i z i n g ) 、自生成的( s e l f - c r e a t i n g ) 和自 管理的( s e l f - a d m i n i s t e r i n g ) 1 2 6 ；结点的加入或离开也可不依赖于某个或者某几个专门结点 进行组织和控制，所以容许结点发生故障，结点随意加入或者离开。m a n e t 的自组织能 力，不但可以简化网络的管理，提高其健壮性( r o b u s t n e s s ) 和灵活性，还能在动态环境下 ( 如结点位置不固定等) 使资源得到有效利用。上述优点引起了人们越来越多的关注【2 ”。 2 1 2m a n e t 面临的技术挑战 虽然m a n e t 具有诱人的应用前景，也面临许多技术挑战，主要有： 1 、可扩展性问题 m a n e t 在规模不断扩大的情况下，由于其结点能力及信道容量和质量受限，网络可 扩展性问题成为研究热点之一【3 7 】。【3 8 1 。涉及到体系结构、路由协议和管理机制等方面。 2 、服务质量( q o s ) 问题 2 8 】 m a n e t 无固定基础设施，拓扑动态变化，带宽受限，链路质量和稳定性较差，使 m a n e t 的服务质量问题增加了特殊困难。 3 、安全问题 m a n e t 基于无线通信，信道易受攻击；缺少管理中心，安全认证策略实施较困难【4 2 ”； 特殊情况下，移动结点自身的安全也会受到威胁。m a n e t 的安全问题从一开始就成为人 们关注的焦点【4 1 1 。 4 、与网络的互联、互通问题 m a n e t 的发展及其普遍、广泛的应用，对m a n e t 之间、m a n e t 与因特网及其它 网络之间的互连、互通问题提出了迫切要求。实现异构刚络的无缝对接1 是一个具有挑战 性的工作。同时，m a n e t 与其它网络间的互操作问题也是当前一个重要研究方向。 5 、能量控制问题 m a n e t 的能源往往依赖轻便、容量有限的能源设备h 5 】_ 7 1 。所以，节约及提高效率成 为一个特殊要研究的问题。人们研究了多种节能技术，例如，有选择地把接收器转入休眠 模式、节能路由算法等。 第6 页 国防科学技术大学研究生院学位论文 6 、路由协议问题 m a n e t 维点移动经鑫，蕊逶豢宽瓷添煮陵，潮络踅誓分装税率裹，鼓缀磷究逶鹰懿 协议及算法。传统的b e l l m a n f o r d 路由算法可靠性差，通信开销大，收敛遽度慢，不适合 m a n e t 网络。路由技术是m a n e t 的关键技术，也是热点技术之一。路睦】问题进一步w 分鸯以下多个子翊题： 鏊本路由问题 包括点点路由、组播路由和广播路由问题。 _ q o s ( q u a l i t yo fs e r v i c e ) 路出麓题 q o s 路c 2 6 t 【2 8 f 3 6 1 问题很大屡瑟上是应多媒体通信的需求而提出的，对于不同类型的 数据，往往需要不同的传输服务质爨。例如，视频信息或话音信息允许一宠的丢失率，但 对传输延时和延时抖动( j i t t e r ) 较为敏感；而某热重要信息，对传输可靠性和实时性均提 出特臻要求。为不霹豹数握滚分配不露懿筵羧路经，是路壶瑟瑟解决静瓣遴。 一多路径路由问题。 大多m a n e t 路由协议存源目的结点对之问只建立一条单路径。为适应m a n e t 特点， 多路径路鑫技术正褥到人髓魏重裰，鞠蘧多条臻缀寒戎替蕈条路径，褒舞l 多蘩貉径来均簿 流量、减轻拥塞，同时采用信道冗余提高传输可嚣性。 路由安全问题 m a n e t 存在安全方嚣豹特殊阉趱，对路由捺汉提供安全支持提出了姆殊要求，倒麴 路由控制消怠的加密、认证等机制。 辩2 m a n e t 鼹叁魏议 2 2 1m a n e t 路由协议分类 针对m a n e t ，人们提出了许多基于不圈策醛黥路由协议煳t 捌2 】， 8 7 t - 9 ”。缀据钵系结构 或路由策略的不同，我们骰魏下分类： 预选型( p r o a c t i v e ) 和随选型( r e a c t i v e ) 1 5 t ； 乎嚣型龌哟秘艨次型( h i e r a r c h i c a l ) ； g p s 辅助型( g p sa s s i s t e d ) 和非g p s 辅鼢( n o n g p sa s s i s t e d ) 墅路由协议； 单路径型( s i n g l e p a t h ) 和多路径型( m u l t i p a t h ) 。 在具体的路由协议设计时，可以综合几秘策醛，下露分剐简甏奔绍。 - 预选墼和隧选溅路由协议 预选裂路由协议 第7 燹 国防科学技术大学研究生院学位论文 预选型( p r o a c t i v e ) 路由协议亦称为主动型路由协议、前应式路由协议。最先用于 p r n e t ( p a c k e tr a d i on e t w o r k ) 。预选型路由协议在每个结点维护一个或多个路由表，其 中包含了该结点到网络中所有其它结点的最新的路由信息。为了维护路由表，每个结点要 定期向网络广播拓扑信息，以维护一致的网络视图。采用不同信息更新的路由表以及不同 的广播策略，形成了多种不同的具体路由协议。包括d s d v t 5 鲋，w r p 5 4 1 ，f s r t 5 5 】和 o l s r 5 6 m 8 4 l 【8 5 。 随选型路由协议 随选型( r e a c t i v e ) 路由协议又称为反应式路由协议、按需路由协议、源激励路由协议， 是专门针对m a n e t 环境提出来的。与预选型路由协议相反，该类协议不事先生成路径， 而是仅在源结点需要时才生成。一般分成两个阶段：路由发现和路由维护。当一个结点需 要向某个目标结点发送数据时，首先查询其路由表，如果不存在所需路径，就启动一个路 由发现过程，通常是广播一个路由请求( r r e q ) 分组，当合适的路由被找到f 返回一个路由 请求响应一r r e p ) ，或所有可能的路由都已检查过，该过程就终止。路由建立后，它就转入 路由维护，直到该路由不再需要( 或通过任何路径都无法访问目标结点无法维护时，只得 重启路由程序) 。该类型协议因发现路由过程、取得和维护信息的方法和传输数据方式的 差异而产生多种不同方案。典型的实例有以下几种：a o d v 5 7 1 ，d s r 5 8 9 】，t o r a 6 0 1 和 s s a 6 ”。 一平面型和层次型路由协议 平面型( f l a t ) 和层次型( h i e r a r c h i c a l ) 的路由协议是针对网络逻辑拓扑结构而言，在 平面型路由协议中，所有结点都处于同一“平面”中，每个结点的功能也都相同。而在层 次型路由协议中【8 3 】，【7 l 】，一些结点组成一个“群，簇”( “c l u s t e r ”) 或“区”( “z o n e ”) ，再由 这些群或区组成较大的“超群簇”( “s u p e rc l u s t e r ”) 或“超区”( “s u p e rz o n e ”) ，还可以由 这些“超群簇”或“超区”组成更大的“超群月筷”或“超区”，等等。这里，“群簇”和 “区”的概念是不同的，对于“群簇”，一般有“群簇”首，群内其它结点均要求能与 群首直接通信，因此群内结点间的通信一般是两跳。对于“区”、并不限定其大小，区内 结点的通信也可以是多跳。 _ g p s 辅助型和非g p s 辅助型路由协议 根据是否使用g p s ( g l o b a lp o s i t i o n i n gs y s t e m ) 提供的定位信息( 坐标位置和速度) 可以 将路由协议分为g p s 辅助型( g p sa s s i s t e d ) 和非g p s 辅助型( n o n - g p sa s s i s t e d ) 。大多数路 由协议可以借助g p s 的位置信息进行改进。目前利用g p s 定位信息的m a n e t 路由协议 还不多。l a r 6 2 l ( 1 0 c a t i o na i d e dr o u t i n g ) 是一个类似于d s r 的随选型路由协议，利用位置 信息选择控制分组泛洪的方向。d r e a m 6 3 ( d i s t a n c er o u t i n g e f f e c t a l g o r i t h m f o r m o b i l i t y ) 是一个预选型路由协议，使用位置信息确定数据分组的泛洪方向，它通过给控制信息设置 不同的t t l ( t i m e t o l i v e ) 值来实现所谓的距离效应( d i s t a n c ee f f e c t ) ，即两个结点枢距越 远它们的相对运动似乎越慢，从而减少网络中的控制信息。s u 6 4 等人首先在m a n e t 中利 第8 页 国防科学技术大学研究生院学位论文 端的延时和t c p 及u d p 的吞吐率都得到明显改善【6 6 】，【1 9 6 1 。l e e 和g e r l a 也说明了类似的结 果【6 8 1 。 无线网络中带宽是有限的，单路径可能没有足够带宽来满足一个连接的需求。如果同 时用多条路径来传输数据，路径的聚合带宽可能会满足应用的需要。多路径有更多的可用 带宽，端到端延时可能会更小。由于m a n e t 无线媒体通信，无线电波之间存在干扰，一 条路径的传输可能会影响另一条路径的传输，会影响吞吐率的提高。研究表明在高密度的 m a n e t 中使用多路径路由比使用单路径具有更高的吞吐率【7 3 】。 多路径路由还有许多其它优点，如q o s 支持【1 9 7 9 引、图像及视频信息传输、【1 9 9 】，【2 删和 增强传输安全性等叫】，【2 0 2 ，【2 0 3 1 。 2 3 1 多路径路由组成 多路径路由协议涉及路径发现及维护和流量分配两方面功能。 一路径发现和维护： 路径发现和维护完成在源结点和目的结点之间寻找多条路径。按路径特点可以分为非 交叉路径和交叉路径，非交叉路径又可以分为无共享结点的非交叉路径和无共享链路的非 交叉路径。无共享结点的非交叉路径实际上是完全非交叉路径，没有共用结点或共用链路。 无共享链路的非交叉路径指没有共用链路，但可能有共用结点。 理论上，无共享结点的非交叉路径能提供更多的累计资源，因为路径间既没有共享结 点也没有共享链路。非交叉路径可提供更多的资源、更高的容错能力。 交叉路径的主要优点是路径发现的约束条件少。对于给定的网络可以存在较多的交叉 路径。因为无共享结点的非交叉路径具有最小的冗余，更易发现。研究证明，存任意密度 的网络中，在任意两个结点中可能只有少数无共享结点的非交叉路径【7 4 】。这是因为在两个 结点之间可能有很少的区域有瓶径链路。相对于交叉路径和无共享结点的非交叉路径，无 共享链路的非交叉路径者是一个折中。 m a n e t 中因结点移动，结点或者链路失败可引起某些或者全部路径中断。在多路径 路由中，路径失效后，何时触发路径发现过程存在多种选择，两个极端情况是，一是等所 有路径失败时才执行一个路径发现过程，一是在每一次路径失败均触发路由发现过程，前 者会引入较大的全路径失效间隔，后者会引入过高的开销。一个折中的方案是设定一阈值 n ，n 条路径失败时，执行路径发现过程，这里n 小于可靠路径数。 一流量分配 源结点选择好到目的的一组路径后，就可沿着这些路径发送数据到目的结点。流量分 配机制用来处理在多路径问如何进行数据分配的问题。分配粒度选择是一个重要问题，我 们可以把全部信息流分配到一条路径，也可按某种规则把报文分到诸路径中。 第1 0 页 围防科学技术大学研究生院学位论文 2 3 2 多路径路由相关研究 在m a n e t 领域，已经提出多个多路径路由算法。 已有算法多数采用创建多条路径，但同时仅一条作为主路径，主路径失效，再选用一 条备份路径取代，此方式我们称为备份( 冗余) 多路径。这类算法对于每个源一目的对在同 一时刻只在一个连接上传送信息。此类算法典型代表有：a o m d v 【6 6 1 、