single one and transfer it to the parent node, in the direction of s. The energy incurred by a network node is proportional to the number of packets sent.

Becchetti et al. 13 assume that data items arrive over time. Each item i is specified by the node vi where the item arises, an arrival time ri and a deadline di by which the data must reach the sink. The goal is to find a feasible transmission schedule minimizing the maximum energy required at any node. Becchetti et al. show that the offline problem is NP-hard and present a 2-approximation algorithm. They also develop distributed online algorithms for synchronous as well as asynchronous communication models. Korteweg et al. 29 study a problem variant where the data items do not have deadlines but should reach the sink with low latency. They present algorithms that simultaneously approximate energy consumption and latency, considering again various communication models.

conclusion

In this survey, we have reviewed algo-
rithmic solutions to save energy.
Another survey on algorithmic prob-
lems in power management was
written by Irani and Pruhs. 27 Over
the past months a large number of
papers have been published, and we
expect that energy conservation from
an algorithmic point of view will con-
tinue to be an active research topic.
There are many directions for future
research. With respect to power-down
mechanisms, for instance, it would
be interesting to design strategies
that take into account the latency that
arises when a system is transitioned
from a sleep state to the active state.
Additionally, we need a better under-
standing of speed scaling techniques
in multiprocessor environments as
multicore architectures become more
and more common not only in serv-
ers but also in desktops and laptops.
Moreover, optimization problems in
networks deserve further algorithmic
investigation. At this point it would
be interesting to study energy-effi-
cient point-to-point communication,
complementing the existing work on
broadcast and data-aggregation proto-
cols. Last but not least, the algorithms
presented so far have to be analyzed
in terms of their implementation and
execution cost: how much extra energy
is incurred in executing the algorithms
in realistic environments.

References

1. http://www.microsoft.com/whdc/system/pnppwr/ powermgmt/ default.mspx

2. albers, s., fujiwara, h. energy-efficient algorithms for flow time minimization. ACM Trans. Algorithms 3 (2007).

3. albers, s., müller, f., schmelzer, s. speed scaling on parallel processors. in Proceedings of the 19th ACM Symposium on Parallelism in Algorithms and Architectures (2007), 289–298.

4. ambühl, c. an optimal bound for the mst algorithm to compute energy efficient broadcast trees in wireless networks. in Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (2005), springer lncs 3580, 1139–1150.

5. augustine, J., irani, s., swamy, c. optimal power-down strategies. SIAM J. Comput. 37 (2008), 1499–1516.

6. bansal, n., bunde, d.P., chan, h.-l., Pruhs k. average rate speed scaling. in Proceedings of the 8th Latin American Symposium on Theoretical Informatics (2008), springer lncs 4957, 240–251.

7. bansal, n., chan, h.-l., lam, t.-W., lee, k.-l. scheduling for speed bounded processors. in Proceedings of the 35th International Colloquium on Automata, Languages and Programming (2008), springer lncs 5125, 409–420.

8. bansal, n., chan, h.-l., Pruhs, k. speed scaling with an arbitrary power function. in Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithm (2009).

9. bansal, n., kimbrel, t., Pruhs, k. speed scaling to manage energy and temperature. J. ACM 54 (2007).

10. bansal, n., Pruhs, k., stein, c. speed scaling for weighted flow time. in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (2007), 805–813.

11. baptiste, P., chrobak m., dürr c. Polynomial time algorithms for minimum energy scheduling. in Proceedings of the 15th Annual European Symposium on Algorithms (2007), springer lncs 4698, 136–150.

12. barroso, l.a. the price of performance. ACM Queue 3 (2005).

13. becchetti, l., korteweg, P., marchetti-spaccamela, a., skutella, m., stougie, l., vitaletti, a. latency constrained aggregation in sensor networks. in Proceedings of the 14th Annual European Symposium on Algorithms (2006), springer lncs 4168, 88–99.

14. benini, l., bogliolo, a., de micheli, g. a survey of design techniques for system-level dynamic power management. IEEE Trans. VLSI Syst. 8 (2000), 299–316.

15. bunde, d.P. Power-aware scheduling for makespan and flow. in Proceedings of the 18th Annual ACM Symposiun on Parallel Algorithms and Architectures (2006), 190–196.

16. caragiannis, i., flammini, m., moscardelli, l. an exponential improvement on the mst heuristic for minimum energy broadcasting in ad hoc wireless networks. in Proceedings of the 34th International Colloquium on Automata, Languages and Programming (2007), springer lncs 4596, 447–458.

17. chan, h.-l., chan, W.-t., lam, t.-W., lee, k.-l., mak, k.-s., Wong P. W.h. energy efficient online deadline scheduling. in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (2007), 795–804.

18. chan, h.-l., edmonds, J., lam, t.-W, lee, l.-k., marchetti-spaccamela, a., Pruhs, k. nonclairvoyant speed scaling for flow and energy. in Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (2009), 255–264.

19. clementi, a.e.f., crescenzi, P., Penna, P., rossi, g., vocca, P. on the complexity of computing minimum energy consumption broadcast subgraphs. in Proceedings of the 18th International Symposium on Theoretical Aspects of Computer Science (2001), springer 2010, 121–131.

20. cormen, t.h., leiserson, c.e., rivest, r.l., stein, c. Introduction to Algorithms, mit Press and mcgraw-hill, 2001.

21. demaine, e.d., ghodsi, m., hajiaghayi, m.t., sayedi-roshkhar, a.s., Zadimoghaddam, m. scheduling to minimize gaps and power consumption. in Proceedings of the 19th Annual ACM Symposium on Parallel Algorithms and Architectures (2007), 46–54.

22. flammini, m., klasing, r., navarra, a., Perennes, s. improved approximation results for the minimum energy broadcasting problem. Algorithmica 49 (2007), 318–336.

23. irani, s., shukla, s.k., gupta, r. algorithms for power savings. ACM Trans. Algorithms 3 (2007).

24. irani, s., shukla, s.k., gupta, r.k. online strategies for dynamic power management in systems with multiple power-saving states. ACM Trans. Embedded Comput. Syst. 2 (2003), 325–346.

25. irani, s., singh, g., shukla, s.k., gupta, r.k. an overview of the competitive and adversarial approaches to designing dynamic power management strategies. IEEE Trans. VLSI Syst. 13 (2005), 1349–1361.

26. irani, s., karlin, a.r. online computation. in Approximation Algorithms for NP-Hard Problems. hochbaum d. ed. P Ws Publishing company, 1997, 521–564.

27. irani, s., Pruhs, k. algorithmic problems in power management. SIGAC T News 36 (2005), 63–76.

28. karlin, a.r., manasse, m.s., mcgeoch, l.a, owicki, s.s. competitive randomized algorithms for nonuniform problems. Algorithmica 11 (1994), 542–571.

29. korteweg, P., marchetti-spaccamela, a., stougie, l., vitaletti, a. data aggregation in sensor networks: balancing communication and delay costs. in Proceedings of the 14th International Colloquium on Structural Information and Communication Complexity (2007), springer lncs 4474, 139–150.

30. lam, t.-W., lee, l.-k., to, i.k.-k., Wong, P. W.h. energy efficient deadline scheduling in two processor systems. in Proceedings of the 18th International Symposium on Algorithms and Computation (2007), springer lncs 4835, 476–487.

31. lam, t.-W., lee, l.-k., to, i.k.-k., Wong, P. W.h. competitive non-migratory scheduling for flow time and energy. in Proceedings of the 20th Annual ACM Symposium on Parallel Algorithms and Architectures (2008), 256–264.

32. lam, t.-W., lee, l.-k., to, i.k.-k., Wong, P. W.h. speed scaling functions for flow time scheduling based on active job count. in Proceedings of the 16th Annual European Symposium on Algorithms (2008), springer lncs 5193, 647–659.

33. li, m., liu, b.J., yao, f.f. min-energy voltage allocation for tree-structured tasks. J. Comb. Optim. 11 (2006), 305–319.

34. li, m., yao, a.c., yao, f.f. discrete and continuous min-energy schedules for variable voltage processors. in Proceedings of the National Academy of Sciences USA 103 (2006), 3983–3987.

35. li, m., yao, f.f. an efficient algorithm for computing optimal discrete voltage schedules. SIAM J. Comput. 35 (2005), 658–671.

36. Pruhs, k., van stee, r., uthaisombut, P. speed scaling of tasks with precedence constraints. Theory Comput. Syst. 43 (2008), 67–80.

37. Pruhs, k., uthaisombut, P., Woeginger, g.J. getting the best response for your erg. ACM Trans. Algorithms 4 (2008).

38. sleator, d.d., tarjan, r.e. amortized efficiency of list update and paging rules. Comm. ACM 28 (1985), 202–208.

39. Wan, P.-J., calinescu, g., li, X.-y., frieder, o. minimum-energy broadcasting in static ad hoc wireless networks. Wireless Netw. 8 (2002), 607–617.

40. yao, f.f., demers, a.J., shenker, s. a scheduling model for reduced cPu energy. in Proceedings of the 36th IEEE Symposium on Foundations of Computer Science (1995), 374–382.

 

Susanne Albers is a professor in the department of computer science at humboldt university, berlin, germany.

Work supported by a gottfried Wilhelm leibniz award of the german research foundation.