# Dynamic Network Formation for FSO Satellite Communication
## 3 Minimum Spanning Tree on Dynamic Graphs (DMST)
### Discrete Dynamic Graphs \(Mst\)
The result show that, after 30 steps, on average, the extra cost reduction was insignificant (Figure 9). Finally, we tested the method of Algorithm 5 for continuous dynamic low-cost degree-bound spanning trees. The main goal was to prove that the method converged to a solution faster after pheromone transfer compared with performing that static method on each time interval. We performed the following experiment: on 200, 400, 800 and 1600 sized graphs, we computed five consecutive communication graphs (representing five time-intervals). On these graphs, we performed two experiments. The first experiment was attempting the static method on each graph, the same as in Figure 8, for 10 steps, and, in the second method, we performed the continuous method with pheromone transfer. We computed the bounded spanning tree cost after each step and presented it in a graph. Figure 10 shows the different method results. The graph shows that the continuous method improved the cost reduction rate significantly. One can see that, if the algorithm starts with a random set of pheromones, the initial convergence will be very rapid (since the initial guess is random). This phenomenon is depicted in the rapid decay of the orange line in the beginning of each sequence. On the other hand, when the computation starts with previously computed pheromones, since those pheromones are already close to optimal, the convergence will be much slower as illustrated by the blue line. The system run-time for each graph size is given by Table 3. The table shows the average time of each step on different graphs, each step includes moving the ants 150 times, updating the graph data and constructing the spanning tree. In order to decide what is the optimal step nail to take to get to the complexity threshold, one has to consider few parameters: (i) The graph size (the number of vertices). \begin{table}
\begin{tabular}{c c c c c} \hline \hline Size (number of vertices) & 200 & 400 & 800 & 1600 \\ \hline Run-time (seconds) & 1.3 & 5.2 & 22.71 & 100.23 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: AC algorithm run-time result. Figure 10: AC for low-cost continuous bounded degree spanning tree algorithm for an 800-vertex graph. (ii) The number of edges. (iii) The rate of topological change of the graph over time. The FSO graph is basically a geometric (visibility) graph in which two nodes may establish a link if the distance between them is below some threshold. Therefore, the graph's average degree increases proportionally to the number of nodes. Therefore, in relatively small graphs (up to 400 nodes) due to a relatively small number of optional routing solutions, the suggested method may get caught in a local minimum, While in dense graphs (e.g., 800 and 1600 nodes), the suggested method seems to be able to \"route out\" of local minimums. Figure 9 and Table 3 show a clear trade-off between the times where it is possible to let a single graph converge and the rate at which the dynamic graph is cut. ## 6 Conclusions

This study proposed a method for calculating a cost-effective bounded degree tree for a dynamic network. The motivation for the study was to suggest a method for the fast calculation of intelligent networks based on satellite interlink optical communications, such as SpaceX's massive Starlink constellation. This paper offers some essential insights into computing such a network: (i) Frequent shifting of the network edges causes major topological changes in the underlying FSO communication graph. Therefore there is a need for a dynamic heuristics applicable of computing runtime solutions for online input scenarios. (ii) In optical communication-based networks, establishing a new link takes time. Hence, an existing link should last for a reasonable duration before creating a new one. (iii) The satellite structure limits the number of concurrent neighbors that each node can be connected to. Given these observations, a method for searching for cost-effective bounded degree spanning trees is presented.