Algebraic connectivity of degree constrained spanning trees for FSO networks

Free space optical (FSO) networking is an attractive technology with applications ranging from high capacity military communications to “Last-mile” broadband access solutions. Topology control is an important problem in FSO networks. The problem of building a spanning tree when number of transceivers on each base station is limited, in FSO networks, is NP-hard. What makes the problem even more challenging is to maximize the algebraic connectivity of the spanning tree. In this paper, we develop an initially configuring, or bootstrapping, algorithm which produces a degree constrained spanning tree with high algebraic connectivity and also high average edge weight, where the edge weight in the graph represents the FSO link reliability. We also develop a fast reconfiguration algorithm when one or more links fail in the FSO network. Our algorithms outperform alternative schemes in improving both algebraic connectivity and average edge weight. The robustness of the resulting topology of FSO networks is significantly improved.