Delay Bounded Maintenance Scheme in Rechargeable Wireless Sensor Networks

Demin Gao, Fuquan Zhang, Jun SongJ. Commun 2013 · DOI

TL;DR

This paper tackles the challenge of ensuring timely data delivery in rechargeable wireless sensor networks (R-WSNs) where energy availability fluctuates. They propose a novel "Active Instance Augmentation" scheme that intelligently adds brief active periods to nodes' schedules to guarantee end-to-end (E2E) delay bounds, significantly outperforming existing methods in reducing delay with minimal energy overhead.

What Problem Does This Paper Address?

Wireless Sensor Networks (WSNs) are crucial for monitoring environments, but their limited battery life is a major bottleneck. Rechargeable WSNs (R-WSNs) aim to overcome this by harvesting energy from the environment. However, this harvested energy is often sporadic and insufficient to power nodes continuously. Consequently, R-WSNs must operate with very low duty cycles, spending most of their time in a sleep state to conserve energy and recharge. This low duty cycle inherently leads to high packet delivery latency, as nodes have to wait for their neighbors to wake up. In many applications, such as critical event detection or command dissemination, meeting strict end-to-end (E2E) delay bounds is essential. Existing solutions often face a trade-off between network lifetime and delay, but in R-WSNs, lifetime is less of a concern due to recharging capabilities. The core problem this paper addresses is how to guarantee E2E delay bounds in R-WSNs without compromising energy efficiency, given the dynamic nature of energy harvesting.

Methods

The paper introduces an "Active Instance Augmented Scheme" to address the E2E delay problem. The core idea is to strategically add short "active instances" to a node's existing working schedule. These augmentations are designed to reduce the sleep latency experienced when a node needs to transmit a packet to a neighbor that might be in its sleep state.

The scheme involves:

  • Active Instance Augmentation: When a node's E2E delay to the sink exceeds a predefined bound, it checks if augmenting its active instance (or its neighbors') can help. This augmentation is only performed if the node has sufficient energy to support the brief active period.
  • Ordinal Sequence Analysis: The effectiveness of augmentation depends on the relative timing of active instances of three consecutive nodes in a path (Nᵢ, Nᵢ₊₁, Nᵢ₊₂). The paper analyzes six different scenarios based on the timing of these instances to determine when augmentation will reduce E2E delay.
  • Algorithm for Finding Minimal Augmentations: An algorithm is proposed to calculate the minimum number of active instances (h) that need to be augmented to meet the E2E delay bound (B). This algorithm aims to minimize energy consumption by finding the smallest h.
  • E2E Delay Maintenance Procedure: A step-by-step procedure is outlined for nodes to check their current E2E delay against the bound and, if necessary, initiate the augmentation process. This process propagates along the path, ensuring that the delay bound is met.

The proposed approach is distributed, meaning each node makes decisions locally based on its own state and information from its neighbors.

Datasets

Not discussed in the paper. The evaluation is based on extensive simulations.

Key Insights and Ideas

  • Active Instance Augmentation as a Targeted Solution: Instead of a blanket increase in duty cycle, the paper proposes a more nuanced approach of adding specific, short active periods. This is crucial for energy efficiency in R-WSNs.
  • The Importance of Relative Timing: The effectiveness of augmentation is highly dependent on the relative timing of active instances of neighboring nodes. Not all augmentations are beneficial; the paper precisely identifies the conditions under which they are effective.
  • Minimizing Energy for Delay Guarantees: The core contribution is achieving delay bounds with minimal energy expenditure by carefully selecting when and how many active instances to augment.
  • Distributed Decision-Making: The proposed scheme operates in a distributed manner, which is essential for the scalability and robustness of WSNs. Nodes only need local information to make decisions.

Key Results

The paper demonstrates the effectiveness of their "Delay Maintenance" scheme through simulations and comparisons with a baseline algorithm (D-APOLLO).

  • Reduced Number of Augmentations: The proposed scheme requires approximately 20% fewer augmented active instances compared to D-APOLLO to achieve the same delay bounds.
  • Lower E2E Delay: In simulations, the Delay Maintenance scheme consistently achieved lower E2E delays than D-APOLLO across various augmentation levels.
  • Faster Delay Reduction: The E2E delay of the Delay Maintenance scheme drops more quickly as the number of augmented active instances increases, indicating greater efficiency.
  • Significant E2E Delay Reduction: For instance, after augmenting 5 active instances, the Delay Maintenance scheme reduced E2E delay by 50 units, while D-APOLLO only reduced it by 38 units, representing a 30% greater reduction.
  • Time Complexity: The time complexity for delay maintenance at individual nodes is O(1), leading to an overall complexity of O(n) for bounding E2E delay from a node to the sink.

Limitations and Future Work

  • Energy Neutrality Assumption: The paper assumes energy-neutral operation, meaning nodes can harvest enough energy to sustain their operations over time. The performance might differ in scenarios where energy harvesting is consistently insufficient.
  • Synchronous Schemes: The paper assumes synchronous schemes for network synchronization, which might not always be feasible in highly dynamic R-WSNs.
  • Future Work: The authors suggest exploring the impact of different energy harvesting rates and environmental conditions on the proposed scheme. Further research could also investigate more complex network topologies and dynamic node failures. The paper also mentions the possibility of extending the scheme to consider two-hop delays, which could be a direction for future work.

Summary updated

BibTeX
@article{gao2013delay,
  author = {Demin Gao and Fuquan Zhang and Jun Song},
  title = {{Delay Bounded Maintenance Scheme in Rechargeable Wireless Sensor Networks}},
  journal = {J. Commun.},
  year = {2013},
  doi = {10.12720/jcm.8.6.398-406},
}
Figure