（信息与通信工程专业论文）无线网络分组调度算法研究.pdf

国防科学技术大学研究生院博士学位论文 摘要 移动通信和互联网的高速发展，使人们对宽带无线接入的需求越来越迫切。 人们期望未来移动通信系统在支持更高传输速率的基础上，能够容纳更多用户并 且满足不同业务的服务质量( q o s ) 要求，而有效的无线分组调度算法正是实现这 一目标的关键。在很多应用环境下，无线信道具有明显的资源受限和时变衰落特 性，基于有线网络或无线静态信道的分组调度算法无法保证无线网络用户获得很 好的q o s 。针对无线时变环境下无线信道的传输特性，设计能够在保证用户q o s 的同时提高无线网络容量的分组调度算法是当前无线通信领域的一个热点。 在多用户共享的无线网络中，利用不同用户独立的时变信道条件进行机会调 度( o p p o m 越s t i cs c h e d u l i n g ) 可以显著提高无线信道的利用率。尽管每次调度总 选择信道条件( 通常以接收信噪比表示) 最好的用户进行传输可以使系统吞吐量 达到最大，但由于无线网络中不同用户的信道条件往往具有很大差别，为了使系 统中每个用户均获得较好的q o s ，在调度过程中必须选择合理的公平准则。在无 线网络中，调度的有效性和公平性通常是两个相互矛盾的性能指标，而有效的机 会调度算法必须根据用户的q o s 要求，在这两个指标之间获得最佳的折中性能。 论文主要针对时变信道环境下时分复用( t d m ) 的无线网络分组调度机制展开了 深入研究。 首先，对无线网络非实时业务分组调度算法进行了研究。论文在对现有 m a x r s n r 算法进行改进的基础上，提出了一种具有小尺度服务时间保证的无线非 实时业务分组调度算法( m m a ) 【r s n r ) 。m m a x r s n r 算法在很好的继承了 m a x r s n r 算法的大尺度服务时间公平性质的同时，能够使每个用户在预先规定的 较短时间内获得服务，从而满足了一些非实时用户对访问时延上限的特殊要求。 在此基础上，通过充分利用多用户分集( m u l t i u s e rd i v e r s 时) 的机会调度策略， m m a x r s n r 能够获得较比例公平( p f ) 算法更好的吞吐量性能。同时，论文还 针对现有机会调度算法无法为用户提供加权服务时间公平性的缺陷，提出了一种 具有小尺度加权服务时间公平性的无线非实时业务分组调度算法( s f o s ) 。该算 法同时利用虚拟时间机制和m a x r s n r 准则，能够在进行有效机会调度的同时， 使每个用户在任意短的时间内获得与其权重成正比的服务时间。 其次，对无线网络实时业务分组调度算法进行了研究。实时业务具有非常严 格的端到端传输时延要求，为了提高实时用户的q o s ，实时业务分组调度算法应 该通过机会调度策略尽量减小实时业务分组在基站发送队列中的等待时间，为此， 论文提出了一种机会的实时业务分组调度算法( o r s ) 。在o r s 算法中，每个用 户的优先函数同时包含该用户的相对信噪比和一个随该用户发送队列的队首 第i 页 国防科学技术大学研究牛院博士学位论文 ( h e a d o f - l i n e ，h o l ) 分组等待时间递增的凹函数。在此情况下，当所有用户的 等待时间均较小时，具有最大相对信噪比的用户将得到调度；而当某个用户的等 待时间逐渐接近其超时期限时，迅速增加的等待时间函数值将使其获得调度。与 目前在h d r 、h s d p a 网络中得到广泛应用的e x p 和m l w d f 算法相比，0 r s 算法能够显著降低系统中所有实时用户的平均等待时间和分组超时率。 第三，对实时和非实时业务共存的无线网络混合业务分组调度算法进行了研 究。由于实时业务和非实时业务具有不同的q o s 要求，如何设计合理的资源调度 策略，使不同类型用户获得较高的q o s ，是未来无线网络调度算法需要解决的关 键问题。论文提出了一种基于p f q 策略的分级调度算法( p f q - h s ) ，该算法具有 独立、分级的调度结构：在第一级调度器中可以使用任何两种调度算法分别对实 时和非实时用户进行独立的调度判决；而在第二级调度器中则采用种基于p f q 策略的机会调度算法( p f q 0 s ) 保证服务的公平性。与目前两种主要的针对混合 业务的分组调度算法m p f 和v t q 相比，p f q h s 能够在保证服务时间公平性的基 础上，为不同类型用户提供较好的q o s 。 第四，对具有功率节省性能的无线网络实时业务分组调度算法进行了研究。 无线网络中很多用户都是依靠电池供电的移动终端，节省移动终端的功率损耗、 延长其使用时间是未来无线网络需要解决的关键问题。一种有效的功率节省方法 是当移动终端的无线网络接口( w n i ) 处于空闲状态时将其切换至睡眠模式。基 于此方法，论文提出了一种针对流媒体业务的、同时使用缓存策略和调度机制的 功率节省算法( j b s ) 。j b s 算法首先在基站一侧引入分组整型缓存，对到达基站 发送队列的流媒体分组进行整型：然后，使用0 r s 策略对流媒体分组进行调度判 决，其目标是使每个流的多个分组同时存在于发送队列中，并能在较短时间内使 移动终端累积得到足够多的睡眠时间。与目前两种主要的功率节省算法b k s 和 l 强s 相比，j b s 算法能够在保证流媒体用户q o s 的同时，有效降低w n i 的功率损 耗。 主题词：无线网络，机会调度，多用户分集，公平，服务质量，功率节省 第i i 页 国防科学技术大学研究生院博士学位论文 a bs t r a c t w i t ht h er a p i dg r o w t l lo fm o b i l ec o 咖叭m i c a t i o n sa n di n t e m e t ，t h ed e m a n d so f w i d e b a n dw i r e l e s sa c c e s sa r eb e c o m i n gu r g e n t p e o p l ee x p e c tt l l a tf u n 鹏m o b i l e c o n u n u n i c a t i o ns y s t e m sc a np r o v i d e1 1 i 曲e r 仃a n s m i s s i o nr a t e sa n ds “s 黟m o r eu s e r s w i mh e t e r o g e n e o u sq u a l i t yo fs e r v i c e ( q o s ) r e q u i r e m e n t s e f f e c t i v ep a c k e ts c h e d u l i n g p o l i c i e sa r ec r i t i c a lt 0a c i l i e v en l i sg o a j i nm a n yc i r c 啪s t a n c e s ，p a c k e ts c h e d u l i n g p o l i c i e sd e s i g n e df o r 谢r e dn e t 、v o r k sa i l d 晰r e l e s ss t a t i cc h 锄i l e l s 盯ei n a d e q u a t ef o r 晰r e l e s sn 印o r k sb e c a u s eo ft h el i m i t e da 1 1 dt i m e v a r ) r m g 丽r e l e s sc h 锄e lc a p a c 时a s ar e s u l t ，i ti sah o tt o p i ci n 廿l ea r e ao fw i r e l e s sc o m m u i l i c a t i o i l st od e s i g nt l l ep a c k e t s c h e d u l i n ga l g o r i m m sb yc o n s i d e r i n gt h ec h a r a c t e r i s t i c so fw i r e l e s st i i i l e - v a d ，i n g c h 锄e l sw i mt h eo b j e c t i v e so fp r 0 v i d i n gq o sg u a r a n t e e st ou s e r s 嬲、v e u 嬲i n c r e a s i n g t l l ec 印a c i t i e so ft l l ew i r e l e s sn 娟v o f k s o p p o 枷s t i cs c h e d u l i n gw h j c he x p l o i t st h ei n d e p e n d e n ta r l dt i m e v a r y i i l gc h a m l e l c o n d i t i o l l so fd i f f e r e mu s e r sc a l lo b v i o u s l yi n c r e 2 l s et h es p e c t m le 伍c i e n c yo f 、栅e l e s s c h 锄e l s t i l o u 曲a l 、v a y ss e r v i n gt h e u s e r sw h 0l l a v e 也eb e s tc h 锄e lc o n d i t i o n s ( r e p r e s e n t e db yt h er e c e i v e ds n r s ) c 觚i n a x h i z et l l es y s t e m 山0 u 曲p 鸣s o m ef a i m e s s r u l e sm u s tb ea d o p t e dms c h e d u l i n gd e c i s i o n si i lo r d e rt 0p r o v i d ee a c hu s e ri i l l e s y s t e mw i t l lb e t t e rq o sc o n s i d e r i n gd i f r e r e n t 、析r e l e s su _ s e r sc a nt i a v ed i s t i r l c tc h a n n e l c o n d i t i o n s s i n c es p e c t r a le m c i e n c ya n d 筋m e s sa r eu s u a l l y 铆oc o n n i c t i n gd e s i 印 o b j e c t i v e s ，锄e 仃e c t i v eo p p o n u 柑s t i cs c h e d u l i n gs c h e l es h o u l d 瓤水e 锄o p t i m 啪 t r a d e - o f fb e t w e e nt h e s et w oo b j e c t i v e sb a s e do nt h eq o sr e q u i r e m e n t so fu s e r s i nt h i s d i s s e r t a t i o n ，w ei 1 1 v e s t i g a t e t l l e p a c k e t s c h e d u l i n g m e c h a n i s m si naw i r e l e s s t i m e - v a r y i n ga n dt i m ed i v i s i o nm u l t i p l e x 访g ( t d m ) s y s t e m f i r s t ，t l l es c h e d u l i n gm e c h a j l i s m sf o rn o n r e a l t i m es e r v i c e si n 谢r e l e s sn e t w o r k s a r ei n v e s t i g a t e d b 嬲e do nt l l ei m p r o v e m e n tt ot h et r a d i t i o n a lm a x i i n u mr e l a t i v es n r ( m a x r s n r ) s c h e m e ，am o d i f i e dm a ) ( r s n rs c h e d u l i n ga l g o r i n u n ( m - m a x - r s n r ) i s p r o p o s e dw h j c h c a i lp r o v i d es h o n t e 咖t e m p o m lg u a r a n t e e w h i l ep o s s e s s i n ge x c e l l e n t l o n g t e n nt e m p o m lf a i m e s si n h e r i t e df i o mm em a x r s n rs c h e m e ，m m a x r s n rc a j l a l s oi n s u r ee a c hu s e rg e ts e r v i c eo v e ra n ys h o r r tt i m ei m e n ，a li no r d e rt os a t i s 母s o m e n o n r e a l t i m eu s e r s r e q u i 珊e t s b a s e do nt h s e sc h a r a c t e r i s t i c s ，m - m a ) 【一r s n ra c l l i e v e s b e t t e rp e r f o 肌锄c ei nt e 咖so fs y s t e m u s e rt l l r o u 曲p u tw h e nc o m p a r e d 、加t ht l l e p r o p o r t i o n a lf a i r ( p f ) s c h e m e m e a i l w h i l e ，n o t i c i i l gt l l el a c ko fp r o v i d i n gw e i 曲t e d t e m p o r a lf a i m e s so fp r e s e mo p p o n u n i s t i cs c h e d u l i n gs c h e m e s ，a 、i r e l e s sn o n r e a l - t h e s e i c es c h e d u l i l l ga l g o r i t h n l 埘1s h o r t - t e 肌、i g h t e dt e m p o r a lf a i m e s si sp r o p o s e d ( s f o s ) t l l i sa l g o r i t h me x p l o i t sb o mt l l ev i r t u a l t i m em e c h a l l i s m 如dt h em a ) ( r s n r r u l et om a k eo p p o r t 吼i s t i cs c h e d l l l i n g m i l ep r o v i d i n ge a c hu s e rw i t hw e i 曲t e d t e m p o r a ls e r v i c eo v e ra n ys h o r r ti n t e r v a l 第i j j 页 国防科学技术大学研究牛院博士学位论文 s e c o n d l y ，t h es c h e d u l i n gp o l i c i e sf o rw i r e l e s sr e a l t i m es e r v i c e sa r es t u d i e d s i n c e r e a l t i m es e r v i c e sh a v es t r i n g e n td e l a yr e q u i r e m e n t s ，a i le f f e c t i v es c h e d u l e rs h o u l d r e d u c et h ew a i t i n gt i m eo ft h er e a l - t i m es e r v i c ep a c k e t si ne a c hu s e r sq u e u eb y e x p l o i t i n go p p o i r c u n i s t i cs c h e d u l i n g t h e r e f o r e ，a i lo p p o r t l m i s t i cs c h e d u l e rf o rw i r e l e s s r e a l 一t i m es e r v i c e s ( o r s ) i sp r e s e n t e d i nt h eo i 岱s c h e m e ，t 1 1 ep r i o r i 田如n c t i o no fe a c h u s e ri n c l u d e sb o t hh i sr e l a t i v es n ra j l da 1 1i n c r e a s i n gc o n c a v em n c t i o no ft h ew a i t i n g t i m eo ft h eh e a d - o f - l i n e ( h o l ) p a c k e ti nt h eu s e r sq u e u e i nt h i sc o n t e x t ，、h e ne a c h u s e rh a ss m a l l e rw a i t i n gt i m e ，t h eu s e r 嘶t ht h em a x i m u mr e l a t i v es n rw i l lb e s c h e d u l e d 0 t h e n i s e ，i ft h ew a i t i n gt i m eo fau s e ri s 印p r o a c h i n gl l i sd e a d l i n e ，t h e r a p i d l yi n c r e a s e dw a i t i n g t i m e 如n c t i o nv a l u em a k e st h eu s e rg e ts c h e d u l e d c o m p a r e d w i t ht l l ee a j l dm l w d fs c h e m e s 、) 柱c hh a v e b e e na d o p t e di nm eh d ra n d h s d p as y s t e m s ，o r sc a no b v i o u s l yr e d u c eb o t ht 1 1 e a v e r a g e 、张i t i n gt i m ea n dt h e p a c k e tv i o i a t i o np r o b a b i l i t i e so fa l lu s e r si nt l l es y s t e m t h i r d l y ， t h ew i r e l e s s s c h e d u l i n gs t r a t e g i e s f o ram i x t u r eo fr e a l - t i m ea n d n o n r e a l t i m es e r v i c e sa r ed e s i g n e d s i n c er e a l t i m ea 1 1 dn o n r e a l t i m eu s e r sh a v eq u i t e d i f f e r e n tq o sr e q u i r e m e n t s ，t h ed e s i g nf o rt l l es c h e d u l i n gp o i i c yt h a tc a i lo 髓r1 1 i 曲e r q o sp r o v i s i o n st oh e t e r o g e n e o u su s e r si sac r i t i c a li s s u ef o r 如t u r e 、) ，i r e l e s sn e t 、) l ，o r k s t h e r e f o r e ，ap a c k e tf a i rq u e u d n gb a s e dh i e r a r c h i c a ls c h e d u l i n gs c h e m e ( p f q - h s ) i s p r o p o s e d ， 州c ha d o p t sa ni n d e p e n d e n ta n dh i e r a r c h i c a l s c h e d u l i n gp r o c e s s t h e f i r s t - s t a g e s c h e d u l e ro fp f q - h sc a nu s e锄y 押，os c h e d u l i n gs c h e m e st om a k e i n d e p e n d e n td e c i s i o n sf o rr e a l - t i m ea n dn o n - r e a l t i m es e r 、，i c e s t h e n ，t h es e c o n d s t a g e s c h e d u l e ru s e sap f qb a s e do p p o r t u n i s t i cs c h e d u l i n gs c h e m e ( p f q o s ) t og u a n m t e e s e i c ef a i m e s s c o m p a r e d 、析t h 伽os c h e d u l i n gs c h e m e sf o ram i x t u r eo fr e a l t i m ea n d n o n r e a l - t i m es e r v i c e s ，i e ，m p fa n dv t q ，p f q h sc a np r o v i d eb e t t e rq o st o h e t e r o g e n e o u su s e r sw h i l em a i n t a i n i n gt e m p o r a lf a i m e s s f o u r t h l y ，t h ep o 、v e r - s a v i n gs c h e d u l i n ga l g o r i t sf o rw i r e l e s sr e a l t i m es e r v i c e s a r ei n v e s t i g a t e d s i n c eam a j o r i t yo fu s e r si nw i r e l e s sn e t w o r k sa r em o b i l et e m i n a l s ( m t s ) p o 、v e r e db yb a t t e d ，t h em e t h o d so nr e d u c i n gt h ep o w e rc o n s u m p t i o n so ft h e s e m t sa r ev e r yc r i t i c a lf o r 如t u r ew i r e l e s sn e t 、v o r k s a ne f f e c t i v ep o w e r s a v i n gm e t h o di s t op u tt h ew i r e l e s sn e t w o r ki n t e r f a c e ( w n i ) o ft l l em ti m os l e e pw h e ni ti si d l e b a s e d o nt h j sm e t l l o d ，aj o i n tb u f f e r i n ga n ds c h e d u n n gp o w e r - s a v i n gs c h e m e ( j b s ) i s p r o p o s e d ，w h o s eg o a l i st or e d u c et 1 1 ep o w e rc o n s u m p t i o l l so ft h em t sw h e nt h e ya r e u s e dt or e c e i v et h es t r e a m i n gs e i c e s i no r d e rt oa c h i e v et h i sg o a l ，j b sf i r s te m p l o y sa s h a p i n g b u 脏ro nt h eb a s es t a t i o n ( b s ) w h i c hb u 行e r st 1 1 ei n p u tp a c k e t s t h e nj b su s e s t h eo r ss c h e m et om a k es c h e d u l i n gd e c i s i o n so ft h es t r e 锄i n gp a c k e t s b yt h i sm e a n s ， j b sc a ns i m u l t a n e o u s l yb u f f e rm u l t i p l ep a c k e t si ne a c hu s e r sq u e u ea n dm a l ( ee a c hm t a c c u m u l a t ee n o u g hs l e 印i n gt i m eo v e rs h o n e rt i m ei i l t e r v a l c o m p 2 u r e dw i t l lt h eo t h e r 觚op o w e r s a v i n gs c h e m e s ，i e ，b k sa n dr b s ，鹏sc a l le 仃e c t i v e l yr e d u c et h ep o w e r c o n s u m p t i o n so f t h ew n i s 、v h i l ee n s u r i n gt h eq o s p r o v i s i o n so ft h es t r e a m i n gu s e r s 第i v 页 国防科学技术大学研究生院博士学位论文 k e yw o r d s ： w i r e i e s sn e t w o r k s ， o p p o r t u n i s t i cs c h e d u n g ， m u i t i u s e r d i v e r s i t y ，f a i r n e s s ，q u a t yo fs e n ，i c e ( q o s ) ，p o w e r s a v i n g 第v 页 围防科学技术大学研究生院博士学位论文 表2 1 表2 2 表2 3 表3 1 表4 1 表4 2 表4 3 表4 4 表4 5 表5 1 表5 2 表5 3 表5 4 表目录 i 汛和f t h 算法的比较2 0 系统的主要仿真参数2 8 s f o s 算法的基本调度过程3 6 两类语音业务的q o s 要求6 2 p f q o s 的基本调度策略7 1 p f q o s 算法中娘的更新方法8 1 p f q o s 的调度过程8 3 第一组仿真结果8 4 第二组仿真结果8 5 j b s 服务器端的操作1 0 2 j b s 客户端的操作10 4 移动终端的平均传输速率1 0 5 仿真中使用的跟踪文件1 0 5 第1 v 页 国防科学技术大学研究生院博士学位论文 图1 1 图1 2 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图2 9 图2 1 0 图2 1 1 图2 1 2 图 图 图 图 图2 1 7 图2 1 8 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图3 1 1 图 目录 两个用户的时变信道条件3 论文主要研究内容之间的关系1 4 基于时分复用系统的无线分组调度框架。1 7 i 汛算法与f t h 算法的系统吞吐量性能的比较2 1 m a x r s n r 算法的调度过程2 3 m m a ) 【- r s n r 算法的访问时延概率3 0 m m a x r s n r 与p f 算法访问时延概率的比较3 0 m m a x r s n r 算法下的服务时间份额31 m m a x r s n r 与p f 算法服务时间份额的比较3 1 m m a ) 【r s n r 与p f 算法吞吐量增益的比较3 3 m m a x _ r s n r 算法的系统吞吐量随用户数量变化的情况3 4 m m a x r s n r 算法的系统吞吐量随五变化的情况3 5 服务时间份额随口变化的曲线一4 1 用户吞吐量随口变化的曲线。4 2 加权服务时间差异的概率曲线。4 3 服务时间份额随口变化的情况4 4 吞吐量增益随口变化的情况4 4 s f o s 与m m a x r s n r 算法的访问时延概率曲线4 5 用户在不同算法下的加权服务时间差异的概率曲线4 6 用户在不同算法下得到的吞吐量增益。4 6 无线网络实时应用系统结构4 9 使用播放缓存消除时延抖动的方法5 0 几种实时业务分组调度算法的分组超时率的比较5 3 不同编码格式的v o i p 流的m o s 值随分组超时率的变化【1 2 们5 7 分组超时率上限相同时的等待时间曲线5 8 分组超时率上限不同时的等待时间曲线5 9 超时期限为2 0 0 m s 时的分组超时率和平均等待时间6 1 分组超时率随超时期限的变化6 1 平均等待时间随超时期限的变化6 2 不同q o s 要求下分组超时率的比较6 3 不同q o s 要求下平均等待时间的比较6 4 第v 页 国防科学技术大学研究生院博士学位论文 图4 1 图4 2 图4 3 图4 4 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 图5 7 图5 8 图5 9 图5 1 0 图5 1 l 图5 1 2 图5 1 3 使用虚拟令牌队列提供最小吞吐量保证的调度算法【1 2 2 j 。6 8 p f q h s 调度器的结构7 0 不同类型的用户q o s 随艘的变化关系8 0 m p f ，v t q 和p f q h s 等三种算法的性能比较8 6 支持实时业务传输的r t p 仙d p i p 协议栈【1 4 9 2 在分组间隔切换至睡眠模式的功率节省策略9 2 b k s 策略的基本调度过程9 3 r b s 算法的基本调度过程9 5 j b s 算法的整型缓存策略9 7 j b s 客户端和服务器端的交互过程。1 0 1 j b s 算法在单一流下的功率节省性能1 0 7 不同算法在1 6 k b p s 的c b r 流下的功率节省性能1 0 9 不同算法在6 4 k b p s 的c b r 流下的播放质量11 0 不同算法在6 4 l 曲p s 的c b r 流下的功率节省性能1 1 0 不同算法在9 2 k b p s 的v b r 流下的播放质量1 1 1 不同算法在9 2 k b p s 的v b r 流下的功率节省性能1 11 j b s 算法的功率节省性能随整型缓存长度的变化1 1 3 第v i 页 围防科学技术大学研究生院博士学位论文 英文缩写 a o d a p b s c b r c d m a f t p g p s g p s h d r h s d p a m a c m t 0 f d m o f d m a p f q q o s r r r t p s f q s n r t c p t d m t d m a u d p u m t s 英文全拼 a u d j oo nd e m a n d a c c e s sp o i n t b a s es t a t i o n 缩略词 c o n s t a n tb i tr a t e c o d ed i v i s i o nm u i t i p l ea c c e s s f i l et 啪s f e rp r o t o c o i g e m e r a l i z e dp r o c e s s o rs h a r i n g g l o b a lp o s j t i o n i n gs y s t e m h 迳hd a t a r a t e h i g hs p e e dd 0 w n i n kp a c k e ta c c e s s m e d i aa c c e s sc o n t r 0 1 m o b i l et e m i n a l 中文 音频点播 访问接入点 基站 恒定码率 码分多址 文件传输协议 通用处理器共享 全球定位系统 高速率数据 高速下行分组接入 媒体访问控制 移动终端 o n h o g o n a if 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 n h o g o n a lf r e q u e n c ym u l t i p l ea c c e s s p a c k e tf a i rq u e u e i n g q u a l i 哆o fs e r v i c e r o u n dr d b i n r e a l - t i m et r a n s p o np r o t o c o l s t a r t t i m ef a i rq u e u i n g s i g n a l t on o i s er a t i o t r a n s m i s s i o nc o n 廿o ip r o t o c 0 i t i m ed i v i s i o nm u l t i p l e x i n g t i m ed i v i s i o nm u l t i p l ea c c e s s u s e rd 她l g m l mp r o t o c a l u n i v e r s a lm o b i l et e l e c o m m u n i c a t i o n s s y s t e m 正交频分多址 分组公平排队 服务质量 轮询 实时传输协议 开始时问公平排队 信噪比 传输控制协议 时分复用 时分多址 用户数据报协议 通用移动通信系统 箢1 2 0 页 国防科学技术大学研究生院博士学位论文 第1 2 l 页 独创性声明 本人声臻所呈交戆学位论文是我本人在导师指导下避 亍的研究王俸及取得蟓掰 究成暴。尽我所知，除了文中特别如淡标注和致谢妁地方外，论文审不包含其德人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题露：莲垡匿鳖佥丝塑鏖篡i 壑墨窭 学位论文作者签名l 。基吣皇 。 窭辩： 沙弩年3 冀f 臻 学位论文版权使用授权书 本人完全了鳃国防科学技术大学有关像馨、使用学位论文昀规定。本人授权国 防科学技术大学可以保壑并淘国家煮关部 飞或机构送交论文的美颦 串和电子文档，允 许论文被查阅静借阕；可娃将学位论文的金部或部分内容编入纛关数据库避行检索， 可泼采用影帮，缩帮或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名：艮l 作者指导教癖懿：熬墨咀魁 爨期： ，参妒参年歹月毒 毽 譬裳：年胄 器 国防科学技术大学研究生院博士学位论文 第一章绪论 1 1 研究背景 随着无线通信技术的飞速发展，当前的无线通信系统同时面临着用户数量迅 速增加和用户对各种多媒体服务要求不断提高这两项重要挑战。为了应对这些挑 战，无线通信系统必须在不断提高系统容量的基础上，保证不同用户获得满意的 服务质量( q u a l i t ) ，o f s e r v i c e ，q o s ) 。 大量研究发现【l 刁】，在很多应用环境下，无线信道具有明显的时变衰落特性。 在一个多用户共享信道的无线网络中，通过设计有效的分组调度算法，不仅能够 充分利用无线信道的时变特性提高频谱利用率、增加系统容量，而且还能够根据 不同业务的特点，确定合理的资源分配策略，以满足不同用户的q o s 。此外，在 功率受限的情况下，通过分组调度算法的设计还能够显著节省移动终端的功率损 耗、延长其使用时间，这使得分组调度算法的研究对于增强无线网络性能更具实 用价值。因此，论文将无线分组调度算法作为研究对象，主要针对时变信道环境 下时分复用( t d m ) 的无线网络分组调度机制展开研究。 到目前为止，人们对有线网络的分组调度问题的研究已渐进成熟1 4 ，5 j 。由于有 线链路具有传输带宽恒定的性质，基于有线网络的分组调度算法能够在任意短的 时间内为所有业务流提供明确的吞吐量和时延保证，从而使有线网络用户能够获 得很好的q o s 。然而，我们很难将针对有线网络设计的分组调度算法直接移植到 无线网络环境当中，这是因为无线网络本身较之有线网络具有很多特殊性，因此， 对无线网络分组调度算法展开深入研究十分必要。概括的说，无线网络的特殊性 主要体现在以下几个方面： 信道条件的时变特性 网络性能与信道条件密切相关 服务公平性与传输有效性相互矛盾 无线网络与有线网络的最大区别在于：无线网络中移动用户的信道条件在大 尺度的路径损耗、阴影衰落以及小尺度的多径衰落等多种因素的影响下，表现出 了明显的时变特性。传统的无线分组调度算法将无线信道建模为具有o n 和o f f 两种状态的马尔可夫链模型：在o f f 状态下，信道处于差错状态，链路容量为0 ， 此时无法进行传输；而在o n 状态下，信道处于无差错状态，链路容量为全部信 道带宽。基于该信道模型的一些具有代表性的分组调度算法包括：c s d p s l 6 j ， 1 w f q 【7 】，c i f q 【8 1 ，s b f a 【明等。此类算法的设计目标是为用户提供公平的服务，它 们需要着重解决的问题是：如何为经历过差错信道的用户提供补偿服务，同时尽 第l 页 国防科学技术大学研究牛院博士学位论文 量彳i 影响其他用户的性能。对基于o n o f f 模型的无线调度算法的详细介绍可见 于文献 1 0 ，1 1 】。这类算法的最大缺陷在于并未考虑到实际通信系统中传输速率的 可变特性。 实际上，当前的无线信道已逐渐具备多个连续的信道状态，系统