（通信与信息系统专业论文）lte中qos调度算法研究.pdf

摘要 l t e ( l o n gt e r me v o l u t i o n ，长期演进) 是3 g p p 启动的一项超3 g 的宽带无线 接入技术。分组调度是l t e 实现高数据容量和快速传输速率不可或缺的重要组成部 分，其主要任务是为无线用户的各种分组业务合理分配无线资源，在保证用户公 平性的前提下，有效提高移动傣道利用率和业务的服务质量( q o s ) 。 论文首先分析了l t e 的背景和发展状况，并通过研究l t e 的网络结构与核心技 术，总结出l t e 的技术特征和性能优点。接着，对分组调度算法的分类、q o s 指标 和调度目标进行了介绍，并对现有的几种经典分组调度算法进行了深入的研究。 通过对这些算法性能的分析，比较了它们的性能特点和应用局限。在此基础上， 结合l t e 的特点提出了两类改进算法，并对它们的性能进行了理论分析和实验仿 真。通过对新算法与经典算法在吞吐量、丢包率、公平性等方面进行比较分析， 说明了改进算法的性熊和优势。 关键词：i _ t e 0 0 s 分组调度算法吞吐量丢包率公平性 a b s t r a c t l t e ( l o n gt e r me v o l u t i o n ) i sab r o a d b a n dw i r e l e s sa c c e s st e c h n o l o g yd e v e l o p e d b yt h et 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 ( 3 g p p ) i no r d e rt oa c h i e v et h eh i g hd a t a r a t e s ，p a c k e ts c h e d u l i n ga l g o r i t h mi san e c e s s a r yp a r to ft h el t es y s t e m i tc a na l l o c a t e t h ew i r e l e s sr e s o u r c e sr a t i o n a l l yf o rp a c k e tr a d i os e r v i c e s n o to n l yt h ef a i r n e s sb e t w e e n u s e r sc a nb ee n s u r e d ，b u ta l s ot h eu t i l i z a t i o no fr a d i oc h a n n e la n dt h eq o so fp a c k e t r a d i os e r v i c e sc a nb ei m p r o v e db yp a c k e ts c h e d u l i n ga l g o r i t h m a f t e r i n t r o d u c i n gt h eb a c k g r o u n dk n o w l e d g ea n dd e v e l o p m e n to ft h e n e x t g e n e r a t i o nw i r e l e s sn e t w o r k - l t e ，t h en e t w o r ks t r u c t u r ea n dk e yt e c h n o l o g i e so fl t e a r es t u d i e di nt h i sp a p e r , a n dm a n ya d v a n t a g e sa n dc h a r a c t e r i s t i c so fl t ea r ep u t f o r w a r d t h e n ，t h ec l a s s i f i c a t i o n ，q o sg u i d e l i n ea n dt h et a r g e to ft h ep a c k e ts c h e d u l i n g a l g o r i t h ma r ei n t r o d u c e d w i t hf i v ec l a s s i c a lp a c k e ts c h e d u l i n ga l g o r i t h m sa v a i l a b l e l u c u b r a t e d ，t h e i rp e r f o r m a n c e sa n ds h o r t a g e sa r ea n a l y z e d b a s e do nt h ea n a l y s i s ，t w o i m p r o v e da l g o r i t h m sa r ep r o p o s e d f i n a l l y , t h et w on e wa l g o r i t h m sa r ea n a l y z e da n d s i m u l a t e d c o m p a r e dw i t hc l a s s i c a lp a c k e ts c h e d u l i n ga l g o r i t h m si nt h r o u g h p u t ，p a c k e t l o s tr a t ea n df a i r n e s s ，t h et w on e wa l g o r i t h m sa r ep r o v e df e a s i b l ea n da d v a n c e d k e y w o r d s ：l o n gt e r me v o l u t i o nq o s p a c k e ts c h e d u l i n ga l g o r i t h m t h r o u g h p u t p a c k e tl o s sr a t ef a i r n e s s 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注髑致谢中所罗列豹内容以外，论文中不 含有其他人已经发表或撰写的研究成果；也不包含为获得西安电子科技大学或其 它教育机构的学位或证书面使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均己在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 日期 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的只是产权单位属西安电子科技大学。本人保诋毕 业离校后，发表论文或使用论文互作成采时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 郝或部分内容，霹以允许采震影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密，在年解密后使用本授权书。 本人签名： 导师签名： 冒期 日期 第一章绪论 第一章绪论 3 g 技术的出现给移动通信带来了巨大影响，为人们的生活带来了前所未有的 体验，使上霹冲浪、联踺游戏、远程办公等摆脱了场地和环境的约束，实现了真 正的无所不在【l j 。随着无线通信技术的进一步发展，o f d m 等新技术应用于无线宽 带接入系统中，将无线遴信的接入速度提升到1 0 0 m b p s 量级，l t e ( l o n gt e r m e v o l u t i o n ，长期演进) 正是这种无线宽带接入系统的代表。l t e 是3 g 的演进，它 改进并增强了3 g 的空中接入技术。l t e 在2 0 m h z 频谱带宽下能够提供下行1 0 0 m b i t s 与上行5 0m b i t s 的峰值速率，并改善了小区边缘用户的性能，提高了小区容 量和降低了系统延迟 2 1 。 1 1l t e 背景介绍 随着移动通信技术的蓬勃发展，无线通信系统呈现出移动他、宽带化和撑化 的趋势，移动通信市场的竞争也豳趋激烈。为应对来自w i m a x ，w i f i 等传统和 新兴无线宽带接入技术的挑战，提高3 g 在宽带无线接入市场的竞争力，3 g p p _ 开 展u t r a 长期演进技术( l o n gt e r me v o l u t i o n ) 的研究，以实现3 g 技术向b 3 g 和4 g 的平滑过渡。l t e 改进并增强了3 g 的空中接入技术，采用o f d m 和m i m o 作为 其无线网络演进的基础性技术。 2 0 0 4 年1 1 月，3 g p p 通过了关于3 g 长期演进( l o n gt e r me v o l u t i o n ) 的立项 工作，2 0 0 5 年6 月的魁j 艺克会议上最终确立了系统目标，l t e 的概念正式确立。 3 g p pl t e 的总体特征是：更高的数据速率、更低的时延、改进的系统容量和覆盖 范围，以及较低的成本翻。 1 1 1l t e 的总体架构 l t e 采用由n o d e b 节点构成的单层结构，与传统的3 g p p 接入网相比，l t e 中没有r n c ( r a d i on e t w o r kc o n t r o l l e r ) 节点。名义上l t e 是对3 g 的演迸，但事实 上，它对3 g p p 的整个体系架构作了革命性变革，逐步趋近于典型的i p 宽带网结 构1 4 j 。总体上说这是一种扁平化的设计思想，这种结构于多方面有利：简化网络和 减小延迟；减少网络层次；降低处理复杂度；提升网络性能；减低网络成本；增 强网络扩展灵活性和降低网络管理复杂度。 l t e 的架构骖j 如图1 1 所示，也羹麓演进型u t r a n 结构( e u t r a n ：e v o l v e d 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 sn e t w o r k ) 。e u t 黜蝌主要由e n b 一层构成。因 为和原来的u t r a n 相比少了r n c 节点，所以e n b 节点不仅需要完成原来n o d e b l t e 中q o s 调度算法研究 的功能，还需要完成r n c 承担的大部分功能，包括物理层、m a c 层、r r c ( r a d i o r e s o u r c ec o n t r 0 1 ) 、调度、接入控制、承载控制、接入移动性管理和r r m ( r a d i o r e s o u r c e m a n a g e m e n t ) 等。n o d e b 之间采用网格( m e s h ) 方式直接互连，这也是对原 有u t r a n 结构的重大修改。e n b 基站之问通过x 2 接口相互连接，e n b 基站通过 s 1 接口与e p c ( e v o l v e d p a c k e t c o t e ) 相连，其中通过s 1 - m m e 接口与m m e ( m o b i l i t y m a n a g e m e n t e n t i t y ) 连接，通过s i - u 接口与s a e ( s y s t e m a r c h i t e c t u r e e v o l u t i o n ) 网关相连。 m m e s a em 关 e n b 1 1 2l t e 模块功能 m m e s a e 网关 e n b 图1 1b u t r a n 总体架构 e n b 图1 2 是s a e l t e 的各网络节点的功能划分示意图。从图12 可以清楚地看到， 由于没有了r n c ，空中接口协议的物理层、m a c 、r l c ( r a d i o l i n k c o n t r o | ) 和r r c 功能都由e n b 进行管理和控制，也包括完成基站之问的切换。由于少了一层节点， 使得m a c 处理与物理层处理之间的时延缩短了，用户层的数据传送和无线资源的 控制变得更加迅捷。这对于采用混合自动重传请求技术( h a r q ) 的纠错方案而言至 关重要。 叁 第一章绪论 3 图1 2s a e l t e 的功能划分 l t e 各个模块的主要功能如下： 1 e n b 基站的主要功能： 1 ) 无线资源管理功熊，无线承载控制，无线准入控制，连接移动性控制以及 上下行链路资源的动态分配与调度； 2 ) 封装用户数据流和压缩i p 报文头； 3 ) 为用户选择m m e ； 4 ) 将用户面数据路豳到s a eg a t e w a y ； 5 ) 调度和传输m m e 寻呼消息； 6 ) 调度和传输广播消息； 7 ) 测量帮测量报告处理。 2 m m e ( m o b i l i t ym a n a g e m e n te n t i t y ，移动性管理实体) 的主要功能： 1 ) 将寻呼消息发向各个e n b ； 4 l t e 中q o s 调度算法研究 2 ) 安全控制( 鉴权认证、信令完整性保护和数据加密) ； 3 ) 用户空阑状态的移动性管理； 4 ) s a e 承载控制。 一 3 s a e ( s y s t e m a r c h i t e c t u r ee v o l u t i o n ，系统架构演进) 网关的主要功能 1 ) 雳户数槎包在无线接入溺的终结； 2 ) 支持u e ( u s e re q u i p m e n t ，用户设备) 的用户面数据交换。 1 2 1l t e 的核心技术 1 2l t e 的的特点与优势 l t e 不仅通过简化结构来优化其性熊，还利用以下几个关键技术来实现其优 异接毹瓣。 l 。传输技术与多址技术 l t e 蕉o f d m a 技术替代了c d m a 技术，更具体遣讲，上行传输采焉o f d m a 技术，而下行传输则采用单载波频分多址( s c f d m a ) 技术。这两种频分技术都 采黑快速簿立叶变换落f d 技术，将分醚的带宽划分隽较小的单位，实现鲻户闻蕊 带宽熬享。采用s c f d m a 易于降低手机功耗，大多数公司支持采用“频域”方 法来生成上行s c - f d m a 信号。相比予多载波传输技术，单载波频分多址可以有 效地降低待发射信号的p a p r ( p e a k - t o - a v e r a g ep o w e rr a t i o ，峰均跣) 。 从计算复杂度的角度来讲，频分技术相对于码分技术丽言，更容易根据带宽 翡要求进行扩展，铡翔燹薹带宽的c d m a 系统院o f d m a 系统需要更强豹计算能 力。此外，通过使用不同大小的f f t ，l t e 能支持1 2 5m h z 、1 6 m h z 、2 5m h z 、 5m h z 、1 0 m h z 、1 5m h z 戮及2 0m h z 等多秸带宽分配的实施要求。 2 宏分集 蕴l 于存在难以解决的“同步鲻题，缎登对攀播( u n i c a s t ) 业务不采溺下霉亍宏 分集。至于对频率要求稍低的多小区广播业务，可采用较大的循环前缀( c p ) 来 解决小区之间的同步问题。为了实现网络结构扁平化、分数化，l t e 不采用上彳亍 宏分集技术。 3 调制与编码 l t e 下行主要采用q p s k 、1 6 q a m 、6 4 q a m 三静谖测方式，上行瞒主要采用 位移b p s k 、q p s k 、8 p s k 和16 q a m 四种方式。至于信道编码，l t e 主器考虑 t u r b o 码，但并不是唯一熊，皱果能获缛骥显酶增益，也会考虑采用其缝的编码方 式，例如l d p c 码。 4 。多天线技术 m i m o 掩米暴l t e 最为校心的技求之一，蔼提高德输速率的主要手段，甜毯 第一章绪论 系统将会设计适用于宏小区、微小区和热点等各种环境的m i m o 技术。l t e 已确 定m i m o 天线个数的基本配置是下行2 ( 2 根发射天线) x 2 ( 2 根接收天线) 、上 行l 2 ，同时也在考虑4 x 4 的高阶天线配置。 当然，具体的m i m o 技术尚未确定，目前考虑的方法包括空分复用( s d m ) 、 空分多址( s d m a ) 、预编码、秩囊适应和智能天线等。下行单用户m i m o 天线的 基本配置，是指u e 有两个发射天线，在基站有两个接收天线。上行通常是2 x 2 的虚拟m i m o ，两个u e 各自有一个发射天线，并共享相弱的时频域资源。 1 2 2l t e 的主要特性 l t e 主要有以下特性1 6 l ： 1 支持不嗣的带宽。支持1 2 5m h z 、1 6m h z 、2 5m h z 、5m h z 、1 0m h z 、 1 5m h z 和2 0m h z 的带宽设置，从技术上保证3 g p pl t e 系统可以使用第3 代移 动通信系统的频谱。 2 提高频谱效率和峰值数据速率。频谱效率达到3 g p pr e l e a s e 6 的2 - - 4 倍， 下行峰值速率要求为1 0 0m b i t s ，上行峰值速率要求为5 0m b i t s 。3 gl t e 系统在 频谱利嗣率方面的技术优势，主要是透过多天线技术、自适应调制与编码( a m c ： a d a p t i v em o d u l a t i o na n dc o d i n g ) 和基于信道质量的频率选择性调度来实现的。 3 。提高小区边缘用户的吞吐率，改善用户在小区边缘的体验，增强3 g p pl t e 系统的覆盖性能，主要是通过频分多址和小区间干扰协调技术( i c i c ，i n t e r - c e l l i n t e r f e r e n c ec o o r d i n a t i o n ) 来实现。 4 降低无线网络时延。用户面内部单向传输时延低于1 0 m s ，控制面小于 l o o m s ，控制面从睡眠状态到激活状态的迁移时间低于5 0 m s ，从驻留状态到激活 状态的迁移时间小于l o o m s ，| 以增强对实时业务的支持。 5 以分组域业务为主要目标，取消电路交换，采用基于全分组的分组交换， 语音业务通过l p 语音( v o i p ) 来实现，放而提高系统频谱利用率。 6 支持与现有3 g p p 系统和非3 g p p 系统的互操作。 7 支持增强型的广播和多撬业务，进一步增强对多媒体广播和多播业务的支 持，满足广播业务、多播业务和单播业务融合的需求，主要通过物理层帧结构、 媒体接入控制层的信道结构和高层的无线资源管理实现。 8 降低建网成本，实现从3 g p pr e l e a s e 6 的低成本演进。 9 实现合理的终端复杂度、成本和耗电。 1 0 支持增强的i m s ( i p 多媒体子系统) 和核心网。 1 1 追求后向兼容，并仔细考虑性能改进和向后兼容之间的平衡。 1 2 针对低速移动优化系统，同时支持高速移动。 6 l t e 中q o s 调度算法研究 1 3 支持配对的( p a i r e d ) 和非配对的( u n p a i r e d ) 频谱分配方式。 1 4 尽霹能支持简单的临频共存。 1 2 3l t e 的技术优势 面对传统运营商纷纷加入移动通信市场及“其他无线通信标准的竞争，3 g p p 启动了l t e 项目。针对w i m a x “低移动性宽带i p 接入的定位以及适用于在办 公室和家庭中使用的短距离无线技术w i f i ，l t e 提出了相对应的需求，如相似的 带宽、数据速率，强调m b m s 等。l t e 与w i m a x 和w i f i 相比有以下技术优势【4 】。 l 。灵活性 l t e 能够支持1 2 5 m h z ，2 5 m h z ，5 m h z ，1 0 m h z ，1 5 m h z 和2 0m h z 等多 种系统带宽。w i m a x 支持1 5 - - 2 0m h z 几种带宽，而w i f i 解决的是无线局域嬲 问题，仅适用于有因特网的地区，因而在系统部署上l t e 更具灵活性。 2 数据速率 l t e 增强了3 g 的空中接入技术，信号的覆盖范围大幅延伸。在2 0m h z 的带 宽下，能达到下行1 0 0m b i t s 、上行5 0m b i t s 的峰值速率；w i f i 与w i m a x 所能 达到的最高速率仅为1 1m b i t s 和7 5m b i t s ，且w i f i 采用的无线电信号易受环境 影响，假如一个用户通过w i f i 与带宽为1 1m b i t s 网络互连，那么其兑现的网速 可能只有lm b i t s 。 3 移动性 l t e 能在3 5 0k m h 的高速移动的情况下达到良好的接收效果，w i m a x 所能 支持的最高移动速率只能达到1 2 0k m h ，w i f i 则仅限于局域网的低速率移动。尽 管l t e 和w i m a x 在原始数据速率方面基本相当，但除了规模更大外，w i m a x 作为一种固定w a n 技术更像w i f i 网络。因此，移动功能的开发工作都是在 w i m a x 标准的基础上进行。 与w i m a x 这种一开始就作为固定无线联阙的技术不同，l t e 一开始就来自 于g s m u m t s 等移动无线领域。移动性是l t e 标准的开发起点，而不是后续添 加的特性。因此，l t e 的移动性不同于w i m a x ，它更加统一于技术本身，是技术 自身的有机组成部分。l t e 的移动能力显著高于w i m a x 。l t e 开发人员可充分利 用其在g s m 和w c d m a 技术领域所积累起来的丰富移动经验和知识进行开发。 1 3l t e 的市场发展现状 研究机构v i s a n t 发布最新研究报告称，新的移动通信技术正在逐步走向成熟， l t e 作为移动运营商的首选移动通信平台，预计将在2 0 1 4 年获得规模化部署，其 用户数将达至l3 9 0 0 万，丽设备收入将达到9 0 亿美元。该咨询机构的分析家指出， 第一章绪论 市场预计基于o f d m 的l t e 技术将在今后3 年加速发展，从2 0 0 8 年到2 0 1 4 年这 6 年闻，将是l t e 打基础的阶段，此后市场的需求将会快速增长。 业内分析家称，l t e 是目前欧洲3 g 系统u m t s 向未来演进的首选技术。2 0 0 9 年，全球g s m 和u m t s 用户数将达到3 0 亿，截止2 0 1 4 年，将会有数百家移动 运营商采用l t e 技术。下面从设备商和运营商的角度对l t e 当前的市场发展状况 进行分析【7 j 。 1 运营商 l t e 目前已经得到了拥有最多运营商的g s m 协会的支持，各主流运营商也纷 纷表态选择l t e 。 美国a t & t 首先表示它将采用l t e 技术。a t & t 移动通信事业部执行长r a l p h & l a v e g a 表示，对于a t & t 而言，l t e 技术将是符合逻辑的选择，未来几年将视 情况投入l t e 网络建设。2 0 0 7 年9 月，英国沃达丰宣布其l t e 计划，沃达丰c e o a r u ns a t i n 表示：“我们将从h s p a 到l t e ，而v e r i z o n 则从e v - - d o 到l t e 。l t e 的部署将会在3 - 4 年后。2 0 0 7 年珏胃，g s m 协会选择了l t e 标准，并声称全 球有超过7 0 0 家g s m 运营商会首选这一标准。2 0 0 7 年1 2 月，美国第二大移动运 营商v e r i z o nw i r e l e s s 宣毒将采用l t e 构建4 g 技术平台，并计划在2 0 0 8 年展开测 试。2 0 0 8 年2 月1 5 日，中国移动总裁王建宙在巴塞罗那举行的2 0 0 8 年3 g s m 大 会上声明，中圜移动将携手英国沃达丰、美国v e r i z o n 加入l t e 的测试。 日本最大的移动运营商_ n t td o c o m o ，可能会成为首家大规模部署l t e 的移动运营商。目前，d o c o m o 正在积极推动提高日本手机宽带服务速度计划， 并期望l t e 能够担当起这重任。对于d o c o m o 丽言，部署l t e 的优势在于其可 以运行于现有的3 g 网络上。现在，d o c o m o 已经启动了对l t e 的测试，并选择 了l t e 合 乍伙俘。 在全球移动运营商的普遍支持下，l t e 展现了美好的未来。来自市场研究公 司j u n i p e rr e s e a r c h 的研究报告表骧，2 0 1 2 年全球l t e 服务用户将达到2 4 0 0 万， l t e 将成为移动宽带技术中长期的继任者。 2 设备商 运营商普遍选择l t e 为全球移动通信产业指明了技术发展的方向，设备制造 商也纷纷加大在l t e 领域的投入，从而推动l t e 不断前进，使l t e 的商用与其他 竞争技术相吃更秀嚣令人期待。 1 ) 在商用产品推出方面： 按照3 g p p 制订的工作计划，l t e 将予2 0 0 8 年或2 0 0 9 年推爨商用产品。与 此对应，设备制造商纷纷计划推出可商用l t e 产品计划。其中，华为计划予2 0 0 9 年正式推出基于多制式基站的l t e 商用产晶，并在全球开始部署l t e 商用网络； n e c 预计i 厢有奖服辞糯千2 0 0 9 年下半年军2 0 1 0 年推出，因而积辍准备相关网 8 l t e 中q o s 调度算法研究 络及终端产品；大唐则与爱立信在l t e 领域展开合作，重点研发l t e t d d 技术， 著预计t d - - l t e 系统将于2 0 1 0 2 0 1 2 年之闯捺泓，并可实现热点地区覆盖。 2 ) 在应用测试方面： 在设备制造商的合力推动下，l t e 于2 0 0 8 年开始部署试商用网络。目前，l t e 应雳测试进展顺利。2 0 0 7 年ll 胃，阿尔卡特朗讯和l g 奄子通过采用前者的l t e 解决方案和后者的l t e 试验终端，成功地完成了l t e 呼叫测试。这是l t e 商业化 进程中的一个重要里纛碑。紧随冀后，诺基委在德国耪棒完成了世界上首铡在市 区环境中对l t e 的多用户野外试验，证实3 g p p 标准技术能够满足l t e 的性能要 求，表鹗l t e 从实验塞翔正式商用又迈进了一步。 1 4 论文工作安排 论文各章的内容安排如下： 第二章主要介绍了分组调度，首先介绍了分组调度中的q o s 性能指标，并根 据q o s 性能指标分析了分组调度的目标，最后分析了l t e 中的调度。 第三章介绍了几种典型的无线分组调度算法，包括轮询调度算法、公平吞吐 量算法、最大载于院算法、眈铡公平算法和ml w d f 算法，对各个算法瀚性熊特 性和缺点进行分析。 第鳃章首先绘凄了两类改进型算法，接着，介绍了算法待真的设诗，最螽对 经典算法和改进算法进行仿真，并对仿真结果进行分析比较。 第五章对论文工终进行总结，并给如了对未来研究工佟的展望。 本文对无线通信中的分组调度算法进行了宥意义的探索和改进，对该领域的 研究工作具有一定的参考价值。 第二章分组调度简介 9 第二章分组调度简介 无线通信系统是资源受限的，如何利用有限的系统资源满足日益增长的用户 需求，汪经成为移动通信设备制造商和运营商亟需解决的问题。如果没有有效的 无线资源管理策略，再先进的传输技术，再宽的带宽也会因调度处理不合适而不 能充分发挥其优势。 2 1 分组调度的基本含义 分组调度就是针对不同分组的数据业务特性，对分组数据用户的业务进行管 理和调度。分组调度要解决的基本问题为：当多个分组业务流等待接受服务时， 必须确定合理的服务规则，安排业务流的服务顺序、服务时间以及传输分组使用 的比特速率，以满足各个业务流的q o s 要求。 调度器是进行分组调度的功能实体。无线通信中调度器的基本模型 8 , 9 1 翔嚣2 1 所示。 图2 1 无线通信中调度器模型 一个好的调度算法要求在保证用户q o s 要求的同时最大化系统容量，要兼顾 系统的吞吐量与用户的q o s 要求。为了达到这一要求，需要为调度器提供一定的 外部信息，如用户信道状况、数据的队列长度等。调度器综合考虑各种因素，在 充分利耀信道状态信息和用户业务队列信息的同时，尽量减少信令及其他各方面 的开销，最大限度地提高系统的性能。 2 2 。1q o s 简介 2 2 无线分组调度 数据、音频、视频等各种多媒体业务的涌现，i n t e m e t 提供的传输服务已由单 一的数据业务服务向综合业务服务发展，不同类型业务对服务质量有不同的要求， 1 0 l t e 中q o s 调度算法研究 所以需要通过q o s 来保证和区别不同业务的服务质量。 q o s 1 0 , 1 h ( q u a l i t yo fs e r v i c e ，照务质量) 是服务性麓的总效果，是鬻户对服 务的满意程度的衡量。q o s 是调度算法所要满足的目标，同时也是锘i 定调度规则 的主要准则。q o s 性能参数包括分组时延( p a c k e td e l a y ) 、时延抖动( d e l a yj i t t e r ) 、 吞睦量( t h r o u g h p 哟秘分缀丢失率( p a c k e tl o s sr a t e ) 等参数，其律瘟用不丽，对q o s 各项指标的要求也不同。例如长文件传输要求传输速率高且分组丢失率低，但对 对延稠抖动不是太敏感；丽撬频会谈不仅要求赞输速率离，焉置对隧延帮抖动也 很敏感。 2 2 2 无线多媒体业务分类 全球无线通信系统将业务分成透大类，基本上是按照时延要求来划分豹。 1 ) 会话式业务：这是一类典型的实时业务，要求端剥端延迟和抖动小。此类 业务有电话、i p 电话、视频会议等。 2 ) 流媒体业务：运一类业务数据流零向传输，也是安时业务，但对延迟要求 较宽松。此类业务有视频点播、网络实况广播等。 3 ) 交互式业务：这类业务的特点是请求一缡应模式，对延迟几乎没有要求。 此类业务的典型代表是w e b 浏览。 莲 背景鼗务：这类业务透常对簧输延遮没裔限制。典型业务如e - m a i l ，或者 后台的f t p 下载等。 2 2 。3 无线多媒体业务q o s 性能分析 董。时延 在无线网络中，时延通常包括四个部分f 络】：处理时延、排队时延、传输时延、 和传播时延。 处理时延是指分缀到达一个节点的输入端与该分组到达该节点的输辩端之闻 的时延。若节点的传输队列在节点的输出端，则排队时延指分组进入传输队列到 该分组实际进入传输熊融延。若等待驮列在节点的输入端，则撵队时延是指分组 进入等待队列到分组进入节点进行处理的时延。传输时延是指发送节点在传输链 路上_ 开始发送分组薛第一个比特到发送完该分组的最瑟一个毙特赞需要的对闻。 传播时延是指发送节点在传输链路上发送第一个比特的时刻到该比特到达圈的节 点的时延。 2 抖动 抖动 1 2 1 是擂由于各种时延的变化导致网络中数据分组到达速率的变化，也可 虢谈为是对甓道时延变动的度量馕。它主要由以下几个溺素琴l 起：分组麴摊酸对 第二章分组调度简介 延、可变的分组大小、中间链路等。补偿抖动的常用方法是在接收端设备( 手机、 掌上电脑等) 上进行缓冲处理，虽然这与减小时延的目标相悖，但对于消除抖动 带来的影响是必要的。 3 丢包 无线网络中主要有三个原因会导致丢包【1 2 】： 1 ) 载波监听多点接入( c s m a ) 域中流量过大，有冲突的包就会被丢弃； 2 ) 时延变化过大，因为包到达缓冲器过晚或过早都会被丢弃； 3 ) 当等待队列满时到达的数据包会被丢弃。 对于语音业务来讲，它具有实时性的特点，所以就没有时间重新发送丢失的 包。这些丢失的包会使语音通信产生间断，进而产生静音，如果频繁发生丢失， 那么通话就变得毫无意义。 2 3 分组调度的主要目标 分组调度要解决的基本问题是【1 4 】：当多个分组业务流等待接受服务时，必须 确定合理的服务规则，安排业务流的服务顺序和服务时间，以满足各个业务流的 q o s 要求。在无线调度算法的研究中，需要考虑的两个重要因素是：吞吐量和公 平性。吞吐量是指小区吞吐量，公平性一般认为是各用户或不同分组业务占用信 道资源的统计结果。吞吐量和公平性是通过调度规则来保证的。分组调度的主要 目标有以下几点： 1 保证时延：对于时延敏感性业务流，要确保时延不能超过某一阈值。 2 保证公平性：算法要能保证无线资源在所有业务流中公平分配。 3 保证吞吐量：算法能够确保系统短期的吞吐量和长期的吞吐量。 4 保证丢包率：算法要能保证分组到达时被丢弃的概率小于某一阈值。 2 4l t e 中的资源调度 调度是3 g p pl t e 的一个重要组成部分。3 g p pr e l e a s e 5 之前将无线分组调度 器功能放置在r n c 上瞄】，但是这样不能自适应地和迅速地反应当前时变信道的信 道信息，从而无法进行迅速的链路自适应和快速调度，所以在l t e 系统中把调度 器放置在基站侧的m a c 层1 2 4 。l t em a c 层的结构如图2 2 所示。这样可以根据 信道的信息进行快速地调度，可以及时地根据信道情况和衰落特性自适应改变调 制方式或其它传输参数，同时减少用户设备m e ) 的内存要求和系统的传输延迟， 这样就更好地满足了高速通信的要求。 l t e 中q o s 调度算法研究 圆2 2 l t e m a c 层结构 h 目r n 圈2 3l t e 时频二维资源 l t e 是基于全i p 的分组交换网络，系统带宽范围从1 , 2 5 m h z 到2 0 m i t z ，大 于典型场景信道相关带宽，调度器每隔一个1 1 1 ( t r a n s m i s s i o nt i m ei n t e r v a l ) 调度 一次，每个t t i 为l m s 。 l t e 中调度的最小无线资源单位为时频资源块( r b ，r e s o u r c eb l o c k ) 每个 时频资源块在频域上由1 2 个子载波( s u b c a r r i e r ) 构成，时域上为l m s ( 1 4 个o f d m 符号) ，对于下行信道，前1 - 3 个符号用于传输控制信令，其余o f d m 符号用于数 据传输。如图2 3 所示，整个频段被划分成大小相等的资源块，若干个r b 组成子 带( s u b b a n d ) 。为了简化调度，下行调度中将予带作为最小调度单元。在每一个 第二章分组调度简介 1 3 子帧的开始，根据一定的调度算法将资源块分配给不同的用户，图2 3 中，该t t i 将频率资源分别分配给了用户董、2 、3 、4 。 因为l t e 中的频带要宽于普通的无线接入系统，这就决定了调度中既需要针 对某一频带选撵在该频带上信道质量最好的用户，也需要对某用户选择其信道 质量最好的频带1 2 5 1 1 2 6 1 。因为无线信道中普遍存在频率选择性衰落，对餍户选择其 信道质量最好的频带就可以很好地克服频率选择性衰落。 l t e 的基本调度流程为：根据信遵状态监视灏测模块提供瀚信道信息和用户 的队列状态，调度器首先依据一定的调度算法，计算出每个用户的优先级，并根 据傀先级对溺户进行撵序，按优先绥颗序调度掰户，然舞搬据耀户在不同子信道 上的信道质量为用户分配最佳子信道，最后将数据送到发射机。l t e 基本调度流 程l z 习鲦图2 。4 所示。 y 图2 4 l t e 基本谖发流稷 调度器进行多业务调度时应该考虑每个用户设备和相应的光线承载的业务量 以及q o s 要求。当一今用户存在多种业务，即用户鸯多个无线承载时，调度器应 当采取群按用户黟的分配原则，即每次调度时调度器给一个用户只发一个调度命 令，多业务闻的资源分配按照业务之间q o s 要求的差别进行分配。 1 4 l t e 中q o s 调度算法研究 2 5 本章小结 通过本章的介绍，可以看融调度器在数据传输中具有十分重要的意义，业务 的q o s 需要由调度器来保证的，如果没有一个好的调度器，纵然有很大的带宽， 用户也可能没有满意的q o s ，系统吞吐量也可戆会很低，所以如何选择调度器中 的调度算法变得尤为重要。下一章就对无线通信系统中几种经典的调度算法进行 分柝。 第三章调度算法介绍 第三章典型调度算法介绍 随着分组调度的发展，涌现出大量的分组调度算法，其中比较经典的有轮询 调度算法，公平吞吐量调度算法，最大载干比算法，比例公平算法和ml w d f 算 法。这五种算法经常被用作其他算法的比对算法，下面就对这五种算法一一进行 分析。 3 1 轮询调度算法 轮询调度算法( r o u n dr o b i n 算法，简称r r 算法) 【1 4 1 7 1 的基本思想是保证小 区内的用户按照某种确定的顺序循环地占用相等时间的无线资源来进行通信。每 个用户对应于一个队列以储存待传数据，在调度时，非空的队列以轮询的方式接 受服务来进行数据传输。轮询调度算法的调度流程如图3 1 所示。 对轮询调度有以下两种理解： 1 时间片上的理解：每个用户获得的调度机会相同，也就是每个用户用于传 输数据的总时间相等。 2 概率论上的理解：轮询地调度每个用户，就被调度的概率而言，对k 个用 户，每个用户一次循环中被调度的概率p ( k ) 都是1 k ，即每个用户以相同的概率占 有可分配的时隙和功率。 轮询调度算法认为不同用户的优先级是相同的，它不仅可以保证用户间的长 期公平性，还可以保证用户的短期公平性，而且轮询调度算法实现简单。 通常，人们认为轮询调度算法是最公平的，可以保障用户间的公平性，但因 为轮询调度没有充分利用系统中的有效信息，如载干比值等，而使得系统资源浪 费，所以系统吞吐量不高。通常r r 调度算法的结果被作为时间公平性的上界。 为了改善轮询调度算法的时延特性、无线信道自适应特性及其在变长分组环 境下的公平性，由它产生了一系列改进型算法，如机会差额轮询调度算法( o d i 淑) 、 无线差额轮询调度算法( w d i 浪) 等。 o d d r 算法对于用户i 引入了定值数据量f i x e db y t e i 和变值数据量 v a r i a b l eb y t e i ，当轮询到用户i 时，每次轮询地发送数据量： s e n d _ b y t e i = f i x e d _ b y t e i + v a r i a b l e _ b y t e i ( 3 1 ) 当用户调度完后更新v a r i a b l eb y t e i ： v a r i a b l e _ b y t e i = v a r i a b l e _ b y t e i - p e n a l t y f a c t o r xs e n d _ b y t e i ( 3 - 2 ) 其中p e n a l t y f a c t o r 是根据无线信道状况调整的参数，有两种定义方法： 1 6 l t e 中q o s 调度算法研究 1 ) 理想传输速率与实际传输速率之比； 2 ) 每单位功耗的理想传输比特数与实际传输比特数之比。 这样就在轮询调度的同时加入了对信道质量的考虑，使得信道状况好的用户 可以传输更多的数据，有助于提高小区吞吐量。 图3 1 轮询调度算法流程 w d d r 在某些方面和o d d r 类似。在每个轮询周期内它将每个用户的数据分 成更小的子块，依次发送每个用户序号最小的子块，当用户i 不存在第j 个子块时 则跳过，继续发送用户i + l 的第j 个子块，这样相当于在轮询调度同时加入对不固 用户数据请求量的考虑，数据请求量大的用户获得更多传输机会，更好地保证用 户数据请求量存在差剐情形下的用户公平性。 第三章调度算法介绍 1 7 轮询调度的主要目的有两点： 1 ) 是对某个连接两言，可能如现其它连接对网络资源的过分占耀丽导致本连 接q o s 变坏，所以要公平分配资源。 2 ) 将当前未分配的带宽动态地、公平地分配给当前所有等待服务的连接。为 各连接提供与其它连接无关的最小带宽。 3 。2 公平吞吐量算法 公平吞吐量调度算法( 1 r 算法) 【2 8 】就是依据用户的吞吐量来确定用户优先级， 进而决定当前应该调度的用户。如式( 3 3 所示： 肚赢( 3 - 3 ) 1 r ( t ) 表示用户过去的吞吐量，这样用户的优先级就和吞吐量成反比，从而保证 了吞吐量低的用户优先级高，可以优先调度，使得用户之闻吞吐量平衡。 公平吞吐量算法的目的是为所有用户提供相同的吞吐量，不用顾虑用户的位 置，用户的信道质量以及用户的q o s 要求，即用户在e n b 附近和用户在小区边缘 都可得到相同的吞吐量。为了让所有用户得到相同的吞吐量，为用户调度相同的 数据量。但是为了保证通信质量，所以信道质量差的用户采用比较低阶的调制编 码方式，所以信道质量差的用户就需要比信道质量较好的用户更多的资源，所戳 其吞吐量不高。公平吞吐量调度的流程如图3 2 所示。 公平吞吐量调度和轮谗调度非常类似，都是公平性很高的调度算法，但是公 平吞吐量调度和轮询调度也存在着一定差异： 1 轮询调度追求的是用户时闻片上的公平性，不同用户的吞吐量不一样。 2 公平吞吐量追求的是用户吞吐量上的公平，不同用户得到的时间片不一样。 公平吞吐量因为过于追求流量公平，没有考虑用户到达速率的差异和信道质 量的差异，所以当用户到达速率差异较大时，会对大数据流的用户造成限制。实 际的公平性应该是按不同用户的数据流量进行区分的，