| We consider one challenging problem in establishing a Free Space Optical (FSO) network. In our model, it is assumed that each node is a base station and its number of transceivers is limited. Such a network can be abstracted by a graph where each node represents a base station and each edge represents a link connecting two base stations. The problem is that of forming a connected topology, which is known to be NP-complete because of the transceiver limitation. What makes this problem even more challenging is the need to have a "distributed" solution to form a connected topology, because a node can have knowledge only of its neighbors. We have developed a fully distributed approximation algorithm, which constructs a spanning tree with maximal node degree at most one larger than that in the optimal solution. Due to its distributed nature, this algorithm outperforms serial algorithms. |
