Mobile edge computing (MEC) is regarded as a promising technology, which can bridge the gap between the demands of applications and the restricted capabilities of mobile terminals (MTs)[1-2]. MEC servers are deployed at the base stations (BSs) in close proximity to mobile subscribers to execute latency-sensitive services, thereby extending the computing, storage and data processing capabilities of MTs.
Little existing literature focuses on resource allocation in MEC systems. The non-cooperative matrix game was formulated in Ref.[3] to solve the resource sharing problem among the cloudlets. Meneguette et al.[4] proposed an effective protocol based on vehicle-to-vehicle (V2V) communication. Nevertheless, due to the search for super nodes in the algorithm, additional time overhead was needed. In Ref.[5], the authors modeled the uplink data transmission of the vehicular network into an equilibrium program with the equilibrium constraints problem. The Bayesian alliance game and automatic learning machine[6]were applied to deal with a large amount of spatio-temporal information. Based on the Markov decision process (MDP), a motion prediction algorithm for dynamic resource allocation was investigated in Ref.[7], which greatly reduced the offloading time and energy consumption. In Ref.[8], a resource allocation algorithm based on the semi-Markov decision process (SMDP) was proposed, which considered the heterogeneous vehicular network and the impact of road side units to maximize long-term utility.
A joint cloud and wireless resource allocation based on evolutionary game (JRAEG) [9] was proposed to solve the service selection problem in heterogeneous networks. A power-delay tradeoff algorithm was proposed in Ref.[10], which applied a joint task offloading and proactive caching method to minimize computing latency. In Ref.[11], users with different computation capabilities shared a single edge server. A convex optimization problem was formulated to minimize the energy consumption. An iterative algorithm[12] was proposed to solve a non-convex optimization problem in the multicell MEC scenario. In Ref.[13], an energy-efficient cooperative computation method was proposed, in which the computational applications can be partitioned into several tasks to be executed in peer nodes.
Although the literature above provided effective approaches to solve the resource allocation problem for the MEC system, there are still some disadvantages in these approaches. The game theory requires multiple iterations between the MTs and BSs, which brings the problem of low convergence speed and large latency. The Markov decision process increases the information interaction between the terminals and the MEC servers, which brings great delay. The auction theory is a well-researched field in economics that has been applied in resource management with the advantages of high efficiency and low computation complexity[14-17]. Therefore, we propose a wireless and cloud resource allocation algorithm based on the combinational parallel auction for MEC systems.
We propose a joint resource allocation algorithm based on parallel auction (JRAPA), including bidding submission, winner determination and pricing stages to maximize the utilities of the service providers (SPs) and satisfy the delay requirements of MTs at the same time. The MTs take available resources from SPs and distance factors into account to decide the bidding priority. A resource constrained utility ranking (RCUR) algorithm is put forward to match the SPs and MTs at the winner determination stage. Moreover, the wireless resource auction and cloud resource auction are processed in parallel, which accelerates the convergence speed of the auction process.
1 System Model
The system model studied in this paper is shown in Fig.1, which includes MTs, BSs, MEC servers, the core network (CN) and central cloud (CC).
Fig.1 An example of MEC system
1.1 Network model
The CC is composed of massive servers, which is the central computational service provider of the whole system. MEC servers are applied to supplement the CC, so that applications can be processed close to the MTs. The MEC servers and BSs are connected through reliable optical fibers, and they are connected to the CN through a wide area network (WAN). In addition, MTs are connected to the BSs through the LTE/5G wireless network. The wired connection between MEC servers and BSs allows the MEC server to provide auxiliary functions for offloading decision making and resources allocation, which guarantees the low delay and high reliability requirements of the applications. Without loss of generality, we assume that each BS only connects with one MEC server.
1.2 Communication model
It is assumed that there are J MTs, denoted as J={1，2,...,J}. The number of BSs/MEC servers is N, which is expressed as N={1,2,...,N}. Orthogonal sub-channels are allocated to MTs connected to each BS, which indicates that there are no interfaces among MTs. The channel between each BS is composed of a fixed path-loss, a slowly varying lognormal shadowing and rayleigh fast fading. The transmission power of MT j is denoted by pj. The uplink transmission rate of MT j connected to BS i is expressed as
(1)
where Bij is the bandwidth allocated to MT j, and gij refers to the channel gain between MT j and BS i. 
is defined as the power of additive Gauss white noise (AWGN).
1.3 Computation model and problem formulation
1.3.1 Computation model of MTs
When a MT needs to offload a task, it should pay the corresponding remuneration to encourage SPs to provide wireless and cloud resources. The utility function of MT j is
(2)
where mij is a two-value variable to show the matching relationship between SP i and MT j, and mij∈ {0,1}. t0,j is the time for MT j to execute a task locally. 
is the bidding price of MT j for a unit wireless resource, and 
is the bidding price for a unit computation resource. sj refers to the number of CPU instructions that MT j requests, and bj is the bandwidth required to upload the task. 
is the delay constrain of MT j. The total delay between MT j and SP i is denoted as
(3)
where Bij and fij are the wireless and cloud resources that MT j required. The matching time between MT j and SP i is denoted as 
1.3.2 Utility function of BSs
We need to consider how to maximize the revenue of BSs.The optimization problem is
(4)
where 
represents the cost of BS i for the allocating unit wireless resource, and 
is the available wireless resource of BS i.
1.3.3 Utility function of MEC servers
It is necessary to consider how to maximize the revenue of MEC servers. Similarly, the optimization problem is
(5)
where 
represents the cost of MEC server i for allocating unit cloud resource, and 
is the available cloud resource of MEC server i.
2 Joint Resource Allocation Algorithm based on Parallel Auction
The resource allocation in the MEC system needs to meet the real-time requirements of tasks. In this section, we propose a parallel auction algorithm to realize the joint allocation of the wireless and cloud resources, aiming at maximizing the utilities of SPs and meeting the delay requirements of MTs at the same time.
2.1 Auction model
The basic auction model of JRAPA is illustrated in Fig.2. MTs are resource buyers, while BSs and MEC servers are resource sellers. We regard BSs and MEC servers as the auctioneers of wireless and cloud resource auction, respectively. Hence, no additional charge is required. The bidding and pricing information of both buyers and sellers is private.
Fig.2 The auction model
As shown in Fig.3, due to the independence of wireless and cloud request channels, the auction of wireless and cloud resources can be processed in parallel. One MT transmits the wireless and cloud resource request while signaling to the BS at the same time. After receiving the two signals, the BS will conduct the wireless resource auction, and the cloud resource request signaling is forwarded to the MEC server to conduct the cloud resource request auction. Parallel auction of wireless and computation resources can achieve fast matching of sellers and buyers, which can meet the low latency requirement of the system.
Fig.3 The description of parallel auction
2.2 Parallel auction algorithm description
An auction mechanism with clear rules will be adopted to prevent dishonest transactions between buyers and sellers. One trade in the parallel auction is successful when both the wireless and cloud resources required by one MT are satisfied. The auction process can be divided into three stages: the bidding submission stage, winner determination stage and pricing stage.
2.2.1 Bidding submission
Each MEC server and each BS broadcast its available cloud resource and wireless resource 
respectively. When receiving the resource information, MT j prioritizes the SPs according to priority factor oi,j, which takes the available resources of the BS and MEC server , the distance dij between SP i and MT j into account.
(6)
where α,β,γ are the available wireless resource factor, available cloud resource factor and distance factor, respectively, and α+β+γ=1.
The priority vector is 
In each round, MT j submits its bidding vector 
where 
and 
are the unit bidding price for wireless and cloud resources of MT j, respectively. When the MT and SP match successfully, the MT stops bidding for wireless and cloud resources.
2.2.2 Winner determination
We define a match matrix M={mij}N×J to describe the relationship between MTs and SPs, where mij∈{0,1}. mij=1 means that SP i and MT j matches, while mij=0 refers to that MT j fails to match SP i. Also, we assume that 
which indicates an MT can only choose service from at most one SP.
We propose a resource constrained utility ranking (RCUR) algorithm to match the MTs and SPs. After receiving the bidding vectors, BS i and MEC server i first calculate the utility vector, respectively. The descending utility vector is obtained as UB(i)={UB(i,1),...,UB(i,Ki)} and UM(i)={UM(i,1),...,UM(i,Ki)}, where Ki represents the number of MTs bidding for BS and MEC server i. BS and MEC server i choose the MT whose utility ranks top in 
and 
respectively, as the winner, and update 
as
(7)
(8)
A winner will not take part in the auction in the next round, and its utility is removed from the utility vectors. The above process will be repeated until 
or 
holds, where φB and φM are the predetermined wireless and cloud resource threshold, respectively. It is noted that if one auction (for example, the auction at the MEC servers) is successful and another auction failed for the same MT, the MT fails to obtain the required resources.
The losers should improve their bidding strategies in the next round. The bidding price update by the functions 
and 
where 
are steps of the price adjustment for unit wireless and cloud resources, respectively.
2.2.3 Pricing stage
An auction should be constructed while the price paid by the buyer is independent of its own bids[16]. At the pricing stage, we adopt the sealed second-price rule, where each winning MT pays the second-high bidding price in the winner set.
Assume that the winners of SP i are expressed as 
where wi is the number of winners. Taking the unit wireless resource pricing of the BS as an example, we assume that the bidding price of winners is ranked as 
where 
According to the second-price rule, the payment for each winner is
(9)
where 
is the payment of the winner whose bidding price is 
and it is assumed that 
By calculating the pricing of the winner of each BS, the wireless resource pricing matrix 
is determined.
Similarly, the MEC servers will also obtain the pricing matrix 
according to the sealed second-price rule.
(10)
where 
is the payment of the winner whose bidding price is 
and it is assumed that 
2.3 Proposed algorithm description
The proposed JRAPA algorithm is described in Algorithm 1, which describes the bidding submission, winner determination and pricing stages of multiple auction rounds to decide the match matrix and pricing matrix. rmax is the maximum auction rounds in the algorithm.
The RCUR algorithm in the winner determination stage is illustrated in Algorithm 2, in which the utilities of SPs are ranked in a descending order to determine the winners, and available wireless and cloud resources are updated with the iterations.
In Algorithm 2, U(i,j) is the utility of the BS or MEC server, which depends on the requested resource. 
refers to the set of candidate MTs, and Ki is the number of MTs in 
φB,φM are the resource thresholds of BSs and MEC servers, respectively.
Algorithm 1 JRAPA algorithm
Output: M, P.
for each particle r=1: rmax do
Bidding submission
Each MT in J calculates oi,j according to Eq.(6).
Sort oi,j in a descending order, and 
is obtained.
MT bids to the BS and MEC server according to the first element in 
Winner determination
for each particle i = 1: N do
BS and MEC server i utilize Algorithm 2 to decide winners. 6:
end for
for j∈J do
end for
end for
Pricing stage
Each MT pays according to (9) and (10).
Algorithm 2 RCUR algorithm
for each particle i=1:Ki do
Calculate the utility for each MT in 
end for
Sort the utility U(i,j) in a descending order. Ui=[Ui(i,1),Ui(i,2),...,Ui(i,Ki)].
for each particle i=1:Ki do
end for
2.4 Properties of JRAPA algorithm
Definition 1 A feasible auction mechanism should satisfy the following properties:
• Computational efficiency. The auction outcome should be completed with a polynomial time complexity.
• Individual rationality. The utility of the buyers and sellers should not be less than zero, which means that no winning buyer is charged more than its bidding, and no winning seller is paid less than its cost.
• Budget balance. The gain of the auctioneer is defined as 
which is equal to the price paid by the buyers subtracting the payment to the sellers. The gain of the auctioneer should be no less than zero.
Lemma 1 The JRAPA is computationally efficient.
Proof In Algorithm 1, in each single-round auction, sorting the priority factors takes O(NJ log(NJ)) time at the bidding submission stage. According to Algorithm 2, at the winner determination stage, there are at most J MTs for each SP. As a consequence, the time complexity of sorting the utility vector is O(NJ log(J)), and the while-loop takes at most O(NJ) time. For bidding strategy adjustment, there are at most J MTs in set J. Hence, it has the time complexity of O(J). Since the auction process will be conducted rmax times, the overall time complexity of Algorithm 1 is O(rmaxNJlog(NJ)).
In other words, JRAPA will converge to a final resource allocation and pricing results in a polynomial time with respect to N, J and rmax, and JRAPA is computationally efficient.
Lemma 2 The JRAPA is individually rational.
Proof On the one hand, for winning buyers, we adopt the sealed second-price rule at the pricing stage, so the payment to sellers is less than the bidding of the winning MT. For winning sellers, as described in previous section, 
and 
Therefore, the utilities of SPs are more than zero.
On the other hand, the utilities of MTs in the loser set JL are zero. Since the utilities of both sellers and buyers are not less than zero, the proposed JRAPA is individually rational.
Lemma 3 The JRAPA is budget balanced.
Proof The MEC servers and BSs are auctioneers, which take charge of the whole auction process in JRAPA. No extra charge is required. The total profit of MEC servers and BSs gained as auctioneers are 
To conclude, the proposed JRAPA is budget balanced.
3 Performance Evaluation
In this section, we use a computer simulation to evaluate the performance of the proposed JRAPA algorithm, and compare the performance of the JRAPA mechanism with other algorithms.
3.1 Simulation setup
We consider a simulation scenario where 3 BSs and 3 MEC servers randomly locate on a 1000-meter road. The initial available resources of BSs and MEC servers are {55, 50, 60} MHz, {7 000, 8 000, 7 500} Mega/s, respectively. We set the channel gain of the MTs following the Gaussian distribution 
where μ0=10, 
The transmission power MT j is set to be σij=1. The wireless and cloud resource requests as well as the delay constraint are randomly distributed on the intervals (0,2) MHz, (20,100) Mega/s, and (5,10) ms, respectively. The fixed transmission power is pj=20 dBm, and ∀j∈J. The factors in Eq.(6) are α= 0.3, β= 0.3, and γ=0.4. Moreover, the wireless and cloud bidding price are distributed within (5,10) $/MHz and (0,1) $/Mega, respectively. We set the cost of the wireless unit and cloud resource to be 
and 
The maximum auction round rmax are set to be 20, and the bidding price adjustment steps of MT j are 
and 
3.2 Simulation results
Fig.4 describes the resource utilization rates of three SPs. In the JRAPA, the resource utilization rates of all three SPs increase when the number of MTs varies from 50 to 200. Since the auction is processed in parallel to achieve faster matching between buyers and sellers, successful trade increases with the increasing number of MTs, and as a result, the resource utilization shows a rising trend. However, when the number of MTs is larger than 200, utilization is no longer increasing. It is due to the limited resource capabilities of SPs, which fail to completely meet the requirements of the MTs.
Fig.4 Average resource utilization of SPs with respect to the number of MTs
We then investigate the convergence speed of the proposed JRAPA algorithm. The successful trade rate (STR) is defined as the proportion of winning MTs. We compare the performance of JRAPA with three algorithms: motion-prediction-based resource allocation (MPRA) [7], one-shot sealed combinational auction (OSCA) and multi-round sealed sequential algorithm (MSSA) [15]. In MPRA, each MT chooses a SP based on motion-prediction, and the SP determines the winners according to the first come first service (FCFS) rule. SSCA is a one-round auction. According to the MSSA, the MT sequentially bids to a SP by means of polling in each iteration.
In Fig.5, the STR of four algorithms is compared when the number of MTs is 100. It is clear that the number of successful trades in MPRA, MSSA and JRAPA shows an upward trend with the iteration times, while in OSCA, the value remains constant. After 3 iterations, the successful trade rate in JRAPA achieves the maximum. The RCUR algorithm and the bidding priority determination in JRAPA increase the successful trade in the auction. In conclusion, the convergence speed of the JRAPA is faster than other algorithms and the maximum STR in the JPARA is 81.82%, 100% and 156.41% larger than that of MPRA, OSCA and MSSA, respectively.
Fig.5 Successful trade rate comparison
Fig.6 shows the average utilities of SPs in different algorithms. Since the MPRA determines the winners according to the FCFS rule, the average utility of SPs in MPRA is revealed randomly. The average utility in the JPARA is 107.91%, 66.02% and 29.44% larger than that of MPRA, OSCA and MSSA, respectively. At the winner determination stage, SPs always choose the MT with the highest utility as the winner in each round of the auction, as a result of which the successful trade rate and average utility of SPs are higher than those of other algorithms.
Fig.6 Average utility of SPs with respect to the number of MTs
The delay of MTi is calculated by Eq.(3), and the average delay is 
As shown in Fig.7, compared with MPRA, OSCA and MSSA, the delay in JRAPA is reduced by 46.67%, 41.46% and 33.33% on average, respectively. On the one hand, since the wireless resource auction and cloud resource auction are processed in parallel, the matching delay between buyers and sellers is significantly reduced. On the other hand, the MTs take available resources of SPs and distance factors into account to determine the bidding priority, which decreases the processing time. As a result, the proposed JRAPA can well meet the latency requirement of MTs, and the delay is significantly reduced compared with other algorithms.
Fig.7 Average delay comparison
4 Conclusion
In this paper, we propose a JRAPA algorithm for MEC system, which includes the bidding submission, winner determination and pricing stages, aiming at maximizing the utilities of SPs and satisfying the delay requirements of the MTs. At the bidding submission stage, the MTs take available resources from SPs and distance into account to determine the bidding priority. At the winner determination stage, a RCUR algorithm is put forward to match the SPs and MTs, and the wireless resource auction and cloud resource auction are processed in parallel to achieve the fast matching of the buyers and the sellers, thus reducing the complexity of the algorithm and system delay. A sealed second-price rule is adopted at the pricing stage to ensure the independence between the price paid by the buyer and its own bid. The JRAPA algorithm is proved to be computationally efficient, individually rational and budget-balanced. Simulation results illustrate that the proposed JRAPA algorithm achieves a better performance in terms of the number of successful trades and utilities of the SPs. Moreover, compared with MPRA, OSCA and MSSA, the delay in JRAPA is significantly reduced.
[1]Mao Y Y, You C S, Zhang J, et al. A survey on mobile edge computing: The communication perspective[J]. IEEE Communications Surveys & Tutorials, 2017, 19(4): 2322-2358. DOI:10.1109/comst.2017.2745201.
[2]Sharma K C, Bhakar R, and Tiwari H. Extreme Nash equilibrium of polymatrix games in electricity market[C]// International Conference on Recent Advances and Innovations in Engineering (ICRAIE-2014). Jaipur, India, 2014: 14631364-1-14631364-5.
[3]Yu R, Ding J F, Huang X M, et al. Optimal resource sharing in 5G-enabled vehicular networks: A matrix game approach[J]. IEEE Transactions on Vehicular Technology, 2016, 65(10): 7844-7856. DOI:10.1109/tvt.2016.2536441.
[4]Meneguette R, Boukerche A. Peer-to-peer protocol for allocated resources in vehicular cloud based on V2V communication[C]//IEEE Wireless Communications and Networking Conference. San Francisco, CA, USA, 2017: 16868607-1-16868607-6.
[5]Zhang H, Tang X, Banez R, et al. An EPEC analysis for power allocation in LTE-V networks[C]//IEEE Global Communications Conference. Singapore, 2017: 17506109-1-17506109-6.
[6]Kumar N,Misra S, Rodrigues J J P C, et al. Coalition games for spatio-temporal big data in internet of vehicles environment: A comparative analysis[J]. IEEE Internet of Things Journal, 2015, 2(4): 310-320. DOI:10.1109/jiot.2015.2388588.
[7]Plachy J, Becvar Z, Strinati E. Dynamic resource allocation exploiting mobility prediction in mobile edge computing[C]//IEEE Annual International Symposium on Personal, Indoor, and Mobile Radio Communications. Valencia, Spain, 2016: 16556137-1-16556137-6.
[8]Lin C C, Deng D J, Yao C C. Resource allocation in vehicular cloud computing systems with heterogeneous vehicles and roadside units[J]. IEEE Internet of Things Journal, 2018, 5(5): 3692-3700. DOI:10.1109/jiot.2017.2690961.
[9]Zhang J, Xia W W, Cheng Z X, et al. An evolutionary game for joint wireless and cloud resource allocation in mobile edge computing[C]//International Conference on Wireless Communications and Signal Processing. Nanjing, China, 2017: 17416811-1-17416811-6.
[10]Sharma K C, Bhakar R, Tiwari H. Extreme nash equilibrium of polymatrix games in electricity market[C]//International Conference on Recent Advances and Innovations in Engineering. Jaipur, India, 2014: 14631364-1-14631364-5.
[11]Sardellitti S, Scutari G, Barbarossa S. Joint optimization of radio and computational resources for multicell mobile-edge computing[J]. IEEE Transactions on Signal and Information Processing over Networks, 2015, 1(2): 89-103. DOI:10.1109/tsipn.2015.2448520.
[12]Sheng Z G, Mahapatra C, Leung V C M, et al. Energy efficient cooperative computing in mobile wireless sensor networks[J]. IEEE Transactions on Cloud Computing, 2018, 6(1): 114-126. DOI:10.1109/tcc.2015.2458272.
[13]Yu R, Ding J F, Huang X M, et al. Optimal resource sharing in 5G-enabled vehicular networks: A matrix game approach[J]. IEEE Transactions on Vehicular Technology, 2016, 65(10): 7844-7856. DOI:10.1109/tvt.2016.2536441.
[14]Zhang H L, Guo F X, Ji H, et al. Combinational auction-based service provider selection in mobile edge computing networks[J]. IEEE Access, 2017, 5: 13455-13464. DOI:10.1109/access.2017.2721957.
[15]Jin A L, Song W, Zhuang W H. Auction-based resource allocation for sharing cloudlets in mobile cloud computing[J]. IEEE Transactions on Emerging Topics in Computing, 2018, 6(1): 45-57. DOI:10.1109/tetc.2015.2487865.
[16]Jin A L, Song W, Wang P, et al. Auction mechanisms toward efficient resource sharing for cloudlets in mobile cloud computing[J]. IEEE Transactions on Services Computing, 2016, 9(6): 895-909. DOI:10.1109/tsc.2015.2430315.
[17]Xu L, Wang J, Nallanathan A, et al. Resource allocation based on double auction for cloud computing system[C]//International Conference on High Performance Computing and Communications. Wuhan, China, 2016: 1538-1543.