Distributed Sensor Location through Linear Programming with Triangle Inequality Constraints

Published

July 2, 2007

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

Pub Type

Journals

Download Paper

Local Download

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 May 18, 2024)