Determining placement of nodes within a wireless network

• US 8,325,628 B2
• Filed: 07/09/2009
• Issued: 12/04/2012
• Est. Priority Date: 07/09/2009
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Scotton, Paolo, Rooney, John N.
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): Moutaouakil, Mounir
• Application Number:
  US12/500,397
• Publication Number:
  US 20110007663A1
• Time in Patent Office: 1,244 Days
• Field of Search: 370254-258, 709220-222, 702/104
• US Class Current: 370/255
• 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 each of a plurality of source nodes and 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 includes every source node; 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,

wherein a unique identifier is assigned to each node, and 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.

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 forwarding each message received by the root node to a fixed network for storage.

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

6. 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.

7. A computer readable storage 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 all 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 from the non-looping paths to utilize for communication between the source nodes and the root node, wherein the set of distinct paths includes every source node, and the non-looping paths comprising the set of distinct paths do not intersect,

wherein a unique identifier is assigned to each node, and 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.

8. The computer storage readable medium of claim 7, further comprising placing the nodes in a regular pattern.

9. The computer readable storage medium of claim 8, wherein the regular pattern comprises one of a grid and a cube.

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

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

12. The computer readable storage medium of claim 7, 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.

13. The computer readable storage medium of claim 12, 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.