Approximating Sensor Network Queries Using In-Network Summaries

Free registration required

Executive Summary

In this paper the authors present new in-network techniques for communication efficient approximate query processing in wireless sensornets. They use a model-based approach that constructs and maintains a spanning tree within the network, rooted at the base-station. The tree maintains compressed summary information for each link that is used to "Stub out" traversal during query processing. The paper is based on a formal model of the in-network tree construction task framed as an optimization problem. The authors demonstrate hardness results for that problem, and develop efficient approximation algorithms for subtasks that are too expensive to compute exactly. They also propose efficient heuristics to accommodate a wider set of workloads, and empirically evaluate their performance and sensitivity to model changes.

  • Format: PDF
  • Size: 536.8 KB