Distributed graph layout for sensor node networks

• US 7,490,014 B1
• Filed: 08/14/2007
• Issued: 02/10/2009
• Est. Priority Date: 02/10/2005
• Status: Expired due to Fees

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Koren, Yehuda, Gotsman, Craig
• Primary Examiner(s): Feliciano; Eliseo Ramos
• Assistant Examiner(s): O MALLEY, MARY CATHERINE
• Application Number:
  US11/893,062
• Time in Patent Office: 546 Days
• Field of Search: 702/150, 702/155, 702/158, 702188-190, 702/33, 702 41- 43, 702/57, 702 94- 95, 702/152, 709223-225, 701213-216, 701/300, 340665-666, 340/668, 340/686.1
• US Class Current: 702/94
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks

Abstract

Certain exemplary embodiments comprise a method, comprising: in a sensor node network comprising a plurality of sensor nodes, each sensor node from the plurality of sensor nodes having location coordinates that are initially unknown, each sensor node from the plurality of sensor nodes having neighbors, each sensor node from the plurality of sensor nodes capable of determining distances only to that sensor node'"'"'s neighbors: for each sensor node from the plurality of sensor nodes, communicating with that sensor node'"'"'s neighbors; and based only on communications between neighbors, in a fully distributed manner, generating a sensor node network layout that indicates the location coordinates of each sensor node.

Claims

1. A method, comprising:

rendering a sensor node network layout of a sensor node network, said sensor node network comprising a plurality of sensor nodes, each sensor node from said plurality of sensor nodes having location coordinates that are initially unknown, each sensor node from said plurality of sensor nodes having neighbors, each sensor node from said plurality of sensor nodes capable of determining distances only to that sensor node'"'"'s neighbors, said network node layout determined via an iterative technique and based upon a generated initial layout of said sensor node network, said sensor node network layout indicative of location coordinates of each sensor node, said generated initial layout determined based only on communications between neighbors, said generated initial layout determined via iteratively averaging eigenvector values for each predetermined sensor node with eigenvector values for each neighbor of each predetermined sensor node, said eigenvector values determined based upon;

$x_i\leftarrow <br><br>a<br><br>\left(x_i+\frac{\underset{\left(i,j\right)\in <br><br>E}{\sum <br><br>}<br><br><br><br>w_{i,j}<br><br>x_j}{\underset{\left(i,j\right)\in <br><br>E}{\sum <br><br>}<br><br>w_{i,j}}\right)$

where;

i and j are adjacent sensor nodes;

E is a set of edges of said plurality of sensor nodes;

w_i,j is a measure of a similarity of similarity of adjacent sensor nodes;

x_j is a location coordinate indicative of a relative position of node j; and

a is a predetermined constant.

2. The method of claim 1, further comprising:

automatically generating said sensor node network layout.

3. The method of claim 1, further comprising:

measuring distances to neighbors via a Received Signal Strength Indicator, said sensor node network layout based upon said distances.

4. The method of claim 1, further comprising:

measuring distances to neighbors via a Time of Arrival technique, said sensor node network layout based upon said distances.

5. The method of claim 1, further comprising:

via an applied heuristic, generating a well-spread fold-free graph layout, said sensor node network layout based upon said well-spread fold-free graph layout.

6. The method of claim 1, further comprising:

via an applied heuristic, generating a well-spread fold-free graph layout, said sensor node network layout based upon said well-spread fold-free graph layout; and

correcting local errors in said well-spread fold-free graph layout.

7. The method of claim 1, further comprising:

via an applied heuristic, generating a well-spread fold-free graph layout, said sensor node network layout based upon said well-spread fold-free graph layout;

balancing local errors in said well-spread fold-free graph layout.

8. The method of claim 1, further comprising:

via an applied heuristic, generating a well-spread fold-free graph layout; and

converging on said sensor node network layout based upon said well-spread fold-free graph layout.

9. The method of claim 1, further comprising:

electing five reference sensor nodes, four of said reference sensor nodes distributed on a periphery of said sensor node network, a fifth reference sensor node chosen in a central portion of said sensor node network; and

determining said sensor node network layout based upon said five reference sensor nodes.

10. The method of claim 1, further comprising:

via said iterative technique, generating said sensor node network layout via a minimization a localized stress energy function.

11. The method of claim 1, further comprising:

via a gradient descent technique, generating said sensor node network layout via motion of an infinitesimal distance in a direction of a spring force operating on a sensor node.

12. The method of claim 1, wherein:

said iterative technique does not involve gradient descent.

13. The method of claim 1, wherein:

said iterative technique comprises majorization.

14. The method of claim 1, further comprising:

placing each sensor node from said plurality of sensor nodes at a two-dimensional barycenter of that sensor node'"'"'s neighbors.

15. The method of claim 1, wherein:

said sensor node network layout is generated based upon a Jacobi iteration.

16. The method of claim 1, wherein:

said iterative technique comprises performing an eternal process of stress minimization.

17. The method of claim 1, further comprising:

providing said location coordinates of at least one sensor node.

18. The method of claim 1, wherein:

said location coordinates change dynamically for each of said plurality of sensor nodes.

19. A system, comprising:

a plurality of sensor nodes of a sensor node network, each sensor node from said plurality of sensor nodes having location coordinates that are initially unknown, each sensor node from said plurality of sensor nodes having neighbors, each sensor node from said plurality of sensor nodes capable of determining distances only to that sensor node'"'"'s neighbors, each sensor node comprising a transceiver adapted to communicate with that sensor node'"'"'s neighbors; and

a sensor node network layout generator adapted to, based on only communications between neighbors, via an iterative technique determine a network node layout based upon a generated initial layout of said sensor node network, said sensor node network layout indicative of location coordinates of each sensor node, said generated initial layout determined based only on communications between neighbors, said generated initial layout determined via iteratively averaging eigenvector values for each predetermined sensor node with eigenvector values for each neighbor of each predetermined sensor node, said eigenvector values determined based upon;

$x_i\leftarrow <br><br>a<br><br>\left(x_i+\frac{\underset{\left(i,j\right)\in <br><br>E}{\sum <br><br>}<br><br><br><br>w_{i,j}<br><br>x_j}{\underset{\left(i,j\right)\in <br><br>E}{\sum <br><br>}<br><br>w_{i,j}}\right)$

where;

i and j are adjacent sensor nodes;

E is a set of edges of said plurality of sensor nodes;

w_i,j is a measure of a similarity of similarity of adjacent sensor nodes;

x_j is a location coordinate indicative of a relative position of node j; and

a is a predetermined constant.