A theory of network localization

被引：419

作者：

Aspnes, James

Eren, Tolga

Goldenberg, David K.

Morse, A. Stephen

Whiteley, Walter

Yang, Yang Richard

Anderson, Brian D. O.

Belhumeur, Peter N.

机构：

[1] Yale Univ, Dept Comp Sci, New Haven, CT 06520 USA

[2] Yale Univ, Dept Elect Engn, Lab Control Sci & Engn, New Haven, CT 06520 USA

[3] York Univ, Dept Math & Stat, N York, ON M3J 1P3, Canada

[4] Natl ICT Australia Ltd, Canberra, ACT 2601, Australia

[5] Columbia Univ, Dept Comp Sci, New York, NY 10029 USA

来源：

IEEE TRANSACTIONS ON MOBILE COMPUTING | 2006年 / 5卷 / 12期

关键词：

computer systems organization; communication/networking and IT; mobile computing; algorithm/protocol design and analysis; architectures; theory of computation; analysis of algorithms and problem complexity; nonnumerical algorithms and problems; geometrical problems and computation; mathematics of computing; discrete mathematics; graph theory; network problems; computer applications; mobile applications; location-dependent and sensitive; wireless sensor networks;

D O I：

10.1109/TMC.2006.174

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：1663 / 1678

页数：16

共 62 条

[1] Recursive position estimation in sensor networks [J].

Albowicz, J ;

Chen, A ;

Zhang, LX .

NETWORK PROTOCOLS, 2001, :35-41

[2] Solving Euclidean distance matrix completion problems via semidefinite programming [J].

Alfakih, AY ;

Khandani, A ;

Wolkowicz, H .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 1999, 12 (1-3) :13-30

[3]

ANDERSON BDO, 2005, GRAPH PROPERTIES EAS

[4]

[Anonymous], P IEEE INFOCOM 03 AP

[5]

[Anonymous], P 6 INT WORKSH DISCR

[6]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[7] The maximum vertex degree of a graph on uniform points in [0,1](d) [J].

Appel, MJB ;

Russo, RP .

ADVANCES IN APPLIED PROBABILITY, 1997, 29 (03) :567-581

[8]

ASPNES J, 2004, P 1 INT WORKSH ALG A

[9]

BERG A, 2002, J COMBINATORIAL TH B

[10]

BISWAS P, 2004, P 3 INT WORKSH INF P

← 1 2 3 4 5 6 7 →