Competitive ratio analysis of online algorithms to minimize packet transmission time in energy harvesting communication system

The design of online algorithms for minimizing packet transmission time is considered for single-user Gaussian channel and two-user Gaussian multiple access channel (GMAC) powered by natural renewable sources. 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 online algorithm adaptively changes the transmission rate according to the causal energy arrival information, so as to minimize the packet transmission time. For a minimization problem, the utility of an online algorithm is tested by finding its competitive ratio or competitiveness that is the maximum of the ratio of the gain of the online algorithm and the optimal offline algorithm over all input sequences. We derive a lower bound that shows that competitive ratio of any online algorithm is at least 1.38 for single-user Gaussian channel and 1.356 for GMAC. 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 is shown to be strictly two-competitive for both the single-user Gaussian channel and the GMAC.