HSDPA分组调度算法实现简析

摘　要　 HSDPA（高速下行分组接入，High Speed Downlink Packages Access）技术是3GPP在R5协议中提出来的提高WCDMA网络下行数据容量和传输速率的重要技术。分组调度是HSDPA的重要组成部分，负责分组业务传输块的调度和管理，对于网络性能有重要影响。本文在扼要描述HSDPA分组调度功能和过程的基础上，重点分析对比了3种经典分组调度算法原理以及在系统中的实现过程，并给出了测试结果。

关键词　HSDPA　MAC　分组调度算法　公平性　吞吐量

1　引言

HSDPA（高速下行分组接入，High Speed Downlink Packages Access）是实现提高WCDMA网络下行数据容量和传输速率的最为重要的技术。它是3GPP在R5协议中为满足上下行数据业务非对称的需求提出来的。它在不改变已有WCDMA网络结构的基础上，大大提高下行数据业务速率（理论最大值可达14.4Mbit/s）。

为改善WCDMA系统性能，HSDPA采用了如下几项重要的新技术，涉及物理层和传输层：流控制；缩短了的无线电帧；新增加的物理信道HS-PDSCH（High Speed Physical Downlink Shared Channel）、  HS-SCCH（Shared Control Channel for HS-DSCH）、  HS-DPCCH（High Speed Dedicated Physical Control Channel）；自适应调制和编码（AMC）；混合自动重复请求（HARQ）；增量冗余；快速分组调度功能等。

HSDPA支持高速数据业务的能力弥补了WCDMA的不足，为运营商开展丰富新颖的数据业务提供了广阔的空间；而且HSDPA向后兼容R99版本，大部分厂商的WCDMA设备只需要软件升级就可以实现HSDPA。可预见在今后一段时间内，HSDPA将是移动通信发展的主流。

本文重点探讨HSDPA快速分组调度功能的实现。

2　HSDPA分组调度算法概述

分组调度（Packet Scheduling，PS）是无线资源管理的一个重要组成部分，从协议框架上来看它位于L2、L3层。

相比于R99，HSDPA把分组调度功能从RNC移植到了Node B的MAC（Media Access Control）层，大幅度减少了延迟，更好地适应信道的快速变化，更大可能地匹配不同无线信道条件下的数据速率。传输层上，在Node B中引入MAC实体MAC-hs来控制HS-DSCH。快速分组调度能根据终端的CQI（Channel Quality Indicator）报告决定下一个2ms时间间隔应该调度给哪个用户，并向具有瞬间最好信道条件的用户发送数据，使得每个瞬间都可以达到最高的用户数据速率和系统吞吐量。同时，2ms的短时间间隔又增加了调度进程的精确度。

在调度算法的研究中，需要考虑的两个重要因素是：吞吐量和公平性。吞吐量包括小区吞吐量和用户吞吐量，公平性可认为是各用户或不同分组业务占用信道资源的统计结果。

分组调度要解决的基本问题：当多个分组业务流等待接受服务时，必须确定合理的服务规则，安排流的服务顺序和服务时间，以满足各个业务流的QoS要求。

一般来说，HSDPA的分组调度算法一般分为3类：

· 最大信号/干扰（Max C/I）方式：系统跟踪每个用户的无线信道衰落特征，依据无线信道C/I的大小顺序，确定给每个用户的优先权，保证每一时刻服务的用户获得的C/I都是最大的。这是一种极端的分配方式，可得到理想的最大吞吐量，但是对于用户之间体现了服务的最不公平性，可能有部分用户一直得不到满意的服务。实现方法简单。

· 基于时间的轮循（Round Robin，RR）方式：每个用户按顺序被服务，得到同样的平均分配时间，但每个用户由于所处环境不同，得到的流量并不一致。用户间的公平性高，但系统吞吐量最低。实现方法简单。

· 正比公平的（Proportional Fair）方式：综合了以上方式的优点，给予当前信道条件逐步变好的用户以比较高的优先级，既照顾到大部分用户的满意度，也能从一定程度上保证比较高的系统吞吐量，是一种实用的调度方法。实现部分公平有很多算法，一般需要考虑到下行信道质量、用户缓冲队列长度、用户平均调度时间等诸多参量。实现方法复杂。

3种分组调度算法的对比如表1所示。

3　HSDPA 分组调度功能实现

HSDPA 的分组调度功能在Node B中实现，主要机制如下：

Node B中的每一块基带处理单元（BBU）都配置了MAC-hs 调度功能，为该BBU板控制的所有HSDPA小区服务。即：MAC-hs将为所有UE ID与Priority Queue ID的组合或者UE ID 与H-ARQ Process ID的组合（简称为"元素"）生成一个调度列表。然后TFRC考虑UE服务小区的可用HS-DSCH资源，来为这些元素分配无线资源。一旦选好了TFRC，MAC-hs 就将MAC-d PDU（一个或多个）组装进一块MAC-hs PDU中，完成调度列表更新，然后开始下一次调度。总体流程如图1所示。

调度列表生成（SLG）每TTI（2ms）运行一次，选择在下一个TTI中要调度的UE。根据调度算法对每个UE及其相关的数据流排序，每个入口都是UE ID和Priority Queue ID（初次传送）或者UE ID和H-ARQ ID（重传）的组合，如图1所示。

对于每个元素，都会分配一个优先级。具有最高优先级的元素将被首先调度，然后是次高优先级的元素，依次类推。通过对输入参数使用不同的权重因子集，可调整调度算法。

生成调度列表需要输入优先级、CQI、调度周期、数据流优先级等参数。SLG的策略是给予重传MAC-hs PDU相比新传MAC-hs PDU更高的权限。

首先要决定一台UE是否可在一个特定的TTI中被调度。如果满足以下条件，MAC-hs将调度一台UE：

（1）自从该UE上一次被调度的TTI算起的时间等于或者长于"effective inter TTI interval"（如果"effective inter TTI interval"等于1，则一台UE可以在每个TTI内被调度）。（2）从该UE中仍能够接收到有效的CQI。

否则将把UE从此次TTI中的调度列表中排除。

SL元素的优先级计算分为2个部分：

（1）重传MAC-hs PDU 的优先级计算

重传优先级基于接收到的CQI变化值以及T1剩余时间（the time before T1 elapse）的组合来决定：Retransmission= f( CQI variation，time before T1 timer elapse) 。

如果在CQI变化值中应用一个高值的因子，重传的可能性就高，因为无线条件改善了。CQI变化值定义为当前CQI与该传输块初次传送时CQI值之间的差值；如果在T1剩余时间上应用一个高值的因子，在达到最大重传次数（一般是4次）之前丢弃MAC-hs PDU的可能性就小了。

UE和与MAC-hs PDU重传相关的H-ARQ进程将根据重传的调度优先级来排序，优先级高的UE调度的可能性高。算法样本举例如下：

SP_Ret= RetransmissionPrioOffset +（Absolute CQI - initial transmission CQI）/30×HSDPA.CQIVariation.Factor + HSDPA.TimerT1.Factor/time before T1 elapses
　　T1 timer：控制MAC-hs PDU在HARQ Process的生存时间，当相关的T1 timer过期时，MAC-hs PDU 会被丢弃。

CQI  variation : 重传CQI与初次传送的CQI之间的变化值。

预期结果：

如果同前一次调度事件相比无线条件改善，CQI variation 会得到较高的权重，从而在重传中获得高的优先级。

如果HARQ buffer中的MAC-PDU即将被丢弃的话，time before T1 elapses会获得较高的权重，获得较高的优先级。

权重因子取值举例如下：  

权重因子以百分比的形式表示出来，范围从0到100，这些因子之和等于100。

（2）新传MAC-hs PDU 的优先级计算

新传MAC-hs PDU 的调度优先级基于如下参数： New Transmission= f（Normalized Delta Time、AbsCQI、RelCQI、Buffer Time、Scheduling Priority Indicator）

①标准差时间（Normalized Delta Time）是从上次调度事件之后过去的时间（以TTI来计算），再除以优先级队列的数量。时间越长，优先级越高。

②绝对CQI（AbsCQI），也就是UE上报的当前CQI值。

③相关CQI值（RelCQI），也就是绝对CQI与平均CQI之间的差值。值越高，优先级越高。

④缓存时间（Buffer Time）是自从接收到数据的时间，与丢弃计时器（Discard Timer）有关。BT距离丢弃计时器截止时间近的（UE，Priority  Queue）会比其他BT值较小的元素有更高的优先级。

（注：Discard timer：控制MAC-d PDU在Priority Queue中的生存时间，由优先级队列处理器来计算。对于一个HS-DSCH帧中每一块来自RNC的MAC-d PDU ，都会分配一个新的discard timer。）

⑤相关队列的调度优先级指示（Scheduling Priority Indicator）：提高SPI将增加在一个TTI内调度的可能性，可使操作员引入对用户的分类（举例：SPI 4："金牌用户"；2："银牌用户"；1："铜牌用户"。）

（注：在Iub接口，每条MAC-d 数据流都有一个优先级队列；在Iub/Iur HS-DSCH 帧协议中，会使用Common Channel Priority Indicator（Cm-CH PI）来标识数据帧优先级，范围从0到15，0的优先级最低，15的优先级最高。在NBAP协议中使用与Cm-CH PI相同值的SPI，输入到调度算法。）

算法样本举例如下：

SP=initialTransmissionPrioOffset + （Absolute CQI /3）×HSDPA.AbsCQIFactor+（Relative CQI/3）×HSDPA.RelCQI.Factor + Normalized Delta time×HSDPA. DeltaTime.Factor×■×（1 +（HSDPA.SPI.Factor×（SPI-1）/50）+ BT×HSDPA.BT.Factor

权重因子对调度算法有重要的影响，通过修改这些因子，可得到不同的算法类型。考虑HSDPA的3大类分组调度算法，我们有如下预期结果：

所有的权重因子设为0 ( 或者除了HSDPA.DeltaTime.Factor以外的因子) ，以达到Round Robin 调度。

给予Absolute CQI较高的权重因子，将得到Max C/I调度。高小区吞吐量，但是公平性降低。

给予Relative CQI 较高的权重因子，将兼顾吞吐量和公平性，实现PF调度。

优先级高的元素首先被调度；在优先级相同的情况下，则未被调度时间最长的元素被首先服务。

权重因子取值举例如下：　　

4　HSDPA调度算法验证

在以上理论研究的基础上，在实验室中我们进行了测试，来验证调度算法的实际表现。简单描述如下:

1. 测试步骤

（1）在Max C/I、RR和PF 3种不同算法下分别进行（2）～（4）的操作。

（2）将4个2Mbit/s业务的UE接入到R5 HSDPA小区，小区分配一条HS-SCCH信道。

（3）4个UE均启动FTP下传，同时启动4个UE的log记录，记录1min后结束。

（4）统计各个UE的调度次数，并记录每个UE的平均速率。

2. 测试结果及分析

在3种调度算法下测试结果如表2所示。

从上表得出在3种不同算法下总吞吐量＆调度次数最大最小差结果如下：

总吞吐量： Max C/I > PF > RR

调度次数最大最小差：Max C/I > PF > RR

我们不难看出测试结果与3种调度算法的理论描述及预期是非常吻合的。在实际网络中，我们可以通过参数调整来达到不同的调度目的，优化网络。

通过以上HSDPA分组调度算法和调度过程的扼要分析，我们已能够比较清楚地了解HSDPA分组调度功能。近年来，HSDPA的分组调度算法越来越被关注，研究人员也提出了许多新的算法和设想，比如自适应比例公平（APF）算法，修改后的最大权重延迟优先（M-LWDF）算法、估计优先权调度（EPS）算法等。这些算法各具特点：APF是公平算法，但其考虑到了不同用户的信道条件，需要对每一用户进行监控以便更新用户控制参数；M-LWDF需要和接纳控制一起工作，它将不同用户分组数据包的时延和当前信道质量信息综合考虑，是针对流业务提出的一种吞吐量最佳算法；EPS对于系统包时延特性的改善效果很突出。

相信随着HSDPA的持续演进和系统商用程度的日益提高，作为HSDPA关键部分的分组调度算法会引发更多的关注与研究，也会涌现出更多新颖且实用的算法。

由于本网页不支持图片与公式效果，如有需要请参阅杂志。