Dynamic energy management in resource limited systems with real-time constraints

The problems considered in this dissertation are motivated by the increasing need for energy management in resource limited systems with real-time constraints. Two techniques are utilized to minimize energy consumption: Dynamic Voltage Scaling and Dynamic Transmission Control, which can greatly conserve energy by finely tuning the voltage level in a processor and the transmission rate in a transceiver unit. Since both techniques face a similar tradeoff between energy and latency, we consider them within the same class of discrete event systems with hard real-time constraints, where tasks are non-preemptive and aperiodic. We study them as dynamic optimization problems whose objective is to minimize energy consumption by dynamically tuning the processing rate (equivalent to the voltage level or the transmission rate) subject to real-time execution constraints.;These problems are approached along three dimensions: topology, cost function and control framework. We begin with the single-stage problem and develop a highly efficient algorithm termed Critical Task Decomposition Algorithm (CTDA) by exploiting the structural properties of an optimal state trajectory. This can solve the off-line problem without relying on any nonlinear programming solver. Then, we study the related admission control problem and develop a Maximal Shift Task Algorithm (MSTA) to guarantee feasibility for both off-line and on-line single-stage problems. Subsequently, the on-line version of the problem is solved by using two methods: worst-case analysis and a probabilistic comparison algorithm. The former can bypass the complexity of random effects and has low computational complexity. The latter can improve performance by using probability distribution information based on a novel idea providing an alternative to standard stochastic programming, in which the efficiency of the off-line solution algorithm, CTDA, can be fully utilized.;Next, we deal with a two-stage system with homogeneous cost functions and find that the optimal structural properties exploited in single-stage systems are no longer applicable to multi-stage systems. After exploring new optimal structural properties, we derive a new efficient algorithm, termed Virtual Deadline Algorithm (VDA), which can obtain the global optimal solution by solving one-dimensional bounded convex optimization problems in spite of the dimensionality of the original problem. Finally, we consider a multi-stage system and a multi-layer system with general cost functions and find that only some of the previous properties of the optimal state trajectory still apply, but they need to be appropriately redefined. Based on that, we obtain an efficient algorithm, still termed Virtual Deadline Algorithm (VDA), which can obtain the global optimal solution by solving low-dimensional bounded convex optimization problems independent of the dimensionality of the original problem.