Optimization and game theory techniques for energy-constrained networked systems and the smart grid

Abstract

The energy needs of all sectors of our modern societies are constantly increasing. Indicatively,annual worldwide demand for electricity has increased ten-fold within the last 50 years. Thus, energyefficiency has become a major target of the research community. The ongoing research efforts are focusedon two main threads, i) optimizing efficiency and reliability of the power grid and ii) improvingenergy efficiency of individual devices / systems. In this thesis we explore the use of optimizationand game theory techniques towards both goals.Stable and economic operation of the power grid calls for electricity demand to be uniformly distributedacross a day. Currently, the price of electricity is fixed throughout a day for most users. Givenalso the highly correlated daily schedules of users, this leads to unbalanced distribution of demand.However, the recent development of low-cost smart meters enables bidirectional communication betweenthe electricity operator and each user, and hence introduces the option of dynamic pricing anddemand adaptation (a.k.a. Demand Response - DR). Dynamic pricing motivates home users to modifytheir electricity consumption profile so as to reduce their electricity bill. Eventually, users by movingdemand out of peak consumption periods lead to a more balanced total demand pattern and a morestable grid.A DR scheme has to balance the contradictory interests of the utility operator and the users.On the one hand, the operator wants to minimize electricity generation cost. On the other hand,each user aims to maximize a utility function that captures the trade-off between timely executionof demands and financial savings. In this thesis we focus on designing efficient DR schemes for theresidential sector. Initially, we introduce a realistic model of user’s response to time-varying pricesand identify the operating constraints of home appliances that make optimal demand scheduling NPHard.Thus, we devise an optimization-based dynamic pricing mechanism and demonstrate how itcan be implemented as a day-ahead DR market. Our numerical results underline the potential ofresidential DR and verify that our scheme exploits DR benefits more efficiently compared to existingones.The large number of home users though and the fact that the utility operator generally lacks the know-how of designing and applying dynamic pricing at such a large scale introduce the need fora new market entity. Aggregators act as intermediaries that coordinate home users to shift or evencurtail their demands and then resell this service to the utility operator. In this direction, we introducea three-level hierarchical model for the smart grid market and we devise the corresponding pricingmechanism for each level. The operator seeks to minimize the smart grid operational cost and offersrewards to aggregators toward this goal. Aggregators are profit-maximizing entities that competeto sell DR services to the operator. Finally, end-users are also self-interested and seek to optimizethe tradeoff between earnings and discomfort. Based on realistic demand traces we demonstrate thedominant role of the utility operator and how its strategy affects the actual DR benefits. Although theproposed scheme guarantees significant financial benefits for each market entity, interestingly usersthat are extremely willing to modify their consumption pattern do not derive the maximum financialbenefit.In parallel to optimizing the power grid itself, per device energy economy has become a goal ofutmost performance. Contemporary mobile devices are battery powered and hence characterized bylimited processing and energy resources. In addition, the latest mobile applications are particularlydemanding and hence cannot be executed locally. Instead, a mobile device can outsource its computationallyintensive tasks to the cloud over its wireless access interface, so as to maximize bothits lifetime and performance. In this thesis, we explore task offloading and Virtual Machine (VM)migration mechanisms for the mobile cloud computing paradigm that minimize energy consumptionand execution time. We identify that in order to decide whether offloading is beneficial, a mobilehas also to consider the delay and energy cost of data transfer from/to the cloud. On the other hand,the challenge for the cloud is to optimally allocate the arising VMs to its servers so as to minimizeits operating cost without sacrificing performance though. Providing quality of service guarantees isparticularly challenging in the dynamic cloud environment, due to the time-varying bandwidth of theaccess links, the ever changing available processing capacity at each server and the time-varying datavolume of each VM. Thus, we propose a mobile cloud architecture that brings the cloud closer tothe user and online VM migration policies spanning fully uncoordinated ones, in which each user orserver autonomously makes its migration decisions, up to cloud-wide ones.Nevertheless, the transceiver is one of the most power consuming components of a mobile wirelessdevice. Since the medium access layer controls when a transmission takes place, it has significantimpact on overall energy consumption and consequently on the lifetime of a device. In this direction,we investigate the potential of sleep modes when several wireless devices compete for medium access.In order to characterize the resulting energy-throughput tradeoff, we calculate the optimal throughputunder energy constraints and we model contention for wireless medium as a non-cooperative game.The strategy of each user consists of its access probability and its sleep mode schedule. We showthat the resulting game has a unique Nash Equilibrium Point and that energy constraints reduce thenegative impact of selfish behaviour, leading to bounded price of anarchy. We devise also a modifiedmedium access scheme, where the state of the medium can be sampled in the beginning of each frameand show that it leads to improved exploitation of the medium without any explicit cooperation. Finally, we move to a scenario where concurrent transmissions over the same channel are not destructivebut lead to reduced performance due to interference. In this context, we consider the problemof joint relay assignment and power control. We develop interference-aware sum-rate maximizationalgorithms that make use of a bipartite maximum weight matching formulation of the problem andgeometric programming and are amenable to distributed implementation. We also identify the importanceof interference for cell-edge users in cellular networks and demonstrate that our schemes bringtogether two main features of 4G systems, namely interference management and relaying.