System and method for demand driven network topology management

• US 9,131,529 B1
• Filed: 08/31/2010
• Issued: 09/08/2015
• Est. Priority Date: 06/29/2009
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Ayyagari, Arun, Li, Winfeng, Battles, Craig F., Dorsett, Michael A.
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): MOYER, DALE S
• Application Number:
  US12/873,182
• Time in Patent Office: 1,834 Days
• Field of Search: 340/539.22, 370/338, 370/252, 370254-255, 701/21
• US Class Current: 1/1
• CPC Class Codes: G05D 1/104 involving a plurality of aircrafts, e.g. formation flying traffic control systems for aircraft G08G5/00
• CPC Class Codes: H04W 16/00 Network planning, e.g. coverage or traffic planning tools; Network deployment, e.g. resource partitioning or cells structures
• CPC Class Codes: H04W 24/02 Arrangements for optimising operational condition
• CPC Class Codes: H04W 84/06 Airborne or Satellite Networks space-based or airborne stations H04B7/185
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements

Abstract

Methods, systems, and devices are disclosed to facilitate operation of a network. First network state data descriptive of a first network state is received. The first network data includes network demand associated with nodes of a dynamic network, where the nodes of the dynamic network include at least one movable node. The first network data also includes a node state of each node of the dynamic network. At least one first link is automatically established between two or more nodes of the dynamic network to satisfy at least a portion of the network demand. Link data is generated where the link data is descriptive of node utilization, the at least one first link, and assignment of the portion of the network demand to the at least one first link. One or more changes to the dynamic network are modeled based on the link data to identify a second network state, wherein the second network state satisfies a greater quantity of the network demand than the first network state.

Claims

1. A method comprising:

receiving, at a processor, first network state data descriptive of a first network state, the first network state data comprising;

network demand associated with nodes of a dynamic network, wherein the nodes of the dynamic network include a movable node; and

node state of each node of the dynamic network;

automatically establishing a first link between two nodes of the dynamic network to satisfy a portion of the network demand;

generating link data, wherein the link data is descriptive of node utilization, the first link, and assignment of the portion of the network demand to the first link; and

modeling one or more changes to the dynamic network based on the link data to identify a second network state, wherein the dynamic network in the second network state satisfies a greater quantity of the network demand than the dynamic network in the first network state,

wherein modeling the one or more changes to the dynamic network includes;

determining a first destination position based on modeling a first movement of the movable node in a first direction, wherein a further movement of the movable node in the first direction beyond the first destination position results in a same or lower quantity of network demand satisfied than in the first destination position,

determining a second destination position based on modeling a second movement of the movable node in a second direction, and

determining a velocity vector of the movable node based on the first destination position and the second destination position.

2. The method of claim 1, wherein the second network state is identified periodically.

3. The method of claim 1, wherein the second network state is identified in response to occurrence of an event.

4. The method of claim 1, further comprising causing the movable node to be repositioned to a new location based on the velocity vector.

5. The method of claim 4, further comprising determining the new location of the movable node based on modified potential fields applied to the nodes of the dynamic network.

6. The method of claim 5, further comprising automatically causing a second link to be established between a pair of the nodes of the dynamic network after the movable node is repositioned, wherein the second link satisfies at least a portion of network demand not satisfied by the first link.

7. The method of claim 4, wherein the new location of the movable node is determined by modeling one or more changes to a connection demand matrix that results from positioning the movable node at each of a plurality of available locations.

8. The method of claim 1, further comprising:

determining that the nodes of the dynamic network are insufficient to satisfy all of the network demand; and

automatically sending a request for an additional node.

9. The method of claim 1, further comprising implementing the second network state by automatically causing one or more links between the nodes of the dynamic network to be changed.

10. A system comprising:

a link management system configured to dynamically establish one or more communication links between a portion of a plurality of nodes of a communication network to accommodate a first network demand, wherein each of the nodes is configured to receive and transmit signals and wherein the plurality of nodes includes a movable node;

a network topology modeling system configured to determine a position of the movable node that supports establishing one or more second communication links to accommodate a second network demand, wherein the second network demand is different than the first network demand, wherein the network topology modeling system is further configured to determine a first destination position based on modeling a first movement of the movable node in a first direction, wherein a further movement of the movable node in the first direction beyond the first destination position results in a same or lower quantity of network demand satisfied than the first destination position, wherein the network topology modeling system is further configured to determine a second destination position based on modeling a second movement of the movable node in a second direction, and wherein the network topology modeling system is further configured to determine a velocity vector of the movable node based on the first destination position and the second destination position; and

a mission control system configured to control movement of the movable node based on a mission objective that is independent of communications of the communication network.

11. The system of claim 10, wherein the mission control system is further configured to send movement information related to the movable node to the network topology modeling system, and wherein the network topology modeling system is configured to determine the position of the movable node based at least in part on the movement information.

12. The system of claim 10, wherein the network topology modeling system and the link management system are distributed among two or more of the plurality of nodes.

13. The system of claim 10, wherein the mission objective includes a distance from a goal location, a formation, or a combination thereof.

14. The system of claim 10, wherein dynamically establishing the one or more communication links includes prioritizing a first route from a sending node to a receiving node over a second route from the sending node to the receiving node when the first route includes fewer intermediate nodes than the second route.

15. The system of claim 10, wherein the link management system uses a greedy allocation method to dynamically establish the one or more communication links.

16. The system of claim 15, wherein existing communication links are given priority by the greedy allocation method.

17. A device comprising:

a processor;

a network interface coupled to the processor; and

a memory accessible to the processer, the memory storing instructions that are executable by the processor to cause the processor to perform operations including;

receiving, at a first node of a dynamic network, first network state data descriptive of a first network state of the dynamic network, the first network state data comprising;

network demand associated with nodes of the dynamic network, wherein the nodes of the dynamic network include the first node; and

node state of each node of the dynamic network;

interacting with a second node of the dynamic network, via the network interface, to establish a first link between a pair of nodes of the dynamic network to satisfy at least a portion of network demand of the dynamic network;

generating link data, wherein the link data is descriptive of node utilization, the first link, and assignment of the portion of the network demand to the first link; and

executing, at the first node, a portion of a model of the dynamic network based on the link data, wherein the model of the dynamic network models one or more changes to the dynamic network to identify a second network state, wherein the dynamic network in the second network state satisfies more of the network demand than the dynamic network in the first network state, wherein the model of the dynamic network models a topological configuration of the nodes of the dynamic network to determine whether repositioning one or more nodes of the dynamic network would enable an additional portion of the network demand to be supported, wherein the model of the dynamic network is generated by determining a first destination position based on modeling a first movement of the first node in a first direction, wherein a further movement of the first node in the first direction beyond the first destination position results in a same or lower quantity of network demand satisfied than in the first destination position, wherein the model of the dynamic network is generated by determining a second destination position based on modeling a second movement of the first node in a second direction, and wherein the model of the dynamic network is generated by determining a velocity vector of the second node based on the first destination position and the second destination position.

18. The device of claim 17, wherein the model of the dynamic network further models links between the nodes of the dynamic network by:

evaluating a first configuration of the links subject to a link cost associated with each link to determine the portion of the network demand that is satisfied by the first configuration; and

in response to the first configuration not being able to satisfy all of the network demand, evaluating a second configuration of the links to determine the portion of the network demand that is satisfied by the second configuration.

19. The device of claim 17, further comprising a motivating system to move the first node from a first position to a second position based on the model, wherein at the second position, the first node supports a third network state of the dynamic network, and wherein the dynamic network in the third network state supports the additional portion of the network demand.

20. The device of claim 17, wherein the second network state is identified periodically.