A Hybrid Grouping Genetic Algorithm for citywide ubiquitous WiFi access deployment

In this paper we describe the application of a Hybrid Grouping Genetic Algorithm (HGGA) to the recent challenge of deploying metropolitan wireless networks, exploiting existing broadband infrastructure, by opening WiFi-enabled customers´ DSL routers to third parties, or WiFi network Design Problem or WiFiDP. The application of a HGGA to this problem aims to produce the layout of a cost effective network deployment plan, considering real life aspects such as budget and DSL router characteristics (coverage, DSL capacity at a specific location, unit price, etc.) The total cost of deployment (i.e. the cost of opening all selected DSL routers for public use) should not exceed the allocated budget. The hybrid grouping genetic algorithm proposed includes a specific encoding to tackle the WiFiDP, in which the group part also includes the type of router to be installed. Moreover, a repairing and local search procedures are included in the algorithm to obtain better performance and always finding feasible solutions. The performance and effectiveness of the proposed HGGA is evaluated using two randomly generated WiFiDP instances (considering 1000 and 2000 users) that were used to perform several experiments. From theses datasets, we compare the results of the proposed HGGA with that of a greedy optimization algorithm previously proposed to solve the WiFiDP challenge.