Three approximation algorithms for energy-efficient query dissemination in sensor database system

Zhao Zhang, Xiaofeng Gao, Xuefei Zhang, Weili Wu, Hui Xiong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

Sensor database is a type of database management system which offers sensor data and stored data in its data model and query languages. In this system, when a user poses a query to this sensor database, the query will be disseminated across the database. During this process, each sensor generates data that match the query from its covered area and then returns the data to the original sensor. In order to achieve an energy-efficient implementation, it will be useful to select a minimally sufficient subset of sensors to keep active at any given time. Thus, how to find a subset efficiently is an important problem for sensor database system. We define this problem as sensor database coverage (SDC) problem. In this paper, we reduce the SDC problem to connected set cover problem, then present two approximation algorithms to select a minimum connected set cover for a given sensor database. Moreover, to guarantee robustness and accuracy, we require a fault-tolerant sensor database, which means that each target in a query region will be covered by at least m sensors, and the selected sensors will form a k-connected subgraph. We name this problem as (k,m)-SDC problem and design another approximation algorithm. These three algorithms are the first approximation algorithms with guaranteed approximation ratios to SDC problem. We also provide simulations to evaluate the performance of our algorithms. We compare the results with algorithms in [17]. The comparison proves the efficiency of our approximations. Thus, our algorithms will become a new efficient approach to solve coverage problem in sensor database systems.

Original languageEnglish (US)
Title of host publicationDatabase and Expert Systems Applications - 20th International Conference, DEXA 2009, Proceedings
Pages807-821
Number of pages15
DOIs
StatePublished - 2009
Event20th International Conference on Database and Expert Systems Applications, DEXA 2009 - Linz, Austria
Duration: Aug 31 2009Sep 4 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5690 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th International Conference on Database and Expert Systems Applications, DEXA 2009
Country/TerritoryAustria
CityLinz
Period8/31/099/4/09

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Fault Tolerance
  • Sensor Database
  • Set Cover

Fingerprint

Dive into the research topics of 'Three approximation algorithms for energy-efficient query dissemination in sensor database system'. Together they form a unique fingerprint.

Cite this