Chapitre 3 clustering

1

Clustering dans réseaux mobiles ad hoc

Présenté par :H. BENKAOUHA

2

IntroductionRéseaux ad hoc plats : problèmes de passage à l’échelle (scalabilité).Réseaux ad hoc hiérarchiques.Regrouper des nœuds géographiquement proches en clusters.Un cluster est identifié par son leader (chef) appelé clusterhead (tête de cluster).

3

Introduction

4

Le leaderChoisi par les autres nœuds => processus d'élection distribué.Sinon définir des critères.Peut être en charge de :

Allocation d'adresses pour les nœuds du clusterRoutageAllocation de slots de communicationsEtc.

5

Les clustersLes clusters peuvent être :

Indépendants, Recouvrants,

=> Nœuds passerelles (gateway)Cardinalité : un cluster à au plus k nœuds.Les nœuds ont des informations complètes sur leur groupe.Les nœuds ont des informations partielles pour les autres groupes.

6

Schema représentatif

7

Avantages du clustering

Passage à l’échelle.Limitation des données à stocker.Robustesse.Adaptée à la mobilité des nœuds.Le routage plus efficace.Optimise l'utilisation des ressources.

8

Inconvénients du clustering

Clusterhead = goulot d'étranglement.Surcoût d’élection des leaders.Surcoût de maintenance et reconstruction des clusters.

9

Comment hiérarchiser?

Choix du leader d’un cluster.Stratégie de choix des nœuds faisant partie d’un cluster.Remplacer un leader.Reconstruire un cluster.Supprimer un cluster.

10

Exigences du clustering

L’organisation en clusters doit être distribuée.=> Critères de formation distribuée des clusters.Bon protocoles de routage intra et inter-clusters.Processus de localisation.…

11

Défis à releverGénérer le moins de trafic possible

=> Favoriser de préférence le trafic local.Minimum de trafic possible lors de la formation des clusters.

Trouver une organisation stable face à la mobilité des nœuds.

Limiter le trafic dû à la maintenance et la reconstruction des cluster.

Prendre en considération la contrainte d’énergie.

12

Choix du leader

Election des chefs de clustersDésignation selon des critères.Mécanismes de base :

Identificateur (le plus petit id)Degré (le degré le plus fort)Energie (possibilité de vivre longtemps)Mobilité (faible)…

13

Former les clusters

Définir la cardinalité du cluster.Définir la notion de voisinage avec le leader : DiamètreC’à.d. le nombre de sauts entre un membre d’un cluster et son leader.

14

Maintenance des clustersComment tenir compte des changements de topologie dus à :

Déplacements : mobilité.Énergie.Déconnexion.

Violations des contraintesArrivée d’un nouveau nœud.Un nœud a la propriété d’éligibilité meilleure que celle du leader.

15

Lowest-ID Cluster Algorithm (LID)

Chaque nœud doit avoir un identifiant unique ID.Le nœud qui a le plus petit ID parmi tous ses voisins est chef => Compare son ID avec ceux des voisins.Le cluster = le leader et tous ses voisins. Une fois le cluster formé : tous les membres ne peuvent plus participer au processus d’élection.Avantages : Simple, RapideInconvénients : Grand nombre de clusters, Ne peuvent être réglable à l’évolution de la topologie.

16

Least Clusterhead Change Algorithm (LLC)

Conçu pour minimiser le changement de clusterheadApporte une meilleure stabilité dans la composition des clusters.

17

High-Connectivity Clustering (HCC)

Election basée sur le degré de connectivité (nombre de voisins du nœud).Cet algorithme souffre des fréquents changements de leaders.

18

Approche basée sur le poidsUn 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. Il est supposé que chaque noeud a la connaissance de son poids.DCA : Distributed Clustering Algorithm

Destiné aux réseaux “quasi-static” : déplacements des noeudsdoivent être “lents”.

DMAC : Mobility-Adaptive Clustering algorithmDestiné aux réseaux de grande mobilité.

19

WCA : Weighted Clustering Algorithm

Formule multi-critères : Mobilité,Connectivité,Énergie.

Synchronisation globale.Échange de voisinage avec tous.

20

Remarques

Clusters de diamètre au plus de 2.2 sauts au max entre 2 nœuds du même cluster.Clusters recouvrants.Certains nœuds appartiennent à 2 clusters simultanément.Phase de formation des clusters répétée périodiquement.

21

Clustering à k sauts

Connectivity Based K_Hop ClusteringDegré de connectivitéRé-exécution périodique de l'algorithme.

Max-Min D-cluster formationInformations sur le k-voisinage

22

Routage avec clustering

VSR : Virtual Structure Routing.Routage intra-cluster: proactif.Routage inter-cluster : réactif.Utilisation de la topologie virtuelle pour découvrir les routes.Les routes sont basées sur les identificateurs de clusters (au lieu des nœuds)