Optimal Rate Schedules with Data Sharing in Energy Harvesting Communication Systems

Weiwei Wu, Huafan Li, Feng Shan, Yingchao Zhao2017 · DOI

TL;DR

This paper tackles the challenge of efficiently transmitting data from energy-harvesting wireless devices to a platform supporting multiple applications. The authors introduce a novel approach that leverages data sharing among these applications to minimize transmission completion time, even with dynamic energy availability and data requests. They develop both offline and online algorithms to achieve this, demonstrating significant improvements over methods that don't exploit data sharing.

What Problem Does This Paper Address?

Modern wireless communication systems are increasingly incorporating energy harvesting to power devices, but the harvested energy is often limited and unstable. This poses a significant challenge for devices needing to transmit data, especially when multiple applications or requesters on a central platform have varying data needs and arrival times. Traditional approaches often treat data requests in isolation, leading to redundant transmissions and inefficient energy use. This paper addresses the problem of optimizing data transmission from energy-harvesting devices to a platform with multiple applications, aiming to minimize the overall completion time while respecting energy constraints and leveraging the potential for data sharing among different requests. The core challenge is to balance energy harvesting dynamics, fluctuating data demands, and the efficiency gains offered by sharing data across applications.

Methods

The paper proposes a two-pronged approach: an offline algorithm for optimal scheduling and an online algorithm for dynamic scenarios.

Offline Algorithm: The offline problem is decomposed into two sub-problems:

  1. Min-Energy Problem (min-E): Minimize energy consumption for a given deadline, considering data requests and energy harvesting. This is solved by first analyzing properties of the optimal rate schedule (non-decreasing, step-function) and then using a "Bottleneck-Select" algorithm. This algorithm iteratively compares optimal rate schedules from two simplified models (one with only energy harvesting, one with only data sharing) to determine the bottleneck and fix parts of the optimal schedule.
  2. Min-Completion Time Problem (min-T): Minimize the overall transmission completion time. This problem is solved by using the min-E solver. The authors establish a relationship where the optimal min-E solution for a given deadline is equivalent to the optimal min-T solution if that deadline is the true minimum completion time. They then employ a binary search strategy (estimation and determination phases) using the min-E solver to find the optimal completion time and the corresponding rate schedule.

Online Algorithm: An event-driven online algorithm, "ONLINE-SELECT," is proposed for scenarios where future task arrivals and energy harvesting events are unknown. This algorithm maintains a constant rate based on currently available information until a new event occurs. It dynamically adjusts the transmission rate by considering the accumulated demand and available energy, aiming to minimize completion time by sharing data among active requests.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm design and simulation-based evaluation.

Key Insights and Ideas

  • Data Sharing as a Key Efficiency Lever: The paper strongly emphasizes that data sharing among multiple applications is crucial for enhancing energy utilization efficiency in energy-harvesting systems. This is a departure from many prior works that treated requests independently.
  • Decomposition for Complexity Management: Decomposing the complex min-E problem into two simpler, well-understood sub-problems (energy-only and data-sharing-only) is a powerful technique. This allows for the development of a structured and provably optimal solution.
  • Bottleneck-Select Algorithm: The core idea of comparing the "bottlenecks" (i.e., the rate-limiting factors) from the energy-harvesting-only and data-sharing-only scenarios to construct the overall optimal rate schedule is novel and effective.
  • Bridging Min-E and Min-T: The insight that the optimal min-E solution for a specific deadline can reveal information about the optimal min-T problem is key to their offline algorithm's design. This allows them to use a binary search on the completion time, leveraging the min-E solver.
  • Event-Driven Online Approach: The online algorithm's event-driven nature, reacting to new tasks and energy arrivals, makes it practical for real-world dynamic environments.

Key Results

  • Optimal Offline Solution: The proposed offline algorithm (BOTTLENECK-SELECT combined with binary search) is proven to find the optimal rate schedule that minimizes transmission completion time while satisfying energy and data constraints.
  • Efficient Online Algorithm: The ONLINE-SELECT algorithm demonstrates near-optimal performance in simulations, achieving completion times within 1.2 to 1.3 times of the optimal offline solution, depending on the scenario.
  • Significant Performance Gains from Data Sharing: Simulations show that exploiting data sharing leads to substantially shorter transmission completion times compared to methods that do not consider data sharing, even when comparing optimal offline solutions.
  • Robustness to Parameter Changes: The performance of the online algorithm remains strong and close to optimal across various changes in the number of tasks, average workload, number of harvestings, and average harvested energy.

Limitations and Future Work

  • Fading Channel: The paper acknowledges that the current work assumes a static channel. Future work will consider transmission in fading channels.
  • Battery Overflow: The current model does not explicitly handle battery overflow. This is identified as an area for future research.
  • Simplified Model: The paper uses a simplified data sharing model. More complex sharing scenarios could be explored.
  • Specific Rate-Power Function: While the framework is general, simulations use a specific AWGN channel rate-power function. Testing with other functions could be beneficial.
  • More Complex System Architectures: The current work focuses on a point-to-point system. Extending to multi-hop or more complex network topologies is a natural next step.

Summary updated

BibTeX
@misc{wu2017optimal,
  author = {Weiwei Wu and Huafan Li and Feng Shan and Yingchao Zhao},
  title = {{Optimal Rate Schedules with Data Sharing in Energy Harvesting Communication Systems}},
  year = {2017},
  doi = {10.3390/s17122958},
}
Figure