Delay-optimal computation task scheduling for mobile-edge computing systems

By Juan Liu, Yuyi Mao, Jun Zhang, Khaled Ben Letaief. International Symposium on Information Theory, 2016

735 citations recorded by the source corpus.

Mobile-edge computing (MEC) emerges as a promising paradigm to improve the quality of computation experience for mobile devices. Nevertheless, the design of computation task scheduling policies for MEC systems inevitably encounters a challenging two-timescale stochastic optimization problem. Specifically, in the larger timescale, whether to execute a task locally at the mobile device or to offload a task to the MEC server for cloud computing should be decided, while in the smaller timescale, the transmission policy for the task input data should adapt to the channel side information. In this paper, we adopt a Markov decision process approach to handle this problem, where the computation tasks are scheduled based on the queueing state of the task buffer, the execution state of the local processing unit, as well as the state of the transmission unit. By analyzing the average delay of each task and the average power consumption at the mobile device, we formulate a power-constrained delay minimization problem, and propose an efficient one-dimensional search algorithm to find the optimal task scheduling policy. Simulation results are provided to demonstrate the capability of the proposed optimal stochastic task scheduling policy in achieving a shorter average execution delay compared to the baseline policies.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/a70aa20d295aa376bc229be48cf987583e71dcea

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Electrical and Electronic Engineering

Citations in the corpus

Latency Optimization for Resource Allocation in Mobile-Edge Computation Offloading (2017, background): “In [6] and [7], the authors have derived the optimal resource allocation solution for a single-user MECO system with multiple elastic tasks to minimize the average execution latency of all tasks under the transmit power constraint.”
Joint Computation and Communication Cooperation for Energy-Efficient Mobile Edge Computing (2018, background): “To characterize the most essential computation and communication tradeoff and as commonly adopted in [10]–[16], we consider that the number of CPU”
Joint offloading and computing optimization in wireless powered mobile-edge computing systems (2017, background): “For example, the authors in [2], [6], [7] investigated the energy-efﬁcient MEC design for mobile devices to minimize their energy consumption subject to the computation requirements.”
A Survey on Mobile Edge Networks: Convergence of Computing, Caching and Communications (2017, background): “In [57], a delay minimization problem is formulated under the constraint of power consumption.”
Deep reinforcement learning based computation offloading and resource allocation for MEC (2018, methodology): “The work in [8] designed the single-user delay-optimal task scheduling policies based on the theory of MDP, which controlled the states of the local processing and transmission units and the task buffer queue length based on the channel state.”
Joint Service Caching and Task Offloading for Mobile Edge Computing in Dense Networks (2018, background): “stochastic task arrivals [7], [8], energy efficiency [9], [10], [11], collaboration [12], [13], [14] etc.”
Stochastic Joint Radio and Computational Resource Management for Multi-User Mobile-Edge Computing Systems (2017, methodology): “In [23], a delay-optimal stochastic task scheduling policy for single-user MEC systems was proposed based on the Markov decision process.”
Mobile Edge Computing: A Survey on Architecture and Computation Offloading (2017, background): “Computation offloading considered in [74] (CSI stands for channel state information).”
Joint Offloading and Trajectory Design for UAV-Enabled Mobile Edge Computing Systems (2019, background): “[9] have proposed a random arrival model for data offloading in multiuser MEC systems.”
Deep Reinforcement Learning for Task Offloading in Mobile Edge Computing Systems (2020, result): “This assumption is consistent with some existing works considering queuing dynamics in an MEC system (e.g., [21]), and the incurred additional delay can be ignored if the number of time slots that a task needs to wait in the queue and to be processed (or sent) is relatively large.”
Collaborative Cloud and Edge Computing for Latency Minimization (2019, methodology): “Based on the Markov decision process approach, the optimal computation task scheduling policy for both local computing and edge computing was developed in [17].”
Edge Computing in Industrial Internet of Things: Architecture, Advances and Challenges (2020, methodology): “The best solution is to ﬁnd the optimal full data ofﬂoading scheme based on task queue information, resource utilization information of edge node, edge server and routing status information [122].”
Dynamic Computation Offloading for Mobile-Edge Computing With Energy Harvesting Devices (2016, methodology): “In addition, a delay-optimal task scheduling policy for single-user MEC systems was developed in [16], and a gametheoretic decentralized computation offloading algorithm was proposed for multi-user mobile cloud computing systems in [17].”
A Survey on Mobile Edge Computing: The Communication Perspective (2017, methodology): “Assuming that concurrent local and edge executions are feasible, the latency-optimal task scheduling policies were designed in [102] based on the theory of Markov decision process (MDP), which controls the states”
A Survey on End-Edge-Cloud Orchestrated Network Computing Paradigms (2019, background): “In Reference [86], the authors consider the computation offloading problem in an MEC system comprising an MD and an MEC server.”
EMM: Energy-Aware Mobility Management for Mobile Edge Computing in Ultra Dense Networks (2017, methodology): “For a single-user MEC system, an energy-optimal binary offloading policy is proposed in [8] by comparing the energy consumption of local execution and offloading, while a delay-optimal task scheduling policy with random task arrivals is proposed in [9].”
Optimized Computation Offloading Performance in Virtual Edge Computing Systems Via Deep Reinforcement Learning (2018, positive): “[17] formulated the problem of delay-optimal computation task offloading under a Markov decision process (MDP) framework and developed an efficient 1-D search algorithm to find the optimal solution.”
Edge of Things: The Big Picture on the Integration of Edge, IoT and the Cloud in a Distributed Computing Environment (2018, background): “[25] proposed a Markov decision process for the task scheduling policy in MEC systems.”