Distributed Graph Layout for Sensor Networks

Gotsman, Craig and Koren, Yehuda (2004) Distributed Graph Layout for Sensor Networks. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 273-284 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_28).

Full text not available from this repository.


Sensor network applications frequently require that the sensors know their physical locations in some global coordinate system. This is usually achieved by equipping each sensor with a location measurement device, such as GPS. However, low-end systems or indoor systems, which cannot use GPS, must locate themselves based only on crude information available locally, such as inter-sensor distances. We show how a collection of sensors, capable only of measuring distances to close neighbors, can compute their locations in a purely distributed manner, i.e. where each sensor communicates only with its neighbors. This can be viewed as a distributed graph drawing algorithm. We experimentally show that our algorithm consistently produces good results under a variety of simulated real-world conditions, and is relatively robust to the presence of noise in the distance measurements.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_28
Classifications:M Methods > M.100 Algebraic
ID Code:594

Repository Staff Only: item control page


I. Borg and P. Groenen, Modern Multidimensional Scaling: Theory and Applications, Springer-Verlag, 1997.

P. Eades, "A Heuristic for Graph Drawing", Congressus Numerantium 42 (1984), 149-160.

T.M.G. Fruchterman and E. Reingold, "Graph Drawing by Force-Directed Placement", Software-Practice and Experience 21 (1991), 1129-1164.

G.H. Golub and C.F. Van Loan, Matrix Computations, Johns Hopkins University Press, 1996.

C. Gotsman and Y. Koren, "Distributed Graph Layout for Sensor Networks", Harvard University Computer Science TR #20-04, 2004.

K.M. Hall, "An r-dimensional Quadratic Placement Algorithm", Management Science 17 (1970), 219-229.

B. Hendrickson, "Conditions for Unique Graph Realizations", SIAM J. Comput., 21 (1992), 6-84.

T. Kamada and S. Kawai, "Algorithm for Drawing General Undirected Graphs", Information Processing Letters 31 (1989), 7-15.

Y. Koren, "On Spectral Graph Drawing", Proc. 9th Inter. Computing and Combinatorics Conference (COCOON'03), LNCS 2697, Springer-Verlag, pp. 496-508, 2003.

M. Mauve, J. Widmer and H. Hartenstein. "A Survey on Position-Based Routing in Mobile Ad-Hoc Networks", IEEE Network, 15(2001), 30-39.

N.B. Priyantha, H. Balakrishnan, Proc. 1st Inter. Conf. on Embedded Networked Sensor Systems (SenSys 2003), 2003, pp. 340-341. Also TR#892, MIT LCS, 2003.

M. Tubaishat, S. Madria. "Sensor Networks : An Overview", IEEE Potentials, 22 (2003), 20-23.

L. Xiao, S. Boyd. "Fast Linear Interations for Distributed Averaging", Systems and Control Letters, 53 (2004), 65-78.

Y. Yemini, "Some Theoretical Aspects of Location-Location Problems", Proc. 20th Annu. IEEE Sympos. Found. Comput. Sci., 1979, pp. 1-8.