Communications - May 2010

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 higher-power 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 competitive 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 guar-
antee. An online strategy must per-
form well on all inputs (idle periods)
that might even be generated by an
adversary. This adversarial scenario
may seem pessimistic but it is consis-
tent with classical algorithm analysis
that evaluates strategies in terms of
their worst-case resources, typically
running time or memory require-
ments. In this section, we will mostly
study algorithms using competitive
analysis but will also consider perfor-
mance on inputs that are generated
according to probability distributions.

systems with two states

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 r T < b, OPT remains in the active state throughout the idle period as transitioning between the active and sleep modes costs more. If r T ³ 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.