（通信与信息系统专业论文）hsdpa流媒体调度算法研究.pdf

摘要 高速下行分组接入技术( h s d p a ) 是r 5 规范中包含的w c d m a 的关键新 特征，它通过使用自适应调制编码、混合自动重传请求、快速调度等关键技术， 来提高下行数据的传输速率。由于流媒体业务的发展和h s d 队的下行高速传 输速率特性，期望h s d p a 也能承载流媒体业务，而h s d p a 承载流媒体业务必 须使用适合流媒体的分组调度算法，本文研究的重点就是研究开发这种分组调 度算法。 本文首先简要介绍了h s d 队技术及其分组调度的基本原理，分析了流媒 体业务的特性及其调度算法的基本要求，然后在研究了两种基于q o s 的调度算 法的基础上。提出了两种基于t o k b u c k c t 的流媒体调度算法。最后结合m a t l a b 仿真对提出的h s d p a 流媒体调度算法的性能进行了全面地分析与比较。 关键词：h s d p a 流媒体分组调度算法q o s a b s t r a c t h i 曲s p dd 0 1 l i n l 【p a c k e ta c c 嚣s 饵s d p a ) i s1 h e 嚣s d a l 砝曲r eo f w c d m a s p e c i f i c a l i o n si n c l u d e di nr d e a 5 ，w h i c hi s 唧1 0 y e dt 0i n c 旭器ed o 砌i n k p a c k e td a t at h r o u g h p u tb ym e a 璐o fm 蛆yk e y 由e c h n i q u 嚣，鲫c h 硒a d a p t i v em o d u l a t i 龃dc 0 曲g ，h 啦疵da u t o m a n c 托p tr e q u e s ta n d 白s ts c h 酣u l i n g d u et 0t h e d 吖e l o p m 舶to f 蜘她s e 九r i c c 强dt h eh i 罟hb i tr a t eo fh s d p 凡h s d p ai sb e l i e v c d t ob ea b l et o 如p p o ns 口c 锄1 i n gs e i c e s 1 ti sn c c 嚣s a r yt 0d e v d 叩ap a c k e ts c h c d u l i n g a l g o r i t h m 砌c hi s 飘血出l et os 骶趾i n gs e i c c 册p p o n e db yh s d p a ，州c hi st h e m a i n p u r p _ 0 鹳o f t h i st h e s i s f i r s n y ，t h et h e s i si n 订o d u c e st h e 研n c i p l eo fh s d p at e c h n o l o g ya n di t sp a c k e t s c h e d l l l i n ga 1 9 0 酊t h 】咀，如d 卸a l y z 嚣t h ec h m 曲e f i s t i co fs 廿黜i n gs e r v i c e 鸽w e l l 鹊血e r e q u i r c m c n t so fs 打锄i n gs c h m l i n ga l g o r i t h m s t h e n ，a r 盯s t u d y i n g 伯，op a c k e t s c h e d u l i n ga l g 晌t b m sb 髂e d 佃( 扣s ，t h et h e s i sp r o p o s 嚣t w ds 咖i gs c h c d u h n g a l g o r i t h l nb 嬲c d t o k 吼b u c k c t f i n a l l y ，s o m et h e o r c t i c a l 锄a l y s i s 龃d 咖p a r i s o n f b rt h 髓ea l g o r i t l l i n sa 他p 刊疏c d 、】l r i t hs o m e 锄p m 盯s i m u l a l i 加b 勰e d m a t l 曲 k e ) 哪o r d s ：s d p a& n a m i n gs e r v i c e p a c k e ts c h e d 山嵋a i g o r i 山m q o s 西安电子科技大学 学位论文创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果：也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：丞坐【鳘 日期五丛：2 ：1 2 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名：迸 导师签名： 日期独盖：至：! 日期星丝! 至! 型 第一章绪论 第一章绪论 1 1 移动通信技术发展 近年来移动通信技术飞速发展，已经历了三个主要发展阶段【”，如图1 1 。每 一代的发展都是技术的突破和观念的创新，其中无线接入技术经历了从模拟到数 字、从电路交换到分组交换的发展历程。第一代移动通信系统起源于2 0 世纪8 0 年代，采用模拟传输技术，以美国的a m p s 、英国的t a c s 和日本的n t t 为代表， 以语音业务为主。 第二代移动通信系统起源于9 0 年代初期，主要采用数字传输技术，以g s m 、 c d m ao n e ( 又叫i s 9 5 ) 和p d c 为代表，以语音和低速率的数据业务为主。其 后，又出现了基于第二代通信系统的2 5 代移动通信系统，包括基于g s m 的g p r s 和e d g e ，基于l s 9 5 的c d m a 2 0 0 0 1 x 等。2 5 代系统增强了分组数据业务的传 输能力，允许高达3 8 4 k b i 以的传输速率，可以提供多媒体业务。 第三代移动通信系统是按照国际电信联盟提出的m 【t 2 0 0 0 标准而设计的新一 代移动通信系统，主要包括w c d m a 、t d s c d m a 和c d m a 2 0 0 0 三种标准制式。 与第一代和第二代移动通信系统相比，第三代移动通信系统采用了c d m a 技术， 基于全口网络，具有支持更多的用户数量、支持更丰富的多媒体高速数据业务等 特点。 图1 1 移动通信技术发展 w c d m a 作为3 g 标准之一于2 0 世纪9 0 年代初在欧共体的研究项目以及欧洲 的一些大的无线通信公司开始了相关的研究工作。1 9 9 8 年1 月，欧洲标准化组织 e t s i 决定把w c d m a 作为第三代空中接口。在1 9 9 9 年底完成了第一套完整的 w c d m a 技术规范。r 9 9 版本的w c d m a 可以提供最高2 m b 彬s 的传输速率，支 持高速数据交换，支持不同服务质量要求的业务，充分满足了m r r - 2 0 0 0 关于第三 代移动通信的技术要求。 其后，3 g p p 发布了w c d m ar 4 版本，w c d m ar 4 与r 9 9 相比无线接入网 2h s d l ，a 流媒体调度算法研究 的网络结构没有改变，其区别主要在于引入了t d s c d m a 技术，同时对一些接口 协议的特性和功能进行了增强。 由于新的无线通信业务的出现，需要系统能够提供更高的传输速率和更低的 网络延迟。为了满足这些需要，w c d m a 需要增加频谱效率和用户数据速率，特 别是在下行方向，因此，3 g p p 发布了w c d m a r 5 版本，其中，高速下行分组接 入技术( h s d p ：a 技术) 包含在w c d m ar 5 规范中。h s d p a 在w c d m ar 9 9 基 础上去除了一些旧的技术，采用了许多关键新技术，并且引入三种新的物理信道， 使得h s d p a 在5 m h z 带宽基础上下行峰值数据理论速率可以达到1 4 4 m b p s ，并且 具有更短的服务反应时间。 1 2 无线通信业务发展 第一代和第二代移动通信的核心业务是窄带话音业务，2 5 代移动通信为用户 提供了许多前所未有的新数据业务，如m m s 、w a p 浏览、手机互动游戏等等 2 j 。 据统计，截至2 0 0 7 年6 月底，中国的移动分组数据用户已达到1 2 8 亿户。可以说， 2 5 代移动通信应用开启了无线通信业务新时代的大门。 近年来，第三代移动通信系统实现了快速发展，据统计，2 0 0 7 年上半年全球 3 g 用户数已达到5 亿。第三代移动通信的发展也推动了无线通信业务新的应用。 3 g 网络可实现高速无线数据连接，基于这一平台，运营商可为用户提供更强大的 多媒体业务，在日本、韩国等3 g 系统商用较早的国家，无线电视、无线广播、视 频通话、高速下载、互动娱乐、地图导航等应用已经进入千家万户。无线通信发 展如下图1 2 。 图1 2 无线通信业务的发展 过去2 0 年，因特网成了世界上最大的信息交换网络，信息网络平台的网络规 模、网络能力和网络质量得到了快速提升。由于信息网络具有极强的信息承载和 业务承载能力，为各种无线通信业务的创新提供了平台和动力源泉。 最新的报告显示，全球移动市场的u 冲u 正在下滑，包括一些欧洲的运营商。 第一章绪论 3 因此，为了保持其利润增长，运营商会不断引入新的数据多媒体业务。 对消费者来说，在信息时代，他们希望运营商不仅仅提供语音业务，他们还 需要丰富多彩的数据业务，比如，商业用户希望能够随时随地上网浏览商业信息， 年轻时尚用户希望可以玩互动游戏等等。 在这些创新的无线通信业务中，流媒体业务是其中的重要的一方面。流媒体 是传递数据的一种技术，它使得数据能够以稳定连续的流续方式来处理。随着移 动通信的发展，流续技术变得越来越重要，因为大多数用户没办法快速下载很大 的多媒体文件，并且移动终端的存储器或者内容知识版权的保护也限制了这种文 件的下载。如果采用流续技术的话，客户端通过浏览器或者插件在整个文件下载 过程中就可以显示数据。 1 3 无线分组调度算法概述 分组调度算法是应分组交换网的需要而逐步发展起来的一个研究领域。分组 调度算法也称为队列调度算法，它运行在网络节点中网络节点中发生冲突需要排 队调度等待之处，按照一定的服务规则对交换节点的不同输入数据业务流分别进 行调度和服务，使所有输入的数据业务流能按预定的方式共享交换节点的输出链 路带宽。在无线网络中，分组调度的基本模型如下图1 3 。 图1 3 无线分组调度基本模型 如图所示，不同输入的分组数据到达网络节点，分组数据按照一定的规则( 比 如不同的用户、不同的q o s 要求等) 排成不同的队列( 数据流) 等待调度。位于 网络节点中的调度器可以获得信道质量信息、分组数据信息以及频率、码道、功 率资源等信息，调度器根据各种信息，选择队列中的数据分配其功率、码道等发 送出去。调度算法就是调度器根据当前的队列状况、环境信息和目标参数，将各 4h s d p a 流媒体调度算法研究 种信道资源分配给数据队列所遵循的一定规则。 分组调度算法最初主要应用在有线网络中，由于无线网络的发展，分组调度 算法逐步引入到无线网络中。因此，早期的无线分组调度算法基本上都是以有线 网络分组调度算法为基础，再根据无线网络的特性修改而来，具有代表性的算法 包括：c s d p s ( c 五脚e 】s 眦d c p 印d 印t p a c k e ts c h 。d u l i n g ) 、州f q ( i d l 切e d w i r e l e s s f a i rq u 删i n g ) 、c 正- q ( c h 锄e l - c d m c p d e n tf a i rq u 即i n g ) 等。但是，上 述算法均没有考虑具体的信道条件，认为链路只存在两个状态( 有差错和无差错) ， 此外，上述所有分组调度算法都是针对单一服务系统进行的研究，比如) m a 系 统，也就是说在任何一个调度时刻只能服务一个分组。然而在c d m a 网络中，基 站可以同时调度多个分组。因此，以上无线分组调度算法并不适合c d m a 蜂窝通 信系统。 近年来人们开始对c d m a 系统分组调度问题展开了深入的研究，提出了许多 调度算法，包括v a r u 提出的h o l p r o ( h e a do f 【血ep s 饥d o 咿b a b i l i 奶算法、 j a l a l i 针对q l l a l c o 蛐公司的c d m a ，r 系统提出的基于s 小限( s i 皿a lt 0 i n t 吲f 打p l 璐n o i s er a t i o ) 和吞吐量测量的调度算法、q l a l c o 姗公司提出的基于 时分复用方式的p f ( p r o p 0 i t i o n a lf a i r ) 等等。 对于h s d p a 技术，人们基于对c d m a 系统分组调度算法的研究，提出了轮 循调度算法、最大载干比调度算法、比例公平调度算法以及快速比例公平调度算 法等等。但是这些算法都是针对非实时业务，不能支持具有时延约束的实时业务。 为了使h s d p a 支持具有时延约束的实时业务，b d l 实验室a n d r e 哪等人提出 了m 啪f ( m o d i f i c dl a 唱e s tw a i td e l a yf i r s t ) 算法，e r i c s n 公司提出了e x p r 脚 算法，并证明了他们具有吞吐量最优性质。这两种算法都考虑用户的信道条件的 快衰落变化的影响，并力图最大化多用户分集增益。但是，这两种调度算法都只 是考虑了实时业务特性的某一方面，比如时延特性或者速率要求特性等，限制了 h s d p a 承载实时业务时的系统容量。 1 4 本文主要内容及各章安排 h s d p a 信道的共享、分组特性有利于承载高速非实时业务。由于实时业务的 发展特别是流媒体业务，需要h s d p a 也能承载流媒体业务。以前的文献大部分是 研究非实时业务的h s d p a 系统性能和网络容量，也有一部分文献研究实时业务的 h s d p a 系统性能和网络容量，但是这些文献基本都是研究泛指的实时业务，很少 有针对流媒体方面的研究。 流媒体相对于普通的实时业务要求具有更小的时延抖动、严格的保证比特速 率、更低的误码率等特性，以保证终端用户的服务质量，因此，本文研究基于流 第一章绪论5 媒体业务的h s d p a 系统性能和网络容量。 本文的研究重点放在h s d p a 承载流媒体业务需要的分组调度算法上，因为分 组调度器是h s d p a 设计的中心实体，分组调度算法是分组调度器的核心。分组 调度算法掌管着可用无线资源在不同用户之间的分配，对h s dp ：a 系统性能有着直 接影响。同时，它还决定着终端用户的性能，具体地说就是不同用户的服务质量。 设计一种合适的h s d p a 流媒体分组调度算法既可以保证流媒体业务在h s d p a 上 的应用又可以提高h s d p a 承载流媒体业务时的系统性能和网络容量。 本文共分为六章，结构安排如下： 第二章主要介绍h s d p a 技术，首先介绍与分组调度有关的h s d p a 的信道、 关键技术等，然后利用效用函数的概念阐述h s d p a 分组调度原理，并由此引出 h s d p a 的三种基本的调度算法。 第三章介绍流媒体业务，包括流媒体业务的q o s 要求以及流媒体业务特性、 流媒体网络传输方式，在此基础上分析h s dp ! a 承载流媒体业务对h s d 队系统提 出的挑战。 第四章是本文的重点，首先根据流媒体业务特性，分析了h s d p a 流媒体调度 算法的基本要求，然后研究了h s d p a 三种基本调度算法用于流媒体业务的情况， 介绍了两种基于q o s 的分组调度算法原理并且分析了其应用于流媒体业务的优缺 点，最后，提出了两种基于t o k 衄b u c k c t 的h s d p ：a 流媒体调度算法。 第五章利用m a n 曲对h s d p a 系统进行建模，在构建的仿真平台上对h s d p a 流媒体调度算法做出仿真，给出仿真结果，并对结果进行了比较分析。 第六章给出了整篇文章的总结，提出了本课题有待于进一步深入研究的问题， 并展望该领域的研究发展趋势。 第二章h s d p ：a 技术 第二章h s d p a 技术 2 1 概述 为了满足高速多媒体业务增长的需要，3 g p p 在w c d m a 系统r 5 协议中引 入高速下行分组接入技术，即h s d p a 。h s d p a 与w c d m a r 9 9 相比，下行性能 方面有显著的提高，其下行理论峰值数据速率可以达到1 4 4 m b p s 。 h s d p a 下行速率的提高得益于h s d p a 采用了大量的关键技术，引入了三种 新的物理信道。采用的关键新技术包括：2 m s 短帧技术、混合自动重传请求 ( h a r q ) 、自适应调制编码( m c ) 、多码传输技术、1 6 q 御订高阶调制、快速 分组调度技术等，如图2 1 所示。引入的三种新的物理信道包括：高速下行链路 共享信道( h s _ d s c h ) 、高速共享控制信道( h s s c c h ) 和上行链路高速专用物 理控制信道( h s d p c c h ) 。 图2 1h s d i a 的关键技术 本章不是关于h s d p a 技术和性能的完全的描述，它只是为了充分理解 h s d p a 分组调度器以及分组调度算法的分析、设计而提供的一个h s d p a 整体的 综述。因此，本章只介绍与分组调度有关的h s d p a 协议架构、新引入的物理信 道和使用的关键算法，然后利用效用函数的概念解释h s d p a 分组调度算法原理， 并引出h s d p a 的三种基本调度算法。 2 2h s d p a 的协议结构 h s d p a 是w c d m ar 9 9 技术基础上的改进和扩充，其目的是提高逻辑下行 共享信道的吞吐量，应该尽最大可能保持其r 9 9 协议结构，因此h s d p a 系统中 8 h s d p a 流媒体调度算法研究 m a c 层以上的协议应该保持不变。在n o d eb 中，h s d p ：a 系统新增加了一个控 制h s d p a 下行共享信道m a c 层的协议栈，即m a c h s 子层，如图2 2 所示脚。 d t c h d t c h u u n 州e b i u b c r n c 培r n c 图2 2 h s d p a 协议架构 从图2 2 中可以看出：协议模型与r 9 9 相比，最大的不同是在n o d e b 和u e 分别引入了m a c h s 子层。n o d e b 的m a c 如实体通过u u 口将m a c 血p d u 传 递给u e 的对等实体m a c h s 。r n c 的m a c - d 实体通过h s d s c hf p 协议将 m a c - d p d u 传递给n o d e b 的m a c - h s 实体。 u t i u n 侧m a c h s 架构如图2 3 所示。引入的u t r a n 侧m a c h s 子层主要 负责流量控制、调度优先级处理、h a r q 处理等，调度优先级处理部分就是通 常说的h s d 只a 调度器，我们要设计的调度算法就应用在此。 图2 3i r n l a n 侧m a c h s 架构1 0 1 在n o d eb 中引入m a c h s 子层的主要原因包括：1 ) 使得调度器可以以一个 无线帧长度为调度周期进行多用户的快速调度，并且在调度过程中可以利用每个 第二章h s d p a 技术 9 服务u e 的即时信道质量信息；2 ) 减少重传时延，提升用户的业务感受；3 ) 提 高伽c 技术链路自适应性能：该技术根据信道质量来调整调制和编码方式，其 性能对信道质量上报的时延非常敏感，时延越大链路自适应性能越差。 2 - 3h s d p a 新增加的物理信道 2 3 1 高速下行链路共享信道 高速下行链路共享信道h s d s c h 在下行链路方向承接用户数据，在物理层， h s d s c h 映射到h s p d s c h 。其扩频因子固定为1 6 ，调制方式可以是q p s k 或 1 6 q m ，信道编码采用l ，3t i b o 码，包含两级速率匹配闭。 h s p d s c h 信道与r 9 9 已有的d p c h 信道相比有很多特点： 1 ) 自适应调制编码( d c ) ：h s p d s c h 放弃了快速功率控制的链路自适应 策略，而是采用自适应的调制编码技术实现链路自适应； 2 ) 2 m s 短帧：h s p d s c h 采用2 m st t i ，与r 9 9 的l o m s 、2 0 m s 、4 0 m s 、8 0 m s t t i 相比，可减小无线链路自适应时延，提高调度的时间粒度，更好地跟踪时变 的无线环境； 3 ) 1 6 q a m 高阶调制：h s d p a 除了支持q p s k 外，还引入了1 6 q a m 调制， 而r 9 9 最高只支持q p s k ，与q p s k 相比，1 6 q 频谱利用率提高一倍； 4 ) 多码传输：h s d s c h 信道支持多码传输和用户之间的时分码道复用， h s p d s c h 可用的最大码道数为1 5 个； 5 ) 混合自动请求重传( h a r q ) ：混合自动请求重传要求速率匹配时根据 r v ( r e d 衄d a n c y v j 巧i o n ) 参数进行打孔或重复，使重传时采用不同的传输格式， 从而增加软比特合并之后的译码性能； 6 ) 动态资源共享：h s p d s c h 可以在2 m s 内进行动态资源共享，包括共享 码道资源和功率资源。 h s - d s c h 信道结构如图2 4 所示【4 】。 i晰 ln m j b i t 8 1 。2 5 6 蛐s ， 1 6 0 7 s l o t 柏s l o t i ls l o t 栉2 图2 4h s p d s c h 的信道结构 1 0h s d p a 流媒体调度算法研究 2 3 2 高速共享控制信道 高速共享控制信道h s s c c h 信道是下行的物理信道，承载h s d s c h 信道译 码所需的物理层关键信令阁，每个h s d s c h 信道都会伴随一个h s s c c h 信道， 只有正确解码h s s c c h 信道，才能解码h s s c c h 信道。其信道结构如图2 5 所 示【4 】。h s s c c h 信道使用的扩频因子为1 2 8 ，调制方式为q p s k ，信道编码为卷 积码。 。2 5 6 娜，4 0 7 s l o t 群0s i 硎ls l o t 撑2 图2 5h s s c c h 的信道结构 h s s c c h 信道承载的信令包含两部分，第一部分( 第一个时隙) 包括信道化 码、调制方式，u e 将在第一个时隙内解出这些信息，用于在第二个时隙的开始 时刻启动h s p d s c h 解扰解扩过程。避免u e 侧码片级的数据缓存；第二部分( 剩 余的两个时隙) 包括传输块大小指示、m 蛾q 进程号、r v 参数、新数据指示。 第二部分信息将会在第二个时隙结束后的一段时间内解出来，在没解出之前，要 缓存h s p d s c h 解码后的符号级数据，等第二部分信息解出之后进行h s d s c h 信道的解速率匹配、软比特合并、t h r b o 译码等操作。因此，h s s c c h 与h s d s c h 要有一定的定时关系，如下图2 6 。 3 t _ 嘲由岫 j 3 k 榴0 邮 lh 引捌b 缸 i 钿( 2 x k5 啪曲啼) 图2 6h s s c c h 与h s d s c h 的定时关系 根据码复用所支持的最大用户数，u t r a n 分配相应数目的多个h s s c c h 。 每个终端最多可以监控4 条h s s c c h 信道。一般在一个t t i 内调度的用户数不 超过4 个( 以减少h s s c c h 对功率和码道资源的消耗) ，h s s c c h 的数目可以 第二章h s d p a 技术 根据h s d p a 业务的功率资源和码道资源进行合理配置。 2 3 3 上行链路高速专用物理控制信道 上行链路高速专用控制信道h s d p c c h 信道是上行的物理信道，它的引入是 为了承载必要的反馈信息，包括h s - p d s c h 信道译码信息( a c 科n a c k ) 和信 道质量指示信息( c q i ) 。该信道的扩频因子为2 5 6 ，调制方式为b p s k 嘲。 h s d p c c h 信道结构如图2 7 所示【4 】。 t m = 2 5 6 0c h i p s2 1 k = 5 1 2 0c h i p s h a r q a c kc b i 1 咖劬? 7 s u b 丘a m 加s u b 丘a m e 螨s u b 丘a m e 自珥 o n c r a d i o 缸mt f = 1 0 图2 7h s - d p c c h 的信道结构 如图2 7 所示，h s d p c c h 信道第一部分为a c k n a c k 域，代表h s p d s c h 的译码结果。如果译出的是a c k ，则说明下行h s s c c h 译码正确，h s p d s c h 译码正确；如果译出的是n a c k ，则说明下行h s s c c h 译码正确，但h s p d s c h 译码错误：如果译出的是d 1 x ，则说明下行h s s c c h 译码错误，h s p d s c h 没 有解调。第二部分为c q i 域，代表u e 的信道质量。 h s - d p c c h 信道对分组调度非常重要，a c n a c k 用来判断是否需要重传， 而c o i 用来选择适合信道质量的传输块大小，也用来计算h s s c c h 需要的功率。 更加重要的是c q i 通常会用在调度算法中表示用户的瞬时速率。 2 4h s d p a 的关键技术 2 4 1 自适应调制编码技术 舢订c 技术的原理是根据信道情况的变化而改变调制方式、编码方式、传输 块大小的模式。在使用j 州c 技术的系统里，处于有利位置的用户，例如接近基 站的用户，其信道质量比较好，可使用高阶调制和高码率( 例如1 6 q w 、较大 的数据块) ，而处于不利位置的用户，例如远离基站的用户，其信道质量比较差， 1 2 h s d p a 流媒体调度算法研究 使用的调制方式和码率则要小一些( 例如q p s k 、较小的数据块) 。信道质量的好坏 用h s d p c c h 信道反馈上来的c q i 表示。 a m c 技术取代r 9 9 快速功率控制技术，主要充分利用信道情况，提高处于 有利位置用户的速率，从而提高整个小区的吞吐量。 h s d p a 中a m c 的过程：移动台周期性的根据信道质量( 导频信道的信噪比) 和由测量功率偏移值( m p o ) 假定的h s d s c h 功率确定在c q i 上报之前的t t i 内满足h s - d s c h 误块率不超过1 0 最大的c q i 值，然后通过h s d p c c h 信道 上报给n o d eb ，n o d eb 根据某种分组调度算法确定用户的调度优先级选择被调 度的用户，然后根据接收到的该用户的c o i 、h s d s c h 可用功率、h s d s c h 可 用码道、u e 的数据量来确定为该u e 传输的传输块的大小、调制方式、h s - d s c h 码道数、h s d s c h 发射功率等参数，然后将这些信息传给符号级处理器进行编 码与复用的操作，然后通过射频调制发射出去。 2 4 2 混合自动重传请求 h a r q ( h y b 谢a m o m a t i cr e p e a tr c q u c s t ) 是一种前向纠错f e c 和重传相结 合的技术。它可以根据链路的状况快速地调整信道的传输速率并实现f e c 与重传 的结合。前向纠错编码( f e c ) 提高了传输的可靠性，但当信道情况较好时，降 低了吞吐量。a r q 在误码率不是很高的情况下可以得到理想的吞吐量，但会引入 时延。考虑将f e c 和灿旧相结合就形成了m 咀q 。在发送的每个数据包中含有 纠错和检错的校验比特。如果接收包中的出错比特数目在纠错能力之内，则错误 被自行纠正，当差错严重，已超出f e c 的纠错能力时，则让发端重发。 如果在一个t t i 时段内的数据解码错误，那么重传操作会在后面几个t t i 时 段内执行。一旦数据被重传，u e 将对当前版本的数据和当前重传的数据进行组 合，这极大地提高了重传成功的几率。直到数据成功解码或达到了预先定义的最 大尝试次数，重传操作才会结束。由于h a r o 机制是在n o d eb 中执行的，因此， 重传请求操作可以非常迅速。 h s d p a 技术的 l u 的方案采用多通道s a w 协议，最大并发通道个数为8 。 s a w 停等协议即是在发端发出一个分组后等待收端的a c k 或n a c k ，以确定重 发分组或新发分组。因此，发端在任何时刻都不能多于一个的出错分组。然而单 通道的s a w 导致了信道在时域上利用不充分，发射机一直在等待响应而没有发 射数据块。为了解决单通道s a w 的这一问题，提出了多通道 l a r q 方案，连续 传输流在多个独立的时分子信道上，每个独立的时分子信道执行s a w 重传协议。 多信道结构保证连续传输，只要确认信息往返时间足够短，那么需要足够少的并 行s a w 通道就可以使数据传输不会因为等待确认信息而被拖延。 第二章h s d p a 技术 1 3 h a r q 有两种运行方式。一种是在重传时，与初次发射时相同，这种方式被 称之为软合并( c c ，c h 鹊ec o m b i n e ) 。另一种就是重传时的数据与前次发射有所 不同( 如仅包含校验比特) ，这种方式被称之为增量冗余( 瓜，h c 舢t a l m ：d 如d 肌c y ) 。 在h s d p a 中物理层地峨q 发送功能通过两级速率匹配来完成。如图2 8 。 第一级速率匹配在编码后的数据与虚拟缓冲区之间匹配，如果编码后的比特小于 等于虚拟缓冲区，则第一级速率匹配透传数据比特；如果编码后的比特大于虚拟 缓冲区，则透传系统比特，打孔校验比特；第二次速率匹配在第一次速率匹配之 后的数据与物理信道比特之间匹配，系统比特和校验比特都会出现打孔或重复的 操作。第二次速率匹配受冗余版本参数r v 控制，r v 参数决定了重传时使用c c 或者瓜中的哪种合并方式。 第一次速率匹配虚拟缓冲区第二攻速率匹配 系统比特 1 打砌重复l 囊 窜 驵 b 面 -比特 授验比特1 - l打孔l i 打砌重复卜+比特 分离 收集 盘验比特2 1打孔 - i 打砌重复卜j + 2 4 3 快速调度技术 图2 8h a i 发送功能模块嗍 h s d p a 技术为了能更好地适应信道的快速变化，将分组调度功能单元放在 n o 如b 的m a c h s 子层中面不是r n c ，这样更加接近用户设备。同时，也将t t i 缩短到2 m s ( 3 个时隙) ，这使得在重传过程中对于终端和n o d eb 之间的往返时 延能够更小。 调度器控制着共享资源的分配，在很大程度上决定了整个系统的行为。调度 时应主要基于信道条件，同时考虑等待发射的数据量与可分配资源的关系、u e 的能力级和缓冲器状态以及业务优先级等情况，并发挥a m c 和h a r o 的能力。 h s d p ：a 的分组调度器的具体组成如下图2 9 所示。分组调度器的核心部分是优先 级计算部分，h s d p ：a 分组调度算法也就应用在这儿。分组调度器根据分组调度算 法来产生各个u e 的综合优先级。其余部分都是综合优先级的实际执行机构，执 行的结果发送到物理层。 1 4 h s d p a 流媒体调度算法研究 图2 9h s d p a 分组调度器组成 为便于后面的理解，我们简要介绍各个部分的作用如下： 优先级计算：主要根据调度算法计算各个u e 的综合优先级。 调度选择器：根据各个u e 的综合优先级选择具有最大优先级的n 个 u e 来进行调度和分配码资源。n 为码分复用的用户数。 h s s c c h 功控：根据后台配置的功率控制算法计算h s s c c h 的功率。 伴随d p c h 的功控算法需要输入d l d p c c h 的功率，基于c q i 的功控 算法需要输入c q i 。 多进程处理：根据受调度u e 的进程状况和重传是否优先的策略来选择 u e 的进程。 最小t t i 间隔要求：对于第1 、2 类u e ，要隔二个t t i 才能再为u e 调 度；对于第3 、4 、1 1 类u e ，要隔一个t t i 才能再为u e 调度。 t f r c 选择器：根据可用的功率资源、码道资源、c q i 、m p o 、缓冲区 数据量进行传输格式的选择，包含调制方式、码道数量、传输块大小、 h s s c c h 的配置信息、h s p d s c h 的功率信息等。 组装：根据t f r c 模块确定的传输块大小对m a c - dp d u 进行组装，组 装为m a c h sp d u 后发送给物理层。 码资源和功率资源池：存放可用的h s p d s c h 的功率和码道信息。 采用快速调度技术，同样的时间内可以为更多的用户服务，更加充分的利用 系统资源，更加发挥a m c 和h a r q 的能力，提高系统的吞吐量。 第二章h s d p a 技术 1 5 由于分组调度算法是本文的重点，因此，下面分两节单独分析h s d p a 调度 算法原理和h s d p a 的三种基本分组调度算法。 2 5h s d p a 分组调度的基本原理 分组调度要解决的问题是如何在一个共享信道上为多个渴望得到数据传输的 用户服务。来描述这个问题通常使用的公式于1 9 9 7 年k d l y 提出【l l 】。k c l l y 使用 了效用函数( u m 时f 吐c t i o n ) 的概念：u 如) ，代表第i 个用户的效用函数。代 表第i 个用户的平均吞吐率。效用函数表示的含义为：用户对于数据传输的满意 程度。那么最好的调度算法为在任意一个t t i 对于所有用户的效用函数之和能够 最大化，用数学公式描述如下： t 最大化 f ( i ) = u ( ) ( 2 - 1 ) 善) g 丑县 ( 4 _ 2 ) 在式( 4 - 2 ) 中，墨表示第i 个用户的速率，g 眠表示第i 个用户的保证比特速率， 这两个速率都是应用层的。式( 4 _ 2 ) 意味着应用层的速率要大于应用层的保证比 特速率，但是不一定要过大，过多超过保证比特速率是没有必要的。流媒体业务 的传输速率的保证也要在n o d eb 调度执行，因此，h s d p ：a 流媒体调度算法的另 一个基本要求就是保证用户的传输速率。 4 3h s d p a 基本调度算法应用于流媒体业务 这里所说的基本调度算法指的是2 6 节介绍的轮循调度算法、最大载干比调 度算法和比例公平调度算法。 大量的文献对上述三种调度算法进行了相关的研究，但是基本上都是基于非 实时业务的调度。在实际应用方面，对于非实时业务三种基本调度算法也得到了 广泛应用，特别是比例公平调度算法。那么，这三种基本调度算法能否用于流媒 体业务昵? 本节我们仅从理论方面对三种基本调度算法应用于实时流媒体业务进 行分析，具体的仿真我们放在第六章，放在第六章的原因是便于与本文提出的流 媒体调度算法的性能进行对比分析。 在分析调度算法的时候，通常会用到优先级的概念，调度器选择优先级最高 的u e 进行调度，因此，每一种调度算法都有自己的优先级计算公式，从式( 2 8 ) 、 ( 2 9 ) 我们可以分别得到最大载干比调度算法和比例公平调度算法的优先级计算 公式分别式( 4 _ 3 ) 和( 4 _ 4 ) ， 弓= d ，( ) ( 4 3 ) 弓= 嘭( 疗) 7 0 ( h ) ( “) 对于轮循调度算法，根据2 6 1 对轮循调度算法的推导和定义， 等待时间的r r 算法，则可以得到优先级计算公式为 已= t i 艘l 璐t s c h e 幽l e dj 假设采用基于u e ( 4 _ 5 ) 第四章h s d p a 流媒体调度算法 2 9 其中，砌吐珊岱曲砒删，表示第j 个用户最后被调度到当前t t i 的时间，只 为表示第j 个用户的优先级。 从式( 4 - 5 ) 看出，轮循调度算法仅仅考虑了u e 的调度时间问题，从式( 4 3 ) 看出最大载干比调度算法仅仅考虑了u e 的瞬时速率，也就是信道质量的好坏， 从式( 4 4 ) 看出比例公平调度算法考虑了u e 的瞬时速率和一定时间窗内的吞吐 量，因此，这三种基本调度算法均没有考虑u e 的q o s 参数。 从4 3 节对h s d 队流媒体调度算法的基本要求的分析看出，流媒体业务对传 输时延、比特速率等提出了严格要求，因此，假如三种基本调度算法应用于流媒 体业务，将无法完全保证流媒体业务对q o s 的要求。 4 4 两种基于q o s 的调度算法 从4 2 节知道，h s d p a 调度算法的基本要求就是要满足两个q o s 要求：传输 时延和保证比特速率，见式( 4 1 ) 和( 4 - 2 ) ，因此，理论上基于q o s 的h s d p a 调度算法可以用于流媒体业务。下面分别介绍两种文献上比较流行的基于q o s 的 分组调度算法( 其他基于q o s 的分组调度算法基本上都是由这两种算法衍生出来 的) ，并分析这两种算法是如何引入q o s 参数的。 4 4 1m l w d f 调度算法 m l w d f 调度算法是m o d i 丘e dh r g e s tw e i 班c dd e l a yf i r s t 调度算法的简称， 最早在【1 6 j 中提出，有很多文献对其研究 1 4 j f j7 】f 。该算法的主要思想是将分组数据 的时延和如何有效利用信道信息平衡考虑，其用户优先级的计算不仅和用户当前 的信道质量有关，还和分组数据队列时延有关。该算法的优先级计算公式如下： 删- _ l o g ( 4 ) 粤掣掣 ( “) 曰 ，l 】表示用户i ( i - 1 ，。，n ) 在n 时刻的调度优先级，这里假设每个用户只有 一个优先级队列，4 为式( 4 1 ) 中的q o s 参数，4 n 】为用户i 在时刻n 的瞬时 速率，【n 是根据式( 2 3 ) 滤波后的n 时刻的用户i 的吞吐量，d j 【万】为用户i 的队列头的等待调度时延，z 为用户i 分组数据的丢弃时间，z 是由高层配置的。 根据式( 4 1 1 ) 可以看出，式( 4 - 6 ) 中的4 【h 】【 相当于比例公平调度算 法，因此可以认为m l 、粕f 调度算法是在p f 调度算法基础上引入延时参数改进 而来。点，口【n 】和z 均是和时间有关的参数，在式( 拍) 中，4 越小，异【h 越 大，也就是说传输时延大于传输时延要求的概率越小，研h 】越大；队列头的等待 h s d p a 流媒体调度算法研究 调度时延d j 甩】越大，吼n 】也越大；丢弃时间z 越小，异【h 】也越大，从这方面来 看，m 啪f 调度算法可以保证一定的时延要求。为什么说可以保证“一定的时 延要求”呢? 从3 3 节流媒体业务的编码我们知道，流媒体业务有c b r 和v b r 两种编码格式，如果分组调度器队列中都是c b r 业务，可以保证所有用户的时延 要求，但是如果分组调度器队列中存在r 业务，那么m 啪f 调度算法就很 难保证所有用户的时延要求，原因是m l w d f 调度算法仅仅考虑了时延参数，也 没有考虑用户业务速率要求。业务速率不同，到达分组调度器的数据量不同，如 果按照m u v i ) f 调度算法，速率大的用户，到达分组调度器的数据量大，用户时 延就会变长。 总的来说，m l w d f 调度算法引入了时延参数，可以保证一定的时延要求， 但是只适合c b r 业务，不适合r 业务。 4 4 2b p f 调度算法 b p f 调度算法是b a r r i 盯p 删o n a lf a i r 分组调度算法的简称，也叫 e x p 髓丘a lp f 调度算法，因为其引入的b a 而盯函数为指数函数形式。文献口3 】 介绍了如何基于m a x