## 4 Methodology
### Simulated Annealing Optimization Based on Graph Partitioning  
It is not easy to handle such a huge central network for satellite-UAV collaborative IoT systems. It is necessary to segment this huge network rationally and reduce the data flow between different parts after segmentation. It is based on this consideration that a novel optimization algorithm proposed is introduced by integrating the GP algorithm with the SA algorithm for satellite-UAV collaborative IoT system topology optimization. GPSA is inspired by the generation method of network maxflow neighborhood [33]. This method is based on the fact that the edges on the minimum cut have a strong influence on the connectivity and invulnerability of the graph. This can be useful in reducing overall computational and hardware complexity. First, graph partitioning can decompose large-scale networks into multiple smaller subnetworks, thus allowing these parts to be computed in parallel on different processing units. It is very useful in distributed computing to reduce computation complexity and increase algorithm-solving efficiency. Second, the load of each subpart is relatively uniform after segmentation, avoiding bottlenecks in the overall performance of the network due to the overloading of certain nodes. Third, the communication overhead between nodes is an important consideration in satellite Internet. By rationally dividing the network, the communication requirements between nodes are reduced so that the sum of link communication costs (bandwidth, etc.) for each part is minimized, thus improving overall performance.  
For a given satellite-UAV-integrated network, GPSA uses the idea of divide and conquer to perform graph partitioning, processes them sequentially, and then merges the results, giving priority to cutting edges. Figure 5 is a flow diagram of the GPSA algorithm.  
The GPSA algorithm first divides the input graph into partitions by the visual matrix and selects some edges in the set of cut edges to preserve in advance. In this thesis, the number of partitions divided by the graph is 4. For each partition, allocate the maximum number of edges in proportion to the number of interior points in the partition. Then, the visibility matrix and distance matrix of each partition are processed, and the initial solution is inherited from the former time slice and adapted according to the self-adapt method. Afterward, apply a partial SA on each partition given a larger exit threshold. It is worth mentioning that this step can be performed in parallel. When the procedures of all partitions are completed, the solution matrices of the subgraph are mapped back to the solution matrix of the full graph, which are merged with the cut edges selected in advance into a complete initial solution, and then the SA algorithm is applied again on this whole graph initial solution.  
Figure 5: A flow diagram of simulated annealing optimization based on graph partitioning.  
The existing works mostly focus on the efficiency (number of iterations) of the iterative process and overlook the situation of the initial solution. However, the structure of the initial solution largely determines the subsequent iterative process. It is an effective way to continuously divide and process the network into smaller and smaller partitions for near-Earth satellite-UAV collaborative IoT systems that may emerge in the future and then merge them step by step into the solution of the entire network.