PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Learning-Based Task Offloading for Vehicular Edge Computing Systems

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

arXiv:1901.05205v1cs.IT

TL;DR

Vehicular task offloading must cope with rapidly changing topology, wireless channels, and computing workloads that obscure the best service vehicle. The paper proposes distributed ALTO, which learns delay during offloading and adapts exploration to task inputs and vehicle occurrence. ALTO achieves low delay, reduces average delay by up to 30% versus UCB, and has sublinear learning regret.

  • Problem

    Dynamic candidate service vehicles, task workloads, network topology, wireless channels, and computing loads make service-vehicle delay difficult to know before offloading.

  • Method

    ALTO applies multi-armed bandit learning so each task vehicle learns candidate service-vehicle delay during distributed offloading without frequent state exchange.

  • Results

    30%: ALTO decreases average delay by up to 30% compared with the existing upper confidence bound based learning algorithm and achieves sublinear learning regret.

  • Takeaways & Limitations

    ALTO adapts task offloading to dynamic vehicular environments while maintaining low delay without frequent exchange of accurate state information.

Abstract

from arXiv · show

The vehicular edge computing (VEC) 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 work, 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 (MAB) 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.

I. INTRODUCTION

Vehicular edge computing uses vehicle and infrastructure resources for low-latency services, but vehicle-to-vehicle offloading must operate under rapidly changing and poorly known conditions. The paper proposes ALTO, a distributed MAB-based approach that learns service-vehicle delay during offloading and adapts to task and vehicle dynamics.

  • VEC combines vehicle and infrastructure computing resources to process tasks from vehicles, onboard devices, and pedestrians.
  • Vehicle-to-vehicle offloading lets task vehicles independently select surrounding service vehicles with surplus computing resources.
  • Rapidly varying topology, wireless channels, and service-vehicle workloads make delay performance difficult to model or predict before offloading.
  • ALTO uses multi-armed bandits to learn neighboring service-vehicle delay while offloading, with distributed operation and no frequent accurate state exchange.
  • ALTO adds input-awareness and occurrence-awareness, and its learning regret is proved sublinear in the dynamic vehicular environment.

B. Task Offloading Algorithms

The paper models distributed vehicle-to-vehicle offloading as a sequence of discovery, upload, execution, and result-feedback procedures. Each task is assigned to one candidate service vehicle, whose total delay combines uplink, computation, and downlink delays.

  • Task vehicles generate computation tasks, while service vehicles provide execution resources; a vehicle’s role can change with resource sufficiency.
  • Each task vehicle may have multiple candidate service vehicles, but offloads each task to a single selected service vehicle.
  • Candidate discovery selects neighboring service vehicles within communication range and moving in the same direction, producing a time-varying set N(t).
  • The offloading procedure includes task upload, task execution, and result feedback after service-vehicle discovery.
  • Total offloading delay is the sum of uplink transmission, computation, and downlink transmission delays.

C. Problem Formulation

The formulation seeks to minimize average offloading delay when each task vehicle must choose among candidate service vehicles without reliable prior state information. The model treats observed per-bit delay as the service capability that must be learned online.

  • The optimization objective is to minimize average offloading delay over T time periods by selecting a service vehicle for each task.
  • The decision variable a_t is the index of the service vehicle selected at time t, constrained to a_t ∈ N(t).
  • Transmission rates and allocated CPU frequencies are difficult to predict and costly to exchange, so the task vehicle may not know which candidate minimizes delay.
  • Learning while offloading selects service vehicles from historical delay observations without acquiring exact transmission rates or CPU frequencies.
  • Under the simplified model, input size varies over time while computation intensity and output-to-input ratio remain constant.
  • Bit offloading delay reflects each candidate service vehicle’s service capability and is the quantity learned by the task vehicle.

IV. ADAPTIVE LEARNING-BASED TASK OFFLOADING ALGORITHM

ALTO adapts MAB task offloading to varying task inputs and dynamically appearing service vehicles. It evaluates candidates using empirical bit delay plus an exploration padding function, then updates estimates from observed completion delays.

  • ALTO is an MAB-based learning algorithm designed to minimize expected offloading delay by learning candidate service-vehicle performance.
  • ALTO normalizes task input size and records service-vehicle occurrence time and selection counts to support input- and occurrence-aware decisions.
  • Each newly appearing service vehicle is selected once to obtain an initial estimate of its bit offloading delay.
  • The utility combines empirical bit offloading delay with a padding function that balances exploration and exploitation under dynamic conditions.
  • ALTO explores more when task input size is small and exploits more when task input size is large.
  • Newly appearing service vehicles receive greater exploration, while repeatedly selected vehicles are increasingly exploited.

A. Complexity

ALTO has linear per-task computational complexity in the number of candidate SeVs and reduces signaling requirements by learning delay information instead of exchanging accurate states. Its regret analysis evaluates performance against a genie-aided optimal policy under dynamic candidate sets.

  • A. Complexity: O(N) complexity per task follows from computing all candidate utilities and selecting the minimum-delay SeV.Here, N = |N(t)| is the number of candidate SeVs in time period t.
  • A. Complexity: O(MN) total computation is required for M independently offloaded tasks across the VEC system.TaVs offload tasks independently, so the per-task complexity accumulates across M tasks.
  • A. Complexity: ALTO has lower complexity than the ant colony optimization baseline, whose reported complexity is O(KM 2N).K denotes the number of ant-colony iterations.
  • A. Complexity: ALTO avoids accurate channel, CPU-frequency, interference, and workload information exchange required by complete-state offloading.This makes the distributed policy easier to implement than the complete-state policy.
  • A. Complexity: The regret criterion is cumulative delay loss relative to a genie-aided policy that always selects the highest-capability SeV.The analysis uses learning regret to characterize ALTO's delay performance.

B. Regret Analysis under Dynamic SeV Set and Identical Input

For identical task inputs and a dynamically changing SeV set, ALTO's regret is analyzed by epochs and bounded logarithmically within each epoch. The resulting bound grows with the number of epochs, while greater SeV randomness increases regret over a fixed horizon.

  • B. Regret Analysis under Dynamic SeV Set and Identical Input: ALTO assumes identical input sizes by setting x_t = x_0 and normalized input ˜x_t = 0.This isolates the regret effect of a varying SeV set.
  • B. Regret Analysis under Dynamic SeV Set and Identical Input: Within each epoch, regret is O(ln T) and inversely proportional to the performance gap between optimal and suboptimal SeVs.The performance gap is denoted δ_n,b.
  • B. Regret Analysis under Dynamic SeV Set and Identical Input: O(B ln T) learning regret is achieved for any finite horizon T with B dynamic-SeV epochs.The bound captures the effect of repeated changes in the candidate set.
  • B. Regret Analysis under Dynamic SeV Set and Identical Input: Higher SeV appearance and disappearance randomness produces a more dynamic environment and higher regret within a fixed number of time periods.Randomness increases the number of epochs B, which appears in the regret bound.
  • B. Regret Analysis under Dynamic SeV Set and Identical Input: The theoretical analysis normalizes bit offloading delay to [0, 1], while the normalization maximum can be updated from observations in practice.The exact prior maximum delay may be difficult to acquire.

C. Regret Analysis under Varying Input and Fixed Candidate SeVs

Under varying task input with fixed candidate SeVs, ALTO’s regret is bounded logarithmically and can exploit input variation, while the fully dynamic case remains conjectural.

  • Varying input and fixed candidate SeVs: Theorem 2 bounds suboptimal-SeV selections and learning regret for finite horizons under varying input data.The result assumes β0 = 2 and P{xt ≤x−} > 0.
  • Varying input and fixed candidate SeVs: O(ln T ) regret shows ALTO can learn the best SeV under time-varying input data.The regret is sublinear relative to the genie-aided optimal policy.
  • Varying input and fixed candidate SeVs: Input-awareness adds E[xt|xt ≤x−] to the regret coefficient, which can be smaller than the fixed-input coefficient x0.Choosing x− so that E[xt|xt ≤x−] < x0 can reduce the regret bound relative to conventional UCB.
  • Joint occurrence and input variation: For periodic input and fixed bit offloading delay, Theorem 3 provides an upper bound on ALTO’s learning regret.The theorem assumes β0 = 2.
  • Joint occurrence and input variation: With jointly varying input size and candidate SeVs, ALTO still achieves O(ln T ) regret and explores only when input is low.The low-input condition is xt = ǫ0.
  • Joint occurrence and input variation: A general O(B ln T ) regret result for random continuous inputs and dynamic SeV sets is stated as a conjecture.The paper explains that jointly coupling vehicle occurrences and input variations makes the upper bound difficult to derive.

VI. SIMULATIONS

Simulations evaluate ALTO in synthetic and realistic settings, comparing it with learning baselines and examining key design parameters. ALTO achieves sublinear learning regret, faster convergence, and lower regret than the compared algorithms under the reported settings.

  • Simulation setup: ALTO is evaluated first in a synthetic scenario and then in a realistic highway scenario using Veins.The synthetic setup uses MATLAB and studies parameter effects before highway-level verification.
  • Algorithm comparison: ALTO decreases learning regret by 85%, 65% and 30% relative to UCB, VUCB and AdaUCB, respectively.The comparison includes UCB, VUCB, AdaUCB, and an optimal genie-aided lower bound.
  • Algorithm comparison: ALTO’s learning regret grows sublinearly with time, while its average delay converges faster to the optimal delay during each epoch.The reported average delay is close to optimal after convergence.
  • Parameter evaluation: When β0 = 0, eliminating exploration makes learning regret drastically worse than when β0 > 0; under these settings, regret is lowest at β0 = 0.2.The simulations report slightly increasing regret as β0 increases above zero, despite prior work associating sublinear regret with β0 > 0.5.
  • Parameter evaluation: Using equal upper and lower normalization thresholds yields lower regret than allowing exploration between the thresholds, with the lowest regret at ρ+ = ρ− = 0.05.The equal-threshold setting explores only when the input size is at or below x−.

B. Simulation under Realistic Highway Scenario

The realistic highway evaluation uses Veins to test ALTO under single- and multi-TaV conditions. ALTO achieves lower average delay than the comparison policies, with gains reaching 30% versus UCB when pAD = 0.1.

  • Scenarios: The experiments compare average delay for one TaV and for 10 TaVs departing every 10 seconds.The multi-TaV setting introduces competition for bandwidth and computing resources.
  • Simulation setup: The evaluation uses Veins with a 12 km Beijing highway segment, two lanes, two ramps, and vehicle speeds capped at 60 km/h.The TaV travels from A to D, while SeVs use routes A-D, A-C, and B-D.
  • Simulation setup: SeV arrivals follow a Bernoulli model with pAC = pBD = 0.05 and pAD ranging from 0.1 to 0.2.Random selection is included as a baseline alongside UCB, VUCB, and AdaUCB.
  • Results: ALTO always outperforms the other learning algorithms and the random policy in the reported highway experiments.The authors interpret this as evidence that ALTO adapts better to the vehicular environment.
  • Results: 30%: ALTO reduces average delay versus UCB when pAD = 0.1 with a single TaV; the reduction is 13% in the multi-TaV scenario.Average delay increases with TaV density, while higher SeV arrival probability lowers delay when TaV density is high.
  • Results: The broader evaluation reports up to 85% lower learning regret and up to 30% lower average delay than classical UCB.These results cover synthetic and realistic highway scenarios.

APPENDIX A PROOF OF LEMMA 1

The appendix derives a regret bound for ALTO by bounding regret within each epoch and summing across epochs. It also relates the special case B = 1 to an opportunistic bandit formulation.

  • Epoch-wise regret bound: The proof begins by defining learning regret in the bth epoch and bounding tasks assigned to suboptimal SeVs when β0 = 2.The bound uses prior lemmas and theorems from the cited literature.
  • Epoch-wise regret bound: The epoch regret bound is obtained by substituting the suboptimal-selection bound into the regret expression.The appendix then concludes the corresponding lemma.
  • Overall bound: Summing regret over the B epochs yields the overall regret bound and proves Theorem 1.The argument applies for every epoch b = 1, 2, ..., B with b ≤ T.
  • Special case: When β0 = 2 and B = 1, ALTO's utility and decision rules can be written in the forms used for the opportunistic bandit problem.The transformation assumes um ∈ [0, 1] and preserves equivalent definitions of regret, utility, and decision making.

APPENDIX D REGRET LOWER BOUND

This appendix gives a regret bound for the fixed-candidate, identical-input case. Under these conditions, ALTO reduces to classical UCB, allowing a divergence-based bound.

  • Assumptions: The lower-bound analysis considers identical input data size x0 and a fixed candidate SeV set N.The epoch index is omitted because the candidate set does not vary.
  • Regret bound: The regret bound depends on D(n, a∗), the Kullback-Leibler divergence between SeV n's and optimal SeV a∗'s bit-offloading delay distributions.The bound is stated in Lemma 2.
  • Reduction to UCB: With a fixed SeV set and identical input size, ALTO reduces to classical UCB, so the classical asymptotic bound on suboptimal selections applies.The resulting bound is substituted into the regret expression to bound RT.

APPENDIX E PROOF OF THEOREM 3

Theorem 3 is proved by separately bounding suboptimal selections and showing eventual selection of the optimal SeV for large inputs. Combining these lemmas yields the theorem.

  • Lemma 3: The proof first bounds the number of tasks offloaded to a suboptimal SeV under periodic inputs and fixed bit-offloading delays.This is formalized as Lemma 3.
  • Lemma 3: The Lemma 3 proof uses contradiction and the inequality ln τ > ln(τ − 1) to establish a selection result for SeV 2.The argument also treats the alternative input case x_t = 1 − ϵ1.
  • Lemma 4: For sufficiently large inputs, ALTO eventually always selects the optimal SeV 1.Lemma 4 states that there exists T1 such that a_t = 1 when t ≥ T1 and x_t = 1 − ϵ1.
  • Auxiliary bound: The proof constructs an auxiliary function f(t) and shows k2t,2 ≥ f(t) for every t ≥ t0.The contradiction argument establishes the inductive lower bound on selections.
  • Theorem 3: Combining Lemmas 3 and 4 with β0 = 2 derives Theorem 3.The theorem follows after bounding suboptimal selections and eventual optimal selection.
Loading 1901.05205v1…