Distributed Scheduling for Time-Critical Tasks in a Two-layer Vehicular Fog Computing Architecture

With the rapid development of vehicular applications and mobile devices, demands for resources to process time-critical and computation-intensive tasks are increasingly prominent. In this paper, we propose a two-layer Vehicular Fog Computing (VFC) architecture, including the client layer and the fog layer. Vehicles may generate tasks as clients, which are further assigned to the nodes in the fog layer for processing. The fog layer aggregates available resources of vehicles and infrastructures by exploiting their communication, computation and storage capabilities. Each task requires certain amount of resources for processing at the fog nodes. We formulate a distributed task allocation (DTA) problem, which takes deadline, vehicle mobility and fog capacity into consideration, and aims at maximizing the overall resource utilization of system, via the cooperation of vehicles and fog nodes. We linearize DTA into a 0-1 integer linear programming (ILP) problem to obtain the optimal solution. Further, we design a heuristic algorithm to obtain near-optimal performance with low computational overhead, which decomposes DTA into two subprocess and schedules tasks in each fog node independently. Finally, we build the simulation model and conduct a series of experiments based on real-world vehicle trajectories, which demonstrate the effectiveness and scalability of the proposed algorithm.