Rigidity, computation, and randomization in network localization

T. Eren; D. K. Goldenberg; W. Whiteley; Y. R. Yang; A. S. Morse; B. D.O. Anderson; P. N. Belhumeur

doi:10.1109/INFCOM.2004.1354686

Rigidity, computation, and randomization in network localization

T. Eren^*, D. K. Goldenberg, W. Whiteley, Y. R. Yang, A. S. Morse, B. D.O. Anderson, P. N. Belhumeur

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

425 Citations (Scopus)

Abstract

In this paper we provide a theoretical foundation for the problem of network localization in which some nodes know their locations and other nodes determine their locations by measuring the distances to their neighbors. We construct grounded graphs to model network localization and apply graph rigidity theory to test the conditions for unique localizability and to construct uniquely localizable networks. We further study the computational complexity of network localization and investigate a subclass of grounded graphs where localization can be computed efficiently. We conclude with a discussion of localization in sensor networks where the sensors are placed randomly.

Original language	English
Title of host publication	IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies
Pages	2673-2684
Number of pages	12
DOIs	https://doi.org/10.1109/INFCOM.2004.1354686
Publication status	Published - 2004
Event	IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies - Hongkong, China Duration: 7 Mar 2004 → 11 Mar 2004

Publication series

Name	Proceedings - IEEE INFOCOM
Volume	4
ISSN (Print)	0743-166X

Conference

Conference	IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies
Country/Territory	China
City	Hongkong
Period	7/03/04 → 11/03/04

Access to Document

10.1109/INFCOM.2004.1354686

Cite this

Eren, T., Goldenberg, D. K., Whiteley, W., Yang, Y. R., Morse, A. S., Anderson, B. D. O., & Belhumeur, P. N. (2004). Rigidity, computation, and randomization in network localization. In IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies (pp. 2673-2684). (Proceedings - IEEE INFOCOM; Vol. 4). https://doi.org/10.1109/INFCOM.2004.1354686

@inproceedings{4678589b76164951b365fcb61a98f36c,

title = "Rigidity, computation, and randomization in network localization",

abstract = "In this paper we provide a theoretical foundation for the problem of network localization in which some nodes know their locations and other nodes determine their locations by measuring the distances to their neighbors. We construct grounded graphs to model network localization and apply graph rigidity theory to test the conditions for unique localizability and to construct uniquely localizable networks. We further study the computational complexity of network localization and investigate a subclass of grounded graphs where localization can be computed efficiently. We conclude with a discussion of localization in sensor networks where the sensors are placed randomly.",

author = "T. Eren and Goldenberg, {D. K.} and W. Whiteley and Yang, {Y. R.} and Morse, {A. S.} and Anderson, {B. D.O.} and Belhumeur, {P. N.}",

year = "2004",

doi = "10.1109/INFCOM.2004.1354686",

language = "English",

isbn = "0780383559",

series = "Proceedings - IEEE INFOCOM",

pages = "2673--2684",

booktitle = "IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies",

note = "IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies ; Conference date: 07-03-2004 Through 11-03-2004",

}

Eren, T, Goldenberg, DK, Whiteley, W, Yang, YR, Morse, AS, Anderson, BDO & Belhumeur, PN 2004, Rigidity, computation, and randomization in network localization. in IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings - IEEE INFOCOM, vol. 4, pp. 2673-2684, IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies, Hongkong, China, 7/03/04. https://doi.org/10.1109/INFCOM.2004.1354686

Rigidity, computation, and randomization in network localization. / Eren, T.; Goldenberg, D. K.; Whiteley, W. et al.
IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies. 2004. p. 2673-2684 (Proceedings - IEEE INFOCOM; Vol. 4).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Rigidity, computation, and randomization in network localization

AU - Eren, T.

AU - Goldenberg, D. K.

AU - Whiteley, W.

AU - Yang, Y. R.

AU - Morse, A. S.

AU - Anderson, B. D.O.

AU - Belhumeur, P. N.

PY - 2004

Y1 - 2004

N2 - In this paper we provide a theoretical foundation for the problem of network localization in which some nodes know their locations and other nodes determine their locations by measuring the distances to their neighbors. We construct grounded graphs to model network localization and apply graph rigidity theory to test the conditions for unique localizability and to construct uniquely localizable networks. We further study the computational complexity of network localization and investigate a subclass of grounded graphs where localization can be computed efficiently. We conclude with a discussion of localization in sensor networks where the sensors are placed randomly.

AB - In this paper we provide a theoretical foundation for the problem of network localization in which some nodes know their locations and other nodes determine their locations by measuring the distances to their neighbors. We construct grounded graphs to model network localization and apply graph rigidity theory to test the conditions for unique localizability and to construct uniquely localizable networks. We further study the computational complexity of network localization and investigate a subclass of grounded graphs where localization can be computed efficiently. We conclude with a discussion of localization in sensor networks where the sensors are placed randomly.

UR - http://www.scopus.com/inward/record.url?scp=8344261381&partnerID=8YFLogxK

U2 - 10.1109/INFCOM.2004.1354686

DO - 10.1109/INFCOM.2004.1354686

M3 - Conference contribution

SN - 0780383559

T3 - Proceedings - IEEE INFOCOM

SP - 2673

EP - 2684

BT - IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies

T2 - IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies

Y2 - 7 March 2004 through 11 March 2004

ER -

Eren T, Goldenberg DK, Whiteley W, Yang YR, Morse AS, Anderson BDO et al. Rigidity, computation, and randomization in network localization. In IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies. 2004. p. 2673-2684. (Proceedings - IEEE INFOCOM). doi: 10.1109/INFCOM.2004.1354686

Rigidity, computation, and randomization in network localization

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this