PaperlayerView exact revision on arXiv

Source-linked AI summary

EMM: Energy-Aware Mobility Management for Mobile Edge Computing in Ultra Dense Networks

Yuxuan Sun, Sheng Zhou, Jie Xu

arXiv:1709.02582v1cs.ITcs.NI

TL;DR

The paper addresses user-centric mobility management in MEC-enabled ultra-dense networks under incomplete information and a long-term user-energy constraint. It combines Lyapunov optimization with multi-armed bandits for online BS selection, including learning and volatile BS availability. The algorithms achieve close-to-optimal delay while satisfying the user’s energy consumption constraint.

  • Problem

    MEC-enabled ultra-dense networks make mobility management difficult because radio access and computing services are co-provisioned, with future and BS-side information unavailable.

  • Method

    EMM integrates Lyapunov optimization for energy-aware online decisions with MAB-based learning of suitable BSs under limited BS-side information.

  • Results

    Close-to-optimal delay performance is achieved while satisfying the user’s energy consumption constraint, including comparisons with oracle and benchmark algorithms.

  • Takeaways & Limitations

    The framework supports user-centric MM with GSI or LSI and can handle candidate BSs that dynamically switch on and off during offloading.

Abstract

from arXiv · show

Merging mobile edge computing (MEC) functionality with the dense deployment of base stations (BSs) provides enormous benefits such as a real proximity, low latency access to computing resources. However, the envisioned integration creates many new challenges, among which mobility management (MM) is a critical one. Simply applying existing radio access oriented MM schemes leads to poor performance mainly due to the co-provisioning of radio access and computing services of the MEC-enabled BSs. In this paper, we develop a novel user-centric energy-aware mobility management (EMM) scheme, in order to optimize the delay due to both radio access and computation, under the long-term energy consumption constraint of the user. Based on Lyapunov optimization and multi-armed bandit theories, EMM works in an online fashion without future system state information, and effectively handles the imperfect system state information. Theoretical analysis explicitly takes radio handover and computation migration cost into consideration and proves a bounded deviation on both the delay performance and energy consumption compared to the oracle solution with exact and complete future system information. The proposed algorithm also effectively handles the scenario in which candidate BSs randomly switch on/off during the offloading process of a task. Simulations show that the proposed algorithms can achieve close-to-optimal delay performance while satisfying the user energy consumption constraint.

I. INTRODUCTION

Integrating MEC with ultra-dense networks complicates user-centric mobility management because radio access and computing services are co-provisioned. EMM addresses uncertain information, energy limits, and volatile candidate BS availability through online, energy-aware decisions.

  • Motivation: MEC-enabled UDN combines dense BS deployment with edge computing, offering low-latency access but complicating mobility management.Existing UDN and MEC studies are mostly separate, while integrated deployments require jointly managing radio access and computing services.
  • Challenges: User-centric MM must operate with limited candidate-BS information, including unknown radio and computation loads.Without knowing which BS offers the best performance, selecting an association is difficult.
  • Challenges: Future tasks, candidate BSs, channel conditions, and edge resources are unavailable, while the long-term energy budget couples decisions across tasks.The user must make sequential decisions without foreseeing future system states.
  • Challenges: Candidate BSs may randomly switch on or off because of decentralized deployment and BS sleeping, requiring mobility management to track good choices quickly.This volatility is particularly relevant in ultra-dense networks managed partly by end-users and operators.
  • Contributions: EMM combines Lyapunov optimization and multi-armed bandits to select BSs and handovers under an energy budget with incomplete information.The framework covers global and limited BS-side information and extends to varying BS sets through volatile-bandit learning.
  • Contributions: The analysis accounts for radio handover, computation migration, and varying candidate BSs while simulations report close-to-optimal delay under the user energy constraint.The algorithms are evaluated against an oracle with exact future information and compared with benchmark approaches.

B. Computation Task and Service Model

The model represents sequentially processed computation tasks that are offloaded to candidate BSs providing both radio access and edge computing. It combines computation, uplink transmission, handover, delay, energy, deadline, and total-budget considerations.

  • Task model: Each task is characterized by input size λm, computation intensity γm, and completion deadline Dm.Input size is measured in bits, while computation intensity specifies required CPU cycles per input bit.
  • Task model: Tasks can be divided into sequential subtasks, allowing different BSs to serve successive subtasks during mobility or changing BS availability.A subtask may trigger a switch when the current BS has weak computing capability or when BSs appear or disappear.
  • Computation service: Each BS has an MEC server, and allocated CPU frequency fm,n depends on capacity and current workload while remaining fixed during one task.The allocated frequency may change across tasks.
  • Communication and energy model: Uplink transmission delay and energy depend on the wireless channel, transmission power, bandwidth, noise, and inter-cell interference.The channel gain is treated as constant during a task when the user does not move substantially.
  • Objective and constraints: Overall delay includes computation, uplink transmission, and handover costs, while total energy accounts for processing-task offloading.Subtasks are processed in sequence, and handover cost depends on the serving-BS sequence.
  • Objective and constraints: The optimization minimizes average delay subject to a total energy budget and per-task completion deadlines.The energy cap is αB relative to battery capacity B, and each task must meet Dm.
  • Optimization challenge: Solving the formulation is difficult because it requires non-causal trip-wide information and is an integer nonlinear program.Even complete future information would not remove the formulation’s high computational complexity.

F. Oracle Benchmark and Theoretical Upper Bound

The oracle benchmark assumes accurate information about the next J tasks and solves a J-step lookahead problem. The online EMM framework uses only causal information and per-task optimization to approximate this benchmark.

  • Oracle benchmark: The oracle knows the complete future information for the next J computation tasks and supplies an upper-bound benchmark for online algorithms.Its impracticality is intentional: it provides a reference for assessing close-to-optimal online performance.
  • Oracle benchmark: The lookahead benchmark minimizes average delay over feasible MM decision sequences subject to the stated constraints.The optimal value g*r is the minimum long-term average delay achieved by the J-step lookahead problem.
  • Oracle benchmark: The user’s trip is divided into R frames of J tasks, giving M = RJ tasks, and the oracle solves a J-step lookahead problem in each frame.When R = 1, the lookahead problem becomes the original offline problem.
  • Online framework: The online framework makes each decision using only causal information and compares its performance with the oracle’s J-step lookahead.At task m, future tasks m + 1, m + 2, ... are unavailable.
  • EMM-GSI: With global state information, the user observes candidate-BS and BS-side states and can avoid handover and computation migration within a task.The selected BS is used for all subtasks when the serving-BS set remains unchanged.
  • EMM-GSI: Lyapunov optimization converts the long-term energy-coupled problem into a per-task weighted minimization of delay and energy.The virtual energy-deficit queue controls the tradeoff, and P3 has complexity O(|A(Lm)|).

B. Performance Bound

EMM-GSI provides a theoretical performance guarantee under feasible operation, while EMM-LSI uses UCB1 to learn an effective BS without initial BS-side information.

  • EMM-GSI: Under the feasibility assumption for P2, Theorem 1 provides EMM-GSI’s performance guarantee.The theorem applies for fixed J and R satisfying M = RJ.
  • EMM-GSI: The worst-case average delay is within O(1/V) of the optimal J-step lookahead delay, while energy consumption deviates by O(V) from the budget.Adjusting V balances average delay and energy consumption.
  • EMM-LSI: With only local system information, EMM-LSI augments EMM with online MAB learning to identify the optimal BS without initial BS-side information.Unknown BS-side delay and energy terms make direct solution of P3 unavailable to the user.
  • EMM-LSI: UCB1 assigns and updates an index for each candidate BS as subtasks are offloaded, supporting continuous exploration and exploitation under noisy observations.The resulting per-task computational complexity is O(K_m|A(L_m)|).

B. Algorithm Performance

The EMM-LSI analysis bounds learning-related performance loss, including suboptimal BS selection, handover, and computation migration, and establishes delay and energy guarantees.

  • Learning regret: Learning regret captures performance loss from both suboptimal BS sampling and unavoidable radio handover and computation migration.The regret is decomposed into sampling regret and handover regret.
  • Learning regret: For a task with K_m subtasks, Proposition 1 upper-bounds the UCB1 learning regret.The bound uses β and the gap δ_m,n between candidate BS performance and the optimal BS.
  • Learning regret: The learning-regret bound is logarithmic in K_m, so P3 is approximately solved within a bounded deviation W when K_m is bounded.This deviation is then incorporated into the EMM-LSI performance analysis.
  • Theorem 2: Theorem 2 guarantees EMM-LSI average-delay performance and bounds total energy deviation for fixed J and R satisfying M = RJ.The delay bound includes UJ and W terms, while the energy bound includes UJ^2, V rJg*_r, and WJ terms.
  • Theorem 2: Even without exact BS-side state information, EMM-LSI guarantees average-delay performance while keeping energy consumption within a bounded deviation from the budget.The guarantee applies despite the user learning BS information online.

C. Implementation Considerations

EMM-LSI addresses the cost of continuous learning by stopping exploration under two heuristic rules. These rules trade off identifying the best BS against handover and migration costs.

  • Continuous learning can incur large handover and migration costs when the best and second-best BSs have similar performance.UCB1 may alternate between similarly valued BSs across subtasks, increasing one-time handover costs.
  • The first heuristic stops UCB1 after Ks subtask offloading decisions and assigns remaining subtasks to the BS with the lowest learned average cost.This scheme reuses the learned BS ranking after the predetermined exploration period.
  • Choosing Ks balances the risk of committing to a suboptimal BS against the handover cost of prolonged learning.A small Ks can misidentify the optimal BS, whereas a large Ks can incur substantial handover cost.
  • A second heuristic stops learning when the learned best and second-best BSs have very similar performance.The rule uses predetermined parameters ϵ and K0 to identify near ties.
  • For randomly varying candidate BS sets, EMM-LSI-V extends EMM-LSI using the VMAB framework and characterizes its performance.The setting includes BSs switching on or off during one task’s offloading process.

A. EMM-LSI-V Algorithm

EMM-LSI-V handles candidate BSs that appear or disappear during task offloading by reusing information across invariant-set epochs. Its VUCB1 learning has logarithmic total regret in the number of subtasks, scaled by the number of epochs.

  • Algorithm motivation: Conventional UCB1 must restart learning when a new BS appears, whereas EMM-LSI-V reuses information about BSs that remain available.The varying-BS setting makes restarting inefficient because other BS states may remain unchanged.
  • Epoch model: An epoch is an interval with an invariant available-BS set, and Bm denotes the task’s unknown total number of epochs.Bm = 1 recovers the fixed-candidate-BS case.
  • VUCB1 learning: VUCB1 initializes only newly appeared BSs at each epoch while retaining information for remaining BSs.Its decision index also accounts for each BS’s appearance time.
  • Algorithm procedure: Algorithm 3 initializes task inputs, updates the virtual queue and control parameter, and applies VUCB1 during each task’s subtask offloading.The algorithm connects to newly appeared BSs, updates estimated costs and counters, then updates q(m).
  • Performance analysis: O(Bm ln Km) is the total VUCB1 regret for task m with Km subtasks and Bm epochs.Proposition 2 gives this bound for the varying-BS learning process.
  • Performance analysis: The bounded VUCB1 deviation W′ preserves a strong EMM-LSI-V performance guarantee relative to exactly solving P3.The guarantee follows by substituting W′ for the fixed-set deviation W in Theorem 2.

VI. SIMULATIONS

Simulations evaluate EMM in a 49-BS MEC-enabled UDN under video-stream workloads, comparing delay and energy against oracle and benchmark policies. Results examine control and learning parameters, showing near-optimal delay, energy-budget tradeoffs, and faster adaptation to changing BS availability.

  • Overall performance: EMM-GSI achieves delay close to the J-step Lookahead, while EMM-GSI and EMM-LSI satisfy the user energy constraint.EMM-LSI is slightly worse than EMM-GSI and outperforms Radio-LSI because it learns both radio and computation states.
  • Control parameter V: Increasing V decreases average delay but increases total energy consumption, producing the [O(1/V), O(V)] delay-energy tradeoff.The simulations use V from 10^-4 to 10 and show that energy consumption can exceed the budget when V is too large.
  • Energy budget: With intermediate energy budgets, EMM-GSI trades off average delay and energy consumption and remains very close to the J-step Lookahead.Large budgets allow optimal delay for EMM-GSI, whereas very low budgets may leave no feasible solution and violate the constraint.
  • Learning duration: Under 30% observation variance, Ks = 20 obtains the best delay performance by balancing suboptimal-BS selection against handover regret.Larger Ks reduces the probability of selecting a suboptimal BS, but excessive learning increases handover frequency and delay.
  • Dynamic BS sets: EMM-LSI-V converges faster than EMM-LSI and reduces handovers when the candidate-BS set changes across task epochs.EMM-LSI-V retains information about remaining BSs, whereas EMM-LSI restarts learning after each BS-set change.

APPENDIX A PROOF OF THEOREM 1

The proof of Theorem 1 uses Lyapunov drift analysis over task slots and J-slot frames to bound EMM-GSI performance. It derives average delay and energy-consumption guarantees by comparing EMM-GSI with a J-step lookahead algorithm.

  • The proof bounds queue evolution using the energy deficit queue, a Lyapunov function, and bounded positive queue increments.
  • A slot is defined as the duration of offloading and computation for one task.
  • The drift-plus-penalty function combines one-slot Lyapunov drift with V times task delay, where V controls the delay–energy tradeoff.
  • Summing frame-level bounds and dividing by the number of slots establishes Theorem 1’s average delay and energy-consumption results.The comparison uses an optimal J-step lookahead algorithm, while G(m) denotes EMM-GSI’s task delay or energy consumption.

APPENDIX B PROOF OF PROPOSITION 1

The proof of Proposition 1 decomposes regret into sampling and handover components. It bounds both terms using concentration arguments and combines them into the proposition’s total regret bound.

  • The analysis explicitly includes handover regret in addition to sampling regret.
  • Chernoff–Hoeffding bounds are used to control the probability of misleading utility comparisons during sampling.
  • The sampling regret and handover regret are separately upper-bounded before being added to prove Proposition 1.

APPENDIX C PROOF OF THEOREM 2

The proof of Theorem 2 applies frame-based drift bounds to EMM-LSI and compares its delay and energy consumption with the corresponding benchmark. Summation over frames yields both theorem parts.

  • The proof introduces task-level delay and energy consumption achieved by EMM-LSI as the quantities bounded in the analysis.
  • Substituting intermediate bounds into the frame inequality produces expressions involving UJ^2, VrJg*_r, and WJ.
  • Summing across frames proves Theorem 2’s energy-consumption and delay claims after the respective normalizations.

APPENDIX D PROOF OF PROPOSITION 2

The proof of Proposition 2 analyzes regret across epochs when the candidate BS set changes. It shows that per-epoch sampling and handover regret are logarithmic in the number of candidate BSs, yielding a total bound across epochs.

  • The sampling and handover regret in each epoch are each shown to be O(ln K).
  • The analysis first bounds connections to a suboptimal BS within each epoch after K_b tasks have been offloaded.
  • The proof uses normalized utility differences and concentration bounds to establish the regret estimates.
  • Across B epochs, the total regret for each task is O(B ln K).
Loading 1709.02582v1…