Near optimal citywide WiFi network deployment using a hybrid grouping genetic algorithm

摘要

This paper presents the application of a Hybrid Grouping Genetic Algorithm (HGGA) to solve the problem of deploying metropolitan wireless networks. In particular, the exploitation of the existing broadband infrastructure (e.g., ADSL networks) by “opening up” WiFi-enabled routers to third party users, is considered to produce a complex problem, henceforth call WiFi network Design Problem or WiFiDP. The application of a HGGA to this problem produces cost-effective network deployment plans, considering real life aspects such as budget (the total cost of deployment – i.e. the cost of opening all selected DSL routers for public use – should not exceed the allocated budget) and DSL router characteristics (coverage, DSL capacity at a specific location, unit price, etc.) The hybrid grouping genetic algorithm proposed incorporates a particular encoding to tackle the WiFiDP, in which the group part also includes the type of router to be installed. Also, a modification of this encoding to consider the working frequencies of routers is presented in this paper. Moreover, a repairing and local search procedures are added to the algorithm to obtain better performance and always find viable solutions. The performance and effectiveness of the proposed HGGA is evaluated using two randomly generated WiFiDP instances (considering 1000 and 2000 users), used to perform several experiments. The comparison of the proposed HGGA results against those of a greedy optimization algorithm (previously proposed to solve the WiFiDP) shows the better performance of this approach. Finally, the application of the HGGA to real datasets in the cities of Berlin (Germany) and Torrejón de Ardoz (Spain) is also reported in the experimental part. In real conditions, the HGGA keeps performing better than previous methods.