Les microrobots MEMS sont des éléments miniaturisés qui peuvent capter et agir sur l'environnement. Leur taille est de l'ordre du millimètre et ils ont une faible capacité de mémoire et une capacité énergétique limitée. Les microrobots MEMS continuent d'accroître leur présence dans notre vie quotidienne. En effet, ils peuvent effectuer plusieurs missions et tâches dans une large gamme d'applications telles que la localisation d'odeur, la lutte contre les incendies, le service médical, la surveillance, le sauvetage et la sécurité. Pour faire ces taches et missions, ils doivent appliquer des protocoles de redéploiement afin de s'adapter aux conditions du travail. Ces algorithmes doivent être efficaces, évolutifs, robustes et ils doivent utiliser de préférence des informations locales. Le redéploiement pour les microrobots MEMS mobiles nécessite actuellement un système de positionnement et une carte (positions prédéfinies) de la forme cible. La solution traditionnelle de positionnement comme l'utilisation d'un GPS consommerait trop d'énergie. De plus, l'utilisation de solutions de positionnement algorithmique avec les techniques de multilatération pose toujours des problèmes à cause des erreurs dans les coordonnées obtenues.Dans la littérature, si nous voulons une auto-reconfiguration de microrobots vers une forme cible constituée de P positions, chaque microrobot doit avoir une capacité mémoire de P positions pour les sauvegarder. Par conséquent, si P est de l'ordre de milliers ou de millions, chaque noeud devra avoir une capacité de mémoire de positions en milliers ou millions. Parconséquent, ces algorithmes ne sont pas extensibles ou évolutifs. Dans cette thèse, on propose des protocoles de reconfiguration où les noeuds ne sont pas conscients de leurs positions dans le plan et n'enregistrent aucune position de la forme cible. En d'autres termes, les noeuds ne stockent pas au départ les coordonnées qui construisent la forme cible. Par conséquent, l'utilisation de mémoire pour chaque noeud est réduite à une complexité constante. L'objectif desalgorithmes distribués proposés est d'optimiser la topologie logique du réseau des microrobots afin de chercher une meilleure complexité pour l'échange de message et une communication peu coûteuse. Ces solutions sont complètement distribués. On montre pour la reconfiguration d'une chaîne à un carré comment gérer la dynamicité du réseau pour sauvegarder l'énergie, on étudie comment utiliser le parallélisme de mouvements pour optimiser le temps d'exécution et lenombre de mouvements. Ainsi, on propose une autre solution où la topologie physique initiale peut être n'importe quelle configuration initiale. Avec ces solutions, les noeuds peuvent exécuter l'algorithme indépendamment du lieu où ils sont déployés, parce que l'algorithme est indépendant de la carte de la forme cible. En outre, ces solutions cherchent à atteindre la forme de la cible avec une quantité minimale de mouvement. / MEMS microrobots are miniaturized elements that can capture and act on the environment. They have a small size, low memory capacity and limited energy capacity. These inexpensive devices can perform several missions and tasks in a wide range of applications such as locating odor, fighting against fires, medical service, surveillance, search, rescue and safety. To do these tasks and missions, they have to carry out protocols of redeployment to adapt to the working conditions. These algorithms should be efficient, scalable, robust and should only use local information. Redeployment for mobile MEMS microrobots currently requires a positioning system and a map (predefined positions) of the target shape. Traditional positioning solutions such as using GPS consumes a lot of energy and it is no applicable in the micro scale. Also, the use of an algorithmic solution positioning with multilateration techniques causes problems due to errors in the coordinates obtained. In the literature works, if we want a microrobots self-reconfiguring to a target shape consisting of P positions, each microrobot must have a storage capacity of at least P positions to save them. Therefore, if P equals to thousands or millions, every node must have a storage capacity of thousands or millions of positions. However, these algorithms are notscalable. In this thesis, we propose protocols of self-reconfiguration where nodes are not aware of their position in the plane and do not record the positions of the target shape. Therefore, the memory space required for each node is significantly reduced at a constant complexity. The purpose of these distributed algorithms is to optimize the logical topology of the network of mobile MEMS microrobots to seek a better complexity for message exchange and inexpensive communication.In this work, we show for the reconfiguration of a chain into a square, how to handle the dynamicity of the network to save energy, and we study how to use parallelism in motion to optimize the execution time and the number of movements. Furthermore, another solution is proposed where the initial physical topology may be any connected configuration. With thesesolutions the nodes can execute the algorithm regardless of where they are deployed, because the algorithm is independent of the map of the target shape. Furthermore, these solutions seek to achieve the shape of the target with a minimum amount of movement.

Les récentes avancées technologiques en particulier dans le domaine de la miniaturisation de dispositifs robotiques laissent présager l'émergence de grands ensembles distribués de petits robots qui coopéreront en vue d'accomplir des tâches complexes (e.g., robotique modulaire, robots en essaims, microsystèmes électromécaniques distribués). Ces grands ensembles seront composés d'entités indépendantes, intelligentes et communicantes qui agiront comme un ensemble à part entière. Pour cela, elles s'auto-organiseront et collaboreront en vue d'accomplir des tâches complexes. Ces systèmes présenteront les avantages d'être plus polyvalents et plus robustes que les systèmes robotiques conventionnels tout en affichant un prix réduit. Ces ensembles formeront des systèmes distribués complexes dans lequel chaque entité sera un système embarqué à part entière avec ses propres capacités et ressources toute fois limitées. Coordonner de tels systèmes posent des défis majeurs et ouvrent de nouvelles opportunités dans l'algorithmique distribuée. Je défends la thèse qu'il faut d'ores et déjà identifier et implémenter des algorithmes distribués servant de primitives de base à la coordination de ces ensembles. Dans ce travail, nous nous focalisons sur une classe particulière de robots, à savoir les robots modulaires distribués formant de grands ensembles de modules fortement contraints en ressources (mémoire, calculs, etc.), placés dans une grille régulière et capables de communiquer entre voisins connexes uniquement. J'ai identifié et implémente trois primitives servant à la coordination de ces systèmes, à savoir l'élection d'un nœud central au réseau, la synchronisation temporelle ainsi que l'auto-reconfiguration. Dans ce manuscrit, je propose un ensemble d'algorithmes distribués réalisant ces primitives. J'ai évalué mes algorithmes en utilisant des expériences sur des modules matériels et en simulation sur des systèmes, composés de quelques dizaines à plus d'une dizaine de milliers de modules. Ces expériences montrent que nos algorithmes passent à l'échelle et sont adaptés aux grands ensembles distribués de systèmes embarqués avec des ressources fortement limités à la fois en mémoire et en calcul. / Technological advances especially in the miniaturization of robotic devices foreshadow the emergence of large-scale ensembles of small-size resource-constrained robots that distributively cooperate to achieve complex tasks (e.g., modular self-reconfigurable robots, swarm robotic systems, distributed microelectromechanical systems, etc.). These ensembles are formed from independent, intelligent and communicating units which act as a whole ensemble. These units cooperatively self-organize themselves to achieve common goals. These systems are tought to be more versatile and more robust than conventional robotic systems while having at the same time a lower cost.These ensembles form complex asynchronous distributed systems in which every unit is an embedded system with its own but limited capabilities. Coordination of such large-scale distributed embedded systems poses significant algorithmic issues and open for new opportunities in distributed algorithms. In my thesis, I defend the idea that distributed algorithmic primitives suitable for the coordination of these ensembles should be both identified and designed.In this work, we focus on a specific class of modular robotics systems, namely large-scale distributed modular robotic ensembles composed of resource-constrained modules that are organized in a lattice structure and which can only communicate with neighboring modules. We identified and implemented three building blocks, namely centrality-based leader election, time synchronization and self-reconfiguration.We propose a collection of distributed algorithms to realize these primitives. We evaluate them using both hardware experiments and simulations on systems ranging from a dozen of modules to more than a dozen of thousands of modules. We show that our algorithms scale well and are suitable for large-scale embedded distributed systems with scarce memory and computing resources.

Nous avons étudié durant cette thèse les moyens de rendre le déploiement d'un intergiciel auto-adaptatif. Le type d'intergiciel que nous avons considéré ici est hiérarchique (structure de graphe) et distribué. Chaque sommet du graphe modélise un processus qui peut être déployé sur une machine physique ou virtuelle d'une infrastructure de type grille/cloud, les arêtes modélisent des liens de communications entre processus. Il offre aux clients des services de calcul haute performance. Les infrastructures de grilles/cloud étant élastiques (perte et ajout de nœuds), un déploiement statique n'est pas la solution idéale car en cas de panne on risque de tout reprendre à zéro, ce qui est coûteux. Nous avons donc proposé un algorithme auto-stabilisant pour que l'intergiciel puisse retrouver un état stable sans intervention extérieure, au bout d'un temps fini, lorsqu'il est confronté à certains types de pannes. Les types de pannes que nous avons considérés sont les pannes transitoires (simulé par la perte de nœuds, l'ajout de nouveaux nœuds, la perte de liens entre deux nœuds). Pour évaluer ces algorithmes, nous avons conçu un simulateur. Les résultats des simulations montrent qu'un déploiement, sujet à des pannes transitoires, s'auto-adapte. Avant d'en arriver à la phase de programmation du simulateur, nous avons d'abord proposé un modèle d'infrastructure distribuée (ce modèle permet de décrire des environnements de type grille/cloud), un modèle pour décrire certains types d'intergiciels hiérarchiques et enfin un modèle pouvant décrire un intergiciel en cours d'exécution (processus déployés sur les machines). / We have studied the means to make a middleware deployment self-adaptive. Our use case middleware is hierarchical and distributed and can be modeled by a graph. A vertex models a process and an edge models a communication link between two processes. The middleware provides high performance computing services to the users.Once the middleware is deployed on a computing infrastructure like a grid or cloud, how it adapt the changes in dynamic environment? If the deployment is static, it may be necessary to redo all the deployment process, which is a costly operation. A better solution would be to make the deployment self-adaptive. We have proposed a rules-based self-stabilizing algorithm to manage a faulty deployment. Thus, after the detection of an unstable deployment, caused by some transients faults (joining of new nodes or deletion of existing nodes which may modify the deployment topology), the system will eventually recover a stable state, without external help, but only by executing the algorithm.We have designed an ad hoc discrete events simulator to evaluate the proposed algorithm. The simulation results show that, a deployment, subjected to transients faults which make it unstable, adapts itself. Before the simulator design, we had proposed a model to describe a distributed infrastructure, a model to describe hierarchical middleware and a model to describe a deployment, that is the mapping between the middleware processes and the hardware on which they are running on.