# Energy-Efficient and QoS-Aware Computation Offloading in GEO/LEO Hybrid Satellite Networks
## 2 Materials and Methods
### Computation Offloading Method Based on Minimum Cost Maximum Flow
#### 2.2.2 Transformation of Computation Offloading Problem into Minimum Cost Maximum Flow Problem
The equation is as follows Figure 3:3 (30) Figure 3:4 (31)
* **e(GEO_Node,T)**: we set the capacity to a larger value, \(Z\), to ensure that the missions can be successfully offloaded to the sink node, \(T\). Since the mission processing result is much smaller than the original amount of data, we neglect the energy consumed by the result return and set the unit cost to zero. Thus, we can obtain Equation (32). Figure 3:5 (32) Figure 3:6 (33)
* **e(Self,T)**: we set the capacity to \(X\) to guarantee that the missions processed on LEO satellites can successfully flow to the sink node, \(T\), and the unit cost is set to zero since there is no additional consumption. Thus, we can obtain Equation (34). Figure 3:7 (34) Figure 3:8 (35)* **e(U,T)**: similar to the capacity definition of \(e(Mission\_Node,U)\), the capacity of this edge is set to \(MAX\), which is also carried out to ensure that the failed missions can successfully flow to the sink node, \(T\), and the unit cost is set to zero since there is no actual consumption, so that Equation (36) can be obtained. Figure 3:9 (36) \[c(u,v)=\sum_{n=1}^{|N_{u}|}B_{n,v}, u=S,\forall v\in\mathcal{L}\]0 (37)  
**Formulation of MCMF for computation offloading:** based on the above mentioned, the partial computation offloading problem for on-board missions can be transformed into the MCMF problem, as shown in Equation (38). The minimum value of \(\sum_{e(u,v)\in\mathcal{E}}f(u,v)w(u,v)\) corresponds to our optimization objective, i.e., total energy consumption, and the offloading decision can be obtained from the solved MCMF. min \[c(u,v)=\sum_{n=1}^{|N_{u}|}B_{n,v}, u=S,\forall v\in\mathcal{L}\]1 (38) s.t. \[c(u,v)=\sum_{n=1}^{|N_{u}|}B_{n,v}, u=S,\forall v\in\mathcal{L}\]2 (39) \[=\left\{ \begin{array}{ll}\sum_{i=1}^{|L|}\sum_{n=1}^{|N_{i}|}B_ {n,i}&u=S\\ -\sum_{i=1}^{|L|}\sum_{n=1}^{|N_{i}|}B_{n,i},&u=T\\ 0,&u\
eq S,T\end{array} \right.\] (40)  
where Equation (39) denotes that the amount of flow passing through an edge cannot exceed its capacity. Since in our improved flow network, as shown in Figure 4a, the U node can guarantee that the data volume of all missions flows out of the source node, \(S\), and into the sink node, \(T\), so the maximum flow, \(f_{max}\), in Equation (21) is equal to \(\sum_{i=1}^{|L|}\sum_{n=1}^{|N_{i}|}B_{n,i}\), and for all intermediate nodes except the source and sink node the outflow must be equal to the inflow. For the convenience of readers, based on Equations (22)-(37), we denote the unit cost of different types of edges by Equation (41), and the capacity of different types of edges can be expressed as Equation (42). \[w(u,v)=\left\{ \begin{array}{ll}0,&u=S,\forall v\in\mathcal{L}\\ 0,&\forall u\in\mathcal{L},\forall v\in\mathcal{N}_{u}\\ \kappa^{geo}(f_{u,i}^{geo})^{2}m_{u,i}+\frac{p_{i}}{R_{u,i}^{w}},&\forall i \in\mathcal{L},\forall u\in\mathcal{N}_{i},\forall v\in\mathcal{H}\\ \kappa^{loc}(f_{u,v}^{loc})^{2}m_{u,v},&\forall u\in\mathcal{N}_{i},v=Self\\ K,&\forall i\in\mathcal{L},\forall u\in\mathcal{N}_{i},v=U\\ 0,&\forall u\in\mathcal{H}\cup Self\cup U,v=T\end{array} \right. \tag{41}\]  
\[c(u,v)=\left\{ \begin{array}{ll}\sum_{n=1}^{|N_{i}|}B_{n,v},&u=S,\forall v\in \mathcal{L}\\ B_{v,n},&\forall u\in\mathcal{L},\forall v\in\mathcal{N}_{u}\\ \frac{f_{u,i}^{geo}}{f_{u,i}^{geo}+R_{v,i}^{w}m_{u,i}},&\forall i\in\mathcal{ L},\forall u\in\mathcal{N}_{i},\forall v\in\mathcal{H}\\ \frac{f_{u,i}^{geo}}{f_{u,i}^{geo}+R_{v,i}^{w}m_{u,i}},&\forall u\in\mathcal{ N}_{i},v=Self\\ \frac{f_{u,i}^{geo}}{f_{u,v}^{geo}},&\forall u\in\mathcal{L},\forall u\in \mathcal{N}_{i},v=U\\ Z,&\forall u\in\mathcal{H},v=T\\ X,&u=Self,v=T\\ MAX,&u=U,v=T\end{array} \right. \tag{42}\]