Method and apparatus for determining optimal paths among objects of a communications network

• US 6,195,553 B1
• Filed: 04/20/1999
• Issued: 02/27/2001
• Est. Priority Date: 04/20/1999
• Status: Active Grant

• Current Assignee: Analytical Graphics
• Original Assignee: Analytical Graphics
• Inventors: Claffery, Douglas J., Holland, David M., Woodburn, James W.
• Primary Examiner(s): Bost, Dwayne D.
• Assistant Examiner(s): VUONG, QUOCHIEN B
• Application Number:
  US09/294,490
• Time in Patent Office: 679 Days
• Field of Search: 455/445, 455/426, 455/427, 455/428, 455/12.1, 455/405, 455/417, 455/13.1, 379/219, 379/220, 379/221, 379/114, 379/115
• US Class Current: 455/445
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04W 76/10 Connection setup
• CPC Class Codes: H04W 76/30 Connection release

Abstract

The present invention relates to a method and apparatus for selecting a path between an originating point and a destination point in a communications network comprising a number of objects for a certain time interval. The method comprises constructing a link availability matrix which comprises a start time and an end time for a link between any two objects in the communications network. The start time for all links in the link availability matrix are arranged in a chronological order. A cost matrix is generated for the first start time in the link availability matrix based on selected factors and continuing through the following start times until a connecting path is found between the originating point and destination point using a number of objects in the network. After a connecting path is found, a first disconnect time based on the end times in the link availability matrix for the objects in the connecting path is selected. Steps (c) and (d) are repeated for all subsequent start time in the link availability matrix for the time interval to identify other connecting paths for the origination and destination points. An optimal path is selected for the communication between the origination and destination points based on the selected factors. The invention also relates to the utilization of graphical depictions of the optimal path preferably on a computer showing Earth imagery and the location of the objects in the communication system.

Claims

1. A method for selecting a path between an originating point and a destination point in a communications network comprising a number of objects for a certain time interval, the method comprising:

a) constructing a link availability matrix which comprises a start time and an end time for a link between any two objects in the communications network;

b) arranging the start time for all links in the link availability matrix in a chronological order;

c) constructing a cost matrix for the first start time in the link availability matrix based on selected factors and continuing through the following start times until a connecting path is found between the originating point and destination point using a number of objects in the network;

d) after a connecting path is found, determining a first disconnect time based on the end times in the link availability matrix for the objects in the connecting path;

e) repeating steps c) and d) for all subsequent start time in the link availability matrix for the time interval to identify other connecting paths for the origination and destination points; and

f) selecting an optimal path for the communication between the origination and destination points based on the selected factors.

2. The method of claim 1 wherein the selected factors are selected from the group consisting of distance, location, interference factors, loading availability, reliability, costs, and other negative characteristics.

3. The method of claim 1 wherein the communications network comprises ground stations and satellites.

4. The method of claim 1 wherein the communications network comprises low Earth orbit satellites.

5. The method of claim 1 further comprising graphical means to display the optimal path for the communication including the available objects.

6. The method of claim 5 wherein the graphical means includes Earth imagery and relative position of the objects in the communications network.

7. A system for selecting an optimal path between an originating point and a destination point in a communications network comprising a number of objects for a certain time interval, the system comprising:

(a) means for constructing a link availability matrix which comprises a start time and an end time for a link between any two objects in the communications network;

(b) means for arranging the start time for all links in the link availability matrix in a chronological order;

(c) software for constructing a cost matrix for the first start time in the link availability matrix based on selected factors and continuing through the following start times until a connecting path is found between the originating point and destination point using a number of objects in the network;

(d) after a connecting path is found, means for determining a first disconnect time based on the end times in the link availability matrix for the objects in the connecting path; and

(e) software for repeating steps c) and d) for all subsequent start time in the link availability matrix for the time interval to identify other connecting paths for the origination and destination points.

8. The system of claim 7, further comprising software to show the optimal path imagery with a designation for the objects in the communication network.

9. A method for selecting a path between an originating point and a destination point in a communications network comprising a number of objects selected from the group comprising ground communication stations, communication satellites and other communication objects, for a certain time interval, the method comprising:

(a) constructing a link availability matrix which comprises a start time and an end time for a link between any two objects in the communications network;

(b) arranging the start time for all links in the link availability matrix in a chronological order;

(c) constructing a cost matrix for the first start time in the link availability matrix based on selected factors and continuing through the following start times until a connecting path is found between the originating point and destination point using a number of objects in the network;

(d) after a connecting path is found, determining a first disconnect time based on the end times in the link availability matrix for the objects in the connecting path;

(e) repeating steps (c) and (d) for all subsequent start time in the link availability matrix for the time interval to identify other connecting paths for the origination and destination points; and

(f) selecting an optimal path for the communication between the origination and destination points based on the selected factors.

10. The method of claim 9 wherein the selected factors are selected from the group consisting of distance, location, interference factors, loading availability, reliability, costs, and other negative characteristics.

11. The method of claim 9 wherein the communications network comprises low Earth orbit satellites.

12. The method of claim 9 further comprising graphical means to display the optimal path for the communication including the available objects.

13. The method of claim 12 wherein the graphical means includes Earth imagery and relative position of the objects in the communications network.