Towards Optimal Planning and Scheduling in Smart Homes

Muhammad Raisul Alam¹, Marc St-Hilaire², Thomas Kunz¹

¹Department of Systems and Computer Engineering, Carleton University, Ottawa, Canada.
²School of Information Technology, Carleton University, Ottawa, Canada.

DOI: 10.4236/sgre.2019.107012                

Abstract

This research addresses the planning and scheduling problem in and among the smart homes in a community microgrid. We develop a bi-linear algorithm, named ECO-Trade to generate the near-optimal schedules of the households’ loads, storage and energy sources. The algorithm also facilitates Peer-to-Peer (P2P) energy trading among the smart homes in a community microgrid. However, P2P trading potentially results in an unfair cost distribution among the participating households. To the best of our knowledge, the ECO-Trade algorithm is the first near-optimal cost optimization algorithm which considers the unfair cost distribution problem for a Demand Side Management (DSM) system coordinated with P2P energy trading. It also solves the time complexity problem of our previously proposed optimal model. Our results show that the solution time of the ECO-Trade algorithm is mostly less than a minute. It also shows that 97% of the solutions generated by the ECO-Trade algorithm are optimal solutions. Furthermore, we analyze the solutions and identify that the algorithm sometimes gets trapped at a local minimum because it alternately sets the microgrid price and quantity as constants. Finally, we describe the reasons of the cost increase by a local minimum and analyze its impact on cost optimization.

Keywords

Smart Homes, Community Microgrid, Demand Side Management (DSM), Peer-to-Peer (P2P) Energy Trading, Bi-Linear Optimization

1. Introduction

The significance of smart home research is growing rapidly because of increasing industrial demand. In North America, the forecasted annual growth rate of smart homes is 23.1%, resulting in 63 million smart homes by 2022 [1] . In 2017, the market revenues of smart homes were $12 billion and within the next five years, the market is expected to reach $36 billion [1] . The healthcare service providers consider the smart home as an effective way of providing healthcare services, especially to the elderly and disabled who do not require intensive healthcare supports. Future smart homes will be connected to various service providers to automate and optimize services. Smart grid is one of the examples of service integration, which aims at optimizing the residential electricity usage according to energy demand and supply. People spend a significant amount of time in their households, which attracts potential investors to promote the integration of all possible services into traditional homes. Current trends indicate that smart homes are gradually becoming the centers for intelligent service consumption.

This research addresses the planning and scheduling problem in smart homes. It also considers the interactions between the smart homes in a community microgrid. In the smart homes, the prosumers generate energy from the renewables (e.g., solar panels, miniature wind turbines, etc.) and store energy into energy storage systems (e.g., electric vehicles, home energy storage, etc.). A network of interconnected smart homes in a neighborhood forms a community microgrid which enables peer-to-peer (P2P) energy trading among themselves. This research emphasizes on energy source, storage and load scheduling in smart homes to increase energy efficiency and minimize the energy costs. Figure 1 illustrates a community microgrid infrastructure formed by smart homes.

This research integrates Demand Side Management (DSM) with P2P energy trading in a community microgrid. However, P2P energy trading may create a cost fairness issue. It means that a household cost when it trades energy in the microgrid is sometimes higher than the cost when it does not participate. This issue may discourage end-users from participating in energy trading. We address this unfair cost distribution problem by assuring Pareto optimality among the households in the microgrid.

Figure 1. Community microgrid—a network of smart homes.

In our previous study, we developed an optimal model to solve this multi-objective cost optimization problem [2] . The optimal model is a non-convex Mixed Integer Non-Linear Programming (MINLP) model and we showed that even for the small and relatively trivial problems, the solution times of the optimal model became intractable, i.e., solution times increase exponentially with the increase of the problem sizes [2] . Therefore, using the optimal model is not practical to solve the real-world problems. To overcome this limitation, we develop a near-optimal algorithm, named ECO-Trade which can solve this optimization problem with lower computation time [3] . Our results show that the solution time of the proposed algorithm is very low, mostly less than a minute, compared to the optimal model which sometimes takes hours. It also shows that, for real and synthetic datasets, at least 97% of the solutions generated by the proposed algorithm are optimal solutions. Therefore, we can conclude that the ECO-Trade algorithm is a better alternative to the optimal model considering both accuracy and solution time.

Furthermore, in contrast to our previous paper [3] where we identified the impact of peer-to-peer trading, this paper analyzes the conditions when the proposed ECO-Trade algorithm breaks down and generates sub-optimal solutions. We analyze the solutions and identify that the proposed algorithm sometimes gets trapped at a local minimum because it alternately sets the microgrid price and microgrid quantity as constants. We describe the reasons of the cost increase by a local minimum and analyze its impact on cost optimization. This analysis may help the future researcher to improve the proposed algorithm.

The reminder of this article is organized as follows. Section 2 identifies the research gap and discusses the significance of the ECO-Trade optimization algorithm. Section 3 describes the ECO-Trade algorithm. Section 4 presents the results using synthetic and real datasets. Section 5 analyzes the conditions for sub-optimal solutions. Section 6 discusses the impact of a local minimum on cost optimization. Finally, Section 7 concludes the article, summarizing our contributions.

2. Literature Review

An energy cost optimization problem is typically formulated as a linear or non-linear optimization model. Linear programming is widely used to solve linear optimization models [4] [5] [6] . The time required to solve a linear model is comparatively lower than a non-linear model. If an optimization model is non-linear but convex, it is still possible to solve within a realistic time frame [7] . However, in general, the solution times of non-linear optimization models are comparatively higher than the linear models and hence, such optimal solution approaches are not suitable to solve these problems [2] . Therefore, a number of researchers proposed approximate algorithms for this purpose [8] [9] [10] [11] . The ECO-Trade algorithm that we use in this paper is an approximate algorithm. However, the solutions generated by the ECO-Trade algorithm are optimal solutions for almost all scenarios and problem sizes.

P2P energy trading among the households is a comparatively new concept. The P2P service providers maintain the distribution network and provide metering and billing services [12] [13] . These projects primarily considered the development of business models rather than optimizing energy cost coordinated with DSM. Shamsi et al. introduced an auction market in a community microgrid [14] . In this microgrid, each household trades energy with others in the presence of the grid. Liu et al. proposed an energy sharing infrastructure among the prosumers [15] . They considered the microgrid energy price as a function of the Supply and Demand Ratio (SDR) and modeled the optimization problem using bi-level programing. Tushar et al. emphasized on assuring fairness among the prosumers while selecting different pricing schemes [16] . This research aimed at obtaining socially optimal solutions, i.e., maximizing the total benefits of all participating households. Long et al. used a variant of the SDR method to ensure cost fairness among the prosumers [17] . However, none of the aforementioned methods coordinate DSM with P2P trading. More specifically, these methods cannot provide a coordinated schedule of the households' loads with energy sources to maximize the benefits of P2P trading.

Table 1 presents a comparison among the methods proposed for P2P energy trading in a microgrid. It shows that Samadi et al. [18] and Zhou et al. [19] proposed similar methods to ours. They used approximate methods to implement DSM systems coordinated with P2P trading. Additionally, Zhou et al. compared the performance among the SDR, Mid-Market Rate (MMR) and Bill Sharing (BS) methods [19] . Their results show that the SDR method outperforms the others. However, none of the methods proposed in the literature evaluated the performance of their approximate algorithms with optimal methods. Therefore, we do not know the accuracy of the solutions generated by these methods and hence cannot evaluate their performance. On the contrary, in this paper, we evaluate our ECO-Trade algorithm with an optimal method [2] . Our results show that for real and synthetic datasets, the ECO-Trade algorithm generates optimal solutions with 97% accuracy.

This work presents a near-optimal cost optimization algorithm which considers the unfair cost distribution problem for a DSM system coordinated with P2P energy trading. Table 1 shows that most of the algorithms reported in the literature do not have the same features as ours. Therefore, a quantitative comparison with these methods is not a proper way to evaluate our algorithm. However, we still need an approach to compare our algorithm to demonstrate its effectiveness. For this reason, we initially developed an optimal model [2] which always provides exact solutions. We used this optimal model to evaluate the performance of the proposed approximate/heuristic algorithm. Table 1 also shows that the prior research rarely evaluated the accuracy of the approximate algorithms compared to optimal models. Furthermore, we analyze the results to identify the causes of sub-optimal solutions which may help to further improve the performance of the ECO-Trade algorithm.

Table 1. Comparison between the P2P energy trading methods.

3. ECO-Trade Algorithm

The proposed ECO-Trade algorithm follows a bi-linear programming approach. It breaks down our previously proposed optimal model (which is a non-convex MINLP model [2] ) into multiple Mixed Integer Linear Programming (MILP) models or modules. Each MILP model considers a convex feasible region which is smaller than the non-convex solution space. The proposed algorithm solves these MILP models until successive iterations converge to the final solution. Algorithm 1 describes the pseudocode of the proposed algorithm. Module 1 calculates the energy demand and generation of individual households. Module 2 determines the microgrid energy price. Module 3 computes the amount of microgrid energy being traded at a given price. The ECO-Trade algorithm iteratively generates the microgrid price (Module 2) and microgrid energy (Module 3) until a termination criterion is satisfied. Module 3 provides the final solution. We introduce the following variables to control the flow of the algorithm: previous cost, $C_{pre}$ , current cost, $C_{cur}$ , threshold value, $ϵ$ , threshold counter, ${ϵ}_{count}$ , maximum threshold counter limit, ${ϵ}_{\max }$ , and cost improvement, ${ϵ}_{cur}$ . x represents the final solution. For a description of all other notations, please see the nomenclature section at the end of this paper.

3.1. Module 1: Initial Demand and Supply Module

Module 1 optimizes the energy cost for the individual households when they do not participate in microgrid energy trading. It computes the initial values of energy supply and demand, $D{S}_{k,h}$ (defined later in (16)). Module 2 uses the values of $D{S}_{k,h}$ as constants in the first iteration of the bi-linear algorithm.

Objective Function: If a household does not participate in microgrid energy trading, its energy cost is expressed as (1).

$C_k^{NoTrade}={\displaystyle \underset{h\in H}{\sum }}G{P}_h\cdot G{E}_{k,h}+{\displaystyle \underset{i\in I}{\sum }}{d}_{k,i}\left({\tau }_{k,i}-\left({\displaystyle \underset{h\in H}{\sum }}{r}_{k,i,h}\cdot h+t_{k,i}-1\right)\right)$ (1)

The objective function is defined as (2),

$\min C_k^{NoTrade}$ (2)

The optimal solution should satisfy the following constraints.

Energy Balance Constraints: Constraint (3) ensures the balance of energy consumption and generation in each timeslot for all households. The total energy consumed by the loads should be the same as the total energy generated by the energy sources. In this constraint, the grid and renewables are energy sources and the home appliances are loads. The storage and the microgrid can be energy sources or loads based on their functionalities in each timeslot.

${\displaystyle \underset{i\in I}{\sum }}{S}_{k,i,h}\cdot p_{k,i}+I{C}_{k,h}\cdot S{P}_k=G{E}_{k,h}+B{E}_{k,h}+R{E}_{k,h},\left(k\in K,h\in H\right)$ (3)

Stored Energy Constraints: In the first timeslot, storage energy is a function of initial storage energy, storage efficiency and self-discharging rate as expressed in (4).

$S{E}_{k,1}=I{E}_k\cdot S{D}_k+I{C}_{k,1}\cdot S{P}_k\cdot E_k-B{E}_{k,1},\left(k\in K\right)$ (4)

The stored energy in the other timeslots is a function of the available stored energy in the immediate previous timeslot, storage efficiency, and self-discharging rate, which has been expressed in (5).

$S{E}_{k,h}=I{E}_{k,h-1}\cdot S{D}_k+I{C}_{k,h}\cdot S{P}_k\cdot E_k-B{E}_{k,h},\left(k\in K,h\in H:h\ne 1\right)$ (5)

The proposed algorithm discourages charging and discharging a storage at the same time because it will increase the energy cost. While charging the storage, due to the efficiency ( $E_k$ ), we lose energy which we could have used directly to power an appliance/load or to sell, without loss.

There are 2 ways to represent storage charging. One is using discrete charging power (on/off charging using a Boolean variable). Another way is using continuous values as the storage charging power. We used the former method so that the proposed algorithm can also consider the storage of an EV. The charging duration of an EV depends on the charging power and this on/off charging feature with fixed charging power gives the user more control over the required time to charge a storage.

Storage Capacity Constraints: Constraints (6) and (7) ensure that a storage energy should not exceed the maximum storage capacity and should not go below the minimum energy level.

$S{E}_{k,h}\le Min{C}_k,\left(k\in K,h\in H\right)$ (6)

$S{E}_{k,h}\ge Min{C}_k,\left(k\in K,h\in H\right)$ (7)

Task Duration Constraints: For each appliance, Constraint (8) maintains the total duration of an operation. It also ensures that the operation of an appliance can be interrupted as long as its duration of operation satisfies the required time to complete the task. For example, a dishwasher is an interruptible appliance. If it takes three hours to complete a task and has to be completed by 12 am, it does not matter what three hours we are operating the dishwasher.

${\displaystyle \underset{h\in H}{\sum }}{S}_{k,i,h}=t_{k,i},\left(k\in K,i\in I\right)$ (8)

Renewable Energy Availability Constraints: Constraint (9) ensures that the energy drown from the renewables should be equal or less than the available energy.

$R{E}_{k\mathrm{,}h}\le R{Q}_{k\mathrm{,}h}\mathrm{,}\left(k\in K\mathrm{,}h\in H\right)$ (9)

Reservation Time Constraints: Constraint (10) specifies that an appliance operation should start after (or at) the reservation time. ${\displaystyle {\sum }_{h\in H}}{r}_{k,i,h}\cdot h$ refers to the reservation timeslot. An appliance is reserved only once in the time horizon. Therefore, the multiplication of $r_{k,i,h}$ by the corresponding timeslot h provides the reservation timeslot.

${\displaystyle \underset{h\in H}{\sum }}{S}_{k,i,h}={\displaystyle \underset{h={\displaystyle {\sum }_{h\in H}}{r}_{k,i,h}\cdot h}{\overset{N}{\sum }}}{S}_{k,i,h},\left(k\in K,i\in I\right)$ (10)

If an appliance is requested multiple times within the same time horizon, the algorithm schedules the appliance operation as if it had multiple similar appliances.

Relationship between the Scheduling Vector and the End Time Constraints: Constraint (11) binds $t_{k,i}$ with $S_{k,i,h}$ . The end time of an appliance should also be the last execution time.

$S_{k\mathrm{,}i\mathrm{,}h}\cdot h\le {\tau }_{k\mathrm{,}i}\mathrm{,}\left(k\in K\mathrm{,}i\in I\mathrm{,}h\in H\right)$ (11)

Maximum Allowable Delay Constraints: Constraint (12) specifies that an appliance operation must be completed before (or at) the user defined maximum allowable time limit.

${\tau }_{k\mathrm{,}i}\le {\beta }_{k\mathrm{,}i}\mathrm{,}\left(k\in K\mathrm{,}i\in I\right)$ (12)

Uninterruptibility Constraints: Constraints (13) and (14) define that an uninterruptible appliance keeps running without any interruption until it completes its operation.

${\displaystyle \underset{d=0}{\overset{t_{k,i}-1}{\sum }}}{S}_{k,i,h+d}-t_{k,i}\ge -t_{k,i}\left(1-U{S}_{k,i,h}\right),\left(k\in K,i\in U,h=\left[1,N-t_{k,i}+1\right]\right)$ (13)

${\displaystyle \underset{h=1}{\overset{N-t_{k,i}+1}{\sum }}}U{S}_{k,i,h}=1,\left(k\in K,i\in U\right)$ (14)

Utility Grid Max Power Limit Constraints: Constraint (15) limits the power that can be drawn from the grid.

$G{E}_{k,h}\le L_k^{\max },\left(k\in K,h\in H\right)$ (15)

Demand and Supply Constraints: Equation (16) calculates the demand or supply of energy from the external energy sources like grid and microgrid. If the value of $D{S}_{k,h}$ is positive, the household has energy demand. If the value of $D{S}_{k,h}$ is negative, the household has energy surplus.

$\begin{array}{l}D{S}_{k\mathrm{,}h}={\displaystyle \underset{i\in I}{\sum }}{S}_{k\mathrm{,}i\mathrm{,}h}\cdot p_{k\mathrm{,}i}+I{C}_{k\mathrm{,}h}\cdot S{P}_k-R{Q}_{k\mathrm{,}h}-S{E}_{k\mathrm{,}h}\\ -B{E}_{k\mathrm{,}h}+Min{C}_k\mathrm{,}\left(k\in K\mathrm{,}h\in H\right)\end{array}$ (16)

3.2. Module 2: Price Computation Module

Module 2 computes the microgrid energy price. In this module, $M{E}_{k,h}$ is a constant and $M{P}_h$ is a variable.

Objective Function: The proposed model in Module 2 is a multi-objective optimization problem which is expressed as (17).

$\min \left(C_{total},C_1,C_2,\cdots ,C_k\right)$ (17)

Here, $C_{total}$ is the total cost of all households and $C_k$ is the total cost of the k-th household which are expressed in (18) and (19) respectively.

$C_{total}={\displaystyle \underset{k\in K}{\sum }}{\displaystyle \underset{h\in H}{\sum }}G{P}_h\cdot G{E}_{k,h}+{\displaystyle \underset{k\in K}{\sum }}{\displaystyle \underset{i\in I}{\sum }}{d}_{k,i}\left({\tau }_{k,i}-\left({\displaystyle \underset{h\in H}{\sum }}{r}_{k,i,h}\cdot h+t_{k,i}-1\right)\right)$ (18)

$C_k={\displaystyle \underset{h\in H}{\sum }}G{P}_h\cdot G{E}_{k,h}+{\displaystyle \underset{h\in H}{\sum }}M{P}_h\cdot M{E}_{k,h}+{\displaystyle \underset{i\in I}{\sum }}{d}_{k,i}\left({\tau }_{k,i}-\left({\displaystyle \underset{h\in H}{\sum }}{r}_{k,i,h}\cdot h+t_{k,i}-1\right)\right)$ (19)

The total energy bought from the microgrid is the same as the total energy sold to the microgrid. Therefore, microgrid energy price does not have an impact on the total cost. Hence, Equation (18) does not require the microgrid energy cost. This multi-objective optimization problem is solved by using $C_{total}$ as the sole objective function and the remaining objective functions, $C_k$ , are added as inequality constraints (Constraint (24) discussed later). Therefore, the objective function of Module 2 is defined as (20).

$\min C_{total}$ (20)

The optimization model should satisfy Constraints (4) (15) as well as the following constraints.

Energy Balance Constraints: Constraint (21) ensures that, in a specific household, total energy consumption is equal or less than the total available energy.

${\displaystyle \underset{i\in I}{\sum }}{S}_{k\mathrm{,}i\mathrm{,}h}\cdot p_{k\mathrm{,}i}+I{C}_{k\mathrm{,}h}\cdot S{P}_k\le G{E}_{k\mathrm{,}h}+B{E}_{k\mathrm{,}h}+R{E}_{k\mathrm{,}h}+M{E}_{k\mathrm{,}h}\mathrm{,}\left(k\in K\mathrm{,}h\in H\right)$ (21)

Microgrid Energy Price Constraints: Constraints (22) and (23) define the maximum and minimum limits of microgrid energy price.

$M{P}_h\ge \mathrm{0,}\left(h\in H\right)$ (22)

$M{P}_h\le G{P}_h\mathrm{,}\left(h\in H\right)$ (23)

Pareto Optimality Constraints: Constraint (24) implements Pareto optimality. It ensures that a household cost when it participates in microgrid trading must be less than or equal to the cost when it does not participate.

$C_k\le C_k^{NoTrade}\mathrm{,}\left(k\in K\right)$ (24)

3.3. Module 3: Energy Computation Module

The third module computes the microgrid energy, $M{E}_{k,h}$ , using the constant microgrid prices, $M{P}_h$ , provided by Module 2. The optimization model of Module 3 is similar to Module 2. The main differences are: 1) it does not require Constraints (22) and (23) because microgrid prices are constants, and 2) Constraint (21) of Module 2 is modified as Constraint (25). Module 3 also requires the following constraints.

Energy Balance Constraints: Constraint (25) ensures that, for a specific household, the total energy consumption should be the same as the total available energy.

${\displaystyle \underset{i\in I}{\sum }}{S}_{k,i,h}\cdot p_{k,i}+I{C}_{k,h}\cdot S{P}_k=G{E}_{k,h}+B{E}_{k,h}+R{E}_{k,h}+M{E}_{k,h},\left(k\in K,h\in H\right)$ (25)

A negative value of $M{E}_{k,h}$ means the household is an energy seller at that specific timeslot. A positive value means the household is a buyer.

Energy Balance Constraints for Microgrid: Constraint (26) ensures that the total energy sold in the microgrid by all households must be equal to the total energy bought from the households.

${\displaystyle \underset{k\in K}{\sum }}M{E}_{k,h}=0,\left(h\in H\right)$ (26)

Energy Constraints While Trading in Microgrid: Constraint (27) calculates the amount of available energy to trade in the microgrid.

$\begin{array}{l}M{Q}_{k,h}={\displaystyle \underset{i\in I}{\sum }}{S}_{k,i,h}\cdot p_{k,i}+I{C}_{k,h}\cdot S{P}_k-G{E}_{k,h}-R{Q}_{k,h}\\ -S{E}_{k,h}-B{E}_{k,h}+Min{C}_k,\left(k\in K,h\in H\right)\end{array}$ (27)

If a household is a seller at a timeslot, this constraint limits the maximum amount of energy that the household can sell to the microgrid. If a household is a buyer, this constraint defines the minimum energy required by the household from the microgrid.

$M{E}_{k\mathrm{,}h}\ge M{Q}_{k\mathrm{,}h}\mathrm{,}\left(k\in K\mathrm{,}h\in H\right)$ (28)

4. Results

In this section, we compare the proposed ECO-Trade algorithm with the optimal model to evaluate its performance. We used a 64 bit Fedora 20 machine with Intel Core i7 CPU (2.67 GHz) and 12 GB RAM to collect the results. CPLEX 12.6.1.0 [20] is used to solve the models.

4.1. Small Scenarios with Synthetic Data

This section shows the impact of the number of households, timeslots and appliances on the computation time. Table 2 specifies the static parameters used for the scenarios. Table 3 shows the minimum and maximum bounds for generating uniformly distributed parameters. The ECO-Trade algorithm terminates if the cost does not improve more than 0.1% in the last 10 iterations. We solved 492 scenarios for the optimal model and the ECO-Trade algorithm. Among all these scenarios, 111 solutions exceeded the cut off time (set to 8 hr) for the optimal model and we did not get any solution for these cases. Therefore, the comparison between the optimal and the ECO-Trade models considers 381 solutions of each model.

Figure 2 shows that the median computation times of the ECO-Trade algorithm are almost constant for any number of appliances. On the contrary, the computation times of the optimal model increase exponentially with the number of appliances. Figure 3 and Figure 4 show that the computation times of both algorithms increase exponentially with the number of timeslots and households. The average of the median solution times of the ECO-Trade algorithm is very low (0.46 sec) compared to the optimal model (2316 sec or 38 min). For all scenarios, the maximum median solution time of the ECO-Trade algorithm is less than 5 sec whereas the maximum median solution time of the optimal model is 7737 sec (2 hr and 9 min). We consider 0.01% deviation from the optimal solution as an acceptable optimal solution. Our results show that over 97% of the ECO-Trade solutions are optimal solutions. The worst deviation from the optimal solution in all 381 cases is 5.2%.

4.2. Large Scenarios with Real Data

In the previous section, we compared the ECO-Trade algorithm with the optimal model for small problem sizes. Although it is the best approach to evaluate the performance of an approximate algorithm, it is not practical for our case because we are unable to generate solutions for large scenarios. If we exclude the non-linear constraints from the optimal model, its time complexity will decrease because in this case, the optimal model will be reduced to an MILP model. However, this optimal model will no longer ensure Pareto optimality.

Table 2. Static parameters.

Table 3. Uniformly distributed parameters.

Figure 2. Comparison between the solution times of the optimal model and the ECO-trade algorithm for different number of appliances.

The cost of the previously proposed optimal model [2] can be equal or greater than the optimal model used in this section. The relationships between these costs are expressed in Figure 5. The minimum cost which does not consider the

Figure 3. Comparison between the solution times of the optimal model and the ECO-trade algorithm for different number of timeslots.

Figure 4. Comparison between the solution times of the optimal model and the ECO-trade algorithm for different number of households.

Pareto optimality is always equal to or less than the minimum cost that considers Pareto optimality. In Figure 5, the difference between these 2 costs is represented by a. Instead of comparing the ECO-Trade algorithm with the optimal model with Pareto optimality [2] (the difference is b), we compare it with the optimal model without Pareto optimality (the difference is c). Here, $c=a+b$ where the value of a is either 0 or a small number. Hence, $c\ge b$ .

We used household load datasets collected in Ottawa [21] . In [21] , the authors

Figure 5. Relationship between the ECO-trade algorithm and the optimal models with/without Pareto optimality.

considered 12 households which were selected based on their annual consumption profiles. The electricity bills of the potential participants were examined; some volunteers were selected for the study because their annual electricity consumption were close to the Canadian average, whereas others were selected because they consume below or above the average.

We collected solar irradiance for Ottawa from the National Solar Radiation Database (NSRDB) [22] which is maintained by the National Renewable Energy Laboratory (NREL) [23] . The database is developed using the Physical Solar Model (PSM) [24] . The PV array configuration is given in Table 4. We used the PV_LIB MATLAB toolbox [25] developed by Sandia National Laboratories [26] to convert the solar irradiance to DC power. The King Diffuse model (developed by David L. King at Sandia National Laboratory) was used to determine the total diffuse irradiance (sky diffuse and ground reflected irradiance) [27] . We did not consider any DC to AC inverter.

We used Tesla Powerwall as the home energy storage. The storage characteristics are given in Table 5 [28] . A Powerwall battery can store up to 6.4 kWh and we consider that its energy level should not go below 40% of the maximum storage capacity (2.56 kWh). The required power to charge the storage is 3.3 kW. Its charging efficiency is 92% and self-discharging rate is approximately 1% per day which is 0.042% per hour.

We used 4 representative days of 2010 based on seasons (summer and winter) and days of the week (weekend day and weekday). We used Real-Time Price (RTP) and Time-Of-Use (TOU) prices of these days to evaluate our algorithm. Hydro Ottawa uses a TOU price which is set by the Ontario Energy Board (OEB) [29] . Pagani et al. considered the day ahead price advertised by the wholesale market as the retail energy price for the end user and proposed that this price can be used as RTP [30] . To use this idea in our research, we collected the hourly wholesale energy price advertised by the Independent Electricity System Operator (IESO) [31] . The Hourly Ontario Energy Price (HOEP) from IESO Historical Reports (2002-present) was used as RTP [32] . IESO is responsible for operating the electricity market and directing the operation of the bulk electrical system in the province of Ontario, Canada. Hydro Ottawa buys energy from IESO [33] .

Table 4. PV array configuration.

Table 5. Characteristics of Tesla Powerwall [28] .

We used different settings of the parameters to generate different scenarios. For household loads, we considered a summer weekday, a summer weekend day, a winter weekday and a winter weekend day load profiles. For each of these load profiles, we divided the scenarios based on user preference: economy and comfort. A user may prefer to save cost, which we labeled as economy. We used a low value of the disutility factor (0.001 per timeslot) so that the algorithm can tolerate more delay in appliance operation. On the other hand, a user may prefer more comfort. In this setting, the disutility factor is set to a higher value (200 per timeslot) so that the algorithm shows reluctance to any delay in appliance operation. If the household has a storage, the scenarios were varied based on the initial storage energy. A household can have minimum storage energy or maximum storage energy at the beginning of a planning cycle. The parameters were also different for RTP and TOU energy price schemes. A detailed description of how these parameters were used to generate different scenarios can be found in [34] .

We generated 112 different scenarios for performance analysis. The ECO-Trade algorithm terminates if the cost does not improve more than 0.1% within 3 consecutive iterations. Results show that the ECO-Trade algorithm provides optimal solutions for 99% of the scenarios. The remaining 1% of cases had a cost at most 1.8% higher than the optimal solution. The median solution time is around 4.6 sec for all scenarios. For the ECO-Trade algorithm, the solution times of 90.2% of the scenarios are below 1 min. We observed that 7.1% of the scenarios took more than 2 min to solve. Therefore, we conclude that the proposed ECO-Trade algorithm is a better alternative to the optimal model considering the trade-off between the accuracy and the solution time.

5. Analysis of Local Minima

The ECO-Trade algorithm sometimes gets trapped into a local minimum and cannot improve the resulting solution any further. In this section, we analyze the conditions under which the algorithm generates sub-optimal solutions. For simplicity, we consider only 2 households, 2 timeslots and 1 appliance. We exclude the renewables and the self-discharging feature of the storage. We do not consider the disutility cost, i.e., all disutility factors are set to 0. The appliance and storage characteristics are shown in Table 6 and Table 7 respectively.

5.1. Cost without Microgrid Trading

We use Module 1 of the ECO-Trade algorithm to generate the household cost when they are not participating in the microgrid energy trading. Table 8 shows that the minimum costs for household 1 and household 2 are 19.5 and 43.5 respectively when they are not participating in microgrid trading. These costs should be the maximum costs when they participate in microgrid trading for cost optimization. Therefore, when the 2 households are optimized individually, the total cost is 63.

5.2. Cost Using the Optimal Model

Now, we introduce the microgrid and solve the same optimization problem, but this time also allowing the households to trade energy with each other. Table 9 summarizes the results for the 2 households, using the same format as before. A negative value of microgrid energy indicates that the household is actually selling energy to the microgrid, whereas a positive value indicates that the household buys that much energy from the microgrid. Compared to the previous solution, the total cost of household 1 decreases from 19.5 to 18.14 and the total cost of household 2 decreases from 43.5 to 41.86.

5.3. Sub-Optimal Cost Using the ECO-Trade Algorithm

To generate a suboptimal result with this simple scenario, we initialize the microgrid prices for the two timeslots as follows. We use the grid price (which is the maximum limit of the microgrid price) as the microgrid price at the 1st timeslot and we use 0 (which is the minimum limit of the microgrid price) as the microgrid price at the last timeslot. The ECO-Trade algorithm gets trapped into a local minimum and cannot improve the solution any further. It generates the same solution in the next few iterations and finally terminates with a solution which is given in Table 10.

In Table 10, for household 1 at timeslot 1, both microgrid and grid prices are 3. It is cost effective to charge the storage with cheap energy at this timeslot to use it at the last timeslot when energy is expensive. In the 1st timeslot, the total

Table 6. Appliance characteristics.

Table 7. Storage characteristics.

Table 8. Cost without microgrid trading.

Table 9. Optimal cost with microgrid trading (optimal model).

minimum load is 7 kWh (2 kWh for the appliance and 5 kWh for charging the storage). Household 1 sells 7 kWh of energy to Household 2. Therefore, the total load at this timeslot is 14 kWh. This 14 kWh is drawn from the grid and the storage (13.5 kWh from the grid and 0.5 kWh from the storage). Selling energy to the microgrid does not have any impact on the household cost because buying grid energy has the same cost as selling energy to the microgrid. Therefore, the

Table 10. Sub-optimal cost with microgrid trading (ECO-trade algorithm).

energy cost for household 1 is 19.53 for 6.5 kWh energy. At timeslot 2, household 1 does not buy energy from the grid. It uses 2 kWh of energy from the storage. The microgrid price is 0 at this timeslot. Hence, buying or selling energy to the microgrid does not impact the household cost (microgrid quantity is set to 0 kWh).

In an iteration, when the microgrid prices are 3 and 0 (constants) for timeslots 1 and 2 respectively, we get a solution which trades −7 kWh and 0 kWh of energy in the microgrid. This solution provides the maximum cost for Household 1, which is 19.5. The microgrid quantity does not have any impact on the energy cost because either the microgrid price is 0 or it is the same as the grid price. Therefore, this solution cannot be improved for the given constant microgrid prices.

In the next iteration, when the microgrid quantities are constants (−7 kWh and 0 kWh for timeslots 1 and 2 respectively) the solution cannot be improved either. At timeslot 1, any microgrid price which is less than 3 will increase the Household 1 energy cost to more than 19.5, which violates the Pareto optimality constraint. For timeslot 2, the microgrid price does not have any impact on energy cost because the households do not trade energy at this timeslot.

A similar explanation is also applicable to household 2. When the microgrid prices are constants (3 and 0 for timeslots 1 and 2 respectively), the total energy cost of this household is the same for any amount of microgrid energy trading. On the other hand, when the microgrid quantities are constants (7 kWh and 0 kWh for timeslots 1 and 2 respectively), any value which is less than 3 violates the Pareto optimality constraint for Household 1. For timeslot 2, the microgrid price does not have any impact because it does not trade energy in microgrid.

In an iteration, if the energy price is greater than 0 (at timeslot 2 for both households), we will not trade energy: the only household available to sell into the microgrid is household 1, but it has no energy available (unless it bought some from the grid, but then it would have to sell at least at the grid price to come out ahead).

In addition to this simple example, we analyze all scenarios which generated sub-optimal solutions. These are relatively large scenarios and it is hard to identify the exact reasons for sub-optimal solutions. We notice different patterns in the solutions which are mostly related to the boundary values of the microgrid price. Every sub-optimal scenario we found has microgrid energy prices that are higher in adjacent timeslots and the price is either 0 or the same as (or at least very close to) the grid price. However, scenarios where the grid prices are close to these boundary values do not always result in a sub-optimal solution.

In the proposed bi-linear optimization, the algorithm sets the microgrid prices as constants and determines the microgrid quantities in one module. In the next iteration, it sets the microgrid quantities as constants and determines the microgrid prices. This property of the algorithm sometimes does not allow the solution to be improved while maintaining the Pareto optimality constraints in each iteration. Therefore, we can conclude that the ECO-Trade algorithm sometimes gets trapped at a local minimum because it alternately sets the microgrid price and microgrid quantity as constants.

6. Impact of Local Minima

In this section, we analyze how a local minimum increases the total cost in a microgrid. To explore the factors, we studied the scenario which provides the worst solution with synthetic data. The scenario consists of 30 households, 2 appliances and 3 timeslots. The parameters used for this optimization were generated randomly as described in Section 4.1. For this scenario, the optimal cost is 132.79 and the sub-optimal cost generated by the ECO-Trade algorithm is 139.68. The sub-optimal cost is 5.2% higher than the optimal cost. We use this specific scenario to analyze all the results presented in this section.

There are 2 main reasons for an increase in the cost of the proposed the ECO-Trade algorithm. First, the sub-optimal microgrid price may force the ECO-Trade algorithm to buy more energy from the grid compared to the optimal solution. Second, it may delay an appliance operation compared to the optimal solution.

6.1. Buying More Energy from the Grid

If, in a microgrid area, the households buy more energy from the grid compared to the optimal solution, then the ECO-Trade algorithm cannot produce the optimal solution. There are 2 main reasons that may cause the solution derived by the ECO-Trade algorithm to buy more energy from the grid:

6.1.1. Energy Loss Due to Storage Charging Efficiency

Table 11 shows that one of the main reasons for the higher cost in the ECO-Trade algorithm is that the derived solution unnecessarily charges the storage, which imposes energy loss due to storage charging. The solution charges the storage devices of households 1, 2, 3, 8, 9, 10, 16, 17 and 26. The optimal model never charges any storage in any households. Due to storage charging efficiency, the ECO-Trade solution lost 3.15 kWh of energy compared to the optimal solution.

Table 11. Impact of local minima on the ECO-trade algorithm cost.

The households in the ECO-Trade solution buy this energy at the 1st timeslot from the grid at a price of 1.41. Therefore, the ECO-Trade algorithm incurs an additional cost of 3.15 kWh*1.41/kWh = 4.43 compared to the optimal solution.

6.1.2. Energy Loss Due to Storage Self-Discharging

In a microgrid area, households may buy more energy from the grid if the storage devices lose more energy due to self-discharging. Table 11 shows that in the sub-optimal solution, the households lose 0.2 kWh more energy compared to the optimal solution due to self-discharging.

6.2. Disutility Cost

The ECO-Trade solution sometimes delays an appliance operation, which increases the cost due to the disutility cost. Table 11 shows that households 4, 20, 21, 23 and 27 increase their cost by 2.35 compared to the optimal model.

Table 11 shows that the total cost increment due to increased disutility and storage charging is 6.78, which is almost the cost difference between the optimal and the ECO-Trade algorithm (6.89). The remaining 0.11 cost increase is due to the cost related to self-discharging loss and the precision of the used values (we considered 2 digits after the decimal point). The root cause of this sub-optimal solution is that the ECO-Trade algorithm does not determine the optimal microgrid price.

7. Conclusions

This paper analyzes the performance of the ECO-Trade algorithm compared to the optimal model. We get 97% optimal solutions for synthetic (small) data sets and 99% optimal solutions for more realistic (large) datasets. Also, the difference in results is less than 5.2% in the first case and 1.8% in the second case. The solution time is almost always less than one minute, and much lower than the optimal model. Therefore, based on the results presented in this paper, we can conclude that the ECO-Trade algorithm is a better alternative to the previously proposed optimal model considering the accuracy and the solution time.

We analyze the solutions generated by the ECO-Trade algorithm for a wide range of problem sizes and identify that the sub-optimal cost potentially arises when the microgrid price reaches the boundary limits. Every sub-optimal scenario we found has microgrid energy prices that are higher in previous adjacent timeslots and the price is either 0 or close to the grid price. In a local minimum, the sub-optimal microgrid energy price forces the households either to buy more energy to compensate for storage energy loss or delays appliance operations. However, having microgrid prices that take on their boundary values is not sufficient for a suboptimal solution to occur. In our work, only a small percentage of cases ended up being trapped in a local minimum. Going forward, we will explore how to deal with this issue. For example, we can verify whether a given solution has microgrid prices at the boundaries, and re-run modules 2 and 3 iteratively using perturbed microgrid prices (for example the average price) as a starting point.

Nomenclature

A) Sets

H Set of timeslots where $h\in H$ I Set of appliances where $i\in I$ K Set of households where $k\in K$ U Set of uninterruptible appliances where $U\subset I$ B) Parameters

$C_{pre}$Previous cost

$C_{cur}$Current cost

$d_{k,i}$Disutility factor of an appliance

$E_k$Storage efficiency

$G{P}_h$Grid energy price

$I{E}_k$Initial storage energy level

$L_k^{\max }$Maximum grid power limit

$Min{C}_k$Maximum storage capacity

$Min{C}_k$Minimum storage capacity

N Number of timeslots in the scheduling time horizon

$p_{k,i}$Power consumption of an appliance

$r_{k,i,h}$Reservation time of an appliance which represents the time when the scheduler gets a request to start a specific appliance (boolean constant, $r_{k,i,h}=1$ means that operation of the appliance is requested)

$R{Q}_{k,h}$Amount of generated renewable energy

$S{D}_k$Self-discharging coefficient of the storage

$S{P}_k$ Required power to charge the storage

$t_{k,i}$ Duration of the running time of an appliance

x Final solution

${\beta }_{k,i}$ Maximum allowable delay of an appliance

$ϵ$ Threshold value

${ϵ}_{count}$ Threshold counter

${ϵ}_{\max }$ Maximum threshold counter limit

${ϵ}_{cur}$ Cost improvement

C) Variables

$B{E}_{k,h}$ Energy used from the storage ( $B{E}_{k,h}\in {ℝ}^{+}$ )

$C_k$ Total cost of the k-th household when it participates in microgrid energy trading ( $C_k\in ℝ$ )

$C_k^{NoTrade}$ Total cost of the k-th household when it does not participate in microgrid energy trading ( $C_k^{NoTrade}\in ℝ$ )

$C_{total}$ Total cost of all households ( $C_{total}\in {ℝ}_0^{+}$ )

$D{S}_{k,h}$ Energy demand or supply of a household ( $D{S}_{k,h}\in ℝ$ , a positive value represents energy demand and a negative value represents energy surplus)

$G{E}_{k,h}$ Energy drawn from the grid ( $G{E}_{k,h}\in {ℝ}^{+}$ )

$I{C}_{k,h}$ Storage charging state (boolean vector, $I{C}_{k,h}=1$ means the storage is in charging state)

$M{Q}_{k,h}$ Demand or supply of microgrid energy ( $M{Q}_{k,h}\in ℝ$ , a positive value represents the minimum energy demand of the household and a negative value represents the maximum amount of energy that the household can sell to the microgrid)

$R{E}_{k,h}$ Energy used from the renewable source ( $R{E}_{k,h}\in {ℝ}^{+}$ )

$S{E}_{k,h}$ Energy level of a storage ( $S{E}_{k,h}\in {ℝ}^{+}$ )

$S_{k,i,h}$ Appliance operation time (boolean vector, $S_{k,i,h}=1$ means the appliance is in operation)

$U{S}_{k,i,h}$ Start time of an uninterruptible appliance (boolean vector, $U{S}_{k,i,h}=1$ represents the timeslot when an uninterruptible appliance starts its operation)

${\tau }_{k,i}$ End time of an appliance operation ( ${\tau }_{k,i}\in \mathbb{N}$ )

D) Variables or Parameters

$D{S}_{k,h}$ Energy demand or supply of a household ( $D{S}_{k,h}\in ℝ$ , a positive value represents energy demand and a negative value represents energy surplus). $D{S}_{k,h}$ is a variable in Module 1 and a parameter in Module 2.

$M{E}_{k,h}$ Energy traded in microgrid ( $M{E}_{k,h}\in ℝ$ , a positive value represents a buyer and a negative value represents a seller). $M{E}_{k,h}$ is a parameter in Module 2 and a variable in Module 3.

$M{P}_h$ Price of microgrid energy ( $M{P}_h\in {ℝ}^{+}$ ). $M{P}_h$ is a variable in Module 2 and a parameter in Module 3.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Backman, M. and Fagerberg, J. (2018) Smart Homes and Home Automation. 6th Edition, Berg Insight’s M2M Research Series.
[2]	Alam, M.R., St-Hilaire, M. and Kunz, T. (2017) An Optimal p2p Energy Trading Model for Smart Homes in the Smart Grid. Energy Efficiency, 10, 1475-1493. https://doi.org/10.1007/s12053-017-9532-5
[3]	Alam, M.R., St-Hilaire, M. and Kunz, T. (2019) Peer-to-Peer Energy Trading among Smart Homes. Applied Energy, 238, 1434-1443. https://doi.org/10.1016/j.apenergy.2019.01.091
[4]	Conejo, A.J., Morales, J.M. and Baringo, L. (2010) Real-Time Demand Response Model. IEEE Transactions on Smart Grid, 1, 236-242. https://doi.org/10.1109/TSG.2010.2078843
[5]	Zhu, Z., Tang, J., Lambotharan, S., Chin, W.H. and Fan, Z. (2012) An Integer Linear Programming Based Optimization for Home Demand-Side Management in Smart Grid. Proceedings of the IEEE PES Innovative Smart Grid Technologies, Washington DC, 16-20 January 2012, 1-5.
[6]	Giorgio, A.D. and Liberati, F. (2014) Near Real Time Load Shifting Control for Residential Electricity Prosumers under Designed and Market Indexed Pricing Models. Applied Energy, 128, 119-132. https://doi.org/10.1016/j.apenergy.2014.04.032
[7]	Tsui, K.M. and Chan, S.C. (2012) Demand Response Optimization for Smart Home Scheduling under Real-Time Pricing. IEEE Transactions on Smart Grid, 3, 1812-1821. https://doi.org/10.1109/TSG.2012.2218835
[8]	Arghandeh, R., Woyak, J., Onen, A., Jung, J. and Broadwater, R.P. (2014) Economic Optimal Operation of Community Energy Storage Systems in Competitive Energy Markets. Applied Energy, 135, 71-80. https://doi.org/10.1016/j.apenergy.2014.08.066
[9]	Hovgaard, T.G., Boyd, S., Larsen, L.F.S. and Argensen, J.B. (2013) Nonconvex Model Predictive Control for Commercial Refrigeration. International Journal of Control, 86, 1349-1366. https://doi.org/10.1080/00207179.2012.742207
[10]	Schroeder, A. (2011) Modeling Storage and Demand Management in Power Distribution Grids. Applied Energy, 88, 4700-4712. https://doi.org/10.1016/j.apenergy.2011.06.008
[11]	Yang, J., He, L. and Fu, S. (2014) An Improved PSO-Based Charging Strategy of Electric Vehicles in Electrical Distribution Grid. Applied Energy, 128, 82-92. https://doi.org/10.1016/j.apenergy.2014.04.047
[12]	Vandebron (2018). https://vandebron.nl
[13]	Sonnen (2018). https://www.sonnenbatterie.de
[14]	Shamsi, P., Xie, H., Longe, A. and Joo, J. (2016) Economic Dispatch for an Agent-Based Community Microgrid. IEEE Transactions on Smart Grid, 7, 2317-2324. https://doi.org/10.1109/TSG.2015.2487422
[15]	Liu, N., Yu, X., Wang, C., Li, C., Ma, L. and Lei, J. (2017) Energy-Sharing Model with Price-Based Demand Response for Microgrids of Peer-to-Peer Prosumers. IEEE Transactions on Power Systems, 32, 3569-3583. https://doi.org/10.1109/TPWRS.2017.2649558
[16]	Tushar, W., Yuen, C., Smith, D.B. and Poor, H.V. (2017) Price Discrimination for Energy Trading in Smart Grid: A Game Theoretic Approach. IEEE Transactions on Smart Grid, 8, 1790-1801. https://doi.org/10.1109/TSG.2015.2508443
[17]	Long, C., Wu, J., Zhou, Y. and Jenkins, N. (2018) Peer-to-Peer Energy Sharing through a Two-Stage Aggregated Battery Control in a Community Microgrid. Applied Energy, 226, 261-276. https://doi.org/10.1016/j.apenergy.2018.05.097
[18]	Samadi, P., Wong, V.W.S. and Schober, R. (2016) Load Scheduling and Power Trading in Systems with High Penetration of Renewable Energy Resources. IEEE Transactions on Smart Grid, 7, 1802-1812. https://doi.org/10.1109/TSG.2015.2435708
[19]	Zhou, Y., Wu, J. and Long, C. (2018) Evaluation of Peer-to-Peer Energy Sharing Mechanisms Based on a Multiagent Simulation Framework. Applied Energy, 222, 993-1022. https://doi.org/10.1016/j.apenergy.2018.02.089
[20]	CPLEX (2018). http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer
[21]	Saldanha, N. and Beausoleil-Morrison, I. (2012) Measured End-Use Electric Load Profiles for 12 Canadian Houses at High Temporal Resolution. Energy and Buildings, 49, 519-530. https://doi.org/10.1016/j.enbuild.2012.02.050
[22]	NSRDB (2018). https://nsrdb.nrel.gov
[23]	NREL (2018). http://www.nrel.gov
[24]	NSRDB VIEWER (2018). https://nsrdb.nrel.gov/nsrdb-viewer
[25]	PV-LIB Toolbox (2019). https://pvpmc.sandia.gov/applications/pv_lib-toolbox/
[26]	Sandia National Laboratories (2018). https://pvpmc.sandia.gov
[27]	Lave, M., Hayes, W., Pohl, A. and Hansen, C.W. (2015) Evaluation of Global Horizontal Irradiance to Plane-of-Array Irradiance Models at Locations across the United States. IEEE Journal of Photovoltaics, 5, 597-606. https://doi.org/10.1109/JPHOTOV.2015.2392938
[28]	Tesla Powerwall (2018). https://www.teslamotors.com/enca/powerwall
[29]	Ontario Energy Board (OEB) (2019). https://www.oeb.ca/
[30]	Pagani, G.A. and Aiello, M. (2015) Generating Realistic Dynamic Prices and Services for the Smart Grid. IEEE Systems Journal, 9, 191-198. https://doi.org/10.1109/JSYST.2014.2320800
[31]	IESO (2016). http://www.ieso.ca/Pages/Power-Data/default.aspx#price
[32]	IESO HOEP (2018). http://www.ieso.ca/Pages/Power-Data/Data-Directory.aspx
[33]	List of All Registered Participants (IESO) (2019). http://www.ieso.ca/en/Sector-Participants/Registration/Organization-Registration-and-Participant-Authorization/Registered-Participants
[34]	Alam, M.R. (2017) Exact and Approximate Solutions for Energy Cost Optimization in Smart Homes. PhD Dissertation, Carleton University, Ottawa.