OFDMA系统用户调度算法的比较研究
摘要:OFDMA系统的资源调度是解决多个业务竞争共享资源问题及提高系统容量的一种有效方法。
本文基于OFDMA系统下行链路，针对支持非实时业务的三种经典分组调度算法进行了对比研究，仿真了系统总吞吐量和算法公平性，仿真结果表明，与轮询调度、最大载干比调度相比之下，比例公平调度算法实现了系统吞吐量和公平性的良好折中，具有明显的优越性。
最后指出资源调度算法的改进方向。
关键词:OFDMA；资源调度；吞吐量；公平性
Comparative study of users scheduling algorithm in OFDMA system
Abstract：The resource scheduling in the system of OFDMA can solve the problem in competition among multi-service when resource be shared and a effective method on improving the system throughput. This paper based on the down-link in the OFDMA system, aiming at studying three classic packet scheduling algorithms which supported Non-Real-Time(NRT) sevices and make comparative study. Simulated the system total throughput and fairness, the results show that, comparing with RR scheduling and Max C/I scheduling , the PF scheduling algorithm get a excellent compromise between throughput and fairness, more comparable than the two other. The improved direction of resource scheduling is given finally.
Key words:OFDMA; resource scheduling; throughput; fairness
正交频分多址(Orthogonal Frequency Division Multiple Access，OFDMA) 为多载波无线通信系统，其多载波之间相互正交重叠，极大提高了频谱资源利用率,在一定程度上解决了未来频谱资源紧张的
问题,在无线通信领域，由于无线资源（如频谱）是及其有限的，而用户的需求是相对无限的，研究资源调度算法对提高无线资源的利用率有重要意义。
本文对比研究了三种经典的无线分组调度算法，有助于继续深入研究改进的调度算法，对提高系统的吞吐量和用户的稳定性具有重要的作用。
1、系统概述与无线分组调度
由于基站更容易对下行传输做统一调度。
假设在OFDMA系统下行链路中，一个小区有k个用户等待调度并分配子载波（子载波数为N），调度器中有基站下行链路排队状态的全部信息，同时信道检测器能完全监测并反馈用户信道信息给调度器。
每个时隙开
始的时刻，调度器根据信道状态，通过预设算法准则，选择符合条件的用户发送数据。
无线资源调度是为了合理分配无线资源给用户，最大限度的满足用户的通信需求；它的最重要的两个目标就是最大化系统的容量和给每个用户提供公平的接入信道的机会。
调度问题的根源在于对资源的争用和分配。
目前经典的分组调度算法有轮询调度（Round-Robin ，RR）[1-2]，最大载干比调度（Max C/I）[3]和比例公平调度（Proportional Fair ，PF）[5]。
无线分组调度模型如图1所示。
图1 无线分组调度模型
分组调度算法基本遵循这样的方式，即从多个队列Q i ，0<i<=N 中选择一个符合某个规则c 的队列Q j 进行服务（分组发送），即从系统中找出一个关系（c ，j ），其中j 为队列编号，寻找关系（c ，j ）的基本方法有两种：
1、先确定j ，即假设下一个要服务的队列Q j ,然后判断该队列是否满足条件c 。
这种方式称作基于轮询的方法。
例如RR 调度。
2、通过比较判断条件c 来确定j 。
按照条件c 的要求为每个队列动态的计算一个优先级Pri ，每次调度最大或最小的Pri 值的队列。
这种方法称作基于优先级的方法。
例如Max C/I 和PF 调度。
2、算法描述
2.1 轮询调度
轮询（Round-Robin ）调度，是一种公平轮询的调度机制，所有用户按顺序依次被调度，公平的分配时隙与子载波；每个用户的传输概率都为1/K （K 为用户数）。
RR 与用户信道条件无关，从占用资源的角度来说，这种调度算法是最公平的。
RR 调度经常作为算法公平性衡量的准则。
2.2 最大载干比调度
载干比（C/I ）也称干扰保护比，是指接收到的有用信号电平与非有用电平的比值。
它反映信号在空间传播过程中，接收端的接收信号的好坏，也即反映出信噪比的好坏。
最大载干比（Max C/I ）调度算法每次调度都选取信道条件最好的用户发送数据，因信噪比直接影响信道容量。
因此，对于N 个在队列中缓存的分组，在等待系统调用，算法选择优先权最大的用户进行数据传输。
1arg max{()}i i K
K t μ*
≤≤= (1)
其中，()i t μ为当前用户信道支持的速率，用()i t μ近似作为C/I 预测值。
调度器对所有等待服务的移动台依据自己接收信号的C/I 预测值进行排序，并按照从大到小的顺序进行发送。
这种调度方式下，具有最高C/I 值的分组将占用信道进行发送，直到其队列清空。
该算法可以使系统得到最大的系统容量，但它不能保证各用户之间的公平性，对于小区边缘信道条件差的用户将很难得到发送机会，信噪比低的用户严重时甚至出现“饿死”。
Max C/I 是一种容量最大化算法[4]
，调度总体思想：调度器在时隙t 的开始时刻对K×N 的最大可达速
率矩阵进行全搜索，找到最大的,()i n t μ的值，将该子载波分配给用户K *，再将这个子载波从可分配的子载波集合中删除;对剩下的K×(N-1)的最大可达速率矩阵进行全搜索，反复进行下去直到N 个子载波都被分配完毕。
这种方法可以达到吞吐量的上界。
2.3 比例公共调度
多用户分集系统中，调度器对保证用户公平性和增大系统吞吐量有重要作用，为了使小区的吞吐量最大化，一般的调度算法通常使能支持的最高数据速率的用户具有最高的的调度优先级如（Max C/I 等）。
由上面两种调度算法，RR 调度只考虑用户的公平，而忽视用户信道条件，这样得到的系统吞吐量不佳，浪费资源；Max C/I 调度总是调度信道最佳的用户传输数据，这样得到的系统吞吐量势必最大，却忽视了用户之间的公平性。
基于这两种算法的优缺点，提出了比例公平算法。
PF 调度器就是针对上两种调度器的一种替代改进算法，它是一种半公平性的调度。
调度器试图利用信道实时的变化情况，尽可能在一个用户的信道质量相对最好的时候对它进行调度，充分利用信道的实变性。
比例公平（Proportional Fair ）调度算法的基本调度策略是在每次调度时选择相对信道条件最好的用户进行传输。
该算法的调度判决表达式为
1arg max{()/()}i i i M
K t T t μ*
≤≤= (2)
其中()i t μ是用户i 在时隙t 时刻当前所能支持的速率，算法通过追踪用户i 在以时刻t 为结尾的时间窗T C 上的平均速率T i (t)，求得以上比值。
在时刻t 选择K *用户传输数据。
T i (t)通常由如下的指数平滑过程进行实时更新：
(11/)(1)()/(11/)(1) ()c
i
i
c
c
i
i T T t R t T i K T T t i K
T t *
*
--+=--≠⎧⎪=⎨
⎪⎩ (3)
其中，c T 是这个平滑过程的时间常数，根据需要设定(单位：时隙)。
通过以上规则，系统调用用户传输数据不仅与用户能提供的瞬时传输速率有关而且与用户过去时间t 内传输的平均吞吐量有关，显然，在覆盖多个用户的系统中，一个用户不可能总是进行通信。
如果用户连续进行通信时，分子T i (t)逐渐增大，而使得该用户的优先级变小。
如果用户i 在很长时间内未被调度，这样它将获得调度特权。
因此，PF 不仅使用户间得到公
平性服务而且兼顾了系统的总吞吐量的提高，能够在传输有效性和服务公平性之间获得较好的折衷性能。
3、公平性
算法的公平性是服务质量（Quality of Service ，QoS ）衡量的重要标准。
无线网络实现公平性比较复杂，在信道条件较差的情况下，根据业务要求或公平准则要求, 数据包常被丢弃，这样导致无线信道资源的浪费。
为了保证无线通信系统的公平调度，计算公平因子对衡量一个算法的质量尤为重要。
仿真中公平性因子定义为：
ax()in()
()
i i i m m F mean μμμ-=
（4）
式中ax()i
m μ为所有用户的最大速率，in()i
m μ为所
有用户的最小速率，()i
mean μ为所有用户的平均速率。
有式可见，Max C/I 算法总是调度小区用户中最大的
()i t μ，存在用户分配不到资源，则F 值最大，按顺序依
次轮询调度最公平，F 值最小，PF 折中，位于两者之间，后面仿真将得到验证。
4、对比仿真
仿真工具为matlab [6]。
仿真参数如下表1，每时隙持续时间1ms ，仿真环境为圆形小区，用户随机均匀的分布。
用户队列假设为infinitely Backlogged Queues 。
信道条件包括大尺度和小尺度衰落，其中Rayleigh 衰落用Jakes 模型[7]
表1 仿真参数
图2 30个用户吞吐量随时间变化
图2 为小区中30个用户吞吐量随时间变化的趋势，由图可见，Max C/I 的系统吞吐量最好，PF 其次，RR 最差。
图3 系统吞吐量随用户数变化
图3为小区用户数的增加，系统吞吐量的变化。
可以看出在用户增加的过程中，Max C/I 算法增加幅度最大，说明用户数最多，越能体现Max C/I 算法在提高系统吞吐量方面的优势，而PF 和RR 增加不明显，因为二者会更多的考虑用户公平性，尤属RR 。
图4为3种算法下随机选取4个用户的的吞吐量情况，RR 中资源公平分配，Max C/I 中则取条件最好的用户服务，用户3、4出现“饿死”，PF 中则选择相对 信道条件最好的用户进行传输，用户容量呈现比例性。
图4各算法下各用户归一化的吞吐量
图5 公平因子
图5为图4下统计的3种算法随机取4个用户的公平性因子比较，从图5可见，RR调度获得最佳的公平性，Max C/I完全忽视用户公平，其公平性最差，PF 公平性良好。
综合上下图Max C/I调度是以牺牲用户公平性为代价获得很好系统吞吐量。
5、结语
研究了OFDMA系统下行链路的支持非实时业务的三种经典分组调度算法，对比分析它们之间性能。
由仿真验证，PF算法更好的完成了OFDMA系统以提高系统吞吐量和用户公平性的目标，在系统吞吐量和用户公平性实现了最佳的折中；本文PF对吞吐量的提高还有欠缺，各种改进的PF公平算法是未来发展的方向，今后在此处将做进一步研究。
参考文献
[1.]Ameigeiras P, Wigard J, Mogensen P. Performance of
packet sheduling methods with different degree of fairness in HSDPA[J]. IEEE Transaction on Wireless
Communication, 2004, (02): 860-861.
[2.]高小林, 基于HSDPA的分组调度算法研究[D]. 硕士.
哈尔滨工业大学, 2006.
[3.]Li-Chun Wang, Wei-Jun Lin. Throughput and fairness
enhancement for OFDMA boradband wireless acess system using the maxium C/I scheduling[J]. IEEE Transaction on Wireless Communication, 2005, (7): 4696-4700.
[4.]阳洁. 基于IEEE802.16的QoS技术研究[D]. 硕士. 浙
江大学, 2005.
[5.]Horvath G, Budapest C. Throughput analysis of the
proportional fair scheduler in HSDPA. IEEE wireless conference, 2008, (1):1-6.
[6.]马莉. MA TLAB语言实用教程[M]. 北京：清华大学出版
社.2010.
[7.]David Tse, Pramod Viswanath. 无线通信基础[M]. 北京:
人民邮电出版社, 2007.。
