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
moving 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.
-
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
moving 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:
-
means for grouping subsets of the nodes into blocks;
means for identifying cutvertices in the network; and
means for iteratively moving one or more of the blocks 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
moving one or more of the nodes in the network 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:
-
means for identifying a geographic center of the non-biconnected network based on current locations of the nodes; and
means for causing 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 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; and
instructions for identifying one or more of the nodes in the network to move 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:
-
means for determining initial positions of the nodes in the one-dimensional non-biconnected network;
means for determining 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
means for causing 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