# Resource Allocation Strategy for Satellite Edge Computing Based on Task Dependency
## 3 System Models and Problem Formulation
### Task Scheduling Model  
#### 3.3.1 Scheduling Model Based on Subtask Degree  
Because the task structure of various types of applications is different, there may be dependency constraints between each task, and the execution of such tasks is seriously affected by its predecessor tasks, so the dependencies between tasks need to be considered before scheduling subtasks. As shown in Figure 2, the numbers 1 to 6 represent the sequence number of the DAG's neutron task nodes, and the arrows between the nodes represent the dependencies between the subtasks. So the first DAG in Figure 2 has four task nodes, the second has six task nodes, and the third has two task node nodes. Different types of applications for user request processing have different requirements for completion time. Therefore, to improve the completion rate of the application within the system, it is necessary to establish a priority queue at the beginning. The queue is sorted according to the deadline delay of the application. In case two applications have the same deadline time, the one with the higher current DAG data volume is selected as the higher priority. The applications to be scheduled are divided into high priority and low priority according to the priority, and the high priority is executed on satellite edge nodes \(a_{ij}=1\). Low-priority ones are executed on the ground \(a_{ij}=0\). Tasks locally executed are prioritized because they can only process one task at a time, so subtasks with smaller deadlines are prioritized. Figure 2: Task dependency diagram. The TBID scheduling algorithm selects the computing task with an in-degree of 0 in each DAG and generates a set of tasks defined as L. Each time a group subtask is completed in the scheduling process, the task and associated edges will be removed from the DAG, and the structure of the DAG will be changed. The point with an in-degree of 0 will become a ready subtask at the next dispatch. The specific scheduling steps of the application program are described in Algorithm 1, and the specific steps to solve the task processing delay of the subtask set through the improved sparrow search algorithm in the scheduling process are described in the next section. The pseudo-code of the scheduling algorithm is as follows:  
```
Input: Applications for all users Output: The completion rate of the application
1.for\(i=1\) to \(m\)do
2. Compare the priorities of each application into a set of high- and low-priority tasks, with high priority executed at satellite edge nodes and low priority locally executed
3.while\(G_{i}\) is not null
4. Use the BFS algorithm to traverse the application's DAG
5.endwhile
6. Obtain the number of layers for each DAG \(SL_{i}\)
7.endfor
8.for\(i=1\) to \(m\)do
9.while\(G_{i}\) is not null
10. Traverse the application's DAG and look for nodes with an indegree of 0 to add to subtask set \(L\). 11. According to Algorithm 2, the resource allocation strategy \(F\) and \(B\) of subtask set L and the completion delay of subtask set tasks are obtained
12. Delete subtask nodes and task-related edges
13.endwhile
14. The application completion delay is calculated according to Equation (6)
15.endfor
16. Calculate the application completion rate according to Equation (7). ```  
**Algorithm 2** Satellite edge resource allocation method based on improved sparrow algorithm  
``` Inputs: subtask set, the proportion of producers, the proportion of investigators early warning value, the maximum number of iterations \(T\), population size Output: optimal resource allocation vectors \(F\), \(B\), subtask set completion delay
1. The TBID scheduling algorithm is used to obtain the subtask set \(L\). 2. According to Equation (12), opposition-based learning is used to initialize the population
3.for\(t=1\) to \(T\)do
4. Calculate the fitness value according to Equations (8)-(11) and find the optimal fit
5.for\(i=1\) to the number of producers do
6. Update the location of the sparrow finder according to Equation (13). 7.endfor
8.for\(i=\) number of producers +1 to population number do
9.