Abstract
In this paper, we develop optimal energy scheduling algorithms for $N$-user fading multiple-access channels with energy harvesting to maximize the channel sum-rate, assuming that the side information of both the channel states and energy harvesting states for $K$ time slots is known a priori, and the battery capacity and the maximum energy consumption in each time slot are bounded. The problem is formulated as a convex optimization problem with $O(NK)$ constraints making it hard to solve using a general convex solver since the computational complexity of a generic convex solver is exponential in the number of constraints. This paper gives an efficient energy scheduling algorithm, called the iterative dynamic water-filling algorithm, that has a computational complexity of $O(NK^2)$ per iteration. For the single-user case, a dynamic water-filling method is shown to be optimal. Unlike the traditional water-filling algorithm, in dynamic water-filling, the water level is not constant but changes when the battery overflows or depletes. An iterative version of the dynamic water-filling algorithm is shown to be optimal for the case of multiple users. Even though in principle the optimality is achieved under large number of iterations, in practice convergence is reached in only a few iterations. Moreover, a single iteration of the dynamic water-filling algorithm achieves a sum-rate that is within $(N-1)K/2$ nats of the optimal sum-rate.
Introduction
In modern wireless networks, devices often rely on energy harvesting (e.g., solar or vibration) to prolong their lifetimes. However, managing this energy is complex due to three conflicting factors: energy causality (energy cannot be spent before it is harvested), finite battery capacity (overflow leads to wastage), and hardware power constraints. When multiple users share a fading Multiple-Access Channel (MAC), the goal is to maximize the total data rate (sum-rate). While this is a convex optimization problem, it involves $O(NK)$ constraints, making standard numerical solvers computationally prohibitive. This paper introduces an efficient Iterative Dynamic Water-filling algorithm that exploits the physical structure of battery and channel dynamics to match the performance of global solvers at a fraction of the cost.
System Model
The system considers $N$ users transmitting to a single receiver over $K$ time slots. Each user $i$ harvests energy $E_i^k$ and stores it in a battery with capacity $B_i^{max}$. The transmission power $p_i^k$ is limited by both the available battery energy and a maximum power constraint $P_i$. The channel is a fading Gaussian MAC where the sum-rate $R^k$ depends on the power allocations and channel gains $H_i^k$ of all users.
Methods
The problem is solved in two main stages:
1. Single-User Case: Dynamic Water-filling
For a single user, the authors propose Dynamic Water-filling. In classic water-filling, a constant "water level" (inverse of signal-to-noise ratio) is used to allocate power. Here, the water level is dynamic, changing only at critical points:
- Battery Depletion Points (BDPs): If the battery hits zero, the water level can increase for future slots.
- Battery Fully-charged Points (BFPs): If the battery is full, the water level can decrease to prevent energy wastage.
2. Multi-User Case: Iterative Dynamic Water-filling
To handle $N$ users, the paper employs an iterative approach. In each iteration, the algorithm optimizes the power schedule for one user at a time, treating the signals from all other users as static interference. This reduces the complex MAC problem into a sequence of single-user problems. A preliminary step involves calculating an optimal "energy wastage" schedule to simplify subsequent power allocation.
Key Insights and Results
The proposed algorithm was evaluated using numerical simulations with energy harvesting modeled as a truncated Gaussian distribution and channel fading as an exponential distribution (Rayleigh fading).
- Optimality and Efficiency: The algorithm achieves the exact same sum-rate as generic convex solvers but reduces complexity to $O(NK^2)$ per iteration.
- Fast Convergence: Convergence is typically reached in just a few iterations. A single iteration is proven to be within $(N-1)K/2$ nats of the absolute optimal sum-rate.
- Simultaneous Transmission: Unlike traditional systems where TDMA is often optimal, this work proves that with finite batteries, users should often transmit simultaneously to prevent energy wastage or exploit high-gain channel states.
- Heuristic Superiority: The algorithm significantly outperforms "Greedy" or "Balanced" energy spreading heuristics, especially when battery capacity is limited.
Conclusion and Future Work
The iterative dynamic water-filling algorithm provides a computationally efficient and optimal solution for sum-rate maximization in energy-harvesting MACs. While this work assumes "offline" optimization with perfect non-causal knowledge of future states, future research will focus on "online" scenarios where only causal information or statistical distributions are available.
Summary updated