PaperlayerView exact revision on arXiv

Source-linked AI summary

Computation Peer Offloading for Energy-Constrained Mobile Edge Computing in Small-Cell Networks

Lixing Chen, Sheng Zhou, Jie Xu

arXiv:1703.06058v2cs.GTcs.DC

TL;DR

The paper studies how MEC-enabled SBSs can coordinate computation peer offloading despite heterogeneous stochastic workloads and individual energy constraints. It develops OPEN with Lyapunov optimization, analyzes centralized and game-based decentralized coordination, and reports improved latency and energy performance while providing bounded deviation from an oracle and bounded energy-constraint violations. The conclusion notes that OPEN assumes precise current-slot task-arrival observations.

  • Problem

    Peer offloading must manage uneven stochastic workloads while respecting limited energy resources committed by individual, self-interested SBS owners.

  • Method

    OPEN applies Lyapunov optimization to online SBS peer offloading, with centralized coordination and a decentralized peer-offloading game.

  • Results

    OPEN achieves bounded deviation from the complete-future-information oracle while bounding individual SBS energy-constraint violations and improving latency and energy performance in simulations.

  • Takeaways & Limitations

    Peer offloading can improve edge-computing performance under limited energy resources without requiring information about future system dynamics.

  • Takeaways & Limitations

    OPEN assumes precise observations of task arrival rates in the current slot, an assumption that may not hold for all network systems.

Abstract

from arXiv · show

The (ultra-)dense deployment of small-cell base stations (SBSs) endowed with cloud-like computing functionalities paves the way for pervasive mobile edge computing (MEC), enabling ultra-low latency and location-awareness for a variety of emerging mobile applications and the Internet of Things. To handle spatially uneven computation workloads in the network, cooperation among SBSs via workload peer offloading is essential to avoid large computation latency at overloaded SBSs and provide high quality of service to end users. However, performing effective peer offloading faces many unique challenges in small cell networks due to limited energy resources committed by self-interested SBS owners, uncertainties in the system dynamics and co-provisioning of radio access and computing services. This paper develops a novel online SBS peer offloading framework, called OPEN, by leveraging the Lyapunov technique, in order to maximize the long-term system performance while keeping the energy consumption of SBSs below individual long-term constraints. OPEN works online without requiring information about future system dynamics, yet provides provably near-optimal performance compared to the oracle solution that has the complete future information. In addition, this paper formulates a novel peer offloading game among SBSs, analyzes its equilibrium and efficiency loss in terms of the price of anarchy in order to thoroughly understand SBSs' strategic behaviors, thereby enabling decentralized and autonomous peer offloading decision making. Extensive simulations are carried out and show that peer offloading among SBSs dramatically improves the edge computing performance.

I. INTRODUCTION

MEC-enabled SBSs can reduce latency through peer computation offloading, but heterogeneous workloads, limited owner-committed energy, uncertainty, and coupled radio-computing resources complicate coordination. The paper addresses these challenges with OPEN, a near-optimal online framework and decentralized peer-offloading game.

  • Motivation: SBSs provide cloud-like edge computing close to users, supporting low-latency processing but with fewer resources than mega-scale data centers.Their small service areas make workloads sensitive to location, time, and user mobility.
  • Motivation: Peer offloading transfers workload from hotspot SBSs to nearby lightly loaded peers, balancing workload across geographically distributed SBSs.This cooperation is intended to enhance MEC performance and resource-utilization efficiency.
  • Challenges: Small-cell peer offloading must account for self-interested owners, stochastic workload arrivals, individual long-term energy constraints, and co-provisioned radio and computing services.These conditions couple decisions across time while requiring decisions without foreseeing the far future.
  • Contributions: OPEN uses Lyapunov optimization for online stochastic peer offloading and stays within a bounded deviation of an oracle while bounding individual SBS energy-constraint violations.The oracle is assumed to know complete future information.
  • Contributions: The paper characterizes peer-offloading strategies through marginal computation cost, formulates a Nash-equilibrium game, and quantifies strategic efficiency loss using price of anarchy.It considers both centralized coordination and decentralized autonomous coordination among SBSs.
  • Evaluation: Extensive simulations report significant improvements in latency reduction and energy efficiency from the proposed method and peer offloading.The evaluation covers various system configurations and traffic arrival patterns.

III. SYSTEM MODEL

The system models MEC-enabled SBSs connected through a LAN, serving dedicated UE sets with limited computing capabilities and making peer-offloading decisions over discretized time slots. Task arrivals vary over time and are represented using Poisson processes, with expected input size and CPU-cycle requirements characterizing each task.

  • A. Network model: N SBSs are deployed in a building and connected by the same Local Area Network (LAN), with each SBS providing communication and computing service.The SBSs may be femtocells and are endowed with limited edge-computing capabilities.
  • A. Network model: An SBS’s computing capability is characterized by its computation service rate f_i, with all SBS rates collected in f = {f_i}_i∈N.The model also collects the UE set and task-arrival information across the network.
  • A. Network model: Each SBS serves a dedicated UE subset M_i, whose tasks can be offloaded to its serving SBS through wireless communications.UEs may include mobile phones and laptops, including devices authorized to access a business’s SBS service.
  • B. Workload arrival model: Peer-offloading decisions occur in discretized time slots, operating at a slower timescale than task arrivals.The operational timeline uses slots such as 1–5 minutes for making peer-offloading decisions.
  • B. Workload arrival model: Task arrivals at UE m in slot t follow a Poisson process with rate π_m^t, and the vector of UE rates describes the slot’s arrival pattern.Different task types may vary in input data size and required CPU cycles.
  • B. Workload arrival model: Each task is modeled with expected input size s bits and expected CPU-cycle requirement h.These expectations simplify the workload model while retaining communication and computation requirements.

C. Transmission model

The transmission and computation models represent delay and energy across wireless access, wired peer offloading, and SBS processing. Peer offloading can reduce overloaded computation, but LAN congestion introduces additional delay.

  • Transmission model: Wireless transmission uses Shannon-capacity downlink rates, with SBS transmission energy modeled for downlink traffic.The model focuses on downlink transmission because wireless transmission energy is assumed to dominate.
  • Transmission model: UE-to-SBS uplink transmission contributes a transmission delay cost for computation-task offloading.The uplink rate is obtained analogously to the downlink rate, and total transmission delay is calculated for UEs covered by each SBS.
  • Peer offloading: Tasks may be offloaded only once, so an offloaded task is processed by its destination SBS without further or return offloading.Feasible profiles require nonnegative offloading, workload conservation, and post-offloading workloads no greater than service rates.
  • Computation delay: LAN peer offloading causes additional congestion delay that depends on total offloaded traffic and is modeled as an M/M/1 queue.The task data size is assumed exponentially distributed, and τ denotes uncongested LAN sending and receiving delay for s bits.
  • Computation delay: Each SBS’s total task delay combines computation delay, network congestion delay, and UE-to-SBS transmission delay.The computation delay is modeled with an M/M/1 queue under Poisson arrivals and exponentially distributed service times.

F. Problem Formulation

The paper formulates peer offloading as long-term delay minimization under individual SBS energy constraints. It then develops OPEN, an online Lyapunov-based framework that uses current information to coordinate centralized or autonomous decisions.

  • F. Problem Formulation: Peer offloading requires SBS cooperation in sharing computing resources and energy costs, while this paper focuses on strategies rather than incentive mechanisms.The strategies take SBS-committed resources as input and can work with any incentive mechanism.
  • 2) Computation energy consumption:: The network operator minimizes long-term system delay subject to individual SBS long-term energy budgets and per-slot energy and delay limits.The per-slot delay cap is intended to guarantee worst-case real-time performance.
  • 2) Computation energy consumption:: Future task arrivals are difficult to predict, while long-term energy constraints couple offloading decisions across time slots.Using more energy in the current slot reduces the energy available for future use, motivating online optimization.
  • IV. ONLINE SBS PEER OFFLOADING: OPEN uses Lyapunov drift-plus-penalty optimization to convert the long-term problem into per-slot problems using current information.Virtual energy-deficit queues guide decisions, and the control parameter V balances delay minimization against energy deficits.
  • IV. ONLINE SBS PEER OFFLOADING: OPEN coordinates centralized decisions and also supports autonomous peer offloading decisions among SBSs.The centralized procedure observes workload arrivals, solves each per-slot problem, and updates deficit queues.
  • A. Lyapunov optimization based online algorithm: Larger energy-deficit queues make reducing current energy deficits more critical in the per-slot objective.The resulting policy follows the principle of using less energy when the energy budget is violated, without future information.
  • A. Lyapunov optimization based online algorithm: Stable virtual queues enforce each SBS’s long-term energy constraint while OPEN provides performance guarantees for delay and energy deficit.The algorithm requires only currently available information as input.

B. Centralized solution to OPEN

The centralized solution determines peer offloading from marginal computation and congestion costs. It classifies SBSs by pre-offloading MaCCs, computes the optimal allocation, and uses binary search to obtain the coordinating threshold.

  • Centralized coordination: The centralized controller collects current information from all SBSs and coordinates the per-slot peer offloading solution.The formulation optimizes accommodated workload and LAN traffic as alternative variables linked deterministically to an offloading profile.
  • Centralized coordination: The per-slot objective contains decision-dependent computation, energy, and congestion costs, while UE-to-SBS delay and SBS-to-UE energy are decision-independent.The solution therefore focuses on the decision-dependent part.
  • SBS categorization: SBSs are categorized as sources, neutrals, or sinks according to whether they offload workload, retain workload locally, or receive workload.An SBS that both sends and receives workload is excluded because extra congestion makes such solutions suboptimal.
  • SBS categorization: Theorem 1 determines SBS categories, post-offloading workloads, and LAN traffic from pre-offloading MaCCs and an optimal threshold.The auxiliary functions represent marginal computation and congestion delay values.
  • SBS categorization: Theorem 1 assigns sinks to ξi < α, neutrals to α ≤ ξi ≤ α + Vg(λ∗), and sources to ξi > α + Vg(λ∗).Sink post-offloading MaCCs equal α, while neutral SBSs neither receive beneficial offloading nor benefit from offloading themselves.
  • OPEN-Centralized: OPEN-Centralized uses binary search and a workload-flow equation to find α by matching inbound and outbound LAN workload.Each iteration identifies sink, source, and neutral SBSs before updating α when the flows do not match.
  • OPEN-Centralized: Any peer offloading profile realizing the optimal workload allocation is optimal for the per-slot problem P2.The algorithm outputs both the optimal SBS workload allocation and corresponding LAN traffic.

C. Performance Analysis of OPEN

The analysis establishes OPEN’s delay–energy tradeoff and explains its decentralized extension. OPEN approaches offline-optimal delay as V grows, while a larger energy deficit and slower convergence accompany that choice; the game formulation studies equilibrium and efficiency loss.

  • Performance analysis: Stable deficit queues imply satisfaction of the long-term energy constraint.The bound follows from the queue update rule and vanishing time-normalized queue backlog.
  • Performance analysis: Virtual energy-deficit queues measure deviations from long-term SBS energy constraints, and queue stability enforces those constraints.The Lyapunov function and one-slot drift are used to guide this stability analysis.
  • Performance analysis: OPEN’s drift-plus-penalty design uses V to control the tradeoff between delay minimization and energy deficit.The performance proof compares OPEN with the optimal solution to P1.
  • Performance analysis: [O(1/V), O(V)] is OPEN’s delay–energy deficit tradeoff.The system approaches offline-optimal performance as V →∞.
  • Performance analysis: Increasing V makes the time-average energy deficit grow linearly, and achieving optimal delay requires a larger deficit queue that postpones convergence.Thus, the delay optimum is accompanied by an energy-deficit and convergence cost.
  • Performance analysis: Total system energy remains almost unchanged across peer offloading decisions because the same tasks remain within the edge system.The main issue is how processing energy is distributed among SBSs, assuming wired transmission energy is negligible.
  • Decentralized peer offloading: In distributed networks without a central authority or complete information, OPEN formulates SBS decisions as a non-cooperative game.The analysis addresses Nash equilibrium and efficiency loss relative to centralized coordination through the Price of Anarchy.
  • Decentralized peer offloading: The decentralized formulation evaluates efficiency loss compared with centralized coordination using the Price of Anarchy.This analysis targets autonomous decision making by self-interested SBSs.

A. Game Formulation

The paper models autonomous SBS peer offloading as a non-cooperative game in which each SBS minimizes its own cost. It establishes equilibrium existence and develops a best-response procedure for reaching Nash equilibrium.

  • A. Game Formulation: The game Γ represents SBSs, their feasible peer-offloading strategies, and individual cost functions.
  • A. Game Formulation: Each SBS adjusts its own peer-offloading strategy to minimize its individual cost while other SBS strategies are fixed.
  • A. Game Formulation: An SBS’s cost combines local-processing costs for retained workload with peer-offloading costs, including other-SBS computation and network congestion delays.
  • B. Existence of Nash Equilibrium: Pair-specific marginal costs form the gradient of each SBS’s cost function and support a variational-inequality characterization of best responses.
  • B. Existence of Nash Equilibrium: The SBS peer-offloading game admits at least one Nash equilibrium when feasible strategies satisfy the stated convexity, compactness, and continuity conditions.
  • C. Algorithm for Achieving Nash Equilibrium: SBS categories distinguish local workload handling and interactions with other SBSs; categories are defined per SBS and may overlap.
  • C. Algorithm for Achieving Nash Equilibrium: The best-response algorithm uses marginal computation costs, identifies sink SBSs, and determines offloading through workload-flow constraints and binary search.
  • C. Algorithm for Achieving Nash Equilibrium: OPEN-Autonomous has SBSs take turns running best response in round-robin fashion until cost changes fall below tolerance; the paper reports a unique equilibrium and simulation-confirmed convergence.

D. Price of anarchy

The paper analyzes efficiency loss from strategic peer offloading by bounding the price of anarchy. The bound depends on marginal-cost heterogeneity, while autonomous offloading retains a delay–energy trade-off under stated limitations.

  • The price of anarchy measures the efficiency loss caused by strategic SBS behavior relative to an optimal peer-offloading profile.
  • A larger ratio of SBSs’ pair-specific marginal costs produces a larger bound on the price of anarchy.
  • Marginal-cost heterogeneity increases with heterogeneity in task arrival rates and computation capacity among SBSs.
  • An extremely fast SBS can attract workload from other SBSs, increasing LAN congestion delay and the price of anarchy.
  • For every time slot, the peer-offloading game’s price of anarchy is bounded, although its value depends heavily on task-arrival patterns and system configuration.
  • OPEN-Autonomous retains an [O(V), O(1/V)] delay–energy-deficit trade-off, but its delay bound is not directly comparable with the optimal system delay.

VI. SIMULATION

The simulations evaluate OPEN in a randomly deployed commercial-complex edge network with heterogeneous users, workloads, SBS resources, and long-term energy constraints. OPEN-C and OPEN-A are compared with no offloading and alternative energy-management schemes.

  • The experiments model SBSs as individually owned facilities connected through a LAN and impose a 22Wh-per-hour long-term energy constraint.
  • The simulated network is a 100m×100m commercial complex whose SBS locations follow a homogeneous Poisson Point Process.
  • Each UE is assigned to a nearby SBS and generates tasks according to a Poisson process; task size, CPU cycles, server frequency, and wireless parameters are specified.
  • The evaluation compares OPEN-C and OPEN-A with NoP, D-Optimal, and SSC benchmarks.
  • NoP disables peer offloading, while D-Optimal minimizes static system delay without long-term energy constraints and SSC imposes a hard per-slot energy constraint.

A. Run-time Performance Evaluation

The runtime evaluation compares delay and energy behavior across peer-offloading schemes and examines OPEN’s response to temporal workload variation and control parameter V. OPEN satisfies long-term energy constraints while trading delay against energy deficit.

  • Without peer offloading, the edge system experiences high delay cost and large energy deficit because SBSs can be overloaded by heterogeneous task arrivals.
  • Peer-offloading schemes achieve much lower system delay cost than NoP, while D-Optimal attains the lowest delay cost but incurs substantial energy deficit.
  • OPEN-C and OPEN-A drive time-average energy deficits to zero, satisfying SBS long-term energy constraints; OPEN-C is close to optimal in delay and OPEN-A has slightly higher delay from strategic behavior.
  • SSC also has zero energy deficit but produces large system delay because per-slot energy constraints make scheduling less flexible under temporal workload heterogeneity.
  • A larger task-arrival rate generally produces higher system delay cost across time slots.
  • OPEN reduces energy consumption after an energy-deficit increase, thereby bringing long-term energy constraints into compliance.
  • OPEN exhibits an [O(1/V), O(V)] trade-off between long-term delay cost and energy deficit; increasing V emphasizes delay and can approach optimal delay as V grows.
  • The simulations recommend V = 50 because OPEN already achieves close-to-optimal delay and further increases offer little improvement.

D. Composition of System Delay

OPEN-C concentrates delay in computation, whereas OPEN-A shifts much of the delay to congestion because non-cooperative SBSs exchange more traffic. OPEN outperforms OPEN-A across time slots, remains effective under heterogeneous and nonstandard task arrivals, and incurs low practical overhead.

  • Delay composition: OPEN-C’s delay is dominated by computation, while OPEN-A’s is dominated by congestion from non-cooperative offloading.Communication delay is unchanged between the two schemes.
  • Price of anarchy: OPEN-C achieves a strictly smaller objective value than OPEN-A in every evaluated time slot.Across 600 time slots, the mean PoA is 1.54 and the maximum is 2.42.
  • System heterogeneity: Higher spatial heterogeneity reduces delay cost for both OPEN-C and OPEN-A by creating more opportunities to balance workload.The evaluation varies normalized heterogeneity by changing the standard deviation of grid-level task arrival rates.
  • Practical overhead: OPEN-C derives solutions in 0.83ms on average, compared with 28.1ms for OPEN-A, and both runtimes are negligible relative to the 1-minute decision cycle.Estimated information-exchange delays are approximately 0.2ms for OPEN-C and 8ms for OPEN-A.
  • Task arrival realization: OPEN remains effective under bursty and non-i.i.d. arrivals, achieving 55.0% delay reduction for bursty arrivals and 37.5% for the non-i.i.d. case.Bursty arrivals increase delay cost because tasks are more likely to queue at edge servers.
  • Conclusion: OPEN optimizes edge performance under individual SBS energy limits without future system information and supports centralized or autonomous decisions.The paper reports a provable performance guarantee and acceptable practical overhead, while identifying more sophisticated congestion models as future work.

APPENDIX A PROOF OF THEOREM 1

The appendix proves Theorem 1 by converting the centralized optimization into balance, feasibility, and Kuhn–Tucker conditions, then deriving cases for neutral, source, and sink SBSs. Lyapunov drift arguments yield long-term delay and energy-deficit bounds under an explicit policy assumption.

  • Traffic representation: The proof uses traffic balance to express each SBS’s effective workload as ω_i = φ_i + u_i − v_i and characterizes network traffic through offloaded flows.Inbound and outbound traffic are denoted by u_i and v_i, respectively.
  • Optimization conditions: The centralized problem is convex with linear constraints, so its first-order Kuhn–Tucker conditions are necessary and sufficient for optimality.The proof introduces Lagrange multipliers and writes the corresponding Lagrangian and optimality conditions.
  • SBS cases: The KKT conditions partition SBS behavior into neutral, source, and sink cases according to inbound and outbound traffic.The proof shows that either inbound or outbound traffic is zero for each SBS, and derives the corresponding inequalities.
  • Performance bound: The Lyapunov drift analysis derives a bound for long-term system delay cost by summing the drift-plus-penalty inequalities over time.The derivation uses nonnegative Lyapunov function values and an initially zero Lyapunov function.
  • Energy bound: The energy-deficit analysis assumes a stationary randomized policy satisfying specified inequalities, then applies it to obtain the long-term bound.The policy is independent of the current energy-deficit queue.

APPENDIX C PROOF OF THEOREM 4

The appendix proves Theorem 4 by formulating the autonomous offloading problem with link-specific flows and deriving its KKT conditions. Case analysis maps optimal solutions to idle, source, neutral, and sink SBS roles, after which drift and price-of-anarchy bounds yield long-term guarantees.

  • Problem formulation: The autonomous problem introduces u_ij and v_ij for workloads into and out of SBS j, then expresses offloaded workload β_ij through these flows.The formulation uses SBS traffic balance and Lagrange multipliers before deriving optimality conditions.
  • KKT conditions: The autonomous optimization is characterized by KKT stationarity, feasibility, complementary slackness, and multiplier conditions.These conditions are written for the link-specific variables and constraints.
  • Behavioral cases: Case analysis identifies idle, source, neutral, and sink SBS roles from whether effective workload is zero and whether inbound or outbound traffic is positive.The proof also assumes outbound traffic v_ij can be nonzero only when i = j.
  • Long-term guarantee: The proof combines the drift-plus-cost bound with the price-of-anarchy bound to establish a long-term system delay guarantee for OPEN-Autonomous.The derivation sums the resulting inequality over time and divides by the time horizon.
  • Energy bound: A separate summation of the autonomous drift inequality yields a long-term energy-deficit bound.The proof directly sums the relevant inequality over the time horizon and rearranges terms.
Loading 1703.06058v2…