UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Demand side management for the future smart grid Samadi Dinani, Pedram 2015

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
24-ubc_2015_may_samadidinani_pedram.pdf [ 1005.62kB ]
Metadata
JSON: 24-1.0167156.json
JSON-LD: 24-1.0167156-ld.json
RDF/XML (Pretty): 24-1.0167156-rdf.xml
RDF/JSON: 24-1.0167156-rdf.json
Turtle: 24-1.0167156-turtle.txt
N-Triples: 24-1.0167156-rdf-ntriples.txt
Original Record: 24-1.0167156-source.json
Full Text
24-1.0167156-fulltext.txt
Citation
24-1.0167156.ris

Full Text

Demand Side Management for the Future Smart GridbyPedram Samadi DinaniB.Sc., Isfahan University of Technology, Isfahan, Iran, 2006M.Sc., Isfahan University of Technology, Isfahan, Iran, 2009A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe Faculty of Graduate and Postdoctoral Studies(Electrical and Computer Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)March 2015c© Pedram Samadi Dinani, 2015AbstractTo achieve a high level of reliability and robustness in power systems, the grid is usuallydesigned for the peak demand rather than the average demand. This usually results inan under-utilized system. Demand side management (DSM) programs can be adopted toshape the load pattern of the users to better utilize the available power generation capacityand to prevent installing new generation and transmission infrastructures. In this thesis,we propose different algorithms for DSM. First, we focus on the problem of maximizingthe social welfare of the users. We consider a scenario where the users are equipped withautomated control units and are able to make price-responsive decisions. We proposea Vickrey-Clarke-Groves (VCG) mechanism to maximize the social welfare of the users.Subsequently, we focus on developing a novel automated load scheduling algorithm tominimize the energy expenses of the user. The proposed algorithm takes into account theeffects of the load uncertainties in future time slots. Moreover, the operational constraintsof different types of appliances including must-run appliances, and interruptible and non-interruptible controllable appliances are studied. Next, we study how the utility companycan set price values for different times of a day such that the peak-to-average ratio (PAR)of the load is minimized. We also consider the effects of the uncertainty regarding theprice-responsiveness of the users. To simulate the likely behavior of the users in responseto different price values for different times of the day, we propose the use of a systemsimulator unit. We propose two pricing algorithms based on stochastic approximationaiming to minimize the PAR of the aggregate load. Finally, we consider systems withiiAbstracthigh penetration of renewable energy resources. To tackle the reverse power flow problemassociated with these systems, we propose a joint load scheduling and trading algorithm.This algorithm encourages the users to sell their excess generation to their neighboringusers which mitigates the reverse power flow problem.iiiPrefaceHereby, I declare that I am the first author of this thesis. Chapters 2-5 encompass workthat has been published or is under review. The corresponding papers are co-authoredby Dr. Vincent Wong and Dr. Robert Schober who supervised me through this research.The papers corresponding to Chapters 2, 3, and 4 were also co-authored by Dr. Amir-Hamed Mohsenian-Rad, who provided valuable comments on these works. The followingpublications describe the work completed in this thesis.Journal Papers, Published• Pedram Samadi, Hamed Mohsenian-Rad, Vincent W. S. Wong, and Robert Schober,“Real-Time Pricing for Demand Response Based on Stochastic Approximation,”IEEE Transactions on Smart Grid, vol. 5, no. 2, pp. 789-798, March 2014.• Pedram Samadi, Hamed Mohsenian-Rad, Vincent W. S. Wong, and Robert Schober,“Tackling the Load Uncertainty Challenges for Energy Consumption Scheduling inSmart Grid,” IEEE Transactions on Smart Grid, vol. 4, no. 2, pp. 1007-1016, June2013.• Pedram Samadi, A. Hamed Mohsenian-Rad, Robert Schober, and Vincent W. S.Wong, “Advanced Demand Side Management for the Future Smart Grid Using Mech-anism Design,” IEEE Transactions on Smart Grid, vol. 3, no. 3, pp. 1170-1180,September 2012.Journal Paper, SubmittedivPreface• Pedram Samadi, Vincent W. S. Wong, and Robert Schober, “Local Scheduling andPower Trading in Systems with High Penetration of Renewable Energy Resources,”submitted, November 2014.Conference Papers, Published• Pedram Samadi, Hamed Mohsenian-Rad, Vincent W. S. Wong, and Robert Schober,“Utilizing Renewable Energy Resources by Adopting DSM Techniques and StorageFacilities,” in Proc. of IEEE International Conference on Communications (ICC),Sydney, Australia, June 2014.• Pedram Samadi, Hamed Mohsenian-Rad, Vincent W. S. Wong, and Robert Schober,“Adaptive Energy Consumption Scheduling with Load Uncertainty for the SmartGrid,” in Proc. of IEEE International Conference on Communications (ICC), Bu-dapest, Hungary, June 2013.• Pedram Samadi, Robert Schober, and Vincent W. S. Wong, “Optimal Energy Con-sumption Scheduling Using Mechanism Design for the Future Smart Grid,” in Proc.of IEEE International Conference on Smart Grid Communications (SmartGridComm),Brussels, Belgium, October 2011.• Pedram Samadi, Hamed Mohsenian-Rad, Robert Schober, Vincent W. S. Wong, andJuri Jatskevich, “Optimal Real-time Pricing Algorithm Based on Utility Maximiza-tion for Smart Grid,” in Proc. of IEEE International Conference on Smart GridCommunications (SmartGridComm), Gaithersburg, Maryland, October 2010.vPrefaceBook Chapter• Pedram Samadi, Hamed Mohsenian-Rad, Vincent W. S. Wong, and Robert Schober,“Demand Side Management for Smart Grid: Opportunities and Challenges,” inSmart Grid Communications and Networking, Edited by Vincent Poor, Zhu Han,and Ekram Hossain, Cambridge University Press, 2011.viTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiList of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xivAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Demand Side Management Techniques . . . . . . . . . . . . . . . . . . . . 21.1.1 DSM Challenges and Opportunities . . . . . . . . . . . . . . . . . 41.1.2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.2 Summary of Results and Contributions . . . . . . . . . . . . . . . . . . . 111.3 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 DSM Using Mechanism Design . . . . . . . . . . . . . . . . . . . . . . . . 162.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.2 System Model and Problem Formulation . . . . . . . . . . . . . . . . . . . 18viiTable of Contents2.2.1 Power System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.2.2 User Preference and Utility Function . . . . . . . . . . . . . . . . . 202.2.3 Energy Cost Model . . . . . . . . . . . . . . . . . . . . . . . . . . 232.2.4 Problem Formulation and Efficient Allocations . . . . . . . . . . . 242.3 Applying the Vickrey-Clarke-Groves Mechanism . . . . . . . . . . . . . . 282.3.1 VCG Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.3.2 VCG Mechanism and Nonnegative Transfer . . . . . . . . . . . . . 322.3.3 VCG Mechanism and Market Clearing Price . . . . . . . . . . . . . 322.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.4.1 Performance Gains from Real-time Interaction with Users . . . . . 332.4.2 The Impact of Reflecting the Generating Cost . . . . . . . . . . . . 342.4.3 Communication Requirements of the VCG System . . . . . . . . . 352.4.4 Effect of Parameter ω . . . . . . . . . . . . . . . . . . . . . . . . . 372.4.5 Exploring the Truthfulness Property . . . . . . . . . . . . . . . . . 382.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393 Energy Consumption Scheduling with Load Uncertainty . . . . . . . . 403.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.3 Problem Formulation and Algorithm Description . . . . . . . . . . . . . . 453.3.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . 463.3.2 Load Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523.3.3 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . 553.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563.4.1 Performance Gains of Users and Utility Company . . . . . . . . . . 583.4.2 Computational Complexity . . . . . . . . . . . . . . . . . . . . . . 59viiiTable of Contents3.4.3 The Impact of Price Control Parameter bt . . . . . . . . . . . . . . 603.4.4 The Impact of Adopting Inclining Block Rates . . . . . . . . . . . 633.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 634 Real-Time Pricing for DSM . . . . . . . . . . . . . . . . . . . . . . . . . . 654.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674.2.1 Centralized Load Control Algorithm . . . . . . . . . . . . . . . . . 684.2.2 Decentralized Price-Based Load Control Algorithm . . . . . . . . . 704.3 Price Control Unit (PCU) . . . . . . . . . . . . . . . . . . . . . . . . . . . 724.3.1 Finite-Difference Price Selection (FDPS) . . . . . . . . . . . . . . . 724.3.2 Simultaneous Perturbation Price Selection (SPPS) . . . . . . . . . 734.3.3 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . 744.3.4 Convergence of the Algorithms . . . . . . . . . . . . . . . . . . . . 754.4 System Simulator Unit (SSU) . . . . . . . . . . . . . . . . . . . . . . . . . 774.4.1 Power Scheduling Done by ECC Devices . . . . . . . . . . . . . . . 784.4.2 Simulation of ECC Operation at SSU . . . . . . . . . . . . . . . . 794.4.3 Updating the Value Function Estimation . . . . . . . . . . . . . . 814.4.4 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . 834.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 844.5.1 Performance Gains for the Utility Company . . . . . . . . . . . . . 864.5.2 Performance Gain of the Users . . . . . . . . . . . . . . . . . . . . 874.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905 Load Scheduling and Power Trading . . . . . . . . . . . . . . . . . . . . . 925.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 925.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94ixTable of Contents5.3 Problem Formulation and Algorithm Description . . . . . . . . . . . . . . 985.3.1 Scheduling Problem Formulation . . . . . . . . . . . . . . . . . . . 995.3.2 Trading Problem Formulation . . . . . . . . . . . . . . . . . . . . . 1035.3.3 Market Clearing Game . . . . . . . . . . . . . . . . . . . . . . . . 1095.3.4 Algorithm Description . . . . . . . . . . . . . . . . . . . . . . . . . 1105.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1115.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1156 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 1176.1 Research Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1176.2 Suggestions for Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 119Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121AppendicesA Proof of Proposition 2.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130B Proof of Theorem 2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131C Proof of Theorem 2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132xList of Tables2.1 Average number of exchanged messages in VCG system and system withprice anticipating users. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.1 List of variables used in this chapter. . . . . . . . . . . . . . . . . . . . . . 483.2 Performance measures and complexity analysis of the proposed algorithm. 614.1 Operating specifications of different appliances. . . . . . . . . . . . . . . . 864.2 Performance measures of different algorithms. . . . . . . . . . . . . . . . . 905.1 Operating specifications of different appliances. . . . . . . . . . . . . . . . 113xiList of Figures2.1 An illustration of the regional energy providers, several users, and multiplepower generators as parts of the general wholesale energy market. . . . . . 192.2 Sample utility functions for power users (α = 0.3). . . . . . . . . . . . . . . 232.3 Power consumption for the proposed VCG method and a peak load pricing(PLP) method. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.4 Payoff of the energy provider for the proposed VCG system, the system withprice anticipating users, and the system with price taking users. . . . . . . 362.5 Power consumption of the first user and aggregate power consumption ofother users when ω of the first user is increased. . . . . . . . . . . . . . . . 382.6 The payoff of the first user for different values of declared ωˆ1 and Eˆ1 (thetrue ω1 is equal 12 and the true E1 is equal 15). . . . . . . . . . . . . . . . 393.1 Different operating states of (a) must-run, (b) non-interruptible controllable,and (c) interruptible controllable appliances. . . . . . . . . . . . . . . . . . 443.2 Must-run appliance a ∈ St with Ta = 3 will be active in τ > t if it startsoperation within time interval [max{t + 1, τ − Ta + 1}, τ ]. . . . . . . . . . . 543.3 The pricing parameters used based on the combined RTP and IBR pricingmodel in (3.3). Parameter bt = 3.5 kW is fixed for all time slots. . . . . . 57xiiList of Figures3.4 Power consumption for (a) the system without ECC deployment, (b) thesystem with ECC deployment, and (c) the system with ECC deployment inwhich complete demand information is available ahead of time. . . . . . . . 593.5 The daily payment of the user for different values of parameter bt. . . . . . 623.6 PAR of the system for different values of parameter bt. . . . . . . . . . . . 623.7 The daily payment of the user for different values of parameter θ. . . . . . 643.8 PAR of the system for different values of parameter θ. . . . . . . . . . . . . 644.1 The block diagram of the proposed closed-loop pricing model. . . . . . . . 664.2 Aggregate load profile in different scenarios. . . . . . . . . . . . . . . . . . 884.3 The PAR of the aggregate load in different scenarios. . . . . . . . . . . . . 885.1 An example for the pattern of power consumption of interruptible control-lable appliance a before and after scheduling. . . . . . . . . . . . . . . . . . 965.2 Average imported power from utility company for different scenarios. . . . 1145.3 Reverse power flow vs. the percentage of users equipped with RERs. . . . 1145.4 MCP for Gut = 12 kW (Case 1) and Gut = 6 kW (Case 2). . . . . . . . . . . 115xiiiList of AbbreviationsAMI Advanced metering infrastructureDAP Day-ahead pricingDG Distributed generatorDLC Direct load controlDSM Demand side managementECC Energy consumption controllerFDPS Finite-deference price selectionGBD Generalized Benders decompositionIBR Inclining block ratesIPM Interior point methodMCP Market clearing pricePAR Peak-to-average ratioPC Personal computerPCU Price control unitPEV Plug-in electric vehiclePHEV Plug-in hybrid electric vehiclePLP Peak load pricingRER Renewable energy resourceRTP Real-time pricingxivList of AbbreviationsSPPS Simultaneous perturbation price selectionSPSP Simultaneous perturbation stochastic approximationSSU System simulator unitTOU Time-of-use (pricing)TV TelevisionVCG Vickrey-Clarke-Groves (mechanism)xvAcknowledgmentsFirst of all, I want to express my deepest sense of gratitude to my supervisors Dr. VincentWong and Dr. Robert Schober without whom this research would not be possible. I wantto thank them for their continuous support, patience, technical and non-technical guidancethat helped me accomplish this research. I also want to thank them for their understandingof the conditions and problems that I was involved with as a new international student.I want to declare my special thanks to Dr. Amir Hamed Mohsenian-Rad for his enor-mous help, advice, and comments through my research. It was not possible to accomplishsome parts without his very helpful advice.I am also thankful to my best friends Keivan Ronasi, Ahmad Ashouri, Nasim Arianpoo,and Anahita Keshavarzi for their always being supportive and accountable. I want tothank Ali, Nastaran, Paria, Mahsa, Pooya, Azadeh, Milad, Bahar, Farid, Gelareh, Nasim,Bahareh, Neshat, Adam, Toufiqul, Imtiaz and all my other friends that definitely I cannotname them all here.Most importantly, I feel indebted to my great family, my father, my mother and mybrothers for their everlasting love, support, and protectivity not only in years of doing PhDbut also throughout my entire life.This work was supported by the Natural Sciences and Engineering Research Council(NSERC) of Canada.xviChapter 1IntroductionDemand side management (DSM) is one of the key components of the future smart grid toenable more efficient and reliable grid operation. To achieve a high level of reliability androbustness in power systems, the grid is usually designed for the peak demand rather thanthe average demand. This usually results in an under-utilized system. With the increasingexpectations of the customers both in quantity and quality of the electric power [1], theemergence of new types of loads such as plug-in hybrid electric vehicles (PHEVs) whichcan potentially double the average residential load, the limited energy resources, and thelengthy and expensive process of exploiting new resources, there is an essential need to im-prove the utilization of the power grids [2]. DSM programs comprise different techniquesemployed to better utilize the available power generation capacity and to prevent installingnew generation and transmission infrastructures. These programs typically aim at one orboth of the following design objectives: reducing consumption and shifting consumption.Adopting energy-aware consumption patterns and constructing energy efficient buildingscan reduce the energy consumption of users. However, there is also a need to develop prac-tical methods to encourage users to shift their usage of high-power household appliancesto off-peak hours.In the current power systems, there is also a high concern regarding environmentalissues. To reduce the emission of greenhouse gases, the deployment of more environmentallyfriendly and sustainable distributed renewable energy resources (RERs) such as wind andsolar attracts more attention. Despite the benefits obtained by integrating RERs into the1Chapter 1. Introductiondistribution system including improved reliability, power quality, and reduced distributionloss, the management of RERs is challenging. Considering the intermittent and randomnature of RERs, it is difficult to match supply and demand. Utilizing backup power andenergy storage facilities are among the well-known solutions which have been proposed totackle this problem [3, 4]. Backup power plants are usually fast acting power generators.However, the cost of operation and maintenance of these facilities is very high, and theenvironmental impact of these power plants is significant. An alternative approach is touse DSM to shape the daily energy consumption of the users in order to reduce the gapbetween supply and demand [5–8].In this thesis, we propose different algorithms for DSM purposes. The proposed al-gorithms aim at achieving different objectives including maximizing the social welfare,minimizing the peak-to-average ratio (PAR) of the aggregate load, and minimizing theenergy expenses of the users. Mathematical tools, such as optimization theory, mechanismdesign, game theory, and dynamic programming are applied in the design and analysisof these algorithms. The rest of this chapter is organized as follows. In Section 1.1, weprovide an overview of different techniques considered for DSM. We summarize the maincontributions and results of this thesis in Section 1.2. Finally, the organization of the thesisis described in Section 1.3.1.1 Demand Side Management TechniquesDSM has been considered since the early 1980s [9–13]. Most power utilities prefer to thinkof DSM as a tool for load shaping, where the electricity demand is re-distributed over acertain period of time (e.g., time-of-day, day-of-week). Broad categories of load shapingobjectives include peak clipping, load shifting, valley filling, strategic conservation, andflexible load shaping [9]. For example, peak clipping includes reducing the customers’2Chapter 1. Introductionload at the peak hours. Load shifting consists of shifting load from the peak hours tothe off-peak periods. Direct load control (DLC) and price-based load control are twogeneral categories of DSM programs. In DLC programs, based on a contract between theenergy provider and the users, the energy provider can remotely control the operationand energy consumption of certain appliances for users [14–20]. DLC programs can beused effectively where there is a centralized control over the operation of different loads,batteries, and alternative storage facilities. Examples of such scenario include microgridsthat can be managed autonomously. In contrast, in price-based programs, the energyprovider provides economic incentives to consumers by reflecting the hourly changes in thewholesale electricity price to the demand side such that users are encouraged to consumewisely [21–26].Wholesale prices (i.e., the prices set by the generators to regional electricity retailersthrough a bidding process) vary drastically between the low-demand times of a day andthe high demand periods. In particular, the electricity prices are lower at low demandhours and higher at high demand hours. However, these changes in the wholesale pricesare currently unnoticed by end users in most regions. That is, users are usually chargedwith some average prices, and thus, there is no incentive for them to change their powerconsumption to utilize the available generation capacity efficiently. Mapping the wholesaleelectricity prices to the retail users can mitigate this problem and encourage users toconserve energy at high demand hours or shift the operation of their high load appliancesfrom peak hours to off-peak hours.Several time differentiating pricing methods have already been proposed in the litera-ture. In time differentiating pricing tariffs, the intended operation period is divided intoseveral time slots, and the price of electricity varies across time slots. For example, theprices may correspond to off-peak, mid-peak, and on-peak hours. The prices are usually3Chapter 1. Introductionhigher in the afternoon on hot days in the summer and cold days in the winter. Examplesof time differentiating pricing include real-time pricing (RTP), time-of-use (TOU) pricing,and day-ahead pricing (DAP) [22, 23]. These methods mainly differ in how frequently theutility company changes the pricing tariffs, which may vary from once or twice a year inTOU pricing to hourly changes in RTP.1.1.1 DSM Challenges and OpportunitiesExtracting Local InformationWith the growing deployment of advanced metering infrastructure (AMI) [27] and auto-mated energy consumption controller (ECC) devices [11, 28, 29], RTP is gradually be-coming a feasible DSM solution. In general, it is difficult for power users to follow theRTP price variations to make appropriate decisions accordingly. In this regard, ECC de-vices can help by making such price-responsive decisions on behalf of users to achievecertain objectives. Examples of such objectives include minimizing the energy expenses[11], maximizing the social welfare [28, 29], minimizing both the energy expenses and thewaiting time [12], and maintaining system stability with minimum curtailment [30]. How-ever, achieving social objectives (e.g., maximizing social welfare) is difficult because of itscomputational complexity. It also requires collecting various information about the energyconsumption behavior of the users, the price elasticity of the users, and the benefit thateach user obtains by consuming a certain amount of energy. However, in general, usersare not willing to reveal such information, unless there is an incentive for them to do so.Therefore, elaborate design rules (mechanisms) are needed such that it is in each user’sself interest to reveal its local information.In Chapter 2, we propose an efficient pricing method to tackle this problem. We assumethat each user is equipped with an ECC as part of its smart meter. All smart meters are4Chapter 1. Introductionconnected to not only the power grid but also a communication infrastructure. This allowstwo-way communication among smart meters and the utility company. We analyticallymodel each user’s preferences and energy consumption patterns in form of a utility function.Based on this model, we propose a Vickrey-Clarke-Groves (VCG) mechanism which aimsto maximize the social welfare, i.e., the aggregate utility functions of all users minus thetotal energy cost. Our design requires that each user provides some information about itsenergy demand. In return, the energy provider will determine each user’s electricity billpayment. The structure of electricity payment for each user is such that users are willingto reveal their local demand information to the energy provider.Load UncertaintyTo shape the load pattern of the users, the energy provider sets different price values fordifferent times of a day. The ECC device of each user retrieves the price informationfrom the energy provider, and based on the constraints set by the user, schedules theoperation of the appliances such that the energy expenses of the user is minimized. Inpractice, the information about the list of the appliances that need to be scheduled is notknown at the beginning of the day, and the decision whether to use some appliances ornot is made throughout the day. Moreover, the constraints on the operation of individualappliances are decided by the user and may vary from time to time. On the other hand,making decisions about the operating state of different appliances for the current time slotdepends on the information about the user’s energy needs available at the current timeslot and the expected schedule determined in the upcoming time slots. The schedulingproblem with load uncertainty usually includes solving a complex problem in the formof mixed-integer programming or dynamic programming. However, in situations wherecomputational complexity or convergence time of the algorithm are critical such as in real-time application, a suboptimal but faster schemes that establish a balance between simple5Chapter 1. Introductionimplementation and adequate performance are preferable.In Chapter 3, we propose a novel optimization-based real-time residential load manage-ment algorithm that takes into account load uncertainty in order to minimize the energypayment for each user. The algorithm takes into account different types of constraints onthe operation of different appliances such as must-run appliances, controllable appliancesthat are interruptible, and controllable appliances that are not interruptible.Price ResponsivenessThe level of success for different pricing methods depends on various factors such as theamount of information being provided to each user, the effectiveness of the mapping of thewholesale prices to the retail prices, and the knowledge and abilities of the users to respondto price information. Another factor is the effectiveness of the home automation system.While the use of ECC devices improves users’ rationality in response to price changes,such ECC devices can also introduce new DSM challenges such as load synchronization[12]. Load synchronization is referred to as the concentration of a large portion of energyconsumption in low-price hours. Therefore, the effect of automated ECC devices on users’price-responsiveness is not obvious and yet to be investigated. That is, to set price valuesfor different times of the day, the energy provider needs to take into account the level ofprice-responsiveness of the users.It has been shown that load synchronization can be prevented by using pricing tariffswith inclining block rates (IBR). For the IBR tariffs, the marginal price increases with thetotal consumed power [31]. That is, beyond a predetermined power consumption threshold,electricity is offered at higher rates. This provides incentives for the users to distributetheir load across different times of the day. Southern California Edison and Pacific Gas& Electric in United States, and British Columbia Hydro in Canada currently use IBRwith various two-level conservation rate structures [32, 33]. In Chapter 3, we consider6Chapter 1. IntroductionRTP combined with IBR tariffs. We also study the effect combined RTP and IBR tariffson the electricity payment of the users as well as on the their load pattern. Moreover,in Chapter 4, we extend this idea and propose a new pricing algorithm to minimize thePAR in aggregate load demand. The key challenge that we seek to address in Chapter 4is the energy provider’s uncertainty about the impact of prices on users’ load profiles, inparticular when users are equipped with automated ECC devices.Reverse Power FlowIntegrating more environmentally friendly RERs into the power grid is one of the mainfeatures of the smart grid. The renewable portfolio standard requires the utility companiesand energy providers in the United States and the United Kingdom to serve a specificminimum amount of their customers’ load with RERs [34]. RERs such as solar and windare non-dispatchable, since they are random in nature. In systems with high penetration ofRERs, the power may flow from the distributed generators (DGs) to the substation, whichnegatively impacts the stability of the system. If the reverse power flow exceeds a certainthreshold, it causes the voltage rise problem, which is a major challenge in integrating alarge number of DGs in the distribution network [35–37].To tackle the reverse power flow problem, it is desirable that users consume theirgenerating power locally rather than injecting the excess power back into the grid. Storagefacilities and DSM techniques can be adopted to shape the load pattern of the users tobetter match supply and demand [3, 4, 24–26, 38, 39]. That is, DSM techniques can beadopted to encourage users to shift their load to time slots with high generation fromRERs. In Chapter 5, we consider the problem of load scheduling in systems with highpenetration of RERs. To mitigate the problem of reverse power flow, we assume that usersare able to sell their excess power to other users. On the one hand, local power tradingcan benefit the users by providing monetary revenue for them. On the other hand, it helps7Chapter 1. Introductionto absorb excess power and to mitigate the reverse power flow problem.1.1.2 Related WorksConsidering the advances of AMI and two-way communication capabilities of smart grid, itbecomes possible to seek different objectives for the power grid. Examples of such objectivesinclude maximizing the social welfare, minimizing the electricity expenses of the users, andminimizing the PAR of the aggregate load. Li et al. [29] adopted the concept of utilityfunctions to quantify the amount of benefit that each user obtains from the operation ofdifferent appliances. They argued that the obtained benefit depends on the volume andthe pattern of the power consumption of the appliance. The authors proposed a schedulingalgorithm which maximizes the obtained benefit subject to various operational constraints.The authors in [40] also considered the benefit that each user obtains from different services.They proposed a control algorithm to schedule the available distributed energy resourcessuch that the obtained benefit is maximized. To tackle the computational complexity ofthe algorithm, particle swarm optimization is adopted to solve the corresponding problem.Conejo et al. [16] considered the problem of load scheduling to maximize the utility of theconsumer. They proposed a linear programming algorithm which takes into account theconstraints regarding the minimum daily energy requirements of the user, the minimumand the maximum load levels within a one hour time slot, and the ramping limits for suchload levels. A robust optimization technique is adopted to model the uncertainty about theprice values in each time slot. The authors in [12] proposed a load scheduling algorithmwhich attempts to achieve a trade-off between minimizing the electricity payment andminimizing the waiting time for the operation of the appliances. The proposed algorithmtakes into account the uncertainty about the price values in the upcoming time slots. Topredict the price values, a weighted average filter is adopted, and its coefficients are adjusted8Chapter 1. Introductionbased on real data. Kim et al. [41] considered the problem of power scheduling with priceuncertainty. The key assumption in [41] is that the price values are independent from theload level in each time slot. As a result, the algorithm in [41] is based on a Markov decisionprocess, where the decision on the operation of each appliance is made independently fromother appliances. The authors in [42] proposed a heuristic algorithm which schedules theoperation of the major appliances in a residential unit. The proposed algorithm benefitsfrom a simple implementation. Moreover, it tries to balance the user comfort and theconsumer price preferences. Xiong et al. [26] devised a scheduling algorithm which aimsto keep the total power consumption below a target value. The proposed setting in [26] issuitable for DSM programs in which due to the complexity of the algorithm a top-downcontrol approach is devised. That is, first, the total power consumption of each user in eachtime slot is determined. This is referred to as user level control. Then, each user tries toschedule the operation of its own appliances to meet the desired power consumption level.This is referred to as appliance level control. The authors in [30] proposed a multi-objectivescheduling algorithm. The proposed algorithm adopts binary particle swarm optimizationtechnique to schedule the operation of interruptible loads. The design aims to achieve thelevel of curtailment required by the system while satisfying the operational constraints ofthe interruptible loads. In addition, the proposed algorithm minimizes the joint paymentsof the users and the frequency of the load interruptions. In [43], Kishore et al. devised atwo-stage control algorithm. In the first stage, based on price values and the preferencesof the user, the operational schedule of different appliances is determined. In the secondstage, neighboring users coordinate to reduce the peak demand.Two-way communication capabilities of the smart grid makes it possible that usersand utility companies interact with each other to provide users with improved customerservices. Some of the works in the literature adopt game theoretic approaches to model9Chapter 1. Introductionthis interaction. Mohsenian-Rad et al. [11] devised a game theoretic approach to modelthe interaction between users. In their proposed system model, each user schedules its loadto minimize its energy expenses. On the other hand, the utility company adopts a timedifferentiating pricing tariff which also takes into account the aggregate load level of theusers. The price values are set by the utility company such that the generation cost or thePAR of the load is minimized. In [28], Chen et al. devised a Stackelberg game approach inwhich the energy provider acts as a leader and users are followers. The algorithm in [28]requires detailed information about users’ energy consumption needs. This design intendsto jointly maximize the social welfare of all users and the revenue of the energy provider.While most of the existing works focused on a scenario with a single utility company,the authors in [44] considered a system with multiple utility companies. In this study,the interaction between utility companies is modeled as a non-cooperative game, whilean evolutionary game model is adopted to model the interaction between the users. Theauthors also studied the criteria required for the convergence of both games. The authorsin [45] studied the impact of the consumers’ price elasticity on the performance of theelectricity market. In this study, users are modeled as agents who are well equipped withsmart grid technologies. The authors concluded that the impact of price elasticity dependson the price level at which users are consuming energy. Moreover, users can benefit moreif they are more price responsive.Concerns about environmental issues and the need to reduce greenhouse gas emissionshave attracted considerable attention to more environmentally friendly RERs. In theliterature, different DSM programs are proposed to deal with uncertainties associated withRERs. The authors in [46] considered the effects of storage units as independent entitieson the electricity market. They formulated the problem of selecting optimal energy andreserve bids for the storage units as a stochastic program that takes into account the10Chapter 1. Introductionfluctuations of market prices due to the random nature of RERs. In [47], to deal with theuncertainties associated with RERs in matching supply and demand, a bidding strategybased on robust optimization is proposed. The authors in [47] showed that as the forecasterror in the electricity price increases, the bidding strategy based on robust optimizationoutperforms the bidding strategy based on a deterministic approach. Kahrobaee et al.[48] proposed a system model in which users are modeled as independent agents makingrational decisions to buy, sell, or store electricity. To make such decisions, the agents takeinto account their current load and generation, and their expected load and generationin the upcoming time slots. The authors also showed that the objective of the users tominimize their electricity expenses is aligned with the objective of the energy provider toflatten the load curve. In [49], Yang et al. proposed a DSM program in which users areequipped with RERs. Each user schedules the operation of its appliances to minimize theelectricity payment. Moreover, users are able to sell their excess generation back to thegrid.1.2 Summary of Results and ContributionsThis thesis covers several algorithms for DSM. The results are divided into four chapters.The contributions in each chapter are as follows:• In Chapter 2, a DSM program is proposed to encourage efficient energy consumptionamong users. The proposed algorithm maximizes the aggregate utility of all users andminimizes the total cost imposed on the energy provider. We focus on systems whereusers are equipped with automated control units with an enhanced level of rationality.That is, users no longer accept the price as a fixed parameter and they can anticipatethe impact of their actions on price values. Moreover, we assume that users havelocal information, and this information is essential for social planner to achieve the11Chapter 1. Introductionmaximum social welfare. We propose a VCG mechanism to elicit local informationfrom rational users. We investigate some of the desired properties of our problemformulation including truthfulness, efficiency, and nonnegative transfer. We compareour efficient VCG DSM method with the case where users are price taker. We studythe differences of these two systems, especially from the user payment perspective,and show that for the VCG mechanism users have to pay less. Simulation resultsconfirm that both the users and the energy provider will benefit from the proposedscheme. The work in Chapter 2 is published in [50].• In Chapter 3, we propose a real-time residential load management algorithm. Theproposed algorithm takes into account the uncertainty about the future load demand,and it does not require the perfect knowledge of users’ energy needs. Our algo-rithm aims at minimizing the electricity payment of residential users. Our design ismulti-stage. As the demand information of the appliances is gradually revealed overtime, the operation schedule of controllable appliances is updated accordingly. Westudy operation constraints to model a variety of appliances including must-run ap-pliances, and interruptible and non-interruptible controllable appliances. Simulationresults show that our proposed scheduling algorithm with load uncertainty reducesthe energy payment of users compared to the case where no scheduling algorithm isadopted. Our proposed scheme also improves the overall power system performanceby reducing the PAR in aggregate load demand. The work in Chapter 3 is publishedin [51].• In Chapter 4, we address the problem of minimizing the PAR in the aggregateload demand through appropriately selecting price values for different time slots.The proposed algorithms take into account the uncertainty about the level of price-responsiveness of the users. We propose two iterative algorithms to be implemented12Chapter 1. Introductionin a price control unit (PCU) based on the information provided by the system simu-lator unit (SSU). The first algorithm, called finite-difference price selection (FDPS),uses a variation of the finite-difference technique [52] to approximate the gradient ofthe PAR minimization objective function. The second algorithm, called simultane-ous perturbation price selection (SPPS), is based on the simultaneous perturbationtechnique [52]. Moreover, an approximate dynamic programming scheme is proposedto simulate the likely behavior of the users in response to various price values atdifferent time slots. Simulation results show that our proposed pricing algorithmsreduce the PAR in aggregate load. In addition, we show that adopting the new pric-ing algorithms is also beneficial for the users if they are equipped with automatedcontrol units. The work in Chapter 4 is published in [53].• In Chapter 5, we focus on the problems of load scheduling and power trading insystems with high penetration of RERs. We consider a game theoretic approachto model the interaction of users with excess power generation. Users compete tosell their extra generation to other local users. The revenue of competing users de-pends on their own marginal cost and the offers advertised by other competing users.Thus, each competing user chooses its offered price and output generation such thatits revenue is maximized. We formulate the problem of selecting the offered price andoutput generation (i.e., the trading problem) as a linear mixed-integer program. Totackle the complexity of the trading problem, we adopt the generalized Benders’ de-composition approach. Moreover, an approximate dynamic programming approach isadopted to schedule the operation of different types of appliances including must-runappliances, and interruptible and non-interruptible controllable appliances. Simula-tion results show that our proposed algorithm reduces the energy payment of userscompared to the case where scheduling is not applied. Our proposed scheme fa-13Chapter 1. Introductioncilitates the integration of RERs and mitigates the reverse power flow problem byproviding the users an opportunity to trade their excess generation locally. The workin Chapter 5 has been submitted for publication in IEEE Transactions on SmartGrid.The VCG mechanism proposed In Chapter 2 is a user level control algorithm. Thatis, this algorithm does not aim to schedule the operation of individual appliances, andthe details of the power consumption of each appliance are hidden from the proposedalgorithm. The load control algorithm proposed in Chapter 3 schedules the operation ofindividual appliances. Moreover, the proposed algorithm takes into account the operationalconstraints of different types of appliances. Thereby, we assume that the price values fordifferent time slots are determined by the energy provider, and are known at the userside. The idea developed in Chapter 3 is extended in Chapter 4, where we address thequestion of how to determine the price values for each time slot. In Chapter 5, we focuson systems where most of the users are equipped with RERs. The load scheduling andtrading algorithm proposed in Chapter 5 reduces the reverse power flow which is a mainbarrier for utilizing the RERs.1.3 Thesis OrganizationThe rest of the thesis is organized as follows. In Chapter 2, we propose a VCG mechanismfor DSM in the future smart grid. The proposed mechanism aims to maximize the aggregateutility of all users while minimizing the total cost of power generation. We investigatesome of the main properties of the proposed mechanism such as truthfulness, efficiency,and nonnegative transfer. In Chapter 3, we propose an optimal residential load controlalgorithm for DSM in presence of load uncertainty. We formulate an optimization problemto minimize the electricity payment of the users in situations where only an estimate of14Chapter 1. Introductionthe future demand is available. We focus on a scenario where real-time pricing is combinedwith IBRs to balance residential load to achieve a low PAR. In Chapter 4, we propose twopricing algorithms based on stochastic approximation technique to minimize the PAR ofthe aggregate load. The proposed algorithms eliminate the need to know the structure ofthe objective function. In our proposed pricing algorithms, we take into account the wayusers will respond to different price values. We also consider the effect of control decisionsof the ECC unit on the users’ load profile. In Chapter 5, we propose a load controlalgorithm for DSM. We consider the problem of joint load scheduling and power trading.An approximate dynamic program is proposed to schedule the operation of different typesof appliances. Furthermore, we adopt a game theoretic approach to model the interactionof users with excess power generation. Users with excess power generation choose theiroffered price and output generation such that they obtain a larger share of the marketand their revenue is maximized. Finally, the thesis is concluded and some potential futurework is introduced in Chapter 6. Each of the main chapters in this thesis is self-containedand included in separate journal articles or conference papers. The notations are definedseparately for each chapter.15Chapter 2Demand Side Management UsingMechanism Design2.1 IntroductionAs discussed in Chapter 1, in this chapter, we focus on developing a novel pricing methodfor DSM to encourage efficient energy consumption among users to achieve certain socialobjectives. However, it is difficult because of its computational complexity to achievethese social objectives, if all appliances of all users are to be jointly scheduled. To tacklethis problem, a top-down control approach is devised. That is, first, the total powerconsumption of each user in each time slot is determined. This is referred to as user levelcontrol. Then, each user tries to schedule the operation of its own appliances to meet thedesired power consumption level. This is referred to as appliance level control [26, 54]. Inthis chapter, we consider the problem of scheduling the total power consumption of eachuser at different time slots. We show that achieving social objectives is challenging even inuser level control and requires collecting various information about the energy consumptionbehavior of the users, the price elasticity of the users, and the benefit that each user obtainsby consuming a certain amount of energy. However, in general, users are not willing toreveal such information, unless there is an incentive for them to do so. Therefore, elaboratedesign rules (mechanisms) are needed such that it is in each user’s self interest to revealits local information. This problem has already been considered for smart grid [55] and in16Chapter 2. DSM Using Mechanism Designother contexts such as in telecommunication networks [56–58]. However, the prior worksassumed that users are price taker who accept the prices as fixed parameters. That is,they do not consider the possibility that their actions may affect the price. For systemswith built-in automated control units, this assumption may no longer be valid. Therefore,here, we consider the case where users can anticipate the impact of their actions on pricevalues.VCG mechanism is a pricing method to elicit local information from rational users.For determining the price charged to each user, users are asked to declare their energydemand information. The payments of the users are then structured such that the usershave incentive to declare their local information truthfully. We note that the VCG pricingmechanism has already been applied to resource management problems, e.g., in computerand communication networks [56]. However, since we consider a different problem formu-lation in the context of smart grid, many of the existing results, e.g., in [56] and [59], arenot directly applicable and need to be revised as will be explained throughout this chapter.The contributions of this chapter are summarized as follows:• We propose a VCG mechanism for DSM programs to encourage efficient energyconsumption among users. In our system model, each user reveals its demand in-formation to the energy provider. By running a centralized mechanism, the energyprovider computes the optimal energy consumption level for each user, and advertisesa specific electricity payment for each user.• We formulate an optimization problem to maximize the aggregate utility of all userswhile minimizing the total cost imposed on the energy provider.• We investigate some of the desired properties of our problem formulation. First,truthfulness and efficiency of the proposed mechanism are proved. Then, for our17Chapter 2. DSM Using Mechanism Designmodel, we show the property of nonnegative transfer which means that the usersalways make nonnegative payments.• We compare our efficient VCG DSM method with the case where users are price taker.We study the differences of these two systems, especially from the user paymentperspective, and show that for the VCG mechanism users have to pay less.• Simulation results confirm that both the users and the energy provider will benefitfrom the proposed scheme.The rest of this chapter is organized as follows. The system model and problem for-mulation are presented in Section 2.2. The VCG mechanism and its different propertiesare discussed in Section 2.3. In Section 2.4, we provide a performance evaluation of theproposed pricing scheme, and the chapter is summarized in Section 2.5.2.2 System Model and Problem Formulation2.2.1 Power SystemAs in [11, 60, 61], we consider a smart power system with a single energy provider andseveral load subscribers or users as part of the general wholesale electricity market as shownin Fig. 2.1. For each user, we assume that there is an ECC unit which is embedded inthe user’s smart meter. The role of the ECC is to control the user’s power consumption,and to coordinate each user with the energy provider. All ECC units are connected to theenergy provider through a communication infrastructure such as a local area network.The intended time cycle for the system’s operation is divided into K time slots, whereK , |K|, and K is the set of all time slots. This division can be based on the behaviorof the users and their power demand pattern: on-peak time slots, off-peak time slots, and18Chapter 2. DSM Using Mechanism DesignFigure 2.1: An illustration of the regional energy providers, several users, and multiplepower generators as parts of the general wholesale energy market.mid-peak time slots. Let N denote the set of all users and N , |N |. In each time slot, weclassify the load demand into two types, must-run loads and controllable loads [40]. Must-run loads are price-inelastic. For example, a refrigerator always needs to be on during theday. On the other hand, controllable loads can be stopped, adjusted, or shifted to othertime slots and include the demand for services such as charging PHEVs. In each time slotk, we use Mkn and mkn to denote the maximum and minimum power level for each user n,respectively. We use Mn , (M1n , . . . ,MKn ) and mn , (m1n, . . . , mKn ) to denote the vectorsof the maximum and minimum power levels of user n in all time slots, respectively. We alsodefine M , (M1, . . . ,MN ) and m , (m1, . . . ,mN). We denote the minimum total energyrequirements of user n as En and the vector of the minimum total energy requirements of allusers as E , (E1, . . . , EN), where for each user n, we have En ≥∑k∈Kmkn. For the users,it is difficult to determine their required demand information, i.e., the minimum and themaximum power requirement in each time slot, the minimum total energy requirement,and the benefit obtained by consuming a certain amount of energy. However, machinelearning and stochastic signal processing techniques can be adopted in each user’s ECCunit to help the user determine its required demand information. The normal pattern ofthe users’ power consumption can be fed into appropriate machine learning algorithms toextract the demand information of the users. In order to provide the required energy for19Chapter 2. DSM Using Mechanism Designeach user n within the operation cycle, it is required that∑k∈Kxkn ≥ En, (2.1)where xkn is the power consumption level of user n in time slot k. Furthermore, we definexn , (x1n, . . . , xKn ) as the vector of energy consumption of user n. The feasible energyconsumption controlling set of user n is defined asXn ,{xn∣∣∑k∈Kxkn ≥ En, mkn ≤ xkn ≤Mkn , ∀ k ∈ K}. (2.2)Our key assumption is that users have price-elastic load. That is, they may shift or changetheir energy consumption in response to price values [62–64].2.2.2 User Preference and Utility FunctionEach user is assumed to be an independent decision maker. The energy demand of eachuser may vary based on different parameters. For example, we can take into accountthe climate conditions and the price of electricity. The energy demand also depends onthe type of the users. Residential users may have different responses to the same pricethan industrial users. Even users within the same category may not be identical. Thedifferent responses of different users to various price scenarios can be modeled by usingutility functions from microeconomics [65]. In fact, we can model the behavior of differentusers through their different choices of utility functions [66]. For each user n, we representthe corresponding utility function as Un(∑k∈K xkn) , U(∑k∈K xkn, ωn), where xkn is thepower consumption level of user n in time slot k and ωn is a parameter, which may varyamong users, representing the value of electricity for each user. For each user, the utilityfunction represents the level of satisfaction obtained by the user as a function of its total20Chapter 2. DSM Using Mechanism Designpower consumption throughout the operation period1.For all the users, we define ω , (ω1, . . . , ωN). We assume that the utility functionsU(x, ω) satisfy the following properties:Property 2.1 Utility functions are non-decreasing. This implies that the marginal benefitis nonnegative:∂U(x, ω)∂x ≥ 0. (2.3)Property 2.2 The marginal benefit of users is a non-increasing function. That is,∂2U(x, ω)∂x2 ≤ 0. (2.4)In other words, the utility functions are concave. While the class of utility functions thatsatisfy (2.3) and (2.4) is very large, it is convenient to have a linear marginal benefit [66],[69].Property 2.3 For a fixed consumption level x, a larger ω gives a larger U(x, ω), whichcan be expressed as∂U(x, ω)∂ω > 0. (2.5)Property 2.4 When the consumption level is zero,U(0, ω) = 0, ∀ω > 0. (2.6)1The value of electricity for the users may also vary at different times of a day. Large loads thatparticipate in wholesale electricity markets discriminate the value of electricity in different time slotsthrough their different choices of utility functions at different times of a day [67, 68]. Considering theadvances in home automation systems, it is conceivable that in the near future, instead of specifying onlythe value of their total power consumption, residential users will be able to determine the value of electricityfor each time slot. In that case, the utility function of each user n can be replaced by∑k∈K U˜kn(xkn), whereU˜kn(·) is the utility function of user n in time slot k.21Chapter 2. DSM Using Mechanism DesignWe note that the operation of each individual appliance is meant to achieve a goal or tofinish a task. For example, the air conditioning system is used to keep the temperature ina predetermined range. Thus, the total power consumption of each user can be consideredas the aggregate power consumption required to complete different tasks. In this chapter,since we define the utility functions for the aggregate load of different tasks, rather than forthe power consumption of each individual appliance, the utility functions do not decrease.This is because users can complete more tasks if they consume more power. Furthermore,it is reasonable to assume that users prioritize their tasks. Therefore, as the prices increase,they tend to ignore some less important tasks or switch to a different mode of operation withlower power consumption. This implies a decreasing marginal benefit and a concave andincreasing utility function for the total power consumption of different tasks. In addition,we assume that users are able to specify how much they value energy through the properchoice of parameter ω, i.e., a higher ω implies a higher utility value. Finally, as utilityfunctions quantify the level of satisfaction of the users, intuitively zero power consumptionshould result in a zero utility value. Recent reports indicate that the behavior of powerusers can indeed be accurately modeled by certain utility functions [69]. In this chapter,we consider quadratic utility functions corresponding to linearly decreasing marginal benefit[15]:U(x, ω) =ωx− α2x2, if 0 ≤ x < ωα ,ω22α , if x ≥ ωα ,(2.7)where α is a pre-determined parameter. A few example utility functions from this classare shown in Fig. 2.2. The point where the utility function gets saturated and does notchange corresponds to the maximum power requirement of the user.22Chapter 2. DSM Using Mechanism Design0 0.5 1 1.5 200.511.5Amount of Power Consumption (kW)Utility / Marginal Benefit  Utility Function (ω = 1)Utility Function (ω = 0.5)Utility Function (ω = 0.3)Marginal Benefit Function (ω = 0.3)U(x,ω)Figure 2.2: Sample utility functions for power users (α = 0.3).2.2.3 Energy Cost ModelWe consider a cost function Ck(Lk) indicating the cost of providing Lk units of energyoffered by the energy provider in each time slot k. We make the following assumptions:Assumption 2.1 The cost functions are increasing with respect to the total offeredenergy capacity.Assumption 2.2 The cost functions are strictly convex.Assumption 2.3 There exists a differentiable, convex, nondecreasing function pk(q) overq ≥ 0 for each k ∈ K, with pk(0) ≥ 0 and pk(q) → ∞ as q → ∞, such that for q ≥ 0Ck(q) =∫ q0pk(z)dz. (2.8)Note that quadratic functions are among several practical examples for cost functionsthat satisfy Assumptions 2.1-2.3, and are considered throughout this chapter [11, 70]:Ck(Lk) = akL2k + bkLk + ck, (2.9)23Chapter 2. DSM Using Mechanism Designwhere ak > 0, bk ≥ 0, and ck ≥ 0 are fixed parameters.2.2.4 Problem Formulation and Efficient AllocationsIn this section, we consider the problem of power consumption level selection. From a socialfairness point of view, it is desirable to utilize the available generated power provided by theenergy provider in such a way that the sum of the utility functions of all users is maximizedand the cost imposed on the energy provider is minimized. If centralized control is feasibleand we can collect all information about the users’ utility functions, an efficient energyconsumption schedule can be characterized as the solution of the following problem:maximizexn∈Xn, n∈N∑n∈NUn(∑k∈Kxkn)−∑k∈KCk(∑n∈Nxkn), (2.10)where xn is the vector of power consumptions of user n, Un(·) is as in (2.7), and Ck(·) isdefined in (2.9). The objective function in problem (2.10) is the sum of all utility functionsminus the total energy cost in the system.Problem (2.10) is a concave maximization problem and can be solved in a centralizedfashion using convex programming techniques such as the interior point method (IPM) [71].Since it is assumed that parameters ωn, mn, Mn, and En for each user n are local infor-mation, the energy provider may not have sufficient information to solve problem (2.10).Each user aims to optimize its local objective. To align these individual objectives withthe social objective, some elaborately designed pricing scheme is needed. In general, usersmay have different approaches in responding to the price values set by the energy provider.This can lead to different equilibriums among users. We are interested in analyzing com-petitive equilibrium and Nash equilibrium. In competitive equilibrium, each user acts as aprice taker. That is, it does not consider the effect of its actions on the price. However, inNash equilibrium, we assume that users are price anticipator, i.e., they consider the effect24Chapter 2. DSM Using Mechanism Designof their actions on the price set by the energy provider.Price Taking UsersIf users are price taker, i.e., they do not consider the effect of their actions on the price, thenwe need to analyze the competitive equilibrium among the users and the energy provider.Given a price vector λ = (λ1, . . . , λK), where λk is the price in time slot k, a user whoconsumes xkn kW electricity in time slot k is charged λkxkn dollars for that time slot. Sinceusers treat the prices as fixed values, the payoff function for each user n becomesPn(xn) = Un(∑k∈Kxkn)−∑k∈Kλkxkn, (2.11)where the first term represents the utility of user n as a function of its power consumption,and the second term represents its payment to the energy provider.We call a pair (x,λ), where x , (x1, . . . ,xN), a competitive equilibrium if each user nmaximizes its own payoff function defined in (2.11) for a given price vector λ, i.e.,Pn(xn) ≥ Pn(x¯n), x¯n ∈ Xn, n ∈ N , (2.12)where vector x is the solution to the problem defined in (2.10). It has been shown thatunder Properties 2.1-2.4 and Assumptions 2.1-2.3, a competitive equilibrium always exists[55, 72], and the results are summarized in the following proposition.Proposition 2.1 There exists a competitive equilibrium (x,λ), where x is an optimalsolution to problem (2.10).The assumption that users are price taker is usually considered when the number ofusers is large, the amount of information provided to each user is limited, and the computerprograms running the decentralized algorithm are embedded in the computer operating25Chapter 2. DSM Using Mechanism Designsystem and are not tampered with by the vast majority of the users. However, as someindividual users such as large industrial users may have a significant impact on the powersystem, or some parts of the power system may act autonomously as in microgrids forhousehold users in which the number of users is much lower than the number of usersin the whole grid, the price taking assumption may not always be valid. When the pricetaking assumption is violated, the model changes into a game, and the assumptions requiredfor the validity of Proposition 2.1 do not hold. We investigate this scenario in the nextsub-section.Price Anticipating UsersIf users are price anticipator, i.e., they do consider the effect of their actions on the price,then we need to analyze the Nash equilibrium of the game which is played among mul-tiple users who compete for the available power provided by the energy provider. Inthis game theoretic model [73], the strategies of the users represent their power con-sumption level. We consider the following pricing scheme for resource allocation. Givenx = (x1, . . . ,xN), the energy provider sets a single price µk(x) = pk(∑n∈N xkn) for timeslot k. User n then pays xknpk(∑n∈N xkn) for that time slot. We use the notation x−nto denote the vector of all consumption powers chosen by users other than user n, i.e.,x−n = (x1, . . . ,xn−1,xn+1, . . . ,xN). Then, given x−n, the payoff of each user n is obtainedasQn(xn;x−n) = Un(∑k∈Kxkn)−∑k∈Kxknpk(∑m∈Nxkm). (2.13)The payoff function Qn is similar to Pn, defined for price-taking users in (2.11). Theonly difference is that while the payoff function Pn takes the price λk as a fixed parameter,price anticipating users realize that the price is set according to pk(∑m∈N xkm), and adjusttheir payoffs accordingly.26Chapter 2. DSM Using Mechanism DesignFrom (2.13), the payoff of each user depends on its power consumption as well as thepower consumptions of other users. Hence, we have the following game among the users:• Players: Registered users in set N .• Strategies: Each user n ∈ N selects its energy consumption level xn ∈ Xn to maxi-mize its payoff.• Payoffs: Qn(xn;x−n) for each user n ∈ N as in (2.13).A Nash equilibrium of the game defined by (Q1, . . . , QN) is a vector x such that for alln ∈ N ,Qn(xn;x−n) ≥ Qn(x¯n;x−n), x¯n ∈ Xn. (2.14)It can be shown that a Nash equilibrium exists for this game, and the results aresummarized in the following proposition. However, the details of the proof can be foundin [73].Proposition 2.2 Suppose that Properties 2.1-2.4 and Assumptions 2.1-2.3 hold. Thereexists a Nash equilibrium x for the game defined by (Q1, . . . , QN).In general, the Nash equilibrium of a resource allocation game may not be optimal[73, 74]. That is, the energy consumption profile obtained at the Nash equilibrium in adistributed pricing scenario may not necessarily be the same as the optimal solution ofthe optimization problem in (2.10). Next, we investigate how the price values can be setcarefully by the utility company such that the system performance becomes optimal at theaforementioned Nash equilibrium.27Chapter 2. DSM Using Mechanism Design2.3 Applying the Vickrey-Clarke-Groves MechanismIn the previous section, we considered a method (mechanism) which uses only a singleprice in each time slot for all users to allocate the provided power. Despite its simplic-ity, the introduced mechanism suffers from a loss in efficiency if users are indeed priceanticipator, and evaluate the effect of their actions on the price function. As mentionedbefore, the main obstacle in solving problem (2.10) is the lack of information about theutility functions of the users and their feasible set of power consumptions. However, if weremove the restriction that the mechanism only chooses a single price, we can elicit thelocal information of the users. One possible approach to convince users to declare theirutility functions and constraint parameters truthfully is the VCG mechanism [75].2.3.1 VCG MechanismIn the VCG class of mechanisms, each user is asked to specify its feasible set of powerconsumption and its utility function, which in case of the utility functions in (2.7) reducesto revealing a utility parameter ωn. For each user n, we use Un(∑k∈K xkn) , U(∑k∈K xkn, ωn)and Uˆn(∑k∈K xkn) , U(∑k∈K xkn, ωˆn) to denote the true and declared utility function andXn and Xˆn to denote the true and declared feasible set of power consumptions, respectively.We defineIn , {ωn,Mn,mn, En} (2.15)andIˆn , {ωˆn, Mˆn, mˆn, Eˆn} (2.16)to denote the true and declared demand parameters, respectively, where ωˆn, Mˆn, mˆn, andEˆn are the declared values for ωn, Mn, mn, and En, respectively. For notational simplicity,28Chapter 2. DSM Using Mechanism Designwe also defineI , {ω,M,m,E} (2.17)andIˆ , {ωˆ, Mˆ, mˆ, Eˆ}, (2.18)where ωˆ, Mˆ, mˆ, and Eˆ are the declared values for vectors ω, M, m, and E, respectively.If user n has a consumption vector xn, but has to pay tn, then the payoff function of usern isUn(∑k∈Kxkn)− tn. (2.19)On the other hand, the social objective is in the form ofUn(∑k∈Kxkn)+∑m∈N−nUm(∑k∈Kxkm)−∑k∈KCk(∑m∈Nxkm), (2.20)where N−n is the set of all users except user n. For a given vector of declared demandinformation Iˆ, the VCG mechanism chooses the energy consumption allocation x(ˆI) as anoptimal solution to problem (2.10) and calculates optimal energy consumption vectors asx(ˆI) = argmaxxn∈Xˆn, n∈N{∑n∈NUˆn(∑k∈Kxkn)−∑k∈KCk(∑n∈Nxkn)}, (2.21)and the payments are structured such thattn(ˆI) = −∑m∈N−nUˆm(∑k∈Kxkm)−∑k∈KCk(∑m∈Nxkm)+ hn(Iˆ−n), (2.22)where hn is an arbitrary function of Iˆ−n, i.e., the declared demand information of the userswith user n excluded from the system. The true demand information of the users other29Chapter 2. DSM Using Mechanism Designthan n is denoted by I−n. The definition of the payments in (2.22) aligns user objectiveswith the social planner’s objective.Remark 2.1 We note that the information in (2.15) is similar to the type of informa-tion submitted by large purchasers of electricity in a wholesale electricity market. Eachpurchaser in a wholesale electricity market makes a day-ahead bid based on its demandcurve. However, in contrast to (2.21) and (2.22), the power share of each purchaser and theprice of electricity in day-ahead markets are determined by clearing the demand againstthe supply offers. The dispatch of the power is then balanced in real-time on the day ofdispatch [67, 68]. As a result, the proposed schemes in this chapter can find interestingapplications also in the wholesale electricity market.Remark 2.2 We note that the VCG energy allocation in (2.21) determines the optimumlevel of energy consumption for the users in each time slot. However, in practice, therealization of random events can influence the level of energy consumption of the users.In this case, each user can be penalized by the energy provider for any deviation from theallocated level of energy consumption.The cost term Ck(·) in (2.20) couples the consumption power variables of all users x.This term makes the whole problem not only a utility maximization but also a cost min-imization problem, and thus, the system objective is different from the normal objectiveof VCG mechanisms studied in other contexts [56, 76, 77]. These changes in our prob-lem formulation require the verification of some desired properties of the proposed VCGmechanism for the new scenario. To this end, we make the following proposition.Proposition 2.3 If the VCG mechanism defined in (2.21) and (2.22) is used to selectelectricity payment values, then declaring Iˆn = In is a dominant strategy for each user n,and following this strategy results in an efficient allocation.30Chapter 2. DSM Using Mechanism DesignThe proof of Proposition 2.3 is given in Appendix A. Proposition 2.3 highlights twomain features of the proposed VCG mechanism. First, the payment of each user is struc-tured such that regardless of other users’ strategies, the intended user cannot do betterthan truthfully declaring its demand information. This feature significantly reduces thecommunication requirements of the method and eliminates the need for interaction amongusers. Second, if all users declare their demand truthfully, the proposed VCG system re-sults in an efficient system, i.e., the utilities of all users are maximized and the cost imposedon the energy provider is minimized. For the following, we need to determine function hnintroduced in (2.22). Here, we will use a popular choice for this function which is referredto as Clarke tax [75],hn(ˆI−n) =∑m∈N−nUˆm(∑k∈Kxkm(ˆI−n))−∑k∈KCk(∑m∈N−nxkm(ˆI−n)), (2.23)where x(ˆI−n) is the VCG allocation choice in (2.21), but when user n is excluded from thesystem. Thus, the payment of user n istn(ˆI) =−∑m∈N−nUˆm(∑k∈Kxkm(ˆI))−∑k∈KCk(∑m∈Nxkm(ˆI))+∑m∈N−nUˆm(∑k∈Kxkm(ˆI−n))−∑k∈KCk(∑m∈N−nxkm(ˆI−n)). (2.24)The payment of user n is the difference in the social welfare of the other users with andwithout the presence of user n.31Chapter 2. DSM Using Mechanism Design2.3.2 VCG Mechanism and Nonnegative TransferIn general, if users can serve as a source of electricity at some time instances during theday, e.g., because they have local generation capability or they can transfer the powerstored in their local batteries back to the grid, then such users may receive paymentsfrom the grid. Such payments can also be interpreted as negative payments made by theusers. However, in the problem formulation considered in this chapter, since users areonly electricity consumers, this case does not arise, and the users’ payments to the gridare always nonnegative. We will refer to this property as nonnegative transfer. In thefollowing theorem, we show that for our problem formulation the nonnegative transferproperty holds.Theorem 2.1 Suppose Properties 2.1-2.4 and Assumptions 2.1-2.3 hold. Then, the VCGmechanism in (2.21) and (2.24) has the property of nonnegative transfer.The proof of Theorem 2.1 is given in Appendix B.2.3.3 VCG Mechanism and Market Clearing PriceThe following theorem shows that the electricity payment of each user in the proposedVCG mechanism is less than its payment in a system which has price taking users anduses marginal cost pricing, i.e., the λ term in Proposition 2.1.Theorem 2.2 Suppose Properties 2.1-2.4 and Assumptions 2.1-2.3 hold. For the VCGmechanism in (2.21) and (2.24), the payment of each user is tn ≤∑k∈K λ∗kxkn(I), whereλ∗=(λ∗1, . . . , λ∗K) is the vector of market clearing prices for problem (2.10).The proof is based on the assumptions that the utility functions are concave and thecost function is convex. Optimality conditions of the VCG allocation (2.21) are adopted to32Chapter 2. DSM Using Mechanism Designrelate the VCG payment of each user to the market clearing price. The proof of Theorem2.2 can be found in Appendix C.2.4 Performance EvaluationIn this section, we present simulation results and assess the performance of our proposedmechanism and the impact of different system parameters. In our simulations, we assumethat all users have concave quadratic utility functions as described in (2.7), where param-eter α is chosen as 0.5. We set the parameters of the cost function in (2.9) for each timeslot to ak > 0, bk = 0, and ck = 0.2.4.1 Performance Gains from Real-time Interaction with UsersTo have a baseline scheme to compare with, we consider a peak load pricing (PLP) methodin which the price value for each time slot is calculated based on the average power con-sumption of the users in each time slot to maximize the payoff of the energy providerwhich is its revenue minus total energy cost. For the PLP method, we assume that theenergy provider has some prior information about the distribution of parameter ω of theusers. Here, we assume a uniform distribution. We assume there are N =50 users. Weconsider K=24 representing a 24-hour period. Parameter ω of each user is selected fromthe set {5, 6, . . . , 15}. However, random events are modeled via a small perturbation inthe ω value of each user. We set the parameter ak of the cost function equal to 0.02, 0.3,and 0.5 for off-peak, mid-peak, and on-peak hours, respectively. We assume that each userhas a minimum required energy in each operation period, En, which varies from 9 kWhto 21 kWh. The minimum power requirements of each user in each time slot, mkn, areset on average to 0.1 kW, 0.5 kW, and 1 kW for off-peak, mid-peak, and on-peak hours,respectively.33Chapter 2. DSM Using Mechanism Design1 8 18 24020406080PLP Pricing MethodTime (Hour)Load (kW)1 8 18 240102030405060VCG MethodTime (Hour)Load (kW)Figure 2.3: Power consumption for the proposed VCG method and a peak load pricing(PLP) method.As illustrated in Fig. 2.3, the proposed VCG mechanism improves the performance ofthe system not only by reducing the power consumption of users but also by reducing thePAR from 1.51 to 1.21.2.4.2 The Impact of Reflecting the Generating CostThe proposed VCG mechanism is used to maximize the social welfare. Maximizing theaggregate utility of all users while minimizing the cost imposed on the energy provider isbeneficial for both users and energy provider. The opportunity of reflecting the fluctua-tions of the wholesale price into the customer side is one of the main advantages of theproposed VCG mechanism. This aspect becomes more important in situations where thecost imposed on the energy provider is high. To have a baseline scheme to compare with,we consider a system which has price anticipating users and employs marginal cost pricing.It has been shown that in a system with price taking users, marginal cost pricing not only34Chapter 2. DSM Using Mechanism Designmaximizes the social welfare, but also maximizes the payoff of the energy provider [55].As an upper bound on the payoff of the energy provider, we consider a system which hasprice taking users and employs marginal cost pricing. We assume there are 50 users, andparameter ω of each user is selected from the set {15, 25, 30, 40}. We assume that for eachuser n, parameter En varies from 10 kWh to 15 kWh and for different time slots, parametermkn is set on average to 0.1 kW, 0.5 kW, and 1 kW for off-peak, mid-peak, and on-peakhours, respectively.Furthermore, we assume that parameter ak of the cost function is constant in all threetime slots. The payoffs of the energy provider for the proposed VCG system, the systemwith price anticipating users, and the system with price taking users for different valuesof parameter ak of the cost function are presented in Fig. 2.4. We can see that, since theVCG payment (2.24) is structured to consider the cost imposed on the energy provider, thepayoff of the energy provider is higher compared to the system with price anticipating users.Note that the proposed VCG system and the price taking system are both efficient systemswith the same power allocation. Hence, they have the same total power consumption.2.4.3 Communication Requirements of the VCG SystemThe communication requirements are among the main aspects considered for any pricingmethod. In this section, the number of messages exchanged between users and also theenergy provider is considered as a measure to compare the proposed VCG system with asystem which has price anticipating users. In the VCG system, each user is asked to declareits parameter ω and its feasible set of power consumption to the energy provider, and inreturn, the energy provider determines the payment and the allocated power of each user.In practice, it may be preferable for the users to communicate only with a trusted entitysuch as the energy provider. However, when users are price anticipator, they form a game35Chapter 2. DSM Using Mechanism Design0.02 0.025 0.03 0.035 0.04 0.045 0.05102104106108110112114116118Parameter aPayoff of the Energy Provider (Dollars)  System with Price Taking UserVCGSystemSystem with Price Anticipating UserFigure 2.4: Payoff of the energy provider for the proposed VCG system, the system withprice anticipating users, and the system with price taking users.and have to exchange messages with each other. Communication requirements become animportant feature specially in situations where the cost imposed on the energy provideris low, and most of the users can compete in the power consumption game. In a systemwhere users are price anticipator, we use the myopic best-response algorithm [75, Ch. 6] tocompute the Nash equilibrium. In this system, each user informs other users whenever itchanges its power consumption. Each time one of the users updates its power consumptioninformation, a message is sent. We set the parameter ak of the cost function equal to 0.02,0.3, and 0.5 for off-peak, mid-peak, and on-peak hours, respectively. We assume that foreach user n, parameter En varies from 10 kWh to 20 kWh and for different time slots,parameter mkn is set on average to 0.1 kW, 0.5 kW, and 1 kW for off-peak, mid-peak, andon-peak hours, respectively.The average number of messages exchanged between the various entities in the VCGsystem and the system with price anticipating users for K =24 is presented in Table 2.1.As illustrated in Table 2.1, the method used in the system with price anticipating users36Chapter 2. DSM Using Mechanism DesignTable 2.1: Average number of exchanged messages in VCG system and system with priceanticipating users.Number of Users N Price Anticipating System VCG System10 42767 2020 79624 4030 87808 6040 135290 8050 145718 100requires much more message exchanges to converge than the VCG mechanism.2.4.4 Effect of Parameter ωIn this section, we explore the effect of parameter ω on different aspects of the power systemfor N = 50 users and K = 3 time slots. In this regard, we mainly focus on the powerconsumption of the system and the payments of the users. To understand how changes inthe parameter ω of a single user can affect others, we consider the same ω for all the usersand change it for the first user starting from 5 while keeping this parameter fixed equal to20 for the other users. We set parameter ak of the cost function equal to 0.02 for all timeslot. For each user n, parameter En selected to be 12, and parameter mkn is set to zero forall time slots.The simulation results for the power consumption of the users are presented in Fig.2.5. We notice that as we increase the ω of the first user, the power consumption of theother users decreases until they reach their minimum power requirements. Intuitively,as the first user values energy more by increasing its ω value, it has a negative impacton the power consumption of its rivals in the system. For the VCG mechanism, thepayments of the users are closely related to their power consumption, i.e., as the firstuser increases its ω, the power consumption of the other users reduces as well as theiraggregate payment until they reach the point where they consume their minimum power37Chapter 2. DSM Using Mechanism Design50 100 150 200 250 300 350 400 450 50001002003004005006007008009001000ω Parameter of the First UserPower Consumption of Users (kW)  Other UsersFirst UserFigure 2.5: Power consumption of the first user and aggregate power consumption of otherusers when ω of the first user is increased.requirements. After reaching this point, as they have a guaranteed amount of powerconsumption, their aggregate payment increases.2.4.5 Exploring the Truthfulness PropertyTruthfulness in dominant strategy for the proposed VCG mechanism means that regardlessof other users’ strategy, the intended user cannot do better than truthfully declare itsdemand information. In this section, we consider a system where there are N=10 usersand K = 3 time slots. We set parameter ak of the cost function equal to 0.02 for alltime slot. For each user n, parameter En is equal to 15 kWh and for different time slots,parameter mkn is set to zero for all time slots. We assume the true ω parameter of theusers is ω = [12, 6, 8, 8, 10, 10, 12, 12, 16, 20] and E1=15. We explore the best response ofthe first user while other users declare their demand information truthfully. As illustratedin Fig. 2.6, the considered user (first user) with ω1=12 and E1=15 cannot do better thantruthfully declare ωˆ1=12 and Eˆ1=15.38Chapter 2. DSM Using Mechanism Design81216202401020304050−50050100Declaredωˆ1X: 12Y: 15Z: 90.9Declared Eˆ1Payoff(Cents)Figure 2.6: The payoff of the first user for different values of declared ωˆ1 and Eˆ1 (the trueω1 is equal 12 and the true E1 is equal 15).2.5 SummaryIn this chapter, we proposed a VCG mechanism for DSM in the future smart grid. Theproposed mechanism aims to maximize the aggregate utility of all users while minimizingthe total cost of power generation. We investigated some of the main properties of theproposed mechanism such as truthfulness, efficiency, and nonnegative transfer. Throughsimulation, we showed that the proposed VCG mechanism improves the performance ofthe system by encouraging users to reduce their power consumption and shift their loadsto off-peak hours. The proposed VCG mechanism significantly reduces the communicationoverhead. We also analyzed the impact of some key parameters on our model throughsimulations. The simulations confirmed that by using our proposed VCG mechanism, inaddition to maximizing the social welfare, the energy provider can benefit as well.39Chapter 3Energy Consumption Schedulingwith Load Uncertainty3.1 IntroductionAs discussed in Chapter 1, despite its importance, the effect of load uncertainties onDSM has not been well-studied in the smart grid literature [11, 16, 29, 40, 41, 78–81].In this chapter, we focus on developing a novel automated optimization-based residentialload scheduling algorithm in a retail electricity market with load uncertainties. We aimto minimize each user’s electricity payment by optimally scheduling the operation of itsappliances in real-time, subject to the operational constraints defined by the users. As in[12], we adopt RTP combined with IBR to better reflect the fluctuation of the wholesaleelectricity prices and to avoid load synchronization.Our design can be partly compared with [41]. The problem tackled in this chapter isdifferent from that in [41] in two aspects. First, the work in [41] addresses uncertaintyin price values while we tackle uncertainty in load and users’ energy consumption needs.Second, the key assumption in [41] is that the price values are independent from the loadlevel in each time slot. Here, we relax this assumption. Our work is also different from theheuristic home automation schemes in [26, 42], as we use an optimization-based approachwith elaborate mathematical modeling and take into account estimates of the future loadto make better decisions. The contributions of this chapter can be summarized as follows:40Chapter 3. Energy Consumption Scheduling with Load Uncertainty• We propose a real-time residential load management algorithm with load uncertaintyfor DSM purposes. Our algorithm is based on solving an optimization problem thataims to minimize the electricity payment of residential users. Each appliance sendsan admission request to the ECC unit to start operation. The operation of eachappliance is subject to acceptance of its request. By running a centralized algorithm,the control unit determines the optimal operation schedule of each appliance in eachtime slot.• We study operation constraints to model a variety of appliances including must-runappliances, and interruptible and non-interruptible controllable appliances. The lastitem refers to those appliances whose operation can be postponed, but once theystart operation, they should stay on until they finish their task.• Simulation results show that our proposed scheduling algorithm with load uncertaintyreduces the energy payment of users compared to the case where no scheduling al-gorithm is adopted. Our proposed scheme also improves the overall power systemperformance by reducing the PAR in aggregate load demand.The rest of this chapter is organized as follows. The system model is introduced inSection 3.2. The problem formulation and algorithm description are presented in Section3.3. Simulation results are provided in Section 3.4. The chapter is summarized in Section3.5.3.2 System ModelIn this section, we present a mathematical model for real-time residential load schedulingwhen combined RTP and IBR tariffs are implemented. We assume that price values are41Chapter 3. Energy Consumption Scheduling with Load Uncertaintyinformed by the retailer to end users through a digital communication infrastructure. Fur-thermore, we assume that each user is equipped with a smart meter, which has an ECCunit capable of scheduling and adjusting the household energy consumption.Consider a residential unit that participates in a DSM program. Let A denote theset of all appliances in this unit. Each appliance a ∈ A can work either as must-runor controllable. Must-run appliances need to start working immediately. For example,we can classify TV and personal computer (PC) as must-run appliances. Clearly, theuser should have the freedom to turn on or turn off the TV whenever he wants withoutthe interference of the ECC. In contrast, the operation of controllable appliances can bedelayed or interrupted if necessary. Each controllable appliance can be either interruptibleor non-interruptible. For a controllable appliance a, if it is non-interruptible, then theECC may only delay its operation. However, for interruptible appliances, it is not onlypossible to postpone the operation but also to interrupt the operation when needed andthen restore the operation later on. Plug-in electric vehicle (PEV) and washing machineare examples of interruptible and non-interruptible controllable appliances, respectively.We assume that based on the demand requirements of the user, each appliance can be setas must-run or controllable. This setting is decided by the user and can vary from timeto time. That is, depending on the preferences of the user, an appliance can be set as amust-run appliance in one day and as a controllable appliance in another day.We divide the intended operation cycle into T time slots. Each time slot begins withan admission control phase. In this phase, to start the operation of an appliance, anadmission request is sent to the ECC unit. Once an admission request is submitted, thestate of the appliance changes from sleep to awake. The appliance remains awake until itsoperation is finished. However, the operation of an awake appliance is subject to acceptanceof its admission request and specification of its operation schedule by the ECC unit. The42Chapter 3. Energy Consumption Scheduling with Load Uncertaintydecisions regarding the admission of the requests and the adjustment of the operation ofdifferent awake appliances are updated periodically in each admission control phase.An awake appliance a can be either inactive (with zero power consumption) or active(operating at nominal power γa). We note that the power consumption of each appliancecould be different at different cycles of its operation due to the changes in the amount ofcurrent being absorbed. However, considering the exact load profile of each appliance addsto the complexity of the model and makes real-time implementation difficult. To tacklethis implementation difficulty, similar to [40, 79], and [41], we consider an average powerconsumption γa for each appliance. Different operating states of must-run and controllableappliances are shown in Fig. 3.1.We note that the operation of different appliances is influenced by the preferences ofthe user. Different parameters of our model may be considered to capture different typesof preferences. For example, our model takes into account the time and the frequency atwhich each appliance sends admission requests to the ECC unit. Furthermore, we assumethat the mode of operation of each appliance, i.e., whether it is must-run or controllable,is not pre-determined. That is, based on the preference of the user, each appliance canwork either as must-run or controllable. Moreover, for controllable appliances, the deadlinebefore which the operation of the appliance has to be finished is also determined based onthe preference of the user. Other aspects of user preferences, such as the desirable roomtemperature, can also be considered to enhance energy consumption scheduling; however,adding those aspects will also make the design more complex and less appealing for real-time implementation in practice.The admission request of each appliance a specifies the total energy Ea needed to finishthe operation of the appliance, the operating power γa, and whether the appliance is must-run or controllable. For controllable appliances, the deadline before which the operation43Chapter 3. Energy Consumption Scheduling with Load UncertaintyFigure 3.1: Different operating states of (a) must-run, (b) non-interruptible controllable,and (c) interruptible controllable appliances.of the appliance has to be finished, denoted by βa, and whether it is interruptible or not,are the additional information to be included in the admission request. For a controllableappliance a, if it is not interruptible, the ECC may only delay its operation. However,for interruptible appliances, it is not only possible to postpone the operation but also tointerrupt the operation when needed.We define binary variable xat ∈ {0, 1} as the state of power consumption of appliancea ∈ A at time slot t ∈ {1, . . . , T}. We set xat = 1 if appliance a is admitted to operate intime slot t (i.e., active), otherwise, we set xat = 0 (i.e., inactive). Let Eat denote the amountof energy required to finish the operation of appliance a while the current time slot is t.Note that given Eat , for each future time slot k > t > 0, we haveEak =[Eat − γak−1∑i=txai]+. (3.1)For controllable appliances that are non-interruptible, their operation can be delayed,but once they become active, they must remain active until the end of their operation.44Chapter 3. Energy Consumption Scheduling with Load UncertaintyThus, for each non-interruptible controllable appliance a, we havexak = 1, ∀ k ∈ {t, . . . , βa}, 0 < Eak < Ea. (3.2)Let lt ,∑a∈A γaxat denote the total household power consumption at time slot t. Weconsider a pricing function λt(lt) which represents the price of electricity in each time slott as a function of the user’s power consumption in that time slot. For combined RTP andIBR pricing tariffs, the price function λt(lt) is defined as [12]:λt(lt) =mt, if 0 ≤ lt ≤ bt,nt, if lt > bt,(3.3)where mt, nt, and bt are pre-determined parameters. We have mt≤nt. Recall from Section3.1 that a combined RTP and IBR pricing model can effectively avoid load synchronization[12].3.3 Problem Formulation and Algorithm DescriptionIn this section, we consider the problem of efficient power scheduling such that the elec-tricity payment of each user is minimized. We assume that only some statistical demandinformation are known ahead of time. The exact information about the list of appliancesthat are awake in each time slot, whether they are must-run or controllable, and the dead-line by which the operation of each appliance should be finished is revealed only graduallyover time. We note that different sets of awake appliances, i.e., must-run and controllable,at future time slot k > t, can be separated into two disjoint subsets. The first subset in-cludes those appliances that are awake at the current time slot t and remain awake at timeslot k>t, i.e., the information about this subset of appliances is known at the current time45Chapter 3. Energy Consumption Scheduling with Load Uncertaintyslot. The second subset consists of those appliances that are asleep at the current timeslot t and will be awake at time slot k>t. However, at the current time slot t, only somestatistical information about this subset of appliances is available. An update is receivedby the ECC unit at the beginning of each time slot, and the energy consumption scheduleof each controllable appliance is adapted accordingly.3.3.1 Problem FormulationThe optimum operation schedule can be determined if the demand information of all ap-pliances is available at the beginning of the scheduling horizon. However, we assume herethat the demand information of the appliances is not known and instead only stochasticinformation regarding the demand is available a priori. Thus, we formulate a schedul-ing problem that minimizes the expected energy payment of the user with respect to de-mand uncertainties. In each time slot t, as the demand information of the appliances isupdated, the operation schedule of each controllable appliance can be rescheduled. Thepower scheduling can be identified in real-time as the solution of the following optimizationproblem:minimizexat , ∀ a ∈ C˜k ,∀ k∈{t, . . . , T}E{Ltλt(Lt)+T∑k=t+1Lk,tλk(Lk,t)}subject to xak ∈ {0, 1}, ∀ a ∈ C˜k, k ∈ {t, . . . , T},γaβa∑k=txak = Eat , ∀ a ∈ C˜k,xak = 1, 0 < Eak < Ea, ∀ a∈N˜k, k ∈{t, . . . , βa},(3.4)46Chapter 3. Energy Consumption Scheduling with Load Uncertaintywhere E{·} denotes the expectation,Lt =∑a∈M˜tγa +∑a∈C˜tγaxat , (3.5)Lk,t =∑a∈Mk,tγa +∑a∈Mˆk,tγa +∑a∈Ck,tγaxak +∑a∈Cˆk,tγaxak, (3.6)xat , (xat , . . . , xaT ), Eak is as in (3.1), and the definitions of the different sets of appliancesMk,t, Mˆk,t, M˜t, Ck,t, Cˆk,t, C˜k, and N˜k are presented in Table 3.1.We note that Eat is known at time slot t, must-run appliances are active as long as theyare awake, Ck,t = Ct,t for all k ≥ t, and as the demand information is known up to time slott, Mˆt,t = Cˆt,t = ∅. The first term in the objective function in (3.4) is the payment of theuser in the current time slot t for the known load Lt, while the second term is the expectedcost of energy in the upcoming time slots. Each appliance can be either on or off. Thisis indicated by the first constraint. The second constraint implies that the operation ofeach appliance should be finished by its deadline. The last constraint guarantees that theoperation of non-interruptible appliances will continue after they become active until theyfinish their job.In our stochastic model, it is possible to devise different objectives and different strate-gies to schedule the operation of different appliances. The performances of different schedul-ing strategies are different. However, their different performances may be compared basedon their average performance and their worst case performance for different demand re-quirements of the user. Problem (3.4) in its current form is difficult to solve as it requiresthe computation of the expected schedule for currently sleeping appliances2. To tackle2One option to solve problem (3.4) is to formulate it as a dynamic programming problem. Consideringthe amount of information required to describe the state of each appliance, i.e., whether the appliance isawake or not, the remaining energy requirements, and the number of time slots remaining to reach thedeadline, we may be faced with a huge state space of outcomes. Dynamic programming may suffer from47Chapter 3. Energy Consumption Scheduling with Load UncertaintyTable 3.1: List of variables used in this chapter.A Set of appliancesT Number of time slotsγa Nominal power of appliance aEa Total required energy of appliance aβa Operating deadline of appliance axat State of power consumption of appliance a at time slot tEat Remaining required energy of appliance a at time slot tlt Total household power consumption at time slot tλt(·) Price function at time slot tmt Price parameter at time slot tnt Price parameter at time slot tbt Price parameter at time slot tMk,t Set of must-run appliances that are awake at time slot tand remain awake at time slot k ≥ tMˆk,t Set of must-run appliances that are asleep at time slot tand will be awake at time slot k ≥ tM˜k Set of all must-run appliances that are awake at time slot k(Mk,t ∪ Mˆk,t)Ck,t Set of controllable appliances that are awake at time slot tand remain awake at time slot k ≥ tCˆk,t Set of controllable appliances that are asleep at time slot tand will be awake at time slot k ≥ tC˜k Set of all controllable appliances that are awake at time slot k(Ck,t ∪ Cˆk,t)Nk,t Set of non-interruptible appliances of Ck,tNˆk,t Set of non-interruptible appliances of Cˆk,tN˜k Set of all non-interruptible appliances that are awake at time slot k(Nk,t ∪ Nˆk,t)St Set of all appliances that are sleeping at time slot tyak Auxiliary variable for each non-interruptible appliance a at each time slot kM Auxiliary large number used in the problem formulationνk Auxiliary variable for each time slot kpat Probability with which appliance a becomes awake at time slot tqa Probability that appliance a does not become awake at any time slotpaτ,t Probability that appliance a becomes awake at time slot τ > t given thatit has not become awake until time slot tδaτ,t Probability that must-run appliance a which is sleeping at time slot twill be active in time slot τ > tTa Number of time slots required to finish the operation of appliance athe curse of dimensionality [82].48Chapter 3. Energy Consumption Scheduling with Load Uncertaintythis problem, we minimize an upper bound of the objective function. We assume all ap-pliances that become awake in future time slots are must-run appliances. In this case, therisk of loss for the user is minimized. That is, from the the user’s electricity paymentpoint of view, the worst performance of the ECC unit for different scheduling strategies isminimized.minimizexat , ∀ a∈C˜tLtλt(Lt)+T∑k=t+1E{L¯k,tλk(L¯k,t)}subject to xak ∈ {0, 1}, ∀ a ∈ C˜t, k ∈ {t, . . . , T},γaβa∑k=txak = Eat , ∀ a ∈ C˜t,xak = 1, 0 < Eak < Ea, ∀ a∈N˜t, k ∈{t, . . . , βa},(3.7)whereL¯k,t =∑a∈Mk,tγa +∑a∈Mˆk,t∪ Cˆk,tγa +∑a∈Ck,tγaxak (3.8)denotes the load at time slot k > t.Problem (3.7) is still difficult to solve in its current form since the last constraint isconditioned on the value of Eak for k∈{t+1, . . . , βa}. From (3.1), for k∈{t+1, . . . , βa}, Eakdepends on variable xai for i ∈ {t, . . . , k−1}, which is unknown and should be determined.However, by introducing an auxiliary variable yak ∈ {0, 1} for each appliance a ∈ N˜t andat each time slot k ∈ {t+1, . . . , βa}, the problem formulation in (3.7) can be re-written ina more tractable form. Here, the auxiliary variable yak indicates whether the operation ofappliance a is finished (yak = 1) or not (yak = 0) at a particular time slot k∈{t+1, . . . , βa}.49Chapter 3. Energy Consumption Scheduling with Load UncertaintyThus, we can re-write problem (3.7) asminimizexat , ∀ a ∈ C˜tyat , ∀ a ∈ N˜tLtλt(Lt)+T∑k=t+1E{L¯k,tλk(L¯k,t)}+MT∑k=t∑a∈C˜tyak (3.9a)subject to xak ∈ {0, 1}, ∀ a ∈ C˜t, k ∈ {t, . . . , T}, (3.9b)yak ∈ {0, 1}, ∀ a ∈ N˜t, k ∈ {t, . . . , T}, (3.9c)γaβa∑k=txak = Eat , ∀ a ∈ C˜t, (3.9d)yak +Eat − γa∑k−1i=t xaiEa≥ ǫ, ∀ a ∈ N˜t, k ∈ {t, . . . , βa}, (3.9e)xak + yak +Eat − γa∑k−1i=t xaiEa≥ 1, ∀ a ∈ N˜t, k ∈ {t, . . . , βa}, (3.9f)where yat , (yat , . . . , yaT ), M is a constant, and 0 < ǫ < min{ γ1E1 , . . . ,γ|A|E|A|} is a smallconstant. We can justify the new constraints as follows. In (3.9e), when Eak = Eat −γa∑k−1i=t xai = 0, yak becomes 1. However, as long as the operation is not finished, i.e.,Eak > 0, since yak appears in the objective of the minimization problem, we have yak = 0.This is true, since for any value Eak > 0, we haveEakEa > ǫ. In (3.9f), when Eak = Ea, wehave yak = 0, and xak can be either 0 or 1, when Ea > Eak > 0, we have yak = 0 and xak hasto be 1. However, when Eak = 0, we have yak = 1, and since xak appears in the objective ofthe minimization problem, it has to be 0.For the price function in (3.3), since mt ≤ nt, for a total load lt at time slot t, the user’spayment lt × λt(lt) is determined as the maximum of the two intersecting lines [12]:lt × λt(lt) = max{mtlt, ntlt+(mt−nt)bt}. (3.10)50Chapter 3. Energy Consumption Scheduling with Load UncertaintyThus problem (3.9) can be reformulated asminimizexat , ∀ a ∈ C˜tyat , ∀ a ∈ N˜tmax{mt(∑a∈C˜tγaxat +∑a∈M˜tγa), nt(∑a∈C˜tγaxat +∑a∈M˜tγa)+ (mt − nt)bt}+T∑k=t+1E{max{mk(∑a∈C˜tγaxak + lk,t), nk(∑a∈C˜tγaxak+lk,t)+(mk−nk)bk}}+MT∑k=t∑a∈C˜tyak (3.11)subject to (3.9b)-(3.9f),wherelk,t ,∑a∈Mk,tγa +∑a∈Mˆk,t∪ Cˆk,tγa. (3.12)Finally, by introducing another auxiliary variable, νk, for each time slot k, and by adoptingthe certainty equivalent approximation technique, i.e., all uncertainties are fixed at theirexpected value [83], we can re-write problem (3.11) asminimizeνt,xat , ∀ a ∈ C˜tyat , ∀ a ∈ N˜tT∑k=tνk +MT∑k=t∑a∈C˜tyak (3.13)subject to (3.9b)-(3.9f),mt(∑a∈C˜tγaxat +∑a∈M˜tγa)≤ νt,nt(∑a∈C˜tγaxat+∑a∈M˜tγa)+(mt − nt)bt ≤ νt,mk(∑a∈C˜tγaxak + lˆk,t)≤ νk, ∀ k∈{t+1, . . . , T},51Chapter 3. Energy Consumption Scheduling with Load Uncertaintynk(∑a∈C˜tγaxak+ lˆk,t)+(mk−nk)bk ≤ νk, ∀ k∈{t+1, . . . , T},where νt, (νt, . . . , νT ), and lˆk,t,E{lk,t}, the estimate of the power consumption of must-run appliances in an upcoming time slot k ≥ t will be calculated in the next sub-section.Problem (3.13) is a mixed-binary linear program and can be solved efficiently by usingMOSEK [84]. The solution of optimization problem (3.13) determines the appropriatescheduling for the operation of controllable appliances. However, for interruptible appli-ances, only the operation schedule of the current time slot t will be executed, and theschedule of the future time slots t + 1, . . . , T may change when the optimization problemis solved again in the next time slot as new information about the future load becomesavailable.3.3.2 Load EstimationIn our system model, we assume that the demand information of the appliances is notknown ahead of time, i.e., in (3.12), the set of awake appliances in the upcoming time slotsk > t that are currently sleeping, Mˆk,t ∪ Cˆk,t, is not known. Instead, only the probabilitywith which each appliance becomes awake at each time slot t, pat , is known before theoperation cycle begins. Such information can be calculated, for example, based on thesleep and awake history of each appliance. For this purpose, we can observe a windowof N consecutive days and mark those days in which appliance a becomes awake in aparticular time slot t. The ratio of the number of marked days to the total number ofobserved days determines the probability with which appliance a becomes awake in timeslot t, pat , P(∆at = 1), where ∆at is a random variable that is equal to one if appliance abecomes awake in time slot t, and equal to zero otherwise. In our model, each appliancecan become awake only once. If an appliance becomes awake more often, we can simply52Chapter 3. Energy Consumption Scheduling with Load Uncertaintyintroduce virtual appliances to deal with this issue. Therefore, we haveT∑t=1pat + qa = 1, (3.14)where qa denotes the probability that appliance a does not become awake at any timewithin the DSM’s operation period [1, T ]. We define paτ,t as the probability that appliancea becomes awake in time slot τ > t given that it has not become awake until time slot t.That is,paτ,t = P(∆aτ = 1 |∆a1 = 0, . . . ,∆at = 0). (3.15)Based on Bayes rule, paτ,t can be calculated aspaτ,t =P(∆a1 = 0, . . . ,∆at = 0 | ∆aτ = 1)P(∆aτ = 1)P(∆a1 = 0, . . . ,∆at = 0). (3.16)If appliance a becomes awake at time slot τ > t, it implies that it has not become awakein previous time slots. Therefore, P(∆a1 = 0, . . . ,∆at = 0 | ∆aτ = 1) = 1. On the otherhand, we obtain P(∆a1 = 0, . . . ,∆at = 0) =∑Tk=t+1 pak + qa based on (3.14). We also haveP(∆aτ = 1) = paτ . Therefore, (3.16) becomespaτ,t =paτ∑Tk=t+1 pak + qa. (3.17)Next, assume that all appliances that become awake in future time slots are must-runappliances, and must-run appliances start operation once they become awake, see Section3.3.1. Let Λaτ denote the random variable that indicates whether must-run appliance a isactive (Λaτ = 1) or not active (Λaτ = 0) in time slot τ . Also, let δaτ,t denote the probabilitythat a must-run appliance a which is sleeping in time slot t will be active in time slot τ > t.By conditioning on the time slot in which must-run appliance a becomes awake, δaτ,t can53Chapter 3. Energy Consumption Scheduling with Load UncertaintyFigure 3.2: Must-run appliance a ∈ St with Ta = 3 will be active in τ > t if it startsoperation within time interval [max{t+ 1, τ − Ta + 1}, τ ].be calculated asδaτ,t = P(Λaτ =1 | ∆a1=0, . . . ,∆at =0)=T∑k=t+1P(Λaτ =1 | ∆a1=0, . . . ,∆at =0,∆ak=1)pak,t, (3.18)where pak,t is defined in (3.15). As illustrated in Fig. 3.2, a currently sleeping appliance willbe active in time slot τ > t, if it starts operation within time frame [max{t+1, τ−Ta+1}, τ ],where Ta , Eaγa is defined as the number of time slots required to finish the operation ofappliance a while operating at power level γa. For simplicity, we assume Ta is integer.Therefore, P(Λaτ =1 | ∆a1=0, . . . ,∆at =0,∆ak=1) = 1 if k ∈ [max{t+ 1, τ − Ta + 1}, τ ], andP(Λaτ =1 | ∆a1=0, . . . ,∆at =0,∆ak=1) = 0 otherwise. Thus, we haveδaτ,t =τ∑k=max{t+1,τ−Ta+1}pak,t. (3.19)Finally, by conditioning on the event of observing a currently sleeping appliance activein an upcoming time slot τ , while the system is at time slot t, the estimate of the powerconsumption required in (3.13) becomes:lˆτ,t = E {lτ,t} =∑a∈Mτ,tγa +∑a∈Stγaδaτ,t, (3.20)54Chapter 3. Energy Consumption Scheduling with Load UncertaintyAlgorithm 3.1: Energy consumption scheduling algorithm in presence of load uncertaintyexecuted at the beginning of each time slot t.1: Receive admission requests.2: Label received requests either as must-run or controllable.3: Activate must-run appliances (start / continue operation).4: Update paτ,t according to (3.17).5: Update δaτ,t according to (3.19).6: Update lˆτ,t according to (3.20).7: Update Eat according to (3.1).8: Solve (3.13) to activate / deactivate controllable appliances.9: if activated device is non-interruptible10: Mark it as must-run.11: end ifwhere St is defined in Table 3.1.3.3.3 Algorithm DescriptionIn this section, we explain the different steps of the proposed energy consumptionscheduling algorithm in presence of load uncertainty (Algorithm 3.1) executed at eachtime slot t.Step 1 At the beginning of the admission control phase at each time slot, all receivedadmission requests are labeled as either must-run or controllable, c.f. Lines 1 and 2.Step 2 Activate must-run appliances a ∈ M˜t right away, c.f. Line 3. That is, start orcontinue their operation at the requested power γa. Their operation will not be interrupted,and they remain must-run until the end of their operation.Step 3 In Line 4, considering the list of appliances that have already become awake,update the probabilities at which other appliances will send an admission request in theupcoming time slots as in (3.17). Adopt (3.19) to update the probabilities with whichsleeping devices become active in upcoming time slots, c.f. Line 5.55Chapter 3. Energy Consumption Scheduling with Load UncertaintyStep 4 Use the current information to calculate the expected load in the upcoming timeslots using (3.20) as indicated in Line 6. Update the remaining required energy of eachappliance at the beginning of the current time slot, i.e., Eat , using (3.1), c.f. Line 7.Step 5 Next, set the “on” / “off” state of each awake controllable appliance for the restof the time slots by solving optimization problem (3.13), c.f. Line 8.Step 6 In Lines 9 to 11, if any non-interruptible controllable appliance became active (i.e.,it switched from off to on) in Step 5, remove it from the list of controllable appliances andadd it to list of must-run devices as it should remain on until it finishes its operation.3.4 Performance EvaluationIn this section, we present simulation results and assess the performance of our proposedDSM algorithm. We run the simulation multiple times with different patterns for the timesat which the appliances become awake. We then present the average results. Unless statedotherwise, the simulation setting is as follows. We assume that the general RTP methodcombined with IBR is adopted as described in (3.3). In our system model, the retail priceparameters, mt, nt, and bt, are set by the retail energy provider to compensate the cost ofproviding energy and to shape the daily energy consumption of the user. However, theseparameters are different from the load cost profile of the energy provider, as the load costprofile of the energy provider is determined in the wholesale electricity market. The exactload cost profile of the retailer is usually not known to the end users. Fig. 3.3 illustrates thevariation of parameters mt and nt of the price function over one day. We consider a singlehousehold with various must-run and controllable appliances. Controllable appliances canbe either interruptible or non-interruptible. Non-interruptible appliances include: electric56Chapter 3. Energy Consumption Scheduling with Load Uncertainty8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 2 3 4 5 6 724681012Time of Day (hour)Pricing Parameters (Cents/kW)  Pricing Parameter ntPricing Parameter mtFigure 3.3: The pricing parameters used based on the combined RTP and IBR pricingmodel in (3.3). Parameter bt = 3.5 kW is fixed for all time slots.stove (Ea=4.5 kWh, γa=1.5 kW), clothes dryer (Ea=1 kWh, γa=0.5 kW), and vacuumcleaner (Ea=3 kWh, γa=1.5 kW). Interruptible appliances include: Refrigerator (Ea=2.5kWh, γa=0.125 kW), air conditioner (Ea=6 kWh, γa=1.5 kW), dishwasher (Ea=2 kWh,γa = 1 kW), heater (Ea = 4 kWh, γa = 1 kW), water heater (Ea = 2 kWh, γa = 1 kW),pool pump (Ea = 4 kWh, γa = 2 kW), and PEV (Ea = 10 kWh, γa = 2.5 kW). Must-runappliances include: Lighting (Ea = 3 kWh, γa = 0.5 kW), TV (Ea = 1 kWh, γa = 0.25kW), PC (Ea = 1.5 kWh, γa = 0.25 kW), ironing appliance (Ea = 2 kWh, γa = 1 kW),hairdryer (Ea = 1 kWh, γa = 1 kW), and others (Ea = 6 kWh, γa = 1.5 kW). The detailsof the average annual energy consumption of different appliances and the average monthlyenergy consumption of residential users in the US can be found in [85] and [86]. The timeslot at which each appliance becomes awake is selected randomly from a pre-determinedtime interval, e.g. [6:00, 14:00] for electric stove and [16:00, 24:00] for PEV.57Chapter 3. Energy Consumption Scheduling with Load Uncertainty3.4.1 Performance Gains of Users and Utility CompanyTo have a baseline to compare with, we consider a system without ECC deployment, whereeach appliance a is assumed to start operation right after it becomes awake at its nominalpower γa. As an upper bound, we also consider a system with ECC deployment in whichall the demand information of the appliances is available ahead of time. Simulation resultsfor the average total power consumption for the proposed residential load control algo-rithm, the system without ECC deployment, and the system in which complete demandinformation is available ahead of time are depicted in Fig. 3.4. In our simulation model,we set bt = 3.5 kW in (3.3) for all time slots. As illustrated in Fig. 3.4, to reduce elec-tricity payment, the ECC unit shifts the load to time slots with lower prices such as theafter midnight hours. However, the high price penalty for exceeding the bt threshold pre-vents load synchronization as discussed in Section 3.1. The simulation results show thatexploiting the use of the ECC unit reduces the average daily payment of the user from4.76 Dollars/day to 4.01 Dollars/day. For the case, where complete information about thedemand of each appliance is available ahead of time, the average daily payment of the useris 3.92 Dollars/day. To evaluate the PAR, the user’s daily peak load is divided by his dailyaverage load. That is, after running the algorithm, at the end of the operation period, wecomputePAR = T max{l1, . . . , lT}∑Tk=1 lk, (3.21)where lk is the total power consumption of the user at time slot k. The proposed algorithmalso helps to reduce the average PAR of the system from 2.66 to 1.98 (25.5% PAR reduction)compared to the system without ECC deployment. The PAR of the system with ECCdeployment if complete demand information is known a priori is 1.89.58Chapter 3. Energy Consumption Scheduling with Load Uncertainty0 5 10 15 20 250123456Time (Hour)Average Load (kW)(a) Without ECC Deployment0 5 10 15 20 25012345Time (Hour)Average Load (kW)(b) With ECC Deployment0 5 10 15 20 25012345Time (Hour)Average Load (kW)(c) With ECC Deployment and Complete Demand InformationFigure 3.4: Power consumption for (a) the system without ECC deployment, (b) thesystem with ECC deployment, and (c) the system with ECC deployment in which completedemand information is available ahead of time.3.4.2 Computational ComplexityIn general, integer linear programs with n integer variables and m constraints are knownto be NP-complete [87]. However, there exist pseudo-polynomial algorithms for solvingm× n integer programs with fixed m which have an order of complexity ofO(n2m+2(mα)(m+1)(2m+1) log(n2(mα2)2m+3)),where α is the maximum coefficient in the set of constraints [88]. A complete discussionof the complexity of such algorithms is out of the scope of this chapter. To illustrate the59Chapter 3. Energy Consumption Scheduling with Load Uncertaintycomplexity of our proposed algorithm, simulation results for the average run time of thealgorithm, the number of integer variables, and the number of constraints for differentnumbers of appliances and different time granularities are given for one time slot in Table3.2. The order of complexity of the algorithm determines the maximum run-time or themaximum number of elementary operation required to solve the problem for any inputscenarios. In practice, the times at which different appliances become awake are distributedover the operation horizon, and it is unlikely that all appliances become awake at the sametime. Thus, at each time slot, the number of awake appliances required to be scheduledis limited. This can significantly reduce the average run time of the algorithm in mostpractical scenarios. By increasing the time granularity, the number of integer variablesand the number of constraints are increased, since the number of time slots at whichthe operation of each appliance should be scheduled is increased. However, the effect ofthis increase is mitigated, since the times at which different appliances become awake aredistributed over a larger number of time slots, and the number of awake appliances in eachtime slot is reduced.3.4.3 The Impact of Price Control Parameter btConsidering the price function as described in (3.3), in each time slot, if the power con-sumption of the user exceeds a certain threshold defined as bt, the user will be penalizedby paying a higher price. The choice of parameter bt has a significant impact on users’payments and the PAR. To have a baseline to compare with, similar to [41], we considera system in which the effect of IBR is ignored and only the basic price in each time slot istaken into account to schedule the operation of different appliances in order to minimizethe electricity payment of the user. Simulation results for the average payment of the userand the PAR of the system for different values of parameter bt are shown in Figs. 3.5 and60Chapter 3. Energy Consumption Scheduling with Load UncertaintyTable 3.2: Performance measures and complexity analysis of the proposed algorithm.Average run time of the algorithm (in seconds).Time granularity |A|=20 |A|=25 |A|=351 hour 0.0287 0.0308 0.035030 minutes 0.0294 0.0316 0.042215 minutes 0.0302 0.0318 0.0988Average number of integer variables.Time granularity |A|=20 |A|=25 |A|=351 hour 80 156 29630 minutes 121 230 44015 minutes 168 316 619Average number of constraints.Time granularity |A|=20 |A|=25 |A|=351 hour 43 79 13930 minutes 46 81 14215 minutes 54 87 1453.6, respectively. Intuitively, increasing the price parameter bt for each time slot resultsin a reduction of the user’s payment as shown in Fig. 3.5. Considering the average PAR,for the system without ECC deployment and the system without IBR consideration, thePAR does not change as the user does not respond to changes of parameter bt. For thesystem with ECC deployment, for low values of parameter bt, even the load of must-runappliances in most time slots exceeds this threshold. Thus, the ECC unit mainly considersthe nt price parameter to schedule the operation of controllable appliances. However, byincreasing parameter bt, since the load of must-run appliances lies below threshold bt insome time slots, the user is encouraged to shift the controllable portion of its load to avoidpaying higher price nt rather than lower price mt, which initially results in reducing thePAR. Later on, a further increase of parameter bt reduces the effect of IBR, entails loadsynchronization effects, and increases the PAR of the system. That is, for large values of61Chapter 3. Energy Consumption Scheduling with Load Uncertainty2 3 4 5 6 7 8 9 102.62.83.03.23.43.63.84.04.2Parameter btUser Payment (Dollars)  Without ECC DeploymentWithout IBR ConsiderationWith ECC DeploymentWith ECC Deployment and Complete Demand Information   1.5% reduction in user payment15% reduction in user payment  Figure 3.5: The daily payment of the user for different values of parameter bt.2 3 4 5 6 7 8 9 101.822.22.42.62.833.23.43.63.8Parameter btPAR  Without ECC DeploymentWithout IBR ConsiderationWith ECC DeploymentWith ECC Deployment and Complete Demand InformationFigure 3.6: PAR of the system for different values of parameter bt.parameter bt, it is less likely that the load of the user exceeds this threshold, and the ECCunit mainly pays attention to the value of the price parameter mt in order to schedule theoperation of controllable appliances. This results in shifting a large portion of the load tolow price time slots. Therefore, for large values of parameter bt, the performance of ourproposed method approaches the one without IBR consideration as shown in Fig. 3.6.62Chapter 3. Energy Consumption Scheduling with Load Uncertainty3.4.4 The Impact of Adopting Inclining Block RatesIn this section, we examine how changes of the two parameters mt and nt of the pricefunction will affect the performance of the system. In our simulation model, parametermt changes as illustrated in Fig. 3.3 and we set bt = 3 kW for all time slots. However,parameter nt is given bynt = θmt, ∀ t ∈ {1, . . . , T}. (3.22)Simulation results for the average daily payment of the user as well as the average PAR ofthe system for different values of parameter θ are depicted in Figs. 3.7 and 3.8, respectively.Intuitively, when θ is equal to one, i.e., when mt = nt for all t, the performance of ourproposed method is the same as the one in which the effect of IBR is ignored. However, byincreasing parameter θ, the payment of the user will be increased, as the user has to paymore every time that its load exceeds threshold bt as shown in Fig. 3.7. As indicated inFig. 3.8, increasing parameter θ improves the PAR of the system, as load synchronizationis prevented. That is, to avoid paying at higher price nt, the ECC unit tries to distributethe load such that it does not exceed the bt threshold. However, for the system withoutIBR consideration, changes of parameter θ do not affect the PAR.3.5 SummaryIn this chapter, we proposed an optimal residential load control algorithm for DSM inpresence of load uncertainty. We formulated an optimization problem to minimize theelectricity payment of the users in situations where only an estimate of the future demandis available. We focused on a scenario where real-time pricing is combined with IBRsto balance residential load to achieve a low PAR. Simulation results showed that theproposed algorithm reduces the energy cost of users, encouraging them to participate in63Chapter 3. Energy Consumption Scheduling with Load Uncertainty1 1.5 2 2.5 3 3.5 42.53.03.54.04.55.05.5Parameter θUser Payment (Dollars)  Without ECC DeploymentWithout IBR ConsiderationWith ECC DeploymentWith ECC Deployment and Complete Demand Information14.7% reduction in user payment25.2% reduction in user paymentFigure 3.7: The daily payment of the user for different values of parameter θ.1 1.5 2 2.5 3 3.5 41.822.22.42.62.833.23.43.63.8Parameter θPAR  Without ECC DeploymentWithout IBR ConsiderationWith ECC DeploymentWith ECC Deployment and Complete Demand InformationFigure 3.8: PAR of the system for different values of parameter θ.DSM. Exploiting IBR with RTP tariffs can help to avoid load synchronization, and thecombination of the general RTP method with our algorithm reduces the PAR of the totalload. The latter provides incentives for utilities to support implementing the proposedalgorithm.64Chapter 4Real-Time Pricing for Demand SideManagement4.1 IntroductionWith the growing deployment of AMI [27] and ECC devices [11, 28, 29, 50, 55, 89], RTPis gradually becoming a feasible DSM solution. In general, it is difficult for power usersto follow the RTP price variations to make appropriate decisions accordingly. In thisregard, ECC devices can help by making such price-responsive decisions on behalf of usersto achieve certain objectives. However, while the use of ECC devices improves users’rationality in response to price changes, such ECC devices can also introduce new DSMchallenges such as load synchronization [12] and price instability [43, 90]. Therefore, theeffect of the automated ECC devices on users’ price-responsiveness is not obvious and yetto be investigated.In this chapter, we address minimizing the PAR in the aggregate load demand throughpricing under the practical scenario that the utility is uncertain about users’ price-responsiveness.While we assume that users are equipped with ECC devices, our approach is quite differentfrom all prior works, e.g., in [11, 12, 28–30], which do not take into account the uncer-tainty in users’ price-responsiveness. Note that such uncertainty is inevitable to preserveuser privacy [91].Some related literature can be summarized as follows. In [28], Chen et al. devised a65Chapter 4. Real-Time Pricing for DSMEnergy ProviderPCUSSUUsersPriceParametersUsers’ Historical Load ProfilesΛ Q(Λ) Figure 4.1: The block diagram of the proposed closed-loop pricing model.Stackelberg game approach in which the energy provider acts as a leader and users arefollowers. This design intends to jointly maximize the social welfare of all users and therevenue of the energy provider. The algorithm in [28] requires detailed information aboutusers’ energy consumption needs. However, for the scheme proposed in this chapter, usersare not required to submit their demand requirements at the beginning of the operationperiod. As a result, our design is more practical and preserves users’ privacy. The authorsof [11] proposed a game theoretic approach to minimize the PAR of the system, whereusers interact with each other and change their power consumption accordingly. However,such interactions may take a long time to converge, in particular in the presence of a largenumber of users. In contrast, our design does not involve direct user interaction. Therefore,it converges much faster.The block diagram of our proposed real-time pricing model is shown in Fig. 4.1. Ourmain contributions are as follows:• We propose two iterative algorithms to be implemented in a price control unit (PCU)for minimizing the PAR of the aggregate load based on the information provided bythe system simulator unit (SSU). The first algorithm, called finite-difference price se-lection (FDPS), uses a variation of the finite-difference technique [52] to approximatethe gradient of the PAR minimization objective function by making small one-at-a-time changes to each individual element of the input price parameter vector. The66Chapter 4. Real-Time Pricing for DSMFDPS algorithm requires only few iterations for convergence. However, it needs alarge number of measurements of the objective function in each iteration.• The second algorithm, called simultaneous perturbation price selection (SPPS), isbased on the simultaneous perturbation technique [52]. Unlike the FDPS algorithm,all elements of the input variable are jointly and randomly perturbed to approximatethe gradient. As a result, the SPPS algorithm significantly reduces the number ofmeasurements of the objective function in each iteration, compared to the FDPSalgorithm. Yet, we show that it achieves a similar performance.• We propose an approximate dynamic programming scheme which simulates how usersautomatically respond to various price values to eliminate the need for users to revealtheir detailed energy consumption needs to the energy provider. This assures userprivacy.• Simulation results show that our proposed pricing algorithms reduce the PAR inaggregate load. In addition, we show that adopting the new pricing algorithms isalso beneficial for the users if they are equipped with automated control units.The rest of this chapter is organized as follows. The system model and problem for-mulation are introduced in Section 4.2. The FDPS and SPPS algorithms are developedin Section 4.3. The SSU is explained in Section 4.4. Simulation results are presented inSection 4.5. The chapter is summarized in Section 4.6.4.2 Problem FormulationLet U denote the set of all users. Let Au denote the set of all appliances of user u ∈ U .We denote Mu as the set of must-run appliances of user u, Cu as the set of controllable67Chapter 4. Real-Time Pricing for DSMappliances of user u, andNu as the non-interruptible subset of Cu. For each user, we assumethat there is an ECC unit which is embedded in the user’s smart meter and controls theuser’s power consumption [24, 25]. The users’ responses to the price changes are doneautomatically using the ECC units. All ECC units are connected to the energy providerthrough a two-way communication infrastructure. The operation period is divided into Ttime slots. We define binary variable xtu,a ∈ {0, 1} as the state of power consumption ofappliance a ∈ Au at time slot t ∈ T , where T , {1, . . . , T}. We set xtu,a = 1 if appliance aoperates in time slot t; otherwise, we have xtu,a = 0. For each user u, Eu,a is the total energyrequirement of appliance a ∈ Au, γu,a is the nominal power consumption of appliance a,and Tu,a = Eu,a/γu,a.4.2.1 Centralized Load Control AlgorithmAssuming that the energy provider is aware of all users’ energy needs and is capable ofremotely controlling the ECC devices of all users, the centralized load control problem tominimize the PAR in aggregate load can be formulated asminimizexu,a ∈ X˜u, ∀ a ∈ Au, ∀ u ∈ UT max{L1, . . . , LT}∑Tt=1 Lt, (4.1)wherexu,a , (x1u,a, . . . , xTu,a), (4.2)Lt =∑u∈U∑a∈Auγu,axtu,a, (4.3)68Chapter 4. Real-Time Pricing for DSMand the feasible set X˜u is defined asX˜u={xu,a∣∣∣∣xtu,a∈{0, 1}, ∀a ∈ Au, ∀ t ∈ T ,γu,aβu,a∑t=αu,axtu,a = Eu,a, ∀ a ∈ Cu,γu,aαu,a+Tu,a−1∑t=αu,axtu,a = Eu,a, ∀ a ∈ Mu,xtu,a = 1, ∀ a∈Nu, ∀ t ∈Tu,a, 0 <Etu,a<Eu,a}. (4.4)Here, αu,a is the earliest time at which the operation of appliance a could be scheduled,βu,a is the deadline by which the operation of appliance a should be finished, Tu,a ={αu,a, . . . , βu,a}, and Etu,a is the amount of energy required to finish the operation of appli-ance a ∈ Au while the system is at time slot t and is calculated asEtu,a =[Eu,a − γu,at−1∑k=1xku,a]+. (4.5)The first constraint in (4.4) indicates that each appliance can be either on or off. Thesecond constraint implies that the operation of each appliance should be scheduled withinits feasible interval. The third constraint indicates that the operation of must-run appli-ances should be started immediately. The last constraint guarantees that the operation ofnon-interruptible appliances will continue, once they become active.The ECC unit does not change the total load of the users,∑Tt=1 Lt, and the denominatorin (4.1) is a constant. We introduce an auxiliary variable Γ and rewrite problem (4.1) asminimizeΓ,xu,a ∈ X˜u,∀ a ∈ Au,∀ u ∈ UΓ69Chapter 4. Real-Time Pricing for DSMsubject to∑u∈U∑a∈Auγu,axtu,a ≤ Γ, ∀ t ∈ T . (4.6)Problem (4.6) is a linear mixed-integer program and can be solved using software such asMOSEK [84]. Its solution provides a performance benchmark for any load control algorithmthat minimizes the PAR of the aggregate load while satisfying the demand requirementsof all users.4.2.2 Decentralized Price-Based Load Control AlgorithmIn this section, we assume that the energy provider has no control over users’ behavior andit may only influence the load by changing the price parameters. Recall from Section 4.1that RTP and IBR are two non-flat pricing models that are used to encourage consumersto shift some of their load from peak hours to off-peak hours and also to prevent loadsynchronization.Let Ltu ,∑a∈Au γu,axtu,a denote the total power consumption of user u at time slott. Let λt(Ltu) denote the selected price of electricity in time slot t as a function of theuser’s power consumption in that time slot. By combining RTP and IBR [31, 32], the pricefunction λt(Ltu) is defined as [12]:λt(Ltu) =mt, if 0 ≤ Ltu ≤ bt,nt, if Ltu > bt,(4.7)where mt, nt, and bt are price parameters, and mt ≤ nt. Also, let Λt , (mt, nt, bt) andΛ , (Λ1, . . . ,ΛT ). The general pricing function in (7) represents an RTP structure thatis combined with IBR. Based on this combined model, the price of electricity depends onthe time of day and also the total load. We assume that the price parameters for eachtime slot are selected such that the PAR of the aggregate load in the system is minimized.70Chapter 4. Real-Time Pricing for DSMThus, the best choice for the price parameters in each time slot is that obtained by solvingthe following optimization problem:minimizeΛQ(Λ) (4.8)subject to mmint ≤ mt ≤ mmaxt , ∀ t ∈ T ,nmint ≤ nt ≤ nmaxt , ∀ t ∈ T ,bmint ≤ bt ≤ bmaxt , ∀ t ∈ T ,mt ≤ nt, ∀ t ∈ T ,whereQ(Λ) = max{L1(Λ), . . . , LT (Λ)}, (4.9)Lt(Λ) denotes the aggregate load at time slot t that depends on the price parameters. mmint ,mmaxt , nmint , nmaxt , bmint , and bmaxt are lower and upper bounds for the price parameters mt,nt, and bt, respectively. To devise an efficient pricing algorithm capable of minimizingthe PAR, the energy provider needs to know the behavior of the users in response to theselected price parameters. With the deployment of the ECC devices, it is very challengingto anticipate the response of the users to different price parameters. Therefore, we cannothave an explicit expression for Q(Λ) and consequently it is not possible to obtain a closed-form analytical solution for (4.8).Due to the challenges explained above, we propose to solve problem (4.8) using aniterative algorithm that does not require a closed-form expression for Q(Λ). That is, wefollow a step-by-step procedure that moves from an initial guess to a final value which isclose to the optimum solution of problem (4.8). There exist different methods to solveproblem (4.8) iteratively. In this regard, we propose to equip the energy provider withan SSU, as shown in Fig. 4.1, that simulates the likely behavior of the users in response71Chapter 4. Real-Time Pricing for DSMto price parameters announced by the energy provider. The information produced by theSSU will then be used by the PCU to select prices.4.3 Price Control Unit (PCU)Recall from Section 4.2.2 that finding a closed-form solution for problem (4.8) is challenging.An alternative is an iterative algorithm using a gradient method. In this regard, we needto approximate the gradient from noisy measurements of Q(Λ). Next, we propose twodifferent methods for this purpose.4.3.1 Finite-Difference Price Selection (FDPS)Using the finite-difference technique [52, Ch. 6], the gradient of the objective function canbe approximated by making small one-at-a-time changes to each of the individual elementsof Λ. That is, the jth element of vector Λ is perturbed and the changes in the objectivefunction are measured. The ratio of the changes in the objective function to the amountof the perturbation of the jth element of vector Λ approximates the jth element of thegradient vector of objective function Q(Λ). The general recursive procedure of updatingthe price parameters in each time slot can be written asΛi+1 = Λi − σigˆi(Λi), (4.10)where p × 1 column vector gˆi(Λi) is an estimate of the gradient of Q(Λ), ∇Q(Λ), atiteration i based on the measurements of Q(Λ)3, Λi is the input vector Λ at iteration i,and p = 3T is the size of vector Λi. The step size σi > 0 is reduced as the number of3For non-differentiable functions, to update the price parameters in (4.10), the subgradient of theobjective function can be used instead of the gradient.72Chapter 4. Real-Time Pricing for DSMiterations increases to assure convergence. In our proposed FDPS algorithm, we use one-sided gradient approximations which involve evaluations of the form Q(Λi +perturbation)and Q(Λi). That is, we obtain the gradient estimate asgˆi(Λi) =Q(Λi+ciζ1)−Q(Λi)ci...Q(Λi+ciζp)−Q(Λi)ci, (4.11)where ζj denotes a p×1 vector with a 1 in the jth position and zeros elsewhere, and ci > 0is the magnitude of the perturbations. Among different methods proposed for selectingcoefficients σi and ci, some specific forms have been suggested in practice which also satisfythe conditions required for convergence of the algorithm [52, Ch. 6]:σi = σ(i+ 1 + A)α , ci = c(i+ 1)γ , (4.12)where σ, α, c, and γ are strictly positive constants, and A ≥ 0 is added to improve theconvergence of the algorithm.4.3.2 Simultaneous Perturbation Price Selection (SPPS)Next, we consider another method for approximating the gradient of the objective functionQ(Λ) which is known as simultaneous perturbation stochastic approximation [52, Ch. 7].Similar to the FDPS algorithm, the SPPS algorithm updates the price parameters as in(4.10). However, unlike FDPS, the SPPS algorithm randomly and jointly perturbs allelements of Λi in order to obtain two different perturbed measurements of Q(·). Thus, the73Chapter 4. Real-Time Pricing for DSMtwo-sided simultaneous perturbation gradient approximation is given bygˆi(Λi) =Q(Λi+ci∆i)−Q(Λi−ci∆i)2ci∆i1...Q(Λi+ci∆i)−Q(Λi−ci∆i)2ci∆ip(4.13)= Q(Λi+ci∆i)−Q(Λi−ci∆i)2ci( 1∆i1, . . . , 1∆ip),where ∆i , (∆i1, . . . ,∆ip)is the perturbation vector, and ∆ij ∈ {−1, 1} is a random number.We note that, for the SPPS algorithm, the number of measurements in each iteration istwo, independent of the size parameter p. Thus, compared to FDPS, the SPPS algorithmprovides large savings in the number of measurements in each iteration, especially if p islarge. This lower per-iteration complexity is beneficial as long as the number of iterationsrequired to converge to an optimal value of Λ⋆ does not increase significantly.4.3.3 Algorithm DescriptionIn this section, we explain the steps of the proposed FDPS and SPPS algorithms (Algo-rithm 4.1) executed at the PCU. At the beginning of the algorithm, the initial values forparameters σ, α, c, γ, A, and Λ0 are selected, c.f. Line 1. At the ith iteration of thealgorithm, the coefficients σi and ci are updated as in (4.12), c.f. Line 3. For the FDPSalgorithm, the gradient is approximated as in (4.11), c.f. Line 5. For the SPPS algorithm,the gradient is approximated as in (4.13), c.f. Line 7. Λi is updated as in (4.10), c.f.Line 9. The algorithm is stopped if the maximum number of allowed iterations is reachedor the difference between two subsequent values of the objective function is less than apre-determined threshold, c.f. Line 10.74Chapter 4. Real-Time Pricing for DSMAlgorithm 4.1 : Price selection algorithm executed at the PCU.1: Select initial value for σ, α, c, γ, A, and Λ0.2: repeat3: Update σi and ci as in (4.12).4: if (FDPS) then5: Calculate gˆi(Λi) as in (4.11).6: elseif (SPPS)7: Calculate gˆi(Λi) as in (4.13).8: end if9: Update Λi as in (4.10).10: until the stopping criteria4.3.4 Convergence of the AlgorithmsWe now present the conditions for convergence of Algorithm 4.1. Convergence of dif-ferent stochastic approximation based algorithms has been analyzed under various con-ditions. In particular, algorithms based on simultaneous perturbation stochastic approx-imation (SPSA) have attracted more attention, as they require fewer objective functionevaluations. Spall showed the convergence of SPSA under a three times differentiabilitycondition for the objective function [52]. However, it was shown later that weaker assump-tions suffice for SPSA to converge [92–94]. The iterative updating step in (4.10) can bewritten asΛi+1 = Λi − σi(g˜i(Λi) + ǫi), (4.14)where g˜i(Λi) is any subgradient of the objective function at the ith iteration, and ǫi rep-resents the observation noise and bias term. For differentiable functions, the subgradientg˜i(Λi) is identical to the gradient of the objective function. For non-differentiable func-tions, the sub-gradient of the objective function Q(·) at Λi is defined as any vector g thatsatisfies the inequality Q(Φ) ≥ Q(Λi) + gT(Φ − Λi) for all Φ. Following the discussion in[93, 94], the conditions for the iterative convergence of Λi to the optimum value Λ∗ thatminimizes the objective function are summarized as75Chapter 4. Real-Time Pricing for DSMA4.1 The domain of Q(·) is convex and closed. Q(·) is convex, and the expected valueE[Q(Λi)] is uniformly bounded, where E{·} denotes mathematical expectation.A4.2 For the step-size parameters we must have: a) σi > 0, b) ci > 0, c) σi → 0, d)ci → 0, e) ∑∞i=0 σi = ∞, and f)∑∞i=0(σi/ci)2 <∞.A4.3 Let Ii , (Λ0, . . . ,Λi). ∑∞i=0(σi)2E[‖ǫi‖2|Ii]<∞.A4.4 The subgradient g˜i is uniformly bounded.A4.5 ∆ij must be independent for all i and j, identically distributed for all j at each iter-ation i, symmetrically distributed about zero, and uniformly bounded in magnitudefor all i and j.Condition A4.1 specifies the criteria required for the convergence of the algorithm to theglobal optimum. Condition A4.2 determines the rate at which the gain σi has to decay.The gain σi should decay neither too fast nor too slow. It has to approach zero fast enoughto damp the effects of the noise as the algorithm gets closer to the solution Λ∗. However, ithas to approach zero at a sufficiently slow rate to ensure full convergence of the algorithm.Condition A4.3 ensures that the algorithm is able to cope with the noise. In practice,for large numbers of users, the effect of each individual user on the aggregate load of thesystem is small and the variations in the demand requirements of different users help inmaking the load curve smooth which also reduces the effects of the noise term. ConditionsA4.4 and A4.5 ensure that the algorithm is asymptotically an unbiased estimator of theoptimum value Λ∗ [94]. Condition A4.5 determines the randomization property of theperturbation vector such that the objective function can be effectively approximated by asmooth function at the points of non-differentiability [94].Together, conditions A4.1-A4.5 specify the ideal requirements for the convergence of thealgorithm. However, in practice, due to the lack of knowledge of the structure of Q(·), it is76Chapter 4. Real-Time Pricing for DSMvery difficult or even impossible to check these conditions. To resolve this issue, gradient-free techniques are adopted to optimize the objective function in this chapter. This alsoreveals the difficulty of verifying the above mentioned conditions. However, despite the factthat some conditions may not be verifiable, it has been shown that the adopted techniquesare among the most effective methods to optimize objective functions with an unknownformulation in practice [52]. Different methods have been proposed in the literature toensure that the stochastic approximation methods converge to the global optimum amongmultiple local optima. One of the well-known approaches is to inject an additive noise inthe right-hand side of the basic updating step in (4.10) [52, Ch. 6].4.4 System Simulator Unit (SSU)In this section, we explain the algorithm to be implemented in the SSU. This requiresan understanding of how the ECC device may operate for each user. We assume thatthe operation of ECC devices in each time slot begins with an admission control phase,where appliances send admission requests to the ECC unit. Once an admission requestis submitted, the state of the appliance changes from sleep to awake. The ECC unitschedules the operation of awake appliances such that the electricity expenses of the userare minimized.To simulate the users’ load patterns, the SSU simulates the time at which each appliancebecomes awake and also the time by which the operation of each appliance has to befinished. Such information can be obtained based on the sleep and awake history of eachappliance. To preserve the users’ privacy, we assume that the actual data is manipulatedsuch that the statistical information is preserved, but it is not possible to extract the exactinformation about the demand requirements of individual users [95, 96]. Various privacyaware smart metering techniques have been proposed in the literature, such as secure meter77Chapter 4. Real-Time Pricing for DSMdata aggregation [97], and privacy aware home energy management system [98]. By usingthe manipulated data, the SSU simulates the likely control decisions of the ECC unit ofeach user based on the price indicated by the PCU. We note that the SSU simulates thelikely behavior of general users, and each general user does not refer to any particular user.In the following, we first explain the control algorithm running in the ECC device ofeach user and then how the SSU simulates the control decisions of the ECC devices.4.4.1 Power Scheduling Done by ECC DevicesFor each user u, the power scheduling is done by the ECC device at the current timeslot t by solving the following optimization problem that is specific to user u and aims tominimize the expected energy cost in the upcoming time slots:V tu(Stu) = minimizextu,a ∈ X tu,∀ a ∈ Cku,∀ k∈T tgt(Stu, Ltu)+ E{V t+1u (St+1u ) | Stu}, (4.15)where T t , {t, . . . , T}, xtu,a , (xtu,a . . . , xTu,a), and we havegt(Stu, Ltu) , Ltuλt(Ltu), (4.16)Ltu =∑a∈Mtuγu,a +∑a∈Ctuγu,axtu,a. (4.17)We refer to V tu(·) as the value function of user u at time slot t, and V T+1u (·) , 0. Foreach user u, we also define the state of the system at time slot t as Stu , (Etu, Itu), whereItu , (Mtu, Ctu) and Etu , (Etu,1, . . . , Etu,|Au|). Here, Mtu and Ctu are the sets of must-run andcontrollable appliances of user u that are awake at time slot t, respectively. The feasible78Chapter 4. Real-Time Pricing for DSMset X tu in problem (4.15) is defined asX tu={xtu,a∣∣∣∣xku,a∈{0, 1}, ∀ a ∈ Cku , ∀ k ∈ T t,γu,aβu,a∑m=kxmu,a = Eku,a, ∀ a ∈ Cku , ∀ k ∈ T txku,a = 1, ∀ a∈N ku , ∀ k ∈T tu,a, 0 <Eku,a<Eu,a}, (4.18)where T tu,a , {t, . . . , βu,a}, and N ku denotes the non-interruptible subset of Cku . The firstterm in the objective function in (4.15) is the payment of the user in the current timeslot t for the known load Ltu, while the second term is the expected cost of energy in theupcoming time slots, which we will refer to as the cost-to-go. The feasible set in (4.18) issimilar to (4.4). However, it is based on the updated information which is available up totime slot t. An algorithm based on linear mixed-integer programming has been proposedin [51] to solve problem (4.15). However, its complexity makes it difficult to be used in theSSU.4.4.2 Simulation of ECC Operation at SSUIn order to mimic the operation of the ECC devices, the energy provider needs to similarlysolve optimization problem (4.15). However, this cannot be done because the energyprovider does not have access to the details regarding the users’ energy needs. To tacklethis problem, we propose an approximate dynamic programming algorithm to estimate thesolution of problem (4.15). First, we note that the state of user u in the next time slot,St+1u , depends on the current state Stu, the decision which is made at the current time slotxtu,a, and the exogenous information which arrives at the beginning of the next time slot79Chapter 4. Real-Time Pricing for DSMIt+1u . We defineStu,x = Sx(Stu,xtu,a), (4.19)St+1u = SI(Stu,x, It+1u ), (4.20)where Stu,x is the state of the system immediately after we make a decision and is referredto as post-decision state [82], Sx(·) is the state transition function which takes into accountthe effect of decisions, and SI(·) is the state transition function which takes into accountthe effect of arrival information.A well-known approach to approximate the cost-to-go is to represent it based on thepost-decision state Stu,x [82]. Problem (4.15) can now be written asVˆ tu(Stu) = minimizextu,a ∈ X tu,∀ a ∈ Ctugt(Stu, Ltu)+ Vˆ t+1u,x (Stu,x), (4.21)where Vˆ tu(·) is the approximation of the cost of being in state Stu, and Vˆ t+1u,x (·) is theapproximation of the cost-to-go by writing it as a function of post-decision state Stu,x ratherthan current state Stu. Since Stu,x is a deterministic function of xtu,a, problem (4.21) is adeterministic optimization problem. Among different techniques considered to approximatethe cost-to-go, parametric models [82] are particularly popular, where the value functionis replaced with a linear regression. Let φt(·) be a basis function which captures somefeatures of the underlying system at time slot t. We approximate the cost-to-go at thenext time slot asVˆ t+1u,x (Stu,x) =T∑k=t+1θkφk(x˜t+1u ), (4.22)80Chapter 4. Real-Time Pricing for DSMwhere θk is the weight coefficient at time slot k, x˜t+1u = (x˜t+1u,1 , . . . , x˜t+1u,|Au|), x˜t+1u,a = (x˜t+1u,a , . . . , x˜Tu,a),and we haveφk(x˜t+1u ) = gk(Stu,x, L˜ku), (4.23)L˜ku =∑a∈Mtuγu,a +∑a∈Ctuγu,ax˜ku,a. (4.24)Furthermore, we can calculate x˜t+1u as follows:x˜t+1u = argminxtu,a ∈ X¯ tu, ∀ a ∈ CtuT∑k=t+1θkgk(Stu,x, lku), (4.25)where X¯ tu is the feasible set defined by (4.18) while the state of the system is Sku,x and thefirst integer constraint in (4.18) is relaxed as 0 ≤ xku,a ≤ 1. lku is defined aslku =∑a∈Mtuγu,a +∑a∈Ctuγu,axku,a. (4.26)The basis functions φk(·) in (4.23) capture the estimate of the cost in future time slotsbased on the information which is available at the current time slot t. The cost-to-gothen is approximated as a weighted sum of the estimated cost of all upcoming time slots.However, as the new observations about the true cost of each time slot are revealed, theweight coefficients θ = (θ1, . . . , θT ) are updated accordingly, as we explain next.4.4.3 Updating the Value Function EstimationAssume that we have n different observations for the true value of being in different states(i.e., the observations from the real system at the end of the entire operation period) thatcan be written in vector form as (V mu , Smu )nm=1. Let φm be the vector of basis functionsevaluated at Smu , and Φn be a matrix with n rows, one corresponding to each observation,81Chapter 4. Real-Time Pricing for DSMand T columns, one for each feature. Let Vnu be a column vector with elements V mu . Byusing least square batch linear regression [82], we can update vector θ asθ =((Φn)TΦn)−1(Φn)TVnu, (4.27)where, T is the transpose operator. We note that at the end of the operation period, wehave multiple observations for different states of the system. The estimate of the valuefunction’s parameters can be improved if the observations of multiple operating periodsare used to update the θ. Moreover, the estimate of the value function’s parameters canbe further improved if users are able to communicate and share their observations to havemore samples to update the parameters of the value function. In practice, it may not bepossible to obtain the true observation of the cost-to-go from the real system because ofprivacy issues. To tackle this problem, the results produced by the SSU can be used toupdate the value function’s parameters. We note that in a real system, users are makingcontrol decisions based on the partial information available at the beginning of each timeslot. That is, the complete demand requirements in the future time slots are not known.The SSU simulates the behavior of each user for different scenarios. For each scenario, tobetter mimic the behavior of each user, the control decisions are similarly made based onpartial information available at the beginning of each time slot. Thus, similar to the realsystem, at each time slot, the exact cost-to-go is not known and only some estimation ofit is available. However, at the end of each scenario, the exact value of cost-to-go can beobserved. These observations can be used instead of true observation from the real systemto update the value function’s parameters.82Chapter 4. Real-Time Pricing for DSMAlgorithm 4.2 : The algorithm executed at the SSU.1: Initialize n.2: Receive price parameters Λ.3: Select initial value for vector θ.4: for u ∈ U5: for t ∈ T6: Determine appliances that become awakeand their demand requirements.7: Receive new information Itu.8: Determine xtu,a as the solution of (4.21).9: Update (Etu,1, . . . , Etu,|Au|) as in (4.5).10: end for11: Update θ as in (4.27).12: end for13: Determine the aggregate load of the system.4.4.4 Algorithm DescriptionWe now explain the steps of the proposed control algorithm (Algorithm 4.2) to be executedin the SSU. At the beginning, the value of n is initialized and the price parameters Λ arereceived from the PCU, c.f. Lines 1 and 2. Subsequently, the initial value for vector θ isselected randomly, c.f. Line 3. For each user u and at the beginning of each time slot t,the appliances that become awake are determined. The SSU also determines the demandrequirements of each appliance. That is, whether the appliance is must-run or controllableand also the deadline by which the operation of the appliance should be finished aredetermined. The lists of awake appliances are then updated, and the operation scheduleof the awake appliances for the current time slot t is calculated as the solution of problem(4.21), c.f. Lines 4 to 10. At the end of the operation period, we update vector θ asin (4.27). The aggregate load of the system in each time slot t is determined as L¯t =∑u∈U∑a∈Auγu,ax¯tu,a, where x¯tu,a is determined at time slot t as the solution of (4.21), c.f.Line 13.83Chapter 4. Real-Time Pricing for DSM4.5 Performance EvaluationIn this section, we present simulation results and assess the performance of our proposedprice control algorithm. Unless stated otherwise, the simulation setting is as follows. Weassume that the general RTP method combined with IBR is adopted as described in (4.7).We consider a system with |U| = 50 users. Each user possesses various must-run andcontrollable appliances. We assume that the exact information about the energy require-ments of the users is not known by the SSU. However, we assume that some statisticalinformation about the energy requirements of the users in form of distribution functions isavailable at the SSU. This statistical information includes the number of appliances, thenominal power consumption of each appliance, the probabilities with which each appliancebecomes awake in each time slot, and the deadline by which the operation of each appli-ance should be finished. The statistical information can be obtained from the operationalhistory of the real system. In the SSU, for a typical household user, we consider on average18 appliances. Some of the appliances and their operating specifications are summarized inTable 4.1. The time slot at which each appliance becomes awake is selected randomly froma pre-determined interval. Based on the demand requirements of the user, each appliancecan be set as must-run or controllable. This setting is decided by the user and can varyfrom time to time.In our simulation setting, we consider various must-run and controllable appliances[51]. For example, we consider electric stove, clothes dryer, and vacuum cleaner as non-interruptible appliances. Refrigerator and air conditioner are modeled as interruptibleappliances, and must-run appliances include: lighting, TV, etc. In general, the operationof some appliances can be correlated. However, taking such correlations into account foralgorithm design would make the implementation of the SSU significantly more complex,which may not be desirable in practice. Therefore, we assume that the operations of84Chapter 4. Real-Time Pricing for DSMappliances are independent. For controllable appliances, the operating deadline is selectedrandomly from the remaining feasible time slots.We note that the SSU does not observe the demand requirements of the users in the realsystem. Instead, it simulates the behavior of each user by running multiple scenarios. Tobetter simulates the decisions made by the user, for each scenario, the information aboutthe demand requirement of the user is updated gradually over time. That is, the SSUmimics the control decisions of the user based on the partial information available at thebeginning of each time slot. For each user u and at the beginning of each time slot t, wedetermine the appliances that become awake and their operating specifications. The listsof awake appliances are then updated, and the operation schedule of the awake appliancesfor the current time slot t is calculated as the solution of problem (4.21). The aggregateload of the system in each time slot t is determined asL¯t =∑u∈U∑a∈Auγu,ax¯tu,a, (4.28)where x¯tu,a is obtained at time slot t as the solution of (4.21). This procedure is repeatedfor multiple scenarios of the demand requirements of each user and the average results areconsidered.By testing different practical examples, it has been shown in [52] that α = 0.602 andγ = 0.101 are good choices for (4.12). To mitigate the effect of the measurement noise, weset c at a level approximately equal to the standard deviation of the measurement noisein Q(Λ). We set A equal to 10 percent of the maximum number of allowed iterations.Coefficient σ in (4.12) plays an important role in the convergence of the algorithm as ithas a significant effect on the step size in the different iterations. To select σ, first foreach element j of Λ, we determine the appropriate value of σj that keeps the range ofchanges in the jth element of Λ in an appropriate range. Second, to assure stability, we85Chapter 4. Real-Time Pricing for DSMTable 4.1: Operating specifications of different appliances.Eu,a (kWh) γu,a (kW) arrival intervalElectric stove 4.5 1.5 [06:00, 14:00]Clothes dryer 1 0.5 [14:00, 22:00]Vacuum cleaner 2 1 [06:00, 15:00]Refrigerator 2.5 0.125 [06:00, 09:00]Air conditioner 4 1 [12:00, 22:00]Dishwasher 2 1 [15:00, 24:00]Heater 6 1.5 [15:00, 03:00]Water heater 3 1.5 [06:00, 23:00]Pool pump 4 2 [12:00, 21:00]PEV 10 2.5 [16:00, 24:00]Lighting 3 0.5 [16:00, 24:00]TV 1 0.25 [16:00, 01:00]PC 1.5 0.25 [08:00, 24:00]Ironing appliance 2 1 [06:00, 16:00]Hairdryer 1 1 [06:00, 13:00]Other 6 1.5 [06:00, 24:00]set σ = min{σ1, . . . , σp}.4.5.1 Performance Gains for the Utility CompanyTo have a baseline to compare with, we consider a system without ECC deployment, whereeach appliance a starts operation right after it becomes awake at its nominal power γu,a.For the system without ECC deployment, users are not responding to the variations ofthe price parameters. Furthermore, as an upper bound on the performance of the energyprovider in minimizing the PAR of the aggregate load, we consider a system in whichthe energy provider knows all the demand requirements of the users and is capable ofcontrolling the ECC units of all the users. The energy provider schedules the operation ofall the appliances of the users such that all the demand requirements of the users are met.This system with direct load control achieves the minimum PAR of the aggregate load,86Chapter 4. Real-Time Pricing for DSMand since the energy provider has full control over the operation of the users’ appliances,the performance of the system is independent of the price parameters. We note that theexistence of a pricing scheme that can achieve this performance bound is not guaranteed.Since optimization problem (4.6) is too complex, we calculate a lower bound on the PARof the system with direct load control. That is, we treat all controllable appliances asif they are interruptible, and instead of solving the mixed integer program, we presentthe results for the corresponding continuous problem. Simulation results for the averagetotal power consumption of the proposed load control algorithms, the system without ECCdeployment, and the lower bound on the PAR of the system with direct load control aredepicted in Fig. 4.2. Simulation results for the average PAR of the aggregate load atdifferent iterations of the proposed SPPS pricing algorithm, the proposed FDPS pricingalgorithm, the system without ECC deployment, and a system with direct load control aredepicted in Fig. 4.3. The simulation results show that the PAR of the aggregate load forthe system without ECC deployment is on average 1.92. Our proposed SPPS algorithmreduces the PAR of the aggregate load to 1.58 (i.e., 18% reduction). Our proposed FDPSalgorithm reduces the PAR of the aggregate load to 1.49 (i.e., 22% reduction). The lowerbound on the achievable PAR of the system with direct load control is on average 1.2.Considering the number of time slots and the number of price parameters for each timeslot, the number of measurements of the FDPS algorithm is 72 times higher than for theSPPS algorithm.4.5.2 Performance Gain of the UsersFor the SSU, we propose a load control algorithm (Algorithm 4.2) which simulates theoperation of the ECC unit of each user. Since the SSU has to be fast enough and hasto deal with the complex system of multiple users, the proposed load control algorithm87Chapter 4. Real-Time Pricing for DSM0 5 10 15 20 25050100150Time (Hour)Average Load (kW) (a) Without ECC Deployment0 5 10 15 20 25050100150Time (Hour)Average Load (kW) (b) With ECC Deployment (SPPS)0 5 10 15 20 25050100150Time (Hour)Average Load (kW) (c) With ECC Deployment (FDPS)0 5 10 15 20 25050100Time (Hour)Average Load (kW) (d) Lower Bound on Direct Load ControlFigure 4.2: Aggregate load profile in different scenarios.1 2 3 4 5 6 7 8 9 10 11 12 13 14 1511.21.41.61.822.2IterationPAR  System without ECC deploymentProposed SPPS algorithmProposed FDPS algorithmSystem with direct load controlFigure 4.3: The PAR of the aggregate load in different scenarios.is based on an approximate dynamic programming approach. The proposed load controlalgorithm can be adopted in the ECC units of the user. Therefore, in this section, weassess the performance of the proposed load control algorithm. To have a baseline to88Chapter 4. Real-Time Pricing for DSMcompare with, we consider a system without ECC deployment, where each appliance ais assumed to start operation right after it becomes awake. As an upper bound, we alsoconsider the scheme in [51] in which problem (4.21) is solved to schedule the operation ofcontrollable appliances. Simulation results show that, to reduce electricity payment, theproposed control algorithm shifts the load to time slots with lower prices such as the fewfirst hours after midnight. However, the high price penalty for exceeding the bt thresholdprevents load synchronization as discussed in Section 4.1. The simulation results showthat the use of the proposed algorithm reduces the average daily payment of the user from$4.85 to $3.99. The average daily payment of the users for the load control algorithm in[51] is $3.88. We can see that the efficiency loss in our proposed scheme compared to theone in [51] is small, although, our design has less computational complexity and is faster.The running times of the proposed FDPS and SPPS algorithms are directly influenced bythe number of measurements of the objective function in each iteration and the runningtime of the SSU for each measurement. The SSU simulates the load pattern of each userto produce the aggregate load pattern of the users. This process can be done in parallelor sequentially. The running time of the SSU increases approximately linearly with thenumber of users if the load pattern of individual users is simulated sequentially. In thefollowing, we evaluate the complexity of the load control algorithm (Algorithm 4.2) whichsimulates the load pattern of each user for different numbers of appliances. In general,integer linear programs with n integer variables and m constraints are NP-complete. Thatis, the order of complexity grows exponentially with respect to n and m [88]. A completediscussion of algorithm complexity is beyond the scope of this chapter. However, to providea general idea about the complexity of our proposed algorithm compared to the one in [51],simulation results for the average running time and the average number of integer variablesfor both algorithms are presented in Table 4.2. The results were obtained by a computer89Chapter 4. Real-Time Pricing for DSMTable 4.2: Performance measures of different algorithms.Average run time of the algorithm (in seconds).|A|=20 |A|=30 |A|=40Proposed algorithm for SSU 0.7324 0.7673 0.7919Algorithm in [51] 2.1364 10.3071 69.5810Average number of integer variables.|A|=20 |A|=30 |A|=40Proposed algorithm for SSU 4 6 10Algorithm in [51] 57 90 129system with Intel(R) Core(TM) i7 CPU 3.07 GHz processor, 12 GB RAM, and Windows7 operating system. We note that the order of complexity is identified for the worst casescenario. However, in practice, by increasing the number of appliances, it is unlikely thatall appliances become awake at the same time. Thus, the running time of the algorithmwill not change significantly in each time slot for most practical scenarios.4.6 SummaryIn this chapter, we proposed two pricing algorithms based on stochastic approximationtechnique to minimize the PAR of the aggregate load. The proposed algorithms eliminatethe need to know the structure of the objective function. In our proposed pricing algo-rithms, we took into account the way users will respond to different price values. We alsoconsidered the effect of control decisions of the ECC unit on the users’ load profile. More-over, we proposed the use of an SSU. A load control algorithm based on the approximatedynamic programming approach is also proposed and executed at the SSU to simulate theoperation of the ECC unit at the demand side. The details of the demand requirements ofthe users at the appliance level are considered in the SSU. Simulation results showed that90Chapter 4. Real-Time Pricing for DSMour proposed algorithms reduce the PAR of the aggregate load. The proposed algorithmsprovide incentives for the users to reduce their energy expenses.91Chapter 5Load Scheduling and Power Tradingin Systems with High Penetration ofRenewable Energy Resources5.1 IntroductionRERs such as solar and wind are non-dispatchable, since they are random in nature. Insystems with high penetration of RERs, the power may flow from DGs to the substation,which negatively impacts the stability of the system. If the reverse power flow exceedsa certain threshold, it causes the voltage rise problem, which is a major challenge inintegrating a large number of DGs in the distribution network [35–37].To tackle the reverse power flow problem, it is desirable that users consume theirgenerating power locally rather than injecting the excess power back into the grid. Storagefacilities and DSM techniques can be adopted to shape the load pattern of the users tobetter match supply and demand [3, 24, 25, 51, 55]. Moreover, users are able to sell theirexcess power to other users. On the one hand, local power trading can benefit the users byproviding monetary revenue for them. On the other hand, it helps to absorb excess powerand to mitigate the reverse power flow problem.Different DSM programs have been designed to facilitate the integration of RERs into92Chapter 5. Load Scheduling and Power Tradingthe power grid, and the impact of different decision makers on the electricity market hasbeen studied [44–49, 99–102]. Most of the existing work in the literature considers the casewhere users can sell their excess generation back into the grid [48, 49, 102]. Despite itsimportance, the possibility of trading energy among local users and the related benefitsthat users may obtain due to competition between local generators have not been wellinvestigated.In this chapter, we focus on modeling the interaction between users that can sell andbuy locally generated electricity. In our model, users can offer their excess local generationcapacity to other users with an appropriately selected price. For a given user, the selectedprice and the offered generation capacity depend on both the marginal cost of the userand the price offered by other users. Thus, users form a game in which they aim tomaximize their own revenue. Due to the competition between multiple local generators,the consuming users may benefit from a lower price compared to the price advertised bythe utility company. Our main contributions in this chapter are as follows:• We consider a game theoretic approach to model the interaction of users with excesspower generation. Users compete to sell their extra generation to other local users.The revenue of competing users depends on their own marginal cost and the offersadvertised by other competing users. Thus, each competing user chooses its offeredprice and output generation such that its revenue is maximized.• We formulate the problem of selecting the offered price and output generation (i.e.,the trading problem) as a mixed-integer program. To tackle the complexity of thetrading problem, we adopt the generalized Benders’ decomposition approach.• We propose an approximate dynamic programming approach to schedule the oper-ation of must-run, interruptible controllable, and non-interruptible controllable ap-pliances. The linearity of the proposed approximated scheduling problem makes it93Chapter 5. Load Scheduling and Power Tradingpossible to schedule the operation of different appliances independently. Indepen-dent scheduling of appliances significantly reduces the complexity of the schedulingalgorithm and makes the real-time implementation of the algorithm possible.• Simulation results show that our proposed algorithm reduces the energy paymentof users compared to the case where trading is not applied. Our proposed schemefacilitates the integration of RERs and mitigates the reverse power flow problem byproviding the users an opportunity to trade their excess generation locally.The rest of this chapter is organized as follows. The system model is introduced in Sec-tion 5.2. In Section 5.3, the problem formulation and algorithm description are presented.Simulation results are provided in Section 5.4, and Section 5.5 concludes the chapter.5.2 System ModelWe consider a smart power system with a single utility company and several users. Eachuser is equipped with a renewable DG, such as photovoltaic cells or wind turbines. Thedemand requirements of the users are met by their local generation, imported power fromother users, and imported power from the utility company. We assume that the structureof underlaying power grid is such that users have the option to export their excess powergeneration back to the utility company or to the other users. Examples of such gridtopologies include micro-grids. The topology of these autonomous systems can be re-configured by their own control infrastructure. Moreover, the adjustable configuration ofthese systems makes it possible for the users to export their excess power generation tothe utility company or to the other users. We also assume that all users are equippedwith advanced metering infrastructure such that their imported and exported power canbe precisely measured. Let U denote the set of users. We assume that each user u ∈ U is94Chapter 5. Load Scheduling and Power Tradingequipped with an energy consumption controller (ECC) capable of scheduling and adjustingthe household energy consumption. The ECC units of all users are connected. We dividethe intended operation cycle into T , |T | time slots, where T , {1, . . . , T}.Let Au denote the set of all appliances of user u. We assume that based on the demandrequirements of the user, each appliance can be set as either must-run or controllable. Thissetting is decided by the user and can vary from time to time. The ECC has no control overthe operation of must-run appliances. In contrast, the operation of controllable appliancescan be delayed or interrupted if necessary. Each controllable appliance can be eitherinterruptible or non-interruptible. For interruptible appliance a, the ECC may delay orinterrupt its operation. However, for non-interruptible appliance a, it is only possible todelay its operation.At the beginning of a time slot, each appliance of user u that is about to start operationsends an admission request to the ECC unit. The admission request specifies whetherthe appliance is must-run or controllable and its operational specifications, i.e., Tu,a ,[αu,a, βu,a], where αu,a is the earliest time at which appliance a can start operating (i.e.,the time slot it becomes awake), and βu,a is the deadline by which the operation of appliancea has to be finished. The power consumption of each appliance can be different at differentcycles of its operation due to changes in the amount of current being absorbed. We definevector Pa , (P a1 , . . . , P aIa) as the power consumption pattern of appliance a if no schedulingis applied, where P ai is the power consumption of appliance a at its ith operating cycle,Ia , |Ia| is the number of operating cycles of appliance a, and Ia , {1, . . . , Ia}. We alsoassume that the duration of each operating cycle is one time slot. In practice, if the actualoperating cycle lasts for more than one time slot, this can be modeled by introducingmultiple consecutive operating cycles having identical values for the power consumption.An example for the pattern of power consumption of controllable appliance a before and95Chapter 5. Load Scheduling and Power Trading    ?  ?  ?  ?  ?  ?  Before scheduling After scheduling !",  #",  !",  #",  Time slots Time slots Figure 5.1: An example for the pattern of power consumption of interruptible controllableappliance a before and after scheduling.after scheduling is illustrated in Fig. 5.1.For each appliance a of user u, we define χu,at , (qu,at , wu,at ) as the state of appliance aat time slot t, where qu,at is the number of remaining operating cycles of appliance a, andwu,at is the number of time slots for which the operation of appliance a can be delayed. Wedefine xu,at ∈ {0, 1} as an indicator which shows whether appliance a of user u is scheduledto operate at time slot t (xu,at = 1) or not (xu,at = 0). The state of appliance a at thenext time slot t + 1, χu,at+1, can be inferred from its current state χu,at , its type, and theoperating decision xu,at . For a must-run appliance a, the initial state is χu,aαu,a = (Ia, 0). Amust-run appliance a starts operation immediately (i.e., xu,at = 1, if qu,at ≥ 1) and its stateχu,at+1 = (qu,at+1, 0) evolves asχu,at+1 =(qu,at − 1, 0), for qu,at > 0. (5.1)For a non-interruptible appliance a, it is only possible to delay its operation. Once ithas started operation, it is not possible to interrupt its operation. The initial state of a96Chapter 5. Load Scheduling and Power Tradingnon-interruptible appliance a is χu,aαu,a = (Ia, βu,a − αu,a − Ia + 1). The state evolves asχu,at+1 =(qu,at , wu,at − 1), if xu,at = 0, wu,at ≥ 1,(qu,at − 1, 0), if xu,at = 1, qu,at ≥ 1.(5.2)For an interruptible appliance a, it is not only possible to delay operation but also tointerrupt operation if required. The initial state of an interruptible appliance a is χu,aαu,a =(Ia, βu,a − αu,a − Ia + 1), and it evolves asχu,at+1 =(qu,at , wu,at − 1), if xu,at = 0, wu,at ≥ 1,(qu,at − 1, wu,at), if xu,at = 1, qu,at ≥ 1.(5.3)We also define χut = (χu,1t , . . . , χu,|Au|t ).To better utilize the RERs and match demand and supply, we assume that each user isequipped with a storage device such as a battery. We define Bb as the storage capacity ofthe battery. We assume that the maximum charging and discharging rates of the batteryare identical and denoted by eb. For time slot t, we define variable yut ∈ [−eb, eb] as thecharging / discharging rate of user u’s battery. Moreover, Λut is the charging state of useru’s battery at the beginning of time slot t. Thus, we haveΛut = Λu0 +t−1∑k=1yuk , (5.4)where Λu0 is the initial charging state of the battery. At any time slot t, the stored energycannot exceed the storage capacity Bb. Moreover, it is not possible to extract more energyfrom the storage unit than what is stored, i.e.,0 ≤ Λut ≤ Bb. (5.5)97Chapter 5. Load Scheduling and Power TradingLet gut denote the total power exported by user u at time slot t. Users may utilizedifferent technologies or different types of RERs to generate power. The intermittentnature of the RERs may cause problems regarding stability, voltage regulation, and powerquality. In general, the quality of the generated power needs to be enhanced before itcan be transmitted to other users. Different techniques have been proposed to improvethe quality of power which results in additional costs for generators [103]. Therefore, themaintenance and operation cost is different for different users. We consider a cost functionCut (gut ) indicating the cost of providing gut units of energy for user u at time slot t. Weassume that the cost function is increasing and strictly convex in the offered energy. Inthis chapter, we consider a quadratic cost function:Cut (gut ) = aut (gut )2 + but gut + cut , (5.6)where aut > 0 and but , cut ≥ 0 are pre-determined parameters.5.3 Problem Formulation and Algorithm DescriptionWe consider the problems of load scheduling and power trading. Each user schedules theoperation of its appliances to reduce its energy expenses. Primarily, each user uses its localgeneration to meet its own demand. If the local generation is not sufficient, then the userbuys energy from its neighbors and the utility company. On the other hand, users withexcess generation capacity compete with each other to sell their extra generations.We define λht as the price value set by the utility company for each time slot t. Werefer to users with excess generation as competing users. The advertised price of competingusers should be less than λht to be economically reasonable for buyers. Competing usersmay have different marginal production cost. Thus, their advertised prices can be different.98Chapter 5. Load Scheduling and Power TradingAmong the competing users, those with the smallest advertised price are selected to servethe demand. The selected competing users are referred to as providing users. Differentapproaches have been proposed in the literature to clear the market and pay the sellers.Providing users may sell their excess generation at their advertised price, or they mayadopt a market clearing price (MCP) to serve the demand [104]. MCP is the highestadvertised price among providing users. In our system model, we assume that the marketis cleared by an MCP. Moreover, competing users who are not selected as providing userscan still sell their extra generation back into the grid at a lower price λlt ≤ λht .5.3.1 Scheduling Problem FormulationWe assume that the exact information about the list of appliances that are awake in eachtime slot, whether they are must-run or controllable, and the deadline by which theiroperation has to be finished is revealed only gradually over time to the ECC units. Theoperating schedule of controllable appliances depends on the price of electricity for thecurrent time slot (i.e., the MCP). On the other hand, the MCP depends on the tentativeload schedule of each user and whether the user has excess generation or not. In general,it is difficult to formulate and solve the joint optimization problem for determining theMCP and the operating schedule of the controllable appliances. To tackle this problem,we determine the operating schedule of the appliances and the MCP in two stages, i.e., thescheduling stage and the trading stage.At the scheduling stage, we assume that the operating schedule of the controllableappliances is determined based on the estimated MCP for each time slot. Each userestimates the average MCP for each time slot based on its observations from past operatingperiods. This estimate can be different for different users as the effects of both selling andbuying energy are taken into account. In this stage, users determine whether they haveexcess generation or have to acquire energy from neighboring users. However, at the99Chapter 5. Load Scheduling and Power Tradingtrading stage, competing users compete and the exact MCP for the current time slot t isdetermined. At the trading stage, competing users prefer to sell their excess generationto their neighbors rather than to the utility company, as they can make more profit byselling at a price higher than λlt. Moreover, the consuming users may also benefit fromlocal trading because the competing users may reduce their offered price compared to λhtto obtain a larger share of the market. We defineLut =∑a∈AuP aIa−qu,at +1xu,at + yut − ψut (5.7)as the load of user u at time slot t, where ψut is the amount of generated power of user uat time slot t. For user u ∈ U at time slot t ∈ T , we define vt(χut , Lut)as the payment ofthe user for the known load Lut :vt(χut , Lut)= µtLut jut +(µtfut + λlt(1− fut ))Lut (1− jut )=(µtjut +(µtfut +λlt(1−fut ))(1−jut ))Lut , (5.8)where µt is the MCP at time slot t, jut is a binary variable specifying whether Lut ≥ 0(jut = 1) or not (jut = 0), and fut denotes the portion of generated power which is processedand sold to neighboring users at price µt.For each user u, the power scheduling is done by its ECC unit at current time slot t bysolving the following optimization problem, which aims to minimize the expected energycost in the upcoming time slots:Vut (χut )=minimizexut ∈ Xut ,yut ∈ Yutvt(χut , Lut)+E{Vut+1(χut+1) | χut}, (5.9)100Chapter 5. Load Scheduling and Power Tradingwhere E{·} denotes the expectation with respect to the demand and generation uncertain-ties in upcoming time slots, xut , (xu,1t . . . , xu,|Au|t ), Xut is the set of actions available foreach appliance a at state χut , and Yut , which is the feasible operating set of the battery, isdefined asYut ={yut | yut ∈ [−eb, eb], 0 ≤ Λut ≤ Bb}. (5.10)vt(χut , Lut)is as (5.8), while the second term on the right hand side of (5.9) is the expectedcost of energy in the upcoming time slots, which we will refer to it as the cost-to-go. Werefer to Vut (·) as the value function of user u at time slot t, and VuT+1(·) , 0. Considering(5.8), we defineθut (χt) , µtjut +(µtfut + λlt(1− fut ))(1− jut ) (5.11)as the effective MCP for user u at time slot t. θut (·) incorporates the effects of bothelectricity payment and electricity revenue for user u. θut (·) depends on the scheduling andtrading decisions of user u, the decisions of other users, and the realizations of randomevents (i.e., the power generation from RERs and the demand requirements of the users).Thus, it is very difficult to calculate θut (·) directly. To tackle this problem, we propose anapproximate dynamic programming approach to estimate the solution of problem (5.9).One approach to approximate the value function is to adopt parametric models [82]. Thevalue function is replaced with a linear regression. Problem (5.9) can be approximated asVˆut (χut ) =minimizexut ∈ Xut ,yut ∈ Yutηut Lut + E{Vˆut+1(χut+1) | χut}, (5.12)where ηut is the weight coefficient of user u at time slot t. A comparison of (5.9) and(5.12) reveals that the coefficient ηut approximates the function θut (χt) in (5.8). However,101Chapter 5. Load Scheduling and Power Tradingas new observations about the true value function for each time slot are revealed, theweight coefficients ηut are updated accordingly, as will be explained later in this section.The linearity of (5.12) makes it possible to calculate the optimal values of xu,at and yutindependently, and thus, to separate the scheduling process of individual appliances. Thatis, for each individual appliance a, we need to solve the following dynamic program:Vˆu,at (χu,at ) =minimizexu,at ∈ Xu,atηut P aIa−qu,at +1xu,at + Vˆu,at+1(χu,at+1), (5.13)where Xu,at is the set of actions available for appliance a at state χu,at , and Vˆu,at (χu,at ) isthe approximate value function for appliance a in state χu,at . When state χu,at is equal to(0, wu,at ), Vˆu,at (χu,at ) = 0 since the operation of the appliance is finished. Problem (5.13)can be solved by backward induction.For operation of the battery, due to the continuity of the decision variables, it is moreconvenient to represent its scheduling process in the form of an optimization problemVˆu,bt (Λut ) = minimizeyuk ∈ Yuk ,k ∈ Tt∑k∈Ttηukyuk , (5.14)where Vˆu,bt (Λut ) is the approximate value function for the battery in state Λut , and Tt ,{t, . . . , T}.We assume that at the end of the operation period, the true value function for thewhole operation period can be observed (i.e., the total electricity cost for all T time slots).We denote the true value function for user u as Vu. However, based on the vector ofvalue function parameters, ηu = (ηu1 , . . . , ηuT ), and the total load vector in each time slot,102Chapter 5. Load Scheduling and Power TradingLu = (Lu1 , . . . , LuT ), the approximated value function isVˆu = LTuηu, (5.15)where T is the transpose operator. After the true value function has been observed, thisnew information is used to adjust the old estimate of parameter ηu. Let m denote thenumber of observations obtained so far. We define Vu,m, Vˆu,m, ηu,m, and Lu,m as thevalues of Vu, Vˆu, ηu, and Lu corresponding to the mth observation, respectively. As thenew (m+ 1)th observation arrives, we update the value function parameters based on therecursive least square method, i.e.,ηu,m+1 = ηu,m +HmLu,m+11δ + LTu,m+1HmLu,m+1(Vu,m+1 − Vˆu,m+1),whereVˆu,m+1 = LTu,m+1ηu,m,andHm+1 = Hm −HmLu,m+1LTu,m+1Hm1δ + LTu,m+1HmLu,m+1.Here, H0 is a positive definite matrix, and 0 < δ < 1 is the observation weight. We notethat the influence of the recent observations decreases more rapidly for smaller values of δ.5.3.2 Trading Problem FormulationIn this section, we consider the trading stage and focus on the competing users and howthey interact. If the aggregate excess generation of the competing users is more than thedemand, the competing users choose their offered price and generation such that they will103Chapter 5. Load Scheduling and Power Tradingbe selected as providing users, and their payoff will be maximized. The competing usersalso take into account the offers advertised by other competing users. In our system model,users do consider the effect of their actions on the MCP. Thus, we need to analyze the Nashequilibrium of the game played among multiple competing users who compete to have someshare of the market. In this game theoretic model, the strategy of each user consists of itsoffered price and generation for sale to other users. Let Gt = {1, . . . , Nt} be the set of allcompeting users at time slot t, where Nt , |Gt|. Moreover, G−ut , Gt \{u} is defined as theset of all competing users other than user u. We denote the offer of competing user u asOut , (πut , gut ), where πut is the offered price and gut is the offered generation capacity. Wedefine O−ut , (Ont |n ∈ G−ut ) as the vector of offers advertised by all competing users otherthan user u. The information about the offers of the other users, i.e., O−ut is received byuser u. Without loss of generality, we assume that the elements of vector O−ut are sortedin an ascending order based on the entries πnt , n ∈ G−ut .User u chooses its offer Out such that it will be selected as a providing user and its payoffis maximized. To identify whether offer Out will place user u among the providing users ornot, the ranking of offer Out among other offers O−ut has to be evaluated. We adopt thebinary auxiliary variable znt , n ∈ G−ut , to indicate whether the offered price πnt is lower orequal to the selected price πut (znt = 1) or not (znt = 0). Thus,rut =∑n∈G−utznt (5.16)indicates the number of users with lower offered prices than user u (i.e., the rank of offerOut among other offers O−ut ). To calculate binary variable znt , the following constraint isadded to the trading optimization problemπutπnt> znt , ∀ n ∈ G−ut . (5.17)104Chapter 5. Load Scheduling and Power TradingIf πnt > πut , constraint (5.17) ensures that znt = 0, i.e., the constraint is active. If theconstraint is inactive, i.e., πnt ≤ πut , znt can be either 0 or 1. To enforce znt = 1 whilethe constraint is inactive, an auxiliary term is added to the objective of the optimizationproblem such that, znt is set to 1. To this end, a term −K1znt is added to the objectiveof the user’s minimization problem, where K1 is a large positive constant. That is, whileconstraint (5.17) is inactive, znt is set to 1 for minimization of the objective function.Starting from the user with the smallest offered price, competing users will be addedto the set of providing users until there is enough generation to serve the demand. In thiscase, the MCP will be equal to the highest offered price among the group of providingusers. We define Snt , n ∈ Gt, as a group of competing users with offered price less thanor equal to πnt . The MCP will be equal to πnt , n ∈ Gt, if the following two conditions aresatisfied:C5.1 The aggregate generation of the users within Snt , n ∈ Gt, is sufficient to meet thedemand.C5.2 Among all groups that satisfy condition C5.1, Snt has the smallest number of members.Condition C5.2 ensures that the process of adding competing users to the set of providingusers will be stopped if we have enough generation to meet the demand. If the aggregategeneration of all competing users is less than the total demand, all competing users willbe selected as providing users and the MCP will be equal to the price advertised by theutility company.We define Snt , n ∈ Gt, asSnt =∑i∈Sntgit (5.18)105Chapter 5. Load Scheduling and Power Trading=∑ni=1 git + (1− znt )gut , if n ∈ G−ut ,∑i∈G−ut zitgit + gut , if n = u(5.19)to denote the aggregate generation of the users within Snt . For each group Snt , n ∈ Gt,we assign a binary auxiliary variable dnt to indicate whether the MCP is set to the offeredprice πnt (dnt = 1) or not (dnt = 0). We also define auxiliary variable d0t which plays thesame role as dnt for the utility company’s price λht . The MCP is finally selected from oneof the advertised prices πnt or λht . Thus, we have∑n∈Gtdnt + d0t = 1. (5.20)To enforce condition C5.1 for evaluating the MCP, the constraintSntDt≥ dnt , ∀ n ∈ Gt (5.21)is added to the trading optimization problem, where Dt is the total demand at time slott. If Snt < Dt, then constraint (5.21) is active and dnt = 0. If constraint (5.21) is inactive,i.e., Snt ≥ Dt, dnt can be either 0 or 1. To satisfy constraint (5.20) and to enforce conditionC5.2 for evaluating the MCP, one of the variables dnt , n ∈ Gt, or d0t has to be set to 1 ifits corresponding constraint (5.21) is inactive and the associated set Snt has the smallestnumber of members. To this end, an auxiliary term K2(∑n∈G−ut ndnt + (Nt + 1)d0t + rut dut)is added to the objective function of the trading optimization problem, where K2 is a largepositive constant. For the added term, the coefficients of the binary variables dnt , n ∈ Gt,are equal to the size of the groups Snt . Thus, to minimize the objective function, among thevariables dnt , n ∈ Gt, for which the corresponding constraint (5.21) is inactive, the one withthe smallest weight is set to 1. However, if the corresponding constraint (5.21) is active106Chapter 5. Load Scheduling and Power Tradingfor all variables dnt , n ∈ Gt, variable d0t will be set to 1. Finally, to evaluate the payoff ofuser u, we define the auxiliary variable ft which indicates whether the offer Out will placeuser u in the set of providing users (ft = 1) or not (ft = 0).Given O−ut , each competing user u solves the following optimization problem to calcu-late its offered price and generation capacityminimizeIt,CtF(It,Ct) (5.22a)subject to ft, d0t , dnt , znt , dut ∈ {0, 1}, ∀ n ∈ G−ut , (5.22b)constraints (5.17), (5.20), (5.21), (5.22c)∑n∈Gt dnt πnt + d0tλhtπut≥ ft, (5.22d)λlt ≤ πut ≤ λht , (5.22e)0 ≤ gut ≤ Gut , (5.22f)where It = (dt, zt, ft), Ct = (gut , πut ), dt , (d0t , dnt |n ∈ Gt), zt , (znt |n ∈ G−ut ), andF(It,Ct) =Cut (gut )−(∑n∈Gtdnt πnt + d0tλht)gut ft−λlt(Gut −gut)−K1∑n∈G−utznt −K2ft +K2(∑n∈G−utndnt + (Nt + 1)d0t + rut dut), (5.23)where K1 ≫ K2, and Gut is the maximum generation capacity of user u at time slot t. Thefirst term in (5.23) is the cost of providing gut units of energy for the intended user u, c.f.(5.6). The second and the third terms reflect the revenue of user u for the offer (πut , gut ).The termµt =∑n∈Gtdnt πnt + d0tλht (5.24)is equal to the MCP. Constraint (5.22d) checks whether or not the considered user u is107Chapter 5. Load Scheduling and Power Tradingselected as a providing user. If the offered price πut is greater than the MCP, then useru is not a providing user (ft = 0). Otherwise, ft can be either 0 or 1. In this case, asft appears in the objective function with a negative sign, it will be set to ft = 1. Theoffered price cannot exceed the price advertised by the utility company and the amount ofgeneration cannot exceed the total generation capacity as reflected by (5.22e) and (5.22f),respectively.Problem (5.22) is a mixed-integer program. By adopting the generalized Benders’decomposition approach [105], problem (5.22) can be re-written asminimizeItV(It) (5.25a)subject to (5.20), (5.22b), (5.25b)πu∗tπnt≥ znt , ∀ n ∈ G−ut , (5.25c)Sn∗tDt≥ dnt , ∀ n ∈ Gt, (5.25d)∑n∈G−ut dnt πnt + dut πu∗t + d0tλhtπu∗t≥ ft, (5.25e)whereV(It) = minimizeCtF(It,Ct) (5.26a)subject to (5.22c)-(5.22f), (5.26b)and problem (5.26) should be feasible for the set of complicating variables It that are heldfixed. Here, C∗t = (πu∗t , gu∗t ) is the solution of (5.26), and Sn∗t is as in (5.18), where Ct isset to C∗t .The procedure for solving problem (5.22) is as follows:108Chapter 5. Load Scheduling and Power TradingStep 1 Let I0t be an initial vector of complicating variable It for which problem (5.26)is feasible. Solve subproblem (5.26) to obtain optimal vector C∗t . BFS = F(I0t ,C∗t ) isthe best value of problem (5.22) found so far, and V(It) = F(It,C∗t ) forms the objectivefunction of problem (5.25). Select the convergence tolerance parameter ǫ > 0.Step 2 Solve problem (5.25) to obtain I∗t and V(I∗t ). If |V(I∗t )−BFS| < ǫ, terminate.Step 3 Solve subproblem (5.26) to obtain C∗t for the complicating variables found in Step2, I∗t . If |F(I∗t ,C∗t )−BFS| < ǫ, terminate. If F(I∗t ,C∗t ) ≤ BFS, update BFS = F(I∗t ,C∗t ).Return to Step 2.We note that for a fixed value of It, problem (5.26) is a convex quadratic optimizationproblem and can be solved efficiently by convex optimization techniques. Moreover, V(It) isbounded. Furthermore, problem (5.25) is a quadratic integer program, which can be solvedefficiently with optimization software such as MOSEK [84]. Following the discussion in[105], the adopted generalized Benders’ decomposition procedure converges to the optimumvalue. The proof of the following theorem can be found in [105].Theorem 5.1 For a finite discrete vector It, the generalized Benders’ decompositionprocedure to solve (5.22) terminates in a finite number of steps for any given ǫ > 0.5.3.3 Market Clearing GameFrom problem (5.22), the payoff of each user depends on its offer (πut , gut ) as well as theoffers of the other users. Hence, we have the following game among the users:• Players: Competing users.• Strategies: Each user selects its offered price and generating capacity (πut , gut ) tominimize its cost.109Chapter 5. Load Scheduling and Power Trading• Costs: The cost of each user is determined based on optimization problem (5.22).In the proposed market clearing game, first, each competing user assumes randomoffers for other competing users O−ut . This assumption is required since at the beginning,competing user u has no prior information about the other users. Next, each competinguser u solves its own local problem (5.22). That is, each user plays its best response to theoffers advertised by other users. Each competing user broadcasts its new offer through thecommunication infrastructure. We note that each user broadcasts its offer only if it hasbeen changed compared to its previous offer. Moreover, it will update its local informationabout the offers of the other users whenever it receives a broadcast message. This procedurecontinues until no competing user changes its offer.5.3.4 Algorithm DescriptionIn this section, we explain the steps of the proposed algorithm for load scheduling andpower trading. At the beginning, the list of the appliances that should be scheduledis updated, c.f. Line 1. Based on the estimated MCP, the operating schedule of eachappliance is determined as in (5.13). Moreover, the charging and discharging rate of thebattery is calculated as in (5.14), c.f. Line 2. At the end of the scheduling stage, the userdetermines whether it has excess generation or not. Users with excess generation receivethe information about the offers of other competing users. Each competing user solves(5.22) by adopting the generalized Benders’ decomposition approach to obtain Out . Usersupdate their offered price and generation in response to the advertised prices by othercompeting users. This process continues until the users reach a Nash equilibrium of thetrading game as described in Section 5.3.3, c.f. Lines 4 to 7. Users that are selected asproviding users sell gut units of their extra generation to consuming users at the MCP,c.f. Line 9. Competing users that are not selected as providing users can sell their excess110Chapter 5. Load Scheduling and Power TradingAlgorithm 5.1: Load scheduling and power trading algorithm executed at each time slott ∈ T for user u ∈ U .1: Update the list of the appliances that are to be scheduled.2: Schedule the appliances as in (5.13) and (5.14).3: if there is excess generation4: repeat5: Receive offers of other users O−ut .6: Solve (5.22) to obtain the offer Out .7: until the Nash equilibrium of the trading game isreached8: if selected as a providing user9: Sell gut units of excess generation to other users atthe MCP.10: end if11: Sell the remaining generation to the grid at price λlt.12: end ifgeneration back to the grid at the lower price λlt, c.f. Line 11.5.4 Performance EvaluationIn this section, we present simulation results and assess the performance of our proposedDSM program. We consider a system with |U| = 10 users. Each user possesses variousmust-run and controllable appliances. We assume that the information about the energyrequirements of the users is not known at the beginning of the operation period. Thatis, the list of appliances that are awake in each time slot, whether they are must-runor controllable, and the deadline by which the operation of each appliance has to befinished are not known a priori. We run the simulation multiple times with differentpatterns for the times at which the appliances become awake. We then present the averageresults. For a typical user, we consider on average 16 appliances. We consider differentpower consumptions for different operation cycles of the appliances. The pattern of powerconsumption of the appliances is known to the ECC. Some of the appliances and their111Chapter 5. Load Scheduling and Power Tradingoperating specifications are summarized in Table 5.1. In our simulation settings, we assumethat λht varies between 12 cents/kWh and 24 cents/kWh for off-peak and on-peak time slots,respectively. The parameter λlt is set to 4 cents/kWh. The cost function parameters autand but are different for different users varying between 0.1 and 0.6, and cut is set to 0, c.f.(5.6).To have a baseline to compare with, we consider a system without ECC deploymentand trading opportunity, where each appliance a starts operation with its power pattern Padirectly after it has sent an admission request to the ECC unit. In this model, the excessgeneration of each user is sold to the utility company if it is not consumed or stored. For thesystem without ECC deployment, users are not responding to the variations of the priceparameters. In order to be able to better evaluate the effect of trading, we also consider asystem in which each users is equipped with an ECC unit to schedule the operation of itscontrollable appliances, but is not able to trade its excess generation with other users.Simulation results for the average total power imported from the utility company forthe proposed load scheduling algorithm, the system without ECC deployment and trading,and the system with ECC deployment but without trading are depicted in Fig. 5.2. Theaverage imported energy for the system without ECC deployment and trading is 367.2kWh, while this value is 349.0 kWh for the system in which users are equipped withECCs but cannot trade. The patterns of power consumption of the latter two systemsare different since the system with ECC deployment shifts most of the load to low pricetime slots. Our proposed load scheduling algorithm reduces the average imported energyto 222.8 kWh because of the trading among the users. The average electricity cost ofthe users for the system without ECC deployment and trading is $60.93. For the systemwith ECC deployment but without trading, this value is reduced to $53.81. Our proposedalgorithm further reduces the electricity cost of the users to $36.77. The advantages of theproposed algorithm are twofold. First, users are able to decrease their energy expenses by112Chapter 5. Load Scheduling and Power TradingTable 5.1: Operating specifications of different appliances.average P ai (kW) arrival intervalElectric stove 1.5 [06:00, 14:00]Clothes dryer 0.5 [14:00, 22:00]Vacuum cleaner 1 [06:00, 15:00]Refrigerator 0.125 [06:00, 09:00]Air conditioner 1 [12:00, 22:00]Dishwasher 1 [15:00, 24:00]Heater 1.5 [15:00, 03:00]Water heater 1.5 [06:00, 23:00]Pool pump 2 [12:00, 21:00]Electric vehicle 2.5 [16:00, 24:00]Lighting 0.5 [16:00, 24:00]TV 0.25 [16:00, 01:00]PC 0.25 [08:00, 24:00]Ironing appliance 1 [06:00, 16:00]Hairdryer 1 [06:00, 13:00]Other 1.5 [06:00, 24:00]selling their excess generation to other users with a price higher than λlt. Second, buyersmay also benefit from the price reduction due to the competition between multiple sellers.Our proposed DSM program encourages the utilization of RERs by providing a tradingopportunity for the users. To evaluate the effect of the proposed algorithm on the amountof power being injected back into the grid (i.e., the reverse power flow) due to the mismatchbetween supply and demand, we show in Fig. 5.3 the reverse power flow as a function ofthe percentage of users that are equipped with RERs. Fig. 5.3 shows that the amount ofreverse power flow is significantly reduced for the proposed algorithm.Due to the competition between the users, the electricity may be offered at a price lowerthan the price advertised by the utility company. To better understand the effect of thecompetition between the users on the MCP, we focus on a simplified model in which a singletime slot is considered, and three competing users try to sell their excess generation to servea demand of Dt = 10 kW. We consider two different scenarios. In the first scenario, each113Chapter 5. Load Scheduling and Power Trading0 5 10 15 20 25051015202530Proposed AlgorithmTime (Hour)Average Load (kW)0 5 10 15 20 25051015202530Without ECC Deployment and Trading Time (Hour)Average Load (kW)0 5 10 15 20 25051015202530With ECC Deployment but without Trading Time (Hour)Average Load (kW)Figure 5.2: Average imported power from utility company for different scenarios.10 20 30 40 50 60 70 80 90 100020406080100120140160180200Percentage of Users with RERsReverse Power Flow (kW)  Without ECC Deployment and TradingWith ECC Deployment but without TradingProposed AglorithmFigure 5.3: Reverse power flow vs. the percentage of users equipped with RERs.competing user has enough generation to meet the demand (i.e., Gut = 12 kW), whereasin the second scenario, the generation capacity of each user is not sufficient to meet thetotal demand (i.e., Gut = 6 kW). We assume λht = 12 cents/kWh, and the cost parameters114Chapter 5. Load Scheduling and Power Trading0.5 1 1.5 202468101214Parameter a1t of the First UserMarketClearingPrice(Cents/kWh)  Case 1Case 2Figure 5.4: MCP for Gut = 12 kW (Case 1) and Gut = 6 kW (Case 2).of the last two users are fixed. Simulation results for the MCP for different values of thefirst user’s parameter aut in (5.6) are depicted in Fig. 5.4. The parameter aut for the lasttwo users is set to 0.6. For the first scenario, if the production cost of the first user is lowenough, the user prefers to reduce its production and shares a small portion of the marketwith other competing users with higher offered prices to keep the price as high as possibleand maximize its revenue. On the other hand, if the production costs of the users arecomparable, the users will also share the market. In this case, the MCP will drop due tothe competition between the users. When the generating capacity of each individual useris not sufficient to meet the total demand, the users will share the market and try to keepthe price high to maximize their revenue.5.5 SummaryIn this chapter, we proposed a load control algorithm for DSM. We considered the prob-lem of joint load scheduling and power trading. An approximate dynamic program wasproposed to schedule the operation of different types of appliances, and a game theoretic115Chapter 5. Load Scheduling and Power Tradingapproach was adopted to model the interaction of the users with excess power generation.Users with excess power generation choose their offered price and output generation suchthat they obtain a larger share of the market and their revenue is maximized. Simulationresults showed that our proposed algorithm reduces the energy costs of the users. Thatis, competing users may sell their extra generation to local users at a price higher thanthe buying price of the utility company, and consuming users may buy the electricity fromneighboring users at a price lower than the selling price of the utility company. Moreover,the possibility to trade facilitates the integration of RERs by encouraging the users toconsume their excess generation locally which mitigates the reverse power flow problem.116Chapter 6Conclusions and Future WorkIn this chapter, we summarize the results and highlight the contributions of this thesis.We also suggest several topics for future work.6.1 Research Contributions• In Chapter 2, we proposed a VCG mechanism for DSM. The proposed algorithmencourages efficient energy consumption among users aiming at maximizing the ag-gregate utility of all users while minimizing the total cost of power generation. Someof the main properties of the proposed mechanism such as truthfulness, efficiency,and nonnegative transfer were studied. We also compared our proposed VCG mech-anism with the case where users are price taker. We studied the differences of thesetwo systems, especially from the user payment perspective, and showed that for theVCG mechanism users paid less. Simulation results confirmed that both the usersand the energy provider benefited from the proposed scheme.• In Chapter 3, we proposed an optimal residential load control algorithm for DSM inpresence of load uncertainty. Our proposed algorithm aimed to minimize the elec-tricity payment of the users while only some estimate of the future demand wasavailable. We focused on a scenario where real-time pricing was combined with in-clining block rate tariffs to balance residential load to achieve a low PAR. We studiedthe operational constraints of a variety of appliances including must-run appliances,117Chapter 6. Conclusions and Future Workand interruptible and non-interruptible controllable appliances. Simulation resultsshowed that our proposed scheduling algorithm with load uncertainty reduced theenergy payment of users compared to the case where no scheduling algorithm wasadopted. Our proposed scheme also improved the overall power system performanceby reducing the PAR in aggregate load demand.• In Chapter 4, we proposed two pricing algorithms based on stochastic approximationtechnique. The proposed algorithms aimed to minimizing the PAR in the aggregateload demand under the practical scenario where the utility company was uncertainabout the users’ price-responsiveness. The proposed algorithms were to be imple-mented in a price control unit based on the information provided the system sim-ulator unit. The system simulator unit considered the effect of control decisions ofthe ECC unit on the users’ load profile. That is, a load control algorithm basedon the approximate dynamic programming approach was proposed to simulate theoperation of the ECC unit at the demand side. Simulation results showed that ourproposed algorithms reduce the PAR of the aggregate load. The proposed algorithmsprovided incentives for the users to reduce their energy expenses.• In Chapter 5, we focused on the problem of joint load scheduling and power tradingin systems with high penetration of renewable energy resources. We proposed anapproximate dynamic programming approach to schedule the operation of must-run as well as the interruptible and non-interruptible controllable appliances. Weshowed that the operation of different appliances can be scheduled independentlywhich significantly reduced the complexity of the scheduling algorithm and made thereal-time implementation of the algorithm possible. Furthermore, we adopted a gametheoretic approach to model the interaction of users with excess power generation.Users with excess power generation choose their offered price and output generation118Chapter 6. Conclusions and Future Worksuch that they obtained a larger share of the market and their revenue was maximized.Simulation results showed that our proposed algorithm reduced the electricity cost ofthe users compared to the case where scheduling and trading were not applied. Ourproposed scheme facilitated the integration of RERs and mitigated the reverse powerflow problem by providing the users an opportunity to trade their excess generationlocally.6.2 Suggestions for Future WorkIn the following, we discus several possibilities for extension of the current work.1. The effect of malicious users: In Chapter 2, we proposed a VCG mechanism tomaximize the social welfare of the users. The ideas developed in this chapter can beextended in several directions. For example, a system with multiple energy providerscan be considered. The effect of malicious users can be explored as well.2. Suboptimal algorithm for load scheduling: In Chapter 3, we proposed an opti-mal load control algorithm for DSM. The problem is formulated as a mixed-integerprogram. However, in situations where computational complexity or convergencetime of the algorithm are critical such as in real-time applications, a suboptimal butfaster scheme that establishes a balance between simple implementation and adequateperformance is desirable. One direction could be designing and analyzing subopti-mal algorithms. Approximate algorithms and heuristics are examples of suboptimalalgorithms. The efficiency loss of these algorithms can be analyzed, and if possiblesome bounds on the performance of these algorithms are determined.3. Pricing algorithm in systems with different objectives: In Chapter 4, weassumed that all users are equipped with ECC units and try to minimize their energy119Chapter 6. Conclusions and Future Workexpenses. In practice, some users may schedule their power consumption to achievedifferent objectives such as minimizing their energy expenses, maximizing the socialwelfare, etc. In general, some users may be equipped with automated control unitswhile others make control decisions manually. To obtain a better estimate of thelikely behavior of the users, for the SSU, considering users with different objectivesand different levels of price-responsiveness is an interesting topic for future work.That is, the SSU needs to implement and simulate the likely load control algorithmsfor different types of users. These algorithms may seek different objectives withdifferent levels of complexity. The SSU needs to establish a balance between theaccuracy of estimations and the simple and fast implementation. Thus, differentsuboptimal algorithms can be adopted to mimic the DSM algorithms controlling theload pattern of the users.4. Different market structures for local trading: In Chapter 5, we considered asystem where users are able to trade their excess generation locally. One directionto extend this idea could be investigating the performance of systems with differentmarket structures in which users trade their excess generation. For example thescenario in which the market is not cleared at a unified MCP and each seller can sellits excess generation as its offered price can be considered.120Bibliography[1] “IEEE guide for smart grid interoperability of energy technology and informationtechnology operation with the electric power system (EPS), end-use applications,and loads,” IEEE Std 2030-2011, pp. 1–126, Oct. 2011.[2] A. Ipakchi and F. Albuyeh, “Grid of the future,” IEEE Power Energy Mag., vol. 7,no. 2, pp. 52–62, Mar. 2009.[3] K. Wang, F. Ciucu, C. Lin, and S. H. Low, “A stochastic power network calculusfor integrating renewable energy sources into the power grid,” IEEE J. on SelectedAreas in Comm., vol. 30, no. 6, pp. 1037–1048, Jul. 2012.[4] A. M. L. da Silva, L. C. Nascimento, M. A. da Rosa, D. Issicaba, and J. Lopes,“Distributed energy resources impact on distribution system reliability under loadtransfer restrictions,” IEEE Trans. on Smart Grid, vol. 3, no. 4, pp. 2048–2055, Dec.2012.[5] H. Nunna and S. Doolla, “Demand response in smart distribution system with mul-tiple microgrids,” IEEE Trans. on Smart Grid, vol. 3, no. 4, pp. 1641–1649, Dec.2012.[6] J. M. Guerrero, F. Blaabjerg, T. Zhelev, K. Hemmes, E. Monmasson, S. Jemei,M. P. Comech, R. Granadino, and J. I. Frau, “Distributed generation: Toward anew energy paradigm,” IEEE Industrial Electronics Mag., vol. 4, no. 1, pp. 52–64,Mar. 2010.[7] Y. Atwa, E. El-Saadany, M. Salama, and R. Seethapathy, “Optimal renewable re-sources mix for distribution system energy loss minimization,” IEEE Trans. on PowerSystems, vol. 25, no. 1, pp. 360–370, Feb. 2010.[8] S. Suryanarayanan, F. Mancilla-David, J. Mitra, and Y. Li, “Achieving the smart gridthrough customer-driven microgrids supported by energy storage,” Proc. of IEEEInt’l. Conf. on Industrial Technology, pp. 884–890, Mar. 2010.[9] C. Gellings, “The concept of demand-side management for electric utilities,” Pro-ceedings of the IEEE, vol. 73, no. 10, pp. 1468–1470, Oct. 1985.[10] B. Ramanathan and V. Vittal, “A framework for evaluation of advanced direct loadcontrol with minimum disruption,” IEEE Trans. on Power Systems, vol. 23, no. 4,pp. 1681–1688, Oct. 2008.121Bibliography[11] A. H. Mohsenian-Rad, V. W. S. Wong, J. Jatskevich, R. Schober, and A. Leon-Garcia, “Autonomous demand-side management based on game-theoretic energyconsumption scheduling for the future smart grid,” IEEE Trans. on Smart Grid,vol. 1, no. 3, pp. 320–331, Dec. 2010.[12] A. H. Mohsenian-Rad and A. Leon-Garcia, “Optimal residential load control withprice prediction in real-time electricity pricing environments,” IEEE Trans. on SmartGrid, vol. 1, no. 2, pp. 120–133, Sep. 2010.[13] M. Fahrioglu and F. Alvarado, “Designing incentive compatible contracts for effectivedemand management,” IEEE Trans. on Power Systems, vol. 15, no. 4, pp. 1255–1260,Nov. 2000.[14] N. Ruiz, I. Cobelo, and J. Oyarzabal, “A direct load control model for virtual powerplant management,” IEEE Trans. on Power Systems, vol. 24, no. 2, pp. 959–966,May 2009.[15] R. Faranda, A. Pievatolo, and E. Tironi, “Load shedding: A new proposal,” IEEETrans. on Power Systems, vol. 22, no. 4, pp. 2086–2093, Nov. 2007.[16] A. Conejo, J. Morales, and L. Baringo, “Real-time demand response model,” IEEETrans. on Smart Grid, vol. 1, no. 3, pp. 236–242, Dec. 2010.[17] T. Jin and M. Mechehoul, “Ordering electricity via Internet and its potentials forsmart grid systems,” IEEE Trans. on Smart Grid, vol. 1, no. 3, pp. 302–310, Dec.2010.[18] M. Alizadeh, A. Scaglione, and R. Thomas, “From packet to power switching: Digitaldirect load scheduling,” IEEE J. on Selected Areas in Comm., vol. 30, no. 6, pp.1027–1036, Jul. 2012.[19] T. Logenthiran, D. Srinivasan, and T. Shun, “Demand side management in smartgrid using heuristic optimization,” IEEE Trans. on Smart Grid, vol. 3, no. 3, pp.1244–1252, Sep. 2012.[20] T. H. Yoo, H. G. Kwon, H. C. Lee, C. Rhee, Y. T. Yoon, and J. Park, “Developmentof reliability based demand response program in Korea,” in Proc. of IEEE InnovativeSmart Grid Technologies, Anaheim, CA, Jan. 2011.[21] M. Shinwar and A. Youssef, “A water-filling based scheduling algorithm for the smartgrid,” IEEE Trans. on Smart Grid, vol. 3, no. 2, pp. 710–719, Jun. 2012.[22] M. Crew, C. Fernando, and P. Kleindorfer, “The theory of peak-load pricing: Asurvey,” Journal of Regulatory Economics, vol. 8, no. 3, pp. 215–248, Nov. 1995.122Bibliography[23] S. Zeng, J. Li, and Y. Ren, “Research of time-of-use electricity pricing models inChina: A survey,” in Proc. of IEEE Int’l. Conf. on Industrial Engineering and En-gineering Management, Singapore, Dec. 2008.[24] C. Chen, K. G. Nagananda, G. Xiong, S. Kishore, and L. V. Synder, “Acommunication-based appliance scheduling scheme for consumer -premise energymanagement systems,” IEEE Trans. on Smart Grid, vol. 4, no. 1, pp. 56–65, Mar.2013.[25] S. Salinas, M. Li, and P. Li, “Multi-objective optimal energy consumption schedulingin smart grids,” IEEE Trans. on Smart Grid, vol. 4, no. 1, pp. 341–348, Mar. 2013.[26] G. Xiong, C. Chen, S. Kishore, and A. Yener, “Smart (in-home) power schedulingfor demand response on the smart grid,” in Proc. of IEEE PES Innovative SmartGrid Technologies Conf., Anaheim, CA, Jan. 2011.[27] R. Krishnan, “Meters of tomorrow,” IEEE Power and Energy Magazine, pp. 92–94,Mar. 2008.[28] J. Chen, B. Yang, and X. Guan, “Optimal demand response scheduling with Stack-elberg game approach under load uncertainty for smart grid,” in Proc. of IEEE Int’lConf. on Smart Grid Communications, Tainan, Taiwan, Nov. 2012.[29] N. Li, L. Chen, and S. H. Low, “Optimal demand response based on utility maxi-mization in power networks,” in Proc. of IEEE Power and Energy Society GeneralMeeting, Detroit, MI, Jul. 2011.[30] M. Pedrasa, T. Spooner, and I. MacGill, “Scheduling of demand side resources usingbinary particle swarm optimization,” IEEE Trans. on Power Systems, vol. 24, no. 3,pp. 1173–1181, Aug. 2009.[31] P. Reiss and M. White, “Household electricity demand, revisited,” Review of Eco-nomic Studies, vol. 72, no. 3, pp. 853–883, July 2005.[32] S. Borenstein, “Equity effects of increasing-block electricity pricing,” Center for theStudy of Energy Markets Working Paper, vol. 180, Nov. 2008.[33] BC Hydro, Electricity Rates, Mar. 10, 2015. [Online]. Available:http://www.bchydro.com/about/planning regulatory/tariff filings.html[34] D. Hurlbut, State Clean Energy Practices: Renewable Portfolio Standards. NationalRenewable Energy Laboratory, 2008.[35] P. M. S. Carvalho, P. F. Correia, and L. A. F. M. Ferreira, “Distributed reactivepower generation control for voltage rise mitigation in distribution networks,” IEEETrans. on Power Systems, vol. 23, no. 2, pp. 766–772, May 2008.123Bibliography[36] R. A. Walling, R. Saint, R. C. Dugan, J. Burke, and L. A. Kojovic, “Summary ofdistributed resources impact on power delivery systems,” IEEE Trans. on PowerDelivery, vol. 23, no. 3, pp. 1636–1644, Jul. 2008.[37] R. Tonkoski, D. Turcotte, and T. El-Fouly, “Impact of high PV penetration onvoltage profiles in residential neighborhoods,” IEEE Trans. on Sustainable Energy,vol. 3, no. 3, pp. 518–527, May 2012.[38] S. Bahramirad, W. Reder, and A. Khodaei, “Reliability-constrained optimal sizingof energy storage system in a microgrid,” IEEE Trans. on Smart Grid, vol. 3, no. 4,pp. 2056–2062, Dec. 2012.[39] Z. Xu, X. Guan, Q. S. Jia, J. Wu, D. Wang, and S. Chen, “Performance analysisand comparison on energy storage devices for smart building energy management,”IEEE Trans. on Smart Grid, vol. 3, no. 4, pp. 2136–2147, Dec. 2012.[40] M. Pedrasa, T. Spooner, and I. MacGill, “Coordinated scheduling of residential dis-tributed energy resources to optimize smart home energy services,” IEEE Trans. onSmart Grid, vol. 1, no. 2, pp. 134–143, Sep. 2010.[41] T. T. Kim and H. V. Poor, “Scheduling power consumption with price uncertainty,”IEEE Trans. on Smart Grid, vol. 2, no. 3, pp. 519–527, Sep. 2011.[42] S. Tiptipakorn and W. Lee, “A residential consumer-centered load control strategyin real-time electricity pricing environment,” in Proc. of North American PowerSymposium, Las Cruces, NM, Oct. 2007.[43] S. Kishore and L. Snyder, “Control mechanisms for residential electricity demand insmartgrids,” in Proc. of IEEE Int’l. Conf. on Smart Grid Communications, Gaithers-burg, MD, Oct. 2010.[44] B. Chai, J. Chen, Z. Yang, and Y. Zhang, “Demand response management withmultiple utility companies: A two-level game approach,” IEEE Trans. on SmartGrid, vol. 5, no. 2, pp. 722–731, Mar. 2014.[45] P. Thimmapuram and J. Kim, “Consumers’ price elasticity of demand modeling witheconomic effects on electricity markets using an agent-based model,” IEEE Trans.on Smart Grid, vol. 4, no. 1, pp. 390–397, Mar. 2013.[46] H. Akhavan-Hejazi and H. Mohsenian-Rad, “Optimal operation of independent stor-age systems in energy and reserve markets with high wind penetration,” IEEE Trans.on Smart Grid, vol. 5, no. 2, pp. 1088–1097, Mar. 2014.[47] A. Thatte, L. Xie, D. Viassolo, and S. Singh, “Risk measure based robust biddingstrategy for arbitrage using a wind farm and energy storage,” IEEE Trans. on SmartGrid, vol. 4, no. 4, pp. 2191–2199, Dec. 2013.124Bibliography[48] S. Kahrobaee, R. Rajabzadeh, L.-K. Soh, and S. Asgarpoor, “A multiagent model-ing and investigation of smart homes with power generation, storage, and tradingfeatures,” IEEE Trans. on Smart Grid, vol. 4, no. 2, pp. 659–668, Jun. 2013.[49] K. Yang and A. Walid, “Outage-storage tradeoff in frequency regulation for smartgrid with renewables,” IEEE Trans. on Smart Grid, vol. 4, no. 1, pp. 245–252, Dec.2012.[50] P. Samadi, A. H. Mohsenian-Rad, R. Schober, and V. W. S. Wong, “Advanceddemand side management for the future smart grid using mechanism design,” IEEETrans. on Smart Grid, vol. 3, no. 3, pp. 1170–1180, Sep. 2012.[51] P. Samadi, A. H. Mohsenian-Rad, V. W. S. Wong, and R. Schober, “Tackling theload uncertainty challenges for energy consumption scheduling in smart grid,” IEEETrans. on Smart Grid, vol. 4, no. 2, pp. 1007–1016, Jun. 2013.[52] J. Spall, Introduction to Stochastic Search and Optimization: Estimation, Simulation,and Control. John Wiley & Sons, 2003, vol. 64.[53] P. Samadi, H. Mohsenian-Rad, V. W. S. Wong, and R. Schober, “Real-time pricingfor demand response based on stochastic approximation,” IEEE Trans. on SmartGrid, vol. 5, no. 2, pp. 789–798, March 2014.[54] M. Alizadeh, A. Scaglione, R. Thomas, and D. Callaway, “Information infrastructurefor cellular load management in green power delivery systems,” in Proc. of IEEE Int’l.Conf. on Smart Grid Communications, Brussels, Belgium, Oct. 2011.[55] P. Samadi, A. H. Mohsenian-Rad, R. Schober, V. W. S. Wong, and J. Jatskevich,“Optimal real-time pricing algorithm based on utility maximization for smart grid,”in Proc. of IEEE Int’l. Conf. on Smart Grid Communications, Gaithersburg, MD,Oct. 2010.[56] S. Yang and B. Hajek, “VCG-Kelly mechanisms for allocation of divisible goods:Adapting VCG mechanisms to one-dimensional signals,” IEEE J. on Selected Areasin Comms., vol. 25, no. 6, pp. 1237–1243, Aug. 2007.[57] S. Su and M. van der Schaar, “On the application of game-theoretic mechanismdesign for resource allocation in multimedia systems,” IEEE Trans. on Multimedia,vol. 10, no. 6, pp. 1197–1207, Oct. 2008.[58] J. Jia, Q. Zhang, Q. Zhang, and M. Liu, “Revenue generation for truthful spectrumauction in dynamic spectrum access,” in Proc. of the Tenth ACM Int’l Symposiumon Mobile Ad Hoc Networking and Computing, New Orleans, LA, May 2009.[59] N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, Algorithmic Game Theory.Cambridge University Press, 2007.125Bibliography[60] S. Caron and G. Kesidis, “Incentive-based energy consumption scheduling algorithmsfor the smart grid,” in Proc. of IEEE Int’l. Conf. on Smart Grid Communications,Gaithersburg, MD, Oct. 2010.[61] C. Ibars, M. Navarro, and L. Giupponi, “Distributed demand management in smartgrid with a congestion game,” in Proc. of IEEE Int’l. Conf. on Smart Grid Commu-nications, Gaithersburg, MD, Oct. 2010.[62] S. Stoft, Power System Economics: Designing Markets for Electricity. Wiley-IEEEPress, 2002.[63] ——, “The demand for operating reserves: Key to price spikes and investment,”IEEE Trans. on Power Systems, vol. 18, no. 2, pp. 470–477, May 2003.[64] P. Visudhiphan and M. Ilic, “Dynamic games-based modeling of electricity markets,”in IEEE Power Engineering Society 1999 Winter Meeting, New York, NY, Feb. 1999.[65] A. Mas-Colell, M. D. Whinston, and J. R. Green, Microeconomic Theory, 1st ed.USA: Oxford University Press, 1995.[66] M. Fahrioglu and F. Alvarado, “Using utility information to calibrate customer de-mand management behavior models,” IEEE Trans. on Power Systems, vol. 16, no. 2,pp. 317–322, May 2001.[67] A. Philpott and E. Pettersen, “Optimizing demand-side bids in day-ahead electricitymarkets,” IEEE Trans. on Power Systems, vol. 21, no. 2, pp. 488–498, May 2006.[68] H. Chao, “Demand response in wholesale electricity markets: The choice of customerbaseline,” J. of Regulatory Economics, vol. 39, no. 1, pp. 1–21, Nov. 2010.[69] M. Fahrioglu, M. Fern, and F. Alvarado, “Designing cost effective demand man-agement contracts using game theory,” in Proc. of IEEE Power Eng. Soc. WinterMeeting, New York, NY, Jan. 1999.[70] A. Wood and B. Wollenberg, Power Generation, Operation, and Control. New York:Wiley-Interscience, 1996.[71] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press,2004.[72] S. Low and D. Lapsley, “Optimization flow control I: Basic algorithm and conver-gence,” IEEE/ACM Trans. on Networking, vol. 7, no. 6, pp. 861–874, Dec. 1999.[73] R. Johari, S. Mannor, and J. Tsitsiklis, “Efficiency loss in a network resource alloca-tion game: The case of elastic supply,” IEEE Trans. on Automatic Control, vol. 50,no. 11, pp. 1712–1724, Nov. 2005.126Bibliography[74] R. Johari and J. Tsitsiklis, “A scalable network resource allocation mechanism withbounded efficiency loss,” IEEE J. on Selected Areas in Comms., vol. 24, no. 5, pp.992–999, May 2006.[75] Y. Shoham and K. Leyton-Brown, Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, 2008.[76] R. Johari and J. Tsitsiklis, “Communication requirements of VCG-like mechanisms inconvex environments,” in Proc. of Allerton Conference on Communication, Control,and Computing, Monticello, IL, Sep. 2005.[77] ——, “Efficiency of scalar-parameterized mechanisms,” Operations Research, vol. 57,no. 4, pp. 823–839, May 2009.[78] R. Ferrero and S. Shahidehpour, “Short-term power purchases considering uncertainprices,” IEE Proceedings of Generation, Transmission and Distribution, vol. 144,no. 5, pp. 423–428, Sep. 1997.[79] T. Hubert and S. Grijalva, “Realizing smart grid benefits requires energy optimiza-tion algorithms at residential level,” in Proc. of IEEE Innovative Smart Grid Tech-nologies, Anaheim, CA, Jan. 2011.[80] M. Parvania and M. Fotuhi-Firuzabad, “Demand response scheduling by stochasticSCUC,” IEEE Trans. on Smart Grid, vol. 1, no. 1, pp. 89–98, Jun. 2010.[81] K. Cheung and R. Rios-Zalapa, “Smart dispatch for large grid operations with inte-grated renewable resources,” in Proc. of IEEE Innovative Smart Grid Technologies,Anaheim, CA, Jan. 2011.[82] W. Powell, Approximate Dynamic Programming: Solving the Curses of Dimension-ality. Wiley-Blackwell, 2007.[83] D. Bertsekas, Dynamic Programming and Optimal Control. Athena Scientific Bel-mont, MA, 2005.[84] “MOSEK,” http://www.mosek.com, Mar. 10, 2015.[85] U.S. Department of Energy, The 2010 Buildings Energy Data Book. Energy Effi-ciency and Renewable Energy, Mar. 2011.[86] “U.S. Energy Information Administration,” Mar. 10, 2015. [Online]. Available:http://www.eia.gov[87] C. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms andComplexity. Courier Dover, 1998.127Bibliography[88] C. Papadimitriou, “On the complexity of integer programming,” J. of the ACM,vol. 28, no. 4, pp. 765–768, Oct. 1981.[89] P. Samadi, R. Schober, and V. W. S. Wong, “Optimal energy consumption schedulingusing mechanism design for the future smart grid,” in Proc. of IEEE Int’l. Conf. onSmart Grid Communications, Brussels, Belgium, Oct. 2011.[90] M. Roozbehani, M. Dahleh, and S. Mitter, “Volatility of power grids under real-timepricing,” IEEE Trans. on Power Systems, vol. 27, no. 4, pp. 1926–1940, Nov. 2012.[91] J. Liu, Y. Xiao, S. Li, W. Liang, and C. Chen, “Cyber security and privacy issuesin smart grids,” IEEE Comm. Surveys and Tutorials, pp. 981–997, Fourth quarter2012.[92] L. Gerencser, G. Kozmann, and Z. Vago, “SPSA for non-smooth optimization withapplication in ECG analysis,” in Proc. of IEEE Conference on Decision and Control,Tampa, FL, Dec. 1998.[93] Y. He, M. C. Fu, and S. I. Marcus, “Convergence of simultaneous perturbationstochastic approximation for nondifferentiable optimization,” IEEE Trans. on Auto-matic Control, vol. 48, no. 8, pp. 1459–1463, Aug. 2003.[94] F. Yousefian, A. Nedic´, and U. V. Shanbhag, “On stochastic gradient and subgradientmethods with adaptive steplength sequences,” Automatica, vol. 48, no. 1, pp. 56–67,Jan. 2012.[95] Y. Kim, E. Ngai, and M. Srivastava, “Cooperative state estimation for preservingprivacy of user behaviors in smart grid,” in Proc. of IEEE Int’l. Conf. on Smart GridCommunications, Brussels, Belgium, Oct. 2011.[96] T. Chim, S. M. Yiu, L. C. K. Hui, and V. O. K. Li, “PASS: Privacy-preservingauthentication scheme for smart grid network,” in Proc. of IEEE Int’l. Conf. onSmart Grid Communications, Brussels, Belgium, Oct. 2011.[97] F. Li, B. Luo, and P. Liu, “Secure information aggregation for smart grids usinghomomorphic encryption,” in Proc. of IEEE Int’l. Conf. on Smart Grid Communi-cations, Gaithersburg, MD, Oct. 2010.[98] G. Kalogridis, C. Efthymiou, S. Denic, T. Lewis, and R. Cepeda, “Privacy for smartmeters: Towards undetectable appliance load signatures,” in Proc. of IEEE Int’l.Conf. on Smart Grid Communications, Gaithersburg, MD, Oct. 2010.[99] Z. Ding, Y. Guo, D. Wu, and Y. Fang, “A market based scheme to integrate dis-tributed wind energy,” IEEE Trans. on Smart Grid, vol. 4, no. 2, pp. 976–984, Jun.2013.128Bibliography[100] I. Lampropoulos, N. Baghina, W. Kling, and P. Ribeiro, “A predictive control schemefor real-time demand response applications,” IEEE Trans. on Smart Grid, vol. 4,no. 4, pp. 2049–2060, Dec. 2013.[101] N. Gatsis and G. Giannakis, “Decomposition algorithms for market clearing withlarge-scale demand response,” IEEE Trans. on Smart Grid, vol. 4, no. 4, pp. 1976–1987, Dec. 2013.[102] I. Atzeni, L. Ordonez, G. Scutari, D. Palomar, and J. Fonollosa, “Demand-side man-agement via distributed energy generation and storage optimization,” IEEE Trans.on Smart Grid, vol. 4, no. 2, pp. 866–876, Jun. 2013.[103] M. Singh, V. Khadkikar, A. Chandra, and R. K. Varma, “Grid interconnection ofrenewable energy sources at the distribution level with power-quality improvementfeatures,” IEEE Trans. on Power Delivery, vol. 26, no. 1, pp. 307–315, Jan. 2011.[104] V. Krishna, Auction Theory, 2nd ed. Academic Press, 2009.[105] A. M. Geoffrion, “Generalized Benders decomposition,” J. of Optimization Theoryand Applications, vol. 10, no. 4, pp. 237–260, 1972.129Appendix AProof of Proposition 2.3Given the payment in (2.22), since user n cannot affect the term hn by changing Iˆn, itdeclares Iˆn only to maximizeWn(xn(Iˆ), tn(Iˆ)) = Un(∑k∈Kxkn(Iˆ))+∑m∈N−nUˆm(∑k∈Kxkm(Iˆ))−∑k∈KCk(∑m∈Nxkm(Iˆ)).However, the above expression is bounded above bymaximizexn∈Xn, xm∈Xˆm,m∈N−nUn(∑k∈Kxkn)+∑m∈N−nUˆm(∑k∈Kxkm)−∑k∈KCk(∑m∈Nxkm).Note that x(ˆI) satisfies (2.21), and user n can achieve the maximum payoff by truthfullydeclaring Iˆn = In for solving (2.21). Since this optimal strategy does not depend onthe demand information declared by other users, it confirms the result that for VCGmechanisms, truthful declaration is a dominant strategy. 130Appendix BProof of Theorem 2.1In the equilibrium, all users declare their demand information truthfully. Then, we canwrite the payment of user n astn(I) =−∑m∈N−nUm(∑k∈Kxkm(I))−∑k∈KCk(∑m∈Nxkm(I))+∑m∈N−nUm(∑k∈Kxkm(I−n))−∑k∈KCk(∑m∈N−nxkm(I−n)),where x(I−n) is the optimal solution for the social objective when user n is excluded fromthe system. So, we have∑m∈N−nUm(∑k∈Kxkm(I−n))−∑k∈KCk(∑m∈N−nxkm(I−n))≥∑m∈N−nUm(∑k∈Kxkm(I))−∑k∈KCk(∑m∈N−nxkm(I)). (B.1)Furthermore, from Assumption 2.1, Ck(·) is an increasing function. Therefore, we have∑m∈N−nUm(∑k∈Kxkm(I−n))−∑k∈KCk(∑m∈N−nxkm(I−n))≥∑m∈N−nUm(∑k∈Kxkm(I))−∑k∈KCk(∑m∈Nxkm(I)), (B.2)and thus (2.24) is nonnegative. 131Appendix CProof of Theorem 2.2In the equilibrium, all users declare their demand information truthfully. So, the paymentof user n istn(I) =−∑m∈N−nUm(∑k∈Kxkm(I))−∑k∈KCk(∑m∈Nxkm(I))+∑m∈N−nUm(∑k∈Kxkm(I−n))−∑k∈KCk(∑m∈N−nxkm(I−n)).Since x(I) is the optimal solution for the social objective problem, the optimality conditionsof (2.21) imply thatλ∗k = pk(∑n∈N xkn(I)),U ′n(∑k∈Kxkn(I))= λ∗k, if xkn(I) > mkn and∑k∈Kxkn(I) > En,U ′n(∑k∈Kxkn(I))≤ λ∗k, if xkn(I) = mkn or∑k∈Kxkn(I) = En,(C.1)where pk(·) has been introduced in (2.8), and λ∗k is the market clearing price for the problem(2.10).132Appendix C. Proof of Theorem 2.2By concavity of Un we haveUn(x) ≥ U ′n(x)x,Un(x)−Un(y)U ′n(x)≤ x− y,(C.2)and by convexity of Ck, we haveCk(q1) ≤ C ′k(q1)q1,Ck(q1)−Ck(q2)C′k(q1)≥ q1 − q2.(C.3)Then, from (C.1)-(C.3), we havetn ≤∑m∈N−nλ∗k[Um(∑k∈Kxkm(I))− Um(∑k∈Kxkm(I−n))]U ′m(∑k∈Kxkm(I))−∑k∈Kλ∗k[Ck(∑m∈N−nxkm(I−n))− Ck(∑m∈Nxkm(I))]pk(∑m∈Nxkm(I))≤∑k∈Kλ∗kxkn(I),which completes the proof. 133

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0167156/manifest

Comment

Related Items