# 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  
**Construction of flow network:** to map the partial computation offloading problem of on-board missions into the MCMF problem, we formulate the problem using a specific structure of the flow network. Figure 3 shows a natural idea to construct a flow network, which corresponds to an instantaneous status of GEO/LEO hybrid satellite networks, while encoding a set of LEO satellites and GEO satellites. The flow network can be described as follows. * **Source node:** the source node (\(S\)) is a virtual node that can satisfy the single-source single-sink condition in solving the MCMF problems. * **LEO node:** the LEO node (\(LEO\_Node\)) denotes the LEO satellite in GEO/LEO hybrid satellite networks. * **GEO node:** the GEO node (\(GEO\_Node\)) denotes the GEO satellite in GEO/LEO hybrid satellite networks. Each node has an edge from the LEO node in its coverage area, and the amount of the flow on the edge indicates the amount of mission data offloaded from the LEO satellite to the GEO satellite. * **Sink node:** the sink node (\(T\)) is a virtual node that is introduced to satisfy the single-source single-sink requirement when solving the MCMF problem. Figure 2: A case of minimum cost maximum flow network. A path of one MCMF solution must first connect to an LEO node from the source node and then reach the sink node through a GEO node. Thus, if a path goes through a GEO node, it represents an offloading for the missions on an LEO satellite. For instance, the solution as shown in Figure 3 corresponds to an offloading decision: missions on \(LEO_{0}\) and \(LEO_{1}\) are offloaded to \(GEO_{0}\); missions on \(LEO_{2}\) are offloaded to \(GEO_{1}\); and missions on \(LEO_{[L]}\) are offloaded to \(GEO_{|H|}\). However, in the multiple satellites and multiple missions scenario, the flow network shown in Figure 3 has the following problems:  
1. Since there may be several missions in LEO satellites, the satellite-level granularity modeling shown in Figure 3 cannot generate mission-level offloading decisions;
2. The network shown in Figure 3 can only represent the process of missions offloaded to GEO satellites and cannot represent the process of missions processed on LEO satellites;
3. Due to the limited computing and storage resources of LEO and GEO satellites, the offloading of several missions may fail. However, the network shown in Figure 3 cannot indicate mission offloading failures. To address the above issues, we propose an improved flow network, as shown in Figure 4a. Based on the initial flow network, as shown in Figure 3, we add three types of nodes, which can be described as follows. * **Mission node:** the mission node (_Mission_Node_) represents the missions generated on or accessed from LEO satellites and different LEO nodes have different numbers of mission nodes. By adding mission nodes, finer-grained mission-level offloading decisions can be generated. * **Self node:** the self node (\(Self\)) indicates the process of missions processed on LEO satellites, and all mission nodes are connected to the self node. * **U node:** when there is a flow passing through the edge connecting a certain mission node and the U node (\(U\)), it means that the processing time of the mission is greater than its QoS constraint, indicating that the offloading has failed. Figure 3: Initial flow network in GEO/LEO hybrid satellite networks. A path of one MCMF solution must first connect to an LEO node from the source node and then pass through the mission node and finally reach the sink node through a GEO node or the U node or the self node. Thus, if a path only goes through a GEO node, it represents a full offloading for a mission on an LEO satellite. In addition, if a path only goes through the self node, it represents that the mission is fully processed on the LEO satellite where the mission is generated, and, if a path goes through both a GEO node and self node, it represents a partial offloading for the mission on an LEO satellite.