Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Distributed Sensor Location through Linear Programming with Triangle Inequality Constraints

Published

Author(s)

Camillo A. Gentile

Abstract

The falling price and reduced size of sensors for monitoring spatially-sensitive environmental properties such as temperature, light, sound, and vibration have motivated research in location algorithms in recent years. To our knowledge, the algorithm which achieves the best performance refines erroneous measurements through an optimization program whose quadratic constraints force the sensors to be consistent with the geometry of the physical world. Since the program is non-convex, the authors relax the constraints to render it convex for which efficient solution methods exist. We propose solving a similar optimization program however by applying convex geometrical constraints directly, necessitating no relaxation of the constraints and in turn ensuring a solution still complaint with the physical world. We show through extensive experimentation that ours outperforms the competing algorithm across all network parameters. In addition, this paper formulates a distributed version of our algorithm which achieves the same globally optimal objective function as the centralized version, and reports the messaging overhead for its convergence.
Citation
IEEE Transactions on Wireless Communications
Volume
6
Issue
7

Keywords

primal-dual method, quadratic programming, semidefinite programming, simplex method

Citation

Gentile, C. (2007), Distributed Sensor Location through Linear Programming with Triangle Inequality Constraints, IEEE Transactions on Wireless Communications, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=51112 (Accessed June 25, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created July 2, 2007, Updated February 19, 2017