Alpha Coverage: Scalable Intermittent Coverage for Mobile Users

Vehicular Internet access via open WLAN access points (AP) 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 worst-case 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 (full coverage) is not very practical due to the prohibitive deployment and operational cost. We have introduced a new notion of intermittent coverage for mobile users, called alpha-coverage, which provides worst-case guarantees on the interconnection gap while using significantly fewer APs than full coverage. We have proposed efficient algorithms to verify whether a given deployment provides alpha-coverage and approximation algorithms for determining a deployment of APs that will provide alpha-coverage. Our algorithms can also be used to supplement open WLAN APs in a region with appropriate number of additional APs that will provide worst-case guarantees on the interconnection gap.

Most Relevant Papers