PaperlayerView exact revision on arXiv

Source-linked AI summary

Wireless Networks for Mobile Edge Computing: Spatial Modeling and Latency Analysis (Extended version)

Seung-Woo Ko, Kaifeng Han, Kaibin Huang

arXiv:1709.01702v4cs.IT

TL;DR

The paper asks how large-scale MEC networks can provide low-latency offloading while satisfying RAN coverage and CSN stability. It models the network spatially and derives latency scaling laws using stochastic geometry, queueing, and parallel computing. The results quantify latency tradeoffs and support provisioning that avoids bottlenecks in either cascaded network component.

  • Problem

    The paper addresses how to analyze communication and computation latency jointly in large-scale MEC networks under RAN coverage and CSN stability constraints.

  • Method

    The paper builds a spatial random MEC model and applies stochastic geometry, queueing, and parallel computing to derive latency scaling laws.

  • Results

    The derived scaling laws characterize comm-latency and comp-latency against network-load and network-resource parameters under coverage and stability constraints.

  • Takeaways & Limitations

    The results provide guidelines for MEC-network provisioning and planning that avoid either the RAN or CSN becoming a performance bottleneck.

Abstract

from arXiv · show

Next-generation wireless networks will provide users ubiquitous low-latency computing services using devices at the network edge, called mobile edge computing (MEC). The key operation of MEC, mobile computation offloading (MCO), is to offload computation intensive tasks from users. Since each edge device comprises an access point (AP) and a computer server (CS), a MEC network can be decomposed as a radio access network (RAN) cascaded with a CS network (CSN). Based on the architecture, we investigate network constrained latency performance, namely communication latency (comm-latency) and computation latency (comp-latency) under the constraints of RAN coverage and CSN stability. To this end, a spatial random network is modeled featuring random node distribution, parallel computing, non-orthogonal multiple access, and random computation-task generation. Given the model and the said network constraints, we derive the scaling laws of comm-latency and comp-latency with respect to network-load parameters (density of mobiles and their task-generation rates) and network-resource parameters (bandwidth, density of APs/CSs, CS computation rate). Essentially, the analysis involves the interplay of theories of stochastic geometry, queueing, and parallel computing. Combining the derived scaling laws quantifies the tradeoffs between the latencies, network coverage and network stability. The results provide useful guidelines for MEC-network provisioning and planning by avoiding either of the cascaded RAN or CSN being a performance bottleneck.

I. INTRODUCTION

The paper shifts MEC research from small-scale offloading techniques toward large-scale network modeling, examining communication and edge-computing performance together under coupled network constraints. It develops a spatially random MEC model to support tractable analysis and provisioning guidance.

  • Modeling approach: A spatial random model incorporates randomly distributed nodes, wireless transmissions, and parallel computing to analyze large-scale MEC performance.The model is designed to remain sufficiently practical while allowing tractable latency analysis.
  • Modeling approach: The analysis applies stochastic geometry, queueing, and parallel-computing theories to the coupled MEC network.The paper emphasizes that communication and edge-computing coupling creates challenges beyond conventional network or queueing models.
  • Practical objective: The resulting framework is intended to provide guidelines for MEC-network provisioning and planning.The stated goal is to avoid either the radio access network or computer-server network becoming a performance bottleneck.
  • Research direction: Large-scale MEC networks with infinite nodes are identified as an important, unexplored setting beyond prior small-scale systems.The paper targets network-level behavior rather than only complex offloading protocols for a few users and servers.
  • Research direction: The study jointly considers wireless communication and edge computing in a MEC architecture decomposed into a RAN cascaded with a computer-server network.This architecture introduces coupled communication and computation performance concerns.

C. Contributions

The paper constructs a tractable stochastic model of large-scale MEC networks and derives latency, throughput, stability, and provisioning results. These results characterize tradeoffs between communication and computation performance under coverage and stability constraints.

  • Modeling MEC networks: The proposed large-scale MEC model combines stochastic geometry, queueing, and parallel computing while representing random nodes, multiple access, and task arrivals.The model is designed to support tractable network-performance analysis despite coupled communication and computation processes.
  • Communication latency: Communication latency is minimized subject to network connectivity, using the spreading factor G to balance interference mitigation against bandwidth loss.Sparse networks favor full-bandwidth transmission, whereas dense networks require larger G to satisfy coverage, increasing Tcomm.
  • Communication latency: Minimum Tcomm decreases inversely with channel bandwidth, grows sub-linearly with expected mobiles per AP, and increases with task-generation probability before saturation.The allowed fraction of disconnected users also affects the latency through a power function with a negative exponent.
  • RAN throughput: RAN task-arrival rate is quasi-concave in expected mobiles per AP, remaining low in both sparse and dense networks and attaining a maximum proportional to bandwidth.The RAN throughput determines the load presented to the CSN.
  • Computation latency: Computation latency requires limiting dynamic VM counts to avoid I/O-interference losses and keeping maximum computing rate above a stability-scaled task-arrival rate.Bounds show Tcomp is inversely proportional to maximum computing rate and linearly proportional to total task-arrival rate.
  • Network provisioning and planning: For provisioning, AP density should maximize RAN throughput under coverage, bandwidth should meet the target Tcomm, and CS capacity should meet target Tcomp while enforcing stability.The derived analytical results simplify the specific planning calculation.

II. MODELING MEC NETWORKS

The model represents APs and mobiles as independent spatial point processes with fixed service zones and coverage-based AP association. It also abstracts task generation, offloading, and computation timing to obtain tractable latency analysis.

  • Spatial network model: APs and co-located CSs are modeled as a homogeneous PPP with density λb, while mobiles form an independent homogeneous PPP with density λm.The analysis focuses on a typical mobile and a typical AP.
  • Coverage and association: Each AP has a fixed-radius MEC-service zone determined by mobile transmission power, and a mobile can access an AP when it lies within that zone.A mobile covered by multiple APs randomly selects one AP for MEC service.
  • Coverage and association: The service-zone radius is chosen so that the fraction of inactive mobiles is no more than δ, supporting close-to-full network coverage.Mobiles outside service zones remain inactive.
  • Task generation: Time is slotted, and each mobile randomly generates a task in each slot with probability p under an independent-generation assumption.The task-generation model is explicitly presented as an abstraction for tractable analysis, although measured requests can be bursty and periodical.
  • Offloading model: A mobile offloads a newly generated task when its buffer is empty; otherwise, the task is computed locally, with a unit buffer and fixed-size transmissions lasting L slots.The resulting task-departure process is Bernoulli with parameter pL.

C. Radio Access Model

The radio-access model uses CDMA-based non-orthogonal access, where spreading trades per-mobile bandwidth for interference suppression and connectivity. It models fading, interference, task transmissions, and synchronous or asynchronous arrivals.

  • Spreading factor: Increasing the spreading factor G reduces each mobile’s bandwidth from B to B/G while reducing interference power by approximately 1/G.The model therefore captures a direct bandwidth–interference tradeoff.
  • Multiple access: CDMA separates users with PN sequences and can support potentially more simultaneous users than OFDMA.Its non-orthogonality provides a tradeoff between system-performance degradation and simultaneous-user capacity.
  • Channel and interference: The uplink uses path-loss and Rayleigh fading, with fixed mobile transmit power and interference generated by an independently thinned Poisson field of active mobiles.Active interferers have density (1−δ)pLλm, and spread spectrum contributes a 1/G interference factor.
  • Transmission model: Successful offloading requires SIR above θ, giving spectral efficiency log2(1+θ) and frame length L = GTmin for a task.Here Tmin is the full-bandwidth transmission time.
  • Offloading modes: Synchronous transmissions create periodic batch arrivals at CSs, whereas asynchronous transmissions produce arrivals at different time instants.Synchronization also incurs common-clock overhead and increases latency.

D. Edge-Computing Model

The edge-computing model sends tasks immediately to CS buffers, where parallel virtual machines process them under queueing and interference effects. Communication and computation latency are defined under coverage and stability constraints.

  • CS architecture: Tasks are delivered to CSs without delay and queue in infinite-capacity buffers under first-come-first-served processing.Each CS supports asynchronous VM creation and removal for parallel computation.
  • Parallel computation: The expected single-task computation time Tc depends on VM count m and increases monotonically with the I/O-interference factor d.Computation time is modeled as an exponential random variable with mean Tc.
  • Task arrivals: Asynchronous task arrivals at a typical AP are approximated by a Poisson process because independent Bernoulli task generations are superposed without synchronization.The approximation is stated for N connected mobiles and spreading factor G.
  • Scope assumptions: The model excludes result downloading because its latency is considered negligible relative to offloading under the stated size and downlink-rate assumptions.VM creation and release latency is included in computation time rather than modeled separately.
  • Latency metrics: Communication latency Tcomm includes mobile-buffer waiting and transmission time, while computation latency Tcomp includes CS queueing delay and actual computation time.The two metrics measure distinct stages of the cascaded RAN–CSN path.
  • Network constraints: The RAN must be ϵ-connected and the CSN ρ-stable, requiring connected mobiles and stable CSs to be at least 1−ϵ and 1−ρ, respectively.The stability condition limits the fraction of unstable CSs, with 0 < ρ ≪ 1.

III. COMMUNICATION LATENCY ANALYSIS

The communication-latency analysis uses stochastic geometry to characterize connectivity, then optimizes CDMA spreading under the coverage constraint. The resulting regimes distinguish sparse networks, where G*=1, from dense networks requiring interference suppression.

  • Connectivity analysis: The connectivity probability of a typical mobile is derived as a function of G using stochastic-geometry analysis.This probability supplies the coverage constraint used in subsequent latency optimization.
  • Transmission–connectivity tradeoff: Increasing G lowers per-mobile bandwidth and raises transmission latency, while suppressing interference and increasing connectivity probability.These opposing effects make moderate spreading factors potentially unfavorable under stringent connectivity constraints.
  • Feasible spreading factors: The feasible spreading-factor set is all integers G≥1 when ξ(g0)≤F(ϵ); otherwise it is S1={G∈Z+|1≤G≤ga}∪S2={G∈Z+|G≥gb}.The boundary values ga and gb solve ξ(G)=F(ϵ).
  • Latency optimization: The comm-latency Tcomm(G) increases monotonically with G, so minimizing communication latency reduces to selecting the smallest feasible spreading factor.The latency includes waiting associated with task arrivals within frames of length L=GTmin.
  • Parameter scaling: The derived scaling laws expose effects of task size ℓ, bandwidth B, mobile density λm, AP density λb, and task-generation probability p.The dense-network case is explicitly characterized through these network parameters.

C. Task-Arrival Rates at APs/CSs

The offloading throughput of the RAN determines task arrivals at the CSN, linking communication conditions to computation load. Arrival scaling differs between sparse and dense networks and between asynchronous and synchronous offloading.

  • Asynchronous offloading: The expected AP task-arrival rate satisfies Λ̄*=N̄β*, where N̄ is the expected connected-mobile count and β* is the optimal per-mobile offloading rate.Thus RAN throughput directly determines CSN load.
  • Sparse networks: In sparse networks, expected task-arrival rate grows linearly with task-generation probability p and expected mobiles per AP λm/λb.Sparse performance is not limited by bandwidth or interference in this regime.
  • Dense networks: In dense networks, expected task-arrival rate grows linearly with bandwidth B but decreases with λm/λb.Reduced offloading leaves more spreading capacity for interference suppression, lightening CS load and reducing computation latency.
  • Synchronous offloading: Under synchronous offloading, tasks arrive at the typical AP in periodic batches, with expected arrivals per frame Ā*=N̄p*.The batch size depends on the number of connected mobiles in the service zone.
  • Synchronous dense regime: As λm/λb→∞, the frame length approaches 1 and expected tasks per frame increase linearly with λm/λb.This is the dense-network synchronous-arrival scaling.

IV. COMPUTATION LATENCY ANALYSIS: ASYNCHRONOUS OFFLOADING

The asynchronous-offloading analysis derives computation-rate conditions for CSN stability and develops an optimal VM-control policy. It also characterizes stable task-arrival rates using queueing, stochastic geometry, and parallel-computing results.

  • Model and stability: The asynchronous-offloading model analyzes randomly distributed task arrivals and departures through a Markov model.The analysis derives a network-stability condition and bounds on average computation latency.
  • VM control: Too many VMs reduce computation rate through I/O interference, while too few provide limited parallel-computing gains.Therefore, VM count should be controlled according to the number of waiting tasks.
  • VM control: The computation rate µ(m) first increases and then decreases with VM count, yielding an optimizing integer mmax.The maximum is obtained from the unimodal behavior of µ(m).
  • VM control: The optimal policy creates mmax VMs when enough tasks are available and otherwise creates as many VMs as possible until the buffer empties.This policy maximizes the computation rate at the typical CS.
  • Network stability: For ρ-stability, the maximum CS computation rate must exceed the expected task-arrival rate by an exponential factor that increases as the required stability probability increases.The result uses the expected number of mobiles connected to the typical CS and a Lambert function.
  • Network stability: Conditioned on CS stability, the expected task-arrival rate is characterized using the stable-CS condition and the Poisson distribution of connected mobiles.The parameter β∗ measures the maximum number of mobiles the CS can serve.

C. Expected Computation Latency

The expected computation latency for asynchronous offloading is bounded by replacing the nonlinear Markov-chain dynamics with tractable queueing models. These bounds support an approximation showing that latency depends on both computation capacity and task-arrival load.

  • Asynchronous latency bounds: The nonlinear departure rate makes exact computation-latency analysis difficult, so modified Markov chains corresponding to M/M/mmax and M/M/1 queues provide tractable bounds.The M/M/mmax construction supports an upper bound, while the M/M/1 construction supports a lower bound.
  • Asynchronous latency bounds: Theorem 2.A gives an upper bound on average computation latency for asynchronous offloading.The bound uses the stable-CS arrival-rate result and the maximum computation rate µmax.
  • Provisioning implication: With sufficient computation resources, the upper and lower bounds have similar forms, yielding an approximation for asynchronous computation latency.The approximation is expressed using constants and the ratio of maximum computation rate to expected task-arrival rate.
  • Provisioning implication: Containing computation latency requires a sufficiently large µmax that scales linearly with total task-arrival rate.The ratio µmax/¯Λ∗ must be sufficiently large for a single offloaded task.

D. Energy Efficiency

The paper connects computation and communication latency results to MEC energy efficiency and network provisioning. It gives separate planning guidance for the RAN and CSN, while noting scope limits for synchronous offloading analysis.

  • Energy efficiency: Offloading energy is derived from transmission power and offloading duration, while local-computing energy depends on task size and the latency deadline.The offloading condition compares Eoff with Eloc.
  • Energy efficiency: Energy savings require Eoff < Eloc, and the condition is dominantly affected by the expected number of mobiles and AP density.For fixed mobile density and task size, a minimum AP density can satisfy the condition.
  • MEC provisioning: RAN planning selects AP density to maximize offloading throughput and provisions sufficient bandwidth for the targeted communication latency.The expected task-arrival rate per AP is quasi-concave in the expected number of mobiles per AP.
  • MEC provisioning: CSN planning requires maximum CS computation rate to exceed expected task-arrival rate by a factor determined by the allowed fraction of unstable CSs.The rate is then planned to meet the targeted computation latency using the asynchronous latency bounds.
  • Synchronous-offloading scope: The Markov-chain approach yields tractable M/M/m and M/M/1 analyses for asynchronous offloading but is inapplicable to synchronous periodic task arrivals.General synchronous analysis is difficult, although light-traffic and heavy-traffic cases are tractable.
  • Synchronous-offloading scope: For synchronous offloading, Theorem 3 bounds light-traffic computation latency, while simulations indicate synchronization generally causes longer latency through CS overloading and I/O interference.The comparison with asynchronous offloading is not determined analytically from the expressions alone.

B. Expected Computation Latency with Heavy-Traffic

For synchronous offloading under heavy traffic, the analysis models queue evolution through arrival and departure processes and derives the expected computation latency. The resulting lower bound has the same form as the asynchronous counterpart and diverges near capacity.

  • Heavy-traffic model: Heavy traffic assumes the CS queue is always non-empty, so the total computation rate is µmax.The departure process is modeled as Poisson with moments determined by µmax and frame duration.
  • Heavy-traffic model: CS stability requires the expected arrival rate to be strictly smaller than the departure rate, imposing N ≤⌊R⌋.Little’s theorem is then used to obtain expected computation latency.
  • Heavy-traffic result: Theorem 4 gives the expected computation latency for synchronous offloading under heavy traffic.The result uses the constant R and the distribution of N from Lemma 4.
  • Comparison: The heavy-traffic lower bound has the same form as the asynchronous-offloading counterpart.Both bounds diverge as task-arrival rate approaches maximum computation rate.

VI. SIMULATION RESULTS

Simulations compare communication and computation latency under asynchronous and synchronous offloading. The results show distinct latency scaling behaviors, operation regimes, bound tightness, and longer computation latency under synchronization.

  • Simulation setup: Analytical results are evaluated against Monte Carlo simulations using 10^4 realizations of PPP-distributed mobiles and APs.Each realization generates offloading tasks, transmits them to corresponding APs, and computes them using virtual machines.
  • Asynchronous offloading: Under asynchronous offloading, expected computation latency versus mobile density is quasi-concave, whereas communication latency increases monotonically.These behaviors partition mobile density into three operation regimes: a middle computation-limited range and communication-limited ranges on either side.
  • Asynchronous offloading: As task-generation probability increases, both latency types converge to corresponding limits, partitioning task-generation rates into communication-limited and computation-limited regimes.The partition follows from their different scaling laws.
  • Asynchronous offloading: The lower bound on computation latency is tighter than the upper bound in the asynchronous case.This comparison is reported for the bounds derived in (37).
  • Synchronous offloading: Synchronous offloading produces longer computation latency, with the quasi-concavity versus mobile density absent in the considered range.In the synchronous case, the center of the computation-limited range corresponds to heavy traffic, where the upper bound is tight; other density ranges favor light-traffic bounds.
  • Synchronous offloading: For synchronous offloading, computation latency is tightly approximated by light-traffic bounds when task-arrival rate is ≤0.3 and heavy-traffic bounds when it is >0.7.The comparison validates the analytical results across the reported task-arrival-rate ranges.
  • Implications: The study derives latency scaling laws under RAN connectivity and CSN stability constraints to guide MEC provisioning and avoid either network component becoming a bottleneck.The model combines stochastic geometry, queuing, and parallel computing for communication and computation latency analysis.
  • Scope and extensions: The analysis assumes a single computation-task type with identical task size and average computation time; heterogeneous tasks remain a practical extension.Hierarchical fog computing, VM migration, and cooperative computing are also identified as future directions.

APPENDIX

The appendix supplements the latency analysis with derivations, approximation checks, and simulations covering task arrivals, network density, computation capability, and asynchronous versus synchronous offloading. The results characterize latency trends and compare the two offloading modes under varying conditions.

  • Derivations: The appendix derives the stationary point of ξ(G) using the Lambert function, selecting the lower branch because it yields g0 > 0.The principal branch gives g0 = 0, while the lower branch completes the positive solution.
  • Approximation: The task-arrival process at APs can be well approximated by the Poisson task-arrival assumption.The appendix compares the comp-latency under the Poisson arrival assumption with the modeled process.
  • Network density: Increasing AP or CS density produces corresponding latency observations when mobile density decreases.Figure 9 examines the effects of AP (CS) density on comm-latency and comp-latency.
  • Offloading comparison: Asynchronous comp-latency is always smaller than synchronous comp-latency, with their ratio decreasing as mobile density grows.The ratio is initially constant for sparse mobiles and then decreases with increasing mobile density.
  • Offloading comparison: The comp-latency gap between asynchronous and synchronous offloading becomes smaller as task arrival becomes heavier, with the ratio eventually converging to a constant.The ratio grows and then converges to a constant as p increases.
Loading 1709.01702v4…