WiFi offloading, where mobile users opportunistically obtain data through WiFi rather than cellular networks, is a promising technique for greatly improving spectrum efficiency and reduce cellular network congestion. We consider a system where the service provider deploys multiple WiFi hotspots to offload mobile traffic, and study the scheduling policy to maximize the amount of offloaded data. Since users' movements are unpredictable, we focus on online scheduling policy, where APs have no knowledge of users' mobility patterns. We study the performance of online policies by comparing them against the optimal offline policy. We prove that any work-conserving policy is able to offload at least half as much data as the offline policy, and then propose an online policy such that when the requested data by each user is very large, the policy can offload (e-1)/e as much data as the offline policy, where e is Euler's constant. We further study the case where the service provider can increase the capacity of WiFi so as to provide some guarantees on the amount of offloaded data. We derive a lower-bound on the trade-off between capacity and the amount of offloaded data, and propose a simple online policy that achieves this lower bound. In addition, we show that our policy only needs half as much capacity as current mechanisms to provide the same performance guarantee.
- Algorithm design and analysis
- optimal scheduling
ASJC Scopus subject areas
- Computer Science Applications
- Electrical and Electronic Engineering
- Applied Mathematics