1

Multi-user Multi-task Offloading and Resource
Allocation in Mobile Cloud Systems

arXiv:1803.06577v1 [] 17 Mar 2018

Meng-Hsi Chen, Ben Liang, Min Dong

Abstract
We consider a general multi-user Mobile Cloud Computing (MCC) system where each mobile user
has multiple independent tasks. These mobile users share the computation and communication resources
while offloading tasks to the cloud. We study both the conventional MCC where tasks are offloaded
to the cloud through a wireless access point, and MCC with a computing access point (CAP), where
the CAP serves both as the network access gateway and a computation service provider to the mobile
users. We aim to jointly optimize the offloading decisions of all users as well as the allocation of
computation and communication resources, to minimize the overall cost of energy, computation, and
delay for all users. The optimization problem is formulated as a non-convex quadratically constrained
quadratic program, which is NP-hard in general. For the case without a CAP, an efficient approximate
solution named MUMTO is proposed by using separable semidefinite relaxation (SDR), followed by
recovery of the binary offloading decision and optimal allocation of the communication resource. To
solve the more complicated problem with a CAP, we further propose an efficient three-step algorithm
named MUMTO-C comprising of generalized MUMTO SDR with CAP, alternating optimization, and
sequential tuning, which always computes a locally optimal solution. For performance benchmarking,
we further present numerical lower bounds of the minimum system cost with and without the CAP.
By comparison with this lower bound, our simulation results show that the proposed solutions for both
scenarios give nearly optimal performance under various parameter settings, and the resultant efficient
utilization of a CAP can bring substantial cost benefit.

I. I NTRODUCTION
Mobile Cloud Computing (MCC) brings abundant cloud resources to extend the capabilities
of resource-limited mobiles devices to improve the user experience [3] [4]. With the help of
cloud resources, mobile devices can potentially reduce their energy consumption or processing
Preliminary results of this work have appeared in [1] and [2], where [1] focuses on the case of conventional two-tier MCC
without a CAP and [2] focuses on the case of three-tier MCC with a CAP. Meng-Hsi Chen and Ben Liang are with the
Department of Electrical and Computer Engineering, University of Toronto, Canada. Min Dong is with the Department of
Electrical, Computer and Software Engineering, University of Ontario Institute of Technology, Canada.

2

delay by offloading their tasks to the cloud. However, integration between mobile devices and
the cloud may affect the quality of service of those offloaded tasks and overall mobile device
energy usage due to additional communication and computation delays and transceiver energy
consumption.
The case of a single mobile user offloading its entire application to the cloud was studied in
[5], [6]. Furthermore, offloading by multiple mobile users was considered in [7]–[9], where each
user has a single application or task to be offloaded to the cloud in its entirety. Different from
such whole-application offloading, the authors of [10]–[16] considered partitioning an application
into multiple tasks. In all these cases, the partitioning problem results in integer programming
that is NP-hard in general.
In conventional MCC systems, communication between the mobile devices and the remote
cloud server often is over a long distance, which may result in large communication delay in task
offloading. In contrast, with an aim to reduce the communication delay for those offloaded tasks,
Mobile/Multiaccess Edge Computing (MEC), as defined by the European Telecommunications
Standards Institute, refers to a distributed MCC system where computing resources are installed
locally at or near the base station of a cellular network [17]–[19]. MEC shares similarities with
micro cloud centers [20], cloudlets [21], fog computing [22], and cyber-foraging [23], except that
the MEC computing servers are managed by a mobile service provider, which allows more direct
control and resource management. Similar to the concept of MEC, one may define a general
computing access point (CAP), which is a wireless access point or a cellular base station with
built-in computation capability. The mobile users’ computing tasks may be processed locally at
the mobile devices, sent to the CAP, or further forwarded to a remote cloud server. With the
additional option of computation by the CAP, we can reduce the need for access to the remote
cloud server, hence decreasing the communication delay and also potentially the overall energy
and computation cost.
In this work, we study the joint optimization of task offloading and resource allocation in a
general mobile cloud access network consisting of multiple mobile users, each having multiple
independent tasks. The wireless access point may serve its conventional networking function and
only forward the received tasks to the remote cloud server, or it may be a CAP that additionally
has limited built-in computation capability to directly process some of the tasks by itself. We take
into consideration the computation and communication energies, CAP and cloud usage costs,
and communication and processing delays at local user devices, the CAP, and the remote cloud

3

server.
The multi-user multi-task scenario adds substantial challenge to system design, since we need
to jointly consider both the offloading decisions and the sharing of limited computation and
communication resources among all users as they compete with each other while offloading
tasks. In particular, the delays of the offloaded tasks of a user will be affected by its assigned
computation and communication resources, as well as the scheduling of those tasks in the
computation and communication pipelines. Therefore, scheduling the tasks of even a single user
contains a multi-machine flow-shop problem [24], which has no known optimal solution in the
literature. In this work, we propose efficient heuristic solutions based on semi-definite relaxation
methods, together with delay bounding techniques, iterative optimization, and further sequential
performance tuning, which are numerically shown to provide nearly optimal performance.
The contributions of this work are summarized as follows:
• We first study the conventional MCC with a non-computing AP, focusing on jointly optimizing
the offloading decision and the communication resource allocation of all tasks, to minimize a
weighted sum of the costs of energy, computation, and delay for all users. The resultant mixed
integer programming problem can be reformulated as a non-convex quadratically constrained
quadratic program (QCQP) [25], which is NP-hard in general. To solve this challenging
problem, we first present a performance bounding framework that utilizes both the upper
and lower bounds of the multi-task total communication and computation delay for each user.
We then propose an efficient Multi-User Multi-Task Offloading (MUMTO) algorithm based on
separable semidefinite relaxation (SDR) [26], with recovery of the binary offloading decision
and subsequent optimal allocation of the communication resource.
• We then consider the presence of a CAP, aiming to jointly optimize the task offloading decisions and the allocation of computation and communication resources of all tasks. However, the
availability of CAP computation further complicates mobile task offloading decisions, adding
an extra dimension of variability at the CAP. To solve this challenging problem, we further
propose an efficient three-step algorithm named MUMTO with CAP (MUMTO-C), which first
utilizes a generalized version of the MUMTO SDR with an added CAP, and then performs
additional alternating optimization and sequential tuning. We show that it always computes a
locally optimal solution, which contains the binary offloading decision and subsequent optimal
allocation of the computation and communication resources.
• We also develop lower bounds of the minimum cost for both scenarios as the benchmark

4

for performance evaluation. Simulation results show that MUMTO and MUMTO-C both give
nearly optimal performance under various parameter settings. Furthermore, for the case with a
CAP, we conduct simulation experiment on alternative combinations of the three components
of the MUMTO-C algorithm, clarifying their roles and contributions to the overall system
performance. Finally, we compare the performance of MUMTO-C against that of purely
local processing, purely cloud processing, and hybrid local-cloud processing without the CAP,
which demonstrates the effectiveness of the proposed algorithm in joint management of the
computation and communication resources in the three-tier computing system of local devices,
CAP, and remote cloud server.
The rest of this paper is organized as follows. In Section II, we discuss the related work. In
Section III, we describe the system model. In Section IV, we provide details of the problem
formulation, the proposed algorithm, and the lower bound of minimum system cost for the
conventional MCC without a CAP. In Section V, the impact on the presence of the CAP is
further studied. We present numerical results in Section VI and conclude in Section VII.
Notations: We denote by aT and AT the transpose of vector a and matrix A, respectively. The
notation diag(a) denotes the diagonal matrix with diagonal elements being elements of vector
a. The trace function of matrix A is denoted by Tr(A). We use A(i, j) to denote the (i, j)th
entry of matrix A, and use A  0 to indicate that A is a positive semi-definite matrix.
II. R ELATED WORK
A. Two-Tier Offloading System
Many existing studies focus on two-tier cloud networks with mobile users and another tier of
external processors.
For a single user offloading its entire application, the tradeoff between energy saving and
computing performance was studied in [5], [6], [27]. Different from the above whole-application
offloading, the authors of [10]–[16] considered partitioning an application into multiple tasks.
Specifically, the authors of [10]–[12] focus on the implementation of offloading mechanisms
from the mobile device to the cloud, while the discussion on optimizing the offloading decisions
was limited. In [13], a heuristic offloading policy was proposed for a mobile user with sequential
tasks. In [14]–[16], the problem of cloud offloading for a mobile user with dependent tasks was
studied. All of the above studies focus on the single-user case.

5

The case of task offloading by multiple mobile users has been considered in [7]–[9], [28]–
[31], but in all of these works, each user only has a single task to process. Without considering
resource allocation, the authors of [7], [9], [28], [29] proposed different approaches to obtain the
offloading decisions for each user. In [8], [30], when all tasks are always offloaded, the authors
optimized the allocation of computation and communication resources. In contrast to the above
studies, instead of optimizing either the offloading decision only or the resource allocation only,
in this work we study the joint optimization as they are inter-dependent. The authors of [31]
considered the joint allocation of offloading decision and resource allocation with a sequential
optimization heuristic. The method can only be applied to the case where each user has a single
task. In contrast, in this work, the system design is much more challenging since we consider
the general multi-user multi-task scenario.
B. Three-Tier Offloading System
Besides the two-tier cloud networks above, the three-tier network model, consisting of mobile
users, a local computing node (e.g., cloudlet or CAP), and a remote cloud server, has been
studied in [32]–[36], [38], [39]. Compared with two-tier systems, the three-tier system adds
extra flexibility for task offloading. In [32]–[35], the authors only focused on optimizing the
offloading decisions without considering the allocation of computation and communication resources. However, since both computation and communication resources are limited and shared
among all users, without efficiently allocating those limited resources to different users, the full
benefit of task offloading cannot be realized. The joint optimization of the offloading decision and
the allocation of computation and communication resources for a general three-tier multi-user
multi-task offloading system has not been investigated before, and it is much more complicated
to solve.
We have previously studied the scheduling of computation and communication resources in
a CAP for a single mobile user [36] and multiple mobile users each with a single task only
[37]–[39], showing substantial system performance improvement under such simplified system
models. In this work, we focus on the joint optimization problem for a general multi-user multitask scenario.

6

Mobile M tasks
User 1

Access Point
Remote
Cloud

M tasks

Mobile
User 2

Mobile M tasks
User N

Fig. 1: System model. The AP may serve its conventional networking function and forward tasks to the remote
cloud server, or be a CAP with built-in computation capability to directly process some received tasks by itself.

III. S YSTEM M ODEL
A. Mobile Cloud Offloading with Multiple Users and Tasks
Consider a general cloud access network consisting of one cloud server, one AP, and N mobile
users, each having M independent tasks, as shown in Fig. 1.1 Examples of the AP may be a
cellular base station or a WiFi access point. The AP may serve its conventional networking
function and forward received tasks to the remote cloud server, or directly process some of
the tasks by itself when it has built-in computation capability. In the latter case, we name
it CAP. In this work, we first study a conventional mobile cloud offloading scenario without
the CAP, aiming to obtain optimal offloading decisions for all mobile users’ tasks as well as
resource allocation. Then, we will further study a more general scenario with the presence of
the CAP, showing substantial system performance improvement. Notice that we do not consider
any specific queueing model for each user’s tasks, since we will show latter in Sections IV-C
and V-C that our proposed solutions are generally applicable to any queueing discipline.
1

We assume the same M for all users only to simplify mathematical notation. It can be easily extended to the case where

each mobile user has a different number of tasks Mi . Our system model is similar to the ones in many previous studies [6],
[7], [9], [27], [29]–[31], where all tasks are assumed to be available at time zero. If the tasks arrive dynamically in time, we
may apply our model and the proposed solution in a quasi-static manner, where the system processes the tasks in batches as
they are collected.

7

B. Cost of Local Processing
We denote Din (ij), Dout (ij), and Y (ij) as the input data size, output data size, and processing
cycles2 of user i’s task j, respectively.3 For task j being locally processed by user i, the
corresponding energy consumed for processing is denoted by Eijl and the processing time is
denoted by Tijl .
C. Cost of Remote Cloud Processing
When user i’s task j is offloaded to the AP, we denote by Eijt and Eijr , respectively, the energy
consumed for wireless transmission and reception by the user. For the wireless connections
between mobile users and the AP, we denote the uplink and downlink transmission times by
Tijt = Din (ij)/(ηiu cui ) and Tijr = Dout (ij)/(ηid cdi ), respectively, where cui and cdi are uplink and
downlink bandwidth allocated to user i, and ηiu and ηid are the spectral efficiency of uplink
and downlink transmission between user i and the AP, respectively4. We have the following
constraints on cui and cdi as they are limited by the uplink bandwidth CUL and downlink bandwidth
CDL
N
X

cui ≤ CUL ,

(1)

N
X

cdi ≤ CDL .

(2)

i=1

and

i=1

We may consider also a total bandwidth constraint
N
X
i=1

(cui + cdi ) ≤ CTotal .

(3)

Since the AP has to further offload the task to the cloud, there is the additional transmission
time between the AP and the cloud denoted by Tijac = (Din (ij) + Dout (ij))/r ac , and the cloud
processing time denoted by Tijc = Y (ij)/f c , where r ac is the transmission rate between the AP
and the cloud and f c is the cloud processing rate for each user. The rate r ac is assumed to be
a pre-determined value regardless of the number of users, since the AP-cloud link is likely to
2

The processing cycles of user i’s task j depends on the input data size and the application type.

3

Similar to [6], [7], [9], [27], [29]–[31], these quantities may be obtained by applying a program profiler a program profiler

[10]–[12].
4

The spectral efficiency can be approximated by log(1 + SNR) where SNR is the link quality between user i and the AP.

8

be a high-capacity wired connection in comparison with the limited wireless links between the
mobile users and the AP, so that there is no need to consider bandwidth sharing among the users.
Similarly, f c is also assumed to be a pre-determined value because of the high computational
capacity and dedicated service of the remote cloud server. Thus, Tijac and Tijc only depend on
user i’s task j itself.
Finally, the cloud usage cost of processing user i’s task j at the cloud is denoted by Cijc . The
usage cost may depend on the data size and processing cycles of a task and the hardware and
energy cost to maintain the cloud server, but such detail is outside the scope of this work. Here
we simply assume that Cijc is given for all i and j.
D. Cost of CAP Processing
When we consider the presence of a CAP, some of the offloaded tasks can be directly processed
by the CAP. If user i’s task j is processed by the CAP (i.e., instead of being further forwarded
to the remote cloud), besides the communication energy (i.e., Eijt and Eijr ) and delay (i.e., Tijt
and Tijr ) mentioned above, we denote the CAP processing time by Tija = Y (ij)/fia , where fia is
the assigned processing rate, which is limited by the total processing rate fA at the CAP
N
X
fia ≤ fA .

(4)

i=1

Similarly, denote the CAP usage cost of processing user i’s task j at the CAP by Cija . In the
following, we first study the conventional MCC without considering the CAP. The impact on
the presence of a CAP will be further studied in Section V.
IV. M ULTI - USER M ULTI - TASK O FFLOADING

WITHOUT

CAP

In this section, we study the conventional mobile cloud network where the AP always forwards
the received tasks to the remote cloud server, focusing on jointly optimizing the offloading
decision and the communication resource allocation of all tasks, to minimize a weighted sum
of the costs of energy, computation, and the delay for all users.
A. Offloading Decision
Since there is no CAP, each mobile user can either process its tasks locally or offload some
of them to the cloud for processing through the AP. Let xij denote the offloading decision for
task j of user i, given by
xij =



0, process task j of user i locally;


1, offload task j of user i to the cloud.

9

B. Problem Formulation
We aim at reducing mobile users’ energy consumption and maintain the service quality of
processing their tasks, measured by the delays incurred due to transmission and/or processing. For
this goal, we define the total system cost as the weighted sum of total energy consumption, the
costs to offload and process all tasks, and the corresponding transmission and processing delays
for all users. Our objective is to minimize the total system cost by jointly optimizing the task
offloading decisions xij and the communication bandwidth resource allocation ri = [cui , cdi ]T .
This optimization problem is formulated as follows:

N X
M
X
l
C
L
C
min
(Eij (1 − xij ) + Eij xij ) + ρi max{Ti , Ti }
{xij },{ri }

i=1

(5)

j=1

s.t. (1), (2), (3),
riu , rid , ≥ 0, ∀i,

(6)

xij ∈ {0, 1}, ∀i, j,

(7)

where EijC , (Eijt + Eijr + βCijc ) is the weighted transmission energy and processing cost of
offloading and processing task j of user i to the cloud, with β being the relative weight; in
addition, TiL is the processing delay of tasks processed by the mobile user i itself, TiC is the
overall transmission and remote-processing delay for tasks of mobile user i processed at the
cloud, and ρi is the weight on the task processing delay relative to energy consumption in the
total system cost.
Depending on the performance requirement, the value of ρi can be adjusted to impose different
emphasis on delay and energy consumption.5 The proposed optimization problem (5) can be
solved by any controller in this network after collecting all required information. In practice, the
controller could be the AP. That is, each user provides its information to the AP, and the AP
broadcasts the obtained offloading decisions (and the corresponding resource allocations) to all
users by solving problem (5).
The above mixed-integer programming problem is difficult to solve in general. Based on
the offloading decision xij for each task, we have the total local processing delay for each
PM l
user TiL =
j=1 Tij (1 − xij ), for all i. However, we note that the overall delay for remote
5

To avoid mathematical redundancy, we only put the weight in front of the delay and normalize the weighted sum cost to

have the unit of energy. However, it can be easily extended to an objective with some arbitrary unit (e.g., dollars).

10

processing, TiC , is challenging to calculate exactly. This is because, when there are multiple tasks
offloaded by a users, the transmission times and processing times may overlap in an unpredictable
manner, which depends on the offloading decision, communication resource allocation, and task
scheduling order. In fact, since TiC consists of the uplink transmission times, remote-processing
time, and downlink transmissions times of all tasks, it may be viewed as the output of a multimachine flowshop schedule, which remains an open research problem [24]. Since TiC is not
precisely tractable, we will use both upper and lower bounds of TiC in our proposed solution
and performance benchmarking. Under the MUMTO algorithm, they are shown to give total
system costs that are close to each other.
C. Multi-user Multi-task Offloading (MUMTO) Algorithm
The joint optimization problem (5) is a mixed-integer non-convex programming problem. To
find an efficient solution to the original problem (5), in the following, we first propose both upper
bound and lower bound formulations of TiC , then transform the optimization problem (5) into a
separable QCQP, and finally propose a separable SDR approach to obtain the binary offloading
decisions {xij } and the communication resource allocation {ri }.
1) Bounds of Remote-Processing Delay: When a mobile user offloads more than one task
to the cloud, there will be overlaps in the communication and processing times as mentioned
above, making it difficult to exactly characterize the overall delay TiC . However, we have the
following upper bound of TiC as the worst-case delay formulation:

M 
X
Din (ij) Dout (ij)
C(U )
ac
c
+
+ Tij + Tij xij , ∀i.
=
Ti
ηiu cui
ηid cdi
j=1

(8)

Since the worst-case delay sums the transmission delays and processing delays together without
any overlap, it will always be greater than the real delay given the same offloading decision and
resource allocation. On the other hand, we separate the offloading delays of all mobile users
into several components and only consider the largest one as the lower bound of TiC :
C(L)

Ti
where Tiu =

PM

j=1

′

= max{Tiu , Tid , Tiuac , Tidac , Tic }, ∀i,

Din (ij)xij /(ηiu cui ) and Tid =

PM

d d
j=1 Dout (ij)xij /(ηi ci )

(9)
are total uplink and

downlink transmission times between the user and the AP for user i, respectively, Tiuac =
P
PM
ac
ac
dac
= M
j=1 Dout (ij)xij /r are total uplink and downlink transmission
j=1 Din (ij)xij /r and Ti

11

′

times between the AP and the cloud for user i, respectively, and Tic =
total cloud processing time for user i.
C(U )

In the following, we will use the worst-case delay Ti

PM

j=1 Y

(ij)xij /f c is the

in optimization problem (5) to obtain

an approximate solution, which can provide an upper bound to the total system cost. We then use
C(L)

Ti

similarly, to obtain a lower bound of the total system cost, for performance benchmarking.

In Section VI, by comparing both cases, we show that the MUMTO algorithm based on the
worst case formulation gives nearly optimal performance.
C(U )

2) QCQP Transformation and Semidefinite Relaxation: We first replace TiC with Ti

in

problem (5), and rewrite the integer constraint (7) as
xij (xij − 1) = 0, ∀i, j.

(10)
C(U )

We also introduce a additional auxiliary variable ti for max{TiL , Ti

}, the problem (5) is now

transformed into the following equivalent problem:

N X
M
X
l
C
min
(Eij (1 − xij ) + Eij xij ) + ρi ti
{xij },{ri ,ti }

s.t.

i=1

M
X
j=1

(11)

j=1

Tijl (1 − xij ) ≤ ti , ∀i,

M 
X
Din (ij)
j=1

ηiu cui


Dout (ij)
ac
c
+ u d + Tij + Tij xij ≤ ti , ∀i,
ηi ci

(12)

(13)

(1), (2), (3), (6), and (10).
In order to obtain the eventual SDR formulation, we first transform the optimization problem
(11) into a separable QCQP problem by the following steps.
First, we introduce two auxiliary variables Diu and Did , and replace constraint (13) with the
following equivalent constraints:
Diu

+

Did

+

M
X
j=1

(Tijac + Tijc )xij ≤ ti , ∀i,

(14)

M
X
Din (ij)xij

≤ Diu , ∀i,

(15)

M
X
Dout (ij)xij

≤ Did , ∀i,

(16)

j=1

ηiu cui

and

j=1

ηid cdi

12

where (14) is the overall offloading delay constraint, and (15) and (16) correspond to the uplink
transmission time and the downlink transmission time, respectively.
Next, we vectorize the variables and parameters in problem (11). Define
wi , [xi1 , . . . , xiM , cui , Diu , cdi , Did , ti ]T , ∀i,

(17)

which is the decision vector for user i with all decision variables. Then, the objective in problem
(11) can be rewritten as
N
X

bTi wi +

N X
M
X

Eijl ,

(18)

i=1 j=1

i=1

C
l
C
l
where bi , [(Ei1
− Ei1
), . . . , (EiM
− EiM
), 01×4 , ρi ]T . We rewrite the local processing delay

constraint (12) as
(bli )T wi

≤−

M
X
j=1

Tijl , ∀i,

(19)

l
where bli , −[Ti1l , . . . , TiM
, 01×4 , 1]T . For the cloud processing delay constraint (14), it can

be rewritten as
(bci )T wi ≤ 0, ∀i,

(20)

ac
c
where bci , [(Ti1ac + Ti1c ), . . . , (TiM
+ TiM
), 0, 1, 0, 1, −1]T . The matrix forms of constraints (15)

and (16) are
wiT Aµi wi + (bµi )T wi ≤ 0, µ ∈ {u, d}, ∀i,

(21)

where




ηiµ


′
1 0
,
Aµi , −  µ
2 η
0
i

0M ×M 0M ×2

′
u
Ai ,  02×M
Aui

03×M 03×2

µ ∈ {u, d},






0M ×3 
0(M +2)×(M +2) 0(M +2)×2 0(M +2)×1 



′
d
Adi
02×3  , Ai ,  02×(M +2)
02×1  ,



03×3
01×(M +2)
01×2
0

bui , [Din (i1), . . . , Din (iM), 01×5 ]T , bdi , [Dout (i1), . . . , Dout (iM), 01×5 ]T .
The uplink and downlink bandwidth resource constraints (1) and (2) correspond to
N
X
i=1

(bUi )T wi = CUL ,

(22)

13

and
N
X

T
(bD
i ) wi = CDL ,

(23)

i=1

T
respectively, where bUi , [01×M , 1, 01×4 ]T and bD
i , [01×M +2 , 1, 01×2 ] . Similarly, the total

bandwidth constraint (3) is rewritten as
N
X
i=1

(bSi )T wi ≤ CTotal ,

(24)

where bSi , [01×M , 1, 0, 1, 0, 0]T . The constraint (6) used to ensure all variables great than or
equal to 0 is replaced by
wi  0, ∀i.

(25)

Finally, we rewrite the integer constraint (10) as
wiT diag(ej )wi − eTj wi = 0, ∀i, j,

(26)

where ej as the (M + 5) × 1 standard unit vector with the jth entry being 1.

By further defining zi , [wiT , 1]T , together with the above matrix form presentations, and
P PM
l
dropping the constant term N
j=1 Eij from the objective function in (18), problem (11)
i=1
can now be further transformed into the following homogeneous separable QCQP formulation:
min
{zi }

N
X

zTi Gi zi

(27)

i=1

s.t. zTi Gli zi ≤ −

M
X
j=1

Tijl , ∀i,

(28)

zTi Gci zi ≤ 0, ∀i,

(29)

zTi Gµi zi ≤ 0, µ ∈ {u, d}, ∀i,

(30)

N
X

zTi GUi zi

i=1

≤ CUL,

zTi GIj zi = 0, ∀i, j,

N
X

zTi GD
i zi

i=1

≤ CDL ,

N
X
i=1

zTi GSi zi ≤ CTotal ,

zi  0, ∀i,

(32)

where


Gi , 

0
1 T
b
2 i



1
b
2 i

0



, Gµi , 

Aµi
1
(bµi )T
2

(31)



1 µ
b
2 i

0

, µ ∈ {u, d},

14



Gπi , 

0
1
(bπi )T
2



1 π
b
2 i

0



1
diag(ej ) − 2 ej
.
, π ∈ {l, c, U, D, S}, GIj , 
0
− 12 eTj

As problems (11) and (27) are equivalent, all constraints have one-to-one correspondence.
The optimization problem (27) is a non-convex separable QCQP problem [25], which is still
NP-hard in general. To find an approximate solution, we apply the separable SDR approach
[26], where we relax the problem into a separable semidefinite programming (SDP) problem.
Specifically, define Zi , zi zTi . The following equality holds:
zTi Gzi = Tr(GZi ),

(33)

with rank(Zi ) = 1. By dropping the rank constraint rank(Zi ) = 1, we have the following
separable SDP problem:
min
{Zi }

N
X

Tr(Gi Zi )

(34)

i=1

s.t. Tr(Gli Zi ) ≤ −

M
X
j=1

Tijl , ∀i,

(35)

Tr(Gri Zi ) ≤ 0, r ∈ {c, u, d}, ∀i,
N
X
i=1

Tr(GUi Zi )

≤ CUL ,

N
X

Tr(GD
i Zi )

i=1

(36)
≤ CDL ,

N
X
i=1

Tr(GSi Zi ) ≤ CTotal ,

Tr(GIj Zi ) = 0, ∀i, j,
Zi (M + 6, M + 6) = 1, ∀i,

(37)
(38)

Zi  0, ∀i.

(39)

The optimal solution {Z∗i } to the above separable SDP problem can be obtained efficiently in
polynomial time using standard SDP software, such as SeDuMi [40]. However, since problem
(34) is a relaxation of the problem (27), the optimal objective of the problem (34) is only a lower
bound of the optimal solution of the problem (27) if {Z∗i } does not have rank 1. Therefore, once

{Z∗i } is obtained, we still need to recover a rank-1 solution from {Z∗i } for the original problem

(5). In the following, we propose an algorithm to obtain the binary offloading decisions {xij }
and the corresponding optimal communication resource allocation {ri } for problem (5).
3) Binary Offloading Decisions and Resource Allocation: Define the offloading solution
vector as x , [xT1 , . . . , xTN ]T , where xi , [xi1 , . . . , xiM ]T , for all i. Since the rank-1 constraint
has been removed from the relaxed problem (34), the obtained solution Z∗i for problem (34)
contains only real numbers. Our goal is to obtain appropriate offloading decisions from Z∗i by

15

Algorithm 1 MUMTO Algorithm
1: Obtain optimal solution Z∗i ’s of the separable SDP problem (34).
2: Extract Z∗i (M + 6, k), for k = 1, ..., M , from Z∗i .
3: Record the values of Z∗i (M + 6, k), for k = 1, ..., M , as pi = [pi1 , . . . , piM ]T .
4: Set xsdr
ij = round(pij ), ∀i, j.

T
sdr T T
sdr
sdr T
5: Set xsdr = [(xsdr
= [xsdr
1 ) , . . . , (xN ) ] , where xi
i1 , . . . , xiM ] .

6: Solve the resource allocation problem (40) based on xsdr ;
7: Compare the minimum cost of (40) under xsdr with those under the local processing only and cloud processing
∗

only solutions. Select the one that yields the minimum system cost as xsdr .
∗
∗
8: Output: the proposed offloading solution xsdr and the corresponding optimal resource allocation {rsdr
}.
i

mapping its elements to binary numbers. Note that only the first M elements in zi correspond
to the offloading decision variables for user i (see wi in (17)). Also, we have Zi = zi zTi and
zi (M + 6) = 1, which means the last row of Zi satisfies Zi (M + 6, k) = zi (k), for all k.
Hence, we can use the values of Z∗i (M + 6, k) to recover the binary offloading decision zi (k),
for k = 1, ..., M. In addition, it can be shown that Z∗i (M + 6, k) ∈ [0, 1], for k = 1, ..., M.
Define pi , [pi1 , . . . , piM ]T , [Z∗i (M + 6, 1), · · · , Z∗i (M + 6, M)]T . We have pij ∈ [0, 1], ∀i, j.

We recover the feasible decisions xsdr
using pi , where xsdr
i
ij = round(pij ) is the rounding result,
T
sdr T T
and obtain the overall offloading decision as xsdr = [(xsdr
1 ) , . . . , (xN ) ] .

Once the offloading decision xsdr is obtained, the optimization problem (5) reduces to the
optimization of communication resource allocation {ri }, which is given by


N
X
C(U )
min
ρi max{TLi , Ti }
E+
{ri }

(40)

i=1

s.t. (1), (2), (3), and (6),
where E ,

PN PM
i=1

l
j=1 (Eij (1

− xij ) + EijC xij ) is a constant value once {xij } are given. This

resource allocation problem (40) is convex, which can be solved optimally using standard convex
optimization solvers. Note that to obtain the best offloading decision, in practice, we should
compare xsdr with local processing only and cloud processing only decisions, and select the
one resulting in the minimum total system cost objective of (40) as the final offloading decision
∗

xsdr .
We summarize MUMTO in Algorithm 1. Notice that the SDP problem (34) can be solved
√
within precision ǫ by the interior point method in O( MN log(1/ǫ)) iterations, where the amount
of work per iteration is O(M 6 N 4 ) [41], while there are 2M N choices in exhaustive search to
find the optimal offloading decision. In addition, once the offloading decision is made, we may

16

schedule the multiple tasks to be offloaded in any arbitrary order. The resultant TiC will be less
C(U )

than Ti

. To measure the effectiveness of this solution, in the following, we introduce a lower

bound of the optimal solution to the original problem (5).
D. Lower Bound on the Optimal Solution
Previously, the cost function in our original optimization problem (5) considers the worst-case
transmission-plus-processing delay (8) for all users. Once the offloading decision is made, we
may schedule the multiple tasks to be offloaded in any arbitrary order. The resultant TiC will be
C(U )

less than Ti

. Therefore, the actual cost based on MUMTO will be lower than the worst-case

cost.
However, we are still interested in the performance of MUMTO compared with an optimal
solution. Therefore, we introduce a lower bound of the optimal solution to the original problem
C(L)

(5). We first introduce a new optimization problem, where Ti

are used instead of TiC and the

objective function is replaced by its lower bound, as follows:

N X
M
X
l
C
L
u
d
uac
dac
c′
min
(Eij (1 − xij ) + Eij xij ) + ρi max{Ti , Ti , Ti , Ti , Ti , Ti }
{xij },{ri }

i=1

(41)

j=1

s.t. (1), (2), (3), (6), and (7).
Notice that under the same offloading decisions and communication resource allocation, this new
objective function will always give us a lower cost than the real cost.
Since the above optimization problem (41) is still non-convex, we formulate a separable SDR
problem similar to (34), whose details are omitted due to page limitation. We note that the
optimal objective of this SDR problem is smaller than the optimal objective of (41). Hence, it
can serve as a lower bound of the minimum total system cost defined by the original optimization
problem (5). In Section VI-B, we show that MUMTO provides nearly optimal performance under
a wide range of parameter settings.
V. M ULTI - USER M ULTI - TASK O FFLOADING

WITH

CAP

When we consider the presence of a CAP, it may serve its conventional networking function
and forward the task to the remote cloud server, or directly process the task by itself. Each task
may be processed locally at the mobile device, at the CAP, or at the remote cloud server. An
optimal offloading decision must take into consideration the computation and communication

17

energies, computation costs, and communication and processing delays at all three locations.
In this section, we further study the mobile cloud computing network with the presence of the
CAP, aiming to jointly optimize the task offloading decisions and the communication and CAP
processing resource allocation.
A. Offloading Decision
Each mobile user can process its tasks locally or offload some of them. With the presence
of a CAP, those offloaded tasks may be processed at the CAP or be further forwarded to the
remote cloud. Instead of only using xij , we denote the offloading decisions for user i’s task j
by xlij , xaij , xcij ∈ {0, 1}, indicating whether user i’s task j is processed locally, at the CAP, or at
the cloud, respectively. The offloading decisions are constrained by
xlij + xaij + xcij = 1.

(42)

Notice that only one of xlij , xaij , and xcij for user i’s task j could be 1.
B. Problem Formulation
The new total system cost is defined as the weighted sum of total energy consumption, the
costs to offload and process all tasks, and the transmission and processing delays for all users.
Define offloading decision vector xij , [xlij , xaij , xcij ]T . With a CAP, both communication and
CAP processing resources needs to be considered, defined by ri , [cui , cdi , fia ]T . Similar to
Section IV-B, our objective is to minimize the total system cost by jointly optimizing the task
offloading decisions {xij } and the communication and CAP processing resource allocation {ri }.
This optimization problem is formulated as follows:

N X
M
X
l l
A a
C c
L
A
C
min
(Eij xij + Eij xij + Eij xij ) + ρi max{Ti , Ti , Ti }
{xij },{ri }

i=1

(43)

j=1

s.t. (1), (2), (3), (4), (42),
cui , cdi , fia , ≥ 0, ∀i,

(44)

xlij , xaij , xcij ∈ {0, 1}, ∀i, j,

(45)

where EijA , (Eijt + Eijr + αCija ) and EijC , (Eijt + Eijr + βCijc ) are the weighted transmission
energy and processing costs of offloading and processing task j of user i to the CAP and cloud,
with α and β being their relative weights, respectively; also, TiL is the processing delay of

18

tasks processed by the mobile user i itself, TiA and TiC are the overall transmission and remoteprocessing delays for the tasks of mobile user i processed at the CAP and cloud, respectively,
and ρi is the weight on the task processing delay relative to energy consumption for user i.
Comparing with the optimization problem (5) in the no-CAP case, the above mixed-integer
programming problem (43) is even more complicated due to the additional CAP processing
cost, EijA , CAP processing delay, TiA , and the placement constraint (42).
For optimization problem (43), we have the overall local processing delay for each user as
P
l l
TiL = M
j=1 Tij xij , for all i. However, as similarly discussed in problem (5), the overall delay for

CAP processing, TiA , and for cloud processing, TiC , are not precisely tractable due to multiple
offloaded tasks may have overlapping transmission or processing time. Therefore, we use both
upper and lower bounds of TiA and TiC in our proposed solution and performance benchmarking.

We will show later that, with the proposed MUMTO-C algorithm, the upper and lower bounds
give estimates to the total system cost that are close to each other.
C. Multi-user Multi-task Offloading with CAP (MUMTO-C) Algorithm
To find an efficient solution to the mixed-integer non-convex programming problem (43), in
the following, we first propose upper-bound and lower-bound formulations of both TiA and TiC ,
then transform the optimization problem (43) into a separable QCQP and the corresponding
SDR problem. Finally, we will propose a three-step MUMTO-C algorithm to obtain the binary
offloading decisions {xij } and the communication and processing resource allocation {ri }.
1) Bounds of CAP-Processing and Cloud-Processing Delays: Similar to Section IV-C1, we
have the following upper bounds, i.e., the worst-case delays:
A(U )

Ti

M
X

((Tijt + Tijr )(xaij + xcij ) + Tija xaij ),

(46)

((Tijt + Tijr )(xaij + xcij ) + (Tijac + Tijc )xcij ).

(47)

=

j=1

C
Ti (U )

=

M
X
j=1

A(U )

In the above expressions, Ti

C(U )

and Ti

represent the direct summing of the transmission

delays and processing delays without any overlap. They are always greater than the actual delay
given the same offloading decision and resource allocation.

19

For performance benchmarking, we will also need the best-case delays. By separating the
offloading delays of all mobile users into several components and only considering the largest
one among them, the lower bounds of TiA and TiC are
A(L)

Ti
C(L)

Ti
′

where Tiu =

PM

′

′

′

′

= max{Tiu , Tid , Tia },

(48)
′

= max{Tiu , Tid , Tiuac , Tidac , Tic },

t a
d
j=1 Tij xij and Ti =

PM

r a
j=1 Tij xij

(49)

are the total uplink and downlink transmission

times between the user and the CAP for user i’s tasks processed at the CAP, respectively,
PM r c
PM t c
d
Tiu =
j=1 Tij xij are the total uplink and downlink transmission
j=1 Tij xij and Ti =

times between the user and the CAP for user i’s tasks processed at the cloud, respectively,
P
P
c
ac
c
ac
Tiuac = M
and Tidac = M
are the total uplink and downlink
j=1 Din (ij)xij /r
j=1 Dout (ij)xij /r
P
′
a a
transmission times between the CAP and the cloud for user i, respectively, and Tia = M
j=1 Tij xij
P
′
c c
and Tic = M
j=1 Tij xij are the total CAP and cloud processing times for user i, respectively.
In the following subsections, we describe the details of the proposed three-step MUMTO-C
A(U )

algorithm, using the worst-case delays Ti

C(U )

and Ti

in optimization problem (43) to obtain an

approximate solution, which gives an upper bound to the actual total system cost. Furthermore,
we show the local optimum property of the obtained binary offloading decisions {xij } and
A(L)

communication and processing resource allocation {ri }. Similarly, Ti

C(L)

and Ti

are used to

obtain a lower bound of the total system cost for performance benchmarking. Finally, we show
in Section VI-C that MUMTO-C achieve actual system cost that is close to the lower bound of
the system cost, and hence is also close to the optimal system cost.
2) Step 1: QCQP Transformation and Semidefinite Relaxation: As mentioned before,
optimization problem (43) is more complicated than problem (5) due to the availability of the
CAP. In order to obtain the eventual SDR formulation, we first rewrite the integer constraint
(45) as
xsij (xsij − 1) = 0,

∀i, j,
A(U )

for s ∈ {l, a, c}, and replace TiA and TiC in (43) with Ti

(50)
C(U )

and Ti

, respectively. Following the

similar procedure in Section IV-C2, we move the delay term from the objective to the constraints
by using additional auxiliary variables ti , and rewrite (43) as

N X
M
X
l l
A a
C c
min
(Eij xij + Eij xij + Eij xij ) + ρi ti
{xij },{ri ,ti }

i=1

j=1

(51)

20

s.t.

M
X
j=1

Tijl xlij ≤ ti , ∀i,

M 
X
Din (ij)
j=1

M 
X
j=1

Dout (ij)
+
ηid cdi



(xaij + xcij ) +

Din (ij) Dout (ij)
+
ηiu cui
ηid cdi



(xaij

ηiu cui

M
X
Y (ij)
j=1

+

xcij )

+

M
X
j=1

fia

xaij ≤ ti , ∀i,

(Tijac + Tijc )xcij ≤ ti , ∀i,

(1), (2), (3), (4), (42), (44), and (50).
Comparing problem (51) with problem (11), we observe that they share a similar structure.
Therefore, we can apply a similar procedure to transform problem (51) into a non-convex
separable QCQP problem that is similar to problem (27), with the optimization vector now
defined by vi , [w̃iT , 1]T , where w̃i , [xTi1 , · · · , xTiM , cui , Diu , cdi , Did , fia , Dia , ti ]T , with Diu , Did

and Dia being the auxiliary variables introduced corresponding to the uplink transmission time,
downlink transmission time, and the CAP processing time, respectively. Auxiliary variables Diu

and Did are similarly defined as in (15) and (16), except that xij in (15) and (16) is now replaced
by (xaij + xcij ). Similar to these two constraints, the new auxiliary variable Dia for the CAP
P
a
a
a
processing time also introduces a new constraint M
j=1 Y (ij)xij /fi ≤ Di . Using the separable
SDR approach, we solve the relaxed separable SDP problem that is similar to problem (34),
with optimization matrix defined by Vi = vi viT with size (3M + 8) × (3M + 8). The details are
omitted to avoid redundancy.
Denote {Vi∗ } as the optimal solution of the corresponding separable SDR problem for the

optimization problem (51). We need to recover a rank-one solution from {Vi∗} for problem (51).

However, the reconstruction of binary offloading decision {xij } in Section IV-C3, as part of the
MUMTO algorithm, cannot be directly applied to find a feasible solution for problem (51) due
to the additional placement constraint (42) for each user’s tasks. To deal with this challenge,
in the following, we propose an modified method, termed MUMTO SDR with CAP (SDR-C),
to obtain the binary offloading decisions {xij } and the corresponding optimal communication
resource allocation {ri } from {Vi∗ }.

Define x , [xT1 , . . . , xTN ]T , where xi , [xi1 , . . . , xiM ]T , for all i. As similarly discussed in Sec-

tion IV-C3, Vi (3M +8, k) = vi (k), for k = 1, · · · , 3M, which correspond to offloading decision
xi for user i. It can be proven that optimal solution Vi∗ (3M + 8, k) ∈ [0, 1], for k = 1, ..., 3M.

Denote pij , [plij , paij , pcij ]T and pi , [pTi1 , . . . , pTiM ]T , [Vi∗ (3M +8, 1), · · · , Vi∗(3M +8, 3M)]T .

21

Then, we have each element in pi having its value within [0, 1], ∀i. We recover the feasible
decisions xsdr
i using pi as follows: for j = 1, · · · , M, set



[1, 0, 0]T, if max psij = plij (local processing)


s∈{l,a,c}

T
xsdr
=
[0, 1, 0] , if max psij = paij (CAP processing)
ij

s∈{l,a,c}



[0, 0, 1]T, if max ps = pc (cloud processing),
ij
ij

(52)

s∈{l,a,c}

T
sdr T T
The overall offloading decision is obtained as xsdr = [(xsdr
1 ) , . . . , (xN ) ] .

After obtaining the offloading decision xsdr , optimization problem (43) is reduced to the
optimization of computation and communication resource allocation {ri }, which is given by


N
X
A(U )
C(U )
L
min
ρi max{Ti , Ti , Ti }
E+
(53)
{ri }

i=1

s.t. (1), (2), (3), (4), and (44),
where E ,

PN PM
i=1

l l
j=1 (Eij xij

+ EijA xaij + EijC xcij ) is a constant value once {xij } are given.

Similar to problem (40), problem (53) is convex, so it can be solved optimally.
3) Step 2: Improvement to SDR-C by Alternating Optimization (AO): After obtaining a
∗

feasible solution {xsdr , {rsdr
i }} from the SDR-C step above, to further reduce the overall system
cost, in the following we introduce an iterative alternating optimization method to further improve
∗

the offloading decision, by using {xsdr , {rsdr
i }} as the starting point of iteration.
As mentioned above, given any offloading decision, the optimization problem (43) is reduced
to the resource allocation problem (53), which is convex and the optimal resource allocation
can be obtained. On the other hand, once the resource allocation {ri } is given, the optimization
problem (43) is reduced to the optimization of offloading decisions {xij } as follows:

N X
M
X
A(U )
C(U )
l l
A a
C c
L
min
(Eij xij + Eij xij + Eij xij ) + ρi max{Ti , Ti , Ti }
{xij }

i=1

(54)

j=1

s.t. (42) and (50).
The offloading decision problem (54) is an integer programming problem. However, it can
be separated into N independent sub-problems, where each sub-problem only considers the
offloading decision of one user. As shown in [36], this can be solved near-optimally by either
using an SDR approach or relaxing the integer constraints to interval constraints. Since the
optimization problem (43) can be separated into two sub-problems (53) and (54). We propose
the following alternating optimization procedure to further reduce the total system cost.

22

∗

∗

∗

sdr
sdr
Set (xao , {rao
i }) = (x , {ri }) as the initial point. At each iteration:
∗

′

ao
i) Solve problem (54) based on {rao
i } to find the corresponding offloading decision x .
′

ii) Solve problem (53) based on xao to find the minimum system cost and the corresponding
′

∗

∗

ao
resource allocation {rao
, {rao
i }. If this provides a lower total system cost, update (x
i }) =
′

′

(xao , {rao
i }).

Repeat steps i and ii until the the total system cost cannot be further decreased. Then output the
∗

∗

solution of the alternating optimization procedure as (xao , {rao
i }).
Note that, despite the approximation in solving (54), since we only accept a better solution
in each iteration, and the system cost is lower bounded, AO always converges. Furthermore, by
∗

∗

∗

sdr
sdr
design, the solution (xao , {rao
i }) is better than or at least as good as (x , {ri }).

4) Step 3: Sequential Tuning (ST) to Reach Local Optimum: In this step, we propose an
∗

∗

iterative procedure starting from {xao , {rao
i }}, termed sequential tuning, to further reduce the
system cost and eventually achieve a local optimum for (43).
∗

∗

∗

∗

Set (xst , {rsti }) = (xao , {rao
i }) as the initial point. At each iteration:
i) Randomly order the lists of all users and their tasks.
ii) Go through the user list one by one. For each examined user, sequentially check each of its
tasks for the three possible offloading decisions, while the offloading decisions of all other
tasks of all users remain unchanged. For each offloading decision, find the total system
cost by solving problem (53). As soon as some user i is found to admit a lower total
∗

∗

system cost by changing the offloading decision of one of its tasks, update (xst , {rsti })
to the new offloading decision and resource allocation that give the lower cost, and exit
the iteration.
∗

∗

Repeat steps i and ii until xst converges, i.e., no change for xst can be made. Then output the
∗

∗

solution of the sequential turning procedure as (xst , {rsti }).
The above procedure is guaranteed to converge. This is because there is a finite number
∗

∗

of possible values for xsti . The iteration eventually will reach some (xst , {rsti }), where the
total system cost cannot be further reduced by modifying any user’s offloading decision (and
∗

∗

corresponding resource allocation). It is straightforward to show that (xst , {rsti }) is a local
optimum of problem (43), since it gives the lowest system cost in the joint binary-valued
neighborhood of x and neighborhood of {ri }. This result is stated in the following proposition.
∗

∗

Proposition 1: The solution (xst , {rsti }) obtained from the sequential tuning procedure is a

locally optimal solution to the original non-convex optimization problem (43).

23

Algorithm 2 MUMTO-C Algorithm
Step 1: Initial offloading solution via SDR-C
1: Transform the original problem (43) into the SDR problem and obtain the optimal solution {Vi∗ }.
2: Extract Vi∗ (3M + 8, k), for k = 1, ..., 3M , from Vi∗ .
T T
l
a
c T
3: Record the values of Vi∗ (3M + 8, k), for k = 1, ..., 3M , by pi = [pT
i1 , . . . , piM ] , where pij = [pij , pij , pij ] .
T
sdr T T
sdr
sdr
4: Set xsdr = [(xsdr
1 ) , . . . , (xN ) ] , where xi is given by (52), and solve problem (53) based on x .

Step 2: Alternating optimization (AO)
∗

∗

∗

∗

sdr
sdr
ao
5: Set (xao , {rao
; set AO = False.
i }) = (x , {ri }), and record the corresponding total system cost as J

6: while AO == False do
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:

∗

′

ao
Solve problem (54) based on {rao
i } to find the corresponding offloading decision x ;
′
′
′
Solve problem (53) based on xao to find the minimum system cost J ao and {rao
i };
′
∗
if J ao < J ao then
∗
∗
′
ao′
ao′
ao∗
Set (xao , {rao
= J ao ;
i }) = (x , {ri }), J
else
Set AO = True;
⊲ Exit while loop
end if
end while
Step 3: Sequential tuning (ST)
∗
∗
∗
∗
st∗
Set (xst , {rsti }) = (xao , {rao
i }), and record the corresponding total system cost as J ; set ST = False.
while ST == False do
Randomly order the lists of all users and their tasks; set user index n = 1; set task index m = 1;
while n ≤ N and m ≤ M do
∗
While keeping xstn′ m′ unchanged for all (n′ , m′ ) except (n′ , m′ ) = (n, m), inspect the three possible
′
st∗
offloading choices of xnm
; find their respective total system costs by solving problem (53); set J st as
′
′
the minimum cost among these three choices, and record the corresponding solution as (xst , {rst
i });
′
∗
if J st < J st then
∗
∗
′
′
∗
′
Set (xst , {rsti }) = (xst , {rsti }), J st = J st ; n ← N + 1;
else if n == N and m == M then
∗
n ← N + 1; ST = True;
⊲ No change of xst can be found; exit
else if n < N and m == M then
n ← n + 1; m ← 1;
else
m ← m + 1;
end if
end while
end while
∗
∗
Output: The offloading decision xst and the corresponding resource allocation {rsti }.

5) Overall MUMTO-C Algorithm: We summarize the above three-step MUMTO-C algorithm
in Algorithm 2.
Even though each of the SDR-C, AO, and ST steps above can be used separately to provide
a feasible solution to the original optimization problem (43), when combined together in the
proposed manner, they each serves an important role in the overall algorithm design. First,

24

SDR-C provides a suitable starting point for AO. Without it, i.e., if we start the AO iteration
from some randomly chosen point in the solution space, as shown in Section VI-C, AO can
converge to some highly sub-optimal solution. Second, with an appropriate starting point, AO
pushes the solution to one that is closer to the optimum. This provide a suitable starting point
for ST, which helps reduce the number of iterations in ST. This is an important step, since each
of the ST iterations can be computationally expensive, as it potentially may require searching
over a large number of tasks. Finally, ST further improves the solution, and more importantly, it
guarantees that the final solution is a local optimum. Further numerical evaluation of the roles
and contributions of each of these steps is given in Section VI-C.
D. Lower Bound on the Optimal Solution
Similar to the case of MUMTO in Section IV-D, to study the performance of MUMTO-C
compared with an optimal solution, we find a lower bound of the optimal solution by introducing
A(L)

a new optimization problem in which Ti

min

{xij },{ri }

N X
M
X
i=1

(Eijl xlij

+

EijA xaij

C(L)

and Ti

+

EijC xcij )

j=1

are used instead as

+

A
C
ρi max{TiL , Ti (L) , Ti (L) }



(55)

s.t. (1), (2), (3), (4), (42), (44), and (50).
Under the same offloading decisions and resource allocation, the objective function in (55) is
always lower than the actual cost. We apply the same approach to solve the corresponding
separable SDR problem of the above non-convex problem (55). Since the optimal objective of
this SDR problem is smaller than the optimal objective of (55), it can serve as a lower bound
to the minimum total system cost defined by the original optimization problem (43).
In Section VI, we show that the proposed MUMTO-C method provides not only a local
optimum solution but also nearly optimal performance compared with the lower bound.
VI. P ERFORMANCE E VALUATION
In this section, we provide computer simulation to study the performance of both proposed
MUMTO and MUMTO-C offloading solutions, respectively, under different parameter settings.
A. Simulation Setup
The following default parameter values are used unless specified otherwise later. We adopt
the mobile device characteristics from [42], which is based on a Nokia smart device, and set the

25
5000
MUMTO-C
random mapping
local processing
cloud processing
lower bound of local-cloud
lower bound of optimum

total cost (J)

4000
3500

local processing
cloud processing
MUMTO
lower bound of optimum

3200

3000
totsl cost (J)

4500

3000
2500

2800

2600

2000
2400
1500
1000
1

1.5

2

2.5

3
β (J/bit)

3.5

4

4.5

5
×10

2200
0.5

Fig. 2: Total system cost versus β without
CAP.

1
C

-7

f (cycle/sec)

1.5
×10

10

Fig. 3: Total system cost versus cloud CPU rate f c
without CAP.

number of mobile users as N = 5. Each user has M = 4 independent tasks. According to Tables
1 and 3 in [42], the mobile device has CPU rate 500 × 106 cycles/s and unit processing energy
consumption

1
730×106

J/cycle. The local computation time per bit is 4.75 × 10−7 s and local

processing energy consumption per bit is 3.25 × 10−7 J. We consider the x264 CBR encode
application, which requires 1900 cycles/byte [42], i.e., Y (ij) = 1900Din(ij). The input and
output data sizes of each task are assumed to be uniformly distributed from 10 to 30MB and
from 1 to 3MB, respectively.
The total transmission bandwidth between the mobile users and the CAP is set to 40 MHz,
with no additional limit on the uplink or downlink, and the transmission and receiving energy
consumptions of the mobile user are both 1.42 × 10−7 J/bit as indicated in Table 2 in [42]. For

simplicity, we set ηiu = ηid = 3.5 b/s/Hz for all i. The CPU rate assigned to each user at the
remote cloud is 10 × 109 cycle/s, and the total CAP processing rate fA is 10 × 109 cycle/s.

When tasks are sent from the CAP to the cloud, the transmission rate r ac is 15 Mpbs. The
cloud and CAP usage costs are assumed to be Cijc = Din (ij) + λ1 /f c + λ2 /CUL + λ3 /CDL and
Cija = Din (ij) + λ1 /fA + λ2 /CUL + λ3 /CDL , respectively, where λ1 = 1018 bits×cycles/s and

λ2 = λ3 = 1016 bits×MHz, which accounts for the input data size, processing rate, and uplink
and downlink capacities. Also, β = 2.5 × 10−7 J/bit, α = 1.5 × 10−7 J/bit, and ρi = ρ = 1 J/s
for all i. Finally, all simulation results are obtained by averaging over 100 realizations of the
input and output data sizes of each task.

26

3600

7000
local processing
cloud processing
MUMTO
lower bound of optimum

3400
6000

3200

totsl cost (J)

totsl cost (J)

3000
2800
2600

5000

4000

2400
local processing
cloud processing
MUMTO
lower bound of optimum

2200
2000
1800
0.5

3000

2000
1
ρ (J/sec)

1.5

Fig. 4: Total system cost versus ρ (ρi = ρ)
without CAP.

4

5

6
7
8
number of tasks per user

9

10

Fig. 5: Total system cost versus number of tasks per user
without CAP.

B. Performance Evaluation for MUMTO without CAP
For comparison, we also consider the following methods: 1) the local processing only scheme
where all tasks are processed by mobile users, 2) the cloud processing only scheme where all
C(L)

tasks are offloaded to the cloud and the cost is obtained based on Ti

, 3) the lower bound

of optimum, which is obtained from the optimal objective value of the SDR of problem (41).
Notice that in all figures the real cost under the same offloading decision and resource allocation
will always between the costs of the proposed MUMTO and the lower bound of optimum.
In Fig. 2, we show the system cost vs. the weight β on the system utility cost. When β becomes
large, all tasks are more likely to be processed by mobile users themselves. Both MUMTO and
the lower bound of optimum in this case converge to the local processing only method. Though
the existence of the cloud can provide additional computation capacity, the processing time at
the cloud depends on the cloud CPU rate f c assigned to each user. In Fig. 3, we plot the total
system cost vs. f c . As expected, a more powerful per-user cloud CPU can dramatically increase
system performance, and MUMTO coverages to the local processing only method when the
per-user cloud CPU rate is too slow to help.
In Fig. 4, we study the system cost under various values of weight ρi = ρ on the delays.
We observe that MUMTO substantially outperforms all other methods. Finally, we examine the
scalability of MUMTO. Fig. 5 plot the total system cost vs. the number of tasks M per user. We
see that MUMTO is close to the lower bound of optimum, indicating that it is nearly optimal
for all M values.

27
7

2600
2400

ST/MUMTO-C
AO-ST/MUMTO-C
SDR-C-ST/MUMTO-C

6

run time ratio

total cost (J)

2200
2000
1800
SDR-C
SDR-C-ST
MUMTO-C
ST
AO-ST
lower bound of optimum

1600
1400

5

4

3

2

1200

1
1

1.5

2
α (J/bit)

2.5

3
×10

1

1.5

2
α (J/bit)

-7

Fig. 6: Total system cost versus α with CAP.

2.5

3
×10

-7

Fig. 7: Run time ratio versus α with CAP.

9

3000
SDR-C
SDR-C-ST
MUMTO-C
ST
AO-ST
lower bound of optimum

7
run time ratio

total cost (J)

2500

ST/MUMTO-C
AO-ST/MUMTO-C
SDR-C-ST/MUMTO-C

8

6
5
4
3

2000

2
1
1500

0
1

1.5

2

2.5

3
β (J/bit)

3.5

4

4.5

5
×10

1

-7

Fig. 8: Total system cost versus β with CAP.

1.5

2

2.5

3
β (J/bit)

3.5

4

4.5

5
×10

-7

Fig. 9: Run time ratio versus β with CAP.

C. Performance Evaluation for MUMTO-C with CAP
1) Contribution of the Algorithm Components: To demonstrate the role and contribution of
each step in the MUMTO-C algorithm, we first compare it with the following methods: 1) the
SDR-C method where only the first step of MUMTO-C is applied, 2) the SDR-C-ST method
where the AO step is skipped, 3) the AO-ST method where only the last two steps of MUMTOC are applied by using random offloading decisions for all tasks as the starting point for the
iterations of AO, 4) the ST method where only the last step of MUMTO-C is applied by using
random offloading decisions for all tasks as the starting point for the iterations of ST, and 5) the
lower bound of optimum, which is obtained from the optimal objective value of the SDR lower
bound of problem (55).
We show the system cost and the run time ratio vs. α in Figs. 6 and 7, respectively. Since
α is the weight on the CAP usage cost, more tasks compete at the CAP when α is smaller.
We observe that MUMTO-C can reduce the system cost by up to 20% compared with purely

28

6000

12
SDR-C
SDR-C-ST
MUMTO-C
ST
AO-ST
lower bound of optimum

5000

total cost (J)

4500

ST/MUMTO-C
AO-ST/MUMTO-C
SDR-C-ST/MUMTO-C

10

8
run time ratio

5500

4000
3500
3000

6

4

2500
2
2000
1500

0
4

5

6
7
8
number of tasks per user

9

10

Fig. 10: Total system cost versus number
of tasks per user with CAP.

4

5

6
7
8
number of tasks per user

9

10

Fig. 11: Run time ratio versus number of tasks per user
with CAP.

applying SDR-C and is much closer to the lower bound of optimum with CAP. Furthermore,
though SDR-C-ST, AO-ST, and ST can provide similarly low cost as MUMTO-C, which can
be attributed to the sequential searching of ST, they require much longer run time to obtain
their solutions. This demonstrates that we require both the SDR-C and AO steps in the proposed
algorithm to provide an effective starting point for the ST step to reach a local minimum solution
quickly.
Similar observations can be made in Figs. 8 and 9, where we show the system cost and the
run time ratio vs. the weight β on the cloud usage cost, and in Figs. 10 and 11, where we show
the system cost and the run time ratio vs. M, the number of tasks per user. When β is large, all
tasks are more likely to be processed by either the mobile users or the CAP. More importantly,
MUMTO-C is shown to be more scalable, since the run-time ratios are nearly linearly increasing
with the number of tasks per user.
2) Comparison with Further Alternatives: For further performance evaluation, we also
consider the following schemes: 1) the local processing only scheme, 2) the cloud processing
only scheme, 3) the lower bound of local-cloud, which is the same as lower bound of optimum
defined in Sec. VI-B, and 4) the random mapping scheme where each task is processed at different
locations with equal probability. As shown in Figs. 12 and 13, the lower bound of optimum with
CAP converges to the lower bound of local-cloud as α becomes large and the lower bound of
local-cloud converges to the local only method as β becomes large. In both figures, MUMTO-C
is near-optimal and substantially outperforms all alternatives especially when the cost of using
the CAP is small or the cost of using the cloud is large.

29
5000

3000

MUMTO-C
random mapping
local processing
cloud processing
lower bound of local-cloud
lower bound of optimum

4500
4000
total cost (J)

total cost (J)

2500

2000
MUMTO-C
random mapping
local processing
cloud processing
lower bound of local-cloud
lower bound of optimum

1500

3500
3000
2500
2000
1500

1000

1000
1

1.5

2
α (J/bit)

2.5

3
×10

1

1.5

2

2.5

-7

Fig. 12: Total system cost versus α with CAP.

3
β (J/bit)

3.5

4

4.5

5
×10

-7

Fig. 13: Total system cost versus β with CAP.

VII. C ONCLUSION
A general mobile cloud computing system consisting of multiple users and one remote cloud
server has been considered, in which each user has multiple independent tasks. To minimize a
weighted total cost of energy, computation, and the delay of all users, we aim to find the overall
optimal tasks offloading decisions and communication resource allocation. We show that the resultant optimization problem is a non-convex separable QCQP. The proposed MUMTO algorithm
uses SDR and binary recovery to jointly compute the offloading decision and communication
resource allocation. For the scenario with the presence of a CAP, the resultant optimization
problem is even more complicated. We further propose a three-step MUMTO-C algorithm,
which always compute a locally optimal solution. By comparison with a lower bound of the
minimum cost for both scenarios, we show that both MUMTO and MUMTO-C give nearly
optimal performance and can substantially out perform existing alternatives over a wide range
of parameter settings.
R EFERENCES
[1] M.-H. Chen, B. Liang, and M. Dong, “Joint offloading decision and resource allocation for multi-user multi-task mobile
cloud,” in Proc. IEEE Int. Conf. Communications (ICC), May 2016.
[2] ——, “Joint offloading and resource allocation for computation and communication in mobile cloud with computing access
point,” in Proc. IEEE Conf. on Computer Communications (INFOCOM), May 2017.
[3] K. Kumar, J. Liu, Y.-H. Lu, and B. Bhargava, “A survey of computation offloading for mobile systems,” Mobile Netw.
Appl., vol. 18, no. 1, pp. 129–140, Feb. 2013.
[4] H. T. Dinh, C. Lee, D. Niyato, and P. Wang, “A survey of mobile cloud computing: architecture, applications, and
approaches,” Wireless Commun. Mobile Comput., vol. 13, no. 18, pp. 1587–1611, 2013.
[5] K. Kumar and Y.-H. Lu, “Cloud computing for mobile users: Can offloading computation save energy?” Computer, vol. 43,
no. 4, pp. 51–56, Apr. 2010.
[6] Y. Wen, W. Zhang, and H. Luo, “Energy-optimal mobile application execution: Taming resource-poor mobile devices with
cloud clones,” in Proc. IEEE Conf. on Computer Communications (INFOCOM), Mar. 2012, pp. 2716–2720.

30

[7] X. Chen, “Decentralized computation offloading game for mobile cloud computing,” IEEE Trans. Parallel Distrib. Syst.,
vol. 26, no. 4, pp. 974–983, Apr. 2015.
[8] S. Ren and M. van der Schaar, “Efficient resource provisioning and rate selection for stream mining in a community
cloud,” IEEE Trans. Multimedia, vol. 15, no. 4, pp. 723–734, Jun. 2013.
[9] E. Meskar, T. D. Todd, D. Zhao, and G. Karakostas, “Energy aware offloading for competing users on a shared
communication channel,” IEEE Trans. Mobile Comput., vol. 16, no. 1, pp. 87–96, Jan. 2017.
[10] E. Cuervo, A. Balasubramanian, D.-k. Cho, A. Wolman, S. Saroiu, R. Chandra, and P. Bahl, “MAUI: Making smartphones
last longer with code offload,” in Proc. ACM Int. Conf. on Mobile Systems, Applications, and Services (MobiSys), Jan.
2010, pp. 49–62.
[11] B.-G. Chun, S. Ihm, P. Maniatis, M. Naik, and A. Patti, “Clonecloud: Elastic execution between mobile device and cloud,”
in Proc. ACM Conf. on Computer Systems (EuroSys), Apr. 2011, pp. 301–314.
[12] S. Kosta, A. Aucinas, P. Hui, R. Mortier, and X. Zhang, “Thinkair: Dynamic resource allocation and parallel execution in
the cloud for mobile code offloading,” in Proc. IEEE Conf. on Computer Communications (INFOCOM), Mar. 2012, pp.
945–953.
[13] W. Zhang, Y. Wen, and D. O. Wu, “Energy-efficient scheduling policy for collaborative execution in mobile cloud
computing,” in Proc. IEEE Conf. on Computer Communications (INFOCOM), Apr. 2013, pp. 190–194.
[14] Y. H. Kao, B. Krishnamachari, M. R. Ra, and F. Bai, “Hermes: Latency optimal task assignment for resource-constrained
mobile computing,” in Proc. IEEE Conf. on Computer Communications (INFOCOM), Apr. 2015, pp. 1894–1902.
[15] S. E. Mahmoodi, R. N. Uma, and K. P. Subbalakshmi, “Optimal joint scheduling and cloud offloading for mobile
applications,” IEEE Trans. Cloud Comput., Apr. 2016.
[16] H. Wu, W. Knottenbelt, K. Wolter, and Y. Sun, “An optimal offloading partitioning algorithm in mobile cloud computing,”
in Proc. Int. Conf. on Quantitative Evaluation of Systems, Aug. 2016, pp. 311–328.
[17] ETSI Group Specification, “Mobile edge computing (MEC); framework and reference architecture,” ETSI GS MEC 003
V1.1.1, 2016.
[18] B. Liang, “Mobile edge computing,” in Key Technologies for 5G Wireless Systems, V. W. S. Wong, R. Schober, D. W. K.
Ng, and L.-C. Wang, Eds., Cambridge University Press, 2017.
[19] Y. Mao, C. You, J. Zhang, K. Huang, and K. B. Letaief, “A survey on mobile edge computing: The communication
perspective,” IEEE Commun. Surveys Tuts., vol. PP, no. 99, pp. 1–1, 2017.
[20] A. Greenberg, J. Hamilton, D. A. Maltz, and P. Patel, “The cost of a cloud: Research problems in data center networks,”
ACM SIGCOMM Comput. Commun. Rev., vol. 39, no. 1, pp. 68–73, Dec. 2008.
[21] M. Satyanarayanan, P. Bahl, R. Caceres, and N. Davies, “The case for VM-based cloudlets in mobile computing,” IEEE
Pervasive Comput., vol. 8, no. 4, pp. 14–23, Oct. 2009.
[22] F. Bonomi, R. Milito, J. Zhu, and S. Addepalli, “Fog computing and its role in the internet of things,” in Proc. ACM
SIGCOMM Workshop on Mobile Cloud Comput., Aug. 2012, pp. 13–16.
[23] G. Lewis and P. Lago, “Architectural tactics for cyber-foraging: Results of a systematic literature review,” J. Syst. Softw.,
vol. 107, pp. 158 – 186, 2015.
[24] M. R. Garey, D. S. Johnson, and R. Sethi, “The complexity of flowshop and jobshop scheduling,” Math. Oper. Res., vol. 1,
no. 2, pp. 117–129, May 1976.
[25] S. Boyd and L. Vandenberghe, Convex Optimization.

Cambridge University Press, 2004.

[26] Z.-Q. Luo, W.-K. Ma, A.-C. So, Y. Ye, and S. Zhang, “Semidefinite relaxation of quadratic optimization problems,” IEEE
Signal Processing Mag., vol. 27, no. 3, pp. 20–34, May 2010.

31

[27] O. Munoz, A. Pascual-Iserte, and J. Vidal, “Optimization of radio and computational resources for energy efficiency in
latency-constrained application offloading,” IEEE Trans. Veh. Technol., vol. 64, no. 10, pp. 4738–4755, Oct. 2015.
[28] R. Kaewpuang, D. Niyato, P. Wang, and E. Hossain, “A framework for cooperative resource management in mobile cloud
computing,” IEEE J. Select. Areas Commun., vol. 31, no. 12, pp. 2685–2700, Dec. 2013.
[29] X. Chen, L. Jiao, W. Li, and X. Fu, “Efficient multi-user computation offloading for mobile-edge cloud computing,”
IEEE/ACM Trans. Netw., vol. 24, no. 5, pp. 2795–2808, Oct 2016.
[30] S. Sardellitti, G. Scutari, and S. Barbarossa, “Joint optimization of radio and computational resources for multicell mobileedge computing,” IEEE Trans. Signal Inf. Process. Netw., vol. 1, no. 2, pp. 89–103, Jun. 2015.
[31] X. Lyu, H. Tian, C. Sengul, and P. Zhang, “Multiuser joint task offloading and resource optimization in proximate clouds,”
IEEE Trans. Veh. Technol., vol. 66, no. 4, pp. 3435–3447, Apr. 2017.
[32] M. R. Rahimi, N. Venkatasubramanian, S. Mehrotra, and A. V. Vasilakos, “Mapcloud: Mobile applications on an elastic
and scalable 2-tier cloud architecture,” in Proc. IEEE/ACM Int. Conf. on Utility and Cloud Comput., Nov. 2012, pp. 83–90.
[33] M. R. Rahimi, N. Venkatasubramanian, and A. V. Vasilakos, “Music: Mobility-aware optimal service allocation in mobile
cloud computing,” in Proc. IEEE Int. Conf. on Cloud Comput., Jun. 2013, pp. 75–82.
[34] J. Song, Y. Cui, M. Li, J. Qiu, and R. Buyya, “Energy-traffic tradeoff cooperative offloading for mobile cloud computing,”
in Proc. IEEE Int. Symposium of Quality of Service (IWQoS), May 2014, pp. 284–289.
[35] V. Cardellini, V. De Nitto Personé, V. Di Valerio, F. Facchinei, V. Grassi, F. Lo Presti, and V. Piccialli, “A game-theoretic
approach to computation offloading in mobile cloud computing,” Math. Prog., vol. 157, no. 2, pp. 421–449, 2016.
[36] M.-H. Chen, B. Liang, and M. Dong, “A semidefinite relaxation approach to mobile cloud offloading with computing
access point,” in Proc. IEEE Int. Workshop on Signal Processing advances in Wireless Commun.(SPAWC), Jun. 2015, pp.
186–190.
[37] M.-H. Chen, M. Dong, and B. Liang, “Resource sharing of a computing access point for multi-user mobile cloud offloading
with delay constraints,” IEEE Trans. Mobile Comput., vol. PP, no. 99, pp. 1-1, 2018.
[38] ——, “Joint offloading decision and resource allocation for mobile cloud with computing access point,” in Proc. IEEE
Int. Conf. Acoustics, Speech, and Signal Processing (ICASSP), Mar. 2016, pp. 3516–3520.
[39] ——, “Multi-user mobile cloud offloading game with computing access point,” in Proc. IEEE Int. Conf. on Cloud
Networking (CLOUDNET), Oct. 2016, pp. 64–69.
[40] M. Grant, S. Boyd, and Y. Ye, “CVX: Matlab software for disciplined convex programming,” 2009. [Online]. Available:
http://cvxr.com/cvx/
[41] Y. Nesterov, A. Nemirovskii, and Y. Ye, Interior-point polynomial algorithms in convex programming.

SIAM, 1994.

[42] A. P. Miettinen and J. K. Nurminen, “Energy efficiency of mobile clients in cloud computing,” in Proc. USENIX Conf. on
Hot Topics in Cloud Comput. (HotCloud), Jun. 2010, pp. 4–11.

