HSDPA分组调度算法的测试和比较

摘要　无线分组调度策略根据端到端业务质量的要求，在考虑业务的优先级和时延要求的情况下兼顾公平性原则，使小区的吞吐量最大化。本文主要研究基于HSDPA的3种分组调度算法，并结合实际测试结果对各种调度算法的性能进行分析。

1、引言

为提高移动分组传输能力，高速下行分组接入（HSDPA）引入了自适应编码调制（AMC）、L1层HARQ（混合反馈重传）、FCS（现场总线控制系统）等技术，更为关键的是采用快速调度算法来提高平均业务速率和系统稳定性。无线分组调度算法解决的主要问题是判决在什么时间分配给哪些用户什么样的无线资源来进行通信。这种判决是以最大化系统吞吐量为目标，保证用户间公平性为前提，确保不同业务流的服务质量（QoS）要求得到满足。

2、分组调度算法

对于不同的业务流，由于其服务质量要求不同，无线分组调度算法的执行也有所不同。针对"尽力而为"的非实时业务，调度算法主要可以分为轮询调度、MAX C/I调度和正比公平调度3类。以HSDPA系统为例，这3类调度策略遵守如下规则：

●确定调度时间间隔（TTI），调度就是在每帧的基础上进行的，在HSDPA中一个TTI为2 ms；

●队列里只要有字节的信息，该队列就是非空的；

●错误接收的分组在ARQ反馈后将重新调度，ARQ反馈与HSDPA的定义相协调；

●重传分组比初传分组具有更高的优先权，但如果连接一比连接二具有较高初始优先权，则连接一的初传优先权仍然大于连接二的重传优先权；

●调度器发送重传分组的次数达到重传允许的最大值后，该分组数据将从队列中丢弃。

2.1　轮询调度

轮询调度（RR）保证小区内所有用户按照某种确定的顺序循环占用等时间的无线资源来进行通信。小区边界的用户比靠近基站的用户得到更低的吞吐量，因此用户的QoS并不是完全公平分布的。算法执行遵循以下规则：

●每个用户对应一个缓存队列，以存放待传数据；

●在调度时，非空的队列以循环的形式接受服务以传送数据；

●在一个队列再次接受服务前，其他所有非空队列必须都被服务过一遍；

●除非只有一个非空队列，否则一个队列不可能连续接受服务；

●调度算法可一次传送多个数据包。

轮循调度从资源分配的公平性角度出发，保证了所有用户占用等量的时间资源进行通信，因此不仅可以保证用户间的长期公平性，而且可以保证用户间的短期公平性。

轮循算法的缺点是没有考虑到不同用户的无线信道的具体情况，因此系统吞吐量较低。

2.2　MAX C/I调度

在MAX C/I调度算法下，较高C/I值的用户比较低C/I值的用户具有更高的分组传输优先权。信道资源可以分配给单个最好信道条件的用户，MAX C/I调度器以牺牲公平性为代价达到更大的系统容量。

对于CDMA传输方式，假设已知小区中的用户数和用户请求的比特速率，则调度算法寻找具有最好C/I的用户，且按照请求比特速率计算相应的功率值，然后调度次高C/I用户，直到分配完所有的系统功率，这时调度算法将输出获得请求比特速率的用户数目。算法执行遵循如下规则。

●每个用户对应一个缓存队列，以存放待传数据；

●在调度时，所有非空队列以用户的C/I为优先级从高到低进行排列；

●任意时刻接受服务的用户总有最高的C/I。

如果在t时刻有K个用户同时请求传输数据，此刻每个用户的C/I为(C/I)k(t)，则MAX C/I调度算法选中的用户为：

（1）

显然，MAX C/I调度可以支持更多的用户以较高的概率实现请求的比特速率，这是因为该算法总是从最好C/I的用户开始调度，这些用户不需要消耗很大功率就可达到请求的速率。

但采用MAX C/I调度后，位于小区边缘的用户将可能得不到服务，由于没有考虑不同用户的公平性要求，该算法不被认可。通常把采用该算法得到的系统吞吐量看作系统吞吐量的上限。

2.3　正比公平调度

在调度决策中，如果每个用户获得调度的机会是公平的，这种调度算法称为公平机会调度算法。典型的公平机会调度算法是由Qualcomm公司提出的正比公平（proportional fairness，PF）调度算法，它在系统吞吐量和用户公平性间进行了折衷。

在PF算法中，每个用户被分配一个相应的优先级，任意时刻小区中优先级最大的用户接受服务。该优先级为：

（2）

这里(C/I)k(t)指第k个用户在t时刻的载干比，反映用户当前时刻所处的信道条件。用户根据当前的信道条件，向基站请求服务速率Rk(t)，式（2）可改写为：

（3）

式中Tk(t)指该用户在以t为结尾的时间窗口中的平均吞吐量。当用户进行连续通信时，Tk(t)逐渐变大，从而使得该用户的优先级变小。(C/I)k(t)可以进一步表示为(C/I)k(t)=，则用户优先级变为：

（4）

这里Pk和I分别是基站对第k个用户的发射功率以及对该用户的小区外干扰，而ak指无线信道损耗中来自慢衰落和路径损耗的慢变化部分，bk指无线信道损耗中来自快衰落的快变化部分。

由于Tk(t)和ak是慢变化的，在同一小区中不同用户的Pk近似相等，且将不同用户的bk看作是独立同分布的，那么在任意时刻同一个小区中的不同用户获取服务的概率是相等的。当用户获取服务时，它的快衰落状况必然是最好的。这样从长时间来看，小区内的用户占用趋于相同的时长进行通信，但由于服务时机的选择，用户只有在快衰落状况比较好的时候才获得服务，所以系统的吞吐量得以提高。

3、调度算法测试

为验证不同分组调度算法的实际性能，在国内某大城市的密集城区环境下做了HSDPA室外性能测试。测试过程中小区用户均匀分布，具体按照CPICH RSCP分别为-70 dBm、-80 dBm和-90 dBm区分近中远3点，每个点2个用户。在单小区（主测小区空载）情况下，HSDPA动态功率分配，以HSDPA码数分别配置为5/10/14个码作为变量参数，分别对3种调度算法进行测试，观察参数变化对调度算法实际性能的影响。

图1给出分别采用3种调度算法得到的小区中每个用户的吞吐率波动情况。测试显示出MAX C/I调度下各终端的下载速率较为分散，用户吞吐率对信号质量比较敏感，位于小区边缘的用户会得不到服务，这说明如果增加小区的用户数或者提高请求的比特速率，采用MAX C/I调度的需求覆盖范围将会缩小。RR算法各终端吞吐率较为接近，而PF算法介于两者之间。

图1 各终端不同场景下的吞吐率波动

3种调度算法的效率分析如图2，当用户均匀分布时，MAX C/I调度能提供最大的小区吞吐率，总吞吐率可以比RR或PF算法高出15%左右，效率最低的是RR，PF介于两者之间。

图2 各种调度算法的小区总吞吐量

从3种调度算法的公平性角度分析（如图3所示），RR调度下小区内不同位置的用户下载速率基本相当，最大吞吐率与平均吞吐率大体持平，最小吞吐率比较相近，为平均吞吐率的60%左右，因此公平性最好。单个用户最大/最小吞吐率与平均吞吐率之比的极值均出现在MAX C/I调度下，分别为大于4和等于0，即得到最好服务的用户速率为平均速率的4倍，而个别用户根本得不到服务，不同位置用户的吞吐率差异巨大，因此MAX C/I调度公平性最差。PF算法介于两者之间。

图3 各种调度算法的远、中、近3点下载速率对比

另外，测试人员又在有邻区（邻区加载75%）的情况进行了测试，结果显示与单小区相类似，且不同调度算法的性能特征更加明显。对于基站的总吞吐率，邻区加载75%并配置10个或14个码时，MAX C/I算法的总吞吐率可以达到RR算法的1.5～2倍。

4、结束语

由以上分析可以看出，MAX C/I算法下的系统吞吐量要远大于其他算法的吞吐量。因为该算法总是选择信道条件最好的用户来服务，为这些用户分配高阶调制方式和高编码率，因此系统的吞吐量最大，但由于完全不考虑用户间的公平性，因此是公平性最差的调度算法。而正比公平算法下小区中的不同用户获取服务的机会是均等的，但比MAX C/I算法得到的系统吞吐量要小，这是由正比公平算法修正了MAX C/I算法的公平性欠缺而得到的，作为公平性提升的代价，其系统吞吐量下降了15%左右。RR算法是公平算法，但得到的系统吞吐量最小，这是因为没有考虑不同用户无线信道的具体情况，总是为用户分配相同的资源，因此资源的整体利用率最低，且用户的QoS并不是完全公平分布的。

随着HSDPA的演进和OFDM、MIMO等技术的应用，分组调度算法将在更加有效利用无线资源，保证不同终端在接收同类业务的公平性方面得到不断提高。