# Minimum-Cost Offloading for Collaborative Task Execution of MEC-Assisted Platooning
## 5 Optimal Offloading Decision for Collaborative Task Execution
### Dynamic Programming Algorithm  
In order to apply the Algorithm 1 to the optimal task offloading decision, we need to find the shortest path according to the task execution cost, execution time and aggregation cost. Specifically, we treat all tasks as a multistep process with chain structure, namely a multistep decision process. The state transition process for the optimal offloading decision of collaborative task execution is depicted in Figure 6. State 0 and state \(n+1\) represent the start and end of the whole application execution respectively. We denote \(r_{k}\) as the location identifier of the task \(k\). For instance, \(r_{k}=1\) indicates that the task \(k\) is executed on Vehicle 1 in the platoon. \(r_{k}\) keeps tracking the position of the application tasks, with 1 to \(m\) indicating the platoon members and 0 for the MEC server, as shown in the following  
\[r_{k}=\left\{ \begin{array}{cl}0,&\text{ MEC server;}\\ 1,&\text{ Vehicle 1;}\\ 2,&\text{ Vehicle 2;}\\ \ldots&\\ m,&\text{ Vehicle }m.\end{array} \right. \tag{17}\]Task \(n+1\) is the output result of the application. Since the output result needs to be sent back to the starting point after the completion of task \(n\), it can be obtained that \(r_{0}=m\) and \(r_{n+1}=m\). The output result of task \(n+1\) does not need to be calculated, and the user does not need to purchase the computing resource, so we have \(b_{n+1}^{m}\). \(s_{k}\) is the decision variable for state \(k\), indicating the choice of which vehicle the task \(k\) should be offloaded to, shown as follows  
\[s_{k}=\left\{ \begin{array}{ll}0,&\text{MEC server execution;}\\ 1,&\text{Vehicle 1 execution;}\\ 2,&\text{Vehicle 2 execution;}\\ \ldots&\\ m,&\text{Vehicle }m\text{ execution.}\end{array} \right. \tag{18}\]  
\(s_{0}\) is the task initiation decision and \(s_{n+1}\) denotes the last decision of the application, that is \(s_{0}=s_{n+1}=m\). The aim is to find an optimal offloading decision strategy set \(S^{*}=\{s_{0},\,s_{1},\ldots,\,s_{n+1}\}\). We next try to find the minimum cost, time delay, and aggregation cost in Figure 6, based on the established iterative equations, respectively. First, we denote \(G_{k-1}(r_{k-1})\) as the minimum cost from task \(k-1\) to task \(n+1\). \(G_{0}(r_{0})\) is the minimum cost for all tasks of the application, given \(G_{n+1}(r_{n+1})=0\). On this basis, we establish an iterative equation of the latter term with the minimum cost. Knowing \(G_{k}(r_{k})\) at state \(k\) for location \(r_{k}\), we obtain every decision at state \(k-1\) so that the cost from state \(k-1\) to state \(n+1\) is minimized. The backward iteration equation with minimum cost is represented by  
\[ \begin{split}& G_{k-1}(r_{k-1})=\min_{s_{k}}[b_{k}(r_{k-1},s_{k})+G_ {k}(r_{k})]\\ & G_{n+1}(r_{n+1})=0\end{split}  \tag{19}\]  
where \(b_{k}(r_{k-1},s_{k})\) refers to the cost to be paid for making the offloading decision \(s_{k}\) fter task \(k-1\) at position \(r_{k-1}\) is completed. Both \(G_{k}(r_{k})\) and \(b_{k}(r_{k-1},s_{k})\) are known. The latter one can be obtained using (6) and (8) when the task is offloaded, that is, \(b_{k}(r_{k-1},s_{k})=b_{k}^{y}\) and \(y=s_{k}\). The system state starts from the state \(n\), and the value of the \(G_{n}(r_{n})\) can be computed from the initial condition \(G_{n+1}(r_{n+1})\) given in the state \(n+1\). Repeat this process for numerical iteration, and we find the optimal objective function value, optimal decision, and optimal path for the entire multistep decision problem in reverse order. Second, let \(H_{k-1}(r_{k-1})\) denote the minimum completion time from task \(k-1\) to task \(n+1\). \(H_{0}(r_{0})\) is the minimum task completion time for all tasks of the application, given \(H_{n+1}(r_{n+1})=0\). Knowing \(H_{k}(r_{k})\) at state \(k\) for location \(r_{k}\), we obtain every decision at state \(k-1\) so that the time delay from state  
Figure 6: Task state transition process. \(k-1\) to state \(n+1\) is minimized.