中国科技论文在线
http://www.paper.edu.cn
刘晓宁
北京邮电大学信息与通信工程学院，北京 (100876)
E-mail ：[email protected]
摘 要：本文通过研究LTE 上行调度算法，提出了几种改进的调度算法，该算法在系统吞吐量及用户公平性上各有改进。LTE 上行调度与下行调度的不同之处在于同一时刻分配各某个用户的所有RB 必须是频域连续的。在下行中采用最多的调度算法就是比例公平（PF, proportional fair）算法。本文研究基于这种准则下PF 调度算法在LTE 上行中的应用。本文研究资源块分组的思想，并研究改进的PF 度量值在上行调度的应用，由此提出了几种改进的PF 上行调度算法。本文通过仿真给出了几种不同调度算法的性能，并加以比较，分析各自的优缺点。
关键词：SC-FDMA LTE 上行调度 比例公平 公平性指数 中图分类号：TN929.53
1．引言
OFDMA 作为LTE 下行无线接入的技术，具有抗多径衰落、频谱效率高的优点。但是OFDMA 的一个主要的缺点就是一个OFDM 符号上的瞬时发射功率的变化非常大，这样会导致非常高的峰均比（PAPR ）。在LTE 上行链路中高峰均比是一个非常严重的问题，因为手机的发射功率是上行需要考虑的主要问题。为了寻找OFDMA 的替换，SC-FDMA 被选为LTE 上行的多址访问方案。
SC-FDMA 是单波载（Single-carrier ），与OFDMA 相比之下具有的较低的PAPR （峰值/平均功率比，peak-to-average power ratio），比多载波的PAPR 低1-3dB 左右（PAPR 是由于多载波在频域叠加引起）。更低的PAPR 可以使移动终端在发送功效方面得到更大的好处，并进而延长电池使用时间。SC-FDMA 具有单载波的低PAPR 和多载波的强韧性的两大优势。因此，LTE 上行多址访问技术采用了SC-FDMA 。
在LTE 上行中，系统带宽被分为多个子频带，即多个子载波组。这些子频带被成为RB （physical resource block）。为了在多用户频率分集中得到好的性能，调度器必须知道各个用户在各个RB 上的瞬时的无线信道情况。这些要作为调度的输入值。
在每个调度时刻, 缓存有数据的UE 会在全频带向基站发送参考信号SRS （sounding reference signal）, 基站会测量各UE 在各个RB 的信道质量指示CQI （channel quality indicator ）。而CQI 是由SINR 决定的。SINR 的值为参考信号的功率与当前干扰及噪声功率之比。基站以此为依据根据不同的调度算法，发送调度信息。从而决定UE 在哪些RB 上传输。
在下行中采用最多的调度算法就是比例公平（PF, proportional fair）算法。它是把各个RB 相互独立的逐个分配给用户。PF 算法兼顾了公平性和有效性，可以使系统达到一个较好的性能。但是PF 算法并不能直接运用到SC-FDMA 中，由于SC-FDMA 的单载波的特性，SC-FDMA 需要在同一时刻分配各某个用户的所有RB 必须是频域连续的。所以LTE 上行调度必须要遵守这个条件[1]。
在这篇论文中，我们研究了PF 算法在SC-FDMA 中的应用。我们提出了几种不同的PF
- 1 -
2．调度算法
2.1 公平性指数（FI ）
在无线通信系统中进行资源分配时，如果我们给用户提供相等的服务机会，如Round Robin 算法，将使得处于较好信道状态下的用户获得较多的数据传输量，而较差信道条件下的用户获得较少的数据传输量；如果我们希望用户们获得相等的数据传输量，则要给处于较差的信道状态的用户提供更多的服务机会。显然，两种方法都存在不公平的问题，那么我们就需要一种标准来衡量用户间资源分配的公平性。在传统的有线通信网络中，公平性的衡量理论已经过讨论研究，三种衡量公平性的方法已经广泛应用于不同的资源分配过程中。我们采用其中的一种作为衡量PF 算法公平性的指标，这就是Jain Fairness[2]。
n
Jain fairness index I Jain =
|∑x i |2n ∑x i 2
i =1i =1
n
其中n 表示用户数，x i 表示用户i 已分配的资源总数。
Jain FI 的取值越高，我们认为分配越公平，也就是说，用户获得的资源越平均则分配越公平[3]。
2.2 PF调度算法
我们考虑一个上行带宽被分为M 个RB 的蜂窝网络，每个基站下有N 个用户。采用PF 调度算法对各用户进行调度。 2.2.1 传统算法Alg1
将传统比例公平调度算法应用到SC-FDMA 中，并且遵守资源块连续的原则[1]。PF 度量值为λi c (t ) =r i c (t ) /R i (t ) ，表示在时隙t 时用户i 在RB 号为c 的RB 上的度量值。r i c (t ) 表示用户i 在c 号RB 上的当前可被分配的速率。速率的计算是由CQI 来决定的，而CQI 的值则是由参考信号在此RB 上的信噪比决定的。R i (t ) 表示用户i 的平均传输速率。
分配算法为：
令U 为可调度的用户的集合，A [M ]为RB 分给用户的状态。对RB 从1到m 循环：选取最大的PF 度量值λi ，其中i ∈U 。如果A [c ]=0，则把RB c分配给用户i ，即A [c ]=i ，
c
U =U −{i }。直到循环结束。
2.2.2 分组算法Alg2
为了使所有的资源块能分配给用户，且用户所分配到得资源块都是连续的。我们采用资源块分组的方式来达到这种要求。先将所有的RB 进行分组，将M 个RB 分为N 组，其中N 为扇区中的用户数。每组中的RB 数为M/N，这些RB 捆绑在一起，一起被分配。
PF 度量值为λi c (t ) =r i c (t ) /R i (t ) ，表示在时隙t 时用户i 在RB 号为c 的RB （组）上的度量值。r i c (t ) 表示用户i 在c 号RB （组）上的当前可被分配的速率。速率的计算是由CQI
- 2 -
的平均传输速率。
分配算法为：
1. 对 λi c 按照从大到小的顺序进行排序，保存到集合V 2. 设集合S 为尚未被分配的RB 组集合 3. 令k =1
4.while （V 不等于空）&（k
4.1 选取PF 度量值大小排序为k th 的RB 组 λi ∈V ，c ∈S 4.2 令I 为已分配给用户i 的RB 组集合 4.3.1 if(c 与I 相邻) or(I =φ) then 4.3.1.1 将RB 组分配给用户i
4.3.1.2 S =S −{c };V =V −{λi };k =1 4.3.2 else k =k +1 4.3.3 endif 4 end while 2.2.3 分组算法Alg3
c
c
R i (t ) 表示用户i
为了能使系统吞吐量及公平性得到更好的提升，我们提出了改进的PF 因子。改进的PF 度量值为：λ(t ) =r i (t ) /{R i (t ) +
j
c i
c
∑ρ
j =1
M
j i (t ) r i j (t )}
其中ρi (t ) 表示当前TTI 资源块j 是否分给用户i ，取值为0或1。
我们将此度量值应用到Alg2，而且需要每当有新RB 组被分配，重新计算PF 度量值。
分配算法为：
1. 对 λi c 按照从大到小的顺序进行排序，保存到集合V 2. 设集合S 为尚未被分配的RB 组集合 3. 令k =1
4.while （V 不等于空）&（k
4.2对V 从大到小排序，选取PF 度量值大小排序为k th 的RB 组 λi c ∈V ，c ∈S 4.3 令I 为已分配给用户i 的RB 组集合 4.4.1 if(c 与I 相邻) or(I =φ) then 4.4.1.1 将RB 组分配给用户i
4.4.1.2 S =S −{c };V =V −{λi c };k =1 4.4.2 else k =k +1 4.4.3 endif 4 end while 2.2.4 算法Alg4
按照PF 度量值由大到小为用户分配RB ，提前是分配的RB 必须连续。不满足条件的
- 3 -
目的：让所有的RB 都按照PF 算法分配给各用户，并且满足RB 连续的条件。
分配算法为：
1. 对 λi c 按照从大到小的顺序进行排序，保存到集合V 2. 令k =1
3.while V不等于空 do
3.1 选取PF 度量值大小排序为k th 的RB 组 λi c ∈V 3.2 令I 为已分配给用户i 的RB 组集合 3.3.1 if(c 与I 相邻) or(I =φ) then 3.3.1.1 将RB 组分配给用户i 3.3.1.2 V =V −{λi c };k =1 3.3.2 else k =k +1 3.3.3 endif 3 end while 2.2.5 算法Alg5
将新PF 度量值运用到前一个算法Alg4中。 PF 度量值为：λ(t ) =r i (t ) /{R i (t ) +
c i
c
M
∑ρ
j =1
j i (t ) r i j (t )} 其中ρi j (t ) 表示当前TTI 资源块
j 是否分给用户i ，取值为0或1。
分配算法为：
1. 对 λi c 按照从大到小的顺序进行排序，保存到集合V 2. 令k =1
3.while V不等于空 do
3.1每当有新RB 组被分配，更新PF 度量值
3.2对V 从大到小排序，选取PF 度量值大小排序为k th 的RB 组 λi c ∈V 3.3 令I 为已分配给用户i 的RB 组集合 3.4.1 if(c 与I 相邻) or(I =φ) then 3.4.1.1 将RB 组分配给用户i 3.4.1.2 V =V −{λi c };k =1 3.4.2 else k =k +1 3.4.3 endif 3 end while
3．仿真结果及分析
- 4 -
S y s t e m t h r o u g h p u t [M b p s ]
Number of active users in cell
图1 系统吞吐量图
0.900.850.80
F a i r n e s s [t =10m s ]
0.750.700.650.600.550.500.450.40
Number of active users in cell
图2 公平性因子图
在仿真中系统带宽为20MHz ，每个RB 所占用的子载波数为12，仿真结果见图1图2。其中图1为各种调度算法的系统吞吐量，图2各种算法的公平性因子图。为从图1和图2中可以看出Alg1的吞吐量最低，因为它无法保证所有的资源块都被分配。在用户数较少的时候，即平均每个用户可分配的资源块较多时Alg2的吞吐量略小于Alg4，但是当用户数增多的时候，Alg2的吞吐量会略大一些，但同时公平性则会较小些。采用新PF 度量值的Alg3在吞吐量及公平性上都比Alg2要好一些。这说明新的PF 度量值可以改进系统的吞吐量及公平性。采用新PF 度量值的Alg5在用户数较少的时候比Alg4的吞吐量要高一些，但是用户数增多的时候，它的吞吐量会比Alg4低一些，但是在公平性上好于Alg4。
4．总结
- 5 -
参考文献
[1] Suk-Bok Lee, Ioannis Pefkianakis, Adam Meyerson, et al．Proportional Fair Frequency-Domain Packet
Scheduling for 3GPP LTE Uplink [R] IEEE INFOCOM 2009 mini-symposium
[2] A.Kumar, J.Kleinberg．Fairness Measures for Resource Allocation [J] IEEE Symposium on
Foundation of Computer Science, 2000 :568-578.
[3] C.E.KOksal, H.I.Kassab, H.Balakrishnan．Analysis of Short term Fairness in wireless media access
Protocols Proceedings [J] ACM SIGMETRICS, June 2000 :118-119.
Proportional Fair Scheduling for LTE uplink
Liu Xiaoning1
1 Information and Communication Engineering School, Beijing University of Posts and
Telecommunications, Beijing, PRC, (100876) Abstract
LTE uplink scheduling is different from downlink scheduling. The different is that uplink scheduling needs the resource blocks allocated to a user must be adjacent in frequency domain. So the traditional PF scheduling algorithm can not be used in LTE uplink directly. This paper provides some new scheduling algorithm by studying LTE uplink such as using RB grouping method and new PF metric. These algorithms have improvement on system throughput and fairness. This paper shows different system performances by adopting different algorithms. Keywords: SC-FDMA LTE uplink scheduling PF 作者简介：刘晓宁，男，1985年生，硕士研究生，主要研究方向是移动通信系统级仿真及算法研究。
- 6 -
中国科技论文在线
http://www.paper.edu.cn
刘晓宁
北京邮电大学信息与通信工程学院，北京 (100876)
E-mail ：[email protected]
摘 要：本文通过研究LTE 上行调度算法，提出了几种改进的调度算法，该算法在系统吞吐量及用户公平性上各有改进。LTE 上行调度与下行调度的不同之处在于同一时刻分配各某个用户的所有RB 必须是频域连续的。在下行中采用最多的调度算法就是比例公平（PF, proportional fair）算法。本文研究基于这种准则下PF 调度算法在LTE 上行中的应用。本文研究资源块分组的思想，并研究改进的PF 度量值在上行调度的应用，由此提出了几种改进的PF 上行调度算法。本文通过仿真给出了几种不同调度算法的性能，并加以比较，分析各自的优缺点。
关键词：SC-FDMA LTE 上行调度 比例公平 公平性指数 中图分类号：TN929.53
1．引言
OFDMA 作为LTE 下行无线接入的技术，具有抗多径衰落、频谱效率高的优点。但是OFDMA 的一个主要的缺点就是一个OFDM 符号上的瞬时发射功率的变化非常大，这样会导致非常高的峰均比（PAPR ）。在LTE 上行链路中高峰均比是一个非常严重的问题，因为手机的发射功率是上行需要考虑的主要问题。为了寻找OFDMA 的替换，SC-FDMA 被选为LTE 上行的多址访问方案。
SC-FDMA 是单波载（Single-carrier ），与OFDMA 相比之下具有的较低的PAPR （峰值/平均功率比，peak-to-average power ratio），比多载波的PAPR 低1-3dB 左右（PAPR 是由于多载波在频域叠加引起）。更低的PAPR 可以使移动终端在发送功效方面得到更大的好处，并进而延长电池使用时间。SC-FDMA 具有单载波的低PAPR 和多载波的强韧性的两大优势。因此，LTE 上行多址访问技术采用了SC-FDMA 。
在LTE 上行中，系统带宽被分为多个子频带，即多个子载波组。这些子频带被成为RB （physical resource block）。为了在多用户频率分集中得到好的性能，调度器必须知道各个用户在各个RB 上的瞬时的无线信道情况。这些要作为调度的输入值。
在每个调度时刻, 缓存有数据的UE 会在全频带向基站发送参考信号SRS （sounding reference signal）, 基站会测量各UE 在各个RB 的信道质量指示CQI （channel quality indicator ）。而CQI 是由SINR 决定的。SINR 的值为参考信号的功率与当前干扰及噪声功率之比。基站以此为依据根据不同的调度算法，发送调度信息。从而决定UE 在哪些RB 上传输。
在下行中采用最多的调度算法就是比例公平（PF, proportional fair）算法。它是把各个RB 相互独立的逐个分配给用户。PF 算法兼顾了公平性和有效性，可以使系统达到一个较好的性能。但是PF 算法并不能直接运用到SC-FDMA 中，由于SC-FDMA 的单载波的特性，SC-FDMA 需要在同一时刻分配各某个用户的所有RB 必须是频域连续的。所以LTE 上行调度必须要遵守这个条件[1]。
在这篇论文中，我们研究了PF 算法在SC-FDMA 中的应用。我们提出了几种不同的PF
- 1 -
2．调度算法
2.1 公平性指数（FI ）
在无线通信系统中进行资源分配时，如果我们给用户提供相等的服务机会，如Round Robin 算法，将使得处于较好信道状态下的用户获得较多的数据传输量，而较差信道条件下的用户获得较少的数据传输量；如果我们希望用户们获得相等的数据传输量，则要给处于较差的信道状态的用户提供更多的服务机会。显然，两种方法都存在不公平的问题，那么我们就需要一种标准来衡量用户间资源分配的公平性。在传统的有线通信网络中，公平性的衡量理论已经过讨论研究，三种衡量公平性的方法已经广泛应用于不同的资源分配过程中。我们采用其中的一种作为衡量PF 算法公平性的指标，这就是Jain Fairness[2]。
n
Jain fairness index I Jain =
|∑x i |2n ∑x i 2
i =1i =1
n
其中n 表示用户数，x i 表示用户i 已分配的资源总数。
Jain FI 的取值越高，我们认为分配越公平，也就是说，用户获得的资源越平均则分配越公平[3]。
2.2 PF调度算法
我们考虑一个上行带宽被分为M 个RB 的蜂窝网络，每个基站下有N 个用户。采用PF 调度算法对各用户进行调度。 2.2.1 传统算法Alg1
将传统比例公平调度算法应用到SC-FDMA 中，并且遵守资源块连续的原则[1]。PF 度量值为λi c (t ) =r i c (t ) /R i (t ) ，表示在时隙t 时用户i 在RB 号为c 的RB 上的度量值。r i c (t ) 表示用户i 在c 号RB 上的当前可被分配的速率。速率的计算是由CQI 来决定的，而CQI 的值则是由参考信号在此RB 上的信噪比决定的。R i (t ) 表示用户i 的平均传输速率。
分配算法为：
令U 为可调度的用户的集合，A [M ]为RB 分给用户的状态。对RB 从1到m 循环：选取最大的PF 度量值λi ，其中i ∈U 。如果A [c ]=0，则把RB c分配给用户i ，即A [c ]=i ，
c
U =U −{i }。直到循环结束。
2.2.2 分组算法Alg2
为了使所有的资源块能分配给用户，且用户所分配到得资源块都是连续的。我们采用资源块分组的方式来达到这种要求。先将所有的RB 进行分组，将M 个RB 分为N 组，其中N 为扇区中的用户数。每组中的RB 数为M/N，这些RB 捆绑在一起，一起被分配。
PF 度量值为λi c (t ) =r i c (t ) /R i (t ) ，表示在时隙t 时用户i 在RB 号为c 的RB （组）上的度量值。r i c (t ) 表示用户i 在c 号RB （组）上的当前可被分配的速率。速率的计算是由CQI
- 2 -
的平均传输速率。
分配算法为：
1. 对 λi c 按照从大到小的顺序进行排序，保存到集合V 2. 设集合S 为尚未被分配的RB 组集合 3. 令k =1
4.while （V 不等于空）&（k
4.1 选取PF 度量值大小排序为k th 的RB 组 λi ∈V ，c ∈S 4.2 令I 为已分配给用户i 的RB 组集合 4.3.1 if(c 与I 相邻) or(I =φ) then 4.3.1.1 将RB 组分配给用户i
4.3.1.2 S =S −{c };V =V −{λi };k =1 4.3.2 else k =k +1 4.3.3 endif 4 end while 2.2.3 分组算法Alg3
c
c
R i (t ) 表示用户i
为了能使系统吞吐量及公平性得到更好的提升，我们提出了改进的PF 因子。改进的PF 度量值为：λ(t ) =r i (t ) /{R i (t ) +
j
c i
c
∑ρ
j =1
M
j i (t ) r i j (t )}
其中ρi (t ) 表示当前TTI 资源块j 是否分给用户i ，取值为0或1。
我们将此度量值应用到Alg2，而且需要每当有新RB 组被分配，重新计算PF 度量值。
分配算法为：
1. 对 λi c 按照从大到小的顺序进行排序，保存到集合V 2. 设集合S 为尚未被分配的RB 组集合 3. 令k =1
4.while （V 不等于空）&（k
4.2对V 从大到小排序，选取PF 度量值大小排序为k th 的RB 组 λi c ∈V ，c ∈S 4.3 令I 为已分配给用户i 的RB 组集合 4.4.1 if(c 与I 相邻) or(I =φ) then 4.4.1.1 将RB 组分配给用户i
4.4.1.2 S =S −{c };V =V −{λi c };k =1 4.4.2 else k =k +1 4.4.3 endif 4 end while 2.2.4 算法Alg4
按照PF 度量值由大到小为用户分配RB ，提前是分配的RB 必须连续。不满足条件的
- 3 -
目的：让所有的RB 都按照PF 算法分配给各用户，并且满足RB 连续的条件。
分配算法为：
1. 对 λi c 按照从大到小的顺序进行排序，保存到集合V 2. 令k =1
3.while V不等于空 do
3.1 选取PF 度量值大小排序为k th 的RB 组 λi c ∈V 3.2 令I 为已分配给用户i 的RB 组集合 3.3.1 if(c 与I 相邻) or(I =φ) then 3.3.1.1 将RB 组分配给用户i 3.3.1.2 V =V −{λi c };k =1 3.3.2 else k =k +1 3.3.3 endif 3 end while 2.2.5 算法Alg5
将新PF 度量值运用到前一个算法Alg4中。 PF 度量值为：λ(t ) =r i (t ) /{R i (t ) +
c i
c
M
∑ρ
j =1
j i (t ) r i j (t )} 其中ρi j (t ) 表示当前TTI 资源块
j 是否分给用户i ，取值为0或1。
分配算法为：
1. 对 λi c 按照从大到小的顺序进行排序，保存到集合V 2. 令k =1
3.while V不等于空 do
3.1每当有新RB 组被分配，更新PF 度量值
3.2对V 从大到小排序，选取PF 度量值大小排序为k th 的RB 组 λi c ∈V 3.3 令I 为已分配给用户i 的RB 组集合 3.4.1 if(c 与I 相邻) or(I =φ) then 3.4.1.1 将RB 组分配给用户i 3.4.1.2 V =V −{λi c };k =1 3.4.2 else k =k +1 3.4.3 endif 3 end while
3．仿真结果及分析
- 4 -
S y s t e m t h r o u g h p u t [M b p s ]
Number of active users in cell
图1 系统吞吐量图
0.900.850.80
F a i r n e s s [t =10m s ]
0.750.700.650.600.550.500.450.40
Number of active users in cell
图2 公平性因子图
在仿真中系统带宽为20MHz ，每个RB 所占用的子载波数为12，仿真结果见图1图2。其中图1为各种调度算法的系统吞吐量，图2各种算法的公平性因子图。为从图1和图2中可以看出Alg1的吞吐量最低，因为它无法保证所有的资源块都被分配。在用户数较少的时候，即平均每个用户可分配的资源块较多时Alg2的吞吐量略小于Alg4，但是当用户数增多的时候，Alg2的吞吐量会略大一些，但同时公平性则会较小些。采用新PF 度量值的Alg3在吞吐量及公平性上都比Alg2要好一些。这说明新的PF 度量值可以改进系统的吞吐量及公平性。采用新PF 度量值的Alg5在用户数较少的时候比Alg4的吞吐量要高一些，但是用户数增多的时候，它的吞吐量会比Alg4低一些，但是在公平性上好于Alg4。
4．总结
- 5 -
参考文献
[1] Suk-Bok Lee, Ioannis Pefkianakis, Adam Meyerson, et al．Proportional Fair Frequency-Domain Packet
Scheduling for 3GPP LTE Uplink [R] IEEE INFOCOM 2009 mini-symposium
[2] A.Kumar, J.Kleinberg．Fairness Measures for Resource Allocation [J] IEEE Symposium on
Foundation of Computer Science, 2000 :568-578.
[3] C.E.KOksal, H.I.Kassab, H.Balakrishnan．Analysis of Short term Fairness in wireless media access
Protocols Proceedings [J] ACM SIGMETRICS, June 2000 :118-119.
Proportional Fair Scheduling for LTE uplink
Liu Xiaoning1
1 Information and Communication Engineering School, Beijing University of Posts and
Telecommunications, Beijing, PRC, (100876) Abstract
LTE uplink scheduling is different from downlink scheduling. The different is that uplink scheduling needs the resource blocks allocated to a user must be adjacent in frequency domain. So the traditional PF scheduling algorithm can not be used in LTE uplink directly. This paper provides some new scheduling algorithm by studying LTE uplink such as using RB grouping method and new PF metric. These algorithms have improvement on system throughput and fairness. This paper shows different system performances by adopting different algorithms. Keywords: SC-FDMA LTE uplink scheduling PF 作者简介：刘晓宁，男，1985年生，硕士研究生，主要研究方向是移动通信系统级仿真及算法研究。
- 6 -