Distributed energy transaction matching method based on energy network constraints and multiple knapsack model

Abstract

This invention provides a distributed energy transaction matching method based on energy network constraints and multiple knapsack model. First, it considers the matching between financial market transactions and actual energy network scheduling, then generates security constraints on the results of distributed transactions. Next, it designs a multiple knapsack model for peer-to-peer distributed transactions, which can meet the common quotation needs of users or producers who issue transactions and achieve efficient matching under energy network security checks. Finally, the model is verified based on the blockchain Ethereum smart contract test verification. This method provides new ideas for the connection between distributed energy trading and actual physical dispatch, proposes an inclusive and efficient matching model for the point-to-point distributed trading market, which has great reference value for the connection between distributed energy trading and actual conditions.

Claims

1. A distributed energy transaction matching and dispatching method based on energy network constraints and a multiple knapsack model, comprising: restricting a maximum possible transaction volume of each of users including buyers and sellers, through an energy trading platform and a blockchain distributed transaction systems all connected with an energy network, to be a smaller value of a declared volume and an energy network limit volume through security checks for distributed transactions on the energy network according to an augmented optimization model of energy scheduling, wherein the augmented optimization model is configured to take y as a system optimization variable, consider a modification of an existing transaction volume, and ensure that a modification amount is as small as possible making an impact on transaction is smaller; obtaining a constraint condition of 0<y<y.sup.sp preventing a mismatch between a current energy transaction market and an actual dispatching by restricting the modification amount of transaction being only capable of reducing or cancelling the existing transaction volume rather than forcing the user to increase transaction volume after the energy network is checked, wherein the augmented optimization model is: $\left\{\begin{array}{c}\underset{x,y}{\max }f\left(x,y\right)+{\rho }^T\left(y^{\mathrm{sp}}-y\right)\\ s.t.g_i\left(x,y\right)=0,i=1,\mathrm{.Math.},N_{\mathrm{eq}}\\ h_j\left(x,y\right)\le 0,j=1,\mathrm{.Math.},N_{\mathrm{ieq}}\\ 0\le y\le y^{\mathrm{sp}}\end{array}\right\}\hspace{1em},$ where x is a decision variable of each of the distributed transaction systems, y is a load and energy production of each of the distributed transaction systems, y.sup.sp is a transaction energy volume determined by an Ethereum contract, y=y.sup.sp indicates that a scheduling boundary condition of each of the distributed transaction systems is the transaction energy volume determined by the Ethereum contract, and g.sub.i and h.sub.j are respectively equality and inequality constraints of energy network security; matching transactions between the buyers and the sellers, by a energy trading system according to the maximum possible transaction volumes of the users and quotations of the buyers and the sellers and obtaining transaction results for the users according to a solving algorithm of the multiple knapsack model fit with peer-to-peer transactions; uploading the matched transaction, by the energy trading system to the energy network for safety verification based on energy constraints of the declared volume and the energy network limit volume; verifying the matched transaction with the energy constraints and facilitating the transaction by smart contract of a blockchain distributed transaction system; and performing, by the energy network, actual physical stream transmissions of energy for the users based on the verified matched transaction results.

2. The distributed energy transaction matching and dispatching method according to claim 1, wherein an objective function of the multiple knapsack model is: $\left\{\begin{array}{c}\underset{P_g,P_d}{\max }\underset{j=1}{\overset{N_d}{.Math.}}{\lambda }_{d,j}{P}_{d,j}-\underset{i=1}{\overset{N_g}{.Math.}}{\lambda }_{g,i}{P}_{g,i}\\ s.t.\underset{i=1}{\overset{N_g}{.Math.}}{P}_{g,i}=\underset{{}^{j=1}}{\overset{N_d}{.Math.}}{P}_{d,j}\\ 0\le P_{g,i}\le P_{g,i}^{\max },0\le P_{d,j}\le P_{d,j}^{\max }\end{array}\right\}\hspace{1em}$ where λ.sub.d,j is the quotation of a j.sup.th buyer, λ.sub.g,i is the quotation of an i.sup.th seller, P.sub.d,j is a matched transaction volume of the j.sup.th buyer, P.sub.g,i a matched transaction volume of the j.sup.th seller, N.sub.g and N.sub.d are respectively the numbers of the sellers and buyers, P.sub.d,j.sup.max and P.sub.g,i.sup.max are respectively maximum possible transaction volumes of the j.sup.th buyer and i.sup.th seller.

3. The distributed energy transaction matching and dispatching method according to claim 2, wherein the solving algorithm of the multiple knapsack model is described as: converting the peer-to-peer energy transaction into a multiple knapsack problem; wherein when N.sub.d>N.sub.g, placing N.sub.d kinds of commodities into N.sub.g boxes with a capacity of P.sub.g,i.sup.max one after another, where a weight of each commodity j is P.sub.j, and a value of unit weight is λ.sub.j; sorting values of the commodities from high to low, placing a high-value commodity first into the boxes until the weight reaches requirements, and repeating a same execution to a next box until the requirements are not met; wherein when N.sub.d≤N.sub.g, placing N.sub.g kinds of goods into N.sub.d boxes with a capacity of P.sub.d,j.sup.max one after another, where a weight of each commodity i is P.sub.i, and a value of unit weight is λ.sub.i; sorting values of the commodities from small to large, placing a small value commodity first until the weight reaches requirements, and repeating a same execution to a next box until the requirements are not met.

4. The distributed energy transaction matching and dispatching method according to claim 3, wherein the multiple knapsack model is configured to solve a problem of the peer-to-peer transactions, which is used in conjunction with the decentralized blockchain technically similar features, the solving algorithm of the multiple knapsack model is written in the Ethereum contract using a “Solidity” to solve the problem.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is the flow chart of the energy network security check;

(2) FIG. 2 is the diagram of the transaction matching process;

(3) FIG. 3 shows the matching results without energy grid verification in the calculation example;

(4) FIG. 4 shows the matching results with energy network verification;

(5) FIG. 5 shows the results of the final 7 successful transactions.

DETAILED DESCRIPTION OF THE INVENTION

(6) Further details of the invention are given below in conjunction with the appended drawings and embodiments:

(7) 1. The distributed energy transaction matching method based on energy network constraints and multiple knapsack model is implemented through the following steps:

(8) (1) An Augmented Optimization Model for Energy Dispatch

(9) Purely distributed transactions cannot consider the actual operation of energy grid scheduling, because all users cannot fully understand the accurate energy grid model and physical operation mechanism. However, energy trading is often constrained by the safe operation of the actual energy network. Therefore, the matching of trading and scheduling must be considered. The traditional optimal scheduling model of energy can be expressed as (1), where x is the decision variable of the system, y is the load and energy production of the system, y.sup.sp is the transaction energy amount determined by the contract, and y=y.sup.sp indicates that the system's scheduling boundary condition is the transaction volume determined by the contract. g.sub.i and h.sub.j are equality and inequality constraints of network system security.

(10) $\begin{array}{cc}\left\{\begin{array}{c}\underset{x}{\max }f\left(x,y\right)\\ s.t.g_i\left(x,y\right)=0,i=1,\mathrm{.Math.},N_{\mathrm{eq}}\\ h_j\left(x,y\right)\le 0,j=1,\mathrm{.Math.},N_{\mathrm{ieq}}\\ y=y^{\mathrm{sp}}\end{array}\right\}\hspace{1em}& \left(1\right)\end{array}$

(11) However, the optimal scheduling model has no feasible solution, which means that for scheduling under a given energy transaction volume, the safe operation constraints will be violated. Therefore, the dispatch needs to check the energy transaction volume to form the following augmented optimization model. Users trade with each other, and at the same time the trading platform interacts with the energy network, check the security of the physical stream transmission. The final transaction result is distributed on the blockchain. The entire process is shown in FIG. 1.

(12) $\begin{array}{cc}\left\{\begin{array}{c}\underset{x,y}{\max }f\left(x,y\right)+{\rho }^T\left(y^{\mathrm{sp}}-y\right)\\ s.t.g_i\left(x,y\right)=0,i=1,\mathrm{.Math.},N_{\mathrm{eq}}\\ h_j\left(x,y\right)\le 0,j=1,\mathrm{.Math.},N_{\mathrm{ieq}}\\ 0\le y\le y^{\mathrm{sp}}\end{array}\right\}\hspace{1em}& \left(2\right)\end{array}$

(13) Among them, the augmented optimization model takes y as the optimization variable of the system, considering the modification of the existing transaction volume, and ensures that the modification amount is as small as possible, so that the impact on the transaction is smaller. It should be noted that after the energy network is checked, the correction amount of the transaction can only reduce or cancel the transaction volume, but cannot force the user to increase transaction volume, so the constraint of 0≤y≤y.sup.sp is obtained.

(14) (2) Multiple Knapsack Model Design Process Under a Safety Check

(15) 1) Establish an Initial Transaction Matching Model

(16) In the matching stage, the same subject can be both producer and consumer in different periods, but the subject can only have one identity at one trading node. In this case, the main task of the energy trading system is to match the amount of energy to the greatest extent, while satisfying some transaction volume constraints given by the energy network check, so that more transactions are successful, and the transaction price is determined according to the market quotation. Set λ.sub.d,j as the quotation of the j.sup.th user, λ.sub.g,i as the quotation of the i.sup.th producer, P.sub.d,j as the matching transaction volume of the j.sup.th user, and set P.sub.g,i as the matching transaction volume of the i.sup.th producer. N.sub.g and N.sub.d are the numbers of producers and users. Because the transaction to be matched originates from the multi-party participants of the energy trading platform, the quotations of the buyer and the seller can be generated at any time, and the transaction can be completed once the price matches, it is attributed to a continuous double auction mechanism.

(17) First, confirm the supply and demand relationship based on the current market volume. When N.sub.d>N.sub.g it is the situation when demand exceeds supply. When N.sub.d≤N.sub.g it is the situation when supply exceeds demand. Based on this, the following matching transaction model is established.

(18) $\begin{array}{cc}\left\{\begin{array}{c}\underset{P_g,P_d}{\max }\underset{j=1}{\overset{N_d}{.Math.}}{\lambda }_{d,j}{P}_{d,j}-\underset{i=1}{\overset{N_g}{.Math.}}{\lambda }_{g,i}{P}_{g,i}\\ s.t.\underset{i=1}{\overset{N_g}{.Math.}}{P}_{g,i}=\underset{{}^{j=1}}{\overset{N_d}{.Math.}}{P}_{d,j}\\ 0\le P_{g,i}\le P_{g,i}^{\max },0\le P_{d,j}\le P_{d,j}^{\max }\end{array}\right\}\hspace{1em}& \left(3\right)\end{array}$

(19) Among them, P.sub.d,j.sup.max and P.sub.g,i.sup.max is the maximum possible transaction volume of the j.sup.th user and the i.sup.th producer, and determined by:
P.sub.g,i.sup.max=min(U.sub.g,i,P.sub.g,i.sup.bid),P.sub.d,j.sup.max=min(U.sub.d,j,P.sub.d,j.sup.bid)  (4)

(20) P.sub.d,j.sup.bid and P.sub.g,i.sup.bid are declaration amount of the j.sup.th user and the i.sup.th producer, U.sub.d,j and U.sub.g,i are limits of the j.sup.th user and the i.sup.th producer after energy network dispatch checking.

(21) 2) Design Multiple Knapsack Solution Ideas

(22) It can be seen that the above optimization model is a linear optimization problem with only one equality constraint and upper and lower bound constraints. Such a special linear optimization problem is transformed into a continuous knapsack problem. When supply exceeds demand, N.sub.d>N.sub.g, the problem can be described from the perspective of the knapsack problem as: We have N.sub.d kinds of commodities placed in N.sub.g boxes with a capacity of P.sub.g,i.sup.max one after another. The weight of each commodity j is P.sub.j, and the value of unit weight is λ.sub.j, then how to load commodities to maximize the total value? The solution idea of the algorithm is: sort the value of the goods from high to low, and place the goods of high value first until the weight reaches the requirement. When N.sub.d≤N.sub.g, there are N.sub.g kinds of commodities placed in N.sub.d boxes with a capacity of P.sub.d,j.sup.max one after another. The weight of each commodity i is P.sub.i, and the value of unit weight is λ.sub.i. The value of the commodities is sorted from low to high, and the low value is first installed. Then change the box and repeat until the conditions are not met.

3) Algorithm Solution Design Based on Blockchain Smart Contract

Definition

(23) i. The corresponding transaction volume of the i.sup.th producer and the j.sup.th user which constitutes a i×j dimensional transaction volume matrix P; ii. The corresponding transaction price of the i.sup.th producer and the j.sup.th user is λ.sub.ij, which constitutes a i×j dimensional transaction volume matrix λ; iii. The remaining amount of the i.sup.th producer's transaction is P.sub.g,i.sup.Δ; iv. The remaining transaction amount of the j.sup.th user is P.sub.d,j.sup.Δ.

(24) Input: The maximum possible transaction volume and quotation of both buyers and sellers, as the following matrix:

(25) $\begin{array}{cc}\left\{\begin{array}{c}{P}_d=(P_{d,1}^{\max },P_{d,2}^{\max },\mathrm{.Math.},P_{d,N_d}^{\max }{)}^T\\ P_g=(P_{g,1}^{\max },P_{g,2}^{\max },\mathrm{.Math.},P_{g,N_g}^{\max }{)}^T\\ {\lambda }_d=({\lambda }_{d,1},{\lambda }_{d,2},\mathrm{.Math.},N_{d,N_d}{)}^T\\ {\lambda }_g={\left({\lambda }_{g,1},{\lambda }_{g,2},\mathrm{.Math.},{\lambda }_{g,N_g}\right)}^T\end{array}\right\}& \left(5\right)\end{array}$

(26) Output: Transaction volume matrix P and transaction price matrix λ.

(27) Initialize: i=1; j=1; P=0; λ=0.

(28) Run:

(29) TABLE-US-00001  1 IF N.sub.d > N.sub.g, then:  2  Sort from largest to smallest for λ.sub.d, the sort set is  ${\lambda }_{I_1},{\lambda }_{I_2},\mathrm{.Math.},{\lambda }_{I_{N_d}};$  3  IF i ≤ N.sub.g, then:  4   p.sub.g,i.sup.Δ = P.sub.g,i.sup.max; P.sub.d,j.sup.Δ = P.sub.d,j.sup.max;  5   When P.sub.g,i.sup.Δ − P.sub.ij ≥ 0 and λ.sub.I.sub.j ≥ λ.sub.g,i, repeat execution:  6    P.sub.ij ← P.sub.I.sub.j;  7    P.sub.g,i.sup.Δ ← P.sub.g,i.sup.Δ − P.sub.ij;  8    P.sub.d,j.sup.Δ ← 0;  9    j ← j + 1; 10   Or: 11    P.sub.ij ← P.sub.g,i.sup.Δ; 12    P.sub.g,i.sup.Δ ← 0; 13    P.sub.d,j.sup.Δ ← P.sub.d,j.sup.Δ − P.sub.ij; 14    i ← i + 1; 15  Or: 16   ${\lambda }_{\mathrm{ij}}=\{\begin{array}{cc}{\lambda }_{d,j}& P_{\mathrm{ij}}>0\\ 0& P_{\mathrm{ij}}=0\end{array},j=1,2,\mathrm{.Math.},N_d$ 17 End 18 IF N.sub.d ≤ N.sub.g, then: 19   Sort from smallest to largest for λ.sub.g, the sort set is   ${\lambda }_{I_1},{\lambda }_{I_2},\mathrm{.Math.},{\lambda }_{I_{N_g}};$ 20   IF j ≤ N.sub.d, Then: 21    P.sub.d,j.sup.Δ = P.sub.d,j.sup.max; P.sub.g,i.sup.Δ = P.sub.g,i.sup.max; 22    When P.sub.d,j.sup.Δ − P.sub.ij ≥ 0 and λ.sub.I.sub.i ≤ λ.sub.d,j, repeat execution: 23     P.sub.ij ← P.sub.I.sub.i; 24     P.sub.d,j.sup.Δ ← P.sub.d,j.sup.Δ − P.sub.ij; 25     P.sub.g,i.sup.Δ ← 0; 26     i ← i + 1; 27   Or: 28   P.sub.ij ← P.sub.d,j.sup.Δ; 29   P.sub.d,j.sup.Δ ← 0; 30   P.sub.g,i.sup.Δ ← P.sub.g,i.sup.Δ − P.sub.ij; 31   j ← j + 1; 32  Or: 33   0${\lambda }_{\mathrm{ij}}=\{\begin{array}{cc}{\lambda }_{g,i}& P_{\mathrm{ij}}>0\\ 0& P_{\mathrm{ij}}=0\end{array},i=1,2,\mathrm{.Math.},N_g$ 34 End

(30) Further, we can get

(31) a) The optimal transaction volume for users and producers is

(32) $\begin{array}{cc}\{\begin{array}{c}{P}_{g,i}^{*}=P_{g,i}^{\max }-P_{g,i}^{\Delta },i=1,2,\mathrm{.Math.},N_g\\ P_{d,j}^{*}=P_{d,j}^{\max }-P_{d,j}^{\Delta },j=1,2,\mathrm{.Math.},N_d\end{array}& \left(6\right)\end{array}$

(33) b) When N.sub.d>N.sub.g, transaction income of the i.sup.th producer is

(34) $\underset{j=1}{\overset{N_d}{.Math.}}{\lambda }_{\mathrm{ij}}{P}_{\mathrm{ij}},$
j=1, 2, . . . , N.sub.d, which is

(35) $\underset{j=1}{\overset{N_d}{.Math.}}\left({\lambda }_{\mathrm{ij}}-{\lambda }_{g,i}\right)P_{\mathrm{ij}},j=1,2,\mathrm{.Math.},N_d$
higher than expected earnings of the quoted price.

(36) c) When N.sub.d≤N.sub.g, Transaction outcome of the j.sup.th user is

(37) $\underset{i=1}{\overset{N_g}{.Math.}}{\lambda }_{\mathrm{ij}}{P}_{\mathrm{ij}},$
i=1, 2, . . . , N.sub.g, which is

(38) $\underset{i=1}{\overset{N_g}{.Math.}}\left({\lambda }_{d,j}-{\lambda }_{\mathrm{ij}}\right)P_{\mathrm{ij}},i=1,2,\mathrm{.Math.},N_g$
lower than the expected cost of the quoted price.

(39) (3) Analysis of Interaction Between Energy Network and Blockchain System

(40) Further, consider the interaction of energy network constraints and blockchain systems as shown in FIG. 2. After the energy trading system obtains the amount of the transaction to be matched, upload it to the energy network for safety verification. If the verification is passed, the smart contract command is triggered to facilitate the transaction. If the transaction fails, the energy network will return the transaction volume constraint, and similarly, multiple blockchain systems can interact with the energy network.

(41) At the beginning of the transaction, it is possible to directly match the transaction without considering the network security constraints to obtain the result of the match-making transaction y.sub.0.sup.sp=(P.sub.g,i*,P.sub.d,j*). If the check is unsuccessful, execute the augmented optimization model (2), and the result must be y.sub.0*≤y.sub.0.sup.sp. The transaction volume constraint y.sub.0* is transferred to the matching model. According to (4), it can be seen that the result of the matching transaction meets the feasibility of the model, and there must be y.sub.1.sup.sp≤y.sub.0*. Further, there are y.sub.1.sup.sp≤y.sub.0*≤y.sub.0.sup.sp. It can be seen that with the iteration of the energy network and the blockchain transaction system, a sequence (y.sub.0.sup.sp, y.sub.1.sup.sp, . . . ) can be obtained. The sequence is monotonically decreasing and has a lower bound, that is, the Cauchy sequence, so it must converge.

(42) 2. Case Analysis

(43) After the method of the invention is realized based on the smart contract of blockchain, the following scenario is set up: in this calculation example, there are 13 users, including 8 sellers and 5 buyers, simulating the market situation as oversupply. Assuming that there are already 8 sellers and 5 buyers in the market and post transactions in sequence to Table 1. It is stipulated that the type of energy traded is testing energy, and the transaction volume applied by 13 users is generated at their own will. The quotation range for the test energy is between 30.00 and 50.00 cents.

(44) (1) Comparison Between the Situation with or without Energy Network Constraints

(45) First, transaction results that do not consider energy network security constraints are shown in Table 1, it can be seen that some users with reasonable prices have successfully traded.

(46) TABLE-US-00002 TABLE 1 Information released by users Amount Remaining Release State (kw .Math. h) amount (kw .Math. h) price (cents) Buyer A Finished 350 0 38.00 B Finished 300 0 40.00 C Unfinished 450 450 35.00 D Finished 500 0 39.00 E Finished 500 0 46.00 Seller F Finished 200 0 31.00 G Finished 450 0 39.00 H Unfinished 50 50 46.00 I Finished 150 0 34.00 J Finished 200 0 43.00 K Unfinished 150 150 44.00 L Finished 350 0 37.00 M Finished 300 0 33.00

(47) Next, get the results of all matched transactions in the blockchain. Eight successful transactions generate new blocks, and the generated information is divided into transaction information and block information, as shown in FIG. 3. Here the block height, Nonce and Difficulty in the block information are displayed.

(48) Furthermore, suppose that the actual trading volume of 5 buyers is constrained by the security of the energy network, and the constraints are shown in Table 2. New transaction results are shown in FIG. 4. It can be seen that the transaction results with or without energy network constraints are different. Take users A and B as an example, in unconstrained condition, users A and B bought all energy sold by users F, M, and I, resulting in user C could not match the energy that meets the quotation, and his transaction failed. In constraints of the energy network, the purchase volume of A and B was constrained, also, M and I still had surplus energy, and C successfully bought in batches. It can be seen that results that contain energy network constraints are more in line with actual physical conditions.

(49) TABLE-US-00003 TABLE 2 Energy network constraints and correction values Users A B C D E Initially Volume (kw .Math. h) 350 300 unsettled 500 500 Constrained Volume (kw .Math. h) 250 200 200 350 450 Final Volume (kw .Math. h) 250 200 200 350 450

(50) (2) Analysis of Actual Transaction Results

(51) From the above transaction information, it can be seen that in the whole process, 7 transactions were finally completed in sequence. The transaction volume and transaction price are shown in FIG. 5 in order. As buyers entered the market, low-cost energy had been sold off, and the transaction price gradually increased. The transaction volume was determined by the need of buyers and sellers. At the same time, in such a market where supply exceeded demand, buyers had more initiative. After buyers entered the market, the system would sort all the current sellers' quotations from low to high, and matched them with buyers in turn.

(52) For example, user A asked for purchase at 38.00 (cents) and release volume of 250 (kw.Math.h), and finally succeeded at 31.00 (cents) for 200 (kw.Math.h) and 33.00 (cents) for 50 (kw.Math.h), that is, buyers' purchase price was less than or equal to his published price. Of course, the sellers' purchase price would not be lower than his published price, which is in line with the expectation of matching results. Besides, some users' quotations were too deviated to complete a transaction. For example, users C and D, after entering the market, the amount of energy available to meet their published prices was less than their needs, so only part of the transaction could be traded, and the rest part would continue to be saved in the market waiting for conditions to be met.

(53) For sellers, H, J, K, the reason they did not complete the transaction is that user H's selling price was higher than all buyers' quotations at that time, so it would not be matched. Although quotations were relatively suitable for users J, K, there were competitors with lower selling prices in the market and the quantity meet needs of buyers, so there was no transaction.

(54) Furthermore, the transaction cost is further quantitatively analyzed in Table 3. The preferential rate represents the ratio of the actual cost to the expected cost. It can be seen that all 5 buyers have received different discounts.

(55) TABLE-US-00004 TABLE 3 Transaction cost analysis Users A B C D E Expected cost (cerds) 9500 8000 7000 13650 20700 Actual cost (ccats) 7850 6600 6750 12950 17550 Discount rate (%) 82.63 82.5 96.43 94.87 84.78

(56) Actual calculation examples above can summarize that: 1) The entire transaction process is implemented according to the logic designed by the smart contract and energy trading system, and it scientifically complies with energy network security check and analyzes user's quotations based on the market situation; 2) Based on the blockchain technology, the energy trading platform can let each transaction data on the chain to generate blocks, and the block data is open and transparent; 3) While protecting interests of both parties, it can save costs, improve transaction efficiency and user experience.