Source-linked AI summary
Optimal Packet Scheduling on an Energy Harvesting Broadcast Link
Mehmet Akif Antepli, Elif Uysal-Biyikoglu, Hakan Erkal
TL;DR
The paper addresses minimizing completion time for transmitting specified bits per user over an energy-harvesting broadcast link with known harvest times. It characterizes the optimal schedule and adapts FlowRight to solve the offline problem. The resulting schedule defers harvested energy, uses non-decreasing power, finishes both users simultaneously, and is solved efficiently by the modified algorithm.
Problem
The paper studies how to minimize transmission completion time for specified bits per user on an energy-harvesting broadcast link with known energy-harvesting instants.
Method
The paper exploits structural properties of the broadcast-channel rate region and adapts the iterative FlowRight algorithm for the multiuser scheduling problem.
Results
The optimal schedule defers some harvested energy, uses non-decreasing power, and completes transmission to both users at the same time.
Takeaways & Limitations
The offline broadcast scheduling problem can be solved efficiently with a modification of FlowRight.
Abstract
from arXiv · showhide
The minimization of transmission completion time for a given number of bits per user in an energy harvesting communication system, where energy harvesting instants are known in an offline manner is considered. An achievable rate region with structural properties satisfied by the 2-user AWGN Broadcast Channel capacity region is assumed. It is shown that even though all data are available at the beginning, a non-negative amount of energy from each energy harvest is deferred for later use such that the transmit power starts at its lowest value and rises as time progresses. The optimal scheduler ends the transmission to both users at the same time. Exploiting the special structure in the problem, the iterative offline algorithm, FlowRight, from earlier literature, is adapted and proved to solve this problem. The solution has polynomial complexity in the number of harvests used, and is observed to converge quickly on numerical examples.
I. INTRODUCTION
The paper studies offline transmission-time minimization for multiple users on an energy-harvesting broadcast link. It establishes structural properties of the optimal schedule and adapts FlowRight to find it.
- Problem setting: The problem minimizes the time needed to transmit given bits to all users when energy harvests and packet arrivals are known in advance.The considered instance has all required bits available at transmission start and assumes sufficient harvested energy for feasibility.
- Motivation: Because transmitting faster is less energy-efficient, the scheduler must balance slowing transmission with minimizing total completion time.This trade-off motivates completion-time optimization under energy-harvesting constraints.
- Optimal-schedule structure: Even with all packets initially available, the optimal schedule defers some harvested energy and uses non-decreasing transmission power over time.Thus, transmission begins at its lowest power and rises as the schedule progresses.
- Broadcast-specific structure: In the broadcast setting, rates and power must be selected jointly because one transmission power can correspond to a continuum of boundary rate pairs.This differs from point-to-point scheduling, where power determines rate through the average-power rate function.
- Optimal-schedule structure: The optimal schedule continuously serves all users, uses rates proportional to their bit amounts, and finishes transmission to every user simultaneously.This observation enables the use of mathematical similarities with an earlier scheduling problem.
- Solution approach: The adapted FlowRight algorithm is proved convergent and optimal, with polynomial complexity in the number of energy harvests used.The paper also discusses implementation and numerical examples in later sections.
II. BROADCAST CHANNEL
The paper characterizes the two-user AWGN broadcast channel through its capacity region and associated minimum-power rate functions. These functions provide the structural basis for the scheduling formulation.
- Channel model: The two-user AWGN broadcast channel has one sender, two receivers, fixed channel gains, and Gaussian noise, with rates constrained by its capacity region.The stronger user is identified by s1 > s2 > 0.
- Minimum-power representation: For any rate pair, a unique minimum average power P = g(r1, r2) places the pair on the capacity-region boundary.A larger average-power constraint produces a capacity region that dominates the region for a smaller constraint.
- Rate-function construction: The paper derives h1 and h2 from the broadcast-channel inequalities after expressing the boundary rates as functions of power and the other user’s rate.The resulting function g is twice continuously differentiable and strictly convex in r1 and r2.
- Rate-region properties: The rate functions h1 and h2 are nonnegative, increase with power, decrease with the other user’s rate, and are concave in power and rate.These properties are stated for the AWGN broadcast-channel rate region and used throughout the paper.
- Rate-region properties: Proposition 1 establishes that the derived functions satisfy the required structural properties of the rate region.The proposition’s proof is referenced in Appendix A.
III. PROBLEM DEFINITION
The paper formulates an offline scheduling problem for transmitting finite bit demands over an energy-harvesting broadcast link with known future energy arrivals. It characterizes feasible schedules through epochs, rate pairs, energy causality, and structural lemmas that reduce the optimization problem.
- Energy arrives at known instants, defining epochs, while the sender can change power and rate pairs over time subject to energy causality.
- The formulation assumes an achievable two-user broadcast rate region with the structural properties used by the scheduling lemmas, and the exposition focuses on two receivers while allowing generalization.
- A schedule is the sequence of rate pairs and their durations, and the offline problem seeks the schedule attaining the infimum completion time T opt.
- The sender must deliver finite B1 and B2 bit demands to two receivers while minimizing overall transmission completion time with future harvest information available.
- Equalizing power across feasible slots preserves energy and duration while transmitting at least as many bits, motivating deferred energy use and nondecreasing power.
- Within an optimal schedule, power and rate pairs remain constant during each used epoch, reducing the problem to epoch-level decisions.
IV. OPTIMAL OFFLINE SCHEDULING WITH THE FLOWRIGHT ALGORITHM
FlowRight starts from a feasible schedule and repeatedly optimizes adjacent epoch pairs, reducing completion time until it returns an optimal schedule. The algorithm uses initialization, local rate and power adjustments, and a termination rule based on successive iterations.
- FlowRight algorithm: FlowRight starts from a feasible initial schedule and iteratively applies local optimizations to improve the schedule by decreasing completion time.Each iteration processes adjacent epoch pairs sequentially.
- Initialization: Initialization assigns each epoch energy equal to the energy harvested at the beginning of that epoch and selects initial rate pairs on the achievable-region boundary.The initial rate ratio is set to B1/B2 while the consumed energy matches the available energy.
- Local optimization: Local optimization combines two consecutive epochs when feasible, equalizing powers and rates while respecting energy causality, or allocates the maximum feasible energy when equalization is impossible.The procedure updates rates, bits, and energy across the two epochs and uses bisection at an energy-causality boundary.
- Termination: Completion time strictly decreases after every nonterminal iteration, while the number of epochs used is non-increasing from iteration to iteration.If completion time does not change, FlowRight has stopped at the previous iteration.
- Optimality: The schedule returned by FlowRight is optimal, and its power allocation and rate pairs coincide with the optimal schedule when the algorithm stops.The proof establishes equality between the FlowRight and optimal schedules at termination.
V. ALGORITHM COMPLEXITY
The complexity analysis separates the cost of local optimization from the number of epoch-pair updates. Simulations indicate convergence after roughly quadratic iterations, yielding polynomial overall complexity in the number of optimized epochs.
- Per-iteration cost: The core computational step is local optimization, whose per-iteration cost scales as Citer ∝ Clocal × nopt.Here, nopt denotes the number of local optimizations performed in an iteration.
- Numerical subroutines: Bisection is used iteratively to solve the nonlinear equations in the local optimization procedures, with iteration counts depending on tolerance levels.The stated bounds include terms proportional to log2(Tupper/ϵ1) and log2(rup_1i/ϵ2).
- Numerical subroutines: In numerical computations, local convergence time was typically on the order of milliseconds.
- Convergence: Simulations observed convergence after a number of iterations on the order of (nopt)^2 for randomized energy, epoch-duration, and bit settings.The observation is based on extensive simulations.
- Overall complexity: The resulting worst-case computation time is Cfr ∝ Clocal × (nopt)^3, which is polynomial in nopt.The cubic scaling combines the local optimization cost with the observed quadratic iteration count.
VI. A NUMERICAL EXAMPLE
A two-user AWGN broadcast example evaluates FlowRight for transmitting 800Mbits to the stronger user and 100Mbits to the weaker user under specified energy arrivals. The algorithm reduces the completion time and produces constant, non-decreasing epoch powers, while leaving the last two harvests unused.
- Setup: 800Mbits and 100Mbits are transmitted to the stronger and weaker users, respectively, in a two-user AWGN broadcast channel.The example uses 100KHz bandwidth, noise spectral density N0 = 10^-13 Watts/Hz, and path losses of 70dB and 75dB.
- Execution cost: The algorithm stops after 59 iterations in 1.29 seconds using the stated stopping criterion and computer configuration.
- Schedule structure: The last two energy harvests are unused, while transmit powers remain constant during epochs and non-decreasing over time.
- FlowRight execution: FlowRight reduces transmission completion time from T up=20.08 hours after initialization to Tmin=19.20 hours in the final schedule.The final schedule is computed for the stated energy harvest instants and amounts.
- Final schedule: The final transmit powers are [1.11, 2.78, 5.56, 15.28, 23.30] mW over durations [5, 2, 2, 4, 6.20] hours.The schedule uses constant power within each listed duration.
VII. CONCLUSIONS AND FUTURE WORK
The paper formulates and solves offline transmission completion-time minimization on an energy-harvesting broadcast link, identifying structural properties of the optimal schedule and adapting FlowRight to compute it efficiently.
- The offline transmission completion-time minimization problem is formulated and solved for an energy-harvesting broadcast link.
- Energy harvested during transmission may be deferred rather than depleted at the end of each epoch, while the schedule balances urgency with energy conservation.
- Both users finish transmission simultaneously at time T under the optimal schedule.
- Transmit powers are non-decreasing over time, making transmission rates highest toward the end of the schedule.
- A modified FlowRight algorithm efficiently solves the problem by repeatedly improving an upper bound on T until convergence to the optimal value.
- Future work: Future work includes data arrivals during transmission, multiple-access systems, and time-varying channel gains, especially in online formulations.
A. Proof of Proposition 1
The proof establishes that h1(P, r) and h2(P, r) are nonnegative, monotone, and concave in power and rate when the other parameter is fixed.
- h1(P, r) and h2(P, r) are nonnegative.
- Their first-order partial derivatives have fixed signs in their respective domains, establishing monotonicity.
- Both functions are concave in power when rate is held constant.
- Both functions are concave in rate when power is held constant.
B. Proof of Lemma 1
The proof shows that f1 is concave in β by differentiating its expression and applying the structural properties of the achievable rate region.
- f1(β) is formed from weighted rate terms evaluated at power-shifted operating points and corresponding subtracted reference terms.
- The second derivative of f1 with respect to β combines power-derivative terms and rate-derivative terms.
- The rate-derivative contribution in the second derivative is zero under the displayed structure.
- The rate-region properties imply that f1 is concave in β.
C. Proof of Lemma 6
The proof establishes concavity of f2 in β by analyzing its second derivative and invoking the stated properties of the achievable rate region.
- f2(β) varies the rate arguments of h2 while weighting the resulting terms by β and 1−β.
- The second derivative of f2 with respect to β contains rate-derivative terms involving the rate difference Δr.
- The rate-region properties imply that f2 is concave in β.