Nathalie Mitton Anthony Busson Éric Fleury

• Nathalie Mitton – Anthony Busson - Éric Fleury

• Laboratoire CITI – INSA de Lyon – INRIA

La problématique

Le routage hiérarchique

Le routage hiérarchique

Le routage hiérarchique

État de l’art du routage hiérarchique

Nos objectifs

• Proposer une méthode de formation de clusters :

• non basée sur des critères « fixes »
• distribuée et asynchrone
•  afin de générer le moins de trafic possible lors de la formation
• qui favorise le trafic local
• qui s’adapte aux changements de topologie
• qui propose une organisation des nœuds stable face à la mobilité des nœuds (afin de limiter le trafic de reconstruction)
•  favoriser la stabilité des nœuds lors de l’élection des chefs de clusters
•  permettre de lisser les petits changements de topologie
•  ne pas prendre en compte les nœuds trop mobiles lors de la phase d’élection

Notre métrique de découpage hiérarchique

• la métrique de densité
• analyse
• la formation des clusters
• exemple

Notre métrique: la densité

Notre algorithme: formation des clusters

Notre contribution: exemple

Notre contribution: exemple

Analyse: densité moyenne

• Si on suppose les nœuds de rayon de voisinage R et répartis avec un processus de Poisson d’intensité :

• On ramène le calcul au calcul de la proba qu’un point donné soit chef de cluster à l’aide du théorème de Campbell.
• Si v est un voisin de u à distance r: le nombre moyen de liens entre v et un autre voisin de u revient au calcul du nombre d nœuds dans A(r) :

Analyse: nombre moyen de clusters

Simulation

Exemples d’organisations obtenues

Théorie – Simulations

Ce que l’on constate:

Conclusion et perspectives

Conclusion et perspectives

Merci de votre attention . Des questions ?