Planificación de Trayectorias Conjuntas, Despliegue de Funciones de Servicio y Programación de Tareas en DAG en Computación en el Borde Potenciada por UAV
Autores: Jia, Runa; Zhao, Kuang; Wei, Xianglin; Zhang, Guoliang; Wang, Yangang; Tu, Gangyi
Idioma: Inglés
Editor: MDPI
Año: 2023
Acceso abierto
Artículo científico
2023
Planificación de Trayectorias Conjuntas, Despliegue de Funciones de Servicio y Programación de Tareas en DAG en Computación en el Borde Potenciada por UAV
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería Robótica
Palabras clave
Programación de tareas
Vehículo aéreo no tripulado
Computación en el borde
Grafos acíclicos dirigidos
Algoritmo genético
Problema de optimización
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 1
Citaciones: Sin citaciones
La programación eficiente de tareas juega un papel clave en la computación en el borde potenciada por vehículos aéreos no tripulados (UAV) debido a la limitación en el suministro de energía y los recursos de computación en las plataformas UAV. Este problema se complica aún más cuando las tareas dependientes del procesamiento se pueden describir como grafos acíclicos dirigidos (DAG) y cada uno de sus componentes solo se puede procesar en una máquina virtual o contenedor que despliega la función de servicio deseada (SF). En este artículo, primero construimos un problema de optimización que tiene como objetivo minimizar el tiempo de finalización de todas las tareas DAG, sujeto a restricciones que incluyen la dependencia de tareas, los recursos de computación ocupados por los UAV, etc. Para abordar este problema, se propone un algoritmo de programación y despliegue conjunto basado en algoritmos genéticos, llamado GA-JoDeS, ya que resolver el problema de programación entera 0-1 establecido en tiempo polinómico es inviable. La decisión de descarga de subtareas y la posición del UAV se codifican en el cromosoma en el algoritmo GA-JoDeS, y el valor de aptitud de un individuo se determina por el tiempo máximo de finalización de todas las tareas DAG. A través de selección, cruce y mutación, el algoritmo GA-JoDeS evoluciona hasta que determina el individuo con el valor de aptitud óptimo como la solución subóptima al problema. Para evaluar el rendimiento de la propuesta, se realizan una serie de simulaciones y se eligen tres métodos tradicionales como puntos de referencia de comparación. Los resultados muestran que el algoritmo GA-JoDeS puede converger rápidamente y puede reducir efectivamente el tiempo de finalización de las tareas DAG con diferentes configuraciones de parámetros.
Descripción
La programación eficiente de tareas juega un papel clave en la computación en el borde potenciada por vehículos aéreos no tripulados (UAV) debido a la limitación en el suministro de energía y los recursos de computación en las plataformas UAV. Este problema se complica aún más cuando las tareas dependientes del procesamiento se pueden describir como grafos acíclicos dirigidos (DAG) y cada uno de sus componentes solo se puede procesar en una máquina virtual o contenedor que despliega la función de servicio deseada (SF). En este artículo, primero construimos un problema de optimización que tiene como objetivo minimizar el tiempo de finalización de todas las tareas DAG, sujeto a restricciones que incluyen la dependencia de tareas, los recursos de computación ocupados por los UAV, etc. Para abordar este problema, se propone un algoritmo de programación y despliegue conjunto basado en algoritmos genéticos, llamado GA-JoDeS, ya que resolver el problema de programación entera 0-1 establecido en tiempo polinómico es inviable. La decisión de descarga de subtareas y la posición del UAV se codifican en el cromosoma en el algoritmo GA-JoDeS, y el valor de aptitud de un individuo se determina por el tiempo máximo de finalización de todas las tareas DAG. A través de selección, cruce y mutación, el algoritmo GA-JoDeS evoluciona hasta que determina el individuo con el valor de aptitud óptimo como la solución subóptima al problema. Para evaluar el rendimiento de la propuesta, se realizan una serie de simulaciones y se eligen tres métodos tradicionales como puntos de referencia de comparación. Los resultados muestran que el algoritmo GA-JoDeS puede converger rápidamente y puede reducir efectivamente el tiempo de finalización de las tareas DAG con diferentes configuraciones de parámetros.