PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Cell Mobile Edge Computing: Joint Service Migration and Resource Allocation

Zezu Liang, Yuan Liu, Tat-Ming Lok, Kaibin Huang

arXiv:2102.03036v1cs.ITmath.IT

TL;DR

MEC handover alone does not account for service migration, computing-resource variation, and migration cost, which complicate efficient mobility support. The paper relaxes binary migration decisions, solves the relaxed problem iteratively, and recovers integer decisions using a problem-structured rounding method. For λ ∈ [0.8, 5], the proposed algorithm achieves over 50% offloading-rate improvement versus the no-migration scheme while maintaining JMH cost less than half of maximum JMH cost consumption.

  • Problem

    MEC handover alone does not account for service migration, computing-resource variation, and migration cost, which complicate efficient mobility support.

    Source: §I · p. 2

  • Method

    The paper relaxes binary migration decisions, solves the relaxed problem iteratively, and recovers integer decisions using a problem-structured rounding method.

    Source: C. Our Contributions · p. 4

  • Results

    For λ ∈ [0.8, 5], the proposed algorithm achieves over 50% offloading-rate improvement versus the no-migration scheme while maintaining JMH cost less than half of maximum JMH cost consumption.

    Source: A. JMH in a General Multi-cell MEC… · p. 26

  • Takeaways & Limitations

    The results support joint migration and handover as a way to manage computation and radio resources in multi-cell MEC, with hotspot mitigation also yielding load balance below a user-load threshold.

    Source: §VI · pp. 28–29

    For the non-convex radio-resource-allocation extension, the dual-based algorithm may not attain the primal optimum because a duality gap can exist.

    Source: E. Extension: JMH with Radio Resource… · p. 19

Abstract

from arXiv · show

Mobile-edge computing (MEC) enhances the capacities and features of mobile devices by offloading computation-intensive tasks over wireless networks to edge servers. One challenge faced by the deployment of MEC in cellular networks is to support user mobility. As a result, offloaded tasks can be seamlessly migrated between base stations (BSs) without compromising the resource-utilization efficiency and link reliability. In this paper, we tackle the challenge by optimizing the policy for migration/handover between BSs by jointly managing computation-and-radio resources. The objectives are twofold: maximizing the sum offloading rate, quantifying MEC throughput, and minimizing the migration cost. The policy design is formulated as a decision-optimization problem that accounts for virtualization, I/O interference between virtual machines (VMs), and wireless multi-access. To solve the complex combinatorial problem, we develop an efficient relaxation-and-rounding based solution approach. The approach relies on an optimal iterative algorithm for solving the integer-relaxed problem and a novel integer-recovery design. The latter outperforms the traditional rounding method by exploiting the derived problem properties and applying matching theory. In addition, we also consider the design for a special case of "hotspot mitigation", referring to alleviating an overloaded server/BS by migrating its load to the nearby idle servers/BSs. From simulation results, we observed close-to-optimal performance of the proposed migration policies under various settings. This demonstrates their efficiency in computation-and-radio resource management for joint service migration and BS handover in multi-cell MEC networks.

I. INTRODUCTION

The paper addresses mobility in MEC by jointly deciding BS handover and service migration while managing computation and radio resources. Its model and algorithms account for interference and migration costs, and the authors also study hotspot mitigation.

B. Service Migration and BS Handover

C. Our Contributions

  • The optimization maximizes weighted sum offloading rates while reducing migration cost, accounting for I/O and multi-user interference.The paper models each user as served by a dedicated VM that migrates with the user’s BS association.Source: C. Our Contributions · p. 4, A. System Model · pp. 5–6
  • The proposed two-stage method relaxes binary migration decisions for fractional programming, then uses problem properties to recover binary decisions more effectively than naive rounding.The paper describes the original problem as an integer nonlinear program that is difficult to solve exactly at large network sizes.Source: C. Our Contributions · p. 4
  • Hotspot mitigation migrates load from an overloaded server to helper servers; below a threshold it can achieve load balance, while above it all servers remain overloaded and more helpers are needed.The contribution is presented as a special JMH design case.Source: C. Our Contributions · p. 4

A. System Model

  • The system uses time slots with fixed user-BS associations and channel gains within each slot, while those conditions can vary between slots.Each user has a dedicated VM, and its service VM migrates when the user switches BSs.Source: A. System Model · p. 5

1) Communication Model:

  • With fixed transmit powers and frequency reuse factor 1, the model treats each user’s uplink transmission rate as deterministic and omits result downloading because computation results are relatively small.Radio-resource allocation among users is deferred to a later extension.Source: 1) Communication Model · p. 6

2) Computation Model:

  • Co-locating more users can increase parallel-computing multiplexing gain but reduces individual computation rates through I/O interference, subject to each BS’s VM capacity.Offloading rate measures offloadable bits per unit time and reflects both transmission and computation time.Source: 2) Computation Model · p. 7

B. Problem Formulation

The formulation selects user-to-BS service placements to trade off weighted offloading rates against migration cost under assignment and capacity constraints. The solution relaxes binary decisions and uses iterative fractional programming to solve the resulting problem.

B. Problem Formulation

  • The objective trades off weighted user offloading rates against total JMH cost, subject to one-BS-per-user and per-BS user-capacity constraints.Feasibility requires total BS capacity to be at least the number of users.Source: B. Problem Formulation · pp. 7–8
  • The binary placement variables make the problem an integer nonlinear program; brute force has O(N^K) complexity, motivating a low-complexity suboptimal algorithm.The paper reports close-to-optimal performance in simulations.Source: B. Problem Formulation · p. 8

III. ALGORITHM DEVELOPMENT

  • The algorithm relaxes binary placement variables to [0, 1] and introduces y_n to represent the number of VMs accommodated at BS n.The relaxed problem provides an upper bound on the original problem.Source: A. Continuous Relaxation and… · pp. 8–9

B. Problem Formulation

A. Continuous Relaxation and Fractional Programming Transform

  • A sufficiently large constant Z shifts the objective into a sum of non-negative functions, enabling the sum-of-ratios algorithm; at optimum, y_n reaches its lower bound on assigned users.The offloading rate decreases as y_n increases.Source: A. Continuous Relaxation and… · p. 9
  • The relaxed sum-of-ratios problem is transformed into a parameterized subtractive-form problem with the same optimum at the parameter tuple satisfying the system equations.An outer iteration finds the parameters while an inner iteration solves the subtractive-form problem.Source: A. Continuous Relaxation and… · pp. 9–10
  • For fixed parameters, the subtractive-form problem is convex because its objective is concave and its constraints are linear, so convex optimization can solve it optimally.Strong duality holds, making the primal problem equivalent to its dual.Source: B. Solving Problem (P2) Given (α, β, γ) · pp. 10–11

1) Optimal JMH Policy in Dual Domain:

The inner solver decomposes a dual problem into user placement and BS load decisions, then uses subgradient updates. Because dual iterations may not yield a feasible primal optimum, the method averages primal iterates; an outer modified Newton iteration then solves the relaxed sum-of-ratios problem globally.

1) Optimal JMH Policy in Dual Domain:

  • Given dual prices, the dual function decomposes into independent user placement subproblems and BS load subproblems, with subgradient updates converging to an optimal dual solution.The stated harmonic step size is ε_t = ε/(t + 1).Source: 1) Optimal JMH Policy in Dual Domain · pp. 11–12
  • A user’s dual-domain JMH decision selects a BS with the highest revenue, defined as weighted offloading-rate profit plus modified cost minus the BS price.The BS price is its Lagrangian multiplier; ties can produce multiple maximizing BS choices.Source: 1) Optimal JMH Policy in Dual Domain · p. 11

2) Optimal Primal Solution Recovery for Problem (P2):

  • The dual solution’s associated primal variables may be suboptimal or infeasible when a user has multiple BSs tied for maximum revenue, so dual convergence alone does not ensure the required inner optimum.The issue arises because the user subproblem is a linear program and the dual function may not be differentiable at the optimum.Source: 2) Optimal Primal Solution Recovery… · p. 12
  • A weighted convex average of prior primal iterates reconstructs a feasible primal solution and converges to the optimum of the inner problem.This recovery is used alongside the dual subgradient iteration.Source: 2) Optimal Primal Solution Recovery… · p. 12
  • The outer sum-of-ratios iteration updates its parameters with a modified Newton method; with the inner problem solved optimally, it reaches the global optimum of the relaxed problem.The paper attributes the inner problem’s guarantee to convexity and its optimal algorithm.Source: C. Finding Optimal Parameters (α∗, β∗,… · pp. 13–14

D. Integer Recovery for Problem (P1)

Integer recovery must preserve the hard constraints while avoiding rounding errors that distort user offloading rates. The proposed recovery rounds the server-load vector using its structure, then optimally assigns users for the recovered vector.

D. Integer Recovery for Problem (P1)

  • Rounding user decisions independently can accumulate variance in aggregate assignments, affecting offloading rates and causing high performance loss.The recovery method instead exploits the structure of the problem to find a feasible decision with less rounding loss.Source: D. Integer Recovery for Problem (P1) · p. 14
  • For a fixed feasible integer load vector y, the problem reduces to a linear assignment problem that the Hungarian algorithm solves optimally in polynomial time.The assignment problem's integer relaxation has an integer optimum, and its complexity is O(K^3).Source: D. Integer Recovery for Problem (P1) · pp. 14–15
  • The recovered integer vector y is a closest feasible vector to fractional y′ under any q-norm with q ≥ 1.The rounding rule produces a feasible integer vector with the smallest rounding error, improving on direct rounding of user decisions.Source: D. Integer Recovery for Problem (P1) · p. 15
  • Algorithm 2 solves the relaxed problem iteratively, rounds y′, then solves the assignment problem for the recovered y.Its stated total complexity is O(T1NK/δ^2 + K^3).Source: D. Integer Recovery for Problem (P1) · p. 16

E. Extension: JMH with Radio Resource Allocation

The JMH design is extended to allocate radio resources as well as migrate services and hand over users. The extension retains the relaxation-and-rounding approach but uses a dual-based method for the coupled integer-recovery problem.

E. Extension: JMH with Radio Resource Allocation

  • The extension allocates radio resources to mitigate mutual interference when large systems assign users different sub-bands.It assumes non-overlapping BS spectra and orthogonal allocation of physical resource blocks (RBs) among each BS’s users.Source: E. Extension: JMH with Radio Resource… · p. 16
  • With RB allocation, user k’s uplink rate to BS n is bk,nηk,n, and each BS’s allocation is limited by its RB capacity Bn.A zero RB allocation gives that user zero offloading rate.Source: E. Extension: JMH with Radio Resource… · p. 17
  • The integer-relaxed extension uses the sum-of-ratios algorithm, with an additional computation of b*k,n in each iteration.For given auxiliary parameters, the relaxed problem separates into the existing (X, y) optimization and an RB-allocation problem.Source: E. Extension: JMH with Radio Resource… · pp. 17–18
  • After rounding y, the remaining coupled assignment-and-RB problem is addressed with Lagrangian relaxation and a subgradient search for its dual multipliers.The relaxed subproblem is a linear assignment problem solvable by the Hungarian algorithm; non-convexity means a duality gap may remain.Source: E. Extension: JMH with Radio Resource… · pp. 18–19

IV. HOTSPOT MITIGATION CASE

The hotspot case models a macro-BS distributing services among idle small-BSs and reduces the decision to the number of services assigned to each BS. Its solution behavior depends on whether the user count is below or above a utility-maximizing threshold.

IV. HOTSPOT MITIGATION CASE

  • The hotspot model moves some services from an overloaded macro-BS to idle small-BSs, assuming common transmission and computation rates per BS and common migration costs to each small-BS.Under these assumptions, the decision is the number of services assigned to each BS.Source: §IV · p. 19
  • When K is below the threshold, the hotspot problem admits an optimal relaxation-and-rounding solution; above it, the preceding algorithm provides an efficient suboptimal solution.The relaxed problem is convex for K ≤ K*, while the general integer nonlinear problem has no efficient exact method stated here.Source: A. Optimal Load Distribution for K ≤K∗ · p. 20, §IV · p. 20
  • The threshold-case method relaxes integer service counts, solves the resulting convex problem, then rounds to recover an integer solution satisfying the total-count constraint.The rounding rule selects among combinations based on the relaxed solution to maximize R.Source: A. Optimal Load Distribution for K ≤K∗ · pp. 20–22
  • The one-sided optimal load Jn is derived from the per-BS utility condition and can be found by bisection search.Jn is the load achieving maximum utility at BS n.Source: A. Optimal Load Distribution for K ≤K∗ · p. 20
  • For K < K*, optimal loads are at or below each BS’s one-sided optimal load Jn; for K > K*, they are at or above Jn.At K = K*, the optimal load at every BS equals Jn.Source: A. Optimal Load Distribution for K ≤K∗ · p. 21
  • Network utility increases with K up to K*, and utility at K* exceeds utility for any K > K*.K* is the optimal number of users the network can accommodate for maximum utility.Source: A. Optimal Load Distribution for K ≤K∗ · p. 21
  • For K > K*, all BSs remain overloaded after optimal migration, so additional small-BSs are needed to increase network capacity.For K < K*, resources are under-utilized after optimal migration, and adding users can increase utility.Source: A. Optimal Load Distribution for K ≤K∗ · p. 21

V. SIMULATION RESULTS

The simulations use seven BSs in a 1 km² area and model user movement with Random Waypoint Mobility. The section’s Fig. 3 presents sum utility against the number of users K.

V. SIMULATION RESULTS

  • The simulation places N = 7 BSs in a 1 km² square area with a regular hexagonal-lattice layout.Users are initially distributed randomly, with BS associations initialized by max-SINR association.Source: §V · p. 23
  • User locations evolve under the Random Waypoint Mobility model, with velocities drawn uniformly from 0 to 5 m/s.The static probability and pause time are both set to zero.Source: §V · p. 23
  • Fig. 3 plots sum utility against the number of users K.Source: Figure 3 · p. 24

A. JMH in a General Multi-cell MEC System

The proposed policy approaches the utility upper bound and remains robust across interference and mobility settings, while its migration-cost weight lets operators trade off offloading gains against JMH cost.

A. JMH in a General Multi-cell MEC System

  • As d increases, the proposed algorithm’s sum utility descends slowest; radio-oriented migration is close when d is small but drops sharply as d grows.The degradation factor is identical across BSs, d_n = d.Source: Figure 4 · p. 24, A. JMH in a General Multi-cell MEC… · p. 25
  • At K=90, the proposed algorithm gains about 34% utility over radio-oriented migration, approaches the upper bound, and both migration schemes beat no migration.The upper-bound comparison is reported for the proposed algorithm; the 34% gain is over radio-oriented migration.Source: A. JMH in a General Multi-cell MEC… · pp. 24–25
  • As vmax rises, the proposed policy resists utility loss while its migrated-user share rises more slowly and remains lower than radio-oriented migration.No migration’s utility falls sharply with increasing vmax; even at vmax = 0, flexible migration policies gain over no migration because wireless fading varies over time.Source: Figure 5 · p. 25, A. JMH in a General Multi-cell MEC… · pp. 25–26
  • For λ ∈ [0.8, 5], offloading-rate improvement exceeds 50% versus no migration while JMH cost stays below half its maximum.A small λ prompts more migrations and higher JMH cost; increasing λ suppresses migrations with little rate improvement but high cost.Source: Figure 6 · p. 26, A. JMH in a General Multi-cell MEC… · p. 26
  • In the radio-resource allocation case, utility rises with K when small and declines slowly from K ≥ 40, while the proposed algorithm outperforms no migration.VM multiplexing helps at small K, whereas I/O interference dominates at larger K; the proposed algorithm mitigates interference more effectively than no migration.Source: Figure 7 · p. 26, A. JMH in a General Multi-cell MEC… · pp. 26–27

B. Hotspot Mitigation Case

In the hotspot-mitigation case, the proposed scheme matches exhaustive-search utility and outperforms no migration, while its load-balancing benefits depend on the user-load regime. At the highest loads, insufficient helper BSs leave imbalance, and adding BSs is needed.

B. Hotspot Mitigation Case

  • Stage I (K ≤ 12) has rising utility without migration because the macro-BS remains under-utilized.Source: B. Hotspot Mitigation Case · p. 27
  • In Stage II (12 < K ≤ 32), migration to helper BSs sustains utility growth, reaching a maximum at K = 32 when BS loads are approximately at their one-side optimal levels.Source: B. Hotspot Mitigation Case · pp. 27–28
  • The proposed algorithm achieves exhaustive-search optimal utility for all K and improves on no migration by extending utility growth and slowing its later decline.Source: B. Hotspot Mitigation Case · p. 27, Figure 8 · p. 28
  • In Stage III (32 < K ≤ 44), utility starts to fall, while the optimal migration scheme distributes load in a balanced manner with each BS slightly above its optimal load.Source: B. Hotspot Mitigation Case · p. 28
  • In Stage IV (K > 44), load imbalance persists: unwanted load is concentrated on one BS, indicating that available helper BSs cannot accommodate the services.Source: B. Hotspot Mitigation Case · p. 28

VI. CONCLUSIONS

  • The paper concludes that communication dominates with few users, computation becomes key at high user counts because of I/O interference, and load balance has a user-count threshold.Source: §VI · p. 29

APPENDIX A. Proof of Theorem 1

The appendix proves the equivalence of an auxiliary-variable transformation and establishes a rounding rule for recovering integer workloads. The rounding proof selects ceilings to satisfy the workload sum while minimizing rounding error.

APPENDIX A. Proof of Theorem 1

  • Introducing β and γ transforms P1′ equivalently, with the resulting optimum linked to the KKT conditions of Problem (14).Source: A. Proof of Theorem 1 · p. 29
  • The proof invokes Fritz-John optimality conditions to obtain conditions corresponding to (15)–(17).Source: A. Proof of Theorem 1 · p. 29

B. Proof of Proposition 1

  • The integer recovery rounds up the required number of fractional workloads with the largest rounding-error reductions, while meeting the sum constraint and BS capacity bounds.Source: B. Proof of Proposition 1 · pp. 30–31

C. Proof of Proposition 2

The proof establishes workload-allocation properties around K*, then uses them to show that network utility rises with user count up to that threshold. At K*, the relaxed optimum upper-bounds utility for every K.

C. Proof of Proposition 2

  • Each BS's utility is maximized at its one-side optimal load Jn, and this allocation yields the maximum sum utility when the user constraint is met.Source: C. Proof of Proposition 2 · p. 31
  • For K < K*, an optimal workload allocation does not exceed Jn at any BS; otherwise, shifting load can improve utility while meeting the total-load constraint.Source: C. Proof of Proposition 2 · p. 31
  • R(K) increases monotonically for K in [0, K*], while R(K*) is an upper bound on R(K) for every K.Source: C. Proof of Proposition 2 · p. 32

D. Proof of Proposition 3

The proof applies a rounding theorem for integer programming to the relaxed workload solution. Strict concavity of R in each workload variable supplies the condition needed for that theorem.

D. Proof of Proposition 3

Related papers

Loading 2102.03036v1…