Systems and methods for automatically placing nodes in an ad hoc network
First Claim
1. A method for achieving biconnectivity in a network that includes a plurality of nodes, the method comprising:
- forming blocks from groups of one or more of the nodes in the network;
selecting one of the blocks as a root block;
identifying other ones of the blocks as leaf blocks; and
collectively moving the nodes in one or more of the leaf blocks to make the network biconnected.
6 Assignments
0 Petitions
Accused Products
Abstract
A system may place nodes (110) within a non-biconnected network (100) that includes multiple interconnected nodes (110) to achieve biconnectivity within the network (100) and transform the network (100) from a non-biconnected one to a biconnected one. A non-biconnected network is one that necessarily becomes partitioned into two or more disconnected networks if a node in a critical position (termed a “cutvertex” node) should fail or otherwise become unavailable. A biconnected network is one that includes at least one additional network link (sometimes termed an “edge”) between nodes belonging to each of the otherwise potentially disconnected networks for the purpose of maintaining network communication therebetween if and when the cutvertex node fails or otherwise becomes unavailable. To achieve biconnectivity, the system may identify one or more nodes (110) to move and determine the direction and distance to move the one or more nodes (110). The system may then move the one or more nodes (110) in the determined direction and distance to transform the non-biconnected network (100) to a biconnected one.
87 Citations
55 Claims
-
1. A method for achieving biconnectivity in a network that includes a plurality of nodes, the method comprising:
-
forming blocks from groups of one or more of the nodes in the network; selecting one of the blocks as a root block; identifying other ones of the blocks as leaf blocks; and collectively moving the nodes in one or more of the leaf blocks to make the network biconnected. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A system for achieving biconnectivity in a network that includes a plurality of nodes, comprising at least one processor configured to:
-
group subsets of the nodes into blocks; identify cutvertices in the network; and collectively move the subset of nodes in one or more of the blocks for a number of iterations to remove the cutvertices from the network. - View Dependent Claims (20)
-
-
21. In a network that includes a plurality of nodes, at least one of the nodes comprising:
-
a network device that is capable of moving within the network; and a movement controller configured to; generate a current view of the network, form blocks from groups of one or more of the nodes in the network based on the current view of the network, and identify one or more of the blocks, as one or more identified blocks, to move to make the network biconnected. - View Dependent Claims (22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37)
-
-
38. A method for achieving biconnectivity in a network that includes a plurality of nodes, the method comprising:
-
generating a graph of the network; identifying cutvertices in the network; and causing one or more of the nodes in the network to move to systematically remove the cutvertices from the network and form a biconnected network.
-
-
39. A method for achieving biconnectivity in a non-biconnected network that includes a plurality of nodes, the method comprising:
-
identifying one or more of the nodes to move; determining direction and distance to move the one or more nodes; and moving the one or more nodes in the determined direction and distance to transform the non-biconnected network to a biconnected network. - View Dependent Claims (40, 41, 42, 43, 44, 45)
-
-
46. A method for achieving biconnectivity in a non-biconnected network that includes a plurality of nodes, the method comprising:
-
determining a geographic center of the non-biconnected network; and moving each of one or more of the nodes a weighted distance towards the geographic center to transform the non-biconnected network to a biconnected network.
-
-
47. In a network that includes a plurality of nodes, at least one of the nodes comprising:
-
a network device that is capable of moving within the network; and a movement controller configured to; determine locations of the nodes, identify a geographic center of the network based on the locations of the nodes, and determine a weighted distance that each of the nodes should move toward the geographic center to achieve biconnectivity in the network.
-
-
48. A system for achieving biconnectivity in a non-biconnected network that includes a plurality of nodes, the system comprising at least one processor configured to:
-
identify a geographic center of the non-biconnected network based on current locations of the nodes; and cause each of one or more of the nodes to move towards the geographic center to transform the non-biconnected network to a biconnected network.
-
-
49. A non-transitory computer-readable medium that includes instructions that when executed by at least one processor causes the processor to perform a method for achieving biconnectivity in a network that includes a plurality of nodes, the computer-readable medium comprising:
-
instructions for determining a current topology of the network; instructions for identifying cutvertices in the network based on the current topology of the network; instructions for identifying one or more of the nodes in the network to move, and instructions for causing each of the indentified one or more nodes to move in a particular direction to systematically remove the cutvertices from the network and form a biconnected network.
-
-
50. A method for achieving biconnectivity in a one-dimensional non-biconnected network that includes a plurality of nodes, comprising:
-
determining initial positions of the nodes in the one-dimensional non-biconnected network; determining a movement schedule for the nodes using one or more linear programming techniques; and causing one or more of the nodes to move based on the determined movement schedule to form a biconnected network from the one-dimensional non-biconnected network. - View Dependent Claims (51, 52, 53)
-
-
54. A system for achieving biconnectivity in a one-dimensional non-biconnected network that includes a plurality of nodes, comprising at least one processor configured to:
-
determine initial positions of the nodes in the one-dimensional non-biconnected network; determine a movement schedule optimally in polynomial time based at least in part on the initial positions of the nodes and a number of the nodes in the one-dimensional non-biconnected network; and cause one or more of the nodes to move based on the determined movement schedule to achieve biconnectivity in the one-dimensional non-biconnected network. - View Dependent Claims (55)
-
Specification