（信息与通信工程专业论文）提高无线mesh网服务质量的队列管理和调度研究.pdf

原创性声明 l i i i i ii1i i l , l l ll li ii iiil y 1719 6 7 7 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名：f 塑望日期：鱼止年月量日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 日期：五垒望翌年盖眨日 摘要 无线m e s hn ( w m n ) 是一种大容量、高速率、多跳性的分布式网 络，具有融合现有多种无线网络的功能，承载业务的多样性使得 w m n 的服务质量保证较其它网络更加困难，而节点间数据流的公平 调度能够很好的解决网络用户服务质量保证的问题。因此，本文在分 析w m n 中节点内和节点间数据流调度的基础上，针对其公平性欠 缺、吞吐量不高等问题，提出了相应的解决方案。 首先，提出一种自适应超时检测模型对缓存队列中数据包进行管 理，解决网络中基于位置的相关竞争造成节点内自身流、中继流的缓 存争用问题。通过设计适用于无线多跳网络的缓存队列门限值和丢包 率函数，对到达节点的数据包进行超时估算；在估算结果的基础上， 采用信道预测因子对信道状态进行实时监测以便调整队列丢包率，根 据节点发送速率的变化调整队列门限值大小；同时设计一种选择性丢 包策略作为缓存队列的丢包方法，在保证节点队列长度的前提下，依 据跳数对进入缓存队列的数据包进行选择，以此来降低中继流被丢弃 的概率。 其次，针对传统m a c 层中二进制指数退避机制在节点间信道分 配不公问题，提出一种分期协同调度的公平队列算法。通过建立分期 协同调度模型，将节点数据传输过程分解为发送、补偿、休眠三个时 期，根据模型参数设计时限约束函数，限定各时期的执行时间长度； 其中，发送期对节点本身数据包进行传输，补偿期设计种补偿流队 列执行对其它节点的资源补偿操作，休眠期放弃对信道的使用，将发 送权限转交给其它节点；各节点按照模型设定的协同调度规则，共同 完成整个网络数据包的公平传输。 最后，利用n s 2 网络仿真工具对节点的吞吐量、丢包率、缓存队 列长度、公平性等进行性能评估，验证所提出的自适应超时检测模型 和公平队列算法的有效性。 关键词无线m e s h 网，公平调度，队列管理，公平队列 a bs t r a c t w i r e l e s sm e s hn e t w o r k ( w m n ) i saw i r e l e s sd i s t r i b u t e dn e t w o r kw i t h l a r g ec a p a c i t y , h i g hs p e e da n dm u l t i h o p ，w h i c hp l a yi m p o r t a n tr o l ei n i n t e g r a t i o no fv a r i o u se x i s t i n gw i r e l e s sn e t w o r k h o w e v e r , t h ed i v e r s i t y o fs e r v i c e sm a k e sq u a l i t yo fs e r v i c ei nw m nm o r ed i 衔c u l t yt h a no t h e r n e t w o r k s f a i rs c h e d u l i n go fd a t as t r e a m sa m o n gn o d e si sa ne s s e n t i a l t e c h n i q u ei ne n s u r i n gt h eq u a l i t yo fs e r v i c ef o rn e t w o r ku s e r s i no r d e rt o u s et h el i m i t e d 仆仆tn e t w o r kr e s o u r c e sf a i r l ya n de f f i c i e n t l y , d a t af l o w s s c h e d u l i n gi na n db e t w e e nt h en o d e sa r es t u d i e di nt h i st h e s i s f i r s t l y , a na d a p t i v eo v e r t i m ed e t e c t i o nm o d e l ( a o d m ) i sp r o p o s e d t os o l v eb u f r e rc o n t e n t i o np r o b l e mo fs e l f - f l o wa n dr e l a y f l o wi nn o d e s c a u s e db yr e l a t e dl o c a t i o n b a s e dc o m p e t i t i o n ，a n dm a n a g et h ep a c k e t si n t h eb u f f e rq u e u e s b yd e s i g n i n gt h et h r e s h o l da n dp a c k e tl o s sf u n c t i o no f b u f i f e rq u e u ew h i c ha r es u i t a b l ef o rw i r e l e s sm u l t i h o pn e t w o r k ，p a c k e t s r e a c h i n gt h en o d ea r et i m e o u te s t i m a t e d b a s e do ne s t i m a t i n gr e s u l t s ，t h e c h a n n e ls t a t ei sm o n i t o r e di nr e a lt i m eb yu s i n gt h ec h a n n e lp r e d i c t i o n f a c t o rt oa d iu s tt h ep a c k e tl o s sr a t e a n dt h ev a l u eo ft h et h r e s h o l di s a d i u s t e da c c o r d i n g t o c h a n g e s o ft h en o d e st r a n s m i s s i o nr a t e f u r t h e r m o r e ，as e l e c t i v ep a c k e tl o s ss t r a t e g yi sd e s i g n e da sp a c k e tl o s s m e t h o do fb u f f e rq u e u e i nt h ep r e m i s eo fg u a r a n t e e i n gq u e u el e n g t ho f n o d e ，t h em o d e ls e l e c t sp a c k e ti n t ob u f f e rq u e u ea c c o r d i n gt oh o pi n o r d e rt or e d u c et h ed r o p p i n gp r o b a b i li t yo fr e l a y f l o w s e c o n d l y , a ni n s t a l l m e n t c o o r d i n a t i o n s c h e d u l i n g b a s e d f a i r q u e u i n ga l g o r i t h m ( i cs f q ) i sp r o p o s e dc o n s i d e r i n gs u c hp r o b l e m sa s u n f a i rc h a n n e la l l o c a t i o na m o n gn o d e si nb i n a r ye x p o n e n t i a lb a c k o f f m e c h a n i s mo ft r a d i t i o n a lm a cl a y e r t h r o u g ht h ee s t a b l i s h m e n to f i n s t a l l m e n tc o o r d i n a t i o n s c h e d u l i n gm o d e l ，d a t ac o m m u n i c a t i o np r o c e s s o fn o d e si sd i v i d e di n t ot h r e e p e r i o d s ，n a m e l y , s e n d i n gs t a g e ， c o m p e n s a t i o ns t a g ea n dd o r m a n c ys t a g e a c c o r d i n gt om o d e lp a r a m e t e r s ， t i m ec o n s t r a i n tf u n c t i o n sa r ed e s i g n e dt ol i m i tt h ee x e c u t i o nt i m el e n g t h o fe a c hp e r i o d t h et r a n s m i s s i o no fp a c k e t so ft h en o d ei t s e l fi sm a d ei n t h es e n d i n gs t a g e ，c o m p e n s a t i o nf l o wq u e u e ，w h i c hi sd e f i n e se a c hn o d e ， e x e c u t e sr e s o u r c ec o m p e n s a t i o nt oo t h e rn o d e si nc o m p e n s a t i o ns t a g ea n d t h ea b a n d o n m e n to fc h a n n e lw i t hs e n d i n gr i g h t sd e l i v e r e d t oo t h e rn o d e s i sc a r r i e do u ti nd o r m a n c ys t a g e e a c hn o d ec o m p l e t e sf a i rt r a n s m i s s i o n o fn e t w o r kp a c k e tt o g e t h e ri n a c c o r d a n c ew i t hf i x e dc o o r d i n a t i o n s c h e d u l i n gr u l eo fm o d e l f i n a l l y , p e r f o r m a n c ee v a l u a t i o n ，i n c l u d i n gt h r o u g h p u t ，p a c k e tl o s s r a t i o b u f f e rq u e u el e n g t ha n df a i r n e s s ，i sc a r r i e do u tt on o d e sb yu s i n g n s 2s i m u l a t i o nt o o l ，s oa st oe x a m i n et h ee f f e c t i v e n e s so ft h ep r o p o s e d a o d ma n di c s f q k e yw o r d sw i r e l e s sm e s hn e t w o r k ，f a i rs c h e d u l i n g ，q u e u em a n a g e 。 m e n t ，f a i rq u e u e i n g 目录 第一章绪论l 1 1 研究背景l 1 2 国内外研究现状2 1 2 1 队列管理的研究现状3 1 2 2 公平队列的研究现状4 1 3 研究目的和意义5 1 4 主要研究内容6 1 5 论文构成7 第二章提高服务质量的公平调度问题分析一8 2 1w m n 中调度策略和q o s 结构的分析8 2 1 1 分布式调度策略8 2 1 2 集中式调度策略9 2 1 3m a c 层服务质量体系结构1 0 2 2 公平调度中服务质量的影响因素1 1 2 2 1 节点内位置相关的竞争1 2 2 2 2 节点间二进制指数退避机制1 2 2 3w m n 中提高服务质量的关键技术1 3 2 3 1 缓存队列管理。1 4 2 3 2 数据流公平排队模型1 5 2 4w m n 中公平调度算法的设计思路16 2 5 本章小结1 7 第三章基于自适应超时检测的缓存队列管理算法18 3 1 自适应超时检测模型a o d m 的设计18 3 1 1 模型变量定义1 8 3 1 2 队列门限值的推导1 9 3 1 3 丢包函数的确定2 0 3 2 模型a o d m 的适应性调整2 2 3 2 1 基于信道预测因子的丢包率调整2 2 3 2 2 基于节点发送速率的门限值调整2 3 3 3a o d m 丢包策略的改进2 5 3 3 1 数据包跳数的计算2 6 3 3 2 选择性丢包策略s d m 2 6 3 4 算法仿真模拟和结果分析2 8 3 4 1 仿真参数与性能判据2 8 3 4 2 仿真结果分析2 9 3 5 本章小结3 2 第四章一种分期协同调度的公平队列算法3 3 4 1i c s f q 的相关问题3 3 4 1 1 算法的应用环境3 3 4 1 2 信道状态监测模块3 4 4 1 3 算法的公平性目标3 4 4 2 队列数据结构一3 5 4 2 1 数据流队列3 5 4 2 2 补偿流队列3 6 4 3 分期协同调度模型i c s m 3 7 4 3 1 分期协同调度模型的架构3 8 4 3 2 分期协作调度的实现机理4 0 4 3 3 分期协同调度的执行流程一4 l 4 4 仿真实验结果与分析4 2 4 4 1 仿真环境与参数4 3 4 4 2 性能评价指标4 4 4 4 3 仿真结果分析4 4 4 5 本章小结4 6 第五章结论与展望4 8 5 1 结论4 8 5 2 展望4 9 参考文献5 0 附录1 图索引5 5 附录2 表索引5 6 致谢5 7 攻读学位期间主要的论文情况和科研情况5 8 w m n q o s r e d b s s s 符号说明 w i r e l e s sm e s hn e t w o r k q u a l i t yo fs e r v i c e r a n d o me a r l yd e t e c t i o n b a s es t a t i o n s u b s c r i b e rs t a t i o n m s h - d s c hm e s hd i s t r i b u t e ds c h e d u l i n gm e s s a g e i e m s h c s c h d c f c s m a c a r t s c t s c i d s d u a o d m t d c p f p cb i t d s d v s d m i c s f q i c s m d c a c s r i n f o r m a t i o ne l e m e n t s m e s hc e n t r a l i z e ds c h e d u l i n gc o n f i g u r a t i o n m e s s a g e d i s t r i b u t e dc o o r d i n a t i o nf u n c t i o n c a r r i e rs e n s e m u l t i p l e a c c e s sw i t h c o l l i s i o na v o i d a n c e r e q u e s tt os e n d c l e a rt os e n d c o n n e c t i o ni d s e r v i c ed a t au n i t a d a p t i v eo v e r t i m ed e t e c t i o nm o d e l t a i ld r o p c h a n n e lp r e d i c t i o nf a c t o r p o w e rc o n t r o lb i t d e s t i n a t i o ns e q u e n c e dd i s t a n c ev e c t o r s e l e c t i v ed r o pm e t h o d i n s t a l l m e n tc o o r d i n a t i o n s c h e d u l i n g b a s e df a i r n e s sq u e u e i n g i n s t a l l m e n tc o o r d i n a t i o n s c h e d u l i n gm o d e l d y n a m i cc h a n n e la s s i g n m e n t c o o r d i n a t i o ns c h e d u l i n gr u l e 无线m e s h ( 网状) 网 服务质量 随机早期检测 基站 用户站 m e s h 网络分布式调 度消息 信息单元 m e s h 网络集中调度 消息 分布式协作模式 载波侦听多址接入 碰撞避免策略 请求发送 允许发送 连接标识符 业务数据单元 自适应超时检测模型 尾丢弃 信道预测因子 功率控制位 目的节点序列距离矢 量路由协议 选择性丢弃策略 分期协同调度的公平 队列 分期协同调度模型 选择动态信道分配 协同调度规则 硕士学位论文第一章绪论 第一章绪论弟一早珀t 匕 随着信息通信的不断发展和进步，无线网络技术已成为当今发展最迅速、使 用最广泛的通信技术之一，是2 1 世纪全球信息技术发展的重要标志。目前，无 线通信正朝着5 w ( 任何地方、任何时间、任何人为任何原因进行任何形式的通信， w h e r e 、w h e n 、w h o 、w h y 、w h a t ) 的目标不断迈进，其宗旨就是为广大移动用 户提供无时不在的“无缝”通信连接。无线m e s h 网【( w m n ，w i r e l e s sm e s hn e t w o r k ) 作为新一代宽带无线接入网络模式，能够融合现有的多种无线网络，很好的顺应 了无线通信的这一发展趋势。随着无线网络的飞速发展和网上信息的急剧膨胀， 如何解决节点内部数据流对缓存区的争用和节点间信道资源的合理分配，是目前 w m n 中服务质量研究的关键问题。本文以公平调度为研究重点，分别从数掘流 连接建立阶段的缓存队列管理的和数据传输阶段的公平排队两方面寻求解决方 案，实现w m n 中服务质量的提高。 1 1 研究背景 无线网络技术的发展r 新月异，各种8 0 2 1 l x 标准不断被更新，随着人们对 8 0 2 1 l a 和8 0 2 1 i e 等w l a n 技术了解的深人，如何突破w l a n 网络结构在覆盖 规模上扩展的约束，提供大面积无线“热区”覆盖和真正平滑漫游能力，成为人们 需要迫切解决的问题，此时w m n 技术作为新一代的无线接入技术应运而生。 w m n 中的无线节点可以同时作为a p 或路由器来发送和接收信号，每个节 点都可以与一个或多个对等节点进行直接通信。与传统的交换式网络相比，w m n 中有新节点加入时，该节点可以自行配置并确定最佳的多跳传输路径，网络能够 自动发现拓扑变化来调整通信路由以获取最有效的传输路径。鉴于上述优点， w m n 被快速商业化，并广泛应用于各种环境 2 1 ，如宽带家庭网络、社区网络、 建筑物自动控制、高速城域网和企业网等。 与其他网络一样，w m n 同样要求为终端用户提供一定的服务质量( q o s ， q u a l i t yo f s e r v i c e ) 保证。从w m n 本身特性来讲，它是一种高容量、大速率、多 信道的分布式网络，因此q o s 保证较为困难。同时，承载业务的多样性又使得 w m n 的q o s 实现起来较其他网络更为复杂1 3 j 。在无线网中，服务质量一般是通 过资源预留和公平调度来满足的，对比诸多影响q o s 的因素来说，公平调度是 最细致的且最能直接影响数据流的上行和下行传输，是无线网络系统兑现服务质 量承诺的核心构件i 4 。 硕士学位论文第一章绪论 在w m n 的调度过程中，每个节点的缓存队列都包含了两种类型的数据包： 自身需要发送的( “自身流”) 和其它节点需要转发的( “中继流”) 。按照i e e e 8 0 2 1 6 的协议规定，w m n 中任何节点必须像发送自身流那样转发其它节点的中继流【5 】。 然而由于自主网络拓扑的多跳性以及节点位置导致承载数据流量和干扰环境的 不同，使得节点内实现数据流问的这种公平竞争非常困难。除此之外，节点之间 在网络发生拥塞时也会相互竞争有限的信道资源，而目前i e e e8 0 2 1 1 分布式协 调功能所采用的二进制指数退避机制不提供任何延时和带宽保证1 6 j ，结果就造成 不同节点在信道资源分配上的差异，从而导致了节点i 日j 的不公平。 综上所述，在公平调度过程中，网络节点内部和节点之间都会竞争有限的网 络资源，这就使得对网络中的数据流进行合理有效的调度显得至关重要，是确保 用户服务质量q o s 和资源公平共享的关键。数据流调度不当将导致网络中瓶颈 增多、吞吐量下降、公平性降低等严重后果，甚至整个网络系统发生崩溃。w m n 的无线多跳，高误码率和射频干扰等特点，更增加了调度问题的复杂性【7j 。因此， 如何在w m n 中合理地调度数据流，是实现各种资源在不同用户之间公平分配和 传输的关键，是一个极具挑战性的课题。 1 2 国内外研究现状 目前，思科、阿德利亚及其它一些中小企业已经可以提供无线网状网的产品， 欧美等地己将开始建立无线网状网的商用网络。如耶路撒冷宣布“无线耶路撒冷” 计划，在其最繁忙的部分商业区提供无线上网服务；“热点阿姆斯特丹”公司开始 新建城市w i f i ，提供城域网无线接入服务；美国费城公布计划，将在全城的街 灯和屋顶上建立数以百计的无线接入点，工程将遍布全城1 3 5 平方英里。在国内， 中国台北市政府启动的“无线新都”计划，要求台北市建立2 0 0 0 0 多个无线接入 点，提供全城无线宽带覆盖【5 】。这些城域网无线接入的解决方案都是基于i e e e 8 0 2 1 l 的无线网状网技术，w m n 已经成为无线宽带城域网研究和应用的重点。 其中，针对w m n 中公平调度的问题近年来引起了国内外学者的广泛关注， 目前出现了大量的解决方案，如在w m n 的调度过程中为不同数据流提供补偿和 惩罚机制以叭，来实现数据流之间带宽分配的平衡；改进已有的m a c 层拥塞控 制算法 1 1 - 1 4 j ，实现数据传输阶段的网络负载均衡；对无线网络的信道状态进行实 时感知i l5 1 、提供多接口多信道机制1 1 6 l 来合理分配信道资源；将有线网络的主动 队列管理方法应用到w m n 的数据流公平排队的设计【l7 埔j 中等等。 在众多的解决方案中，本论文关注于队列管理机制和公平队列算法对数据流 调度中服务质量的提高，前者是数据流连接建立阶段必做的一项准备工作，是实 现节点内数据包公平排队的前提；后者是数据传输阶段需要深入考虑的一个重要 2 硕士学位论文 第一章绪论 问题，是防止链路状况十分不稳定的w m n 网络中负载不均衡、数据阻塞和网络 吞吐量下降的一种重要手段。 1 2 1 队列管理的研究现状 队列管理通过在适当的时l 、日j 丢弃部分数据包来控制缓存队列的长度，实现 了对处理器中缓存资源的管理和分配，它和调度机制、缓存管理是互补的，也是 提供反馈的源头。最常用的队列管理是尾丢弃( t d ，t a i ld r o p ) 策略，从算法复杂 度来说，t d 是最简单的，然而尾丢弃会造成业务流对缓存的死锁和产生全局同 步效应，同时缓存长时间处于满状态，导致较长的排队等待时延。 为降低队列的时延，f l o y d 箸j 9 1 9 j 提出了随机早期检测算法r e d ( r a n d o me a r l y d e t e c t i o n ) ，该算法采用网关的平均队列长度作为网络拥塞的度量值，以平均队 长的分段线性函数作为丢弃概率函数。然而，r e d 算法的参数配置非常复杂，会 引起网络的不稳定和大量分组丢失；为此，邓等【2 0 】提出了一种非线性自适应r e d 拥塞控制机制，利用一个高阶分组丢弃函数对不同阈值的分组进行标记，通过参 数p m a x 自适应调整，避免了静态参数设置的约束和缓存区的溢出；文献【1 7 】提出 t l r e d ( t r a f f i cl o a da d a p t i v er e d ) 、文献【18 】提出a h r e d ( a dh o ch a z a r dr e d ) 算法都足典型的r e d 改进算法，它们根据网络的拥塞程度相应的增加或减小丢包 概率，来增强对网络流量负载变化的自适应能力。 上述算法解决了r e d 的参数自适应能力从而降低了延时，但它们并没有考 虑数据流间的公平性。因此，不少人开始在公平性方面对队列算法进行研究，如 l i n 等【2 l 】提出了在无线接入点a p 上采用虚拟队列管理算法v q r e d 的方法，解 决w l a n 固定基础设施中存在的上下行链路、同向数据流间的不公平性题； z h o u 等【2 2 】针对路由器对快速流和慢速流处理速度的不同，提出了一种可扩展的 公平随机早期检测s f r e d 算法，在该算法中维护一个有限主动流的统计列表， 利用该列表s f r e d 惩罚快速流、保护慢速流，来实现网络的公平性；岳1 2 圳等提出 一种基于等效活动流预测的主动队列管理机制，通过抑制行为不端流进入队列的 机会，从而获得业务流间的近似公平；c s f q ( c o r es t a t e l e s sf a i rq u e u e ) 1 2 4 1 通过早 期丢包来实现最大最小公平原则，从而在公平性上达到公平队列算法的效果； 前面提到的算法大多应用在单跳的无线网中，由于w m n 是多跳的自组织网 络，数据流会随着跳数的增加而有效带宽逐渐降低1 25 | ，如何解决这个问题成为 目前多跳网研究的热点。l i m 等1 2 6 j 针对w m n 中数据流随跳数增加吞吐量快速减 小导致节点“饿死”的问题，提出了根据跳数信息实现不同丢弃优先权的加权随机 早期检测机制，该机制通过网络j 爿j 塞时发送具有更高优先权、更远节点的数据包 来实现公平性；文献 2 7 付旨出w m n 中继节点的队列缓存管理算法限制了跳数较 硕士学位论文 第一章绪论 多数据流的性能，并提出一种新的基于i e e e8 0 2 1 l s 的队列管理算法，通过在活 跃m e s h 节点中公平共享有效缓冲区来改善这种情况；b i n h 等【2 8 】针对无线多跳网 中增加节点数目和流量负载导致网络迅速超载的问题，提出了一种中继平衡和队 列管理方法，来减少数据包传输过程中的时延，同时保持了高吞吐量。张等【2 9 j 针对w m n 的公平性问题，首次提出队列管理和资源分配联合的解决方法，并通 过改进i e e e8 0 2 1 1 竞争窗口处理方法得到一种新的自适应分布式无线资源分配 协议，保证了在网络重载时节点的公平性。 从上述分析可以看出，已有的无线队列管理算法侧重于在单跳网络中的应 用，对多跳网特别是w m n 的研究还很少。由目前提出的适用于多跳网的队列管 理算法分析可知，其关注的重点在中继节点如何能够处理好高跳数数据流的性 能，保证其公平性的同时提高吞吐量、降低时延，是w m n 中队列管理的今后进 一步研究的方向。 1 2 2 公平队列的研究现状 在无线多跳网中，早期的公平队列算法分为节点激活和链路激活两种【3 0 1 ， 节点激活的队列算法可以保证所有节点发送的分组都被其所有邻居成功接收；链 路激活的算法则保证目的节点能够成功地接收分组。当前比较流行的一种分类方 式是按照无线网络的体系结构，分为集中式和分布式【3 1 1 两类，前者需要知道网 络全局拓扑信息，后者至多允许知道其邻居信息。在已有的队列算法中，无论是 集中式还是分布式，其性能方面的研究主要集中在吞吐量和服务质量两方面。 为提高w m n 的网络吞吐量，c a p o n 等1 3 2 j 提出将调度和路由优化结合，同时 考虑功率控制、链路速率约束以及自适应调制编码，以最大化系统吞吐量为目标， 将问题建模为混合整数线性规划问题；而r e a z 等【3 列考虑到同时优化路由和调度 的复杂性，将上述两个问题分离，采用启发式的算法对链路功率的调整，在保证 已调度链路满足s i n r 要求的前提下，对新的链路进行调度；然而上述两种算法 需要综合考虑功率控制、信道测量和反馈技术，设计的调度算法复杂性过高，大 都处于理论研究阶段。夏等【3 4 l 提出一种基于拥塞的机会调度算法，通过发送节 点向多个下一跳接收节点发送r t s ( r e q u e s tt os e n d ) 帧，接收节点根据自身拥塞 程度按照一定概率依照调度优先级顺序发送c t s ( c l e a rt os e n d ) 帧，来提高网络 端到端的饱和吞吐量。 公平队列算法中对服务质量的研究得到了较多的关注，这主要是由于 8 0 2 1 l s 协议采用的c s m a c a 竞争机制对系统的q o s 支持能力较弱，而8 0 2 。1 6 m e s h 模式目前对服务质量的定义只停留在数据包级别【3 5 l 。因此，s h e t i y a 等【3 6 】 分别针对实时匀速、实时变速和非实时业务设计了不同的调度算法，每条业务流 4 硕士学位论文 第一章绪论 上的资源都由控制节点分配，最终按照一定的原则将所有的算法综合，得到了能 满足不同业务q o s 需求的调度算法；h o n g 等1 3 7 通过对路由和调度的联合优化来 提供q o s 支持，依据业务的q o s 需求、节点的承载能力以及链路间干扰来进行 路径选择，而每个m e s h 节点和每条链路的资源分配由网关节点统一执行。 公平性作为q o s 中的一个重要因素，越来越多的算法开始从这个方面入手 来提高网络的服务质量。在w m n 中，按照公平性由高到低划分，现有的公平调 度协议可分为五种类型【3 8 】，即硬性公平( h a r df a i r n e s s ) 、最大- 最小公平( m a x m i n ) 、 比例公平( p r o p o r t i o n a lf a i r n e s s ) 、偏混合公平( m i x e d b i a s ) 以及最大吞吐量。s o n g w u l u 3 9 】首次提出了一种理想公平队列算法i w f q ，通过补偿滞后流附加带宽来保证 公平性，但i w f q 在超前流的惩罚平滑性方面稍显不足，而且同步流在对滞后流 的补偿中也会受到影响；文献【4 0 】提出的无线公平服务w f s 能够分离数据流的 带宽延迟需要，分别对待出错和延迟敏感的数据流，但w f s 的补偿机制相当复 杂，可实现性小； h u b a u x 等【4 1 】提出一种公平调度机制来优化w m n 中的带宽利用率，该机制 通过为各个链路分配发送权限来保证每个终端用户的公平；为实现公平性和吞吐 量的平衡，t a n g 等【4 2 】设计了一种简单的最大最小公平模型，该模型在下行链路 调度中融入硬性公平规则来解决网络高吞吐量的问题，保证了各个数据流的最大 最小带宽分配；k i d o n g 等【4 3 】为互连的w m n 和视频传感器网络提出了一种公平 调度方法，通过m e s h 节点在网络链路容量充足时执行公平调度策略、不足时进 行流量疏导来提供公平性；r a g h u n a t h a n 等l 删提出一种比例公平的调度算法，在 网络资源充足时，系统以吞吐量最大化为目标，在网络拥塞或繁忙时，降低网络 吞吐量来强制为各个节点提供公平性；s i n g h 等1 4 5 】在调度中采用偏混合( m i x e d b i a s ) 技术实现公平性，该技术对网络资源进行隔离，运用不同的公平技术到每个 资源部件中，当网络变得拥塞和繁忙时，贪婪节点会受到惩罚，公平性得到了加 强，该算法实现了长期公平。 综上所述，目前已有很多文献对w m n 中调度技术进行了研究，然而现有的 算法只是在吞吐量和公平性中选择其中一种作为性能判据，一般而言，随着公平 性的增加吞吐量会相应降低，反之亦然。如何在这两者之间进行折衷，使不同业 务需求的节点能够获得最好的服务质量还有待进一步研究。因此，设计一种公平 调度算法，在保证公平性的前提下，能够最大化的提高网络的吞吐量，成为今后 研究的重点。 1 3 研究目的和意义 随着无线网络的快速发展，其信道带宽不断增大，已经从8 0 2 1 1 最大2 m b p s 硕士学位论文 第一章绪论 提高到8 0 2 1l a g 的5 4 m b p s ，未来的8 0 2 1i n 则能够达到1 0 8 m b p s 。信道带宽的 不断增大越发突显了信道带宽资源公平分配的重要性，没有公平的开销和信道竞 争机制，网络中不同节点之间获得的服务质量就会存在巨大的差异。特别是在极 端情况下，甚至可能发生单个节点独占全部信道带宽的情况，使得其它用户的基 本服务质量要求无法得到满足，显然这种不公平是无法接受的。 解决公平调度问题的目地就是使网络中的任意节点能够平等的访问信道资 源，在相同的网络负载下，节点所获得的网络资源不会因为其地理位置和拓扑结 构的不同而存在巨大的差异，以此也确保各个付费用户的服务质量。但由于i e e e 8 0 2 1 1 的m a c 机制中的某些特性如二进制指数退避算法等并不能够提供很好的 公平性，使得基于8 0 2 1 1 标准的w l a n 和w m n 都存在资源分配不公的现象。 相比之下，w m n 网络由于承载业务类型的多样性使得其q o s 实现起来较其它网 络更加困难。 因此，本论文将重点放在解决w m n 数据流公平调度的问题上，根据w 在拓扑和传输上的特殊性，针对目前无线网调度机制无法满足用户服务质量需求 的现状，探索合理有效的解决方案。本论文的主要目标是通过对目前w m n 调度 机制在q o s 方面的探索和研究，发现其中的不足之处，提出新的解决办法，增 强网络的吞吐量、资源利用率和公平性。这一目标的实现对于提高w m n 的整体 性能，满足网络中多媒体业务的不同q o s 要求以及推动w m n 的应用，具有重 要的理论指导意义和实际意义。 1 4 主要研究内容 本论文致力于w m n 数据流公平调度问题的研究，尤其关注于节点内缓存队 列的管理和节点间数据流公平排队。文章在详细分析w m n 现有调度机制的基础 上，总结出公平调度中影响服务质量的两个关键因素，针对节点内缓存队列中自 身流和中继流竞争的现象，提出一种基于自适应超时检测的缓存队列管理算法， 增强了数据流问对缓存区占用的公平性；针对传统m a c 层拥塞调节机制在节点 间信道资源分配不公的问题，设计了一种分期协同调度的公平队列算法，提高了 实时业务的端到端吞吐率，降低了延时。论文的研究内容主要包括以下几个方面： ( 1 ) w m n 数据包调度中服务质量问题的分析 研究w m n 中现存的数据包调度机制，分析这些机制在公平性方面的特点， 指出它们应用于w m n 的不足之处，最后总结出问题和难点，并给出解决思路： ( 2 ) 提出一种基于自适应超时检测的缓存队列管理算法 为解决w m n 中节点内自身流和中继流竞争问题，提出了一种白适应超时检 测模型对进入缓存队列的数据包进行管理。该模型对r e d 算法做出改进，通过 6 硕士学位论文 第一章绪论 对节点缓存队列门限值、丢包率计算方法的重新定义，使其适用于无线多跳的应 用环境。为了提高中继流进入缓存队列的概率，设计了一种选择性丢包s d m 的 保障机制，结合自适应超时检测模型实现了节点内数据流的公平性。 ( 3 ) 设计一种分期协同调度的公平队列算法 针对传统m a c 层二进制指数退避机制在节点间信道带宽分配不公的问题， 提出了一种分期协同调度的公平队列算法。该算法为节点设计了一种新的补偿流 队列，用来实现对网络中”被补偿”节点的记录。通过建立分期协同调度模型，将 节点的数据传输过程划分为发送、补偿、休眠三个时期，利用信道监测机制确定 队列的信道状态，实现了节点间对数据流的协同调度。 ( 4 ) 性能评估 对提出的缓存管理算法和公平队列算法进行性能分析和仿真验证。 1 5 论文构成 论文分五章，后续章节的组织结构如下： 第二章本章在研究w m n 现存数据包调度机制的基础上，分析了调度过程 中对q o s 的影响因素，提出了具有针对性的解决办法，最后阐述了公平调度算 法的设计思路，作为后续章节算法设计的检测标准。 第三章基于自适应超时检测的缓存队列管理算法。该算法以随机早期检测 算法r e d 为基础，设计了一种自适应超时检测模型对缓存队列中的数据包进行 早期检测和队列门限制的自适应调整。鉴于该模型中采用的随机丢包策略对数据 流不公平的丢弃，文章又提出了一种选择性丢包策略，极大的提高了调度中的公 平性。 第四章一种分期协同调度的公平队列算法。设计了一种分期协同调度的公 平队列算法，包括新的队列结构，信道状态检测模块和分期协同调度模型等，最 后通过性能分析和仿真模拟对提出的吞吐率、延时和公平性进行性能评估。 第五章结论与展望。对本文所作研究进行总结，同时提出后继