US5778317A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for allocating channels in a radio network using a genetic algorithm
Assignee: North South Holdings Inc
•
Filing: 1996-05-13
•
Granted: 1998-07-07
•
Expires: 2016-05-13
Abstract
Abstract A method of allocating radio channels among tactical networks of radio transceivers which uses fuzzy logic to evaluate quality of communication and which uses a genetic algorithm to find an optimal channel allocation plan. The method generates plural plans which each have a random allocation of the radio channels to the networks, and evaluates each plan to provide a goodness vector for each of the plans. The goodness vector is a vector of goodness values which are continuous from best to worst. The process iteratively ranks the evaluated plans based on their goodness vectors, uses higher ranked plans to generate further plans which are also ranked, and deletes lower ranked plans until the top ranked plan or the goodness vector does not change for a predetermined period. The channels are allocated in accordance with the top ranked plan.
Inventors
- 👤 Alan Richard Kaminsky
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 16:30
CPC Classifications
H; H04; H04W; H04W16/00; H04W16/14; H04W16/18; H04W28/00; H04W28/16
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
118 words
A method of planning allocation of channelized resources among networks of the resources, the method comprising the steps of: (a) generating plural plans for allocating the resources to the networks, each of the plural plans having a random allocation of the resources to the networks; (b) evaluating each of the plural plans to provide a vector for each of the plans which includes quality values on a scale which is continuous from best to worst; and (c) iteratively ranking the evaluated plans from best to worst based on the vector, and using higher ranked plans to generate further plans which are also ranked until the top ranked one of the plans does not change for a predetermined period.
Claim 2
Independent Claim
118 words
A method of planning allocation of channelized resources among networks of the resources, the method comprising the steps of: (a) generating plural plans for allocating the resources to the networks, each of the plural plans having a random allocation of the resources to the networks; (b) evaluating each of the plural plans to provide a vector for each of the plans which includes quality values on a scale which is continuous from best to worst; and (c) iteratively ranking the evaluated plans from best to worst based on the vector, and using higher ranked plans to generate further plans which are also ranked until the top ranked one of the plans does not change for a predetermined period.
Claim 3
Dependent Claim
43 words
The method of claim 1 wherein the step of generating further plural plans comprises the steps of selecting two of the plural plans using a distribution function which favors higher ranked plans, and forming a new plan by combining the selected two plans.
Claim 4
Dependent Claim
42 words
The method of claim 2 wherein the step of generating further plural plans comprises the steps of selecting one of the plural plans using a distribution function which favors higher ranked plans, and forming a new plan by mutating the selected plan.
Claim 5
Dependent Claim
35 words
The method of claim 1 wherein the step of ranking the plans comprises the steps of weighting the vector values and summing the weighted values to provide a numerical value for ranking the plural plans.
Claim 6
Dependent Claim
38 words
The method of claim 4 wherein the step of ranking the plans comprises the steps of assigning relative ranks to the vector values and wherein the weighted vector values which are summed are of the same relative rank.
Claim 7
Dependent Claim
27 words
The method of claim 1 wherein the predetermined period is determined by either a passage of time or number of further plural plans which have been added.
Claim 8
Dependent Claim
23 words
The method of claim 1 wherein the step of iteratively ranking further comprises the step of deleting lower ranked ones of the plans.
Claim 9
Independent Claim
178 words
A method of allocating radio channels among networks of radio transceivers where the number of possible allocation plans is vast, the method comprising the steps of: (a) generating plural plans for allocating the radio channels to the networks, each of the plural plans having a random allocation of the radio channels to the networks; (b) evaluating each of the plural plans to provide a goodness vector for each of the plans; (c) ranking the evaluated plans from best to worst based on the goodness vector; (d) adding further plural plans which are revisions of higher ranked ones of the plural plans until a predetermined number of further plural plans have been added; (e) performing steps (b) and (c) and deleting lower ranked ones of the plural plans; (f) repeating steps (d)-(e) until one of (i) the top ranked one of the plans and (ii) the goodness vector of the top ranked one of the plans does not change for a predetermined period; and (g) allocating the radio channels in accordance with the top ranked one of the plans.
Claim 10
Independent Claim
178 words
A method of allocating radio channels among networks of radio transceivers where the number of possible allocation plans is vast, the method comprising the steps of: (a) generating plural plans for allocating the radio channels to the networks, each of the plural plans having a random allocation of the radio channels to the networks; (b) evaluating each of the plural plans to provide a goodness vector for each of the plans; (c) ranking the evaluated plans from best to worst based on the goodness vector; (d) adding further plural plans which are revisions of higher ranked ones of the plural plans until a predetermined number of further plural plans have been added; (e) performing steps (b) and (c) and deleting lower ranked ones of the plural plans; (f) repeating steps (d)-(e) until one of (i) the top ranked one of the plans and (ii) the goodness vector of the top ranked one of the plans does not change for a predetermined period; and (g) allocating the radio channels in accordance with the top ranked one of the plans.
Claim 11
Dependent Claim
21 words
The method of claim 8 wherein the goodness vector comprises values on a scale which is continuous between best and worst.
Claim 12
Dependent Claim
27 words
The method of claim 8 wherein the predetermined period is determined by either a passage of time or number of further plural plans which have been added.
Claim 13
Dependent Claim
55 words
The method of claim 8 wherein the step of evaluating the plural plans comprises the step of considering at least one of following goodness factors: best-channels communication quality, average communication quality, channel count maximized, channel count minimized, frequency spread in range, frequency spread maximized, frequency spread uniformity, delay spread, inter-network spectrum reuse, and collocation interference.
Claim 14
Dependent Claim
24 words
The method of claim 11 further comprising the step of measuring the goodness factors on a scale which is continuous from best to worst.
Claim 15
Dependent Claim
43 words
The method of claim 8 wherein the step of adding further plural plans comprises the steps of selecting two of the plural plans using a distribution function which favors higher ranked plans, and forming a new plan by combining the selected two plans.
Claim 16
Dependent Claim
42 words
The method of claim 8 wherein the step of adding further plural plans comprises the steps of selecting one of the plural plans using a distribution function which favors higher ranked plans, and forming a new plan by mutating the selected plan.
Claim 17
Dependent Claim
31 words
The method of claim 8 wherein the step of evaluating the plural plans comprises the step of predicting the effect of skywave and groundwave propagation on reliability over time of day.
Claim 18
Dependent Claim
27 words
The method of claim 8 wherein the step of evaluating the plural plans comprises the step of predicting the probability of multipath propagation over time of day.
Claim 19
Dependent Claim
47 words
The method of claim 8 wherein each of the networks has a desired number of channels and wherein the step of evaluating the plural plans comprises the step of comparing the number of channels allocated under each of the plural plans to the desired number of channels.
Claim 20
Dependent Claim
35 words
The method of claim 8 wherein the step of evaluating the plural plans comprises the steps of determining an average communication quality over time for each of the plural plans and comparing the determined averages.
Claim 21
Dependent Claim
43 words
The method of claim 8 wherein each of the networks has a desired frequency spread and wherein the step of evaluating the plural plans comprises the step of comparing the frequency spread under each of the plural plans to the desired frequency spread.
Claim 22
Dependent Claim
43 words
The method of claim 8 wherein each of the networks has a desired delay spread and wherein the step of evaluating the plural plans comprises the step of comparing the delay spread under each of the plural plans to the desired delay spread.
Claim 23
Dependent Claim
54 words
The method of claim 8 wherein there is a maximum desired amount of inter-network frequency spectrum reuse and wherein the step of evaluating the plural plans comprises the step of comparing the amount of inter-network frequency spectrum reuse under each of the plural plans to the maximum desired amount of inter-network frequency spectrum reuse.
Claim 24
Dependent Claim
54 words
The method of claim 8 wherein there is a maximum desired amount of frequency spectrum collocation interference and wherein the step of evaluating the plural plans comprises the step of comparing the amount of frequency spectrum collocation interference under each of the plural plans to the maximum desired amount of frequency spectrum collocation interference.
Claim 25
Dependent Claim
35 words
The method of claim 8 wherein the step of ranking the plans comprises the steps of weighting goodness vector values and summing the weighted values to provide a numerical value for ranking the plural plans.
Claim 26
Dependent Claim
39 words
The method of claim 23 wherein the step of ranking the plans comprises the steps of assigning relative ranks to goodness vector values and wherein the weighted goodness vector values which are summed are of the same relative rank.
References Cited (Backward Citations)
US4935877A
Cited
US5293640A
Cited
US5355367A
Cited
US5038399A
Cited
US5245696A
Cited
US5428815A
Cited
US5394509A
Cited
US5404574A
Cited
US5390283A
Cited
US5557639A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-07-06 | 2002-01-05 | 2002-07-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-07-06 | 2006-01-05 | 2006-07-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-07-06 | 2010-01-05 | 2010-07-07 | $7700.00 | Window Closed / Lapsed |