Method of allocating links between a set of areas and a set of satellites

• US 6,259,913 B1
• Filed: 08/02/1999
• Issued: 07/10/2001
• Est. Priority Date: 08/06/1998
• Status: Expired due to Fees

• Current Assignee: Alcatel SA (Nokia Corporation)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Gaudin, Etienne, Noreils, Fabrice
• Primary Examiner(s): Urban, Edward F.
• Assistant Examiner(s): Milord, Marceau
• Application Number:
  US09/365,398
• Time in Patent Office: 708 Days
• Field of Search: 455/427, 455/429, 455/12.1, 455/13.3, 455/25, 455/424, 455/67.3, 455/67.4, 455/67.6, 455/450, 455/514, 455/509, 455/447, 370/323, 370/317, 370/316
• US Class Current: 455/429
• CPC Class Codes: H04B 7/2123 Variable assignment, e.g. demand assignment

Abstract

A method of allocating links between a set of satellites and a set of areas on the ground, the links being determined by a channel, includes the following steps, which are iterated for each channel and for each satellite: constructing an interference graph, and use of the graph by a search algorithm associated with a constraints propagation algorithm to verify the capacities. Applications include satellite communications.

Claims

1. A method of allocating links between a set of satellites and a set of areas on the ground each equipped with at least one gateway, said links being determined by a channel, said method comprising the following steps, which are iterated for each channel and for each satellite:

constructing an interference graph,

using said graph by a search algorithm associated with a constraints propagation algorithm to determine the greatest number of said areas toward which a beam from said each satellite can be pointed by allocating said channel to said beam.

2. The method of allocating links claimed in claim 1 wherein the construction of said graph at a time at which a satellite covers a number of areas with a number of beams and a number of channels includes the following steps:

constructing said graph for said satellite in which each node of said graph corresponds to an area such that the number of channels demanded for said area is greater than the number of channels allocated,

updating said graph by removing or adding an area as and when links are allocated.

5. The method of allocating links claimed in claim 1 wherein said iteration for each channel and for each satellite consists in reiterating all the steps of said method for another channel up to the last channel and then reiterating all of the preceding steps for another satellite up to the last satellite.

8. The method of allocating links claimed in claim 1 wherein said each satellite has a steerable antenna.

3. A method of allocating links between a set of satellites and a set of areas on the ground each equipped with at least one gateway, said links being determined by a channel, said method comprising the following steps, which are iterated for each channel and for each satellite:

constructing an interference graph,

use of said graph by a search algorithm associated with a constraints propagation algorithm to verify the capacities,

wherein the search algorithm uses the following steps;

calculating an interference coefficient for each pair of areas of the graph for a channel,

comparing the sum of the interference coefficients for each area to a predetermined maximum acceptable interference threshold,

creating a partition of at most the same number of elements as the number of beams and which includes a number of areas such that for each area the sum of said interference coefficients does not exceed said predetermined threshold.

4. The method of allocating links claimed in claim 3 wherein the creation of said partition includes the following steps:

taking a candidate area from said partition,

verifying that the number of channels demanded for said area is equal to the maximum number of channels for said area, in which case said area is included in said partition,

completing said partition with the other candidate areas for which the verification result is negative but for which the sum of said interference coefficients does not exceed said threshold.

6. The method of allocating links claimed in claim 3 wherein the construction of said graph at a time at which a satellite covers a number of areas with a number of beams and a number of channels includes the following steps:

constructing said graph for said satellite in which each node of said graph corresponds to an area such that the number of channels demanded for said area is greater than the number of channels allocated,

updating said graph by removing or adding an area as and when links are allocated.

7. The method of allocating links claimed in claim 3 wherein said iteration for each channel and for each satellite consists in reiterating all the steps of said method for another channel up to the last channel and then reiterating all of the preceding steps for another satellite up to the last satellite.

9. The method of allocating links claimed in claim 3 wherein said each satellite has a steerable antenna.