Optimization Online


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

Sunyoung Kim(skim***at***ewha.ac.kr)
Masakazu Kojima(kojima***at***is.titech.ac.jp)
Hayato Waki(hayato.waki***at***jsb.uec.ac.jp)
Makoto Yamashita(makoto.yamashita***at***is.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

  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