HSDPA中的分组调度算法

一、引言

高速下行分组接入(HSDPA)是WCDMA在无线传输方面的增强和演化，相比WCDMA在物理层上增加了HS-DSCH、HS-SCCH和HS-DPCCH三条逻辑信道。为提高移动分组数据传输能力，3GPP Release5协议中采用了自适应编码调制(AMC)、L1层H-ARQ、FCS等技术。另外，短的TTI(2ms)和多码道传输同样增强了数据速率。上面这些技术的引入都会要求系统对传输模式的快速自适应，而传输模式的选择策略关键是快速调度算法，也是系统设计的核心要素。

对于HSDPA系统，分组调度器由WCDMA的RNC侧移到了NodeB侧，这样调度器能容易地接入到空中接口的测量参数，更大可能匹配不同无线信道下的数据速率, 满足不同种类高速分组数据业务的QoS 要求, 其中尤为关键的是通过调度算法来提高平均业务速率和系统的整体稳定性。为最大化吞吐量，调度器必须选择最大载干比(C/I)的用户传输数据。但这种机制可能会使距离NodeB最近的UE产生信道资源垄断。因此HSDPA的调度算法将起到非常重要的作用，这需要充分考虑到各用户分组排队等候的情况、信道条件及其变化状况等。

本文在第二部分介绍了分组调度概述和研究内容；第三部分介绍了传统的调度算法；第四部分分别介绍了HSDPA系统中的两种代表性调度算法；最后，对其性能进行分析比较。

二、分组调度概述和研究内容

分组调度(Packet Scheduling,下面简称PS)是无线资源管理的一个重要组成部分，从协议框架上来看它位于L2、L3层。3GPP Realease5以前的版本一般将无线分组调度算法放在RNC上进行，借鉴了计算机网络的做法。但对无线网络有其自身的特点(或者说QoS要求)，如信道的快速时变特性，将PS放置在RNC侧就不能很好的、自适应的、迅速的反映当前时变信道的传输信息，从而无法进行快速的链路自适应(LA)和快速PS，所以未来的移动通信系统都把PS放置在基站侧进行控制，这样PS可以及时的根据信道情况和衰落特性自适应改变调制方式或其它传输参数，同时减少用户设备(UE)的内存要求和系统的传输延迟。

经典的分组调度有六个要素：被调度对象、调度者、调度目标、调度规则、调度代价和调度结果。在无线通信分别对应于下面六个实体：

l 被调度对象――存放在队列中不同业务流的分组。

l 调度者――网络节点或驻留在其中的一段程序。

l 调度目标――QoS保证及各业务之间享受服务的公平性。

l 调度规则――调度算法，它是其余五个要素的纽带。

l 调度代价――计算复杂度及缓存区资源占有情况。

l 调度结果――经过调度算法控制后，各个业务实际所获的服务质量。

在HSDPA中，分组调度器在协议中的位置，以及它和H-ARQ、AMC等关键技术的实现关系如右图所示。PS的功能是判决在什么时间分配给哪些用户什么样的无线资源(频率、时间、码道、甚至子载波)来进行通信。这种判决是以最大化系统吞吐量为目标，以保证用户间的公平性为前提，以确保不同业务流的服务质量要求(QoS)为基础的。

图1 PS在HSDPA中的作用示意图

三、经典分组调度算法

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

分组调度要解决的基本问题：当多个分组业务流等待接受服务时，必须确定合理的服务规则，安排流的服务顺序和服务时间，以满足各个业务流的QoS要求。QoS性能参数包括分组时延(Packet Delay)、延时抖动(Delay Jitter)、吞吐量(Throughput)和分组丢失率(Packet Loss Rate)等参数。

下面介绍三种经典的无线分组调度算法：

1). 最大载干比算法(Maximum Carrier to Interference，简称Max C/I):

Max C/I调度算法是一种典型的利用“多用户分集效果”来实现最大化系统容量的调度算法。它的基本思想是对所有待服务移动台依据其接收信号C/I预测值进行排序，并按照从大到小的顺序进行发送。公式表示如下：

所选用户:

在这种方式下，距离基站近的移动台由于其信道条件好会一直接收服务，而处于小区边缘的用户的由于C/I较低，这些用户将得不到服务机会，甚至出现所谓“饿死现象”，从占有系统资源的角度来看，这种调度算法是最不公平的。但该算法所得到的系统容量可以作为其它调度算法的上界。另外该算法的实现也是最简单的。

2). 轮循算法(Round Robin，简称RR)：

RR算法的基本思想是保证小区内的用户按照某种确定的顺序循环占用等时间的无线资源来进行通信。每个用户对应一个队列以存放待传数据，在调度时非空的队列以轮循的方式接受服务以传送数据。

轮循算法不仅可以保证用户间的长期公平性，还可以保证用户的短期公平性；另外算法实现简单。但该算法由于没有考虑到不同用户无线信道的具体情况，因此系统吞吐量是很低的。通常，人们认为RR算法是最公平的，因为它保证所有用户占用等量的时间进行通信；同时人们认为该算法是性能最低的(它的系统吞吐量在实际系统中是最低的)。RR算法是公平性的上界和算法性能的下界。

3). 正比公平算法(Proportional Fair,简称PF):

PF算法给小区内每个用户分配一个相应的优先级，小区中优先级最大的用户接受服务。该算法的优先级定义如下：

这里(C/I)(t)指第i个用户在t时刻的载干比，而λ(t)指该用户在以t为结尾的时间窗内的吞吐量。显然，在覆盖多个用户的小区中，当用户连续通信时，λ(t)逐渐变大，从而使该用户的优先级变小，无法再获得服务。

该算法对时间窗的长度通常有严格的要求，一般要足以覆盖快衰落的变化，并且满足用户的时延要求。

由于不同用户的(C/I)(t)是独立同分布的，因此在任意时刻同一小区内的不同用户获取服务的概率是相等的。当用户获取服务时，它的快衰落状况必然是最好的。这样从长时间来看，小区内的用户占用相同的时长进行通信，是一种公平调度算法；同时由于服务时机选择，用户只有在快衰落状况比较好的时候才获得服务，所以系统吞吐量得以提高。通过仿真可以看到，相对于RR算法，采用PF算法的系统吞吐量提高了25%左右。

下面简要比较一下三种算法的性能：

三、现代通信中的PS算法

从上面的分析可以看到，PF算法是无线通信中常用的分组调度算法。实际上对一些低速率的NRT(Non Real Time)业务有很大的适应范围。但对一些QoS要求比较高的分组业务来说，PF算法还要做一些修正以适应新的业务。下面就来介绍两种常见的算法。

1). 自适应比例公平(APF)算法：

PF算法在用户间经历相似的信道条件时可以给出公平的数据速率分配。实际上，由于用户信道所经历的往往具有不同的衰落特性，PF算法就不能给出和其平均速率成正比的公平分配，从而造成某些用户的QoS下降。Jack M. Holtzman在“Asymptotic analysis of proportional fair algorithm”一文中指出了用户在经历更多信道变化时会比其它用户具有更高的优先级，从而获得较高的数据速率。

为了弥补PF算法的公平性缺失，很多改进算法被提了出来，如Hoon Kim所提出的DRC(Data Rate Control)准则，Ghassane Aniba提出的APF算法等。下面着重介绍APF算法。

同其它PS算法一样，APF的目标也是提供用户公平性的同时最大化用户吞吐量。用户的优先级定义如下：

式中，R是用户t时刻的瞬时速率，λ是用户的平均数据率(吞吐量)，c是用户i的控制参数。由此可以看出该算法比PF算法多出一监控更新模块，该模块能追踪不同用户信道的快速变化。算法在每个TTI执行一次，而c的更新需要较大的时间周期，比如50TTI=0.1秒。在更新模块中我们计算用户i的比例数据率(R/λ)和所有用户的平均值之间的差异是否在可接收的范围内。如果超出设定范围则用户的控制参数c得到更新，其准则如下：

式中，Δc的选择依赖于收敛速度的选择和收敛值附近的波动考虑。Δc越大，收敛速度越快同时收敛值附近的毛刺越大；反之，收敛速率慢但比较平滑。一般取Δc=0.01 0.001。

研究分析和仿真结果表明，相对于PF算法(各用户分配到的速率在18%~46%之间)，APF算法(各用户分配到的速率在26%~28%之间)获得良好的公平性。然而这种公平性的增强是以牺牲约10%的系统吞吐量为代价的。但对每一个用户来说，相当于3%的平均平均速率损失，因此该算法是公平算法，并且对不同信道条件下的用户没有明显的速率损失。

2). M-LWDF算法：

M-LWDF(Modified Largest Weighted Delay First)算法是针对高速率业务流而提出的，广泛用于HSDPA、EVDO、4G等系统中。该算法的主要思想是将分组数据包的时延和如何有效利用信道信息平衡考虑，其用户优先级的计算不仅和用户当前的信道质量有关，还和包的队列时延有关。

用户i在第n个TTI的优先级计算公式如下：

式中，δ代表用户的QoS参数，R(n)是用户在第n个TTI的最大数据速率，λ是用户i的平均吞吐量，D[n]是用户i所在包的队列延时，T是用户i能容忍的最大时延(丢弃时间参数)。

该算法在小区吞吐量和基站队列所产生的时延抖动作了有效折衷，是一种非公平算法，用户信道条件好时会有更好的QoS，一般有2~3s的队列延时。然而对信道条件差的用户来说，该算法会造成这些用户的数据包在基站侧有较大的时延，当时延超过用户的最大容忍时间时就会被抛弃。为了降低被抛弃的概率，提高用户间公平性，需要对吞吐量较低的用户进行补偿，该补偿利用了信道条件有利的用户低时延。这时上面公式修正为：

式中，/R[n]代表用户i的TTI平均最大数据速率，max{/R[n]}是一个常量，其值等于小区中最大的/R[n]。

修正公平性后的算法虽然具有良好的公平性，但是小区吞吐量会下降。例如，对Ti=3s时采用修正公平性的M-LWDF算法会导致小区吞吐量降低8%左右。M-LWDF算法是吞吐量最佳算法。实际系统中对于流业务的用户来说，其用户间的吞吐量近似相等，因此一般不便对较差信道环境的用户分配更高的优先级。

四、结论和展望

本文先给出了无线分组调度中常见的三种经典算法：Max C/I、RR和PF算法。通过对这些算法的分析，并结合HSDPA系统的新特性，本文分析了APF和M-LWDF算法。

APF算法是公平算法，但其考虑到了不同用户的信道条件，需要对每一用户进行监控以便更新用户控制参数。在算法结构上比较复杂，需要两个模块，一个每TTI更新一次用户的瞬时速率，另一个每50个TTI更新一次用户控制参数。M-LWDF算法需要和接纳控制一起工作，它将不同用户分组数据包的时延和当前信道质量信息综合考虑，是针对流业务提出的一种吞吐量最佳算法。

分组调度作为HSDPA中的关键部分，随着HSDPA的进一步演进，MIMO和OFDM技术的引入，势必会引起分组调度新的研究热潮。

参考文献：

[1] 3GPP TR 25.922,“Radio resource management strategies”, http://www.3gpp.org, Semtemper,2005

[2] Aniba,G.; Aissa,S. “Fast packet scheduling assuring fairness and quality of service in HSDPA”, Electrical and Computer Engineering, 2004. Canadian Conference on.Volume 4. 2-5 May 2004 Page(s):2243 - 2246 Vol.4

[3] Ameigeiras, P.; Wigard, J.; Mogensen, P.;“Performance of packet scheduling methods with different degree of fairness in HSDPA” Vehicular Technology Conference, 2004. VTC2004-Fall. 2004 IEEE 60th Volume 2, 26-29 Sept. 2004 Page(s):860 - 86? Vol. 2

[4] Ameigeiras, P.; Wigard, J.; Mogensen, P；“Performance of the M-LWDF scheduling algorithm for streaming services in HSDPA” Vehicular Technology Conference, 2004. VTC2004-Fall. 2004 IEEE 60th. Volume 2, 26-29 Sept. 2004 Page(s):999 - 1003 Vol.2

[5]王莹 张平，“无线资源管理”，北京邮电大学出版社，2005.5

作者：付军峰，fjf_dream@163.com，东南大学无线电工程系研究生