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, we address the problems of access point provisioning in congested hot spots and multi-hop mesh networks. We argue that both problems are closely related and show that they are NP-Complete. We 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. With uniform and skewed distribution of end-hosts, a small addition to the minimum budget required gave benefits of upto 65% and 85% respectively.