（通信与信息系统专业论文）cdma2000+1x+evdv系统分组调度算法研究.pdf

摘要 无线网络中的分组调度器在分组数据到达网络节点时，对到达的各种业务的 数据包进行排队、分配无线资源，如w a l s h 码、时隙和频率等，以满足网络系统 的不同性能要求。本文以c d m a 2 0 0 0l xe v - d v 系统为背景，对无线分组调度算 法进行了研究和仿真，主要工作如下： 1 采用基于效用函数的规划方法对分组调度算法的基本原理做了阐述。在介绍 效用函数的基础上，分析了三种基于效用函数的调度模型，即u 调度、s 调 度和j u s 调度，分析发现：不同性能的调度算法在u 调度、s 调度和j - t i s 调 度中分别体现为用户目标函数u o f 、系统目标函数s o f 和用户一系统目标函 数u s o f 的不同。 2 对三种典型的分组调度算法进行了仿真研究。从理论和仿真两方面对最大载 干比调度、轮循调度和正比公平性调度等三种典型调度算法的系统吞吐量性 能和用户公平性性能进行了分析和比较。 3 对能够取得吞吐量和公平性折衷的调度算法做了仿真研究和改进。首先对加 性联合优化和乘性联合优化调度进行了理论分析，并通过仿真研究了两者的 性能，以及各自的参数对性能的影响。然后在最大载干比调度和轮循调度基 础上，提出了基于吞吐量划分的混合调度算法，并通过仿真对该混合调度算 法的性能进行了分析。 4 对保障服务质量的调度算法进行了仿真研究。以保障服务速率为例，通过理 论分析和系统仿真对基于指数栅栏函数的调度和基于二次栅栏函数的调度等 两种调度算法的速率保障性能进行了研究，并且分析了各自的参数变化对调 度性能的影响。 关键词：e v - d v ，分组调度，系统吞吐量，用户公平性，服务质量，最大载 干比调度，轮循调度，正比公平性调度，效用函数，栅栏函数 a b s t r a c t p a c k e ts c h e d u l e ri nw i r e l e s sn e t w o r ki su s e dt oq u e u ev a r i o u sk i n do fd a t a p a c k , s ，a l l o c a t ew i t l e s sr e s o u r c e s ，e g w a l s hc o d e s ，t i m es l o t sa n df f e q u e n c s oa s t os a r i s f yk i n d so fs y s t e m s p e r f o r m a n c ed e m a n d t h i sd i s s e r t a t i o nf o c u s e so nt h e r e s e a r c h i n go fp a c k e ts c h e d u l i n ga l g o r i t h m si nc d m a 2 0 0 0 l xe v - d vs y s t e m t h e m a i nc o n t e n t sa r ea sf o l l o w s ： 1 w ee x p a t i a t e o nf u n d a m e n t a lo fp a e k e t s c h e d u l i n ga l g o r i t h m su s i n g u t i l i t y - b a s e do p t i m i z a t i o nt e c h n i q u e s w ea n a l y s et h r e es c h e d u l i n gm o d e l sb a s e d o nu t i l i t yf u n c t i o n ，i e us c h e d u l i n gm o d e l ，ss c h e d u l i n gm o d e la n dj u s s c h e d u l i n gm o d e l ，a n d ac o n c l u s i o ni sd e r i v e d ：d i f f e r e n tp a c k e ts c h e d u l i n g a l g o r i t h m sw i t hd i f f e r e n tp e r f o r m a n c ea r et h ee m b o d i m e n to f d i f f e r e n tu s e ro b j e c t f u n c t i o n 口o f ) ，d i f f e r e n ts y s t e mo b j e c tf u n c t i o n ( s o f ) a n dj o i n t ( u s e ra n ds y s t e m ) o b j e c tr u c t i o n ( u s o f ) c o r r e s p o n d i n g t ous c h e d u l i n gm o d e l ，ss c h e d u l i n gm o d e l a n dj u ss c h e d u l i n gm o d e l 2 w ea n a l y s et h et h r e er e p r e s e n t a t i v ep a c k e ts c h e d u l i n ga l g o r i t h m s m a xc f l ， r o u n dr o b i na 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 ga r et h et h r e er e p r e s e n t a t i v e p a c k e ts c h e d u l i n ga l g o r i t h m s ，w ec o m p a r e t h e i r p e r f o r m a n c e o f s y s t e m t h r o u g h p u ta n du s e rf a i r n e s st h r o u g ht h e o r ya n a l y s i sa n dc o m p u t e rs i m u l a t i o n 3 w er e s e a r c ho nt h ep a c k e ts c h e d u l i n ga l g o r i t h m se n a b a l i n gt r a d e - o f fb e t w e e n s y s t e mt h r o u g h p u ta n du s e rf a i r n e s s f i r s t l y , w ea n a l y s es y n t h e t i c a lp e r f o r m a n c e o fa d d i t i v ej o i n to p t i m i z a t i o n s c h e d u l i n ga l g o r i t h ma n dm u l t i p l i c a t i v ej o i n t o p t i m i z a t i o ns c h e d u l i n ga l g o r i t h mt h r o u g ht h e o r ya n a l y s i s a n d c o m p u t e r s i m u l a t i o n ，a n dt h ec h a n g i n gr u l eo f s y n t h e t i c a lp e r f o r m a n c ew h e nt h e i rp a r a m e t e r c h a n g e di sa l s od i s c u s s e da tt h es a m et i m e t h e n ，w ep r o p o s eah y b r i ds c h e d u l i n g a l g o r i t h mb a s e do nm a x c is c h e d u l i n ga n dr o u n dr o b i ns c h e d u l i n g ，w ea l l a l y s e i t sp e r f o r m a n c et h r o u g ht h e o r ya n a l y s i sa n dc o m p u t e rs i m u l a t i o n i i i a b s t r a c t 4 w eh a v ear e s e a r c h i n go ut h es c h e d u l i n ga l g o r i t h m st h a tg u a r a n t e eu s e r s q u a l i t yo fs e r v i c e w ea n a l y s et h ep e r f o r m a n c eo fg u a r a n t e e i n gu s e r s d a t ar a t eo f t h et w os c h e d u l i n ga l g o r i t h m si n c l u d i n gs c h e d u l i n gb a s e do ne x p o n e n t i a lb a r r i e r f u n c t i o na n ds c h e d u l i n gb a s e do nq u a d r a t i cb a r r i e rf u n c t i o nt h r o u g ht h e o r y a n a l y s i sa n dc o m p u t e rs i m u l a t i o n ，a n dt h ei n f l u e n c eo np e r f o r m a n c ei n t r o d u c e db y t h e i rp a r a m e t e r k e y w o r d s ：e v - d v , p a c k e ts c h e d u l i n g ，s y s t e mt h r o u g h p u t ，u s e rf a i r n e s s ， q u a l i t y o fs e r v i c e ( q o s ) ，m a xc i ，r o u n dr o b i n ，p r o p o r t i o n a lf a i r n e s s ，u t i l i t y f u n o t i o n b a r r i e rf u n c t i o n 插图目录 图1 1 ：基站中无线资源管理算法的基本模型 图1 2 ：无线分组调度模型 图2 1 图2 2 一些语音、数据和多媒体业务的用户效用函数 系统效用函数举例 图3 1 ：c d m a 2 0 0 0 系统提供数据业务时的协议结构 图3 2 ：c d m a 2 0 0 0 ( r e l e a s ec ) 协议层结构 图3 3 ：1 xe v - d v 前向链路功率资源举例一 图3 4 ：小区分布示意图 图3 5 ：用户归一化分组呼叫吞吐量累积分布函数示例 图4 1 ：最大载千比调度流程图4 1 图4 2 ：轮循调度流程图4 2 图4 3 ：正比公平性调度流程图4 4 图4 4 ：h t t p 业务三层模型一4 5 图4 5 ：分组呼叫解析模型4 7 图4 6 ：h t t p 业务简化模型4 7 图4 7 ：h t t p 业务生成简化模型4 8 图4 8 ：扇区平均数据吞吐量5 0 图4 9 ：扇区平均分组呼叫吞吐量5 0 图4 1 0 ：用户归一化分组呼叫吞吐量累积分布函数曲线5 1 图4 1 1 ：用户分组呼叫吞吐量累积分布函数曲线5 2 图4 1 2 ：用户平均分组呼q q 延时5 3 图5 1 ：加性联合优化调度流程图 图5 - 2 ：加性联合优化调度中参数k 对调度性能的影响 图5 3 ：乘性联合优化调度流程图 图5 4 ：乘性联合优化调度中参数k 对调度性能的影响， 5 6 5 7 5 9 6 0 他眩 捞孔弛站弱 插图目录 图5 5 ：扇区平均数据吞吐量6 1 图5 6 ：用户归一化分组呼叫吞吐量累积分布函数曲线6 2 图5 7 ：用户分组呼叫吞吐量累积分布函数曲线6 3 图5 8 ：扇区平均数据吞吐量6 4 图5 9 ：用户归一化分组呼叫吞吐量累积分布函数曲线6 4 图5 1 0 ：用户分组呼叫吞吐量累积分布函数曲线6 5 图5 1 1 ：基于吞吐量划分的混合调度流程图一6 7 图5 1 2 ：吞吐量门限值强对系统性能的影响6 9 图5 1 3 ：基于吞吐量划分的混合调度器功能模块示意图7 0 图5 ，1 4 ：赢区平均数据吞吐量7 1 图5 1 5 ：用户归一化分组呼叫吞吐量累积分布函数曲线7 1 图5 ，1 6 ：用户分组呼叫吞吐量累积分布函数曲线7 2 图6 1 ：基于指数栅栏函数的调度流程图 图6 2 ：基于指数栅栏函数的调度下的用户平均速率 图6 3 ：基于二次栅栏函数的调度流程图 图6 4 ：基于二次栅栏函数的调度下用户平均速率 圈6 5 ：最大载干比调度下用户平均速率 图6 6 ：正比公平性调度下用户平均速率 图6 7 ：轮循调度下用户平均速率 v 1 1 1 7 6 8 l 8 3 8 5 8 6 8 6 8 7 表4 1 表4 2 表6 1 表6 2 表6 3 表6 4 表格目录 系统仿真基本假设 业务模型参数 业务模型参数服从的分布 仿真中采用的几种业务类型参数 基于指数栅栏函数的调度方式下各用户的平均服务速率统计 各种调度方式下各用户的平均服务速率统计 4 6 4 8 7 8 7 8 7 9 8 0 1 6 q a m 3 g 3 g p p 2 8 p s k a 2 i r a c k a m c a r q b 3 g b s b s c b t s c a c c d f c d m c d m a c d m a 2 0 0 0 e p e v - d o e v d v f c s f f c h f p d c c h f p d c h 缩略语 1 6q u a d r a t u r ea m p l i t u d em o d u l a t i o n 3 t hg e n e r a t i o n t h r dg e n e r a t i o np a r t n e r s h i pp r o j e c t2 8p h a s es h i f tk e y i n g a s y n c h r o n o u sa d e 【p t i v e i n c r e m e n t a l r e d u n d a n c y a c k n o w l e d g e m e n t a d a p t i v em o d u l a t i o na n dc o d i n g a u t o m a t i cr e p e a tr e q u e g b e y o n d3 t hg e n e r a t i o n b a s es t a t i o n b a s es t e l i o nc o n t r o l l e r b a s et r a n s c e i v e rs y s t e m c a i ia c c e s sc o n t r o i c u m u l a t i v ed i s t r i b u t i o nf u n c t i o n ， c o d ed i v i s i o nm u l t i p l e x c o d ed i v i s i o nm u l t i p l ea c c e s s c o d ed i v i s i o nm u k i p l ea c c e s s2 0 0 0 e n c o d e rp a c k e t e v o l u t i o n d a t ao n l y e v o l u t i o n d a t aa n dv o i c e f a s tc e l ls e l e c t i o n f o r w a r d - f u n d a m e n l a lc h a n n e i f o r w a r d p a e k e td a t ac o n t r o jc h a n n e 】 f o r w a r d - p a c k e td a t ac h a n n e i 1 6 阶正交幅度调度 第三代移动通信 第三移动通信伙伴计划2 8 进移相键控 异步自适应递增冗余 接收成功确认 自适应调制编码 自动重传请求 3 代后移动通信 基站 基站控制器 基站收发信系统 呼叫接入控制 累积分布函数 码分复用 码分多址接入 码分多址接入2 0 0 0 编码器数据包 快速小区小区 前向基本信道 前向分组数据控制信道 前向分组数据信道 缩略语 f s c h f t p g p r s g p s g s m h a r q h c i p i r l a l a c l c m a c m c s m i m o m s n f r _ u n a c k p c p c f p d c h c f p d s n p i c h p p p p s q o s q p s k f o r w a r d - s u p p l e m e n t a lc h a n n e l f i l et r a n s f e rp r o t o c o l g e n e r a ip a c k e tr a d i os e r v i c e 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 l o b a l s y s t c m f o r m o b i l e c o m m u n i c a t i o n s 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 h a n d o f f c o n t r 0 1 i n t e r n e tp r o t o c o l i n c r e m e n t a lr e d u n d a n c y l i n k a d a p t a t i o n l i n ka c c e s $ c o n t r o l l o a dc o u t r o l m e d i u ma c c e s sc o n t r o l m o d u l m i o na n dc o d i n gs c h e m e m u l t i p l ei n p u tm u l t i p l eo u t p u t m o b i l es t a t i o n m a x i m u mt r a r t s f e fu n i t u n a c k n o w l e d g e d p o w e rc o n t r o l p a c k e tc o n t r o lf u n c t i o n p a c k e td a mc h a n n e lc o n t m lf u n c t i o n p a c k e td a t as e r v i n gn o d e p i l o tc h a n n e l p o i n t t o p o i n tp r o t o c o l p a c k e ts c h e d u l i n g q u a t i t yo fs e r v i c e q u a t e r n a r yp h a s es h i f tk e y i n g 前向补充信道 文件传输协议 通用分组无线业务 通用处理机共享 全球移动通信系统 混合自动重传请求 切换控制 互联网协议 递增冗余 链路自适应 链路接入控制 负载控制 媒体接入控制 调制编码方案 多输入多输出分集技术 移动台 最大传输单元 接收错误确认 功率控制 分组控制功能 分组数据信道控制功能 分组数据业务节点 导频信道 点到点协议 分组调度 服务质量 四进移相键控 东南大学项士学位论文 r a a r a c k c h r - c q i c h r l p r n r r m s f i s o f s p t c p n ) m u d p u f u o f w d v i a 、v f i 下s r e s o u r c ea l l o c a t i o na l g o r i t h m r e v e r s e a c k n o w l e d g e m e n tc h a n n e l r e v e r s e - c h a n n e lq u a l i t yi n d i c a t i o n c h a n n e l r a d i ol i n kp r o t o c o l r a d i on e t w o r k r a d i or e s o u r c em a n a g e m e n t s e r v i c ef a i r n e s si n d e x s y s t e mo b j e c t i v ef u n c t i o n s u b p a c k e t t r a n s f e rc o n t r o ip r o t o c o l t i m ed i v i s i o nm u l t i p l e x u s e rd a t ap r o t o c 0 1 u t i l i t yf u n c t i o n u s e ro b j e c t i v ef u n c t i o n w i d e b a n dc o d ed i v i s i o nm u l t i p l ea c c e s s w o r s t c a s ef a i r n e s si n d e x w i r e l e s sf a i rs e r v i c e 资源分配算法 反向确认信道 反向信道质量指示倍道 无线链路协议 无线网络 无线资源管理 服务公平指数 系统目标函数 子数据包 传输控制协议 时分复用 用户数据包协议 效用函数 用户目标函数 宽带码分多址接入 最坏公平指数 无线公平服务 学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名 日期：边： ，形 关于学位论文使用授权的说明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括 刊登) 授权东南大学研究生院办理。 第1 章绪论 当第三代( 3 g ) 移动通信系统的开发工作正在如火如荼地进行时，有关“后 3 g ( b 3 g ) ”移动通信系统的研究工作也悄然开始。 1 1研究背景 第三代移动通信系统具有支持多媒体业务的能力，可以根据具体的业务要 求，提供必要的系统带宽。第三代移动通信系统所支持的多媒体业务一般可以划 分为会话类型、数据流类型、交互类型和后台类型例。随着信息技术的不断发展， 移动通信技术和i n t e r n e t 技术逐渐呈现日益融合的趋势，高速数据业务将成为移 动通信系统业务的主要组成部分，这就对移动通信系统的系统容量和通信质量提 出了更高的要求剐。因此，如何有效地利用有限的无线资源实现系统性能的最大 化是移动通信领域所要解决的核心问题。 1 1 1无线资源管理( r r m ) 无线通信系统的无线资源主要包括以下几个方面： 信道资源，往往表现为对隙、频带、码等形式； 信号发射功率； 基站或基站天线，等。 所谓无线资源管理就是根据系统的具体情况，合理地为接入的业务分配和管 理上述无线资源，以使系统的性能( 妇频谱利用率等) 最大化。 实际上，无线资源管理涉及移动台( m s ) 与基站( b s ) 之间建立无线链路 的问题，包括选择基站、信道分配、上行( 移动台到基站) 和下行( 基站到移动台) 发射功率控制等等，这些操作统称为资源分配算法限a a ，r e s o u r c ea l l o c a t i o n a l g o r i t h m ) 。无线资源管理主要负责对系统可以使用的所有无线资源进行分配和 管理，其核心问题是在保证网络服务质量的前提下提高频谱利用率。其基本出发 点是在网内话务量分布不均匀，且信道的状态因信号衰落和干扰而起伏变化的状 1 第1 幸绪论 况下，设法灵活地分配和及时调整可用资源。无线资源管理技术主要包括呼叫接 入控制( c a c ) 、分组调度( p s ) 、功率控制( p c ) 、切换控制( h c ) 、负载控制 ( l c ) 等。上述各种功能都是通过相应的算法来实现的，其中接入控制、负载 控制和分组调度是面向网络的算法，而功率控制和切换控制是面向各个连接的算 法。图l ，1 【2 j 给出了基站中无线资源管理算法的基本模型，资源估计器控制着整 个无线资源管理算法的实现。当有用户请求发生时，接入控制裁决是否接入该请 求，对于电路交换类型业务，若被接入则经功率控制后就可以直接发送出去；对 于分组交换类型业务菪被接入后则根据业务类型送到相应的队列中，随后，队 列调度器进行发送调度，若采用的是时间调度器。则进行时隙分配。图1 1 中的 功率和速率调度器完成对发射功率和发送速率的分配。 一一一- ：由资源估计器对无线资源管理算法的控制 ，；用户的业务流和相应信息 图1 1 ：基站中无线资源管理算法的基本模型 无线资源管理的具体算法与网络结构( 宏蜂窝、微蜂窝、微微蜂窝) 、多址 接入方式( w c d m a 、e d m a 2 0 0 0 、t d s c d m a 、l a s c d m a ) 、智能天线运用方 式、业务种类和业务模型( t r a f f i cp a t t e r n ) 、越区切换方式、上行或下行场合等 因素有关网。下面对无线资源管理的主要算法做一个概述。 ( 1 ) 呼叫接 控制 接入控制过程根据系统的实际负荷决定是否接收新到达的用户的呼叫请求， 东南大学项士学位论文 从而控制系统中通话的用户数量，使系统负荷维持在一个比较稳定的水平上。接 入控制策略分为基于功率和基于吞吐量的两种方案。在接入控制中，系统需要分 别估计用户接入可能会对上、下行链路造成的影响。只有上下行两个方向的负荷 情况都允许用户业务接入系统才能批准其接入。允许用户接入的负荷门限可以在 系统的设计规划过程中设定。 例如，c d m a 系统是一个自干扰系统，其系统容量不是一个相对固定的值， 而具有较大的弹性，服务质量与同时接受服务的用户数量之间存在着平衡与折衷 的关系。如果允许用户负荷过度增长，那么小区的覆盖面积就会减少到规划数值 以下，而且已接入用户的服务质量也无法得到保证。所以合理有效的接入控制算 法对c d m a 系统的稳定运行具有重要意义。 ( 2 ) 分组调度 分组调度功能是在分组用户之间共享可用的空中接口资源。分组调度能决定 码速率和相应的数据长度。 在c d m a 中，分组调度可采用两种方式：码分或时分。在码分方式下，大 量的用户可同时使用一个低速率信道。当用户容量需要增加时，码速率就要降低。 在时分方式下，在某一时刻所有资源可被分配给一个或少数的几个用户。这样一 个用户可在一个非常高的码率下传输。当在时分方式下用户数增加时，每个用户 都要等待较长的时间来传输。 ( 3 ) 功丰控制 在c d m a 系统中，由于用户共用相同的频带，且各用户的扩频码之间存在 着非理想的相关特性，用户发射功率的大小将直接影响系统的总容量，从而使得 功率控制技术成为c d m a 系统中的最为重要的核心技术之一。常见的c d m a 功 率控制技术可分为开环功率控制、闭环功率控制和外环功率控制三种类型。开环 功率控制的基本原理是根据用户接收功率与发射功率之积为常数的原则，先行测 量接收功率的大小，并由此确定发射功率的大小。开环功率控制用于确定用户的 初始发射功率，或用户接收功率发生突变时的发射功率调节。闭环功率控制通过 对接收功率的测量值及与信干比门限值的对比，确定功率控制比特信息，然后通 过信道把功率控制比特信息传送到发射端，并据此调节发射功率的大小。外环功 第1 聿绪论 率控制技术则是通过对接收误帧率的计算，确定闭环功率控制所需的信干比门 限。在w c d m a 和c d m a 2 0 0 0 系统中，上行信道采用了开环、闭环和外环功率控 制技术，下行信道则采用了闭环和外环功率技术。但两者的闭环功率控制速度有 所不同，前者为每秒1 5 0 0 次，后者为每秒8 0 0 次。 ( 4 ) 切换控羽 当一个移动台从一个基站的覆盖范围移动到另外一个基站的覆盖范围，通过 切换移动台保持与基站的通信，可以分为硬切换、软切换和更软切换三种方式。 硬切换在切换过程中，移动台先中断与原来基站的通信，再与目标基站取得 联系。一般发生在分配不同频率或者不同的帧偏置的c d m a 信道之间。 软切换是指移动台在中断与原来基站的业务通信之前，和工作在相同频点的 另一基站建立起业务联接。软切换是c d m a 系统特有的关键技术之，是系统 无线资源与优化的重点，软切换算法和相关参数的设置直接影响着系统的容量和 服务质量。软切换用户比例过低会降低宏分集增益，减小系统容量，而如果软切 换用户比例过高则会占用基站过多的发射功率，占用过多的无线资源，同样会造 成系统容量的下降。 更软切换是一个基站内不同扇区之间的切换，它是由一个基站完成的，不同 的扇区天线相当于不同的多经分量被合并成个话音帧送至选择器，作为此基 站的语音帧。 ( 5 ) 负栽拔制 无线资源管理功能的一个重要任务是确保系统不要过载，保持系统运行的稳 定。如果系统规划适当。接入控制和分组调度就能工作得很好，过载的情况就能 避免。如果遇到了过载的情况，负载控制功能让系统快速而有控制地达到目标负 荷。下面是为了减少负荷而采取的必要的负荷控制措施：下行快速负载控制： 拒绝由移动台发出的下行功率增加命令。上行快速负载控制：降低由上行快速 功控使用的上行目标e c i o 。降低分组数据业务的吞吐量。切换到另一个 c d m a 2 0 0 0 的载波。与i s 9 5 之间的切换。减少实时业务的码速率。受控 方式下的掉话。 4 东南大学硕士学位论文 1 1 2无线分组调度 传统的有线传输网络从交换的角度可以分为电路交换网和分组交换网，分组 调度算法是应分组交换网的需要而逐步发展起来的一个研究领域。分组调度算法 也称队列调度算法，它运行在网络节点中发生冲突需排队等待调度之处，按照一 定的服务规则对交换节点的不同输入业务流分别进行调度和服务，使所有的输入 业务流能按预定的方式共享交换节点的输出链路带宽5 ”。 根据不同的服务规则，分组调度算法可以分为以下几种：先到先服务、循环 调度、处理机共享、优先级服务、随机服务等。根据调度算法的调度目标，也可 分为基于时延的和基于速率的这两类。根据通信网络环境，又可分为无线环境下 的分组调度【5 0 5 0 6 0 7 】和有线环境下的分组调度。根据调度算法的工作状态，又可 以分为工作保持( w o r k i n g - c o n s e r v i n g ) 和非工作保持( n o n w o r k i n g c o n s e r v i n g ) 2 8 o 其中工作保持算法表示只要系统中有等待分组，调度算法就一定会工作：而 非工作保持算法则意味着即使系统中有等待分组，调度算法也可能暂时不对其进 行调度。工作保持算法具有更高的链路利用率，而非工作保持算法能对端到端时 延及时延抖动进行很好的控制。 实际上，对于某一特定的调度算法，根据不同的分类标准，它可能属于多个 不同的类，所以并没有一种统一的分类标准。根据调度算法的服务规则、调度目 标及其发展趋势，同时为了能更清晰地说明各类算法之间的区别，我们可以把目 前已出现的队列调度算法大致分为如下五类：基于轮循的调度算法、基于优先级 的调度、基于通用处理机共享( 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 ) 的算法、基于 时延的调度算法、基于服务曲线( s e r v i c ec u r v e ) 的算法等。 评价有线分组调度算法性熊的好坏主要涉及到时延性能、公平性、复杂性这 三个方面。分组调度算法可能在不同环境下有不同的应用。例如，分组调度算法 可能被用于隔离恶意业务流来为正常业务流提供服务质量( q o s ) 保证；分组调度 算法还可能用来让用户平等的分享链路的可用带宽，或者用来实现分级的链路共 享等。实际上，有效的分组调度算法应该拥有诸多好的特性，即下面要讨论的队 列调度算法应达到的主要性能指标。 时延性能：队列调度算法应为不同的业务流提供端到端的时延保证，而且只 第1 章绪论 与此业务流的某些参数( 如带宽需求等) 有关，而与其他的业务流无关。s t i l i a d i s 和v a r m a 首先提出了一种分析网络中不同队列调度算法带来的端到端时延的模 型：时延速率调度器( l r s ，l a t e n c y r a t es e r v e r ) 。c h i u s s i 随后又提出了另一种分 析端到端时延的模型：速率分隔时签调度器( r s t ，r a t e s p a c e d t i m e s t a m p s c h e d u l e r ) ，此模型的限制条件比l r s 要少且在定长分组环境下应用时更加有效。 公平性：可用的链路带宽必须以公平的方式分配给共享此链路的各业务流； 此外分组调度算法必须能够隔离不同的业务流，让不同的流只能获取自己应该享 用的带宽，这样即使存在恶意或高突发性业务，它也不致影响到其他的正常业务 流。一个不公平的调度算法可能会在一较短的时间间隔里给预约了相同带宽的两 个业务分配不同的服务速率。关于调度算法公平性的定义有：服务公平指数( s r i ， s e r v i c ef a i r a e s si n d e x ) 9 , 1 1 埽最坏公平指数( w f i ，w o r s t - e a s ef a i r n e s si n d e x ) t ：7 1 9 ，1 1 1 两种。s f i 表示任意两个活动队列在任意时间间隔内受到的归一化服务量f 等于服 务量与其分配的服务速率的比值) 的最大差值；w f i 用来表示个队列在分组级 系统和相应流系统上接受到的服务量的最大差值，较大的w f i 意味着该调度算法 输出业务量有较大的突发性。 复杂性和可扩展性：调度算法实现起来必须比较简单。在高速网络中，传输 一个分组的时间很小，所以调度算法必须在短时间里完成对分组的调度，这就要 求调度算法尽量简单，易于实现。另外当业务流数量增加和链路速率变化范围较 大时，调度算法仍应有效工作；这要求调度算法应该具有良好的可扩展性。 本论文研究的主要内容是无线系统中的分组调度算法。在无线分组网络中， 分组调度的作用和有线网络中相同。但是，无线网络同有线网络相比具有很大的 特殊性，最重要的三点就是带宽的有限性、信道的位置依赖性以及突发和高的信 道误码特性。为了充分地利用带宽，当由于误码或其它原因造成某一正在传递数 据的连接暂时中断，系统应该将该信道临时分配给别的连接。为了实现公平性， 在暂时中断服务的连接恢复正常以后，获得额外服务的连接就当作出补偿。因此 基于有线网络的分组调度算法不能直接应用于无线网络。另外，在有线网络中， 分组调度器所分配的资源比较单一，通常是分配时隙资源，而在无线网络中，尤 其是在3 g 及“b 3 g ”网络中，分组调度器所需考虑的分配资源可能是多方面的， 6 东南大学硕士学位论文 如频率、时隙、w a l s h 码及发射功率等。图1 2 描述了无线分组调度的基本模型： 不同输八业务流随机到达网络节点，由队列管理实体按照一定的排队规则排队进 入相应的队列等待调度，调度器可以获得分组传输结果和信道质量等环境信息， 网络管理者可以配置调度器的目标参数，调度器根据当前系统的各种信息，将频 率、时隙、w a l s h 码和功率等无线资源分配给系统中的分组队列。分组调度算法 就是调度器根据当前的队列状况、环境信息和目标参数，将各种信道资源分配给 数据队列的所遵循的一定规则。 芦 据毒 图12 ：无线分组调度模型 在g p s 等有线网络调度算法的基础上，结合无线网络的特点，许多学者提出 了一些无线分组调度算法来保障用户公平性：s o n g w u l u 等提出了w f s ( w i r e l e s s f a i rs e r v i c e ) 算法【4 】，t s e u g e n e n g 等提出了c i f q ( c h a n n e l - c o n d i t i o ni n d e p e n d e n t p a c k e tf a i r n e s sq u e u e i n g ) 算法嘲，p r a m a n a t h a n 提出了s b f a ( s e r v e rb a s e d f a i r n e s s a p p r o a c h ) 算法1 6 】，以及如w 产q 、耵幻+ 、s c f q 、s f q 、f f q 、s p f q 等等算法m ，- o j i j 2 。这些调度算法是在有线网络调度算法的基础上改进得到的， 第l 章绪论 而有线网络调度算法的设计目标通常只是提供用户公平性和业务端到端时延保 障，因此这些改进后的无线调度算法也属于公平性调度算法，即以用户公平性和 业务时延保障为目标，不考虑如何提高无线信道的吞吐量。而这一点，对于信道 资源相对不足的无线网络来说是一个明显的缺陷，也是实际无线系统设计时需要 考虑的问题。 本论文的研究内容决定了在讨论各种调度算法的时候，无线系统的吞吐量是 衡量调度算法的一个重要的性能指标，加之前面给出评价公平性调度算法的时延 性能、公平性和复杂性三个指标将构成本文评价调度算法的基本指标。另外，根 据各种业务服务质量( q o s ) 的不同，可以将业务做多种方法的分类：按照端到 端不同的时延要求，可以将业务分为实时性业务和非实时性业务，v f j 女n i r , 电话就 是典型的实时性业务，它需要保障业务的端到端的延时，主观测量表明这种延时 不能超过4 0 0 m s t 5 0 l ，而f t p 文件下载业务是典型的非实时性业务，不需要保障端 到端时延；按照服务速率的不同可以将业务划分为不同等级的服务类型，如 1 6 k b p s ，3 2 k b p s ，6 4 k b p s ，1 2 8 k b p s ，2 5 6 k b p s ，3 8 4 k b p s 等等类型a 对不同业务所 要求的服务质量不同提供不同的服务质量保障性能，也是本论文在研究一些保 障q o s 调度算法时重要的评价指标。 1 2论文的研究工作 本文基于c d m a 2 0 0 0l xe v - d v 系统，研究了前向分组数据信道( f p d c h ) 的分组调度算法，包括不区分服务等级的分组调度算法，如最大载干比调度、轮 循调度和正比公平性调度等，以及区分业务服务等级的分组调度算法，如基于指 数栅栏函数的调度等。论文主要内容安排如下： 第2 章采用基于效用函数的规划方法对调度算法的基本原理做了阐述，并且 分析了三种基于效用函数的调度模型，即u 调度、s 调度和j u s 调度。 第3 章描述了c d m a 2 0 0 0l xe v - d v 系统的关键