METHOD OF OPTIMIZING AN INTERPLANETARY COMMUNICATIONS NETWORK

• US 20080155070A1
• Filed: 05/16/2007
• Published: 06/26/2008
• 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
• Granted Patent: US 10,142,013 B2
• Time in Patent Office: Days
• US Class Current: 709/220
• 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 an interplanetary communications network, said method comprising the steps of:

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

b) providing forecasts of traffic demand in said interplanetary communications network;

c) determining objective functions responsive to said demands and characterizing communications over said network;

d) determining at least one limit for each said objective function; and

e) adjusting said initial network configuration responsive to determined object function limits.

2. A method as in claim 1, wherein the initial network configuration provided in step (a) 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 the step (c) of determining objective functions generates a routing model defining communications routes between nodes and end to end in said network.

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

7. A method as in claim 6, wherein after the step (d) of determining objective function limits, the method further comprises the step (d1) of returning to step (c), traffic demands results from said routing model are returned, and said objective functions are further provided responsive to said traffic demands results.

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

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

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

a) providing an initial network topology for an interplanetary communications network;

b) defining network communications indicating between communications between network nodes;

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

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

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

f) adjusting said initial network configuration responsive to said object function at said selected limit.

11. A method as in claim 10, wherein the initial network topology provided in step (a) includes node orbital parameters and a description of node motion.

12. A method as in claim 10, wherein the step (b) of defining network communications comprises the steps of:

i) determining contact windows between said nodes, contact windows being described in a window matrix (W); and

ii) determining sub-windows in ones of said contact windows.

13. A method as in claim 10, wherein the step (d) of determining objective functions comprises the steps of:

i) determining objective function parameters;

ii) determining objective function variables; and

iii) determining objective function constraints.

14. A method as in claim 13, 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.

15. A method as in claim 14, 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 (K^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.

16. A method as in claim 15, 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).

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

a total link load (g_i), where for link load a_ij, g_i≦

a_ij;

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

a set of feasible solutions (x ε

X) to the objective function (ƒ

(x)).

18. A method as in claim 17, wherein the objective function constraints are linear and the step (e) of driving each objective function to a selected limit comprises applying linear programming.

19. A method as in claim 18, wherein said linear programming is mixed integer linear programming.

20. A method as in claim 17, wherein the step (e) 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)}.

21. A method as in claim 17, wherein the step (e) 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)}.

22. A method as in claim 17, wherein the step (e) optimizes the objective function for average residual link and buffer capacity according to

23. A method as in claim 15, 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).

24. A method as in claim 23, wherein the step (e) of 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.

25. A method as in claim 24, wherein the step (e) of 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.

26. A method as in claim 25, 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}.

27. A method as in claim 23, wherein the objective function constraints comprise:

an average delay from link capacity having the form

28. A method as in claim 23, wherein the step (e) of driving each objective function to a selected limit comprises applying simulated annealing (SA).

29. A method as in claim 10, wherein the step (f) of adjusting said initial network configuration comprises:

i) determining a time dependent network traffic flow assignment;

ii) adjusting node buffer and storage assignments; and

iii) adjusting node link activation assignments.

30. A method as in claim 29, where the step (ii) of adjusting said node buffer and storage assignments comprises changing storage capacity on at least one node.

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