# Dynamic Network Formation for FSO Satellite Communication
## 3 Minimum Spanning Tree on Dynamic Graphs (DMST)
### Discrete Dynamic Graphs \(Mst\)
This section presents a heuristic method for computing a cost-effective bounded spanning tree on dynamic graphs. Note that the bounded degree minimum spanning tree problem is NP-Hard even for static graphs. This motivated the offered heuristic attempts to provide a low cost solution in a reasonable time. Figure 6 shows an example of why an algorithm for finding unbounded \(MST\) will yield insufficient results that do not match the optimization we are looking for. This figure describes two spanning graphs of the same satellite-based network of 500 vertices. Figure 6a shows the minimum spanning tree with no degree limit (calculated by a Kruskal algorithm); the vertices painted in red are vertices with a rank higher than 3. Figure 6b depicts a (non-minimal) spanning graph of the same graph with all vertices less than 3. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Edges** & **t1** & **t2** & **t3** & **T** \\ \hline \(e_{1}\) & 2 & 1 & 3 & 6 \\ \(e_{2}\) & 2 & 2 & 4 & 8 \\ \(e_{3}\) & 1 & 7 & 1 & 9 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: MST algorithm example. Figure 5: Algorithm example: communication graph constellation at three points in time (t1–t3). The optimal tree (T) and the algorithm result (T’) on trees (t1) and (t2), which is not optimal. Previous works have tackled this problem in different methods [27; 28; 29]. One of the methods utilizes an Ant-Colony (AC) algorithm [30]. AC algorithms are inspired from ants' behavior in their colony and the way they are seeking for food in their vicinity. AC algorithms are mainly used to find the shortest path on the traveling salesman problem (another NP-hard problem). Each ant solves the search problem by walking a certain path and leaves behind a pheromones trail to guide the next ant to come. The next ant will prefer to choose a way that has a strong pheromones scent, an indication that other ants already used it. After several such cycles, all the ants manage to find the shortest way to the food. The intuition for choosing the AC method to build such a communication network where the vertices are connected via minimum weight is as follows: a standard MST algorithm chooses the low weighted edges until reaching a tree while avoiding circles (using the Kruskal algorithm). This algorithm provides an MST with some vertices having higher degree than allowed. This method can be adopted to bounded degree trees by'replacing' edges that violate the degree restriction and using a bypass to connect the vertex to the rest of the network (via other vertices). However, choosing such a path is hard and relies on the question: what is the shortest path between two connected component on graph. With the AC method, the ants mark the best edges to use for minimizing the path between the graph vertices. Building the tree using the pheromone level could yield a graph that connects the vertices using optimal paths. To the best of our knowledge, all the previous methods that tackled this problem were restricted to static graphs only. The novelty of this work is the adaptation of the AC method for dynamic bounded-degree spanning trees. The rest of this section describes both static and dynamic bounded-degree graphs using the AC algorithm. ### AC Algorithm for Finding Low Cost Degree Bound Spanning Tree

The algorithm is divided into the following stages:

1. Initialization. The ants are randomly assigned to the graph vertices. 2. Search. The ants \"move\" on the graph when they prefer high cost edges in high probability. A visited edge will be marked to update the pheromone levels in the next step. 3. Graph construction. Creating a spanning graph using the pheromone level on the edges while avoiding the degree-bound restriction. 4. Quality check. If the tree's weight is lower than the tree we calculated earlier, it will be the new candidate. If not: Rearrange the pheromone level to avoid a local minimum situation (Evaporate pheromones). Figure 7 presents the Ant-Colony algorithm for dynamic graph flows. Figure 6: (a) MST of a 500 vertices graph.