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



Camillo A. Gentile


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.
IEEE Transactions on Wireless Communications


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


Gentile, C. (2007), Distributed Sensor Location through Linear Programming with Triangle Inequality Constraints, IEEE Transactions on Wireless Communications, [online], (Accessed June 25, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created July 2, 2007, Updated February 19, 2017