Un algorithme distribué pour la localisation dans les rcsfs

Abstract

Les réseaux de capteurs sans fil (RCSFs) sont une nouvelle technologie, qui a surgit après les grands progrès technologiques concernant le développement des capteurs, des processeurs puissants et des protocoles de communication sans fil. Ce type de réseaux, composé de centaines voire des milliers d’éléments, a pour but la collecte de données de l’environnement, leur traitement et leur transmission vers le monde intérieur. A cet égard, le travail présenté dans ce mémoire s’inscrit dans des réseaux de capteurs sans fil. Il porte sur l'étude et la mise en oeuvre d’un algorithme distribué pour la problématique de localisation dans les réseaux de capteurs sans fil. La localisation est utilisée pour trouver les positions plus au moins exacte des capteurs déployés aléatoirement. Nous introduisons une nouvelle approche de localisation se basant sur le principe des CSPs (Problème de Satisfaction de contraintes). Notre approche se base sur une organisation hiérarchique, où le réseau est divisé en un ensemble de clusters. Nous avons utilisé le principe des multi agents, où chaque agent représente un cluster qui regroupe un ensemble de contraintes. Les contraintes inter clusters, représentent les contraintes inter agents. Cette représentation nous permet d’avoir une modélisation par un CSP distribué qui nous a permis de proposer un algorithme de localisation distribué. Mots clés : Réseaux de capteurs sans fil (RCSF), la localisation, clustering, alliances dans un graphe, problème de satisfaction de contraintes, CSP distribués Abstract : Wireless Sensor Networks (RCSFs) is a new technology, which has emerged after the great technological advances in the development of sensors, powerful processors and wireless communication protocols. This type of network, composed of hundreds or even thousands of elements, aims to collect environmental data, their processing and their transmission to the inner world. In this respect, the work presented in this thesis is part of wireless sensor networks. It focuses on the study and implementation of a distributed algorithm for the localization problem in wireless sensor networks. The location is used to find the more or less exact positions of the sensors deployed randomly. We introduce a new localization approach based on the principle of CSPs (Constraint Satisfaction Problem). Our approach is based on a hierarchical organization, where the network is divided into a set of clusters. We used the principle of multi agents, where each agent represents a cluster that groups a set of constraints. The inter-cluster constraints represent the inter-agent constraints. This representation allows us to have a modeling by a distributed CSP which allowed us to propose a distributed localization algorithm. Key words : wireless sensor network, localization, clustering, alliances in a graph, constraints satisfaction problem, distributed CSP