Task partitioning and offloading in collaborative edge computing environments

Abstract

In the past decade, edge computing has become popular as it pushes the computation and data storage closer to data sources to address issues with cloud computing such as privacy, network congestion, latency, etc. Collaborative edge computing (CEC) is a new paradigm of edge computing, where multiple stakeholders (IoT devices, edge devices, cloud, or end-users) collaborate with each other by sharing data and computation resources to satisfy individual and/or global goals. One of the fundamental issues in CEC is partitioning and offloading the tasks among heterogeneous edge devices. However, they are difficult problems to solve due to two unique features of CEC: 1) the data required for a task are from multiple edge devices, and 2) tasks can be offloaded to an edge device at a multi-hop distance due to heterogeneity among edge device resources. The transfer of data to an edge device at a multi-hop distance leads to contention among network flows. This makes it difficult to estimate the communication cost of transmitting data as the network link could be occupied by another network flow. This thesis studies the task partitioning and offloading problems in CEC considering different application models. We mathematically formulate the problems, design algorithm to solve the problems, and conduct extensive simulation experiments to evaluate the proposed solutions. This thesis makes four main contributions. 1) Propose a framework named Edge Mesh as an abstraction of CEC for our study. Edge Mesh distributes decision-making within the network by sharing data and computation resources among mesh network of edge devices. We describe the functionalities, research framework, and the main principles for designing Edge Mesh and its functions. 2) Solve the problem of data-aware task allocation in CEC, where we consider both the placement and transmission of data to make task allocation decision. Compared to the traditional problem, the input data for each dependent task is distributed at different edge devices leading to contended network flows. We jointly formulate the task allocation (start time and device for each task) and network flow scheduling (start time of flow) problem. We propose a multi-stage greedy algorithm (MSGA) that solves the problem by jointly considering the placement of tasks and adjustment of network flows. 3) Solve the problem of multi-hop offloading of multiple DAG tasks in CEC. This problem jointly makes a decision of offloading dependent subtasks within each DAG task and scheduling network flows that are generated to transfer data between dependent subtasks. We propose a joint dependent task offloading and flow scheduling heuristic (JDOFH) that solves the problem by leveraging the knowledge of all tasks and start time of network flows. 4) Solve the problem of multi-hop multi-task partial offloading in CEC. Each independent task is partitioned into two parts, i.e. local and remote, where the remote part can be offloaded to an edge device at multi-hop distance. We address the challenging issue of dependency among different variables, including partial offloading ratio, the remote device for each task, start time of the task, and start time of flows. We propose a joint partial offloading and flow scheduling heuristic (JPOFH) that decides partial offloading ratio by considering both waiting times at the devices and start time of input data flows. In summary, this thesis systematically investigates the requirements and solves the task partitioning and offloading problems in CEC. The proposed solutions address the issues resulting from distributed data sources and multi-hop task offloading in CEC. We also outline future directions, including distributed solutions for dynamic task partitioning and offloading, real-world prototype, integration with blockchain, 5G, etc.