Multi-Task Offloading over Vehicular Clouds under Graph-based Representation

Vehicular cloud computing has emerged as a promising paradigm for fulfilling user requirements in computation-intensive tasks in modern driving environments. In this paper, a novel framework of multi-task offloading over vehicular clouds (VCs) is introduced where tasks and VCs along with their internal connections are modeled as undirected weighted graphs. Aiming to achieve a trade-off between minimizing task completion time and data exchange costs, task components are efficiently mapped to available virtual machines in the related VCs. The problem is formulated as a non-linear integer programming problem, mainly under constraints of limited contact between vehicles as well as available resources, and addressed considering different problem sizes. In small size scenarios with a couple of tasks and service providers in a VC, we determine optimal solutions; in larger size cases, a connection-restricted random-matching-based subgraph isomorphism algorithm is proposed that presents low computational complexity. Evaluation of the proposed algorithms against greedy-based baseline methods is conducted via extensive simulations.