Opportunistic Mobile Data Offloading with Deadline Constraints

Due to the explosive proliferation of mobile cloud computing applications, much data needs to be transmitted between mobile users and clouds, incurring a huge traffic demand on cellular networks. Mobile offloading is a promising approach to address this challenge. In this paper, we focus on the problem of offloading many deadline-sensitive data items to some WiFi networks with capacity constraints; that is, how to schedule each data item to the WiFi networks, so that we can offload as many data items before their deadlines as possible, while taking the constraints of transmission capacity into consideration. This problem involves a probabilistic combination of multiple 0-1 knapsack constraints, which differs from existing problems. To solve this problem, we propose a greedy oFfline Data Offloading (FDO) algorithm, achieving an approximation ratio of 2. Also, we propose an oNline Data Offloading (NDO) algorithm, which has a competitive ratio of 2. Additionally, we extend our problem to a more general scenario where WiFi transmission costs are heterogeneous. We design a Heterogeneous Data Offloading (HDO) algorithm to solve the extended problem, and give its performance analysis. Finally, we demonstrate the significant performances of our algorithms through extensive simulations based on some real-world and synthetic WiFi datasets.