I.
Chapitre 0 : Les Systèmes Distribués en Environnements Ad Hoc :
Ø Système Distribué : Ensemble fini de processus communicant via message à travers un
système de communication.
Ø Réseaux Multi-sauts : C’est lorsque le message de la source passe par plusieurs nœuds pour
atteindre la destination.
Ø Système mobile :
• Cellulaire (Avec infrastructure) :
- Il existe des stations de base qui communique entre eux.
- Toutes les communications passent par la station de base.
• Ad-Hoc (Sans infrastructure) :
- Communication direct entre les nœuds.
- Réseau multi-sauts ou chaque nœud joue le rôle d’un routeur.
Ø Ad-Hoc : A cet effet (c.à.d. il est réalisé pour une opération précise).
Ø Pourquoi existe des communication uni et bidirectionnelle : A cause de la portée de chaque
nœud, par exemple si un nœud a une portée de 500m et l’autre 300m donc le 2eme nœud
reçoit du premier nœud ms ne peut pas répondre.
Ø Types de réseaux Ad-Hoc :
1. MANET : Mobile Ad-Hoc Network (unités mobiles seulement).
2. WANET : Vehicular Ad-Hoc Network (Entre véhicule et route).
3. WSN : Wireless Sensor Network (Réseau de capteur sans fil).
4. WASN : WSN + Actionneurs
5. IOT : Internet of thinks, Echange de données entre les dispositifs du monde réel avec
le réseau internet.
Ø Manet (Ad-Hoc) : Réseau Ad-Hoc + mobilité, il se forme de façon spontané à partie d’entités
mobiles automatiquement organisé sans besoin d’infrastructure fixe préexistante.
Ø Caractéristique d’un réseau Manet :
• Topologie dynamique
- Quitter ou rejoindre le réseau à tout instant
- Déplacement et changement d’état des nœuds
- Risque de partitionnement (Système se divise en plusieurs entités)
• Risque hétérogénéité des nœuds (Equipements, propriétés physique des équipements,
les logiciels).
• Bande passante limitée (inférieure aux réseaux filaire et le taux d’erreur élevé.
• Limite de ressources de l’équipement (Mémoire, processeurs …).
• Contrainte d’énergie (Problème d’autonomie)
• Déconnexions fréquentes (Volontaire, Non volontaire, Mode veille).
• Sécurité limitée car c’est une transmission sans fil n’importe qui peut capter les données
et réaliser des attaques donc les nœuds sont vulnérables.
Ø Avantage d’un réseau Ad-Hoc :
• Facilité de déploiement
• Création de réseau au vol
• Emergence de nouvelles applications
Ø Domaines d’application :
• Domaine militaire
• Opérations de secours
• Catastrophes naturelles
• Capter des grandeurs physiques (température, pression, humidité ...).
II. Chapitre 1 : Routage dans les réseaux mobiles Ad-hoc:
Ø Routage unicast dans les réseaux Ad-Hoc :
• Tous les nœuds sont de même niveau.
• Il n’existe pas de routeurs dans le réseau.
• La source envoie un paquet vers la destination en passant par des nœuds intermédiaires.
• Le routage permet à un hôte de trouver le prochain hôte en utilisant le trajet le plus
court existant dans le réseau.
Ø Le calcul du plus court chemin basé sur : le nombre de nœuds intermédiaires.
Ø Critères de performance (Manet) :
• Nombre de sauts (hop).
• Bande passante disponible
• Stabilité des routes par rapport à la mobilité
• Consommation d’énergie (Emission des messages fait consommer le plus d’énergies dans
les nœuds donc un bon protocole c’est celui qui fait minimiser l’envoie des messages
entre les nœuds).
Ø Classes de protocoles de routage :
• Proactifs : DSDV, OLSR, TBRBF, FSR, DREAM, BABEL
• Réactifs : DSR, AODV, TORA, RDMAR, ABR
• Hybrides : ZRP, SHARP, DDR
Ø Technique pour déterminer le plus court chemin dans le protocole proactif : Chaque nœud
maintient une table de routage qui la met à jour par échange de message.
• Technique état de lien (Link State) :
- Chaque nœud maintient sa propre vision de la topologie du réseau et diffuse (par
inondation) l’état des liens de ses voisins à tous les nœuds du réseau.
- Mise à jour périodique ou en cas de changement
- Chaque nœud diffuse l’état des liens de ses voisins
- Un nœud recevant les informations d’état de liens met à jour sa table de routage
- Utilisation d’un algorithme de calcule des plus court chemins
• Technique vecteur de distance (Distance vector) :
- Chaque nœud diffuse à ses voisins sa vision des distances le séparant de tous les
autres hôtes (initialement 0 vers lui-même et 1 vers chacun de ses voisins)
- Pour choisir le plus court chemin d’un nœud vers n’importe quelle destination en se
basent sur les informations reçus par tous ses voisins.
- Un message de mise à jour contient un vecteur d’une ou plusieurs entrées ou chaque
entrée contient la distance vers une destination donnée (technique de l’algorithme
de Bellman-Ford)
- Le processus se répète tant que y a un changement de la distance minimale séparant
deux nœuds
Ø Technique pour déterminer le plus court chemin dans le protocole réactif :
- Les nœuds mobiles ne maintiennent pratiquement pas d’informations sur la
topologie du réseau (pas besoin de la table de routage sauf des exceptions par
exemple l’algorithme AODV).
- Etablissement d’une route uniquement lorsqu’elle est demandée avec un mécanisme
de découverte.
- La source émet une requête de route qui est diffusée jusqu’à atteindre le nœud
destinataire (les nœuds intermédiaires sont mémorisés durant la phase de diffusion
pour pouvoir utiliser le chemin inverse pour que la destination puisse répondre à la
source).
- La source utilise la route découverte pour transmettre les données à la destination.
Ø Technique pour déterminer le plus court chemin dans le protocole hybrides :
- Il forme la combinaison entre le protocole réactif et proactif
- Il permet d’offrir un compromis entre charge de trafic et temps de latence
Ø Choix du protocole de routage : le choix dépend du type d’application et du réseau
• Protocole Réactif :
- Permet un meilleur passage à l’échelle parce qu’il réduit la charge de trafic dans le
réseau (pas de diffusion périodique)
- Mieux adapté pour les réseaux mobiles disposant d’une bande passante limitée
• Protocole Proactif :
- Offre un meilleur temps de latence pour établir une route car Il ne nécessite pas de
mécanisme de découverte préalable
- Mieux adapté pour les réseaux mobiles ayant des contraintes sur le temps
Ø Message de contrôle : Messages propre au protocole utilisé par exemple un message de
découverte de route ou de mise à jour ou des messages de réponses sont tous des messages
de calculé spéciale pour le protocole utilisé.
Ø Message de calcul (données) : Message envoyer pour chercher la route vers une destination
Ø DSDV (Destination-Sequenced Distance vector routing protocole) :
• Protocole proactif (vecteur à distance) (Bellman-Ford)
• Chaque nœud maintient une table de routage
[Destination, Next-Hop, Distance, N° séquence]
• Basé sur les numéros de séquences :
- Résoudre le problème de boucle de routage et nous permet de choisir les routes les
plus fraiches.
- Il est lié au nœud de destination (c’est elle qu’elle vas l’incrémenter sauf seulement à
l’initialisation)
- Il est incrémenté en cas de changement de topologie
è Si Numéro de séquence Paire la route Existe vers la destination
è Sinon le lien n’existe pas
- A la réception le destinataire incrémente le numéro de séquence par +2
- Lorsque la topologie change (destruction d’un lien par exemple) le nœud
intermédiaire incrémente le numéro de séquence +1 et informe les autres que y a
plus route vers la destination dans le lien concerné (si au moment de changement de
topologie et un message circule il sera rejeté ou bien envoyer dans une nouvelle
route après la mise à jour).
- Choix d’un chemin :
è On choisit toujours le plus récent (numéro de séquence le plus élevé).
è Si égalité, on choisit la plus petite distance.
• Mise à jour des tables de routage :
1- Mise à jour complète : diffusion périodique de la table de routage uniquement entre
les voisins (et non pas une diffusion par inondation broad-cast).
2- Mise à jour incrémentale : Se fait en cas de changement de topologie (Rupture) et les
informations diffusées sont seulement les nouvelles informations.
Ø OLSR (Optimized Link State Routing Protocol) :
• Protocole Proactif (état de liens) (Dijkstra)
• Adaptation du protocole OSPF
• Contrairement au protocole OSPF, OLSR réduit la surcharge dans le réseau.
• L’informations d’état de lien est produite seulement par les nœuds élus comme MPRs
(Multipoint Relay)
• Un nœud MPR doit rapporter seulement des liens entre lui-même et ses sélecteurs
• Principe de fonctionnement :
- Chaque nœud a un ensemble de MPR(i) (les voisins directs de i permettant
d’atteindre tous les voisins à 2 sauts).
- Chaque nœud MPR a un ensemble de MPR-Selectors(j) (les voisins de j qui ont
sélectionné j comme MPR).
- Chaque nœud réalise 2 opérations principales :
è Déterminer les voisins directs (Par envoie des messages Hello)
è Déterminer les MPR et MPR-Selecotrs qui vont s’échanger des messages TC
(contrôle de topologie).
• Les messages Hello permettent :
ü Découvrir l’ensemble du réseau
ü Transmettre l’état et le type de lien entre un nœud et ses voisins
ü Pour élire et spécifier les MPRs
• Les messages TC permettent :
ü Transmettre la liste des voisins et construire localement une vue globale de la
topologie du réseau
ü Réaliser les tables de routage à partir de cette topologie en utilisant l’algorithme
de Dijkstra
Ø AODV (Routage avec vecteur de distance à la demande)
• Protocole réactif (routage avec vecteur de distance à la demande)
• Amélioration du DSDV
• Prendre en charge seulement les liens symétriques
• Utilise 2 mécanismes (découverte de route / maintenance de route) inspiré du DSR
• Chaque nœud maintient une table de routage partielle :
Adresse destination
Nœud Suivant
Nombres de sauts
Numéro de séquence (affecté au chemin par la destination)
Temps d’expiration de l’entrée dans la table de routage
Routing flag (actif/ Non actif) un booléen pour spécifier l’état de la route
• Structure de la requête de découverte de la route :
Identifiant de la source
Numéro de séquence
Identifiant de la destination
BroadCast ID (incrémenté à chaque nouvelle diffusion de la requête)
Le temps de vie TTL (décrémenter à chaque arrivé d’un nœud intermédiaire)
• Utilisation des numéros de séquences dans les messages de requêtes qui servent à
maintenir la consistance des informations de routage et pour l’utilisation des routes les
plus fraiches (si le numéro de séquence n’est pas connu alors la valeur par défaut est
égale à nul)
• Principe de fonctionnement :
1- Découverte de la route :
- Un nœud diffuse une RREQ pour créer un chemin s’il veut atteindre une destination
et sa route est non disponible dans la table de routage (destination inconnue, TTL
expiré, chemin défaillant).
- A la réception de RREQ par un nœud intermédiaire, il sauvegarde l’identifiant à partir
de lequel RREQ est reçu pour construire le chemin inverse (lors de la réponse de la
destination) et diffuse le RREQ vers ses voisins.
2- Réponse de route :
- Incrémentation du numéro de séquence NUMSEQ++ par la destination et prend le
maximum entre le numéro de séquence local et reçu avant de répondre à la source.
- Le Message RREP est un message de réponse qui est diffusé selon les entrées crées
par RREQ
- Dans le cas où le message RREP n’est pas reçu durant une certaine période
RREP_WAIT_TIME alors la source rediffuse RREQ en incrémentant le BroadCast id
- Dans le cas où le message RREQ est diffusé pendant un certain nombre de fois
RREQ_RETRIES sans recevoir de réponse alors un message d’erreur est délivré
3- Maintenance des routes :
- Transmission périodique des messages « Hello » pour pouvoir détecter les nœuds
voisins
- A l’envoie de 3 messages « Hello » sans avoir de réponse le nœud suppose que le lien
est défaillant
- Suppression des entrées de la table de routage participantes au chemin actif
concernées par les liens défaillants
- Lorsqu’un lien est défaillant et un message de RREP est dans la route de la
destination vers la source un message UNSOLICITED RREP est diffusé aux voisins
actifs jusqu’à la source contenant (NUMSEQ+1 et Nombre de sauts = infini)
Ø Voisin actif : Délivre au moins un paquet de données sans dépasser une période
Ø Entrée active : Utilisée par un voisin actif
Ø Chemin actif : Passe par des entrées actives dans la transmission
Ø ZRP (Zone Routing Protocol) :
• Protocole hybride
• Utilise 3 protocoles :
è IARP (Proactif)
è IERP (Réactif)
è BRP
• Chaque nœud définie sa zone de routage avec une distance minimale (Nombre de sauts)
avec distance <= Rayon de la zone
• IARP :
- Semblable à DSDV et appliquer à l’intérieur de la zone
- Offre des routes optimales vers la destination à l’intérieur de la zone
• IERP :
- S’occupe de la recherche à l’extérieur de la zone
• BRP :
- Utiliser pour construire la liste des nœuds périphérie
- Guide la propagation des requêtes de recherche de route de IERP dans le réseau
• Algorithme :
SI (Destination appartient à la zone) Alors chemin trouvé par IARP
SINON
Envoyer (RREQ) vers Nœuds périphériques
SI (Nœud périphérique connait D) Alors
Envoyer (RREP)
Chemin trouvé
SINON
Nœud périphérique diffusent RREQ vers leurs propres nœuds périphériques…
FSI
FSI
Ø TORA (Temporary Ordered Routing)
• Protocole Réactif (création de routes à la demande)
• Basé structure DAG (structure logique qui permet de mettre à jour les routes)
• Hypothèses :
- Réseaux Manet
- Chaque nœud à un identifiant unique
- Connaissance préalable du voisinage
- Liens bidirectionnels
- Horloge globale
• Principe de fonctionnement :
- Création de DAG (graphe acyclique dirigé) en envoyant des messages de QRY en cas
de création des routes et des messages UPD en cas de mise à jour ou des messages
de réponses et à la fin des messages de type CLR en cas de suppression de routes.
- Le principe consiste à transformer un graphe non orienté (réseau) en graphe orienté
(DAG), il utilise aussi pour chaque destination un quintuplé appelé Height (Hauteur)
(-, -, -, -, i)
- Utilisation des messages « Hello » pour connaitre les voisins d’un nœud.
• Avantages :
- Offre plusieurs routes vers la même destination
- Maintenance simple
- Pas de boucles de routage
- Optimisation des utilisations des ressources
- Détection du partitionnement
- Suppression des routes invalides
• Inconvénients :
- Les routes ne sont pas optimales
- Ne prend pas en considération les nouveaux liens
- Utilisation d’une horloge physique globale.
- Il n’y a pas d’étude comparative dans l’article
Ø TBRPF (Topology BroadCast based on reverse path forwarding)
• Protocole proactif (création d’une table de routage)
• Protocole à état de liens (connaissance de la topologie, information sur les liens et leurs états
et couts).
• Hypothèses :
- Réseau MANET
- Chaque nœud a un ID unique
- Attribution d’un Coût à chaque lien de communication sans fil (entre 2 nœuds)
- Connaissance préalable du voisinage
- Liens bidirectionnels : pas de dé séquencement, pas d’erreurs
• Basé sur le protocole ERPF
• Principe de fonctionnement :
- Construction d’un arbre couvrant pour chaque source (dirigé vers la source) et ce
dernier est sauvegardé de façon distribuée
- Pour Chaque source, un nœud connait (parmi ses voisins) dans l’arbre couvrant (son
père « successeur » et ses enfants « prédécesseurs »)
- L’arbre permet d’avoir connaissance de la topologie et des états des liens et évite
l’inondation aveugle dans le réseau
- La construction de l’arbre nécessite l’utilisation de la topologie et les états des liens
- Chaque nœud i maintient une table de topologie TTi
État d’un lien (les 2 extrémité, son cout et Numéro de séquence)
Information sur l’arbre (père et ses enfants)
Les voisins à un saut (Grâces aux messages « Hello »)
- Lors du lancement :
Un temps de convergence est nécessaire
Chaque nœud connait ses voisins et qui sont les sources de ses arbres et les
parents aussi
Les voisins se déclarent enfants pour chaque source
L’information est propagée petit à petit dans le réseau
A un moment donné chaque nœud connaitra tous les nœuds du réseau et les
arbres couvrants créés
- Mise à jour événementielle : Nouveau lien, Rupture d’un lien, Modification du coût
d’un lien
- Mise à jour périodique : Chaque Dt pour affecter une nouvelle date (numéro de
séquence le plus récent) à chaque lien et transférer l’information
• Avantages :
- Utilisation de l’arbre pour minimiser la diffusion des messages de topologie.
- Simple.
- Bon mécanisme de maintenance
• Inconvénients :
- Période de convergence non évidente : Sortie du paradoxe poulet-œuf.
- Trop d’informations sauvegardées : un arbre pour chaque source.
- Maintenance à chaque événement + périodique : Surcharge
- Problème dans les réseaux de grande taille.
III. Routage Multicast dans les Manets :
• Pourquoi on utilise le multicast : Besoin de travailler en groupe pour effectuer une tache
• Avantage du Multicast :
- Réduire les couts de communication (Pour une seule transmission on la délivre à
plusieurs destinations)
- Economiser la bande passante
- Economiser les ressources réseau
• Exigence pour réaliser le multicast :
- Adressage multicast
- Un nœud désirant participer à la session doit joindre l’adresse réseau
- Aptitude à propager l’information reçu au niveau des nœuds
• Applications du multicast :
- Conférences
- Travail collaboratif
- Mise à jour des Base de données répliqués
- Jeux distribués
• Contraintes liées au routage multicast :
- Les membres groupe changer
- Topologie change (les états de liens changent)
- Les ressources (Disponibilité de la bande passante, Contraintes d’énergie)
• Défis de conception :
- Robustesse (Résister à la mobilité et le taux de délivrance de paquet est très élevé)
- Efficacité (Nombre de messages de contrôles < Nombre de message de diffusion)
- Diminution de surcout en contrôle
- Gestion des ressources (Economiser énergie, mémoire …)
- Passage à l’échelle
- Assurer une certaine qualité de service
- Sécurité
• Classification des protocoles de routage multicast :
1- Basé arbre (Tree-based) :
- Un seul chemin entre source et la destination
- Structure distribuée et sauvegarder au niveau de la source
- Basé sur les liens physique ou logiques (si le lien est un lien physique alors l’arbre va
contenir des nœuds transmetteurs (forwarding Grey) qui n’appartient pas au groupe
multicast)
- Avantage : Meilleur en efficacité
- MAODV (création se fait à la demande), ADMR, AMRIS, LAM, LGT …
2- Basé Maille (Mesh-based) :
- Il existe plusieurs chemins de la source vers la destination
- Avantage : Meilleur en robustesse (si forte mobilité, disponibilité de routes
multiples), et mise à jour en cas de panne rapide et facile.
• Classification selon l’approche de construction du chemin (réactif / proactif)
• Classification selon l’initialisation de la session multicast (par l’émetteur/ par le récepteur)
IV. Routage avec Qos dans les MANETs
Ø Modèle de Qos : Il faut classifier les paquets de données en minimum deux classes :
- Paquets Qos
- Paquets Ordinaires BE (Best Effort) - pas d’exigence particulière –
Ø Contrôle d’admission :
- Décider si on accepte ou on refuse le flux Qos
- Dégrade à un niveau inacceptable Qos offert = Refuser
- Un contrôle d’admission dépend :
ü De la politique choisie
ü Des ressources disponibles
ü Qos demandée par les flux déjà acceptés
ü Degré d’exactitude d’estimation des ressources
(Mauvaise estimation = Mauvais contrôle d’admission)
Ø Routage par Qos :
- Définir une route entre la source et la destination
- Satisfaire exigence Qos du flux
- Utiliser la signalisation Qos pour sélectionner une route satisfaisante (une
signalisation veut dire Estimer et contrôler localement Qos)
Ø Défis :
- Algorithme simple (complexité proche de Dijkstra)
- Routes courtes implique la Minimisation des ressources réseau
- Prendre en considération la métrique choisie
- Rester conscient des interférences
Ø MAC avec Qos :
- Doit être déterministe
- Gère la priorité
- Fournit des informations Qos
Ø Métrique pour routage Qos :
- Additive : Délai = La somme des délais sur les liens formant la route
- Concave : Bande passante = Minimum des bandes passantes sur les liens formant la
route
- Multiplicative (Taux d’erreur) : produit des taux d’erreur sur la route
Ø Types de routages :
• Routage monocritère :
- Le cout d’un lien est lié à la valeur de la métrique considérée
- Acceptation d’un nouveau flux modifie les délais et la bande passante dans la zone
d’interférence des nœuds intermédiaires
• Routage multicritère : Prend en considération plusieurs critères (Meilleur Bande passante,
si égalité meilleur délai …etc.)
Ø Extension de protocoles de routage :
• AODV avec Qos :
- Entendre message RREQ et RREP pour sélectionnée route satisfaisant Qos
- Rajout d’un message ICMP Qos-Lost pour signaler l’impossible de satisfaire Qos
- Réserver une Bande passante sur chemin par zone d’interférence
• OLSR avec Qos :
- 4 classes de flux :
1- Message de contrôle OLSR
2- Exigence délai
3- Exigence bande passante
4- Best effort
- L’utilisateur à accès a 3 classes de flux (Exigence délai, Exigence BP, Best effort)
- Types MPR :
MPRF : Procédure classique pour la diffusion
MPRB :
§ Se base sur la bande passante pour le routage
§ Chaque nœud mesure et inclut sa Bande passante local disponible
dans les messages « Hello »
§ Election du MPRB en se basant sur la bande passante disponible à 2
sauts
§ MPRB embarque dans TC :
v BP minimum dans sa zone d’interférence
v Nœuds MPRB selectors
v BP disponible
V. Clustering dans réseaux mobiles Ad-Hoc
• Un cluster : Groupe de nœuds géographiquement proches
• Un cluster est identifié par un leader « cluster head »
• Choix d’un leader :
- Défini selon un processus d’élection distribué
- Défini selon des critères, qui sont :
Identificateur (Plus grand ou plus petit)
Degré (Plus fort degré)
Une grande énergie
Une faible mobilité
• Un cluster peut être Indépendants (pas de nœud commun entre les cluster) ou recouvrant
(contrairement au indépendants)
• Nœud passerelles :
- Direct : un nœud qui fait partie de deux cluster et permet la communication entre
deux cluster différent
- Indirect : une paire de nœuds qui appartient à 2 clusters voisin et sont aussi voisins
qui vont permettre la communication entre les 2 chef des clusters
• Cardinalité d’un cluster K = Nombre maximum de nœuds dans un groupe
• Les nœuds ont des informations complètes sur leurs groupe et partielle sur les autres
groupes
• Avantage d’un cluster :
- Passage à l’échelle
- Limitation des données à stocker
- Robustesse
- Adaptée à la mobilité des nœuds
- Routage plus efficace
- Optimise l’utilisation des ressources
• Inconvénient du clustering :
- Cluster head = goulot d’étranglement
- Surcout d’élection des leaders
- Surcout de maintenance et reconstruction des clusters
• Exigence 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
• Défis à relever :
- Générer le moins de trafic possible
- Trouver une organisation stable face à la mobilité des nœuds
- Prendre en considération la contrainte d’énergie
• Former les clusters :
- Définir la cardinalité du cluster
- Définir la notion de voisinage avec le leader
- « Diamètre » représente le nombre de sauts entre un membre du groupe et son
leader
• Maintenance des clusters :
- Tenir compte des changements de topologie (Mobilité, Energie, Déconnexion)
- Violation des contraintes :
Arrivée d’un nouveau nœud
Un nœud à des propriétés meilleures que celle du leader
• Lowest-ID cluster Algorithm (LID)
- Chaque nœud a un ID unique
- Le nœud qui a le plus petit ID est le leader
- Distance entre deux nœuds d’un cluster est max=2
- Un nœud ayant deux leaders est une « Passerelle »
- Si le cluster forme les membres ne peuvent pas participer au processus d’élection
- Périodiquement un nœud transmet son id et les identifiants de ses voisins
- Nouvelle élection est produite si une violation de condition d’éligibilité et en cas de
changement des membres
- Avantage : Simple et rapide
- Inconvénients : certains clusters ne peuvent être réglable au passage à l’échelle
• Least cluster head change Algorithm (LCC)
- Même principe que LID pour l’élection du CH et formation des clusters
- Il permet de minimiser la maintenance :
Un déplacement d’un nœud mon chef = aucun changement des 2 chefs
2 chefs dans le même cluster = changement de chef
- Avantage : Apporte une meilleure stabilité dans la composition des clusters
• High – connectivity clustering (HCC)
- Election basée sur le degré de connectivité le plus grand
- Chaque nœud calcule sa connectivité en recevant les IDs de ses voisins (Il diffuse son
ID à ses voisins)
- Echange de l’information du degré de connectivité sur le voisinage
- Le nœud ayant le plus grand degré se déclare leader
- Diamètre = 2
- Cardinalité = illimitée
- Inconvénients : L’algorithme souffre de fréquents changements de leaders
• Approche basée sur le poids
- Poids est défini par :
Vitesse de déplacement
Energie
Combinaison de plusieurs métriques …
- Critère d’élection : Poids optimal dans le voisinage
- Hypothèse : chaque nœud connait son poids
- Algorithme :
1- DCA (Distributed clustering Algorithm) : les nœuds sont lents et quasi-statique
2- DMAC (Mobility-Adaptive Clustering) : Destiné aux réseaux de grande mobilité
• WCA (Weighted clustering Algorithm
- Formule multicritères :
ü Mobilité
ü Connectivité au degré
ü Energie
ü Distance moyenne entre le nœud et ses voisins
ü Temps cumulé par un nœud en tant que cluster header
- Synchronisation globale
- Echange de voisinage avec tous les nœuds
- Le cluster header est celui qui a le poids minimal
- Pas de deux clusters header voisins
- Diamètre = 2
- Cluster header communiquent directement en passant en mode HPM en
augmentant son rayon de communication
- La phase de formation des clusters est répétée périodiquement
Ø Clustering à k sauts
- Le choix de CH se fait par degré de connectivité et en cas d’égalité on fait notre choix
par rapport au ID
- Réexécution périodique de l’algorithme
- Fusion de clusters pour atteindre K sauts