[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

Optimal multi-dimensional dynamic resource allocation in mobile cloud computing

Abstract

In this paper, we propose a model for mobile application profiles, wireless interfaces, and cloud resources. First, an algorithm to allocate wireless interfaces and cloud resources has been introduced. The proposed model is based on the wireless network cloud (WNC) concept. Then, considering power consumption, application quality of service (QoS) profiles, and corresponding cost functions, a multi-objective optimization approach using an event-based finite state model and dynamic constraint programming method has been used to determine the appropriate transmission power, process power, cloud offloading and optimum QoS profiles. Numerical results show that the proposed algorithm saves the mobile battery life and guarantees both QoS and cost simultaneously. Moreover, it determines the best available cloud server resources and wireless interfaces for applications at the same time.

1 Introduction

Popularity of smartphones and related applications in various fields are increasing in everyday life significantly. These devices have a wide range of features (e.g., high-speed processors and supporting multiple wireless interfaces). Furthermore, due to increasing complexity of applications, smartphones require a significant computational capability. In addition, they have become a primary computing platform for many users due to the well-developed applications in realms such as mobile commerce, mobile learning, mobile health care, mobile computing, mobile gaming, and etc. As applications become more and more complex, mobile users experience shorter battery lifetime. Most of the smartphone applications are QoS-sensitive and computation-intensive to perform on a mobile system. Mobile cloud computing is a new concept in which mobile users access the cloud virtual resources via the Internet. It is beneficial to QoS and battery saving by means of mobile data offloading. Mobile computation offloading technique shares application code between the cloud server and the mobile. Most of the time, mobile users need to maintain a low level of power consumption and thus computation must be performed in the cloud which comes with cost. Therefore, mobile users always face a trade-off between communication and computation [1].

On the other hand, wireless network cloud (WNC) [2] proposes an architecture to join wireless access systems to cloud computing and shift the processing of base stations with different technologies to a virtual cloud network. Therefore, all wireless technologies is converging and is suitable for next generation wireless networks. WNC and cloud radio access network (C-RAN) [3] using similar software-defined radio (SDR) concept tend to decrease wireless network operating cost while enhancing the total network performance. Accordingly, without doubt, the next generation of wireless networks (5G) movement toward wireless clouds is irresistible [4, 5].

Despite flexibility and great potential applicability, resource allocation problem in heterogeneous wireless networks (HetNet) attributed with WNC and mobile cloud computing has received scarce attention as of today. Therefore, the prime contribution of the current research has been based on bridging HetNet with WNC and mobile cloud computing to better allocate resources to the end user. In addition, a multi-objective optimization problem considering cloud server power consumption, operating cost, and QoS followed by a detailed trade-off amongst user objectives have been studied.

In this paper, we propose a model including the operators, clouds, applications, and mobile profile parameters. Due to the fact that a part of the algorithm has to be conducted in smartphones, complexity order of the problem becomes a vital parameter. Estimation and approximation techniques have been used to linearly approximate the parameters to decrease complexity order of our algorithm. Using dynamic constraint programming [6, 7], event-based lexicographic multi-objective optimization method [8] and QoS-based resource allocation solutions [9, 10] with consideration to the resources and applications constraints, network, and mobile resources have been allocated to applications simultaneously.

It is worthy of note that the main objective of this paper concerns performance metrics of mobile devices and users, regardless of cloud computing centers and wireless operators related challenges, [1116] which have not been considered in this paper.The rest of the paper is organized as follows: this study’s related works is discussed in Section 2, in Section 3, the system model will be defined, followed by the optimization algorithm in Section 4. Within Section 5, numerical results reveal performance of the proposed multi-dimensional algorithm. Finally, Section 6 concludes the paper.

2 Related works

Rahimi et al., [17], Fernando et al., [18], and Dinh et al., [19] give an overview of the mobile cloud computing (MCC) presenting definition, architecture, applications, and approaches, then, on the corresponding challenges at the operational, user, and application levels have been discussed. They introduced MCC as the dominant computing model for mobile applications in the future.

Moreover, extensive research such as in [2022] has been done over wireless local area network (WLAN)/ cellular interworking mechanisms, which combines WLANs and cellular data networks into integrated wireless data networks featured with QoS capabilities. Liu et al. [23] suggest a new dynamic load balance (DLB) scheme to improve communication performance focusing on underlying users. In their proposed scheme, joint session admission control is a basis for user mobility, cognition, and service arrival awareness in integrated 3G/WLAN networks. Gazis et al.and Luo et al. [24, 25] recommend a standardization policy in the area of WLAN-cellular data network integration for different interworking architectures. Proposing the generic interworking architectures in the technical literature, [26] studies general aspects of integrated WLAN-cellular data networks. Access network discovery and selection function (ANDSF) suggests a function for selection of access network and control offloading amongst 3rd generation partnership project (3GPP) and other access networks. Such selections are based on the mobile battery saving, user preference, and operator policies. However, ANDSF does not consider application preferences, selection optimality, and simultaneous power allocation.

In general, international standards and standardization bodies such as WiMAX and 3GPP decide to move toward creating a seamless integrated wireless technology entitled HetNet [27]. HetNet by its nature includes a variety of wireless access technologies. Access networks are connected through a backbone which is a network core for all of them. Moreover, HetNet consists of both macro and micro cells as well as low power nodes which have distinct or overlapped coverage areas. When a multi-interface device moves within a HetNet environment, its default network for every connection can be determined based on a set of predetermined parameters of network nature such as QoS settings, signal strength, backbone utilization, speed preference, selected cost or service, and mobile node’s remained battery life.

Furthermore, some researchers have studied power consumption in smartphones. Murmuria et al., [28] and Carroll and Heiser [29] measure, analyze, and model power usage of smartphones by characterizing their sub-systems power usages. Balasubramanian et al. [30] consider wireless interface selection problem as a statistical decision problem and propose an algorithm to select the wireless network interface considering the context of the mobile applications in order to improve the battery lifetime. Hence, the features of wireless access interface selection also has fundamental impact on the performance of mobile computing applications and their power consumption.

There are some trade-offs amongst power consumption, QoS parameters, and costs. These objectives are dependent on network parameters, applications profiles, and cloud resources. Cuervo et al. [31] aim to optimize energy consumption of a mobile device by estimation and evaluating the trade-off between the energy consumed by local processing versus the transmission of code and data for cloud offloading. Decision process in [31] considers information and complex characteristics of the mobile environment. A framework for smartphones is introduced in [32]. It shifts smartphone application processing into the cloud centers. It is based on the concept of smartphone virtualization in the cloud and addresses lack of scalability by creating virtual machines of a complete smartphone system on the cloud. ThinkAir [32] provides on-demand resource allocation by dynamically managing VMs in the cloud via using an execution controller. The execution controller handles decision-making and communication with the cloud server. It considers execution time, energy, and cost to make decision in order to achieve optimum performance. With regard to the network profile parameters, device profile parameters, and program profile parameters of the smartphone, ThinkAir dynamically allocates the available cloud resources to the programs simultaneously. Kumar and Lu [33] suggest that cloud computing can potentially save energy through offloading of applications processing with limited reliability and quality of service requirements. This reflects the fact that for some applications such as delay-sensitive ones, migrated offloading to the clouds could not significantly offer energy savings to the smartphones while satisfying QoS parameters.

Trade-off between system throughput and energy consumption of mobile devices has been addressed in [34]. Based on the Lyapunov optimization approach, an online control algorithm is designed to balance energy and throughput. It maximizes a joint utility using stability-utility parameters while bounding the traffic queue length, via making instantaneous decisions to control the transmission pattern. The admission control algorithm diminishes the need for statistical estimation of traffic arrivals and link conditions.

In order to allocate resources amongst the cloud users efficiently, a communication framework amongst cloud users and service providers has been designed in [35]. There, authors propose a biding language in order to convert cloud user demands into the organized requests which helps cloud providers to support heterogeneous user demands while protecting the systems from selfish user behavior. Moreover, online compatible online cloud auction (COCA) mechanism is implemented to make users incentive to reveal their honest valuations. Finally, they have considered the sum of all the valuations of the allocated resources as the benchmark.

A QoS-aware resource-allocation multiple cooperative subtasks of jobs in cloud-based computing and data store services are investigated in [36]. Defining the objective function as a weighted sum of the expense and the job completion time and job execution time deadlines and budget constraints, game theory approach is used to solve the scheduling problem. First, considering users as their chosen strategy regardless of the others, a binary integer programming method is proposed to obtain the initial independent optimization solution. Then, an evolutionary strategy is designed to achieve the optimal solution.

Regarding the scalability advantage of public clouds and better QoS especially delay and power consumption of local clouds, MAPCloud is proposed in [37]. This provided a means to select local and public clouds for mobile applications in order to increase the performance and scalability of the applications. Interestingly, for a fixed price, MAPCloud decreases 32% of the delay and power consumption while providing scalability. Then, cloud resource allocation for mobile applications (CRAM) using heuristic methods has been developed as a resource allocation module for mobile applications achieving 84% of the optimal power saving solutions for large amount of users.

Rahimi et al. [38] focused on modeling the mobile applications as location-time workflows (LTW) of task. 2D location map is used to locate mobile hosts and cloud resources. Moreover, trajectory has been associated with mobile users. Defining QoS as a function of delay, power, and price, an efficient heuristic algorithm called MuSIC is proposed to maximize the mobile utilities while ensuring high-application QoS.

Applying the game theory approach, coalition of the cloud service providers is addressed in [39] where the uncertainty of internal users from each provider has been taken into account. First, with respect to randomness of demand, a stochastic linear programming game model to study the resource and revenue sharing for cloud providers is developed. Then, using the Markov chain to model coalitional arrangement, the coalitional game for forming the cooperation to share resource and revenue are investigated.

In this paper, we address performance modeling of mobile applications using MCC and WNC. A resource allocation algorithm is proposed to allocate resources and mobile transmission power and process power.

3 System model

In this section, we present a system model for optimum resource allocation. We assumed that mobile users access application clouds via WNC and the Internet. Figure 1 shows the presumed topology based on [2] and [19]. However, as of today, smartphones just support WLAN/cellular technologies simultaneously.We assume that there are a number of active applications on a mobile phone that support both WLAN and cellular technologies. In order to achieve a better performance and improve power saving, a portion of the processing workload has to be offloaded to the clouds. As depicted in the Figure 2, each application must choose a proper wireless interface and a cloud network to offload the processes to. However, the said selection process depends on parameters such as battery lifetime and required processing load. In addition, a feasible QoS profile for the application needs to be determined.

Figure 1
figure 1

Network topology.

Figure 2
figure 2

Algorithm architecture.

In order to conceive this model presumption, we defined sets of variables according to application profiles, computing resource profiles, and network profiles. A={1,2,..,i,..I} states a set of mobile applications, C R={1,..,j,,..J} states a set of available cloud computing resources, and W N={W N1,..,W N k ,,..W N K } represents accessible wireless network interfaces collection. Note thatI, J, and K are the number of active applications, available clouds, and wireless interfaces, respectively. Each collection element is a vector of characteristics which is related to the cost, power consumption, and QoS. An operating point OPn = (Un,Pn,Cn) is defined to describe the mobile system behavior over the n th time slot. Un shows the utilization associated with mobile user satisfaction and is strictly related to the QoS indexes of applications. Pn represents mobile phone power consumption, and Cn demonstrates mobile phone cost function. In this paper, appropriate jC R and kW N are assigned to the i th application in order for better formulation of controlling and optimizing the operating point. Therefore, operating point indicates important objectives of mobile user such as mobile power consumption at each time slot. All parameters of the model are detailed in Table 1.

Table 1 Table of parameters

Moreover, there are some limitations and restrictions on resources and user profiles which are strictly dependent on the mobile application QoS requirements and network parameters. In the following subsections, the objective functions and constraints will be investigated. Traffic rate of the i th application is defined discretely between λ min i and λ max i where i belongs to {1,2,...,I}. Due to the bound limits, different functions of downlink traffics are linearly approximated using affine functions and the Taylor series. Such approximations decrease the complexity order in a dramatic way while errors remain small.

3.1 QoS utilization and constraints

As explained before, utilization function is related to application QoS characteristics. Objective utilization function will be as follows:

U= i = 1 I ( χ i dep ( λ i , R i )+ χ i indep )
(1)

where χ i dep ( λ i , R i ) depends on the upload and download rate. Conversely, χ i indep is independent from the upload and download rate in the i th application utilization function.

Delay process consists of two parts, namely processing delay and communication delay. Also, communication delay includes two parts: wireless link delay and internet network delay. Applications such as cloud mobile gaming (CMG) interact closely with cloud servers. Therefore, uplink delay is a significant parameter as well. In addition, effective capacity concept has been used to model downlink wireless link delay. Assuming that arrival rates and service rates of the wireless links are all stationary and independent, according to the Gartner-Ellis limits [40, 41], wireless link delay violation probability of k th wireless interface is approximated by [4244]:

pr( D k > D k Th ) e - θ μ k D k Th
(2)

Internet delay (delay between the wireless network cloud and cloud servers) for interactive applications such as CMG denotes the round trip time delay, and for streaming applications denotes the one-way delay. Calculating the Internet delay requires a complicated procedure. However, assuming that the mobile cloud computing centers are near the wireless access network, Internet delay may be considered as a Gaussian random variable. Therefore, linear estimator [45] based on adaptive algorithm proposed in [46] is used to predict the Internet delay:

β j n ̂ = β j n - 1 + r σ β j n σ β ̂ j n ( β ̂ i n - 1 - β j n - 1 )
(3)

where r is equal to

r= E 2 ( β j n - E ( β j n ) ) ( β j n ̂ - E ( β ̂ j n ) ) ( E ( β j n - E ( β j n ) ) 2 ) ( E ( β ̂ j n - E ( β ̂ j n ) ) 2 )
(4)

β j n represents the Internet delay of the j th cloud server with the application in the n th time slot. After cloud server selection process, a cloud server is mapped to the i th application. Hereafter, we assume that the j th cloud server and k th wireless interface are assigned to the i th application. Therefore, total delay of i th application could be written by

D i = processdelay + wirelessuplinkdelay + internetdelay + cloudprocessdelay + wirelessdownlinkdelay
(5)

In Equation 5, the first part denotes the processing delay in the mobile phone related to the number of instructions per time slot executed in the mobile phone. Mobile process delay is approximated by C i - η i S i where η i represents the offloading instructions to the cloud and S i denotes effective processor speed dedicated to i th application. The second part denotes the uploading delay of smartphone approximated by TD i R i . The third part represents the network delay represented by β j . The forth part denotes the processing delay of the cloud server considered as η i + γ i S j . Finally, the last part implies the downlink delay of the k th interface represented by D w k . D w k is considered a random variable and its expected value is of great benefit to decision-making. The expected delay has to be less than the application delay threshold. QoS characteristics of the i th application could be written as follows:

Q i ={ λ min i , λ max i , λ i , R min i , R max i , R i , D i , D i Th }
(6)

3.2 Power consumption process

Power consumption also consists of two main parts, namely transmission power consumption and processing power consumption. The formulation will be as follows:

P=processingpower+transmissionpower
(7)

The first part indicates the processing power consumption, and the second part is the transmission power. Processing power may be approximated linearly as a function of effective processor speed dedicated to the applications.

Processingpower= i = 1 I P comp S i
(8)

Transmission power itself consists of connection maintenance power consumption [47] and data transmission power consumption.

Transmissionpower= k = 1 K ( P k tr ( H k , R k ) + P maint ( k ) )
(9)

Transmission power depends on the channel state information (CSI) and transmission rate of the mobile phone. Without a doubt, OFDM is the dominant technology in the current and future transmission technologies. With respect to the CSI on the receiver side, ‘Water filling’ could be an optimum algorithm to allocate the transmission power to the sub-carriers. Considering a single antenna, it will be equal to

P k tr ( H k , R k )= m k = 1 M k e ln 2 ( R k W k - m k = 1 M k log 2 ( h mk Γ k n mk ) ) - h mk Γ k n mk
(10)

where W k represents the k th interface sub-channel bandwidth. h mk is the m th sub-channel quality indicator of k th interface. Γ k indicates coding gain of k th interface, n mk states the m th sub-channel noise of the k th interface, and M k represents the number of subcarriers of the k th interface.

In the rest of the paper, we use Equation (10) as the transmission power function. Connection maintenance power consumption has a linear relation with transmission time. According to central limit theorem, allocated processing power for applications is approximated by a Gaussian random variable. Then, mobile CPU process sharing feasibility is defined by Pr i = 1 I S i > S p therefore, i = 1 I μ S ( i ) + ζ i = 1 I σ S ( i ) <S where ζ=Φ-1(1-p), Φ-1 is the inverse function of the CDF of normal distribution with μS(i) and σS(i) as the first and the second moments, respectively. For the proof, see [48].

3.3 Cost function

The cost function consists of the following two parts:

Cost=wirelessoperatorcosts+cloudservicecosts
(11)

We assumed that each active application receives service from a specific cloud server and a wireless interface is selected for communication of each application. Based on the proposed cost model in [49], the mobile cloud service cost function could be written as follows:

cloudservicecosts= j = 1 J α comp ( γ j + η j ) + α j UL R j + α j DL λ j
(12)

where λ j denotes the sum of the incoming traffic rates of applications which the j th cloud server is assigned to them. We assumed that each application is linked to a cloud server. First part indicates the computation cost while the second and the third parts represent the cost associated with data upload and download to cloud servers, respectively. Wireless access network costs also could be approximated linearly by

wirelessoperatorcosts= k = 1 K α k w λ k ′′ + σ k w R k ′′
(13)

λ k and R k denote the sum of incoming and outgoing traffic rates, respectively, of applications which the k th interface is assigned to them. Accordingly, the following characteristics for clouds and wireless network interfaces are proposed: CR j ={ α j UL , α j DL , β j , S j } and WN k ={ α k w , H k , R k max , P maint ( k ) } (See Table 1).

It is also possible to define objective functions and constraints with respect to application tasks instead of applications alone. Changing the scale from application to task increases resource allocation accuracy as well as complexity order of the algorithm.

4 Problem formulation and solution

4.1 Problem definition

Less power consumption, user satisfaction, and cost are of great interest to many mobile users. In this section, we propose a multi-objective dynamic resource allocation algorithm to optimize the aforementioned topics of interest in the form of objective function and processes with respect to the network resources and mobile and application constraints. Dynamic constraint programming and lexicographic-event-based optimization method [8] have been used to solve the multi-objective optimization problem. However, complexity order of the proposed algorithm also needs to be considered. Moreover, the previously highlighted measures of interest usually are not available in a closed form and are mostly obtained from numerical data. Henceforth, linear interpolation method for numerical data and the Taylor series for closed form function have been applied to approximate the input data or non-linear functions in a short interval, e.g., λ i [ λ min i , λ max i ]. However, as it will be explained shortly, the proposed protocol architecture design does not depend on linear functions of the system model. In fact, application of non-linear functions will not impact the complexity order drastically.

Figure 3 shows the overall structure of the proposed algorithm. The algorithm takes the parameters of cloud profiles, wireless access networks, mobile devices, and mobile applications as its input. In addition, it linearly approximates inputs such as cloud server delay based on which the state and corresponding events are selected. In the next level, optimum wireless network interface, best available cloud servers, offloading coefficients of applications, processing power and transmission power of the mobile phone and optimum QoS profile will be selected. Obtaining an optimum offloading solution, the execution controller introduced in [32] manages the shared process between the mobile phone and cloud servers.

Figure 3
figure 3

The proposed algorithm structure.

4.2 Problem formulation

Objective processes could be written as follows:

F 1 I (n)=-U(n)
(14)
F 2 I (n)=P(n)
(15)
F 3 I (n)=cost(n)
(16)

Here, we used negative utilization factor to convert the maximization problem to a minimization problem. Mobile device and resources constraints are iA

0 η i (n) C i (n)
(17)
Σ i = 1 I ( μ S i (n)+ζ σ S i (n))<S
(18)
λ k ′′ (n) μ k (n)
(19)

Application QoS profile constraints (Qmin<Q i <Qmax) are considered as follows: iA

E{ D i (n)} D i th
(20)
λ min i λ i (n) λ max i
(21)
R min i R i (n) R max i
(22)

The current delay model approximates the real delay scenarios. To accommodate a more complicated type of delay, Equation (20) can be replaced by arbitrary complex constraints.We use lexicographic optimization method to solve the proposed multi-objective optimization problem. Objective functions are prioritized based on the state of the system. In fact, only one objective function is selected in each state and others are considered as constraints. The state of the system depends on the next occurring event. A finite state model (FSM) is proposed for optimal resource allocation while considering different events to transit amongst the states. Figure 4 shows the proposed FSM structure.

Figure 4
figure 4

FSM structure.

The states are as follows:

  1. 1.

    Best QoS strategy: in this state, we try to maximize user utilization while considering other objectives as constraint.

  2. 2.

    Cost-effective mode: in this state, considering the QoS and power consumption constraints, the proposed resource allocation algorithm attempts to minimize the cost of the system.

  3. 3.

    Energy-saving mode: in this state, the proposed algorithm minimizes the power consumption of the system considering QoS and cost constraints.

The transition events take place as detailed below:

Ω occurs when ε(n)≤ε(nth) where ε(n) and ε(n th) denote the mobile energy in the n th time slot and its threshold, respectively. It shows that mobile energy is in a critical situation. Ω ́ occurs when: ε(n)≤ε(nth) and β happens when ε(n)≥ε(n-1) meaning that mobile device is being charged and is not in a critical situation energy wise. ϕ happens when B g(n)≤B gth where Bg and B g th denotes the mobile budget fee in the n th time slot and its threshold, respectively, reflecting the fact that mobile user budget is approaching levels lower than its threshold. Also, ϕ ́ occurs when B g(n)≥B g th. QoS-sensitive state is considered as the initial state. According to the occurring events, dynamic constraint programming is applied to find the optimal solution. The state of the system is shown by x, where x belongs to the set of states; X={1,2,3}. In each state, we solve the following optimization problem:

Argmin WN , CR , η , λ , R , S F x x I ST : F x ́ x I F x ́ th x ́ X , x ́ x ( 17 ) , ( 18 ) , ( 19 ) , ( 20 ) , ( 21 ) , ( 22 )

where Equations (17), (18), (19) and Equations (20), (21), (22) are the resources and the mobile applications constraints, respectively, and

λ = λ 1 , .... λ i , ... λ I η = η 1 , .... η i , ... η I R = R 1 , .... R i , ... R I S = S 1 , .... S i , ... S I

Not only proper mobile cloud computing center and interface should be selected for the applications but also offloading, downloading, and uploading rates also should be determined in order to optimize the objective functions considering the constraints.

For instance, considering x=2, the optimization problem will be as follows:

Argmin η , λ , R , S i = 1 I P comp S i + k = 1 K ( Pt k ( H k , R k ) + P maint ( k ) ) ST : i = 1 I χ i , λ dep ( λ i ) + χ i , R dep ( R i ) + χ i indep U th j = 1 J α comp ( γ j + η j ) + α j UL R j + α j DL λ j + k = 1 K α k w λ k " + σ k w R k " Cost th E { D i ( n ) } D i th i A R min i R i ( n ) R max i i A 0 η i ( n ) C i ( n ) i A Σ i = 1 I ( μ S i ( n ) + ζ σ S i ( n ) ) < S λ min i λ i ( n ) λ max i i A λ k ′′ ( n ) μ k ( n ) k WN

Here, first the best possible wireless network interface and cloud have to be selected for each active application. Next, process offloading, and variables such as download/upload rate and effective processor speed dedicated to the applications with the goal of minimizing the power consumption of the device will be calculated.

4.3 Problem solution

w x i is considered as the input of the proposed algorithm corresponding to the i th application such as WN, CR collections in the x state. u x i also is considered as the control variable vector related to the i th application such as offloading factor and i th application incoming traffic rate at the x state. u x i is selected from a predetermined set U. URI is restricted to Equations (17), (18), (19), and (21). We assumed that s i is non-zero in all applications, because all applications need some process in a mobile phone. After multiplying Equation (5) by s i , all constraints and objective functions will be linear in terms of η, λ, and S. The only non-linear variable is power transmission rate. Bender decomposition method [7] is used to decompose the problem into functions linear in variables (i.e., η, λ, and S) and non-linear in variable R. Minimum amount of R i could be easily found through Equations (5) and (20) as follows:

R min i = D i th - ( β ̂ j + C i - η i S i + η i + γ i S j ) - E { Dw i } TD i
(23)

Then, R i could be found by

R i = R min i + ε R ( i )
(24)

where εR(i) is dependent on the objective function and objective constraints. In order to find the εR(i), simple incremental selection algorithm [50] is used. It ranges from 0 to R max i - R min i . However, if the transmission power consumption is linearly approximated in terms of transmission rate [30], then optimization problem will be simplified to a bilinear matrix inequality problem which could be solved with less complexity. f x ́ i ( u x i , w x i (j,k)x) shows the x ́ th objective function derived from the i th application. Therefore, cost to go function could be written as below:

F x x I = f x x I ( u x I , w x I ( j , k ) x ) + i = 1 I - 1 f x x ( u x i , w x i ( j , k ) x )
(25)

Thus,

F x x I = f x x I ( u x I , w x I (j,k)x)+ F x x I - 1
(26)

Also, the following constraint should be satisfied for the successive objective functions:

F x ́ x I = f x ́ x I ( u x I , w x I (j,k)x)+ F x ́ x I - 1 F x ́ x th x ́ X, x ́ x
(27)

Optimal solution to this problem could be found using dynamic programming (DP). It should be noted that applications are sorted according to their priorities and importance. Hence, the initial value of the objective is related to the most prioritized application. However, due to the constraints, computation complexity is much higher than a usual dynamic programming problem with brute-force search. A diagram based on [9] is proposed to find the optimal solution. Moreover, a method of learning from the mistakes [7] is used to restrict the feasible optimization region. Figure 5 shows the proposed algorithm structure. Using DP, the network and cloud resources are selected. In each DP step, linear programming output determines control variables of the system u x i . In order to decrease the complexity order, instead of brute-force search in resource and network selection, a policy is developed to assign the resources with the lowest objective values considering the application and resources constraints. The algorithm pseudo code is shown in Algorithm 1.

Figure 5
figure 5

Algorithm architecture.

To improve modeling, T D i and C i could be approximated linearly by η i and λ i

TD i = Y TD i η i + Z TD i , C i = Y C i λ i + Z C i
(28)

where Y TD i and Z TD i are coefficients used in linear approximation of the uploading data of i th application in terms of offloading computation. Y C i is the incoming traffic dependent part of the i th application process while Z C i is its independent part.

For more precise resource allocation under some conditions, it is possible to approximate the functions by higher order of the Taylor series or other functions (e.g., exponential family). The proposed algorithm, using bender decomposition method, always breaks the optimization method into two different parts, namely linear and non-linear optimization part.

Argmin u g ( u nonlin ) + p u lin ST : z ( u nonlin ) + qu lin G resource constraints applications constraints
(29)

where ulin,unonlin represent linear and non-linear control variables, respectively. Therefore, master problem is divided into sub-problems. Using column generation techniques, two sub-optimization problems are minimized simultaneously. Integration of the two aforementioned linear and non-linear subproblems restricts the optimization feasible region and despite of the increasing complexity, it converges to an optimal solution.

5 Numerical results

In this section, some numerical results are presented to verify analysis of the previous section. Resources and application constraints are usually based on [2830]. The resource characteristics considered in the numerical results are shown on Table 2. In the studied problem, we assumed that a main application such as CMG, video call, or media streaming is always present within the network, while considering presence of others as minor applications such as online social networks, health monitoring, or file and application download (I is considered a random variable between 2; 10 over the time). Fifty different cloud service providers with different characteristics have been considered in the network. The number of available WiFis is a random variable between 0 to 4. However, the number of available cellular networks varies from 1 to 5. If available resources are not enough for all applications, then the proposed algorithm allocates resources in order to maximize the objective function ignoring applications with less weight in the objective function. Connection maintenance power consumption includes elements such as receiving data power consumption. Receiving power consumption itself depends on several transmission parameters such as network contention [51].

Table 2 Numerical validation parameters

Objective indicators are defined as follows: u indicator (n)= u ( n ) u max ( n ) ×100, P indicator (n)= p min ( n ) p ( n ) ×100 and cost indicator (n)= cost min ( n ) cost ( n ) ×100 where umax(n), pmin(n), and costmin(n) represent the extremum achievable utilization, cost, and power consumption without considering the constraints of the mobile device at the n th time slot. Figure 6 shows the mobile device performance with respect to the time. As demonstrated, the mobile device had started with the best QoS strategy state and had a large utilization factor. After budget reduction state changed to cost effective mode, the algorithm minimized the cost of the mobile usage. Finally, when the remaining battery energy went lower than the threshold (10%) the state was changed to energy-saving mode which minimizes the device power consumption. Blue line shows the average tracking of the operating point through the time. Red points are the operating point samples during different time slots. Figure 7 shows power efficiency factor for different number of applications and different power consumption thresholds. As it is shown in Figure 7, generally with higher power consumption thresholds and more applications, utilization function tends to increase. However, for higher levels in number of applications with low power consumption threshold, utilization function is lower in comparison with applications 1with the same power threshold limit due to larger number of constraints. Figure 8 depicts the system power efficiency over the time domain for different average network delays. Value of power efficiency function shows the state transition from the best QoS strategy or cost-effective mode to energy-effective mode. Figure 8 shows that state transition takes place earlier for larger amounts of E (β). This indicates flexibility of the network in the proposed algorithm. However, for large values of E(β), algorithm could not find a feasible optimum point satisfying all the constrains. In addition, power efficiency decreased in a dramatic way. Also, Figure 9 shows the power efficiency in terms of different utilization thresholds and cost thresholds. It is obvious that with decrease in average utilization threshold, while average cost threshold increases, power efficiency increases as well.The complexity order of the proposed optimization algorithm is less than the complexity of brute-force search method. As depicted in Figure 10, the programming effort required which is defined by logarithm of the syntax lines to code the algorithm for the proposed dynamic constant programming is much less than the brute-force search.

Figure 6
figure 6

Operating point tracking on the time.

Figure 7
figure 7

Utilization indicator for different power thresholds and different number of applications.

Figure 8
figure 8

Power efficiency track over the time domain and different β parameters.

Figure 9
figure 9

Power efficiency.

Figure 10
figure 10

Complexity comparison.

6 Conclusions

In this paper, based on WNC concept, a system model for next generation of mobile communication has been considered. Cost, QoS, and power consumption functions are defined based on the system model. Next, a multi-dimensional optimization algorithm is proposed to optimize the objectives of a mobile user. The proposed multi-dimensional optimization algorithm takes network parameters, mobile device, and application constraints as input to optimally select the network resources and applications QoS profiles with optimum offloading coefficients. The proposed algorithm is established on event-based lexicographic optimization method and dynamic constraint programming. Numerical results for different environmental variables revealed that the proposed algorithm could be dynamically adaptive to environmental parameters variation. We have solved the optimization problem assuming particular linear approximations which may not be always valid. The next step could be extending the current work to the case of nonlinear functions and processes. In addition to the objectives of mobile users, performance metrics of cloud computing data centers and wireless operators can be considered as well.

References

  1. Hu X, Xing G, Leung JYT: Exploring the interplay between computation and communication in distributed real-time scheduling. Compu. IEEE Trans 2011, 60(12):1759-1771.

    Article  MathSciNet  Google Scholar 

  2. Lin Y, Shao L, Zhu Z, Wang Q, Sabhikhi R: Wireless network cloud: architecture and system requirements. IBM J. Res. Dev 2010, 54(1):4-12.

    Article  Google Scholar 

  3. Jimaa S, Chai KK, Chen Y, Alfadhl Y: LTE-A: an overview and future research areas. Wireless and Mobile Computing,(WiMob), IEEE 7th International Conference On Networking and Communications, Shanghai, China 2011, 395-399.

    Google Scholar 

  4. Milosavljevic M, Sofianos S, Kourtessis P, Senior JM: Self-organized cooperative 5G RANS with intelligent optical backhauls for mobile cloud computing. 2013 IEEE International Conference On Communications Workshops (ICC), Budapest, Hungary 2013, 900-904.

    Chapter  Google Scholar 

  5. Demestichas P, Georgakopoulos A, Karvounas D, Tsagkaris K, Stavroulaki V, Lu J, Xiong C, Yao J: 5G on the horizon: key challenges for the radio-access network. IEEE Vehicular Technol. Mag 2013, 8(3):47-53.

    Article  Google Scholar 

  6. Hladik PE, Cambazard H, Déplanche AM, Jussien N: Solving a real-time allocation problem with constraint programming. J. Syst. Softw 2008, 81(1):132-149. 10.1016/j.jss.2007.02.032

    Article  Google Scholar 

  7. Hladik PE, Cambazard H, Déplanche AM, Jussien N: Dynamic constraint programming for solving hard real-time allocation problems. Network 2005, 4(m1):2.

    Google Scholar 

  8. Marler RT, Arora JS: Survey of multi-objective optimization methods for engineering. Struct. Multidisciplinary Optimization 2004, 26(6):369-395. 10.1007/s00158-003-0368-6

    Article  MathSciNet  Google Scholar 

  9. Lee C, Lehoczky J, Siewiorek D, Rajkumar R, Hansen J: A scalable solution to the multi-resource qos problem. 20th IEEE Symposium on Real-Time Systems, Phoenix, Arizona, USA 1999, 315-326.

    Google Scholar 

  10. Rajkumar R, Lee C, Lehoczky JP, Siewiorek DP: Practical solutions for QoS-based resource allocation problems. 19th IEEE Symposium on Real-Time Systems, Philadelphia, USA 1998, 296-306.

    Google Scholar 

  11. Duan Q, Yan Y, Vasilakos AV: A survey on service-oriented network virtualization toward convergence of networking and cloud computing. Netw. Service Manag. IEEE Trans 2012, 9(4):373-392.

    Article  Google Scholar 

  12. Xu F, Liu F, Jin H, Vasilakos AV: Managing performance overhead of virtual machines in cloud computing: a survey, state of the art, and future directions. Proc. IEEE 2014, 102(1):11-31.

    Article  Google Scholar 

  13. Wang L, Zhang F, Aroca JA, Vasilakos AV, Zheng K, Hou C, Li D, Liu Z: Greendcn: a general framework for achieving energy efficiency in data center networks. Selected Areas Commun. IEEE J 2014, 32(1):4-15.

    Article  Google Scholar 

  14. Wang L, Zhang F, Vasilakos AV, Hou C, Liu Z: Joint virtual machine assignment and traffic engineering for green data center networks. ACM SIGMETRICS Perform. Eval. Rev 2014, 41(3):107-112. 10.1145/2567529.2567560

    Article  Google Scholar 

  15. López-Pérez D, Chu X, Vasilakos AV, Claussen H: Power minimization based resource allocation for interference mitigation in OFDMA femtocell networks. Selected Areas Commun. IEEE J 2014, 32(2):333-344.

    Article  Google Scholar 

  16. López-Pérez D, Chu X, Vasilakos AV, Claussen H: On distributed and coordinated resource allocation for interference mitigation in self-organizing LTE networks. IEEE/ACM Trans. Netw. (TON) 2013, 21(4):1145-1158.

    Article  Google Scholar 

  17. Rahimi MR, Ren J, Liu CH, Vasilakos AV, Venkatasubramanian N: Mobile cloud computing: a survey, state of art and future directions. Mobile Netw. Appl 2014, 19(2):133-143. 10.1007/s11036-013-0477-4

    Article  Google Scholar 

  18. Fernando N, Loke SW, Rahayu W: Mobile cloud computing: a survey. Future Generation Comput. Syst 2013, 29(1):84-106. 10.1016/j.future.2012.05.023

    Article  Google Scholar 

  19. Dinh HT, Lee C, Niyato D, Wang P: A survey of mobile cloud computing: architecture, applications, and approaches. Wireless Commun. Mobile Comput 2013, 13(18):1587-1611. 10.1002/wcm.1203

    Article  Google Scholar 

  20. Balasubramanian A, Mahajan R, Venkataramani A: Augmenting mobile 3G using WiFi. In Proceedings of the 8th ACM International Conference on Mobile Systems, Applications, and Services. San Francisco, CA, USA; 2010:209-222.

    Google Scholar 

  21. Lee K, Rhee I, Lee J, Chong S, Yi Y: Mobile data offloading: how much can WiFi deliver? 2013.

    Google Scholar 

  22. Han B, Hui P, Srinivasan A: Mobile data offloading in metropolitan area networks. ACM SIGMOBILE Mobile Comput. Commun. Rev 2011, 14(4):28-30. 10.1145/1942268.1942279

    Article  Google Scholar 

  23. Liu Q, Yuan J, Shan X, Wang Y, Su W: Dynamic load balance scheme based on mobility and service awareness in integrated 3G/WLAN networks. Global Mobile Congress (GMC), Shanghai, China 2010, 1-6.

    Google Scholar 

  24. Gazis V, Alonistioti N, Merakos L: Toward a generic ‘always best connected’ capability in integrated WLAN/UMTS cellular mobile networks (and beyond). Wireless Commun. IEEE 2005, 12(3):20-29. 10.1109/MWC.2005.1452851

    Article  Google Scholar 

  25. Luo J, Mukerjee R, Dillinger M, Mohyeldin E, Schulz E: Investigation of radio resource scheduling in WLANs coupled with 3G cellular network. Commun. Mag. IEEE 2003, 41(6):108-115. 10.1109/MCOM.2003.1204756

    Article  Google Scholar 

  26. Salkintzis AK, Fors C, Pazhyannur R: WLAN-GPRS integration for next-generation mobile data networks. Wireless Commun. IEEE 2002, 9(5):112-124. 10.1109/MWC.2002.1043861

    Article  Google Scholar 

  27. Ng C, Paik E, Ernst T, Bagnulo M: Analysis of multihoming in network mobility support, RFC 4980 Internet, Draft draft IETF nemo multihoming issues 05. IETF, USA; 2007.

    Google Scholar 

  28. Murmuria R, Medsger J, Stavrou A, Voas JM: Mobile application and device power usage measurements. 2012 IEEE Sixth International Conference On Software Security and Reliability (SERE), Gaithersburg, MD, USA 2012, 147-156.

    Chapter  Google Scholar 

  29. Carroll A, Heiser G: An analysis of power consumption in a smartphone. In Proceedings of the 2010 USENIX Annual Technical conference, Boston, MA, USA. USENIX Association; 2010:271-285.

    Google Scholar 

  30. Balasubramanian N author=Balasubramanian, A280-293.

  31. Cuervo E, Balasubramanian A, Cho D, Wolman A, Saroiu S, Chandra R, Bahl P: Maui: making smartphones last longer with code offload. In Proceedings of the 8th International ACM Conference on Mobile Systems, Applications, and Services, San Francisco, CA, USA. ACM; 2010:49-62.

    Google Scholar 

  32. Kosta S, Aucinas A, Hui P, Mortier R, Zhang X: ThinkAir: dynamic resource allocation and parallel execution in the cloud for mobile code offloading. In Proceedings of IEEE INFOCOM, Orlando, FL, USA. IEEE; 2012:945-953.

    Google Scholar 

  33. Kumar K, Lu YH: Cloud computing for mobile users: can offloading computation save energy? Computer 2010, 43(4):51-56.

    Article  Google Scholar 

  34. Fang W, Li Y, Zhang H, Xiong N, Lai J, Vasilakos AV: On the throughput-energy tradeoff for data transmission between cloud and mobile devices. Inf. Sci 2014, 283: 79-93.

    Article  Google Scholar 

  35. Zhang H, Li B, Jiang H, Liu F, Vasilakos AV, Liu J: A framework for truthful online auctions in cloud computing with heterogeneous user demands. Proceedings IEEE INFOCOM 2013, Turin, Italy 2013, 1510-1518.

    Chapter  Google Scholar 

  36. Wei G, Vasilakos AV, Zheng Y, Xiong N: A game-theoretic method of fair resource allocation for cloud computing services. J. Supercomputing 2010, 54(2):252-269. 10.1007/s11227-009-0318-1

    Article  Google Scholar 

  37. Rahimi MR, Venkatasubramanian N, Mehrotra S, Vasilakos AV: MAPCloud: mobile applications on an elastic and scalable 2-tier cloud architecture. In Proceedings of the 5th IEEE/ACM Fifth International Conference on Utility and Cloud Computing, Chicago, USA. IEEE Computer Society; 2012:83-90.

    Google Scholar 

  38. Rahimi MR, Venkatasubramanian N, Vasilakos AV: MuSIC: mobility-aware optimal service allocation in mobile cloud computing. In IEEE Sixth International Conference On Cloud Computing,Santa Clara, CA, USA. IEEE; 2013:75-82.

    Google Scholar 

  39. Niyato D, Vasilakos AV, Kun Z: Resource and revenue sharing with coalition formation of cloud providers: Game theoretic approach. In Proceedings of the 2011 11th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, Newport Beach, CA, USA. IEEE Computer Society; 2011:215-224.

    Chapter  Google Scholar 

  40. Chang CS: Performance Guarantees in Communication Networks. Springer-Verlag, New York, USA; 2000.

    Book  Google Scholar 

  41. Wu D, Negi R: Effective capacity: a wireless link model for support of quality of service. Wireless Commun. IEEE Trans 2003, 2(4):630-643.

    Google Scholar 

  42. Tang J, Zhang X: Quality-of-service driven power and rate adaptation over wireless links. Wireless Commun. IEEE Trans 2007, 6(8):3058-3068.

    Article  Google Scholar 

  43. Tang J, Zhang X: Cross-layer modeling for quality of service guarantees over wireless links. Wireless Commun. IEEE Trans 2007, 6(12):4504-4512.

    Article  Google Scholar 

  44. Zhang ZL: End-to-end support for statistical quality of service guarantees in multimedia networks. PhD Thesis Dissertation

  45. Deutsch R: Estimation Theory. Prentice-Hall, New Jersey, USA; 1965.

    Google Scholar 

  46. Kansal A, Karandikar A: Adaptive delay estimation for low jitter audio over INTERNET. In IEEE Global Telecommunications Conference, San Antonio, TX, USA, vol. 4. IEEE; 2001:2591-2595.

    Google Scholar 

  47. Rahmati A, Zhong L: Context-for-wireless: context-sensitive energy-efficient wireless data transfer. In Proceedings of the 5th International Conference on Mobile Systems, Applications and Services, San Juan, Puerto Rico, USA. ACM; 2007:165-178.

    Google Scholar 

  48. Wang M, Meng X, Zhang L: Consolidating virtual machines with dynamic bandwidth demand in data centers. Proceedings of IEEE INFOCOM 2011, Shanghai, China 2011, 71-75.

    Chapter  Google Scholar 

  49. Chen F, Guo K, Lin J, La Porta T: Intra-cloud lightning: building CDNs in the cloud. In Proceedings of IEEE INFOCOM, Orlando, FL, USA. IEEE; 2012:433-441.

    Google Scholar 

  50. Du Q, Zhang X: QoS-aware base-station selections for distributed MIMO links in broadband wireless networks. Selected Areas Commun. IEEE J 2011, 29(6):1123-1138.

    Article  Google Scholar 

  51. Manweiler J, Roy Choudhury R: Avoiding the rush hours: WiFi energy management via traffic isolation. In Proceedings of the 9th International Conference on Mobile Systems, Applications, and Services, Washington DC, USA. ACM; 2011:253-266.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Shahin Vakilinia.

Additional information

Competing interests

The authors declare that they have no competing interests.

Authors’ original submitted files for images

Rights and permissions

Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (https://creativecommons.org/licenses/by/4.0), which permits use, duplication, adaptation, distribution, and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Vakilinia, S., Qiu, D. & Ali, M.M. Optimal multi-dimensional dynamic resource allocation in mobile cloud computing. J Wireless Com Network 2014, 201 (2014). https://doi.org/10.1186/1687-1499-2014-201

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1186/1687-1499-2014-201

Keywords