Learning-Based Task Offloading for Vehicular Cloud Computing Systems

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

TL;DR

This paper introduces AVUCB (Adaptive Volatile Upper Confidence Bound), a distributed learning algorithm that helps vehicles decide which neighboring car to offload computation tasks to. By treating neighboring vehicles as "arms" in a multi-armed bandit problem, the system learns to minimize processing delays in highly dynamic traffic environments without requiring constant, heavy communication overhead.

What Problem Does This Paper Address?

Modern vehicles are essentially mobile data centers, but individual tasks (like AR/VR or autonomous driving calculations) often exceed a single vehicle's capacity. Vehicular Cloud Computing (VCC) allows "Task Vehicles" (TaVs) to offload work to nearby "Service Vehicles" (SeVs) with spare CPU cycles.

However, VCC is a chaotic environment. Unlike static edge servers, vehicles move fast, wireless channels flicker, and an SeV’s available computing power fluctuates. Traditional centralized offloading requires massive signaling overhead to keep track of everyone's status. This paper seeks a distributed way for a vehicle to "learn" which neighbors are reliable performers on the fly, even as those neighbors enter and leave its communication range.

Methods

The authors frame the offloading decision as a Multi-Armed Bandit (MAB) problem. In a classic MAB scenario, a player pulls different levers (arms) to find the one with the best payout. Here, each neighboring SeV is an "arm," and the "payout" is a lower offloading delay.

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

  1. Occurrence-Awareness: Standard MAB assumes the set of arms is fixed. AVUCB handles a "volatile" action space where SeVs appear and disappear. It tracks the "occurrence time" of each SeV to prioritize learning about newcomers.
  2. Load-Awareness: The algorithm adjusts its exploration strategy based on the size of the current task. If a task is small, the "cost" of a bad offloading decision is low, so the algorithm uses it as a "cheap" opportunity to explore less-known SeVs. If the task is large, it plays it safe and offloads to a known high-performer (exploitation).

Datasets

The researchers evaluated their algorithm using two primary setups:

  • Synthetic Scenario: A MATLAB simulation with 1 TaV and 5 SeVs with varying CPU capacities and randomized movement to test basic convergence and volatility handling.
  • Realistic Highway Scenario: They used SUMO (Simulation of Urban MObility) to model a 12km stretch of the G6 Highway in Beijing. This included realistic traffic flows, ramps where vehicles enter/exit, and speeds up to 90 km/h, providing a rigorous test of the algorithm's ability to handle rapid topology changes.

Key Insights and Ideas

  • The "Cheap Exploration" Strategy: One of the most intuitive "aha" moments is the use of task size as a weighting factor. By normalizing the input data size, the algorithm intelligently decides when it can afford to be curious and when it needs to be efficient.
  • Distributed over Centralized: By allowing each vehicle to learn independently based on its own historical observations (delay feedback), the system eliminates the need for a central controller to constantly poll every vehicle for its current CPU load and channel state.
  • Mathematical Regret Bounds: The authors don't just show it works in simulation; they provide theoretical proofs that the "regret" (the performance gap between their algorithm and an omniscient optimal solver) grows only logarithmically over time, which is the gold standard for MAB algorithms.

Key Results

  • Regret Reduction: In scenarios where SeVs appear and disappear, AVUCB reduced the "learning regret" by approximately 50% compared to the standard UCB1 algorithm.
  • Fast Convergence: The average delay achieved by AVUCB converged to near-optimal levels much faster than baseline learning algorithms.
  • Robustness: In the realistic SUMO highway simulation, AVUCB consistently outperformed UCB1, VUCB1 (occurrence-aware only), and random policies, maintaining a delay profile very close to the "Optimal Policy" (which assumes perfect future knowledge).

Limitations and Future Work

  • I.I.D. Assumption: The theoretical analysis assumes that bit offloading delays are independent and identically distributed (i.i.d.) over time. While simulations showed the algorithm works even when this isn't strictly true, real-world bursty traffic might challenge this.
  • Single-Hop Focus: The current model assumes a TaV offloads directly to a 1-hop neighbor. It does not yet account for multi-hop offloading or cooperation between multiple SeVs to solve a single task.
  • Heterogeneous Clouds: The authors suggest that future work should look at how this learning approach integrates with a "three-tier" architecture involving SeVs, local MEC servers, and the remote cloud simultaneously.

Summary updated

Abstract

Vehicular cloud computing (VCC) is proposed to effectively utilize and share the computing and storage resources on vehicles. However, due to the mobility of vehicles, the network topology, the wireless channel states and the available computing resources vary rapidly and are difficult to predict. In this work, we develop a learning-based task offloading framework using the multi-armed bandit (MAB) theory, which enables vehicles to learn the potential task offloading performance of its neighboring vehicles with excessive computing resources, namely service vehicles (SeVs), and minimizes the average offloading delay. We propose an adaptive volatile upper confidence bound (AVUCB) algorithm and augment it with load-awareness and occurrence-awareness, by redesigning the utility function of the classic MAB algorithms. The proposed AVUCB algorithm can effectively adapt to the dynamic vehicular environment, balance the tradeoff between exploration and exploitation in the learning process, and converge fast to the optimal SeV with theoretical performance guarantee. Simulations under both synthetic scenario and a realistic highway scenario are carried out, showing that the proposed algorithm achieves close-to- optimal delay performance.
BibTeX
@inproceedings{sun2018learning,
  author = {Yuxuan Sun and Xueying Guo and Sheng Zhou and Zhiyuan Jiang and Xin Liu and Zhisheng Niu},
  title = {{Learning-Based Task Offloading for Vehicular Cloud Computing Systems}},
  booktitle = {ICC},
  year = {2018},
  url = {https://openreview.net/forum?id=1m-xcidT-n1c},
}

Loading related content...

Figure