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



Yüklə 445 b.
tarix26.10.2017
ölçüsü445 b.


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

  • 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]

  • 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


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é

  • Auto Organisation

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


Travaux existants et Objectif

  • Etude asymptotique [gupta00,zemlianov05]

  • 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



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
    • 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 ?







Dostları ilə paylaş:


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2017
rəhbərliyinə müraciət

    Ana səhifə