HSxPA分组调度算法评析

摘　要：

摘　要：调度问题的根源在于对资源的竞争和分配，分组调度算法的优劣也直接影响HSxPA数据业务传输的性能。本文首先阐明HSxPA概念，接着厘清HSxPA中分组调度算法的几个种类，最后对几种主要的分组调度算法进行评析。

关键词：

关键词：HSxPA　分组调度算法　数据

1　HSxPA概述

     HSPA（High Speed Packet Access，HSPA）高速分组接入，其中x指D（Downlink）或U（Uplink）即下行或上行，HSxPA即指HSDPA和HSUPA。HSDPA是Node B（Node Base Station，Node B）基站到UE（User Equipment，UE）用户终端的下行链路上的分组数据的接入，HSUPA指UE到Node B的上行链路上的分组数据的传输。

     HSDPA为WCDMA（Wideband Code Division Multiple Access，WCDMA）宽带码分多址的R5版下行链路提供分组数据业务，传输速率可达8-10 Mbit/s，理论最大值可达14.4Mbps 。HSDPA主要采用自适应调制和编码（Adaptive Modulation Coding, AMC）、混合自动重传请求（Hybrid Automatic Repeat reQuest ，HARQ）、快速分组调度等技术。HSDPA中的调度功能主要是由NodeB中新增的MAC-hs功能实体完成的。

     HSUPA为WCDMAR6版的上行链路提供分组数据业务，传输速率最高可达到5.76Mbit/s。主要混合自动重传请求HARQ、快速分组调度及2ms短帧等技术，原有的分组调度功能是在RNC（Radio Network Control，RNC）无线网络控制器上实现的，现在转换到NodeB上。另外，E-E-DPDCH、E-DPCCH、E-AGCH、E-RGCH、E-HICH等五条信道和 MAC-e实体是HSUPA的新引入。NodeB中新增的MAC-e实体使HSUPA数据业务的快速调度成为可能。

2　分组调度算法的主要种类

     在HSxPA系统，分组调度算法直接决定分组数据业务的服务质量，它的任务是确定合理的调度规则，等待接受服务的多个UE按特定的规则排序，然后系统按这个排序进行调度，其中特定的规则就是分组调度所采用的算法。主要的分组调度算法有以下几类：轮循、最大载干比、比例公平、功率偏移计算及修正最大加权时延优先调度算法。

     轮循（Round Robin，RR），就是Node B轮流地为UE提供分组数据服务。RR算法严格计算每一个UE的调度概率，不会因为信道环境或数据块大小以及慢衰落等情况而改变它对公平机会的趋于绝对的追求。因此，在考察其他算法在公平性上的性能，通常想当然与RR算法进行比较。

     最大载干比（MAX-C/I），Node B先调度具有最佳信道条件的UE，不去考虑最先服务的UE的数据块大小，如果有剩余资源或该UE服务停止，才为信道条件稍差的UE提供服务。Node B总为具有最好下行信号质量的UE服务，所以HSxPA系统可以获得最大吞吐率。

　　最大功率偏移(MAX Power Offset ，PO)，PO指UE数据信道上可用功率与控制信道上功率的比值，需要说明的是，PO值的设置取决于小区的覆盖范围，小区的不同位置决定了Node B用不同的功率，原则上来讲，距离越远如小区边缘地带，PO值会越大，相反小区中心位置则不需要那么大的功率值。MAX PO法即选取具有最大功率偏移值的用户作为优先服务的对象。

     比例公平调度（Proportional Fair，PF），Node B调度具有最大公平因子的一个或多个终端，该算法的系统吞吐量和服务公平性在RR和MAX-C/I之间。

     修正最大加权时延优先(Modified Largest Weighted Delay First，M-LWDF)算法，其主要策略是将分组数据包时延和与其相关的无线信道的质量加入优先级排列中，其用户优先级主要考虑包的队列时延。

3　主要分组调度算法的评析

3.1　RR算法

　　RR算法对小区中的各个用户轮流进行调度，在某个时隙对一个用户进行调度，在下个时隙则调度另一个用户。如果有n个用户，那么每个用户接受服务的机会均等，概率都等于1/n，即系统可分配的资源公平地分配给每个UE。RR算法不考虑无线环境，即使无线环境差，系统也会为数据块大的UE服务，过于关注UE的公平性，系统及UE的吞吐率较低。

3.2　MAX-C/I算法

     效用函数(Utility Function，UF)的 “效用”用来衡量UE对系统提供的服务的满意程度，这是调度问题中比较普遍的优化方法，每一个UE都用效用函数来描述系统资源分配的效用值。效用函数的特性是，当系统分配的资源高于某一个阈值时，则UE的满意度会最高，当系统分配的资源低于某一个阈值时，其满意度几乎为零。

     Max C／I算法根据预服务的UE所接收信号的C/I的估计值进行排序，然后把这个排序作为优先调度的准则，进行分配无线资源。具有C／I最大值的用户将一直占用信道，不管传输数据块有多大，直到其数据块全部发送完毕，或者出现具有更大C／I值的用户才停止服务。具有较低的C／I值的用户只有选择等待。

     每个UE的效用函数为：Uj(Rj)= Rj，目标函数取为：，调度是为了追求目标函数的极值。显然这是一种贪婪的分组调度算法，如果在每个调度时刻都选择使得目标函数O增量最大的UE，那么最终得到的用户目标函数O就是最大的。

     Max C／I算法在每一个调度周期都会选择C／I值最大的UE，也就是说它首先要考虑的是保证系统吞吐量的最大化，而不是UE的公平机会，那么Max C／I算法至少是不够周全的。

3.3　MAXPO算法

     MAX PO算法的原理是在调度之前，先将调度用户列表中的用户按报告的PO的大小进行排序，然后再按顺序为表中的用户分配资源。Max PO算法虽然在公平性方面优于Max C／I算法，但调度中的所有用户，仍然采用“贪婪”原则进行资源分配。所谓的“贪婪”原则，即每选中一个被调度的UE，就尽量满足该UE的请求。在后面的仿真对比中，会利用Max PO算法与HSDPA 算法加以比较和分析。

3.4　PF算法

     在现有非实时性调度算法中，PF算法得到了广泛的应用，PF在每次调度判决之前，对每个用户的优先函数进行排列，对用户优先函数最高的业务进行调度。在任意时刻t用户i的优先函数Pi(t)的公式为：

        其中，表示用户i在时隙t时数据最大传输速率，是用户i的数据平均吞吐量。PF算法为了使用户长期获得公平的服务时间，并提高用户的吞吐量，一般认为系统所接收到的信噪比在时间上服从独立同分布，而且系统所接收到的信噪比和系统速率之间成线性关系。但是，PF算法对实时业务如视频和语音等并不适用。对于实时业务流，它们有着严格的时延限制，所以通常用分组丢弃率Pr表示其服务质量：

                                                            (3-2)

     其中，，Ti表示用户i的超时丢弃时间，Wi表示用户i的分组排队时间，di表示用户i的分组丢弃率的最大值。为将PF算法引入实时业务，对PF算法的优先级函数中加入了分组时延：

     其中，是设定的算法的等待时延的门限值，C是一个大于1的定值，由公式可见，

其分组丢弃率有所减少是因为分组时延大于的实时用户将得到更多的调度传输。但是，由于信道容量、分组长度、分组到达速率等会随着时间改变，算法的性能会受这样因素共同决定了其参数和C的取值，所以很难取得最佳的参数值同时满足非实时和实时用户的服务质量。

3.5　M-LWDF算法

     在支持实时业务的调度算法中，M-LWDF算法应用较多，其UE优先级的函数公式为：

      式3-4中，是用户的平均传输速率，此算法的优先函数兼顾了分组丢弃率和队首时延及用户信道条件，能够为用户提供比较高的服务质量。但该算法不能解决实时用户和非实时用户之间的资源分配问题，且不能对每个用户实际的吞吐量作出保证。因此，无法保证这两类用户获得服务的公平性。

4　结论

     综上所述，分组调度算法还存在着不足，从而影响HSxPA数据业务的传输性能，因此对分组调度算法的研究，主要目标应在保证不同用户Qos的前提下，力求在系统吞吐量及服务公平机会这两种主要性能上做到最大化。