An Approximation Algorithm for Data Storage Placement in Sensor Networks
Authors:
- 1 August 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 71-78
Abstract
Data storage has become an important issue in sensor networks as a large amount of collected data needs to be archived for future information retrieval. This paper proposes to introduce storage nodes that can store data collected from the sensors in their proximities. The storage nodes alleviate the heavy load of transmitting all the data to a central place for archiving and reduce the communication cost induced by the network query. This paper considers the storage node placement problem to minimize the total power consumption for data funneling to the storage nodes and data query. We formulate it as an integer linear programming problem and present an approximation algorithm based on a rounding technique. Our simulation shows that our approximation algorithm performs well in practice.Keywords
This publication has 25 references indexed in Scilit:
- Approximating the two-level facility location problem via a quasi-greedy approachMathematical Programming, 2006
- Analysis of hop-distance relationship in spatially random sensor networks2005
- On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem2005
- Data MULEs: modeling a three-tier architecture for sparse sensor networks2003
- A new greedy approach for facility location problems2002
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxationJournal of the ACM, 2001
- Analysis of a Local Search Heuristic for Facility Location ProblemsJournal of Algorithms, 2000
- GPSR2000
- Greedy Strikes Back: Improved Facility Location AlgorithmsJournal of Algorithms, 1999
- Approximation algorithms for facility location problems (extended abstract)1997