45
Routage et MAC dans les r´ eseaux de capteurs sans fil erard Chalhoub 8 novembre 2010

Réseaux de capteurs sans fil

Embed Size (px)

DESCRIPTION

Routage et MAc des réseaux de capteurs sans fil

Citation preview

Page 1: Réseaux de capteurs sans fil

Routage et MAC dans les reseaux de capteurs sans fil

Gerard Chalhoub

8 novembre 2010

Page 2: Réseaux de capteurs sans fil

Table des matieres

1 Introduction au routage 41.1 Vecteur de distance vs Etat de liens . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.1.1 Vecteur de distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4Etapes d’un protocole vecteur de distance . . . . . . . . . . . . . . . . . . 4

1.1.2 Counting-to-infinity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.1.3 Etat de liens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Etapes d’un protocole etat de liens . . . . . . . . . . . . . . . . . . . . . . 51.1.4 Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Protocoles proactifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2.1 Exemple : OLSR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Interet des MPR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6Echanges periodiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3 Protocoles reactifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3.1 Exemple : AODV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4 Protocoles hierarchiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.5 Protocoles hybrides . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.5.1 Exemple : ZRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10IARP et IERP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10NDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10Exemple d’envoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.6 Protocoles geographiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.6.1 Exemple : LAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2 Les techniques de routage dans les reseaux de capteurs sans fil 142.1 Domaines d’application des reseaux de capteurs sans fil . . . . . . . . . . . . . . 14

2.1.1 Applications militaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.1.2 Applications liees a la securite . . . . . . . . . . . . . . . . . . . . . . . . 152.1.3 Applications environnementales . . . . . . . . . . . . . . . . . . . . . . . . 152.1.4 Applications medicales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.1.5 Applications ecologiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.1.6 Applications de tracabilite et de localisation . . . . . . . . . . . . . . . . . 16

2.2 Contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.2.1 Rappel : differences entre MANET et WSN . . . . . . . . . . . . . . . . . 162.2.2 Criteres a prendre en compte . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3 Preambule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.3.1 Flooding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.3.2 Gossiping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.3.3 Conlusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.4 Classification des protocoles de routage des reseaux de capteurs sans fil . . . . . 17

1

Page 3: Réseaux de capteurs sans fil

2.4.1 Protocoles Data-centric . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17SPIN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17Direct Diffusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.4.2 Procotoles hierarchiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18LEACH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18TEEN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.4.3 Protocoles bases sur la position . . . . . . . . . . . . . . . . . . . . . . . . 18GEAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.4.4 Protocoles bases sur la QoS . . . . . . . . . . . . . . . . . . . . . . . . . . 19SAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19SPEED . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3 Les protocoles MAC dans les WSN 203.1 Exemples de protocoles MAC pour les reseaux de capteurs sans fil . . . . . . . . 20

3.1.1 Economie d’energie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20Overhearing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21Collisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21Idle listening . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21Envois infructueux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21Overhead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.1.2 Protocoles bases sur un sequencement temporel . . . . . . . . . . . . . . . 22TRAMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22FLAMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22E-MAC, L-MAC et AI-LMAC . . . . . . . . . . . . . . . . . . . . . . . . 23

3.1.3 Protocoles bases sur la contention . . . . . . . . . . . . . . . . . . . . . . 24CSMA/CA de la norme IEEE 802.11 . . . . . . . . . . . . . . . . . . . . . 24S-MAC, T-MAC et D-MAC . . . . . . . . . . . . . . . . . . . . . . . . . . 24LPL : B-MAC, WiseMAC, B-MAC+, X-MAC et DW-LPL . . . . . . . . 26

3.1.4 Protocoles hybrides . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27Z-MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27G-MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28Funneling-MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

4 La norme 802.15.4 304.1 Couche physique IEEE 802.15.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.1.1 Activation et desactivation du module radio . . . . . . . . . . . . . . . . . 314.1.2 Indication de la qualite du lien . . . . . . . . . . . . . . . . . . . . . . . . 314.1.3 Test d’occupation du medium ou CCA (Clear Channel Assessment) . . . 314.1.4 Selection du canal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.2 Couche MAC IEEE 802.15.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.2.1 Acces au medium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

Algorithme de CSMA/CA slotte . . . . . . . . . . . . . . . . . . . . . . . 33Algorithme de CSMA/CA non-slotte . . . . . . . . . . . . . . . . . . . . . 34

4.2.2 Les scans, la creation du reseau, les associations et la synchronisation . . 36Les scans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36Creation du reseau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37Association et desassociation . . . . . . . . . . . . . . . . . . . . . . . . . 37Synchronisation avec le beacon du coordinateur . . . . . . . . . . . . . . . 37

4.2.3 Echange de donnees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

Gerard Chalhoub, Clermont Universite 2 Reseaux de capteurs sans fil

Page 4: Réseaux de capteurs sans fil

Echange direct . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38Echange indirect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38Echange en GTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

5 ZigBee 405.1 Couche reseau ZigBee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

5.1.1 Creation de la topologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.1.2 Allocation des adresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

Allocation d’adresses hierarchiques . . . . . . . . . . . . . . . . . . . . . . 41Allocation d’adresses aleatoires . . . . . . . . . . . . . . . . . . . . . . . . 42

5.1.3 Routage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42Routage hierarchique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5.2 Couche application ZigBee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

Gerard Chalhoub, Clermont Universite 3 Reseaux de capteurs sans fil

Page 5: Réseaux de capteurs sans fil

Chapitre 1

Introduction au routage

Les reseaux mobiles ad hoc MANET : ensemble d’entites mobiles communicant en sans filsans aucune infrastructure pour gerer le reseau. Il n’y a pas la notion de routeur ou passerelledediee. Tous les nœuds sont des routeurs. Ce type de reseaux est souvent represente par ungraphe de noeuds relies entre-eux par des aretes, G (V, E).

Routage : trouver un chemin pour envoyer un message d’un nœud vers une destination seloncertains criteres. Parmi les defis a lever par les protocoles de routage :

– portee limitee (nombre de voisins),– mobilite (changement de topologie),– interferences,– liens instables.

1.1 Vecteur de distance vs Etat de liens

Les protocoles de routage sont regroupes sous 2 grandes familles : vecteur de distance etetat de liens.

1.1.1 Vecteur de distance

Les echanges se limitent au voisinage direct. Chaque nœud maintient une table de vecteurde distance (distance = cout, vecteur = direction) qui lui indique les nœuds atteints via sesvoisins avec le cout de chaque chemin. Un nœud diffuse son DV periodiquement ou quand il lemet a jour.

Etapes d’un protocole vecteur de distance

1. calculer le cout de chaque lien avec ses voisins directs,

2. echanger ceci avec les voisins uniquement,

3. mettre a jour sa table de routage en fonction des tables des voisins.

Les informations echangees :– chaque nœud envoie periodiquement a ses voisins :

– le nombre de sauts qui le separe d’une destination donnee,– le prochain saut vers cette destination .

– rajoute les routes directement dans la table de routage.

4

Page 6: Réseaux de capteurs sans fil

1.1.2 Counting-to-infinity

A-B-C-D, quand A est mort, B recoit une information de C indiquant que A est a deuxsauts de C, mais cela en passant par B, mais B ne le sait pas. C envoi son DV a B, B detecteque C peut atteindre A en 2 sauts, ainsi lui met a jour son DV en indiquant qu’il peut atteindreA en 3 sauts, et ainsi de suite jusqu’a arriver a l’infini.

Une solution sera de ne pas envoyer le vecteur de distance de A a B parce que C passe parB pour atteindre A. Une autre solution sera de rajouter un numero de sequence comme fait leprotocole DSDV.

1.1.3 Etat de liens

Echanges periodiques avec tout le reseau. Chaque nœud informe tout le reseau de sa listede voisins, ainsi tous les nœuds sont capables de construire la carte du reseau en considerantuniquement les liens bidirectionnels. La construction de carte du reseau permet a un nœud deconstruire une table de routage en appliquant un algorithme de plus court chemin sur la cartecomme Dijkstra.

Etapes d’un protocole etat de liens

1. connaıtre les voisins directs a l’aide des HELLO,

2. donner un cout a chaque lien,

3. diffuser cette information a tout le reseau,

4. appliquer un algorithme pour calculer les chemins vers toutes les destinations du reseau.

Les informations echangees :– chaque nœud envoie des informations consernant :

– ses liens avec ses voisins,– l’etat de chaque lien .

– ces informations sont diffusees a tous les nœuds du reseau,– chaque nœud calcule sa table de routage en se basant sur ces informations.

1.1.4 Dijkstra

Dijkstra (prononce dikstra) permet de trouver le plus court chemin a partir d’un nœuddonne dans le graphe pour atteindre les autres nœuds. Les etapes a suivre sont les suivantes :

1. on demarre du noeud source et on considere que le cout vers tous les autres noeuds vaut∞,

2. on commence par marquer les couts des arretes qui sortent du nœud,

3. on choisit ensuite comme prochain saut le nœud avec le cout le plus petit,

4. on continue a partir du nœud choisi et on marque le cout cumule pour atteindre les nœudsdirectement lies a ce dernier,

5. on revient a l’etape 3 jusqu’on aura atteint l’ensemble des nœuds.

1.2 Protocoles proactifs

Les routes pour l’ensemble des destinations du reseau sont mises a jour periodiquement. Unevision globale du reseau est toujours disponible.

Avantage(s) :

Gerard Chalhoub, Clermont Universite 5 Reseaux de capteurs sans fil

Page 7: Réseaux de capteurs sans fil

A

2

159

10

11

6

9

14

7

C

F

D

E

B

Fig. 1.1 – Un exemple d’un graphe.

Nœud en cours B C D E F

A 7/A 9/A - 14/A -B 7/A 9/A 22/B 14/A -C 7/A 9/A 20/C 11/C -E 7/A 9/A 20/C 11/C 20/E

Tab. 1.1 – Dijkstra applique au graphe de la figure 1.1.

– diminue le delai avant d’envoyer un message.Desavantage(s) :

– le trafic de maintenance surcharge le reseau,– pas pratique sous forte mobilite.

1.2.1 Exemple : OLSR

Optimized Link State Routing protocol. Projet HYPERCOM du laboratoire francais INRIA.Les noeuds echangent uniquement une sous-partie de leurs voisins : les MPR (Multi-PointRelay). Ce sont les nœuds qui permettent d’atteindre l’ensemble des voisins a deux sauts.

Ceci diminue la surcharge due a la diffusion a l’ensemble des voisins (un nœud envoie lesmessages de donnees uniquement aux MPR), et diminue la taille des echanges des listes desvoisins en se limitant aux MPR. Chaque nœud diffuse a l’ensemble du reseau la liste de nœudsl’ayant elu comme MPR (messages TC).

Interet des MPR

Innondation sans MPR : un nœud retransmet un message si et seulement si il ne l’a pas dejarecu.

Innondation avec MPR : un nœud retransmet un message si et seulement si il ne l’a pas dejarecu et il vient de le recevoir d’un nœud dont il est MPR.

Echanges periodiques

– Des messages HELLO avec les voisins a un saut. Ces messages contiennent la liste desvoisins a un saut qui permettent de choisir les MPR.

Gerard Chalhoub, Clermont Universite 6 Reseaux de capteurs sans fil

Page 8: Réseaux de capteurs sans fil

Fig. 1.2 – OLSR et les MPR. (source : wiki.uni.lu/secan-lab/graphics/olsr02.gif)

– Des messages TC (Topology Control) pour echanger la liste des nœuds l’ayant elu commeMPR. Ces messages permettent de construire une image du reseau avec tous les nœudset un sous ensemble de liens.

1.3 Protocoles reactifs

Contrairement au mode proactif, les routes sont etablies a la demande. Une requete dedecouverte de route vers une destination donnee est propagee sur le reseau quand le nœud abesoin de lui envoyer un message.

Avantage(s) :– Diminue la surcharge du reseau, il n’y a pas de trafic periodique d’entretient des tables

de routage a propager sur le reseau.Desavantage(s) :

– Plus de delai avant l’envoi d’un message en attendant la decouverte d’une route,– Risque de saturation a cause d’innondations multiples.

1.3.1 Exemple : AODV

Ad hoc On-demande Distance Vector.Des messages HELLO sont echanges avec les voisins a un saut pour surveiller les liens avec

ces derniers. Au bout de 4 messages HELLO non recus d’un voisin, le lien est considere perdu.Un nœud qui cherche a envoyer un message a une destination dont il ne connaıt pas le

chemin envoie une RREQ Route REQuest en broadcast. A chaque saut intermediaire la routevers la source est construite pour que le nœud ayant la reponse puisse retransmettre la reponseen unicast. Chaque nœud intermediaire rajoute son identite sur le chemin.

Un nœud n’ayant pas recu la requete avant, ne connaıt pas la destination et n’est pas lui-meme la destination, envoie le message a son tour en broadcast. Sur le chemin de retour, tousles nœuds intermediaires sont capables de stocker le chemin vers la destination.

Le chemin le plus court est choisi si plusieurs RRESP Route RESPonse sont recues. Leschemins dans la table de routage ont une duree de vie.

Si une coupure a eu lieu sur le chemin, une RERR Route ERRor est renvoyee a la sourceet les nœuds intermediaires suppriment cette route de leurs tables de routage respectives. La

Gerard Chalhoub, Clermont Universite 7 Reseaux de capteurs sans fil

Page 9: Réseaux de capteurs sans fil

source declenche une nouvelle RREQ.

HELLO

RREQ

RREP

Data

RERR

S 1 2 D

Fig. 1.3 – Echanges de trames avec AODV.

1.4 Protocoles hierarchiques

Les protocoles hierarchiques ont ete proposes pour reduire la taille des tables de routage dansles reseaux tres larges. Ceci en decoupant le reseau en regions. Chaque region est connectee aune autre region a travers un ou plusieurs nœuds. Ce decoupage reduit la taille des tables deroutage parce qu’elles ne contiennent que les nœuds de la region du nœud.

Fig. 1.4 – Configuration plate. (source : http ://ntwebresel-ler.com/html/how routing algorithms work.html)

1.5 Protocoles hybrides

Les protocoles hybrides sont utulises dans un reseau decoupe en zone. Ils emploient unprotocole proactif dans la zone et un protocole reactif pour les communications inter-zones.

Gerard Chalhoub, Clermont Universite 8 Reseaux de capteurs sans fil

Page 10: Réseaux de capteurs sans fil

Destination Prochain saut Cout

B B 1C C 1D B 2E B 3F B 3G B 4H B 5I C 5J C 6K C 5L C 4M C 4N C 3O C 4P C 2Q C 3

Tab. 1.2 – Table de routage de A.

Fig. 1.5 – Configuration hierarchique. (source : http ://ntwebresel-ler.com/html/how routing algorithms work.html)

Destination Prochain saut Cout

B B 1C C 1Region 2 B 2Region 3 C 2Region 4 C 3Region 5 C 4

Tab. 1.3 – Table de routage de A.

Gerard Chalhoub, Clermont Universite 9 Reseaux de capteurs sans fil

Page 11: Réseaux de capteurs sans fil

1.5.1 Exemple : ZRP

Avec ZRP Zone Routing Protocol les requetes de routes sont plus rapides (par rapport aun protocole reactif) car les informations des zones sont deja disponibles grace au protocoleproactif. Il est plus simple de garder une vision de la topologie d’une zone que pour le reseauentier.

Chaque nœud definit sa propre zone. Les nœuds a 3 sauts du nœud par exemple.

Fig. 1.6 – Zone de S. (source : Nicklas Beijar, Zone Routing Protocol (ZRP))

IARP et IERP

Routage intra-zone IARP IntrA-zone Routing Protocol et routage inter-zone IERP IntEr-zone Routing Protocol.

IARP est un protocole proactif qui echange des messages HELLO pour maintenir la listedes voisins et des routes vers les voisins appartenant a la zone.

A la place des Broadcast, ZRP utilise les Bordercast. Bordercast Resolution Protocol (BRP)utilise les informations fournies par IARP pour atteindre les nœuds periferiques.

NDP

Neighbor Discovery Protocol (NDP) met a jour les tables de IARP, IERP utilise les tablesde IARP, IERP relaie les route requeste avec BRP. BRP utilise les tables de IARP pour orienterles requetes.

Si la destination est dans la zone, la route est donnee par IARP, sinon une requete est faitepar IERP. Une requete de route est envoyee aux nœuds periferiques avec BRP. Et ceci jusqu’aatteindre la destination.

Deux techniques pour renvoyer la reponse en unicast :– Les nœuds intermediaires rajoutent leurs adresses dans la requete, comme fait AODV.– Les informations concernant le prochain saut sont stockees dans les nœuds, ceci evite de

surcharger les trames de requete et de reponse.BRP atteint les nœuds periferiques avec un multicast, moins couteux qu’un broadcast.Quand la zone est limitee a un saut, ZRP devient un protocol reactif. Le choix de la taille

de la zone doit etre fait selon le degre de mobilite.

Gerard Chalhoub, Clermont Universite 10 Reseaux de capteurs sans fil

Page 12: Réseaux de capteurs sans fil

Fig. 1.7 – Architecture de ZRP. (source : Nicklas Beijar, Zone Routing Protocol (ZRP))

Exemple d’envoi

Fig. 1.8 – Zone de S. (source : Nicklas Beijar, Zone Routing Protocol (ZRP))

S veut envoyer un message a X, il ne trouve pas X dans sa zone avec IARP, il envoie unerequete aux nœuds periferiques avec BRP. I ne le trouve pas dans sa zone, I envoie une requetea ses nœuds periferiques.

T recoit la requete et trouve X dans sa zone. T rajoute le chemin de lui vers X au cheminconstruit dans la requete et renvoie une reponse avec le chemin complet.

1.6 Protocoles geographiques

Dans un protocole geographique, le but est de reduire la zone de diffusion de la requete deroute pour diminuer la surcharge du reseau due au trafic de controle des protocoles de routage.La position est donnee grace a un systeme de GPS.

Gerard Chalhoub, Clermont Universite 11 Reseaux de capteurs sans fil

Page 13: Réseaux de capteurs sans fil

Fig. 1.9 – Zone de I. (source : Nicklas Beijar, Zone Routing Protocol (ZRP))

1.6.1 Exemple : LAR

Avec le protocole LAR Location-Aided Routing un nœud estime la position de son destina-taire en fonction de son ancienne position a un instant donne et sa vitesse. Ceci donne une zoned’un rayon donne (calcule grace a la vitesse du nœud : R = vitesse ∗ (t1–t0).) et de centre laderniere position connue. Cette zone est appelee expected zone (zone susceptible).

Zone de requete : elle est plus grande que la zone susceptible. Ce sont uniquement lesnoeuds appartenant a cette zone qui diffusent la requete de route. La raison est que si la sourcen’appartient pas a la zone estimee, elle doit atteindre la zone en passant par des noeuds quin’appartiennent pas a la zone susceptible.

Plus la zone de requete est grande plus la probabilite de trouver une reponse est grandemais plus le trafic de controle est grand.

Fig. 1.10 – Zone de requete et zone d’estimation : source a l’exterieure. (source : Young-BaeKo and Nitin H. Vaidya, Location-Aided Routing (LAR) in mobile ad hoc networks)

Deux methodes sont possible pour effectuer la decouverte de route :– La requete de route inclut les coordonnees des 4 points qui constituent la zone de requete,

si un nœud recoit la requete il diffuse le message uniquement s’il est dans la zone. Quand

Gerard Chalhoub, Clermont Universite 12 Reseaux de capteurs sans fil

Page 14: Réseaux de capteurs sans fil

Fig. 1.11 – Zone de requete et zone d’estimation : source a l’interieure. (source : Young-Bae Koand Nitin H. Vaidya, Location-Aided Routing (LAR) in mobile ad hoc networks)

D recoit le message il inclut sa position actuelle dans la reponse. La vitesse moyenne oumax etant connue.

– La source inclut la distance Ds entre elle la destination et la derniere position connue dela destination. Quand un noeud intermediaire recoit la requete il la diffuse si et seulementsi : a ∗ Ds + b ≥ Di. Ensuite, il remplace la distance dans la requete par Di. De cettefacon un noeud forward la requete si et seulement si il est plus proche de la destiantionque celui de qui il a recu la requete.

Pour inclure une estimation d’erreur sur la position connue, dans la premiere methodeR = erreur+ v ∗ (t1–T0). Dans la deuxieme methode les valeurs de a et b sont fixees en fonctionde l’erreur estimee. Les noeuds intermediaires peuvent recalculer la zone de requete avant dediffuser la requete.

La table de positions : une entree par nœud dont la position est connue. Quand un nœudsouhaite connaıtre la position d’un autre nœud il verifie sa table de positions, s’il ne trouve pasune entree correspondante, il diffuse sur le reseau une requete de route. Les nœuds ecoutent lesreponses et mettent a jour leurs tables.

Gerard Chalhoub, Clermont Universite 13 Reseaux de capteurs sans fil

Page 15: Réseaux de capteurs sans fil

Chapitre 2

Les techniques de routage dans les

reseaux de capteurs sans fil

Un nœud capteur est constitue de 4 entites essentielles a son fonctionnement :– une entite de captage (son, temperature, humidite, intensite, vibration, pression, mouve-

ment, pollution...),– un micocontrolleur,– une source d’energie,– une antenne de communication.Un luxe sera de trouver un GPS ou un moyen de mobilite.

Fig. 2.1 – Un nœud capteur. (source : Classification and comparision of routing protocols inwireless sensor networks, UbiCC Journal – Volume 4)

2.1 Domaines d’application des reseaux de capteurs sans fil

Nous pouvons citer les domaines suivants : militaire, environnemental, domestique, sante,securite, ecologie, tracabilite, etc. Des exemples d’applications potentielles dans ces differentsdomaines sont exposes ci-dessous.

14

Page 16: Réseaux de capteurs sans fil

WAN

Reseau de capteurs sans fil

Reseau

Unite de controle

Passerelle

Fig. 2.2 – Un exemple d’un reseau de capteurs sans fil.

2.1.1 Applications militaires

Le deploiement rapide, l’auto-configuration et la tolerance aux pannes des reseaux de cap-teurs sont des caracteristiques qui font de ce type de reseaux un outil appreciable dans un teldomaine. Deploiement sur un endroit strategique ou difficile d’acces, afin de surveiller toutesles activites des forces ennemies ou d’analyser le terrain avant d’y envoyer des troupes (par ladetection d’agents chimiques, biologiques ou de radiations, par exemple).

2.1.2 Applications liees a la securite

Diminuer considerablement les depenses financieres consacrees a la securisation des lieux eta la protection des etres humains tout en garantissant des resultats plus fiables.

(i) la detection des alterations dans la structure d’un batiment, suite a un seisme ou auvieillissement, par des capteurs integres dans les murs ou dans le beton,

(ii) la surveillance des mouvements afin de constituer un systeme de detection d’intrusionsdistribue. L’aspect distribue rend plus complexe la possibilite de mettre hors d’usage ce systemede surveillance.

2.1.3 Applications environnementales

(i) la dispersion de thermo-capteurs a partir d’un avion sur une foret pour signaler uneventuel debut d’incendie dans le champ de captage,

(ii) le semis de nœuds capteurs en meme temps avec les graines dans les champs agricolespour pouvoir identifier les zones seches et rendre l’irrigation plus efficace,

(iii) le deploiement de nœuds capteurs sur les sites industriels, les centrales nucleaires ou dansles raffineries de petrole pour detecter des fuites de produits toxiques (gaz, produits chimiques,elements radioactifs, petrole, etc.) et alerter les utilisateurs dans un delai suffisamment courtpour permettre une intervention efficace.

2.1.4 Applications medicales

Surveillance permanente des patients et une possibilite de collecter des informations physio-logiques de meilleure qualite facilitant ainsi le diagnostic de maladies grace a des micro-capteurs

Gerard Chalhoub, Clermont Universite 15 Reseaux de capteurs sans fil

Page 17: Réseaux de capteurs sans fil

qui pourront etre ingeres ou implantes sous la peau.(i) les micro-cameras qui peuvent etre ingerees et sont capables, sans avoir recours a la

chirurgie, de transmettre des images de l’interieur d’un corps humain,(ii) la creation d’une retine artificielle composee d’une centaine de micro-capteurs pour

ameliorer la vision de l’œil.

2.1.5 Applications ecologiques

L’integration de plusieurs micro-capteurs dans le systeme de climatisation et de chauffagedes immeubles. Ainsi, la climatisation ou le chauffage ne sont declenches qu’aux endroits ou il ya des personnes presentes et seulement si c’est necessaire. Le systeme distribue peut aussi main-tenir une temperature homogene dans les pieces. Utilisee a grande echelle, une telle applicationpermettrait probablement de reduire la demande mondiale en energie.

2.1.6 Applications de tracabilite et de localisation

Suite a une avalanche il est necessaire de localiser les victimes enterrees sous la neige enequipant les personnes susceptibles de se trouver dans des zones a risque par des capteurs.Ainsi, les equipes de sauvetage peuvent localiser plus facilement les victimes.

Contrairement aux solutions de tracabilite et de localisation basees sur le systeme de GPS(Global Positionning System), les reseaux de capteurs peuvent etre tres utiles dans des endroitsclos comme les mines par exemple.

2.2 Contraintes

Un WSN ideal doit passer a l’echelle, etre robuste, econome en energie, offrir des perfor-mances reseaux raisonnables en terme de delai et taux de perte, etre fiable, pas chere et nedemande pas de maintenance a long terme. Un peu trop exigeant ! !

Trois limitations essentielles : energie, calcul et portee.

2.2.1 Rappel : differences entre MANET et WSN

1. WSN collecte de donnees, MANET plus orientes calcul distribue,

2. nombre de nœuds dans WSN plus grand que celui des MANET,

3. WSN limitations en calcul et en energie, MANET sont rechargeable et plus puissants,

4. WSN deploye de facon ad hoc mais peu mobile alos que MANET sont mobiles,

5. debit limite en WSN par rapport au MANET.

2.2.2 Criteres a prendre en compte

1. Tolerance aux pannes : maintenir l’activite du reseau meme si des nœuds sont morts (piles,panne, conditions physiques, etc.),

2. Passage a l’echelle : dixaines, centaines et meme des milliers de nœuds,

3. Couts : n*1000*cout d’un nœud,

4. Conditions geographiques : sous marins, zone de guerre, forets, barrage, industrie, etc.,

5. Consommation energetique : on consomme moins en faisant du multi-sauts,

6. Collecte des mesures : periodique (continue), sous evenement, a la demande, hybride,

7. Agregation de donnees : min, max, moyenne (moins de transmission),

Gerard Chalhoub, Clermont Universite 16 Reseaux de capteurs sans fil

Page 18: Réseaux de capteurs sans fil

8. Qualite de service : duree de vie, delai, taux de perte, latence, energie. . .

9. Surcharge : trafic de controle, calcul,

10. Deploiement du reseau : aleatoire, predefinit, etc.

2.3 Preambule

2.3.1 Flooding

Pour prendre en compte les faibles capacites de calcul des nœuds capteurs, les protocolesde routage les plus simples sont ceux qui sont bases sur le flooding. En revanche, ceci creeune duplication de paquets, les nœuds recoivent plusieurs fois le meme paquet. Les nœuds neprennent pas en compte la limitation energetique.

2.3.2 Gossiping

Limite la diffusion en choisissant un seul nœud voisin pour lui envoyer le message. Non priseen compte de la limitation energetique et reception multiple de la meme donnee. Possibilite detourner en boucle.

2.3.3 Conlusion

Necessite d’un protocol de routage.

2.4 Classification des protocoles de routage des reseaux de cap-

teurs sans fil

– Hierarchique ou plat : dans plat tous les nœuds sont du meme niveau, type et capa-cite, hierarchique certains sont plus puissants que d’autres, certains peuvent avoir destaches que les autres n’ont pas. On parle de cluster dans hiearchique et chef de cluster(aggregation des donnees provenant d’un meme cluster).

– Data centric : requete de collecte d’un type de donnees.– Location aware : notion de position et de region, dependance GPS.– Base sur la QoS : taux de perte, delai, latence, consommation.

2.4.1 Protocoles Data-centric

Ces protocoles supposent qu’il est difficile d’avoir des identifiants comme les adresses MACou IP pour pouvoir communiquer entre les nœuds capteurs. Ne demandent pas un mecanismed’adressage. Les informations sont propagees de proche en proche.

Envoient une annonce des donnees avant d’envoyer les donnees elles-memes, les voisins in-teresses demandent les donnees annoncees, les donnees sont ensuite envoyees.

SPIN

Sensor Protocol for Information via Negotiation. Annonce les donnees par des paquets ADV(ADVertise), les nœuds interesses repondent par une REQ (REQuest) et ensuite les donneessont envoyees. Point fort : connaissance se limite au voisinage a un saut.

Ne garantie pas la reception des donnees : si le nœud destinataire ne se trouve pas a porteed’un nœud qui annonce l’envoi, les donnees ne seront jamais transmises.

Gerard Chalhoub, Clermont Universite 17 Reseaux de capteurs sans fil

Page 19: Réseaux de capteurs sans fil

Direct Diffusion

C’est l’inverse de SPIN : les nœuds interesses par une donnee diffusent une requete. Lesnœuds voisins prennent en compte cette requete, repondent en fonction et rediffusent a leurtour la requete.

2.4.2 Procotoles hierarchiques

Construction de clusters (groupe de nœuds) avec un chef par cluster qui se chargera detransmettre les messages generes par son cluster aux autres chefs de clusters pour atteindre ladestination finale. Le choix du chef de cluster (cluster head) est fait soit a tour de role, soitselon le nombre de voisins en considerant comme cluster head le nœud avec le plus de voisins,soit selon le niveau de l’energie residuelle...

LEACH

Low Energy Clustering Hierarchy. 5% des nœuds sont elus pour etre des chefs de clusters.Election periodique des chefs de clusters en fonction du % de nombre de cluster, nombre de tourdepuis lequel le nœud n’a pas ete chef de cluster. TDMA est utilise dans le cluster et CDMAentre les clusters. Aggregation des donnees generees dans un cluster limite la redondance et laconsommation energetique.

Suppose que les chefs de clusters sont capables d’atteindre la station de base qui recoltetout.

TEEN

Threshold sensitive Energy Efficient Network protocol. Transmettre uniquement quand lavaleur detectee est superieure a un certain seuil fixe par le chef de cluster. Ensuite, un nœudne transmet pas la meme donnee tant que sa valeur n’a pas change d’un seuil de variation(aussi fixe par le chef de cluster). TEEN adopte plusieurs niveau de clusters : clusters de chefde clusters.

N’est pas adapte pour la surveillance periodique. Une extension APTEEN (Adaptive Thre-shold sensitive Energy Efficient Network protocol) supporte deux types de generations trafic :periodique et critique (depassement d’un seuil).

La complexite est au niveau de la creation des clusters et la definition des seuils.En consommation energetique TEEN moins qu’APTEEN, et APTEEN consomme moins

que LEACH.

2.4.3 Protocoles bases sur la position

Dans les reseaux de capteurs, on considere que la position du nœud est plus importante queson identite (adresse). Ce type de protocoles considerent que les nœuds connaıssent leur positionrespective et sont capables de connaıtre la position des autres nœuds. Ainsi, cette informationest utilisee pour diriger les messages vers la region dans laquelle se trouve la destination.

GEAR

Geographic and Energy Aware Routing. Ce protocole de routage decoupe le reseau en regions.Chaque nœud connaıt le cout pour atteindre chaque region. L’acheminement des packets suitles etapes suivantes :

Gerard Chalhoub, Clermont Universite 18 Reseaux de capteurs sans fil

Page 20: Réseaux de capteurs sans fil

1. acheminer le paquet jusqu’a la region, en envoyant le paquet au nœud le plus proche dela region parmi ses voisins et ayant le niveau d’energie residuelle le plus eleve (fonctionde distance et d’energie),

2. acheminer le paquet dans la region de destination par une sorte de diffusion si le nombre denœud n’est pas eleve, sinon la region est decoupee en sous-region et le paquet est tranmisindividuellement a chaque sous-region.

Chaque paquet contient la region destination. Chaque nœud connaıt sa position, son energieresiduelle, la position et l’energie residuelle de ses voisins (a la demande). Un lien existe entre2 nœuds quand ils sont a portee et leur niveau d’energie leur permet d’effectuer l’envoi.

2.4.4 Protocoles bases sur la QoS

Dans ce type de protocoles, les performances du reseau sont prises en compte pour garantirun delai de bout-en-bout raisonnable qui repond aux besoins de l’application. C’est surtout lecas des applications indutrielles et militaires.

SAR

Sequential Assignment Routing. Base sur la construction d’arbre a partir des voisins du puits.Les liens de chaque arbre sont choisis en fonction du delai observe et de l’energie residuelle desnœuds. Les donnees sont associees a un niveau de priorite.

La creation des arbres est assez lourde.

SPEED

Une metrique supplementaire par rapport a GEAR : le delai.Se base sur une table de positions. Il estime le delai sur chaque saut en calculant le delai

d’aller-retour (en retranchant le temps de traitement cote recepteur). Le prochain saut est choisiparmi les voisins qui sont plus proches de la destination que le nœud.

Gerard Chalhoub, Clermont Universite 19 Reseaux de capteurs sans fil

Page 21: Réseaux de capteurs sans fil

Chapitre 3

Les protocoles MAC dans les WSN

3.1 Exemples de protocoles MAC pour les reseaux de capteurs

sans fil

Un protocole MAC pour les reseaux de capteurs sans fil doit trouver le bon compromisentre l’economie d’energie, l’aspect temps reel et l’auto-configuration. Dans cette partie, nouspresentons quelques protocoles MAC proposes pour les reseaux de capteurs sans fil presentesselon leur type. Nous avons identifie trois types : les protocoles bases sur un sequencement tem-porel, les protocoles bases sur un evitement de collision probabiliste et les protocoles hybrides.Nous decrivons en resume quelques protocoles MAC representatifs de chacun de ces types. Anoter que ces protocoles sont les plus etudies dans la litterature et non pas forcement les plusperformants : il s’agit de protocoles de base et parfois sujets a optimisation.

3.1.1 Economie d’energie

Les sources de consommation d’energie sur un nœud capteur sont le module radio, le micro-processeur et le capteur. La communication radio est souvent la plus consommatrice parmi lestrois. La consommation d’un capteur varie dans une tres large plage selon son type. Un capteurconsommant beaucoup d’energie est souvent alimente par sa propre source energetique. Nousconsiderons ici que la couche MAC est concernee uniquement par l’utilisation du module radioet du microprocesseur.

Dans un reseau de capteurs, la portee est de l’ordre d’une dizaine de metres dans un milieuclos avec une puissance d’emission de 0 dBm (1 mW ). Avec ce niveau de puissance d’emission,l’energie consommee pour la reception et celle consommee pour l’emission sont quasiment egales.Le tableau 3.1 montre un exemple d’energie consommee pour chaque etat du module radio d’unecarte B2400ZB-tiny.

Un protocole MAC econome en energie essaie d’utiliser le moins souvent possible le moduleradio. Les modules radio peuvent avoir plusieurs niveaux de consommation quand ils ne sontpas en mode emission ou reception, moins le nœud consomme moins il est reactif, c’est pourcela que les differents etats de sommeil existent pour assurer une flexibilite selon le degre dereactivite demande par la couche MAC.

L’utilisation inutile du module provient de 5 sources essentielles : le Overhearing, les colli-sions, le Idle listening, les envois infructueux et les messages de controle.

20

Page 22: Réseaux de capteurs sans fil

Etat Energieconsommee

Emission 26 mA

Receptionou ecoute

29 mA

Veille 15 µA

Sommeil 3 µA

Tab. 3.1 – Energie consommee par etat par le composant radio d’une carte B2400ZB-tiny.

Overhearing

L’overhearing est la reception par un nœud d’une trame qui ne lui est pas destinee. L’energieconsommee pour la reception et le traitement des donnees de cette trame est perdue et sansaucun interet.

Collisions

Les collisions sont a la fois une source de degradation des performances du reseau et de perted’energie. Les pertes de trames a cause des collisions forcent les nœuds a retransmettre le memepaquet plusieurs fois et donc a rester actif pour le repeter et verifier qu’il est bien recu par ladestination. A noter que les retransmissions ne se font que pour les trames envoyees en modeunicast (a un seul destinataire) et avec une demande d’acquittement.

Idle listening

C’est l’attente d’une trame par le module radio. Cela arrive quand il a ete demande a unnœud d’etre eveille mais qu’il ne recoit aucune trame et n’en transmet aucune non plus. Memesi le nœud ne transmet pas et ne recoit pas, le fait que son module radio soit active et pret pourrecevoir consomme autant d’energie que pour la reception.

Envois infructueux

Cela arrive quand un nœud essaie de communiquer avec un autre nœud qui n’est plus acces-sible parce qu’il est en mode sommeil par exemple (ou hors de portee). Le nœud emetteur esten attente d’un acquittement, et il retransmet donc la meme trame plusieurs fois. Il consommede l’energie en le faisant du fait qu’il soit reste en mode transmission et en mode reception pourl’eventuel acquittement.

Overhead

L’Overhead constitue les messages de controle et tout bit utilise pour encapsuler des donneesutiles a l’application. Cet Overhead genere par la couche MAC, a pour but d’assurer le bonfonctionnement de la methode d’acces mais cela amplifie les 4 sources de consommation acontre-temps.

Gerard Chalhoub, Clermont Universite 21 Reseaux de capteurs sans fil

Page 23: Réseaux de capteurs sans fil

3.1.2 Protocoles bases sur un sequencement temporel

Les protocoles MAC appliquant un sequencement temporel decoupent le temps en slots,chaque slot de temps est alloue (localement) a un seul nœud pour lui garantir l’acces au canalafin qu’il puisse transmettre ses donnees. La methode TDMA est un exemple de methode desequencement temporel dans les reseaux sans fil.

Ces protocoles sont generalement economes en energie car ils evitent les collisions, ils limitentle idle listening et le overhearing, et mettent les nœuds en mode sommeil durant les slots detemps reserves aux autres nœuds. De plus, ils garantissent un delai borne de bout-en-bout siun algorithme d’allocation prend en compte les caracteristiques du trafic. En revanche, l’aspectcentralise et le besoin d’une synchronisation rendent ce type de protocoles rigide et non-adaptepour les topologies dynamiques et mobiles.

Par la suite, nous decrivons brievement les protocoles TRAMA, FLAMA, E-MAC, L-MACet AI-LMAC.

TRAMA

TRAMA (TRaffic-Adaptive Medium Access control) divise le temps en slots de temps etse base sur le trafic annonce par les nœuds pour designer les emetteurs et les recepteurs pourchaque slot de temps. Pour ce faire, TRAMA applique trois mecanismes :

– un protocole de voisinage appele NP (Neighbor Protocol) pour echanger la liste des voisinsa un saut entre les nœuds, ce qui permet d’etablir une connaissance des voisins a deuxsauts,

– un protocole d’echange de calendriers appele SEP (Schedule Exchange Protocol) ou chaquenœud annonce ce qu’il a comme trafic a envoyer en precisant les recepteurs concernes,

– un protocole d’election adaptative AEA (Adaptative Election Algorithm) qui choisit lesemetteurs et les recepteurs pour un slot de temps donne en fonction des informationscollectees par NP et SEP.

TRAMA decoupe le temps en alternant des intervalles de temps a acces planifie et des in-tervalles de temps a acces aleatoire. Chaque intervalle est constitue de slots de temps. TRAMAcommence par des intervalles a acces aleatoire pour permettre au reseau de s’etablir. Lesechanges pour la decouverte de voisinage du protocole NP sont effectues durant les intervalles aacces aleatoire. Ces intervalles servent aussi pour permettre aux nouveaux nœuds de rejoindrele reseau. L’envoi de trames de donnees se fait durant les intervalles a acces planifie.

�������

�������

�������

�������

����

Acces planifie Acces aleatoire

Basculement entre actif/inactif

Fig. 3.1 – Decoupage temporel de TRAMA pour un nœud du reseau.

Pour realiser son decoupage temporel, TRAMA a besoin que chaque nœud diffuse son ca-lendrier de trafic et fasse une decouverte de voisinage a deux sauts.

FLAMA

FLAMA (FLow-Aware Medium Access) est propose comme une amelioration de TRAMA.Comme TRAMA, FLAMA divise le temps selon deux modes d’activite : intervalles de temps a

Gerard Chalhoub, Clermont Universite 22 Reseaux de capteurs sans fil

Page 24: Réseaux de capteurs sans fil

acces planifie et intervalles de temps a acces aleatoire. FLAMA a aussi besoin de connaıtre levoisinage d’un nœud a deux sauts et des informations concernant le flux de donnees des voisinsa un saut.

En revanche, FLAMA ne diffuse pas de calendriers de trafic durant les intervalles de temps aacces planifie mais echange durant les intervalles de temps a acces aleatoire des informations parrapport aux flux de donnees lies a l’application. En outre, FLAMA etablit une synchronisationglobale du reseau base sur l’estampillage des trames et une topologie arborescente pour le relaisde donnees.

Pour determiner les emetteurs et les recepteurs concernes par chaque slot de temps lors del’intervalle a acces planifie, FLAMA applique un algorithme plus simple que celui utilise dansTRAMA. Comme TRAMA, FLAMA assure des transmissions sans collision en ne permettantqu’a un seul nœud d’emettre dans un voisinage a deux sauts.

Acces planifie Acces aleatoire

Fig. 3.2 – Decoupage temporel de FLAMA.

FLAMA est plus performant que TRAMA en terme d’economie d’energie et de perte detrames. De plus, FLAMA ameliore le delai de bout en bout par rapport a TRAMA gracea l’exploitation des routes definies a partir d’un arbre pour le cheminement multi-sauts. Enrevanche, FLAMA surcharge le reseau par des echanges pour connaıtre le flux de l’applicationet etablir une synchronisation globale du reseau de proche en proche.

E-MAC, L-MAC et AI-LMAC

E-MAC (Event MAC) decoupe le temps en slots, chaque slot est lui-meme decoupe entrois parties respectivement prevues pour accueillir les requetes de communication, le trafic decontrole et le trafic de donnees. E-MAC definit trois types de nœuds : les nœuds actifs possedantun slot, les nœuds passifs ne possedant pas de slot et ne transmettant qu’apres avoir fait unerequete pour utiliser le slot d’un voisin durant la partie dediee aux requetes de communicationdu slot du voisin, et les nœuds dormants qui dorment la plupart du temps et choisissent unmode passif ou actif quand ils se reveillent. Chaque nœud diffuse une information concernantles slots utilises par ses voisins durant la partie trafic de controle de son slot. Les nœuds doiventtous se reveiller durant la partie trafic de controle des slots de leurs voisins.

L’allocation des slots commence par une station de base qui choisit un slot et annonce cechoix par une diffusion. Ensuite, ses voisins choisissent aleatoirement un slot. En cas de choixd’un meme slot, les nœuds signalent ce fait durant la partie trafic de controle. Les slots sontreutilises a partir de trois sauts.

L-MAC (Lightweight-MAC) adopte le meme mecanisme d’allocation de slots et de decoupagetemporel que E-MAC. En revanche, L-MAC force tous les nœuds a avoir au moins un slot.Ainsi, la partie requete de communication du slot n’est plus presente dans L-MAC et un slotest fractionne en 2 parties seulement.

AI-LMAC (Adaptive, Information-centric and Lightweight MAC) est une amelioration deL-MAC qui prend en compte les conditions du trafic applicatif et offre la possibilite aux nœudsd’avoir plusieurs slots. AI-LMAC regroupe les nœuds avec des relations pere-fils. Le pere surveilleles conditions de trafic de ses fils et demande a ses fils de s’allouer plus de slots ou de se desallouerdes slots selon leur charge.

Gerard Chalhoub, Clermont Universite 23 Reseaux de capteurs sans fil

Page 25: Réseaux de capteurs sans fil

La figure 3.3 montre le decoupage temporel en slots des trois protocoles.

����������������������������������������������������������

������

���������

���������

������

������

���������

���������

��

E-MAC

L-MAC et AI-LMAC

Requete de communication Trafic de controle Donnees

Fig. 3.3 – Decoupage temporel de E-MAC, L-MAC et AI-MAC.

3.1.3 Protocoles bases sur la contention

Dans ce type de protocoles MAC, les nœuds accedent au medium durant le meme intervallede temps en utilisant un algorithme de la famille CSMA/CA, chacune de ses variantes essayantd’eviter les collisions.

Le point fort de ce type de protocoles est sans doute l’extensibilite et le passage a l’echelle.En revanche, ces protocoles n’offrent pas de delai borne du fait qu’ils ne garantissent pas l’accesau medium des que la charge du reseau augmente.

Nous allons commencer cette partie en decrivant brievement l’algorithme de CSMA/CA dela norme IEEE 802.11 en mode DCF, sur lequel est basee la plupart des protocoles qui exploitentde differentes facons une periode de contention, ce que nous allons decrire par la suite.

CSMA/CA de la norme IEEE 802.11

CSMA/CA est une methode d’acces de la meme famille que CSMA/CD (Carrier SenseMultiple Access with Collision Detection) puisqu’elle impose a un emetteur de s’assurer que lecanal est libre avant d’emettre. Dans CSMA/CA, les collisions ne peuvent pas etre detecteescomme dans le CSMA/CD, un nœud essaie d’eviter les collisions (sans vraiment les eviter a 100%). Ceci a cause de l’effet d’aveuglement du medium sans fil (Near Far Effect) qui empeche uneentite de recevoir quand elle est en train d’emettre.

Rappel : Clear Channel Assessment, zone d’interferencesTerminal cache et terminal expose

S-MAC, T-MAC et D-MAC

S-MAC (Sensor-MAC) est concu pour assurer une methode d’acces econome en energie pourles reseaux de capteurs sans fil. Pour ce faire, les nœuds se mettent en mode sommeil pendantune certaine duree et se reveillent pour ecouter le medium pendant une autre duree.

Les nœuds echangent leur calendrier de periodes d’ecoute en le diffusant a leurs voisins aun saut. Ainsi, chaque nœud connaıt le calendrier de ses voisins et sait quand il faut se reveillerpour communiquer avec un nœud a sa portee. Plusieurs nœuds peuvent avoir le meme intervallede temps comme periode d’ecoute. Les nœuds accedent au medium en utilisant le CSMA/CAde IEEE 802.11 avec le mecanisme RTS/CTS. En outre, un champ supplementaire est ajoutea tous les messages (y compris les messages RTS/CTS et les acquittements) indiquant la dureede l’echange, ce qui permet aux nœuds non concernes de dormir pendant cette duree.

Pour maintenir une synchronisation des horloges, les nœuds emetteurs envoient des messagesde synchronisation SYNC au debut de la periode d’ecoute de leurs voisins.

Gerard Chalhoub, Clermont Universite 24 Reseaux de capteurs sans fil

Page 26: Réseaux de capteurs sans fil

A

B

C

D

-82 dBm

-95 dBm

Zone d’interference

Portee

Seuil de reception

Seuil de detection de porteuse

Fig. 3.4 – Portee et zone d’interference.

A B C

Fig. 3.5 – A et C envoient simultanement deux messages a B et generent un risque de collisionen B.

A B CD

Fig. 3.6 – A communique avec D. B veut communiquer avec C mais ne le fait pas parce que Aoccupe le medium, alors que si B communique avec C aucune collision n’aura lieu.

Gerard Chalhoub, Clermont Universite 25 Reseaux de capteurs sans fil

Page 27: Réseaux de capteurs sans fil

SYNC

SYNC

RTS

RTS

replacementsRecepteur A

Emetteur B

Emetteur C

sommeilecouteSYNC

ecouteSYNCecoute RTS ecoute RTS

envoi de donneessi CTS recu

envoi de donneessi CTS recu

Fig. 3.7 – Sequencement des periodes d’ecoute et de sommeil dans S-MAC.

T-MAC (Timeout-MAC) propose de mettre un nœud en mode sommeil apres un temps TAdurant lequel le nœud n’a recu aucun message. Ainsi, T-MAC reduit l’idle listening par rapporta S-MAC.

S-MAC

T-MAC sommeilsommeil

sommeilsommeil

TA TATA

Fig. 3.8 – Sequencement des periodes d’ecoute et de sommeil de T-MAC et de S-MAC.

Avec cette approche, T-MAC fait dormir un nœud sans s’etre assure que ses voisins n’ontplus de donnees a lui envoyer. En effet, les donnees a envoyer du voisin ont pu etre retardees acause d’un echec d’acces au canal.

Early sleep : Ce probleme est appele le sommeil premature.D-MAC (Data gathering MAC) propose un sequencement des periodes d’activite qui favo-

rise la collecte d’informations dans une topologie arborescente. Les nœuds de meme niveau sereveillent en meme temps.

LPL : B-MAC, WiseMAC, B-MAC+, X-MAC et DW-LPL

Le LPL (Low Power Listening) est l’une des premieres approches pour reduire l’idle listeningen introduisant une periode d’inactivite au niveau de la couche physique. L’idee est de penaliserles emetteurs en envoyant un preambule long pour economiser l’energie des recepteurs. Lesrecepteurs activent leur module radio periodiquement pour detecter la presence d’un preambule.La duree de transmission du preambule doit etre de la meme longueur que l’intervalle entre deuxreveils d’un recepteur.

L’un des premiers protocoles MAC pour les reseaux de capteurs sans fil bases sur cettetechnique est B-MAC (Berkeley-MAC).

WiseMAC a ete propose pour reduire la longueur du preambule en fonction des periodes dereveil des recepteurs voisins.

B-MAC+ ameliore B-MAC en remplacant le long preambule par plusieurs petits messagesappeles des paquets de countdown contenant chacun l’identifiant du destinataire et le tempsrestant pour commencer l’envoi des donnees.

X-MAC decompose lui aussi le long preambule en plusieurs preambules de petite tailleincluant l’identifiant du destinataire du message. Contrairement a B-MAC+, le destinataire

Gerard Chalhoub, Clermont Universite 26 Reseaux de capteurs sans fil

Page 28: Réseaux de capteurs sans fil

B

A

replacemen

Reveil periodique

Preambule Envoi de donnees

Receptiondu preambule

Reception des donnees

Fig. 3.9 – LPL : L’emetteur utilise un long preambule pour permettre au recepteur d’activerson module radio seulement de temps en temps.

previent l’emetteur de son ecoute avec un acquittement envoye entre deux preambules consecutifs.L’emetteur peut alors commencer la transmission des donnees. Cela reduit l’overhead au niveaude l’emetteur qui arrete la transmission du preambule des la reception de l’acquittement.

DW-LPL (Dual Wake-up LPL) limite le probleme de l’overhearing en employant la tech-nique du LPL pour les messages diffuses uniquement. L’envoi de messages unicast utilise unetechnique de signalement par des trames specifiques envoyes par les recepteurs pour informerleur entourage qu’ils sont prets a recevoir des trames en unicast. Les instants et la periodicited’envoi des messages de signalement sont independants d’un nœud a l’autre.

3.1.4 Protocoles hybrides

Une troisieme famille de protocoles propose de combiner les deux methodes : TDMA etCSMA/CA. Ainsi, ces protocoles essaient d’avoir les avantages des deux methodes en alternantles deux dans le temps ou en les combinant d’une maniere intelligente. Dans la suite, nous allonsdecrire trois protocoles hybrides : Z-MAC, G-MAC et Funneling-MAC.

Z-MAC

Z-MAC (Zebra-MAC) est un protocole hybride qui alterne des periodes de TDMA et CSMA/CAselon le nombre d’entites en concurrence en un instant donne. Z-MAC utilise un decoupage tem-porel base sur TDMA et gere les acces durant les slots avec le CSMA/CA de IEEE 802.11.

Une fois le reseau deploye, Z-MAC commence par une phase de decouverte du voisinage adeux sauts suivie par une assignation de slots aux nœuds en utilisant DRAND (Distributed Ran-domized TDMA Scheduling For Wireless Adhoc Networks). DRAND est un protocole distribuequi assure qu’un slot de temps n’est pas assigne a deux nœuds situes a moins de trois sautsl’un de l’autre. La synchronisation necessaire est obtenue a l’aide de deux protocoles utilises defacon complementaire.

Pour acceder au medium, si le nœud est le proprietaire du slot courant, il attend un tempsaleatoire plus petit qu’une valeur To puis effectue un CCA. Si le canal est libre, il emet. Sinon,il attend que le canal devienne libre et il recommence la meme demarche. Si le slot actuelappartient a un voisin a deux sauts et si le nœud a recu une indication de forte contention d’unde ses voisins a deux sauts, le nœud n’a pas le droit d’utiliser ce slot. Sinon, il attend un tempsaleatoire compris entre To et Tno avant d’effectuer un CCA.

Z-MAC utilise la technique LPL. Comme les nœuds peuvent emettre durant tous les inter-valles, les nœuds ecoutent le medium periodiquement pour verifier s’il y a des emissions qui lesconcernent.

Gerard Chalhoub, Clermont Universite 27 Reseaux de capteurs sans fil

Page 29: Réseaux de capteurs sans fil

������

������

��������

������

������

����

������

������

��������A

B

C

D

C

DA

B

To

To

To

To

To

To

Tno

Tno

Tno

Tno

Tno

Tno

Fig. 3.10 – Decoupage temporel de Z-MAC. Notons l’existence d’un temps pendant lequel lemedium n’est pas utilise.

G-MAC

G-MAC (Gateway MAC) organise les echanges a l’interieur d’un cluster. Dans ce domaine,un cluster est un ensemble de nœuds gere par une station appelee passerelle. G-MAC decoupele temps en deux periodes : une periode de collecte ou les echanges se font en CSMA/CA, etune periode de distribution ou les echanges se font en TDMA.

Durant la periode de collecte, les nœuds envoient a leur passerelle deux types de trafic : lesrequetes FRTS (Future Request To Send) pour reserver un slot de temps dans la periode dedistribution pour echanger avec d’autres nœuds appartenant au meme cluster, et le trafic inter-cluster destine aux nœuds appartenant a des clusters differents. Durant un slot, les echangesse font selon le sequencement RTS-CTS-donnees-acquittement. La periode de distribution com-mence par une diffusion d’un message GTIM (Gateway Traffic Indication Message) qui contientles indications temporelles des deux periodes suivantes ainsi que le sequencement des echangesentre les nœuds du cluster qui ont reussi a envoyer une requete FRTS.

Pendant la periode de collecte et pendant les slots non reserves de la periode de distribution lapasserelle echange les donnees inter-cluster avec d’autres passerelles une fois la collecte terminee.

������������

������������

GT

IM

Periode de collecte Periode de distribution

Echanges de RTS (donnees inter-cluster)

Requetes FRTS (donnees intra-cluster)

Echanges entre passerelles

Echanges de donnees intra-cluster

Echanges entre passerelles

Fig. 3.11 – Decoupage temporel de G-MAC.

Funneling-MAC

Funneling-MAC est un protocole MAC qui prend en compte le goulot d’etranglement dontsouffrent la plupart des applications des reseaux de capteurs. Ce phenomene survient quandune station du reseau joue le role d’un puits de donnees vers lequel un ensemble de capteurs

Gerard Chalhoub, Clermont Universite 28 Reseaux de capteurs sans fil

Page 30: Réseaux de capteurs sans fil

dirige son trafic. Cela est represente sur la figure 3.12 sur laquelle est identifiee une zone a fortecharge.

Puits

Goulot d’etranglement

TDMA et CSMA/CA

CSMA/CA

Zone a forte charge

Fig. 3.12 – Gestion du goulot d’etranglement dans Funneling-MAC.

Funneling-MAC adopte une methode d’acces en CSMA/CA dans l’ensemble du reseau du-rant un intervalle de temps suivi par un intervalle de temps durant lequel une methode d’accesen TDMA est utilisee pour la zone a forte charge uniquement pour offrir plus de temps d’accesaux nœuds a proximite du puits. Ces deux intervalles de temps constituent une supertrame. Cedecoupage est represente sur la figure 3.13.

La zone a forte charge est dimensionnee par une diffusion d’un beacon par le nœud puits.Les nœuds qui ne recoivent pas ce beacon appliquent le CSMA/CA.

SupertrameSupertrame

TDMATDMA CSMA/CACSMA/CA

Bea

con

Bea

con

Fig. 3.13 – Decoupage temporel dans Funneling-MAC.

Le puits se base sur le chemin parcouru par les trames qu’il recoit pour definir le sequencementet le dimensionnement des slots TDMA alloues aux nœuds de la zone a forte charge. Seuls lesnœuds appartenant a la zone a forte charge mettent a jour le chemin parcouru par une trame.

Pour eviter que les nœuds qui se trouvent au dela de la zone a forte charge interferent avec ledecoupage temporel du TDMA et le beacon transmit par le nœud puits, les nœuds de la zone aforte charge generent periodiquement une trame contenant les informations concernant la dureede la periode CSMA/CA, la duree de la periode TDMA et le nombre de supertrames jusqu’auprochain beacon.

Gerard Chalhoub, Clermont Universite 29 Reseaux de capteurs sans fil

Page 31: Réseaux de capteurs sans fil

Chapitre 4

La norme 802.15.4

4.1 Couche physique IEEE 802.15.4

La couche physique IEEE 802.15.4 est generalement prise en charge par le module radio.Elle offre quatre debits differents. Le tableau 4.1 resume les debits proposes selon la frequenceet la modulation.

Frequence(MHz)

ModulationDebit(kb/s)

868/868.6 BPSK 20

868/868.6 ASK 250

868/868.6 O-QPSK 100

902/928 BPSK 40

902/928 ASK 250

902/928 O-QPSK 250

2400/2483.5 O-QPSK 250

Tab. 4.1 – Le debit en fonction de la frequence et de la modulation.

Dans la bande de frequences des 2.4 GHz, le debit est donc de 250 Kb/s, il lui est associeun seuil de reception qui va jusqu’a −92 dBm.1

Avec les trois plages de frequences, la couche physique offre 27 canaux de transmissiondifferents dont 16 sur la plage de frequences de 2400/2483.5 MHz separes de 5 MHz, 10 surla plage de frequences de 902/928 separes de 2 MHz et 1 canal sur la plage de frequences de868/868.6 MHz. L’usage de ces canaux depend de la legislation des pays dans lesquels dessolutions conformes a ce standard sont utilisees.

Parmi les fonctionnalites de controle de cette couche, nous pouvons disposer de celles quipermettent de :

– activer et desactiver le module radio,– remonter l’etat d’un lien a la couche superieure,– tester l’occupation du canal en faisant un CCA,– choisir le canal de transmission.

1A noter que le debit utilise pour l’envoi des trames de donnees par la couche physique de la norme IEEE802.11 est de 11 Mbits/s, ce qui donne un seuil de reception de −82 dBm. Le seuil de detection de porteuse estde −95 dBm.

30

Page 32: Réseaux de capteurs sans fil

4.1.1 Activation et desactivation du module radio

Le module radio possede trois etats de fonctionnement : un etat de transmission, un etat dereception et un etat de sommeil. Le temps de changement d’etat entre transmission et receptionne doit pas depasser les 192 µs. Cet etat est pilote par la couche MAC. Il est essentiel poureconomiser de l’energie de mettre le module en mode sommeil.

4.1.2 Indication de la qualite du lien

Le LQI (Link Quality Indication) caracterise la qualite d’un lien a un instant donne suite aune reception d’une trame. Ce parametre est essentiel pour les protocoles des couches reseau etapplication. Par exemple, un protocole de routage peut exploiter cette indication afin d’identifierles meilleurs liens a utiliser dans son choix de routes.

4.1.3 Test d’occupation du medium ou CCA (Clear Channel Assessment)

Le CCA permet de savoir l’etat du canal radio. Il est essentiel pour le fonctionnement del’algorithme de CSMA/CA de la couche MAC. La couche physique est capable d’effectuer troismodes de CCA differents :

– La detection d’un signal avec une puissance recue superieure a un certain seuil.– La detection d’un signal conforme a la modulation de la couche physique.– La detection d’un signal qui repond aux deux conditions.A noter que le seuil de detection d’activite est typiquement -95 dBm.

4.1.4 Selection du canal

Comme la couche physique offre plusieurs canaux de transmission, il est necessaire deselectionner un canal precis, ceci a la demande des couches superieures. Le changement decanal est aussi fait implicitement par la couche physique suite a une demande de scrutation surl’ensemble des plages de frequences chacune constituant un canal de transmission. Cette actionest appelee un scan.

4.2 Couche MAC IEEE 802.15.4

La couche MAC 802.15.4 supporte deux modes de fonctionnement selon les besoins appli-catifs : le mode suivi de beacon et le mode non suivi de beacon. En mode suivi de beacon, lecoordinateur envoie periodiquement un beacon pour synchroniser l’activite des entites qui luisont attachees selon une structure de supertrame donnee sur la figure 4.1. En mode non suivide beacon, les beacons ne sont utilises que pour la decouverte du reseau.

Par la suite, nous allons decrire les fonctionnalites de gestion essentielles de la couche MAC802.15.4 :

– l’acces au medium,– les scans, la creation du reseau et l’association,– la synchronisation avec un coordinateur,– les echanges de trames.

4.2.1 Acces au medium

Un coordinateur limite l’acces au medium en utilisant la diffusion de beacon delimitant dessupertrames. La structure de la supertrame est definie par les deux parametres BI (Beacon In-terval) qui definit l’intervalle qui separe deux beacons consecutifs et SD (Superframe Duration)

Gerard Chalhoub, Clermont Universite 31 Reseaux de capteurs sans fil

Page 33: Réseaux de capteurs sans fil

qui definit la duree de la supertrame.

BI et SD sont calcules en fonction de BO (Beacon Order) et SO (Superframe Order) selonles formules suivantes :

{

BI = aBaseSuperframeDuration.2BO,SD = aBaseSuperframeDuration.2SO,

avec 0 ≤ SO ≤ BO ≤ 14, aBaseSuperframeDuration est un attribut de la couche MAC quidefinit la duree de la supertrame quand SO = 0 (15.36 ms pour valeur par defaut pour aBaseSu-perframeDuration). aBaseSuperframeDuration = aBaseSlotDuration∗aNumSuperframeSlots,avec aBaseSlotDuration le nombre de symboles (un symbole vaut 4 bits) constituant un slot de lasupertrame quand SO = 0. aBaseSlotDuration a 60 comme valeur par defaut. aNumSuperframeSlotsest le nombre de slots qui constituent la supertrame, il vaut 16.

La portion active de la supertrame est decoupee en aNumSuperframeSlots slots de tempsegaux et est composee de trois parties : le beacon, la CAP (Contention Access Period) et laCFP (Contention Free Period). Durant la CAP toutes les stations sont en competition pouracceder au medium alors que la CFP est constituee de slots de temps, appeles GTS (GuaranteedTime Slot) alloues a chaque station pour communiquer avec le coordinateur.

Le debut du premier slot est l’instant d’envoi du beacon. La CAP suit la fin de transmissiondu beacon et la CFP, si elle est presente, suit immediatement la fin de la CAP. Si un coordinateurne souhaite pas appliquer la structure de la supertrame, il initialise les valeurs de BO et de SOa 15. Dans ce cas, nous nous retrouvons dans un PAN en mode non suivi de beacon.

��������������������������������������������������������������������������������

������������

��������

��������

0 1 2 3 4 5 6 7 8 9 101112131415

beaconbeacon

CAP CFP

SD (periode d’activite)

BI

GTS GTS periode d’inactivite

Fig. 4.1 – La structure de la supertrame.

La figure 4.1 montre un exemple d’une supertrame incluant un periode de CAP, une periodede CFP contenant deux GTS de tailles differentes et une periode d’inactivite (car BO = SO+1).

L’acces au medium durant la CAP pour toute trame, sauf les acquittements et les beacons,est gere selon l’algorithme de CSMA/CA slotte. Avant tout envoi, l’entite doit s’assurer depouvoir finir la transaction (incluant la reception d’un acquittement s’il est demande) et depouvoir attendre un IFS (InterFrame Space)2 avant la fin de la CAP. Si ce n’est pas le cas,l’envoi est reporte a la CAP de la supertrame suivante. L’envoi de trames durant les slotsreserves au GTS s’effectue sans CSMA/CA.

2La duree d’un IFS depend de la longueur du MPDU (MAC Protocol Data Unit) de la trame envoyee, ce quicorrespond a la payload physique. Quand cette longueur depasse 18 octets, le IFS vaut 40 symboles, sinon, le IFSvaut 12 symboles

Gerard Chalhoub, Clermont Universite 32 Reseaux de capteurs sans fil

Page 34: Réseaux de capteurs sans fil

Algorithme de CSMA/CA slotte

L’algorithme de CSMA/CA slotte est applique pour l’envoi d’une trame durant la periodeCAP de la supertrame, sauf pour l’envoi des trames de beacon et des trames d’acquittement.L’algorithme se base sur une unite de temps appele periode de backoff, une periode de backoffest egale a aUnitBackoffPeriod symboles, soit 20 symboles. La synchronisation est basee sur undecoupage du temps en intervalles a trois niveaux differents et imbriques : des supertrames, elle-meme decoupees en slots, eux-meme decoupes en periode de backoff. Les frontieres des periodesde backoff de CSMA/CA pour chaque entite sont alignees avec les frontieres des slots de lasupertrame. Le debut de la premiere periode de backoff est le debut du premier slot de la CAP(debut de la transmission du beacon). Toute activite de la couche physique doit commencer ala frontiere d’une periode de backoff. Ainsi, toute les entites sont synchronisees entre-elles surles periodes de backoff.

La figure 4.2 montre la hierarchie du decoupage temporel et l’alignement des periodes debackoff avec les slots de la supertrame. Nous avons considere le cas ou BO = SO = 0, ce quinous donne un slot de supertrame durant 0,96 ms. Dans ce cas, chaque slot de supertramecontient trois periodes de backoff. La supertrame montree sur la figure 4.2 ne comporte pas deCFP.

beacon

CAP

Une periode de backoff Un slot de la supertrame

Fig. 4.2 – Les periodes de backoff et les 16 slots de la supertrame.

L’algorithme de CSMA/CA slotte est une variante de CSMA/CA qui exploite une synchro-nisation precise pour se dispenser de surveiller en permanence l’occupation du medium, ce quiconsomme beaucoup d’energie. Il est base sur trois parametres essentiels : NB, BE et CW. NB(Number of Backoffs) est le nombre de fois ou l’entite a applique l’algorithme pour essayerd’envoyer la trame courante. BE (Backoff Exponent) est l’exposant de backoff qui definit lalongueur de l’intervalle dans lequel il faut tirer un backoff. CW (Contention Window) definit lenombre de periodes de backoff consecutives a la fin desquelles le canal doit etre detecte libreavant de commencer la transmission.

La figure 4.3 presente une version simplifiee des differentes etapes de l’algorithme de CSMA/CAslotte. La premiere etape est la phase d’initialisation. L’algorithme commence avec BE =macMinBE, NB = 0 et CW = 2. Une fois les parametres initialises, l’etape 2 consiste a locali-ser la frontiere de la prochaine periode de backoff et a attendre un nombre entier de periodes debackoff tire aleatoirement dans l’intervalle [0; 2BE−1]. Si la duree du backoff tire est plus longueque le nombre restant de periodes de backoff dans la CAP, l’algorithme consomme le backoffjusqu’a la fin de la CAP et reporte ce qui lui reste pour la CAP de la supertrame suivante.

Apres la consommation de ce backoff, la couche MAC verifie que le nombre restant deperiodes de backoff dans la CAP est suffisant pour effectuer 2 CCA, transmettre la trame

Gerard Chalhoub, Clermont Universite 33 Reseaux de capteurs sans fil

Page 35: Réseaux de capteurs sans fil

physique et recevoir un eventuel acquittement. Si c’est le cas, l’etape 3 est appliquee. Danscette etape, la couche MAC demande a la couche PHY d’effectuer un CCA a la frontiere de laprochaine periode de backoff. Si le temps restant dans cette supertrame est suffisant, la coucheMAC reporte le CCA au debut de la CAP de la prochaine supertrame, en commencant avecun tirage de backoff pour eviter les collisions systematiques dues a plusieurs reports de CCAeffectues par differentes entites.

Si la couche PHY detecte que le canal est libre, la couche MAC decremente CW, puis testesi CW est nul. Si c’est le cas, la couche MAC demande a la couche PHY de commencer latransmission a la frontiere de la prochaine periode de backoff. Si CW n’est pas nul, la coucheMAC demande a la couche PHY de faire un autre CCA. Le medium n’est donc pas scrute enpermanence, mais c’est deux CCA consecutifs positifs qui permettent de conclure que le mediumest libre 3.

Si la couche PHY detecte que le canal est occupe, la couche MAC incremente NB etBE de 1 (a condition que BE reste inferieur ou egal a macMaxBE) et remet CW a 2.Si NB = macMaxCSMABackoffs, l’algorithme renvoie un echec d’acces. C’est alors a lacouche MAC de demander une retransmission de la meme trame tant que le nombre de ten-tatives est plus petit que macMaxFrameRetries (macMaxFrameRetries = 3 par defaut). SiNB < macMaxCSMABackoffs, l’algorithme retourne a l’etape 2.

Le mode BLE (Battery Life Extension) : le coordinateur de PAN peut decider de fairetravailler le reseau en mode BLE pour economiser d’avantage de l’energie. Un bit specifique estreserve dans le beacon a cet effet. Quand ce bit est mis a 1, les entites associees a ce coordinateurdoivent acceder au medium en respectant un IFS suivi d’une duree de macBattLifeExtPeriodsapres la reception du beacon.

macBattLifeExtPeriods est un entier qui correspond a un nombre de periodes de backoff,qui est calcule en fonction de trois termes : (i) la valeur maximum d’un backoff tire dans unefenetre avec BE = 2, cela vaut 3 periodes de backoff, (ii) la duree de CCA, ce qui fait 2periodes de backoff, et (iii) la duree de transmission du preambule physique et du champ desynchronisation de l’en-tete physique, cela fait, pour la frequence de 2.4 GHz, une longueur de5 octets et donc une duree arrondie a une seule periode de backoff.

Le total fait alors 6 periodes de backoff. Une entite qui souhaite emettre un message dansun reseau en mode BLE doit envoyer sa trame dans les 6 periodes de backoff qui suivent l’IFSapres la reception du beacon. Le coordinateur et toutes les autres entites se mettent en modesommeil si aucune trame n’est transmise avant cette duree.

Algorithme de CSMA/CA non-slotte

L’algorithme de CSMA/CA non-slotte est applique pour les envois de trames dans un reseauen mode non suivi de beacon. Pour autant, il ne s’agit pas de CSMA/CA de la norme IEEE802.11. Le parametre CW n’existe pas dans l’algorithme de CSMA/CA non-slotte : il suffit dedetecter une seule fois que le canal est libre pour commencer une transmission. L’unite du tempsreste la periode de backoff, mais l’activite des entites n’est pas synchronisee sur ces periodes debackoff.

La figure 4.4 presente les differentes etapes du CSMA/CA non-slotte. L’algorithme com-mence par la phase d’initialisation en mettant BE = macMinBE et NB = 0. Puis, elle tirealeatoirement un nombre entier de periodes de backoff. Apres la consommation du backoff,la couche MAC demande a la couche PHY d’effectuer un CCA. Si la couche PHY detectele canal libre, la couche MAC commence la transmission. Si ce n’est pas le cas, la coucheMAC incremente NB et BE (a condition que BE reste inferieur ou egal a macMaxBE).

3Dans le cas du CSMA/CA de la norme 802.11, la scrutation du canal est faite durant le backoff

Gerard Chalhoub, Clermont Universite 34 Reseaux de capteurs sans fil

Page 36: Réseaux de capteurs sans fil

ouioui

non oui

nonnon

Initialisation : BE = macMinBE, NB = 0 et CW = 2

Localiser la frontiere dela prochaine periode de backoff

Tirage de backoff dans [0; 2BE − 1]

Effectuer un CCA

Canal libre ?

NB = NB + 1BE = min(BE + 1, macMaxBE)

NB >macMaxCSMABackoffs

CW = CW − 1

CW = 0 ?

Echec Succes

Etape 1

Etape 2

Etape 3

Fig. 4.3 – Diagramme de l’algorithme de CSMA/CA slotte de la norme IEEE 802.15.4.

Gerard Chalhoub, Clermont Universite 35 Reseaux de capteurs sans fil

Page 37: Réseaux de capteurs sans fil

Si NB < macMaxCSMABackoffs, l’algorithme revient au tirage de backoff. Si NB =macMaxCSMABackoffs, l’algorithme renvoie un diagnostic d’echec d’acces. C’est alors ala couche MAC de demander une retransmission de la meme trame tant que le nombre de ten-tatives est plus petit que macMaxFrameRetries (macMaxFrameRetries vaut 3 par defaut).

Echec

non

oui

non

oui

Initialisation BE = macMinBE et NB = 0

Tirage de backoff dans [0; 2BE − 1]

Effectuer un CCA

Canal libre ?

NB = NB + 1BE = min(BE + 1, macMaxBE)

NB >macMaxCSMABackoffs

Succes

Fig. 4.4 – Diagramme de l’algorithme de CSMA/CA non-slotte de la norme IEEE 802.15.4.

4.2.2 Les scans, la creation du reseau, les associations et la synchronisation

Les scans

Afin de decouvrir les reseaux existants a portee, de creer un reseau, de s’associer a un reseauou de se synchroniser avec un reseau, la couche MAC effectue un des quatre types de scanssuivants :

– Le scan d’energie permet de recuperer l’energie maximum detectee sur chaque canal. Cescan est utilise par un coordinateur souhaitant creer un PAN afin de choisir le canalconvenable.

– Le scan actif permet de recuperer la liste des identifiants de PAN existants. Le scanactif suit la diffusion de requete de beacon. Un coordinateur fonctionnant selon un modenon suivi de beacon repond a cette requete par une diffusion de beacon. Un coordinateurfonctionnant selon un mode suivi de beacon l’ignore et continue a envoyer ses beaconsperiodiquement. Ce scan est utilise par un coordinateur souhaitant creer un PAN pour

Gerard Chalhoub, Clermont Universite 36 Reseaux de capteurs sans fil

Page 38: Réseaux de capteurs sans fil

choisir le bon identifiant de PAN, ou par une station qui cherche a s’associer a un PAN(dont elle connaıt l’identifiant).

– Le scan passif comme pour le scan actif, permet de recuperer la liste des identifiantsde PAN existants. En revanche, la station n’envoie pas une requete de beacon mais elleeffectue une ecoute passive de chaque canal a scanner pour une duree donnee. Ce scan estutilise par une station qui cherche a s’associer a un PAN.

– Le scan d’orphelin permet a une station de retrouver son coordinateur apres une perte desynchronisation avec ce dernier.

Creation du reseau

La couche superieure envoie une requete a la couche MAC pour effectuer un scan actif surune liste de canaux afin de decouvrir les reseaux existants a portee. Une fois le bon canal choisi,la couche superieure decide d’un identifiant de PAN et demande a la couche MAC d’initier unPAN avec cet identifiant.

Association et desassociation

Apres avoir effectue un scan (passif ou actif) et remonte le resultat du a la couche superieure,cette derniere demande a la couche MAC de s’associer a un PAN specifique en precisant sonidentifiant PAN et l’adresse du coordinateur correspondant. Suite a cette demande, la coucheMAC genere une requete d’association a destination du coordinateur.

A la reception d’une requete d’association, la couche MAC du coordinateur remonte l’infor-mation a la couche superieure et c’est a celle-ci de decider d’accepter ou pas cette requete enfonction des ressources qu’il lui reste par exemple. La reponse a cette requete d’association estenvoyee en mode de transmission indirecte (voir le paragraphe 4.2.3).

Suite a une requete de desassociation envoyee par la couche superieure, la couche MACenvoie une indication de desassociation au coordinateur pour l’informer que la station sou-haite se desassocier du PAN. De meme, la couche superieure d’un coordinateur peut decider dedesassocier une station qui lui est associee, elle lui envoie alors une commande de desassociationpour l’informer de ce fait.

Synchronisation avec le beacon du coordinateur

Dans le mode suivi de beacon, les entites restent synchronisees au reseau grace a la transmis-sion periodique d’une trame de beacon par le coordinateur. Le tableau 4.2 montre les differentschamps de ce beacon.

Toute station appartenant a un beacon-enabled PAN doit pouvoir se synchroniser avec lebeacon de son coordinateur pour connaıtre la structure de la supertrame, et aussi pour recupererles trames la concernant (comme indique par la liste des entites ayant des trames en instance).Si une station ne recoit pas un nombre aMaxLostBeacons consecutifs de beacons, la couche MACdetecte une perte de synchronisation et indique ce constat a la couche superieure.

La couche MAC rejette toute trame de beacon dont l’adresse source ou l’identifiant du PANne correspondent pas a l’adresse du coordinateur ou a l’identifiant du PAN auquel la station estassociee, respectivement.

4.2.3 Echange de donnees

Dans la primitive de requete de transmission de donnees envoyee par la couche superieure, unchamp (txOptions) specifie dans quel mode de transmission des donnees doivent etre transmises.

Gerard Chalhoub, Clermont Universite 37 Reseaux de capteurs sans fil

Page 39: Réseaux de capteurs sans fil

Octets :2

1 2 2/8 0/5/6/10/14

2variable variable variable

2

Framecontrol

Numerodesequence

PANIDsource

Adressesource

Entetesecurite

Specif-icationsde lasuper-trame

Champsde GTS

Liste desadressesenattente

Payload FCS

Entete MAC Payload MAC FooterMAC

Tab. 4.2 – Format du beacon de la norme IEEE 802.15.4.

Les trois modes d’echange sont : echange direct, echange indirect, echange en GTS. Ce champspecifie aussi si la trame de donnees doit etre acquittee ou pas.

Echange direct

Durant la CAP, la station essaie d’envoyer la trame en CSMA/CA slotte. En cas de trans-mission avec demande d’acquittement, la couche MAC fait macMaxFrameRetries tentatives(par defaut 3 tentatives) si l’acquittement n’est pas recu au bout de macAckWaitDuration 4

Echange indirect

Pour favoriser l’aspect economie d’energie, les stations feuilles initient la communication avecleur coordinateur, et cela selon deux procedures : (i) dans un PAN en mode suivi de beacon,le coordinateur indique dans son beacon la liste des adresses des entites qui ont des trames enattente chez lui, (ii) dans un PAN en mode non suivi de beacon, la station feuille sollicite lecoordinateur pour verifier s’il a des trames en attente pour elle.

Le coordinateur conserve les trames en attente pour une duree de macTransactionPersis-tenceTime avant de les supprimer si la station concernee ne l’a pas sollicite pour les recuperer.

Echange en GTS

L’allocation des GTS est faite uniquement par le coordinateur du PAN. Un GTS est allouesoit en mode reception (du coordinateur du PAN vers la station) soit en mode emission (de lastation vers le coordinateur du PAN).

Une station demande l’allocation d’un GTS aupres du coordinateur du PAN auquel elle estaffiliee. Le nombre maximal de GTS est limite a 7, a condition que la duree de la CAP restantereste superieure ou egale a aMinCAPLength (aMinCAPLength = 7 ms pour la frequence de2.4 GHz).

La reponse d’une requete de GTS est envoyee dans le beacon via des descripteurs deGTS. Cette information est gardee dans le beacon pour aGTSDescPersistenceTime (par defautaGTSDescPersistenceT ime = 4) beacons consecutifs.

4macAckWaitDuration = aUnitBackoffPeriod + aTurnaroundT ime + phySHRDuration + 6 ∗

phySymbolsPerOctet, ou aUnitBackoffPeriod = 320 µs, aTurnaroundT ime = 192 µs, phySHRDuration =128 µs (pour la frequence de 2.4 GHz), 6 represente le nombre d’octets de l’en-tete PHY incluant la longueur dela payload PHY de l’acquittement.

Gerard Chalhoub, Clermont Universite 38 Reseaux de capteurs sans fil

Page 40: Réseaux de capteurs sans fil

La desallocation d’un GTS peut etre faite soit a la demande de la couche superieure de lastation ayant le GTS, soit par la couche superieure du coordinateur du PAN suite au constatque la station n’a plus utilise son GTS durant 2 ∗ n supertrames consecutives5.

5n = 28−BO si 0 ≤ BO ≤ 8, n = 1 si 9 ≤ BO ≤ 14.

Gerard Chalhoub, Clermont Universite 39 Reseaux de capteurs sans fil

Page 41: Réseaux de capteurs sans fil

Chapitre 5

ZigBee

5.1 Couche reseau ZigBee

La couche reseau de ZigBee est restee compatible avec la couche MAC IEEE 802.15.4 en as-surant des fonctionnalites complementaires et compatibles avec celles de la couche MAC. Il s’agitsoit de fonctionnalites liees a la transmission de donnees, comme l’encapsulation des donneesapplicatives et le choix du prochain saut du cheminement du paquet, soit de fonctionnalitesliees a la gestion, comme la gestion des tables de routage, la configuration de la topologie etl’allocation des adresses logiques.

5.1.1 Creation de la topologie

Comme pour la couche MAC IEEE 802.15.4, la couche reseau supporte deux types de topo-logies : topologie en etoile et topologie maillee. Un cas particulier d’une topologie maillee est latopologie arborescente. Le topologie arborescente est appelee cluster-tree.

association

Coordinateur du PAN

Coordinateur

Feuille

Fig. 5.1 – Topologie cluster-tree.

Dans un reseau de topologie cluster-tree, le coordinateur du PAN transmet dans le beacontrois parametres essentiels que chaque coordinateur doit respecter et qui definissent la topologie

40

Page 42: Réseaux de capteurs sans fil

en arbre du reseau. Ces trois parametres sont :– la profondeur maximale du reseau (Lm),– le nombre maximal de fils par coordinateur (Cm),– le nombre maximal de fils coordinateurs par coordinateur (Rm) .A noter que si Lm = 1 nous nous retrouvons dans une topologie en etoile.

5.1.2 Allocation des adresses

Avant d’etre associee au reseau, une entite n’a que son adresse MAC IEEE, appelee adresselongue. Cette adresse occupe 8 octets. Afin d’optimiser la taille des champs d’adressage dans lestrames echangees, la couche reseau alloue une adresse courte logique qui n’occupe que 2 octets.Il existe deux mecanismes pour cette allocation : une allocation d’adresses hierarchiques et uneallocation d’adresses aleatoires.

Allocation d’adresses hierarchiques

L’allocation des adresses courtes se fait en se basant sur la profondeur du coordinateur et surles trois parametres Lm, Rm et Cm. Ce mecanisme d’allocation est distribue. A chaque coordi-nateur est confie une plage d’adresses selon sa profondeur. L’etendue de cette plage d’adressesest appelee Cskip. Cskip pour une profondeur d donnee est calcule selon la formule suivante :

Cskip(d) =

1 + Cm ∗ (Lm − d − 1) si Rm = 1,

1+Cm−Rm−Cm∗RmLm−d−1

1−Rmsinon

Les adresses sont allouees differemment selon le type de la station qui s’associe :

AdrC = AdrP + 1 + nbC ∗ Cskip(d),

AdrF = AdrP + Rm ∗ Cskip(d) + n

ou AdrC designe l’adresse allouee pour un nouveau coordinateur, AdrP l’adresse du pere,AdrF l’adresse allouee pour une nouvelle feuille, nbC le nombre actuel de coordinateurs fils, nest un entier superieur a 1 incremente suite a chaque nouvelle association d’une feuille (1 ≤ n ≤(Cm − Rm)).

Prenons le cas ou Lm = 3, Rm = 3 et Cm = 5, valeurs que nous designerons par (3, 3, 5).Cela nous donne les valeurs donnee sur le tableau 5.1 pour Cskip selon la profondeur d :

ProfondeurCskip

0 21

1 6

2 1

3 0

Tab. 5.1 – Valeurs de Cskip pour l’exemple (3, 3, 5).

A noter qu’un coordinateur de profondeur Lm n’accepte aucune association. En appliquantle jeu de parametres (3, 3, 5) au le cluster-tree de la figure 5.1, nous obtenons les adressesdonnees sur la figure 5.2 pour chaque station.

Gerard Chalhoub, Clermont Universite 41 Reseaux de capteurs sans fil

Page 43: Réseaux de capteurs sans fil

44

43

22

64

65

48

45

62

23

27

41 1

82

7

0

6

Coordinateur du PAN

Coordinateur

Feuille

Fig. 5.2 – Allocation des adresses hierarchiques sur un exemple. Le coordinateur 1 par exemple,qui est a la profondeur 1, a alloue l’adresse 2 a son premier fils et 8 au deuxieme, 8 = 2+Cskip(1).

Allocation d’adresses aleatoires

Dans le mode d’allocation d’adresses aleatoires, les parametres Lm, Rm, Cm et la profondeurn’ont plus d’effet sur le choix d’une adresse courte. Apres avoir accepte l’association d’une entite,le coordinateur choisit aleatoirement une adresse courte, en verifiant que cette adresse ne soitpresente dans aucune entree de sa table NIB (Network layer Information Base). Les eventuellesconflits d’adresses sont detectes et resolus par un mecanisme supplementaire.

5.1.3 Routage

Tout coordinateur qui possede des capacites de routage, maintient une table de routagequi sera utilisee pour determiner le prochain saut pour les paquets qui sont a destination desstations qui se trouvent hors portee du coordinateur. Nous allons nous limiter a detailler leroutage hierarchique uniquement.

Routage hierarchique

L’allocation d’adresses hierarchiques offre la possibilite d’appliquer un routage hierarchique.Les coordinateurs n’ayant pas une strategie de routage particuliere appliquent le routage hierarchique.Ce routage ne demande pas d’echanges supplementaires pour trouver les routes, ni la construc-tion de tables de routage.

Les routes utilisees pour acheminer les paquets dans un routage hierarchique sont unique-ment les routes de l’arbre. Pour determiner le prochain saut dans un routage hierarchique lecoordinateur applique un algorithme qui retourne l’adresse du prochain saut en fonction de sonadresse et l’adresse de la destination finale du paquet.

Nous designons par Adr l’adresse du coordinateur qui cherche a router le paquet selon leroutage hierarchique, d sa profondeur, AdrP l’adresse de son pere, DestF inale l’adresse de ladestination finale du paquet et Dest l’adresse du prochain saut.

Gerard Chalhoub, Clermont Universite 42 Reseaux de capteurs sans fil

Page 44: Réseaux de capteurs sans fil

si Adr < DestF inale ≤ Adr + Cskip(d − 1),

alors si DestF inale > Adr + Rm ∗ Cskip(d),

alors Dest = DestF inale,

sinon Dest = Adr + 1 + ⌊DestF inale−(Adr+1)Cskip(d) ⌋ ∗ Cskip(d),

sinon Dest = AdrP

Si DestF inale est comprise entre Adr et Adr + Cskip(d − 1), la destination finale est undescendant du coordinateur. Si ce n’est pas le cas, le coordinateur remonte le paquet a son pereen mettant Dest = AdrP .

Si la destination finale est un descendant, le coordinateur verifie si elle est une de ses feuilles.Si c’est le cas, il met Dest = DestF inale. Si la destination finale n’est pas une feuille, pourtrouver le fils vers lequel il va router le paquet, le coordinateur applique la formule Dest =Adr + 1 + ⌊DestF inale−(Adr+1)

Cskip(d) ⌋ ∗ Cskip(d).

5.2 Couche application ZigBee

La couche application de ZigBee est constituee de la sous-couche APL (APplication sub-Layer), du ZDO (ZigBee Device Object) et de l’Application Framework contenant des profilspredefinis. La figure 5.3 represente les trois entites de la couche application.

ZDO

NLME-SAPNLDE-SAP

APSDE-SAPAPSDE-SAPAPSDE-SAP

...

Couche applicationAPL

Couche reseauNET

Application framework

Objetapplicatif

240

Objetapplicatif

1

Fig. 5.3 – Couche application ZigBee. L’interface entre la couche application est les differentsobjets est appelee APSDE pour (APplication Support sub-layer Data Entity).

L’APS (APplication Support) constitue l’interface entre la couche reseau d’une part, le ZDOet les objets predefinis d’autre part. Nous listons a titre indicatif quelques services offerts parl’APS : l’encapsulation des donnees, la fragmentation et l’assemblage de donnees, le cryptagede donnees et l’adressage par groupe.

Gerard Chalhoub, Clermont Universite 43 Reseaux de capteurs sans fil

Page 45: Réseaux de capteurs sans fil

L’Application Framework peut supporter 240 objets applicatifs differents sur un meme nœudZigBee. L’objet applicatif par defaut est defini dans le ZDO. L’Application Framework permetaussi de definir des profils applicatifs specifiant des formats de messages et la facon de les traiterentre un ensemble d’objets applicatifs appartenant a des nœuds ZigBee differents. La figure 5.4represente un exemple de deux nœuds ZigBee A et B ayant chacun plusieurs objets applicatifs(interrupteur 1 et interrupteur 2 appartenant au nœud A et lampe 1, lampe 2, lampe 3 et lampe4 appartenant au nœud B). Nous voyons comment l’objet applicatif Int1 (interrupteur 1) peutcommuniquer a plusieurs objets applicatifs (lampe 1, lampe 2 et lampe 3) grace a une tablede binding qui permet de formaliser les correspondances entre differents objets. Cette table estpartagee par tous les nœuds qui partage la meme application. Les objets interrupteurs Int1 etInt2 et les lampes L1, L2, L3 et L4 appartiennent tous a un meme profil applicatif, ce qui leurpermet de comprendre les messages echanges entre-eux.

Binding Table

L1 L2 L3 L4

Radio Radio

Nœud A

Nœud B

Int1

Int2

Fig. 5.4 – Exemples d’application et de profils ZigBee.

Gerard Chalhoub, Clermont Universite 44 Reseaux de capteurs sans fil