Source-linked AI summary
Power-Delay Tradeoff in Multi-User Mobile-Edge Computing Systems
Yuyi Mao, Jun Zhang, S. H. Song, Khaled B. Letaief
TL;DR
The paper examines how multi-user MEC can balance mobile-device power consumption and computation-task execution delay under stochastic workloads. It formulates a buffer-stable power-minimization problem and develops a Lyapunov-based online policy for local execution and offloading. The analysis establishes an [O (1/V); O (V)] power-delay tradeoff, supported by simulations including execution-delay changes from 33.2 to 1.05 ms with MEC as V decreases.
Problem
Multi-user MEC must balance mobile-device power consumption and task execution delay when computation-intensive workloads exceed device capabilities and task arrivals are stochastic.
Method
The paper formulates power minimization with task-buffer stability constraints and develops a Lyapunov-based online policy jointly selecting local CPU frequencies, offloading power, and bandwidth.
Results
[O (1/V); O (V)] characterizes the power-consumption and execution-delay tradeoff, while MEC reduces execution delay from 33.2 to 1.05 ms as V decreases.
Takeaways & Limitations
The proposed algorithm balances mobile-device power consumption and computation experience in multi-user MEC systems.
Abstract
from arXiv · showhide
Mobile-edge computing (MEC) has recently emerged as a promising paradigm to liberate mobile devices from increasingly intensive computation workloads, as well as to improve the quality of computation experience. In this paper, we investigate the tradeoff between two critical but conflicting objectives in multi-user MEC systems, namely, the power consumption of mobile devices and the execution delay of computation tasks. A power consumption minimization problem with task buffer stability constraints is formulated to investigate the tradeoff, and an online algorithm that decides the local execution and computation offloading policy is developed based on Lyapunov optimization. Specifically, at each time slot, the optimal frequencies of the local CPUs are obtained in closed forms, while the optimal transmit power and bandwidth allocation for computation offloading are determined with the Gauss-Seidel method. Performance analysis is conducted for the proposed algorithm, which indicates that the power consumption and execution delay obeys an [O (1/V); O (V)] tradeoff with V as a control parameter. Simulation results are provided to validate the theoretical analysis and demonstrate the impacts of various parameters to the system performance.
I. INTRODUCTION
The paper studies multi-user MEC as a response to computation-intensive applications and limited mobile-device processing capability. It formulates an online joint local-execution and offloading design to balance mobile-device power consumption against execution delay.
- MEC addresses computation-intensive applications that exceed the limited processing capability of mobile devices.
- Long-term task arrivals require stochastic control because randomly arriving tasks remain coupled when applications tolerate execution latency.
- Multiple devices make radio-resource management challenging because transmit power and available spectrum must be jointly managed for offloading.
- The proposed Lyapunov-based online algorithm jointly decides local CPU frequencies, offloading transmit power, and bandwidth allocation.CPU frequencies are obtained in closed forms; transmit power and bandwidth are determined with the Gauss-Seidel method.
- The algorithm is analyzed and simulated to characterize and control the tradeoff between mobile-device power consumption and execution delay.
A. Computation Task and Task Queueing Models
Tasks arrive stochastically at each mobile device and wait in a buffer until local execution or MEC offloading serves them. The queue evolves from prior backlog, task departures, and new arrivals.
- Fine-grained tasks arrive at each device at the beginning of a time slot and become processable in the next slot.
- Arrivals are i.i.d. across time within [Ai,min, Ai,max], with mean arrival rate λi for device i.
- Each slot divides processed work between local execution Dl,i(t) and MEC offloading Dr,i(t).
- Qi(t + 1) = max{Qi(t) − DΣ,i(t), 0} + Ai(t), where DΣ,i(t) is total task departure.
B. Local Execution Model
The local execution model maps device CPU frequency to the amount of processed input and its power consumption. Each input bit requires an application-dependent number of CPU cycles, subject to a maximum frequency.
- Each input bit requires Li CPU cycles, determined by application type through offline measurements.
- The scheduled local CPU frequency fi(t) cannot exceed the device-specific maximum fi,max.
- Local execution power consumption is modeled using the effective switched capacitance κ associated with chip architecture.
C. MEC Server Execution Model
The MEC server executes offloaded tasks after wireless transmission from mobile devices. The model uses parallel server cores, fading channels, shared bandwidth, and transmit-power constraints.
- The MEC server has N CPU cores, executes different applications in parallel, and has negligible processing latency.
- Wireless channels are modeled as i.i.d. frequency-flat block fading with finite-mean channel power gains.
- Offloaded task volume depends on channel gain, transmit power ptx,i(t), and allocated bandwidth fraction αi(t).
- Transmit power is bounded by pi,max, while bandwidth allocations form a vector selected from the feasible set A.
III. PROBLEM FORMULATION
The paper formulates stochastic power minimization for multi-user MEC while requiring task-buffer mean-rate stability. The formulation captures CPU frequency, transmit power, and bandwidth decisions, with a modified problem used to enable tractable analysis.
- Performance Metrics: The objective minimizes mobile-device power consumption while measuring execution delay through average task-buffer queue length.Power includes local CPU and computation-offloading transmit power; Little’s Law links queue length to execution delay.
- Problem Formulation: The optimization jointly determines local CPU-cycle frequencies, transmit powers, and bandwidth allocations for each device and time slot.The decisions obey bandwidth, CPU-frequency, and transmit-power constraints.
- Problem Formulation: Mean-rate stability of task buffers ensures that arrived computation tasks are executed with finite delay.The stability constraint is the long-term queueing requirement in the stochastic optimization problem.
- Problem Formulation: The stochastic problem is difficult because optimal decisions are temporally correlated and local execution is jointly considered with computation offloading.The formulation must account for multiple devices and their coupled radio-resource decisions.
- Problem Reformulation: The modified problem P2 replaces the feasible bandwidth set with a restricted set, while remaining feasible for P1 and arbitrarily close in optimal value as ǫA becomes sufficiently small.The paper therefore focuses on P2 for the subsequent development.
IV. ONLINE LOCAL EXECUTION AND COMPUTATION
The paper develops an online local-execution and computation-offloading policy for the modified problem using Lyapunov optimization. A deterministic optimization problem is solved at each time slot, followed by performance analysis of the resulting tradeoff.
- IV. ONLINE LOCAL EXECUTION AND COMPUTATION: The proposed policy uses Lyapunov optimization to solve P2 through a deterministic problem at each time slot.The policy jointly addresses local execution and computation offloading.
- IV. ONLINE LOCAL EXECUTION AND COMPUTATION: The section analyzes the proposed algorithm to reveal the power-delay tradeoff in multi-user MEC systems.
A. Lyapunov Optimization-Based Online Algorithm
The online algorithm minimizes an upper bound on Lyapunov drift-plus-penalty greedily each time slot. This maintains task buffers at a small level while minimizing mobile-device power consumption.
- A. Lyapunov Optimization-Based Online Algorithm: The Lyapunov drift measures the conditional expected change in the queue-based Lyapunov function between consecutive time slots.
- A. Lyapunov Optimization-Based Online Algorithm: The drift-plus-penalty function adds V times expected power consumption to the Lyapunov drift.V is the algorithm’s control parameter with units bits2 · W−1.
- A. Lyapunov Optimization-Based Online Algorithm: The drift-plus-penalty upper bound applies under feasible CPU frequencies, transmit powers, and bandwidth allocations, with C a constant.The proof of the bound is omitted due to space limitation.
- A. Lyapunov Optimization-Based Online Algorithm: At each time slot, the algorithm greedily minimizes an upper bound of the drift-plus-penalty function.The resulting deterministic problem retains P2’s constraints except the task-buffer stability constraints.
- A. Lyapunov Optimization-Based Online Algorithm: The online procedure observes queue, auxiliary, and task-arrival states, determines f(t), ptx(t), and α(t), then updates the task buffers.
B. Optimal Solution For PPTS
The paper solves the per-slot deterministic problem by deriving CPU frequencies in closed form and alternating between transmit-power and bandwidth optimization. Joint convexity guarantees that the Gauss-Seidel procedure converges to the global optimum.
- Optimal CPU-cycle Frequencies: The optimal CPU-cycle frequency is obtained by solving a bounded per-device optimization problem and selecting a stationary or boundary solution.
- Optimal CPU-cycle Frequencies: The optimal CPU frequency increases with task-buffer backlog because executing more tasks helps keep queue length small.
- Optimal CPU-cycle Frequencies: The optimal CPU frequency decreases with V and the computation intensity parameter Li.Larger V increases the power weight, while larger Li makes local execution less efficient.
- Optimal Transmit Power and Bandwidth Allocation: The alternating minimization procedure converges to the global optimum because SP2 is jointly convex with a Cartesian-product feasible region.Transmit powers are obtained in closed form and bandwidth allocation is determined by the Lagrangian method.
- Optimal Transmit Power and Bandwidth Allocation: For fixed bandwidth, transmit power is optimized per device through a bounded problem whose solution is attained at a stationary point or boundary.
- Optimal Transmit Power and Bandwidth Allocation: Bandwidth allocation is coupled across devices and is solved using the Lagrangian method and KKT conditions, with bisection used to find the optimal multiplier.
- Algorithm Properties: The online algorithm requires no prior task-arrival or channel-fading information and has low per-slot complexity.Closed-form CPU frequencies and efficient alternating minimization support these properties.
C. Performance Analysis
The analysis establishes upper bounds for mobile-device power consumption and task-buffer queue lengths, revealing an adjustable power-delay tradeoff governed by V.
- Theoretical guarantees: Theorem 1 provides upper bounds on mobile-device power consumption and average task-buffer queue length under the proposed policy.It also establishes mean rate stability for every task queue when the optimization problem is feasible.
- Power-delay tradeoff: The average power consumption approaches the optimum with a gap that decreases inversely with V.The optimum is represented by the optimal value of P2.
- Power-delay tradeoff: The upper bound on execution delay increases linearly with V, yielding an [O (1/V), O (V)] power-delay tradeoff.The tradeoff follows from inverse power reduction and linear delay growth as V changes.
- Design implication: Small V is suited to delay-sensitive applications, whereas large V is suited to energy-sensitive networks and delay-tolerant applications.Adjusting V balances the conflicting power-consumption and execution-delay objectives.
V. SIMULATION RESULTS
Simulations validate the theoretical power-delay tradeoff and show how MEC availability, task arrivals, and user count affect execution delay and power consumption.
- Control-parameter effects: Power consumption decreases inversely with V and converges to P opt Σ for sufficiently large V, while average queue length increases linearly with V.The queue-length behavior verifies the predicted [O (1/V), O (V)] tradeoff.
- MEC comparison: With MEC, execution delay decreases from 33.2 to 1.05 ms as V decreases, whereas without MEC it remains around 103 ms.Without MEC, devices cannot stabilize task buffers even with small V because local CPUs operate at maximum frequency.
- Parameter effects: As power consumption decreases, average execution delay generally increases, so V must be selected to balance the two objectives.For N = 5 and Ai,max = 4 kbits, a 20 ms delay requirement corresponds to V = 3 × 10^9 bits^2 · W^-1 and 0.1 W power consumption.
- Parameter effects: At a given execution delay, power consumption increases with computation task arrival rate and the number of mobile devices.Heavier MEC workloads require more power to stabilize task buffers.
- Parameter effects: When V approaches infinity, doubling task arrival rates produces higher power consumption than doubling mobile devices.The difference is attributed to increased multi-user diversity gain and additional available local CPUs.
VI. CONCLUSIONS
The paper formulates and analyzes a multi-user MEC power-delay tradeoff using Lyapunov optimization, with simulations validating the resulting [O (1/V), O (V)] relationship.
- Conclusions: The study formulates a power-minimization problem with task-buffer stability constraints and derives an online local-execution and computation-offloading algorithm.The algorithm is based on Lyapunov optimization.
- Conclusions: Performance analysis characterizes an [O (1/V), O (V)] tradeoff between mobile-device power consumption and execution delay.Simulation results validate the theoretical analysis and show that the algorithm balances power consumption and computation experience quality.
- Future work: Future work could extend the findings to scenarios with fairness considerations among multiple devices.This identifies fairness as an open direction beyond the current study.