# 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
Otherwise, if a path goes through the U node, it represents that the offloading has failed. For instance, all bold edges can be one possible solution obtained by MCMF algorithms, as shown in Figure 4b. The figure corresponds to an offloading decision: \(mission_{0}\) on \(LEO_{0}\) is fully offloaded to \(GEO_{0}\); \(mission_{1}\) and \(mission_{2}\) on \(LEO_{1}\) are partially offloaded to \(GEO_{1}\) and the remaining parts are processed on \(LEO_{1}\) simultaneously; \(mission_{3}\) on \(LEO_{2}\) is failed; and \(mission_{4}\) on \(LEO_{3}\) is fully processed on \(LEO_{3}\). **Capacity and unit cost:** as indicated in Section 2.2.1, the capacity and the unit cost are the key factors in solving MCMF problems. Thus, based on Figure 4a, the capacity and the unit cost of different types of edges will be defined to transform this partial computation offloading problem into an MCMF problem. Let \(e(u,v)\) denote the edges from node \(u\) to node \(v\), and \(\mathcal{E}\) denote the set of all edges. We use \(c(u,v)\) and \(w(u,v)\) to represent the capacity and the unit cost of \(e(u,v)\), respectively. Next, we present the capacity and unit cost of different types of edge in \(\mathcal{E}\). * **e(S,LEO_Node)**: we set the capacity to be the sum of the amount of data of all missions on the LEO node. Since there is no actual consumption, the unit cost is set to zero, which can be given by \[c(u,v)=\sum_{n=1}^{|N_{u}|}B_{n,v}, u=S,\forall v\in\mathcal{L}\] (22) \[w(u,v)=0, u=S,\forall v\in\mathcal{L}\] (23)
* **e(LEO_Node,Mission_Node)**: we set the capacity to the amount of data of the mission node \(v\). And the unit cost is set to zero as there is no actual consumption, which can be expressed as \[c(u,v)=B_{v,u}, \forall u\in\mathcal{L},\forall v\in\mathcal{N}_{u}\] (24) \[w(u,v)=0, \forall u\in\mathcal{L},\forall v\in\mathcal{N}_{u}\] (25)  
Figure 4: Improved flow network and a case in GEO/LEO hybrid satellite networks. (**a**) Improved flow network in GEO/LEO hybrid satellite networks. (**b**) A case of improved flow network. * **e(Mission_Node,GEO_Node)**: the maximum amount of mission data that can be offloaded to the GEO satellite is calculated based on the QoS constraint and the processing density, and the capacity is set to this calculated value. We also set the unit cost to the sum of the unit transmission energy consumption and the unit computational energy consumed by the GEO satellite, as shown in Equation (26). \[c(u,v) =\frac{f_{u,v}^{v,geo}\tau_{u,i}R_{u,i}^{v}}{f_{u,v}^{v,geo}+R_{u,i}^{v}m_ {u,i}}, \forall i\in\mathcal{L},\forall u\in\mathcal{N}_{i},\forall v\in\mathcal{H}\] (26) \[w(u,v) =\frac{E_{u,i}^{v,geo}+E_{u,i}^{v,tra}}{\lambda_{u,i}B_{u,i}}\] \[=\kappa^{geo}(f_{u,i}^{v,geo})^{2}m_{u,i}+\frac{p_{i}}{R_{u,i}^{v }}, \forall i\in\mathcal{L},\forall u\in\mathcal{N}_{i},\forall v\in\mathcal{H}\] (27)
* **e(Mission_Node, Self)**: we calculate the maximum amount of mission data that can be be processed on the LEO satellite based on the QoS constraint and the processing density, and set the capacity to this calculated value. The unit computational energy consumed by the LEO satellite is mapped to the unit cost, as shown in Equation (28). Figure 3:0 (28) Figure 3:1 Figure 3:2 (29)
* **e(Mission_Node,U)**: the capacity of this edge is set to \(Y\), and \(Y\) needs to be greater than the total sum of the amount of the mission data, which is to ensure that failed missions can successfully flow to the sink node, \(T\). In addition, the unit cost is set to \(K\), and \(K\) is greater than the unit energy consumption of all offloaded missions. This is because the proposed SSPCO method selects the path with the minimum cost while finding the shortest augmenting path. If the unit cost of \(e(Mission_Node,U)\) is small, SSPCO will give up offloading missions to GEO satellite nodes or self nodes and offload to U nodes instead, which leads to offloading failure.