Query: mobile edge computing with inter-user task dependency

title: Optimal Task Offloading and Resource Allocation in Mobile Edge Computing With Inter User Task Dependency
abstract: Mobile edge computing (MEC) has recently emerged as a cost effective paradigm to enhance the computing capability of hardware constrained wireless devices (WDs) In this paper, we first consider a two user MEC network, where each WD has a sequence of tasks to execute. In particular, we consider task dependency between the two WDs, where the input of a task at one WD requires the final task output at the other WD. Under the considered task dependency model, we study the optimal task offloading policy and resource allocation (e.g. on offloading transmit power and local CPU frequencies) that minimize the weighted sum of the WDs' energy consumption and task execution time. The problem is challenging due to the combinatorial nature of the offloading decisions among all tasks and the strong coupling with resource allocation. To tackle this problem, we first assume that the offloading decisions are given and derive the closed form expressions of the optimal offloading transmit power and local CPU frequencies. Then, an efficient bi section search method is proposed to obtain the optimal solutions. Furthermore, we prove that the optimal offloading decisions follow an one climb policy, based on which a reduced complexity Gibbs Sampling algorithm is proposed to obtain the optimal offloading decisions. We then extend the investigation to a general multi user scenario, where the input of a task at one WD requires the final task outputs from multiple other WDs. Numerical results show that the proposed method can significantly outperform the other representative benchmarks and efficiently achieve low complexity with respect to the call graph size.

title: Optimal Offloading and Resource Allocation in Mobile Edge Computing with Inter User Task Dependency
abstract: In this paper, we consider a two user mobile edge computing (MEC) network, where each wireless device (WD) has a sequence of tasks to execute. In particular, we consider task dependency between the two WDs, where the input of a task at one WD requires the final task output at the other WD. Under the considered task dependency model, we study the optimal task offloading policy and resource allocation (on offloading transmit power and local CPU frequencies) that minimize the weighted sum of the WDs' energy consumption and execution time. The problem is challenging due to the combinatorial nature of the offloading decision among all tasks and the strong coupling with resource allocation among subsequent tasks. When the offloading decision is given, we obtain the closed form expressions of the offloading transmit power and local CPU frequencies and propose an efficient method to obtain the optimal solutions. Furthermore, we prove that the optimal offloading decision follows an one climb policy, based on which a reduced complexity algorithm is proposed to obtain the optimal offloading decision in polynomial time. Numerical results validate the effectiveness of our proposed methods.

title: Dependency Aware Dynamic Task Scheduling in Mobile Edge Computing
abstract: With the popularity and development of the Internet of things (IoT) human life has been deeply affected. Because of the limitations of computation capability and battery capacity, it is difficult for IoT devices to support frequent and complex computing. Motivated by this challenge, many works attempt to upload tasks of IoT devices to the cloud center for computation. However, because of the limitation of distance and bandwidth, cloud computing is difficult to guarantee low latency. As a feasible solution, Mobile Edge Computing (MEC) has attracted more and more attention. Most existing works focus on the computation offloading strategy, while the task scheduling on edge servers is not studied in depth. The tasks uploaded by IoT devices are dynamic and random, and there are dependencies between these tasks. Therefore, it is difficult for edge servers to find a task scheduling scheme to minimize the task execution delay. In this paper, to solve the task scheduling problem of edge server in multi server and multi user MEC system, we propose a heuristic algorithm based on the following three scenarios: 1) Tasks uploaded by IoT devices is dynamic and uncertain. 2) There are dependencies between tasks. 3) The computation capability of the edge server is limited. Experimental results show that the proposed algorithm can significantly reduce the overall completion time of tasks and the average task execution delay in the edge server.

title: Task Scheduling for Mobile Edge Computing Using Genetic Algorithm and Conflict Graphs
abstract: In this paper, we consider parallel and sequential task offloading to multiple mobile edge computing servers. The task consists of a set of inter dependent sub tasks, which are scheduled to servers to minimize both offloading latency and failure probability. Two algorithms are proposed to solve the scheduling problem, which are based on genetic algorithm and conflict graph models, respectively. Simulation results show that these algorithms provide performance close to the optimal solution, which is obtained through exhaustive search. Furthermore, although parallel offloading uses orthogonal channels, results demonstrate that the sequential offloading yields a reduced offloading failure probability when compared to the parallel offloading. On the other hand, parallel offloading provides less latency. However, as the dependency among sub tasks increases, the latency gap between parallel and sequential schemes decreases.

title: Joint Task Offloading and Allocation of Communication and Computation Resources for Energy Efficient Mobile Edge Computing with Sequential Task Dependency
abstract: In this paper, we investigate a mobile edge computing (MEC) system with its computation task subjected to sequential task dependency, which is critical for video stream processing and intelligent MEC applications. To minimize energy consumption per mobile device while limiting task processing delay, task offloading strategy, communication resource, and computation resource are optimized jointly under both slow and fast fading channels. In slow fading channels, an optimization problem is formulated, which is mixed integer and non convex. To solve this challenging problem, we decompose it as a one dimensional search of task offloading decision problem and a non convex optimization problem with task offloading decision given. Through mathematical manipulations, the non convex problem is transformed to be a convex one, which is shown to be solvable only with the simple Golden search method. In fast fading channels, optimal online policy depending on instant channel state is derived. In addition, it is proved that the derived policy will converge to be offline when channel coherence time is low, which can help to save extra computation complexity. Numerical results verify the correctness of our analysis and the effectiveness of our proposed strategies over existing methods.

title: Energy Efficient Task Offloading and Resource Allocation in Mobile Edge Computing with Sequential Task Dependency
abstract: In this paper, we investigate the computation task with its sub tasks subjected to sequential dependency for a mobile edge computing (MEC) system, under both slow fading channel and fast fading channel. To minimize mobile device's energy consumption while limiting task processing delay, offloading strategy (which decides to offload since which sub task) communication resource (in terms of transmit power in every fading block) and computation resource (in terms of CPU frequency for local computing) are optimized jointly. In slow fading channel, channel state always keeps stable. With offloading decision given, the optimization of the rest variables is non convex but is transformed to be convex. Golden search method is only required to find the optimal solution by decomposing the investigated problem into two levels. Then the optimal offloading decision can be easily selected. In fast fading channel, channel state may fluctuate even when offloading data. Online policy depending on instant channel state is desired and the optimal solution is derived. In addition, it is proved the derived online policy will converge to an offline policy when channel coherence time is short enough, which can help to save computation complexity. Numerical results verify the effectiveness and correctness of our proposed strategies and analysis.

title: Energy efficient Task Offloading for Relay Aided Mobile Edge Computing under Sequential Task Dependency
abstract: In this paper, we study a mobile edge computing (MEC) system in which the mobile device is assisted by a base station (BS) and a relay node. The mobile device has sequential tasks to complete, whereas the relay assists the mobile device on both task offloading and task computation. In specific, two cases are investigated, which are 1) the relay has no tasks to complete itself, and 2) the relay has tasks to complete itself. Our target is to minimize the total energy consumption of the mobile device and the relay through optimizing the transmit duration in task offloading, CPU frequency in task computing along with the task index to offload in the sequential tasks. In the first case, we decompose the mixed integer non convex problem into two levels. In the lower level problem, thanks to the convexity, Karush Kuhn Tucker (KKT) conditions are utilized to simplify the problem, which is then solved with bisection search. In the upper level problem, to find solution of the task index to offload, rather than utilizing traversal method, we develop a monotonic condition to simplify the searching process. In the second case, in order to guarantee the successful computation of the mobile device and relay, the uploading transmission is classified into three schemes. Within each scheme, the non convex problem is decomposed. In the lower level problem, semi closed solution is found by KKT conditions. In the upper level problem, traversal method is applied to find the optimal offloading index. Index Terms Mobile edge computing (MEC) sequential tasks, relay communications, resource allocation for communication and computation. X. Li, R. Fan, and H. Hu are with the School of Information and Electronics, Beijing Institute of Technology, Beijing 100081, P. R. China.

title: Offloading and Resource Allocation With General Task Graph in Mobile Edge Computing: A Deep Reinforcement Learning Approach
abstract: In this paper, we consider a mobile edge computing (MEC) system, where an access point (AP) assists a mobile device (MD) to execute an application consisting of multiple tasks following a general task call graph. The objective is to jointly determine the offloading decision of each task and the resource allocation (e.g. CPU computing power) under time varying wireless fading channels and stochastic edge computing capability, so that the energy time cost (ETC) of the MD is minimized. Solving the problem is particularly hard due to the combinatorial offloading decisions and the strong coupling among task executions under the general dependency model. Conventional numerical optimization methods are inefficient to solve such a problem, especially when the problem size is large. To address the issue, we propose a deep reinforcement learning (DRL) framework based on the actor critic learning structure. In particular, the actor network utilizes a DNN to learn the optimal mapping from the input states (i.e. wireless channel gains and edge CPU frequency) to the binary offloading decision of each task. Meanwhile, by analyzing the structure of the optimal solution, we derive a low complexity algorithm for the critic network to quickly evaluate the ETC performance of the offloading decisions output by the actor network. With the low complexity critic network, we can quickly select the best offloading action and subsequently store the state action pair in an experience replay memory as the training dataset to continuously improve the action generation DNN. To further reduce the complexity, we show that the optimal offloading decision exhibits an one climb structure, which can be utilized to significantly reduce the search space of action generation. Numerical results show that for various types of task graphs, the proposed algorithm achieves up to 99.1% of the optimal performance while significantly reducing the computational complexity compared to the existing optimization methods.

title: Deep Reinforcement Learning Based Offloading for Mobile Edge Computing with General Task Graph
abstract: In this paper, we consider a mobile edge computing (MEC) system, where an access point (AP) assists a mobile device (MD) to execute an application consisting of multiple tasks following a general task call graph. The objective is to jointly determine the offloading decision of each task and the resource allocation (e.g. CPU computing power) under time varying wireless fading channels and stochastic edge computing capability, so that the energy time cost (ETC) of the MD is minimized. Solving the problem is particularly hard due to the combinatorial offloading decisions and the strong coupling among task executions under the general dependency model. To address the issue, we propose a deep reinforcement learning (DRL) framework based on the actor critic learning structure. In particular, the actor network utilizes a deep neural network (DNN) to learn the optimal mapping from the input states (i.e. wireless channel gains and edge CPU frequency) to the binary offloading decision of each task. Meanwhile, for the critic network, we show that given the offloading decision, the remaining resource allocation problem becomes convex, where we can quickly evaluate the ETC performance of the offloading decisions output by the actor network. Accordingly, we select the best offloading action and store the state action pair in an experience replay memory as the training dataset to continuously improve the action generation DNN. Numerical results show that for various types of task graphs, the proposed algorithm achieves up to 99.5% of the optimal performance while significantly reducing the computational complexity compared to the existing optimization methods.

title: Dependency Aware Task Scheduling in Vehicular Edge Computing
abstract: Vehicular edge computing (VEC) offers a new paradigm to improve vehicular services and augment the capabilities of vehicles. In this article, we study the problem of task scheduling in VEC, where multiple computation intensive vehicular applications can be offloaded to roadside units (RSUs) and each application can be further divided into multiple tasks with task dependency. The tasks can be scheduled to different mobile edge computing servers on RSUs for execution to minimize the average completion time of multiple applications. Considering the completion time constraint of each application and the processing dependency of multiple tasks belonging to the same application, we formulate the multiple tasks scheduling problem as an optimization problem that is NP hard. To solve the optimization problem, we develop an efficient task scheduling algorithm. The basic idea is to prioritize multiple applications and prioritize multiple tasks so as to guarantee the completion time constraints of applications and the processing dependency requirements of tasks. The numerical results demonstrate that our proposed algorithm can significantly reduce the average completion time of multiple applications compared with benchmark algorithms.