Randomized Cost Analysis for Non-Clairvoyant Task Offloading in Edge Computing

Most of the previous research on task offloading in mobile edge computing has focused on clairvoyant task scheduling, which assumes that the characteristics of the tasks are known apriori. This assumption is unrealistic for many practical scenarios with randomly generated tasks in mobile edge computing. In this article, a randomized cost analysis of task offloading in mobile edge computing environment is done, where the characteristics of tasks are not known. The aim is to co-optimize the overall completion time and cost for executing a set of tasks. Task being executed may request some of the predefined services from cloud/edge devices. It is quite a challenge to ensure the quality of experience of end user and service provider in terms of time and cost due to the uncertain and diverse task characteristics. In order to tackle this problem, an efficient randomized task offloading model is formulated to reduce the overall execution time and cost. To this end, we present two service unaware and two service aware algorithms, namely SUN-BS, SUN-TS, SAN-BS and SAN-TS using randomized stochastic and randomized probabilistic approaches that provides near optimal solution. We further perform complexity analysis to show the theoretical upper bounds for makespan and total cost with certain performance guarantee. Numerical simulation experiments are conducted to demonstrate the performance improvement of proposed algorithms SUN-BS (54%-68%) in term of makespan and SAN-TS (7%-20%) in terms of cost over the traditional scheduling algorithms.