The DOI matches its Crossref record; 26 of the 26 references it cites were found in a registry or an index.
Semidefinite Programming Approaches for Sensor Network Localization With Noisy Distance Measurements
Abstract
A sensor network localization problem is to determine the positions of the sensor nodes in a network given incomplete and inaccurate pairwise distance measurements. Such distance data may be acquired by a sensor node by communicating with its neighbors. We describe a general semidefinite programming (SDP)-based approach for solving the graph realization problem, of which the sensor network localization problems is a special case. We investigate the performance of this method on problems with noisy distance data. Error bounds are derived from the SDP formulation. The sources of estimation error in the SDP formulation are identified. The SDP solution usually has a rank higher than the underlying physical space which, when projected onto the lower dimensional space, generally results in high estimation error. We describe two improvements to ameliorate such a difficulty. First, we propose a regularization term in the objective function that can help to reduce the rank of the SDP solution. Second, we use the points estimated from the SDP solution as the initial iterate for a gradient-descent method to further refine the estimated points. A lower bound obtained from the optimal SDP objective value can be used to check the solution quality. Experimental results are presented to validate our methods and show that they outperform existing SDP methods. Note to Practitioners—Wireless sensor networks consist of a large number of inexpensive wireless sensors deployed in a geographical area with the ability to communicate with their neighbors within a limited radio range. Wireless sensor networks are finding increasing applicability to a range of monitoring applications in civil and military scenarios, such as biodiversity and geographical monitoring, smart homes, industrial control, surveillance, and traffic monitoring. It is often very useful in the applications of sensor networks to know the locations of the sensors. Global positioning systems suffer from many drawbacks in this scenario, such as high cost, line-of-sight issues, etc. Therefore, there is a need to develop robust and efficient algorithms that can estimate or “localize” sensor positions in a network by using only the mutual distance measures (received signal strength, time of arrival) that the wireless sensors receive from their neighbors. This paper describes an algorithm that solves the sensor network localization problem using advanced optimization techniques. We also study the effect of using very noisy measurements and propose robust methods to deal with high noise. Finally, simulation results for the algorithms are presented to demonstrate their performance in terms of computational effort and accuracy.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Linear Matrix Inequalities in System and Control Theory
Boyd, S., El Ghaoui, L., Feron, E., & Balakrishnan, V. (1994) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970777 · Cited by 21,687
Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
Sturm, J. F. (1999) · Optimization Methods and Software · doi:10.1080/10556789908805766 · Cited by 7,377
Wireless sensor networks for habitat monitoring
Mainwaring, A., Culler, D., Polastre, J., Szewczyk, R., & Anderson, J. (2002) · Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications · doi:10.1145/570738.570751 · Cited by 4,166
GPS-less low-cost outdoor localization for very small devices
Bulusu, N., Heidemann, J., & Estrin, D. (2000) · IEEE Personal Communications · doi:10.1109/98.878533 · Cited by 3,592
Understanding GPS : principles and applications
Kaplan, E. (1996) · Cited by 3,528
Understanding GPS. Principles and applications
Rycroft, M. J. (1997) · Journal of Atmospheric and Solar-Terrestrial Physics · doi:10.1016/s1364-6826(97)83337-8 · Cited by 3,409
Location systems for ubiquitous computing
Hightower, J., & Borriello, G. (2001) · Computer · doi:10.1109/2.940014 · Cited by 2,987
Dynamic fine-grained localization in Ad-Hoc networks of sensors
Savvides, A., Han, C.-C., & Strivastava, M. B. (2001) · Proceedings of the 7th annual international conference on Mobile computing and networking · doi:10.1145/381677.381693 · Cited by 2,694
SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
Toh, K. C., Todd, M. J., & Tütüncü, R. H. (1999) · Optimization Methods and Software · doi:10.1080/10556789908805762 · Cited by 1,894
Self-citationAd hoc positioning system (APS)
Niculescu, D., & Nath, B. (2002) · GLOBECOM'01. IEEE Global Telecommunications Conference (Cat. No.01CH37270) · doi:10.1109/glocom.2001.965964 · Cited by 1,801
Convex position estimation in wireless sensor networks
Doherty, L., pister, K. S. J., & El Ghaoui, L. (2002) · Proceedings IEEE INFOCOM 2001. Conference on Computer Communications. Twentieth Annual Joint Conference of the IEEE Computer and Communications Society (Cat. No.01CH37213) · doi:10.1109/infcom.2001.916662 · Cited by 1,632
Solving semidefinite-quadratic-linear programs using SDPT3
T�t�nc�, R. H., Toh, K. C., & Todd, M. J. (2003) · Mathematical Programming · doi:10.1007/s10107-002-0347-5 · Cited by 1,152
Self-citationRobust Positioning Algorithms for Distributed Ad-Hoc Wireless Sensor Networks
Savarese, C., Rabaey, J. M., & Langendoen, K. G. (2002) · Cited by 846
SDPT3 -- A Matlab Software Package for Semidefinite Programming
Toh, K.-C., Todd, M. J., & Tütüncü, R. H. (1996) · eCommons (Cornell University) · Cited by 663
Self-citationSemidefinite programming for ad hoc wireless sensor network localization
Biswas, P., & Ye, Y. (2004) · Proceedings of the 3rd international symposium on Information processing in sensor networks · doi:10.1145/984622.984630 · Cited by 573
Self-citationLocalization from connectivity in sensor networks
Shang, Y., Rumi, W., Zhang, Y., & Fromherz, M. (2004) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2004.67 · Cited by 569
Semidefinite programming based algorithms for sensor network localization
Biswas, P., Lian, T.-C., Wang, T.-C., & Ye, Y. (2006) · ACM Transactions on Sensor Networks · doi:10.1145/1149283.1149286 · Cited by 543
Self-citationLearning a kernel matrix for nonlinear dimensionality reduction
Weinberger, K. Q., Sha, F., & Saul, L. K. (2004) · Twenty-first international conference on Machine learning - ICML '04 · doi:10.1145/1015330.1015345 · Cited by 517
Rigidity, computation, and randomization in network localization
Eren, T., Goldenberg, O. K., Whiteley, W., Yang, Y. R., Morse, A. S., Anderson, B. D. O., & Belhumeur, P. N. (2005) · IEEE INFOCOM 2004 · doi:10.1109/infcom.2004.1354686 · Cited by 517
Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
Benson, S. J., Ye, Y., & Zhang, X. (2000) · SIAM Journal on Optimization · doi:10.1137/s1052623497328008 · Cited by 276
Self-citationProblems of distance geometry and convex properties of quadratic maps
Barvinok, A. I. (1995) · Discrete & Computational Geometry · doi:10.1007/bf02574037 · Cited by 226
Global Continuation for Distance Geometry Problems
Moré, J. J., & Wu, Z. (1997) · SIAM Journal on Optimization · doi:10.1137/s1052623495283024 · Cited by 208
Relaxation on a mesh: a formalism for generalized localization
Howard, A., Mataric, M. J., & Sukhatme, G. (2002) · Proceedings 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems. Expanding the Societal Role of Robotics in the the Next Millennium (Cat. No.01CH37180) · doi:10.1109/iros.2001.976308 · Cited by 180
Convergence behavior of interior-point algorithms
Güler, O., & Ye, Y. (1993) · Mathematical Programming · doi:10.1007/bf01580610 · Cited by 160
Self-citationA semidefinite programming approach to tensegrity theory and realizability of graphs
So, A. M., & Ye, Y. (2006) · doi:10.5555/1109557.1109641 · Cited by 38
Self-citationA semidefinite programming approach to tensegrity theory and realizability of graphs
So, A. M., & Ye, Y. (2006) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1145/1109557.1109641 · Cited by 28
Self-citation
Cited by
Semidefinite Relaxation of Quadratic Optimization Problems
Luo, Z.-Q., Ma, W.-K., So, A., Ye, Y., & Zhang, S. (2010) · IEEE Signal Processing Magazine · doi:10.1109/msp.2010.936019 · Cited by 3,715
Self-citationEuclidean Distance Matrices: Essential theory, algorithms, and applications
Dokmanic, I., Parhizkar, R., Ranieri, J., & Vetterli, M. (2015) · IEEE Signal Processing Magazine · doi:10.1109/msp.2015.2398954 · Cited by 611
Euclidean Distance Geometry and Applications
Liberti, L., Lavor, C., Maculan, N., & Mucherino, A. (2014) · SIAM Review · doi:10.1137/120875909 · Cited by 523
3D Human Pose Estimation from a Single Image via Distance Matrix Regression
Moreno-Noguer, F. (2017) · 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2017.170 · Cited by 397
Angular synchronization by eigenvectors and semidefinite programming
Singer, A. (2011) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2010.02.001 · Cited by 329
Metadata
- Authors
- Biswas, P., Liang, T.-C., Toh, K.-C., Ye, Y., & Wang, T.-C.
- Venue
- IEEE Transactions on Automation Science and Engineering
- Published
- 2006-10
- Volume
- 3
- Issue
- 4
- Pages
- 360-371
- ISSN
- 1545-5955 (ISSN-L)
- OpenAlex
- W2146281661
- Cited by
- 451
- References
- 26
- FWCI
- 23.62
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.