Une Auto-Organisation et ses Applications pour les Réseaux Ad-Hoc et Hybrides Thèse de doctorat de

Une Auto-Organisation et ses Applications pour les Réseaux Ad-Hoc et Hybrides

• Thèse de doctorat de

• Fabrice THEOLEYRE

• CITI – INRIA ARES – INSA Lyon

Motivations

• Approche classique en ad hoc

• Vision à plat
• Égalité et solidarité
• Ensemble déstructuré … à utiliser tel quel
• Tout refaire … à chaque fois

• Exemple

• Diffusion
• Routage
• …

Plan

• Objectif et Définition

• Proposition d’auto-organisation

• Propriétés

• Avantages pour les services réseau

• Impact sur la capacité

• Expérimentations

• Conclusion et Perspectives

Objectif

• Organiser le réseau avant son utilisation

• Et prouver l’efficacité d’une auto-organisation

(ma) définition

• Introduit une vue hiérarchique

• Vue logique ≠ topologie radio
• Un ou plusieurs niveaux de hiérarchie

• Localisé (auto)

• Couche d’auto-organisation

• Couche fédératrice
• Mutualisation
• Un moyen et non une fin

Plan

• Objectif et Définition

• Proposition d’auto-organisation

• Propriétés

• Avantages pour les services réseau

• Impact sur la capacité

• Expérimentations

• Conclusion et Perspectives

Description générale de CDCL

Carences des dorsales existantes

• Algorithmes localisés [wu99, stojmenovic01]

• Règle : je suis redondant
• Pas conçus pour la persistance
• Pas d’arbre

• Algorithmes distribués [butenko03]

• Borne de cardinalité
• Pas de maintenance

• Dorsale non flexible

• k-CDS

CDCL – Dorsale - Construction

• Initiée par un (ou plusieurs) leader(s)
• Poids
• énergie, mobilité, degré
• k-CDS
• Création d’un ensemble dominant
• Elections locales
• Interconnexion
• Invitations avec des inondations locales

CDCL – Exemple de 2-CDS

CDCL – Clusters - Construction

• Algorithme classique [lin97]

• Le nœud a plus fort poids  clusterhead
• Puis ralliement des voisins

• Modifications

• Rayon flexible
• Tire parti de la dorsale
• Optimisation du nombre de participants
• Trafic de contrôle
• Auto-organisation intégrée
• Clusterhead = dominant
• Distance via la dorsale

CDCL – Clusters - Construction

CDCL – Maintenance

• Vitale

• Mobilité
• Robustesse aux fautes

• Dorsale

• Maintenance événementielle
• Dominé isolé
• Dominant déconnecté de la dorsale
• Dorsale cassée
• Dominant superflu

• Clusters

• Vecteur de distance

Vue synthétique

Plan

• Objectif et Définition

• Proposition d’auto-organisation

• Propriétés

• Avantages pour les services réseau

• Impact sur la capacité

• Expérimentations

• Conclusion et Perspectives

Evaluation de performances

• Simulations

• OPNET Modeler 8.1
• 40 nœuds distribués aléatoirement
• Couche MAC (802.11) + radio réaliste
• Hellos
• toutes les 4 secondes
• Mesures :
• cardinalité, connexité, persistance
• Paramètres
• densité, mobilité, nombre de nœuds
• Comparaison
• CDCL / Wu & Li

Convergence

Impact de la mobilité

Impact de la mobilité

Trafic de contrôle

Cardinalité bornée

Propriétés - conclusion

• Quelle(s) conclusion(s) ?

• Rapidité de convergence

• Robustesse à la mobilité

• changements locaux  impact local

• Persistance

• Cardinalité bornée (et réduite)

•  Comment l’exploiter efficacement ?

Plan

• Objectif et Définition

• Proposition d’auto-organisation

• Propriétés

• Avantages pour les services réseau

• Impact sur la capacité

• Expérimentations

• Conclusion et Perspectives

Bénéfices d’une auto-organisation

VSR – Passage à l’échelle

Plan

• Objectif et Définition

• Proposition d’auto-organisation

• Propriétés

• Avantages pour les services réseau

• Impact sur la capacité

• Expérimentations

• Conclusion et Perspectives

Problématique

• Capacité

• Débit atteignable par le réseau
• Dimensionne les applications

• Auto Organisation

• Supprime certains liens
• Surcharge certains nœuds
• Pas le plus court chemin

Travaux existants et Objectif

• Etude asymptotique [gupta00,zemlianov05]

• Capacité asymptotique
• Routage intégré dans la modélisation
•  ne permet pas une comparaison

• But :

• Capacité quantitative
• Topologie, trafic de contrôle et routes donnés
• Débit atteignable avec une couche MAC idéale
• ordonnancement parfait, avec équité
• Problème de type multi-flots
• Programmation linéaire

Capacité : problème(s)

• Comment est impactée la capacité ?

• Interférences radio
• Multisauts

• Hypothèses de modélisation

• Liens bidirectionnels
• Broadcast de C
• Unicast de C à D
• Contraintes locales

Contraintes

• Multisauts

• Contraintes linéaires :

Contraintes

• Partage des ressources radio

• Borne inférieure
• Seuls les 2-voisins peuvent interférer :
• Ex : équité terminaux

Contraintes

• Partage des ressources radio

• Borne inférieure
• Partage entre liens radio

Contraintes

• Partage des ressources radio

• Borne supérieure
• Autoriser les communications du type :
• Référencement des communications possibles :

Contraintes

• Partage des ressources radio

• Borne supérieure : calculer la proportion
• Calcul des MIS  NP-Complet  exhaustif
• Algorithme de calcul statistique
• Ex: équité liens radio

Contraintes

• Partage des ressources radio

• Borne supérieure
• Partage entre liens radio
• Avec équité liens radio

Démarche adoptée

• Données

• Topologie, routes, trafic de contrôle

• Contraintes de flux

• sur chaque lien radio traversé

• Contraintes de partage radio

• Borne inférieure
• Borne supérieure

• Programmation linéaire

• Capacité

Capacité

Conclusion

• Réseau ad hoc
• pas d’impact de notre auto-organisation
• impact possible si mal conçu (exemple : [wu99])
• Réseau hybride
• backbone mal équilibré à la racine
• goulot d’étranglement

Plan

• Objectif et Définition

• Proposition d’auto-organisation

• Propriétés

• Avantages pour les services réseau

• Impact sur la capacité

• Expérimentations

• Conclusion et Perspectives

Pourquoi des expérimentations ?

• Evaluation de l’auto-organisation

• Simulations
• OPNET
• cardinalité, persistance, délai, taux de livraison, etc.…
• Analyse théorique
• auto-stabilisation
• complexité
• cardinalité
• …

• problème : la modélisation radio

Evaluation

• Problèmes

• Liens radio
• instabilité
• hétérogénéité
• unidirectionnels
• Performances de 802.11 [dhoutaut03]

Débits TCP

Mobilité – Débit TCP

Plan

• Objectif et Définition

• Proposition d’auto-organisation

• Propriétés

• Avantages pour les services réseau

• Impact sur la capacité

• Expérimentations

• Conclusion et Perspectives

Conclusion

• Proposition d’une structure d’auto organisation

• Robustesse
• Stabilité
• Rapidité de convergence

• Avantages pour les services réseau

• Routage
• Internet sans-fil multisauts
• Peu d’impact sur la capacité

• Évaluation

• Simulations
• Analyse théorique
• Expérimentations réelles

•  « Une auto-organisation améliore les performances d’un réseau ad hoc ou hybride »

Perspectives

• Conception

• Plateforme complète

• Évaluation de performances

• Implémenter de nouveaux testbeds
• Scénarios test

• Auto-*

• réseaux de capteurs ?
• auto configuration ?
• contrôle de topologie ?
• architecture : en couches, modulaire ?