Urban free-space optical network optimization

This paper presents a set of graph optimization problems related to free-space optical communication networks. Such laser-based wireless networks require a line of sight to enable communication, thus a visibility graph model is used herein. The main objective is to provide connectivity from a communication source point to terminal points through the use of some subset of available intermediate points. To this end, we define a handful of problems that differ mainly in the costs applied to the nodes and/or edges of the graph. These problems should be optimized with respect to cost and performance. The problems at hand are shown to be NP-hard. A generic heuristic based on a genetic algorithm is proposed, followed by a set of simulation experiments that demonstrate the performance of the suggested heuristic method on real-life scenarios. The suggested genetic algorithm is compared with the Euclidean Steiner tree method. Our simulations show that in many settings, especially in dense graphs, the genetic algorithm finds lower-cost solutions than its competitor, while it falls behind in some settings. However, the run-time performance of the genetic algorithm is considerably better in graphs with 1000 nodes or more, being more than twice faster in some settings. We conclude that the suggested heuristic improves run-time performance on large-scale graphs and can handle a wider range of related optimization problems. The simulation results suggest that the 5G urban backbone may benefit significantly from using free-space optical networks.