# Blockchain-Enabled Task Offloading and Resource Allocation in Fog Computing Networks

Authors: Xiaoge Huang; Xuesong Deng; Chengchao Liang; Weiwei Fan
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

To address the data security and user privacy issues in the task offloading process and resource allocation of the fog computing network, a blockchain-enabled fog computing network task offloading model is proposed in this paper. Furthermore, to reduce the network utility which is defined as the total energy consumption of the fog computing network and the total delay of the blockchain network, a blockchain-enabled fog computing network task offloading and resource allocation algorithm (TR-BFCN) is proposed to jointly optimize the task offloading decision and resource allocation. Finally, the original nonconvex optimization problem is converted into two suboptimization problems, namely, task offloading decisions and computational resource allocations. Moreover, a two-stage Stackelberg game model is designed to obtain the optimal amount of purchased resource and the optimal resource pricing. Simulation results show that the proposed TR-BFCN algorithm can effectively reduce the network utility compared with other algorithms.


---

## Body

## 1. Introduction

With the rapid growth of smart devices and the development of the Internet of Things (IoT), the traditional network architecture is facing a huge flow load problem [1]. As a supplement to cloud computing, fog computing could randomly deploy a large number of fog nodes (FNs) at the edge of the network to deal with the real-time application requirements generated by devices and improve network performance [2]. In the distributed fog network, IoT devices (IDs) interact with FNs in real time. Due to the mobility of IDs, service migration across FNs will occur during the interaction [3]. Meanwhile, because FNs are distributed in an unsupervised environment, the security of the user’s data during the task processing is an important challenge for fog computing networks (FCNs) [4]. Currently, to ensure the user privacy and data security in fog computing networks, the following two methods are taken into account:
(i)
Method 1: develop a reliable, effective mechanism to evaluate the reputation of IDs and FNs. Reputation of IDs and FNs is used to indicate their credibility [5]. If the user privacy is leaked or data tampering occurs, the reputation of the associated nodes will be decreased. Reference [6] proposed a context-aware trust evaluation algorithm to calculate the trustworthiness of users in FCNs. Reference [7] proposed a trust forwarding mechanism in FCNs, which divided the network into edge communication communities, and set the reputation of nodes in the community based on actual factors such as the communication probability and service degree. Reference [8] considered the reputation of vehicles in distributed Internet of Vehicles. The authors mainly considered familiarity, similarity, and timeliness to calculate the local reputation of vehicles. Finally, the local reputation and the historical reputation were combined to calculate the globe reputation of vehicles. Reference [9] proposed a resource allocation scheme for community-based fog computing based on reputation mechanism. A user first submits his/her task request to the community-based fog network, and then, the fog server makes a reliable resource allocation process based on multiple-layer communities and reputation calculation. Reference [10] proposed innovative approach that estimates the initial reputation values of newcomer services in web service recommendation systems through the use of the fog node’s (service provider) reputation and ANN model. The quality of services and reputation of previously published services are used to estimate the reputation values of newcomer services(ii)
Method 2: combine blockchain technology to achieve reliable data transmission [11]. Blockchain has unique features such as fault tolerance, security, and immutability, as well as the potential to provide decentralized databases and network operations [12]. Blockchain technology is used to realize the verification and traceability by building a decentralized ledger to record transactions between users [13]. Different from traditional digital ledgers, blockchain does not rely on a central authority [14]. In addition, the consistency of the ledgers between nodes is ensured by the consensus mechanism. Reference [15] proposed a user privacy protection scheme based on blockchain and federated learning (Blockchain-Enabled Federated Learning (FL-Block)), which proposed an autonomous learning process without any central trust agency to maintain the global model, and complete data processing and transmission through the blockchain Proof-of-Work mechanism and consensus mechanism [16]. In addition, the authors jointly considered the communication delay, consensus delay, and computation cost to optimize the block generation rate. Reference [17] studied the data security and user privacy issues in the vehicle fog networks. A lightweight anonymous authentication mechanism assisted by blockchain was proposed to realize the flexibility and anonymity of cross-center authentication, reduce the communication delay of data authentication, and build a lightweight network authentication mechanism. Reference [18] proposed a data sharing model based on blockchain. The data owner processes the original data generation according to the algorithm provided by the data requester. The data report is returned to the demander, and the data sharing platform supervises all the behaviors of the sharing parties and writes the entire sharing process into the blockchain, which not only satisfies the demander’s use of data but also avoids the risk of data leakage by the data holderHowever, due to the limited computing capability of FNs, when FNs process task offloading and blockchain verification at the same time, there could be a shortage of resources, resulting in the task offloading time increasing or the block generation and verification delay increasing, which affects the transaction’s recording time in the blockchain [19]. In order to optimize the allocation of computing capability and ensure the security of the network, we propose a task offloading and resource allocation algorithm in blockchain-enabled fog computing network (TR-BFCN) in this paper. The TR-BFCN algorithm is aimed at minimizing network utility, i.e., the total energy consumption of the FCN and the total delay of the blockchain network, by jointly optimizing the task offloading decision and resource allocation between two networks.


## 2. Network Modeling and Analysis

### 2.1. Network Model

A blockchain-based fog computing network (FCN) is shown in Figure1, which includes the device layer and the fog layer. The fog layer consists of geodistributed fog nodes (FNs) to provide computing, storage, and communication resources to nearby IoT devices (IDs). Besides, blockchain is deployed in the fog layer to verify and record transactions. The task offloading process is composed of three parts: master node election, resource pricing and offloading decision-making, and blockchain consensus process. The Authorized Service Center (ASC) is a trusted edge server, which is responsible for monitoring the FNs in the coverage area and the authentication process of network entities. The ASC will generate a unique public-private key pair and identification code for each entity, as well as the entity’s cancellation and other functions.Figure 1
Blockchain-enabled fog computing network scenario.Firstly, IDs should finish the registration and authentication through the ASC, then they could offload tasks to associated FNs for processing. FNs with higher reputation value will be elected as blockchain nodes, which will not only provide offloading services but also block consensus services.Secondly, IDs purchase computing resources from FNs to transfer the offloading tasks. Then, the task offloading decisions and resource allocation will be performed to minimize the network utility.Finally, the task offloading process in the FCN is regarded as a transaction record. The elected blockchain nodes will package transactions to generate blocks and perform a block consensus verification process. The verified blocks will be added to the blockchain network, to guarantee the network security and transactions traceability. The blockchain technology is used to preserve transactions among distributed nodes, which requires additional storage capacity on devices. Moreover, the consensus algorithms used to ensure the data security of devices also require additional computing and communication resources.


### 2.2. Communication Model

LetDk,Ck denotes the task offloading request sent by ID k, where Dk (bit) is the size of the task and Ck (cycle/bit) is the task calculation frequency, i.e., the task processing intensity. The total system bandwidth W is divided into N resource blocks (RB) with equal bandwidth, namely, B=W/N. To avoid interference between IDs during task offloading, each RB could be only assigned to one ID and one FN. The uplink transmission rate of ID k offloading task to FN m on RB n is given as
(1)rk,n,mt=Blog21+pk,n,mhk,n,m2σ2,where pk,n,m denotes the transmission power from ID k to FN m through RB n; hk,n,mt=lk,m⋅gk,n,m represents the channel gain value, including large-scale fading lk,m=csk,mdk,m−α and small-scale fading gk,n,m, where c represents the average channel gain at 1 km; sk,m is the logarithmic shadow fading variable with mean 0 and standard deviation σsh; dk,m denotes the distance from ID k to FN m; and α is the path loss index. gk,n,m is the independent and identically distributed complex Gaussian random variables with zero mean unit variance. σ2 represents additive white Gaussian noise.Therefore, the offloading delaytk,mtr from ID k to FN m by RB n is given as
(2)tk,mtr=∑m=1M∑n=1Nak,mxmkDkbn,mrk,n,m,where αk,m is the allocation index between ID k and FN m. And αk,m=1 indicates that ID k will offload tasks to FN m, while αk,m=0 represents that ID k will not offload tasks to FN m; bm,n is the allocation index between RB n and FN m. bm,n=1 indicates that ID k will offload tasks to FN m on RB n, and bm,n=0 represents that ID k will not offload tasks to FN m on RB n. Moreover, ID k could offload tasks to multiple FNs, and xmk indicates the task offloading proportional coefficient from ID k to FN m.Thus, the total transmission energy consumption of the fog computing network can be expressed as(3)Etrfog=∑k=1K∑n=1N∑m=1Mak,mpk,n,mxmkDkbm,nrk,n,mt.


### 2.3. Calculation Model

For the computation phase, we mainly consider the task computation delay and the computation energy consumption of FNm.The task computation delay of FNmtk,mser is given by
(4)tk,mser=xmkDkCkfk,mF,where Ck denotes the number of CPU cycles required to process the unit data size and fk,mF (cycle/s) represents the computation resources provided by FN m for the task offloaded from ID k.Thus, the computation energy consumption of FNm is given as
(5)Ek,mcal=κmfk,mF2xmkDkCk,where κm is the energy consumption coefficient of FN m.Therefore, the computation energy consumption of the FCN could be calculated by(6)Ecalfog=∑k=1K∑n=1N∑m=1Mak,mbm,nκmfk,mF2xmkDkCk.In summary, the total energy consumption of the FCN includes the transmission energy consumption and the computation energy consumption, which can be expressed as(7)Efog=∑k=1K∑n=1N∑m=1Mak,mpk,n,mxmkDkbn,mrk,n,m+bn,mκmfk,mF2xmkDkCk.


### 2.4. Blockchain Network Consensus Model

Based on blockchain technology, the FCN could effectively prevent malicious FNs from tampering or copying user data and improve the reliability of data transmission. In the blockchain network, transaction records will be processed in the following two steps:(1)
Block generation, where the transaction records are packaged to generate blocks through the master node(2)
Block consensus, where the master node will broadcast the new block to verification nodes to form a unified ledger information; then, all verification nodes compare the hash value and return the verification results to the master node through their private key signaturesIf the verification is passed, the master node will add the new block to the blockchain.Assume there are L blockchain nodes, the master nodemb could process transaction records, and the block generation delay is given as
(8)tmbblock=IbCbfmbB,where fmbB, mb, and Cb denote the computation frequency, the task processing intensity, and the processing data size of the master node mb, respectively. Assume that all verification nodes are honest and reliable; the consensus process is divided into two steps: block propagation and block verification. In the block propagation phase, the propagation rate from the master node mb to the verification node mb′ is
(9)Rmb,mb′=minmb′∈L,mb′≠mbRmb,mb′.Correspondingly, the block transmission delaytmb,mb′pro=Sb/Rmb,mb′, where Sb represents the block size.In the block verification phase, the verification node will confirm the content of the block broadcasted by the master node, with the verification delay(10)tmb,mb′ver=maxmb′≠mbδbfmb′B,where δb is the number of CPU cycles required for block verification and fmb′B represents the computation frequency to verify the block.Therefore, the total delay of the blockchain network is expressed as(11)tblock=∑mb=1LχmbIbCbfmbB+SbRmb,mb′+tmb,mb′ver,where χmb represents the master node indication parameter. If χmb=1, FN mb will be elected as the master node.


## 2.1. Network Model

A blockchain-based fog computing network (FCN) is shown in Figure1, which includes the device layer and the fog layer. The fog layer consists of geodistributed fog nodes (FNs) to provide computing, storage, and communication resources to nearby IoT devices (IDs). Besides, blockchain is deployed in the fog layer to verify and record transactions. The task offloading process is composed of three parts: master node election, resource pricing and offloading decision-making, and blockchain consensus process. The Authorized Service Center (ASC) is a trusted edge server, which is responsible for monitoring the FNs in the coverage area and the authentication process of network entities. The ASC will generate a unique public-private key pair and identification code for each entity, as well as the entity’s cancellation and other functions.Figure 1
Blockchain-enabled fog computing network scenario.Firstly, IDs should finish the registration and authentication through the ASC, then they could offload tasks to associated FNs for processing. FNs with higher reputation value will be elected as blockchain nodes, which will not only provide offloading services but also block consensus services.Secondly, IDs purchase computing resources from FNs to transfer the offloading tasks. Then, the task offloading decisions and resource allocation will be performed to minimize the network utility.Finally, the task offloading process in the FCN is regarded as a transaction record. The elected blockchain nodes will package transactions to generate blocks and perform a block consensus verification process. The verified blocks will be added to the blockchain network, to guarantee the network security and transactions traceability. The blockchain technology is used to preserve transactions among distributed nodes, which requires additional storage capacity on devices. Moreover, the consensus algorithms used to ensure the data security of devices also require additional computing and communication resources.


## 2.2. Communication Model

LetDk,Ck denotes the task offloading request sent by ID k, where Dk (bit) is the size of the task and Ck (cycle/bit) is the task calculation frequency, i.e., the task processing intensity. The total system bandwidth W is divided into N resource blocks (RB) with equal bandwidth, namely, B=W/N. To avoid interference between IDs during task offloading, each RB could be only assigned to one ID and one FN. The uplink transmission rate of ID k offloading task to FN m on RB n is given as
(1)rk,n,mt=Blog21+pk,n,mhk,n,m2σ2,where pk,n,m denotes the transmission power from ID k to FN m through RB n; hk,n,mt=lk,m⋅gk,n,m represents the channel gain value, including large-scale fading lk,m=csk,mdk,m−α and small-scale fading gk,n,m, where c represents the average channel gain at 1 km; sk,m is the logarithmic shadow fading variable with mean 0 and standard deviation σsh; dk,m denotes the distance from ID k to FN m; and α is the path loss index. gk,n,m is the independent and identically distributed complex Gaussian random variables with zero mean unit variance. σ2 represents additive white Gaussian noise.Therefore, the offloading delaytk,mtr from ID k to FN m by RB n is given as
(2)tk,mtr=∑m=1M∑n=1Nak,mxmkDkbn,mrk,n,m,where αk,m is the allocation index between ID k and FN m. And αk,m=1 indicates that ID k will offload tasks to FN m, while αk,m=0 represents that ID k will not offload tasks to FN m; bm,n is the allocation index between RB n and FN m. bm,n=1 indicates that ID k will offload tasks to FN m on RB n, and bm,n=0 represents that ID k will not offload tasks to FN m on RB n. Moreover, ID k could offload tasks to multiple FNs, and xmk indicates the task offloading proportional coefficient from ID k to FN m.Thus, the total transmission energy consumption of the fog computing network can be expressed as(3)Etrfog=∑k=1K∑n=1N∑m=1Mak,mpk,n,mxmkDkbm,nrk,n,mt.


## 2.3. Calculation Model

For the computation phase, we mainly consider the task computation delay and the computation energy consumption of FNm.The task computation delay of FNmtk,mser is given by
(4)tk,mser=xmkDkCkfk,mF,where Ck denotes the number of CPU cycles required to process the unit data size and fk,mF (cycle/s) represents the computation resources provided by FN m for the task offloaded from ID k.Thus, the computation energy consumption of FNm is given as
(5)Ek,mcal=κmfk,mF2xmkDkCk,where κm is the energy consumption coefficient of FN m.Therefore, the computation energy consumption of the FCN could be calculated by(6)Ecalfog=∑k=1K∑n=1N∑m=1Mak,mbm,nκmfk,mF2xmkDkCk.In summary, the total energy consumption of the FCN includes the transmission energy consumption and the computation energy consumption, which can be expressed as(7)Efog=∑k=1K∑n=1N∑m=1Mak,mpk,n,mxmkDkbn,mrk,n,m+bn,mκmfk,mF2xmkDkCk.


## 2.4. Blockchain Network Consensus Model

Based on blockchain technology, the FCN could effectively prevent malicious FNs from tampering or copying user data and improve the reliability of data transmission. In the blockchain network, transaction records will be processed in the following two steps:(1)
Block generation, where the transaction records are packaged to generate blocks through the master node(2)
Block consensus, where the master node will broadcast the new block to verification nodes to form a unified ledger information; then, all verification nodes compare the hash value and return the verification results to the master node through their private key signaturesIf the verification is passed, the master node will add the new block to the blockchain.Assume there are L blockchain nodes, the master nodemb could process transaction records, and the block generation delay is given as
(8)tmbblock=IbCbfmbB,where fmbB, mb, and Cb denote the computation frequency, the task processing intensity, and the processing data size of the master node mb, respectively. Assume that all verification nodes are honest and reliable; the consensus process is divided into two steps: block propagation and block verification. In the block propagation phase, the propagation rate from the master node mb to the verification node mb′ is
(9)Rmb,mb′=minmb′∈L,mb′≠mbRmb,mb′.Correspondingly, the block transmission delaytmb,mb′pro=Sb/Rmb,mb′, where Sb represents the block size.In the block verification phase, the verification node will confirm the content of the block broadcasted by the master node, with the verification delay(10)tmb,mb′ver=maxmb′≠mbδbfmb′B,where δb is the number of CPU cycles required for block verification and fmb′B represents the computation frequency to verify the block.Therefore, the total delay of the blockchain network is expressed as(11)tblock=∑mb=1LχmbIbCbfmbB+SbRmb,mb′+tmb,mb′ver,where χmb represents the master node indication parameter. If χmb=1, FN mb will be elected as the master node.


## 3. Optimization Problem Modeling

To minimize the network utility, namely, the sum of the total energy consumption of the FCN and the total delay of the blockchain network, the optimization problem could be represented as(12)minak,m,bm,n,xmk,fk,mF,χmb,fmbBw=α∑k=1K∑m=1M∑n=1Nak,mpk,n,mxmkDkbm,nrk,m,n+κmfk,mF2xmkDkCk+1−αβ∑mb=1LχmbIbCbfmbB+SbRmb,mb′+tmb,mb′ver,s.t.C1:∑k=1Kak,m≥1,∀m;∑m=1Mak,m≥1,∀k,C2:∑m=1Mbn,m≤1,∀n;∑n=1Nbn,m≥1,∀n,C3:∑m=1Mαk,mfk,mF≤∑m=1Mfk,m∗,∀k,C4:∑k=1Kαk,mfk,mF+fmbB≤Fmmax,∀m,C5:∑m=1M∑n=1Nak,mxmkDkbm,nrk,m,n+xmTDkCkfk,mF≤τkT,∀k,C6:∑m=1MxmkDk=Dk,∀k,C7:∑mb=1Lχmb=1,∀mb∈L,C8:ak,m,bm,n,xmk,α,β,χmb,κm∈0,1,∀k,m,n,mb,C9:fk,mF≥0,fmbB≥0,∀m,mb,where α is the proportion of the total energy consumption of the FCN in the optimization goal; C1 indicates that an ID can select multiple FNs to offload tasks; C2 indicates that an RB can only be allocated to one FN, but each FN can be allocated multiple RBs; C3 indicates that the computation resources allocated by the FCN cannot exceed the purchased computation resources; C4 indicates the computation resources constraint; C5 indicates that the total delay of the FCN cannot exceed the maximum tolerable delay of the task; C6 is the task size constraint; and C7 is the blockchain master node constraint, which ensures that there is only one master node in each processing cycle.


## 4. Task Offloading and Resource Allocation Scheme in Blockchain-Enabled Fog Computing Network

To optimize the computation resource allocation of the FCN and the blockchain network, in this paper, we propose the task offloading and resource allocation algorithm in blockchain-enabled fog computing network (TR-BFCN), which includes the Differentiated Resource Pricing Algorithm (DRPA), task offloading decision algorithm, and computation resource allocation algorithm.


### 4.1. Computing Resource Allocation Algorithm Based on Differentiated Pricing

Firstly, a two-stage Stackelberg game is considered to optimize the amount of resources to purchase and the associated price. In the Stackelberg game, the cost of IDk to purchase computation resource from FN m is expressed as
(13)ck,mD=pk,mfk,m,where pk,m denotes the price for ID k to purchase the computation resources from FN m, and fk,m represents the amount of computation resources purchased by ID k from FN m.The revenue function of IDk to offload tasks to FN m is defined as
(14)uk,m=ϖ×log1+fk,mCk,where ϖ is the benefit factor of ID k and Ck denotes the number of CPU cycles required to process the unit data size. The offloading revenue of IDs is related to the amount of offloading tasks fk,m/Ck. To maximize the benefits of ID k, the optimization problem is modeled as
(15)maxfk,mUk,mfk,m=∑m=1Muk,m−ck,mD,s.t.C1:fk,mmin≤fk,m≤fk,mmax,where fk,mmin and fk,mmax denote the minimum and the maximum amount of computation resources that could be purchased by ID k from FN m, respectively.The computation energy cost of offloading tasks from IDk to FN m is defined as
(16)ck,mF=κmfk,m2,where κm is the energy consumption coefficient of FN.Therefore, the utility function of FNm is defined as
(17)um=∑k=1Kpk,mfk,m−ck,mF,where pk,m is the price of computation resources provided by FN m for ID k.To maximize the utility of FNm, the price to purchase computation resources should be optimized. The dynamic price optimization problem is modeled as
(18)maxpk,mUk,mpk,m=∑k=1Kpk,mfk,m−ck,mF,s.t.C1:pk,m≥pk,mcost,where C1 indicates that the price is not lower than the cost of FN m. To ensure that the revenue of FN m is nonnegative, let um=0, and we have pk,mcost=κmfk,mmin.SinceUk,mfk,mis a convex function offk,m, the constraint is a linear function. The optimization problem is convex, which can be solved by the Lagrange multiplier method. The Lagrange function is defined as
(19)Lk,mDfk,m,λ,υ=Uk,mfk,m+∑m=1Mλmfk,m−fk,mmax+∑m=1Mυmfk,mmin−fk,m,where λ and υ are the Lagrange multipliers.The KKT (Karush-Kuhn-Tucker) condition is used to find the partial derivative of the Lagrange functionLk,mDfk,m,λ,υ with respect to the variable fk,m. The optimal solution fk,m∗ can be obtained by
(20)fk,m∗=ϖpk,m−λm+υmln2−Lk+,where X+=max0,X. The Lagrange multipliers λm and υm are updated by the following equations:
(21)λmn+1=λmn+1+θ1n∑m=1Mfk,m−fk,mmax+,(22)υmn+1=υmn+1+θ2n∑m=1Mfk,mmin−fk,m+,where n is the number of iterations and θ1n and θ2n are the step sizes.Substitutingfk,m∗ into (18) to find the second derivative, we can obtain
(23)∂2Uk,mpk,m∂pk,m2=4ϖLkκm−2ϖυm−λmln2Θ−3−6κmϖ2ln22Θ−4≤0,where Θ=pk,m+υm−λm; i.e., the revenue function of FN m is a convex function with respect to the variable pk,m, and its constraints are all linear functions. Therefore, the dynamic price optimization problem can be solved by the Lagrange multiplier method, and the Lagrange function is
(24)Lk,mFpk,m,φ=Uk,mpk,m+∑k=1Kφkpk,m−κmfk,mmin,where φk is the Lagrange multiplier.Similarly, the KKT condition could be used to find the partial derivative of its Lagrange functionLk,mFpk,m,φ with respect to the variable pk,m; the optimal solution pk,m∗ is given by
(25)pk,m∗=Θ+2κmϖΘln2−Lk+φkΘ2ln2ϖ+.The Lagrange multiplierφk is updated by
(26)φkn+1=φkn+1+θ3n∑k=1Kpk,m−κmfk,mmin+,where n is the number of iterations and θ3n is the step size.To prove that the optimal solution (fk,m∗, pk,m∗) is the Nash equilibrium solution, the following definitions and lemmas are proposed.Definition 1.
When the pricepk,m of FN m is fixed, the following condition is satisfied:
(27)Lk,mDfk,m,λ,υ=supLk,mDfk,m,λ,υ.Meanwhile, when the computing resourcesfk,m purchased by ID k from FN m are fixed, the following condition is satisfied:
(28)Lk,mFpk,m,φ=supLk,mFpk,m,φ.Then, (fk,m∗, pk,m∗) is the Nash equilibrium solution, which will be proven by the following three lemmas.Lemma 2.
When the quotation of FNm is fixed, the revenue function Lk,mDfk,m,λ,υ of ID k is maximized at fk,m∗.Proof.
Since the second-order partial derivative ofLk,mDfk,m,λ,υ is less than 0, Lk,mDfk,m,λ,υ is a convex function of variable fk,m. Therefore, Lk,mDfk,m,λ,υ achieves the maximum at fk,m∗. According to Definition 1, fk,m∗ is the Nash equilibrium solution.☐Lemma 3.
The optimal computing resourcefk,m∗ purchased by ID k from FN m decreases as the price pk,m increases.Proof.
Based on the first-order partial derivative of the optimal solutionfk,m∗, we could obtain
(29)∂fk,m∗∂pk,m=−ϖΘ2<0.
From (29), we know that fk,m∗ is a monotonically decreasing function of variable pk,m. When the quotation of FN m is too high, less IDs will purchase resources, resulting in decreasing of the revenue of FN m. Therefore, the optimal price of FNs could be obtained by setting the first partial derivative of Lk,mFpk,m,φ to 0 [20].☐Lemma 4.
When the optimal computing resourcefk,m∗ purchased by ID k from FNs is fixed, the revenue function Lk,mFpk,m,φ of FN m achieves the maximum at pk,m∗.Proof.
Since the second-order partial derivative ofLk,mFpk,m,φ with respect to variable pk,m is less than or equal to 0, Lk,mFpk,m,φ is a convex function with respect to variable pk,m. Therefore, Lk,mFpk,m,φ achieves the maximum at pk,m∗. According to Definition 1, pk,m∗ is the Nash equilibrium solution.☐Therefore, the optimal solution (fk,m∗, pk,m∗) is the Nash equilibrium solution of the Stackelberg game. The dynamic resource pricing algorithm (DRPA) is shown in Algorithm 1.Algorithm 1: Dynamic resource pricing algorithm (DRPA).
(0) Initializefk,m, pk,m, ω, tmax, λ,υ,φ, ε1, and ε2(1) Whilet≤tmax(2)  Fork=1,⋯,K(3)   Form=1,⋯,M(4)    Updatepk,m∗t according to (25)(5)    Updatefk,m∗t according to (20)(6)    Ifpk,m∗t−pk,mt−1≤ε1 && fk,m∗t−fk,mt−1≤ε2(7)     Output optimal pricepk,m∗t and computation resources fk,m∗t(8)    End if(9)    Else(10)      The algorithm does not converge, lett=t+1, fk,mt−1=fk,m∗t(11)      Update Lagrange multiplierλ,υ,φ according to (21), (22), and (26)(12)      Update the number of iterationst=t+1 and return to step 1(13)    End else(14)   End for(15)  End for(16) End while


### 4.2. Task Offloading and Transmission Resource Allocation Algorithm

To further minimize the utility of the FCN, the task offloading decisions and transmission resource allocation algorithm is proposed. Since the optimization problem is nonconvex, we decompose it into two subproblems and solve them individually to minimize the total energy consumption of the FCN.Firstly, the original optimization problem could be transformed to(30)minak,m,bm,n,xmk,fk,mFα∑k=1K∑m=1M∑n=1Nak,mpk,n,mxmkDkbm,nrk,m,n+κmfk,mF2xmkDkCk,s.t.C1~C6,C8′:ak,m,bm,n,xmk,κm∈0,1,∀k,m,n,C9′:fk,mF≥0,∀m.Based on the optimal task offloading algorithm proposed in [21], the task offloading decisions and transmission resource allocation results in this scenario can be obtained.


### 4.3. Computing Resource Allocation Algorithm

The task offloading decisions and transmission resource allocation could be obtained through the above algorithm. In addition, the alternate direction method is used to optimize the computation resource allocation in the FCN and blockchain network.First of all, with the fixed computation resourcefmbB of the blockchain network, we could solve the computation resource allocation problem in the FCN. Due to the coupling relationship between variables in the optimization problem, we assume that when ID k offloads tasks to multiple FNs simultaneously, the offloading proportional xmk from ID k to FN m is dependent on the amount of computation resources purchased from FN m, which is expressed as
(31)xmk=fk,m∗∑m=1Mfk,m∗.Based on the Lagrange multiplier method, the optimal solutionfk,mF can be obtained. The constraint C5 is rewritten as
(32)fk,mF≥xmTDkCkτkT−xmkDkpk,m,n/bm,nrk,m,n.Then, the Lagrange function is given by(33)LFfk,mF,π1,π2,π3=α∑k=1K∑m=1M∑n=1Nκmfk,mF2xmkDkCk+π1∑m=1M∑n=1Nfk,mF−xmTDkCkτkT−xmkDkpk,m,n/ak,mbm,nrk,m,n+π2Fmmax−fmbB−∑k=1Kak,mfk,mF+π3∑m=1Mfk,m∗−∑m=1Mαk,mfk,mF,where π1, π2, and π3 are the Lagrange multipliers. Thus, the optimal solution fk,mF of the optimization problem can be obtained:
(34)fk,mF=ak,mπ2+ak,mπ3−π12ακmxmkDkCk.The Lagrange multiplier update are updated by(35)π1n+1=π1n+1+θ2n∑m=1M∑n=1Nfk,mF−xmTDkCkτkT−xmkDkpk,m,n/ak,mbm,nrk,m,n+,π2n+1=π2n+1+θ2nFmmax−fmbB−∑k=1Kak,mfk,mF+,π3n+1=π3n+1+θ2n∑m=1Mfk,m∗−αk,mfk,mF+,where θ2n is the step size.Secondly, with the obtained computation resourcefk,mF of the FCN, the blockchain node selection and computation resource allocation problem could be expressed as
(36)minχmb,fmbB1−αβ∑mb=1LχmbIbCbfmbB+SbRmb,mb′+tmb,mb′ver,s.t.C4′:fmbB≤Fmmax−∑k=1Kfk,mF,∀mb,m′,C8″~C9″.Based on the reputation model proposed in [22], an odd number of nodes with high reputation will be selected as blockchain nodes to participate in the blockchain consensus process. Therefore, the computing resource allocation problem in the blockchain network is transformed into
(37)minfmbB1−αβIbCbfmbB+SbRmb,mb′+tm,m′ver,s.t.C4′:fmbB≤Fmmax−∑k=1Kfk,mF,∀mb,C9′:fmbB≥0,∀mb.The optimization problem is a linearly decreasing function; whenfmbB takes the maximum value, the objective function obtains the minimum value, and we have
(38)fmbB=Fmmax−∑k=1Kfk,mF.Finally, based on the alternating direction method,fk,mF and fmbB could reach the convergence, and the associated network utility could be obtained. The computation resource allocation algorithm is summarized in Algorithm 2.Algorithm 2: Computation resource allocation algorithm.
(0) Initializeχmb, fk,mF, fmbB, number of iterations k, and maximum tolerance threshold ε(1) Updatet=t+1(2) Whilewt−wt−1≥ε do(3)  Obtainpk,m∗t and fk,m∗t according to the algorithm DRPA(4)  Obtainak,mt and bn,mt according to the algorithm COTRA(5)  Obtainfk,mF and fmbB according to (34) and (38)(6) End whileThe computational complexity for one round of pricing for FNs of DRPA isOM. Thus, the total computational complexity of DRPA is OMK, where K denotes the number of IDs. Considering that the loop number of DRPA is t≤tmax, thus, the total computational complexity of DRPA is On=On2logn.


## 4.1. Computing Resource Allocation Algorithm Based on Differentiated Pricing

Firstly, a two-stage Stackelberg game is considered to optimize the amount of resources to purchase and the associated price. In the Stackelberg game, the cost of IDk to purchase computation resource from FN m is expressed as
(13)ck,mD=pk,mfk,m,where pk,m denotes the price for ID k to purchase the computation resources from FN m, and fk,m represents the amount of computation resources purchased by ID k from FN m.The revenue function of IDk to offload tasks to FN m is defined as
(14)uk,m=ϖ×log1+fk,mCk,where ϖ is the benefit factor of ID k and Ck denotes the number of CPU cycles required to process the unit data size. The offloading revenue of IDs is related to the amount of offloading tasks fk,m/Ck. To maximize the benefits of ID k, the optimization problem is modeled as
(15)maxfk,mUk,mfk,m=∑m=1Muk,m−ck,mD,s.t.C1:fk,mmin≤fk,m≤fk,mmax,where fk,mmin and fk,mmax denote the minimum and the maximum amount of computation resources that could be purchased by ID k from FN m, respectively.The computation energy cost of offloading tasks from IDk to FN m is defined as
(16)ck,mF=κmfk,m2,where κm is the energy consumption coefficient of FN.Therefore, the utility function of FNm is defined as
(17)um=∑k=1Kpk,mfk,m−ck,mF,where pk,m is the price of computation resources provided by FN m for ID k.To maximize the utility of FNm, the price to purchase computation resources should be optimized. The dynamic price optimization problem is modeled as
(18)maxpk,mUk,mpk,m=∑k=1Kpk,mfk,m−ck,mF,s.t.C1:pk,m≥pk,mcost,where C1 indicates that the price is not lower than the cost of FN m. To ensure that the revenue of FN m is nonnegative, let um=0, and we have pk,mcost=κmfk,mmin.SinceUk,mfk,mis a convex function offk,m, the constraint is a linear function. The optimization problem is convex, which can be solved by the Lagrange multiplier method. The Lagrange function is defined as
(19)Lk,mDfk,m,λ,υ=Uk,mfk,m+∑m=1Mλmfk,m−fk,mmax+∑m=1Mυmfk,mmin−fk,m,where λ and υ are the Lagrange multipliers.The KKT (Karush-Kuhn-Tucker) condition is used to find the partial derivative of the Lagrange functionLk,mDfk,m,λ,υ with respect to the variable fk,m. The optimal solution fk,m∗ can be obtained by
(20)fk,m∗=ϖpk,m−λm+υmln2−Lk+,where X+=max0,X. The Lagrange multipliers λm and υm are updated by the following equations:
(21)λmn+1=λmn+1+θ1n∑m=1Mfk,m−fk,mmax+,(22)υmn+1=υmn+1+θ2n∑m=1Mfk,mmin−fk,m+,where n is the number of iterations and θ1n and θ2n are the step sizes.Substitutingfk,m∗ into (18) to find the second derivative, we can obtain
(23)∂2Uk,mpk,m∂pk,m2=4ϖLkκm−2ϖυm−λmln2Θ−3−6κmϖ2ln22Θ−4≤0,where Θ=pk,m+υm−λm; i.e., the revenue function of FN m is a convex function with respect to the variable pk,m, and its constraints are all linear functions. Therefore, the dynamic price optimization problem can be solved by the Lagrange multiplier method, and the Lagrange function is
(24)Lk,mFpk,m,φ=Uk,mpk,m+∑k=1Kφkpk,m−κmfk,mmin,where φk is the Lagrange multiplier.Similarly, the KKT condition could be used to find the partial derivative of its Lagrange functionLk,mFpk,m,φ with respect to the variable pk,m; the optimal solution pk,m∗ is given by
(25)pk,m∗=Θ+2κmϖΘln2−Lk+φkΘ2ln2ϖ+.The Lagrange multiplierφk is updated by
(26)φkn+1=φkn+1+θ3n∑k=1Kpk,m−κmfk,mmin+,where n is the number of iterations and θ3n is the step size.To prove that the optimal solution (fk,m∗, pk,m∗) is the Nash equilibrium solution, the following definitions and lemmas are proposed.Definition 1.
When the pricepk,m of FN m is fixed, the following condition is satisfied:
(27)Lk,mDfk,m,λ,υ=supLk,mDfk,m,λ,υ.Meanwhile, when the computing resourcesfk,m purchased by ID k from FN m are fixed, the following condition is satisfied:
(28)Lk,mFpk,m,φ=supLk,mFpk,m,φ.Then, (fk,m∗, pk,m∗) is the Nash equilibrium solution, which will be proven by the following three lemmas.Lemma 2.
When the quotation of FNm is fixed, the revenue function Lk,mDfk,m,λ,υ of ID k is maximized at fk,m∗.Proof.
Since the second-order partial derivative ofLk,mDfk,m,λ,υ is less than 0, Lk,mDfk,m,λ,υ is a convex function of variable fk,m. Therefore, Lk,mDfk,m,λ,υ achieves the maximum at fk,m∗. According to Definition 1, fk,m∗ is the Nash equilibrium solution.☐Lemma 3.
The optimal computing resourcefk,m∗ purchased by ID k from FN m decreases as the price pk,m increases.Proof.
Based on the first-order partial derivative of the optimal solutionfk,m∗, we could obtain
(29)∂fk,m∗∂pk,m=−ϖΘ2<0.
From (29), we know that fk,m∗ is a monotonically decreasing function of variable pk,m. When the quotation of FN m is too high, less IDs will purchase resources, resulting in decreasing of the revenue of FN m. Therefore, the optimal price of FNs could be obtained by setting the first partial derivative of Lk,mFpk,m,φ to 0 [20].☐Lemma 4.
When the optimal computing resourcefk,m∗ purchased by ID k from FNs is fixed, the revenue function Lk,mFpk,m,φ of FN m achieves the maximum at pk,m∗.Proof.
Since the second-order partial derivative ofLk,mFpk,m,φ with respect to variable pk,m is less than or equal to 0, Lk,mFpk,m,φ is a convex function with respect to variable pk,m. Therefore, Lk,mFpk,m,φ achieves the maximum at pk,m∗. According to Definition 1, pk,m∗ is the Nash equilibrium solution.☐Therefore, the optimal solution (fk,m∗, pk,m∗) is the Nash equilibrium solution of the Stackelberg game. The dynamic resource pricing algorithm (DRPA) is shown in Algorithm 1.Algorithm 1: Dynamic resource pricing algorithm (DRPA).
(0) Initializefk,m, pk,m, ω, tmax, λ,υ,φ, ε1, and ε2(1) Whilet≤tmax(2)  Fork=1,⋯,K(3)   Form=1,⋯,M(4)    Updatepk,m∗t according to (25)(5)    Updatefk,m∗t according to (20)(6)    Ifpk,m∗t−pk,mt−1≤ε1 && fk,m∗t−fk,mt−1≤ε2(7)     Output optimal pricepk,m∗t and computation resources fk,m∗t(8)    End if(9)    Else(10)      The algorithm does not converge, lett=t+1, fk,mt−1=fk,m∗t(11)      Update Lagrange multiplierλ,υ,φ according to (21), (22), and (26)(12)      Update the number of iterationst=t+1 and return to step 1(13)    End else(14)   End for(15)  End for(16) End while


## 4.2. Task Offloading and Transmission Resource Allocation Algorithm

To further minimize the utility of the FCN, the task offloading decisions and transmission resource allocation algorithm is proposed. Since the optimization problem is nonconvex, we decompose it into two subproblems and solve them individually to minimize the total energy consumption of the FCN.Firstly, the original optimization problem could be transformed to(30)minak,m,bm,n,xmk,fk,mFα∑k=1K∑m=1M∑n=1Nak,mpk,n,mxmkDkbm,nrk,m,n+κmfk,mF2xmkDkCk,s.t.C1~C6,C8′:ak,m,bm,n,xmk,κm∈0,1,∀k,m,n,C9′:fk,mF≥0,∀m.Based on the optimal task offloading algorithm proposed in [21], the task offloading decisions and transmission resource allocation results in this scenario can be obtained.


## 4.3. Computing Resource Allocation Algorithm

The task offloading decisions and transmission resource allocation could be obtained through the above algorithm. In addition, the alternate direction method is used to optimize the computation resource allocation in the FCN and blockchain network.First of all, with the fixed computation resourcefmbB of the blockchain network, we could solve the computation resource allocation problem in the FCN. Due to the coupling relationship between variables in the optimization problem, we assume that when ID k offloads tasks to multiple FNs simultaneously, the offloading proportional xmk from ID k to FN m is dependent on the amount of computation resources purchased from FN m, which is expressed as
(31)xmk=fk,m∗∑m=1Mfk,m∗.Based on the Lagrange multiplier method, the optimal solutionfk,mF can be obtained. The constraint C5 is rewritten as
(32)fk,mF≥xmTDkCkτkT−xmkDkpk,m,n/bm,nrk,m,n.Then, the Lagrange function is given by(33)LFfk,mF,π1,π2,π3=α∑k=1K∑m=1M∑n=1Nκmfk,mF2xmkDkCk+π1∑m=1M∑n=1Nfk,mF−xmTDkCkτkT−xmkDkpk,m,n/ak,mbm,nrk,m,n+π2Fmmax−fmbB−∑k=1Kak,mfk,mF+π3∑m=1Mfk,m∗−∑m=1Mαk,mfk,mF,where π1, π2, and π3 are the Lagrange multipliers. Thus, the optimal solution fk,mF of the optimization problem can be obtained:
(34)fk,mF=ak,mπ2+ak,mπ3−π12ακmxmkDkCk.The Lagrange multiplier update are updated by(35)π1n+1=π1n+1+θ2n∑m=1M∑n=1Nfk,mF−xmTDkCkτkT−xmkDkpk,m,n/ak,mbm,nrk,m,n+,π2n+1=π2n+1+θ2nFmmax−fmbB−∑k=1Kak,mfk,mF+,π3n+1=π3n+1+θ2n∑m=1Mfk,m∗−αk,mfk,mF+,where θ2n is the step size.Secondly, with the obtained computation resourcefk,mF of the FCN, the blockchain node selection and computation resource allocation problem could be expressed as
(36)minχmb,fmbB1−αβ∑mb=1LχmbIbCbfmbB+SbRmb,mb′+tmb,mb′ver,s.t.C4′:fmbB≤Fmmax−∑k=1Kfk,mF,∀mb,m′,C8″~C9″.Based on the reputation model proposed in [22], an odd number of nodes with high reputation will be selected as blockchain nodes to participate in the blockchain consensus process. Therefore, the computing resource allocation problem in the blockchain network is transformed into
(37)minfmbB1−αβIbCbfmbB+SbRmb,mb′+tm,m′ver,s.t.C4′:fmbB≤Fmmax−∑k=1Kfk,mF,∀mb,C9′:fmbB≥0,∀mb.The optimization problem is a linearly decreasing function; whenfmbB takes the maximum value, the objective function obtains the minimum value, and we have
(38)fmbB=Fmmax−∑k=1Kfk,mF.Finally, based on the alternating direction method,fk,mF and fmbB could reach the convergence, and the associated network utility could be obtained. The computation resource allocation algorithm is summarized in Algorithm 2.Algorithm 2: Computation resource allocation algorithm.
(0) Initializeχmb, fk,mF, fmbB, number of iterations k, and maximum tolerance threshold ε(1) Updatet=t+1(2) Whilewt−wt−1≥ε do(3)  Obtainpk,m∗t and fk,m∗t according to the algorithm DRPA(4)  Obtainak,mt and bn,mt according to the algorithm COTRA(5)  Obtainfk,mF and fmbB according to (34) and (38)(6) End whileThe computational complexity for one round of pricing for FNs of DRPA isOM. Thus, the total computational complexity of DRPA is OMK, where K denotes the number of IDs. Considering that the loop number of DRPA is t≤tmax, thus, the total computational complexity of DRPA is On=On2logn.


## 5. Simulation Results and Analysis

To verify the effectiveness of task offloading and resource allocation algorithm in the blockchain-enabled fog network (TR-BFCN), the following two algorithms are used for comparison.Random resource allocation algorithm (RAA). This algorithm uses different resource pricing to ensure the network revenue of IDs and FNs and uses random offloading decisions and transmission resource allocation.Unified price algorithm (UPA) [23]. This algorithm adopts a unified resource pricing, i.e., each ID purchases the same computing resource from different FNs, and adopts the optimal offloading decision and transmission resource allocation.Figures2 and 3 show the computation resources purchased by different IDs and the associated prices with K=3, M=10, and N=16. For ID 1, the task processing intensity is 200 cycles/bit; for ID 2, it is 300 cycles/bit; and for ID 3, it is 400 cycles/bit. As shown in the figure, with the number of tasks increasing, the computation resources purchased by IDs increase, and the amount of computation resources purchased by different IDs from different FNs is also different. ID 1 has a lower task processing intensity and purchases fewer computation resources with a higher price, whereas ID 3 has a higher task processing intensity and purchases more computation resources with a lower price.Figures 2
Purchased resources of IDs for different task processing intensities.Figures 3
The price of resources purchased by ID under different task processing intensities.Figures4 and 5, respectively, show the convergence of the purchased computation resources and the associated prices. The DRPA algorithm converges when the number of iterations reaches 10. It can be seen that FN 1 has the smallest energy consumption factor κm and the lowest cost, and FN 5 has the largest energy consumption factor κm and the highest cost. As κm increases, the computing resources that can be purchased decrease, and resource quotations continue to increase correspondingly.Figure 4
Convergence of purchased computing resources.Figures 5
Convergence of price versus the purchased computation resources.Figure6 shows the network utility versus the number of FNs. It can be seen that the network utility is a decrease function of the number of FNs, which converges when the number of iterations is greater than 12. With the increase of the number of FNs, IDs could purchase computation resources from more available FNs; thus, the total network delay and the network utility could be reduced. Moreover, as the number of FNs increases, more FNs can be selected as blockchain nodes, and the network utility will be further minimized.Figure 6
Network utility versus the number of FNs.Figure7 shows the network utility versus the number of IDs. The task transmission delay and computation delay increase when the number of offloading tasks increases, resulting in the increase of the network utility. Compared with other algorithms, the proposed TR-BFCN algorithm has the lowest network utility. For algorithm RAA, ID may offload tasks to FNs with poor channel conditions, resulting in high transmission delay and high network utility. The simulation results show that the proposed DRPA algorithm could make each FN provide different computation resources for each ID according to the task processing intensity, which can effectively reduce the network utility.Figure 7
Network utility versus the number of IDs.Figure8 shows the relationship between the network utility and the task processing intensity with three algorithms. The increase in task processing intensity leads to the increase in network calculation delay; thus, the total energy consumption of the network also increases. The ID in the algorithm RAA may offload tasks to the FN with poor channel conditions, which could increase the transmission delay. In the UPA algorithm, each ID purchases the same amount of computing resources from each FN. For FNs with rich computing resources or higher processing costs, the ID has not obtained the optimal amount of computing resources to maximize its own revenue, resulting in higher network utility.Figure 8
Network utility versus task processing intensity for different algorithms.Figure9 shows the relationship between network utility and the number of FNs with different algorithms. With the number of FNs increasing, the available computing resources also increase. Therefore, the available FNs for each ID to offload tasks are increasing, and IDs could select the FN with better processing capability for task offloading, resulting in the decrease of the total network delay and the total energy consumption, as well as the network utility.Figure 9
Network utility versus the number of FNs.


## 6. Conclusions

In this paper, we proposed a task offloading and resource allocation scheme in the blockchain-enabled FCN to minimize the network utility by optimizing the resource pricing, task offloading decisions, and resource allocation. The FCN was responsible for the task offloading and the blockchain network was responsible for the security in the data communication process. Firstly, we proposed a task offloading model in the blockchain-enabled FCN; secondly, based on the two-stage Stackelberg model, a dynamic resource pricing algorithm was proposed to ensure the fairness of transactions. Finally, we verified the feasibility and effectiveness of the proposed algorithm by simulation results.



---

*Source: 7518534-2021-12-20.xml*