Adaptive Learning-Based Task Offloading for Vehicular Edge Computing Systems

Yuxuan Sun, Xueying Guo, Jinhui Song, Sheng Zhou, Zhiyuan Jiang, Xin Liu, Zhisheng Niu

TL;DR

This paper introduces ALTO (Adaptive Learning-based Task Offloading), a distributed algorithm that allows vehicles to "learn while offloading" in the highly volatile environment of Vehicular Edge Computing (VEC). By treating neighboring vehicles as "arms" in a multi-armed bandit (MAB) framework, ALTO minimizes offloading delays by intelligently balancing the exploration of new service providers with the exploitation of known high-performers, specifically adapting to varying task sizes and the constant arrival/departure of vehicles.

What Problem Does This Paper Address?

Vehicular Edge Computing (VEC) aims to turn cars into moving data centers. A "Task Vehicle" (TaV) with a heavy computation load (like autonomous driving sensor fusion or video processing) can offload work to nearby "Service Vehicles" (SeVs) with spare CPU cycles.

However, VEC is a nightmare for traditional optimization:

  1. High Mobility: Vehicles enter and leave communication range rapidly, meaning the set of available "servers" is always changing.
  2. Uncertainty: A TaV doesn't know the current CPU load or wireless channel quality of its neighbors without massive signaling overhead.
  3. Dynamic Workloads: Task sizes vary; a bad offloading decision for a tiny task is a minor hiccup, but a bad decision for a massive task causes a significant delay spike.

The authors tackle the challenge of making optimal offloading decisions in a distributed manner without requiring frequent, bandwidth-heavy state exchanges between vehicles.

Methods

The authors frame the problem as a Multi-Armed Bandit (MAB) problem. In a classic MAB, a gambler chooses between multiple slot machines (arms) with unknown reward distributions. Here, each SeV is an "arm," and the "reward" is the inverse of the offloading delay.

The core contribution is the ALTO algorithm, which improves upon the standard Upper Confidence Bound (UCB) approach with two novel features:

  • Input-Awareness: ALTO normalizes the input task size ($x_t$). It realizes that when a task is small, the "cost" of a mistake is low, so it uses small tasks as opportunities to explore less-known SeVs. When a task is large, it prioritizes exploitation of the best-known SeV to avoid massive delays.
  • Occurrence-Awareness: Unlike standard MABs where the set of arms is fixed, ALTO tracks the "birth time" of each SeV. It uses a padding function that accounts for how long an SeV has been available, ensuring that newly arrived vehicles are given a fair chance to be tested.

The algorithm is distributed; each TaV maintains its own local estimates of SeV performance based on past observations of total delay (upload + execution + download).

Datasets

The paper relies on two types of simulation environments rather than static datasets:

  1. Synthetic Scenario: A MATLAB-based simulation with 8 SeVs and 3 distinct "epochs" where SeVs appear and disappear to test the algorithm's theoretical bounds.
  2. Realistic Highway Scenario: The authors used the Veins framework, which couples SUMO (Simulation of Urban MObility) for realistic traffic patterns with OMNeT++ for accurate wireless network modeling. They simulated a 12km segment of the G6 Highway in Beijing using map data from OpenStreetMap (OSM).

Key Insights and Ideas

  • Learning is better than Signaling: Instead of asking every neighbor "How busy are you?" every millisecond (which congests the network), it is more efficient for the TaV to simply observe how long tasks take and build a statistical model of its neighbors.
  • The "Small Task" Opportunity: One of the most clever insights is using task size as a control for exploration. By weighting the exploration term with $(1 - \tilde{x}_t)$, the algorithm naturally becomes more "adventurous" when the stakes are low and "conservative" when the stakes are high.
  • Sublinear Regret: The authors mathematically prove that ALTO achieves "sublinear regret." In layman's terms, this means that as time goes on, the gap between ALTO's performance and a "Genie" (who knows everything perfectly) grows slower and slower, eventually converging toward optimal behavior.

Key Results

  • Delay Reduction: In highway simulations, ALTO reduced average offloading delay by up to 30% compared to the standard UCB algorithm.
  • Regret Optimization: ALTO outperformed existing variants like VUCB (occurrence-aware) and AdaUCB (input-aware) by 30% to 65%, and outperformed basic UCB by 85% in terms of cumulative learning regret.
  • Fast Convergence: The "Average Delay vs. Time" plots show that ALTO reaches a stable, near-optimal state much faster than competing algorithms, which is crucial in a vehicular environment where an SeV might only be nearby for a few minutes.

Limitations and Future Work

  • Stochastic Assumption: The theoretical proof assumes delay distributions are independent and identically distributed (i.i.d.). In reality, traffic congestion or a sudden burst of tasks from other vehicles could create "adversarial" conditions where delays are correlated.
  • Single TaV Focus: While the algorithm is distributed, the simulations primarily focus on the performance of a single TaV. Future work could explore the "Tragedy of the Commons" where multiple TaVs all try to offload to the same "best" SeV simultaneously, potentially crashing its performance.
  • RSU Integration: The paper briefly mentions Road Side Units (RSUs) as a fallback but doesn't deeply explore the joint optimization of vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) offloading.

Summary updated

Abstract

The vehicular edge computing system integrates the computing resources of vehicles, and provides computing services for other vehicles and pedestrians with task offloading. However, the vehicular task offloading environment is dynamic and uncertain, with fast varying network topologies, wireless channel states, and computing workloads. These uncertainties bring extra challenges to task offloading. In this paper, we consider the task offloading among vehicles, and propose a solution that enables vehicles to learn the offloading delay performance of their neighboring vehicles while offloading computation tasks. We design an adaptive learning based task offloading (ALTO) algorithm based on the multi-armed bandit theory, in order to minimize the average offloading delay. ALTO works in a distributed manner without requiring frequent state exchange, and is augmented with input-awareness and occurrence-awareness to adapt to the dynamic environment. The proposed algorithm is proved to have a sublinear learning regret. Extensive simulations are carried out under both synthetic scenario and realistic highway scenario, and results illustrate that the proposed algorithm achieves low delay performance, and decreases the average delay up to 30% compared with the existing upper confidence bound based learning algorithm.
BibTeX
@article{sun2019adaptive,
  author = {Yuxuan Sun and Xueying Guo and Jinhui Song and Sheng Zhou and Zhiyuan Jiang and Xin Liu and Zhisheng Niu},
  title = {{Adaptive Learning-Based Task Offloading for Vehicular Edge Computing Systems}},
  journal = {IEEE Trans. Vehicular Technology},
  year = {2019},
  url = {https://openreview.net/forum?id=YMTrGc7vRY},
}

Loading related content...

Figure