# Dynamic Network Formation for FSO Satellite Communication
## 1 Introduction
### Related Works  
Most research related to new space communication optimization are still addressing RF technology and often is led by commercial companies (e.g., Project Loon [1], NSLCOMM and Iridium NEXT [2]). Few new space research projects relate to laser-com: StarLink is a massive LEO constellation designed by SpaceX, and its main goal is to allow a global coverage, high-bandwidth and low latency satellite network. The Starlink backbone is based on laser-com between satellites [3], while the space-to-earth segment is based on RF communication [4]. FSO communication was suggested as an alternative to fiber optic networks and RF links [5; 6] in terrestrial and urban scenarios. NASA has an optical communications program (see [7])--in particular, a lunar laser-com demonstration (see [8])--and the MIT Node Project focuses on laser-com for nano-satellites (see [9]). The goal of these projects is, ultimately, to create a network of satellites that will provide full coverage for the ground stations scattered around the Earth. The communication between these satellites is planned to be optic-based at the end of the process. Laser communication is fast, secure and does not require a frequency license appose to RF communication. The field of FSO link optimization has been investigated in several aspects, including optimal modulation of maximizing the bandwidth [10; 11], minimizing bit error rate [12] and security concerning optical jamming [13]. In addition, space has optimal conditions for optical communication because there is no atmosphere like on Earth. Nevertheless, such a network also has limitations; point-to-point optical communication requires accurate aiming that requires time. In addition, each satellite can have a limited number of optical communication components, and each component can be linked to one satellite at a time. These restrictions imply that the network has to change from time to time to provide full coverage. Figure 1: Ground station satellite communication illustration. This Figure demonstrates communication between 2 ground stations: \(gs_{i},gs_{j}\) via 3 satellites: \(s_{1},s_{2},s_{3}\). Given the satellite infrastructure, the question arises, how to build a network that is optimal for transmitting data. This paper offers an algorithm for building such a network. The problem of networking a group of satellites that has limited components can be referred to as the Bounded-Degree Minimum Spanning Tree problem (BDMST). In the Minimum Bounded-Degree Spanning Tree problem, the goal is to find a spanning tree in a given graph \(G\) that minimizes the graph cost and the graph degree to some constant \(n\). Determine if there exists a spanning tree with maximum degree n is NP-Complete for \(n=2\)[14] since it captures the Hamilton-Path problem with cardinality n. The Minimum Bounded-Degree Spanning Tree problem has proved to be NP-hard; therefore, it appears unlikely that a polynomial time solution algorithm exists for the problem [15]. The problem was first defined by [16] who suggested a branch-and-bound algorithm to construct a Minimum Bounded-Degree Spanning Tree. This algorithm is the optimal solution for a tree with up to 100 vertices. The optimal solution for the instances with up to 200 vertices was later suggested by [PERSON] [17]. Instances with up to 500 vertices were considered in the study of [PERSON] et al. [18], which proposed a genetic algorithm that uses a direct tree representation. In this paper, we consider the case of the Starlink satellite constellation that, as of Q4 2021, consists of over 1600 operational LEO satellites and thousands more are expected in coming years. Finding optimal routing schemes in a such massive constellation is extremely demanding. However, there are some efficient heuristics methods for finding sub-optimal solutions. One of the heuristics, presented by [PERSON] and [PERSON] [19], uses a genetic algorithm. They proposed a bi-objective genetic algorithm for d-MST problem with the violation degree as the second objective.