## 4 Algorithm Design
### DMP-TA Algorithm
```
1 Define \(f:GT\to V:\forall GT,\exists!v_{i}\in V:f(GT)=v_{i}\);
2 Initialize \(p=1\), \(q=2\), \(k=1\);
3 for\(\forall tw_{p,j,kp}\in GTW_{p,j}\) and \(\forall tw_{q,j,kq}\in GTW_{q,j}\)do
4 if\((\exists S_{j}\in GS:\forall T_{pi}\in GT_{p},GTW_{pi,j}\
eq\varnothing)\)and \((\forall T_{pi}\in GT_{p},\exists S_{j}\in GS,tw_{p,q,j,k}\in GTW_{pq,j})\)then
5\(E_{p,q}=\{tw_{p,j,kp},tw_{q,j,kq}\}\);
6\(E\gets E\cup E_{p,q}\);
7\(k=k+1\);
8 while\(p<|GT|\)do
9 if\(q\leq|GT|\)then
10\(q=q+1\);
11 else
12\(p=p+1\);
13\(q=p+1\);
14
15 return\(G\)
```  
**Algorithm 2**Initial MSMTAG model construction algorithm  
In summary, the critical steps of the DMP-TA algorithm can be described as follows: starting from the initial task aggregation graph \(G\) constructed in Algorithm 1, the edge \(E_{p,q}\) with the maximum merge priority is selected in each round, and the two vertices \(v_{p}\) and \(v_{q}\) connected to this edge are merged to form a new aggregation task \(v_{C_{pq}}\), and the minimum energy required to execute the aggregation task \(v_{C_{pq}}\) is calculated and updated according to Algorithm 2. Next, the edges of vertices \(v_{p}\) and \(v_{q}\) and the edges connected to vertices \(v_{p}\) and \(v_{q}\) are deleted, and the edges of vertex \(v_{C_{pq}}\) and the edges connected to vertex \(v_{C_{pq}}\) are added, and the merging priority of the newly added edges is calculated, and the next round of computation is performed. The algorithm ends when the set of edges \(E\) in the aggregation graph \(G\) is empty, and the DMP-TA algorithm is described in Algorithm 3 as follows. ```
1 Sort \(GTW\) by end time to get \(TWL=\{tw_{x1,j,k1},\ldots\}\) for \(TL=\{T_{x1},\ldots\}\). Initialize \(b_{i},f_{i}\) for min energy start and end times for the first \(i\) tasks. if\((te_{x1}-\max\{ts_{x1},ts_{x2}\})\geq\max\{d_{x1},d_{x2}\}\)then
2\(f_{2}=te_{x1}\); \(b_{2}=te_{x1}-\max\{d_{x1},d_{x2}\}\);
3 else
4\(f_{2}=\max\{te_{x1},d_{x2}+ts_{x2}\}\); \(b_{2}=\min\{te_{x1}-d_{x1},ts_{x2}\}\);
5 for\(i=3\)to\(l\)do
6 if\((\min\{f_{i-1},te_{xi}\}-\max\{b_{i-1},t_{xi}\})\geq d_{xi}\)then
7\(f_{i}=f_{i-1}\); \(b_{i}=b_{i-1}\);
8
9 else
10\(f_{i}=ts_{xi}+d_{xi}\); \(b_{i}=b_{i-1}\);
11\(\delta_{C_{p}}=\frac{\Sigma\theta_{x1,j,k}}{l}\);
12\(ME_{p}=(f_{l}-b_{l})\times oe_{j}+2\frac{|\delta_{C_{p}}|}{\omega_{j}}\times se _{j}\). ```  
**Algorithm 2**Dynamic planning-based algorithm for minimum energy calculation for aggregated tasks  
The time complexity of the DMP-TA algorithm is \(O\big{(}n^{3}\big{)}\), where \(n\) is the number of meta-tasks. ```
1 Initialize MSMTAG Model
2 foreach\(v\in V\)do
3 Compute \(E_{\min}(v)\) ; // Minimum energy for executing the task at \(v\)\(AP(E_{i,j})=f_{\min}(v_{i})+f_{\min}(v_{j})-f_{\min}(v_{C_{i,j}})\);
4 while\(E\
eq\emptyset\)do
5\(E_{\max}=\arg\max AP(E_{i,j})\) ; // Select the edge with the highest AP. \(E\leftarrow(E\setminus E_{i,j})\cup\{E_{\max}\}\);
6\(v_{p}=\text{Merge}(v_{i},v_{j})\) ; // Merge vertices to a new vertex \(v_{p}\). Recompute \(E_{\min}(v_{p})\);
7 foreach\(v_{k}\in V\), \(v_{k}\to v_{p}\)do
8 ifConditions of Equation (2)and Equation (3) are satisfiedthen
9\(E\gets E\cup E_{k,p}\) ; // Update edges
10 Update \(AP(E_{k,p})\) ; // Recalculate AP for new edges
11 return\(G\)
```  
**Algorithm 3**DMP-TA Algorithm  
The time complexity of constructing the initial MSMTAG model is \(O\big{(}n^{2}\big{)}\) (Line 1). The time complexity of computing the minimum execution energy of the corresponding aggregated tasks for all vertices in the initial MSMTAG model \(G\) is \(O\big{(}n^{2}\big{)}\) (Lines 2-3). The task aggregation graph with \(n\) vertices has at most \(C_{n}^{2}\) edges, and it takes \(\frac{1}{2}\times n\times(n-1)\) calculations to compute the maximum merge priority of all edges, in that the time complexity of computing the edge with the maximum merge priority in the algorithm is \(O\big{(}n^{2}\big{)}\) (Line 4), and similarly, the time complexity of selecting the edge with the maximum merge priority is \(O\big{(}n^{2}\big{)}\) (Line 6).