Deadline-Sensitive Mobile Data Offloading via Opportunistic Communications

With the explosive proliferation of smartphones, many mobile cloud computing applications have emerged in recent years. These applications generally involve many data transmissions between mobile users and the cloud side. In order to reduce the monetary cost of these data transmissions, an effective approach is to offload partial data traffic from cellular networks to WiFi networks, when mobile users pass by some WiFi Access Points (APs). In this paper, we focus on the problem of offloading many deadline-sensitive data items to some WiFi APs with capacity constraints; that is, how to schedule each data item to the WiFi APs, 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, and prove that this algorithm can achieve an approximation ratio of 2. Moreover, we extend our data offloading strategy to the online decision case, and propose an oNline Data Offloading (NDO) algorithm, which has a competitive ratio of 2. Finally, we demonstrate the significant performances of our algorithms through extensive simulations.