Soutenance mémoire
NŒUD CAPTEUR
Un nœud capteur est un dispositif électronique capable d’acquérir des données environnementales, de les traiter et de les communiquer à un utilisateur final.
Dans le reste du manuscrit, nous utilisons les termes capteur ou nœud pour désigner un nœud capteur de manière abrégée.
Un nœud capteur est constitué des composants suivants :
— Un processeur dont la puissance de calcul est limitée. Il est utilisé pour le traitement des données captées et des données transmises par les autres capteurs.
— Une mémoire exploitée à la fois pour stocker des données recueillies ainsi que pour l’exécution d’un programme.
— Un émetteur-récepteur radio permettant les communications entre capteurs via un medium sans fil. La puissance de signal utilisée détermine la portée de communication. Toutefois, plus la puissance augmente, plus la consommation énergétique est importante.
— Une unité de captage permettant de mesurer des grandeurs physiques telles que la température, la luminosité ou encore l’humidité. Les données captées sont, ensuite, transformées en données numériques pouvant être exploitées par le processeur.
— Une source d’énergie fournissant l’énergie nécessaire au fonctionnement des autres composants. La ressource énergétique, la plus souvent utilisée, est la batterie. Toutefois, suivant les applications, les capteurs peuvent être branchés à une source énergétique continue.
— Un GPS (Global Positioning System) permettant de géolocaliser le capteur. Il s’agit d’un dispositif optionnel car les contraintes économiques et énergétiques limitent son utilisation.
RÉSEAU DE CAPTEURS SANS FIL
Dans cette section, nous présentons les réseaux de capteurs de manière générale. Puis, nous détaillons les divers modèles permettant de les modéliser suivant les caractéristiques à prendre en compte. Pour finir, nous expliquerons les différents challenges propres à ce type de réseau.
GÉNÉRALITÉS SUR LES RÉSEAUX DE CAPTEURS SANS FIL
Nous définissons, dans cette section, ce que constitue un réseau de capteurs sans fil, leurs domaines d’utilisation, les différents modes de collecte et de déploiement et, pour finir les topologies.
Réseau de capteurs sans fil
Un réseau de capteurs sans fil est un réseau ad hoc constitué d’un ensemble de nœud capteurs mesurant et communiquant des données environnementales pour les transmettre à un ou plusieurs nœuds particuliers nommé nœud puits ou station de base. Les communications au sein de ce type de réseau sont effectuées via des ondes radio.
D’après la définition, un réseau de capteur se compose de deux types de nœuds : les nœuds capteurs et les nœuds puits. Les premiers ont pour objectif de relever des informations sur la zone de captage et, ensuite, de les transférer vers le point de collecte représenté par la station de base ou le puits. La station de base, quant à elle, récupère les informations qui lui sont transmises et les envoie au centre de traitement. Elle peut également envoyer un message à tous les nœuds capteurs afin de diffuser une information comme par exemple, la périodicité de l’acquisition des données environnementales. Un réseau de capteurs peut se composer d’une ou plusieurs stations de base : nous parlons de réseau mono-station de base (mono sink) ou de réseau multi-station de base (multi-sink). Les réseaux de capteurs appartiennent à la famille des réseaux ad hoc. Au sein de ce type de réseau, la communication s’effectue par le bais d’ondes radio. Ils se caractérisent par leur capacité à s’organiser sans infrastructure définie au préalable.
Domaines d’utilisation :
Les domaines d’utilisation des réseaux de capteurs sont divers et variés [21, 42]. Dans la suite, nous donnons quelques exemples :
— La santé : un exemple est le réseau corporel (Body Area Network). Il s’agit d’un réseau sans fil permettant d’interconnecter sur, autour ou dans le corps humain, des minuscules dispositifs pouvant effectuer des mesures (capteurs) ou agir de façon active (actionneurs). Ces capteurs sont en mesure de communiquer avec un centre de service distant afin, par exemple, de communiquer l’état du patient sous observation. Des exemples de capteurs corporels sont les capteurs de glycémie ou encore de pression artérielle [49]. Notamment, l’implantation d’un biocapteur chez un patient fournit une méthode plus précise et moins invasive pour mesurer le taux de glucose et, en fonction du résultat, un dispositif complémentaire peut effectuer une injection automatique d’insuline.
— L’urbanisation et l’infrastructure : les capteurs sont utilisés, par exemple, dans le cadre des villes intelligentes. Federspiel et al. [9] étudient l’amélioration de la production, de la distribution et de la consommation d’énergie via l’utilisation de capteurs. Idwan et al. [80] proposent l’utilisation des réseaux de capteurs pour optimiser la gestion des déchets grâce à l’utilisation de bennes à ordures intelligentes équipées de capteurs de niveau de déchets. La connaissance du niveau pouvant être utilisée par les municipalités pour déployer le nombre suffisant de camions et de personnes pour la collecte des déchets. De plus, la planification du parcours et les routes à suivre peuvent être effectués pour minimiser le temps et le carburant nécessaires.
— L’environnement : les capteurs sont utilisés pour surveiller la nature. Par exemple, ils permettent la détection des inondations ou la présence de feu dans les forêts. Un autre exemple d’application peut être la prédiction du temps météorologique. L’un des exemples les plus représentatifs est le déploiement d’un réseau de capteurs composé de 32 nœuds sur l’île Great Duck [11]. Les capteurs utilisés détectaient la température, la pression barométrique et l’humidité. Le but était de surveiller l’environnement naturel d’un oiseau (pétrel de mer) et son comportement en fonction des changements climatiques.
— Le domaine militaire : les capteurs sont utilisés afin de détecter des explosifs ou encore dans un champs de bataille pour détecter les mouvements des troupes ennemies. Par exemple, l’université de Virginie propose de remplacer les mines par des milliers de capteurs dispersés qui détecteront une intrusion d’unités hostiles [17].
Modes de collecte :
La collecte des informations environnementales peut se faire suivant trois modes différents :
— Supervision (Monitoring) : Ce mode permet l’acquisition en continu de la grandeur à mesurer. Les capteurs envoient de manière périodique les données acquises.
— Collecte à la demande : Lorsque nous souhaitons avoir les informations, la station de base effectue une diffusion pour propager la demande. Les capteurs effectuent la mesure et remontent l’information mesurée à la station de base.
— Collecte suite à un événement : Lorsqu’un événement se produit (changement brusque de température, détection d’un mouvement, minuteur expiré, etc), les capteurs ayant détecté l’information la remontent jusqu’à la station de base.
Modes de déploiement :
Les réseaux de capteurs peuvent être déployés suivant une topologie pré-configurée ou dispersés de manière aléatoire [23]. Il existe des réseaux de capteurs sans fils mobiles dont le déploiement n’est pas fixe. Nous ne nous intéressons pas à l’aspect mobile dans nos travaux. Une fois les capteurs déployés, une topologie logique peut être mise en place afin de palier au manque d’infrastructure physique des réseaux de capteurs sans fils.
PROTOCOLES DE LA SOUS-COUCHE MAC
D’après Pal et al. [73], dans les réseaux de capteurs sans fils, les protocoles MAC peuvent être divisés en deux catégories : les protocoles avec ou sans contention. Dans la première catégorie, nous retrouvons, par exemple, ALOHA (Additive Link On-Line Hawaii System) et CSMA (Carrier Sense Multiple Access).
Dans les protocoles MAC sans contention, l’accès des nœuds au medium est divisé par rapport au temps (Time Division Multiple Access ou TDMA), ou la fréquence (Frequency Division Multiple Access ou FDMA) ou le code (Code Division Multiple Access ou CDMA). Ces méthodes permettent aux différents nœuds d’accéder au medium sans interférer les uns avec les autres et évite ainsi efficacement les collisions. Le mécanisme de contrôle d’accès au medium le plus populaire pour les réseaux ad-hoc utilise le CSMA (Carrier Sense Multiple Access). Toutefois, dans le cas des réseaux sans fils, il présente de nombreux inconvénients, tels que un coût énergétique élevé ou encore un délai d’accès accru. Pour ces raisons, le TDMA (Time Division Multiple Access) semble plus approprié pour ce type de réseaux [79]. C’est pour cela que nous nous concentrons sur le protocole TDMA.
Le nombre d’intervalles de temps dans chaque trame TDMA est appelé la longueur de la trame. Un intervalle de temps a une longueur de temps unitaire requise pour qu’un paquet soit transmis entre nœuds adjacents. Lorsque les nœuds sont proches, des collisions peuvent se produire en cas de transmissions simultanées. Par conséquent, l’utilisation de TDMA en tant que protocole MAC dans les réseaux multihop sans fil nécessite un ordonnancement des nœuds afin d’éviter les collisions. Un protocole TDMA a pour objectif de définir un ordonnancement. Cela consiste à déterminer un nombre d’intervalles de temps ou créneaux (slot). Chaque nœud se voit associer un créneau pour transmettre ses données et un certain nombre de créneaux pour recevoir les données de ses voisins.
|
Table des matières
Introduction
I Les réseaux de capteurs sans fils
1 Réseaux de capteurs sans fil hétérogènes
1.1 Contexte
1.1.1 Nœud capteur
1.1.2 Réseau de capteurs sans fil
1.1.2.1 Généralités sur les réseaux de capteurs sans fil
1.1.2.2 Modèles de connexité
1.1.2.3 Modèles d’interférence
1.1.2.4 Challenges
1.2 Notations
1.3 Problèmes
1.3.1 Diffusion
1.3.2 Routage multi-couche
1.3.2.1 Le modèle en couches
1.3.2.2 Le cross-layering
1.3.2.3 Protocoles de la sous-couche MAC
1.4 Méthodes de résolution
1.5 Résultats obtenus
II Communications dans les réseaux sans fils
2 La diffusion dans les réseaux de capteurs sans fils
2.1 Ensemble dominant connexe
2.1.1 Graphe de disques unitaires
2.1.2 Graphe de disques avec liens bidirectionnels
2.1.3 Graphe de disques
2.1.4 Graphe général
2.1.5 Synthèse
2.2 Ensemble dominant connexe avec équilibrage de la charge
2.2.1 Graphe de disques unitaires
2.2.2 Synthèse
2.3 Ensemble dominant connexe et énergie
2.3.1 Graphe de disques unitaires
2.3.2 Graphe de disques
2.3.3 Synthèse
2.4 Ensemble dominant connexe et latence
2.4.1 Graphe de disques unitaires
2.4.2 Graphe Cordal
2.4.3 Graphe de disques
2.4.4 Graphe général
2.4.5 Synthèse
2.5 Ensemble dominant connexe tolérant aux pannes
2.5.1 Graphe de disques unitaires
2.5.2 Graphe de disques avec liens bidirectionnels
2.5.3 Graphe de disques
2.5.4 Graphe non orienté
2.5.5 Graphe général
2.5.6 Synthèse
2.6 Synthèse
III Contributions
3 Algorithme d’approximation pour la diffusion dans les réseaux de capteurs
3.1 Caractérisation du problème
3.1.1 Complexité
3.1.2 Programme linéaire en nombres entiers
3.2 Algorithme d’approximation BB
3.3 Étude préliminaire
3.3.1 Structure du chemin P1 par rapport à P2
3.3.2 Preuve du théorème 1
3.4 Algorithme Bounded Backbone (BB)
3.5 Preuve
3.6 Synthèse
4 Heuristiques pour la diffusion dans les réseaux de capteurs
4.1 Heuristique naïve
4.2 Heuristique Highly Bounded Backbone (HBB)
4.3 Recuit simulé
4.4 Expérimentations
4.4.1 Description
4.4.2 Résultats et analyses
4.4.3 Synthèse des expérimentations
4.5 Synthèse
5 Routage multi-couche
5.1 Protocoles cross-layer dans les WSN
5.1.1 Approches cross-layer inter-couche
5.1.2 Approches cross-layer par fusion de couches
5.2 Formalisation du problème
5.2.1 Définition du problème
5.2.2 Modélisation de la solution
5.3 Programme linéaire en nombres entiers
5.4 Algorithme IDeg-Routing&MAC
5.5 Exemple explicatif
5.6 Simulations
5.6.1 Description
5.6.2 Résultats
5.6.3 Discussion
5.7 Synthèse
Conclusion
Télécharger le rapport complet
