US5455821A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Communication system resource allocation method
Assignee: Google Technology Holdings LLC
•
Filing: 1994-11-10
•
Granted: 1995-10-03
•
Expires: 2014-11-10
Abstract
Abstract A method of allocating communication resources in a communication system includes retrieving (404) from the communication system a communication system resource allocation. An allocation parameter is set to an initial value (406) and communication resources are randomly selected from cells (414). A candidate communication resource is either swapped or mutated for the selected communication resource (416) and the system performance is evaluated with the candidate communication resource (422). If system performance is improved the candidate resource is retained as part of the allocation (426, 432), or if system performance is degraded, the candidate resource is retained with a probability (428, 432). The steps repeat while the allocation parameter is valid (408), and upon completion a new communication resource allocation is downloaded to the communication system (410).
Inventors
- 👤 Dennis R. Schaeffer
- 👤 Mark T. Ahlenius
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 14:51
CPC Classifications
H; H04; H04W; H04W16/00; H04W16/02; H04W16/04; H04W16/10; H04W16/12; H04W24/00; H04W24/02; H04W28/00; H04W28/16; H04W28/18; H04W72/00; H04W72/02; H04W72/04
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
211 words
A method of allocating communication resources in a communication system comprising the steps of: a) retrieving from the communication system a communication system resource allocation; b) setting an allocation parameter to an initial value; c) randomly selecting from a cell of the communication system an allocated communication resource; d) identifying a candidate communication resource within the communication system by either randomly selecting the candidate communication resource from another cell of the communication system with a first probability or randomly selecting the candidate communication resource from a plurality of available communication resources with a second probability; e) switching the candidate communication resource for the allocated communication resource; f) evaluating a system performance metric; g) accepting the candidate communication resource if the system performance metric is improved; h) accepting with a third probability the candidate communication resource if the system performance metric is degraded; i) rejecting the candidate communication resource if it is not accepted in either the step (g) or the step (h) and replacing the candidate communication resource with the allocated communication resource; j) adjusting the allocation parameter according to a defined schedule; k) repeating the steps (c) through (i) while the allocation parameter exceeds a threshold value; and l) downloading the communication system resource allocation to the communication system database.
Claim 2
Independent Claim
211 words
A method of allocating communication resources in a communication system comprising the steps of: a) retrieving from the communication system a communication system resource allocation; b) setting an allocation parameter to an initial value; c) randomly selecting from a cell of the communication system an allocated communication resource; d) identifying a candidate communication resource within the communication system by either randomly selecting the candidate communication resource from another cell of the communication system with a first probability or randomly selecting the candidate communication resource from a plurality of available communication resources with a second probability; e) switching the candidate communication resource for the allocated communication resource; f) evaluating a system performance metric; g) accepting the candidate communication resource if the system performance metric is improved; h) accepting with a third probability the candidate communication resource if the system performance metric is degraded; i) rejecting the candidate communication resource if it is not accepted in either the step (g) or the step (h) and replacing the candidate communication resource with the allocated communication resource; j) adjusting the allocation parameter according to a defined schedule; k) repeating the steps (c) through (i) while the allocation parameter exceeds a threshold value; and l) downloading the communication system resource allocation to the communication system database.
Claim 3
Dependent Claim
16 words
The method of claim 1 wherein the third probability is a function of the allocation parameter.
Claim 4
Dependent Claim
26 words
The method of claim 1 further comprising prior to the step (j), the step of repeating the steps (c) through (i) a first number of times.
Claim 5
Dependent Claim
33 words
The method of claim 1 wherein the step (j) further comprises, measuring an acceptance rate of candidate communication resources and adjusting the allocation parameter if the acceptance rate is less an acceptance threshold.
Claim 6
Dependent Claim
33 words
The method of claim 4 further comprising after the step (j) freezing communication resources allocated to the cell if failed consecutive attempts to substitute candidiate communication resources therefore goes above a freeze threshold.
Claim 7
Dependent Claim
18 words
The method of claim 5 wherein the step (c) further comprises randomly selecting a non-frozen allocated communication resource.
Claim 8
Dependent Claim
15 words
The method of claim 1 wherein the step (f) comprises determining a system interference value.
Claim 9
Dependent Claim
41 words
The method of claim 7 wherein the step of determining a system interference value comprises determining an interference level between the candidate communication resource and an interfering communication resource as the inverse of the carrier-to-interferer ratio expressed as a power ratio.
Claim 10
Dependent Claim
37 words
The method of claim 8 wherein the step of calculating a system interference value further comprises: ii) identifying a type of the interfering communication resource; and iii) modifying the system interference value in response to the type.
Claim 11
Dependent Claim
46 words
The method of claim 9 wherein the step of calculating a system interference value further comprises: vi) repeating the steps (i) through (iii) for a plurality of interfering communication resources; and v) summing the system interference value for each of the plurality of interfering communication resources.
Claim 12
Dependent Claim
18 words
The method of claim 1 wherein the communication system comprises a time division multiple access (TDMA) communication system.
Claim 13
Dependent Claim
25 words
The method of claim 1 wherein the allocated communication channel comprises a pair of radio frequencies in a frequency division multiple access (FDMA) communication system.
Claim 14
Dependent Claim
225 words
A communication system resource allocation method comprising the steps of: a) retrieving from a communication system database a communication system resource allocation; b) setting an allocation parameter to an initial value; c) randomly selecting from a cell of the communication system a changeable communication resource; d) identifying a candidate communication resource within the communication system by either randomly selecting the candidate communication resource from another cell of the communication system with a first probability or randomly selecting the candidate communication resource from a plurality of available communication resources with a second probability; e) switching the candidate communication resource for the allocated communication resource; f) evaluating system performance with the candidate communication resource; g) accepting the candidate communication resource if the system performance is improved h) accepting the candidate communication resource if the system performance is degraded with a third probability i) rejecting the candidate communication resource if it is not accepted in either the step (g) or the step (h) and replacing the candidate communication resource with the changeable communication resource; j) repeating the steps (c) through (i) a first number of times; k) adjusting the allocation parameter according to a defined schedule; l) repeating steps (c) through (j) a second number of times while the allocation parameter exceeds a threshold value; and m) downloading the communication system resource allocation to the communication system database.
Claim 15
Dependent Claim
225 words
A communication system resource allocation method comprising the steps of: a) retrieving from a communication system database a communication system resource allocation; b) setting an allocation parameter to an initial value; c) randomly selecting from a cell of the communication system a changeable communication resource; d) identifying a candidate communication resource within the communication system by either randomly selecting the candidate communication resource from another cell of the communication system with a first probability or randomly selecting the candidate communication resource from a plurality of available communication resources with a second probability; e) switching the candidate communication resource for the allocated communication resource; f) evaluating system performance with the candidate communication resource; g) accepting the candidate communication resource if the system performance is improved h) accepting the candidate communication resource if the system performance is degraded with a third probability i) rejecting the candidate communication resource if it is not accepted in either the step (g) or the step (h) and replacing the candidate communication resource with the changeable communication resource; j) repeating the steps (c) through (i) a first number of times; k) adjusting the allocation parameter according to a defined schedule; l) repeating steps (c) through (j) a second number of times while the allocation parameter exceeds a threshold value; and m) downloading the communication system resource allocation to the communication system database.
Claim 16
Dependent Claim
16 words
The method of claim 13 wherein the third probability is a function of the allocation parameter.
Claim 17
Dependent Claim
33 words
The method of claim 14 wherein the step (k) further comprises, measuring an acceptance rate of candidate communication resources and adjusting the allocation parameter if the acceptance rate is less an acceptance threshold.
Claim 18
Dependent Claim
31 words
The method of claim 15 further comprising after the step (k) marking as non-changeable communication resources if failed consecutive attempts to substitute candidiate communication resources therefore goes above a freeze threshold.
Claim 19
Dependent Claim
15 words
The method of claim 13 wherein the step (f) comprises calculating a system interference value.
Claim 20
Dependent Claim
41 words
The method of claim 17 wherein the step of calculating a system interference value comprises determining an interference level between the candidate communication resource and an interfering communication resource as the inverse of the carrier-to-interferer ratio expressed as a power ratio.
Claim 21
Dependent Claim
37 words
The method of claim 18 wherein the step of calculating a system interference value further comprises: ii) identifying a type of the interfering communication resource; and iii) modifying the system interference value in response to the type.
Claim 22
Dependent Claim
49 words
The method of claim 18 wherein the step of calculating a system interference value further comprises the steps of: vi) repeating the steps (i) through (iii) for a plurality of interfering communication resources; and v) summing the system interference value for each of the plurality of interfering communication resources.
Claim 23
Dependent Claim
37 words
The method of claim 20 wherein the step of identifying a type of the interfering communication resource comprises determining if the interfering communication resource belongs to a neighbor cell, a same site cell or a same cell.
Claim 24
Dependent Claim
34 words
The method of claim 20 wherein the step of identifying a channel type of the interfering communication resource comprises determining if the interfering channel is a co-channel communication resource or an adjacent-channel communication resource.
Claim 25
Independent Claim
298 words
A method of allocating communication channels in a cellular communication system comprising the steps of: a) retrieving from a communication system database a communication channel allocation; b) setting an allocation parameter to an initial value; c) randomly selecting from a cell of the communication system a changeable communication channel; d) identifying a candidate communication channel within the communication system by either randomly selecting the candidate communication channel from another cell of the communication system with a first probability or randomly selecting the candidate communication channel from a plurality of available communication channels with a second probability; e) switching the candidate communication channel for the allocated communication channel; f) calculating a system interference value by: i) determining an interference level between the candidate communication resource and an interfering communication resource as the inverse of the carrier-to-interferer ratio expressed as a power ratio; ii) identifying a type of the interfering channel; iii) modifying the interference level in response to the type; iv) repeating the steps (i) through (iii) for a plurality of interfering channels; and v) summing the interference level for each of the plurality of interfering channels; g) accepting the candidate communication channel if the system performance is improved; h) accepting the candidate communication channel if the system performance is degraded with a third probability; i) rejecting the candidate communication channel if it is not accepted in either the step (g) or the step (h) and replacing the candidate communication channel with the changeable communication channel; j) repeating the steps (c) through (i) a first number of times; k) adjusting the allocation parameter according to a defined schedule; l) repeating steps (c) through (j) a second number of times while the allocation parameter exceeds a threshold value; and m) downloading the communication channel allocation to the communication system database.
Claim 26
Independent Claim
298 words
A method of allocating communication channels in a cellular communication system comprising the steps of: a) retrieving from a communication system database a communication channel allocation; b) setting an allocation parameter to an initial value; c) randomly selecting from a cell of the communication system a changeable communication channel; d) identifying a candidate communication channel within the communication system by either randomly selecting the candidate communication channel from another cell of the communication system with a first probability or randomly selecting the candidate communication channel from a plurality of available communication channels with a second probability; e) switching the candidate communication channel for the allocated communication channel; f) calculating a system interference value by: i) determining an interference level between the candidate communication resource and an interfering communication resource as the inverse of the carrier-to-interferer ratio expressed as a power ratio; ii) identifying a type of the interfering channel; iii) modifying the interference level in response to the type; iv) repeating the steps (i) through (iii) for a plurality of interfering channels; and v) summing the interference level for each of the plurality of interfering channels; g) accepting the candidate communication channel if the system performance is improved; h) accepting the candidate communication channel if the system performance is degraded with a third probability; i) rejecting the candidate communication channel if it is not accepted in either the step (g) or the step (h) and replacing the candidate communication channel with the changeable communication channel; j) repeating the steps (c) through (i) a first number of times; k) adjusting the allocation parameter according to a defined schedule; l) repeating steps (c) through (j) a second number of times while the allocation parameter exceeds a threshold value; and m) downloading the communication channel allocation to the communication system database.
Claim 27
Dependent Claim
16 words
The method of claim 23 wherein the third probability is a function of the allocation parameter.
Claim 28
Dependent Claim
33 words
The method of claim 24 wherein the step (k) further comprises, measuring an acceptance rate of candidate communication channels and adjusting the allocation parameter if the acceptance rate is less an acceptance threshold.
Claim 29
Dependent Claim
32 words
The method of claim 25 further comprising after the step (k) marking as non-changeable communication channels if failed consecutive attempts to substitute a candidate communication resource therefore goes above a freeze threshold.
Claim 30
Dependent Claim
34 words
The method of claim 23 wherein the step of identifying a type of the interfering channel comprises determining if the channel belongs to a neighbor cell, a same site cell or a same cell.
Claim 31
Dependent Claim
30 words
The method of claim 27 wherein the step of identifying a channel type of the interfering channel further comprises determining if the interfering channel is a co-channel or an adjacent-channel.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-10-02 | 1999-04-03 | 1999-10-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-10-02 | 2003-04-03 | 2003-10-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-10-02 | 2007-04-03 | 2007-10-03 | $7700.00 | Window Closed / Lapsed |