Soutenance mémoire
Couverture avec un déploiement aléatoire
Les RCSF ont été envisagés initialement comme une technologie qui permettrait de réaliser des applications de capture dans des régions dont l’infrastructure est limitée ou quasiment absente, telles que les zones dangereuses, hostiles ou difficilement accessibles, utilisant des capteurs à faible coût. Dans la majorité des applications des RCSF, les capteurs sont déployés de manière aléatoire, du moment que c’est plus simple et relativement moins cher pour les RCSF denses [76]. Cependant, le déploiement des RCVSF est différent par rapport aux RCSF car le modèle de capture directionnel des RCVSF impose de nouveaux challenges qui nécessitent de nouvelles recherches dans la maintenance de la couverture et la préservation de l’énergie.
Afin de compenser le manque du positionnement exact dans le déploiement aléatoire et d’assurer une tolérance aux pannes, les noeuds sont typiquement déployés de manière très dense, avec plus de capteurs qu’il en faut contrairement au placement optimal. Le réseau résultant sera composé de plusieurs noeuds redondants, qui peuvent être utiles aussi bien pour économiser l’énergie que pour maintenir la couverture et la connectivité. La densité du déploiement permet de réduire également le champ de communication et par conséquent diminuer la consommation d’énergie [77].
Les auteurs dans [78] affirment que le fait d’utiliser un grand nombre de capteurs vidéo à faible résolution est plus judicieux pour les applications environnementales avec occlusion par rapport à l’utilisation d’un nombre limité de capteurs à haute résolution. Ce qui nous permet de prolonger la durée de vie ainsi que la couverture du réseau déployé [76].
Le déploiement d’un RCVSF est un problème crucial qui a un impact direct sur la couverture et la connectivité du réseau. En considérant une zone de surveillance difficilement accessible pour les humains, les capteurs sont dispersés à partir d’un avion, ce qui donne lieu à un grand nombre de capteurs non contrôlés déployé tout au long de la région cible. Une approche intéressante est d’améliorer la configuration initiale des noeuds déployés, en utilisant d’autres stratégies telles que le redéploiement et les noeuds mobiles [79]. Des difficultés additionnelles concernant la mobilité des noeuds et l’accès à la zone de surveillance doivent être considérées lorsque des stratégies de déploiement et de post-déploiement sont planifiées [60].
II.7.2.1 Localisation des noeuds capteurs après déploiement
Après un déploiement aléatoire, les capteurs peuvent être placés n’importe où dans la zone de surveillance et leur localisation et densité peuvent être connues préalablement. Donc, il est attendu à ce que les capteurs découvrent leur position courante puisque c’est nécessaire pour plusieurs applications telles que la surveillance et le suivi et également pour les algorithmes d’optimisation de la couverture, maintenance de la connectivité et préservation d’énergie. Une solution de localisation doit être appliquée puisque la connectivité des noeuds et leur couverture doivent être correctement calculées avec les coordonnées spatiales des noeuds. La plupart des applications sur les RCVSF se concentrent sur la connaissance des positions des capteurs ainsi que les directions courantes des caméras. La localisation des noeuds déployés aléatoirement est aussi définie comme un problème d’extraction de la topologie après déploiement.
Quelques algorithmes de localisation pour les RCSF traditionnels peuvent être trouvés dans [80]. Comme les RCVSF fonctionnent en suivant un modèle de capture directionnel, la direction courante de chaque capteur est aussi inconnue, ce qui nécessite des algorithmes spécifiques pour la localisation des noeuds. Par exemple, le GPS (Global Positioning System) ne peut pas être utilisé pour la découverte de la couverture dans les RCVSF à cause du manque d’information concernant l’orientation des caméras, en plus du coût et la perte d’énergie.
Les algorithmes de localisation peuvent être exécutés de manière centralisée ou distribuée. Les algorithmes centralisés sont exécutés dans le Sink ou dans un serveur central, économisant l’énergie en évitant un calcul additionnel au niveau des noeuds. De plus, comme le Sink est considéré comme un dispositif sans contrainte en ressources, des algorithmes complexes peuvent facilement y être exécutés. L’inconvénient est la faible scalabilité des algorithmes centralisés. Pour les algorithmes distribués, la découverte de la localisation est exécutée par chaque noeud, de manière indépendante, utilisant des informations sur le voisinage. Les algorithmes distribués supportent mieux la scalabilité mais demande un calcul au niveau du noeud capteur sans fil.
Pour la localisation des noeuds dans les RCVSF, la plupart des solutions considèrent les zones de chevauchement du CdV des capteurs, utilisant des algorithmes inspirés du domaine de la vision assistée par ordinateur pour estimer la position des noeuds. Nous abordons dans ce qui suit quelques solutions qui ont été proposées dans la littérature :
Dans [81], des images capturées à partir de différents noeuds sont traitées dans un serveur central, qui calcule la superposition des CdV. L’algorithme centralisé proposé calcule des paramètres tels que la translation des coordonnées, l’angle de rotation et le facteur d’échelle. Ces paramètres sont ensuite diffusés à travers tout le réseau utilisant un protocole approprié. La dernière étape de localisation des noeuds est basée sur l’estimation de ces paramètres entre chaque paire de noeuds voisins.
Les auteurs dans [82] ont présenté quatre méthodes de localisation distribuées pour les réseaux de capteurs visuels. Dans la première méthode, l’observation des noeuds voisins est utilisée pour la localisation des noeuds en identifiant le chevauchement contenu dans les images extraites. Les trois autres méthodes sont basées sur l’observation simultanée d’une cible mobile qui peut avoir un mouvement arbitraire, une vitesse constante et connaît ses propres coordonnées.
Dans [83], une cible mobile est aussi utilisée pour découvrir la position des caméras. Ce travail définit le problème de la localisation et le suivi simultané (Simultaneous Localization and Tracking (SLAT)), où les directions des caméras sont estimées tout au long de la trajectoire de la cible mobile, utilisant un algorithme distribué « online ».
La localisation des capteurs directionnels a également été étudiée dans [84]. La méthode proposée identifie automatiquement les zones de chevauchement des CdV des caméras pour estimer la localisation et la direction des noeuds et permet en cas de changement de topologie une mise à jour « online » des informations sur la topologie du réseau. Elle peut aussi traiter des types hétérogènes de capteurs vidéo. La redondance des différentes prises de vues des caméras est exploitée pour assurer de meilleures performances par rapport aux algorithmes similaires.
Les auteurs dans [85] ont présenté un algorithme distribué pour la localisation et l’auto-calibration d’un RCVSF déployé aléatoirement. Le réseau de capteur est modélisé en utilisant deux graphes non-orientés. Le premier concerne le graphe de communication, représentant la communication sans fil ad hoc entre les noeuds. Le second graphe représente la relation en termes de vision entre les caméras, où deux noeuds sont associés si et seulement s’ils voient la même scène ou objet (même sous différents points de vue). Le voisinage dans le graphe de vision est utilisé pour la calibration. Le travail présenté dans [86] a poursuivi cette recherche, en traitant plus de détails et proposant des résultats d’expérimentations.
Dans [87], des informations sur le CdV des caméras sont utilisées pour la localisation des noeuds en trois dimensions, traitée avec différentes méthodes pour obtenir la position des noeuds. Ils ont également abordé brièvement une solution pour la localisation distribuée d’un très grand nombre de capteurs vidéo, puisque dans la majorité des travaux, les expérimentations sur la localisation des noeuds considèrent uniquement peu de noeuds déployés.
Algorithmes de couverture
Plusieurs travaux ont traité le problème d’optimisation du placement des caméras et plus récemment des capteurs en considérant un déploiement déterministe. Lorsque les capteurs sont déployés aléatoirement, la couverture peut également être optimisée, en se basant sur les positions, les orientations et le nombre de capteurs. Les algorithmes pour le placement optimal des caméras/capteurs suivant un déploiement déterministe sont des principes de base pour l’optimisation de la couverture dans un RCVSF déployé aléatoirement mais avec quelques adaptations.
Lorsque des capteurs vidéo qui ne peuvent pas changer leurs orientations courantes sont déployés aléatoirement dans une zone de surveillance, la région de couverture sera définie par les positions et orientations courantes des capteurs juste après le déploiement. Dans ce cas, un algorithme peut calculer uniquement les noeuds redondants afin de tenter de prolonger la durée de vie du réseau, du moment que la région de couverture ne peut pas être changée (mais épuisée au fil du temps).
Si les orientations courantes des capteurs sont reconfigurables, des algorithmes peuvent calculer des orientations optimisées pour une couverture maximisée d’une zone avec le minimum de noeuds actifs. Dans ce qui suit, nous présentons différents algorithmes et méthodes pour l’amélioration de la couverture après un déploiement aléatoire des capteurs.
Ai et Abouzeid [76] ont proposé deux algorithmes centralisés et un algorithme distribué pour calculer les orientations initiales des capteurs directionnels afin de couvrir le maximum de cibles en activant le minimum de capteurs. Les orientations calculées sont utilisées pour changer les directions des capteurs vidéo actifs, en gardant les capteurs inactifs pour remplacer les noeuds défaillants, ou qui ont épuisé leur énergie dans le but de prolonger la durée de vie du réseau. Ceci a été défini par les auteurs comme le problème de couverture maximale avec le minimum de capteurs (Maximum Coverage with Minimum Sensors (MCMS)). Ce problème peut être résolu avec deux algorithmes centralisés (ILP et greedy) et l’algorithme distribué « greedy ». Les algorithmes proposés ont été validés par expérimentations. Ils ont pu déduire que l’approche centralisée « ILP » a fourni de meilleurs résultats (couverture plus large avec moins de capteurs actifs) par rapport aux algorithmes « greedy » centralisés et distribués. Cependant, les algorithmes « ILP » exigent plus de ressources d’énergie et de calcul par rapport aux algorithmes « greedy ». Enfin les solutions centralisées n’assurent pas de scalabilité ce qui rend l’algorithme distribué « greedy » le plus approprié pour les RCVSF.
Cai et al. [88] ont aussi étudié le déploiement aléatoire des capteurs avec des orientations configurables, mais se concentrent sur l’activation des noeuds pour la surveillance de cibles. La solution proposée tente de couvrir toutes les cibles en définissant les orientations de chaque capteur et en désactivant les noeuds redondants. Cette approche est définie comme le problème des ensembles de couverture directionnels multiple (Multiple Directional Cover Sets (MDCS). Les directions des capteurs sont organisées en sous ensembles non-disjoints (ensembles couvrants), permettant à un capteur de faire partie de plusieurs ensembles. Afin de calculer les ensembles couvrants, plusieurs algorithmes centralisés et distribués ont été proposés, basés sur la programmation linéaire et les heuristiques. L’un d’entre eux, l’algorithme « Feedback », a pour objectif de générer le minimum d’ensembles couvrants pour que le temps de transition entre les différents ensembles couvrants soit moins important. Ceci, afin de réduire le lapse de temps pendant lequel les cibles ne sont pas couvertes.
Des caméras avec mobilité angulaire ont été étudiées dans [89]. Les réseaux de capteurs visuels avec des noeuds capteurs équipés de caméras avec une mobilité angulaire peuvent assurer dynamiquement la couverture d’une région en évitant les espaces déjà couverts et le risque de chevauchement. Les auteurs ont proposé l’algorithme « Face-Away » qui est une solution « greedy » pour atteindre un taux de couverture maximal dans la région d’intérêt.
Les auteurs dans [5] ont traité le problème d’ordonnancement adaptatif de l’activité des noeuds capteurs avec une seule direction. Leur objectif est de prolonger la durée de vie du réseau tout en prenant en compte la criticité des applications de surveillance. Un algorithme distribué a été proposé pour maintenir la couverture et la connectivité de la zone de surveillance en utilisant les ensembles couvrants.
Sung et Yang [90] ont proposé un algorithme distribué d’auto-redéploiement pour améliorer le taux de couverture global dans le champ de capture d’un réseau de capteurs directionnels qui est composé de capteurs mobiles et rotationnels. Les auteurs ont utilisé le diagramme de Voronoï pour déterminer les positions ainsi que les directions de capture des capteurs. L’algorithme proposé est appelé DVSA (Distributed Voronoi-Based Self-Redeployment Algorithm).
Dans [91], les auteurs se sont concentrés sur les réseaux de capteurs d’images pour proposer une méthode basée sur la reconnaissance d’images floues et un champ potentiel virtuel en considérant la direction et le mouvement des capteurs pour l’amélioration de la couverture.
Les auteurs dans [92] proposent une méthode distribuée pour changer l’orientation des noeuds sans fil afin de minimiser l’effet d’occlusion. Chaque noeud découvre indépendamment ses voisins et analyse les régions qui contiennent des obstacles ou des chevauchements. Selon les informations découvertes à partir du voisinage, les noeuds peuvent ajuster automatiquement les orientations des caméras pour changer leur CdV. Les auteurs dans [92] ont présenté un résultat intéressant sur les régions avec de fortes occlusions, il s’agit du fait d’utiliser plusieurs caméras à faible résolution serait une meilleure solution par rapport au choix de quelques caméras à forte résolution, ce qui a été certifié également dans [78].
Nous proposons dans le tableau II.1 une synthèse sur les principaux travaux de recherche sur la couverture dans les RCVSF selon les différentes approches abordées dans les sous-sections précédentes.
La plupart des approches existantes sont orientées optimisation comme les travaux présentés dans [60], [76], etc.
Certaines approches traitent bien la technique d’ordonnancement des capteurs, comme celles présentées dans [60], [76] et [5]. Afin de bénéficier des avantages offerts par cette technique, nous avons exploité l’algorithme d’ordonnancement adaptatif proposé dans [5]. Cependant, contrairement à la solution présentée dans [5], où les capteurs utilisés sont limités à une seule direction, dans notre proposition, les capteurs employés sont dotés de plusieurs directions avec la possibilité de transition d’une direction vers une autre pour étendre leur CdV.
Dans certains travaux [92], bien que la technique de rotation ait été prise en considération, les auteurs proposent toujours des solutions qui évitent le risque de chevauchement entre les CdV avec un parcours de tous le périmètre du capteur vidéo de 0° jusqu’à 360°. Cette approche nécessite un traitement complexe au niveau de chaque noeud capteur. Par conséquent, dans notre solution, nous avons limité le nombre de directions à trois au maximum afin de minimiser le temps de calcul.
La plupart des travaux existants qui utilisent la fonction de rotation, visent un seul objectif qui est l’optimisation de la couverture. Cependant, dans l’approche proposée dans cette thèse nous visons plusieurs objectifs. La technique de rotation est exploitée afin de maximiser la couverture, alors que la redondance et l’ordonnancement de l’activité des capteurs vidéo sont utilisés pour la tolérance aux pannes et économiser de l’énergie.
Concernant la prise en considération de l’existence d’obstacles dans l’élaboration d’un algorithme de couverture, peu de travaux ont été proposés dans la littérature. Les auteurs dans [92] ont traité le problème d’occlusion en minimisant le chevauchement des CdV des capteurs vidéo. Dans la solution proposée, nous prenons en compte la présence d’obstacles dans la zone de surveillance pour minimiser l’effet d’occlusion. Cependant, Contrairement à l’approche proposée dans [92], nous tirons profit du risque de chevauchement des CdV des capteurs vidéo pour obtenir des noeuds redondants. Ces derniers seront exploités dans l’étape d’ordonnancement de l’activité des capteurs vidéo.
Par rapport aux différents travaux de recherche présentés précédemment, le modèle de couverture proposé dans cette thèse appartient à la catégorie de la couverture de zone. Comme notre objectif principal est la couverture des endroits stratégiques et sensibles donc le déploiement adéquat des capteurs vidéo est un déploiement aléatoire. L’approche adoptée dans la solution proposée est complètement distribuée, ce qui favorise l’utilisation des réseaux de grandes tailles et nécessite moins de traitement par rapport à une approche centralisée.
Métriques de couverture
Plusieurs travaux se sont intéressés aux métriques de couverture aussi bien pour les RCSF traditionnels que pour les RCVSF plus récemment.
Dans [93], le taux de couverture et de connectivité d’un RCSF traditionnel a été mesuré, avec une classification en trois différents groupes : couverture complète avec connectivité, couverture partielle avec connectivité et couverture avec connectivité restreinte. L’auteur affirme que la couverture sans connectivité est insensée pour les RCSF, puisque les données collectées ne peuvent pas être récupérées à partir d’un noeud en « offline ». La même idée est valable pour les RCVSF.
Les auteurs dans [79] ont défini une métrique intéressante pour mesurer la qualité du déploiement en termes de couverture en considérant des capteurs vidéo. Dans ce travail, le champ du noeud (Node Area « NA ») est défini comme un cercle centré sur le noeud, et le champ de couverture du réseau (Network Coverage Area « NCA ») comme l’union de tous les NA. Le champ de capture de chaque noeud est seulement un secteur de ce cercle, représentant une intersection entre le CdV et le champ du noeud. La qualité de la couverture du déploiement résultante (Deployement Coverage Quality « DCQ ») est le ratio entre la somme de tous les champs de capture (Network Relevant Sensing Areas « NRSA ») et le NCA. Les résultats d’expérimentation présentés dans [79] montrent que le DCQ augmente lorsque le nombre de noeuds déployés est plus important. Une métrique similaire est aussi décrite dans [94] :
|
Table des matières
Remerciements
Résumé
Abstract
Table des matières
Liste des figures
Liste des tableaux
Liste des abréviations
Introduction générale
1. Problématique et motivation
2. Objectifs
3. Principales contributions de la thèse
4. Organisation de la thèse
Partie I : Etat de l’art
Chapitre I : Généralités sur les Réseaux de Capteurs Vidéo Sans Fil (RCVSF)
I.1 Introduction
I.2 Historique d’évolution des réseaux de capteurs sans fil
I.3 Types de réseaux de capteurs sans fil
I.3.1 RCSF terrestre
I.3.2 RCSF souterrain
I.3.3 RCSF aquatique
I.3.4 RCSF multimédia
I.3.5 RCSF mobile
I.4 RCVSF
I.4.1 Définition
I.4.2 Architecture
I.4.3 Systèmes d’exploitation
I.4.4 Dispositifs de capture vidéo
I.4.4.1 Caméras basées sur des composants commerciaux
I.4.4.2 Caméras conçues pour les réseaux de capteurs
I.5 Caractéristiques et contraintes d’un RCVSF
I.6 Classification des RCVSF selon le modèle de surveillance
I.7 Domaines d’application des RCVSF
I.8 Concept de redondance dans les RCVSF
I.8.1 Types de redondance
I.8.2 Rôle de la redondance dans les RCVSF
I.8.3 Redondance basée sur le chevauchement des CdV
I.8.4 Redondance basée sur la similitude de la capture
I.8.5 Redondance basée sur la pertinence de la capture
I.9 Conclusion
Chapitre II : Surveillance et problématique de la couverture
II.1 Introduction
II.2 Concept de surveillance
II.3 Historique sur les approches de surveillance
II.4 Réseaux de surveillance
II.4.1 Réseaux de surveillance à base de capteurs scalaires
II.4.2 Réseaux de surveillance à base de capteurs multimédias
II.4.3 Réseaux de surveillance à base de capteurs Hybrides
II.5 Principes de la couverture vidéo
II.6 Catégories de couverture
II.6.1 Couverture de cibles prédéterminées
II.6.2 Couverture de barrière
II.6.3 Couverture de zone
II.7 Couverture suivant la stratégie de déploiement
II.7.1 Couverture avec déploiement déterministe
II.7.1.1 Placement optimal des caméras
II.7.1.2 Placement optimal des capteurs
II.7.2 Couverture avec déploiement aléatoire
II.7.2.1 Localisation des noeuds capteurs après déploiement
II.7.2.2 Algorithmes de couverture
II.7.2.3 Métriques de couverture
II.8 Conclusion
Partie II : Contributions
Chapitre III : Proposition d’un modèle de couverture fiable pour la surveillance
III.1 Introduction
III.2 Modèle de représentation du CdV d’un capteur vidéo à une seule direction
III.3 Notions de géométrie pour le modèle de couverture
III.3.1 Coordonnées cartésiennes et polaires d’un point
III.3.2 Norme d’un vecteur
III.3.3 Produit scalaire
III.3.4 Aire d’un triangle
III.3.5 Test d’inclusion d’un point dans un triangle
III.3.6 Génération d’un point aléatoire à l’intérieur d’un triangle
III.4 Définition d’un ensemble couvrant
III.5 Stratégie de base de construction d’un ensemble couvrant
III.6 Pourcentage de couverture d’un ensemble couvrant
III.7 Modèle de couverture avec capteurs vidéo rotationnels
III.7.1 Mécanismes de rotation d’un capteur vidéo
III.7.2 Modèle de représentation des CdV d’un capteur vidéo rotationnel
III.7.3 Formules de calcul géométriques des différents CdV
III.7.4 Fonction de sélection d’un CdV
III.8 Nouvelles stratégies de construction d’ensembles couvrants
III.8.1 Couverture avec tolérance aux pannes
III.8.1.1 Fonction de construction d’ensembles couvrants avec tolérance aux pannes
III.8.1.2 Exemple de modèle de construction d’ensembles couvrants avec tolérance aux pannes
III.8.2 Couverture avec haute précision
III.9 Ordonnancement de l’activité dynamique des capteurs vidéo
III.9.1 Algorithme d’ordonnancement
III.9.2 Ajustement en fonction de la criticité de l’application
III.9.2.1 Vitesse de capture d’un noeud vidéo
III.9.2.2 Approche par ajustement statique
III.9.2.3 Approche par ajustement dynamique
III.10 Implémentation et évaluation des performances
III.10.1 Le simulateur OMNeT++
III.10.1.1 Définition
III.10.1.2 Construction d’un modèle de simulation OMNeT++
III.10.2 Présentation du modèle de simulation du RCVSF
III.10.3 Implémentation des algorithmes du nouveau modèle de couverture
III.10.3.1 Programme implémentant le calcul des coordonnées des
triangles représentant les CdV du capteur vidéo
III.10.3.2 Programme implémentant la fonction de sélection d’un CdV
III.10.3.3 Programmes implémentant les nouvelles stratégies de
construction d’ensembles couvrants
III.10.4 Evaluation des performances
III.10.4.1 Paramètres de simulation
III.10.4.2 Métriques de performances
III.10.4.3 Résultats de simulation et interprétation
III.11 Conclusion
Chapitre IV : Modèle de couverture fiable avec prise en considération d’obstacles
IV.1 Introduction
IV.2 Notion d’occlusion
IV.3 Autres formes géométriques d’un obstacle
IV.4 Modèle de couverture avec évitement d’obstacles
IV.5 Fonction de sélection d’un CdV avec évitement d’obstacles
IV.6 Fonction de construction d’ensembles couvrants avec évitement d’obstacles
IV.7 Applications visées pour l’exploitation du modèle de couverture proposé
IV.7.1 Applications pour l’économie d’énergie
IV.7.2 Applications pour la tolérance aux pannes
IV.8 Implémentation des algorithmes
IV.8.1 Programme implémentant la fonction de sélection d’un CdV avec
évitement d’obstacles
IV.8.2 Programme implémentant la fonction de construction d’ensembles
couvrants avec évitement d’obstacles
IV.9 Evaluation des performances
IV.9.1 Résultats de simulation des modèles RCVSFROb et RCVSF
IV.9.1.1 Pourcentage moyen de couverture avec variation de la densité du réseau
IV.9.1.2 Pourcentage moyen de couverture avec variation du champ de communication
IV.9.1.3 Nombre moyen d’ensembles couvrants
IV.9.1.4 Pourcentage moyen de noeuds actifs
IV.9.2 Résultats de simulation des modèles RCVSFROb et DVSA
IV.9.2.1 Pourcentage moyen de couverture avec variation de la densité du réseau
IV.9.2.2 Pourcentage moyen de couverture avec variation du champ de capture
IV.10 Conclusion
Conclusion générale
Perspectives
Bibliographie
Annexe A : Le simulateur OMNeT++ : Aperçu du logiciel
A.1 Introduction
A.2 Définition
A.3 Propriétés du simulateur OMNeT++
A.4 Etapes d’installation du simulateur OMNeT++
A.5 Architecture d’OMNeT++
A.6 Les principaux fichiers d’OMNeT++
A.6.1 Fichier .ned
A.6.2 Fichier .ini
A.6.3 Fichier .msg
A.7 Exécution d’une simulation sous OMNeT++
A.8 Les plateformes d’OMNeT++
A.8.1 Mobility Framework
A.8.2 Mixim
A.8.3 Castalia
A.9 Conclusion
Annexe B : Modèle de simulation d’un RCVSF sous OMNeT++
B.1 Introduction
B.2 Etapes d’installation du modèle de simulation
B.3 Présentation de quelques fichiers et répertoires du modèle
B.4 Exécution d’un scénario de simulation
B.5 Analyse des résultats
Télécharger le rapport complet
