More Web Proxy on the site http://driver.im/

article

Theory of semidefinite programming for Sensor Network Localization

Authors:

Anthony Man-Cho So,

Yinyu YeAuthors Info & Claims

Mathematical Programming: Series A and B, Volume 109, Issue 2-3

Pages 367 - 384

Published: 01 March 2007 Publication History

Abstract

We analyze the semidefinite programming (SDP) based model and method for the position estimation problem in sensor network localization and other Euclidean distance geometry applications. We use SDP duality and interior-point algorithm theories to prove that the SDP localizes any network or graph that has unique sensor positions to fit given distance measures. Therefore, we show, for the first time, that these networks can be localized in polynomial time. We also give a simple and efficient criterion for checking whether a given instance of the localization problem has a unique realization in $$\mathcal{R}^2$$ using graph rigidity theory. Finally, we introduce a notion called strong localizability and show that the SDP model will identify all strongly localizable sub-networks in the input network.

References

[1]

Alfakih A.Y. (2000): Graph rigidity via euclidean distance matrices. Linear Algebra Appl. 310, 149---165

[2]

Alfakih A.Y. (2001): On rigidity and realizability of weighted graphs. Linear Algebra Appl. 325, 57---70

[3]

Alfakih A.Y., Khandani A., Wolkowicz H. (1999): Solving euclidean distance matrix completion problems via semidefinite programming. Comput. Opt. Appl. 12, 13---30

Digital Library

[4]

Alfakih, A.Y., Wolkowicz, H.: On the embeddability of weighted graphs in euclidean spaces. Research Report CORR 98-12, University of Waterloo, Department of Combinatorics and Optimization (1998)

[5]

Alfakih, A.Y., Wolkowicz, H.: Euclidean distance matrices and the molecular conformation problem. Research Report CORR 2002-17, University of Waterloo, Department of Combinatorics and Optimization (2002)

[6]

Alizadeh F. (1995): Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Opt. 5, 13---51

[7]

Aspnes, J., Goldenberg, D., Yang, Y.R.: On the computational complexity of sensor network localization. ALGOSENSORS 2004, in LNCS 3121, 32---44 (2004)

[8]

Bă¿doiu, M.: Approximation algorithm for embedding metrics into a two-dimensional space. Proceedings 14th SODA, pp. 434---443 (2003)

Digital Library

[9]

Bă¿doiu, M., Demaine, E.D., Hajiaghayi, M.T., Indyk, P.: Low-dimensional embedding with extra information. Proceedings 20th SoCG, pp. 320---329 (2004)

Digital Library

[10]

Barvinok A. (1995): Problems of distance geometry and convex properties of quadratic maps. Disc. Comput. Geom. 13, 189---202

Digital Library

[11]

Barvinok, A.: A course in convexity. AMS (2002)

[12]

Biswas, P., Ye, Y.: Semidefinite programming for Ad Hoc wireless sensor network localization. Proceedings 3rd IPSN, pp. 46---54 (2004)

Digital Library

[13]

Boyd, S., Ghaoui, L.E., Feron, E., Balakrishnan, V.: Linear matrix inequalities in system and control theory. SIAM (1994)

[14]

Doherty, L., Ghaoui, L.E., Pister, S.J.: Convex position estimation in wireless sensor networks. Proceedings 20th INFOCOM, Vol. 3, pp. 1655---1663 (2001)

[15]

Eren, T., Goldenberg, D.K., Whiteley, W., Yang, Y.R., Moore, A.S., Anderson, B.D.O., Belhumeur, P.N.: Rigidity, computation, and randomization in network localization. Proceedings 23rd INFOCOM (2004)

[16]

Goldfarb D., Scheinberg K. (1998): Interior point trajectories in semidefinite programming. SIAM J. Opt. 8(4): 871---886

Digital Library

[17]

Gower, J.C.: Some distance properties of latent root and vector methods in multivariate analysis. Biometrika 53 325---338 (1966)

[18]

Graver, J., Servatius, B., Servatius, H.: Combinatorial rigidity. AMS (1993)

[19]

Güler O., Ye Y. (1993): Convergence behavior of interior point algorithms. Math. Prog. 60, 215---228

Digital Library

[20]

Hendrickson B. (1992): Conditions for unique graph realizations. SIAM J. Comput. 21(1): 65---84

Digital Library

[21]

Hendrickson B. (1995): The molecule problem: exploiting structure in global optimization. SIAM J. Opt. 5(4): 835---857

[22]

Jackson, B., Jordán, T.: Connected rigidity matroids and unique realizations of graphs. Preprint (2003)

[23]

Laurent M. (2001): Matrix completion problems. The Encycl. Optim. 3, 221---229

[24]

Linial N., London E., Rabinovich Yu. (1995): The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2): 215---245

[25]

Moré J., Wu Z. (1997): Global continuation for distance geometry problems. SIAM J. Opt. 7, 814---836

Digital Library

[26]

Savarese, C., Rabay, J. Langendoen, K.: Robust positioning algorithms for distributed Ad-Hoc wireless sensor networks. USENIX Annual Technical Conference (2002)

Digital Library

[27]

Savvides, A., Han, C.-C., Srivastava, M.B.: Dynamic fine-grained localization in Ad-Hoc networks of sensors. Proceedings 7th MOBICOM, pp. 166---179 (2001)

Digital Library

[28]

Savvides, A., Park, H., Srivastava, M.B.: The bits and flops of the n-hop multilateration primitive for node localization problems. Proceedings 1st WSNA, pp. 112---121 (2002)

Digital Library

[29]

Schoenberg I.J. (1935): Remarks to Maurice Fréchet's Article "Sur la Définition Axiomatique d'une Classe d'Espace Distanciés Vectoriellement Applicable sur l'Espace de Hilbert". Ann. Math. 36(3): 724---732

[30]

Shang, Y., Ruml, W., Zhang, Y., Fromherz, M.P.J.: Localization from mere connectivity. Proceedings 4th MOBIHOC, pp. 201---212 (2003)

Digital Library

[31]

Torgerson W.S. (1952): Multidimensional scaling: I. theory and method. Psychometrika 17, 401---419

[32]

Trosset M.W. (2000): Distance matrix completion by numerical optimization. Comput. Opt. Appl. 17, 11---22

Digital Library

[33]

Trosset M.W. (2002): Extensions of classical multidimensional scaling via variable reduction. Comput. Stat. 17(2): 147---162

[34]

Young G., Householder A.S. (1938): Discussion of a set of points in terms of their mutual distances. Psychometrika 3, 19---22

Cited By

Ping HWang YShen XLi DChen W(2022)On Node Localizability Identification in Barycentric Linear LocalizationACM Transactions on Sensor Networks10.1145/354714319:1(1-26)Online publication date: 8-Dec-2022
https://dl.acm.org/doi/10.1145/3547143
Jing GWan CDai R(2022)Angle Fixability and Angle-Based Sensor Network Localization2019 IEEE 58th Conference on Decision and Control (CDC)10.1109/CDC40024.2019.9029907(7899-7904)Online publication date: 28-Dec-2022
https://dl.acm.org/doi/10.1109/CDC40024.2019.9029907
Tabaghi PDokmanić IVetterli M(2020)Kinetic Euclidean Distance MatricesIEEE Transactions on Signal Processing10.1109/TSP.2019.295926068(452-465)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1109/TSP.2019.2959260
Show More Cited By

Index Terms

Theory of semidefinite programming for Sensor Network Localization

Recommendations

Explicit Sensor Network Localization using Semidefinite Representations and Facial Reductions

The sensor network localization (SNL) problem in embedding dimension $r$ consists of locating the positions of wireless sensors, given only the distances between sensors that are within radio range and the positions of a subset of the sensors (called ...
Sensor network localization, euclidean distance matrix completions, and graph realization
MELT '08: Proceedings of the first ACM international workshop on Mobile entity localization and tracking in GPS-less environments

We study Semidefinite Programming, SDP, relaxations for Sensor Network Localization, SNL, with anchors and with noisy distance information. The main point of the paper is to view SNL as a (nearest) Euclidean Distance Matrix, EDM, completion problem and ...
Semidefinite programming based algorithms for sensor network localization

An SDP relaxation based method is developed to solve the localization problem in sensor networks using incomplete and inaccurate distance information. The problem is set up to find a set of sensor positions such that given distance constraints are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematical Programming: Series A and B

Mathematical Programming: Series A and B Volume 109, Issue 2-3

March 2007

408 pages

ISSN:0025-5610

Issue’s Table of Contents

Copyright © Copyright © 2007 Springer-Verlag.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 March 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ping HWang YShen XLi DChen W(2022)On Node Localizability Identification in Barycentric Linear LocalizationACM Transactions on Sensor Networks10.1145/354714319:1(1-26)Online publication date: 8-Dec-2022
https://dl.acm.org/doi/10.1145/3547143
Jing GWan CDai R(2022)Angle Fixability and Angle-Based Sensor Network Localization2019 IEEE 58th Conference on Decision and Control (CDC)10.1109/CDC40024.2019.9029907(7899-7904)Online publication date: 28-Dec-2022
https://dl.acm.org/doi/10.1109/CDC40024.2019.9029907
Tabaghi PDokmanić IVetterli M(2020)Kinetic Euclidean Distance MatricesIEEE Transactions on Signal Processing10.1109/TSP.2019.295926068(452-465)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1109/TSP.2019.2959260
Farias VLi A(2019)Learning Preferences with Side InformationManagement Science10.1287/mnsc.2018.309265:7(3131-3149)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1287/mnsc.2018.3092
Shen XMitchell J(2018)A penalty method for rank minimization problems in symmetric matricesComputational Optimization and Applications10.5555/3287989.328801471:2(353-380)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.5555/3287989.3288014
Zhou XShi PLim CYang CGui W(2018)A dynamic state transition algorithm with application to sensor network localizationNeurocomputing10.1016/j.neucom.2017.08.010273:C(237-250)Online publication date: 17-Jan-2018
https://dl.acm.org/doi/10.1016/j.neucom.2017.08.010
Yuan GGhanem B(2016)A proximal Alternating Direction Method for semi-definite rank minimizationProceedings of the Thirtieth AAAI Conference on Artificial Intelligence10.5555/3016100.3016220(2300-2308)Online publication date: 12-Feb-2016
https://dl.acm.org/doi/10.5555/3016100.3016220
Gepshtein SKeller Y(2015)Sensor Network Localization by Augmented Dual EmbeddingIEEE Transactions on Signal Processing10.1109/TSP.2015.241121163:9(2420-2431)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1109/TSP.2015.2411211
Zorn KSahinidis N(2014)Global optimization of general nonconvex problems with intermediate polynomial substructuresJournal of Global Optimization10.1007/s10898-014-0190-259:2-3(673-693)Online publication date: 1-Jul-2014
https://dl.acm.org/doi/10.1007/s10898-014-0190-2
Zhao YFukushima M(2013)Rank-one solutions for homogeneous linear matrix equations over the positive semidefinite coneApplied Mathematics and Computation10.1016/j.amc.2012.11.022219:10(5569-5583)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1016/j.amc.2012.11.022
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents