Power management and competitiveness Problem setting: In a general scenario, we are given a device that always resides in one of several states. In review articles addition to the active state there can be, for instance, standby, suspend, sleep, and full-off states. These states have individual power consumption rates. The energy incurred in transitioning the system from a higherpower to a lower-power state is usually negligible. However, a power-up operation consumes a significant amount of energy. Over time, the device experiences an alternating sequence of active and idle periods. During active periods, the system must reside in the active mode to perform the required tasks. During idle periods, the system may be moved to lower-power states. An algorithm has to decide when to perform the transitions and to which states to move. The goal is to minimize the total energy consumption. As the energy consumption during the active periods is fixed, assuming that prescribed tasks have to be performed, we concentrate on energy minimization in the idle intervals. In fact, we focus on any idle period and optimize the energy consumption in any such time window. This power management problem is an online problem, that is, at any time a device is not aware of future events. More specifically, in an idle period, the system has no information when the period ends. Is it worthwhile to move to a lower-power state and benefit from the reduced energy consumption, given that the system must finally be powered up again at a cost to the active mode? Performance analysis: Despite the handicap of not knowing the future, an online strategy should achieve a provably good performance. Here the algorithms community resorts to com petitive analysis, where an online algorithm ALG is compared to an optimal offline algorithm OPT. 38 OPT is an omniscient strategy that knows the entire future and can compute a state transition schedule of minimum total energy. Online algorithm ALG is called c-competitive if for every input, such as, for any idle period, the total energy consumption of ALG is at most c times that of OPT. Competitive analysis provides a strong worst-case performance guarantee. An online strategy must perform well on all inputs (idle periods) that might even be generated by an adversary. This adversarial scenario may seem pessimistic but it is consistent with classical algorithm analysis that evaluates strategies in terms of their worst-case resources, typically running time or memory requirements. In this section, we will mostly study algorithms using competitive analysis but will also consider performance on inputs that are generated according to probability distributions. In the following, we will first study systems that consist of two states only. Then we will address systems with multiple states. We stress that we consider the minimization of energy. We ignore the delay that arises when a system is transitioned from a lowerpower to a higher-power state. Consider a two-state system that may reside in an active state or in a sleep state. Let r be the power consumption rate, measured in energy units per time unit, in the active state. The power consumption rate in the sleep mode is assumed to be 0. The results we present in the following generalize to an arbitrary consumption rate in the sleep mode. Let b energy units, where b > 0, be required to transition the system from the sleep state to the active state. We assume that the energy of transitioning from the active to the sleep state is 0. If this is not the case, we can simply fold the corresponding energy into the cost b incurred in the next power-up operation. The system experiences an idle period whose length T is initially unknown. An optimal offline algorithm OPT, knowing T in advance, is simple to formulate. We compare the value of rT, which is the total energy consumed during the idle period when residing in the active mode, to the power-up cost of b. If rT < b, OPT remains in the active state throughout the idle period as transitioning between the active and sleep modes costs more. If rT ³ b, using the sleep mode is beneficial. In this case OPT transitions to the sleep state right at the beginning of the idle period and powers up to the active state at the end of the period. The following deterministic online algorithm mimics the behavior of OPT, which uses the sleep mode on idle periods of length at least b/r. energy has become a leading design constraint for computing devices. hardware engineers and system designers explore new directions to reduce energy consumption of their products. Consider a system with l states s 1 , …, s l . Let r i be the power consumption rate of s i . We number the states in order of decreasing rates, such as, r 1 > … > r l . Hence s 1 is the active state and s l represents the state with lowest energy consumption. Let b i be the energy required to transition the system from s i to the active state s 1 . As transitions from lower-power states are more expensive we have b 1 £ … £ b l . Moreover, obviously, b 1 = 0. We assume again that transitions from higher-power to lower-power states incur 0 cost because the corresponding energy is usually negligible. The goal is to construct a state transition schedule minimizing the total energy consumption in an idle period. Irani et al. 24 presented online and offline algorithms. They assume that the transition energies are additive, such as, transitioning from a lowerpower state s j to a higher-power state s i , where i < j, incurs a cost of b j − b i . An algorithm aLG-d: In an idle period first remain in the active state. After b/r time units, if the period has not ended yet, transition to the sleep state. It is easy to prove that ALG-D is 2-competitive. We only need to consider two cases. If rT < b, then ALG-D consumes rT units of energy during the idle interval and this is in fact equal to the consumption of OPT. If rT ³ b, then ALG-D first consumes r . b/r = b energy units to remain in the active state. An additional power-up cost of b is incurred at the end of the idle interval. Hence, ALG-D's total cost is 2b, while OPT incurs a cost of b for the power-up operation at the end of the idle period. It is also easy to verify that no deterministic online algorithm can achieve a competitive ratio smaller than 2. If an algorithm transitions to the sleep state after exactly t time units, then in an idle period of length t it incurs a cost of tr + b while OPT pays min{rt, b} only. We remark that power management in two-state systems corresponds to the famous ski-rental problem, a cornerstone problem in the theory of online algorithms, see, for example, Irani and Karlin. 26 Interestingly, it is possible to beat the competitiveness of 2 using randomization. A randomized algorithm transitions to the sleep state according to a probability density function p(t). The probability that the system powers down during the first t 0 time units of an idle period is ò 0 t 0 p(t)dt. Karlin et al. 28 determined the best probability distribution. The density function is the exponential function e rt/b , multiplied by the factor to ensure that p(t) integrated over the entire time horizon is 1, that is, the system is definitely powered down at some point. algorithm aLG-r: Transition to the sleep state according to the probability density function ALG-R achieves a considerably improved competitiveness, as compared to deterministic strategies. Results by Karlin et al. 28 imply that ALG-R attains a competitive ratio of , where e » 2.71 is the Eulerian number. More precisely, in any idle period the expected energy consumption of ALG-R is not more than times that of OPT. Again, is the best competitive ratio a randomized strategy can obtain. From a practical point of view, it is also instructive to study stochastic settings where the length of idle periods is governed by probability distributions. In practice, short periods might occur more frequently. Probability distributions can also model specific situations where either very short or very long idle periods are more likely to occur, compared to periods of medium length. Of course, such a probability distribution may not be known in advance but can be learned over time. In the following, we assume that the distribution is known. Let Q = (q(T) ) 0£T<∞ be a fixed probability distribution on the length T of idle periods. For any t ³ 0, consider the deterministic algorithm ALG t that always powers down after exactly t time units. If the idle period ends before ALG t powers down, such as, if T < t, then the algorithm remains in the active state for the duration of the idle interval and uses an energy of rT. If the idle period has not yet ended when ALG t powers down, such as, if T ³ t, then the algorithm incurs a fixed energy of rt + b because an energy of rt is consumed before the system in powered down and a cost b is incurred to transition back to the active mode. In order to determine the expected cost of ALG t , we have to integrate over all possibilities for the length T of the idle period using the probability distribution Q. The two terms in the expression below represent the two cases. Note that the probability that the idle period has not yet ended when ALG t powers down is (1) Karlin et al. 28 proposed the following strategy that, given Q, simply uses the best algorithm ALG t . algorithm aLG-P: Given a fixed Q, let A Q * be the deterministic algorithm ALG t that minimizes Equation 1. Karlin et al. proved that for any Q, the expected energy consumption of  Interestingly, for variable T the optimal cost has a simple graphical representation, see Figure 1 . If we consider all linear functions f i (t) = r i t + b i , representing the total energy consumption using state s i , then the optimum energy consumption is given by the lowerenvelope of the arrangement of lines. One can use this lower-envelope to guide an online algorithm to select which state to use at any time. Let S OPT (t) denote the state used by OPT in an idle period of total length t, such as, S OPT (t), that is, the solution to the equation Here we assume that states whose functions do not occur on the lower-envelope, at any time, are discarded. We remark that the algorithm is a generalization of ALG-D for twostate systems. Irani et al. 24 proved that Lower-Envelope is 2-competitive. This is the best competitiveness a deterministic algorithm can achieve in arbitrary state systems. Irani et al. 24 also studied the setting where the length of idle periods is generated by a probability distribution Q = (q(T) ) 0£T<∞ . They determine the time t i when an online strategy should move from state s i−1 to s i , 2 £ i £ l. To this end consider the deterministic online algorithm ALG t that transitions to the lower-power state after exactly t time units. We determine the expected cost of ALG t in an idle period whose length T is generated according to Q, assuming that only states s i−1 and s i are available. Initially ALG t resides in state s i−1 . If the idle period ends before ALG t transitions to the lower-power state, such as, if T < t, then the energy consumption is r i−1 T. If the idle period has not ended yet when ALG t transitions to the lower-power state, such as, if T ³ t, the algorithm incurs an energy r i−1 t while residing in s i−1 during the first t time units and an additional energy of r i (T − t) when in state s i during the remaining T − t time units. At the end of the idle period, a power-up cost of b i − b i−1 is paid to transition from s i back to s i−1 . Hence, in this case ALG t incurs a total energy of r i−1 t The expected cost of ALG t , assuming that only s i−1 and s i are available, is Let t i be the time t that minimizes the above expression. Irani et al. 24 proposed the following algorithm. Algorithm ALG-P(l): Change states at the transition times t 2 ,…,t l defined above. ALG-P(l) is a generalization of ALG-P for two-state systems. Irani et al. proved that for any fixed probability distribution Q, the expected energy consumption of ALG-P(l) is no more than times the expected optimum consumption. Furthermore, Irani et al. presented an approach for learning an initially unknown Q. They combined the approach with ALG-P(l) and performed experimental tests for an IBM mobile hard drive with four power states. It shows that the combined scheme achieves low energy consumptions close to the optimum and usually outperforms many single-value prediction algorithms. Augustine et al. 5 investigate generalized multistate systems in which the state transition energies may take arbitrary values. Let b ij ³ 0 be the energy required to transition from s i to s j , 1 £ i, j £ l. Augustine et al. demonstrate that LowerEnvelope can be generalized and achieves a competitiveness of 3 + 2Ö2  5.8. This ratio holds for any state system. Better bounds are possible for specific systems. Augustine et al. devise a strategy that, for a given system S, achieves a competitive ratio arbitrarily close to the best competitiveness c* possible for S. Finally, the authors consider stochastic settings and develop optimal state transition times. Many modern microprocessors can run at variable speed. Examples are the Intel SpeedStep and the AMD processor PowerNow. High speeds result in higher performance but also high energy consumption. Lower speeds save energy but performance degrades. The well-known cube-root rule for CMOS devices states that the speed s of a device is proportional to the cube-root of the power or, equivalently, the power is proportional to s 3 . The algorithms literature considers a generalization of this rule. If a processor runs at speed s, then the required power is s a , where a > 1 is a constant. Obviously, energy consumption is power integrated over time. The goal is to dynamically set the speed of a processor so as to minimize energy consumption, while still providing a desired quality of service. Dynamic speed scaling leads to many challenging scheduling problems. At any time a scheduler has to decide not only which job to execute but also which speed to use. Consequently, there has been considerable research interest in the design and analysis of efficient scheduling algorithms. This section reviews the most important results developed over the past years. We first address scheduling problems with hard job deadlines. Then we consider the minimization of response times and other objectives. In general, two scenarios are of interest. In the offline setting, all jobs to be processed are known in advance. In the online setting, jobs arrive over time, and an algorithm, at any time, has to make scheduling decisions without knowledge of any future jobs. Online strategies are evaluated again using competitive analysis. Online algorithm ALG is c-competitive if, for every input, the objective function value (typically the energy consumption) of ALG is within c times the value of an optimal solution. In a seminal paper, initiating the algorithmic study of speed scaling, Yao et al. 40 investigated a scheduling problem with strict job deadlines. At this point, this framework is by far the most extensively studied algorithmic speed scaling problem. Consider n jobs J 1 ,…, J n that have to be processed on a variable-speed processor. Each job J i is specified by a release time r i , a deadline d i , and a processing volume w i . The release time and the deadline mark the time interval in which the job must be executed. The processing volume is the amount of work that must be done to complete the job. Intuitively, the processing volume can be viewed as the number of CPU cycles necessary to finish the job. The processing time of a job depends on the speed. If J i is executed at constant speed s, it takes w i /s time units to complete the job. Preemption of jobs is allowed, that is, the processing of a job may be suspended and resumed later. The goal is to construct a feasible schedule minimizing the total energy consumption. The framework by Yao et al. assumes there is no upper bound on the maximum processor speed. Hence there always exists a feasible schedule satisfying all job deadlines. Furthermore, it is assumed that a continuous spectrum of speeds is available. We will discuss later how to relax these assumptions. Fundamental algorithms: Yao et al. 40 first study the offline setting and develop an algorithm for computing optimal solutions, minimizing total energy consumption. The strategy is known as YDS referring to the initials of the authors. The algorithm proceeds in a series of iterations. In each iteration, a time interval of maximum density is identified and a corresponding partial schedule is constructed. Loosely speaking, the density of an interval I is the minimum average speed necessary to complete all jobs that must be scheduled in I. A high density requires a high speed. Formally, the density D I of a time interval I = [t, t¢] is the total work to be completed in I divided by the length of I. More precisely, let S I be the set of jobs J i that must be processed in I because their release time and deadline are in I, such as, Algorithm YDS repeatedly determines the interval I of maximum density. In such an interval I, the algorithm schedules the jobs of S I at speed D I using the Earliest Deadline First (EDF) policy. This well-known policy always executes the job having the earliest deadline, among the available unfinished jobs. After this assignment, YDS removes set S I as well as time interval I from the problem instance. More specifically, for any unscheduled job J i whose deadline is in the interval I, the new deadline is set to the beginning of I because the time window I is not available anymore for the processing of J i . Formally, for any J i with d i Î I, the new deadline time is set to d i := t. Similarly, for any unscheduled J i whose release time is in I, the new release time is set to the end of I. Again, formally for any J i with r i Î I, the new release time is r i := t¢. Time interval I is discarded. This process repeats until there are no more unscheduled jobs. We give a summary of the algorithm in pseudocode. review articles the horizontal axis. In the first iteration YDS identifies I 1 = [3, 8] as interval of maximum density, along with set S I 1 = { J 2 , J 3 }. In I 1 , the red job J 2 is preempted at time 5 to give preference to the orange job J 3 having an earlier deadline. In the second iteration I 2 = [13, 20] is the maximum density interval. The dark green and light green jobs are scheduled; preemption is again used once. In the third iteration, the remaining job J 3 is scheduled in the available time slots. Obviously, when identifying intervals of maximum density, YDS only has to consider intervals whose boundaries are equal to the release times and deadlines of the jobs. A straightforward implementation of the algorithm has a running time of O(n 3 ). Li et al. 34 showed that the time can be reduced to O(n 2 log n). Further improvements are possible if the job execution intervals form a tree structure. If the given job instance is not feasible, the situation is more delicate. In this case it is impossible to complete all the jobs. The goal is to design algorithms that achieve good throughput, which is the total processing volume of jobs finished by their deadline, and at the same time optimize energy consumption. Papers 7, 17 present algorithms that even work online. At any time the strategies maintain a pool of jobs they intend to complete. Newly arriving jobs may be admitted to this pool. If the pool contains too large a processing volume, jobs are expelled such that the throughput is not diminished significantly. The algorithm by Bansal et al. 7 is 4-competitive in terms of throughput and constant competitive with respect to energy consumption. Temperature minimization: High processor speeds lead to high temperatures, which impair a processor's reliability and lifetime. Bansal et al. 9 consider the minimization of the maximum temperature that arises during processing. They assume that cooling follows Newton's Law, which states that the rate of cooling of a body is proportional to the difference in temperature between the body and the environment. Bansal et al. 9 show that algorithms YDS and BKP have favorable properties. For any jobs sequence, the maximum temperature is within a constant factor of the minimum possible optimal schedule for the currently available unfinished jobs. Bansal et al. 9 gave a comprehensive analysis of the above algorithm and proved that the competitive ratio is exactly a a . Hence, in terms of competitiveness, Optimal Available is better than Average Rate. Bansal et al. 9 also presented a new online algorithm, called BKP according to the initials of the authors, which can be viewed as approximating the optimal speeds of YDS in an online manner. Again, the algorithm considers interval densities. For times t, t 1 , and t 2 with t 1 < t £ t 2 , let w(t, t 1 , t 2 ) be the total processing volume of jobs that have arrived by time t, have a release time of at least t 1 and a deadline of at most t 2 . Then, intuitively, max t 1 , t 2 w(t, t 1 , t 2 )/(t 2 − t 1 ) is an estimate of the speed used by YDS, based on the knowledge of jobs that have arrived by time t. The new algorithm BKP approximates this speed by considering specific time windows [et − (e − 1)t¢, t¢], for t¢ > t, of length e(t¢ − t). The corresponding necessary speed is then multiplied by a factor of e. algorithm BKP: At any time t use a speed of e . s(t), where Available unfinished jobs are processed using EDF. Bansal et al. 9 proved that BKP achieves a competitive ratio of , which is better than the competitiveness of Optimal Available for large values of a. All the above online algorithms attain constant competitive ratios that depend on a and no other problem parameter. The dependence on a is exponential. For small values of a, which occur in practice, the competitive ratios are reasonably small. A result by Bansal et al. 9 implies that the exponential dependence on a is inherent to the problem. Any randomized online algorithm has a competitiveness of at least W( (4/3) a ). refinements-Bounded speed: The problem setting considered so far assumes a continuous, unbounded spectrum of speeds. However, in practice only a finite set of discrete speed levels s 1 < s 2 < ... < s d is available. The 23 investigate an extended problem setting where a variable-speed processor may be transitioned into a sleep state. In the sleep state, the energy consumption is 0 while in the active state even at speed 0 some non-negative amount of energy is consumed. Hence, Irani et al. 23 combine speed scaling with power-down mechanisms. In the standard setting without sleep state, algorithms tend to use low speed levels subject to release time and deadline constraints. In contrast, in the setting with sleep state it can be beneficial to speed up a job so as to generate idle times in which the processor can be transitioned to the sleep mode. Irani et al. 23 develop online and offline algorithms for this extended setting. Baptiste et al. 11 and Demaine et al. 21 also study scheduling problems where a processor may be set asleep, albeit in a setting without speed scaling. minimizing Response time A classical objective in scheduling is the minimization of response times. A user releasing a task to a system would like to receive feedback, say the result of a computation, as quickly as possible. User satisfaction often depends on how fast a device reacts. Unfortunately, response time minimization and energy minimization are contradicting objectives. To achieve fast response times, a system must usually use high processor speeds, which lead to high energy consumption. On the other hand, to save energy, low speeds should be used, which result in high response times. Hence, one has to find ways to integrate both objectives. Consider n jobs J 1 , …, J n that have to be scheduled on a variable-speed processor. Each job J i is specified by a release time r i and a processing volume w i . When a job arrives, its processing volume is known. Preemption of 37 study a problem setting where a fixed energy volume E is given and the goal is to minimize the total flow time of the jobs. The authors assume all jobs have the same processing volume. By scaling, we can assume all jobs have unitsize. Pruhs et al. 37 consider the offline scenario where all the jobs are known in advance and show that optimal schedules can be computed in polynomial time. However, in this framework with a limited energy volume it is difficult to construct good online algorithms. If future jobs are unknown, it is unclear how much energy to invest for the currently available tasks. energy plus flow times: Albers and Fujiwara 2 proposed another approach to integrate energy and flow time minimization. They consider a combined objective function that simply adds the two costs. Let E denote the energy consumption of a schedule. We wish to minimize . By multiplying either the energy or the flow time by a scalar, we can also consider a weighted combination of the two costs, expressing the relative value of the two terms in the total cost. Albers and Fujiwara concentrate on unit-size jobs and show that optimal offline schedules can be constructed in polynomial time using a dynamic programming approach. In fact the algorithm can also be used to minimize the total flow time of jobs given a fixed energy volume. Bansal et al. and Lam et al. 7, 32 propose algorithms for the setting that there is an upper bound on the maximum processor speed. All the above results assume that when a job arrives, its processing volume is known. Papers 18, 32 investigate the harder case that this information is not available. The results presented so far address single-processor architectures. However, energy consumption is also a major concern in multiprocessor environments. Currently, relatively few results are known. Albers et al. 3 investigate deadline-based scheduling on m identical parallel processors. The goal is to minimize the total energy on all the machines. The authors first settle the complexity of the offline problem by showing that computing optimal schedules is NP-hard, even for unit-size jobs. Hence, unless P = NP, optimal solutions cannot be computed efficiently. Albers et al. 3 then develop polynomial time offline algorithms that achieve constant factor approximations, such as, for any input the consumed energy is within a constant factor of the true optimum. They also devise online algorithms attaining constant competitive ratios. Lam et al. 30 study deadline-based scheduling on two speed-bounded processors. They present a strategy that is constant competitive in terms of throughput maximization and energy minimization. Bunde 15 investigates flow time minimization in multiprocessor environments, given a fixed energy volume. He presents hardness results as well as approximation guarantees for unit-size jobs. Lam et al. 31 consider the objective function of minimizing energy plus flow times. They design online algorithms achieving constant competitive ratios. Makespan minimization: Another basic objective function in scheduling is makespan minimization, that is, the minimization of the point in time when the entire schedule ends. Bunde 15 assumes that jobs arrive over time and develops algorithms for single-and multiprocessor environments. Pruhs et al. 36 consider tasks having precedence constraints defined between them. They devise algorithms for parallel processors given a fixed energy volume. Wireless networks such as ad hoc networks and sensor networks have received considerable attention over the last few years. Prominent applications of such networks are habitat observation, environmental monitoring, and forecasting. Network nodes usually have very limited battery capacity so that effective energy management strategies are essential to improve the lifetime of a network. In this survey, we focus on two algorithmic problems that have received considerable interest in the research community recently. Moreover, these problems can be viewed as scheduling problems and hence are related to the topics addressed in the previous sections. network topologies Wireless ad hoc network do not have a fixed infrastructure. The network basically consists of a collection of radio stations with antennas for sending and receiving signals. During transmission a station s has to choose a transmission power P s , taking into account that the signal strength decreases over distance. The signal is successfully received by a station t only if P s /dist(s,t) a > g. Here dist(s,t) denotes the distance between s and t, coefficient a > 1 is the attenuation rate and g > 0 is a transmission quality parameter. In practice the attenuation rate is in the range between 2 and 5. Without loss of generality we may assume g = 1. In data transmission, a very basic operation is broadcast, where a given source node wishes to send a piece of information to all other nodes in the network. We study the problem of designing broadcast topologies allowing energy-efficient broadcast operations in wireless networks. Consider a set V of n nodes that are located in the real plane R 2 . A source node s Î V has to disseminate a message to all other nodes in the network. However s does not have to inform all v Î V directly. Instead nodes may serve as relay stations. If v receives the message and transmits it to w 1 , …, w k , then v has to use a power of P v = max 1£j£k dist(v, w j ) a . The goal is to find a topology, that is, a transmission schedule that minimizes the total power/energy E = S v ÎV P v incurred by all the nodes. Note that such a schedule corresponds to a tree T that is rooted at s and contains all the nodes of V. The children of a node v are the nodes to which v transfers the message. Clementi et al. 19 showed that the computation of optimal schedules is NP-hard. Therefore one resorts to approximations. An algorithm ALG achieves a c-approximation if for every input, such as, for every node set V, the solution computed by ALG incurs an energy consumption of no more than c times the optimum value. Wan et al. 39 investigate various algorithms in terms of their approximation guarantees. The most extensively studied strategy is MST. For a given node set V, MST computes a standard minimum spanning tree T, such as, a tree of minimum total edge length containing all the vertices of V (see, e.g., Cormen et al. 20 ). The tree is rooted at source node s. Data transmission is performed along the edges of T, that is, each node transmits a received message to all of its children in the tree. Intuitively, this algorithm is sensible because the small total edge length of a minimum spanning tree should lead to a small overall energy consumption. algorithm MsT: For a given V, compute a minimum spanning tree rooted at s. Any node v transmits a given message to all of its children in T. Many and Wan et al. 39 imply that the approximation ratio c of BIP satisfies 13/3 £ c £ 6. It would be interesting to develop tight bounds for this algorithm. As mentioned above, sensor networks are typically used to monitor an environment, measuring, e.g., temperature or a chemical value. The data has to be transferred to a designated sink node that may perform further actions. Becchetti et al. 13 and Korteweg et al. develop energy-efficient protocols for data aggregation. Suppose the transmission topology is given by a tree T rooted at the sink s. Data gathered at a network node v is transmitted along the path from v to s in T. Network nodes have the ability to combine data. If two or more data packets simultaneously reside at a node v, then v may merge these packets into a review articles 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 v i where the item arises, an arrival time r i and a deadline d i 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. In this survey, we have reviewed algorithmic solutions to save energy. Another survey on algorithmic problems 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 continue 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 understanding of speed scaling techniques in multiprocessor environments as multicore architectures become more and more common not only in servers 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-efficient point-to-point communication, complementing the existing work on broadcast and data-aggregation protocols. 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. Susanne Albers is a professor in the department of computer science at humboldt university, berlin, germany.
We mention the area of energy-aware scheduling, where energy consumption is taken into account (see REF for an overview).
Energy-efficient algorithms
CACM
Computer Science