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

Directeurs de thèse :

Fabrice Valois

Eric Fleury

2/47

Contexte Qu’est ce qu’un réseau ad

hoc ? Hybride ?

Défis Routage, Confidentialité…

Contraintes Mobilité Hétérogénéité Radio

3/47

Motivations Approche classique en ad hoc

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

Exemple Diffusion Routage …

4/47

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

5/47

Objectif

Organiser le réseau avant son utilisation Et prouver l’efficacité d’une auto-

organisation

dominant

Ensemble Connecté Dominant

(CDS)

Clustering: Diamètre / rayon /

cardinalité

dominé

clusterhead

6/47

(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

Theoleyre, Valois, Auto-organisation de réseaux ad hoc : concepts et impacts, chap. 5 de Réseaux mobiles ad hoc et réseaux de capteurs, Hermès, 2006, 101-128

7/47

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

8/47

Description générale de CDCL

1. Découverte de voisinage

2. Construction d’une dorsale

3. Construction de grappes

Theoleyre, Valois, A Virtual Structure for Mobility Management in Hybrid Network, in IEEE WCNC, USA, 2004

Theoleyre, Valois, Structure virtuelle pour une auto-organisation dans les réseaux ad-hoc et hybrides, Annales des Télécommunications, accepté avec révisions mineures

9/47

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

5

68

3

2

7

5

7

4

8

10/47

CDCL – Dorsale - Construction Initiée par un (ou plusieurs) leader(s) Poids

o énergie, mobilité, degré k-CDS

1. Création d’un ensemble dominanto Elections locales

2. Interconnexiono Invitations avec des inondations locales

11/47

4

CDCL – Exemple de 2-CDS

10

5 Remarque :Construction

d’un arbre

4

7

5

2

98

8

Dominant

Dominé

En élection

Hello

Invitation

Lien radio

connexion

Leader

12/47

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

o Optimisation du nombre de participantso Trafic de contrôle

Auto-organisation intégréeo Clusterhead = dominanto Distance via la dorsale

13/47

CDCL – Clusters - Construction

5

8

4

3

7

10

5

7

10

Distance max = 2 sauts

14/47

CDCL – Maintenance Vitale

Mobilité Robustesse aux fautes

Dorsale Maintenance événementielle1. Dominé isolé2. Dominant déconnecté de la dorsale3. Dorsale cassée4. Dominant superflu

Clusters Vecteur de distance

15/47

Vue synthétique

16/47

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

17/47

Evaluation de performances Simulations

OPNET Modeler 8.1 40 nœuds distribués aléatoirement Couche MAC (802.11) + radio réaliste Hellos

o toutes les 4 secondes

Mesures :o cardinalité, connexité, persistance

Paramètreso densité, mobilité, nombre de nœuds

Comparaisono CDCL / Wu & Li

18/47

Convergence

50 nœuds statiques, degré = 10, kcds=1

19/47

Impact de la mobilité

40 nœuds, degré = 10, modèle de mobilité random waypoint

20/47

Impact de la mobilité

40 nœuds, degré = 10, modèle de mobilité random waypoint

21/47

Trafic de contrôle

degré = 10, modèle de mobilité random waypoint, vitesse de 5m/s

22/47

Cardinalité bornée

degré = 10

Borne théorique :

MCDSkCDCL .=

23/47

Propriétés - conclusionQuelle(s) conclusion(s) ?

1. Rapidité de convergence2. Robustesse à la mobilité

changements locaux impact local

3. Persistance4. Cardinalité bornée (et réduite)

Comment l’exploiter efficacement ?

24/47

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

25/47

Bénéfices d’une auto-organisation Routage ad hoc

Virtual Structure Routing (VSR) Adapte les protocoles existants Dorsale pour la diffusion Double hiérarchie

Internet sans-fil multisauts Self-Organized Mobility Management (SOMoM) Dorsale = arbre proactif de routage

Économie d’énergieS

D

Theoleyre, Valois, Virtual Structure Routing in Ad Hoc Networks, in IEEE ICC, Corée du Sud, 2005

Theoleyre, Valois, Mobility management in multihops wireless access networks, in IFIP PWC, France, 2005

26/47

VSR – Passage à l’échelle

degré = 10, modèle de mobilité random waypoint, vitesse de 5m/s

27/47

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

28/47

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

Quel impact sur la capacité ?

Comparaison à plat / auto organisé

29/47

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

o Topologie, trafic de contrôle et routes donnéso Débit atteignable avec une couche MAC idéale

ordonnancement parfait, avec équité

Problème de type multi-flotso Programmation linéaire

30/47

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

31/47

Contraintes

Multisauts

Contraintes linéaires :

S D

Quantité de données = q

q q q

Trafic du lien radio e =

Somme des trafics des flux passant par e

32/47

Contraintes

Partage des ressources radio Borne inférieure

o Seuls les 2-voisins peuvent interférer :o Ex : équité terminaux

ab

d

c

e

0 1/5 2/5 3/5 4/5 1

a b c d e

Rivano, Theoleyre, Valois, Capacity Evaluation Framework and Validation of Self-Organized Routing Schemes, in IEEE IWWAN, USA, 2006

33/47

Contraintes

Partage des ressources radio Borne inférieure

o Partage entre liens radio

0 1/5 2/5 3/5 4/5 1

a b c d e

Trafic de contrôle

de dTrafic de

données vers c

Trafic de données vers e

2

1 −2

1 −

ab

d

c

e

34/47

Contraintes

Partage des ressources radio Borne supérieure

o Autoriser les communications du type :

o Référencement des communications possibles :

35/47

Contraintes

Partage des ressources radio Borne supérieure : calculer la proportion

o Calcul des MIS NP-Complet exhaustifo Algorithme de calcul statistique

Ex: équité liens radio

36/47

Contraintes

Partage des ressources radio Borne supérieure

o Partage entre liens radioo Avec équité liens radio

02/3- 1-

IS1 IS2

Trafic du lien radio a = Trafic

du lien radio c

1

Trafic de contrôle

Trafic du lien radio b

a

b

c

a

b

c

37/47

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é

38/47

Capacité

degré = 10, capacité par flux, toutes les routes actives, équité liens radio

Wu & Li

VSR = OLSR :borne >

borne <

39/47

Conclusion

Réseau ad hoco pas d’impact de notre auto-organisation o impact possible si mal conçu (exemple : [wu99])

Réseau hybrideo backbone mal équilibré à la racineo goulot d’étranglement

40/47

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

41/47

Pourquoi des expérimentations ? Evaluation de l’auto-organisation

Simulationso OPNETo cardinalité, persistance, délai, taux de livraison, etc.

… Analyse théorique

o auto-stabilisationo complexitéo cardinalitéo …

problème : la modélisation radio

42/47

Evaluation

Problèmes Liens radio

o instabilitéo hétérogénéitéo unidirectionnels

Performances de 802.11 [dhoutaut03]

43/47

Débits TCP

flux TCP vers Internet

44/47

Mobilité – Débit TCP

débit instantané, flux constant vers Internet

45/47

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

46/47

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 »

47/47

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 ?

48/47

49/47

Chapitres de livre Theoleyre, Valois, Auto-organisation de réseaux ad hoc :

concepts et impacts, chap. 5 de Réseaux mobiles ad hoc et réseaux de capteurs, Hermès, 2006, 101-128

Conférences Internationales Theoleyre, Valois, On the Performances of the Routing

Protocols in MANET: Classical versus Self-Organized Approaches, in IFIP Networking, Portugal, 2006

Rivano, Theoleyre, Valois, Capacity Evaluation Framework and Validation of Self-Organized Routing Schemes, in IEEE IWWAN, USA, 2006

Theoleyre, Valois, About the self-stabilization of a virtual topology for self-organization in ad hoc networks, in IEEE SSS, Espagne, 2005

Theoleyre, Valois, Mobility management in multihops wireless access networks, in IFIP PWC, France, 2005

Theoleyre, Valois, Virtual Structure Routing in Ad Hoc Networks, in IEEE ICC, Corée du Sud, 2005

Theoleyre, Valois, A Virtual Structure for Mobility Management in Hybrid Network, in IEEE WCNC, USA, 2004