Distributed graph layout for sensor node networks

• US 7,275,014 B1
• Filed: 02/10/2005
• Issued: 09/25/2007
• Est. Priority Date: 02/10/2005
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Koren, Yehuda, Gotsman, Craig
• Primary Examiner(s): Ramos-Feliciano; Eliseo
• Assistant Examiner(s): O MALLEY, MARY CATHERINE
• Application Number:
  US11/055,261
• Time in Patent Office: 957 Days
• Field of Search: 702/155, 702/158, 702188-190, 702/150, 709223-225, 701213-216, 701/300
• US Class Current: 702/150
• 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:

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;

based only on communications between neighbors, in a fully distributed manner, generating an initial layout, the initial layout determined via iteratively averaging eigenvector values for each predetermined sensor node with eigenvector values for each neighbor of each predetermined sensor node, the eigenvector values determined based upon;

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

where;

i and j are adjacent sensor nodes;

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

w_i,j is a measure of a 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;

utilizing the initial layout, via an iterative technique not involving gradient descent, generating a sensor node network layout that indicates the location coordinates of each sensor node; and

rendering the sensor node network layout.

2. The method of claim 1, further comprising:

avoiding communications between non-neighboring sensor nodes.

3. The method of claim 1, further comprising:

minimizing communications between each sensor node and its neighbors.

4. The method of claim 1, further comprising:

avoiding any centralized control of said method.

5. The method of claim 1, wherein:

the generated sensor node network layout is optimal.

6. The method of claim 1, wherein:

the initial layout is fold-free.

7. The method of claim 1, further comprising:

providing the generated sensor node network layout.

8. The method of claim 1, further comprising:

via the iterative technique, minimizing a localized stress energy function.

9. The method of claim 1, wherein:

the iterative technique is fully distributed.

10. The method of claim 1, wherein:

the iterative technique comprises majorization.

11. The method of claim 1, further comprising:

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

12. The method of claim 1, wherein:

the initial layout is based on a distributed eigenvector computation.

13. The method of claim 1, wherein:

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

14. The method of claim 1, further comprising:

providing the location coordinates of at least one sensor node.

15. The method of claim 1, wherein:

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

16. The method of claim 1, wherein:

the sensor node network layout is two-dimensional.

17. The method of claim 1, wherein:

the sensor node network layout is three-dimensional.

18. The method of claim 1, wherein:

at least a portion of the sensor node network layout is located indoors.

19. A system, 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, 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;

in a fully distributed manner and not based on gradient descent, generate an initial layout, the initial layout determined via iteratively averaging eigenvector values for each predetermined sensor node with eigenvector values for each neighbor of each predetermined sensor node, the eigenvector values determined based upon;

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

where;

i and j are adjacent sensor nodes;

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

w_i,j is a measure of a 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; and

utilizing the initial layout, via an iterative technique not involving gradient descent, generate a sensor node network layout that indicates the location coordinates of each sensor node.

20. A machine readable medium storing instructions for activities

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 on only communications between neighbors, in a fully distributed manner and not based on gradient descent, generating an initial layout, the initial layout determined via iteratively averaging eigenvector values for each predetermined sensor node with eigenvector values for each neighbor of each predetermined sensor node, the eigenvector values determined based upon;

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

where;

i and j are adjacent sensor nodes;

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

w_j,i is a measure of a 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;

utilizing the initial layout, via an iterative technique not involving gradient descent, generating a sensor node network layout that indicates the location coordinates of each sensor node; and

rendering the sensor node network layout.