S2U: An efficient algorithm for optimal integrated points placement in hybrid optical-wireless access networks

Integration of optical and wireless networks is considered as one of the promising technologies for next generation Internet access. In this paper, we consider the integrated points placement problem in the hybrid optical-wireless system for optimal resource utilization under the given constraints including hop count, cluster size, and relay load. While the optimization formulation is an NP-hard problem in general, we propose a polynomial-time heuristic algorithm – S2U algorithm to obtain the near-optimal solution that minimizes the number of integrated points required to support all wireless BSs residing in the wireless part of the integrated system. In contrast to the existing work, our S2U algorithm forms the clusters starting from the network edge towards its center and the construction of clusters is not only based on the greedy idea but also considers load balancing. We present a theoretical analysis of the complexity of the proposed S2U algorithm and its approximation ratio to the optimal solution. Furthermore, we present extensive numerical results to compare the proposed S2U algorithm with the main existing methods. It is shown that S2U can not only cover a network with a smaller number of integrated points, but also achieve better network performance in terms of the average transmission delay (average hop count) and load balance. In addition, we compare our results with the optimal solution obtained via CPLEX in terms of the minimum number of integrated points. The results show that the gap between the results obtained from our S2U algorithm and the optimal results is within 5% in average.