TSAR: a two tier sensor storage architecture using interval skip graphs

Peter Desnoyers, Deepak Ganesan, Prashant J. ShenoySenSys 2005 · DOI

TL;DR

This paper introduces TSAR, a novel two-tier storage architecture for sensor networks that separates data from metadata. By leveraging resource-rich proxies for distributed indexing and energy-efficient local storage at sensors, TSAR efficiently supports spatio-temporal and value-based queries while minimizing sensor energy consumption.

What Problem Does This Paper Address?

Modern sensor networks are increasingly multi-tiered, with many low-power, untethered sensors managed by more powerful, tethered proxies. Existing sensor storage systems often assume a flat, homogeneous architecture, failing to exploit this tiered structure. This leads to inefficiencies: either all data is sent to a central server (high write cost, potential bottleneck) or sensors must handle complex queries and indexing (high energy cost). The challenge is to design a storage system that effectively utilizes the distinct resource capabilities of each tier, enabling efficient data archival and retrieval while respecting the severe energy constraints of individual sensors.

Methods

TSAR's core innovation lies in its two-tier approach:

  • Proxy Tier: Interval Skip Graph: TSAR employs a novel distributed index structure called the Interval Skip Graph. This structure combines features of Interval Trees and Skip Graphs to efficiently store and query ordered intervals (representing time or value ranges). It offers O(log n) expected search and update complexity and provides a unified view of distributed sensor data. A "sparse" variant is introduced to optimize for scenarios with many more data items than proxies, reducing network overhead.
  • Sensor Tier: Local Archive and Adaptive Summarization: Each sensor maintains a local, append-only circular buffer in flash memory for archival. Crucially, sensors don't store complex indexes. Instead, they periodically send "summaries" of their data (metadata, time intervals, and pointers to local data) to proxies. TSAR also introduces an adaptive summarization technique. Sensors dynamically adjust the granularity of their summaries based on the ratio of true hits to false hits from application queries, balancing the energy cost of sending summaries against the cost of wasted energy on false query results.

Datasets

The paper uses two datasets for evaluation:

  • James Reserve Data: A temperature dataset from eleven temperature sensors over 34 days.
  • Synthetic Data: Data generated using a uniformly distributed random walk.

These datasets are used to seed sensor nodes in simulations and on the testbed, ensuring repeatable experiments.

Key Insights and Ideas

  • Tiered Architecture is Key: The paper strongly argues that a one-size-fits-all storage approach for sensor networks is insufficient. Exploiting the distinct resource capabilities of sensors and proxies is crucial for efficiency.
  • Separation of Data and Metadata: Storing raw data locally on sensors and using proxies for distributed metadata indexing is a powerful paradigm. This allows sensors to remain simple and energy-efficient while enabling complex queries at the proxy level.
  • Interval Skip Graphs for Spatio-Temporal Data: The Interval Skip Graph is a well-suited data structure for indexing spatio-temporal and value-based sensor data, offering efficient range query support.
  • Adaptive Summarization Balances Trade-offs: The adaptive summarization technique is a clever way to dynamically manage the energy cost of metadata updates versus the cost of false positives during queries, a fundamental trade-off in distributed sensor data management.
  • Flash Memory is a Game Changer: The paper highlights the increasing capacity and decreasing energy cost of flash memory, making local archival storage on sensors a viable and energy-efficient strategy.

Key Results

  • Query Performance: TSAR achieves low end-to-end query latency, with components like sensor communication (approx. 300ms per hop) and proxy communication being dominant factors.
  • Index Performance: Sparse Interval Skip Graphs demonstrate logarithmic scaling for inserts and lookups, with performance improving with fewer proxies.
  • Energy Efficiency: NAND flash memory is shown to be significantly more energy-efficient (up to 150x) than radio communication for data storage and retrieval.
  • Adaptive Summarization Effectiveness: Simulations show that the adaptive summarization algorithm successfully adjusts summary granularity to balance update costs and false hit rates in response to varying query rates.
  • Resilience: The skip graph structure provides resilience to proxy failures, with remaining data still accessible. Redundant summaries further enhance resilience against single proxy failures.

Limitations and Future Work

  • Testbed Size: The physical testbed was limited to four proxies and twelve sensors, necessitating simulations for evaluating larger-scale scenarios.
  • Query Types: The current implementation primarily supports range queries on value or time, with planned extensions to include spatial scoping.
  • Summarization Granularity: The paper focuses on adapting the interval over which summaries are constructed, noting that application-specific adaptation of the data summary itself (e.g., using wavelet compression) is a separate area.
  • Failure Handling: While skip graphs offer resilience to proxy failures, handling of sensor node failures and wireless link fading is largely outside the scope of this paper.
  • Future Work: The authors suggest exploring other index structures for alternate query types and further investigating adaptive summarization techniques.

Summary updated

BibTeX
@inproceedings{desnoyers2005tsar,
  author = {Peter Desnoyers and Deepak Ganesan and Prashant J. Shenoy},
  title = {{TSAR: a two tier sensor storage architecture using interval skip graphs}},
  booktitle = {SenSys},
  year = {2005},
  doi = {10.1145/1098918.1098923},
}
Figure