（通信与信息系统专业论文）ieee80216e下行资源调度算法研究.pdf

摘要 随着无线数据服务和多媒体应用需求的快速增长，人们期待未来的无线网络能够 满足为多类业务提供分q o s 服务的需求，因此支持不同q o s 服务的分组调度算法和 接入控制算法成为宽带无线通信网络发展的关键。正交频分复用( o f d m ) 技术作为 一种无线环境下的高速传输技术，具有良好的抗多径信道干扰能力，本文主要研究 i e e e 8 0 2 1 6 e 基于o f d m a 技术的多业务分组调度算法和接入控制算法。 第一章概述了课题研究的背景和涉及的关键技术，为深入课题的研究进行了知识 上的积累。 第二章分析了几种经典的无线通信系统中的分组调度算法和接入控制算法，包括： 最早截止时间有限调度算法、轮询调度算法、最大载干比算法、加权公平队列以及公 平调度算法、基于优先级的接入控制算法、基于呼叫优先的接入控制算法、基于移动 信息的接入控制算法。详细分析了这几种分组调度算法和接入控制算法的适用条件和 各自的优缺点。 第三章首先详细分析了i e e e 8 0 2 1 6 e 协议q o s 方面的特点和架构，并研究了与调 度算法相关的物理层机制，其次，根据i e e e 8 0 2 1 6 e 业务的特点和q o s 需求，提出了 适用于i e e e 8 0 2 1 6 e 的下行分组调度和接入控制总体方案。方案特点是：满足不同业 务的q o s 需求，提高系统的吞吐量和带宽利用率。 第四章在研究相关文献的基础上，提出了基于“树型 结构的下行分组调度算法， 其次，对改进算法的各个功能模块进行了详细的分析设计；最后，对改进后的分组调 度算法进行了仿真分析；仿真结果表明，改进后的分组调度算法能满足实时业务的 q o s 需求，有利于提高实时业务的吞吐量，系统丢包率明显降低，并且系统带宽利用 率得到较高的提升。 第五章提出了基于i e e e 8 0 2 16 e 的动态接入控制算法，对算法各个模块进行了详 细的分析和设计，并对算法进行了仿真分析，仿真结果表明，动态接入控制算法有利 于降低系统的阻塞率，并且系统的带宽利用率有较大的提升。 论文最后总结全文工作，探讨在此领域可以进一步研究的思路和方向。 关键词：i e e e 8 0 2 1 6 e ，w i m a x ，资源调度，接入控制，q o s a b s t r a c t e v e r yo n ee x p e c t sf u t u r ew i r e l e s sn e t w o r kc a l lp r o v i d eq o sg u a r a n t e e sf o rv a r i o u s a p p l i c a t i o n sw i t ht h er a p i dg r o w t ho fw i r e l e s sd a t as e r v i c ea n dm u l t i m e d i aa p p l i c a t i o n s t h e r e f o r e ，t h es c h e d u l i n ga l g o r i t h m ss u p p o r t i n gd i f f e r e n tq o ss e r v i c e sb e c o m et h ek e y p o i n tf o rt h ed e v e l o p m e n to fb r o a d b a n dw i r e l e s sc o m m u n i c a t i o nn e t w o r k s o f d m t e c h n e l e g y , a sah i g h s p e e dt r a n s m i s s i o nt e c h n o l o g yf o rw i r e l e s se n v i r o n m e n t ，i se f f e c t i v e a ta n t i m u l t ip a t hf a d i n g s ot h i st h e s i sm a i n l yf o c u s e so nt h er e s e a r c ho nd i f f e r e n tp a c k e t s c h e d u l i n ga l g o r i t h m sb a s e do no f d mi nb r o a d b a n dw i r e l e s sa c c e s ss y s t e m sn a m e di e e e 8 0 2 16 e i nc h a p t e ro n e ，ac o m p r e h e n s i v ea n di n - d e p t ha n a l y s i so ft h ea s s o c i a t e dr e s e a r c hi s d i s c u s s e d ，i n c l u d i n gb a c k g r o u n do ft h er e s e a r c hp r o j e c ta n dr e l a t e dt e c h n i q u e i nc h a p t e rt w o ，s o m ec l a s s i cp a c k e ts c h e d u l i n ga l g o r i t h m sf o rw i r e l e s ss y s t e ma r e a n a l y z e d ，i n c l u d i n ge n dd e a d l i n ef i r s t ，r o u n dr o b i n ，m a xc i ，w e i g h tf a i r n e s sq u e u i n g a n dp r o p o r t i o n a lf a i r n e s ss c h e d u l i n g i nt h i sc h a p t e r , w ea l s oa n a l y z es o m ec l a s s i cc a c a l g o r i t h m sf o rm o b i l ec o m m u n i c a t i o ns y s t e m ，i n c l u d i n gc a ca l g o r i t h m sb a s e dp r i o r i t y , c a c a l g o r i t h m sb a s e dh a n d o v e re t c t h e s ea l g o r i t h m s c o n d i t i o n sf o ru t l i z i n ga r ep r e s e n t e d ， w h a t sm o r e ，t h er e s p e c t i v ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h ea b o v ea l g o r i t h m sa r e a n a l y z e d i nc h a p t e rt h r e e ，w ef i r s ta n a l y z et h ei e e e8 0 2 16 eq o sa r c h i t e c t u r e t h e n ，w e i n t r o d u c et h em e c h a n i s mo fi e e e 8 0 2 16 em a ca n dp h yl a y e r i na d d i t i o n ，c o n s i d e r i n g t h ef e a t u r eo fi e e e 8 0 2 16 e ，p r i o r i t i e so fd i f f e r e n ts e r v i c e sa n dr e q u i r e m e n t so fq o s ， g e n e r a ls c h e m eo fs c h e d u l i n ga n dc a ca l g o r i t h ma r ep r o p o s e d t h ef e a t u r eo ft h i sd e s i g n i st h a ti tc a nm e e td i f f e r e n tn e e d so fq o sa n di m p r o v et h eb a n d w i t hu t i l i t i e s i nc h a p t e rf o u r , w ep r o p o s eas o r to fi m p r o v e ds c h e d u l i n ga l g o r i t h m sb a s e do n t r e e s t r u c t u r e t h e n ，w ed i s c u s st h ed e t a i l e dd e s i g no f e a c hm o d e lf o rt h em o d i f i e da l g o r i t h m s a d d i t i o n a l l y ，t h es i m u l a t i o nr e s u l t sp r o v e dt h a ti ti sf a v o r a b l ef o rr e a l - t i m es e r v i c es u c ha s u g sa n dr t p s ，f o ri n c r e a s i n gt h en e t w o r kt h r o u g h p u t ，a n df o ri m p r o v i n gt h eb a n d w i d t h u t i l i t i e s i nc h a p t e rf i v e ，w ep r o p o s ead y n a m i cc a ca l g o r i t h ma n dd i s c u s st h ep r o c e e d i n go f a l g o r i t h m ，t h e n ，w ed i s c u s st h ec o m p l e t ea n a l y s i sa n dd e s i g no fa l g o r i t h m t h es i m u l a t i o n r e s u l t sp r o v e dt h a tt h en e wc a ca l g o r i t h mc a t li m p r o v es y s t e mp e r f o r m a n c e ，i n c r e a s et h e b a n d w i t hu t i l i t i e s t h el a s tc h a p t e ro ft h i st h e s i sp r o v i d e st h ec o n c l u s i o no ft h et h e s i s a n di ta l s o d i s c u s s e st h ep r o s p e c ti nt h i sf i e l da tt h ee n d k e y w o r d s ：i e e e 8 0 2 16 e ，w i m a x ，r e s o u r c e ，s c h e d u l i n g ，c a c ，q o s 插图索引 图1 1w i m a x 无线接入的拓扑结构图1 图3 1i e e e 8 0 2 1 6 em a c 层架构1 3 图3 2i e e e 8 0 2 1 6q o s 架构1 7 图3 3o f d m a 物理层s l o t 映射方式18 图3 4o f d m a 物理层帧结构1 9 图3 5 上下行子帧z o n e 的情况19 图4 1 树型结构调度模型2 3 图4 2 改进后的调度架构2 4 图4 3 资源初始化流程2 5 图4 - 4 队列管理流程2 6 图4 5u g s 业务调度流程2 7 图4 6r t p s 业务调度流程2 8 图4 7n r t p s 业务调度流程2 9 图4 8b e 业务调度流程3 0 图4 9 剩余资源调度流程。3l 图4 1 0 实时业务的平均吞吐量3 3 图4 11 非实时业务平均吞吐量3 3 图4 1 2 实时业务的丢包率3 4 图5 1 基于门限的接入控制算法3 7 图5 2 基于公平性的接入控制算法3 7 图5 3 动态接入控制算法的总体结构3 8 图5 4 动态接入控制算法总体流程3 9 图5 5u g s 业务接入流程4 0 图5 - 6r t p s 业务接入控制流程4 1 图5 7n r t p s 业务接入流程一4 2 图5 8u g s 业务阻塞率曲线4 3 图5 - 9r t p s 业务阻塞率曲线4 4 图5 1 0n r t p s 业务阻塞率曲线4 4 图5 1 1 带宽利用率4 5 v 表格索引 表3 1i e e e 8 0 2 1 6 e 物理层机制1 5 表3 2 不同业务的q o s 参数1 7 表4 1 系统参数设置3 2 表4 2 业务仿真参数3 2 表4 3 q o s 参数设置3 2 表4 4自适应调制方式3 2 表4 5 延时性能分析3 4 表5 1q o s 参数设置4 3 v i i 缩略语 ( 按文中出现顺序) 无线保真( w i f i ，w i r e l e s s f i d e l i t y ) 全球微波接入操作性( w i m a x ，w o r l di n t e r o p e r a b i l i t yf o rm i c r o w a v ea c c e s s ) 城域网( m a n ，m e t r o p o l i t a n a r e an e t w o r k s ) 基站( b s ，b a s es t a t i o n ) 电气与电子工程师协会( i e e e ，i n s t i t u t eo fe l e c t r i c a la n de l e c t r o n i c se n g i n e e r s ) 非视距( n l o s ，n o n - l i n e - o f - s i g h t ) 服务质量( q o s ，q u a l i t yo fs e r v i c e ) 非请求的主动授权业务( u g s ，u n s o l i c i t e dg r a n ts e r v i c e ) 实时轮询业务，s ，r e a l - t i m ep o l l i n gs e r v i c e ) 非实时轮询业务( i m p s ，n o nr e a lt i m ep o l l i n gs e r v i c e ) 尽力而为业务( b e ，b e s te f r o r t ) 呼叫接入控制( c a c ，c a l la d i m i s s i o nc o n t r 0 1 ) 正交频分复用( o f d m ，o r t h o g o n a lf r e q u e n c y d i v i s i o nm u l t i p l e x ) 正交频分多址( o r t h o g o n a lf r e q u e n c yd i v i s i o nm u l t i p l e xa c c e s s ) 无线资源管理( r r m ，o f d m a ，r a d i o r e s o u r c em a n a g e m e n t ) 媒体接入控制( m a c ，m e d i u m a c c e s sc o n t r 0 1 ) 部分使用子信道( p u s c p a r t i a lu s a g eo fs u b c h a n n e d 自适应调制编码( a m c ，a d a p t i v e m o d u l a t i o na n dc o d i n g ) 分类一队列一调度( c q s ，c l a s s i f i c a t i o n , q u e u i n g ，s c h e d u l i n g ) 最早截止时间( e d f , e n dd e a d l i n ef i r s t ) 加权公平队列( w r q ，w e i g h t e df a i r n e s sq u e u i n g ) 轮询调度( i 氓r o u n dr o b i n ) 先入先出队列( f i f o ，f i r s t - i n p u tf i r s t - o u t p u t ) 混合自动重传请求( h a r q ，h y b r i da u t o m a t i cr e p e a tr e q u e s t ) 公共处理共享( g p s ，g e n e r a l i z e dp r o c e s s o rs h a r i n g ) 文件传输协议f f t p , f i l et r a n s f e rp r o t o c 0 1 ) 最大载干比( m a xc i ，m a x i m u mc a r t i e r - t o i n t e r f e r e n c e ) 比例公平( p f ，p r o p o r t i o n a lf a i r n e s s ) i x 数据记录控制( d r c ，d a t ar e c o r dc o n t r 0 1 ) 点对多点( p m p , p o i n t - t o m u l t i p l e - p o i n t ) 连接标识符( c i d ，c o n n e c t i o ni d e n t i f y ) 自动请求重传( a r q ，a u t o m a t i cr e p e a tr e q u e s t ) 服务数据单元( s d u ，s e r v i c ed a t au n i t ) 协议数据单元( p d u ，p r o t o c o ld a t au n i t ) 无线局域网( w l a n ，w i r e l e s sl o c a la c c e s sn e t w o r k ) x 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了 谢意。 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复 印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和 纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办 理。 签名障虢澜期：埘 第1 章绪论 第1 章绪论 1 1 1 课题研究背景 随着互联网技术的发展，人们对i n t e m e t 的信息传递、商务和娱乐等功能的要求 越来越高，因此，用户对带宽的需求也不断增加。目前各国对以光缆为主体的核心网 络建设己经初具规模，光缆的传输速率和容量可以满足要求，但是在无线接入网方面， 宽带无线接入己经成为制约高速上网和其他业务的瓶颈。 目前比较有竞争力的宽带接入技术有三种：w i f i ，w i m a x ，3 g 。其中w i m a x ( w o r l di n t e r o p e r a b i l i t yf o rm i c r o w a v ea c c e s s ，全球微波接入互操作性) 是基于i e e e 8 0 2 1 6 标准的，它实现了2 1 1 g h z 的非视距( n l o s ，n o nl i g h to fs i g h t ) 传输和 1 0 - 6 6 g h z 的视距( l o s ，l i g h to fs i g h t ) 传输，峰值带宽可达7 5 m b p s 。由于其快速、低 成本搭建、易扩展等优点，w i m a x 被普遍认为是未来最有前途的宽带无线技术之一【l 】。 图1 1 是w i m a x 无线接入的网络结构图。其功能逻辑组包括移动用户台( m s s ) 、 接入网络( a s n ) 、连接服务网络( c s n ) 和外部网络( 如i n t e r n e t ，3 g 等) 。 m s s 包括移动电话，便携式电脑，p d a 等；w i m a x 系统定义用户终端设备与用 户基站间的连接接口，提供用户终端设备的接入。但用户终端设备本身并不属于 w i m a x 系统。 a s n ：由b s 和接入网关( a s ng w ) 组成，可以连接到多个c s n ，为不同n s p 的c s n 提供无线接入服务。 c s n ：可以由路由器、a a a 代理或服务器、用户数据库、因特网网关设备等组成， 主要功能有：因特网接入，为用户会话连接，给终端分配p 地址，用户计费以及结 算，基于用户系统参数的q o s 及许可控制等。 m s s 白 m s s m s s 网络管理 图1 1w i m a x 无线接入的拓扑结构图 1 东南大学硕士学位论文 在无线通信系统中，无线资源永远是有限的，因此，研究有限频谱资源的最大化， 并且合理利用无线资源有着积极而又重要的意义，而无线资源管理承担的就是这样的 作用。它包括了：分组调度、功率控制、移动性管理、接入控制、负载控制等等。它 们每个部分都对无线系统的良好运作起着举足轻重的作用。其中，分组调度和接入控 制更是影响系统性能的最关键两个环节，能在很大程度上决定系统的效率。 1 1 2 课题研究背景 目前，针对不同无线通信系统的调度算法和接入控制算法的研究已经越来越受人 们重视，但其成熟程度因系统的复杂程度不一也显得有些参差不齐。对于复杂链路环 境，尤其是在多径丰富的无线链路环境下分组调度和接入控制的研究才刚刚开始，如 何在m a c 层的方案算法设计中考虑物理层信道变化对其的影响，实施跨越层次的算 法设计对于实际系统的演进有着重要的指导意义。同时，在w i m a x 系统中，无线链 路q o s ( q u a l i t yo fs e r v i c e ，服务质量) 需求的加入，带来了不同用户的可变速率、不同 时延要求的新特性，这对于无线分组调度和接入控制的设计提出了新的、更高层次的 要求。 在i e e e 8 0 2 1 6 e 标准【2 ，3 】中仅规定了具体的业务类型和q o s 特性，对具体的分组调 度和接入控制并没给出算法和实现，因此，结合i e e e 8 0 2 1 6 e 标准，提出适用于 i e e e 8 0 2 1 6 e 系统的分组调度和接入控制算法，具有很强的实用价值。 以上种种，正是本文展开研究w i m a x 网络下分组调度和接入控制算法的意义所 在。 1 2 国内外研究现状 分组调度的概念在有线网络中由来己久，而在无线移动网络中，分组调度同样有 着重要作用，特别是在多业务的无线移动网络中，业务分组调度作为无线资源管理的 一个重要组成部分，更侧重于对系统整体性能和不同业务服务质量的保证。同时，在 无线网络中，信道参数具有时变特性，因此，设计优良的调度算法将遇到更大的挑战 性。 接入控制要求根据新连接的业务特征、q o s 和网络资源与当前状况进行比较，决 定是否接纳这个新连接，在保障己接纳连接的q o s 与接纳尽可能多的新连接之间寻 求平衡点。 目前国内外研究无线调度算法的文献很多【4 - ”】，主要分为三类： 1 、偏向于系统性能 偏向于系统性能的的调度算法是以某个用户的信道质量作为参考，其结果是系统 性能不错，但公平性不好，如最大c i 算法。 2 、考虑用户公平性 将用户的公平性作为考虑因素，但是较少或没有考虑信道质量因素，因此系统吞 吐量不够高，如传统正比公平算法，轮循算法及其众多衍生算法。 3 、综合用户公平性和信道质量 用信道质量作为与前两类算法抗衡的唯一因素，如基于平均吞吐量公平【8 】算法， 但是系统性能不是特别理想，吞吐量有待进一步提高。 2 第1 章绪论 目前国内外研究无线系统接入控制算法的文献也很多1 4 也0 1 ，主要有以下三种： 1 、基于可用带宽的算法 当有新连接到达时，c a c 策略首先判断系统是否存在剩余带宽，若存在则接纳新 呼叫。这种算法的优点是算法比较简单，可以尽可能多的接入连接，但不保证系统的 q o s 质量。 2 、基于门限的算法 为了增加高优先级业务的接入机会，门限策略是当系统满足某些条件时，通过动 态地拒绝到达的某类服务请求来改善吞吐量。这种算法保证了高优先级业务的优先接 入，缺点是高优先级业务过多时，会使得低优先级业务阻塞率增大。 3 、基延迟保障的算法 该算法基于连接的最终期限，检查连接的延迟保障，计算系统可用带宽，满足条 件则接入新连接。保证了现有业务的q o s 不被降级和新业务的q o s ，但是接入条件较 高，要求不能影响已有连接的q o s ，带宽利用率不高。 1 3 论文的章节安排 本文共分为五章，各个章节安排如下： 第1 章：绪论。本章首先描述了课题背景和课题研究的意义；然后对目前国内外 在无线分组调度和接入控制算法领域的成果进行了分析；最后阐述了本文的具体的章 节安排。 第2 章：无线通信系统中的资源分配算法研究。本章主要是在研究i e e e 8 0 2 1 6 e 资源调度算法之前，对无线通信系统中的无线资源管理，特别是无线分组调度和接入 控制作一般性的研究。为文章后续章节提出改进调度算法和接入控制算法作准备。本 章首先分析了无线通信系统中的无线资源管理和q o s 机制；然后，对无线领域的分组 调度算法作了深入研究，着重分析了几种经典的无线调度算法；最后，本章分析了无 线系统中的接入控制算法，并对几种常见的接入控制算法进行了分析。 第3 章：i e e e 8 0 2 1 6 e 下行资源调度总体方案设计。本章主要分析了i e e e 8 0 2 1 6 e 下行分组调度和接入控制的总体方案，首先分析了i e e e 8 0 2 16 e 物理层和m a c 层机 制；其次，对i e e e 8 0 2 1 6 e 协议中的q o s 机制和帧结构进行了重点研究，为后续章节 提出调度算法和接入控制算法作准备；最后，重点对下行分组调度和接入控制总体方 案进行了研究，在分析i e e e 8 0 2 1 6 e 对分组调度调度和接入控制要求的基础上，提出 了适用于i e e e 8 0 2 1 6 e 的下行分组调度和接入控制总体方案。 第4 章：基于i e e e 8 0 2 1 6 e 下行分组调度改进算法研究与实现。本章在研究已有 文献的基础上，提出了一种改进的下行分组调度算法，对各模块进行了详细设计，并 对改进后的算法进行了仿真分析，将改进前后的调度算法进行了比较。仿真结果表明， 改进后的调度算法在系统吞吐量性能，丢包率，业务延时性能等方面有较大的提高。 第5 章：基于i e e e 8 0 2 1 6 e 的动态接入控制算法研究。本章在研究相关文献的基 础上，提出了一种动态使用预留资源的接入控制算法，对算法的各个模块进行了详细 的分析和设计，并对算法进行了仿真分析，仿真结果表明，动态接入控制算法有利于 降低系统的阻塞率，同时，系统的带宽利用率有较大的提升。 第2 章无线通信系统中的资源分配算法研究 第2 章无线通信系统中的资源分配算法研究 本章在研究i e e e 8 0 2 1 6 e 资源调度算法之前，对无线通信系统中的无线资源管理， 特别是无线分组调度和接入控制作深入研究。本章首先分析了无线通信系统中的无线 资源管理和q o s 机制；然后，深入分析了无线通信领域的分组调度算法，着重分析了 几种经典的无线调度算法；最后，对无线系统中的接入控制算法进行了研究，并对几 种典型的接入控制算法进行了分析。 2 1 无线网络中的资源管理与q o s 机制 无线资源管理( r r m ) 就是对移动通信系统的空中接口资源的规划和调度【8 】。之 所以要研究无线资源管理就是希望在有限的无线资源环境下，在保证一定的规划覆盖 和服务质量要求的前提下，接入尽可能多的用户。如果没有无线资源管理技术，即使 再好的无线传输技术也无法发挥它应有的优势，极端的情况甚至可能导致系统无法正 常运行。无线资源管理涉及到一系列与无线资源分配相关的研究课题，例如接入控制、 分组调度、功率控制、切换策略等。 无线通信系统发展的趋势是支持多媒体业务以满足用户不断增长的业务需求，也 就是说，大量高速的分组业务将在通信系统中占据主导地位。所以，原有的无线资沂 分配策略无法适应新的系统，应当重新考虑在多种业务并存的分组交换条件下的资源 分配问题。 q o s 是q u a l i t yo fs e r v i c e 的缩写，意思是服务质量，通常是指用户对网络所提供 的服务的满意程度。q o s 的目的是向用户提供端到端的服务质量保证，保证网络在发 生拥塞时重要业务信息的安全性，并保证网络资源的高效使用。q o s 有一套度量参数 指标，包括时延、时延抖动、带宽以及丢包率等。简而言之，q o s 就是网络为了保证 通信服务的质量而提供的一种处理机制。而分组调度和接入控制是该机制的两个重要 的组成部分。 无线网络中的资源管理与q o s 机制主要是执行以下几种功能： 1 、接入控制 接入控制决定一个呼叫是被接入还是被拒绝，接入控制的策略就是要在接受一个 呼叫请求的同时，既能够保证向新用户用户提供足够的资源以保证其q o s ，同时又不 影响到网络中原有的用户。 2 、分组调度 分组调度是一种保障用户之间共享可用的空中接口资源的机制。在w i m a x 系统 中，共有四种业务：u g s 、r t p s 、n r t p s 、b e ，这四种业务具有不同的q o s 特性，分 组调度就是针对分组数据不同的q o s 特性，对分组数据用户的业务进行管理和调度。 3 、切换策略 切换是一个重要的移动管理性能，它是蜂窝系统独有的功能，也是移动通信系统 的一个关键特性，直接影响整个系统的性能。切换不仅要求保证用户在穿越边界时仍 然能保证通信正常连接，而且还需要快速、有效，这样才有利于降低整个系统的干扰， 减少掉话，提高系统容量。 5 东南大学硕士学位论文 4 、功率控制 功率控制在无线通信系统的资源分配中占据重要的位置。一个优化的功率控制算 法可以使系统的容量大大增加，因而提高了系统频谱使用的效率。功率控制的目标是： 在为每个用户提供可以接受的服务质量的同时减少对其它用户的干扰。 2 2 无线通信系统中的分组调度算法 分组调度是系统资源管理的核心机制之一，是解决多个业务竞争共享资源问题的 有效手段。分组调度实现对链路带宽的管理，是按照一定的规则来决定队列中选择哪 个分组进行发送，使得所有输入业务能够按照预定的方式共享输出链路带宽。影响它 的主要性能参数包括带宽分配、时延和时延抖动等，是实现网络服务质量控制的核心 技术之一。 2 2 1 分组调度的策略和功能 分组调度一般采用c q s ( c l a s s i f i c a t i o n ，q u e u i n g ，s c h e d u l i n g ) 结构。每个接口有一个 调度器，每个调度器对应多个队列，这些队列之间共享输出链路容量。分组调度主要 有以下一些功能： l 、带宽分配 一个调度器可为特定的业务类提供最低的带宽保证，以确保分组规则从该类所在 队列取出。一个调度器也可以提供速率整形以限制该类队列被服务的频率。根据调度 器设计，可以对每一队列既强调上限带宽又强调下限带宽，或对某些队列只强调上限 或只强调下限带宽。 2 、时延控制 时延控制一般只针对高优先级的实时业务，在w i m a ) 【中，主要针对u g s ，r t p s 业务。 3 、优先级控制 在多媒体业务占主导的通信系统中，系统的优先级控制有着举足轻重的作用，优 先级控制方式可以是静态优先级，也可以是动态优先级。 业务调度算法的性能指标可以从三个方面来衡量，即有效性、公平性和复杂性。 各种衡量标准之间往往是矛盾的，某一个指标性能的提高可能是以牺牲另一个指标性 能为代价。因此，实际应用中使用的算法是需要综合考虑各种因素，根据实际情况协 调各方面的特性。 有效性主要包括对系统资源的利用率以及时延方面的特性。从系统和用户两方面 考虑，系统要求资源利用率高，而用户的要求体现在时延方面的特性。 分组调度算法的公平性是指应该以公平的方式对各业务流分配可用的带宽资源， 并且不同的业务流之间应该相互隔离，以防止突发业务或恶意流对正常业务流的影 响。 分组调度算法的复杂性是指调度算法是否容易实现。如果调度算法设计的过于复 杂，那么在高速网络中，就不能快速的调度并对分组进行转发，这样调度模块将成为 一个网络系统中的瓶颈，影响到整个系统的效率。 6 第2 章无线通信系统中的资源分配算法研究 2 2 2 无线分组调度算法的特点 无线环境下分组调度算法相对于有线网络业务调度算法有其特殊性，主要有下面 几个因素： 1 、无线链路可变性 无线网络与有线网络最大的区别就是传输链路的可变性。无线网络由于恶劣的传 输环境很容易发生错误，无线传输链路深受各种干扰和衰落的影响。因此，无线链路 的容量有非常高的可变性。在一些严重的突发错误状态下，无线链路有时会坏到没有 能力成功传输分组，此外，无线链路的容量还会随着位置变化而变化。在一个特定的 时间内，b s 可以同时与多个s s 进行通信，由于不同的物理位置，一些可以与进行无 错误传输，而其他的则不行，甚至不能通信，这就是所谓基于位置的错误。这就要求 调度算法具有特定的动态机制来处理链路因时间和位置而发生的变化。 2 、公平性 有线网络业务调度公平性通常是通过分配通信流一个特定的服务速率来保证的， 而且调度算法可以阻止不同业务流之间的互相干扰。但是无线网络中的公平性问题复 杂的多，如果不考虑链路可靠性，则很可能会发生根据一定的服务规则和公平原则调 度一个数据分组在无线链路上传输时，这条链路实际正处于错误状态，从而浪费传输 带宽。在这种情况下，延迟发送这个分组，直到链路从错误状态中恢复过来，莽以某 种方式补偿。 3 、服务质量 无线宽带网络将为不同的通信业务提供不同的服务质量，因此必须能区分和保证， 为了达到这个目标，相应的对q o s 支持的机制应该集成到调度算法中。 4 、吞吐量和频谱利用率 带宽是无线网络中最珍贵的资源，一个高效的调度算法应该致力于系统吞吐量和 频谱利用率最大化。 2 3 典型的无线分组调度算法 由于在无线通信系统中，实时性业务的q o s 要求最高，如何为实时性业务提供质 量保证，基本上是调度算法研究中的重点。所以在众多类型的调度算法中，我们关注 的基本都是实时性算法。实时性调度算法大致可以分成两类： 第一种是基于优先级的调度算法，基于优先级的调度算法给每个分组分配一个优 先级，在每次进程调度时，调度器总是调度那个具有最高优先级的分组来执行。根据 不同的优先级分配方法。 第二种是基于比例共享的调度算法。比例共享调度算法指基于系统资源的使用比 例的共享式的调度算法，其基本思想就是按照一定的权重比例对一组需要调度的分组 行调度，让它们的调度次序与它们的权重完全成正比。像轮询和公平队列等算法都属 于比例共享调度算法。比例共享调度算法的一个问题就是它没有定义任何优先级的概 念，所有的分组都根据它们相应的比例权重共享系统资源。 另外由于针对无线信道的时变和系统容量的有限性，还出现了专门以用户信道载 干比作为调度标准的m a xc i 算法等，下面分别进行分析。 7 东南大学硕士学位论文 2 3 1e d f o e n dd e a d l i n ef i r s t ) 最早截止时间有限算法 e d f 2 l 】属于动态优先级调度算法。在实时调度算法中，e d f 算法是使用最多的一 种动态优先级调度算法，该算法给就绪队列中的各个任务根据它们的截止期限 ( d e a d l i n e ) 来分配优先级，具有最近的截止期限的任务具有最高的优先级。这种调度算 法根据任务的资源需求来动态地分配任务的优先级，其目的就是在资源分配和调度时 有更大的灵活性。 此类算法的基本思想是：给每个队列分配一个时延参数d i 作为时延上界，以及分 组到达时间a i ，这两个参数分别对应队列中每个分组的q o s 参数中分组到达时间和 最大时延。为每一个到达的分组计算时间标签t i = a i + d i ，作为到期时间( d e a d l i n e ) ，然 后按照到期时间从小到大，将所有分组进行排队。每次调度具有最小到期时间t i 的分 组。它通过保证满足各任务对截止时间的要求的来确定任务的优先权。 算法将保证到达分组的时延要求作为调度算法的首要关键因素来考虑。但是算法 中没有体现对无线通信系统中信道条件的时变特性的关注，因此对系统吞吐量以及不 同用户之间的公平性没有考虑。算法复杂度主要体现在每个分组的时延标签的计算和 排序。 2 3 2r r o r o u n dr o b i n ) 轮询调度算法 轮循调度即r o u n dr o b i n 调度【2 2 ，2 3 1 ，简称为r r 调度，其目标是保障用户间的公 平性，即保障每个用户都能得到一定的服务时间和最低时延要求。保障用户公平性和 最低服务质量的调度算法在文献中有较全面的介绍，这里仅描述该算法思想的基本特 点，由此思想可以衍生出多种基于轮循思想的公平性调度算法。r r 调度的要点如下： 在调度实体中，非空的源队列以循环方式进行服务； 一个用户被再次服务之前，其它的非空源队列必须都被服务一次； 当前帧中被服务的用户不能在紧接的下一帧中继续被服务，除非调度器中只 有一个非空源队列： 调度器可以对一个帧中所选定的源队列的数据进行分组。 在存h a r q 机制的系统中，调度器总是优先传输过程产生的h a r q 重传分组， 因为尽快传输重传分组，可以提高终端的合并解码性能和降低终端的复杂度，处理完 重传分组后，按照f i f o 原则依次对有分组等待传输的用户进行调度，r r 调度中，系 统维护一个等待服务的用户标识队列，当一个新用户进入等待服务的队列，或一个用 户被调度后，将其插入该标识队列的队尾。 轮循调度是一种简单调度算法，以循环分配资源的方式保障用户间的公平性，但 没有考虑无线信道的时变特点，也没有利用无线信道所提供的信息( 如载干比值等) ， 因此它难以充分利用系统资源以达到较高的系统容量。另外从算法复杂性考虑，由于 r r 调度本质上是f i f o ，因此是一种复杂度很低的简易算法。 2 3 3w r q ( w e i g h t e df a i r n e s sq u e u i n g ) 加权公平队列算法 岍q 算法是属于g p s ( g e n e r a l i z e dp r o c e s s o rs h a r i n g ) 模型的一种经典算法，g p s 模型是一个理想化的流模型，该模型假定每一个队列中的业务元可以无限小，队列之 间具有相同的优先级，调度器可以根据各队列的共享比例同时服务所有的队列，该模 型构建的是能够使各业务流真正公平的共享资源的服务器，它能够为每个业务流提供 8 第2 章无线通信系统中的资源分配算法研究 明确的端到端时延上限保证。该模型目前仅用于理论分析。 加权公平队列w f q 分为两种，一种是基于流的加权公平队y u ( w f q ) ，目标是确 保拥塞发生