# Resource Allocation Strategy for Satellite Edge Computing Based on Task Dependency
## 3 System Models and Problem Formulation
### Task Model
#### 3.2.2 Application Completion Rate Model  
The transmission delay of subtask offloading to the edge computing server can be expressed as:  
\[T_{i,j}^{us}\ =\ \frac{D_{i,j}}{R_{us}^{lj}} \tag{1}\]  
\(R_{us}^{i,j}\) represents the uplink transmission rate (unit: Mbps), \(R_{us}^{i,j}\) expressed as:  
\[R_{us}^{i,j}=B_{ij}\log_{2}(1+\frac{P_{i,j}\beta_{i,j}}{N}) \tag{2}\]  
The transmitted power of the subtask \(v_{i,j}\) is expressed as \(P_{i,j}\), the channel gain is expressed as \(g_{i,j}\), and the white Gaussian noise power is expressed as \(N\) and \(B_{i,j}\) is the allocated bandwidth resource in MHz. The processing delay of the subtask offloading to the MEC server is:  
\[T_{i,j}^{\rm sec}=\frac{C_{i,j}}{F_{i,j}} \tag{3}\]  
\(F_{i,j}\) represents the computing resources (in cycles/s) allocated to a task. The processing delay of a local computing task is composed of a processing delay and a waiting delay. Since tasks are locally processed one at a time, the waiting time for a task is the sum of the computing time of all tasks before the task \(v_{i,j}\) in the task set. The expression is:  
\[T_{i,j}^{l}=\frac{C_{i,j}}{F^{l}}+T_{i,j}^{l,w} \tag{4}\]  
\(F^{l}\) represents the local computing resources (unit: cycles/s), \(T_{i,j}^{l,w}\) represents the waiting time. According to Equations (1)-(4), the total delay in task completion is:  
\[T_{i,j}^{\rm\less}=(1-a_{i,j})T_{i,j}^{l}+a_{i,j}(T_{i,j}^{\rm sec}+T_{i,j}^{ us}+2\frac{\rm S}{v}) \tag{5}\]  
where \(a_{i,j}\) is the processing method of the task, the distance from the mobile device to the satellite node is expressed as \(s\), and the speed of light is expressed as \(v\). To satisfy the relationship between tasks, the scheduling algorithm should reasonably arrange the processing sequence of tasks, enabling suspended tasks to acquire as many resources as possible to expedite the processing time. Therefore, a scheduling processing scheme is set up: each DAG is processed according to the scheduling algorithm. Only when all tasks with an in-degree of 0 in the current task graph have been processed (all resources are completely released) can the next schedule start processing. \(EST_{i}\) represents the maximum completion delay of all predecessor tasks of the last task in the \(i\)th application. When the task output degree in the task graph is 0, \(T_{i,exit}^{s}\) represents the processing time of the last task, \(L\) is the set of tasks processed at the edge node for the current in-degree of 0, \(sl_{i}\) is the number of times the current execution scheduling algorithm processes the DAG graph, and \(SL_{i}\) is the maximum number of layers of the application DAG to be scheduled. Therefore, the completion time of the application can be expressed as:  
\[EST_{i}=\sum\limits_{s_{l}=1}^{SL_{i}-1}\max\limits_{j\in L}T_{i,j}^{s} \tag{6}\] \[T_{i}=EST_{i}+T_{exit}^{s}\]The constraint optimization model is established as follows:  
\[ \begin{split}&\max\lambda=\frac{\sum\limits_{i=1}^{\frac{n}{n}}I_{i}}{m} \\ & s.t.\ \ C1:I_{i}=\left\{\begin{array}{cc}1&T_{i}\ \leq T_{d}^{i}\\ 0&T_{i}>T_{d}^{i}\end{array}\right.\\ &\ C2:\sum\limits_{v_{ij}\in I}B_{ij}\leq B_{\max}\\ &\ C3:\sum\limits_{v_{ij}\in I}F_{ij}\leq F_{\max}\\ &\ C4:a_{ij}\in\{0,1\}\ i\in M_{s}j\in N,\end{split}  \tag{7}\]  
\(m\) is the total number of applications that need to be processed. From Equation (6), we calculate \(T_{i}\). When application \(i\) is completed within the limited delay and returns the result, \(T_{i}\leq T_{d}^{i}\), \(I_{i}=1\) indicates that the application was successfully processed, otherwise it is 0; where \(A\), \(F\), and \(B\) represent the uninstall policy and the resource allocation strategy. \(A\) is the set of subtask offloading policies, \(A=\left\{a_{i,j}\right\}i\in M,j\in N\). \(F\) is the set of computing resource allocation policies \(F=\left\{F_{i,j}\right\}\) and \(F_{\max}\) is the computing resources that can be allocated to subtasks.