Skip to main navigation Skip to search Skip to main content

Efficient scheduling for periodic aggregation queries in multihop sensor networks

  • Illinois Institute of Technology
  • Tsinghua University
  • Hangzhou Dianzi University

Research output: Contribution to journal › Article › peer-review

58 Scopus citations

Abstract

In this paper, we study periodic query scheduling for data aggregation with minimum delay under various wireless interference models. Given a set $ of periodic aggregation queries, each query Q i ∈ $ has its own period Q i ∈ $ and the subset of source nodes Q i ∈ $ containing the data. We first propose a family of efficient and effective real-time scheduling protocols that can answer every job of each query task Q i ∈ $ within a relative delay O(Pi) under resource constraints by addressing the following tightly coupled tasks: routing, transmission plan constructions, node activity scheduling, and packet scheduling. Based on our protocol design, we further propose schedulability test schemes to efficiently and effectively test whether, for a set of queries, each query job can be finished within a finite delay. Our theoretical analysis shows that our methods achieve at least a constant fraction of the maximum possible total utilization for query tasks, where the constant depends on wireless interference models. We also conduct extensive simulations to validate the proposed protocol and evaluate its practical performance. The simulations corroborate our theoretical analysis.

Original languageEnglish
Article number6045302
Pages (from-to)690-698
Number of pages9
JournalIEEE/ACM Transactions on Networking
Volume20
Issue number3
DOIs
StatePublished - Jun 2012

Keywords

  • Aggregation
  • delay
  • interference
  • periodic
  • query scheduling
  • schedulability
  • utilization

Fingerprint

Dive into the research topics of 'Efficient scheduling for periodic aggregation queries in multihop sensor networks'. Together they form a unique fingerprint.

Cite this