1 Introduction

The rapid increase in the integration of distributed energy resources (DERs) into the power system along with deploying information and communication technologies (ICTs) has changed power system from a hierarchical structure to a deregulated system [1]. In the new power system, many consumers have been compelled to be more engaged of their energy consumption, which has changed them to prosumers who proactively manage their generation and demands. Prosumers with surplus energy could supply their energy to consumers with energy deficits to earn some benefit through energy trading. The current electricity market structure is still operating under conventional characteristics, without taking full advantage of local energy sharing [2]. Hence, new electricity market should be designed in a more consumer-centric manner to incorporate prosumers into the energy market [3].

Consumer-centric electricity markets enable players to trade energy directly in a peer-to-peer (P2P) environment. P2P trading is a novel proposal for operation of the new electricity markets, which engages prosumers in the market and contributes towards substantially increasing the percentage of renewable energy penetration into the current electricity grid [4]. Different market structures can be implemented for P2P energy trading such as community-based market [5], and distributed bilateral trading market [6]. A comprehensive review of different market frameworks for local energy trading is presented in [7]. In the community-based market, each player can share energy with other players and there is a virtual supervisory node to facilitate energy trading among prosumers. In this market, each player is a decision maker, and coordinator only generates a coordination signal to guarantee convergence among different players. On the other side, in the bilateral trading market, there is no coordinator and all players can negotiate directly to reach agreement on the price and amount of traded energy. Although these structures are different in the degree of centralization, in both cases market players can negotiate on energy trading, whether directly or through coordinator. Therefore, for proper implementation of P2P markets, an appropriate model of negotiation mechanism and market clearing should be designed.

In recent years, several methods have been proposed for designing market clearing and negotiation mechanism in P2P markets. These methods include dual decomposition [8], alternating direction method of multipliers (ADMM) [9], distributed consensus-based algorithms [10], and consensus + innovation methods [1, 6]. In all of these methods, the negotiation and market clearing algorithm is an iterative process, which needs to be executed iteratively to reach the optimal outcome. Due to the large number of players involved in the negotiation and the number of iterations needed, implementation of these methods may be challenging in practice. Hence, the interaction and negotiation mechanisms should be designed adequately. As the number of players in the consumer-centric markets increases, the communication and computation overheads would be the main barriers in the real-world implementation of P2P markets. To enhance the scalability of the P2P market, the number of agents an algorithm deals with should be reduced. This decrease in the number of players can reduce the complexity of algorithm, as well as the computation and communication overheads [11].

Given this context, market segmentation can be applied to reduce the number of negotiating players in the P2P market to enhance scalability of these markets. Different clustering methods can be used for market segmentation to group similar players separately. Due to recent advances in the ICT, there has been a growing interest in the literature to employ data mining techniques such as clustering in energy sector. Authors in [12] use clustering to form virtual association of prosumers for smart energy trading, where prosumers in a cluster agree to operate together in the market as a single entity. In [13], different clustering methods are applied to form virtual microgrid through orchestrating prosumers to reduce total energy cost through the reduction of total relative forecasting inaccuracies. A geometric clustering is proposed in [14] to allocate local power exchange centres for local energy trading, where location is considered as the only feature for the clustering, and the demand-supply constraint is not included in the optimization problem for clustering.

This paper proposes an adaptive segmentation method for market clearing to enhance the scalability of P2P markets. In the proposed method, market players are clustered based on their features, and players in each segment negotiate separately to reach convergence on the price and amount of traded energy. The proposed method uses balanced k-means clustering, to ensure the demand-supply constraint in each segment. Then the distributed algorithm for market clearing in each segment is presented, where ADMM method is employed to design the market clearing and negotiation process. At the third step, a quality of experience (QoE) index is defined based on the satisfaction of players to check if fairness of market can be increased by swapping players in different segments. The proposed method can be employed with any consumer-centric market structure and different distributed optimization methods. Here, two different structures including community-based and fully decentralized bilateral trading market have been considered for the market structure. The operation of the adaptive segmentation method is tested for different case studies.

2 Market structure

The market structure is consumer-centric where prosumers and consumers can join the market to trade energy directly. The proposed market organization in this paper provides a segmented P2P market, where in contrast to full P2P market, each agent only negotiates with a limited number of agents with similar preferences. Two different structures for the market have been considered: community-based market and bilateral trading market. In the community-based market, players solve their individual problems in each segment, and a virtual supervisory node gathers individual outcomes to generate coordination signal. Player with highest reputation factor or a local data centre can act as virtual supervisory node. The bilateral trading market is a fully decentralized market, where each player can simultaneously negotiate with trading partners over the price and energy. The structure of full and segmented P2P markets for community and bilateral trading are shown in Fig. 1a–d, respectively.

Fig. 1
figure 1

Market structures

Full size image

The considered market in this paper is a forward market, where players participate in the market for energy allocation for the next time slot. Also, the communication network among players is assumed to be connected, which means that there exists a path between any pair of players. Hence, the communication network may be totally different from the physical network. The proposed market clearing is developed as a deterministic clearing for a single market time, which can be extended for multiple time considering temporally binding constraints. Here the time unit is considered to be one hour, which allows using terms power and energy interchangeably.

3 Market clearing method

Consider a market composed of a set of Np agents including active prosumers as sellers, and consumers as buyers. During each time interval, each market participant joins to the market for energy trading and tries to minimize its cost. The objective function is to clear the market with large number of players with fewer data exchange, while the privacy of players and the minimization of cost are considered in the clearing process. An adaptive segmentation method for market clearing is proposed, which has three main steps namely segmentation, market clearing in each segment, and re-segmentation. The details of each step are given in the following.

3.1 Segmentation

Market segmentation is one of the most fundamental strategic marketing concepts, which can be used to group players according to their similarity in several dimensions related to a product under consideration. Segmenting a market means dividing its potential consumers into separate subsets where players in the same group are similar with respect to a given set of characteristics. Cluster analysis allows reducing the number of observations, by grouping them into homogeneous clusters. In the P2P energy trading, as there are a large number of players, market segmentation can be used to divide market into several segments, where in each segment only a few players with similar features negotiate for energy trading. In this paper, an adaptive segmentation method is proposed to divide a large-scale market into several subgroups, where two important characteristics are considered to form segments: capacity (to secure trading amount) and price (to improve/minimize utility/cost). For each player \(i\), a bid vector \(\varvec{\varpi }_{i}\) is submitted to the market.

$$\varvec{\varpi }_{i} = [\bar{X}_{i} ,\gamma_{i} ]\;\;\;\;\;\quad \forall i$$
(1)

where \(\bar{X}_{i}\) and \(\gamma_{i}\) are the maximum energy and its corresponding price for player \(i\), which indicates a point of marginal cost/benefit curve of player. If player i is a buyer, \(\bar{X}_{i}\) is a negative value and represents its demand, whereas for a seller, \(\bar{X}_{i}\) is a positive value representing the generation. A set of \(N_{\text{c}}\) segments is generated before segmentation and players will be clustered in these typical segments separately. Historical data can be used to set initial segments. Determining the number of segments without prior information is a non-trivial and computationally expensive problem. The segmentation method used in this paper is distance-based, where market players are assigned to the different segments \(j \in \left\{ {1, 2, \ldots ,N_{\text{c}} } \right\}\) based on their distance from the centroid of each segment. This problem can be formulated as follows:

$$\mathop { \hbox{min} }\limits_{y} \;\sum\limits_{i = 1}^{{N_{\text{p}} }} {\sum\limits_{j = 1}^{{N_{\text{c}} }} {y_{ij} } } [(\overline{X}_{i} - x_{j} )^{2} + (\gamma_{i} - \rho_{j} )^{2} ] \,$$
(2)
$${\text{s}} . {\text{t}} .\;\sum\limits_{j = 1}^{{N_{\text{c}} }} {y_{ij} } = 1\;\;\;\;\;\;\;\;\forall i$$
(3)
$$x_{j} = \frac{{\sum\limits_{i = 1}^{{N_{\text{p}} }} {y_{ij} \overline{X}_{i} } }}{{\sum\limits_{i = 1}^{{N_{\text{p}} }} {y_{ij} } }}\;\;\;\;\;\;\;\;\forall j$$
(4)
$$\rho_{j} = \frac{{\sum\limits_{i = 1}^{{N_{\text{p}} }} {y_{ij} \gamma_{i} } }}{{\sum\limits_{i = 1}^{{N_{\text{p}} }} {y_{ij} } }}\;\;\;\;\;\;\;\;\forall j$$
(5)
$$y_{ij} \in \left\{ {0,1} \right\}\;\;\;\quad \forall i, j$$
(6)

where \(y_{ij}\) is a binary number for allocation of player \(i\) to segment \(j\); \(x_{j}\) and \(\rho_{j}\) are energy and price of centroid in segment \(j\), respectively. The constraint (3) ensures that every player is only allocated to one segment. It is known that removing constraints (4) and (5) does not change the optimal solution of this problem. In other words, for each possible grouping of points to clusters, if cluster centres are freely chosen to minimize the total distance of points to these centres, the optimal centres will be located at the centroids of clusters [15]. Solving this nonlinear problem to optimality is computationally intensive [16]. The popular k-means algorithm provides an approximate solution to this problem through a sequence of iterations, as follows:

  • Step 1: Assign initial values to \(x_{j}\) and \(\rho_{j}\) variables.

  • Step 2: Fix the values of \(x_{j}\) and \(\rho_{j}\) variables and solve for \(y_{ij}\) variables.

  • Step 3: Fix the \(y_{ij}\) variables and solve for \(x_{j}\) and \(\rho_{j}\) variables.

The iteration between Steps 2 and 3 of this algorithm continues until the clustering obtained in Step 2 does not change in two consecutive iterations. A notable advantage of k-means algorithm is that the subproblems of Steps 2 and 3 have closed-form solutions. Given a fixed set of centres, the optimal assignment is obtained by assigning each point to the closest centre. As stated before, the optimal centres for each given clustering are located at the centroids of the clusters.

It should be noted that in each segment the total demand and supply should be balanced, and that this constraint needs to be taken into account during the segmentation. The goal here is to solve the clustering problem subject to these extra constraints:

$$\underline{\theta } \le \sum\limits_{i = 1}^{{N_{\text{p}} }} {y_{ij} } \overline{X}_{i} \le \overline{\theta }$$
(7)

where \(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\theta }\) and \(\bar{\theta }\) represent the bounds on the degree of imbalance in each cluster. This problem can be solved using the same approach as k-means, except that the subproblem of Step 2 changes into the following balanced assignment problem (BAP):

$$\left\{ {\begin{array}{*{20}l} {\mathop { \hbox{min} }\limits_{y} \sum\limits_{i = 1}^{{N_{\text{p}} }} {\sum\limits_{j = 1}^{{N_{\text{c}} }} {d_{ij} y_{ij} } } } \hfill \\ {{\text{s}} . {\text{t}} .\;(3) - (7)} \hfill \\ \end{array} } \right.$$
(8)

where the constant \(d_{ij}\) represents the distance between the bid vector of player \(i\) and coordinates of the centroid of the segment j, as computed in the previous iteration of the algorithm.

Theorem 1

BAP is strongly NP-hard.

Proof

This complexity result is proved by a polynomial reduction from 3-partition, which is known to be NP-complete [17]. The 3-partition problem can be described as follows: given \(B \in \varvec{Z}^{ + }\) and 3p elements with weights \(w_{i}\) such that \(B/4 \le w_{i} \le B/2\), how these elements can be partitioned into p sets such that the sum of weights in each partition equals B? An instance of BAP can be created from an instance of 3-partition by substituting \(N_{\text{p}}\) with 3p, \(N_{\text{c}}\) with p, \(d_{ij}\) with 0, \(\bar{X}_{i}\) with \(w_{i}\), and both \(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\theta }\) and \(\bar{\theta }\) with B.

The BAP can be solved as integer linear programming problem using existing solvers. However, the cost of solving an integer program at each iteration of the algorithm can be prohibitive. An alternative method is to use a local search method for solving this problem. Local search methods often produce high-quality solutions within reasonable times. The local search methods repeatedly move from one solution to another neighbouring solution in order to gradually improve the solution quality. This requires frequent evaluation of quality of neighbouring solutions, which in turn poses implementation challenges. These challenges have motivated development of constraint-based local search (CBLS) frameworks [18]. In CBLS frameworks, the problem and search strategy are specified in a high level language, which is later translated into efficient algorithms and carefully designed data structures. In this paper, OscaR.cbls is used to implement the local search method for solving BAP [19].

3.2 Market clearing in each segment for community-based market

After forming segments, players in each segment start to trade energy. They can decide on the traded energy independently. The objective of each market player is to minimize its own cost. A quadratic cost function for each player \(i\) is considered as:

$$C_{i} \left( {x_{i} } \right) = \frac{1}{2} \alpha_{i} x_{i}^{2} + \beta_{i} x_{i} + \delta_{i}$$
(9)

where \(\alpha_{i} ,\beta_{i} ,\delta_{i} > 0\) are cost function parameters of player \(i\); \(x_{i} > 0\) if the power is generated or injected into the system (player \(i\) is seller) and \(x_{i} < 0\) if player \(i\) is a buyer. For a seller this cost function refers to the cost of generating energy \(x_{i}\), whereas for the buyer, this function refers to the utility function and utility of buyer by consuming energy \(x_{i}\). In each segment, the objective is to minimize cost (or maximize welfare) of all players. Thus the objective function in segment \(j\) is presented as:

$$\hbox{min} \;\sum\limits_{i} {C_{i} (x_{i} )}$$
(10)
$${\text{s}} . {\text{t}} .\;\sum\limits_{i} {x_{i} } = 0$$
(11)
$$\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{X}_{i} \le x_{i} \le \bar{X}_{i} \;\;\;\;\quad \forall i$$
(12)

where \(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{X}_{i}\) is the minimum generated/demanded energy of player i. The energy of each player is bounded by (12) and at each time slot role of player is restrained to be either seller or buyer (\(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{X}_{i} \bar{X}_{i} \ge 0\)). The optimization problem in (10) is a convex problem subject to affine constraints where the inequality constraints related to minimum and maximum limits of demand and supply are local and can be treated as the boundaries of the domain of the problem. The problem in (10) can be augmented as (13) using Karush–Kuhn–Tucker (KKT) multipliers [20].

$$\sum\limits_{i} {C_{i} (x_{i} ) + \lambda_{j} } \sum\limits_{i} {x_{i} }$$
(13)

where \(\lambda_{j}\) represents Lagrangian or KKT multiplier and is the same as market clearing price in segment \(j\). In the community-based market, a single price system is considered in each segment, where players do not express individual preferences. By applying dual decomposition, a distributed iterative approach can be developed to maximize welfare without any need to have individual parameters of all market players [21]. The updates of the decision variables of player \(i\) is based on the KKT optimality conditions of the local optimization problem. The relaxed Lagrangian function of the local optimization problem can be expressed as:

$${\mathcal{L}}\left( {x_{i} ,\lambda_{j} ,\bar{\mu }_{i} ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{i} } \right) = C_{i} \left( {x_{i} } \right) - \lambda_{j} x_{i} + \bar{\mu }_{i} \left( {x_{i} - \bar{X}_{i} } \right) - \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{i} \left( {x_{i} - \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{X}_{i} } \right)$$
(14)

where \(\bar{\mu }_{i}\) and \(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{i}\) are Lagranigian multipliers related to the upper and lower boundaries of generation, respectively. With this definition, the first-order optimality condition of the relaxed problem given by KKT conditions is:

$$x_{{i,{\text{T}}}} = \frac{{\lambda_{j} - \bar{\mu }_{i} + \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{i} - \beta_{i} }}{{\alpha_{i} }}$$
(15)

where \(x_{{i,{\text{T}}}}\) is the target energy of player \(i\) at price \(\lambda_{j}\). An iterative algorithm can be applied to clear market in each segment, where each player is only aware of its own information and updates its energy based on the market price. The updating rules of Lagrangian multipliers, players’ energy, and price in the kth iteration can be expressed by (16)–(19).

figure a
$$x_{i}^{k + 1} = { \hbox{max} }\left( {0,x_{i}^{k} + \eta_{i} \left( {x_{{i,{\text{T}}}}^{k} - x_{i}^{k} } \right)} \right)$$
(16)
$$\bar{\mu }_{i}^{k + 1} = \hbox{max} \left( {0,\bar{\mu }_{i}^{k} + \xi_{i} \left( {x_{i}^{k + 1} - \bar{X}_{i} } \right)} \right)$$
(17)
$$\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{i}^{k + 1} = \hbox{max} \left( {0,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{i}^{k} + \xi_{i} \left( {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{X}_{i} - x_{i}^{k + 1} } \right)} \right)$$
(18)
$$\lambda_{j}^{k} = \hbox{max} \left( {0,\lambda_{j}^{k - 1} - \eta_{j} \left( {\mathop \sum \limits_{i} x_{i}^{k - 1} } \right)} \right)$$
(19)

where \(\eta_{i}\), \(\xi_{i}\), and \(\eta_{j}\) are positive tuning parameters. The executed algorithm by each player is presented in Algorithm 1. After receiving \(\lambda_{j}^{k}\), each player calculates its target energy and then will update its energy based on the price and the target energy. This energy will be sent to the coordinator, who calculates updated price using updated energy of players. This algorithm stops when stopping criteria in (20) is met.

$$\left| {\lambda_{j}^{k + 1} - \lambda_{j}^{k} } \right| < \varepsilon_{j}$$
(20)

where \(\varepsilon_{j}\) is a small positive parameter to indicate algorithm termination in segment j.

3.3 Market clearing in each segment for bilateral trading market

In the decentralized bilateral P2P energy trading, each player can trade energy with other players directly, without any need to a coordinator. In this case, the traded energy by each player i is defined as the sum of the energy \(x_{im}\) bilaterally traded with connected agent \(m \in \varOmega_{i}\), where \(\varOmega_{i}\) is the set of connected agents. The primal objective function for this market can be modelled as:

$$\mathop {\hbox{min} }\limits_{{x_{im} }} \;\sum\limits_{i} {\sum\limits_{m} {C_{i} } } (x_{im} )$$
(21)
$${\text{s}}.{\text{t}}.\;x_{im} + x_{mi} = 0\;\;\;\;\;\quad i \in N_{\text{p}} , m \in \varOmega_{i}$$
(22)
$$x_{i} = \sum\limits_{{m \in \varOmega_{i} }} {x_{im} } \;\;\;\;\;\quad \forall i$$
(23)

The constraint in (22) imposes physical feasibility of any trade, and the traded energy by each player is bounded by (12). Different methods such as ADMM and consensus + innovation methods can be applied to solve this problem [6]. The distributed updating rules for this method can be derived by utilizing the primal-dual gradient descent method as follows [22]:

$$\lambda_{im}^{k + 1} = \hbox{max} \left( {0,\lambda_{im}^{k} - \xi_{\lambda }^{k} \left( {x_{im} + x_{mi} } \right)} \right)$$
(24)
$$x_{im}^{k + 1} = { \hbox{max} }\left( {0, x_{ij}^{k} + f_{i}^{ - 1} \left( {\lambda_{im}^{k + 1} - \bar{\mu }_{i}^{k + 1} + \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{i}^{k + 1} - x_{i}^{k} } \right)} \right)$$
(25)
$$x_{im}^{k + 1} = { \hbox{min} }\left( {0, x_{ij}^{k} + f_{i}^{ - 1} \left( {\lambda_{im}^{k + 1} - \bar{\mu }_{i}^{k + 1} + \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{i}^{k + 1} - x_{i}^{k} } \right)} \right)$$
(26)
$$f_{i} \left( {\lambda_{im} } \right) \triangleq \mathop \sum \limits_{m} \lambda_{im} x_{im} - C_{i} \left( {x_{im} } \right)$$
(27)

where \(\lambda_{im}^{k}\), \(x_{im}^{k + 1}\) are the amount of traded energy and its corresponding price in each transaction; \(\xi_{\lambda }^{k}\) is the positive tuning parameter; fi(·) is defined as dual objective function of each player i. \(\bar{\mu }_{i}^{k + 1}\) and \(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{i}^{k + 1}\) can be calculated using (17) and (18), respectively. If player is a seller, the traded energy should be updated using (25), whereas for a buyer, this updated rule is stated as (26). The implemented bilateral market is fully decentralized, and after segmentation, all calculations are made by each player separately, without having a third party or coordinator. The executed algorithm by each player is given at Algorithm 2. The stopping criteria for this algorithm are as (28).

$$\left\{ {\begin{array}{*{20}l} {\left| {\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{i}^{k} - \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\mu }_{i}^{k - 1} } \right| < \varepsilon_{i} } \\ {\left| {\bar{\mu }_{i}^{k} - \bar{\mu }_{i}^{k - 1} } \right| < \varepsilon_{i} } \\ {\left| {\lambda_{im}^{k + 1} - \lambda_{im}^{k} } \right| < \varepsilon_{\lambda } } \\ \end{array} } \right.$$
(28)

where \(\varepsilon_{i}\) and \(\varepsilon_{\lambda }\) are small positive parameters to indicate algorithm termination by player i.

figure b

3.4 Re-segmentation

After market clearing, if players are not satisfied with the price in the segment, they will be assigned to a new segment. Satisfaction of players can be measured using satisfaction index (SI) as below:

$$SI_{i} = \left\{ {\begin{array}{*{20}l} {\chi_{i} \frac{{\lambda_{j} }}{{\gamma_{i} }}} \;\;\hfill & {x_{i} > 0} \hfill \\ {\chi_{i} \frac{{\gamma_{i} }}{{\lambda_{j} }}} \hfill & {x_{i} < 0} \hfill \\ \end{array} } \right.$$
(29)

where \(\chi_{i}\) is the reputation factor of player \(i\), which is calculated based on the performance of player in the previous transactions and can be calculated using proposed method in [23]. Reputation factor of players is considered in calculation of their satisfaction index to avoid them from cheating. The higher values of SI show higher satisfaction of player. Fairness of players satisfaction is evaluated using QoE of players [24]. This factor is calculated using satisfaction of all players in the segment and shows fairness from users’ perspective.

$$QoE_{j} = 1 - \frac{{\sigma_{j} }}{{\sigma_{{j,{ \hbox{max} }}} }}\;\;\;\;\; \quad \forall j$$
(30)

where \(\sigma_{j}\) is the standard deviation of weighted SI in segment j; \(\sigma_{{j,{ \hbox{max} }}}\) is the maximum possible standarnd deviation for these indices. The maximum value for \(QoE_{j}\) is 1, which means that variation in SI among players is zero, whenever all players have the same satisfaction level. QoE in each segment can be changed by changing clearing price. It can be proved that swapping players between segments will change clearing price, and that this swapping can change QoE in the segment. The clearing price in each segment should be extracted to show that it can be changed by swapping players. The first order optimality gives the energy for each player in the clearing point as (15). Also, in the clearing point traded energy is balanced, i.e. \(\mathop \sum \limits_{i} x_{i} = 0\). Clearing price in each segment can be calculated by substituting traded energy by each player in (11). The total traded energy can be obtained by adding traded energy of each player as presented in (31):

$$\sum\limits_{i} {x_{{i,{\text{T}}}} = \sum\limits_{i} {\frac{{\lambda_{j} + \underline{\mu }_{i} - \overline{\mu }_{i} - \beta_{i} }}{{\alpha_{i} }}} }$$
(31)

By substituting (31) into (11), price in each segment can be expressed as:

$$\lambda_{j} = \frac{1}{{N_{\text{p}} }}\sum\limits_{i} {\left( {\beta_{i} - \underline{\mu }_{i} - \overline{\mu }_{i} } \right)}$$
(32)

Equation (32) verifies that the rate of change in the price with regard to rate of change of players cost function parameter (\(\Delta \lambda_{j} /\Delta \beta_{i}\)) is always positive, which means that by increasing \(\beta_{i}\) (swapping a player with another player with higher \(\beta_{i}\) from another segment) the price in the segment will be increased. Since the parameters of market players are unknown, an alternative method is needed to designate the player with the highest or lowest \(\beta_{i}\) for swapping when it is required. For each player, the starting bid of player is known (\(\bar{X}_{i} ,\gamma_{i}\)). Assuming that all players start with a point from their marginal cost/benefit curve, from (9) the marginal price of each player is as (33), which can be rearranged to find \(\beta_{i}\).

$$\gamma_{i} = \alpha_{i} \bar{X}_{i} + \beta_{i}$$
(33)
figure c

From (29) and (33), it can be expressed that for players with \(x_{i} > 0\), higher values of SI show lower values of \(\beta_{i}\), and players with \(x_{i} < 0\) have higher SI when they have higher \(\beta_{i}\). Therefore, to increase price in a segment, a seller with higher SI (lower \(\beta_{i}\)) should be swapped with a seller with lower SI (higher \(\beta_{i}\)). Increasing price in the segment with the lowest QoE will increase the satisfaction level of players and reduce the difference between QoE in different segments. The algorithm for re-segmentation is summarized in Algorithm 3. In this algorithm, in the segment with the highest clearing price, seller with the highest SI will be transferred to the segment with the lowest price (to reduce price in this segment and increase QoE). Also, in the segment with the lowest clearing price, buyer with the highest SI will be transferred to the segment with the lowest price (to increase clearing price and increase QoE in the segment). This swapping is repeated till standard deviation of QoE (\(\sigma_{\text{QoE}}\)) in different segments is decreasing.

In the bilateral trading, as each transaction has a unique price, instead of \(\lambda_{j}\) in (29), the average price of different transactions of players in segment j can be used. The rest of algorithm would be the same as re-segmentation in the community-based market.

3.5 Scalability analysis

In practice, consumer-centric markets are challenged by increasing number of players. Hence, this section provides analysis on the ability of the proposed segmentation method to enhance scalability of these markets. It is important to notice that for P2P algorithms, the complexity of all agents depends on the number of trading partners. Therefore, the complexity of the algorithm can be reduced by limiting the number of trading partners per agent. P2P market will be challenged by increasingly large numbers of participants. Hence, the market clearing method should have the ability to scale up. As stated in [11], the time complexity of the negotiation algorithm can be split as:

$$T\left( {N_{\text{p}} } \right) = t_{\text{alg}} \left( {N_{\text{p}} } \right)t_{\text{str}} \left( {N_{\text{p}} } \right)$$
(34)

where \(t_{\text{alg}} \left( {N_{\text{p}} } \right)\) is the algorithmic complexity which indicates the dependency of the number of iteration for convergence on the number of agents \(N_{\text{p}}\); \(t_{\text{str}}\left( {N_{\text{p}} } \right)\) is the structural complexity which represents the dependency to the computation of each iteration. The algorithmic complexity includes complexity of clustering algorithm and market clearing algorithm. The implemented clustering algorithm have a complexity of

figure d

 For the implemented distributed algorithms, the complexity can be obtained empirically which yields that a complexity

figure e

for community-based clearing and a linear complexity

figure f

for bilateral trading, where \(W_{i}\) is number of trading partners of player i. Hence, the algorithm complexity for community-based and bilateral trading markets can be written as (35) and (36), respectively.

(35)
(36)

Also, the structural complexity depends on the computation and communication time, and for community-based market and bilateral trading market, it can be expressed as \(O\left( {N_{\text{p}} } \right)\) and \(O\left( {W_{i} } \right)\), respectively. As the algorithmic complexity and structural complexity are both related to the number of agents, reducing this number can reduce the time complexity of the algorithm. Since the proposed segmentation method can reduce number of trading agents, it can be verified that this method enhances the scalability of the P2P markets.

4 Case studies

4.1 Simulation setup

The proposed segmentation method is tested for a market with 100 players (55 sellers and 45 buyers). As the cost function parameters of market players are dependent on their preferences, these parameters are randomly generated, where \(\alpha_{i} \in \left( {0,1} \right)\) and \(\beta_{i} \in \left[ {2, 7} \right]\) if player i is a seller, and \(\beta_{i} \in \left[ {7, 15} \right]\) if player i is a buyer [25]. The minimum and maximum capacity of each player is randomly chosen to have \(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{X}_{i} \in \left[ {0, 8} \right]\;{\text{kWh}}\) and \(\bar{X}_{i} \in \left[ {0, 8} \right]\;{\text{kWh}}\), respectively. The stopping criteria in both structures are set to \(0.001\) for all segments and all players. Also, tuning parameter of all players for their local constraints is set to \(\xi_{i} = 0.001\). All case studies are performed on a computer with an Intel Core i7 processor running at 2.60 GHz using 16 GB of RAM.

4.2 Performance evaluation

The optimality of the proposed method is evaluated by comparing the results with the distributed implementation of both algorithms without segmentation. The total 100 players in the market are divided to 5 segments and results for this market are summarized in Table 1, where the computation time includes the required time for segmentation, and for the proposed method, QoE relates to the average QoE of all segments. From this table, it can be verified that in terms of total traded energy, for both market structures, the proposed method can reach approximately the same results as the method without segmentation. Since there is fewer number of players in each segment than in the total market, the number of required iterations for convergence is lower, which makes the clearing process faster. In the community-based market, the number of required signals in each iteration is \(2N_{\text{p}}\), and the total number of required signals (\(N_{si}\)) is \(2N_{\text{p}} K\), where K is the required number of iterations for convergence. Therefore, the total number of required signals in the segmented market can be obtained as follows:

$$N_{{{\text{s}}i}} = \sum\limits_{j} {2N_{{{\text{p}},j}} } K_{j}$$
(37)

where \(N_{{{\text{P}},j}}\) and \(K_{j}\) are number of agents and required iterations for convergence in segment j, respectively. In the bilateral trading market, the number of signal in each iteration is a factor of number of sellers and buyers and can be expressed as \(2N_{\text{B}} N_{\text{S}} K\), where \(N_{\text{B}}\) and \(N_{\text{S}}\) are the number of buyers and sellers, respectively, and \(N_{\text{B}} + N_{S} = N_{\text{p}}\). Therefore, the total number of signals in the bilateral trading market is as follows:

$$N_{{{\text{s}}i}} = \sum\limits_{j} {2N_{{{\text{B}},j}} } N_{{{\text{S}},j}} K_{j}$$
(38)

where \(N_{{{\text{B}},j}}\) and \(N_{{{\text{S}},j}}\) are the number of buyers and sellers in segment j, respectively.

The results from Table 1 show that using the proposed method, the number of signals can be reduced in both markets, which contributes to the lower communication overheads in the system. Also, the same QoE of players can be reached using the segmentation method, which shows that for this number of segments, segmentation is not decreasing the satisfaction of players.

Table 1 Performance evaluation of segmentation method
Full size table

4.3 Scalability analysis: impact of number of segments and players

This case study investigates the impact of number of segments on the performance of the proposed algorithm. For the same set of players as the previous section, the number of segments has changed from 1 to 25. When the number of segments is equal to one, it means that there is no segmentation in the market and results for this case are considered as the basis for the comparison. For this case study, computation time of algorithm, optimality gap and number of signals are compared. Optimality gap is the difference between total traded energies in the segmented market and market without segmentation. For the computation time and number of signals, results from market clearing without segmentation are considered as the basis to normalize the outputs. Figure 2 shows the results for the community-based market, which verifies that using the proposed method, the number of signals and computation time can be reduced with an approximate linear rate. However, by increasing in the number of segments, the optimality gap is increased. Results for bilateral market are shown in Fig. 3, which illustrate that increase in the number of segments can reduce computation time and number of signals. The focused results for number of segments from 21 to 25 are presented in Fig. 4, to confirm that increase in the number of segments is decreasing the computation time and number of signals. In Fig. 4, results for time and number of signals are not normalized. Comparing results in Figs. 2 and 3 yields that as bilateral market needs more computation time and a large number of signals, the segmentation method in bilateral trading has a more significant impact. Also, for the given market, the optimum number of segments is five, where computation time and number of signals can be reduced significantly without a considerable increase in the optimality gap.

Fig. 2
figure 2

Performance of segmentation method in community-based market

Full size image
Fig. 3
figure 3

Performance of segmentation method in bilateral trading market

Full size image
Fig. 4
figure 4

Performance of segmentation method in bilateral trading market (focus on number of segments 21 to 25)

Full size image

The performance of re-segmentation step has been evaluated in Fig. 5, where QoE of players for different market structures are compared before and after re-segmentation. This figure illustrates that QoE of players after re-segmentation is always higher than or equal to the QoE before re-segmentation. It should be noted that generally increasing in the number of segments reduces QoE of players. This is due to the decrease in market competitiveness as the number of players decreases.

Fig. 5
figure 5

QoE of players with and without re-segmentation

Full size image

The segmentation time for different number of players is measured to extract the complexity of the segmentation step, as plotted in Fig. 6. For different number of players, the segmentation step is executed 20 times and the average segmentation time is calculated. Figure 6 illustrates that increase in the number of players results in the linear increase of segmentation time, which verifies the linear complexity of the segmentation algorithm. Also, as shown in the figure, the segmentation time rises when the number of segments increases.

Fig. 6
figure 6

Impact of number of players on segmentation time

Full size image

5 Conclusion

In this paper, an adaptive segmentation method is proposed to enhance scalability of the P2P markets. The proposed method uses k-means clustering to group players to different segments based on the similarity among them, where market in each segment can be cleared separately. This method is implemented for two different market structures including community-based market and decentralized bilateral market and clearing algorithms for both structures are presented. Also, to make the segmentation method adaptive, a third step is considered to increase market fairness by increasing QoE of players. Results from case studies show that the proposed algorithm can enhance scalability of P2P markets by reducing computation time and number of signals for market clearing. This decrease in the bilateral market is more significant, since the number of trading partners of each player has a substantial impact on the computation time and number of signals.

Future research needs to be performed to incorporate additional features in the proposed segmentation method, such as geometric segmentation to incorporate transmission losses. Furthermore, the determination of number of segments for each market would be another possible topic for future works.