PaperlayerView exact revision on arXiv

Source-linked AI summary

Dynamic Computation Offloading for Mobile-Edge Computing with Energy Harvesting Devices

Yuyi Mao, Jun Zhang, Khaled B. Letaief

arXiv:1605.05488v1cs.IT

TL;DR

Limited mobile-device energy can interrupt computation, motivating green MEC systems powered by energy harvesting. The paper develops LODCO, a low-complexity online strategy that jointly controls offloading, local CPU frequency, and transmit power using instantaneous side information. Analysis establishes asymptotic optimality, and simulations show LODCO outperforms greedy benchmark policies in execution cost.

  • Problem

    Limited battery energy can interrupt mobile computation, creating a need for green MEC systems that use energy harvesting while maintaining computation performance.

  • Method

    LODCO is a low-complexity online algorithm that jointly decides offloading, mobile CPU-cycle frequencies, and transmit power using limited prior knowledge.

  • Results

    The proposed algorithm is asymptotically optimal and outperforms greedy benchmark policies in execution cost.

  • Takeaways & Limitations

    LODCO provides an online computation-offloading strategy for MEC systems with energy-harvesting devices and requires little prior knowledge.

  • Takeaways & Limitations

    The paper identifies extending the framework to MEC systems with multiple mobile devices and resource-limited MEC servers as worthwhile future work.

Abstract

from arXiv · show

Mobile-edge computing (MEC) is an emerging paradigm to meet the ever-increasing computation demands from mobile applications. By offloading the computationally intensive workloads to the MEC server, the quality of computation experience, e.g., the execution latency, could be greatly improved. Nevertheless, as the on-device battery capacities are limited, computation would be interrupted when the battery energy runs out. To provide satisfactory computation performance as well as achieving green computing, it is of significant importance to seek renewable energy sources to power mobile devices via energy harvesting (EH) technologies. In this paper, we will investigate a green MEC system with EH devices and develop an effective computation offloading strategy. The execution cost, which addresses both the execution latency and task failure, is adopted as the performance metric. A low-complexity online algorithm, namely, the Lyapunov optimization-based dynamic computation offloading (LODCO) algorithm is proposed, which jointly decides the offloading decision, the CPU-cycle frequencies for mobile execution, and the transmit power for computation offloading. A unique advantage of this algorithm is that the decisions depend only on the instantaneous side information without requiring distribution information of the computation task request, the wireless channel, and EH processes. The implementation of the algorithm only requires to solve a deterministic problem in each time slot, for which the optimal solution can be obtained either in closed form or by bisection search. Moreover, the proposed algorithm is shown to be asymptotically optimal via rigorous analysis. Sample simulation results shall be presented to verify the theoretical analysis as well as validate the effectiveness of the proposed algorithm.

I. INTRODUCTION

Mobile applications create a tension between resource-limited devices and computation-intensive workloads, while conventional cloud offloading can incur WAN latency. MEC reduces latency and can prolong battery lifetime, but EH-enabled MEC requires jointly designing offloading, local execution, transmission, and energy-aware policies.

  • Motivation: Computation-intensive mobile applications strain resource-limited devices, compromising satisfactory quality of experience.Examples include navigation, face recognition, and interactive online gaming.
  • Motivation: MEC offloads tasks to physically proximal servers, potentially reducing latency, avoiding congestion, and prolonging mobile-device battery lifetime.Conventional cloud systems may incur long latency through data exchange over wide-area networks.
  • Energy constraints: Battery exhaustion can terminate mobile applications and make devices unavailable, while larger batteries increase hardware cost and frequent recharging may be impractical.The latter issue is especially relevant to hard-to-reach wireless sensor networks and IoT surveillance nodes.
  • Energy harvesting: Energy harvesting captures recyclable ambient energy such as solar radiation, wind, and human motion, supporting self-sustainability, perpetual operation, and green computing.The ICT sector’s increasing energy consumption strengthens the motivation for renewable energy sources.
  • Contribution: The paper develops new design methodologies for MEC systems with energy-harvesting devices to address these challenges.Prior computation offloading work includes code offloading, stochastic control, decentralized algorithms, and joint communication-computation resource allocation.
  • Design challenges: EH-enabled MEC introduces a joint design problem involving offloading decisions, mobile CPU-cycle frequencies, transmission policies, and time-correlated battery dynamics.Its objective shifts from minimizing battery energy consumption toward optimizing computation performance because harvested energy comes for free.

B. Contributions

The paper develops an EH-enabled MEC system and proposes LODCO for online computation offloading under causal side information. LODCO jointly manages execution mode, CPU frequency, and transmit power, with asymptotic optimality and reduced task failure supported by analysis and simulations.

  • System model: The paper studies an MEC system with an energy-harvesting mobile device whose tasks may run locally or be offloaded to the MEC server.The device is powered by harvested energy, and tasks can also be dropped when neither execution mode is feasible.
  • Performance metric: The execution cost combines execution delay and task failure, while DVFS and transmit-power control optimize local execution and offloading.The metric penalizes both delay and dropped tasks.
  • Problem formulation: The ECM problem is formulated as an intractable high-dimensional Markov decision problem using causal side information.The formulation accounts for current system information without assuming future side information.
  • LODCO algorithm: LODCO makes per-slot offloading, CPU-frequency, and transmit-power decisions by solving a deterministic optimization problem in closed form or through bisection search.The algorithm is designed as a low-complexity online policy.
  • Structural property: The proposed policy identifies a non-decreasing relationship between available battery energy and scheduled CPU-cycle frequencies or transmit power.More available energy is associated with shorter execution delay for mobile execution or MEC-server execution.
  • Performance analysis: LODCO achieves asymptotically optimal ECM performance by tuning two control parameters without requiring statistical information about tasks, channels, or EH processes.This supports operation when the involved stochastic processes are unpredictable.
  • Simulation evaluation: Simulations compare LODCO with three benchmark policies and report improved execution cost together with reduced task failure.The simulations are intended to verify the theoretical asymptotic-optimality analysis.

C. Energy Harvesting Model

The EH model represents renewable energy as intermittent packet arrivals, with harvested energy stored for later computation or transmission. The formulation uses an effectively large battery while showing that the proposed policy yields a finite practical capacity bound.

  • Energy arrivals: The EH process is modeled as successive energy-packet arrivals with a maximum harvestable-energy value Emax.The model captures stochastic and intermittent renewable-energy behavior.
  • Energy storage: A selected amount of each arriving energy packet is harvested and stored for local execution or computation offloading starting in the next time slot.The stored energy is not immediately available within the arrival slot.
  • Battery capacity: The analysis initially assumes a sufficiently large battery, then shows that the battery level is deterministically upper-bounded under the proposed policy.This establishes that only a finite-capacity battery is needed in implementation.
  • Optimization formulation: Including harvested-energy decisions as optimization variables facilitates the derivation and performance analysis of the algorithm.The approach follows related techniques used in earlier studies.
  • Battery dynamics: Battery energy evolves through harvested energy and device consumption, subject to energy-causality constraints.Consumption depends on the selected mode, CPU frequency, and transmit power.
  • Model scope: The baseline model ignores energy consumed by screens and operating systems, although more general energy models can be handled with minor modifications.The paper discusses adapting the algorithm to include such consumption.
  • Control challenge: EH computation-offloading control must handle both energy and channel information while balancing current-task performance against future-task performance.Temporally correlated battery levels couple decisions across time slots.

III. PROBLEM FORMULATION

The paper formulates execution-cost minimization for EH-enabled MEC as a long-term control problem that balances delay and dropped tasks under energy, channel, and device constraints. It then identifies the dimensionality and temporal-coupling challenges of standard MDP solutions.

  • III. PROBLEM FORMULATION: The execution-cost minimization section defines the performance metric and formulates the ECM problem while identifying its technical challenges.Execution delay is treated as a key QoE measure.
  • A. Execution Cost Minimization Problem: The system can execute tasks locally or at the MEC server, but intermittent energy and deep channel fading can force task dropping.Dropped tasks are penalized in the objective.
  • A. Execution Cost Minimization Problem: Execution cost is the weighted sum of execution delay and task-dropping cost, with φ weighting the dropping penalty.The formulation assumes τd ≤ φ so successful execution is preferred to dropping.
  • A. Execution Cost Minimization Problem: Problem P1 minimizes long-term average execution cost over computation modes, CPU frequencies, transmit power, and harvested-energy decisions.Its constraints include operation, deadline, energy-causality, battery, power, frequency, and indicator restrictions.
  • A. Execution Cost Minimization Problem: P1 includes battery-discharge, maximum-power, maximum-frequency, and binary computation-mode constraints.The battery-output constraint prevents over-discharging within a time slot.
  • B. Problem Analysis: The system state contains task, harvestable-energy, battery, and channel information, while actions select computation mode, CPU frequency, and transmit power.Allowable actions depend on the current state rather than state and action history.
  • B. Problem Analysis: P1 is a Markov decision process, but standard MDP algorithms require finite state and action quantization that can cause large computational and storage burdens.For the example quantization, 2KME = 4000 system states, and action-space growth can make LP methods infeasible even for W = 1000.
  • B. Problem Analysis: Quantization may severely degrade performance and makes storing the optimal policy difficult, motivating a low-complexity alternative without state or action discretization.The proposed LODCO algorithm is introduced to address these limitations.

IV. DYNAMIC COMPUTATION OFFLOADING: THE LODCO ALGORITHM

LODCO simplifies the EH offloading problem through structural properties, a modified ECM formulation, and Lyapunov control with a virtual energy queue. Its performance approaches the original problem as the perturbation lower bound vanishes.

  • Algorithm design: The algorithm design first establishes an optimal CPU-frequency property, then introduces a modified ECM problem to enable Lyapunov optimization.The resulting LODCO solution is feasible for P1 and is later shown asymptotically optimal.
  • CPU-frequency structure: All scheduled CPU cycles for a locally executed task use the same frequency, reducing the decision from a W-dimensional vector to a scalar f_t.This property reduces the number of optimization variables.
  • Modified ECM problem: A positive lower bound Emin on battery output energy removes cross-slot coupling from the per-slot optimization and yields modified problem P2.P2 retains P1’s constraints while adding the battery-output restriction.
  • Asymptotic relation: As Emin approaches zero, ν(Emin) vanishes and P2 can be made arbitrarily close to P1.Thus the modified problem preserves asymptotic optimality relative to the original formulation.
  • Lyapunov framework: Because battery levels are temporally correlated, LODCO uses weighted perturbation, a perturbation parameter θ, and a virtual energy queue ˜B_t = B_t − θ.These devices address the time-dependent allowable action sets that prevent direct use of vanilla Lyapunov optimization.
  • Per-slot control: In each time slot, LODCO minimizes a weighted sum of net harvested energy and execution cost, using the virtual queue length and control parameter V as weights.The queue is driven toward θ while execution cost is minimized.
  • Implementation: Algorithm 1 observes current task, energy, and channel information, solves a deterministic constrained problem, updates the virtual queue, and advances to the next slot.The framework can also be modified to account for basic-operation power consumption, although those changes are not detailed.

B. Optimal Computation Offloading in Each Time Slot

The per-time-slot problem is decomposed into local execution, MEC offloading, harvesting, and task dropping, with each mode solved through feasibility conditions and objective minimization. The optimal offloading decision compares the resulting costs across the three computation modes.

  • Mobile execution: Local execution is feasible if and only if fL ≤ fU, where fL = max{κW, fmax}.
  • Mobile execution: The optimal local CPU-cycle frequency balances harvested-energy cost against execution cost and increases with the virtual energy queue length.A higher frequency reduces execution delay when more harvested energy is available.
  • Mobile execution: The optimal local CPU-cycle frequency is independent of the channel gain ht.
  • MEC offloading: MEC offloading may be infeasible under wireless fading because the feasible transmit-power set changes with the channel gain.The battery output-energy constraint prevents the optimal transmit power from being monotonic in ht.
  • MEC offloading: For feasible offloading, the optimal transmit power is non-decreasing with the virtual energy queue length and depends on both battery energy and channel state.A higher battery energy level yields higher transmit power and smaller execution latency.
  • Optimal computation offloading: The optimal computation mode is selected by evaluating the PCO objective for task dropping, mobile execution, and MEC-server execution.When no computation task arrives, PCO has a single feasible action with zero execution and transmission power.

V. PERFORMANCE ANALYSIS

The performance analysis establishes feasibility of LODCO and then analyzes the performance achievable by the proposed algorithm.

  • The section first proves LODCO feasibility and then analyzes the performance achieved by the proposed algorithm.

A. Feasibility

The feasibility analysis shows that LODCO preserves energy causality under its per-time-slot optimal decisions. It also bounds the device battery level and gives a storage condition for selecting the control parameter.

  • When Bt < Ẽmax, the optimal per-time-slot solution sets harvested energy, local frequency, and transmit power to zero, so energy causality is not violated.
  • The LODCO battery energy level is confined within an interval determined by the algorithm’s energy thresholds.
  • The battery capacity should exceed Ẽmax + Emax − Emin to guarantee V > 0.

B. Asymptotic Optimality

The asymptotic analysis compares LODCO with auxiliary relaxed problems and derives a worst-case execution-cost bound. The bound becomes arbitrarily tight as V increases and Emin decreases, yielding asymptotic optimality for the original design problem.

  • P3 relaxes P2 by replacing energy causality with equality between average harvested-energy consumption and average harvested energy.
  • For any δ > 0, a stationary randomized policy for P3 can approach its optimum while keeping the energy-consumption discrepancy arbitrarily small.
  • Theorem 1 upper-bounds the execution cost achieved by LODCO and characterizes its worst-case performance.
  • As V → +∞ and Emin → 0, the execution-cost upper bound becomes arbitrarily tight, so LODCO asymptotically achieves the optimal performance of P1.
  • The asymptotic guarantee requires higher battery capacity and longer convergence time, creating a tunable trade-off with system performance.Increasing V or decreasing Emin raises the battery-energy stabilization level and postpones convergence.

VI. SIMULATION RESULTS

Simulations verify LODCO’s feasibility and asymptotic optimality, then evaluate its performance across system parameters against three greedy benchmark policies. LODCO reduces execution cost and task drops while trading off completion time, convergence, and battery capacity.

  • Theoretical Results Verification: LODCO confines the battery energy level and satisfies energy causality, confirming the algorithm’s feasibility.The harvested energy accumulates and stabilizes around a perturbed level under the proposed control.
  • Theoretical Results Verification: Larger V or smaller Emin lowers long-term average execution cost but slows convergence and raises the stabilized energy level.These parameters therefore require balancing performance against convergence behavior.
  • Theoretical Results Verification: Execution cost decreases inversely with V and converges to the optimal value of P2, while required battery capacity grows linearly with V.For an 18 mW battery, V = 1.6 × 10−4 J2 · second−1 yields 74.4%, 51.8% and 46.3% gains over the three benchmarks.
  • Performance Evaluation: As device distance increases, offloading performance deteriorates; at d = 80 m, LODCO still provides more than 40% performance gain over Mobile Execution (GD).When the device is close to the MEC server, offloading policies converge and outperform Mobile Execution (GD).

VII. CONCLUSIONS

The paper studies MEC systems with energy-harvesting mobile devices and proposes LODCO for dynamic offloading under renewable-energy constraints. Analysis and simulations report asymptotic optimality, lower execution cost and fewer computation failures, with minor delay degradation.

  • VII. CONCLUSIONS: LODCO is a low-complexity dynamic computation offloading algorithm for MEC systems with energy-harvesting mobile devices.The execution cost measures both execution delay and task failure.
  • VII. CONCLUSIONS: The algorithm’s decisions include mobile CPU-cycle frequencies and computation-offloading transmit power, whose monotonic dependence on battery energy was characterized.These properties describe how energy harvesting affects system operations.
  • VII. CONCLUSIONS: Theoretical analysis establishes the asymptotic optimality of the proposed algorithm.The analysis includes the bound EC_LODCO ≤ EC* for the long-term execution cost.
  • VII. CONCLUSIONS: The study presents a viable approach for designing future MEC systems powered by renewable energy.Extensions include multiple mobile devices, resource-limited MEC servers, and wireless energy transfer combined with energy harvesting.

APPENDIX

The appendix proves properties of the optimization problems and establishes the execution-cost bound used for LODCO’s optimality result. It also derives monotonicity of transmit power with respect to the transformed battery-energy variable.

  • Optimization-problem relationship: The appendix relates P2 to P1 by treating P2 as a tightened version of P1 and constructing feasible solutions between them.The construction handles cases involving infeasible or dropped tasks and bounds the resulting extra execution cost.
  • Energy-feasibility construction: The minimum energy required to meet the mobile-execution deadline is denoted by E_min.When available energy is below E_min, the deadline constraint cannot be met for mobile execution.
  • Energy-feasibility construction: The constructed solution incurs at most φ units of extra execution cost, with task-request probability ρ incorporated into the resulting bound.This supports the comparison between the two optimization formulations.
  • Monotonicity: The transmit power p_t* is non-decreasing with the transformed battery-energy variable B̃_t.The derivation uses the fact that k(h,p) decreases with p for p > 0 and covers both signs of B̃_t.
  • Theorem 1: The Lyapunov drift-plus-penalty analysis leads to EC_LODCO ≤ EC* after conditional expectations, summation over time slots, and division by T as T approaches infinity.The proof uses LODCO’s optimal solution to the per-time-slot problem.
Loading 1605.05488v1…