An Online Learning Approach to Computation Offloading in Dynamic Fog Networks

Fog computing provides computation and services to the edge of networks to support real-time applications. The latency performance is a crucial metric in fog computing. In this paper, we consider a computation offloading problem in a fog network with unknown dynamics. In this network, mobile users can offload their computational tasks to neighborhood fog nodes (FNs) in each time slot. The queue of arrival tasks at each FN follows a Markov model with unknown statistics. In order to provide satisfactory quality of experience, the network latency needs to be minimized. In this paper, we construct an offloading policy with interleaved exploration and exploitation epochs to solve the sequential FN selection problem. An upper bound of regret is derived to show the effectiveness of the proposed method. The proposed policy is optimal in the sense that it achieves a regret with sub-linear order. In addition, the proposed policy can be applied to both single-user setting and multi-user setting. Simulation results show that when compared with the existing offloading algorithms, the proposed algorithm can reduce the average latency by 7%~47% in the single-user setting, and 91% in the multi-user setting.