PaperlayerView exact revision on arXiv

Source-linked AI summary

Dynamic Service Migration in Mobile Edge Computing Based on Markov Decision Process

Shiqiang Wang, Rahul Urgaonkar, Murtaza Zafer, Ting He, Kevin Chan, Kin K. Leung

arXiv:1506.05261v2cs.DCcs.NImath.OC

TL;DR

Service migration in mobile edge computing must balance migration overhead against increased transmission delay under uncertain user mobility. The paper formulates this problem as an MDP, reduces the state to user-service distance, and develops efficient solution methods. The distance model is exact for uniform one-dimensional mobility, has constant-bounded error for uniform two-dimensional mobility, and performs well on real-world taxi traces.

  • Problem

    MEC service migration requires deciding when and where to migrate despite uncertain mobility and competing migration and distant-transmission costs.

  • Method

    The paper uses a general-cost MDP, approximates its state space with user-service distance, and develops closed-form and modified policy-iteration solution methods.

  • Results

    The distance-based MDP is exact for uniform 1-D mobility, has constant-bounded error for uniform 2-D mobility, and achieves average cost reductions of up to 44% against never/always-migrate or myopic policies.

  • Takeaways & Limitations

    The approach provides an efficient service-migration solution that remains effective when practical conditions such as incomplete edge-server coverage and capacity limits are included.

Abstract

from arXiv · show

In mobile edge computing, local edge servers can host cloud-based services, which reduces network overhead and latency but requires service migrations as users move to new locations. It is challenging to make migration decisions optimally because of the uncertainty in such a dynamic cloud environment. In this paper, we formulate the service migration problem as a Markov Decision Process (MDP). Our formulation captures general cost models and provides a mathematical framework to design optimal service migration policies. In order to overcome the complexity associated with computing the optimal policy, we approximate the underlying state space by the distance between the user and service locations. We show that the resulting MDP is exact for uniform one-dimensional user mobility while it provides a close approximation for uniform two-dimensional mobility with a constant additive error. We also propose a new algorithm and a numerical technique for computing the optimal solution which is significantly faster than traditional methods based on standard value or policy iteration. We illustrate the application of our solution in practical scenarios where many theoretical assumptions are relaxed. Our evaluations based on real-world mobility traces of San Francisco taxis show superior performance of the proposed solution compared to baseline solutions.

I. INTRODUCTION

Mobile edge computing reduces service access delay by placing cloud-capable servers near users, but mobility creates a service migration problem involving uncertain movement and competing migration and transmission costs. The paper addresses this problem with an MDP framework covering general costs, multidimensional mobility, efficient solution methods, and practical trace-driven evaluation.

  • Motivation: MEC places cloud-capable edge servers near network entities such as base stations to reduce service access delay.This supports delay-sensitive and data-intensive mobile applications.
  • Problem: User movement can require migrating services to preserve MEC benefits, but migration causes interruption and network overhead while non-migration increases transmission delay.The decision must balance migration and distant-transmission costs under uncertain mobility.
  • Related Work: Prior work considered Markovian mobility without migration decisions, restricted MDP migration studies, or one-dimensional mobility with specific or constant costs.The paper identifies two-dimensional mobility and general cost models as missing from earlier MDP-based work.
  • Contributions: The paper proposes an MDP formulation with general cost models and approximates its large state space using user-service distance.The distance approximation is exact for uniform one-dimensional mobility and supports two-dimensional models with bounded error.
  • Evaluation: The proposed approach is applied to realistic San Francisco taxi traces involving multiple users, incomplete edge-server coverage, and limited service capacity.The practical evaluation compares the proposed policy with baseline approaches.

B. Performance Objective

The paper models migration as an infinite-horizon discounted-cost MDP whose actions choose whether and where to move the service. Structural properties then motivate a distance-based MDP with distance-dependent migration and transmission costs.

  • Control Decisions and Costs: A system state records the user and service locations, and an action selects a new service location or leaves the service unmigrated.Migration cost depends on service displacement, while transmission cost depends on the post-action user-service distance.
  • Performance Objective: The objective is to minimize long-term expected discounted total cost under deterministic policies and random user locations.The discount factor satisfies 0 < γ < 1.
  • Performance Objective: The optimal solution is a stationary policy obtained from the Bellman equation for an infinite-horizon discounted-cost MDP.A stationary policy uses the same decision rule in every timeslot.
  • Structural Properties: An optimal action never places the service farther from the user than its current location.When migration and transmission costs are constant for positive distances, migrating anywhere other than the user’s current location is not optimal.
  • Distance-Based MDP: The distance-based MDP uses user-service distance as its state, limits attention to distances from 0 through N, and forces migration when distance reaches N.The post-action distance determines the next-state transition through the mobility model.
  • Distance-Based MDP: The one-timeslot cost is b(|d(t) − d′(t)|) + c(d′(t)), with migration constrained along the shortest path between user and service.This representation applies to one-dimensional mobility and to suitable two-dimensional distance metrics.
  • Cost Functions: Migration and transmission costs are modeled in constant-plus-exponential forms that can represent varied realistic cost shapes and approximate arbitrary cost functions.Their parameters control distance effects while preserving nonnegative, non-decreasing costs.

B. Closed-Form Solution to Discounted Sum Cost

The paper derives the discounted cost for a fixed policy through balance equations and interval-wise difference equations. Unknown interval coefficients are determined recursively, yielding a closed-form value function computable across all distance states.

  • 1) Problem Formulation with Difference Equations:: The discounted sum cost for a policy satisfies a balance equation derived from the distance-based MDP recursion.The formulation uses d(0) = d as shorthand when evaluating the value function.
  • 1) Problem Formulation with Difference Equations:: For migration states n_k, the value function on each interval [n_{k−1}, n_k] has an interval-specific closed-form expression.The expression applies to every distance in the interval under the given policy.
  • 1) Problem Formulation with Difference Equations:: The interval solution uses constants A_k and B_k together with coefficients m_1, m_2, D, and H determined by model parameters.The coefficients include combinations of transition, migration, transmission, and discount parameters.
  • 1) Problem Formulation with Difference Equations:: The closed-form interval expression is obtained by solving the associated difference equation.The paper refers the detailed derivation to its appendix.
  • 2) Finding the Coefficients:: Additional constraints connect value expressions across migration states and determine the unknown coefficients for each interval.Actions mapping one state to another provide relations used alongside the interval solution.
  • 2) Finding the Coefficients:: For the initial interval [0, n_0], two constraints determine A_0 and B_0 from the balance equation and the boundary relation.The constraints are represented by equations (13) and (14).
  • 2) Finding the Coefficients:: For each later interval [n_{k−1}, n_k], one constraint comes from the preceding boundary and a second depends on the relative migration state.The cases distinguish whether a(n_k) is at or below n_{k−1}.
  • 2) Finding the Coefficients:: The resulting value function is closed-form for all d ∈ [0, N] and can be evaluated numerically in O(N) time.This follows after expressing the interval coefficients in closed form.

3) Solution is in Closed-Form:

To compute the optimal policy efficiently, the paper replaces Gaussian elimination within policy iteration with the derived difference-equation solution and restricts candidate actions using structural results.

  • C. Algorithm for Finding the Optimal Policy: Value iteration may require many iterations, while policy iteration commonly computes each policy’s value function by solving a linear system.Gaussian elimination gives this computation complexity O(N^3).
  • C. Algorithm for Finding the Optimal Policy: The modified policy-iteration algorithm computes V(d) using the closed-form difference-equation result instead of Gaussian elimination.It also restricts actions to migrating toward lower states or not migrating.
  • C. Algorithm for Finding the Optimal Policy: Only migration to lower distance states or no migration needs to be checked, based on the structural theorem.This action restriction further reduces the policy search space.
  • C. Algorithm for Finding the Optimal Policy: The algorithm solves coefficient systems using either equation (16) or equation (17), depending on the applicable interval case.The resulting coefficients are then used to obtain V(d) for the interval.
  • C. Algorithm for Finding the Optimal Policy: The method reduces complexity relative to policy iteration and avoids the long convergence time associated with standard value iteration.Its per-iteration complexity is stated in the paper’s complete algorithm description.

V. APPROXIMATE SOLUTION FOR 2-D MOBILITY

The paper approximates the 2-D offset-based MDP with a distance-based MDP, maps its optimal policy back to the 2-D model, and analyzes the resulting error and computational savings.

  • A. Offset-Based MDP: The 2-D offset model represents user-service displacement on hexagonal cells using rings indexed by distance and polar state indices.States with equal hop distance from the service form a ring; the distance is the minimum number of hexagonal-cell hops.
  • A. Offset-Based MDP: The 2-D offset model has M = 3N^2 + 3N states excluding the origin, substantially more than the distance-based model and motivating the approximation.This state-space reduction significantly lowers computational time.
  • A. Offset-Based MDP: The distance-based approximation uses p0 = 6r, p = 2.5r, and q = 1.5r to match aggregate transitions between rings.The higher- and lower-ring probabilities vary across offset states, so p and q use their median values.
  • A. Offset-Based MDP: The optimal distance-based policy is mapped to the 2-D model by selecting shortest paths between rings, preserving migration and transmission costs.For a state in ring i, a destination in ring i′ can be reached in |i − i′| hops, and states within a ring have equal transmission cost.
  • C. Bound on Approximation Error: The approximation error comes from transition-probability differences of at most 0.5r, with a constant bound that increases with γ while relative error can remain low.The bound is worst-case; numerical evaluation instead studies average approximation performance under 2-D random walks.
  • D. Numerical Evaluation: The proposed method takes about 0.1% of the computation time of standard value or policy iteration while producing discounted sum costs very close to optimal.For N = 10, the 2-D model has M = 330 states; the proposed algorithm has O(N^2) complexity versus approximately O(M^2) per standard iteration.
  • D. Numerical Evaluation: Baseline policies approach optimal cost in different migration-cost regimes: always-migrate when |β_l| is small and never-migrate when |β_l| is large.Small migration costs make migration beneficial in most cases, whereas large migration costs favor not migrating.

VI. APPLICATION TO REAL-WORLD SCENARIOS

The paper adapts its distance-based MDP to practical systems with changing mobility, incomplete edge-server deployment, and service-capacity limits. It combines periodic parameter estimation with heuristic placement and migration updates to produce deployable decisions.

  • VI. APPLICATION TO REAL-WORLD SCENARIOS: The practical formulation accounts for missing edge servers, finite service capacity, and multiple users and services, but the resulting constrained MDP is substantially harder to solve.A heuristic placement procedure is therefore used instead of a full theoretical analysis of the constrained model.
  • VI. APPLICATION TO REAL-WORLD SCENARIOS: The transition parameter r is estimated from recent observations, while cost parameters are computed from current base-station, network, and edge-server measurements.The controller averages empirical cell-level movement probabilities and updates the model periodically.
  • VI. APPLICATION TO REAL-WORLD SCENARIOS: The procedure updates service placement at the start of each timeslot and performs migration when needed.Base stations report user movement and the controller sends updated placement instructions to edge servers.
  • VI. APPLICATION TO REAL-WORLD SCENARIOS: Every Tu timeslots, the controller recomputes model parameters and the optimal distance-based policy using measurements from the previous Tw slots.This allows the MDP and algorithm to adapt to changing network and user dynamics.
  • C. Service Placement Update: The placement heuristic initially ignores edge-server capacity, then reassigns services whose assigned edge server exceeds its capacity.New services are placed on the closest available edge server before capacity corrections are applied.
  • C. Service Placement Update: For initialized services, the policy selects migration actions by minimizing immediate and future discounted costs subject to the existence of a suitable edge server.When all base stations have edge servers, this action matches the distance-based MDP optimum; otherwise, it may differ.

D. Performance Analysis

The performance analysis studies estimation accuracy and the cost impact of practical action constraints. It establishes unbiasedness and variance behavior for the mobility estimator, then bounds the loss from constrained migration choices.

  • D. Performance Analysis: The analysis assumes an infinite 2-D mobility space, while real deployments have finitely many cells and boundary cells with fewer neighbors.At boundaries, the probability assigned to each neighboring cell is larger than r under the stated model.
  • 1) Estimation of Parameter r: E{r̂} = r: under the 2-D random-walk model, the estimated transition parameter is unbiased.The paper interprets this as supporting accurate long-term estimation of the true mobility parameter.
  • 1) Estimation of Parameter r: Var{r̂} ≤ 1/(144N_BS T_w): the estimator’s variance upper bound decreases inversely with the observation-window length T_w.This result assumes the stated user-independence condition and ideal 2-D random-walk mobility.
  • 1) Estimation of Parameter r: The ideal random-walk mobility model may not hold precisely in practice, and r may vary over time or across geographic areas.The paper therefore uses an estimation procedure designed to accommodate possible model violations.
  • 1) Estimation of Parameter r: The estimation procedure weights cells and timeslots equally, rather than pooling all user samples, to accommodate imbalanced observations and possible mobility-model violations.The alternative pooled estimator may have lower variance, but the proposed weighting preserves fairness across cells and slots.
  • 2) Cost Difference Due to Additional Constraints: The constrained policy’s excess discounted cost is bounded when deviations from the optimal action are bounded by K.The deviation distribution depends on edge-server availability, capacity constraints, and system load; larger K corresponds intuitively to more restrictive conditions.

E. Trace-Driven Simulation

The trace-driven evaluation applies the migration framework to San Francisco taxi mobility under realistic placement, capacity, and load conditions. The proposed approach generally achieves lower costs than baseline policies, while constrained resources narrow its advantage.

  • Trace-driven setup: 536 San Francisco taxis are modeled as independent users requesting independent services in simulations based on real-world mobility traces.The traces were collected on May 31, 2008, with different numbers of active taxis across the day.
  • Trace-driven setup: The simulation includes hexagonal and real base-station placements, varying numbers of edge servers, and different service capacities per edge server.The default configuration uses 100 base stations with edge servers, each hosting at most 50 services.
  • Cost models: The cost model combines user-service distance with system-load effects, including queueing-related delay through resource-availability parameters R_t and R_p.Both non-constant and constant migration/transmission cost definitions are evaluated.
  • Results: The proposed approach gives lower costs than other approaches in almost all tested cases.The comparison includes always-migrate, never-migrate, and myopic policies, with instantaneous and daily average costs reported.
  • Results: When edge-server count or capacity is small, the proposed approach approaches never-migrate and myopic policies because better service locations are rarely available.The instantaneous-cost fluctuation reflects changes in the number of active taxis over the day.
  • Practical extensions: The discussion extends the framework beyond its simplifying assumptions by allowing richer cost models, additional MDP dimensions, multiple users, distributed control, and non-co-located edge servers.Adding network, edge-server, or service-state dimensions increases the state space and creates a complexity–accuracy tradeoff.

APPENDIX A PROOF OF THEOREM 1

The appendix proves that migrations farther from the user can be removed without increasing cost, then develops analytic and numerical procedures for related cost and value calculations. These constructions support efficient policy analysis under the paper’s MDP model.

  • Theorem 1 proof: For any policy that migrates farther from the user, a policy can be constructed that removes such migrations without increasing total cost.The construction preserves earlier and later actions while replacing an interval of migrations with a later migration when needed.
  • Theorem 1 proof: The replacement policy can be constructed without prior knowledge of future user locations.It reacts to the underlying policy’s migration actions and the first later time when the relevant distance condition holds.
  • Theorem 1 proof: History-dependent replacement policies cannot outperform Markovian policies for this problem, yielding a Markovian policy with the same no-farther-migration property.The conclusion assumes identical action spaces for all possible states.
  • Cost-function approximation: The migration cost function is approximated by a constant-plus-exponential form, b(x) = β_c + β_lµ^x, using numerically selected parameters.Two possible parameter sets are compared by their sum squared error, and the lower-error set is chosen.
  • Cost-function approximation: The appendix illustrates approximation results for logarithmic, square-root, and quadratic cost functions.These examples appear in Figure A.1.

APPENDIX D PROOF OF THEOREM 2

Theorem 2 is established by modifying the two-dimensional MDP’s transition probabilities, bounding the resulting cost difference, and identifying the modified process with the distance-based MDP. The construction uses ring-based state aggregation.

  • Proof construction: The proof first modifies transition probabilities in the original two-dimensional MDP to even out differences in neighboring-cell counts.The modified MDP retains the original state connectivity but changes transition probabilities.
  • Cost comparison: The proof bounds the difference between discounted sum costs in the original and modified two-dimensional MDPs under a common policy.The original and modified value functions are denoted V(i,j) and U(i,j), respectively.
  • Distance-based equivalence: The modified two-dimensional MDP is shown to be equivalent to the distance-based MDP when transitions are considered by ring index.This equivalence supplies the link between the two-dimensional process and the reduced state representation.
  • Proof construction: In the modified MDP, transitions within the same ring have probability r, while transitions to lower and higher rings use adjusted probabilities.The adjustments depend on whether a state has one, two, or three neighboring cells in the adjacent ring.
  • Distance-based equivalence: Figure A.2 illustrates the original and modified two-dimensional MDPs using exemplar states and transition probabilities.The figure presents the original model and its modified counterpart side by side.

Part I – Upper bound on the difference between V (i, j) and U(i, j) for a given policy π

This part bounds the discounted-cost difference between the original and modified 2-D MDPs under a shared policy, then shows that the modified MDP’s optimal policy reduces to the distance-based MDP.

  • The balance equations compare discounted costs under the original and modified MDPs while using the same policy and value-function notation.The modified MDP transition probabilities enter explicitly in the expectation terms.
  • The transition-probability discrepancy is localized to lower and higher rings, whose probability differences have opposite signs and magnitude 0.5r distributed across neighbors.When ia(i,j)=0, the transition probabilities coincide and the discrepancy term vanishes.
  • The triangle inequality and two-hop-neighbor restriction replace the transition-weighted value differences with a maximum over relevant neighboring states.This yields the recursive upper-bound relation for |U(i,j)−V(i,j)|.
  • The resulting bound satisfies a discounted fixed-point equation, with alternative bounds ϵV and ϵU and overall bound ϵ=min{ϵV,ϵU}.The convergence argument uses 0<γ<1 and the convergent value differences between neighboring states.
  • Value iteration preserves equal value functions within each ring and gives optimal actions with the same ring index across states sharing that ring.This symmetry enables the optimal modified-2-D policy to map one-to-one to a policy for the distance-based MDP.
  • The distance-based policy is obtained through a value-iteration update that removes the location index j because costs and transition probabilities are ring-symmetric.The mapping uses shortest paths between states in the modified 2-D MDP.

Part III – Error bound for distance-based approximation

This part transfers the shared-policy cost bound to optimal policies, establishing an additive error relationship between the original 2-D MDP and its distance-based approximation.

  • The true optimal cost comes from the optimal policy of the original 2-D MDP, whereas the approximate optimal cost applies the distance-based policy through the modified 2-D MDP.The modified and distance-based MDPs have equivalent optimal policies.
  • The cost difference under the original optimal policy is bounded by ϵV, the upper bound obtained for the shared-policy comparison.This follows from applying the same policy to the original and modified MDPs.
  • Optimality supplies the remaining inequalities because an optimal policy cannot have higher cost than any alternative policy.The proof compares the original optimal policy with the approximate policy and the modified-MDP optimum.
  • The final additive error bound combines the shared-policy bound with the optimal-policy comparisons and the equivalence between the modified and distance-based MDPs.The proof concludes after substituting the intermediate bounds.

APPENDIX G PROOF OF THEOREM 5

This appendix derives the variance behavior of the estimator r̂ under the random-walk mobility model and explains why unconditional variance is difficult to obtain.

  • The estimator conditions on M, the collection of user counts across base stations and time slots used as samples.The sample set is random because user mobility is random.
  • Lemma 1 gives the conditional variance of r̂ when M is fixed, using conditional expectations and independence assumptions.The conditional expectation equals r, so the between-sample conditional-mean variance is zero.
  • Given the user counts, the number of users leaving a cell follows a binomial distribution under the stated random-walk assumptions.The conditional model uses the current cell count and departure probability 6r.
  • The unconditional variance is difficult to derive because the finite hexagonal mobility model’s stationary distribution is hard to obtain and the sample size is random.Despite this limitation, the lemma indicates the gap between r̂ and r and supports Theorem 5.
  • M Var{r̂|M} ≤ 1/(144N_BS T_w), providing a bound on the conditional estimator variance.The bound follows by substituting the preceding variance expressions.

APPENDIX H PROOF OF THEOREM 6

This appendix analyzes the modified transition process induced by randomized actions and bounds its value-function difference from the original distance-based MDP.

  • For the original distance-based MDP, transitions have zero probability when the next distance differs from the post-action distance by more than one.This local transition structure is used to restrict the error analysis.
  • The randomized distance-based MDP is equivalent to one following the optimal action with modified transition probabilities.The two processes share states but differ in transition probabilities.
  • The modified transition expression depends on ν=1−p−q and Δt=d(t+1)−d′(t), with separate boundary and interior cases for N≥5.For smaller N, analogous expressions are stated to apply without being detailed.
  • The value difference is analyzed through Ψ, the difference between modified and original transition probabilities, and the resulting balance equation.Positive and negative contributions to Ψ are separated in the proof.
  • Because the discounted value functions converge for 0<γ<1, the bound ϵ can be solved from the resulting fixed-point relation.The proof uses the bounded transition support and convergence of both value iterations.

APPENDIX I ADDITIONAL SIMULATION RESULTS WITH REAL-WORLD

The proposed method yields positive average cost reductions over alternative migration policies across varied simulation parameters, reaching up to 44% under default settings. Benefits narrow when ES capacity or the number of ESs is small, while the discount factor trades off instantaneous and long-term costs.

  • Cost reductions: Up to 44% average cost reduction is achieved against never-migrate, always-migrate, or myopic policies under default ES settings.Cost reduction is defined as (C0 − C)/C0, where positive values favor the proposed method.
  • Parameter effects: Small ES counts or low per-ES capacity reduce the advantage over never-migrate and myopic policies because migration opportunities become scarce.The proposed method still outperforms these baselines on average with positive cost reduction.
  • Parameter effects: Always-migrate becomes relatively less competitive when the action space is small because it continues paying migration costs without clear benefits.This explains why its comparative cost reduction can increase in constrained settings.
  • Variability: Average performance is best in almost all cases, but instantaneous costs can exceed baseline costs in some instances.The error bars represent standard deviations of cost reductions computed from instantaneous costs across times of day.
  • Variability: With γ = 0.9, the method minimizes discounted sum cost rather than instantaneous cost at every timeslot.Setting γ = 0 makes the algorithm equivalent to the myopic policy, allowing the balance to be adjusted.
Loading 1506.05261v2…