Applications du partitionnement des réseaux de capteurs sans fil au multicast géographique et au tri partiel

La progression des technologies sans fil, offre aujourd'hui de nouvelles perspectives dans le domaine des télécommunications. Les récentes avancées des moyens de communications sans fil permettent l'utilisation de l'information à travers des unités de calculs portables qui ont des caractéristiques particulières (une faible capacité de stockage, une source d'énergie autonome, etc.) et s'introduisant dans le réseau à travers une interface de communication sans fil. Un réseau de capteurs sans fil est composé de centaines voire de milliers de capteurs. Les capteurs sont des dispositifs ayant les particularités suivantes : (1) Capacité de capturer des données relatives à l'environnement où ils sont physiquement placés et de les convertir en signaux électriques. Les données récupérées peuvent être de nature différente et la manière d'obtenir ces données est susceptible de varier. (2) Capacité d'effectuer un traitement sur les données récupérées. (3) Capacité d'échanger ces données avec d'autres dispositifs. Le problème d'initialisation des capteurs consiste à attribuer à chacune des n stations un entier dans l'intervalle [1 n] de telle façon que deux stations ne peuvent pas avoir le même numéro d'identification. Nous avons proposé une approche basée sur l'algorithme de partitionnement de Basagni. Le processus de notre algorithme est composé de : (1) Partitionnement du réseau, (2) Attribution des identifiants partiels, (3) Le gossiping, (4) Les identifiants finaux. Aussi, nous avons superposé deux algorithmes de partitionnement pour résoudre le probléme de multicast géographique dans le réseau de capteurs sans fil. La première approche utilise l'algorithme de partitionnement de Gerla & Tsai et la deuxième exploite la technique de partitionnement hiérarchique de Banerjee & Khuller. Nos approches garantissent la livraison du message pour chaque noeud dans la région geocast. Le premier algorithme garantit la livraison à tous les noeuds dans une ou plusieurs régions geocast, tandis que le second algorithme tient compte de la profondeur de l'arbre hiérarchique de partitionnement et l'estimation de nombres de rondes de radiodiffusions dans le pire des cas, nécessaire pour résoudre le problème de geocast donné. Et finalement, nous avons proposé des algorithmes de résolution pour le problème du tri partiel, en utilisant les réseaux de capteurs sans fil avec les modèles multiples sauts. La principale motivation de nos approches pour ce problème en utilisant le modèle multi-sauts, est le fait qu'il n'existe pas de solutions sur ce modèle. Initialement, nous considérons que chaque noeud dans le réseau possède une et une seule donnée. Une fois le problème résolu, nous procédons à une généralisation de notre approche pour résoudre le problème du tri partiel dans le cas où un noeud peut avoir plusieurs données.The rise of Wireless technologies, today offers new perspectives in the field of telecommunication. Recent advances in Wireless communication allow the use of information through mobile computing units that have specific characteristics (low storage, capacity, an autonomous source of energy...) and access the network interface through a Wireless communication links. A Wireless sensor network consists of hundereds or thousands of sensors. The sensor are devices with following features : (1) Ability to capture data relating to the environment where they are physically located and convert them into electrical signals. (2) Capacity to perform processing on the retrieved. (3) Ability to exchange data with other devices. The initialization problem of the sensors consists of assigning each station an integer in the range [1 n] so that two stations may not have the same identification number. We proposed an approach based on the basagni clustering algorithm. The processing of our algorithm is composed of : (1) Network partitioning. (2) Assignment of partial identifiers. (3) The gossiming. (4) Final identifiers. Also we superimposed two clustering algorithms to solve the problem of geocast in the Wireless sensor networks. The first approach uses the clustering algorithm of Gerla & Tsai and the second exploits the technique of the hierarchical control clustering of Banerjee & Khuller. Our approachs guarantee delivery message to each node in the geocast region. The first algorithm guarantees delivery to all nodes in one or more geocast regions. Whereas, the second algorithm takes into account the depht of the hierarchical tree partitioning and estimates the numbers of broadcast rounds in the worst case necessary to solve the given geocast problem. And finally, we proposed algorithms for solving the sort partial problem in multi-hop Wireless sensor networks. The main motivation of our approaches to tackle this problem in multi-hop model is the fact that there were not yet solutions on this model. Initially, we consider that each node in the network holds one and only one data. Once the problem with one data item is solved, we proceed to generalize our approach to solving the sort partial problem in the case where a node can have multiple data items.AMIENS-BU Sciences (800212103) / SudocSudocFranceF