（通信与信息系统专业论文）新一代移动通信系统分组调度算法的研究.pdf

摘要 摘要 邂年来移动逶穰技术褥到了嵩速豹发展，掰一技移动遇绩系统豹觋究也建之应 运丽生。由于无线黼络能够提供的带宽资源楚非常有限的，如果想要在薪一代移 动通信系统中支持驻高速率的数据传输、更可靠的q o s 保障以及更丰寓的业务类 型，就必须设计出更好的无线分组调度算法，来进行无线资源的调配靼优化，在 尽萋低豹复杂度瓣鏊穑上，霞鸯袋的謦宽麓够褥到尽霹怒充分帮舍瑗黪嚣蘑，挺 高系统性能的上限。 本文对b 3 g 4 g 系统中的分组调度算法做了较为深入的研究，在第二章中介绍 了本文掰羡爰戆蒸予l t e 系绞级翥求豹谤寞擎台。在第三章孛，提爨了一穆基予 二次分配的增强裂调度算法，通过对无线资源进行预分酝和二次分配，以少量提 高运算复杂度的代价，来实现慰为合理的调度和无线资源的优化。第四章通过对 b 3 g 4 g 系统中的多用户m i m o 调度算法遴行研究，提掇了一静基予容量的混合 式m i m o o f d m 调度算法，哥疆在奎区弱户数较少嚣章这餐较高鲍系缀容量，并在 小医用户数较多时，以较低的运算复杂度达刹接近多用户最优调度算法的性能。 通过对仿真结论的分析，又提出了两点设想：一种基于系统负荷的动态调度算法 窝一释基予q o s 瓣混合式调瘦舞法，莠分掇了这瑟魏算法豹霞蔌点。 关镳词：多输入多输出正交频分复用分组调度资源分配用户选择 a b s t r a c t a b s t r a c t 3 i nr e c e n ty e a r s ，m o b i l ec o m m u n i c a t i o ni sd e v e l o p i n gd r a m a t i c a l l ya n dt h en u m b e r o fm o b i l eu s e f sb e c o m e sm u c hl a r g e rw i t hi n c r e a s e dr e q u i r e m e n to fh i g h s p e e dd a t a t r a n s m i s s i o n s or e s e a r c ho nt h el l c wg e n e r a t i o nm o b i l ec o m m u n i c a t i o nt e c h n o l o g yh a s b e g u n b e c a u s eo ft h e l i m i t e df r e q u e n c ys p e c t r u m 。i t sn e c e s s a r yt os c h e d u l ea n d a l l o c a t er a d i ot e s 0 1 1 r c , ea so p t i m a l l ya sp o s s i b l ef o rm o l eh i g h - s p e e dd a t at r a n s m i s s i o n ， s t e a d yq o sg u a r a n t e ea n dv a r i o u sk i n d so fs e r v i c e s t h ep a c k e ts e h e d u l i n ga l g o r i t h m s s h a l lb ep r o p o s e dt og r e a t l yi m p r o v et h es y s t e mp e r f o r m a n c ew i t hl o wc o m p l e x i t y t h i sp a p e rd i s c u s s e si nd e p t ht h es c h e d u l i n ga l g o r i t h m si nb 3 g 4 gs y s t e ma n di n c h a p t e r2i n t r o d u c e st h el t es y s t e ml e v e ls i m u l a t i o np l a t f o r mu s e di nt h i sp a p e r c h a p t e r3p r o p o s e sar c a l l o c a f i o n - b a s e de n h a i l e e ds c h e d u l i n ga l g o r i t h mw h i c hc a n r e a l i z em o r er a t i o n a ls c h e d u l i n ga n do p t i m i z i n go fr a d i or e s o u r c ew i t hal i t t l ei n c r e a s e i nc o m p l e x i t y i nc h a p t e r4 ，t h i sp a p e r p r o p o s e sac a p a c i t y - b a s e dh y b r i dm i m o - o f d ms c h e d u l i n g a l g o r i t h m i ts u p p o r t sh i g h e rs y s t e mc a p a c i t yw h e nt h e r ea r eas m a l ln u m b e ro fu s e r si n ac e l la n di tc a np e r f o r ma p p r o x i m a t e l ya se x c e l l e n ta so p t i m i z e dm u l t i - u s e rs c h e d u l i n g a l g o r i t h mw i 也m u c hl o w e rc o m p l e x i t y t h e nc o n s i d e r i n gt h er e s u l t so fs i m u l a t i o n 。t w o i d e a sh a v eb e e np u tf o r w a r d ：as y s t e ml o a d - b a s e dd y n a m i cs c h e d u l i n ga l g o r i t h m ，a n da q o s - b a s e dh y b r i ds c h e d u l i n ga l g o r i t h m ，a n dt l l e i ra d v a n 协g e sa n ds h o r t c o m i n g sa r e d i s c a s s e d k e y w o r d ：m i m o o f d mp a c k e ts c h e d u l i n gr e s o u r c ea l l o c a t i o n u s e rs e l e c t i o n 讴安电子科技大学 学位论文独创性( 或创新性) 声明 策承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取褥的研究成果。尽我所知，除了文中特别加以标 注器羧游孛瑟罗梦| l 熬蠹容戳终，论文孛不镪含其蘧久经发表交撰麓：j 妻戆簪 究成 果；也不包含为获得西安电子科技大学或熬它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 鹱势表示了谢意。 申请学位论文与资料着意不实之处，本人承担一切麓法律责任。 本人签名：粗 西安电子科技大学 关予论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生磁校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 整送交论文戆复鼙锌，蠢谗纛螽纛诺溺论文；学较霹叛公毒论文豹全部或部分痰 容，可以允许采埔影印、缩印域其它复制簪段保存论文。同时本入保证，毕业屠 结含学位论文研究课题再攥写的文章一律辫名单位为题发电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文耩于傈密，程一年解密露逶褥本授权书e 本入签名：二粗 导师签名： 疆期型：；：牛 网期型：! ：! 兰 第一章绪论 第一章绪论 1 1 无线蜂窝网发展概述 蜂窝组网理论由美国贝尔实验室提出，是移动通信发展引发的构想，是构造移 动通信网的一种新方法。过去十几年全球无线移动通信系统得到很大的发展，无 线移动通信技术经历了第一代模拟系统到第二代数字无线移动通信系统 ( 2 g 2 5 g ) 的演变，最近几年提供更大带宽、更大容量和更灵活宽带多媒体业务 的第三代数字移动通信系统( 3 g ) 逐渐发展了起来，而新一代无线移动通信系统 ( b 3 g 4 g ) 的发展也已经起步。 第一代蜂窝移动通信系统是模拟移动通信系统，利用模拟传输方式来实现话音 业务，包括美国的a m p s ( 先进的移动电话业务) 、英国的t a c s ( 全接入通信系 统) 、斯堪的纳维亚的n m t ( 北欧移动电话) 以及日本的n t t ( 日本电话和电报) 等。以g s m ( 全球移动通信系统) 和i s 9 5 为代表的第二代蜂窝移动通信系统主 要是为低速话音业务而设计，利用数字传输方式实现话音和低码率数据业务，其 容量和频谱利用率高于第一代。第二代进一步向第三代演变，被称为2 5 代的g p k s ( g e n e r a l p a c k e t r a d i os y s t e m ) 和e d g e ( e n h a n c e d d a t a r a t e f o r g l o b a l e v o l u t i o n ) 系统增强了分组数据业务的传输能力，将最大传输速率分别提高，使移动用户能 够获得除话音以外的更多的无线数据服务。 随着移动通信的飞速发展与日益融合，移动用户对于多种业务服务的需求不断 增长，包括国际电信联盟( i n t e r n a t i o n a l t e l e c o m m u n i c a t i o n u n i o n ，i t u ) 在内的许 多国际组织和机构，致力于第三代移动通信系统的研究开发及相关标准的制定， 制定出了能够提供更大带宽、更大容量和更灵活服务的第三代( 3 r dg e n e r a t i o n ， 3 g ) 移动通信系统的标准，主要包括以美国为代表的e d m a 2 0 0 0 ，以欧洲为代表的 w c d m a ，以及我国提出的t d s c d m a 等。第三代移动通信系统的特点是宽带化、 智能化、个人化，具有大容量、高速率、多业务、多码率以及变码率的特点，支 持移动多媒体业务，可以为一个用户同时提供多种业务，而不同业务具有不同的 服务质量要求。随着业务需求的增加，为了在无线链路上提供更高的数据传输速 率，h s d p a ( h i 曲s p e e dd a t ad o w n l i n kp a c k e ta c c e s s ) ，h s u p a ( h i g hs p e e dd a t a u p l i n kp a c k e t a c c e s s ) 等技术在标准中被引入。 3 g 可以提供更宽的频带，不仅传输语音，还能传输各种数据，从而提供快捷 方便的无线应用。然而，3 g 系统仍然存在很多不足，比如：尽管其传输速率可达 2 m b s ，但仍无法满足多媒体通信的需求；多种无线接入标准并存，为实现无缝切 新一代移动通信系统分组调度算法的研究 换窝漫游增加了难度；耩链提供溅务速率懿动淼范围不太 不韪缀努瀵怒各晕中堑 务类型爱求：分配绘3 g 系统的资源趋于饱和游。因此，新一代移动透信系统的研 究随之威运而生。 额一代移动通信投术，是指越过了3 g 技术的b 3 g ( h s p a 、l t e ) 、4 g 移动通 痞技术，瑷及无线窕带等瑟商2 0 2 0 年懿未来技术。 b 3 g 4 g 系统能够提供更高的传输速率和频谱利用率( 张高速移动环境支持最 高约1 0 0 m b s 的速率，在低速移动环境达到速率1 g b s ) ，拥有更好的安会性、智 能蛙葶曩灵活性，更好戆黄竣质量葶嚣鼹务凄量( q o s ) 窝更低熬费竣残本。b 3 g 4 g 移动通倍系统的研究已经愈臻成熟，它必将在不久的将来取代3 g 移动通信系统。 1 2 新一代移动通信系统中的m i m o o f d m 技术 在束来酶宽带无线通信系统中，存在两个袋严峻的挑战：多径衰落僚邀和频谱 效率。由于o f d m 技术能够有效地对抗多径传播，很好地解决频率选择性衰落信 道中的抗干扰阉题，丽m i m o 技术能够在不增加所占用带徽的前提下大幅度的提 毫无线遴信懿容量，这样，将o f d m 移m i m o 嚣耪技零耱缝合，裁髭实魏缀毫戆 传输速率和很强的可靠性。 因此，m i m o ，o f d m 技术相结合可以克服_ 无线信道频率选择性衰落，增加系 统容量，嶷高频谱剩蠲率，成为b 3 g 4 g 移动邋售系统中关键按本之一。 1 2 1o f d m 的基本原理 o f d m ( o r t h o g o n a tf 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 ) 即斑交频分复溺技术，是 一种无线环境下的裔遥传输技术。箕基本暴壤为：将信遒分成许多正交予信遒， 将高速的串行数据流分解成若干低速的并行予数据流同时程相互正交的予信道上 传输，在每个子信邋上进行窄带调制和传输。这样，尽管熬个信道是非平坦的， 兵毒频率选择性，稳蹩每个予僖遂是糖鼹孚壤豹，在每个子信遂主透露耱是窄豢 传输，信号带宽小于信道的相关带宽，因此就可以大大消除符号间干扰( i s i ) 。由 于在o f d m 系统中备个子信道的裁波相互正交，这样不但减小了子载波阀的相互 于撬( 羚 ) ，嗣对又捷毒了频谱测爝率。另外f d m 技术之绣强备受关注，其孛 一条报麓要的原因怒它可以乖j 嗣俊速傅立叶反变换( i f f t ) 鬻散傅立时变换( f f t ) 代替多裁波调制和解调。o f d m 技术具有以下优点： 1 ) 频谱剥用率很高，从理论上讲可以接避祭奎斯特极限，这一点在频谱资源 有隈煞无线鞴凌孛裰鸯鬟鬃。 2 ) 抗多径干扰和抗频率选择性衰落能力强。在多载波系统中，低速的多路并 行传输可以减弱多径传播的影响，通过加循环前缀( c p ) 的方法可以消除 第一章绪论 符号间的干扰。 3 ) 采趸魂态予载波分配技术麓镬系统达到豢大毙特零。攘据各予载波上豹衰 落程度不同，为用户分配簸合适的予倍道和传输速率，使系统的比特率最 大化。 妨对蛋子载波避行联合编磁，可使其具蠢缀强的抗衰潞能力。o f d m 技术本 身已经举l 塌了信道的频率分集，魏采衰落不是蒋澍严重，就没岿簧荐粕辩 域均衡器。通过对各个倍道进行联合编码，可以使系统性能得到熙进一步 的提高。 5 ) 霹潋采曩i f f t 嚣f f t 采实现o f d m 缮号戆调副秘籍调，荔予缓赐d s p 实现。 o f d m 系统结构如图1 1 ： 图1 1o f d m 系绶框图 参照图l 。l ，o f d m 系统工作过程为：输入的二进制信息比特首先经过串并转 换交隽路并孬阮褥流，各予傣遂主静穰患跑稽数禳据备信道的特毪爨遥应的分 配，然后各子信道上的信息比特根据各自的调制方式，分别进行星座映射，得到 信号空间中的复数嫩标，然后经过快速傅立叶逆变换i f f t ，经过并1 串转换，再加 入疆环耪缀( e p ) ，数躇l 转换( 转纨) ，最嚣送入售遂送行转戆。在接收臻，绩号 首先经过模数转( a d ) ，去除循环前缀，串并转换，然聪经过快速傅巍叶变换 ( f f t ) ，得到每个予信道上的接收信号，然腑经星座逆映射得到每个予信道上的 接收比特，再经过弗串转换褥到枣雩亍的接收蹴特流。 1 2 2m i m o 的基本原理 m i m o ( 多输入多输出) 技术在发送端和接收端采用多天线同时进行信号的发 送鞠蔹l 殳，它是攀入多出( s i m o ) 茅珏多入攀滋( m l s o ) 技术静结合。m i m o 系 统中，由于各发射天线间同时发送的信号占用间一个频谱，并未增加带宽，而多 4 新一代移动通信系统分组调艘算法的研究 天线馊褥空闫孛静终输信道增多，因两能够大大提高系统容量和频谱零l 用率。 m i m o 技术的最大优煮就是篚有效利用随枫寂落帮可能存程的多径传播来成倍的 提高业务传输速率。 对予发射天线数为 b 接收天线数为胁的m i m o 系统，假设信道为狱立的瑞 零l 衰落髂遵，剩系统戆容量毒袋装示为”l ： n c = l 0 9 2 d e t ( “。+ o 。v ，i x h h “) b p s h z ( 1 1 ) 1 、，r 其中s n r 为接收端警均痿嗓比，h = ( 。) 椎辑是信道矩黪，其中元素。是发 射天线脚刭接陂天线之闻的衰落系数。著n r , n r 穰大，刘信道容量邋戳为： q ，静 c = m i n ( n ，n g ) l 0 9 2 ( = 釜竺) b p s h z ( 1 2 ) 可敬看窭，功率雾鞋带宽露定辩，m i m o 系绞瓣容量上藤夔着最夺天线数戆增鸯羹 而线性增加，而相同条件下的酱通智能天线系统，其容量仅随天线数的对数增加 而增加。因此，m i m o 技术是提筒系统容量极为有效的手段。和传统的单天线系 统攘魄，m i m o 系绞豹垅点表现凌茨下方嚣： 1 ) 在闭环m i m o 系统中可获得较高的阵列增益 由于m i m o 系统收发端使用阵列信号处理算法，以及相关合并技术，使得接 收信号的平均信嗓比( s n r ) 褥到了明显改善。在一些实鼯的m i m o 系统中，信 遭狡态僚意反馈辩爵麓存在一定鹣差错或实鞣懿m i m o 穰邋变往太抉，系统戆发 射端不能够获得完荧的信道状态信息：另一方面，需要反馈的信道状态信息量随 着接收端天线数目的增加而急剧增大，但在实际m i m o 系统中反向信道的容量有 羧，爱馈鲍焦惠太多将严重影确系缓銮量。鼗蜒，部分爱续信道妖态德纛或发射 端知邋部分信道状态信息的m i m o 收发技术熙其有实际的应用价值，发射端知道 部分倍道状态信息的m i m o 系统成为m i m o 技术重要的研究方向。 2 ) 室闻分集增麓 无线信号传输辩，移动台的移渤竣及移动念溺圈舔境鹣交亿，傻霉多经信号懿 功率随机变化，这就是衰落效应。分集是对抗无线信号衰落的有效手段，它主要 依靠棚同信号通过多个独立衰落踌径的传输，最然，多个路径同时经历寝落的概 率缦甄。与对窝秘羰率分集裙魄较，m i m o 察阗分集豹最大霞势在于不霉要颧努 的时频资源开销。如闰1 2 所示的m i m o 系统中，若不考虑复用，将会肖r 。 条独立路径，接收机如果统一合并这些路径的信号，和s i m o 相比，m i m o 将获 褥甄；除分集效果，接收枫误妈率性能将会锝到显著撼赢。 3 ) 窆闯复用增益 m 1 m o 能够在不增加发射功率或者频带资源的情况下，实现信道容量随 m i n i n r ，n r ，线形增长。该增益就是空间复用增益，可以实现通过不同的天线传输 第一章绪论 不同的数据信息，即无线数据信号的多路并行传输，从而大大提高m 1 m o 系统的 信道容量。如果各路信息仅属于一个用户，则称为单用户m i m o ( s u m i m 0 ) ， 如果各路信息属于不同的用户，则称为多用户m o ( m u m i m o ) 。著名的b l a s t 结构就是将待发射的信息流分解为多路并行子流，对各路子流独立地进行编码、 调制与映射到其对应的发射天线上，在收端采用迫零或迫零结合干扰消除等技术 将多路子数据流分离。其实质是将单路高信噪比信道分解为多路相互重叠的低信 噪比信道并行传输，达到空间复用的目的，从而提高频谱利用率。 m i m o 系统结构如图1 2 ： 发射天线 弋泠如，p l v z 兰； 孓菇2v “， 歹 y 2l f 一勺；“。 y n 。、l 信道接收天线 图1 2 m i m o 系统结构图 1 2 3m i m o 一0 f d m 系统结构 o f d m 技术能够有效对抗多径效应，克服频率选择性衰落，使受到干扰的信号 能够可靠的接收，但是在有限的带宽下无法进一步提高系统容量和频谱效率。 m i m o 技术能够在不增加带宽的情况下，成倍地提高通信系统的容量和频谱效率， 但是m l m o 技术却无法克服信道上的频率选择性衰落。因此m 1 m o 与o f d m 技 术相结合的m i m o o f d m 技术凭借其多输入多输出天线和正交频分复用调制两大 特有的优势，能够大大提高频谱效率和系统容量，满足下一代无线传输网的要求。 m i m o o f d m 系统结构如图1 3 ： 罩：u 新一代移动通信系统分组调度算法的研究 击 图1 3m i m o - o f d m 系统框图 1 3 无线资源分组调度算法研究概述 1 3 1 分缝调度算法掰面对酶主黉游题 因为无线网提供给用户的带宽受到带宽资源的限制，只有通过更加有效的方法 进行罗曩线资源豹调瓣，才能镬系统提供高速数据透信豹能力帮对多媒体数务躲支 持。在撵供给用户燹多服务内容的同时，还必须傈证用户的( 如s ( q u a l i t y o f s e r v i c e ， 服务质量) 。无线网络同有线网络相比具有很大的特殊性，所以要将有线网络中的 分组调度算法有效地引入无线嘲络，就必需充分的考虑无线网络的特绦性。这些 特臻魏生要有下蘸捌举匏这些： 高误码率和突发错误： 无线链路释量与位置和时间相关； 骞羧熬带突； 用户的移动性； 功率受限。 基于无线网络以上的一些特殊性及分组调发本身的目标，我们在设计笼线网络 孛分缌调度算法静辩候必需考虑t 述特殊缝，下嚣褥霹算法设诗孛涉及嶷的主要 的问题进行阐述，即设计无线分组调度算法需要考虑的主骤问题。 1 ) 无线链路的可变性 无线嚣络纛有线阚络最大豹不弱裁是砖簸辘路静可交瞧。叁于手扰、袭减等因 素，蠢线信道的质壤有很高的可变性。由于饿置的不同，一些移动台可以和基站 进行觅错的通信，然而其它有一些可能根本不能进行通信。此外，移渤台的移动 性增加了链路的可变性。这样的链路可变性黉求设计的调度算法必需巍动态的机 制来簸瑾这些与时阗穗位置有关戆信道质量交纯。 2 ) 公平性 在有线网络中，调度的公平饿通常是由分配个确定的服务速率给一个具体的 第一章绪论 流加以保证的，而且调度算法阻止不同的流互相干扰。然而公平性问题在无线网 络调度中更加复杂一些。由于链路出错的原因可能导致一个流暂时损失了分配给 它的带宽。为了确保公平性，当链路状态恢复过来后，需要补偿这个受影响的流 的损失。但是如何补偿这个损失不是一个容易的问题。此外，公平性的粒度例如 短期公平性和长期公平性是影响调度策略的另一个因素。一个合适的无线调度公 平性的描述必须依赖服务模型、业务类型以及信道特征。 3 1 服务质量 宽带无线网将为不同类型的业务提供服务，对这些不同类型的业务需要提供不 同的q o s 。因此，在系统中必需保证不同业务获得了不同的q o s 支持。为了达 到这个目标，相应的机制必需集成到调度算法里面。在不同的调度模型中，保证 q o s 的机制也是不一样的。 4 ) 数据吞吐量和信道利用率 对于无线网络来说最重要的资源就是带宽。一个有效的无线分组调度算法必需 尽量的减少在恶劣的信道条件下进行的无效传输，同时必需尽量增加有效的服务 分配和无线信道的带宽利用率。 5 ) 功率限制和简单性 在蜂窝无线网中，分组调度算法主要是运行在基站上。基站用于计算的功率是 不用加以考虑的。然而对于移动台来说功率是受限的，所以一个好的分组调度算 法应该使用最少数量的控制信息，以减少移动台发送这些信息的功率开销。 此外分组调度算法还必需满足简单的原则，不能过于复杂，这样才能高速调度 实时多媒体业务，满足其严格的时延要求。 1 3 2 调度算法的发展 对于有线网络，最早在实际路由器中获得应用的调度算法是先入先出( f i r s ti n f i r s to 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 ) 算法 2 j ，这种算法摒弃了这种依靠分组到达次序的排队方法，通过为各个 业务流合理地分配权值来控制它们获得发送的机会，公平性有所增强，但是，在 处理变长分组的时候，效果仍然不理想。9 0 年代，基于分组传输综合业务的实际 需求带动了对于调度算法的研究。d e m e r s p 】，p a r e k h 和g a l l a g e r 4 1 5 1 等人先后研究了 基于流体流的并行服务模型，即通用处理器共享( 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 ) ，在这种模型中，业务流被看成是可以无限分割的流体，而服务器可以同时 新一代移动通信系统分组调度算法的研究 为多个业务流同时暇务，服务的尺度也可以无嫩小。因此，g p s 模型可以满足淀 之阕钓独立往，并可以实现对不褥时延蒂宽鬃求的韭务流静区分骚务，为调度算 法的麝期研究提供了理论参考。 g p s 模型是一个理想化的公平模型，在实际系统中不可能实现。这是因为实际 系统中，餮窭链黪农弱一薅刻哭貌缀务一个分缝，瑟显只露当簧送宠一拿分缝之 后才能够服务其他的分组。也就楚说，实际系统中，调度的“粒度”蘩比g p s 模 型粗得多。根据g p s 模型，p a r e k h 和g a u a g e r 提出了基于g p s 分组化近似的加权 公平掺敬( w e i g h t e df a i rq u e u i n g , w f q ) 调凌嚣法【4 】f 捌。这怒第一个真灏意义上的 公平调度算法，可以提供有界辩时延保证。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 i n g , s c f q ) 算 法，邋过牺牲了一定的公平性来换取了复杂度的降低【6 1 。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 - e a s ef a i rw e i g h t e df a i rq u e u i n g , w f 2 q ) 谲 度算法 7 1 。 1 9 9 7 年，他们改进了w f 2 q 算法，新算法w f 2 q + e 鬓杂度方面有所降低【8 】。 同年，g o y a l 等人改变了计算廉拟时间的计簿方法，提如了开始时间公平排队 ( s t a r t - t i m ef a i rq u e u i n g , s t f q ) 算法，这释磐法两样吴蠢低复杂度鞫鲑戆公平往 【们。 g p s 模型虽然简单，但也有一定的局限性。在g p s 模趔和其近似化算法中， 对业务鹣嚣求只馒耀速搴一个参数来逶季亍撼滚，这载镬 ! 譬辩廷与謦宽熬分配互超 藕合程一起。也就燕说，如栗需凝低时延，那就必需高带宽。因此这对于低时延、 低带宽的业务无法获得高的资源利用率。因此，对于时延敏感性业务，需要有其 她的算法送行q o s 豹保证。 最早弱期优先( e a r l i e s td e a d l i n ef i r s t , e d f ) 算法是这类算法辛豹载装h o j ，在 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 ae 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 模型，飘爨终豹建度 解决了时延和带宽的解耦问题】。并在后续的几年中，许多学者基于服务曲线的 理论搬出了很多新的算法，如最犟期限优先斧钉分级公平服务曲线等等( 谯这些模型 第一章绪论 9 中，通过使用非线性的服务曲线，实现了带宽和时延的孵耦) 。一方黼他们也发展 了黢务莛线懿嚣论，著骜其磷突接连嚣臻程羧称俸网终徽积分学貔学麓。 此外，还有诸如基于优先级的调度算滋、随机调度髯法、分类调度算法等等。 可以满足不同的调度目标要求。 焉线调度算法约骚究要鞘微獍一些。1 9 8 9 年，a 。d e m e r s 等人最够凌无线网络 中馘域性和突笈错误特性考虑进调度算法，提出了依靠链路状态的分组调度算法 ( c h a n n ds 协t ed e p e n d e n tp a c k c ts c h e d u l i n g ，c s d p s ) l “j 。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 d w i r e l e s sf m rq u e u e i n g ，i w f q ) t | 3 l 。在其论文孛，作者撵出无线链路突发错误会零 致肖线网络发展起来的调度算法在无线环境中应用时的失效。因为谢些处于积魇 状态的业务流( 设为f 1 ) b o 使根据w f q 等薄法的调度结果获得了发送机会也会由 予镳路失效夏穆发送援会转莰给其建兹鼗务滚( 设舞q ，麸露导致公乎缝无法镙 证。为了保证公平性，就需袋对发生链路突发错误的救务流在其恢囊正常传输时 对之进行补偿。i w f q 中的补偿模型是隐禽的，算法保掩了服务的顺序标记，可以 记墩滞后流滞蕊的服务量。这样，涝后流旦检测到链路恢复正常，裁会马上囊 番发送过程，势籍浠后懿监务麓弥静过来。 然而i w f q 的补偿过程并不科学，会引起所谓的隔离性问题。因为对n 的补 偿可能会影响列对于正常业务流的正常服务。为了解决隔离性问题，以开始时间 公平簿歇s 疆q 为参照，s t i o i c a 等人掇懑了独立予镰鼹狡瑷豹分娩公手接敬 ( c h a n n e l c o n d i f i o ni nd e p e n d e n tp a c k e tf a i rq u e u i n g ，c i f q ) q ，该辫法的补偿模 型比i w f q 更加合理，能够饿得补偿行为熙加平滑，从而提高了算法对业务流之 间调度的隔离度。他们在算法中定义了超秘服务( l e a d ) 秘滞后服务( l a g ) 豹概念， 黻始终正常的数务流( 设兔f 3 ) 为参照，蠡翻垃分剐可以称作滞后流和超前流。算 法娥定补偿行为只能在超前流和滞后流之间进行，而不能影响正常流所得到的服 务。而且仅当超箭流主动“交如超前份额”的时候，滞后流才能够得到补偿。通 过这秘可控羹耱缮过程较努懿解决替嫠亵戮篱之闻酶矛瓣。 1 9 9 8 年，e r a m a n a t h a n 等人提出的纂于服务的公平方式( s e r v e rb a s e df m r a p p r o a c h ，s b f a ) 【l5 】调度算法从另外的角度提供了对差错流的补偿机制。在s b f a 中，系统预窝了部分信道带宽雳终於偿，嚣不是在滋嚣漉帮超兹浚之闻交换对 陈来实现 偿。算法维护了一个虚拟流，称作长时公平服务器( l o n gt i m ef a i r s 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 中的顺序而定。算法维护了业务流之间的长时公平性，但怒对业务流不 o 新一代移幼通信系统分组调度算法的研究 提供筑辩豹公平经绦涯，瞧没有簸坏壤嚣下鹣瓣廷要。针对i w f q 豹缺点和在无 线网络上传输时延敏感型业务的需求，l 1 l 和b h a r g h a v a 等人又提出一种新的算法 无线公平服务( w i t e l e s sf a i rs e r v i c e ，w f s ) 算法【1 3 】。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 和最大裁干 l ( 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 ) 这两种简聃的调度算法下系统吞吐攒的变化i i 。在2 0 0 0 年，q u a l e o m m 公 司的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 1 7 1 。僮褥一提酶是，这些算法虽然魄较篱革， 但是将无线调度的目标从公平饿、时延等传统性能需求扩展到了对无线资源进行 优化的新视角，开拓了调度算法的一个新的研究领域。 1 3 。3 分组调度的经典算法 无线信道具有时变特性，这决定了无线调度算法的易变性。另外，由于不同用 户传竣豹业务类型不弱，楣应鹣公平牲褰韭务翡q o s 要求也决定了无线谖度算法 毖须懿有相当的灵活度。无线系统的复杂程度不同，针对不同系统的调度算法研 究程腱也参差不齐。研究先进的调度算法是提高数据业务吞吐量，保诞用户间的 公平饿，满足业务q o s 的根本。 穰瓣算法静复杂往纛哥爝经，嚣蓑在实辩系统中采溺瓣算法主要蠢轮溺算法 ( r r ) 、最大载干比算法( m a xc i ) 和比例公平算法( p f ) 。 1 3 。3 。1 轮搦算法( 装疑) 轮询算法就是尽量保证能以相等的机会分配资源给系统中的每个用户，而不考 虑系绕的总吞吐爨旋该尽量大，它能保证该小区内豹所有用户按照某葶中确定的顺 序循环占用等露闯鹃无线资源采进行逶信。 轮询算法就调度上的概率而窗，对五个用户，每个用户k 被调度到的概率为 1 p ( 秘= ( 1 。3 ) a 轮询算法的目标是保障用户间的公平性，即保障每个用户都能得到一定的服务 资源。从资源分配的公平性角魔来说，它保证了所有用户占用等量的时频资源进 第一章绪论 行通信。因此，轮询算法不仅可以保证用户间的短期公平性，而且还可以保证用 户间的长期公平性。从算法复杂性考虑，由于轮询算法无优先级指标，不需排队， 因此是一种复杂度很低的调度算法，这也是为什么一些实际系统采用轮转算法的 原因。 轮询算法是一种最简单、最公平的调度算法，但是它没有考虑到不同用户的无 线信道的具体情况，因此它是一种简单但不稳定的调度算法，如果占用某个时隙 的用户突然进入阴影区，其信道性能迅速衰落，传输速率下降，则系统吞吐量很 低。并且它只适合用于单业务的环境中，因为它没有考虑多业务的延迟优先级问 题，即在多业务环境中其公平性无法体现。 加权轮询算法( w r r ) 在r r 算法的基础上作了改进，按照权重公平的分配整 个资源。w r r 算法在系统承载量很轻时，服务流每次能获得大于自身的平均需求 的带宽，因此所有服务流都能获得很好的性能。但是当系统承载量越来越重，带 宽不再足够，所有用户的性能都会急剧下降，并且系统会较早地呈现饱和状态。 1 3 3 2 最大载干比算法( m a xc f l ) 最大载干比算法根据注水理论，保证了具有最好链路条件( 即c i 最高) 的用 户分配资源时具有最高的优先级。因为具有高c ，i 的用户可以以较高速率正确传输 数据分组，如果先服务它的话就会使整个系统的吞吐量提高。很显然，c i 调度器 以牺牲公平性为代价达到更大的系统容量。 如果在时刻t 有k 个用户同时请求传输数据，第k 个用户在时刻t 的最大载波 干扰为( c z ) ：，则最大载干比调度算法选中的用户为： k = a r g m a x ( c h ) ：( 1 4 ) j = l ，- 最大载干比算法不仅复杂度低，其选择信道状况最好的用户进行调度，可以在 系统中达到最高的传输速率，任何其他算法的系统吞吐量都不可能超过它，因此 该算法所能得到的系统吞吐量可以作为其他算法的上限。 但是最大载干比算法的最大缺点就是完全不考虑不同用户的公平性要求，是一 种最不公平的调度算法。按照这种算法，某些处于小区边缘的用户的c i 可能较低， 那么这些用户可能始终得不到服务的机会，而出现“饿死”的现象。最大c i 主要 适用于单业务环境，在多业务环境中由于每种业务的c i 差距大，这时候直接采用 最大载干比算法无法保证系统的高吞吐量 1 ”。 新一代移动通信系统分组调度算法的研究 1 3 3 3 比例公平算法( p f ) 最大载于比算法提嘉了系统的蚕蛙量却不能保证用户的公乎性，轮询算法为了 保诫公平饿而不能充分利用秃线资源，而比例公平算法就是为了同时兼顾用户的 公警性和系统吞黢量嚣提出懿。 假设有k 个用户，最大载干比算法在时隙t 选择满足式( 1 5 ) 的用户f ( f ) 进行服 务： 韵= 鹕熙勰 弘5 ) 式( 1 5 ) 中愿) 表示用户k 在对隙t 的调度速率，t a t - 1 ) 为用户k 农对隙t 之前 的平均吞吐量。由式( 1 + 5 ) 可以看出，调度概率与该用户的速率成正比，也就怒其速 率麓离，被调度上熬橇会越大，哥毅保 蒌器蛙萋；与瘸户最逐段辩闯接收的数 据赞成反比，也就是之前被调度的次数越多，这一次被调度到的概率就可能越低， 用戳保证公平性。 对隙t 调度先成后，各用户的平均吞吐量t a t ) 通过式( 1 6 ) 进行更新，分为第t 个时隙调度用户k 和在第t 个时隙不调度用户k 两种情况： k ；) 五g 不( f ) ：0 | ( i - 三瑗 lt c f ( 醇m k ( 1 。6 ) f 尊k t 。是一个窗翻参数，表示平均速率中包含了多长戳德的信邀信息。f 。越大，平 均用户吞吐量会参考以往更长的历史值，因此长期公平性越好，反之t ，越小，平 均吞吐量熙多的楚强调近期的吞吐纛值，这样，调度算法会对用户倍道的突变更 为敏感。 比例公平算法在尽餐保证用户间公平性的同时，为具有较好信道条件的用户提 供饶先的黻务。该算法结合了最大载干院箨法平拜轮询算法的优点，裔前还径广泛 应用中。 1 3 4 m i m o - o f d m 系统的无线资源调度研究现状 在多载波系统中，无线信道的频率选择性衰落会使得传输带宽中的备子裁波所 经历的衰落状况不同，这样由子载波组成的传输予信道也会具有不同的传输质量， 如粜平均分配数据比特稠功搴，则瑟根据传输质量最差的子信道来分配，这样就 会披低整个系统的传输速率，造成无线资源的浪费，因此应该根据备子信道的特 薤动态缝分配数据比特秘臻攀，在臻道增豢好魏予售遵上多分配一势数据滋特， 砭 ，一0 + 玲 n 一 一 第一章绪论 在信道衰落厉害的子信道上少分配一些数据比特，可以达到优化系统性能的目的。 在o f d m 这样的多载波调制系统中，可以根据每个子信道上不同的比特数来选择 不同的调制方案，在传输质量好的子信道上采用高阶的调制方案以提高容量，在 传输质量低的子信道上采用低阶的调制方案以保证传输正确率，这样可以更加合 理的利用无线资源，来获得最优的系统性能。对于o f d m 系统，首先要根据各个 用户的需求来分配子信道，在为每个用户分配了子信道后就要在相应的子信道上 分配传输比特和发射功率，即为相应用户设定合适的m c s ( 调制编码方案) 。 目前，关于o f d m m i m o 系统动态无线资源分配的方法基本可以分为两类： 边值自适应( m a r g i n a d a p t i v e ，m a ) f 1 9 】和速率自适应( r a t e a d a p t i v e ，r a ) 2 0 】。 边值自适应是指在传输速率和误码率约束条件下使得发射功率最小；速率自适应 是指在发射功率约束条件下达到传输速率最大。注水算法【2 l 】是解决多载波系统的 子载波、比特和功率分配的最优方法，但是注水算法是一个非线性求解问题，有 很高的复杂度，在实际应用中，常以牺牲一部分性能为代价来降低其