Workload Optimization for Swarm-Powered Ad-hoc Clouds

Les applications de détection modernes peuvent être décomposées en phases de détection et de calcul, où les données sont généralement collectées par un système local dédié de l'internet des objets dans la phase de détection pour être traitées dans la phase de calcul. Compte tenu de la quantité massive de données présentes dans ces applications, l'étape de calcul peut nécessiter des ressources de stockage et de calcul robustes dans le nuage. Cependant, les infrastructures communes de l'informatique en nuage présentent des problèmes (par exemple, une latence élevée) qui sont inadmissibles pour les applications limitées dans le temps comme les interventions d'urgence et les opérations de secours en cas de catastrophe. Les paradigmes de l'informatique en périphérie de réseau et du nuage ad-hoc traitent ces problèmes en fournissant des ressources de stockage et de calcul à proximité de leurs utilisateurs, permettant ainsi aux applications de conserver leurs phases de calcul locales. Par conséquent, ces paradigmes ont été largement utilisés dans des applications avec des restrictions de temps et de réseau. Par exemple, un essaim de drones collectant des photos et des vidéos d'une zone post-catastrophe peut créer une infrastructure de nuage ad-hoc sans fil pour traiter les données collectées indépendamment de la connexion Internet. Par conséquent, l'optimisation de la charge de travail supportée par un nuage ad-hoc local est cruciale pour stimuler le succès des applications limitées dans le temps. Cette thèse étudie l'utilisation optimale des nuages ad-hoc créé par un essaim de drones tout en respectant les contraintes de groupement et de mise en réseau. Afin d'illustrer l'applicabilité des contributions de cette thèse, nous adoptons une mission de cartographie 3D propulsée par des essaims pour des opérations d'intervention d'urgence réelles comme cas d'utilisation. La première contribution propose un nouveau problème d'optimisation, nommé Covering- Assignment Problem for swarm-powered ad-hoc clouds (CAPsac), pour la génération et l'exécution efficaces de charges de travail de calcul multi-noeuds soumises à des contraintes de géolocalisation et de groupement. Le CAPsac vise à minimiser le temps d'achèvement global des tâches déchargées sur le nuage ad-hoc tout en tenant compte des délais de transmission entre les drones. En plus de prouver que le problème est NP-difficile, nous présentons deux formulations combinatoires pour le résoudre. Les résultats sur la solution des formulations montrent que l'une d'entre elles peut être utilisée pour résoudre, dans la limite de temps configurée, plus de 50% des instances réalistes considérées impliquant jusqu'à 200 images et 6 drones. L'obtention rapide de charges de travail quasi-optimales est cruciale pour le cas d'utilisation adopté de la mission de cartographie 3D propulsée par essaim. Par conséquent, la deuxième contribution présente une heuristique de programmation mathématique basée sur la décomposition et une heuristique de recherche en voisinage variable pour résoudre le CAPsac. L'analyse expérimentale montre que les méthodes quasi-optimales proposées atteignent rapidement l'optimalité ou améliorent les meilleures solutions connues pour presque toutes les instances réalistes testées comprenant jusqu'à 1000 images et 15 drones. Enfin, concernant notre troisième contribution, nous décrivons et évaluons le swarm-powered Optimized 3D Mapping Pipeline (OptiMaP) pour les missions de cartographie 3D d'intervention d'urgence. L'OptiMaP est construit comme une application ROS embarquée qui est connectée via un middleware de télécommunication ad-hoc (HEAVEN) fourni par notre partenaire Humanitas Solutions. Les simulations comprenant jusqu'à 5 drones et 363 images ont révélé que les deux versions de l'OptiMaP peuvent réduire de manière significative le temps de réalisation des missions de cartographie 3D propulsée par essaim.