RCSF

Routage et MAC dans les reseaux de capteurs sans fil
Gerard Chalhoub
26 octobre 2010
Table des mati`

eres
1 Introduction au routage
1.1 Vecteur de distance vs Etat

de liens . . . . . . .
1.1.1 Vecteur de distance . . . . . . . . . . . .
Etapes
dun protocole vecteur de distance
1.1.2 Counting-to-infinity . . . . . . . . . . . .
1.1.3 Etat
de liens . . . . . . . . . . . . . . . .
Etapes dun protocole etat de liens . . . .

1.1.4 Dijkstra . . . . . . . . . . . . . . . . . . .
1.2 Protocoles proactifs . . . . . . . . . . . . . . . . .
1.2.1 Exemple : OLSR . . . . . . . . . . . . . .
Interet des MPR . . . . . . . . . . . . . .
Echanges
periodiques . . . . . . . . . . .
1.3 Protocoles reactifs . . . . . . . . . . . . . . . . .
1.3.1 Exemple : AODV . . . . . . . . . . . . . .
1.4 Protocoles hierarchiques . . . . . . . . . . . . . .
1.5 Protocoles hybrides . . . . . . . . . . . . . . . . .
1.5.1 Exemple : ZRP . . . . . . . . . . . . . . .
IARP et IERP . . . . . . . . . . . . . . .
NDP . . . . . . . . . . . . . . . . . . . . .
Exemple denvoi . . . . . . . . . . . . . .
1.6 Protocoles geographiques . . . . . . . . . . . . .
1.6.1 Exemple : LAR . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4
4
4
4
5
5
5
5
5
6
6
6
7
7
8
8
10
10
10
11
11
12
2 Les techniques de routage dans les r

eseaux de capteurs sans fil
2.1 Domaines dapplication des reseaux de capteurs sans fil . . . . . . . . .
2.1.1 Applications militaires . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2 Applications liees `
a la securite . . . . . . . . . . . . . . . . . . .
2.1.3 Applications environnementales . . . . . . . . . . . . . . . . . . .
2.1.4 Applications medicales . . . . . . . . . . . . . . . . . . . . . . . .
2.1.5 Applications ecologiques . . . . . . . . . . . . . . . . . . . . . . .
2.1.6 Applications de tracabilite et de localisation . . . . . . . . . . . .
2.2 Contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Rappel : differences entre MANET et WSN . . . . . . . . . . . .
2.2.2 Critères `
a prendre en compte . . . . . . . . . . . . . . . . . . . .
2.3 Preambule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1 Flooding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.2 Gossiping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.3 Conlusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Classification des protocoles de routage des reseaux de capteurs sans fil
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
14
14
15
15
15
15
16
16
16
16
16
17
17
17
17
17
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.4.1
2.4.2
2.4.3
2.4.4
Protocoles Data-centric . . . .
SPIN . . . . . . . . . . . . . .
Direct Diffusion . . . . . . . . .
Procotoles hierarchiques . . . .
LEACH . . . . . . . . . . . . .
TEEN . . . . . . . . . . . . . .
Protocoles bases sur la position
GEAR . . . . . . . . . . . . . .
Protocoles bases sur la QoS . .
SAR . . . . . . . . . . . . . . .
SPEED . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3 Les protocoles MAC dans les WSN

3.1 Exemples de protocoles MAC pour les reseaux de capteurs sans fil
3.1.1 Economie
denergie . . . . . . . . . . . . . . . . . . . . . . .
Overhearing . . . . . . . . . . . . . . . . . . . . . . . . . . .
Collisions . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Idle listening . . . . . . . . . . . . . . . . . . . . . . . . . .
Envois infructueux . . . . . . . . . . . . . . . . . . . . . . .
Overhead . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.2 Protocoles bases sur un sequencement temporel . . . . . . .
TRAMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.3 FLAMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.4 E-MAC, L-MAC et AI-LMAC . . . . . . . . . . . . . . . .
3.1.5 Protocoles bases sur la contention . . . . . . . . . . . . . .
CSMA/CA de la norme IEEE 802.11 . . . . . . . . . . . . .
3.1.6 S-MAC, T-MAC et D-MAC . . . . . . . . . . . . . . . . . .
3.1.7 LPL : B-MAC, WiseMAC, B-MAC+, X-MAC et DW-LPL
3.1.8 Protocoles hybrides . . . . . . . . . . . . . . . . . . . . . .
Z-MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
G-MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Funneling-MAC . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
17
17
18
18
18
18
18
18
19
19
19
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
20
20
20
21
21
21
21
21
22
22
22
23
24
24
26
27
27
27
28
29
4 La norme 802.15.4
4.1 Couche physique IEEE 802.15.4 . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 Activation et desactivation du module radio . . . . . . . . . . . . . . .
4.1.2 Indication de la qualite du lien . . . . . . . . . . . . . . . . . . . . . .
4.1.3 Test doccupation du medium ou CCA (Clear Channel Assessment) .
4.1.4 Selection du canal . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Couche MAC IEEE 802.15.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1 Accès au medium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Algorithme de CSMA/CA slotte . . . . . . . . . . . . . . . . . . . . .
Algorithme de CSMA/CA non-slotte . . . . . . . . . . . . . . . . . . .
4.2.2 Les scans, la creation du reseau, les associations et la synchronisation
Les scans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Creation du reseau . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Association et desassociation . . . . . . . . . . . . . . . . . . . . . . .
Synchronisation avec le beacon du coordinateur . . . . . . . . . . . . .
4.2.3 Echange
de donnees . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
31
31
32
32
32
32
32
32
34
35
37
37
38
38
38
38
Gerard Chalhoub, Clermont Universit

e
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Reseaux de capteurs sans fil

Echange
direct . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Echange indirect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Echange
en GTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5 ZigBee
5.1 Couche reseau ZigBee . . . . . . . . . . .
5.1.1 Creation de la topologie . . . . . .
5.1.2 Allocation des adresses . . . . . . .
Allocation dadresses hierarchiques
Allocation dadresses aleatoires . .
5.1.3 Routage . . . . . . . . . . . . . . .
Routage hierarchique . . . . . . . .
5.2 Couche application ZigBee . . . . . . . . .

e
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
41
41
41
42
42
43
43
43
44
Chapitre 1
Introduction au routage
Les reseaux mobiles ad hoc MANET : ensemble dentites mobiles communicant en sans fil
sans aucune infrastructure pour gerer le reseau. Il ny a pas la notion de routeur ou passerelle
dediee. Tous les nuds sont des routeurs. Ce type de reseaux est souvent represente par un
graphe de noeuds relies entre-eux par des aretes, G (V, E).
Routage : trouver un chemin pour envoyer un message dun nud vers une destination selon
certains critères. 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 et
etat de liens.
1.1.1
Vecteur de distance
Les echanges se limitent au voisinage direct. Chaque nud maintient une table de vecteur
de distance (distance = co
ut, vecteur = direction) qui lui indique les nuds atteints via ses
voisins avec le co
ut de chaque chemin. Un nud diffuse son DV periodiquement ou quand il le
met à jour.
Etapes
dun protocole vecteur de distance
1. calculer le co
ut 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 nud envoie periodiquement à ses voisins :
le nombre de sauts qui le separe dune destination donnee,
le prochain saut vers cette destination .
rajoute les routes directement dans la table de routage.
1.1.2
Counting-to-infinity
A-B-C-D, quand A est mort, B recoit une information de C indiquant que A est à deux
sauts de C, mais cela en passant par B, mais B ne le sait pas. C envoi son DV à B, B detecte
que C peut atteindre A en 2 sauts, ainsi lui met à jour son DV en indiquant quil peut atteindre
A en 3 sauts, et ainsi de suite jusquà arriver à linfini.
Une solution sera de ne pas envoyer le vecteur de distance de A à B parce que C passe par
B pour atteindre A. Une autre solution sera de rajouter un numero de sequence comme fait le
protocole DSDV.
1.1.3
Etat
de liens
Echanges
periodiques avec tout le reseau. Chaque nud informe tout le reseau de sa liste
de voisins, ainsi tous les nuds sont capables de construire la carte du reseau en considerant
uniquement les liens bidirectionnels. La construction de carte du reseau permet à un nud de
construire une table de routage en appliquant un algorithme de plus court chemin sur la carte
comme Dijkstra.
Etapes
dun protocole
etat de liens
1. connatre les voisins directs `
a laide des HELLO,
2. donner un co
ut `
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 nud envoie des informations consernant :
ses liens avec ses voisins,
letat de chaque lien .
ces informations sont diffusees `
a tous les nuds du reseau,
chaque nud 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 à partir dun nud
donne dans le graphe pour atteindre les autres nuds. Les etapes à suivre sont les suivantes :
1. on demarre du noeud source et on considère que le co
ut vers tous les autres noeuds vaut
,
2. on commence par marquer les co
uts des arretes qui sortent du nud,
3. on choisit ensuite comme prochain saut le nud avec le co
ut le plus petit,
4. on continue `
a partir du nud choisi et on marque le co
ut cumule pour atteindre les nuds
directement lies `
a ce dernier,
5. on revient `
a letape 3 jusquon aura atteint lensemble des nuds.
1.2
Protocoles proactifs
Les routes pour lensemble des destinations du reseau sont mises à jour periodiquement. Une
vision globale du reseau est toujours disponible.
Avantage(s) :
e
6
2
11
C
14
9
15
10
A
7
Fig. 1.1 Un exemple dun graphe.

Nud en cours
A
B
C
E
B
7/A
7/A
7/A
7/A
C
9/A
9/A
9/A
9/A
D
22/B
20/C
20/C
E
14/A
14/A
11/C
11/C
F
20/E
Tab. 1.1 Dijkstra applique au graphe de la figure 1.1.

diminue le delai avant denvoyer 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-Point
Relay). Ce sont les nuds qui permettent datteindre lensemble des voisins à deux sauts.
Ceci diminue la surcharge due `
a la diffusion à lensemble des voisins (un nud envoie les
messages de donnees uniquement aux MPR), et diminue la taille des echanges des listes des
voisins en se limitant aux MPR. Chaque nud diffuse à lensemble du reseau la liste de nuds
layant elu comme MPR (messages TC).
Int
er
et des MPR
Innondation sans MPR : un nud retransmet un message si et seulement si il ne la pas dejà
recu.
Innondation avec MPR : un nud retransmet un message si et seulement si il ne la pas dejà
recu et il vient de le recevoir dun nud dont il est MPR.
Echanges
p
eriodiques
Des messages HELLO avec les voisins à un saut. Ces messages contiennent la liste des
voisins `
a un saut qui permettent de choisir les MPR.

e
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 nuds layant elu comme
MPR. Ces messages permettent de construire une image du reseau avec tous les nuds
et un sous ensemble de liens.
1.3
Protocoles r
eactifs
Contrairement au mode proactif, les routes sont etablies a` la demande. Une requete de
decouverte de route vers une destination donnee est propagee sur le reseau quand le nud a
besoin de lui envoyer un message.
Avantage(s) :
Diminue la surcharge du reseau, il ny a pas de trafic periodique dentretient des tables
de routage `
a propager sur le reseau.
Desavantage(s) :
Plus de delai avant lenvoi dun message en attendant la decouverte dune route,
Risque de saturation `
a cause dinnondations multiples.
1.3.1
Exemple : AODV
Ad hoc On-demande Distance Vector.

Des messages HELLO sont echanges avec les voisins à un saut pour surveiller les liens avec
ces derniers. Au bout de 4 messages HELLO non recus dun voisin, le lien est considere perdu.
Un nud qui cherche `
a envoyer un message à une destination dont il ne connat pas le
` chaque saut intermediaire la route
chemin envoie une RREQ Route REQuest en broadcast. A
vers la source est construite pour que le nud ayant la reponse puisse retransmettre la reponse
en unicast. Chaque nud intermediaire rajoute son identite sur le chemin.
Un nud nayant pas recu la requete avant, ne connat pas la destination et nest pas luimeme la destination, envoie le message à son tour en broadcast. Sur le chemin de retour, tous
les nuds intermediaires sont capables de stocker le chemin vers la destination.
Le chemin le plus court est choisi si plusieurs RRESP Route RESPonse sont recues. Les
chemins 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 à la source
et les nuds intermediaires suppriment cette route de leurs tables de routage respectives. La
e
source declenche une nouvelle RREQ.

S
HELLO
RREQ
RREP
Data
RERR
Fig. 1.3 Echanges

de trames avec AODV.
1.4
Protocoles hi
erarchiques
Les protocoles hierarchiques ont ete proposes pour reduire la taille des tables de routage dans
les reseaux très larges. Ceci en decoupant le reseau en regions. Chaque region est connectee `
a
une autre region `
a travers un ou plusieurs nuds. Ce decoupage reduit la taille des tables de
routage parce quelles ne contiennent que les nuds de la region du nud.
Fig.
1.4
Configuration
plate.
ler.com/html/how routing algorithms work.html)
1.5
(source
http
://ntwebresel-
Protocoles hybrides
Les protocoles hybrides sont utulises dans un reseau decoupe en zone. Ils emploient un
protocole proactif dans la zone et un protocole reactif pour les communications inter-zones.

e
Destination
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
Prochain saut
B
C
B
B
B
B
B
C
C
C
C
C
C
C
C
C
Co
ut
1
1
2
3
3
4
5
5
6
5
4
4
3
4
2
3
Tab. 1.2 Table de routage de A.
Fig.
1.5
Configuration
hierarchique.
ler.com/html/how routing algorithms work.html)
Destination
B
C
Region 2
Region 3
Region 4
Region 5
Prochain saut
B
C
B
C
C
C
(source
http
://ntwebresel-
Co
ut
1
1
2
2
3
4
Tab. 1.3 Table de routage de A.

e
1.5.1
Exemple : ZRP
Avec ZRP Zone Routing Protocol les requetes de routes sont plus rapides (par rapport `
a
un protocole reactif) car les informations des zones sont dejà disponibles gr
ace au protocole
proactif. Il est plus simple de garder une vision de la topologie dune zone que pour le reseau
entier.
Chaque nud definit sa propre zone. Les nuds à 3 sauts du nud 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 IntErzone Routing Protocol.
IARP est un protocole proactif qui echange des messages HELLO pour maintenir la liste
des voisins et des routes vers les voisins appartenant à la zone.
` la place des Broadcast, ZRP utilise les Bordercast. Bordercast Resolution Protocol (BRP)
A
utilise les informations fournies par IARP pour atteindre les nuds periferiques.
NDP
Neighbor Discovery Protocol (NDP) met à jour les tables de IARP, IERP utilise les tables
de IARP, IERP relaie les route requeste avec BRP. BRP utilise les tables de IARP pour orienter
les requetes.
Si la destination est dans la zone, la route est donnee par IARP, sinon une requete est faite
par IERP. Une requete de route est envoyee aux nuds periferiques avec BRP. Et ceci jusquà
atteindre la destination.
Deux techniques pour renvoyer la reponse en unicast :
Les nuds intermediaires rajoutent leurs adresses dans la requete, comme fait AODV.
Les informations concernant le prochain saut sont stockees dans les nuds, ceci evite de
surcharger les trames de requete et de reponse.
BRP atteint les nuds periferiques avec un multicast, moins co
uteux quun 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.

e
10
Fig. 1.7 Architecture de ZRP. (source : Nicklas Beijar, Zone Routing Protocol (ZRP))
Exemple denvoi
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 une
requete aux nuds periferiques avec BRP. I ne le trouve pas dans sa zone, I envoie une requete
à ses nuds periferiques.
T recoit la requete et trouve X dans sa zone. T rajoute le chemin de lui vers X au chemin
construit dans la requete et renvoie une reponse avec le chemin complet.
1.6
Protocoles g
eographiques
Dans un protocole geographique, le but est de reduire la zone de diffusion de la requete de

route pour diminuer la surcharge du reseau due au trafic de contr
ole des protocoles de routage.
La position est donnee gr
ace `
a un système de GPS.

e
11
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 nud estime la position de son destinataire en fonction de son ancienne position à un instant donne et sa vitesse. Ceci donne une zone
dun rayon donne (calcule gr
ace `
a la vitesse du nud : R = vitesse (t1 t0 ).) et de centre la
dernière position connue. Cette zone est appelee expected zone (zone susceptible).
Zone de requete : elle est plus grande que la zone susceptible. Ce sont uniquement les
noeuds appartenant `
a cette zone qui diffusent la requete de route. La raison est que si la source
nappartient pas `
a la zone estimee, elle doit atteindre la zone en passant par des noeuds qui
nappartiennent pas `
a la zone susceptible.
Plus la zone de requete est grande plus la probabilite de trouver une reponse est grande
mais plus le trafic de contr
ole est grand.
Fig. 1.10 Zone de requete et zone destimation : source à lexterieure. (source : Young-Bae
Ko 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 nud recoit la requete il diffuse le message uniquement sil est dans la zone. Quand
e
12
Fig. 1.11 Zone de requete et zone destimation : source à linterieure. (source : Young-Bae Ko
and 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 ou
max etant connue.
La source inclut la distance Ds entre elle la destination et la dernière position connue de
la destination. Quand un noeud intermediaire recoit la requete il la diffuse si et seulement
si : a Ds + b Di . Ensuite, il remplace la distance dans la requete par Di . De cette
facon un noeud forward la requete si et seulement si il est plus proche de la destiantion
que celui de qui il a recu la requete.
Pour inclure une estimation derreur sur la position connue, dans la première methode
R = erreur + v (t1 T0 ). Dans la deuxième methode les valeurs de a et b sont fixees en fonction
de lerreur estimee. Les noeuds intermediaires peuvent recalculer la zone de requete avant de
diffuser la requete.
La table de positions : une entree par nud dont la position est connue. Quand un nud
souhaite connatre la position dun autre nud il verifie sa table de positions, sil ne trouve pas
une entree correspondante, il diffuse sur le reseau une requete de route. Les nuds ecoutent les
reponses et mettent `
a jour leurs tables.

e
13
Chapitre 2
Les techniques de routage dans les

r
Un nud capteur est constitue de 4 entites essentielles à son fonctionnement :
une entite de captage (son, temperature, humidite, intensite, vibration, pression, mouvement, pollution...),
un micocontr
olleur,
une source denergie,
une antenne de communication.
Un luxe sera de trouver un GPS ou un moyen de mobilite.
Fig. 2.1 Un nud capteur. (source : Classification and comparision of routing protocols in
wireless sensor networks, UbiCC Journal Volume 4)
2.1
Domaines dapplication des r

Nous pouvons citer les domaines suivants : militaire, environnemental, domestique, sante,
securite, ecologie, tracabilite, etc. Des exemples dapplications potentielles dans ces differents
domaines sont exposes ci-dessous.
14
WAN
R
eseau
Reseau de capteurs sans fil
Passerelle
Unite de contr
ole
Fig. 2.2 Un exemple dun reseau de capteurs sans fil.
2.1.1
Applications militaires
Le deploiement rapide, lauto-configuration et la tolerance aux pannes des reseaux de capteurs sont des caracteristiques qui font de ce type de reseaux un outil appreciable dans un tel
domaine. Deploiement sur un endroit strategique ou difficile daccès, afin de surveiller toutes
les activites des forces ennemies ou danalyser le terrain avant dy envoyer des troupes (par la
detection dagents chimiques, biologiques ou de radiations, par exemple).
2.1.2
Applications li
ees `
a la s
ecurit
e
Diminuer considerablement les depenses financières consacrees à la securisation des lieux et

à la protection des etres humains tout en garantissant des resultats plus fiables.
(i) la detection des alterations dans la structure dun b
atiment, suite à un seisme ou au
vieillissement, par des capteurs integres dans les murs ou dans le beton,
(ii) la surveillance des mouvements afin de constituer un système de detection dintrusions
distribue. Laspect distribue rend plus complexe la possibilite de mettre hors dusage ce système
de surveillance.
2.1.3
Applications environnementales
(i) la dispersion de thermo-capteurs à partir dun avion sur une foret pour signaler un
eventuel debut dincendie dans le champ de captage,
(ii) le semis de nuds capteurs en meme temps avec les graines dans les champs agricoles
pour pouvoir identifier les zones sèches et rendre lirrigation plus efficace,
(iii) le deploiement de nuds capteurs sur les sites industriels, les centrales nucleaires ou dans
les 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 court
pour permettre une intervention efficace.
2.1.4
Applications m
edicales
Surveillance permanente des patients et une possibilite de collecter des informations physiologiques de meilleure qualite facilitant ainsi le diagnostic de maladies gr
ace à des micro-capteurs
e
15
qui pourront etre ingeres ou implantes sous la peau.

(i) les micro-cameras qui peuvent etre ingerees et sont capables, sans avoir recours à la
chirurgie, de transmettre des images de linterieur dun corps humain,
(ii) la creation dune retine artificielle composee dune centaine de micro-capteurs pour
ameliorer la vision de lil.
2.1.5
Applications
ecologiques
Lintegration de plusieurs micro-capteurs dans le système de climatisation et de chauffage

des immeubles. Ainsi, la climatisation ou le chauffage ne sont declenches quaux endroits o`
u il y
a des personnes presentes et seulement si cest necessaire. Le système distribue peut aussi maintenir une temperature homogène dans les pièces. Utilisee à grande echelle, une telle application
permettrait probablement de reduire la demande mondiale en energie.
2.1.6
Applications de tracabilit
e et de localisation
Suite à une avalanche il est necessaire de localiser les victimes enterrees sous la neige en
equipant les personnes susceptibles de se trouver dans des zones à 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 système de GPS
(Global Positionning System), les reseaux de capteurs peuvent etre très utiles dans des endroits
clos comme les mines par exemple.
2.2
Contraintes
Un WSN ideal doit passer `

a lechelle, etre robuste, econome en energie, offrir des performances reseaux raisonnables en terme de delai et taux de perte, etre fiable, pas chère et ne
demande pas de maintenance `
a long terme. Un peu trop exigeant ! !
Trois limitations essentielles : energie, calcul et portee.
2.2.1
Rappel : diff
erences entre MANET et WSN
1. WSN collecte de donnees, MANET plus orientes calcul distribue,

2. nombre de nuds dans WSN plus grand que celui des MANET,
3. WSN limitation en calcul et energie, MANET sont rechargeable et plus puissants,
4. WSN deployes de facon ad hoc mais peu mobiles alos que MANET sont mobiles,
5. debit limite en WSN par rapport au MANET.
2.2.2
Crit`
eres `
a prendre en compte
1. Tolerance aux pannes : maintenir lactivite du reseau meme si des nuds sont morts (piles,
panne, conditions physiques, etc.),
2. Passage `
a lechelle : dixaines, centaines et meme des milliers de nuds,
3. Co
uts : n*1000*co
ut dun nud,
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 evènement, à la demande, hybride,
7. Aggregation de donnees : min, max, moyenne (moins de transmission),
e
16
8. Qualite de service : duree de vie, delai, taux de perte, latence, energie. . .

9. Surcharge : trafic de contr
ole, calcul,
10. Deploiement du reseau : aleatoire, predefinit, etc.
2.3
2.3.1
Pr
eambule
Flooding
Pour prendre en compte les faibles capacites de calcul des nuds capteurs, les protocoles
de routage les plus simples sont ceux qui sont bases sur le flooding. En revanche, ceci cree
une duplication de paquets, les nuds recoivent plusieurs fois le meme paquet. Les nuds ne
prennent pas en compte la limitation energetique.
2.3.2
Gossiping
Limite la diffusion en choisissant un seul nud voisin pour lui envoyer le message. Non prise
en compte de la limitation energetique et reception multiple de la meme donnee. Possibilite de
tourner en boucle.
2.3.3
Conlusion
Necessite dun protocol de routage.
2.4
Classification des protocoles de routage des r

Hierarchique ou plat : dans plat tous les nuds sont du meme niveau, type et capacite, hierarchique certains sont plus puissants que dautres, certains peuvent avoir des
taches que les autres nont pas. On parle de cluster dans hiearchique et chef de cluster
(aggregation des donnees provenant dun meme cluster).
Data centric : requete de collecte dun 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 quil est difficile davoir des identifiants comme les adresses MAC
ou IP pour pouvoir communiquer entre les nuds capteurs. Ne demandent pas un mecanisme
dadressage. Les informations sont propagees de proche en proche.
Envoient une annonce des donnees avant denvoyer les donnees elles-memes, les voisins interesses 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 nuds interesses repondent par une REQ (REQuest) et ensuite les donnees
sont envoyees. Point fort : connaissance se limite au voisinage à un saut.
Ne garantie pas la reception des donnees : si le nud destinataire ne se trouve pas à portee
dun nud qui annonce lenvoi, les donnees ne seront jamais transmises.

e
17
Direct Diffusion
Cest linverse de SPIN : les nuds interesses par une donnee diffusent une requete. Les
nuds voisins prennent en compte cette requete, repondent en fonction et rediffusent à leur tour
la requete. Ceci suppose une connaissance geographique du reseau pour orienter les requetes
dans les regions o`
u la donnee recherchee est censee etre produite.
2.4.2
Procotoles hi
erarchiques
Construction de clusters (groupe de nuds) avec un chef par cluster qui se chargera de
transmettre les messages generes par son cluster aux autres chefs de clusters pour atteindre la
destination finale. Le choix du chef de cluster (cluster head) est fait soit à tour de r
ole, soit
selon le nombre de voisins en considerant comme cluster head le nud avec le plus de voisins,
soit selon le niveau de lenergie residuelle...
LEACH
Low Energy Clustering Hierarchy. 5% des nuds sont elus pour etre des chefs de clusters.
Election
periodique des chefs de clusters en fonction du % de nombre de cluster, nombre de tour
depuis lequel le nud na pas ete chef de cluster. TDMA est utilise dans le cluster et CDMA
entre les clusters. Aggregation des donnees generees dans un cluster limite la redondance et la
consommation energetique.
Suppose que les chefs de clusters sont capables datteindre la station de base qui recolte
tout.
TEEN
Threshold sensitive Energy Efficient Network protocol. Transmettre uniquement quand la
valeur detectee est superieure `
a un certain seuil fixe par le chef de cluster. Ensuite, un nud
ne transmet pas la meme donnee tant que sa valeur na pas change dun seuil de variation
(aussi fixe par le chef de cluster). TEEN adopte plusieurs niveau de clusters : clusters de chef
de clusters.
Nest pas adapte pour la surveillance periodique. Une extension APTEEN (Adaptive Threshold sensitive Energy Efficient Network protocol) support deux types de generation trafic :
periodique et critique (depassement dun seuil).
La complexite est au niveau de la creation des clusters et la definition des seuils.
En consommation energetique TEEN moins quAPTEEN, et APTEEN consomme moins
que LEACH.
2.4.3
Protocoles bas
es sur la position
Dans les reseaux de capteurs, on considère que la position du nud est plus importante que
son identite (adresse). Ce type de protocoles considèrent que les nuds connassent leur position
respective et sont capables de connatre la position des autres nuds. Ainsi, cette information
est 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 nud connat le co
ut pour atteindre chaque region. Lacheminement des packets suit
les etapes suivantes :

e
18
1. acheminer le paquet jusquà la region, en envoyant le paquet au nud le plus proche de

la region parmi ses voisinset ayant le niveau denergie residuelle le plus eleve (fonction de
distance et denergie),
2. acheminer le paquet dans la region de destination par une sorte de diffusion si le nombre de
nud nest pas eleve, sinon la region est decoupee en sous-region et le paquet est tranmis
individuellement `
a chaque sous-region.
Chaque paquet contient la region destination. Chaque nud connat sa position, son energie
residuelle, la position et lenergie residuelle de ses voisins (à la demande). Un lien existe entre
2 nuds quand ils sont `
a portee et leur niveau denergie leur permet deffectuer lenvoi.
2.4.4
Protocoles bas
es sur la QoS
Dans ce type de protocoles, les performances du reseau sont prises en compte pour garantir
un delai de bout-en-bout raisonnable qui repond aux besoins de lapplication. Cest surtout le
cas des applications indutrielles et militaires.
SAR
Sequential Assignment Routing. Base sur la contruction darbre à partir des voisins du puits.
Les liens de chaque arbre sont choisis en fonction du delai observe et de lenergie residuelle des
nuds. Les donnees sont associees `
a un niveau de priorite.
La creation des arbres est assez lourde.
SPEED
Une metrique supplementaire par rapport à GEAR : le delai.
Se base sur une table de positions. Il estime le delai sur chaque saut en calculant le delai
daller-retour (en retranchant le temps de traitement cote recepteur). Le prochain saut est choisi
parmi les voisins qui sont plus proches de la destination que le nud.

e
19
Chapitre 3
Les protocoles MAC dans les WSN

3.1
Exemples de protocoles MAC pour les r

eseaux de capteurs
sans fil
Un protocole MAC pour les reseaux de capteurs sans fil doit trouver le bon compromis
entre leconomie denergie, laspect temps reel et lauto-configuration. Dans cette partie, nous
presentons quelques protocoles MAC proposes pour les reseaux de capteurs sans fil presentes
selon leur type. Nous avons identifie trois types : les protocoles bases sur un sequencement temporel, 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. A
noter que ces protocoles sont les plus etudies dans la litterature et non pas forcement les plus
performants : il sagit de protocoles de base et parfois sujets à optimisation.
3.1.1
Economie
d
energie
Les sources de consommation denergie sur un nud capteur sont le module radio, le microprocesseur et le capteur. La communication radio est souvent la plus consommatrice parmi les
trois. La consommation dun capteur varie dans une très large plage selon son type. Un capteur
consommant beaucoup denergie est souvent alimente par sa propre source energetique. Nous
considerons ici que la couche MAC est concernee uniquement par lutilisation du module radio
et du microprocesseur.
Dans un reseau de capteurs, la portee est de lordre dune dizaine de mètres dans un milieu
clos avec une puissance demission de 0 dBm (1 mW ). Avec ce niveau de puissance demission,
lenergie consommee pour la reception et celle consommee pour lemission sont quasiment egales.
Le tableau 3.1 montre un exemple denergie consommee pour chaque etat du module radio dune
carte B2400ZB-tiny.
Un protocole MAC econome en energie essaie dutiliser le moins souvent possible le module
radio. Les modules radio peuvent avoir plusieurs niveaux de consommation quand ils ne sont
pas en mode emission ou reception, moins le nud consomme moins il est reactif, cest pour
cela que les differents etats de sommeil existent pour assurer une flexibilite selon le degre de
reactivite demande par la couche MAC.
Lutilisation inutile du module provient de 5 sources essentielles : le Overhearing, les collisions, le Idle listening, les envois infructueux et les messages de contr
ole.
20

Etat
Energie
consomm
ee
Emission
Reception
ou ecoute
Veille
Sommeil
26 mA
29 mA
15 A
3 A
Tab. 3.1 Energie

consommee par etat par le composant radio dune carte B2400ZB-tiny.
Overhearing
Loverhearing est la reception par un nud dune trame qui ne lui est pas destinee. Lenergie
consommee pour la reception et le traitement des donnees de cette trame est perdue et sans
aucun interet.
Collisions
Les collisions sont `
a la fois une source de degradation des performances du reseau et de perte
denergie. Les pertes de trames `
a cause des collisions forcent les nuds à retransmettre le meme
paquet plusieurs fois et donc `
a rester actif pour le repeter et verifier quil est bien recu par la
` noter que les retransmissions ne se font que pour les trames envoyees en mode
destination. A
unicast (à un seul destinataire) et avec une demande dacquittement.
Idle listening
Cest lattente dune trame par le module radio. Cela arrive quand il a ete demande à un
nud detre eveille mais quil ne recoit aucune trame et nen transmet aucune non plus. Meme
si le nud ne transmet pas et ne recoit pas, le fait que son module radio soit active et pret pour
recevoir consomme autant denergie que pour la reception.
Envois infructueux
Cela arrive quand un nud essaie de communiquer avec un autre nud qui nest plus accessible parce quil est en mode sommeil par exemple (ou hors de portee). Le nud emetteur est
en attente dun acquittement, et il retransmet donc la meme trame plusieurs fois. Il consomme
de lenergie en le faisant du fait quil soit reste en mode transmission et en mode reception pour
leventuel acquittement.
Overhead
LOverhead constitue les messages de contr
ole et tout bit utilise pour encapsuler des donnees
utiles à lapplication. Cet Overhead genere par la couche MAC, a pour but dassurer le bon
fonctionnement de la methode daccès mais cela amplifie les 4 sources de consommation `
a
contre-temps.

e
21
3.1.2
Protocoles bas
es sur un s
equencement temporel
Les protocoles MAC appliquant un sequencement temporel decoupent le temps en slots,

chaque slot de temps est alloue (localement) à un seul nud pour lui garantir laccès au canal
afin quil puisse transmettre ses donnees. La methode TDMA est un exemple de methode de
sequencement temporel dans les reseaux sans fil.
Ces protocoles sont generalement economes en energie car ils evitent les collisions, ils limitent
le idle listening et le overhearing, et mettent les nuds en mode sommeil durant les slots de
temps reserves aux autres nuds. De plus, ils garantissent un delai borne de bout-en-bout si
un algorithme dallocation prend en compte les caracteristiques du trafic. En revanche, laspect
centralise et le besoin dune synchronisation rendent ce type de protocoles rigide et non-adapte
pour les topologies dynamiques et mobiles.
Par la suite, nous decrivons brièvement les protocoles TRAMA, FLAMA et LEACH.
TRAMA
TRAMA (TRaffic-Adaptive Medium Access control) divise le temps en slots de temps et
se base sur le trafic annonce par les nuds pour designer les emetteurs et les recepteurs pour
chaque slot de temps. Pour ce faire, TRAMA applique trois mecanismes :
un protocole de voisinage appele NP (Neighbor Protocol) pour echanger la liste des voisins
à un saut entre les nuds, ce qui permet detablir une connaissance des voisins à deux
sauts,
un protocole dechange de calendriers appele SEP (Schedule Exchange Protocol) o`
u chaque
nud annonce ce quil a comme trafic à envoyer en precisant les recepteurs concernes,
un protocole delection adaptative AEA (Adaptative Election Algorithm) qui choisit les
emetteurs et les recepteurs pour un slot de temps donne en fonction des informations
collectees par NP et SEP.
TRAMA decoupe le temps en alternant des intervalles de temps à accès planifie et des intervalles de temps `
a accès aleatoire. Chaque intervalle est constitue de slots de temps. TRAMA
commence par des intervalles `
a accès aleatoire pour permettre au reseau de setablir. Les
echanges pour la decouverte de voisinage du protocole NP sont effectues durant les intervalles `
a
accès aleatoire. Ces intervalles servent aussi pour permettre aux nouveaux nuds de rejoindre
le reseau. Lenvoi de trames de donnees se fait durant les intervalles à accès planifie.
1
0
0
1
0
1
0
1
0
1
0
1
Accès planifie
1
0
0
1
0
1
0
1
0
1
0
1
Accès aleatoire
1
0
0
1
0 Basculement entre actif/inactif
1
Fig. 3.1 Decoupage temporel de TRAMA pour un nud du reseau.
Pour realiser son decoupage temporel, TRAMA a besoin que chaque nud diffuse son calendrier de trafic et fasse une decouverte de voisinage à deux sauts.
3.1.3
FLAMA
FLAMA (FLow-Aware Medium Access) est propose comme une amelioration de TRAMA.
Comme TRAMA, FLAMA divise le temps selon deux modes dactivite : intervalles de temps `
a
accès planifie et intervalles de temps a` accès aleatoire. FLAMA a aussi besoin de connatre le
e
22
voisinage dun nud `

a deux sauts et des informations concernant le flux de donnees des voisins
à un saut.
En revanche, FLAMA ne diffuse pas de calendriers de trafic durant les intervalles de temps `
a
accès planifie mais echange durant les intervalles de temps à accès aleatoire des informations par
rapport aux flux de donnees lies `
a lapplication. En outre, FLAMA etablit une synchronisation
globale du reseau base sur lestampillage des trames et une topologie arborescente pour le relais
de donnees.
Pour determiner les emetteurs et les recepteurs concernes par chaque slot de temps lors de
lintervalle à accès planifie, FLAMA applique un algorithme plus simple que celui utilise dans
TRAMA. Comme TRAMA, FLAMA assure des transmissions sans collision en ne permettant
quà un seul nud demettre dans un voisinage à deux sauts.
Accès planifie
Accès aleatoire
Fig. 3.2 Decoupage temporel de FLAMA.

FLAMA est plus performant que TRAMA en terme deconomie denergie et de perte de
trames. De plus, FLAMA ameliore le delai de bout en bout par rapport à TRAMA gr
ace
à lexploitation des routes definies `
a partir dun arbre pour le cheminement multi-sauts. En
revanche, FLAMA surcharge le reseau par des echanges pour connatre le flux de lapplication
et etablir une synchronisation globale du reseau de proche en proche.
3.1.4
E-MAC, L-MAC et AI-LMAC
E-MAC (Event MAC) decoupe le temps en slots, chaque slot est lui-meme decoupe en
trois parties respectivement prevues pour accueillir les requetes de communication, le trafic de
contr
ole et le trafic de donnees. E-MAC definit trois types de nuds : les nuds actifs possedant
un slot, les nuds passifs ne possedant pas de slot et ne transmettant quaprès avoir fait une
requete pour utiliser le slot dun voisin durant la partie dediee aux requetes de communication
du slot du voisin, et les nuds dormants qui dorment la plupart du temps et choisissent un
mode passif ou actif quand ils se reveillent. Chaque nud diffuse une information concernant
les slots utilises par ses voisins durant la partie trafic de contr
ole de son slot. Les nuds doivent
tous se reveiller durant la partie trafic de contr
ole des slots de leurs voisins.
Lallocation des slots commence par une station de base qui choisit un slot et annonce ce
choix par une diffusion. Ensuite, ses voisins choisissent aleatoirement un slot. En cas de choix
dun meme slot, les nuds signalent ce fait durant la partie trafic de contr
ole. Les slots sont
reutilises à partir de trois sauts.
L-MAC (Lightweight-MAC) adopte le meme mecanisme dallocation de slots et de decoupage
temporel que E-MAC. En revanche, L-MAC force tous les nuds a` avoir au moins un slot.
Ainsi, la partie requete de communication du slot nest plus presente dans L-MAC et un slot
est fractionne en 2 parties seulement.
AI-LMAC (Adaptive, Information-centric and Lightweight MAC) est une amelioration de
L-MAC qui prend en compte les conditions du trafic applicatif et offre la possibilite aux nuds
davoir plusieurs slots. AI-LMAC regroupe les nuds avec des relations père-fils. Le père surveille
les conditions de trafic de ses fils et demande à ses fils de sallouer plus de slots ou de se desallouer
des slots selon leur charge.
La figure 3.3 montre le decoupage temporel en slots des trois protocoles.
e
23
0
1
E-MAC
000
111
00
11
11111111111111111111111111
00000000000000000000000000
000
111
00
11
L-MAC et AI-LMAC
00
11
000
111
11111111111111111111111111
00000000000000000000000000
00
11
000
111
Requete de communication
Trafic de contr
ole
Donnees
Fig. 3.3 Decoupage temporel de E-MAC, L-MAC et AI-MAC.
3.1.5
Protocoles bas
es sur la contention
Dans ce type de protocoles MAC, les nuds accèdent au medium durant le meme intervalle
de temps en utilisant un algorithme de la famille CSMA/CA, chacune de ses variantes essayant
deviter les collisions.
Le point fort de ce type de protocoles est sans doute lextensibilite et le passage à lechelle.
En revanche, ces protocoles noffrent pas de delai borne du fait quils ne garantissent pas laccès
au medium dès que la charge du reseau augmente.
Nous allons commencer cette partie en decrivant brièvement lalgorithme de CSMA/CA de
la norme IEEE 802.11 en mode DCF, sur lequel est basee la plupart des protocoles qui exploitent
de 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 daccès de la meme famille que CSMA/CD (Carrier Sense
Multiple Access with Collision Detection) puisquelle impose à un emetteur de sassurer que le
canal est libre avant demettre. Dans CSMA/CA, les collisions ne peuvent pas etre detectees
comme dans le CSMA/CD, un nud essaie deviter les collisions (sans vraiment les eviter à 100
%). Ceci à cause de leffet daveuglement du medium sans fil (Near Far Effect) qui empeche une
entite de recevoir quand elle est en train demettre.
Rappel : Clear Channel Assessment, zone dinterf
erences
Zone dinterference
C
Portee
A
B
Seuil de detection de porteuse
-82 dBm
Seuil de reception
-95 dBm
Fig. 3.4 Portee et zone dinterference.
Terminal cach
e et terminal expos
e
e
24
Fig. 3.5 A et C envoient simultanement deux messages à B et genèrent un risque de collision

en B.
Fig. 3.6 A communique avec D. B veut communiquer avec C mais ne le fait pas parce que A
occupe le medium, alors que si B communique avec C aucune collision naura lieu.

e
25
3.1.6
S-MAC, T-MAC et D-MAC
S-MAC (Sensor-MAC) est concu pour assurer une methode daccès econome en energie pour
les reseaux de capteurs sans fil. Pour ce faire, les nuds se mettent en mode sommeil pendant
une certaine duree et se reveillent pour ecouter le medium pendant une autre duree.
Les nuds echangent leur calendrier de periodes decoute en le diffusant à leurs voisins `
a
un saut. Ainsi, chaque nud connat le calendrier de ses voisins et sait quand il faut se reveiller
pour communiquer avec un nud `
a sa portee. Plusieurs nuds peuvent avoir le meme intervalle
de temps comme periode decoute. Les nuds accèdent au medium en utilisant le CSMA/CA
de IEEE 802.11 avec le mecanisme RTS/CTS. En outre, un champ supplementaire est ajoute
à tous les messages (y compris les messages RTS/CTS et les acquittements) indiquant la duree
de lechange, ce qui permet aux nuds non concernes de dormir pendant cette duree.
Pour maintenir une synchronisation des horloges, les nuds emetteurs envoient des messages
de synchronisation SYNC au debut de la periode decoute de leurs voisins.
ecoute
SYNC
Recepteur A
ecoute
sommeil SYNC
ecoute RTS
Emetteur
B SYNC
RTS
envoi de donnees
si CTS recu
Emetteur
C
RTS
envoi de donnees
si CTS recu
SYNC
ecoute RTS
Fig. 3.7 Sequencement des periodes decoute et de sommeil dans S-MAC.

T-MAC (Timeout-MAC) propose de mettre un nud en mode sommeil après un temps TA
durant lequel le nud na recu aucun message. Ainsi, T-MAC reduit lidle listening par rapport
à S-MAC.
S-MAC
sommeil
T-MAC
sommeil
sommeil
TA
sommeil
TA
TA
Fig. 3.8 Sequencement des periodes decoute et de sommeil de T-MAC et de S-MAC.

Avec cette approche, T-MAC fait dormir un nud sans setre assure que ses voisins nont
plus de donnees `
a lui envoyer. En effet, les donnees à envoyer du voisin ont pu etre retardees `
a
cause dun echec daccès au canal.
Early sleep : Ce probl`
eme est appel
e le sommeil pr
ematur
e.
D-MAC (Data gathering MAC) propose un sequencement des periodes dactivite qui favorise la collecte dinformations dans une topologie arborescente. Les nuds de meme niveau se
reveillent en meme temps.

e
26
3.1.7
LPL : B-MAC, WiseMAC, B-MAC+, X-MAC et DW-LPL
Le LPL (Low Power Listening) est lune des premières approches pour reduire lidle listening
en introduisant une periode dinactivite au niveau de la couche physique. Lidee est de penaliser
les emetteurs en envoyant un preambule long pour economiser lenergie des recepteurs. Les
recepteurs activent leur module radio periodiquement pour detecter la presence dun preambule.
La duree de transmission du preambule doit etre de la meme longueur que lintervalle entre deux
reveils dun recepteur.
Preambule
Envoi de donnees
Reveil periodique
Reception
du preambule
Reception des donnees
Fig. 3.9 LPL : Lemetteur utilise un long preambule pour permettre au recepteur dactiver
son module radio seulement de temps en temps.
Lun des premiers protocoles MAC pour les reseaux de capteurs sans fil bases sur cette
technique est B-MAC (Berkeley-MAC).
WiseMAC a ete propose pour reduire la longueur du preambule en fonction des periodes de
reveil des recepteurs voisins.
B-MAC+ ameliore B-MAC en remplacant le long preambule par plusieurs petits messages
appeles des paquets de countdown contenant chacun lidentifiant du destinataire et le temps
restant pour commencer lenvoi des donnees.
X-MAC decompose lui aussi le long preambule en plusieurs preambules de petite taille
incluant lidentifiant du destinataire du message. Contrairement à B-MAC+, le destinataire
previent lemetteur de son ecoute avec un acquittement envoye entre deux preambules consecutifs.
Lemetteur peut alors commencer la transmission des donnees. Cela reduit loverhead au niveau
de lemetteur qui arrete la transmission du preambule dès la reception de lacquittement.
DW-LPL (Dual Wake-up LPL) limite le problème de loverhearing en employant la technique du LPL pour les messages diffuses uniquement. Lenvoi de messages unicast utilise une
technique de signalement par des trames specifiques envoyes par les recepteurs pour informer
leur entourage quils sont prets `
a recevoir des trames en unicast. Les instants et la periodicite
denvoi des messages de signalement sont independants dun nud à lautre.
3.1.8
Protocoles hybrides
Une troisième famille de protocoles propose de combiner les deux methodes : TDMA et
CSMA/CA. Ainsi, ces protocoles essaient davoir les avantages des deux methodes en alternant
les deux dans le temps ou en les combinant dune manière intelligente. Dans la suite, nous allons
decrire 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/CA
selon le nombre dentites en concurrence en un instant donne. Z-MAC utilise un decoupage temporel base sur TDMA et gère les accès 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 `
a
deux sauts suivie par une assignation de slots aux nuds en utilisant DRAND (Distributed RanGerard Chalhoub, Clermont Universit
e
27
domized TDMA Scheduling For Wireless Adhoc Networks). DRAND est un protocole distribue
qui assure quun slot de temps nest pas assigne à deux nuds situes à moins de trois sauts
lun de lautre. La synchronisation necessaire est obtenue à laide de deux protocoles utilises de
facon complementaire.
Pour acceder au medium, si le nud est le proprietaire du slot courant, il attend un temps
aleatoire plus petit quune 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 actuel
appartient à un voisin `
a deux sauts et si le nud a recu une indication de forte contention dun
de ses voisins `
a deux sauts, le nud na pas le droit dutiliser ce slot. Sinon, il attend un temps
aleatoire compris entre To et Tno avant deffectuer un CCA.
B
To Tno
To Tno
11
00
00
11
T
11
00
00
11
00
11
T
11
00
00
11
00
11
Tno
Tno
To Tno
1
0
0
1
11
00
00
11
T
11
00
00
11
00
11
Tno
Fig. 3.10 Decoupage temporel de Z-MAC. Notons lexistence dun temps pendant lequel le
medium nest pas utilise.
Z-MAC utilise la technique LPL. Comme les nuds peuvent emettre durant tous les intervalles, les nuds ecoutent le medium periodiquement pour verifier sil y a des emissions qui les
concernent.
G-MAC
G-MAC (Gateway MAC) organise les echanges à linterieur dun cluster. Dans ce domaine,
un cluster est un ensemble de nuds gere par une station appelee passerelle. G-MAC decoupe
le temps en deux periodes : une periode de collecte o`
u les echanges se font en CSMA/CA, et
une periode de distribution o`
u les echanges se font en TDMA.
Durant la periode de collecte, les nuds envoient à leur passerelle deux types de trafic : les
requetes FRTS (Future Request To Send) pour reserver un slot de temps dans la periode de
distribution pour echanger avec dautres nuds appartenant au meme cluster, et le trafic intercluster destine aux nuds appartenant à des clusters differents. Durant un slot, les echanges
se font selon le sequencement RTS-CTS-donnees-acquittement. La periode de distribution commence par une diffusion dun message GTIM (Gateway Traffic Indication Message) qui contient
les indications temporelles des deux periodes suivantes ainsi que le sequencement des echanges
entre les nuds du cluster qui ont reussi à envoyer une requete FRTS.
Pendant la periode de collecte et pendant les slots non reserves de la periode de distribution la
passerelle echange les donnees inter-cluster avec dautres passerelles une fois la collecte terminee.

e
28
Periode de collecte
GTIM
Echanges
de RTS (donnees inter-cluster )
Requetes FRTS (donnees intra-cluster )
Echanges
entre passerelles
11
00
00
11
00
11
00
11
00
11
00
11
Periode de distribution
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 detranglement dont
souffrent la plupart des applications des reseaux de capteurs. Ce phenomène survient quand
une station du reseau joue le r
ole dun puits de donnees vers lequel un ensemble de capteurs
dirige son trafic. Cela est represente sur la figure 3.12 sur laquelle est identifiee une zone à forte
charge.
CSMA/CA
TDMA et CSMA/CA
Zone `
a forte charge
Goulot detranglement
Puits
Fig. 3.12 Gestion du goulot detranglement dans Funneling-MAC.

Funneling-MAC adopte une methode daccès en CSMA/CA dans lensemble du reseau durant un intervalle de temps suivi par un intervalle de temps durant lequel une methode daccès
en TDMA est utilisee pour la zone `
a forte charge uniquement pour offrir plus de temps daccès
aux nuds à proximite du puits. Ces deux intervalles de temps constituent une supertrame. Ce
decoupage est represente sur la figure 3.13.
La zone `
a forte charge est dimensionnee par une diffusion dun beacon par le nud puits.
Les nuds qui ne recoivent pas ce beacon appliquent le CSMA/CA.
Le puits se base sur le chemin parcouru par les trames quil recoit pour definir le sequencement
et le dimensionnement des slots TDMA alloues aux nuds de la zone à forte charge. Seuls les
nuds appartenant `
a la zone `
a forte charge mettent à jour le chemin parcouru par une trame.
Pour eviter que les nuds qui se trouvent au del`
a de la zone a` forte charge interfèrent avec le
decoupage temporel du TDMA et le beacon transmit par le nud puits, les nuds de la zone `
a
e
29
ts
CSMA/CA TDMA
Beacon
Beacon
Supertrame
CSMA/CA TDMA
Supertrame
Fig. 3.13 Decoupage temporel dans Funneling-MAC.

forte charge genèrent periodiquement une trame contenant les informations concernant la duree
de la periode CSMA/CA, la duree de la periode TDMA et le nombre de supertrames jusquau
prochain beacon.

e
30
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 frequence
et la modulation.
Fr
equence
(MHz)
Modulation
868/868.6
868/868.6
868/868.6
902/928
902/928
902/928
2400/2483.5
BPSK
ASK
O-QPSK
BPSK
ASK
O-QPSK
O-QPSK
D
ebit
(kb/s)
20
250
100
40
250
250
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 associe
un seuil de reception qui va jusquà 92 dBm.1
Avec les trois plages de frequences, la couche physique offre 27 canaux de transmission
differents dont 16 sur la plage de frequences de 2400/2483.5 M Hz separes de 5 M Hz, 10 sur
la plage de frequences de 902/928 separes de 2 M Hz et 1 canal sur la plage de frequences de
868/868.6 M Hz. Lusage de ces canaux depend de la legislation des pays dans lesquels des
solutions conformes `
a ce standard sont utilisees.
Parmi les fonctionnalites de contr
ole de cette couche, nous pouvons disposer de celles qui
permettent de :
activer et desactiver le module radio,
remonter letat dun lien `
a la couche superieure,
tester loccupation du canal en faisant un CCA,
choisir le canal de transmission.
1`
A noter que le debit utilise pour lenvoi des trames de donnees par la couche physique de la norme IEEE
802.11 est de 11 M bits/s, ce qui donne un seuil de reception de 82 dBm. Le seuil de detection de porteuse est
de 95 dBm.
31
4.1.1
Activation et d
esactivation du module radio
Le module radio possède trois etats de fonctionnement : un etat de transmission, un etat de

reception et un etat de sommeil. Le temps de changement detat entre transmission et reception
ne doit pas depasser les 192 s. Cet etat est pilote par la couche MAC. Il est essentiel pour
economiser de lenergie de mettre le module en mode sommeil.
4.1.2
Indication de la qualit
e du lien
Le LQI (Link Quality Indication) caracterise la qualite dun lien à un instant donne suite `
a
une reception dune trame. Ce paramètre est essentiel pour les protocoles des couches reseau et
application. Par exemple, un protocole de routage peut exploiter cette indication afin didentifier
les meilleurs liens `
a utiliser dans son choix de routes.
4.1.3
Test doccupation du m
edium ou CCA (Clear Channel Assessment)
Le CCA permet de savoir letat du canal radio. Il est essentiel pour le fonctionnement de
lalgorithme de CSMA/CA de la couche MAC. La couche physique est capable deffectuer trois
modes de CCA differents :
La detection dun signal avec une puissance recue superieure à un certain seuil.
La detection dun signal conforme à la modulation de la couche physique.
La detection dun signal qui repond aux deux conditions.
` noter que le seuil de detection dactivite est typiquement -95 dBm.
A
4.1.4
S
election du canal
Comme la couche physique offre plusieurs canaux de transmission, il est necessaire de

selectionner un canal precis, ceci `
a la demande des couches superieures. Le changement de
canal est aussi fait implicitement par la couche physique suite à une demande de scrutation sur
lensemble des plages de frequences chacune constituant un canal de transmission. Cette action
est 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 applicatifs : le mode suivi de beacon et le mode non suivi de beacon. En mode suivi de beacon, le
coordinateur envoie periodiquement un beacon pour synchroniser lactivite des entites qui lui
sont attachees selon une structure de supertrame donnee sur la figure 4.1. En mode non suivi
de 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 MAC
802.15.4 :
laccès au medium,
les scans, la creation du reseau et lassociation,
la synchronisation avec un coordinateur,
les echanges de trames.
4.2.1
Acc`
es au m
edium
Un coordinateur limite laccès au medium en utilisant la diffusion de beacon delimitant des

supertrames. La structure de la supertrame est definie par les deux paramètres BI (Beacon Interval) qui definit lintervalle qui separe deux beacons consecutifs et SD (Superframe Duration)
e
32
qui definit la duree de la supertrame.

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

BI = aBaseSuperf rameDuration.2BO ,
SD = aBaseSuperf rameDuration.2SO ,
avec 0 SO BO 14, aBaseSuperframeDuration est un attribut de la couche MAC qui
definit la duree de la supertrame quand SO = 0 (15.36 ms pour valeur par defaut pour aBaseSuperframeDuration). aBaseSuperf rameDuration = aBaseSlotDurationaN umSuperf rameSlots,
avec aBaseSlotDuration le nombre de symboles (un symbole vaut 4 bits) constituant un slot de la
supertrame quand SO = 0. aBaseSlotDuration a 60 comme valeur par defaut. aN umSuperf rameSlots
est le nombre de slots qui constituent la supertrame, il vaut 16.
La portion active de la supertrame est decoupee en aNumSuperframeSlots slots de temps
egaux et est composee de trois parties : le beacon, la CAP (Contention Access Period) et la
CFP (Contention Free Period). Durant la CAP toutes les stations sont en competition pour
acceder au medium alors que la CFP est constituee de slots de temps, appeles GTS (Guaranteed
Time Slot) alloues `
a chaque station pour communiquer avec le coordinateur.
Le debut du premier slot est linstant denvoi du beacon. La CAP suit la fin de transmission
du beacon et la CFP, si elle est presente, suit immediatement la fin de la CAP. Si un coordinateur
ne souhaite pas appliquer la structure de la supertrame, il initialise les valeurs de BO et de SO
à 15. Dans ce cas, nous nous retrouvons dans un PAN en mode non suivi de beacon.
CAP
CFP
111
000
00
11
000
111
00
GTS 11
GTS
periode dinactivite
000
111
00
11
1111111111111111111111111111111111
0000000000000000000000000000000000
00011
111
00
0 1 2 3 4 5 6 7 8 9 101112131415
beacon
beacon
SD (periode dactivite)
BI
Fig. 4.1 La structure de la supertrame.
La figure 4.1 montre un exemple dune supertrame incluant un periode de CAP, une periode
de CFP contenant deux GTS de tailles differentes et une periode dinactivite (car BO = SO+1).
Laccès au medium durant la CAP pour toute trame, sauf les acquittements et les beacons,
est gere selon lalgorithme de CSMA/CA slotte. Avant tout envoi, lentite doit sassurer de
pouvoir finir la transaction (incluant la reception dun acquittement sil est demande) et de
pouvoir attendre un IFS (InterFrame Space) 2 avant la fin de la CAP. Si ce nest pas le cas,
lenvoi est reporte `
a la CAP de la supertrame suivante. Lenvoi de trames durant les slots
reserves au GTS seffectue sans CSMA/CA.
2
La duree dun IFS depend de la longueur du MPDU (MAC Protocol Data Unit) de la trame envoyee, ce qui
correspond `
a la payload physique. Quand cette longueur depasse 18 octets, le IFS vaut 40 symboles, sinon, le IFS
vaut 12 symboles

e
33
Algorithme de CSMA/CA slott

e
Lalgorithme de CSMA/CA slotte est applique pour lenvoi dune trame durant la periode
CAP de la supertrame, sauf pour lenvoi des trames de beacon et des trames dacquittement.
Lalgorithme se base sur une unite de temps appele periode de backoff, une periode de backoff
est egale à aUnitBackoffPeriod symboles, soit 20 symboles. La synchronisation est basee sur un
decoupage du temps en intervalles `
a trois niveaux differents et imbriques : des supertrames, ellememe decoupees en slots, eux-meme decoupes en periode de backoff. Les frontières des periodes
de backoff de CSMA/CA pour chaque entite sont alignees avec les frontières des slots de la
supertrame. Le debut de la première 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 `
a
la frontière dune periode de backoff. Ainsi, toute les entites sont synchronisees entre-elles sur
les periodes de backoff.
La figure 4.2 montre la hierarchie du decoupage temporel et lalignement des periodes de
backoff avec les slots de la supertrame. Nous avons considere le cas o`
u BO = SO = 0, ce qui
nous donne un slot de supertrame durant 0,96 ms. Dans ce cas, chaque slot de supertrame
contient trois periodes de backoff. La supertrame montree sur la figure 4.2 ne comporte pas de
CFP.
CAP
beacon
Une periode de backoff
Un slot de la supertrame
Fig. 4.2 Les periodes de backoff et les 16 slots de la supertrame.

Lalgorithme de CSMA/CA slotte est une variante de CSMA/CA qui exploite une synchronisation precise pour se dispenser de surveiller en permanence loccupation du medium, ce qui
consomme beaucoup denergie. Il est base sur trois paramètres essentiels : NB, BE et CW. NB
(Number of Backoffs) est le nombre de fois o`
u lentite a applique lalgorithme pour essayer
denvoyer la trame courante. BE (Backoff Exponent) est lexposant de backoff qui definit la
longueur de lintervalle dans lequel il faut tirer un backoff. CW (Contention Window) definit le
nombre de periodes de backoff consecutives à la fin desquelles le canal doit etre detecte libre
avant de commencer la transmission.
La figure 4.3 presente une version simplifiee des differentes etapes de lalgorithme de CSMA/CA
slotte. La première etape est la phase dinitialisation. Lalgorithme commence avec BE =
macM inBE, N B = 0 et CW = 2. Une fois les paramètres initialises, letape 2 consiste à localiser la frontière de la prochaine periode de backoff et à attendre un nombre entier de periodes de
backoff tire aleatoirement dans lintervalle [0; 2BE 1]. Si la duree du backoff tire est plus longue
que le nombre restant de periodes de backoff dans la CAP, lalgorithme consomme le backoff
jusquà la fin de la CAP et reporte ce qui lui reste pour la CAP de la supertrame suivante.
Après la consommation de ce backoff, la couche MAC verifie que le nombre restant de
periodes de backoff dans la CAP est suffisant pour effectuer 2 CCA, transmettre la trame
e
34
physique et recevoir un eventuel acquittement. Si cest le cas, letape 3 est appliquee. Dans
cette etape, la couche MAC demande a` la couche PHY deffectuer un CCA à la frontière de la
prochaine periode de backoff. Si le temps restant dans cette supertrame est suffisant, la couche
MAC reporte le CCA au debut de la CAP de la prochaine supertrame, en commencant avec
un tirage de backoff pour eviter les collisions systematiques dues à plusieurs reports de CCA
effectues par differentes entites.
Si la couche PHY detecte que le canal est libre, la couche MAC decremente CW, puis teste
si CW est nul. Si cest le cas, la couche MAC demande à la couche PHY de commencer la
transmission `
a la frontière de la prochaine periode de backoff. Si CW nest pas nul, la couche
MAC demande `
a la couche PHY de faire un autre CCA. Le medium nest donc pas scrute en
permanence, mais cest deux CCA consecutifs positifs qui permettent de conclure que le medium
est libre 3 .
Si la couche PHY detecte que le canal est occupe, la couche MAC incremente NB et
BE de 1 (à condition que BE reste inferieur ou egal à macM axBE) et remet CW à 2.
Si N B = macM axCSM ABackof f s, lalgorithme renvoie un echec daccès. Cest alors à la
couche MAC de demander une retransmission de la meme trame tant que le nombre de tentatives est plus petit que macMaxFrameRetries (macM axF rameRetries = 3 par defaut). Si
N B < macM axCSM ABackof f s, lalgorithme retourne à letape 2.
Le mode BLE (Battery Life Extension) : le coordinateur de PAN peut decider de faire
travailler le reseau en mode BLE pour economiser davantage de lenergie. Un bit specifique est
reserve dans le beacon `
a cet effet. Quand ce bit est mis à 1, les entites associees à ce coordinateur
doivent acceder au medium en respectant un IFS suivi dune duree de macBattLif eExtP eriods
après la reception du beacon.
macBattLif eExtP eriods est un entier qui correspond à un nombre de periodes de backoff,
qui est calcule en fonction de trois termes : (i) la valeur maximum dun backoff tire dans une
fenetre avec BE = 2, cela vaut 3 periodes de backoff, (ii) la duree de CCA, ce qui fait 2
periodes de backoff, et (iii) la duree de transmission du preambule physique et du champ de
synchronisation de len-tete physique, cela fait, pour la frequence de 2.4 GHz, une longueur de
5 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 dans
un reseau en mode BLE doit envoyer sa trame dans les 6 periodes de backoff qui suivent lIFS
après la reception du beacon. Le coordinateur et toutes les autres entites se mettent en mode
sommeil si aucune trame nest transmise avant cette duree.
Algorithme de CSMA/CA non-slott
e
Lalgorithme de CSMA/CA non-slotte est applique pour les envois de trames dans un reseau
en mode non suivi de beacon. Pour autant, il ne sagit pas de CSMA/CA de la norme IEEE
802.11. Le paramètre CW nexiste pas dans lalgorithme de CSMA/CA non-slotte : il suffit de
detecter une seule fois que le canal est libre pour commencer une transmission. Lunite du temps
reste la periode de backoff, mais lactivite des entites nest pas synchronisee sur ces periodes de
backoff.
La figure 4.4 presente les differentes etapes du CSMA/CA non-slotte. Lalgorithme commence par la phase dinitialisation en mettant BE = macM inBE et N B = 0. Puis, elle tire
aleatoirement un nombre entier de periodes de backoff. Après la consommation du backoff,
la couche MAC demande `
a la couche PHY deffectuer un CCA. Si la couche PHY detecte
le canal libre, la couche MAC commence la transmission. Si ce nest pas le cas, la couche
MAC incremente N B et BE (`
a condition que BE reste inferieur ou egal à macM axBE).
3
Dans le cas du CSMA/CA de la norme 802.11, la scrutation du canal est faite durant le backoff

e
35

Etape
1
Initialisation : BE = macM inBE, N B = 0 et CW = 2
Etape
2
Localiser la frontière de
la prochaine periode de backoff
Tirage de backoff dans [0; 2BE 1]
Etape
3
Effectuer un CCA
Canal libre ?
non
oui
NB = NB + 1
BE = min(BE + 1, macM axBE)
non
CW = CW 1
NB >
macMaxCSMABackoffs
CW = 0 ?
oui
non
oui
Echec
Succès
Fig. 4.3 Diagramme de lalgorithme de CSMA/CA slotte de la norme IEEE 802.15.4.

e
36
Si N B < macM axCSM ABackof f s, lalgorithme revient au tirage de backoff. Si N B =

macM axCSM ABackof f s, lalgorithme renvoie un diagnostic dechec daccès. Cest alors `
a
la couche MAC de demander une retransmission de la meme trame tant que le nombre de tentatives est plus petit que macMaxFrameRetries (macM axF rameRetries vaut 3 par defaut).
Initialisation BE = macM inBE et N B = 0
Tirage de backoff dans [0; 2BE 1]
Effectuer un CCA
Canal libre ?
non
NB = NB + 1
BE = min(BE + 1, macM axBE)
oui
non
NB >
macMaxCSMABackoffs
oui
Succès
Echec
Fig. 4.4 Diagramme de lalgorithme de CSMA/CA non-slotte de la norme IEEE 802.15.4.
4.2.2
Les scans, la cr
eation du r
eseau, les associations et la synchronisation
Les scans
Afin de decouvrir les reseaux existants à portee, de creer un reseau, de sassocier à un reseau
ou de se synchroniser avec un reseau, la couche MAC effectue un des quatre types de scans
suivants :
Le scan denergie permet de recuperer lenergie maximum detectee sur chaque canal. Ce
scan est utilise par un coordinateur souhaitant creer un PAN afin de choisir le canal
convenable.
Le scan actif permet de recuperer la liste des identifiants de PAN existants. Le scan
actif suit la diffusion de requete de beacon. Un coordinateur fonctionnant selon un mode
non suivi de beacon repond `
a cette requete par une diffusion de beacon. Un coordinateur
fonctionnant selon un mode suivi de beacon lignore et continue à envoyer ses beacons
periodiquement. Ce scan est utilise par un coordinateur souhaitant creer un PAN pour

e
37
choisir le bon identifiant de PAN, ou par une station qui cherche à sassocier à un PAN
(dont elle connat lidentifiant).
Le scan passif comme pour le scan actif, permet de recuperer la liste des identifiants
de PAN existants. En revanche, la station nenvoie pas une requete de beacon mais elle
effectue une ecoute passive de chaque canal à scanner pour une duree donnee. Ce scan est
utilise par une station qui cherche à sassocier à un PAN.
Le scan dorphelin permet `
a une station de retrouver son coordinateur après une perte de
synchronisation avec ce dernier.
Cr
eation du r
eseau
La couche superieure envoie une requete à la couche MAC pour effectuer un scan actif sur
une liste de canaux afin de decouvrir les reseaux existants à portee. Une fois le bon canal choisi,
la couche superieure decide dun identifiant de PAN et demande à la couche MAC dinitier un
PAN avec cet identifiant.
Association et d
esassociation
Après avoir effectue un scan (passif ou actif) et remonte le resultat d
u à la couche superieure,
cette dernière demande `
a la couche MAC de sassocier à un PAN specifique en precisant son
identifiant PAN et ladresse du coordinateur correspondant. Suite à cette demande, la couche
MAC genère une requete dassociation à destination du coordinateur.
` la reception dune requete dassociation, la couche MAC du coordinateur remonte linforA
mation à la couche superieure et cest à celle-ci de decider daccepter ou pas cette requete en
fonction des ressources quil lui reste par exemple. La reponse à cette requete dassociation est
envoyee en mode de transmission indirecte (voir le paragraphe 4.2.3).
Suite à une requete de desassociation envoyee par la couche superieure, la couche MAC
envoie une indication de desassociation au coordinateur pour linformer que la station souhaite se desassocier du PAN. De meme, la couche superieure dun coordinateur peut decider de
desassocier une station qui lui est associee, elle lui envoie alors une commande de desassociation
pour linformer de ce fait.
Synchronisation avec le beacon du coordinateur
Dans le mode suivi de beacon, les entites restent synchronisees au reseau gr
ace à la transmission periodique dune trame de beacon par le coordinateur. Le tableau 4.2 montre les differents
champs de ce beacon.
Toute station appartenant `
a un beacon-enabled PAN doit pouvoir se synchroniser avec le
beacon de son coordinateur pour connatre la structure de la supertrame, et aussi pour recuperer
les 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 MAC
detecte une perte de synchronisation et indique ce constat à la couche superieure.
La couche MAC rejette toute trame de beacon dont ladresse source ou lidentifiant du PAN
ne correspondent pas `
a ladresse du coordinateur ou à lidentifiant du PAN auquel la station est
associee, respectivement.
4.2.3
Echange
de donn
ees
Dans la primitive de requete de transmission de donnees envoyee par la couche superieure, un

champ (txOptions) specifie dans quel mode de transmission des donnees doivent etre transmises.

e
38
Octets :
2
Frame
control
Numero PAN
de
ID
sequence source
2/8
0/5/6/
10/14
Adresse Entete Specifsource securite ications

de
la
supertrame
variable variable variable
Champs
de GTS
Liste des
adresses
en
attente
Payload MAC
Ent
ete MAC
Payload
FCS
Footer
MAC
Tab. 4.2 Format du beacon de la norme IEEE 802.15.4.

Les trois modes dechange sont : echange direct, echange indirect, echange en GTS. Ce champ
specifie aussi si la trame de donnees doit etre acquittee ou pas.
Echange
direct
Durant la CAP, la station essaie denvoyer la trame en CSMA/CA slotte. En cas de transmission avec demande dacquittement, la couche MAC fait macMaxFrameRetries tentatives
(par defaut 3 tentatives) si lacquittement nest pas recu au bout de macAckWaitDuration 4
Echange
indirect
Pour favoriser laspect economie denergie, les stations feuilles initient la communication avec
leur 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 en
attente chez lui, (ii) dans un PAN en mode non suivi de beacon, la station feuille sollicite le
coordinateur pour verifier sil a des trames en attente pour elle.
Le coordinateur conserve les trames en attente pour une duree de macTransactionPersistenceTime avant de les supprimer si la station concernee ne la pas sollicite pour les recuperer.
Echange
en GTS
Lallocation des GTS est faite uniquement par le coordinateur du PAN. Un GTS est alloue
soit en mode reception (du coordinateur du PAN vers la station) soit en mode emission (de la
station vers le coordinateur du PAN).
Une station demande lallocation dun GTS auprès du coordinateur du PAN auquel elle est
affiliee. Le nombre maximal de GTS est limite à 7, à condition que la duree de la CAP restante
reste superieure ou egale `
a aMinCAPLength (aM inCAP Length = 7 ms pour la frequence de
2.4 GHz).
La reponse dune requete de GTS est envoyee dans le beacon via des descripteurs de
GTS. Cette information est gardee dans le beacon pour aGTSDescPersistenceTime (par defaut
aGT SDescP ersistenceT ime = 4) beacons consecutifs.
4
macAckW aitDuration = aU nitBackof f P eriod + aT urnaroundT ime + phySHRDuration + 6

phySymbolsP erOctet, o`
u aU nitBackof f P eriod = 320 s, aT urnaroundT ime = 192 s, phySHRDuration =
128 s (pour la frequence de 2.4 GHz), 6 represente le nombre doctets de len-tete PHY incluant la longueur de
la payload PHY de lacquittement.

e
39
La desallocation dun GTS peut etre faite soit à la demande de la couche superieure de la
station ayant le GTS, soit par la couche superieure du coordinateur du PAN suite au constat
que la station na plus utilise son GTS durant 2 n supertrames consecutives5 .
n = 28BO si 0 BO 8, n = 1 si 9 BO 14.

e
40
Chapitre 5
ZigBee
5.1
Couche r
eseau ZigBee
La couche reseau de ZigBee est restee compatible avec la couche MAC IEEE 802.15.4 en assurant des fonctionnalites complementaires et compatibles avec celles de la couche MAC. Il sagit
soit de fonctionnalites liees `
a la transmission de donnees, comme lencapsulation des donnees
applicatives et le choix du prochain saut du cheminement du paquet, soit de fonctionnalites
liees à la gestion, comme la gestion des tables de routage, la configuration de la topologie et
lallocation des adresses logiques.
5.1.1
Cr
eation de la topologie
Comme pour la couche MAC IEEE 802.15.4, la couche reseau supporte deux types de topologies : topologie en etoile et topologie maillee. Un cas particulier dune topologie maillee est la
topologie 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 beacon
trois paramètres essentiels que chaque coordinateur doit respecter et qui definissent la topologie
41
en arbre du reseau. Ces trois paramètres sont :

la profondeur maximale du reseau (Lm),
le nombre maximal de fils par coordinateur (Cm),
le nombre maximal de fils coordinateurs par coordinateur (Rm) .
` noter que si Lm = 1 nous nous retrouvons dans une topologie en etoile.
A
5.1.2
Allocation des adresses
Avant detre associee au reseau, une entite na que son adresse MAC IEEE, appelee adresse
longue. Cette adresse occupe 8 octets. Afin doptimiser la taille des champs dadressage dans les
trames echangees, la couche reseau alloue une adresse courte logique qui noccupe que 2 octets.
Il existe deux mecanismes pour cette allocation : une allocation dadresses hierarchiques et une
allocation dadresses aleatoires.
Allocation dadresses hi
erarchiques
Lallocation des adresses courtes se fait en se basant sur la profondeur du coordinateur et sur
` chaque coordiles trois paramètres Lm, Rm et Cm. Ce mecanisme dallocation est distribue. A
nateur est confie une plage dadresses selon sa profondeur. Letendue de cette plage dadresses
est appelee Cskip. Cskip pour une profondeur d donnee est calcule selon la formule suivante :
si Rm = 1,
1 + Cm (Lm d 1)
Cskip(d) =
1+CmRmCmRmLmd1
sinon
1Rm
Les adresses sont allouees differemment selon le type de la station qui sassocie :
AdrC = AdrP + 1 + nbC Cskip(d),
AdrF = AdrP + Rm Cskip(d) + n
o`
u AdrC designe ladresse allouee pour un nouveau coordinateur, AdrP ladresse du père,
AdrF ladresse allouee pour une nouvelle feuille, nbC le nombre actuel de coordinateurs fils, n
est un entier superieur `
a 1 incremente suite à chaque nouvelle association dune feuille (1 n
(Cm Rm)).
Prenons le cas o`
u 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 :
Cskip
Profondeur
0
1
2
3
21
6
1
0
Tab. 5.1 Valeurs de Cskip pour lexemple (3, 3, 5).

` noter quun coordinateur de profondeur Lm naccepte aucune association. En appliquant
A
le jeu de paramètres (3, 3, 5) au le cluster-tree de la figure 5.1, nous obtenons les adresses
donnees sur la figure 5.2 pour chaque station.
e
42
45
62
27
44
23
48
43
0
22
65
64
41
1
2
Coordinateur du PAN
8
Coordinateur
Feuille
Fig. 5.2 Allocation des adresses hierarchiques sur un exemple. Le coordinateur 1 par exemple,
qui est à la profondeur 1, a alloue ladresse 2 à son premier fils et 8 au deuxième, 8 = 2+Cskip(1).
Allocation dadresses al
eatoires
Dans le mode dallocation dadresses aleatoires, les paramètres Lm, Rm, Cm et la profondeur
nont plus deffet sur le choix dune adresse courte. Après avoir accepte lassociation dune entite,
le coordinateur choisit aleatoirement une adresse courte, en verifiant que cette adresse ne soit
presente dans aucune entree de sa table NIB (Network layer Information Base). Les eventuelles
conflits dadresses sont detectes et resolus par un mecanisme supplementaire.
5.1.3
Routage
Tout coordinateur qui possède des capacites de routage, maintient une table de routage
qui sera utilisee pour determiner le prochain saut pour les paquets qui sont à destination des
stations qui se trouvent hors portee du coordinateur. Nous allons nous limiter à detailler le
routage hierarchique uniquement.
Routage hi
erarchique
Lallocation dadresses hierarchiques offre la possibilite dappliquer un routage hierarchique.
Les coordinateurs nayant pas une strategie de routage particulière appliquent le routage hierarchique.
Ce routage ne demande pas dechanges supplementaires pour trouver les routes, ni la construction de tables de routage.
Les routes utilisees pour acheminer les paquets dans un routage hierarchique sont uniquement les routes de larbre. Pour determiner le prochain saut dans un routage hierarchique le
coordinateur applique un algorithme qui retourne ladresse du prochain saut en fonction de son
adresse et ladresse de la destination finale du paquet.
Nous designons par Adr ladresse du coordinateur qui cherche à router le paquet selon le
routage hierarchique, d sa profondeur, AdrP ladresse de son père, DestF inale ladresse de la
destination finale du paquet et Dest ladresse du prochain saut.

e
43

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

si DestF inale > Adr + Rm Cskip(d),
alors Dest = DestF inale,
inale(Adr+1)
sinon Dest = Adr + 1 + DestF Cskip(d)
Cskip(d),
sinon Dest = AdrP
Si DestF inale est comprise entre Adr et Adr + Cskip(d 1), la destination finale est un
descendant du coordinateur. Si ce nest pas le cas, le coordinateur remonte le paquet à son père
en mettant Dest = AdrP .
Si la destination finale est un descendant, le coordinateur verifie si elle est une de ses feuilles.
Si cest le cas, il met Dest = DestF inale. Si la destination finale nest pas une feuille, pour
trouver le fils vers lequel il va router le paquet, le coordinateur applique la formule Dest =
inale(Adr+1)
Cskip(d).
Adr + 1 + DestF Cskip(d)
5.2
Couche application ZigBee
La couche application de ZigBee est constituee de la sous-couche APL (APplication subLayer), du ZDO (ZigBee Device Object) et de lApplication Framework contenant des profils
predefinis. La figure 5.3 represente les trois entites de la couche application.
Application framework
Objet
Objet
applicatif ... applicatif
1
240
APSDE-SAP APSDE-SAP
ZDO
APSDE-SAP
Couche application
APL
NLDE-SAP
NLME-SAP
Couche reseau
NET
Fig. 5.3 Couche application ZigBee. Linterface entre la couche application est les differents
objets est appelee APSDE pour (APplication Support sub-layer Data Entity).
LAPS (APplication Support) constitue linterface entre la couche reseau dune part, le ZDO
et les objets predefinis dautre part. Nous listons à titre indicatif quelques services offerts par
lAPS : lencapsulation des donnees, la fragmentation et lassemblage de donnees, le cryptage
de donnees et ladressage par groupe.
e
44
LApplication Framework peut supporter 240 objets applicatifs differents sur un meme nud
ZigBee. Lobjet applicatif par defaut est defini dans le ZDO. LApplication Framework permet
aussi de definir des profils applicatifs specifiant des formats de messages et la facon de les traiter
entre un ensemble dobjets applicatifs appartenant à des nuds ZigBee differents. La figure 5.4
represente un exemple de deux nuds ZigBee A et B ayant chacun plusieurs objets applicatifs
(interrupteur 1 et interrupteur 2 appartenant au nud A et lampe 1, lampe 2, lampe 3 et lampe
4 appartenant au nud B). Nous voyons comment lobjet applicatif Int1 (interrupteur 1) peut
communiquer `
a plusieurs objets applicatifs (lampe 1, lampe 2 et lampe 3) gr
ace à une table
de binding qui permet de formaliser les correspondances entre differents objets. Cette table est
partagee par tous les nuds qui partage la meme application. Les objets interrupteurs Int1 et
Int2 et les lampes L1, L2, L3 et L4 appartiennent tous à un meme profil applicatif, ce qui leur
permet de comprendre les messages echanges entre-eux.
Radio
Radio
L1
L2
L3
L4
Int1
Nud B
Int2
Binding Table
Nud A
Fig. 5.4 Exemples dapplication et de profils ZigBee.

e
45

RCSF

Transféré par

Droits d'auteur :

Formats disponibles

RCSF

Transféré par

Informations du document

Description originale:

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

RCSF

Transféré par

Droits d'auteur :

Formats disponibles

Routage et MAC dans les reseaux de capteurs sans fil

Table des mati`

1.1 Vecteur de distance vs Etat

Etapes dun protocole etat de liens . . . .

2 Les techniques de routage dans les r

3 Les protocoles MAC dans les WSN

Gerard Chalhoub, Clermont Universit

Reseaux de capteurs sans fil

Gerard Chalhoub, Clermont Universit

Reseaux de capteurs sans fil

Vecteur de distance vs Etat

Reseaux de capteurs sans fil

Fig. 1.1 Un exemple dun graphe.

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

Gerard Chalhoub, Clermont Universit

Reseaux de capteurs sans fil

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

Ad hoc On-demande Distance Vector.

Reseaux de capteurs sans fil

source declenche une nouvelle RREQ.

Fig. 1.3 Echanges

Gerard Chalhoub, Clermont Universit

Reseaux de capteurs sans fil

Tab. 1.2 Table de routage de A.

Tab. 1.3 Table de routage de A.

Gerard Chalhoub, Clermont Universit

Reseaux de capteurs sans fil

Gerard Chalhoub, Clermont Universit

Reseaux de capteurs sans fil

Dans un protocole geographique, le but est de reduire la zone de diffusion de la requete de

Gerard Chalhoub, Clermont Universit

Reseaux de capteurs sans fil

Reseaux de capteurs sans fil

Gerard Chalhoub, Clermont Universit

Reseaux de capteurs sans fil

Les techniques de routage dans les

Domaines dapplication des r

Reseau de capteurs sans fil

Fig. 2.2 Un exemple dun reseau de capteurs sans fil.

Diminuer considerablement les depenses financi`eres consacrees `a la securisation des lieux et

Reseaux de capteurs sans fil

qui pourront etre ingeres ou implantes sous la peau.

Lintegration de plusieurs micro-capteurs dans le syst`eme de climatisation et de chauffage

Un WSN ideal doit passer `

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

Reseaux de capteurs sans fil

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

Necessite dun protocol de routage.

Classification des protocoles de routage des r

Gerard Chalhoub, Clermont Universit

Reseaux de capteurs sans fil

Gerard Chalhoub, Clermont Universit

Reseaux de capteurs sans fil

1. acheminer le paquet jusqu`a la region, en envoyant le paquet au nud le plus proche de

Gerard Chalhoub, Clermont Universit

Reseaux de capteurs sans fil

Les protocoles MAC dans les WSN

Exemples de protocoles MAC pour les r

Tab. 3.1 Energie