On the Online Minimization of Completion Time in an Energy Harvesting System


SOURCE WiOpt 2016, Phoenix, May 9-13, 2016

Published Date:2016-5


This paper considers a single-transmitter energy
harvesting system and looks into the problem of completion
time minimization from the worst-case point of view. In offline
study, an optimal algorithm [1] is given to yield the minimum
completion time of transmission. However, for online algorithms,
the randomness of future energy arrivals adds to the difficulty
of scheduling, thus the offline minimum completion time cannot
always be reached. This leads to the question “What is the
deterministic performance bound of online algorithms compared
to the offline optimum”. By a game-theoretic method, this paper
shows that with an infinite-sized battery, there exist several
algorithms that guarantee a completion time no more than the
twice of its offline counterpart for all possible energy arrivals,
and more importantly that the ratio of two cannot be further
reduced. This property is of great significance especially when
reliability is valued in the system.

This entry was posted in Publications and tagged . Bookmark the permalink.

Leave a Reply