# A Lyapunov-Optimized Dynamic Task Offloading Strategy for Satellite Edge Computing
## 4 Task Offload Optimization Algorithm  
### Problem Conversion  
Long-term constraints and optimization objectives pose significant challenges to solving the optimization problem \(P1\), primarily because obtaining task information for future time slots is challenging. \(P1\) can be characterized as a Markov decision process (MDP), which conventional MDP methods such as reinforcement learning can potentially address. However, the general MDP algorithm is highly complex, rendering it unsuitable for real-time communication requirements. Furthermore, the MDP algorithm requires storing the optimal action for each state, which can significantly occupy satellite storage space. The Lyapunov optimization method is a promising online optimization approach that does not require a priori knowledge of statistical and future data [19]. One such approach is the Lyapunov-optimized dynamic task offloading strategy, which has been proposed by [PERSON] et al. in their paper [20]. This approach optimizes the task offloading decision based on the Lyapunov optimization technique, which can effectively balance the trade-off between system stability and task completion time. Other recent studies in the field of mobile edge computing include the joint task offloading and resource allocation approach proposed by [PERSON] et al. [21]. The Lyapunov method can convert the optimization of long-term objectives into solving the minimal value for each time slot, based on theoretical principles. First, we define the virtual task queues vector in the satellite constellation as  
\[\theta(t)\triangleq[Q_{1}(t),Q_{2}(t),\cdots,Q_{N}(t)]. \tag{15}\]  
The Lyapunov function can be expressed as  
\[L(\theta(t))\triangleq\frac{1}{2}\sum_{k=1}^{N}Q_{k}(t)^{2}. \tag{16}\]  
The Lyapunov drift is defined as  
\[\Delta(\theta(t))=L(\theta(t+1))-L(\theta(t)), \tag{17}\]  
which shows the variation in the system queue between two time slots. Analyze the \(\Delta(\theta(t))\) as  
\[ \begin{array}{ll}\Delta(\theta(t))&=L(\theta(t+1))-L(\theta(t))\\ &=\frac{1}{2}\sum_{k=1}^{N}Q_{k}(t+1)^{2}-\frac{1}{2}\sum_{k=1}^{N}Q_{k}(t)^ {2}\\ &\leq\frac{1}{2}\Big{(}\sum_{k=1}^{N}(Q_{k}(t)-C_{k}(t)*\tau+D_{k}(t))^{2}- \sum_{k=1}^{N}Q_{k}(t)^{2}\Big{)}\\ &=\frac{1}{2}\Big{(}\sum_{k=1}^{N}Q_{k}(t)^{2}+2*\sum_{k=1}^{N}Q_{k}(t)*(D_{k }(t)-C_{k}(t)*\tau)+\sum_{k=1}^{N}((D_{k}(t)-C_{k}(t)*\tau)^{2}-\sum_{k=1}^{N} Q_{k}(t)^{2}\Big{)}\\ &=\sum_{k=1}^{N}Q_{k}(t)*(D_{k}(t)-C_{k}(t)*\tau)+\frac{1}{2}\sum_{k=1}^{N}(( D_{k}(t)-C_{k}(t)*\tau)^{2}\\ &\leq\sum_{k=1}^{N}Q_{k}(t)*(D_{k}(t)-C_{k}(t)*\tau)+\frac{1}{2}\sum_{k=1}^{N} D_{k}(t)^{2}+(C_{k}(t)*\tau)^{2}\\ &\leq\delta+\sum_{k=1}^{N}Q_{k}(t)*(D_{k}(t)-C_{k}(t)*\tau)\end{array}  \tag{18}\]  
As \(D_{k}(t)\) conforms to a random distribution with upper bound \(\lambda_{max}\) and \(C_{k}(t)\) is the satellite CPU's computing capacity, \(\frac{1}{2}\sum_{k=1}^{N}D_{k}(t)^{2}+(C_{k}(t)*\tau)^{2}\) must have an exact max value \(\delta\) at time slot \(t\). Furthermore, we add up the \(\sum_{k=1}^{N}(T_{k}(t)+\beta*E_{k}(t))\) of each time slot to obtain  
\[\Delta(\theta(t))+\,\mathrm{V}\sum_{k=1}^{N}(T_{k}(t)+\beta*E_{k}(t))\leq \delta+\sum_{k=1}^{N}Q_{k}(t)*(D_{k}(t)-C_{k}(t)*\tau)+V\sum_{k=1}^{N}(T_{k}(t) +\beta*E_{k}(t)), \tag{19}\]  
in which \(V\) represents the weight to adjust the importance of the two metrics. The right half of the equation is called the drift plus penalty function. Summarize (19), and we can obtain  
\[ \begin{array}{ll}&\lim_{T\to\infty}\frac{1}{t}(\sum_{t=0}^{T-1}\Delta( \theta(t))+\,\mathrm{V}\sum_{k=1}^{N}(T_{k}(t)+\beta*E_{k}(t)))\\ &=\lim_{T\to\infty}\Big{(}\frac{L(\theta(t))}{T}+\frac{\mathrm{V}}{T}\sum_{t =0}^{T-1}\,\sum_{k=1}^{N}(T_{k}(t)+\beta*E_{k}(t))\Big{)}\\ &=\lim_{T\to\infty}\frac{L(\theta(t))}{T}+\lim_{T\to\infty}\frac{\mathrm{V}}{ T}\sum_{t=0}^{T-1}\,\sum_{k=1}^{N}\text{Cost}.\end{array}  \tag{20}\]  
Hence, the long-term optimization problem \(P1\) is transformed into finding the offloading strategy for each time slot that minimizes the drift plus penalty function within that time slot.