INSTITUT DE LA FRANCOPHONIE POUR L’INFORMATIQUE MEMOIRE DE FIN D’ETUDES ALGORITHME D’INITIALISATION ECONOME EN ENERGIE DANS LES RESEAUX RADIO MULTISAUTS Encadrant Etudiant Vlady RAVELOMANANA Binh Thanh DOAN Hanoi, 16 mars 2006 Ce stage de DEA a été effectué au sein de l’équipe Optimisation Combinatoire et Algorithmique Distribuée (OCAD) du Laboratoire d’Informatique de Paris-Nord (LIPN) LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Remerciements Je voudrais tout d’abord remercier le Directeur Christophe FOUQUERE et le Professeur Christian LAVAULT pour m’avoir accueilli dans l’équipe Optimisation Combinatoire et Algorith- mique Distribuée (OCAD) du Laboratoire d’Informatique de Paris- Nord (LIPN). Je tiens à remercier tout particulièrement M. Vlady RAVELOMANANA pour avoir proposé ce sujet de stage et m’avoir encadré pendant ces six mois. Les connaissances et le savoir- faire qu’il m’a apportés sont et resteront précieux pour moi.
Je le remercie de son contact cha- leureux, ses conseils et encouragements, son soutien permanent et la liberté de recherche qu’il a bien voulu me laisser. Qu’il trouve ici l’expression de ma profonde reconnaissance. Mes plus sincères remerciements vont à tous les professeurs, personnels, thésards et stagiaires du LIPN pour une ambiance de travail particulièrement favorable. Un grand merci aux professeurs, mes amis de l’Institut de la Francophonie pour l’Informa- tique (IFI) pour m’avoir donné des cours de très bonne qualité et pour leur soutien tout au long de mes études à l’IFI.
Merci enfin à mes parents, ma sœur, mon frère et mes amis pour leur encouragement de tous les instants. ii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Résumé Un réseau de capteurs (ou senseurs) est un système réparti qui se compose d’un grand nombre de minuscules senseurs avec des émetteurs-récepteurs de faible puissance sans unité centrale de traitement. Un des problèmes les plus importants dans ces réseaux consiste à réduire au minimum la consommation d’énergie, de sorte à maximiser la durée de la vie du réseau. Dans le pro- blème d’initialisation (également appelé problème d’identification),chacun des n nœuds (pro- cesseurs) originellement anonymes du réseau est affecté une identité unique dans [1,.
Nous considérons ce réseau de n nœuds qui sont distribués aléatoirement uniformément sur une surface X. On suppose que ce réseau est synchrone et que le temps est discrétisé et est divisé en unités. Deux nœuds peuvent communiquer quand ils sont à une distance de tout au plus r de l’un à l’autre (r est le paramètre de la transmission réception). De plus, si deux voisins ou plus d’un processeur u sont en cours de transmission au même temps, u ne peut pas recevoir leurs messages : (problème de collision).
Nous supposons aussi que les nœuds n’ont aucune connaissance a priori de la topologie du réseau. Pour résoudre le problème d’initialisation, nous proposons un algorithme randomisé éco- 3/4 1/4 nome en énergie qui s’exécute en au plus O n log (n) unité de temps, tout en as- surant qu’aucune station ne s’éveille plus que O n1/4 log (n)3/4 unités de temps. Cet algo- rithme randomisé résout le problème d’initialisation avec une probabilité tendant vers 1 quand le nombre de stations n est grand. Mots-clefs : réseau sans fil multisauts ; auto-configuration dans le réseau ad-hoc ; proto- coles distribués randomisés ; initialisation ; algorithme économe en énergie iii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Abstract A sensor networks is a distributed system consisting of a large number of tiny sensors with low-power transceivers and no central controller.
One of the most important problems in such networks is to minimize the energy consump- tion, and maximize the network lifetime. In the initialization problem (also known as naming) each of the n indistinguishable nodes (processors) in a given network is assigned a unique identifier, ranging from 1 to n. We consider a network where n nodes (processors) are randomly deployed in a square X. The network is assumed to be synchronous and the time to be slotted.
Two nodes can com- municate if they are at a distance of at most r from each other (r is the transmitting/receiving range). Moreover, if two or more neighbors of a processor u are transmitting concurrently at the same time slot, u cannot receive either of their messages (collision problem). We suppose also that the nodes have no a priori knowledge about the topology of the network. To solve the initialization problem, we propose an energy-efficient randomized algorithm running in at most O n 3/4 log (n)1/4 time slots, with no station being awake for more than O n1/4 log (n)3/4 time slots.
Our randomized algorithm resolves the initialization problem with probability tending to 1 as the number of stations n gets large. Keywords : Multihop networks ; self-configuration in ad hoc networks ; randomized distri- buted protocols ; initialization ; naming ; energy efficient algorithms. iv LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Table des matières Remerciements ii Résumé iii Abstract iv Acronymes x 1 Introduction 1 1.1 Réseau de capteurs : .4 Plan du document .4 Mode de communication .5 Taille du réseau .2 Etat de l’art .2 Regroupement des stations. 19 v LUAN VAN CHAT LUONG download : add luanvanchat@agmail.4 Chemins de communication entre les clusters .1 Affecter l’identité temporaire .2 Affecter la couleur .2 Regroupement des nœuds .4 Chaîne de communication entre des clusters.
45 A Probabilité 47 Bibliographie 47 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Table des figures 1.1 Un service militaire utilisant les réseaux de capteurs .3 Initialisation pour 24 nœuds .1 La collision dans la communication.2 Le modèle single-saut .3 Le modèle multi-sauts .1 Les senseurs endormis et éveillés .2 Distribuer aléatoirement uniformément des capteurs sur une surface .3 Rayon de transmission .4 Diamètre du graphe .5 Couler des nœuds .6 Affecter l’identité temporaire et Colorer les nœuds .7 Regroupement des clusters .9 Construction des chemins .11 Affecter des T MP ID et regrouper en des clusters .12 Initialisation locale et initialisation globale .1 Affecter des temporaire identités aux nœuds .2 Colorer des nœuds .5 Schéma pour choisir un chef de chaque groupe .6 Choisir des chefs entre des candidats .7 Chosir le chef qui est le plus proche .8 Regrouper des nœuds .9 Couvrir totalement l’espace .11 Chemins de communication entre des clusters .12 Chemin de communication entre deux clusters .14 Plusieurs chemins entre deux clusters. 40 vii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Liste des tableaux 2.1 Détection de collision .2 Initialisation dans les réseaux radio à saut unique sans détection de collision .1 Comparaison entre deux résultats .2 Comparaison entre deux résultats avec k = 1q.3 Comparaison entre deux résultats avec k = 4 logn n. 45 viii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Liste des algorithmes 1 T MP ID. 41 ix LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Acronymes DC Détection de Collision sans-DC sans Détection de Collision GPS Global Position System CH Cluster Head TempID Temporary IDentity LocalID Local IDentity GroupID Group IDentity GlobalID Global IDentity x LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chapitre 1 Introduction 1.1 Contexte Apparus il y a quelques années, les réseaux sans fil connaissent un énorme succès.
Ils sont en plein développement du fait de la flexibilité de service. Leur développement ouvre une nouvelle ère dans le domaine des télécommunications [1]. Les réseaux sans fil sont utiles quand aucune connexion filaire n’est disponible. Par exemple, lors d’interventions sur le site d’une catastrophe naturelle telle qu’un incendie de forêt, lors d’une opération militaire ou encore d’une opération de sauvetage de personnes et plus généralement lors de la nécessité d’une construction rapide d’un réseau.
Un autre exemple, pour effectuer une mesure automatique d’humidité, de température ou pour prevenir une incendie de forêt, nous pouvons éparpiller des capteurs sur cette forêt. Ce système sans fil va rassembler ces données de température, d’humidité ou détecter le début d’une incendie. C’est pourquoi, les réseaux de capteurs qui datent de plusieurs dizaines d’années consti- tuent la plus grande catégorie de réseaux.1 Réseau de capteurs : Un réseau de capteurs est un déploiement d’un grand nombre de petits, pas chers, équi- pements autonomes (appelés encore senseurs) dans lesquels, chaque senseur peut sentir, calculer, envoyer/recevoir des données pour rassembler des informations dans le but de sa- tisfaire une tâche concrète. 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.1 – Un service militaire utilisant les réseaux de capteurs F IG .2 – Senseur LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 Caractéristiques : – Mobilité : la topologie du réseau peut changer rapidement, de façon aléatoire et non prédictive [2].
– Liaisons sans fil : tous les nœuds communiquent par ondes radio[2]. – Equivalence des nœuds du réseau : toutes les nœuds sont équivalents, sans aucune centralisation[2]. – Autonomie des nœuds : la consommation d’énergie constitue un problème majeur puisque ces derniers fonctionnent sur des batteries autonomes. Il est important que les protocoles mis en place dans les réseaux ad hoc prennent en compte cette spécificité[2].3 Applications : Aujourd’hui, il y a énormément d’applications utilisant les réseaux de capteurs : – Contrôle de l’environnement : pour le mesure des températures, des pressions, d’hu- midités dans un endroit.
– Militaire : pour les services de sécurité, la détection de dangers chimiques, etc. – Applications industrielles : pour gérer la circulation, la direction d’un objet, la lumière, etc .2 Problème Typiquement, les nœuds des réseaux de capteurs sont de petite taille, économique, peu chères et contiennent un processeur, une interface radio et une batterie. A cause du fait qu’il n’y a aucune centralisation, ces réseaux rencontrent les problèmes principaux tels que ceux issus des systèmes distribués classiques à savoir les algorithmes d’élection, d’initialisation, le routage, etc. Pour le problème d’initialisation, dans les communications des réseaux statiques (par exemple les réseaux filaires), l’identification (l’adresse) des processeurs est stockée dans une certaine mémoire locale ou est reçue au moment du démarrage.
Cependant, dans un ré- seau dynamique construit à partit de plus petits composants, ou quand une partie de réseau LUAN VAN CHAT LUONG download : add luanvanchat@agmail.3 Motivation & objectifs 4 F IG .3 – Initialisation pour 24 nœuds existant est assignée comme les réseaux ad-hoc pour résoudre une tâche dans un environ- nement de traitement multitâche, les processeurs ne peuvent pas donner automatiquement leurs identifications [14, 6]. D’une façon générale, le problème d’initialisation affecte à chacun des n nœuds (ano- nymes) – donc impossible à différencier entre eux – une identité unique, et une valeur de 1 à n. Par ailleurs, ces nœuds fonctionnent grâce à l’énergie fournie par leur batterie. C’est pour- quoi, un des problèmes parmi les plus importants dans les réseaux consiste à réduire la consommation d’énergie, de sorte à maximiser la durée de vie du réseau.
Ainsi, un des problèmes sur ce type de réseaux est celui de l’initialisation tout en mini- misant l’énergie consommée. En d’autres termes, il faut éviter une consommation excessive d’énergie lors du processus d’initialisation car les nœuds sont autonomes et ont chacun un potentiel énergétique limité.3 Motivation & objectifs D’abord, ce problème fondamental d’initialisation a été abordé dans le domaine des sys- tèmes parallèles et répartis [6, 14]. Plus tard, l’initialisation dans le cas des réseaux radio a été discutée dans [4, 11, 12, 13, 17]. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.4 Plan du document 5 Dans [17], V.
Ravelomanana a donné un algorithme quasi-optimal d’initialisation dans les réseaux radio multi-sauts. Cependant, il ne s’agit pas d’un protocole économe en énergie. Pourtant, nous allons nous inspirer de quelques idées importantes présentes dans l’algo- rithme d’initialisation quasi-optimimale décrit dans [17] pour construire notre protocole. Ainsi, en se concentrant plus particulièrement sur le problème d’initialisation dans les ré- seaux de capteurs multi-sauts, nous proposons un nouvel algorithme d’initialisation économe en énergie.
Nous ferons une analyse du problème et nous démontrerons nos résultats dans le chapitre 4.