Optimizations Of Power Allocation

The number of mobile users (devices) reaches 5 billion in year 2010. Due to the great number of devices and the fact that all the devices are equipped with limited battery (power), designing algorithms to save the energy usage on a single device or properly utilize the power to maximize the date throughput of the mobile system receives many concerns. We theoretically study several scheduling/allocation problems to optimize the power usage on a device and the system. We provide a thorough study on approximation algorithms (or exact) to compute the (optimal) power allocation on a single device and online algorithms with optimal competitive ratio to maximize the data throughput on a mobile system.Dynamic voltage scaling technique provides the capability for processors to adjust the speed and control the energy consumption. We study the pessimistic accelerate model where the acceleration rate of the processor speed is at most K and jobs cannot be executed during the speed transition period. The objective is to find a min-energy (optimal) schedule that finishes every job within its deadline. The aligned jobs where earlier released jobs have earlier deadlines are studied. We start by investigating a special case where all jobs have a common arrival time and design an O(n2) algorithm to compute the optimal schedule based on some nice properties of the optimal schedule. Then, we study the general aligned jobs and obtain an O(n2) algorithm to compute the optimal schedule by using the algorithm for the common arrival time case as a building block. Because our algorithm relies on the computation of the optimal schedule in the ideal model (K=∞), in order to achieve O(n2) complexity, we improve the complexity of computing the optimal schedule in the ideal model for aligned jobs from the currently best known O(n2 log n) to O(n2). We further study the speed scaling problem with memory/cache consideration. Each job needs some time for memory operation when it is fetched from the memory/cache. We investigate the general jobs for with-cache model with resource augmentation where the memory operation time speeds up by at most s times. We proposed a (2as/(s-1))α/2-approximation algorithm for such a setting.We then turn to the power allocation problem on a mobile system (wireless networks). The limited power, dynamic status and interferences are all serious concerns of the wireless channels. Apart from considering the physical characteristics, another important direction it to study the selfish behaviors of the users (e.g. transmitters). We study the online power allocation problem on the time varying channels to maximize the global gains of the network with interference. Besides the physical constraints, treating each user as an individual agent (player) in a game theoretical view, we simultaneously capture the selfish behavior of the users. The users are allowed to cheat on their private value (power budget) to increase their own utility. We aim at maximizing the global gains of the network while ensuring that each agent optimizes its own utility by reporting its true power budget (admits truthful mechanism). We derive a general lower boundΩ(log H/h)-competitive for any randomized algorithm using Yao's minimax principle. We further propose a randomized online algorithm which not only admits truthful mechanism but also is provedΩ(log H/h)-competitive in expectation and hence optimal with respect to the competitive ratio.