# Adaptive Computation Offloading with Task Scheduling Minimizing Reallocation in VANETs
## 2 Related Works
### Task Scheduling  
Task scheduling is one of the major factors affecting the performance of CO because the length of the schedule determines the total completion time of all tasks. Then, to the best of our knowledge, there have been no task scheduling methods that consider the precedence relationships between tasks in a dynamic topology like VANET. Thus, we introduce two methods, HEFT [7] and Max-Min [8], instead, which are used in a static environment like parallel processing servers. First, HEFT is a representative scheduling algorithm that considers the relationship between tasks in the form of a DAG, but it is basically for the multi-processor computing environment with very low communication cost between static processors. In HEFT, the earliest finish time (EFT) of each task, when it is executed on every processor, is calculated. For instance, regarding EFT (\(t_{i}\), \(p_{j}\)), the EFT of task \(t_{i}\) on processor \(p_{j}\), is computed as:  
\[EFT\big{(}t_{i},p_{j}\big{)}=w_{ij}+max\bigg{\{}avail[j],\max_{m\in pred(t_{i} )}(AFT(t_{m})+c_{mi})\bigg{\}} \tag{1}\]  
where \(w_{ij}\) is the expected execution time of the task \(t_{i}\) on processor \(p_{j}\); \(avail[j]\) is the earliest time when \(p_{j}\) is ready to execute \(t_{i}\); \(pred(t_{i})\) is the set of predecessor tasks of \(t_{i}\); \(AFT(t_{m})\) is the actual finish time (AFT) of \(t_{m}\); and \(c_{mi}\) is the data transfer cost from \(t_{m}\) to \(t_{i}\). The schedule length is defined as the largest one among AFTs of all tasks:  
\[schedule\ length=max_{\forall i}\big{\{}AFT(t_{i})\big{\}} \tag{2}\]  
HEFT schedules a set of tasks, \(\mathbf{T}\), in a DAG \(\mathbf{D}\) on a given set of heterogeneous processors \(\mathbf{P}\). HEFT computes the average processing cost \(\overline{w}_{i}\) of a task \(t_{i}\) and the average communication cost \(\overline{c}_{ij}\) between tasks \(t_{i}\) and \(t_{j}\) in the given DAG. Then, it calculates the upward ranks of every task in \(\mathbf{D}\) reversely from an exit task \(t_{exit}\). The upward rank \(rank_{u}(t_{i})\) is the total cost from task \(t_{i}\) to the exit task, defined as:  
\[rank_{u}(t_{i})=\overline{w}_{i}+\max_{t_{h}\in isu(t_{i})}(\overline{c}_{ih}+ rank_{u}(t_{h})) \tag{3}\]  
where \(isu(t_{i})\) is the set of the immediate successors of \(t_{i}\). HEFT sorts the tasks in \(\mathbf{T}\) in non-increasing order by \(rank_{u}\) into the sorted list \(\mathbf{T^{\prime}}\). Then, it gets the first task (i.e., the task with the highest rank) \(t_{i}\) in \(\mathbf{T^{\prime}}\) and allocates the task to the minimum EFT processor (i.e., the processor that can finish the task the fastest) using insertion-based scheduling. The insertion-based scheduling inserts \(t_{i}\) to the first time slot of \(p_{k}\) where the task can be executed. Finally, \(t_{i}\) is allocated to the minimum EFT processor \(p_{min}\). Another well-known scheduling method, Max-Min [8], is very simple, considering only the computation power of processors. Max-Min calculates the estimated finish time \(K_{ij}\) of a task \(t_{i}\) on a processor \(p_{j}\) for every task and every processor. Then, Max-Min allocates the task with the largest \(K_{ij}\) to the processor that can execute it the fastest. This allocation is repeated until every task is scheduled. Several recent works [23; 24] utilize duplication-based DAG scheduling. The Task Duplication-based Clustering Algorithm (TDCA) [23] improved performance by accurate parameter definition, enhanced clustering, and by considering the chain reaction. On the other hand, Lachesis [24], which is a task duplication-based learning algorithm, uses a convolutional network to parse a DAG and uses a heuristic search algorithm to allocate selected tasks to selected nodes. Although duplication-based scheduling is effective in reducing the schedule length, by maximizing computing resource usage, it cannot work on resource-constraint devices, such as mobile phones and vehicles, since it has to make copies of tasks to idle processors.