Method of optimizing an interplanetary communications network

• US 10,142,013 B2
• Filed: 05/16/2007
• Issued: 11/27/2018
• Est. Priority Date: 12/20/2006
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: El-Damhougy, Hesham, Jarett, Keith
• Primary Examiner(s): Swearingen, Jeffrey R
• Application Number:
  US11/749,172
• Publication Number:
  US 20080155070A1
• Time in Patent Office: 4,213 Days
• Field of Search: None
• CPC Class Codes: G06F 15/177 Initialisation or configuration control processor initialisation G06F9/4405
• CPC Class Codes: H04B 7/18584 Arrangements for data networking, i.e. for data packet routing, for congestion control data switching networks H04L12/00

Abstract

A method of designing an interplanetary communications network with an Artificial Neural Network (ANN) at each node. Object functions are generated that relate network characteristics and performance. Each object function is driven to an extreme (min or max) to provide an optimum network configuration. The optimum network configuration includes the number of nodes and the number of antennas for each node, node placement, specific node storage capacity and communications capacity for nodes and for links between nodes.

Claims

1. A method of optimizing a communications network, said method comprising:

providing an initial network configuration for an interplanetary communications network, said interplanetary communications network having a plurality (k) of nodes;

providing forecasts of traffic demand in said interplanetary communications network;

determining objective functions by a computer responsive to said demands and characterizing communications over links between said nodes in said network;

determining by said computer at least one limit for each said objective function;

adjusting said initial network configuration, and thereby producing an adjusted network configuration, responsive to said at least one limit for each said objective function; and

deploying said interplanetary communications network with said adjusted network configuration.

2. A method as in claim 1, wherein the provided initial network configuration includes a network topology description, routing metrics and expected network utilization.

3. A method as in claim 2, wherein the routing metrics include specific link capacities and a time varying link description (W(t)).

4. A method as in claim 2, wherein the expected network utilization includes link and node demand forecasts.

5. A method as in claim 2, wherein during the step of determining objective functions said computer generates a routing model defining communications routes between nodes and end to end in said network.

6. A method as in claim 5, wherein said computer applies weights to links in defined said communications routes.

7. A method as in claim 6, wherein after determining objective function limits, the method further comprises the step:

returning to determining objective functions, said computer returning traffic demands results from said routing model, and further providing said objective functions responsive to said traffic demands results.

8. A method as in claim 1, where adjusting said initial network configuration comprises changing storage capacity on at least one node.

9. A method as in claim 1, where adjusting said initial network configuration comprises changing the number of antennas on at least one node.

10. A method as in claim 1, wherein the determined objective function limits are selected from the group consisting of residual link and buffer capacity, average residual link and buffer capacity, and utilization of a most bottlenecked link and buffer capacity.

11. A method as in claim 1 further comprising, after said interplanetary communications network is deployed, adding one or more nodes to said interplanetary communications network or removing one or more of the plurality of nodes of said interplanetary communications network.

12. A method of designing an optimized communications network, said method comprising:

providing to a computer an initial network topology for an interplanetary communications network;

defining network communications indicating time varying communications links between network nodes;

providing a traffic demand matrix indicating communications requirements between network nodes;

determining objective functions for said interplanetary communications network by said computer responsive to defined said network communications and said traffic demand matrix;

driving each objective function to a selected limit by said computer, said objective function at said selected limit being identified as indicating an optimum interplanetary communications network configuration;

adjusting an initial network configuration, and thereby producing an adjusted network configuration, responsive to said objective function at said selected limit; and

deploying said interplanetary communications network with said adjusted network configuration.

13. A method as in claim 12, wherein the provided initial network topology includes node orbital parameters and a description of node motion.

14. A method as in claim 12, wherein defining network communications comprises:

determining contact windows in said time varying communications links between said nodes, contact windows being described in a window matrix (W); and

determining sub-windows in ones of said contact windows.

15. A method as in claim 12, wherein determining objective functions comprises:

determining objective function parameters;

determining objective function variables; and

determining objective function constraints.

16. A method as in claim 15, wherein for each node i, the objective function parameters comprise:

a traffic demand matrix (M(W)) during contact windows (W);

a set (N(ω

_ij)) of available links to neighboring nodes j during a contact window (ω

_ij);

a maximum number of active links (α

_ij);

a number (N_ij) of available links during a contact window (ω

_ij);

a data transport cost (B_ij) through said node i to said neighboring nodes j; and

a buffer storage cost (buff_i) for storing data.

17. A method as in claim 16, wherein the objective function variables comprise:

an end-to-end link traffic load (X^nm_ij);

a total link traffic load (F_ij);

a node traffic (K^nm_ij) from end-to-end link traffic;

a total node traffic (X^nm_i) stored at said node i from end-to-end link traffic;

a total link stored node traffic (K_ij);

a total stored node traffic (K_i); and

a link activation (A_ij) function indicating active links.

18. A method as in claim 17, wherein the objective function parameters further comprise:

a set of contact windows (W);

a set of window complements (C(W));

a link capacity to neighboring nodes j (C_ij); and

a node buffer storage size (b_i).

19. A method as in claim 18, wherein the objective function constraints comprise:

a total link load (g_j), where for link load a_ij, g_i≤

a_ij;

a demand responsive flow allocation to neighboring node j (h_j), where h_j=_j; and

a set of feasible solutions (x∈

X) to the objective function (ƒ

(x)).

20. A method as in claim 19, wherein the objective function constraints are linear and driving each objective function to a selected limit comprises said computer applying linear programming.

21. A method as in claim 20, wherein said linear programming is mixed integer linear programming.

22. A method as in claim 19, wherein said computer driving each objective function to a selected limit optimizes the objective function for residual link and buffer capacity according to Maximize

{Σ

<sub>N(ω

ij)∈

W</sub>Σ

<sub>(i,j)∈

N(i,j)</sub>A_ijB_ij(C_ij−

F_ij)+Σ

_C(W)Σ

_ibuff_i(b_i−

K_i)}.

23. A method as in claim 19, wherein said computer driving each objective function to a selected limit optimizes the objective function for utilization of most bottlenecked link and buffer according to

(Maximize)_N(ω

ij)∈

WY={Min<sub>(i,j)∈

N(ω

ij)</sub>A_ijB_ij(C_ij−

F_ij)+Min<sub>i∈

(W)</sub>buff_i(b_i−

K_i)}.

24. A method as in claim 19, wherein said computer driving each objective function to a selected limit optimizes the objective function for average residual link and buffer capacity according to

25. A method as in claim 17, wherein W is an initial contact window and the objective function variables further comprises:

a link capacity to neighboring nodes j (C_ij); and

a node buffer size (b_i).

26. A method as in claim 25, wherein driving each objective function to a selected limit comprises pre-selecting a network topology, said traffic demand matrix, potential links between node pairs and associated communications link costs.

27. A method as in claim 26, wherein driving each objective function provides an optimal flow assignment minimizing average path delay while meeting the traffic demands for the pre-selected said network topology, link capacity, and buffer capacity.

28. A method as in claim 27, wherein the optimal flow assignment is optimized according to:

Minimize{Σ

<sub>N(ω

ij)∈

W</sub>Σ

<sub>(i,j)∈

N(ω

ij)</sub>A_ijB_ijC_ij+Σ

_C(W)Σ

_ibuff_ib_i}.

29. A method as in claim 25, wherein driving each objective function to a selected limit comprises applying simulated annealing (SA).

30. A method as in claim 12, wherein adjusting said initial network configuration comprises:

determining a time dependent network traffic flow assignment;

adjusting node buffer and storage assignments; and

adjusting node link activation assignments.

31. A method as in claim 30, where adjusting said node buffer and storage assignments comprises changing storage capacity on at least one node.

32. A method as in claim 30, where adjusting said node link activation assignments comprises changing the number of antennas on at least one node.

33. A method of designing an optimized communications network, said method comprising the steps of:

providing an initial network topology for an interplanetary communications network;

defining network communications indicating time varying communications links between network nodes;

providing a traffic demand matrix indicating communications requirements between network nodes;

determining objective functions for said interplanetary communications network responsive to defined said network communications and said traffic demand matrix, wherein determining objective functions comprises the steps of;

determining objective function parameters,

determining objective function variables comprising;

a total link traffic load (F_ij);

a total stored node traffic (K_i);

a link activation (A_ij) function indicating active links;

a link capacity to neighboring nodes j (C_ij); and

a node buffer size (b_i), and

determining objective function constraints, wherein the objective function constraints comprise;

an average delay from link capacity having the form