A Theory of Network Localization

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 rigi...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on mobile computing 2006-12, Vol.5 (12), p.1663-1678
Main Authors: Aspnes, J., Eren, T., Goldenberg, D.K., Morse, A.S., Whiteley, W., Yang, Y.R., Anderson, B.D.O., Belhumeur, P.N.
Format: Magazinearticle
Language:English
Subjects:
Algorithm design and analysis
algorithm/protocol design and analysis
analysis of algorithms and problem complexity
Applied sciences
architectures
communication/networking and IT
Computation
Computational complexity
computer applications
Computer networks
Computer systems organization
Computer vision
Construction
discrete mathematics
Exact sciences and technology
Foundations
geometrical problems and computation
Global Positioning System
graph theory
Graphs
Large-scale systems
Localization
location-dependent and sensitive
Mathematics
mathematics of computing
Miscellaneous
mobile applications
Mobile computing
network problems
Networks
nonnumerical algorithms and problems
Operation, maintenance, reliability
Pervasive computing
Position (location)
Printers
Sensors
Services and terminals of telecommunications
Systems, networks and services of telecommunications
Telecommunications
Telecommunications and information theory
Telemetry. Remote supervision. Telewarning. Remote control
Teleprocessing networks. Isdn
theory of computation
wireless sensor networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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
ISSN:1536-1233
1558-0660
DOI:10.1109/TMC.2006.174