# Adaptive Computation Offloading with Task Scheduling Minimizing Reallocation in VANETs
## 6 Performance Evaluation  
Using the Veins network simulator [6], we compared the performances of VAO, HEFT, and Max-Min in terms of schedule length, reallocation probability, and data transfer time. Actually, since neither HEFT nor Max-Min include a way to reallocate tasks, the VIRQ/VIRP process of VAO was adopted for the HEFT and Max-Min task reallocation. So, the message overheads of the three methods are naturally the same. In VAO, \(\alpha\) was set to 3 empirically, or only neighbor vehicles whose routes overlap the route of the RV for more than 3 blocks were selected as candidate SVs. When \(\alpha\) was greater than 3, performance dropped because of the scarce number of candidate SVs. When \(\alpha\) was smaller than 3, the chance of task reallocation rarely decreased, as compared with HEFT. We first compared the schedule length by each algorithm and observed the effects of data transfer time and the number of SVs on the overall performance. Then, the reallocation probability of each algorithm is investigated. Finally, the effect of the depth of width of a DAG on performance is studied. Figure 3 shows the DAG representation of an offloaded application used for the simulation, with both depth and width of 4. The depth and width mean the total number of levels in a DAG and the maximum number of nodes in one level, respectively. The road structure is shown in Figure 4. A total of 100-300 vehicles, which is proportional to the simulation time, with a maximum speed of 30 km/h were randomly deployed on the roads. Each of them followed one of 30 routes that were randomly generated, and its processing power followed uniform distribution between 200 and 600 MIPS. Figure 5 compares the average schedule length over 1000 simulations for an application that can be represented by a DAG with both depth and width of 4. As mentioned in Section 3, the schedule length by HEFT was 15.3% shorter than Max-Min, since HEFT makes the schedule considering relationships between tasks of an application, which is represented in a DAG. On the other hand, VAO created schedules 11.7% longer than HEFT, although VAO also utilizes a DAG. This is because VAO filters out some searched vehicles from the set of candidate SVs, based on how long their routes overlap the route of the RV. The smaller the number of candidate SVs, the smaller the number of tasks that can be executed in parallel. Furthermore, if some vehicles with high computing power are excluded from the candidate SVs' set, the total computing capability of the offloading system would be degraded. More experiments were needed to better understand these results. Figure 3: An example of DAG of depth 4, width 4. We performed additional simulations 1000 times with various densities of vehicles so that the number of searched vehicles could be different. Figure 5(a) depicts the schedule length against the number of searched vehicles \(|\mathbf{V}|\). When \(|\mathbf{V}|\) was 0, tasks could not be offloaded (no CO happened); and when \(|\mathbf{V}|\) became 1, the schedule lengths of HEFT and Max-Min decreased by 39.4%. As \(|\mathbf{V}|\) increased, the schedule length typically decreased, but after \(|\mathbf{V}|\) was greater than 4, the schedule lengths by HEFT and Max-Min were stable around 41.7% and 49.1% of the no CO case. This is because the width of the DAG for our application was 4. Since up to four tasks can be executed simultaneously in a level, many more vehicles than 4 are not much help to improve parallel computing efficiency. However, in the case of VAO, about twice as many searched vehicles were needed to stabilize the performance because some of the searched vehicles were excluded from the candidate SVs' set, due to their different routes from the RV's route. Figure 5(b) shows the schedule length when the number of searched vehicles \(|\mathbf{V}|\) is sufficient. When \(|\mathbf{V}|\) is large enough, the schedule lengths by HEFT and Max-Min do not change much. On the other hand, the schedule length by VAO continuously decreases as \(|\mathbf{V}|\) increases.