# Dynamic Network Formation for FSO Satellite Communication
## 3 Minimum Spanning Tree on Dynamic Graphs (DMST)
### Discrete Dynamic Graphs \(Mst\)
The red notes degree greater than three. (b) Three bounded degree spanning tree of the graph presented in (a). The main method of this algorithm is presented in Algorithm 2. The method inputs are the graph, the edge weights and the number of steps, which is the number of attempts to build a spanning tree. The main method first assigns ants to randomly chosen vertices in the graph, initiates the pheromone level for each edge and then loops over the number of steps where each step moves the ants along the graph and builds a tree described in Algorithms 3 and 4. ```
Input: \(\bullet\) communication graph \(G\) \(\bullet\) a weight function for each edge \(w\) \(\bullet\) maximum degree: \(\lambda\) \(\bullet\) number of steps: \(n\) and number of ants \(a\) Result: low-cost degree-bound spanning tree \(T\) let \(T=<N,\emptyset>\) be an empty graph assign \(a\) ants to random vertex in \(G\) init pheromones on \(G\) edges for\(n\)-stepsdo T=Move Ants and Build Spanning Tree Algorithm 3 (G,w,T, \(\lambda\)) return\(T\)
```
**Algorithm 2**AC algorithm for low cost degree-bound spanning tree: Main method. Algorithm 3 describe the ants' movement on the graph and the pheromones update. For a predefined number t times, the ants move on the graph, and the ants move from one vertex to another favoring the low cost edge (with some probability) to travel along. On the edge chosen, the pheromone level will be updated using this formula:

\[Ph=\epsilon\times Ph_{old}+(1-\epsilon)\frac{1}{cost} \tag{1}\]

where \(Ph_{old}\) is the previous pheromone level, \(cost\) is the edge cost, and \(\epsilon\) is a predefined parameter used to define the weight of the new calculation on the pheromone level against the old pheromone level. After moving the ants a few times, the algorithm attempts to construct a tree based on the pheromone level on the edges; the construction method is also based on [PERSON]'s algorithm or contracting a minimum spanning tree but taking into account the degree bound. Figure 7: The Ant-Colony algorithm flow. ```
Input:
* communication graph \(G\)
* a weight function for each edge \(w\)
* a Tree \(T\)
* maximum degree \(\lambda\) Result: low-cost degree-bound spanning tree \(T\)
1 let \(C=w(T)\)
2 whilew(T) is decreasingdo
3 for\(t\)timesdo
4 move ants(\(G\))
5 update pheromones(\(G\))
6\(T\)=construct tree(\(G\), \(\lambda\)) (using Algorithm 4)
7 if\(w(G^{\prime})\leq c\)then
8\(c=w(G^{\prime})\)
9\(T=G^{\prime}\)
10 evaporate pheromones(\(G\)) return\(T\)
```
**Algorithm 3**Move ants and build spanning tree algorithm. ### Local Minimum

The Ant Colony algorithm performs well against \(NP\)-hard problems. However, it has an inherent disadvantage of falling in local minimum, which is very likely in the addressed problem of satellite inter-links given the massive number of vertices and iterations. This is why the evaporation process is commonly utilized in AC algorithms. The probabilistic nature of this process can overcome those problems [31]. Our implementation of the evaporation process is elaborated in Algorithm 3. ```
Input:
* dynamic graph \(G\) and the pheromone level on the edges
* degree-bound \(\lambda\) Result: low-cost degree-bound spanning tree T
1 let T=<N,\(\emptyset\)> be an empty graph
2 SE=sort G edges by pheromone level
3 whileT is not connecteddo
4 let e={ i, j} be the first edge on SE
5 if( adding e does not form a circle in T) and (after adding e i and j degree is \(\leq\lambda\))then
6 T=T+e
7 remove e
8 return\(T\)
```
**Algorithm 4**Tree construction algorithm. Algorithm 5

### Optimizing the Next Step: Pheromones Transfer

After describing the AC method used for finding a low cost bounded degree spanning tree a static graph, this subsection describes how an extension can provide a fair solution on a dynamic graph as well. The algorithm described in this section uses the observations from the low-cost spanning tree problem on dynamic graphs and the algorithm presented in Algorithm 2. The method will be performed continuously for each time interval of the dynamic graph.