# Dynamic Network Formation for FSO Satellite Communication
## 2 Problem of Interest  
We start by describing a number of key logical components that are required for formally stating the problem at hand:  
* Communication link: two points (each point can represent a satellite) have a communication link if they are closer than a predefined minimum distance \(m_{d}\). Denote the distance between two satellites \(s_{i},s_{j}\) as \(d(s_{i},s_{j})\), and we define a function: \(LOS:\rightarrow\mathbb{R}^{+}\) so that: \(LOS(s_{i},s_{j})=d(s_{i},s_{j})\) if \(d<m_{d}\) and \(\infty\) otherwise. \(LOS\) stands for Line-Of-Sight. * Static Communication Graphs: a graph \(G_{c}(t)=<V,E>\) where the vertices \(V\) represent the satellites. The edges \(E\) are defined from the \(LOS\) function, meaning, between two vertices in \(V\) there is an edge if there is a \(LOS\) between them. The weight function denotes as \(W:E\rightarrow\mathbb{R}^{+}\) is defined so that \(e=v_{i},v_{j}\) and \(W(e)=distance(v_{i},v_{j})\). Note that, by definition this graph is not necessarily connected. However, in this scenario, we assume a connected graph scenario. We will justify this assumption in the upcoming sections. Figure 2 demonstrates the communication graph computation. Dynamic Communication Graphs: a dynamic graph is a graph defined in a time interval, where the edges' weights change over time. The dynamic communication graph denotes as: \(G_{d}(t)=<V,E,T>\) where the vertices \(V\) represent the satellites, and the edges \(E\) are defines by the \(LOS\) function in each point in time \(t\in T\). The weight function denotes \(W:\{E,T\}\rightarrow\mathbb{R}^{+}\) is defined so that \(e=(v_{i},v_{j})\), and \(W(e,t)\) is the distance between the vertices \((v_{i},v_{j})\) in time \(t\). Equipped with the above terms, one can describe the problem's state. The problem can be defined as how to construct an _optimal_ spanning graph that connects all the vertices in _every_ time interval. By optimal, one means the smallest sub-network where every two points (satellites) can communicate either by a direct link or through other points (point A communicates with point B via point C). If one substitutes each vertex with a communication satellite and each edge with a communication link, the motivation is both clear and important. A simpler version of this problem is well known in the literature as the Minimum Spanning Tree (or _MST_) problem [22]. As mentioned above, static graphs are graphs with static (unchanging) weights. A static _MST_ problem (_MST_ on static graphs) can be solved (\(O(nlogn)\) by applying [PERSON]'s or [PERSON]'s algorithm [23]. However, since a satellite constellation is constantly changing, one faces a _dynamic_ graph scenario where the edges' weights are changing over time, the _MST_ is susceptible to changes. Theoretically, one can treat a dynamic scenario as a consecutive static-graph problems, each can be solved using classical methods. Alas, this approach raises two important ramifications that have not been addressed thus far. Figure 2: Communication graph illustration. (**a**), The satellites constellation and (**b**) the FSO communication graph created by such a constellation. First, changing the optimal network structure (due to satellites' movements) cannot be done instantly, especially not when using optic communications. Establishing an optic connection between two satellites is a delicate procedure that takes acquisition time. Thus, the dynamic scenario forces us to consider an alternative method for graphs spanning over time. It should be noted that the actual acquisition time of an inter-satellite laser link may vary and is hardware dependent, yet even few milliseconds may cause significant delays. For a detailed analysis of the expected delays and a comparison between fiber-optics and inter-satellite laser back-hauling, see [24; 25]. The second problem has to do with the maximum number of edges each vertex is allowed to have. An optic communication between two satellites is obtained by a dedicated optic module.