A theory of network localization

James Aspnes; Tolga Eren; David K. Goldenberg; A. Stephen Morse; Walter Whiteley; Richard Yang; Brian D.O. Anderson; Peter N. Belhumeur

doi:10.1109/TMC.2006.174

A theory of network localization

James Aspnes^*, Tolga Eren, David K. Goldenberg, A. Stephen Morse, Walter Whiteley, Richard Yang, Brian D.O. Anderson, Peter N. Belhumeur

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

529 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
Article number	1717436
Pages (from-to)	1663-1677
Number of pages	15
Journal	IEEE Transactions on Mobile Computing
Volume	5
Issue number	12
DOIs	https://doi.org/10.1109/TMC.2006.174
Publication status	Published - Dec 2006
Externally published	Yes

Access to Document

10.1109/TMC.2006.174

Cite this

@article{35e833b31aba4317a10a9da0d1c8c5c5,

title = "A theory of 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.",

keywords = "Algorithm/protocol design and analysis, Analysis of algorithms and problem complexity, Architectures, Communication/networking and IT, Computer systems organization, Mobile computing, Nonnumerical algorithms and problems, Theory of computation",

author = "James Aspnes and Tolga Eren and Goldenberg, {David K.} and Morse, {A. Stephen} and Walter Whiteley and Richard Yang and Anderson, {Brian D.O.} and Belhumeur, {Peter N.}",

year = "2006",

month = dec,

doi = "10.1109/TMC.2006.174",

language = "English",

volume = "5",

pages = "1663--1677",

journal = "IEEE Transactions on Mobile Computing",

issn = "1536-1233",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "12",

}

TY - JOUR

T1 - A theory of network localization

AU - Aspnes, James

AU - Eren, Tolga

AU - Goldenberg, David K.

AU - Morse, A. Stephen

AU - Whiteley, Walter

AU - Yang, Richard

AU - Anderson, Brian D.O.

AU - Belhumeur, Peter N.

PY - 2006/12

Y1 - 2006/12

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.

KW - Algorithm/protocol design and analysis

KW - Analysis of algorithms and problem complexity

KW - Architectures

KW - Communication/networking and IT

KW - Computer systems organization

KW - Mobile computing

KW - Nonnumerical algorithms and problems

KW - Theory of computation

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

U2 - 10.1109/TMC.2006.174

DO - 10.1109/TMC.2006.174

M3 - Article

SN - 1536-1233

VL - 5

SP - 1663

EP - 1677

JO - IEEE Transactions on Mobile Computing

JF - IEEE Transactions on Mobile Computing

IS - 12

M1 - 1717436

ER -

A theory of network localization

Abstract

Access to Document

Other files and links

Fingerprint

Cite this