S~2U: 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 - S~2U 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 S~2U 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 S~2U algorithm and its approximation ratio to the optimal solution. Furthermore, we present extensive numerical results to compare the proposed S~2U algorithm with the main existing methods. It is shown that S~2U 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 S~2U algorithm and the optimal results is within 5% in average.