text: This paper studies online transmission policies for an energy harvesting transmitter. Unlike the existing online policies which more or less require the knowledge on the future behavior of the energy and data arrival processes, we consider a practical but significantly more challenging scenario where the energy and data arrival processes are assumed to be totally unknown. Our design is formulated as a robust-optimal control problem which aims to optimize the worst-case performance. The transmission policy is designed only based on the current battery energy level and the data queue length directly monitored by the transmitter itself. Specifically, we apply an event-trigger approach in which the transmitter continuously monitors the battery energy and data queue length, and triggers an event when a significant change occurs in either of them. Once an event is triggered, the transmission policy is updated by the solution to the robust-optimal control problem. We consider both the transmission time and throughput as the performance metrics and formulated two optimization problems. The solutions are given in either a simple analytical form or an easy-to-implement algorithm.
  @cite_24: The design of online algorithms for maximizing the achievable rate in a wireless communication channel between a source and a destination over a fixed number of slots is considered. The source is assumed to be powered by a natural renewable source, and the most general case of arbitrarily varying energy arrivals is considered, where neither the future energy arrival instants or amount nor their distribution is known. The fading coefficients are also assumed to be arbitrarily varying over time, with only causal information available at the source. For a maximization problem, the utility of an online algorithm is tested by finding its competitive ratio or competitiveness that is defined to be the maximum of the ratio of the gain of the optimal offline algorithm and the gain of the online algorithm over all input sequences. We show that the lower bound on the optimal competitive ratio for maximizing the achievable rate is arbitrarily close to the number of slots. Conversely, we propose a simple strategy that invests available energy uniformly over all remaining slots until the next energy arrival, and show that its competitive ratio is equal to the number of slots, to conclude that it is an optimal online algorithm.
  @cite_15: A competitive analysis for the online and offline optimization problems for a slotted energy harvesting (EH) wireless communication system is studied. The objective is to design online strategies that minimize the competitive rate gap that is defined as the maximum gap between the optimal rates that can be achieved by the offline and online policies over all possible energy arrival profiles. It is shown that the competitive rate gap is upper-bounded by the logarithm of the number of slots, and a myopic online transmission policy is proposed that achieves a lower rate gap.
  @cite_17: Preface 1. Introduction to competitive analysis: the list accessing problem 2. Introduction to randomized algorithms: the list accessing problem 3. Paging: deterministic algorithms 4. Paging: randomized algorithms 5. Alternative models for paging: beyond pure competitive analysis 6. Game theoretic foundations 7. Request - answer games 8. Competitive analysis and zero-sum games 9. Metrical task systems 10. The k-server problem 11. Randomized k-server algorithms 12. Load-balancing 13. Call admission and circuit-routing 14. Search, trading and portfolio selection 15. Competitive analysis and decision making under uncertainty Appendices Bibliography Index.
  @cite_11: We consider the optimal online packet scheduling problem in a single-user energy harvesting wireless communication system, where energy is harvested from natural renewable sources, making future energy arrivals instants and amounts random in nature. The most general case of arbitrary energy arrivals is considered where neither the future energy arrival instants or amount, nor their distribution is known. The problem considered is to adaptively change the transmission rate according to the causal energy arrival information, such that the time by which all packets are delivered is minimized. We assume that all bits have arrived and are ready at the source before the transmission begins. For a minimization problem, the utility of an online algorithm is tested by finding its competitive ratio or competitiveness that is defined to be the maximum of the ratio of the gain of the online algorithm with the optimal offline algorithm over all input sequences. We derive a lower and upper bound on the competitive ratio of any online algorithm to minimize the total transmission time in an energy harvesting system. The upper bound is obtained using a lazy' transmission policy that chooses its transmission power to minimize the transmission time assuming that no further energy arrivals are going to occur in future. The lazy transmission policy is shown to be strictly two-competitive. We also derive an adversarial lower bound that shows that competitive ratio of any online algorithm is at least 1.325.
summary: Our paper is mostly related to the recent work in @cite_24 @cite_15 @cite_11 , which considered the similar assumptions that the future energy arrival is unknown. @cite_24 @cite_15 @cite_11 , the competitive analysis @cite_17 was employed to minimize the gap between online and offline performances. However, minimizing this gap cannot directly guarantee a certain system performance (e.g., optimal worst-case performance) of online algorithms. Additionally, these recent studies still considered time-slotted systems, and hence, the transmission protocol is updated in every time slot, regardless of the change in the amount of energy available.