Exploiting Overlap for Provisioning of Access Points in Wireless Networks
802.11 - based wireless LANs have become commonplace in home and office environments. In this paper, the authors address the problems of access point provisioning in congested hot spots and multi-hop mesh networks. They argue that both problems are closely related and show that they are NP Complete. They propose a single greedy heuristic that exploits the notion of overlapping placement of access points to address both problems. A LP relaxation approach is also proposed to solve the provisioning problem in congested hotspots. An experimental evaluation using synthetic user distributions and a real office environment shows that exploiting overlap and the presence of multiple channels can be an effective approach for alleviating hotspots and extending coverage.