Exploiting Statistical Mobility Models for Efficient WiFi Deployment

Recent years have witnessed the emergence of numerous new Internet services for mobile users. Supporting mobile applications via public WiFi networks has received significant research attention. Nevertheless, recent empirical studies showed that unplanned WiFi networks cannot provide satisfactory Quality of Service for interactive mobile applications due to intermittent network connectivity. In this paper, we exploit statistical mobility characteristics of users to deploy WiFi Access Points (APs) for continuous service for mobile users. We study two AP deployment problems that aim to maximize the continuous user coverage and to minimize the AP deployment cost, respectively. Both problems are formulated based on mobility graphs that capture the statistical mobility patterns of users. We prove that not only both problems are NP-complete but also they are identical to each other. We develop several optimal and approximation algorithms for different topologies of mobility graphs.We prove that our approximation algorithms generate the result that is at least 1 2 of the optimal solution. The effectiveness of our approaches is validated by extensive simulations using real user mobility traces.