Approximated Assignment Algorithms for Unordered and Ordered Tasks in Data Shared MEC Systems

The appearance of Mobile Edge Computing (MEC) successfully solves the bottlenecks of traditional Cloud based networks. Since mobile edges, e.g., base stations, and mobile devices have certain data processing capabilities, it is not necessary to offload all the tasks to the cloud for handling. Therefore, it is quite important to decide the optimal task assignment in MEC systems, and a series of algorithms have been proposed. However, the existing algorithms ignored the data distribution during task assignment, so that their applied ranges are quite limit. Considering the data sharing is quite important in a MEC system, this paper studies task assignment algorithms in Data Shared Mobile Edge Computing Systems in detail. Specifically, three algorithms are proposed to deal with the unordered and ordered holistic tasks respectively. Meanwhile, the situation that the tasks are divisible is also considered, and two algorithms for rearranging the divisible tasks are proposed for different optimization goals. The hardness of the problem, the correctness, complexities, and ratio bounds of the proposed algorithms are analyzed theoretically. Finally, extensive experimental results are carried out. Both theoretical analysis and experiment results show that all the proposed algorithms have high performance in terms of latency, satisfied rate, and energy consumption.

1 Introduction

WITH the development of IoT techniques and the proliferation of smart mobile devices, wireless applications become increasingly complicated, such as intelligent manufacture, driverless vehicles and smart health care, etc. Meanwhile, the QoS (Quality of Service) requirements by applications, including response delay, computation accuracy, congestion control, and energy conservation etc., become much stricter than before. Such requirements cannot be satisfied well in traditional Cloud based networks, where all data are transmitted to the Cloud for processing. Furthermore, the data collected by current IoT devices manifest an explosive growth, so that it is also not practical to transmit all data to the Cloud.