Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

/Y2// ‘5’/ - 7c2 Université dc Montréal Localisation des noeuds dans les réseau

/Y2// ‘5’/ - 7c2 Université dc Montréal Localisation des noeuds dans les réseaux de capteurs sans fil par Boushaba Mustapha Département d’informatique et de recherche opérationnelle faculté des arts et des sciences Mémoire présenté à la Faculté des études supérieures en vue de l’obtention du grade de Maîtrise ès sciences (M.Sc.) en Informatique Avril, 2007 © Boushaba Mustapha, 2007 7o j (t! n Universit de Montréal Direction des bibJothèques AVIS L’auteur a autorisé l’Université de Montréal à reproduite et diffuser, en totalité ou en partie, par quelque moyen que ce soit et sur quelque support que ce soit, et exclusivement à des fins non lucratives d’enseignement et de recherche, des copies de ce mémoire ou de cette thèse. L’auteur et les coauteurs le cas échéant conservent la propriété du droit d’auteur et des droits moraux qui protègent ce document. Ni la thèse ou le mémoire, ni des extraits substantiels de ce document, ne doivent être imprimés ou autrement reproduits sans l’autorisation de l’auteur. Afin de se conformer à la Loi canadienne sur la protection des renseignements personnels, quelques formulaires secondaires, coordonnées ou signatures intégrées au texte ont pu être enlevés de ce document. Bien que cela ait pu affecter la pagination, il n’y a aucun contenu manquant. NOTICE The author of this thesis or dissertation has granted a nonexclusive license allowing Université de Montréal to reproduce and publish the document, in part or in whole, and in any format, solely for noncommercial educational and research purposes. The author and co-authors if applicable retain copyright ownership and moral rights in this document. Neither the whote thesis or dissertation, nor substantial extracts from it, may be printed or otherwise reproduced without the author’s permission. In compliance with the Canadian Privacy Act some supporting forms, contact information or signatures may have been removed from the document. While this may affect the document page count, it does flot represent any loss of content from the document. Université de Montréal Faculté des études supérieures Ce mémoire intitulé Localisation des noeuds dans les réseaux de capteurs sans fil présenté par: Boushaba Mustapha a été évalué par un jury composé des personnes suivantes: Houari Sahraoui, président Abdelhakim Hafid, directeur de recherche Abdenahim Bensiimane, codirecteur de recherche Mostapha Aboulharnid, membre du jury M6moire accepté le 15 juillet 2007 in Résumé La miniaturisation des composants électroniques a récemment permis de fabriquer des systèmes de petite taille dotés d’un microprocesseur, d’une mémoire, d’une capacité de communication et de senseurs. Ces systèmes sont appelés noeuds de capteurs. Lors de leur déploiement dans un environnement, ils interagissent d’une façon autonome et sans fil formant ainsi un réseau de capteurs capable d’acheminer des informations depuis une source vers une station de base. Les réseaux de capteurs sont utilisés dans de nombreuses applications comme la détection des mines, le contrôle de l’environnement ou encore la gestion du trafic routier, etc. Toutes ces applications nécessitent de connaître la position des noeuds pour traiter l’évènement. Bien entendu, la solution évidente visant à équiper tous les noeuds d’un module GPS est extrêmement coûteuse et est soumise à de nombreuses contraintes (plus d’énergie consommée, les GPS ne fonctionnent pas à l’intérieur des bâtiments). De plus, le calcul de la position des noeuds est le plus souvent influencé par les erreurs de mesures. Ces erreurs dépendent de la nature des milieux environnementaux où les capteurs sont déployés. Par ailleurs, des erreurs dans les distances et les angles estimés entre chaque paire de noeuds peuvent engendrer des erreurs de positionnement. Ces dernières peuvent être propagées à travers le réseau et ainsi devenir cumulatives. Vu l’importance pratique de ces problèmes, plusieurs techniques ont été proposées dans la littérature pour y remédier. Certaines d’entre elles utilisent une fraction des noeuds comme ancres (équipées de GPS) afin de permettre à d’autres noeuds de déterminer leurs positions. Ces approches présentent cependant certains inconvénients. En effet, quelques approches localisent moins de noeuds dans les réseaux, d’autres nécessitent une forte densité d’ancres ou un grand degré de connectivité et certaines localisent plus de noeuds mais avec une grande marge d’erreurs entre les positions estimées et les positions réelles. iv Nos travaux de recherche tentent à pallier aux déficiences énumérées ci-dessus. Ils reposent d’une part sur l’utilisation des distances, des angles d’arrivée et des ancres pour estimer la position des noeuds et d’autre part sur un mécanisme de contrôle d’erreur permettant de localiser avec plus de précision les noeuds et de réduire la propagation et l’accumulation des erreurs à travers le réseau. Mots-clés Angles d’arrivée, Erreurs de mesures, Localisation, Réseaux de capteurs, Trilatération, Triangulation, GPS V Abstract The electronic miniaturization of components enables the manufacturing of tiny systems equipped with microprocessor, memory, capacity of communication and sensors. These systems known as sensors nodes, self interact to form a network without requiring an established infrastructure. In these networks, nodes are capable of sensing their environments and sending collected information to one or more base stations through wireless links. Sensors networks are used by many applications, including environmental areas, traffic control, and military operations such as detection of mines. Most of sensor-based applications require the knowledge of the positions of sensors for processing the collected information. Equipping all the nodes with a GPS is extremely expensive in terms of dollars and power consumption; moreover GPS is flot appropriate inside buildings. The estimation of a node’s position most ofien includes enors due to the measurements of distance and incoming angles between neighbors. These errors vary with the nature of the environment where the sensors are deployed. These positioning errors can be propagated through the network and thus become cumulative. $everal localization techniques have been proposed in the open literature. Techniques of interest use a fraction of the nodes as landmarks (equipped with GPS) to help others nodes to be localized. More ofien, these techniques require high number of landmarks and/or big node degree; they also fail to locate a high percentage of non positioned nodes with good accuracy (Le., computed position Vs. real position). In this project, wc propose new techniques to locate nodes in sensors networks; our techniques requires a smaller number of landmarks, locates more non-positioned nodes with better accuracy than existing approaches. Keywords Angle ofArrival, Errors Measurement, Localization, Sensor Networks, Trilateration, Triangulation, GPS vi Table des matières Résumé iii Abstract y Table des matières vi Liste des tableaux ix Liste des figures x Liste des sigles et des abréviations xii Accord des coauteurs xiii Dédicace xiv Remerciements xv Chapitre 1 1 Introduction 1 1.1 Les réseaux de capteurs 1 1.2 Motivation 3 1.3 Description des problèmes de la localisation 5 1.4 Contributions 6 1.5 Organisation du mémoire 7 Chapitre 2 9 Revue de littérature 9 2.1 Techniques de mesure des distances 9 2.1.1 Heure d’arrivée TOA 10 2.1.2 Différence de Temps d’arrivée 10 2.1.3 Angle d’arrivée AoA 12 2.1.4 Force du signal RSST 12 2.2 Les erreurs de mesures 13 2.3 Techniques d’estimation des coordonnées 15 2.3.1 La triangulation 16 2.3.2 La trilatération 17 vii 2.3.3 La multilatération. 1$ 2.4 Techniques de déploiement des noeuds 19 2.5 Les algorithmes existants de localisation des noeuds 22 2.5.1 Approches distribuées 24 2.5.1.1 APS (Ad-Hoc Positioning System) 24 2.5.1.2 AHLoS (Ad-Hoc Localization System) 2$ 2.5.1.3 APIT (Approximate Point In Triangulation) 31 2.5.2 Approches centralisées 33 2.6 Conclusion 34 Chapitre 3 36 Localisation des noeuds de capteurs dans un milieu exempt d’erreurs 36 Mise en contexte 36 A2L: Angle to Landmarks Based Method Positioning for Wireless Sensor Networks... 37 Abstract 37 I. INTRODUCTION 37 II. Related work 39 III. Angle to Landmark Algorithrn 41 A. Message exchanges by A2L nodes 44 B. A2L algorithm 45 IV. Experimental resuits 4$ V. Conclusion 56 References 57 Chapitre 4 59 Localisation des noeuds de capteurs dans un milieu avec erreurs 59 Mise en contexte 59 HA-A2L: Angle to Landmark-based High Accuracy localization method in Sensor Networks 60 Abstract 60 viii I. INTRODUCTION .60 II. Related work. 63 III. HA-A2L 65 A. Network Model 65 B. Enor Model 66 C. HA-A2L Localization Algorithm 67 IV. SIMULATION 74 V. CONCLUSION 80 References 80 Chapitre 5 82 Conclusion et perspectives 82 5.1. Conclusion 82 5.2. Perspectives 83 ix Liste des tableaux Tableau 1. Énergie consommé par un noeud de capteur Mica II 2 Tableau 2. Aperçu des propriétés d’un ensemble représentatif des méthodes distribuées 35 X Liste des figures Chapitrel fig. 1 Composants d’un noeud de Capteur Mica II 1 Chapitre 2 fig. 1 Illustration du Principe TDOA 11 fig.2 Noeud Medusa 12 Fig.3 Loi normale 14 fig.4 Propriétés d’une distribution normale 15 Fig.5 Principe de la localisation à l’aide des ancres 16 fig.6 Illustration du principe de la triangulation 17 fig.7 Illustration du principe de la trilatération 18 fig.$ Illustration du principe de la multilatération 19 fig.9 Exemples de disposition des ancres 20 Fig.10 Techniques de placement des ancres 22 fig. 11 DV-hop 25 fig.12 DV-euclidean 27 Fig.13 Principe d’une multilatération atomique et itérative 29 Fig.14 Cas ambigu pour une multilatération atomique ou itérative 30 Fig. 15 Estimation de la position d’un noeud par APIT 31 uploads/Litterature/ boushaba-mustapha-2007-memoire.pdf