Nos travaux se positionnent dans le cadre de l'algorithmique distribuée et plus particulièrement des réseaux ad hoc. Les réseaux ad hoc sont auto-organisés en permettant des échanges directs entre nœuds mobiles et ne reposent sur aucune infrastructure. Chaque nœud peut se déplacer librement et indépendamment des autres impliquant une modification perpétuelle de la topologie. Dans ce contexte, la probabilité que des défaillances surviennent dans le réseau est importante. Ces défaillances gênent le bon fonctionnement du réseau et peuvent même entrainer une paralysie de celui-ci. C'est pourquoi la conception de solutions pour de tels réseaux nécessitent des mécanismes de gestion de fautes. Parmi ceux-ci, l'approche d'auto-stabilisation permet à un système de gérer les fautes transitoires. Nous étendons cette approche pour répondre aux principaux problèmes liés à la mobilité des nœuds. Notre objectif est de répondre à un double besoin d'auto-organisation du réseau et d'optimisation du nombre de messages échangés. Notre approche consiste à découper le réseau en clusters afin de lui donner une structure hiérarchique. Cette dernière rend l'utilisation du réseau plus efficace et plus performante. L'algorithme que nous avons développé à cet effet est auto-stabilisant et n'est basé que sur des connaissances locales. Nous exploitons cette solution pour proposer deux utilisations efficaces : la diffusion d'informations dans le réseau et le routage. La diffusion d'informations exploite un arbre couvrant inter-clusters, construit sans surcoût, en parallèle de la clusterisation. Le routage quant à lui exploite cet arbre pour permettre à la fois d'optimiser le délai de bout en bout et le nombre de messages échangés. / Our work relies in the domain of distributed system, more preciselly ad hoc networks. Ad hoc networks are self-organized allowing direct exchanges between mobile nodes and do not rely on any infrastruture. Each node can move freely and independently of each others involving continuous topology variability. In this context, the probability that a failure occurs in the network is high. These failures hinder the proper functioning of the network and even causes its paralysis. Therefore, designing solutions for such networks requires fault management mechanisms. Among these, a self-stabilizating approach allows the system to withstand transient faults. We extend this approach to answer the problems induced by nodes mobility. We have two main objectives: a self-organizing network and optimizing number of exchanged messages. Our approach consists in dividing the network into clusters in order to give it a hierarchical structure. This solution allows a more efficient and effective network use. The algorithm that we developed for this purpose is a self-stabilizing algorithm based only on local informations. Based on this solution, we propose two efficient use cases: Information broadcast and a routing protocol. Information broadcast uses an inter-cluster spanning tree, generated without any overhead. In the same time as the clustering process. The routing protocol uses this tree for both round trip and number of exchanged messages optimization.
| Identifer | oai:union.ndltd.org:theses.fr/2011REIMS036 |
| Date | 30 June 2011 |
| Creators | Haggar, Bachar Salim |
| Contributors | Reims, Flauzac, Olivier |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0789 seconds