A Robust Formulation for Efficient Application Offloading to Clouds

摘要

Application offloading to clouds is the key enabler for compute-intensive applications running on mobile devices. An offloading algorithm employs estimated averages of the execution and communication costs of application modules to decide on a modules subset to be offloaded with the objective of minimizing a certain metric (e.g., execution time or energy). This decision is highly affected by the inherent uncertainty arising from the estimated cost averages due to natural fluctuations or measurement inaccuracies. In this article, we propose a novel offloading scheme that takes into consideration these uncertainties. The proposed work first formulates the offloading problem as a tractable robust optimization one where the uncertainty in $k$ cost parameters is incorporated by allowing these parameters to fluctuate within intervals specified from profiling the application and the network. We then show that this problem can be transformed into $k+1$ binary linear programs that are solved while preserving the complexity of the original problem. In contrast to existing approaches, the performance of the obtained decision is guaranteed as long as the behavior of the uncertain parameters remains within the given intervals. Performance evaluation results using a face detection and synthetically generated applications with a large number of modules demonstrate the robustness of the obtained offloading decisions.