Sparse WiFi Deployment for Vehicular Internet Access With Bounded Interconnection Gap

Vehicular Internet access via open WiFi access points (APs) has been demonstrated to be a feasible solution to provide opportunistic data service to moving vehicles. Using an in situ deployment, however, such a solution does not provide performance guarantees due to unpredictable intermittent connectivity. On the other hand, a solution that tries to cover every point in an entire road network with APs (a full coverage) is not very practical due to prohibitive deployment and operational costs. In this paper, we introduce a new notion of intermittent coverage for mobile users, called Alpha Coverage, which provides worst-case guarantees on the interconnection gap, i.e., the distance or expected delay between two consecutive mobile-AP contacts for a vehicle, while using significantly fewer APs than needed for full coverage. We propose efficient algorithms to verify whether a given deployment provides Alpha Coverage. The problem of finding an economic deployment that provides alpha-coverage turns out to be NP-hard. We hence provide both approximation algorithms that have provable guarantees on the performance as well as efficient heuristics that perform well in practice. The efficiency of our algorithms is demonstrated via simulations using data from real-world road networks.