## 3 Dynamic Link Establishment of Mega-Constellations
### Optimization Matching Algorithm for Dynamic Links
Therefore, in practical implementation, it suffices to record merely the position of the receptacle for each flower to represent the entire configuration. This encapsulates the approach to resolving issues arising from odd cycles. In the case of considering the maximum weight matching, let \(x_{e}\) represent whether to select edge e as the matching edge between two satellite nodes, where \(x_{e}=1\) indicates selecting the edge, otherwise \(x_{e}=0\). Let \(S\subseteq E\), defining \(x(S)=\sum_{e\in S}x_{e}\), and \(\gamma(S)\), representing the set of edges in set \(S\). Let \(\delta(v)\) denote the set of edges connected to satellite node \(v\), \(w(e)\) be the edge weight, and O represent all of the blossoms. Assign a weight value to each satellite node, denoted as \(z_{u}\) for node \(u\), and when encountering a blossom, let the weight be \(z_{B}\). For all of the edges (\(u\),\(v\)), in the context of maximum weight matching, all matching edges must be \"equal edges (Grow)\", meaning that the sum of the weight of  
Figure 11: Illustration of the “flower”. the satellite nodes \(u\) and \(v\)'s weights should equal the weight of edge (\(u\),\(v\)), as shown in Equation (10):  
\[z_{u}+z_{v}=w(e) \tag{10}\]  
In this case, the edge label \(z_{e}=z_{u}+z_{w}-w(e)=0\). Then, solving the maximum weight-matching problem can be expressed as the following linear programming problem:  
\[\text{Objective}:\ \max\!\!\sum_{e\in E}w(e)x_{e} \tag{11}\]  
\[\text{Constraints}:\ \begin{cases}\  
If \(\delta=\delta_{3}\) occurs, to prevent \(z_{B}<0\), it is necessary to split the blossom. During the blossom-splitting process, alternating paths within the blossom need to be retained, and the remaining satellite nodes not included in the alternating paths are designated as white. During the algorithm initialization, all of the top labels of satellite nodes \(u\) are set to the following:  
\[z_{u}=\max(\{w(e)\})/2,e\in E \tag{21}\]  
For all matched points \(u,z_{u}>0\) is required; points with top labels of zero will become unmatched points. The above describes the solution method for the maximum weight-matching problem in a general graph. As mentioned earlier, through the previously calculated \(\alpha(t)\), we have already determined whether the satellites are subject to the connectable constraints at each time moment. The matrix itself is constructed based on the persistence duration of the satellites, serving as the weights for the subsequent matching processes. As time progresses, the persistence duration of the satellites gradually decreases, leading to a reduction in the weights within the matrix. Consequently, during the next round of matching, satellites with diminished durations may receive less priority due to their relatively smaller weights, resulting in frequent switching phenomena. To mitigate this issue, we introduce the \"elite retention strategy\" borrowed from genetic algorithms to address the problem of frequent switches caused by diminishing weights. Before each matching operation at any given time, we first examine whether pairs of satellites that were previously connected in various connection strategies exist. If such pairs are found, they are designated as \"elite\" pairs. For these elite pairs, their corresponding weights are not calculated based on the current moment's values but are instead adjusted to reflect their initial maximum weight when the connection was first established. Consequently, even as the persistence duration of the satellites decreases, the weights of these elite pairs remain at a high level, effectively mitigating the issue of frequent switches. Through this enhancement, we can more effectively manage satellite matching problems at each time instant, thereby improving the stability and efficiency of the system. A flowchart illustrating this method is presented in Figure 13.  
Figure 12: Principle diagram of the algorithm’s key steps.