# Dynamic Network Formation for FSO Satellite Communication
## 3 Minimum Spanning Tree on Dynamic Graphs (DMST)
### Discrete Dynamic Graphs \(Mst\)  
A discrete dynamic graph at time interval \(T=[0,t]\) is defined as an orderly set of graphs sampled at different timestamps between 0 and \(T\). We assume no topological changes, i.e, only the edges' weights are changing. The minimal spanning graph during \(T\) will be defined as the \(MST\). Put it differently, from all the edges in the complete graph, only the ones whose sum is minimal over time will be chosen. Figure 3 shows the difference in the MST on a simulated star-link graph in four different states in time. Between the states, there is only one second. This figure illustrates the problem of computing a bounded degree MST in short time intervals. Algorithm 1 describes the optimal spanning tree for dynamic communication graph process. ```
Input: Set of \(z\) communication graphs: \(G=g_{1}=<N,E_{1}>,\ldots g_{z}=<N,E_{z}>\) Result: An optimal spanning tree \(T=<N,E>\)
1 let \(G^{\prime}=<N,\emptyset>\) be an empty graph
2 forgin\(G\)do
3 forein\(E(g)\)do
4 w(G'(e))=w(g(e))+w(e)
5\(T=ST(G^{\prime})\) (T is the minimum spanning tree of G') return Figure 4 illustrates the algorithm by an example. Table 1 illustrates how the algorithm constructed the minimal spanning tree for that example. This algorithm is based on [PERSON]'s algorithm for finding a spanning tree in a static graph. The [PERSON]'s algorithm method for finding a minimum spanning tree is to start with an empty graph (only vertices and no edges) and to gradually add low cost edges until the graph is fully connected. Herein, we use that method but on an accumulating graph that is the sum of the edges costs through all the graphs. This algorithm is an extension to [PERSON]'s algorithm for a dynamic MST, and therefore its correctness relays on the dynamic MST definition and the correctness \begin{table}
\begin{tabular}{c c c c c} \hline
**Edges** & **t1** & **t2** & **t3** & **T** \\ \hline \(e_{1}\) & 1 & 8 & 2 & 11 \\ \(e_{2}\) & 1 & 2 & 4 & 7 \\ \(e_{3}\) & 7 & 3 & 1 & 11 \\ \(e_{4}\) & 2 & 2 & 2 & 6 \\ \(e_{5}\) & 3 & 4 & 3 & 10 \\ \hline \end{tabular}
\end{table} 
Table 1: MST on a dynamic graph algorithm example. Figure 4: Algorithm example: communication graph constellation at three points in time (t1–t3) and the optimal spanning tree (T). Figure 3: Dynamic MST. A 50-vertices star-link graph in four states one second apart. The magenta edges are the new edges that were added from the previous states. The vertices are colored differently so that the graph motion is easier to track. (**a**) MST in time 0. (**b**) MST in time 1. (**c**) MST in time 2. (**d**) MST in time 3. ### MST for Continuous Dynamic Graph

After presenting algorithm that computes the minimal spanning tree in dynamic graphs where the function on the edges is discrete, this subsection will discuss the continuous form of this problem. One method of handling the continuous mode is to arbitrarily choose number of points in time and use the algorithm on these points. Figure 5, and Table 2 shows a case where this method will not provide the optimal solution. Observation: the functions that represent the edges weight on dynamic graphs when dealing with satellite constellations are continuous functions. Since the weight of this edges is the distance between two satellites and due to the fact that the satellites moves in continuous orbit. We can rely on this observation to argue that, for dynamic graphs, we can provide a continuous solution when computing the integral over the edges in time instead of summing the edges weight in the discrete version. ## 4 The Degree Bounded Spanning Tree (DBST) Heuristic

As explained in Section 3.2, the spanning of a dynamic FSO-based network cannot be fully achieved using MST, since each satellite (vertex) has a limited amount of communication components it can carry (usually three or four). Thus, the number of links (or edges) for each vertex is bounded. This problem is referred to in the literature as \"the bounded degree minimum spanning tree\" [26].