Determining Placement of Nodes Within a Wireless Network

• US 20110007663A1
• Filed: 07/09/2009
• Published: 01/13/2011
• Est. Priority Date: 07/09/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rooney, John G., Scotton, Paolo
• Granted Patent: US 8,325,628 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/128 for finding disjoint paths
• CPC Class Codes: H04W 40/246 Connectivity information discovery

Abstract

A system of nodes including processors within a wireless sensor network includes an arrangement of the nodes with data connections therebetween within the wireless sensor network, wherein the data connections are limited to a set of distinct, non-intersecting paths, wherein each source node of the nodes is connected with a root nodes of the nodes by at least a predetermined number of the paths

Claims

1. A method for creating a wireless sensor network of nodes, comprising:

providing the wireless sensor network of the nodes, wherein each node includes a processor for communicating data across the wireless sensor network;

determining all non-looping paths between a plurality of source nodes to a root node of the nodes;

selecting a set of distinct, non-intersecting paths from the non-looping paths, wherein the set of distinct, non-intersecting paths includes a predetermined number of paths from each of the plurality of source nodes; and

annealing the set of distinct, non-intersecting paths by replacing at least one node of the set of distinct, non-intersecting paths with an unused node having a lower cost.

2. The method of claim 1, further comprising placing the nodes in a regular pattern.

3. The method of claim 2, wherein the regular pattern comprises one of a grid and a cube.

4. The method of claim 1, further comprising obtaining every non-looping path between each of the plurality of source nodes and the root node.

5. The method of claim 1, wherein a unique identifier is assigned to each node.

6. The method of claim 5, wherein determining all non-looping paths comprises:

a) adding a corresponding unique identifier to a message and broadcasting the message a unit distance from a given source node;

b) adding a corresponding unique identifier to the message at each of nodes within a unit distance of the given source node and rebroadcasting the message the unit distance, resulting in a plurality of messages, upon determining that the unique identifier of the respective node is not already in the message; and

c) repeating step b) until every one of the plurality of messages is received by the root node.

7. The method of claim 6, further comprising forwarding each message received by the root node to a fixed network for storage.

8. The method of claim 6, wherein steps a) through c) are repeated for each of the plurality of source nodes.

9. The method of claim 1, wherein selecting the set of distinct, non-intersecting paths comprises:

determining a node utilization number for each of a plurality of non-source nodes, wherein the node utilization number represents a number of times the corresponding non-source node appears in a plurality of feasible paths from the plurality of source nodes to the root node; and

adding the plurality of non-source nodes to a solution set in an order based on the node utilization number corresponding to each non-source node.

10. A computer readable medium embodying instructions executed by a processor to perform a method for determining a placement of nodes within a wireless sensor network, the method steps comprising:

providing an initial arrangement of the nodes within the wireless sensor network;

determining non-looping paths between each of a plurality of source nodes and a root node of the nodes; and

selecting a set of distinct paths to connect the nodes from the non-looping paths determining the placement, wherein the set of distinct paths includes every source node and the non-looping paths comprising the set of distinct paths do not intersect.

11. The computer readable medium of claim 10, further comprising placing the nodes in a regular pattern.

12. The computer readable medium of claim 11, wherein the regular pattern comprises one of a grid and a cube.

13. The computer readable medium of claim 10, further comprising obtaining every non-looping path between each of a plurality of source nodes and a root node.

14. The computer readable medium of claim 10, wherein a unique identifier is assigned to each node.

15. The computer readable medium of claim 14, wherein determining non-looping paths comprises:

a) adding a corresponding unique identifier to a message and broadcasting the message a unit distance from a given source node;

b) adding a corresponding unique identifier to the message at each of nodes within a unit distance of the given source node and rebroadcasting the message the unit distance, resulting in a plurality of messages, upon determining that the unique identifier of the respective node is not already in the message; and

c) repeating step b) until every one of the plurality of messages is received by the root node.

16. The computer readable medium of claim 15, further comprising forwarding each message received by the root node to a fixed network for storage.

17. The computer readable medium of claim 15, wherein steps a) through c) are repeated for each of the plurality of source nodes.

18. The computer readable medium of claim 10, wherein selecting a set of distinct paths comprises:

determining a node utilization number for each of a plurality of non-source nodes, wherein the node utilization number represents a number of times a node appears in a plurality of feasible paths from the plurality of source nodes to the root node; and

adding the plurality of non-source nodes to a solution set in an order based on the node utilization number corresponding to each non-source node.

19. The computer readable medium of claim 18, wherein selecting the set of distinct paths further comprises an annealing to replace at least one node of the set of distinct paths with an unused node having a lower cost.

20. A system of nodes comprising processors within a wireless sensor network, comprising an arrangement of the nodes with data connections therebetween within the wireless sensor network, wherein the data connections are limited to a set of distinct, non-intersecting paths, wherein each source node of the nodes is connected with a root nodes of the nodes by at least a predetermined number of the paths.