WQR-UD: An online scheduling algorithm for FemtoClouds

FemtoClouds are computing platforms, implementing the Fog Computing paradigm, consisting in an ensemble of heterogeneous mobile devices whose users agree to run the tasks offloaded by other users. FemtoClouds are well suited for the execution of Bag-of-Tasks (BoTs) applications, but, being characterized by high resource heterogeneity and volatility, require the availability of scheduling techniques able to effectively deal with ensembles of independently-owned, heterogeneous devices that can suddenly leave the system. In this paper we propose WQR-UD, an online scheduling algorithm that, thanks to the combination of simple task and device selection policies (that do not require any information concerning the applications and the devices) with effective heterogeneity and volatility tolerance mechanisms, is able to effectively schedule a stream of BoT applications on FemtoCloud systems. We assess the ability of WQR-UD to meet its design goals by running an extensive simulation study for a large set of realistic operational scenarios. Our results clearly indicate that WQR-UD is able to effectively schedule a stream of BoT applications on FemtoCloud systems