Upload
eustacia-buisson
View
106
Download
0
Embed Size (px)
Citation preview
Contrôle de topologie et diffusion dans les réseaux ad hoc
David SIMPLOT-RYL
IRCICA/LIFL, Univ. Lille 1CNRS UMR 8022 - INRIA Futurshttp://www.lifl.fr/RD2P
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Plan
Contrôle de topologie et diffusion dans les réseaux ad hoc
1. Introduction et notions de base Types de réseaux ; Familles de protocoles
2. Contrôle de topologie Ajustement de portées ;
Ensembles dominants
3. Diffusion d’information Diminution du nombre
d’émission ; Ajustement
de portées
4. Perspectives derecherche
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Familles de réseaux
Réseau centralisé (à la Wi-Fi ou GSM)accès au réseau via des points d’accès (PA)
hybride
Réseau hybride
Réseau avec PA « étendu » par le ad hoc
ad hoc single hop
Communication point à point (mode ad hoc de Wi-Fi)
centralisé
ad hoc
Réseau ad hocChaque POPS est potentiellement un routeur
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Ad hoc vs centralisé
Bilan énergétiqueEn centralisé
Chaque mobile ne communique qu’avec un point d’accès fixe
En ad hoc On communique moins loin (10 fois moins) et on doit également
relayer les messages des autres mobiles
90% des communications d’un mobile sont pour les autres ou pour les messages de maintenance du réseau !
On consomme donc au moins 10 fois moins en ad hoc
Partage spatial du médiumBande passante/Accès au médium meilleurs en ad hoc
centralisé ad hoc
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Ad hoc vs centralisé (suite)
Partage du médium
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Ad-hoc vs centralisé (suite)
Connectivité au « réseau »En centralisé
Infrastructure « point d’accès » recouvrante Coûteux mais connexion au réseau assurée dans la couverture
En ad hoc La connexion au réseau est trop aléatoire ? « Il faut une densité monstrueuse ! »
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Connexité du réseau
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Connexité du réseau (suite)
Nombre d’objets par zone de communication (densité)
Pro
babi
lité
de c
onne
xité
du
rése
au (
%)
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Ad-hoc vs centralisé (suite)
Connectivité au « réseau »En centralisé
Infrastructure « point d’accès » recouvrante Coûteux mais connexion au réseau assurée dans la couverture
En ad hoc La connexion au réseau est trop aléatoire ? « Il faut une densité monstrueuse ! » Pour une portée de 10 m :
Seulement un objet tous les 21 m²
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Familles de protocoles
CentralisésLe comportement des mobiles est « dirigé » par un objet central
Protocoles locauxLe mobile adapte son comportement en fonction de son environnement localBon comportement face à la mobilité
Protocoles globauxLe mobile est capable de ramener à lui les informations sur le réseauIl est capable d’avoir une vision globale ou quasi-globale du réseauSimilaire au centralisé
Com
plex
ité d
u m
obile
RFID tags
Smart sensor PDALaptop
Protocoles centralisés
Protocoles locaux
Protocoles globaux
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Plan
Contrôle de topologie et diffusion dans les réseaux ad hoc
1. Introduction et notions de base Types de réseaux ; Familles de protocoles
2. Contrôle de topologie Ajustement de portées ;
Ensembles dominants
3. Diffusion d’information Diminution du nombre
d’émission ; Ajustement
de portées
4. Perspectives derecherche
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Ajustement de portées
Modèle énergétique :Pour émettre à une distance d
E(d) = d
2, le facteur d’atténuation du signal
Diviser la portée de chaque mobile par 2, c’est au moins 4 la durée de vie du réseau…
Uniform transmission range = 100 m
Connected graph
Range = 67 mConnected graph
Range = 44 mNon-connected graph
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Ajustement de portées
C’est le problème de l’assignement de portée :Il faut définir une fonction r: V[0,R] telle que le graphe induit par r est connexe
C’est un problème NP-Complet [Clementi, Ferreira]
Exemple de protocole probabiliste :Chaque nœud u choisit la plus petite portée p telle que Np(u)k
avec k=14 par exemple
Pb. la connexité n’est pas garantie et il est facile de construire un contre-exemple
Il y a tout aussi simple et plus sûr…
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Utiliser des sous graphes connexes
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Graphe RNG (Relative Neighborhood Graph)
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Ajustement de portées
Solution triviale :Ajuster la portée de chaque nœud à la distance maximale d’un voisin RNG, LMST (local) ou MST (global)
Algorithme gloutonMTCP [Wieselthier 2000]
IPTCP et ses variantes locales [Simplot-Ryl 2003]
IPTCPMTCP
1-LIPTCP 1-LMTCP
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Ensembles dominants
Objectifs :Désigner un sous-ensemble des nœuds qui serve de « backbone » pour les autres nœuds
Applications :Mettre inactifs ou en semi-veille le plus de nœuds possible dans un réseau de capteurs
Définition :Un ensemble E est dominant ssi tout nœud est soit
membre de E voisin d’un nœud de E
On cherche généralement des ensembles dominants connexes (CDS pour Connected Dominating Sets)
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Ensemble dominants Wu & Dai
(Version simplifiée)
Chaque nœud possède une priorité (e.g. son ID)Un nœud n’est pas dominant ssi
L’ensemble de ses voisins de plus haute priorité est connexe et « couvre » tous ses voisins
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Variante appliquée aux réseaux de capteurs
On change la notion de « couverture »On utilise la batterie restante comme prioritéOn obtient un Connected Area Dominating Set
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Plan
Contrôle de topologie et diffusion dans les réseaux ad hoc
1. Introduction et notions de base Types de réseaux ; Familles de protocoles
2. Contrôle de topologie Ajustement de portées ;
Ensembles dominants
3. Diffusion d’information Diminution du nombre
d’émission ; Ajustement
de portées
4. Perspectives derecherche
Simplot-Ryl - Contrôle de topologie …2 mars 2004
2. Diffusion d’information
Objectif de la diffusion (broadcast) Envoyer une information à tous les nœuds du réseaux
ou à une partie du réseauÀ une certaine distance « en sauts » dans le réseau
Utilisation du TTLÀ une zone géographique
Geocasting
Application :« advertising »
i.e. publication de servicesRequêtes de servicesDécouverte de routes
En centralisé : calcul d’un arbre recouvrant diffusionEn local : inondation arbre recouvrant
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Blind flooding (1/2)
Inondation aveugleChaque message de broadcast émis possède un numéro de séquence unique pour chaque diffusion
(SN pour sequence number)Chaque nœud possède une table de broadcast (BT) pour stocker les SN déjà rencontrés
Protocole :Un nœud désirant initier le broadcast :
génère un SN (généralement ID+cpt) Envoie le message à ses voisins avec ce SN (+ éventuellement un TTL) Enregistre dans sa BT ce SN
Un nœud recevant un message avec un SN donné Vérifie que ce SN n’est pas dans sa BT sinon paquet droppé Vérifie éventuellement que la TTL != 0 sinon paquet droppé Envoie ce message à ses voisins Enregistre ce SN dans sa BT
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Blind flooding (2/2)
PourAlgorithme simple à implémenter
Sur MAC idéale, 100% des nœuds sont atteints
ContreBeaucoup de messages envoyés
Sur MAC réelle, beaucoup de collisions Nb. en diffusion, pas de RTS/CTS
Les messages peuvent être redondants :
SAB
C
DE
S émet (A, B, C et E reçoivent)
A, B et E réémettent
C aussi
D réémet
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Diffusion
Démo
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Optimisation de la diffusion
Diminuer le nombre de nœud émettant le message de diffusionCritère SRB = Saved ReBroadcast= % de nœuds ayant reçu le message mais qui n’ont pas réémisPlus le SRB d’un protocole est grand, mieux c’est
Économie d’énergie Pour le blind flooding : SRB = 0%
Garantir la couverture du réseauCritère RE = REachability= % de nœuds atteignables effectivement atteintsPlus le RE d’un protocole est grand, mieux c’estEn dessous de 90%, le protocole est considéré comme défaillant
Pour le blind flooding avec MAC idéale : RE = 100%
Autres critères :Connaissances requises par le protocole
Localité, système de positionnement, distance entre les nœuds, etc.Latence de la diffusion
Temps moyen pour que chaque nœud obtienne l’informationDistorsion
Nombre de sauts effectué par le message / distance « en sauts » avec la source Peut être important pour la découverte de route
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Optimisation
Diminuer le nombre de retransmissionsPar exemple en utilisant les ensembles dominants
Pb. on pénalise toujours les mêmes nœuds…
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Optimisation de la diffusion (suite)
MPR : Multipoint Relay Flooding Protocol [Qayyum et al. 2002]
SRB ~ 50 %, RE > 95 % (densité moyenne aux alentours de 15)
Courtesy to Laurent Viennot
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Optimisation basée sur la distance
[Tseng et al. 2002] On fixe un seuil au-delà duquel les nœuds réémettent
InconvénientsLe nœud B n’est pas considéré comme un relais alors qu’il est le seul voisin de A à pouvoir contacter G
Les nœuds C et E eux vont réémettre pour rien…
Il faut une mesure de la distance entre les nœuds
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Optimisation basée sur la distance
Idée : Utiliser un gradient de probabilité plutôt qu’un seuil sur la distance
Inconvénients :Nécessite toujours une mesure de distanceN’empêche pas les retransmissionsinutiles telles que celles de C et E…
Idée : utiliser le voisinage pourcalculer une « distance »
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Changement de distance
On définit la « distance »Pour deux nœuds u et v :
Nb. Ce n’est pas une vraie
distance : (u,v) (v,u)
Dans un réseau dense, est
linéaire avec la distance.
)(
)(\)(),(
uN
uNvNvu
u vN(u)
N(v)\N(u)
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Changement de distances (suite)
RésultatsSuivant différentes formes de gradientsSRB ~ 50 %RE > 95 %
Comparable à MPR [Qayyum et al. 2002]
LocalitéMPR = 2BRP = 1 (…)
Décision de forwardMPR = émetteurBRP = récepteur
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Neighbour Elimination Scheme
[Peng, Lu][Stojmenović]Ne pas émettre immédiatementFaire la liste des voisins non couvertsAu bout d’un timeout, réémettre le message si la liste est non vide
Ce protocole élimine d’office les nœuds E et C qui n’ont pas de voisins non couverts par AOn ne retient que les nœuds qui ont un arc « sortant » de la zone de communication de A
Idée : diminuer le nombre de nœuds en « diminuant le nombre d’arcs »
Simplot-Ryl - Contrôle de topologie …2 mars 2004
RNG Relay Subset flooding protocol
On fait un NES limité aux voisins RNG
Simplot-Ryl - Contrôle de topologie …2 mars 2004
RRS (suite)
Inconvénient :Il faut la distance entre les nœuds (pour le RNG)
Idée : on remplace la distance par une distance reposant sur les voisins :
)()(
)(\)()(\)(),(
vNuN
uNvNvNuNvu
Simplot-Ryl - Contrôle de topologie …2 mars 2004
RRS (suite)
Une bonne résistance à la charge(donc à la mobilité)
Au prix d’une latence plus élevée en raison du NESCes algorithmes ne requièrent ni positionnement ni contrôle de puissance…
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Diminution de la portée
Atténuation du signalPour de petites distances, la puissance reçue diminue avec le carré de la distance
Proposition duale : La puissance nécessaire pour être reçu à une distance d augmente
avec le carré de la distance…
PC = Power Consumption En fait, en raison du multi-chemins (des ondes réfléchies, de la
diffraction, etc.) on a plutôt :
2.)( dkdPC
2.)( dkdPC
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Couche physique (5/7)
D’après Pythagore :-), toutes ces configurations utilisent la même puissance…Physiquement impossible (couche MAC, génération du signal, etc.)On utilise le modèle (validé par expérimentation [Feeney 2002])
Par exemple, on utilisera les modèles=2, c=0 (classique) et =4, c=108
0,2)( ccddPC
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Consommation énergétique
Avec une antenne directionnelle, on dépense moins d’énergie
Proportionnelle à la surface couverte
=angle d’ouverture du faisceau
d=distance à laquelle on désire émettre
c1 et c2 sont des constantes supposées connues
c1 prise en compte du coût de la couche MAC
c2 prise en compte du coût d’orientation du faisceau, signal processing
L’omnidirectionnelle est un cas particulier du directionnel
21)(2
),( ccddPC
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Broadcast Incremental Power (BIP)
Caractéristiques de BIP: Wieselthier et al. (2000) Construction d’un arbre de diffusion depuis un mobile
Prend en compte le fait que les antennes sont omnidirectionnelles
Meilleur algorithme connu Centralisé !
A
B
C
DS
A
B
C
DSBIP
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Algorithmes locaux
RBOP (LBOP) [Cartigny et al. 2003]Neighbour Elimination Scheme limité aux voisins RNG (LMST)
comme pour RRS
avec ajustement de portée au voisin RNG le plus éloigné
Pb. on a tendance à toujours minimiser la portée de retransmission
La constante c dans le modèle énergétique peut être pénalisante…
En fait, il existe un rayon de retransmission optimal :
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Target Radius Based Protocol (TRBP)
Choix du rayon d’émission - E(r) = r α + c (α ≥ 2, c ≥ 0)
α est pénalisant avec un r trop grandC est pénalisant avec un r trop petit
→ Minimiser le rayon n’est pas toujours la meilleure solution→ Il existe un rayon cible Rt optimal pour chaque nœud
Notre protocole :1. Adapter la topologie pour se rapprocher de ce rayon optimal,2. sélectionner des relais dans le réseau,3. attacher chaque nœud passif à un relais.
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Target Radius Based Protocol (TRBP)
1. Contrôle de topologie Calcul d’un sous-graphe connexe G’=(V,E’) e.g. RNG ou LMST Chaque nœud adapte son rayon
2. Choix de relais : Calcul d’un ensemble dominant
3. Attachement de chaque nœud passif au relais le plus proche
Rayon cible = 65Rayon unitaire = 100
Nœud dominant
Nœud passif
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Target Radius Based Protocol (TRBP)
Résultats expérimentaux – Contrôle de topologie
Il est possible de contrôler la distance entre voisins dominants.
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Target Radius Based Protocol (TRBP)
Résultats expérimentaux – Economie d’énergie (Densité de 50)
RBOP (2003)
BIP (2000)
LBOP (2003)
Minima de TRBP
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Target Radius Based Protocol (TRBP)
Résultats expérimentaux – Economie d’énergie
Surcoût de RBOP 121%
Surcoût de TRBP avec le LMST29%
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Localized BIP - Principe
Principe de fonctionnement
1. Le nœud source applique BIP dans son voisinage à deux sauts,
2. Le paquet est émis avec les instructions pour chaque voisin,
3. Les voisins appliquent le même schéma en tenant compte des instructions reçues.
L’arbre obtenu est différent de celui de BIP, mais suffisamment proche
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Localized BIP - Principe
S
A
B
C
E
D
F
G
Graphe de base
S
A
B
C
E
D
F
Arbre de S
E
D
F
G
Arbre de E
Exemple d’application S applique BIP dans son voisinage à deux sauts et transmet ses choix E fait de même en tenant compte des instructions reçues
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Localized BIP - Principe
A
D
C
S
B
Graphe de base
A
D
C
S
B
Arbre de diffusion
Pourquoi le voisinage à deux sauts? S ne prend pas D en compte C ne doit pas relayer
→ D n’est pas atteint
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Localized BIP - Principe
Problèmes de couverture A choisit F pour toucher G B choisit E pour toucher G
BA
CE
G
FD
Graphe de base
BA
E
G
FD
Arbre de A
BA
CE
G
F
Arbre de B
→ Ajout du NES sur un sous-ensemble de voisins
(LMST ou RNG)
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Performances
Comparaison avec d’autres protocoles de diffusionBIP (Algorithme centralisé d’origine)
Wielselthier et al. 2000
LBOP (NES sur les voisins LMST avec ajustement de portée) Ingelrest et al. 2003
TR-LBOP (LBOP avec utilisation d’un rayon cible) Ingelrest et al. 2004
Observation de divers paramètresDiffusion (taux de couverture)
SRB (Saved Rebroadcast)
EER (Expanded Energy Ratio)
Latence
Simplot-Ryl - Contrôle de topologie …2 mars 2004
PerformancesTaux de couverture
A partir d’une densité de 40, la diffusion devient totale sans NES
Simplot-Ryl - Contrôle de topologie …2 mars 2004
PerformancesEnergie dépensée
BIP
LBIP sans NES
Densités faibles
Simplot-Ryl - Contrôle de topologie …2 mars 2004
PerformancesEnergie dépensée
BIP et LBIP
TR-LBOP
LBOP
Réseaux denses
Simplot-Ryl - Contrôle de topologie …2 mars 2004
PerformancesTaux de nœuds inactifs
LBOP
Simplot-Ryl - Contrôle de topologie …2 mars 2004
PerformancesLatence
LBIP possède une latence plus faible que les autres
TR-LBOP
LBOP
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Plan
Contrôle de topologie et diffusion dans les réseaux ad hoc
1. Introduction et notions de base Types de réseaux ; Familles de protocoles
2. Contrôle de topologie Ajustement de portées ;
Ensembles dominants
3. Diffusion d’information Diminution du nombre
d’émission ; Ajustement
de portées
4. Perspectives derecherche
Simplot-Ryl - Contrôle de topologie …2 mars 2004
4. Perspectives de recherche
Protocoles de diffusion spécialisésPour la découverte de routes
Équité entre les nœuds (dominating sets ) Durée de vie des routes (BRP, RRS )
Pour la construction d’arbres recouvrants (spanning trees) Interrogation de population de tags, de capteurs
Pour la dissémination d’information…
Lecteur
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Dissémination d’informations
réplica dans le cache
Information source
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Perspectives de recherche (suite)
Contrôle de topologieÉviter la création de liens critiques
Facteur important pour la robustesse des liens entre deux nœuds
Réseaux hybrides Équité/activity scheduling pour les
nœuds prêts des AP
hybride
Simplot-Ryl - Contrôle de topologie …2 mars 2004
Bibliographie
Etat de l’Art sur la diffusionF. Ingelrest, D. Simplot-Ryl, and I. Stojmenovic. Energy-efficient broadcasting in wireless mobile ad hoc network. Chapter in Ressource Management in Wireless Networking. M. Cardei, I. Cardei, and D.-Z. Du. Kluwer. to appear.
Dernière avancée broadcastingF. Ingelrest, D. Simplot-Ryl, and I. Stojmenovic. Target radius over LMST for energy-efficient broadcast protocol in ad hoc networks. In Proc. IEEE Int. Conf. On Communications (ICC’2004), (Paris, France, 2004). to appear.F. Ingelrest, and D. Simplot-Ryl. Localized broadcast incremental power for wireless ad hoc network. submitted.
Contrôle de topologie et broadcasting pour les réseaux de capteurs
J. Carle, and D. Simplot-Ryl. Energy efficient area monitoring by sensor networks. IEEE Computer Magazine 37, 2 (2004), 40-46.F. Ingelrest, D. Simplot-Ryl, and I. Stojmenovic. A dominating sets and target radius based localized activity scheduling and minimum energy broadcast protocol for ad hoc and sensor networks. submitted.
Diffusion et routage dans les réseaux hybridesF. Ingelrest, D. Simplot-Ryl, and I. Stojmenovic. Routing and broadcasting in hybrid ad hoc multi-hop cellular and wireless internet networks. submitted.
Contrôle de topologie et diffusion dans les réseaux ad hoc
David SIMPLOT-RYL
IRCICA/LIFL, Univ. Lille 1CNRS UMR 8022 - INRIA Futurshttp://www.lifl.fr/RD2P