Latency-aware Batch Task Offloading for Vehicular Cloud: Maximizing Submodular Bandit

The concept and application of smart city brings us enormous computing resources, but it also brings considerable computing heterogeneity. In this paper, we propose a brand new scenario of batch task offloading for vehicular cloud which maximizes the performance of offloading strategy in case of satisfying the deadline restraints and reliability requirements. To capture the sources of the service delay better, we split the task offloading process into several components, and focus on the optimization of routing and task execution. We model our problem (Batch Task Offloading for Vehicle Cloud problem with reliability restraints) in a submodular function maximizing perspective and show its NP-hardness. We present a novel greedy algorithm for offline scenario and analyze its theoretical performance. We prove our algorithm is (1 - {1 e}) -approximate in polynomial time. Furthermore, we study the problem in the online scenario using bandit submodular set maximizing model. We present an algorithm with regret bound O (log^2\ T) running in a small amount of arms which can reduce the computing complexity and the number of selected arms under the same performance. We also evaluate our algorithm in a microscopic and continuous traffic simulation platform, SUMO. The result shows our algorithms (both online and offline) outperforms other existing algorithms over 20%.