Distributed Sensor Location through Linear Programming with Triangle Inequality Constraints

Published

June 1, 2006

Author(s)

Camillo A. Gentile

Abstract

Interest in dense sensor networks due to falling prices and reduced size has motivated research in sensor location in recent years. To our knowledge, the algorithm which achieves the best performance in sensor location solves an optimization program by relaxing the quadratic geometrical constraints of the network to render the program convex. In recent work we proposed solving the same program, however by applying convex geometrical constraints directly, necessitating no relaxation of the constraints and in turn ensuring a tighter solution. This paper proposes a distributed version of our algorithm which achieves the same globally optimal objective function as the decentralized version. We conduct extensive experimentation to substantiate the robustness of our algorithm even in the presence of high levels of noise, and report the messaging overhead for convergence.

Conference Location

Istanbul, TU

Conference Title

IEEE International Conference on Communications

Pub Type

Conferences

Download Paper

Local Download

Keywords

Simplex Method, Primal-Dual Method, Quadratic Programming, Semi-Definite Programming

Citation

Gentile, C. (2006), Distributed Sensor Location through Linear Programming with Triangle Inequality Constraints, IEEE International Conference on Communications, Istanbul, TU, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=150593 (Accessed July 4, 2025)