# Adaptive Computation Offloading with Task Scheduling Minimizing Reallocation in VANETs
## 3 System Model  
Offloading tasks to clouds or other devices allows mobile devices to overcome the limitation on computation resources. However, offloading to the remote cloud is not suitable for real-time applications because of inevitable long latency. Even in the case of edge/fog computing, a fast-moving vehicle can easily go far from the edge/fog server in a short time, resulting in increased latency. According to current vehicular technology trends, we may expect that vehicles are to be equipped with computational resources, such as CPU, memory, and communication capabilities, and will be able to execute applications using their computational resources managed by virtual machine techniques [25; 26]. In this environment, a vehicle can request other vehicles to handle its tasks. In modern computer systems, various types of high-performance computing processors, like CPU, graphics processing unit (GPU), neural processing unit (NPU), field programmable gate array (FPGA) utilizing CUDA [27] or OpenCL [28] can be used to process codes. In this paper, regardless of the types of processors, we model the computing power of a vehicle in MIPS (million instructions per second) units.  
Vehicles in a VANET communicate with each other via V2V communications, such as DSRC and cellular vehicle-to-everything (C-V2X). After searching for nearby vehicles, an RV requests SVs to execute its tasks. A set of SVs, \(V^{s}\),is a subset of the set of searched vehicles \(V\) (\(V^{s}\in V\)). Assuming that there is no conflict and fading on wireless channels between vehicles, we consider only the amount of data that should be transferred on each channel. Then, the communication overhead on wireless is usually larger than the wired channel, so the transfer cost should be complemented by reducing the processing cost with the optimized task schedule.  
Figure 1 compares the efficiency of the task schedules made by HEFT and Max-Min. Suppose that an application consists of five tasks and their precedence relationships can be represented in a DAG as in Figure 1a. In this graph, nodes and edges correspond to tasks and the dependency between two tasks, respectively. If a task \(t_{i}\) in a DAG needs the result of another task \(t_{k}\), \(t_{k}\) must be finished before the execution of \(t_{i}\). In this case, \(t_{k}\) is the predecessor of \(t_{i}\) and \(t_{i}\) is the successor of \(t_{k}\). An edge of a DAG points from a predecessor to a successor.  
Figure 1b,c are the Gantt charts of task executions by Max-Min and HEFT. Here, \(v_{1}\) is an RV and the other two vehicles are SVs; and the computation powers of \(v_{1}\), \(v_{2}\), and \(v_{3}\) are 100, 150, and 200 MIPS, respectively. Max-Min and HEFT in \(v_{1}\) allocate tasks according to their algorithms. As you can see, HEFT made a shorter schedule length than Max-Min by overlapping data transfer time with execution time on SVs. In our experiment, the schedule length of HEFT was shorter than that of Max-Min by 15.3% on average. This is because HEFT computes the explicit rank of each task, in other words, the order of executing each task, in an upward direction from an exit task based on a DAG, while Max-Min does not use a DAG. Therefore, we also adopt the DAG for the proposed method.  
Figure 1: \(Cont.\)In this example, the task allocation is decided offline before actual execution, since HEFT and Max-Min were designed for static environments, such as parallel processing servers. However, in VANET, task reallocation must be handled frequently, since the associated SVs may leave the communication range of the RV without returning the computation result.