Low-complexity scheduling for energy-efficient transmission of packets with individual deadlines

This paper aims at energy-efficient transmission of packets with individual deadlines. In order to reduce the transmission energy of a packet, a lower data rate should be adopted, while the deadline restraint leads to a rate lower limit. It is derived theoretically that the energy-optimal transmission, i.e., the transmission consuming the minimal energy, follows three theorems: (1) the rate is invariable except for the deadlines of the packets; (2) the rate is non-increasing over the whole transmission time; (3) if the rate decreases at a deadline, only the terminated packets have been transmitted. Then, a scheduling algorithm based on backward unidirectional valve (BUV) is proposed, where the packets are divided into multiple groups and each group corresponds to a fixed rate. Specifically, the packets are handled one by one, and any packet is taken as a new group in the initial. If the transmission rate of the new group is not lower than that of its preceding neighboring group, the two groups are amalgamated into one, and this procedure is implemented constantly before the rate decreases in stairs. The BUV scheduling not only achieves the energy-optimal transmission, but also has a low computational complexity.