## 5 Algorithm Design
### Resource Allocation  
Assuming that \(x_{i,0}^{*}\), \(x_{i,S}^{*}\), and \(x_{i,B}^{*}\) are fixed, the sets \(\mathcal{N}^{D}=\left\{i\left|x_{i,0}^{*}=1\right\},\mathcal{N}^{S}=\left\{i \left|x_{i,S}^{*}=1\right\}\right.\), and \(\mathcal{N}^{B}=\left\{i\left|x_{i,B}^{*}=1\right\}\right.\) can be obtained, \(\mathcal{P}\) can be transformed into the problem \(\mathcal{P}1\). \[\min_{\left\{f_{i,S}\sim f_{i,B}\right\}}\sum_{i\in\mathcal{N}^{ D}}\frac{c_{i}a_{i}}{f_{i,0}}+\sum_{i\in\mathcal{N}^{S}}\left(\frac{a_{i}}{r_{ i,S}}+\frac{2d_{i,S}}{c}+\frac{c_{i}a_{i}}{f_{i,S}}\right)+\sum_{i\in \mathcal{N}^{B}}\left(\frac{a_{i}}{r_{i,S}}+\frac{2d_{i,S}}{c}+\frac{a_{i}}{r_ {\text{S,G}}}+\frac{2d_{\text{S,G}}}{c}+\frac{c_{i}a_{i}}{f_{i,B}}\right)\] (8a) s.t. \[\sum_{i\in\mathcal{N}^{B}}f_{i,B}\leq F_{\text{B}}, \tag{8b}\] \[0\leq f_{i,S}\leq F_{\text{S}},\forall i\in\mathcal{N}^{S},\] (8c) \[0\leq f_{i,B}\leq F_{\text{B}},\forall i\in\mathcal{N}^{B}. \tag{8d}\]  
Equation (8a) is the objective function. The meanings of (8b)-(8e) are similar with those of (7b)-(7e). It can be seen from \(\mathcal{P}1\) that the local computing delay is a constant, and the computing resource allocation of the LEO satellite and that of the BS are independent. Therefore, \(\mathcal{P}1\) can be decomposed into two sub-problems, i.e., \(\mathcal{P}1.1\) and \(\mathcal{P}1.2\), then \(f_{i,S}^{*}\) and \(f_{i,B}^{*}\) can be obtained by solving them separately. \(\mathcal{P}1.1\) is the computing resource allocation of the LEO satellite's MEC server, which can be expressed as  
\[\min_{\left\{f_{i,S}\right\}}\sum_{i\in\mathcal{N}^{S}}\left(\frac{a_{i}}{r_ {i,S}}+\frac{2d_{i,S}}{c}+\frac{c_{i}a_{i}}{f_{i,S}}\right) \tag{9}\]  
s.t. (8b) and (8d). The sum in (9) is denoted by \(U^{S}\). \(\partial U^{S}/\partial f_{i,S}=-c_{i}a_{i}/(f_{i,S})^{2}\). The first derivative is less than 0. \(\partial^{2}U^{S}/\partial\left(f_{i,S}\right)^{2}=2c_{i}a_{i}/(f_{i,S})^{3}\). The second derivative is greater than 0. \(\partial^{2}U^{S}/(\partial f_{i,S}\partial f_{j,S})=0\), \(i,j\in\mathcal{N}^{S}\), \(i\
eq j\). The second mixed partial derivative is equal to 0. Therefore, the Hessian matrix of \(U^{S}\) is positive definite, and \(U^{S}\) is convex. \(\mathcal{P}1.1\) can be solved by using the Lagrange multiplier method, the Lagrange function is constructed as  
\[L(f_{i,S},\theta)=\sum_{i\in\mathcal{N}^{S}}\left(\frac{a_{i}}{r_{i,S}}+\frac{ 2d_{i,S}}{c}+\frac{c_{i}a_{i}}{f_{i,S}}\right)+\theta\bigg{(}\sum_{i\in \mathcal{N}^{S}}f_{i,S}-F_{\text{S}}\bigg{)}, \tag{10}\]  
where \(\theta\) is the Lagrange multiplier and \(\theta\geq 0\). Karush-Kuhn-Tucker (KKT) conditions are listed as  
\[\frac{\partial L(f_{i,S},\theta)}{\partial f_{i,S}} =-\frac{c_{i}a_{i}}{\left(f_{i,S}\right)^{2}}+\theta=0, \tag{11}\] \[\frac{\partial L(f_{i,S},\theta)}{\partial\theta} =\sum_{i\in\mathcal{N}^{S}}f_{i,S}-F_{\text{S}}=0, \tag{12}\]\[\theta\bigg{(}\sum\limits_{i\in\mathcal{N}^{\text{S}}}f_{i,\text{S}}-F_{ \text{S}}\bigg{)}=0, \tag{13}\] \[\theta\geq 0,\] (14) \[\sum_{i\in\mathcal{N}^{B}}f_{i,B}\leq F_{\text{B}}, \tag{8b}\]0  
\(f_{i,\text{S}}=\sqrt{c_{i}a_{i}/\theta}\) is obtained from (11). Substituting it into (12), we can get \(\sum_{i\in\mathcal{N}}\sqrt{c_{i}a_{i}/\theta}-F_{\text{S}}=0\), i.e., \(\sum_{i\in\mathcal{N}^{\text{S}}}\sqrt{c_{i}a_{i}}=F_{\text{S}}\sqrt{\theta}\). So \(f_{i,\text{S}}=\sqrt{c_{i}a_{i}}/\sqrt{\theta}=F_{\text{S}}\sqrt{c_{i}a_{i}}/ \left(\sum_{i\in\mathcal{N}^{\text{S}}}\sqrt{c_{i}a_{i}}\right)\). Considering (8d), we can deduce  
\[\sum_{i\in\mathcal{N}^{B}}f_{i,B}\leq F_{\text{B}}, \tag{8b}\]1  
\(\mathcal{P}\)1.2 is the computing resource allocation of the BS's MEC server, which can be expressed as  
\[\sum_{i\in\mathcal{N}^{B}}f_{i,B}\leq F_{\text{B}}, \tag{8b}\]2 (16) s.t. (8c) and (8e). The sum in (16) is denoted by \(U^{\text{B}}\). \(\partial U^{\text{B}}/\partial f_{i,\text{B}}=-c_{i}a_{i}/(f_{i,\text{B}})^{2}\). The first derivative is less than 0.