Retrieval of the Extreme Values under Deadline Constraints in Wireless Sensor Networks

Seung Jun Baek, Xiaohan Yu, Kyogu Lee, Hyunhak Kim

TL;DR

This paper tackles the challenge of efficiently retrieving the most extreme (e.g., highest temperature) data from wireless sensor networks (WSNs) under strict deadlines, crucial for applications like alarm systems. They propose a novel distributed scheme that prioritizes high-urgency data, reduces network traffic through selective forwarding and overhearing, and significantly decreases retrieval latency compared to baseline methods.

What Problem Does This Paper Address?

Wireless sensor networks (WSNs) are deployed for various monitoring tasks, and a common objective is to summarize the sensed data, often by finding extreme values (maximum or minimum). This is particularly important for "alarm" systems where detecting an unusual or extreme event (like a dangerously high temperature) requires timely notification. The core challenge is retrieving this extreme data to a central "sink" node within a strict deadline. In WSNs, sensors generate data that can be heterogeneous and may not be directly comparable. Furthermore, forwarding all data to the sink would lead to significant network traffic, energy consumption, and increased latency, making it difficult to meet deadlines. This paper addresses the problem of maximizing the probability of retrieving the extreme data within a given deadline, focusing on a distributed approach that balances prioritizing urgent data with managing network contention.

Methods

The authors propose a three-pronged approach to tackle this problem:

  1. Priority-Based Medium Access: Instead of treating all data equally, sensors "score" their data based on how much it deviates from its usual distribution, representing its urgency. A novel distributed medium access control (MAC) scheme is introduced where sensors with higher scores are given higher priority to access the communication channel. This is achieved through a randomized back-off mechanism that is dynamically adjusted based on the data's score and the number of previous collisions. The goal is to ensure that high-urgency data gets transmitted earlier.
  2. Selective Forwarding: This technique leverages the "max" function's property. If a sensor receives a data packet (score) that is lower than the highest score it has already processed or forwarded, it can simply drop the packet. This significantly reduces unnecessary traffic and the associated contention.
  3. Exploiting Overhearing: Since wireless transmissions are broadcast, sensors can overhear transmissions from nearby nodes. If a sensor overhears data with a higher score than its current highest-known score, it updates its record. This information can then be used to further suppress unnecessary transmissions through selective forwarding, creating a synergistic effect.

These three techniques are combined into a unified, fully distributed scheme.

Datasets

Not discussed in the paper. The paper focuses on a simulated network environment and does not use real-world datasets.

Key Insights and Ideas

  • Data Urgency as a Score: Mapping raw sensor data to a "score" based on its deviation from normal behavior provides a unified measure of urgency, enabling prioritization even with heterogeneous sensor data.
  • Balancing Priority and Contention: Aggressively prioritizing high-score data is beneficial, but it must be balanced to avoid excessive collisions. The proposed scheme dynamically adjusts contention based on score and collision history.
  • Synergistic Effect of Techniques: Combining priority-based MAC with selective forwarding and overhearing creates a powerful system. Reduced traffic from selective forwarding and overhearing allows for more aggressive priority assignment in the MAC layer, leading to a virtuous cycle of reduced latency.
  • Distributed Nature is Key: The entire scheme is designed to be fully distributed, which is crucial for WSNs where centralized control is often impractical.

Key Results

The paper demonstrates through simulations that the proposed scheme significantly outperforms a baseline scheme (uniform medium access with simple aggregation) in reducing retrieval latency.

  • For retrieving the maximum data (b=1), the proposed scheme achieved latency reductions of 19%-20% (for m=10) and 15%-17% (for m=30) at a retrieval probability of 0.8.
  • When retrieving multiple extreme values (b=3), the latency reduction increased to 32–33% (m=10) and 30–32% (m=30) at a retrieval probability of 0.8.
  • Mean latency reductions ranged from 15.1-18.0% for b=1 and 31.1-34.3% for b=3.
  • The proposed scheme achieves a good balance between prioritizing high-score nodes and maintaining a sufficient number of successful transmissions, unlike some other priority-based schemes that might reduce transmissions too much.

Limitations and Future Work

  • Analytical Approximation: The analytical model for transmission probability assumes an infinite number of minislots (m → ∞) and ignores collisions. While the results show good agreement with simulations for finite m, especially for conditional probabilities, it's an approximation.
  • Parameter Tuning: The performance is sensitive to system parameters like γ (warping factor) and β (lower bound for ECW size). The paper suggests that setting γ > 1 and β small leads to more aggressive behavior, but optimal tuning for specific scenarios might require further investigation.
  • Extension to k-Maximum Retrieval: The paper discusses extensions for retrieving the k-th largest data and for periodically generated data samples, suggesting these are areas for future research.
  • Optimizing Waiting Times: The current scheme transmits data as soon as it's available. The authors note that extending the scheme to incorporate optimized waiting times for aggregation could be a future direction.

Summary updated

Abstract

We consider a problem of retrieving the extreme value among sensed data under deadline constraints in wireless sensor networks with potential applications to alarm systems. The sensed data is mapped to a score which we adopt as a unified measure of the relative urgency of the data. The objective is to retrieve the data with the maximum score. We propose fully distributed schemes for contention based medium access and data combining. The proposed medium access scheme uses a randomized back-off which is controlled based on the score of the data to be transmitted. Data combining techniques are proposed to further suppress unnecessary traffic and reduce contention. The key observation is that one should aggressively prioritize packets with high score, up to an extent that does not incur excessive contention in channel access. Designed to capture such aspect, the proposed scheme is shown to substantially decrease the latency of the retrieval.
BibTeX
@inproceedings{baek2011retrieval,
  author = {Seung Jun Baek and Xiaohan Yu and Kyogu Lee and Hyunhak Kim},
  title = {{Retrieval of the Extreme Values under Deadline Constraints in Wireless Sensor Networks}},
  booktitle = {Sensors},
  year = {2011},
  url = {https://openreview.net/forum?id=FDKc4_HBEUn},
}

Loading related content...

Figure