Scheduling method with tunable throughput maximization and fairness guarantees in resource allocation
A flexible scheduling method with tunable throughput maximization and fairness guarantees in resource allocation is required and suitable for high-rate packet data and other services. Our inventive method, named Alpha-Rule, employs a control variable α, that permits dynamic and/or real-time adjustment/tradeoff between aggregate throughput, per-user throughput, and per-user resource allocation. Our method advantageously operates in conjunction with Multiple-Input Multiple-Output techniques such as Space-Time Block Coding (STBC), Bell Labs Layered Space-Time (BLAST) and others, while offering greater flexibility than existing scheduling techniques, e.g., max-C/I or Proportionally Fair (PF).
1. A method of determining which users, from a plurality of users, access to a communications system is to be provided, such access being provided to the plurality of users over a plurality of channels, the method comprising the steps of:
determining, for each of plurality of channels and for each of the plurality of users, a channel measurement feedback characteristic;
determining, for each of the plurality of channels and for each of the plurality of users, a past throughput characteristic; and
determining, a user to be provided access according to the following relationship:
k
*
=
arg
max
k
{
w
k
r
k
(
t
)
r
~
k
(
t
)
a
}
where
r k (t) is the channel measurement feedback characteristic of user k;
{tilde over (r)} k (t) is the mean throughput of user k;
w k is a weight applied to each of the users;
α is the Alpha Rule tuning parameter wherein α≠0 and α≠1; and k* is the selected user; and
determining, a throughput characteristic for the system;
determining, a fairness characteristic for the system; and
adjusting α, as a result of the determined throughput characteristic and the determined fairness characteristic; and
comparing, the determined throughput characteristic for the system with a target throughput characteristic; and
comparing, the determined fairness characteristic for the system with a target fairness characteristic.
2. The method according to claim 1 wherein the adjusting step further comprising the steps of:
decrementing α, by a predetermined amount, when the determined throughput characteristic for the system is ≦ the target throughput characteristic and the determined fairness characteristic for the system is ≧ the target fairness characteristic.
3. The method according to claim 1 wherein the adjusting step further comprising the steps of:
Incrementing α, by a predetermined amount, when the determined throughput characteristic for the system is ≧ the target throughput characteristic and the determined fairness characteristic for the system is ≦ the target fairness characteristic.
4. The method according to claim 1 wherein the adjusting step further comprising the steps of:
adjusting the targets, by a predetermined amount, when the determined throughput characteristic for the system is ≦ the target throughput characteristic and the determined fairness characteristic for the system is ≦ the target fairness characteristic.
5. The method according to claim 1 , wherein the throughput characteristic {tilde over (R)} is determined according to the following relationship:
R
~
=
∑
k
=
1
K
r
~
k
(
t
)
where
{tilde over (r)} k (t) is the mean throughput of user k; and K is the total number of users.
6. The method according to claim 1 , wherein the fairness characteristic {tilde over (F)} is determined according to the following relationship:
F
~
=
(
∑
k
=
1
K
r
~
k
(
t
)
)
2
(
K
∑
k
=
1
K
r
~
k
(
t
)
2
)
where
{tilde over (r)} k (t) is the mean throughput of user k; and
K is the total number of users.
7. The method according to claim 2 , wherein α is decremented by a percentage of its present value.
8. The method according to claim 3 , wherein α is incremented by a percentage of its present value.
9. The method according to claim 3 , wherein the percentage that α is decremented by is between 0% and 100%.
10. The method according to claim 8 , wherein the percentage that α is incremented by is between 0% and 100%.
11. The method according to claim 1 , wherein the adjusting of α is performed in real-time.