Method and apparatus for distributed optimal reverse link scheduling of resources, such as a rate and power in a wireless communication system

• US 6,597,705 B1
• Filed: 09/10/1998
• Issued: 07/22/2003
• Est. Priority Date: 09/10/1998
• Status: Expired due to Term

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Rezaiifar, Ramin, Holtzman, Jack
• Primary Examiner(s): Yao, Kwang Bin
• Assistant Examiner(s): NGUYEN, HANH N
• Application Number:
  US09/151,391
• Time in Patent Office: 1,776 Days
• Field of Search: 370/468, 370/318, 370/320, 370/328, 370/329, 370/331-333, 370/348, 370/335, 370/342, 370/330, 370/346, 370/441, 370/395.41, 370/395.21, 370/395.2, 370/432, 370/477, 370/498, 455/433, 455/450, 455/452, 455/500, 455/524, 455/63, 455/67.3
• US Class Current: 370/468
• CPC Class Codes: H04W 28/18 Negotiating wireless communication parameters
• CPC Class Codes: H04W 52/24 using SIR [Signal to Interference Ratio] or other wireless path parameters
• CPC Class Codes: H04W 52/265 taking into account the quality of service QoS
• CPC Class Codes: H04W 52/267 taking into account the information rate
• CPC Class Codes: H04W 52/343 taking into account loading or congestion level
• CPC Class Codes: H04W 52/346 distributing total power among users or channels

Abstract

A method, and corresponding apparatus, applies to individual base stations in a wireless communications systems, where each base station performs rate assignment to mobile stations optimally, but independently of the other base stations. Different base stations affect each other through other cell interference, and continuously modify their reversed link rate assignment based on the other—cell interference received and the requested rates from the mobile stations. The base stations converge to a stable condition with uncoordinated optimizations. The optimizing technique maximizes total through put in each cell (maximizing rates) while maintaining interference to other cells at a minimum level, and being subject to at least some of the following constraints: mobile station'"'"'s maximum transmit power, mobile station'"'"'s requested rate, discrete set of possible rates, maximum rise—over—thermal interference at the base station, and minimum required received error per bit normalized for noise.

Claims

1. In a communication system having at least first and second base stations, the base stations having communication resources for exchanging communication signals with at least first and second user stations, respectively, a method for allocating the resources in the communication system, comprising:

at each of the first and second user stations, transmitting a request for an allocation of resources for transmitting a type of data by the user station;

at the first and second base stations, receiving the requests from the first and second user stations, respectively, and other user stations, and allocating resources at the first and second base stations in response to the requests, wherein the first base station optimizes the allocation of resources independently of the allocation of resources of the second base station and minimizes interference in accordance with system stability and throughput with the second base station, while the second base station optimizes the allocation of resources independently of the allocation of resources of the first base station and minimizes interference with the first base station in accordance with system stability and throughput;

at the first and second base stations, transmitting first and second assignment signals to the first and second user stations, respectively, wherein each assignment signal specifies a transmission rate; and

at the first and second user stations, transmitting the type of data at a rate specified in the first and second assignment signals, respectively;

wherein the allocation of resources includes optimizing transmission powers for N number of user stations for the first base station by optimizing;

$\underset{P}{\max }<br><br>\underset{i=1}{\stackrel{N}{\sum <br><br>}}<br><br>h_i<br><br>P_i,$

subject to;

2. In a communication system having at least first and second base stations, the base stations having communication resources for exchanging communication signals with at least first and second user stations, respectively, a method for allocating the resources in the communication system, comprising:

at each of the first and second user stations, transmitting a request for an allocation of resources for transmitting a type of data by the user station;

at the first and second base stations, receiving the requests from the first and second user stations, respectively, and other user stations, and allocating resources at the first and second base stations in response to the requests, wherein the first base station optimizes the allocation of resources independently of the allocation of resources of the second base station and minimizes interference in accordance with system stability and throughput with the second base station, while the second base station optimizes the allocation of resources independently of the allocation of resources of the first base station and minimizes interference with the first base station in accordance with system stability and throughput, wherein the allocation of resources includes optimizing power values based on the received requests, the user stations'"'"' maximum transmit power, a discrete set of transmission rates, maximum rise-over-thermal interference, and minimum required error rate; and

at the first and second base stations, transmitting first and second assignment signals to the first and second user stations, respectively, wherein each assignment signal specifies a transmission rate; and

at the first and second user stations, transmitting the type of data at a rate specified in the first and second assignment signals, respectively.

3. The method of claim 2 wherein the allocation of resources includes:

optimizing power values based on the received requests and interference from adjacent base stations; and

identifying rates corresponding to the optimized power values;

and wherein transmitting first and second assignment signals includes transmitting a first identified rate for transmitting a first group of the data packets;

and wherein the method further comprises;

optimizing new power values based on newly received bandwidth requests and new interference from adjacent base stations;

identifying new rates corresponding to the optimized new power values; and

transmitting a second identified rate for transmitting a second group of the data packets.

4. The method of claim 2 wherein the allocation of resources includes:

optimizing power values based on the received requests and interference from adjacent base stations; and

identifying rates corresponding to the optimized power values;

and wherein transmitting first and second assignment signals includes transmitting first and second identified rates.

5. The method of claim 2 wherein the allocation of resources includes synchronously optimizing power values based on the received requests and interference from adjacent base stations.

6. The method of claim 2 wherein the allocation of resources includes assigning higher transmission rates for user stations closer to a center of a cell in which the first base station is located.

7. The method of claim 2 wherein the allocation of resources includes, at each base station:

optimizing power values based on the received requests and interference from adjacent base stations;

identifying assignment signals corresponding to the optimized power values; and

repeating the optimizing and identifying, and wherein the repeating converges the optimizing to stable values among the base stations.

8. In a communication system having at least first and second base stations, the base stations having communications resources for exchanging communication signals with at least first and second user stations, respectively, a method comprising:

receiving transmission requests from the first and second user stations and other user stations, and allocating resources at the first and second base stations in response to requests received from the first, second and other user stations, wherein the first base station optimizes the allocation of resources independently of the allocation of resources of the second base station and minimizes interference with the second base station in accordance with system stability and throughput, while the second base station optimizes the allocation of resources independently of the allocation of resources of the first base station and minimizes interference with the first base station in accordance with system stability and throughput, wherein receiving transmission requests includes receiving a transmission rate request, and wherein allocation of resources includes optimizing power values based on the received rate requests, the user stations'"'"' maximum transmit power, a discrete set of transmission rates, maximum rise-over-thermal interference, and minimum required error rate; and

transmitting first and second assignment signals to the first and second user stations, respectively, wherein the first and second assignment signals specify at least one transmission criteria at which the first and second user stations are to transmit data, respectively.

9. The method of claim 8 wherein receiving transmission requests includes receiving a transmission rate request, and wherein allocation of resources includes:

optimizing power values based on the received rate requests and interference from adjacent base stations; and

identifying rates corresponding to the optimized power values;

and wherein transmitting first and second assignment signals includes transmitting first and second identified rates.

10. The method of claim 8 wherein allocation of resources includes synchronously optimizing power values based on the received rate requests and interference from adjacent base stations.

11. The method of claim 8 wherein receiving transmission requests includes receiving a transmission rate request, and wherein allocation of resources includes assigning higher transmission rates for user stations closer to a center of a cell in which the first base station is located.

12. The method of claim 8 wherein allocation of resources includes, at each base station:

optimizing power values based on the received requests and interference from adjacent base stations;

identifying assignment signals corresponding to the optimized power values; and

repeating the optimizing and identifying, and wherein the repeating converges the optimizing to stable values among the base stations.

13. The method of claim 8 wherein receiving transmission requests includes receiving a transmission rate request for data packets, and wherein allocation of resources includes:

optimizing power values based on the received rate requests and interference from adjacent base stations; and

identifying rates corresponding to the optimized power values;

and wherein transmitting first and second assignment signals includes transmitting a first identified rate for transmitting a first group of the data packets; and

wherein the method further comprises;

optimizing new power values based on newly received rate requests and new interference from adjacent base stations;

identifying new rates corresponding to the optimized new power values; and

transmitting a second identified rate for transmitting a second group of the data packets.

14. In a communication system having at least first and second base stations, the base stations having communications resources for exchanging communication signals with at least first and second user stations, respectively, a method comprising:

receiving transmission requests from the first and second user stations and other user stations, and allocating resources at the first and second base stations in response to requests received from the first, second and other user stations, wherein the first base station optimizes the allocation of resources independently of the allocation of resources of the second base station and minimizes interference with the second base station in accordance with system stability and throughput, while the second base station optimizes the allocation of resources independently of the allocation of resources of the first base station and minimizes interference with the first base station in accordance with system stability and throughput; and

transmitting first and second assignment signals to the first and second user stations, respectively, wherein the first and second assignment signals specify at least one transmission criteria at which the first and second user stations are to transmit data, respectively;

wherein allocation of resources includes optimizing transmission powers for N number of user stations for the first base station by optimizing;

$\underset{P}{\max }<br><br>\underset{i=1}{\stackrel{N}{\sum <br><br>}}<br><br>h_i<br><br>P_i,$

subject to;

15. In a communication system having k number of cells and N number of users, a method of scheduling resources comprising:

receiving rate requests at each of the k number of cells;

at each cell, optimizing;

$\underset{P}{\max }<br><br>\underset{i=1}{\stackrel{N}{\sum <br><br>}}<br><br>h_i<br><br>P_i,$

subject to;

16. The method of claim 15 wherein optimizing includes synchronously optimizing power values based on the received rate requests and interference from adjacent cells.

17. The method of claim 15 wherein optimizing includes optimizing power values based on a discrete set of transmission rates, and maximum rise-over-thermal interference.

18. The method of claim 15, further comprising, at each cell:

repeating the receiving, optimizing and assigning, and wherein the repeating converges the optimizing to stable values among the k number of cells.

19. In a communication system having at least first and second base stations, the base stations having communications resources for exchanging communication signals with at least first and second user stations, respectively, an apparatus comprising:

means for receiving transmission requests from the first and second user stations and other user stations, and for allocating the resources in response to requests received from the first, second and other user stations, wherein a first means for allocating resources optimizes the resource allocation independently of the resource allocation of a second means for allocating resources and minimizes interference with the second base station in accordance with system stability and throughput, while the second means for allocating resources optimizes the resource allocation independently of the resource allocation of the first means for allocating resources and minimizes interference with the first base station in accordance with system stability and throughput, wherein the means for receiving transmission requests receives a transmission rate request, and wherein the means for allocating resources includes means for optimizing power values based on the received rate requests, the user stations'"'"' maximum transmit power, a discrete set of transmission rates, maximum rise-over-thermal interference, and minimum required error rate; and

means for transmitting first and second assignment signals to the first and second user stations, respectively, wherein the first and second assignment signals specify at least one transmission criteria at which the first and second user stations are to transmit data, respectively.

20. The apparatus of claim 19 wherein the means for receiving transmission requests includes means for receiving a transmission rate request, and wherein the means for allocating resources includes:

means for optimizing power values based on the received rate requests and interference from adjacent base stations; and

means for identifying rates corresponding to the optimized power values;

and wherein the means for transmitting first and second assignment signals includes transmitting first and second identified rates.

21. The apparatus of claim 19 wherein the means for allocating resources includes means for synchronously optimizing power values based on the received rate requests and interference from adjacent base stations.

22. By The apparatus of claim 19 wherein the means for receiving transmission requests receives a transmission rate request, and wherein the means for allocating resources assigns higher transmission rates for user stations closer to a center of a cell in which the first base station is located.

23. The apparatus of claim 19 wherein the means for allocating resources includes, at each base station:

means for optimizing power values based on the received requests and interference from adjacent base stations;

means for identifying assignment signals corresponding to the optimized power values; and

means for repeating the optimizing and identifying, and wherein the repeating converges the optimizing to stable values among the base stations.

24. The apparatus of claim 19 wherein the means for receiving transmission requests receives a transmission rate request for data packets, and wherein the means for allocating resources includes:

means for optimizing power values based on the received rate requests and interference from adjacent base stations; and

means for identifying rates corresponding to the optimized power values;

and wherein the means for transmitting first and second assignment signals transmits a first identified rate for transmitting a first group of the data packets; and

wherein the means for allocating resources further includes;

optimizing new power values based on newly received rate requests and new interference from adjacent base stations;

identifying new rates corresponding to the optimized new power values; and

transmitting a second identified rate for transmitting a second group of the data packets.

25. In a communication system having at least first and second base stations, the base stations having communications resources for exchanging communication signals with at least first and second user stations, respectively, an apparatus comprising:

means for receiving transmission requests from the first and second user stations and other user stations, and for allocating the resources in response to requests received from the first, second and other user stations, wherein a first means for allocating resources optimizes the resource allocation independently of the resource allocation of a second means for allocating resources and minimizes interference with the second base station in accordance with system stability and throughput, while the second means for allocating resources optimizes the resource allocation independently of the resource allocation of the first means for allocating resources and minimizes interference with the first base station in accordance with system stability and throughput; and

means for transmitting first and second assignment signals to the first and second user stations, respectively, wherein the first and second assignment signals specify at least one transmission criteria at which the first and second user stations are to transmit data, respectively;

wherein the means for allocating resources includes means for optimizing transmission powers for N number of user stations for the first base station by optimizing;

$\underset{P}{\max }<br><br>\underset{i=1}{\stackrel{N}{\sum <br><br>}}<br><br>h_i<br><br>P_i,$

subject to;

26. In a communication system having at least first and second base stations, the base stations having communication resources for exchanging communication signals with at least first and second user stations, respectively, an apparatus comprising:

first and second receivers at the first and second base stations that receive transmission requests from the first and second user stations, all respectively, and from other user stations;

first and second processors, coupled to the first and second receivers, that allocate resources in response to requests received from the first and second user stations, all respectively, and from other user stations, wherein the first processor optimizes the allocation of resources independently of the allocation of resources of the second base station and minimizes interference with the second base station in accordance with system stability and throughput, while the second processor optimizes the allocation of resources independently of the allocation of resources of the first base station and minimizes interference with the first base station in accordance with maximum stability and throughput; and

first and second transmitters, coupled to the first and second processors, that transmit first and second assignment signals to the first and second user stations, all respectively, wherein the first and second assignment signals specify at least one transmission criteria at which the first and second user stations are to transmit data, respectively, wherein the first and second transmitters receive transmission rate requests, and wherein the first and second processors optimize power values based on the received rate requests, the user stations'"'"' maximum transmit power, a discrete set of transmission rates, maximum rise-over-thermal interference, and minimum required error rate.

27. The apparatus of claim 26 wherein the first and second receivers receive transmission requests including a transmission rate request, and wherein the first and second processors are programmed for:

optimizing power values based on the received rate requests and interference from adjacent base stations; and

identifying rates corresponding to the optimized power values;

and wherein the first and second transmitters transmit first and second identified rates.

28. The apparatus of claim 26 wherein the first and second processors synchronously optimize power values based on the received rate requests and interference from adjacent base stations.

29. The apparatus of claim 26 wherein the first and second transmitters receive transmission rate requests, and wherein the first and second processors assign higher transmission rates for user stations closer to a center of a cell in which the first and second base stations are located, respectively.

30. The apparatus of claim 26 wherein the first and second processors are each programmed for:

optimizing power values based on the received requests and interference from adjacent base stations;

identifying assignment signals corresponding to the optimized power values; and

repeating the optimizing and identifying, and wherein the repeating converges the optimizing to stable values among the base stations.

31. The apparatus of claim 26 wherein the first and second receivers receive transmission rate requests for data packets to be transmitted by the first user stations, and wherein the first processor is programmed for:

optimizing power values based on the received rate requests and interference from adjacent base stations; and

identifying rates corresponding to the optimized power values, including first identified rate for transmitting a first group of the data packets;

optimizing new power values based on newly received rate requests and new interference from adjacent base stations;

identifying new rates corresponding to the optimized new power values; and

transmitting a second identified rate for transmitting a second group of the data packets.

32. In a communication system having at least first and second base stations, the base stations having communication resources for exchanging communication signals with at least first and second user stations, respectively, an apparatus comprising:

first and second receivers at the first and second base stations that receive transmission requests from the first and second user stations, all respectively, and from other user stations;

first and second processors, coupled to the first and second receiver systems, that allocate resources in response to requests received from the first and second user stations, all respectively, and from other user stations, wherein the first processor optimizes the allocation of resources independently of the allocation of resources of the second base station and minimizes interference with the second base station in accordance with system stability and throughput, while the second processor optimizes the allocation of resources independently of the allocation of resources of the first base station and minimizes interference with the first base station in accordance with maximum stability and throughput; and

first and second transmitters, coupled to the first and second processors, that transmit first and second assignment signals to the first and second user stations, all respectively, wherein the first and second assignment signals specify at least one transmission criteria at which the first and second user stations are to transmit data, respectively;

wherein each of the first and second processors is programmed for optimizing transmission powers for N number of user stations by optimizing;

$\underset{P}{\max }<br><br>\underset{i=1}{\stackrel{N}{\sum <br><br>}}<br><br>h_i<br><br>P_i,$

subject to;

33. A computer-readable medium having instructions stored thereon to cause computers in a communication system to perform a method, wherein the system includes at least first and second base stations, the base stations having communications resources for exchanging communication signals with at least first and second user stations, respectively, the method comprising:

receiving transmission requests from the first and second user stations and other user stations, and allocating resources at the first and second base stations in response to the requests received from the first, second and other user stations, wherein the first base station optimizes the allocation of resources independently of the allocation of resources of the second base station and minimizes interference with the second base station in accordance with system stability and throughput, while the second base station optimizes the allocation of resources independently of the allocation of resources of the first base station and minimizes interference with the first base station, in accordance with system stability and throughput, wherein receiving transmission requests includes receiving a transmission rate request, and wherein allocation of resources includes optimizing power values based on the received rate requests, optimizing the user stations'"'"' maximum transmit power, optimizing a discrete set of transmission rates, optimizing maximum rise-over-thermal interference, and optimizing minimum required error rate; and

transmitting first and second assignment signals to the first and second user stations, respectively, wherein the first and second assignment signals specify at least one transmission criteria at which the first and second user stations are to transmit data, respectively.

34. The computer-readable medium of claim 33 wherein receiving transmission requests includes receiving a transmission rate request, and wherein allocation of resources includes:

optimizing power values based on the received rate requests and interference from adjacent base stations; and

identifying rates corresponding to the optimized power values;

and wherein transmitting first and second assignment signals includes transmitting first and second identified rates.

35. The computer-readable medium of claim 33 wherein allocation of resources includes synchronously optimizing power values based on the received rate requests and interference from adjacent base stations.

36. The computer-readable medium of claim 33 wherein receiving transmission requests includes receiving a transmission rate request, and wherein allocation of resources includes assigning higher transmission rates for user stations closer to a center of a cell in which the first base station is located.

37. The computer-readable medium of claim 33 wherein allocation of resources includes, at each base station:

optimizing power values based on the received requests and interference from adjacent base stations;

identifying assignment signals corresponding to the optimized power values; and

repeating the optimizing and identifying, and wherein the repeating converges the optimizing to stable values among the base stations.

38. A computer-readable medium having instructions stored thereon to cause computers in a communication system to perform a method, wherein the system includes at least first and second base stations, the base stations having communications resources for exchanging communication signals with at least first and second user stations, respectively, the method comprising:

receiving transmission requests from the first and second user stations and other user stations, and allocating resources at the first and second base stations in response to the requests received from the first, second and other user stations, wherein the first base station optimizes the allocation of resources independently of the allocation of resources of the second base station and minimizes interference with the second base station in accordance with system stability and throughput, while the second base station optimizes the allocation of resources independently of the allocation of resources of the first base station and minimizes interference with the first base station, in accordance with system stability and throughput; and

transmitting first and second assignment signals to the first and second user stations, respectively, wherein the first and second assignment signals specify at least one transmission criteria at which the first and second user stations are to transmit data, respectively;

wherein allocation of resources includes optimizing transmission powers for N number of user stations for the first base station by optimizing;

$\underset{P}{\max }<br><br>\underset{i=1}{\stackrel{N}{\sum <br><br>}}<br><br>h_i<br><br>P_i,$

subject to;

 

A_minP≧

(I_oc+N₀)W1

39. A method for use in a communication system having at least first and second base stations exchanging communication signals with at least first and second user stations, respectively, the method comprising:

receiving, at the first and second base stations, transmission rate or power requests from the first and second user stations, respectively, and from other user stations;

independently from the second base station and in accordance with system stability and throughput, determining at the first base station optimum rate or power assignments, including an optimum rate or power assignment for the first user station, based on received requested rates or powers by weighting a sum of the requested rates or powers subject to predetermined rate or power values and subject to interference from the second base station, wherein the predetermined rate or power values include a user stations'"'"' maximum transmit power and a discrete set of transmission rates, and wherein weighting a sum of the requested rates or powers is also subject to maximum rise-over-thermal interference and minimum required error rate; and

at the first and second base stations, transmitting first and second rate or power assignment signals to the first and second user stations, all respectively, wherein the first and second assignment signals specify at least rate or power transmission criteria at which the first and second user stations are to transmit data, respectively.

40. The method of claim 39 wherein receiving transmission rate or power requests includes receiving a transmission rate request, and wherein determining optimum rate or power assignments includes:

optimizing power values based on the received rate requests and based on interference from adjacent base stations; and

identifying rates corresponding to the optimized power values;

and wherein transmitting first and second rate or power assignment signals includes transmitting first and second identified rates.

41. The method of claim 39 wherein receiving transmission rate or power requests includes receiving a transmission rate request, and wherein determining optimum rate or power assignments includes assigning higher transmission rates for user stations closer to a center of a cell in which the first base station is located.

42. A method for use in a communication system having at least first and second base stations exchanging communication signals with at least first and second user stations, respectively, the method comprising:

receiving, at the first and second base stations, transmission rate requests from the first and second user stations, respectively, and from other user stations;

at the first and second base stations, determining channel gains for the first and second user stations, respectively, and from other user stations;

independently from the second base station and in accordance with system stability and throughput, determining at the first base station optimum rate assignments, including an optimum rate assignment for the first user station, based on received requested rates by assigning higher rates for user stations having higher channel gains; and

independently from the first base station and in accordance with system stability and throughput, determining at the second base station optimum rate assignments, including an optimum rate assignment for the second user station, based on received requested rates by assigning higher rates for user stations having higher channel gains, wherein determining optimum rate assignments includes optimizing power values based on the received rate requests, user stations'"'"' maximum transmit power, a discrete set of transmission rates, maximum rise-over-thermal interference, and minimum required error rate; and

at the first and second base stations, transmitting first and second rate assignment signals to the first and second user stations, all respectively, wherein the first and second rate assignment signals specify at least rate transmission criteria at which the first and second user stations are to transmit data, respectively.

43. The method of claim 42 wherein determining optimum rate assignments includes:

optimizing power values based on the received rate requests and based on interference from adjacent base stations; and

identifying rates corresponding to the optimized power values.

44. The method of claim 42 wherein determining optimum rate assignments includes assigning higher transmission rates for user stations closer to a center of a cell in which the first base station is located.