Dependent Task Offloading in Edge Computing Using GNN and Deep Reinforcement Learning

Zequn Cao, Xiaoheng Deng, Sheng Yue, Ping Jiang, Ju Ren, Jinsong GuiIEEE Internet of Things Journal 2024 · DOI

TL;DR

This paper tackles the complex problem of dependent task offloading (DTO) in edge computing, where tasks are broken down into subtasks with interdependencies. They propose a novel Graph Attention Network (GAT) and Deep Reinforcement Learning (DRL) based approach (DTODRL) to minimize task completion time in multi-user, multi-edge environments, outperforming existing methods.

What Problem Does This Paper Address?

The increasing prevalence of the Internet of Everything (IoE) has led to a surge in data and computation demands that traditional cloud computing struggles to meet due to latency and reliability concerns. Mobile Edge Computing (MEC) offers a solution by deploying computing resources closer to users. A key challenge in MEC is task offloading, where tasks are moved from user devices to edge servers. While existing approaches often assume tasks are independent or can be split arbitrarily, real-world applications often consist of subtasks with logical dependencies, forming a Directed Acyclic Graph (DAG). This dependency structure makes simple offloading strategies inefficient and can lead to suboptimal performance. This paper addresses the "Dependent Task Offloading" (DTO) problem, aiming to schedule these dependent subtasks across multiple users and edge servers to minimize the overall task completion time (makespan).

Methods

The core of the proposed solution, DTODRL, combines two powerful techniques:

  • Graph Attention Network (GAT): To effectively capture the complex dependencies and features within the DAG representation of tasks, GAT is employed. This allows the model to understand the relationships between subtasks. Crucially, the GAT encoder is pre-trained in an unsupervised manner on a resourceful cloud. This pre-training decouples the computationally intensive graph representation learning from the real-time scheduling process on the edge, leading to faster and more stable DRL training.
  • Deep Reinforcement Learning (DRL) with Proximal Policy Optimization (PPO): DRL is used to learn an optimal offloading policy. PPO is chosen for its sample efficiency, stable training, and ability to avoid local optima. The DTODRL designs a comprehensive state space that includes task graph information (encoded by GAT) and available offloading location profiles. It also introduces a multi-dimensional action space to handle the selection of both the dependent task node and its offloading location. The reward function is designed to directly minimize the average finish time of all tasks.

Datasets

The paper does not explicitly mention using pre-existing public datasets. Instead, they generate synthetic data using a DAG generator described in prior work ([5], [45]). This generator allows for the creation of various graph structures with parameters controlling node count, out-degree, shape, and regularity, enabling comprehensive testing across different scenarios.

Key Insights and Ideas

  • DAGs are Crucial for Realistic Task Offloading: The paper highlights that ignoring task dependencies (represented by DAGs) leads to suboptimal offloading decisions, a gap not fully addressed by prior work.
  • Unsupervised GAT Pre-training for Efficiency: Pre-training the GAT encoder in the cloud is a smart strategy. It offloads the heavy computation and data requirements of graph representation learning, making the edge-side DRL scheduler more efficient and responsive.
  • Multi-Dimensional Action Space for Granular Control: The proposed action space, which selects both a node and its location, provides the necessary granularity to manage dependent tasks effectively.
  • DTODRL Adapts to Complexity: The DTODRL demonstrates robustness and adaptability across both simple and complex MEC environments, outperforming baseline methods.

Key Results

The DTODRL consistently outperforms baseline methods (Local, Random, Round-Robin, and HEFT) in terms of reducing the mean Average Finish Time (AFT) of tasks.

  • In single-user, single-edge scenarios, DTODRL approaches optimal solutions, especially for smaller DAGs.
  • In multi-user, multi-edge scenarios, DTODRL shows significant improvements, particularly as the number of users and edge servers increases. For instance, in Figure 7, DTODRL consistently achieves the lowest mean AFT across various DAG sizes and user counts.
  • The paper demonstrates that DTODRL is effective even with a limited number of edge servers, showcasing its ability to optimize resource utilization.

Limitations and Future Work

  • Energy Consumption Not Explicitly Optimized: While the paper suggests that minimizing makespan indirectly reduces energy consumption, it doesn't explicitly optimize for energy efficiency.
  • Focus on Makespan: The primary optimization goal is task completion time (makespan). Future work could explore other optimization objectives.
  • Future Directions: The authors propose extending their work to investigate more powerful graph-based encoders, explore other optimization goals like energy consumption, and consider stricter resource constraints (e.g., memory, storage, service caching). They also aim to further investigate the impact of data quality and reliability.

Summary updated

BibTeX
@article{cao2024dependent,
  author = {Zequn Cao and Xiaoheng Deng and Sheng Yue and Ping Jiang and Ju Ren and Jinsong Gui},
  title = {{Dependent Task Offloading in Edge Computing Using GNN and Deep Reinforcement Learning}},
  journal = {IEEE Internet of Things Journal},
  year = {2024},
  doi = {10.1109/jiot.2024.3374969},
}
Figure