OFDM系统分组调度算法仿真与分析

2012-10-27刘平，张成，车进

通信技术 2012年3期

关键词：轮询公平性吞吐量

刘平，张成，车进

（宁夏大学物理电气信息学院，宁夏银川 750021）

0 引言

随着通信需求的迅速增长，人们对下一代无线通信系统在频点、带宽、峰值速率、平均吞吐量、边缘用户吞吐量、时延以及兼容性等方面提出了许多新的要求[1]。

在无线通信系统中，单位范围内用户对通信速率需求的总和常常大于系统所能提供的接入速率。在这种无线资源广泛存在的“供需矛盾”情况下，必须对无线资源按照一定规则进行分配，实现这一功能的器件就是调度器，分配资源的规则叫做调度算法[2]。

1 分组调度算法及其关键指标

对下一代蜂窝系统的分组调度算法来说，所要完成的基本任务是根据各种复杂的情况来合理的进行资源分配。这种分配应该兼顾到不同带宽、不同时延、不同服务质量等级的用户需求，并且还应该考虑到单位区域内的系统总吞吐量和频率利用率。

为了对不同的分组调度算法进行定量的比较，需要选取系统中一些有代表性的参数作为依据。从本质上来说，分组调度算法是一种分配资源的规则。因此在调度算法的设计中，最重要的两个也是最需要平衡考虑的两个因素是算法的效率和公平性。效率的高低用吞吐量即一定范围内单位时间里传输的数据总量加以衡量。公平性则反映了系统为各个用户提供的接入机会。除了反映效率和公平的指标，在调度算法设计时还应考虑到算法的复杂程度和时延特性。其中算法的复杂度代表每次调度的时间代价并且决定算法的运行周期；时延特性则是一个重要的服务质量指标，对于实时性要求较高的业务来说，时延特性尤其需要考虑。

以上所提到的吞吐量、公平性、时延特性和算法复杂度是对分组调度算法进行对比评估的重要指标[3]。

2 OFDM系统下行链路分组调度算法

对于分组交换数据业务来说，分组调度的地位等同于信道资源分配在电路交换业务中的地位，分组调度在分组业务的无线资源管理中处于中心支配地位，很大程度上决定了整个无线分组业务系统所能提供的服务质量和效率，并在一定程度上影响着其他技术和算法的决策和执行。下一代蜂窝系统在物理层采用了OFDM作为调制技术，对于采用了OFDM技术的系统而言，调度算法所分配的系统基本资源是一个时频块（TFU）。位于媒体接入控制（MAC）层的调度器在工作时必须有业务需求、资源信息等来自物理层的信息支持，既调度器应进行跨层设计。同时，好的调度算法应该兼顾吞吐量、公平性，算法复杂度和时延特性，根据算法的特点，基本调度算法主要有以下几种[4-7]。

2.1 轮询调度算法

轮询(Round Robin RR)算法的基本原则是使小区内的所有用户以确定的顺序循环占用均等时长的无线资源，该算法认为所有的用户在优先级上是平等的。在任何一个时刻，每个申请用户能够获得资源的概率完全相同，通过这种方式来保证算法的公平性。轮询调度算法的优点之一是实现简单，算法复杂度低。此外，由于轮询算法赋予所有用户以相同的优先级，为每个用户提供了相同的接入概率，因此被认为是最公平的，其算法结果常常作为公平性的上限。与之相对应的是，由于系统中与每个用户信道质量有关的信息没有被轮询调度算法所利用，进而使得系统资源浪费，总吞吐量不高。

2.2 公平吞吐量算法

与轮询调度算法类似，公平吞吐量(Max-Min)算法的主要关注点也放在了系统公平性的实现上。它与轮询算法的不同之处在于，轮询算法是以确定顺序使所有用户循环占用等时长的资源，追求实现用户时间上的公平性；公平吞吐量算法追求实现的是不同用户之间吞吐量上的均衡，并不确保每个用户得到的时长资源相同。该调度算法的优先级计算公式为：

2.3 最大载干比调度算法

最大载干比(Max C/I,Maximum Carrier Interference)算法是一种优先考虑效率的调度算法。其基本思想是在进行无线资源分配时，始终优先满足当前时刻信道质量最好的用户所提出的请求。在该算法中，如果在t时刻有K个用户请求传输数据，则被选中的用户为:

显然，假设某一用户的C/I最高，则该用户的优先级也最高。由于采用效率优先的算法设计思想，既资源优先分配给信道条件最好的用户，所以这种算法活动的吞吐量是系统吞吐量的极大值，通常被作为吞吐量的上界。以最高效率为代价的是，由于最大载干比算法只为信道条件最优的用户分配资源，对于信道条件差的用户来说无法得到服务机会继而出现“饥饿效应”，因此该算法的公平性有待改进。

2.4 比例公平调度算法

与前 3种算法不同，比例公平算法(PF，Proportional Fair)是一种兼顾公平性和系统吞吐量的调度算法，在比例公平调度算法中，用户当前时刻的信道质量和之前一段时间的传输速率被同时考虑作为资源分配的依据。由此比例公平算法在公平和效率直接取到一定程度的折中，成为目前被广泛采用的一种算法。其优先级公式为：

其中n是TTI索引，DRCk,m(n) 是第k个用户在第m个子载波（或者子信道）要求的速率，Rk(n)是用户k在n个TTI中已经获得的速率，α和β是调节公平性的系数，通常取α=β=1。Rk(n)的更新方程为：

3 仿真及结果分析

为了检验不同的调度算法的性能，需要在不同的带宽条件以及业务模式下对系统进行仿真。参照参考文献[8]技术标准设定（表1）；同时仿真前面所提到的 4种调度算法: 轮询(RR，Round Robin)算法、最大载干比(Max C/I，Maximum Carrier Interference)算法，公平吞吐量(Max-Min)算法以及比例公平算法(PF，Proportional Fair)。为了定量的表述不同算法的公平性，这里选用公平指数β作为公平性的测量标准。其定义为：M为系统中的总用户数，Bi为分配给i用户的带宽。β→ 1，说明公平性好；反之说明公平性差。

表1 仿真参数

图1、图2为4种基本调度算法的仿真结果图。

图1反映的是在不同调度算法情况下，单位小区用户数与系统吞吐量之间的关系。从中可以看出，由于Max C/I算法在设计时以效率为优先考虑对象，尽量满足信道条件好的用户对系统资源的需求，故而实现了系统吞吐量的最大化，其系统吞吐量可以作为吞吐量的上限来对其他算法加以衡量；Max-Min(公平吞吐量)算法则首先考虑公平性，优先保证了传输速率较低的用户，然而由于其过于追求流量公平，忽视了用户速率和信道质量的差异，当系统中用户到达速率差异过大时，会对高速率用户带来过多的限制而以此为代价换来的低速率用户吞吐量的提升又不明显，会导致系统总吞吐量降低。对于RR算法来说，没有利用信道信息，系统吞吐量最低。PF算法其吞吐量非常接近Max C/I算法的吞吐量，在系统吞吐量方面具有一定的优势。

图2反映的是在不同调度算法情况下，单位小区用户数与公平指数之间的关系。从中可以看出，RR算法由于为每个用户提供了相同的接入概率和等时长的资源，其结果是公平性的上界。Max C/I算法优先考虑系统吞吐量的最大化，其公平性最差。Max-Min算法在用户数规模较小的情况下，公平性较好，然而随着用户数的增加，不可避免地造成用户间传输速率差值的增大，该算法只能过多地牺牲较高速率用户以此来为较低速率的用户提供更多的资源分配机会，最终造成系统公平性下降。对PF算法来说，由于同时考虑了用户当前时刻的信道质量和之前一段时间的传输速率，固其公平性介于 Max C/I算法和RR算法之间。