Online scheduling for delayed mobile offloading

WiFi offloading, where mobile users opportunistically obtain data through WiFi rather than through cellular networks, is a promising technique to greatly improve 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 the movements of users are unpredictable, we focus on online scheduling policy where APs do not have any knowledge about the users' mobility patterns. We study performance of online policies by comparing 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 that can offload (e-1)/e as much data as the offline policy. We further study the case where the service provider can increase the capacity of WiFi so as to provide guarantees on the amount of offloaded data. We propose a simple online policy and prove that our policy only needs half as much capacity as current mechanism to provide the same performance guarantee.