Abstract
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 \(\mathcal{O}(2^{\alpha})\)-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–1)α-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 α.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bansal, N., Coppersmith, D., Sviridenko, M.: Improved Approximation Algorithms for Broadcast Scheduling. In: Proceedings of the Symposium on Discrete Algorithms (SODA) (2006)
Bansal, N., Kimbrel, T., Pruhs, K.: Dynamic Speed Scaling to Manage Energy and Temperature. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS) (2004)
Burkhart, M., von Rickenbach, P., Wattenhofer, R., Zollinger, A.: Does Topology Control Reduce Interference? In: Proceedings of the Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc) (2004)
Clementi, A., Crescenzi, P., Penna, P., Rossi, G., Vocca, P.: On the Complexity of Computing Minimum Energy Consumption Broadcast subgraphs. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol. 2010, Springer, Heidelberg (2001)
Edmonds, J., Pruhs, K.: Multicast Pull Scheduling: When Fairness is Fine. Algorithmica 36(3), 315–330 (2003)
Gao, G.-Y., Wang, S.-K.: A Multi-Agent System Architecture for Geographic Information Gathering. Journal of Zhejiang University SCIENCE 5(11), 1367–1373 (2004)
Gunia, C.: On Broadcast Scheduling with Limited Energy. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds.) CIAC 2006. LNCS, vol. 3998, Springer, Heidelberg (2006)
Kalyanasundaram, B., Pruhs, K., Velauthapillai, M.: Scheduling Broadcasts in Wireless Networks. In: Paterson, M. (ed.) ESA 2000. LNCS, vol. 1879, Springer, Heidelberg (2000)
Li, X.-Y., Song, W.-Z., Wang, W.: A Unified Energy-Efficient Topology for Unicast and Broadcast. In: Proceedings of the International Conference on Mobile Computing and Networking (MobiCom) (2005)
Moscibroda, T., Wattenhofer, R.: Minimizing Interference in Ad Hoc and Sensor Networks. In: Proceedings of the Joint Workshop on Foundations of Mobile Computing (2005)
Pruhs, K., Uthaisombut, P.: A Comparison of Multicast Pull Models. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, Springer, Heidelberg (2002)
Qiao, D., Choi, S., Shin, K.-G.: Goodput Analysis and Link Adaptation for IEEE 802.11a Wireless LANs. Transactions on Mobile Computing 1(4), 278–292 (2002)
Yao, F., Demers, A., Shenker, S.: A Scheduling Model for Reduced CPU Energy. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS) (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Briest, P., Gunia, C. (2006). Energy-Efficient Broadcast Scheduling for Speed-Controlled Transmission Channels. In: Asano, T. (eds) Algorithms and Computation. ISAAC 2006. Lecture Notes in Computer Science, vol 4288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11940128_67
Download citation
DOI: https://doi.org/10.1007/11940128_67
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49694-6
Online ISBN: 978-3-540-49696-0
eBook Packages: Computer ScienceComputer Science (R0)