- ALGORITHME D’INITIALISATION ECONOME EN ENERGIE DANS LES. - 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,..,n].. - Nous supposons aussi que les nœuds n’ont aucune connaissance a priori de la topologie du réseau.. - 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.. - 4.2 Regroupement des nœuds. - 3.6 Affecter l’identité temporaire et Colorer les nœuds. - 11 4.1 Initialisation globale. - – 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].. - 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. - D’une façon générale, le problème d’initialisation affecte à chacun des n nœuds (ano- nymes. - 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é.. - 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].. - Ravelomanana a donné un algorithme quasi-optimal d’initialisation dans les réseaux radio multi-sauts. - 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. - Enfin, les résultats pour le problème d’initialisation dans les réseaux radio seront exposés dans la section “Etat de l’art”, section 2.2.. - – Réseaux radio avec détection de collision : les nœuds sont capables de distinguer le message significatif du bruit.. - – Réseaux radio sans détection de collision : les nœuds ne sont pas capables à distin- guer le message du bruit.. - C’est pourquoi, dans ce modèle, la communication entre les nœuds est plus difficile que le modèle DC. - Normalement, en réalité, les nœuds sont minuscules, elles n’ont pas de matériels spécifiques de détection de collisions.. - En d’autres termes, dans ces réseaux, il y a un canal uniquement pour touts les nœuds [9]. - Chaque nœud peut communiquer directement avec tous les autres nœuds.. - Par ailleurs, une com- munication entre deux nœuds peuvent s’appuyer sur les nœuds intermédiaires[9]. - – le nombre de nœuds n est connu exactement : Tous les nœuds dans les réseaux connaissent n exactement.. - – le nombre de nœuds n est connu partiellement : les nœuds connaissent l’ordre de grandeur de la taille du réseau considéré. - Le problème d’initialisation est fondamental dans la conception de protocoles pour les réseaux et dans les systèmes multiprocesseurs [6]. - Dans [11], les auteurs ont présenté un protocole d’initialisation pour le modèle à saut unique avec la détection de collision. - Durant ce protocole, les n nœuds sont identifiés en O(n) unité de temps, avec une probabilité supérieure à 1 − 1. - Dans [13], les protocoles randomisés d’initialisation sont abordés par Olariu et Nakano pour les réseaux radio à saut unique sans détection collision. - Dans les réseaux radio multi-sauts, Ravelomanana [17] a présenté les deux premiers algorithmes aléatoirisés d’initialisation qui fonctionnent en temps sous-linéaire : d’une com- plexité de O √. - Son algorithme résout le problème d’initialisation et de Gossiping (communication tous-à-tous) dans le modèle le plus difficile, à savoir quand il n’y a pas de détection de collision. - Pour éviter la collision, l’auteur affecte tous les nœuds situés à une distance deux les uns des autres (2 − sauts) des couleurs (des codes) 2 à 2 différentes. - De plus, nous avons ex- pliqué pourquoi la connaissance de la taille de réseaux affecte la complexité du problème d’initialisation.. - Tous les nœuds vont exécuter le même programme( le même algorithme).. - De plus, dans plusieurs applications, les nœuds des réseaux peuvent se déplacer, et donc la topologie des réseaux n’est pas stable. - Pour cette raison, nous supposons que les nœuds ne connaissent aucune information sur la topologique des réseaux, exceptée la mesure |X | de la surface X.. - – Taille du réseau : Supposant que la taille de réseaux est connue partiellement, n = O(X) par tous les nœuds.. - Divisant tous les nœuds en groupes (clusters) et initialiser localement. - Enfin, la phase finale est l’initialisation globale.. - Dans cette section, nous présentons les phases principales pour construire notre algo- rithme d’initialisation économe en énergie.. - Après, nous allons regrouper tous les nœuds en groupe dans la phase regroupement. - Ensuite, à chaque nœud est affecté une identité lo- cale dans son cluster, quand l’étape d’initialisation locale est finie. - En utilisant les chemins de communication entre des clusters dans la phase construction des chemins, tous les nœuds possèdent identités globales dans la phase finale.. - Comme tous les nœuds du réseau radio sont indifférents, notre première tâche est d’affec- ter une identité temporaire (T MP ID) à chacun d’eux. - Grâce au protocole T IME , tous les nœuds connaissent le temps global courant.. - Les nœuds rouges peuvent envoyer des signaux quand le temps est rouge.. - 3.6 – Affecter l’identité temporaire et Colorer les nœuds. - Ce processus de division est un pas essentiel de notre algorithme d’initialisation. - Le protocole local d’initialisation est exécuté de manière distributif par tous les nœuds dans tous les clusters. - Chaque nœud du réseau transmet son T MP ID à tous les autres de son cluster. - En utilisant le protocole coloration A SSIGN C OLOR , nous refusons la collision de transmission entre les nœuds. - Au final, tous les nœuds connaissent les T MP IDs de toutes les autres stations de leur. - A la fin de l’étape d’initialisation locale, chaque nœud a deux identités : son identité tem- poraire (T MP ID) et son identité locale (L OCAL ID), dépendant de son cluster.. - L’idée est la suivante : lors d’une communication, tous les nœuds sont endormis pour économiser leurs batteries, sauf les nœuds situés sur le chemin. - L’étape d’initialisation globale est exécutée comme l’étape d’initialisation locale en utili- sant l’algorithme G OSSIP entre tous les clusters. - En plus, nous avons parlé de notre idée générale pour notre algorithme d’initialisation.. - Enfin, par les chemins de communication, la phase d’initialisation globale est terminée.. - 3.12 – Initialisation locale et initialisation globale. - Dans ce chapitre, nous avons concentrer les algorithmes et leurs démonstration pour résoudre le problème d’initialisation pour le réseau de capteur. - Avant, nous avons supposé que tous les nœuds étaient indifférents. - 2: pour tous les noeuds faire. - Tous les nœuds choisissent par hasard, uniformément, indépendamment une identité dans le rang [1...n 5. - Dans le temps "rouge", tous les nœuds "rouges". - Alors, tous les nœuds dans k − sauts connaissent les informations des autres.G OSSIP (k) est présenté dans l’algorithme 3.. - Comme la présentation dans la section 3.2, avant d’initialiser localement, il faut regrouper (clustering) tous les nœuds en clusters. - Dans cette étape, tous les nœuds doivent regrouper en des clusters par leur chef. - – Alors, les nœuds reçoivent les T MP ID s des chefs.. - – Et les nœuds choisissent leur chef qui est le plus proche.. - Ici, c’est l’algorithme de regroupement des nœuds (C LUSTERING ) Algorithme 6 C LUSTERING. - log (n) 9 , tous les nœuds deviennent des candidats aux chefs des groupes. - Nous avons. - Maintenant, tous les nœuds sont groupés en clusters. - – Les nœuds sont groupés en clusters par le protocole C LUSTERING. - – Ensuite, dans chaque cluster, tous les nœuds échangent leur T MP ID avec les autres nœuds dans leur cluster.. - Par des chemins, tous les clusters peuvent échanger des informations d’autres. - En utilisant ces informations, tous les clusters vont initialiser globalement.. - Quand deux groupes communiquent pour échanger leurs informations (G ROUP ID,Nombre de nœuds), nous pouvons économiser l’énergie en laissant tous les nœuds dormir sauf ceux sur un chemin prédéterminé comme à la figure 4.13.. - Nous avons E(ξ i. - C’est pourquoi, la formule 4.7 est montrée.. - Comme la phase d’initialisation locale, tous les clusters utilisent le protocole G OSSIP sur le graphe des clusters par plusieurs chemins de communication pour initialiser globalement.. - En utilisant ce protocole G OSSIP tous les clusters échangent (G ROUP ID, nombre de nœuds).. - Ensuite, tous les clusters connaissent les informations (G ROUP ID, nombre de nœuds) des autres.. - Alors, grâce au rang de G ROUP ID, chaque cluster va affecter l’identité globale à tous les nœuds comme à la figure 4.15.. - 2: Pour tous les nœuds,. - 6: Pour tous les clusters,. - log n , l’initialisation globale est O(k × √. - En plus, nous avons dans la phase G OSSIP pour les clusters, tous les nœuds ne doivent pas être éveillés tout le temps. - Dans ce chapitre, nous avons présenté nos algorithmes économes en énergie pour faire l’initialisation globale pour le réseau de capteurs multi-sauts (mutli-hops) sans détection de collision (sans-DC). - – La phase préparation : à tous les nœuds sont affectées des identités temporaires. - Seulement les nœuds sur des che- mins doivent éveiller pour transmettre des informations. - Dans ce chapitre, nous allons comparer le résultat de notre algorithme d’initialisation avec le résultat précédent. - – Temps d’exécution : O (k. - log n.Diamtre)=O. - Temps d’exécution O( √. - Mais, l’algorithme n’est pas économe en énergie. - Parce que, dans l’exécution de l’algorithme, tous les nœuds doivent être éveillés tout le temps comme. - Pourtant, dans tous les deux cas, la formule. - T emps 0 execution × T emps d 0 veil = O(n log n) (5.1) est toujours vraie pour tous les deux algorithmes.