ABSTRACT
T
HE K-mutual exclusion problem is an important legacy
of the mutual exclusion problem in distributed systems and in the AD HOC
networks, this problem has known a constantly evolution in context where many
algorithms have been proposed to solve this problem.
In this thesis, we will first introduce the concept of
distributed systems and the AD HOC networks, which will allow us to focus on
the mutual exclusion problem and its generalization to K resources on the one
hand, and explain the concept of the fault tolerance which can increase the
performance of algorithms on the other hand.
We also present algorithms that treat the K-mutual
exclusion problem, and ensuring the fault tolerance in distributed systems and
the AD HOC networks.
We used the NS-2 simulation tool, to
study the performance of proposed algorithms and to specify the parameters that
influence the performance of these algorithms.
Key-words : Distributed systems, Mobile AD HOC Network
(MANET), Distributed algorithm, Mutual exclusion, K-mutual exclusion,
Simulation, NS-2.
TABLE DEs mATièREs
TABLE DEs mATièREs vi
LisTE DEs FiGuREs x
INTRoDucTioN GéNéRALE
1
|
1
2
|
NoTioNs GéNéRALEs
1.1 SysTèmE
RépARTi
1.1.1 Introduction
1.1.2 Définition
d'un système réparti
1.1.3 Les
caractéristiques d'un système réparti
1.1.4 Les avantages et
les inconvénients
1.1.4.1
Avantages
1.1.4.2
Inconvénients
1.1.5 Problèmes
liés aux systèmes répartis
1.1.6 Conclusion
1.2 LEs RésEAux
AD HOC
1.2.1 Introduction
1.2.2 Réseaux
mobiles sans fil
1.2.2.1
Les réseaux mobiles avec infrastructure
1.2.2.2
Les réseaux mobiles sans infrastructure
1.2.3 Les
réseaux mobiles AD HOC
1.2.3.1
Les caractéristiques des réseaux AD HOC
1.2.3.2
Les avantages des réseaux AD HOC
1.2.3.3
Les inconvénients des réseaux AD HOC
1.2.3.4
Applications des réseaux AD HOC
1.2.3.5
Problèmes liés aux réseaux AD HOC
1.2.4 Problème
de routage dans les réseaux AD HOC
1.2.4.1
Définition du routage
1.2.4.2
Classification des protocoles de routage
1.2.4.2.a
Les protocoles de routage proactifs
1.2.4.2.b
Les protocoles de routage réactifs (à la demande) .
1.2.4.2.c
Les protocoles de routage hybrides
CoNcLusioN
LE pRoBLèmE DE
L'ExcLusioN muTuELLE ET LA ToLéRANcE Aux pANNEs
2.1 LE pRoBLèmE DE
L'ExcLusioN muTuELLE
2.1.1 Introduction
2.1.2 L'exclusion
mutuelle en réparti
|
3
4
4
4
5
5
5
6
7
7
8
8
8
8
9
9
10
11
11
12
14
14
14
14
15
15
15
16
17
18
18
18
|
2.1.2.1
La notion de l'exclusion mutuelle 18
2.1.2.2
Les états d'un processus 19
2.1.2.3
Notions de base 19
2.1.2.4
Propriétés d'un algorithme d'exclusion mutuelle
19
2.1.3 Bref historique
20
2.1.4 Les classes de
solutions d'exclusion mutuelle 20
2.1.4.1
Les algorithmes à permissions 21
2.1.4.1.a
Permissions individuelles 21
2.1.4.1.b
Permissions d'arbitres 21
2.1.4.1.c
Permissions mixtes 22
2.1.4.2
Les algorithmes à jeton 22
2.1.4.2.a
Les algorithmes à diffusion (non structuré) 23
2.1.4.2.b
Les algorithmes à structure logique (Structuré) . . .
23
2.1.5 Synthèse
et conclusion 23
2.2 LE pRobLèME DE LA
K-ExcLusioN MuTuELLE 25
2.2.1 Description du
problème 25
2.2.2 Résolution
du problème 25
2.3 LE pRobLèME DE
L'ExcLusioN MuTuELLE DANs LEs RésEAux AD HOC
25
2.4 LE pRobLèME DE LA
K-ExcLusioN MuTuELLE DANs LEs RésEAux AD HOC .
26
2.5 LA ToLéRANcE Aux
pANNEs 26
2.5.1 Solutions
26
2.5.2 Les types de la
tolérance aux pannes 26
2.5.2.1
Tolérance aux pannes par mémoire stable 27
2.5.2.2
Tolérance aux pannes par duplication 27
CoNcLusioN 28
3 SiMuLATioN DE L'ALgoRiThME
DANs LEs sysTèMEs RépARTis 29
3.1 INTRoDucTioN 31
3.2 L'ALgoRiThME 31
3.2.1 Objectif de
l'algorithme 31
3.2.2 Structure logique
utilisée 31
3.2.3 Principe de
fonctionnement 33
3.2.4 Hypothèses
34
3.2.5 Description de
l'algorithme 34
3.2.5.1
Variables locales 34
3.2.5.2
Les messages utilisés 35
3.2.5.3
Les procédures de l'algorithme 35
3.2.6 Preuve de
l'algorithme 40
3.2.6.1
La K-exclusion mutuelle 40
3.2.6.2
Absence d'interblocage 40
3.2.6.3
Absence de la famine 41
3.2.7 Complexité
de l'algorithme en nombre de messages 41
3.3 RésuLTATs DE
siMuLATioN 42
3.3.1 Les
paramètres de simulation 42
3.3.2 Evaluation de
performance 43
3.3.3 Les étapes
d'un scénario 43
3.3.4 Résultats
et interprétations 44
3.3.4.1
Variation du nombre de requêtes 44
3.3.4.2
Variation du nombre de ressources 44
3.3.4.3
Variation du nombre de sites 45
3.4 AMéLIoRATIoN
N°1 (LE MESSAGE
RECHERCHE) 46
3.4.1 Résultats
et interprétations 47
3.4.1.1
Variation du nombre de requêtes 47
3.4.1.2
Variation du nombre de ressources 47
3.4.1.3
Variation du nombre de sites 48
3.5 AMéLIoRATIoN
N°2 (ANNULER LA MéTHoDE
{UTILISER LE PLUS CoURT CHEMIN}) 48
3.5.1 Résultats
et interprétations 51
3.5.1.1
Variation du nombre de requêtes 51
3.5.1.2
Variation du nombre de ressources 51
3.5.1.3
Variation du nombre de sites 51
3.6 AMéLIoRATIoN
N°3 (ARRêT DES MoUVEMENTS
INUTILES) 52
3.6.1 Résultats
et interprétations 53
3.6.1.1
Variation du nombre de requêtes 53
3.6.1.2
Variation du nombre de ressources 53
3.6.1.3
Variation du nombre de sites 54
3.7 LES CoURBES FINALE ET
CoMPARAISoN 54
3.7.1 Variation du
nombre de requêtes 54
3.7.2 Variation du
nombre de ressources 55
3.7.3 Variation du
nombre de sites 55
3.8 CoNCLUSIoN 55
3.9 LA ToLéRANCE AUX
PANNES 56
3.9.1 L'idée de
base 56
3.9.2 Description de
l'algorithme 56
3.9.2.1
Les variables locales 56
3.9.2.2
Les messages utilisés 56
3.9.2.3
Les procédures de l'algorithme 57
3.9.3 Résultats
et interprétations 58
3.9.3.1
Variation du nombre de requêtes 58
3.9.3.2
Variation du nombre de ressources 58
3.9.3.3
Variation du nombre de sites 58
3.10 AMéLIoRATIoN
(ALGoRITHME ToLéRANT AUX PANNES
AMéLIoRé) 59
3.10.1 Résultats
et interprétations 60
3.10.1.1
Variation du nombre de requêtes 60
3.10.1.2
Variation du nombre de ressources 60
3.10.1.3
Variation du nombre de sites 60
CoNCLUSIoN 62
4 SIMULATIoN DE L'ALGoRITHME
DANS LES RéSEAUX AD HOC 63
4.1 INTRoDUCTIoN 64
4.2 L'ALGoRITHME 64
4.2.1 Hypothèses
du Système 64
4.2.2 Les
procédures de l'algorithme 64
4.2.3 Paramètres
de simulation 69
4.2.3.1
Les paramètres fixes 69
4.2.3.2
Les paramètres variables 69
4.2.4 Résultats
et interprétations 70
4.2.4.1
Variation du nombre de demandeurs 70
4.2.4.2
Variation de la portée de communication 71
4.2.4.3
Variation de la vitesse de mouvement 71
4.2.4.4
Variation du nombre de noeuds 72
4.2.5 Conclusion
72
4.3 ToLéRANcE AuX pANNEs
72
4.3.1 Résultats
et interprétations 73
4.3.1.1
Variation du nombre de demandeurs 73
4.3.1.2
Variation de la portée de communication 73
4.3.1.3
Variation de la vitesse de mouvement 73
4.3.1.4
Variation du nombre de noeuds 74
CoNcLusioN 74
CoNcLusioN ET PERspEcTivEs
75
BibLiogRAphiE 76
A ANNEXE ETuDE DE
L'ouTiL DE siMuLATioN NS-2
79
A.1 PREuvE Du
ThéoRèME TRuc 80
B ANNEXE LEs scRipTs DE Nos
siMuLATioNs 81
B.1 LE scRipT TCL
(sysTèME RépARTi) 82
B.2 LE ScRipT TCL AD
HOC 85
AcRoNyMEs 91
| 
