（计算机系统结构专业论文）多信道无线mesh网络中的信道分配和路由算法研究.pdf

中雹科学技术大学硕士学位论文 摘要 随着i e e e8 0 2 “等无线接入技术的发展，无线m e s h 网络已经逐步成为企 业界和消费者瞩目的焦点之一。如何提高无线m e s h 网络的容量来满足用户日益 增长的带宽需求( 如实时音频、视频下载等) 是近年来研究的热点和难点。i e e e 8 0 2 1 1a b g 等标准都定义了不同数目的正交信道，利用这些正交信道可以同时 发送数据包且不会相互干扰。充分利用多信道正交的特点，就可以减少节点间的 冲突，从而提高无线m e s h 网络的容量。 本文研究了多信道无线m e s h 网络中的信道分配问题和路由度量问题，分别 提出了相应的解决方案。其主要研究内容和贡献如下： 本文首先研究了多信道无线m e s h 网络中的信道分配问题。在对已有的信道 分配方案进行了详细的分析和比较后，本文提出了两种新的信道分配方案，即组 划分信道分配方案和基于冲突图的分布式信道分配方案。组划分方案首先将自己 的邻居节点分组，然后对每组节点进行统一的接口卡和信道分配；基于冲突图的 信道分配方案主要通过在链路冲突图中引入极大团的思想来解决信道分配问题， 首先相互干扰的链路通过其相应的代理节点交换链路负载信息，然后各个极大团 中链路根据其所在团中的链路负载信息运用贪心算法进行分布式信道分配。组划 分分配方案简单实用，针对网格状拓扑结构，该分配方法是较好的解决方案，但 是该方法在进行信道分配时没有考虑链路的负载情况，并且其分配效果与拓扑结 构密切相关；基于冲突图的分布式分配方案不仅不依赖于网络拓扑，而且在网络 负载变化和网络可用资源变化( 节点配置的网络接口卡数目和网络中可用的信道 数目) 的情况下均能够有效的进行信道分配，相比传统的集中式信道分配方案， 该方法应用于实际网络中具有更好的可操作性。 其次，本文还研究了多信道无线m e s h 网络中的路由度量问题。通过分析现 有路由度量方法应用于该网络的不足，提出了一种新的路由度量方法r m 3 ，该 方法不仅考虑了路径的期望传输时间，而且综合考虑了信道的多样性以及信道的 切换开销等因素。该度量方法能很好的应用于“源发起按需路由协议”中。 通过仿真实验表明，本文提出的信道分配方案能够较好的利用网络中提供的 多个正交信道，与其它当前的信道分配方法相比较，该方法能够较大的提高网络 的吞吐率；路由度量方法在多数情况下优于目前已经提出的路由度量方法，尤其 在网络接口卡需要在多个信道之间频繁切换的情况下，具有非常好的性能。 关键词；多信道，无线m e s h 网络，冲突图，团，路由度量 中国科学技术大学硕士学位论文 a b s t r a c t w 弛t h er a p i dd e v e l o p m e n ti nw i r e l e s sa c c e s st e c l m o l o g i a s ，w i r e l e s sm e s h n e t w o r k sh a sg r a d u a l l yb e c o m eah o tt o p i ci nb u s i n e s s h o wt oi m p r o v ew i r e l e s s m e s hn e t w o r k s c a p a c i t yt om e e tg r o w i n gu s e rd e m a n df o rb a n d w i d t h ( s u c h 船 r e a l - t i m ea u d i o v i d e od o w n l o a d i n g ) i sa n o t h e rh o tt o p i ei nr e c e n ty e a r s t h em e e 8 0 2 1 l as t a n d a r da n dm e e8 0 2 1 l b 8 0 2 1 l gs t a n d a r d sp r o v i d e1 2a n d 3 n o n - o v e r l a p p i n gf r e q u e n c yc h a n n e l s ，r e s p e c t i v e l y , t h a tc o u l db eu s e ds i m u l t a n e o u s l y w i t h i nan e i g h b o r h o o d a b i l i t yt ou t i l i z em u l t i p l ec h a n n e l sw i t h i nt h es a m en e t w o r k s u b s t a n t i a l l yi n c r e a s e st h ee f f e c t i v eb a n d w i d t ha v a i l a b l et ow i r e l e s sn e t w o r kn o d e s , t h e r e b ye n h a n c i n gt h ew i r e l e s sm e s hn e t w o r k s c a p a c i t y i nt h i st h e s i s ，w ec o n s i d e rt h ec h a n n e la s s i g n m e n tp r o b l e ma n dr o u t i n gm e t r i c p r o b l e mf o rm u l t i h o pw i r e l e s sm e s hn e t w o r k si nw h i c he a c hn o d eh a sm u l t i p l e i n t e r f a c e s t h em a i nc o n t e n ta n dc o n t r i b u t i o na r ca sf o l l o w s ： 刚st h e s i sf i r s t d e e p l yi n v e s t i g a t e so nt h ec h a n n e la l l o c a t i o np r o b l e mi n m u r i - 吧h a n n e lw i r e l e s sm e s hn e t w o r k s g i v e nt h en u m b e ro fi n t e r f a c e sa te a c hn o d e a n da v a i l a b l ec h a n n e l si nt h es y s t e m , w ed e v e l o pa n de v a l u a t e2n o v e lc h a n n e l a s s i g n m e n ta l g o r i t h m sf o rm u l t i c h a n n e lw i r e l e s sm e s hn e t w o r k s t h ef i r s ta l g o r i t h m i sg r o u pp a r t i t i o n i n gs c h e m e ，w h i c hp e r f o r m sc h a n n e la s s i g n m e n tb a s e do nn e t w o r k t o p o l o g y 1 1 1 es e c o n da l g o f i t h m r e s o l v e st h ec h a n n e la s s i g n m e n tp r o b l e mb y i n t r o d u c i n gm a x i m a lc l i q u ei n l i n kc o n f l i c tg r a p h , w h i c hu s e s g r e e d ya l g o r i t h m c h a n n e la s s i g n m e n ti nad i s t r i b u t e di n a n n e rw h i l em a i n t a i n i n gn e t w o r kc o n n e c t i v i t y n 蟛s e c o n da s s i g n m e n ta l g o r i t h mc a ne f f e c t i v e l ya d a p ti t s e l fw i t ht h en u m b e ro f c h a n n e l s i n t e r f a c e s a sn e wc h a n n e l sb o _ 7 , o m ea v a i l a b l e ，t h ea l g o r i t h mc a l li n c r e a s et h e d 朗瑚d i s t a n c ea n dt h u si n c r e a s et h et h r o u g h p u to f t h en e t w o r k s s e c o n d l y , t h i st h e s i sc o n c e n t r a t e so nt h er o u t i n gm e t r i cp r o b l e m i nm u l t i c h a n n e l w i r e l e s sm e s hn e t w o r k s i nt h i st h e m s ，w eh a v ep r o p o s e dan e w r o u t i n gm e t r i c ( i 吖) f o rm u h i - e h a r m e lw i r e l e s sm e s hn e t w o r k s t h ep r o p o s e dr m ；im e t r i cn o to n l ya i m e d a tm i n i m i z i n gt h en u m b e ro f h o p su s e da n dt h en u m b e ro f i n t e r f a c es w i t c h e sr e q u i r e d a l o n gap a t h , b u ta l s oe n s u r e d 伽a tc h a n n e ld i v e r s ep a t h sa r es e l e c t e d 。a n dt h e 州m e t r i c i se a s i l yi n t e g r a t e di n t oas o u r c e - i n i t i a t e do n - d e m a n dr o u t i n gp r o t o c 0 1 o u rs i m u l a t i o nr e s u l t ss h o wt h a to b r sd i s t r i b u t e dc h a n n e la s s i g n m e n ta l g o r i t h m s i g n i f i c a n t l yi m p r o v e sn e t w o r kp e r f o r m a n c ei nt e r m so ft h r o u g h p u ta n dd e l a ya n di s c o m p a r a b l et ot h eb e s tp r i o rc e n t r a l i z e ds c h e m et h a tj o i n t i yc o n s i d e r sr o u t i n ga n d c h a r m e la s s i g n m e n t d e t a i l e de v a l u a t i o n sh a v es h o w nt h a ti ns e v e r a ls c e n a r i o s 。r m 3 m e t r i co b t l 攒f o l m so t h e rr o u t i n gm e t r i c st h a th a v eb e e np r o p o s e di nt h ep a s t ，a n dt h e m e t r i ci sw e l l - s u i t e df o rt h es c e n a r i ow h e r et h en u m b e ro fi n t e r f a c e sp e rn o d ei s s m a l l e rt h a nt h en u m b e ro f c h a n n e l s k e yw o r d s ：m u l t i c h a n n e l ，w i r e l e s sm e s hn e t w o r k s ，c o n f l i c to r a p h , c l i q u e ， r o u t i n gm e t r i c n 中国科学技术大学学位学位论文相关声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究 工作所取得的成果。除已特别加以标注和致谢的地方外，论文中 不包含任何他人已经发表或撰写过的研究成果。与我一同工作的 同志对本研究所做的贡献均己在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权， 即：学校有权按有关规定向国家有关部门或机构送交论文的复 印件和电子版，允许论文被查阅或借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复翩手段保存、 汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：塑= ! 矽7 年f 月艿1 3 中西科学技术大学硕士学位论文 第1 章绪论 第1 章绪论 近年来，无线局域网w l a n ( w i r e l e s sl o c a la r e an e t w o r k ) 依其所具有的较大 数据传输速率，作为高效率、低成本的无线解决方案已经成为当今的主流技术之 一，w l a n 也一直被认为是3 g 和3 g 后移动数据通信部分的一个主要竞争对手。 无线局域网的移动性为用户创造了高效灵活的工作环境，大大提高了工作效率， 其价值已被越来越多的人们所认同。对于服务提供商，无线局域网的无线宽带接 入能力与漫游能力可以提供给用户随时随地“永远在线”的网络接入服务，为i s p 带来了新的商机。 但在传统w l a n 中，节点在进行无线连接之前必须首先访问集中的接入点 a p ( a c c e s sp o i n t ) ，由于a p 的覆盖范围有限，传统w l a n 在大面积开放区域覆 盖方面显得力不从心。虽然人们对此提出了一些解决方法，如通过多种无线技术 的共存来提高无线的覆盖和位置的适应性等等，但这些方法大多是以增加接入点 或降低网络运行效率为代价的。于是人们把目光转向了另一种网络结构一无线 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 ) ，希望通过这种全新的网络结构来克服传 统无线网络中所存在的固有缺点，实现无线宽带领域中的一次变革。 本章首先介绍了无线m e s h 网络的定义、架构、特点及其应用，然后对无线 m e s h 网络研究中的一些关键技术进行介绍，最后给出本文的主要研究内容与组 织结构。 1 1 无线m e s h 网络简介 1 1 1 无线m e s h 网络的概念 无线m e s h 网络( 简称w m n 、无线网状网、无线多跳网或无线网格网) 是一种 多跳、具有自组织和自愈等特点的新型宽带无线网络，也是一种高容量、高速率 的分布式网络。无线m e s h 网络不同于传统的无线网络，它可以看成是w l a n ( 单 跳) 和移动a dh o c 网络( 多跳) 的融合，且发挥了两者的优势【1 】。无线m e s h 网络 作为可以解决“最后l k m ”网络接入瓶颈问题的方案，已被写入了i e e e 8 0 2 1 6 ( w i m a x ) 无线宽带接入网络标准中【2 4 】，目前也纳入到i e e e8 0 2 1 5 m e s h 5 ，6 】和正在制定的i e e e8 0 2 1 i sm e s h 标准中【7 ，8 】。从技术特点来看， w m n 将成为未来无线城域网( w m 朋叼中核心网的理想组网方式，它也是迄今为 止唯一一种建设商用移动a dh o c 网络的可行技术【9 1 2 】。 传统的无线网络必须首先访问集中的接入点才能进行无线连接。这样，即使 中国科学技术大学硕士学位论文 第l 章绪论 两个8 0 2 1 1 b 的节点互相都在彼此的通信范围之内，它们也必须通过接入点才能 进行通信。而“m e s h ”这个词原来的意思就是指全连通，即所有的节点都互相 连接，所以在无线m e s h 网络中，每个节点都可以与一个或者多个对等节点进行 直接通信。m e s h 网络技术原是一项军方技术，随着人们对i e e e8 0 2 1 l a b 和 8 0 2 1 l g 等w l a n 技术了解的深入，无线m e s h 网络才逐步成为企业界和消费者 瞩目的焦点 1 】。 目前主要观点认为，w m n 是一种由无线链路连接路由器和终端设备的静态 无线网络，是i n t e r n e t 的无线版本，即i n t e m e t 的构架其实就己经是一个m e s h 网 络的结构【1 】。众所周知，接入i n t e m e t 的用户位于网络的边缘，他们通过网络内 部的路由器和节点相互连接，而这些路由器和节点的连接方式是这样的：当任意 两个节点之间的一条链路失效后，路由器会经由一个或多个别的路由器找到一条 替代路径。这也正好体现了m e s h 网络的思想。 1 1 2 无线m e s h 网络的架构 传统的无线接入技术中，主要采用的是点到点或者点到多点的拓扑结构。例 如移动a d h o e 网络和i e e e 一8 0 2 1 1 无线局域网就分别是点对点的网状网络和点到 多点的星型网络的代表。在这种拓扑结构中一般都存在一个中心节点，例如移动 通信系统中的基站、i e e e8 0 2 1 l 无线局域网中的a p 等等。中心节点一方面与 各个无线终端通过单跳无线链路相连，以此来控制无线终端对无线网络的访问； 另一方面，中心节点又通过有线链路与有线骨干网络相连，提供到骨干网的连接。 实际上，无线m e s h 网络吸收了星型与网状两种网络的优点，是对两者的一种无 缝融合【l 】。在无线m e s h 网络中，采用网状m e s h 拓扑结构，也可以说是一种多 点到多点的网络拓扑结构。在这种网络结构中，各个网络节点通过相邻其他网络 节点，以无线多跳的方式相连。 无线m e s h 网络主要由两种网络节点组成：m e s h 路由器( m e s hr o u t e r ) 和m e s h 终端( m e s he n dd e v i c e ) 。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 路由器与外部网络( 如i n t e m e t ) 相连。m e s h 终端也具备有一 定的m e s h 网络互连和分组转发功能，但是一般不具有网关桥接的功能。通常， m e s h 终端通常就只有一个无线接口，实现的复杂度也远小于m e s h 路由器。m e s h 终端可以是笔记本电脑、掌上电脑、手机以及p d a 等终端设备。m e s h 终端之间 2 中国科学技术大学硕士学位论文 第l 章绪论 互连构成小型的对等通信网络。m e s h 路由器和m e s h 终端之间的混合组网如下 图所示【l 】： 匿1 - 1 无线m e s h 网络的架构 1 1 3 无线m e s h 网络的特点和优点 从以上介绍可以看出，无线m e s h 网络在架构上面和传统的无线网络存在着 明显的区别。与传统的无线接入技术相比，无线m e s h 网络更具有着如下一些显 著特点f l 】： ( 1 )具有a d h o e 网络的特点 由于传统w l a n 在大面积开放区域覆盖方面显得力从心。无线m e s h 网络在 诞生之初的目标就是能够在不牺牲网络运行效率的情况下扩展现有无线网络的 覆盖范围。为了能够实现这个目标，无可避免的采用了多跳m e s h 网络。在多跳 m e s h 网络架构中，无线链路间的距离更短、发射功率更小、节点间的干扰更少 和重用效率更高，这样不仅能够提供大面积的无线区域覆盖和真正的平滑漫游能 力，更能提升网络的系统容量，提离网络的运行效率。 3 中圈科学技术大学硕士学位论文 第l 章绪论 无线m e s h 网络也具有a d h o e 网络结构灵活、易于部署和配置、容错以及网 状连接多点到多点通信等特点，使得无线m e s h 网络的初始部署成本低，并且可 以根据需要来逐步扩容。自组织和自愈能力使得无线m e s h 网络不需要网络管理 员来手工进行网络的配置，而是自动发现新节点，自动完成网络配置过程，自动 维护网络正常运行，在出现节点或者链路故障时也可以自动调整完成网络自愈 无线m e s h 网络除了具备a dh o e 网络的特性和优点以为，还有着自己与a d h o e 网络的不同特点。 ( 2 )具有无线基础设施骨干网和支持多种类型的网络接入 无线m e s h 网络内，由m e s h 路由器组成了一个无线骨干网，专门用于给无 线终端用户提供可靠的网络连接。这个无线骨干网在无线区域内提供了大覆盖范 围，以及连通性和健壮性。而在a dh o e 网络中，主要是各个不可靠的终端用户 来进行通信，不存在有专门提供网络连接服务的基础骨干网，这也给a dh o e 的 应用带来了很大的限制。 在无线m e s h 网络中，既支持无线终端接入骨干网，又支持无线终端之间的 对等网络通信【1 3 】。此外，无线m e s h 技术还可以与其他的无线网络技术相结合， 更好的给这些无线网络的终端用户提供无线接入服务。例如无线m e s h 网络可以 通过m e s h 路由器的网关桥接功能，整合现在已有的多种无线嘎络技术，如 w i m a x 1 4 ，1 5 ，z i g b e e 1 6 和蜂窝网络等等。这样，通过m e s h 路由器组成的 无线骨干网，可以把多种不同的无线网络连接到一起，形成一个“无线互联网”。 ( 3 ) 移动性 无线m e s h 网络与同样采用多跳网状拓扑的a d h o e 网络相比，移动性方面也 有着很大的不同。a dh o e 网络是由移动终端设备组成的无线分布式多跳网络， 其中一般不包含静止的节点设备，而无线m e s h 网络中的无线路由器大多是静止 的设备，而用户终端也可以是静止或移动的无线接入终端，具有很小的移动性。 所以在无线m e s h 网络里面，不存在a dh o e 网络中由于用户终端的移动性和不 可靠性给路由协议和网络配置部署等带来的巨大挑战。 由于m e s h 路由器一般为静止不动的设备，m e s h 路由器和移动终端也都没有 很苛刻的功耗限制。这样，在设计m e s h 路由器的物理层、m a c 层以及网络层 协议时，可以不考虑苛刻的功耗限制，这不仅大大的简化了协议的设计，更可以 采用性能相对更高的设计方案。 1 1 4 无线m e s h 网络的应用 同样作为无线多跳网络，与a dh o e 网络技术只用于军事以及专用特殊网络 不同，无线m e s h 网络的研究开发是由实际应用需求为驱动力的，其应用场景和 应用范围相当广泛，并且有着不可替代的作用和优势。无线m e s h 网络可以和 4 中国科学技术大学硕士学位论文 第1 章绪论 匝e e8 0 2 1 1w l a n 、m e e8 0 2 1 6 w m a n 以及3 g 移动通信等各种无线接入技术 相结合，实现家庭网络、企业网络、社区、学校网络以及城域网络内的多层次、 多范围的无线应用【i 】。 ( 1 )家庭 现在，宽带家庭网络互连大多还采用i e e e8 0 2 1 1w l a n 来实现，但w l a n 在a p 的放置需要现场勘察，但仍不免会产生覆盖不到的盲区。为了消除盲区， 可在家庭互联网络中采用无线m e s h 技术，放置多个小型m e s h 路由器，以多跳 m e s h 网络互连家庭内部数字设备不仅可以消除盲区，同时还可以大大提高网络 的容错性，且可减少由于迂回访问产生造成的网络拥塞。 ( 2 ) 企业 目前。i e e e8 0 2 1 1w l a n 已经在企业办公室写字楼中得到了广泛的应用， 但这些w l a n 或者相互没有连接，或者采用不太经济的有线以太网方式相连。 如果采用无线m e s h 网络技术，通过m e s h 路由器将这些w l a n 互连，一方面可 以解决w l a n 网络之间的连通性问题，另一方面相对采用有线互连的方式还可 以节约成本、灵活部署、提高网络的容错性和健壮性等。 ( 3 )社区 通过在社区内放置多个m e s h 路由器，可以将社区内各用户家庭的网络互连， 形成一个社区无线多跳网络。有了这个社区无线互连网络，就可以在社区内用户 家庭之间共享若干个i n t e m e t 接入设备，而不必在每个用户家庭安装i n t e r n e t 接 入设备。而且，社区无线m e s h 网络还可以容许社区用户家庭无需通过远端服务 提供商网络，就可以在社区内本地相互访问，共享社区内网络资源。而且无线 m e s h 网络的网状拓扑结构，也给用户提供了更加可靠的网络连接。 ( 4 ) 学校 校园无线网络与大型企业非常类似，但也有自己的不同特点。一是校园 w l a n 的规模巨大，不仅地域范围大，用户多，而且通信量也大，因为与一般 企业用户相比学生会更多地使用多媒体；二是网络覆盖的要求高，网络必须能够 实现室内、室外、礼堂、宿舍、图书馆、公共场所等之间的无缝漫游；三是负载 平衡非常重要，由于学生经常要集中活动，当学生同时在某个位置使用网络时就 可能发生通信拥塞现象。 解决这些问题的传统作法是在室内高密度地安装a p ，而在室外安装的a p 数量则很少。但由于校园网的用户需求变化较大，有可能经常需要增加新的a p 或调整a f 的部署位置，这会带来很大的成本增加。而使用m e s h 方式组网，不 仅易于实现网络的结构升级和调整，而且能够实现室外和室内之间的无缝漫游。 ( 5 )城域网 。5 中国科学技术大学硕士学位论文 第1 章绪论 通过无线m e s h 网络，整合i e e e8 0 2 1 6w m a n ，i e e e8 0 2 1 1w l a n 以及 3 g 移动通信等其他无线接入技术可以形成一个大范围、多层次、多样化接入方 式的城域无线接入网络，使得该网络的覆盖广度、深度等都大大的增加。 1 2 无线m e s h 网络的关键技术因素 无线m e s h 网络作为一种新的无线接入网络技术，需要考察影响其性能的关 键技术因素。这些技术因素如下： ( 1 ) 物理层无线电技术 无线m e s h 宽带网络中一个重要的问题就是天线的使用，因为每个节点必须 和各个方向上的多个节点通信，很简单的一种方式就是采用全向天线【1 7 】，但是 这样覆盖范围有限，并会带来干扰，导致频谱利用率下降，网络容量减小，所以 不建议采用全向天线。美国的s k y p i l o t 公司将智能天线技术【1 8 】应用于无线m e s h 网络，允许频谱重复使用，从而大大提高了频谱的利用率，同时减小了干扰。在 i e e e8 0 2 1 6 a 宽带无线接入标准中也建议把智能天线技术应用到无线m e s h 宽带 接入网络中。 其他的还有自适应调制编码、m 1 m o 技术 1 9 ，2 0 】以及多无线电多信道系统 2 1 ，2 2 等，也都已经成为下一代无线接入系统的不可或缺的关键技术。此外，为 了进一步改善无线射频性能以及高层协议的控制，更先进的可重配置无线电 【2 3 】、感知无线电【2 4 】、甚至软件无线电技术【2 5 】都已经开始在无线系统中有所运 用。这些高级物理层无线电技术的开发设计不仅对物理层性能起着决定性作用， 而且要求运行整合物理层、m a c 层和网络层进行整体设计，以便最大限度提高 整个网络的性能 2 6 1 。 f 2 1m a c 层协议 无线m e s h 网络是分布式无线多跳网状网。现有的针对单跳无线网络设计的 m a c 机制并不适应于无线m e s h 网络，例如i e e e8 0 2 1 1w l a n 的m a c 机制在 无线链路跳数达到四跳以上时，性能下降的非常大。同时，在无线m e s h 网络这 种分布式无线多跳网状网中，由于实现时间同步和码管理困难，采用t d m a 和 c d m a 多址接入也比较复杂【2 7 】。此外，在无线m e s h 网络中，还要求能够有效 的进行空间频率重用，以提高网络容量。这样，m a c 机制设计是无线m e s h 网 络性能和成功与否的关键技术因素之一。 ( 3 ) 路由层协议 无线m e s h 网络中，路由协议的设计是一个关键。首先，无线m e s h 宽带接 入网络中一个很重要的问题是路由选择，例如从节点a 到节点b ，可以经过不 同的用户站中转，存在多条路径，于是选择哪条路径就成为一个关键问题，这将 6 中国科学技术大学硕士学位论文 第1 章绪论 直接影响系统的性能 2 8 】。在无线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 e 网络协 议简单的多的路由协议：而对于m e s h 终端，则需要采用类似于a dh o e 网络的 路由协议。这样，就需要一种行之有效的路由协议能够自适应支持m e s h 路由器 和m e s h 终端。 ( 4 ) q o s 业务支持以及兼容性和互操作性支持 与a d h o e 网络不同，无线m e s h 网络的大多数应用都是具有不同q o s 要求的 宽带业务。这样，除了端到端时延和公平性以外，还需要在通信协议中考虑时延 抖动、聚合吞吐量、每节点吞吐量以及分析分组丢失率等性能评价指标。 对于无线m e s h 网络来说，最好不仅能支持m e s h 终端，还能支持传统的无 线终端。这就需要无线m e s h 网络能够后向兼容传统无线终端。此外，无线m e s h 网络需要能够包容整合多种异构类型无线接入网络，因而要求m e s h 路由器在不 同异构无线接入网络中具有互操作性。 1 3 本文的主要内容 随着人们对i e e e8 0 2 “等w l a n 技术了解的深入，无线m e s h 网络已经逐 步成为企业界和消费者瞩目的焦点之一。无线m e s h 网络作为典型的多跳无线网 络，如何利用无线介质的共享特性来满足用户日益增长的带宽需求( 如实时音频、 视频下载等) ，是近年来研究的热点和难点所在。由于i e e e8 0 2 1 1a b g 等标准 都定义了不同数目的正交信道，利用这些正交信道可以同时发送数据包且不会相 互干扰。充分利用信道正交的特点，就可以减少节点间的冲突，提高无线m e s h 网络的容量。 本文对多信道无线m e s h 网络进行了研究，重点研究了其中的信道分配阃题 和路由度量问题。针对信道分配问题，我们提出了组划分信道分配方案和基于冲 突图的分布式信道分配方案。组划分方案首先将自己的邻居节点分组，然后对每 组节点进行统一的接口卡和信道分配；基于冲突图的分布式信道分配方案主要通 过在链路冲突图中引入极大团的思想来解决信道分配问题。仿真实验结果表明在 无线m e s h 网络中采用多信道技术能够获得性能的提升，如果信道分配合理，更 7 中田科学技术大学硕士学位论文第l 章绪论 能获得非线性的性能提升。 针对路由度量问题，我们提出了一种适用于多信道无线m e s h 网络的路由度 量方法r m 3 ( r o u t i n gm e t r i cf o rm u l t i c h a n n e lw h e l e s sm e s hn e t w o r k s ) ，该方法不 仅考虑了路径的期望传输时间，更综合考虑了信道的多样性以及信道的切换开销 等因素。通过仿真实验表明，应用我们提出的路由度量方法的路由策略在大部份 情况下优于应用目前已经提出的路由度量方法的路由策略，尤其是在单节点配置 的网络接口卡数目小于可用的信道数目，网络接口卡需要频繁在多个信道之间切 换时，具有非常好的性能。 1 4 本文的结构安排 本章介绍了无线m e s h 网络概念、架构、特点和无线m e s h 网络中的一些关键 技术等。以下各章的结构安排如下； 第二章首先介绍了多信道无线m e s h 网络，包括多信道技术的必要性和多信 道的频谱支持等，然后重点介绍了多信道无线m e s h 网络中协议的研究现状，主 要包括多信道m a c 协议和多信道路由协议的研究现状。 第三章首先提出了信道分配问题，并对信道分配问题的复杂度进行了分析， 然后提出了两种信道分配方案，并对其正确性和性能进行了分析和仿真实验验 证。 第四章通过分析现有路由度量方法应用于多信道无线m e s h 网络的不足，提 出了一种新的适合多信道无线m e s h 网络的路由度量方法。 第五章总结了全文，并对今后进一步工作进行了展望。 8 中国科学技术大学硕士学位论文第2 章基于多信道的无线m e s h 网络研究 第2 章基于多信道的无线m e s h 网络研究 随着人们对i e e e8 0 2 1 1 等无线接入技术了解的深入，无线m e s h 网络已经 逐步成为企业界和消费者瞩目的焦点。无线m e s h 网络作为典型的多跳无线网络， 如何利用无线介质的共享特性来满足用户日益增长的带宽需求( 如实时音频、视 频下载等) ，是近年来研究的热点和难点所在。由于i e e e8 0 2 1la b g 等标准都 定义了不同数目的正交信道，利用这些正交信道可以同时发送数据包且不会相互 干扰。如果可以充分利用多信道的特点，就会减少节点间的冲突，提高无线m e s h 网络的容量。 ， 本章首先介绍了多信道无线m e s h 网络，包括为什么采用多信道技术，基于 多信道的无线m e s h 网络的模型等，然后重点研究了采用多信道技术给无线m e s h 网络中的m a c 协议和路由协议带来的全新挑战，最后是已有的一些典型多信道 m a c 协议和多信道路由协议介绍。 2 1 基于多信道的无线m e s h 网络 2 1 1 多信道技术的必要性 在宽带无线接入领域，随着多种无线通信技术的蓬勃发展，人们对网络带宽 的需求也与日俱增。现在越来越多的应用都需要高带宽的支持，对网络的容量提 出了新的需求。 但在目前i e e e8 0 2 1 1a g 标准中，5 4 m b p s 是链路层速率的上限。如果再除 去m a c 竞争开销、报文的头部开销以及传输错误等开销的话，实际的应用带宽 降低为理论速率的一半。由于链路之间干扰的存在，最大的链路层速率随着传输 双方距离的增大更会迅速下降。在使用i e e e8 0 2 1 l b a g 协议组成无线多跳网络 时，网络节点间在通信时由于存在冲突和干扰，降低了网络的吞吐量 2 9 】，由于 8 0 2 1 1 内在的介质访问协议的特性，在多跳的环境下，还会影响高层协议的性能， 比如导致t c p 协议的不公平性和不稳定性等【3 0 】。i e e e8 0 2 1 l b a g 等标准都定 义了不同数目的互不相交的信道，利用这些正交信道可以同时发送数据包而不会 相互干扰。如果可以充分利用多信道的特点，就会减少节点问冲突，提高无线 m e s h 网络的容量。 2 1 2 多信道的频谱支持 多信道的产生主要是通过划分可用频率频谱产生，所以可用信道的数目和每 9 。 中国科学技术大学硕士学位论文第2 章基于多信道的无线m e s h 网络研究 个信道分配的可用带宽主要就取决于可用的频谱总数。频谱分配一直是由美国的 联邦通信委员会f c c ( f e x l c r a lc o m m u n i c a t i o mc o m m i s s i o n ) 负责管理。目前大部 分低频率波段的频谱都已经被f c c 预留或者分配给了特权用户，像现在商用的 i e e e8 0 2 1 lw l a n 硬件主要运行在低频率频谱上面( 例如2 4g h z 和5g h z 频 谱、。所以，当前可用的信道数目主要取决于未被使用的频谱数。 近来，为了调整无线频率，f c c 于2 0 0 2 年6 月成立了“无线频谱政策任务 组( s p e c t r u mp o l i c yt a s kf o r c e ) ”。智能无线的工作方针即由该组织制定。在该方 针中使用被称为“认知无线电( c o g n i t i v er a d i o ) ”等多项技术，能够避开正在使 用的频道，动态地分配频率。f c c 在推进智能无线技术的同时还将放宽有关限 制。比如，利用率较低的频率的再出租，在人口密度低、不易产生无线干扰的地 区，放宽无线频率的使用条件等。这些都表明在不久的将来，将会有更多的低频 率波段的频谱能够使用。随着无线电技术的更新和发展，以前不适合于w l a n 的高频率段频谱现在也能够被使用。下图列出了现在一些可以利用的频谱，上面 部分主要是对全世界范围开放的工业、科技、医学( i s m ) 频率波段可用的频谱， 下面部分主要是高频率波段可用的频谱( 例如在6 0g h z 波段有将近7g h z 的可 用频谱【3 l 】) 。综上所述，无论是高频率段，还是低频率段，在不久的将来将会有 越来越多的频谱可供使用。 3c h a n n e l s8c h a n n e l s4c h a n n e l s 9 1 5m h z2 4 5g h z 5 2 5g h z5 8g h z 2 4 1 2 5g h z6 1 2 5g h z1 2 2 5g h z 图2 - 1 当前一些未被授权的可用频谱 目前，已有的无线技术可用的信道数目已经非常可观。例如，i e e e8 0 2 1 1 分别在5 ( 3 h z 和2 4g h z 波段提供1 2 个和5 个正交的信道。所以相对于主机的 网络接口卡数目，可用的信道数目还是相当巨大的。我们的研究也主要集中在主 机接口卡数目低于网络可用信道数目的基础上。 1 0 中国科学技术大学硕士学位论文第2 章基于多信遭的无线m e s h 同络研究 2 1 3 频谱的划分 将可用频谱划分为多个信道可以很好的和现有的i e e e8 0 2 1 l 技术相衔接 【3 2 。尤其是当可用的频谱非常大的时候，将其划分为多个信道不仅可以简化网 络接口卡的硬件设计，更可以降低m a c 协议的开销。但是如果一味的增加将频 谱划分为多个信道的数目也会得不偿失。因为为了确保两个信道之间不互相干 扰，在信道划分的时候，两个信道之间会有一个保护波段产生。随着信道划分数 目的增加，用于保护频谱的大小也是线性增加的，这将是一笔不小的开销。在实 际的应用中，能够最大化信道利用率的最优信道划分数目还和网络接口卡的性能 息息相关，当前的网络接口卡性能只能支持几个信道 3 2 1 。 2 1 4 信道和网络接口卡模型 本文中基于多信道的无线m e s h 网络采用如下的信道和网络接口卡模型【3 2 】： 首先我们假设网络中可用的信道数目为c ( 即c 个信道是正交的信道，所有信 道相互之间同时传输数据互相不干扰) 。在本文的研究中，为了便于分析，所有 的c 个信道都是同构的：即所有的信道都支持相同的数据传输速率和数据传输范 围。针对异构的信道，我们提供对最大传输范围和传输速率的参数设置，这样本 文的研究同样适用于信道异构的情况。然后我们假设每个主机中有肘个可用的 网络接口卡，针对每个主机装配不同数目网络接口卡的更一般情况，会在后面具 体的协议中进行分析。 每个网络接口卡在同一时间只能在一个信道上发送或者接受数据( 半双工操 作) 。每个网络接口卡在一定时间内可以切换到网络中的任何一个信道，切换花费 的时间记为切换延时s ，随着低层硬件技术的发展，这个延时在今后可能会忽略 不计。但在本为的研究中切换延时都是有考虑的，这样可以确保协议在网络接口 卡切换延时不同的情况下正常工作( 例如新技术带来的切换延时减小) 。 瓜 l h o s t 际 l 一 图2 _ 2n 信道m 网络接口卡模型 孕善 中匿科学技术大学硕士学位论文第2 章基于多信道的无线m e s