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.

Abstract

Modern sensing applications can be decomposed into sensing and computing phases, where data is typically collected by a dedicated local internet of things system in the sensing phase to be processed in the computing phase. Given the massive amount of data present in such applications, the computing step may require robust storage and computing resources in the cloud. However, common cloud computing infrastructures present issues (e.g., high latency) that are inadmissible for timely manner applications as emergency response and disaster relief operations. The edge computing and ad-hoc cloud paradigms address those issues by providing storage and computing resources close to their users, thus allowing applications to keep their computing phases local. Consequently, those paradigms have been extensively employed in applications with time and network restrictions. For instance, a swarm of drones collecting photos and video over a post-disaster area can create a wireless ad-hoc cloud infrastructure to process the collected data regardless of network connectivity. Therefore, optimizing the workload carried by a local ad-hoc cloud is crucial for boosting the success of timely manner applications. This thesis investigates the optimal use of swarm-powered ad-hoc clouds while fulfilling clustering and networking constraints. In order to illustrate the applicability of the contributions of this thesis, we adopt a swarm-powered 3D mapping mission for real-life emergency response operations as our use case. The first contribution proposes a new optimization problem, namely the Covering-Assignment Problem for swarm-powered ad-hoc clouds (CAPsac), for the efficient generation and execution of multi-node computing workloads subject to data geolocation and clustering constraints. The CAPsac aims to minimize the overall completion time of the tasks offloaded to the ad-hoc cloud while accounting for inter-drone transmission delays. Besides proving that the problem is NP-hard, we present two combinatorial formulations to solve it. Computational results on the solution of the formulations show that one of them can be used to solve, within the configured time limit, more than 50% of the considered real-world instances involving up to 200 images and 6 drones. Obtaining near-optimal workloads quickly is crucial for the adopted swarm-powered 3D mapping mission use case. Therefore, the second contribution presents a mathematical programming heuristic based on decomposition and a variable neighborhood search heuristic for solving the CAPsac. The experimental analysis shows that the proposed near-optimum methods rapidly reach optimality or improve the best known solutions for almost all tested realistic instances comprising up to 1000 images and 15 drones. Finally, in our third contribution, we describe and assess the swarm-powered Optimized 3D Mapping Pipeline (OptiMaP) for emergency response 3D mapping missions. The OptiMaP is built as an embedded ROS application that is connected through an ad-hoc telecommunication middleware (HEAVEN) provided by our partner Humanitas Solutions. The simulations comprising up to 5 drones and 363 images revealed that the two versions of the OptiMaP can significantly decrease the completion times of swarm-powered 3D mapping missions.