Optimizations of power allocation


Student thesis: Doctoral Thesis

View graph of relations


  • Weiwei WU

Related Research Unit(s)


Awarding Institution
Award date3 Oct 2011


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 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(n2logn) to O(n2). We then turn to the power allocation problem on the multi‐machine system (or devices on the mobile 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 is 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, by 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). Let the channel quality of all users be varying over time in range [h, H] and it equals 0 when that user is not allowed to transmit any data in that time. 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 O(log H/h) - competitive in expectation and hence optimal with respect to the asymptotic competitive ratio.

    Research areas

  • Wireless communication systems, Conservation, Electric power, Power supply