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

摘要 无线网络中的分组调度技术是在网络数据到达的节点处，对到达的 各种业务的数据包进行排队、分配网络无线资源，如信道码、时隙和频 率等，以最大限度地提高网络无线资源豹利用率，满足多个用户所需要 的服务质量本文以使用了h s d p a 技术的w c d m a 系统为背景，研究 如何在数据到达节点一一n o d eb 端，使用合理的数据分组调度算法 全文的内容安排如下： 首先针对一般的无线通信系统，分析了分组调度算法的要素，并对 分组调度问题进行了数学建模然后简要介绍了h s d p a 技术的主要特 点，以及由此对分组调度算法研究所带来的一些新问题 本文第三章对现有研究文献中已有的三种使用于h s d p a 的经典分 组调度方法，即轮循调度、最大载干比调度和比例公平性调度，进行了 介绍并从原理和仿真上对它们的各项性能，如系统吞吐量、分组呼叫 延时和用户公平性等，进行了比较 第四章和第五章分别介绍了作者提出的改进型的分组调度算法 在第四章，以轮循调度和最大载干比调度为基础，从对系统吞吐量 性能和用户公平性进行折中的角度考虑，提出了两种混合调度方案，即 基于载干比划分和基于时隙划分的混合调度算法，并通过仿真分析了这 两种算法的性能 在第五章中，针对多速率业务模型，提出了一种基于速率控制的调 度方法，并仿真分析了其性能 关键词：h s d p a ，分组调度，业务模型，排队模型，状态空间，信道载 干比，系统吞吐量，用户公平性，轮循调度，最大载干比调度，半公平 性调度，基于载于比划分，基于时隙划分，混合调度，速率控制 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 f d a t ap a c k e t s ，a l l o c a t ew i r e l e s sr e s o u r c e s ，e gc h a n n e lc o d e s ，t i m es l o t sa n d f r e q u e n c ya n di m p r o v et h eu t i l i z a t i o ne f f i c i e n c yo fw i r e l e s sr e s o u r c e ss oa st o s a t i s f yk i n d so fu s e r ss e r v i c ed e m a n d t h i sd i s s e r t a i o n ，w em a i n l yf o c u so n p a c k e ts c h e d u l i n ga l g o r i t h m si nn o d ebi nh s d p as y s t e m f i r s t ，b a s e do nt h eu n i v e r s a lw i r e l e s sc o m m u n i c a t i o ns y s t e m ，w ea n a l y s e t h ew o r k i n gc h a r a c t e r i s t i c sa n da s s o c i a t e dr e s e a c h i n gb a c k g r o u n do fp a c k e t s c h e d u l i n ga l g o r i t h m s w eu p b u i l das c h e d u l i n gm o d e lo fd y n a m i cb a n d w i d t h a l l o c a t i o n ，i n c l u d i n gf o u rk i n d so ft r a f f i ct y p e s ，a n d 矗n a l y s ei tf r o mv i e w p o i n t o fm a t h e m a t i c s ，t h e nw es i m p l yi n t r o d u c et h ec h a r a c t e r i s t i c so fh s d p a t e c h n i c s ，a n ds o m en e wp r o b l e m so fp a c k e ts c h e d u l i n gi n t r o d u c e db yh s d p a i nc h a p t e r3o ft h i sd i s s e r t a i o n ，w ea n a l y s et h et h r e ep a c k e ts c h e d u l i n g a l g o r i t h m s ，w h i c ha r ef i tf o rh s d p a ，i n c l u d i n gr o u n dr o b i n ，m a xc ia n d p r o p o r t i o n a lf a i r n e s ss c h e d u l e r w ec o m p a r et h e i rs e v e r a lp e r f o r m a n c ei n c l u d i n gt h es y s t e mp e r f o r m a n c e ，p a c k e t c a l ld e l a ya n d u s e rf a i r n e s st h r o u g h t h e o r ya n a l y s i n ga n dc o m p u t e rs i m u l a t i o n i nc h a p t e r4a n dc h a p t e r5w ei n t r o d u c et h ei m p r o v e dp a c k e ts c h e d u l i n g a l g o r i t h m sp r o p o s e db ya u t h o r i nc h a p t e r4o ft h i sd i s s e r t a t i o n ，w ep r o p o s et w oh y b r i ds c h e d u l i n g m e t h o db a s e do nr o u n dr o b i na n dm a xc is c h e d u l e r ，t h a ti sc i r b a s e d a n ds l o t b a s e ds c h e d u l e r w ea n a l y z e dt h e i rp e r f o r m a n c et h r o u g ht h e o r y a n a l y s i n ga n dc o m p u t e rs i m u l a t i o n i nc h a p t e r5 ，w ep r o p o s ean e ws c h e d u l i n ga l g o r i t h mb a a e do i lr a t e c o n t l o la n dw ea n a l y z e dt h e i rp 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 n ga n d c o m p u t e rs i m u l a t i o n k e y w o r d s ：h s d p a ，p a c k e ts c h e d u l e ，t r a f f i cm o d e l ，q u e u e i n gm o d e l ，s t a t e s p a c e ，c h a n n e lc i r ，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 ，r o u n dr o b i n ，m a x c i ，p r o p o r t i o n a lf a i r n e s s ，c i r - b a s e d ，s l o t b a s e d jh y b r i ds c h e d u l e ，r a t e c o n t r 0 1 插图目录 1 1w c d m a 无线接入网络结构 1 2 调度模型， 2 1 2 2 2 3 2 4 2 5 26 2 7 2 8 2 9 2 1 0 2 1 1 3 1 3 2 3 3 34 3 5 3 6 3 7 3 8 4 1 42 4 3 4 4 4 5 带宽划分示意图 由( g ，b ) 计算( f ，b ) 中带宽b ，和b 目的计算步骤 ( c ，b ) 空间的状态转移率图 ( 七，b ) 空间的状态转移率图， 新用户服务阻塞率 系统平均吞吐量 w c d m a r e l e a s e 9 9 无线调度示意图 h s d p a 无线接口协议结构 h s d p a 中u t r a n 端的m a c 层结构 m a c _ h s 功能结构。 小区分布示意图 ， 轮循调度流程图 最大载干比调度流程图 ， 比例公平性调度流程图 w e b 业务模型示意图 系统平均用户分组呼叫吞吐量 用户分组呼叫吞吐量的c d f ， 用户分组呼叫延时的c d f ， 用户分组呼叫平均服务延时分布 基于载干比戈分的混合调度流程图 载干比门限值对系统性能的影响， 基于载干比划分的混合调度器功能结构示意图 系统平均用户分组呼叫吞吐量 用户分组呼叫吞吐量的c d f ， o ， 坞 埔 ” 如 雏 鲋 弘 巧 号 盯 船 蛇 “ 舛 蛎 插图目录 46 用户分组呼叫延时的c d f 47 用户分组呼叫平均服务延时分布 4 8 本章采用的时隙划分方式 4 9 基于时隙划分混合调度流程图 41 0 m ：r 值对系统性能的影响， 4 1 l 基于时隙划分混合调度器功能结构示意图 4 、1 2 系统平均用户分组呼叫吞吐量， 4 1 3 用户分组呼叫吞吐量的c d f 41 4 用户分组呼q 延时的c d f 4 1 5 用户分组呼叫平均服务延时分布 5 1 速率控制调度流程图 ， 5 2 优先级指标计算方法 ， 53 带宽划分模型 5 4 速率控制调度器功能结构示意图 卯 们的 的h 弛 驰 弘 弱弱 骆缸 表格目录 1 1 i m t 一2 0 0 0 无线接口技术标准 2 1 四种业务特性比较 ， 2 2 a m c 下行链路数据率 3l 系统仿真基本假设 3 2 业务模型 5 1 业务模型分布 5 ，2 仿真中采用的几种业务类型参数 5 3 最大载干比调度下的用户服务速率统计 5 4 轮循调度下的用户服务速率统计 5 5 比例公平性调度下的用户服务速率统计 5 6 速率控制调度下的用户服务速率统计 5 7 不同调度方式下的数据分组延时统计量 ， 儿 盟 弘 弱 娩 鲥钮融弧阻 缩略语 3 g 3 g p p a c k a m c a m r a r q b e r b s c b t s c d m a c d f c i r c n c p g h c p i c h c r n c c s d c a d c h d s c h d r c d 。r n c f c a f c s f e c f e r f i f o f t p g i ，s g s m 缩略语 3 t hg e n e r a t i o n t h i 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 t 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 d a p t i v em u l t i r a t e ( s p e e c hc o d e c ) a u t o m a t i cr e p e a tr e q u e s t b i te r r o rr a t e b a s es t a t 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 o d ed i v i s i o nm u l t i p l ea c c e s s 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 a r r i e rt oi n t e r f e r e n c er a r i o c o r en e t w o r k c o m m o np a c i 【e tc h a n n e l c o m m o np i l o tc h a n n e l c o n t r o l l i n gr n c c i r c u i ts w i t c h e d d y n a m i cc h a n n e la l l o c a t i o n d e d i c a t e dc h a n n e l d o w n l i n ks h a r e dc h a n n e l d 砒ar a t ec o n t r o l d r i f t r n c f i x e dc h a n n e la l l o c a t i o n f a s tc e l ls e l e c t i o n f o r w a r de r r o rc o r r e c t i o n n a m ee r r o rr a t e f i r s ti n p u tf i r s to u t p u t f i l et r a r t s f e rp r o t o c o l 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 ls y s t e mf o rm o b i l ec o m m u n i c a t i o n s 第三代移动通信 第三代移动通信伙伴计划 接收成功确认 自适应调制与编码 自适应多速率( 话音声码器) 自动重传请求 误比特率 基站控制器 基站传输系统 码分多址接入 累积分布函数 载干比 核心网 公共分组信道 公共导频倍道 控制r n c 电路交换 动态信道分配 专用信道 下行共享信道 数据速率控制 漂移无线网络控制器 固定信道分配 快速小区选择 前向纠错 误帧率 先进先出准则 文件传输协议 通用处理机共享 全球移动通信系统 缩略语 h a r q h s d p a h s d s c h i p m a c m c s m i m o m t u n b u e p d c p f p m i b p s q a m q o s q p s k r c a r n c r n s r r r a a r r c s a p s b f a s f s m s s r n c t f c u e u m t s u t r a u t r a n 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 i g hs p e e dd o w n l i n kp a c k e ta c c e s s h i g hs p e e dd o w n l i n ks h a r e dc h a n n e l i n t e r n e tp r o t o c o l m e d i u ma c c e s sc o n t r o l m o d u l a t i o na n dc o d i n g s y s t e m 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 a x i m u mt r a n s f e ru n i t n u m b e ro fb a c k g r o u n d7 n a 佑cu e p e r s o n a ld i g i t a lc e l l u l a r p r o p o r t i o n a lf a i r n e s s p e r f o r m a n c em a n a g e m e n ti n f o m a t i o nb a s e p a c k e ts w i t c h e d q 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 q u a l 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 n d o mc h a n n e la l l o c a t i o n r a d i on e t w o r kc o n t r o l e r r a d i on e t w o r ks u b s y s t e m r o u n dr o b i n 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 a d i or e s o u r c ec o n t r o l s e r v i c ea c c e s sp o i n t s e r v e rb a s e df a i r n e s sa p p r o a c h s p r e a d i n gf a c t o r s h o r tm e s s a g es e r v i c e s e r v i n gr n c 、 t r a n s p o r tf o r m a tc o m b i n a t i o n u s e re q u i p m e n t 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 ss y s t e m u n i v e r s a lt e r r e s t r i a lr a d i oa c c e s s u n i v e r s a jt e r r e s t r i a lr a d i oa c c e s sn e t w o r k 混合自动重传请求 高速下行链路分组接入 高速下行共享信道 互联网协议 媒体接入控制 调制编码系统 多输入多输出分集技术 最大传输单元 后台业务u e 数目 个人数字蜂窝系统 比例公平性调度 性能管理信息基 分组交换 正交幅度调制 服务质量 四进移相键控 随机信道分配 无线网络控制器 无线网络子系统 轮循调度 资源分配算法 无线资源控制 服务接入点 基于服务的公平性方法 扩展因子 短消息服务 服务r n c 传输格式组合 用户设备 通用移动通信系统 通用陆地无线接入 通用陆地无线接入网 x n 缩略语 v o l pv b i c eo v e ri p w c d m aw 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 f sw i r e l e s sf a i rs e r v i c e 基于i p 协议的话音业务 宽带码分多址接入 无线公平服务 学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工 作及取得的研究成果尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获 得东南大学或其它教育机构的学位或证书而使用过的材料与我同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示了谢意 签名墼监日期 及胛3 、3 、工。 关于学位论文使用授权的说明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所 送交学位论文的复印件和电子文档，可以采用影印、缩印或其他复制手 段保存论文。本人电子文档的内容和纸质论文的内容相一致除在保密 期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论 文的全部或部分内容论文的公布( 包括刊登) 授权东南大学研究生院 办理 签名：量盥 导师签名 腽牝喊刎血 第一章绪论 当今世界已步入信息时代，随着社会经济的发展，人们对通信的需求不断增 长第三代移动通信技术即是应这种需求而发展起来的在此之前，称为第一代移 动通信系统的模拟蜂窝系统和称为第二代移动通信系统的数字系统例如g s m 、 p d c 、c d m a o n e ( i s 一9 5 ) 和u s - t d m a ( i s 一1 3 6 ) ，都已使得语音通信在众多世界主 要市场中能够无线化，而消费者不仅逐渐发现移动语音通信不可替代的重要作 用，同时也日益认识到诸如文本 肖息传送，数据网的接入等正在迅速成长的其他 业务的价值所在 1 1 研究背景 第三代系统是为多媒体通信设计的：通过该系统提供的高质量图像和视频， 人与人之间的通信能力进一步增强；而第三代系统所带来的更新更灵活的通信 能力和更高的数据速率使得公用网和专用网上的信息与业务的接入能力大大增 强所有这一切，连同第二代系统向第三代系统的平滑过渡，都将为设备制造商， 运营商及使用网络的应用提供商创造新的商机【6 4 1 1 1 3 g 系统的无线接口标准 从1 9 8 5 年，未来公共陆地移动通信系统( f p l m t s ) 概念首次被提出，到 2 0 0 0 年在芬兰赫尔辛基召开的i t ut g 8 1 第1 8 次会议最终通过了i m t 2 0 0 0 无 线接口技术规范建议，历经1 5 年，终于最后确立了第三代移动通信系统所包含 的无线接口技术标准该会议将无线接口的标准明确为以下5 个标准： i m t 一2 0 0 0c d m ad s 对应w c d m a c d m a 技术 i m t 2 0 0 0c d m am c 对应c d m a 2 0 0 0 i m t - 2 0 0 0c d m at d d 对应t d s c d m a 和u t r at d d t d m a 技术 i m t - 2 0 0 0t d m as c 对应u w c 一1 3 6 i m t 一2 0 0 0f d m a t d m a 对应d e c t 上述5 个名称，i t u 又进一步简化为i m t d s 、i m t m c 、i m t t d 、 2 第一章绪论 i m t s c 和i m t f t 可以说i m t 2 0 0 0 的地面无线接口标准由5 个标准构成 下面对三种c d m a 技术做简要说明： i m t 一2 0 0 0c d m ad s ( i m t d s ) 是3 g p p 的w c d m a 技术与3 g p p 2 的c d m a 2 0 0 0 技术的直接扩频部分( d s ) 融合后的技术，仍称为w c d m a 。这也是本文研 究所基于的系统此标准将同时支持g s mm a p 和a n s i - 4 1 两个核心网络 i m t 一2 0 0 0c d m am c ( i m t - m c ) ，即c d m a 2 0 0 0 ，在融合后，只含多载波方 式即1 x 、3 x 、6 x 、9 x 等此标准也将同时支持a n s i - 4 1 和g s mm a p 两大核心网 i m t 一2 0 0 0c d m at d d ( i m t t d ) 目前实际上包括了低码片速率t d s c d m a 和高码片速率u t r at d d ( t d c d m a ) 两个技术目前两个技术的物理层完 全分开，分别采用我国c w t s 和3 g p p 的两套技术规范，第2 层和第3 层基 本相同 1 1 23 g 系统的网络结构 第三代移动通信系统的网络结构必须具有较好的灵活性，以使现有的第二代 移动通信系统能够顺利地向第三代移动通信系统过渡，保护已有投资。i t u t 图1 ，l ：w c d m a 无线接入网络结构 s g l l 对i m t 一2 0 0 0 网络的功能结构、信令要求、协议等进行了研究，提出了一些 原则性的建议而欧洲方面则通过a c t sr a i n b o w 计划对第三代移动通信系 5 j i 研究背景 3 统的网络结构进行了研究，其研究成果已被e t s i 采纳总的来说，对第三代移 动通信系统网络结构的考虑应遵循如下几个原则：( 1 ) 在逻辑上将传送网和信令 网分开；( 2 ) 宏分集完全由接入网控制；( 3 ) 在功能上分为接入网和核心网 图1 1 是w c d m a 系统的无线接入网络( u t r a n ) 结构示意图u t r a n 由 无线网络予系统( r n s ) 组成，r n s 通过i u 接口与核心网相连无线网络子系统 r n s 包括无线网络控制器和一或多个n o d eb n o d eb 支持f d d 模式、t d d 模式或双模式，可处理一个或多个小区，并通过i u b 接口与无线网络控制器r n c 相连r n c 负责切换控制，提供支持不同n o d eb 间宏分集的组合、分裂的功 能支持f d d 模式的n o d eb 包含可选的宏分集功能无线网络控制器r n c 通过 i u r 接口相互连接，i u r 可通过r n c 间的物理连接直接相连或通过合适的传输网 相连 无线网络控制器( r n c ) 是负责控制u t r a n 无线资源的网络元素，它与核 心网( c n ) 相连，并且负责终止定义移动台和u t r a n 间消息和进程的无线资源 控制( r r c ) 协议r n c 在逻辑上与g s m 系统中的基站控制器( b s c ) 相对应 n o d eb 相当于g s m 系统中的基站， “n o d eb ”这个名词最初是在制定标准 的过程中作为一个临时词汇丽采用的，但从此沿用至今n o d eb 的主要功能是 进行空中接口l 1 层的处理，包括信道编码和交织、速率匹配、扩频等，另外还 执行一些基本的无线资源管理操作，例如内环功率控制等，在引入h s d p a 技术 后，还要执行一部分分组调度的功能 1 1 33 g 系统的无线资源管理技术 无线资源管理的问题涉及移动用户与基站之间建立无线链路，包括选择基 站、信道分配、上行( 手机到基站) 和下行( 基站到手机) 发信功率控制等等，这 些操作统称为资源分配算法( r a a ，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 ) 无线资源 管理的核心问题是在保证网络服务质量的前提下，提高频谱利用率其基本出发 点是在网内话务量分布不均匀，且信道的状态因信号衰落和干扰而起伏变化的状 况下，设法灵活地分配和及时调整可用资源无线资源管理技术主要包括信道资 源分配、软切换策略、功率控制、接入控制、负载控制、分组调度等 ( 1 ) 信道分配策略 在现代蜂窝网络中，随着用户密度的增加，信道分配对网络容量直接起着至 关重要的作用信道可以是多重含义：在f d m a 中，指频率或无线载波；在t d m a 中，指时隙；在c d m a 中，指正交码或p n 码而信道分配本身的范畴为其中的 第一章绪论 任何一种或两种以上的合成目前有三种分配方式，即固定信道分配( f c a ) 、动 态信道分配( d c a ) 和随机信道分配( r c a ) ( 2 ) 软切换策略 软切换是指移动台在中断与原来基站的业务通信之前，和工作在相同频点的 另一基站建立起业务联接软切换是c d m a 系统特有的关键技术之一，是系统 无线资源与优化的重点，软切换算法和相关参数的设置直接影响着系统的容囊和 服务质量软切换用户比例过低会降低宏分集增益，减小系统容量，而如果软切 换用户比例过高则会占用基站过多的发射功率，占用过多的无线资源，同样会造 成系统容量的下降 ( 3 ) 功率控制 在c d m a 系统中，由于用户共用相同的频带，且各用户的扩频码之间存在 着非理想的相关特性，用户发射功率的大小将直接影响系统的总容量，从而使得 功率控制技术成为c d m a 系统中的最为重要的核心技术之一常见的c d m a 功 率控制技术可分为开环功率控制、闭环功率控制和外环功率控制三种类型开环 功率控制的基本原理是根据用户接收功率与发射功率之积为常数的原则，先行 测量接收功率的大小，并由此确定发射功率的大小开环功率控制用于确定用户 的初始发射功率，或用户接收功率发生突变时的发射功率调节闭环功率控制通 过对接收功率的测薰值及与信干比门限值的对比，确定功率控制比特信息，然后 通过信道把功率控制比特信息传送到发射端，并据此调节发射功率的大小外环 功率控制技术则是通过对接收误帧率的计算，确定闭环功率控制所需的信于比门 限在w c d m a 和c d m u 2 0 0 0 系统中，上行信道采用了开环、闭环和外环功率控 制技术，下行信道则采用了闭环和外环功率技术。但两者的闭环功率控制速度有 所不同，前者为每秒1 6 0 0 次，后者为每秒8 0 0 次。 ( 4 ) 接入控制 c d m a 系统是一个自干扰的系统，它的系统容量不是一个相对固定的值， 而具有较大的弹性，服务质量与同时接受的用户数量之间存在着平衡与折中的关 系。如果允许空中接口负荷过渡增长，那么小区的覆盖面积就会减少到预计的数 值以下，而且已有连接的服务质量也无法得到保证所以合理有效的接入控制算 法对c d m a 系统的稳定运行具有重要意义接入控制过程根据系统的实际负荷 决定是否接收新到达的用户的呼叫请求，从而控制系统中通话的用户数量，使系 】1 研究背景 5 统负荷维持在一个比较稳定的水平上接入控制策略分为基于功率和基于吞吐量 的两种方案在接入控制中，系统需要分别估计用户接入可能会对上、下行链路 造成的影响只有上下行两个方向的负荷情况都允许用户业务接入系统才能批准 其接入允许用户接入的负荷门限可以在系统的设计规划过程中设定 ( 5 ) 负载控制 无线资源管理功能的一个重要任务是确保系统不要过载，保持稳定如果系 统规划适当，接入控制和分组调度就能工作得很好，过载的情况就能避免如果 遇到了过载的情况，负荷控制功能让系统快速而有控制地达到目标负荷下面 是为了减少负荷而采取的必要的负荷控制措施：( 1 ) 下行快速负荷控制：拒绝 由移动台发出的下行功率增加命令( 2 ) 上行快速负荷控制：降低由上行快速功 控使用的上行目标e c i o 。( 3 ) 降低分组数据业务的吞吐量( 4 ) 切换到另一个 w c d m a 的载波( 5 ) 与g s m 之间的切换( 6 ) 减少实时业务的码速率( 7 ) 受 控方式下的掉话 ( 6 ) 分组调度 分组调度功能是在分组用户之间共享可用的空中接口资源。分组调度能决 定码速率和相应的数据长度在c d m a 中，分组调度可采用两种方式：码分或 时分在码分方式下，大量的用户可同时使用一个低速率信道当用户容量需要 增加时，码速率就要降低。在时分方式下，在某一时刻所有资源可被分配给一个 或少数的几个用户这样一个用户可在一个非常高的码率下传输在w c d m a r e l e a s e 9 9 中，最小的时间分辨率是1 0 m s 帧当在时分方式下用户数增加时，每 个用户都要等待较长的时间来传输 1 1 43 g 系统的增强技术 在传统的移动通信系统中，上行链路和下行链路的频带是事先规定的而且容 量大致相当，这是因为过去的移动通信系统承担的大多为话音业务，上下行链路 的业务量大致是相等的而在第三代移动通信系统中，由于业务种类的扩展，上 下行链路的业务量将会有很大的差异，下行链路的业务量将普遍大于上行链路 的业务量要提高3 g 系统的下行数据业务能力，不仅需要使用更灵活的空中接 口，而且还要使用合理的无线资源管理方案，才能使网络的下行业务能力得到有 效改善为达到这一目的，3 g p p 和3 g p p 2 在空中接口的改进方面提出使用自 适应调制编码( a m c ) 、混合自动重传( h a r q ) 、多输入输出( m i m o ) 等几种技 6 第一章绪论 术，在无线资源管理方面提出使用快速小区选择( f c s ) 方案这几种技术在有些 文献中被称为3 5 g 技术，在w c d m a 中被称为h s d p a 技术，在c d m a 2 0 0 0 中被 称为 x e v d v 技术由摩托罗拉，诺基亚等公司提出的w c d m a 高速下行链路 分组接入( h s d p a ) 技术针对不同用户高速数据业务的要求，采用了链路自适应 技术，可实现高达1 0 8 m b p s 的下行高速数据传输，得到了普遍重视采用h s d p a 技术，能提供完整的i m t ，2 0 0 0 所要求的多媒体业务，而且还支持第二代b t s 的 接入，具有适合多种业务速率，动态分配带宽和易于同有线宽带综合业务数字网 接口的优点可以看出，h s d p a 可以更好的满足第三代移动用户对多媒体业务 的需求。 高速下行链路分组接入( h s d p a ) 系统是在w c d m ar e l e a s e 9 9 系统基础上增 加h s d s c h 传输信道，采用自适应调制编码( a m c ) 、混合自动请求重传( h a r q ) 、 快速小区选择( f c s ) 以及多输入多输出天线处理( m i m o ) 等技术而形成的一个 w c d m a 增强型系统( 详述参见文献【1 ) h s d p a 技术的最主要特点是充分利用 无线信道的时变信息，来控制下行链路信息的传输方式、传输速率和传输路径， 以达到克服快衰落影响和提高信道利用率的目标 h s d p a 技术应用于下行共享信道，而共享信道具有动态分配信道的特点， 即所有的用户以时分方式和码分方式共享无线信道资源，那么分组调度在这里 就具有极其重要的作用分组调度功能在每一个传输时隙选择一个或几个用户 的分组数据，决定分配信道码的个数，扩展因子以及发射功率等参数选择一个 好的分组调度算法，可以获得高吞吐量性能和高信道利用率，还可以控制用户公 平性，另外对需要服务速率保障的业务流，也可以通过分组调度来实现对业务流 速率的控制。在r e l e a s e 9 9 的w c d m a 系统中，共享信道采用固定的调制编码方 式，使用快速功率控制技术克服快衰落，因此可以简单的控制每一帧的信道速率 都相同，而采用h s d p a 技术后，信道速率将随无线信道的衰落而随机变化，那么 控制用户公平性和服务速率就变得更复杂一些，与此同时，也带来了提高无线信 道利用率的途径，这些都与分组调度功能有着密切的关系本文旨在对h s d p a 系统下共享信道的分组调度方法进行一些研究与探讨 1 1 5 无线系统分组调度概述 在传统的有线传输系统中，从交换的角度来说，主要包括两种网络，一种是 电路交换网，一种是分组交换网分组调度算法正是应分组交换网的需要而逐步 发展起来的一个研究领域分组调度算法也称为队列调度算法，它运行在网络节 1 】研究背景 7 塑坠兰一 o ： = o d a t a 图1 2 ：调度模型 点中发生冲突需要排队调度等待之处，按照一定的服务规则对交换节点的不同输 入业务流分别进行调度和服务，使所有的输入业务流能按预定的方式共享交换节 点的输出链路带宽 在无线分组网络中，分组调度的作用和有线网络中相同，但由于无线信道不 同于有线信道的一些性质，也使得无线分组调度具有一些不同于有线分组调度的 特点在有线网络中，信道质量稳定，链路总带宽基本保持不变，而在无线网络 中，无线信道是时变信道，信道质量和链路带宽随用户位置、速率、地理状况等 因素的不同而随机变化，在这种情况下，无线分组出错的可能性增大，甚至在某 段时间内无法传输，这就需要对有线网络中的调度算法作出一些改进才可适用于 无线网络；另外，在有线网络中，分组调度器所分配的资源比较单一，通常是分 配时隙资源，而在无线网络中，尤其是3 g 网络中，分组调度器所需考虑的分配 资源可能是多方面的，如频率，时隙，信道码以及发送功率等图1 2 描述了无 线分组调度的基本模型：不同输入业务流随机到达网络节点，由队列管理实体按 照一定的排队规则分别进入相应队列等待调度，调度器可以获得分组传输结果和 信道质量等环境信息，网络管理者可以配置调度器的目标参数，调度器根据当前 系统的各种信息j 将频率、时隙、信道码和功率等无线信道资源分配给系统中的 分组队列。调度算法就是调度器根据当前的队列状况、环境信息和目标参数，将 各种信道资源分配给数据队列所遵循的一定规则 许多研究者根据无线网络的特点，对有线网络调度算法进行改进，提出了 一些无线分组调度算法来保障用户公平性 s o n g w ul u 等在文献f 8 1 中提出的 8 第一章绪论 w f s ( w i r e l e s sf a i rs e r v i c e ) 算法，t s e u g e n en g 等在文献 9 】中提出的c i f q ( c h a n n e l - e o n d i t i o ni n d e p e n d e n tp a c k e tf a i rq u e u e i n g ) 算法，p r a m a n a t h a n 在文献 1 0 中提出的s b f a ( s e r v e rb a s e df a i r n e s sa p p r o a c h ) 算法，都是在g p s ( g e n e r a l i z e d p r o c e s s o rs h a r i n g ) 等有线网络调度算法基础上，考虑位置相关性信道错误特性， 添加速率补偿机制来实现的而有线网络调度算法的设计目标通常只是提供用户 公平性和业务的端到端时延保障，因此这些改进后的无线调度算法也是属于公平 性调度算法，即只以用户公平性和业务时延保障为目标，不考虑如何提高无线信 道的吞吐量。而这一点对于信道资源相对不足的无线网络来说，是一个明显的缺 点，也是许多实际无线网络系统设计时需要考虑的问题本文所研究与探讨的调 度方法，考虑的性能目标不局限于用户公平性和业务端到端时延保障，还要考虑 无线系统吞吐量的改善。 提到了调度算法的公平性和时延保障，就需要了解业务的统计特性和服务质 量。因为用户公平性实质上是指业务公平性，简单的解释就是需要带宽大的业务 分配较大的带宽，需要带宽小的业务分配较小的带宽，它们之间互不侵犯；而时 延保障也是针对不问业务的不同时延需求来提供的所以设计分组调度算法之 前，必须先确定网络所提供服务的业务类型及其所需的服务质量描述一个业务 的服务质量，最常用的两个指标是服务速率和端到端延时。按照端到端延时要求 的不同，可以将业务分为实时性业务和非实时性业务，例如数字电话就是典型的 实时性业务，它需要保障业务的端到端延时，主观测量表明这种延时小于4 0 0 m s 时个人感观才可接受【6 4 j ，而f t p 文件传输则是典型的非实时性业务，不需要 保障端到端延时另外还可以根据服务速率将业务划分为不同服务等级，例如 3 2 k b p s 类型，6 4 k b p s 类型，1 2 8 k b p s 类型以及3 8 4 k b p s 类型等等 一种调度算法设计之前，应该有一个优化的目标，设计好后，应该有一个评 价其优劣的标准，这就是调度算法的性能指标公平性调度算法的性能指标主要 涉及到时延性能，公平性和复杂性三个方面在无线网络中，还可以考虑吞吐量 指标。在不同的文献里，所采用的性能指标具体形式有所不同，但其所代表的意 义基本一致 1 2 本文的内容安排 本文主要研究h s d p a 系统中对共享信道的分组调度方法，包括不区分业务 服务等级的单业务类型分组调度，如最大载干比调度和轮循调度等；以及区分业 5 1 2 本文的内容安排 9 务服务等级的多业务类型分组调度，如速率控制调度内容安排如下： 第二章首先根据无线通信系统的工作特点，提出了一种无线调度系统的数学 模型，并给出了一套对调度系统进行数学建模和分析的方法，然后描述了h s d p a 系统的主要技术背景以及h s d p a 系统中高速共享信道分组调度的特点，最后简 要介绍了本文的算法研究中所采用的系统仿真平台 第三章介绍了参考文献中提出的几类适合h s d p a 系统的无线分组调度算 法，包括轮循调度、最大载干比调度和比例公平性调度，并通过仿真比较了各