Source-linked AI summary
Optimal Packet Scheduling in an Energy Harvesting Communication System
Jing Yang, Sennur Ulukus
TL;DR
The paper studies how to minimize completion time when data and harvested energy arrive under causality constraints. It derives globally optimal off-line scheduling policies for packets initially available and packets arriving during transmission, assuming arrival times and amounts are known. The scope is limited to these deterministic, forecast-known scenarios, while the corresponding on-line algorithm is left for future work.
Problem
The problem is to minimize the time until all packets are delivered while respecting causality constraints on data and harvested-energy arrivals.
Method
The paper derives optimal transmission policies and a progressive off-line algorithm that uses a lower bound on completion duration to allocate rates and powers.
Results
The paper proves that its algorithm produces an optimal off-line transmission policy in each of the two packet-arrival scenarios.
Takeaways & Limitations
Known data and energy arrival schedules permit globally optimal completion-time scheduling for both initially ready packets and packets arriving during transmission.
Abstract
from arXiv · showhide
We consider the optimal packet scheduling problem in a single-user energy harvesting wireless communication system. In this system, both the data packets and the harvested energy are modeled to arrive at the source node randomly. Our goal is to adaptively change the transmission rate according to the traffic load and available energy, such that the time by which all packets are delivered is minimized. Under a deterministic system setting, we assume that the energy harvesting times and harvested energy amounts are known before the transmission starts. For the data traffic arrivals, we consider two different scenarios. In the first scenario, we assume that all bits have arrived and are ready at the transmitter before the transmission starts. In the second scenario, we consider the case where packets arrive during the transmissions, with known arrival times and sizes. We develop optimal off-line scheduling policies which minimize the time by which all packets are delivered to the destination, under causality constraints on both data and energy arrivals.
I. INTRODUCTION
The paper formulates completion-time minimization for a single-user energy-harvesting link with causally arriving data and energy, using known arrival schedules to derive optimal off-line policies. It addresses both packets ready before transmission and packets arriving during transmission, while noting the corresponding stochastic on-line problem remains intractable.
- System model: The system contains data and energy queues, with transmission rate and power controlled according to available data and harvested energy.The model concerns a single communication node and energy-harvesting wireless channel.
- Assumptions and scope: The paper assumes that data and energy arrival times and amounts are known exactly, enabling an optimal off-line algorithm.This deterministic setting is adopted because the fully stochastic problem and corresponding real-time on-line algorithm are described as intractable.
- Problem formulation: The objective is to minimize T, the time by which all data packets reach the destination, subject to data and energy causality.Packets cannot be delivered before arrival, and harvested energy cannot be used before it arrives.
- Scenarios: Two traffic scenarios are considered: all packets are ready before transmission, or packets arrive during transmission with known times and sizes.Both scenarios retain known energy-harvesting times and amounts.
- Motivation: Completion-time minimization requires balancing faster transmission from greater energy use against waiting for future energy arrivals.The paper therefore focuses on sophisticated utilization of harvested energy rather than a fixed energy budget alone.
- Contribution: The proposed algorithm first obtains a lower bound on the final transmission duration, then progressively determines rate and power allocations and proves the resulting policy optimal.Allocation proceeds until all transmission rates and powers are determined.
II. SCENARIO I: PACKETS READY BEFORE TRANSMISSION STARTS
Scenario I assumes all B0 bits are available at t = 0 and seeks the minimum completion time under causal energy arrivals. The optimal offline policy has nondecreasing power, constant rate between harvests, and a tight energy-feasible structure characterized algorithmically and proved optimal.
- System model and objective: All B0 bits are available at the transmitter at t = 0, while energy arrives at known times with harvested amounts E1, E2, ..., EK.The system minimizes transmission completion time T while respecting energy causality.
- Structural properties: Transmit power is nondecreasing across transmission intervals: p1 ≤ p2 ≤ ... ≤ pN.This monotonicity follows from concavity of g(p), since rearranging power can preserve feasibility while increasing transmitted bits earlier.
- Structural properties: The transmission power and rate remain constant between consecutive energy harvests and can change only when new energy arrives.Thus, each interval between harvests corresponds to a constant-power transmission segment.
- Structural properties: Whenever the transmission rate changes, cumulative energy consumed equals cumulative energy harvested at that instant.In the energy-curve representation, slope changes occur where the consumption curve touches the harvesting curve.
- Optimal-policy characterization: For a fixed completion time T, the optimal energy-consumption curve is the tightest string below the harvesting curve connecting the origin to harvested energy by T.Its linear-segment slopes represent transmit powers; monotonicity selects the smallest feasible slope successively.
- Algorithm and optimality: The allocation procedure progressively determines transmission rates and powers, and Theorem 2 states that it gives the optimal transmission policy.The algorithm uses lower and upper bounds on completion time and continues until all transmission rates and powers are determined.
III. SCENARIO II: PACKETS ARRIVE DURING TRANSMISSIONS
For packets arriving during transmission, the optimal off-line policy minimizes completion time while respecting both energy and data causality. Its structure is characterized by nondecreasing rates, constant rates between event epochs, and tight causality constraints when rates change.
- System model: The scenario models initial bits and energy, followed by known packet and energy arrivals during transmission.Arrival epochs are ordered jointly as event times for the scheduling analysis.
- Objective: The objective is to minimize T, the time by which the last bit is delivered.Feasibility must account for both average data arrival rate and average sustainable power.
- Optimal structure: Optimal transmission rates increase monotonically over time.Because the power-rate function is monotone, the corresponding transmit powers also increase monotonically.
- Optimal structure: Power or rate remains constant between event epochs and changes only potentially when energy or a new packet arrives.Equalizing rates within an event-free interval saves energy that can shorten the final transmission duration.
- Optimal structure: When the rate changes at an energy epoch, cumulative consumed and harvested energy are equal; at a packet epoch, cumulative departures and arrivals are equal.If both events coincide, at least one causality constraint is tight.
- Algorithm: Theorem 3 gives an if-and-only-if characterization: each next rate is the smallest feasible rate from the corresponding event epoch.The resulting policy is unique for a fixed completion time, and the paper's iterative algorithm is optimal.
IV. SIMULATION RESULTS
Simulations illustrate the proposed optimal scheduling policies under energy harvesting and packet-arrival profiles. The examples show that power changes at relevant energy or data events and that unused late energy can occur.
- Initially available packets: For an initially available 5.44 Mbits, energy arrivals at t = [0, 2, 5, 6, 8, 9, 11]s produce the illustrated optimal policy.The channel example uses bandwidth 1MHz, noise spectral density 10^-19W/Hz, and a 1km link with about 110dB path loss.
- Initially available packets: The active transmission completes at T = 9.5s, before the last energy harvest at t = 11s, which is not used.The corresponding example is shown with powers p = [3, 5, 10, 20]mW and durations l = [5, 3, 1, 0.5]s.
V. CONCLUSIONS
The paper studies completion-time minimization in energy harvesting communication under two packet-arrival scenarios. It derives structural properties and globally optimal off-line scheduling policies for both scenarios.
- Problem: The paper minimizes transmission completion time in an energy harvesting communication system.Completion time is the time by which all packets are delivered.
- Scenarios: It considers packets available before transmission and packets arriving during transmission.Both scenarios use known arrival information under the deterministic setting described in the paper.
- Approach: The authors first analyze structural properties of the optimal transmission policy.These properties support the scheduling construction in each scenario.
- Conclusion: They then develop a globally optimal off-line scheduling policy for each scenario.The conclusion states that the scheduling policies are obtained separately for the two cases.
A. The Proof of Theorem 1
The proof of Theorem 1 establishes that the stated transmission-policy structure is both necessary and sufficient for optimality. It uses energy feasibility, concavity of the power-rate function, and contradiction arguments.
- Proof strategy: The proof separately establishes necessity and sufficiency of the policy structure.The sufficiency argument assumes a competing policy with a smaller completion time and derives a contradiction.
- Conclusion: The theorem concludes that a policy is optimal if and only if it has the stated structure.This completes the proof by combining the necessity and sufficiency arguments.
- Sufficiency: If the policy's next power is not the smallest feasible average power, the proof identifies a tighter energy or data constraint.The argument begins from the preceding interval, where cumulative energy consumption equals harvested energy.
- Necessity: The proof examines two relative-order cases for consecutive energy epochs, illustrated in Fig. 11(a) and Fig. 11(b).In each case, feasibility forces a duration whose power conflicts with the required optimal structure.
- Sufficiency: Concavity of the power-rate function implies that the proposed policy can depart more bits over the relevant interval than a higher-power alternative.Thus, a competing policy cannot deliver all B0 bits in a shorter completion time.
B. The Proof of Theorem 2
The proof establishes that the allocation procedure satisfies the structural properties required for optimality. It then concludes that the procedure yields the unique optimal policy.
- If T ≤ s̃i1, no future harvested energy is used; if T > s̃i1, later harvested energy must be used for transmission.
- The contradiction argument confirms that the structural condition remains valid when additional harvested energy is needed.
- The allocation procedure first verifies that p1 satisfies the structural requirement in (40).
- The same argument extends the required properties from p1 to p2, p3, and subsequent transmission powers.
- Based on Lemma 1, the allocation procedure gives the unique optimal policy.
- Figure 12 illustrates the two cases considered in the proof of Theorem 2.
C. The Proof of Theorem 3
The proof shows that the first transmission rate must be the smallest feasible rate from time zero, determined by either energy or data constraints. It then extends this structure to later rates and establishes optimality by contradiction.
- The first rate r1 must satisfy the structural condition required for the optimal transmission policy.
- If r1 violates the condition, an alternative arrival point exposes infeasibility under the energy or data constraint.
- The binding constraint can be either the energy constraint or the data constraint.
- Therefore, r1 is the smallest feasible rate starting from t = 0, and the same property holds for r2, r3, and subsequent rates.
- Any policy with a shorter completion time would be infeasible according to Lemmas 4 and 6, proving optimality.
D. The Proof of Theorem 4
The proof shows that a constant initial rate can remain feasible under both energy and data causality constraints. It concludes that the resulting rate structure achieves the shortest transmission duration and is unique.
- A constant power p1 = g^-1(r1) is used to evaluate the first transmission rate and its feasibility.
- Maintaining rate r1 until the last bit departs is feasible from both the energy and data arrival perspectives.
- If T exceeds the relevant arrival point, additional harvested energy must be used to transmit the remaining data.
- The proof extends the required structure from r1 to r2, r3, and subsequent rates.
- The procedure yields the unique optimal transmission policy.