3G系统中的分组调度算法

摘　要　无线分组调度算法的功能是为无线用户的各种分组业务合理分配无线资源，在满足用户间公平性前提下有效提高移动信道利用率和服务质量（QoS）。本文介绍并比较了3G系统的三类经典分组调度算法，分析了新一代无线通信系统中分组调度算法所面临的问题。

关键词　分组调度算法　轮循调度　最大载干比调度　比例公平调度

1　前言

无线通信系统是资源受限的，如何利用有限的系统资源满足日益增长的用户需求，已经成为移动通信系统制造商和运营商亟需解决的问题。没有有效的无线资源管理策略，再先进的传输技术也会因受到资源的限制而不可能充分发挥其优势。作为一项关键技术，无线资源管理已经成为衡量一个移动通信系统体制是否可行、系统服务质量优劣的准则。无线资源管理主要包括切换控制、功率控制、接入控制、负荷控制以及分组调度等方面的内容。

无线资源管理是3G系统无线网络控制器（RNC）的重要组成部分，其主要作用是负责空中接口资源的分配和使用，确保用户业务的服务质量、系统规划的覆盖区域以及提高系统容量。在3G的演进过程中，标准化组织3GPP和 3GPP2也在不断完善和增强相关技术。对于分组调度算法，一方面要考虑到算法实现的复杂度，另一方面需要注意对系统性能指标的影响，如公平性、时延、业务的服务质量（QoS）等。目前采用比较多的调度算法主要有轮循调度、最大载干比调度、比例公平调度三种类型。本文主要在介绍它们的基本工作原理以及它们的改进型调度算法并进行比较。

2　3G系统中的无线分组调度算法

在分组通信中，为了获得统计复用增益，需要多个业务流共享带宽。因此，当多个用户争用资源时，就需要有一种机制来确定服务次序，有效地分配无线资源，这就是分组调度。由于无线信道时变特性、带宽资源有限和移动台功率受限等因素的影响，无线网络中的分组调度算法有别于有线网络。

图1描述了无线分组调度机制的基本原理。调度器首先根据信道状态监视/预测模块提供的信道信息和用户的队列状态，依据一定的调度算法，计算出每个用户的优先级，然后根据优先级对用户数据排队，并分配无线资源，最后送到发射机。

2.1　轮循调度算法

轮循调度算法（RR）假设所有用户具有相同的优先级，保证以相等的机会为系统中所有用户分配相同数量的资源，使用户按照某种确定的顺序占用无线资源进行通信。其主要思想是，以牺牲吞吐量为代价，公平地为系统内的每个用户提供资源。由于RR算法不考虑不同用户无线信道的具体情况，虽然保证了用户时间公平性，但吞吐量是极低的。通常RR调度算法的结果被作为时间公平性的上界。为了改善RR算法的时延特性、无线信道自适应特性及其在变长分组环境下的公平性，由它产生了一系列改进型算法，如机会差额轮循（ODRR）、无线差额轮循（WDRR）等。ODDR算法对于用户i引入了定值计数器Qi和变值计数器DCi，当轮循道用户i时，DCi＝DCi+Qi。每次轮循发送的数据量p不超过DCi，并更新DCi，令DCi = DCi- PenaltyFactor·Size（p）。其中PenaltyFactor是根据无线信道状况调整的参数，例如可以定义为理想传输速率与实际传输速率之比或每单位功耗的理想传输比特数与实际传输比特数之比，这样就使得信道状况好的用户可以传输更多的数据。WDDR在某些方面和ODDR类似，在每个轮循周期内它将每个用户的数据分成更小的子块，依次发送每个用户的序号最小的子块，当用户i不存在第j个子块时则跳过，继续发送用户i+1的第j个子块。总之，它们都尽量保持RR算法实现简单的特点，同时又努力提高吞吐量。

2.2　最大载干比调度算法

最大载干比（max C/I）调度算法保证具有最好链路条件的用户获得最高的优先级：

无线信道状态好的用户优先级高，使得数据正确传输的几率增加，错误重传的次数减少，整个系统的吞吐量得到了提升。显然，精确的信道预测算法则会带来更高的增益。

虽然max C/I能够适应无线信道的时变性，但是完全不考虑用户间的公平性。为了保证每个用户达到最低吞吐量，同时对于信道条件好的用户的吞吐量也有一定限制，文献[1]提出了速率受限最大载干比调度算法。其主要思想是设定速率门限值，限制高传输速率用户的传输机会，补偿速率较低的用户。若设传输速率的上限为Rth_max，下限为Rth_min。当用户平均速率大于Rth_max时，用户优先级设为最低（值为0），而用户平均速率小于Rth_min时，该用户享有最高优先级（值为∞）。

......
......
......

2.4　三种主要分组调度算法的比较

RR和max C/I算法实现简单，分别考虑的是时间公平性和最大吞吐量两种极限情况下的系统性能，其主要用作评估其他调度算法性能的参考，而在实际系统并不采用。表1主要对三种基本调度算法进行了简单比较。

RR算法的优点是从资源占用的角度保证了用户间的公平性，缺点是不考虑用户间的信道差异，不利于改善系统吞吐量。max C/I算法完全根据时变的信道状况进行用户调度，可以最大限度的提高频谱利用率，缺点是用户间的公平性无法得到保证。由于信道的阴影效应、多径衰落的影响，有时处于小区半径中间地区的移动台的C/I也可能会高于离基站较近的移动台，但是位于小区边缘的移动台由于路径损耗大，可能在很长的时间内都得不到系统服务。另外，RR算法和max C/I算法在进行资源调度时，都不考虑以前的调度状况，因此是无记忆的。PF调度算法综合考虑了用户的信道条件差异和对于公平性的要求，是对吞吐量和公平性的折中，同样适用于高速下行分组接入（HSDPA）等各种无线通信系统。PF调度算法是目前公认比较好的调度算法，但它是以提高算法复杂度为代价的。

3　未来分组调度算法发展趋势

随着无线数据业务的普及和多媒体应用需求的增长，未来的无线通信网络将为多种业务类型提供接入服务，同时用户对于QoS的要求也越来越高。网络中的用户将不受时间、地点网络类型的限制，根据业务类型和接入成本自定义服务等级，因此分组调度算法必须引入QoS的区分和确保机制。但是现有的算法均没有考虑到实际系统中多业务QoS要求，只适用于单业务的传输。因此，为了满足多业务混合传输，提供QoS确保机制也是今后算法改进需要关注的一个主要方面。此外，传统无线资源管理算法的功能是比较清晰和独立的，各种算法在完成自己的功能外，很少和其他无线资源管理算法进行交互。但是在未来无线通信系统中，要求无线资源管理算法进行综合设计，充分考虑各个功能块之间的相互联系和影响，以适应物理信道和业务需求的变化。

另一方面，为了使移动用户峰值传输速率比3G系统提高1~2个数量级，新一代无线通信系统空中接口的物理层将采用多输入多输出（MIMO）、正交频分复用（OFDM）、混合自动重传请求（HARQ）、自适应调制编码技术（AMC）等无线增强新技术，这给无线资源管理带来了新的机遇和挑战。例如，当系统采用AMC时，max C/I算法可使系统获得最高的吞吐量。OFDM技术会使得无线资源呈时频二维结构——在时间上将无线资源划分为多个时隙，每个时隙由多个OFDM符号组成，在频率上将无线资源划分为多个子信道。OFDM系统的调度算法不仅要考虑用户间的服务次序，更重要的是考虑在同时进行分组传输的用户间如何合理配置时隙与子载波资源。同一时隙下同一用户的数据不仅可以分布在不同的子载波上，还可以分布在不同OFDM符号内。而MIMO又引入了可供分配的空间域资源。因此，新一代的无线调度策略需要考虑包括时域、频域、空间域在内的多维无线资源的合理调配，使无线资源的使用能够适应于业务承载要求和无线信道质量的变化，以较低的无线分组调度算法获得较高的频谱利用率和较好的用户公平性，最大限度的共享无线资源。

4　总结

本文主要阐述了三类主流的无线分组调度算法，分析了未来无线通信技术引进OFDM、MIMO新技术对于无线分组调度算法的影响。无论是简单RR算法、能够动态跟踪信道信息的max C/I算法、综合考虑性能与复杂度的PF算法，还是未来无线通信系统引进新技术后的改进的分组调度算法，其主要思想都是结合系统可用的无线资源、信道状况、业务的QoS需求等因素确定用户优先级顺序，然后依据排队结果分配无线资源，发送分组数据，尽可能地使系统的吞吐量获得较大的改善，并使用户公平地共享无线频谱资源，保证业务的QoS。

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