Allocating resources in a frequency-time space to mobile station data

• US 8,300,591 B1
• Filed: 12/07/2007
• Issued: 10/30/2012
• Est. Priority Date: 12/08/2006
• Status: Expired due to Fees

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Bontu, Chandra, Hawryluck, Mark, Larijani, Parsya
• Primary Examiner(s): Ferris, Derrick
• Assistant Examiner(s): SMARTH, GERALD A
• Application Number:
  US11/999,919
• Time in Patent Office: 1,789 Days
• Field of Search: 370/330
• US Class Current: 370/330
• CPC Class Codes: H04J 11/00 Orthogonal multiplex systems, e.g. using WALSH codesH04J13/00 takes precedence
• CPC Class Codes: H04L 5/0007 the frequencies being orthogonal, e.g. OFDM(A), DMT
• CPC Class Codes: H04L 5/0037 Inter-user or inter-terminal allocation
• CPC Class Codes: H04L 5/0069 Allocation based on distance or geographical location allocation based on terminal or device properties in general, H04W72/51
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames

Abstract

To allocate resources in an orthogonal frequency domain multiple access (OFDMA) system, two-dimensional rectangular regions are assigned in a frequency-time space to data bursts associated with mobile stations. At least one data burst does not fit in an available space in the frequency-time space is determined. In response to the determining, the assigned two-dimensional rectangular regions are reshaped.

Claims

1. A method of allocating resources in an orthogonal frequency domain multiple access (OFDMA) system, comprising:

assigning, by a processor using an algorithm having at least one predefined shaping rule, two-dimensional rectangular regions in a frequency-time space to data bursts associated with mobile stations;

dividing a number of slots in the two-dimensional rectangular region allocated to each mobile station by prime factors;

providing the prime factors to a fitting algorithm;

using, by the fitting algorithm, the prime factors to further shape the two-dimensional rectangular regions;

determining, by the processor, that at least one data burst does not fit in an available space in the frequency-time space; and

in response to the determining, the processor reshaping the assigned two-dimensional rectangular regions, wherein reshaping the assigned two-dimensional rectangular regions comprises modifying a shape of at least a particular one of the assigned two-dimensional rectangular regions based on changing the at least one predefined shaping rule.

2. The method of claim 1, wherein assigning the two-dimensional rectangular regions in the frequency-time space is based on a criterion that specifies that the frequency-time space is to be as fully utilized as possible.

3. The method of claim 1, further comprising using combinations of the prime factors to define a height and a width of the two-dimensional rectangular region for each mobile station.

4. The method of claim 3, wherein using the prime factors to further shape the two-dimensional rectangular region for each mobile station comprises:

using the prime factors to define a wide rectangular region for a fast-moving mobile station; and

using the prime factors to define a tall, narrow rectangular region for a slow-moving mobile station, the slow-moving mobile station moving at a speed less than the fast-moving mobile station.

5. The method of claim 1, further comprising:

determining whether the number of slots is exactly divisible by the prime factors;

in response to determining that the number of slots is not exactly divisible by the prime factors, adjusting the number of slots in the corresponding two-dimensional rectangular region.

6. The method of claim 1, wherein assigning the two-dimensional rectangular regions in the frequency-time space comprises assigning the two-dimensional rectangular regions for downlink data bursts.

7. A method of allocating resources in an orthogonal frequency domain multiple access (OFDMA) system, comprising:

assigning, by a processor, two-dimensional rectangular regions in a frequency-time space to data bursts associated with mobile stations;

determining, by the processor, that at least one data burst does not fit in an available space in the frequency-time space;

in response to the determining, the processor reshaping the assigned two-dimensional rectangular regions; and

applying, by the processor, a fitting algorithm to further define the two-dimensional rectangular regions, where the fitting algorithm assigns differently shaped two-dimensional regions to fast-moving mobile stations and to slow-moving mobile stations, the fast-moving mobile stations moving at a speed greater than the slow-moving mobile stations, wherein the fitting algorithm increases a ratio of a width of the rectangular region to a height of the rectangular region for a mobile station that is fast moving, and increases a ratio of a height of the rectangular region to a width of the rectangular region for a mobile station that is slow moving.

8. The method of claim 7, wherein the fitting algorithm uses a criterion that specifies that data burst errors are to be reduced.

9. The method of claim 7, wherein the fitting algorithm specifies that the corresponding two-dimensional rectangular region is to be as close as possible to a square for a mobile station that is neither fast moving nor slow moving.

10. A base station comprising:

a wireless transceiver, configured to communicate with mobile stations;

wherein the base station is configured to implement a scheduler, wherein the schedule is configured to;

assign data bursts associated with mobile stations communicated with the base station to two-dimensional rectangular regions in a frequency-time space;

determine that at least one data burst does not fit in an available space in the frequency-time space;

in response to the determining, reshaping the assigned two-dimensional rectangular regions; and

apply a fitting algorithm to further define the two-dimensional rectangular regions, where the fitting algorithm assigns differently shaped two-dimensional regions to fast-moving mobile stations and to slow-moving mobile stations, the fast-moving mobile stations moving at a speed greater than the slow-moving mobile stations, wherein the fitting algorithm increases a ratio of a width of the rectangular region to a height of the rectangular region for a mobile station that is fast moving, and increases a ratio of a height of the rectangular region to a width of the rectangular region for a mobile station that is slow moving.

11. The base station of claim 10, wherein the scheduler is configured to further relax rules associated with shaping the two-dimensional rectangular regions according to the speeds of the mobile stations in reshaping the assigned two-dimensional rectangular regions.

12. The base station of claim 10, wherein the shaping of the two-dimensional rectangular regions is based on a first shaping rule for fast-moving mobile stations having speeds above a first threshold, and a second, different shaping rule for slow-moving mobile stations having speeds below a second threshold.

13. The base station of claim 10, wherein the scheduler is implemented as part of a medium access control (MAC) layer of the base station.

14. The base station of claim 10, wherein the base station further comprises:

a processor; and

a memory medium coupled to the processor, wherein the memory medium stores program instructions executable by the processor to implement at least a portion of the scheduler.

15. An article comprising at least one non-transitory computer-readable storage medium containing instructions that when executed cause a system to:

assign, using an algorithm having at least one predefined shaping rule, two-dimensional rectangular regions in a frequency-time space to data bursts associated with mobile stations;

divide a number of slots in the two-dimensional rectangular region allocated to each mobile station by prime factors;

provide the prime factors to a fitting algorithm;

use, by the fitting algorithm, the prime factors to further shape the two-dimensional rectangular regions;

determine that at least one data burst does not fit in an available space in the frequency-time space; and

in response to the determining, reshape the assigned two-dimensional rectangular regions, wherein reshaping the assigned two-dimensional rectangular regions comprises modifying a shape of at least a particular one of the assigned two-dimensional rectangular regions based on changing the at least one predefined shaping rule.

16. The article of claim 15, wherein the instructions when executed cause the system to further use combinations of the prime factors to define a height and a width of the two-dimensional rectangular region for each mobile station.

17. An article comprising at least one non-transitory computer-readable storage medium containing instructions that when executed cause a system to:

assign two-dimensional rectangular regions in a frequency-time space to data bursts associated with mobile stations;

determine that at least one data burst does not fit in an available space in the frequency-time space;

in response to the determining, reshape the assigned two-dimensional rectangular regions; and

apply a fitting algorithm to further shape the two-dimensional rectangular regions, where the fitting algorithm assigns differently shaped two-dimensional regions to fast-moving mobile stations and to slow-moving mobile stations, the fast-moving mobile stations moving at a speed greater than the slow-moving mobile stations, wherein the fitting algorithm increases a ratio of a width of the rectangular region to a height of the rectangular region for a mobile station that is fast moving, and increases a ratio of a height of the rectangular region to a width of the rectangular region for a mobile station that is slow moving.

18. The article of claim 17, wherein the fitting algorithm specifies that the corresponding two-dimensional rectangular region is to be as close as possible to a square for a mobile station that is neither fast moving nor slow moving.