PaperlayerView exact revision on arXiv

Source-linked AI summary

Joint Optimization of Service Caching Placement and Computation Offloading in Mobile Edge Computing Systems

Suzhi Bi, Liang Huang, Ying-Jun Angela Zhang

arXiv:1906.00711v3cs.NI

TL;DR

The paper addresses the coupled placement and offloading decisions that arise when a mobile user uploads customized programs for edge execution. It derives a tractable joint optimization and reduced-complexity alternating method, with simulations showing lower computation delay and energy consumption than benchmark methods. The results are intended as an offline benchmark because the model assumes non-causal knowledge of future task parameters.

  • Problem

    Existing service-caching approaches commonly assume all tasks are offloaded and do not cover local execution with MU-provided customized programs, although these choices are interdependent.

  • Method

    The paper jointly optimizes caching placement, computation offloading, and resource allocation, derives closed-form resource allocation, converts the MINLP to a 0-1 ILP, and alternates caching and offloading updates.

  • Results

    Joint optimization significantly reduces the MU's computation delay and energy consumption compared to benchmark methods, while alternating minimization offers a reduced-complexity alternative for large-size problems.

  • Takeaways & Limitations

    The resulting methods provide joint and reduced-complexity optimization approaches for service-cache-assisted MEC with local execution and reusable user-generated programs.

  • Takeaways & Limitations

    The study considers an offline model with non-causal knowledge of future computation task parameters and a single-server, single-user setting.

Abstract

from arXiv · show

In mobile edge computing (MEC) systems, edge service caching refers to pre-storing the necessary programs for executing computation tasks at MEC servers. At resource-constrained edge servers, service caching placement is in general a complicated problem that highly correlates to the offloading decisions of computation tasks. In this paper, we consider a single edge server that assists a mobile user (MU) in executing a sequence of computation tasks. In particular, the MU can run its customized programs at the edge server, while the server can selectively cache the previously generated programs for future service reuse. To minimize the computation delay and energy consumption of the MU, we formulate a mixed integer non-linear programming (MINLP) that jointly optimizes the service caching placement, computation offloading, and system resource allocation. We first derive the closed-form expressions of the optimal resource allocation, and subsequently transform the MINLP into an equivalent pure 0-1 integer linear programming (ILP). To further reduce the complexity in solving the ILP, we exploit the underlying structures in optimal solutions, and devise a reduced-complexity alternating minimization technique to update the caching placement and offloading decision alternately. Simulations show that the proposed techniques achieve substantial resource savings compared to other representative benchmark methods.

I. INTRODUCTION

The paper studies joint service caching and computation offloading for a dependent task sequence in a single-user MEC system. It formulates and simplifies the optimization, then evaluates joint and alternating methods against benchmarks.

  • I. INTRODUCTION: Existing service-caching studies generally assume all tasks are offloaded and focus on reducing workload forwarded to the cloud.These assumptions can be non-optimal when wireless transmission or edge execution is costly.
  • I. INTRODUCTION: The considered system executes M dependent tasks, with each task processed locally or at the edge and each task output serving as the next task's input.Tasks use one of N programs, and the MU supplies program data for edge execution.
  • I. INTRODUCTION: The proposed formulation jointly optimizes offloading, service caching, and resource allocation to minimize the MU's computation delay and energy consumption.The original problem is a MINLP with binary decisions and continuous CPU-frequency and transmit-power variables.
  • I. INTRODUCTION: Simulations show that joint optimization significantly reduces the MU's computation delay and energy consumption relative to benchmark methods.The alternating method provides a reduced-complexity alternative for large-size problems, while the study assumes offline non-causal knowledge of future task parameters.
  • I. INTRODUCTION: The paper allows local execution when appropriate and lets the MU upload customized programs that the edge server can cache for later reuse.This makes caching placement and offloading decisions interdependent.

1) Computation Model:

The computation model represents local and edge execution, program generation, caching causality, storage capacity, and wireless transmission costs for each task. Program caching persists across tasks subject to causal availability and capacity constraints.

  • 1) Computation Model:: Local execution uses CPU frequency fi, bounded by fmax, with workload Li, efficiency parameter κ, and exponent α ≥ 2 determining computation time and energy.The edge server uses fixed frequency f0 > fmax.
  • 1) Computation Model:: When edge execution requires an uncached program, the server incurs program-generation time Wi based on the program type used by task i.Wi is the sum of the generation times Dj weighted by the task's program indicators ui,j.
  • 1) Computation Model:: A cached program at task i is attainable only if it was cached before the previous task or uploaded during the previous edge execution.Otherwise, xi,j must be zero, enforcing caching causality.
  • 1) Computation Model:: At every task stage, the cached program sizes satisfy a capacity constraint weighted by cj and bounded by C.The model assumes C ≥ maxj=1,···,M cj to avoid a trivial solution.
  • 1) Computation Model:: Wireless costs depend on task-specific channel gain hi, bandwidth, transmit power, noise, and the sizes of uploaded program and task data.Program and task data may be jointly encoded when both are offloaded.
  • 1) Computation Model:: The model separately accounts for program-data transmission, task-data transmission, result downloading, and the associated MU energy consumption.When both data types are sent, their time and energy costs are additive.

B. Performance Metric

The performance metric combines task execution and preparation costs, including data transmission and program generation. The total energy similarly combines program uploads, local computation, and task-data offloading through a weighted TEC objective.

  • B. Performance Metric: Total computation delay consists of task execution time and preparation time before execution.Preparation includes data transmission and program generation.
  • B. Performance Metric: Two consecutive locally executed tasks require no program or task-data transmission delay.This is the ai−1 = 0 and ai = 0 case.
  • B. Performance Metric: Switching from local to edge execution requires task-data transmission and may additionally require program upload and generation.The latter costs occur when the required program is not cached.
  • B. Performance Metric: Switching from edge to local execution requires downloading the previous computation output to the MU.This is the only preparation cost in that transition case.
  • B. Performance Metric: Consecutive edge executions avoid task-input transmission because the next input is already available as the previous edge output.Program transmission and generation remain necessary when the program is absent from the service cache.
  • B. Performance Metric: TEC is the weighted sum T EC = βT + (1 −β)E, combining total computation time T and MU energy E.The weighting parameter satisfies β ∈ [0, 1].

III. JOINT CACHING PLACEMENT AND COMPUTATION OFFLOADING OPTIMIZATION

The paper jointly optimizes offloading, service caching, and resource allocation to minimize the MU’s total energy consumption and computation delay. It derives optimal resource allocations and converts the resulting MINLP into a pure binary ILP.

  • Optimal resource allocation: Resource allocation can be optimized separately for any feasible offloading and caching decisions, enabling closed-form optimal allocations.The binary feasibility set is independent of the resource-allocation variables.
  • Equivalent ILP formulation: After substituting the optimal allocations, the problem is equivalently transformed into a pure 0-1 ILP over offloading and caching decisions.The transformed problem can be handled by standard integer-optimization algorithms.
  • Problem formulation: The optimization jointly determines task offloading, service caching placement, and system resource allocation to minimize the MU’s total energy consumption and computation delay.The decision variables include binary offloading and caching variables plus continuous CPU-frequency and transmit-power allocations.
  • Problem formulation: The formulation is a MINLP because its objective and constraints combine binary decisions with nonlinear delay and energy functions.The original form lacks an efficient optimal algorithm.

B. Optimal Resource Allocation

The resource-allocation subproblem decomposes into independent scalar optimizations for task-related durations. Closed-form solutions determine offloading, service, and local-computing durations, from which CPU frequency and transmit power are recovered.

  • Resource-allocation decomposition: For any feasible offloading and caching decisions, the optimal resource-allocation variables can be optimized independently of those binary decisions.This follows because minimizing each task’s energy and delay cost does not depend on the caching placement or offloading solution.
  • Closed-form solutions: The optimization of the duration vector decomposes into individual scalar optimization problems, yielding closed-form solutions for offloading and service-computing durations.The derivation uses the Lambert-W function for the offloading-duration expression.
  • Resource recovery: Once the optimal durations are obtained, the corresponding CPU frequencies and transmit powers are recovered from the original task-resource relationships.The recovery uses equations (1), (5), and (6).
  • Offloading allocation: When the channel gain is below a fixed threshold, an offloaded task uses maximum transmit power; above the threshold, it offloads for a shorter time.The threshold separates maximum-power transmission from shorter-duration offloading.
  • Local-computing allocation: For locally computed tasks, higher delay weight or greater energy efficiency favors faster computation, reaching fmax when either condition is sufficiently strong.Energy efficiency is represented by a smaller κ.

C. Equivalent ILP Formulation

The paper exploits caching-causality structure to eliminate redundant placement variables and reformulates the remaining optimization as an equivalent ILP or multidimensional knapsack problem. This substantially reduces the caching decision dimension while preserving optimal values.

  • C. Equivalent ILP Formulation: Introducing auxiliary variables zi = aixi,ϕi and bi = aiai−1 linearizes multiplicative terms, producing a standard 0-1 ILP solvable by branch and bound.The auxiliary-variable constraints force the products to hold at the optimum.
  • A. Structure of the Caching Causality: The reduced formulation assumes a feasible offloading decision and optimizes caching placement subject to the original causality and capacity constraints.The offloading-task index set is A.
  • A. Structure of the Caching Causality: The original formulation contains MN caching variables, but only placement variables associated with offloaded tasks need to be optimized.The remaining variables are redundant under the caching-causality structure.
  • A. Structure of the Caching Causality: For a tagged offloading task k, Vk contains consecutive preceding task indices whose next offloaded task of service type ϕk is k.Examples include V8 = {5, 6, 7, 8} and V10 = {7, 8, 9, 10}.
  • A. Structure of the Caching Causality: Caching variables after the last subsequent offloaded task of a service type can be set to zero without changing the optimal value.Variables associated with service types that are never offloaded again are also unnecessary.
  • A. Structure of the Caching Causality: Proposition 2 replaces variables within each Vk by the variable at the corresponding tagged offloading task while preserving feasibility and objective value.This establishes that only {xk,ϕk | k ∈ A} are independent variables.
  • A. Structure of the Caching Causality: The replacement can remove caching-causality constraints and redundant variables, for example replacing x7,1, x8,1, and x9,1 by x10,1.The replacement also removes the associated constraints for that service type and task range.
  • A. Structure of the Caching Causality: The reduced caching problem is a multidimensional knapsack problem with at most |A| ≤ M binary variables instead of MN.Exact algorithms can solve moderate-size instances in reasonable computation time, including over 500 variables within 0.1 second in the cited example.

B. Optimal Caching Placement: A Case Study

The caching-placement formulation removes redundant structure from the original problem and yields a smaller standard 0-1 MKP that can retrieve the original solution.

  • B. Optimal Caching Placement: A Case Study: Variable replacement constructs caching constraints for the example, after which duplicated and redundant constraints are identified.For example, C2 is redundant under C ≥ c_i, and C3 duplicates C2; C6 is redundant if C7 holds.
  • B. Optimal Caching Placement: A Case Study: Fig. 3 illustrates an optimal transformed solution, its retrieved caching placement, and the resulting cached-task state.Red or black boxes represent x*_{i,j}=1 or 0 in the transformed solution, while shaded or empty boxes represent cached or uncached tasks.
  • B. Optimal Caching Placement: A Case Study: After removing redundancy, the example has 7 binary variables and 5 caching-capacity constraints instead of 36 variables and 12 constraints.The resulting formulation also removes all caching-causality constraints and becomes a standard 0-1 MKP.
  • B. Optimal Caching Placement: A Case Study: The optimal solution of the reduced formulation can be retrieved for the original caching-placement problem using Proposition 2.The example explicitly uses the transformed optimum to obtain the corresponding solution of (P4).

V. OPTIMAL TASK OFFLOADING DECISION

Given caching placement, the offloading problem becomes easier because cached-task decisions have structured optima, leaving the main optimization over uncached tasks.

  • V. OPTIMAL TASK OFFLOADING DECISION: After optimizing cached tasks, the remaining ILP contains only offloading variables for uncached tasks.The method eliminates all cached-task offloading variables before transforming the remaining problem into an equivalent ILP.
  • V. OPTIMAL TASK OFFLOADING DECISION: With caching placement fixed, feasibility is characterized by requiring a preceding task to be offloaded at the start of every program run.This replaces all caching-causality constraints and removes |S| variables before introducing auxiliary variables.
  • V. OPTIMAL TASK OFFLOADING DECISION: The caching state alternates between cached and uncached segments, with equal numbers K of each segment and cached segments determined by the placement.Virtual boundary tasks ensure the sequence starts with a cached segment and ends with an uncached segment.
  • V. OPTIMAL TASK OFFLOADING DECISION: When K=1, no computational-complexity improvement is obtained, although this case rarely occurs with a proper initial caching placement.For K>1, cached segments provide the structure used by the decomposition.
  • V. OPTIMAL TASK OFFLOADING DECISION: Once boundary decisions a_ek and a_uk are fixed, cached and uncached segment objectives can be optimized separately over disjoint variables.This decomposition enables efficient treatment of each cached segment according to four boundary cases.
  • V. OPTIMAL TASK OFFLOADING DECISION: For cached segments, the optimal policy depends on endpoint decisions: all edge execution, one edge offloading interval, one downloaded result, or a one-climb policy.The relevant transition indices can be found by linear or two-dimensional search, depending on the case.

B. Equivalent ILP Formulation

The segment-based offloading formulation linearizes endpoint products with auxiliary variables and reduces the pure 0-1 optimization size when cached tasks are numerous.

  • B. Equivalent ILP Formulation: Complementary variables and endpoint products rewrite the segment objective into a form suitable for integer linear constraints.The construction defines q_k=a_ek a_uk and q̄_k=a_ek(1−a_uk), then introduces auxiliary variables.
  • B. Equivalent ILP Formulation: Constraints (33c)–(33f) enforce the auxiliary-product relations because the objective decreases with the corresponding auxiliary variables.The resulting formulation is a pure 0-1 integer optimization problem.
  • B. Equivalent ILP Formulation: Fig. 5 tracks the average segment count K and cached-task count |A1| while solving (33) for different task counts M.The plotted quantities characterize how the reduced formulation behaves during alternating minimization.
  • B. Equivalent ILP Formulation: The formulation removes 2|A1| variables for cached tasks while adding 3(K−1) auxiliary variables.It is effective when the number of cached tasks |A1| is substantially larger than the number of segments K.

C. Alternating Minimization

Alternating minimization alternately optimizes caching and offloading, and simulations evaluate it alongside the joint optimum and benchmark schemes under stated workload and channel assumptions.

  • C. Alternating Minimization: Starting from a(0), the method repeatedly computes optimal caching X given a and optimal offloading a given X until objective improvement stops.This alternating scheme exploits the separately tractable subproblems.
  • C. Alternating Minimization: The simulations average results over 50 independent instances with N=6 program types and Markov-generated task sequences.Task and program parameters are uniformly sampled from the ranges in Table I.
  • C. Alternating Minimization: The evaluation compares optimal joint optimization and alternating minimization with Popular-cache and cache-oblivious offloading benchmarks.The alternating method is initialized with a_i=1 for every task.
  • C. Alternating Minimization: Fig. 6 presents the optimal energy-delay tradeoff of joint optimization as β varies.The figure is interpreted together with the weighting parameter that controls the relative emphasis on energy and delay.

A. TEC Performance Evaluation

The joint optimization generally provides the best TEC performance, while alternating minimization offers a lower-complexity alternative as task count grows. Performance depends on program-generation delay, cache capacity, channel quality, and objective weighting.

  • Program-generation time: TEC increases with program-generation time for all methods, while Cache-oblivious performance degrades as generation time becomes large.Cache-oblivious offloads almost all tasks, so repeated offloading and program initialization can exceed edge-computation savings.
  • Caching capacity: Larger caching capacity decreases TEC and increases task offloading ratios across all considered schemes.When C = 6, Cache-oblivious approaches the optimal scheme because all programs can be stored.
  • Channel quality: When de = 3, joint optimization reduces TEC by more than 25% compared with all other schemes.Increasing path loss weakens wireless channels, reducing offloading ratios and increasing TEC; the proposed method retains a significant advantage.
  • Overall comparison: The optimal joint optimization scheme has evident TEC advantages, whereas Popular-cache performs poorly because it neglects task offloading decisions.Cache-oblivious performs well mainly with short program-generation time or less stringent delay requirements.
  • Task-count scaling: 13.5% lower TEC is achieved on average by the optimal scheme than by alternating minimization as M varies.TEC increases linearly with M for all schemes, but the two proposed methods outperform the others.
  • Complexity evaluation: The alternating minimization CPU time rises from 0.1 to 0.25 second as M increases sixfold, while joint optimization grows from 3.3 seconds to around 19 minutes.Its iteration count remains below 3, making alternating minimization a reduced-complexity alternative for large M.

APPENDIX A PROOF OF PROPOSITION 1

The proof characterizes the optimal scalar resource variable using convexity, boundary conditions, and the Lambert-W function. The resulting solution depends on whether the stationary point is feasible.

  • Optimality conditions: The objective is strictly convex within the feasible set, so the optimum is determined by a stationary point or a feasible boundary.The proof uses the derivative condition L′(v1) = 0 to identify the candidate stationary solution.
  • Closed-form solution: The stationary-point expression uses the Lambert-W function, with v1 = ln 2·Oi−1.The proof obtains this expression after transforming the derivative condition through natural exponentiation.
  • Boundary case: If the stationary point is feasible, it gives the optimum; otherwise, the optimum occurs at the relevant feasible-set boundary.The proof distinguishes whether τu_i = 0 is achievable within the feasible set.

APPENDIX B PROOF OF PROPOSITION 2

The proof establishes structural properties of feasible caching and offloading solutions. It shows that certain caching variables can be substituted without changing the objective, and identifies the offloading requirements associated with cache transitions.

  • Caching-variable substitution: For tasks sharing a service type, replacing non-tagged caching variables with the tagged task’s value preserves feasibility and objective value.If the tagged variable is one, backward induction forces the corresponding earlier variables to one; if zero, the constraints remain satisfied.
  • Caching-variable substitution: The substitution is valid because the objective is unchanged and the relevant constraints remain feasible under either binary value.The proof separately verifies feasibility for x̂k,j = 1 and x̂k,j = 0.
  • Offloading condition: For every index i in S, feasibility requires ai−1 = 1 when a cache transition occurs across consecutive tasks.The necessity follows from ui−1,jai−1 ≥ xi,j − xi−1,j and xi,j − xi−1,j = 1 for all j.
  • Offloading condition: The same condition is sufficient because the constraints divide into cases according to whether the transition index matches the preceding task’s service type.For nonmatching service types, the cache difference is nonpositive; for matching types, ai−1 = 1 satisfies the constraint.
Loading 1906.00711v3…