Systems and methods for automatically placing nodes in an ad hoc network

• US 20050114551A1
• Filed: 08/29/2003
• Published: 05/26/2005
• Est. Priority Date: 08/29/2003
• Status: Active Grant

• Current Assignee: Raytheon BBN Technlogies Corp. (Rtx Corporation)
• Original Assignee: Raytheon BBN Technlogies Corp. (Rtx Corporation)
• Inventors: Basu, Prithwish, Redi, Jason Keith
• Granted Patent: US 8,166,204 B2
• Time in Patent Office: Days
• US Class Current: 709/249
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks
• CPC Class Codes: H04W 4/08 User group management
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

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.

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.

2. The method of claim 1, wherein the forming blocks includes:

generating a graph of a current view of a topology of the network, and

generating a block tree based on the current view of the topology of the network, the block tree organizing the nodes into one or more blocks.

3. The method of claim 2, wherein the generating a graph includes:

determining locations of the nodes in the network, and

determining the current view of the topology of the network based on the locations of the nodes in the network.

4. The method of claim 3, wherein the determining locations of the nodes includes:

periodically receiving updates from the nodes, each of the updates includes a location of a corresponding one of the nodes.

5. The method of claim 4, wherein the determining locations of the nodes further includes:

extracting neighbor information from the updates.

6. The method of claim 1, further comprising:

identifying cutvertices in the network.

7. The method of claim 6, wherein the moving one or more of the leaf blocks includes:

moving one or more of the leaf blocks to remove one or more of the cutvertices from the network.

8. The method of claim 1, wherein the selecting one of the blocks includes:

identifying one of the blocks that includes a maximum number of nodes as the root block.

9. The method of claim 1, wherein the moving one or more of the leaf blocks includes:

moving all of the nodes within one of the leaf blocks collectively when the leaf block is moved.

10. The method of claim 1, wherein the one or more of the leaf blocks are moved while minimizing a total distance moved by all of the nodes in the network.

11. The method of claim 1, wherein the moving one or more of the leaf blocks includes:

moving each of the one or more of the leaf blocks, as a particular leaf block, towards a nearest node in a parent block.

12. The method of claim 11, wherein the particular leaf block is moved towards the nearest node until at least one new edge appears between the particular leaf block and the parent block.

13. The method of claim 1, wherein the moving of one or more of the leaf blocks is performed iteratively until the network is biconnected.

14. The method of claim 1, wherein the moving of one or more of the leaf blocks is performed after final positions for the one or more of the leaf blocks is determined.

15. The method of claim 1, wherein the method is performed by one or more of the nodes in the network.

16. The method of claim 1, wherein the method is performed by each of the nodes in the network.

17. The method of claim 1, wherein the nodes are capable of moving on their own.

18. The method of claim 1, wherein the nodes include robotic nodes.

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.

20. The system of claim 19, wherein the network becomes biconnected when all of the cutvertices have been removed from the network.

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.

22. The at least one node of claim 21, wherein the movement controller is further configured to instruct the network device to move to a particular location when the at least one node is one of the nodes in one of the one or more identified blocks.

23. The at least one node of claim 22, wherein all of the nodes within the one of the one or more identified blocks move collectively.

24. The at least one node of claim 21, wherein when generating a current view of the network, the movement controller is configured to:

determine locations of the nodes in the network, and

determine a current topology of the network based on the locations of the nodes in the network.

25. The at least one node of claim 24, wherein when determining locations of the nodes, the movement controller is configured to periodically receive updates from the nodes, each of the updates including a location of the corresponding node.

26. The at least one node of claim 25, wherein when determining locations of the nodes, the movement controller is further configured to extract neighbor information from the updates.

27. The at least one node of claim 21, wherein the movement controller is further configured to identify cutvertices in the network.

28. The at least one node of claim 27, wherein when identifying one or more of the blocks to move, the movement controller is configured to identify a distance and direction to move the one or more identified blocks so as to remove one or more of the cutvertices from the network.

29. The at least one node of claim 21, wherein the movement controller is further configured to:

identify one of the blocks that includes a maximum number of nodes as a root block, and

identify other ones of the blocks as leaf blocks, the one or more identified blocks being ones of the leaf blocks.

30. The at least one node of claim 21, wherein the movement controller is further configured to determine a distance and direction that the one or more identified blocks should move.

31. The at least one node of claim 30, wherein the one or more identified blocks are moved so as to minimize a total distance moved by all of the nodes in the network.

32. The at least one node of claim 30, wherein each of the one or more identified blocks, as a particular block, is to move towards a nearest node in a parent block.

33. The at least one node of claim 32, wherein the particular block is to move towards the nearest node until at least one new edge appears between the particular block and the parent block.

34. The at least one node of claim 21, wherein moving of the one or more identified blocks is performed iteratively until the network is biconnected.

35. The at least one node of claim 21, wherein moving of the one or more identified blocks is performed after final positions for the one or more identified blocks is determined.

36. The at least one node of claim 21, wherein the at least one node includes all of the nodes in the network.

37. The at least one node of claim 21, wherein the nodes include robotic nodes.

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.

40. The method of claim 39, wherein the identifying one or more of the nodes to move includes:

forming blocks from groups of at least one of the nodes in the non-biconnected network,

selecting one of the blocks as a root block, and

identifying other ones of the blocks as leaf blocks.

41. The method of claim 40, wherein the one or more nodes are included in one or more of the leaf blocks.

42. The method of claim 41, wherein the moving the one or more nodes includes:

moving the one or more nodes collectively with other ones of the one or more nodes within a same one of the leaf blocks.

43. The method of claim 39, wherein the determining direction and distance to move includes:

determining a geographic center of the non-biconnected network, and

determining weighted distances for moving the one or more nodes toward the geographic center.

44. The method of claim 43, wherein the weighted distances are related to distances that the nodes are from the geographic center.

45. The method of claim 43, wherein the direction for a particular node of the one or more nodes includes a straight line joining a starting position of the particular node and the geographic center.

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.

51. The method of claim 50, wherein the determining a movement schedule includes:

determining the movement schedule as an objective function,

converting the objective function into a linear programming representation, and

solving the linear programming representation optimally in polynomial time.

52. The method of claim 51, wherein the linear programming representation is solved as a function of a number of nodes in the one-dimensional non-biconnected network.

53. The method of claim 50, wherein each of the nodes in the biconnected network is capable of communicating with other ones of the nodes in the biconnected network one and two hops away.

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.

55. The system of claim 54, wherein each of the nodes is capable of communicating with other ones of the nodes one and two hops away after biconnectivity is achieved in the one-dimensional non-biconnected network.