# 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.3 Successive Shortest Path-Based Computation Method  
There are two main methods to solve the MCMF problems: one is the cycle-canceling algorithm (CCA). CCA first uses the method of solving the maximum flow problems to establish a feasible flow, \(f\), and then, in the process of eliminating negative cycles, the total cost is gradually reduced while ensuring the feasibility of \(f\) until there is no negative cycle [29]. The other is the successive shortest path algorithm (SSPA). SSPA generally takes zero flow as the initial flow, finds an augmenting path from the source node, \(S\), to the sink node, \(T\), on the residual network, augments the flow on this path to the current flow, and then iteratively finds the augmenting path until it increases to the maximum flow. While finding the augmenting path, SSPA gives preference to the augmenting path with the minimum cost, thus ensuring that the augmented flow costs the minimum among the current feasible flows [30]. Next, the time complexity of these two algorithms is analyzed for the computation offloading problem studied in this paper. For CCA, the [PERSON]'s algorithm can be used to obtain the maximum flow with a time complexity of \(O(V^{2}E)\), where \(V\) denotes the number of nodes and \(E\) denotes the number of edges. Assuming that each elimination of negative cost cycles can reduce the cost by at least 1 unit, and \(C\) denotes the maximum capacity of all edges, then there are, at most, \(ECM\) times to find negative cost cycles and increase/decrease flow operations, where \(M\) denotes the maximum unit cost among all edges. In addition, the Bellman-Ford algorithm can be used to find negative cost cycles. Then, the time complexity of CCA is \(O(V^{2}E+VE^{2}CM)\) and, since \(VE^{2}CM\) is much larger than \(V^{2}E\), the final time complexity is \(O(VE^{2}CM)\). For SSPA, the Bellman-Ford algorithm with time complexity of \(O(VE)\) is used in finding the minimum cost path. Then SSPA augments, at most, \(O(VC)\) times. The time complexity of SSPA is \(O(V^{2}CE)\). In this paper, we study the partial computation offloading problem in GEO/LEO hybrid satellite networks, where the situation is \(C>M>E>V\). The time complexity analysis of the above two algorithms shows that the time complexity of SSPA is better than that of CCA (\(O(V^{2}CE)<O(VE^{2}CM)\)) for our problem. Therefore, we propose the successive shortest path-based computation offloading (SSPCO) algorithm, as shown in Algorithm 1. SSPCO uses the shortest path fast algorithm to search for the shortest path with unit cost as weight from the source node, \(S\), to the sink node, \(T\). Specifically, the flow network, \(G\), is first constructed based on the input set of on-board missions, GEO/LEO satellite processing capacity, channel bandwidth, and channel gain (line 1), and then the corresponding residual network, \(G^{R}\), is constructed based on \(G\), and the flows and unit costs of the edges on \(G^{R}\) are initialized (lines 2-7); the shortest augmenting path from the source node to the sink node is continuously searched for and augmented in residual network, \(G^{R}\), until there is no augmenting path, \(p\), in \(G^{R}\) (lines 8-18); finally, the MCMF is transformed into the offloading decision: if there is flow from the mission node to the U node, it is considered as the mission offloading failure, otherwise the offloading ratio can be calculated by the flow on the edges from the mission node to the GEO satellite node and the self node (lines 19-27).