A Resource Allocation Mechanism for Edge-Blockchain

Abstract

Blockchain technology develops rapidly, which has a broad application prospect in solving security problem of the Internet of things (IoT). However, IoT devices with limited computing resources cannot afford high computing cost of blockchain mining. To solve this problem, edge computing is introduced to improve resource allocation efficiency in trusted IoT network based on blockchain. Therefore, IoT devices can choose to offload tasks to edge servers or local collaborative mining devices. Moreover, to maximize system revenue, a two-stage auction strategy is put forward to reasonably allocate computing resources in blockchain network. In the first stage of auction strategy, computing tasks can be offloaded to edge server, and the second stage realizes resource allocation of collaborative mining devices to utilize idle computing resource adequately. Simulation results show that the proposed strategy performs better than linear search algorithm in terms of effectiveness and rationality.

1 Introduction

First proposed by Satoshi in 2009, blockchain has attracted attention from both academia and industry [1]. Blockchain is a distributed database replicated and shared among members of network. When transaction is created, blockchain node verify transaction safely and transparently through the mining process. Then, transactions are added into chains, where links between blocks and their contents are cryptographically protected and cannot be forged [2]. Its features include security, transparency, distribution, tamper-proof, traceability, etc.

However, the development of blockchain in IoT devices (Electricity, transportation, logistics, etc.) is hindered by a major challenge brought by proof-of-work (PoW) process [3]. The main obstacle is that mobile devices with limited energy fall short to afford high computing resources of mining process. Some researches adopts cloud computing to address this problem. A resource allocation mechanism had been proposed to offload mining tasks to cloud server in [4]. However, it is not efficient due to high latency. Therefore, edge computing is a promising technology. In [5], author proposed a method to offload the task to edge server to decrease delay, but resources of idle devices in network are wasted. Idle devices in network can share computing resources with miners to assist in mining, then they can obtain rewards according to their contribution [6]. To improve resource allocation efficiency and utilize idle computing resource in blockchain network, a resource allocation mechanism is proposed in this paper where mining task can be offloaded to both edge server and local collaborative mining devices.

Compared with traditional resources allocation, innovations of our work lie in offloading of devices mining tasks to both edge computing server and co-mining devices, based on our proposed two-stage auction strategy. The main contributions of this paper are summarized as follows:

• Two offloading modes are proposed in the resource allocation mechanism based on edge computing. Miners can offload their mining tasks to non-mining devices or edge server, which takes advantage of idle resources within blockchain network and reduces load on edge server.

• A two-stage auction strategy is proposed to optimize system revenue. The resource allocation for offloading computing tasks to edge server is implemented in the first stage, and the second stage realizes resource allocation of offloading tasks to collaborative mining equipment.

• Simulation is conducted to evaluate key performance parameters including number of devices, reward factors, number of transactions and so on. And simulation results show that the proposed strategy performs better than linear search algorithm.

The rest of this paper is organized as follows: Sect. 2 reviews the system model. Section 3 presents the resource allocation strategy. The evaluation function is presented in Sect. 4. Section 5 analyzes experimental results and corresponding discussions. Section 6 presents conclusions and future work.

2 System Model

2.1 Network Model

As shown in Fig. 1, we consider a scenario where edge computing server (ES) provides resources for devices with insufficient computing resource to support blockchain services. There are $N = \{ 1,2, \ldots ,n\}$ devices with certain computing resource under an edge computing server. Due to lack of computing resource of device, they can offload their tasks to edge server to complete consensus process. In this paper, we define the computing resource that devices need to obtain from the edge server as $d = \{ d_{1} , \ldots ,d_{i} , \ldots ,d_{n} \}$, and auction price of device is $b = \{ b_{1} ,b_{2} , \ldots ,b_{n} \}$. $X = \{ x_{1} ,x_{2} , \ldots ,x_{n} \}$, $x_{i} \in \{ 0,1\}$ is used to indicate whether edge server allocates computing resources to device. ${\text{P}}\text{ = }\left\{ {p_{1} ,p_{2} , \ldots ,p_{n} } \right\}$ denotes actual transaction price of computing resources.

Fig. 1.

The blockchain network based on edge computing

In order to maintain the stability of blockchain network, a s-type utility function is used to describe benefits of blockchain network as Eq. (1) shows. With the increasing of computing resources, devices can get more rewards. Therefore, as more and more devices participate in mining process, blockchain network will also be safer and more stable.

$$ \chi (d_{N} ) = \frac{{1 - e^{{ - \mu d_{N} }} }}{{1 + \nu e^{{ - \mu d_{N} }} }} $$

(1)

where $d_{N} = \sum\nolimits_{i \in N} {d_{i} x_{i} }$ is the sum of computing resources, and $\mu ,\,\nu$ are positive parameters. It’s a slowing down of the utility function, and it’s going to go to 1.

2.2 Mining Mechanism Supported by Edge Server

Given $x_{i}$, $d_{i}$ and $g_{i}$, device $i's$ hash capability $\gamma_{i}$ is represented as Eq. (2).

$$ \gamma_{i} (d_{i} ,x_{i} ) = \frac{{d_{i}^{\alpha } x_{i} + g_{i} }}{{\sum\nolimits_{j \in N} {(g_{j} + d_{j}^{\alpha } x_{j} )} }} \, i \in N $$

(2)

where $\sum\nolimits_{i \in N} {\gamma_{i} = 1}$ and $\alpha$ is an exponential parameter of hash power function. $g_{i}$ is defined as the computing resource of each device. $\gamma_{i} (d,x)$ is hash power function with parameter is set as $\alpha = 1.2$ in the rest of this section [7].

In mining competition, miners need to be the first to find correct nonce to solve POW problem and propagate the block to reach consensus. The generation of new blocks follows a Poisson process with a constant rate $1/\lambda$. Firstly, miners collect unconfirmed transactions represent by $S = \{ s_{1} ,s_{2} , \ldots ,s_{n} \}$ into their blocks [8]. Secondly, miner $i$ broadcast its block to blockchain network to reach consensus, The propagation delay is affected by the size of transactions $s_{i}$. The first miner which reach consensus can get a reward $R$ composed of a fixed bonus $T$ and a flexible fee affected by transactions $s$ and the transaction fee rate $r$. Thus, miner $i's$ expected reward $R_{i}$ is expressed by Eq. (3).

$$ R_{i} = (T + rs_{i} )P_{i} (\gamma_{i} (d,x),s_{i} ) $$

(3)

Through mining competition above, getting rewards involves building blocks and reaching consensus. The probability of building a new block $P_{i}^{m}$ is equal to miner $i's$ hash power. However, the miner may even lose the tournament if its new block does not achieve consensus as first. This kind of mined block that cannot be added on to the blockchain is called orphaned block [8]. Moreover, the block containing larger size of transactions has higher chance becoming orphaned. Here, we assume that miner $i's$ block propagation time $\tau_{i}$ is linear to the size of transactions in its block, i.e., $\tau_{i} = \xi s_{i}$.$\xi$ is a constant that reflects the impact of $s_{i}$ on $\tau_{i}$. Since the arrival of new blocks follows a Poisson distribution, miner $i's$ orphaning probability can be approximated by $P_{i}^{o} = 1 - e^{{ - \frac{1}{\lambda }\tau_{i} }}$ [9]. After substituting $\tau_{i}$, $P_{i}$ can be calculated as follows.

$$ P_{i} = P_{i}^{m} (1 - P_{i}^{o} ) = \gamma_{i} e^{{ - \frac{1}{\lambda }\xi \tau_{i} }} $$

(4)

According to above mechanism, to maximize utility of system, an optimal function can be represented as Eq. (5)

$$ \begin{aligned} \begin{array}{*{20}l} {Max\left\{ {\sum\nolimits_{i \in N} {(T + \eta s_{i} )\frac{{d_{i}^{\alpha } x_{i} + g_{i} }}{{\sum\nolimits_{j \in N} {(g_{j} + d_{j} x_{j} )} }}e^{{ - \frac{1}{\lambda }\tau_{i} }} - \sum\nolimits_{i \in N} {d_{i} x_{i} Ecs - \sum\nolimits_{i \in N} {g_{i} cs_{i} } } } } \right\}} \hfill \\ {} \hfill \\ \end{array} \\ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,s.t. \, \sum\nolimits_{i \in N} {d_{i} x_{i} \le C{ , }x_{i} \in \left\{ {0,1} \right\}} { , }\forall i \in N \\ \end{aligned} $$

(5)

where ${\text{Ecs}}$ refers to cost of unit computing resources of edge computing server, $cs_{i}$ refers to cost of device $i's$ computing resources. Assume that computing resources of edge computing server is C. Then total computing resources that all devices can obtain from edge server should be less than C.

3 Resource Allocation Strategy

In this section, in order to solve proposed optimization problem (maximizing system benefits), a two-stage resource auction strategy is designed as Fig. 2 shows. In the first stage, VCG auction is used to realize resource allocation between edge servers and devices. In the second stage, vickrey auction is used to realize allocation between miner and sharer. In addition, we also prove the rationality and authenticity of strategy.

Fig. 2.

Two-stage auction strategy on computing resource allocation

3.1 Allocation Between Edge Server and Devices Based on VCC Auction

In the first stage of auction, VCG auction is adopted. Device $i$ first sent $d_{i}$ and offer $b_{i}$ to edge computing server. After receiving the bids from all devices, edge computing servers would select winner, allocate corresponding computing resources and determine actual transaction price according to VCG auction rules.

Thus, devices in blockchain network can be divided into two categories. As winner of the first auction, such devices can obtain computing resources from edge server, and act as miners in blockchain network. In addition, such devices also act as buyers in the second stage of Vickrey auction. Other devices are failed devices in the first phase of auction, which do not have enough computing resources to solve PoW problem, so they can only serve as computing resource sharing devices in blockchain network. We define $x_{i} \in \left\{ {0,1} \right\}$, when $x_{i} = 1$, device $i$ is a miner, $x_{i} = 0$ means device $i$ is a sharer.

3.2 Allocation Between Miners and Sharers Based on Vickrey Auttion

In particular, for buyer $j$, we calculate and get a composition of the agreed-price matrix $v_{j}^{i}$. Therefore auction bidding price in the second stage can be described by means of matrix Η.

$$ H = \left[ \begin{aligned} \nu_{1}^{1} \, \ldots \, \nu_{1}^{i} \, \ldots \, \nu_{1}^{K} \hfill \\ \nu_{j}^{1} \, \ldots \, \nu_{j}^{i} \, \ldots \, \nu_{j}^{K} \hfill \\ \nu_{L}^{1} \, \ldots \, \nu_{L}^{i} \, \ldots \, \nu_{L}^{K} \hfill \\ \end{aligned} \right] $$

(6)

Two problems need to be solved in the second stage of auction. The first is how to match sellers and buyers. To solve this problem, we adopt the second price matching mechanism according to the rules of Eq. (6).

$$ p_{j}^{2nd} = \arg \text{Sec} ond_{j \in N/w} \nu_{j}^{i} , j \in N\backslash W,i \in W $$

(7)

where $p_{j}^{2nd}$ is final transaction price of device $j$.$\nu_{j}^{i}$ is the agreed price where device $j$ is in resource sharer set $N\backslash W$ and device $i$ is in miner set W.

As for the second problem is how to determine actual transaction price between miner and sharer. $\delta \in (0,1)$ is defined. we will determine price of device resource interaction according to the rule of Eq. (8).

$$ \nu_{j}^{i} = \delta v_{i} + (1 - \delta )v_{j}, j \in N\backslash W,i \in W $$

(8)

where $\delta$ is the weight of pricing process, which is decided through negotiation between seller and buyer.

4 Evaluation Function in a Two-Stage Auction

In this section, in order to assess two stage auction strategy reasonably on the resource allocation strategy in blockchain network based on edge computing, we establish the profit function of edge service provider, miner and sharer, it provides a basis for simulation to verify that strategy is reasonable, flexible, and effective.

Firstly, for resource-sharing device $j \in N\backslash W$ in the blockchain network, the cost paid by device in two-stage auction process is the cost of selling its computing resources in the second-stage auction process.

$$ \text{Cos}_{j} = g_{j} cs_{j} , j \in N\backslash W $$

(9)

The income obtained by resource-sharing device j in two-stage auction is obtained by assisting some mining devices in the second stage auction

$$ R_{j}^{i} = g_{i} p_{j}^{2nd} , j \in N\backslash W $$

(10)

So device $j's$ net income is (11).

$$ U_{j} = g_{i} p_{j}^{2nd} - g_{j} cs_{j} , j \in N\backslash W $$

(11)

Then for miners $i \in W$, its costs in the process of two stage auction can be divided into two parts: payment of purchasing computing resource from edge computing server in the first stage of auction, as well as costs for collaborative mining resources sharing devices in the second stage of auction.

$$ M\cos_{i} = p_{i} + R_{j}^{i} , i \in W $$

(12)

Income of miner in two-stage auction is expected reward for participating in mining process, and miner’s income is Eq. (13)

$$ R_{i} = (T + \eta s_{i} )\frac{{d_{i}^{\alpha } x_{i} + g_{i} + g_{j} }}{{\sum\nolimits_{j \in N} {(g_{j} + d_{j}^{\alpha } x_{j} )} }}{\text{e}}^{{ - \frac{1}{\lambda }\tau_{i} }} , i \in W,j \in N\backslash W $$

(13)

Finally, for edge computing service provider, the cost obtained in two-stage auction is operating cost of edge server for selling edge computing resources:

$$ E\cos = \sum\nolimits_{i \in N} {d_{i} x_{i} \cdot Ecs} \, $$

(14)

Profit of edge computing server is paid by miners for gaining computing resource.

$$ Einc = \sum\nolimits_{i \in N} {p_{i} \, } $$

(15)

Therefore, edge computing service provider gains a net profit in two-stage auction process as follows:

$$ U{}_{E} = \sum\nolimits_{i \in N} {p_{i} - \sum\nolimits_{i \in N} {d_{i} x_{i} \cdot Ecs} } $$

(16)

Above all, the overall income of whole system can be calculated as follows.

$$ S_{all} = \sum\nolimits_{i \in W} {U_{i} } + \sum\nolimits_{j \in N\backslash W} {U_{j} } + U_{E} $$

(17)

5 Experiment Results and Performance Analysis

In this chapter, the two-stage auction strategy is simulated to verify the effectiveness and rationality of the two-stage auction strategy, and is compared with linear search algorithm mentioned above. Simulation result proves that the strategy proposed has better system benefits.

Table 1. Simulation parameter

Fig. 3.

The relationship between auction winners and number of devices with different edge computing resource.

We first analyze the relationship between number of auction winners (i.e., miner) and number of network devices under different amount of computing resource of edge server. In Fig. 3, as the amount of devices increases, the number of winners grows at a gradually slowing rate, and then converges to a stable value. At same time, we find that the stable value is determined by computing resource provided by edge server.

Fig. 4.

The influence of transaction on system revenue under different equipment quantity.

As shown in Fig. 4, with the increasing of packaging transaction in different number of devices, the system revenue will first increase and then gradually decline after reaching maximum value. Reason is that as transaction rises, the propagation delay will also increase. Hence a larger probability of generating isolated blocks and reducing the system revenue will rise.

Fig. 5.

The difference between bidding price and trading price.

In Fig. 5, we compared the relationship between buyer’s bidding price and trading price in the first stage of auction when there are 30 edge devices. The encapsulation information of block is in optimal area value as shown in Fig. 5 and other fixed parameters are complied with Table 1. As can be seen from Fig. 5, due to the adoption of VCG auction strategy, the final price of buyers is generally lower than bidding price, thus avoiding buyers from being cheated in auction process.

Fig. 6.

Comparison of benefits of different algorithms.

In addition, we also compared our proposed two-stage auction algorithm with existing linear search algorithm. The results are shown in Fig. 6, our proposed two-stage auction strategy has better performance than existing strategy in improving the revenue of system.

6 Conclusion and Future Work

In this paper, we propose a resource allocation mechanism for blockchain network based on edge computing to solve the PoW problem, where blockchain is used to solve the security problem of IoT. In order to maximize the system revenue, a two-stage auction strategy is proposed. Offloading computing tasks to edge server is implemented in the first stage, and the second stage realizes resource allocation of collaborative mining devices. Then, in simulation, we studied the effects of various parameters such as number of devices, transaction and reward factor on policy performance. Moreover, the performance of our mechanism is compared with linear search method, the simulation results show that under our proposed mechanism, system can get better benefits. In the future, we will consider the different requirements of the devices.