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

摘要 摘要 无线m e s h 网络由无线路由器和无线接入点通过多跳连接的方式组成，具有 传输速率较高、覆盖范围较广和组网成本较低等特点，是解决无线终端接入 i i l t e m e t 的一种比较有竞争力的技术方案。无线链路的传输速率因链路干扰问题 而降低，目前降低干扰的种有效方法是采用正交信道传输数据，在8 0 2 1 l 删g 等标准中定义了不同数目的正交信道，研究如何有效利用正交信道提高网络吞 吐率具有十分重要的意义。 本文基于i e e e8 0 2 1 lm a c 协议，围绕如何提高无线m e s h 网络吞吐率这一 问题，开展了以下研究工作： 针对目前已有的集中式静态信道分配算法在大规模无线m e s h 网络中存在 的可扩放性问题，提出了基于链路负载信息的分布式信道分配算法l l d c a 算法。该算法通过分布式构建链路冲突图，使同一冲突域内数据传输量较大的 链路优先选择干扰程度较低的信道，互不干扰的链路间能够并行选择信道，从 而较大降低了链路分配所需要的轮数。理论分析表明，对任意给定的正整数f ， 该算法在d ( 1 0 9 ，1 ) + f + 1 轮内结束的概率大于1 一( 叫j d + 1 ) “- ，其中一为网络中数据传 输量大于o 的链路数目，d 为链路冲突图的最大顶点度；各链路的消息复杂度 为d ( d ) 。模拟实验表明该分布式算法的性能与i i w a l a 等人提出的集中式分配 算法的性能相当，与g r o u pc a 算法相比较能够将网络吞吐率提升3 倍左右。 针对目前缺少统一的静态信道分配算法性能评价标准的问题，提出了基于 “冲突链路带宽占用率”的性能评价模型，通过计算同一冲突域中每条链路所在 信道的带宽占用率，量化了信道分配结果对每条链路的影响，该模型能够较好 评价各种静态信道分配算法的性能。基于该评价模型，提出了使用“网络拓扑控 制”策略优化静态信道分配的算法，根据“冲突链路带宽占用率”的计算结果判断 是否使用当前已有链路传输待分配链路的数据。模拟实验表明在网络中同时存 在数据传输量较大和较小的链路时，该方法能够利用更多的正交信道，使网络 吞吐率在l l d c a 算法的基础上再提升1 0 以上。 针对混合式无线m e s h 网络中因少量节点在信道切换时存在较多冲突而影 响传输速率的问题，提出了分布式信道切换序列生成算法叫c s 算法。r c s 算法采用随机景换策略生成新的切换序列，从而较好的分散了节点间的传输冲 突，均衡了各节点的有效传输带宽。在r c s 算法中，各网络节点的信道切换序 列独立生成，有利于节点的动态加入和离开，其运行时间与正交信道的数目成 线性关系，保证了信道切换序列生成的实时性。仿真实验表明，在网络负载程 摘要 度达到7 5 以上时，该算法与当前同类算法相比能够将网络节点获得的有效带 宽最小值提升3 0 以上，网络总吞吐率提升5 1 5 。 针对目前基于混合式策略的信道分配算法未考虑各节点数据传输量差异从 而导致信道负载不均的问题，提出了负载平衡的分布式信道分配算法 l b c a 。通过分布式构建节点局部冲突图，使处于同一冲突域中数据传输 量较多的节点优先选择负载较小的信道，从而较好平衡了各信道负载。模拟实 验表明，在网络负载程度达到8 0 以上时，对可用信道数目不大于6 的网络， l b c a 算法获得的网络吞吐率与当前相关算法相比提升了l o 以上。 针对当前多信道路由度量标准在网络中数据流的数量较少时，不能够充分利 用网络的可选路径和信道资源问题，提出了一种基于“跨层设计”的按需路由和 信道分配算法。该算法综合考虑路由问题与信道分配问题，首先利用目前已有 的多信道路由度量标准使用按需路由策略寻找最小传输时延路径，然后为该路 径上的相邻链路尽量分配互不相同的信道，从而降低了路径上相邻链路间的干 扰，提高了网络吞吐率。模拟实验表明，在信道数目为1 2 且“源节点”和“目的 节点”总数量占网络总节点数的比例小于5 0 时，该算法与当前同类型算法相 比，能够将网络吞吐率提升l o 2 0 。 针对当前的无线m e s h 网络结构难以有效解决在网络中存在大量网内和网间 数据流时的数据有效传输问题，提出了一种新型的混合式无线m e s h 网络结构。 在该结构中，根据节点距离固定网络接入点的距离，将网络划分为静态m e s h 区域和动态m e s h 区域；并基于该网络结构提出了一种新型的路由算法，采用将 反应式路由协议和先验式路由协议相结合的方法，较好解决了在网络中同时存 在上述两种数据流时的数据有效传输问题。模拟实验表明，在信道数目为1 2 并 且访问固定网络产生的数据流占网络总数据流量的6 0 8 0 时，与当前已有的 m e s h 结构相比，该新型m e s h 结构能够将网络吞吐率提升1 5 以上。 关键词：无线m e s h 网络：多接口多信道；信道分配：链路调度；按需路由： 冲突图；随机置换：混合式分配 a b s t r a c t 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 sa r ec o m p r i s e do fan u m b e ro f 、i r e l e s sr o m e r sa j l d 谢r e l e s sa c c e s sp o i n t sw h i c ha r ec o r m e c t e dt oe a c ho t h e ri nam u l t i - h o pm a n n e r i t h a se m e r g e da so n eo ft h ep r o m i s i n gs o l u t i o n sf o rn e x tg e n e r a t i o n 谢r e l e s sn e t w o r k s b e c a u s ei tc o u l dp r o v i d el l i g h - s p e e dd a t ar a t e ，e n l a 唱ew i r e l e s ss e r v i c ec o v e r a g ea l r e a a n dr e d u c et h en e t 、v o r ki n s t a i l a t i o nc o s t t h et r a n s f e rr a t eo fw i r e l e s sl i n k sc o u l db e d e c r e a l s e db yi n t e r f e r e n c e ，s ou s i n gn o n o v e r l a p p e dc h 猢e l sf o rd a t at r a n s 佗ri s a 1 1 e 所c i e n tw a yt ol e s s e nl i n ki n t e r f e r e n c e d i f - f e r e n tn u r n b e r so fn o n o v e r l a p p e l = l c h 蛐e l sa r ed e f i n e di 1 1i e e e8 0 2 11a 厂b 儋s t a n d a r d sa n dt h en e t w o r kt h r o u 曲p u t c o u i db ei n c r e a s e de f r e c t i v e l yb yu t i l j z i n gt h o s ec h a n n e l s r e s e a r c ho nh o wt o i n c r e a s et h et h r o u 曲p u to fw i r e l e s sm e s hn e t w o r ki so f 伊e a ts i g n i f i c a n c e b 2 l s e do ni e e e8 0 2 1lm a cp r o t o c o l ，t h er e s e a r c hw o r kp r e s e n t e di nt h i s d i s s e n a t i o ni sm a i l l l yf o c u s e do nh o wt oi m p r o v et h et h r o u g h p u t so fw i r e l e s sm e s h n e t w o r k s f i r s t l y ，c o n s i d e r i n gt h ep r o b l e mt h a tc u r r e n tc e n t r a lc h a r m e la l g o r i t h m sh a v et h e s c a l a b i l i t yp r o b l e mi nl a 喀es c 削ew i r e 】e s sm e s hn e t w o r k s ，an e wl j n k l o a db a s e d d 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 ( l l d c a ) w a s p r o p o s e dt oa s s i g nc h a n n e i s t ol i n k s t h i sa l g o r i t l u l lc o n s t r u c t e d “d kc o n f l i c tg r a p hf i r s t l yi nd i s t r i b u t e dw a y b y e x c h a n g i n gt h el o c a l l i n ki o a di n f o m a t i o nw i t h i ni t sk - h o pn e i g h b o r si nt h ew i r e l e s s n e t 、v o r ka 1 1 dt h e na s s i g n e dc h a l m e l st ol i n k sa c c o r d i n gt ot h el i n kl o a dp r i o r i t i e si n j i m 【c o n n i c tg r 印h l i n k st h a td i dn o ti n t e r f e r e n c ew i t he a c ho t h e rc o u l ds e l e c t c h 锄e l sc o n c u r r e n t l y ；s ot h en m i n gr o u n d so fl l d c a h a db e e ns i g n i f i c a n t l y r e d u c e d t h e o r e t i c a la n a l y s i ss h o w st h a tf o ra n yg i v e np o s i t i v ei n t e g e r 己l l d c a c o u l df i n i s hi 1 1 d ( 1 0 9 m + f + lr 0 岫d s w j t h p r o b a b i j i t yh i g h e r t h a n 卜( 驯d + 1 ) 卜1 、v h e r e 丹i st h en 啪b e ro fj i n k sw h o s el o a d sa r ep o s i t i v en u m b e ri nt h e n e t w o r ka 1 1 ddi st h em a x i m u mn o d ed e g r e ei nt h el i n kc o n f l i c t g r a p h ，a n dt h e m e s s a g ec o m p l e x i t yo fe v e r yl i n ki nt h i sa l g o r i t h mi sd ( d ) s i m u l a t i o nr e s u l t ss h o w t h a tt h i sd i s t r i b u t e da l g o r i t h mh a sn e a r l yt h es a m ep e r f o r m a n c e a l st h ec e n t r a l c h 锄e ia l s s i g m n e n ta l g o r i t h m p r o p o s e db ya s h i s hr a n i w a l ae ta la n di tc o u l d i m p r o v et h en e t w o r kt h r o u g h p u tb yaf - a c t o ro ft h r e ew h e nc o m p a r i n gw i t hg r o u p c a a l g o r i n u n s e c o n d l y ， an e wp e r f o r m a n c e e v a l u a t i o nm o d e lf o rc h 锄e la s s ig 姗e n t a l g o r i t h m sw a sp r o p o s e db a l s e do n “c o n n i c tl i n kb a n d w i d t ho c c u d a t i o nr a t e ”t h e a b s t r a c t i m p a c to fc h a n n e la s s i g n m e n tr e s u l t0 ne a c hl i n kw a sq u a n t i f i e db yc o m p u t i n gt h e c h a n n e lb a n d w i d t ho c c u p a t i o nr a t eo f e a c hl i n ki ni t sc o n n i c ta r e a t 1 1 i sm o d e lc o u l d e v a l u a t et h ep e r f - o r m a n c eo fd i f f e r e n tc h a n n e la s s i g m e n ta l g o r i t 上u i l s ，b a s e do nt h i s e v a l u a t i o nm o d e l ，an e w 甜g o r i t l u nw a sp r o p o s e dt oi m p r o v et h es t a t i cc h a 衄e l a s s i g m e n ta l g o r i t sb yu s i n gt o p o l o g yc o n t r o ls t r a t e g y ad e c i s i o nw a sm a d eb y u s i n gm i sm o d e lb e f o r ea s s j g n i n gac h 枷e lt oal i n k s i m u l a t i o nr e s u l t ss h o wt h a t t h i sa l g o r i t h mc o u l di m p r o v et h en e t w o r kt h o u g h p u tb yaf a c t o ro f1o t h a n l l d c aw h e nt h en e t w o r kc o n s i s t so fh e a v y i o a da n dl i g h t l o a dl i n k sa tt h es 锄e t i m e t h i r d l y ，c o n s i d e r i n gt h ep r o b l e mt h a tt h et r a n s f e rr a t e so fs o m en o d e sm a yb e d e c r e a s e dd u et ot h e i rc h a n n e ls w i t c h i n gs e q u e n c e sb e i n gp l e n t yo fc o l l i s i o n sw i t h t h a to ft h e i rn e i g h b o r s ，ad i s t r i b u t e da l g o r i t h n lw a sp r o p o s e dt og e n e r a i ec h a n n e l s w i t c h i n gs e q u e n c e si nh y b r i dm e s hn e t w o r k s an e ws e q u e n c ew a sg e n e r a t e di n e a c hr o u n du s i n gr a n d o mp e r m u t a t i o nm e t h o da c c o r d i n gt ot h en o d e sc u r r e n t s w i t c h i n gs e q u e n c e a n di td i s t r i b u t e dt h es e n d i n gc o i li s i o n s a m o n gd i 腩r e n t n o d e p a i r s ，s ot h eu s e m lb a n d w i d t ho fe v e r yn o d ew a se f l f e c t i v e l yb a l a n c e d e v e r y n o d eg e n e r a t e sn e ws e q u e n c e si n d e p e n d e n t l yw i t h o u ta n yn e g o t i a t i o nw i hi t s n e i g h b o f s t h i sa l g o r i t h mi si n s e n s i t i v et 0t o p o l o g yc h a n g e ，s oi ti sc o n v e n i e n tf o r n o d e st oj o i nq rl e a v et h en e t w o r kd y n a i l l i c a n y t h ea l g o r i t h m s1 1 】n n i n gt i m ei s m l e a u rt ot h en u m b e ro fo n h o g o n a lc h a 衄e l si nt h en e t w o r k ，s oar e a l t i m en e w s e q u e n c eg e n e r a t i o ni sg u a r a n t e e d e x p e r i m e n t a lr e s u l t ss h o wt h a tt h i sa l g o r i t h m c o u l de f _ f e c t i v e l yi m p r o v et h en o d e sm i n i m u mu s e f u lb a n d w i d t hb yaf a c t o ro fm o r e t h a n3 0 a j l di m p r o v et h en e t w o r kt o t a l t h r o u g h p u tb yaf a c t o ro f5 15 w h e n t h en e t w o r kl o a di n c r e a s e st o7 5 o fi t sc a p a c i t y f o u r t h l y ，b yu t i l i z i n gt h e1 0 a di n f o r m a t i o no fm e s hn o d e si nh y b r i dc h a r l n e l a s s i g n m e n ts t f a t e g y ， al o a d b a i a n c e dd i s t r i b u t e dc h a n n e ia s s i g n m e n ta l g o r i t h i i l ( l b c a ) 、v a sp r o p o s e di nt h i sp a p e r al o c a ln o d ec o n n i c tg r a p hw a sc o n s t r u c t e di na d i s t r i b u t e dw a ya n dl h o s eh e a v yl o a d e dn o d e sw e r ea s s i g n e dt ol i g h tl o a d e dc h a n n e l s b yl b c aa l g o r i t h m i nt h i sw a y ，t h el o a d so fe v e r ) rc h a n n e l 、阮r eb a l a n c e d s i m u l a t i o nr e s u l t ss h o wt h a tm en e t w o r kt h r o u g h p u tc o u l db ei m p r o v e db yaf a c t o r 0 fa b o v e10 t h a j lt h a to fs t a t e o f 二a r ta 1 9 0 t h m si nm e s hn e t w o r k sw i t hn om o r e m a n6c h a n n e l sv m e nt h en e t w o r k1 0 a di n c r e a s e st o8 0 o fi t sc a p a c i t y f i r h l y ， an e wj o i n t r o u t i n g a n dc h a n n e l a s s i g n m e n ta i g o r i t h mu s i n g “c r o s s l a y e r m e t h o dw a sp r o p o s e dt oo p t i m i z et h en e t w o r kp e r f o r m a n c ew h e nt h e a b s t r a c t n u m b e ro fn o w smm en e t w o r kw a sn o tl a r g e t h es h o r t e s tp a t hw a sd i s c o v e r e d f i r s t l yl l s i i 唱t h ec u r r e n ta v a i l a b l er o m i n gm e 埘c sa 1 1 dt h e nn e wd i f l e r e n tc h a 肌e l s w e r e 2 l s s i g n e dt o t h o s el i n k s i nm i s 、a y t h ei n t e r f e r e n c eo nt h a t p a t hw a s m i n i m i z e da n dt h et r a n s f e rr a t ew a si n c r e a s e d s i m u l a t i o nr e s u l t ss h o wm a tt h j s 越g o r i t h mc o u l di m p r 。v e 搬e n e t 、v o r k 虹o u g h p u tb y af a c t o ro flo 2 0 c o m p a r i n gw i t ho t h e rs t a t e - o f a na l g o r i t h m sw h e nt h ep e r c e n t a g eo ft h es u m m a t i o n o fs o u i ea n dd e s t i n a t i o nn o d e si sn om o t t h a n5 0 f i n a l l y an e wn e t w o r kt o p o i o g yf o ro 唱a u l i z i n gw i r e i e s sm e s hn e t w o r kw a s p r o p o s e dt oi m p r o v et h en e t w o r kt h r o u 曲p u tw h e nt h en e t w o r kc o n t a i n sm a s s i v e i n t r a i m e s ha n di n t e r - m e s hf l o w ss i m u l t a n e o u s l y 7 r h en e t w o r kw a sd i v i d e di n t ot w o p a n s ：t h es t a t i cm e s hz o n ei nw h i c hc h a n n e l sw e r ea s s i g n e dt om e s hn o d e ss t a t i c a l l y a n d 硅【ed y n a m i cm e s hz o n ei nw h i c ht h ec h a n n e la s s i g n m e n ts t r a t e g yw a sh y b r i d a s s i g r n e n tm e t h o d an e wr o u t i n ga l g o r i t i m lw a sa l s op r o p o s e df o rt h en e wn e t w o r k t o p o l o g yo r g a n i z a t i o nb yc o m b i n i n gp r o a c t i v ea n dr e a c t i v ep r o t o c o l s ，s i m u l a t i o n r e s u l t ss h o wt h a tt 1 1 en e t w o r kt h r o u 曲p u tc o u l db ei m p r o v e db yaf a c t o ro f15 a b o v ec o m p 撕n g 州t ht r e et o p o l o g ya n dh y b r i dt 叩o l o g y 、v h e nt h ec h 姗e 1n 啪b e r o ft h en e t w o r ki s12a n dt h e 锄o u n to fi m e r - n o wi so f6 0 一8 0 o ft h et o t a l n e t 、v o r kf l o w1 0 a d k e yw o r d s ：w i r e l e s sm e s hn e t w o r k s ， m u l t i - i n t e r f a c em u l t i c h 锄l e l ， c h a n n e l a s s i g n m e 嫩， “n ks c h e d u l e ，o n - d e m a n dr o 试i n g ，c o n b i c t 鲈a p h ， r a n d o mp e 咖u t a t i o n ，h y b r i dc h 猢e la s s i g 啪e n t i i i 论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工 作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包 含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对 本研究所做的贡献均己在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 保密的学位论文在解密后也遵守此规定。 作者签名：芏圭重 硼年，月7 日 第一章绪论 第一章绪论 无线m e s h 网络由无线路由器和无线接入点通过多跳连接的方式组成，是无 线终端接入i n t e m e t 的一种比较有竞争力的解决方案【2 】。由于无线信号的扩散 特性，使得相近链路间存在干扰问题，从而降低了链路的传输速率【3 】。目前采用 正交信道是降低干扰的一种有效方法，在8 0 2 1 l 怕g 【4 j 等标准中定义了不同数目 的正交信道，研究者提出了基于多接口多信道( m u l t i r a d i o ，m u l t i c h a l l l l e l ) 的 无线m e s h 结构【5 】1 6 】。鉴于目前网络本身的成本问题，网络节点配置的接口卡数 目通常会少于正交信道的数目( 比如8 0 2 11 a 能够提供1 2 个正交信道，节点接口 卡的数目一般为2 3 个【5 1 ) ，若各节点采用相同的信道分配方式，则难以充分利 用网络所拥有的正交信道【5 】；传统a d h o c 网络普遍采用多跳路由协议【7 】【8 】，该类 协议主要以节点间的最小跳数作为路径选择依据，不能准确反映无线链路的传 输特点，因此需要研究适合于无线m e s h 网络的信道分配和路由算法，从而降低 无线链路间的干扰，提高无线m e s h 网络吞吐率。 本章首先对无线m e s h 网络进行概述，然后介绍无线m e s h 网络中的一些关 键技术，最后给出本论文的研究内容和组织结构。 1 1 无线m e s h 网络概述 无线m e s h 网络( 无线网状网) 是一种无线多跳网络，具有数据传输速率较 高、部署成本较低和自组织等特点，因此成为无线终端接入i n t e m e t 的一种比较 有竞争力的技术方案【ij 【2 】，引起了学术界【9 、工业界【2 j 【1 3 i 和相关标准化组织【h j 的重视。在传统的w l a n 体系结构中【4 1 ，无线用户通过单跳方式连接到无线接 入点( a c c e s sp o i m ，简称a p ) ，a p 通过有线链路连接到i n t e m e t 或其它a p ， 限制了a p 能够提供的无线接入范围。无线m e s h 网络技术结合了、。a n 技术 和无线自组网( a dh o c 网) 技术【l 】的优点，利用无线路由器将无线接入点以及 其它流量汇集设备通过无线多跳的方式连接起来，从而扩大了无线网络的覆盖 范围，为无线用户提供更加便捷的i n t e m e t 接入服务。无线m e s h 网络的系统架 构如图1 1 所示，主要包括由无线路由器和无线接入点通过多跳连接方式组成的 无线m e s h 骨干网和由无线终端设备形成的自组织网络【1 】【”，无线终端设备可以 直接连接到a p ，也可通过多跳方式接入a p ，a p 之间通过无线路由器连接，并 最终到达具有网关功能的无线路由器，该类型路由器具有接入固定网络或其它 外部网络的能力。 第一章绪论 无线m e s h 网络与传统的无线网络相比，可以为更大范围内的用户提供无 线信号覆盖，采用多跳的连接方式使得无线链路间的距离变短，从而降低了 m e s h 节点的发射功率，提高了无线链路的传输速率；无线m e s h 路由器的移动 性很低，具有较强的计算和通信能力，有持续的电力供应，不需要考虑路由设 备的节能问题，因此由无线m e s h 路由器构成的骨干网具有较好的稳定性和健壮 性，能够为用户提供持续、可靠的接入服务；带网关功能的无线m e s h 路由器不 但可以为用户提供固定网络接入服务，而且可以通过桥接转换设备与蜂窝网、 w i m a x 网【1 5 j 、z i g b e e l l 6 j 网等其它类型的网络进行通信。 f “i ，蕊营嚣 奠竹暇岛嚣每西j 袋井勰 前嵇簪景 ，一一一5 ；：葛孑一 _ 謦ji 鬻：名划 出一一一一j 茹妻 j、 鬣j _ j 、，二、 图1 1 无线m e s h 网络的系统架构 无线m e s h 网络具有较高的传输速率、较广的覆盖范围和较低的组网成本， 在企业网络、社区网络和校园网络等多种场合下有着广阔的应用前景【| j 【1 7 】，无 线m e s h 网络可以为办公楼内部提供无缝的信号覆盖，可以将企业厂区通过无线 链路连接在一起，为实现办公、生产自动化提供有效的网络接入支持；在社区 中使用无线m e s h 网络，可以使若干用户共享台i n t e m e t 接入设备( 比如a d s l 接入设备) ，为用户节省了接入成本，也方便了社区内部的网络资源共享；在 学校内部，无线m e s h 网络能够为学生和老师提供随时随地的网络接入服务。无 线m e s h 网络已经具有很多实际的应用案例，例如，在2 0 0 6 年，思科连同i b m 、 s e a k a y 和a z u l s t a rn e t 、o r k s 共同赢得了美国加州硅谷地区的无线m e s h 网络建 设项目【1 8 】【19 1 ，在总面积超过3 9 0 0 平方公里的土地上，宽带无线m e s h 网络将为 第一章绪论 2 4 0 万居民提供无处不在的无线网络接入服务。 1 2 无线m e s h 网络关键技术 无线链路传输存在信号衰落、多径干扰、同信道干扰等问题【2 0 】【2 l 】，从而降 低了无线链路的传输速率，为了使无线m e s h 网络能够为用户提供更好的网络接 入服务，需要对无线m e s h 网络的关键技术进行研究，从而提高网络吞吐率，这 些技术因素包括如下几个部分： ( 1 ) 物理层传输技术 无线链路物理传输速率的增加能够直接提升系统的传输性能，多输入多输 出( m i m o ) 技术【2 2 必】利用无线信号多径传输的特点，在多对收发天线间构建独立 子信道进行数据传输，发送端的多个天线同时将不同的无线信号输出，而接收 端的多个天线分别接收信号，然后对其作解码合成处理，在信道相关性较低的 情况下，信道容量随天线数量近似线性增长，在实际测试中，m i m o 技术的频 谱效率可以达到2 0 4 0 b p s h z ，8 0 2 1i 定义一个频道占用2 2 m h z 频带，也就是 说m i m o 最高速度的理论值可达4 0 0 m p s ，极大提高了无线链路的传输速度： 波束成形技术( b e a m f 0 咖i n g ) 2 5 】【2 6 j 分为自适应波束成形、固定波束和切换波束成 形技术，可以有效降低相干噪声信号的影响，提高阵列输出的信噪比：超宽带 ( u 、) 技术【z 7 】共享其它无线技术的频带，通过发送纳秒级脉冲来传输数据信 号，u w b 信号的传输范围为1 0 m 以内，其传输速率可达5 0 0 m b i 珧，是实现个 人通信和无线局域网通信的一种理想调制技术：智能天线技术1 2 引、认知无线电 技术f 2 9 】和软件无线电【3 0 】等技术也已应用于无线传输，降低了链路的传输干扰， 提高了频谱的利用效率；物理层编码技术【3 l 】利用无线信道的广播特性通过对无 线信号的编解码减少数据包的传输个数，提升了数据的传输速率。这些新型通 信技术的出现，大大增加了无线链路的带宽，而早期制定的部分网络协议和规 范不能很好的适应物理层通信技术的发展，因此，需要设计新的协议和规范 【3 2 】【3 3 】。 ( 2 ) 链路层传输协议 传统的i e e e8 0 2 1l c 协议使用r t s c t s 传输机制和二进制退避算法l 训， 不能够很好的适应无线多跳网络的特点【3 4 】【3 5 】，在多跳数据传输中，由于相近链 路间存在干扰，8 0 2 1l 的传输机制会较大降低系统的传输速率【2 ，此外，8 0 2 ，11 m a c 协议是单信道m a c 协议，而在8 0 2 1 1 加g 标准【4 】中提供了不同数目的正 交信道，因此需要对m a c 机制进行研究，使其能够有效利用网络提供的多信 道资源【3 6 1 。在每个节点仅配置一块网络接口卡时，多信道的利用需要通过修改 第一章绪论 m a c 层协议【”】【3 引，在节点配置有多块接口卡时，可以保持当前的8 0 2 ，1 1m a c 协议不变，通过增强链路控制子层的功能利用多信道【5 】【3 9 1 【4 0 1 。信道分配问题是 多信道利用的关键问题陋j ，有效的信道分配算法能够降低相近链路间的干扰， 增加并发传输的链路数目；多信道网络中的链路调度问题是m a c 传输机制研 究中的另一个关键问题【4 ，有效的链路调度算法能够降低同信道链路间的传输 干扰，提升无线m e s h 网络的传输性能。 ( 3 ) 网络层路由协议 由于无线m e s h 网络中节点间的传输链路是无线链路，因此节点间通常存在 多条传输路径，各条链路的传输距离和所处环境不同，导致每条链路的传输质 量存在差异1 4 2 j ，选择不同的传输路径会直接影响节点问的传输速率，因此路由 度量问题是网络层路由协议中的一个关键问题。在无线m e s h 网络中，路由度量 标准不能仅依据节点间的最小跳数【4 2 1 ，而需要综合考虑无线m e s h 网络的传输特 点，包括链路的传输质量差异【6 l 【4 2 1 、路径的多信道利用情况【6 】【4 3 】和链路的数据传 输量和干扰情况p 】等，从而为通信节点间选择传输速率较高的路径。为充分利用 无线链路资源，路由协议需要具有定的负载平衡能力】【4 5 】，避免因少量链路 的数据传输量过大而导致系统传输性能下降的问题。 “) 无线网络容量的研究 无线网络的容量研究具有重要的理论意义，能够为无线网络的算法设计和 性能评估提供指导【4 l 】。g u p t a 和k 啪a r 【4 6 】研究了无线多跳网络的容量问题，给 出了网络吞吐率、链路传输带宽和节点数目之间的关系，为无线网络容量的研 究工作奠定了基础。j a i n p j 研究了链路干扰问题对无线多跳网络传输性能的影 响，使用线性规划方法给出了估计网络吞吐率上界和下界的算法，k o d i a l 锄和 n a n d a g o p a l l 【4 1 】f 4 7 】研究了在给定多对( 源节点，目的节点) 通信需求情况下的网络吞 吐率问题，给出了网络吞吐率的上界和一个可以达到的下界，该问题类似于固 定网络中的多商品流问题【4 8 儿4 9 l ，但与固定网络不同，相互干扰的无线链路不能 够同时发送数据，因此在求解无线多跳网络的吞吐率时，需要联合考虑路由和 调度问题。k y a s a n u r 和v a i d y a 【5 0 】研究了多接口多信道网络的容量问题，给出了 网络吞吐率与网络信道数目、接口卡数目、链路传输带宽、网络节点数目之间 的关系。目前无线m e s h 网络容量研究主要集中于对网络容量上界和下界的估 计，其上界估计值与下界估计值仍相差较大，因此需要研究更精确的无线m e s h 网络容量计算方法。 4 第一章绪论 1 3 本文研究内容和研究思路 无线m e s h 网络传输速率的提升能够为无线用户提供更好的无线接入服务， 而多信道分配算法、路由算法和链路调度等算法对无线m e s h 网络的链路传输速 率有重要影响，本文基于当前的i e e e8 0 2 1 1 m a c 协议【4 】，研究多接口多信道 无线m e s h 网络中的信道分配、路由和链路调度，我们将研究如下几个问题： ( 1 ) 分布式静态信道分配问题 在接口卡切换时延较大的情况下，静态信道分配策略是目前种较好的解 决方案，各网络接口卡的信道分配策略对降低链路干扰、提高传输速率有重要 影响。 本文首先针对目前已有的集中式静态分配算法【5 】【50 1 在大规模无线m e s h 网络 中存在的可扩放性问题，提出基于链路负载信息的分布式静态信道分配算法 一i ，i ，d c a 算法。该算法首先通过分布式方法构建网络的链路冲突图，然后各 节点根据其局部链路冲突图信息，根据各链路的数据传输量进行信道选择，在 同一冲突域内数据量较大的链路优先选择干扰程度低的信道，互不干扰的链路 间能够并发的选择信道，从而较大降低链路分配所需要的轮数。理论分析表明， 对任意给定的正整数f ，该算法在优1 0 9 刀) + f + l 轮内结束的概率大于l 一( 纠d + 旷， 其中以为网络中数据传输量大于o 的链路数目，d 为链路冲突图的最大顶点度， 各链路的消息复杂度为伙d ) ；模拟实验表明该分布式算法的性能与i 协i 、v a l a 等 人提出的集中式分配算法【5 j 的性能相当，与u pc a 算法【5 】相比较能够将网络 吞吐率提升3 倍左右。 其次针对当前信道分配算法的性能评价方法主要是采用模拟实验而缺少统 一评价标准的问题，提出基于“冲突链路带宽占用率”的静态信道分配算法性能 评价模型，通过计算网络中每条链路所在信道的数据传输量，量化在同一冲突 域中各链路能够获得的传输速率，反映信道分配结果对每条链路的影响，该模 型能够较好的评价各种静