Worst-case performance guarantees of scheduling algorithms maximizing weighted throughput in energy-harvesting networks

• We generalize the models studied in Lei et al. [8], Michelusi et al. [3], Michelusi et al. [9] by incorporating packet deadlines and removing any assumptions made on packets value distributions, packet arrival patterns, or harvesting energy arrival patterns.
• We present an exact offline algorithm.
• We provide a lower bound of competitive ratio for deterministic online algorithms. We also provide a family of optimal deterministic online algorithms.
• We provide a randomized algorithm. Our efforts show that randomization helps in maximizing weighted throughput in the online setting. Note that this randomized algorithm does not depend on the stochastic features of the input.
• We experimentally evaluate the performance of the proposed offline and online algorithms against some known work.

Energy harvesting has recently emerged as a technique to enable longer operating time of sensor networks. However, due to harvesting energy's not-completely predictable stochastic nature, some packets may still fail to be transmitted due to insufficient energy supply. Also, packets in sensor networks are usually associated with sensitive time-critical information. Based on these observations, we theoretically study algorithms scheduling weighted packets with deadlines in energy-harvesting networks. In our model, packets arrive in an online manner, each packet has a value representing its priority and a value representing its deadline. Harvesting energy is gathered over time and transmitting one packet takes a unit of energy. The objective is to maximize the total value of the packets sent, subject to energy and deadline constraints. In this paper, we design both offline and online algorithms maximizing weighted throughput. We analyze these algorithms’ performance guarantees against their worst-case scenarios and empirically compare them with the conventional and classic scheduling algorithms. The simulation results show that our online algorithms have far better performance than conventional ones.