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.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Joint Trajectory Planning, Service Function Deploying, and DAG Task Scheduling in UAV-Empowered Edge Computing


    Beteiligte:
    Runa Jia (Autor:in) / Kuang Zhao (Autor:in) / Xianglin Wei (Autor:in) / Guoliang Zhang (Autor:in) / Yangang Wang (Autor:in) / Gangyi Tu (Autor:in)


    Erscheinungsdatum :

    2023




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Unbekannt





    Dynamic edge computing empowered by reconfigurable intelligent surfaces

    Paolo Di Lorenzo / Mattia Merluzzi / Emilio Calvanese Strinati et al. | BASE | 2022

    Freier Zugriff

    Service Function Chain Scheduling in Heterogeneous Multi-UAV Edge Computing

    Yangang Wang / Hai Wang / Xianglin Wei et al. | DOAJ | 2023

    Freier Zugriff