SFSDP: a Sparse Version of Full SemiDefinite Programming Relaxation for Sensor Network Localization Problems

Sunyoung Kim(skimewha.ac.kr)
Masakazu Kojima(kojimais.titech.ac.jp)
Hayato Waki(hayato.wakijsb.uec.ac.jp)
Makoto Yamashita(makoto.yamashitais.titech.ac.jp)

Abstract: SFSDP is a Matlab package for solving a sensor network localization problem. These types of problems arise in monitoring and controlling applications using wireless sensor networks. SFSDP implements the semidefinite programming (SDP) relaxation proposed in Kim et al. [2009] for sensor network localization problems, as a sparse version of the full semidefinite programming relaxation (FSDP) by Biswas and Ye [2004]. To improve the efficiency of FSDP, SFSDP exploits the aggregated and correlative sparsity of a sensor network localization problem. As a result, SFSDP can handle much larger-sized problems than other softwares, and three-dimensional anchor-free problems. SFSDP can analyze the input data of a sensor network localization problem, solves the problem, and displays the computed locations of sensors. SFSDP also includes the features of generating test problems for numerical experiments.

Keywords: Sensor network localization problems, semidefinite programming relaxation, sparsity exploitation, Matlab software package.

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Report B-457, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology

Download: [PDF]

Entry Submitted: 07/30/2009
Entry Accepted: 07/31/2009
Entry Last Modified: 07/30/2009

Modify/Update this entry