Source-linked AI summary
Joint Service Caching and Task Offloading for Mobile Edge Computing in Dense Networks
Jie Xu, Lixing Chen, Pan Zhou
TL;DR
The paper addresses the under-studied problem of joint service caching and task offloading in MEC-enabled dense cellular networks, accounting for heterogeneous and spatially varying service demand. It proposes an online decentralized algorithm with provable close-to-optimal performance and bounded energy-consumption violation.
Problem
Service heterogeneity and caching decisions on base stations are often overlooked in MEC, motivating investigation of service caching in dense cellular networks.
Method
The paper develops an efficient online and decentralized algorithm using a variation of Gibbs sampling to tailor caching decisions to temporal and spatial service popularity.
Results
The algorithm achieves close-to-optimal performance compared to an optimal algorithm with full future information while bounding potential energy-consumption violation and remaining scalable to large networks.
Takeaways & Limitations
Joint caching and offloading can be implemented online and decentralized while adapting service caching to temporal and spatial demand patterns with provable performance guarantees.
Takeaways & Limitations
The current model assumes a fixed user-cell association, identified as a limitation requiring future research.
Abstract
from arXiv · showhide
Mobile Edge Computing (MEC) pushes computing functionalities away from the centralized cloud to the network edge, thereby meeting the latency requirements of many emerging mobile applications and saving backhaul network bandwidth. Although many existing works have studied computation offloading policies, service caching is an equally, if not more important, design topic of MEC, yet receives much less attention. Service caching refers to caching application services and their related databases/libraries in the edge server (e.g. MEC-enabled BS), thereby enabling corresponding computation tasks to be executed. Because only a small number of application services can be cached in resource-limited edge server at the same time, which services to cache has to be judiciously decided to maximize the edge computing performance. In this paper, we investigate the extremely compelling but much less studied problem of dynamic service caching in MEC-enabled dense cellular networks. We propose an efficient online algorithm, called OREO, which jointly optimizes dynamic service caching and task offloading to address a number of key challenges in MEC systems, including service heterogeneity, unknown system dynamics, spatial demand coupling and decentralized coordination. Our algorithm is developed based on Lyapunov optimization and Gibbs sampling, works online without requiring future information, and achieves provable close-to-optimal performance. Simulation results show that our algorithm can effectively reduce computation latency for end users while keeping energy consumption low.
I. INTRODUCTION
MEC brings computing and storage toward the network edge, but resource-limited BSs must decide which heterogeneous, changing-demand services to cache. The paper jointly optimizes service caching and task offloading in dense cellular networks with an online, decentralized algorithm.
- Motivation: MEC-enabled BSs can serve computation requests locally, while excess tasks are offloaded to the cloud in a hierarchical structure.This edge placement supports applications requiring low latency and reduces reliance on centralized cloud infrastructure.
- Problem setting: Service caching stores application services and related databases or libraries at edge servers, enabling tasks requiring those services to execute.Because BS resources are limited, only a small service set can be cached simultaneously.
- Problem setting: Cached-service choices determine which tasks can be offloaded and therefore significantly affect edge-computing performance.BSs must jointly optimize caching and offloading decisions.
- Challenges: Optimal caching must account for heterogeneous resource requirements and popularity patterns that change across users, locations, and time.The paper motivates adaptive updates based on predicted service popularity.
- Challenges: Random demand arrivals and long-term energy constraints require online decisions without future system information.Dense multi-cell networks further couple demand and resources across spatial and temporal domains, motivating coordination among BSs.
- Approach and contributions: OREO jointly optimizes dynamic service caching and task offloading online using Lyapunov optimization and decentralized Gibbs-sampling coordination.The algorithm has provable close-to-optimal performance, bounds potential energy-constraint violation, and is designed to scale to large networks.
II. RELATED WORK
Prior MEC studies largely emphasize computation offloading, while service caching must additionally account for service availability, computing and storage constraints, and coupled decisions in dense cellular networks.
- Research gap: Most prior MEC work studies computation offloading while implicitly assuming edge servers can process any offloaded task type.Service availability is crucial in MEC because edge servers have limited resources.
- Related approaches: Existing cloud-placement approaches cannot directly design MEC service-caching policies because mobile networks are more complex and volatile, with spatially and temporally coupled decisions.The cited comparison contrasts conventional placement settings with MEC conditions.
- Related approaches: Compared with related cloudlet work, this study addresses overlapping BS coverage, provides a strong performance guarantee, and enables decentralized coordination.The prior work used non-overlapping coverage, heuristic solutions, and centralized coordination.
- Research gap: Service caching differs from content caching because it jointly considers computing and storage constraints with task offloading.The paper identifies this joint optimization as necessary for overall system performance.
- Contribution and scope: The paper proposes an efficient online and decentralized algorithm for dynamic service caching and task offloading in cellular networks.The authors characterize the model as a first step and note that future improvements are discussed in the conclusion.
A. Network and Services
The system models a dense cellular network in which BSs cache heterogeneous computing services and jointly decide caching and local processing for region-based demand.
- Network model: The network contains N BSs serving users across M disjoint regions, where each region can reach multiple BSs because of dense deployment.Regions represent statistical request information and support relatively infrequent service-caching updates.
- BS resources: Each BS has storage capacity C_n and maximum CPU frequency f_n for processing tasks offloaded by users.At each slot, BSs make service-caching and task-offloading decisions.
- Services: A service is an application hosted by a BS, and executing it requires caching associated data such as libraries and databases.Examples include video streaming, social gaming, navigation, and augmented reality.
- Services: Services are heterogeneous in storage and CPU requirements, with service k requiring storage c_k and task workload modeled exponentially with mean µ_k.The model includes K computing services.
- Demand model: Demand is region- and service-specific, follows a Poisson arrival model, and can be predicted short-term for the next slot.The paper distinguishes this immediate prediction from the long-term information required by an offline algorithm.
- Caching decisions: Caching a service enables its tasks to be processed at the network edge, reducing computation latency and improving user quality of experience.Limited storage prevents caching all services simultaneously, requiring selective caching.
- Task routing: If no reachable BS caches a requested service, tasks are sent to the remote cloud; otherwise, demand is distributed among BSs offering that service.The model assumes even distribution among eligible BSs but allows other association rules.
2) Task Offloading:
Task offloading determines what fraction of cached-service workload each BS processes locally versus sends to the cloud, with resulting latency and energy modeled through queueing and CPU assumptions.
- Task offloading: For cached services, each BS chooses the fraction of tasks processed locally, while the remaining tasks are offloaded to the remote cloud.The local-processing fraction is a continuous decision variable in [0, 1].
- Task offloading: Offloading fractions are planned at each slot, while actual actions occur when tasks arrive and depend on task requirements.The slot-level plan provides reasonably fine-grained control.
- Cost model: Different caching and offloading decisions produce different computation latency and computing energy consumption.The optimization therefore considers both performance dimensions.
- Energy model: The BS is modeled as processing tasks at maximum CPU speed under workload and using minimum speed when idle, with negligible idle energy.Static power remains when the BS is turned on.
- Delay model: Average computation delay is modeled using an M/G/1 queue and its sojourn time, combining service and waiting time.Poisson arrivals and service-time moments support the queueing analysis.
- Delay model: Because service types may differ, overall service time is modeled as a random sampling among exponential distributions, with first and second moments used in the queue analysis.The Pollaczek–Khinchin formula is used to obtain expected sojourn time.
- Cloud offloading: Cloud-offloaded tasks are assumed to experience delay mainly from transmission because the remote cloud has ample computing power.The resulting cloud delay contributes to total expected computation delay cost.
D. Problem Formulation
The problem formulation jointly minimizes long-term computation delay and energy under storage and per-slot constraints, while motivating an online decentralized solution for unknown demand dynamics.
- D. Problem Formulation: The network operator jointly chooses service caching and task offloading to minimize computation latency while keeping total computation energy low.The objective is evaluated across BSs over time.
- D. Problem Formulation: The formulation includes a long-term network energy constraint, individual BS storage limits, and per-slot energy and delay bounds.The long-term average energy consumption must not exceed Q.
- D. Problem Formulation: The long-term energy constraint couples BS decisions spatially and temporally.This coupling links decisions across BSs and time slots.
- D. Problem Formulation: Offline optimization requires future task-demand distributions, which are difficult to predict, and the resulting problem is mixed-integer nonlinear programming.These properties motivate making decisions online and on the fly.
- A. Lyapunov-based Online Algorithm: OREO is an online algorithm developed under Lyapunov optimization and compared with the optimal offline algorithm for latency minimization.The framework converts the long-term problem into per-slot problems using current-slot information.
- A. Lyapunov-based Online Algorithm: OREO lets BSs choose cached services and the workload retained at the edge or offloaded to the cloud in a distributed manner.The method is designed for decentralized coordination among BSs.
- A. Lyapunov-based Online Algorithm: A virtual energy-deficit queue tracks deviation from the energy constraint and guides current-slot decisions without future information.The Lyapunov function measures the queue’s congestion level, while larger backlog makes energy reduction more critical.
- A. Lyapunov-based Online Algorithm: OREO minimizes a drift-plus-cost bound subject to storage and per-slot constraints, with V controlling the latency–energy tradeoff.A Gibbs-sampling variation determines the decision pair used by the algorithm.
B. Distributed Optimization for P2
The paper solves P2 as a distributed joint service-caching and task-offloading problem using Gibbs sampling, with decentralized neighborhood updates and convergence to the global optimum as τ approaches zero.
- P2 is a mixed-integer nonlinear programming problem because caching decisions are binary while offloading decisions are continuous.
- OREO uses a distributed Gibbs-sampling variation to iteratively determine the service-caching and task-offloading decision pair at each time slot.The decision pair is selected at the beginning of a time slot.
- Each selected base station virtually changes its caching decision, computes the neighborhood delay-cost difference, and probabilistically accepts the new action.The acceptance probability balances exploration and exploitation through the smooth parameter τ.
- Updates require coordination only among neighboring base stations, which exchange caching decisions after each iteration.Base stations without common neighboring stations may update simultaneously because their caching decisions do not affect one another.
- Very small τ can leave the algorithm in local optima for a long time, whereas τ →+∞ prevents convergence through continual exploration.
- As τ decreases, the algorithm converges with higher probability to P2's global optimum, and τ →0 yields global convergence.
C. Performance Analysis
Lyapunov analysis establishes OREO's delay and energy guarantees under long-term energy constraints. The algorithm achieves an [O(1/V ), O(V )] delay-energy tradeoff and approaches offline optimal performance as V grows.
- Lyapunov optimization is used to analyze OREO's performance under the long-term energy constraint.
- OREO bounds both time-average system delay and time-average base-station energy consumption under the long-term constraint.The theorem expresses the delay and energy guarantees relative to optimal delay, maximum delay, and long-term energy surplus.
- The resulting delay-energy tradeoff is [O(1/V ), O(V )].Increasing V improves delay asymptotically but increases time-average energy consumption linearly with V.
- OREO asymptotically achieves the offline problem P1's optimal performance as V →∞.
- Achieving P1's optimal performance requires a larger energy-deficit queue, which postpones convergence and raises average energy consumption.
V. SIMULATION
Simulations in a 500m×500m network with 9 base stations evaluate OREO against caching and energy-management benchmarks. OREO provides near-optimal delay while closely following the long-term energy constraint.
- Simulation setup: The simulation uses 9 regularly deployed base stations serving a 500m×500m area divided into 25 regions.Service demand is modeled using Poisson arrivals, with parameters collected in Table I.
- Benchmarks: OREO is compared with non-cooperative caching, centralized delay-optimal caching, and myopic caching under a per-slot energy constraint.
- Performance comparison: OREO achieves near-to-optimal delay while closely following the long-term energy constraint.
- Performance comparison: The centralized optimal scheme achieves the lowest delay but incurs large energy consumption, whereas OREO slightly sacrifices delay to satisfy the energy constraint.
- Energy management: A hard per-slot energy constraint can leave myopic caching far below the long-term energy limit, resulting in inefficient energy usage.
- Performance comparison: The non-cooperative strategy has inferior delay-minimization and energy-saving performance because it neglects interdependence among base stations.
- Convergence: With τ = 10^-2, the distributed algorithm finds the global optimum with fewer iterations than at τ = 10^-3, while larger τ values can produce inferior converged solutions.
C. Impact of storage capacity
OREO adapts joint service caching and task offloading to storage, energy, demand, and spatial-coordination conditions. Larger storage generally lowers delay, while the algorithm keeps energy consumption near its constraint and coordinates distinct caching decisions across adjacent BSs.
- System delay decreases as storage capacity increases because more services can be cached at BSs.
- With small storage capacity, OREO achieves the same system delay as the centralized delay-optimal scheme.Few tasks are processed at BSs, so the energy deficit queue is zero in most slots and the problem degenerates to the delay-optimal format.
- As storage capacity increases, OREO’s delay diverges from the delay-optimal scheme to meet the energy consumption constraint.
- OREO’s energy consumption closely follows the predetermined energy consumption constraint across storage capacities, unlike three benchmarks that overuse or underuse it.
- A larger energy consumption constraint lowers system delay, but the performance gain becomes modest when Q is large.OREO also converges to the predetermined energy consumption constraint.
- Adjacent BSs with similar demand patterns can make dramatically different caching decisions, accommodating more service types and computation tasks.The paper attributes the resulting cooperation to improved overall system efficiency.
- When energy deficit is small, BSs retain more workload locally; when it is large, they process less workload at the edge.This shifts energy consumption toward the predetermined constraint while balancing computation delay and energy use.
APPENDIX
The appendix analyzes OREO’s distributed caching process as a Markov chain and derives delay and energy performance bounds. It establishes convergence toward an optimal state in probability under the Gibbs-sampling formulation.
- Each BS’s caching decision forms one dimension of an N-dimensional Markov chain, with one BS selected uniformly to explore a new decision per iteration.
- The stationary distribution is proportional to e^(-f(S)/τ), where f(S) is the objective value for state S.
- The Markov chain is irreducible and aperiodic, making the stationary distribution valid and unique.
- As τ approaches zero, the stationary probability of the optimal state approaches one, so the algorithm converges to that state in probability.
- The proof derives time-average system-delay and energy-consumption bounds using Lyapunov drift analysis and a stationary randomized comparison policy.
- The delay and energy bounds follow after summing drift inequalities over time and using nonnegative Lyapunov backlog terms.
Algorithm 2 Distributed algorithm for OREO
Algorithm 2 implements OREO through repeated decentralized updates. Each iteration predicts service demand, samples a BS and feasible cache decision, optimizes the associated offloading decision, and stops when the criterion is met.
- The algorithm initializes service-cache and task-offloading decisions and their objective value before iterative updates.
- Each iteration predicts service demand and randomly selects a BS together with a candidate service-cache decision.
- A candidate cache decision is considered only when feasible, after which the algorithm minimizes P2 over the related decisions.
- The procedure updates neighboring-BS coordination and returns the decisions when the stopping criterion is satisfied; otherwise, it repeats the sampling step.