（通信与信息系统专业论文）宽带无线通信系统中分组调度算法的研究.pdf

摘要 摘要 随着无线数据服务和多媒体应用需求的快速增长，人们期待未来的无线网络能够满足为多娄业务提 供分层q o s 服务的需求，因此支持不同q o s 服务的分组调度算法成为宽带无线通信网络发展的关键。 正交频分复用( o f d m ) 技术作为一种无线环境下的高速传输技术，具有良好的抗多径信道干扰能力， 因此本文主要研究基于o f d m 技术的固定宽带无线接入系统中的多业务分组调度算法。 本文首先介绍了现有有线和：无线网络中的调度算法，概括了它们的发展以及各自的优缺点，并简单 描述i e e e 8 0 2 1 6 - 2 0 0 4 防议中的调度服务机制。然后从网络模型、节点模型、m a c 层仿真模块以及应用 层业务参数、物理层参数五个方面重点介绍了基于o p n e t 的宽带无线接入系统仿真平台。接着在第三 章介绍了加权r o u n d r o b i n ( w r r ) 、最大载干比( m a xc i ) 以及q u a l c o m m 比例公平调度( q p f ) 三 种经典的分组调度算法，描述了前两种算法在仿真系统中的实现流程并对算法性能作了简单分析，重点 分析了o p f 算法性能及存在问题，为第四章长帧比例公平调度算法( l f p f ) 的提出做铺垫。第四章介 绍了l f p f 调度算法，它是比例公平思想在宽带无线接入系统m a c 层框架和长帧结构下的实现，文中 给出了算法规则与比例公平定义的致性证明，分析了“饥饿”避免机制以及与m a xc i 算法相比的优越 性。第五章介绍了联合加权( j w ) 调度算法，它结合了信道情况、用户等级、业务等级、时延补偿四个 影响算法性能的重要因素，灵活的满足不同系统不同场景的需求。通过四个因子权重的调整，可以使得 性能逼近l f p f 调度算法，时延及吞吐量性能较好，可控性强。论文第六章对四种仿真场景下的不同算 法的仿真结果作了分析和比较，验证了l f p f 以及j w 调度算法的良好性能。最后，第七章简单总结了 全文工作，并进一步探讨在此领域可以进一步研究的思路和方向。 关键词：正交频分复用，服务质量，分组调度，加权r o u n d r o b i n ，最大载干比，比例公平 a b s 打a c t a b s t r a c t e v e r yo n ee x p e c t st h ef u t u r ew i r e l e s sn e t w o r kc a np r o v i d eq o sg u a r a n t e e sf o rd i f f e r e n ta p p l i c a t i o n sw i t h t h er a p i di n c r e a s eo 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 s w i t hs u p p o r to fd i f f e r e mq o sr e q u i r e m e n t sb e c o m et h ek e yp o i n to ft 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 s c o m m u n i c a t i o nn e t w o r k s o f d mt e c h n o l o g y ，a sa h i g h - s p e e d t r a n s m i s s i o n t e c h n o l o g y f o rw i r e l e s s e n v i r o n m e n t ，i sg o o da ta n t i - m u l t ip a t hf a d i n g s ot h et h e s i sm a i n l yp r o v i d e st h er e s e a r c hr e s u l t sf o rd i f f e r e n t p a c k e ts c h e d u l i n ga l g o r i t h m si nf i x e db 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 s f i r s tc h a p t e ri n t r o d u c e st h es c h e d u l i n ga l g o r i t h m si nw i r e da n dw i r e l e s sn e t w o r k s ，i n c l u d i n gt h e i rh i s t o r i e s ， a d v a n t a g e sa n dd i s a d v a n t a g e s t h ed e s c r i p t i o no fs c h e d u l i n gm e c h a n i s mf o rs t a n d a r di e e e 8 0 2 1 6 - 2 0 0 4i sa l s o i n c l u d e ds e c o n dc h a p t e rs h o w st h eb r o a d b a n dw i r e l e s sa c c e s ss y s t e ms i m u l a t o ro no p n e t i tc o n s i s t so ff i v e p a r t s ，n e t w o r km o d e l ，n o d em o d e l ，m a cl a y e rs i m u l a t i o nm o d u l e ，a p p l i c a t i o np a r a m e t e r sa n dp h yl a y e r p a r a m e t e r s t h i r dc h a p t e rp r o v i d e s3c l a s s i c a la l g o r i t h m s ，w e i g h t e dr o u n d r o b i n ( w e d s ) ，m a xc 1 ，a n dq - p f f r o mq u a l c o m m t h ef o r m e rt w oa l g o r i t h m sa r es i m p l ya n a l y z e d a n dt h eq p fa l g o r i t h mi sd e t a i l e da n a l y z e d ， s u c ha sp e r f o r m a n c e ，p r o b l e m sa n ds oo n c h a p t e r4p r e s e n t st h el f - p fa l g o r i t h m i ti st h ei m p l e m e n t a t i o no f p fw i t hl o n gf l a m es t r u c t u r eu n d e rb w a m a c l a y e ra r c h i t e c t u r e a n dt h i sc h a p t e ra l s op r o v e st h ec o n s i s t e n c y o ft h i sa l g o r i t h mw i t hd e f i n i t i o no fp f t h ea v o i d a n c eo f h u n g r y a n da d v a n t a g e sc o m p a r e dw j mm a xc ia r e a n a l y z e d c h a p t e r5s h o w st h ej wa l g o r i t h m i tc o n s i s t so fc h a n n e lc o n d i t i o n ，u s e rp r i o r i t y , a p p l i c a t i o np r i o r i t y d e l a yc o m p e n s a t i o n i ti sf l e x i b l ee n o u g ht os a t i s f yd i f f e r e n ts y s t e m sa n dd i f f e r e n ts c e n a r i o s t h r o u g ht h e t u n i n go ft h ef o u rw e i g h t s t h ep e r f o r m a n c eo fj wa p p r o a c h e st h ep e r f o r m a n c eo fl f p fi t sp e r f o r m a n c eo f d e l a ya n dt h r o u g h p u ti sq u i t eg o o d ，a n di ti se a s yf o rc o n t r o l t h el a s tc h a p t e rp r o v i d e st h ec o n c l u s i o no f t h et h e s i s a n di ts h o w st h ep r o s p e c to f t h i sf i e l da tt h ee n d k e y w o r d s ：o r t h o g o n mf r e q u e n c yd i v i s i o nm u l t i p l e x i n g , q u a l i t yo fs e r v i c e ，p a c k e ts c h e d u l i n g ，w e i g h t e d r o u n d - r o b i n ，m a xc f ! ，p r o p o r t i o n a lf a i r n e s s i i 插圈目录 插图目录 图1 宽带无线接入系统网络模型1 0 图2b s 节点模型11 图3s s 节点模型1 2 图4 u e 节点模型 图5o n - o f f 模型1 3 图6 频分双工方式下o f d m 帧结构1 5 图7 各层开销示意1 7 图8w r r 算法简单流程图。 图9m a xc i 算法简单流程图 图1 0l f - p f 算法简单流程图2 8 图i1j w 算法总流程图 图1 2 测距请求信令带宽分配流程图3 6 图1 3u g s 数据带宽分配流程图 图1 4r t p s m t p s 服务b r 信令带宽分配流程图 图1 5r t p s n r t p s 数据带宽分配流程图3 9 图1 6b e 数据带宽分配流程图4 0 图1 7 函数y q 和y = p o w e l ( x ，2 ) 曲线比较4 2 图1 8v o l p 业务平均时延性能比较( 3 0u e s ) 4 3 图1 9v o i p 业务平均时延抖动性能比较( 3 0u e s ) 图2 0v o i p 业务吞吐量性能比较( 3 0l i e s ) 图2 1 针对v o i p 业务的另一种服务方式4 5 图2 2v o d 业务平均时延性能比较( d = 1 0 0 m ) 4 6 图2 3v o d 业务平均时延性能比较( d = 5 0 0 m ) 4 6 图2 4v o d 业务平均时延性能比较( d = 1 0 0 0 m ) 4 6 图2 5v o d 业务平均时延性能比较( d = 1 5 0 0 m ) 4 6 图2 6v o d 业务平均时延性能比较( d = 2 0 0 0 m ) 4 7 图2 7v o d 业务平均时延抖动性能比较( d f l 0 0 m ) 4 7 图2 8 v o d 业务平均时延抖动性能比较( d = 5 0 0 m ) ，4 7 图2 9v o d 业务平均时延抖动性能比较( d = 1 0 0 0 m ) 4 8 v 1 插图目录 图3 0v o d 业务。f 均时延抖动性能比较( d = 】5 0 0 m ) 4 8 图3 lv o d 业务平均时延抖动性能比较( d = 2 0 0 0 m ) 4 8 图3 2v o d 业务吞吐量眭能比较( d = 1 0 0 m ) 4 9 图3 3v o d 业务吞吐量性能比较( d = 5 0 0 m ) 4 9 图3 4v o d 业务吞吐量性能比较( d = 1 0 0 0 m ) 4 9 图3 5v o d 业务吞吐量性能比较( d = l s 0 0 m ) 图3 6v o d 业务吞吐量性能比较( d = 2 0 0 0 m ) 一 图3 7f t p 业务平均时延性能比较( d = 1 0 0 m ) ，5 0 图3 8f t p 业务平均时延性能比较( d = 5 0 0 m ) 图3 9f t p 业务平均时延性能比较( d = 1 0 0 0 m ) 图4 0f t p 业务平均时延性能比较( d = 1 5 0 0 m ) 图4 1f t p 业务平均时延性能比较( d - 一2 0 0 0 m ) 图4 2f t p 业务吞吐量性能比较( d = 1 0 0 m ) 。5 2 图4 3f t p 业务吞吐量性能比较( d = 5 0 0 m ) 5 2 图4 4f t p 业务吞吐量性能比较( d = 1 0 0 0 m ) 5 2 图4 5f t p 业务吞吐量性能比较( d = 1 5 0 0 m ) 。 图4 6f t p 业务吞吐量性能比较( d - - 2 0 0 0 m ) 一 图4 7f t p 业务平均误比特率性能比较， ! ；：! 5 2 5 3 表1v o l p 业务参数 表格目录 表2v o d 业务参数1 3 表3 f t p 业务参数。 表4h n 甲业务参数1 4 表5 仿真服务类q o s 参数表。1 6 表6 物理层基本参数 表7 调制编码方案1 8 表8 时延补偿步进表3 4 表9 分用户等级的j w - i 算法结果 表1 0 混合业务场景仿真结果表5 5 v i l l 缩略语 缩略语 a m c a d a p t i v em o d u l a t i o nc o d i n g 自适应调制技术 a r pa d d r e s sr e s o l u t i o np r o t o c o l 地址解析协议 a r q a u t o m a t i cr e t r a n s m i s s i o nr e q u e s t 自动重传 b eb e s te f f o r t 尽力而为服务 b p s k b i n a r yp h a s es h i f tk e y i n g 二进制相移键控 b rb a n d w i d t hr e q u e s t 带宽请求 b sb a s es t a t i o n 基站 b b r o a d b a n dw i r e l e s sa c c e s s 宽带无线接入 c i f q c h a n n e l - c o n d i t i o ni nd e p e n d e n tp a c k e tf a i rq u e u e i n g 独立于链路状况的分组公平排队 c s d p sc h a n n e ls t a t ed e p e n d e n tp a c k e ts c h e d u l i n g 基于链路状态的分组调度 d c dd o w n l i n kc h a n n e ld e s c r i p t o r 下行信道描述符 d i u cd o w n l i n ki n t e r v a lu s a g ec o d e 下行间隔使用码 d l 执pd o w n l i n km a p 下行链路映射 e d fe a r l i e s td e a d l i n ef i r s t 最早到期优先 f d d f r e q u e n c yd i v i s i o nd u a l 频分双工 f i f 0f i r s ti nf i r s to u t 先进先出 f t pf i l et r a n s f e rp r o t o c o l 文件传输协议 g p sg 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 s g r a n t p e r s s 基于s s 分配带宽 h t t p h y p e r t e x tt r a n s f e rp r o t o c o l 超文本传输协议 i ei n f o r m a t i o ne l e m e n t 信息元素 i pi n t e m e tp r o t o c o l 网际协议 i w f q i d e a l i z e dw t r e l e s sf a i rq u e u e i n g 理想无线公平排队 j wj o i n tw e i g h t 联合加权调度 l f - p f l o n gf r a m e p r o p o r t i o n a lf a i r n e s s 长帧比例公平调度 l t f s l o n gt i m ef a i rs e r v e r 长时公平服务器 m a cm e d i u ma c c e s sc o n t r o l 媒体接入控制 m a x c im a x i m u mc a r r i e r i n t e r f e r e n c e 最大载干比 n r t p sn o n - r e a l - t i m ep o l l i n gs e r v i c e 非实时轮询服务 o f d m 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 x i n g 正交频分复用 o f d m a 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 ea c c e s s正交频分多址 p f p r o p o r t i o n a lf a i r n e s s 比例公平 缩略语 p h y p h y s i c a l物理 p d up r o t o c o ld a t au n i t 协议数据单元 q a mq u a d r a t u r ea m p l i t u d em o d u l m i o n正交幅度调制 q o sq u a l i t yo f s e r v i c e服务质量 q p s k q u a d r i p h a s es h i f tk e y i n g四相移键控 r t p sr e a l t i m ep o l l i n gs e r v i c e 实时轮询服务 s b f as e r v e rb a s e df a i r a p p r o a c h 基于服务的公平方式 s c f q s e l f c l o c k e df a i rq u e u e i n g 自同步公平排队 s ss u b s c r i b e rs t a t i o n 用户站 s t f q s t a r t t i m ef a i rq u e u e i n g 开始时间公平排队 t d m at i m ed i v i s i o nm u l t i p l ea c c e s s 时分多址方式 u c d u p l i n tc h a n n e ld e s c r i p t o r上行信道描述符 u eu s e re q u i p m e n t 用户设备 u o su n s o l i c i t e dg r a n ts e r v i c e 直接带宽分配服务 u i u c u p l i n ki n t e r v a lu s a g ec o d e上行间隔使用码 u l m a p u p l i n km a p上行链路映射 v o d v i d e oo nd e m a n d 视频点播 、，o i pv o i c eo v e ri p i p 电话 w e d d w e i g h t e de a r l i e s td u ed a t e加权最早到期优先 w f qw e i g h t e df a i rq u e u e i n g加权公平排队 w f 。q w o r s t - c a s ef a i rw e i g h t e df a i rq u e u e i n g 最坏情况公平加权公平排队 w f sw i r e l e s sf a i rs e r v i c e 无线公平服务 w r r w e i g h t e dr o u n d r o b i n加权r o u n d r o b i n x 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢 意。 研究生签名： 拯硷日期：_ 2 亟纽站 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸 质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包 括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 繇一翩虢镣励； 7 第一章绪论 1 1 研究背景 第一章绪论 1 1 1 宽带无线接入系统简介 本文研究的调度算法主要应用于宽带无线通信系统中的一种宽带无线接入系统( b r o a d b a n d w i r e l e s s a c c e s s ，b w a ) ，采用的空中接口协议是i e e e8 0 2 1 6 2 0 0 4 ，主要应用于固定接入的无线城域网。 本节简单介绍该系统状况及空口协议。 宽带无线接入系统是定位于宽带l p 城域网的无线接入系统，其最大覆盖范围是5 0 公里。主要用于 固定无线宽带接入、地理位置分散的信息热点回程传输或大业务量用户的接入。作为一种城域网接入手 段，采用了多种技术来应对建筑物阻挡情况下的非视距和阻挡视距的传播条件，因此可以实现非视距传 输。宽带无线接入系统可以作为企业t 1 或家庭x d s l 和c a b l em o d e m 的无线扩充技术，或者取代有线 宽带接入的市场。因此从这个意义上说，宽带无线接入系统是解决“最后一公里”的通信接入问题。特别 是对于很多发展中国家或偏远地区没有电缆和数字用户线路( d i g i t a ls u b s c r i b e rl i n e ，d s l ) 服务，有线 基础设施费用较高，通过宽带无线接入网的布建将助于打开此市场，也就是最后一公里的无线宽带布建。 i e e e8 0 2 1 6 - 2 0 0 4 协议主要规范了支持多媒体业务的固定宽带无线接入系统的空中接口，包括：媒 体接入控制( m e d i u m a c c e s sc o n t r o l ，m a c ) 层( 包括加密子层) 和物理( p h y s i c a l ，p h y ) 层、毫米波频 率范围、点到多点拓扑结构、用户站和基站。该标准是一个基于连接的标准，其a t m 和基于分组的汇 聚子层可接收来自各种上层协议的数据，空中接1 2 1 提供全服务质量( q u a l i t yo fs e r v i c e , q o s ) 支持。 8 0 2 1 6 2 0 0 4 接入系统要高效地满足每终端多个连接和多种q o s 需求，它利用各种请求机制平衡无需竞 争的接入的稳定性和竞争接入的效率。根据不同的工作环境，m a c 结构可以支持多种物理层描述。当 工作频段为1 0 6 6 g h z ，p h y 层采用单载波( s i n g l ec a r r i e r , s o 调制。工作频段在li g h z 以下，p h y 层可 以选择正交频分复用( 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 x i n g , o f d m ) ，正交频分多址( o r t h o g o n a l f r e q u e n c yd i v i s i o nm u l t i p l e a c c e s s ，o f d m a ) ，s c 三种调制方式。本文主要研究基于o f d m 的固定宽带 无线接入系统。 1 1 2 有线网络中调度算法研究概述 最早在实际路由器中获得应用的调度算法是先进先出( f i r s t i n f i r s t o u t ，f i f o ) 算法。这种调度方法 完全依据分组的到达次序进行输出。如果某个流在一段时间内发生业务突发，到达的分组数目较多，那 么其他的流就无法得到正常的服务，因此，f i f o 无法保证各个流之间的公平性，各个流之间的独立性也 不好。 1 9 8 6 年左右，h a h n e 提出了加权r o u n d - r o b i n ( w e i g h t e dr o u n dr o b i n ，w r r ) 算法【l 】，这种算法摒 弃了这种依靠分组到达次序的排队方法，通过为各个业务流合理地分配权值来控制它们获得发送的机会， 公平性有所增强，但是，在处理变长分组的时候，效果仍然不理想。 9 0 年代，基于分组传输综合业务的实际需求带动了对于调度算法的研究。d e m e r s 2 ，p a r e k h 和 g a l l a g e r 3 4 等人先后研究了基于流体流的并行服务模型，即通用处理器共享( g e n e r a l i z e dp r o c e s s o r 1 东南大学硕士学伯讫史 s h a r i n g ，g p s ) ，在这种模型中，业务流被看成是可以无限分割的流体，而服务器可以同时为多个业务流 同时服务，服务的尺度也可以无限小。因此，g p s 模型可以满足流之问的独立性，并可以实现对不同时 延带宽要求的业务赢的区分服务，为调度算法的后期研究提供了理论参考。 g p s 模型是一个理想化的公平模型，在实际系统中不可能实现。这是因为实际系统中，输出链路在 同一时刻只能服务一个分组，而且只有当传送完一个分组之后才能够服务其他的分组。也就是说，实际 系统中，调度的“粒度”要比g p s 模型粗得多。根据g p s 模型，p a r e k h 和g a l l a g e r 提出了基于g p s 分组 化近似的加权公平排队( w e i g h t e df a i rq u e u e i n g ，w f q ) 调度算法【3 】【4 】。这是第一个真正意义上的公平 调度算法，可以提供有界的时延保证。w f q 在路由器的设计中获得了实际应用。但是在处理高速分组调 度时，w f q 显得复杂度相对较高。 后来的学者主要从减少计算复杂度的方面对w f q 作了一些改进和拓展，如g o l e s t a n i 在1 9 9 4 年提 出的自同步公平排队( s e l f c l o c k e df a i rq u e u e i n g , s c f q ) 算法，通过牺牲了一定的公平性来换取了复杂 度的降低【5 】。1 9 9 6 年，b e n n e t t 和h z h a n g 等人从另外的角度定义了公平性，并获得一种比w f q 更公 平，但复杂度仍较高的最坏情况公平加权公平排队( w o r s t - c a s ef a i rw e i g h t e df a i rq u e u e i n g ，w f 2 q ) 调g t 算法【6 】。 1 9 9 7 年，他们改进了w f 2 q 算法，新算法w f 2 q + 在复杂度方面有所降低【7 】。同年，g o y a l 等人改 变了计算虚拟时间的计算方法，提出了开始时间公平排队( s t a r t - 2 n m ef a i rq u e u e i n g , s t f q ) 算法，这种 算法同样具有低复杂度和好的公平性 8 】。 g p s 模型虽然简单，但也有一定的局限性。在g p s 模型和其近似化算法中，对业务的需求只使用速 率一个参数来进行描述，这就使得时延与带宽的分配互相耦合在一起。也就是说，如果需要低时延，那 就必需高带宽。因此这对于低时延、低带宽的业务无法获得高的资源利用率。因此，对于时延敏感性业 务，需要有其他的算法进行q o s 的保证。 最早到期优先( e a r l i e ad e a d l i n ef k s t , e d f ) 算法是这类算法中的代表【9 】，在e d f 算法中，为每种业 务( 或其服务队列) 分配了一个时延参数，表示允许在系统中停留的时延期限。e d f 算法根据分组到达时 间和所属业务时延期限之和对所有分组进行排序，先服务最快要到期的分组，因此它在分组超时丢包率 方面具有最好的性能。e d f 算法在发展中得到了一些扩展，派生出了如针对时延的d e l a y e d d 算法和针 对时延抖动的j i t t e r - e d d 调度算法以及可以提供对业务流进行更加灵活的区分控制的加权最早到期优先 ( w e i g h t e de a r l i e s td u ed a t e ，w e d d ) 算法等等。 1 9 9 5 年左右，c r u z 等人首先提出了基于服务曲线的q o s 模型，从另外的角度解决了时延和带宽的 解耦问题 i o 】。并在后续的几年中，许多学者基于服务曲线的理论提出了很多新的算法，如最早期限优 先和分级公平服务曲线等等( 在这些模型中，通过使用非线性的服务曲线，实现了带宽和时延的解耦) 。 一方面他们也发展了服务曲线的理论，并将其研究推进到现在被称作网络微积分学的学科。 此外，还有诸如基于优先级的调度算法、随机调度算法、分类调度算法等等。可以满足不同的调度 目标要求。 1 1 3 无线网络中调度算法研究概述 无线调度算法的研究要稍微晚一些。1 9 8 9 年，a d e m e r s 等人最早将无线网络中区域性和突发错误 2 第一章绪论 特性考虑进调度算法，提出了依靠链路状态的分组调度算法( c h a n n e ls t a t e d e p e n d e n t p a c k e ts c h e d u l i n g c s d p s ) 【11 】。1 9 9 7 年，l u 和b h a r g h a v a 等人以w f q 为参照，提出了蜂窝结构无线网络中的理想公平 调度算法( i d e a l i z e dw i r e l e s sf a i rq u e u e i n g , i w f q ) 1 2 。在其论文中，作者指出无线链路突发错误会导致 有线网络发展起来的调度算法在无线环境中应用时的失效。因为有些处于积压状态的业务流( 设为f i ) t l o 使根据w f q 等算法的调度结果获得了发送机会也会出于链路失效而将发送机会转让给其他的业务流( 设 为f 2 ) ，从而导致公平性无法保证。为了保证公平性，就需要对发生链路突发错误的业务流在其恢复正常 传输时对之进行补偿。i w v q 中的补偿模型是隐含的，算法保持了服务的顺序标记，可以记录滞后流滞 后的服务量。这样，滞后流一旦检测到链路恢复正常，就会马上启动发送过程，并将滞后的业务量弥补 过来。 然而i w v q 的补偿过程并不科学，会引起所谓的隔离性问题。因为对f l 的补偿可能会影响到对于正 常业务流的正常服务。为了解决隔离性问题，以开始时间公平排队s t f q 为参照，s t i o i c a 等人提出了独 立于链路状况的分组公平排队( c h a n n e l c o n d i t i o ni nd e p e n d e n tp a c k e tf a i rq u e u e i n g , c i f q ) 【1 3 】，该算 法的补偿模型比i w f q 更加合理，能够使得补偿行为更加平滑，从而提高了算法对业务流之间调度的隔 离度。他们在算法中定义了超前服务( l e a d ) 和滞后服务( l a g ) 的概念，以始终正常的业务流( 设为6 ) 为参 照，f 1 和f 2 分别可以称作滞后流和超前流。算法规定补偿行为只能在超前流和滞后流之间进行，而不能 形响正常流所得到的服务。而且仅当超前流主动“交出超前份额”的时候，滞后流才能够得到补偿。通过 这种可控的补偿过程较好的解决补偿和隔离之间的矛盾。 1 9 9 8 年，p r a m a n a t h a n 等人提出的基于服务的公平方式( s e r v e r b a s e d f a i r a p p r o a c h , s b f a ) 1 4 1 调 度算法从另外的角度提供了对差错流的补偿机制。在s b f a 中，系统预留了一部分信道带宽用作补偿， 而不是在滞后流和超前流之间交换时隙来实现补偿。算法维护了一个虚拟流，称作长时公平服务器( l o n g t i m ef a i rs e r v e r , l t f s ) 来提供补偿并根据业务流的权值为之分配用作补偿的预留带宽。如果为某个流分 配了时隙但是由于链路错误无法进行发送，则l t f s 就将该时隙在l t f s 的队列中缓存起来，而系统最终 会将l t f s 与其他正常业务流一同分配带宽进行调度。在s b f a 中没有超前服务的概念。滞后业务流得 到补偿的顺序依据其时隙在l t f s 中的顺序而定。算法维护了业务流之间的长时公平性，但是对业务流 不提供短时的公平性保证，也没有最坏情况下的时延界。针对i w f q 的缺点和在无线网络上传输时延敏 感型业务的需求，l u 和b h a r g h a v a 等人又提出一种新的算法无线公平服务( w i r e l e s sf a i rs e r v i c e ，w f s ) 算法【1 2 】。w f s 将理想公平、信道状态及补偿与惩罚相结合，实现了时延和带宽的解耦，同时实现了长 时公平性和短时公平性的保证，此外，w f s 算法具有较好的隔离性，实现了超前服务量的良好降级性能。 这些研究开创了无线调度算法的研究局面，但是对于无线环境的考虑仅仅局限于突发链路错误的影 响，相对简单。1 9 9 9 年c a s i m i r o 等人研究了自适应调制系统的分组调度问题，考察了r o u n d r o b i n 和最 大载干比( m a x i m u mc a r r i e r i n t e r f e r e n c e ，m a xc i ) 这两种简单的调度算法下系统吞吐量的变化【1 5 】。在 2 0 0 0 年，q u a l c o m l n 公司的j a l a l i 等人在对h d r 系统中提到了他们针对h d r 系统所设计的比例公平调 度算法( p r o p o r t i o n a lf a i r n e s s ，p f ) 【1 6 。值得一提的是，这些算法虽然比较简单，但是将无线调度的目 标从公平性、时延等传统性能需求扩展到了对无线资源进行优化的新视角，开拓了调度算法的一个新的 研究领域。 3 东南大孚硕上学伸论上 1 1 4 无线网络的特点对调度的影响 从排队论的视角来看，无线系统和有线系统的主要区别在于服务者行为方面的差别。一条有线链路 通常可以用一个以恒定比特速率进行服务的单服务者模型来表示，而同一时刻，只能有个业务流占用 实际带宽。而在无线系统中，是一个不定比特速率服务的多服务者模型，情况要复杂得多。归结起来， 影响无线系统的分组调度算法，使之与有线系统的分组调度算法呈现较大差异的因素主要有以下几个方 面： 无线链路中的突发误码 目前，高速分组网络中对链路误码率的要求在不大于1 0 4 的数量级。当前的光纤通信技术完全可以 提供这种链路保证。但在无线通信中，现有技术对误码率的保证一般在1 0 6 1 0 。的水平。这种高的误码 率对差错敏感性的数据业务影响很大。而且，无线环境中，这种链路质量通常是与移动台的位置相关的， 不同的移动台所感受到的链路质量并不相同。这对于调度算法，特别是公平性的保证影响很大。往往使 得保证公平的“e f f o r t 得不到相应公平的 r e s u l t 【1 8 】。所以努力等于结果，对应的是有线网络的情况。 对分组的调度区分上下行 在蜂窝网络中，所有处于基站覆盖范围内的用户都和基站维持通信。无论上行通信还是下行通信都 由基站来控制。因此，在小区范围内，基站是唯一合乎逻辑的调度执行实体。对于下行方向，基站容易 了解每个业务流占用缓存的情况；而对于上行业务流的信息，基站就很难及时了解到。比如，某个上行 业务流何时开始发送，何时完毕，当前等待上传的业务量有多少。宽带无线接入系统通过m a c 层的随 机接入、轮询和捎带请求机制来获得用户站的数据发送需求。因此，m a c 层的具体方案是会对上行调 度产生影响，是研究上行调度过程中所必须要考虑的问题。由于在有线网络中会采用其他的组网方式或 技术来保证q o s 调度，因此，在有线网络中很少看到有针对上行调度问题的研究，而上行调度正是无线 网络的难点问题。 某些无线系统中的动态比特速率服务行为 调度算法的研究涉及带宽资源分配，在性能分析研究中，几乎所有的调度算法都假定总的链路的工 作带宽是一个常数c 。这种假设在有线网络中是成立的。在无突发错误的状态下，现有的许多使用固定 调制方式的无线网络也满足这个假设。但是，近年来，自适应调制技术( a d a p t i v e m o d u l a t i o n c o d i n g , a m c ) 在无线系统中得到广泛使用，改变了这种局面。使用自适应调制技术之后，系统可以根据用户的链路状 况动态调制方式，从而使得系统的工作带宽不再是一个常数，而成为一个随着信道质量变化的参量。自 适应调制方式支持的时分复用系统与传统系统在实际净荷比特速率的支持能力上有一些差异，这对调度 器的设计将产生影响。特别的，多个用户不同的信道状态使得系统中存在所谓“多用户分集”现象，因而 也就出现了优化系统容量的可能性。这对于调度器的设计将带来深远影响。 需要对链路质量进行测量和反馈 由于调度器位于基站，而调度需要考虑链路速率、链路质量以及上下行的要求。而这就要求对链路 质量进行测量和