Method for allocating channels in a radio network using a genetic algorithm

• US 5,778,317 A
• Filed: 05/13/1996
• Issued: 07/07/1998
• Est. Priority Date: 05/13/1996
• Status: Expired due to Term

• Current Assignee: North South Holdings Incorporated (Spherix Incorporated)
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Kaminsky, Alan Richard
• Primary Examiner(s): Vo, Nguyen
• Assistant Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US08/645,098
• Time in Patent Office: 785 Days
• Field of Search: 455/33.1, 455/34.2, 455/34.1, 455/54.1, 455/56.1, 455/62, 455/63, 455/67.1, 455/450, 455/451, 455/452, 455/517, 455/524, 455/446, 455/447, 455/448, 455/449
• US Class Current: 455/450
• CPC Class Codes: H04W 16/14 Spectrum sharing arrangements between different networks
• CPC Class Codes: H04W 16/18 Network planning tools
• CPC Class Codes: H04W 28/16 Central resource management; Negotiation of resources or communication parameters, e.g. negotiating bandwidth or QoS [Quality of Service]

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. The method of claim 1 wherein the step of iteratively ranking further comprises the step of deleting lower ranked ones of the plans.

8. 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.

9. The method of claim 8 wherein the goodness vector comprises values on a scale which is continuous between best and worst.

10. 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.

11. 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.

12. The method of claim 11 further comprising the step of measuring the goodness factors on a scale which is continuous from best to worst.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. 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.

22. 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.

23. 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.

24. 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.