# Dynamic Network Formation for FSO Satellite Communication
## 3 Minimum Spanning Tree on Dynamic Graphs (DMST)
### Discrete Dynamic Graphs \(Mst\)
At the starting point (first time interval), the algorithm will perform the method for static graph but, for the next time intervals, the algorithm will use the previously calculated graph pheromones, for a prediction on edge at the time interval. Algorithm 5 describes the continuous process. ```
Input:
1. dynamic graph G=<V,E>
2. a weight function for each edge \(w\)
3. maximum degree:\(\lambda\)
4. previous state graph: prev
5. Pheromones percent to copy P
Result: low-cost degree-bound spanning tree T
1 let T=<N,\(\varnothing\)> be an empty graph
2 E=chose P percent of the edges in prev to reassign pheromones
3 copy pheromones in prev(E) in to G(E)
4 T= Algorithm 3 (G,w,T, \(\lambda\)) from line 5. return\(T\)
```

**Algorithm 5**AC algorithm for low-cost degree-bound spanning tree: continuous method. The continuous method will be performed on each time interval. Each time the method obtains the previous state graph _prev_, which holds the latest calculated pheromones, the method will copy some of the pheromones to the current graph in order to speed up the calculation. The top 50% of the pheromones are chosen for this process. Since the graph is continuous, it is a reasonable assumption that optimal edges will keep their score while sub-optimal edges will be replaced. We rely on the observation that, between time intervals, the majority if the edges weights will not change significantly, considering that the satellite movement is continuous. However, the method does not copy all the pheromones from the previous state in order to avoid a local minimum. A predefined parameter \(P\) represents the percentage of pheromones to copy. The rest of the edge pheromones will be initiated the same as in the first state. After copying the pheromones, the method will perform the main loop described in Algorithm 2. ## 5 Results

In order to test the proposed method on real data, we built a simulator that used real-time satellite motion information. We created a dynamic graph from this data and tested our algorithm (nDBST) with respect to the run time, convergence and final graph cost. This section describes both the simulator itself and the results on static and dynamic graphs. ### Simulator

The real-time data was obtained from the Starlink satellite network. Since Starlink satellite locations are available online (and can be even computed for two weeks in advance), it was a perfect candidate to verify the algorithm's correctness. A series of dynamic graphs were created and embedded using two open source Python libraries:

* Networkx [32]. This library was developed for the study of complex networks and has method implementations, such as computing MST, check connectivity and computing the connected components of graph algorithms. * Ephen [33]. Used for performing high-precision astronomy computations. The simulation can be conceptually divided to two steps: pre-process and method testing. The pre-process step retrieves the Starlink satellite locations using the Ephem library, computes the distance between the satellites, and assigns each edge with the respective cost as described in Section 2. For the method testing step, we implemented the low-cost bounded degree method described in Algorithm 2 and tested its performance on these graphs. The code used for testing the method can be found at [[https://github.com/RevitalMarbel/AC_for_dnbdst](https://github.com/RevitalMarbel/AC_for_dnbdst)]([https://github.com/RevitalMarbel/AC_for_dnbdst](https://github.com/RevitalMarbel/AC_for_dnbdst)) (accessed on 24 October 2021). The experiment included graphs in different sizes: 200, 400, 800 and 1600 vertices. On each of these graphs, we allocated ants on half of the edges randomly. We ran the static method for 20 steps and printed the cost reduction of T. We found that 20 steps, as the next table shows, was usually sufficient to reach a result that is close to the minimum (\(MST\)). In order to test the method abilities to reduce the cost over time, we extended the run-time by performing the method for 50 steps.