Hag Gar

JDIR'09: 10èmes Journées Doctorales en Informatique et Réseaux

Clusterisation auto-stabilisante pour les réseaux ad-hoc Bachar Salim HAGGAR Université de Reims Champagne Ardenne - UFR Sciences Exactes et Naturelles Département de Mathématiques et Informatique - CReSTIC/SYSCOM E-mail : [email protected] Résumé—Un réseau ad-hoc sans fil est composé essentiellement d’hôtes mobiles qui communiquent les uns avec les autres sans infrastructure fixe et sans administration centrale. Les principaux problèmes liés à ces réseaux sont l’imprédictible mobilité des hôtes et un débit de communication modeste. Dans ce contexte, un des problèmes majeurs est le partionnement du réseau en groupe appelés clusters, donnant ainsi une organisation hiérarchique. Dans ce papier, nous présentons un algorithme déterministe de clusterisation auto-stabilisant pour les réseaux ad-hoc. L’algorithme garantit qu’à partir d’un état quelconque, le réseau sera entièrement organisé en cluster en au plus D+2 transitions où D est le diamètre du réseau. De plus, en cas de changement topologique du réseau, le système converge automatiquement vers une nouvelle organisation. Mots clés - réseaux ad-hoc, cluster, routage, auto-stabilisation

I. I NTRODUCTION Aujourd’hui, les réseaux sans fil sont de plus en plus populaires à cause de leur facilité de déploiement. Ces réseaux ont un rôle crucial à jouer au sein des réseaux informatiques. Elles offrent des solutions ouvertes pour fournir la mobilité ainsi que des services essentiels là où l’installation d’infrastructures n’est pas possible. Toutefois, les réseaux sans fil sont classés en deux catégories : les réseaux avec infrastructure et sans infrastructure [1]. Les réseaux avec infrastructure qui utilisent généralement le modèle de la communication cellulaire et les réseaux sans infrastructure, appelés également réseaux adhoc. Un réseau mobile ad hoc, consiste donc en un grand nombre d’unités mobiles se déplaçant dans un environnement quelconque en utilisant comme moyen de communication des liaisons sans fil. Les principaux problèmes liés à ces réseaux sont la limitation de bande passante, la limitation de la source d’énergie et le caractère ”pseudo aléatoire” de la mobilité des hôtes. Ils sont communément appelés MANET pour Mobile Ad Hoc Network. Ces réseaux ont la particularité de s’autocréer, s’auto-organiser et s’auto-administrer et ne reposent sur aucune infrastructure fixe [2]. Les éléments les composant communiquent par des liaisons sans fil, potentiellement mobiles, et peuvent être amenés à entrer ou sortir du réseau à tout moment. Ils sont caractérisés par la capacité de chaque participant d’agir à la fois comme client et comme routeur du réseau. Si un émetteur n’est pas à porté directe de la machine de destination, les informations devront être transmises de proche en proche, le long d’un chemin établi et maintenu par le réseau.

31

L’algorithme de routage consiste à assurer une stratégie qui garantit, à n’importe quel moment, la connexion entre n’importe quelle paire de nœuds appartenant au réseau. Cette stratégie doit prendre en considération les changements de la topologie du réseau, ainsi que d’autres caractéristiques comme la bande passante, le nombre de liens, la limitation d’énergie, etc. Avec l’émergence de ces dispositifs, de multiples recherches ont été faites dans les communications mobiles. Ces recherches se concentrent en particulier sur les façons de router les informations entre les nœuds. Compte tenu de la mobilité imprévisible des nœuds, la topologie d’un réseau adhoc est instable et est susceptible à de fréquents changements. Les schémas de routage des réseaux ad hoc peuvent être classés en deux catégories : les protocoles proactifs et réactifs [14]. Les protocoles de routage proactifs tentent de maintenir à jour dans chaque nœud les informations de routage concernant tous les autres nœds du réseau [3] . Chaque nœud maintient donc une table pour stocker les informations de routage. Du fait de l’aspect dynamique de la topologie des réseaux adhoc, la maintenance des tables de routage nécessite l’envoi périodique par chaque nœud d’un message de signalisation indiquant sa présence à tous ses voisins. Ces protocoles atteignent rapidement leurs limites avec l’accroissement du nombre de nœuds et de leur mobilité. Parmi ceux-ci nous avons par exemple : DSDV [4] et GSR [5]. Les protocoles réactifs ne gardent que les routes en cours d’utilisation pour le routage. A la demande, le protocole va chercher à travers le réseau une route pour atteindre une destination. Ces protocoles sont basés sur le principe de la création de route à la demande. Ainsi lorsqu’un nœud veut communiquer avec une station distante, il est obligé de déterminer une route dynamiquement. Cette technique permet de ne pas inonder le réseau par des paquets de contrôle et de ne pas conserver les routes non utilisées. Mais elle nécessite en contre partie un certain temps pour établir une route avant de pouvoir la transmettre. Parmi ceux-ci nous avons par exemple : DSR [6] et AODV [7]. Afin de combiner les avantages de ces deux approches, de nombreux chercheurs ont proposé la technique de clusterisation. La clusterisation consiste à partitionner le réseau en groupe d’entités appelé cluster en donnant au réseau une structure hiérarchique [8], [14]. L’objectif principal est d’introduire un premier niveau de hiérarchie. Un cluster est composé d’un

JDIR'09: 10èmes Journées Doctorales en Informatique et Réseaux

clusterhead, de nœuds de passage et éventuellement de nœuds appelés ordinaires. Dans ce papier, nous proposons un nouvel algorithme autostabilisant qui est basé sur l’identité de son voisinage pour construire les clusters. Cette construction se fait à l’aide des identités portées par chaque nœud, identité supposée unique. L’avantage de cet algorithme est l’ensemble des phases de découverte de topologie et de structuration du réseau qui ne nécessite qu’un unique message. Cette approche consiste donc à combiner les deux phases en une seule et à fabriquer des clusters disjoints, c’est à dire qu’un nœud n’appartient qu’à un seul cluster. II. É TAT DE L’ ART Dans la littérature, il existe de nombreuses propositions pour clusteriser les réseaux ad hoc. Toutes ces solutions sont destinées à identifier un sous ensemble des nœuds du réseau (appelé cluster). Les clusters sont identifiés par leur clusterhead. Si le clusterhead disparaît, le cluster n’est plus valide. Les différents algorithmes se distinguent sur le critère de sélection des clusterheads. Parmi ces algorithmes nous avons : Lowest-ID cluster Algorithm(LID) [12], Least Clusterhead Change Algorithm(LLC) [9], High-Connectivity Clustering(HCC) [10], [13]. Dans le Lowest-ID Cluster Algorithm(LID) [12], chaque hôte mobile dans le réseau doit avoir un identifiant unique ID. Le nœud qui a le plus petit ID parmi tous ses voisins est élu comme clusterhead. Le cluster est formé par le clusterhead et tous ses voisins. Une fois le cluster formé, tous les membres de ce cluster ne peuvent plus participer au processus d’élection. Chaque hôte compare son ID avec ceux de ses voisins. S’il a le plus petit ID parmi tous ses voisins, il concède le rôle de clusterhead et ses voisins deviennent des membres de ce cluster. Il a l’avantage d’être simple et rapide dans la construction des clusters mais il génère aussi un grand nombre de clusters et ne peuvent être réglable à l’évolution de la topologie. Le Least Clusterhead Change Algorithm (LLC) [9], est conçu pour minimiser le changement de clusterhead et apporte une meilleure stabilité dans la composition des clusterheads. Dans High-Connectivity Clustering(HCC) [10], [13], l’élection de clusterheads est basée sur le degré de connectivité(nombre de voisins du nœud) au lieu des identités des nœuds. Un nœud est élu comme clusterhead s’il a la plus haute connectivité parmi tous ses voisins. Cet algorithme souffre de fréquents changements de clusterheads. Dans [11], 2 algorithmes de clusterisation sont proposés, en apportant une nouvelle approche. Le premier, le Distributed Clustering Algorithm (DCA) qui est destiné aux réseaux “quasi-static”, dans lequel les déplacements des nœuds doivent être “lents”. Un poids est définit par la vitesse de déplacement de chaque nœud. Le critère de l’élection du clusterhead est le poids maximal dans son voisinage. Le nœud dont le poids est le plus grand parmi tous ses voisins est élu clusterhead. Le second algorithme est destiné aux réseaux de grande mobilité et appelé Mobility-Adaptive Clustering algorithm (DMAC).

32

Chaque nœud réagit localement à toutes les variations en fonction de son statut : clusterhead ou nœud membre. Dans les 2 algorithmes, il est attribué aux nœuds des poids différents et il est supposé que chaque nœud a la connaissance de son poids. Un nœud est choisi pour être clusterhead si son poids est plus grand que parmi tous ses voisins. III. C ONTRIBUTIONS Pour la totalité des algorithmes cités, qui construisent des clusters de diamètre au plus de 2, ces derniers sont recouvrants, c’est à dire qu’il existe des nœuds du graphe qui appartiennent à 2 clusters simultanément. L’algorithme déterministe que nous proposons construit également des clusters de diamètre au plus égal à 2 où chaque nœud n’appartient qu’à un seul cluster. Aucun cluster n’est donc récouvrant. De plus, 2 clusterhead ne sont jamais voisins et les messages échangés ne sont que de taille log(2n+3) avec n le nombre de nœud du graphe. Notre solution est auto-stabilisante et tolérante aux modifications topologiques. Depuis n’importe quel état initial, l’ensemble des clusters valides est créé en au plus D+2 transitions, avec D diamètre du graphe. IV. M ODÈLE Le système est modelisé par un graphe non orienté G = (V, E) où V est l’ensemble des nœuds du réseau et E modélise l’ensemble des connexions qui existent entre ces nœuds. Une arête (u, v) ∈ E si et seulement si u et v peuvent mutuellement recevoir les transmissions de u et v. Ce qui implique que tous les liens entre les nœuds sont bidirectionnels. Dans ce cas, on dit que u et v sont voisins. L’ensemble des voisins d’un nœud v ∈ V est noté N eigh. Chaque nœud u du réseau à un identifiant unique id et peut communiquer avec un sousensemble N eighu ⊆ V . On définit la distance entre deux nœuds u et v dans le graphe G comme le nombre d’arêtes minimal le long du chemin entre u et v. Dans un but de clarté, nous utiliserons dans la suite de ce papier les notations suivantes : – N eighu : désigne le voisinage du nœud u – Ci : désigne la configuration i – Cli : le cluster i. – id(u) : désigne l’identité du nœud u – d(u, v) : la distance entre le nœud u et v – Xu : la variable X du nœud u – M ax : le nœud dont l’identité est la plus grande de toutes les identités, c’est à dire id(M ax)= max{(id(u), u ∈ G)} – m.x : désigne la variable x contenue dans le message m – D : désigne le diamètre du graphe. Définition 4.1 (Cluster): On définit un cluster par un graphe connexe dont le diamètre est inférieur ou égal à 2. Définition 4.2 (Clusterisation): La clusterisation est le processus d’élection de clusterhead et affectation des nœuds dans un unique cluster. Chaque nœud possède un identifiant unique id et deux variables : cl-id et Statut. 1 ≤ id ≤ n, 1 ≤ cl-id ≤ n et Statut ∈ {CH, N M, N P }

JDIR'09: 10èmes Journées Doctorales en Informatique et Réseaux

– CH : clusterhead – N M : nœud membre – N P : nœud de passage Définition 4.3 (Clusterhead): Statut(u)= CH ssi u =max(v/v ∈ N eighu ∧ cl-idu = cl-idv ) Définition 4.4 (nœud membre): Statut(u)= N M ssi (∀ v ∈ N eighu , v ∈ N eigh-clu ∧ id(u)< id(v)) Définition 4.5 (nœud de passage): Statut(u)= N P ssi (∃ v ∈ N eighu , cl-idu 6= cl-idv ) V. P RINCIPE D ’ EXÉCUTION Le choix du clusterhead est basé sur les identifiants associés à chaque nœud : le nœud dont l’identité est plus grande parmi tous ses voisins devient clusterhead. Afin de mieux répondre aux exigences imposées par le réseau sans fil notamment la mobilité des nœuds, l’algorithme satisfait les 2 propriétés suivantes : (i) Chaque nœud du réseau doit appartenir à un unique cluster ; (ii) Tous les nœuds d’un même cluster sont à distance au plus de 1 de leur clusterhead. Nous supposons les hypothèses suivantes – Un message envoyé par un nœud est réçu correctement en un temps fini par tous ses voisins à distance 1. – Chaque cluster possède un unique clusterhead. L’algorithme partitionne le réseau en clusters et chaque cluster a un clusterhead qui effectue des tâches particulières. La construction des clusters se fait par échange périodique de message hello entre chaque nœud du réseau. Chaque message hello transmis par un nœud contient son id, son statut et son cl-id. Ce message sert également à chaque nœud pour annoncer sa présence. Pendant une certaine durée, chaque nœud enregistre les messages reçus. A l’expiration de cette durée, chaque nœud va comparer les identités des expéditeurs et le nœud dont l’identité est plus grande au sein d’un même cluster sera clusterhead. De plus chaque message de type hello contient le Statut de l’expéditeur. A la réception de ce message, tous les voisins deviennent alors des nœuds membres. Dans le cas où un nœud se trouve être entouré de plusieurs clusterheads, il devient un nœud de passage. A la fin du processus chaque nœud sera dans un des trois états suivants : clusterhead, nœud membre ou nœud de passage. Dans l’hypothèse où deux clusterheads deviennent voisins,

un message hello à ses voisins annonçant son nouveau statut. Dans le cas contraire, il conserve le rôle de clusterhead. Dans les réseaux ad hoc, la topologie du réseau change fréquemment due à la mobilité des nœuds. Nous devons donc gérer, 1) les nœuds qui se déplacent, 2) les nœuds qui disparaissent et les nœuds qui apparaissent. Notre algorithme permet également de gérer ces cas. – L’apparition d’un nouveau nœud. Quand un nouveau nœud arrive dans le réseau, il diffuse, à un intervalle de temps régulier un message de type hello. A l’expiration de son timeout, s’il n’a reçu aucun message de type hello de la part d’un clusterhead, le nœud devient clusterhead. Si le nœud a reçu un message hello de la part d’un clusterhead, le nœud devient alors un nœud membre. Dans le cas où il reçoit plus d’un clusterhead, le nœud devient un nœud de passage. – Disparition d’un nœud. De la même manière que pour l’apparition, par échange des messages hello les vosins se rendent compte de cette disparition – Le déplacement d’un nœud. Cas équivalent à l’apparition d’un nouveau nœud (voir figure 2 et 3). cluster 11

cluster 6 16 2

4

3

11 7 cluster 13

9

Clusterhead

6

Ordinary Node 13

5

Gateway 1

10

F IG . 2.

Déclaration d’un clusterhead

cluster 9

cluster 16 16 2

4

3 9

7 Clusterhead 6

11

Ordinary Node 13

cluster 13

Gateway

5 1 10

cluster 11

cluster 6 16 2

4

F IG . 3.

3

11 7 cluster 13

9

Clusterhead

6

Ordinary Node 13

5

Gateway 1

10

F IG . 1.

Déplacement d’un nœud

A. L’algorithme

Déclaration d’un clusterhead

le premier nœud qui détecte le conflit par l’intermédiaire des messages hello reçus compare son identité à celle du clusterhead voisin. Si son identité est plus petite, il abandonne son statut de clusterhead et devient nœud membre et envoie

33

Nous supposons dans la suite de ce papier les propriétés suivantes : Propriété 5.1 (Cluster disjoint): ∀ i, j avec i 6= j. T Cli Clj = ∅ Propriété 5.2: Soit Cl un cluster. ∀ u ∈ Cl, ∃! v tel que Statut(v) = CH. ∀ u ∈ Cl, Statut(u) = CH ⇒ ∀ v ∈ Cl, id(u) > id(v) La technique que nous proposons partitionne le graphe en clusters bien formés. C’est à dire que le cluster vérifie les deux propriétés suivantes :

JDIR'09: 10èmes Journées Doctorales en Informatique et Réseaux

Propriété 5.3: Les clusters construits forment une partition du graphe. Propriété 5.4: Chaque nœud est à distance au plus 1 d’un clusterhead.

condition 1 de la définition 5.1. Les conditions 2 et 3 sont respectivement illustrées par les nœuds 6 et 5. Nous pouvons également remarquer dans la figure 4 que les nœuds 4 et 8 sont cohérents. cluster 2

algorithme 1 Algorithme de clusterisation sur un nœud i cl-id : Identité du cluster du nœud i m.Statut : Statut du message m m.j : Identité du message m m.cl-id : Identité du cluster du message m Statut ∈ {CH, N M, N P } R1.a) if (Statut = CH) ∧ (cl-id 6= id) then cl-id ← id ; envoie Hello(id, Statut, cl-id) ; end if R1.b) if (Statut 6= CH) ∧ ( cl-id = id ∨(∀ m ∈ Hello, cl-id 6= m.j)∨(∃ m ∈ Hello, cl-id = m.j ∧ m.statut 6= CH)) then Statut ← CH ; cl-id ← id ; envoie Hello(id, Statut, cl-id) ; end if R2 : A la Réception d’un Hello(j, Statut, cl-id) R2.a) if (Statut 6= CH) ∧ (∀ m ∈ Hello, m.j < id) then Statut ← CH ; cl-id ← id ; envoie Hello(id, Statut, cl-id) ; end if R2.b) if (Statut 6= CH) ∧ (∃ m ∈ Hello, m.Statut = CH ∧ m.cl-id > cl-id) then Statut ← N P ; cl-id ← m.cl-id ; envoie Hello(id, Statut, cl-id) ; end if R2.c) if (Statut 6= CH) ∧ (∃ m ∈ Hello, m.Statut = CH ∧ m.cl-id < cl-id) then Statut ← N P ; envoie Hello(id, Statut, cl-id) ; end if R2.d) if (Statut 6= CH) ∧ (∃ m ∈ Hello, (m.Statut = N P ∨ m.Statut = N M ) ∧ m.cl-id 6= cl-id) then Statut ← N P ; envoie Hello(id, Statut, cl-id) ; end if R2.e) if (Statut 6= CH) ∧ (∃ m ∈ Hello, (m.Statut = CH ∧ m.cl-id= cl-id) then Statut ← N M ; envoie Hello(id, Statut, cl-id) ; end if R3) if (Statut = CH) ∧ (∃ m ∈ Hello, m.Statut = CH ∧ m.j > id) then Statut ← N M ; cl-id ← m.cl-id ; envoie Hello(id, Statut, cl-id) ; end if R4) envoie Hello(id, Statut, cl-id) ;

Dans un but de clarté, nous définissons les termes suivants : Définition 5.1 (Nœud incohérent): Un nœud u est dit incohérent si et seulement si une des conditions suivantes est verifiée (voir figure 4). 1) ∀ v ∈ N eighu , cl-id(u) 6= id(v) ∧ cl-id(u) 6= id(u). 2) cl-id(u) = id(u) ∧ Statut(u) 6= CH. 3) cl-id(u) 6= id(u) ∧ Statut(u) = CH . Dans la figure 4, le nœud 7 est clusterhead. Son id est 7 et son cl-id est 2, le nœud 7 est donc un nœud incohérent, tout comme le nœud 1 et 2 car ils vérifient tous les trois la

34

1 cluster 3 Clusterhead

5 7 3

Gateway

cluster 8

2 Ordinary node

4 8

6

F IG . 4.

cluster 6

Nœud incoherent

Définition 5.2 (Cluster incohérent): Un cluster Cl est dit incohérent si et seulement si une des conditions suivantes est verifiée. 1) ∃ u ∈ Cl tel que u est un nœud incoherent. 2) ∃ u ∈ Cl tel que Statut(u) = CH, ∃ v ∈ Cl, id(v) > id(u). 3) ∀ u ∈ Cl, cl-id(u) 6= Max(id(v)/ v ∈ Cl). 4) ∀ u ∈ Cl, Statut(u) 6= CH. Dans la figure 5, le nœud 1 est un clusterhead mais n’a pas la plus grande id dans son cluster, donc le cluster est incohérent. Le nœud 1 vérifie la condition 2 de la définition 5.2. Les conditions 3 et 4 sont illustrées respectivement par le cluster 2 et 6. cluster 1

1

cluster 2 Clusterhead

5 3

7

Gateway 2 Ordinary node 6 cluster 6 8

4

F IG . 5.

Cluster incohérent

Définition 5.3 (Configuration): Nous disons qu’au terme d’une configuration, un nœud a reçu au moins un message de tous ses voisins et a exécuté une unique règle. Définition 5.4 (Transition): Nous appelons transition le passage d’une configuration Ci à une configuration Ci+1 . Nous appelons transition i la transition qui permet de passer de la configuration Ci à Ci+1 . Définition 5.5 (Cluster-Max): Nous appelons Cluster-Max, le cluster ayant pour identité id(M ax). Lemme 5.1: A C1 le nœud Max est tel que : Statut(M ax) = CH et cl-id(M ax) = id(M ax) Preuve. A C0 : 1) Soit Statut(M ax)= CH – Si cl-id(M ax) 6= id donc la règle R1.a peut s’exécuter et à C1 , cl-id(M ax)= id(M ax). – Si cl-id(M ax)= id(M ax) alors seule la règle R4 ne peut être appliquée

JDIR'09: 10èmes Journées Doctorales en Informatique et Réseaux

2) Soit Statut(M ax) 6= CH – Si cl-id(M ax)= id(M ax) alors la règle R1.b peut s’exécuter et à C1 , Statut(M ax)= CH, clid(M ax)= id(M ax). – Si cl-id(M ax) 6= id(M ax) par définition de M ax, nous avons ∀ u ∈ G id(M ax) > id(u) donc seule la règle R2.a s’exécute et à C1 , Statut(M ax)= CH et cl-id(M ax)= id(M ax).  Corollaire 5.1: Le nœud M ax est cohérent à C1 . Corollaire 5.2: ∀i ≥ 1 à Ci le nœud Max n’exécutera que la règle R4 et Statut(M ax) = CH Remarque 5.1: A C1 nous pouvons remarquer que tout nœud qui devrait être CH à la fin de la convergence ne l’est pas encore. Lemme 5.2: A C1 tous les nœuds sont cohérents. Preuve. A C0 d’après la définition 5.1, nous avons : – Les nœuds du cas 1 n’appliquent que les règles R1.a ou R1.b. – Les nœuds du cas 2 n’appliquent que la règle R1.b. – Les nœuds du cas 3 n’appliquent que la règle R1.a. Dans tous les cas, nous obtenons à C1 , pour tous les nœuds incohérents à C0 , après exécution des règles pouvant être appliquées, Statut(u)= CH et cl-id(u)= id(u).  Lemme 5.3: Soit u ∈ N eigh(M ax). A C2 nous avons, clid(u)= id(M ax) et Statut(u) ∈ {N M, N P } Preuve. A la configuration C1 : u ∈ N eigh(M ax) 1) Soit Statut(u)= CH. D’après le lemme 5.2, nous savons que si Statut(u)= CH alors cl-id(u)= id(u). De plus par définition de M ax, nous avons id(u)< id(M ax) donc seule la règle R3 peut s’exécuter. Donc à C2 nous avons Statut(u)= N M et cl-id(u)= id(M ax). 2) Soit Statut(u)6= CH. Par définition de M ax, nous avons id(u)< id(M ax) et u va recevoir un message m de la part de M ax avec m.Statut= CH : – Si cl-id(u)< m.cl-id, d’après R2.b, à C2 Statut(u)= N P et cl-id(u)= id(M ax). – Si cl-id(u)= m.cl-id, d’après R2.e, à C2 Statut(u)= N M et cl-id(u)= id(M ax). – Le cas cl-id(u)> m.cl-id est impossible. Le nœud est cohérent et cl-id(M ax)= id(M ax)= M ax{id(v), v ∈ G}.  Corollaire 5.3: A C2 , tous les nœuds voisins du Max appartiennent au même cluster que Max. Corollaire 5.4: Soit u ∈ N eigh(M ax), d’après le corollaire 5.2, à C2 , nous avons cl-id(u)= id(M ax) et Statut(M ax)= CH Théorème 5.1: ∀ i ≥ 1 à Ci tous les nœuds sont cohérents. Preuve. Faisons la preuve par récurence. Pour i= 1 à C1 , ∀u ∈ G, u est cohérent d’après le lemme 5.2. Supposons que la proposition est vraie jusqu’au rang i. Nous avons donc ∀ 1 6 j ≤ i, u est cohérent à Cj . Prouvons maintenant que u est cohérent à Ci+1 . 1) Soit u ∈ G tel que Statut(u)= CH à Ci . D’après l’hypothèse de récurence u est cohérent donc d’après la

35

définition de la cohérence, cl-id(u)= id(u). u va donc appliquer soit R3 soit R4. – Si u applique R3 alors à Ci+1 , Statut(u)= N M et cl-id(u)= cl-id(v) avec v ∈ N eigh(u). Or à Ci Statut(v)= CH et v est cohérent donc cl-id(v)= id(v) à Ci . Donc à Ci+1 , cl-id(u)= id(v), u est donc toujours cohérent à Ci+1 . – Si u applique R4, ni son Statut ni cl-id ne changerons donc u est toujours cohérent à Ci+1 . 2) Soit u ∈ G tel que Statut(u) 6= CH à Ci . Nous savons que u est cohérent à Ci donc les règles R1.a et R1.b ne peuvent pas s’appliquer. – Si u applique R2.a à Ci alors à Ci+1 , Statut(u)= CH et cl-id(u)= id(u) donc u est cohérent à Ci+1 . – Si u applique R2.b à Ci alors à Ci+1 , cl-id(u)= clid(v) avec v ∈ N eigh(u). Or à Ci , Statut(v)= CH et comme v est cohérent à Ci , cl-id(v)= id(v). Donc à Ci+1 , cl-id(u)= id(v) et u est toujours cohérent. – De façon similaire, si u applique R2.c ou R2.d, nous aurons à Ci+1 , Statut(u)= N P . A Ci , par hypothèse de récurence, u est cohérent donc cl-id(u)= id(v) avec v ∈ N eigh(u) donc à Ci+1 nous aurons toujours cl-id(u)= id(v). – De façon similaire, si u applique R2.e nous obtiendrons à Ci+1 , Statut(u)= N M et cl-id(u)= id(v) avec v ∈ N eigh(u). Dans tous les cas, à Ci+1 u est cohérent. Donc ∀i > 1, à Ci , tous les nœuds sont cohérents.  Lemme 5.4: Soient u ∈ N eigh(M ax) et v ∈ N eighu \{M ax}. A C3 nous avons : cl-id(v) 6= cl-id(M ax). Preuve. Soient u ∈ N eigh(M ax) et v ∈ N eighu \{M ax} à C2 , tel que cl-id(v)= id(v), id(u) ou id(w) avec w ∈ N eighv \{u}. D’après le lemme 5.3, Statut(u) ∈ {N M, N P }. Comme v est cohérent cl-id(v) 6= id(u) d’après le théoreme 5.1. Donc cl-id(v)= id(v) ou id(w).  Corollaire 5.5: A C2 , les nœuds à distances 1 de M ax appartiennent à Cluster-Max qui est cohérent. Théorème 5.2: Soit u ∈ G tel que ∀i > 1 dist(u, M ax) < i. A partir de Ci+1 , les valeurs de Statut(u) et cl-id(u) ne changerons plus . Pour des raisons de place, nous présentons dans ce papier qu’un schéma global de la preuve. Preuve. Faisons la preuve par récurrence. Pour i= 2, ce sont les nœuds à distance 1 de M ax, ∀u ∈ N eigh(M ax) à C2 , cl-id(u)= id(M ax) et Statut(u) ∈ {N M, N P } d’après le lemme 5.3. Prouvons qu’à partir de la configuration C3 les valeurs de Statut(u) et cl-id(u) ne changerons plus. A C2 , u peut exécuter les règles R2.c, R2.e ou R4. – S’il exécute la règle R4, alors le théorème est prouvé. – S’il exécuter la règle R2.c alors ∃ v ∈ N eigh(u)\{M ax} tel que cl-id(v) < cl-id(u) et Statut(v)= CH à C2 . A C3 , nous avons alors Statut(u)= N P et cl-id(u) n’a pas changé. Prouvons maintenant par l’absurde que u n’appliquera plus que la règle R2.c. Nous savons que u ne peut appli-

JDIR'09: 10èmes Journées Doctorales en Informatique et Réseaux

quer que R2.c, R2.e et R4. Supposons que u applique R2.e, alors comme les règles sont appliquées avec des priorités, cela signifie que les conditions de la règle R2.c n’ont pas été rencontrées. Cela implique que ∀ v ∈ N eigh(u)\{M ax}, cl-id(v) ≥ cl-id(u). Or cl-id(u)= cl-id(M ax) à C3 . Dons il est impossible que cl-id(v) > cl-id(u). cl-id(v)= cl-id(u) alors comme v est cohérent d’après le théorème 5.1 et que cl-id(u)= id(M ax) la seule solution possible est v= M ax, ce qui contredit notre hypothèse. Donc ∀ i ≥ 2, u n’appliquera plus que R2.c. – S’il exécute la règle R2.e alors de façon analogue à la preuve du cas précédent, cela signifie que ∀ v ∈ N eigh(u), v est également voisin de M ax. Pour i=2 l’hypothèse de récurrence est vraie. Supposons que l’hypothèse est vraie pour 2 ≤ j ≤ i. C’est à dire ∀v ∈ G tel que dist(u, M ax) < i, les valeurs de Statut(u) et cl-id(u) ne changent plus à partir de Ci+1 . Prouvons qu’elle reste vraie pour j= i + 1. Soit u ∈ G tel que dist(u, M ax) < i. u est cohérent et peut appliquer R2.a, R2.b, R2.c, R2.d, R2.e, R3 ou R4. – S’il exécute la règle R2.a alors ∀ v ∈ N eigh(u) tel que id(u) > id(v) à Ci+1 . A Ci+2 , nous aurons alors Statut(u)= CH et cl-id(u)= id(v). Prouvons maintenant par l’absurde que u n’appliquera plus que la règle R4. Nous savons que u ne peut appliquer que les règles R2.a, R2.b, R2.c, R2.d, R2.e, R3 ou R4. On suppose que u applique la règle R2.b. Cela implique ∃ v ∈ N eigh(u) tel que cl-id(u) < cl-id(v) et Statut(v)= CH. Or cl-id(u)= id(u) à Ci+2 . Comme v est cohérent d’après le théorème 5.1 la seule solution possible est donc Statut(u) 6= CH, ce qui contredit notre hypothèse. Donc ∀ i ≥ 3, u n’appliquera plus que la règle R4 et les valeurs de Statut(u) et cl-id(u) ne changerons plus à partir de Ci+2 . – De façon similaire au point précedent, il est possible de prouver que si u exécute R2.b, R2.c, R2.d, R2.e, R3 ou R4 à Ci+1 alors l’hypothèse de récurrence est vérifiée. Pour des raisons de place, nous ne détaillons pas cette preuve dans ce papier. L’hypothèse de récurrence est donc vérifiée ∀i > 1.  Corollaire 5.6: Le temps de stabilisation de l’algorithme est de D+2. VI. C ONCLUSION ET PERSPECTIVES

qu’un unique message pour découvrir le voisinage d’un nœud et faire la clusterisation. De plus, notre algorithme s’adapte automatiquement aux modifications topologiques mais risque de modifier fortement la structuration du réseau. Afin de palier ce phénomène, nous travaillons sur une évolution de notre solution. R ÉFÉRENCES [1] C. Basile, M-O. Killijian, D. Powell, A Survey of Dependability Issues in Mobile Wireless Networks. Technical Report, LAAS CNRS Toulouse, France 2003. [2] S. Maamar, A. Lamia, G. Leila, B. Azeddine, Etude des Performances des Protocoles de Routage dans les Réseaux Mobiles Ad-Hoc, 4 th Internationnal Conference on Computer integrated manufacturing CIP 2007 [3] F. Theoleyre, Une auto-organisation et ses applications pour les réseaux ad hoc et hybrides, PhD thesis, INSA de Lyon, Lyon, France,2006. [4] C-E. Perkins, P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,” Comp. Commun. Rev., Oct. 1994, pp. 234 ?44. [5] T-W. Chen, M. Gerla Global State Routing : A New Routing Scheme for Ad-hoc Wireless Networks, juin 1998. [6] D-B. Johnson, D-A. Maltz, “The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR),” IETF Internet draft,19 July 2004. [7] C-E. Perkins, E-B. Royer, S. Das “Ad hoc On-Demand Distance Vector (AODV) Routing,” RFC 3561, July 2003. [8] C. Johnen, L. H. Nguyen Self-Stabilizing weight-based Clustering Algorithm for Ad hoc sensor Networks. International Workshop, ALGOSENSORS 2006, Venice, Italy, juillet 2006. [9] C-C. Chiang, H-K. Wu, W. Liu, M. Gerla, Routing in Clustered Multuhop, Mobile Wireless Networks With Fading ChannelL. IEEE singapore international conference on networks, 1997. [10] M. Gerla, G. P, S-J. Lee. Wireless, mobile ad-hoc network routing, IEEE/ACM FOUCUS 99, 1999. [11] S. Basagni, Distributed Clustering Ad Hoc Networks, In Proceedings of the IEEE International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN), 1999.

Dans ce papier, nous proposons un nouveau algorithme déterministe pour partitionner le réseau en cluster. L’objectif principal est d’introduire un premier niveau de hiérarchie dans le réseau. L’algorithme que nous développons à cet effet est un algorithme auto-stabilisant qui n’est basé que sur des connaissances locales : chaque nœud ne connaît que la liste de ses voisins. Cela permet ainsi de réduire considérablement la consommation de bande passante en évitant de faire des broadcast ou multicast. Chaque nœud n’appartiendra qu’à un seul cluster en au plus D+2 transitions. Contrairement à la plupart des autres algorithmes de clusterisation, nous utiliserons

36

[12] A. Ephremides, J-E. Wieselthier, D-J. Baker, A Design Concept For Reliable Mobile Radio Network With Frenquency Hopping Signaling, Procedings of the IEEE, Vol.75, NO.1, January 1987 [13] H. Taniguchi, M. Inoue, T. Masuzawa, H. fujiwara, Clustering Algorithms In Ad Hoc Networks, Electronics and Communications in Japan, Part 2, Vol. 88, No. 1, 2005. [14] N. Mitton, Auto-organisation des réseaux sans fil multi-sauts à grande échelle, PhD thesis, INSA de Lyon, Lyon, France, 2006.