PaperlayerView exact revision on arXiv

Source-linked AI summary

Follow Me at the Edge: Mobility-Aware Dynamic Service Placement for Mobile Edge Computing

Tao Ouyang, Zhi Zhou, Xu Chen

arXiv:1809.05239v1cs.NIcs.AIcs.DCcs.MMcs.SE

TL;DR

Erratic user mobility forces MEC services to move among edge nodes to preserve latency, but frequent migration raises operational cost. The paper uses Lyapunov optimization with centralized and distributed approximation schemes to make online, near-optimal placement decisions under a long-term migration budget. Its analyses and evaluations demonstrate the cost-efficiency of both schemes, while distributed placement reduces decision-making runtime in simulation.

  • Problem

    The paper addresses how to maintain low user-perceived latency under unpredictable mobility while limiting the operational cost of frequent service migration.

  • Method

    Lyapunov optimization decomposes the long-term constrained problem into real-time decisions, solved approximately using Markov approximation and distributed best-response updates.

  • Results

    Theoretical analysis and trace-driven evaluations demonstrate the cost-efficiency of the proposed centralized and distributed schemes, with distributed placement dramatically reducing decision-making runtime in simulation.

  • Takeaways & Limitations

    The framework provides online mobility-aware service placement that balances time-averaged latency and migration cost without requiring future mobility or request-arrival information.

Abstract

from arXiv · show

Mobile edge computing is a new computing paradigm, which pushes cloud computing capabilities away from the centralized cloud to the network edge. However, with the sinking of computing capabilities, the new challenge incurred by user mobility arises: since end-users typically move erratically, the services should be dynamically migrated among multiple edges to maintain the service performance, i.e., user-perceived latency. Tackling this problem is non-trivial since frequent service migration would greatly increase the operational cost. To address this challenge in terms of the performance-cost trade-off, in this paper we study the mobile edge service performance optimization problem under long-term cost budget constraint. To address user mobility which is typically unpredictable, we apply Lyapunov optimization to decompose the long-term optimization problem into a series of real-time optimization problems which do not require a priori knowledge such as user mobility. As the decomposed problem is NP-hard, we first design an approximation algorithm based on Markov approximation to seek a near-optimal solution. To make our solution scalable and amenable to future 5G application scenario with large-scale user devices, we further propose a distributed approximation scheme with greatly reduced time complexity, based on the technique of best response update. Rigorous theoretical analysis and extensive evaluations demonstrate the efficacy of the proposed centralized and distributed schemes.

I. INTRODUCTION

Mobile edge computing reduces latency by placing cloud capabilities near users, but erratic mobility makes service continuity and cost-efficient migration difficult. The paper proposes online centralized and distributed placement schemes balancing latency against long-term migration cost without future mobility information.

  • Motivation: Mobile edge computing places cloud capabilities near mobile devices to address the latency limits of centralized cloud services.MEC deploys computing platforms at the radio access network edge, close to users.
  • Mobility challenge: Erratic user mobility requires service profiles to migrate across edges so users remain connected to nearby service locations.Keeping a profile at a departed edge can greatly increase perceived latency.
  • Performance-cost trade-off: Nearest-edge placement can overload MEC nodes, while frequent cross-edge migration incurs operational cost, creating a latency-cost trade-off.User-perceived latency combines communication and computing delay, and migration consumes scarce WAN bandwidth.
  • Proposed framework: The framework minimizes long-run user-perceived latency under a long-term migration-cost budget without requiring a priori user-mobility information.Lyapunov optimization converts the stochastic long-term problem into real-time decisions.
  • Algorithms: Centralized and distributed approximation schemes seek near-optimal placement solutions for the resulting NP-hard real-time optimizations.The distributed scheme extends preliminary work toward large-scale and ultra-dense networks using non-cooperative best-response updates.
  • Related work: Prior work addresses mobility using future-information prediction, Markovian assumptions, or related long-term resource constraints, whereas this work emphasizes migration-cost budgeting.The paper positions its framework relative to cloud service placement and mobility-aware MEC studies.

III. SYSTEM MODEL AND PROBLEM FORMULATION

The model assigns each mobile user’s service profile to one MEC node and represents latency as computing delay plus communication delay. Computing load, network conditions, and placement decisions jointly determine QoS.

  • III. SYSTEM MODEL AND PROBLEM FORMULATION: The system contains M MEC nodes attached to base stations or access points and N mobile users served through a device-oriented service model.Each user’s service profile and application environment are associated with that mobile device.
  • A. Service Placement Model: Each user’s service profile should migrate across edges to follow mobility and maintain low service latency.The placement decision is represented by a binary indicator x_i^k(t).
  • A. Service Placement Model: x_i^k(t)=1 means user k’s profile is placed at MEC node i at time t, while x_i^k(t)=0 otherwise.At each time slot, each user is served by one and only one MEC node.
  • B. QoS Model: The placement variables determine user-perceived latency, which is jointly composed of computing delay and communication delay.The total latency combines D_k(t) and L_k(t).
  • B. QoS Model: Computing delay reflects shared MEC capacity, request workload R_k(t), the number of served users N_i(t), and node capacity F_i.The model assumes equal resource allocation among users at a serving MEC node.
  • B. QoS Model: Dynamic placement can balance load across MEC nodes when request surges threaten satisfactory service at small-scale edge nodes.Video stream analytics illustrates how input data size and computation intensity determine required CPU cycles.
  • B. QoS Model: Communication delay includes network propagation and data transmission components influenced by hop distance, bandwidth, and current request and user-location information.The paper uses a general communication-delay model without imposing structural assumptions on network conditions.
  • B. QoS Model: The communication latency experienced by user k is expressed as a function of the placement decision x_i^k(t).The placement selects which MEC node contributes the user’s communication delay.

C. Migration Cost Model

The migration-cost model accounts for the operational cost of moving user service profiles between MEC nodes. It frames active migration as necessary for QoS but potentially excessive when performed frequently.

  • C. Migration Cost Model: Cross-edge migration consumes scarce and expensive WAN bandwidth, creating operational cost beyond the latency benefits of dynamic placement.The model introduces migration cost for transferring each user’s service profile between edges.
  • C. Migration Cost Model: E_ji^k(t) denotes the cost of migrating user k’s service profile from source MEC node j to destination MEC node i.The model assumes E_ji^k(t)=0 when source and destination nodes are identical.
  • C. Migration Cost Model: The total migration cost at time t is computed from the placement decisions and per-user source-to-destination migration costs.The formulation aggregates migration costs across all N users.
  • C. Migration Cost Model: The paper’s central trade-off is maintaining QoS by following user mobility without incurring excessive cost from frequent migration.Alternative resource-allocation models, including weighted allocation, remain applicable to the Markov approximation scheme.

D. Navigating the Performance-Cost Trade-off

The paper replaces weighted-sum tuning with long-term latency minimization under a predefined migration-cost budget, then uses Lyapunov optimization for online control without a priori system information.

  • The framework minimizes long-term average service latency subject to a predefined long-term, time-averaged migration-cost budget.The budget is represented by Eavg over T time slots.
  • Erratic mobility and service requests make accurate long-run prediction difficult, requiring continual policy adjustment to system dynamics.
  • Lyapunov optimization decomposes the long-term problem into real-time minimization problems without requiring a priori system information.
  • Queue construction: The virtual queue records exceeded migration cost relative to the long-term budget, with Q(0) = 0.
  • Queue stability: Virtual-queue stability ensures that time-averaged migration cost does not exceed the budget.The paper characterizes stability through lim T →∞ E{Q(T)}/T = 0.
  • Queue stability: A quadratic Lyapunov function and one-step drift are introduced to control virtual-queue congestion.

2) Queue stability:

The drift-plus-penalty framework combines queue stabilization with latency optimization, allowing the online placement decision to balance current delay against migration-cost backlog.

  • The one-step conditional Lyapunov drift includes a queue-backlog–migration-cost product that adapts decisions to system dynamics.
  • After virtual-queue construction, the original problem becomes a sequence of real-time placement optimizations.
  • The drift-plus-penalty function incorporates queue stability into delay performance for each real-time decision.
  • V is a non-negative control parameter that adjusts the trade-off between delay performance and migration-cost queue backlog.
  • Lemma 1 provides a supremum bound for the drift-plus-penalty function at every time slot.

B. Online Service Placement Algorithm

The online algorithm minimizes a real-time drift-plus-penalty bound, using Markov approximation for the NP-hard centralized placement problem and iteratively searching feasible policies.

  • The real-time placement problem minimizes a drift-plus-penalty supremum bound after replacing the difficult max term with a tractable upper-bound formulation.
  • Each time slot obtains a close-to-optimal placement schedule and then updates the migration-cost virtual queue.
  • The real-time optimization is NP-hard because of its combinatorial nature, motivating a near-optimal Markov approximation.
  • Markov approximation: Markov approximation converts the combinatorial problem into an equivalent entropy-regularized convex log-sum-exp problem, with β →∞ recovering the original formulation.
  • Markov approximation: The placement policy evolves as a discrete-time Markov chain through probabilistic updates, with transitions based on the cost difference between policies.
  • Markov approximation: The operator records the best policy found during iterations, while the algorithm can converge at a super-linear rate with proper parameter tuning.

D. Best Response Update Method

The distributed mechanism models multi-user service placement as a congestion game and uses asynchronous best-response updates to search for a Nash equilibrium with reduced decision-making time.

  • Best-response mechanism: The distributed scheme applies best-response updates so each user greedily selects a MEC node minimizing its own placement cost.The mechanism treats the placement problem as a congestion game with user-specific costs.
  • Nash equilibrium: A placement profile is a Nash equilibrium when no user can further reduce its cost by unilaterally changing its placement policy.The equilibrium defines the stopping condition for distributed policy search.
  • Update process: Asynchronous updates process services by assigned IDs, updating one indexed service while keeping higher-indexed strategies unchanged.The service placement profile is updated iteratively according to the current service ordering.
  • Convergence: The distributed search reaches a Nash equilibrium because the placement game has a finite improvement path under best-response updates.Theorem 1 states that an equilibrium can be achieved within at most M best-response update steps.
  • Complexity: Each update iteration performs N minimizations over at most M values, giving complexity O(NM log M) per iteration.The total running time also depends on the number of iterations required for convergence.
  • Efficiency: The distributed scheme dramatically reduces placement decision-making time compared with the Markov approximation scheme.The update iteration count is identified as a critical contributor to time overhead.

V. PERFORMANCE ANALYSIS

The performance analysis studies the optimality gaps of the centralized Markov approximation and distributed best-response schemes, and compares both online algorithms with the offline optimum.

  • Analysis scope: The analysis evaluates optimality gaps for the Markov approximation and best-response update schemes, then compares them with the offline optimum.Both online algorithms operate within the Lyapunov framework.

A. Markov Approximation

The Markov approximation scheme has a distinctive stationary distribution and an optimality gap that decreases with larger β, while the distributed scheme is bounded relative to the centralized benchmark.

  • Markov approximation: The Markov approximation algorithm converges to a distinctive stationary distribution because its service-placement Markov chain is time-reversible.Theorem 2 establishes existence of the stationary distribution.
  • Optimality gap: Increasing β allows the Markov approximation to approach the minimal supremum bound, with small performance deviation when β is sufficiently large.The paper states that β is usually large enough within an acceptable scope.
  • Optimality gap: The Markov approximation worst-case solution error is no more than 1/β ln |δ|.Here, |δ| denotes the number of feasible service-placement policies at time slot t.
  • Distributed benchmark: The distributed scheme’s approximation ratio μ measures worst-case equilibrium performance against the centralized optimum, with μ bounded by Theorem 4.A larger μ indicates lower efficiency relative to the centralized benchmark.
  • Evaluation: Numerical results show that the distributed scheme is efficient compared with the centralized approximation.This statement concerns the reported numerical comparison of the two schemes.

C. Optimality Analysis

The paper analyzes two online approximation algorithms for an NP-hard placement problem and derives delay and migration-cost bounds under the Lyapunov framework.

  • Problem and algorithms: The transformed service-placement problem is NP-hard, so the online framework uses approximation algorithms for tractable decision-making.The analyzed algorithms are centralized Markov approximation and distributed best-response update schemes.
  • Delay performance: Theorem 5 gives bounds on the long-term delay performance achieved by both proposed online algorithms.The bound holds for any non-negative control parameter V.
  • Migration-cost constraint: Theorem 6 gives a bound on migration-cost queue backlog assuming Eavg > 0 and an initially zero backlog.The queue bound is stated to hold for all time slots.
  • Performance-cost trade-off: The online algorithms exhibit an [O(1/V), O(V)] performance-cost trade-off between delay performance and migration-cost queue backlog.Increasing V brings delay performance closer to the offline optimum while affecting the queue-backlog bound.
  • Numerical evaluation: The numerical studies evaluate time-averaged perceived latency under a long-term migration-cost constraint and verify the derived theoretical results.The evaluation covers the proposed algorithms’ latency performance and theoretical bounds.

A. Simulation Setup

The evaluation uses a simulated 63-cell MEC city scenario to compare the proposed centralized and distributed algorithms with migration baselines. Results examine latency, migration cost, queue behavior, adaptability, and convergence under varying control parameters and budgets.

  • Simulation Setup: The simulation divides downtown Helsinki into 63 500×500 m² areas, each containing one MEC node with maximum computing capacity Fi = 25GHz.Mobile devices follow a shortest-path map-based movement model in the ONE simulator.
  • Simulation Setup: The benchmark compares Always Migration and No Migration strategies with GM, GRK, GK, and FMeC approaches.The proposed centralized algorithm is CA, while the distributed algorithm is DA.
  • Latency Cost Trade-off: With 315 mobile users, a 202.5-unit long-term migration-cost budget, and β = 0.1, average latency decreases with V and approaches a minimum for both proposed algorithms.The latency evaluation varies the control parameter V under multiple online algorithms.
  • Latency Cost Trade-off: At V = 1000, CA and DA improve average latency by approximately 8% to 56% over the benchmarks.The AM strategy performs poorly because only almost two-thirds of MEC nodes provide all user services during every time slot.
  • Latency Cost Trade-off: The latency-cost trade-off follows [O(1/V), O(V)]: increasing V lowers time-averaged latency while increasing the migration-cost queue backlog approximately linearly.CA has slightly better queue-backlog performance than DA at large V.
  • Latency Cost Trade-off: Average migration cost decreases over time and gradually converges to the migration-cost budget, although large V can violate the budget over finite horizons.When the migration backlog is large, CA prioritizes reducing it; when small, it prioritizes minimizing latency.
  • Latency Cost Trade-off: As V increases, latency-performance distributions become more centralized around the median, consistent with dynamic adjustment of the migration backlog queue.This behavior is reported for the two proposed algorithms.

D. Efficient on different dense networks

The proposed algorithms remain effective as user density increases, while computation delay becomes the dominant source of latency growth. The distributed scheme also reduces placement-update running time, especially with many users.

  • D. Efficient on different dense networks: The two proposed algorithms continue to work efficiently across networks with different user-to-MEC density ratios.Higher user density increases computation delay, which is identified as the main factor behind rising perceived latency.
  • D. Efficient on different dense networks: Service migration balances edge load and slows the growth of total perceived latency as user density increases.Computation delay grows significantly faster than total perceived latency, while network propagation delay is unaffected by user amount.
  • D. Efficient on different dense networks: Maintaining the original quality of service in denser networks requires the operator to increase edge computation capacity.This follows from the reported growth of computation delay with user density.
  • D. Efficient on different dense networks: The distributed DA scheme dramatically reduces placement-decision running time compared with centralized CA, especially when the user population is large.Asynchronous best-response updates converge faster to an equilibrium, supporting DA’s efficiency in large-scale ultra-dense networks.
Loading 1809.05239v1…