Optimization Online


Solving the Sensor Network Localization Problem using an Heuristic Multistage Approach

Andrea Cassioli (cassioli***at***dsi.unifi.it)

Abstract: The Sensor Network Localization Problem (SNLP), arising from many applied fields related with environmental monitoring, has attracted much research during the last years. Solving the SNLP deals with the reconstruction of a geometrical structure from incomplete pairwise distances between sensors. In this paper we present an heuristic multistage approach in which the solving strategy is tailored on the type of problem instance at hand, formulated as a box-constrained optimization problem. We focus on low-noise SNLP, a scenario common in literature for which we propose a geometric routine (based on trilateration) to find a starting guess for the sensor configuration. Local searches and problem dependent decomposition techniques are then applied to refine the sensor localizations. Computational results are presented and compared with different test sets available in literature, showing the proposed strategy to be effective for this family of SNLP instances and quite robust in different settings.

Keywords: Sensor network localization ; Graph realization ; Distance geometry ; Decomposition Techniques

Category 1: Nonlinear Optimization (Bound-constrained Optimization )

Category 2: Applications -- OR and Management Sciences (Telecommunications )


Download: [PDF]

Entry Submitted: 03/26/2009
Entry Accepted: 03/26/2009
Entry Last Modified: 01/13/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society