# A Lyapunov-Optimized Dynamic Task Offloading Strategy for Satellite Edge Computing
## 4 Task Offload Optimization Algorithm
### Offloading Algorithm Based on The Hungarian Method  
It is evident that for the transformed optimization objective \(P2\), the offloading decisions for each time slot are sufficient to determine \(P2\) for that slot. Assuming that in cases where only a subset of the satellites in the constellation receives a new task at this time slot (\(M<N\)), a virtual task \(A_{i}(t)=\{0\}\) is assigned to the remaining satellites. Specifically, in a specific time slot, the offloading decision \(o(t)\) is defined as an \(N\times N\) matrix, which is shown as  
\[o=\begin{bmatrix}o_{1}^{1}&\cdots&o_{1}^{N}\\ \vdots&\ddots&\vdots\\ o_{N}^{1}&\cdots&o_{N}^{N}\end{bmatrix}. \tag{22}\]  
It is supposed to find a specific offloading strategy \(\pi\in S\) to minimize \(P2\), in which \(S\) is the set of all feasible solutions. Combined with constraints (1) (3) (4), the optimization problem \(P2\) can be defined as a classic assignment problem [24]. The Hungarian method is a widely adopted approach for solving this type of problem [24]. Referring to the offloading matrix \(o\), we define a cost matrix of the same size as  
\[L=\begin{bmatrix}L_{1}^{1}&\cdots&L_{1}^{N}\\ \vdots&\ddots&\vdots\\ L_{N}^{1}&\cdots&L_{N}^{N}\end{bmatrix}. \tag{23}\]  
\(L_{i}^{j}\in L,i,j\in\{1,2,\cdots,N\}\) represents the value of objective function if task \(A_{i}\) is offloaded to the \(j\)th satellite, which is calculated by \(L_{i}^{j}=Q_{j}(t)*\left(D_{j}(t)-C_{j}(t)*\tau\right)+V*(T_{j}(t)+\beta*E_{j} (t))\). The Hungarian method can solve the best matching that minimizes \(P2\), i.e., the optimal solution of the problem by certain transformation. The detailed steps are shown below  
1. For each row in the matrix \(L\), identify its minimum entry and subtract it from all entries in that row;
2. For all entries \(L_{i}^{j}\) equal to 0, mark them as starred zeros, provided that there are no existing starred zeros in the same row or column;
3. Cover each column that contains a starred zero. If all columns are covered, proceed to Step 7;
4. Repeat the following procedure until all zeros in the matrix are covered: Find an uncovered zero and prime it. If there are no starred zeros in the same row as the primed zero, proceed to Step 5. Otherwise, cover this row and uncover the column containing the starred zero;
5. Continue to construct a series of alternating primed and starred zeros until no additional uncovered zeros can be found. Then, proceed to Step 6;
6. Locate the smallest entry among all uncovered entries in the matrix. Subtract this entry from all uncovered entries, and add it to all entries that are covered twice. Return to Step 4;The algorithm terminates when all entries in the matrix are covered. The set of assignments corresponding to the starred zeros constitutes the optimal solution to the assignment problem.  
According to the obtained optimal solution, then the optimization objective \(P2\) can be solved. The optimal solution for \(P2\) across all time slots is computed, followed by obtaining the optimal solution for \(P1\). The procedure of the dynamic offloading algorithm that employs Lyapunov optimization and the Hungarian algorithm (DOALH) is shown in Algorithm 1.  
```
Input: System parameter \(Hop\), \(A(t),C(t),B,\leavevmode\
obreak\ \mathit{p}^{trans},\mathit{p}^{com},T\) Algorithm 1. Obtain the optimization objective function based on \(P1\);
2. Convert the objective function to \(P2\) utilizing Lyapunov optimization;
3. For \(t<T\): Using the Hungarian algorithm to determine the optimal offloading strategy in the specific time slot;
4. Counting the optimal solutions for all \(T\) time slots; Output: The minimum mean value of \(\mathit{Cost}\) in \(T\) time slots
```  
**Algorithm 1** The DOALH algorithm  
The complexity of the DOALH algorithm is \(T\mathcal{O}\big{(}N^{2}\big{)}\).