Energy-Efficient Broadcast Scheduling for Speed-Controlled Transmission Channels

摘要

We consider the problem of computing broadcast schedules for a speed-controlled channel minimizing overall energy consumption. Each request defines a strict deadline and we assume that sending at some speed s for t time units consumes energy t · s~α. For the case that the server holds a single message and the speed of a broadcast needs to be fixed when it is started, we present an O(2~α)-competitive deterministic online algorithm and prove that this is asymptotically best possible even allowing randomization. For the multi-message case we prove that an extension of our algorithm is (4c- l)~α-competitive if the lengths of requests vary by at most a factor of c. Allowing the speed of running broadcasts to be changed, we give lower bounds that are still exponential in α.