Déploiement optimal des nœuds de capteurs employant le clustering K-means et un algorithme génétique

Larbi, Rihem (2021). Déploiement optimal des nœuds de capteurs employant le clustering K-means et un algorithme génétique. Mémoire de maîtrise électronique, Montréal, École de technologie supérieure.

Prévisualisation

PDF Télécharger (5MB) | Prévisualisation

Résumé

Au cours des dernières décennies, les réseaux de capteurs sans fil ont reçu un nouvel essor grâce à la miniaturisation des composants électroniques. Ces composants ont permis de fabriquer de petits systèmes équipés de dispositifs de mémoire, de microprocesseurs, de communication et de capteurs. Ces systèmes sont appelés "nœuds de capteurs". Lorsqu’ils sont déployés dans une zone d’intérêt, ils interagissent et communiquent entre eux de façon autonome pour former un réseau de capteurs capable de transmettre des informations à la station de base. Les réseaux de capteurs sont utilisés dans plusieurs domaines d’application tels que la santé, le transport, l’armée et l’agriculture. Cependant, ces applications sont particulièrement sensibles sur la qualité de la couverture du terrain et sur la connectivité du réseau. De plus, plusieurs chercheurs s’intéressent aux problèmes soulevés par ces applications, tels que l’énergie, la couverture, la connectivité et le chevauchement, en d’autres termes le problème de déploiement de nœuds.

Dans ce projet de mémoire, nous abordons le problème du déploiement de nœuds dans une application spécifique qui est la prévention des incendies dans les forêts. Nous proposons une approche de déploiement comprenant deux phases : une phase de représentation de la zone basée sur un algorithme d’apprentissage non supervisé qui est le clustering K-means et une phase de déploiement de nœuds de capteurs basée sur l’algorithme génétique. L’objectif de la première phase est de déterminer les points d’intérêt à couvrir en tenant compte de la structure de la zone géographique. En ce qui concerne la deuxième phase, son objectif est de déterminer l’emplacement optimal des nœuds de capteurs en tenant compte de différentes contraintes telles que la couverture, la connectivité, le coût de déploiement et le chevauchement entre les nœuds.

Les simulations réalisées ont démontré la performance de notre solution à optimiser le déploiement de nœuds de capteurs dans des zones géographiques à grande et petite échelle tout en assurant une couverture maximale, une connectivité totale du réseau, un nombre minimum de nœuds et un chevauchement minimal. En outre, les résultats expérimentaux ont prouvé l’efficacité de notre approche pour fournir des solutions optimales.

Titre traduit

Optimal sensor node deployment employing K-means clustering and genetic algorithm

Résumé traduit

In recent decades, wireless sensor networks have received a new impetus thanks to the miniaturization of electronic components. These components have made it possible to manufacture small systems equipped with memory devices, microprocessors, communication and sensor devices. These systems are called "sensor nodes". When deployed in an area of interest, they interact and communicate with each other autonomously to form a network of sensors capable of transmitting information to the base station. Sensor networks are used in several application areas such as health, transportation, military and agriculture. However, these applications are particularly sensitive on the quality of the coverage of the field and the network connectivity. In addition, several researchers are interested in the problems raised by these applications, such as energy, coverage, connectivity and redundancy, in other words, the problem of node deployment.

In this thesis project, we address the problem of the deployment of sensor nodes in a specific application which is the prevention of forest fires. We propose a deployment approach comprising two phases : a phase of area representation based on an unsupervised learning algorithm which is the K-means clustering, and a phase of sensor node deployment based on the genetic algorithm. The objective of the first phase is to determine the points of interest to be covered taking into account the structure of the geographical area. For the second phase, its objective is to determine the optimal location of the sensor nodes taking into account various constraints such as coverage, connectivity, cost of deployment and overlap between nodes.

The simulations carried out have demonstrated the performance of our solution in optimizing the deployment of sensor nodes in large and small-scale geographical areas while ensuring maximum coverage, full network connectivity, minimum number of nodes and minimum redundancy. In addition, experimental results have proven the effectiveness of our approach to provide optimal solutions.

Type de document:	Mémoire ou thèse (Mémoire de maîtrise électronique)
Renseignements supplémentaires:	"Mémoire présenté a l’École de technologie supérieure comme exigence partielle a l’obtention de la maîtrise avec mémoire en génie des technologies de l’information". Comprend des références bibliographiques (pages 67-70).
Mots-clés libres:	WSN, K-means, algorithme génétique
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Gherbi, Abdelouahed
Programme:	Maîtrise en ingénierie > Génie des technologies de l'information
Date de dépôt:	03 nov. 2021 15:52
Dernière modification:	03 nov. 2021 15:52
URI:	https://espace.etsmtl.ca/id/eprint/2770

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt