Stochastic Control of Computation Offloading to a Helper With a Dynamically Loaded CPU

Yunzheng Tao, Changsheng You, Ping Zhang, Kaibin Huang

TL;DR

This paper introduces an energy-efficient strategy for IoT devices to offload heavy computation tasks to "opportunistic" helpers—like nearby smartphones or access points—whose CPUs are often busy with their own primary tasks. By modeling the randomness of both the wireless channel and the helper's CPU availability as Markov chains, the authors derive control policies that minimize energy consumption while strictly meeting task deadlines, effectively beating the "curse of dimensionality" typically found in such optimization problems.

What Problem Does This Paper Address?

Mobile Edge Computing (MEC) usually assumes the existence of dedicated, always-available servers. However, in a dense "Internet of Things" (IoT) environment, the most accessible computing resources are often "opportunistic helpers"—devices like a neighbor's smartphone or a local router.

The challenge is that these helpers are not dedicated; their CPU resources are "random and intermittent" because they prioritize their own primary functions. An IoT device offloading a task faces a dual-uncertainty problem:

  1. Channel Randomness: The wireless link quality fluctuates.
  2. Helper Randomness: The helper's CPU might suddenly become "busy," forcing offloaded data to sit in a buffer or requiring the user to compute more locally to meet a deadline.

The authors seek to find the optimal "offloading policy"—deciding exactly how much data to compute locally versus how much to send to the helper in each time slot—to minimize total energy use without missing the deadline.

Methods

The authors frame the problem as a finite-horizon Markov Decision Process (MDP). They model the system using four state variables: the helper CPU state (idle/busy), the channel state (good/bad), the remaining data to be computed, and the current buffer size at the helper.

Key technical approaches include:

  • Stochastic Modeling: Using stationary Markov chains to represent the temporal correlation of the wireless channel (Gilbert-Elliott model) and the helper's CPU load.
  • Dynamic Programming (DP): While standard DP can solve these problems numerically, it suffers from the "curse of dimensionality" (computational complexity grows exponentially with the number of states).
  • Closed-Form Derivations: For the "zero-buffer" case, the authors successfully derive an optimal policy in closed form.
  • Approximation & Policy Selection: For large and small buffer scenarios where the math becomes intractable, they develop sub-optimal policies based on energy-cost function approximations and a "Buffer-Aware Candidate-Policy Selection" (BACS) scheme.

Datasets

This paper does not use a real-world dataset. Instead, it validates the proposed policies through numerical simulations based on standard empirical models in the field:

  • Task Size: Typically 3000 to 5000 bits.
  • Time Horizon: 5 to 8 slots (100ms each).
  • Power Model: Monomial functions for transmission and local CPU power (common in MEC literature).
  • Transition Probabilities: Set to $P_{gg}=0.8$ (channel) and $P_{11}=0.8$ (CPU) to simulate realistic temporal correlation.

Key Insights and Ideas

  • Proportional Offloading: In the zero-buffer case, the optimal amount of data to offload in any given slot is always proportional to the remaining data. The "scaling factor" is determined by the instantaneous channel and CPU states.
  • The Buffer as a "Shock Absorber": A helper buffer allows the user to exploit "good" channel states even when the helper CPU is currently busy, storing data for future processing. However, there is a point of diminishing returns; once the buffer is large enough (around 1000 bits in their tests), increasing it further yields no extra energy savings.
  • Complexity Reduction: By deriving structured policies, the authors reduced the computational complexity from $O(D^4)$ (where $D$ is data size) to a mere $O(4K)$ (where $K$ is the number of slots). This makes the algorithm light enough to run on low-power IoT hardware in real-time.
  • Demand-Computing: The authors introduce a "demand-computing" constraint for the final time slot, ensuring that if the helper is busy at the very end, the user scales up its own CPU frequency to finish the task on time, regardless of the energy cost.

Key Results

  • Energy Savings: The proposed stochastic policies achieved approximately 30% reduction in energy consumption compared to a baseline "equal-allocation" policy.
  • Near-Optimality: The sub-optimal policies designed for large/small buffers were shown to be within 7% of the true numerical optimum found via brute-force DP, while being significantly faster to compute.
  • Linear Sensitivity: Energy consumption was found to decrease almost linearly as the helper's "idle probability" increased, highlighting the high value of even slightly under-utilized edge resources.

Limitations and Future Work

  • One-Shot Tasks: The current model assumes a single task with a fixed deadline. Real-world IoT devices often deal with "bursty" data arrivals, which would require a more complex queuing model.
  • Single Helper: The paper focuses on a one-to-one user-helper relationship. Future work could explore "collaborative offloading" where a user chooses between multiple available opportunistic helpers.
  • Helper Capacity: The model assumes the helper has "unlimited" computation capacity when idle. Incorporating finite helper CPU speeds would add another layer of realism (and complexity) to the optimization.

Summary updated

BibTeX
@article{tao2019stochastic,
  author = {Yunzheng Tao and Changsheng You and Ping Zhang and Kaibin Huang},
  title = {{Stochastic Control of Computation Offloading to a Helper With a Dynamically Loaded CPU}},
  journal = {IEEE Trans. Wireless Communications},
  year = {2019},
  doi = {10.1109/twc.2018.2890653},
}
Figure