Joint Resource Allocation Using Evolutionary Algorithms in Heterogeneous Mobile Cloud Computing Networks

Weiwei Xia, Lianfeng Shen

National Mobile Communications Research Lab, Southeast University, Nanjing 210096, China

Abstract: The problem of joint radio and cloud resources allocation is studied for heterogeneous mobile cloud computing networks.The objective of the proposed joint resource allocation schemes is to maximize the total utility of users as well as satisfy the required quality of service (QoS) such as the end-to-end response latency experienced by each user. We formulate the problem of joint resource allocation as a combinatorial optimization problem.Three evolutionary approaches are considered to solve the problem: genetic algorithm (GA),ant colony optimization with genetic algorithm(ACO-GA), and quantum genetic algorithm(QGA). To decrease the time complexity, we propose a mapping process between the resource allocation matrix and the chromosome of GA, ACO-GA, and QGA, search the available radio and cloud resource pairs based on the resource availability matrixes for ACOGA, and encode the difference value between the allocated resources and the minimum resource requirement for QGA. Extensive simulation results show that our proposed methods greatly outperform the existing algorithms in terms of running time, the accuracy offinal results, the total utility, resource utilization and the end-to-end response latency guaranteeing.

Keywords: heterogeneous mobile cloud computing networks; resource allocation; genetic algorithm; ant colony optimization; quantum genetic algorithm

I. INTRODUCTION

With the rapid development of mobile networks and portable smart devices, the demands for high-speed data applications, such as high-quality wireless video streaming,social networking, and interactive gaming,have been growing exponentially recently [1].Mobile cloud computing (MCC) is widely considered as a promising paradigm to satisfy the high-speed multimedia demands of end users, as well as provide higher capacity of mobile networks [2, 3]. MCC not only benefits mobile end users by offloading the computing and storage requirements from mobile devices into the powerful cloud computing platforms,but also can be beneficial to radio access networks (RAN). Cloud radio access networks(C-RAN) would provide on-demand resource processing, delay-aware storage, and high network capacity wherever needed [4]. In the environment of C-RAN, there usually exist heterogeneous radio access networks with dif-ferent capabilities in terms of bandwidth, latency, coverage area, or cost [5]. The complementary characteristics of different RANs can support multiple types of user requirements which have different quality of service (QoS)demands, as well as provide seamless user-accessing and global coverage of networks.

In mobile cloud computing systems, a critical challenge is how to guarantee the QoS from end-to-end applications’ perspective [6].Actually, in the heterogeneous mobile cloud scenario, to satisfy the required QoS of diverse users and ensure the optimal usage of the resources of clouds and wireless networks,it becomes essential to jointly manage the cloud and radio resources in the clouds and the heterogeneous RANs [7, 8]. However,most of the previous works which studied the cloud computing and wireless networks have addressed the resource allocation of the two important areas separately [9-13]. In [9], a distributed multi-service resource allocation algorithm in heterogeneous wireless access medium is studied. However, the analytical models are only applicable to the heterogeneous wireless networks which solve their own network utility maximization problems.Energy efficient radio resource allocation in the two-tier heterogeneous cloud radio access networks is studied respectively in [10-12].However, cloud resource allocation is not considered in these studies. In [13], a multicloud resource allocation algorithm based on a Markov Decision Process is proposed, which is capable of dynamically assigning the computational resources to a set of service requirements. However, radio resource allocation in the wireless networks is not considered.

In [14], the optimal strategy to assign each mobile user the radio and cloud resources jointly is proposed to minimize the overall energy consumption, under latency constraints.However, the strategy is found not for the MCC systems with the heterogeneous RANs,but for the cellular network with small-cell base stations. The topology configuration and rate allocation problem in C-RAN is studied in[15], with the objective of optimizing the endto-end performance of mobile cloud computing users. The homogeneous cellular network with cooperated BSs is considered as the radio access network. The dynamic cloud and wireless networks operations are studied jointly in [16], where the cloud mobile media price decision, wireless resource allocation and interference management are formulated as a multi-level Stackelberg game. However, the end-to-end performance of mobile cloud computing users is not given sufficient consideration. In [17], a cross-network radio and cloud resource management scheme for heterogeneous mobile cloud networks is proposed. The objective of the studied scheme is to maximize the tenant revenue while satisfying the QoS requirements. Nevertheless, the overlapping coverage of heterogeneous RANs and multiple types of service requirements are not taken into consideration. In [18], a dynamic heterogeneous resource orchestration framework is proposed aiming at achieving maximal performance of end users and minimal cost of cloud resources in the heterogeneous mobile cloud computing system. However, the diverse QoS requirements of users are not taken into consideration. In [19], the offloading selection, radio and computational resource allocation are jointly optimized to effectively save energy consumption on mobile terminals. However,the study set the same constraints of available radio and computational resource allocation to diverse users. In [20], an online joint radio and computational resource management algorithm is proposed to minimize the system power consumption without considering the economic cost of offloading. Moreover, the execution delay of the algorithm increases linearly with the control parameter. In [21], the offloading decisions of all users’ tasks as well as the allocation of computation and communication resources are jointly optimized to minimize the overall cost of all users in a multi-user mobile cloud computing system. However,the economic costs of offloading and resource allocation are not taken into consideration.

In the cloud computing networks, the users accessed by heterogeneous RANs could be connected to the cloud provider through the cloud management broker, which provides the management and optimization of cloud resources in order to guarantee the QoS requirements of users [22]. However, the long wide area network (WAN) latency is a fundamental obstacle while a mobile device executes a resource-intensive application on a distant computer server. The concept of cloudlet was put forward in [23], and the main idea is bringing computational resources closer to the mobile user. The simplicity of management and utilization of a cloudlet makes it be easily deployed on many scenarios such as base station (BS) in cellular network and access point(AP) in WLAN. Recent researches show that bringing resources closer to the user improves not only power consumption at the terminal side but also the important QoS metric latency[14][24]. Therefore, in this paper, we use the mobile cloud computing system with local cloudlets to guarantee the end-to-end QoS of mobile users.

In this paper, we jointly study the radio and cloud resource allocation in heterogeneous mobile cloud computing networks. The overlapping coverage of mobile networks and the heterogeneity of service requirements are given sufficient consideration. The objective of the proposed joint resource allocation schemes is to maximize the total utility of users as well as satisfy the QoS requirement such as the response latency experienced by each user.The joint resource allocation in heterogeneous mobile cloud computing networks is formulated as a combinatorial optimization problem.Evolutionary algorithms are stochastic search methods that can be an outstanding alternative to solve complicated combinatorial optimization problem. GA has been considered as a class of general-purpose search strategies for optimization problems [25]. ACO algorithm is inspired by the foraging behaviour of real ants,which are capable of exploring and collecting pheromone information [26, 27]. QGA is a novel evolutionary technique which is based on the concept and principles of quantum computing [28, 29]. Therefore, in this paper we focus on these three typical evolutionary algorithms, and the joint resource allocation problem is solved by using genetic algorithm(GA), ant colony optimization with genetic algorithm (ACO-GA), and quantum genetic algorithm (QGA), respectively. To decrease the time complexity, we propose a mapping process between the radio or cloud resource allocation matrix and the chromosome of GA,ACO-GA, and QGA, search the available radio and cloud resource pair for each service requirement based on the resource availability matrixes for ACO-GA, and encode the difference value between the allocated radio or cloud resources and the minimum resource requirement for QGA. The performances of the proposed resource allocation schemes are evaluated by using extensive computer simulations.

The remainder of this paper is organized as follows. The system model and problem formulation are described in Sect. II. The proposed joint resource allocation schemes based on GA and ACO-GA and QGA are presented in Sect. III, IV, and V, respectively. In Sect. VI,the time complexity of three evolutionary algorithms is analysed. In Sect. VII, the performances of the proposed schemes are evaluated and compared with existing schemes. Finally,we conclude the paper in Sect. VIII.

II. SYSTEM DESCRIPTION AND PROBLEM FORMULATION

The system we consider in this paper is shown in figure 1, which mainly consists of two sub-systems, i.e., heterogeneous radio access networks and cloud computing networks(CCNs). The wireless communication mainly happens at the heterogeneous RANs, while the processing for the cloud services happens in the CCNs.

2.1 Heterogeneous radio access networks

In the coverage area of heterogeneous radio access networks, a set N of RANs with different access technologies is available, with N ={1,2,..,N}, and each RAN has the bandwidth limitation Ln. It is assumed that RAN-1 (cellular network) served by macro base stations (MBSs) has the largest coverage, and RAN-n (n=2,3,…,N) served by small base stations (SBSs) has smaller coverage. We assume that M mobile terminals (MTs), denoted by set M, M ={1,2,..,M}, are uniformly distributed in the geographical region, and each MT with several wireless interfaces is able to connect to different RANs. The number of bandwidth units allocated from RAN-n to a MT m is denoted as bm,n, where n∈N and m∈M. The radio resource allocation matrix Bwindicates how the radio resources are allocated,where bm,n=0 if the resources of RAN-n are not allocated to MT m, andif the bandwidth of RAN-n is allocated with a value betweenandto MT m. The variablesanddenote the minimum and maximum number of bandwidth units to meet the service requirement of MT m, respectively. Different types of services usually have different bandwidth requirements. For example, the constant bit rate (CBR) service of MT m requires a constant bandwidth, i.e.On the other hand, MT m with a variable bit rate service requires a bandwidth allocation withinand. Because the overlapping coverage of RANs, not all of the radio resources are available to each MT. The matrixis applied to denote the radio resource availability for MTs,where lm,n=1 if and only if the radio resources through RAN-n are available to the MT m,and l=0 otherwise. Let the parameter

m,ndenote the price MT m uses one basic bandwidth unit assigned by RAN-n.

2.2 Cloud computing networks

In the cloud computing networks, the local cloudlets are connected with each other and to the Internet. The MBSs or SBSs connect to the local cloudlets through wired link. A mobile user canfind the appropriate MBS or SBS in a short distance, and then access cloud functionalities. In this paper, the computational resources are mainly considered as cloud resources in the cloudlets. It is assumed that there are a set R of local cloudlets be available to the mobile users, with R ={1,2,...,R}, and each cloudlet has computational capability Cr(CPU cycles/s). The cloud computing tasks from the MTs can be time-sensitive game data processing, scientific computing, multimediafile adaption, etc,. The data size of the job of the MT m involved in the computation intensive service requirement is denoted as ηm,which takes ?mCPU cycles to execute. The computational resources required by a service range betweenand, which represent the maximum and minimum fraction of Crassigned by the cloud to MT m. We denote the prices that MT m uses cloud resources provided by cloudlet-r as prm.

The cloud resource allocation matrix Crrepresents the cloud resource allocation, where cm,r=0 if the resources of cloudlet-r are not allocated to MT m, andif cloudlet-r allocates the resources betweenandto the service requirement. The matrixis applied to denote the cloud resource availability for MTs, where lm,r=1 if and only if the cloud resources through cloudlet-r are available to MT m, and lm,r=0 otherwise.

2.3 Problem formulation

The objective to jointly allocate radio and cloud resources to the upcoming service requests is to maximize the total reward of all the mobile users as well as satisfying the services’ QoS requirements. Let xm,n(xm,n∈{0,1})/xm,r(xm,r∈{0,1}) d e n o t e whether the service requirement from MT-m is allocated resources by RAN-n/cloudlet-r or not. Let um(bm,n,cm,r) denote a utility function of jointly allocating the bandwidth bm,nfrom RAN-n and the cloud resources cm,rfrom cloudlet-r to the service requirement of MT m.The utility function is given by

where w, γ and θ are constants indicating the scale and the shape of utility function, λ and ε denote the weights which represent the tradeoff between the transmission rate and service cost. Thefirst term in the right hand side of the utility function represents the attained reward of users from allocated bandwidth bm,nand cloud resources cm,r[9]. The second term represents the cost MT pays for the allocated radio resources, which is related with the traffic type and the radio access technologies. The third term represents the cost MT pays for the allocated cloud resources.

The objective of resource allocation is to maximize the total utility of users, while guaranteeing the bandwidth assigned to MT m can satisfy its QoS requirement, the total bandwidth provided by RAN-n cannot exceed the capacity limitation, the allocated cloud resources can satisfy the requirement of MT m, the total cloud resources allocated by cloudlet-r cannot exceed the capacity limitation, and the overall latency for each service request must be lower than the maximum tolerable value. The sixth and seventh constraints mean that each MT’s service requirement can only be served by one wireless network and one local cloudlet. The objective formulation is given by

In Eq. (3), W0is the bandwidth of one unit,hm,ndenotes the transmission power of RAN-n to user m, gm,ndenotes the channel gain between MT m and RAN-n, and σ0denotes the background noise power.

Unfortunately, Eq. (2) is inherently combinatorial and then NP hard, which makes the solving of the problem of joint allocation of cloud and radio resources hard to achieve.Since evolutionary algorithms are proved to be an outstanding alternative to solve combinatorial optimization problem in reasonable time.Therefore, we propose to use evolutionary algorithms to efficiently solve the problem.

III. THE JOINT RESOURCE ALLOCATION BASED ON GA

The GA engine maintains a population of possible radio and cloud resource allocation solutions. A solution corresponds to a chromosome which is an encoded representation of the resource allocation to each MT. As bm,n=0 when lm,n=0 for each service requirement, only one MBS/SBS and one local cloudlet will allocate the radio and computational resources to each service requirement, if we encode every element in Bwand Cr, there will be a lot of redundancy in the chromosome. So we propose to encode only those elements which do not take the value 0. In each chromosome,the gene bmis denoted as the radio resources allocated to the service requirement from MT m, and gene cmis denoted as the computational resources allocated to it. Letbe the vector of variable bmandbe the vector of variable cm. Therefore, a chromosomeis a vector of genes. In order to evaluate the fitness of the chromosome, we need to map the chromosome to the resource allocation matrixes Bwand Cr. bmis mapped to one of the elements in Bwwhose locations are in set, and cmto one of the elements in Crwhose locations are in set. Figure 2 is an example of mapping the chromosome to the resource allocation matrixes, where M=6, N=5, and R=4. In figure 2, the gene b2is mapped to one of the elements whose locations are in set Aw={(2,1),(2,2),(2,4)}, i.e. b2,1, b2,2and b2,4in matrix Bwrandomly. Note that encoding all the elements in Bwand Crneeds 54 integers,while encoding the elements in a chromosome only needs 12 integers.

The GA engine maintains a population set H of H solutions,. Each solution h has afitness value associated to it which is found by evaluating the fitness function.We apply the penalty functions to solve the constrained optimization problem [31]. The extended objective of solution h is defined as

Fig. 2. An example of mapping the chromosome to the resource allocation matrixes.

where σn, μrand θmare sufficiently large penalty factors. Definethefitness is calculated by

In Eq. (5), ζ＞1, which is the control coef ficient. The process of resource allocation based on GA is given as follows.

Step 1: Given the parameters H, Ln,parameters governing the generation of successor populations: the crossover rate cr of the population and the mutation rate u. Set the values of, prm, w, γ, θ, λ and ε. Given L Lw,r,set the length of the chromosome as 2M, and setsuch that elements inare arranged increasingly in n and r, respectively.

Step 2: Randomly generate a population of H solutions with the variable values inuniformly-distributed betweenand,and the variable values inuniformly-distributed betweenand. Moreover,because each MT’s service requirement can only be served by one network and one local cloudlet, for each solution, the initialized allocation of radio and cloud resources should satisfy the constraints

Step 3: For all the chromosomes, map the mth variable ofto one of the elements in Bwwhose locations are in set Awand map the mth variable ofto one of the elements in Crwhose locations are in set

Step 4: Compute thefitness of each solution of the current population according to Eq. (4)(5).

Step 5: The H members of H are ranked according to their fitness values in an order of highest-to-lowest value. Then only thefirst(1-cr)×H members of H are directly selected to the next generation.

Step 6: The remaining cr×H solutions of H are selected based on roulette wheel selection scheme, and the crossover scheme in [32] is performed on these selected solutions.

Step 7: u percent of solutions in H are chosen randomly for mutation. For each selected solution, one randomly selected non-zero gene is replaced by a new random value satisfying

Step 8: When the iterations reach the predefined maximum generation Igmax, stop; if not,go to step 4.

IV. THE JOINT RESOURCE ALLOCATION BASED ON ACO-GA

ACO can converge into the neighbourhood of the optimal solution through pheromone deposits, but with the limitation of premature convergence [26]. GA has the ability of exploring a broader searching space to find the feasible solution but with lower computational efficiency [25]. We intends to take advantage of both ACO and GA strategies to achieve an overall efficient solution while avoiding their disadvantages.

The ACO model is shown in figure 3. The set of service requirements is denoted asIn the ACO model,the set of available radio and computational resources is denoted as

The process of resource allocation based on ACO-GA is shown as follows.

Step 1: Put A ants on the set of service requirementsrandomly, and set the initial pheromone and heuristic information. Given Lw,Lrand setsuch that elements in Aw, Arare arranged increasingly in n and r,respectively. Set such GA parameters as the crossover rate cr, the mutation rate u and the values of variables, prm, w, γ, θ, λ, ε,,, Cr,,and. Set the loop counter Nc= 0, and Ic= 0.

Step 2: Each ant a (a=1,..., A) selects the appropriate radio resources betweenandand the appropriate cloud resources betweenandto the service requirements according to the probability

where α and β are the parameters representing the importance of pheromone and heuristic information, respectively,is the set of feasible pairs of bandwidth and cloud resources to be selected by ant a for service requirement sm, withThat means ant a only searches the pairs of resources from the available RAN and local cloudlet, and the resources should satisfy the quality requirement of MT m. Therefore, the search space is greatly decreased.

Step 3: Ant a moves to the next service requirement which was not assigned resources,and repeats Step 2 until all the M service requirements are assigned resources.

Fig. 3. ACO model.

Step 4: After all the A ants select the appropriate pairs of bandwidth and cloud resources to the service requirements according to the probabilities, the utility of each of A solutions is computed asand the best solution with the maximum utility is selected to update the pheromone in the searching route of the ant with the best solution. The pheromone trail update rule is performed as:

where 0≤ρ≤1 is a parameter governing the pheromone decay process. ?τmd′is defined as

where ubestis the utility of the best solution with

Step 5: Set Nc=Nc+1. If Nc＜Ncmax, repeat Step 2-4, else go to Step 6.

Step 6: A population set of A solutions are obtained, i.e.For all the chromosomes, map the resources pair () for the service requirement smto bm,nand cm,rin matrix Bwand Cr, respectively. Compute thefitness of each solution of the current population according to Eq. (4)(5).

Step 7: The A solutions are ranked according to theirfitness values in an order of highest-to-lowest value. Then the first (1-cr)×A solutions are directly selected to the next generation. The remaining cr×A solutions are selected based on roulette wheel selection scheme. A crossover scheme in [32] is performed and u percent of solutions are chosen randomly for mutation.

Step 8: Set the generation of iterations Ic=Ic+1. If Ic＜Icmax, repeat Step 2-7, else stop.

V. THE JOINT RESOURCE ALLOCAITON BASED ON QGA

QGA adopts qubit chromosome to represent the superposition of solutions. To decrease the redundancy in the qubit chromosome, we propose to encode only those elements which do not take the value 0 in Bwand Cr, and encode the difference value between the allocated radio resources and Bmmin, and that between the allocated computational resources and.Therefore, the length of the chromosome is decreased, and the search space is greatly decreased.

QGA maintains a population of qubit chromosomes,with the ith chromosomeat generation g can be represented as

where W is the number of quantum genes and can be expressed aswith Rmbe the binary string length to denote the difference value, andbe the binary string length to denote the value.andmust satisfywheredenotes the population size.

The process of resources allocation based on QGA is shown as follows.

Step 1: Set population sizeand set the number of qubits W in the chromosome. The parameters,,,and.Given Lw, Lrand set Aw, Arsuch that elements in Aw, Arare arranged increasingly in n and r, respectively. Set g=0, and initialize Q(g)=Q(0), whereandare initialized with

Step 2: Make P(g) by observing the states of Q(g), whereandis a binary solution of.

Step 3: Convert the binary string P(g) into integer string. For the ith chromosome,convert thefirstbits to M integers,and each integer addsto obtain vector. Convert the subsequen tbits to M integers, and each integer addsto obtain vector. For all the chromosomes,map the mth variable ofto one of the elements in Bwwhose locations are in set, and map the mth variable ofto one of the elements in Crwhose locations are in setThen compute thefitness values according to Eq. (4)(5), and store the best solution with the largestfitness value.

Step 4: If it reaches the maximum generation Iqmax, terminate the algorithm; else, go to step 5.

Step 5: Set g=g+1, observe chromosomes in Q(g?1) to obtain P(g).

Step 6: Repeat the processes in Step 3, update Q(g?1) by using quantum crossover and quantum mutation as in [29], and go to Step 4.

VI. COMPLEXITY ANALYSIS

In this section, we analyse the time complexity of the proposed three algorithms. In the joint resource allocation scheme based on GA, the mapping operation takes constant time as it depends on the number of chromosome, which isfixed. Thefitness calculation is about some elementary addition, subtraction, multiplication and division; thus, the time is constant.The time for a crossover operation depends on the chromosome size and the population size.Since the sizes of the chromosome and population are 2M and H, respectively, it will be of the order O(2MH). The time for the mutation operation depends on the size of the population, and it is bounded by O(H). Thus, the complexity of GA is of the order O((2M+1)HImax).

In the proposed scheme based on ACOGA, in the ACO phase, for an ant, the time complexity can be bounded by O(MJ), withNow, there are A number of ants in each round, so the time complexity for the maximum round is O(MJANcmax). The complexity for the GA phase is O((2M+1)AIcmax). Therefore, the complexity of the proposed ACO-GA algorithm will be of the order O(MJANcmax-+(2M+1)AIcmax).

In the proposed QGA-based scheme, the time for the quantum crossover and quantum mutation depends on the size of the chromosome and the population size. Since the size of the chromosome and population is W and,respectively, it will be of the order O(2W).Therefore, the complexity of QGA is of the

VII. SIMULATION RESULTS

In this section, based on our simulation platform for heterogeneous networks with local cloud computing module, we evaluate the performance of the proposed joint resource allocation schemes and compare them with the existing schemes.

7.1 Simulation scenarios and system parameter settings

In heterogeneous mobile access networks, we consider three RANs: RAN-1 is LTE-based cellular network, RAN-2 and RAN-3 are LTE-based femto-cell networks. The coverage ranges of MBS and SBS are set respectively to be 500m and 50m, and the mobile terminals and femto-cells are randomly distributed within the coverage range of a macro-cell.The transmission power of MBS hm,nisfixed as 46dBm and that of SBS is 20dBm [33]. We set the path loss between MT m and MBS as 15.3+37.6log10dmand the path loss between MT m and SBS as 46.86+20log10dm, where dmis the distance between MT m and MBS/SBS[33]. We also take the parameters of the small scale and shadow fading in [33].

Two types of computation intensive service requirements are considered: type-1 service requirements with the data size ηmbeing 1000KB; type-2 service requirements with ηm=2000KB. Each MT m randomly supports one type of service requirements. For the type-1 service requirement, the minimum and maximum number of required bandwidth units are==1, and the minimum and maximum computational resource requirements are=108(CPU cycles/s) and=109(CPU cycles/s), respectively. For the type-2 service requirements,=3,=5,and==109(CPU cycles/s). In the cloud computing networks, it is assumed that there are two local cloudlets be available to the mobile users, i.e. R=2.

We choose the same parameters of the evolutionary algorithms such as H,, A,cr, Igmax, Icmax, Iqmax, and u. As for the QGA-based scheme, the increment of rotation angle of quantum gates is decreased linearly from 0.05π at the first generation to 0.005π at the last generation[29]. Table 1 summarizes the main simulation parameters.

7.2 Optimization performance of the proposed joint resource allocation schemes

We compare the performance of the proposed joint resource allocation schemes with the successive convex approximation (SCA)-based algorithm [34] and the exhaustive search (ES)method. In the SCA-based joint resource allocation scheme, an approximation method is adopted to compute a local optimal solution of Eq. (2). In the ES method, optimal values of utilities are obtained. The results are shown in table 2. In table 2, the best, worst and average values of the objective function are achieved by the GA, ACO-GA, QGA, SCA and ES after 30 times of running for every algorithm,with M=5. As it can be seen, the running time of three proposed algorithms are always much shorter than that of ES. The reason is that a mapping process between the radio or cloud resource allocation matrix and the chromosome is used in the proposed algorithms,the available radio and cloud resource pairs based on the resource availability matrixes are searched in ACO-GA, and only the difference values between the allocated resources and the minimum resource requirement are encoded for QGA. Therefore, the time complexity of the proposed algorithms is greatly decreased.It can also be seen from table 2 that ACO-GA has less running time than GA and QGA. This is because the basic idea behind ACO-GA is to generate initial solutions by the ACO method, and then serve these solutions to the GA as its initial population of individuals. Thus,the GA will start with a population, which is not randomly generated as in the general case,but one rather closer to the optimal solution.Therefore, ACO-GA can achieve commensurate calculations precision with less computation resources, in terms of time and memory.

The proposed three algorithms achieve the similar values of total utility which is denoted asand the utilities are very close to the optimal valuesobtained by ES. The ES method achieves the maximum utilities at the expense of high computational complexity. The utility of all three evolutionary algorithms perform far better than SCA. This is because in SCA-based scheme, the original nonconvex problem is approximated to a sequence of strongly convex problems converging to a local solution of the original problem. Therefore, the proposed three algorithms can achieve better performance in terms of the accuracy offinal results.

Table I. Simulation parameters.

Table II. Performance comparison.

Fig. 4. Comparison of utility.

7.3 Performance Improvement of the Proposed Joint Resource Allocation Schemes

We evaluate the performance improvement of the proposed three schemes and compare them with the existing schemes. There are two existing schemes used for comparison. The first one is the QoS aware dynamic resource allocation scheme proposed in [17], which is called Existing scheme I. The second one seperately optimizes the radio and computing resources, which is called Existing scheme II.

7.3.1 Utility improvement

Through extensive simulations, it is found that the utilities of the proposed three resource allocation schemes are close to each other,which can be seen in table 2. Therefore, we select the QGA-based scheme to compare with the existing shemes. The utility performance with different numbers of MTs is plotted in figure 4a. It can be seen from figure 4a that all the utilities under three resource allocation schemes increase when the number of MTs increases. This is because more radio and computational resources are allocated when there are more service requirements in the system. The proposed QGA-based scheme can achieve the highest utility and significantly improves the utility, compared to the Existing scheme I and II. The utility with the Existing scheme II is the lowest among three schemes and increases slowly as the number of MTs increases. The reseaon is the Existing scheme II does not allocate the radio and computational resources jointly, which results in the uneffective allocation of resources and the lower utility. Nevertheless, the proposed scheme based on QGA achieves higher utility than the existing schemes, for example, with the number of MTs being 20, by 56.46% compared with Existing scheme I and by 140.35% compared with Existing scheme II.

In figure 4b, the utility performance with different price of femto-cell access is plotted,when the number of MTs being 5. It is shown in figure 4b that the utilities of all the schemes decrease as the prices rises. This is because when the prices increase, higher costs will have to be paid by mobile users, which lower the utility. The proposed scheme also outperforms the existing ones, with the improvement of 39.99% comparing with Existing scheme I, that of 63.20% comparing with Existing scheme II, respectively, at the price of RAN-2 access being $0.005. The result illustrates again that the proposed QGA-based scheme efficiently allocates the radio and computational resources and can achieve the best utility performance.

The reason for the proposed scheme to have the highest utility is as follows. Firstly,it is owing to the coordination on resource allocation between the heterogeneous wireless networks and local cloudlets. Secondly, the traffic-differentiated resources allocation can better balance the resources to satisfy different requirements of multiple types of service requirements. These two factors make radio and cloud resources be allocated more efficiently among multiple service requirements, thus boosting the overall utility.

7.3.2 Response latency improvement

We compare the average response latency of type-1 service requirements among the proposed schemes based on GA, ACO-GA, QGA,Existing scheme I and Existing scheme II. It can be seen from figure 5 that the average response latencies of Existing scheme I and Existing scheme II increase significantly when the number of MTs increases. This is because when the number of service requirements increases, the system allocates less radio and computatioanl resources to each accepted service requirement to accommodate more access requirements. Therefore, the response latency increases. It can also be seen from figure 5 that the average response latencies of the proposed schemes based on GA, ACO-GA and QGA are close to each other. Moreover,the average response latencies of the proposed schemes increase slightly with the increasing of service requirements, and always keep lower than the response latency upperbound. The

Fig. 5. Comparison of response latency.

reason is that the proposed resource allocation schemes strike a balance between the efficient reource allocation and the response lantency to achieve the maximum utility. Meanwhile,the use of local cloudlets in the cloud computing networks avoids the latency through wired links to remote cloud servers. Therefore, it guarantees the lower average response latencies compared with the existing schemes.

7.3.3 Radio resource utilization improvement

Fig. 6. Comparison of radio resource utilization.

We compare the radio resource utilization versus the number of MTs with type-2 service requirements among the proposed schemes based on GA, ACO-GA, QGA and the existing schemes. Let ηsdenote radio resource utilization and be defined asIt can be seen from figure 6 that ηsin the proposed schemes increases as the number of type-2 MTs increases. Moreover, as shown in figure 6, ηsin the proposed schemes is bigger than that in the existing schemes. The reason is that diverse user quality requirements are considered in the proposed resource allocation schemes. As the number of MTs with type-2 service requirements increases, the total amount of allocated bandwidth resources increases accordingly, and type-2 services require more radio resources than type-1 services. As a result, the resource utilization is more efficient in the proposed schemes.However, in the existing shemes, there is no difference between different types of service requirements, which results in the lower resource utilization. Moreover, the intrinsic features of joint resource allocation as well as satisfying the QoS requirements in the proposed schemes guarantee the better QoS performance in terms of resource utilization.

VIII. CONCLUSIONS

In this paper, we studied the joint resource allocation problem in heterogeneous mobile cloud computing networks. The objective of the proposed joint resource allocation schemes is to maximize the total utility of users as well as satisfy the QoS requirement such as the end-to-end response latency experienced by each user. The radio and cloud resources are jointly allocated by using GA, ACO-GA,and QGA, respectively. To the best of our knowledge, this is thefirst work that exploits the evolutionary algorithms to achieve joint resource allocation for mobile cloud computing. Moreover, some efficient methods such as mapping process are used to decrease the time complexity of the proposed evolutionary algorithms. Simulation results show that compared to the existing schemes, the proposed joint resource allocation schemes can achieve significant performance improvement in terms of running time, the accuracy offinal results,utility, response latency and radio resource utilization.

ACKNOWLEDGEMENTS

This work is supported by the National Natural Science Foundation of China (No. 61741102,No. 61471164), and China Scholarship Council.