Air interface scheduler for wireless communication networks

• US 6,917,812 B2
• Filed: 12/03/2001
• Issued: 07/12/2005
• Est. Priority Date: 12/03/2001
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Damnjanovic, Aleksandar
• Primary Examiner(s): D AGOSTA, STEPHEN M
• Application Number:
  US10/005,980
• Publication Number:
  US 20030104817A1
• Time in Patent Office: 1,317 Days
• Field of Search: 455/452.1, 455/452.2, 455/453, 455/517, 455/519, 455/524, 455/525, 370231-235, 37039521-39543
• US Class Current: 455/452.2
• CPC Class Codes: H04W 28/18 Negotiating wireless communication parameters
• CPC Class Codes: H04W 72/54 based on quality criteria
• CPC Class Codes: H04W 72/569 of the traffic information

Abstract

A scheduler permits efficient and flexible scheduling between simultaneous users of an air interface in a wireless communication networks in consideration of desired QoS parameters and class-based preferential scheduling. By appropriately defining the utility functions used by the scheduler in user scheduling, scheduling may, among other goals, be biased toward satisfaction of average or minimum throughput constraints, be biased toward meeting QoS delay constraints, or be biased based on combined considerations of these goals. Where QoS delay constraints are considered, the scheduler might adopt a dynamic approach to updating delay terms in the utility functions, such that users are not over-served or underserved relative to a desired quality of service.

Claims

1. A method of scheduling a plurality of users sharing use of an air interface in a wireless communication network, the method comprising:

calculating a scheduling metric for each user, said scheduling metric being dependent on a minimum data rate defined for the user;

defining the scheduling metrics such that assigning a higher minimum data rate value to a given user preferentially biases scheduling of that user;

defining the scheduling metrics such that a magnitude of the scheduling metric for each user depends on a differential value between an average served data rate of the user and the minimum data rate defined for the user, wherein users having smaller differential values are preferentially scheduled; and

scheduling users based on the scheduling metrics.

2. The method of claim 1, wherein calculating a scheduling metric for each user comprises calculating scheduling metrics for the plurality of users at a scheduling decision point.

3. The method of claim 2, wherein scheduling users based on the scheduling metrics comprises selecting the user having the greatest scheduling metric for a defined interval of service via the air interface.

4. The method of claim 3, further comprising defining the scheduling metrics such that the magnitudes of the scheduling metrics vary proportionately with the minimum data rates defined for the users, so that scheduling is preferentially biased towards users having higher defined minimum data rates.

5. The method of claim 1, further comprising defining a minimum data rate for each user based upon a user class of each user, and wherein different user classes have different minimum data rates such that scheduling is biased by user class.

6. The method of claim 1, further comprising:

defining a common minimum data rate for the plurality of users; and

including a user variable in the scheduling metric of each user such that scheduling of the plurality of users is biased by the user class variables.

7. The method of claim 6, further comprising setting a value of the user variable for each user based on a user class associated with the user, wherein different user classes have different user variable values such that scheduling is biased by user class.

10. The method of claim 1, further comprising defining the scheduling metric for each user to depend upon a QoS delay constraint associated with the user in addition to the minimum data rate defined for the user, wherein the QoS delay constraint defines a maximum delay for pending data to be delivered to the user via the air interface.

11. The method of claim 10, further comprising dynamically updating the QoS delay constraint for each user based on whether the QoS delay constraint is violated.

12. The method of claim 10, wherein dynamically updating the QoS delay constraint increases the scheduling preference of the user if the QoS delay constraint is violated, and decreases the scheduling preference of the user if the QoS delay constraint is not violated.

8. The method of claim 8, wherein calculating the scheduling metric for each user comprises differentiating a utility function that depends on the minimum data rate defined far the user.

9. The method of claim 8, wherein differentiating the utility function comprises differentiating log(R_i−

R_i,min), where R_i equals the average served data rate of the i^th user and R_i,min equals the minimum data rate defined for the i^th user.

13. A method of scheduling use of an air interface shared by users of a wireless communication network, the method comprising:

assigning a utility function to each user that is dependent on an average served rate and a desired minimum data rate associated with the user, wherein the utility function assigned to each user is dependent an a differential value between the average served rate and the desired minimum data rate associated with the user;

evaluating the utility function for each user to determine a scheduling metric for the user, wherein a magnitude of the scheduling metric varies proportionately to the minimum data rate; and

scheduling the user having the greatest scheduling metric magnitude.

14. The method of claim 13, wherein the users are divided into a plurality of user classes, and further comprising assigning different minimum data rates to different user classes.

15. The method of claim 14, further comprising assigning a relatively higher minimum data rate to users in a preferred user class such that scheduling is preferentially biased towards users in the preferred user class.

16. The method of claim 13, wherein users are divided into a plurality of user classes, and further comprising:

assigning a common minimum data rate to all users; and

including a class variable in the utility function assigned to each user to bias scheduling based on a user class.

17. The method of claim 13, further comprising:

defining a scheduling preference variable for each; and

including the scheduling preference variable as a multiplier in the utility function assigned to each user, such that user scheduling is biased by the scheduling preference values.

18. The method of claim 17, further comprising assigning a value to the scheduling preference variable for each user based on a user class associated with the user, such that users in a preferred class are assigned preferential scheduling preference values.

19. The method of claim 17, further comprising assigning a value to the scheduling preference value for each user based on one of a plurality of service plans assigned to the user, wherein each of said plurality of service plans has a different scheduling preference value.

20. The method of claim 13, wherein me utility function is defined as U_i(R_i)=log (R_i=R_i,min), where R_i is the measured data throughput of the i^th user and R_i,min is the minimum data throughput associated with the i^th user.

21. The method of claim 20, wherein evaluating the utility function for each user comprises differentiating U_i(R_i), such that the scheduling metric vanes inversely with the magnitude of (R_i−

R_i,min).

22. The method of claim 21, further comprising:

defining a minimum value for (Ri−

Ri,min) to use in determining the scheduling metric; and

using the minimum value to calculate the scheduling metric if (Ri−

Ri,min) is equal to or less than zero.

23. The method of claim 13, further comprising:

defining the utility function associated with each user as the sum of a throughput-based term dependent on the minimum data rate associated with the user, and a C/I-based term dependent on current reception conditions associated with the user;

setting weighting coefficients for multiplying the throughput-based and C/I-based terms to achieve a desired scheduling bias between scheduling users to maintain desired minimum data rates versus scheduling users to maintain a desired aggregate throughput.

24. The method of claim 13, further comprising:

associating a delay constraint with each user, wherein the delay constraint depends on a QoS desired by the user;

increasing the scheduling preference of the user when the delay constraint is violated; and

decreasing the scheduling preference of the user when the delay constraint is not violated.

25. The method of claim 24, wherein associating a delay constraint with each user comprises defining the utility function assigned to each user as the product of a first term dependent on the minimum data throughput associated with the user, and a second term dependent on the delay constraint associated with the user.

26. The method of claim 24, wherein associating a delay constraint with each user comprises defining the utility function assigned to each user as the sum of a first term dependent on the minimum data throughput associated with the user, and a second term dependent on the delay constraint associated with the user.

27. A wireless communication network comprising:

at least one radio base station to serve a plurality of users over a shared air interface; and

a scheduler to schedule use of the air interface by the plurality of users, the scheduler comprising;

a metric calculator to calculate a scheduling metric for each user, wherein said scheduling metric is calculated based on a minimum data rate defined for the user, and further wherein the metric calculator calculates the scheduling metric for each user based on a differential value between an average served rate of the user (R_i) and the minimum data rate of the user (R_i,min), such that the scheduling metric becomes more favorable as R_i approaches R_i,min; and

a comparator to compare the scheduling metrics to identify the user having the most favorable scheduling metric, such that the identified user is scheduled for service via the air interface.

28. The wireless communication network of claim 27, wherein the scheduler defines the scheduling metric for each user as the ratio of a requested data rate from the user to the difference value for the user (R_i−

R_i,min), such that the scheduling metric becomes more favorable as the requested data rate increases.

29. The wireless communication network of claim 28, wherein the network comprises a TIA/EIA/IS-856 HDR network, and wherein requested data rates are received by the network from the users as Data Rate Control (DRC) values.

30. The wireless communication network of claim 29, wherein the scheduler defines the scheduling metric for each user as a function of DRC_i/(R_i−

R_i,min), such that the scheduling metric for the i^th user becomes more favorable with higher DRC_i values, and with smaller difference values (R_i−

R_i,min).

31. The wireless communication network of claim 27, wherein the scheduler defines the scheduling metric for each user to depend on the inverse of the difference value (R_i−

R_i,min), such that as the magnitude of the differential value decreases, the magnitude of the scheduling metric increases, and wherein a greater scheduling metric magnitude corresponds to a more favorable scheduling metric.

32. The wireless communication network of claim 27, wherein scheduling preference is biased by assigning different minimum data rate values to different users.

33. The wireless communication network of claim 27, wherein all users are assigned a common minimum data rate, and wherein scheduling preference is biased by including a user variable in the scheduling metric.

34. The wireless communication network of claim 33, wherein the user variable is a multiplier of the scheduling metric, such that a greater multiplier results in a more favorable scheduling metric.

35. The wireless communication network of claim 27, wherein the metric calculator calculates the scheduling metric for each user in further dependence on a delay constraint parameter.

36. The wireless communication network of claim 35, wherein the metric calculator calculates the scheduling mettle for each user based on a utility function assigned to each user, arid wherein the utility function is a sum of a first term dependent on the minimum data rate defined for the user, and a second term dependent on the delay constraint parameter.

37. The wireless communication network of claim 35, wherein the metric calculator calculates the scheduling metric for each user based on a utility function assigned to each user, and wherein the utility function is a product of a first term dependent on the minimum data rate defined for the user, and a second term dependent on the delay constraint parameter.

38. The wireless communication network of claim 35, wherein the scheduler dynamically updates the delay constraint parameter for each user in dependence on whether or not a QoS desired by the user is being met, such that the scheduling metric of the user becomes more favorable if the desired QoS is not met, and less favorable if the desired QoS is met.

39. A scheduler to schedule use of a wireless communication network air interface that is shared by a plurality of users, the scheduler comprising:

a metric calculator to calculate a scheduling metric for each user, wherein said scheduling metric is calculated based on a minimum data rate defined for the user, wherein the metric calculator calculates the scheduling metric for each user based on a differential value between an average served rate of the user (R_i) and the minimum data rate of the user (R_i,min), such that the scheduling metric becomes more favorable as R_i approaches R_i,min; and

)

a comparator to compare the scheduling metrics to identify the user having the most favorable scheduling metric, such that the identified user is scheduled for service via the air interface.

40. The scheduler of claim 39, wherein the scheduler defines the scheduling metric of a requested data rate from the user to the differential value for the user (R_i−

R_i,min), such that the scheduling metric becomes more favorable as the requested data rate increases.

41. The scheduler of claim 40, wherein the network comprises a TIA/EIA/IS-856 HDR network, and wherein requested data rates are received by the network from the users as Date Rate Control (DRC) values.

42. The scheduler of claim 41, wherein the scheduler defines the scheduling metric for each user as a function of DRC_i/(R_i−

R_i,min), such that the scheduling metric for the i^th user becomes more favorable with higher DRC, values, and with smaller differential values (R_i−

R_i,min).

43. The scheduler of claim 39, wherein the scheduler defines the scheduling metric for each user to depend on We inverse of the differential value (R_i−

R_i,min), such that as the magnitude of the differential value decreases, the magnitude of the scheduling metric increases, and wherein a greater scheduling metric magnitude corresponds to a more favorable scheduling metric.

44. The scheduler of claim 39, wherein scheduling preference is biased by assigning different minimum data rate values to different users.

45. The scheduler of claim 39, wherein all users are assigned a common minimum data rate, and wherein scheduling preference is biased by including a user variable in the scheduling metric.

46. The scheduler of claim 45, wherein the user variable is a multiplier of the scheduling metric, such that a greater multiplier results in a more favorable scheduling metric.

47. The scheduler of claim 39, wherein the metric calculator calculates the scheduling metric for each user further based on a delay constraint parameter.

48. The scheduler of claim 47, wherein the metric calculator calculates the scheduling metric for each user based on a utility function assigned to each user, and wherein the utility function is a sum of a first term dependent on the minimum data rate defined for the user, and a second term dependent on the delay constraint parameter.

49. The scheduler of claim 47, wherein the metric calculator calculates the scheduling metric for each user based on a utility function assigned to each user, and wherein the utility function is a product of a first term dependent on the minimum data rate defined for the user, and a second term dependent on the delay constraint parameter.

50. The scheduler of claim 47, wherein the scheduler dynamically updates the delay constraint parameter for each user based on whether or not a QoS desired by the user is being met, such that the scheduling metric of the user becomes more favorable if the desired QoS is not met, and less favorable if the desired QoS is met.