Routage g éographique dans les r éseaux de capteurs et actionneurs

This thesis is about wireless multi-hop networks such as wireless sensors networks or hybrid sensor/actuator networks and actuator networks. Those kinds of networks are composed of independent entities (nodes, i.e. the robots) which have very limited computing and memory capabilities. Moreover, they are battery powered and have to work in an efficient way. They communicate through the radio medium and do not require any static infrastructure. In order to relay messages between actuators up to the base station, we use what is called "routing protocols". In order to be efficient, those protocols have to find a routing path, over multiple robots, in a local and distributed manner, without any global knowledge about the network. My works rely on CoMNet, the first geographic routing protocol which relies on the controlled mobility of the robots while guaranteeing network connectivity despite their movements. CoMNet relocates next hop node on each routing step, according to a predefined relocation pattern. Its aims to adapt the network topology to the routed traffic in order to save energy. Nevertheless, CoMNet does not consider the consequences of those relocations more than in a one-hop way. By making node N relocating node N +1 on the routing path, CoMNet adapts the topology locally. But CoMNet ignores the fact that making this N + 1 node move changes its routing possibilities too. We proposed MobileR (Mobile Recursivity), a new routing protocol which takes this phenomena into account. MobileR, at each routing step, anticipates the routing in a multi-hop manner through computations over its one-hop neighbors. It makes the current forwarding node compute all the possible routing paths toward the destination using relocation patterns recursively. The cost-over-progress of each path is computed and the next hop selected is the first hop on the best computed path. Still, the protocol is completely localized and no information, except the forwarding packet, is shared between nodes. On the one hand, the relocating nodes principle is not without consequences. It brings new issues to solve. For instance, in wireless sensor networks, events are likely to be detected by multiple sensors. Consequently, on events occurrence, multiple sensors transmit message toward the destination. But those source nodes are geographically close, as they report the same event. Hence the routing paths for the data they transmit are very close and even merge close to the destination. This phenomena has to be considered. In current routing protocol for actuators, those common routing path parts provoke useless oscillation and premature node death as relocating scheme compete for the same nodes. As a response to this phenomena, I propose the PAMAL (PAth Merging ALgorithm) routing algorithm. PAMAL detects those routing path crossing and handles them in a purely localized way. It makes nodes oscillation stop and provokes a path merging upstream and uses a packet aggregation downstream. Thanks to this behavior, PAMAL makes the network lifetime increase up to 37% with the simplest possible aggregation. But on the other hand, controlled mobility also makes possible new answers to old routing issues in wireless sensors networks. The Greedy Routing Recovery (GRR) routing protocol takes controlled mobility into account in order to increase delivery rate on topology with holes or obstacles. Indeed, None of the few existing routing protocols for actuator networks proposes any mechanism to bypass obstacles or topology holes where greedy routing is impossible. They all rely on a greedy forwarding routing strategy toward destination node. Hence they all fail when the current holding node has no neighbor closer to the destination than itself. GRR includes a dedicated relocation pattern which will make it bypass routing holes and create a routing path on which greedy forwarding will be possible. The obstacle, or hole, is circumvented by relocating nodes all around. Thanks to this light recovery, next routing are going to be in a fully greedy forwarding way. Simulation results show that the light recovery mechanism we use in GRR has a hit ratio of 72% over network topologies where traditional CoMNet fails.Cette thèse se positionne dans le contexte des réseaux sans fil multi-sauts tels les réseaux de capteurs ou les réseaux de capteurs/actionneurs ou encore de robots mobiles. Ces réseaux sont composés d'entités (nœuds) indépendantes (c.-à-d. les robots) possédant des capacités limitées en termes de taille mémoire, de capacité de calcul et sont soumis à des contraintes énergétiques fortes (ces composants reposent sur des batteries). Ils communiquent exclusivement par voie radio, il n'y a donc aucune infrastructure fixe. Pour pouvoir relayer les messages d'un robot à une station de base, on utilise des protocoles dits " de routage" qui ont en charge de déterminer quel robot doit relayer le message, de façon locale et distribuée, sans connaissance globale du réseau. Nous nous sommes basé sur CoMNet, le premier protocole de routage géographique utilisant la mobilité contrôlée tout en garantissant la connexité de celui-ci. CoMNet va, à chaque routage, relocaliser le prochain saut selon un schéma de relocalisation prédéfini de manière à adapter la topologie du réseau à son trafic, et ce afin d'économiser de l'énergie. CoMNet propose trois schémas de relocalisation différents adaptés à différents environnements, et l'on en choisit un au démarrage du réseau. Toutefois, CoMNet, en faisant bouger le prochain nœud N, va certes adapter la topologie, mais aussi modifier le voisinage de ce même nœud. Quand ça sera à lui de transmettre le message il n'aura plus forcément les mêmes possibilités, ses voisins ayant changé. La relocalisation d'un nœud N va servir de base pour celle de N + 1 et les suivants dans le routage. En réponse à ce problème, nous avons proposé MobileR (Mobile Recursivity). MobileR va, à chaque étape du routage, essayer d'anticiper sur plusieurs sauts pour choisir le prochain noeud. Il va calculer la relocalisation des voisins N et pour chacun d'entre eux les multiples N + 1 possibles, etc. MobileR va donc calculer à chaque étape du routage les coûts sur progrès de chacun des chemins (avec nœuds relocalisés) possibles. Le paquet sera alors transmis, au premier nœud du chemin qui minimise ce ratio. Le principe même de relocaliser les nœuds apporte son lot de nouveaux problèmes. Ainsi, dans les réseaux de capteurs, il y a souvent plusieurs nœuds sources qui détectent un même événement et vont émettre des messages à router vers l'unique station de base. Les chemins de routage de ces différents messages sont physiquement proches - vu qu'ils sont liés à un même événement - et ce d'autant plus qu'on se rapproche de la station de base. Ces chemins vont finir par se croiser, et le noeud de croisement va sans cesse être relocalisé par chacun des chemins. C'est pourquoi j'ai proposé le protocole de routage PAMAL (PAth Merging ALgorithm) en réponse à un problème introduit par la mobilité. En effet, PAMAL permet de détecter ces intersections et de les gérer localement. Il va arrêter ces oscillations parasites, provoquer une fusion des chemins de routage en amont du noeud d'intersection et une agrégation de paquets en aval. PAMAL propose ainsi une amélioration de la durée de vie du réseau allant jusqu'à 37% avec un mécanisme d'agrégation très simple. La mobilité contrôlée permet aussi d'envisager de nouvelles solutions à des anciens problèmes. Le protocole GRR (Greedy Routing Recovery) propose ainsi un mécanisme de récupération pour augmenter le taux de délivrance des messages dans les réseaux de capteurs/actionneurs avec obstacle(s). En effet aucun des protocoles de routage reposant sur des actionneurs n'implémente un procédé pour contourner les obstacles ou les zones de faible densité où le routage glouton simple est impossible. Ils routent tous les messages de manière gloutonne vers la destination. Le routage échoue alors quand un noeud n'a plus de voisin plus proche de la destination que lui-même. C'est pourquoi GRR va, quand le routage glouton simple de proche en proche échoue, appliquer un nouveau schéma de relocalisation qui va permettre de contourner l'obstacle tout en restaurant le routage glouton. L'obstacle va ainsi être circonvenu en relocalisant des nœuds tout autour. Ainsi, les routages suivants seront gloutons. Sans pour autant garantir la délivrance de 100% des messages, nos simulations montrent que le mécanisme de récupération de GRR permet de router avec succès dans 72% des cas sur des topologies où CoMNet échoue dans tous les cas