# 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
\begin{table}
\begin{tabular}{l l} \hline \hline
**The Improved Sparrow Search Algorithm** & **Mapping Relationships** \\ \hline Individual vectors & Resource allocation results \\ Individual weight & The result of resource allocation for each subtask \\ Fitness function & Subtask completion delay \\ Population & Different collections of resource allocation policies \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Mapping between algorithms and optimization problems. The OBL strategy calculates the opposite solution of the current solution, finally selects a better fitness solution from the current solution and the corresponding opposite solution, and updates the individual. The opposition-based learning strategy is widely used by scholars in various algorithms. The literature [28] indicates that the opposition-based learning strategy can be used to generate reverse solutions in the search space to increase the diversity of the population. Therefore, the opposition-based learning strategy is introduced when the sparrow population is initialized to expand the search space of the sparrow to maintain population diversity and enhance the global search ability. The initialization is as follows:

\[X_{i,j}^{*}=ub_{i,j}+lb_{i,j}-X_{i,j} \tag{12}\]

where \(ub_{i,j}\) is the upper bound of the search space, \(lb_{i,j}\) is the lower bound of the search space. After the randomly generated original sparrow population and opposite sparrow population are merged into a new population, the fitness function of the new population is calculated. (2) Producer location updates combined with whale-optimized random search strategies. In the sparrow search algorithm, global exploration is mainly undertaken by the producer. When the food searched by the producer is located in the local optimal, a large number of scroungers will pour into the location, resulting in the loss of population position diversity and the local optimum, and at the same time, the overall search performance deteriorates, affecting the optimization effect. So, the producer position is fused with the random search location update mechanism in the whale optimization algorithm to improve the global search ability of the algorithm. The producer position is updated to:

\[X_{i,j}^{t+1}=\left\{ \begin{array}{l}X_{rand}^{t}-A\cdot\left|C\cdot X_{rand} ^{t}-X_{i,j}^{t}\right|\ \ R_{2}<ST\\ X_{i,j}^{t}+Q\cdot L\ \ \ \ \ \ \ \ R_{2}\geq ST\end{array} \right. \tag{13}\]

\(t\) represents the number of current iterations, where \(A\) and \(C\) are vectors of coefficients, \(A=2 ar_{1}-a\), \(C=2r_{2},a=2-2t/T\). \(r_{1}\) and \(r_{2}\) is the random number in (0, 1), \(a\) is the convergence factor that linearly decreases from 2 to 0, and \(T\) is the maximum number of iterations. \(X_{i,j}^{t}\) is the position information of the \(i\)th sparrow in the \(j\)-dimension. \(R_{2}<ST\) indicates that there are no predators around, and the producer can conduct a large-scale search. When a scout finds a predator and immediately sends an alarm signal. \(R_{2}\geq ST\), \(R_{2}(R_{2}\in[0,1])\) represents the early warning value, and \(ST(ST\in[0.5,1])\) represents the safety value. \(Q\) is a random number that follows a normal distribution, and \(L\) represents a matrix representing \(1\times d\) with all 1 elements. Scroungers location update as:

\[X_{i,j}^{t+1}=\left\{ \begin{array}{l}Q\cdot\exp(\frac{X_{rand}^{t}-X_{i,j}^ {t}}{i^{2}})\ \ if\ \ \ i>\frac{n}{2}\\ X_{p}^{t+1}+\left|X_{i,j}^{t}-X_{p}^{t+1}\right|\cdot A^{+}\cdot L\ if\ \ \ i\leq\frac{n}{2}\end{array} \right. \tag{14}\]

\(X_{p}\) is the optimal position occupied by the current discoverer, and \(X_{worst}\) represents the current global worst position. \(A\) represents a matrix, where each element is randomly assigned a value of 1 or \(-1\), and \(A^{+}=A^{\top}\big{(}AA^{\top}\big{)}^{-1}\). When \(i>n/2\), it indicates the \(i\)th scroungers with a lower fitness value have not received food, are in a very hungry state, and need to fly elsewhere to feed to obtain more energy.