Joint Trajectory Planning, Service Function Deploying, and DAG Task Scheduling in UAV-Empowered Edge Computing
Efficient task scheduling plays a key role in unmanned aerial vehicle (UAV)-empowered edge computing due to the limitation in energy supply and computation resource on the UAV platforms. This problem becomes much more complicated when the processing-dependent tasks that can be described as directed...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-07-01
|
| Series: | Drones |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2504-446X/7/7/443 |
| _version_ | 1797589632406257664 |
|---|---|
| author | Runa Jia Kuang Zhao Xianglin Wei Guoliang Zhang Yangang Wang Gangyi Tu |
| author_facet | Runa Jia Kuang Zhao Xianglin Wei Guoliang Zhang Yangang Wang Gangyi Tu |
| author_sort | Runa Jia |
| collection | DOAJ |
| description | Efficient task scheduling plays a key role in unmanned aerial vehicle (UAV)-empowered edge computing due to the limitation in energy supply and computation resource on the UAV platforms. This problem becomes much more complicated when the processing-dependent tasks that can be described as directed acyclic graphs (DAGs) and each of their components can only be processed on a virtual machine or container that deploys the desired service function (SF). In this paper, we first build an optimization problem that aims to minimize the completion time of all DAG tasks subject to constraints including task dependency, computation resource occupied by the UAVs, etc. To tackle this problem, a genetic algorithm-based joint deployment and scheduling algorithm, named GA-JoDeS, is put forward, since solving the established 0–1 integer programming problem in polynomial time is infeasible. Subtask offloading decision and UAV position are encoded into the chromosome in the GA-JoDeS algorithm, and the fitness value of an individual is decided by the maximum completion time of all DAG tasks. Through selection, crossover, and mutation, the GA-JoDeS algorithm evolves until it determines the individual with the optimal fitness value as the suboptimal solution to the problem. To evaluate the performance of the proposal, a series of simulations is conducted, and three traditional methods are chosen as comparison benchmarks. The results show that the GA-JoDeS algorithm can convergence quickly, and it can effectively reduce the completion time of DAG tasks with different parameter settings. |
| first_indexed | 2024-03-11T01:09:20Z |
| format | Article |
| id | doaj.art-fe3df0fafeca42f2a536a0433f77cbec |
| institution | Directory Open Access Journal |
| issn | 2504-446X |
| language | English |
| last_indexed | 2024-03-11T01:09:20Z |
| publishDate | 2023-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Drones |
| spelling | doaj.art-fe3df0fafeca42f2a536a0433f77cbec2023-11-18T19:01:07ZengMDPI AGDrones2504-446X2023-07-017744310.3390/drones7070443Joint Trajectory Planning, Service Function Deploying, and DAG Task Scheduling in UAV-Empowered Edge ComputingRuna Jia0Kuang Zhao1Xianglin Wei2Guoliang Zhang3Yangang Wang4Gangyi Tu5College of Electronics and Information Engineer, Nanjing University of Information Science and Technology, Nanjing 210044, ChinaThe Sixty-Third Research Institute, National University of Defense Technology, Nanjing 210007, ChinaThe Sixty-Third Research Institute, National University of Defense Technology, Nanjing 210007, ChinaThe Sixty-Third Research Institute, National University of Defense Technology, Nanjing 210007, ChinaThe Sixty-Third Research Institute, National University of Defense Technology, Nanjing 210007, ChinaCollege of Electronics and Information Engineer, Nanjing University of Information Science and Technology, Nanjing 210044, ChinaEfficient task scheduling plays a key role in unmanned aerial vehicle (UAV)-empowered edge computing due to the limitation in energy supply and computation resource on the UAV platforms. This problem becomes much more complicated when the processing-dependent tasks that can be described as directed acyclic graphs (DAGs) and each of their components can only be processed on a virtual machine or container that deploys the desired service function (SF). In this paper, we first build an optimization problem that aims to minimize the completion time of all DAG tasks subject to constraints including task dependency, computation resource occupied by the UAVs, etc. To tackle this problem, a genetic algorithm-based joint deployment and scheduling algorithm, named GA-JoDeS, is put forward, since solving the established 0–1 integer programming problem in polynomial time is infeasible. Subtask offloading decision and UAV position are encoded into the chromosome in the GA-JoDeS algorithm, and the fitness value of an individual is decided by the maximum completion time of all DAG tasks. Through selection, crossover, and mutation, the GA-JoDeS algorithm evolves until it determines the individual with the optimal fitness value as the suboptimal solution to the problem. To evaluate the performance of the proposal, a series of simulations is conducted, and three traditional methods are chosen as comparison benchmarks. The results show that the GA-JoDeS algorithm can convergence quickly, and it can effectively reduce the completion time of DAG tasks with different parameter settings.https://www.mdpi.com/2504-446X/7/7/443mobile edge computingDAG task schedulingdelayservice deployment |
| spellingShingle | Runa Jia Kuang Zhao Xianglin Wei Guoliang Zhang Yangang Wang Gangyi Tu Joint Trajectory Planning, Service Function Deploying, and DAG Task Scheduling in UAV-Empowered Edge Computing Drones mobile edge computing DAG task scheduling delay service deployment |
| title | Joint Trajectory Planning, Service Function Deploying, and DAG Task Scheduling in UAV-Empowered Edge Computing |
| title_full | Joint Trajectory Planning, Service Function Deploying, and DAG Task Scheduling in UAV-Empowered Edge Computing |
| title_fullStr | Joint Trajectory Planning, Service Function Deploying, and DAG Task Scheduling in UAV-Empowered Edge Computing |
| title_full_unstemmed | Joint Trajectory Planning, Service Function Deploying, and DAG Task Scheduling in UAV-Empowered Edge Computing |
| title_short | Joint Trajectory Planning, Service Function Deploying, and DAG Task Scheduling in UAV-Empowered Edge Computing |
| title_sort | joint trajectory planning service function deploying and dag task scheduling in uav empowered edge computing |
| topic | mobile edge computing DAG task scheduling delay service deployment |
| url | https://www.mdpi.com/2504-446X/7/7/443 |
| work_keys_str_mv | AT runajia jointtrajectoryplanningservicefunctiondeployinganddagtaskschedulinginuavempowerededgecomputing AT kuangzhao jointtrajectoryplanningservicefunctiondeployinganddagtaskschedulinginuavempowerededgecomputing AT xianglinwei jointtrajectoryplanningservicefunctiondeployinganddagtaskschedulinginuavempowerededgecomputing AT guoliangzhang jointtrajectoryplanningservicefunctiondeployinganddagtaskschedulinginuavempowerededgecomputing AT yangangwang jointtrajectoryplanningservicefunctiondeployinganddagtaskschedulinginuavempowerededgecomputing AT gangyitu jointtrajectoryplanningservicefunctiondeployinganddagtaskschedulinginuavempowerededgecomputing |