Algorithms for Data Sharing-Aware Task Allocation in Edge Computing Systems

Edge computing has been developed as a low-latency data driven computation paradigm close to the end user to maximize profit, and/or minimize energy consumption. Edge computing allows each user’s task to analyze locally-acquired sensor data at the edge to reduce the resource congestion and improve the efficiency of data processing. To reduce application latency and data transferred to edge servers it is essential to consider data sharing for some user tasks that operate on the same data items. In this article, we formulate the data sharing-aware allocation problem which has as objectives the maximization of profit and minimization of network traffic by considering data-sharing characteristics of tasks on servers. Because the problem is <inline-formula><tex-math notation="LaTeX">${\sf NP-hard}$</tex-math></inline-formula>, we design the <inline-formula><tex-math notation="LaTeX">${\sf DSTA}$</tex-math></inline-formula> algorithm to find a feasible solution in polynomial time. We investigate the approximation guarantees of <inline-formula><tex-math notation="LaTeX">${\sf DSTA}$</tex-math></inline-formula> by determining the approximation ratios with respect to the total profit and the amount of total data traffic in the edge network. We also design a variant of <inline-formula><tex-math notation="LaTeX">${\sf DSTA}$</tex-math></inline-formula>, called <inline-formula><tex-math notation="LaTeX">${\sf DSTAR}$</tex-math></inline-formula> that uses a smart rearrangement of tasks to allocate some of the unallocated tasks for increased total profit. We perform extensive experiments to investigate the performance of <inline-formula><tex-math notation="LaTeX">${\sf DSTA}$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">${\sf DSTAR}$</tex-math></inline-formula>, and compare them with a representative greedy baseline that only maximizes profit. Our experimental analysis shows that, compared to the baseline, <inline-formula><tex-math notation="LaTeX">${\sf DSTA}$</tex-math></inline-formula> reduces the total data traffic in the edge network by up to 20% across 45 case study instances at a small profit loss. In addition, <inline-formula><tex-math notation="LaTeX">${\sf DSTAR}$</tex-math></inline-formula> increases the total profit by up to 27% and the number of allocated tasks by 25% compared to <inline-formula><tex-math notation="LaTeX">${\sf DSTA}$</tex-math></inline-formula>, all while limiting the increase of total data traffic in the network.