Approche Théorie des Graphes pour la Surveillance d’un ...theses.univ-oran1.dz/document/TH2445.pdf · d’un Réseau de Capteurs sans fil Présenté par BENAHMED Khélifa Pour

République Algérienne Démocratique et Populaire Ministère de l’enseignement supérieur et de la recherche

Scientifique

Université d’Oran Es-senia Faculté des Sciences

Département d’informatique

Thème

Approche Théorie des Graphes pour la Surveillance

d’un Réseau de Capteurs sans fil

Présenté par

BENAHMED Khélifa

Pour l’obtention du diplôme de Magister en Informatique

Option : Méthodes et Modèles pour la sécurité des S.I Membres du jury : Mr RAHMOUNI Mustapha Kamel Président Prof. Université d’Oran Es-Senia Mr SEKHRI Larbi Examinateur M.C. Université d’Oran Es-Senia Mr MESSABIH Belhadri Examinateur M.C. U.S.T.O Mr BOUAMRANE Karime Examinateur C.C. Université d’Oran Es-Senia Mr HAFFAF Hafid Encadreur Prof. Université d’Oran Es-Senia Mr KECHAR Bouabdalah Co-encadreur C.C. Université d’Oran Es-Senia

Février 2007

Remerciements

C'est avec l’enthousiasme le plus vif et le plus sincère que je remercie en premier lieu, Monsieur Mustapha Kamel RAHMOUNI, Professeur à l’université Es-Senia, d’une part, pour la confiance et l’encouragement qu’il m’a accordé durant toute l’année théorique , d’autre part pour l’honneur qu’il me fait en présidant ce jury. Je remercie également, Monsieur Larbi SEKHRI Maître de conférences, à l’université Es-Senia, Monsieur Belhadri MESSABIH Maître de conférences, à l’ U.S.T.O et Monsieur Karime BOUAMRANE Chargé de cours, à l’université Es-Senia d’avoir acceptés de siéger dans ce jury afin d’examiner ce modeste travail. Ensuite, j’adresse mes plus chaleureux remerciements à mon directeur de thèse, Monsieur Hafid HAFFAF, Professeur au département d'Informatique à l’université Es-Senia, pour ses attentions constante et ses conseils pertinents et qui a énormément contribué à mon évolution scientifique et technique. Au même titre, je remercie Monsieur Bouabdalah KECHAR, chargé de cours au niveau du département d'Informatique qui a assuré le co-encadrement de cette thèse. Je leur suis extrêmement reconnaissant pour la disponibilité, pour les conseils prodigués et pour le suivi particulier dont ils ont fait preuve pendant les phases de recherche et de rédaction de la présente thèse. Plus personnellement, je tiens à remercier vivement mes amis Messieurs Belaguid Mustapha et Kaïd Nouredine, pour leurs soutiens et aides. Je remercie aussi mon épouse, d’avoir été un soutien moral inébranlable, même dans les moments difficiles.

Je dédie cette thèse à la mémoire de mes parents,

à ma femme, et à mes enfants.

Table des matières Table des figures..............................................................................................1 Liste des tableaux ............................................................................................3 Introduction Générale.....................................................................................4 1. Présentation des réseaux de capteurs sans fil ...........................................9 1.1 Introduction ..................................................................................................................9 1.2 Les réseaux ad hoc.........................................................................................................10 1.2.1 Définitions..................................................................................................................10 1.3 Les réseaux de capteurs sans fil ....................................................................................11 1.3.1 Introduction ........................................................................................................11 1.3.2 Définitions .........................................................................................................12 1.3.3 Comparaison entre les RCSF et les réseaux Ad hoc ..............................................14 1.3.4 Domaines d’applications .......................................................................................14 1.3.5 Architecture d’un réseau de capteurs ....................................................................17 1.3.6 La pile protocolaire des RCSF ..............................................................................18 1.3.6.1 La Couche physique ...............................................................................19 1.3.6.2 La Couche liaison de données .................................................................19 1.3.6.3 La Couche MAC : Medium Access control ..............................................19 1.3.6.4 La Couche réseau ..................................................................................20 1.3.6.5 La Couche de transport ............................................................................21 1.3.6.6 La Couche application ............................................................................21 1.3.7 Facteurs influençant la conception d’un réseau de capteurs ................................21 1.3.7.1 Le Coût ..................................................................................................21 1.3.7.2 Densité et taille du réseau ......................................................................22 1.3.7.3 Contrainte matérielle ...............................................................................22 1.3.7.4 Déploiement d’un Réseau de capteurs ..................................................23 1.3.7.5 Environnent ............................................................................................24 1.3.7.6 Media de transmission ............................................................................24 1.3.7.7 Energie consommée ................................................................................25 1.3.7.8 La tolérance aux fautes ............................................................................27 1.3.7.9 La sécurité ..............................................................................................27 1.3.8 La Connectivité ...................................................................................................28 1.3.8.1 Préliminaires ...........................................................................................28 1.3.8.2 Définitions ...............................................................................................29 1.3.9 La Couverture .....................................................................................................31 1.3.9.1 Définitions .............................................................................................31 1.3.10 La localisation ...................................................................................................34 1.3.10.1 Algorithme de localisation ...................................................................34 1.3.11 Le routage .........................................................................................................37 1.3.11.1 LEACH ................................................................................................37 1.3.11.2 TEEN et APTEEN .................................................................................39 1.3.11.3 Gossiping ............................................................................................40

1.3.11.4 Grad ......................................................................................................40 1.3.11.5 SPIN .......................................................................................................40 1.3.11.6 Routage géographique ............................................................................41 1.3.12 La durée de vie d’un réseau ................................................................................41 1.3.13 Les limites des réseaux de capteurs sans fil ........................................................41 1.4 Conclusion ....................................................................................................................43 1.5 Bibliographie ................................................................................................................44 2. La Surveillance ……………………………………………………………..49 2.1 Introduction .................................................................................................................49 2.2 La Supervision .............................................................................................................51 2.3 La Surveillance ............................................................................................................51 2.4 Surveillance Temps Réel .............................................................................................51 2.5. Terminologie propre à la surveillance ...........................................................................52 2.6 Classes de pannes .........................................................................................................54 2.7 Classification des défaillances selon leur origine ...........................................................55 2.8 Les modes de fonctionnement d’un système .................................................................57 2.9 La sûreté de fonctionnement ........................................................................................57 2.9.1 Introduction .........................................................................................................57 2.9.2 Entraves à la sûreté de fonctionnement .................................................................57 2.9.3 Attributs de la sûreté de fonctionnement ...............................................................58 2.9.4 Moyens d’assurer la sûreté de fonctionnement .....................................................60 2.10 Critères de performance d'un système de diagnostic ..................................................61 2.11 Panorama des méthodes employées en surveillance ...................................................62 2.12 Notion de redondance ................................................................................................63 2.12.1 Redondance matérielle .....................................................................................63 2.12.2 Redondance analytique ....................................................................................65 2.13 La Tolérance aux Fautes ............................................................................................66 2.13.1 Définition .......................................................................................................66 2.13.2 Techniques de tolérance aux fautes...................................................................67 2.13.3 Travaux existants pour les RCSF .....................................................................67 2.14 Mécanismes de survie classiques dans les réseaux ......................................................70 2.14.1 Restauration ....................................................................................................70 2.14.2 Protection ........................................................................................................70 2.15 Le cahier des charges de la surveillance .....................................................................70 2.16 Conclusion ..................................................................................................................72 2.17 Bibliographie ..............................................................................................................73 3. Modélisation des RCSF …………………………………………………..76 3.1 Introduction ............................................................................................................76 3.2 Modélisation par les graphes ...................................................................................76 3.3 Réduction du degré d'un graphe ...............................................................................78 3.3.1 Graphe de Gabriel (GG) .................................................................................79 3.3.2 Graphe du voisin relatif (RNG) .......................................................................80 3.4 Conclusion ..............................................................................................................83 3.5 Bibliographie ...........................................................................................................84

4. Proposition de solutions pour la surveillance d’un RCSF .......................85 4.1 Introduction .............................................................................................................85 4.2 Test et surveillance des RCSF ................................................................................85 4.2.1 Test en ligne ...................................................................................................86 4.3 Contexte de notre travail ..........................................................................................87 4.4 Travaux existants dans le domaine surveillance des RCSF .......................................87 4.5 Modélisation d’un RCSF...........................................................................................88 4.6 Déploiement des nœuds capteurs ..............................................................................90 4.7 Les stratégies tolérantes aux fautes ...........................................................................92 4.7.1 Stratégie pour garantir la connectivité du RCSF .............................................92 4.7.1.1 Objectifs ............................................................................................92 4.7.1.2 Travaux existants ...............................................................................93 4.7.1.3 Algorithme pour le système de prédiction de la connectivité ..............94 4.7.1.4 Évaluation de la robustesse du lien par un ensemble de chemins noeud-disjoints .................................................................................95 4.7.2 Stratégie pour garantir la couverture du RCSF ...............................................102 4.7.2.1 Travaux existants ...............................................................................103 4.7.2.2 La durée de vie de la couverture ........................................................103 4.7.2.3 Définition du problème .....................................................................103 4.7.2.4 Algorithme pour le système de prédiction des couvertures ................105 4.7.2.5 Évaluation de la robustesse des liens de couverture pour chaque cible .......................................................................................105 4.7.2.6 Approche d’une couverture minimale ................................................107 4.8 Conclusion ................................................................................................................113 4.9 Bibliographie ............................................................................................................114 4.10 Publications .............................................................................................................118 Conclusion Générale ......................................................................................................119 Annexes ..........................................................................................................................120 Annexe A : Simulation et Résultats ............................................................................121 Annexe B : Notions de base sur la théorie des graphes ...............................................125

1

Tables des figures

0.1 : Modules d’une procédure de surveillance ..............................................................5 1.1 : Exemple d'un réseau ad hoc ....................................................................................10 1.2 : Topologie d’un réseau Ad Hoc ................................................................................11 1.3 : Espace d'application des RCSF ...............................................................................15 1.4 : Application des réseaux de capteurs sans fil dans le domaine de la médecine...........16 1.5 : Un service militaire utilisant les réseaux de capteurs ...............................................16 1.6 : Déploiement des RCSF dans un champ d’agriculture .............................................17 1.7 : Déploiement des RCSF près d’un volcan ............................................................17 1.8 : Architecture de communication dans un RCSF .......................................................17 1.9 : La pile des protocoles d’un réseau de capteurs .....................................................18 1.10 : Structure du canal IEEE 802.15.4 .........................................................................19 1.11.a : Topologie en étoile .............................................................................................21 1.11.b : Topologie point à point ......................................................................................21 1.12 : Les composants d’un nœud capteur ....................................................................23 1.13.a : Energie consommée par les sous-systèmes d'un noeud capteur ...........................25 1.13.b : Energie moyenne consommée par un RCSF........................................................25 1.14 : Modèle d'énergie d’un nœud capteur..................................................................26 1.15 : Communication à sauts multiples .......................................................................29 1.16.a : Noeuds formant le réseau de capteurs ................................................................30 1.16.b : Porté de radio .....................................................................................................30 1.16.c : Connectivité des nœuds ......................................................................................30 1.17 : But de la connectivité .........................................................................................30 1.18.a : Couverture d’une région ....................................................................................32 1.18.b : Couverture de points .........................................................................................32 1.18.c : Couverture d’une barrière ..................................................................................32 1.19 : Relation entre connectivité et couverture ............................................................33 1.20 : Localisation par multilateration ..........................................................................35 1.21 : Illustration de la multilateration collaborative ...................................................36 1.22 : Illustration de la multiangulation ........................................................................36 1.23 : Modèle de Cluster, utilisé par LEACH ..............................................................38 1.24 : Dissipation de l’énergie dans le système ...........................................................38 1.25 : Dissipation de l’énergie dans le cas du protocole TEEN .....................................39 1.26 : Protocole Spin ..................................................................................................40 2.1 : Schéma de principe de la supervision .................................................................50 2.2 : Niveaux de modélisation et objectifs de diagnostic .............................................52 2.3 : Anomalies et Observations classées par criticité croissante .................................54 2.4 : Flux d’informations dans un système de surveillance .........................................55 2.5 : Biais de capteur .................................................................................................56 2.6 : Dérive capteur ...................................................................................................56 2.7 : Valeur aberrante ................................................................................................56 2.8 : Propagation d’une erreur ....................................................................................58 2.9 : La chaîne fondamentale des entraves ................................................................58 2.10 : Définition du MTBF ..........................................................................................59 2.11 : Relation entre MTTF, MTTR et MTBF ..............................................................59 2.12 : L’arbre de la sûreté de fonctionnement ...............................................................61 2.13 : Classification des méthodes de surveillance .......................................................63

2

2.14 : Redondance physique .........................................................................................63 2.15 : Détection à partir d’un modèle parallèle ..............................................................65 2.16 : Les techniques de tolérance aux fautes ................................................................67 2.17 : Protocole de contrôle de topologie CBTC ............................................................68 2.18 : Exemple de graphe avec l’algorithme MST..........................................................68 2.19 : Graphe de Yao.....................................................................................................69 3.1 : Connectivité et couverture dans un réseau de capteurs sans fil ............................77 3.2 : Exemples de Graphe Disk Unitaire .....................................................................77 3.3 : Structures utilisées dans les réseaux sans fil ........................................................79 3.4 : Le graphe de Gabriel............................................................................................79 3.5 : Configuration simple de RNG..............................................................................80 3.6 : Le graphe du disque unitaire de densité 8 ............................................................80 3.7 : Le graphe RNG associé au graphe disque unitaire .......................................80 3.8 : Comparaison entre les techniques de réduction de la complexité d’un GDU.........82 4.1 : Schéma du diagnostic en ligne pour un RCSF ........................................... 87 4.2 : Graphe de connectivité et couverture d’un RCSF .......................................88 4.3 : Graphe de dépendance d’un RCSF .......................................89 4.4 : Modèle d’un composant élémentaire .......................................89 4.5 : Déploiement des nœuds capteurs dans une grille .......................................91 4.6 : Déploiement pour assurer la couverture dans un local .......................................91 4.7 : Déploiement pour assurer la connectivité dans un local .......................................91 4.8 : Partitionnement du réseau dû à la mobilité des nœuds capteurs ...........................93 4.9 : Exemple de topologies ........................................................................................95 4.10.a : Réseau 1-connecté ........................................................................................................ 95 4.10.b : Réseau 2-connecté ................................................................................................... 95 4.10.c : Réseau 3-connecté ........................................................................................................... 95 4.11 : Évolution du nombre de chemins disjoints entre deux nœuds capteurs. ................96 4.13 : Graphe biconnexe ................................................................................................98 4.14 : Graphes à composantes biconnexes......................................................................98 4.15 : Graphe G (de connectivité) .................................................................................100 4.16 : T l’arborescence engendrée par la fouille .............................................................100 4.17.a : Points K-couvert ……........................................................................................102 4.17.b : Région K-couverte .............................................................................................102 4.18 : Déploiement aléatoire des capteurs pour l’observation des cibles ......................103 4.19 : Exemple avec trois cibles C = {c1, c2, c3} et quatre capteurs S ={s1, s2, s3, s4} 104 4.20 : Graphe biparti, couverture des cibles par les nœuds capteurs ..............................104 4.21 : Exemple d'affectation .........................................................................................108 4.22 : Couplage simple .................................................................................................110 4.23 : Chaîne alternée améliorante ................................................................................110 4.24 : Couplage maximal ..............................................................................................110 4.25 : Organigramme de Mise en veille des nœuds capteurs. .......................................112 4.26.a : Passage d’un capteur de nouveau en mode sommeil ...........................................112 4.26.b : Passage d’un capteur en mode active ..................................................................112 B.1 : Graphes non orientés...........................................................................................126 B.2 : Graphes biparti...................................................................................................128 B.3 : Augmentation d’un couplage à partir d’un chemin augmentant ...........................129

3

Liste des tableaux

1.1 : Comparaison entre les RCSF et les réseaux Ad hoc ................................................14 1.2 : Récapitulatif des protocoles de routage des RCSF ...................................................20 4.1 : Matrice d’adjacence du graphe biparti .....................................................................107

4

Introduction Générale

Depuis quelques années, le marché des réseaux et des applications sans fil s’est considérablement développé. De ce constat, une nouvelle branche s’est créée pour offrir des solutions économiquement intéressantes pour la surveillance à distance et le traitement des données dans les environnements complexes et distribués : les réseaux de capteurs sans fil (RCSF ou WSN : Wireless Sensor Networks).

Les réseaux de capteurs sans fil sont constitués de nombreux nœuds communiquant

généralement par ondes radio. Les capteurs ne sont pas intégrés à une quelconque architecture préexistante du réseau ; c’est pourquoi ils communiquent à l’aide d’un réseau ad- hoc sans fil. L’alimentation électrique de chaque capteur est assurée par une batterie individuelle, dont la consommation pour la communication et le calcul lié au traitement de l’information doit être optimisée. Le champ d’utilisation de tels réseaux touche les applications biologiques, chimiques, environnementales, la surveillance sismique et même la télésurveillance personnelle.

L’utilisation d’un modèle des réseaux de capteurs dans des environnements contraints, où la

qualité du service offert est primordiale, nécessite la mise en place d’une infrastructure de supervision qui puisse surveiller et contrôler les services reposant sur ce modèle, par exemple, dans le cadre de l’utilisation d’une infrastructure de RCSF, la mise en oeuvre d’une couverture maximale du réseau et la garantie d’une accessible à chaque usager est nécessaire. Or, dans un environnement où chaque noeud du réseau peut tomber en panne de manière imprévisible, entraînant ainsi un isolement de quelques parties du réseau, cette garantie n’est ni automatique ni aussi simple à assurer.

Les réseaux de capteurs font désormais partie de ces systèmes qu’il est crucial de surveiller.

L’intégration de mécanismes de supervision aux services des réseaux de capteurs sans fil est donc indispensable à leur utilisation sous contraintes de qualité de service, de la tolérance aux fautes, du bon fonctionnement du réseau tout au long de son exploitation et enfin l’augmentation de la durée de vie du réseau. Les approches de gestion actuelles sont nombreuses, mais chacun apporte une solution partielle au problème de surveillance et s’adaptent mal aux propriétés du modèle et contraintes nombreuses des réseaux de capteurs sans fil. De ce fait, le travail présenté ici concerne la proposition et la validation d’un modèle de surveillance des RCSF basé sur l’approche théorie des graphes, qui respecte les spécificités des RCSF.

Dans le passé, les systèmes automatisés de production ont aidé à assister l’opérateur dans

des tâches de conduite automatique du processus pour améliorer la qualité des produits finis, la sécurité et le rendement des unités industrielles. Le but essentiel était l’amélioration de la production en implantant des commandes performantes. Aujourd’hui, un autre défi est relevé : il s’agit de l’automatisation de la supervision des processus en utilisant un système intelligent fournissant à l’utilisateur une aide dans la gestion de ses tâches d’alarmes urgentes dans le but de faire augmenter la fiabilité et la sûreté de fonctionnement des processus.

Ces dernières années, les travaux de recherche sur le diagnostic ont mobilisé une large communauté de chercheurs. Terme peu répandu il y a une quinzaine d’années, le diagnostic aujourd’hui à pleinement conquis sa place. Le suivi du mode de fonctionnement d’un système est décrit par trois étapes:


5

- étape de la détection du mode sous lequel le système fonctionne (défaillant ou pas); - étape de l’identification et de la localisation de la cause du mauvais fonctionnement; - et l’étape du maintien du fonctionnement du processus, changement de sa configuration ou bien son arrêt définitif.

Selon [Brun90] et [Coir93], la surveillance nécessite la mise en oeuvre de nombreuses tâches décrites par la figure 0.1.

Figure. 0.1 – Modules d’une procédure de surveillance

Les communautés Automatique et Intelligence Artificielle ont toutes les deux consacré un bon nombre de travaux au développement d’algorithmes de détection et de localisation des défaillances. Ces algorithmes sont conçus à partir des méthodes à base de modèle, ou sur le traitement des signaux issus des procédés. Les techniques développées reposent sur la redondance d’informations présente sur les systèmes. Cette redondance peut être calculée à partir de la connaissance physique du système (modèles analytiques, modèles issus d’une phase d’apprentissage) ou bien uniquement à partir des informations délivrées par ses entrées et ses sorties.

Le diagnostic à l’aide des méthodes à base de modèle se fait selon deux étapes : la première étape consiste à générer les résidus à partir de la détermination des relations de redondance analytique [Fran90], [Iser84] ; la deuxième étape a pour but de décider l’état de fonctionnement du système. Généralement la décision se fait à l’aide d’un seuil fixé par apprentissage, au-delà duquel le résidu est déclaré anormal.

Dans le diagnostic à base de signal des processus, la décision se réalise au fur et à mesure que

la réception de données. Donc aucun modèle analytique n’est déterminé. Or, ce type de méthodes est adapté aux processus stationnaires où les caractéristiques et la structure des procédés ne varient pas. Ceci n’est pas toujours le cas quand il s’agit des systèmes en génies des procédés.


6

Ce mémoire s’inscrit dans ce courant d’automatisation de la supervision d’un réseau de capteur sans fil, puisque son objectif est de fournir une aide intelligente a un opérateur chargé de la surveillance d’un tel système. Etant donné un flot continu d’informations reçues par un centre de supervision, l’objectif de ce travail est la mise en place d’un système qui est en mesure d’analyser ce flot d’informations et d’en donner une interprétation plus compréhensible pour un opérateur humain. Le système supervisé étant réparti et de grande taille, l’idée de ce mémoire est d’adopter des stratégies tolérantes aux fautes, qui s’appuient sur la théorie des graphes et exploitant uniquement les informations fournis par les nœuds de capteurs et la topologie du réseau. L’objectif le plus important visé par ce travail, est la conception d’un système de supervision capable de détecter les problèmes au plus tôt afin de pouvoir assurer la qualité de service demandée par les utilisateurs finaux (sûreté, efficacité, disponibilité). L’un des défis de ce travail est de mettre en place des algorithmes pour la surveillance d’un RCSF, qui répondent a ces problèmes tout en étant les plus efficaces possible.

La complexité du problème vient en particulier du fait que les informations à traiter sont

nombreuses (taille du réseau, nombre d’informations dissipées dans le réseau,...) et que l’on cherche à établir plusieurs mécanismes qui assurent une tolérance aux fautes dans le réseau, pour une disponibilité et continuité des services connectivité et couverture.

Organisation du mémoire

Ce document a été organisé suivant différentes thématiques. Il se compose de quatre chapitres abordant des sujets connexes. Une conclusion générale et des perspectives sont données à la fin du document.

Le premier chapitre de ce mémoire, présente de manière plus en moins brève les bases

essentielles sur les réseaux de capteurs sans fil, afin d’en comprendre les mécanismes, les caractéristiques et les facteurs qui influencent la conception de ces types de réseau. Il met aussi en évidence leurs limites et les principales ressources et services misent en disposition, et qui nécessitent d’être surveillés pour que la durée de vie du réseau soit prolongée.

Le deuxième chapitre présente les motivations et le vocabulaire relatif à la surveillance et à la sûreté de fonctionnement, afin de se positionner par rapport à ce qu’on trouve dans la littérature scientifique. Il introduit la tolérance aux fautes comme un moyen de sûreté de fonctionnement. On termine ce chapitre par quelques notions sur la tolérance aux fautes puis enfin nous établirons un cahier des charges dans lequel nous définissons les besoins et les objectifs à atteindre par notre travail.

Le troisième chapitre définit des notions fondamentales sur quelques propriétés de la théorie

des graphes nécessaire pour la modélisation des RCSF. Le quatrième chapitre est plus formel, dans lequel nous présentons nos contributions pour la

surveillance du réseau, à l’aide de modèles et d’algorithmes inspirés de la théorie des graphes, pour chacun des problèmes détaillés dans le cahier des charges du chapitre 2 : Il s’agit de stratégies optimales, qui garantissent la tolérante aux fautes dans le réseau de capteurs sans fil.


7

Finalement, on donnera une conclusion générale que nous avons tirée du travail effectué durant la préparation de ce mémoire et nous proposons quelques perspectives pouvant ouvrir la voie à d’autres travaux dans le domaine de la surveillance des RCSF.

Présenté de façon très concise, l’annexe sur la théorie des graphes et les résultats de simulation est laissée à la fin du mémoire.


8

Bibliographie Les références sont classées alphabétiquement selon le nom du premier auteur. [Brun90] M. Brunet, D. Jaume, M. Labarrère, A. Rault et M. Vergé. Détection et diagnostic de

pannes Approche par modélisation. Traité des Nouvelles Technologies. Hermès, 1990. [Coir93] P. Coirault, J-D. Gabano et J-C. Trigeassou. Maintenance prédictive d’un entraînement

électrique par identification paramétrique. Diagnostic et sûreté de fonctionnement, 3(1) : 69–95, 1993.

[Fran90] P. M. Frank. , “Fault diagnosis in dynamic systems using analytical and knowledge-

based redundancy - a survey and some new results.” Automatica, 26(3):459—474, 1990.

[Iser84] R. Iserman. “Process fault detection based on modelling and estimation methods. A

survey ” Automatica, 20(4): 387 - 404, 1984.


9

Chapitre 1 Présentation des réseaux de capteurs sans fil 1.1 Introduction

L'essor des technologies sans fil offre aujourd'hui de nouvelles perspectives dans le domaine des télécommunications. En comparaison avec l'environnement filaire, l'environnement sans fil permet aux utilisateurs d'accéder et de manipuler des informations à travers des unités de calculs mobiles (PC portable, PDA, périphériques PC, capteur, ... etc.). De plus, avec les avancées récentes, en terme de performances et de miniaturisation, réalisées en microélectronique (microcontrôleur, DSP, transceiver RF, ... etc.), les applications liées au traitement mobile sans fil devraient être de plus en plus répandues. En effet, les réseaux sans fil offrent une grande flexibilité d'emploi. En particulier, ils permettent la mise en réseaux de sites dont le câblage serait trop onéreux à réaliser dans leur totalité, voir même impossible dans certains cas.

Les réseaux sans fil peuvent être classés en deux catégories : les réseaux avec infrastructure

fixe préexistante, et les réseaux sans infrastructure. Dans la première catégorie, le modèle de la communication utilisé est généralement le modèle cellulaire. Dans ce modèle, un point d'accès assure la liaison entres les terminaux mobiles et le réseau câblé, les utilisateurs peuvent se déplacer de manière transparente (sans perte de connectivité) d'un point d'accès à un autre à l'intérieur du réseau. La deuxième catégorie est celle des réseaux ad hoc que l'on verra en détail par la suite.

Chapitre 1 - Présentation des réseaux de capteurs sans fil

10

Dans ce chapitre, nous allons définir les réseaux ad hoc, puis donner les informations nécessaires pour comprendre la suite de ce manuscrit à savoir quelques informations généralistes sur les réseaux de capteurs sans fil. Puis, nous allons passer en revue la plupart des facteurs influencent la conception des réseaux de capteurs sans fil. On décrit ensuite de manière détaillé trois points essentielles dans un réseau de capteurs à savoir : la consommation de l’énergie, les problèmes de la connectivité et la couverture, sur lesquelles repose le but de notre travail, car si on doit surveiller un réseau de capteurs c’est pour des soucis : d’économiser l’énergie, d’assurer la connectivité et la couverture du réseau et maximiser la durée de vie globale du réseau.

Figure. 1.1 - Exemple d'un réseau ad hoc.

1.2 Les réseaux ad hoc

1.2.1 Définitions

Le terme « ad hoc » est une locution d’origine latine qui signifie « qui convient au sujet, à la situation. » On parle donc de réseaux auto-adaptatifs (capables de s’organiser par eux-mêmes). Une autre lecture de la définition peut signifier une propriété d’universalité de ce moyen de communication, comme si ce procédé pouvait satisfaire tous les besoins en terme de communication entre objets mobiles [Cart03].

La définition la plus concise d’un réseau ad hoc est la suivante : « un réseau ad hoc est un réseau sans fil à contrôle totalement décentralisé » [Cart03]. Par réseau sans fil, on entend que toutes les communications entre objets se font par voie aérienne, une interface radio dans chaque mobile permettant d’émettre et de recevoir. Le terme de contrôle décentralisé indique que l’ensemble des opérations pour la découverte et la maintenance du réseau se fait localement par chaque noeud. Chacun gère ses communications à partir des informations connues sur le réseau et sur l’état interne du noeud, dans le but de faire émerger un comportement cohérent du réseau (des routes correctement établies).

Les réseaux ad hoc peuvent inclure le concept de mobilité [Bans03]. Par mobilité, on désigne

le fait que chaque terminal peut se déplacer à l’intérieur du site, seul ou avec un groupe. Ces mouvements entraînent des changements dans les routes construites, ainsi que dans les caches d’information sur la topologie du réseau. Un noeud doit maintenir à jour ces informations et conserver dans un état valide les routes qui commencent, passent ou finissent par lui-même.


11

Le concept de mobilité inclut aussi certains états, tels que la déconnexion ou l’impossibilité de joindre le réseau. La topologie des réseaux ad hoc étant volatile et variable, chacun des membres peut quitter le groupe de communication sans avertissement. Ainsi, le fait qu’un noeud soit absent du réseau est un état normal, qui ne doit pas gêner les autres participants. Cette caractéristique doit être prise en compte à chaque couche du modèle réseau OSI : le routage doit se faire dans la mesure du possible (i.e. le noeud destinataire doit être joignable), de manière transparente, tout en s’adaptant aux déficiences d’une partie du réseau (en trouvant des chemins alternatifs par exemple).

Au niveau des couches supérieures (applications), chaque programme doit pouvoir accéder à des informations supplémentaires pour tenir compte de l’aspect changeant et sans garantie du réseau. Par exemple, il peut disposer d’outils lui indiquant la qualité d’un lien entre deux noeuds [Haus03, Haus05]. La figure 1.2, illustre la topologie d’un réseau Ad hoc.

Figure. 1.2 – Topologie d’un réseau Ad Hoc. 1.3 Les réseaux de capteurs sans fil 1.3.1 Introduction Le développement des réseaux sans fil et des réseaux mobiles ouvre une nouvelle ère dans le domaine des télécommunications, avec l’apparition du WIFI, de la téléphonie mobile, et les technologies des réseaux Ad hoc. Actuellement, l’essentiel de l’effort de recherche porte sur les réseaux mobiles et sur les problématiques liées aux réseaux ad hoc, car ces technologies couvrent tout le domaine lié au monde des réseaux (routage, gestion de la mobilité, auto configurabilité, qualité de service, redondance des architectures). La nature très variée de ces types de réseaux rend les performances de ceux-ci relativement faibles et mal adaptées aux applications industrielles. C’est pour cela qu’un autre type d’architecture de réseaux dit “ad hoc” trouve actuellement une application dans les réseaux de capteurs, plus connus sous le nom de Wireless Sensor Networks (WSNs), qui sont une technologie émergente issue des progrès de différents domaines. Ils ont en effet profité de la miniaturisation des composants électroniques, de l’augmentation de leur capacité (puissance de calculs, énergie, etc…), de la diminution des coûts de fabrication mais également des avancées dans les réseaux de communication sans-fil à travers l’essor des téléphones mobiles, des PDAs, etc.

.


12

Les technologies sans fils offrent de nouvelles perspectives dans le domaine des télécommunications et des réseaux. Les réseaux de capteurs sont des réseaux sans infrastructure fixe, qui doivent pouvoir être déployés de façon rapide, par exemple, dans des zones sensibles. Leur but est le plus souvent de surveiller une zone, de prendre régulièrement des mesures et de faire remonter des alarmes vers certains nœuds déployés qui sont en mesure de relayer l’information à grande échelle. La contrainte forte sur ces capteurs qui sont petits et donc limités en capacité (mémoire / CPU / énergie) est de maximiser la durée de vie du réseau, i.e., le processus de surveillance qu’ils sont censé mettre en œuvre [Chel04].

Les réseaux de capteurs trouvent des applications dans des réseaux sans fil et sans infrastructure ne nécessitant pas un débit élevé tel que la domotique ou l’agriculture intelligente. La réalisation de ce type de réseau requiert la mise en oeuvre de techniques développées pour les réseaux ad hoc; cependant, la plupart des protocoles développés pour ceux ci ne sont pas transposables tels que aux réseaux de capteurs. En effet, il convient de répertorier les spécificités de ces derniers [Chel04] [Poma04]:

� Les noeuds capteurs sont limités dans la puissance, les capacités de traitement et la mémoire.

� Consommation électrique faible; � Faible débit; � Auto configurabilité; � La topologie d'un réseau de capteurs change fréquemment. � Forte densité de noeuds; � Redondant et collaboratif; � Tolérant aux fautes. � Les noeuds capteurs peuvent ne pas avoir d'identification globale. � L’inévitabilité des interférences. Les transmissions radios ne sont pas isolées, et le

nombre de canaux disponibles est limité, ce qui force le partage. Les interférences peuvent être de natures diverses à savoir des émetteurs travaillant à des fréquences trop proches ; des bruits parasites dus à l’environnement; des phénomènes d’atténuation, de réflexion et de chemins multiples dus à l’environnement.

� La faible sécurité : il est facile d’espionner passivement un canal radio.

On peut alors s’apercevoir que les contraintes ne sont pas de même nature et vont nécessiter d’autres approches que celles actuellement développées dans le cadre des réseaux Ad hoc. 1.3.2 Définitions Définition 1: Les réseaux de capteurs utilisent un grand nombre de dispositifs très petits, nommés « nœuds capteurs », pour former un réseau sans infrastructure établie. Dans ces réseaux, chaque nœud est capable de détecter son environnement et de traiter l’information au niveau local ou de l’envoyer à un ou plusieurs points de collecte, à l’aide d’une connexion sans fil [Lamo06].


13

Définition 2: Un réseau de capteurs sans fil, est un réseau composé de nombreux petits nœuds indépendants, qui peuvent s’auto organiser. Les nœuds capteurs sont de taille d’une boite de film de 35 mm [Wik/org], se composant d’une batterie, d’une unité radio, d’une unité de capture et d’une unité de calcul. Définition 3: Les réseaux de capteurs sont, par définition, des systèmes à milliers de noeuds ayant une zone de couverture extrêmement réduite (de l'ordre de 3m), déployés d'une manière dense dans un environnement hétérogène. De plus, chaque noeud du réseau dispose d'une réserve énergétique (ex. pile) ayant une durée de vie limitée et dont le remplacement peut s'avérer impossible. Du fait d'une production quasi-industrielle, certains capteurs peuvent exhiber un comportement non prévu (non conforme a leur spécification), lorsqu'ils sont déployés sur le terrain et donc perturber les capteurs sains. Les réseaux de capteurs se trouvent à la confluence d'une variété de domaines de recherche: systèmes distribués, réseaux mobiles ad hoc, systèmes de (nano) robots, systèmes de pairs. Les réseaux de capteurs soulèvent un nombre de problèmes qui constituent chacun un défi à relever [Zhao03]. Les défis de ces réseaux sont un modèle unitaire qui doit inclure les caractéristiques suivantes :

1. Communication et agrégation d'information. La communication dans un réseau de capteurs doit prendre en compte, non seulement la mobilité, mais aussi la dégradation en énergie de chaque noeud participant au réseau. Ainsi, un modèle adapté à la spécificité des réseaux de capteurs peut être conçu en augmentant les solutions proposées dans le cadre des systèmes ad hoc en prenant en compte l'aspect énergétique. En particulier, l'échange efficace d'information entre les noeuds du réseau semble devoir se baser sur des techniques d'agrégation de l'information.

2. Connectivité du réseau. Dans un réseau de capteurs, le principal défi est de réaliser un

ensemble de tâches tout en dépensant le moins possible d'énergie. Par exemple, lorsque l'ensemble des capteurs transmet simultanément l'information, on peut assister à l'apparition d'interférences ou de collisions engendrant une perte significative de l'information transmise. Une mise en veille de certains capteurs devient nécessaire. Ceci conduit au problème de la couverture complète de la zone de déploiement, et cela d'une manière connexe, en dépit de capteurs inactifs.

3. Tolérance aux fautes. Deux causes majeures sont à l'origine des défaillances des capteurs

: leur production quasi-industrielle conduisant à des dysfonctionnements plus ou moins graves d'une partie non négligeable d'entre eux, et des comportements malveillants à l'origine d'intrusions difficilement détectables. Un premier défi sera donc d'identifier et de modéliser formellement les modes de défaillances des capteurs, puis de repenser les techniques de tolérance aux fautes à mettre en oeuvre sur le terrain.

4. Intelligence de groupe. Auto-organisation / auto-gestion. Le principe de localité est

fondamental dans les systèmes à grande échelle, fortement mobiles. Un premier objectif sera d'identifier les critères selon lesquels les noeuds peuvent s'auto-organiser, ainsi que la caractérisation des formes possibles d'auto-organisation intelligente (auto-gestion) lorsque les capteurs ont la capacité de se diriger librement dans leur région de déploiement.


14

1.3.3 Comparaison entre les RCSF et les réseaux Ad hoc Le tableau 1.1, présente une comparaison entre les réseaux de capteurs et les réseaux ad hoc [Chel04] :

Tableau 1.1 - Comparaison entre les RCSF et les réseaux Ad hoc

1.3.4 Domaines d’applications

Le champ d’applications visées pour les réseaux de capteurs est très vaste, ils trouvent leurs applications dans presque tout les domaines de la vie quotidienne [Akyi02] ; parmi celles-ci, on peut citer :

� Contrôle, surveillance et suivi de processus industriel (processus chimique); � Domotique; � Transport ferroviaire et automobile; � Détection d’intrusions et surveillance militaire; � Agriculture, détection de paramètres environnement aux complexes; � Exploration de l’espace � Séisme et désastre � Capteurs médicaux.

Dans les réseaux de capteurs, plus qu’ailleurs, la nature des applications va influencer le

protocole à implémenter. Par exemple, dans un réseau permettant la surveillance et l’étude de paramètres environnementaux tel que l’humidité, les capteurs devront être conçus pour avoir une grande autonomie (4 ans avec une pile AAA), un faible coût ainsi qu’une forte densité.

En revanche, les réseaux de type militaire auront pour leur part des protocoles plus orientés

sur la fiabilité du réseau.

Réseaux de capteurs (RCSF) Réseaux Ad hoc 1. Objectif ciblé 1. Générique / communication

2. Les nœuds collaborent pour remplir un objectif

2. Chaque nœud a son propre objectif

3. Flot de données « Many-to-one »

3. Flot « Any-to-any »

4. Energie est un facteur déterminant

4. Débit est majeur

5. Utilisation du broadcast 5. Communication point à point


15

La figure 1.3, montre un espace d'application des RCSF [Eiko05]. Cela permet la surveillance d'une grande variété de phénomènes environnementaux avec une qualité adéquate.

Figure. 1.3- Espace d'application des RCSF • Présentation de quelques domaines d’application

• Domaine de la médecine : cette technologie consiste en la surveillance de la

température, la fréquence cardiaque, l’oxygénation du sang et le pouls du patient [Deva04][Poma04], etc.

Par exemple :

On peut placer sur le corps d’un patient des capteurs qui surveillent constamment sa température, sa fréquence cardiaque, l’oxygénation du sang et son pouls.

Un émetteur – récepteur transmet les données à une station de base branchée à un ordinateur

personnel ou poste des soins infirmiers ou même à un assistant numérique.


16

Figure 1.4 : Application des réseaux de capteurs sans fil dans le domaine de la médecine.

• Le domaine militaire : qui constitue en la surveillance de zones sensibles, les

mouvements de l'ennemi, etc.

Par exemple :

On cas de guerre si on veut connaître les mouvements de l’ennemi, il est plus raisonnable de ne pas aller sur le terrain, il suffit simplement de survoler la zone à couvrir et de déployer les capteurs de l’hélicoptère afin qu’ils collectent les données et les transmettent à la station de base.

Ces RCSF peuvent fournir d’autres services tels que :

� La surveillance des munitions et des équipements militaires ; � L’évaluation des dommages ; � La connaissance de la position de ses propres soldats.

Figure 1.5. – Un service militaire utilisant les réseaux de capteurs


17

• Domaine de la sécurité et de l’environnement : système d’identification et d’authentification, la détection de feu dans les forêts, surveillance d'entrepôts chimiques, volcan, et zone de séisme, etc. Par exemple :

- Dans le cas des forets, on place des capteurs pour qu’ils puissent collectés les données et des actionneurs afin qu’ils actionnent des alarmes en cas de feux.

- Dans le cas de contrôle d’émigration des animaux, on peut rattachés des nœuds capteurs à l’animal.

Figure 1.6 - Déploiement des RCSF dans un Figure 1.7 - Déploiement des RCSF champ d’agriculture près d’un volcan 1.3.5 Architecture d’un réseau de capteurs Les nœuds capteurs sont habituellement dispersés aléatoirement à travers une zone géographique, appelée champ de captage, qui définit le terrain d'intérêt pour le phénomène capté. Les données captées sont acheminées grâce à un routage multi-saut à un nœud considéré comme un "point de collecte", appelé nœud puit (ou sink). Ce dernier peut être connecté à l'utilisateur du réseau via Internet ou un satellite. Ainsi, l'usager peut adresser des requêtes aux autres nœuds du réseau, précisant le type de données requises et récolter les données environnementales captées par le biais du nœud puits. La figure 1.8, montre l’architecture de communication dans un RCSF.

Figure. 1.8 - Architecture de communication dans un RCSF [Akyi04].

Nœuds capteurs


18

1.3.6 La pile protocolaire des RCSF

La pile de protocole employée par le Sink et tous les autres noeuds capteurs est donnée par la figure 1.9. Cette pile de protocole combine la gestion de la puissance et du routage, intègre les données avec les protocoles de gestion de réseau, communique la puissance efficacement à travers le média sans fil, et favorise les efforts coopératifs des noeuds capteurs. La pile de protocole comprend : la couche application, la couche transport, la couche réseau, la couche liaison de données, la couche physique, le plan de gestion de la puissance, le plan de gestion de mobilité, et le plan de gestion des tâches [Akyi02, Akyi04, Poma04].

Figure 1.9 - La pile des protocoles d’un réseau de capteurs. La norme IEEE 802.15.4 a été spécialement définie en fonction des caractéristiques des

réseaux de capteurs, un faible débit et une faible consommation électrique. Elle décrit le fonctionnement de la couche physique, et de la couche MAC. Pour la couche physique deux bandes de fréquence ont été retenues la bande 2.4 GHz et la bande 868 / 915 MHz, c’est au total 27 canaux de communication avec 3 différents débits possibles soit 16 canaux à 250 kbps dans la bande 2.4 GHz, 10 canaux à 40 kbps dans la bande 915 MHz, et 1 canal à 20 kbps dans la bande 868 MHz. Les réseaux qui supporteront la norme 802.15.4 pourront librement choisir d’utiliser l’un des 27 canaux utilisables en fonction de sa disponibilité et du débit recherché. L’émission dans la bande de fréquence 868 / 915 MHz s’effectue en utilisant la technologie DSSS (Direct-Sequence Spread Spectrum) et la modulation BPSK (Binary Phase Shift Keyring). La bande 2.4 GHz utilise également la technologie DSSS, mais avec une modulation O-QPSK La sensibilité minimale du récepteur définie dans la norme est de -82 dBm pour la bande 2.4 GHz et de -92 dBm pour la bande 868 / 915 MHz. Ces sensibilités permettent d’émettre à une puissance de 1 mW sur 10-20 m de rayon [Akyi02, Mazi05].

IEEE 802.15.4 MAC

Upper Layers

IEEE 802.15.4 SSCSIEEE 802.2

LLC, Type I

IEEE 802.15.42400 MHz

PHY

IEEE 802.15.4868/915 MHz

PHY

IEEE 802.15.4 MAC

Upper Layers

IEEE 802.15.4 SSCSIEEE 802.2

LLC, Type I

IEEE 802.15.42400 MHz

PHY

IEEE 802.15.4868/915 MHz

PHY

Couches supérieurs


19

La figure 1.10, illustre la bande de fréquence de la norme IEEE 802.15.4 [Blul05] :

Figure 1.10 – Structure du canal IEEE 802.15.4. 1.3.6.1 La Couche physique Deux différents médias peuvent être utilisés pour communiquer dans un réseau de capteurs sans fil : les infrarouges et les radiofréquences [Gran01].

Elle permet d’assurer une modulation simple et robuste, la transmission, et les techniques de réception. Elle est responsable de:

� choix de fréquence � génération de fréquence porteuse � détection et propagation de signal � modulation de signal et chiffrage de données.

1.3.6.2 La Couche liaison de données

La couche liaison de données est responsable du multiplexage du flux de données, de la détection des frames de données, d’accès au medium et du contrôle d'erreur. 1.3.6.3 La Couche MAC : Medium Access Control

Assure: � La création de l'infrastructure du réseau � Le Partage efficace des ressources de communication entre les noeuds capteurs

Quelques MAC pour les réseaux de capteurs : � Self-organizing medium access control pour les réseaux de capteurs et l'algorithme

Eaves-drop-and-register Algorithm � CSMA-Based Medium Access � Hybrid TDMA/FDMA-Based


20

1.3.6.4 La Couche réseau Elle Vise principalement :

� La gestion efficace de la puissance � Le routage efficace qui, minimise les flux, et économise de l’énergie. � L'agrégation de données quand cela ne gêne pas l'effort de collaboration des noeuds

capteurs. � Un réseau de capteurs idéal est basé sur un bon adressage et localisation.

On présente dans ce qui suit quelques types de protocoles de routage, le détaille sur ces protocoles sera traité dans la section 1.3.11. [Akyi02] :

Tableau. 1.2 - récapitulatif des protocoles de routage des RCSF • Topologies des RCSF

Deux topologies sont supportées par le protocole 802.15.4, la topologie en étoile, et la topologie point à point (voir les figures 1.11.a et 1 .11.b). Dans la topologie en étoile, les communications s’établissent directement entre le noeud central (coordinateur) et les capteurs, le coordinateur étant le noeud qui initie et gère les communications dans le réseau.

La topologie point à point (Peer to Peer) permet à chaque noeud du réseau de communiquer

avec n’importe quel autre noeud, ce qui permet de réaliser des réseaux ayant une architecture beaucoup plus complexe. La topologie point à point se rapproche alors plus du mode de communication tel qu’il est structuré dans un réseau ad hoc.

Protocole de routage Description

Flooding Diffuse les données à tous les noeuds voisins sans se soucier si elles les reçoivent avant ou pas

Gossiping Envoie les données à un voisin aléatoirement choisi

SPIN Envoie les données aux noeuds capteurs seulement s’ils sont intéressant ; Il a trois types de messages (ADV, REQ, DATA)

SAR Crée des arbres multiples où la racine de chaque arbre est un voisin d’un saut au Sink

LEACH Formes des clusters pour réduire au minimum la dissipation d'énergie

Directed diffusion Installent des gradients pour que les données passent de la source vers le Sink pendant une diffusion d'intérêt


21

La topologie point à point nécessite l’utilisation d’un protocole de routage (routage mesh, ad hoc...etc) qui doit être géré par la couche réseau, mais cette partie n’est pas définie dans le protocole IEEE 802.15.4. [Mazi05]

Figure 1.11.a - Topologie en étoile Figure 1.11.b -Topologie point à point 1.3.6.5 La Couche de transport

Cette couche est particulièrement nécessaire quand le système est prévu pour être consulté par

l'Internet ou d'autres réseaux externes. Le type de protocoles TCP/UDP répond à la plupart des exigences. Des informations détaillées sur la couche de transport sont précisées dans la littérature [Pott00].

1.3.6.6 La Couche application

Le protocole de gestion rend le matériel et logiciel des couches inférieures transparentes aux applications de gestion de réseau de capteur. On distingue les protocoles de gestion suivants [Akyi02] :

� Protocole de gestion de capteur (Sensor management protocol: SMP) � Task assignment and data advertisement protocol (TADAP) � requêtes de capteur et Protocoles de diffusion de données (Sensor query and data

dissemination protocol : SQDDP) 1.3.7 Facteurs influençant la conception d’un réseau de capteur

La conception d’un réseau de capteurs est influencée par beaucoup de facteurs, nous citons parmi ceux-ci : le coûts de production des capteurs, la densité, la tolérance aux fautes ; le passage à l’échelle, l’environnement d'opération ; la topologie du réseau de capteur ; les contraintes de matériel ; le média de transmission ; et la puissance d'énergie. Ces facteurs sont sujets de beaucoup de chercheurs. Cependant, aucune de ces études n'a une pleine vue intégrée de tous les facteurs. Ces facteurs sont importants parce qu'ils servent de directive pour concevoir un protocole ou un algorithme pour les réseaux de capteurs. En outre, ces facteurs influençant peuvent être employés pour comparer différentes solutions. 1.3.7.1 Le Coût Souvent, les réseaux de capteurs sont composés d’un très grand nombre de noeuds. Le prix d’un noeud est critique afin de pouvoir concurrencer un réseau de surveillance traditionnel. Actuellement un noeud ne coûte souvent pas beaucoup plus que 1$[Mazi05]. Le coût d'un noeud simple est très important pour justifier le coût global du réseau.


22

1.3.7.2 La Densité et taille du réseau

Le nombre de noeuds capteurs déployés dans l’étude d’un phénomène peut être de l'ordre des centaines ou des milliers. Il dépend de l'application, le nombre peut atteindre une valeur extrême des millions. La densité des noeuds peut être plus que 20 noeuds /m3. Les nouveaux schémas doivent pouvoir travailler avec ce nombre de noeuds. Ils doivent également utiliser la forte densité des réseaux de capteurs. La densité peut s'étendre de peu de noeuds de capteurs à quelques centaines de noeuds dans une région, qui peut être moins de 10 m de diamètre [ChoS00].

La densité µ peut être calculée selon [Bulu01] par la formule :

ARNR /)..()( 2πµ = (1.1) .

Où N est le nombre de noeuds capteurs dispersés dans la région A, et R la porté de transmission par radio.

La densité d’un réseau de capteurs donne une indication sur la possibilité qu’un réseau passe

à l’échelle. 1.3.7.3 Contrainte matérielle

Un noeud capteur se compose de quatre composants de base, comme montré dans la figure 1.12 [Akyi02] : une unité de collecte d’informations, une unité de traitement, une unité d'émetteur récepteur, et une unité de puissance. On peut aussi avoir des composants additionnels tels qu'un système de localisation, un générateur de puissance, et un système de mobilité. L’unité de collecte se composent habituellement de deux sous-unités : un capteur et un convertisseur analogique numérique (ADC). Les signaux analogiques produits par les capteurs basés sur le phénomène observé sont convertis en signaux numériques par le ADC, puis introduit dans l'unité de traitement. L'unité de traitement, qui est généralement associée à une petite unité de stockage, contrôle les procédures qui font collaborer le noeud de capteur avec les autres noeuds pour effectuer les tâches de collecte assignées. L’unité émettrice réceptrice relie le noeud au réseau. Un des composants les plus importants d'un noeud capteur est l'unité de puissance. Les unités de puissance peuvent être équipées par des unités de génération de puissance, telles que les piles solaires. Il y a également d'autres sous-unités dont dépendent les applications. La plupart des techniques de routage et des tâches de collecte exigent la connaissance d’une localisation avec une exactitude élevée. Ainsi, il est évident qu'un noeud de capteur ait un système de localisation d’endroit. Un système de mobilité peut parfois être nécessaire pour déplacer les noeuds capteurs.


23

Toutes ces sous-unités peuvent devoir s'adapter dans un module boîte d'allumettes. La taille

exigée peut être plus petite qu’un centimètre cube, qui est assez léger pour demeurer suspendu dans le ciel [Akyi02 , Mazi05].

Figure 1.12 - Les composants d’un nœud capteur 1.3.7.4 Déploiement d’un réseau de capteurs

Des centaines à plusieurs milliers de noeuds peuvent être déployées dans un champ de

capteurs. Déployer un nombre élevé de noeuds exige une maintenance continue de la topologie. Nous examinons en ce qui suit les techniques liées à l'entretien de la topologie en trois phases [Akyi02] : • Phase de Pré déploiement et déploiement : Des noeuds capteurs peuvent être déployés de manière aléatoire par un largage d'un avion, par artillerie, par un missile, ou placés de manière organisée un par un par un humain ou un robot. • Phase de post-déploiement : Après déploiement, les changements de topologie sont dus au changement de la position des noeuds capteurs, de l’accessibilité (dû à un blocage, d’un bruit, obstacles mobiles, etc.), de l'énergie disponible ou d’un défaut de fonctionnement. • Phase Redéploiement additionnelle : Des nœuds capteurs additionnels peuvent être redéployés à tout moment pour remplacer des noeuds en défaut de fonctionnement ou en raison de changement des tâches.


24

1.3.7.5 Environnent

Les noeuds capteurs peuvent être déployés en masse directement à l'intérieur du phénomène à observer. Par conséquent, ils fonctionnent habituellement sans surveillance dans des régions géographiques éloignées. Ils peuvent travailler à l'intérieur de grandes machines, au fond d'un océan, dans un champ biologique ou chimique contaminé, dans un champ de bataille au delà des lignes ennemies, dans un grand bâtiment ou à la maison, dans une foret ou attaché à un animal. 1.3.7.6 Media de Transmission

Dans un réseau de capteurs, les noeuds communicants sont liés par un média sans fil. Ces liens peuvent être constitués par la radio, l'infrarouge, ou les médias optiques. Une grande partie du matériel courant pour les noeuds capteurs est basé sur la conception de circuit RF. La radio de µAMPS, décrit dans [Gold03] emploie un émetteur récepteur Bluetooth de 2.4 gigahertz avec un synthétiseur de fréquence intégré. Le dispositif de basse puissance décrit dans [Eiko05] emploie un émetteur récepteur à canal unique de RF fonctionnant à 916 mégahertz. L'architecture intégrée du réseau de capteurs (WINS) [Gold03] emploie également les liens par radio pour la communication. Le module de communication utilise un mode de communication comme, par exemple la communication évènementielle ou la communication en client/serveur, et un protocole de communication ou type de transmission comme le WIFI, le Bluetooth, Zigbee, etc.

• Les Etats d’un noeud capteur

Un capteur est initialisé avant toute utilisation, c'est l'état Init. Puis il fonctionne selon trois

modes : le mode Actif où il exécute une fonction ou transmet un message, le mode Idle où il est seulement à l'écoute d'éventuels messages à recevoir et le mode Sleep où il est en veille. Enfin il se met dans l'état Stop lorsque la batterie est vide ou qu'il est mis hors tension (bouton OFF). Lorsqu'il est actif, le capteur peut envoyer et recevoir des messages (et seulement recevoir s'il est dans l'état Idle). La transmission des messages connaît trois états. Avant toute transmission, le module de communication du capteur (la radio) doit être dans l'état Idle, c'est-à-dire qu'aucune transmission n'est en cours sur le réseau. Le réseau doit être vide de message. Après quoi le capteur peut soit envoyer soit recevoir un message. La transmission des messages est décrite plus en détail dans [Lee02]. Un capteur ne peut pas envoyer et recevoir des messages simultanément. Il fonctionne en half duplex, c'est-à-dire qu'il ne fait qu'une transmission à la fois.


25

1.3.7.7 Energie consommée

Un noeud capteur sans fil, est un dispositif microélectronique, qui nécessite seulement une source d'énergie limitée (< 0.5 Ah, 1.2 V). La vie d’un noeud de capteur montre, donc, une dépendance forte à l’égard de la vie de batterie. Dans un réseau de capteurs chaque nœud joue les deux rôles émetteur et récepteur. De plus, chaque défaut de fonctionnement de quelques noeuds peut causer des changements topologiques significatifs et pourrait exiger le re-routage des paquets et la réorganisation du réseau. Cela nécessite, une conservation et une gestion optimale de l’énergie. C’est pour ces raisons aussi que les chercheurs concentrent actuellement leurs travaux sur la conception de protocoles qui prennent en considération la contrainte d’énergie limité. La tâche principale d'un noeud capteur est la détection des événements, l’exécution rapide des traitements locaux, puis la transmission des données. Ce qui permet diviser la consommation de l'énergie selon l’ordre décroissant suivants [Akyi02, Mazi05, Poma04, Salh01]:

� La communication (émission et réception) � traitement de données, agrégation � Acquisition ou capture des données

L’histogramme présenté par la figure 1.13.a, illustre la consommation de l’énergie par les

différents sous-systèmes d’un nœud capteur. Le graphe de la figure 1.13.b, montre la consommation moyenne en énergie [Teix04] : Figure 1.13.a - Energie consommée par les sous-systèmes d'un noeud capteur [Poma04].

Figure 1.13.b - Energie moyenne consommée par un RCSF.

Puis

sanc

e (m

W)

Traitement Radio


26

• Modèle d'énergie d’un nœud

Dans un noeud capteur les composants de communication consomment la majeure partie de l'énergie [Eiko05]. Un modèle simple pour un réseau sans fil peut être représenté par le schéma suivant [Salh01]:

Figure 1.14 - Modèle d'énergie d’un nœud capteur. La consommation électrique moyenne pour un noeud peut être définie ainsi [Mazi05]:

SPPP .)1(. 0 αα −+= (1.2)

SPP ≥0 Où : P = la consommation électrique moyenne α = le taux de fonctionnement Po = la puissance consommée à l’état actif Ps = la puissance consommée à l’état veille (mode sleep)

La consommation électrique pour la transmission d’un message de k-bits sur une distance d est donnée par la formule [Salh01] :

),()(),( dkEkEdkE ampTxelecTxTx −− += (1.3) αε dkkEdkE ampelecTx ∗∗+∗=),(

La consommation électrique pour la réception d’un message de k-bits est donnée par la formule :

)()( kEkE elecRxRx −= (1.4)

kEkE elecRx ∗=)(

Une grande partie de la recherche relative aux RCSF, sont la mobilité et les problèmes de l’énergie. En raison de ces conditions, la majeure partie de la littérature est concentrée sur la recherche des solutions à de divers niveaux du protocole de transmission, y compris l’énergie efficace. L’efficacité énergétique est souvent gagnée en adoptant une réduction de l’activité des nœuds capteurs. Les idées populaires d'économie de puissance incluent des noeuds spécialisés, la négociation, la fusion des données, et le réglage du porté de communication [Salh01].


27

1.3.7.8 La tolérance aux fautes

La tolérance aux fautes est la capacité de garantir les fonctionnalités du réseau de capteurs sous n'importe quelle interruption due aux échecs des noeuds capteurs. Les causes majeures qui sont à l'origine des défaillances des capteurs sont : leur production quasi-industrielle conduisant à des dysfonctionnements plus ou moins graves d'une partie non négligeable d'entre eux, des comportements malveillants à l'origine d'intrusions difficilement détectables. Le manque de puissance, les dommages physiques et l’interférence environnementale [Akyi02].

Un premier défi sera donc d'identifier et de modéliser formellement les modes de défaillances

des capteurs, puis de repenser les techniques de tolérance aux fautes à mettre en oeuvre sur le terrain.

En particulier les mécanismes traditionnels de détection de défaillances devront tenir compte

des composantes mobilité et autonomie du modèle. De plus, les solutions proposées dans le contexte des systèmes répartis (y compris les réseaux ad hoc) ignorent la dégradation énergétique du système, supposent a priori une forte connectivité du système et reposent sur l'hypothèse que chaque noeud du système a une connaissance globale du système. Ces hypothèses deviennent caduques dans les réseaux de capteurs en raison du coût de communication nécessaire pour obtenir cette connaissance.

1.3.7.9 La sécurité

Les RCSF connaissent actuellement une grande extension et une large utilisation dans différents types d'applications, dont celles exigeant une grande sécurité. Les contraintes qu’on a abordées précédemment dont une densité importante, une capacité de calcul et de stockage limitées, une communication sans fil et une ressource énergétique limitée, font que l'application des mesures classiques de sécurité est restreinte. Est donc delà la sécurité des réseaux de capteurs s’ajoute comme contrainte qui doit être prise en compte dès la conception des capteurs.

• Vulnérabilité

Les réseaux de capteurs sans fil possèdent certaines vulnérabilités [FeHu03] : - La première vulnérabilité est liée à la technologie sans fil sous jacente. Quiconque

possédant un récepteur adéquat peut potentiellement écouter ou perturber les messages échangés.

- Les nœuds eux-mêmes sont des points de vulnérabilité du réseau car un attaquant peut compromettre un composant laissé sans surveillance.

- L'absence d'infrastructure fixe pénalise l'ensemble du réseau dans la mesure où il faut faire abstraction de toute entité centrale de gestion pour l'accès aux ressources.

- Les mécanismes de routage sont d'autant plus critiques dans les réseaux RCSF, quand chaque nœud participe à l'acheminement des paquets à travers le réseau. De plus les messages de routage transitent sur les ondes radio.

• Défis de la sécurité

1- Le premier défi consiste à minimiser la consommation de l'énergie tout en maximisant les performances de sécurité. En effet, ces performances et les mécanismes de sécurité


28

utilisés sont fortement influencés par les capacités et les contraintes du nœud capteur, et l'énergie constitue l'essentiel des capacités du nœud. La plus grande partie d'énergie consommée par un nœud pour assurer la sécurité est reliée:

�� Au calcul requis pour les fonctions de sécurité, tels que le chiffrement, déchiffrement, signature des données, vérification de la signature.

�� A l'énergie requise pour la transmission des données de sécurité �� A l'énergie requise pour le stockage des paramètres de sécurité, tel que le stockage

de la clé de chiffrage.

2- La topologie des RCSF les rend exposés aux attaques, quelles soient passives ou actives. Contrairement aux réseaux filaires où la sécurité peut être renforcée par les firewalls, les attaques dans les RCSF peuvent survenir de toutes les directions et cibler n'importe quel nœud du réseau.

3- La communication sans fil caractérisant les RCSF, rend les schémas de sécurité utilisés dans les réseaux filaires impraticables.

1.3.8 La Connectivité 1.3.8.1 Préliminaires

Considérons un réseau de capteurs sans fil de communication à saut multiple (voir figure 1.15), où tous les noeuds coopèrent dans le but d’assurer des communications entre chacun. Un tel réseau peut être représenté de la manière suivante. Soit un graphe G = (V,E) représentant le réseau sans fil, avec V l’ensemble des noeuds et E ∈V2 les arcs donnant les communications directes possibles : (u, v) appartient à E si et seulement si u peut envoyer directement un message à v (on dit alors que v est voisin de u). Les couples appartenant à E dépendent de la position des noeuds et de leur portée de communication. Nous prenons l’hypothèse que la portée R de chaque noeud est identique. Soit d(u,v) la distance entre les noeuds u et v. L’ensemble E peut-être défini comme suit [Haus05] :

{ }RvudVvuE ≤∈= ),(),( 2 (1.5)

Ce graphe est connu sous le nom de graphe disque unitaire [Cla90], avec R comme rayon de

transmission. Dans ce graphe, G�= (V, E), nous définissons Vn = � comme le nombre de nœuds

dans le réseau. Le voisinage N(u) d’un noeud u représente l’ensemble des noeuds voisins de u, défini par { }Evuv ∈),/( .


29

Figure 1.15 - Communication à sauts multiples [Falc04]. 1.3.8.2 Définitions Connectivité : • Un réseau de capteurs est dit connecté si et seulement si il existe au moins une route entre

chaque paire de nœuds [Mer03]. La connectivité dépend essentiellement de l’existence des routes. Elle est affectée par les changements de topologie dus à la mobilité, la défaillance des nœuds, les attaques, etc … . Ce qui a pour conséquences : la perte des liens de communication, l’isolement des nœuds, la partitionnement du réseau, la mises à jours des routes et le reroutage, . . .etc.

• Un graphe G est dit a k-(arc) connectés s'il y a au moins k disjoint chemins entre deux noeuds quelconques Vvu ∈, . La connectivité est une mesure de tolérance aux fautes ou de diversité de chemin dans le réseau. La 1- connectivité est une condition fondamentale pour que le réseau soit opérationnel.

En effet la connectivité d’un réseau dépend de la densité du réseau [Mazi05]. Kleinrock et

Silverster [Klei78], ont montré que lorsque la densité du réseau µ(R) atteignait 6 noeuds, la probabilité qu’un noeud soit connecté tend vers 1, ie que le réseau forme un graphe connexe. La démonstration faite par Kleinrock et Silverster montre qu’il n’est pas possible d’envisager la création de réseaux sans fil si les réseaux en question ne possèdent pas une densité égale à 6 nœuds ou supérieure à cette limite. Exemple : Modélisation de la connectivité dans un réseau de capteurs sans fil

� Soit un déploiement de N capteurs, uniformément distribués dans une zone de taille LxL

� Deux nœuds capteurs n1 et n2 , de coordonnées respectives (x1, y1) et (x2,y2) , seraient reliés si et seulement si d(n1, n2) ≤ R.

d, étant la distance euclidienne, elle est définie par la formule suivante [Erwa04]:

d(n1,n2) = ))y-(y )x-((x 221

221 + (1.6)


30

Les figures suivantes, illustre la connectivité dans de tel réseau de capteurs :

Figure 1.16.a - noeuds formant le réseau de capteurs Figure 1.16.b - Porté de radio Figure 1.16.c - Connectivité des nœuds

Le but de la connectivité peut être récapitulé comme suit : On suppose avoir des événements à

capter x et nous souhaitons transmettre cette occurrence d’événement à y ∈ V. Nous voudrions pouvoir transmettre cette occurrence avec succès et avec une probabilité élevée pour touts x, y. La situation est illustrée ci-dessous [Inan03] :

Figure 1.17 - But de la connectivité

x : un événement si, y : des nœuds capteurs Ri: rayon de connectivité (porté de transmission) ri : rayon de couverture (porté de capture)

Ri

ri


31

Un chemin existe de x à y, si et seulement si il y a une séquence de nœuds dans un état de réception dans les position S0, S1, ….. , Sk tel que :

)(:1 0 capturéêtrepeutXrSXP i≤− ,

,)mod

,',...1(:2 11

réceptioneenestSsiseulement

etsiSàSdetransmisêtrepeutXévénementlkipourRSSP

i

iiiii −− =≤−

.)(:3 YàetransmettrpeutSRYSP kik ≤−

On peut dire que le chemin est à k sauts. Et que le réseau et à chemin connectés si et seulement si pour tout x, y ; il existe un chemin connectant x et y. 1.3.9 La couverture

Dans cette partie, on considèrent un réseau constitué de n capteurs si , i = 1…n , déployés pour surveiller une région d'intérêt qui est un secteur ou un ensemble de cibles. Un capteur peut prendre une des états suivants : émetteur, récepteur, tournent au ralenti, ou dorment. L'état de sommeil est quand la radio est éteint et l'état à vide est quand le transceiver ne fait ni transmission ni réception. Chaque capteur sj, peut être en activité sans interruption pendant un temps maximum bi. Soit ri et Ri noter respectivement la porté de capture des événements et la porté de communication du capteur sj. Notons que cela assure un secteur de capture du nœud sj grâce à un disque de centre le capteur sj et de rayon ri. Il sera de même pour la porté de communication. Un capteur couvre une cible q si et seulement si la cible q est dans le disque de capture de si. Formellement, on considère une cible comme un point, alors on peut définir [MyTT05, Card05, Ilya05 ]: 1.3.9.1 Définitions Couverture: La surface totale se trouvant en dessous du porté de capture des données [Podu05]. Couverture d’un point : On dit qu’un capteur si, couvre un point q si et seulement si la distance ii rsqd ≤),( [Ilya05].

Un modèle de couverture a été présenté par Meguerdichian et al. [Naev04], dans lequel la

capacité de capture de données par les noeuds capteurs diminue à mesure que la distance augmente. Un autre facteur important est le temps de capture (ou exposition), plus le temps d'exposition est long, plus la capacité de capture sera grande. Le modèle de capture bidimensionnel est défini par [Ilya05] :

[ ]k

psdpsS

),(),(

λ= (1.6)

Où d(s , p) est la distance euclidienne entre le nœud capteur s et le point p ; λ et k sont des paramètres de la technologie des capteurs.


32

Couverture d’une région : On dit qu’un capteur couvre une région A, si et seulement si pour chaque point q dans A, la distance ii rsqd ≤),( [Ilya05]. Les figures suivantes, illustre ces définitions :

Figure 1.18. (a) couverture d’une région, (b) couverture de points, (c) couverture d’une barrière

Deux capteurs peuvent communiquer directement l'un à l'autre si et seulement si chaque

capteur est à l'intérieur de la porté de communication de l'autre. Formellement, nous avons [Ilya05] : Communication Directe : Les capteurs si et sj peuvent communiquer directement l'un à l'autre si et seulement si jji Rssd ≤),( et iij Rssd ≤),(

Degré : c’est le nombre moyen des voisins à travers tous les noeuds. Un degré plus élevé de noeud peut fournir une meilleure couverture du réseau. Il est donné par la formule suivante :

n

iN

G Vi

∑∈=

)()deg( (1.7)

Spanning Ratio: Un graph G s'appelle c-spanner si pour tous u, v ∈V il existe un chemin p = (u = v0, v1, v2...., vl = v) de u à v dans G, avec :

),(.)(1

01 vudcvvdP

l

i

ii∑−

=

+ ≤= (1.8)

Où d (u, v) est la distance euclidienne. Si G est c-spanner, c s'appelle son spanning ratio. Le spanning ratio est un indicateur du nombre de saut entre deux noeuds il donne leur séparation.


33

Remarques :

- La couverture mesure la qualité du service d'un réseau de capteurs. Elle répond aux questions :

� A quel degré le réseau peut-il observer un secteur ?

• Les secteurs faiblement couverts peuvent bénéficiés de futurs déploiement ou reconfiguration.

� Quelle est la probabilité pour qu’un événement soit détecté dans une période de

temps ?

- Si le rayon de communication Rt > 2rc (rc : rayon de couverture) et la région à surveiller est couverte, alors la connectivité des nœuds capteurs est assurée. [Hwan05], (voir figure 1.19)

Figure 1.19 – relation entre connectivité et couverture


34

1.3.10 La localisation

L'information réceptionnée par un nœud capteur des autres noeuds, permet de calculer sa position physique. Cette information peut être aussi, employée par différents algorithmes tels que le routage basé sur la localisation.

Diverses recherches sont concentrées sur la détection des positions des noeuds capteurs. Par

exemple, Moore [Moor04] propose un algorithme qui localise avec succès des noeuds dans un réseau de capteurs avec des mesures de distance, n’utilisant aucune balize (beacons). Shang [Shan04] et Ji [JiXa04] utilisent la graduation multi dimensionnelle d' (MDS) pour identifier les positions des nœuds capteurs. Ceci emploie l'information de connectivité telle que les endroits des noeuds dans le réseau, et les distances estimées entre les voisins ou les positions connues pour certains noeuds. Cheng [Chen04] propose une technique de positionnement basé sur le temps (TPS). TPS se base sur TDoA (Time-Difference-of-Arrival) des signaux RF mesurés localement sur un nœud capteur pour détecter les différences des portés par rapport à trois stations de base. Ces différences sont ramenées à une moyenne avant qu'elles soient combinées pour estimer l'endroit du nœud capteur par le trilateration.

Le positionnement précis est une clé pour beaucoup d'applications dans les réseaux de

capteurs sans fil, comprenant la surveillance des réseaux, les capteurs robotiques, le routage basé sur la localisation, des espaces intelligentes et le contrôle de l'environnement par les capteurs mobiles. Bien que le GPS puisse potentiellement fournir un positionnement précis, la complexité des récepteurs exigés peut être trop coûteuse pour des nœuds capteurs peu coûteux. En outre, le signal de GPS est extrêmement faible et le positionnement peut être incertains à l’intérieur d’un bâtiment ou sous le feuillage dense. Ces inconvénients sur le positionnement de GPS ont mené à un intérêt croissant pour la recherche de méthodes GPS-less de localisation distribuées pour les réseaux de capteurs sans fil [Eiko05]. 1.3.10.1 Algorithme de localisation

À partir d'un nombre suffisant de mesures de distance ou d'angle, les positions des noeuds peuvent être estimées. En traitant des distances, ce processus s'appelle le multilateration, en traitant des angles sa s'appelle le multiangulation.

Proprement parler, la triangulation se rapporte à une localisation basée par angle avec trois

points de référence, mais le même terme est parfois employé pour toute distance ou évaluation de position basée par angle. • Multilatération Local

Le cas le plus simple du multilatéraion se présente quand un noeud inconnu estime sa position en utilisant un certain nombre de références et de distances connues.


35

On deux dimensions, avec n références connues R1, R2, …, Rn avec des coordonnées cartésiennes (Rix, Riy) , i = 1 … n, la position (Ux, Uy) d’un noeud inconnu peut être déterminé en utilisant les distances d(Ri, U) , comme dans [Gobe04]:

222 ),1()1()1( URdURUR YYXX =−+− 222 ),2()2()2( URdURUR YYXX =−+−

. (1.9) .

222 ),()()( URndURnURn YYXX =−+−

La figure 1.20, montre un exemple de multilateration local avec trois points de référence donnés.

Figure 1.20 – Localisation par multilateration

La figure 1.20, Multilateration : Mesurant les distances aux trois points de référence connus R1, R 2 et R 3, le noeud U peut déterminer sa position comme intersection de trois cercles.

Pour des noeuds qui ont moins de trois références disponibles, le multilateration local ne peut

pas être appliqué directement. Les solutions possibles incluent une solution itérative ou de collaboration. • Multilateration Iterative

Dans le cas d’une multilateration itératif, pendant chaque itération, tous les noeuds ont un nombre minimum de noeuds de référence disponibles (habituellement 3), qui estiment leurs positions. Dans la prochaine itération elles deviennent des références. De cette façon, l'information de position peut être propagée par le réseau de capteurs. À mesure que la distance des noeuds de référence augmente, l'exactitude de la localisation diminuée à cause des erreurs qui s'accumulent. L'ordre dans lequel les noeuds devraient estimer leur position peut être optimisé pour réduire les erreurs. Tant que de plus en plus de noeuds vont finir par savoir leurs positions, il sera bénéfique de raffiner itérativement les calculs précédemment faits. Un avantage de multilateration itératif est que le calcul peut simplement être fait localement sur les nœuds [Gobe04].


36

• Multilateration Collaborative

Le multilateration itératif n'aide pas dans le cas illustré dans la figure 1.21. Ici, chacun des deux noeuds inconnus "voit" seulement deux références. Cependant, comme montré dans [Savv01], elles peuvent résoudre un problème de collaboration de multilateration.

L'inconvénient principal du multilateration collaborative est qu’il exige un calcul centralisé. Le calcul centralisé est fortement indésirable, car il nécessite un échange considérable de message et n’est pas fiable dans un grand réseau. Récemment, Savvides et autres [Savv02], ont présentés des algorithmes se basant sur des calculs distribués pour la multilateration collaborative.

Figure 1.21 - Illustration de la multilateration collaborative

• Multiangulation

La Multiangulation est semblable à la multilateration, mais au lieu des distances, la multiangulation emploie des angles pour déterminer la position des nœuds capteurs [Hig01]. Dans le cas de deux dimensions, au moins deux angles avec des références et la distance entre ces références sont nécessaires pour déterminer la position d'un noeud inconnu, (voir la figure 1.22). Le sens d'arrivée de l'information peut être employé comme source unique pour la localisation ou en combinaison avec l'information de distance [Gobe04 ].

Figure 1.22 - Illustration de la multiangulation


37

1.3.11 Le routage

Le routage dans les réseaux de capteurs diffère du routage traditionnel, car le mode de communication dans les réseaux de capteurs est du type “plusieurs vers un” (n − to − one), ou “un vers plusieurs ” one − to − n, c’est à dire que les informations recueillies par les capteurs sont ensuite centralisées vers une passerelle. Les flux qui transitent sur le réseau ont pour unique destination la passerelle. Cette dernière centralise les informations recueillies par les capteurs.

Les protocoles de routage développés pour les réseaux de capteurs vont alors être beaucoup

plus simples que ceux crées pour les réseaux ad hoc, car les problématiques liées aux communications point à point dans les réseaux ad hoc augmentent beaucoup la complexité des tables de routage, de l’espace d’adressage ...etc.

Deux grandes familles de protocoles réseaux ont été suggérées pour les réseaux de capteurs.

La première famille regroupe les protocoles dont le but est de minimiser la consommation énergétique moyenne, en utilisant par exemple des algorithmes d’acheminement des paquets, et pour lesquels le critère de performance est la consommation électrique est primordiale.

La seconde famille regroupe pour sa part les protocoles dont le but est de limiter les flux applicatifs transitant sur le réseau. En minimisant ainsi les flux, le protocole permet d’économiser de l’énergie.

2.3.11.1 LEACH

LEACH [Akyi02, Hein02, Hein00] (Low-Energy Adaptive Clustering Hierarchy) est un protocole de routage destinée aux réseaux de capteurs. Son principal avantage est de minimiser la consommation énergétique des éléments du réseau. Le protocole LEACH est un protocole hiérarchique, car le réseau est divisé en clusters, et chaque cluster possède un noeud “maître”, le noeud maître est en charge de la gestion de son cluster. Il est élu périodiquement parmi les noeuds formant le cluster, en fonction de l’état de sa batterie.

Un message qui est émis par un noeud au sein d’un cluster, est ensuite routé par le noeud

maître vers la passerelle du réseau de capteurs. Si on considère que la distance entre le noeud maître et un noeud du cluster est faible, la puissance nécessaire à l’envoi d’un paquet entre eux est aussi faible qu’une communication directe entre un noeud et la passerelle.

Le protocole LEACH permet ainsi en structurant le réseau de manière hiérarchique de

proposer un protocole qui économise l’énergie d’un capteur désirant émettre un paquet.


38

La figure 1.23, illustre une architecture en cluster, utilisé par le protocole LEACH :

Figure 1.23 - Modèle de Cluster, utilisé par LEACH La figure 1.24, présente la dissipation de l’énergie dans le cas du protocole LEACH :

Figure 1.24 - Dissipation de l’énergie dans le système [Jing02].

Diamètre du réseau (m)

Ene

rgie

tota

le d

issi

pée

dans

le s

ystè

me

(jo

ule)


39

1.3.11.2 TEEN et APTEEN

TEEN (Treeshold sensitive Energy Efficient sensor Network protocol) [Agra01] est un protocole hiérarchique développé afin de répondre aux besoins de réseaux réactifs. En effet, la plupart des protocoles considèrent que les capteurs ne doivent transmettre l’information qu’au bout d’un certain temps. Autrement dit, les délais de transmission d’une information peuvent être longs. De plus, il s’ensuit que certaines mesures sont transmises inutilement, puisque n’intéressant pas la “gateway”. Les auteurs de [Agra01] ont donc proposés l’algorithme qui permet de remonter l’information suivante : une fois les clusters formés, la tête de cluster transmet deux seuils aux différents noeuds. Ces deux seuils, notés HT (Hard Treshosld), ST (Soft Tresholds) permettent aux capteurs de savoir s’il doit remonter l’information : le HT est la valeur minimum de la grandeur mesurée, au delà de laquelle le capteur est susceptible de transmettre l’information. Lorsque ces valeurs sont au-dessus du HT, le capteur ne transmet l’information que si la valeur courante diffère d’au moins ST unités de la valeur précédemment transmise. On peut donc contrôler le nombre de paquets envoyés en jouant sur ces deux valeurs. TEEN permet donc de construire un protocole réactif, ce qui permet d’économiser de l’énergie.

APTEEN (Adaptative Threshold sensitive Energy Efficient sensor Network protocol)

[Agra02], permet de trouver un compromis entre les protocoles proactifs (envoi de l’information à une dates données) et les protocoles réactifs (envoi de l’information suivant différents critères).

L’idée simple de (APTEEN) est de rajouter aux deux seuils précédemment décrits une troisième valeur, TC qui sera le temps maximal entre deux envois d’information mesurés. On assure ainsi qu’un capteur toujours vivant envoie périodiquement de l’information.

La figure 1.25, présente la dissipation de l’énergie dans le cas des protocoles TEEN et

APTEEN:

Figure 1.25 - Dissipation de l’énergie dans le cas du protocole TEEN [Jing02].

Ene

rgie

dis

sipé

e (

J)

Temps (s)


40

1.3.11.3 Gossiping

Gossiping est une technique de dissémination d’information dans laquelle chaque noeud qui reçoit un paquet à relayer, envoie le paquet reçu à un de ces voisins tirée aléatoirement [Akyi02].

1.3.11.3 Grad

Gradient Broadcast [FYeZ05] est un protocole qui permet d’acheminer les données transitant sur le réseau vers le noeud qui collecte les données. Pour cela le noeud qui collecte les données le (Sink) se charge de mettre en place des chemins qui relient les capteurs jusqu’à lui même. Pour construire les différents chemins, le noeud Sink diffuse sur le réseau un paquet dans lequel il déclare une métrique avec un coût à zéro. Les noeuds les plus proches qui reçoivent le paquet mettent à jour la métrique et retransmettent le paquet et ainsi de suite. Quand un capteur veut émettre une donnée, il envoie alors le paquet, au noeud qui a déclaré la métrique la plus faible pour aller au noeud Sink et le paquet est alors retransmis de noeud en noeud toujours en suivant la route qui possède alors la plus faible métrique. 1.3.11.4 SPIN

Le protocole SPIN [Hein99], permet de disséminer des informations sur le réseau de manière ciblée. Le fonctionnement du protocole SPIN permet de réduire la charge du réseau par rapport aux méthodes de diffusion traditionnelles tel que l’inondation ou l’algorithme de Gossiping. Le protocole SPIN utilise essentiellement trois primitives ADV/REQ/DATA. Un noeud voulant émettre une donnée commence par envoyer un paquet ADV. Les nœuds qui reçoivent ce paquet vérifient qu’ils n’ont pas encore répondu à cette demande auquel cas ils renvoient un paquet REQ. Le noeud qui a initié la communication envoie alors un paquet DATA pour chaque réponse REQ reçue (voir Figures 1.26). Un noeud peut parfaitement ne pas répondre aux sollicitations, par exemple dans le but d’économiser son énergie, sans pour autant mettre le fonctionnement du protocole en défaut. Ensuite chaque noeud qui fait office de relais peut très bien agréger ses propres données aux données qui sont déjà contenue dans le paquet.

Figure 1.26 - Protocole Spin : Étapes 1 à 6 montrent les trois messages (ADV, REQ, et DATA) utilisés dans le processus poignée de main (handshake).


41

1.3.11.6 Routage géographique

Le routage Géographique [Jain01] est une technique qui permet de résoudre en partie les problèmes de passage à l’échelle du routage dans les réseaux ad hoc. En effet cette technique propose un algorithme distribué de routage, basé sur la position géographique des noeuds dans le réseau. L’algorithme consiste à choisir dans la table de routage < (Pi, Si) > d’un noeud S, dans lequel Pi est la position géographique d’un noeud et Si l’adresse d’un noeud voisin, le noeud Si qui minimise la longueur du chemin à parcourir jusqu’à la destination D.

Ce protocole apporte une solution au problème de l’explosion des tables de routage dans les

réseaux ad hoc, car pour fonctionner cet algorithme n’a besoin que de la connaissance de la topologie du réseau, donc d’une table de routage restreinte. Ensuite on s’assure que le chemin parcouru par le paquet avec cet algorithme est optimal, car il est basé sur la distance géographique.

Bien que cet algorithme soit développé pour les réseaux ad hoc il est tout à fait possible de

l’utiliser dans le cadre des réseaux de capteurs car les problématiques au niveau du routage sont très liées.

1.3.12 La durée de vie d’un réseau

Plusieurs définitions coexistent dans la littérature. Une définition présentée dans [Mhat04] dit qu’un réseau de capteurs devient inutilisable lorsque la connectivité entre les nœuds est perdue ou lorsque le rôle de mesure ne peut pas être assuré sur toute la surface à couvrir. Dans [Bhar04], les auteurs définissent la durée de vie du réseau comme le temps cumulé d’activité du réseau. Dans [Mhat04], les auteurs définissent la durée de vie du réseau par la durée de vie du premier nœud capteur à tomber en panne à cause d’une perte d’énergie ou un problème catastrophique. 1.3.13 Les limites des réseaux de capteurs sans fil

Les réseaux sans fil et plus particulièrement les réseaux de capteurs sont limités dans leurs performances par des phénomènes physiques. Ces phénomènes physiques et leurs interactions sur le fonctionnement des protocoles ne sont généralement pas pris en compte dans les modèles qui sont développés.

Les limites connues dans les réseaux sans fil sont : la capacité du réseau qui évolue en

fonction de )( nθ bit-métre/s et le débit par noeud qui évolue en fonction de )1( nLogθ . Ce modèle permet de montrer que le débit chute très fortement en fonction du nombre de noeuds dans le réseau [Gupt00].

D’autres facteurs comme les problèmes de déconnexion, de non couverture, les contraintes

d’énergie, de sécurité physique limitée, d'absence d'infrastructure, de topologie dynamique, de panne des nœuds capteurs et de bande passante limitée, vont influencer les performances des RCSF.


42

A cet effet le but de ce travail est de proposer des solutions pour la surveillance d’un réseau de capteurs sans fil, pour un soucis d’augmenter sa durée de vie et d’assurer la tolérance aux fautes dans le réseau (pour que ces services restent disponibles malgré la présence d’éventuelles pannes des nœuds capteurs).


43

1.4 Conclusion

Nous avons présenté tout au long de ce chapitre, les caractéristiques et les facteurs influençant la conception des réseaux de capteurs sans fil. La description que nous avons faite sur les réseaux de capteurs fournira au lecteur les bases nécessaires à la compréhension de la suite du document et le sensibilisera aux problématiques liées à nos travaux.

Nous avons essayé d’expliquer de manière explicite les fonctions essentielles d’un RCSF, il

s’agit de la connectivité, la couverture et le problème de l’énergie, sur lesquelles se focalisent nos objectifs. Par ailleurs nous avons pu, souligné quelques limites des RCSF. Les problématiques de ce type de réseaux sont nombreuses et substantiellement différentes de celle des mondes filières.

Afin de résoudre ces limites par une surveillance permanente, nous présenterons dans le

prochain chapitre quelques définitions sur les concepts de la surveillance et son intérêt pour un réseau de capteurs sans fil.


44

1.5 Bibliographie [Agra01] A. M. D. Agrawal. TEEN: A Routing Protocol for Enhanced Efficiency in Wireless

sensor Networks. In IEEE Proceedings 15th International, pages 2009–2015, April 2001.

[Agra02] A. M. D. Agrawal. APTEEN : A Hybrid Protocol for Efficient Routing and

comprehensive Information Retrieval in Wireless Sensor Networks. In IEEE Proceedings 15th International, pages 195–202, April 2002.

[Akyi02] I F Akyildiz, W Su, Y Sankarasubramaniam and E Cayirci (Aug 2002) A survey on

sensor networks, IEEE Communications Magazine, 40(8), 102–114. [Akyi04] I. F. Akyildiz , «wireless sensor and actor networks» , School of Electrical and

computer Engineering Georgia Institute of Technology, 2004. [Bans03] N. Bansal and Z. Liu. Capacity, delay and mobility in wireless ad-hoc networks. In

Proc. IEEE INFOCOM 2003, San Francisco, USA, 2003. [Bhar04] M. Bhardwaj and A. Chandrakasan. Bounding the lifetime of sensor networks via

optimal role assignements. In INFOCOM 2004, Hong Cong, China, March 2004. IEEE.

[Bulu01] N. Bulusu, D. Estrin, L. Girod, J. Heidemann, Scalable coordination for wireless

sensor networks: self-configuring localization systems, International Symposium on Communication Theory and Applications (ISCTA 2001), Ambleside, UK, July 2001.

[Blul05] Bin Lu, Long Wu, Thomas G. Habtler, Rouald G. Harley, and José A. Gutiérrez, « On

the Application of Wireless Sensor Ntworks in Condition Monitoring and Energy Usage Evaluation for Electronic Machines», School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, USA, November 2005.

[Card05] Mihaela Cardei , Jie Wu , «Coverage in Wireless Sensor Networks», Florida Atlantic

University, 2005. [Cart03] Julien CARTIGNY, «Contributions à la diffusion dans les réseaux ad hoc », thèse de

doctorat, Université des Sciences et Technologies de Lille, 2003. [Chel04] G.Chelius, E. Fleury et T.Mignon .Broadcast, énergie et réseaux de capteurs sans fil.

CITI, Insa de Lyon – ARES, INRIA, 2004. [Chen04] Cheng, X. et al. , «TPS: A Time-Based Positioning Scheme for Outdoor Wireless

Sensor Networks. », Proc. Infocom, 2004.


45

[ChoS00] S. Cho, A. Chandrakasan, Energy-efficient protocols for low duty cycle wireless microsensor, Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, Maui, HI Vol. 2 (2000), p. 10.

[Clar90] B.N. Clark, C.J. Colbourn, and D.S. Johnson. Unit disk graphs. Discrete Mathematics,

86:165_177, 1990. [Deva04] V. Devabhaktuni. Hôpital du 21éme siècle .2004. [Eiko05] Eiko Yoneki, Jean Bacon, “A survey of Wireless Sensor Network technologies:

research trends and middleware’s role” , Technical Report, Number 646, University of Cambridge United Kingdom, ,September 2005.

[Erwa04] M. Erwan ERMEL, « Localisation et Routage géographique dans les réseaux sans fil

hétérogènes.», thèse de doctorat, Université Paris VI Pierre et Marie CURIE, 21 Juin 2004.

[Falc04] Alessio Falchi, «SensorNetworks», 2004 [FeHu03] Fei Hu, Neeraj K.Sharma. "Security consideration in ad hoc sensor networks".

26 Novembre 2003. [FYeZ05] F. Ye, G. Zhong, S. Lu, and L. Zhang. Gradient broadcast: A robust data delivery

protocol for large scale sensor networks. ACM Wireless Networks (WINET), 11(2), March 2005.

[Gobe04] Peter Gober1, Artur Ziviani2,3, Petia Todorova1, Marcelo Dias de Amorim2, Philipp

H¨ unerberg1 and Serge Fdida2 , «Topology Control and Localization in Wireless Ad Hoc and Sensor Networks. », Petropolis, Brazil, 2004.

[Gold03] Andrea J. Goldsmith, N. Bambos, Fouad A. Tobagi, “capacity and cross-layer design

of wireless ad hoc networks”, Stavros Toumpis July 2003 [Gran01] G. Le Grand, "Qualité de service dans les environnements Internet mobiles", Thèse

de doctorat de l'université de Paris VI, 2001. [Gupt00] P. Gupta and P. Kumar. Capacity of wireless networks. IEEE Transactions on

Information theory, IT-46, March 2000. [Haus03] M. Hauspie, J. Carle, and D. Simplot. Partition detection in mobile ad-hoc networks

using multiple disjoint path set. In 1st International Workshop on Objects models and Multimedia technologies (OMMT), Genova, Switzerland, 2003.

[Haus05] Michaël Hauspie, «Contributions à l'étude des gestionnaires de services distribués dans

les réseaux ad hoc », thèse de doctorat, Université des Sciences et Technologies de Lille, 2005.


46

[Hein99] W. Heinzelman, J. Kulik, and H. Balakrishnan. Adaptive protocols for information dissemination in wireless sensor networks. In Proceedings of 5th ACM/IEEE Mobicom Conference, Seattle, WA, August 1999.

[Hein00] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. , «Energy-efficient

communication protocol for wireless microsensor networks. »,In proceedings on 33r annual Hawaii International Conference on System Sciences, HICSS, pages 3005–3014, 2000.

[Hein02] W. B. Heinzelman, A. Chandrakasan, and H. Balakrishnan. , «An application-specific

protocol architecture for wireless microsensor networks. », IEEE Transactions on Wireless Communications, 1(4):660–6670, October 2002.

[Hwan05] Ten-Hwang Lai, «Coverage and Connectivity Issues in Sensor Networks», Ohio

State University, 2005. [Ilya05] Mohammad Ilyas and Imad Mahgoub , «Handbook of Sensor Networks: Compact

Wireless and Wired Sensing Systems», Printed in the United States of America, 2005. [Inan03] Metin Inanc, Malik Magdon-Ismail and Bulent Yener , «Power Optimal Connectivity

and Coverage in Wireless Sensor Networks», Department of Computer Science, Rensselaer Polytechnic Institute, New York, USA, 2003.

[Jain01] R. Jain, A. Puri, and R. Sengupta. Geographical routing using partial information for

wireless ad hoc networks. In Proceedings of IEEE Personal Communications, volume 8, pages 48–57, Febuary 2001.

[Jing02] Jing Li, «A Survey on Wireless Sensor Networks», Electrical Engineering

Telecommunication and Information Technology Laboratory Department of Electrical and Computer Engineering Mississippi State University, October 2002.

[JiXa04] Ji, X. et al. , «Sensor Positioning in Wireless Ad-hoc Sensor Networks with

Multidimensional Scaling. », Proc. Infocom, 2004. [Klei78] L. Kleinrock and J. Silvester. Optimum transmission radii for packet radio networks or

why six is a magic number. In National Telecommunications Conference, Birmingham, Alabama, pages 4.3.2–4.3.5, December 1978.

[Lamo06] Louise Lamont, [email protected], Centre de recherches sur les communications

Canada CRC. Juin 2006. [Lee02] Nelson Lee, Philip Levis, Jason Hill, « Mica High Speed Radio Stack », 11 Septembre

2002. [Mazi05] Alexandre Delye de Mazieux, Vincent Gauthier, Michel Marot, Monique Becker,

« Etat de l’art sur les réseaux de capteurs », Rapport de Recherche INT N°05001RST, Institut National des Télécommunications, Evry, France, Avril 2005.


47

[Mera03] Rabah Meraihi, «Gestion de la qualité de service et contrôle de topologie dans les réseaux ad hoc», Thèse de doctorat, Ecole nationale supérieure des télécommunications, TELECOM Paris, 2003.

[Mhat04] V. Mhatre and C. Rosenberg, D. Kofman, R. Mazumdar, and N. Shroff., «Design of

surveillance Sensor grids with a lifetime constraint. », In European Workshop on Wireless Sensor Networks (EWSN), Berlin, Germany, January 2004.

[Moor04] Moore, D. et al. , «Robust distributed network localization with noisy range

measurements. », Proc. SenSys, 2004. [MyTT05] My T. Thai Feng Wang Ding-Zhu Du, «Coverage Problems in Wireless Sensor

Networks: Designs and Analysis», Dept. Of Computer Science & Enginering, University of Minnesota inneapolis, 2005.

[Naev04] Marco Naeve, “IEEE 802.15.4 MAC Overview ” ,Company Eaton Corporation, 4201

North 27th Street, Milwaukee, WI 53216, USA , 10 May, 2004. [Podu05] Sameera Poduri , Sundeep Pattem, Bhaskar Krishnamachari, Gaurav Sukhatme,

«A unifying framework for tunable topology control in sensor», University of Southern alifornia, USA, 2005.

[Poma04] Carlos Pomalaza-Ráez, « Wireless Ad Hoc & Sensor Networks », University of Oulu,

Finland, 2004. [Pott00] G.J. Pottie, W.J. Kaiser, Wireless integrated network sensors, Communications of the

ACM 43 (5) (2000) 551–558. [Savv01] A Savvides, C-C Han and M B Strivastava (2001) , «Dynamic fine-grained localization

in ad-hoc networks of sensors», Proceedings of the seventh annual international conference on Mobile computing and networking, 166–179.

[Savv02] A Savvides, H Park and M B Srivastava (2002) , «The bits and flops of the n-hop

multilateration primitive for node localization problems», Proceedings of the first ACM international workshop on Wireless sensor networks and applications, 112–121.

[Shan04] Shang, Y. et al. , «Improved MDS-Based Localization. », Proc. Infocom, 2004. [Teix04] Ingrid Teixeira, José Ferreira de Rezende and Aloysio de Castro P. Pedroza, «Wireless

Sensor Network: Improving the Network Energy Consumption»,Simposio Barasileiro de Telecommunicaçoes, Setembro 2004


48

[Wik/org] www.en.wikipedia.org/wiki/Wsn [Zhao03] Jerry Zhao. Ramesh Govindan. Deborah Estrin, «Computing Aggregates for

Monitoring Wireless sensor Networks », University of Southern California, Los Angeles, 2003.


49

Chapitre 2

La Surveillance

L’objectif de ce chapitre est de présenter le vocabulaire relatif à la surveillance et la “sûreté de fonctionnement” et d’introduire la tolérance aux fautes comme un moyen de la sûreté de fonctionnement. Nous y présentons les techniques utilisées pour réaliser la tolérance aux fautes. Enfin, dans la dernière section, nous précisons dans un cahier des charges, l’approche choisie dans le contexte de notre travail.

Comme notre travail se focalise sur la partie tolérance aux fautes FTC (Fault Tolerance

Control), un résumé des méthodes FTC dédiées aux réseaux de capteurs sans fil sera développé dans ce chapitre.

2.1. Introduction

Parmi les objectifs les plus importants de l’automatisation aujourd’hui concerne l’augmentation de la fiabilité, de la disponibilité et de la sûreté de fonctionnement des processus technologiques. C’est la raison pour laquelle on met en oeuvre des systèmes de surveillances dont l’objectif est d’être capable, à tout instant, de fournir l’état de fonctionnement des différents équipements constitutifs d’un processus technologique.

Tant au niveau de la détection et de l’isolation des fautes (FDI) qu’au niveau de la tolérance

aux fautes (FTC: Fault Tolerant Control), l’opérateur de supervision gère deux types d’information. Le premier concerne la détection et l’isolation de défauts survenus sur l’installation, et le deuxième indique les possibilités de laisser fonctionner ou non le processus.

Chapitre 2 - La Surveillance

50

La figure. 2.1 résume, le principe de la FDI et de la FTC.

Figure. 2.1 - Schéma de principe de la supervision Au niveau de la FTC, deux approches sont à distinguées: l’approche passive et l’approche active [Patt97]. L’approche passive est basée sur la commande robuste qui vise à définir pour les systèmes contrôlés en boucle fermée, des régulateurs insensibles aux fautes. Aucune information sur les défaillances fournies par les algorithmes de FDI n’est utilisée, ainsi que la structure du système n’est pas modifiée. Par contre, l’approche active, comme son nom l’indique, utilise les informations du module FDI en temps réel pour adapter le système à sa nouvelle situation en cas d’occurrence de défaillances. Les travaux de recherche sur la surveillance ont mobilisé ces dernières années une large communauté de chercheurs. Car, il faut dire que la surveillance était peu répandue il y a une quinzaine d’années. Aujourd’hui en raison, d’une part des contraintes économiques de compétitivité accentuées par la mondialisation, et d’autre part de la sûreté de fonctionnement, la surveillance a pleinement conquis sa place, surtout pour les processus en génie des procédés en raison de leur caractère à risque (processus chimique, nucléaire, etc ...). De plus le souci de la protection de l’environnement est une raison supplémentaire de l’importance de la surveillance de ce type de procédé [Mran04].


51

2.2 La Supervision

La supervision a pour but de contrôler l'exécution d'une opération ou d'un travail effectué par d'autres sans rentrer dans les détails de cette exécution. La supervision recouvre l'aspect fonctionnement normal et anormal : − En fonctionnement normal, son rôle est surtout de prendre en temps réel les dernières décisions correspondant aux degrés de liberté exigés par la flexibilité décisionnelle. Pour cela, elle est amenée à faire de l'ordonnancement temps réel, de l'optimisation, à modifier en ligne la commande et à gérer le passage d'un algorithme de surveillance à l'autre ; − En présence de défaillance, la supervision va prendre toutes les décisions nécessaires pour le retour vers un fonctionnement normal. Après avoir déterminé un nouveau fonctionnement, il peut s'agir de choisir une solution curative, d'effectuer des réordonnancements "locaux", de prendre en compte la stratégie de surveillance, de déclencher des procédures d'urgence, etc. 2.2 La Surveillance

Toute prise de décision est basée sur les informations acquises des ressources et de l’historique des activités exécutées. La surveillance est responsable de l’acquisition des signaux en provenance des ressources et de la commande. Ces informations sont utilisées pour la reconstitution de l'état réel du système commandé, et pour faire les inférences nécessaires afin de produire les données utilisées pour reconstituer l’état réel du système ou pour dresser des historiques de fonctionnement.

Les activités de la surveillance sont donc limitées aux fonctions relatives aux informations (la collecte, le stockage, les inférences, etc.). A priori, la surveillance a un rôle passif vis-àvis de la commande. Toutefois, elle peut agir sur le procédé pour tester une ressource et obtenir les informations nécessaires sur son état.

La surveillance représente une interface entre l’opérateur et l’installation physique, son rôle est de fournir les informations sur l’état de fonctionnement (correct ou erroné) des dispositifs surveillés ainsi que valider les informations issues des capteurs et localiser les composants défaillants.

La surveillance se réalise à l’aide des algorithmes conçus pour traiter les données brutes (issues des automatismes et des opérateurs) et les données mesurées (issues des capteurs) dans l’objectif de produire des données dont l’efficacité a été prouvée par le système. Il s’agit des données valides.

2.4 Surveillance Temps Réel

Il est souhaitable mais souvent difficile d’obtenir le moment précis du début d’un défaut sauf lorsque les symptômes sont d’apparition récente. Le début peut être brutal ou progressif. L’évolution dans le temps peut être permanente ou intermittente, il est nécessaire de savoir si le symptôme s’est aggravé dans le temps c-à-d s’il a augmenté d’intensité ou de fréquence. Toutes ces préoccupations doivent être soumises à l’action d’une surveillance temps réel et c’est l’unique moyen disponible pour rechercher et regrouper les symptômes si l’on projette de découvrir le défaut à son origine.


52

2.5 Terminologie propre à la surveillance

Il semble intéressant, de rappeler les principaux termes utilisés dans la surveillance des systèmes. La terminologie suivante sera adoptée [Buss02, Toua05]:

• Système physique

Un système physique est un ensemble d’éléments (composants, constituants) interconnectés ou en interaction organisés pour réaliser une fonction.

• Composant

Un composant industriel est un organe technologique qui forme une partie du processus industriel (Nœud capteur, station de base, ...). Ce dernier peut être affecté par des pannes.

• Modèle

Un modèle d’un système physique est une description de sa structure et une représentation comportementale ou fonctionnelle de chacun de ses composants. Une représentation comportementale est constituée de relations entre diverses variables du système, appelées classiquement relations de causes à effets. Une représentation fonctionnelle est plus abstraite puisqu’elle ne s’adresse qu’aux objectifs présumés que le système physique doit remplir (qui pourraient être définies par un cahier des charges comme un temps de réponse ou un rendement à satisfaire). D’où le concept de raisonnement téléologique exprimé par Milne [Miln87] à la figure 2.2, exprimant l’idée que seule la finalité du système (c’est-à-dire ce pourquoi il a été conçu) nous intéresse.

Le niveau structurel, quant à lui, s’appuie sur la structure réelle du système physique et décrit

les interconnections entre ses différents éléments ou constituants. Les niveaux comportemental et fonctionnel comprennent des relations entre des grandeurs physiques (variables) et permettent de mettre en évidence la présence d’un événement normal ou anomalie. Le niveau structurel, quant à lui, permet de déterminer l’élément affecté par le défaut. L’intérêt de cette décomposition est de rappeler que, puisqu’un modèle contient toute l’information relative à un système physique, il est utilisable ensuite par la procédure de diagnostic.

Figure 2.2 - Niveaux de modélisation et objectifs de diagnostic.


53

• Défaut − Tout écart entre la caractéristique observée sur le dispositif et la caractéristique de référence, lorsque celui-ci est en dehors des spécifications. − N'importe quel état indésirable d'un composant ou d'un système. Un défaut n'implique pas nécessairement une défaillance. − Déviation non permise d'au moins une propriété ou un paramètre caractéristique du système des conditions acceptables ou (et) standards. − Un défaut est une anomalie de comportement au sein d'un système physique localisée au niveau d’un composant.

• Défaillance

Une défaillance définit une anomalie fonctionnelle au sein d’un système physique, c’est-à-dire caractérise son incapacité à accomplir certaines fonctions qui lui sont assignées.

Les défauts incluent les défaillances mais la réciproque n'est pas vraie. Un système peut remplir sa fonction tout en présentant une anomalie de comportement. Par exemple, le bruit anormal est un défaut qui peut permettre de présager d'une défaillance à venir. La recherche de défauts est donc fondamentale en diagnostic.

• Fautes Une faute est caractérisée par sa nature, son origine et son étendue temporelle. Une panne est

une interruption permanente de la capacité du système à réaliser sa fonction requise. Il est clair que dès l’apparition d’une défaillance, caractérisée par la cessation du dispositif à accomplir sa fonction, on déclarera le dispositif en panne. Par conséquent, une panne résulte toujours d’une défaillance.

• Erreur

Une erreur est définie comme l’écart entre une valeur mesurée ou estimée d’une variable et la vraie valeur spécifiée par le modèle d’un capteur jugé théoriquement correcte.

• Symptôme

Caractère distinctif d'un état fonctionnel anormal.

• Contraintes Les contraintes sont les limitations imposées par la nature (lois physiques) ou l’opérateur. . • Résidu

Un résidu ou indicateur de faute exprime l’incohérence entre les informations disponibles et les informations théoriques fournies par un modèle (supposées décrire correctement le processus).

• Diagnostic Le diagnostic des systèmes permet d’identifier les causes possibles de la défaillance. Il a pour

objectif de fournir les informations sur l’instant et sur l’amplitude de la défaillance. • Perturbation

Entrée du système physique qui n’est pas une commande. Autrement dit, c’est une entrée non contrôlée.


54

La figure 2.3, représente les anomalies suivant leur criticité croissante [Adro00]. Il existe également une criticité croissante entre défaillance et panne. De la non conformité (ou anomalie) dans le cas d’une défaillance, on passe à une inaptitude à accomplir une fonction dans le cas d’une panne.

Figure 2.3 - Anomalies et Observations classées par criticité croissante. 2.6 Classes de pannes

La capacité d’identification du modèle de pannes joue un rôle très important si l’on veut réaliser la tolérance aux pannes. En effet, les conséquences et le traitement d’une panne diffèrent selon son modèle. Les pannes peuvent être classées selon plusieurs critères : leur degré de gravité, leur degré de permanence et leur nature.

Un premier classement des pannes selon le degré de gravité des défaillances [Aviz04] conduit à :

– pannes franches (crash fault) : soit le système fonctionne normalement (les résultats sont

corrects), soit il ne fait rien. Il s’agit du modèle de panne le plus simple auquel on essaie de se ramener chaque fois que cela est possible ;

– pannes par omission : des messages sont perdus en entrée et/ou en sortie. Ce type de panne est utilisé pour les réseaux ;

– pannes de temporisation : les déviations par rapport aux spécifications concernent uniquement le temps (typiquement le temps de réaction à un événement);

- pannes par valeurs : les résultats produits par un composant défaillant sont incorrects; - pannes byzantines : le système peut faire n’importe quoi, y compris avoir un comportement

malveillant. Un second classement des pannes selon leur degré de permanence [Aviz04] est également possible :

– panne transitoire : elle se produit de manière isolée ; – panne intermittente : elle se produit aléatoirement plusieurs fois ; – panne permanente : elle persiste dès qu’elle apparaît jusqu’à réparation.


55

On utilise également un troisième classement selon la nature de la panne [Aviz04] : – pannes accidentelles : elles se produisent de manières accidentelles ; – pannes intentionnelles : elles sont créées avec une intention qui peut être malicieuse.

2.7 Classification des défaillances selon leur origine Une classification en fonction du type du composant du système qui est à l’origine d’une

défaillance a été proposée par [Carp99]. Elle considère qu’un système possède trois types de composants ayant des fonctionnalités différentes : les capteurs (pour la mesure), les actionneurs (pour la mise en oeuvre de la commande) et le système proprement dit. Une défaillance peut provenir donc, soit d’un capteur, soit d’un actionneur soit des composants du système.

Figure 2.4 - Flux d’informations dans un système de surveillance. 1) Une défaillance de capteur (défauts du type (B) sur la figure 2.4) se traduit par le fait que la mesure fournie par ce capteur ne correspond pas à la réalité car elle est entachée d’une erreur. 2) Une défaillance d’actionneur (défauts du type (A) sur la figure 2.4) se traduit, quand à elle, par le fait que l’actionneur ne réagit pas correctement à la commande qui lui est imposée. 3) Une défaillance du système (défauts du type (C) sur la figure 2.4) correspond à une modification permanente et suffisante de ses caractéristiques physiques.

Pour concevoir un système de diagnostic, il faut d’abord savoir ce que l’on veut détecter cela

revient essentiellement à définir le type de défauts susceptibles d’altérer le bon fonctionnement d’un système. Ce dernier peut être divisé en trois catégories différentes [Ripo99].:

• Les biais, • Les dérives, • Les valeurs aberrantes,

En fait, qu’il s’agisse de défauts liés aux capteurs ou aux actionneurs ou aux composants du

processus (comme illustré dans la figure 2.4, ils se traduisent par une modification du signal associé.


56

Un biais correspond à un saut brutal du signal. La figure 2.5, simule un biais d’amplitude 5 à l’instant 50 appliqué à un signal bruité (bruit blanc additionnel).c’est le cas pour des capteurs dont un composant élémentaire est défaillant. Ce défaut affecte le système de manière permanente et peut occasionner de graves dégâts.

Figure 2.5 - Biais de capteur. Une dérive se manifeste par une croissance lente et continue du signal, et donc un éloignement de sa valeur nominale. Ces défauts permanents sont plus difficiles à détecter à leur origine du fait de leur faible amplitude et de leur lente évolution. La figure 2.6, montre une dérive capteur affectant le système au temps 50 avec une dérive de 0.01 par unité de temps. Par exemple certains capteurs peuvent présenter une dérive de plus de 10 % après une année d’activité, à cause d’un échauffement intensif ou d’un encrassement.

Figure 2.6 - Dérive capteur. Les valeurs aberrantes sont des défauts dits fugitifs : elles affectent le système de manière instantanée. Leur cause est souvent due à un parasite, par exemple une perturbation électromagnétique .elles se manifestent par un écart important et sporadique par rapport à la valeur nominale du signal. La figure 4 représente un tel défaut au temps 50.

Figure 2.7 - Valeur aberrante.


57

2.8 Les modes de fonctionnement d’un système

Un système possède généralement plusieurs modes de fonctionnement. Ces modes de fonctionnement correspondent au fait que la mission, pour laquelle le système a été conçu, est totalement, partiellement ou pas du tout remplie [Dubu90], • Modes de fonctionnement normaux : la mission est accomplie. Plusieurs modes de fonctionnements nominaux permettent d’obtenir l’adéquation avec l’objectif de la mission. Un mode de fonctionnement peut s’écarter du fonctionnement nominal tout en restant normal. • Modes de fonctionnement anormaux : la mission n’est que partiellement ou pas du tout remplie. Le service n’est pas satisfaisant. Ces modes peuvent correspondre aux :

1. Modes interdits, le système ne doit absolument pas fonctionner dans ces modes pour des raisons de sécurité. 2. Modes défaillants, mauvais fonctionnement du système. 3. Modes dégradés, La mission est partiellement remplie ou elle est remplie avec des performances moindres. 4. Modes critiques, les caractéristiques de fonctionnement sont particulières et généralement non souhaitées.

• Modes de fonctionnements d’exception : ils sont normaux ou anormaux mais aussi peu tolérés ou fréquents d’indisponibilité, le système ne peut accomplir sa mission ou évoluer (mode transitoire de passage d’un mode de fonctionnement à un autre). 2.9 La sûreté de fonctionnement

2.9.1 Introduction

La sûreté de fonctionnement d’un système est la propriété qui permet à ses utilisateurs de placer une confiance justifiée dans le service qu’il leur délivre. Le service délivré par un système est son comportement tel que perçu par son, ou ses utilisateurs ; un utilisateur est un autre système (humain ou physique) qui interagit avec le système considéré [Lapr95].

Selon les applications cibles du système, les différentes facettes de la sûreté de

fonctionnement se voient accorder une importance plus ou moins grande. La sûreté de fonctionnement peut être considérée selon des points de vue différents mais complémentaires. Pour la sûreté de fonctionnement d’un système, Laprie propose trois points de vue présentés dans les sous-sections suivantes : les entraves à la sûreté de fonctionnement, les attributs de la sûreté de fonctionnement et les moyens permettant de l’assurer.

2.9.2 Entraves à la sûreté de fonctionnement Les fautes, les erreurs et les défaillances sont les causes et les conséquences de la non sûreté de fonctionnement [Aviz04].


58

Figure 2.8 – Propagation d’une erreur [Aviz04]

Une défaillance du système survient lorsque le service délivré diffère du service spécifié. Comme la figure 2.8 l’illustre, la défaillance survient parce que le système a un comportement erroné : une erreur est la partie de l’état du système qui est susceptible d’entraîner une défaillance. La cause adjugée ou supposée de l’erreur est une faute. Une erreur est donc la manifestation d’une faute dans le système, et une défaillance est l’effet d’une erreur sur le service. Ceci conduit à la chaîne fondamentale présentée dans la figure 2.9 :

Figure 2.9 – La chaîne fondamentale des entraves [Aviz04] 2.9.3 Attributs de la sûreté de fonctionnement

Les attributs de la sûreté de fonctionnement d’un système mettent plus ou moins l’accent sur les propriétés que doivent vérifier la sûreté de fonctionnement du système. Ces attributs permettent d’évaluer la qualité du service fourni par un système. Les attributs de la sûreté de fonctionnement sont définis par :

• La fiabilité )(tRK , est l’aptitude d’un système à accomplir une fonction requise dans des conditions données et ce pendant un durée donnée. Une mesure de cette fiabilité concerne le temps entre deux défaillances consécutives (MTBF : temps moyen entre deux défiances) (voir figure 2.9). Pour une période de temps de durée t, la MTBF est liée à la fiabilité par une distribution de Poisson qui indique la probabilité de ne pas avoir un échec dans l'intervalle de temps (0 ; t) [Salh01, Lala01, Chia04] :

)exp()( ttR KK λ−= (2.1)

Où : MTTF

K

1=λ est le taux de défaillance du nœud capteur k et t c’est la période de temps.

MTTF (Mean Time To Failure), temps moyen jusqu’à la défaillance, ou temps moyen de bon fonctionnement.


59

Figure 2.10 - Définition du MTBF.

• La disponibilité est l’aptitude d’un système à être en état d’accomplir une mission dans des conditions données, à un instant donné et, en supposant que la fourniture des moyens extérieurs nécessaires soit assurée. Elle caractérise les risques de dysfonctionnement d’un système et sa capacité à y faire face [Carp99]. La disponibilité regroupe les notions de fiabilité et de maintenabilité.

La disponibilité d'un système est donc étroitement liée à la fiabilité, puisqu'elle est définie

comme la probabilité pour laquelle le système fonctionne correctement à un moment donné. Il est lié à la (MTBF: temps moyen entre deux fautes) et à la durée moyenne de réparation (MTTR : durée moyenne de reprise) par la relation suivante [Chia04] :

MTTRMTBF

MTBFitéDisponibil

+= (2.2)

MTBF=MTTF + MTTR

Une disponibilité élevée peut donc être obtenue par un long MTTF ou par une durée moyenne de reprise MTTR courte. Cette situation est illustrée par la figure 2.11.

Figure 2.11 - Relation entre MTTF, MTTR et MTBF.


60

• La maintenabilité est l’aptitude d’un système à être maintenu ou rétabli dans un mode de fonctionnement normal, lui permettant de fournir un service, lorsque la maintenance est effectuée dans des conditions données et avec des moyen prescrits. C’est aussi la probabilité que la maintenance d’une entité E, assurée dans des conditions données avec des moyens et procédures prescrites, s’achève à un instant t2 pour un instant d’occurrence de la défaillance t1.

M(t1,t2) = P[entité défaillante à t1 soit réparée à t2] (2.3) • La crédibilité précise le comportement en cas d’anomalies du système. Elle repose sur la

notion d’intégrité et de sécurité. • L’intégrité représente l’assurance du système à accomplir correctement la mission pour laquelle il a été conçu. Cette assurance implique bien entendu sa capacité à reconnaître le mode de fonctionnement dans lequel se trouve le système (normal ou anormal) et à signaler ce mode de fonctionnement [Carp99]. • La confidentialité : cet attribut évalue la capacité du système à fonctionner en dépit de fautes

intentionnelles et d’intrusions illégales; • La sécurité est l’aptitude du système à éviter de faire apparaître, dans des conditions données,

des événements catastrophiques ou l’assurance du système à résister à des entrées non autorisées ou incorrectes et à pouvoir les signaler.

Remarque :

L’importance des attributs de la sûreté de fonctionnement présentés ci-dessus est principalement liée aux applications et à leurs besoins. Par exemple, pour les applications critiques comme le pilotage de fusées, une grande importance doit être donnée à tous les attributs de la sûreté de fonctionnement. Les applications parallèles à longue durée d’exécution font prévaloir la maintenabilité et la fiabilité.

2.9.4 Moyens d’assurer la sûreté de fonctionnement

Les moyens utilisés pour assurer la sûreté de fonctionnement sont définis par les méthodes et les approches utilisées pour assurer cette propriété [Lapr94]. Les approches les plus connues sont :

- La prévention des fautes qui s’attache aux moyens permettant d’éviter l’occurrence

de fautes dans le système. Ce sont généralement les approches de vérification des modèles conceptuels ;

- L’élimination des fautes qui se focalise sur les techniques permettant de réduire la

présence de fautes ou leurs impacts. Cela est réalisé par des méthodes statiques de preuve de la validité du système (simulation, preuves analytiques, tests, ...) ;


61

- La prévision des fautes qui prédit l’occurrence des fautes (temps, nombre, impact) et leurs conséquences. Ceci est réalisé généralement par des méthodes d’injection de fautes afin de valider le système relativement à ces fautes;

- La tolérance aux fautes qui essaye de fonctionner en dépit des fautes. Le degré de

tolérance aux fautes se mesure par la capacité du système à continuer à délivrer son service en présence de fautes.

Nos contributions seront plus précisément dans les axes prévisions et tolérances aux fautes.

La figure 2.12 résume les notions associées à la sûreté de fonctionnement présentées ci-dessus.

Figure 2.12 – L’arbre de la sûreté de fonctionnement [Lapr94] 2.10 Critères de performance d'un système de diagnostic

Comment s'assurer que le système de diagnostic développé soit le plus performant possible ?. Pour répondre à une telle question, il convient tout d'abord de définir en vertu de quels critères

le système peut être évalué. D'une manière générale, nous pouvons regrouper les différents critères de performance du système de détection de la manière suivante [Ripo99]: La notion de détectabilité est l'aptitude du système de diagnostic à pouvoir déceler la présence d’une défaillance sur le procédé. Elle est fortement liée à la notion d'indicateurs de défauts (résidus) : le générateur de résidu doit, d’une certaine manière, être sensible à la défaillance que l’on souhaite détecter.


62

L’isolabilité est la capacité du système de diagnostic à remonter directement à l’origine du défaut. Une alarme engendre bien souvent de nouvelles alarmes et il devient dès lors difficile de retrouver l’organe défaillant. La propriété d’isolabilité est liée à la structure des résidus et à la procédure de détection elle-même. La sensibilité caractérise l’aptitude du système à détecter des défauts d’une certaine amplitude. Elle dépend non seulement de la structure des résidus mais aussi du rapport de l’amplitude du bruit de mesure avec celle du défaut. La robustesse détermine la capacité du système à détecter des défauts indépendamment des erreurs de modélisation (sensibilité du résidu aux défauts et insensibilité vis-à-vis des perturbations). Généralement, la robustesse est définie par rapport à toutes les entrées inconnues. 2.11 Panorama des méthodes employées en surveillance

Les deux principaux critères de classification des méthodes de surveillance sont le type de connaissance utilisé, et la stratégie de diagnostic. Même si, il faut le souligner, la méthode de diagnostic utilisée dépend fortement du type de modèle, le type de la connaissance a priori sur le système reste le critère principal de classification des méthodes de surveillance.

Les méthodes de surveillance sont basées sur deux approches : les méthodes utilisant des modèles opératoires et celles utilisant des modèles de diagnostic. On les classe souvent en méthodes avec ou sans modèle. Une classification globale est donnée par la figure 2.13 [Buss02, Venk02].

L’approche dite sans modèle signifie ”sans modèle du système à surveiller”. Cette approche utilise bien sûr des modèles, même si ceux-ci reposent sur des descripteurs qui caractérisent le fonctionnement du système observé dans différents modes de fonctionnement (normal, défaut n°1, défaut n°2,...). L’algorithme de surveillance consiste alors à reconnaître en temps réel l’appartenance de ces descripteurs aux formes acquises dans une procédure d’apprentissage [Dubu90], [Pomo92].

L’approche avec modèle, utilise un modèle opératoire. Bien que la connaissance exprimée par

ces modèles puisse se représenter sous des formes très variées, la méthodologie de surveillance est identique, elle utilise l’idée de la redondance qui existe entre la connaissance exprimée par le modèle et celle que portent les données qu’il produit.


63

Figure 2.13 – Classification des méthodes de surveillance 2.12 Notion de redondance

La redondance est une notion essentielle des techniques de diagnostic. Le terme redondance est utilisé pour traduire la possibilité de connaître la valeur d’une variable de différentes manières. Le niveau de redondance s’apparente au nombre de degrés de liberté d’un système (nombre de degrés de liberté = nombre de variables - nombre d’équations (contraintes)). Si le nombre de mesures dépasse le nombre de degrés de liberté, le système devient donc redondant et le nombre (degré) de redondances peut se définir par la différence entre le nombre de mesures et le nombre de degrés de liberté. Deux types de redondance peuvent être distingués : la redondance matérielle et la redondance analytique.

2.12.1 Redondance matérielle

Afin de détecter des pannes à partir des signaux mesurés, il faut un moyen pour distinguer le mode sain et les modes de pannes du système surveillé. La méthode la plus simple consiste à utiliser la redondance physique [Gert91]. Il s’agit de doubler ou tripler des composantes d’un système (voir figure 2.14). Si ces composantes identiques placées dans le même environnement émettent des signaux identiques, on considère que ces composantes sont à l’état sain, et dans le cas contraire on considère qu’une panne c’est produite dans au moins une des composantes.

Figure 2.14 - Redondance physique


64

Cette méthode par redondance physique à l’avantage d’être conceptuellement simple, mais est coûteuse à être mise en oeuvre et conduit à des installations encombrantes.

Un autre inconvénient est que les composantes identiques fabriquées dans la même série

peuvent se dégrader de la même façon et tomber en panne en même temps. Pour pallier à ce dernier inconvénient, on peut utiliser des composantes différentes qui remplissent la même fonction. Par exemple, pour mesurer n variables on utilise m capteurs différents. Représentons par x ∈Rn ces n variables et y ∈Rm les sorties des m capteurs, et supposons que les capteurs sont conçus tels que (on ignore ici les erreurs de mesure).

y = C.x (2.4)

Où C est une matrice m×n de rang colonne plein. Si m > n, i.e. les capteurs sont redondants (mais différents), on peut trouver une matrice V de dimension (m−n)×m et de rang ligne plein qui satisfait V.C = 0. Alors la relation y = C.x implique que, pour tout x ∈Rn, V.y = 0 (2.5)

La violation de cette équation par les mesures y implique la non vérification de l’équation (2.4) et donc l’apparition d’une panne. La relation (2.5) est appelée équation de parité ou encore équation de redondance. Exemple [Ragot98]: Considérons le système de mesure suivant :

)(

202

101

111

201

121

)( kXky ×

= (2.6)

Qui correspond à une configuration simple où on dispose de cinq mesures (couplés) de trois

grandeurs. On pourra aisément constater la redondance inhérente ce système de mesure; celle-ci peut être utilisée pour générer deux équations de redondance liant les composantes yi(k) du vecteur de mesure : 0)()(2)( 431 =−+− kykyky (2.7)

0)()(4)(2 531 =−+− kykyky (2.8)

En l’absence d’erreurs de mesures, les équations (2.7) et (2.8) sont parfaitement vérifiées. Elle ne le sont pas si une ou plusieurs mesures sont entachées d’erreurs.


65

2.12.2 Redondance analytique

La redondance analytique est basée sur l’exploitation des relations analytiques liant différentes grandeurs mesurées d’un système en fonctionnement normal. Ces relations, ne faisant intervenir que des grandeurs mesurées, sont appelées relations de redondance analytique. Celles-ci peuvent être issues de l’expression mathématique de lois physiques ou peuvent être déduites d’une analyse statistique des mesures. Ces relations sont utilisées pour vérifier la cohérence des mesures vis-à-vis du modèle du système en générant des signaux indicateurs de défauts, dont la valeur est révélatrice de la présence de défauts. Sous condition de trouver de telles relations entre les variables mesurées, la redondance analytique permet une exploitation simultanée des informations fournies par les mesures et les modèles disponibles. Cette approche, en contrepartie de calculs supplémentaires, permet, par rapport à la redondance matérielle, de limiter le nombre de capteurs nécessaires à la surveillance. En plus de limiter le nombre de capteurs nécessaires, la redondance analytique permet d’appréhender des défauts affectant aussi bien la chaîne d’instrumentation que le système commandé ou ses organes de commande puisqu’elle intègre bien plus d’informations que la redondance matérielle [Dibo05].

Le diagnostic par redondance analytique suit une démarche qui peut se résumer comme suit : On dispose d’un modèle décrivant le fonctionnement normal du système et on surveille le fonctionnement réel en testant la cohérence entre ce modèle et les observations disponibles. Si celles-ci ne vérifient pas les équations du modèle, on en déduit que le fonctionnement réel n’est pas normal. On produit alors un symptôme (appelé aussi résidu). Cette phase est appelée la phase de génération de symptôme ou phase de détection. Dans une deuxième phase, l’analyse diagnostique se fait alors en comparant le résultat de génération des résidus aux vecteurs binaires des différents défauts dont on possède le modèle de mauvais fonctionnement. L’isolation du défaut sur le système se produit lorsque la signature des symptômes est la même que l’une des signatures de défaut. Cette phase est appelée phase de localisation des défauts.

La figure 2.15, nous donne une présentation du principe général du diagnostic à base de modèles.

Figure 2.15 - Détection à partir d’un modèle parallèle.

Du figure 2.15, la redondance analytique est obtenue par un modèle du procédé qui est alimenté en ligne par les mêmes entrées u(t) que celui-ci. Les résidus r(t) sont calculés par différence entre les mesures y(t) du procédé et les valeurs de référence y*(t) issues du modèle. Les résidus alimentent un module de décision qui a pour but de vérifier si le procédé est dans sa plage de fonctionnement normal et de générer des alarmes si une anomalie est détectée.

Ces dernières années, de nombreuses approches de détection à base de redondance analytique ont été étudiées dans la littérature. Dans la plupart des ces méthodes, nous trouvons deux étapes pour l’obtention du diagnostic : la génération des résidus et leur évaluation. Donc, la génération des résidus est une étape primordiale dans un processus FDI.


66

Les modèles analytiques sont une représentation mathématique de la loi d’évolution des variables physiques du système. Le système est décrit par un ensemble d’équations données par les lois générales. Par exemple,un modèle couramment utilisé est le modèle d’état linéaire dans le domaine temporel dans lequel le vecteur d’état x(t) ,le vecteur d’entrée u(t) et le vecteur de sortie y(t) sont reliés par l’intermédiaire des matrices A,B,C :

)()(

)()()(

tCxty

tButAxtx

=

+=& (2.9)

Les procédés ainsi modélisés ne suivent pas toujours une telle représentation. Les principaux

aspects à prendre en compte afin de minimiser les erreurs de modélisation sont les suivantes :

• Incertitudes sur les paramètres du modèle, • Modifications de structures du système, • Non linéarités, • Perturbations subies par le système, • Bruits affectant les mesures.

2.13 La Tolérance aux Fautes 2.13.1 Définition

La tolérance aux fautes représente la capacité d’un système à remplir sa fonction en dépit des fautes [Aviz04]. D’autres moyens de la sûreté de fonctionnement peuvent être envisagés pour bâtir des systèmes sûrs de fonctionnement (i.e. l’élimination, la prévention ou encore la prévision des fautes). Dans le cadre du travail présenté dans ce manuscrit, nous nous Intéressons exclusivement à la tolérance aux fautes.

Les propriétés d’un système sûr de fonctionnement sont souvent corrélées à son domaine d’application. Ainsi, un réseau de capteurs sans fil est dit sûr de fonctionnement, si et seulement s'il est, d’une part disponible (c'est-à-dire toujours prêt à être utilisé) et, d’autre part, fiable (c'est-à-dire qu'il délivre son service de façon continue sur une période temporelle donnée). D’autres attributs comme la confidentialité ou l’intégrité peuvent être plus appropriés pour qualifier d'autres systèmes sûrs de fonctionnement, comme les applications bancaires ou du domaine de la santé publique. Dans ce mémoire, nous nous focalisons sur les notions de disponibilité et de fiabilité. Lors de l’exploitation d’un réseau de capteurs sans fil, des fautes peuvent être introduites sans être corrigées. Les erreurs correspondantes restent latentes pendant la durée de vie du système jusqu’à ce qu’elles soient activées. L’activation d’une erreur d’un composant d’un réseau de capteurs peut affecter le service qu’il rend, auquel cas le composant est déclaré défaillant. Par ailleurs, la défaillance d’un composant représente une faute auprès des autres composants avec lesquels il interagit. Les défaillances, les erreurs et les fautes représentent les entraves à la tolérance aux fautes [Benn05].


67

2.13.2 Techniques de tolérance aux fautes

La tolérance aux fautes dans les systèmes répartis est toujours réalisée par l’emploi d’un mécanisme de redondance [Aviz06]. Cette dernière peut être physique (duplication de composants), ou bien informationnelle (redondance de données, codes, signatures).

Figure 2.16 – Les techniques de tolérance aux fautes 2.13.3 Travaux existants pour les RCSF

Quelques algorithmes tolérants aux fautes pour le contrôle de topologie d’un réseau de capteurs sans fil, ont été présentés ces dernières années. La plus part de ces algorithmes sont basés sur les graphes de voisinage. Ce sont des constructions issues de la géométrie calculatoire qui permettent de rendre compte de la proximité des sommets dans un espace Rd. Le but de ces travaux est d’assurer une forte connectivité et couverture dans le réseau avec une réduction de la consommation d’énergie. Un résumé sur ces travaux se trouve dans [Thal05, Gwen04, Ning04, Ning05, JieW06]. En ce qui suit, nous passons en revue quelques travaux existants sur le contrôle de topologie dans les réseaux de capteurs sans fil :

- (M. Penrose 1999 et Bettstetter 2002), étudiés la k-connectivité dans les graphes aléatoires. Le résultat principal de leurs travaux est qu'un graphe géométrique aléatoire est k nœuds connectés avec une probabilité élevée s'il existe un arc entre les noeuds quand ils sont à la plupart à une distance r. La valeur de r doit être choisie de sorte que le graphe ait un degré minimum égale à k. Ils ont donnés une limite inférieure et supérieure sur la valeur minimum de r et ont analysés la probabilité pour que le graphe soit à k nœuds connectés.

- (Li et al., 2003), apportent une extension aux travaux de M. Penrose, en ajoutant un seuil

minimum et maximum à la valeur de r, pour que le graphe aura une probabilité élevée de k-connectivité.

- (Meguerdichian et al., 2001), ont proposés un algorithme polynomial optimal pour

résoudre la meilleure couverture. Cet algorithme est basé sur une combinaison des techniques de la géométrie combinatoire et de la théorie des graphes.

- (L. Li, J. Y. Halpern, V. Bahl, Y. M.Wang, et R.Wattenhofer., 2001) , proposent le protocole

CBTC ( Cone Based Topology Control ). Dans cette technique un ensemble de nœuds { }kwww ,...,, 21 voisins d’un nœud v, sont sélectionnés pour satisfaire la condition suivante : Si le disque de transmission de centre v est divisé en k connes par les lignes vwi ( ki ≤≤1 ) et l’angle du conne maximal n’est pas supérieur àα . Il est prouvé que,

Tolérance aux fautes

Redondance

Physique Informationnelle


68

quand 6/5πα ≤ , CBTC préserve la connectivité du réseau et quand 3/2πα ≤ ; le sous graphe symétrique correspondant (c’est le sous graphe après élimination de touts les arcs unidirectionnel) est connecté.

- (Bahramgiri et al., 2002), proposent une extension à l’algorithme CBTC, introduit par Li

et les autres, pour construire une topologie tolérante aux fautes. Ils ont prouvés qu’il suffit d’un angle de k3/2π , dans un réseau homogène pour préserver la k- connectivité (voir figure 2.17).

Figure 2.17 – protocole de contrôle de topologie CBTC.

- (Ning Li et al., 2003) ainsi que (Hajiaghayi et autres, 2003), présentent des algorithmes d'approximation pour trouver des sous graphes k-connectés. Le but est de trouver de manière centralisée un arbre recouvrant d’énergie minimale (MST ou Minimum-power Spanning Tree) à partir du graphe du réseau de capteurs sans fil. La construction de cet arbre MST (voir figure 2.18) est possible dans le cas où on peut déterminer la distance entre les noeuds. Avec cette information, le poids des arcs est calculé avec un modèle énergétique. L’algorithme est simple : tant que tous les noeuds ne sont pas joints, choisir l’arc le moins coûteux non encore sélectionné et l’ajouter dans l’arbre MST. De plus, pour éviter de choisir deux noeuds faisant partie du même composant connexe, l’algorithme intègre un mécanisme de coloriage des noeuds. Ce protocole possède plusieurs propriétés intéressantes. D’une part, il est connu que le graphe MST(G) = (V;Emst) est symétrique (non-dirigé), ce qui permet de ne pas avoir de liens unidirectionels. D’autre part, chaque noeud de V peut-être la racine d’un arbre recouvrant en utilisant MST(G), donc n’importe quel nœud peut être source de la diffusion. Finalement, il est connu que MST(G) est fortement connexe si le graphe G est fortement connexe. Une fois l’arbre construit, il suffit d’ajuster la portée de chaque noeud pour que chacun couvre uniquement ses voisins dans l’arbre. Pour cela, les auteurs proposent une fonction d’assignement des portées de chaque noeud à partir de MST.

Figure. 2.18 – Exemple de graphe avec l’algorithme MST


69

- (C.C. Yao, 1982 puis X.Y. Li et al., 2003), proposent une solution basé sur les graphes

de Yao. Ce qui préserve également la k-connectivité dans les réseaux homogènes. L'inconvénient principal de cette solution est qu'elle exige un réseau homogène et emploie beaucoup de liens additionnels inutiles pour réaliser la k-connectivité. Construire un Graphe de Yao [Gwen04] nécessite de découper l’espace autour de chaque noeud en k secteurs d’angle k/2π . Dans ce graphe, chaque noeud est connecté avec son plus proche voisin dans chaque secteur (voir figure 2.19).

Figure 2.19 – Graphe de Yao.

- Dans (Basu et al., 2004), les auteurs proposent des algorithmes simples de contrôle de mouvement d’un sous ensemble (nœuds capteurs) mobiles pour maintenir une "bi-connectivité" dans le réseau. Ainsi le partitionnement du réseau peut être évité en cas d’échec d’un nœud critique. L’objectif de l’optimisation étant de minimiser les distances parcourues par les nœuds mobiles. Pour une topologie réseau à deux dimensions, des heuristiques ont été proposées pour garantir la bi-connectivité de la topologie. Cette étude se focalise sur des aspects de graphes afin de remédier au problème de partitionnement plus qu’à des aspects de performances réseau.

- Dans (Wang et al., 2004), des approches distribuées de déploiement de capteurs ont été

proposées. Elles sont basées sur les diagrammes de Voronoi, et permettent de déplacer itérativement les capteurs d’une zone dense vers une zone moins dense afin d’assurer une meilleure couverture de l’environnement étudié.

- (Ning Li et Jennifer C. Hou, 2004-2005), présentent l’algorithme FLSS (Fault tolerant

Local Spanning Subgraph) de contrôle de topologie pour un réseau hétérogène. Ils ont développé leur algorithme pour un contrôle de la k-connectivité au lieu de la connectivité en utilisant des techniques de propagation des flux.


70

2.14 Mécanismes de survie classiques dans les réseaux

Deux façons opposées mais complémentaires d’aborder une panne coexistent dans les réseaux: la restauration et la protection. Chacune peut être utilisée pour rétablir le trafic en cas de panne 2.14.1 Restauration

La restauration consiste à rerouter dynamiquement des connexions lorsqu’une panne survient sur le réseau. On doit alors calculer, au moment de la panne, un nouveau routage à partir des ressources disponibles. Dans la suite de ce mémoire nous ne traitons pas le problème de la restauration, mais celui de la protection comme moyen pour assurer la tolérance aux fautes. 2.14.2 Protection

Le principe de la protection est de prévoir à l’avance tous les cas de pannes pouvant survenir sur le réseau afin de mettre en place des solutions de secours assurant la continuité du trafic. Il s’agit par exemple de proposer des chemins de protection sur lesquelles pourra être acheminée une requête lorsque son chemin principal, celui sur lequel elle est routée par défaut quand il fonctionne, est affecté par une panne. 2.15 Le cahier des charges de la surveillance

L’élément principal du cahier des charges est la définition du sous-ensemble (sous système) des composants du système que l’on souhaite surveiller pour des raisons de sécurité, de qualité de production de maintenance, etc... [Bela04]. On associe à chaque composant à surveiller, la relation du système qui matérialise son mode de comportement normal. Ainsi le cahier des charges de surveillance doit permettre de définir le sous-ensemble de relations du système FS �⊂ F [Carp96]. Il doit définir le sous-ensemble de variables ou grandeurs physiques devant impérativement être connues et stipuler le sous-ensemble des inconnues qui ne sont pas mesurables physiquement. Il doit aussi préciser les composants et les défaillances associées qui doivent y être détectées et/ou localisées. Il peut aussi contenir les performances attendues en terme de détection, de prédiction des pannes et de configuration du système.

Pour cela, on peut déterminer trois indices permettant de caractériser ces performances

[Carp99]: • La probabilité de fausse alarme (détection d’une anomalie en fonctionnement normal). • La probabilité de non détection (défaillance non détectée). • Le délai de détection.

Enfin, il est possible de définir dans le cahier des charges de surveillance la capacité de localisation qui indique la possibilité de déterminer l’origine de la défaillance, c’est-à-dire d’identifier la cause de la panne parmi les causes prises en compte par le système de surveillance. Dans le cas idéal, il serait souhaitable de pouvoir localiser toutes les causes de défaillance.


71

Dans le cadre de notre travail, les points essentiels que nous mentionnons dans le cahier des charges sont sous formes de besoins et de mécanismes pour une surveillance continue du réseau de capteurs sans fil, on vise essentiellement à répondre aux besoins suivants : 1. Garantir une connectivité permanente dans le réseau : Dans le contexte tolérance aux

fautes, on propose un algorithme de prédiction de partitionnement du réseau, comme outil tolérant aux fautes. Il vise à maximiser la durée de vie du réseau en terme de connectivité.

2. Garantir une couverture complète et continue des cibles à surveiller par le réseau :

Dans ce cadre, on propose deux algorithmes, le premier nous aides à savoir l’état de couverture des différentes cibles. Le deuxième, assure une couverture minimale dans le réseau ce qui permet d’économiser la consommation de l’énergie (les nœuds capteurs qui n’appartiennent pas à la couverture minimale seront mis en mode veille).

3. Garantir une économie de l’énergie pendant l’exploitation du réseau : L’utilisation

d’une interface radio engendre un coût énorme pour la consommation énergétique dans un réseau de capteur sans fil, chaque entité du réseau consomme de l’énergie, surtout l’émission et la réception des communications. Fenney propose plusieurs analyses [Feen01, LFee01] montrant le surcoût énergétique des interfaces radios et des principaux algorithmes de routage. De même, Chen et al. [Chen03] démontrent l’accroissement important de l’énergie requise en fonction de la puissance et de la taille du message. De nombreux travaux s’intéressent à la réduction de la consommation. Une des idées qu’on va essayer de développer est d’offrir une politique d’alternance des communications entre les noeuds. En basculant les nœuds capteurs entre les modes : active, écoute et veille. Cela permet d’économiser et équilibré la consommation de l’énergie entre les nœuds capteurs, ce qui maximise la durée de vie du réseau.


72

2.16 Conclusion

Dans ce chapitre, nous avons présenté les concepts de base de la surveillance et la notion de sûreté de fonctionnement d’un système informatique. Nous avons vu que la tolérance aux fautes n’est qu’un moyen pour assurer la sûreté de fonctionnement d’un système et qu’on utilise toujours la redondance pour l’obtenir. De plus, la tolérance aux fautes est un sujet de recherche important pour les systèmes répartis tel que les RCSF. Ces systèmes disposent de deux propriétés importantes : la sûreté (un mauvais comportement n’apparaît jamais) et la vivacité ( un bon comportement apparaît ultimement).

Nous avons vu aussi que la surveillance peut être implémentée selon deux approches. Les méthodes sans modèles sont simples à mettre en oeuvre et ne nécessitent pas une connaissance complète du système. Cependant, elles sont gourmandes en ressources informatiques. Les méthodes à base de modèles requièrent une connaissance parfaite du fonctionnement du système mais offrent l’avantage de se prêter à une modélisation rigoureuse.

L’objectif de ce chapitre a été de présenter les différents travaux dans le domaine de la

surveillance des systèmes, et de justifier le contexte dans lequel nous nous sommes placés afin d’élaborer notre système de supervision, dédié aux réseaux de capteurs sans fil. Notre travail va se focaliser plus précisément sur le 2ème axe du processus de la surveillance (la partie tolérance aux fautes et plus précisément la prédiction des pannes).

Enfin on a clôturé ce chapitre par un cahier des charges, qui indique l’ensemble des besoins et

une brève description des solutions proposées pour la surveillance d’un réseau de capteurs sans fil.


73

2.17 Bibliographie [Adro00] Adrot O., « Diagnostic à base de modèles incertains utilisant l'analyse par intervalles

L’approche bornante ». Doctorat de l'Institut National Polytechnique de Lorraine, France, Décembre 2000.

[Aviz04] Algidras Avizienis, Jean-Claude Laprie, Brian Randell et Carl Landwehr, « Basic

Concepts and Taxonomy of Dependable and Scure Computing», IEEE Transactions on Dependable and secire computing, 1 (1), pp.11-33, Janvier-Mars 2004.

[Aviz06] A. Avizienis. Fault-tolerant systems. IEEE Trans. Computers, 25(12) : 1976. [Bela04] Belaguid Mustapha, «Optimisation des algorithmes de génération des RRAs en analyse

structurelle pour la surveillance. », Thèse de magister, Université d’Oran Es-Senia, Octobre 2004.

[Benn05] Mohamed Taha Bennani, « Tolérance aux Fautes dans les Systèmes Répartis à base

d'Intergiciels Réflexifs Standards », Institut national des sciences appliquées de Toulouse, Thèse de doctorat, 20 juin 2005.

[Buss02] Frédéric Busson, Les bond graphs multienergies pour la modélisation et la surveillance

en génie des procédés, thèse de doctorat, Université des Sciences et Technologies de Lille, décembre 2002.

[Carp96] T. Carpentier et R. Litwak. Une approche structurelle pour le positionnement de

capteurs en vue de la surveillance. AGI’96, Forum des doctorants, Automatique, Génie informatique et Image, pages 103—107, Juin 1996.

[Carp99] T. Carpentier. Placement de Capteurs Pour la Surveillance Des Processus

Complexes. PhD thesis, L’Université des Sciences et Technologies de LILLE, 1999. [Chen03] Y. Chen, E.G. Sirer, and S.B. Wicker. On selection of optimal transmission power

for ad hoc networks. In Proc. 36th Hawaii International Conference on System Sciences (HICSS’2003), Hawaii, January 2003.

[Chia04] Man Wah Chiang. , Zeljko Zilic. , Katarzyna Radecka. and Jean-Samuel

Chenard1. , «Architectures of Increased Availability Wireless Sensor Network Nodes», McGill University, USA, 2004.

[Dibo05] Moustapha ALHAJ DIBO, « Validation de données et diagnostic des systèmes

incertains a l'aide de l'analyse par intervalle. », Thèse de doctorat, Ecole doctorale IAEM Lorraine, 18 juillet 2005.

[Dubu90] B. Dubuisson. Diagnostic et Reconnaissance Des Formes. Hermes edition, 1990. [Feen01] L.M. Feeney. An energy-consumption model for performance analysis of routing

protocols for mobile ad hoc networks. ACM J. of Mobile Networks and Applications, 3(6) :239–249, 2001.


74

[Gert91] J. Gertler. Analytical redundancy methods in fault detection and isolation. In IFAC Symposium on Fault Detection Supervision and Safety for Technical Process, pages 9–22, Baden Baden, Germany, 1991.

[Gwen04] Gwendal Simon, « Conception et réalisation d’un système pour environnement virtuel

massivement partagé.», Thèse de doctorat, Université de Rennes 1, 10 décembre 2004. [JieW06] Jie Wu, Fei Dai, “Mobility-Sensitive Topology Control in Mobile Ad Hoc Networks, ”,

IEEE Transactions on parallel and distributed systems, Vol. 17, NO. 6, June 2006. [Lala01] P. Lala, Self-Checking and Fault Tolerant Digital Design, Morgan Kaufmann, 2001. [Lapr95] J.-C. Laprie, J. Arlat, J.-P. Blanquart, A. Costes, Y. Crouzet, Y. Deswarte, J.-C. Fabre,

H. Guillermain, M. Kaâniche, K. Kanoun, C. Mazet, D. Powell, C. Rabéjac et P. Thévenod, Guide de la sûreté de fonctionnement, 369p., 1995.

[Lapr94] J-C. Laprie. ARAGO 15, « Concepts de base de la tolérance aux fautes.», MASSON,

Paris, 1994. [LFee01] L.M. Feeney and M. Nilson. Investigating the energy consumption of a wireless

network Interface in an ad hoc networking environment. In Proc. IEEE INFOCOM 2001, pages 1548–1557, Anchorage AK, April 2001.

[Miln87] Milne R., «Strategies for diagnosis. », IEEE Transactions on Systems, Man and

Cybernetics, Vol. 17, No 3, p 333-339, 1987. [Mran04] Rim MRANI ALAOUI, « Conception d’un module de diagnostic a base des suites

de bandes temporelles en vue de la supervision des procèdes énergétique. Application en ligne à un générateur de vapeur. », Thèse de doctorat, Université des Sciences et Technologies de Lille, 9 novembre 2004

. [Ning04] Ning Li and Jennifer C. Hou, “FLSS: A Fault-Tolerant Topology Control Algorithm

for Wireless Networks“,Department of Computer Science University of Illinois at Urbana-Champaign Urbana, 2004.

[Ning05] Ning Li and Jennifer C. Hou, “Localized topology control algorithms for heterogeneous wireless networks,” IEEE/ACM Trans. Netw., vol. 13, no. 6, 2005.

[Patt97] R. J. Patton. Fault-tolerant control: The 1997 situation. Safeprocess, 1997. [Penc02] Yannick PENCOL., «Diagnostic décentralisé de systèmes à événements discrets :

application aux réseaux de télécommunications», Thèse de doctorat, Université de RENNES 1, 28 juin 2002.

[Pomo92] D. Pomorski. Apprentissage Automatique Symbolique et Numérique. Construction et

Évalution D’un Ensemble de Règles À Partir Des Données. PhD thesis, Université des Sciences et Technologies de Lille, Paris, 1992.

[


75

Ragot98] D. MAQUIN et J. RAGOT. Diagnostic de fonctionnement des systèmes a partir de modeles, 1998.

[Rago04] J. Ragot, D. Maquin et M. Alhaj Dibo. Détection de défauts de capteurs : une

approche aveugle. In 3ème Colloque Interdisciplinaire en Instrumentation, C2I 2004, pages 101–108, Cachan, France, 2004.

[Ripo99] Patrick RIPOLL, Conception d’un système de diagnostic flou applique au moteur

automobile, thèse de doctorat, 13 décembre 1999. [Salh01] Ayad Salhieh. Jennifer Weinmann. Manish Kochhal. Loren Schwiebert. , «Power

Efficient Topologies for Wireless Sensor Networks», Wayne State University, Dept. of Electrical and Computer Engineering, Detroit, MI 48202.

[Thal05] Bernhard Thallner, «Topology Control for Fault-Tolerant Communication in

Wireless Ad Hoc Networks», Institut f¨ur Technische Informatik , Universität Wien, im März 2005.

[Toua05] Samir TOUAF, «Diagnostic logiques des systèmes complexes dynamiques dans un

contexte multi- agent » , Doctorat de l’université Joseph Fourier - Grenoble 1, France, 2005.

[Venk02] Venkat Venkatasubramanian , Raghunathan Rengaswamy , Kewen Yin Surya N.

Kavuri, «A review of process fault detection and diagnosis Part I: Quantitative model-based methods», School of Chemical Engineering, Purdue University, West Lafayette, USA, 2002.

[Vill88] A. Villemeur., « Sûreté de Fonctionnement Des Systèmes Industriels. Fiabilité

– Facteurs Humains – Informatisation. » , Eyrolles edition, 1988.


76

Chapitre 3 Modélisation des RCSF 3.1 Introduction

Avant d’aborder nos propositions en terme de modèles tolérants aux fautes pour un réseau de capteurs sans fil, on a jugé nécessaire de rappeler brièvement quelques notions fondamentales qui reviendront constamment au long de ce chapitre. En premier lieu, il convient de préciser quelques propriétés sur la théorie des graphes nécessaire pour la représentation des RCSF.

3.2 Modélisation par les graphes

Dans la majorité des cas d'étude , un réseau de capteurs sans fil peut être modélisé comme un graphe unitaire G =(V,E ) avec V l'ensemble des noeuds du graphe (à chaque nœud capteur du réseau correspond un noeud dans le graphe) et E l'ensemble des arcs donnant les possibilités de communication directes entre les noeuds (nous considérons dans ce document que la communication est symétrique, c'est à dire que si une noeud peut en entendre un autre, il peut également se faire entendre par lui. Le graphe correspondant est alors non orienté). Si on pose d(u,v) comme étant la distance physique séparant les noeuds u et v, et R le rayon de communication des noeuds, l'ensemble E se définit par : [Cart03] E=(u,v)∈V2d(u,v)≤R (3.1) d : distance euclidienne

d = )y - (y ) x- (x 221

221 + (3.2)

On pose n=|V| : nombre de nœuds dans le réseau

Pour la couverture, on note par r, le rayon de couverture (ou de capture), tel que : R ≥ 2r. La figure 3.1 présente les deux rayons (connectivité et couverture).

Chapitre 3 - Modélisation des RCSF

77

Figure. 3.1 - Connectivité et couverture dans un réseau de capteurs sans fil

La figure 3.2, présente des exemples de graphes Disk Unitaire (GDU), où le degré de connectivité est très élevé, ce qui rend difficile l’étude des ces types de graphes [Wang04].

Figure 3.2. Exemples de Graphe Disk Unitaire [Wang04]

À partir de cette modélisation de base, nous pouvons fournir différentes définitions qui vont nous servir par la suite. Définition 3.1 : Soit u un noeud. On appelle voisinage de u l'ensemble N(u) contenant les noeuds que u peut joindre directement. La relation binaire représentant le lien de communication est supposée symétrique, i.e. u’∈ N(u) ⇔ u∈ N(u’) (i.e. tous les noeuds du réseau ont la même portée de communication) [Haus05].


78

Définition 3.2 : Soient v et w deux noeuds du réseau. Une route p entre v et w est une suite de noeuds o1,o2, . . . ,on telle que o1 = v, on = w et quelque soit i entier, 1≤ i < n, oi+1 ∈ N(oi). On

note P~

l'ensemble des noeuds appartenant au chemin, soit { }Un

i ioP1

~=

= . On note |p| le nombre

de sauts de p, (|p| = n − 1). L'ensemble des routes reliant v à w est notée P(v,w) [Haus05].

Il est évident que toutes les routes disponibles ne sont pas forcément intéressantes pour la communication. Par exemple, les routes très longues, les routes où il y a des nœuds capteurs avec énergie faible ou les routes contenant des boucles ne sont pas intéressantes. Les routes optimales en nombre de sauts et consommation d’énergie optimale sont quant à elles peu nombreuses et sensibles aux changements de topologie [TohK97]. Nous définissons donc ici les types de routes potentiellement intéressantes. Définition 3.3 : Soient v et w deux noeuds du réseau et p = o1,o2, . . . ,on ∈ P(v,w) une route entre v et w [Haus05]. 1. p est appelée route optimale si et seulement si ∀ p’ ∈ P(v,w) |p’|≥ |p|. Si p est optimale, |p| est appelée distance entre v et w et est notée d(v,w). 2. p est dite sans boucle si et seulement si pour tout couple i,j d'entiers, 1≤ i,j ≤ n, oi = oj ⇒ i = j. 3. p est dite k-sous-optimale ( k ≥ 1), si et seulement si p est sans boucle et |p| < d(v,w) + k. On note SOPk(v,w) l'ensemble des routes k sous-optimales entre v et w. Le degré moyen d’un réseau est la moyenne du nombre de voisins de chaque nœud [CarJ03] :

n

iN

G Vi

∑∈=

)()deg( (3.3)

3.3 Réduction du degré d'un graphe

Pour de nombreuses applications, et en particulier celles que nous présentons, il est intéressant de proposer des algorithmes permettant de diminuer le degré moyen d'un graphe. Le degré moyen d'un graphe est le nombre moyen d'arêtes pour chaque noeud. On peut citer, par exemple, les arbres de recouvrement minimaux (Minimum Spanning Tree), les graphes de Gabriel, le graphe des voisins MPR , ou les ensembles dominants, les graphes RNG (Relative Neighborhood Graph) [Tous80]. Dans la suite de ce chapitre nous allons analyser les différents algorithmes possibles pour construire un graphe de connectivité réduit et planaire. Nous passerons en revue quelques unes de ces structures, on distingues deux types : les structures géométrique plate et les structures hiérarchiques. La figure 3.3 résume ces deux structures [Wang04].


79

Structures pour la topologie de réseau Structures plates Structures Hiérarchiques MST RNG GG Yao Del CDS Figure 3.3. - Structures utilisées dans les réseaux sans fil. 3.3.1 Graphe de Gabriel (GG)

Le graphe de Gabriel (GG ou Gabriel Graph) est un graphe planaire qui peut être définie par l’équation suivante : Un lien (u,v) existe entre deux sommets u,v ∈ G, si il n'y a aucun autre

sommet w ∈ G dans un cercle de diamètre uv [Kuli05] ( voir figure 3.4) . :

∀ w∈ G, w ≠u, w ≠v : d2 (u,v) < [ d2 (u,w)+d2(v,w) ] (3.4)

Figure 3.4. - le graphe de Gabriel

Un nœud peut enlever les liens non GG. L’algorithme est le suivant :

m= médiatrice entre le noeuds u et v

Pour tout v ∈ N faire

Pour tout w ∈ N faire

Si w = = v alors

Continuer

Sinon

Si dist (m, w) < dist (u, m) alors

Eliminer l’arc (u, v)

Sortir

Fin si

Fin Pour

Fin Pour


80

3.3.2 Graphe du voisin relatif (RNG)

Le RNG (Relative Neighborhood Graph ou Graphe du Voisin Relatif) [CarJ03, Tous80,

Kuli05] est un fondement de la géométrie informatique, avec des applications dans la géographie, cartographie, reconnaissances de séquences, etc.

Le RNG contient le sous ensemble RNG(G) = (V, ERNG) avec V : l’ensemble des nœuds qui

répond à la propriété suivante :

ERNG(G)= {(u, v) ∈ E | ∌ w ∈ V, d(u,w)< d(u,v) Λ d(v,w) < d(u,v).} (3.5)

Une autre écriture de la propriété :

ERNG(G)= {(u, v) ∈ E | ∌ w ∈ N(u) ∩ N(u) d(u,w)< d(u,v) Λ d(v,w) < d(u,v).} (3.6)

Avec N (u) : l’ensemble de nœuds voisins de u.

La figure 3.5 montre mieux cette propriété car le nœud w étant présent alors le lien (u,v) n’est pas dans le RNG, les deux liens valides dans le RNG sont alors (u,w) et (v,w) .

Figure 3.5 - configuration simple de RNG

Les figures 3.6 et 3.7 [Cart03, CarJ03], représentent respectivement le graphe qui représente le réseau sans fil et la deuxième représente le graphe RNG associé.

Figure 3.6 - Graphe disque unitaire Figure 3.7 - Graphe RNG associé au de densité 8. graphe disque unitaire.


81

Dans ce type de graphe tous les noeuds connaissent leurs voisins immédiatement, de sorte que

les nœuds forment la liste des voisins RNG et enlèvent les voisins non-RNG on peut mieux voir cela avec cette algorithme : (N l’ensemble des nœuds).

• Algorithme de la découverte des voisins RNG pour un nœud capteur (c)

RNG est déjà appliqué dans les réseaux sans fil , le nombre de voisin RNG est autour de 2 à 6 et cela a été démontré dans des études précédentes [CarJ03].

RNG peut être déduit localement par chaque nœud en employant seulement la distance avec

ses voisins distants. En posant comme principe l’utilisation de quelques nœuds équipés du système GPS ou d’autres techniques pour connaître la position des nœuds pour mesurer la distance.

Les nœuds doivent envoyer périodiquement les messages HELLO avec leurs coordonnées de

façon que les nœuds déduisent leurs voisins RNG.

M : liste des voisins de c

Début

Pour chaque voisin a ∈ M

Drapeau= vrai

Pour (b ∈ M & b ≠ a)

Faire

Si distance (a, b) <distance (c, a)

Alors

Si distance (c, b) < distance (c, a)

Alors

Drapeau = faux ;

Fin si

Fin si

Fin pour

Si Drapeau

Alors

Ajouter le noeud a comme voisin RNG du noeud c

Fin si


82

• Quelques propriétés du graphe RNG

Les graphes RNG possèdent quelques propriétés très intéressantes :

- Un graphe RNG est un graphe planaire. L’utilisation des graphes RNG a déjà fait l’objet de quelques travaux dans le cas des réseaux sans fil.

- Toussaint dans [Tous80] a montré que si le graphe G est connecté alors RNG (G) est lui aussi connecté.

- Une autre propriété intéressante est la taille du graphe RNG obtenu, en terme de nombre de liens. Il a été démontré que la taille minimale et maximale du graphe RNG sont bornées en deux dimensions. La démonstration est relativement triviale et s’appuie sur le fait que MST (arbres recouvrants minimaux ou Minimum Spanning Tree) est le sous-graphe de RNG et que RNG est le sous-graphe de DT (le procédé de triangulation de Delaunay ou Delaunay Triangulations). On peut en déduire que

)()()( GDTGRNGGMST ≤≤ . Soit Vn = le nombre de noeuds dans le graphe, on peut

écrire n-1≤|RNG (G) |≤3n-6. Une meilleure estimation de la borne supérieure de 3n-10 est proposée dans le cas où n ≥8. Cette valeur est importante, car elle permet de donner une estimation du nombre moyen de voisins RNG d’un noeud. Si l’on prend la borne

supérieure 3n-6, chaque voisin a en moyenne )6(3)6()(3nnn

n −=− . Lorsque ∞→n

alors le nombre moyen de voisins tend vers 3. Cette propriété indique que si la densité augmente, alors le nombre moyen maximal de voisins est stable. Ce résultat est une borne supérieure théorique. De manière empirique, le nombre moyen de voisins a été évalué à 2,6 nœuds [CarJ03].

- Quel que soit la fonction de distance utilisé le graphe reste connexe si cette fonction est monotone.

L’avantage avec les graphes GG et RNG, c’est qu’en réduisant le nombre de lien cela

contribue à plus d’efficacité dans les réseaux sans fil et cela a été démontrer avec l’expérience. RNG et GG sont tous les deux utilisés dans les réseaux ah doc, distribués chaque nœud peut

déduire le graphe. La figure 3.8 [Burk04], nous donne une comparaison entre les différents algorithmes de

réduction des liens de communication.

Figure 3.8 - Comparaison entre les techniques de réduction de la complexité d’un GDU.

Inte

rfér

ence

Densité du réseau (nœuds par unité de disk).


83

3.4 Conclusion

Dans ce chapitre, nous avons montré que les RCSF peuvent être modélisés par un graphe, qui représente les relations entre les différents nœuds capteurs. Ce graphe qui reflète la topologie du réseau, est connu sous le nom de graphe disque unitaire. Durant notre étude théorique de la modélisation des RCSF en graphe, on a constaté que le graphe généré est trop dense en nombre de liens de communication et donc son exploitation n’est pas chose facile. A cette fin on a proposé de réduire sa complexité à l’aide de la technique RNG, pour enfin aboutir à un graphe planaire de connectivité réduite.


84

3.5 Bibliographie [Burk04] Martin Burkhart . Pascal von Rickenbach. Roger Wattenhofer. Aaron Zollinger,

«Does Topology Control Reduce Interference? », Swiss Federal Institute of Technology Zurich, 2004.

[CarJ03] Julien CARTIGNY , « Contributions à la diffusion dans les réseaux ad hoc », Thèse

de doctorat, Université des Sciences et Technologies de Lille, 19 décembre 2003. [Cart03] Julien Cartigny and David Simplot, Ivan Stojmenovié, «Localized minimum-energy

broadcasting in ad-hoc networks», Université de Lille 1, IEEE INFOCOM 2003. [Haus05] Michaël Hauspie, «Contributions à l'étude des gestionnaires de services distribués dans

les réseaux ad hoc», Thèse de doctorat, Université des Sciences et Technologies de Lille, Janvier 2005.

[Kuli05] Lars Kulik , « Data Dissemination in Wireless Sensor Networks », University of

Melbourne, 2005. [TohK97] C.-K. Toh. Associativity based routing for ad hoc mobile networks. Wireless Personal

Communications Journal, Special Issue on Mobile Networking and Computing Systems, 4(2):103_139, March 1997.

[Tous80] G. Toussaint. The relative neighborhood graph of Finite planar set. Pattern Recognition,

12(4):261_268, 1980. [Wang04] Yu Wang, «Efficient localized topology control for wireless ad hoc networks»,

Graduate College of the Illinois Institute of Technology, Chicago, Illinois, May 2004.


85

Chapitre 4 Proposition de solutions pour la surveillance d’un RCSF 4.1 Introduction

Dans ce chapitre, nous abordons la problématique de la surveillance dans les réseaux de capteurs sans fil. Nous établissons des solutions tolérantes aux fautes basées sur quelques propriétés de la théorie des graphes et la redondance matérielle pour la supervision d’un RCSF. Dans ce contexte, nous proposons des stratégies pour prédire la robustesse des liens de connectivité et de la couverture du réseau, tout en minimisant la consommation de l’énergie. 4.2 Test et surveillance des RCSF

Dans un réseau de capteurs les fautes sont induites par des défauts physiques ou défauts logiques qui affectent la conception, la fabrication ou le fonctionnement des composants d’un réseau de capteurs sans fil. Les défauts de conception sont commis soit par les humains soit par les logiciels au cours du processus de conception. Les défauts de fabrications résultent des imperfections dans le procédé de fabrication. Les défauts en opération sont généralement dus à la fatigue ou aux contraintes environnementales au cours des sollicitations du système. Les interférences électroniques, ainsi que les vibrations et les températures extrêmes sont des sources potentielles de ce type de défaut. Certains défauts de conception et de fabrication peuvent échapper à la détection lors de test appropriés ces défauts s’associent à la fatigue et aux perturbations environnementales pour créer des fautes dans un RCSF en exploitation. Sous certaines conditions de fonctionnement, les fautes engendrent des erreurs de sortie dans un nœud capteur, qui se caractérisent par des états incorrects.

Les erreurs entraînent des défaillances qui se caractérisent par une déviation plus ou moins

importante du comportement du RCSF par rapport au comportement normal attendu. La défaillance devient un risque de danger si elle est susceptible d’entraîner des déconnexions de certaines zones du réseau, mauvaise couverture des événements, mauvaise agrégation des données collectées, etc.

Chapitre 4 - Proposition de solutions pour la surveillance d’un RCSF

86

4.2.1 Test en ligne

Le diagnostic ou test est un maillon de tout système ; il permet de mesurer la qualité et la fiabilité des composants d’un système. L’intérêt du test est multiple, il permet d’une part de fournir des systèmes opérationnels et d’autre part, grâce au diagnostic, de remettre en cause les procédures de fabrication ou de conception et donc d’augmenter le rendement et la durée de vie d’un réseau de capteurs par exemple. Le test s’insère donc naturellement dans le processus de synthèse et de réalisation de tout système, et plus particulièrement dans la gestion d’un réseau de capteurs sans fil [Sime05].

Les techniques de test se classifient en deux catégories suivant qu’elles sont applicables au

système en exploitation ou hors exploitation. On distingue ainsi le test en ligne et le test hors ligne. Dans notre cas pour la surveillance d’un réseau de capteurs sans fil on se base sur un test en ligne. L’objectif visé est de s’affranchir de l’influence des fautes pour ainsi contribuer à l’amélioration de la sécurité et la sûreté de fonctionnement d’un réseau de capteurs sans fil.

Différents méthodes peuvent être conjointement utilisées pour atteindre cet objectif. Parmi les moyens les plus couramment mis en œuvre, on distingue :

- La prévention des défaillances qui vise la réduction de la probabilité d’occurrence de fautes.

- La tolérance aux fautes qui concerne la réduction de la sensibilité de la fonction implémentée aux fautes.

- La prévision qui implique la surveillance du système. Elle regroupe les opérations de détection et localisation de fautes afin de décider d’une action compensatrice de sorte que le processus puisse continuer à remplir la mission qui lui a été confiée, malgré la présence des défauts mis en évidence. La décision d’intervention ou de reconfiguration est prise lorsqu’il y a évidence expérimentale d’un défaut imminent.

La complexité des systèmes actuels tels un RCSF et la nécessité d’accomplir ces tâches dans

un temps restreint limitent fortement le rôle des opérateurs humains. Il est donc nécessaire de confier la tâche de surveillance à un module automatique de diagnostic. A l’occurrence d’une défaillance, la réaction du module de surveillance commence par la détection du défaut, passe par la localisation du composant défectueux (le nœud capteur en échec) et se termine par une auto -reconfiguration qui concerne la remise en état de la partie défectueuse du système et permettant au réseau de poursuivre sa mission malgré l’évidence d’un défaut.

La reconnaissance en ligne permet de détecter en continu un défaut en se basant sur le modèle

de comportement, afin de détecter, localiser et identifier une défaillance. La figure 4.1 montre le diagramme de blocs associé au diagnostic en ligne pour réseau de capteurs sans fil.


87

Figure. 4.1 – Schéma du diagnostic en ligne pour un RCSF.

4.3 Contexte de notre travail

Une partie importante de notre travail porte sur le développement de models et algorithmes pour la surveillance d’un réseau de capteurs sans fil et cela en s’appuyant sur les propriétés de la théorie des graphes et de la redondance matériel. Plus précisément dans ce chapitre, nous travaillons sur l’élaboration de modèles et le développement d’outils permettant le contrôle en ligne des composants d’un RCSF et qui aident à la reconfiguration du réseau.

L’objectif visé, est la vérification du fonctionnement du réseau en cours d’opération sans

suspendre ni affecter le fonctionnement normal qui reste prioritaire par rapport aux opérations de vérifications, pour cela il nous faut un schéma de routage adéquat qui prend en charge les informations urgentes de supervision, afin de les routés vers la station de surveillance sans perturbé le bon fonctionnement du réseau. On présente dans ce chapitre les travaux que nous avons développés en ce sens dans le cadre de la surveillance en ligne d’un RCSF. Afin d’atteindre cet objectif, les architectures et modèles proposés exploitent essentiellement les propriétés de la théorie des graphes et la redondance matériel.

- La redondance en matériel concerne la disponibilité dans le réseau de plusieurs nœuds capteurs redondants (comme moyen pour économiser la consommation d’énergie, l’équilibrage des charges et rendre le RCSF tolérant aux fautes).

4.4 Travaux existants dans le domaine surveillance des RCSF

Un certain nombre d'efforts indépendants ont été réalisés ces dernières années pour le développement d’architectures matérielle et logicielle nécessaire pour les réseaux de capteurs sans fil. Les défis et les principes de conception impliqués dans la gestion des RCSF sont discutés dans certains nombres de travaux récents [Estr01, Estr99, Mang00, Pott00, EstD01]. Un bon aperçu récent sur les réseaux de capteurs sans fil se trouve dans [Akyi02].

Les mécanismes d'auto-configuration et d'auto-organisation sont nécessaires en raison des

conditions d'opération de surveillance dans des environnements incertains et dynamiques. Une certaine attention a été donnée au développement de mécanismes d'auto-configuration et d'auto-organisation localisé, distribué, pour les réseaux de capteurs sans fil [Cerp02, Sohr00].


88

Les réseaux de capteurs sans fil sont un exemple de système de calcul de grande échelle et distribué où la tolérance aux fautes est importante. Les réseaux de capteurs doivent être économiquement fiables, les différents noeuds capteurs doivent être des dispositifs peu coûteux. De tels dispositifs sont susceptibles d'exhiber des comportements incertains. Par conséquent, il est important de garantir que le comportement défectueux de différents composants n'affecte pas le comportement global du réseau. Certains des premiers travaux dans le domaine des réseaux de capteurs sans fil se concentrent sur le routage fiable avec des topologies arbitraires des réseaux [Iyen92, Iyen94], caractérisent les modalités des défauts [Pras91, Pras94], tolérant aux fautes quand ils performent l’intégration des nœuds capteurs [Chak02] et assurent la couverture des phénomènes physique [Ches02]. Un mécanisme pour détecter les défauts dans les réseaux de capteurs sans fil est décrit dans [Paol03].

Après de nombreuses recherche bibliographique, on a constaté qu’il Il y a peu de travaux antérieur dans la littérature sur la détection et la correction des fautes dans un réseau de capteurs sans fil.

Pour contribuer dans ce domaine qui est peut riche comme indiqué précédemment. Nous proposons un système de surveillance qui sera basé sur des algorithmes centralisés, par exemple : des algorithmes pour la détection des voisins RNG, couverture des cibles, etc …

La surveillance sera basée sur les flux d’informations qui circulent dans le réseau (voir la

figure 4.2). 4.5 Modélisation d’un RCSF

Pour la modélisation du réseau, on se base sur les propriétés fournies par le graphe représentant le réseau de capteurs sans fil suivant :

Figure 4.2 – graphe de connectivité et couverture d’un RCSF


89

De la figure 4.2, on peut déduire le modèle de graphe présenté par la figure 4.3. C’est un graphe plus formel puisque il regroupe l’ensemble des flux d’information qui circulent dans le réseau : Data i,m Figure 4.3 – graphe de dépendance d’un RCSF. Où Ni : le nœud capteur d’ordre i , i = 1.. n Cj : événement à capter, j = 1..m fi -1,i : flux d’information transmis du nœud i-1 au nœud i Data i,m : information collectée par le nœud i de l’événement m

Comme illustré dans la figure 4.3, le système se compose d’un ensemble de nœuds capteurs. Où chaque nœud i reçoit des entrées notés Ui(t) ( les signaux d’entrées au nœud i à l’instant t) et génère des sorties notés Yi(t) ( les signaux de sorties du nœud i à l’instant t). Puis une fonction de transfert G(Ui(t)), qui transforme par agrégation ou fusion les entrées Ui(t) du nœud capteur en signal de sortie Yi(t). S’ajoute à cela les fautes qui affectent un nœud de capteur. La figure 4.4, illustre le modèle d’un composant élémentaire : fi(t) Ui(t) Yi(t) Figure 4.4 - Modèle d’un composant élémentaire

Un composant élémentaire (nœud capteur), réagit soit à des événements exogènes du système, soit à des événements internes produits par un autre composant élémentaire. Ce composant peut répondre à de tels événements en produisant des événements vers l’environnement ou vers d’autres composants élémentaires du système. Ainsi, le modèle d’un composant élémentaire doit exprimer la réponse à un stimulus (une séquence d’événements) par une autre séquence d’événements.

CM

Ni

Ni - p

Ni - 2

Ni - 3 Ni - 1

C1

C2 fi -1, i

Ni + 1

fi , i + 1

Data i-1,1

Noeud de capteur G(Ui(t))

Couverture d’événement

Connectivité


90

Ce principe peut être facilement modélisé à l’aide de iΓ , dont l’objectif est de modéliser la

traduction d’une séquence d’entrée en une séquence de sortie. iΓ , est un 4-uplet :

(.)),,,( i

ii

Fautes

i

Sorties

i

Entréesi G∑∑∑=Γ (5.7)

Où :

i

Entrées∑ : Les entrées du nœud capteur n° i : ensemble des événements

déclencheurs (Événements dont la cible est iΓ ).

i

Sorties∑ : Les sorties du nœud capteur n° i : ensemble des événements émis par le

noeud capteur (événements dont l’origine est iΓ )

ii

Fautes∑ : Les fautes qui affectent le nœud capteur n° i

(.)iG : Fonction (fonction d’agrégation ou fusion des valeurs d’entrées

au nœud capteur n° i) 4.6 Déploiement des nœuds capteurs

Le déploiement des nœuds capteurs ressemble au problème de la galerie d’art [ORou87], qui consiste à déterminer le nombre d’observateur nécessaires pour couvrir une salle de galerie d’art de telle sorte que chaque point soit visible par au moins un observateur. Ce problème a été résolu d’une manière optimale dans un espace 2D, et a été défini comme problème NP complet dans le cas du 3D. Un placement basé sur une grille de nœuds capteurs pour une surveillance efficace a été proposé dans [Chak02]. Les nœuds de capteurs sont placés aux points de grille tels que chaque point de grille est couvert par un sous-ensemble unique de ces capteurs. Le problème de placement a été formulé en termes de minimisation de coût sous les contraintes de couverture. Ceci est développé en un modèle de programmation entière (ILP) pour résoudre le problème de déploiement. Une approche diviser pour régner a été également utilisée pour résoudre les grandes configurations (nombre de points de grille > 50), où le modèle en ILP nécessite un grand temps d’exécution. [Megu01] a proposé un algorithme polynomial optimal pour résoudre la meilleure couverture. Cet algorithme est basé sur une combinaison des techniques de la géométrie combinatoire et de la théorie des graphes, particulièrement les algorithmes de recherche de graphe et le diagramme de Voronoi [MegS01, Megu01].

Les applications visées sont, entre autres, les réseaux de surveillance (application militaire) ou

des réseaux de surveillance sismiques (application civile) pour lesquelles la topologie peut-être simple et/ou régulière. Nous supposons dans notre travail, qu’il est possible de placer les capteurs de manière organisée ou bien de les répondre aléatoirement. Il y a des scénarios d’applications militaires comme décrits dans [Mhat04] pour lesquels il est possible d’avoir un contrôle complet de placements des nœuds. Pour les applications civiles, il est possible d’envisager que les capteurs sont attachés à un dispositif de renforcement de béton afin de mesurer l’activité sismique ou le trafic sur un pont.

Dans notre travail, on propose une configuration spéciale pour les nœuds capteurs, de sorte

que certains capteurs seront actifs et d’autres en mode veille (ou sleep mode). Cette technique nous permet d’économiser l’énergie globale du réseau tout en gardant la disponibilité des services connectivité et couverture et par la suite d’augmenter la longévité du réseau.


91

La figure 4.5, illustre le déploiement aléatoire des nœuds capteurs et des cibles.

Figure 4.5 - Déploiement aléatoire des nœuds capteurs et des cibles. Remarques :

- Le déploiement des capteurs est une issue critique parce qu'il affecte le coût et la capacité de détection d'un réseau de capteurs sans fil.

- Un bon déploiement des nœuds capteurs devrait assurer la couverture et la connectivité du réseau (voir figures 4.6 et 4.7) .

Figure 4.6 - Déploiement pour assurer la couverture Figure 4.7 - Déploiement pour assurer dans un local la connectivité dans un local


92

4.7 Les stratégies tolérantes aux fautes

Dans la plupart des cas, les réseaux de capteurs sans fil sont déployés dans un environnement hostile, de ce fait les nœuds et les liens sans fil éprouvent des échecs fréquents, de tels échecs de nœuds ou de liens ont souvent un impact significatifs sur le fonctionnement et la fiabilité des réseaux de capteurs sans fil et des application de niveau supérieur. Dans cette section nous proposons des solutions de surveillance pour que le RCSF soit tolérant aux fautes. On se basant sur les propriétés offertes par la théorie des graphes, puisque les réseaux de capteurs sont souvent modélisés par les graphes (comme indiqué dans le chapitre 3).

La question qui se pose, c’est comment assurer la tolérance aux fautes dans un RCSF. Une des

techniques traditionnels de tolérance aux fautes, consiste à construire une topologie reliée par k nœuds / arcs.

D’après les objectifs fixés et les besoins évoqués dans le cahier des charges, on propose les

solutions suivantes:

- Une stratégie pour assurer une connectivité permanente du réseau. - Une stratégie pour assurer une couverture efficace des événements, associé à une

stratégie pour la réduction des coûts énergétiques.

4.7.1 Stratégie pour garantir la connectivité du RCSF

Nous nous intéresserons dans cette section, aux méthodes de prédiction de partitionnement du réseau. Plus particulièrement, nous proposerons une méthode se basant sur les propriétés de la théorie des graphes, cela afin de garantir une communication tolérante aux fautes entre toute paire de nœuds capteurs.

Pour permettre une utilisation « longue durée » des services connectivité et couverture, il faut

assurer leurs disponibilités. Autrement dit Prédire les déconnexions et les endroits non couverts du réseau. 4.7.1.1 Objectifs

Les algorithmes de prédiction de partitionnement comme outil tolérant aux fautes visent à l'amélioration de la durée de vie d'un service par la détection de rupture de la connexité du réseau. Comme l'illustre la figure 4.8, la perte d’énergie, la mobilité des noeuds, ,ainsi que la portée limitée de leur communication, etc. …, implique la possibilité de voir disparaître toute possibilité de trouver une route entre un nœud capteur source et un nœud capteur destination.

Si on pouvait fournir aux applications la possibilité de détecter un tel événement, celles-ci

pourraient adapter leur comportement afin de maintenir le service. Plusieurs réactions à un tel événement sont envisageables. En fonction de la nature du service, il est même tout à fait possible de fournir plusieurs types de comportement. Par exemple, le renforcement des routes par l’activation de quelques nœuds endormis, déplacement des capteurs, etc.. .


93

Nœud source déplacements des nœuds capteurs Nœud destination Lien radio Lien rompu Figure. 4.8 - Partitionnement du réseau dû à la mobilité des nœuds capteurs.

La section suivante présente quelques travaux existants en matière de prédiction de partitionnement.

4.7.1.2 Travaux existants

Dans [Park97], Park et al. présentent TORA, un protocole de routage adaptatif pour les réseaux ad hoc assurant une maintenance des routes. Dans ce protocole, les auteurs utilisent une méthode de détection de partition du réseau après coup qui permet de nettoyer les tables de routages des entrées concernant les noeuds qui ne sont plus atteignables. Ce protocole détecte donc la partition du réseau après que celle-ci soit arrivée. Cette approche ne permet donc pas de réagir en avance à une future déconnexion.

Dans [Shah01], Shah et al. cherchent à améliorer l'accès aux données dans un réseau ad hoc en

détectant les partitionnements du réseaux avant qu'ils n'arrivent. Dans leur scénario, un noeud n1 nécessite des informations qui sont disponibles sur un autre noeud situé quelque part dans le réseau (notons le n2). Afin de permettre à n1 d'accéder aux données situées sur n2 même si la connexion avec ce dernier casse physiquement, les auteurs proposent un mécanisme de réplication des données basé sur un système de prédiction de partitionnement. Chaque noeud embarque un système de positionnement de type GPS et calcule sa vitesse par mesures successives de sa position. Périodiquement, chaque noeud diffuse cette information dans le réseau. Donc, chaque noeud appartenant à une même composante connexe connaît le comportement de ses voisins concernant la mobilité. Ils peuvent donc prédire, par interpolation de trajectoire, à quel moment un noeud hébergeant une information donnée va quitter la composante avant qu'il le fasse vraiment.

Wang et al. proposent une approche similaire dans [Wang02]. Néanmoins, leur proposition est

plus centralisée et est basée sur une extension du Référence Point Group Mobility (RPGM) par Hong et al. [Hong99]. Les noeuds embarquent un système de positionnement et envoient leur position et leur vitesse à un serveur central qui les rassemble en groupe en fonction de leur caractéristique de mobilité (position, vitesse). Le serveur connaît alors la façon dont se déplacent chaque groupe et peut prédire les partitionnement du réseau et avertir les noeuds concernés. Les avantages et inconvénients d'une telle méthode sont équivalents à


94

ceux de la méthode citée précédemment avec pour inconvénient supplémentaire l'utilisation d'un serveur central qui devient alors un point critique du réseau, tant au niveau de la charge réseau qu'au niveau disponibilité.

Malgré les bons résultats que peuvent donner de telles méthodes, les contraintes qu'elles

entraînent rendent impossible leur utilisation sur tout type d'objet. 4.7.1.3 Algorithme pour le système de prédiction de connectivité

Nous proposons d'effectuer des mesures sur la ou les routes disponibles entre un nœud capteur source et un noeud capteur destination à intervalles réguliers. Si une faiblesse dans la liaison est détectée, nous pouvons alors soit reconfiguré le réseau par exemple : réveiller certains nœuds capteurs ou les déplacés pour renforcer les routes, ou bien prévenir le routage pour qu’il adapte son comportement en fonction de sa politique de réaction face aux ruptures du réseau.

Nous pouvons alors, grâce à cette petite analyse, proposer un algorithme de prédiction de

partitionnement répondant à nos besoins, qui sera exécuté périodiquement. Les étapes de cet algorithme sont :

L'algorithme proposé est très simple mais possède un point non encore éclaircie, il s’agit de

l'évaluation de la robustesse du lien. C'est cette évaluation que nous allons étudier dans la suite de ce chapitre. Dans la littérature il existe plusieurs techniques d’évaluation tel que : la notion de liens critiques, des noeuds critiques et des ensembles de chemins nœud/arc-disjoints.

Dans notre cas, nous proposerons une évaluation de la connectivité, basée sur la recherche des

ensembles de chemins disjoints, et des propriétés de la connexité des graphes. Définition 4.1 : La robustesse1

- L’IEEE définit la robustesse comme "le degré selon lequel un système, ou un composant, peut fonctionner en présence d’entrées invalides ou de conditions environnementales stressantes" (IEEE Std 610.12-1990) [Pach04].

- Nous proposons aussi la définition informelle suivante : Un système/composant est dit robuste vis à vis d’une propriété si et seulement si celle-ci est préservée lors de toutes exécutions, y compris en dehors des conditions nominales. Plus précisément, le système garde un fonctionnement acceptable en présence d’entrées invalides, de dysfonctionnements internes, de conditions de stress, de pannes, etc.

1 Voir [Pach04], pour des définitions plus formelles.

- Évaluer la robustesse du lien entre le nœud capteur source et le nœud capteur destination

- Si cette robustesse est inférieure à un seuil donné , Envoyer une alerte


95

4.7.1.4 Évaluation de la robustesse du lien par un ensemble de chemins noeud-disjoints • Description de la méthode

La méthode d'évaluation que nous proposons se base sur la propriété de la k-connexité dans un graphe (donnée par la définition 4.2) et sur l'idée suivante. Plus il y aura de chemins existant entre un nœud capteur source et un noeud capteur destination, moins les chances de rupture de la connexion sont importantes. En effet, si un des chemins disparaît, la communication sera toujours possible en passant par un autre. La figure 4.9, illustre cette idée grâce à deux topologies.

(a) (b) Nœud source Noeud intermédiaire Noeud destination Nœud défaillant Figure. 4.9 - Exemple de topologies.

Dans le premier cas, figure 4.9.a, le lien est fiable. En effet, si un nœud disparaît, il reste encore deux routes possibles pour faire transiter les paquets. Par contre, dans le deuxième cas, figure 4.9.b, s’il ne reste qu'un chemin et que celui-ci cède, la communication est définitivement rompue.

Définition 4.2 : k-connectivité

Le graphe de communication d'un ensemble de capteurs M est dit k-connecté si pour deux sommets quelconques Ii et Ij de M, il existe k sommet de disjoints chemins de Ii à Ij. Une définition équivalente est, que après suppression de n'importe quel k-1 noeuds le graphe de communication de M reste encore connecté. On dit aussi qu’il y a K chemins entre chaque deux nœuds. Les figures suivantes illustrent quelques cas de k-connexité [Hwan05, Zhou04] : Figure.4.10.a – réseau 1-connecté Figure. 4.10.b - réseau 2-connecté Figure.4.10.c - réseau 3-connecté


96

Définition 4.3 : Chemins noeud-disjoints

Un ensemble de chemins noeud-disjoints est un ensemble de chemins qui n'ont en commun que la source et la destination [Ziel06].

Ainsi, cet ensemble permet de représenter avec une certaine fiabilité le fait que le lien entre les

noeuds capteurs source et destination est fort ou non. En effet, s'il y a de nombreux chemins noeud-disjoints entre les deux noeuds, il faudra alors qu'un nombre important de noeuds cessent de participer au routage des paquets entre le noeud source et destination (parce qu'ils se sont déplacés ou qu'ils se sont éteints par perte d’énergie ou panne accidentelle) pour que la communication soit rompue.

La valeur de l'évaluation de la robustesse du lien sera alors le nombre de chemins noeud-

disjoints qu'il existe entre le nœud capteur source et le nœud capteur destination. S'il n'en reste qu'un (réseau 1-connecté), le lien devient non faible car la disparition d'un seul noeud peut entraîner la rupture de la connexion entre les nœuds source et destination. La figure 4.11 montre l'évolution du nombre de chemins disjoints entre les nœuds durant une connexion. On voit bien que ce nombre chute progressivement jusqu'à tomber à 1 peu avant la rupture effective de la connexion.

Figure. 4.11 - Évolution du nombre de chemins disjoints entre deux nœuds capteurs [HausO5]. • Génération des ensembles de chemins disjoints

Le but et de pouvoir générer un ensemble de chemins noeud-disjoints existant entre le nœud capteur source et destinataire. Ce problème est classé NP-difficile [Laco03, Papa02].

Alerte

Déconnexion


97

• Travaux existants

Le problème est, non trivial et est comparable aux travaux existants sur le routage multi-

chemins pour la qualité de service [DasK03, Papa02, LinX02, LeeS01, Leun01]. Dans ce contexte, le but est de générer le maximum de chemins possible lors de la recherche de route afin de pouvoir obtenir une qualité de service maximum grâce à la distribution des paquets sur les différentes routes disponibles.

Dans [Papa02], Haas et al. proposent un algorithme distribué pour calculer un ensemble de

chemins disjoints. Ils utilisent une méthode de construction itérative qui fusionne un ensemble de chemins précédemment obtenu avec un nouveau chemin qui contient un ou plusieurs liens arrière (i.e. un lien qui va de la destination à la source).

Dans [DasK03], Das et al. utilisent un algorithme de diffusion qui n'est plus basé sur un

numéro de séquence, mais sur le chemin actuellement parcouru par le paquet de recherche. On note respectivement s et d les noeuds source et destination. Le paquet de recherche de route contient un nombre de saut qui est décrémenté à chaque retransmission et la liste des noeuds constituant le chemin que le paquet suit.

Lee et al. ont proposé une extension de la diffusion aveugle dans [LeeS01]. Ils utilisent

toujours un numéro de séquence pour éviter les rediffusions inutiles mais ils rajoutent une condition sur l'émetteur direct du paquet afin de rendre moins restrictive la règle de non retransmission. • Notre proposition

Dans notre cas, on peut se limité à la 2-connexité, puisqu’il suffit d’avoir aux moins deux chemins entre la source et la destination, pour garantir une certaine connectivité tolérante aux fautes. La définition 4.4, sur un graphe biconnexe et le théorème de Menger [Meng27, Böhm01, Mohi02], nous donne une condition nécessaire et suffisante. Théorème 4.1 : (Menger , 1927) Soit G un graphe non orienté. - Soient s et t deux sommets distincts non adjacents de G. Alors la cardinalité minimum d’un

ensemble de sommets (s,t)-séparateur k(s,t) est égale au nombre maximum de (s,t)- chemins indépendants.

- Soient s et t deux sommets distincts de G. Alors la cardinalité minimum d’un ensemble d’arêtes (s,t)-séparateur k’(s,t) est égale au nombre maximum de (s,t)-chemins arête-disjoints. [Mohi02]

Corollaire 4.1 (Menger) Soit G un graphe à au moins deux sommets.

- G est k-connexe si et seulement si deux sommets quelconques peuvent être joints par k chemins indépendents.

- G est k-arête connexe si est seulement si deux sommets quelconques peuvents être joints par k chemins arête-disjoints.

Dans un graphe non orienté le nombre maximum de chemins deux à deux noeud-disjoints d'un

sommet x à un sommet y non adjacents est égal au nombre minimum de noeuds à supprimer pour déconnecter x de y (voir le détaille sur le théorème de Menger dans la partie annexe B).


98

La recherche de chemins noeud-disjoints entre deux noeuds peut donc se ramener à la recherche de noeuds dont la suppression déconnecte ces derniers. De tels noeuds sont dits critiques (ou points d’articulation), et peuvent être détectés par des algorithmes centralisés de type recherche en profondeur [Tarj72, Gond95].

Dans [Goya02], Goyal et Cafery utilisent la notion de liens critiques afin de prédire des

partitionnements. Cette notion est identique à celle de noeud critique à ceci près qu'on ne considère alors pas les noeuds dont la suppression déconnecte le réseau mais les liens. Ces liens peuvent également être détecté par une recherche en profondeur sur le graphe complet. C'est cette solution qu'on va retenir pour la surveillance de notre réseau, dans le cas de la connectivité.

Définition 4.4 : Un graphe est biconnexe si pour chaque couple vuvu ≠,, , il existe deux chemins sommet-disjoints qui joignent u et v [Ziel06]. (voir figure 4.13)

Figure 4.13 – graphe biconnexe Définition 4.5 : Point d'articulation est un sommet dont la suppression avec les arêtes adjacentes donne un graphe non connexe [Ziel06]. Définition 4.6 : Composante biconnexe le plus grand sous graphe biconnexe [Ziel06]. Exemple : Le graphe suivant présente Six points d'articulation (en jaune) et 7 composantes biconnexes [Ziel06].

Figure 4. 14 - graphes à composantes biconnexes


99

Propriété: Un graphe est biconnexe si et seulement si il n'a pas de points d'articulations (ou point de séparation) [Ziel06]. • Autres propriétés des composantes biconnexes :

- Deux composantes biconnexes sont soit disjointes soit possèdent un sommet commun qui est un point d'articulation,

- Un point d'articulation appartient à au moins deux composantes biconnexes, Chaque arête appartient à exactement une composante biconnexe,

- Si le graphe possède au moins un sommet alors chaque composante biconnexe possède au moins deux sommets,

- Dans un graphe biconnexe, Il y a deux chemins disjoints entre n’importe quelle paire de sommets

- Dans un graphe biconnexe, Il y a un cycle au travers de n’importe quelle paire de Sommets,

- Un graphe sans point d'articulation est un graphe bi-connexe.

• Algorithme de détection des points d'articulation On suggère de travailler sur un graphe de connectivité planaire (graphe RNG). Cela permet de

réduire la complexité du graphe disque unitaire, diminué les interférences radio et rend la surveillance du service connectivité plus facile.

Les problèmes de 2-connexité se ramènent à un parcours en profondeur [Maco97] : Algorithme : Détection des points d’articulation d’un graphe non orienté

a) Effectuer une fouille en profondeur dans G. Soient

• T l’arborescence engendrée par la fouille,

• PréNum [v] ≡ le numéro attribué par la fouille au sommet v de G. {Cette numérotation désigne le pré-ordre comme ordre de visite de T}

b) Parcourir l’arborescence T en post-ordre. Au moment de la visite de chaque noeud v, calculer PPH [ v] (le PréNum du Plus Haut) comme le minimum de :

• PréNum [ v],

• PréNum [ w] pour tout sommet w tel que ∃{ v, w} ∈ A–T, • PPH [ x] pour tout sommet x qui est un fils de v (dans T).

c) Déterminer les points d’articulation de G comme suit: i) la racine de T est un point d’articulation de G

⇔ elle possède plus d’un fils. ii) un sommet v autre que la racine de T est un point d’articulation de G

⇔ v a un fils x tel que PPH [ x] ≥ PréNum [ v] .


100

L’algorithme de détection des points d’articulation que nous avons présenté [Maco97], possède une complexité de l’ordre de O(N + M) pour un graphe ayant N sommets et M arêtes. On peut considérer cet algorithme comme une spécialisation du parcours en profondeur de Tarjant.

L’exemple suivant, illustre l’application de l’algorithme de détection sur le graphe G (figure

4.15), la génération de l’arborescence T par la fouille (figure 4.16), parcours de l’arborescence T en post-ordre, puis enfin la détermination des points d’articulation du graphe G.

Figure 4.15 - Graphe G (de connectivité) Figure 4.16 - T l’arborescence engendrée par la fouille

Lorsqu’on effectue une fouille en profondeur, le graphe ci-dessous contient toutes les arêtes du graphe initial: les arcs gras forment un arbre recouvrant, tandis que les autres sont représentés en grisé. De plus, ces derniers vont nécessairement d’un noeud à un de ses ancêtres.

À gauche de chaque noeud v et en gras est indiqué PréNum [v], traduisant l’ordre de sa visite dans une exploration du graphe en pré-ordre.

À droite de chaque noeud est indiqué PPH [v] défini ainsi: soit w le noeud le plus haut dans T

tel que on peut atteindre w à partir de v en descendant autant de lignes continues (arcs de T) qu’on veut et en remontant au plus une ligne grisée (arête de A–T). Alors : PPH [ v] = PréNum du Plus Haut noeud atteignable à partir de v = PréNum [ w]. Ainsi: PPH [7] = PréNum [4] = 6, PPH [6] = PPH [5] = PréNum [2] = 2.


101

Étude de PPH : • Le plus haut noeud w atteignable de cette manière est nécessairement un ancêtre de v. Le plus

haut w est donc celui qui minimise PréNum. • Soit un noeud v autre que la racine, et supposons que v n’a pas de fils. Alors ce n’est pas un point d’articulation de G (évident).

• Soit v un noeud autre que la racine, et soit x un fils de v.

- Supposons que PPH [ x] < PréNum [ v]. Alors il existe une chaîne d’arêtes qui lie x aux autres sommets du graphe, même si v est supprimé. (cas du noeud 3 de la figure). Donc, si cela est vrai pour tous les fils x de v, v n’est pas un point d’articulation.

- Si, pour au moins un fils x de v, PPH [ x] ≥ PréNum [ v], alors il n'existe pas de chaîne pour relier x au père de v (cas du noeud 4 de la figure). Donc v est un point d’articulation.

• Si v est la racine, c’est un point d’articulation si et seulement si v a au moins 2 fils (dans ce cas la déconnexion de la racine sépare ses sous-arbres) , c’est le cas du noeud 1 de la figure

4.16. Remarques : • On peut faire une généralisation est passé des graphes 2-connexe en graphes k-connexe. • La détection des points d’articulation dans le graphe représentant l’état du réseau, permet : de

remédier aux problèmes de déconnexion, avant leurs apparitions, par une reconfiguration du réseau (renforcement des régions du réseau où il y a les points d’articulation, exemple : activation de certains nœuds capteurs qui sont en mode veille, déplacement des nœuds vers les points d’articulations, augmentation de la porté de connectivité de certains noeuds).


102

4.7.2 Stratégie pour garantir la couverture du RCSF

Nous concevons un mécanisme de recouvrement, qui prend en compte l’économie de l’énergie du réseau, dans lequel seulement une partie des nœuds capteurs qui participent à la couverture des cibles sont en activités, alors que touts les autres seront en mode veille.

En traite dans cette partie le problème de couverture des cibles. Le but est de maximiser la

vie du réseau sans fil, contraint par la puissance, déployée pour surveiller un ensemble de cibles avec des endroits connus (c1,c2, …. , cm). Nous considérons un grand nombre de nœuds capteurs, déployées aléatoirement ou de manière organisé au proximité d’un ensemble de cibles, qui envoient l’information captée à un nœuds central (le Sink) pour traitement. La méthode employée pour prolonger la vie du réseau se base sur la définition 4.7 et sur le théorème de (König 1931, Egerváry 1931 voir annexe B). Le but est d’installer le minimum de nœuds captures actives, tout en répondant aux exigences de couverture et de réduire l’énergie consommée par le réseau. Cette méthode abaisse la densité des nœuds actifs, et de ce fait réduisant l’interférence dans la couche MAC.

Définition 4.7 : k-couverture

Soit un réseau de capteurs constitue de n nœuds capteurs et une région d’intérêt A, on dit qu’on a une k-couverture si et seulement si les deux conditions suivantes sont vérifies [Hwan05, Zhou04] :

1. Satisfaction des conditions de couverture pour un maximum de temps de la vie du réseau

2. Chaque point q dans A est couvert par au moins k distinctes capteurs. Les figures 4.17.a et 4.17.b, présentent des exemples de k-couverture : Figure. 4.17.a – points K- couverts Figure. 4.17.b - région K-couverte

1-couverture 2-couverture 3-couverture

6

54

3

2

1

7

8 R


103

4.7.2.1 Travaux existants

La plus part des travaux sur la couverture des RCSF, se basent sur la porté circulaire de la couverture [AlyM06].

Dans la littérature on trouve les travaux de :

- Maguerdichian et al : dans leurs travaux ils définissent si chaque points ou cibles est k-couverte. Ils utilisent le diagramme de voronoi pour modéliser la couverture des régions par les nœuds capteurs.

- Potkonjack et al: partitionnent les noeuds capteurs dans des ensembles mutuellement

exclusive. Maximise la durée de vie de la couverture par division de la charge de couverture sur les nœuds capteurs couvrant des domaines communs.

- Tian et al : leurs travaux se basent sur la porté circulaire de la couverture des nœuds

capteurs. Ils utilisent pour cela une heuristique distribué, pour calculer un planning de couverture. L’algorithme est polynomial en nombre de nœuds capteurs.

- Huang et al : organisent les nœuds capteurs selon un nombre minimum de capteurs requis

pour couvrir le secteur surveillé. En vérifiant si chaque points dans le secteur est surveillé par au moins k nœuds capteurs au lieu de seulement un nœud capteur.

Remarque : Toutes les solutions proposées si dessus sont basées sur l’intersection des régions de couvertures.

4.7.2.2 La durée de vie de la couverture

C’est la durée de couverture d’une cible Cj par un ensemble de nœuds capteurs S(j), jusqu'à ce que ces derniers manquent d’énergie [AlyM06]. 4.7.2.3 Définition du problème

Considérant N nœuds capteurs S={S1…Sn} , aléatoirement déployés dans un plan euclidien pour couvrir à tout moment M cibles C={C1,…Cm}, || S || >> || C ||. Chaque nœud capteur a une énergie initiale Ei (voir figure 4.18).

Figure 4.18 – déploiement aléatoire des capteurs pour l’observation des cibles


104

La figure 4.19, montre un exemple avec quatre nœuds capteurs S1, S2, S3, S4 et trois cibles,

C1, C2, C3. Chaque nœud possède un rayon de capture r.

Figure. 4.19 – Exemple avec trois cibles C = {C1, C2, C3} et quatre capteurs S ={ S1, S2, S3, S4 }

De ce réseau sans fil, on déduit un graphe biparti, qui représente les relations de couverture

entre chaque cible et un certain nombre de nœuds capteurs. La figure 4.20, illustre ce graphe biparti : Cibles Nœuds capteurs C3 X S1 S2 C2 X S3 C1 X S4 Figure. 4.20 – Graphe biparti, couverture des cibles par les nœuds capteurs

Pour que ce réseau soit tolérant aux fautes, il faut que chaque cible soit couverte part k nœuds

capteurs. Dans le cas où k-1 nœuds de capteurs tombent en échec, la cible reste couverte et le réseau reste opérationnel en terme de couverture.

Si k= 2, pour chaque cible, on dit que le réseau est bi couvert et c’est une condition suffisante

pour que le service couverture soit disponible.

Dans l’exemple précèdent on a :

- La cible C3 est couverte par 2 nœuds capteurs est donc même si un nœud tombe en panne, l’autre nœud assure la couverture de la cible C3.

- Même chose pour la cible C2. - La cible C1 est couverte par 3 nœuds capteurs est donc même si 2 nœuds tombent en

panne, un nœud assure la couverture de la cible C1. Dans ce cas on peut dire que le réseau est tolérant aux fautes pour le service couverture.

c3 X

X c2 c1 X

S1

S2

S3

S4


105

D’une autres part, d’après le théorème [Sohr00], cité dans le chapitre 1 : la vérification de la

couverture suffit pour décider sur l’état de la connexité du réseau. Sous ces conditions, on peut se limiter à la surveillance de la couverture du réseau.

Afin de prédire la robustesse de chaque relation de couverture entre une cible et les nœuds

capteurs on propose l’algorithme qui va être décrit dans la section suivante :

4.7.2.4 Algorithme pour le système de prédiction des couvertures

Nous proposons donc la même stratégie que celle établie pour la connectivité précédemment. On procède donc par effectuer des mesures sur la ou les liens disponibles entre une cible et les nœuds capteurs qui la couvrent à intervalles réguliers. Si une faiblesse est détectée, nous pouvons alors prévenir une reconfiguration de la couverture des nœuds capteurs pour qu’ils adaptent leurs comportements face aux ruptures de la couverture, dus aux nœuds qui tombent en pannes.

Nous proposons un algorithme de prédiction de la non disponibilité de la couverture, qui sera

exécuté périodiquement. Les étapes de cet algorithme sont :

Pour évaluer la robustesse du lien entre la cible et les nœuds capteurs, nous proposerons une

évaluation basée sur le calcul de degré de chaque sommets cible du graphe biparti de couverture. La métrique du degré est certainement la plus naturelle et la plus simple à calculer puisqu’elle

définit le poids d’un sommet par le nombre de ses voisins. 4.7.2.5 Évaluation de la robustesse des liens de couverture pour chaque cible

Le but et de pouvoir générer un ensemble de liens de couverture existant entre la cible et les nœuds capteurs. Dans ce contexte, le but est de générer le maximum de lien de couverture, afin de pouvoir obtenir une qualité de service de couverture maximum grâce à la disponibilité de k nœuds capteurs pour couvrir une cible.

• Évaluer la robustesse du lien entre la cible et les nœuds capteurs qui la couvrent • Si cette robustesse est inférieure à un seuil donné, envoyer une alerte

(reconfiguration : activation de certains nœuds où les liens de couverture sont faibles)


106

L’algorithme :

- Complexité de l’algorithme : L’algorithme est de complexité polynomiale de l’ordre de

O(m.d). Où d est la densité du réseau c’est à dire le nombre moyen de degré du réseau par rapport à chaque cible et m le nombre de cibles.

Données : Liste des neouds capteurs : SJ, j = 1..N Liste des cibles : Ci , i = 1... M Matrice d’adjacence du graphe biparti : A[M,N] V, Vi : variable logique // pour une décision de reconfiguration Résultat : Liste des degrés de chaque sommet cible : Di Décision de reconfiguration du réseau Pour i= 1 … M // parcourt des sommets cible du graphe Di :=0 Pour j= 1 … M Calcul de Di : degré de la cible Ci : (Di :=Di +A[i,j]) Si Di≥ 2 Alors // Les liens de couverture de la cible Ci sont tolérants aux fautes

Sinnon Vi=false Fin si Fin pour Fin pour I :=1 Tant que i≤ M et Vi=True Faire Si Vi = false alors V= false Fin si i ++ Fin Faire Si V= false alors // Le réseau n’est pas tolérant aux fautes et donc reconfiguration du réseau (Par activation de Certains nœuds capteurs où Vi = false ) Sinon // Le réseau est tolérant aux fautes en terme de couverture Fin si


107

Exemple : pour le graphe biparti de la figure 4.20, on obtient : d = (2 + 2 + 3) / 3 = 2 m = 3 - Représentation des relations entre les cibles et les nœuds capteurs par une matrice

de couverture : On peut représenté l’exemple de la figure 4.20, par la matrice suivante :

Nœuds capteurs Cibles

S1 S2 S3 S4

C1 1 0 1 1 C2 0 1 0 1 C3 1 0 0 1

Tableau 4.1 – Matrice d’adjacence du graphe biparti 4.7.2.6 Approche d’une couverture minimale • Formulation du problème

Le but, c’est de trouver un algorithme qui assure une couverture minimale c'est-à-dire obtenir une couverture de long vie. L’idée de base c’est de trouver un planning pour que les nœuds capteurs observent tous les cibles de manière efficace tout en économisant l’énergie consommée par le réseau. Cela peut ce faire par la recherche d’un couplage maximale dans un graphe bipartie, les nœuds capteurs qui ne seront pas couvert par le couplage seront mis en mode veille.

Considérons la même définition du problème de la section 4.7.2.3, avec en plus les contraintes

suivantes :

- Cij : Le coût énergétique de couverture (énergie par unité de temps), - Chaque capteurs peut couvrir au plus une cible dans un temps donné, - Chaque cible peut être couverte par au plus un capteur. - Toutes les cibles devront être couvertes à tout moment.

• Couplage biparti maximum

Le problème d’affectation (ou couplage biparti maximum) peut se formuler de la manière suivante [Gond79]:

Etant donné un graphe simple G=[X, U] non orienté (U un ensemble d'arête) biparti (X un

ensemble de sommet où X = X1∪X2, avec X1 = {c1,c2,…,cm} et X2 = {s1,s2,…,sn}), une affectation consiste à déterminer un sous ensemble maximum K⊂�U tel que deux arêtes quelconques de K ne soient pas adjacentes.

Degré = 3

Degré = 2

Degré = 2


108

Figure 4.21 - Exemple d'affectation

En effet le but de l’affectation est que tout élément de X1 possède un et un seul élément dans X2 et que tout élément de X2 sélectionné par un élément de X1 ne soit choisi qu’une et une seule fois.

• Couplage et couverture

Définition 4.7 Soit G = (V, E) un graphe. Un ensemble K ⊂ V est une couverture de E si toute arête de G est incidente à un sommet de K.

Soit K la couverture d'un graphe. Alors pour tout couplage M, K contient au moins une extrémité de chaque arête de M. Donc |M |≤|K|. Ainsi la cardinalité maximale d'un couplage est au plus égale à la cardinalité minimale d'une couverture. Pour un graphe biparti, il y a égalité. (Voir le théorème de (König 1931, Egerváry 1931) dans l’annexe B). • Principes généraux des algorithmes de couplage Recherche de chaîne alternée et améliorante ou augmentante (CAA)

Le problème de couplage maximal dans un graphe biparti ou non peut être résolu grâce aux deux propriétés suivantes dues à Berge, dont la démonstration figure dans [Berg83].

- Soit un graphe simple G=(X,E) , un couplage C de G, et une CAA µ pour C. Alors un transfert sur µ donne un nouveau couplage C’ avec 1' += CC .

- Un couplage est maximal si et seulement s’il n’admet aucune CAA. • Algorithme pour le couplage biparti maximal

Nous présentons maintenant un algorithme très rapide utilisant les chaînes alternées augmentantes (Théorème de Berge 1957, voir annexe B), pour trouver un couplage maximal dans un graphe biparti G(X,Y,E). Il peut aussi être vu comme une forme spécialisée de l’algorithme de Ford et Fulkerson pour le flot maximal.

Cibles Noeuds capteurs

c1

c2

c3

n1

n2

n3

n4

Cibles Noeuds capteurs

c1

c2

c3

n1

n2

n3

n4


109

L’algorithme : [Laco03] Complexité de l’algorithme : L’algorithme est de complexité polynomiale de l’ordre de O(N.M), avec N : nombre de sommets, M : nombre d’arc.

Donnée : Un graphe biparti G = (X, Y, E) Résultat : un couplage maximal (et donc une couverture minimale) Début : couplage =Ø Pour tous sommets x de X Y faire Si x non marqué alors Tant que voisin(x) est marqué faire choisir un autre voisin de x Ftq Si il existe un voisin de x non marqué alors on marque ce voisin couplage = couplage U {x voisin(x)} Fsi Fsi Fpr à ce stade de l'algorithme on a un couplage "simple" on va maintenant chercher les chaînes alternées améliorantes Tant que couplage non max Pour tous sommets x non marqué faire chaine_alternee_ameliorante = améliorer(x); amélioration du couplage; Ppr Ftq Fin Améliorer(chaîne) Données: une chaîne de départ, le graphe G muni d'un couplage Résultat: une chaîne alternée améliorante Début On récupère le dernier sommet z de la chaîne passée en paramètre. Pour tous les voisins y de z faire Si y non marqué alors chaîne_alternée = chaîne + y; marque y; marque z; Sinon on récupère dans le couplage le voisin t de y; Améliorer(chaîne+ y + t); Fsi Fpr Fin


110

• Représentation graphique des étapes de l'algorithme

Affichage du couplage simple: les sommets marqués en bleu et les arêtes du couplage en blanc.

Figure 4.22 - Couplage simple

Recherche d'une chaîne alternée améliorante. Modification du couplage: on affiche en mauve les arêtes qui vont être supprimées du couplage et les sommets affectés par cette modification. Et on affiche en vert les arêtes qui améliorent le couplage.

Figure 4.23 - Chaîne alternée améliorante

Finalement on affiche en blanc les arêtes faisant partie du couplage maximal. Les sommets et les arêtes affectés par les modifications restent en mauve.

Figure 4.24 - Couplage maximal


111

Remarques :

- Les nœuds capteurs qui n’appartiennent pas au couplage maximal (la couverture minimale), passeront en mode veille (Sleep mode). Mais cela peut conduire au problème de la couverture complète de la zone de déploiement, et de manière connexe, en dépit des capteurs inactifs. Et donc on doit là aussi prévoir un compromis entre l’économie de l’énergie et la couverture complète de la zone à observer par le réseau.

- S’il arrive que des cibles, ne soient pas couvertes. Alors des solutions de reconfiguration du réseau sont envisageables, par exemple :

o Activation des nœuds qui sont en mode veille et qui sont proches des cibles en question,

o Augmentation des portés de couverture, pour les nœuds actives proches des cibles,

o Déplacement des nœuds capteurs vers les cibles non couvertes. • Réduction des coûts énergétiques

En plus des contraintes environnementales (déploiement de réseaux de capteurs dans des

environnements hostiles ou difficiles d’accès.), une contrainte très importante est l’économie de batterie. En effet, un réseau de capteurs ne peut survivre si la perte d’énergie des noeuds est trop importante car ceci engendre des pertes de communication dues à une trop grande distance entre les nœuds capteurs. Donc il est très important que les batteries durent le plus longtemps possible étant donné que dans la plupart des applications ils sont placés aléatoirement (impossible de retourner changer les batteries). En plus, un tel réseau s’auto configure et s’auto organise, en fonction des ressources énergétiques restantes et de la distribution géographique des noeuds (disséminations initiales par largage par exemple, qui les place de manière assez aléatoire) ; ce qui implique que la connectivité et la couverture doivent être préservée autant que possible automatiquement lorsque la topologie du réseau change (suite à l’apparition, la disparition ou au mouvement de certains noeuds).

Plusieurs protocoles ont été développes ou adaptés afin d’optimiser la consommation

d’énergie durant les dernières années [Estr99]. Tous ces travaux utilisent et référencent un modèle de consommation simple où l’énergie dépensé est proportionnelle au nombre de bits émis et dépend à la fois de la distance de communication et d’une constante, le gradient distance/puissance ( pour le détaille voir chapitre 1).

La communication engendre un coût énorme pour la consommation d’énergie (plus de 80%

d'énergie consommée est pour la communication. [Estr99, Savv01, GaoQ05]. Afin de réduire cette dernière. Nous avons proposé par l’approche précédemment décrite, de choisir parmi tous les nœuds du réseau, des nœuds de capteurs qu’on peut alterner entre le mode veille et le mode actif tout en gardant la connectivite et la couverture du réseau.

Le mode veille veut dire que l’interface radio est inactif ceci implique que le capteur ne peut

ni recevoir ni émettre. Seul existe la consommation des messages de contrôle (overheads). Le Mode actif veut dire une consommation des émissions et des réceptions.


112

• Proposition de solutions pour le réveil des nœuds capteurs Le mode réveil consiste à réveiller les capteurs pour faire une découverte des voisins, cette dernière se fait périodiquement de la manière suivante. - S’il n’ y a aucun changement, c’est à dire :

o Existence d’un nœud voisin de couverture active, alors dans ce cas le nœud capteur se remet en mode veille (sleep mode).

- Dans le cas contraire (pas de capteur voisin de couverture active), alors il passe en mode actif.

L’organigramme suivant et les figures 4.26 (a) et (b), illustres le principe de cet algorithme :

Figure 4.25 – Organigramme de Mise en veille des nœuds capteurs. Figure 4.26.a - Passage d’un capteur de nouveau Figure 4.26.b - Passage d’un capteur en en mode veille mode active

Remarque :

On plus, du mécanisme de réveil automatique des nœuds capteurs, on peut donné, au superviseur, la possibilité d’activer, endormir ou déplacer des nœuds capteurs à distance. Cela entre dans le cadre de la reconfiguration du réseau.


113

4.8 Conclusion

Nous avons présenté dans ce chapitre nos solutions en terme de mécanismes pour la surveillance d’un réseau de capteurs sans fil : il s’agit de modèles et d’algorithmes tirés de la théorie des graphes, pour le contrôle de la topologie , la prévention contre la déconnection et la non couverture du réseau.

Le but de nos contributions est d’assurer une forte connectivité et couverture, afin de

maximiser la durée de vie du réseau, mais aussi d’augmenter la qualité des liens et la gestion de l’énergie.

On peut également imaginer des situations où nos modèles et algorithmes peuvent être étendus

dans le but d’inclure d’autres contraintes spécifiques à une application ou à une configuration du réseau.

Nos contributions en terme d’algorithme de surveillance et de contrôle de topologie se basent

sur des solutions centralisées. Cependant, il serait intéressant de concevoir que des approches distribuées, plus adaptée à l’environnement des réseaux de capteurs. Dans une telle approche, l’objectif est de répartir la tâche de contrôle de topologie en un ensemble de contrôles de topologie régionaux.


114

4.9 Bibliographie [Akyi02] I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A Survey on Sensor

Networks,” IEEE Comm. Magazine, vol. 40, no. 8, pp. 102-114, Aug. 2002. [AlyM06] Mohamed Aly, Kirk Pruhs, Taieb Znati & Brady Hunsaker, «On the Coverage

Problem for Myopic Sensors.», University of Pittsburgh, USA, August 2006. [Berg83] C. Berge, «Graphes», Gauthier-Villars, 1983. [Böhm01] T. Böhme, F. Göring, and J. Harant. «Menger’s theorem. Journal of Graph Theory»,

37 :35_36, 2001. [Cerp02] A. Cerpa and D. Estrin, “ASCENT: Adaptive Self-Configuring sensor Networks

Topologies,” Proc. INFOCOM, 2002. [Chak02] Krishnendu Chakrabarty, S. Sitharama Iyengar, Hairong Qi, Eungchun Cho, « Grid

Coverage for Surveillance and Target Location in Distributed Sensor Networks», IEEE Transactions on Computers, Vol. 51, N°, 12, December 2002.

[Ches02] S. Chessa and P. Santi, “Crash Faults Identification in Wireless Sensor Networks,” ,

Computer Comm., vol. 25, no. 14, pp. 1273-1282, Sept. 2002. [DasK03] S.K. Das, A. Mukherjee, S. Bandyopadhyay, D. Saha, and K. Paul. An adaptive

framework for QoS routing through multiple paths in ad-hoc wireless networks. Journal of Parallel and Distributed Computing, 63:141-153, 2003.

[EstD01] D. Estrin et al., “Embedded, Everywhere: A Research Agenda for Networked Systems

of Embedded Computers,” Nat’l Research Council Report, 2001. [Estr99] D. Estrin, R. Govindan, J. Heidemann, and S. Kumar, “Next Century Challenges :

Scalable Coordination in Sensor Networks,” Proc. ACM/IEEE Int’l Conf. Mobile Computing and Networks (MobiCom ’99), Aug. 1999.

[Estr01] D. Estrin, L. Girod, G. Pottie, and M. Srivastava, “Instrumenting the World with

Wireless Sensor Networks,” Proc. Int’l Conf. Acoustics, Speech and Signal rocessing (ICASSP 2001), May 2001.

[GaoQ05] Q.Gao, K.J.Blow, D.J.Holding, Ian Marshall, «Analysis of Energy Conservation in

Sensor Networks», 1Aston University, Aston Triangle, Birmingham, UK, 2005. [Gond79] M. Gondran, M. Minoux., «Graphes et algorithmes», Eyrolles Ed. (1979). [Gond95] Michel Gondran, Michel Minoux, « Graphes et algorithmes», Editions Eyrolles 1995. [Goya02] D. Goyal and Jr. J. Caffery . Partition avoidance in mobile ad hoc netwoks using

netwok survivability concepts. In Proceedings of the Seventh International Symposium on computers and Communications (ISCC ’02), 2002.


115

[Haus05] Michaël Hauspie, Jean Carle, David Simplot, « Partition Detection in Mobile Ad-Hoc Networks Using Multiple Disjoint Paths Set. », LIFL/IRCICA - Univ. Lille 1, 2005.

[Hong99] X. Hong, M. Gerla, G. Pei, and C. Chiang. A group mobility model for ad-hoc

wireless networks. In Proceedings of the 2nd ACM International Workshop on Modeling and Simulation of Wireless and Mobile Systems, 1999.

[HuoY01] Ying Huo, Petros A. Ioannou, and Majdedin Mirmirani, ,”Fault-Tolerant Control and

Reconfiguration for High Performance Aircraft: Review”, CATT Technical Report 01-11-01, University of Southern California, Los Angeles, USA, November 2001.

[Hwan05] Ten-Hwang Lai, «Coverage and Connectivity Issues in Sensor Networks», Ohio

State University, 2005. [IanD04] D.Ian and N.D.Georganas. , «Connectivity, maintenance and coverage preservation in

wireless sensor networks. », 2004. [Iyen92] S.S. Iyengar, M.B. Sharma, and R.L. Kashyap, “Information Routing and Reliability

Issues in Distributed Sensor Networks,” IEEE Trans. Signal Processing, vol. 40, no. 2, pp. 3012-3021, Dec. 1992.

[Iyen94] S.S. Iyengar, D.N. Jayasimha, and D. Nadig, “A Versatile Architecture for the

Distributed Sensor Integration Problem,” IEEE Trans. Computers, vol. 43, no. 2, Feb. 1994.

[Kris02] Bhaskar Krishnamachari, Deborah Estrin, Stephen Wicker, « Modelling Data- Centric

Routing in Wireless Sensor Networks», School of Electrical and Computer Engineering, Cornell University, Ithaca, 2002.

[Kris04] Bhaskar Krishnamachari, Sitharama Iyengar, «Distributed Bayesian Algorithms for

Fault-Tolerant Event Region Detection in Wireless Sensor Networks.», IEEE Transactions on computers, Vol. 53, N°. 3, March 2004.

[Laco03] Philipe Lacomme Christian Prins, Marc Servaux, « Algorithmes de graphes. », Edition

Eyrolles, 2ième Edition, 2OO3. [LeeS01] S. Lee and M. Gerla. Split multipath routing with maximally disjoint paths in ad hoc

networks. In Proceedings of the IEEE Internation Conference on Communications, pages 3201_3205, 2001.

[Leun01] R. Leung, J. Liu, E. Poon, C. Chan, and B. Li. MP-DSR: A QoSaware multi-path

dynamic source routing protocol for wireless adhoc networks. In Proceedings of the 26th IEEE Annual Conference on Local Computer Networks (LCN 2001), Tampa, Florida, November 2001

[LinX02] X. Lin and I. Stojmenovi¢. Location-based localized alternate, disjoint and multi-path

routing algorithms for wireless networks. Journal of Parallel and Distributed Computing, 2002.


116

[Maco97] Maciej Macowicz , « Approche générique des traitements de graphes », Thèse de doctorat, Institut national des sciences appliquées de Lyon, 1997.

[Mang00] W.W. Manges, “Wireless Sensor Network Topologies,” Sensors Magazine, vol.17, no.

5, May 2000. [Marz89] K. Marzullo, “Implementing Fault-Tolerant Sensors,” TR89-997, Dept. of Computer

Science, Cornell Univ., May 1989. [MegS01] Seapahn Meguerdichian, Gang Qu, Farinaz Koushanfar, Miodrag Potkonjak,

«Exposure In Wireless Ad-Hoc Sensor Networks. », Computer Science Department University of California, Los Angeles, USA, July 2001.

[Megu01] S. Meguerdichian, F. Koushanfar, M. Potkonjak, M. B. Srivastava, «Coverage

Problems In Wireless Ad-hoc Sensor Networks», INFOCOM 2001 : 1380-1387, Anchorage, Alaska, April 22-26, 2001.

[Meng27] K. Menger. Zur allgemeinen kurven theorie. Fund. Math., 10:96_115, 1927. [Mhat04] V. Mhatre, C. Rosenberg, D. Kofman, R. Mazumdar, and N. Shroff, « Design of

surveillance sensor grids with a lifetime constraint», In European Workshop on Wireless Sensor Networks (EWSN), Berlin, Germany, January 2004.

[Mohi02] Mohiuddin Ahmed , « Decentralized Information Processing in Wireless Peer-to-Peer

Networks», University of California , Los Angeles, USA, pp. 100-106, 2002. [ORou87] J. O’Rourke, «Art Gallery Theorems and Algorithms. », New York, Oxford Univ.

Press, 1987. [Pach04] Cyril Pachon, «Une approche pour la génération automatique de tests de robustesse,»,

Revue Électronique ISDM : InfoComm Sciences for Decision Making : Permanent online journal of Information and Communication Technologies, Février 2004.

[Paol03] Andrea Paoli, ”Fault Detection and Fault Tolerant Control for Distributed Systems.”,

Ph.D. Thesis, University of Bologna, 2003.

[Papa02] P. Papadimitratos, Z.J. Haas, and E.G. Sirer. Path set selection in mobile ad hoc

networks. In MobiHoc 2002, June 2002. [Park97] V.D. Park and M. Scott Corson. A highly adaptive distributed routing algorithm for

mobile wireless networks. In Proceedings of IEEE INFOCOM '97, Japan, April 1997. [Pott00] G.J. Pottie and W.J. Kaiser, “Wireless Integrated Network Sensors,” Comm. ACM, vol.

43, no. 5, pp. 551-558, May 2000.


117

[Pras91] L. Prasad, S.S. Iyengar, R.L. Kashyap, and R.N. Madan, “Functional Characterization of Fault Tolerant Interation in Distributed Sensor Networks,” IEEE Trans. Systems, Man, and Cybernetics, vol. 21, no. 5, Sept./Oct. 1991.

[Pras94] L. Prasad, S.S. Iyengar, R.L. Rao, and R.L. Kashyap, “Fault- Tolerant Sensor

Integration Using Multiresolution Decomposition,” Physical Rev. E, vol. 49, no. 4, Apr. 1994.

[Ratt04] Linda Rattfalt, «A comparative study of two structural methods for fault isolability

analysis», Master's thesis, Lille University of Science and Technology, 25th February. 2004.

[Savv01] A. Savvides, C. C. Han and M. Srivastava, «Dynamic fine-grained localization in ad-

hoc networks of sensors», MobiCom 2001, Rome, Italy, 166–179, 2001 [Schm06] Stefan Schmid, Roger Wattenhofer, «Algorithmic models for sensor networks.»,

Computer Engineering and Networks Laboratory, Zurich, Switzerland, Fevrier 2006. [Shah01] S.H. Shah, K. Chen, and K. Nahrstedt. Cross-layer design for data accessibility in

mobile ad hoc networks. In Proceedings of 5th World multiconference on systemics, cybernetics and informatics (SCI 2001), Orlando, Florida, July 2001.

[Sime05] Emmanuel Simeu, « Test et surveillance intégrés des systèmes embarqués.»,

Mémoire , Diplôme d’habilitation à diriger des recherches, Université Joseph Fourier de Grenoble , septembre 2005.

[Sohr00] K. Sohrabi, J. Gao, V. Ailawadhi, and G.J. Pottie, “Protocols for Self-Organization of a

Wireless Sensor Network,” IEEE Personal Comm., vol. 7, no. 5, pp. 16-27, Oct. 2000. [Tarj72] R. Tarjan. Depth First Search and linear graph algorithms. SIAM Journal of

Computing, 1:146_160, 1972. [Wang02] K. H. Wang and B. Li. Group mobility and partition prediction in wireless ad-hoc

networks. In Proceedings of IEEE International Conference on Communications (ICC 2002), volume 2, pages 1017-1021, New York, April 2002.

[Zhao03] Jerry Zhao and Ramesh Govindan, Deborah Estrin, « Computing Aggregates for

Monitoring Wireless Sensor Networks. », Department of Computer Science, University of Southern California, Los Angeles,USA, 2003.

[Zhou04] Zongheng Zhou, Samir Das, Himanshu Gupta, " Connected K-Coverage Problem in

Sensor Networks", Proc. of the 13th Int. Conf. on Computer Communication and Networks (IC3N), Chicago, IL, Oct 2004.

[Ziel06] Wies law Zielonka , «Algorithmique », LIAFA, Université Denis Diderot, Septembre

2006.


118

4.10 Publications [01] K. Benahmed, H. Haffaf, B. Kechar, « Approche de la théorie des graphes pour la

surveillance des réseaux de capteurs sans fil», 8ième Séminaire international sur la physique énergétique, Centre universitaire Béchar, Novembre 2006. www.univ-bechar.dz/sipe8/Documents/Benahmed.pdf

[02] K. Benahmed, « La sécurité dans les réseaux de capteurs sans fil », Third Spring School of

Data-processing'2006 - Computer Security: Trends and Applications, INI (Institut National d’Informatique) , Alger, juin 17- 19 2006. www.ini.dz/conference/ecole_printemps2006/Pdf/13_JC_ART_BENAHMED.pdf


119

Conclusion générale

La surveillance des processus complexe comme c’est le cas dans les réseaux de capteurs sans fil où les contraintes sont nombreuses (densité des nœuds, les problèmes de connectivité et de couverture, l’énergie, les milieux hostile de déploiement, etc. ), nécessite l’utilisation d’un système de supervision fiable et robuste dont la conception et l’implémentation demandent des connaissances théorique considérables. La théorie des graphes a été largement utilisée dans ce domaine surtout dans les réseaux classique et les réseaux Ad hoc, comme méthode basée modèles.

Dans ce travail, nous avons débuté par une étude approfondie des RCSF, dans le but de mettre

en évidence les services critiques du réseau, qui nécessitent une surveillance continue. Ensuite, nous avons abordé la surveillance pour localiser l’axe sur le quel se portera notre travail. Il s’agissait de trouver des mécanismes qui assurent la tolérance aux fautes dans un RCSF. Après avoir montré l’intérêt de la théorie des graphes pour la modélisation des réseaux de capteurs, nous avons adopté les graphes RNG pour la modélisation de la connectivité et les graphes bipartis pour la couverture.

Notre contribution c’est matérialisé sous la forme de stratégies pour le contrôle de la topologie

d’un RCSF. Nous avons proposé une stratégie pour prédire les déconnexions par la détection des points d’articulations dans un graphe de connectivité. Ces points représentent les maillons faibles du réseau et donc une reconfiguration du réseau par déplacement des nœuds ou modification de la porté de communication renforce les connexions. Pour la couverture on a proposé l’utilisation des graphes bipartis pour représenter les relations entre les cibles et les capteurs qui les couvrent. A cet effet des algorithmes on été proposés pour la recherche de la robustesse des liens de couverture et d’une couverture minimale par le calcul d’un couplage maximal. On a proposé aussi, que les nœuds capteurs qui n’appartiennent pas au couplage seront basculés dans le mode veille (sleep mode), pour une économie de l’énergie.

Finalement, nous avons concrétisé nos propositions théorique, par l’élaboration d’un

simulateur qui permet : le déploiement des nœuds capteurs de manière aléatoire ou organisée, le déploiement des cibles à couvrir par le réseau et enfin l’exploitation des algorithmes proposés pour la surveillance.

Comme perspectives, nous proposons une approche nouvelle pour transporter les méthodes classiques de l'automatique à l'échelle des grands systèmes distribués. Cela consiste à abandonner toute idée de supervision centralisée, pour la remplacer par une algorithmique distribuée de supervision. Cette approche permet d’assurer un équilibrage des charges entre les nœuds et de renforcer les mécanismes de tolérance aux fautes. Une modélisation orienté objets des composants et des flux d’informations (exemple UML) sera aussi plus adaptée à de tel système. Le choix des nœuds capteurs à mettre en veille par le couplage maximal, doit être soumis à des contraintes tel que la valeur résiduelle de l’énergie. Enfin ce travail peut être couplé à un réseau réel pour valider les résultats de la simulation avec l’expérimentale.

Conclusion générale

120

Annexes

Annexes

121

Annexe A Simulation et résultats

Le but est d’établir un système permettant de simuler la surveillance d’un réseau de capteurs sans fil, afin d’en permettre l’évaluation des algorithmes proposés. Description de la phase des testes : Le superviseur, lance l’application (Wireless.exe). Il voit alors apparaître l’interface suivante :

De l’option, Fonction : Paramètres, il peut introduire les paramètres du réseau. Par la suite les nœuds capteurs seront déployés, voir le screenshot suivant :

Annexe A - Résultats de simulation

122

Une simple clique sur un nœud, permet de donner toutes ces informations. Un « drag and drop », permet de changer la position initiale d’un nœud. On peut voir aussi les liaisons de connectivités entre les différents nœuds capteurs (c’est le graphe GDU). Ce qui montre la complexité de ce type de graphe.

Le résultat suivant, nous montre la réduction d’un graphe GDU, par la technique RNG. Ainsi

que la détection des points d’articulations du réseau.

L’interface suivante, montre le déploiement des cibles (des feux dans notre cas), ainsi qu’une

couverture maximale des différentes cibles. Une cible peut être couverte par plus d’un nœud.


123

Le screenshot suivant, affiche le graphe biparti, qui montre la couverture maximale des différentes cibles.

L’histogramme suivant, nous montre des résultats statistique sur l’état de couverture des cibles avant le lancement de la couverture minimale.


124

Un calcul d’une couverture minimale, par l’algorithme de couplage maximal, nous donne le graphe biparti suivant :


125

L’interface suivante, nous montre l’état du réseau, après calcul d’une couverture minimale.

Le graphe suivant, illustre l’énergie résiduelle (restante) du réseau à chaque intervalle de temps.

Ce graphe, est obtenu en temps réel après activation d’une simulation continue (grâce à un timer). Ce qui montre que la dissipation de l’énergie augmente au début du déploiement de manière accélérée. Mais une fois l’algorithme de couverture minimale lancer, on constate que la pente du graphe tend vers une forme horizontale. Ce qui prouve que certains nœuds sont en mode veille.


126

Annexe B

Notions de base sur la théorie des graphes

Cette annexe a pour objectif de fournir quelques éléments sur la théorie des graphes. En effet, les solutions présentées utilisent à différents niveaux des propriétés et des algorithmes classiques de ce domaine. On présente dans un premier temps les graphes non orientés et les graphes planaires. Cette famille est particulièrement utilisée pour la gestion des différentes spécifications géométriques d’un RCSF. Ensuite, les graphes bipartis seront expliqués. Ils sont utilisés pour la modélisation de la couverture dans un réseau de capteur. B.1 Introduction

Le langage des graphes permet de représenter simplement la structure d’un grand nombre de situations : – L’exemple le plus classique est la représentation d’un réseau de communication : réseau de routes représenté dans une carte routière, réseau de chemins de fer, de téléphone, de relais de télévision, réseaux électriques, etc. ... – La famille d’exemples la plus générale est la représentation d’une relation binaire, qu’elle soit algébrique, mécanique, chimique, sociologique ..., comme les règles de certains jeux, l’ordonnancement des opérations de montage ou de démontage d’un ensemble technologique ...

Ce langage est utilisé à plusieurs reprises dans ce manuscrit (sur tout dans le chapitre quatre, lors de l’élaboration des solutions pour la tolérance aux fautes dans un RCSF). Le but de ce chapitre est de présenter brièvement les définitions nécessaires, les principales notions et les différents algorithmes utilisés. B.2 Définitions et concepts de base [Gond95, Maqu03, Sigw02] Définition 1 : graphe non orienté Soit E un ensemble fini.

Si E= { {x, y} | x∈V et y∈V } alors G = ( V, E) est un graphe non orienté. V : ensemble de sommets E : ensemble d’arêtes Exemple :

Figure B.1 – Graphes non orientés

Annexe B - Notions de base sur la théorie des graphes

127

Définition 2 : Le degré d'un sommet v, noté d(v) est le nombre de voisins de v. Un noeud de degré nul est dit isoler. Les degrés minimum, maximum et moyen sont désignés par

( ) { }VvvdG ∈= )(minδ , { }VvvdG ∈=∆ )(max)( et ∑∈

=Vv

vdv

Gd )(1

)(

Définition 3 : Chemin Un chemin est un graphe P = (V;E) avec { }kxxxV ,...,, 10= et { }kk xxxxxxE 1,2110 ....,,, −= où tous

les sommets xi sont distincts. x0 et xk sont les extrémités du chemin et x1….xk les noeuds internes. On dit que deux chemins sont indépendants si aucun des deux ne contient de noeuds internes de l'autre. Définition 4 : Graphe connexe, Un graphe non-vide G est dit connexe si et seulement si entre 2 sommets quelconques de G il existe un chemin. Si U⊆ V (G) et que G[U] est connexe on dira aussi que U est connexe. Définition 5 : Une composante connexe, est un sous-graphe maximal de G. Notons qu'une composante connexe étant non-vide, le graphe vide ne posséde pas de composantes connexes. Définition 6 : Une arborescence, est un graphe orienté possédant un sommet privilégié, la racine, tel qu’il existe un et un seul chemin depuis la racine à tout autre sommet. Définition 7 : Forêt, un graphe non orienté qui est un ensemble fini d’arbres (ou d’arborescences s’il est orienté) disjoints est appelé une forêt. Durant le parcours en profondeur d’un graphe non orienté, on distingue deux types d’arc :

- Les arcs yx → tels que parcours(x) appelle parcours(y) sont nommés arcs couvrants. - Les arcs dont l’extrémité terminale est un ascendant de l’extrémité initiale dans la forêt,

sont appelés arcs en arrière. Définition 8 : Point d'articulation, soit G=(X, A) un graphe non-orienté. Un sommet x est un point d'articulation si la suppression de x déconnecte deux sommets de G. Définition 9 : Dans un graphe non orienté biconnexe G, une paire d'articulation est une paire de sommets dont le retrait déconnecte G. Un graphe connexe qui ne contient pas de paires d'articulation est dit triconnexe : dans un tel graphe, il existe au moins trois chemins distincts entre deux sommets distincts quelconques [Schr04].

Définition 10 : Graphe k-connexe, G est dit k-connexe ssi kG > et G - X est connexe pour

tout X⊆ V avec kX < . En d'autres mots, G est k-connexe si 2 sommets quelconques ne sont

pas séparés par moins de k autres sommets. Par convention, le graphe vide est 0-connexe et par définition un graphe 1-connexe est un graphe non-trivial connexe.

Un graphe non orienté est k-connexe s'il reste connexe après suppression d'un ensemble quelconque de k-1 arêtes et s'il existe un ensemble de k arêtes qui déconnecte le graphe.


128

Autrement dit, un graphe est k-connexe si et seulement s’il existe au moins k chaînes indépendantes (arcs-disjointes) entre chaque couple de sommets. Le plus grand entier k(G) pour lequel G est k-connexe est appelé degré de connexité.

Théorème 1 : Théorème de Menger

Soit G connexe, égal à H ∪ K l’union de deux graphes, telle que H et K ont un seul sommet s en commun. Un tel sommet est dit séparateur. Soient x et y deux sommets distincts de s, l’un dans H, l’autre dans K. Tout chemin allant de x à y doit passer par s. Il n’existe donc pas de cycle élémentaire passant par x et y. (Un 8 n’est pas un cycle élémentaire). Il n’existe pas de paire de chemins disjoints reliant x à y [Cour04].

La réciproque est vraie : si dans un graphe connexe, deux sommets x et y ne peuvent être

reliés par deux chemins disjoints, alors, c’est qu’il existe un sommet séparateur, un goulot d’étranglement en quelque sorte. Preuve : Considérons un chemin c de x à y dans G. Soit H0 le sous-graphe défini comme réunion des chemins dans G issus de x et qui ne rencontrent pas c (sauf en x). Soit K0 la réunion des chemins issus de y et qui ne rencontrent pas c (sauf en y). Soit x0 le sommet sur c le plus éloigné de x lié à un sommet de H0. Soit y0 le sommet de c le plus loin de y lié à un sommet de K0. On a sur le chemin c : x ≤ x0 ≤ y0 ≤ y (car si y0 < x0, on aurait deux chemins disjoints.) N’importe quel sommet entre x0 et y0 (inclus) est un séparateur de G qui sépare x et y.

Ce résultat se généralise aux ensembles de k chemins disjoints. Un ensemble de sommets U est un k-séparateur d’un graphe connexe et sépare x de y si U a au plus k sommets et si x et y sont dans deux composantes connexes du sous graphe obtenu en retirant U et tous les arcs incidents.

Le théorème de Menger (1926) dit que si dans un graphe connexe x et y sont deux sommets

non adjacents et s’il n’existe pas k chemins disjoints entre x et y, alors il existe un (k − 1)-séparateur séparant x et y.

D’un point de vue logique ce théorème énonce un changement de quantification : la négation

d’une propriété existentielle : « il n’existe pas d’ensemble de k chemins disjoints tels que ... » est montrée équivalente à une propriété de la forme existentielle : « il existe un k-séparateur . . . ». Définition 11 : Graphe biparti

Soit G = (X, E) un graphe. Si ∃ une partition de X en X1 et en X2 ( X1 ∩X2 = Ø et X1∪X2 = X ) telle que ∀ x, y∈Xii ( i = 1, 2 ) ( x et y ne sont pas incidents / adjacents dans Xi - {x, y} ∉ E ) alors G est un graphe bipartite.

Figure B.2 – Graphes biparti


129

Définition 12 : Un graphe est planaire s’il admet une représentation dans laquelle aucune de ses arêtes n’en croise une autre. Définition 13: Couplages dans les graphes [Gond95]:

Deux arêtes sont indépendantes si elles n’ont pas d’extrémité en commun. Un ensemble M d’arêtes indépendantes de G est appelé couplage. Les sommets incidents à une arête de G sont les sommets couplés ou couverts par M. Si U est un ensemble des sommets couplés par M, on dit que M sature U. Les sommets de V (G)\ U sont dits exposés.

Soit G un graphe et M un couplage. Un chemin M-alternant dans G est un chemin dont les

arêtes sont alternativement dans E\M et de M. Un chemin M-alternant dont le début et la fin sont des sommets exposés est dit M-augmentant. On peut utiliser un chemin M-augmentant P pour transformer M en un couplage plus grand (voir Figure A.4) : en effet, si P est un chemin M-alternant alors la différence symétrique entre M et E(P) : M′ = M∆E(P) = (M \(E(P) ∩M) ∪(E(P) \M) est aussi un couplage. Sa taille |M′| vaut |M|+1 si les deux extrémités de P sont exposées, |M| si une seule des extrémités est exposée et |M| − 1 si les deux extrémités sont couvertes.

Figure B.3 – Augmentation d’un couplage à partir d’un chemin augmentant (les arêtes en gras sont celles du couplage).

Théorème 2 : (Berge 1957) Soit M �un couplage dans un graphe G. M est maximum si et seulement si il n’existe pas de chemin M-augmentant. Théorème 3 : (König 1931, Egerváry 1931) Soit G = ((A, B), E) un graphe biparti. La cardinalité maximum d'un couplage est égale à la cardinalité minimum d'une couverture.


130

B.3 Bibliographie [Cour04] Bruno Courcelle, « Introduction à la théorie des graphes : Définitions, applications et

techniques de preuves », Université Bordeaux 1, LaBRI (CNRS UMR 5800), 20 Avril, 2004.

[Gond95] M. Gondran et M. Minoux. ,« Graphes et Alorithmes. »,1995. 3 ième édition revue et

augmentée. [Laco03] Philipe Lacomme Christian Prins, Marc Servaux, « Algorithmes de graphes. », Edition

Eyrolles, 2ième Edition, 2003. [Maqu03] Didier Maquin, « Eléments de Théorie des Graphes », Institut national polytechnique

de Lorraine, 2003. [Schr04] P. Schreck, P. Mathis, A. Fabre ,« Constructions géométriques, dessin industriel et

informatique », CNRS-Université Louis Pasteur, Strasbourg, 10 novembre 2004. [Sigw02] Eric Sigward, « Introduction à la théorie des graphes », Mars 2002.
