# Research on Multi-DAG Satellite Network Task Scheduling Algorithm Based on Cache-Composite Priority
## 3 System Model
### Cost Model  
Assuming that multiple users on the ground initiate different service requests, these service requests are represented as \(a=\{application_{1},application_{2},\ldots,application_{n}\}\), where \(n\) represents the number of requests. Thus, the set of service request identifiers can be represented as \(N=\{1,2,\ldots,n\}\). As the tasks in the service requests are too large, they need to be divided into multiple subtasks. The relationship between subtasks is represented by a directed acyclic graph (DAG). An example DAG is illustrated in Figure 3. The DAG is represented by the binary tuple \(G=(V,E)\), where \(V=\{v_{1},v_{2},\ldots,v_{s}\}\) represents the subtask node set of the DAG, \(s=|V|\) represents the total number of subtasks, \(E=\{e_{i,j}\mid e_{i,j}=<v_{i},v_{j}>,e_{i,j}\in V\times V\}\) represents the directed edges of the DAG, and each edge connects two different subtasks at its two ends. If \(e_{i,j}\in E\), it means that there is a dependency between subtask \(v_{i}\) and subtask \(v_{j}\), whereby subtask \(v_{j}\) can only be executed after the successful completion of subtask \(v_{i}\). Let \(P=\{p_{1},p_{2},\ldots,p_{m}\}\) represent the set of edge computing nodes, where \(m=|P|\) denotes the number of edge computing nodes. We use \(w_{i,j}\) to represent the calculation delay of subtask \(v_{i}\) on the edge computing node \(p_{j}\). \(w_{i,j}\) can be expressed as  
\[w_{i,j}=\frac{L_{i}}{h_{j}} \tag{1}\]  
where \(L_{i}\) is the calculation amount of the subtask \(v_{i}\), represented by million instructions (MI), and \(h_{j}\) is the processing power of the current edge computing node \(p_{j}\), represented by million instructions per second (MIPS). Then, the energy consumption \(\Theta_{i,j}\) of this execution can be expressed as  
\[\Theta_{i,j}=w_{i,j}\times P_{j}^{work} \tag{2}\]  
where \(P_{j}^{work}\) represents the power of the edge computing node \(p_{j}\) in operation. Therefore, we define the matrix \(W=[w_{i,j}]_{s\times m}\) as the computation latency of the subtask set on all edge computing nodes. Similarly, the matrix \(J=[\Theta_{i,j}]_{s\times m}\) is defined as the energy consumption of the task set on all edge computing nodes. Figure 3: DAG example diagram (s = 10). \[W= \begin{bmatrix}w_{11}&w_{12}&\cdots&w_{1m}\\ w_{21}&w_{22}&\cdots&w_{2m}\\ \vdots&\vdots&\ddots&\vdots\\ w_{s1}&w_{s2}&\cdots&w_{sm}\end{bmatrix}  \tag{3}\]  
\[J= \begin{bmatrix}\Theta_{11}&\Theta_{12}&\cdots&\Theta_{1m}\\ \Theta_{21}&\Theta_{22}&\cdots&\Theta_{2m}\\ \vdots&\vdots&\ddots&\vdots\\ \Theta_{s1}&\Theta_{s2}&\cdots&\Theta_{sm}\end{bmatrix}  \tag{4}\]  
Assuming that in a satellite network, the communication speed between any two edge computing nodes is the same, we can use the transmission cost between two nodes as the communication cost. Each edge in the DAG corresponds to a communication cost. Let \(C=\{c_{i,j}\mid e_{i,j}\in E,c_{i,j}>0\}\) represent the set of communication costs for the entire DAG, where \(e_{i,j}\) represents the directed edge from subtask \(v_{i}\) to its successor subtask \(v_{j}\), and \(c_{i,j}\) is the weight of \(e_{i,j}\). The communication cost can be expressed as  
\[c_{i,j}=t_{i,j}\times P_{pass} \tag{5}\]  
where \(t_{i,j}\) represents the communication latency between edge computing nodes \(i\) and \(j\), and \(P_{pass}\) represents the transmission power between satellites. Adopting the concept of upward rank values proposed by the classical HEFT algorithm, sorting the subtask priorities \(rank_{k}(v_{i})\) for each DAG, \(rank_{k}(v_{i})\) can be expressed as  
\[rank_{k}(v_{i})=\alpha\;\overline{w}_{i}+\beta\;\overline{\Theta}_{i}+\max(c_ {i,j}+rank_{k}(v_{j})) \tag{6}\]  
where \(\overline{w}_{i}\) represents the average execution time of the subtask \(v_{i}\) on different edge computing nodes, and \(\overline{\Theta}_{i}\) represents the average energy consumption of the subtask \(v_{i}\) on different edge computing nodes.