Resource Sharing of a Computing Access Point for Multi-user Mobile Cloud Offloading with Delay Constraints

1 INTRODUCTION

• Mobile cloud offloading must balance energy use, computing performance, and communication delay; MEC places computing resources at or near cellular base stations to reduce communication delay.MEC servers are managed by a mobile service provider, allowing more direct control and resource management.Source: §1 · p. 1
• A CAP is a wireless access point or cellular base station with computation capability, so tasks can be processed locally there or forwarded to the remote cloud.Adding the CAP can potentially reduce communication delay and overall energy and computation cost.Source: §1 · p. 1
• The paper jointly minimizes energy, computation, and maximum-delay costs by optimizing multi-user offloading and communication and computation resources; shareCAP applies SDR and randomization mapping to the resulting NP-hard QCQP.The original formulation is a mixed-integer program.Source: §1 · p. 2
• For strict per-user processing deadlines, shareCAP-D combines SDR, adaptive adjustment, and sequential tuning to obtain a feasible, locally optimal solution.The standard shareCAP method lacks a feasibility guarantee in this setting.Source: §1 · p. 2
• The proposed shareCAP and shareCAP-D methods achieve nearly optimal performance across a wide range of settings, while adding a CAP significantly reduces energy and computation costs versus cloud-only offloading.The comparison uses an optimal offloading policy obtained by exhaustive search.Source: §1 · p. 2

2 RELATED WORK

• Single-user studies examined energy models, task partitioning, heuristics, dependent tasks, intermittent connectivity, and mobility, while implementation-focused systems limited discussion of offloading-decision optimization.These studies focused on a single mobile user.Source: §2 · p. 2
• Earlier multi-user two-tier work studied provider revenue, fixed resource use, always-offloaded tasks, joint utility optimization, or decentralized decisions, but did not cover the full three-tier setting.Some game-theoretic studies omit communication and computation resource allocation.Source: §2 · p. 2
• Prior three-tier studies proposed centralized heuristics or game-theoretic offloading decisions, but did not jointly optimize offloading and communication and computation resource allocation.The interaction between offloading decisions and resource allocation makes the joint problem more complicated.Source: §2 · pp. 2–3
• The paper contrasts its single-task-per-user case with, citing a low-complexity, nearly optimal algorithm and support for strict per-task deadlines that 's approach cannot address.The paper also states that the problem structures and solution approaches differ.Source: §2 · p. 3

3.1.1 Mobile Cloud with CAP

• The CAP is both a wireless gateway and a processor: it can process received tasks or forward them to the cloud, subject to shared resource limits.Multiple users’ tasks require allocation of the CAP’s communication and computation resources.Source: §3.1.1 · p. 3
• Tasks are assumed available at time zero; dynamically arriving tasks may instead be handled in batches over time intervals.The zero-time assumption is described as similar to existing studies.Source: §3.1.1 · p. 3

3.1.2 Offloading Decision

• Each user’s task is assigned to local, CAP, or cloud processing through offloading decisions, with only one processing location selected per user.The decision variables indicate whether the task is processed locally, at the CAP, or at the cloud.Source: §3.1.2 · p. 3

3.1.3 Cost of Local Processing

• Task input and output sizes and processing cycles are assumed known, allowing local processing energy and time to be modeled.The paper notes that profiling can provide these task quantities.Source: §3.1.3 · p. 3

3.1.4 Cost of CAP Processing

• CAP processing accounts for wireless transmission and reception, allocated uplink/downlink bandwidth, processing rate, and usage cost.The CAP’s total processing rate constrains per-user assignments; its usage-cost model is outside the work’s scope and is treated as given.Source: §3.1.4 · pp. 3–4

3.1.5 Cost of Cloud Processing

• Cloud processing adds CAP-to-cloud transmission and cloud computation; both rates are treated as predetermined and independent of the number of users.The paper attributes these assumptions to the high-capacity wired link and dedicated cloud service.Source: §3.1.5 · p. 4

3.2 Problem Formulation

• The optimization jointly chooses offloading and communication/CAP processing resources to minimize weighted energy, usage, and maximum transmission and processing delay costs.A network controller, potentially the CAP, can collect user information and broadcast the resulting decisions and allocations.Source: §3.2 · pp. 4–5
• Because delay is an objective rather than a constraint, solutions are feasible under the formulation, but strict task deadlines require additional treatment.The paper notes that some decisions may violate strict processing deadlines and discusses that scenario separately.Source: §3.2 · p. 5

4.1 Overview of the Proposed Solution

• For fixed offloading decisions, resource allocation is convex and solvable optimally; exhaustive search over 3^N decisions is globally optimal but grows exponentially.The proposed shareCAP method is introduced as an efficient alternative to that search.Source: §4.1 · p. 5

4 SHARECAP OFFLOADING SOLUTION

• shareCAP transforms the problem into a separable QCQP, then applies semidefinite relaxation and randomization to recover binary offloading decisions.The equivalent QCQP is non-convex and NP-hard in general.Source: §4.1 · p. 5, §4 · p. 5, §4.2 · p. 7

4.2 QCQP Reformulation and Semidefinite Relaxation

• Dropping the rank-one constraint relaxes the equivalent QCQP into a separable SDP that standard SDP software can solve in polynomial time.The QCQP constraints correspond to the original delay, placement, bandwidth, and CAP-processing constraints.Source: §4.2 · p. 7

4.3 Binary Offloading Decisions via Randomization

• The randomization maps SDP-derived marginal probabilities to feasible placements, evaluates candidate allocations, and selects the lowest-cost solution; ten trials give performance close to optimal.The proposed mapping respects the placement constraint, unlike sign-based randomization, which may produce infeasible decisions.Source: §4.3 · pp. 7–8

5 OFFLOADING WITH DELAY CONSTRAINTS

• Strict processing deadlines make some offloading decisions infeasible, motivating the three-step shareCAP-D procedure.The procedure consists of SDR, adaptive adjustment, and sequential tuning.Source: §5 · p. 8

5.1 Step 1: QCQP Transformation and Semidefinite Relaxation

• The strict deadlines add per-user constraints to the separable QCQP and its SDP relaxation, which is always feasible, but randomization alone cannot guarantee a feasible offloading vector.The method instead uses a deterministic initial offloading solution before feasibility repair.Source: §5.1 · p. 9

5.2 Step 2: Obtaining a Feasible Solution via Adaptive Adjustment

• Adaptive adjustment always produces a feasible solution by testing the current decisions and switching offloaded tasks to local processing when needed.The paper assumes each user can meet its deadline through local processing.Source: §5 · p. 8, §5.2 · p. 9

5.3 Step 3: Obtaining a Local Optimum via Sequential Turning

• Sequential tuning further reduces system cost until no user’s offloading decision can be changed to lower it, yielding a local optimum under strict delay constraints.Its final cost is no higher than the feasible adaptive-adjustment solution.Source: §5.3 · pp. 9–10

6 EXTENSION TO SUM DELAY OPTIMIZATION

• The objective can account for the sum of all users’ task delays instead of the maximum transmission and processing delays used earlier.The strict per-task delay constraint can also be included for time-sensitive applications.Source: §6 · p. 10
• The sum-delay problem can be transformed into a separable QCQP and SDP relaxation using a procedure similar to the original formulation.The resulting SDR structure is the stated difference from the original problem.Source: §6 · p. 10
• The shareCAP procedure, or shareCAP-D when strict delay constraints apply, can obtain the offloading decisions and corresponding resource allocation for the sum-delay problem.The derivation is omitted in the paper.Source: §6 · p. 10

7.1 Parameter Setup

• The evaluation averages 100 task-size realizations, uses N = 8 by default, and compares against local-only, cloud-only, local-cloud, random-mapping, and exhaustive-search policies.The default device characteristics are based on a Nokia mobile phone.Source: §7.1 · p. 11

7.2 Performance of ShareCAP

• Across varying weights, user counts, and scaled resources, ShareCAP outperforms the compared methods and stays close to the exhaustive-search optimum.The scaled-resource case increases uplink and downlink bandwidth and total CAP processing rate in proportion to the number of users.Source: Figure 4 · p. 11, Figure 5 · p. 11, Figure 6 · p. 12
• As cloud-processing cost weight β rises, tasks become more likely to run locally or at the CAP; as β falls, ShareCAP, local-cloud, and optimal policies converge to cloud processing.As CAP CPU rate rises, ShareCAP performance improves; when the CAP is too slow to help, ShareCAP converges to local-cloud.Source: §7.2 · pp. 11–12

7.3 Performance of ShareCAP-D

• ShareCAP-D remains near-optimal as the delay factor is relaxed, except when θ is close to 1 and the problem is nearly infeasible.Moderately relaxed delay constraints allow more feasible offloading decisions and a local optimum closer to the optimal solution.Source: Figure 7 · p. 12, §7.3 · p. 12
• With θ = 1.1, ShareCAP-D's cost declines steeply as CAP CPU rate increases and is nearly identical to the optimal policy when fA ≥ 5 × 10^9.It outperforms all compared methods except the optimal solution in this setting.Source: Figure 8 · p. 12, §7.3 · p. 12
• With θ = 1.1, ShareCAP-D's system cost remains close to the optimal policy across varying numbers of users.The authors describe this as showing scalability despite the additional delay constraints.Source: §7.3 · pp. 12–13, Figure 9 · p. 13

• The objective is to minimize a weighted total cost of energy, computation, and maximum delay across users.Source: §8 · p. 13
• ShareCAP uses semidefinite relaxation and a new randomization mapping; under strict task deadlines, three-step ShareCAP-D obtains a feasible, locally optimal solution.Source: §8 · p. 13
• Numerical results suggest nearly optimal performance across a wide range of settings, while efficient CAP utilization can bring substantial cost benefit.Source: §8 · p. 13