US6987738B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for packet scheduling and radio resource allocation in a wireless communication system
Assignee: Google Technology Holdings LLC
•
Filing: 2001-01-12
•
Granted: 2006-01-17
•
Expires: 2021-01-12
Abstract
Abstract A method of performing packet level transmission scheduling in a communications systems including a plurality of cells, each cell including a base station and plurarity of mobile stations. The method performs scheduling while considering radio resource allocation at the wireless access node. In a schedule plan phase of the method, average power and average effective data rate are determined for all mobile stations in the system. In addition, the planned fractions of frames ρ that each mobile in the system will transmit is determined so that resources are allocated fairly. In the actual schedule phase of the method, current power and effective data rate values are compared to the average power values. This information along with the ρ values is used to determine the actual schedule of packet transmissions for all mobiles in a particular cell.
Inventors
- 👤 Vijay G. Subramanian
- 👤 Rajeev Agarwal
- 👤 Richard J. La
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 16:57
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/50; H04L47/56; H04L47/10; H04L47/62; H04L47/625; H04L47/626; H04W; H04W28/00; H04W28/02; H04W28/0231; H04W28/0236; H04W72/00; H04W72/50; H04W72/54; H04W8/00; H04W8/02; H04W8/04; H04W24/00; H04W28/16; H04W28/18; H04W28/22; H04W72/04; Y; Y02; Y02D; Y02D30/00; Y02D30/70
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
196 words
In a communications system comprising a plurality of cells, each cell having a base station and a plurality of mobile stations, a method of scheduling packet transmission comprising: a) determining a nominal power level for all base stations in the system; b) determining an average effective data rate for all mobile stations in the system; c) using the nominal power level and average effective data rate to determine a tentative transmission schedule for each of the plurality of mobile stations in the system; d) determining an actual power value for each of the plurality of mobile stations in a particular cell; e) determining an actual effective data rate for each of the plurality of mobile stations in the cell; f) determining a present credit value for each of the plurality of mobile stations in the cell; g) determining which mobile station of the plurality of mobile stations has a lowest amount of normalized bytes transmitted, wherein normalized bytes transmitted is calculated as a function of the present credit value for each of the plurality of mobile stations in the cell; and h) scheduling for transmission, the mobile station with the lowest amount of normalized bytes transmitted.
Claim 2
Dependent Claim
196 words
In a communications system comprising a plurality of cells, each cell having a base station and a plurality of mobile stations, a method of scheduling packet transmission comprising: a) determining a nominal power level for all base stations in the system; b) determining an average effective data rate for all mobile stations in the system; c) using the nominal power level and average effective data rate to determine a tentative transmission schedule for each of the plurality of mobile stations in the system; d) determining an actual power value for each of the plurality of mobile stations in a particular cell; e) determining an actual effective data rate for each of the plurality of mobile stations in the cell; f) determining a present credit value for each of the plurality of mobile stations in the cell; g) determining which mobile station of the plurality of mobile stations has a lowest amount of normalized bytes transmitted, wherein normalized bytes transmitted is calculated as a function of the present credit value for each of the plurality of mobile stations in the cell; and h) scheduling for transmission, the mobile station with the lowest amount of normalized bytes transmitted.
Claim 3
Dependent Claim
88 words
The method of claim 1 wherein step b) comprises the steps of: i) approximating a signal to interference plus noise ratio (SINR) for each of the plurality of mobile stations in the system; ii) using the SINR to determine at least one of a modulation and coding scheme, a spreading factor and an effective data rate for each of the plurality of mobile stations in the system; and iii) using the effective data rate to determine the average effective data rate for all mobile stations in the system.
Claim 4
Dependent Claim
34 words
The method of claim 2 wherein the step of approximating the SINR comprises using the nominal power level, a present gain, a present interference channel gain and receiver noise power plus unaccounted interference terms.
Claim 5
Dependent Claim
43 words
The method of claim 3 wherein the present gain, the present interference channel gain and receiver noise power plus unaccounted interference terms are obtained by polling transceivers at each of the plurality of mobile stations and the base station for a measurement report.
Claim 6
Dependent Claim
20 words
The method of claim 2 wherein the step of approximating the SINR comprises obtaining the SINR from a measurement report.
Claim 7
Dependent Claim
28 words
The method of claim 2 wherein step ii) comprises using a plot of signal to interference plus noise ratio vs. FER to determine the modulation and coding scheme.
Claim 8
Dependent Claim
40 words
The method of claim 6 further comprising using a plot of signal to interference plus noise ratio vs. effective data rate and the modulation and coding scheme to determine the effective data rate for each mobile station in the system.
Claim 9
Dependent Claim
37 words
The method of claim 1 wherein step c) further comprises using the average effective data rate to determine a planned fraction of frames to be used by each of the plurality of mobile stations in the system.
Claim 10
Dependent Claim
33 words
The method of claim 1 wherein step d) comprises using the nominal power level and present values of gain and interference terms in a power control algorithm to determine the actual power value.
Claim 11
Dependent Claim
36 words
The method of claim 1 wherein step e) comprises using the nominal power level and present values of gain and interference terms in a link data rate adaptation algorithm to determine the actual effective data rate.
Claim 12
Dependent Claim
52 words
The method of claim 1 wherein step f) comprises using the actual effective date rate, the average effective data rate and a quality of service of each mobile station of the plurality of mobile stations in the cell to compute the present credit value of each of the plurality of mobile stations.
Claim 13
Dependent Claim
23 words
The method of claim 1 further comprising the step of updating the amount of normalized bytes for each mobile station in the cell.
Claim 14
Dependent Claim
43 words
The method of claim 1 further comprising the steps of: i) when system resources have not been exhausted, scheduling for transmission, the mobile station with a next lowest amount of normalized bytes transmitted; and j) repeating step i) until system resources are exhausted.
Claim 15
Dependent Claim
74 words
The method of claim 1 wherein the average effective data rate in step b) is defined as {circumflex over (R)} j,avg new and is calculated as {overscore (R)} j,avg new =(1−τ)· {circumflex over (R)} j,avg old +τ·{circumflex over (R)} j , wherein τ is an exponential filter coefficient and τ(0≦τ≦1), {circumflex over (R)} j is a present actual effective date rate and {circumflex over (R)} j,avg old is a previous average effective data rate.
Claim 16
Dependent Claim
88 words
The method of claim 1 wherein the present credit value in step f) is defined as C j and is calculated as C j = w j R ^ j , avg β ( R ^ j R ^ j , avg ) γ , wherein w j is a QoS weight, {circumflex over (R)} j,avg is an average effective date rate, {circumflex over (R)} j is a present actual effective date rate, β is a first fairness parameter and γ is a second fairness parameter.
Claim 17
Dependent Claim
135 words
The method of claim 1 , wherein step g) comprises: for the plurality of mobile stations, determining an amount of normalized bytes to transmit at a beginning of a scheduling interval by updating a quantity {overscore (W)} j a first time using W _ j = W _ j + ϕ · number of bytes transmitted j C j ; updating quantity {overscore (W)} j a second time using {overscore (W)} j =(1−φ)·{overscore (W)} j ; calculating the normalized bytes to transmit as {overscore (W)} j ; and sorting the normalized bytes, {overscore (W)} j , to determine which mobile station of the plurality of mobile stations has the lowest amount of normalized bytes transmitted; wherein φ is a discount factor and C j is the present credit value.
Claim 18
Dependent Claim
55 words
The method of claim 1 wherein the present credit value in step f) is defined as C j and is calculated as C j =w j {circumflex over (R)} j,avg β , wherein w j is a QoS weight, {circumflex over (R)} j,avg is an average effective date rate, and β is a fairness parameter.
Claim 19
Dependent Claim
168 words
The method of claim 1 , wherein step g) comprises: for the plurality of mobile stations, determining an amount of normalized bytes to transmit at a beginning of a scheduling interval by updating a quantity {overscore (W)} j a first time using W _ j = W _ j + ϕ · number of bytes transmitted j C j updating quantity {overscore (W)} j a second time using {overscore (W)} j =(1−φ)·{overscore (W)} j ; calculating the normalized bytes to transmit as W _ j ( R ^ j , avg R ^ j ) γ ; and sorting the normalized bytes to determine which mobile station of the plurality of mobile stations has the lowest amount of normalized bytes transmitted wherein φ is a discount factor, C j is the present credit value, {circumflex over (R)} j,avg is an average effective date rate, {circumflex over (R)} j is a present actual effective date rate and γ is a fairness parameter.
References Cited (Backward Citations)
US6069883A
Cited
US6335922B1
Cited
US5923650A
Cited
US6333927B1
Cited
WO2000014900A1
Cited
US6519705B1
Cited
US6567387B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2009-01-16 | 2009-07-18 | 2010-01-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2013-01-16 | 2013-07-18 | 2014-01-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2017-01-16 | 2017-07-18 | 2018-01-17 | $7700.00 | Window Closed / Lapsed |