（信号与信息处理专业论文）无线mesh网络中的高吞吐量可扩展路由算法.pdf

南京邮电大学硕士研究生学位论文 摘要 摘要 无线m e s h 网络是一种高容量、高速率的分布式网络，它不同于传统的任何一种有线 与无线网络，具有自配置、自愈合、高带宽、兼容性、低成本等优点，非常适合于覆盖大 面积开放区域。无线m e s h 技术的出现为解决不同网络之间的接入问题提供了极大的可能 性，并越来越引起国内外学者、专家和研究人员的广泛关注，已经成为无线通信领域新的 研究热点。 与传统的a dh o c 网络不同，大部分的m e s h 网络应用为宽带应用且有不同的q o s 要求。然而，现有的a dh o c 路由协议没有考虑端到端的传输延时和公平性，延时抖动， 节点吞吐量和丢包率等度量，因此不能支持无线m e s h 网络中高吞吐量，不同q o s 要求 的应用。另外，现存网络协议支持的网络性能不具有扩展性，随着m e s h 网络节点数量和 规模的增大，网络的性能将急剧下降。 本文在分析已有a dh o c 路由算法的基础上，研究了无线m e s h 网络中支持高吞吐 量的路由协议。文中提出了一种支持网关和节点间有效通信的路由架构和链路容量、流间 流内干扰感知的路由判据。相比于其他路由算法，本算法综合考虑了多接口多无线电m e s h 网络中影响吞吐量和延时的主要因素，因此具有最优的性能。通过n s 一2 网络仿真，验证 了本路由算法能够有效地改善网络的吞吐量、端到端时延等指标，且与同类型算法相比在 平均路径长度和占用网络带宽方面没有明显的增加。 另外，对于无线m e s h 网络的可扩展性问题，本文提出了一种能感知流量分布的骨 干网形成算法，在算法中，簇头节点相互连接构成骨干网，每个骨干节点会监控自身的流 量负载。如果负载超过了特定的门限，分簇将自动的分裂成更小的簇或汇聚成较大的簇。 仿真结果表明，算法能有效地提高无线m e s h 网络的可扩展性和流量负载平衡性。 关键词：无线m e s h 网络；多接口多无线电；干扰感知路由；骨干网 a b s t r a c t w i r e l e s sm e s hn e t w o r k s ( x 哪r m n s ) a r ed y n a m i c a l l ys e l f - o r g a n i z e da n ds e l f - c o n f i g u r e d ，w i t ht h e n o d e si nt h en e t w o r ka u t o m a t i c a l l ye s t a b l i s h i n ga l la dh o cn e t w o r ka n dm a i n t a i n i n gt h em e s h c o n n e c t i v i t y t h es e l f - c o n f i g u r a t i o n , s e l f - o r g a n i z a t i o n ，h e t e r o g e n e o u sa n dl o w - c o s tc h a r a c t e r i s t i c o fw r l v n sm a k ei tm o s ts u i t a b l ef o rt h ew i r e l e s sa c c e s sf o rl a r g eo p e na r e a b e c a u s eo ft h e i r a d v a n t a g e so v e ro t h e rw i r e l e s sn e t w o r k s ，w m n sa r eu n d e r g o i n gr a p i dp r o g r e s sa n di n s p i r i n g n u m e r o u sa p p l i c a t i o n s d i f f e r e n tf r o mc l a s s i c a la dh o cn e t w o r k s ，m o s ta p p l i c a t i o n so fw m n sa r eb r o a d b a n ds e r v i c e s w i t hh e t e r o g e n e o u sq o sr e q u i r e m e n t s t h u s ，i na d d i t i o nt oe n d t o e n dt r a n s m i s s i o nd e l a ya n d f a i r n e s s ，m o r ep e r f o r m a n c em e t r i c s ，s u c ha sd e l a yj i t t e r , a g g r e g a t ea n dp e r - n o d et h r o u g h 。p u t ，a n d p a c k e tl o s sr a t i o s ，m u s tb ec o n s i d e r e db yc o m m u n i c a t i o np r o t o c o l s m e a n w h i l e ，t h ee x i s t i n g s e c u r i t ys c h e m e sp r o p o s e df o ra dh o cn e t w o r k sa r es t i l ln o tm a t u r ee n o u g ht ob ei m p l e m e n t e d p r a c t i c a l l yi nw m n s b a s e do ne x i t i n ga dh o cr o u t i n ga l g o r i t h m t h i sp a p e rf o c u s e so nt h eh i g h - t h r o u g h p u tr o u t i n g a l g o r i t h mf o rw m n s a n o v e lr o u t i n ga r c h i t e c t u r es u p p o r t i n gt h et r a f f i cf r o mc l i e n tn o d e st o g a t e w a ya n dc a p a c i t ya n di n t e r f e r e n c e a w a r er o u t i n gm e t r i cw a sp r o p o s e dt oe n h a n c et h e n e t w o r kp e r f o r m a n c e c o m p a r e dt oo t h e rr e l a t e dm u t i n ga l g o r i t h m ，t h ea l g o r i t h mc a p t u r e st h e m a i nf a c t o rd e t e r i o r a t i n gt h er o u t i n gp e r f o r m a n c ei n c l u d i n gl i n kc a p a c i t y , i n t e r f l o w a n d i n t r a - f l o wi n t e r f e r e n c ei nw m n s t h r o u g he x t e n s i v es i m u l a t i o no nn s 一2p l a t f o r m ，t h ea lg o r i t h m o u t p e r f o r m so t h e rr o u t i n ga l g o r i t h m so nt h et e r mo f n e t w o r kt h r o u g h p u ta n de n d - t o - e n dd e l a y i na n o t h e rc h a p t e ro ft h i sp a p e r , al o a da w a r ea d a p t i v eb a c k b o n es y n t h e s i s ( l a a b s ) a l g o r i t h m w a sp r o p o s e dt oa u t o m a t i c a l l yb a l a n c et h et r a f f i cf l o wi nt h ew m n s t h eb n e tw i l ld y n a m i c a l l y s p l i ti n t os m a l l e rs i z e o rm e r g ei n t ob i g g e ro n ea c c o r d i n gt os t a t i s t i cl o a di n f o r m a t i o no f b a c k b o n en o d e s ( b n s ) s i m u l a t i o nr e s u l t ss h o wl a a b sg e n e r a t e sm o d e r a t eb n e ts i z ea n d c o n v e r g e sq u i c k l y , t h u sp r o v i d i n g s c a l a b l ea n ds t a b l eb n e tt of a c i l i t a t et r a f f i cf l o w k e yw o r d s ：伥烈s ；m u l t i i n t e r f a c em u l t i c h a n n e l ；i n t e r f e r e n c e a w a r er o u t i n g ；b n e t i i 南京邮电大学硕士研究生学位论文 缩略语一览 a o d v a o d v 二g t b 3 g 4 g c d m a c g s r c 队 c s c d a g d s d v d s r d v a e t t e t x i e t f i m e p i s p l a a b s l c c l q s r m a c m a n e t m c d s m r - l q s r p f a p s t n q o s r c t r r e p 对迮q r t t 缩略语一览 a dh o co nd e m a n dd i s t a n c ev e c t o r a dh o co nd e m a n dd i s t a n c ev e c t o r - g a t e w a yt r e e b e y o n d3g e n e r a t i o n 4g e n e r a t i o n c o d ed i v i s i o nm u l t i p l ea c c e s s c l u s t e r h e a dg a t e w a ys w i t c hr o u t i n g c a p a c i t ya n di n t e r f e r e n c ea w a r e c h a n n e ls w i t c hc o s t d i r e c t e da c y c l i cg r a p h i c d e s t i n a t i o ns e q u e n c e dd e s t i n a t i o nv e c t o r d y n a m i cs o u r c er o u t i n g d i s t a n c ev e c t o ra l g o r i t h m e x p e c t e dt r a n s m i s s i o nt i m e e x p e c t e dt r a n s m i s s i o nc o u n tm e t r i c i n t e r a c te n g i n e e r i n gt a s kf o r c e i n t e m e tm a n e te n c a p s u l a t i o np r o t o c o l i n t e r a c ts e r v i c e p r o v i d e r l o a da w a r ea d a p t i v eb a c k b o n es y n t h e s i s l e a s tc l u s t e rc h a n g e l i n kq u a l i t ys o u r c er o u t i n g m e d i u ma c c e s sc o n t r o l m o b i l ea dh o cn e t w o r k s m i n i m u mc o n n e c t e dd o m i n a t i n gs e t m u l t i - r a d i ol i n kq u a l i t ys o u r c er o u t i n g p a t hf i n d i n ga l g o r i t h m p u b l i cs w i t c h e dt e l e p h o n en e t w o r k q u a l i t yo fs e r v i c e r e s i d u a lc h a n n e lt i m e r o u t er e p l y r o u t er e q u i r e m e n t r o u n dt r i pt i m e v 南京邮电大学硕士研究生学位论文 缩略语一览 t d m a v o i p v p n w c e t t 、礼a n w m n s o w s n z i 冲 t i m ed i v i s i o nm u l t i p l ea c c e s s v o i c eo v e ri n t e r a c tp r o t o c o l v i r t u a lp r i v a t en e t w o r k w e i g h t e dc u m u l a t i v ee x p e c t e dt r a n s m i s s i o nt i m e w i r e l e s sl o c a la r e an e t w o r k s 。慨l e s sm e s hn e t w o r k s w i r e l e s sr o u t i n gp r o t o c o l w i r e l e s ss e n s o rn e t w o r k z o n er o u t i n gp r o t o c o l v i 南京邮电大学硕士研究生学位论文 第一章绪论 第一章绪论 近年来，移动通信技术作为快速、便携、可靠方便的通信方式而受到广泛关 注，新一代的移动通信技术要求无线网络能够支持速度更快、容量更大且服务更 稳定的实时通信业务。而无线m e s h 网络【1 1 具有不需要固定基础设施、组网快速 灵活等特点，已经成为下一代移动通信技术的研究热点之一。 1 1 课题研究背景 随着信息技术的日新月异，无线通信发生了重大的变化并取得了迅猛的发 展。未来无线通信技术将朝着宽带化、移动化、全i p 化、异构化及个性化等方 面发展，以达到通信的。无所不在”。 一般认为，未来的无线通信系统将由各种不同的网络融合而成，其中包括未来 的蜂窝移动通信网络、无线局域网( w l a n ) 、移动a dh o c 网络( m a n e t ) 、 无线传感器网络( w s n ) 、卫星网络、公共电话交换网络( p s t n ) 等。网络融 合具有融合增益，体现在：网络间流量均衡、网络分集、覆盖延伸和多样性服务， 最终使得无线通信网拥有更大的容量、更好的质量、更经济和更便利的服务。然 而，多设备共存、多网共存、多接入技术共存的局面使得网络融合变得困难重重。 网络融合分为两个层面：一是在网络拓扑上选择不同网络的融合点，二是在通信 过程中如何选择端到端的路由重置的触发条件。在这两个层面都有简单融合和深 度融合之分。在第一个层面上，简单融合的做法就是在网络的最边缘一一终端上 设置多种模式，使其工作在不同的网络。这种方式没有从本质上改变原来网络的 组网和接入的方式，不具备很好的覆盖延伸和可扩展功能。在第二个层面上，最 简单的做法是在通信建立之初就选定网络，基本没有路由重置，这是一种成熟的 方法，并已有产品出现。由于感知功能的局限，目前大多数研究方法是设定一个 静态的和唯一的垂直切换触发条件。这两种方法都在网络分集和流量均衡上有较 大的局限性。 无线m e s h 技术的出现为解决不同网络之间的接入问题提供了极大的可能 南京邮电大学硕士研究生学位论文第一章绪论 性，并越来越引起国内外学者、专家和研究人员的广泛关注，已经成为无线通信 领域新的研究热点。在此基础上构建的新型宽带无线网络结构称为无线m e s h 网 络( w m n ：w i r e l e s sm e s hn e t w o r k s ) ，即种高容量、高速率的分布式网络，它不 同于传统的任何种有线与无线网络，具有自配置、自愈合、高带宽、兼容性、 低成本等优点，非常适合于覆盖大面积开放区域( 包括室外和室内) 。未来的蜂 窝移动通信网络、w l a n 、m a n e t 、w s n 、卫星网络、p s t n 等可以通过w m n 集成到因特网中( 图11 ) 。可见，w m n 将是未来无线通信领域重大技术革新，将 成为未来无线城域网核心网理想的组网方式，是构建b 3 g 4 g 的潜在技术之一。 图11 异构无线m e s h 网络示意图 由于无线m e s h 网络具有巨大的应用前景，因此成为了国内外各高校以及研 究机构的研究热点之一。目前，国内外研究人员已经对无线m e s h 网络的多无 线电技术、m a c 协议、路由协议、服务质量( q o s ) 、多址接入、可扩展性以及安 全性等关键问题，进行了广泛而深入的研究。近年来也有许多相关的论文和著作 在国内外一级刊物上发表。 本课题作为江苏省高校自然科学研究项目：0 6 k j a s l 0 0 1 “基于环境感知的异 南京邮电大学硕士研究生学位论文 第一章绪论 构无线m e s h 网络体系结构及关键技术研究 的子项目之一，主要研究了无线 m e s h 网络中的高吞吐量、可扩展性路由，负载平衡等问题。 1 2 论文的内容及结构安排 本文首先在第二章对目前国内外无线m e s h 网络技术的研究情况进行了总 结，介绍了无线m e s h 网络的应用前景，以及无线m e s h 网络的关键设计因素。 接着针对本论文讨论的高吞吐量路由算法，对已有的路由算法作了简要介绍，同 时分析了适用于m e s h 网络的路由算法应具有的特性。最后简单回顾了网络分 簇算法和层级路由算法，为介绍可扩展路由和流量平衡骨干网形成算法作铺垫。 第三章在分析已有a dh o c 路由算法的基础上，提出了一种支持多接口多无 线电无线m e s h 网络通信的a o d v - g t ( g a t e w a yt r e e ) 路由架构和链路容量、 流间流内干扰感知的c i a 路由判据。相比于其他路由算法，a o d v - g t 路由架构 和c i a 路由判据综合考虑了多接口多无线电m e s h 网络中影响吞吐量和延时的 主要因素，因此具有最优的性能。通过n s 2 网络仿真，我们将a o d v - g t 算法 和同类型算法在吞吐量、端到端延时等网络性能上做比较，同时比较了平均路径 长度和控制信息开销，以得到路由算法的综合性能评价。 第四章提出了一种能感知流量分布的骨干网形成算法( l a a b s ) 有效地解决 无线m e s h 网络的可扩展性和流量负载平衡性。最后通过仿真结果显示l a a b s 算法在流量平衡和信息开销上明显优于m a x m i nd h o p 启发算法。 第五章对全文进行了总结，并指出了下一步可能的研究方向。 南京邮电大学硕士研究生学位论文第二章无线m e s h 网络及相关算法概述 第二章无线m e s h 网络及相关算法概述 尽管在过去十年间研究者投入了大量的精力研究如何应用a dh o c 网络，这 一类型的网络仍然没有得到大规模的应用。而对基于无线a dh o c 的应用产品 商业价值有限的解释是，我们的研究都集中于军事或特殊民用场合的应用。而另 一方面，普通用户更关注于具有较高带宽，易于接入英特网的应用。为了使移动 a dh o c 网络更具有商用价值，我们需要将研究重点转移到更具实用性的“机会 a dh o c 网络”，即把a dh o c 网络不再只看做孤立的自组织网络，而是作为一 种己存在的有线网络更具灵活性，更有效的接入方式。事实上，一种新型的网络 符合了这种需求：无线m e s h 网纠引。 2 1 无线m e s h 网络概述 移动a dh o c 网络( m a n e t s ) 是节点以无线的方式相互连接构成的网络。 这些节点以自由、动态的方式自组织配置成a dh o c 拓扑结构，帮助人或设备 在无通信基础设施的地区实现互联。a dh o c 的概念不是新近想出来的，而是己 存在了三十年，如分组交换网( 1 9 7 2 ) 、自适应无线电网络( 1 9 8 0 ) 、全球移动通 信系统( 9 0 年代早期) 。传统上来说，战术网络( t a c t i c a ln e t w o r k s ) 是唯一应用 a dh o c 网络结构的系统。最近，随着廉价无线技术的引入( 比如，b l u e t o o t h 和i e e e 8 0 2 1 1 ) ，以及i n t e r n e t 工程工作小组( i e t f ) 的标准化工作，使得人们 越来越关注于将a dh o c 网络应用于军事以外的地方。事实上，在这个领域已 经存在上千篇研究论文了。i e t fm a n e tw g 正在将四种路由协议标准化，且 i e e e8 0 2 1 1 无线网卡也支持使用这一系列技术。但是，这种技术还没有影响到 我们使用无线网络的方式。除了在实验环境下，用户很少使用到8 0 2 1 l a dh o c 网络，更不用说多跳a dh o c 网络。一种流行的解释是：大部分的a dh o c 网 络研究不是由国防部( d o d ) 提出的要求( 几千a dh o c 节点的大规模军事应 用) ，就是特殊的民用场合( 灾害救助、行星探索等) 。这些研究与普通用户的 需求大相径庭。事实上，用户需要的是一个多用途的网络平台，其中费用是关键 4 南京邮电大学硕士研究生学位论文 第二章无线m e s h 网络及相关算法概述 问题，英特网接入是必要问题。因此，要想将m a n e t s 应用到民用场合，传统 - m a n e t s 的定义需要修改。从m a n e t s 的一个主要限制“由没有基础架构的用 户或设备组成，修改为更实用的“机会a dh o c 网络”。a dh o c 网络不再只 看做孤立的自组织网络，而是作为一种己存在的有线网络更具灵活性，更有效的 接入方式，与有线网络共存。无线m e s h 网络正是顺应了这种需求的产物。无 线m e s h 网络通过无线互连的移动或固定节点构成多跳的a dh o c 网络。与 m a n e t s 类似，用户的设备作为m e s h 网络活跃的一部分，动态的加入网络， 既作为网络的终端，也作为其他设备的路由器，增加了网络的覆盖范围。无线 m e s h 网络继承了m a n e t s 的很多优点，但是以民用的应用为主要目标。更进 一步的是，与m a n e t s 的研究主要基于仿真不同，m e s h 网络从一开始就与实 际的测试床有关。通过设计足够好的解决方案，我们可以验证这种技术在民用领 域的适用程度，同时吸引用户采用这种技术。虽然m e s h 网络刚提出不久，已 经在无线市场上显示了巨大的潜力。如所谓的基于8 0 2 1 1 技术的社区网络，通 过向整个社区的用户提供因特网接入服务来共享因特网接入链路。例如s e a t t l e w i r e l e s s ，c h a m p a i g n - u r b a n ac o m m u n i t yw i r e l e s sn e t w o r k ( c u w i n ) ，s a n f r a n c i s c ob a w u g ，和m i t 的r o o f n e t 系统。另外一方面，不少公司开始探索 m e s h 网络在室内和室外应用的潜力。( 比如m e s h n e t w o r k s ，t r o p o sn e t w o r k s ， r a d i a n tn e t w o r k s ，f i r e t i d e 等) 比如，室内m e s h 网通过与无线接入点互联，利 用m a n e t s 已有的路由算法，可以在不需要有线基础架构的情况下扩展w l a n 的连接。室外的m e s h 网络，可以用来在大范围的地区提供无线接入，减少有 线接入点的数目。 这种具有广泛前景的技术最近又得到了进一步的支持，i e e e 8 0 2 1 1 成立了 8 0 2 1 1 s 工作组为能提高无线局域网的m e s h 网络定义m a c 层和物理层的标准。 在这种类型的网络中，8 0 2 1 1 接入点以逐跳，类似路由器的方式相互传递信息。 当用户和接入点增加时，系统容量相应增加。除了8 0 2 1 】s ，其他i e e e 工作小组 也在为他们的协议添加m e s h 网支持部分。( 如8 0 2 1 5 5 ，8 0 2 1 6 a 和8 0 2 2 0 ) * 京邮电丈学碗l 研究生学位* 女剪二章光线m e s h 月络h “关算法概述 2 1 1 无线m e s i t 网络的应用 针对基于无线m e s h 架构的社区网络的商业应用最近已经得到了部署。想要 区分所有这些基于无线m e s h 网络的应用太过复杂，因此在这一节，我们集中 介绍从m e s h 网络受益的应用案例口j 。 1 ) 智能传输系统 许多公共交通公司、政府机构和研究组织正在寻求实现智能传输系统的可能 解决方案。( 如安全，低能耗，高效和保密的集成公共交通系统) 如图2l 所示， 无线m e s h 网络有希望成为控制交通服务所需的信息传输系统的灵活实现方案。 这种应用场景的一个案例是p o r t s m o u t h 实时交通信息系统( p o r t a l ) 。这个系 统，作为城市公托交通网络的一部分，能向乘客提供实时的路况信息。这个系统 依靠在3 0 0 多辆公交车上安置由m e s h n e t w o r k s 公司提供的m e s h 节点得以实 现。这个刚络允许用户能看到遍布整个城市，超过四十个地段的实时交通信息， 比如公交车所在的位置、最终的目的地、计划运行的时问等。人们同样设计了类 似的系统，希望能环节城市的交通拥挤，控制污染，改进传输系统的安全和保密 性等问冠。 图2l 无线m e s h 网络的应用 2 ) 公共安全 9 1 1 事件史无前例的吸引了人们对公共安全问题的关注。( 警察、消防部门、 急救和应急服务等) 产生了大量对无线网络应提供移动性支持、可靠性、灵活性 和高带宽连接的要求，基于蜂窝网络的解决方案已经采用了很多年，但是在很多 方面人们并不感到满意。蜂窝网络的数据传输速率有限，甚至低于拨号网络，而 南京邮电大学硕士研究生学位论文 第二章无线m e s h 网络及相关算法概述 且网络的部署相当昂贵。而无线m e s h 看起来是解决政府部门和安全机构的有 效方案。目前，已经出现了许多提供公共安全的m e s h 网络应用。比如，s a nm a t t e o 警署在所有的移动计算机，机车上安装了带有8 0 2 1 l b g 无线网卡的p d a ，户外 的m e s h 网络是由t r o p o sn e t w o r k s 公司提供的m e s h 互联技术。在郊区安装了 超过3 0 个的t r o p o sw i f i 接入点，以提供全面的覆盖。安装在接入点的t r o p o s 软件提供自发现、自配置和集中式网络管理和控制等功能。 3 ) 公共因特网接入 无论大小，英特网服务提供商( i s p s ) 都在大量地部署w i f i 技术以解决无 线宽带接入的需要。而无线m e s h 技术目前来看，是在城市、郊区和偏远地区 提供不需要昂贵的有线基础设施，同时提供室内、室外无线接入的理想方案。一 个案例是2 0 0 4 年四月在c a l i f o r n i a , c e r r i t o s 市启动的全市范围的宽带网络计划。 使用a i i r m e s h 通讯公司的产品，这种网络是基于t r o p p sm e s h 技术，使用了超 过1 3 0 个的室外接入点，覆盖了超过8 平方公里的城市区域，其中只有不到2 0 的接入点配备了有线连接。网络配置开销的显著减少，保证了即使在有限用户 的区域，如偏远或人烟稀少的地区，仍然能够快速配置宽带无线接入服务。( 图 2 1 所示) 2 1 2 无线m e s h 网络架构 无线m e s h 网络的架构主要可以分为三类【4 】： 1 ) 有基础设施骨干m e s h 网 在这种网络架构下，m e s h 路由器为客户提供基础设施，如图2 2 所示，实 线和虚线分别表示无线和有线链路。除了使用最常见的i e e e 8 0 2 1 1 技术，m e s h 基础设施可以使用多种无线技术构建，m e s h 路由器构成了自配置、自愈的网状 链路。通过网关，m e s h 路由器也可接入因特网。这种方法，也称为有基础设施 的m e s h 网，通过m e s h 路由器的网关和网桥作用，能为普通用户提供骨干网 的支持，能将m e s h 网络整合到现有的无线技术中。带有以太网接口的用户能 通过m e s h 路由器接入以太网络。如果用户使用不同的无线电技术，用户能和 同样带有以太网接口接入m e s h 网络的基站连接。 7 南京邮电大学硕士研究生学位论文 第二章无线m e s h 网络及相关算法概述 图2 2 有基础设施骨干m e s h 网络架构 2 ) 用户m e s h 网 用户m e s h 网络在用户设备间提供点到点的连接。在这种网络中，用户节点 组成实际的网络来提供终端的应用同时运行路由和配置功能。因此，无需为这种 网络配备m e s h 路由器。用户m e s h 网络只使用一种无线电。因此，它可视作 为传统的a dh o c 网络。但是，相比与骨干m e s h 网络，终端设备的功能必须 得到增强，因为它要执行额外的路由和自配置功能。 图2 3 混合m e s h 网络架构 8 南京邮电大学硕士研究生学位论文第二章无线m e s h 网络及相关算法概述 3 ) 混合m e s h 网络 这种结构是骨干和用户m e s h 的结合，如图2 3 所示。m e s h 用户能通过 m e s h 路由器接入网络，也能够与其他m e s h 用户直连。当基础设施能提供到 其他网络，如因特网，晰f i ，w i m a x ，蜂窝网和传感器网络等的连接，用户节 点的路由功能必须提供强劲的连接和覆盖能力。 总的来说，m e s h 网络的主要特点可以归纳为以下几点： m e s h 网络支持a dh o c 连接，且具有自组织、自配置、自愈的能力。 m e s h 网络是多跳网络，但是由骨干节点提供骨干支持。 m e s h 路由器移动性较弱，能执行路由和配置功能，减少了用户节点的计算 负载。 终端节点的移动性能由骨干网有效的支持。 m e s h 网络是集成的异构网络，同时包括有线和无线的连接，因此存在多种 的接入方式。 m e s h 路由器和m e s h 用户的能量限制是不同的。 m e s h 网络不是孤立的网络，需要与其他无线网络相互兼容和互操作。 因此，m e s h 网络是a dh o c 网络的分化，这种特性需要新的算法和设计原 则来实现m e s h 网的新功能。 2 1 3 无线m e s h 网络关键设计因素 1 ) 无线电技术 目前已经提出了很多方法来增强无线系统的容量和灵活性。典型的例子如定 向和智能天线，多天线系统( m i m o ) 和多接口多无线电系统。 为了进一步增强无线电系统的性能且能被高层协议所控制，许多更先进的无 线电技术被提出，如可配置无线电、认知无线电，甚至是软件无线电。虽然这些 无线电技术还没有成形，因为他们的动态控制能力，被认为是未来无线系统的平 台。这些先进的无线技术都需要高层协议的支持，特别是m a c 和路由协议的支 持。 2 ) 可扩展性 9 南京邮电大学硕士研究生学位论文 第二章无线m e s h 网络及相关算法概述 可扩展性是m e s h 网络的关键因素。没有可扩展性的网络在网络规模增加 - 时，性能将急剧下降。如，路由算法可能无法找到可靠的路径，m a c 协议也将 使吞吐量减少。为了支持可扩展性，从m a c 层到应用层的协议都应具有可扩展 性。 3 ) 网状连接 m e s h 网络的优势来源于网状的连接。为了保证有效的m e s h 连接，需要自 组织的网络和拓扑控制算法。拓扑感知的m a c 和路由协议能有效的改善m e s h 网络性能。 4 ) 带宽和q o s 与传统的a dh o c 网络不同，大部分的m e s h 网络应用为宽带应用且有不 同的q o s 要求。因此，除了端到端的传输延时和公平性，更多的性能度量，如 延时抖动，节点吞吐量和丢包率需要在协议中考虑。 5 ) 安全保密性 在过去的几年中，虽然已经为无线局域网提过很多安全算法，但是他们都不 完全适用于m e s h 网络。比如，因为分布架构的存在，无线m e s h 网络不能中 心式的授权和分发公钥。a dh o c 网络的安全算法可以在m e s h 网络中采用， 但是仍然需要进一步作修改。 6 ) 易用性 协议的设计必须让网络能自我配置。此外，网络管理协议的设计必须能有效 的维持操作，监控网络性能，配置参数。这些工具是m e s h 网络实现快速配置 所必须的。 7 ) 相容性和互操作 在m e s h 网中，必需要为普通用户和m e s h 用户提供网络接入支持。因此， m e s h 网络需要和传统的用户兼容，这就要求m e s h 路由器能整合异构网络的 功能。 2 1 4 m e s h 网研究面临的挑战 1 ) 网络容量 1 0 南京邮电大学硕士研究生学位论文 第二章无线m e s h 网络及相关算法概述 目前为止，已经有许多针对a dh o c 网络容量的研究。考虑到m e s h 网络 和a dh o c 网络的相似性，研究成果能被采用到m e s h 网络的研究中。 文献 5 】中得到了a dh o c 网络容量的上下限，指出了提高网络容量的有效 方法：节点应该和周围节点相互通信。为了实现这一目标，文献 5 建议了两类 方法： 通过部署中继节点能提高吞吐量。 节点需要组成簇结构。 换句话说，非邻居节点的通信应该通过中继节点和簇结构。但是考虑到 m e s h 网络的分布特性，分簇方法或部署中继是一项具有挑战性的工作。 文献 6 】反映了文献 5 】中方法的实现。文献 6 1 q b 建议通过节点的移动性增加 网络容量。源节点直到目标节点足够近才发送信息。因此，节点只与他的邻居节 点通信。这种方法的限制是：传输延时比较大且节点需要的缓存可能趋于无限。 文献 5 1 1 6 1 的分析对无线网络容量的研究起了很大的推动作用。这些研究的局 限在于网络协议还没有被考虑到。不同的接入协议，功率控制方法和路由协议能 明显的改善无线网络的容量。但是文献 5 】 6 】只考虑了过分简化的模型。 文献 5 】中方法的另一个局限性是理论的容量限制是基于渐进分析。它并没有 揭示当网络节点较少时的准确容量。假设的网络尺寸和节点密度与实际的网络大 小并不匹配。更进一步，a dh o c 网络的分析不能直接应用到m e s h 网中。因 此，m e s h 网络需要新的分析结果。 2 2 无线m e s h 网络中的有效路由 尽管已经提出了许多a dh o c 网络的路由协议，针对m e s h 网络的路由协 议仍然是个活跃的领域。我们认为最优的路由协议必须包括以下几点： 多种性能度量。大多数现存的路由协议此阿用最少跳数作为路径选择的 度量。这在许多情况下效率低下。 可扩展性。在大范围的m e s h 网络中保持路径需要很长的时间。因此， 可扩展的路由协议对于m e s h 网络至关重要。 健壮性。为了避免服务的中断，路由协议必须能应对链路断裂和拥塞。 南京邮电大学硕士研究生学位论文第二章无线m e s h 网络及相关算法概述 同时路由协议需要具有流量平衡能力。 在m e s h 基础架构下的有效路由。考虑到m e s h 路由器弱移动性无功率 限制要求，路由算法相对a dh o c 网络要求简单有效，且能和m e s h 基 础架构相结合。 现存的几种路由算法已经考虑到了这些要求。但是没有任何一种包括了所有 的特性。 2 2 1 具有多种性能度量的路由协议 文献 7 】中研究了路由判据对路由协议性能的影响，而一种考虑了链路质量的 源路由( l q s r ) 根据链路质量选择路径。并分别实现了几种性能判据，如期望 传输次数( e t x ) ，r 阿。对使用了这些路由判据的路由协议的性能与只使用了 最小跳数算法的性能做了比较。对于静态的无线m e s h 网络，e t x 能取得最好 的性能，而最小跳数在节点移动的情况下比其他三种性能优越。因此，在考虑了 移动性的m e s h 网络中使用文献 7 】中采用的链路质量判据是不够的。 多无线电路由。文献 8 】中介绍了一种多无线电链路质量路由( m r l q s r ) ， 采用了称为加权累积期望传输时间( w c e 兀) 的算法。w c e t t 同时考虑了链 路质量和最小跳数，因此在延时和吞吐量上取得了很好的平衡。m r l q s r 算法 假定每个节点上的无线电能配置到互不干扰的信道上。 多路径路由。使用多径路由的主要目标是实现更好的流量平衡和提供更高的 容错能力。在源和目的节点选择的多径，当链路因为信道质量差或移动而断裂时， 可以选择已有路径的另一条通路。因为不需要等待建立新路径，端到端延时，吞 吐量和容错能力得到提高。但是，在给定的路由判据下，算法的性能取决于源到 目的节点间非耦合路径的数目。 层级路由。在层级路由【9 】中，采用了一种自组织的方法将一组网络节点分簇。 每个簇由一个或几个簇头节点，簇中的节点位于簇头节点一跳或几跳的距离。因 为簇间连接性的需要，许多簇间的节点相互通信构成网关。当节点密度较高时， 层级路由算法能取得更好的性能，因为更小的开销，更短的路径长度和快速路径 建立的过程。但是，保持层级路由的复杂度可能抵消分簇带来的收益。进一步而 言，在m e s h 网络中由于用户节点通信能力有限，应该避免成为簇头节点。 南京邮电大学硕士研究生学位论文第二章无线m e s h 网络及相关算法概述 地理路由算法。相比于拓扑路由，地理路由算法只依靠节点的位置信息来传 - 输分组【1 0 1 。因此，相比其他算法，拓扑的变化对地理路由算法的性能影响较小。 早期的地理路由算法是一类单路径的贪婪路由算法，分组的传输是由当前节点、 邻居节点和目的节点的位置信息共同决定的。但是，所有的贪婪路由算法存在共 同的问题，如即使源和目的之间存在一条路径，传输也得不到保证。为了能保证 传输，文献 1 0 】中建议了基于平面图的地理路由算法。但是，这些算法比贪婪算 法的信息开销更大。 2 2 2 开放的研究问题 对于m e s h 网络中的路由协议，许多问题还有待研究。 可扩展性。层级路由算法能解决这个问题，但是仍然存在复杂和难于管理的 问题。依靠g p s 或其他定位技术支持的地理路由算法，也会增加m e s h 网络的 复杂度和开销。因此，新的可扩展路由算法有待研究。 更好的路由判据。新的路由判据应能够整合到合适的路由框架使得整体的性 能得到提升。 路由层m a c 层跨层设计。新的路由算法应能和m a c 交互作用来提升性能。 将多种m a c 判据加入到路由算法是个很好的例子。但是，因为m a c 层和路由 层联系如此紧密，只交换参数是不够的。整合m a c 层和路由层的部分功能是个 有前景的方向。 有效m e s h 路由。在m e s h 框架下，比a dh o c 网络中路由算法更有效和 简单的路由算法有待进一步研究。 2 3 传统分簇算法介绍 在论述如何设计无线m e s h 网络中的高吞吐量路由算法后，我们还将介绍构 建层级网络解决路由的可扩展性和网络流量平衡问题。在本节，我们先简要介绍 传统的骨干网形成，即分簇算法，其中绝大多数是针对a dh o c 网络设计的。 层级网络是组织拥有大数量节点网络的有效方法。在单分层结构中，节点被 分成簇，有的拥有簇头节点，有的则没有。这种结构适合于数量在几百个节点的 南京邮电大学硕士研究生学位论文第二章无线m e s h 网络及相关算法概述 网络。文献 1 1 】【1 2 】 1 3 】提出的多层结构以多层簇头节点形成树形结构组织。一个 三层的网络由普通节点、簇头和超级簇头组成，适用于数量在数千节点的网络。 在本文中，我们集中介绍单层结构。 早期的文献【1 4 】【1 5 】【1 2 】【1 6 】【1 7 1 假定簇