# Adaptive Computation Offloading with Task Scheduling Minimizing Reallocation in VANETs
## 4 Problem Formulation  
As mentioned earlier, the optimal task allocation problem is NP-hard. However, we can get a near-optimal solution using linear programming.  
First, the allocation of \(t_{i}\) is denoted by a binary variable \(x_{ij}\) which is set to 1 when \(t_{i}\) is allocated to vehicle \(v_{j}\), and otherwise, 0:  
\[x_{ij}=\left\{\begin{array}{ll}1&\mbox{if $t_{i}$ is allocated to $v_{j}$}\\ 0&\mbox{otherwise}\end{array}\right. \tag{4}\]  
A task schedule \(\chi\) is represented by a matrix consisting of \(x_{ij}\)/s\({}^{\prime}\):  
\[\chi=\left[\begin{array}{ccc}x_{11}&\cdots&x_{1n_{v}}\\ \vdots&\ddots&\vdots\\ x_{n_{t}1}&\cdots&x_{n_{t}n_{v}}\end{array}\right] \tag{5}\]  
where \(n_{v}\) is the number of SVs and \(n_{t}\) is the number of tasks.  
For the sake of simplicity, we assume that a vehicle executes only one task at a time and that a task cannot be allocated to more than one vehicle simultaneously. In order to guarantee a task being allocated to only one vehicle, the following condition must be satisfied:  
\[x_{i1}+x_{i2}+\ldots+x_{in_{v}}=1,\;\forall i\in\{1,\;2,\ldots,n_{t}\} \tag{6}\]  
A task without any predecessor is called an entry task, and a task without any successor is called an exit task. Only the applications with one entry task are considered in this paper.  
For executing task \(t_{i}\) on an SV \(v_{j}\), all of its predecessors must be finished beforehand, and the results from the predecessors must be received by \(v_{j}\). Therefore, \(ST(t_{i})\), the start time of \(t_{i}\), must satisfy the following condition:  
\[ST(t_{i})>\underset{t_{m}\in\mathit{pred}(t_{i})}{max}(AFT(t_{m})+c_{mi}) \tag{7}\]  
where \(\mathit{pred}(t_{i})\) is the set of the immediate predecessors of \(t_{i}\) and \(c_{mi}\) is the data transfer cost from \(t_{m}\) to \(t_{i}\). Furthermore, because an SV is assumed not to execute more than one task at the same time, \(ST(t_{i})\) must satisfy the following condition:  
\[ST(t_{i})\textless ST(t_{k})\;\mathit{or}\;ST(t_{i})>AFT(t_{k}),\;\;t_{k}\in alloc (j) \tag{8}\]  
Figure 1: An example of task scheduling: (**a**) DAG representation of the application to be offloaded; (**b**) The Gantt chart of task executions offloaded by the Max-Min; (**c**) The Gantt chart of task executions offloaded by the HEFT.  
where \(AFT(t_{k})=ST(t_{k})+E_{kj}\) and \(alloc(j)\) is the set of tasks allocated (or offloaded) to \(v_{j}\). The value \(E_{kj}\) is the execution time of \(t_{k}\) on \(v_{j}\) and can be computed as \(E_{kj}=O(k)ipb(k)/mips(j)\) where \(O(k)\) is the data size of \(t_{k}\), \(ipb(k)\) is the number of instructions needed to process \(1\) byte of data in \(t_{k}\), and \(mips(j)\) is the computing power of processor \(j\) expressed in MIPS.  
Assuming that there is no task reallocation, the objective function is:  
\[\begin{split} minimize\underset{t_{i}\in T}{max}\{AFT(t_{i})\}\\ \text{s.t.}\;(4)\,\sim(8)\end{split} \tag{9}\]  
However, a fast-moving SV can be out of the communication range of the RV easily, so unfinished tasks that had been allocated to the SV have to be reallocated to other vehicles. If the set of the tasks that should be reallocated is \(RT\), the objective function is:  
\[\begin{split} minimize\underset{t_{i}\in RT}{max}\{AFT(t_{i})\}\\ \text{s.t.}\;(4)\,\sim(8)\end{split} \tag{10}\]  
In the dynamic vehicular environment, the vehicles in the coverage area of a vehicle tend to change frequently. After offloading tasks to SVs, the RV has to continuously track the SVs for possible task reallocation events.