Genetic algorithms and greedy-randomized adaptive search procedure for router placement problem in wireless networks

摘要

Wireless networks are present in all the large buildings or sites, and they are expected to provide high speed Internet for the connected users. This can be achieved by connecting wireless routers to the Internet backbone through fast connection cables (e.g. fiber optics), as well finding optimal distribution of the routers along the building, so that the targeted area is covered with Internet access as much as possible, provided that the cost constraints of routers and the cost of their mutual interconnection are satisfied. Therefore, in this paper, we present two approaches for solving the problem of router placement in a two-dimensional area, where the goal is to provide optimal Internet coverage by meeting the cost constraints. Our first approach is based on Genetic Algorithms, and the second one employs the Greedy-Randomized Adaptive Search Procedure. Both approaches utilize a neighborhood exploration mechanism that consists of operators which are dealing with adding, removing, jumping and shifting routers in the target area. Furthermore, an advanced operator for intelligent shifting of routers inside a predefined neighborhood is implemented. The computational experiments, performed over a data set of four large instances, indicate that both proposed approaches can obtain competitive results to the ones that are presently available in the literature. Consequently, the results indicate that both approaches can be easily adapted for application in practice for designing the topography of wireless networks, in terms of router placement and distribution.