# Adaptive Computation Offloading with Task Scheduling Minimizing Reallocation in VANETs
## 1 Introduction  
As artificial intelligence (AI) has attracted much attention, many recent applications in vehicular ad-hoc networks (VANETs) also contain AI algorithms with resource-intensive computational tasks. However, all vehicles may not have enough computing resources to run those computationally intensive tasks, so computation offloading (CO) [1] has been investigated as a promising technique to overcome this resource limitation. Historically, CO was proposed to lighten the computation overhead of resource-constrained devices by transferring computational tasks to resource-abundant servers like a cloud. However, since cloud servers are usually located in remote areas, long data transfer time hindered CO from being widely adopted in VANETs. The security concern along the long path from a requesting vehicle to a cloud server could also be another problem. This is why edge computing [2] and fog computing [3] were suggested, which perform computation at edge or fog servers near requesting vehicles. However, edge or fog servers are in fixed locations, while vehicles move fast, so vehicles might leave the communication range of edge servers even before computation at the edge servers is complete. As a result, requesting vehicles should often receive computation results through multi-hop communication via road side units (RSUs), not directly from the edge servers. This multi-hop communication latency, although it is not as much as the latency from cloud servers, may be intolerable for recent time-sensitive applications, such as autonomous driving. Therefore, this paper focuses only on offloading to nearby vehicles, instead of to fixed remote servers. CO to nearby vehicles has several advantages as compared with CO to edge servers. First, the distance to other vehicles is usually shorter than the distance toedge servers, which can reduce the bit error rate (BER) during the transmission. Second, the number of neighbor vehicles is usually greater than the number of neighbor edge servers, so more tasks can be offloaded at one time, leveraging the advantage of parallel processing. However, there are two important issues to be solved in CO to other vehicles: (i) efficient task scheduling and adaptive allocation to service vehicles, (ii) reallocation of the tasks interrupted by topology changes. In CO to cloud or edge servers, all computational works are statically assigned to several servers. On the other hand, there can be many candidate vehicles that can provide services in CO to other vehicles, so tasks should be efficiently scheduled and adaptively distributed to them. Actually, task scheduling has a huge impact on the overall performance of CO, but finding the optimal schedule is a well-known NP-hard problem [4; 5]. Thus, heuristic scheduling methods should be designed. When designing a task scheduling method, we must first consider the relationship between tasks. For example, if task B needs the results of task A, the two tasks should be assigned so that task A can be completed before task B. However, the precedence relationship between tasks may not be so explicit. Assuming that there is task C that needs the result of task B above, task C should also be executed after task A finishes. This kind of precedent and descendent relationship may not be seen at first glance. We adopt a directed acyclic graph (DAG) to clearly show the precedence relationship between tasks. In a DAG, nodes represent task computation cost and edges represent the precedence relationship between tasks, as well as the data transfer cost. After constructing a DAG with tasks belonging to one application, a CO requesting vehicle (RV) assigns each task to a nearby vehicle, so that it may be completed before the required finish time. Then the actual finish time depends on the computing power of the CO service vehicles (SVs), so the information on the neighbors should be collected before the task allocation. Here, our proposed method, _vehicular adaptive offloading_ (VAO), is used.