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.